Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.jikesrvm.compilers.opt.ir
Class IR

java.lang.Object
  extended by org.jikesrvm.compilers.opt.ir.IR

public final class IR
extends Object

An IR object (IR is short for Intermediate Representation) contains all the per-compilation information associated with a method that is being compiled.

IR objects are intended to be transitory. They are created to compile a particular method under a given compilation plan and are discarded once the compilation plan has been completed.

The primary component of the IR is the FCFG (factored control flow graph) The FCFG contains intermediate language instructions grouped into factored basic blocks. In addition to the FCFG, an IR object also contains a variety of other supporting and derived data structures.

See Also:
ControlFlowGraph, BasicBlock, Instruction, Operator, Operand

Nested Class Summary
private static class IR.BitSetBBEnum
           
 
Field Summary
 SSAOptions actualSSAOptions
          Options that define the SSA properties currently carried by the IR.
private  BasicBlock[] basicBlockMap
          Backing store for getBasicBlock(int).
 ControlFlowGraph cfg
          The FCFG (Factored Control Flow Graph)
 OptCompiledMethod compiledMethod
          The compiled method created to hold the result of this compilation.
 SSAOptions desiredSSAOptions
          Options that define the SSA properties desired the next time we enter SSA form.
 GenerationContext gc
          The root generation context for the current compilation.
private  boolean handlerLivenessComputed
          Was liveness for handlers computed?
private  boolean hasSysCall
          Does this IR include a syscall?
static byte HIR
          Part of an enumerated type used to encode IR Level
 HIRInfo HIRInfo
          Pointer to the HIRInfo for this method.
 InlineOracle inlinePlan
          The inlining oracle to be used for the current compilation.
 InstrumentationPlan instrumentationPlan
          Information specifying what instrumentation should be performed during compilation of this method.
 byte IRStage
          The IR is tagged to identify its level (stage).
static byte LIR
          Part of an enumerated type used to encode IR Level
 LIRInfo LIRInfo
          Pointer to the LIRInfo for this method.
 NormalMethod method
          The NormalMethod object corresponding to the method being compiled.
static byte MIR
          Part of an enumerated type used to encode IR Level
 MIRInfo MIRInfo
          Pointer to the MIRInfo for this method.
 OptOptions options
          The compiler options that apply to the current compilation.
 TypeReference[] params
          The specialized parameters to be used in place of those defined in the NormalMethod.
static boolean PARANOID
          Control for (dynamic) IR invariant checking.
 ArchitectureSpecificOpt.RegisterPool regpool
          The Register pool
static boolean SANITY_CHECK
          Control for (dynamic) IR invariant checking.
 GenericStackManager stackManager
          The stack manager.
static byte UNFORMED
          Part of an enumerated type used to encode IR Level
 
Constructor Summary
IR(NormalMethod m, CompilationPlan cp)
           
IR(NormalMethod m, InlineOracle ip, OptOptions opts)
           
 
Method Summary
 void clearBasicBlockScratchObject()
          Clear (set to null) the scratch object on all basic blocks currently in this IR.
 void clearInstructionScratchObject()
          Clear (set to null) the scratch object on all instructions currently in this IR.
 void clearInstructionScratchWord()
          Clear (set to zero) the scratch word on all instructions currently in this IR.
 BasicBlock firstBasicBlockInCodeOrder()
          Return the first basic block with respect to the current code linearization order.
 Instruction firstInstructionInCodeOrder()
          Return the first instruction with respect to the current code linearization order.
 Enumeration<BasicBlock> forwardBlockEnumerator()
          Forward (with respect to the current code linearization order) iteration overal all the basic blocks in the IR.
 Enumeration<Instruction> forwardInstrEnumerator()
          Forward (with respect to the current code linearization order) iteration over all the instructions in this IR.
 BasicBlock getBasicBlock(int number)
          Get the basic block with a given number.
 Enumeration<BasicBlock> getBasicBlocks()
          Enumerate the basic blocks in the IR in an arbitrary order.
 Enumeration<BasicBlock> getBasicBlocks(BitVector bits)
          Get an enumeration of all the basic blocks whose numbers appear in the given BitSet.
 boolean getHandlerLivenessComputed()
          States whether liveness for handlers is available & @return whether liveness for handlers is available
 int getMaxBasicBlockNumber()
           
 NormalMethod getMethod()
           
 int getNumberOfSymbolicRegisters()
          Return the number of symbolic registers for this IR
 Enumeration<Operand> getParameters()
          Return an enumeration of the parameters to the IR Warning: Only valid before register allocation (see CallingConvention)
