Static Value-Flow Analysis
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Member Functions | Private Attributes | Friends | List of all members
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 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 96 of file SVFLoopAndDomInfo.h.

97 {
98 }

◆ ~SVFLoopAndDomInfo()

virtual SVF::SVFLoopAndDomInfo::~SVFLoopAndDomInfo ( )
inlinevirtual

Definition at line 100 of file SVFLoopAndDomInfo.h.

100{}

Member Function Documentation

◆ addToBB2LoopMap()

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

Definition at line 130 of file SVFLoopAndDomInfo.h.

131 {
132 bb2LoopMap[bb].push_back(loopBB);
133 }
SVF::SVFLoopAndDomInfo::bb2LoopMap
Map< const SVFBasicBlock *, LoopBBs > bb2LoopMap
map a BasicBlock (if it is in a loop) to all the BasicBlocks in this loop
Definition SVFLoopAndDomInfo.h:55
SVF::IRBuilder
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74

◆ dominate()

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

Definition at line 102 of file SVFValue.cpp.

103{
104 if (bbKey == bbValue)
105 return true;
106
107 // An unreachable node is dominated by anything.
108 if (isUnreachable(bbValue))
109 {
110 return true;
111 }
112
113 // And dominates nothing.
114 if (isUnreachable(bbKey))
115 {
116 return false;
117 }
118
119 const Map<const SVFBasicBlock*,BBSet>& dtBBsMap = getDomTreeMap();
120 Map<const SVFBasicBlock*,BBSet>::const_iterator mapIter = dtBBsMap.find(bbKey);
121 if (mapIter != dtBBsMap.end())
122 {
123 const BBSet & dtBBs = mapIter->second;
124 if (dtBBs.find(bbValue) != dtBBs.end())
125 {
126 return true;
127 }
128 }
129
130 return false;
131}
SVF::SVFLoopAndDomInfo::getDomTreeMap
Map< const SVFBasicBlock *, BBSet > & getDomTreeMap()
Definition SVFLoopAndDomInfo.h:166
SVF::SVFLoopAndDomInfo::dtBBsMap
Map< const SVFBasicBlock *, BBSet > dtBBsMap
map a BasicBlock to BasicBlocks it Dominates
Definition SVFLoopAndDomInfo.h:52
SVF::SVFLoopAndDomInfo::isUnreachable
bool isUnreachable(const SVFBasicBlock *bb) const
Definition SVFLoopAndDomInfo.h:176
SVF::SVFLoopAndDomInfo::BBSet
Set< const SVFBasicBlock * > BBSet
Definition SVFLoopAndDomInfo.h:46
SVF::Map
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
Definition GeneralType.h:101

◆ findNearestCommonPDominator()

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

find nearest common post dominator of two basic blocks

Definition at line 163 of file SVFValue.cpp.

164{
165 assert(A && B && "Pointers are not valid");
166 assert(A->getParent() == B->getParent() &&
167 "Two blocks are not in same function");
168
169 // Use level information to go up the tree until the levels match. Then
170 // continue going up til we arrive at the same node.
171 while (A != B)
172 {
173 // no common PDominator
174 if(A == NULL) return NULL;
175 const auto lvA = getBBPDomLevel().find(A);
176 const auto lvB = getBBPDomLevel().find(B);
177 assert(lvA != getBBPDomLevel().end() && lvB != getBBPDomLevel().end());
178
179 if (lvA->second < lvB->second) std::swap(A, B);
180
181 const auto lvAIdom = getBB2PIdom().find(A);
182 assert(lvAIdom != getBB2PIdom().end());
183 A = lvAIdom->second;
184 }
185
186 return A;
187}
SVF::SVFLoopAndDomInfo::getBBPDomLevel
const Map< const SVFBasicBlock *, u32_t > & getBBPDomLevel() const
Definition SVFLoopAndDomInfo.h:145
SVF::SVFLoopAndDomInfo::getBB2PIdom
const Map< const SVFBasicBlock *, const SVFBasicBlock * > & getBB2PIdom() const
Definition SVFLoopAndDomInfo.h:155
NULL
#define NULL
Definition extapi.c:5

