retdec
var_def_stmt_optimizer.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_LLVMIR2HLL_OPTIMIZER_OPTIMIZERS_VAR_DEF_STMT_OPTIMIZER_H
8 #define RETDEC_LLVMIR2HLL_OPTIMIZER_OPTIMIZERS_VAR_DEF_STMT_OPTIMIZER_H
9 
10 #include <cstddef>
11 #include <map>
12 #include <set>
13 #include <vector>
14 
18 
19 namespace retdec {
20 namespace llvmir2hll {
21 
22 class Statement;
23 class UForLoopStmt;
24 class ValueAnalysis;
25 
66 class VarDefStmtOptimizer final: public FuncOptimizer {
67 public:
69 
70  virtual std::string getId() const override { return "VarDefStmt"; }
71 
72 private:
74  enum class OptType {
75  A,
76  P
77  };
78 
80  struct StmtToOptimize {
83  };
84 
86  struct NextLvlStmts {
88  std::size_t order;
90  };
91 
94  struct FirstUse {
96  std::size_t level;
97  };
98 
100  using VarDefStmtVec = std::vector<ShPtr<VarDefStmt>>;
101 
103  using VarVarDefMap = std::map<ShPtr<Variable>, ShPtr<VarDefStmt>>;
104 
106  using VarStmtToOptimizeMap = std::map<ShPtr<Variable>, StmtToOptimize>;
107 
109  using VarFirstUseMap = std::map<ShPtr<Variable>, FirstUse >;
110 
112  using LevelCountMap = std::map<std::size_t, std::size_t>;
113 
115  using VarLevelCountMap = std::map<ShPtr<Variable>, LevelCountMap>;
116 
118  using VecNextLvlStmts = std::vector<NextLvlStmts>;
119 
121  using IntNextLvlStmtsMap = std::map<std::size_t, VecNextLvlStmts>;
122 
123 private:
124  virtual void doOptimization() override;
125 
126  void analyseVariablesInStmt(ShPtr<Statement> stmt, VarSet &thisLvlVars);
127  void clearAllRecords();
129  void findStmtsToOptimize();
131  void getVarsFromVarDefStmts(const VarDefStmtSet &noInitVarDefStmts);
133  ShPtr<Statement> parent, std::size_t order, VarSet &vars);
135  ShPtr<Variable> var) const;
137  std::size_t order);
138  void optimizeAssignStmts(StmtSet &toRemoveStmts) const;
139  void optimizeVarDefStmts() const;
140  void optimizeWithPrepend(StmtSet &toRemoveStmts) const;
142  void removeStructAndArrayVarDefStmts(VarDefStmtSet &noInitVarDefStmts) const;
143  void removeToBeRemovedStmts(StmtSet toRemoveStmts) const;
144  virtual void runOnFunction(ShPtr<Function> func) override;
145  void saveCountOfUsageVars(const VarSet &vars);
146  void saveVars(ShPtr<Statement> parent, std::size_t order, VarSet vars);
148  void sortVarDefStmts(const VarDefStmtSet &noInitVarDefStmts);
150  VarSet &thisLvlVars, std::size_t order);
152  ShPtr<Variable> optimizedVar) const;
153 
154 private:
157 
159  std::size_t level;
160 
164 
171 
174 
178 
182 
185 };
186 
187 } // namespace llvmir2hll
188 } // namespace retdec
189 
190 #endif
A base class of all function optimizers.
Definition: func_optimizer.h:44
ShPtr< Module > module
The module that is being optimized.
Definition: optimizer.h:79
Optimizes VarDefStmt to closest place of it's variable use.
Definition: var_def_stmt_optimizer.h:66
bool isAssignStmtWithVarOnLhs(ShPtr< Statement > stmt, ShPtr< Variable > var) const
Checks if stmt is an AssignStmt and assigned variable is a var.
Definition: var_def_stmt_optimizer.cpp:550
void removeStructAndArrayVarDefStmts(VarDefStmtSet &noInitVarDefStmts) const
Removes structures VarDefStmt and array VarDefStmt from noInitVarDefStmts.
Definition: var_def_stmt_optimizer.cpp:453
std::map< ShPtr< Variable >, FirstUse > VarFirstUseMap
Mapping of a Variable into a FirstUse.
Definition: var_def_stmt_optimizer.h:109
VarLevelCountMap varLevelCountMap
Definition: var_def_stmt_optimizer.h:181
std::vector< NextLvlStmts > VecNextLvlStmts
Vector of NextLvlStmts.
Definition: var_def_stmt_optimizer.h:118
void saveCountOfUsageVars(const VarSet &vars)
This function is responsible for counting of blocks where a variable is used in the same level.
Definition: var_def_stmt_optimizer.cpp:348
VarStmtToOptimizeMap optimizeStmts
Definition: var_def_stmt_optimizer.h:177
void setStmtToOptimize(ShPtr< Variable > var, ShPtr< Statement > stmt)
Assigns to a variable statement to optimize.
Definition: var_def_stmt_optimizer.cpp:580
ShPtr< Statement > findCorrectStatement(ShPtr< Variable > var, std::size_t level)
void clearAllRecords()
Clear all records about variables that are collected in function analyses.
Definition: var_def_stmt_optimizer.cpp:709
void optimizeAssignStmts(StmtSet &toRemoveStmts) const
Optimizes assign statements.
Definition: var_def_stmt_optimizer.cpp:677
std::size_t level
Saves level of current nesting.
Definition: var_def_stmt_optimizer.h:159
VarDefStmtOptimizer(ShPtr< Module > module, ShPtr< ValueAnalysis > va)
Constructs a new optimizer.
Definition: var_def_stmt_optimizer.cpp:45
VarSet varsFromVarDefStmt
Set of all variables from VarDefStmt to optimize.
Definition: var_def_stmt_optimizer.h:173
VarDefStmtVec sortedNoInitVarDefStmts
Vector of sorted VarDefStmt by name of variable.
Definition: var_def_stmt_optimizer.h:184
void saveVars(ShPtr< Statement > parent, std::size_t order, VarSet vars)
Saves all variables that are used in block to parent of this block.
Definition: var_def_stmt_optimizer.cpp:324
VarFirstUseMap firstUseMap
Definition: var_def_stmt_optimizer.h:163
IntNextLvlStmtsMap mapOfNextLvlStmts
Definition: var_def_stmt_optimizer.h:170
std::map< std::size_t, std::size_t > LevelCountMap
Mapping of a level of nesting into a count of usage variable.
Definition: var_def_stmt_optimizer.h:112
std::map< ShPtr< Variable >, StmtToOptimize > VarStmtToOptimizeMap
Mapping of a Variable into a StmtToOptimize.
Definition: var_def_stmt_optimizer.h:106
void getVarsFromVarDefStmts(const VarDefStmtSet &noInitVarDefStmts)
Gets all variables from noInitVarDefStmts and saves them into varsFromVarDefStmt.
Definition: var_def_stmt_optimizer.cpp:484
OptType
Enumeration for type of optimizations.
Definition: var_def_stmt_optimizer.h:74
void removeToBeRemovedStmts(StmtSet toRemoveStmts) const
Remove all statements that are in toRemoveStmts from abstract syntax tree.
Definition: var_def_stmt_optimizer.cpp:699
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 statem...
Definition: var_def_stmt_optimizer.cpp:526
void optimizeVarDefStmts() const
Optimizes all VarDefStmt after analyses in VarDefStmtOptimizer.
Definition: var_def_stmt_optimizer.cpp:590
virtual void runOnFunction(ShPtr< Function > func) override
Performs all optimizations on the given function.
Definition: var_def_stmt_optimizer.cpp:59
std::map< ShPtr< Variable >, ShPtr< VarDefStmt > > VarVarDefMap
Mapping of a Variable into a VarDefStmt.
Definition: var_def_stmt_optimizer.h:103
ShPtr< ValueAnalysis > va
Analysis of values.
Definition: var_def_stmt_optimizer.h:156
void findStmtsToOptimize()
Finds the final statement to optimize.
Definition: var_def_stmt_optimizer.cpp:404
std::vector< ShPtr< VarDefStmt > > VarDefStmtVec
Vector of VarDefStmt.
Definition: var_def_stmt_optimizer.h:100
void optimizeWithPrepend(StmtSet &toRemoveStmts) const
Optimizes statements that have to be optimized with prepend statement.
Definition: var_def_stmt_optimizer.cpp:628
virtual std::string getId() const override
Returns the ID of the optimizer.
Definition: var_def_stmt_optimizer.h:70
std::map< std::size_t, VecNextLvlStmts > IntNextLvlStmtsMap
Mapping of a level of nesting into a vector of NextLvlStmts.
Definition: var_def_stmt_optimizer.h:121
bool tryOptimizeUForLoop(ShPtr< UForLoopStmt > loop, ShPtr< Variable > optimizedVar) const
Tries to optimize the given variable for the given universal for loop.
Definition: var_def_stmt_optimizer.cpp:216
ShPtr< Statement > findStmtToPrepend(ShPtr< Variable > var, std::size_t level) const
Finds a statement in level to prepend.
Definition: var_def_stmt_optimizer.cpp:379
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 fo...
Definition: var_def_stmt_optimizer.cpp:103
void sortVarDefStmts(const VarDefStmtSet &noInitVarDefStmts)
Sorts VarDefStmts by name from set into sortedNoInitVarDefStmts.
Definition: var_def_stmt_optimizer.cpp:509
virtual void doOptimization() override
Performs the optimization on all functions in the module.
Definition: var_def_stmt_optimizer.cpp:51
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.
Definition: var_def_stmt_optimizer.cpp:168
void analyseVariablesInStmt(ShPtr< Statement > stmt, VarSet &thisLvlVars)
Analyses statement stmt.
Definition: var_def_stmt_optimizer.cpp:249
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.
Definition: var_def_stmt_optimizer.cpp:303
std::map< ShPtr< Variable >, LevelCountMap > VarLevelCountMap
Mapping of a Variable into a LevelCountMap.
Definition: var_def_stmt_optimizer.h:115
A base class of all function optimizers.
A library providing API for working with back-end IR.
std::shared_ptr< T > ShPtr
An alias for a shared pointer.
Definition: smart_ptr.h:18
std::set< ShPtr< VarDefStmt > > VarDefStmtSet
Set of VarDefStmt.
Definition: types.h:60
std::set< ShPtr< Variable > > VarSet
Set of variables.
Definition: types.h:57
std::set< ShPtr< Statement > > StmtSet
Set of statements.
Definition: types.h:69
Definition: archive_wrapper.h:19
Declarations, aliases, macros, etc. for the use of smart pointers.
Definition: var_def_stmt_optimizer.h:94
ShPtr< Statement > stmt
Definition: var_def_stmt_optimizer.h:95
std::size_t level
Definition: var_def_stmt_optimizer.h:96
Structure that saves basic information about next nesting level block.
Definition: var_def_stmt_optimizer.h:86
VarSet vars
variables that are visible from this block
Definition: var_def_stmt_optimizer.h:89
std::size_t order
order of parent statement in it's block
Definition: var_def_stmt_optimizer.h:88
ShPtr< Statement > stmt
parent statement of block
Definition: var_def_stmt_optimizer.h:87
Structure that saves statement to optimize and type of optimization.
Definition: var_def_stmt_optimizer.h:80
OptType optType
Definition: var_def_stmt_optimizer.h:82
ShPtr< Statement > stmt
Definition: var_def_stmt_optimizer.h:81
Aliases for several useful types.