|
||||||||||
前のクラス 次のクラス | フレームあり フレームなし | |||||||||
概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド |
java.lang.Object | +--coins.aflow.Flow
Representation of data flow information: Each expression is assigned an expression identifier (FlowExpId) if the expression has a value (such as r-value or l-value). If two expressions has the same form then the corresponding expression identifier is the same. Interface hierarchy: BitVector |- BBlockVector -- for BBlock |- ExpVector -- for expression |- FlowAnalSymVector -- for symbol |- PositionVector -- for def/use point |- DefVector -- for definition point BitVectorIterator |- ExpVectorIterator -- traverses all expressions | that have true bit in a given bit vector. |- FlowAnalSymVector -- traverses all symbols that have true bit in a given bit vector. |- PositionVectorIterator -- traverses all true def/use nodes |- DefVectorIterator -- traverses all def nodes Class hierarchy: BitVectorImpl extends Root implements BitVector |- BBlockVectorImpl implements BBlockVector |- ExpVectorImpl implements ExpVector |- FlowAnalSymVector implements FlowAnalSymVector |- PositionVectorImpl implements PositionVector |- DefVectorImpl implements DefVector BitVectorIteratorImpl implements BitVectorIterator |- ExpVectorIteratorImpl implements ExpVectorIterator |- FlowAnalSymVectorIteratorImpl implements FlowAnalSymVector |- PositionVectorIteratorImpl implements PositionVectorIterator |- DefVectorIteratorImpl implements DefVectorIterator Basic data flow information is as follows: Notations x, y, t, u : variable or register representing an operand. op : operator. def(x) : shows that value of x is definitely defined. mod(x) : shows that value of x is posibly defined. use(x) : shows that x is used. p(def(x)) : value of x is (definitely) modified (i.e. via assign) at program point p. p(mod(x, y, ...)) : value of x, y, ... are modified at program point p (modified means possibly changed). p(use(x)) : x is used at program point p. or_all(z) : construct a set by applying or-operation on all components indicated by z. and_all(z) : construct a set by applying and-operation on all components indicated by z. PDef(B) = { p | p(mod(x, y, ...)) is included in B and after that point there is no p' s.t. p'(def(x)) nor p" s.t. p"(def(y)), ... in B. } DKill(B) = { p | p(def(x)) is not included in B and p'(def(x)) is included in B. } PReach(B)= { p | there is some path from program point p that modifies some variables x, y, ... (that is, p(mod(x, y, ...))) to the entry of B such that there is no p'(def(x)) or no p''(def(y)) or ... on that path. } PReach(B) = or_all( (PDef(B') | (PReach(B') - DKill(B'))) for all predecessors B' of B) DDefined(B) = { x | x is definitely modified in B. } PDefined(B) = { x | x is posibly modified in B. } PExposed(B) = { x | x is possibly used in B and x is not definitely set in B before x is used. } PUsed(B) = {x|x is possibly used in B} DEGen(B) = { op(x,y) | expression op(x,y) is computed in B and after that point, neither x nor y are possibly set in B. } Thus, the result of op(x,y) is available after B. PEKill(B) = { op(x,y) | operand x or y is possibly modified in B and the expression op(x,y) is not re-evaluated after that definition in B. } If t = op(x,y) is killed in B, then op(t,u) should also be killed in B. DAvailIn(B) = { op(x,y) | op(x,y) is computed in every paths to B and x, y are not modified after the computations on the paths. } Thus, the result of op(x,y) can be used without re-evaluation in B. DAvailOut(B) = { op(x,y) | op(x,y) is computed in every paths to the exit of B and x, y are not modified after the computations on the paths. } Thus, op(x,y) can be used without re-evaluation after B. Following relations hold. DAvailIn(B) = and_all(DAvailOut(B') for all predecessors B' of B) if B is not an entry block; DAvailIn(B) = { } if B is an entry block. DAvailOut(B) = DEGen(B) | (DAvailIn(B) - PEKill(B)) PLiveIn(B) = { x | x is alive at entry to B, that is, on some path from entrance point of B to use point of x, x is not definitely set. } Thus, x in PLiveIn(B) should not be changed until it is used. PLiveOut(B) = { x | x is live at exit from B, that is, there is some path from B to B' where x is in PExposed(B'). } Following relations hold. PLiveOut(B) = or_all(PLiveIn(B') for all successors B' of B PLiveIn(B) = PExposed(B) | (PLiveOut(B) - DDefined(B)) DDefIn(B) = { x | x is always defined at entry to B whichever path may be taken. } DDefIn(B) = and_all(DDefOut(B') for all predecessors B' of B) DDefOut(B) = { x | x is always defined at exit from B whichever path may be taken.} DDefOut(B) = DDefined(B) | DefIn(B) Data structure There are several ways of representing data flow information such as bit vector representation and discrete list representation. When a new data flow information is introduced, it will be necessary to solve new data flow equation concerning it. For that purpose, several methods treating bit vector data structures are provided. By using these methods and methods in BitVectorInterface, we will be able to solve new data flow equation and to access the new data flow information. In the bit vector representation, information can be accessed by position number of IR nodes and index number of symbols which can be get from IR node or symbol table each respectively. BBlockVector is a bit vector representing 0/1 information for each BBlock. DefVector is a bit vector representing 0/1 information for each value-setting node. If its value at position p is 1, true is represented for the IR node at p, if it is 0, false is represented at that node. PointVector is a bit vector representing 0/1 information for each IR node. If its value at position p is 1, true is represented for the IR node at p, if it is 0, false is represented at that node. FlowAnalSymVector is a bit vector representing 0/1 information for each symbol such as variable or register. A symbol is assigned a local index. By local I mean it is unique within a subprogram. If FlowAnalSymVector value at position i is 1, true is represented for the symbol having index number i, if it is 0, false is represented for that symbol. ExpVector is a bit vector representing 0/1 information for each unique expression. Expressions having the same form are assigned the same local object (FlowExpId). An expression is represented by the index number assigned to the FlowExpId corresponding to the expression. If an ExpVector's n-th bit is 1, true is represented for the expression having the FlowExpId object whose index is i. All the indexes such as symbol indexes are numbered 1, 2, 3, ... . If such numbering is not yet performed, the index value will be 0. Position 0 in the bit vectors is not used. Usage Bit vector class having definite bit length should be defined as a subclass of BitVector. Its procedure for a subprogram is as follows: // Flow Analyzer Initiation Assign index number to symbols accessed in the subprogram; Assign index number to FlowExpIds representing expression; // Individual Flow Analyses Required for the Optimization to Perform Instantiate DefVectors by SubpFlow#defVector(); Instantiate ExpVectors by SubpFlow#expVector(); Manipulate the bit vectors by using methods for BitVector operation; Instantiate DefVectorIterator for some DefVector by SubpFlow#defVectorIterator(); Scan all nodes having true bit in the DefVector by using the DefVectorIterator. Instantiate ExpVectorIterator for some ExpVector by flowRoot.subpFlow.expVectorIterator(); Scan all symbols or expressions having true bit in the ExpVector by using the ExpVectorIterator.
This class itself is a demo driver class for flow analysis modules. In real world, each flow analysis module is called on demand by higher level modules. See { coins.aflow.util.SelfCollectingResults}.
フィールドの概要 | |
Flow |
flow
|
FlowRoot |
flowRoot
|
protected SubpFlow |
fSubpFlow
|
HirRoot |
hirRoot
|
IoRoot |
ioRoot
|
コンストラクタの概要 | |
Flow(FlowRoot pFlowRoot)
|
メソッドの概要 | |
AssignFlowExpId |
assigner(SubpFlow pSubpFlow)
|
BBlockHir |
bblock(LabeledStmt pLabeledStmt,
HirSubpFlow pHirSubpFlow)
|
BBlockSubtreeIterator |
bblockSubtreeIterator(BBlock pBBlock)
|
BBlockVector |
bblockVector(SubpFlow pSubpFlow)
|
static boolean |
checkTreeStructure(HIR pHIR,
IoRoot pIoRoot)
Checks if the tree structure under the given HIR node is valid. |
void |
dbg(int level,
java.lang.Object pObject)
|
void |
dbg(int level,
java.lang.String pHeader,
java.lang.Object pObject)
|
DefUseCell |
defUseCell(IR pDefNode)
|
DefUseList |
defUseList()
|
DefVector |
defVector(SubpFlow pSubpFlow)
|
void |
doHir()
Performs various HIR flow analyses. |
void |
doHir0(SubpDefinition subpDef,
FlowResults lResults,
SubpFlow lSubpFlow)
|
int |
doHirForC()
Assuming the input program is C, give some warnings. |
void |
doLir()
Performs various LIR flow analyses. |
Edge |
edge(BBlock pFrom,
BBlock pTo)
|
ExpVector |
expVector(SubpFlow pSubpFlow)
|
FlowAnalSymVector |
flowAnalSymVector(SubpFlow pSubpFlow)
|
SubpFlow |
getSubpFlow()
|
static boolean |
isExecutable(IR pIR)
Returns true if the given node is thought of as executable, giving grounds to what would be returned by getNextExecutableNode() in BBlockNodeIterator. |
void |
message(int level,
java.lang.String mes)
|
PointVector |
pointVector(SubpFlow pSubpFlow)
|
FlowResults |
results()
|
SetRefRepr |
setRefRepr(Stmt pStmt,
BBlockHir pBBlockHir)
|
SetRefReprList |
setRefReprList(BBlock pBBlock)
|
void |
setSubpFlow(SubpFlow pSubpFlow)
|
SubpFlow |
subpFlow(SubpDefinition pSubpDef,
FlowResults pResults)
|
void |
test()
|
UDChain |
udChain(IR pUseNode)
|
UDList |
udList()
|
(パッケージプライベート) void |
warning(java.lang.String mes)
output warning message. |
クラス java.lang.Object から継承したメソッド |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
フィールドの詳細 |
public final FlowRoot flowRoot
public final HirRoot hirRoot
public final IoRoot ioRoot
public final Flow flow
protected SubpFlow fSubpFlow
コンストラクタの詳細 |
public Flow(FlowRoot pFlowRoot)
メソッドの詳細 |
public int doHirForC()
public void doHir()
public void doHir0(SubpDefinition subpDef, FlowResults lResults, SubpFlow lSubpFlow)
public void doLir()
public static boolean isExecutable(IR pIR)
public static boolean checkTreeStructure(HIR pHIR, IoRoot pIoRoot)
public void dbg(int level, java.lang.String pHeader, java.lang.Object pObject)
public void dbg(int level, java.lang.Object pObject)
public void message(int level, java.lang.String mes)
void warning(java.lang.String mes)
mes
- warning messagepublic void test()
public AssignFlowExpId assigner(SubpFlow pSubpFlow)
public BBlockHir bblock(LabeledStmt pLabeledStmt, HirSubpFlow pHirSubpFlow)
public BBlockSubtreeIterator bblockSubtreeIterator(BBlock pBBlock)
public BBlockVector bblockVector(SubpFlow pSubpFlow)
public DefUseCell defUseCell(IR pDefNode)
public DefUseList defUseList()
public DefVector defVector(SubpFlow pSubpFlow)
public Edge edge(BBlock pFrom, BBlock pTo)
public ExpVector expVector(SubpFlow pSubpFlow)
public FlowAnalSymVector flowAnalSymVector(SubpFlow pSubpFlow)
public PointVector pointVector(SubpFlow pSubpFlow)
public FlowResults results()
public SetRefRepr setRefRepr(Stmt pStmt, BBlockHir pBBlockHir)
public SetRefReprList setRefReprList(BBlock pBBlock)
public SubpFlow subpFlow(SubpDefinition pSubpDef, FlowResults pResults)
public UDChain udChain(IR pUseNode)
public UDList udList()
public SubpFlow getSubpFlow()
public void setSubpFlow(SubpFlow pSubpFlow)
|
||||||||||
前のクラス 次のクラス | フレームあり フレームなし | |||||||||
概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド |