|
||||||||||
前のクラス 次のクラス | フレームあり フレームなし | |||||||||
概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド |
BBlock interface:
Interface for basic block class BBlock.
Data flow analysis and basic control flow analysis are done
based on the graph of basic blocks.
All methods other than static ones are a method used for
BBlock object ("this" is a BBlock instance).
Structure of basic blocks:
Input program represented in HIR or LIR is decomposed into
basic blocks. Control flow of the program can be represented
by a graph of basic blocks connected by predecessor/successor
relation. Information of the basic block is represented by
an object of BBlock class.
Contents of a basic block can be treated as a sequence of subtrees
which may be either HIR subtree or LIR subtree.
Such subtree is called a "top-subtree".
The top-subtree of HIR may represent a part of statement or
expression where some other part of the statement or expression
may be included in different basic blocks. For LIR, on the other hand, an LIR subtree is just a member of the aforementioned sequence, and there are no links or complex relations between LIR subtrees.
An HIR statement attached with label (LabeledStmt)
starts a new basic block.
If an HIR expression has label definition, it starts a new basic block(This may change in the future).
Depth first traversal of HIR tree from left to right represents
a sequence of HIR nodes. In this traversal, if an HIR statement
node is encountered, it starts a new top-subtree.
If a top-subtree is an expression subtree and another
expression subtree or statement subtree without label definition
succeeds immediately after the top-subtree, then the
succeeding subtree is treated as the next top-subtree.
The LIR top-subtree represents an LIR instruction.
In LIR flow analysis, a basic block is composed of a list of
LIR top-subtees (LIR instructions). LIR basic block is based solely on the flow of control. The control flow graph LIR basic blocks form will therefore be "irreducible".
Data flow analysis are done on the graph of basic blocks
and most of data flow information is associated with basic blocks.
The graph of basic blocks can be get from a SubpFlow object, which corresponds to a subprogram.
While HIR flow analysis and optimization can be thought of as utilizing the information supplied by the control flow graph, LIR flow analysis/optimization are done totally based on the control flow graph. An LIR basic block object holds the whole LIR subtree sequence that are associated to the basic block object, while in HIR there is only a link between the the basic block and the LabeledStmt
that signifies the start of the basic block. A SetRefRepr
class that wraps an HIR statement/LIR instruction along with its collection class SetRefReprList
will blur the distinction, however.
Relation between control flow and data flow:
This class provides accessor methods for data flow information for convinience, but actual data flow information is stored in an external object, namely, a FlowResults
object. When there is a modification of code that changes data flow but not control flow, the data flow information the external object holds must be cleared, but the control flow information this class holds will remain valid.
Methods listed here are used after flow analysis to get
information or to modify control flow.
(There may be many methods private to flow analysis
modules other than the methods listed below.)
When control flow is changed, data flow information
may not be consistent because data flow information
is not automatically updated by the control flow
modification. In order to make them consistent,
it is necessary to do data flow analysis again
after a group of control flow modifications are
completed.
メソッドの概要 | |
void |
addEdge(Exp pConditionalExp,
BBlock pToBlock)
addEdge: Add edge from this block to pToBlock that is to be taken when pConditionalExp is true. |
void |
addToPredList(BBlock pPred)
addToPredList: addToSuccList: Add the basic block pPred/pSucc to the list of predecessors/successors of this basic block, and this block is added to the list of successors/predecessors of pPred/pSucc. |
void |
addToSuccList(BBlock pSucc)
|
BBlockNodeIterator |
bblockNodeIterator()
|
BBlockSubtreeIterator |
bblockSubtreeIterator()
bblockSubtreeIterator: Create an iterator to traverse all top-subtree in this basic block. |
void |
changePredEdge(BBlock pBefore,
BBlock pAfter)
|
void |
changeSuccEdge(BBlock pBefore,
BBlock pAfter)
changeEdge: Change the edge between this block and pBefore to a new edge between this block and pAfter. |
void |
deleteBBlock()
deleteBBlock: Delete this block and add successors of this block to the set of successors of all predecessors of this block. |
void |
deleteEdge(BBlock pToBlock)
deleteEdge: Delete the edge from this block to pToBlock and adjust related addresses and links so as to keep consistency. |
void |
deleteFromPredList(BBlock pPred)
deleteFromPredList: deleteFromSuccList: Delete the basic block pPred/pSucc from to the list of predecessors/successors of this basic block, and this block is deleted from the list of successors/predecessors of pPred/pSucc. |
void |
deleteFromSuccList(BBlock pSucc)
|
void |
fuseSuccessor(BBlock pToBlock)
fuseSuccessor: Fuse the successor pToBlock with this block and make all successors of pToBlock as successors of this block. |
int |
getBBlockNumber()
getBBlockNumber: Get the block number attached to this basic block. |
ExpVector |
getDAvailIn()
getAvailIn: Get bit vector showing AvailIn set of this block. |
ExpVector |
getDAvailOut()
getAvailOut: Get bit vector showing AvailOut set of this block. |
FlowAnalSymVector |
getDDefIn()
getDefIn: Get bit vector showing DefIn set of this block. |
FlowAnalSymVector |
getDDefined()
getDDefined: Get bit vector showing DDefined set of this block. |
FlowAnalSymVector |
getDDefOut()
getDefOut: Get bit vector showing DefOut set of this block. |
ExpVector |
getDEGen()
getEGen: Get bit vector showing DEGen set of this block. |
FlowAnalSymVector |
getDExposed()
getDExposed: Get bit vector showing DExposed set of this block. |
DefVector |
getDKill()
getDKill: Get bit vector showing DKill set of this block. |
java.util.List |
getDomForSubpFlow()
Get the list of BBlock s that dominate this BBlock in the SubpFlow this BBlock belongs to. |
java.util.List |
getDominatedChildrenForSubpFlow()
getDominatedChildren: setDominatedChildren: Get/set the list of basic blocks immediately dominated by this block. |
FlowAnalSymVector |
getDUsed()
getDUsed: //##12 Get bit vector showing DUsed set of this block. |
BBlock |
getImmediateDominatorForSubpFlow()
getImmediateDominator: Get/set a basic block immediately dominating this block. |
BBlock |
getImmediatePostdominatorForSubpFlow()
getImmediatePostDominator: Get a basic block immediately post dominating this block. |
IR |
getIrLink()
getIrLink: Get the top-subtree that starts this basic block. |
Label |
getLabel()
getLabel: Get a label attached to the first top-subtree of this basic block. |
DefVector |
getPDef()
getPDef: Get bit vector showing PDef set of this block. |
FlowAnalSymVector |
getPDefined()
getPDefined: Get bit vector showing PDefined set of this block. |
ExpVector |
getPEKill()
getEKill: Get bit vector showing EKill set of this block. |
FlowAnalSymVector |
getPExposed()
getPExposed: Get bit vector showing PExposed set of this block. |
DefVector |
getPKill()
getPKill: Get bit vector showing PKill set of this block. |
FlowAnalSymVector |
getPLiveIn()
getLiveIn: Get bit vector showing LiveIn set of this block. |
FlowAnalSymVector |
getPLiveOut()
getLiveOut: Get bit vector showing LiveOut set of this block. |
java.util.List |
getPostdomForSubpFlow()
|
java.util.List |
getPostdominatedChildrenForSubpFlow()
getPostDominatedChildren: setPostDominatedChildren: Get/set the list of basic blocks post dominated by this block. |
DefVector |
getPReach()
Returns the PReach. |
Edge |
getPredEdge(BBlock pFromBBlock)
getPredEdge: getSuccEdge: Get the edge corresponding to the predecessor/successor to/from this basic block. |
java.util.List |
getPredList()
getPredList: getSuccList: Get the predecessor/successor list of this basic block. |
FlowAnalSymVector |
getPUsed()
getPUsed: //##12 Get bit vector showing PUsed set of this block. |
SetRefReprList |
getSetRefReprs()
Gets the SetRefReprList object that is the list of SetRefRepr objects, each of which wrap a statement/instruction. |
java.util.List |
getStrictDomForSubpFlow()
Get the strict dominator for this BBlock in the SubpFlow this BBlock belongs to. |
java.util.List |
getStrictPostdomForSubpFlow()
|
SubpFlow |
getSubpFlow()
Returns the SubpFlow object this BBlock belongs to. |
Edge |
getSuccEdge(BBlock pToBBlock)
|
java.util.List |
getSuccList()
|
java.lang.Object |
getWork()
getWork: setWork: get/set information privately used in each phase. |
boolean |
isDAvailIn(FlowExpId pExpId)
isAvailIn: See if the expression represented by pExpId is available (value is always computed) at entry to this block. |
boolean |
isDAvailOut(FlowExpId pExpId)
isAvailOut: See if the expression represented by pExpId is available (value is always computed) at exit from this block. |
boolean |
isDDef(SetRefRepr pSetRefRepr)
isDef: See if definition at position pPos is done in this block. |
boolean |
isDDefIn(Sym pSym)
isDefIn: See if pSym is always defined at entry to this block whichever path may be take. |
boolean |
isDDefined(Sym pSym)
isDefined: See if the value of pSym is defined in this block. |
boolean |
isDDefOut(Sym pSym)
isDefOut: See if pSym is always defined at exit from this block. |
boolean |
isDEGen(FlowExpId pExpId)
isEGen: See if expression designated by pReg is generated (computed in this block and afterwards its operand is not changed) in this block. |
boolean |
isDExposed(Sym pSym)
isExposed: See if the variable of pSym is used in this block without setting its value in this block. |
boolean |
isDKill(SetRefRepr pSetRefRepr)
isKill: See if definition at position pPos is killed in this block. |
boolean |
isDUsed(Sym pSym)
isUsed: //##12 See if the value of pSym is used in this block. |
boolean |
isEntryBBlock()
isEntryBlock: See if this block is the entry block in the graph of basic blocks. |
boolean |
isExitBBlock()
isExitBlock: See if this block is the exit block in the graph of basic blocks. |
boolean |
isPDef(SetRefRepr pSetRefRepr)
|
boolean |
isPDefined(Sym pSym)
isModified: See if the value of pSym is modified in this block. |
boolean |
isPEKill(FlowExpId pExpId)
isEKill: See if expression designated by pReg is killed (its operand is defined) in this block. |
boolean |
isPExposed(Sym pSym)
|
boolean |
isPKill(SetRefRepr pSetRefRepr)
|
boolean |
isPLiveIn(Sym pSym)
isLiveIn: See if pSym is live at entry to this block (value at entry is used in this block or in some successor of this block). |
boolean |
isPLiveOut(Sym pSym)
isLiveOut: See if pSym is live at exit from this block (value at exit is used in some successor of this block). |
boolean |
isPReach(SetRefRepr pSetRefRepr)
isReach0: See if definition at position pPos may reach to the entry point of this block. |
boolean |
isPUsed(Sym pSym)
|
FlowResults |
results()
Returns the FlowResults object that holds data flow information. |
void |
setDAvailIn(ExpVector pVect)
|
void |
setDAvailOut(ExpVector pVect)
|
void |
setDDefIn(FlowAnalSymVector pVect)
|
void |
setDDefined(FlowAnalSymVector pVect)
|
void |
setDDefOut(FlowAnalSymVector pVect)
|
void |
setDEGen(ExpVector pVect)
|
void |
setDExposed(FlowAnalSymVector pVect)
|
void |
setDKill(DefVector pVect)
|
void |
setDomForSubpFlow(java.util.List pDom)
Set the list of BBlock s that dominate this BBlock in the SubpFlow this BBlock belongs to. |
void |
setDominatedChildrenForSubpFlow(java.util.List pDominatedChildren)
|
void |
setDUsed(FlowAnalSymVector pVect)
|
void |
setImmediateDominatorForSubpFlow(BBlock pDominator)
|
void |
setImmediatePostdominatorForSubpFlow(BBlock pPostDominator)
|
void |
setIrLink(IR pIR)
|
void |
setPDef(DefVector pVect)
|
void |
setPDefined(FlowAnalSymVector pVect)
|
void |
setPEKill(ExpVector pVect)
|
void |
setPExposed(FlowAnalSymVector pVect)
|
void |
setPKill(DefVector pVect)
|
void |
setPLiveIn(FlowAnalSymVector pVect)
|
void |
setPLiveOut(FlowAnalSymVector pVect)
|
void |
setPostdomForSubpFlow(java.util.List pPostdom)
|
void |
setPostdominatedChildrenForSubpFlow(java.util.List pPostDominatedChildren)
|
void |
setPReach(DefVector pVect)
|
void |
setPUsed(FlowAnalSymVector pVect)
|
SetRefRepr |
setRefRepr(IR pIR)
Returns the SetRefRepr object enclosing the given IR. |
void |
setSetRefReprs(SetRefReprList pSetRefReprs)
Sets the SetRefReprList object that is the list of SetRefRepr objects, each of which wrap a statement/instruction. |
void |
setWork(java.lang.Object pWork)
|
java.lang.String |
toStringDetail()
toStringDetail: //##10 |
java.lang.String |
toStringShort()
toStringShort: //##10 |
メソッドの詳細 |
public int getBBlockNumber()
public IR getIrLink()
public void setIrLink(IR pIR)
public Label getLabel()
public SubpFlow getSubpFlow()
SubpFlow
object this BBlock
belongs to.
public FlowResults results()
FlowResults
object that holds data flow information.
public SetRefReprList getSetRefReprs()
SetRefReprList
object that is the list of SetRefRepr
objects, each of which wrap a statement/instruction.
public void setSetRefReprs(SetRefReprList pSetRefReprs)
SetRefReprList
object that is the list of SetRefRepr
objects, each of which wrap a statement/instruction.
public java.util.List getPredList()
public java.util.List getSuccList()
public Edge getPredEdge(BBlock pFromBBlock)
public Edge getSuccEdge(BBlock pToBBlock)
public boolean isEntryBBlock()
public boolean isExitBBlock()
public java.util.List getDomForSubpFlow()
BBlock
s that dominate this BBlock
in the SubpFlow
this BBlock
belongs to.
public void setDomForSubpFlow(java.util.List pDom)
BBlock
s that dominate this BBlock
in the SubpFlow
this BBlock
belongs to.
public java.util.List getStrictDomForSubpFlow()
BBlock
in the SubpFlow
this BBlock belongs to. A strict dominator is the dominator list minus the BBlock
itself.
public BBlock getImmediateDominatorForSubpFlow()
public void setImmediateDominatorForSubpFlow(BBlock pDominator)
public java.util.List getDominatedChildrenForSubpFlow()
public void setDominatedChildrenForSubpFlow(java.util.List pDominatedChildren)
public java.util.List getPostdomForSubpFlow()
public void setPostdomForSubpFlow(java.util.List pPostdom)
public java.util.List getStrictPostdomForSubpFlow()
public BBlock getImmediatePostdominatorForSubpFlow()
public void setImmediatePostdominatorForSubpFlow(BBlock pPostDominator)
public java.util.List getPostdominatedChildrenForSubpFlow()
public void setPostdominatedChildrenForSubpFlow(java.util.List pPostDominatedChildren)
public java.lang.Object getWork()
public void setWork(java.lang.Object pWork)
public BBlockSubtreeIterator bblockSubtreeIterator()
SetRefReprIterator
is the preferred method of iterating subtrees.
See SetRefReprIterator
public BBlockNodeIterator bblockNodeIterator()
public java.lang.String toStringShort()
public java.lang.String toStringDetail()
public void fuseSuccessor(BBlock pToBlock)
public void changeSuccEdge(BBlock pBefore, BBlock pAfter)
public void changePredEdge(BBlock pBefore, BBlock pAfter)
public void addEdge(Exp pConditionalExp, BBlock pToBlock)
public void deleteEdge(BBlock pToBlock)
public void deleteBBlock()
public void addToPredList(BBlock pPred)
public void addToSuccList(BBlock pSucc)
public void deleteFromPredList(BBlock pPred)
public void deleteFromSuccList(BBlock pSucc)
public DefVector getPDef()
public void setPDef(DefVector pVect)
public DefVector getDKill()
public void setDKill(DefVector pVect)
public DefVector getPKill()
public void setPKill(DefVector pVect)
public DefVector getPReach()
public void setPReach(DefVector pVect)
public FlowAnalSymVector getDDefined()
FlowAnalSym
s that are definitely defined in this BBlock
.
public void setDDefined(FlowAnalSymVector pVect)
public FlowAnalSymVector getPDefined()
FlowAnalSym
s whose value may have changed in this BBlock
..
public void setPDefined(FlowAnalSymVector pVect)
public FlowAnalSymVector getDUsed()
SetRefRepr
s (specified by SetRefRepr#getUseSyms()).
public void setDUsed(FlowAnalSymVector pVect)
public FlowAnalSymVector getPUsed()
public void setPUsed(FlowAnalSymVector pVect)
public FlowAnalSymVector getDExposed()
public void setDExposed(FlowAnalSymVector pVect)
public FlowAnalSymVector getPExposed()
public void setPExposed(FlowAnalSymVector pVect)
public ExpVector getDEGen()
FlowExpId
s that appear in this BBlock and the result of the computation of the expression of the FlowExpId can definitely be used at the end of this BBlock.
public void setDEGen(ExpVector pVect)
public ExpVector getPEKill()
FlowExpId
s whose operand set (specified by FlowExpId#getOperandSet()) intersects the Modified set of this BBlock
.
public void setPEKill(ExpVector pVect)
public ExpVector getDAvailIn()
public void setDAvailIn(ExpVector pVect)
public ExpVector getDAvailOut()
public void setDAvailOut(ExpVector pVect)
public FlowAnalSymVector getPLiveIn()
public void setPLiveIn(FlowAnalSymVector pVect)
public FlowAnalSymVector getPLiveOut()
public void setPLiveOut(FlowAnalSymVector pVect)
public FlowAnalSymVector getDDefIn()
public void setDDefIn(FlowAnalSymVector pVect)
public FlowAnalSymVector getDDefOut()
public void setDDefOut(FlowAnalSymVector pVect)
public boolean isDDef(SetRefRepr pSetRefRepr)
public boolean isPDef(SetRefRepr pSetRefRepr)
public boolean isDKill(SetRefRepr pSetRefRepr)
public boolean isPKill(SetRefRepr pSetRefRepr)
public boolean isPReach(SetRefRepr pSetRefRepr)
public boolean isDDefined(Sym pSym)
public boolean isPDefined(Sym pSym)
public boolean isDUsed(Sym pSym)
public boolean isPUsed(Sym pSym)
public boolean isDExposed(Sym pSym)
public boolean isPExposed(Sym pSym)
public boolean isDEGen(FlowExpId pExpId)
public boolean isPEKill(FlowExpId pExpId)
public boolean isDAvailIn(FlowExpId pExpId)
public boolean isDAvailOut(FlowExpId pExpId)
public boolean isPLiveIn(Sym pSym)
public boolean isPLiveOut(Sym pSym)
public boolean isDDefIn(Sym pSym)
public boolean isDDefOut(Sym pSym)
public SetRefRepr setRefRepr(IR pIR)
SetRefRepr
object enclosing the given IR.
|
||||||||||
前のクラス 次のクラス | フレームあり フレームなし | |||||||||
概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド |