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