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