◆ getBB2LoopMap()

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

Definition at line 90 of file SVFLoopAndDomInfo.h.

91 {
92 return bb2LoopMap;
93 }

◆ getBB2PIdom() [1/2]

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

Definition at line 160 of file SVFLoopAndDomInfo.h.

161 {
162 return bb2PIdom;
163 }
SVF::SVFLoopAndDomInfo::bb2PIdom
Map< const SVFBasicBlock *, const SVFBasicBlock * > bb2PIdom
map a BasicBlock to its immediate dominator in pdom tree, used in findNearestCommonPDominator
Definition SVFLoopAndDomInfo.h:57

◆ getBB2PIdom() [2/2]

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

Definition at line 155 of file SVFLoopAndDomInfo.h.

156 {
157 return bb2PIdom;
158 }

◆ getBBPDomLevel() [1/2]

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

Definition at line 150 of file SVFLoopAndDomInfo.h.

151 {
152 return bb2PdomLevel;
153 }
SVF::SVFLoopAndDomInfo::bb2PdomLevel
Map< const SVFBasicBlock *, u32_t > bb2PdomLevel
map a BasicBlock to its level in pdom tree, used in findNearestCommonPDominator
Definition SVFLoopAndDomInfo.h:56

◆ getBBPDomLevel() [2/2]

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

Definition at line 145 of file SVFLoopAndDomInfo.h.

146 {
147 return bb2PdomLevel;
148 }

◆ getDomFrontierMap() [1/2]

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

Definition at line 107 of file SVFLoopAndDomInfo.h.

108 {
109 return dfBBsMap;
110 }
SVF::SVFLoopAndDomInfo::dfBBsMap
Map< const SVFBasicBlock *, BBSet > dfBBsMap
map a BasicBlock to its Dominate Frontier BasicBlocks
Definition SVFLoopAndDomInfo.h:54

◆ getDomFrontierMap() [2/2]

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

Definition at line 102 of file SVFLoopAndDomInfo.h.

103 {
104 return dfBBsMap;
105 }

◆ getDomTreeMap() [1/2]

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

Definition at line 166 of file SVFLoopAndDomInfo.h.

167 {
168 return dtBBsMap;
169 }

◆ getDomTreeMap() [2/2]

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

Definition at line 171 of file SVFLoopAndDomInfo.h.

172 {
173 return dtBBsMap;
174 }

◆ getExitBlocksOfLoop()

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

Definition at line 83 of file SVFValue.cpp.

84{
85 if (hasLoopInfo(bb))
86 {
87 const LoopBBs blocks = getLoopInfo(bb);
88 if (!blocks.empty())
89 {
90 for (const SVFBasicBlock* block : blocks)
91 {
92 for (const SVFBasicBlock* succ : block->getSuccessors())
93 {
94 if ((std::find(blocks.begin(), blocks.end(), succ)==blocks.end()))
95 exitbbs.push_back(succ);
96 }
97 }
98 }
99 }
100}
SVF::SVFLoopAndDomInfo::getLoopInfo
const LoopBBs & getLoopInfo(const SVFBasicBlock *bb) const
Definition SVFValue.cpp:76
SVF::SVFLoopAndDomInfo::hasLoopInfo
bool hasLoopInfo(const SVFBasicBlock *bb) const
Definition SVFLoopAndDomInfo.h:112

◆ getLoopHeader()

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

Definition at line 119 of file SVFLoopAndDomInfo.h.

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

◆ getLoopInfo()

const SVFLoopAndDomInfo::LoopBBs & SVFLoopAndDomInfo::getLoopInfo ( const SVFBasicBlock *  bb) const

Definition at line 76 of file SVFValue.cpp.

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

◆ getPostDomTreeMap() [1/2]

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

Definition at line 140 of file SVFLoopAndDomInfo.h.

