retdec
Protected Member Functions | Protected Attributes | Private Member Functions | List of all members
retdec::llvmir2hll::CFGTraversal Class Referenceabstract

A base class of all CFG traversals. More...

#include <cfg_traversal.h>

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

Protected Member Functions

 CFGTraversal (ShPtr< CFG > cfg, bool defaultCurrRetVal)
 Constructs a new traverser. More...
 
 ~CFGTraversal ()=default
 
bool getCurrRetVal () const
 Returns the value that should be returned as the result of visiting a statement. More...
 
bool performTraversal (ShPtr< Statement > startStmt)
 Performs a traversal of the current CFG, starting at startStmt. More...
 
bool performTraversalFromSuccessors (ShPtr< Statement > stmt)
 Performs a traversal of the current CFG, starting at the successor(s) of stmt. More...
 
bool performReverseTraversal (ShPtr< Statement > startStmt)
 Performs a reverse traversal of the current CFG, starting at startStmt. More...
 
bool performReverseTraversalFromPredecessors (ShPtr< Statement > stmt)
 Performs a reverse traversal of the current CFG, starting at the predecessor(s) of stmt. More...
 
virtual bool visitStmt (ShPtr< Statement > stmt)=0
 Visits the given statement stmt. More...
 
virtual bool getEndRetVal () const =0
 Returns the value that should be returned when an end of the traversal is reached. More...
 
virtual bool combineRetVals (bool origRetVal, bool newRetVal) const =0
 Computes a new return value from the original return value (origRetVal) and the new return value (newRetVal). More...
 

Protected Attributes

ShPtr< CFGcfg
 CFG that is being traversed. More...
 
StmtUSet checkedStmts
 Statements that have been checked (to prevent looping). More...
 
bool currRetVal
 Current return value of visitStmt(). More...
 
bool stopTraversal
 Should the traversal be stopped? More...
 

Private Member Functions

bool performTraversalImpl (ShPtr< CFG::Node > startNode, CFG::stmt_iterator startStmtIter)
 A non-recursive implementation of performTraversal(). More...
 
std::pair< bool, bool > visitSingleNode (CFG::stmt_iterator startStmtIter, CFG::stmt_iterator endStmtIter)
 Visit a single node during our traversal, and all the statements in it. More...
 
bool performReverseTraversalImpl (ShPtr< CFG::Node > startNode, CFG::stmt_reverse_iterator startStmtRIter)
 A non-recursive implementation of performReverseTraversal(). More...
 
bool traverseNodePredecessors (ShPtr< CFG::Node > node)
 Traverses all the predecessors of node. More...
 
- Private Member Functions inherited from retdec::utils::NonCopyable
 NonCopyable (const NonCopyable &)=delete
 
NonCopyableoperator= (const NonCopyable &)=delete
 
 NonCopyable ()=default
 
 ~NonCopyable ()=default
 

Detailed Description

A base class of all CFG traversals.

A concrete CFG traverser has to implement all purely abstract member functions.

This class is based on the "Template method" design pattern.

Instances of this class have reference object semantics.

Constructor & Destructor Documentation

◆ CFGTraversal()

retdec::llvmir2hll::CFGTraversal::CFGTraversal ( ShPtr< CFG cfg,
bool  defaultCurrRetVal 
)
protected

Constructs a new traverser.

Parameters
[in]cfgCFG that should be traversed.
[in]defaultCurrRetValDefault value of currRetVal.
Preconditions
  • cfg is non-null

◆ ~CFGTraversal()

retdec::llvmir2hll::CFGTraversal::~CFGTraversal ( )
protecteddefault

Member Function Documentation

◆ combineRetVals()

virtual bool retdec::llvmir2hll::CFGTraversal::combineRetVals ( bool  origRetVal,
bool  newRetVal 
) const
protectedpure virtual

◆ getCurrRetVal()

bool retdec::llvmir2hll::CFGTraversal::getCurrRetVal ( ) const
protected

Returns the value that should be returned as the result of visiting a statement.

This function can be called only after calling visitStmt().

◆ getEndRetVal()

virtual bool retdec::llvmir2hll::CFGTraversal::getEndRetVal ( ) const
protectedpure virtual

Returns the value that should be returned when an end of the traversal is reached.

For example, the end may mean the end node of the CFG or a statement that has already been traversed.

Implemented in retdec::llvmir2hll::VarUseCFGTraversal, retdec::llvmir2hll::VarDefCFGTraversal, retdec::llvmir2hll::OptimFuncInfoCFGTraversal, retdec::llvmir2hll::NodesOfVarUseCFGTraversal, retdec::llvmir2hll::NoVarDefCFGTraversal, retdec::llvmir2hll::ModifiedBeforeReadCFGTraversal, and retdec::llvmir2hll::LhsRhsUsesCFGTraversal.

◆ performReverseTraversal()

bool retdec::llvmir2hll::CFGTraversal::performReverseTraversal ( ShPtr< Statement startStmt)
protected

