coins.opt
クラス PRE

java.lang.Object
  |
  +--coins.opt.CommonSubexpElim
        |
        +--coins.opt.CommonSubexpElimHir
              |
              +--coins.opt.CommonSubexpElimHirE
                    |
                    +--coins.opt.PRE

public class PRE
extends CommonSubexpElimHirE

PRE

 Partial redundancy elimination.
 This is invoked when option -coins:hirOpt=pre is given.
 See
   I. Nakata: Compiler Construction and Optimization, Asakura Shoten, 1999.
   D. M. Dhamdhere: E-path_PRE - Partial Redundance Elimination Made Easy,
   SIGPLAN Notices, Vol. 37(8), pp.53-65 (Aug. 2002).

 Symbols and equations according to the E-path_PRE:
 -------------------------------------------------
   locally available   // EGen (downward exposed)
       // e is computed and after the computation, operands are not changed.
   available   // DAvailIn
       // e is already computed on any path to this basic block and
       // after the computation, its operands are not changed.
   partially available //
   locally anticipable // AntLoc (upward exposed)
       // e appeares in this basic block and its operands are not set in
       // preceeding operations (before use) in the basic block.
   safe  // Either anticipable or available.
   e-path([b_i ... b_k]) = set of eliminatable computation e included
  in b_k, i.e.
  {e | e is locally available in b_i
   and locally anticipable in b_k } &
   empty((b_i ... b_k)) &  // not computed in intermediate point
   e is safe at exit of each node on the path [b_i ... b_k),
  where, b_i, ..., b_k are basic block i, ..., basic block k, respectively.
  e-path suffix is the maximal suffix of an E-path such that
  AntIn * (not AvIn) = true for each node in it.
 Data flow properties
 --------------------
   Comp_i  : e is locally available in b_i
   Antloc_i  : e is locally anticipable in b_i
   Transp_i  : b_i does not contain definitions of e's operands
   AvIn_i  : e is available at entry of b_i
   AvOut_i   : e is available at exit  of b_i
   AntIn_i   : e is anticipable at entry of b_i
   AntOut_i  : e is anticipable at exit  of b_i
   EpsIn_i   : entry of b_i is in an e-path suffix
   EpsOut_i  : exit  of b_i is in an e-path suffix
   Redund_i  : Occurrence of e in b_i is redundant
   Insert_i  : Insert t_e := e in node b_i
   Insert_i_j : Insert t_e := e along edge (b_i, b_j)
   SaIn_i  : A Save must be inserted above the entry of b_i
   SaOut_i   : A Save must be inserted above the exit  of b_i
   Save_i  : e should be saved in t_e in node b_i
  where, t_e is a temporal variable to hold the value of e.
 Data flow equations
 -------------------
   AvIn_i    = PAI_p (AvOut_p)
   AvOut_i   = AvIn_i * Transp_i + Comp_i
   AntIn_i   = AntOut_i * Transp_i + Antloc_i
   AntOut_i  = PAI_s (AntIn_s)
   EpsIn_i   = (SIGMA_p (AvOut_p + EpsOut_p)) * AntIn_i * (not AvIn_i)
   EpsOut_i  = EpsIn_i * (not Antloc_i)
   Redund_i  = (EpsIn_i + AvIn_i) * Antloc_i
   Insert_i  = (not AvOut_i) * (not EpsOut_i) * PAI_s(EpsIn_s)
   Insert_i_j = (not AvOut_i) * (not EpsOut_i) * (not Insert_i) * EpsIn_j
   SaOut_i   = SIGMA_s (EpsIn_s + Redund_s + SaIn_s) * AvOut_i
   SaIn_i    = SaOut_i * (not Comp_i)
   Save_i    = SaOut_i * Comp_i * (not (Redund_i * Transp_i))
  where, _s means successor and _p means predecessor.

 Optimization using E-path_PRE is done by
   Save the value of e: computation t_e is inserted before an
   occurence of e and the occurrence of e is replaced by t_e
   (as indicated by Save_i).
   Insert an evaluation of e: A computation t_e = e; is inserted
   (as indicated by Insert_i and Insert_i_j).
   Eliminate a redundant evaluation of e: An occurrence of e is
   replaced by t_e (as indicated by Redund_i).
 


