retdec
|
Optimizes VarDefStmt to closest place of it's variable use. More...
#include <var_def_stmt_optimizer.h>
Classes | |
struct | FirstUse |
struct | NextLvlStmts |
Structure that saves basic information about next nesting level block. More... | |
struct | StmtToOptimize |
Structure that saves statement to optimize and type of optimization. More... | |
Public Member Functions | |
VarDefStmtOptimizer (ShPtr< Module > module, ShPtr< ValueAnalysis > va) | |
Constructs a new optimizer. More... | |
virtual std::string | getId () const override |
Returns the ID of the optimizer. More... | |
![]() | |
Optimizer (ShPtr< Module > module) | |
Constructs a new optimizer. More... | |
ShPtr< Module > | optimize () |
Performs all the optimizations of the specific optimizer. More... | |
![]() | |
virtual void | visit (ShPtr< GlobalVarDef > varDef) override |
virtual void | visit (ShPtr< Function > func) override |
virtual void | visit (ShPtr< AssignStmt > stmt) override |
virtual void | visit (ShPtr< BreakStmt > stmt) override |
virtual void | visit (ShPtr< CallStmt > stmt) override |
virtual void | visit (ShPtr< ContinueStmt > stmt) override |
virtual void | visit (ShPtr< EmptyStmt > stmt) override |
virtual void | visit (ShPtr< ForLoopStmt > stmt) override |
virtual void | visit (ShPtr< UForLoopStmt > stmt) override |
virtual void | visit (ShPtr< GotoStmt > stmt) override |
virtual void | visit (ShPtr< IfStmt > stmt) override |
virtual void | visit (ShPtr< ReturnStmt > stmt) override |
virtual void | visit (ShPtr< SwitchStmt > stmt) override |
virtual void | visit (ShPtr< UnreachableStmt > stmt) override |
virtual void | visit (ShPtr< VarDefStmt > stmt) override |
virtual void | visit (ShPtr< WhileLoopStmt > stmt) override |
virtual void | visit (ShPtr< AddOpExpr > expr) override |
virtual void | visit (ShPtr< AddressOpExpr > expr) override |
virtual void | visit (ShPtr< AndOpExpr > expr) override |
virtual void | visit (ShPtr< ArrayIndexOpExpr > expr) override |
virtual void | visit (ShPtr< AssignOpExpr > expr) override |
virtual void | visit (ShPtr< BitAndOpExpr > expr) override |
virtual void | visit (ShPtr< BitOrOpExpr > expr) override |
virtual void | visit (ShPtr< BitShlOpExpr > expr) override |
virtual void | visit (ShPtr< BitShrOpExpr > expr) override |
virtual void | visit (ShPtr< BitXorOpExpr > expr) override |
virtual void | visit (ShPtr< CallExpr > expr) override |
virtual void | visit (ShPtr< CommaOpExpr > expr) override |
virtual void | visit (ShPtr< DerefOpExpr > expr) override |
virtual void | visit (ShPtr< DivOpExpr > expr) override |
virtual void | visit (ShPtr< EqOpExpr > expr) override |
virtual void | visit (ShPtr< GtEqOpExpr > expr) override |
virtual void | visit (ShPtr< GtOpExpr > expr) override |
virtual void | visit (ShPtr< LtEqOpExpr > expr) override |
virtual void | visit (ShPtr< LtOpExpr > expr) override |
virtual void | visit (ShPtr< ModOpExpr > expr) override |
virtual void | visit (ShPtr< MulOpExpr > expr) override |
virtual void | visit (ShPtr< NegOpExpr > expr) override |
virtual void | visit (ShPtr< NeqOpExpr > expr) override |
virtual void | visit (ShPtr< NotOpExpr > expr) override |
virtual void | visit (ShPtr< OrOpExpr > expr) override |
virtual void | visit (ShPtr< StructIndexOpExpr > expr) override |
virtual void | visit (ShPtr< SubOpExpr > expr) override |
virtual void | visit (ShPtr< TernaryOpExpr > expr) override |
virtual void | visit (ShPtr< Variable > var) override |
virtual void | visit (ShPtr< BitCastExpr > expr) override |
virtual void | visit (ShPtr< ExtCastExpr > expr) override |
virtual void | visit (ShPtr< FPToIntCastExpr > expr) override |
virtual void | visit (ShPtr< IntToFPCastExpr > expr) override |
virtual void | visit (ShPtr< IntToPtrCastExpr > expr) override |
virtual void | visit (ShPtr< PtrToIntCastExpr > expr) override |
virtual void | visit (ShPtr< TruncCastExpr > expr) override |
virtual void | visit (ShPtr< ConstArray > constant) override |
virtual void | visit (ShPtr< ConstBool > constant) override |
virtual void | visit (ShPtr< ConstFloat > constant) override |
virtual void | visit (ShPtr< ConstInt > constant) override |
virtual void | visit (ShPtr< ConstNullPointer > constant) override |
virtual void | visit (ShPtr< ConstString > constant) override |
virtual void | visit (ShPtr< ConstStruct > constant) override |
virtual void | visit (ShPtr< ConstSymbol > constant) override |
virtual void | visit (ShPtr< ArrayType > type) override |
virtual void | visit (ShPtr< FloatType > type) override |
virtual void | visit (ShPtr< IntType > type) override |
virtual void | visit (ShPtr< PointerType > type) override |
virtual void | visit (ShPtr< StringType > type) override |
virtual void | visit (ShPtr< StructType > type) override |
virtual void | visit (ShPtr< FunctionType > type) override |
virtual void | visit (ShPtr< VoidType > type) override |
virtual void | visit (ShPtr< UnknownType > type) override |
![]() | |
virtual | ~Visitor ()=default |
Private Types | |
enum class | OptType { A , P } |
Enumeration for type of optimizations. More... | |
using | VarDefStmtVec = std::vector< ShPtr< VarDefStmt > > |
Vector of VarDefStmt. More... | |
using | VarVarDefMap = std::map< ShPtr< Variable >, ShPtr< VarDefStmt > > |
Mapping of a Variable into a VarDefStmt. More... | |
using | VarStmtToOptimizeMap = std::map< ShPtr< Variable >, StmtToOptimize > |
Mapping of a Variable into a StmtToOptimize. More... | |
using | VarFirstUseMap = std::map< ShPtr< Variable >, FirstUse > |
Mapping of a Variable into a FirstUse. More... | |
using | LevelCountMap = std::map< std::size_t, std::size_t > |
Mapping of a level of nesting into a count of usage variable. More... | |
using | VarLevelCountMap = std::map< ShPtr< Variable >, LevelCountMap > |
Mapping of a Variable into a LevelCountMap. More... | |
using | VecNextLvlStmts = std::vector< NextLvlStmts > |
Vector of NextLvlStmts. More... | |
using | IntNextLvlStmtsMap = std::map< std::size_t, VecNextLvlStmts > |
Mapping of a level of nesting into a vector of NextLvlStmts. More... | |
Private Member Functions | |
virtual void | doOptimization () override |
Performs the optimization on all functions in the module. More... | |
void | analyseVariablesInStmt (ShPtr< Statement > stmt, VarSet &thisLvlVars) |
Analyses statement stmt. More... | |
void | clearAllRecords () |
Clear all records about variables that are collected in function analyses. More... | |
ShPtr< Statement > | findCorrectStatement (ShPtr< Variable > var, std::size_t level) |
void | findStmtsToOptimize () |
Finds the final statement to optimize. More... | |
ShPtr< Statement > | findStmtToPrepend (ShPtr< Variable > var, std::size_t level) const |
Finds a statement in level to prepend. More... | |
void | getVarsFromVarDefStmts (const VarDefStmtSet &noInitVarDefStmts) |
Gets all variables from noInitVarDefStmts and saves them into varsFromVarDefStmt . More... | |
void | goToNextBlockAndAppendVisibleVars (ShPtr< Statement > stmt, ShPtr< Statement > parent, std::size_t order, VarSet &vars) |
Calls recursion to next block and append visible variables from the next block to the currenct block. More... | |
bool | isAssignStmtWithVarOnLhs (ShPtr< Statement > stmt, ShPtr< Variable > var) const |
Checks if stmt is an AssignStmt and assigned variable is a var. More... | |
VarSet | oneBlockTraversal (ShPtr< Statement > stmt, ShPtr< Statement > parent, std::size_t order) |
This function is recursive. One recursion visits all statements in block and calls a new recursion for the next nesting level blocks. More... | |
void | optimizeAssignStmts (StmtSet &toRemoveStmts) const |
Optimizes assign statements. More... | |
void | optimizeVarDefStmts () const |
Optimizes all VarDefStmt after analyses in VarDefStmtOptimizer. More... | |
void | optimizeWithPrepend (StmtSet &toRemoveStmts) const |
Optimizes statements that have to be optimized with prepend statement. More... | |
OptType | prependOrAssign (ShPtr< Statement > stmt, ShPtr< Variable > var) const |
Analyses the given statement and makes a decision if the optimization will be with prepend the statement or change the assign statement. More... | |
void | removeStructAndArrayVarDefStmts (VarDefStmtSet &noInitVarDefStmts) const |
Removes structures VarDefStmt and array VarDefStmt from noInitVarDefStmts. More... | |
void | removeToBeRemovedStmts (StmtSet toRemoveStmts) const |
Remove all statements that are in toRemoveStmts from abstract syntax tree. More... | |
virtual void | runOnFunction (ShPtr< Function > func) override |
Performs all optimizations on the given function. More... | |
void | saveCountOfUsageVars (const VarSet &vars) |
This function is responsible for counting of blocks where a variable is used in the same level. More... | |
void | saveVars (ShPtr< Statement > parent, std::size_t order, VarSet vars) |
Saves all variables that are used in block to parent of this block. More... | |
void | setStmtToOptimize (ShPtr< Variable > var, ShPtr< Statement > stmt) |
Assigns to a variable statement to optimize. More... | |
void | sortVarDefStmts (const VarDefStmtSet &noInitVarDefStmts) |
Sorts VarDefStmts by name from set into sortedNoInitVarDefStmts . More... | |
void | tryToFindAndEnterToNextNestingLevel (ShPtr< Statement > stmt, VarSet &thisLvlVars, std::size_t order) |
Tries to find the enter of the next nesting level block and enters it if it is found. More... | |
bool | tryOptimizeUForLoop (ShPtr< UForLoopStmt > loop, ShPtr< Variable > optimizedVar) const |
Tries to optimize the given variable for the given universal for loop. More... | |
Private Attributes | |
ShPtr< ValueAnalysis > | va |
Analysis of values. More... | |
std::size_t | level |
Saves level of current nesting. More... | |
VarFirstUseMap | firstUseMap |
IntNextLvlStmtsMap | mapOfNextLvlStmts |
VarSet | varsFromVarDefStmt |
Set of all variables from VarDefStmt to optimize. More... | |
VarStmtToOptimizeMap | optimizeStmts |
VarLevelCountMap | varLevelCountMap |
VarDefStmtVec | sortedNoInitVarDefStmts |
Vector of sorted VarDefStmt by name of variable. More... | |
Additional Inherited Members | |
![]() | |
template<class OptimizerType , typename... Args> | |
static ShPtr< Module > | optimize (ShPtr< Module > module, Args &&... args) |
Creates an instance of OptimizerType with the given arguments and optimizes the given module by it. More... | |
![]() | |
FuncOptimizer (ShPtr< Module > module) | |
Constructs a new function optimizer. More... | |
template<typename T > | |
void | visitNestedAndSuccessorStatements (ShPtr< T > stmt) |
Visits the given statement, its nested statements, and successor statements (depending on the settings of the visitor). More... | |
![]() | |
virtual void | doInitialization () |
Performs pre-optimization matters. More... | |
virtual void | doFinalization () |
Performs post-optimization matters. More... | |
![]() | |
OrderedAllVisitor (bool visitSuccessors=true, bool visitNestedStmts=true) | |
Constructs a new visitor. More... | |
virtual void | visitStmt (ShPtr< Statement > stmt, bool visitSuccessors=true, bool visitNestedStmts=true) |
Visits the given statement, and possibly its successors or nested statements. More... | |
void | restart (bool visitSuccessors=true, bool visitNestedStmts=true) |
"Restarts" the visitor so it is in the state like it was when it was created. More... | |
bool | makeAccessedAndCheckIfAccessed (ShPtr< Type > type) |
Makes the given type accessed. More... | |
![]() | |
Visitor ()=default | |
![]() | |
ShPtr< Function > | currFunc |
Function that is currently being optimized. More... | |
![]() | |
ShPtr< Module > | module |
The module that is being optimized. More... | |
![]() | |
ShPtr< Statement > | lastStmt |
Statement that has been accessed as the last one. More... | |
StmtUSet | accessedStmts |
A set of all accessed statements. More... | |
TypeUSet | accessedTypes |
A set of all accessed types. More... | |
bool | visitSuccessors |
Should statements' successor be accessed? More... | |
bool | visitNestedStmts |
Should nested statements be accessed? More... | |
Optimizes VarDefStmt to closest place of it's variable use.
For example, the following code
can be optimized into
and
can be optimized into
Instances of this class have reference object semantics.
This is a concrete optimizer which should not be subclassed.
|
private |
Mapping of a level of nesting into a vector of NextLvlStmts.
|
private |
Mapping of a level of nesting into a count of usage variable.
|
private |
Vector of VarDefStmt.
|
private |
|
private |
Mapping of a Variable into a LevelCountMap.
|
private |
Mapping of a Variable into a StmtToOptimize.
|
private |
Mapping of a Variable into a VarDefStmt.
|
private |
Vector of NextLvlStmts.
|
strongprivate |
retdec::llvmir2hll::VarDefStmtOptimizer::VarDefStmtOptimizer | ( | ShPtr< Module > | module, |
ShPtr< ValueAnalysis > | va | ||
) |
Constructs a new optimizer.
[in] | module | Module to be optimized. |
[in] | va | Analysis of values. |
|
private |
Analyses statement stmt.
This function appends all variables that are used in stmt into thisLvlVars because these variables are visible from this block. It also saves the first usage of every variable.
[in] | stmt | The statement to analyse. |
[in,out] | thisLvlVars | Set of variables that are visible from this block. |
|
private |
Clear all records about variables that are collected in function analyses.
|
overrideprivatevirtual |
Performs the optimization on all functions in the module.
This function calls runOnFunction() for each function in the module.
Only redefine if you want to prescribe the order in which functions are optimized; otherwise, just override runOnFunction().
Reimplemented from retdec::llvmir2hll::FuncOptimizer.
|
private |
|
private |
Finds the final statement to optimize.
|
private |
Finds a statement in level to prepend.
[in] | var | A variable for which is finding statement. |
[in] | level | A nested level where is finding statement. |
|
inlineoverridevirtual |
Returns the ID of the optimizer.
Implements retdec::llvmir2hll::Optimizer.
|
private |
Gets all variables from noInitVarDefStmts and saves them into varsFromVarDefStmt
.
[in] | noInitVarDefStmts | A set of VarDefStmt . |
|
private |
Calls recursion to next block and append visible variables from the next block to the currenct block.
[in] | stmt | The first statement in block. |
[in] | parent | A parent of next nested level block. |
[in] | order | An order of parent in his block. |
[in,out] | vars | A VarSet of variables that are visible from the current block. |
|
private |
Checks if stmt is an AssignStmt
and assigned variable is a var.
[in] | stmt | A statement to check if is it an AssignStmt . |
[in] | var | A variable to check if is on left side of AssignStmt . |
true
if the stmt is an AssignStmt
and var is on left side of AssignStmt
, otherwise false
.
|
private |
This function is recursive. One recursion visits all statements in block and calls a new recursion for the next nesting level blocks.
This function also analyses variables usage in blocks.
[in] | stmt | The first statement in block. |
[in] | parent | A parent of block. |
[in] | parOrder | An order of parent in his block. |
VarSet
of vars that are visible from this block.
|
private |
Optimizes assign statements.
[in,out] | toRemoveStmts | Set for optimized VarDefStmt that can be removed. |
|
private |
Optimizes all VarDefStmt after analyses in VarDefStmtOptimizer.
|
private |
Optimizes statements that have to be optimized with prepend statement.
[in,out] | toRemoveStmts | Set for optimized VarDefStmt that can be removed. |
|
private |
Analyses the given statement and makes a decision if the optimization will be with prepend the statement or change the assign statement.
[in] | stmt | A statement to check. |
[in] | var | A variable that will be optimized. |
|
private |
Removes structures VarDefStmt and array VarDefStmt from noInitVarDefStmts.
[in,out] | noInitVarDefStmts | A set of VarDefStmt . |
|
private |
Remove all statements that are in toRemoveStmts from abstract syntax tree.
[in] | toRemoveStmts | Set of all statements to remove. |
|
overrideprivatevirtual |
Performs all optimizations on the given function.
[in,out] | func | Function to be optimized. |
By default, this function calls func->accept(this)
.
Reimplemented from retdec::llvmir2hll::FuncOptimizer.
|
private |
This function is responsible for counting of blocks where a variable is used in the same level.
[in] | vars | A VarSet of vars that need to add to counting. |
|
private |
Saves all variables that are used in block to parent of this block.
[in] | parent | A parent of block. |
[in] | order | An order of parent in his block. |
[in] | vars | A VarSet of variables that are visible from current block. |
|
private |
Assigns to a variable statement to optimize.
[in] | var | A variable for VarDefStmt. |
[in] | stmt | A statement to optimize. |
|
private |
Sorts VarDefStmts by name from set into sortedNoInitVarDefStmts
.
[in] | noInitVarDefStmts | A set to sort into vector sortedNoInitVarDefStmts . |
|
private |
Tries to optimize the given variable for the given universal for loop.
true
when the optimization was performed, false
otherwise.
|
private |
Tries to find the enter of the next nesting level block and enters it if it is found.
Tries to find the enter of the next nesting level block. If it is found, this function enters this block. After out from the entered block, it appends visible variables to the current block.
[in] | stmt | The current statement. |
[in,out] | thisLvlVars | Set of vars that are visible from this block. |
[in] | order | Order of the current statement. |
|
private |
|
private |
Saves level of current nesting.
|
private |
Map of all next level statements like if, else if, while, switch, for etc. Access to this map is by nesting level. Items are all next level statements in this mapped nesting level. With next level statements are also saved parents of next level statements(one level upper block entry) and order in current block of these next level statements.
|
private |
Map of all statements to optimize. Access to map is by variable from VarDefStmt to optimize.
|
private |
Vector of sorted VarDefStmt by name of variable.
|
private |
Analysis of values.
|
private |
Mapping variable into it's number of use in separate blocks of same nesting level.
|
private |
Set of all variables from VarDefStmt to optimize.