private  Object getVariableDef(String where, Operand operand)
          Get the variable defined by this operand
private  Object getVariableUse(String where, Operand operand)
          Get the variable used by this operand
 boolean hasReachableExceptionHandlers()
           
 boolean hasSysCall()
           
 int incomingParameterBytes()
          How many bytes of parameters does this method take?
 boolean inSSAForm()
          Are we in SSA form?
 boolean inSSAFormAwaitingReEntry()
          Are we in SSA form that's broken awaiting re-entry?
 boolean isParameter(Operand op)
          Is the operand a parameter of the IR?
 BasicBlock lastBasicBlockInCodeOrder()
          Return the last basic block with respect to the current code linearization order.
 Instruction lastInstructionInCodeOrder()
          Return the last instruction with respect to the current code linearization order.
 int numberInstructions()
          Densely number all the instructions currently in this IR from 0...numInstr-1.
 void printInstructions()
          Print the instructions in this IR to System.out.
 void pruneExceptionalOut()
          Prune the exceptional out edges for each basic block in the IR.
 void resetBasicBlockMap()
          Recompute the basic block map, so can use getBasicBlock(int) to index into the basic blocks quickly.
 Enumeration<BasicBlock> reverseBlockEnumerator()
          Reverse (with respect to the current code linearization order) iteration overal all the basic blocks in the IR.
 Enumeration<Instruction> reverseInstrEnumerator()
          Reverse (with respect to the current code linearization order) iteration over all the instructions in this IR.
 void setHandlerLivenessComputed(boolean value)
          Record whether or not liveness information for handlers is available
 void setHasSysCall(boolean b)
           
 void setInstructionScratchWord(int value)
          Set the scratch word on all instructions currently in this IR to a given value.
 boolean strictFP(Instruction... is)
          Should strictfp be adhered to for the given instructions?
 void unfactor()
          Partially convert the FCFG into a more traditional CFG by splitting all nodes that contain PEIs and that have reachable exception handlers into multiple basic blocks such that the instructions in the block have the expected post-dominance relationship.
 void verify(String where)
          Verify that the IR is well-formed.
 void verify(String where, boolean checkCFG)
          Verify that the IR is well-formed.
private  void verifyAllBlocksAreReachable(String where)
          Verify that every block in the CFG is reachable as failing to do so will cause EnterSSA.insertPhiFunctions to possibly access elements in DominanceFrontier.getIteratedDominanceFrontier and then DominanceFrontier.getDominanceFrontier that aren't defined.
private  void verifyAllBlocksAreReachable(String where, BasicBlock curBB, BitVector visitedNormalBBs, BitVector visitedExceptionalBBs, boolean fromExceptionEdge)
          Verify that every block in the CFG is reachable as failing to do so will cause EnterSSA.insertPhiFunctions to possibly access elements in DominanceFrontier.getIteratedDominanceFrontier and then DominanceFrontier.getDominanceFrontier that aren't defined.
private  void verifyBBConstruction(String where)
          Verify basic block construction from the basic block and instruction information.
private  void verifyCFG(String where)
          Verify control flow graph construction
private  void verifyInstructions(String where)
          Verify that every instruction: 1) has operands that back reference it 2) is valid for its position in the basic block 3) if we are MIR, has no guard operands
