#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

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	SVFIRWriter

class	SVFIRReader

Detailed Description

Definition at line 41 of file SVFLoopAndDomInfo.h.

Member Typedef Documentation

◆ BBList

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

Definition at line 47 of file SVFLoopAndDomInfo.h.

◆ BBSet

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

Definition at line 46 of file SVFLoopAndDomInfo.h.

◆ LoopBBs

typedef BBList SVF::SVFLoopAndDomInfo::LoopBBs

Definition at line 48 of file SVFLoopAndDomInfo.h.

Constructor & Destructor Documentation

◆ SVFLoopAndDomInfo()

SVF::SVFLoopAndDomInfo::SVFLoopAndDomInfo ( )

inline

Definition at line 60 of file SVFLoopAndDomInfo.h.

61 {

62 }

◆ ~SVFLoopAndDomInfo()

virtual SVF::SVFLoopAndDomInfo::~SVFLoopAndDomInfo ( )

inlinevirtual

Definition at line 64 of file SVFLoopAndDomInfo.h.

64{}

Member Function Documentation

◆ addToBB2LoopMap()

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

inline

Definition at line 94 of file SVFLoopAndDomInfo.h.

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

◆ dominate()

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

Definition at line 65 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 126 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;
}

◆ getBB2PIdom() [1/2]

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

inline

Definition at line 124 of file SVFLoopAndDomInfo.h.

    {
        return bb2PIdom;
    }

◆ getBB2PIdom() [2/2]

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

inline

Definition at line 119 of file SVFLoopAndDomInfo.h.

    {
        return bb2PIdom;
    }

◆ getBBPDomLevel() [1/2]

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

inline

Definition at line 114 of file SVFLoopAndDomInfo.h.

    {
        return bb2PdomLevel;
    }

◆ getBBPDomLevel() [2/2]

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

inline

Definition at line 109 of file SVFLoopAndDomInfo.h.

    {
        return bb2PdomLevel;
    }

◆ getDomFrontierMap() [1/2]

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

inline

Definition at line 71 of file SVFLoopAndDomInfo.h.

    {
        return dfBBsMap;
    }

◆ getDomFrontierMap() [2/2]

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

inline

Definition at line 66 of file SVFLoopAndDomInfo.h.

    {
        return dfBBsMap;
    }

◆ getDomTreeMap() [1/2]

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

inline

Definition at line 130 of file SVFLoopAndDomInfo.h.

    {
        return dtBBsMap;
    }

◆ getDomTreeMap() [2/2]

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

inline

Definition at line 135 of file SVFLoopAndDomInfo.h.

    {
        return dtBBsMap;
    }

◆ getExitBlocksOfLoop()

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

Definition at line 46 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 83 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 39 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 104 of file SVFLoopAndDomInfo.h.

    {
        return pdtBBsMap;
    }

◆ getPostDomTreeMap() [2/2]

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

inline

Definition at line 99 of file SVFLoopAndDomInfo.h.

    {
        return pdtBBsMap;
    }

◆ getReachableBBs()

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

inline

Definition at line 146 of file SVFLoopAndDomInfo.h.

    {
        return reachableBBs;
    }

◆ hasLoopInfo()

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

inline

Definition at line 76 of file SVFLoopAndDomInfo.h.

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

◆ isLoopHeader()

bool SVFLoopAndDomInfo::isLoopHeader ( const SVFBasicBlock * bb ) const

Definition at line 152 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 140 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 89 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 96 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;
}

◆ setReachableBBs()

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

inline

Definition at line 151 of file SVFLoopAndDomInfo.h.

    {
        reachableBBs = bbs;
    }

Friends And Related Symbol Documentation

◆ SVFIRReader

friend class SVFIRReader

friend

Definition at line 44 of file SVFLoopAndDomInfo.h.

◆ SVFIRWriter

friend class SVFIRWriter

friend

Definition at line 43 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 55 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 56 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 57 of file SVFLoopAndDomInfo.h.

◆ dfBBsMap

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

private

map a BasicBlock to its Dominate Frontier BasicBlocks

Definition at line 54 of file SVFLoopAndDomInfo.h.

◆ dtBBsMap

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

private

map a BasicBlock to BasicBlocks it Dominates

Definition at line 52 of file SVFLoopAndDomInfo.h.

◆ pdtBBsMap

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

private

map a BasicBlock to BasicBlocks it PostDominates

Definition at line 53 of file SVFLoopAndDomInfo.h.

◆ reachableBBs

BBList SVF::SVFLoopAndDomInfo::reachableBBs

private

reachable BasicBlocks from the function entry.

Definition at line 51 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

Public Types

Public Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ BBList

◆ BBSet

◆ LoopBBs

Constructor & Destructor Documentation

◆ SVFLoopAndDomInfo()

◆ ~SVFLoopAndDomInfo()

Member Function Documentation

◆ addToBB2LoopMap()

◆ dominate()

◆ findNearestCommonPDominator()

◆ getBB2PIdom() [1/2]

◆ getBB2PIdom() [2/2]

◆ getBBPDomLevel() [1/2]

◆ getBBPDomLevel() [2/2]

◆ getDomFrontierMap() [1/2]

◆ getDomFrontierMap() [2/2]

◆ getDomTreeMap() [1/2]

◆ getDomTreeMap() [2/2]

◆ getExitBlocksOfLoop()

◆ getLoopHeader()

◆ getLoopInfo()

◆ getPostDomTreeMap() [1/2]

◆ getPostDomTreeMap() [2/2]

◆ getReachableBBs()

◆ hasLoopInfo()

◆ isLoopHeader()

◆ isUnreachable()

◆ loopContainsBB()

◆ postDominate()

◆ setReachableBBs()

Friends And Related Symbol Documentation

◆ SVFIRReader

◆ SVFIRWriter

Member Data Documentation

◆ bb2LoopMap

◆ bb2PdomLevel

◆ bb2PIdom

◆ dfBBsMap

◆ dtBBsMap

◆ pdtBBsMap

◆ reachableBBs