SVF::SVFLoopAndDomInfo Class Reference

#include <SVFLoopAndDomInfo.h>

Public Types
typedef Set< const SVFBasicBlock * >	BBSet
typedef std::vector< const SVFBasicBlock * >	BBList
typedef BBList	LoopBBs

Public Member Functions
	SVFLoopAndDomInfo ()
virtual	~SVFLoopAndDomInfo ()
const Map< const SVFBasicBlock *, BBSet > &	getDomFrontierMap () const
Map< const SVFBasicBlock *, BBSet > &	getDomFrontierMap ()
bool	hasLoopInfo (const SVFBasicBlock *bb) const
const LoopBBs &	getLoopInfo (const SVFBasicBlock *bb) const
const SVFBasicBlock *	getLoopHeader (const LoopBBs &lp) const
bool	loopContainsBB (const LoopBBs &lp, const SVFBasicBlock *bb) const
void	addToBB2LoopMap (const SVFBasicBlock *bb, const SVFBasicBlock *loopBB)
const Map< const SVFBasicBlock *, BBSet > &	getPostDomTreeMap () const
Map< const SVFBasicBlock *, BBSet > &	getPostDomTreeMap ()
const Map< const SVFBasicBlock *, u32_t > &	getBBPDomLevel () const
Map< const SVFBasicBlock *, u32_t > &	getBBPDomLevel ()
const Map< const SVFBasicBlock *, const SVFBasicBlock * > &	getBB2PIdom () const
Map< const SVFBasicBlock *, const SVFBasicBlock * > &	getBB2PIdom ()
Map< const SVFBasicBlock *, BBSet > &	getDomTreeMap ()
const Map< const SVFBasicBlock *, BBSet > &	getDomTreeMap () const
bool	isUnreachable (const SVFBasicBlock *bb) const
const BBList &	getReachableBBs () const
void	setReachableBBs (BBList &bbs)
void	getExitBlocksOfLoop (const SVFBasicBlock *bb, BBList &exitbbs) const
bool	isLoopHeader (const SVFBasicBlock *bb) const
bool	dominate (const SVFBasicBlock *bbKey, const SVFBasicBlock *bbValue) const
bool	postDominate (const SVFBasicBlock *bbKey, const SVFBasicBlock *bbValue) const
const SVFBasicBlock *	findNearestCommonPDominator (const SVFBasicBlock *A, const SVFBasicBlock *B) const
	find nearest common post dominator of two basic blocks

Protected Member Functions
void	setDomTreeMap (Map< const SVFBasicBlock *, BBSet > &dtMap)
void	setPostDomTreeMap (Map< const SVFBasicBlock *, BBSet > &pdtMap)
void	setDomFrontierMap (Map< const SVFBasicBlock *, BBSet > &dfMap)
void	setBB2LoopMap (Map< const SVFBasicBlock *, LoopBBs > &bb2Loop)
void	setBB2PdomLevel (Map< const SVFBasicBlock *, u32_t > &bb2Pdom)
void	setBB2PIdom (Map< const SVFBasicBlock *, const SVFBasicBlock * > &bb2PIdomMap)
const Map< const SVFBasicBlock *, LoopBBs > &	getBB2LoopMap () const

Private Attributes
BBList	reachableBBs
	reachable BasicBlocks from the function entry.
Map< const SVFBasicBlock *, BBSet >	dtBBsMap
	map a BasicBlock to BasicBlocks it Dominates
Map< const SVFBasicBlock *, BBSet >	pdtBBsMap
	map a BasicBlock to BasicBlocks it PostDominates
Map< const SVFBasicBlock *, BBSet >	dfBBsMap
	map a BasicBlock to its Dominate Frontier BasicBlocks
Map< const SVFBasicBlock *, LoopBBs >	bb2LoopMap
	map a BasicBlock (if it is in a loop) to all the BasicBlocks in this loop