フィールドの概要
(パッケージプライベート)  ExpVector fAllOne
           
(パッケージプライベート)  ExpVector fAllZero
           
(パッケージプライベート)  ExpVector[] fAntIn
           
(パッケージプライベート)  ExpVector[] fAntloc
           
(パッケージプライベート)  ExpVector[] fAntOut
           
(パッケージプライベート)  ExpVector[] fAvailIn
           
(パッケージプライベート)  ExpVector[] fAvailOut
           
(パッケージプライベート)  ExpVector[] fComp
           
(パッケージプライベート)  CompileThread fCompileThread
           
(パッケージプライベート)  boolean fCompileTime
           
(パッケージプライベート)  ExpVector[] fEpsIn
           
(パッケージプライベート)  ExpVector[] fEpsOut
           
(パッケージプライベート)  ExpVector[] fInsert
           
(パッケージプライベート)  java.util.List[] fInsertEdge
           
 Flow flow
           
(パッケージプライベート)  ExpVector[] fRedund
           
protected  boolean fRegularSubp
           
(パッケージプライベート)  ExpVector[] fSave
           
(パッケージプライベート)  ExpVector[] fSaveIn
           
(パッケージプライベート)  ExpVector[] fSaveOut
           
protected  ShowDataFlow fShowFlow
           
protected  SubpDefinition fSubpDef
           
protected  boolean fSubsPtr
           
(パッケージプライベート) static long fTimeInMillis
           
protected  int fTraceLevel
           
(パッケージプライベート)  ExpVector[] fTransp
           
 IoRoot ioRoot
           
 
クラス coins.opt.CommonSubexpElimHirE から継承したフィールド
fAlias, fAvailableExps, fAvailableTemps, fBeforePRE, fExpCost, fIndexMax, fIndexMin, fLatestNodeForExpId, fRecordAlias, fReplacedNodes, fThreshold
 
クラス coins.opt.CommonSubexpElimHir から継承したフィールド
fGlobalExpTempMap, fGlobalTempExpMap, hir
 
クラス coins.opt.CommonSubexpElim から継承したフィールド
fDbgLevel, fFunctionsWithoutSideEffect, flowRoot, fSubpFlow, sym, symRoot
 
コンストラクタの概要
PRE(SubpFlow pSubpFlow, SubpDefinition pSubpDef, boolean pSubsPtr, int pThreshold)
          PRE Construct an instance of PRE for specified subprogram.
 
メソッドの概要
 void addFirstStmtOfBBlock(Stmt pStmt, BBlock pBBlock)
           
 void addLastStmtOfBBlock(Stmt pStmt, BBlock pBBlock)
           
protected  void collectTempsUsedInReplacement()
           
protected  ExpVector computeAntloc(BBlock pBBlock)
          Compute AntLoc for pBBLock, that is, expressions whose operands are not set by preceeding operations in pBBlock.
 boolean doPRE()
          doPRE Do partial redundancy elimination for the PRE instance.
protected  boolean eliminateRedundantExpressions()
           
protected  Exp findExpWithExpId(HIR pHir, ExpId pExpId)
          findNodeWithExpId Find node with pExpId in the subtree pHir.
protected  void initiateDataFlowInformation()
          initiateDataFlowInformation Initiate data flow information required to solve the data flow equations given by Dhamdhere.
 void insertHeadStmtCaringBranch(BBlock pBBlock, Stmt pStmt)
          Insert pStmt as the head Stmt of pBBlock.
 void insertTailStmtCaringBranch(BBlock pBBlock, Stmt pStmt)
          Add pStmt at the tail of pBBlock.
 void insertToEdge(BBlock pFrom, BBlock pTo, Stmt pStmt)
          insertToEdge There are following cases in the relations of edge and basic blocks: case 1: pFrom has only 1 successor pTo and pTo has only one predecessor; case 2: pFrom has only 1 successor pTo and pTo has multiple prececessor; case 3: pFrom has multiple successor and pTo has only 1 predecessor; case 4: pFrom has multiple successor and pTo has multiple predecessor; In case 1 and case 2, the operation to be inserted should be placed as the last statement (before unconditional goto) of pFrom BBlock.
 boolean isConditionalExpOfControlStmt(HIR pHir)
          Return true if pHir is a conditional expression of control statement (IfStmt, LoopStmt, SwitchStmt) or return true if its parent is a LabeledStmt that is a conditional expression part of control statement.
