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.controlflow;
014
015 import static org.jikesrvm.compilers.opt.ir.Operators.ARCH_INDEPENDENT_END_opcode;
016 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ADD_opcode;
017 import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP_opcode;
018 import static org.jikesrvm.compilers.opt.ir.Operators.INT_SUB_opcode;
019 import static org.jikesrvm.compilers.opt.ir.Operators.LABEL;
020
021 import java.util.ArrayList;
022 import java.util.Enumeration;
023
024 import org.jikesrvm.VM;
025 import org.jikesrvm.compilers.opt.DefUse;
026 import org.jikesrvm.compilers.opt.OptimizingCompilerException;
027 import org.jikesrvm.compilers.opt.ir.BasicBlock;
028 import org.jikesrvm.compilers.opt.ir.BasicBlockEnumeration;
029 import org.jikesrvm.compilers.opt.ir.Binary;
030 import org.jikesrvm.compilers.opt.ir.BoundsCheck;
031 import org.jikesrvm.compilers.opt.ir.GuardResultCarrier;
032 import org.jikesrvm.compilers.opt.ir.GuardedBinary;
033 import org.jikesrvm.compilers.opt.ir.GuardedUnary;
034 import org.jikesrvm.compilers.opt.ir.IR;
035 import org.jikesrvm.compilers.opt.ir.IREnumeration;
036 import org.jikesrvm.compilers.opt.ir.IfCmp;
037 import org.jikesrvm.compilers.opt.ir.Instruction;
038 import org.jikesrvm.compilers.opt.ir.InstructionFormat;
039 import org.jikesrvm.compilers.opt.ir.Label;
040 import org.jikesrvm.compilers.opt.ir.Move;
041 import org.jikesrvm.compilers.opt.ir.NullCheck;
042 import org.jikesrvm.compilers.opt.ir.Operator;
043 import org.jikesrvm.compilers.opt.ir.Phi;
044 import org.jikesrvm.compilers.opt.ir.RegisterOperandEnumeration;
045 import org.jikesrvm.compilers.opt.ir.ResultCarrier;
046 import org.jikesrvm.compilers.opt.ir.Unary;
047 import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
048 import org.jikesrvm.compilers.opt.ir.operand.ConditionOperand;
049 import org.jikesrvm.compilers.opt.ir.operand.ConstantOperand;
050 import org.jikesrvm.compilers.opt.ir.operand.IntConstantOperand;
051 import org.jikesrvm.compilers.opt.ir.operand.Operand;
052 import org.jikesrvm.compilers.opt.ir.operand.RegisterOperand;
053 import org.jikesrvm.compilers.opt.ssa.GCP;
054 import org.jikesrvm.compilers.opt.util.GraphNode;
055 import org.jikesrvm.util.BitVector;
056
057 /**
058 * <p>A node in the LST (Loop Structure Tree) with added information
059 * on:
060 *
061 * <ul><li>Whether this is a countable, affine or non-regular loop</li>
062 * <li>The registers being used to hold the loop iterator</li>
063 * <li>The initial loop iterator value</li>
064 * <li>The terminal loop iterator value</li>
065 * <li>The instruction that modifies the iterator</li>
066 * <li>The phi instruction that merges the redefined iterator with its original value</li>
067 * <li>The condition used to test for loop termination</li>
068 * <li>The stride operand</li>
069 * </ul>
070 *
071 * The information is only held on regular loops. The regular loop
072 * structure is:
073 *
074 * <listing>
075 * predecessor:
076 * initialLoopIterator = ...;
077 * header:
078 * phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator)
079 * ...body1...
080 * carriedLoopIterator = phiLoopIterator iteratorInstr.opcode stride;
081 * ...body2...
082 * exit:
083 * if carriedLoopIterator condition terminalIteratorValue goto header
084 * successor:
085 * </listing>
086 *
087 * While loops (and implicitly for loops) aren't handled as they can
088 * be transformed to this form by {@link CFGTransformations}.
089 *
090 * TODO:
091 * <ul><li>More complex iterator instructions (sequences rather than single instructions)</li>
092 * <li>Handle longs, floats and doubles as loop iterators</li>
093 * <li>Consideration of more loop structures</li>
094 * </ul>
095 * </p>
096 *
097 * @see LSTNode
098 */
099 public final class AnnotatedLSTNode extends LSTNode {
100 // -oO Debug information Oo-
101 /**
102 * Flag to optionally print verbose debugging messages
103 */
104 private static final boolean DEBUG = false;
105
106 // -oO Cached values for convenience Oo-
107 /**
108 * A pointer to the governing IR
109 */
110 private final IR ir;
111
112 // -oO Blocks that get set up during the recognition of the loop Oo-
113 /**
114 * The out of loop block before the header
115 */
116 public BasicBlock predecessor;
117 // N.B. the header is defined in the superclass
118 /**
119 * The in loop block that either loops or leaves the loop
120 */
121 public BasicBlock exit;
122 /**
123 * The out of loop block following the exit block
124 */
125 public BasicBlock successor;
126
127 // -oO Instructions that get set up during the recognition of the loop Oo-
128 /**
129 * The if instruction within the exit block
130 */
131 private Instruction ifCmpInstr;
132 /**
133 * The instruction that modifies the iterator
134 */
135 private Instruction iteratorInstr;
136
137 // Values that get determined during the recognition of the loop
138 /**
139 * The the initial iterator that comes into the phi node in the header
140 */
141 public Operand initialIteratorValue;
142 /**
143 * The iterator that is used to loop within the exit block
144 */
145 private Operand carriedLoopIterator;
146 /**
147 * The the phi iterator that gets modified by the stride to produce the carried iterator
148 */
149 private Operand phiLoopIterator;
150 /**
151 * The value that ends the loop
152 */
153 public Operand terminalIteratorValue;
154 /**
155 * The condition that is used to check for the end of loop
156 */
157 public ConditionOperand condition;
158 /**
159 * The stride operand to the iterator instruction
160 */
161 public Operand strideValue;
162
163 // -oO Interfaces to the rest of the compiler Oo-
164 /**
165 * Constructor
166 *
167 * @param ir The containing IR
168 * @param node The node that's being annotated
169 */
170 public AnnotatedLSTNode(IR ir, LSTNode node) {
171 // Clone information from non-annotated node
172 super(node);
173 this.ir = ir;
174
175 // Process inner loops
176 Enumeration<GraphNode> innerLoops = node.outNodes();
177 // Iterate over loops contained within this loop annotating from the inside out
178 while (innerLoops.hasMoreElements()) {
179 AnnotatedLSTNode nestedLoop = new AnnotatedLSTNode(ir, (LSTNode) innerLoops.nextElement());
180 insertOut(nestedLoop);
181 }
182 // Annotate node
183 perform();
184 }
185
186 /**
187 * Is this a countable loop of the form:
188 * <listing>
189 * predecessor:
190 * initialLoopIterator = ConstantInitialValue;
191 * header:
192 * phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator)
193 * ...body1...
194 * carriedLoopIterator = phiLoopIterator (+|-) ConstantStride;
195 * ...body2...
196 * exit:
197 * if carriedLoopIterator condition ConstantTerminalIteratorValue goto header
198 * successor:
199 * </listing>
200 * ie. lots of constant fields so we can calculate the number of
201 * loop iterations (handy for pre-scheduling).
202 *
203 * @return Whether this a countable loop or not
204 */
205 public boolean isCountableLoop() {
206 return (initialIteratorValue != null) &&
207 isConstant(initialIteratorValue) &&
208 (terminalIteratorValue != null) &&
209 isConstant(terminalIteratorValue) &&
210 (strideValue != null) &&
211 isConstant(strideValue) &&
212 (iteratorInstr != null) &&
213 ((iteratorInstr.operator.opcode == INT_ADD_opcode) || (iteratorInstr.operator.opcode == INT_SUB_opcode));
214 }
215
216 /**
217 * Is this an affine loop of the form:
218 * <listing>
219 * predecessor:
220 * initialLoopIterator = ...;
221 * header:
222 * phiLoopIterator = phi (initialLoopIterator, carriedLoopIterator)
223 * ...body1...
224 * carriedLoopIterator = phiLoopIterator (+|-) invariantStride;
225 * ...body2...
226 * exit:
227 * if carriedLoopIterator condition invariantTerminalIteratorValue goto header
228 * successor:
229 * </listing>
230 * ie. lots of constant fields so we can calculate the number of
231 * loop iterations (handy for pre-scheduling).
232 *
233 * @return Whether this an affine loop or not
234 */
235 public boolean isAffineLoop() {
236 return (initialIteratorValue != null) &&
237 isLoopInvariant(initialIteratorValue, loop, header) &&
238 (terminalIteratorValue != null) &&
239 isLoopInvariant(terminalIteratorValue, loop, header) &&
240 (strideValue != null) &&
241 isLoopInvariant(strideValue, loop, header) &&
242 (iteratorInstr != null) &&
243 ((iteratorInstr.operator.opcode == INT_ADD_opcode) || (iteratorInstr.operator.opcode == INT_SUB_opcode));
244 }
245
246 /**
247 * Is this loop a non-regular loop?
248 *
249 * @return Whether this is a non-regular loop
250 */
251 public boolean isNonRegularLoop() {
252 return !isAffineLoop();
253 }
254
255 /**
256 * Is this value modified by the loop?
257 *
258 * @return whether the value is modified
259 */
260 public boolean isInvariant(Operand op) {
261 return isLoopInvariant(op, loop, header);
262 }
263
264 /**
265 * Is this operand related to the iterator of this loop?
266 *
267 * @param op Operand to test
268 * @return whether related to iterator (initial, phi or carried)
269 */
270 public boolean isRelatedToIterator(Operand op) {
271 return isFixedDistanceFromPhiIterator(op);
272 }
273
274 /**
275 * Is this operand related to the phi iterator of this loop?
276 * @param op Operand to test
277 * @return whether related to iterator (phi)
278 */
279 public boolean isPhiLoopIterator(Operand op) {
280 return op.similar(phiLoopIterator);
281 }
282
283 /**
284 * Is this operand related to the carried iterator of this loop?
285 * @param op Operand to test
286 * @return whether related to iterator (carried)
287 */
288 public boolean isCarriedLoopIterator(Operand op) {
289 return op.similar(carriedLoopIterator);
290 }
291
292 /**
293 * Is the loop iterator monotonic?
294 */
295 public boolean isMonotonic() {
296 return isConstant(strideValue);
297 }
298
299 /**
300 * Return the stride value for monotonic loops
301 *
302 * @return the constant stride value
303 */
304 public int getMonotonicStrideValue() {
305 if (iteratorInstr.operator.opcode == INT_SUB_opcode) {
306 return -((IntConstantOperand) strideValue).value;
307 } else if (iteratorInstr.operator.opcode == INT_ADD_opcode) {
308 return ((IntConstantOperand) strideValue).value;
309 } else {
310 throw new Error("Error reading stride value");
311 }
312 }
313
314 /**
315 * Is the loop iterator a monotonic increasing value
316 */
317 public boolean isMonotonicIncreasing() {
318 if ((!isMonotonic()) ||
319 condition.isGREATER() ||
320 condition.isGREATER_EQUAL() ||
321 condition.isHIGHER() ||
322 condition.isHIGHER_EQUAL()) {
323 return false;
324 } else {
325 return getMonotonicStrideValue() > 0;
326 }
327 }
328
329 /**
330 * Is the loop iterator a monotonic decreasing value
331 */
332 public boolean isMonotonicDecreasing() {
333 if ((!isMonotonic()) ||
334 condition.isLESS() ||
335 condition.isLESS_EQUAL() ||
336 condition.isLOWER() ||
337 condition.isLOWER_EQUAL()) {
338 return false;
339 } else {
340 return getMonotonicStrideValue() < 0;
341 }
342 }
343
344 /**
345 * Does this basic block appear in the loop?
346 */
347 public boolean contains(BasicBlock block) {
348 return (block.getNumber() < loop.length()) && loop.get(block.getNumber());
349 }
350
351 // -oO Utility methods Oo-
352 /**
353 * Converts the annotated loop to a concise string
354 */
355 public String toString() {
356 String ifCmpString = "??";
357 if ((ifCmpInstr != null) && (IfCmp.conforms(ifCmpInstr))) {
358 ifCmpString = IfCmp.getCond(ifCmpInstr).toString();
359 }
360 return ("// pred: " +
361 predecessor +
362 "\n" +
363 "loop : " +
364 initialIteratorValue +
365 ";\n" +
366 "head {" +
367 header +
368 "}:\n" +
369 " " +
370 phiLoopIterator +
371 "=phi(" +
372 initialIteratorValue +
373 "," +
374 carriedLoopIterator +
375 ");\n" +
376 " " +
377 carriedLoopIterator +
378 "=" +
379 phiLoopIterator +
380 "+" +
381 strideValue +
382 ";\n" +
383 "// blocks: " +
384 loop +
385 "\n" +
386 "exit {" +
387 exit +
388 "}:\n" +
389 " if(" +
390 carriedLoopIterator +
391 " " +
392 ifCmpString +
393 " " +
394 terminalIteratorValue +
395 ")\n" +
396 " goto head;\n" +
397 "// succ: " +
398 successor +
399 "\n");
400 }
401
402 /**
403 * Dump a human readable description of the loop
404 */
405 public void dump() {
406 VM.sysWrite("********* START OF SSA LOOP DUMP in AnnotatedLSTNode FOR " + ir.method + "\n");
407 if (isNonRegularLoop()) {
408 VM.sysWrite("Non-regular");
409 } else if (isAffineLoop()) {
410 VM.sysWrite("Affine");
411 } else if (isCountableLoop()) {
412 VM.sysWrite("Countable");
413 } else {
414 VM.sysWrite("INVALID");
415 }
416 VM.sysWrite(" Loop:\n\tIteratorInstr: " +
417 iteratorInstr.toString() +
418 "\n\tIfCmpInstr:" +
419 ifCmpInstr.toString() +
420 "\n\tTerminalIteratorValue: " +
421 terminalIteratorValue.toString() +
422 "\n\tInitialIteratorValue: " +
423 initialIteratorValue.toString() +
424 "\n\tCarriedLoopIterator: " +
425 carriedLoopIterator.toString() +
426 "\n\tPhiLoopIterator: " +
427 phiLoopIterator.toString() +
428 "\n\tStrideValue: " +
429 strideValue.toString() +
430 "\n\tLoop: " +
431 getBasicBlocks().toString() +
432 " / " +
433 loop.toString() +
434 "\n");
435
436 BasicBlockEnumeration loopBlocks = getBasicBlocks();
437 // loop_over_basic_blocks:
438 while (loopBlocks.hasMoreElements()) {
439 // The current basic block
440 BasicBlock curLoopBB = loopBlocks.next();
441 dumpBlock(curLoopBB);
442 }
443 VM.sysWrite("********* END OF SSA LOOP DUMP in AnnotatedLSTNode FOR " + ir.method + "\n");
444 }
445
446 /**
447 * Dump a human readable description of a basic block within the loop
448 *
449 * @param block The basic block to dump
450 */
451 void dumpBlock(BasicBlock block) {
452 if (block == header) {
453 VM.sysWrite("Header ");
454 }
455 if (block == exit) {
456 VM.sysWrite("Exit ");
457 }
458 VM.sysWrite("Block #" + block.getNumber() + ":\n");
459 // Print the instructions
460 IREnumeration.AllInstructionsEnum instructions = new IREnumeration.AllInstructionsEnum(ir, block);
461 while (instructions.hasMoreElements()) {
462 Instruction instr = instructions.next();
463 dumpInstruction(ir, instr);
464 }
465 }
466
467 /**
468 * Dump a human readable description of an instruction within a
469 * basic block within the loop
470 *
471 * @param ir Containing IR
472 * @param instr The instruction to dump
473 */
474 static void dumpInstruction(IR ir, Instruction instr) {
475 VM.sysWrite(instructionToString(ir, instr));
476 }
477
478 /**
479 * Convert instruction to String in of AnnotatedLSTNode format
480 *
481 * @param ir Containing IR
482 * @param instr The instruction to dump
483 */
484 static String instructionToString(IR ir, Instruction instr) {
485 StringBuilder sb = new StringBuilder();
486 sb.append(instr.bcIndex).append("\t").append(instr.isPEI() ? "E" : " ").append(instr.isGCPoint() ? "G " : " ");
487 if (instr.operator == LABEL) {
488 sb.append("LABEL").append(Label.getBlock(instr).block.getNumber());
489 if (Label.getBlock(instr).block.getInfrequent()) {
490 sb.append(" (Infrequent)");
491 }
492 } else {
493 IREnumeration.AllDefsEnum defs = new IREnumeration.AllDefsEnum(ir, instr);
494 IREnumeration.AllUsesEnum uses = new IREnumeration.AllUsesEnum(ir, instr);
495 sb.append(instr.operator).append("\n\t defs: ");
496 while (defs.hasMoreElements()) {
497 sb.append(defs.next().toString());
498 if (defs.hasMoreElements()) {
499 sb.append(", ");
500 }
501 }
502 sb.append("\n\t uses: ");
503 while (uses.hasMoreElements()) {
504 sb.append(uses.next().toString());
505 if (uses.hasMoreElements()) {
506 sb.append(", ");
507 }
508 }
509 }
510 sb.append("\n");
511 return sb.toString();
512 }
513
514 /**
515 * Test whether the operand is constant
516 *
517 * @param op Operand to determine whether it's constant
518 * @return Is the operand constant
519 */
520 static boolean isConstant(Operand op) {
521 return op instanceof IntConstantOperand;
522 }
523
524 /**
525 * Is this operand a fixed distance from the phi iterator?
526 *
527 * @param op the operand to test
528 * @return whether or not it is a fixed distance
529 */
530 boolean isFixedDistanceFromPhiIterator(Operand op) {
531 if (op.similar(phiLoopIterator)) {
532 return true;
533 } else {
534 Instruction opInstr = definingInstruction(op);
535 if ((opInstr.operator.opcode == INT_ADD_opcode) || (opInstr.operator.opcode == INT_SUB_opcode)) {
536 Operand val1 = Binary.getVal1(opInstr);
537 Operand val2 = Binary.getVal2(opInstr);
538 return ((val1.isConstant() && isFixedDistanceFromPhiIterator(val2)) ||
539 (val2.isConstant() && isFixedDistanceFromPhiIterator(val1)));
540 } else {
541 return false;
542 }
543 }
544 }
545
546 /**
547 * Get fixed distance from the phi iterator
548 *
549 * @param op the operand to test
550 * @return the fixed distance
551 */
552 public int getFixedDistanceFromPhiIterator(Operand op) {
553 if (op.similar(phiLoopIterator)) {
554 return 0;
555 } else {
556 Instruction opInstr = definingInstruction(op);
557 if (opInstr.operator.opcode == INT_ADD_opcode) {
558 Operand val1 = Binary.getVal1(opInstr);
559 Operand val2 = Binary.getVal2(opInstr);
560 if (val1.isConstant()) {
561 return val1.asIntConstant().value + getFixedDistanceFromPhiIterator(val2);
562 } else {
563 VM._assert(val2.isConstant());
564 return getFixedDistanceFromPhiIterator(val1) + val2.asIntConstant().value;
565 }
566 } else if (opInstr.operator.opcode == INT_SUB_opcode) {
567 Operand val1 = Binary.getVal1(opInstr);
568 Operand val2 = Binary.getVal2(opInstr);
569 if (val1.isConstant()) {
570 return val1.asIntConstant().value - getFixedDistanceFromPhiIterator(val2);
571 } else {
572 VM._assert(val2.isConstant());
573 return getFixedDistanceFromPhiIterator(val1) - val2.asIntConstant().value;
574 }
575 }
576 }
577 throw new Error("Value isn't fixed distance from phi iterator");
578 }
579
580 /**
581 * Test whether operand value will be invariant in a loop by tracing
582 * back earlier definitions. There is similar code in {@link
583 * LoopUnrolling}.
584 *
585 * @param op Operand to determine whether it's invariant
586 * @param loop Loop in which we wish to know the invariance of the operand
587 * @param header The loop header for determining if PEIs are invariant
588 * @return Whether the operand is invariant or not
589 */
590 private static boolean isLoopInvariant(Operand op, BitVector loop, BasicBlock header) {
591 boolean result;
592 if (op.isConstant()) {
593 result = true;
594 } else if (op.isRegister()) {
595 Instruction instr = definingInstruction(op);
596 // Is the instruction that defined this register in the loop?
597 if (!CFGTransformations.inLoop(instr.getBasicBlock(), loop)) {
598 // No => the value is invariant in the loop
599 result = true;
600 } else {
601 // Trace op to where invariant/variant values may be defined
602 switch (instr.operator().format) {
603 case InstructionFormat.Binary_format:
604 result =
605 (isLoopInvariant(Binary.getVal1(instr), loop, header) &&
606 isLoopInvariant(Binary.getVal2(instr), loop, header));
607 break;
608 case InstructionFormat.BoundsCheck_format:
609 if (isLoopInvariant(BoundsCheck.getRef(instr), loop, header) &&
610 isLoopInvariant(BoundsCheck.getIndex(instr), loop, header)) {
611 // Iterate over instructions before the null check
612 Instruction lastInst;
613 if (header == instr.getBasicBlock()) {
614 lastInst = instr;
615 } else {
616 lastInst = header.lastInstruction();
617 }
618 result = false;
619 Instruction itrInst;
620 for (itrInst = header.firstRealInstruction(); itrInst != lastInst; itrInst =
621 itrInst.nextInstructionInCodeOrder()) {
622 // Check it would be safe for this nullcheck to before
623 // the loop header without changing the exception
624 // semantics
625 if (BoundsCheck.conforms(itrInst) &&
626 BoundsCheck.getRef(itrInst).similar(BoundsCheck.getRef(instr)) &&
627 BoundsCheck.getIndex(itrInst).similar(BoundsCheck.getIndex(instr))) {
628 // it's safe if there's already an equivalent null check
629 result = true;
630 break;
631 } else if (itrInst.isAllocation() ||
632 itrInst.isDynamicLinkingPoint() ||
633 (itrInst.operator.opcode >= ARCH_INDEPENDENT_END_opcode) ||
634 itrInst.isPEI() ||
635 itrInst.isThrow() ||
636 itrInst.isImplicitLoad() ||
637 itrInst.isImplicitStore() ||
638 GCP.usesOrDefsPhysicalRegisterOrAddressType(itrInst)) {
639 // it's not safe in these circumstances (see LICM)
640 if (DEBUG) {
641 VM.sysWriteln("null check not invariant: " + itrInst);
642 }
643 break;
644 }
645 }
646 if (itrInst == instr) {
647 // did we iterate to the end of the instructions and
648 // find instr
649 result = true;
650 }
651 } else {
652 result = false;
653 }
654 break;
655 case InstructionFormat.GuardedBinary_format:
656 result =
657 (isLoopInvariant(GuardedBinary.getVal1(instr), loop, header) &&
658 isLoopInvariant(GuardedBinary.getVal2(instr), loop, header) &&
659 isLoopInvariant(GuardedBinary.getGuard(instr), loop, header));
660 break;
661 case InstructionFormat.GuardedUnary_format:
662 result =
663 (isLoopInvariant(GuardedUnary.getVal(instr), loop, header) &&
664 isLoopInvariant(GuardedUnary.getGuard(instr), loop, header));
665 break;
666 case InstructionFormat.Move_format:
667 result = isLoopInvariant(Move.getVal(instr), loop, header);
668 break;
669 case InstructionFormat.NullCheck_format:
670 if (isLoopInvariant(NullCheck.getRef(instr), loop, header)) {
671 // Iterate over instructions before the null check
672 Instruction lastInst;
673 if (header == instr.getBasicBlock()) {
674 lastInst = instr;
675 } else {
676 lastInst = header.lastInstruction();
677 }
678 result = false;
679 Instruction itrInst;
680 for (itrInst = header.firstRealInstruction(); itrInst != lastInst; itrInst =
681 itrInst.nextInstructionInCodeOrder()) {
682 // Check it would be safe for this nullcheck to before
683 // the loop header without changing the exception
684 // semantics
685 if (NullCheck.conforms(itrInst) && NullCheck.getRef(itrInst).similar(NullCheck.getRef(instr))) {
686 // it's safe if there's already an equivalent null check
687 result = true;
688 break;
689 } else if (itrInst.isAllocation() ||
690 itrInst.isDynamicLinkingPoint() ||
691 (itrInst.operator.opcode >= ARCH_INDEPENDENT_END_opcode) ||
692 itrInst.isPEI() ||
693 itrInst.isThrow() ||
694 itrInst.isImplicitLoad() ||
695 itrInst.isImplicitStore() ||
696 GCP.usesOrDefsPhysicalRegisterOrAddressType(itrInst)) {
697 // it's not safe in these circumstances (see LICM)
698 if (DEBUG) {
699 VM.sysWriteln("null check not invariant: " + itrInst);
700 }
701 break;
702 }
703 }
704 if (itrInst == instr) {
705 // did we iterate to the end of the instructions and
706 // find instr
707 result = true;
708 }
709 } else {
710 result = false;
711 }
712 break;
713 case InstructionFormat.Unary_format:
714 result = isLoopInvariant(Unary.getVal(instr), loop, header);
715 break;
716 default:
717 // Unknown instruction format so leave
718 result = false;
719 break;
720 }
721 }
722 } else { // Other operand types
723 result = false;
724 }
725 if (DEBUG) {
726 VM.sysWriteln("isLoopInvariant: " + op + (result ? " true" : " false"));
727 }
728 return result;
729 }
730
731 /**
732 * Loop invariants may not be accessible before a loop, so generate
733 * the instructions so they are
734 *
735 * @param block to generate instructions into
736 * @param op the operand we hope to use before the loop
737 */
738 public Operand generateLoopInvariantOperand(BasicBlock block, Operand op) {
739 Instruction instr = definingInstruction(op);
740 if (op.isConstant() || !CFGTransformations.inLoop(instr.getBasicBlock(), loop)) {
741 // the operand is already invariant
742 return op;
743 } else {
744 RegisterOperand result;
745 Instruction opInstr = definingInstruction(op);
746 // create result of correct type
747 if (ResultCarrier.conforms(opInstr)) {
748 result = ResultCarrier.getResult(opInstr).copyRO();
749 result.setRegister(ir.regpool.getReg(result));
750 } else {
751 if (VM.VerifyAssertions) VM._assert(GuardResultCarrier.conforms(opInstr));
752 result = GuardResultCarrier.getGuardResult(opInstr).copyRO();
753 result.setRegister(ir.regpool.getReg(result));
754 }
755 Instruction resultInstruction;
756 Operator operator = instr.operator;
757 switch (operator.format) {
758 case InstructionFormat.Binary_format:
759 resultInstruction =
760 Binary.create(operator,
761 result,
762 generateLoopInvariantOperand(block, Binary.getVal1(instr)),
763 generateLoopInvariantOperand(block, Binary.getVal2(instr)));
764 break;
765 case InstructionFormat.BoundsCheck_format:
766 resultInstruction =
767 BoundsCheck.create(operator,
768 result,
769 generateLoopInvariantOperand(block, BoundsCheck.getRef(instr)),
770 generateLoopInvariantOperand(block, BoundsCheck.getIndex(instr)),
771 generateLoopInvariantOperand(block, BoundsCheck.getGuard(instr)));
772 break;
773 case InstructionFormat.GuardedBinary_format:
774 resultInstruction =
775 GuardedBinary.create(operator,
776 result,
777 generateLoopInvariantOperand(block, GuardedBinary.getVal1(instr)),
778 generateLoopInvariantOperand(block, GuardedBinary.getVal2(instr)),
779 generateLoopInvariantOperand(block, GuardedBinary.getGuard(instr)));
780 break;
781 case InstructionFormat.GuardedUnary_format:
782 resultInstruction =
783 GuardedUnary.create(operator,
784 result,
785 generateLoopInvariantOperand(block, GuardedUnary.getVal(instr)),
786 generateLoopInvariantOperand(block, GuardedUnary.getGuard(instr)));
787 break;
788 case InstructionFormat.Move_format:
789 resultInstruction = Move.create(operator, result, generateLoopInvariantOperand(block, Move.getVal(instr)));
790 break;
791 case InstructionFormat.NullCheck_format:
792 resultInstruction =
793 NullCheck.create(operator, result, generateLoopInvariantOperand(block, NullCheck.getRef(instr)));
794 break;
795 case InstructionFormat.Unary_format:
796 resultInstruction = Unary.create(operator, result, generateLoopInvariantOperand(block, Unary.getVal(instr)));
797 break;
798 default:
799 // Unknown instruction format so leave
800 throw new Error("TODO: generate loop invariant for operator " + operator);
801 }
802 resultInstruction.copyPosition(instr);
803 block.appendInstruction(resultInstruction);
804 DefUse.updateDUForNewInstruction(resultInstruction);
805 return result.copyRO();
806 }
807 }
808
809 /**
810 * Follow the operand's definition filtering out moves
811 * This code is taken and modified from an old {@link LoopUnrolling}
812 *
813 * @param use Operand to follow
814 * @return the first defintion of the instruction which isn't a move
815 */
816 public static Operand follow(Operand use) {
817 while (true) {
818 // Are we still looking at a register operand?
819 if (!use.isRegister()) {
820 // No - we're no longer filtering out moves then
821 break;
822 }
823 // Get definitions of register
824 RegisterOperand rop = use.asRegister();
825 RegisterOperandEnumeration defs = DefUse.defs(rop.getRegister());
826 // Does register have definitions?
827 if (!defs.hasMoreElements()) {
828 // No - Register musn't be defined in this block
829 break;
830 }
831 // Get the 1st instruction that defines the register
832 use = defs.next();
833 Instruction def = use.instruction;
834 // Was the instruction that defined this register a move?
835 if (!Move.conforms(def)) {
836 // No - return the register operand from the defining instruction
837 break;
838 }
839 // Does the register have multiple defintions?
840 if (defs.hasMoreElements()) {
841 // Yes - too complex to follow so let's leave
842 break;
843 }
844 use = Move.getVal(def);
845 }
846 return use;
847 }
848
849 /**
850 * Find the instruction that defines an operand.
851 * If the operand is a register, return the instruction that defines it, else return the operands instruction
852 *
853 * @param op The operand we're searching for the definition of
854 */
855 public static Instruction definingInstruction(Operand op) {
856 Instruction result = op.instruction;
857 // Is operand a register?
858 if (op instanceof RegisterOperand) {
859 // Yes - check the definitions out
860 RegisterOperandEnumeration defs = DefUse.defs(((RegisterOperand) op).getRegister());
861 // Does this register have any defintions?
862 if (!defs.hasMoreElements()) {
863 // No - must have been defined in previous block so just return register
864 } else {
865 // Get the instruction that defines the register
866 result = defs.next().instruction;
867 // Check to see if there are any more definitions
868 if (defs.hasMoreElements()) {
869 // Multiple definitions of register, just return register to be safe
870 result = op.instruction;
871 }
872 }
873 }
874 return result;
875 }
876
877 /**
878 * Is the a particular block in this loop?
879 *
880 * @return true => block is in the loop, false => block not in loop
881 */
882 public boolean isInLoop(BasicBlock block) {
883 return CFGTransformations.inLoop(block, loop);
884 }
885
886 /**
887 * Return an enumeration of basic blocks corresponding to a depth
888 * first traversal of the blocks in the loops graphs
889 *
890 * @param block block to visit
891 * @param bbs enumeration so far
892 * @param blocksLeftToVisit blocks left to visit
893 * @return Blocks in loop with header first and exit last
894 */
895 private BBEnum getBasicBlocks(BasicBlock block, BBEnum bbs, BitVector blocksLeftToVisit) {
896 if (block != exit) {
897 bbs.add(block);
898 }
899 blocksLeftToVisit.clear(block.getNumber());
900 BasicBlockEnumeration successors = block.getNormalOut();
901 while (successors.hasMoreElements()) {
902 block = successors.next();
903 if (blocksLeftToVisit.get(block.getNumber())) {
904 getBasicBlocks(block, bbs, blocksLeftToVisit);
905 }
906 }
907 return bbs;
908 }
909
910 /**
911 * Return an enumeration of basic blocks corresponding to a depth
912 * first traversal of the blocks in the loops graphs
913 *
914 * @return Blocks in loop with header first and exit last
915 */
916 public BasicBlockEnumeration getBasicBlocks() {
917 BitVector blocksLeftToVisit = new BitVector(loop);
918 BBEnum bbs = getBasicBlocks(header, new BBEnum(), blocksLeftToVisit);
919 if (exit != null) {
920 // place the exit block at the end of the list if we've recognized one
921 bbs.add(exit);
922 }
923 return bbs;
924 }
925
926 /**
927 * Check the edges out of a block are within the loop
928 *
929 * @param block to check
930 */
931 private void checkOutEdgesAreInLoop(BasicBlock block) throws NonRegularLoopException {
932 // The blocks (copy of) that are branched to from this block
933 BasicBlockEnumeration block_outEdges = block.getOut();
934 // Check that the blocks that we branch into are all inside the loop
935 // loop_over_loop_body_block_out_edges:
936 while (block_outEdges.hasMoreElements()) {
937 BasicBlock curEdgeBB = block_outEdges.next();
938 // Is this block in the loop?
939 if ((!isInLoop(curEdgeBB)) && (block != exit)) {
940 // Block wasn't in the loop
941 throw new NonRegularLoopException(
942 "Parallelization giving up: edge out of block in loop to a block outside of the loop, and the block wasn't the loop exit" +
943 ((block == header) ? " (it was the header block though)" : ""));
944 }
945 } // end of loop_over_loop_body_block_out_edges
946 }
947
948 /**
949 * Check the edges into a block are from within the loop
950 *
951 * @param block to check
952 */
953 private void checkInEdgesAreInLoop(BasicBlock block) throws NonRegularLoopException {
954 // The blocks (copy of) that branch to this block
955 BasicBlockEnumeration block_inEdges = block.getIn();
956 // Check that the blocks that branch into this one are all inside the loop too
957 // loop_over_loop_body_block_in_edges:
958 while (block_inEdges.hasMoreElements()) {
959 BasicBlock curEdgeBB = block_inEdges.next();
960 // Is this block in the loop?
961 if ((!isInLoop(curEdgeBB)) && (block != header)) {
962 // Block wasn't in the loop
963 throw new NonRegularLoopException(
964 "Parallelization giving up: edge into a block in the loop from a block outside of the loop, and the block wasn't the loop header" +
965 ((block == exit) ? " (it was the exit block though)" : ""));
966 }
967 } // end of loop_over_loop_body_block_in_edges
968 }
969
970 // -oO Perform annotation Oo-
971 /**
972 * Convert node into annotated format
973 */
974 private void perform() throws OptimizingCompilerException {
975 // Check we have a loop
976 if (loop == null) {
977 return;
978 }
979 // Process the header first as it's the most likely source of non-regularity
980 try {
981 processHeader();
982 // Get the basic blocks that constitute the loop
983 BasicBlockEnumeration loopBlocks = getBasicBlocks();
984
985 // Loop over all blocks within this loop and calculate iterator.. information
986 // loop_over_basic_blocks:
987 while (loopBlocks.hasMoreElements()) {
988 // The current basic block
989 BasicBlock curLoopBB = loopBlocks.next();
990
991 // Is this block the loop header?
992 if (curLoopBB == header) {
993 // The header was already processed
994 } else {
995 processLoopBlock(curLoopBB);
996 }
997 }
998 } catch (NonRegularLoopException e) {
999 if (DEBUG) {
1000 VM.sysWrite(e.summary() + "\n");
1001 }
1002 // Make sure this loop looks non-regular
1003 initialIteratorValue = null;
1004 }
1005 if (DEBUG && (!isNonRegularLoop())) {
1006 dump();
1007 }
1008 }
1009
1010 /**
1011 * Process the loop header basic block
1012 */
1013 private void processHeader() throws NonRegularLoopException {
1014 // The blocks (copy of) that branch to this block
1015 BasicBlockEnumeration head_inEdges = header.getIn();
1016 // Loop over blocks that branch to this one
1017 // loop_over_header_in_edges:
1018 while (head_inEdges.hasMoreElements()) {
1019 BasicBlock curEdgeBB = head_inEdges.next();
1020 // Is this block in the loop?
1021 if (isInLoop(curEdgeBB)) {
1022 // Yes - must be the exit block
1023 if (exit != null) {
1024 // we already have an exit block so loop structure is too
1025 // complex for us to understand
1026 throw new NonRegularLoopException(
1027 "Multiple back edges to the header block making exit block undistinguishable.");
1028 }
1029 exit = curEdgeBB;
1030 processExit();
1031 } else {
1032 // No - this is an out of loop block going into the header
1033 if (predecessor != null) {
1034 // we already have a predecessor to the header block, more
1035 // than 1 is beyond this optimisation at the moment
1036 throw new NonRegularLoopException(
1037 "Multiple out of loop edges into the header making predecessor block undistinguishable.");
1038 }
1039 predecessor = curEdgeBB;
1040 }
1041 } // end of loop_over_header_in_edges
1042 // If the header isn't the exit block, check it doesn't branch outside of the loop
1043 if (header != exit) {
1044 checkOutEdgesAreInLoop(header);
1045 }
1046 }
1047
1048 /**
1049 * Process the loop exit basic block
1050 */
1051 private void processExit() throws NonRegularLoopException {
1052 // If the exit isn't the header block, check it doesn't have in edges from outside the loop
1053 if (header != exit) {
1054 checkInEdgesAreInLoop(exit);
1055 }
1056 // Check the exit block leaves the loop
1057 BasicBlockEnumeration exitBlock_outEdges = exit.getOut();
1058 boolean exits = false;
1059 // check_exit_block_exits:
1060 while (exitBlock_outEdges.hasMoreElements()) {
1061 BasicBlock curExitBlockOutEdgeBB = exitBlock_outEdges.next();
1062 if (isInLoop(curExitBlockOutEdgeBB)) {
1063 // An in loop out edge from the exit block
1064 } else {
1065 // An out of loop edge from the exit block
1066 exits = true;
1067 successor = curExitBlockOutEdgeBB;
1068 if (successor == header) {
1069 throw new NonRegularLoopException("Unimplemented condition - see LoopUnrolling.java : 240");
1070 }
1071 }
1072 } // end of check_exit_block_exits
1073 if (!exits) {
1074 throw new NonRegularLoopException(
1075 "Exit block (containing back edge to header) doesn't have an out of loop out edge.");
1076 } else {
1077 // Get the if instruction used to loop in the exit block
1078 ifCmpInstr = exit.firstBranchInstruction();
1079 if (ifCmpInstr == null) {
1080 throw new NonRegularLoopException("Exit block branch doesn't have a (1st) branching instruction.");
1081 } else if (ifCmpInstr.operator.opcode != INT_IFCMP_opcode) {
1082 throw new NonRegularLoopException("branch is int_ifcmp but " + ifCmpInstr.operator + "\n");
1083 } else {
1084 // Get the terminal and iterator operations
1085 carriedLoopIterator = follow(IfCmp.getVal1(ifCmpInstr));
1086 terminalIteratorValue = follow(IfCmp.getVal2(ifCmpInstr));
1087 condition = (ConditionOperand) IfCmp.getCond(ifCmpInstr).copy();
1088 // Check we have them the right way around and that they do the job we expect
1089 {
1090 boolean iteratorInvariant = isLoopInvariant(carriedLoopIterator, loop, header);
1091 boolean terminalValueInvariant = isLoopInvariant(terminalIteratorValue, loop, header);
1092 // Is the iterator loop invariant?
1093 if (iteratorInvariant) {
1094 // Yes - Is the terminal value loop invariant?
1095 if (terminalValueInvariant) {
1096 // Yes - both parameters to the condition are invariant
1097 throw new NonRegularLoopException(
1098 "Exit block condition values are both invariant (single or infinite loop):\n" +
1099 "Loop = " +
1100 loop.toString() +
1101 "\nIterator = " +
1102 carriedLoopIterator +
1103 "\nTerminal = " +
1104 terminalIteratorValue);
1105 } else {
1106 // No - swap values over
1107 Operand temp = terminalIteratorValue;
1108 terminalIteratorValue = carriedLoopIterator;
1109 carriedLoopIterator = temp;
1110 }
1111 } else {
1112 // No - Is the terminal value loop invariant?
1113 if (terminalValueInvariant) {
1114 // Yes - this is the condition we hoped for
1115 } else {
1116 // No - both loop values are variant and loop is too complex to analyse
1117 throw new NonRegularLoopException("Exit block condition values are both variant.");
1118 }
1119 }
1120 }
1121 // Check target of "if" is the header
1122 if (Label.getBlock(IfCmp.getTarget(ifCmpInstr).target).block != header) {
1123 // No - can't optimise loop in this format
1124 // TODO: swap ifxxx around so that branch is to header and fall-through is exit
1125 throw new NonRegularLoopException("Target of exit block branch isn't the loop header.");
1126 }
1127 // Calculate stride value
1128 RegisterOperandEnumeration iteratorDefs =
1129 DefUse.defs(((RegisterOperand) carriedLoopIterator).getRegister());
1130 // Loop over definitions of the iterator operand ignoring moves
1131 while (iteratorDefs.hasMoreElements()) {
1132 Operand curDef = follow(iteratorDefs.next());
1133 // Is this definition within the loop?
1134 if (isInLoop(curDef.instruction.getBasicBlock())) {
1135 // Yes - have we already got an iterator instruction
1136 if ((iteratorInstr == null) || (iteratorInstr == curDef.instruction)) {
1137 // No - record
1138 iteratorInstr = curDef.instruction;
1139 } else {
1140 // Yes - loop too complex again
1141 throw new NonRegularLoopException("Multiple definitions of the iterator.");
1142 }
1143 }
1144 }
1145 // Did we find an instruction?
1146 if (iteratorInstr == null) {
1147 // No => error
1148 throw new NonRegularLoopException("No iterator definition found.");
1149 } else
1150 if ((iteratorInstr.operator.opcode != INT_ADD_opcode) && (iteratorInstr.operator.opcode != INT_SUB_opcode)) {
1151 // Is it an instruction we recognise?
1152 // TODO: support more iterator instructions
1153 throw new NonRegularLoopException("Unrecognized iterator operator " + iteratorInstr.operator);
1154 } else {
1155 // only carry on further analysis if we think we can understand the loop
1156 // Does this iterator instruction use the same register as it defines
1157 Operand iteratorUse = follow(Binary.getVal1(iteratorInstr));
1158 // The iterator should be using a phi node of the initial and generated value
1159 if (!carriedLoopIterator.similar(iteratorUse)) {
1160 // SSA ok so far, read PHI node
1161 Instruction phiInstr = iteratorUse.instruction;
1162 if (!Phi.conforms(phiInstr)) {
1163 // We didn't find a PHI instruction
1164 throw new NonRegularLoopException("Iterator (" +
1165 iteratorUse +
1166 ") not using a phi instruction but " +
1167 phiInstr);
1168 }
1169 // We have the SSA we hoped for - tidy up
1170 strideValue = follow(Binary.getVal2(iteratorInstr));
1171 initialIteratorValue = follow(Phi.getValue(phiInstr, 0));
1172 phiLoopIterator = iteratorUse;
1173 if (initialIteratorValue instanceof BasicBlockOperand) {
1174 throw new Error("BasicBlock mess up!");
1175 }
1176 if (initialIteratorValue == iteratorUse) {
1177 initialIteratorValue = follow(Phi.getValue(phiInstr, 1));
1178 }
1179 if (initialIteratorValue instanceof BasicBlockOperand) {
1180 throw new Error("BasicBlock mess up!2");
1181 }
1182 } else {
1183 // Not in SSA form as iterator modifies an operand
1184 throw new NonRegularLoopException("Iterator modifies (uses and defines) operand " +
1185 iteratorUse +
1186 " and is therefore not in SSA form.");
1187 }
1188 // Check the initialIteratorValue was defined outside of (before) the loop header or is constant
1189 if (!isLoopInvariant(initialIteratorValue, loop, header)) {
1190 throw new NonRegularLoopException("Initial iterator not constant or defined outside the loop - " +
1191 initialIteratorValue);
1192 } else if (!(strideValue instanceof ConstantOperand)) {
1193 // Check the stride value constant
1194 throw new NonRegularLoopException("Stride not constant - " + strideValue);
1195 }
1196 }
1197 }
1198 }
1199 }
1200
1201 /**
1202 * Process a regular block within the loop
1203 *
1204 * @param block The basic block to process
1205 */
1206 private void processLoopBlock(BasicBlock block) throws NonRegularLoopException {
1207 checkInEdgesAreInLoop(block);
1208 checkOutEdgesAreInLoop(block);
1209 }
1210
1211 /**
1212 * Get the carried loop iterator
1213 *
1214 * @return carried loop iterator
1215 */
1216 public Operand getCarriedLoopIterator() {
1217 return carriedLoopIterator;
1218 }
1219
1220 // -oO Utility classes Oo-
1221 /**
1222 * Exception thrown when a non-regular loop is encountered
1223 */
1224 private static class NonRegularLoopException extends Exception {
1225 /** Support for exception serialization */
1226 static final long serialVersionUID = -7553504903633114882L;
1227 /**
1228 * Brief description of problem
1229 */
1230 private final String _summary;
1231
1232 /**
1233 * Constructor
1234 */
1235 NonRegularLoopException(String s) {
1236 super(s);
1237 _summary = s;
1238 }
1239
1240 /**
1241 * A brief description of the error
1242 */
1243 String summary() {
1244 return _summary;
1245 }
1246 }
1247
1248 /**
1249 * This class implements {@link BasicBlockEnumeration}. It is
1250 * used for iterating over basic blocks in a fashion determined by
1251 * the order in which basic blocks are added.
1252 */
1253 static final class BBEnum implements BasicBlockEnumeration {
1254 /**
1255 * ArrayList holding basic blocks
1256 */
1257 private final ArrayList<BasicBlock> blocks;
1258 /**
1259 * The current block of the iterator
1260 */
1261 private int currentBlock;
1262
1263 /**
1264 * Constructor
1265 */
1266 public BBEnum() {
1267 blocks = new ArrayList<BasicBlock>();
1268 }
1269
1270 /**
1271 * Insert a block to the end of the list
1272 * @param block to insert
1273 */
1274 public void add(BasicBlock block) {
1275 blocks.add(block);
1276 }
1277
1278 /**
1279 * Is the iterator at the end of the vector
1280 * @return whether there are more elements in the vector
1281 */
1282 public boolean hasMoreElements() {
1283 return currentBlock < blocks.size();
1284 }
1285
1286 /**
1287 * Get the next element from the vector and move the current block along
1288 * @return next element
1289 */
1290 public BasicBlock nextElement() {
1291 BasicBlock result = blocks.get(currentBlock);
1292 currentBlock++;
1293 return result;
1294 }
1295
1296 /**
1297 * Get the next element from the vector and return without requiring a cast
1298 * @return next element
1299 */
1300 public BasicBlock next() {
1301 BasicBlock result = blocks.get(currentBlock);
1302 currentBlock++;
1303 return result;
1304 }
1305
1306 /**
1307 * String representation of the object
1308 * @return string representing the object
1309 */
1310 public String toString() {
1311 return blocks.toString();
1312 }
1313 }
1314 }