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.ir;
014
015import static org.jikesrvm.compilers.opt.driver.OptConstants.UNKNOWN_BCI;
016import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
017import static org.jikesrvm.compilers.opt.ir.Operators.DOUBLE_IFCMP_opcode;
018import static org.jikesrvm.compilers.opt.ir.Operators.FLOAT_IFCMP_opcode;
019import static org.jikesrvm.compilers.opt.ir.Operators.GOTO_opcode;
020import static org.jikesrvm.compilers.opt.ir.Operators.IG_CLASS_TEST_opcode;
021import static org.jikesrvm.compilers.opt.ir.Operators.IG_METHOD_TEST_opcode;
022import static org.jikesrvm.compilers.opt.ir.Operators.IG_PATCH_POINT_opcode;
023import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP2_opcode;
024import static org.jikesrvm.compilers.opt.ir.Operators.INT_IFCMP_opcode;
025import static org.jikesrvm.compilers.opt.ir.Operators.LABEL;
026import static org.jikesrvm.compilers.opt.ir.Operators.LONG_IFCMP_opcode;
027import static org.jikesrvm.compilers.opt.ir.Operators.LOOKUPSWITCH_opcode;
028import static org.jikesrvm.compilers.opt.ir.Operators.LOWTABLESWITCH_opcode;
029import static org.jikesrvm.compilers.opt.ir.Operators.REF_IFCMP_opcode;
030import static org.jikesrvm.compilers.opt.ir.Operators.TABLESWITCH_opcode;
031
032import java.util.Enumeration;
033
034import org.jikesrvm.VM;
035import org.jikesrvm.compilers.opt.LocalCSE;
036import org.jikesrvm.compilers.opt.OptimizingCompilerException;
037import org.jikesrvm.compilers.opt.inlining.InlineSequence;
038import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
039import org.jikesrvm.compilers.opt.ir.operand.MemoryOperand;
040import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
041import org.jikesrvm.compilers.opt.ir.operand.Operand;
042import org.jikesrvm.compilers.opt.ir.operand.StackLocationOperand;
043import org.vmmagic.pragma.Inline;
044import org.vmmagic.pragma.NoInline;
045
046/**
047 * Instructions are the basic atomic unit of the IR.
048 * An instruction contains an {@link Operator operator} and
049 * (optionally) some {@link Operand operands}.
050 * In addition, an instruction may (or may not) have
051 * valid {@link #bcIndex} and{@link #position} fields that
052 * together encode a description of the bytecode that it came from.
053 * <p>
054 * Although we use a single class, <code>Instruction</code>,
055 * to implement all IR instructions, there are logically a number
056 * of different kinds of instructions.
057 * For example, binary operators, array loads, calls,
058 * and null_checks all have different number of operands with differing
059 * semantics.  To manage this in an abstract, somewhat object-oriented,
060 * but still highly efficient fashion we have the notion of an
061 * <em>Instruction Format</em>. An Instruction Format is a class
062 * external to Instruction (defined in the instructionFormat package)
063 * that provides static methods to create instructions and symbolically
064 * access their operands.  Every instance of <code>Operator</code>
065 * is assigned to exactly one Instruction Format.  Thus, the instruction's
066 * operator implies which Instruction Format class can be used to
067 * access the instruction's operands.
068 * <p>
069 * There are some common logical operands (eg Result, Location) that
070 * appear in a large number of Instruction Formats.  In addition to the
071 * basic Instruction Format classes, we provided additional classes
072 * (eg ResultCarrier, LocationCarrier) that allow manipulation of all
073 * instructions that contain a common operands.
074 * <p>
075 * A configuration (OptOptVIFcopyingGC) is defined in which all methods of
076 * all Instruction Format classes verify that the operator of the instruction
077 * being manipulated actually belongs to the appropriate Instruction Format.
078 * This configuration is quite slow, but is an important sanity check to make
079 * sure that Instruction Formats are being used in a consistent fashion.
080 * <p>
081 * The instruction's operator also has a number of traits.  Methods on
082 * <code>Instruction</code> are provided to query these operator traits.
083 * In general, clients should use the methods of Instruction to query
084 * traits, since a particular instruction may override the operator-provided
085 * default in some cases. For example, {@link #isMove()}, {@link #isBranch()},
086 * {@link #isPEI()}, and {@link #isCall()} are some of the trait queries.
087 * <p>
088 * Unfortunately, the combination of operators, operator traits, and
089 * Instruction Formats often leads to a tricky decision of which of three
090 * roughly equivalent idioms one should use when writing code that
091 * needs to manipulate instructions and their operands.
092 * For example,
093 * <pre>
094 * if (Call.conforms(instr)) {
095 *    return Call.getResult(instr);
096 * }
097 * </pre>
098 * and
099 * <pre>
100 * if (instr.operator() == CALL) {
101 *    return Call.getResult(instr);
102 * }
103 * </pre>
104 * and
105 * <pre>
106 * if (instr.isCall()) {
107 *    return ResultCarrier.getResult(instr);
108 * }
109 * </pre>
110 * are more or less the same.
111 * In some cases, picking an idiom is simply a matter of taste,
112 * but in others making the wrong choice can lead to code that is less
113 * robust or maintainable as operators and/or instruction formats are added
114 * and removed from the IR. One should always think carefully about which
115 * idiom is the most concise, maintainable, robust and efficient means of
116 * accomplishing a given task.
117 * Some general rules of thumb (or at least one person's opinion):
118 * <ul>
119 * <li> Tests against operator traits should be preferred
120 *      to use of the conforms method of an Instruction Format class if
121 *      both are possible.  This is definitely true if the code in question
122 *      does not need to access specific operands of the instruction.
123 *      Things are murkier if the code needs to manipulate specific
124 *      (non-common) operands of the instruction.
125 * <li> If you find yourself writing long if-then-else constructs using
126 *      either Instruction Format conforms or operator traits then you ought to
127 *      at least consider writing a switch statement on the opcode of the
128 *      operator.  It should be more efficient and, depending on what your
129 *      desired default behavior is, may be more robust/maintainable as well.
130 * <li> Instruction Format classes are really intended to represent the
131 *      "syntactic form" of an instruction, not the semantics of its operator.
132 *      Using "conforms" when no specific operands are being manipulated
133 *      is almost always not the right way to do things.
134 * </ul>
135 *
136 * @see Operator
137 * @see Operand
138 * @see BasicBlock
139 */
140public final class Instruction {
141
142  /**
143   * BITFIELD used to encode {@link #operatorInfo}.
144   * NB: OI_INVALID must be default value!
145   */
146  private static final byte OI_INVALID = 0x00;
147  /** BITFIELD used to encode {@link #operatorInfo}. */
148  private static final byte OI_PEI_VALID = 0x01;
149  /** BITFIELD used to encode {@link #operatorInfo}. */
150  private static final byte OI_PEI = 0x02;
151  /** BITFIELD used to encode {@link #operatorInfo}. */
152  private static final byte OI_GC_VALID = 0x04;
153  /** BITFIELD used to encode {@link #operatorInfo}. */
154  private static final byte OI_GC = 0x08;
155
156  /*
157   * NOTE: There are currently several free bits: 0x10, 0x20,
158   * 0x40 and 0x80.
159   */
160
161  /**
162   * The index of the bytecode that this instruction came from.
163   * In combination with the {@link #position}, the bcIndex field
164   * uniquely identifies the source position of the bytecode that
165   * this instruction came from.
166   */
167  public int bcIndex = UNKNOWN_BCI;
168
169  /**
170   * A description of the tree of inlined methods that contains the bytecode
171   * that this instruction came from.<p>
172   * In combination with the {@link #bcIndex}, the position field
173   * uniquely identifies the source position of the bytecode that
174   * this instruction came from.<p>
175   * A single position operator can be shared by many instruction objects.
176   *
177   * @see InlineSequence
178   * @see org.jikesrvm.compilers.opt.runtimesupport.OptEncodedCallSiteTree
179   */
180  public InlineSequence position;
181
182  /**
183   * The operator for this instruction.<p>
184   * The same operator object can be shared by many instruction objects.
185   */
186  private Operator operator;
187
188  /**
189   * The next instruction in the intra-basic-block list of instructions,
190   * will be {@code null} if no such instruction exists.
191   */
192  private Instruction next;
193
194  /**
195   * The previous instruction in the intra-basic-block list of instructions,
196   * will be {@code null} if no such instruction exists.
197   */
198  private Instruction prev;
199
200  /**
201   * Override and refine the operator-based trait (characteristic)
202   * information.
203   * @see Operator
204   */
205  private byte operatorInfo = OI_INVALID;
206
207  /**
208   * The operands of this instruction.
209   */
210  private Operand[] ops;
211
212  /**
213   * INTERNAL IR USE ONLY: create a new instruction with the specified number
214   * of operands.<p>
215   *
216   * <strong>For internal use only -- general clients MUST use the appropriate
217   * InstructionFormat class's create and mutate methods to create
218   * instruction objects!!!</strong>
219   *
220   * @param op operator
221   * @param size number of operands
222   * @return the created instruction
223   */
224  public static Instruction create(Operator op, int size) {
225    return new Instruction(op, size);
226  }
227
228  private Instruction(Operator op, int size) {
229    operator = op;
230    ops = new Operand[size];
231  }
232
233  /**
234   * Create a copy of this instruction.
235   * The copy has the same operator and operands, but is not linked into
236   * an instruction list.
237   *
238   * @return the copy
239   */
240  public Instruction copyWithoutLinks() {
241    Instruction copy = new Instruction(operator, ops.length);
242    for (int i = 0; i < ops.length; i++) {
243      if (ops[i] != null) {
244        copy.ops[i] = ops[i].copy();
245        copy.ops[i].instruction = copy;
246      }
247    }
248    copy.bcIndex = bcIndex;
249    copy.operatorInfo = operatorInfo;
250    copy.position = position;
251
252    return copy;
253  }
254
255  /**
256   * Returns the string representation of this instruction
257   * (mainly intended for use when printing the IR).
258   *
259   * @return string representation of this instruction.
260   */
261  @Override
262  public String toString() {
263    StringBuilder result = new StringBuilder("    ");
264    if (isPEI()) {
265      result.setCharAt(0, 'E');
266    }
267    if (isGCPoint()) {
268      result.setCharAt(1, 'G');
269    }
270
271    if (operator == LABEL) {
272      result.append("LABEL").append(Label.getBlock(this).block.getNumber());
273      if (Label.getBlock(this).block.getInfrequent()) result.append(" (Infrequent)");
274      return result.toString();
275    }
276
277    result.append(operator);
278    Operand op;
279    int N = getNumberOfOperands();
280    int numDefs = getNumberOfDefs();
281    //int numIDefs = operator.getNumberOfImplicitDefs();
282
283    // print explicit defs
284    int defsPrinted = 0;
285    for (int i = 0; i < numDefs; i++) {
286      op = getOperand(i);
287      if (op != null) {
288        if (defsPrinted > 0) result.append(", ");
289        if (defsPrinted % 10 == 9) result.append('\n');
290        result.append(op);
291        defsPrinted++;
292      }
293    }
294
295    // print implicit defs
296    result.append(GenericPhysicalDefUse.getString(operator.implicitDefs));
297    defsPrinted += operator.getNumberOfImplicitDefs();
298
299    // print separator
300    if (defsPrinted > 0) {
301      if (operator.getNumberOfDefUses() == 0) {
302        result.append(" = ");
303      } else {
304        result.append(" <-- ");
305      }
306    }
307
308    // print explicit uses
309    int usesPrinted = 0;
310    for (int i = numDefs; i < N; i++) {
311      op = getOperand(i);
312      if (usesPrinted > 0) result.append(", ");
313      if ((defsPrinted + usesPrinted) % 10 == 9) result.append('\n');
314      usesPrinted++;
315      if (op != null) {
316        result.append(op);
317      } else {
318        result.append("<unused>");
319      }
320    }
321
322    // print implicit defs
323    result.append(GenericPhysicalDefUse.getString(operator.implicitUses));
324    usesPrinted += operator.getNumberOfImplicitUses();
325
326    return result.toString();
327  }
328
329  /**
330   * Return the next instruction with respect to the current
331   * code linearization order.
332   *
333   * @return the next instruction in the code order or
334   *         <code>null</code> if no such instruction exists
335   */
336  public Instruction nextInstructionInCodeOrder() {
337    if (next == null) {
338      if (VM.VerifyAssertions) VM._assert(BBend.conforms(this));
339      BasicBlock nBlock = BBend.getBlock(this).block.nextBasicBlockInCodeOrder();
340      if (nBlock == null) {
341        return null;
342      } else {
343        return nBlock.firstInstruction();
344      }
345    } else {
346      return next;
347    }
348  }
349
350  /**
351   * Return the previous instruction with respect to the current
352   * code linearization order.
353   *
354   * @return the previous instruction in the code order or
355   *         <code>null</code> if no such instruction exists
356   */
357  public Instruction prevInstructionInCodeOrder() {
358    if (prev == null) {
359      BasicBlock nBlock = Label.getBlock(this).block.prevBasicBlockInCodeOrder();
360      if (nBlock == null) {
361        return null;
362      } else {
363        return nBlock.lastInstruction();
364      }
365    } else {
366      return prev;
367    }
368  }
369
370  /**
371   * @return has this instruction been linked with a previous instruction? ie
372   *         will calls to insertBefore succeed?
373   */
374  public boolean hasPrev() {
375    return prev != null;
376  }
377
378  /**
379   * Gets the basic block that contains this instruction.
380   * <p>
381   * Note: this instruction takes O(1) time for LABEL and BBEND
382   * instructions, but will take O(# of instrs in the block)
383   * for all other instructions. Therefore, although it can be used
384   * on any instruction, care must be taken when using it to avoid
385   * doing silly O(N^2) work for what could be done in O(N) work.
386   *
387   * @return basic block that contains the instruction
388   */
389  public BasicBlock getBasicBlock() {
390    if (isBbFirst()) {
391      return Label.getBlock(this).block;
392    } else if (isBbLast()) {
393      return BBend.getBlock(this).block;
394    } else {
395      // Find basic block by going forwards to BBEND instruction
396      Instruction instr = null; // Set = null to avoid compiler warning.
397      for (instr = getNext(); !instr.isBbLast(); instr = instr.getNext()) ;
398      return BBend.getBlock(instr).block;
399    }
400  }
401
402  /**
403   * Set the source position description ({@link #bcIndex},
404   * {@link #position}) for this instruction to be the same as the
405   * source instruction's source position description.
406   *
407   * @param source the instruction to copy the source position from
408   */
409  public void copyPosition(Instruction source) {
410    bcIndex = source.bcIndex;
411    position = source.position;
412  }
413
414  /**
415   * Get the {@link #bcIndex bytecode index} of the instruction.
416   *
417   * @return the bytecode index of the instruction
418   */
419  public int getBytecodeIndex() {
420    return bcIndex;
421  }
422
423  /**
424   * Set the {@link #bcIndex bytecode index} of the instruction.
425   *
426   * @param bci the new bytecode index
427   */
428  public void setBytecodeIndex(int bci) {
429    bcIndex = bci;
430  }
431
432  /**
433   * Return the instruction's operator.
434   *
435   * @return the operator
436   */
437  public Operator operator() {
438    return operator;
439  }
440
441  public void changeOperatorTo(Operator newlySetOperator) {
442    operator = newlySetOperator;
443  }
444
445  /**
446   * Return the opcode of the instruction's operator
447   * (a unique id suitable for use in switches); see
448   * {@link Operator#opcode}.
449   *
450   * @return the operator's opcode
451   */
452  public char getOpcode() {
453    return operator.opcode;
454  }
455
456  /*
457  * Functions dealing with the instruction's operands.
458  * Clients currently are grudgingly allowed (but definitely NOT encouraged)
459  * to depend on the fact that operands are partially ordered:
460  * first all the defs, then all the def/uses, then all the uses.
461  * This may change in the future, so please try not to depend on it unless
462  * absolutely necessary.
463  *
464  * Clients must NOT assume that specific operands appear in
465  * a particular order or at a particular index in the operand array.
466  * Doing so results in fragile code and is generally evil.
467  * Virtually all access to operands should be through the operand enumerations
468  * or through accessor functions of the InstructionFormat classes.
469  */
470
471  /**
472   * Get the number of operands in this instruction.
473   *
474   * @return number of operands
475   */
476  public int getNumberOfOperands() {
477    if (operator.hasVarUsesOrDefs()) {
478      return getNumberOfOperandsVarUsesOrDefs();
479    } else {
480      return operator.getNumberOfDefs() + operator.getNumberOfPureUses();
481    }
482  }
483
484  // isolate uncommon cases to enable inlined common case of getNumberOfOperands
485  private int getNumberOfOperandsVarUsesOrDefs() {
486    int numOps = ops.length - 1;
487    int minOps;
488    if (operator().hasVarUses()) {
489      minOps = operator.getNumberOfDefs() + operator.getNumberOfPureFixedUses() - 1;
490    } else {
491      minOps = operator.getNumberOfFixedPureDefs() - 1;
492    }
493    while (numOps > minOps && ops[numOps] == null) numOps--;
494    return numOps + 1;
495  }
496
497  /**
498   * Returns the number of operands that are defs
499   * (either pure defs or combined def/uses).<p>
500   *
501   * By convention, operands are ordered in instructions
502   * such that all defs are first, followed by all
503   * combined defs/uses, followed by all pure uses.
504   * Note that this may change in the future.
505   *
506   * @return number of operands that are defs
507   */
508  public int getNumberOfDefs() {
509    if (operator.hasVarDefs()) {
510      int numOps = operator.getNumberOfFixedPureDefs();
511      for (; numOps < ops.length; numOps++) {
512        if (ops[numOps] == null) break;
513      }
514      return numOps;
515    } else {
516      return operator.getNumberOfDefs();
517    }
518  }
519
520  /**
521   * Returns the number of operands that are pure defs.<p>
522   *
523   * By convention, operands are ordered in instructions
524   * such that all defs are first, followed by all
525   * combined defs/uses, followed by all pure uses.
526   * Note that this may change in the future.
527   *
528   * @return number of operands that are defs
529   */
530  public int getNumberOfPureDefs() {
531    if (operator.hasVarDefs()) {
532      if (VM.VerifyAssertions) {
533        VM._assert(operator.getNumberOfDefUses() == 0);
534      }
535      int numOps = operator.getNumberOfFixedPureDefs();
536      for (; numOps < ops.length; numOps++) {
537        if (ops[numOps] == null) break;
538      }
539      return numOps;
540    } else {
541      return operator.getNumberOfFixedPureDefs();
542    }
543  }
544
545  /**
546   * Returns the number of operands that are pure uses.<p>
547   *
548   * By convention, operands are ordered in instructions
549   * such that all defs are first, followed by all
550   * combined defs/uses, followed by all pure uses.
551   * Note that this may change in the future.
552   *
553   * @return number of operands that are defs
554   */
555  public int getNumberOfPureUses() {
556    if (operator.hasVarDefs()) {
557      if (VM.VerifyAssertions) {
558        VM._assert(operator.getNumberOfDefUses() == 0);
559      }
560      int numOps = operator.getNumberOfFixedPureUses();
561      int i = getNumberOfDefs() + numOps;
562      for (; i < ops.length; i++) {
563        if (ops[i] == null) break;
564        numOps++;
565      }
566      return numOps;
567    } else {
568      if (operator.hasVarUses()) {
569        return getNumberOfOperands() - operator.getNumberOfDefs();
570      } else {
571        return operator.getNumberOfFixedPureUses();
572      }
573    }
574  }
575
576  /**
577   * Returns the number of operands that are uses
578   * (either combined def/uses or pure uses).<p>
579   *
580   * By convention, operands are ordered in instructions
581   * such that all defs are first, followed by all
582   * combined defs/uses, followed by all pure uses.
583   * Note that this may change in the future.
584   *
585   * @return how many operands are uses
586   */
587  public int getNumberOfUses() {
588    if (operator.hasVarUses()) {
589      return getNumberOfOperands() - operator.getNumberOfPureDefs();
590    } else {
591      return operator.getNumberOfUses();
592    }
593  }
594
595  /**
596   * Replace all occurances of the first operand with the second.
597   *
598   * @param oldOp   The operand to replace
599   * @param newOp   The new one to replace it with
600   */
601  public void replaceOperand(Operand oldOp, Operand newOp) {
602    for (int i = 0; i < ops.length; i++) {
603      if (getOperand(i) == oldOp) {
604        putOperand(i, newOp);
605      }
606    }
607  }
608
609  /**
610   * Replace any operands that are similar to the first operand
611   * with a copy of the second operand.
612   *
613   * @param oldOp   The operand whose similar operands should be replaced
614   * @param newOp   The new one to replace it with
615   */
616  public void replaceSimilarOperands(Operand oldOp, Operand newOp) {
617    for (int i = 0; i < ops.length; i++) {
618      if (oldOp.similar(getOperand(i))) {
619        putOperand(i, newOp.copy());
620      }
621    }
622  }
623
624  /**
625   * Replace all occurances of register r with register n
626   *
627   * @param r the old register
628   * @param n the new register
629   */
630  public void replaceRegister(Register r, Register n) {
631    for (Enumeration<Operand> u = getUses(); u.hasMoreElements();) {
632      Operand use = u.nextElement();
633      if (use.isRegister()) {
634        if (use.asRegister().getRegister() == r) {
635          use.asRegister().setRegister(n);
636        }
637      }
638    }
639    for (Enumeration<Operand> d = getDefs(); d.hasMoreElements();) {
640      Operand def = d.nextElement();
641      if (def.isRegister()) {
642        if (def.asRegister().getRegister() == r) {
643          def.asRegister().setRegister(n);
644        }
645      }
646    }
647  }
648
649  /**
650   * @return {@code true} if this instruction holds any memory or
651   *  stack location operands
652   */
653  public boolean hasMemoryOperand() {
654    for (int i = 0; i < ops.length; i++) {
655      Operand op = getOperand(i);
656      if (op instanceof MemoryOperand || op instanceof StackLocationOperand) {
657        return true;
658      }
659    }
660    return false;
661  }
662
663  /**
664   * Enumerate all "leaf" operands of an instruction.
665   * <p>
666   * NOTE: DOES NOT RETURN MEMORY OPERANDS, ONLY
667   *       THEIR CONTAINED OPERANDS!!!!!
668   *
669   * @return an enumeration of the instruction's operands.
670   */
671  public Enumeration<Operand> getOperands() {
672    // By passing -1 as the last parameter we pretending
673    // that treating all operands are uses. Somewhat ugly,
674    // but avoids a third OE class.
675    return new OE(this, 0, getNumberOfOperands() - 1, -1);
676  }
677
678  /**
679   * Enumerate all memory operands of an instruction
680   *
681   * @return an enumeration of the instruction's operands.
682   */
683  public Enumeration<Operand> getMemoryOperands() {
684    return new MOE(this, 0, getNumberOfOperands() - 1);
685  }
686
687  /**
688   * Enumerate all the root operands of an instruction
689   * (DOES NOT ENUMERATE CONTAINED OPERANDS OF MEMORY OPERANDS).
690   *
691   * @return an enumeration of the instruction's operands.
692   */
693  public Enumeration<Operand> getRootOperands() {
694    return new ROE(this, 0, getNumberOfOperands() - 1);
695  }
696
697  /**
698   * Enumerate all defs (both pure defs and def/uses) of an instruction.
699   *
700   * @return an enumeration of the instruction's defs.
701   */
702  public Enumeration<Operand> getDefs() {
703    return new OEDefsOnly(this, 0, getNumberOfDefs() - 1);
704  }
705
706  /**
707   * Enumerate all the pure defs (ie not including def/uses) of an instruction.
708   *
709   * @return an enumeration of the instruction's pure defs.
710   */
711  public Enumeration<Operand> getPureDefs() {
712    return new OEDefsOnly(this, 0, getNumberOfPureDefs() - 1);
713  }
714
715  /**
716   * Enumerate all the pure uses (ie not including def/uses) of an instruction.
717   *
718   * @return an enumeration of the instruction's pure defs.
719   */
720  public Enumeration<Operand> getPureUses() {
721    return new OEDefsOnly(this, getNumberOfDefs(), getNumberOfOperands() - 1);
722  }
723
724  /**
725   * Enumerate all the def/uses of an instruction.
726   *
727   * @return an enumeration of the instruction's def/uses.
728   */
729  public Enumeration<Operand> getDefUses() {
730    return new OEDefsOnly(this, getNumberOfPureDefs(), getNumberOfDefs() - 1);
731  }
732
733  /**
734   * Enumerate all uses of an instruction (includes def/use).
735   *
736   * @return an enumeration of the instruction's uses.
737   */
738  @Inline
739  public Enumeration<Operand> getUses() {
740    int numOps = getNumberOfOperands() - 1;
741    int defsEnd = operator.hasVarDefs() ? numOps : operator.getNumberOfPureDefs() - 1;
742    return new OE(this, 0, numOps, defsEnd);
743  }
744
745  /**
746   * Enumerate all root uses of an instruction.
747   *
748   * @return an enumeration of the instruction's uses.
749   */
750  public Enumeration<Operand> getRootUses() {
751    return new ROE(this, getNumberOfPureDefs(), getNumberOfOperands() - 1);
752  }
753
754  /*
755  * Methods dealing with the instruction's operator.
756  * In the HIR and LIR these methods act simply as forwarding
757  * methods to the Operator method.  In the MIR, they allow
758  * us to override the operator-level defaults. Overrides mainly
759  * occur from null-check combining (the null check gets folded into
760  * a load/store instruction which does the check in hardware via
761  * a segv when the ptr is null), but may occur for other reasons as well.
762  * In the future, we may allow overrides on the HIR/LIR as well.
763  * Thus, it is generally a good idea for clients to always use the
764  * instruction variant of these methods rather than calling the
765  * corresponding method directly on the operator.
766  */
767
768  /**
769   * Does the instruction represent a simple move (the value is unchanged)
770   * from one "register" location to another "register" location?
771   *
772   * @return <code>true</code> if the instruction is a simple move
773   *         or <code>false</code> if it is not.
774   */
775  public boolean isMove() {
776    return operator.isMove();
777  }
778
779  /**
780   * Is the instruction an intraprocedural branch?
781   *
782   * @return <code>true</code> if the instruction is am
783   *         intraprocedural branch or <code>false</code> if it is not.
784   */
785  public boolean isBranch() {
786    return operator.isBranch();
787  }
788
789  /**
790   * Is the instruction a conditional intraprocedural branch?
791   *
792   * @return <code>true</code> if the instruction is a conditional
793   *         intraprocedural branch or <code>false</code> if it is not.
794   */
795  public boolean isConditionalBranch() {
796    return operator.isConditionalBranch();
797  }
798
799  /**
800   * Is this instruction a branch that has that has only two possible
801   * successors?
802   *
803   * @return <code>true</code> if the instruction is an
804   * interprocedural conditional branch with only two possible
805   * outcomes (taken or not taken).
806   */
807  public boolean isTwoWayBranch() {
808    return isConditionalBranch() && !IfCmp2.conforms(this) &&
809        !(VM.BuildForIA32 &&
810            org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.conforms(this)) &&
811        !(VM.BuildForPowerPC &&
812            org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.conforms(this));
813  }
814
815  /**
816   * Is the instruction an unconditional intraprocedural branch?
817   * We consider various forms of switches to be unconditional
818   * intraprocedural branches, even though they are multi-way branches
819   * and we may not no exactly which target will be taken.
820   * This turns out to be the right thing to do, since some
821   * arm of the switch will always be taken (unlike conditional branches).
822   *
823   * @return <code>true</code> if the instruction is an unconditional
824   *         intraprocedural branch or <code>false</code> if it is not.
825   */
826  public boolean isUnconditionalBranch() {
827    return operator.isUnconditionalBranch();
828  }
829
830  /**
831   * Is the instruction a direct intraprocedural branch?
832   * In the HIR and LIR we consider switches to be direct branches,
833   * because their targets are known precisely.
834   *
835   * @return <code>true</code> if the instruction is a direct
836   *         intraprocedural branch or <code>false</code> if it is not.
837   */
838  public boolean isDirectBranch() {
839    return operator.isDirectBranch();
840  }
841
842  /**
843   * Is the instruction an indirect intraprocedural branch?
844   *
845   * @return <code>true</code> if the instruction is an indirect
846   *         interprocedural branch or <code>false</code> if it is not.
847   */
848  public boolean isIndirectBranch() {
849    return operator.isIndirectBranch();
850  }
851
852  /**
853   * Is the instruction a call (one kind of interprocedural branch)?
854   *
855   * @return <code>true</code> if the instruction is a call
856   *         or <code>false</code> if it is not.
857   */
858  public boolean isCall() {
859    return operator.isCall();
860  }
861
862  /**
863   * Is the instruction a pure call (one kind of interprocedural branch)?
864   *
865   * @return <code>true</code> if the instruction is a pure call
866   *         or <code>false</code> if it is not.
867   */
868  public boolean isPureCall() {
869    if (operator.isCall()) {
870      MethodOperand methOp = Call.getMethod(this);
871      if (methOp != null && methOp.hasPreciseTarget() && methOp.getTarget().isPure()) {
872        return true;
873      }
874    }
875    return false;
876  }
877
878  /**
879   * Is the instruction a call but not a pure call (one kind of interprocedural branch)?
880   *
881   * @return <code>true</code> if the instruction is a nonpure call
882   *         or <code>false</code> if it is not.
883   */
884  public boolean isNonPureCall() {
885    if (operator.isCall()) {
886      MethodOperand methOp = Call.getMethod(this);
887      boolean isPure = methOp != null && methOp.hasPreciseTarget() && methOp.getTarget().isPure();
888      return !isPure;
889    }
890    return false;
891  }
892
893  /**
894   * Is the instruction a conditional call?
895   * We only allow conditional calls in the MIR, since they
896   * tend to only be directly implementable on some architecutres.
897   *
898   * @return <code>true</code> if the instruction is a
899   *         conditional call or <code>false</code> if it is not.
900   */
901  public boolean isConditionalCall() {
902    return operator.isConditionalCall();
903  }
904
905  /**
906   * Is the instruction an unconditional call?
907   * Really only an interesting question in the MIR, since
908   * it is by definition true for all HIR and LIR calls.
909   *
910   * @return <code>true</code> if the instruction is an unconditional
911   *         call or <code>false</code> if it is not.
912   */
913  public boolean isUnconditionalCall() {
914    return operator.isUnconditionalCall();
915  }
916
917  /**
918   * Is the instruction a direct call?
919   * Only interesting on the MIR.  In the HIR and LIR we pretend that
920   * all calls are "direct" even though most of them aren't.
921   *
922   * @return <code>true</code> if the instruction is a direct call
923   *         or <code>false</code> if it is not.
924   */
925  public boolean isDirectCalll() {
926    return operator.isDirectCall();
927  }
928
929  /**
930   * Is the instruction an indirect call?
931   * Only interesting on the MIR.  In the HIR and LIR we pretend that
932   * all calls are "direct" even though most of them aren't.
933   *
934   * @return <code>true</code> if the instruction is an indirect call
935   *         or <code>false</code> if it is not.
936   */
937  public boolean isIndirectCall() {
938    return operator.isIndirectCall();
939  }
940
941  /**
942   * Is the instruction an explicit load of a finite set of values from
943   * a finite set of memory locations (load, load multiple, _not_ call)?
944   *
945   * @return <code>true</code> if the instruction is an explicit load
946   *         or <code>false</code> if it is not.
947   */
948  public boolean isExplicitLoad() {
949    return operator.isExplicitLoad();
950  }
951
952  /**
953   * Should the instruction be treated as a load from some unknown location(s)
954   * for the purposes of scheduling and/or modeling the memory subsystem?
955   *
956   * @return <code>true</code> if the instruction is an implicit load
957   *         or <code>false</code> if it is not.
958   */
959  public boolean isImplicitLoad() {
960    return operator.isImplicitLoad();
961  }
962
963  /**
964   * Is the instruction an explicit store of a finite set of values to
965   * a finite set of memory locations (store, store multiple, _not_ call)?
966   *
967   * @return <code>true</code> if the instruction is an explicit store
968   *         or <code>false</code> if it is not.
969   */
970  public boolean isExplicitStore() {
971    return operator.isExplicitStore();
972  }
973
974  /**
975   * Should the instruction be treated as a store to some unknown location(s)
976   * for the purposes of scheduling and/or modeling the memory subsystem?
977   *
978   * @return <code>true</code> if the instruction is an implicit store
979   *         or <code>false</code> if it is not.
980   */
981  public boolean isImplicitStore() {
982    return operator.isImplicitStore();
983  }
984
985  /**
986   * Is the instruction a throw of a Java exception?
987   *
988   * @return <code>true</code> if the instruction is a throw
989   *         or <code>false</code> if it is not.
990   */
991  public boolean isThrow() {
992    return operator.isThrow();
993  }
994
995  /**
996   * Is the instruction a PEI (Potentially Excepting Instruction)?
997   *
998   * @return <code>true</code> if the instruction is a PEI
999   *         or <code>false</code> if it is not.
1000   */
1001  public boolean isPEI() {
1002    // The operator level default may be overriden by instr specific info.
1003    if ((operatorInfo & OI_PEI_VALID) != 0) {
1004      return (operatorInfo & OI_PEI) != 0;
1005    } else {
1006      return operator.isPEI();
1007    }
1008  }
1009
1010  /**
1011   * Has the instruction been explictly marked as a a PEI (Potentially Excepting Instruction)?
1012   *
1013   * @return <code>true</code> if the instruction is explicitly marked as a PEI
1014   *         or <code>false</code> if it is not.
1015   */
1016  public boolean isMarkedAsPEI() {
1017    if ((operatorInfo & OI_PEI_VALID) != 0) {
1018      return (operatorInfo & OI_PEI) != 0;
1019    } else {
1020      return false;
1021    }
1022  }
1023
1024  /**
1025   * Is the instruction a potential GC point?
1026   *
1027   * @return <code>true</code> if the instruction is a potential
1028   *         GC point or <code>false</code> if it is not.
1029   */
1030  public boolean isGCPoint() {
1031    // The operator level default may be overridden by instr specific info.
1032    if ((operatorInfo & OI_GC_VALID) != 0) {
1033      return (operatorInfo & OI_GC) != 0;
1034    } else {
1035      return operator.isGCPoint();
1036    }
1037  }
1038
1039  /**
1040   * Is the instruction a potential thread switch point?
1041   *
1042   * @return <code>true</code> if the instruction is a potential
1043   *         thread switch point or <code>false</code> if it is not.
1044   */
1045  public boolean isTSPoint() {
1046    // Currently the same as asking if the instruction is a GCPoint, but
1047    // give it a separate name for documentation & future flexibility
1048    return isGCPoint();
1049  }
1050
1051  /**
1052   * Is the instruction a compare (val,val) =&gt; condition?
1053   *
1054   * @return <code>true</code> if the instruction is a compare
1055   *         or <code>false</code> if it is not.
1056   */
1057  public boolean isCompare() {
1058    return operator.isCompare();
1059  }
1060
1061  /**
1062   * Is the instruction an actual memory allocation instruction
1063   * (NEW, NEWARRAY, etc)?
1064   *
1065   * @return <code>true</code> if the instruction is an allocation
1066   *         or <code>false</code> if it is not.
1067   */
1068  public boolean isAllocation() {
1069    return operator.isAllocation();
1070  }
1071
1072  /**
1073   * Is the instruction a return (interprocedural branch)?
1074   *
1075   * @return <code>true</code> if the instruction is a return
1076   *         or <code>false</code> if it is not.
1077   */
1078  public boolean isReturn() {
1079    return operator.isReturn();
1080  }
1081
1082  /**
1083   * Is the instruction an acquire (monitorenter/lock)?
1084   *
1085   * @return <code>true</code> if the instruction is an acquire
1086   *         or <code>false</code> if it is not.
1087   */
1088  public boolean isAcquire() {
1089    return operator.isAcquire();
1090  }
1091
1092  /**
1093   * Is the instruction a release (monitorexit/unlock)?
1094   *
1095   * @return <code>true</code> if the instruction is a release
1096   *         or <code>false</code> if it is not.
1097   */
1098  public boolean isRelease() {
1099    return operator.isRelease();
1100  }
1101
1102  /**
1103   * Could the instruction either directly or indirectly
1104   * cause dynamic class loading?
1105   *
1106   * @return <code>true</code> if the instruction is a dynamic linking point
1107   *         or <code>false</code> if it is not.
1108   */
1109  public boolean isDynamicLinkingPoint() {
1110    return operator.isDynamicLinkingPoint();
1111  }
1112
1113  /**
1114   * Is the instruction a yield point?
1115   *
1116   * @return <code>true</code> if the instruction is a yield point
1117   *          or <code>false</code> if it is not.
1118   */
1119  public boolean isYieldPoint() {
1120    return operator.isYieldPoint();
1121  }
1122
1123  /**
1124   * Record that this instruction is not a PEI.
1125   * Leave GCPoint status (if any) unchanged.
1126   */
1127  public void markAsNonPEI() {
1128    operatorInfo &= ~OI_PEI;
1129    operatorInfo |= OI_PEI_VALID;
1130  }
1131
1132  private char getMIR_START_opcode() {
1133    if (VM.BuildForIA32) {
1134      return org.jikesrvm.compilers.opt.ir.ia32.ArchOperators.MIR_START_opcode;
1135    } else {
1136      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
1137      return org.jikesrvm.compilers.opt.ir.ppc.ArchOperators.MIR_START_opcode;
1138    }
1139  }
1140  /**
1141   * NOTE: ONLY FOR USE ON MIR INSTRUCTIONS!!!!
1142   * Record that this instruction is a PEI.
1143   * Note that marking as a PEI implies marking as GCpoint.
1144   */
1145  public void markAsPEI() {
1146    if (VM.VerifyAssertions) VM._assert(getOpcode() > getMIR_START_opcode());
1147    operatorInfo |= (OI_PEI_VALID | OI_PEI | OI_GC_VALID | OI_GC);
1148  }
1149
1150  /**
1151   * NOTE: ONLY FOR USE ON MIR INSTRUCTIONS!!!!
1152   * Record that this instruction does not represent a potential GC point.
1153   * Leave exception state (if any) unchanged.
1154   */
1155  public void markAsNonGCPoint() {
1156    if (VM.VerifyAssertions) VM._assert(getOpcode() > getMIR_START_opcode());
1157    operatorInfo &= ~OI_GC;
1158    operatorInfo |= OI_GC_VALID;
1159  }
1160
1161  /**
1162   * NOTE: ONLY FOR USE ON MIR INSTRUCTIONS!!!!
1163   * Record that this instruction is a potential GC point.
1164   * Leave PEI status (if any) unchanged.
1165   */
1166  public void markAsGCPoint() {
1167    if (VM.VerifyAssertions) VM._assert(getOpcode() > getMIR_START_opcode());
1168    operatorInfo |= (OI_GC_VALID | OI_GC);
1169  }
1170
1171  /**
1172   * NOTE: ONLY FOR USE ON MIR INSTRUCTIONS!!!!
1173   * Mark this instruction as being neither an exception or GC point.
1174   */
1175  public void markAsNonPEINonGCPoint() {
1176    if (VM.VerifyAssertions) VM._assert(getOpcode() > getMIR_START_opcode());
1177    operatorInfo &= ~(OI_PEI | OI_GC);
1178    operatorInfo |= (OI_PEI_VALID | OI_GC_VALID);
1179  }
1180
1181  /**
1182   * Return the probability (in the range 0.0 - 1.0) that this two-way
1183   * branch instruction is taken (as opposed to falling through).
1184   *
1185   * @return The probability that the branch is taken.
1186   */
1187  public float getBranchProbability() {
1188    if (VM.VerifyAssertions) VM._assert(isTwoWayBranch());
1189    return BranchProfileCarrier.getBranchProfile(this).takenProbability;
1190  }
1191
1192  /**
1193   * Record the probability (in the range 0.0 - 1.0) that this two-way
1194   * branch instruction is taken (as opposed to falling through).
1195   *
1196   * @param takenProbability    The probability that the branch is taken.
1197   */
1198  public void setBranchProbability(float takenProbability) {
1199    if (VM.VerifyAssertions) VM._assert(isTwoWayBranch());
1200    BranchProfileCarrier.getBranchProfile(this).takenProbability = takenProbability;
1201  }
1202
1203  /**
1204   * Invert the probabilty of this branch being taken.  This method
1205   * should be called on a branch instruction when its condition is
1206   * reversed using flipCode().
1207   */
1208  public void flipBranchProbability() {
1209    if (VM.VerifyAssertions) VM._assert(isTwoWayBranch());
1210    setBranchProbability(1.0f - getBranchProbability());
1211  }
1212
1213  /**
1214   * Returns the basic block jumped to by this BRANCH instruction.
1215   * TODO: Not all types of branches supported yet.
1216   *
1217   * @return the target of this branch instruction
1218   */
1219  public BasicBlock getBranchTarget() {
1220    switch (getOpcode()) {
1221      case GOTO_opcode:
1222        return Goto.getTarget(this).target.getBasicBlock();
1223
1224      case INT_IFCMP_opcode:
1225      case REF_IFCMP_opcode:
1226      case LONG_IFCMP_opcode:
1227      case FLOAT_IFCMP_opcode:
1228      case DOUBLE_IFCMP_opcode:
1229        return IfCmp.getTarget(this).target.getBasicBlock();
1230
1231      case IG_CLASS_TEST_opcode:
1232      case IG_METHOD_TEST_opcode:
1233      case IG_PATCH_POINT_opcode:
1234        return InlineGuard.getTarget(this).target.getBasicBlock();
1235
1236      default:
1237        if (VM.BuildForIA32) {
1238          if (org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.conforms(this)) {
1239            return org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.getTarget(this).target.getBasicBlock();
1240          } else if (org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.conforms(this)) {
1241            return org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.getTarget(this).target.getBasicBlock();
1242          }
1243        } else {
1244        if (org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.conforms(this)) {
1245          return org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.getTarget(this).target.getBasicBlock();
1246        } else if (org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.conforms(this)) {
1247          return org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.getTarget(this).target.getBasicBlock();
1248        }
1249      }
1250      throw new OptimizingCompilerException("getBranchTarget()",
1251                    "operator not implemented",
1252                    operator.toString());
1253    }
1254  }
1255
1256  /**
1257   * Return an enumeration of the basic blocks that are targets of this
1258   * branch instruction.
1259   *
1260   * @return the targets of this branch instruction
1261   */
1262  public Enumeration<BasicBlock> getBranchTargets() {
1263    int n = getNumberOfOperands();
1264    BasicBlock.ComputedBBEnum e = new BasicBlock.ComputedBBEnum(n);
1265
1266    switch (getOpcode()) {
1267      case GOTO_opcode: {
1268        BranchOperand tgt = Goto.getTarget(this);
1269        e.addElement(tgt.target.getBasicBlock());
1270      }
1271      break;
1272
1273      case INT_IFCMP2_opcode:
1274        e.addElement(IfCmp2.getTarget1(this).target.getBasicBlock());
1275        e.addPossiblyDuplicateElement(IfCmp2.getTarget2(this).target.getBasicBlock());
1276        break;
1277
1278      case INT_IFCMP_opcode:
1279      case REF_IFCMP_opcode:
1280      case LONG_IFCMP_opcode:
1281      case FLOAT_IFCMP_opcode:
1282      case DOUBLE_IFCMP_opcode:
1283        e.addElement(IfCmp.getTarget(this).target.getBasicBlock());
1284        break;
1285
1286      case IG_PATCH_POINT_opcode:
1287      case IG_CLASS_TEST_opcode:
1288      case IG_METHOD_TEST_opcode:
1289        e.addElement(InlineGuard.getTarget(this).target.getBasicBlock());
1290        break;
1291
1292      case TABLESWITCH_opcode:
1293        e.addElement(TableSwitch.getDefault(this).target.getBasicBlock());
1294        for (int i = 0; i < TableSwitch.getNumberOfTargets(this); i++) {
1295          e.addPossiblyDuplicateElement(TableSwitch.getTarget(this, i).target.getBasicBlock());
1296        }
1297        break;
1298
1299      case LOWTABLESWITCH_opcode:
1300        for (int i = 0; i < LowTableSwitch.getNumberOfTargets(this); i++) {
1301          e.addPossiblyDuplicateElement(LowTableSwitch.getTarget(this, i).target.getBasicBlock());
1302        }
1303        break;
1304
1305      case LOOKUPSWITCH_opcode:
1306        e.addElement(LookupSwitch.getDefault(this).target.getBasicBlock());
1307        for (int i = 0; i < LookupSwitch.getNumberOfTargets(this); i++) {
1308          e.addPossiblyDuplicateElement(LookupSwitch.getTarget(this, i).target.getBasicBlock());
1309        }
1310        break;
1311
1312      default:
1313
1314        if (VM.BuildForIA32 &&
1315            org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.conforms(this)) {
1316          e.addElement(org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.getTarget(this).target.getBasicBlock());
1317        } else if (VM.BuildForPowerPC &&
1318            org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.conforms(this)) {
1319          e.addElement(org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.getTarget(this).target.getBasicBlock());
1320        } else if (VM.BuildForIA32 &&
1321            org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.conforms(this)) {
1322          e.addElement(org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch.getTarget(this).target.getBasicBlock());
1323        } else if (VM.BuildForPowerPC &&
1324            org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.conforms(this)) {
1325          e.addElement(org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch.getTarget(this).target.getBasicBlock());
1326        } else if (VM.BuildForIA32 &&
1327            org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.conforms(this)) {
1328          e.addElement(org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.getTarget1(this).target.getBasicBlock());
1329          e.addPossiblyDuplicateElement(org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.getTarget2(this).target.getBasicBlock());
1330        } else if (VM.BuildForPowerPC &&
1331            org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.conforms(this)) {
1332          e.addElement(org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getTarget1(this).target.getBasicBlock());
1333          e.addPossiblyDuplicateElement(org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.getTarget2(this).target.getBasicBlock());
1334        } else if (VM.BuildForIA32 &&
1335            org.jikesrvm.compilers.opt.ir.ia32.MIR_LowTableSwitch.conforms(this)) {
1336          for (int i = 0; i < org.jikesrvm.compilers.opt.ir.ia32.MIR_LowTableSwitch.getNumberOfTargets(this); i++) {
1337            e.addPossiblyDuplicateElement(org.jikesrvm.compilers.opt.ir.ia32.MIR_LowTableSwitch.getTarget(this, i).
1338                target.getBasicBlock());
1339          }
1340        } else if ((VM.BuildForIA32 &&
1341            org.jikesrvm.compilers.opt.ir.ia32.MIR_CondBranch2.conforms(this)) ||
1342            (VM.BuildForPowerPC &&
1343             org.jikesrvm.compilers.opt.ir.ppc.MIR_CondBranch2.conforms(this))) {
1344          throw new OptimizingCompilerException("getBranchTargets()",
1345                                                    "operator not implemented",
1346                                                    operator().toString());
1347        } else {
1348          throw new OptimizingCompilerException("getBranchTargets()",
1349                                                    "operator not implemented",
1350                                                    operator().toString());
1351        }
1352    }
1353
1354    return e;
1355  }
1356
1357  /**
1358   * Return {@code true} if this instruction is the first instruction in a
1359   * basic block.  By convention (construction) every basic block starts
1360   * with a label instruction and a label instruction only appears at
1361   * the start of a basic block
1362   *
1363   * @return <code>true</code> if the instruction is the first instruction
1364   *         in its basic block or <code>false</code> if it is not.
1365   */
1366  public boolean isBbFirst() {
1367    return operator == LABEL;
1368  }
1369
1370  /**
1371   * Return {@code true} if this instruction is the last instruction in a
1372   * basic block.  By convention (construction) every basic block ends
1373   * with a BBEND instruction and a BBEND instruction only appears at the
1374   * end of a basic block
1375   *
1376   * @return <code>true</code> if the instruction is the last instruction
1377   *         in its basic block or <code>false</code> if it is not.
1378   */
1379  public boolean isBbLast() {
1380    return operator == BBEND;
1381  }
1382
1383  /**
1384   * Mainly intended for assertion checking;  returns true if the instruction
1385   * is expected to appear on the "inside" of a basic block, false otherwise.
1386   *
1387   * @return <code>true</code> if the instruction is expected to appear
1388   *         on the inside (not first or last) of its basic block
1389   *         or <code>false</code> if it is expected to be a first/last
1390   *         instruction.
1391   */
1392  public boolean isBbInside() {
1393    return !(operator == LABEL || operator == BBEND);
1394  }
1395
1396  /*
1397  * Primitive Instruction List manipulation routines.
1398  * All of these operations assume that the IR invariants
1399  * (mostly well-formedness of the data structures) are true
1400  * when they are invoked.
1401  * Effectively, the IR invariants are defined by IR.verify().
1402  * These primitive functions will locally check their invariants
1403  * when IR.PARANOID is true.
1404  * If the precondition is met, then the IR invariants will be true when
1405  * the operation completes.
1406  */
1407
1408  /**
1409   * Insertion: Insert newInstr immediately after this in the
1410   * instruction stream.
1411   * Can't insert after a BBEND instruction, since it must be the last
1412   * instruction in its basic block.
1413   *
1414   * @param newInstr the instruction to insert, must not be in an
1415   *                 instruction list already.
1416   */
1417  public void insertAfter(Instruction newInstr) {
1418    if (IR.PARANOID) {
1419      isForwardLinked();
1420      newInstr.isNotLinked();
1421      VM._assert(!isBbLast(), "cannot insert after last instruction of block");
1422    }
1423
1424    // set position unless someone else has
1425    if (newInstr.position == null) {
1426      newInstr.position = position;
1427      newInstr.bcIndex = bcIndex;
1428    }
1429
1430    // Splice newInstr into the doubly linked list of instructions
1431    Instruction old_next = next;
1432    next = newInstr;
1433    newInstr.prev = this;
1434    newInstr.next = old_next;
1435    old_next.prev = newInstr;
1436  }
1437
1438  /**
1439   * Insertion: Insert newInstr immediately before this in the
1440   * instruction stream.
1441   * Can't insert before a LABEL instruction, since it must be the first
1442   * instruction in its basic block.
1443   *
1444   * @param newInstr the instruction to insert, must not be in
1445   *                 an instruction list already.
1446   */
1447  public void insertBefore(Instruction newInstr) {
1448    if (IR.PARANOID) {
1449      isBackwardLinked();
1450      newInstr.isNotLinked();
1451      VM._assert(!isBbFirst(), "Cannot insert before first instruction of block");
1452    }
1453
1454    // set position unless someone else has
1455    if (newInstr.position == null) {
1456      newInstr.position = position;
1457      newInstr.bcIndex = bcIndex;
1458    }
1459
1460    // Splice newInstr into the doubly linked list of instructions
1461    Instruction old_prev = prev;
1462    prev = newInstr;
1463    newInstr.next = this;
1464    newInstr.prev = old_prev;
1465    old_prev.next = newInstr;
1466  }
1467
1468  /**
1469   * Replacement: Replace this with newInstr.
1470   * We could allow replacement of first &amp; last instrs in the basic block,
1471   * but it would be a fair amount of work to update everything, and probably
1472   * isn't useful, so we'll simply disallow it for now.
1473   *
1474   * @param newInstr  the replacement instruction must not be in an
1475   *                  instruction list already and must not be a
1476   *                  LABEL or BBEND instruction.
1477   */
1478  public void replace(Instruction newInstr) {
1479    if (IR.PARANOID) {
1480      isLinked();
1481      newInstr.isNotLinked();
1482      VM._assert(isBbInside(), "Can only replace BbInside instructions");
1483    }
1484
1485    Instruction old_prev = prev;
1486    Instruction old_next = next;
1487
1488    // Splice newInstr into the doubly linked list of instructions
1489    newInstr.prev = old_prev;
1490    old_prev.next = newInstr;
1491    newInstr.next = old_next;
1492    old_next.prev = newInstr;
1493    next = null;
1494    prev = null;
1495  }
1496
1497  /**
1498   * Removal: Remove this from the instruction stream.
1499   *
1500   *  We currently forbid the removal of LABEL instructions to avoid
1501   *  problems updating branch instructions that reference the label.
1502   *  We also outlaw removal of BBEND instructions.
1503   *  <p>
1504   *  NOTE: We allow the removal of branch instructions, but don't update the
1505   *  CFG data structure.....right now we just assume the caller knows what
1506   *  they are doing and takes care of it.
1507   *  <p>
1508   *  NB: execution of this method nulls out the prev &amp; next fields of this
1509   *
1510   * @return the previous instruction in the instruction stream
1511   */
1512  public Instruction remove() {
1513    if (IR.PARANOID) {
1514      isLinked();
1515      VM._assert(!isBbFirst() && !isBbLast(), "Removal of first/last instructions in block not supported");
1516    }
1517
1518    // Splice this out of instr list
1519    Instruction Prev = prev, Next = next;
1520    Prev.next = Next;
1521    Next.prev = Prev;
1522    next = null;
1523    prev = null;
1524    return Prev;
1525  }
1526
1527  /*
1528   * Helper routines to verify instruction list invariants.
1529   * Invocations to these functions are guarded by IR.PARANOID and thus
1530   * the calls to VM.Assert don't need to be guarded by VM.VerifyAssertions.
1531   */
1532
1533  // Our Checkstyle assertion plugin does not handle this case because that
1534  // would require tracking all calls. Therefore, switch off checkstyle for
1535  // the affected methods.
1536
1537  //CHECKSTYLE:OFF
1538
1539  private void isLinked() {
1540    VM._assert(prev.next == this, "is_linked: failure (1)");
1541    VM._assert(next.prev == this, "is_linked: failure (2)");
1542  }
1543
1544  private void isBackwardLinked() {
1545    VM._assert(prev.next == this, "is_backward_linked: failure (1)");
1546    // OK if next is null (IR under construction)
1547    VM._assert(next == null || next.prev == this, "is_backward_linked: failure (2)");
1548  }
1549
1550  private void isForwardLinked() {
1551    // OK if prev is null (IR under construction)
1552    VM._assert(prev == null || prev.next == this, "is_forward_linked: failure (1)");
1553    VM._assert(next.prev == this, "is_forward_linked (2)");
1554  }
1555
1556  private void isNotLinked() {
1557    VM._assert(prev == null && next == null, "is_not_linked: failure (1)");
1558  }
1559
1560  //CHECKSTYLE:ON
1561
1562  /*
1563  * Implementation: Operand enumeration classes
1564  */
1565  /** Shared functionality for operand enumerations */
1566  private abstract static class BASE_OE implements Enumeration<Operand> {
1567    protected final Instruction instr;
1568    protected int i;
1569    protected final int end;
1570    protected Operand nextElem;
1571    protected static final boolean DEBUG = false;
1572
1573    protected BASE_OE(Instruction instr, int start, int end) {
1574      this.instr = instr;
1575      this.i = start - 1;
1576      this.end = end;
1577      this.nextElem = null;
1578    }
1579
1580    @Override
1581    public final boolean hasMoreElements() {
1582      return nextElem != null;
1583    }
1584
1585    @Override
1586    public final Operand nextElement() {
1587      Operand temp = nextElem;
1588      if (temp == null) fail();
1589      advance();
1590      if (DEBUG) {
1591        System.out.println(" next() returning: " + temp);
1592      }
1593      return temp;
1594    }
1595
1596    protected abstract void advance();
1597
1598    @NoInline
1599    private static void fail() {
1600      throw new java.util.NoSuchElementException("OperandEnumerator");
1601    }
1602  }
1603
1604  /** enumerate leaf operands in the given ranges */
1605  private static final class OE extends BASE_OE {
1606    private final int defEnd;
1607    private Operand deferredMOReg;
1608
1609    OE(Instruction instr, int start, int end, int defEnd) {
1610      super(instr, start, end);
1611      this.defEnd = defEnd;
1612      if (DEBUG) {
1613        System.out.println(" --> OE called with inst\n" +
1614                           instr +
1615                           "\n start: " +
1616                           start +
1617                           ", end: " +
1618                           end +
1619                           ", defEnd: " +
1620                           defEnd);
1621      }
1622      advance();
1623    }
1624
1625    @Override
1626    protected void advance() {
1627      if (deferredMOReg != null) {
1628        nextElem = deferredMOReg;
1629        deferredMOReg = null;
1630      } else {
1631        Operand temp;
1632        do {
1633          i++;
1634          if (i > end) {
1635            temp = null;
1636            break;
1637          }
1638          temp = instr.getOperand(i);
1639          if (temp instanceof MemoryOperand) {
1640            MemoryOperand mo = (MemoryOperand) temp;
1641            if (mo.base != null) {
1642              temp = mo.base;
1643              deferredMOReg = mo.index;
1644              break;
1645            } else {
1646              temp = mo.index;
1647            }
1648          } else {
1649            if (i <= defEnd) {
1650              // if i is in the defs, ignore non memory operands
1651              temp = null;
1652            }
1653          }
1654        } while (temp == null);
1655        nextElem = temp;
1656      }
1657    }
1658  }
1659
1660  /**
1661   * Enumerate the def operands of an instruction (ignores memory
1662   * operands, since the contained operands of a MO are uses).
1663   */
1664  private static final class OEDefsOnly extends BASE_OE {
1665    OEDefsOnly(Instruction instr, int start, int end) {
1666      super(instr, start, end);
1667      if (DEBUG) {
1668        System.out.println(" --> OEDefsOnly called with inst\n" + instr + "\n start: " + start + ", end: " + end);
1669      }
1670      advance();
1671    }
1672
1673    @Override
1674    protected void advance() {
1675      Operand temp;
1676      do {
1677        i++;
1678        if (i > end) {
1679          temp = null;
1680          break;
1681        }
1682        temp = instr.getOperand(i);
1683      } while (temp == null || temp instanceof MemoryOperand);
1684      nextElem = temp;
1685      // (i>end and nextElem == null) or nextElem is neither memory nor null
1686    }
1687  }
1688
1689  /** Enumerate the memory operands of an instruction */
1690  private static final class MOE extends BASE_OE {
1691    MOE(Instruction instr, int start, int end) {
1692      super(instr, start, end);
1693      if (DEBUG) {
1694        System.out.println(" --> MOE called with inst\n" + instr + "\n start: " + start + ", end: " + end);
1695      }
1696      advance();
1697    }
1698
1699    @Override
1700    protected void advance() {
1701      Operand temp;
1702      do {
1703        i++;
1704        if (i > end) {
1705          temp = null;
1706          break;
1707        }
1708        temp = instr.getOperand(i);
1709      } while (!(temp instanceof MemoryOperand));
1710      nextElem = temp;
1711      // (i>end and nextElem == null) or nextElem is memory
1712    }
1713  }
1714
1715  /** Enumerate the root operands of an instruction */
1716  private static final class ROE extends BASE_OE {
1717    ROE(Instruction instr, int start, int end) {
1718      super(instr, start, end);
1719      if (DEBUG) {
1720        System.out.println(" --> ROE called with inst\n" + instr + "\n start: " + start + ", end: " + end);
1721      }
1722      advance();
1723    }
1724
1725    @Override
1726    protected void advance() {
1727      Operand temp;
1728      do {
1729        i++;
1730        if (i > end) {
1731          temp = null;
1732          break;
1733        }
1734        temp = instr.getOperand(i);
1735      } while (temp == null);
1736      nextElem = temp;
1737      // (i>end and nextElem == null) or nextElem != null
1738    }
1739  }
1740
1741  /*
1742  * The following operand functions are really only meant to be
1743  * used in the classes (such as instruction formats) that
1744  * collaborate in the low-level implementation of the IR.
1745  * General clients are strongly discouraged from using them.
1746  */
1747
1748  /**
1749   * NOTE: It is incorrect to use getOperand with a constant argument
1750   * outside of the automatically generated code in Operators.
1751   * The only approved direct use of getOperand is in a loop over
1752   * some subset of an instructions operands (all of them, all uses, all defs).
1753   *
1754   * @param i which operand to return
1755   * @return the ith operand
1756   */
1757  public Operand getOperand(int i) {
1758    return ops[i];
1759  }
1760
1761  /**
1762   * NOTE: It is incorrect to use getClearOperand with a constant argument
1763   * outside of the automatically generated code in Operators.
1764   * The only approved direct use of getOperand is in a loop over
1765   * some subset of an instructions operands (all of them, all uses, all defs).
1766   *
1767   * @param i which operand to return
1768   * @return the ith operand detatching it from the instruction
1769   */
1770  public Operand getClearOperand(int i) {
1771    Operand o = ops[i];
1772    if (o != null) {
1773      o.instruction = null;
1774    }
1775    ops[i] = null;
1776    return o;
1777  }
1778
1779  /**
1780   * NOTE: It is incorrect to use putOperand with a constant argument
1781   * outside of the automatically generated code in Operators.
1782   * The only approved direct use of getOperand is in a loop over
1783   * some subset of an instruction's operands (all of them, all uses, all defs).
1784   *
1785   * @param i which operand to set
1786   * @param op the operand to set it to
1787   */
1788  public void putOperand(int i, Operand op) {
1789    if (op == null) {
1790      ops[i] = null;
1791    } else {
1792      // TODO: Replace this silly copying code with an assertion that operands
1793      //       are not shared between instructions and force people to be
1794      //       more careful!
1795      if (op.instruction != null) {
1796        op = outOfLineCopy(op);
1797      }
1798      op.instruction = this;
1799      ops[i] = op;
1800      if (op instanceof MemoryOperand) {
1801        MemoryOperand mOp = op.asMemory();
1802        op = mOp.loc;
1803        if (op != null) op.instruction = this;
1804        op = mOp.guard;
1805        if (op != null) op.instruction = this;
1806        op = mOp.base;
1807        if (op != null) op.instruction = this;
1808        op = mOp.index;
1809        if (op != null) op.instruction = this;
1810      }
1811    }
1812  }
1813
1814  @NoInline
1815  private Operand outOfLineCopy(Operand op) {
1816    return op.copy();
1817  }
1818
1819  /**
1820   * Enlarge the number of operands in this instruction, if necessary.
1821   * Only meant to be used by InstructionFormat classes.
1822   *
1823   * @param newSize the new minimum number of operands.
1824   */
1825  public void resizeNumberOfOperands(int newSize) {
1826    int oldSize = ops.length;
1827    if (oldSize != newSize) {
1828      Operand[] newOps = new Operand[newSize];
1829      int min = oldSize;
1830      if (newSize < oldSize) {
1831        min = newSize;
1832      }
1833      for (int i = 0; i < min; i++) {
1834        newOps[i] = ops[i];
1835      }
1836      ops = newOps;
1837    }
1838  }
1839
1840  /**
1841   * For IR internal use only; general clients should use
1842   * {@link #nextInstructionInCodeOrder()}.
1843   *
1844   * @return the contents of {@link #next}
1845   */
1846  Instruction getNext() {
1847    return next;
1848  }
1849
1850  /**
1851   * For IR internal use only;   general clients should always use higer level
1852   * mutation functions.
1853   * Set the {@link #next} field of the instruction.
1854   *
1855   * @param n the new value for next
1856   */
1857  void setNext(Instruction n) {
1858    next = n;
1859  }
1860
1861  /**
1862   * For IR internal use only; General clients should use
1863   * {@link #prevInstructionInCodeOrder()}.
1864   *
1865   * @return the contents of {@link #prev}
1866   */
1867  Instruction getPrev() {
1868    return prev;
1869  }
1870
1871  /**
1872   * For IR internal use only;   general clients should always use higer level
1873   * mutation functions.
1874   * Set the {@link #prev} field of the instruction.
1875   *
1876   * @param p the new value for prev
1877   */
1878  void setPrev(Instruction p) {
1879    prev = p;
1880  }
1881
1882  /**
1883   * For IR internal use only;   general clients should always use higer level
1884   * mutation functions.
1885   * Clear the {@link #prev} and {@link #next} fields of the instruction.
1886   */
1887  void clearLinks() {
1888    next = null;
1889    prev = null;
1890  }
1891
1892  /**
1893   * Are two instructions similar, i.e. having the same operator and
1894   * the same number of similar operands?
1895   * @param similarInstr instruction to compare against
1896   * @return true if they are similar
1897   */
1898  public boolean similar(Instruction similarInstr) {
1899    if (similarInstr.operator != operator) {
1900      return false;
1901    } else {
1902      int num_operands = getNumberOfOperands();
1903      if (similarInstr.getNumberOfOperands() != num_operands) {
1904        return false;
1905      } else {
1906        for (int i = 0; i < num_operands; i++) {
1907          Operand op1 = getOperand(i);
1908          Operand op2 = similarInstr.getOperand(i);
1909          if ((op1 == null) && (op2 == null)) {
1910            return true;
1911          }
1912          if ((op1 == null) || (op2 == null) || !op1.similar(op2)) {
1913            return false;
1914          }
1915        }
1916        return true;
1917      }
1918    }
1919  }
1920
1921  /**
1922   * For IR internal use only;   general clients should always use higer level
1923   * mutation functions.
1924   * Link this and other together by setting this's {@link #next} field to
1925   * point to other and other's {@link #prev} field to point to this.
1926   *
1927   * @param other the instruction to link with.
1928   */
1929  void linkWithNext(Instruction other) {
1930    next = other;
1931    other.prev = this;
1932  }
1933
1934  /**
1935   * Allow BURS a back door into linkWithNext. This method should only be called
1936   * within BURS.
1937   *
1938   * @param other the next instruction
1939   */
1940  public void BURS_backdoor_linkWithNext(Instruction other) {
1941    linkWithNext(other);
1942  }
1943
1944  /**
1945   * Might this instruction be a load from a field that is declared
1946   * to be volatile?
1947   *
1948   * @return <code>true</code> if the instruction might be a load
1949   *         from a volatile field or <code>false</code> if it
1950   *         cannot be a load from a volatile field
1951   */
1952  public boolean mayBeVolatileFieldLoad() {
1953    if (LocalCSE.isLoadInstruction(this)) {
1954      return LocationCarrier.getLocation(this).mayBeVolatile();
1955    }
1956    return false;
1957  }
1958
1959}