protected  boolean isRegisterizableExp(HIR pHir)
          Decide whether pHir is an expression that can be replaced by a register containing the value of the expression.
protected  boolean localCommonSubexpElimination()
           
 Stmt makeAssignStmt(Var pVar, Exp pExp)
          makeAssignStmt Make assign statement pVar = pExp.copyWithOperands()
protected  boolean normalizeHir()
           
protected  void printExpVectorArray(java.lang.String pHeader, ExpVector[] pVectorArray)
           
protected  void printExpVectorArray2(java.lang.String pHeader1, ExpVector[] pVectorArray1, java.lang.String pHeader2, ExpVector[] pVectorArray2)
           
 long printTimeInMillis(java.lang.String pHeader, boolean pPrint, boolean pMonitor)
          printTimeInMillis prints the current time if required.
 void replaceExpWithTemp(Exp pExp, Var pVar)
           
protected  void selectExpsForPRE()
          selectExpForPRE Select expressions listed up as redundant exp in some basic block and their cost is greater or equal to fThreshold.
(パッケージプライベート)  void selectLargestRedundantExps(HIR pHir, java.util.Set pRedundantExps, java.util.Set pSelectedExps, BBlock pBBlock)
          selectLargestRedundantExps selects ExpIds representing largest redundant expressions in the given HIR subtree pHir.
(パッケージプライベート)  void selectLargestRedundantExpsInBBlock(java.util.Set pRedundantExps, java.util.Set pSelectedExps, BBlock pBBlock)
          selectLargestRedundantExpsInBBlock selects redundant expressions that are not included in larger redundant expression in the specified basic block pBBlock.
protected  void solveDataFlowEquations()
           
protected  boolean subscriptToPointerTransformation(java.util.Map pPtrSubsCorrespondence)
          preparatoryTransformation Remove critical edges.
 
クラス coins.opt.CommonSubexpElimHirE から継承したメソッド
adjustAvailability, containsCall, dbg, dbg, doBBlockLocal, estimateExpCost, getLatestCall, getLatestNodeOfExp, insertTheStatement, replaceAvailableExp, replaceExp, replaceTheExpression, toBeExcluded, tryToEliminateExp, tryToEliminateSubexp, tryToReplaceSubexp
 
クラス coins.opt.CommonSubexpElimHir から継承したメソッド
eliminateComplex, eliminateSimple, operandSet, recordTempExpCorrespondence, registerUseSyms, reregisterSubexps
 
クラス coins.opt.CommonSubexpElim から継承したメソッド
doBBlockLocal
 
クラス java.lang.Object から継承したメソッド
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

フィールドの詳細

ioRoot

public final IoRoot ioRoot

flow

public final Flow flow

fShowFlow

protected ShowDataFlow fShowFlow

fSubpDef

protected SubpDefinition fSubpDef

fRegularSubp

protected boolean fRegularSubp

fSubsPtr

protected boolean fSubsPtr

fTraceLevel

protected int fTraceLevel

fCompileThread

CompileThread fCompileThread

fTimeInMillis

static long fTimeInMillis

fCompileTime

boolean fCompileTime

fComp

ExpVector[] fComp

fAntloc

ExpVector[] fAntloc

fTransp

ExpVector[] fTransp

fAvailIn

ExpVector[] fAvailIn

fAvailOut

ExpVector[] fAvailOut

fAntIn

ExpVector[] fAntIn

fAntOut

ExpVector[] fAntOut

fEpsIn

ExpVector[] fEpsIn

fEpsOut

ExpVector[] fEpsOut

fRedund

