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;
014
015 import java.lang.reflect.Constructor;
016 import java.util.ArrayList;
017 import java.util.Enumeration;
018
019 import org.jikesrvm.VM;
020 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
021 import org.jikesrvm.compilers.opt.ir.Binary;
022 import org.jikesrvm.compilers.opt.ir.BoundsCheck;
023 import org.jikesrvm.compilers.opt.ir.Call;
024 import org.jikesrvm.compilers.opt.ir.GetField;
025 import org.jikesrvm.compilers.opt.ir.GetStatic;
026 import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
027 import org.jikesrvm.compilers.opt.ir.GuardedBinary;
028 import org.jikesrvm.compilers.opt.ir.GuardedUnary;
029 import org.jikesrvm.compilers.opt.ir.InstanceOf;
030 import org.jikesrvm.compilers.opt.ir.LocationCarrier;
031 import org.jikesrvm.compilers.opt.ir.Move;
032 import org.jikesrvm.compilers.opt.ir.NullCheck;
033 import org.jikesrvm.compilers.opt.ir.BasicBlock;
034 import org.jikesrvm.compilers.opt.ir.IR;
035 import org.jikesrvm.compilers.opt.ir.IRTools;
036 import org.jikesrvm.compilers.opt.ir.Instruction;
037 import org.jikesrvm.compilers.opt.ir.InstructionFormat;
038 import org.jikesrvm.compilers.opt.ir.Operator;
039 import static org.jikesrvm.compilers.opt.ir.Operators.BOUNDS_CHECK_opcode;
040 import static org.jikesrvm.compilers.opt.ir.Operators.GUARD_MOVE;
041 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ZERO_CHECK_opcode;
042 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ZERO_CHECK_opcode;
043 import static org.jikesrvm.compilers.opt.ir.Operators.MONITORENTER_opcode;
044 import static org.jikesrvm.compilers.opt.ir.Operators.MONITOREXIT_opcode;
045 import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK_opcode;
046 import static org.jikesrvm.compilers.opt.ir.Operators.READ_CEILING_opcode;
047 import static org.jikesrvm.compilers.opt.ir.Operators.REF_MOVE;
048 import static org.jikesrvm.compilers.opt.ir.Operators.TRAP_IF_opcode;
049 import static org.jikesrvm.compilers.opt.ir.Operators.WRITE_FLOOR_opcode;
050 import org.jikesrvm.compilers.opt.ir.Register;
051 import org.jikesrvm.compilers.opt.ir.PutField;
052 import org.jikesrvm.compilers.opt.ir.PutStatic;
053 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
054 import org.jikesrvm.compilers.opt.ir.TrapIf;
055 import org.jikesrvm.compilers.opt.ir.TypeCheck;
056 import org.jikesrvm.compilers.opt.ir.Unary;
057 import org.jikesrvm.compilers.opt.ir.ZeroCheck;
058 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
059 import org.jikesrvm.compilers.opt.ir.operand.LocationOperand;
060 import org.jikesrvm.compilers.opt.ir.operand.Operand;
061 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
062 import org.jikesrvm.compilers.opt.ir.operand.TrapCodeOperand;
063
064 /**
065 * Perform local common-subexpression elimination for a factored basic
066 * block.
067 * <ul>
068 * <li> Note: this module also performs scalar replacement of loads
069 * <li> Note: this module also performs elimination of redundant
070 * nullchecks, boundchecks, and zero checks.
071 * </ul>
072 * Algorithm: Muchnick pp.379-385
073 */
074 public class LocalCSE extends CompilerPhase {
075 private final boolean isHIR;
076
077 /**
078 * Constructor
079 */
080 public LocalCSE(boolean isHIR) {
081 super(new Object[]{isHIR});
082 this.isHIR = isHIR;
083 }
084
085 /**
086 * Constructor for this compiler phase
087 */
088 private static final Constructor<CompilerPhase> constructor =
089 getCompilerPhaseConstructor(LocalCSE.class, new Class[]{Boolean.TYPE});
090
091 /**
092 * Get a constructor object for this compiler phase
093 * @return compiler phase constructor
094 */
095 @Override
096 public Constructor<CompilerPhase> getClassConstructor() {
097 return constructor;
098 }
099
100 @Override
101 public final void reportAdditionalStats() {
102 VM.sysWrite(" ");
103 VM.sysWrite(container.counter1 / container.counter2 * 100, 2);
104 VM.sysWrite("% Infrequent BBs");
105 }
106
107 @Override
108 public final boolean shouldPerform(OptOptions options) {
109 return options.LOCAL_CSE;
110 }
111
112 @Override
113 public final String getName() {
114 return "Local CSE";
115 }
116
117 /**
118 * Perform Local CSE for a method.
119 *
120 * @param ir the IR to optimize
121 */
122 @Override
123 public final void perform(IR ir) {
124 // iterate over each basic block
125 for (BasicBlock bb = ir.firstBasicBlockInCodeOrder(); bb != null; bb = bb.nextBasicBlockInCodeOrder()) {
126 if (bb.isEmpty()) continue;
127 container.counter2++;
128 if (bb.getInfrequent()) {
129 container.counter1++;
130 if (ir.options.FREQ_FOCUS_EFFORT) continue;
131 }
132 if (isHIR) {
133 optimizeBasicBlockHIR(ir, bb);
134 } else {
135 optimizeBasicBlockLIR(ir, bb);
136 }
137 }
138 }
139
140 /**
141 * Perform Local CSE for a basic block in HIR.
142 *
143 * @param ir the method's ir
144 * @param bb the basic block
145 */
146 private void optimizeBasicBlockHIR(IR ir, BasicBlock bb) {
147 AvExCache cache = new AvExCache(ir.options, true);
148 // iterate over all instructions in the basic block
149 for (Instruction inst = bb.firstRealInstruction(),
150 sentinel = bb.lastInstruction(),
151 nextInstr = null; inst != sentinel; inst = nextInstr) {
152 nextInstr = inst.nextInstructionInCodeOrder(); // cache before we
153 // mutate prev/next links
154 // 1. try and replace this instruction according to
155 // available expressions in the cache, and update cache
156 // accordingly.
157 if (isLoadInstruction(inst)) {
158 loadHelper(ir, cache, inst);
159 } else if (isStoreInstruction(inst)) {
160 storeHelper(cache, inst);
161 } else if (isExpression(inst)) {
162 expressionHelper(ir, cache, inst);
163 } else if (isCheck(inst)) {
164 checkHelper(ir, cache, inst);
165 } else if (isTypeCheck(inst)) {
166 typeCheckHelper(ir, cache, inst);
167 }
168
169 // 2. update the cache according to which expressions this
170 // instruction kills
171 cache.eliminate(inst);
172 // Non-pure CALL instructions and synchronizations KILL all memory locations!
173 if (inst.isNonPureCall()) {
174 cache.invalidateAllLoads();
175 } else if (isSynchronizing(inst) || inst.isDynamicLinkingPoint()) {
176 cache.invalidateAllLoads();
177 }
178 }
179 }
180
181 /**
182 * Perform Local CSE for a basic block in LIR.
183 *
184 * @param ir the method's ir
185 * @param bb the basic block
186 */
187 private void optimizeBasicBlockLIR(IR ir, BasicBlock bb) {
188 AvExCache cache = new AvExCache(ir.options, false);
189 // iterate over all instructions in the basic block
190 for (Instruction inst = bb.firstRealInstruction(),
191 sentinel = bb.lastInstruction(),
192 nextInstr = null; inst != sentinel; inst = nextInstr) {
193 nextInstr = inst.nextInstructionInCodeOrder(); // cache before we
194 // mutate prev/next links
195 // 1. try and replace this instruction according to
196 // available expressions in the cache, and update cache
197 // accordingly.
198 if (isExpression(inst)) {
199 expressionHelper(ir, cache, inst);
200 } else if (isCheck(inst)) {
201 checkHelper(ir, cache, inst);
202 }
203
204 // 2. update the cache according to which expressions this
205 // instruction kills
206 cache.eliminate(inst);
207 }
208 }
209
210 /**
211 * Is a given instruction a CSE-able load?
212 */
213 public static boolean isLoadInstruction(Instruction s) {
214 return GetField.conforms(s) || GetStatic.conforms(s);
215 }
216
217 /**
218 * Is a given instruction a CSE-able store?
219 */
220 public static boolean isStoreInstruction(Instruction s) {
221 return PutField.conforms(s) || PutStatic.conforms(s);
222 }
223
224 /**
225 * Does the instruction compute some expression?
226 *
227 * @param inst the instruction in question
228 * @return true or false, as appropriate
229 */
230 private boolean isExpression(Instruction inst) {
231 if (inst.isDynamicLinkingPoint()) return false;
232 switch (inst.operator.format) {
233 case InstructionFormat.Unary_format:
234 case InstructionFormat.GuardedUnary_format:
235 case InstructionFormat.Binary_format:
236 case InstructionFormat.GuardedBinary_format:
237 case InstructionFormat.InstanceOf_format:
238 return true;
239 case InstructionFormat.Call_format:
240 return inst.isPureCall();
241 default:
242 return false;
243 }
244 }
245
246 /**
247 * Is the given instruction a check instruction?
248 *
249 * @param inst the instruction in question
250 * @return true or false, as appropriate
251 */
252 private boolean isCheck(Instruction inst) {
253 switch (inst.getOpcode()) {
254 case NULL_CHECK_opcode:
255 case BOUNDS_CHECK_opcode:
256 case INT_ZERO_CHECK_opcode:
257 case LONG_ZERO_CHECK_opcode:
258 return true;
259 case TRAP_IF_opcode:
260 TrapCodeOperand tc = TrapIf.getTCode(inst);
261 return tc.isNullPtr() || tc.isArrayBounds() || tc.isDivByZero();
262 default:
263 return false;
264 }
265 }
266
267 private boolean isTypeCheck(Instruction inst) {
268 return TypeCheck.conforms(inst);
269 }
270
271 /**
272 * Process a load instruction
273 *
274 * @param ir the containing IR object.
275 * @param cache the cache of available expressions
276 * @param inst the instruction begin processed
277 */
278 private void loadHelper(IR ir, AvExCache cache, Instruction inst) {
279 LocationOperand loc = LocationCarrier.getLocation(inst);
280 if (loc.mayBeVolatile()) return; // don't optimize volatile fields
281
282 // look up the expression in the cache
283 AvailableExpression ae = cache.find(inst);
284 if (ae != null) {
285 RegisterOperand dest = ResultCarrier.getClearResult(inst);
286 if (ae.tmp == null) {
287 // (1) generate a new temporary, and store in the AE cache
288 RegisterOperand newRes = ir.regpool.makeTemp(dest.getType());
289 ae.tmp = newRes.getRegister();
290 // (2) get the CSE value into newRes
291 if (ae.isLoad()) {
292 // the first appearance was a load.
293 // Modify the first load to assign its result to a new temporary
294 // and then insert a move from the new temporary to the old result
295 // after the mutated first load.
296 RegisterOperand res = ResultCarrier.getClearResult(ae.inst);
297 ResultCarrier.setResult(ae.inst, newRes);
298 ae.inst.insertAfter(Move.create(getMoveOp(res), res, newRes.copyD2U()));
299 } else {
300 // the first appearance was a store.
301 // Insert a move that assigns the value to newRes before
302 // the store instruction.
303 Operand value;
304 if (PutStatic.conforms(ae.inst)) {
305 value = PutStatic.getValue(ae.inst);
306 } else {
307 value = PutField.getValue(ae.inst);
308 }
309 ae.inst.insertBefore(Move.create(getMoveOp(newRes), newRes, value.copy()));
310 }
311 // (3) replace second load with a move from the new temporary
312 Move.mutate(inst, getMoveOp(dest), dest, newRes.copyD2U());
313 } else {
314 // already have a temp. replace the load with a move
315 RegisterOperand newRes = new RegisterOperand(ae.tmp, dest.getType());
316 Move.mutate(inst, getMoveOp(dest), dest, newRes);
317 }
318 } else {
319 // did not find a match: insert new entry in cache
320 cache.insert(inst);
321 }
322 }
323
324 /**
325 * Process a store instruction
326 *
327 * @param cache the cache of available expressions
328 * @param inst the instruction begin processed
329 */
330 private void storeHelper(AvExCache cache, Instruction inst) {
331 LocationOperand loc = LocationCarrier.getLocation(inst);
332 if (loc.mayBeVolatile()) return; // don't optimize volatile fields
333
334 // look up the expression in the cache
335 AvailableExpression ae = cache.find(inst);
336 if (ae == null) {
337 // did not find a match: insert new entry in cache
338 cache.insert(inst);
339 }
340 }
341
342 /**
343 * Process a unary or binary expression.
344 *
345 * @param ir the containing IR object
346 * @param cache the cache of available expressions
347 * @param inst the instruction begin processed
348 */
349 private void expressionHelper(IR ir, AvExCache cache, Instruction inst) {
350 // look up the expression in the cache
351 AvailableExpression ae = cache.find(inst);
352 if (ae != null) {
353 RegisterOperand dest = ResultCarrier.getClearResult(inst);
354 if (ae.tmp == null) {
355 // (1) generate a new temporary, and store in the AE cache
356 RegisterOperand newRes = ir.regpool.makeTemp(dest.getType());
357 ae.tmp = newRes.getRegister();
358 // (2) Modify ae.inst to assign its result to the new temporary
359 // and then insert a move from the new temporary to the old result
360 // of ae.inst after ae.inst.
361 RegisterOperand res = ResultCarrier.getClearResult(ae.inst);
362 ResultCarrier.setResult(ae.inst, newRes);
363 ae.inst.insertAfter(Move.create(getMoveOp(res), res, newRes.copyD2U()));
364 // (3) replace inst with a move from the new temporary
365 Move.mutate(inst, getMoveOp(dest), dest, newRes.copyD2U());
366 } else {
367 // already have a temp. replace inst with a move
368 RegisterOperand newRes = new RegisterOperand(ae.tmp, dest.getType());
369 Move.mutate(inst, getMoveOp(dest), dest, newRes);
370 }
371 } else {
372 // did not find a match: insert new entry in cache
373 cache.insert(inst);
374 }
375 }
376
377 /**
378 * Process a check instruction
379 *
380 * @param cache the cache of available expressions
381 * @param inst the instruction begin processed
382 */
383 private void checkHelper(IR ir, AvExCache cache, Instruction inst) {
384 // look up the check in the cache
385 AvailableExpression ae = cache.find(inst);
386 if (ae != null) {
387 RegisterOperand dest = GuardResultCarrier.getClearGuardResult(inst);
388 if (ae.tmp == null) {
389 // generate a new temporary, and store in the AE cache
390 RegisterOperand newRes = ir.regpool.makeTemp(dest.getType());
391 ae.tmp = newRes.getRegister();
392 // (2) Modify ae.inst to assign its guard result to the new temporary
393 // and then insert a guard move from the new temporary to the
394 // old guard result of ae.inst after ae.inst.
395 RegisterOperand res = GuardResultCarrier.getClearGuardResult(ae.inst);
396 GuardResultCarrier.setGuardResult(ae.inst, newRes);
397 ae.inst.insertAfter(Move.create(GUARD_MOVE, res, newRes.copyD2U()));
398 // (3) replace inst with a move from the new temporary
399 Move.mutate(inst, GUARD_MOVE, dest, newRes.copyD2U());
400 } else {
401 // already have a temp. replace inst with a guard move
402 RegisterOperand newRes = new RegisterOperand(ae.tmp, dest.getType());
403 Move.mutate(inst, GUARD_MOVE, dest, newRes);
404 }
405 } else {
406 // did not find a match: insert new entry in cache
407 cache.insert(inst);
408 }
409 }
410
411 /**
412 * Process a type check instruction
413 *
414 * @param ir Unused
415 * @param cache The cache of available expressions.
416 * @param inst The instruction being processed
417 */
418 private static void typeCheckHelper(IR ir, AvExCache cache, Instruction inst) {
419 // look up the check in the cache
420 AvailableExpression ae = cache.find(inst);
421 if (ae != null) {
422 // it's a duplicate; blow it away.
423 Move.mutate(inst, REF_MOVE, TypeCheck.getClearResult(inst), TypeCheck.getClearRef(inst));
424 } else {
425 // did not find a match: insert new entry in cache
426 cache.insert(inst);
427 }
428 }
429
430 private static Operator getMoveOp(RegisterOperand r) {
431 return IRTools.getMoveOp(r.getType());
432 }
433
434 /**
435 * Is this a synchronizing instruction?
436 *
437 * @param inst the instruction in question
438 */
439 private static boolean isSynchronizing(Instruction inst) {
440 switch (inst.getOpcode()) {
441 case MONITORENTER_opcode:
442 case MONITOREXIT_opcode:
443 case READ_CEILING_opcode:
444 case WRITE_FLOOR_opcode:
445 return true;
446 default:
447 return false;
448 }
449 }
450
451 /**
452 * Implements a cache of Available Expressions
453 */
454 protected static final class AvExCache {
455 /** Implementation of the cache */
456 private final ArrayList<AvailableExpression> cache = new ArrayList<AvailableExpression>(3);
457
458 private final OptOptions options;
459 private final boolean doMemory;
460
461 AvExCache(OptOptions opts, boolean doMem) {
462 options = opts;
463 doMemory = doMem;
464 }
465
466 /**
467 * Find and return a matching available expression.
468 *
469 * @param inst the instruction to match
470 * @return the matching AE if found, null otherwise
471 */
472 public AvailableExpression find(Instruction inst) {
473 Operator opr = inst.operator();
474 Operand[] ops = null;
475 LocationOperand location = null;
476 switch (inst.operator.format) {
477 case InstructionFormat.GetField_format:
478 if (VM.VerifyAssertions) VM._assert(doMemory);
479 ops = new Operand[]{GetField.getRef(inst)};
480 location = GetField.getLocation(inst);
481 break;
482 case InstructionFormat.GetStatic_format:
483 if (VM.VerifyAssertions) VM._assert(doMemory);
484 location = GetStatic.getLocation(inst);
485 break;
486 case InstructionFormat.PutField_format:
487 if (VM.VerifyAssertions) VM._assert(doMemory);
488 ops = new Operand[]{PutField.getRef(inst)};
489 location = PutField.getLocation(inst);
490 break;
491 case InstructionFormat.PutStatic_format:
492 if (VM.VerifyAssertions) VM._assert(doMemory);
493 location = PutStatic.getLocation(inst);
494 break;
495 case InstructionFormat.Unary_format:
496 ops = new Operand[]{Unary.getVal(inst)};
497 break;
498 case InstructionFormat.GuardedUnary_format:
499 ops = new Operand[]{GuardedUnary.getVal(inst)};
500 break;
501 case InstructionFormat.Binary_format:
502 ops = new Operand[]{Binary.getVal1(inst), Binary.getVal2(inst)};
503 break;
504 case InstructionFormat.GuardedBinary_format:
505 ops = new Operand[]{GuardedBinary.getVal1(inst), GuardedBinary.getVal2(inst)};
506 break;
507 case InstructionFormat.Move_format:
508 ops = new Operand[]{Move.getVal(inst)};
509 break;
510 case InstructionFormat.NullCheck_format:
511 ops = new Operand[]{NullCheck.getRef(inst)};
512 break;
513 case InstructionFormat.ZeroCheck_format:
514 ops = new Operand[]{ZeroCheck.getValue(inst)};
515 break;
516 case InstructionFormat.BoundsCheck_format:
517 ops = new Operand[]{BoundsCheck.getRef(inst), BoundsCheck.getIndex(inst)};
518 break;
519 case InstructionFormat.TrapIf_format:
520 ops = new Operand[]{TrapIf.getVal1(inst), TrapIf.getVal2(inst), TrapIf.getTCode(inst)};
521 break;
522 case InstructionFormat.TypeCheck_format:
523 ops = new Operand[]{TypeCheck.getRef(inst), TypeCheck.getType(inst)};
524 break;
525 case InstructionFormat.InstanceOf_format:
526 ops = new Operand[]{InstanceOf.getRef(inst), InstanceOf.getType(inst)};
527 break;
528 case InstructionFormat.Call_format:
529 int numParams = Call.getNumberOfParams(inst);
530 ops = new Operand[numParams+2];
531 ops[0] = Call.getAddress(inst);
532 ops[1] = Call.getMethod(inst);
533 for (int i=0; i < numParams; i++) {
534 ops[i+2] = Call.getParam(inst, i);
535 }
536 break;
537 default:
538 throw new OptimizingCompilerException("Unsupported type " + inst);
539 }
540
541 AvailableExpression ae = new AvailableExpression(inst, opr, ops, location, null);
542 int index = cache.indexOf(ae);
543 if (index == -1) {
544 return null;
545 }
546 return cache.get(index);
547 }
548
549 /**
550 * Insert a new available expression in the cache
551 *
552 * @param inst the instruction that defines the AE
553 */
554 public void insert(Instruction inst) {
555 Operator opr = inst.operator();
556 Operand[] ops = null;
557 LocationOperand location = null;
558
559 switch (inst.operator.format) {
560 case InstructionFormat.GetField_format:
561 if (VM.VerifyAssertions) VM._assert(doMemory);
562 ops = new Operand[]{GetField.getRef(inst)};
563 location = GetField.getLocation(inst);
564 break;
565 case InstructionFormat.GetStatic_format:
566 if (VM.VerifyAssertions) VM._assert(doMemory);
567 location = GetStatic.getLocation(inst);
568 break;
569 case InstructionFormat.PutField_format:
570 if (VM.VerifyAssertions) VM._assert(doMemory);
571 ops = new Operand[]{PutField.getRef(inst)};
572 location = PutField.getLocation(inst);
573 break;
574 case InstructionFormat.PutStatic_format:
575 if (VM.VerifyAssertions) VM._assert(doMemory);
576 location = PutStatic.getLocation(inst);
577 break;
578 case InstructionFormat.Unary_format:
579 ops = new Operand[]{Unary.getVal(inst)};
580 break;
581 case InstructionFormat.GuardedUnary_format:
582 ops = new Operand[]{GuardedUnary.getVal(inst)};
583 break;
584 case InstructionFormat.Binary_format:
585 ops = new Operand[]{Binary.getVal1(inst), Binary.getVal2(inst)};
586 break;
587 case InstructionFormat.GuardedBinary_format:
588 ops = new Operand[]{GuardedBinary.getVal1(inst), GuardedBinary.getVal2(inst)};
589 break;
590 case InstructionFormat.Move_format:
591 ops = new Operand[]{Move.getVal(inst)};
592 break;
593 case InstructionFormat.NullCheck_format:
594 ops = new Operand[]{NullCheck.getRef(inst)};
595 break;
596 case InstructionFormat.ZeroCheck_format:
597 ops = new Operand[]{ZeroCheck.getValue(inst)};
598 break;
599 case InstructionFormat.BoundsCheck_format:
600 ops = new Operand[]{BoundsCheck.getRef(inst), BoundsCheck.getIndex(inst)};
601 break;
602 case InstructionFormat.TrapIf_format:
603 ops = new Operand[]{TrapIf.getVal1(inst), TrapIf.getVal2(inst), TrapIf.getTCode(inst)};
604 break;
605 case InstructionFormat.TypeCheck_format:
606 ops = new Operand[]{TypeCheck.getRef(inst), TypeCheck.getType(inst)};
607 break;
608 case InstructionFormat.InstanceOf_format:
609 ops = new Operand[]{InstanceOf.getRef(inst), InstanceOf.getType(inst)};
610 break;
611 case InstructionFormat.Call_format:
612 int numParams = Call.getNumberOfParams(inst);
613 ops = new Operand[numParams+2];
614 ops[0] = Call.getAddress(inst);
615 ops[1] = Call.getMethod(inst);
616 for (int i=0; i < numParams; i++) {
617 ops[i+2] = Call.getParam(inst, i);
618 }
619 break;
620 default:
621 throw new OptimizingCompilerException("Unsupported type " + inst);
622 }
623
624 AvailableExpression ae = new AvailableExpression(inst, opr, ops, location, null);
625 cache.add(ae);
626 }
627
628 /**
629 * Eliminate all AE tuples that contain a given operand
630 *
631 * @param op the operand in question
632 */
633 private void eliminate(RegisterOperand op) {
634 int i = 0;
635 loop_over_expressions:
636 while (i < cache.size()) {
637 AvailableExpression ae = cache.get(i);
638 if (ae.ops != null) {
639 for (Operand opx : ae.ops) {
640 if (opx instanceof RegisterOperand && ((RegisterOperand) opx).getRegister() == op.getRegister()) {
641 cache.remove(i);
642 continue loop_over_expressions; // don't increment i, since we removed
643 }
644 }
645 }
646 i++;
647 }
648 }
649
650 /**
651 * Eliminate all AE tuples that are killed by a given instruction
652 *
653 * @param s the store instruction
654 */
655 public void eliminate(Instruction s) {
656 int i = 0;
657 // first kill all registers that this instruction defs
658 for (Enumeration<Operand> defs = s.getDefs(); defs.hasMoreElements();) {
659 // first KILL any registers this instruction DEFS
660 Operand def = defs.nextElement();
661 if (def instanceof RegisterOperand) {
662 eliminate((RegisterOperand) def);
663 }
664 }
665 if (doMemory) {
666 // eliminate all memory locations killed by stores
667 if (LocalCSE.isStoreInstruction(s) || (options.READS_KILL && LocalCSE.isLoadInstruction(s))) {
668 // sLocation holds the location killed by this instruction
669 LocationOperand sLocation = LocationCarrier.getLocation(s);
670 // walk through the cache and invalidate any killed locations
671 while (i < cache.size()) {
672 AvailableExpression ae = cache.get(i);
673 if (ae.inst != s) { // a store instruction doesn't kill itself
674 boolean killIt = false;
675 if (ae.isLoadOrStore()) {
676 if ((sLocation == null) && (ae.location == null)) {
677 // !TODO: is this too conservative??
678 killIt = true;
679 } else if ((sLocation != null) && (ae.location != null)) {
680 killIt = LocationOperand.mayBeAliased(sLocation, ae.location);
681 }
682 }
683 if (killIt) {
684 cache.remove(i);
685 continue; // don't increment i, since we removed
686 }
687 }
688 i++;
689 }
690 }
691 }
692 }
693
694 /**
695 * Eliminate all AE tuples that cache ANY memory location.
696 */
697 public void invalidateAllLoads() {
698 if (!doMemory) return;
699 int i = 0;
700 while (i < cache.size()) {
701 AvailableExpression ae = cache.get(i);
702 if (ae.isLoadOrStore()) {
703 cache.remove(i);
704 continue; // don't increment i, since we removed
705 }
706 i++;
707 }
708 }
709 }
710
711 /**
712 * A tuple to record an Available Expression
713 */
714 private static final class AvailableExpression {
715 /**
716 * the instruction which makes this expression available
717 */
718 final Instruction inst;
719 /**
720 * the operator of the expression
721 */
722 final Operator opr;
723 /**
724 * operands
725 */
726 final Operand[] ops;
727 /**
728 * location operand for memory (load/store) expressions
729 */
730 final LocationOperand location;
731 /**
732 * temporary register holding the result of the available
733 * expression
734 */
735 Register tmp;
736
737 /**
738 * @param i the instruction which makes this expression available
739 * @param op the operator of the expression
740 * @param ops the operands
741 * @param loc location operand for memory (load/store) expressions
742 * @param t temporary register holding the result of the available
743 * expression
744 */
745 AvailableExpression(Instruction i, Operator op, Operand[] ops,
746 LocationOperand loc, Register t) {
747 this.inst = i;
748 this.opr = op;
749 this.ops = ops;
750 this.location = loc;
751 this.tmp = t;
752 }
753
754 /**
755 * Two AEs are "equal" iff
756 * <ul>
757 * <li> for unary, binary and ternary expressions:
758 * the operator and the operands match
759 * <li> for loads and stores: if the 2 operands and the location match
760 * </ul>
761 */
762 @Override
763 public boolean equals(Object o) {
764 if (!(o instanceof AvailableExpression)) {
765 return false;
766 }
767 AvailableExpression ae = (AvailableExpression) o;
768 if (isLoadOrStore()) {
769 if (!ae.isLoadOrStore()) {
770 return false;
771 }
772 boolean result = LocationOperand.mayBeAliased(location, ae.location);
773 if (ops == null || ae.ops == null){
774 return result && ops == ae.ops;
775 }
776 result = result && ops[0].similar(ae.ops[0]);
777 if (ops.length > 1) {
778 result = result && ops[1].similar(ae.ops[1]);
779 } else {
780 /* ops[1] isn't present, so ae.ops[1] must also not be present */
781 if (ae.ops.length > 1) {
782 return false;
783 }
784 }
785 return result;
786 } else if (isBoundsCheck()) {
787 // Augment equality with BC(ref,C1) ==> BC(ref,C2)
788 // when C1>0, C2>=0, and C1>C2
789 if (!opr.equals(ae.opr)) {
790 return false;
791 }
792 if (!ops[0].similar(ae.ops[0])) {
793 return false;
794 }
795 if (ops[1].similar(ae.ops[1])) {
796 return true;
797 }
798 if (ops[1] instanceof IntConstantOperand && ae.ops[1] instanceof IntConstantOperand) {
799 int C1 = ((IntConstantOperand) ops[1]).value;
800 int C2 = ((IntConstantOperand) ae.ops[1]).value;
801 return C1 > 0 && C2 >= 0 && C1 > C2;
802 } else {
803 return false;
804 }
805 } else {
806 if (!opr.equals(ae.opr)) {
807 return false;
808 }
809 if (ops.length != ae.ops.length) {
810 return false;
811 } else {
812 if (ops.length == 2) {
813 return (ops[0].similar(ae.ops[0]) && ops[1].similar(ae.ops[1])) ||
814 (isCommutative() && ops[0].similar(ae.ops[1]) && ops[1].similar(ae.ops[0]));
815 } else {
816 for (int i=0; i < ops.length; i++) {
817 if (!ops[i].similar(ae.ops[i])) {
818 return false;
819 }
820 }
821 return true;
822 }
823 }
824 }
825 }
826 /**
827 * Unused hashcode method
828 */
829 @Override
830 public int hashCode() {
831 return opr.hashCode();
832 }
833
834 /**
835 * Does this expression represent the result of a load or store?
836 */
837 public boolean isLoadOrStore() {
838 return GetField.conforms(opr) || GetStatic.conforms(opr) || PutField.conforms(opr) || PutStatic.conforms(opr);
839 }
840
841 /**
842 * Does this expression represent the result of a load?
843 */
844 public boolean isLoad() {
845 return GetField.conforms(opr) || GetStatic.conforms(opr);
846 }
847
848 /**
849 * Does this expression represent the result of a store?
850 */
851 public boolean isStore() {
852 return PutField.conforms(opr) || PutStatic.conforms(opr);
853 }
854
855 /**
856 * Does this expression represent the result of a bounds check?
857 */
858 private boolean isBoundsCheck() {
859 return BoundsCheck.conforms(opr) || (TrapIf.conforms(opr) && ((TrapCodeOperand) ops[2]).isArrayBounds());
860 }
861
862 /**
863 * Is this expression commutative?
864 */
865 private boolean isCommutative() {
866 return opr.isCommutative();
867 }
868 }
869 }