retdec
cfg.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_LLVMIR2HLL_GRAPHS_CFG_CFG_H
8 #define RETDEC_LLVMIR2HLL_GRAPHS_CFG_CFG_H
9 
10 #include <cstddef>
11 #include <string>
12 #include <unordered_map>
13 #include <vector>
14 
18 
19 namespace retdec {
20 namespace llvmir2hll {
21 
22 class Expression;
23 class Function;
24 class Statement;
25 
41 class CFG final: private retdec::utils::NonCopyable {
42  friend class RecursiveCFGBuilder;
43  friend class NonRecursiveCFGBuilder;
44 public:
45  class Node;
46  class Edge;
47 
49  using stmt_iterator = StmtVector::const_iterator;
50 
52  using stmt_reverse_iterator = StmtVector::const_reverse_iterator;
53 
55  using NodeVector = std::vector<ShPtr<Node>>;
56 
58  using node_iterator = NodeVector::const_iterator;
59 
61  using EdgeVector = std::vector<ShPtr<Edge>>;
62 
64  using edge_iterator = EdgeVector::const_iterator;
65 
67  using succ_iterator = EdgeVector::const_iterator;
68 
70  using pred_iterator = EdgeVector::const_iterator;
71 
74  using StmtInNode = std::pair<ShPtr<Node>, stmt_iterator>;
75 
82  friend class RecursiveCFGBuilder;
83  friend class NonRecursiveCFGBuilder;
84  public:
85  Node();
86  explicit Node(const std::string &label);
87 
88  std::string getLabel() const;
89 
92  bool hasStmts() const;
93  std::size_t getNumberOfStmts() const;
94  void addStmt(ShPtr<Statement> stmt);
95  void replaceStmt(ShPtr<Statement> stmt, const StmtVector &stmts);
96  void removeStmt(ShPtr<Statement> stmt);
97 
98  stmt_iterator stmt_begin() const;
99  stmt_iterator stmt_end() const;
100 
104 
107  bool hasSuccs() const;
108  bool hasSucc(ShPtr<Edge> edge) const;
109  std::size_t getNumberOfSuccs() const;
110  void addSucc(ShPtr<Edge> succ);
111  ShPtr<Edge> getFirstSucc() const;
112  void removeSucc(ShPtr<Edge> succ);
113 
114  succ_iterator succ_begin() const;
115  succ_iterator succ_end() const;
117 
120  bool hasPreds() const;
121  bool hasPred(ShPtr<Edge> edge) const;
122  std::size_t getNumberOfPreds() const;
123  void addPred(ShPtr<Edge> pred);
124  void removePred(ShPtr<Edge> succ);
125 
126  pred_iterator pred_begin() const;
127  pred_iterator pred_end() const;
129 
130  private:
132  std::string label;
133 
136 
139 
142  };
143 
150  friend class RecursiveCFGBuilder;
152  public:
154  ShPtr<Expression> label = nullptr);
155 
156  ShPtr<Node> getSrc() const;
157  ShPtr<Expression> getLabel() const;
158  ShPtr<Node> getDst() const;
159 
160  private:
163 
166 
169  };
170 
171 public:
172  CFG(ShPtr<Function> func);
173 
175 
178  std::size_t getNumberOfNodes() const;
179  void addEntryNode(ShPtr<Node> node);
180  void addExitNode(ShPtr<Node> node);
181  ShPtr<Node> getEntryNode() const;
182  ShPtr<Node> getExitNode() const;
184  bool stmtExistsInCFG(ShPtr<Statement> stmt) const;
187  bool hasNodeForStmt(ShPtr<Statement> stmt) const;
188  void addNode(ShPtr<Node> node);
189  void splitNodes();
190  void removeNode(ShPtr<Node> node);
191  void removeEmptyNodes();
192  void removeUnreachableNodes();
194  void removeStmt(ShPtr<Statement> stmt);
195  void replaceStmt(ShPtr<Statement> stmt, const StmtVector &stmts);
196 
198 
199  node_iterator node_begin() const;
200  node_iterator node_end() const;
202 
206  ShPtr<Expression> label = nullptr);
207  void removeEdge(ShPtr<Edge> edge);
208 
209  edge_iterator edge_begin() const;
210  edge_iterator edge_end() const;
212 
213 private:
215  using StmtNodeMapping = std::unordered_map<ShPtr<Statement>, ShPtr<Node>>;
216 
217 private:
218  ShPtr<Node> addNode(const std::string &label = "");
219 
220  void splitNode(ShPtr<Node> node);
221 
229 
230 private:
233 
236 
239 
242 
245 
248 };
249 
250 } // namespace llvmir2hll
251 } // namespace retdec
252 
253 #endif
An edge of a CFG (represents program flow).
Definition: cfg.h:149
ShPtr< Node > getSrc() const
Returns the source node of the edge.
Definition: cfg.cpp:314
ShPtr< Expression > label
Edge label.
Definition: cfg.h:165
Edge(ShPtr< Node > src, ShPtr< Node > dst, ShPtr< Expression > label=nullptr)
Constructs a new edge src -> dst, optionally labelled by label.
Definition: cfg.cpp:308
ShPtr< Node > getDst() const
Returns the destination node of the edge.
Definition: cfg.cpp:330
ShPtr< Node > src
Edge source.
Definition: cfg.h:162
ShPtr< Expression > getLabel() const
Returns the edge's label.
Definition: cfg.cpp:323
ShPtr< Node > dst
Edge destination.
Definition: cfg.h:168
A node of a CFG (represents a basic block).
Definition: cfg.h:81
std::size_t getNumberOfPreds() const
Returns the number of predecessors.
Definition: cfg.cpp:256
std::size_t getNumberOfStmts() const
Returns the number of statements in the node.
Definition: cfg.cpp:80
succ_iterator succ_end() const
Returns an iterator past the last edge leaving the node.
Definition: cfg.cpp:229
bool hasPred(ShPtr< Edge > edge) const
Returns true if the node has the given predecessor, false otherwise.
Definition: cfg.cpp:247
pred_iterator pred_begin() const
Returns an iterator to the first edge entering the node.
Definition: cfg.cpp:289
bool hasStmts() const
Returns true if the node has some statements, false otherwise.
Definition: cfg.cpp:73
Node()
Constructs a new node.
Definition: cfg.cpp:33
StmtVector stmts
Vector of statements forming a basic block.
Definition: cfg.h:135
stmt_iterator stmt_begin() const
Returns an iterator to the first statement in the basic block.
Definition: cfg.cpp:130
bool hasSucc(ShPtr< Edge > edge) const
Returns true if the node has the given successor, false otherwise.
Definition: cfg.cpp:171
std::string label
Label.
Definition: cfg.h:132
stmt_reverse_iterator stmt_rbegin() const
Returns a constant reverse iterator to the last statement in the basic block.
Definition: cfg.cpp:145
void addStmt(ShPtr< Statement > stmt)
Adds stmt to the statements in the node.
Definition: cfg.cpp:90
pred_iterator pred_end() const
Returns an iterator past the last edge entering the node.
Definition: cfg.cpp:296
void addSucc(ShPtr< Edge > succ)
Adds the given successor to the node.
Definition: cfg.cpp:190
stmt_reverse_iterator stmt_rend() const
Returns a constant reverse iterator before the first statement in the basic block.
Definition: cfg.cpp:153
EdgeVector succs
Vector of edges leaving the node.
Definition: cfg.h:138
void removeStmt(ShPtr< Statement > stmt)
Removes the given statement from the node.
Definition: cfg.cpp:121
bool hasPreds() const
Returns true if the node has some predecessors, false otherwise.
Definition: cfg.cpp:236
ShPtr< Edge > getFirstSucc() const
Returns the first successor of the node.
Definition: cfg.cpp:201
std::size_t getNumberOfSuccs() const
Returns the number of successors.
Definition: cfg.cpp:180
bool hasSuccs() const
Returns true if the node has some successors, false otherwise.
Definition: cfg.cpp:160
EdgeVector preds
Vector of edges entering the node.
Definition: cfg.h:141
stmt_iterator stmt_end() const
Returns an iterator past the last statement in the basic block.
Definition: cfg.cpp:137
void addPred(ShPtr< Edge > pred)
Adds the given predecessor to the node.
Definition: cfg.cpp:266
std::string getLabel() const
Returns the node's label.
Definition: cfg.cpp:47
void removePred(ShPtr< Edge > succ)
Removes the given predecessor from the node.
Definition: cfg.cpp:280
void removeSucc(ShPtr< Edge > succ)
Removes the given successor from the node.
Definition: cfg.cpp:213
succ_iterator succ_begin() const
Returns an iterator to the first edge leaving the node.
Definition: cfg.cpp:222
void replaceStmt(ShPtr< Statement > stmt, const StmtVector &stmts)
Replaces stmt with stmts.
Definition: cfg.cpp:104
A representation of a control-flow graph (CFG).
Definition: cfg.h:41
ShPtr< Node > getExitNode() const
Returns the exit node of the CFG.
Definition: cfg.cpp:386
ShPtr< Edge > addEdge(ShPtr< Node > src, ShPtr< Node > dst, ShPtr< Expression > label=nullptr)
Adds a new edge to the CFG.
Definition: cfg.cpp:726
void removeStmt(ShPtr< Statement > stmt)
Removes stmt from the CFG.
Definition: cfg.cpp:518
StmtNodeMapping stmtNodeMapping
Mapping between a statement and a node in which the statement is.
Definition: cfg.h:247
void removeStmtFromNode(ShPtr< Statement > stmt, ShPtr< CFG::Node > node)
Removes the given statement from the given node.
Definition: cfg.cpp:495
ShPtr< Function > getCorrespondingFunction() const
Returns the function which corresponds to the CFG.
Definition: cfg.cpp:346
void removeNode(ShPtr< Node > node)
Removes the selected node from the CFG.
Definition: cfg.cpp:755
std::unordered_map< ShPtr< Statement >, ShPtr< Node > > StmtNodeMapping
Mapping of a statement into its corresponding node.
Definition: cfg.h:215
EdgeVector::const_iterator pred_iterator
Predecessors iterator.
Definition: cfg.h:70
NodeVector nodes
Vector of nodes.
Definition: cfg.h:235
bool stmtExistsInCFG(ShPtr< Statement > stmt) const
Returns true if the given statement exists in the CFG, false otherwise.
Definition: cfg.cpp:397
NodeVector getUnreachableNodes() const
Returns unreachable nodes.
Definition: cfg.cpp:622
void replaceStmt(ShPtr< Statement > stmt, const StmtVector &stmts)
Replaces stmt with stmts in the CFG.
Definition: cfg.cpp:570
void removeEmptyNodes()
Removes nodes with no statements from the CFG.
Definition: cfg.cpp:911
StmtVector::const_iterator stmt_iterator
Statements iterator.
Definition: cfg.h:49
StmtVector::const_reverse_iterator stmt_reverse_iterator
Statements reverse iterator.
Definition: cfg.h:52
void addNode(ShPtr< Node > node)
Adds the given node to the CFG.
Definition: cfg.cpp:708
EdgeVector::const_iterator edge_iterator
Edges iterator.
Definition: cfg.h:64
ShPtr< Node > getEntryNode() const
Returns the entry node of the CFG.
Definition: cfg.cpp:379
ShPtr< Node > exitNode
Exit node.
Definition: cfg.h:244
stmt_reverse_iterator getReverseIteratorFromIterator(stmt_iterator i)
Returns a reverse iterator for the given iterator i.
Definition: cfg.cpp:451
void addEntryNode(ShPtr< Node > node)
Adds the given entry node to the CFG.
Definition: cfg.cpp:356
void addExitNode(ShPtr< Node > node)
Adds the given entry node to the CFG.
Definition: cfg.cpp:369
std::size_t getNumberOfNodes() const
Returns the number of nodes in the CFG.
Definition: cfg.cpp:469
void validateEveryPredAndSuccIsInNodes()
Asserts out if there is a node whose predecessor/successor is not in nodes.
Definition: cfg.cpp:967
NodeVector::const_iterator node_iterator
Nodes iterator.
Definition: cfg.h:58
static ShPtr< Statement > getLastStmtInNode(ShPtr< Node > node)
Returns the last statement in the given node.
Definition: cfg.cpp:656
ShPtr< Function > correspondingFunction
Function to which this CFG corresponds.
Definition: cfg.h:232
void splitNodes()
Splits the CFG so that each node contains a single statement.
Definition: cfg.cpp:478
EdgeVector edges
Vector of edges.
Definition: cfg.h:238
std::vector< ShPtr< Node > > NodeVector
Vector of nodes.
Definition: cfg.h:55
node_iterator node_begin() const
Returns an iterator to the first node in the CFG.
Definition: cfg.cpp:667
void splitNode(ShPtr< Node > node)
Splits the given node into several nodes, each containing a single statement.
Definition: cfg.cpp:834
StmtInNode getNodeForStmt(ShPtr< Statement > stmt) const
Returns the node and position of the given statement in the CFG.
Definition: cfg.cpp:412
ShPtr< Node > entryNode
Entry node.
Definition: cfg.h:241
CFG(ShPtr< Function > func)
Constructs a new CFG.
Definition: cfg.cpp:339
bool hasNodeForStmt(ShPtr< Statement > stmt) const
Returns true if the given statement exists in the CFG, false otherwise.
Definition: cfg.cpp:439
void validateIngoingAndOutgoingEdges()
Asserts out if there is an outgoing edge from A to B but no ingoing edge from B to A or vice versa in...
Definition: cfg.cpp:1032
EdgeVector::const_iterator succ_iterator
Successors iterator.
Definition: cfg.h:67
std::pair< ShPtr< Node >, stmt_iterator > StmtInNode
Definition: cfg.h:74
edge_iterator edge_begin() const
Returns an iterator to the first edge in the CFG.
Definition: cfg.cpp:681
std::vector< ShPtr< Edge > > EdgeVector
Vector of edges.
Definition: cfg.h:61
node_iterator node_end() const
Returns an iterator past the last node in the CFG.
Definition: cfg.cpp:674
void removeUnreachableNodes()
Removes unreachable nodes.
Definition: cfg.cpp:955
void removeEdge(ShPtr< Edge > edge)
Removes the selected edge from the CFG.
Definition: cfg.cpp:820
void validateThereAreNoEmptyNodes()
Asserts out if there is an empty node in the CFG.
Definition: cfg.cpp:989
edge_iterator edge_end() const
Returns an iterator past the last edge in the CFG.
Definition: cfg.cpp:688
void validateEveryNonEmptyStatementHasNode()
Asserts out if there is a non-empty statement without a node in the CFG.
Definition: cfg.cpp:1006
A non-recursive creator of control-flow graphs (CFGs) from functions.
Definition: non_recursive_cfg_builder.h:29
A recursive creator of control-flow graphs (CFGs) from functions.
Definition: recursive_cfg_builder.h:27
A mixin to make classes non-copyable.
Definition: non_copyable.h:27
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< Statement > > StmtVector
Vector of statements.
Definition: types.h:96
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.