SVF::CHGraph Class Reference

#include <CHG.h>

Inheritance diagram for SVF::CHGraph:

Public Types
enum	RELATIONTYPE { CONSTRUCTOR = 0x1 , DESTRUCTOR = 0x2 }
typedef Set< const CHNode * >	CHNodeSetTy
typedef FIFOWorkList< const CHNode * >	WorkList
typedef Map< std::string, CHNodeSetTy >	NameToCHNodesMap
typedef Map< const ICFGNode *, CHNodeSetTy >	CallNodeToCHNodesMap
typedef Map< const ICFGNode *, VTableSet >	CallNodeToVTableSetMap
typedef Map< const ICFGNode *, VFunSet >	CallNodeToVFunSetMap
Public Types inherited from SVF::CommonCHGraph
enum	CHGKind { Standard , DI }
Public Types inherited from SVF::GenericGraph< NodeTy, EdgeTy >
typedef NodeTy	NodeType
typedef EdgeTy	EdgeType
typedef OrderedMap< NodeID, NodeType * >	IDToNodeMapTy
	NodeID to GenericNode map. More...
typedef IDToNodeMapTy::iterator	iterator
	Node Iterators. More...
typedef IDToNodeMapTy::const_iterator	const_iterator

Public Member Functions
	CHGraph (SVFModule *svfModule)
	~CHGraph () override=default
void	addEdge (const std::string className, const std::string baseClassName, CHEdge::CHEDGETYPE edgeType)
CHNode *	getNode (const std::string name) const
void	getVFnsFromVtbls (const CallICFGNode *cs, const VTableSet &vtbls, VFunSet &virtualFunctions) override
void	dump (const std::string &filename)
void	view ()
void	printCH ()
u32_t	getVirtualFunctionID (const SVFFunction *vfn) const
const SVFFunction *	getVirtualFunctionBasedonID (u32_t id) const
void	addInstances (const std::string templateName, CHNode *node)
const CHNodeSetTy &	getDescendants (const std::string className)
const CHNodeSetTy &	getInstances (const std::string className)
bool	csHasVtblsBasedonCHA (const CallICFGNode *cs) override
bool	csHasVFnsBasedonCHA (const CallICFGNode *cs) override
const VTableSet &	getCSVtblsBasedonCHA (const CallICFGNode *cs) override
const VFunSet &	getCSVFsBasedonCHA (const CallICFGNode *cs) override
Public Member Functions inherited from SVF::CommonCHGraph
virtual	~CommonCHGraph ()
CHGKind	getKind (void) const
Public Member Functions inherited from SVF::GenericGraph< NodeTy, EdgeTy >
	GenericGraph ()
	Constructor. More...
virtual	~GenericGraph ()
	Destructor. More...
void	destroy ()
	Release memory. More...
iterator	begin ()
	Iterators. More...
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
void	addGNode (NodeID id, NodeType *node)
	Add a Node. More...
NodeType *	getGNode (NodeID id) const
	Get a node. More...
bool	hasGNode (NodeID id) const
	Has a node. More...
void	removeGNode (NodeType *node)
	Delete a node. More...
u32_t	getTotalNodeNum () const
	Get total number of node/edge. More...
u32_t	getTotalEdgeNum () const
void	incNodeNum ()
	Increase number of node/edge. More...
void	incEdgeNum ()

Static Public Member Functions
static bool	classof (const CommonCHGraph *chg)

Private Attributes
SVFModule *	svfMod
u32_t	classNum
u32_t	vfID
double	buildingCHGTime
Map< std::string, CHNode * >	classNameToNodeMap
NameToCHNodesMap	classNameToDescendantsMap
NameToCHNodesMap	classNameToAncestorsMap
NameToCHNodesMap	classNameToInstAndDescsMap
NameToCHNodesMap	templateNameToInstancesMap
CallNodeToCHNodesMap	callNodeToClassesMap
Map< const SVFFunction *, u32_t >	virtualFunctionToIDMap
CallNodeToVTableSetMap	callNodeToCHAVtblsMap
CallNodeToVFunSetMap	callNodeToCHAVFnsMap

Friends
class	SVFIRWriter
class	SVFIRReader
class	CHGBuilder

Additional Inherited Members
Public Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy >
u32_t	edgeNum
	total num of node More...
u32_t	nodeNum
	total num of edge More...
Protected Attributes inherited from SVF::CommonCHGraph
CHGKind	kind
Protected Attributes inherited from SVF::GenericGraph< NodeTy, EdgeTy >
IDToNodeMapTy	IDToNodeMap
	node map More...

