retdec
Classes | Static Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
retdec::llvmir2hll::CallInfoObtainer::SCCComputer Class Reference

A computation of strongly connected components (SCCs) from a call graph. More...

Inheritance diagram for retdec::llvmir2hll::CallInfoObtainer::SCCComputer:
Inheritance graph
[legend]
Collaboration diagram for retdec::llvmir2hll::CallInfoObtainer::SCCComputer:
Collaboration graph
[legend]

Classes

struct  CalledFuncInfo
 Information about a CalledFunc from the SCC algorithm. More...
 

Static Public Member Functions

static FuncVectorSet computeSCCs (ShPtr< CG > cg)
 Computes and returns all strongly connected components (SCCs) in the given call graph. More...
 

Private Types

using CalledFuncStack = std::stack< ShPtr< CG::CalledFuncs > >
 Stack of CalledFuncs. More...
 
using CalledFuncInfoMap = std::map< ShPtr< CG::CalledFuncs >, CalledFuncInfo >
 Mapping of a CalledFunc into its information. More...
 

Private Member Functions

 SCCComputer (ShPtr< CG > cg)
 Constructs a computer. More...
 
void visit (ShPtr< CG::CalledFuncs > calledFunc, CalledFuncInfo &calledFuncInfo)
 Visits the given node in the call graph. More...
 
FuncVectorSet findSCCs ()
 Finds and returns all strongly connected components (SCCs) in the given call graph. More...
 
- Private Member Functions inherited from retdec::utils::NonCopyable
 NonCopyable (const NonCopyable &)=delete
 
NonCopyableoperator= (const NonCopyable &)=delete
 
 NonCopyable ()=default
 
 ~NonCopyable ()=default
 

Private Attributes

ShPtr< CGcg
 Call graph of the current module. More...
 
int index
 The 'index' variable from the SCC algorithm. More...
 
FuncVectorSet sccs
 The set of computed SCCs. More...
 
FuncSet currentSCC
 The currently computed SCC. More...
 
CalledFuncStack stack
 The 'stack' variable from the SCC algorithm. More...
 
CalledFuncInfoMap calledFuncInfoMap
 Information about every CalledFunc. More...
 

Detailed Description

A computation of strongly connected components (SCCs) from a call graph.

See http://en.wikipedia.org/wiki/Strongly_connected_component for a description of an SCC.

The used algorithm is the Tarjan's strongly connected components algorithm, see http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Instances of this class have reference object semantics.

Member Typedef Documentation

◆ CalledFuncInfoMap

Mapping of a CalledFunc into its information.

◆ CalledFuncStack

Stack of CalledFuncs.

Constructor & Destructor Documentation

◆ SCCComputer()

retdec::llvmir2hll::CallInfoObtainer::SCCComputer::SCCComputer ( ShPtr< CG cg)
private

Constructs a computer.

Parameters
[in]cgCall graph of the current module.
Preconditions
  • cg is non-null

Member Function Documentation

◆ computeSCCs()

CallInfoObtainer::FuncVectorSet retdec::llvmir2hll::CallInfoObtainer::SCCComputer::computeSCCs ( ShPtr< CG cg)
static

Computes and returns all strongly connected components (SCCs) in the given call graph.

Preconditions
  • cg is non-null

A single function is not considered to be an SCC unless it contains a call to itself (see the description of FuncInfoCompOrder).

◆ findSCCs()

CallInfoObtainer::FuncVectorSet retdec::llvmir2hll::CallInfoObtainer::SCCComputer::findSCCs ( )
private

Finds and returns all strongly connected components (SCCs) in the given call graph.

A single function is not considered to be an SCC unless it contains a call to itself (see the description of FuncInfoCompOrder).

◆ visit()

void retdec::llvmir2hll::CallInfoObtainer::SCCComputer::visit ( ShPtr< CG::CalledFuncs calledFunc,
CalledFuncInfo calledFuncInfo 
)
private

Visits the given node in the call graph.

Parameters
[in]calledFuncThe given node.
[in,out]calledFuncInfoInformation about calledFunc.

Corresponds to the strongconnect(v) function from http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Member Data Documentation

◆ calledFuncInfoMap

CalledFuncInfoMap retdec::llvmir2hll::CallInfoObtainer::SCCComputer::calledFuncInfoMap
private

Information about every CalledFunc.

◆ cg

ShPtr<CG> retdec::llvmir2hll::CallInfoObtainer::SCCComputer::cg
private

Call graph of the current module.

◆ currentSCC

FuncSet retdec::llvmir2hll::CallInfoObtainer::SCCComputer::currentSCC
private

The currently computed SCC.

◆ index

int retdec::llvmir2hll::CallInfoObtainer::SCCComputer::index
private

The 'index' variable from the SCC algorithm.

◆ sccs

FuncVectorSet retdec::llvmir2hll::CallInfoObtainer::SCCComputer::sccs
private

The set of computed SCCs.

◆ stack

CalledFuncStack retdec::llvmir2hll::CallInfoObtainer::SCCComputer::stack
private

The 'stack' variable from the SCC algorithm.


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