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 static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ALOAD_opcode;
016 import static org.jikesrvm.compilers.opt.ir.Operators.BYTE_ASTORE_opcode;
017 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ALOAD_opcode;
018 import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_ASTORE_opcode;
019 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ALOAD_opcode;
020 import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_ASTORE_opcode;
021 import static org.jikesrvm.compilers.opt.ir.Operators.GETFIELD_opcode;
022 import static org.jikesrvm.compilers.opt.ir.Operators.GETSTATIC_opcode;
023 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ALOAD_opcode;
024 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ASTORE_opcode;
025 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ALOAD_opcode;
026 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ASTORE_opcode;
027 import static org.jikesrvm.compilers.opt.ir.Operators.PUTFIELD_opcode;
028 import static org.jikesrvm.compilers.opt.ir.Operators.PUTSTATIC_opcode;
029 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ALOAD_opcode;
030 import static org.jikesrvm.compilers.opt.ir.Operators.REF_ASTORE_opcode;
031 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ALOAD_opcode;
032 import static org.jikesrvm.compilers.opt.ir.Operators.SHORT_ASTORE_opcode;
033 import static org.jikesrvm.compilers.opt.ir.Operators.UBYTE_ALOAD_opcode;
034 import static org.jikesrvm.compilers.opt.ir.Operators.USHORT_ALOAD_opcode;
035
036 import java.lang.reflect.Constructor;
037 import java.util.Enumeration;
038 import java.util.HashMap;
039 import java.util.HashSet;
040 import java.util.Iterator;
041
042 import org.jikesrvm.ArchitectureSpecificOpt.RegisterPool;
043 import org.jikesrvm.classloader.RVMField;
044 import org.jikesrvm.classloader.FieldReference;
045 import org.jikesrvm.classloader.TypeReference;
046 import org.jikesrvm.compilers.opt.OptOptions;
047 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
048 import org.jikesrvm.compilers.opt.dfsolver.DF_Solution;
049 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
050 import org.jikesrvm.compilers.opt.driver.OptimizationPlanAtomicElement;
051 import org.jikesrvm.compilers.opt.driver.OptimizationPlanCompositeElement;
052 import org.jikesrvm.compilers.opt.driver.OptimizationPlanElement;
053 import org.jikesrvm.compilers.opt.ir.ALoad;
054 import org.jikesrvm.compilers.opt.ir.AStore;
055 import org.jikesrvm.compilers.opt.ir.BasicBlock;
056 import org.jikesrvm.compilers.opt.ir.GetField;
057 import org.jikesrvm.compilers.opt.ir.GetStatic;
058 import org.jikesrvm.compilers.opt.ir.IR;
059 import org.jikesrvm.compilers.opt.ir.IRTools;
060 import org.jikesrvm.compilers.opt.ir.Instruction;
061 import org.jikesrvm.compilers.opt.ir.Move;
062 import org.jikesrvm.compilers.opt.ir.PutField;
063 import org.jikesrvm.compilers.opt.ir.PutStatic;
064 import org.jikesrvm.compilers.opt.ir.Register;
065 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
066 import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
067 import org.jikesrvm.compilers.opt.ir.operand.Operand;
068 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
069 import org.jikesrvm.compilers.opt.ssa.IndexPropagation.ArrayCell;
070 import org.jikesrvm.compilers.opt.ssa.IndexPropagation.ObjectCell;
071
072 /**
073 * This class implements the redundant load elimination by
074 * Fink, Knobe && Sarkar. See SAS 2000 paper for details.
075 */
076 public final class LoadElimination extends OptimizationPlanCompositeElement {
077
078 /**
079 * @param round which round of load elimination is this?
080 */
081 public LoadElimination(int round) {
082 super("Load Elimination",
083 new OptimizationPlanElement[]{new OptimizationPlanAtomicElement(new GVNPreparation(round)),
084 new OptimizationPlanAtomicElement(new EnterSSA()),
085 new OptimizationPlanAtomicElement(new GlobalValueNumber()),
086 new OptimizationPlanAtomicElement(new LoadEliminationPreparation(round)),
087 new OptimizationPlanAtomicElement(new EnterSSA()),
088 new OptimizationPlanAtomicElement(new IndexPropagation()),
089 new OptimizationPlanAtomicElement(new LoadEliminator())});
090 this.round = round;
091 }
092
093 static final boolean DEBUG = false;
094
095 @Override
096 public boolean shouldPerform(OptOptions options) {
097 return options.SSA_LOAD_ELIMINATION;
098 }
099
100 @Override
101 public String getName() {
102 return "Array SSA Load Elimination, round " + round;
103 }
104
105 /**
106 * which round of load elimination is this?
107 */
108 private final int round;
109
110 static final class LoadEliminator extends CompilerPhase {
111 @Override
112 public String getName() {
113 return "Load Eliminator";
114 }
115
116 /**
117 * Return this instance of this phase. This phase contains no
118 * per-compilation instance fields.
119 * @param ir not used
120 * @return this
121 */
122 @Override
123 public CompilerPhase newExecution(IR ir) {
124 return this;
125 }
126
127 /**
128 * main driver for redundant load elimination
129 * <p>
130 * Preconditions: Array SSA form and Global Value Numbers computed
131 * @param ir the governing IR
132 */
133 @Override
134 public void perform(IR ir) {
135
136 if (ir.desiredSSAOptions.getAbort()) return;
137
138 boolean didSomething = eliminateLoads(ir, ir.HIRInfo.indexPropagationSolution);
139 // Note that SSA is no longer valid!!!
140 // This will force construction of SSA next time we call EnterSSA
141 ir.actualSSAOptions.setScalarValid(false);
142 ir.actualSSAOptions.setHeapValid(false);
143 ir.HIRInfo.loadEliminationDidSomething = didSomething;
144
145 // clear the following field to avoid excess memory retention
146 ir.HIRInfo.indexPropagationSolution = null;
147 }
148 }
149
150 /**
151 * Eliminate redundant loads with respect to prior defs and prior
152 * uses.
153 *
154 * @return true if any load is eliminated.
155 */
156 static boolean eliminateLoads(IR ir, DF_Solution available) {
157 // maintain a mapping from value number to temporary register
158 HashMap<UseRecord, Register> registers = new HashMap<UseRecord, Register>();
159 UseRecordSet UseRepSet = replaceLoads(ir, available, registers);
160 replaceDefs(ir, UseRepSet, registers);
161
162 return (UseRepSet.size() > 0);
163 }
164
165 /**
166 * Walk over each instruction. If its a USE (load) of a heap
167 * variable and the value is available, then replace the load
168 * with a move from a register.
169 * <p>
170 * POSTCONDITION: sets up the mapping 'registers' from value number
171 * to temporary register
172 * @param ir the IR
173 * @param available information on which values are available
174 * @param registers a place to store information about temp registers
175 */
176 static UseRecordSet replaceLoads(IR ir, DF_Solution available, HashMap<UseRecord, Register> registers) {
177 UseRecordSet result = new UseRecordSet();
178 SSADictionary ssa = ir.HIRInfo.dictionary;
179 GlobalValueNumberState valueNumbers = ir.HIRInfo.valueNumbers;
180 for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
181 Instruction s = e.nextElement();
182 if (!GetField.conforms(s) && !GetStatic.conforms(s) && !ALoad.conforms(s)) {
183 continue;
184 }
185 // this instruction is a USE of heap variable H.
186 // get the lattice cell that holds the available indices
187 // for this heap variable
188 HeapOperand<?>[] H = ssa.getHeapUses(s);
189 if (H == null) {
190 // this case can happen due to certain magics that insert
191 // INT_LOAD instructions in HIR
192 // TODO: clean up HIR representation of these magics
193 continue;
194 }
195 if (H.length != 1) {
196 throw new OptimizingCompilerException("LoadElimination: load with wrong number of heap uses");
197 }
198 if (GetField.conforms(s) || GetStatic.conforms(s)) {
199 int valueNumber = -1;
200 if (GetField.conforms(s)) {
201 Object address = GetField.getRef(s);
202 valueNumber = valueNumbers.getValueNumber(address);
203 } else {
204 // for getStatic, always use the value number 0
205 valueNumber = 0;
206 }
207 ObjectCell cell = (ObjectCell) available.lookup(H[0].getHeapVariable());
208 if (cell == null) {
209 continue; // nothing available
210 }
211
212 // .. if H{valueNumber} is available ...
213 if (cell.contains(valueNumber)) {
214 result.add(H[0].getHeapVariable(), valueNumber);
215 TypeReference type = ResultCarrier.getResult(s).getType();
216 Register r = findOrCreateRegister(H[0].getHeapType(), valueNumber, registers, ir.regpool, type);
217 if (DEBUG) {
218 System.out.println("ELIMINATING LOAD " + s);
219 }
220 replaceLoadWithMove(r, s);
221 }
222 } else { // ALoad.conforms(s)
223 Object array = ALoad.getArray(s);
224 Object index = ALoad.getIndex(s);
225 ArrayCell cell = (ArrayCell) available.lookup(H[0].getHeapVariable());
226 if (cell == null) {
227 continue; // nothing available
228 }
229 int v1 = valueNumbers.getValueNumber(array);
230 int v2 = valueNumbers.getValueNumber(index);
231 // .. if H{<v1,v2>} is available ...
232 if (cell.contains(v1, v2)) {
233 result.add(H[0].getHeapVariable(), v1, v2);
234 TypeReference type = ALoad.getResult(s).getType();
235 Register r =
236 findOrCreateRegister(H[0].getHeapVariable().getHeapType(), v1, v2, registers, ir.regpool, type);
237 if (DEBUG) {
238 System.out.println("ELIMINATING LOAD " + s);
239 }
240 replaceLoadWithMove(r, s);
241 }
242 }
243 }
244 return result;
245 }
246
247 /**
248 * Replace a Load instruction s with a load from a scalar register r
249 * <p>
250 * TODO: factor this functionality out elsewhere
251 */
252 static void replaceLoadWithMove(Register r, Instruction load) {
253 RegisterOperand dest = ResultCarrier.getResult(load);
254 RegisterOperand rop = new RegisterOperand(r, dest.getType());
255 load.replace(Move.create(IRTools.getMoveOp(dest.getType()), dest, rop));
256 }
257
258 /**
259 * Perform scalar replacement actions for a Def of a heap variable.
260 * <p>
261 * NOTE: Even loads can def a heap variable.
262 *
263 * @param UseRepSet stores the uses(loads) that have been eliminated
264 * @param registers mapping from valueNumber -> temporary register
265 */
266 static void replaceDefs(IR ir, UseRecordSet UseRepSet, HashMap<UseRecord, Register> registers) {
267 SSADictionary ssa = ir.HIRInfo.dictionary;
268 for (Enumeration<Instruction> e = ir.forwardInstrEnumerator(); e.hasMoreElements();) {
269 Instruction s = e.nextElement();
270 if (!GetField.conforms(s) &&
271 !GetStatic.conforms(s) &&
272 !PutField.conforms(s) &&
273 !PutStatic.conforms(s) &&
274 !ALoad.conforms(s) &&
275 !AStore.conforms(s)) {
276 continue;
277 }
278 if (!ssa.defsHeapVariable(s)) {
279 continue;
280 }
281 // this instruction is a DEF of heap variable H.
282 // Check if UseRepSet needs the scalar assigned by this def
283 HeapOperand<?>[] H = ssa.getHeapDefs(s);
284 if (H.length != 1) {
285 throw new OptimizingCompilerException("LoadElimination: encountered a store with more than one def? " +
286 s);
287 }
288 int valueNumber = -1;
289 Object index = null;
290 if (AStore.conforms(s)) {
291 Object address = AStore.getArray(s);
292 index = AStore.getIndex(s);
293 valueNumber = ir.HIRInfo.valueNumbers.getValueNumber(address);
294 } else if (GetField.conforms(s)) {
295 Object address = GetField.getRef(s);
296 valueNumber = ir.HIRInfo.valueNumbers.getValueNumber(address);
297 } else if (PutField.conforms(s)) {
298 Object address = PutField.getRef(s);
299 valueNumber = ir.HIRInfo.valueNumbers.getValueNumber(address);
300 } else if (GetStatic.conforms(s)) {
301 valueNumber = 0;
302 } else if (PutStatic.conforms(s)) {
303 valueNumber = 0;
304 } else if (ALoad.conforms(s)) {
305 Object address = ALoad.getArray(s);
306 valueNumber = ir.HIRInfo.valueNumbers.getValueNumber(address);
307 index = ALoad.getIndex(s);
308 }
309 if (index == null) {
310 // Load/Store
311 if (UseRepSet.containsMatchingUse(H[0].getHeapVariable(), valueNumber)) {
312 Operand value = null;
313 if (PutField.conforms(s)) {
314 value = PutField.getValue(s);
315 } else if (PutStatic.conforms(s)) {
316 value = PutStatic.getValue(s);
317 } else if (GetField.conforms(s) || GetStatic.conforms(s)) {
318 value = ResultCarrier.getResult(s);
319 }
320 TypeReference type = value.getType();
321 Register r = findOrCreateRegister(H[0].getHeapType(), valueNumber, registers, ir.regpool, type);
322 appendMove(r, value, s);
323 }
324 } else {
325 // ALoad / AStore
326 int v1 = valueNumber;
327 int v2 = ir.HIRInfo.valueNumbers.getValueNumber(index);
328 if (UseRepSet.containsMatchingUse(H[0].getHeapVariable(), v1, v2)) {
329 Operand value = null;
330 if (AStore.conforms(s)) {
331 value = AStore.getValue(s);
332 } else if (ALoad.conforms(s)) {
333 value = ALoad.getResult(s);
334 }
335 TypeReference type = value.getType();
336 Register r = findOrCreateRegister(H[0].getHeapType(), v1, v2, registers, ir.regpool, type);
337 appendMove(r, value, s);
338 }
339 }
340 }
341 }
342
343 /**
344 * Append an instruction after a store instruction that caches
345 * value in register r.
346 */
347 static void appendMove(Register r, Operand src, Instruction store) {
348 TypeReference type = src.getType();
349 RegisterOperand rop = new RegisterOperand(r, type);
350 store.insertAfter(Move.create(IRTools.getMoveOp(type), rop, src.copy()));
351 }
352
353 /**
354 * Given a value number, return the temporary register allocated
355 * for that value number. Create one if necessary.
356 *
357 * @param heapType a TypeReference or RVMField identifying the array SSA
358 * heap type
359 * @param valueNumber
360 * @param registers a mapping from value number to temporary register
361 * @param pool register pool to allocate new temporaries from
362 * @param type the type to store in the new register
363 */
364 static Register findOrCreateRegister(Object heapType, int valueNumber, HashMap<UseRecord, Register> registers,
365 RegisterPool pool, TypeReference type) {
366 UseRecord key = new UseRecord(heapType, valueNumber);
367 Register result = registers.get(key);
368 if (result == null) {
369 // create a new temp and insert it in the mapping
370 result = pool.makeTemp(type).getRegister();
371 registers.put(key, result);
372 }
373 return result;
374 }
375
376 /**
377 * Given a pair of value numbers, return the temporary register
378 * allocated for that pair. Create one if necessary.
379 *
380 * @param heapType a TypeReference identifying the array SSA
381 * heap type
382 * @param v1 first value number
383 * @param v2 second value number
384 * @param registers a mapping from value number to temporary register
385 * @param pool register pool to allocate new temporaries from
386 * @param type the type to store in the new register
387 */
388 static Register findOrCreateRegister(Object heapType, int v1, int v2, HashMap<UseRecord, Register> registers,
389 RegisterPool pool, TypeReference type) {
390 UseRecord key = new UseRecord(heapType, v1, v2);
391 Register result = registers.get(key);
392 if (result == null) {
393 // create a new temp and insert it in the mapping
394 result = pool.makeTemp(type).getRegister();
395 registers.put(key, result);
396 }
397 return result;
398 }
399
400 // A UseRecord represents a load that will be eliminated
401 static class UseRecord {
402 final Object type; // may be either a TypeReference or a RVMField
403 final int v1; // first value number (object pointer)
404 final int v2; // second value number (array index)
405 static final int NONE = -2;
406
407 UseRecord(Object type, int valueNumber) {
408 this.type = type;
409 this.v1 = valueNumber;
410 this.v2 = NONE;
411 }
412
413 UseRecord(Object type, int v1, int v2) {
414 this.type = type;
415 this.v1 = v1;
416 this.v2 = v2;
417 }
418
419 @Override
420 public boolean equals(Object o) {
421 if (o instanceof UseRecord) {
422 UseRecord u = (UseRecord) o;
423 return ((u.type.equals(type)) && (u.v1 == v1) && (u.v2 == v2));
424 }
425 return false;
426 }
427
428 @Override
429 public int hashCode() {
430 return type.hashCode() + v1 + v2;
431 }
432 }
433
434 static final class UseRecordSet {
435 final HashSet<UseRecord> set = new HashSet<UseRecord>(10);
436
437 // Does this set contain a use that has the same type as H and
438 // the given value number?
439 boolean containsMatchingUse(HeapVariable<?> H, int valueNumber) {
440 Object type = H.getHeapType();
441 UseRecord u = new UseRecord(type, valueNumber);
442 return (set.contains(u));
443 }
444
445 // Does this set contain a use that has the same type as H and
446 // the given value number pair <v1,v2>?
447 boolean containsMatchingUse(HeapVariable<?> H, int v1, int v2) {
448 Object type = H.getHeapType();
449 UseRecord u = new UseRecord(type, v1, v2);
450 return (set.contains(u));
451 }
452
453 // add a USE to the set
454 void add(HeapVariable<?> H, int valueNumber) {
455 UseRecord u = new UseRecord(H.getHeapType(), valueNumber);
456 set.add(u);
457 }
458
459 void add(HeapVariable<?> H, int v1, int v2) {
460 UseRecord u = new UseRecord(H.getHeapType(), v1, v2);
461 set.add(u);
462 }
463
464 int size() { return set.size(); }
465 }
466
467 /**
468 * @param map a mapping from key to HashSet
469 * @param key a key into the map
470 * @return the set map(key). create one if none exists.
471 */
472 private static <T> HashSet<T> findOrCreateIndexSet(HashMap<Object, HashSet<T>> map, Object key) {
473 HashSet<T> result = map.get(key);
474 if (result == null) {
475 result = new HashSet<T>(5);
476 map.put(key, result);
477 }
478 return result;
479 }
480
481 /**
482 * Do a quick pass over the IR, and return types that are candidates
483 * for redundant load elimination.<p>
484 *
485 * Algorithm: return those types T where
486 * <ul>
487 * <li>there's a load L(i) of type T
488 * <li>there's another load or store M(j) of type T, M!=L and V(i) == V(j)
489 * </ul>
490 * <p>
491 * The result contains objects of type RVMField and TypeReference, whose
492 * narrowest common ancestor is Object.
493 */
494 @SuppressWarnings("unchecked")
495 public static HashSet<Object> getCandidates(IR ir) {
496 GlobalValueNumberState valueNumbers = ir.HIRInfo.valueNumbers;
497 // which types have we seen loads for?
498 HashSet<Object> seenLoad = new HashSet<Object>(10);
499 // which static fields have we seen stores for?
500 HashSet<RVMField> seenStore = new HashSet<RVMField>(10);
501 HashSet<Object> resultSet = new HashSet<Object>(10);
502 HashSet<FieldReference> forbidden = new HashSet<FieldReference>(10);
503 // for each type T, indices(T) gives the set of value number (pairs)
504 // that identify the indices seen in memory accesses to type T.
505 HashMap indices = new HashMap(10);
506
507 for (Enumeration be = ir.getBasicBlocks(); be.hasMoreElements();) {
508 BasicBlock bb = (BasicBlock) be.nextElement();
509 if (!ir.options.FREQ_FOCUS_EFFORT || !bb.getInfrequent()) {
510 for (Enumeration<Instruction> e = bb.forwardInstrEnumerator(); e.hasMoreElements();) {
511 Instruction s = e.nextElement();
512 switch (s.operator().opcode) {
513 case GETFIELD_opcode: {
514 Operand ref = GetField.getRef(s);
515 FieldReference fr = GetField.getLocation(s).getFieldRef();
516 RVMField f = fr.peekResolvedField();
517 if (f == null) {
518 forbidden.add(fr);
519 } else {
520 HashSet<Integer> numbers = findOrCreateIndexSet(indices, f);
521 int v = valueNumbers.getValueNumber(ref);
522 Integer V = v;
523 if (numbers.contains(V)) {
524 resultSet.add(f);
525 } else {
526 numbers.add(V);
527 }
528 seenLoad.add(f);
529 }
530 }
531 break;
532 case PUTFIELD_opcode: {
533 Operand ref = PutField.getRef(s);
534 FieldReference fr = PutField.getLocation(s).getFieldRef();
535 RVMField f = fr.peekResolvedField();
536 if (f == null) {
537 forbidden.add(fr);
538 } else {
539 HashSet<Integer> numbers = findOrCreateIndexSet(indices, f);
540 int v = valueNumbers.getValueNumber(ref);
541 Integer V = v;
542 if (numbers.contains(V)) {
543 if (seenLoad.contains(f)) {
544 resultSet.add(f);
545 }
546 } else {
547 numbers.add(V);
548 }
549 }
550 }
551 break;
552 case GETSTATIC_opcode: {
553 FieldReference fr = GetStatic.getLocation(s).getFieldRef();
554 RVMField f = fr.peekResolvedField();
555 if (f == null) {
556 forbidden.add(fr);
557 } else {
558 if (seenLoad.contains(f) || seenStore.contains(f)) {
559 resultSet.add(f);
560 }
561 seenLoad.add(f);
562 }
563 }
564 break;
565 case PUTSTATIC_opcode: {
566 FieldReference fr = PutStatic.getLocation(s).getFieldRef();
567 RVMField f = fr.peekResolvedField();
568 if (f == null) {
569 forbidden.add(fr);
570 } else {
571 if (seenLoad.contains(f)) {
572 resultSet.add(f);
573 }
574 seenStore.add(f);
575 }
576 }
577 break;
578 case INT_ALOAD_opcode:
579 case LONG_ALOAD_opcode:
580 case FLOAT_ALOAD_opcode:
581 case DOUBLE_ALOAD_opcode:
582 case REF_ALOAD_opcode:
583 case BYTE_ALOAD_opcode:
584 case UBYTE_ALOAD_opcode:
585 case USHORT_ALOAD_opcode:
586 case SHORT_ALOAD_opcode: {
587 Operand ref = ALoad.getArray(s);
588 TypeReference type = ref.getType();
589 if (type.isArrayType()) {
590 if (!type.getArrayElementType().isPrimitiveType()) {
591 type = TypeReference.JavaLangObjectArray;
592 }
593 }
594 Operand index = ALoad.getIndex(s);
595
596 HashSet<ValueNumberPair> numbers = findOrCreateIndexSet(indices, type);
597 int v1 = valueNumbers.getValueNumber(ref);
598 int v2 = valueNumbers.getValueNumber(index);
599 ValueNumberPair V = new ValueNumberPair(v1, v2);
600 if (numbers.contains(V)) {
601 resultSet.add(type);
602 } else {
603 numbers.add(V);
604 }
605 seenLoad.add(type);
606 }
607
608 break;
609
610 case INT_ASTORE_opcode:
611 case LONG_ASTORE_opcode:
612 case FLOAT_ASTORE_opcode:
613 case DOUBLE_ASTORE_opcode:
614 case REF_ASTORE_opcode:
615 case BYTE_ASTORE_opcode:
616 case SHORT_ASTORE_opcode:
617
618 {
619 Operand ref = AStore.getArray(s);
620 TypeReference type = ref.getType();
621 if (type.isArrayType()) {
622 if (!type.getArrayElementType().isPrimitiveType()) {
623 type = TypeReference.JavaLangObjectArray;
624 }
625 }
626 Operand index = AStore.getIndex(s);
627
628 HashSet<ValueNumberPair> numbers = findOrCreateIndexSet(indices, type);
629 int v1 = valueNumbers.getValueNumber(ref);
630 int v2 = valueNumbers.getValueNumber(index);
631 ValueNumberPair V = new ValueNumberPair(v1, v2);
632
633 if (numbers.contains(V)) {
634 if (seenLoad.contains(type)) {
635 resultSet.add(type);
636 }
637 } else {
638 numbers.add(V);
639 }
640 }
641 break;
642
643 default:
644 break;
645 }
646 }
647 }
648 }
649
650 // If we have found an unresolved field reference, then conservatively
651 // remove all fields that it might refer to from the resultSet.
652 for (final FieldReference fieldReference : forbidden) {
653 for (Iterator i2 = resultSet.iterator(); i2.hasNext();) {
654 Object it = i2.next();
655 if (it instanceof RVMField) {
656 final RVMField field = (RVMField) it;
657 if (!fieldReference.definitelyDifferent(field.getMemberRef().asFieldReference())) {
658 i2.remove();
659 }
660 }
661 }
662 }
663
664 return resultSet;
665 }
666
667 /**
668 * This class sets up the IR state prior to entering SSA for load
669 * elimination
670 */
671 public static class LoadEliminationPreparation extends CompilerPhase {
672 /**
673 * Cosntructor
674 */
675 public LoadEliminationPreparation(int round) {
676 super(new Object[]{round});
677 this.round = round;
678 }
679
680 /**
681 * Constructor for this compiler phase
682 */
683 private static final Constructor<CompilerPhase> constructor =
684 getCompilerPhaseConstructor(LoadEliminationPreparation.class, new Class[]{Integer.TYPE});
685
686 /**
687 * Get a constructor object for this compiler phase
688 * @return compiler phase constructor
689 */
690 @Override
691 public Constructor<CompilerPhase> getClassConstructor() {
692 return constructor;
693 }
694
695 @Override
696 public final boolean shouldPerform(OptOptions options) {
697 return options.SSA_LOAD_ELIMINATION;
698 }
699
700 @Override
701 public final String getName() {
702 return "Load Elimination Preparation";
703 }
704
705 private final int round;
706
707 @Override
708 public final void perform(IR ir) {
709 // register in the IR the SSA properties we need for load
710 // elimination
711 ir.desiredSSAOptions = new SSAOptions();
712 ir.desiredSSAOptions.setScalarsOnly(false);
713 ir.desiredSSAOptions.setBackwards(false);
714 ir.desiredSSAOptions.setInsertUsePhis(true);
715 ir.desiredSSAOptions.setHeapTypes(LoadElimination.getCandidates(ir));
716 ir.desiredSSAOptions.setAbort((round > ir.options.SSA_LOAD_ELIMINATION_ROUNDS) ||
717 (!ir.HIRInfo.loadEliminationDidSomething));
718 }
719 }
720
721 /**
722 * This class sets up the IR state prior to entering SSA for GVN.
723 */
724 public static class GVNPreparation extends CompilerPhase {
725
726 @Override
727 public final boolean shouldPerform(OptOptions options) {
728 return options.SSA_LOAD_ELIMINATION;
729 }
730
731 @Override
732 public final String getName() {
733 return "GVN Preparation";
734 }
735
736 private final int round;
737
738 /**
739 * Constructor
740 */
741 public GVNPreparation(int round) {
742 super(new Object[]{round});
743 this.round = round;
744 }
745
746 /**
747 * Constructor for this compiler phase
748 */
749 private static final Constructor<CompilerPhase> constructor =
750 getCompilerPhaseConstructor(GVNPreparation.class, new Class[]{Integer.TYPE});
751
752 /**
753 * Get a constructor object for this compiler phase
754 * @return compiler phase constructor
755 */
756 @Override
757 public Constructor<CompilerPhase> getClassConstructor() {
758 return constructor;
759 }
760
761 @Override
762 public final void perform(IR ir) {
763 // register in the IR the SSA properties we need for load
764 // elimination
765 ir.desiredSSAOptions = new SSAOptions();
766 ir.desiredSSAOptions.setScalarsOnly(true);
767 ir.desiredSSAOptions.setBackwards(false);
768 ir.desiredSSAOptions.setInsertUsePhis(false);
769 ir.desiredSSAOptions.setAbort((round > ir.options.SSA_LOAD_ELIMINATION_ROUNDS) ||
770 (!ir.HIRInfo.loadEliminationDidSomething));
771 }
772 }
773 }