Detailed Description

Definition at line 233 of file CHG.h.

Member Typedef Documentation

CallNodeToCHNodesMap

typedef Map<const ICFGNode*, CHNodeSetTy> SVF::CHGraph::CallNodeToCHNodesMap

Definition at line 244 of file CHG.h.

CallNodeToVFunSetMap

typedef Map<const ICFGNode*, VFunSet> SVF::CHGraph::CallNodeToVFunSetMap

Definition at line 246 of file CHG.h.

CallNodeToVTableSetMap

typedef Map<const ICFGNode*, VTableSet> SVF::CHGraph::CallNodeToVTableSetMap

Definition at line 245 of file CHG.h.

CHNodeSetTy

typedef Set<const CHNode*> SVF::CHGraph::CHNodeSetTy

Definition at line 240 of file CHG.h.

NameToCHNodesMap

typedef Map<std::string, CHNodeSetTy> SVF::CHGraph::NameToCHNodesMap

Definition at line 242 of file CHG.h.

WorkList

typedef FIFOWorkList<const CHNode*> SVF::CHGraph::WorkList

Definition at line 241 of file CHG.h.

Member Enumeration Documentation

RELATIONTYPE

enum SVF::CHGraph::RELATIONTYPE

Enumerator
CONSTRUCTOR
DESTRUCTOR

Definition at line 248 of file CHG.h.

    {
        CONSTRUCTOR = 0x1, // connect node based on constructor
        DESTRUCTOR = 0x2 // connect node based on destructor
    } RELATIONTYPE;

Constructor & Destructor Documentation

CHGraph()

SVF::CHGraph::CHGraph ( SVFModule *  svfModule )

inline

Definition at line 254 of file CHG.h.

                                 : svfMod(svfModule), classNum(0), vfID(0), buildingCHGTime(0)
    {
        this->kind = Standard;
    }

~CHGraph()

SVF::CHGraph::~CHGraph ( )

overridedefault

Member Function Documentation

addEdge()

void CHGraph::addEdge	(	const std::string	className,
		const std::string	baseClassName,
		CHEdge::CHEDGETYPE	edgeType
	)

Definition at line 97 of file CHG.cpp.

{
    CHNode *srcNode = getNode(className);
    CHNode *dstNode = getNode(baseClassName);
    assert(srcNode && dstNode && "node not found?");
 
    if (!hasEdge(srcNode, dstNode, edgeType))
    {
        CHEdge *edge = new CHEdge(srcNode, dstNode, edgeType);
        srcNode->addOutgoingEdge(edge);
        dstNode->addIncomingEdge(edge);
    }
}

addInstances()

void SVF::CHGraph::addInstances ( const std::string  templateName, CHNode *  node  )

inline

Definition at line 290 of file CHG.h.

    {
        NameToCHNodesMap::iterator it = templateNameToInstancesMap.find(
                                            templateName);
        if (it != templateNameToInstancesMap.end())
            it->second.insert(node);
        else
            templateNameToInstancesMap[templateName].insert(node);
    }

classof()

static bool SVF::CHGraph::classof ( const CommonCHGraph *  chg )

inlinestatic

Definition at line 313 of file CHG.h.

    {
        return chg->getKind() == Standard;
    }

csHasVFnsBasedonCHA()

bool CHGraph::csHasVFnsBasedonCHA ( const CallICFGNode *  cs )

overridevirtual

Implements SVF::CommonCHGraph.

Definition at line 79 of file CHG.cpp.

{
    CallNodeToVFunSetMap::const_iterator it = callNodeToCHAVFnsMap.find(cs);
    return it != callNodeToCHAVFnsMap.end();
}

csHasVtblsBasedonCHA()

bool CHGraph::csHasVtblsBasedonCHA ( const CallICFGNode *  cs )

overridevirtual

Implements SVF::CommonCHGraph.

Definition at line 74 of file CHG.cpp.

{
    CallNodeToVTableSetMap::const_iterator it = callNodeToCHAVtblsMap.find(cs);
    return it != callNodeToCHAVtblsMap.end();
}

dump()

void CHGraph::dump

(

const std::string &

filename

)

Dump call graph into dot file

Definition at line 242 of file CHG.cpp.

{
    GraphPrinter::WriteGraphToFile(outs(), filename, this);
    printCH();
}

getCSVFsBasedonCHA()