private  void verifyRegisterDefs(String where)
          Verify that every non-physical, non-parameter symbolic register that has a use also has at least one def
private  void verifyRegisterTypes(String where)
          Verify that no register is used as a long type and an int type PRECONDITION: register lists computed
private  void verifyUseFollowsDef(String where)
          Check whether uses follow definitions and that in SSA form variables aren't multiply defined
private  void verifyUseFollowsDef(String where, HashSet<Object> definedVariables, BasicBlock curBB, BitVector visitedBBs, ArrayList<BasicBlock> path, int maxPathLength, boolean traceExceptionEdges)
          Check whether uses follow definitions and in SSA form that variables aren't multiply defined
private  void verror(String where, String msg)
          Generate error
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

SANITY_CHECK

public static final boolean SANITY_CHECK
Control for (dynamic) IR invariant checking. By default, SANITY_CHECK == Configuration.VerifyAssertions. When SANITY_CHECK is true, critical invariants are checked by complex routines that depend on them, and verify is invoked several times during compilation.

See Also:
Constant Field Values

PARANOID

public static final boolean PARANOID
Control for (dynamic) IR invariant checking. By default PARANOID is false. PARANOID must not be true unless Configuration.VerifyAssertions is also true. When PARANOID is true many IR utility functions check the invariants on which they depend, and verify(String,boolean) is invoked as each compilation phase is performed.

See Also:
Constant Field Values

UNFORMED

public static final byte UNFORMED
Part of an enumerated type used to encode IR Level

See Also:
Constant Field Values

HIR

public static final byte HIR
Part of an enumerated type used to encode IR Level

See Also:
Constant Field Values

LIR

public static final byte LIR
Part of an enumerated type used to encode IR Level

See Also:
Constant Field Values

MIR

public static final byte MIR
Part of an enumerated type used to encode IR Level

See Also:
Constant Field Values

method

public final NormalMethod method
The NormalMethod object corresponding to the method being compiled. Other methods may have been inlined into the IR during compilation, so method really only represents the primary or outermost method being compiled.

params

public final TypeReference[] params
The specialized parameters to be used in place of those defined in the NormalMethod.

compiledMethod

public final OptCompiledMethod compiledMethod
The compiled method created to hold the result of this compilation.

options

public final OptOptions options
The compiler options that apply to the current compilation.

desiredSSAOptions

public SSAOptions desiredSSAOptions
Options that define the SSA properties desired the next time we enter SSA form.

actualSSAOptions

public SSAOptions actualSSAOptions
Options that define the SSA properties currently carried by the IR. Compiler phases that are invoked on SSA form should update this object to reflect transformations on SSA form.

gc

public GenerationContext gc
The root generation context for the current compilation.

inlinePlan

public final InlineOracle inlinePlan
The inlining oracle to be used for the current compilation. TODO: It would make more sense to have the inlining oracle be a component of the generation context, but as things currently stand the IR is created before the generation context. We might be able to restructure things such that the generation context is created in the IR constructor and then eliminate this field, replacing all uses with gc.inlinePlan instead.

instrumentationPlan

public final InstrumentationPlan instrumentationPlan
Information specifying what instrumentation should be performed during compilation of this method.

cfg

public ControlFlowGraph cfg
The FCFG (Factored Control Flow Graph)

regpool

public ArchitectureSpecificOpt.RegisterPool regpool
The Register pool

stackManager

public final GenericStackManager stackManager
The stack manager.

IRStage

public byte IRStage
The IR is tagged to identify its level (stage). As compilation continues, the level monotonically increases from UNFORMED to HIR to LIR to MIR.

handlerLivenessComputed

private boolean handlerLivenessComputed
Was liveness for handlers computed?

HIRInfo

public HIRInfo HIRInfo
Pointer to the HIRInfo for this method. Valid only if IRStage>=HIR

