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 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.

100 {
101 }

◆ ~SVFLoopAndDomInfo()

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

Definition at line 103 of file SVFLoopAndDomInfo.h.

103{}

Member Function Documentation

◆ addToBB2LoopMap()

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

Definition at line 133 of file SVFLoopAndDomInfo.h.

134 {
135 bb2LoopMap[bb].push_back(loopBB);
136 }
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:58
SVF::IRBuilder
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:76

◆ dominate()

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

Definition at line 103 of file SVFValue.cpp.

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

◆ 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.

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

◆ getBB2LoopMap()

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

Definition at line 93 of file SVFLoopAndDomInfo.h.

94 {
95 return bb2LoopMap;
96 }

◆ getBB2PIdom() [1/2]

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

Definition at line 163 of file SVFLoopAndDomInfo.h.

164 {
165 return bb2PIdom;
166 }
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:60

◆ getBB2PIdom() [2/2]

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

Definition at line 158 of file SVFLoopAndDomInfo.h.

159 {
160 return bb2PIdom;
161 }

◆ getBBPDomLevel() [1/2]

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

Definition at line 153 of file SVFLoopAndDomInfo.h.

154 {
155 return bb2PdomLevel;
156 }
SVF::SVFLoopAndDomInfo::bb2PdomLevel
Map< const SVFBasicBlock *, u32_t > bb2PdomLevel
map a BasicBlock to its level in pdom tree, used in findNearestCommonPDominator
Definition SVFLoopAndDomInfo.h:59

◆ getBBPDomLevel() [2/2]

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

Definition at line 148 of file SVFLoopAndDomInfo.h.

149 {
150 return bb2PdomLevel;
151 }

◆ getDomFrontierMap() [1/2]

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

Definition at line 110 of file SVFLoopAndDomInfo.h.

111 {
112 return dfBBsMap;
113 }
SVF::SVFLoopAndDomInfo::dfBBsMap
Map< const SVFBasicBlock *, BBSet > dfBBsMap
map a BasicBlock to its Dominate Frontier BasicBlocks
Definition SVFLoopAndDomInfo.h:57

◆ getDomFrontierMap() [2/2]

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

Definition at line 105 of file SVFLoopAndDomInfo.h.

106 {
107 return dfBBsMap;
108 }

◆ getDomTreeMap() [1/2]

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

Definition at line 169 of file SVFLoopAndDomInfo.h.

170 {
171 return dtBBsMap;
172 }

◆ getDomTreeMap() [2/2]

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

Definition at line 174 of file SVFLoopAndDomInfo.h.

175 {
176 return dtBBsMap;
177 }

◆ getExitBlocksOfLoop()

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

Definition at line 84 of file SVFValue.cpp.

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

◆ getLoopHeader()

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

Definition at line 122 of file SVFLoopAndDomInfo.h.

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

◆ getLoopInfo()

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

Definition at line 77 of file SVFValue.cpp.

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

◆ getPostDomTreeMap() [1/2]

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

Definition at line 143 of file SVFLoopAndDomInfo.h.

144 {
145 return pdtBBsMap;
146 }
SVF::SVFLoopAndDomInfo::pdtBBsMap
Map< const SVFBasicBlock *, BBSet > pdtBBsMap
map a BasicBlock to BasicBlocks it PostDominates
Definition SVFLoopAndDomInfo.h:56

◆ getPostDomTreeMap() [2/2]

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

Definition at line 138 of file SVFLoopAndDomInfo.h.

139 {
140 return pdtBBsMap;
141 }

◆ getReachableBBs()

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

Definition at line 185 of file SVFLoopAndDomInfo.h.

186 {
187 return reachableBBs;
188 }
SVF::SVFLoopAndDomInfo::reachableBBs
BBList reachableBBs
reachable BasicBlocks from the function entry.
Definition SVFLoopAndDomInfo.h:54

◆ hasLoopInfo()

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

Definition at line 115 of file SVFLoopAndDomInfo.h.

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

◆ isLoopHeader()

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

Definition at line 190 of file SVFValue.cpp.

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

◆ isUnreachable()

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

Definition at line 179 of file SVFLoopAndDomInfo.h.

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

◆ loopContainsBB()

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

Definition at line 128 of file SVFLoopAndDomInfo.h.

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

◆ postDominate()

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

Definition at line 134 of file SVFValue.cpp.

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

◆ setBB2LoopMap()

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

Definition at line 78 of file SVFLoopAndDomInfo.h.

79 {
80 bb2LoopMap = bb2Loop;
81 }

◆ setBB2PdomLevel()

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

Definition at line 83 of file SVFLoopAndDomInfo.h.

84 {
85 bb2PdomLevel = bb2Pdom;
86 }

◆ setBB2PIdom()

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

Definition at line 88 of file SVFLoopAndDomInfo.h.

89 {
90 bb2PIdom = bb2PIdomMap;
91 }

◆ setDomFrontierMap()

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

Definition at line 73 of file SVFLoopAndDomInfo.h.

74 {
75 dfBBsMap = dfMap;
76 }

◆ setDomTreeMap()

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

Definition at line 63 of file SVFLoopAndDomInfo.h.

64 {
65 dtBBsMap = dtMap;
66 }

◆ setPostDomTreeMap()

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

Definition at line 68 of file SVFLoopAndDomInfo.h.

69 {
70 pdtBBsMap = pdtMap;
71 }

◆ setReachableBBs()

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

Definition at line 190 of file SVFLoopAndDomInfo.h.

191 {
192 reachableBBs = bbs;
193 }

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:
Generated by doxygen 1.9.8