Map< const SVFBasicBlock *, u32_t >	bb2PdomLevel
	map a BasicBlock to its level in pdom tree, used in findNearestCommonPDominator
Map< const SVFBasicBlock *, const SVFBasicBlock * >	bb2PIdom
	map a BasicBlock to its immediate dominator in pdom tree, used in findNearestCommonPDominator

Friends
class	GraphDBClient

Detailed Description

Definition at line 44 of file SVFLoopAndDomInfo.h.

Member Typedef Documentation

BBList

typedef std::vector<const SVFBasicBlock*> SVF::SVFLoopAndDomInfo::BBList

Definition at line 50 of file SVFLoopAndDomInfo.h.

BBSet

typedef Set<const SVFBasicBlock*> SVF::SVFLoopAndDomInfo::BBSet

Definition at line 49 of file SVFLoopAndDomInfo.h.

LoopBBs

typedef BBList SVF::SVFLoopAndDomInfo::LoopBBs

Definition at line 51 of file SVFLoopAndDomInfo.h.

Constructor & Destructor Documentation

SVFLoopAndDomInfo()

SVF::SVFLoopAndDomInfo::SVFLoopAndDomInfo ( )

inline

Definition at line 99 of file SVFLoopAndDomInfo.h.

    {
    }

~SVFLoopAndDomInfo()

virtual SVF::SVFLoopAndDomInfo::~SVFLoopAndDomInfo ( )

inlinevirtual

Definition at line 103 of file SVFLoopAndDomInfo.h.

{}

Member Function Documentation

addToBB2LoopMap()

void SVF::SVFLoopAndDomInfo::addToBB2LoopMap ( const SVFBasicBlock * bb, const SVFBasicBlock * loopBB )

inline

Definition at line 133 of file SVFLoopAndDomInfo.h.

    {
        bb2LoopMap[bb].push_back(loopBB);
    }

dominate()

bool SVFLoopAndDomInfo::dominate	(	const SVFBasicBlock *	bbKey,
		const SVFBasicBlock *	bbValue ) const

Definition at line 103 of file SVFValue.cpp.

{
    if (bbKey == bbValue)
        return true;
 
    // An unreachable node is dominated by anything.
    if (isUnreachable(bbValue))
    {
        return true;
    }
 
    // And dominates nothing.
    if (isUnreachable(bbKey))
    {
        return false;
    }
 
    const Map<const SVFBasicBlock*,BBSet>& dtBBsMap = getDomTreeMap();
    Map<const SVFBasicBlock*,BBSet>::const_iterator mapIter = dtBBsMap.find(bbKey);
    if (mapIter != dtBBsMap.end())
    {
        const BBSet & dtBBs = mapIter->second;
        if (dtBBs.find(bbValue) != dtBBs.end())
        {
            return true;
        }
    }
 
    return false;
}

findNearestCommonPDominator()

const SVFBasicBlock * SVFLoopAndDomInfo::findNearestCommonPDominator	(	const SVFBasicBlock *	A,
		const SVFBasicBlock *	B ) const

find nearest common post dominator of two basic blocks

Definition at line 164 of file SVFValue.cpp.

{
    assert(A && B && "Pointers are not valid");
    assert(A->getParent() == B->getParent() &&
           "Two blocks are not in same function");
 
    // Use level information to go up the tree until the levels match. Then
    // continue going up til we arrive at the same node.
    while (A != B)
    {
        // no common PDominator
        if(A == NULL) return NULL;
        const auto lvA = getBBPDomLevel().find(A);
        const auto lvB = getBBPDomLevel().find(B);
        assert(lvA != getBBPDomLevel().end() && lvB != getBBPDomLevel().end());
 
        if (lvA->second < lvB->second) std::swap(A, B);
 
        const auto lvAIdom = getBB2PIdom().find(A);
        assert(lvAIdom != getBB2PIdom().end());
        A = lvAIdom->second;
    }
 
    return A;
}

getBB2LoopMap()

