Static Value-Flow Analysis
Loading...
Searching...
No Matches
Andersen.h
Go to the documentation of this file.
1//===- Andersen.h -- Field-sensitive Andersen's pointer 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 * Andersen.h
25 *
26 * Created on: Nov 12, 2013
27 * Author: Yulei Sui
28 *
29 * The field-sensitive implementation is improved based on
30 *
31 * Yuxiang Lei and Yulei Sui. "Fast and Precise Handling of Positive Weight Cycles for Field-sensitive Pointer Analysis".
32 * 26th International Static Analysis Symposium (SAS'19)
33 */
34
35#ifndef INCLUDE_WPA_ANDERSEN_H_
36#define INCLUDE_WPA_ANDERSEN_H_
37
39#include "WPA/WPAStat.h"
40#include "WPA/WPASolver.h"
41#include "SVFIR/SVFIR.h"
42#include "Graphs/ConsG.h"
43#include "Util/Options.h"
44
45namespace SVF
46{
47
48
49class ThreadCallGraph;
50
55
57{
58public:
60
61public:
62
69
71 ~AndersenBase() override;
72
74 virtual void analyze() override;
75
76 virtual void solveAndwritePtsToFile(const std::string& filename);
77
78 virtual void readPtsFromFile(const std::string& filename);
79
80 virtual void solveConstraints();
81
83 virtual void initialize() override;
84
86 virtual void finalize() override;
87
89 virtual bool updateCallGraph(const CallSiteToFunPtrMap&) override;
90
93
95 virtual void connectCaller2ForkedFunParams(const CallICFGNode* cs, const FunObjVar* F,
97
99 virtual void connectCaller2CalleeParams(const CallICFGNode* cs, const FunObjVar* F,
101
103
104 static inline bool classof(const AndersenBase *)
105 {
106 return true;
107 }
108 static inline bool classof(const PointerAnalysis *pta)
109 {
110 return ( pta->getAnalysisTy() == Andersen_BASE
111 || pta->getAnalysisTy() == Andersen_WPA
113 || pta->getAnalysisTy() == AndersenSCD_WPA
114 || pta->getAnalysisTy() == AndersenSFR_WPA
115 || pta->getAnalysisTy() == TypeCPP_WPA
116 || pta->getAnalysisTy() == Steensgaard_WPA);
117 }
119
122 {
123 return consCG;
124 }
125
127
128 inline NodeID sccRepNode(NodeID id) const override
129 {
130 return consCG->sccRepNode(id);
131 }
133 {
134 return consCG->sccSubNodes(repId);
135 }
137
139 virtual bool addCopyEdge(NodeID src, NodeID dst) = 0;
140
142 inline void printStat()
143 {
145 }
146
147 virtual void normalizePointsTo() override;
148
150 void cleanConsCG(NodeID id);
151
153
155
163
165 static double timeOfSCCDetection;
166 static double timeOfSCCMerges;
167 static double timeOfCollapse;
170 static double timeOfProcessCopyGep;
174
175protected:
183};
184
189{
190
191
192public:
194
198 {
199 }
200
202 virtual ~Andersen()
203 {
204
205 }
206
208 virtual void initialize();
209
211 virtual void finalize();
212
214 inline void resetData()
215 {
220 }
221
223
224 static inline bool classof(const Andersen *)
225 {
226 return true;
227 }
228 static inline bool classof(const PointerAnalysis *pta)
229 {
230 return (pta->getAnalysisTy() == Andersen_WPA
232 || pta->getAnalysisTy() == AndersenSCD_WPA
233 || pta->getAnalysisTy() == AndersenSFR_WPA);
234 }
236
238 virtual inline const PointsTo& getPts(NodeID id)
239 {
240 return getPTDataTy()->getPts(sccRepNode(id));
241 }
242 virtual inline bool unionPts(NodeID id, const PointsTo& target)
243 {
244 id = sccRepNode(id);
245 return getPTDataTy()->unionPts(id, target);
246 }
247 virtual inline bool unionPts(NodeID id, NodeID ptd)
248 {
249 id = sccRepNode(id);
250 ptd = sccRepNode(ptd);
251 return getPTDataTy()->unionPts(id,ptd);
252 }
253
254
255 void dumpTopLevelPtsTo();
256
258 {
260 }
261
262protected:
263
265
267 virtual inline void computeDiffPts(NodeID id)
268 {
269 if (Options::DiffPts())
270 {
271 NodeID rep = sccRepNode(id);
272 getDiffPTDataTy()->computeDiffPts(rep, getDiffPTDataTy()->getPts(rep));
273 }
274 }
275 virtual inline const PointsTo& getDiffPts(NodeID id)
276 {
277 NodeID rep = sccRepNode(id);
278 if (Options::DiffPts())
279 return getDiffPTDataTy()->getDiffPts(rep);
280 else
281 return getPTDataTy()->getPts(rep);
282 }
283
286 {
287 if (!Options::DiffPts())
288 return;
291 getDiffPTDataTy()->updatePropaPtsMap(srcRep, dstRep);
292 }
293 inline void clearPropaPts(NodeID src)
294 {
295 if (Options::DiffPts())
296 {
297 NodeID rep = sccRepNode(src);
298 getDiffPTDataTy()->clearPropaPts(rep);
299 }
300 }
301
302 virtual void initWorklist() {}
303
305 virtual void processNode(NodeID nodeId);
306
308
309 void processAllAddr();
310
311 virtual bool processLoad(NodeID node, const ConstraintEdge* load);
312 virtual bool processStore(NodeID node, const ConstraintEdge* load);
313 virtual bool processCopy(NodeID node, const ConstraintEdge* edge);
314 virtual bool processGep(NodeID node, const GepCGEdge* edge);
315 virtual void handleCopyGep(ConstraintNode* node);
316 virtual void handleLoadStore(ConstraintNode* node);
317 virtual void processAddr(const AddrCGEdge* addr);
318 virtual bool processGepPts(const PointsTo& pts, const GepCGEdge* edge);
320
322 virtual inline bool addCopyEdge(NodeID src, NodeID dst)
323 {
324 if (consCG->addCopyCGEdge(src, dst))
325 {
326 updatePropaPts(src, dst);
327 return true;
328 }
329 return false;
330 }
331
334
335 virtual bool mergeSrcToTgt(NodeID srcId,NodeID tgtId);
336
338
339 void mergeSccNodes(NodeID repNodeId, const NodeBS& subNodes);
340 void mergeSccCycle();
342
344 virtual void collapsePWCNode(NodeID nodeId);
345 void collapseFields();
349
352
354 virtual NodeStack& SCCDetect();
355
356
357
360 {
362 {
363 const PointsTo& pts = getPts(it->first);
365
366 for (NodeID o : pts)
367 {
370 }
371
372 for (NodeID o : fldInsenObjs)
373 {
375 for (NodeID f : allFields) addPts(it->first, f);
376 }
377 }
378 }
379
381 virtual const std::string PTAName() const
382 {
383 return "AndersenWPA";
384 }
385
388 virtual void cluster(void) const;
389};
390
391
392
397{
398
399private:
400
401 static AndersenWaveDiff* diffWave; // static instance
402
403public:
405
408 {
409 if(diffWave==nullptr)
410 {
412 diffWave->analyze();
413 return diffWave;
414 }
415 return diffWave;
416 }
418 {
419 if (diffWave)
420 delete diffWave;
421 diffWave = nullptr;
422 }
423
424 virtual void initialize();
425 virtual void solveWorklist();
426 virtual void processNode(NodeID nodeId);
427 virtual void postProcessNode(NodeID nodeId);
428 virtual bool handleLoad(NodeID id, const ConstraintEdge* load);
429 virtual bool handleStore(NodeID id, const ConstraintEdge* store);
430};
431
432} // End namespace SVF
433
434#endif /* INCLUDE_WPA_ANDERSEN_H_ */
newitem type
Definition cJSON.cpp:2739
void setValue(T v)
static bool classof(const PointerAnalysis *pta)
Definition Andersen.h:108
static double timeOfSCCMerges
Definition Andersen.h:166
static u32_t numOfProcessedCopy
Number of processed Addr edge.
Definition Andersen.h:157
NodeBS & sccSubNodes(NodeID repId)
Definition Andersen.h:132
static u32_t numOfSCCDetection
Definition Andersen.h:164
virtual void normalizePointsTo() override
static u32_t numOfSfrs
Number of processed Store edge.
Definition Andersen.h:161
virtual void finalize() override
Finalize analysis.
Definition Andersen.cpp:89
static double timeOfUpdateCallGraph
Definition Andersen.h:172
static u32_t numOfProcessedStore
Number of processed Load edge.
Definition Andersen.h:160
virtual void connectCaller2ForkedFunParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect forksites.
Definition Andersen.cpp:244
static u32_t numOfProcessedAddr
Statistics.
Definition Andersen.h:156
virtual bool updateCallGraph(const CallSiteToFunPtrMap &) override
Update call graph.
Definition Andersen.cpp:190
void printStat()
dump statistics
Definition Andersen.h:142
void heapAllocatorViaIndCall(const CallICFGNode *cs, NodePairSet &cpySrcNodes)
CallSite2DummyValPN callsite2DummyValPN
Definition Andersen.h:179
virtual void readPtsFromFile(const std::string &filename)
Definition Andersen.cpp:157
static u32_t numOfProcessedLoad
Number of processed Gep edge.
Definition Andersen.h:159
static double timeOfSCCDetection
Definition Andersen.h:165
NodeBS redundantGepNodes
Definition Andersen.h:152
virtual bool addCopyEdge(NodeID src, NodeID dst)=0
Add copy edge on constraint graph.
virtual void initialize() override
Initialize analysis.
Definition Andersen.cpp:73
ConstraintGraph * getConstraintGraph()
Get constraint graph.
Definition Andersen.h:121
~AndersenBase() override
Destructor.
Definition Andersen.cpp:64
virtual void analyze() override
Andersen analysis.
Definition Andersen.cpp:133
static u32_t numOfFieldExpand
Definition Andersen.h:162
static double timeOfProcessLoadStore
Definition Andersen.h:171
static u32_t numOfProcessedGep
Number of processed Copy edge.
Definition Andersen.h:158
static double timeOfProcessCopyGep
Definition Andersen.h:170
OrderedMap< const CallICFGNode *, NodeID > CallSite2DummyValPN
Definition Andersen.h:59
static u32_t MaxPointsToSetSize
Definition Andersen.h:169
virtual void solveConstraints()
Definition Andersen.cpp:100
virtual bool updateThreadCallGraph(const CallSiteToFunPtrMap &, NodePairSet &)
Update thread call graph.
Definition Andersen.cpp:224
virtual void connectCaller2CalleeParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect callsites.
static double timeOfCollapse
Definition Andersen.h:167
static u32_t AveragePointsToSetSize
Definition Andersen.h:168
virtual void solveAndwritePtsToFile(const std::string &filename)
Definition Andersen.cpp:168
ConstraintGraph * consCG
Constraint Graph.
Definition Andersen.h:177
void cleanConsCG(NodeID id)
remove redundant gepnodes in constraint graph
Definition Andersen.cpp:180
AndersenBase(SVFIR *_pag, PTATY type=Andersen_BASE, bool alias_check=true)
Constructor.
Definition Andersen.h:64
static bool classof(const AndersenBase *)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition Andersen.h:104
NodeID sccRepNode(NodeID id) const override
SCC methods.
Definition Andersen.h:128
static AndersenWaveDiff * createAndersenWaveDiff(SVFIR *_pag)
Create an singleton instance directly instead of invoking llvm pass manager.
Definition Andersen.h:407
static void releaseAndersenWaveDiff()
Definition Andersen.h:417
AndersenWaveDiff(SVFIR *_pag, PTATY type=AndersenWaveDiff_WPA, bool alias_check=true)
Definition Andersen.h:404
virtual bool handleStore(NodeID id, const ConstraintEdge *store)
virtual bool handleLoad(NodeID id, const ConstraintEdge *load)
virtual void postProcessNode(NodeID nodeId)
static AndersenWaveDiff * diffWave
Definition Andersen.h:401
virtual void processNode(NodeID nodeId)
virtual void handleLoadStore(ConstraintNode *node)
Definition Andersen.cpp:496
void setDetectPWC(bool flag)
Definition Andersen.h:257
virtual ~Andersen()
Destructor.
Definition Andersen.h:202
void mergeSccNodes(NodeID repNodeId, const NodeBS &subNodes)
Merge sub node in a SCC cycle to their rep node.
Definition Andersen.cpp:729
virtual void processNode(NodeID nodeId)
Override WPASolver function in order to use the default solver.
Definition Andersen.cpp:455
virtual void initialize()
Initialize analysis.
Definition Andersen.cpp:418
CallSite2DummyValPN callsite2DummyValPN
Map an instruction to a dummy obj which created at an indirect callsite, which invokes a heap allocat...
Definition Andersen.h:264
void sanitizePts()
Sanitize pts for field insensitive objects.
Definition Andersen.h:359
virtual NodeStack & SCCDetect()
SCC detection.
Definition Andersen.cpp:825
virtual void mergeNodeToRep(NodeID nodeId, NodeID newRepId)
Merge sub node to its rep.
Definition Andersen.cpp:880
bool collapseNodePts(NodeID nodeId)
Definition Andersen.cpp:744
void dumpTopLevelPtsTo()
Definition Andersen.cpp:930
void updatePropaPts(NodeID dstId, NodeID srcId)
Handle propagated points-to set.
Definition Andersen.h:285
static bool classof(const PointerAnalysis *pta)
Definition Andersen.h:228
Andersen(SVFIR *_pag, PTATY type=Andersen_WPA, bool alias_check=true)
Constructor.
Definition Andersen.h:196
SCCDetection< ConstraintGraph * > CGSCC
Definition Andersen.h:193
virtual void computeDiffPts(NodeID id)
Handle diff points-to set.
Definition Andersen.h:267
void clearPropaPts(NodeID src)
Definition Andersen.h:293
virtual bool addCopyEdge(NodeID src, NodeID dst)
Add copy edge on constraint graph.
Definition Andersen.h:322
virtual bool unionPts(NodeID id, NodeID ptd)
Definition Andersen.h:247
virtual void initWorklist()
Definition Andersen.h:302
void resetData()
Reset data.
Definition Andersen.h:214
virtual const PointsTo & getDiffPts(NodeID id)
Definition Andersen.h:275
virtual bool processGep(NodeID node, const GepCGEdge *edge)
Definition Andersen.cpp:613
static bool classof(const Andersen *)
Methods for support type inquiry through isa, cast, and dyn_cast:
Definition Andersen.h:224
virtual void handleCopyGep(ConstraintNode *node)
Definition Andersen.cpp:476
virtual bool unionPts(NodeID id, const PointsTo &target)
Definition Andersen.h:242
virtual bool processLoad(NodeID node, const ConstraintEdge *load)
Definition Andersen.cpp:553
virtual const PointsTo & getPts(NodeID id)
Operation of points-to set.
Definition Andersen.h:238
void collapseFields()
collapse positive weight cycles of a graph
Definition Andersen.cpp:695
virtual bool processStore(NodeID node, const ConstraintEdge *load)
Definition Andersen.cpp:573
virtual bool processCopy(NodeID node, const ConstraintEdge *edge)
Definition Andersen.cpp:593
virtual bool processGepPts(const PointsTo &pts, const GepCGEdge *edge)
Definition Andersen.cpp:622
void mergeSccCycle()
Definition Andersen.cpp:710
virtual void processAddr(const AddrCGEdge *addr)
Definition Andersen.cpp:538
void updateNodeRepAndSubs(NodeID nodeId, NodeID newRepId)
Updates subnodes of its rep, and rep node of its subs.
Definition Andersen.cpp:890
virtual void finalize()
Finalize analysis.
Definition Andersen.cpp:432
virtual const std::string PTAName() const
Get PTA name.
Definition Andersen.h:381
void processAllAddr()
handling various constraints
Definition Andersen.cpp:524
virtual void cluster(void) const
Definition Andersen.cpp:908
virtual bool mergeSrcToTgt(NodeID srcId, NodeID tgtId)
Definition Andersen.cpp:849
virtual void collapsePWCNode(NodeID nodeId)
Collapse a field object into its base for field insensitive analysis.
Definition Andersen.cpp:686
bool collapseField(NodeID nodeId)
Definition Andersen.cpp:764
DiffPTDataTy * getDiffPTDataTy() const
PTDataTy * getPTDataTy() const
Get points-to data structure.
virtual bool addPts(NodeID id, NodeID ptd)
NodeID sccRepNode(NodeID id) const
SCC rep/sub nodes methods.
Definition ConsG.h:230
CopyCGEdge * addCopyCGEdge(NodeID src, NodeID dst)
Add Copy edge.
Definition ConsG.cpp:222
NodeBS & sccSubNodes(NodeID id)
Definition ConsG.h:238
NodeBS & getAllFieldsObjVars(NodeID id)
Definition ConsG.h:311
iterator begin()
Iterators.
IDToNodeMapTy::iterator iterator
Node Iterators.
static Option< bool > DetectPWC
Definition Options.h:216
static const Option< bool > DiffPts
Definition Options.h:215
PTATY
Pointer analysis type list.
@ AndersenSCD_WPA
Selective cycle detection andersen-style WPA.
@ Andersen_BASE
Base Andersen PTA.
@ Andersen_WPA
Andersen PTA.
@ AndersenWaveDiff_WPA
Diff wave propagation andersen-style WPA.
@ TypeCPP_WPA
Type-based analysis for C++.
@ AndersenSFR_WPA
Stride-based field representation.
@ Steensgaard_WPA
Steensgaard PTA.
bool isFieldInsensitive(NodeID id) const
void dumpStat()
Dump the statistics.
PTATY getAnalysisTy() const
Type of pointer analysis.
SVFIR::CallSiteToFunPtrMap CallSiteToFunPtrMap
u32_t OnTheFlyIterBudgetForStat
Flag for iteration budget for on-the-fly statistics.
void set(unsigned Idx)
u32_t iterationForPrintStat
print out statistics for i-th iteration
Definition WPASolver.h:173
for isBitcode
Definition BasicTypes.h:68
std::stack< NodeID > NodeStack
u32_t NodeID
Definition GeneralType.h:56
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
Set< NodePair > NodePairSet
unsigned u32_t
Definition GeneralType.h:47
WPASolver< ConstraintGraph * > WPAConstraintSolver
Definition Andersen.h:54