001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.ssa;
014
015 import java.util.ArrayList;
016 import java.util.Enumeration;
017 import java.util.HashMap;
018 import java.util.HashSet;
019 import java.util.Iterator;
020 import java.util.Set;
021 import org.jikesrvm.VM;
022 import org.jikesrvm.classloader.RVMField;
023 import org.jikesrvm.classloader.FieldReference;
024 import org.jikesrvm.classloader.TypeReference;
025 import org.jikesrvm.compilers.opt.OperationNotImplementedException;
026 import org.jikesrvm.compilers.opt.ir.ALoad;
027 import org.jikesrvm.compilers.opt.ir.AStore;
028 import org.jikesrvm.compilers.opt.ir.BBend;
029 import org.jikesrvm.compilers.opt.ir.GetField;
030 import org.jikesrvm.compilers.opt.ir.GetStatic;
031 import org.jikesrvm.compilers.opt.ir.GuardedUnary;
032 import org.jikesrvm.compilers.opt.ir.Label;
033 import org.jikesrvm.compilers.opt.ir.BasicBlock;
034 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
035 import org.jikesrvm.compilers.opt.ir.IR;
036 import org.jikesrvm.compilers.opt.ir.Instruction;
037 import org.jikesrvm.compilers.opt.ir.InstructionEnumeration;
038 import org.jikesrvm.compilers.opt.ir.Operators;
039 import static org.jikesrvm.compilers.opt.ir.Operators.ARRAYLENGTH_opcode;
040 import static org.jikesrvm.compilers.opt.ir.Operators.ATTEMPT_ADDR_opcode;
041 import static org.jikesrvm.compilers.opt.ir.Operators.ATTEMPT_INT_opcode;
042 import static org.jikesrvm.compilers.opt.ir.Operators.BBEND_opcode;
043 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ALOAD_opcode;
044 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ASTORE_opcode;
045 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_LOAD_opcode;
046 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_STORE_opcode;
047 import static org.jikesrvm.compilers.opt.ir.Operators.CALL_opcode;
048 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ALOAD_opcode;
049 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ASTORE_opcode;
050 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_LOAD_opcode;
051 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_STORE_opcode;
052 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ALOAD_opcode;
053 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ASTORE_opcode;
054 import static org.jikesrvm.compilers.opt.ir.Operators.GETFIELD_opcode;
055 import static org.jikesrvm.compilers.opt.ir.Operators.GETSTATIC_opcode;
056 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ALOAD_opcode;
057 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ASTORE_opcode;
058 import static org.jikesrvm.compilers.opt.ir.Operators.INT_LOAD_opcode;
059 import static org.jikesrvm.compilers.opt.ir.Operators.INT_STORE_opcode;
060 import static org.jikesrvm.compilers.opt.ir.Operators.LABEL_opcode;
061 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ALOAD_opcode;
062 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ASTORE_opcode;
063 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_LOAD_opcode;
064 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_STORE_opcode;
065 import static org.jikesrvm.compilers.opt.ir.Operators.MONITORENTER_opcode;
066 import static org.jikesrvm.compilers.opt.ir.Operators.MONITOREXIT_opcode;
067 import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY_UNRESOLVED_opcode;
068 import static org.jikesrvm.compilers.opt.ir.Operators.NEWARRAY_opcode;
069 import static org.jikesrvm.compilers.opt.ir.Operators.NEWOBJMULTIARRAY_opcode;
070 import static org.jikesrvm.compilers.opt.ir.Operators.NEW_UNRESOLVED_opcode;
071 import static org.jikesrvm.compilers.opt.ir.Operators.NEW_opcode;
072 import static org.jikesrvm.compilers.opt.ir.Operators.PHI;
073 import static org.jikesrvm.compilers.opt.ir.Operators.PHI_opcode;
074 import static org.jikesrvm.compilers.opt.ir.Operators.PREPARE_ADDR_opcode;
075 import static org.jikesrvm.compilers.opt.ir.Operators.PREPARE_INT_opcode;
076 import static org.jikesrvm.compilers.opt.ir.Operators.PUTFIELD_opcode;
077 import static org.jikesrvm.compilers.opt.ir.Operators.PUTSTATIC_opcode;
078 import static org.jikesrvm.compilers.opt.ir.Operators.READ_CEILING_opcode;
079 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ALOAD_opcode;
080 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ASTORE_opcode;
081 import static org.jikesrvm.compilers.opt.ir.Operators.REF_LOAD_opcode;
082 import static org.jikesrvm.compilers.opt.ir.Operators.REF_STORE_opcode;
083 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ALOAD_opcode;
084 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ASTORE_opcode;
085 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_LOAD_opcode;
086 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_STORE_opcode;
087 import static org.jikesrvm.compilers.opt.ir.Operators.SYSCALL_opcode;
088 import static org.jikesrvm.compilers.opt.ir.Operators.UBYTE_ALOAD_opcode;
089 import static org.jikesrvm.compilers.opt.ir.Operators.UBYTE_LOAD_opcode;
090 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_BEGIN_opcode;
091 import static org.jikesrvm.compilers.opt.ir.Operators.UNINT_END_opcode;
092 import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_ALOAD_opcode;
093 import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_LOAD_opcode;
094 import static org.jikesrvm.compilers.opt.ir.Operators.WRITE_FLOOR_opcode;
095 import org.jikesrvm.compilers.opt.ir.Phi;
096 import org.jikesrvm.compilers.opt.ir.PutField;
097 import org.jikesrvm.compilers.opt.ir.PutStatic;
098 import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
099 import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
100 import org.jikesrvm.compilers.opt.ir.operand.LocationOperand;
101 import org.jikesrvm.compilers.opt.ir.operand.Operand;
102
103 /*
104 * This module tracks heap variables needed for Array SSA form.
105 */
106
107 /**
108 * An <code> SSADictionary </code> structure holds lookaside
109 * information regarding Heap Array SSA form for an IR. The general idea
110 * is that all Heap Array SSA form information resides in this lookaside
111 * structure. Note that this is not the case for scalar SSA information.
112 *
113 * <P> See our SAS 2000 paper
114 * <a href="http://www.research.ibm.com/jalapeno/publication.html#sas00">
115 * Unified Analysis of Arrays and Object References in Strongly Typed
116 * Languages </a> for an overview of Array SSA form. More implementation
117 * details are documented in {@link SSA <code> SSA.java </code>}.
118 *
119 * @see SSA
120 */
121 @SuppressWarnings("unchecked")
122 // Generic HeapOperands and HeapVariables make this
123 // impossible to typecheck properly
124 public final class SSADictionary {
125
126 /**
127 * Flag to turn on debugging
128 */
129 private static final boolean DEBUG = false;
130
131 /**
132 * The object for the heap variable that is used for modelling
133 * explicit exception dependencies
134 */
135 static final String exceptionState = "X-State";
136
137 /**
138 * A mapping from <code> Instruction </code> to the set of heap
139 * operands (an <code> HeapOperand[]</code>) that this instruction
140 * uses. Note that PHI instructions <STRONG> do not </STRONG> appear in
141 * this mapping.
142 */
143 private final HashMap<Instruction, HeapOperand<Object>[]> uses =
144 new HashMap<Instruction, HeapOperand<Object>[]>();
145
146 /**
147 * A mapping from <code> Instruction </code> to the set of heap
148 * operands (an <code> HeapOperand[]</code>) that this instruction
149 * defines. Note that PHI instructions <STRONG> do not </STRONG> appear in
150 * this mapping.
151 */
152 private final HashMap<Instruction, HeapOperand<Object>[]> defs =
153 new HashMap<Instruction, HeapOperand<Object>[]>();
154
155 /**
156 * A mapping from <code> HeapKey </code> to the set of heap
157 * variables introduced for this IR
158 */
159 private final HashMap<HeapKey<Object>, HeapVariable<Object>> heapVariables =
160 new HashMap<HeapKey<Object>, HeapVariable<Object>>();
161
162 /**
163 * A mapping from heap variable type to <code> Integer </code>
164 * This structure holds the next number to assign when creating
165 * a new heap variable name for a given type
166 */
167 private HashMap<Object, Integer> nextNumber = new HashMap<Object, Integer>();
168
169 /**
170 * A mapping from <code> BasicBlock </code> to <code> ArrayList
171 * </code> of <code> Instruction </code>.
172 * This map holds the list of heap phi instructions stored as
173 * lookaside for each basic block.
174 */
175 private final HashMap<BasicBlock, ArrayList<Instruction>> heapPhi =
176 new HashMap<BasicBlock, ArrayList<Instruction>>(10);
177
178 /**
179 * An empty vector, used for utility.
180 */
181 private static final ArrayList<Instruction> emptyArrayList = new ArrayList<Instruction>(0);
182
183 /**
184 * A mapping from <code> HeapVariable </code> to <code> HashSet
185 * </code> of <code> HeapOperand </code>.
186 * This map holds the set of heap operands which use each heap
187 * variable.
188 */
189 private final HashMap<HeapVariable<Object>, HashSet<HeapOperand<Object>>> UseChain =
190 new HashMap<HeapVariable<Object>, HashSet<HeapOperand<Object>>>(10);
191
192 /**
193 * A mapping from <code> HeapVariable </code> to <code> HeapOperand </code>.
194 * This map holds the set of heap operands which define each heap
195 * variable.
196 */
197 private final HashMap<HeapVariable<Object>, HeapOperand<Object>> DefChain =
198 new HashMap<HeapVariable<Object>, HeapOperand<Object>>(10);
199
200 /**
201 * The set of instructions which have been registered to potentially
202 * exit the procedure
203 */
204 private final HashSet<Instruction> exits = new HashSet<Instruction>(10);
205
206 /**
207 * A mapping from a heap variable type to a <code> HashSet
208 * </code> of <code> Instruction </code>.
209 * The set of all uses of a heap variable type
210 * <em> before </em> we performed renaming for SSA.
211 */
212 private final HashMap<Object, HashSet<HeapOperand<Object>>> originalUses =
213 new HashMap<Object, HashSet<HeapOperand<Object>>>(10);
214
215 /**
216 * A mapping from a heap variable type to a <code> HashSet
217 * </code> of <code> Instruction </code>.
218 * The set of all definitions of a heap variable type
219 * <em> before </em> we performed renaming for SSA.
220 */
221 private final HashMap<Object, HashSet<HeapOperand<Object>>> originalDefs =
222 new HashMap<Object, HashSet<HeapOperand<Object>>>(10);
223
224 /**
225 * The set of type to build heap array variables for
226 */
227 private final Set<Object> heapTypes;
228
229 /**
230 * Should the heap array SSA form constructed include uphi functions?
231 * That is, does a <em> use </em> create a new name for a heap variable.
232 */
233 private final boolean uphi;
234
235 /**
236 * Should PEIs and stores to the heap be modelled via an explicit exception
237 * state heap variable?
238 */
239 private final boolean insertPEIDeps;
240
241 /**
242 * A pointer to the governing IR
243 */
244 private final IR ir;
245
246 /**
247 * Initialize a structure to hold Heap Array SSA information.
248 *
249 * @param heapTypes only create heap arrays for these locations.
250 * if null, create all heap arrays
251 * @param uphi Should we use uphi functions? (ie. loads create a new
252 * name for heap arrays)
253 */
254 SSADictionary(Set<Object> heapTypes, boolean uphi, boolean insertPEIDeps, IR ir) {
255 this.heapTypes = heapTypes;
256 this.uphi = uphi;
257 this.insertPEIDeps = insertPEIDeps;
258 this.ir = ir;
259 }
260
261 /**
262 * Does a particular instruction <em> use </em> any heap variable?
263 *
264 * @param s the instruction in question
265 * @return true iff the instruction uses any heap variable. false
266 * otherwise
267 */
268 boolean usesHeapVariable(Instruction s) {
269 // special case code for Phi instructions
270 if (Phi.conforms(s)) {
271 Operand result = Phi.getResult(s);
272 return (result instanceof HeapOperand);
273 }
274 HeapOperand<Object>[] o = uses.get(s);
275 return (o != null);
276 }
277
278 /**
279 * Does a particular instruction <em> define </em> any heap variable?
280 *
281 * @param s the instruction in question
282 * @return true iff the instruction defs any heap variable. false
283 * otherwise
284 */
285 boolean defsHeapVariable(Instruction s) {
286 // special case code for Phi instructions
287 if (s.operator == PHI) {
288 Operand result = Phi.getResult(s);
289 return (result instanceof HeapOperand);
290 }
291 HeapOperand<Object>[] o = defs.get(s);
292 return (o != null);
293 }
294
295 /**
296 * Return the heap operands used by an instruction.
297 *
298 * @param s the instruction in question
299 * @return an array of the heap operands this instruction uses
300 */
301 public HeapOperand<Object>[] getHeapUses(Instruction s) {
302 if (s.operator == PHI) {
303 if (!usesHeapVariable(s)) return null;
304 HeapOperand<Object>[] result = new HeapOperand[Phi.getNumberOfValues(s)];
305 for (int i = 0; i < result.length; i++) {
306 result[i] = (HeapOperand) Phi.getValue(s, i);
307 }
308 return result;
309 } else {
310 return uses.get(s);
311 }
312 }
313
314 /**
315 * Return the heap operands defined by an instruction.
316 *
317 * @param s the instruction in question
318 * @return an array of the heap operands this instruction defs
319 */
320 public HeapOperand<Object>[] getHeapDefs(Instruction s) {
321 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
322 return defs.get(s);
323 }
324
325 /**
326 * Return the number of heap operands defined by an instruction
327 *
328 * @param s the instruction in question
329 * @return the number of heap operands this instruction defs
330 */
331 int getNumberOfHeapDefs(Instruction s) {
332 return getHeapDefs(s).length;
333 }
334
335 /**
336 * Replace all heap variables that an instruction defs with
337 * new heap variables. Each new heap variable has the same
338 * type as the old one, but a new number. Essentially, this
339 * function introduces new names required for translation
340 * into SSA form. This instruction will be the single static
341 * definition for each new heap variable.
342 *
343 * @param s the instruction that writes to the new heap variables
344 * @param b the basic block containing <code> s </code>
345 * @return the new heap variables that the instruction defines
346 */
347 //@SuppressWarnings("unchecked")
348 HeapOperand<Object>[] replaceDefs(Instruction s, BasicBlock b) {
349 if (s.operator() == PHI) {
350 // Note that a PHI
351 // instruction defs exactly one heap variable, newH[0]
352 HeapOperand<Object> oldDef = (HeapOperand) Phi.getResult(s);
353 int number = getNextHeapVariableNumber(oldDef.getHeapType());
354 HeapOperand<Object>[] newH = new HeapOperand[1];
355 newH[0] = new HeapOperand<Object>(new HeapVariable<Object>(oldDef.getHeapType(), number, ir));
356 newH[0].setInstruction(s);
357 Phi.setResult(s, newH[0]);
358 // record the new heap definition
359 newH[0].getHeapVariable().registerDef(b);
360 if (DEBUG) System.out.println("New heap def " + newH[0] + " for " + s);
361 // store the new heap variable in relevant data structures
362 HeapKey<Object> key = new HeapKey<Object>(number, oldDef.getHeapType());
363 heapVariables.put(key, newH[0].getHeapVariable());
364 return newH;
365 } else {
366 // get old heap operands defined by this instruction
367 HeapOperand<Object>[] oldH = defs.get(s);
368 HeapOperand<Object>[] newH = new HeapOperand[oldH.length];
369 // for each old heap variable ..
370 for (int i = 0; i < oldH.length; i++) {
371 // create a new heap variable
372 int number = getNextHeapVariableNumber(oldH[i].getHeapType());
373 newH[i] = new HeapOperand<Object>(new HeapVariable<Object>(oldH[i].getHeapType(), number, ir));
374 newH[i].setInstruction(s);
375 // record the new heap definition
376 newH[i].getHeapVariable().registerDef(b);
377 if (DEBUG) System.out.println("New heap def " + newH[i] + " for " + s);
378 // store the new heap variable in relevant data structures
379 HeapKey<Object> key = new HeapKey<Object>(number, oldH[i].getHeapType());
380 heapVariables.put(key, newH[i].getHeapVariable());
381 }
382 // record the new heap variables this instruction defs
383 defs.put(s, newH);
384 return newH;
385 }
386 }
387
388 /**
389 * Return an enumeration of the heap variables in this IR.
390 *
391 * @return the heap variables stored for this IR
392 */
393 Iterator<HeapVariable<Object>> getHeapVariables() {
394 return heapVariables.values().iterator();
395 }
396
397 /**
398 * Return an enumeration of the control-phi functions for
399 * <em> Heap </em> variables at the beginning of a basic block.
400 *
401 * @param bb the basic block in question
402 * @return the phi instructions for heap variables at the beginning of
403 * the basic block
404 */
405 public Iterator<Instruction> getHeapPhiInstructions(BasicBlock bb) {
406 ArrayList<Instruction> v = heapPhi.get(bb);
407 if (v == null) {
408 return emptyArrayList.iterator();
409 }
410 return v.iterator();
411 }
412
413 /**
414 * Return an enumeration of all instructions for a basic block, including
415 * the control-PHI functions for <em> heap </em> variables stored
416 * implicitly here.
417 *
418 * @param bb the basic block in question
419 * @return an enumeration of all instructions in this basic block,
420 * including heap phi instructions stored implicitly in this lookaside
421 * structure
422 */
423 AllInstructionEnumeration getAllInstructions(BasicBlock bb) {
424 return new AllInstructionEnumeration(bb, this);
425 }
426
427 /**
428 * Return an enumeration of all uses of a particular heap variable.
429 *
430 * @param A the heap variable in question
431 * @return an iterator over all instructions that use this heap
432 * variable
433 */
434 Iterator<HeapOperand<Object>> iterateHeapUses(HeapVariable<Object> A) {
435 HashSet<HeapOperand<Object>> u = UseChain.get(A);
436 return u.iterator();
437 }
438
439 /**
440 * Return the operand that represents a heap variable's unique def.
441 *
442 * @param A the heap variable in question
443 * @return the heap operand that represents this heap variable's unique
444 * static definition
445 */
446 HeapOperand<Object> getUniqueDef(HeapVariable<Object> A) {
447 return DefChain.get(A);
448 }
449
450 /**
451 * Return an enumeration of all the original uses of a heap variable.
452 * That is, return an iteration of all uses of the heap variable
453 * <em> before </em> we performed renaming for SSA.
454 *
455 * @param A the heap variable in question
456 * @return an iteration of all instructions that used this heap
457 * variable, prior to renaming for SSA
458 */
459 @SuppressWarnings("unused")
460 // Useful for debugging ??
461 private Iterator<HeapOperand<Object>> iterateOriginalHeapUses(HeapVariable<Object> A) {
462 Object type = A.getHeapType();
463 HashSet<HeapOperand<Object>> set = findOrCreateOriginalUses(type);
464 return set.iterator();
465 }
466
467 /**
468 * Return an enumeration of all the original definitions of a heap variable.
469 * That is, return an iteration of all defs of the heap variable
470 * <em> before </em> we performed renaming for SSA.
471 *
472 * @param A the heap variable in question
473 * @return an iteration of all instructions that defined this heap
474 * variable, prior to renaming for SSA
475 */
476 @SuppressWarnings("unused")
477 // Useful for debugging ??
478 private Iterator<HeapOperand<Object>> iterateOriginalHeapDefs(HeapVariable<Object> A) {
479 Object type = A.getHeapType();
480 HashSet<HeapOperand<Object>> set = findOrCreateOriginalDefs(type);
481 return set.iterator();
482 }
483
484 /**
485 * Return a set of all the original uses of a heap variable.
486 * That is, return the set of all uses of the heap variable
487 * <em> before </em> we performed renaming for SSA.
488 *
489 * @param type The heap variable in question
490 * @return the set of all instructions that used this heap
491 * variable, prior to renaming for SSA
492 */
493 private HashSet<HeapOperand<Object>> findOrCreateOriginalUses(Object type) {
494 HashSet<HeapOperand<Object>> result = originalUses.get(type);
495 if (result != null) {
496 return result;
497 }
498 // not found: create a new set
499 result = new HashSet<HeapOperand<Object>>(2);
500 for (Iterator<HeapVariable<Object>> e = getHeapVariables(); e.hasNext();) {
501 HeapVariable<Object> B = e.next();
502 if (B.getHeapType().equals(type)) {
503 HashSet<HeapOperand<Object>> u = UseChain.get(B);
504 result.addAll(u);
505 }
506 }
507 // store it in the hash set, and return
508 originalUses.put(type, result);
509 return result;
510 }
511
512 /**
513 * Return a set of all the original definitions of a heap variable.
514 * That is, return the set of all uses of the heap variable
515 * <em> before </em> we performed renaming for SSA.
516 *
517 * @param type the heap variable in question
518 * @return the set of all instructions that defined this heap
519 * variable, prior to renaming for SSA
520 */
521 private HashSet<HeapOperand<Object>> findOrCreateOriginalDefs(Object type) {
522 HashSet<HeapOperand<Object>> result = originalDefs.get(type);
523 if (result != null) {
524 return result;
525 }
526 // not found: create a new set
527 result = new HashSet<HeapOperand<Object>>(2);
528 for (Iterator<HeapVariable<Object>> e = getHeapVariables(); e.hasNext();) {
529 HeapVariable<Object> B = e.next();
530 if (B.getHeapType().equals(type)) {
531 HeapOperand<Object> def = getUniqueDef(B);
532 if (def != null) {
533 result.add(def);
534 }
535 }
536 }
537 // store it in the hash set, and return
538 originalDefs.put(type, result);
539 return result;
540 }
541
542 /**
543 * Return the number of uses of a heap variable.
544 *
545 * @param A the heap variable in question
546 * @return the number of uses of the heap variable
547 */
548 int getNumberOfUses(HeapVariable<Object> A) {
549 HashSet<HeapOperand<Object>> u = UseChain.get(A);
550 return u.size();
551 }
552
553 /**
554 * Return an enumeration of all heap variables that may be
555 * exposed on procedure exit.
556 *
557 * @return an enumeration of all heap variables that may be exposed on
558 * procedure exit
559 */
560 Iterator<HeapVariable<Object>> enumerateExposedHeapVariables() {
561 ArrayList<HeapVariable<Object>> v = new ArrayList<HeapVariable<Object>>();
562 for (Iterator<HeapVariable<Object>> e = getHeapVariables(); e.hasNext();) {
563 HeapVariable<Object> H = e.next();
564 if (isExposedOnExit(H)) {
565 v.add(H);
566 }
567 }
568 return v.iterator();
569 }
570
571 /**
572 * Is heap variable H exposed on procedure exit?
573 *
574 * @return true or false as appropriate
575 */
576 boolean isExposedOnExit(HeapVariable<Object> H) {
577 for (Iterator<HeapOperand<Object>> i = iterateHeapUses(H); i.hasNext();) {
578 HeapOperand<Object> op = i.next();
579 Instruction s = op.instruction;
580 if (exits.contains(s)) {
581 return true;
582 }
583 }
584 return false;
585 }
586
587 /**
588 * Recompute the chain of uses for each heap variable.
589 * NOTE: for now this procedure does <em> not </em> recompute
590 * def chains
591 */
592 void recomputeArrayDU() {
593 UseChain.clear();
594 DefChain.clear();
595 // create a set of uses for each heap variable
596 for (Iterator<HeapVariable<Object>> e = getHeapVariables(); e.hasNext();) {
597 HeapVariable<Object> H = e.next();
598 HashSet<HeapOperand<Object>> u = new HashSet<HeapOperand<Object>>(2);
599 UseChain.put(H, u);
600 }
601 // populate the use chain with each use registered
602 for (HeapOperand<Object>[] operands : uses.values()) {
603 if (operands == null) continue;
604 for (HeapOperand<Object> operand : operands) {
605 HeapVariable<Object> v = operand.getHeapVariable();
606 HashSet<HeapOperand<Object>> u = UseChain.get(v);
607 u.add(operand);
608 }
609 }
610 // record the unique def for each heap variable
611 for (HeapOperand<Object>[] operands : defs.values()) {
612 if (operands == null) continue;
613 for (HeapOperand<Object> operand : operands) {
614 HeapVariable<Object> v = operand.getHeapVariable();
615 DefChain.put(v, operand);
616 }
617 }
618 // handle each HEAP PHI function.
619 for (BasicBlockEnumeration e = ir.getBasicBlocks(); e.hasMoreElements();) {
620 BasicBlock bb = e.nextElement();
621 for (Iterator<Instruction> hp = getHeapPhiInstructions(bb); hp.hasNext();) {
622 Instruction phi = hp.next();
623 HeapOperand<Object> H = (HeapOperand) Phi.getResult(phi);
624 HeapVariable<Object> v = H.getHeapVariable();
625 DefChain.put(v, H);
626 for (int i = 0; i < Phi.getNumberOfValues(phi); i++) {
627 HeapOperand<Object> Hu = (HeapOperand) Phi.getValue(phi, i);
628 HeapVariable<Object> vu = Hu.getHeapVariable();
629 HashSet<HeapOperand<Object>> u = UseChain.get(vu);
630 u.add(Hu);
631 }
632 }
633 }
634 }
635
636 /**
637 * Delete an HeapOperand from the use chain of its heap variable
638 *
639 * @param op the heap operand to be deleted
640 */
641 void deleteFromUseChain(HeapOperand<Object> op) {
642 HeapVariable<Object> hv = op.getHeapVariable();
643 HashSet<HeapOperand<Object>> u = UseChain.get(hv);
644 u.remove(op);
645 }
646
647 /**
648 * Add an HeapOperand to the use chain of its heap variable
649 *
650 * @param op the heap operand to be added
651 */
652 void addToUseChain(HeapOperand<Object> op) {
653 HeapVariable<Object> hv = op.getHeapVariable();
654 HashSet<HeapOperand<Object>> u = UseChain.get(hv);
655 u.add(op);
656 }
657
658 /**
659 * Create a heap control phi instruction, and store it at the
660 * beginning of a basic block.
661 *
662 * @param bb the basic block
663 * @param H the heap variable to merge
664 */
665 void createHeapPhiInstruction(BasicBlock bb, HeapVariable<Object> H) {
666 Instruction s = makePhiInstruction(H, bb);
667 /*
668 HeapOperand[] Hprime = new HeapOperand[1];
669 Hprime[0] = new HeapOperand(H);
670 Hprime[0].setInstruction(s);
671 defs.put(s, Hprime);
672 */
673 ArrayList<Instruction> heapPhis = heapPhi.get(bb);
674 if (heapPhis == null) {
675 heapPhis = new ArrayList<Instruction>(2);
676 heapPhi.put(bb, heapPhis);
677 }
678 heapPhis.add(s);
679 registerInstruction(s, bb);
680 }
681
682 /**
683 * Register that an instruction now uses the set of heap operands
684 *
685 * @param s the instruction in question
686 * @param H the set of heap operands which s uses
687 */
688 void replaceUses(Instruction s, HeapOperand<Object>[] H) {
689 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
690 uses.put(s, H);
691 for (HeapOperand<Object> aH : H) {
692 aH.setInstruction(s);
693 }
694 }
695
696 /**
697 * Return the total number of heap variables allocated for the IR
698 *
699 * @return the total number of heap variables allocated for the IR
700 */
701 int getNumberOfHeapVariables() {
702 return heapVariables.size();
703 }
704
705 /**
706 * Register that an instruction s can potentially leave the procedure.
707 * We conservatively record that s uses all heap variables.
708 * <p> NOTE: This function should be called before renaming.
709 * <p> NOTE: Only need to use this for backwards analyses
710 *
711 * @param s the instruction in question
712 * @param b s's basic block
713 */
714 @SuppressWarnings("unchecked")
715 void registerExit(Instruction s, BasicBlock b) {
716 // setup an array of all heap variables
717 // TODO: for efficiency, cache a copy of 'all'
718 Iterator<HeapVariable<Object>> vars = heapVariables.values().iterator();
719 HeapOperand<Object>[] all = new HeapOperand[heapVariables.size()];
720 for (int i = 0; i < all.length; i++) {
721 all[i] = new HeapOperand<Object>(vars.next());
722 all[i].setInstruction(s);
723 // record that all[i] is def'ed in b
724 all[i].getHeapVariable().registerDef(b);
725 }
726 // record that s uses all heap variables
727 uses.put(s, all);
728 // record that instruction s can exit the procedure
729 exits.add(s);
730 }
731
732 /**
733 * Register that an instruction s has unknown side effects. That is,
734 * we conservatively record that s defs and uses all heap variables.
735 * <p> NOTE: This function should be called before renaming.
736 *
737 * @param s the instruction in question
738 * @param b the basic block containing s
739 */
740 @SuppressWarnings("unchecked")
741 void registerUnknown(Instruction s, BasicBlock b) {
742 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
743 // setup an array of all heap variables
744 // TODO: for efficiency, cache a copy of 'all'
745 Iterator vars = heapVariables.values().iterator();
746 HeapOperand<Object>[] all = new HeapOperand[heapVariables.size()];
747 for (int i = 0; i < all.length; i++) {
748 all[i] = new HeapOperand<Object>((HeapVariable<Object>) vars.next());
749 all[i].setInstruction(s);
750 // record that all[i] is def'ed in b
751 all[i].getHeapVariable().registerDef(b);
752 }
753 // record that s uses and defs all heap variables
754 uses.put(s, all);
755 defs.put(s, all);
756 // record that instruction s can exit the procedure
757 exits.add(s);
758 }
759
760 /**
761 * Record the heap variables that instruction s defines and uses.
762 *
763 * @param s the instruction in question
764 * @param b the basic block containing s
765 */
766 void registerInstruction(Instruction s, BasicBlock b) {
767 if (!s.isImplicitLoad() &&
768 !s.isImplicitStore() &&
769 !s.isAllocation() &&
770 s.operator() != PHI &&
771 !(insertPEIDeps &&
772 (s.isPEI() ||
773 Label.conforms(s) ||
774 BBend.conforms(s) ||
775 s.operator.opcode == UNINT_BEGIN_opcode ||
776 s.operator.opcode == UNINT_END_opcode))) {
777 return;
778 }
779 // handled by registerUnknown
780 if (s.isDynamicLinkingPoint()) {
781 return;
782 }
783 switch (s.getOpcode()) {
784 case LABEL_opcode: // only reached if insertPEIDeps
785 labelHelper(s, b);
786 break;
787 case BBEND_opcode: // only reached if insertPEIDeps
788 bbendHelper(s, b);
789 break;
790 case UNINT_BEGIN_opcode: // only reached if insertPEIDeps
791 case UNINT_END_opcode: // only reached if insertPEIDeps
792 registerUse(s, exceptionState);
793 registerDef(s, b, exceptionState);
794 break;
795 case GETFIELD_opcode:
796 getFieldHelper(s, b);
797 break;
798 case PUTFIELD_opcode:
799 putFieldHelper(s, b);
800 break;
801 case GETSTATIC_opcode:
802 getStaticHelper(s, b);
803 break;
804 case PUTSTATIC_opcode:
805 putStaticHelper(s, b);
806 break;
807 case NEW_opcode:
808 case NEW_UNRESOLVED_opcode:
809 newHelper(s, b);
810 break;
811 case NEWARRAY_opcode:
812 case NEWARRAY_UNRESOLVED_opcode:
813 newArrayHelper(s, b);
814 break;
815 case NEWOBJMULTIARRAY_opcode:
816 /* SJF: after talking with Martin, I'm not sure what the
817 correct Array SSA representation for an allocation should
818 be. Since we do not yet use these heap variables, do
819 nothing for now.
820 Future: this should probably def the heap variable for every
821 field of the object type allocated.
822 // treat this opcode like a CALL
823 registerUnknown(s,b);
824 */
825 break;
826 case INT_ALOAD_opcode:
827 case LONG_ALOAD_opcode:
828 case FLOAT_ALOAD_opcode:
829 case DOUBLE_ALOAD_opcode:
830 case REF_ALOAD_opcode:
831 case BYTE_ALOAD_opcode:
832 case UBYTE_ALOAD_opcode:
833 case USHORT_ALOAD_opcode:
834 case SHORT_ALOAD_opcode:
835 aloadHelper(s, b);
836 break;
837 case INT_ASTORE_opcode:
838 case LONG_ASTORE_opcode:
839 case FLOAT_ASTORE_opcode:
840 case DOUBLE_ASTORE_opcode:
841 case REF_ASTORE_opcode:
842 case BYTE_ASTORE_opcode:
843 case SHORT_ASTORE_opcode:
844 astoreHelper(s, b);
845 break;
846 case ARRAYLENGTH_opcode:
847 arraylengthHelper(s, b);
848 break;
849 case CALL_opcode:
850 case SYSCALL_opcode:
851 case MONITORENTER_opcode:
852 case MONITOREXIT_opcode:
853 case PREPARE_INT_opcode:
854 case PREPARE_ADDR_opcode:
855 case ATTEMPT_INT_opcode:
856 case ATTEMPT_ADDR_opcode:
857 case READ_CEILING_opcode:
858 case WRITE_FLOOR_opcode:
859 // do nothing: these cases handled by registerUnknown
860 break;
861 case UBYTE_LOAD_opcode:
862 case BYTE_LOAD_opcode:
863 case USHORT_LOAD_opcode:
864 case SHORT_LOAD_opcode:
865 case INT_LOAD_opcode:
866 case LONG_LOAD_opcode:
867 case DOUBLE_LOAD_opcode:
868 case REF_LOAD_opcode:
869 // !!TODO: how to handle this special case?
870 break;
871 case BYTE_STORE_opcode:
872 case SHORT_STORE_opcode:
873 case REF_STORE_opcode:
874 case INT_STORE_opcode:
875 case LONG_STORE_opcode:
876 case DOUBLE_STORE_opcode:
877 // !!TODO: how to handle this special case?
878 break;
879 case PHI_opcode:
880 phiHelper(s, b);
881 break;
882 default:
883 if (!Operators.helper.isHandledByRegisterUnknown(s.getOpcode()) && !s.isPEI()) {
884 System.out.println("SSA dictionary failed on " + s.toString());
885 throw new OperationNotImplementedException("SSADictionary: Unsupported opcode " + s);
886 }
887 } // switch
888 if (insertPEIDeps) {
889 if (s.isImplicitStore()) addExceptionStateToUses(s);
890 if (s.isPEI()) addExceptionStateToDefs(s, b);
891 }
892 }
893
894 /**
895 * Record the effects of a getfield instruction on the heap array
896 * SSA form. Register the heap variables that this instruction uses and
897 * defs. Note that if inserting uphi functions, a getfield defs a new
898 * heap variable name.
899 *
900 * @param s the getfield instruction
901 * @param b the basic block containing s
902 */
903 private void getFieldHelper(Instruction s, BasicBlock b) {
904 LocationOperand locOp = GetField.getLocation(s);
905 FieldReference field = locOp.getFieldRef();
906 registerUse(s, field);
907 if (uphi) {
908 registerDef(s, b, field);
909 }
910 }
911
912 /**
913 * Record the effects of a putfield instruction on the heap array
914 * SSA form. Register the heap variables that this instruction uses and
915 * defs.
916 *
917 * @param s the getfield instruction
918 * @param b the basic block containing s
919 */
920 private void putFieldHelper(Instruction s, BasicBlock b) {
921 LocationOperand locOp = PutField.getLocation(s);
922 FieldReference field = locOp.getFieldRef();
923 registerUse(s, field);
924 registerDef(s, b, field);
925 }
926
927 /**
928 * Record the effects of a getstatic instruction on the heap array
929 * SSA form. Register the heap variables that this instruction uses and
930 * defs. Note that if inserting uphi functions, a getstatic defs a new
931 * heap variable name.
932 *
933 * @param s the getstatic instruction
934 * @param b the basic block containing s
935 */
936 private void getStaticHelper(Instruction s, BasicBlock b) {
937 LocationOperand locOp = GetStatic.getLocation(s);
938 FieldReference field = locOp.getFieldRef();
939 registerUse(s, field);
940 if (uphi) {
941 registerDef(s, b, field);
942 }
943 }
944
945 /**
946 * Record the effects of a putstatic instruction on the heap array
947 * SSA form. Register the heap variables that this instruction uses and
948 * defs.
949 *
950 * @param s the putstatic instruction
951 * @param b the basic block containing s
952 */
953 private void putStaticHelper(Instruction s, BasicBlock b) {
954 LocationOperand locOp = PutStatic.getLocation(s);
955 FieldReference field = locOp.getFieldRef();
956 registerUse(s, field);
957 registerDef(s, b, field);
958 }
959
960 /**
961 * Update the heap array SSA form for an allocation instruction
962 *
963 * @param s the allocation instruction
964 * @param b the basic block containing the allocation
965 */
966 private void newHelper(Instruction s, BasicBlock b) {
967 /* SJF: after talking with Martin, I'm not sure what the
968 correct Array SSA representation for an allocation should
969 be. Since we do not yet use these heap variables, do
970 nothing for now.
971 Future: this should probably def the heap variable for every
972 field of the object type allocated.
973 TypeOperand typeOp = New.getType(s);
974 RVMType type = typeOp.type;
975 registerUse(s,type);
976 registerDef(s,b,type);
977 */
978 }
979
980 /**
981 * Update the heap array SSA form for an array allocation instruction
982 *
983 * @param s the allocation instruction
984 * @param b the basic block containing the allocation
985 */
986 private void newArrayHelper(Instruction s, BasicBlock b) {
987 // TODO: use some class hierarchy analysis
988 /* SJF: after talking with Martin, I'm not sure what the
989 correct Array SSA representation for an allocation should
990 be. Since we do not yet use these heap variables, do
991 nothing for now.
992 Future: this should probably def the heap variable for every
993 field of the object type allocated.
994 TypeOperand typeOp = NewArray.getType(s);
995 RVMType type = typeOp.type;
996 if (!type.asArray().getElementType().isPrimitiveType())
997 type = ClassLoaderProxy.JavaLangObjectArrayType;
998 registerUse(s,type);
999 registerDef(s,b,type);
1000 */
1001 }
1002
1003 /**
1004 * Record the effects of a aload instruction on the heap array
1005 * SSA form. Register the heap variables that this instruction uses and
1006 * defs. Note that if inserting uphi functions, a aload defs a new
1007 * heap variable name.
1008 *
1009 * @param s the aload instruction
1010 * @param b the basic block containing s
1011 */
1012 private void aloadHelper(Instruction s, BasicBlock b) {
1013 // TODO: use some class hierarchy analysis
1014 TypeReference type = ALoad.getArray(s).getType();
1015
1016 // After cond branch splitting, operand may be a Null constant
1017 // filter out it now -- Feng
1018 if (type.isArrayType()) {
1019 if (!type.getArrayElementType().isPrimitiveType()) {
1020 type = TypeReference.JavaLangObjectArray;
1021 }
1022 registerUse(s, type);
1023 if (uphi) {
1024 registerDef(s, b, type);
1025 }
1026 }
1027 }
1028
1029 /**
1030 * Record the effects of an astore instruction on the heap array
1031 * SSA form. Register the heap variables that this instruction uses and
1032 * defs.
1033 *
1034 * @param s the astore instruction
1035 * @param b the basic block containing s
1036 */
1037 private void astoreHelper(Instruction s, BasicBlock b) {
1038 // TODO: use some class hierarchy analysis
1039 TypeReference type = AStore.getArray(s).getType();
1040
1041 // After cond branch splitting, operand may be a Null constant
1042 // filter out it now -- Feng
1043 if (type.isArrayType()) {
1044 if (!type.getArrayElementType().isPrimitiveType()) {
1045 type = TypeReference.JavaLangObjectArray;
1046 }
1047 registerUse(s, type);
1048 registerDef(s, b, type);
1049 }
1050 }
1051
1052 /**
1053 * Record the effects of an arraylength instruction on the heap array
1054 * SSA form. Register the heap variable that this instruction uses.
1055 *
1056 * @param s the arraylength instruction
1057 * @param b the basic block containing s
1058 */
1059 private void arraylengthHelper(Instruction s, BasicBlock b) {
1060 // TODO: use some class hierarchy analysis
1061 TypeReference type = GuardedUnary.getVal(s).getType();
1062
1063 // After cond branch splitting, operand may be a Null constant
1064 // filter it out now -- Feng
1065 if (type.isArrayType()) {
1066 if (!type.getArrayElementType().isPrimitiveType()) {
1067 type = TypeReference.JavaLangObjectArray;
1068 }
1069 registerUse(s, type);
1070 }
1071 }
1072
1073 /**
1074 * Record the effects of a phi instruction on the heap array
1075 * SSA form. Register the heap variables that this instruction uses
1076 * and defs.
1077 *
1078 * @param s the phi instruction
1079 * @param b the basic block containing s
1080 */
1081 private void phiHelper(Instruction s, BasicBlock b) {
1082 // for phi function, we dont' register implicit defs and uses
1083 // since they're explicit in the instruction
1084 /*
1085 Object result = Phi.getResult(s);
1086 if (!(result instanceof HeapOperand))
1087 return;
1088 HeapOperand H = (HeapOperand)Phi.getResult(s);
1089 Object Htype = H.getHeapType();
1090 if (Htype instanceof RVMType) {
1091 RVMType t = (RVMType)Htype;
1092 registerDef(s, b, t);
1093 }
1094 else if (Htype instanceof RVMField) {
1095 RVMField f = (RVMField)Htype;
1096 registerDef(s, b, f);
1097 }
1098 else {
1099 String a = (String)Htype;
1100 registerDef(s, b, a);
1101 }
1102 for (int i = 0; i < Phi.getNumberOfValues(s); i++) {
1103 HeapOperand U = (HeapOperand)Phi.getValue(s, i);
1104 Object Utype = U.getHeapType();
1105 if (Utype instanceof RVMType) {
1106 RVMType t = (RVMType)Utype;
1107 registerUse(s, t);
1108 }
1109 else if (Utype instanceof RVMField) {
1110 RVMField f = (RVMField)Utype;
1111 registerUse(s, f);
1112 } else {
1113 String a = (String)Utype;
1114 registerUse(s, a);
1115 }
1116 }
1117 */
1118 }
1119
1120 /**
1121 * Record the effects of a label instruction on the heap array
1122 * SSA form. Register the exception state that this instruction defs.
1123 *
1124 * @param s the label instruction
1125 * @param b the basic block containing s
1126 */
1127 private void labelHelper(Instruction s, BasicBlock b) {
1128 BasicBlockEnumeration e = b.getIn();
1129 boolean newHandler = !e.hasMoreElements();
1130 while (!newHandler && e.hasMoreElements()) {
1131 if (!(e.next().isExceptionHandlerEquivalent(b))) newHandler = true;
1132 }
1133 if (newHandler) registerDef(s, b, exceptionState);
1134 }
1135
1136 /**
1137 * Record the effects of a bbend instruction on the heap array
1138 * SSA form. Register the exception state that this instruction uses.
1139 *
1140 * @param s the label instruction
1141 * @param b the basic block containing s
1142 */
1143 private void bbendHelper(Instruction s, BasicBlock b) {
1144 BasicBlockEnumeration e = b.getOut();
1145 boolean newHandler = !e.hasMoreElements();
1146 while (!newHandler && e.hasMoreElements()) {
1147 if (!(e.next().isExceptionHandlerEquivalent(b))) newHandler = true;
1148 }
1149 if (newHandler) registerUse(s, exceptionState);
1150 }
1151
1152 /**
1153 * Register that an instruction uses a heap variable of a given
1154 * type.
1155 *
1156 * @param s the instruction in question
1157 * @param t the type of the heap variable the instruction uses
1158 */
1159 private void registerUse(Instruction s, TypeReference t) {
1160 // if the heapTypes set is defined, then we only build Array
1161 // SSA for these types. So, ignore uses of types that are
1162 // not included in the set
1163 if (heapTypes != null) {
1164 if (!heapTypes.contains(t)) {
1165 return;
1166 }
1167 }
1168 HeapVariable<Object> H = findOrCreateHeapVariable(t);
1169 HeapOperand<Object>[] Hprime = new HeapOperand[1];
1170 Hprime[0] = new HeapOperand<Object>(H);
1171 Hprime[0].setInstruction(s);
1172 uses.put(s, Hprime);
1173 }
1174
1175 /**
1176 * Register that an instruction writes a heap variable for a given
1177 * type.
1178 *
1179 * @param s the instruction in question
1180 * @param b s's basic block
1181 * @param t the type of the heap variable the instruction modifies
1182 */
1183 private void registerDef(Instruction s, BasicBlock b, TypeReference t) {
1184 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
1185 // if the heapTypes set is defined, then we only build Array
1186 // SSA for these types. So, ignore uses of types that are
1187 // not included in the set
1188 if (heapTypes != null) {
1189 if (!heapTypes.contains(t)) {
1190 return;
1191 }
1192 }
1193 HeapVariable<Object> H = findOrCreateHeapVariable(t);
1194 H.registerDef(b);
1195 HeapOperand<Object>[] Hprime = new HeapOperand[1];
1196 Hprime[0] = new HeapOperand<Object>(H);
1197 Hprime[0].setInstruction(s);
1198 defs.put(s, Hprime);
1199 }
1200
1201 /**
1202 * Register that an instruction uses a heap variable for a given
1203 * field.
1204 *
1205 * @param s the instruction in question
1206 * @param fr the field heap variable the instruction uses
1207 */
1208 private void registerUse(Instruction s, FieldReference fr) {
1209 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
1210 RVMField f = fr.peekResolvedField();
1211 HeapOperand<Object> H;
1212 if (f == null) {
1213 // can't resolve field at compile time.
1214 // This isn't quite correct, but is somewhat close.
1215 // See defect 3481.
1216 H = new HeapOperand<Object>(findOrCreateHeapVariable(fr));
1217 } else {
1218 // if the heapTypes set is defined, then we only build Array
1219 // SSA for these types. So, ignore uses of types that are
1220 // not included in the set
1221 if (heapTypes != null) {
1222 if (!heapTypes.contains(f)) {
1223 return;
1224 }
1225 }
1226 H = new HeapOperand<Object>(findOrCreateHeapVariable(f));
1227 }
1228 HeapOperand<Object>[] Hprime = new HeapOperand[1];
1229 Hprime[0] = H;
1230 Hprime[0].setInstruction(s);
1231 uses.put(s, Hprime);
1232 }
1233
1234 /**
1235 * Register that instruction <code>s</code> writes a heap variable for
1236 * a given field.
1237 *
1238 * @param s the instruction in question
1239 * @param b <code>s</code>'s basic block
1240 * @param fr the field heap variable the instruction modifies
1241 */
1242 private void registerDef(Instruction s, BasicBlock b, FieldReference fr) {
1243 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
1244 RVMField f = fr.peekResolvedField();
1245 HeapOperand<Object> H;
1246 if (f == null) {
1247 // can't resolve field at compile time.
1248 // This isn't quite correct, but is somewhat close.
1249 // See bug #1147433
1250 H = new HeapOperand<Object>(findOrCreateHeapVariable(fr));
1251 } else {
1252 // if the heapTypes set is defined, then we only build Array
1253 // SSA for these types. So, ignore uses of types that are
1254 // not included in the set
1255 if (heapTypes != null) {
1256 if (!heapTypes.contains(f)) {
1257 return;
1258 }
1259 }
1260 H = new HeapOperand<Object>(findOrCreateHeapVariable(f));
1261 }
1262 H.value.registerDef(b);
1263 HeapOperand<Object>[] Hprime = new HeapOperand[1];
1264 Hprime[0] = H;
1265 Hprime[0].setInstruction(s);
1266 defs.put(s, Hprime);
1267 }
1268
1269 /**
1270 * Register that an instruction uses a heap variable for a given
1271 * field.
1272 *
1273 * @param s the instruction in question
1274 * @param a the field heap variable the instruction uses
1275 */
1276 @SuppressWarnings("unchecked")
1277 private void registerUse(Instruction s, String a) {
1278 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
1279 // if the heapTypes set is defined, then we only build Array
1280 // SSA for these types. So, ignore uses of types that are
1281 // not included in the set
1282 if (heapTypes != null) {
1283 if (!heapTypes.contains(a)) {
1284 return;
1285 }
1286 }
1287 HeapVariable<Object> H = findOrCreateHeapVariable(a);
1288 HeapOperand<Object>[] Hprime = new HeapOperand[1];
1289 Hprime[0] = new HeapOperand<Object>(H);
1290 Hprime[0].setInstruction(s);
1291 uses.put(s, Hprime);
1292 }
1293
1294 /**
1295 * Register that the instruction <code>s</code> writes a heap variable for
1296 * a given field.
1297 *
1298 * @param s the instruction in question
1299 * @param b <code>s</code>'s basic block
1300 * @param a XXX TODO Check this XXX The field in question.
1301 */
1302 @SuppressWarnings("unchecked")
1303 private void registerDef(Instruction s, BasicBlock b, String a) {
1304 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
1305 // if the heapTypes set is defined, then we only build Array
1306 // SSA for these types. So, ignore uses of types that are
1307 // not included in the set
1308 if (heapTypes != null) {
1309 if (!heapTypes.contains(a)) {
1310 return;
1311 }
1312 }
1313 HeapVariable<Object> H = findOrCreateHeapVariable(a);
1314 H.registerDef(b);
1315 HeapOperand<Object>[] Hprime = new HeapOperand[1];
1316 Hprime[0] = new HeapOperand<Object>(H);
1317 Hprime[0].setInstruction(s);
1318 defs.put(s, Hprime);
1319 }
1320
1321 /**
1322 * Returns a copy of H with an additional free slot at position 0
1323 *
1324 * @param H the array of HeapOperands to be extended.
1325 */
1326 @SuppressWarnings("unchecked")
1327 private static HeapOperand<Object>[] extendHArray(HeapOperand<Object>[] H) {
1328 HeapOperand<Object>[] res;
1329
1330 if (H == null) {
1331 res = new HeapOperand[1];
1332 } else {
1333 res = new HeapOperand[H.length + 1];
1334 for (int i = 0; i < H.length; ++i) {
1335 res[i + 1] = H[i];
1336 }
1337 }
1338 return res;
1339 }
1340
1341 /**
1342 * Register that an instruction defines the exception state.
1343 *
1344 * @param s the instruction in question
1345 * @param b s's basic block
1346 */
1347 @SuppressWarnings("unchecked")
1348 void addExceptionStateToDefs(Instruction s, BasicBlock b) {
1349 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
1350 HeapVariable<Object> H = findOrCreateHeapVariable(exceptionState);
1351 H.registerDef(b);
1352 HeapOperand<Object>[] Hprime = extendHArray(defs.get(s));
1353 Hprime[0] = new HeapOperand<Object>(H);
1354 Hprime[0].setInstruction(s);
1355 defs.put(s, Hprime);
1356 }
1357
1358 /**
1359 * Register that an instruction defines the exception state.
1360 *
1361 * @param s the instruction in question
1362 */
1363 @SuppressWarnings("unchecked")
1364 void addExceptionStateToUses(Instruction s) {
1365 if (VM.VerifyAssertions) VM._assert(s.operator != PHI);
1366 HeapVariable<Object> H = findOrCreateHeapVariable(exceptionState);
1367 HeapOperand<Object>[] Hprime = extendHArray(uses.get(s));
1368 Hprime[0] = new HeapOperand<Object>(H);
1369 Hprime[0].setInstruction(s);
1370 uses.put(s, Hprime);
1371 }
1372
1373 /**
1374 * Return the heap variable for a given type or field with
1375 * number 0.
1376 * If no heap variable yet exits for this type or field, create a new
1377 * one.
1378 *
1379 * @param type the <code> TypeReference </code> or <code> RVMField </code>
1380 * identifying the desired heap variable
1381 * @return the desired heap variable
1382 */
1383 @SuppressWarnings("unchecked")
1384 private HeapVariable<Object> findOrCreateHeapVariable(Object type) {
1385 if (DEBUG) {
1386 System.out.print("findOrCreateHeapVariable " + type);
1387 }
1388 HeapKey<Object> key = new HeapKey<Object>(0, type);
1389 HeapVariable<Object> H = heapVariables.get(key);
1390 if (DEBUG) {
1391 System.out.println("... found " + H);
1392 }
1393 if (H == null) {
1394 // note: if not found, then we have never created a heap
1395 // variable with the correct type. So, create one, with number
1396 // 0
1397 int number = getNextHeapVariableNumber(type); // should return 0
1398 H = new HeapVariable<Object>(type, number, ir);
1399 heapVariables.put(key, H);
1400 if (DEBUG) {
1401 System.out.println("... created " + heapVariables.get(key));
1402 }
1403 }
1404 return H;
1405 }
1406
1407 /**
1408 * Get the next number to be assigned to a new heap variable
1409 * for a given type or field.
1410 *
1411 * @param type the <code> TypeReference </code> or <code> RVMField </code>
1412 * identifying the heap variable
1413 * @return the next integer (monotonically increasing) to identify a new
1414 * name for this heap variable
1415 */
1416 private int getNextHeapVariableNumber(Object type) {
1417 Integer current = nextNumber.get(type);
1418 if (current == null) {
1419 // no number found. Create one.
1420 Integer one = 1;
1421 nextNumber.put(type, one);
1422 return 0;
1423 }
1424 // bump up the number
1425 Integer next = current + 1;
1426 nextNumber.put(type, next);
1427 return current;
1428 }
1429
1430 /**
1431 * Create a phi-function instruction for a heap variable
1432 *
1433 * @param H a symbolic variable for a Heap variable
1434 * @param bb the basic block holding the new phi function
1435 * instruction
1436 * @return the instruction <code> H = phi H,H,..,H </code>
1437 */
1438 private static Instruction makePhiInstruction(HeapVariable<Object> H, BasicBlock bb) {
1439 int n = bb.getNumberOfIn();
1440 BasicBlockEnumeration in = bb.getIn();
1441 HeapOperand<Object> lhs = new HeapOperand<Object>(H);
1442 Instruction s = Phi.create(PHI, lhs, n);
1443 lhs.setInstruction(s);
1444 for (int i = 0; i < n; i++) {
1445 HeapOperand<Object> op = new HeapOperand<Object>(H);
1446 op.setInstruction(s);
1447 Phi.setValue(s, i, op);
1448 BasicBlock pred = in.next();
1449 Phi.setPred(s, i, new BasicBlockOperand(pred));
1450 }
1451 return s;
1452 }
1453
1454 /**
1455 * This class represents the name of a heap variable in the heap array
1456 * SSA form.
1457 */
1458 private static final class HeapKey<T> {
1459 /**
1460 * The number and type comprise the name of a heap variable in array SSA
1461 * form
1462 */
1463 private final int number;
1464 /**
1465 * The number and type comprise the name of a heap variable in array SSA
1466 * form
1467 */
1468 private final T type;
1469
1470 /**
1471 * Create a new name for a heap variable.
1472 *
1473 * @param number the number, a unique integer from SSA renaming
1474 * @param type the type (a <code> RVMField </code> or <code>
1475 * TypeReference </code>
1476 */
1477 HeapKey(int number, T type) {
1478 this.number = number;
1479 this.type = type;
1480 }
1481
1482 /**
1483 * Test against another key for equality. This function is used to
1484 * retrive items from hashtables.
1485 *
1486 * @param key the object to compare with
1487 * @return true or false as appropriate
1488 */
1489 public boolean equals(Object key) {
1490 if (!(key instanceof HeapKey)) {
1491 return false;
1492 }
1493 HeapKey<T> k = (HeapKey) key;
1494 return ((type.equals(k.type)) && (number == k.number));
1495 }
1496
1497 /**
1498 * Return a hash code for this name.
1499 *
1500 * TODO: come up with a better hash function.
1501 *
1502 * @return the hash code
1503 */
1504 public int hashCode() {
1505 return type.hashCode() + 8192 * number;
1506 }
1507 }
1508
1509 /**
1510 * This class implements an <code> Enumeration </code> over all
1511 * instructions for a basic block. This enumeration includes
1512 * explicit instructions in the IR and implicit phi instructions
1513 * for heap variables, which are stored only in this lookaside
1514 * structure.
1515 */
1516 static final class AllInstructionEnumeration implements Enumeration<Instruction> {
1517 /**
1518 * An enumeration of the explicit instructions in the IR for a basic
1519 * block
1520 */
1521 private final InstructionEnumeration explicitInstructions;
1522
1523 /**
1524 * An enumeration of the implicit instructions in the IR for a basic
1525 * block. These instructions appear only in the SSA dictionary
1526 * lookaside structure.
1527 */
1528 private final Iterator<Instruction> implicitInstructions;
1529
1530 /**
1531 * The label instruction for the basic block
1532 */
1533 private Instruction labelInstruction;
1534
1535 /**
1536 * Construct an enumeration for all instructions, both implicit and
1537 * explicit in the IR, for a given basic block
1538 *
1539 * @param bb the basic block whose instructions this enumerates
1540 */
1541 AllInstructionEnumeration(BasicBlock bb, SSADictionary dict) {
1542 explicitInstructions = bb.forwardInstrEnumerator();
1543 implicitInstructions = dict.getHeapPhiInstructions(bb);
1544 labelInstruction = explicitInstructions.next();
1545 }
1546
1547 /**
1548 * Are there more elements in the enumeration?
1549 *
1550 * @return true or false
1551 */
1552 public boolean hasMoreElements() {
1553 return (implicitInstructions.hasNext() || explicitInstructions.hasMoreElements());
1554 }
1555
1556 /**
1557 * Get the next instruction in the enumeration
1558 *
1559 * @return the next instruction
1560 */
1561 public Instruction nextElement() {
1562 if (labelInstruction != null) {
1563 Instruction temp = labelInstruction;
1564 labelInstruction = null;
1565 return temp;
1566 }
1567 if (implicitInstructions.hasNext()) {
1568 return implicitInstructions.next();
1569 }
1570 return explicitInstructions.next();
1571 }
1572 }
1573 }