LIRInfo

public LIRInfo LIRInfo
Pointer to the LIRInfo for this method. Valid only if IRStage>=LIR.

MIRInfo

public MIRInfo MIRInfo
Pointer to the MIRInfo for this method. Valid only if IRStage>=MIR.

basicBlockMap

private BasicBlock[] basicBlockMap
Backing store for getBasicBlock(int).

hasSysCall

private boolean hasSysCall
Does this IR include a syscall? Initialized during lir to mir conversion;

Constructor Detail

IR

public IR(NormalMethod m,
          InlineOracle ip,
          OptOptions opts)
Parameters:
m - The method to compile
ip - The inlining oracle to use for the compilation
opts - The options to use for the compilation

IR

public IR(NormalMethod m,
          CompilationPlan cp)
Parameters:
m - The method to compile
cp - The compilation plan to execute
Method Detail

getMethod

public NormalMethod getMethod()
Returns:
The NormalMethod object corresponding to the method being compiled. Other methods may have been inlined into the IR during compilation, so method really only represents the primary or outermost method being compiled.

inSSAForm

public boolean inSSAForm()
Are we in SSA form?

inSSAFormAwaitingReEntry

public boolean inSSAFormAwaitingReEntry()
Are we in SSA form that's broken awaiting re-entry?

hasSysCall

public boolean hasSysCall()

setHasSysCall

public void setHasSysCall(boolean b)

printInstructions

public void printInstructions()
Print the instructions in this IR to System.out.

strictFP

public boolean strictFP(Instruction... is)
Should strictfp be adhered to for the given instructions?

firstInstructionInCodeOrder

public Instruction firstInstructionInCodeOrder()
Return the first instruction with respect to the current code linearization order.

Returns:
the first instruction in the code order

lastInstructionInCodeOrder

public Instruction lastInstructionInCodeOrder()
Return the last instruction with respect to the current code linearization order.

Returns:
the last instruction in the code order

firstBasicBlockInCodeOrder

public BasicBlock firstBasicBlockInCodeOrder()
Return the first basic block with respect to the current code linearization order.

Returns:
the first basic block in the code order

lastBasicBlockInCodeOrder

public BasicBlock lastBasicBlockInCodeOrder()
Return the last basic block with respect to the current code linearization order.

Returns:
the last basic block in the code order

forwardInstrEnumerator

public Enumeration<Instruction> forwardInstrEnumerator()
Forward (with respect to the current code linearization order) iteration over all the instructions in this IR. The IR must not be modified during the iteration.

Returns:
an enumeration that enumerates the instructions in forward code order.

reverseInstrEnumerator

public Enumeration<Instruction> reverseInstrEnumerator()
Reverse (with respect to the current code linearization order) iteration over all the instructions in this IR. The IR must not be modified during the iteration.

Returns:
an enumeration that enumerates the instructions in reverse code order.

getBasicBlocks

public Enumeration<BasicBlock> getBasicBlocks()
Enumerate the basic blocks in the IR in an arbitrary order.

Returns:
an enumeration of BasicBlocks that enumerates the basic blocks in an arbitrary order.

forwardBlockEnumerator

public Enumeration<BasicBlock> forwardBlockEnumerator()
Forward (with respect to the current code linearization order) iteration overal all the basic blocks in the IR.

Returns:
an enumeration of BasicBlocks that enumerates the basic blocks in forward code order.

reverseBlockEnumerator

public Enumeration<BasicBlock> reverseBlockEnumerator()
Reverse (with respect to the current code linearization order) iteration overal all the basic blocks in the IR.

Returns:
an enumeration of BasicBlocks that enumerates the basic blocks in reverse code order.

getParameters

public Enumeration<Operand> getParameters()
Return an enumeration of the parameters to the IR Warning: Only valid before register allocation (see CallingConvention)

Returns:
the parameters of the IR.

isParameter

public boolean isParameter(Operand op)
Is the operand a parameter of the IR? Warning: Only valid before register allocation (see CallingConvention)

Parameters:
op - the operand to check
Returns:
true if the op is a parameter to the IR, false otherwise

incomingParameterBytes

public int incomingParameterBytes()
How many bytes of parameters does this method take?

resetBasicBlockMap

public void resetBasicBlockMap()
Recompute the basic block map, so can use getBasicBlock(int) to index into the basic blocks quickly. TODO: think about possibly keeping the basic block map up-to-date automatically (Use a hashtable, perhaps?).

getBasicBlock

public BasicBlock getBasicBlock(int number)
Get the basic block with a given number. PRECONDITION: resetBasicBlockMap() has been called before calling this function, but after making any changes to the set of basic blocks in the IR.

Parameters:
number - the number of the basic block to retrieve
Returns:
that requested block

getBasicBlocks

public Enumeration<BasicBlock> getBasicBlocks(BitVector bits)
Get an enumeration of all the basic blocks whose numbers appear in the given BitSet. PRECONDITION: resetBasicBlockMap() has been called before calling this function, but after making any changes to the set of basic blocks in the IR.

Parameters:
bits - The BitSet that defines which basic blocks to enumerate.
Returns:
an enumeration of said blocks.

numberInstructions

public int numberInstructions()
Densely number all the instructions currently in this IR from 0...numInstr-1. Returns the number of instructions in the IR. Intended style of use: 
    passInfo = new passInfoObjects[ir.numberInstructions()];
    ...do analysis using passInfo as a look aside
            array holding pass specific info...

Returns:
the number of instructions

setInstructionScratchWord

public void setInstructionScratchWord(int value)
Set the scratch word on all instructions currently in this IR to a given value.

Parameters:
value - value to store in all instruction scratch words

clearInstructionScratchWord

public void clearInstructionScratchWord()
Clear (set to zero) the scratch word on all instructions currently in this IR.

clearInstructionScratchObject

public void clearInstructionScratchObject()
Clear (set to null) the scratch object on all instructions currently in this IR.

clearBasicBlockScratchObject

public void clearBasicBlockScratchObject()
Clear (set to null) the scratch object on all basic blocks currently in this IR.

getNumberOfSymbolicRegisters

public int getNumberOfSymbolicRegisters()
Return the number of symbolic registers for this IR

getMaxBasicBlockNumber

public int getMaxBasicBlockNumber()
Returns:
the largest basic block number assigned to a block in the IR. Will return -1 if no block numbers have been assigned.

pruneExceptionalOut

public void pruneExceptionalOut()
Prune the exceptional out edges for each basic block in the IR.

hasReachableExceptionHandlers

public boolean hasReachableExceptionHandlers()
Returns:
true if it is possible that the IR contains an exception handler, false if it is not. Note this method may conservatively return true even if the IR does not actually contain a reachable exception handler.

unfactor

public void unfactor()
Partially convert the FCFG into a more traditional CFG by splitting all nodes that contain PEIs and that have reachable exception handlers into multiple basic blocks such that the instructions in the block have the expected post-dominance relationship. Note, we do not bother to unfactor basic blocks that do not have reachable exception handlers because the fact that the post-dominance relationship between instructions does not hold in these blocks does not matter (at least for intraprocedural analyses). For more information see.

getHandlerLivenessComputed

public boolean getHandlerLivenessComputed()
States whether liveness for handlers is available & @return whether liveness for handlers is available

setHandlerLivenessComputed

public void setHandlerLivenessComputed(boolean value)
Record whether or not liveness information for handlers is available

verify

public void verify(String where)
Verify that the IR is well-formed.

NB: this is expensive -- be sure to guard invocations with debugging flags.

Parameters:
where - phrase identifying invoking compilation phase

verify

public void verify(String where,
                   boolean checkCFG)
Verify that the IR is well-formed.

NB: this is expensive -- be sure to guard invocations with debugging flags.

Parameters:
where - phrase identifying invoking compilation phase
checkCFG - should the CFG invariants be checked (they can become invalid in "late" MIR).

verifyBBConstruction

private void verifyBBConstruction(String where)
Verify basic block construction from the basic block and instruction information.

Parameters:
where - phrase identifying invoking compilation phase

verifyCFG

private void verifyCFG(String where)
Verify control flow graph construction

Parameters:
where - phrase identifying invoking compilation phase

verifyInstructions

private void verifyInstructions(String where)
Verify that every instruction:

Parameters:
where - phrase identifying invoking compilation phase

verifyAllBlocksAreReachable

private void verifyAllBlocksAreReachable(String where)
Verify that every block in the CFG is reachable as failing to do so will cause EnterSSA.insertPhiFunctions to possibly access elements in DominanceFrontier.getIteratedDominanceFrontier and then DominanceFrontier.getDominanceFrontier that aren't defined. Also verify that blocks reached over an exception out edge are not also reachable on normal out edges as this will confuse liveness analysis.

Parameters:
where - phrase identifying invoking compilation phase

verifyAllBlocksAreReachable

private void verifyAllBlocksAreReachable(String where,
                                         BasicBlock curBB,
                                         BitVector visitedNormalBBs,
                                         BitVector visitedExceptionalBBs,
                                         boolean fromExceptionEdge)
Verify that every block in the CFG is reachable as failing to do so will cause EnterSSA.insertPhiFunctions to possibly access elements in DominanceFrontier.getIteratedDominanceFrontier and then DominanceFrontier.getDominanceFrontier that aren't defined. Also verify that blocks reached over an exception out edge are not also reachable on normal out edges as this will confuse liveness analysis.

Parameters:
where - location of verify in compilation
curBB - the current BB to work on
visitedNormalBBs - the blocks already visited (to avoid cycles) on normal out edges
visitedExceptionalBBs - the blocks already visited (to avoid cycles) on exceptional out edges
fromExceptionEdge - should paths from exceptions be validated?

verifyRegisterDefs

private void verifyRegisterDefs(String where)
Verify that every non-physical, non-parameter symbolic register that has a use also has at least one def

Parameters:
where - phrase identifying invoking compilation phase

verifyRegisterTypes

private void verifyRegisterTypes(String where)
Verify that no register is used as a long type and an int type PRECONDITION: register lists computed

Parameters:
where - phrase identifying invoking compilation phase

verifyUseFollowsDef

private void verifyUseFollowsDef(String where)
Check whether uses follow definitions and that in SSA form variables aren't multiply defined

verifyUseFollowsDef

private void verifyUseFollowsDef(String where,
                                 HashSet<Object> definedVariables,
                                 BasicBlock curBB,
                                 BitVector visitedBBs,
                                 ArrayList<BasicBlock> path,
                                 int maxPathLength,
                                 boolean traceExceptionEdges)
Check whether uses follow definitions and in SSA form that variables aren't multiply defined

Parameters:
where - location of verify in compilation
definedVariables - variables already defined on this path
curBB - the current BB to work on
visitedBBs - the blocks already visited (to avoid cycles)
path - a record of the path taken to reach this basic block
traceExceptionEdges - should paths from exceptions be validated?

getVariableUse

private Object getVariableUse(String where,
                              Operand operand)
Get the variable used by this operand

Parameters:
where - the verification location
operand - the operand to pull a variable from
Returns:
null if the variable should be ignored otherwise the variable

getVariableDef

private Object getVariableDef(String where,
                              Operand operand)
Get the variable defined by this operand

Parameters:
where - the verification location
operand - the operand to pull a variable from
Returns:
null if the variable should be ignored otherwise the variable

verror

private void verror(String where,
                    String msg)
Generate error

Parameters:
where - phrase identifying invoking compilation phase
msg - error message
Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD