retdec
|
Copy propagation optimization. More...
#include <copy_propagation_optimizer.h>
Public Member Functions | |
CopyPropagationOptimizer (ShPtr< Module > module, ShPtr< ValueAnalysis > va, ShPtr< CallInfoObtainer > cio) | |
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 Member Functions | |
virtual void | doOptimization () override |
Performs the optimization on all functions in the module. More... | |
virtual void | runOnFunction (ShPtr< Function > func) override |
Performs all optimizations on the given function. More... | |
void | performOptimization () |
Performs the copy propagation optimization. More... | |
bool | stmtOrUseHasBeenModified (ShPtr< Statement > stmt, const StmtSet &uses) const |
Returns true if stmt or any its uses in uses has been modified, false otherwise. More... | |
void | handleCaseEmptyUses (ShPtr< Statement > stmt, ShPtr< Variable > stmtLhsVar) |
Handles the situation from performOptimization() when there are no uses of a variable after its definition before a subsequent definition. More... | |
void | handleCaseSingleUse (ShPtr< Statement > stmt, ShPtr< Variable > stmtLhsVar, ShPtr< Statement > use) |
Handles the situation from performOptimization() when there is a single use of a variable after its definition before a subsequent definition. More... | |
void | handleCaseInductionVariable (ShPtr< Statement > stmt, ShPtr< Variable > stmtLhsVar, const StmtSet &uses) |
Handles a specific pattern occurring in for loop induction variables: More... | |
void | handleCaseInductionVariable2 (ShPtr< Statement > stmt, ShPtr< Variable > stmtLhsVar, const StmtSet &uses) |
void | handleCaseMoreThanOneUse (ShPtr< Statement > stmt, ShPtr< Variable > stmtLhsVar, const StmtSet &uses) |
Handles the situation from performOptimization() when there is more than one use of a variable after its definition before a subsequent definition. More... | |
bool | shouldBeIncludedInDefUseChains (ShPtr< Variable > var) |
Should the given variable be included in def-use chains? More... | |
Visitor Interface | |
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 |
Private Attributes | |
ShPtr< CFGBuilder > | cfgBuilder |
The used builder of CFGs. More... | |
ShPtr< ValueAnalysis > | va |
Analysis of values. More... | |
ShPtr< CallInfoObtainer > | cio |
Obtainer of information about function calls. More... | |
ShPtr< VarUsesVisitor > | vuv |
Visitor for obtaining uses of variables. More... | |
ShPtr< DefUseAnalysis > | dua |
Def-use analysis. More... | |
ShPtr< UseDefAnalysis > | uda |
Use-def analysis. More... | |
ShPtr< DefUseChains > | ducs |
Def-use chains. More... | |
ShPtr< UseDefChains > | udcs |
Use-def chains. More... | |
std::map< DefUseChains::StmtVarPair, std::size_t > | def2uses |
Associative def-use chains. More... | |
std::map< ShPtr< Variable >, std::set< std::size_t > > | var2dus |
VarSet | globalVars |
StmtSet | toEntirelyRemoveStmts |
Set of statements that should be removed entirely. More... | |
StmtSet | toRemoveStmtsPreserveCalls |
StmtSet | modifiedStmts |
Set of statements that have been modified (altered or removed). More... | |
bool | codeChanged |
Has the code changed? 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... | |
Copy propagation optimization.
This optimization replaces the occurrences of targets of direct assignments with their values. A direct assignment is a statement of the form x = y
, which simply assigns the value of y
to x
.
For example, the following code
can be replaced with
provided that certain conditions are met (e.g. a
and b
are non-global and are not used anywhere else).
This optimization also removes dead assignments or variable definitions. These are assignments which assign a value into a variable which is then never used.
For example, the following code
can be replaced with
provided that a
is non-global.
Instances of this class have reference object semantics.
This is a concrete optimizer which should not be subclassed.
retdec::llvmir2hll::CopyPropagationOptimizer::CopyPropagationOptimizer | ( | ShPtr< Module > | module, |
ShPtr< ValueAnalysis > | va, | ||
ShPtr< CallInfoObtainer > | cio | ||
) |
Constructs a new optimizer.
[in] | module | Module to be optimized. |
[in] | va | Analysis of values. |
[in] | cio | Obtainer of information about function calls. |
|
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.
|
inlineoverridevirtual |
Returns the ID of the optimizer.
Implements retdec::llvmir2hll::Optimizer.
|
private |
Handles the situation from performOptimization() when there are no uses of a variable after its definition before a subsequent definition.
[in] | stmt | Definition of stmtLhsVar. |
[in] | stmtLhsVar | Variable defined in stmt. |
If this function changes the code, codeChanged
is set to true
.
|
private |
Handles a specific pattern occurring in for loop induction variables:
This gets optimized into:
[in] | defStmt | Definition of defVar |
[in] | defVar | Variable defined in s |
[in] | uses | Uses of defVar. |
If this function changes the code, codeChanged
is set to true
.
|
private |
x = undef y = undef x = 0 while(true) y = x ... x = y + A <- optimized stmt if (y cond B) break
y = undef y = 0 while(true) ... if (y cond B) break y = y + A
|
private |
Handles the situation from performOptimization() when there is more than one use of a variable after its definition before a subsequent definition.
[in] | stmt | Definition of stmtLhsVar. |
[in] | stmtLhsVar | Variable defined in stmt. |
[in] | uses | Uses of stmtLhsVar. |
If this function changes the code, codeChanged
is set to true
.
|
private |
Handles the situation from performOptimization() when there is a single use of a variable after its definition before a subsequent definition.
[in] | stmt | Definition of stmtLhsVar. |
[in] | stmtLhsVar | Variable defined in stmt. |
[in] | use | Use of stmtLhsVar. |
If this function changes the code, codeChanged
is set to true
.
|
private |
Performs the copy propagation optimization.
If this function changes the code, codeChanged
is set to true
.
|
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 |
Should the given variable be included in def-use chains?
|
private |
Returns true
if stmt or any its uses in uses has been modified, false
otherwise.
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
overrideprivate |
|
private |
The used builder of CFGs.
|
private |
Obtainer of information about function calls.
|
private |
Has the code changed?
|
private |
Associative def-use chains.
|
private |
Def-use analysis.
|
private |
Def-use chains.
|
private |
Global variables in module
. This is here to speedup the traversal. By using this set, we do not have to ask module
every time we need such information.
|
private |
Set of statements that have been modified (altered or removed).
|
private |
Set of statements that should be removed entirely.
|
private |
Set of assign/variable-defining statements that should be removed, but function calls should be preserved.
|
private |
Use-def analysis.
|
private |
Use-def chains.
|
private |
Analysis of values.
|
private |
|
private |
Visitor for obtaining uses of variables.