const Map< const SVFBasicBlock *, LoopBBs > & SVF::SVFLoopAndDomInfo::getBB2LoopMap ( ) const

inlineprotected

Definition at line 93 of file SVFLoopAndDomInfo.h.

    {
        return bb2LoopMap;
    }

getBB2PIdom() [1/2]

Map< const SVFBasicBlock *, const SVFBasicBlock * > & SVF::SVFLoopAndDomInfo::getBB2PIdom ( )

inline

Definition at line 163 of file SVFLoopAndDomInfo.h.

    {
        return bb2PIdom;
    }

getBB2PIdom() [2/2]

const Map< const SVFBasicBlock *, const SVFBasicBlock * > & SVF::SVFLoopAndDomInfo::getBB2PIdom ( ) const

inline

Definition at line 158 of file SVFLoopAndDomInfo.h.

    {
        return bb2PIdom;
    }

getBBPDomLevel() [1/2]

Map< const SVFBasicBlock *, u32_t > & SVF::SVFLoopAndDomInfo::getBBPDomLevel ( )

inline

Definition at line 153 of file SVFLoopAndDomInfo.h.

    {
        return bb2PdomLevel;
    }

getBBPDomLevel() [2/2]

const Map< const SVFBasicBlock *, u32_t > & SVF::SVFLoopAndDomInfo::getBBPDomLevel ( ) const

inline

Definition at line 148 of file SVFLoopAndDomInfo.h.

    {
        return bb2PdomLevel;
    }

getDomFrontierMap() [1/2]

Map< const SVFBasicBlock *, BBSet > & SVF::SVFLoopAndDomInfo::getDomFrontierMap ( )

inline

Definition at line 110 of file SVFLoopAndDomInfo.h.

    {
        return dfBBsMap;
    }

getDomFrontierMap() [2/2]

const Map< const SVFBasicBlock *, BBSet > & SVF::SVFLoopAndDomInfo::getDomFrontierMap ( ) const

inline

Definition at line 105 of file SVFLoopAndDomInfo.h.

    {
        return dfBBsMap;
    }

getDomTreeMap() [1/2]

Map< const SVFBasicBlock *, BBSet > & SVF::SVFLoopAndDomInfo::getDomTreeMap ( )

inline

Definition at line 169 of file SVFLoopAndDomInfo.h.

    {
        return dtBBsMap;
    }

getDomTreeMap() [2/2]

const Map< const SVFBasicBlock *, BBSet > & SVF::SVFLoopAndDomInfo::getDomTreeMap ( ) const

inline

Definition at line 174 of file SVFLoopAndDomInfo.h.

    {
        return dtBBsMap;
    }

getExitBlocksOfLoop()

void SVFLoopAndDomInfo::getExitBlocksOfLoop	(	const SVFBasicBlock *	bb,
		BBList &	exitbbs ) const

Definition at line 84 of file SVFValue.cpp.

{
    if (hasLoopInfo(bb))
    {
        const LoopBBs blocks = getLoopInfo(bb);
        if (!blocks.empty())
        {
            for (const SVFBasicBlock* block : blocks)
            {
                for (const SVFBasicBlock* succ : block->getSuccessors())
                {
                    if ((std::find(blocks.begin(), blocks.end(), succ)==blocks.end()))
                        exitbbs.push_back(succ);
                }
            }
        }
    }
}

getLoopHeader()

const SVFBasicBlock * SVF::SVFLoopAndDomInfo::getLoopHeader ( const LoopBBs & lp ) const

inline

Definition at line 122 of file SVFLoopAndDomInfo.h.

    {
        assert(!lp.empty() && "this is not a loop, empty basic block");
        return lp.front();
    }

getLoopInfo()

const SVFLoopAndDomInfo::LoopBBs & SVFLoopAndDomInfo::getLoopInfo

(

const SVFBasicBlock *

bb

)

const

Definition at line 77 of file SVFValue.cpp.

