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