Static Value-Flow Analysis
Loading...
Searching...
No Matches
AndersenSCD.cpp
Go to the documentation of this file.
1//===- AndersenSCD.cpp -- SCD based field-sensitive Andersen's analysis-------//
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 * AndersenSCD.cpp
25 *
26 * Created on: 09, Feb, 2019
27 * Author: Yuxiang Lei
28 */
29
30#include "WPA/AndersenPWC.h"
32#include "Util/Options.h"
33#include "Util/PTAStat.h"
34
35using namespace SVF;
36using namespace SVFUtil;
37using namespace std;
38
40
41
46{
47 // Initialize the nodeStack via a whole SCC detection
48 // Nodes in nodeStack are in topological order by default.
49 NodeStack& nodeStack = SCCDetect();
50
51 for (NodeID nId : sccCandidates)
53 sccCandidates.clear();
54
55 // propagate point-to sets
56 while (!nodeStack.empty())
57 {
58 NodeID nodeId = nodeStack.top();
59 nodeStack.pop();
60
61 if (sccRepNode(nodeId) == nodeId)
62 {
63 collapsePWCNode(nodeId);
64
65 if (isInWorklist(nodeId))
66 // push the rep of node into worklist
67 pushIntoWorklist(nodeId);
68
69 double propStart = stat->getClk();
70 // propagate pts through copy and gep edges
71 ConstraintNode* node = consCG->getConstraintNode(nodeId);
72 handleCopyGep(node);
73 double propEnd = stat->getClk();
74 timeOfProcessCopyGep += (propEnd - propStart) / TIMEINTERVAL;
75
77 }
78 }
79
80 // New nodes will be inserted into workList during processing.
81 while (!isWorklistEmpty())
82 {
83 NodeID nodeId = popFromWorklist();
84
85 double insertStart = stat->getClk();
86 // add copy edges via processing load or store edges
87 ConstraintNode* node = consCG->getConstraintNode(nodeId);
88 handleLoadStore(node);
89 double insertEnd = stat->getClk();
90 timeOfProcessLoadStore += (insertEnd - insertStart) / TIMEINTERVAL;
91 }
92}
93
94
99{
101
102 double sccStart = stat->getClk();
104 double sccEnd = stat->getClk();
105 timeOfSCCDetection += (sccEnd - sccStart)/TIMEINTERVAL;
106
107 double mergeStart = stat->getClk();
109 double mergeEnd = stat->getClk();
110 timeOfSCCMerges += (mergeEnd - mergeStart)/TIMEINTERVAL;
111
112 if (!Options::DetectPWC())
113 {
114 sccStart = stat->getClk();
115 PWCDetect();
116 sccEnd = stat->getClk();
117 timeOfSCCDetection += (sccEnd - sccStart) / TIMEINTERVAL;
118 }
119
120 return getSCCDetector()->topoNodeStack();
121}
122
123
128{
129 // replace scc candidates by their reps
130 NodeSet tmpSccCandidates = sccCandidates;
131 sccCandidates.clear();
132 for (NodeID candidate : tmpSccCandidates)
133 sccCandidates.insert(sccRepNode(candidate));
134 tmpSccCandidates.clear();
135
136 // set scc edge type as direct edge
137 bool pwcFlag = Options::DetectPWC();
138 setDetectPWC(true);
139
141
142 // reset scc edge type
143 setDetectPWC(pwcFlag);
144}
145
146
151{
152 NodeID nodeId = node->getId();
153
154 if (!Options::DetectPWC() && getSCCDetector()->subNodes(nodeId).count() > 1)
155 processPWC(node);
156 else if(isInWorklist(nodeId))
158}
159
160
165{
166 NodeID repId = rep->getId();
167
168 NodeSet pwcNodes;
169 for (NodeID nId : getSCCDetector()->subNodes(repId))
170 pwcNodes.insert(nId);
171
172 WorkList tmpWorkList;
173 for (NodeID subId : pwcNodes)
174 if (isInWorklist(subId))
175 tmpWorkList.push(subId);
176
177 while (!tmpWorkList.empty())
178 {
179 NodeID nodeId = tmpWorkList.pop();
180 computeDiffPts(nodeId);
181
182 if (!getDiffPts(nodeId).empty())
183 {
184 ConstraintNode *node = consCG->getConstraintNode(nodeId);
185 for (ConstraintEdge* edge : node->getCopyOutEdges())
186 {
187 bool changed = processCopy(nodeId, edge);
188 if (changed && pwcNodes.find(edge->getDstID()) != pwcNodes.end())
189 tmpWorkList.push(edge->getDstID());
190 }
191 for (ConstraintEdge* edge : node->getGepOutEdges())
192 {
193 if (GepCGEdge *gepEdge = SVFUtil::dyn_cast<GepCGEdge>(edge))
194 {
195 bool changed = processGep(nodeId, gepEdge);
196 if (changed && pwcNodes.find(edge->getDstID()) != pwcNodes.end())
197 tmpWorkList.push(edge->getDstID());
198 }
199 }
200 }
201 }
202}
203
204
210{
211 double insertStart = stat->getClk();
212
213 NodeID nodeId = node->getId();
214 // handle load
216 eit = node->outgoingLoadsEnd(); it != eit; ++it)
217 for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
218 getPts(nodeId).end(); piter != epiter; ++piter)
219 {
220 NodeID ptd = *piter;
221 if (processLoad(ptd, *it))
222 {
223 reanalyze = true;
224 }
225 }
226
227 // handle store
229 eit = node->incomingStoresEnd(); it != eit; ++it)
230 for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
231 getPts(nodeId).end(); piter != epiter; ++piter)
232 {
233 NodeID ptd = *piter;
234 if (processStore(ptd, *it))
235 {
236 reanalyze = true;
237 }
238 }
239
240 double insertEnd = stat->getClk();
241 timeOfProcessLoadStore += (insertEnd - insertStart) / TIMEINTERVAL;
242}
243
244
249{
251
252 NodeID dst = addr->getDstID();
253 NodeID src = addr->getSrcID();
254 addPts(dst,src);
255 addSccCandidate(dst);
256}
257
258
263{
264 if (Andersen::addCopyEdge(src, dst))
265 {
266 addSccCandidate(src);
267 return true;
268 }
269 return false;
270}
271
272
277{
278 double cgUpdateStart = stat->getClk();
279
280 CallEdgeMap newEdges;
281 onTheFlyCallGraphSolve(callsites,newEdges);
282 NodePairSet cpySrcNodes;
283 for(CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); it!=eit; ++it )
284 {
285 for(FunctionSet::iterator cit = it->second.begin(), ecit = it->second.end(); cit!=ecit; ++cit)
286 {
287 connectCaller2CalleeParams(it->first,*cit,cpySrcNodes);
288 }
289 }
290
291 double cgUpdateEnd = stat->getClk();
292 timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL;
293
294 return (!newEdges.empty());
295}
#define TIMEINTERVAL
Definition SVFType.h:604
int count
Definition cJSON.h:216
static double timeOfSCCMerges
Definition Andersen.h:170
static u32_t numOfSCCDetection
Definition Andersen.h:168
static double timeOfUpdateCallGraph
Definition Andersen.h:176
virtual void connectCaller2CalleeParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect callsites.
Definition Andersen.cpp:294
static u32_t numOfProcessedAddr
Statistics.
Definition Andersen.h:160
static double timeOfSCCDetection
Definition Andersen.h:169
static double timeOfProcessLoadStore
Definition Andersen.h:175
static double timeOfProcessCopyGep
Definition Andersen.h:174
ConstraintGraph * consCG
Constraint Graph.
Definition Andersen.h:181
NodeID sccRepNode(NodeID id) const override
SCC methods.
Definition Andersen.h:132
virtual bool addCopyEdge(NodeID src, NodeID dst)
static AndersenSCD * scdAndersen
Definition AndersenPWC.h:52
virtual bool updateCallGraph(const CallSiteToFunPtrMap &callsites)
virtual void processAddr(const AddrCGEdge *addr)
virtual NodeStack & SCCDetect()
virtual void handleLoadStore(ConstraintNode *node)
virtual void solveWorklist()
virtual void handleCopyGep(ConstraintNode *node)
virtual void processPWC(ConstraintNode *rep)
void addSccCandidate(NodeID nodeId)
Definition AndersenPWC.h:82
NodeSet sccCandidates
Definition AndersenPWC.h:53
virtual void PWCDetect()
void setDetectPWC(bool flag)
Definition Andersen.h:273
virtual void computeDiffPts(NodeID id)
Handle diff points-to set.
Definition Andersen.h:283
virtual bool addCopyEdge(NodeID src, NodeID dst)
Add copy edge on constraint graph.
Definition Andersen.h:338
virtual const PointsTo & getDiffPts(NodeID id)
Definition Andersen.h:291
virtual bool processGep(NodeID node, const GepCGEdge *edge)
Definition Andersen.cpp:635
virtual void handleCopyGep(ConstraintNode *node)
Definition Andersen.cpp:498
virtual bool processLoad(NodeID node, const ConstraintEdge *load)
Definition Andersen.cpp:575
virtual const PointsTo & getPts(NodeID id)
Operation of points-to set.
Definition Andersen.h:242
void collapseFields()
collapse positive weight cycles of a graph
Definition Andersen.cpp:717
virtual bool processStore(NodeID node, const ConstraintEdge *load)
Definition Andersen.cpp:595
virtual bool processCopy(NodeID node, const ConstraintEdge *edge)
Definition Andersen.cpp:615
void mergeSccCycle()
Definition Andersen.cpp:732
virtual void collapsePWCNode(NodeID nodeId)
Collapse a field object into its base for field insensitive analysis.
Definition Andersen.cpp:708
virtual void onTheFlyCallGraphSolve(const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges)
On the fly call graph construction.
virtual bool addPts(NodeID id, NodeID ptd)
const_iterator outgoingLoadsEnd() const
Definition ConsGNode.h:194
const ConstraintEdge::ConstraintEdgeSetTy & getGepOutEdges() const
Definition ConsGNode.h:123
const_iterator incomingStoresBegin() const
Definition ConsGNode.h:215
const_iterator incomingStoresEnd() const
Definition ConsGNode.h:219
ConstraintEdge::ConstraintEdgeSetTy::const_iterator const_iterator
Definition ConsGNode.h:45
const ConstraintEdge::ConstraintEdgeSetTy & getCopyOutEdges() const
Definition ConsGNode.h:115
const_iterator outgoingLoadsBegin() const
Definition ConsGNode.h:190
bool push(const Data &data)
Definition WorkList.h:180
bool empty() const
Definition WorkList.h:161
NodeID getDstID() const
NodeID getSrcID() const
get methods of the components
static Option< bool > DetectPWC
Definition Options.h:208
OrderedMap< const CallICFGNode *, FunctionSet > CallEdgeMap
PTAStat * stat
Statistics.
SVFIR::CallSiteToFunPtrMap CallSiteToFunPtrMap
const_iterator iterator
Definition PointsTo.h:41
void find(void)
Definition SCC.h:331
GNodeStack & topoNodeStack()
Definition SCC.h:130
NodeID getId() const
Get ID.
Definition SVFValue.h:158
virtual void pushIntoWorklist(NodeID id)
Definition WPASolver.h:157
FIFOWorkList< NodeID > WorkList
Definition WPASolver.h:56
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405
for isBitcode
Definition BasicTypes.h:70
std::stack< NodeID > NodeStack
Definition GeneralType.h:92
Set< NodeID > NodeSet
Definition GeneralType.h:87
u32_t NodeID
Definition GeneralType.h:76
Set< NodePair > NodePairSet
Definition GeneralType.h:88