BasicBlock (Jikes RVM API)

Overview

Package

Class

Use

Tree

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 BasicBlock

java.lang.Object
  org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
      org.jikesrvm.compilers.opt.util.SortedGraphNode
          org.jikesrvm.compilers.opt.ir.BasicBlock

All Implemented Interfaces:: GraphElement, GraphNode

Direct Known Subclasses:: ExceptionHandlerBasicBlock

public class BasicBlock
extends SortedGraphNode
extends SortedGraphNode

A basic block in the Factored Control Flow Graph (FCFG).

Just like in a standard control flow graph (CFG), a FCFG basic block contains a linear sequence of instructions. However, in the FCFG, a Potentially Excepting Instruction (PEI) does not necessarily end its basic block. Therefore, although instructions within a FCFG basic block have the expected dominance relationships, they do not have the same post-dominance relationships as they would under the traditional basic block formulation used in a CFG. We chose to use an FCFG because doing so significantly reduces the number of basic blocks and control flow graph edges, thus reducing the time and space costs of representing the FCFG and also increasing the effectiveness of local (within a single basic block) analysis. However, using an FCFG does complicate flow-sensitive global analaysis. Many analyses can be easily extended to work on the FCFG. For those analyses that cannot, we provide utilities (IR.unfactor(), unfactor(IR)) to effectively convert the FCFG into a CFG. For a more detailed description of the FCFG and its implications for program analysis see the PASTE'99 paper by Choi et al. Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs

The instructions in a basic block have the following structure

The block begins with a LABEL.
Next come zero or more non-branch instructions.
Next come zero or more conditional branches
Next comes zero or one unconditional branch
Finally the block ends with a BBEND

CALL instructions do not end their basic block. ATHROW instructions do end their basic block. Conventionally, we refer to the real instructions of the block as those that are between the LABEL and the BBEND. We say that the block is empty if it contains no real instructions.

See Also:: IR, Instruction, ControlFlowGraph

Nested Class Summary
`(package private) static class`	`BasicBlock.BBEnum`
`(package private) static class`	`BasicBlock.ComputedBBEnum`
`(package private) static class`	`BasicBlock.ExceptionOutEdgeEnum`
`(package private) static class`	`BasicBlock.InEdgeEnum`
`(package private) class`	`BasicBlock.NormalOutEdgeEnum`
`(package private) static class`	`BasicBlock.OutEdgeEnum`

Nested classes/interfaces inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
`SpaceEffGraphNode.GraphEdgeEnumeration<T extends GraphEdge>, SpaceEffGraphNode.OutEdgeEnumeration`

Field Summary
`(package private) static short`	`CAN_THROW_EXCEPTIONS` Bitfield used in flag encoding
`(package private) Instruction`	`end` Last instruction of the basic block (BBEND).
`(package private) static short`	`EXCEPTION_HANDLER` Bitfield used in flag encoding
`(package private) static short`	`EXCEPTION_HANDLER_WITH_NORMAL_IN` Bitfield used in flag encoding
`ExceptionHandlerBasicBlockBag`	`exceptionHandlers` Encodes exception handler info for this block.
`protected short`	`flags` Used to encode various properties of the block.
`protected float`	`freq` Relative execution frequency of this basic block.
`(package private) static short`	`IMPLICIT_EXIT_EDGE` Bitfield used in flag encoding
`(package private) static short`	`INFREQUENT` Bitfield used in flag encoding
`(package private) static short`	`LANDING_PAD` Bitfield used in flag encoding
`(package private) static short`	`REACHABLE_FROM_EXCEPTION_HANDLER` Bitfield used in flag encoding
`(package private) static short`	`SCRATCH` Bitfield used in flag encoding
`(package private) Instruction`	`start` First instruction of the basic block (LABEL).
`(package private) static short`	`UNSAFE_TO_SCHEDULE` Bitfield used in flag encoding

Fields inherited from class org.jikesrvm.compilers.opt.util.SortedGraphNode
`backwardSortNumber, forwardSortNumber, sortedNext, sortedPrev`

Fields inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
`_inEdgeEnd, _inEdgeStart, _outEdgeEnd, _outEdgeStart, info, next, nextSorted, prev, scratch, scratchObject`

Constructor Summary
`private`	`BasicBlock()` This constructor is only used for creating an EXIT node
	`BasicBlock(int i, InlineSequence position, ControlFlowGraph cfg)` Creates a new basic block at the specified location.
`protected`	`BasicBlock(int i, InlineSequence position, int num)` Creates a new basic block at the specified location with the given basic block number.

