public class CFG
extends java.lang.Object
RuleTriggerMethodAdapter
for an example of how the methods provided by this class are invoked during visiting of the method byte code.
Methods provided for driving CFG construction include:
add(int)
, add(int, int)
,
add(int, int, int)
add(int, int[])
add(int, String)
,
add(int, String, String, String)
, add(int, String, int)
,
CFG#split(org.objectweb.asm.Label)
, CFG#split(org.objectweb.asm.Label, org.objectweb.asm.Label)
,
CFG#split(org.objectweb.asm.Label, org.objectweb.asm.Label, org.objectweb.asm.Label)
,
CFG#split(org.objectweb.asm.Label, org.objectweb.asm.Label, org.objectweb.asm.Label[])
,
CFG#visitLabel(org.objectweb.asm.Label)
,
CFG#visitTryCatchBlock(org.objectweb.asm.Label, org.objectweb.asm.Label, org.objectweb.asm.Label, String)
,
CFG#visitTriggerStart(org.objectweb.asm.Label)
, CFG#visitTriggerEnd(org.objectweb.asm.Label)
,
visitMaxs()
, visitEnd()
,
Normal control flow linkage is explicitly represented in the blocks as a list containing the labels of the target blocks. Labels are used rather than handles on the block themselves so that forward links to blocks which have not yet been generated can be modelled. Labels are resolved to the relevant block and instruction index as they are visited during walking of the bytecode.
The outgoing control flow link count can be obtained by calling methodBBlock.nOuts()
. The label of the block to which control is transferred can be identified by calling
method BBlock.nthOut(int)
. Note that valid link indices run from 1 to nOuts() (see below). Once
a label has been visited it can be resolved to a CodeLocation
by calling method
CFG#getLocation(org.objectweb.asm.Label)
. The returned value identifies both a block and an instruction
offset in the block.
Several caveats apply to this simple picture. Firstly, blocks ending in return or throw have no control flow -- they
pass control back to the caller rather than to another basic block. So, the count returned by BBlock.nOuts()
will be 0 for such blocks.
Secondly, all blocks except the last have a distinguished link which identifies the block successor link
relationship. The successor block can be obtained by supplying value 0 as argument to method
BBlock.nthOut(int)
. This link is additional to any control flow links and it is not
included in the count returned by BBlock.nOuts()
. Note that where there is a control flow link to the
next block in line (e.g. where the block ends in an ifXX instruction) the label employed for the distinguished 0
link will also appear in the set of control flow links (as link 1 in the case of an ifXX instruction).
The final caveat is that this graph model does not identify control flow which occurs as a consequence of
generated exceptions.
TryCatchDetails
which identify the location of the try/catch start, its end and the associated handler
start location. Once again labels are used so as to allow modelling of forward references to code locations
which have not yet been generated.
Note that handler start labels always refer to a code location which is at the start of a basic block. Start
and end labels for a given try/catch block may refer to code locations offset into their containing basic block
and possibly in distinct blocks.
Methods #tryCatchStart(org.objectweb.asm.Label)
, #tryCatchEnd(org.objectweb.asm.Label)
and #tryCatchHandlerStart(org.objectweb.asm.Label)
can be called to determine whether a given label
identifies, respectively, the start of a try catch block, the end of a try catch block or the start of a handler
block. Methods #tryCatchStartDetails(org.objectweb.asm.Label)
#tryCatchEndDetails(org.objectweb.asm.Label)
,
and #tryCatchHandlerStartDetails(org.objectweb.asm.Label)
can be used to retrieve the associated
TryCatchDetails
information.
CFG#getBlock(org.objectweb.asm.Label)
to resolve the primary label for a block (i.e. the
one supplied as argument to a split call) to the associated block. It also provides method
CFG#getBlockInstructionIdx(org.objectweb.asm.Label)
to resolve a label to a CodeLocation
i.e.
block and instruction index within a block. Both methods return null if the label has not yet been visited.
Method getContains(BBlock)
is also provided to obtain a list of all labels contained within a
specific block. There may be more than one label which resolves to a location within a specific block. For
example, the handler start label associated with a try/catch handler is contained in the handler block at
offset 0 but is never the primary label for the block. Iteration over the contained set is used internally
in the cfg to resolve equivalent labels.
getPairedEnter(CodeLocation)
,
and getPairedExit(CodeLocation, BBlock)
9note that a given enter will never have more than one
exit in any given block).
The cfg associates monitor enters and exits with their enclosing block, allowing it to identify the start and/or
end of synchronized regions within a specific block. This information can be propagated along control flow links
to identify outstanding monitor enters at any point in a given control flow path. Whenever a block is created
it is associated with a set of open enter instructions i.e. enter instructions occurring along all control flow
paths to the block for which no corresponding exit has been executed.
carryForward()
. This
method identifies the current block's open enters list (how will emerge below), updates it with any enters and
exits performed in the block and then, for each each outgoing control link, associates the new list with the
linked block by inserting the list into a hash table keyed by the block label. Clearly, if the current block was
itself arrived at via normal control flow then its open enters list will already be available in the hash table.
Handler blocks require a different lookup.
carryForward()
. This requires identifying all try/catch regions which enclose the block
and tagging the corresponding TryCatchDetails
object with the location of any monitor enter instructions
which are open at some point in the try catch region. If this is done for every block encountered during
the bytecode walk then at the point where the handler block is split all enter instructions which are still open
somewhere within the try/catch region will be listed in the TryCatchDetails
. So, at the split point
the old block can be tested to see if it is labelled as a try/catch handler target and, if so, its open enters
list can be looked up by locating the TryCatchDetails
associated with the handler start label.
Modifier and Type | Field and Description |
---|---|
private java.util.Map<Label,BBlock> |
blocks
a mapping from the start label of a basic block to the associated block
|
private java.util.Map<BBlock,FanOut> |
contains
a map identifying the containment relationship between a basic block and labels which identify
instructions located within the block - the first entry is the block label itself
|
private static int |
CONTAINS
flag value passed to request a check for a containment and returned to notify a containment
|
private BBlock |
current
the current basic block
|
private java.util.List<TryCatchDetails> |
currentTryCatchStarts
a list of all try catch blocks which are started but not ended.
|
static Type |
EARLY_RETURN_EXCEPTION_TYPE
Type identifying return exceptions thrown by runtime
|
static java.lang.String |
EARLY_RETURN_EXCEPTION_TYPE_NAME
name of type identifying return exceptions thrown by runtime
|
private BBlock |
entry
the label of the first basic block in the code
|
static Type |
EXECUTE_EXCEPTION_TYPE
Type identifying execute exceptions thrown by runtime
|
static java.lang.String |
EXECUTE_EXCEPTION_TYPE_NAME
name of type identifying execute exceptions thrown by runtime
|
private java.util.Map<CodeLocation,CodeLocation> |
inverseMonitorPairs
an inverse map from each monitor exit instruction to the monitor enter insructions it closes.
|
private java.util.Map<Label,CodeLocation> |
labelLocations
a mapping from each label to its enclosing basic block and instruction offset
|
private TriggerDetails |
latestTrigger
details of the last trigger section encountered set when a trigger start label is notified
|
private java.lang.String |
methodName
the name of the method for which this is a CFG
|
private java.util.Map<CodeLocation,java.util.List<CodeLocation>> |
monitorPairs
a map from monitor enter instructions to the monitor exit insructions which close them.
|
private java.util.List<java.lang.String> |
names
a list of names employed in the bytecode
|
private int |
nextIdx
a counter used to number bblocks in code order
|
private java.util.Map<Label,java.util.List<CodeLocation>> |
openMonitorEnters
a map from block labels to any unclosed monitor enter instructions outstanding when the block is entered.
|
private static int |
OVERLAPS
flag value passed to request a check for an overlap and returned to notify an overlap
|
static Type |
THROW_EXCEPTION_TYPE
Type identifying throw exceptions thrown by runtime
|
static java.lang.String |
THROW_EXCEPTION_TYPE_NAME
name of type identifying throw exceptions thrown by runtime
|
private java.util.Map<Label,TriggerDetails> |
triggerEnds
a map from labels which identify the end of a code injection sequence to details of the labels
which locate the sequence and its exception handlers
|
private java.util.Map<Label,TriggerDetails> |
triggerStarts
a map from labels which identify the start of a code injection sequence to details of the labels
which locate the sequence and its exception handlers
|
private java.util.Map<Label,java.util.List<TryCatchDetails>> |
tryCatchEnds
a map from try catch block end labels to the corresponding try catch block details -- the value
is a list because the code reader will reuse the same label when two try catch blocks end at the
same bytecode
|
private java.util.Map<Label,java.util.List<TryCatchDetails>> |
tryCatchHandlers
a map from try catch block handler labels to the corresponding try catch block details -- the value
is a list because the code reader will reuse the same label when two handler blocks start at the
same bytecode
|
private java.util.Map<Label,java.util.List<TryCatchDetails>> |
tryCatchStarts
a map from try catch block start labels to the corresponding try catch block details -- the value
is a list because the code reader will reuse teh same label when two try catch blocks start at the
same bytecode
|
private static int |
UNKNOWN
flag value returned to notify that a containment cannot yet be computed
|
Constructor and Description |
---|
CFG(java.lang.String methodName,
Label start)
construct a CFG labelling the initial block with a given label
|
Modifier and Type | Method and Description |
---|---|
void |
add(int instruction)
aopend an instruction to the current block
|
void |
add(int instruction,
int operand)
append an instruction with one operand to the current block
|
void |
add(int instruction,
int[] operands)
append an operand with more than two operands ot the current block
|
void |
add(int instruction,
int operand1,
int operand2)
append an instruction with two operands to the current block
|
void |
add(int instruction,
java.lang.String name)
append an instruction with a String operand to the current block
|
void |
add(int instruction,
java.lang.String name,
int dims)
append a multiarray create instruction to the current block
|
void |
add(int instruction,
java.lang.String owner,
java.lang.String name,
java.lang.String desc)
append a field or method instruction with 3 String operands to the current block
|
private void |
addContains(BBlock block,
Label label)
add a label to the list of labels contained in a given block
|
(package private) void |
addMonitorPair(CodeLocation enter,
CodeLocation exit)
pair a monitor enter instruction with an associated monitor exit instructions
|
private void |
carryForward()
forward details of open monitor and try catch block locations from the current
block to its reachable labels.
|
private int |
computeContainment(CodeLocation tryStart,
CodeLocation tryEnd,
CodeLocation enter,
CodeLocation exit,
int flags)
compute whether the the region defined by a given enter and exit location pair overlaps or is contained within
the region defined by a try start and end location pair when both regions ar erestricted to the current block
|
BBlock |
getBlock(Label label)
return the block containing a label if known
|
int |
getBlockInstructionIdx(Label label)
return the index of the label in its enclosing block's instruction sequence of -1 if the
label has not yet been visited.
|
FanOut |
getContains(BBlock block)
return a link object listing all the labels contained in a given block
|
CodeLocation |
getLocation(Label label)
return the location of the label if known or null if it has not yet been reached.
|
java.lang.String |
getName(int nameIdx) |
java.util.List<CodeLocation> |
getOpenMonitorEnters(Label label)
retrieve the list of monitor enter locations open at the start of a given block
|
java.util.Iterator<CodeLocation> |
getOpenMonitors(TriggerDetails triggerDetails)
retrieve the list of monitor enter locations associated with a trigger block.
|
CodeLocation |
getPairedEnter(CodeLocation exit)
locate the monitor enter instruction associated with a given monitor exit
|
private CodeLocation |
getPairedExit(CodeLocation enter,
BBlock block)
locate a monitor exit instruction in block associated with a given monitor enter
|
int |
getSavedMonitorIdx(CodeLocation open)
return the index of the local var at which this monitorenter saved its lock object
|
boolean |
hasLocation(Label label)
test whether the location of a label is known yet
|
boolean |
inBytemanHandler()
check if the current block is a byteman-generated handler i.e.
|
boolean |
inBytemanTrigger()
check if the current block is a byteman-generated trigger section.
|
boolean |
inRethrowHandler()
return true if the current block is a rethrow handler i.e.
|
CodeLocation |
nextLocation()
return a location which will identify the next instruction added to the current block
|
CodeLocation |
setLocation(Label label)
set the location of a label to the next instruction offset in the current block
|
void |
split(Label newStart)
split the graph at a control-flow dead-end using the label provided to identify the new current
block.
|
void |
split(Label newStart,
Label out)
split the graph at a control-flow goto point using the labels provided to identify the new current
block and the goto target.
|
void |
split(Label newStart,
Label out,
Label out2)
split the graph at a control-flow if branch point using the labels provided to identify the new current
block the if branch target and the else branch target.
|
void |
split(Label newStart,
Label dflt,
Label[] labels)
split the graph at a control-flow switch branch point using the labels provided to identify the new
current block, the switch case default branch target and the rest of the switch case branch targets.
|
java.lang.String |
toString()
generate a string representation of the CFG
|
java.util.Iterator<TriggerDetails> |
triggerDetails()
return an iterator ovver all known trigger detailsd
|
boolean |
triggerEnd(Label label)
test if a label marks the end of a trigger block
|
TriggerDetails |
triggerEndDetails(Label label)
return the list of details of try catch blocks which end at this label
|
boolean |
triggerStart(Label label)
test if a label marks the start of a trigger block
|
TriggerDetails |
triggerStartDetails(Label label)
return details of any trigger block which starts at this label
|
boolean |
tryCatchEnd(Label label)
test if a label marks the end of a try catch block
|
java.util.List<TryCatchDetails> |
tryCatchEndDetails(Label label)
return the list of details of try catch blocks which end at this label
|
boolean |
tryCatchHandlerStart(Label label)
test if a label marks the start of the handler for a try catch block
|
java.util.List<TryCatchDetails> |
tryCatchHandlerStartDetails(Label label)
return the list of details of try catch blocks whose handler startsend at this label
|
boolean |
tryCatchStart(Label label)
test if a label marks the start of a try catch block
|
java.util.List<TryCatchDetails> |
tryCatchStartDetails(Label label)
return the list of details of try catch blocks which start at this label
|
private boolean |
tryStartMayContainEnter(CodeLocation tryStart,
CodeLocation enter)
check whether the instructions exposed by a monitor enter may be contained within the scope of a
tryStart.
|
void |
visitEnd() |
void |
visitLabel(Label label)
notify the CFG that a label has been visited by the method visitor and hence its position will now
be resolved
|
void |
visitMaxs()
this can be called when the code generator call visiMaxs but it does nothing just now
|
void |
visitTriggerEnd(Label label)
notify the CFG that a label which represents the end of a trigger injection sequence has just been visited
by the method visitor.
|
void |
visitTriggerStart(Label label)
notify the CFG that a label which represents the start of a trigger injection sequence has just been visited
by the method visitor.
|
void |
visitTryCatchBlock(Label start,
Label end,
Label handler,
java.lang.String type)
notify the CFG of the location of a try catch block.
|
public static final Type EXECUTE_EXCEPTION_TYPE
public static final Type EARLY_RETURN_EXCEPTION_TYPE
public static final Type THROW_EXCEPTION_TYPE
public static final java.lang.String EXECUTE_EXCEPTION_TYPE_NAME
public static final java.lang.String EARLY_RETURN_EXCEPTION_TYPE_NAME
public static final java.lang.String THROW_EXCEPTION_TYPE_NAME
private java.lang.String methodName
private BBlock entry
private BBlock current
private int nextIdx
private java.util.Map<Label,BBlock> blocks
private java.util.Map<Label,CodeLocation> labelLocations
private java.util.Map<BBlock,FanOut> contains
private java.util.List<java.lang.String> names
private java.util.Map<Label,TriggerDetails> triggerStarts
private java.util.Map<Label,TriggerDetails> triggerEnds
private TriggerDetails latestTrigger
private java.util.Map<Label,java.util.List<TryCatchDetails>> tryCatchStarts
private java.util.Map<Label,java.util.List<TryCatchDetails>> tryCatchEnds
private java.util.Map<Label,java.util.List<TryCatchDetails>> tryCatchHandlers
private java.util.List<TryCatchDetails> currentTryCatchStarts
private java.util.Map<Label,java.util.List<CodeLocation>> openMonitorEnters
private java.util.Map<CodeLocation,java.util.List<CodeLocation>> monitorPairs
private java.util.Map<CodeLocation,CodeLocation> inverseMonitorPairs
private static final int OVERLAPS
private static final int CONTAINS
private static final int UNKNOWN
public CFG(java.lang.String methodName, Label start)
methodName
- the name of the method fro which this is a CFGstart
- a label for the entry block of the CFGpublic void add(int instruction)
instruction
- public void add(int instruction, int operand)
instruction
- operand
- public void add(int instruction, int operand1, int operand2)
instruction
- operand1
- operand2
- public void add(int instruction, int[] operands)
instruction
- operands
- public void add(int instruction, java.lang.String name)
instruction
- name
- public void add(int instruction, java.lang.String name, int dims)
instruction
- name
- the name of the array base typedims
- the number of array dimensionspublic void add(int instruction, java.lang.String owner, java.lang.String name, java.lang.String desc)
instruction
- name
- public CodeLocation setLocation(Label label)
label
- the label whose location is to be setpublic CodeLocation getLocation(Label label)
label
- the label whose location is desiredpublic boolean hasLocation(Label label)
label
- the label whose location is desiredpublic CodeLocation nextLocation()
public BBlock getBlock(Label label)
label
- the label whose containing block is desiredpublic FanOut getContains(BBlock block)
block
- the block whose labels are being soughtprivate void addContains(BBlock block, Label label)
block
- the block whose containslist is to be updatedlabel
- the label to be added to the listpublic java.util.List<CodeLocation> getOpenMonitorEnters(Label label)
label
- the label of the blockpublic java.util.Iterator<CodeLocation> getOpenMonitors(TriggerDetails triggerDetails)
triggerDetails
- the trigger being checkedvoid addMonitorPair(CodeLocation enter, CodeLocation exit)
enter
- exit
- private CodeLocation getPairedExit(CodeLocation enter, BBlock block)
enter
- public CodeLocation getPairedEnter(CodeLocation exit)
exit
- public int getSavedMonitorIdx(CodeLocation open)
private void carryForward()
private int computeContainment(CodeLocation tryStart, CodeLocation tryEnd, CodeLocation enter, CodeLocation exit, int flags)
tryStart
- the location of the start of the try region which will already have been visitedtryEnd
- the location of the end of the try region which may be null because the end point has not been
yet visitedenter
- the location of the start of the monitor region which will already have been visitedexit
- the location of an exit corresponding to the enter which may be null because the exit has not
yet been visitedflags
- OVERLAPS if an overlap is being checked for or CONTAINS if a containment is being checked forprivate boolean tryStartMayContainEnter(CodeLocation tryStart, CodeLocation enter)
enter
- tryStart
- public void split(Label newStart)
newStart
- the label to be used to identify the new current blockpublic void split(Label newStart, Label out)
newStart
- the label to be used to identify the new current blockout
- the target of the GOTOpublic void split(Label newStart, Label out, Label out2)
newStart
- the label to be used to identify the new current blockout
- the target of the if branchout2
- the target of the else branch which probably ought to be the same label as passed for the
current block (IF instructions assume drop-through)public void split(Label newStart, Label dflt, Label[] labels)
newStart
- the label to be used to identify the new current blockdflt
- the switch case default branch targetlabels
- the other switch case branch targetspublic boolean tryCatchStart(Label label)
label
- the label to be testedpublic boolean tryCatchEnd(Label label)
label
- the label to be testedpublic boolean tryCatchHandlerStart(Label label)
label
- the label to be testedpublic java.util.List<TryCatchDetails> tryCatchStartDetails(Label label)
label
- public java.util.List<TryCatchDetails> tryCatchEndDetails(Label label)
label
- public java.util.List<TryCatchDetails> tryCatchHandlerStartDetails(Label label)
label
- public boolean triggerStart(Label label)
label
- the label to be testedpublic boolean triggerEnd(Label label)
label
- the label to be testedpublic TriggerDetails triggerStartDetails(Label label)
label
- public TriggerDetails triggerEndDetails(Label label)
label
- public java.util.Iterator<TriggerDetails> triggerDetails()
public void visitLabel(Label label)
label
- public void visitTriggerStart(Label label)
label
- public void visitTriggerEnd(Label label)
label
- public void visitTryCatchBlock(Label start, Label end, Label handler, java.lang.String type)
start
- end
- handler
- type
- public boolean inBytemanHandler()
public boolean inRethrowHandler()
public boolean inBytemanTrigger()
public void visitMaxs()
public void visitEnd()
public java.lang.String toString()
toString
in class java.lang.Object
public int getBlockInstructionIdx(Label label)
label
- public java.lang.String getName(int nameIdx)