ExpVector[] fRedund

fInsert

ExpVector[] fInsert

fInsertEdge

java.util.List[] fInsertEdge

fSaveIn

ExpVector[] fSaveIn

fSaveOut

ExpVector[] fSaveOut

fSave

ExpVector[] fSave

fAllZero

ExpVector fAllZero

fAllOne

ExpVector fAllOne
コンストラクタの詳細

PRE

public PRE(SubpFlow pSubpFlow,
           SubpDefinition pSubpDef,
           boolean pSubsPtr,
           int pThreshold)
PRE Construct an instance of PRE for specified subprogram.

パラメータ:
pSubpDef - Subprogram definition as the target of PRE transformation.
pThreshold - Replacement threshold; Expressions with cost less than pThreshold are not replaced by temporal but recomputed each time.
メソッドの詳細

doPRE

public boolean doPRE()
doPRE Do partial redundancy elimination for the PRE instance. Before actual PRE transformation, this invokes local common subexpression elimination, Subs-expression to pointer-expression transformation, and critical edge removal transformation. Data flow computation is executed because the local common subexpression elimination may have changed the program. After PRE, pointer-expression to Subs-expression transformation takes place.

戻り値:
true if some expressions are transformed, false if no expression is transformed.

subscriptToPointerTransformation

protected boolean subscriptToPointerTransformation(java.util.Map pPtrSubsCorrespondence)
preparatoryTransformation Remove critical edges.

パラメータ:
pPtrSubsCorrespondence - record pointer-Subs correspondence.
戻り値:
true if HIR is changed, false if no change.

normalizeHir

protected boolean normalizeHir()

localCommonSubexpElimination

protected boolean localCommonSubexpElimination()

collectTempsUsedInReplacement

protected void collectTempsUsedInReplacement()

initiateDataFlowInformation

protected void initiateDataFlowInformation()
initiateDataFlowInformation Initiate data flow information required to solve the data flow equations given by Dhamdhere.


computeAntloc

protected ExpVector computeAntloc(BBlock pBBlock)
Compute AntLoc for pBBLock, that is, expressions whose operands are not set by preceeding operations in pBBlock.

パラメータ:
pBBlock - basic block.
戻り値:
AntLoc vector of pBBlock.

solveDataFlowEquations

protected void solveDataFlowEquations()

selectExpsForPRE

protected void selectExpsForPRE()
selectExpForPRE Select expressions listed up as redundant exp in some basic block and their cost is greater or equal to fThreshold. If an expression is selected, its subexpressions are not selected so that replacement takes place for the largest redundant expression. Left hand side expression of AssignStmt is not selected because it can not be replaced by temporal variable. Generate temporal variable for each of the selected expressions to represent its value, and put it in fExpTempMap using corresponding ExpId as a key.


selectLargestRedundantExpsInBBlock

void selectLargestRedundantExpsInBBlock(java.util.Set pRedundantExps,
                                        java.util.Set pSelectedExps,
                                        BBlock pBBlock)
selectLargestRedundantExpsInBBlock selects redundant expressions that are not included in larger redundant expression in the specified basic block pBBlock.

パラメータ:
pRedundantExps - set of ExpIds representing all redundant expressions in pBBlock.
pSelectedExps - set of ExpIds representing selected redundant expressions.
pBBlock - basic block.

selectLargestRedundantExps

void selectLargestRedundantExps(HIR pHir,
                                java.util.Set pRedundantExps,
                                java.util.Set pSelectedExps,
                                BBlock pBBlock)
selectLargestRedundantExps selects ExpIds representing largest redundant expressions in the given HIR subtree pHir. If an expression is found to be redundant, then it is selected but its subexpressions are not selected.

パラメータ:
pHir - HIR subtree within which redundant expressions are to be searched.
pRedundantExps - set of all redundant expressions in pBBlock.
pSelectedExps - set of selected redundant expressions.
pBBlock - basic block.

eliminateRedundantExpressions

protected boolean eliminateRedundantExpressions()

findExpWithExpId

protected Exp findExpWithExpId(HIR pHir,
                               ExpId pExpId)
