retdec
|
A representation of a control-flow graph (CFG). More...
#include <cfg.h>
Classes | |
class | Edge |
An edge of a CFG (represents program flow). More... | |
class | Node |
A node of a CFG (represents a basic block). More... | |
Public Types | |
using | stmt_iterator = StmtVector::const_iterator |
Statements iterator. More... | |
using | stmt_reverse_iterator = StmtVector::const_reverse_iterator |
Statements reverse iterator. More... | |
using | NodeVector = std::vector< ShPtr< Node > > |
Vector of nodes. More... | |
using | node_iterator = NodeVector::const_iterator |
Nodes iterator. More... | |
using | EdgeVector = std::vector< ShPtr< Edge > > |
Vector of edges. More... | |
using | edge_iterator = EdgeVector::const_iterator |
Edges iterator. More... | |
using | succ_iterator = EdgeVector::const_iterator |
Successors iterator. More... | |
using | pred_iterator = EdgeVector::const_iterator |
Predecessors iterator. More... | |
using | StmtInNode = std::pair< ShPtr< Node >, stmt_iterator > |
Public Member Functions | |
CFG (ShPtr< Function > func) | |
Constructs a new CFG. More... | |
ShPtr< Function > | getCorrespondingFunction () const |
Returns the function which corresponds to the CFG. More... | |
Edges Accessors | |
ShPtr< Edge > | addEdge (ShPtr< Node > src, ShPtr< Node > dst, ShPtr< Expression > label=nullptr) |
Adds a new edge to the CFG. More... | |
void | removeEdge (ShPtr< Edge > edge) |
Removes the selected edge from the CFG. More... | |
edge_iterator | edge_begin () const |
Returns an iterator to the first edge in the CFG. More... | |
edge_iterator | edge_end () const |
Returns an iterator past the last edge in the CFG. More... | |
Private Types | |
using | StmtNodeMapping = std::unordered_map< ShPtr< Statement >, ShPtr< Node > > |
Mapping of a statement into its corresponding node. More... | |
Private Member Functions | |
ShPtr< Node > | addNode (const std::string &label="") |
Adds a new node to the CFG. More... | |
void | splitNode (ShPtr< Node > node) |
Splits the given node into several nodes, each containing a single statement. More... | |
Validation | |
void | validateEveryPredAndSuccIsInNodes () |
Asserts out if there is a node whose predecessor/successor is not in nodes . More... | |
void | validateThereAreNoEmptyNodes () |
Asserts out if there is an empty node in the CFG. More... | |
void | validateEveryNonEmptyStatementHasNode () |
Asserts out if there is a non-empty statement without a node in the CFG. More... | |
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 the CFG. More... | |
![]() | |
NonCopyable (const NonCopyable &)=delete | |
NonCopyable & | operator= (const NonCopyable &)=delete |
NonCopyable ()=default | |
~NonCopyable ()=default | |
Private Attributes | |
ShPtr< Function > | correspondingFunction |
Function to which this CFG corresponds. More... | |
NodeVector | nodes |
Vector of nodes. More... | |
EdgeVector | edges |
Vector of edges. More... | |
ShPtr< Node > | entryNode |
Entry node. More... | |
ShPtr< Node > | exitNode |
Exit node. More... | |
StmtNodeMapping | stmtNodeMapping |
Mapping between a statement and a node in which the statement is. More... | |
Friends | |
class | RecursiveCFGBuilder |
class | NonRecursiveCFGBuilder |
Nodes Accessors | |
std::size_t | getNumberOfNodes () const |
Returns the number of nodes in the CFG. More... | |
void | addEntryNode (ShPtr< Node > node) |
Adds the given entry node to the CFG. More... | |
void | addExitNode (ShPtr< Node > node) |
Adds the given entry node to the CFG. More... | |
ShPtr< Node > | getEntryNode () const |
Returns the entry node of the CFG. More... | |
ShPtr< Node > | getExitNode () const |
Returns the exit node of the CFG. More... | |
NodeVector | getUnreachableNodes () const |
Returns unreachable nodes. More... | |
bool | stmtExistsInCFG (ShPtr< Statement > stmt) const |
Returns true if the given statement exists in the CFG, false otherwise. More... | |
StmtInNode | getNodeForStmt (ShPtr< Statement > stmt) const |
Returns the node and position of the given statement in the CFG. More... | |
stmt_reverse_iterator | getReverseIteratorFromIterator (stmt_iterator i) |
Returns a reverse iterator for the given iterator i. More... | |
bool | hasNodeForStmt (ShPtr< Statement > stmt) const |
Returns true if the given statement exists in the CFG, false otherwise. More... | |
void | addNode (ShPtr< Node > node) |
Adds the given node to the CFG. More... | |
void | splitNodes () |
Splits the CFG so that each node contains a single statement. More... | |
void | removeNode (ShPtr< Node > node) |
Removes the selected node from the CFG. More... | |
void | removeEmptyNodes () |
Removes nodes with no statements from the CFG. More... | |
void | removeUnreachableNodes () |
Removes unreachable nodes. More... | |
void | removeStmtFromNode (ShPtr< Statement > stmt, ShPtr< CFG::Node > node) |
Removes the given statement from the given node. More... | |
void | removeStmt (ShPtr< Statement > stmt) |
Removes stmt from the CFG. More... | |
void | replaceStmt (ShPtr< Statement > stmt, const StmtVector &stmts) |
Replaces stmt with stmts in the CFG. More... | |
node_iterator | node_begin () const |
Returns an iterator to the first node in the CFG. More... | |
node_iterator | node_end () const |
Returns an iterator past the last node in the CFG. More... | |
static ShPtr< Statement > | getLastStmtInNode (ShPtr< Node > node) |
Returns the last statement in the given node. More... | |
A representation of a control-flow graph (CFG).
See http://en.wikipedia.org/wiki/Control_flow_graph.
Empty statements are never present in a CFG.
Use a subclass of CFGBuilder to create instances of this class. Whenever the underlying backend IR (= code of the function) is changed, like a statement is removed, the CFG is invalidated and has to be re-built.
Instances of this class have reference object semantics.
This class is not meant to be subclassed.
using retdec::llvmir2hll::CFG::edge_iterator = EdgeVector::const_iterator |
Edges iterator.
using retdec::llvmir2hll::CFG::EdgeVector = std::vector<ShPtr<Edge> > |
Vector of edges.
using retdec::llvmir2hll::CFG::node_iterator = NodeVector::const_iterator |
Nodes iterator.
using retdec::llvmir2hll::CFG::NodeVector = std::vector<ShPtr<Node> > |
Vector of nodes.
using retdec::llvmir2hll::CFG::pred_iterator = EdgeVector::const_iterator |
Predecessors iterator.
using retdec::llvmir2hll::CFG::stmt_iterator = StmtVector::const_iterator |
Statements iterator.
using retdec::llvmir2hll::CFG::stmt_reverse_iterator = StmtVector::const_reverse_iterator |
Statements reverse iterator.
using retdec::llvmir2hll::CFG::StmtInNode = std::pair<ShPtr<Node>, stmt_iterator> |
Statement in a node (first -> node, second -> position of the statement within the node).
|
private |
Mapping of a statement into its corresponding node.
using retdec::llvmir2hll::CFG::succ_iterator = EdgeVector::const_iterator |
Successors iterator.
ShPtr< CFG::Edge > retdec::llvmir2hll::CFG::addEdge | ( | ShPtr< Node > | src, |
ShPtr< Node > | dst, | ||
ShPtr< Expression > | label = nullptr |
||
) |
Adds a new edge to the CFG.
[in] | src | Source node. |
[in] | dst | Destination node. |
[in] | label | Optional edge label. |
This function properly updates src->succs
and preds->dst
.
Adds the given entry node to the CFG.
Adds the given entry node to the CFG.
CFG::edge_iterator retdec::llvmir2hll::CFG::edge_begin | ( | ) | const |
Returns an iterator to the first edge in the CFG.
CFG::edge_iterator retdec::llvmir2hll::CFG::edge_end | ( | ) | const |
Returns an iterator past the last edge in the CFG.
Returns the entry node of the CFG.
Returns the last statement in the given node.
CFG::StmtInNode retdec::llvmir2hll::CFG::getNodeForStmt | ( | ShPtr< Statement > | stmt | ) | const |
std::size_t retdec::llvmir2hll::CFG::getNumberOfNodes | ( | ) | const |
Returns the number of nodes in the CFG.
Entry and exit nodes are also included.
CFG::stmt_reverse_iterator retdec::llvmir2hll::CFG::getReverseIteratorFromIterator | ( | stmt_iterator | i | ) |
Returns a reverse iterator for the given iterator i.
CFG::NodeVector retdec::llvmir2hll::CFG::getUnreachableNodes | ( | ) | const |
Returns unreachable nodes.
An unreachable node is a node that cannot be reached by traversing the graph from the entry node by following the direction of edges.
For example, in the CFG below
the unreachable nodes are E
, F
, and G
.
In some cases, the exit node can be unreachable as well. For example, this may happen for a CFG of the following function:
Returns true
if the given statement exists in the CFG, false
otherwise.
CFG::node_iterator retdec::llvmir2hll::CFG::node_begin | ( | ) | const |
Returns an iterator to the first node in the CFG.
CFG::node_iterator retdec::llvmir2hll::CFG::node_end | ( | ) | const |
Returns an iterator past the last node in the CFG.
Removes the selected edge from the CFG.
If the selected edge doesn't exist, this function does nothing.
void retdec::llvmir2hll::CFG::removeEmptyNodes | ( | ) |
Removes nodes with no statements from the CFG.
Let A
, B
, and be
three nodes, where A and are
non-empty and B is empty, and let them be connected in the following way:
Then, this function optimizes this structure into
Removes the selected node from the CFG.
The following actions are done:
If the node doesn't exist, this function does nothing.
This function may invalidate the existing node iterators.
void retdec::llvmir2hll::CFG::removeStmtFromNode | ( | ShPtr< Statement > | stmt, |
ShPtr< CFG::Node > | node | ||
) |
Removes the given statement from the given node.
If there either is no such node or stmt is not in the node, this function does nothing.
void retdec::llvmir2hll::CFG::removeUnreachableNodes | ( | ) |
Removes unreachable nodes.
void retdec::llvmir2hll::CFG::replaceStmt | ( | ShPtr< Statement > | stmt, |
const StmtVector & | stmts | ||
) |
Splits the given node into several nodes, each containing a single statement.
Nodes for the empty statement are not created.
void retdec::llvmir2hll::CFG::splitNodes | ( | ) |
Splits the CFG so that each node contains a single statement.
Nodes for the empty statement are not created.
Returns true
if the given statement exists in the CFG, false
otherwise.
|
private |
Asserts out if there is a non-empty statement without a node in the CFG.
|
private |
Asserts out if there is a node whose predecessor/successor is not in nodes
.
|
private |
Asserts out if there is an outgoing edge from A
to B
but no ingoing edge from B
to A
or vice versa in the CFG.
|
private |
Asserts out if there is an empty node in the CFG.
Only nodes different from the entry and exit nodes are checked.
|
friend |
|
friend |
|
private |
Vector of edges.
|
private |
Vector of nodes.
|
private |
Mapping between a statement and a node in which the statement is.