Static Value-Flow Analysis
Loading...
Searching...
No Matches
FlowSensitive.cpp
Go to the documentation of this file.
1//===- FlowSensitive.cpp -- Sparse flow-sensitive 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 * FlowSensitive.cpp
25 *
26 * Created on: Oct 28, 2013
27 * Author: Yulei Sui
28 */
29
30#include "Util/Options.h"
31#include "SVFIR/SVFModule.h"
32#include "WPA/WPAStat.h"
33#include "WPA/FlowSensitive.h"
34#include "WPA/Andersen.h"
36
37using namespace SVF;
38using namespace SVFUtil;
39
40std::unique_ptr<FlowSensitive> FlowSensitive::fspta;
41
46{
48
49 stat = new FlowSensitiveStat(this);
50
51 // TODO: support clustered aux. Andersen's.
52 assert(!Options::ClusterAnder() && "FlowSensitive::initialize: clustering auxiliary Andersen's unsupported.");
54
55 // If cluster option is not set, it will give us a no-mapping points-to set.
57 && "FS::init: plain-mapping and cluster-fs are mutually exclusive.");
59 {
60 cluster();
61 // Reset the points-to cache although empty so the new mapping could
62 // be applied to the inserted empty set.
63 getPtCache().reset();
64 }
65 else if (Options::PlainMappingFs())
66 {
67 plainMap();
68 // As above.
69 getPtCache().reset();
70 }
71
73
75 //AndersenWaveDiff::releaseAndersenWaveDiff();
76}
78{
80
81 double start = stat->getClk(true);
83 DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Start Solving Constraints\n"));
84
85 do
86 {
88
90 dumpStat();
91
92 callGraphSCC->find();
93
96 }
98
99 DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Finish Solving Constraints\n"));
100
101 // Reset the time-up alarm; analysis is done.
103
104 double end = stat->getClk(true);
105 solveTime += (end - start) / TIMEINTERVAL;
106
107}
108
113{
115 initialize();
116 if(!filename.empty())
119 if(!filename.empty())
122 finalize();
123}
124
129{
130 if(!Options::ReadAnder().empty())
131 {
133 }
134 else
135 {
136 if(Options::WriteAnder().empty())
137 {
138 initialize();
140 finalize();
141 }
142 else
143 {
145 }
146 }
147}
148
150{
152 initialize();
154 if(!filename.empty())
155 this->readFromFile(filename);
157 finalize();
158}
159
164{
165 if(Options::DumpVFG())
166 svfg->dump("fs_solved", true);
167
169 while (nodeStack.empty() == false)
170 {
171 NodeID rep = nodeStack.top();
172 nodeStack.pop();
173 const NodeBS& subNodes = getSCCDetector()->subNodes(rep);
174 if (subNodes.count() > maxSCCSize)
175 maxSCCSize = subNodes.count();
176 if (subNodes.count() > 1)
177 {
178 numOfNodesInSCC += subNodes.count();
179 numOfSCC++;
180 }
181 }
182
183 // TODO: check -stat too.
184 if (Options::ClusterFs())
185 {
187 const PTDataTy *ptd = getPTDataTy();
188 // TODO: should we use liveOnly?
189 Map<PointsTo, unsigned> allPts = ptd->getAllPts(true);
190 // TODO: parameterise final arg.
193
194 // Do the same for the candidates. TODO: probably temporary for eval. purposes.
195 for (std::pair<hclust_fast_methods, std::vector<NodeID>> &candidate : candidateMappings)
196 {
197 // Can reuse stats, since we're always filling it with `evaluate`, it will always be overwritten.
200 }
201 }
202
204}
205
210{
211 double start = stat->getClk();
213 double end = stat->getClk();
214 sccTime += (end - start) / TIMEINTERVAL;
215 return nodeStack;
216}
217
222{
224 if (processSVFGNode(node))
225 propagate(&node);
226
228}
229
234{
235 double start = stat->getClk();
236 bool changed = false;
237 if (AddrSVFGNode* addr = SVFUtil::dyn_cast<AddrSVFGNode>(node))
238 {
240 if (processAddr(addr))
241 changed = true;
242 }
243 else if (CopySVFGNode* copy = SVFUtil::dyn_cast<CopySVFGNode>(node))
244 {
246 if (processCopy(copy))
247 changed = true;
248 }
249 else if (GepSVFGNode* gep = SVFUtil::dyn_cast<GepSVFGNode>(node))
250 {
252 if(processGep(gep))
253 changed = true;
254 }
255 else if (LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
256 {
258 if(processLoad(load))
259 changed = true;
260 }
261 else if (StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
262 {
264 if (processStore(store))
265 changed = true;
266 }
267 else if (PHISVFGNode* phi = SVFUtil::dyn_cast<PHISVFGNode>(node))
268 {
270 if (processPhi(phi))
271 changed = true;
272 }
275 ActualOUTSVFGNode>(node))
276 {
278 changed = true;
279 }
282 NullPtrSVFGNode>(node))
283 {
284 changed = true;
285 }
286 else if (SVFUtil::isa<CmpVFGNode, BinaryOPVFGNode>(node) ||
287 SVFUtil::dyn_cast<UnaryOPVFGNode>(node))
288 {
289 }
290 else
291 {
292 assert(false && "unexpected kind of SVFG nodes");
293 }
294
295 double end = stat->getClk();
296 processTime += (end - start) / TIMEINTERVAL;
297
298 return changed;
299}
300
310{
311 double start = stat->getClk();
312 bool changed = false;
313
314 if (DirectSVFGEdge* dirEdge = SVFUtil::dyn_cast<DirectSVFGEdge>(edge))
316 else if (IndirectSVFGEdge* indEdge = SVFUtil::dyn_cast<IndirectSVFGEdge>(edge))
318 else
319 assert(false && "new kind of svfg edge?");
320
321 double end = stat->getClk();
323 return changed;
324}
325
330{
331 double start = stat->getClk();
332 bool changed = false;
333
334 SVFGNode* src = edge->getSrcNode();
335 SVFGNode* dst = edge->getDstNode();
336 // If this is an actual-param or formal-ret, top-level pointer's pts must be
337 // propagated from src to dst.
338 if (ActualParmSVFGNode* ap = SVFUtil::dyn_cast<ActualParmSVFGNode>(src))
339 changed = propagateFromAPToFP(ap, dst);
340 else if (FormalRetSVFGNode* fp = SVFUtil::dyn_cast<FormalRetSVFGNode>(src))
342 else
343 {
344 // Direct SVFG edge links between def and use of a top-level pointer.
345 // There's no points-to information propagated along direct edge.
346 // Since the top-level pointer's value has been changed at src node,
347 // return TRUE to put dst node into the work list.
348 changed = true;
349 }
350
351 double end = stat->getClk();
353 return changed;
354}
355
361{
362 const FormalParmSVFGNode* fp = SVFUtil::dyn_cast<FormalParmSVFGNode>(dst);
363 assert(fp && "expecting a formal param node");
364
365 NodeID pagDst = fp->getParam()->getId();
366 const PointsTo &srcCPts = getPts(ap->getParam()->getId());
368
369 return changed;
370}
371
377{
378 const ActualRetSVFGNode* ar = SVFUtil::dyn_cast<ActualRetSVFGNode>(dst);
379 assert(ar && "expecting an actual return node");
380
381 NodeID pagDst = ar->getRev()->getId();
382 const PointsTo & srcCPts = getPts(fr->getRet()->getId());
384
385 return changed;
386}
387
392{
393 double start = stat->getClk();
394
395 SVFGNode* src = edge->getSrcNode();
396 SVFGNode* dst = edge->getDstNode();
397
398 bool changed = false;
399
400 // Get points-to targets may be used by next SVFG node.
401 // Propagate points-to set for node used in dst.
402 const NodeBS& pts = edge->getPointsTo();
403 for (NodeBS::iterator ptdIt = pts.begin(), ptdEit = pts.end(); ptdIt != ptdEit; ++ptdIt)
404 {
405 NodeID ptd = *ptdIt;
406
407 if (propVarPtsFromSrcToDst(ptd, src, dst))
408 changed = true;
409
411 {
414 for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
416 {
417 if (propVarPtsFromSrcToDst(*fieldIt, src, dst))
418 changed = true;
419 }
420 }
421 }
422
423 double end = stat->getClk();
425 return changed;
426}
427
432{
433 bool changed = false;
434 if (SVFUtil::isa<StoreSVFGNode>(src))
435 {
436 if (updateInFromOut(src, var, dst, var))
437 changed = true;
438 }
439 else
440 {
441 if (updateInFromIn(src, var, dst, var))
442 changed = true;
443 }
444 return changed;
445}
446
451{
452 double start = stat->getClk();
453 NodeID srcID = addr->getPAGSrcNodeID();
458 bool changed = addPts(addr->getPAGDstNodeID(), srcID);
459 double end = stat->getClk();
460 addrTime += (end - start) / TIMEINTERVAL;
461 return changed;
462}
463
468{
469 double start = stat->getClk();
470 bool changed = unionPts(copy->getPAGDstNodeID(), copy->getPAGSrcNodeID());
471 double end = stat->getClk();
472 copyTime += (end - start) / TIMEINTERVAL;
473 return changed;
474}
475
480{
481 double start = stat->getClk();
482 bool changed = false;
483 NodeID pagDst = phi->getRes()->getId();
484 for (PHISVFGNode::OPVers::const_iterator it = phi->opVerBegin(), eit = phi->opVerEnd(); it != eit; ++it)
485 {
486 NodeID src = it->second->getId();
487 const PointsTo& srcPts = getPts(src);
488 if (unionPts(pagDst, srcPts))
489 changed = true;
490 }
491
492 double end = stat->getClk();
493 phiTime += (end - start) / TIMEINTERVAL;
494 return changed;
495}
496
501{
502 double start = stat->getClk();
503 bool changed = false;
504 const PointsTo& srcPts = getPts(edge->getPAGSrcNodeID());
505
507 const GepStmt* gepStmt = SVFUtil::cast<GepStmt>(edge->getPAGEdge());
508 if (gepStmt->isVariantFieldGep())
509 {
510 for (NodeID o : srcPts)
511 {
513 {
514 tmpDstPts.set(o);
515 continue;
516 }
517
519 tmpDstPts.set(getFIObjVar(o));
520 }
521 }
522 else
523 {
524 for (NodeID o : srcPts)
525 {
527 {
528 tmpDstPts.set(o);
529 continue;
530 }
531
532 NodeID fieldSrcPtdNode = getGepObjVar(o, gepStmt->getAccessPath().getConstantStructFldIdx());
534 }
535 }
536
537 if (unionPts(edge->getPAGDstNodeID(), tmpDstPts))
538 changed = true;
539
540 double end = stat->getClk();
541 gepTime += (end - start) / TIMEINTERVAL;
542 return changed;
543}
544
545
553{
554 double start = stat->getClk();
555 bool changed = false;
556
557 NodeID dstVar = load->getPAGDstNodeID();
558
559 const PointsTo& srcPts = getPts(load->getPAGSrcNodeID());
560
561 // p = *q, the type of p must be a pointer
562 if(load->getPAGDstNode()->isPointer())
563 {
564 for (PointsTo::iterator ptdIt = srcPts.begin(); ptdIt != srcPts.end(); ++ptdIt)
565 {
566 NodeID ptd = *ptdIt;
567
568 if (pag->isConstantObj(ptd))
569 continue;
570
571 if (unionPtsFromIn(load, ptd, dstVar))
572 changed = true;
573
575 {
579 for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
581 {
582 if (unionPtsFromIn(load, *fieldIt, dstVar))
583 changed = true;
584 }
585 }
586 }
587 }
588 double end = stat->getClk();
589 loadTime += (end - start) / TIMEINTERVAL;
590 return changed;
591}
592
600{
601
602 const PointsTo & dstPts = getPts(store->getPAGDstNodeID());
603
610 if (dstPts.empty())
611 return false;
612
613 double start = stat->getClk();
614 bool changed = false;
615
616 // *p = q, the type of q must be a pointer
617 if(getPts(store->getPAGSrcNodeID()).empty() == false && store->getPAGSrcNode()->isPointer())
618 {
619 for (PointsTo::iterator it = dstPts.begin(), eit = dstPts.end(); it != eit; ++it)
620 {
621 NodeID ptd = *it;
622
623 if (pag->isConstantObj(ptd))
624 continue;
625
626 if (unionPtsFromTop(store, store->getPAGSrcNodeID(), ptd))
627 changed = true;
628 }
629 }
630
631 double end = stat->getClk();
632 storeTime += (end - start) / TIMEINTERVAL;
633
634 double updateStart = stat->getClk();
635 // also merge the DFInSet to DFOutSet.
638 bool isSU = isStrongUpdate(store, singleton);
639 if (isSU)
640 {
641 svfgHasSU.set(store->getId());
643 changed = true;
644 }
645 else
646 {
647 svfgHasSU.reset(store->getId());
648 if (weakUpdateOutFromIn(store))
649 changed = true;
650 }
651 double updateEnd = stat->getClk();
653
654 return changed;
655}
656
661{
662 bool isSU = false;
663 if (const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
664 {
665 const PointsTo& dstCPSet = getPts(store->getPAGDstNodeID());
666 if (dstCPSet.count() == 1)
667 {
670 singleton = *it;
671
672 // Strong update can be made if this points-to target is not heap, array or field-insensitive.
676 {
677 isSU = true;
678 }
679 }
680 }
681 return isSU;
682}
683
688{
689 double start = stat->getClk();
692
693 // Bound the new edges by the Andersen's call graph.
694 // TODO: we want this to be an assertion eventually.
696 for (typename CallEdgeMap::value_type &csfs : newEdges)
697 {
698 const CallICFGNode *potentialCallSite = csfs.first;
700
701 // Check this callsite even calls anything per Andersen's.
702 typename CallEdgeMap::const_iterator andersFunctionSetIt
705 {
706 potentialFunctionSet.clear();
707 }
708
710 for (FunctionSet::iterator potentialFunctionIt = potentialFunctionSet.begin();
712 {
715 {
716 // potentialFunction is not in the Andersen's call graph -- remove it.
718 }
719 else
720 {
721 // potentialFunction is in the Andersen's call graph -- keep it..
723 }
724 }
725 }
726
729
731
732 double end = stat->getClk();
734 return (!newEdges.empty());
735}
736
741{
742 CallEdgeMap::const_iterator iter = newEdges.begin();
743 CallEdgeMap::const_iterator eiter = newEdges.end();
744 for (; iter != eiter; iter++)
745 {
746 const CallICFGNode* cs = iter->first;
747 const FunctionSet & functions = iter->second;
748 for (FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
749 {
750 const SVFFunction* func = *func_iter;
752 }
753 }
754}
755
761{
762 for (const SVFGEdge* edge : edges)
763 {
764 SVFGNode* dstNode = edge->getDstNode();
765 if (SVFUtil::isa<PHISVFGNode>(dstNode))
766 {
769 pushIntoWorklist(dstNode->getId());
770 }
771 else if (SVFUtil::isa<FormalINSVFGNode, ActualOUTSVFGNode>(dstNode))
772 {
775 bool changed = false;
776
777 SVFGNode* srcNode = edge->getSrcNode();
778
779 const NodeBS& pts = SVFUtil::cast<IndirectSVFGEdge>(edge)->getPointsTo();
780 for (NodeBS::iterator ptdIt = pts.begin(), ptdEit = pts.end(); ptdIt != ptdEit; ++ptdIt)
781 {
782 NodeID ptd = *ptdIt;
783
785 changed = true;
786
788 {
791 for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
793 {
795 changed = true;
796 }
797 }
798 }
799
800 if (changed)
801 pushIntoWorklist(dstNode->getId());
802 }
803 }
804}
805
806
811{
812 if (SVFUtil::isa<StoreSVFGNode>(src))
813 {
814 if (propDFOutToIn(src, var, dst, var))
815 return true;
816 }
817 else
818 {
819 if (propDFInToIn(src, var, dst, var))
820 return true;
821 }
822 return false;
823}
824
826{
827 std::vector<std::pair<unsigned, unsigned>> keys;
828 for (const auto& pair : *pag)
829 keys.emplace_back(pair.first, 1);
830
831 PointsTo::MappingPtr nodeMapping =
832 std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::cluster(ander, keys, candidateMappings, "aux-ander"));
833 PointsTo::MappingPtr reverseNodeMapping =
834 std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::getReverseNodeMapping(*nodeMapping));
835
836 PointsTo::setCurrentBestNodeMapping(nodeMapping, reverseNodeMapping);
837}
838
840{
842 && "FS::cluster: plain mapping requires dense allocation strategy.");
843
844 const size_t numObjects = NodeIDAllocator::get()->getNumObjects();
845 PointsTo::MappingPtr plainMapping = std::make_shared<std::vector<NodeID>>(numObjects);
846 PointsTo::MappingPtr reversePlainMapping = std::make_shared<std::vector<NodeID>>(numObjects);
847 for (NodeID i = 0; i < plainMapping->size(); ++i)
848 {
849 plainMapping->at(i) = i;
850 reversePlainMapping->at(i) = i;
851 }
852
854}
855
856void FlowSensitive::countAliases(Set<std::pair<NodeID, NodeID>> cmp, unsigned *mayAliases, unsigned *noAliases)
857{
858 for (std::pair<NodeID, NodeID> locPA : cmp)
859 {
860 // loc doesn't make a difference for FSPTA.
861 NodeID p = locPA.second;
862 for (std::pair<NodeID, NodeID> locPB : cmp)
863 {
864 if (locPB == locPA) continue;
865
866 NodeID q = locPB.second;
867
868 switch (alias(p, q))
869 {
871 ++(*noAliases);
872 break;
874 ++(*mayAliases);
875 break;
876 default:
877 assert("Not May/NoAlias?");
878 }
879 }
880 }
881
882}
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:484
#define TIMEINTERVAL
Definition SVFType.h:512
#define DGENERAL
Definition SVFType.h:490
cJSON * p
Definition cJSON.cpp:2559
copy
Definition cJSON.cpp:414
const PAGNode * getParam() const
Return parameter.
Definition VFGNode.h:907
static AndersenWaveDiff * createAndersenWaveDiff(SVFIR *_pag)
Create an singleton instance directly instead of invoking llvm pass manager.
Definition Andersen.h:408
AliasResult alias(const SVFValue *V1, const SVFValue *V2) override
Interface expose to users of our pointer analysis, given Value infos.
virtual void writeToFile(const std::string &filename)
Interface for analysis result storage on filesystem.
virtual bool readFromFile(const std::string &filename)
virtual void writeObjVarToFile(const std::string &filename)
void finalize() override
Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.
virtual void onTheFlyCallGraphSolve(const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges)
On the fly call graph construction.
PersistentPointsToCache< PointsTo > & getPtCache()
PTData< NodeID, NodeSet, NodeID, PointsTo > PTDataTy
const PointsTo & getPts(NodeID id) override
virtual bool unionPts(NodeID id, const PointsTo &target)
PTDataTy * getPTDataTy() const
Get points-to data structure.
virtual bool addPts(NodeID id, NodeID ptd)
void processNode(NodeID nodeId) override
Handle various constraints.
u32_t numOfProcessedLoad
Number of processed Phi node.
virtual void solveConstraints()
virtual bool unionPtsFromIn(const SVFGNode *stmt, NodeID srcVar, NodeID dstVar)
virtual void updateConnectedNodes(const SVFGEdgeSetTy &edges)
Update nodes connected during updating call graph.
u32_t numOfProcessedCopy
Number of processed Addr node.
virtual void countAliases(Set< std::pair< NodeID, NodeID > > cmp, unsigned *mayAliases, unsigned *noAliases)
Fills may/noAliases for the location/pointer pairs in cmp.
double gepTime
time of handling gep edges
static std::unique_ptr< FlowSensitive > fspta
double indirectPropaTime
time of points-to propagation of top-level pointers
virtual bool propagateFromAPToFP(const ActualParmSVFGNode *ap, const SVFGNode *dst)
double addrTime
time of handling address edges
virtual bool propagateFromFRToAR(const FormalRetSVFGNode *fr, const SVFGNode *dst)
virtual bool propDFInToIn(const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
NodeStack & SCCDetect() override
SCC detection.
double solveTime
time of solve.
bool isStrongUpdate(const SVFGNode *node, NodeID &singleton)
Return TRUE if this is a strong update STORE statement.
virtual void readPtsFromFile(const std::string &filename)
virtual bool unionPtsFromTop(const SVFGNode *stmt, NodeID srcVar, NodeID dstVar)
virtual void plainMap(void) const
Sets the global best mapping as a plain mapping, i.e. n -> n.
AndersenWaveDiff * ander
virtual bool propDFOutToIn(const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
u32_t numOfProcessedStore
Number of processed Load node.
SVFG::SVFGEdgeSetTy SVFGEdgeSetTy
void analyze() override
Flow sensitive analysis.
double storeTime
time of store edges
virtual bool updateInFromIn(const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
double copyTime
time of handling copy edges
bool propFromSrcToDst(SVFGEdge *edge) override
Propagation.
u32_t numOfProcessedGep
Number of processed Copy node.
friend class FlowSensitiveStat
virtual void cluster(void)
virtual bool strongUpdateOutFromIn(const SVFGNode *node, NodeID singleton)
Handle strong updates.
void finalize() override
Finalize analysis.
void clearAllDFOutVarFlag(const SVFGNode *stmt)
bool processSVFGNode(SVFGNode *node)
virtual bool processLoad(const LoadSVFGNode *load)
bool propVarPtsAfterCGUpdated(NodeID var, const SVFGNode *src, const SVFGNode *dst)
virtual bool processPhi(const PHISVFGNode *phi)
virtual bool processStore(const StoreSVFGNode *store)
u32_t maxSCCSize
Number of processed mssa node.
virtual bool processCopy(const CopySVFGNode *copy)
double loadTime
time of load edges
bool updateCallGraph(const CallSiteToFunPtrMap &callsites) override
Update call graph.
virtual bool weakUpdateOutFromIn(const SVFGNode *node)
Handle weak updates.
virtual bool processAddr(const AddrSVFGNode *addr)
u32_t numOfProcessedPhi
Number of processed Gep node.
double propagationTime
time of points-to propagation.
virtual bool propAlongDirectEdge(const DirectSVFGEdge *edge)
Propagate points-to information along a DIRECT SVFG edge.
void initialize() override
Initialize analysis.
void connectCallerAndCallee(const CallEdgeMap &newEdges, SVFGEdgeSetTy &edges)
Connect nodes in SVFG.
std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > candidateMappings
Save candidate mappings for evaluation's sake.
virtual bool processGep(const GepSVFGNode *edge)
double directPropaTime
time of points-to propagation of address-taken objects
double processTime
time of processNode.
u32_t numOfProcessedAddr
Statistics.
virtual bool propVarPtsFromSrcToDst(NodeID var, const SVFGNode *src, const SVFGNode *dst)
Propagate points-to information of a certain variable from src to dst.
virtual bool propAlongIndirectEdge(const IndirectSVFGEdge *edge)
Propagate points-to information along an INDIRECT SVFG edge.
double phiTime
time of phi nodes.
double sccTime
time of SCC detection.
double updateTime
time of strong/weak updates.
virtual bool updateInFromOut(const SVFGNode *srcStmt, NodeID srcVar, const SVFGNode *dstStmt, NodeID dstVar)
u32_t numOfProcessedMSSANode
Number of processed formal ret node.
virtual void solveAndwritePtsToFile(const std::string &filename)
double updateCallGraphTime
time of updating call graph
GEdgeSetTy::const_iterator const_iterator
bool isFieldInsensitive() const
Return true if its field limit is 0.
static std::vector< NodeID > cluster(BVDataPTAImpl *pta, const std::vector< std::pair< NodeID, unsigned > > keys, std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > &candidates, std::string evalSubtitle="")
static std::vector< NodeID > getReverseNodeMapping(const std::vector< NodeID > &nodeMapping)
static void printStats(std::string title, Map< std::string, std::string > &stats)
static void evaluate(const std::vector< NodeID > &nodeMap, const Map< PointsTo, unsigned > pointsToSets, Map< std::string, std::string > &stats, bool accountForOcc)
Fills in *NumWords statistics in stats..
static NodeIDAllocator * get(void)
Return (singleton) allocator.
NodeID getNumObjects(void) const
Returns the total number of memory objects.
static const Option< bool > PlainMappingFs
Use an explicitly plain mapping with flow-sensitive (not null).
Definition Options.h:47
static const OptionMap< SVF::NodeIDAllocator::Strategy > NodeAllocStrat
Definition Options.h:35
static const Option< std::string > ReadAnder
Definition Options.h:214
static const Option< bool > ClusterAnder
Whether to stage Andersen's with Steensgaard and cluster based on that data.
Definition Options.h:41
static const Option< u32_t > FsTimeLimit
Time limit for the main phase (i.e., the actual solving) of FS analyses.
Definition Options.h:72
static const Option< bool > ClusterFs
Whether to cluster FS or VFS with the auxiliary Andersen's.
Definition Options.h:44
static const Option< std::string > WriteAnder
Definition Options.h:212
static const Option< bool > DumpVFG
Definition Options.h:111
bool isFieldInsensitive(NodeID id) const
bool isLocalVarInRecursiveFun(NodeID id) const
Whether a local variable is in function recursions.
OrderedMap< const CallICFGNode *, FunctionSet > CallEdgeMap
virtual void initialize()
Initialization of a pointer analysis, including building symbol table and SVFIR etc.
virtual bool isBlkObjOrConstantObj(NodeID ptd) const
PTAStat * stat
Statistics.
NodeID getFIObjVar(NodeID id)
SVFIR * getPAG() const
const CallSiteToFunPtrMap & getIndirectCallsites() const
Return all indirect callsites.
bool isArrayMemObj(NodeID id) const
NodeID getGepObjVar(NodeID id, const APOffset &ap)
void dumpStat()
Dump the statistics.
CallEdgeMap & getIndCallMap()
Get callees from an indirect callsite.
Set< const SVFFunction * > FunctionSet
void setObjFieldInsensitive(NodeID id)
SVFIR::CallSiteToFunPtrMap CallSiteToFunPtrMap
static SVFIR * pag
SVFIR.
CallGraphSCC * callGraphSCC
SCC for PTACallGraph.
bool isHeapMemObj(NodeID id) const
Whether this object is heap or array.
virtual const NodeBS & getAllFieldsObjVars(NodeID id)
u32_t OnTheFlyIterBudgetForStat
Flag for iteration budget for on-the-fly statistics.
bool empty() const
Returns true if set is empty.
Definition PointsTo.cpp:98
std::shared_ptr< std::vector< NodeID > > MappingPtr
Definition PointsTo.h:42
static void setCurrentBestNodeMapping(MappingPtr newCurrentBestNodeMapping, MappingPtr newCurrentBestReverseNodeMapping)
Definition PointsTo.cpp:371
static MappingPtr getCurrentBestNodeMapping()
Definition PointsTo.cpp:361
NodeID getId() const
Get ID.
SVFG * buildPTROnlySVFG(BVDataPTAImpl *pta)
SVFGNode * getSVFGNode(NodeID id) const
Get a SVFG node.
Definition SVFG.h:150
void dump(const std::string &file, bool simple=false)
Dump graph into dot file.
Definition SVFG.cpp:576
virtual void connectCallerAndCallee(const CallICFGNode *cs, const SVFFunction *callee, SVFGEdgeSetTy &edges)
Connect SVFG nodes between caller and callee for indirect call site.
Definition SVFG.cpp:658
bool isConstantObj(NodeID id) const
Definition SVFIR.h:465
const MemObj * getBaseObj(NodeID id) const
Definition SVFIR.h:481
static double getClk(bool mark=false)
Definition SVFStat.cpp:48
virtual bool isPointer() const
Whether it is a pointer.
void set(unsigned Idx)
unsigned count() const
void reset(unsigned Idx)
NodeID getPAGDstNodeID() const
Definition VFGNode.h:157
PAGNode * getPAGSrcNode() const
Definition VFGNode.h:162
PAGNode * getPAGDstNode() const
Definition VFGNode.h:167
NodeID getPAGSrcNodeID() const
Definition VFGNode.h:152
NodeStack nodeStack
stack used for processing nodes.
Definition WPAFSSolver.h:64
virtual NodeStack & SCCDetect()
SCC detection.
Definition WPAFSSolver.h:67
SCC * getSCCDetector() const
Get SCC detector.
Definition WPASolver.h:67
virtual void pushIntoWorklist(NodeID id)
Definition WPASolver.h:156
virtual void propagate(GNODE *v)
Definition WPASolver.h:127
virtual void initWorklist()
Definition WPASolver.h:97
void setGraph(GraphType g)
Definition WPASolver.h:78
virtual NodeStack & SCCDetect()
SCC detection.
Definition WPASolver.h:86
u32_t numOfIteration
num of iterations during constraint solving
Definition WPASolver.h:200
virtual void solveWorklist()
Definition WPASolver.h:108
hclust_fast_methods
Definition fastcluster.h:66
std::string hclustMethodToString(hclust_fast_methods method)
Returns a string representation of a hclust method.
Definition SVFUtil.cpp:261
void stopAnalysisLimitTimer(bool limitTimerSet)
Definition SVFUtil.cpp:311
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
Definition SVFUtil.cpp:100
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241
bool startAnalysisLimitTimer(unsigned timeLimit)
Definition SVFUtil.cpp:290
std::ostream & outs()
Overwrite llvm::outs()
Definition SVFUtil.h:50
for isBitcode
Definition BasicTypes.h:68
std::stack< NodeID > NodeStack
u32_t NodeID
Definition GeneralType.h:55
@ MayAlias
Definition SVFType.h:529
@ NoAlias
Definition SVFType.h:528
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:96