findNodeWithExpId Find node with pExpId in the subtree pHir. If end of BBlock encountered, return null.

パラメータ:
pHir - subtree within which expression is searched.
pExpId - ExpId of expression to be searched.
戻り値:
the expression found or null if not found.

replaceExpWithTemp

public void replaceExpWithTemp(Exp pExp,
                               Var pVar)

makeAssignStmt

public Stmt makeAssignStmt(Var pVar,
                           Exp pExp)
makeAssignStmt Make assign statement pVar = pExp.copyWithOperands()

パラメータ:
pVar - left hand side variable.
pExp - right hand side expression.
戻り値:
assignment statement.

insertToEdge

public void insertToEdge(BBlock pFrom,
                         BBlock pTo,
                         Stmt pStmt)
insertToEdge There are following cases in the relations of edge and basic blocks: case 1: pFrom has only 1 successor pTo and pTo has only one predecessor; case 2: pFrom has only 1 successor pTo and pTo has multiple prececessor; case 3: pFrom has multiple successor and pTo has only 1 predecessor; case 4: pFrom has multiple successor and pTo has multiple predecessor; In case 1 and case 2, the operation to be inserted should be placed as the last statement (before unconditional goto) of pFrom BBlock. In case 3, the operation to be inserted should be placed placed as the first statement of pTo BBlock (after label definition). If critical edges have already been removed, case 4 does not occur and the insertion point can be simply determined.

パラメータ:
pFrom - Edge start point.
pTo - Edge end point.
pStmt - Statement to be inserted.

insertHeadStmtCaringBranch

public void insertHeadStmtCaringBranch(BBlock pBBlock,
                                       Stmt pStmt)
Insert pStmt as the head Stmt of pBBlock. If the first Stmt of pBBlock is a conditional Exp of control statement, then insert pStmt to all predecessors.

パラメータ:
pBBlock -
pStmt -

insertTailStmtCaringBranch

public void insertTailStmtCaringBranch(BBlock pBBlock,
                                       Stmt pStmt)
Add pStmt at the tail of pBBlock. If pBBlock has tail statement that is a conditional Exp of some control statement, then add pStmt to all successor BBlock of pBBlock.

パラメータ:
pBBlock - BBlock to which pStmt is to be added.
pStmt - statement to be added.

addFirstStmtOfBBlock

public void addFirstStmtOfBBlock(Stmt pStmt,
                                 BBlock pBBlock)

addLastStmtOfBBlock

public void addLastStmtOfBBlock(Stmt pStmt,
                                BBlock pBBlock)

isConditionalExpOfControlStmt

public boolean isConditionalExpOfControlStmt(HIR pHir)
Return true if pHir is a conditional expression of control statement (IfStmt, LoopStmt, SwitchStmt) or return true if its parent is a LabeledStmt that is a conditional expression part of control statement. Return false in other cases.

パラメータ:
pHir - subtree to be examined.
戻り値:
true if pHir is a conditional expression of control statement.

isRegisterizableExp

protected boolean isRegisterizableExp(HIR pHir)
Decide whether pHir is an expression that can be replaced by a register containing the value of the expression.

パラメータ:
pHir - HIR subtree to be examined.
戻り値:
true if can be replaced by register, false otherwise.

printExpVectorArray

protected void printExpVectorArray(java.lang.String pHeader,
                                   ExpVector[] pVectorArray)

printExpVectorArray2

protected void printExpVectorArray2(java.lang.String pHeader1,
                                    ExpVector[] pVectorArray1,
                                    java.lang.String pHeader2,
                                    ExpVector[] pVectorArray2)

printTimeInMillis

public long printTimeInMillis(java.lang.String pHeader,
                              boolean pPrint,
                              boolean pMonitor)
printTimeInMillis prints the current time if required. "diff" means the elapsed time from the previous call of this method in milli-seconds.

パラメータ:
pHeader - is the heading message to be printed with the time.
pPrint - true if the time is to be printed.
pMonitor - true if the time is to be displayed on monitor.
戻り値:
the current time in milli-seconds.