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