{
    assert(hasLoopInfo(bb) && "loopinfo does not exist (bb not in a loop)");
    Map<const SVFBasicBlock*, LoopBBs>::const_iterator mapIter = bb2LoopMap.find(bb);
    return mapIter->second;
}

getPostDomTreeMap() [1/2]

Map< const SVFBasicBlock *, BBSet > & SVF::SVFLoopAndDomInfo::getPostDomTreeMap ( )

inline

Definition at line 143 of file SVFLoopAndDomInfo.h.

    {
        return pdtBBsMap;
    }

getPostDomTreeMap() [2/2]

const Map< const SVFBasicBlock *, BBSet > & SVF::SVFLoopAndDomInfo::getPostDomTreeMap ( ) const

inline

Definition at line 138 of file SVFLoopAndDomInfo.h.

    {
        return pdtBBsMap;
    }

getReachableBBs()

const BBList & SVF::SVFLoopAndDomInfo::getReachableBBs ( ) const

inline

Definition at line 185 of file SVFLoopAndDomInfo.h.

    {
        return reachableBBs;
    }

hasLoopInfo()

bool SVF::SVFLoopAndDomInfo::hasLoopInfo ( const SVFBasicBlock * bb ) const

inline

Definition at line 115 of file SVFLoopAndDomInfo.h.

    {
        return bb2LoopMap.find(bb) != bb2LoopMap.end();
    }

isLoopHeader()

bool SVFLoopAndDomInfo::isLoopHeader

(

const SVFBasicBlock *

bb

)

const

Definition at line 190 of file SVFValue.cpp.

{
    if (hasLoopInfo(bb))
    {
        const LoopBBs& blocks = getLoopInfo(bb);
        assert(!blocks.empty() && "no available loop info?");
        return blocks.front() == bb;
    }
    return false;
}

isUnreachable()

bool SVF::SVFLoopAndDomInfo::isUnreachable ( const SVFBasicBlock * bb ) const

inline

Definition at line 179 of file SVFLoopAndDomInfo.h.

    {
        return std::find(reachableBBs.begin(), reachableBBs.end(), bb) ==
               reachableBBs.end();
    }

loopContainsBB()

bool SVF::SVFLoopAndDomInfo::loopContainsBB ( const LoopBBs & lp, const SVFBasicBlock * bb ) const

inline

Definition at line 128 of file SVFLoopAndDomInfo.h.

    {
        return std::find(lp.begin(), lp.end(), bb) != lp.end();
    }

postDominate()

bool SVFLoopAndDomInfo::postDominate	(	const SVFBasicBlock *	bbKey,
		const SVFBasicBlock *	bbValue ) const

Definition at line 134 of file SVFValue.cpp.

{
    if (bbKey == bbValue)
        return true;
 
    // An unreachable node is dominated by anything.
    if (isUnreachable(bbValue))
    {
        return true;
    }
 
    // And dominates nothing.
    if (isUnreachable(bbKey))
    {
        return false;
    }
 
    const Map<const SVFBasicBlock*,BBSet>& dtBBsMap = getPostDomTreeMap();
    Map<const SVFBasicBlock*,BBSet>::const_iterator mapIter = dtBBsMap.find(bbKey);
    if (mapIter != dtBBsMap.end())
    {
        const BBSet & dtBBs = mapIter->second;
        if (dtBBs.find(bbValue) != dtBBs.end())
        {
            return true;
        }
    }
    return false;
}

setBB2LoopMap()

void SVF::SVFLoopAndDomInfo::setBB2LoopMap ( Map< const SVFBasicBlock *, LoopBBs > & bb2Loop )

inlineprotected

Definition at line 78 of file SVFLoopAndDomInfo.h.

    {
        bb2LoopMap = bb2Loop;
    }

setBB2PdomLevel()

void SVF::SVFLoopAndDomInfo::setBB2PdomLevel ( Map< const SVFBasicBlock *, u32_t > & bb2Pdom )

inlineprotected