141 {
142 return pdtBBsMap;
143 }
SVF::SVFLoopAndDomInfo::pdtBBsMap
Map< const SVFBasicBlock *, BBSet > pdtBBsMap
map a BasicBlock to BasicBlocks it PostDominates
Definition SVFLoopAndDomInfo.h:53

◆ getPostDomTreeMap() [2/2]

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

Definition at line 135 of file SVFLoopAndDomInfo.h.

136 {
137 return pdtBBsMap;
138 }

◆ getReachableBBs()

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

Definition at line 182 of file SVFLoopAndDomInfo.h.

183 {
184 return reachableBBs;
185 }
SVF::SVFLoopAndDomInfo::reachableBBs
BBList reachableBBs
reachable BasicBlocks from the function entry.
Definition SVFLoopAndDomInfo.h:51

◆ hasLoopInfo()

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

Definition at line 112 of file SVFLoopAndDomInfo.h.

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

◆ isLoopHeader()

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

Definition at line 189 of file SVFValue.cpp.

190{
191 if (hasLoopInfo(bb))
192 {
193 const LoopBBs& blocks = getLoopInfo(bb);
194 assert(!blocks.empty() && "no available loop info?");
195 return blocks.front() == bb;
196 }
197 return false;
198}

◆ isUnreachable()

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

Definition at line 176 of file SVFLoopAndDomInfo.h.

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

◆ loopContainsBB()

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

Definition at line 125 of file SVFLoopAndDomInfo.h.

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

◆ postDominate()

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

Definition at line 133 of file SVFValue.cpp.

134{
135 if (bbKey == bbValue)
136 return true;
137
138 // An unreachable node is dominated by anything.
139 if (isUnreachable(bbValue))
140 {
141 return true;
142 }
143
144 // And dominates nothing.
145 if (isUnreachable(bbKey))
146 {
147 return false;
148 }
149
150 const Map<const SVFBasicBlock*,BBSet>& dtBBsMap = getPostDomTreeMap();
151 Map<const SVFBasicBlock*,BBSet>::const_iterator mapIter = dtBBsMap.find(bbKey);
152 if (mapIter != dtBBsMap.end())
153 {
154 const BBSet & dtBBs = mapIter->second;
155 if (dtBBs.find(bbValue) != dtBBs.end())
156 {
157 return true;
158 }
159 }
160 return false;
161}
SVF::SVFLoopAndDomInfo::getPostDomTreeMap
const Map< const SVFBasicBlock *, BBSet > & getPostDomTreeMap() const
Definition SVFLoopAndDomInfo.h:135

◆ setBB2LoopMap()

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

Definition at line 75 of file SVFLoopAndDomInfo.h.

76 {
77 bb2LoopMap = bb2Loop;
78 }

◆ setBB2PdomLevel()

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

Definition at line 80 of file SVFLoopAndDomInfo.h.

81 {
82 bb2PdomLevel = bb2Pdom;
83 }

◆ setBB2PIdom()

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

Definition at line 85 of file SVFLoopAndDomInfo.h.

86 {
87 bb2PIdom = bb2PIdomMap;
88 }

◆ setDomFrontierMap()

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

Definition at line 70 of file SVFLoopAndDomInfo.h.

71 {
72 dfBBsMap = dfMap;
73 }

◆ setDomTreeMap()

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

Definition at line 60 of file SVFLoopAndDomInfo.h.

61 {
62 dtBBsMap = dtMap;
63 }

◆ setPostDomTreeMap()

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

Definition at line 65 of file SVFLoopAndDomInfo.h.

66 {
67 pdtBBsMap = pdtMap;
68 }

◆ setReachableBBs()

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

Definition at line 187 of file SVFLoopAndDomInfo.h.

188 {
189 reachableBBs = bbs;
190 }

Friends And Related Symbol Documentation

◆ GraphDBClient

friend class GraphDBClient
friend

Definition at line 44 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:
Generated by doxygen 1.9.8