retdec
Classes | Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Friends | List of all members
retdec::llvmir2hll::CFG Class Referencefinal

A representation of a control-flow graph (CFG). More...

#include <cfg.h>

Inheritance diagram for retdec::llvmir2hll::CFG:
Inheritance graph
[legend]
Collaboration diagram for retdec::llvmir2hll::CFG:
Collaboration graph
[legend]

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< FunctiongetCorrespondingFunction () const
 Returns the function which corresponds to the CFG. More...
 
Edges Accessors
ShPtr< EdgeaddEdge (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< NodeaddNode (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...
 
- Private Member Functions inherited from retdec::utils::NonCopyable
 NonCopyable (const NonCopyable &)=delete
 
NonCopyableoperator= (const NonCopyable &)=delete
 
 NonCopyable ()=default
 
 ~NonCopyable ()=default
 

Private Attributes

ShPtr< FunctioncorrespondingFunction
 Function to which this CFG corresponds. More...
 
NodeVector nodes
 Vector of nodes. More...
 
EdgeVector edges
 Vector of edges. More...
 
ShPtr< NodeentryNode
 Entry node. More...
 
ShPtr< NodeexitNode
 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< NodegetEntryNode () const
 Returns the entry node of the CFG. More...
 
ShPtr< NodegetExitNode () 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< StatementgetLastStmtInNode (ShPtr< Node > node)
 Returns the last statement in the given node. More...
 

Detailed Description

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.

Member Typedef Documentation

◆ edge_iterator

using retdec::llvmir2hll::CFG::edge_iterator = EdgeVector::const_iterator

Edges iterator.

◆ EdgeVector

Vector of edges.

◆ node_iterator

using retdec::llvmir2hll::CFG::node_iterator = NodeVector::const_iterator

Nodes iterator.

◆ NodeVector

Vector of nodes.

◆ pred_iterator

using retdec::llvmir2hll::CFG::pred_iterator = EdgeVector::const_iterator

Predecessors iterator.

◆ stmt_iterator

using retdec::llvmir2hll::CFG::stmt_iterator = StmtVector::const_iterator

Statements iterator.

◆ stmt_reverse_iterator

using retdec::llvmir2hll::CFG::stmt_reverse_iterator = StmtVector::const_reverse_iterator

Statements reverse iterator.

◆ StmtInNode

Statement in a node (first -> node, second -> position of the statement within the node).

◆ StmtNodeMapping

using retdec::llvmir2hll::CFG::StmtNodeMapping = std::unordered_map<ShPtr<Statement>, ShPtr<Node> >
private

Mapping of a statement into its corresponding node.

◆ succ_iterator

using retdec::llvmir2hll::CFG::succ_iterator = EdgeVector::const_iterator

Successors iterator.

Constructor & Destructor Documentation

◆ CFG()

retdec::llvmir2hll::CFG::CFG ( ShPtr< Function func)

Constructs a new CFG.

Parameters
[in]funcThe CFG will correspond to this function.

Member Function Documentation

◆ addEdge()

ShPtr< CFG::Edge > retdec::llvmir2hll::CFG::addEdge ( ShPtr< Node src,
ShPtr< Node dst,
ShPtr< Expression label = nullptr 
)

Adds a new edge to the CFG.

Parameters
[in]srcSource node.
[in]dstDestination node.
[in]labelOptional edge label.
Returns
The added edge.

This function properly updates src->succs and preds->dst.

Preconditions
  • src and dst are non-null

◆ addEntryNode()

void retdec::llvmir2hll::CFG::addEntryNode ( ShPtr< Node node)

Adds the given entry node to the CFG.

Preconditions
  • node is non-null

◆ addExitNode()

void retdec::llvmir2hll::CFG::addExitNode ( ShPtr< Node node)

Adds the given entry node to the CFG.

Preconditions
  • node is non-null

◆ addNode() [1/2]

ShPtr< CFG::Node > retdec::llvmir2hll::CFG::addNode ( const std::string &  label = "")
private

Adds a new node to the CFG.

Parameters
[in]labelOptional label of the node.
Returns
The added node.

◆ addNode() [2/2]

void retdec::llvmir2hll::CFG::addNode ( ShPtr< Node node)

Adds the given node to the CFG.

◆ edge_begin()

CFG::edge_iterator retdec::llvmir2hll::CFG::edge_begin ( ) const

Returns an iterator to the first edge in the CFG.

◆ edge_end()

CFG::edge_iterator retdec::llvmir2hll::CFG::edge_end ( ) const

Returns an iterator past the last edge in the CFG.

◆ getCorrespondingFunction()

ShPtr< Function > retdec::llvmir2hll::CFG::getCorrespondingFunction ( ) const

Returns the function which corresponds to the CFG.

In other words, it returns the function from which this CFG was created.

◆ getEntryNode()

ShPtr< CFG::Node > retdec::llvmir2hll::CFG::getEntryNode ( ) const

Returns the entry node of the CFG.

◆ getExitNode()

ShPtr< CFG::Node > retdec::llvmir2hll::CFG::getExitNode ( ) const

Returns the exit node of the CFG.

◆ getLastStmtInNode()

ShPtr< Statement > retdec::llvmir2hll::CFG::getLastStmtInNode ( ShPtr< Node node)
static

Returns the last statement in the given node.

◆ getNodeForStmt()

CFG::StmtInNode retdec::llvmir2hll::CFG::getNodeForStmt ( ShPtr< Statement stmt) const

Returns the node and position of the given statement in the CFG.

If stmt doesn't exist in the CFG, the first component of the returned pair is the null pointer. The second component is then (obviously) invalid.

Preconditions
  • stmt is non-null

◆ getNumberOfNodes()

std::size_t retdec::llvmir2hll::CFG::getNumberOfNodes ( ) const

Returns the number of nodes in the CFG.

Entry and exit nodes are also included.

◆ getReverseIteratorFromIterator()

CFG::stmt_reverse_iterator retdec::llvmir2hll::CFG::getReverseIteratorFromIterator ( stmt_iterator  i)

Returns a reverse iterator for the given iterator i.

Preconditions
  • i can be accessed, i.e. it is not a past-end iterator

◆ getUnreachableNodes()

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

Entry
/ | \
A B C F-+
| | |
D E G-+
\
Exit

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:

void func() {
while (true) {}
}

◆ hasNodeForStmt()

bool retdec::llvmir2hll::CFG::hasNodeForStmt ( ShPtr< Statement stmt) const

Returns true if the given statement exists in the CFG, false otherwise.

Preconditions
  • stmt is non-null

◆ node_begin()

CFG::node_iterator retdec::llvmir2hll::CFG::node_begin ( ) const

Returns an iterator to the first node in the CFG.

◆ node_end()

CFG::node_iterator retdec::llvmir2hll::CFG::node_end ( ) const

Returns an iterator past the last node in the CFG.

◆ removeEdge()

void retdec::llvmir2hll::CFG::removeEdge ( ShPtr< Edge edge)

Removes the selected edge from the CFG.

If the selected edge doesn't exist, this function does nothing.

Preconditions
  • edge is non-null

◆ removeEmptyNodes()

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:

A --> B --> C

Then, this function optimizes this structure into

A --> C

◆ removeNode()

void retdec::llvmir2hll::CFG::removeNode ( ShPtr< Node node)

Removes the selected node from the CFG.

The following actions are done:

  • If the node has a single successor, all ingoing edges into the node are redirected to this successor. Otherwise, all ingoing edges are removed.
  • All outgoing edges from the node are removed.
  • The node is removed from the CFG.

If the node doesn't exist, this function does nothing.

This function may invalidate the existing node iterators.

Preconditions
  • node is non-null
  • node is not the entry or the exit node

◆ removeStmt()

void retdec::llvmir2hll::CFG::removeStmt ( ShPtr< Statement stmt)

Removes stmt from the CFG.

Parameters
[in]stmtStatement to be removed.

If stmt doesn't exist in the CFG, this function does nothing.

Preconditions
  • stmt is non-null

◆ removeStmtFromNode()

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.

Preconditions
  • both stmt and node are non-null

◆ removeUnreachableNodes()

void retdec::llvmir2hll::CFG::removeUnreachableNodes ( )

Removes unreachable nodes.

◆ replaceStmt()

void retdec::llvmir2hll::CFG::replaceStmt ( ShPtr< Statement stmt,
const StmtVector stmts 
)

Replaces stmt with stmts in the CFG.

Parameters
[in]stmtStatement to be replaced.
[in]stmtsStatements that will replace stmt.

If stmt doesn't exist in the CFG, this function does nothing.

Preconditions
  • stmt are non-null

◆ splitNode()

void retdec::llvmir2hll::CFG::splitNode ( ShPtr< Node node)
private

Splits the given node into several nodes, each containing a single statement.

Nodes for the empty statement are not created.

◆ splitNodes()

void retdec::llvmir2hll::CFG::splitNodes ( )

Splits the CFG so that each node contains a single statement.

Nodes for the empty statement are not created.

◆ stmtExistsInCFG()

bool retdec::llvmir2hll::CFG::stmtExistsInCFG ( ShPtr< Statement stmt) const

Returns true if the given statement exists in the CFG, false otherwise.

Preconditions
  • stmt is non-null

◆ validateEveryNonEmptyStatementHasNode()

void retdec::llvmir2hll::CFG::validateEveryNonEmptyStatementHasNode ( )
private

Asserts out if there is a non-empty statement without a node in the CFG.

◆ validateEveryPredAndSuccIsInNodes()

void retdec::llvmir2hll::CFG::validateEveryPredAndSuccIsInNodes ( )
private

Asserts out if there is a node whose predecessor/successor is not in nodes.

◆ validateIngoingAndOutgoingEdges()

void retdec::llvmir2hll::CFG::validateIngoingAndOutgoingEdges ( )
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.

◆ validateThereAreNoEmptyNodes()

void retdec::llvmir2hll::CFG::validateThereAreNoEmptyNodes ( )
private

Asserts out if there is an empty node in the CFG.

Only nodes different from the entry and exit nodes are checked.

Friends And Related Function Documentation

◆ NonRecursiveCFGBuilder

friend class NonRecursiveCFGBuilder
friend

◆ RecursiveCFGBuilder

friend class RecursiveCFGBuilder
friend

Member Data Documentation

◆ correspondingFunction

ShPtr<Function> retdec::llvmir2hll::CFG::correspondingFunction
private

Function to which this CFG corresponds.

◆ edges

EdgeVector retdec::llvmir2hll::CFG::edges
private

Vector of edges.

◆ entryNode

ShPtr<Node> retdec::llvmir2hll::CFG::entryNode
private

Entry node.

◆ exitNode

ShPtr<Node> retdec::llvmir2hll::CFG::exitNode
private

Exit node.

◆ nodes

NodeVector retdec::llvmir2hll::CFG::nodes
private

Vector of nodes.

◆ stmtNodeMapping

StmtNodeMapping retdec::llvmir2hll::CFG::stmtNodeMapping
private

Mapping between a statement and a node in which the statement is.


The documentation for this class was generated from the following files: