|
||||||||||
| 前のクラス 次のクラス | フレームあり フレームなし | |||||||||
| 概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド | |||||||||
Flow interface
Interface for flow analysis.
See also interfaces SubpFlow, BBlock, LoopInf, and BitVector.
Interface hierarchy concerning flow analysis ** ()
Flow
SubpFlow
|- HirSubpFlow
|- LirSubpFlow
BBlock
Edge
BBlockSubtreeIterator
BBlockNodeIterator
BitVector
|- ExpVector
|- PointVector
|- DefVector
ExpVectorIterator
PointVectorIterator
DefUseCell
DefUseList
FlowIrLinkCell
Class hierarchy concerning flow analysis **
Root
|- FlowImpl implements Flow
|- SubpFlowImpl implements SubpFlow
| |- HirSubpFlowImpl implements HirSubpFlow
| |- LirSubpFlowImpl implements LirSubpFlow
|
|- BBlockImpl implements BBlock
|- EdgeImpl implement Edge
|
|- BBlockSubtreeIteratorImpl implements BBlockSubtreeIterator
|- BBlockNodeIteratorImpl implements BBlockNodeIterator
|- BitVectorImpl implements BitVector
| |- ExpVectorImpl implements DefVector
| |- PositionVectorImpl implements PositionVector
| |- DefVectorImpl implements DefVector
|- BitVectorIteratorImpl implements BitVectorIterator
| |- ExpVectorIteratorImpl implements ExpVectorIterator
| |- PositionVectorIteratorImpl implements PositionVectorIterator
|
|- DefUseCellImpl implements DefUseCell
|- DefUseListImpl implements DefUseCell
|- FlowIrLinkCellImpl implements FlowIrLinkCell
Position of flow analysis in compiling process ** ()
Compiler set up;
Front {
Translate all subprograms in a compile unit into HIR; }
Prepare for HIR flow analysis {
FlowRoot hirFlowRoot = new FlowRoot(hirRoot); }
for each subprogram definition lSubpDef do {
hirFlowRoot.controlFlow
= hirFlowRoot.flow.controlFlowAnal(lSubpDef);
hirFlowRoot.dataFlow
= hirFlowRoot.flow.dataFlowAnal(lSubpDef);
Do HIR transformations for optimization or parallelization;
}
Caution:
Result of data flow may be incorrect if flow analysis of all
subprogram is done and then the result of flow analysis
is used, because data flow information of global variables may
reflect the data for the last subprogram, not the subprogram
under processing.
Control flow analysis and data flow analysis ** ()
Control flow analysis and data flow analysis are done
based on the graph of basic blocks in each subprogram.
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 structure of basic blocks is explained
in the interface BBlock.
The flow information (either control flow or data flow) can be
got by methods of SubpFlow which corresponds to each subprogram.
The SubpFlow can be accessed by subp.getSubpFlow()
where subp is a subprogram. (The SubpFlow computed last is active.)
Detailed information for each basic block can be got by
methods in BBlock.
The BBlock can be got by subpFlow.getEntryBBlock() or
subp.getEntryBBlock() where subpFlow is SubpFlow of some
subprogram. Other BBlocks can be reached by traversing
the contro flow graph (see cfgIterator of SubpFlow).
The control flow is based on predecessor/successor relation
of basic blocks in either HIR or LIR.
Elementary information of the data flow is indexed by symbol
number or node number in either HIR or LIR.
Each basic block is assigned a source label or internal label.
The first top-subtree is either LabeledStmt in HIR or
DefLabel in LIR.
The graph of basic blocks can be gotten from subprogram symbol
(using getEntryBBlock, getDefUseList, getFlowInf, etc.).
Some methods for accessing flow information:
getIndex() in Sym : get the index of a symbol .
getNodeIndex() in HIR : get the node index of HIR or LIR.
getBBlock() in Label : get BBlock to which this label is attached.
getIndexedSym(int pSymIndex) in SubpFlow : get Sym from sym-index.
getIndexedNode(int pNodeIndex) in SubpFlow
: get IR node from node index.
getBBlock(int pBBlockNumber) in SubpFlow
: get BBlock from BBlock number.
cfgIterator() in SubpFlow :
: used in traversing BBlock in DFO from entry BBlock.
cfgFromExitIterator() in SubpFlow :
: used in traversing BBlock from exit BBlock.
symListIterator() in SubpFlow :
: traverse symbols accessed in the subprogram.
bblockSubtreeIterator in BBlock
: used in traversing top-subtrees in BBlock.
bblockNodeIterator in BBlock
: used in traversing all IR nodes in BBlock.
setPointVectorLeng(int pBitLeng) in SubpFlow
: set length of bit vectors for PointVector.
setExpVectorLeng(int pBitLeng) in SubpFlow
: set length of bit vectors for ExpVector.
isDefined(Sym pSym) in BBlock: pSym is defned in the BBlock.
isUsed (Sym pSym) in BBlock: pSym is used in the BBlock.
isLiveIn (Sym pSym) in BBlock: pSym is in LiveIn in the BBlock.
getReach() in BBlock: get bit vector showing reaching definition.
....
Data flow information of HIR is destroied when
LIR flow analysis is performed. HIR data flow information
is not valid when LIR data flow analysis is performed. ()
Relation between control flow and data flow: ()
Methods listed in BBlock 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 in BBlock.)
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.
Basic data flow information:
In the implementation of data flow analysis, each variable
and each register are assigned a unique index number to identify
them in data structures for flow analysis. Each program point
defining or using variables and registers is assigned a unique
position number to identify it quickly.
Each expression is assigned an expression identifier
if the expression has r-value or l-value.
If two expressions has the same form then
the corresponding expression identifier is the same.
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 defined.
use(x) : shows that x is used.
p(def(x)) : value of x is defined at program point p.
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.
Def(B) =
{ p | for some x, p(def(x)) is included in B and after
that point there is no def(x) in B. }
Kill(B) =
{ p | for some x, p(def(x)) is included in B'
(where, B' != B) and there exists some defining
point of x p'(def(x)) in B. }
Reach(B)=
{ p | there is some path from program point p
defining x (that is p(def(x))) to the entry of B
such that there is no p'(def(x)) on that path. }
Reach(B) = or_all( (Def(B') | (Reach(B') - Kill(B')))
for all predecessors B' of B)
Defined(B) =
{ x | x is set in B. }
Used(B) =
{ x | x is used in B. }
Exposed(B) =
{ x | x is used in B and x is not set in B
before x is used. }
EGen(B) =
{ op(x,y) | expression op(x,y) is computed in B and after
that point, neither x nor y are set in B. }
Thus, the result of op(x,y) is available after B.
EKill(B) =
{ op(x,y) | operand x or y is defined 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.
AvailIn(B) =
{ op(x,y) | op(x,y) is computed in every paths to B and
x, y are not set after the computations
on the paths. }
Thus, the result of op(x,y) can be used without
re-evaluation in B.
AvailOut(B) =
{ op(x,y) | op(x,y) is computed in B and after that
point, x, y are not set in B. }
Thus, op(x,y) can be used without re-evaluation after B.
Following relations hold.
AvailIn(B) = and_all(AvailOut(B') for all predecessors
B' of B) if B is not an entry block;
AvailIn(B) = { } if B is an entry block.
AvailOut(B) = EGen(B) | (AvailIn(B) - EKill(B))
LiveIn(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 set. }
LiveOut(B) =
{ x | x is live at exit from B, that is, there is some
path from B to B' where x is in Exposed(B'). }
Following relations hold.
LiveOut(B) = or_all(LiveIn(B') for all successors B' of B)
LiveIn(B) = Exposed(B) | (LiveOut(B) - Defined(B))
DefIn(B) =
{ x | x is always defined at entry to B whichever path
may be taken. }
DefIn(B) = and_all(DefOut(B') for all predecessors B' of B)
DefOut(B) =
{ x | x is always defined at exit from B whichever path
may be taken.}
DefOut(B) = Defined(B) | DefIn(B)
In the computation of EGen, EKill, AvailIn, AvailOut,
the result of alias analysis is used unconditionally.
In the computation of Defined and Used, the result of
alias analysis is not used. How to use alias information
such as the set of symbols that may be aliased to a variable.
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.
PosVector 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.
ExpVector is a bit vector representing 0/1 information
for each symbol such as variable or register. An expression is
represented by the index number assigned to an abstract register
corresponding to the expression. If ExpVector 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.
| フィールドの概要 | |
static int |
STATE_CFG_AVAILABLE
|
static int |
STATE_CFG_RESTRUCTURING
|
static int |
STATE_DATA_FLOW_AVAILABLE
|
static int |
STATE_DATA_UNAVAILABLE
|
static int |
STATE_HIR_FLOW_AVAILABLE
|
static int |
STATE_LIR_FLOW_AVAILABLE
|
| メソッドの概要 | |
ControlFlow |
controlFlow()
|
ControlFlow |
controlFlowAnal(SubpFlow pSubpFlow)
controlFlowAnal Do control flow analysis of the subprogram specified by pSubpFlow, i.e. |
DataFlow |
dataFlow()
|
DataFlow |
dataFlowAnal()
|
DataFlow |
dataFlowAnal(SubpDefinition pSubpDef)
dataFlowAnal // REFINE comment. |
void |
dbg(int level,
java.lang.Object pObject)
|
void |
dbg(int level,
java.lang.String pHeader,
java.lang.Object pObject)
|
void |
doHir()
Do control flow analysis and data flow analysis. |
int |
getFlowAnalStateLevel()
|
SubpFlow |
getSubpFlow()
|
Subp |
getSubpUnderAnalysis()
getSubpFlow Get currently effective SubpFlow information. |
void |
resetAllFlowInf(Subp pSubp)
|
void |
setFlowAnalStateLevel(int pStateLevel)
|
| フィールドの詳細 |
public static final int STATE_DATA_UNAVAILABLE
public static final int STATE_CFG_RESTRUCTURING
public static final int STATE_CFG_AVAILABLE
public static final int STATE_DATA_FLOW_AVAILABLE
public static final int STATE_HIR_FLOW_AVAILABLE
public static final int STATE_LIR_FLOW_AVAILABLE
| メソッドの詳細 |
public ControlFlow controlFlowAnal(SubpFlow pSubpFlow)
public void resetAllFlowInf(Subp pSubp)
public DataFlow dataFlowAnal(SubpDefinition pSubpDef)
public SubpFlow getSubpFlow()
public DataFlow dataFlow()
public DataFlow dataFlowAnal()
public int getFlowAnalStateLevel()
public void setFlowAnalStateLevel(int pStateLevel)
public Subp getSubpUnderAnalysis()
public ControlFlow controlFlow()
public void doHir()
public void dbg(int level,
java.lang.String pHeader,
java.lang.Object pObject)
public void dbg(int level,
java.lang.Object pObject)
|
||||||||||
| 前のクラス 次のクラス | フレームあり フレームなし | |||||||||
| 概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド | |||||||||