Method Summary
`private void`	`addTargets(BasicBlock.ComputedBBEnum e, TypeReference thrownException)`
`void`	`appendInstruction(Instruction i)` Append instruction to this basic block by inserting it right before the BBEND instruction in the instruction list.
`void`	`appendInstructionRespectingTerminalBranch(Instruction i)` Append instruction to this basic block by inserting it right before the BBEND instruction in the instruction list.
`void`	`appendInstructionRespectingTerminalBranchOrPEI(Instruction i)` Append instruction to this basic block by inserting it right before the BBEND instruction in the instruction list.
`void`	`augmentExecutionFrequency(float f)` Augment the estimated relative execution frequency of this block.
`boolean`	`canThrowExceptions()` Can this block possibly throw an exception?
`void`	`clearCanThrowExceptions()` Clear the may raise an exception property of the block
`void`	`clearExceptionHandlerBasicBlock()` Clear the block is the first one in an exception handler property of the block.
`void`	`clearInfrequent()` Clear the infrequently executed property of the block
`void`	`clearLandingPad()` Clear the landing pad property of the block
`void`	`clearMayThrowUncaughtException()` Clear the may raise uncaught exception property of the block
`void`	`clearReachableFromExceptionHandler()` Clear the block is reachable from an exception handler property of the block.
`void`	`clearScratchFlag()` Clear the scratch flag.
`void`	`clearUnsafeToSchedule()` Clear the unsafe to schedule property of the block
`BasicBlock`	`copyWithoutLinks(IR ir)` Copies a basic block.
`BasicBlock`	`createSubBlock(int bc, IR ir)`
`BasicBlock`	`createSubBlock(int bc, IR ir, float wf)` Creates a new basic block that inherits its exception handling, etc from 'this'.
`private void`	`deleteExceptionalOut()`
`void`	`deleteNormalOut()` Delete all the non-exceptional out edges.
`void`	`discardInstructions()`
`InstructionEnumeration`	`enumerateBranchInstructions()` Return an enumeration of the branch instructions in this basic block.
`LiveIntervalEnumeration`	`enumerateLiveIntervals()`
`Instruction`	`firstBranchInstruction()` Return the first branch instruction in the block.
`Instruction`	`firstInstruction()`
`Instruction`	`firstRealInstruction()`
`InstructionEnumeration`	`forwardInstrEnumerator()` Forward enumeration of all the instruction in the block.
`InstructionEnumeration`	`forwardRealInstrEnumerator()` Forward enumeration of all the real instruction in the block.
`BasicBlockEnumeration`	`getApplicableExceptionalOut(Instruction instr)` An enumeration of the subset of exceptional out edges that are applicable to the given instruction (assumed to be in instruction in 'this')
`BasicBlockEnumeration`	`getExceptionalOut()` An enumeration of the 'exceptional' (reached via exceptional control flow) out nodes of the block.
`BasicBlockEnumeration`	`getExceptionHandlers()` An enumeration of the in scope exception handlers for this basic block.
`float`	`getExecutionFrequency()` Return the estimated relative execution frequency of the block
`BasicBlock`	`getFallThroughBlock()` If there is a fallthrough FCFG successor of this node return it.
`LiveIntervalElement`	`getFirstLiveIntervalElement()` Returns NULL or an LiveIntervalElement (GCMaps/RegAlloc).
`BasicBlockEnumeration`	`getIn()` An enumeration of the FCFG in nodes.
`boolean`	`getInfrequent()` Has the block been marked as being infrequently executed?
`BasicBlockEnumeration`	`getInNodes()` An enumeration of the FCFG in nodes.
`boolean`	`getLandingPad()` Has the block been marked as landing pad?
`BasicBlockEnumeration`	`getNormalOut()` An enumeration of the 'normal' (not reached via exceptional control flow) out nodes of the block.
`BasicBlock`	`getNotTakenNextBlock()`
`int`	`getNumberOfExceptionalOut()` Get the number of out nodes that are to exception handler basic blocks
`int`	`getNumberOfNormalOut()` Get the number of out nodes that are to "normal" basic blocks
`int`	`getNumberOfRealInstructions()` How many real instructions does the block contain?
`BasicBlock.OutEdgeEnum`	`getOut()` An enumeration of the FCFG out nodes.
`BasicBlock.OutEdgeEnum`	`getOutNodes()` An enumeration of the FCFG out nodes.
`BasicBlockEnumeration`	`getReachableExceptionHandlers()` Returns an Enumeration of the in scope exception handlers that are actually reachable from this basic block in the order that they are applicable (which is semantically meaningful).
`boolean`	`getScratchFlag()` Is the scratch flag set on the block?
`boolean`	`hasApplicableExceptionalOut(Instruction instr)` Are there any exceptional out edges that are applicable to the given instruction (assumed to be in instruction in 'this')
`boolean`	`hasAthrowInst()` Does this basic block contain an explicit athrow instruction?
`boolean`	`hasExceptionHandlers()` Is this block in the scope of at least exception handler?
`boolean`	`hasGoto()` Does this basic block end in a GOTO instruction?
`boolean`	`hasNonReturningCall()` Does this basic block end in a call that never returns?
`boolean`	`hasNonReturningOsr()`
`boolean`	`hasReachableExceptionHandlers()` Are there exceptinal handlers that are reachable via exceptional control flow from this basic block?
`boolean`	`hasReturn()` Does this basic block end in a RETURN instruction?
`boolean`	`hasSwitch()` Does this basic block end in a SWITCH instruction?
`boolean`	`hasTrap()` Does this basic block end in an explicit trap?
`void`	`initializeLiveRange()` Clear the scratch object from previous uses (rename scratchObject manipulations for GCMaps/RegAlloc).
`(package private) void`	`initInOutSets()`
`boolean`	`isEmpty()` Returns true if the block contains no real instructions
`boolean`	`isExceptionalOut(BasicBlock bb)` Is there an 'exceptional' out edge to the given basic block?
`boolean`	`isExceptionHandlerBasicBlock()` Is this block the first basic block in an exception handler?
`boolean`	`isExceptionHandlerEquivalent(BasicBlock other)` Compare the in scope exception handlers of two blocks.
`private boolean`	`isExceptionHandlerWithNormalIn()`
`boolean`	`isExit()` Is this block the exit basic block?
`boolean`	`isIn(BasicBlock bb)` Is there an in edge from the given basic block?
`boolean`	`isNormalOut(BasicBlock bb)` Is there a 'normal' out edge to the given basic block?
`boolean`	`isOut(BasicBlock bb)` Is there an out edge to the given basic block?
`boolean`	`isReachableFromExceptionHandler()` Has the block been marked as being reachable from an exception handler?
`boolean`	`isUnsafeToSchedule()` Has the block been marked as being unsafe to schedule (due to the presence of Magic)?
`void`	`killFallThrough()` Replace fall through in this block by an explicit goto
`Instruction`	`lastInstruction()`
`Instruction`	`lastRealInstruction()`
`(package private) static BasicBlock`	`makeExit()` Make an EXIT node.
`Instruction`	`makeGOTO()` Make a GOTO instruction, branching to the first instruction of this basic block.
`BranchOperand`	`makeJumpTarget()` Make a branch operand with the label instruction of this block.
`boolean`	`mayThrowUncaughtException()` Can a PEI in this block possibly raise an uncaught exception?
`boolean`	`mergeFallThrough(IR ir)` If this block has a single non-Exception successor in the CFG then we may be able to merge the two blocks together.
`void`	`moveBehind(BasicBlock pred, IR ir)` Move me behind `pred'.
`BasicBlock`	`nextBasicBlockInCodeOrder()` Return the next basic block in with respect to the current code linearization order.
`void`	`prependInstruction(Instruction i)` Prepend instruction to this basic block by inserting it right after the LABEL instruction in the instruction list.
`void`	`prependInstructionRespectingPrologue(Instruction i)` Prepend instruction to this basic block but respect the prologue instruction, which must come first.
`void`	`prependLiveIntervalElement(LiveIntervalElement li)` Prepend a live interval element to the list being maintained in scratchObject (GCMaps/RegAlloc).
`BasicBlock`	`prevBasicBlockInCodeOrder()` Return the previous basic block in with respect to the current code linearization order.
`void`	`printExtended()` Print a detailed dump of the block to the sysWrite stream
`(package private) void`	`pruneExceptionalOut(IR ir)` Prune away exceptional out edges that are not reachable given this block's instructions.
`void`	`recomputeNormalOut(IR ir)` Recompute the normal out edges of 'this' based on the semantics of the branch instructions in the block.
`void`	`redirectOuts(BasicBlock b, BasicBlock bCopy, IR ir)` Change all branches from this to b to branches that go to bCopy instead.
`void`	`replicateNormalOut(IR ir)` For each basic block b which is a "normal" successor of this, make a copy of b, and set up the CFG so that this block has normal out edges to the copies.
`BasicBlock`	`replicateThisOut(IR ir, BasicBlock b)` For basic block b which has to be a "normal" successor of this, make a copy of b, and set up the CFG so that this block has normal out edges to the copy.
`BasicBlock`	`replicateThisOut(IR ir, BasicBlock b, BasicBlock pred)` For basic block b which has to be a "normal" successor of this, make a copy of b, and set up the CFG so that this block has normal out edges to the copy.
`InstructionEnumeration`	`reverseInstrEnumerator()` Reverse enumeration of all the instruction in the block.
`InstructionEnumeration`	`reverseRealInstrEnumerator()` Reverse enumeration of all the real instruction in the block.
`void`	`scaleExecutionFrequency(float f)` Scale the estimated relative execution frequency of this block.
`BasicBlock`	`segregateInstruction(Instruction target, IR ir)` Ensure that the target instruction is the only real instruction in its basic block and that it has exactly one successor and one predecessor basic blocks that are linked to it by fall through edges.
`void`	`setCanThrowExceptions()` Mark the block as possibly raising an exception.
`private void`	`setCanThrowExceptions(boolean v)`
`void`	`setExceptionHandlerBasicBlock()` Mark the block as the first block in an exception handler.
`void`	`setExceptionHandlerWithNormalIn()`
`void`	`setExecutionFrequency(float f)` Set the estimated relative execution frequency of this block.
`void`	`setInfrequent()` Mark the block as being infrequently executed.
`(package private) void`	`setInfrequent(boolean v)`
`private void`	`setIsExceptionHandlerBasicBlock(boolean v)`
`void`	`setLandingPad()` Mark the block as a landing pad for loop invariant code motion.
`void`	`setMayThrowUncaughtException()` Mark the block as possibly raising an uncaught exception.
`private void`	`setMayThrowUncaughtException(boolean v)`
`void`	`setReachableFromExceptionHandler()` Mark the block as being reachable from an exception handler.
`void`	`setScratchFlag()` Set the scratch flag
`void`	`setUnsafeToSchedule()` Mark the block as being unsafe to schedule.
`private void`	`setUnsafeToSchedule(boolean v)`
`BasicBlock`	`splitNodeAt(Instruction last_instr_BB1, IR ir)` Splits a node at an instruction point.
`BasicBlock`	`splitNodeWithLinksAt(Instruction last_instr_BB1, IR ir)` Splits a node at an instruction point.
`String`	`toString()` Returns the string representation of this basic block.
`(package private) void`	`unfactor(IR ir)` Convert a block in the FCFG into the equivalent set of CFG blocks by splitting the original block into sub-blocks at each PEI that reaches at least one exception handelr.

Methods inherited from class org.jikesrvm.compilers.opt.util.SortedGraphNode
`getBackwardSortedNext, getBackwardSortNumber, getForwardSortedNext, getForwardSortNumber, getNewSortMarker, getSortedNext, getSortMarker, getSortNumber, isSortMarkedWith, setBackwardSortNumber, setForwardSortNumber, setSortedNext, setSortMarker, setSortNumber, setSortNumber`

Methods inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraphNode
_sortDFS, _sortRevTop, _sortTop, append, appendInEdge, appendOutEdge, clearDfsVisited, clearFlags, clearInFlags, clearLoopHeader, clearOnStack, clearOutFlags, clearTopVisited, deleteIn, deleteOut, deleteOut, deleteOut, dfsVisited, findOutEdgeTo, firstInEdge, firstInNode, firstOutEdge, firstOutNode, flagsOn, getIndex, getNext, getNumber, getNumberOfIn, getNumberOfOut, getPrev, getScratch, hasIn, hasOneIn, hasOneIn, hasOneOut, hasOneOut, hasOut, hasZeroIn, hasZeroOut, inEdges, inNodes, insertOut, insertOut, isLoopHeader, markDFN, markSCC, onStack, outEdges, outNodes, pointsIn, pointsOut, printInEdges, printInNodes, printOutEdges, printOutNodes, remove, removeIn, removeIn, removeOut, removeOut, replaceInEdge, replaceOut, setDfsVisited, setDfsVisitedOnStack, setIndex, setLoopHeader, setNumber, setOnStack, setScratch, setTopVisited, sortDFS, sortRevTop, sortTop, topVisited

Methods inherited from class org.jikesrvm.compilers.opt.util.SpaceEffGraphNode

_sortDFS, _sortRevTop, _sortTop, append, appendInEdge, appendOutEdge, clearDfsVisited, clearFlags, clearInFlags, clearLoopHeader, clearOnStack, clearOutFlags, clearTopVisited, deleteIn, deleteOut, deleteOut, deleteOut, dfsVisited, findOutEdgeTo, firstInEdge, firstInNode, firstOutEdge, firstOutNode, flagsOn, getIndex, getNext, getNumber, getNumberOfIn, getNumberOfOut, getPrev, getScratch, hasIn, hasOneIn, hasOneIn, hasOneOut, hasOneOut, hasOut, hasZeroIn, hasZeroOut, inEdges, inNodes, insertOut, insertOut, isLoopHeader, markDFN, markSCC, onStack, outEdges, outNodes, pointsIn, pointsOut, printInEdges, printInNodes, printOutEdges, printOutNodes, remove, removeIn, removeIn, removeOut, removeOut, replaceInEdge, replaceOut, setDfsVisited, setDfsVisitedOnStack, setIndex, setLoopHeader, setNumber, setOnStack, setScratch, setTopVisited, sortDFS, sortRevTop, sortTop, topVisited

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

Field Detail