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