retdec
structure_converter.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_LLVMIR2HLL_LLVM_LLVMIR2BIR_CONVERTER_STRUCTURE_CONVERTER_H
8 #define RETDEC_LLVMIR2HLL_LLVM_LLVMIR2BIR_CONVERTER_STRUCTURE_CONVERTER_H
9 
10 #include <functional>
11 #include <queue>
12 #include <stack>
13 #include <unordered_map>
14 #include <unordered_set>
15 #include <utility>
16 #include <vector>
17 
23 
24 namespace llvm {
25 
26 class Function;
27 class Loop;
28 class LoopInfo;
29 class Pass;
30 class ScalarEvolution;
31 
32 } // namespace llvm
33 
34 namespace retdec {
35 namespace llvmir2hll {
36 
37 class IfStmt;
38 class LabelsHandler;
39 class LLVMValueConverter;
40 class Statement;
41 class SwitchStmt;
42 
46 enum class SwitchParent {Yes, No};
47 
52 private:
54  enum class DFSNodeState {
55  Opened,
56  Closed
57  };
58 
59  using SwitchClause = std::pair<ExprVector, ShPtr<CFGNode>>;
60 
61  using BBSet = std::unordered_set<llvm::BasicBlock *>;
62  using CFGNodeQueue = std::queue<ShPtr<CFGNode>>;
63  using CFGNodeStack = std::stack<ShPtr<CFGNode>>;
64  using CFGNodeVector = std::vector<ShPtr<CFGNode>>;
65  using LoopSet = std::unordered_set<llvm::Loop *>;
66  using SwitchClauseVector = std::vector<ShPtr<SwitchClause>>;
67 
68  using MapBBToBBSet = std::unordered_map<llvm::BasicBlock *, BBSet>;
69  using MapBBToCFGNode = std::unordered_map<llvm::BasicBlock *, ShPtr<CFGNode>>;
70  using MapCFGNodeToSwitchClause = std::unordered_map<ShPtr<CFGNode>, ShPtr<SwitchClause>>;
71  using MapCFGNodeToDFSNodeState = std::unordered_map<ShPtr<CFGNode>, DFSNodeState>;
72  using MapLoopToCFGNode = std::unordered_map<llvm::Loop *, ShPtr<CFGNode>>;
73  using MapStmtToTargetNode = std::unordered_map<ShPtr<Statement>, ShPtr<CFGNode>>;
74  using MapTargetToGoto = std::unordered_map<ShPtr<CFGNode>, std::vector<ShPtr<GotoStmt>>>;
75  using MapStmtToClones = std::unordered_map<ShPtr<Statement>, std::vector<ShPtr<Statement>>>;
76 
77 public:
79 
80  ShPtr<Statement> convertFuncBody(llvm::Function &func);
81 
82 private:
85  ShPtr<CFGNode> createCFG(llvm::BasicBlock &root);
86  void detectBackEdges(ShPtr<CFGNode> cfg) const;
87  bool reduceCFG(ShPtr<CFGNode> cfg);
88  bool inspectCFGNode(ShPtr<CFGNode> node);
91  CFGNodeQueue &toBeVisited, CFGNode::CFGNodeSet &visited) const;
93  CFGNodeQueue &toBeVisited, CFGNode::CFGNodeSet &visited,
94  llvm::Loop *loop) const;
95  bool BFSTraverse(ShPtr<CFGNode> cfg,
96  std::function<bool (ShPtr<CFGNode>)> inspectFunc) const;
98  std::function<bool (ShPtr<CFGNode>)> inspectFunc) const;
100  std::function<bool (ShPtr<CFGNode>)> pred) const;
102  const ShPtr<CFGNode> &node2) const;
104 
107  bool isSequence(const ShPtr<CFGNode> &node) const;
109  const ShPtr<CFGNode> &node) const;
110  bool isIfElseStatement(const ShPtr<CFGNode> &node) const;
111  bool isIfStatement(const ShPtr<CFGNode> &node, std::size_t succ) const;
113  std::size_t succ) const;
115  std::size_t succ) const;
117  std::size_t succ) const;
119  std::size_t succ) const;
121  std::size_t succ) const;
122  bool isContinueStatement(const ShPtr<CFGNode> &node) const;
123  bool isForLoop(const ShPtr<CFGNode> &node) const;
124  bool isWhileTrueLoop(const ShPtr<CFGNode> &node) const;
126  std::size_t succ) const;
127  bool isSwitchStatement(const ShPtr<CFGNode> &node) const;
128  bool canBeCloned(const ShPtr<CFGNode> &node) const;
130 
133  void reduceToSequence(ShPtr<CFGNode> node);
136  void reduceToIfStatement(ShPtr<CFGNode> node, std::size_t succ);
137  void reduceToIfStatementClone(ShPtr<CFGNode> node, std::size_t succ);
139  std::size_t succ);
141  std::size_t succ);
143  std::size_t succ);
145  void reduceToForLoop(ShPtr<CFGNode> node);
148  ShPtr<CFGNode> node, std::size_t succ);
151 
155  const ShPtr<CFGNode> &clause, const ShPtr<CFGNode> &ifSuccessor);
157  const ShPtr<CFGNode> &clause, const ShPtr<CFGNode> &ifSuccessor);
159  const ShPtr<Statement> &trueBody,
160  const ShPtr<Statement> &falseBody = nullptr) const;
162 
165  ShPtr<CFGNode> getLoopSuccessor(const ShPtr<CFGNode> &loopNode) const;
166  void completelyReduceLoop(ShPtr<CFGNode> loopNode);
168 
172  ShPtr<CFGNode> getSwitchSuccessor(const ShPtr<CFGNode> &switchNode) const;
174  const ShPtr<CFGNode> &switchNode) const;
175  bool isNodeAfterSwitchClause(const ShPtr<CFGNode> &node,
176  const ShPtr<CFGNode> &clauseNode) const;
177  bool hasDefaultClause(const ShPtr<CFGNode> &switchNode,
178  const ShPtr<CFGNode> &switchSuccessor) const;
179  bool isReducibleClause(const ShPtr<CFGNode> &clauseNode,
180  const ShPtr<CFGNode> &switchNode,
181  const ShPtr<CFGNode> &switchSuccessor,
182  bool hasDefault = true) const;
183  bool hasOnlySwitchOrClausesInPreds(const ShPtr<CFGNode> &clauseNode,
184  const ShPtr<CFGNode> &switchNode, bool hasDefault) const;
185  bool fallsThroughToAnotherCase(const ShPtr<CFGNode> &clauseNode,
186  const ShPtr<CFGNode> &switchNode, bool hasDefault) const;
188  const ShPtr<CFGNode> &switchSuccessor, bool hasDefault);
190  bool hasDefault) const;
192  const ShPtr<CFGNode> &switchSuccessor) const;
194  const SwitchClauseVector &clauses) const;
196  const ShPtr<CFGNode> &switchNode,
197  const ShPtr<CFGNode> &switchSuccessor,
198  const CFGNode::CFGNodeSet &generated);
199  bool isClauseTerminatedByBreak(const ShPtr<CFGNode> &clauseNode,
200  const ShPtr<CFGNode> &switchSuccessor) const;
202  const ExprVector &conds, const ShPtr<Statement> &clauseBody) const;
203  void removeReducedSuccsOfSwitch(const ShPtr<CFGNode> &switchNode,
204  bool hasDefault) const;
206 
210  const ShPtr<CFGNode> &succ);
212  const ShPtr<CFGNode> &succ);
214  const ShPtr<CFGNode> &target);
216  const ShPtr<CFGNode> &to);
217  ShPtr<Statement> getPHICopiesForSuccessor(llvm::BasicBlock *currBB,
218  llvm::BasicBlock *succ);
220 
223  void initialiazeLLVMAnalyses(llvm::Function &func);
224  llvm::Loop *getLoopFor(const ShPtr<CFGNode> &node) const;
225  bool isLoopHeader(const ShPtr<CFGNode> &node) const;
226  bool isLoopHeader(const ShPtr<CFGNode> &node, llvm::Loop *loop) const;
227  bool isNodeOutsideLoop(const ShPtr<CFGNode> &node, llvm::Loop *loop) const;
228  bool isInParentLoopOf(const ShPtr<CFGNode> &node, llvm::Loop *loop) const;
229  unsigned getTripCount(llvm::Loop *loop) const;
230  bool canBeForLoop(llvm::Loop *loop) const;
232 
236  ShPtr<Statement> statement, SwitchParent sp);
237  void replaceGoto(CFGNodeVector &targets);
238  void correctUndefinedLabels();
239  std::vector<ShPtr<Statement>> findContinueOrBreakStatements(
240  ShPtr<Statement> parent, SwitchParent sp);
241  unsigned getStatementCount(ShPtr<Statement> statement);
242  void insertClonedLoopTargets( ShPtr<Statement> origParent,
243  ShPtr<Statement> newParent);
244  void fixClonedGotos(ShPtr<Statement> statement);
246 
249  void addGotoTargetIfNotExists(const ShPtr<CFGNode> &node);
251  const ShPtr<CFGNode> &clause, const ShPtr<CFGNode> &ifSuccessor) const;
252  std::string getLabel(const ShPtr<CFGNode> &node) const;
253  void cleanUp();
255 
257  llvm::Pass *basePass;
258 
260  llvm::LoopInfo *loopInfo;
261 
262  // Anylysis of scalar expressions in loops.
263  llvm::ScalarEvolution *scalarEvolution;
264 
267 
270 
273 
277 
280 
283 
286 
289 
292 
293  // A set of already reduced loops.
295 
296  // A set of already reduced loops.
298 
299  // A stack representing hierarchy of the parent statements during structuring.
301 
302  // A set of statements that are already on the stack.
304 
305  // A vector of nodes, which are targets of goto.
307 
308  // A set of nodes, which are targets of goto.
310 
311  // A set of nodes, which are already generated to the resulting code.
313 
316 };
317 
318 } // namespace llvmir2hll
319 } // namespace retdec
320 
321 #endif
A converter of LLVM basic blocks.
A representation of a control-flow graph node.
A converter of LLVM basic blocks.
Definition: basic_block_converter.h:42
std::unordered_set< ShPtr< CFGNode > > CFGNodeSet
Definition: cfg_node.h:58
A converter of the LLVM function structure.
Definition: structure_converter.h:51
void reduceToIfStatementClone(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement without else c...
Definition: structure_converter.cpp:1147
void reduceToSequence(ShPtr< CFGNode > node)
Reduces node node and its only successor into a single node which contains merged bodies of both node...
Definition: structure_converter.cpp:1059
std::unordered_set< llvm::Loop * > LoopSet
Definition: structure_converter.h:65
void reduceToNestedWhileTrueLoopWithContinueInHeader(ShPtr< CFGNode > node, std::size_t succ)
Reduces the given node node is into a while(true) statement, when on the index succ is the body of th...
Definition: structure_converter.cpp:1394
std::stack< ShPtr< CFGNode > > CFGNodeStack
Definition: structure_converter.h:63
std::unordered_map< llvm::BasicBlock *, BBSet > MapBBToBBSet
Definition: structure_converter.h:68
void reduceToIfStatement(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement without else c...
Definition: structure_converter.cpp:1118
BasicBlockConverter bbConverter
A converter of the LLVM basic block.
Definition: structure_converter.h:269
void replaceGoto(CFGNodeVector &targets)
Replaces goto with code if there is only one reference to it.
Definition: structure_converter.cpp:165
ShPtr< Statement > getPHICopiesForSuccessor(llvm::BasicBlock *currBB, llvm::BasicBlock *succ)
Returns PHI copies for the given basic block currBB and its successor succ.
Definition: structure_converter.cpp:2213
unsigned getStatementCount(ShPtr< Statement > statement)
Returns number of statements in parent statement (body of if/while etc.)
Definition: structure_converter.cpp:240
std::unordered_map< llvm::Loop *, ShPtr< CFGNode > > MapLoopToCFGNode
Definition: structure_converter.h:72
llvm::LoopInfo * loopInfo
Information about loops.
Definition: structure_converter.h:260
bool isNodeAfterSwitchClause(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &clauseNode) const
Determines whether the given node node is after the given switch clause clauseNode.
Definition: structure_converter.cpp:1698
bool isIfStatementWithBreakByGotoInLoop(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and in its successor on...
Definition: structure_converter.cpp:828
std::unordered_map< ShPtr< CFGNode >, DFSNodeState > MapCFGNodeToDFSNodeState
Definition: structure_converter.h:71
std::unordered_map< ShPtr< CFGNode >, ShPtr< SwitchClause > > MapCFGNodeToSwitchClause
Definition: structure_converter.h:70
std::queue< ShPtr< CFGNode > > CFGNodeQueue
Definition: structure_converter.h:62
bool isNestedWhileTrueLoopWithContinueInHeader(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is a while(true) statement, when on the index succ is the body...
Definition: structure_converter.cpp:960
ShPtr< Statement > getIfClauseBody(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &clause, const ShPtr< CFGNode > &ifSuccessor)
Creates a new body of the given if clause clause.
Definition: structure_converter.cpp:1505
void reduceToForLoop(ShPtr< CFGNode > node)
Reduces node node into a node with for loop.
Definition: structure_converter.cpp:1329
ShPtr< Statement > getGotoForSuccessor(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &target)
Creates a goto statement which jumps from the given node node to the given target node target.
Definition: structure_converter.cpp:2173
bool isSequenceWithTerminatingBranchToClone(const ShPtr< CFGNode > &node) const
Determines whether the given node node can be reduced with following node as a sequence,...
Definition: structure_converter.cpp:684
ShPtr< Statement > getAssignsToPHINodes(const ShPtr< CFGNode > &from, const ShPtr< CFGNode > &to)
Returns assignments to the PHI nodes from the given node from and to the given node to.
Definition: structure_converter.cpp:2198
bool isIfStatementWithBreakInLoop(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and in its successor on...
Definition: structure_converter.cpp:795
DFSNodeState
Information about state of node during DFS traversal.
Definition: structure_converter.h:54
ShPtr< IfStmt > getIfStmt(const ShPtr< Expression > &cond, const ShPtr< Statement > &trueBody, const ShPtr< Statement > &falseBody=nullptr) const
Returns new if statement with the given condition cond and true body trueBody and false body (else cl...
Definition: structure_converter.cpp:1556
void correctUndefinedLabels()
If goto target label is not used in code, it is replaced with its clone (that is used)
Definition: structure_converter.cpp:267
void reduceToIfElseStatementWithBreakInLoop(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement with break sta...
Definition: structure_converter.cpp:1176
BBSet reducedSwitches
Definition: structure_converter.h:297
void initialiazeLLVMAnalyses(llvm::Function &func)
Initializes required LLVM analyses for converted function func.
Definition: structure_converter.cpp:2258
LoopSet reducedLoops
Definition: structure_converter.h:294
ShPtr< CFGNode > getSwitchSuccessor(const ShPtr< CFGNode > &switchNode) const
Returns successor of the given switch node switchNode.
Definition: structure_converter.cpp:1657
ShPtr< CFGNode > popFromQueue(CFGNodeQueue &queue) const
Pop and return node from the given queue queue.
Definition: structure_converter.cpp:498
bool hasDefaultClause(const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor) const
Determines whether the given switch node switchNode has a default clause.
Definition: structure_converter.cpp:1724
void fixClonedGotos(ShPtr< Statement > statement)
Definition: structure_converter.cpp:130
llvm::Pass * basePass
Pass that have instantiated the converter.
Definition: structure_converter.h:257
std::vector< ShPtr< Statement > > findContinueOrBreakStatements(ShPtr< Statement > parent, SwitchParent sp)
Finds break and continue statements in cloned statements.
Definition: structure_converter.cpp:2138
MapLoopToCFGNode loopHeaders
Definition: structure_converter.h:276
void addGotoTargetIfNotExists(const ShPtr< CFGNode > &node)
Adds node node to the vector of the goto targets if it isn't already there.
Definition: structure_converter.cpp:2393
bool isIfElseStatementWithContinue(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and in its successor on...
Definition: structure_converter.cpp:860
bool isIfStatement(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement without else clause and if body is in the s...
Definition: structure_converter.cpp:721
void reduceToContinueStatement(ShPtr< CFGNode > node)
Reduces node node into a node which is terminated by switch statement.
Definition: structure_converter.cpp:1297
bool isInParentLoopOf(const ShPtr< CFGNode > &node, llvm::Loop *loop) const
Determines whether the given node node is in the parent loop of the given loop loop.
Definition: structure_converter.cpp:2338
std::unordered_map< ShPtr< Statement >, std::vector< ShPtr< Statement > >> MapStmtToClones
Definition: structure_converter.h:75
bool hasOnlySwitchOrClausesInPreds(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Determines whether the given switch clause clauseNode has only switch node or other clauses in predec...
Definition: structure_converter.cpp:1782
ShPtr< Statement > replaceBreakOrContinueOutsideLoop(ShPtr< Statement > statement, SwitchParent sp)
Replaces break/continue statements that are outside of loop with goto statements.
Definition: structure_converter.cpp:284
bool isNodeAfterAllSwitchClauses(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &switchNode) const
Determines whether the given node node is after all clauses of the given switch switchNode.
Definition: structure_converter.cpp:1673
CFGNode::CFGNodeSet statementsOnStack
Definition: structure_converter.h:303
void reduceToWhileTrueLoop(ShPtr< CFGNode > node)
Reduces node node into a node with while(true) loop.
Definition: structure_converter.cpp:1364
llvm::Loop * getLoopFor(const ShPtr< CFGNode > &node) const
Returns the innermost loop for the given node node. If node is not inside loop, returns nulptr.
Definition: structure_converter.cpp:2270
bool isIfElseStatement(const ShPtr< CFGNode > &node) const
Determines whether the given the given node node is an if statement with else clause.
Definition: structure_converter.cpp:704
std::vector< ShPtr< CFGNode > > CFGNodeVector
Definition: structure_converter.h:64
void completelyReduceLoop(ShPtr< CFGNode > loopNode)
Completely reduces the given loop node loopNode.
Definition: structure_converter.cpp:1608
MapTargetToGoto targetReferences
A map of references for goto targets.
Definition: structure_converter.h:288
std::unordered_set< llvm::BasicBlock * > BBSet
Definition: structure_converter.h:61
std::string getLabel(const ShPtr< CFGNode > &node) const
Returns a label of the given node node.
Definition: structure_converter.cpp:2423
std::vector< ShPtr< SwitchClause > > SwitchClauseVector
Definition: structure_converter.h:66
ShPtr< Statement > getIfClauseBodyClone(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &clause, const ShPtr< CFGNode > &ifSuccessor)
Creates a new body of the given if clause clause. The body of the clause is cloned.
Definition: structure_converter.cpp:1528
CFGNode::CFGNodeSet gotoTargetsSet
Definition: structure_converter.h:309
unsigned getTripCount(llvm::Loop *loop) const
Returns number of iterations for the given for loop loop. If loop is not a for loop,...
Definition: structure_converter.cpp:2362
std::unordered_map< llvm::BasicBlock *, ShPtr< CFGNode > > MapBBToCFGNode
Definition: structure_converter.h:69
ShPtr< LabelsHandler > labelsHandler
A handler of labels.
Definition: structure_converter.h:266
CFGNodeStack statementsStack
Definition: structure_converter.h:300
bool existsPathWithoutLoopsBetween(const ShPtr< CFGNode > &node1, const ShPtr< CFGNode > &node2) const
Determines whether exists direct path (without loops) between two given nodes node1 and node2.
Definition: structure_converter.cpp:650
MapBBToBBSet generatedPHINodes
A map of already generated phi nodes from specific basic blocks.
Definition: structure_converter.h:279
void detectBackEdges(ShPtr< CFGNode > cfg) const
Traverses the given control-flow graph cfg and detects all back edges.
Definition: structure_converter.cpp:364
void addClausesWithTheSameCond(ShPtr< SwitchStmt > switchStmt, const ExprVector &conds, const ShPtr< Statement > &clauseBody) const
Adds case clauses with different conditions, but with the same clause body to the given switch statem...
Definition: structure_converter.cpp:2042
bool reduceCFG(ShPtr< CFGNode > cfg)
Traverses the given control-flow graph cfg and tries to reduce some nodes to control-flow statements.
Definition: structure_converter.cpp:400
bool isClauseTerminatedByBreak(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchSuccessor) const
Determines whether the given switch clause clauseNode is terminated by a break statement.
Definition: structure_converter.cpp:2023
ShPtr< SwitchStmt > getSwitchStmt(const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor, bool hasDefault)
Returns new switch statement which is created from the given switch node switchNode.
Definition: structure_converter.cpp:1841
CFGNode::CFGNodeSet generatedNodes
Definition: structure_converter.h:312
MapStmtToClones stmtClones
A map of clones of statement.
Definition: structure_converter.h:291
ShPtr< CFGNode > BFSFindFirst(ShPtr< CFGNode > cfg, std::function< bool(ShPtr< CFGNode >)> pred) const
Traverses the given control-flow graph cfg using breadth-first search and returns first node which sa...
Definition: structure_converter.cpp:625
bool isReducibleClause(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor, bool hasDefault=true) const
Determines whether the given switch clause clauseNode is a clause ready to be reduced.
Definition: structure_converter.cpp:1748
bool isNodeOutsideLoop(const ShPtr< CFGNode > &node, llvm::Loop *loop) const
Determines whether the given node node is outside of the given loop loop.
Definition: structure_converter.cpp:2320
bool canBeCloned(const ShPtr< CFGNode > &node) const
Determines whether the given node node can be cloned.
Definition: structure_converter.cpp:1031
llvm::ScalarEvolution * scalarEvolution
Definition: structure_converter.h:263
bool fallsThroughToAnotherCase(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Determines whether the given switch clause clauseNode falls through to the another case clause or to ...
Definition: structure_converter.cpp:1813
bool canBeForLoop(llvm::Loop *loop) const
Determines whether the given loop loop can be a for loop.
Definition: structure_converter.cpp:2377
SwitchClauseVector getSwitchClauses(const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Returns a vector of clauses of the given switch node switchNode.
Definition: structure_converter.cpp:1871
ShPtr< SwitchClause > findFirstClauseWithSinglePred(const SwitchClauseVector &clauses) const
Returns first switch clause from the vector of clauses clauses which has only single predecessor.
Definition: structure_converter.cpp:1955
bool isIfStatementWithTerminatingBranch(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement and successor on the index succ is terminat...
Definition: structure_converter.cpp:741
void removeReducedSuccsOfSwitch(const ShPtr< CFGNode > &switchNode, bool hasDefault) const
Removes reduced successors of the given switch node switchNode.
Definition: structure_converter.cpp:2064
bool isContinueStatement(const ShPtr< CFGNode > &node) const
Determines whether the given node node is terminated by continue statement.
Definition: structure_converter.cpp:895
bool isSwitchStatement(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a switch statement.
Definition: structure_converter.cpp:991
std::unordered_map< ShPtr< CFGNode >, std::vector< ShPtr< GotoStmt > >> MapTargetToGoto
Definition: structure_converter.h:74
bool isWhileTrueLoop(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a while(true) loop.
Definition: structure_converter.cpp:945
bool inspectCFGNode(ShPtr< CFGNode > node)
Inspects the given CFG node node and tries to reduce this and neighboring nodes to any control-flow s...
Definition: structure_converter.cpp:417
ShPtr< Statement > convertFuncBody(llvm::Function &func)
Converts body of the given LLVM function func into a sequence of statements in BIR which include cond...
Definition: structure_converter.cpp:87
bool isIfStatementWithTerminatingBranchToClone(const ShPtr< CFGNode > &node, std::size_t succ) const
Determines whether the given node node is an if statement and successor on the index succ is terminat...
Definition: structure_converter.cpp:774
bool isForLoop(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a reducible for loop.
Definition: structure_converter.cpp:927
bool isSequence(const ShPtr< CFGNode > &node) const
Determines whether the given node node can be reduced with following node as a sequence.
Definition: structure_converter.cpp:669
ShPtr< Statement > getSuccessorsBodyClone(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &succ)
Creates a new body of the given node node successor succ. The body of the successor is cloned.
Definition: structure_converter.cpp:2105
bool BFSTraverse(ShPtr< CFGNode > cfg, std::function< bool(ShPtr< CFGNode >)> inspectFunc) const
Traverses the given control-flow graph cfg using breadth-first search and inspect every node by funct...
Definition: structure_converter.cpp:570
CFGNodeVector gotoTargets
Definition: structure_converter.h:306
SwitchClauseVector sortSwitchClauses(const SwitchClauseVector &clauses, const ShPtr< CFGNode > &switchSuccessor) const
Returns sorted vector of switch clauses clauses.
Definition: structure_converter.cpp:1916
ShPtr< CFGNode > getLoopSuccessor(const ShPtr< CFGNode > &loopNode) const
Returns successor of the given loop node loopNode.
Definition: structure_converter.cpp:1590
void reduceToIfElseStatementWithBreakByGotoInLoop(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement with goto stat...
Definition: structure_converter.cpp:1221
void addBranchMetadataToEndOfBodyIfNeeded(ShPtr< Statement > &body, const ShPtr< CFGNode > &clause, const ShPtr< CFGNode > &ifSuccessor) const
Adds metadata of the form "branch -> xxx" to the body of the given if statement (if needed).
Definition: structure_converter.cpp:2407
void cleanUp()
Cleans up the helper containers.
Definition: structure_converter.cpp:2432
ShPtr< Statement > getClauseBody(const ShPtr< CFGNode > &clauseNode, const ShPtr< CFGNode > &switchNode, const ShPtr< CFGNode > &switchSuccessor, const CFGNode::CFGNodeSet &generated)
Returns new case clause of the switch statement which is created from the given switch node clauseNod...
Definition: structure_converter.cpp:1979
MapStmtToTargetNode gotoTargetsToCfgNodes
A map of goto target statements to cfg nodes.
Definition: structure_converter.h:285
ShPtr< Statement > getSuccessorsBody(const ShPtr< CFGNode > &node, const ShPtr< CFGNode > &succ)
Creates a new body of the given node node successor succ.
Definition: structure_converter.cpp:2089
void reduceToIfElseStatement(ShPtr< CFGNode > node)
Reduces node node and both its successors into a single node with if statement with else clause.
Definition: structure_converter.cpp:1094
std::unordered_map< ShPtr< Statement >, ShPtr< CFGNode > > MapStmtToTargetNode
Definition: structure_converter.h:73
ShPtr< LLVMValueConverter > converter
A converter from LLVM values to values in BIR.
Definition: structure_converter.h:272
MapStmtToTargetNode loopTargets
A map of targets for break and continue statements.
Definition: structure_converter.h:282
void addUnvisitedSuccessorsToQueueInLoop(const ShPtr< CFGNode > &node, CFGNodeQueue &toBeVisited, CFGNode::CFGNodeSet &visited, llvm::Loop *loop) const
Adds all unvisited successors inside loop loop of the given node node to the queue toBeVisited and al...
Definition: structure_converter.cpp:543
ShPtr< Module > resModule
The resulting module in BIR.
Definition: structure_converter.h:315
void reduceSwitchStatement(ShPtr< CFGNode > node)
Reduces node node into a node with the switch statement.
Definition: structure_converter.cpp:1633
ShPtr< CFGNode > createCFG(llvm::BasicBlock &root)
Creates control-flow graph of the function from the given root basic block root.
Definition: structure_converter.cpp:325
void addUnvisitedSuccessorsToQueue(const ShPtr< CFGNode > &node, CFGNodeQueue &toBeVisited, CFGNode::CFGNodeSet &visited) const
Adds all unvisited successors of the given node node to the queue toBeVisited and also to the set of ...
Definition: structure_converter.cpp:513
void structureByGotos(ShPtr< CFGNode > cfg)
Completely structures given CFG cfg using goto statements.
Definition: structure_converter.cpp:1439
bool isLoopHeader(const ShPtr< CFGNode > &node) const
Determines whether the given node node is a loop header.
Definition: structure_converter.cpp:2287
std::pair< ExprVector, ShPtr< CFGNode > > SwitchClause
Definition: structure_converter.h:59
void insertClonedLoopTargets(ShPtr< Statement > origParent, ShPtr< Statement > newParent)
Inserts cloned break/continue stmts in case they need replacing.
Definition: structure_converter.cpp:2122
StructureConverter(llvm::Pass *basePass, ShPtr< LLVMValueConverter > conv, ShPtr< Module > module)
Constructs a new structure converter.
Definition: structure_converter.cpp:72
bool BFSTraverseLoop(ShPtr< CFGNode > cfg, std::function< bool(ShPtr< CFGNode >)> inspectFunc) const
Traverses the given control-flow graph cfg of a loop using breadth-first search and inspect every nod...
Definition: structure_converter.cpp:598
void reduceToSequenceClone(ShPtr< CFGNode > node)
Reduces node node and its only successor into a single node which contains merged bodies of both node...
Definition: structure_converter.cpp:1077
void reduceToIfElseStatementWithContinue(ShPtr< CFGNode > node, std::size_t succ)
Reduces node node and its successor on index succ into a single node with if statement with continue ...
Definition: structure_converter.cpp:1257
A mixin to make classes non-copyable.
Definition: non_copyable.h:27
ShPtr< Module > module
The current module.
Definition: hll_writer.cpp:100
Definition: itanium_ast_ctypes_parser.h:12
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::vector< ShPtr< Expression > > ExprVector
Vector of expressions.
Definition: types.h:99
SwitchParent
Enum class to distinguish when parent of statement is switch or not.
Definition: structure_converter.h:46
Definition: archive_wrapper.h:19
A mixin to make classes non-copyable.
Declarations, aliases, macros, etc. for the use of smart pointers.
Aliases for several useful types.