Static Value-Flow Analysis
Loading...
Searching...
No Matches
SVFLoopAndDomInfo.h
Go to the documentation of this file.
1//===- SVFLoopAndDomInfo.h -- ------------------------------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-2017> <Yulei Sui>
6//
7
8// This program is free software: you can redistribute it and/or modify
9// it under the terms of the GNU Affero General Public License as published by
10// the Free Software Foundation, either version 3 of the License, or
11// (at your option) any later version.
12
13// This program is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16// GNU Affero General Public License for more details.
17
18// You should have received a copy of the GNU Affero General Public License
19// along with this program. If not, see <http://www.gnu.org/licenses/>.
20//
21//===----------------------------------------------------------------------===//
22
23/*
24* SVFLoopAndDomInfo.h
25*
26* Created on: Feb 7, 2025
27* Author: Xiao Cheng
28*
29*/
30
31#ifndef SVFLOOPANDDOMINFO_H
32#define SVFLOOPANDDOMINFO_H
33
34#include "SVFIR/SVFType.h"
35#include "Graphs/GraphPrinter.h"
36#include "Util/Casting.h"
37#include "Graphs/BasicBlockG.h"
38
39namespace SVF
40{
42{
43
44public:
46 typedef std::vector<const SVFBasicBlock*> BBList;
47 typedef BBList LoopBBs;
48
49private:
57
58public:
60 {
61 }
62
63 virtual ~SVFLoopAndDomInfo() {}
64
66 {
67 return dfBBsMap;
68 }
69
74
75 inline bool hasLoopInfo(const SVFBasicBlock* bb) const
76 {
77 return bb2LoopMap.find(bb) != bb2LoopMap.end();
78 }
79
80 const LoopBBs& getLoopInfo(const SVFBasicBlock* bb) const;
81
82 inline const SVFBasicBlock* getLoopHeader(const LoopBBs& lp) const
83 {
84 assert(!lp.empty() && "this is not a loop, empty basic block");
85 return lp.front();
86 }
87
88 inline bool loopContainsBB(const LoopBBs& lp, const SVFBasicBlock* bb) const
89 {
90 return std::find(lp.begin(), lp.end(), bb) != lp.end();
91 }
92
93 inline void addToBB2LoopMap(const SVFBasicBlock* bb, const SVFBasicBlock* loopBB)
94 {
95 bb2LoopMap[bb].push_back(loopBB);
96 }
97
99 {
100 return pdtBBsMap;
101 }
102
107
109 {
110 return bb2PdomLevel;
111 }
112
117
119 {
120 return bb2PIdom;
121 }
122
127
128
130 {
131 return dtBBsMap;
132 }
133
135 {
136 return dtBBsMap;
137 }
138
139 inline bool isUnreachable(const SVFBasicBlock* bb) const
140 {
141 return std::find(reachableBBs.begin(), reachableBBs.end(), bb) ==
142 reachableBBs.end();
143 }
144
145 inline const BBList& getReachableBBs() const
146 {
147 return reachableBBs;
148 }
149
151 {
153 }
154
155 void getExitBlocksOfLoop(const SVFBasicBlock* bb, BBList& exitbbs) const;
156
157 bool isLoopHeader(const SVFBasicBlock* bb) const;
158
159 bool dominate(const SVFBasicBlock* bbKey, const SVFBasicBlock* bbValue) const;
160
161 bool postDominate(const SVFBasicBlock* bbKey, const SVFBasicBlock* bbValue) const;
162
165};
166}
167
168#endif //SVFLOOPANDDOMINFO_H
const Map< const SVFBasicBlock *, BBSet > & getPostDomTreeMap() const
const LoopBBs & getLoopInfo(const SVFBasicBlock *bb) const
Definition SVFValue.cpp:70
const Map< const SVFBasicBlock *, BBSet > & getDomFrontierMap() const
Map< const SVFBasicBlock *, BBSet > & getDomTreeMap()
std::vector< const SVFBasicBlock * > BBList
Map< const SVFBasicBlock *, BBSet > dtBBsMap
map a BasicBlock to BasicBlocks it Dominates
bool dominate(const SVFBasicBlock *bbKey, const SVFBasicBlock *bbValue) const
Definition SVFValue.cpp:96
bool isLoopHeader(const SVFBasicBlock *bb) const
Definition SVFValue.cpp:183
void getExitBlocksOfLoop(const SVFBasicBlock *bb, BBList &exitbbs) const
Definition SVFValue.cpp:77
const SVFBasicBlock * findNearestCommonPDominator(const SVFBasicBlock *A, const SVFBasicBlock *B) const
find nearest common post dominator of two basic blocks
Definition SVFValue.cpp:157
Map< const SVFBasicBlock *, BBSet > pdtBBsMap
map a BasicBlock to BasicBlocks it PostDominates
const Map< const SVFBasicBlock *, u32_t > & getBBPDomLevel() const
const BBList & getReachableBBs() const
Map< const SVFBasicBlock *, BBSet > & getPostDomTreeMap()
Map< const SVFBasicBlock *, u32_t > bb2PdomLevel
map a BasicBlock to its level in pdom tree, used in findNearestCommonPDominator
const Map< const SVFBasicBlock *, const SVFBasicBlock * > & getBB2PIdom() const
const Map< const SVFBasicBlock *, BBSet > & getDomTreeMap() const
Map< const SVFBasicBlock *, BBSet > & getDomFrontierMap()
bool isUnreachable(const SVFBasicBlock *bb) const
const SVFBasicBlock * getLoopHeader(const LoopBBs &lp) const
Map< const SVFBasicBlock *, const SVFBasicBlock * > bb2PIdom
map a BasicBlock to its immediate dominator in pdom tree, used in findNearestCommonPDominator
bool hasLoopInfo(const SVFBasicBlock *bb) const
void setReachableBBs(BBList &bbs)
Set< const SVFBasicBlock * > BBSet
Map< const SVFBasicBlock *, LoopBBs > bb2LoopMap
map a BasicBlock (if it is in a loop) to all the BasicBlocks in this loop
bool loopContainsBB(const LoopBBs &lp, const SVFBasicBlock *bb) const
Map< const SVFBasicBlock *, BBSet > dfBBsMap
map a BasicBlock to its Dominate Frontier BasicBlocks
void addToBB2LoopMap(const SVFBasicBlock *bb, const SVFBasicBlock *loopBB)
Map< const SVFBasicBlock *, const SVFBasicBlock * > & getBB2PIdom()
BBList reachableBBs
reachable BasicBlocks from the function entry.
bool postDominate(const SVFBasicBlock *bbKey, const SVFBasicBlock *bbValue) const
Definition SVFValue.cpp:127
Map< const SVFBasicBlock *, u32_t > & getBBPDomLevel()
for isBitcode
Definition BasicTypes.h:68
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74