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