#include <SVFValue.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 More...

Private Attributes
BBList	reachableBBs
	reachable BasicBlocks from the function entry. More...

Map< const SVFBasicBlock *, BBSet >	dtBBsMap
	map a BasicBlock to BasicBlocks it Dominates More...

Map< const SVFBasicBlock *, BBSet >	pdtBBsMap
	map a BasicBlock to BasicBlocks it PostDominates More...

Map< const SVFBasicBlock *, BBSet >	dfBBsMap
	map a BasicBlock to its Dominate Frontier BasicBlocks More...

Map< const SVFBasicBlock *, LoopBBs >	bb2LoopMap
	map a BasicBlock (if it is in a loop) to all the BasicBlocks in this loop More...

Map< const SVFBasicBlock *, u32_t >	bb2PdomLevel
	map a BasicBlock to its level in pdom tree, used in findNearestCommonPDominator More...

Map< const SVFBasicBlock , const SVFBasicBlock >	bb2PIdom
	map a BasicBlock to its immediate dominator in pdom tree, used in findNearestCommonPDominator More...

Friends
class	SVFIRWriter

class	SVFIRReader

Detailed Description

Definition at line 50 of file SVFValue.h.

Member Typedef Documentation

◆ BBList

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

Definition at line 56 of file SVFValue.h.

◆ BBSet

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

Definition at line 55 of file SVFValue.h.

◆ LoopBBs

typedef BBList SVF::SVFLoopAndDomInfo::LoopBBs

Definition at line 57 of file SVFValue.h.

Constructor & Destructor Documentation

◆ SVFLoopAndDomInfo()

SVF::SVFLoopAndDomInfo::SVFLoopAndDomInfo ( )

inline

Definition at line 69 of file SVFValue.h.

70 {

71 }

◆ ~SVFLoopAndDomInfo()

virtual SVF::SVFLoopAndDomInfo::~SVFLoopAndDomInfo ( )

inlinevirtual

Definition at line 73 of file SVFValue.h.

73 {}

Member Function Documentation

◆ addToBB2LoopMap()

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

inline

Definition at line 103 of file SVFValue.h.

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

◆ dominate()

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

Definition at line 54 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 115 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 133 of file SVFValue.h.

     {
         return bb2PIdom;
     }

◆ getBB2PIdom() [2/2]

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

inline

Definition at line 128 of file SVFValue.h.

     {
         return bb2PIdom;
     }

◆ getBBPDomLevel() [1/2]

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

inline

Definition at line 123 of file SVFValue.h.

     {
         return bb2PdomLevel;
     }

◆ getBBPDomLevel() [2/2]

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

inline

Definition at line 118 of file SVFValue.h.

     {
         return bb2PdomLevel;
     }

◆ getDomFrontierMap() [1/2]

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

inline

Definition at line 80 of file SVFValue.h.

     {
         return dfBBsMap;
     }

◆ getDomFrontierMap() [2/2]

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

inline

Definition at line 75 of file SVFValue.h.

     {
         return dfBBsMap;
     }

◆ getDomTreeMap() [1/2]

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

inline

Definition at line 139 of file SVFValue.h.

     {
         return dtBBsMap;
     }

◆ getDomTreeMap() [2/2]

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

inline

Definition at line 144 of file SVFValue.h.

     {
         return dtBBsMap;
     }

◆ getExitBlocksOfLoop()

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

Definition at line 35 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 92 of file SVFValue.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 28 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 113 of file SVFValue.h.

     {
         return pdtBBsMap;
     }

◆ getPostDomTreeMap() [2/2]

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

inline

Definition at line 108 of file SVFValue.h.

     {
         return pdtBBsMap;
     }

◆ getReachableBBs()

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

inline

Definition at line 155 of file SVFValue.h.

     {
         return reachableBBs;
     }

◆ hasLoopInfo()

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

inline

Definition at line 85 of file SVFValue.h.

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

◆ isLoopHeader()

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

Definition at line 141 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 149 of file SVFValue.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 98 of file SVFValue.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 85 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 160 of file SVFValue.h.

     {
         reachableBBs = bbs;
     }

Friends And Related Function Documentation

◆ SVFIRReader

friend class SVFIRReader

friend

Definition at line 53 of file SVFValue.h.

◆ SVFIRWriter

friend class SVFIRWriter

friend

Definition at line 52 of file SVFValue.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 64 of file SVFValue.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 65 of file SVFValue.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 66 of file SVFValue.h.

◆ dfBBsMap

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

private

map a BasicBlock to its Dominate Frontier BasicBlocks

Definition at line 63 of file SVFValue.h.

◆ dtBBsMap

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

private

map a BasicBlock to BasicBlocks it Dominates

Definition at line 61 of file SVFValue.h.

◆ pdtBBsMap

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

private

map a BasicBlock to BasicBlocks it PostDominates

Definition at line 62 of file SVFValue.h.

◆ reachableBBs

BBList SVF::SVFLoopAndDomInfo::reachableBBs

private

reachable BasicBlocks from the function entry.

Definition at line 60 of file SVFValue.h.

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

/home/runner/work/SVF/SVF/svf/include/SVFIR/SVFValue.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 Function Documentation

◆ SVFIRReader

◆ SVFIRWriter

Member Data Documentation

◆ bb2LoopMap

◆ bb2PdomLevel

◆ bb2PIdom

◆ dfBBsMap

◆ dtBBsMap

◆ pdtBBsMap

◆ reachableBBs