coins.aflow
クラス Flow

java.lang.Object
  |
  +--coins.aflow.Flow

public class Flow
extends java.lang.Object

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
 

フィールドの詳細

flowRoot

public final FlowRoot flowRoot

hirRoot

public final HirRoot hirRoot

ioRoot

public final IoRoot ioRoot

flow

public final Flow flow

fSubpFlow

protected SubpFlow fSubpFlow
コンストラクタの詳細

Flow

public Flow(FlowRoot pFlowRoot)
メソッドの詳細

doHirForC

public int doHirForC()
Assuming the input program is C, give some warnings.


doHir

public void doHir()
Performs various HIR flow analyses. The command line switches determine which analyses to perform. See coins.FlowRoot.


doHir0

public void doHir0(SubpDefinition subpDef,
                   FlowResults lResults,
                   SubpFlow lSubpFlow)

doLir

public void doLir()
Performs various LIR flow analyses. The command line switches determine which analyses to perform. See coins.FlowRoot.


isExecutable

public 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.


checkTreeStructure

public static boolean checkTreeStructure(HIR pHIR,
                                         IoRoot pIoRoot)
Checks if the tree structure under the given HIR node is valid.


dbg

public void dbg(int level,
                java.lang.String pHeader,
                java.lang.Object pObject)

dbg

public void dbg(int level,
                java.lang.Object pObject)

message

public void message(int level,
                    java.lang.String mes)

warning

void warning(java.lang.String mes)
output warning message.

パラメータ:
mes - warning message

test

public void test()

assigner

public AssignFlowExpId assigner(SubpFlow pSubpFlow)

bblock

public BBlockHir bblock(LabeledStmt pLabeledStmt,
                        HirSubpFlow pHirSubpFlow)

bblockSubtreeIterator

public BBlockSubtreeIterator bblockSubtreeIterator(BBlock pBBlock)

bblockVector

public BBlockVector bblockVector(SubpFlow pSubpFlow)

defUseCell

public DefUseCell defUseCell(IR pDefNode)

defUseList

public DefUseList defUseList()

defVector

public DefVector defVector(SubpFlow pSubpFlow)

edge

public Edge edge(BBlock pFrom,
                 BBlock pTo)

expVector

public ExpVector expVector(SubpFlow pSubpFlow)

flowAnalSymVector

public FlowAnalSymVector flowAnalSymVector(SubpFlow pSubpFlow)

pointVector

public PointVector pointVector(SubpFlow pSubpFlow)

results

public FlowResults results()

setRefRepr

public SetRefRepr setRefRepr(Stmt pStmt,
                             BBlockHir pBBlockHir)

setRefReprList

public SetRefReprList setRefReprList(BBlock pBBlock)

subpFlow

public SubpFlow subpFlow(SubpDefinition pSubpDef,
                         FlowResults pResults)

udChain

public UDChain udChain(IR pUseNode)

udList

public UDList udList()

getSubpFlow

public SubpFlow getSubpFlow()

setSubpFlow

public void setSubpFlow(SubpFlow pSubpFlow)