Static Value-Flow Analysis
Loading...
Searching...
No Matches
WPAFSSolver.h
Go to the documentation of this file.
1//===- WPAFSSolver.h -- WPA flow-sensitive solver-----------------------------//
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 * @file: WPAFSSolver.h
25 * @author: yesen
26 * @date: 14/02/2014
27 * @version: 1.0
28 *
29 * @section LICENSE
30 *
31 * @section DESCRIPTION
32 *
33 */
34
35
36#ifndef WPAFSSOLVER_H_
37#define WPAFSSOLVER_H_
38
39#include "WPA/WPASolver.h"
40
41namespace SVF
42{
43
47template<class GraphType>
48class WPAFSSolver : public WPASolver<GraphType>
49{
50public:
52 WPAFSSolver() : WPASolver<GraphType>()
53 {}
55 virtual ~WPAFSSolver() {}
56
58 virtual inline NodeID sccRepNode(NodeID id) const
59 {
60 return id;
61 }
62
63protected:
65
68 {
70 this->getSCCDetector()->find();
71
75 NodeStack& topoStack = this->getSCCDetector()->topoNodeStack();
76 while (!topoStack.empty())
77 {
78 NodeID nodeId = topoStack.top();
79 topoStack.pop();
80 const NodeBS& subNodes = this->getSCCDetector()->subNodes(nodeId);
81 for (NodeBS::iterator it = subNodes.begin(), eit = subNodes.end(); it != eit; ++it)
82 {
83 revTopoStack.push(*it);
84 }
85 }
86
87 assert(nodeStack.empty() && "node stack is not empty, some nodes are not popped properly.");
88
90 while (!revTopoStack.empty())
91 {
93 revTopoStack.pop();
94 nodeStack.push(nodeId);
95 }
96
97 return nodeStack;
98 }
99};
100
101
102
106template<class GraphType>
107class WPASCCSolver : public WPAFSSolver<GraphType>
108{
109public:
113
114 WPASCCSolver() : WPAFSSolver<GraphType>() {}
115
116 virtual ~WPASCCSolver() {}
117
118protected:
119 virtual void solve()
120 {
123 while (!this->isWorklistEmpty())
124 this->popFromWorklist();
125
126 NodeStack& nodeStack = this->SCCDetect();
127
128 while (!nodeStack.empty())
129 {
130 NodeID rep = nodeStack.top();
131 nodeStack.pop();
132
133 setCurrentSCC(rep);
134
135 const NodeBS& sccNodes = this->getSCCDetector()->subNodes(rep);
136 for (NodeBS::iterator it = sccNodes.begin(), eit = sccNodes.end(); it != eit; ++it)
137 this->pushIntoWorklist(*it);
138
139 while (!this->isWorklistEmpty())
140 this->processNode(this->popFromWorklist());
141 }
142 }
143
145 virtual void propagate(GNODE* v)
146 {
147 child_iterator EI = GTraits::direct_child_begin(v);
148 child_iterator EE = GTraits::direct_child_end(v);
149 for (; EI != EE; ++EI)
150 {
151 if (this->propFromSrcToDst(*(EI.getCurrent())))
153 }
154 }
155
156 virtual inline void addNodeIntoWorkList(NodeID node)
157 {
158 if (isInCurrentSCC(node))
159 this->pushIntoWorklist(node);
160 }
161
162 inline bool isInCurrentSCC(NodeID node)
163 {
164 return (const_cast<NodeBS&>(this->getSCCDetector()->subNodes(curSCCID))).test(node);
165 }
166 inline void setCurrentSCC(NodeID id)
167 {
168 curSCCID = this->getSCCDetector()->repNode(id);
169 }
170
172};
173
174
175
179template<class GraphType>
180class WPAMinimumSolver : public WPASCCSolver<GraphType>
181{
182public:
186
187 WPAMinimumSolver() : WPASCCSolver<GraphType>() {}
188
189 virtual ~WPAMinimumSolver() {}
190
191protected:
192 virtual void solve()
193 {
194 bool solveAll = true;
197 if (!this->isWorklistEmpty())
198 {
199 solveAll = false;
200 while (!this->isWorklistEmpty())
202 }
203
204 NodeStack& nodeStack = this->SCCDetect();
205
206 while (!nodeStack.empty())
207 {
208 NodeID rep = nodeStack.top();
209 nodeStack.pop();
210
211 this->setCurrentSCC(rep);
212
213 NodeBS sccNodes = this->getSCCDetector()->subNodes(rep);
214 if (solveAll == false)
216
217 for (NodeBS::iterator it = sccNodes.begin(), eit = sccNodes.end(); it != eit; ++it)
218 this->pushIntoWorklist(*it);
219
220 while (!this->isWorklistEmpty())
221 this->processNode(this->popFromWorklist());
222
223 removeCandidates(sccNodes);
224 }
225 }
226
227 virtual inline void addNodeIntoWorkList(NodeID node)
228 {
229 if (this->isInCurrentSCC(node))
230 this->pushIntoWorklist(node);
231 else
232 addNewCandidate(node);
233 }
234
235private:
236 inline void addNewCandidate(NodeID node)
237 {
238 candidates.set(node);
239 }
240 inline const NodeBS& getCandidates() const
241 {
242 return candidates;
243 }
248
250};
251
252} // End namespace SVF
253
254#endif /* WPAFSSOLVER_H_ */
void set(unsigned Idx)
bool intersectWithComplement(const SparseBitVector &RHS)
iterator begin() const
virtual NodeID sccRepNode(NodeID id) const
SCC methods.
Definition WPAFSSolver.h:58
NodeStack nodeStack
stack used for processing nodes.
Definition WPAFSSolver.h:64
WPAFSSolver()
Constructor.
Definition WPAFSSolver.h:52
virtual NodeStack & SCCDetect()
SCC detection.
Definition WPAFSSolver.h:67
virtual ~WPAFSSolver()
Destructor.
Definition WPAFSSolver.h:55
const NodeBS & getCandidates() const
NodeBS candidates
nodes which need to be analyzed in current iteration.
WPASolver< GraphType >::GTraits GTraits
void addNewCandidate(NodeID node)
void removeCandidates(const NodeBS &nodes)
virtual ~WPAMinimumSolver()
WPASolver< GraphType >::child_iterator child_iterator
WPASolver< GraphType >::GNODE GNODE
virtual void addNodeIntoWorkList(NodeID node)
virtual void solve()
WPASolver< GraphType >::GTraits GTraits
NodeID curSCCID
index of current SCC.
void setCurrentSCC(NodeID id)
virtual void addNodeIntoWorkList(NodeID node)
WPASolver< GraphType >::GNODE GNODE
virtual ~WPASCCSolver()
WPASolver< GraphType >::child_iterator child_iterator
virtual void solve()
bool isInCurrentSCC(NodeID node)
virtual void propagate(GNODE *v)
Propagation for the solving, to be implemented in the child class.
NodeID Node_Index(GNODE node)
Get node ID.
Definition WPASolver.h:183
NodeID popFromWorklist()
Worklist operations.
Definition WPASolver.h:151
GTraits::NodeRef GNODE
Definition WPASolver.h:49
SCC * getSCCDetector() const
Get SCC detector.
Definition WPASolver.h:67
virtual void pushIntoWorklist(NodeID id)
Definition WPASolver.h:156
GTraits::ChildIteratorType child_iterator
Definition WPASolver.h:51
virtual bool propFromSrcToDst(GEDGE *)
Propagate information from source to destination node, to be implemented in the child class.
Definition WPASolver.h:138
bool isWorklistEmpty()
Definition WPASolver.h:160
virtual void processNode(NodeID)
Following methods are to be implemented in child class, in order to achieve a fully worked PTA.
Definition WPASolver.h:122
for isBitcode
Definition BasicTypes.h:68
std::stack< NodeID > NodeStack
u32_t NodeID
Definition GeneralType.h:55
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
iter_range< typename GenericGraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)