Definition at line 83 of file SVFLoopAndDomInfo.h.

    {
        bb2PdomLevel = bb2Pdom;
    }

setBB2PIdom()

void SVF::SVFLoopAndDomInfo::setBB2PIdom ( Map< const SVFBasicBlock *, const SVFBasicBlock * > & bb2PIdomMap )

inlineprotected

Definition at line 88 of file SVFLoopAndDomInfo.h.

    {
        bb2PIdom = bb2PIdomMap;
    }

setDomFrontierMap()

void SVF::SVFLoopAndDomInfo::setDomFrontierMap ( Map< const SVFBasicBlock *, BBSet > & dfMap )

inlineprotected

Definition at line 73 of file SVFLoopAndDomInfo.h.

    {
        dfBBsMap = dfMap;
    }

setDomTreeMap()

void SVF::SVFLoopAndDomInfo::setDomTreeMap ( Map< const SVFBasicBlock *, BBSet > & dtMap )

inlineprotected

Definition at line 63 of file SVFLoopAndDomInfo.h.

    {
        dtBBsMap = dtMap;
    }

setPostDomTreeMap()

void SVF::SVFLoopAndDomInfo::setPostDomTreeMap ( Map< const SVFBasicBlock *, BBSet > & pdtMap )

inlineprotected

Definition at line 68 of file SVFLoopAndDomInfo.h.

    {
        pdtBBsMap = pdtMap;
    }

setReachableBBs()

void SVF::SVFLoopAndDomInfo::setReachableBBs ( BBList & bbs )

inline

Definition at line 190 of file SVFLoopAndDomInfo.h.

    {
        reachableBBs = bbs;
    }

Friends And Related Symbol Documentation

GraphDBClient

friend class GraphDBClient

friend

Definition at line 47 of file SVFLoopAndDomInfo.h.

Member Data Documentation

bb2LoopMap

Map<const SVFBasicBlock*, LoopBBs> SVF::SVFLoopAndDomInfo::bb2LoopMap

private

map a BasicBlock (if it is in a loop) to all the BasicBlocks in this loop

Definition at line 58 of file SVFLoopAndDomInfo.h.

bb2PdomLevel

Map<const SVFBasicBlock*, u32_t> SVF::SVFLoopAndDomInfo::bb2PdomLevel

private

map a BasicBlock to its level in pdom tree, used in findNearestCommonPDominator

Definition at line 59 of file SVFLoopAndDomInfo.h.

bb2PIdom

Map<const SVFBasicBlock*, const SVFBasicBlock*> SVF::SVFLoopAndDomInfo::bb2PIdom

private

map a BasicBlock to its immediate dominator in pdom tree, used in findNearestCommonPDominator

Definition at line 60 of file SVFLoopAndDomInfo.h.

dfBBsMap

Map<const SVFBasicBlock*,BBSet> SVF::SVFLoopAndDomInfo::dfBBsMap

private

map a BasicBlock to its Dominate Frontier BasicBlocks

Definition at line 57 of file SVFLoopAndDomInfo.h.

dtBBsMap

Map<const SVFBasicBlock*,BBSet> SVF::SVFLoopAndDomInfo::dtBBsMap

private

map a BasicBlock to BasicBlocks it Dominates

Definition at line 55 of file SVFLoopAndDomInfo.h.

pdtBBsMap

Map<const SVFBasicBlock*,BBSet> SVF::SVFLoopAndDomInfo::pdtBBsMap

private

map a BasicBlock to BasicBlocks it PostDominates

Definition at line 56 of file SVFLoopAndDomInfo.h.

reachableBBs

BBList SVF::SVFLoopAndDomInfo::reachableBBs

private

reachable BasicBlocks from the function entry.

Definition at line 54 of file SVFLoopAndDomInfo.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/Util/SVFLoopAndDomInfo.h
• /home/runner/work/SVF/SVF/svf/lib/SVFIR/SVFValue.cpp