retdec
non_recursive_cfg_builder.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_LLVMIR2HLL_GRAPHS_CFG_CFG_BUILDERS_NON_RECURSIVE_CFG_BUILDER_H
8 #define RETDEC_LLVMIR2HLL_GRAPHS_CFG_CFG_BUILDERS_NON_RECURSIVE_CFG_BUILDER_H
9 
10 #include <queue>
11 #include <unordered_map>
12 #include <vector>
13 
19 
20 namespace retdec {
21 namespace llvmir2hll {
22 
23 class Expression;
24 class Statement;
25 
30 public:
31  virtual void buildCFG() override;
32 
34 
35 private:
37  struct Job {
46  stmt): pred(pred), cond(cond), stmt(stmt) {}
47 
50 
53 
56  };
57 
59  struct EdgeToAdd {
68  ShPtr<Expression> cond = nullptr):
70 
73 
76 
79  };
80 
82  using JobQueue = std::queue<Job>;
83 
85  using EdgesToAdd = std::vector<EdgeToAdd>;
86 
88  using StmtNodeMapping = std::unordered_map<ShPtr<Statement>, ShPtr<CFG::Node>>;
89 
90 private:
92 
96  virtual void visit(ShPtr<AssignStmt> stmt) override;
97  virtual void visit(ShPtr<BreakStmt> stmt) override;
98  virtual void visit(ShPtr<CallStmt> stmt) override;
99  virtual void visit(ShPtr<ContinueStmt> stmt) override;
100  virtual void visit(ShPtr<EmptyStmt> stmt) override;
101  virtual void visit(ShPtr<ForLoopStmt> stmt) override;
102  virtual void visit(ShPtr<UForLoopStmt> stmt) override;
103  virtual void visit(ShPtr<GotoStmt> stmt) override;
104  virtual void visit(ShPtr<IfStmt> stmt) override;
105  virtual void visit(ShPtr<ReturnStmt> stmt) override;
106  virtual void visit(ShPtr<SwitchStmt> stmt) override;
107  virtual void visit(ShPtr<UnreachableStmt> stmt) override;
108  virtual void visit(ShPtr<VarDefStmt> stmt) override;
109  virtual void visit(ShPtr<WhileLoopStmt> stmt) override;
111 
113  EdgesToAdd &edgesToAdd,
114  ShPtr<Expression> edgeCond = nullptr);
115  void addEdgeFromVector(const EdgeToAdd &edge);
117  ShPtr<Statement> stmt);
118  void addEdgesFromVector(const EdgesToAdd &edgesToAdd);
119  void addStatement(ShPtr<Statement> stmt);
122  void createAndAddNode();
123  void createEdgesToBeAdded();
124  void createEntryNode();
125  void createExitNode();
128  ShPtr<Statement> stmt);
130  void createOtherNodes();
131  void doJob(const Job &job);
132  void doJobs();
133  void initializeCFGBuild();
134  void purgeCFG();
135  void validateCFG();
137 
138 private:
141 
144 
147 
150 
153 
156 };
157 
158 } // namespace llvmir2hll
159 } // namespace retdec
160 
161 #endif
A representation of a control-flow graph (CFG).
A base class for creators of control-flow graphs (CFGs) from functions.
A base class for creators of control-flow graphs (CFGs) from functions.
Definition: cfg_builder.h:31
A non-recursive creator of control-flow graphs (CFGs) from functions.
Definition: non_recursive_cfg_builder.h:29
void doJob(const Job &job)
Performs the given job.
Definition: non_recursive_cfg_builder.cpp:296
void visitForOrUForLoop(ShPtr< Statement > loop, ShPtr< Statement > body)
Implementation of visit() for for loops.
Definition: non_recursive_cfg_builder.cpp:224
void createNewNodeIfStmtHasSucc(ShPtr< Statement > stmt)
Creates a new node for stmt if it has a successor.
Definition: non_recursive_cfg_builder.cpp:611
void initializeCFGBuild()
Initializes all the needed data so the CFG can be built.
Definition: non_recursive_cfg_builder.cpp:158
void createEntryNode()
Creates entry node.
Definition: non_recursive_cfg_builder.cpp:170
StmtNodeMapping emptyStmtToNodeMap
Mapping of an empty statement to its node.
Definition: non_recursive_cfg_builder.h:152
NonRecursiveCFGBuilder()
Constructs a new builder.
Definition: non_recursive_cfg_builder.cpp:145
void addEdgeFromCurrNodeToSuccNode(ShPtr< Statement > stmt, EdgesToAdd &edgesToAdd, ShPtr< Expression > edgeCond=nullptr)
Finds successor and add edges to edgesToAdd for stmt.
Definition: non_recursive_cfg_builder.cpp:449
std::queue< Job > JobQueue
Queue of jobs.
Definition: non_recursive_cfg_builder.h:82
void addEdgeFromVector(const EdgeToAdd &edge)
Add edge to CFG.
Definition: non_recursive_cfg_builder.cpp:383
ShPtr< CFG::Node > currNode
Currently generated node.
Definition: non_recursive_cfg_builder.h:149
void createOtherNodes()
Creates other nodes.
Definition: non_recursive_cfg_builder.cpp:195
EdgesToAdd edgesToAddLast
Vector of saved edges that have to be added at the end.
Definition: non_recursive_cfg_builder.h:146
void purgeCFG()
Purges the CFG by removing useless nodes.
Definition: non_recursive_cfg_builder.cpp:206
JobQueue jobQueue
Queue of all jobs.
Definition: non_recursive_cfg_builder.h:140
EdgesToAdd edgesToAddFirst
Vector of saved edges for nodes that will be added first.
Definition: non_recursive_cfg_builder.h:143
void createExitNode()
Creates exit node.
Definition: non_recursive_cfg_builder.cpp:188
void addEdgesFromVector(const EdgesToAdd &edgesToAdd)
Adds edges from edgesToAdd.
Definition: non_recursive_cfg_builder.cpp:372
static ShPtr< NonRecursiveCFGBuilder > create()
Creates and returns a new NonRecursiveCFGBuilder.
Definition: non_recursive_cfg_builder.cpp:151
std::vector< EdgeToAdd > EdgesToAdd
Vector of edges.
Definition: non_recursive_cfg_builder.h:85
virtual void visit(ShPtr< GlobalVarDef > varDef) override
Definition: visitor_adapter.h:34
void addStmtToNodeAndToMapOfStmtToNode(ShPtr< Statement > stmt)
Adds stmt to currNode and to stmtNodeMapping.
Definition: non_recursive_cfg_builder.cpp:552
void resolveGotoTargets(ShPtr< Statement > stmt)
Resolve goto targets.
Definition: non_recursive_cfg_builder.cpp:541
std::unordered_map< ShPtr< Statement >, ShPtr< CFG::Node > > StmtNodeMapping
Mapping of a statement into its corresponding node.
Definition: non_recursive_cfg_builder.h:88
void addStatement(ShPtr< Statement > stmt)
Adds a statement to the current node and to map of statements to node, and adds a forward or backward...
Definition: non_recursive_cfg_builder.cpp:565
void createNewNodeAndConnectWithPredNode(ShPtr< Statement > stmt)
Creates new node and add it. Also save edge from this new node to previous node.
Definition: non_recursive_cfg_builder.cpp:581
void validateCFG()
Validates the created CFG.
Definition: non_recursive_cfg_builder.cpp:214
void createEdgesToBeAdded()
Creates connecting edges for all nodes.
Definition: non_recursive_cfg_builder.cpp:361
void createAndAddNode()
Creates new node and set it to current node.
Definition: non_recursive_cfg_builder.cpp:621
bool stopIterNextStmts
Signalizes if we want to iterate through statements or not.
Definition: non_recursive_cfg_builder.h:155
void doJobs()
Tops and pop one job from queue and starts doing of job.
Definition: non_recursive_cfg_builder.cpp:280
virtual void buildCFG() override
Builds cfg.
Definition: non_recursive_cfg_builder.cpp:246
void createNewNodeForIfSwitchForWhileStmtAndAddStmtToNode(ShPtr< Statement > stmt)
Creates new node if is needed for if, while, for, switch statements and also add statement to node.
Definition: non_recursive_cfg_builder.cpp:594
void addJobToQueue(ShPtr< CFG::Node > pred, ShPtr< Expression > cond, ShPtr< Statement > stmt)
Creates new job and add new job to queue of jobs.
Definition: non_recursive_cfg_builder.cpp:272
A visitor whose visit methods do nothing by default.
Definition: visitor_adapter.h:30
virtual void visit(ShPtr< GlobalVarDef > varDef) override
Definition: visitor_adapter.h:34
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
Definition: archive_wrapper.h:19
Declarations, aliases, macros, etc. for the use of smart pointers.
Structure for edges that will be added to CFG.
Definition: non_recursive_cfg_builder.h:59
ShPtr< CFG::Node > node
Predecessor node.
Definition: non_recursive_cfg_builder.h:72
ShPtr< Expression > cond
Condition for edge.
Definition: non_recursive_cfg_builder.h:78
ShPtr< Statement > succStmt
Statement of second one node.
Definition: non_recursive_cfg_builder.h:75
EdgeToAdd(ShPtr< CFG::Node > node, ShPtr< Statement > succStmt, ShPtr< Expression > cond=nullptr)
Constructs a new edge to add.
Definition: non_recursive_cfg_builder.h:67
Structure for jobs that have to be performed.
Definition: non_recursive_cfg_builder.h:37
ShPtr< Statement > stmt
First statement from which job starts.
Definition: non_recursive_cfg_builder.h:55
ShPtr< CFG::Node > pred
Predecessor node of this job.
Definition: non_recursive_cfg_builder.h:49
Job(ShPtr< CFG::Node > pred, ShPtr< Expression > cond, ShPtr< Statement > stmt)
Constructs a new job.
Definition: non_recursive_cfg_builder.h:45
ShPtr< Expression > cond
Condition for edge.
Definition: non_recursive_cfg_builder.h:52
Aliases for several useful types.
A visitor whose visit methods do nothing.