retdec
|
A non-recursive creator of control-flow graphs (CFGs) from functions. More...
#include <non_recursive_cfg_builder.h>
Classes | |
struct | EdgeToAdd |
Structure for edges that will be added to CFG. More... | |
struct | Job |
Structure for jobs that have to be performed. More... | |
Public Member Functions | |
virtual void | buildCFG () override |
Builds cfg . More... | |
![]() | |
ShPtr< CFG > | getCFG (ShPtr< Function > func) |
Returns a CFG of the given function func. More... | |
Static Public Member Functions | |
static ShPtr< NonRecursiveCFGBuilder > | create () |
Creates and returns a new NonRecursiveCFGBuilder. More... | |
Private Types | |
using | JobQueue = std::queue< Job > |
Queue of jobs. More... | |
using | EdgesToAdd = std::vector< EdgeToAdd > |
Vector of edges. More... | |
using | StmtNodeMapping = std::unordered_map< ShPtr< Statement >, ShPtr< CFG::Node > > |
Mapping of a statement into its corresponding node. More... | |
Private Member Functions | |
NonRecursiveCFGBuilder () | |
Constructs a new builder. More... | |
void | addEdgeFromCurrNodeToSuccNode (ShPtr< Statement > stmt, EdgesToAdd &edgesToAdd, ShPtr< Expression > edgeCond=nullptr) |
Finds successor and add edges to edgesToAdd for stmt. More... | |
void | addEdgeFromVector (const EdgeToAdd &edge) |
Add edge to CFG. More... | |
void | addJobToQueue (ShPtr< CFG::Node > pred, ShPtr< Expression > cond, ShPtr< Statement > stmt) |
Creates new job and add new job to queue of jobs. More... | |
void | addEdgesFromVector (const EdgesToAdd &edgesToAdd) |
Adds edges from edgesToAdd. More... | |
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 edge from the current node to the successor/parent of stmt. More... | |
void | addStmtToNodeAndToMapOfStmtToNode (ShPtr< Statement > stmt) |
Adds stmt to currNode and to stmtNodeMapping . More... | |
void | resolveGotoTargets (ShPtr< Statement > stmt) |
Resolve goto targets. More... | |
void | createAndAddNode () |
Creates new node and set it to current node. More... | |
void | createEdgesToBeAdded () |
Creates connecting edges for all nodes. More... | |
void | createEntryNode () |
Creates entry node. More... | |
void | createExitNode () |
Creates exit node. More... | |
void | createNewNodeAndConnectWithPredNode (ShPtr< Statement > stmt) |
Creates new node and add it. Also save edge from this new node to previous node. More... | |
void | createNewNodeForIfSwitchForWhileStmtAndAddStmtToNode (ShPtr< Statement > stmt) |
Creates new node if is needed for if, while, for, switch statements and also add statement to node. More... | |
void | createNewNodeIfStmtHasSucc (ShPtr< Statement > stmt) |
Creates a new node for stmt if it has a successor. More... | |
void | createOtherNodes () |
Creates other nodes. More... | |
void | doJob (const Job &job) |
Performs the given job. More... | |
void | doJobs () |
Tops and pop one job from queue and starts doing of job. More... | |
void | initializeCFGBuild () |
Initializes all the needed data so the CFG can be built. More... | |
void | purgeCFG () |
Purges the CFG by removing useless nodes. More... | |
void | validateCFG () |
Validates the created CFG. More... | |
void | visitForOrUForLoop (ShPtr< Statement > loop, ShPtr< Statement > body) |
Implementation of visit() for for loops. More... | |
Visitor Interface | |
virtual void | visit (ShPtr< AssignStmt > stmt) override |
virtual void | visit (ShPtr< BreakStmt > stmt) override |
virtual void | visit (ShPtr< CallStmt > stmt) override |
virtual void | visit (ShPtr< ContinueStmt > stmt) override |
virtual void | visit (ShPtr< EmptyStmt > stmt) override |
virtual void | visit (ShPtr< ForLoopStmt > stmt) override |
virtual void | visit (ShPtr< UForLoopStmt > stmt) override |
virtual void | visit (ShPtr< GotoStmt > stmt) override |
virtual void | visit (ShPtr< IfStmt > stmt) override |
virtual void | visit (ShPtr< ReturnStmt > stmt) override |
virtual void | visit (ShPtr< SwitchStmt > stmt) override |
virtual void | visit (ShPtr< UnreachableStmt > stmt) override |
virtual void | visit (ShPtr< VarDefStmt > stmt) override |
virtual void | visit (ShPtr< WhileLoopStmt > stmt) override |
virtual void | visit (ShPtr< GlobalVarDef > varDef) override |
virtual void | visit (ShPtr< Function > func) override |
virtual void | visit (ShPtr< AssignStmt > stmt) override |
virtual void | visit (ShPtr< BreakStmt > stmt) override |
virtual void | visit (ShPtr< CallStmt > stmt) override |
virtual void | visit (ShPtr< ContinueStmt > stmt) override |
virtual void | visit (ShPtr< EmptyStmt > stmt) override |
virtual void | visit (ShPtr< ForLoopStmt > stmt) override |
virtual void | visit (ShPtr< UForLoopStmt > stmt) override |
virtual void | visit (ShPtr< GotoStmt > stmt) override |
virtual void | visit (ShPtr< IfStmt > stmt) override |
virtual void | visit (ShPtr< ReturnStmt > stmt) override |
virtual void | visit (ShPtr< SwitchStmt > stmt) override |
virtual void | visit (ShPtr< UnreachableStmt > stmt) override |
virtual void | visit (ShPtr< VarDefStmt > stmt) override |
virtual void | visit (ShPtr< WhileLoopStmt > stmt) override |
virtual void | visit (ShPtr< AddOpExpr > expr) override |
virtual void | visit (ShPtr< AddressOpExpr > expr) override |
virtual void | visit (ShPtr< AssignOpExpr > expr) override |
virtual void | visit (ShPtr< AndOpExpr > expr) override |
virtual void | visit (ShPtr< ArrayIndexOpExpr > expr) override |
virtual void | visit (ShPtr< BitAndOpExpr > expr) override |
virtual void | visit (ShPtr< BitOrOpExpr > expr) override |
virtual void | visit (ShPtr< BitShlOpExpr > expr) override |
virtual void | visit (ShPtr< BitShrOpExpr > expr) override |
virtual void | visit (ShPtr< BitXorOpExpr > expr) override |
virtual void | visit (ShPtr< CallExpr > expr) override |
virtual void | visit (ShPtr< CommaOpExpr > expr) override |
virtual void | visit (ShPtr< DerefOpExpr > expr) override |
virtual void | visit (ShPtr< DivOpExpr > expr) override |
virtual void | visit (ShPtr< EqOpExpr > expr) override |
virtual void | visit (ShPtr< GtEqOpExpr > expr) override |
virtual void | visit (ShPtr< GtOpExpr > expr) override |
virtual void | visit (ShPtr< LtEqOpExpr > expr) override |
virtual void | visit (ShPtr< LtOpExpr > expr) override |
virtual void | visit (ShPtr< ModOpExpr > expr) override |
virtual void | visit (ShPtr< MulOpExpr > expr) override |
virtual void | visit (ShPtr< NegOpExpr > expr) override |
virtual void | visit (ShPtr< NeqOpExpr > expr) override |
virtual void | visit (ShPtr< NotOpExpr > expr) override |
virtual void | visit (ShPtr< OrOpExpr > expr) override |
virtual void | visit (ShPtr< StructIndexOpExpr > expr) override |
virtual void | visit (ShPtr< SubOpExpr > expr) override |
virtual void | visit (ShPtr< TernaryOpExpr > expr) override |
virtual void | visit (ShPtr< Variable > var) override |
virtual void | visit (ShPtr< BitCastExpr > expr) override |
virtual void | visit (ShPtr< ExtCastExpr > expr) override |
virtual void | visit (ShPtr< FPToIntCastExpr > expr) override |
virtual void | visit (ShPtr< IntToFPCastExpr > expr) override |
virtual void | visit (ShPtr< IntToPtrCastExpr > expr) override |
virtual void | visit (ShPtr< PtrToIntCastExpr > expr) override |
virtual void | visit (ShPtr< TruncCastExpr > expr) override |
virtual void | visit (ShPtr< ConstArray > constant) override |
virtual void | visit (ShPtr< ConstBool > constant) override |
virtual void | visit (ShPtr< ConstFloat > constant) override |
virtual void | visit (ShPtr< ConstInt > constant) override |
virtual void | visit (ShPtr< ConstNullPointer > constant) override |
virtual void | visit (ShPtr< ConstString > constant) override |
virtual void | visit (ShPtr< ConstStruct > constant) override |
virtual void | visit (ShPtr< ConstSymbol > constant) override |
virtual void | visit (ShPtr< ArrayType > type) override |
virtual void | visit (ShPtr< FloatType > type) override |
virtual void | visit (ShPtr< IntType > type) override |
virtual void | visit (ShPtr< PointerType > type) override |
virtual void | visit (ShPtr< StringType > type) override |
virtual void | visit (ShPtr< StructType > type) override |
virtual void | visit (ShPtr< FunctionType > type) override |
virtual void | visit (ShPtr< VoidType > type) override |
virtual void | visit (ShPtr< UnknownType > type) override |
![]() | |
virtual void | visit (ShPtr< GlobalVarDef > varDef) override |
virtual void | visit (ShPtr< Function > func) override |
virtual void | visit (ShPtr< AddOpExpr > expr) override |
virtual void | visit (ShPtr< AddressOpExpr > expr) override |
virtual void | visit (ShPtr< AssignOpExpr > expr) override |
virtual void | visit (ShPtr< AndOpExpr > expr) override |
virtual void | visit (ShPtr< ArrayIndexOpExpr > expr) override |
virtual void | visit (ShPtr< BitAndOpExpr > expr) override |
virtual void | visit (ShPtr< BitOrOpExpr > expr) override |
virtual void | visit (ShPtr< BitShlOpExpr > expr) override |
virtual void | visit (ShPtr< BitShrOpExpr > expr) override |
virtual void | visit (ShPtr< BitXorOpExpr > expr) override |
virtual void | visit (ShPtr< CallExpr > expr) override |
virtual void | visit (ShPtr< CommaOpExpr > expr) override |
virtual void | visit (ShPtr< DerefOpExpr > expr) override |
virtual void | visit (ShPtr< DivOpExpr > expr) override |
virtual void | visit (ShPtr< EqOpExpr > expr) override |
virtual void | visit (ShPtr< GtEqOpExpr > expr) override |
virtual void | visit (ShPtr< GtOpExpr > expr) override |
virtual void | visit (ShPtr< LtEqOpExpr > expr) override |
virtual void | visit (ShPtr< LtOpExpr > expr) override |
virtual void | visit (ShPtr< ModOpExpr > expr) override |
virtual void | visit (ShPtr< MulOpExpr > expr) override |
virtual void | visit (ShPtr< NegOpExpr > expr) override |
virtual void | visit (ShPtr< NeqOpExpr > expr) override |
virtual void | visit (ShPtr< NotOpExpr > expr) override |
virtual void | visit (ShPtr< OrOpExpr > expr) override |
virtual void | visit (ShPtr< StructIndexOpExpr > expr) override |
virtual void | visit (ShPtr< SubOpExpr > expr) override |
virtual void | visit (ShPtr< TernaryOpExpr > expr) override |
virtual void | visit (ShPtr< Variable > var) override |
virtual void | visit (ShPtr< BitCastExpr > expr) override |
virtual void | visit (ShPtr< ExtCastExpr > expr) override |
virtual void | visit (ShPtr< FPToIntCastExpr > expr) override |
virtual void | visit (ShPtr< IntToFPCastExpr > expr) override |
virtual void | visit (ShPtr< IntToPtrCastExpr > expr) override |
virtual void | visit (ShPtr< PtrToIntCastExpr > expr) override |
virtual void | visit (ShPtr< TruncCastExpr > expr) override |
virtual void | visit (ShPtr< ConstArray > constant) override |
virtual void | visit (ShPtr< ConstBool > constant) override |
virtual void | visit (ShPtr< ConstFloat > constant) override |
virtual void | visit (ShPtr< ConstInt > constant) override |
virtual void | visit (ShPtr< ConstNullPointer > constant) override |
virtual void | visit (ShPtr< ConstString > constant) override |
virtual void | visit (ShPtr< ConstStruct > constant) override |
virtual void | visit (ShPtr< ConstSymbol > constant) override |
virtual void | visit (ShPtr< ArrayType > type) override |
virtual void | visit (ShPtr< FloatType > type) override |
virtual void | visit (ShPtr< IntType > type) override |
virtual void | visit (ShPtr< PointerType > type) override |
virtual void | visit (ShPtr< StringType > type) override |
virtual void | visit (ShPtr< StructType > type) override |
virtual void | visit (ShPtr< FunctionType > type) override |
virtual void | visit (ShPtr< VoidType > type) override |
virtual void | visit (ShPtr< UnknownType > type) override |
![]() | |
virtual | ~Visitor ()=default |
Visitor ()=default | |
Private Attributes | |
JobQueue | jobQueue |
Queue of all jobs. More... | |
EdgesToAdd | edgesToAddFirst |
Vector of saved edges for nodes that will be added first. More... | |
EdgesToAdd | edgesToAddLast |
Vector of saved edges that have to be added at the end. More... | |
ShPtr< CFG::Node > | currNode |
Currently generated node. More... | |
StmtNodeMapping | emptyStmtToNodeMap |
Mapping of an empty statement to its node. More... | |
bool | stopIterNextStmts |
Signalizes if we want to iterate through statements or not. More... | |
Additional Inherited Members | |
![]() | |
CFGBuilder ()=default | |
![]() | |
ShPtr< CFG > | cfg |
A CFG that is currently being built. More... | |
ShPtr< Function > | func |
A function from which the CFG is being built. More... | |
A non-recursive creator of control-flow graphs (CFGs) from functions.
|
private |
Vector of edges.
|
private |
Queue of jobs.
|
private |
Mapping of a statement into its corresponding node.
|
private |
Constructs a new builder.
|
private |
Finds successor and add edges to edgesToAdd for stmt.
[in] | stmt | Finds successor for this statement. |
[out] | edgesToAdd | Place to save edge. |
[in] | edgeCond | Condition of edge. |
|
private |
Add edge to CFG.
[in] | edge | Edge to add. |
|
private |
Adds edges from edgesToAdd.
[in] | edgesToAdd | Edges to add. |
|
private |
Creates new job and add new job to queue of jobs.
[in] | pred | Predecessor of node where is a stmt. |
[in] | cond | Condition for the edge from node where is a stmt and pred node. |
[in] | stmt | First statement of new node. |
Adds a statement to the current node and to map of statements to node, and adds a forward or backward edge from the current node to the successor/parent of stmt.
[in] | stmt | Statement to add. |
|
private |
Adds stmt to currNode
and to stmtNodeMapping
.
[in] | stmt | Statement to add. |
|
overridevirtual |
Builds cfg
.
When this function is called, cfg
and func
are correctly initialized.
Implements retdec::llvmir2hll::CFGBuilder.
|
static |
Creates and returns a new NonRecursiveCFGBuilder.
|
private |
Creates new node and set it to current node.
|
private |
Creates connecting edges for all nodes.
This function add edges from two vectors of edges. It is needed because we want to have ordered edges like for example
We want to have first edge the true condition and second edge the false condition. The edgesToAddLast
contains edges that have to be last edges for its node.
|
private |
Creates entry node.
|
private |
Creates exit node.
|
private |
Creates new node and add it. Also save edge from this new node to previous node.
[in] | stmt | Statement of new node. |
|
private |
Creates new node if is needed for if, while, for, switch statements and also add statement to node.
[in] | stmt | Statement to add. |
|
private |
Creates a new node for stmt if it has a successor.
[in] | stmt | Statement to check if has a successor. |
|
private |
Creates other nodes.
|
private |
Performs the given job.
Iterates through one nested level from statement which is saved in job. Also create new node for job and add backward edge from this new node to predecessor node.
[in] | job | A job to perform. |
|
private |
Tops and pop one job from queue and starts doing of job.
|
private |
Initializes all the needed data so the CFG can be built.
|
private |
Purges the CFG by removing useless nodes.
|
private |
Resolve goto targets.
When the statement is a goto target and there are some statements in the current node, we have to add the statement into a new node. Otherwise do nothing.
[in] | stmt | Statement to check. |
|
private |
Validates the created CFG.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
inlineoverrideprivate |
|
overrideprivatevirtual |
Reimplemented from retdec::llvmir2hll::VisitorAdapter.
|
private |
Implementation of visit() for for loops.
Currently generated node.
|
private |
Vector of saved edges for nodes that will be added first.
|
private |
Vector of saved edges that have to be added at the end.
|
private |
Mapping of an empty statement to its node.
|
private |
Queue of all jobs.
|
private |
Signalizes if we want to iterate through statements or not.