const VFunSet & CHGraph::getCSVFsBasedonCHA ( const CallICFGNode *  cs )

overridevirtual

Implements SVF::CommonCHGraph.

Definition at line 90 of file CHG.cpp.

{
    CallNodeToVFunSetMap::const_iterator it = callNodeToCHAVFnsMap.find(cs);
    assert(it != callNodeToCHAVFnsMap.end() && "cs does not have vfns based on CHA.");
    return it->second;
}

getCSVtblsBasedonCHA()

const VTableSet & CHGraph::getCSVtblsBasedonCHA ( const CallICFGNode *  cs )

overridevirtual

Implements SVF::CommonCHGraph.

Definition at line 84 of file CHG.cpp.

{
    CallNodeToVTableSetMap::const_iterator it = callNodeToCHAVtblsMap.find(cs);
    assert(it != callNodeToCHAVtblsMap.end() && "cs does not have vtabls based on CHA.");
    return it->second;
}

getDescendants()

const CHNodeSetTy& SVF::CHGraph::getDescendants ( const std::string  className )

inline

Definition at line 299 of file CHG.h.

    {
        return classNameToDescendantsMap[className];
    }

getInstances()

const CHNodeSetTy& SVF::CHGraph::getInstances ( const std::string  className )

inline

Definition at line 303 of file CHG.h.

    {
        return templateNameToInstancesMap[className];
    }

getNode()

CHNode * CHGraph::getNode

(

const std::string

name

)

const

Definition at line 112 of file CHG.cpp.

{
    auto chNode = classNameToNodeMap.find(name);
    if (chNode != classNameToNodeMap.end()) return chNode->second;
    else return nullptr;
}

getVFnsFromVtbls()

void CHGraph::getVFnsFromVtbls ( const CallICFGNode *  cs, const VTableSet &  vtbls, VFunSet &  virtualFunctions  )

overridevirtual

get target virtual functions

get the function name of the virtual callsite

Implements SVF::CommonCHGraph.

Definition at line 124 of file CHG.cpp.

{
    size_t idx = callsite->getFunIdxInVtable();
    string funName = callsite->getFunNameOfVirtualCall();
    for (const SVFGlobalValue *vt : vtbls)
    {
        const CHNode *child = getNode(vt->getName());
        if (child == nullptr)
            continue;
        CHNode::FuncVector vfns;
        child->getVirtualFunctions(idx, vfns);
        for (CHNode::FuncVector::const_iterator fit = vfns.begin(),
                feit = vfns.end(); fit != feit; ++fit)
        {
            const SVFFunction* callee = *fit;
            if (callsite->arg_size() == callee->arg_size() ||
                    (callsite->isVarArg() && callee->isVarArg()))
            {
 
                // if argument types do not match
                // skip this one
                if (!checkArgTypes(callsite, callee))
                    continue;
 
                string calleeName = callee->getName();
 
                /*
                 * The compiler will add some special suffix (e.g.,
                 * "[abi:cxx11]") to the end of some virtual function:
                 * In dealII
                 * function: FE_Q<3>::get_name
                 * will be mangled as: _ZNK4FE_QILi3EE8get_nameB5cxx11Ev
                 * after demangling: FE_Q<3>::get_name[abi:cxx11]
                 * The special suffix ("[abi:cxx11]") needs to be removed
                 */
                const std::string suffix("[abi:cxx11]");
                size_t suffix_pos = calleeName.rfind(suffix);
                if (suffix_pos != string::npos)
                    calleeName.erase(suffix_pos, suffix.size());
 
                /*
                 * if we can't get the function name of a virtual callsite, all virtual
                 * functions calculated by idx will be valid
                 */
                if (funName.size() == 0)
                {
                    virtualFunctions.insert(callee);
                }
                else if (funName[0] == '~')
                {
                    /*
                     * if the virtual callsite is calling a destructor, then all
                     * destructors in the ch will be valid
                     * class A { virtual ~A(){} };
                     * class B: public A { virtual ~B(){} };
                     * int main() {
                     *   A *a = new B;
                     *   delete a;  /// the function name of this virtual callsite is ~A()
                     * }
                     */
                    if (calleeName[0] == '~')
                    {
                        virtualFunctions.insert(callee);
                    }
                }
                else
                {
                    /*
                     * for other virtual function calls, the function name of the callsite
                     * and the function name of the target callee should match exactly
                     */
                    if (funName.compare(calleeName) == 0)
                    {
                        virtualFunctions.insert(callee);
                    }
                }
            }
        }
    }
}