Performs a reverse traversal of the current CFG, starting at startStmt.

Returns
Result of the traversal (its meaning may vary from subclass to subclass).
Preconditions
  • startStmt is non-null and it is not an empty statement (recall that a CFG doesn't contain empty statements)

◆ performReverseTraversalFromPredecessors()

bool retdec::llvmir2hll::CFGTraversal::performReverseTraversalFromPredecessors ( ShPtr< Statement stmt)
protected

Performs a reverse traversal of the current CFG, starting at the predecessor(s) of stmt.

Returns
Result of the traversal (its meaning may vary from subclass to subclass).
Preconditions
  • startStmt is non-null and it is not an empty statement (recall that a CFG doesn't contain empty statements)

◆ performReverseTraversalImpl()

bool retdec::llvmir2hll::CFGTraversal::performReverseTraversalImpl ( ShPtr< CFG::Node node,
CFG::stmt_reverse_iterator  stmtRIter 
)
private

A non-recursive implementation of performReverseTraversal().

Parameters
[in]nodeNode to be traversed.
[in]stmtRIterReverse iterator to a statement in node to be checked.

If stmtIter equals node->stmt_rend(), the function traverses all predecessors of node.

◆ performTraversal()

bool retdec::llvmir2hll::CFGTraversal::performTraversal ( ShPtr< Statement startStmt)
protected

Performs a traversal of the current CFG, starting at startStmt.

Returns
Result of the traversal (its meaning may vary from subclass to subclass).
Preconditions
  • startStmt is non-null and it is not an empty statement (recall that a CFG doesn't contain empty statements)

◆ performTraversalFromSuccessors()

bool retdec::llvmir2hll::CFGTraversal::performTraversalFromSuccessors ( ShPtr< Statement stmt)
protected

Performs a traversal of the current CFG, starting at the successor(s) of stmt.

Returns
Result of the traversal (its meaning may vary from subclass to subclass).
Preconditions
  • startStmt is non-null and it is not an empty statement (recall that a CFG doesn't contain empty statements)

◆ performTraversalImpl()

bool retdec::llvmir2hll::CFGTraversal::performTraversalImpl ( ShPtr< CFG::Node node,
CFG::stmt_iterator  stmtIter 
)
private

A non-recursive implementation of performTraversal().

Parameters
[in]nodeNode to be traversed.
[in]stmtIterIterator to a statement in node to be checked.

This function traverses the entire CFG rooted at node, starting with the statement in stmtIter.

◆ traverseNodePredecessors()

bool retdec::llvmir2hll::CFGTraversal::traverseNodePredecessors ( ShPtr< CFG::Node node)
private

Traverses all the predecessors of node.

Returns
Result of the traversal, just like performReverseTraversal().

This function is meant to be called within functions traversing a CFG in reverse.

◆ visitSingleNode()

std::pair< bool, bool > retdec::llvmir2hll::CFGTraversal::visitSingleNode ( CFG::stmt_iterator  stmtIter,
CFG::stmt_iterator  endStmt 
)
private

Visit a single node during our traversal, and all the statements in it.

Parameters
[in]stmtIterIterator to a statement in node to be checked.
[in]endStmtIterator to last statement in node to be checked.
Returns
Result of the visit, and whether to skip children of the node.

◆ visitStmt()

virtual bool retdec::llvmir2hll::CFGTraversal::visitStmt ( ShPtr< Statement stmt)
protectedpure virtual

Visits the given statement stmt.

return true if the traversing should continue, false otherwise.

Note: checkedStmts is modified in CFGTraversal, so it is not necessary for the implementation of this function to add stmt to checkedStmts.

If you want the traversal to end prematurely, set the stopTraversal variable to true. Otherwise, if you just return false, the traversal may still continue from other branches because of recursion.

Implemented in retdec::llvmir2hll::VarUseCFGTraversal, retdec::llvmir2hll::VarDefCFGTraversal, retdec::llvmir2hll::OptimFuncInfoCFGTraversal, retdec::llvmir2hll::NodesOfVarUseCFGTraversal, retdec::llvmir2hll::NoVarDefCFGTraversal, retdec::llvmir2hll::ModifiedBeforeReadCFGTraversal, and retdec::llvmir2hll::LhsRhsUsesCFGTraversal.

Member Data Documentation

◆ cfg

ShPtr<CFG> retdec::llvmir2hll::CFGTraversal::cfg
protected

CFG that is being traversed.

◆ checkedStmts

StmtUSet retdec::llvmir2hll::CFGTraversal::checkedStmts
protected

Statements that have been checked (to prevent looping).

◆ currRetVal

bool retdec::llvmir2hll::CFGTraversal::currRetVal
protected

Current return value of visitStmt().

◆ stopTraversal

bool retdec::llvmir2hll::CFGTraversal::stopTraversal
protected

Should the traversal be stopped?


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