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