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.*;
016
017 import java.lang.reflect.Constructor;
018 import java.util.Enumeration;
019 import java.util.HashSet;
020 import java.util.Iterator;
021
022 import org.jikesrvm.VM;
023 import org.jikesrvm.compilers.opt.DefUse;
024 import org.jikesrvm.compilers.opt.OptOptions;
025 import org.jikesrvm.compilers.opt.controlflow.DominatorInfo;
026 import org.jikesrvm.compilers.opt.controlflow.DominatorTree;
027 import org.jikesrvm.compilers.opt.controlflow.Dominators;
028 import org.jikesrvm.compilers.opt.controlflow.DominatorsPhase;
029 import org.jikesrvm.compilers.opt.driver.CompilerPhase;
030 import org.jikesrvm.compilers.opt.ir.AStore;
031 import org.jikesrvm.compilers.opt.ir.BBend;
032 import org.jikesrvm.compilers.opt.ir.BasicBlock;
033 import org.jikesrvm.compilers.opt.ir.ExceptionHandlerBasicBlock;
034 import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
035 import org.jikesrvm.compilers.opt.ir.IR;
036 import org.jikesrvm.compilers.opt.ir.Instruction;
037 import org.jikesrvm.compilers.opt.ir.Label;
038 import org.jikesrvm.compilers.opt.ir.LocationCarrier;
039 import org.jikesrvm.compilers.opt.ir.Operator;
040 import org.jikesrvm.compilers.opt.ir.Phi;
041 import org.jikesrvm.compilers.opt.ir.PutField;
042 import org.jikesrvm.compilers.opt.ir.PutStatic;
043 import org.jikesrvm.compilers.opt.ir.Register;
044 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
045 import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
046 import org.jikesrvm.compilers.opt.ir.operand.HeapOperand;
047 import org.jikesrvm.compilers.opt.ir.operand.LocationOperand;
048 import org.jikesrvm.compilers.opt.ir.operand.Operand;
049 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
050 import org.jikesrvm.compilers.opt.liveness.LiveAnalysis;
051 import org.jikesrvm.compilers.opt.util.Queue;
052
053 /**
054 * This class does loop invariant code movement. It is a subphase of {@link GCP} (global code placement).
055 */
056 public class LICM extends CompilerPhase {
057 /** Generate debug output? */
058 private static final boolean DEBUG = false;
059 /** Generate verbose debug output? */
060 private static boolean VERBOSE = false;
061
062 /**
063 * Constructor for this compiler phase
064 */
065 private static final Constructor<CompilerPhase> constructor = getCompilerPhaseConstructor(LICM.class);
066
067 /**
068 * Get a constructor object for this compiler phase
069 * @return compiler phase constructor
070 */
071 @Override
072 public Constructor<CompilerPhase> getClassConstructor() {
073 return constructor;
074 }
075
076 /**
077 * Execute loop invariant code motion on the given IR.
078 */
079 @Override
080 public void perform(IR ir) {
081 this.ir = ir;
082
083 if (DEBUG && ir.hasReachableExceptionHandlers()) {
084 VM.sysWrite("] " + ir.method + "\n");
085 (new LiveAnalysis(false, false, true, false)).perform(ir);
086 Enumeration<BasicBlock> e = ir.getBasicBlocks();
087 while (e.hasMoreElements()) {
088 BasicBlock b = e.nextElement();
089 if (b instanceof ExceptionHandlerBasicBlock) {
090 VM.sysWrite("] " + b + ": " + ((ExceptionHandlerBasicBlock) b).getLiveSet() + "\n");
091 }
092 }
093 }
094
095 if (ir.hasReachableExceptionHandlers() || GCP.tooBig(ir)) {
096 resetLandingPads();
097 return;
098 }
099
100 VERBOSE = ir.options.DEBUG_GCP;
101
102 if (VERBOSE && ir.options.hasMETHOD_TO_PRINT()) {
103 VERBOSE = ir.options.fuzzyMatchMETHOD_TO_PRINT(ir.method.toString());
104 if (!VERBOSE) {
105 resetLandingPads();
106 return;
107 }
108 }
109
110 if (VERBOSE) VM.sysWrite("] " + ir.method + "\n");
111 initialize(ir);
112 if (VERBOSE) SSA.printInstructions(ir);
113
114 Instruction inst = ir.firstInstructionInCodeOrder();
115 while (inst != null) {
116 Instruction next = inst.nextInstructionInCodeOrder();
117 if (DEBUG) System.out.println("scheduleEarly: " + inst);
118 scheduleEarly(inst);
119 inst = next;
120 }
121
122 inst = ir.lastInstructionInCodeOrder();
123 while (inst != null) {
124 Instruction next = inst.prevInstructionInCodeOrder();
125 scheduleLate(inst);
126 inst = next;
127 }
128 resetLandingPads();
129 if (DEBUG) SSA.printInstructions(ir);
130 ir.actualSSAOptions.setScalarValid(false);
131 }
132
133 /**
134 * Returns the name of the phase
135 */
136 @Override
137 public String getName() {
138 return "LICM";
139 }
140
141 /**
142 * @return <code>true</code> if SSA-based global code placement is being
143 * performed
144 */
145 @Override
146 public boolean shouldPerform(OptOptions options) {
147 return options.SSA_GCP;
148 }
149
150 //------------------------- Implementation -------------------------
151
152 /**
153 * Is it save to move the given instruction, depending on we are
154 * in heapSSA form or not?
155 * @param inst
156 * @param ir
157 */
158 public static boolean shouldMove(Instruction inst, IR ir) {
159 if ((inst.isAllocation()) || inst.isDynamicLinkingPoint() || inst.operator.opcode >= ARCH_INDEPENDENT_END_opcode) {
160 return false;
161 }
162
163 if (ir.IRStage != IR.HIR &&
164 ((inst.isPEI()) || inst.isThrow() || inst.isImplicitLoad() || inst.isImplicitStore())) {
165 return false;
166 }
167
168 switch (inst.operator.opcode) {
169 case INT_MOVE_opcode:
170 case LONG_MOVE_opcode:
171 case INT_COND_MOVE_opcode:
172 case LONG_COND_MOVE_opcode:
173 case FLOAT_COND_MOVE_opcode:
174 case DOUBLE_COND_MOVE_opcode:
175 case REF_COND_MOVE_opcode:
176 case PUTSTATIC_opcode:
177 case PUTFIELD_opcode:
178 case GETSTATIC_opcode:
179 case GETFIELD_opcode:
180 case INT_ALOAD_opcode:
181 case LONG_ALOAD_opcode:
182 case FLOAT_ALOAD_opcode:
183 case DOUBLE_ALOAD_opcode:
184 case REF_ALOAD_opcode:
185 case BYTE_ALOAD_opcode:
186 case UBYTE_ALOAD_opcode:
187 case SHORT_ALOAD_opcode:
188 case USHORT_ALOAD_opcode:
189 case INT_ASTORE_opcode:
190 case LONG_ASTORE_opcode:
191 case FLOAT_ASTORE_opcode:
192 case DOUBLE_ASTORE_opcode:
193 case REF_ASTORE_opcode:
194 case BYTE_ASTORE_opcode:
195 case SHORT_ASTORE_opcode:
196 case CHECKCAST_opcode:
197 case CHECKCAST_NOTNULL_opcode:
198 case CHECKCAST_UNRESOLVED_opcode:
199 case MUST_IMPLEMENT_INTERFACE_opcode:
200 case INSTANCEOF_opcode:
201 case INSTANCEOF_NOTNULL_opcode:
202 case INSTANCEOF_UNRESOLVED_opcode:
203 case PI_opcode:
204 case FLOAT_MOVE_opcode:
205 case DOUBLE_MOVE_opcode:
206 case REF_MOVE_opcode:
207 case GUARD_MOVE_opcode:
208 case GUARD_COMBINE_opcode:
209 case TRAP_IF_opcode:
210 case REF_ADD_opcode:
211 case INT_ADD_opcode:
212 case LONG_ADD_opcode:
213 case FLOAT_ADD_opcode:
214 case DOUBLE_ADD_opcode:
215 case REF_SUB_opcode:
216 case INT_SUB_opcode:
217 case LONG_SUB_opcode:
218 case FLOAT_SUB_opcode:
219 case DOUBLE_SUB_opcode:
220 case INT_MUL_opcode:
221 case LONG_MUL_opcode:
222 case FLOAT_MUL_opcode:
223 case DOUBLE_MUL_opcode:
224 case INT_DIV_opcode:
225 case LONG_DIV_opcode:
226 case FLOAT_DIV_opcode:
227 case DOUBLE_DIV_opcode:
228 case INT_REM_opcode:
229 case LONG_REM_opcode:
230 case FLOAT_REM_opcode:
231 case DOUBLE_REM_opcode:
232 case INT_NEG_opcode:
233 case LONG_NEG_opcode:
234 case FLOAT_NEG_opcode:
235 case DOUBLE_NEG_opcode:
236 case REF_SHL_opcode:
237 case INT_SHL_opcode:
238 case LONG_SHL_opcode:
239 case REF_SHR_opcode:
240 case INT_SHR_opcode:
241 case LONG_SHR_opcode:
242 case REF_USHR_opcode:
243 case INT_USHR_opcode:
244 case LONG_USHR_opcode:
245 case REF_AND_opcode:
246 case INT_AND_opcode:
247 case LONG_AND_opcode:
248 case REF_OR_opcode:
249 case INT_OR_opcode:
250 case LONG_OR_opcode:
251 case REF_XOR_opcode:
252 case INT_XOR_opcode:
253 case REF_NOT_opcode:
254 case INT_NOT_opcode:
255 case LONG_NOT_opcode:
256 case LONG_XOR_opcode:
257 case INT_2LONG_opcode:
258 case INT_2FLOAT_opcode:
259 case INT_2DOUBLE_opcode:
260 case INT_2ADDRSigExt_opcode:
261 case INT_2ADDRZerExt_opcode:
262 case LONG_2ADDR_opcode:
263 case ADDR_2INT_opcode:
264 case ADDR_2LONG_opcode:
265 case LONG_2INT_opcode:
266 case LONG_2FLOAT_opcode:
267 case LONG_2DOUBLE_opcode:
268 case FLOAT_2INT_opcode:
269 case FLOAT_2LONG_opcode:
270 case FLOAT_2DOUBLE_opcode:
271 case DOUBLE_2INT_opcode:
272 case DOUBLE_2LONG_opcode:
273 case DOUBLE_2FLOAT_opcode:
274 case INT_2BYTE_opcode:
275 case INT_2USHORT_opcode:
276 case INT_2SHORT_opcode:
277 case LONG_CMP_opcode:
278 case FLOAT_CMPL_opcode:
279 case FLOAT_CMPG_opcode:
280 case DOUBLE_CMPL_opcode:
281 case DOUBLE_CMPG_opcode:
282 case NULL_CHECK_opcode:
283 case BOUNDS_CHECK_opcode:
284 case INT_ZERO_CHECK_opcode:
285 case LONG_ZERO_CHECK_opcode:
286 case OBJARRAY_STORE_CHECK_opcode:
287 case OBJARRAY_STORE_CHECK_NOTNULL_opcode:
288 case BOOLEAN_NOT_opcode:
289 case BOOLEAN_CMP_INT_opcode:
290 case BOOLEAN_CMP_ADDR_opcode:
291 case FLOAT_AS_INT_BITS_opcode:
292 case INT_BITS_AS_FLOAT_opcode:
293 case DOUBLE_AS_LONG_BITS_opcode:
294 case LONG_BITS_AS_DOUBLE_opcode:
295 case ARRAYLENGTH_opcode:
296 case GET_OBJ_TIB_opcode:
297 case GET_CLASS_TIB_opcode:
298 case GET_TYPE_FROM_TIB_opcode:
299 case GET_SUPERCLASS_IDS_FROM_TIB_opcode:
300 case GET_DOES_IMPLEMENT_FROM_TIB_opcode:
301 case GET_ARRAY_ELEMENT_TIB_FROM_TIB_opcode:
302 return !(GCP.usesOrDefsPhysicalRegisterOrAddressType(inst));
303 }
304 return false;
305 }
306
307 /**
308 * Schedule this instruction as early as possible
309 * @param inst
310 */
311 private Instruction scheduleEarly(Instruction inst) {
312 Instruction _earlyPos;
313
314 if (getState(inst) >= early) return getEarlyPos(inst);
315
316 setState(inst, early);
317 setEarlyPos(inst, inst);
318
319 // already on outer level?
320 //if (ir.HIRInfo.LoopStructureTree.getLoopNestDepth(getBlock(inst)) == 0)
321 // return inst;
322
323 if (ir.options.FREQ_FOCUS_EFFORT && getOrigBlock(inst).getInfrequent()) {
324 return inst;
325 }
326
327 // explicitly INCLUDE instructions
328 if (!shouldMove(inst, ir)) {
329 return inst;
330 }
331 // dependencies via scalar operands
332 _earlyPos = scheduleScalarDefsEarly(inst.getUses(), ir.firstInstructionInCodeOrder(), inst);
333 if (VM.VerifyAssertions) VM._assert(_earlyPos != null);
334
335 // memory dependencies
336 if (ir.IRStage == IR.HIR) {
337 _earlyPos = scheduleHeapDefsEarly(ssad.getHeapUses(inst), _earlyPos, inst);
338 if (VM.VerifyAssertions) VM._assert(_earlyPos != null);
339 }
340
341 /* don't put memory stores or PEIs on speculative path */
342 if ((inst.isPEI() && !ir.options.SSA_LICM_IGNORE_PEI) || inst.isImplicitStore()) {
343 while (!postDominates(getBlock(inst), getBlock(_earlyPos))) {
344 _earlyPos = dominanceSuccessor(_earlyPos, inst);
345 }
346 }
347
348 setEarlyPos(inst, _earlyPos);
349
350 if (DEBUG && getBlock(_earlyPos) != getBlock(inst)) {
351 VM.sysWrite("new earlyBlock: " + getBlock(_earlyPos) + " for " + getBlock(inst) + ": " + inst + "\n");
352 }
353
354 setBlock(inst, getBlock(_earlyPos));
355 return _earlyPos;
356 }
357
358 /**
359 * Schedule as late as possible.
360 * @param inst
361 */
362 BasicBlock scheduleLate(Instruction inst) {
363 if (DEBUG) VM.sysWrite("Schedule Late: " + inst + "\n");
364
365 BasicBlock lateBlock = null;
366 int _state = getState(inst);
367 if (_state == late || _state == done) return getBlock(inst);
368
369 setState(inst, late);
370
371 if (ir.options.FREQ_FOCUS_EFFORT) {
372 BasicBlock _origBlock = getOrigBlock(inst);
373 if (_origBlock.getInfrequent()) {
374 return _origBlock;
375 }
376 }
377
378 // explicitly INCLUDE instructions
379 if (!shouldMove(inst, ir)) {
380 return getOrigBlock(inst);
381 }
382
383 // dependencies via scalar operands
384 lateBlock = scheduleScalarUsesLate(inst, lateBlock);
385 if (DEBUG) VM.sysWrite("lateBlock1: " + lateBlock + " for " + inst + "\n");
386
387 // dependencies via heap operands
388 if (ir.IRStage == IR.HIR) {
389 lateBlock = scheduleHeapUsesLate(inst, lateBlock);
390 if (DEBUG) VM.sysWrite("lateBlock2: " + lateBlock + " for " + inst + "\n");
391 }
392
393 // if there are no uses, this instruction is dead.
394 if (lateBlock == null) {
395 if (VERBOSE) VM.sysWrite("deleting " + inst + "\n");
396 inst.remove();
397 } else {
398 if (DEBUG && lateBlock != getOrigBlock(inst)) {
399 VM.sysWrite("new lateBlock: " + lateBlock + " for " + getOrigBlock(inst) + ": " + inst + "\n");
400 }
401
402 BasicBlock to = upto(getEarlyPos(inst), lateBlock, inst);
403 if (to == null) {
404 lateBlock = getOrigBlock(inst);
405 } else {
406 if (VM.VerifyAssertions) VM._assert(getState(inst) != done);
407 lateBlock = to;
408 if (getOrigBlock(inst) != to) move(inst, to);
409 }
410 }
411 setState(inst, done);
412 setBlock(inst, lateBlock);
413 return lateBlock;
414 }
415
416 /**
417 * return `a's successor on the path from `a' to `b' in the dominator
418 * tree. `a' must dominate `b' and `a' and `b' must belong to
419 * different blocks.
420 */
421 private Instruction dominanceSuccessor(Instruction a, Instruction b) {
422 BasicBlock aBlock = getBlock(a);
423 BasicBlock bBlock = getBlock(b);
424
425 if (VM.VerifyAssertions) {
426 VM._assert(aBlock != bBlock && dominator.dominates(aBlock, bBlock));
427 }
428
429 BasicBlock last = null;
430
431 while (bBlock != aBlock) {
432 last = bBlock;
433 bBlock = dominator.getParent(bBlock);
434 }
435 return last.firstInstruction();
436 }
437
438 /**
439 * compare a and b according to their depth in the dominator tree
440 * and return the one with the greatest depth.
441 */
442 private Instruction maxDominatorDepth(Instruction a, Instruction b) {
443 BasicBlock aBlock = getBlock(a);
444 BasicBlock bBlock = getBlock(b);
445 int aDomDepth = dominator.depth(aBlock);
446 int bDomDepth = dominator.depth(bBlock);
447
448 if (aDomDepth > bDomDepth) return a;
449 if (aDomDepth < bDomDepth) return b;
450
451 if (VM.VerifyAssertions) VM._assert(aBlock == bBlock);
452
453 // if an instruction depends on a branch, it can not be placed in
454 // this block. Make sure we record this fact. We use this
455 // information in upto()
456 return a.isBranch() ? a : b;
457 }
458
459 private BasicBlock commonDominator(BasicBlock a, BasicBlock b) {
460 //VM.sysWrite ("CD: "+a+", "+b);
461 if (a == null) return b;
462 if (b == null) return a;
463
464 while (a != b) {
465 int aDomDepth = dominator.depth(a);
466 int bDomDepth = dominator.depth(b);
467 if (aDomDepth >= bDomDepth) a = dominator.getParent(a);
468 if (bDomDepth >= aDomDepth) b = dominator.getParent(b);
469 }
470 //VM.sysWrite (" = "+a+"\n");
471 return a;
472 }
473
474 /**
475 * Schedule me as early as possible,
476 * but behind the definitions in e and behind earlyPos
477 */
478 private Instruction scheduleScalarDefsEarly(Enumeration<Operand> e, Instruction earlyPos,
479 Instruction inst) {
480 while (e.hasMoreElements()) {
481 Operand op = e.nextElement();
482 Instruction def = definingInstruction(op);
483
484 scheduleEarly(def);
485
486 if (def.isBranch()) def = dominanceSuccessor(def, inst);
487
488 earlyPos = maxDominatorDepth(def, earlyPos);
489 }
490 return earlyPos;
491 }
492
493 /**
494 * Schedule me as early as possible,
495 * but behind the definitions of op[i] and behind earlyPos
496 */
497 Instruction scheduleHeapDefsEarly(HeapOperand<?>[] op, Instruction earlyPos, Instruction me) {
498 if (op == null) return earlyPos;
499
500 for (HeapOperand<?> anOp : op) {
501 Instruction def = definingInstruction(anOp);
502
503 // if (me.isImplicitLoad() || me.isImplicitStore())
504 // def = _getRealDef(def, me)
505 // ;
506 // else if (me.isPEI())
507 // def = _getRealExceptionDef(def)
508 // ;
509
510 if (VM.VerifyAssertions) VM._assert(def != null);
511 earlyPos = maxDominatorDepth(scheduleEarly(def), earlyPos);
512 }
513 return earlyPos;
514 }
515
516 BasicBlock useBlock(Instruction use, Operand op) {
517 //VM.sysWrite ("UseBlock: "+use+"\n");
518 BasicBlock res = scheduleLate(use);
519 if (res != null && Phi.conforms(use)) {
520 int i;
521 for (i = Phi.getNumberOfValues(use) - 1; i >= 0; --i) {
522 if (Phi.getValue(use, i) == op) {
523 res = Phi.getPred(use, i).block;
524 break;
525 }
526 }
527 if (VM.VerifyAssertions) VM._assert(i >= 0);
528 }
529 return res;
530 }
531
532 /**
533 * Schedule me as late as possible,
534 * but in front of my uses and before latePos
535 */
536 private BasicBlock scheduleScalarUsesLate(Instruction inst, BasicBlock lateBlock) {
537 Operand resOp = getResult(inst);
538
539 if (resOp == null || !(resOp instanceof RegisterOperand)) {
540 return lateBlock;
541 }
542
543 Register res = ((RegisterOperand) resOp).getRegister();
544 Enumeration<RegisterOperand> e = DefUse.uses(res);
545
546 while (e.hasMoreElements()) {
547 Operand op = e.nextElement();
548 Instruction use = op.instruction;
549 BasicBlock _block = useBlock(use, op);
550 lateBlock = commonDominator(_block, lateBlock);
551 }
552 return lateBlock;
553 }
554
555 /**
556 * Schedule me as early as possible,
557 * but behind the definitions of op[i] and behind earlyPos
558 */
559 BasicBlock scheduleHeapUsesLate(Instruction inst, BasicBlock lateBlock) {
560 //VM.sysWrite (" scheduleHeapUsesLate\n");
561 Operand[] defs = ssad.getHeapDefs(inst);
562 if (defs == null) return lateBlock;
563
564 //VM.sysWrite (" defs: "+defs.length+"\n");
565 for (Operand def : defs) {
566 @SuppressWarnings("unchecked") // Cast to generic HeapOperand
567 HeapOperand<Object> dhop = (HeapOperand) def;
568 HeapVariable<Object> H = dhop.value;
569 if (DEBUG) VM.sysWrite("H: " + H + "\n");
570 Iterator<HeapOperand<Object>> it = ssad.iterateHeapUses(H);
571 //VM.sysWrite (" H: "+H+" ("+ssad.getNumberOfUses (H)+")\n");
572 while (it.hasNext()) {
573 HeapOperand<Object> uhop = it.next();
574 //VM.sysWrite (" uhop: "+uhop+"\n");
575 Instruction use = uhop.instruction;
576 //VM.sysWrite ("use: "+use+"\n");
577 BasicBlock _block = useBlock(use, uhop);
578 lateBlock = commonDominator(_block, lateBlock);
579 }
580 }
581 return lateBlock;
582 }
583
584 /**
585 * Return the instruction that defines the operand.
586 * @param op
587 */
588 Instruction definingInstruction(Operand op) {
589 if (op instanceof HeapOperand) {
590 @SuppressWarnings("unchecked") // Cast to generic HeapOperand
591 HeapOperand<Object> hop = (HeapOperand) op;
592 HeapVariable<Object> H = hop.value;
593 HeapOperand<Object> defiOp = ssad.getUniqueDef(H);
594 // Variable may be defined by caller, so depends on method entry
595 if (defiOp == null || defiOp.instruction == null) {
596 return ir.firstInstructionInCodeOrder();
597 } else {
598 //VM.sysWrite ("def of "+op+" is "+defiOp.instruction+"\n");
599 return defiOp.instruction;
600 }
601 } else if (op instanceof RegisterOperand) {
602 Register reg = ((RegisterOperand) op).getRegister();
603 Enumeration<RegisterOperand> defs = DefUse.defs(reg);
604 if (!defs.hasMoreElements()) { // params have no def
605 return ir.firstInstructionInCodeOrder();
606 } else {
607 Instruction def = defs.nextElement().instruction;
608 // we are in SSA, so there is at most one definition.
609 if (VM.VerifyAssertions) VM._assert(!defs.hasMoreElements());
610 //if (defs.hasMoreElements()) {
611 // VM.sysWrite("GCP: multiple defs: " + reg + "\n");
612 // return null;
613 //}
614 return def;
615 }
616 } else { // some constant
617 return ir.firstInstructionInCodeOrder();
618 }
619 }
620
621 /**
622 * Get the result operand of the instruction
623 * @param inst
624 */
625 Operand getResult(Instruction inst) {
626 if (ResultCarrier.conforms(inst)) {
627 return ResultCarrier.getResult(inst);
628 }
629 if (GuardResultCarrier.conforms(inst)) {
630 return GuardResultCarrier.getGuardResult(inst);
631 }
632 if (Phi.conforms(inst)) {
633 return Phi.getResult(inst);
634 }
635 return null;
636 }
637
638 /**
639 * Visit the blocks between the late and the early position along
640 * their path in the dominator tree.
641 * Return the block with the smallest execution costs.
642 */
643 BasicBlock upto(Instruction earlyPos, BasicBlock lateBlock, Instruction inst) {
644
645 BasicBlock _origBlock = getOrigBlock(inst);
646 BasicBlock actBlock = lateBlock;
647 BasicBlock bestBlock = lateBlock;
648 BasicBlock earlyBlock = getBlock(earlyPos);
649
650 if (VM.VerifyAssertions) {
651 if (!dominator.dominates(earlyBlock.getNumber(), _origBlock.getNumber()) ||
652 !dominator.dominates(earlyBlock.getNumber(), lateBlock.getNumber())) {
653 SSA.printInstructions(ir);
654 VM.sysWrite("> " +
655 earlyBlock.getNumber() +
656 ", " +
657 _origBlock.getNumber() +
658 ", " +
659 lateBlock.getNumber() +
660 "\n");
661 VM.sysWrite("" + inst + "\n");
662 }
663 VM._assert(dominator.dominates(earlyBlock.getNumber(), _origBlock.getNumber()));
664 VM._assert(dominator.dominates(earlyBlock.getNumber(), lateBlock.getNumber()));
665 }
666 for (; ;) {
667 /* is the actual block better (less frequent)
668 than the so far best block? */
669 if (frequency(actBlock) < frequency(bestBlock)) {
670 if (DEBUG) {
671 VM.sysWrite("going from " + frequency(_origBlock) + " to " + frequency(actBlock) + "\n");
672 }
673 bestBlock = actBlock;
674 }
675 /* all candidates checked? */
676 if (actBlock == earlyBlock) {
677 break;
678 }
679
680 /* walk up the dominator tree for next candidate*/
681 actBlock = dominator.getParent(actBlock);
682 }
683 if (bestBlock == _origBlock) return null;
684 if (DEBUG) VM.sysWrite("best Block: " + bestBlock + "\n");
685 return bestBlock;
686 }
687
688 /**
689 * How expensive is it to place an instruction in this block?
690 */
691 final float frequency(BasicBlock b) {
692 return b.getExecutionFrequency();
693 }
694
695 /**
696 * move `inst' behind `pred'
697 */
698 void move(Instruction inst, BasicBlock to) {
699
700 BasicBlock _origBlock = getOrigBlock(inst);
701 Instruction cand = null;
702
703 /* find a position within bestBlock */
704 if (dominator.dominates(_origBlock.getNumber(), to.getNumber())) {
705 // moved down, so insert in from
706 Instruction last = null;
707 Enumeration<Instruction> e = to.forwardInstrEnumerator();
708 while (e.hasMoreElements()) {
709 cand = e.nextElement();
710 if (DEBUG) VM.sysWrite(cand.toString() + "\n");
711 // skip labels, phis, and yieldpoints
712 if (!Label.conforms(cand) && !cand.isYieldPoint() && !Phi.conforms(cand)) {
713 break;
714 }
715 last = cand;
716 }
717 cand = last;
718 } else {
719 // moved up, so insert at end of block
720 Enumeration<Instruction> e = to.reverseInstrEnumerator();
721 while (e.hasMoreElements()) {
722 cand = e.nextElement();
723 if (DEBUG) VM.sysWrite(cand.toString() + "\n");
724 // skip branches and newly placed insts
725 if (!BBend.conforms(cand) && !cand.isBranch() && !relocated.contains(cand)) {
726 break;
727 }
728 }
729 if (DEBUG) VM.sysWrite("Adding to relocated: " + inst + "\n");
730 relocated.add(inst);
731 }
732
733 if (DEBUG && moved.add(inst.operator)) {
734 VM.sysWrite("m(" + (ir.IRStage == IR.LIR ? "l" : "h") + ") " + inst.operator + "\n");
735 }
736 if (VERBOSE) {
737 VM.sysWrite(ir.IRStage == IR.LIR ? "%" : "#");
738 VM.sysWrite(" moving " + inst + " from " + _origBlock + " to " + to + "\n" + "behind " + cand + "\n");
739
740 }
741 inst.remove();
742 cand.insertAfter(inst);
743 }
744
745 //------------------------------------------------------------
746 // some helper methods
747 //------------------------------------------------------------
748
749 /**
750 * does a post dominate b?
751 * @param a
752 * @param b
753 */
754 boolean postDominates(BasicBlock a, BasicBlock b) {
755 boolean res;
756 if (a == b) {
757 return true;
758 }
759 //VM.sysWrite ("does " + a + " postdominate " + b + "?: ");
760 DominatorInfo info = (DominatorInfo) b.scratchObject;
761 res = info.isDominatedBy(a);
762 //VM.sysWrite (res ? "yes\n" : "no\n");
763 return res;
764 }
765
766 /**
767 * Get the basic block of an instruction
768 * @param inst
769 */
770 BasicBlock getBlock(Instruction inst) {
771 return block[inst.scratch];
772 }
773
774 /**
775 * Set the basic block for an instruction
776 * @param inst
777 * @param b
778 */
779 void setBlock(Instruction inst, BasicBlock b) {
780 block[inst.scratch] = b;
781 }
782
783 /**
784 * Get the early position of an instruction
785 * @param inst
786 */
787 Instruction getEarlyPos(Instruction inst) {
788 return earlyPos[inst.scratch];
789 }
790
791 /**
792 * Set the early position for an instruction
793 * @param inst
794 * @param pos
795 */
796 void setEarlyPos(Instruction inst, Instruction pos) {
797 earlyPos[inst.scratch] = pos;
798 }
799
800 /**
801 * Get the block, where the instruction was originally located
802 * @param inst
803 */
804 BasicBlock getOrigBlock(Instruction inst) {
805 return origBlock[inst.scratch];
806 }
807
808 /**
809 * Set the block, where the instruction is originally located.
810 * @param inst
811 * @param b
812 */
813 void setOrigBlock(Instruction inst, BasicBlock b) {
814 origBlock[inst.scratch] = b;
815 }
816
817 /**
818 * In what state (initial, early, late, done) is this instruction
819 * @param inst
820 */
821 int getState(Instruction inst) {
822 return state[inst.scratch];
823 }
824
825 /**
826 * Set the state (initial, early, late, done) of the instruction
827 * @param inst
828 * @param s
829 */
830 void setState(Instruction inst, int s) {
831 state[inst.scratch] = s;
832 }
833
834 //------------------------------------------------------------
835 // initialization
836 //------------------------------------------------------------
837
838 /**
839 * initialize the state of the algorithm
840 */
841 void initialize(IR ir) {
842 this.ir = ir;
843
844 relocated = new HashSet<Instruction>();
845 // Note: the following unfactors the CFG
846 new DominatorsPhase(true).perform(ir);
847 Dominators.computeApproxPostdominators(ir);
848 dominator = ir.HIRInfo.dominatorTree;
849 if (DEBUG) VM.sysWrite("" + dominator.toString() + "\n");
850 int instructions = ir.numberInstructions();
851 ssad = ir.HIRInfo.dictionary;
852 DefUse.computeDU(ir);
853 ssad.recomputeArrayDU();
854 // also number implicit heap phis
855 Enumeration<BasicBlock> e = ir.getBasicBlocks();
856 while (e.hasMoreElements()) {
857 BasicBlock b = e.nextElement();
858 Iterator<Instruction> pe = ssad.getHeapPhiInstructions(b);
859 while (pe.hasNext()) {
860 Instruction inst = pe.next();
861 inst.scratch = instructions++;
862 inst.scratchObject = null;
863 }
864 }
865 state = new int[instructions];
866 origBlock = new BasicBlock[instructions];
867 block = new BasicBlock[instructions];
868 earlyPos = new Instruction[instructions];
869 e = ir.getBasicBlocks();
870 while (e.hasMoreElements()) {
871 BasicBlock b = e.nextElement();
872 Enumeration<Instruction> ie = ssad.getAllInstructions(b);
873 while (ie.hasMoreElements()) {
874 Instruction inst = ie.nextElement();
875 setBlock(inst, b);
876 setOrigBlock(inst, b);
877 setState(inst, initial);
878 }
879 }
880 if (ir.IRStage == IR.HIR) {
881 e = ir.getBasicBlocks();
882 while (e.hasMoreElements()) {
883 BasicBlock b = e.nextElement();
884
885 if (ir.options.FREQ_FOCUS_EFFORT && b.getInfrequent()) continue;
886
887 Enumeration<Instruction> ie = ssad.getAllInstructions(b);
888 while (ie.hasMoreElements()) {
889 Instruction inst = ie.nextElement();
890 while (simplify(inst, b)) ;
891 }
892 }
893 ssad.recomputeArrayDU();
894 }
895 }
896
897 //------------------------------------------------------------
898 // private state
899 //------------------------------------------------------------
900 private static final int initial = 0;
901 private static final int early = 1;
902 private static final int late = 2;
903 private static final int done = 3;
904
905 private HashSet<Instruction> relocated;
906
907 private int[] state;
908 private BasicBlock[] block;
909 private BasicBlock[] origBlock;
910 private Instruction[] earlyPos;
911 private SSADictionary ssad;
912 private DominatorTree dominator;
913 private IR ir;
914 private final HashSet<Operator> moved = DEBUG ? new HashSet<Operator>() : null;
915
916 private boolean simplify(Instruction inst, BasicBlock block) {
917 if (!Phi.conforms(inst)) return false; // no phi
918
919 //if (Phi.getNumberOfValues (inst) != 2) return false; // want exactly 2 inputs
920
921 //VM.sysWrite ("Simplify "+inst+"\n");
922
923 Operand resOp = Phi.getResult(inst);
924
925 if (!(resOp instanceof HeapOperand)) {
926 //VM.sysWrite (" no heap op result\n");
927 return false; // scalar phi
928 }
929
930 int xidx = -1;
931 Instruction x = null;
932
933 for (int i = Phi.getNumberOfValues(inst) - 1; i >= 0; --i) {
934 Instruction in = definingInstruction(Phi.getValue(inst, i));
935 if (getOrigBlock(in) != getOrigBlock(inst) && dominator.dominates(getOrigBlock(in), getOrigBlock(inst))) {
936 if (xidx != -1) return false;
937 xidx = i;
938 x = in;
939 } else if (!dominator.dominates(getOrigBlock(inst), getOrigBlock(in))) {
940 return false;
941 }
942 }
943 if (x == null) return false;
944
945 replaceUses(inst, (HeapOperand<?>) Phi.getValue(inst, xidx), Phi.getPred(inst, xidx), true);
946
947 @SuppressWarnings("unchecked") // Cast to generic HeapOperand
948 HeapOperand<Object> hop = (HeapOperand) resOp;
949 if (hop.value.isExceptionHeapType()) return false;
950
951 /* check that inside the loop, the heap variable is only used/defed
952 by simple, non-volatile loads or only by stores
953
954 if so, replace uses of inst (a memory phi) with its dominating input
955 */
956 int type = checkLoop(inst, hop, xidx, block);
957 if (type == CL_LOADS_ONLY || type == CL_STORES_ONLY || type == CL_NONE) {
958 replaceUses(inst, (HeapOperand<?>) Phi.getValue(inst, xidx), Phi.getPred(inst, xidx), false);
959 }
960 return false;
961 }
962
963 static final int CL_NONE = 0;
964 static final int CL_LOADS_ONLY = 1;
965 static final int CL_STORES_ONLY = 2;
966 static final int CL_LOADS_AND_STORES = 3;
967 static final int CL_COMPLEX = 4;
968
969 /**
970 * check that inside the loop, the heap variable is only used/defed
971 * by simple, non-volatile loads/stores<p>
972 *
973 * returns one of:
974 * CL_LOADS_ONLY, CL_STORES_ONLY, CL_LOADS_AND_STORES, CL_COMPLEX
975 */
976 @SuppressWarnings("unused")
977 // useful for debugging
978 private int _checkLoop(Instruction inst, HeapOperand<?> hop, int xidx) {
979 for (int i = Phi.getNumberOfValues(inst) - 1; i >= 0; --i) {
980 if (i == xidx) continue;
981 Instruction y = definingInstruction(Phi.getValue(inst, i));
982 while (y != inst) {
983 //VM.sysWrite (" y: "+y+"\n");
984 if (y.isImplicitStore() || y.isPEI() || !LocationCarrier.conforms(y)) {
985 return CL_COMPLEX;
986 }
987
988 // check for access to volatile field
989 LocationOperand loc = LocationCarrier.getLocation(y);
990 if (loc == null || loc.mayBeVolatile()) {
991 //VM.sysWrite (" no loc or volatile field\n");
992 return CL_COMPLEX;
993 }
994 for (HeapOperand<?> op : ssad.getHeapUses(y)) {
995 if (op.value.isExceptionHeapType()) continue;
996 if (op.getHeapType() != hop.getHeapType()) return CL_COMPLEX;
997 y = definingInstruction(op);
998 }
999 }
1000 }
1001 return CL_LOADS_ONLY;
1002 }
1003
1004 /**
1005 * check that inside the loop, the heap variable is only used/defed
1006 * by simple, non-volatile loads/stores<p>
1007 *
1008 * returns one of:
1009 * CL_LOADS_ONLY, CL_STORES_ONLY, CL_LOADS_AND_STORES, CL_COMPLEX
1010 */
1011 private int checkLoop(Instruction inst, HeapOperand<Object> hop, int xidx, BasicBlock block) {
1012 HashSet<Instruction> seen = new HashSet<Instruction>();
1013 Queue<Instruction> workList = new Queue<Instruction>();
1014 int _state = CL_NONE;
1015 int instUses = 0;
1016
1017 seen.add(inst);
1018 for (int i = Phi.getNumberOfValues(inst) - 1; i >= 0; --i) {
1019 if (i == xidx) continue;
1020 Instruction y = definingInstruction(Phi.getValue(inst, i));
1021 if (y == inst) instUses++;
1022 if (!(seen.contains(y))) {
1023 seen.add(y);
1024 workList.insert(y);
1025 }
1026 }
1027
1028 while (!(workList.isEmpty())) {
1029 Instruction y = workList.remove();
1030 if (Phi.conforms(y)) {
1031 for (int i = Phi.getNumberOfValues(y) - 1; i >= 0; --i) {
1032 Instruction z = definingInstruction(Phi.getValue(y, i));
1033 if (z == inst) instUses++;
1034 if (!(seen.contains(z))) {
1035 seen.add(z);
1036 workList.insert(z);
1037 }
1038 }
1039 } else if ((y.isPEI()) || !LocationCarrier.conforms(y) || y.operator.isAcquire() || y.operator.isRelease()) {
1040 return CL_COMPLEX;
1041 } else {
1042 // check for access to volatile field
1043 LocationOperand loc = LocationCarrier.getLocation(y);
1044 if (loc == null || loc.mayBeVolatile()) {
1045 //VM.sysWrite (" no loc or volatile field\n");
1046 return CL_COMPLEX;
1047 }
1048 if (y.isImplicitStore()) {
1049 // only accept loop-invariant stores
1050 // conservatively estimate loop-invariance by header domination
1051 if (!inVariantLocation(y, block)) return CL_COMPLEX;
1052 _state |= CL_STORES_ONLY;
1053 } else {
1054 _state |= CL_LOADS_ONLY;
1055 }
1056 for (HeapOperand<?> op : ssad.getHeapUses(y)) {
1057 if (op.value.isExceptionHeapType()) continue;
1058 if (op.getHeapType() != hop.getHeapType()) return CL_COMPLEX;
1059 y = definingInstruction(op);
1060 if (y == inst) instUses++;
1061 if (!(seen.contains(y))) {
1062 seen.add(y);
1063 workList.insert(y);
1064 }
1065 }
1066 }
1067 }
1068 if (_state == CL_STORES_ONLY && ssad.getNumberOfUses(hop.value) != instUses) {
1069 return CL_COMPLEX;
1070 }
1071
1072 return _state;
1073 }
1074
1075 private boolean inVariantLocation(Instruction inst, BasicBlock block) {
1076 if (PutStatic.conforms(inst)) return true;
1077 if (PutField.conforms(inst)) {
1078 return useDominates(PutField.getRef(inst), block);
1079 }
1080 if (AStore.conforms(inst)) {
1081 return ((useDominates(AStore.getArray(inst), block)) && useDominates(AStore.getIndex(inst), block));
1082 }
1083 if (VM.VerifyAssertions) {
1084 VM._assert(VM.NOT_REACHED, "inst does not conform to PutStatic, Putfield or AStore: " + inst);
1085 }
1086 return false;
1087 }
1088
1089 private boolean useDominates(Operand op, BasicBlock block) {
1090 if (!(op instanceof RegisterOperand)) return true;
1091 Instruction inst = definingInstruction(op);
1092 BasicBlock b = getOrigBlock(inst);
1093 return b != block && dominator.dominates(b, block);
1094 }
1095
1096 /**
1097 * In the consumers of `inst', replace uses of `inst's result
1098 * with uses of `replacement'
1099 */
1100 private boolean replaceUses(Instruction inst, HeapOperand<?> replacement,
1101 BasicBlockOperand replacementBlock, boolean onlyPEIs) {
1102 if (VM.VerifyAssertions) VM._assert(Phi.conforms(inst));
1103
1104 boolean changed = false;
1105 @SuppressWarnings("unchecked") // Cast to generic HeapOperand
1106 HeapOperand<Object> hop = (HeapOperand) Phi.getResult(inst);
1107 HeapVariable<Object> H = hop.value;
1108 Iterator<HeapOperand<Object>> it = ssad.iterateHeapUses(H);
1109 while (it.hasNext()) {
1110 hop = it.next();
1111 Instruction user = hop.instruction;
1112 if (onlyPEIs && !user.isPEI()) continue;
1113
1114 if (Phi.conforms(user)) {
1115 for (int i = 0; i < Phi.getNumberOfValues(user); i++) {
1116 if (Phi.getValue(user, i) == hop) {
1117 Phi.setValue(user, i, replacement.copy());
1118 Phi.setPred(user, i, (BasicBlockOperand) replacementBlock.copy());
1119 }
1120 }
1121 changed |= replacement.value != H;
1122 } else {
1123 HeapOperand<?>[] uses = ssad.getHeapUses(user);
1124 for (int i = uses.length - 1; i >= 0; --i) {
1125 if (uses[i].value == H) {
1126 changed |= replacement.value != H;
1127 uses[i] = replacement.copy();
1128 uses[i].setInstruction(user);
1129 }
1130 }
1131 }
1132 if (DEBUG && changed) {
1133 VM.sysWrite(" changing dependency of " + user + "\n" + "from " + H + " to " + replacement + "\n");
1134 }
1135 }
1136 if (!onlyPEIs) {
1137 for (int i = Phi.getNumberOfValues(inst) - 1; i >= 0; --i) {
1138 Phi.setValue(inst, i, replacement.copy());
1139 }
1140 }
1141 return changed;
1142 }
1143
1144 private void resetLandingPads() {
1145 Enumeration<BasicBlock> e = ir.getBasicBlocks();
1146 while (e.hasMoreElements()) e.nextElement().clearLandingPad();
1147 }
1148 }