getVirtualFunctionBasedonID()

const SVFFunction* SVF::CHGraph::getVirtualFunctionBasedonID ( u32_t  id ) const

inline

Definition at line 278 of file CHG.h.

    {
        Map<const SVFFunction*, u32_t>::const_iterator it, eit;
        for (it = virtualFunctionToIDMap.begin(), eit =
                    virtualFunctionToIDMap.end(); it != eit; ++it)
        {
            if (it->second == id)
                return it->first;
        }
        return nullptr;
    }

getVirtualFunctionID()

u32_t SVF::CHGraph::getVirtualFunctionID ( const SVFFunction *  vfn ) const

inline

Definition at line 269 of file CHG.h.

    {
        Map<const SVFFunction*, u32_t>::const_iterator it =
            virtualFunctionToIDMap.find(vfn);
        if (it != virtualFunctionToIDMap.end())
            return it->second;
        else
            return -1;
    }

printCH()

void CHGraph::printCH

(

)

Definition at line 218 of file CHG.cpp.

{
    for (CHGraph::const_iterator it = this->begin(), eit = this->end();
            it != eit; ++it)
    {
        const CHNode *node = it->second;
        outs() << "class: " << node->getName() << "\n";
        for (CHEdge::CHEdgeSetTy::const_iterator it = node->OutEdgeBegin();
                it != node->OutEdgeEnd(); ++it)
        {
            if ((*it)->getEdgeType() == CHEdge::INHERITANCE)
                outs() << (*it)->getDstNode()->getName() << " --inheritance--> "
                       << (*it)->getSrcNode()->getName() << "\n";
            else
                outs() << (*it)->getSrcNode()->getName() << " --instance--> "
                       << (*it)->getDstNode()->getName() << "\n";
        }
    }
    outs() << '\n';
}

view()

void CHGraph::view

(

)

Definition at line 248 of file CHG.cpp.

{
    SVF::ViewGraph(this, "Class Hierarchy Graph");
}

Friends And Related Function Documentation

CHGBuilder

friend class CHGBuilder

friend

Definition at line 237 of file CHG.h.

SVFIRReader

friend class SVFIRReader

friend

Definition at line 236 of file CHG.h.

SVFIRWriter

friend class SVFIRWriter

friend

Definition at line 235 of file CHG.h.

Member Data Documentation

buildingCHGTime

double SVF::CHGraph::buildingCHGTime

private

Definition at line 323 of file CHG.h.

callNodeToCHAVFnsMap

CallNodeToVFunSetMap SVF::CHGraph::callNodeToCHAVFnsMap

private

Definition at line 334 of file CHG.h.

callNodeToCHAVtblsMap

CallNodeToVTableSetMap SVF::CHGraph::callNodeToCHAVtblsMap

private

Definition at line 333 of file CHG.h.

callNodeToClassesMap

CallNodeToCHNodesMap SVF::CHGraph::callNodeToClassesMap

private

Definition at line 329 of file CHG.h.

classNameToAncestorsMap

NameToCHNodesMap SVF::CHGraph::classNameToAncestorsMap

private

Definition at line 326 of file CHG.h.

classNameToDescendantsMap

NameToCHNodesMap SVF::CHGraph::classNameToDescendantsMap

private

Definition at line 325 of file CHG.h.

classNameToInstAndDescsMap

NameToCHNodesMap SVF::CHGraph::classNameToInstAndDescsMap

private

Definition at line 327 of file CHG.h.

classNameToNodeMap

Map<std::string, CHNode*> SVF::CHGraph::classNameToNodeMap

private

Definition at line 324 of file CHG.h.

classNum

u32_t SVF::CHGraph::classNum

private

Definition at line 321 of file CHG.h.

svfMod

SVFModule* SVF::CHGraph::svfMod

private

Definition at line 320 of file CHG.h.

templateNameToInstancesMap

NameToCHNodesMap SVF::CHGraph::templateNameToInstancesMap

private

Definition at line 328 of file CHG.h.

vfID

u32_t SVF::CHGraph::vfID

private

Definition at line 322 of file CHG.h.

virtualFunctionToIDMap

Map<const SVFFunction*, u32_t> SVF::CHGraph::virtualFunctionToIDMap

private

Definition at line 331 of file CHG.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/Graphs/CHG.h
• /home/runner/work/SVF/SVF/svf/lib/Graphs/CHG.cpp