|
||||||||||
前のクラス 次のクラス | フレームあり フレームなし | |||||||||
概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド |
java.lang.Object | +--coins.opt.CommonSubexpElim | +--coins.opt.CommonSubexpElimHir | +--coins.opt.CommonSubexpElimHirE | +--coins.opt.PRE
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.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 |
フィールドの詳細 |
public final IoRoot ioRoot
public final Flow flow
protected ShowDataFlow fShowFlow
protected SubpDefinition fSubpDef
protected boolean fRegularSubp
protected boolean fSubsPtr
protected int fTraceLevel
CompileThread fCompileThread
static long fTimeInMillis
boolean fCompileTime
ExpVector[] fComp
ExpVector[] fAntloc
ExpVector[] fTransp
ExpVector[] fAvailIn
ExpVector[] fAvailOut
ExpVector[] fAntIn
ExpVector[] fAntOut
ExpVector[] fEpsIn
ExpVector[] fEpsOut
ExpVector[] fRedund
ExpVector[] fInsert
java.util.List[] fInsertEdge
ExpVector[] fSaveIn
ExpVector[] fSaveOut
ExpVector[] fSave
ExpVector fAllZero
ExpVector fAllOne
コンストラクタの詳細 |
public PRE(SubpFlow pSubpFlow, SubpDefinition pSubpDef, boolean pSubsPtr, int pThreshold)
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.メソッドの詳細 |
public boolean doPRE()
protected boolean subscriptToPointerTransformation(java.util.Map pPtrSubsCorrespondence)
pPtrSubsCorrespondence
- record pointer-Subs correspondence.
protected boolean normalizeHir()
protected boolean localCommonSubexpElimination()
protected void collectTempsUsedInReplacement()
protected void initiateDataFlowInformation()
protected ExpVector computeAntloc(BBlock pBBlock)
pBBlock
- basic block.
protected void solveDataFlowEquations()
protected void selectExpsForPRE()
void selectLargestRedundantExpsInBBlock(java.util.Set pRedundantExps, java.util.Set pSelectedExps, BBlock pBBlock)
pRedundantExps
- set of ExpIds representing all redundant
expressions in pBBlock.pSelectedExps
- set of ExpIds representing selected
redundant expressions.pBBlock
- basic block.void selectLargestRedundantExps(HIR pHir, java.util.Set pRedundantExps, java.util.Set pSelectedExps, BBlock pBBlock)
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.protected boolean eliminateRedundantExpressions()
protected Exp findExpWithExpId(HIR pHir, ExpId pExpId)
pHir
- subtree within which expression is searched.pExpId
- ExpId of expression to be searched.
public void replaceExpWithTemp(Exp pExp, Var pVar)
public Stmt makeAssignStmt(Var pVar, Exp pExp)
pVar
- left hand side variable.pExp
- right hand side expression.
public void insertToEdge(BBlock pFrom, BBlock pTo, Stmt pStmt)
pFrom
- Edge start point.pTo
- Edge end point.pStmt
- Statement to be inserted.public void insertHeadStmtCaringBranch(BBlock pBBlock, Stmt pStmt)
pBBlock
- pStmt
- public void insertTailStmtCaringBranch(BBlock pBBlock, Stmt pStmt)
pBBlock
- BBlock to which pStmt is to be added.pStmt
- statement to be added.public void addFirstStmtOfBBlock(Stmt pStmt, BBlock pBBlock)
public void addLastStmtOfBBlock(Stmt pStmt, BBlock pBBlock)
public boolean isConditionalExpOfControlStmt(HIR pHir)
pHir
- subtree to be examined.
protected boolean isRegisterizableExp(HIR pHir)
pHir
- HIR subtree to be examined.
protected void printExpVectorArray(java.lang.String pHeader, ExpVector[] pVectorArray)
protected void printExpVectorArray2(java.lang.String pHeader1, ExpVector[] pVectorArray1, java.lang.String pHeader2, ExpVector[] pVectorArray2)
public long printTimeInMillis(java.lang.String pHeader, boolean pPrint, boolean pMonitor)
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.
|
||||||||||
前のクラス 次のクラス | フレームあり フレームなし | |||||||||
概要: 入れ子 | フィールド | コンストラクタ | メソッド | 詳細: フィールド | コンストラクタ | メソッド |