Static Value-Flow Analysis
Loading...
Searching...
No Matches
Andersen.cpp
Go to the documentation of this file.
1//===- Andersen.cpp -- 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 * Andersen.cpp
25 *
26 * Created on: Nov 12, 2013
27 * Author: Yulei Sui
28 */
29
32#include "WPA/Andersen.h"
33#include "WPA/Steensgaard.h"
34#include "WPA/WPAStat.h"
35#include "Util/CoreBitVector.h"
36#include "Util/GeneralType.h"
37#include "Util/Options.h"
38#include "Util/SVFUtil.h"
39
40#include <utility>
41
42#include <algorithm>
43#include <cstdint>
44#include <vector>
45
46using namespace SVF;
47using namespace SVFUtil;
48using namespace std;
49
50
58
63
69
74{
75 delete consCG;
76 consCG = nullptr;
77}
78
83{
87 stat = new AndersenStat(this);
92 consCG->dump("consCG_initial");
93}
94
99{
102 consCG->dump("consCG_final");
103
105 consCG->print();
107}
108
110{
111 // Start solving constraints
112 DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Start Solving Constraints\n"));
113
114 bool timeLimited = Options::AnderTimeLimit() > 0;
115 if (timeLimited)
116 {
117 assert(Options::FsTimeLimit() == 0 && "both -ander-time-limit and -fs-time-limit set.");
119 }
120
121 initWorklist();
122 do
123 {
126 printStat();
127
128 reanalyze = false;
129
131
133 reanalyze = true;
134
135 }
136 while (reanalyze);
137
138 // Analysis is finished, reset the alarm if we set it.
139 if (timeLimited)
140 {
142 }
143
144 DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Finish Solving Constraints\n"));
145}
146
151{
152 if(!Options::ReadAnder().empty())
153 {
155 }
156 else
157 {
158 if(Options::WriteAnder().empty())
159 {
160 initialize();
162 finalize();
163 }
164 else
165 {
167 }
168 }
169}
170
174void AndersenBase::readPtsFromFile(const std::string& filename)
175{
176 initialize();
177 if (!filename.empty())
178 this->readFromFile(filename);
179 finalize();
180}
181
185void AndersenBase:: solveAndwritePtsToFile(const std::string& filename)
186{
188 initialize();
189 if (!filename.empty())
190 this->writeObjVarToFile(filename);
192 if (!filename.empty())
193 this->writeToFile(filename);
194 finalize();
195}
196
198{
199 // Remove only this node from its representative's members. Erasing the whole
200 // member set would leave every other member mapped to a representative that no
201 // longer lists it, so sccSubNodes would stop being the inverse of sccRepNode.
202 consCG->getSubs(consCG->sccRepNode(id)).reset(id);
203 for (NodeID sub: consCG->getSubs(id))
204 consCG->resetRep(sub);
205 consCG->resetSubs(id);
206 consCG->resetRep(id);
207 assert(!consCG->hasGNode(id) && "this is either a rep nodeid or a sub nodeid should have already been merged to its field-insensitive base! ");
208}
209
211{
212
213 double cgUpdateStart = stat->getClk();
214
215 CallEdgeMap newEdges;
216 onTheFlyCallGraphSolve(callsites, newEdges);
217 NodePairSet cpySrcNodes;
218 for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end();
219 it != eit; ++it)
220 {
221 for (FunctionSet::iterator cit = it->second.begin(),
222 ecit = it->second.end();
223 cit != ecit; ++cit)
224 {
225 connectCaller2CalleeParams(it->first, *cit, cpySrcNodes);
226 }
227 }
228
229 bool hasNewForkEdges = updateThreadCallGraph(callsites, cpySrcNodes);
230
231 for (NodePairSet::iterator it = cpySrcNodes.begin(),
232 eit = cpySrcNodes.end();
233 it != eit; ++it)
234 {
235 pushIntoWorklist(it->first);
236 }
237
238 double cgUpdateEnd = stat->getClk();
239 timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL;
240
241 return ((!newEdges.empty()) || hasNewForkEdges);
242}
243
245 NodePairSet& cpySrcNodes)
246{
247 CallEdgeMap newForkEdges;
248 onTheFlyThreadCallGraphSolve(callsites, newForkEdges);
249 for (CallEdgeMap::iterator it = newForkEdges.begin(), eit = newForkEdges.end(); it != eit; it++)
250 {
251 for (FunctionSet::iterator cit = it->second.begin(),
252 ecit = it->second.end();
253 cit != ecit; ++cit)
254 {
255 connectCaller2ForkedFunParams(it->first, *cit, cpySrcNodes);
256 }
257 }
258 return !newForkEdges.empty();
259}
260
265 NodePairSet& cpySrcNodes)
266{
267 assert(F);
268
269 DBOUT(DAndersen, outs() << "connect parameters from indirect forksite "
270 << cs->valueOnlyToString() << " to forked function "
271 << *F << "\n");
272
274
275 const PAGNode *cs_arg = tdCallGraph->getThreadAPI()->getActualParmAtForkSite(cs);
276 const PAGNode *fun_arg = tdCallGraph->getThreadAPI()->getFormalParmOfForkedFun(F);
277
278 if(cs_arg->isPointer() && fun_arg->isPointer())
279 {
280 DBOUT(DAndersen, outs() << "process actual parm"
281 << cs_arg->toString() << "\n");
282 NodeID srcAA = sccRepNode(cs_arg->getId());
283 NodeID dstFA = sccRepNode(fun_arg->getId());
284 if (addCopyEdge(srcAA, dstFA))
285 {
286 cpySrcNodes.insert(std::make_pair(srcAA, dstFA));
287 }
288 }
289}
290
292// * Connect formal and actual parameters for indirect callsites
293// */
295 const FunObjVar* F, NodePairSet &cpySrcNodes)
296{
297 assert(F);
298
299 DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << cs->valueOnlyToString() << " to callee " << *F << "\n");
300
301 const CallICFGNode* callBlockNode = cs;
302 const RetICFGNode* retBlockNode = cs->getRetICFGNode();
303
304 if(SVFUtil::isHeapAllocExtFunViaRet(F) && pag->callsiteHasRet(retBlockNode))
305 {
306 heapAllocatorViaIndCall(cs,cpySrcNodes);
307 }
308
309 if (pag->funHasRet(F) && pag->callsiteHasRet(retBlockNode))
310 {
311 const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode);
312 const PAGNode* fun_return = pag->getFunRet(F);
313 if (cs_return->isPointer() && fun_return->isPointer())
314 {
315 NodeID dstrec = sccRepNode(cs_return->getId());
316 NodeID srcret = sccRepNode(fun_return->getId());
317 if(addCopyEdge(srcret, dstrec))
318 {
319 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
320 }
321 }
322 else
323 {
324 DBOUT(DAndersen, outs() << "not a pointer ignored\n");
325 }
326 }
327
328 if (pag->hasCallSiteArgsMap(callBlockNode) && pag->hasFunArgsList(F))
329 {
330
331 // connect actual and formal param
332 const SVFIR::ValVarList& csArgList = pag->getCallSiteArgsList(callBlockNode);
333 const SVFIR::ValVarList& funArgList = pag->getFunArgsList(F);
334 //Go through the fixed parameters.
335 DBOUT(DPAGBuild, outs() << " args:");
336 SVFIR::ValVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end();
337 SVFIR::ValVarList::const_iterator csArgIt = csArgList.begin(), csArgEit = csArgList.end();
338 for (; funArgIt != funArgEit; ++csArgIt, ++funArgIt)
339 {
340 //Some programs (e.g. Linux kernel) leave unneeded parameters empty.
341 if (csArgIt == csArgEit)
342 {
343 DBOUT(DAndersen, outs() << " !! not enough args\n");
344 break;
345 }
346 const PAGNode *cs_arg = *csArgIt ;
347 const PAGNode *fun_arg = *funArgIt;
348
349 if (cs_arg->isPointer() && fun_arg->isPointer())
350 {
351 DBOUT(DAndersen, outs() << "process actual parm " << cs_arg->toString() << " \n");
352 NodeID srcAA = sccRepNode(cs_arg->getId());
353 NodeID dstFA = sccRepNode(fun_arg->getId());
354 if(addCopyEdge(srcAA, dstFA))
355 {
356 cpySrcNodes.insert(std::make_pair(srcAA,dstFA));
357 }
358 }
359 }
360
361 //Any remaining actual args must be varargs.
362 if (F->isVarArg())
363 {
364 NodeID vaF = sccRepNode(pag->getVarargNode(F));
365 DBOUT(DPAGBuild, outs() << "\n varargs:");
366 for (; csArgIt != csArgEit; ++csArgIt)
367 {
368 const PAGNode *cs_arg = *csArgIt;
369 if (cs_arg->isPointer())
370 {
371 NodeID vnAA = sccRepNode(cs_arg->getId());
372 if (addCopyEdge(vnAA,vaF))
373 {
374 cpySrcNodes.insert(std::make_pair(vnAA,vaF));
375 }
376 }
377 }
378 }
379 if(csArgIt != csArgEit)
380 {
381 writeWrnMsg("too many args to non-vararg func.");
382 writeWrnMsg("(" + cs->getSourceLoc() + ")");
383 }
384 }
385}
386
388{
389 assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?");
390 const RetICFGNode* retBlockNode = cs->getRetICFGNode();
391 const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode);
392 NodeID srcret;
393 CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs);
394 if(it != callsite2DummyValPN.end())
395 {
396 srcret = sccRepNode(it->second);
397 }
398 else
399 {
400 NodeID valNode = pag->addDummyValNode();
401 NodeID objNode = pag->addDummyObjNode(cs->getType());
402 addPts(valNode,objNode);
403 callsite2DummyValPN.insert(std::make_pair(cs,valNode));
404 consCG->addConstraintNode(new ConstraintNode(valNode),valNode);
405 consCG->addConstraintNode(new ConstraintNode(objNode),objNode);
406 srcret = valNode;
407 }
408
409 NodeID dstrec = sccRepNode(cs_return->getId());
410 if(addCopyEdge(srcret, dstrec))
411 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
412}
413
415{
416 SVFIR::MemObjToFieldsMap &memToFieldsMap = pag->getMemToFieldsMap();
417 SVFIR::OffsetToGepVarMap &GepObjVarMap = pag->getGepObjNodeMap();
418
419 // clear GepObjVarMap/memToFieldsMap/nodeToSubsMap/nodeToRepMap
420 // for redundant gepnodes and remove those nodes from pag
422 {
423 NodeID base = pag->getBaseObjVarID(n);
424 const GepObjVar* gepNode = pag->getGepObjVar(n);
425 assert(gepNode && "Not a gep node in redundantGepNodes set");
426 const APOffset apOffset = gepNode->getConstantFieldIdx();
427 GepObjVarMap.erase(std::make_pair(base, apOffset));
428 memToFieldsMap[base].reset(n);
429 cleanConsCG(n);
430
431 pag->removeGNode(const_cast<GepObjVar*>(gepNode));
432 }
433}
434
439{
440 resetData();
442
444
447}
448
453{
454 // TODO: broken
456 {
458 const PTDataTy *ptd = getPTDataTy();
459 // TODO: should we use liveOnly?
460 // TODO: parameterise final arg.
462 if (print_stat)
463 {
464 NodeIDAllocator::Clusterer::printStats("post-main", stats);
465 }
466 }
467
470 // sanitizePts();
472}
473
478{
479 // sub nodes do not need to be processed
480 if (sccRepNode(nodeId) != nodeId)
481 return;
482
483 ConstraintNode* node = consCG->getConstraintNode(nodeId);
484 double insertStart = stat->getClk();
485 handleLoadStore(node);
486 double insertEnd = stat->getClk();
487 timeOfProcessLoadStore += (insertEnd - insertStart) / TIMEINTERVAL;
488
489 double propStart = stat->getClk();
490 handleCopyGep(node);
491 double propEnd = stat->getClk();
492 timeOfProcessCopyGep += (propEnd - propStart) / TIMEINTERVAL;
493}
494
499{
500 NodeID nodeId = node->getId();
501 computeDiffPts(nodeId);
502
503 if (!getDiffPts(nodeId).empty())
504 {
505 for (ConstraintEdge* edge : node->getCopyOutEdges())
506 processCopy(nodeId, edge);
507 for (ConstraintEdge* edge : node->getGepOutEdges())
508 {
509 if (GepCGEdge* gepEdge = SVFUtil::dyn_cast<GepCGEdge>(edge))
510 processGep(nodeId, gepEdge);
511 }
512 }
513}
514
519{
520 NodeID nodeId = node->getId();
521 for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
522 getPts(nodeId).end(); piter != epiter; ++piter)
523 {
524 NodeID ptd = *piter;
525 // handle load
527 eit = node->outgoingLoadsEnd(); it != eit; ++it)
528 {
529 if (processLoad(ptd, *it))
530 pushIntoWorklist(ptd);
531 }
532
533 // handle store
535 eit = node->incomingStoresEnd(); it != eit; ++it)
536 {
537 if (processStore(ptd, *it))
538 pushIntoWorklist((*it)->getSrcID());
539 }
540 }
541}
542
547{
548 for (ConstraintGraph::const_iterator nodeIt = consCG->begin(), nodeEit = consCG->end(); nodeIt != nodeEit; nodeIt++)
549 {
550 ConstraintNode * cgNode = nodeIt->second;
551 for (ConstraintNode::const_iterator it = cgNode->incomingAddrsBegin(), eit = cgNode->incomingAddrsEnd();
552 it != eit; ++it)
554 }
555}
556
561{
563
564 NodeID dst = addr->getDstID();
565 NodeID src = addr->getSrcID();
566 if(addPts(dst,src))
567 pushIntoWorklist(dst);
568}
569
576{
580// if (pag->isBlkObjOrConstantObj(node))
581 if (pag->isConstantObj(node) || pag->getSVFVar(load->getDstID())->isPointer() == false)
582 return false;
583
585
586 NodeID dst = load->getDstID();
587 return addCopyEdge(node, dst);
588}
589
596{
600// if (pag->isBlkObjOrConstantObj(node))
601 if (pag->isConstantObj(node) || pag->getSVFVar(store->getSrcID())->isPointer() == false)
602 return false;
603
605
606 NodeID src = store->getSrcID();
607 return addCopyEdge(src, node);
608}
609
616{
618
619 assert((SVFUtil::isa<CopyCGEdge>(edge)) && "not copy/call/ret ??");
620 NodeID dst = edge->getDstID();
621 const PointsTo& srcPts = getDiffPts(node);
622
623 bool changed = unionPts(dst, srcPts);
624 if (changed)
625 pushIntoWorklist(dst);
626 return changed;
627}
628
636{
637 const PointsTo& srcPts = getDiffPts(edge->getSrcID());
638 return processGepPts(srcPts, edge);
639}
640
644bool Andersen::processGepPts(const PointsTo& pts, const GepCGEdge* edge)
645{
647
648 PointsTo tmpDstPts;
650 {
651 // If a pointer is connected by a variant gep edge,
652 // then set this memory object to be field insensitive,
653 // unless the object is a black hole/constant.
654 for (NodeID o : pts)
655 {
656 if (consCG->isBlkObjOrConstantObj(o))
657 {
658 tmpDstPts.set(o);
659 continue;
660 }
661
662 if (!isFieldInsensitive(o))
663 {
665 consCG->addNodeToBeCollapsed(consCG->getBaseObjVarID(o));
666 }
667
668 // Add the field-insensitive node into pts.
669 NodeID baseId = consCG->getFIObjVar(o);
670 tmpDstPts.set(baseId);
671 }
672 }
673 else if (const NormalGepCGEdge* normalGepEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
674 {
675 // TODO: after the node is set to field insensitive, handling invariant
676 // gep edge may lose precision because offsets here are ignored, and the
677 // base object is always returned.
678 for (NodeID o : pts)
679 {
680 if (consCG->isBlkObjOrConstantObj(o) || isFieldInsensitive(o))
681 {
682 tmpDstPts.set(o);
683 continue;
684 }
685
686 NodeID fieldSrcPtdNode = consCG->getGepObjVar(o, normalGepEdge->getAccessPath().getConstantStructFldIdx());
687 tmpDstPts.set(fieldSrcPtdNode);
688 }
689 }
690 else
691 {
692 assert(false && "Andersen::processGepPts: New type GEP edge type?");
693 }
694
695 NodeID dstId = edge->getDstID();
696 if (unionPts(dstId, tmpDstPts))
697 {
698 pushIntoWorklist(dstId);
699 return true;
700 }
701
702 return false;
703}
704
709{
710 // If a node is a PWC node, collapse all its points-to target.
711 // collapseNodePts() may change the points-to set of the nodes which have been processed
712 // before, in this case, we may need to re-do the analysis.
713 if (consCG->isPWCNode(nodeId) && collapseNodePts(nodeId))
714 reanalyze = true;
715}
716
718{
719 while (consCG->hasNodesToBeCollapsed())
720 {
721 NodeID node = consCG->getNextCollapseNode();
722 // collapseField() may change the points-to set of the nodes which have been processed
723 // before, in this case, we may need to re-do the analysis.
724 if (collapseField(node))
725 reanalyze = true;
726 }
727}
728
729/*
730 * Merge constraint graph nodes based on SCC cycle detected.
731 */
733{
734 NodeStack topoOrder = getSCCDetector()->topoNodeStack();
735
736 while (!topoOrder.empty())
737 {
738 NodeID repNodeId = topoOrder.top();
739 topoOrder.pop();
740 const NodeBS& subNodes = getSCCDetector()->subNodes(repNodeId);
741 // merge sub nodes to rep node
742 mergeSccNodes(repNodeId, subNodes);
743 if (subNodes.count() > 1)
744 {
745 pushIntoWorklist(repNodeId);
746 reanalyze = true;
747 }
748 }
749}
750
751
756void Andersen::mergeSccNodes(NodeID repNodeId, const NodeBS& subNodes)
757{
758 for (NodeBS::iterator nodeIt = subNodes.begin(); nodeIt != subNodes.end(); nodeIt++)
759 {
760 NodeID subNodeId = *nodeIt;
761 if (subNodeId != repNodeId)
762 {
763 mergeNodeToRep(subNodeId, repNodeId);
764 }
765 }
766}
767
772{
773 bool changed = false;
774 const PointsTo& nodePts = getPts(nodeId);
776 PointsTo ptsClone = nodePts;
777 for (PointsTo::iterator ptsIt = ptsClone.begin(), ptsEit = ptsClone.end(); ptsIt != ptsEit; ptsIt++)
778 {
779 if (isFieldInsensitive(*ptsIt))
780 continue;
781
782 if (collapseField(*ptsIt))
783 changed = true;
784 }
785 return changed;
786}
787
792{
797 if (consCG->isBlkObjOrConstantObj(nodeId))
798 return false;
799
800 bool changed = false;
801
802 double start = stat->getClk();
803
804 // set base node field-insensitive.
806
807 // replace all occurrences of each field with the field-insensitive node
808 NodeID baseId = consCG->getFIObjVar(nodeId);
809 NodeID baseRepNodeId = consCG->sccRepNode(baseId);
810 NodeBS & allFields = consCG->getAllFieldsObjVars(baseId);
811 for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end(); fieldIt != fieldEit; fieldIt++)
812 {
813 NodeID fieldId = *fieldIt;
814 if (fieldId != baseId)
815 {
816 // use the reverse pts of this field node to find all pointers point to it
817 const NodeSet revPts = getRevPts(fieldId);
818 for (const NodeID o : revPts)
819 {
820 // change the points-to target from field to base node
821 clearPts(o, fieldId);
822 addPts(o, baseId);
824
825 changed = true;
826 }
827 // merge field node into base node, including edges and pts.
828 NodeID fieldRepNodeId = consCG->sccRepNode(fieldId);
829 mergeNodeToRep(fieldRepNodeId, baseRepNodeId);
830 if (fieldId != baseRepNodeId)
831 {
832 // gep node fieldId becomes redundant if it is merged to its base node who is set as field-insensitive
833 // two node IDs should be different otherwise this field is actually the base and should not be removed.
834 redundantGepNodes.set(fieldId);
835 }
836 }
837 }
838
839 if (consCG->isPWCNode(baseRepNodeId))
840 if (collapseNodePts(baseRepNodeId))
841 changed = true;
842
843 double end = stat->getClk();
844 timeOfCollapse += (end - start) / TIMEINTERVAL;
845
846 return changed;
847}
848
853{
855
856 double sccStart = stat->getClk();
858 double sccEnd = stat->getClk();
859
860 timeOfSCCDetection += (sccEnd - sccStart)/TIMEINTERVAL;
861
862 double mergeStart = stat->getClk();
863
865
866 double mergeEnd = stat->getClk();
867
868 timeOfSCCMerges += (mergeEnd - mergeStart)/TIMEINTERVAL;
869
870 return getSCCDetector()->topoNodeStack();
871}
872
877{
878
879 if(nodeId==newRepId)
880 return false;
881
883 updatePropaPts(newRepId, nodeId);
884 unionPts(newRepId,nodeId);
885
887 ConstraintNode* node = consCG->getConstraintNode(nodeId);
888 bool pwc = consCG->moveEdgesToRepNode(node, consCG->getConstraintNode(newRepId));
889
894 if(node->isPWCNode())
895 pwc = true;
896
898 updateNodeRepAndSubs(node->getId(),newRepId);
899
900 consCG->removeConstraintNode(node);
901
902 return pwc;
903}
904/*
905 * Merge a node to its rep node based on SCC detection
906 */
908{
909
910 if (mergeSrcToTgt(nodeId,newRepId))
911 consCG->setPWCNode(newRepId);
912}
913
914/*
915 * Updates subnodes of its rep, and rep node of its subs
916 */
918{
919 consCG->setRep(nodeId,newRepId);
920 NodeBS repSubs;
921 repSubs.set(nodeId);
923 // update nodeToSubsMap, union its subs with its rep Subs
924 NodeBS& nodeSubs = consCG->sccSubNodes(nodeId);
925 for(NodeBS::iterator sit = nodeSubs.begin(), esit = nodeSubs.end(); sit!=esit; ++sit)
926 {
927 NodeID subId = *sit;
928 consCG->setRep(subId,newRepId);
929 }
930 repSubs |= nodeSubs;
931 consCG->setSubs(newRepId,repSubs);
932 consCG->resetSubs(nodeId);
933}
934
939{
940 // Reuse this expansion for the index lookup and, when necessary, every
941 // comparison in the exhaustive fallback.
942 PointsTo expandedPts;
943 expandFIObjs(getPts(node), expandedPts);
944 if (auto aliases = collectMayAliasesFromIndex(expandedPts))
945 return std::move(*aliases);
946
947 NodeBS aliases;
948 const bool queryPointsToBlackHole = containBlackHoleNode(expandedPts);
949 for (SVFIR::iterator it = pag->begin(), eit = pag->end(); it != eit; ++it)
950 {
951 const NodeID candidate = it->first;
952 if (queryPointsToBlackHole)
953 {
954 aliases.set(candidate);
955 continue;
956 }
957
958 PointsTo candidatePts;
959 expandFIObjs(getPts(candidate), candidatePts);
960 if (containBlackHoleNode(candidatePts) ||
961 expandedPts.intersects(candidatePts))
962 aliases.set(candidate);
963 }
964 return aliases;
965}
966
972std::vector<NodeBS> Andersen::getMayAliasesBatch(const std::vector<NodeID>& nodes)
973{
974 std::vector<NodeBS> results;
975 results.reserve(nodes.size());
976 Map<PointsTo, NodeBS> answers;
977 size_t cachedMembers = 0;
978 // Bound the reuse cache separately from the caller-owned results.
979 constexpr size_t maxCachedSets = 256;
980 constexpr size_t maxCachedMembers = 1 << 20;
981 for (NodeID node : nodes)
982 {
983 const PointsTo& pts = getPts(node);
984 auto cached = answers.find(pts);
985 if (cached != answers.end())
986 {
987 results.push_back(cached->second);
988 continue;
989 }
990
991 NodeBS aliases = getMayAliases(node);
992 const size_t members = static_cast<size_t>(pts.count()) + aliases.count();
993 if (members > maxCachedMembers)
994 {
995 results.push_back(std::move(aliases));
996 continue;
997 }
998 if (answers.size() == maxCachedSets || cachedMembers > maxCachedMembers - members)
999 {
1000 answers.clear();
1001 cachedMembers = 0;
1002 }
1003 auto inserted = answers.emplace(pts, std::move(aliases));
1004 cachedMembers += members;
1005 results.push_back(inserted.first->second);
1006 }
1007 return results;
1008}
1009
1023std::optional<NodeBS> Andersen::collectMayAliasesFromIndex(const PointsTo& expandedPts)
1024{
1025 if (!getPTDataTy()->hasReversePts() || containBlackHoleNode(expandedPts))
1026 return std::nullopt;
1027
1028 NodeBS objects;
1029 const u32_t nodeBound = pag->getTotalNodeNum();
1030 for (NodeID object : expandedPts)
1031 {
1032 objects.set(object);
1033 const NodeID base = pag->getBaseObjVarID(object);
1034 objects.set(base);
1035 if (isFieldInsensitive(base))
1036 objects |= pag->getAllFieldsObjVars(base);
1037 }
1038 objects.set(pag->getBlackHoleNode());
1039
1040 const size_t wordCount = (static_cast<size_t>(nodeBound) +
1042 CoreBitVector representatives(wordCount);
1043 for (NodeID object : objects)
1044 {
1045 for (NodeID key : getRevPts(object))
1046 {
1047 const NodeID representative = sccRepNode(key);
1048 // Reverse points-to sets can retain stale postings. Confirm the
1049 // posting with one current-set bit test before treating it as an
1050 // alias witness, unless an earlier object already confirmed it.
1051 if (!representatives.test(representative) &&
1052 getPts(representative).test(object))
1053 representatives.set(representative);
1054 }
1055 }
1056
1057 // SCC subnode sets are individually ordered, but their concatenation is
1058 // not globally ordered. Collect them densely before inserting into the
1059 // sparse result, where backward insertions would be costly.
1060 CoreBitVector answer(wordCount);
1061 for (NodeID representative : representatives)
1062 {
1063 for (NodeID subNode : sccSubNodes(representative))
1064 answer.set(subNode);
1065 }
1066
1067 // normalizePointsTo can remove field nodes while their ids remain in
1068 // points-to sets. Do not return those stale nodes.
1069 NodeBS aliases;
1070 for (NodeID id : answer)
1071 {
1072 if (pag->hasGNode(id))
1073 aliases.set(id);
1074 }
1075 return aliases;
1076}
1077
1083{
1085
1086 PointerAnalysis* pta = this;
1087 const FunObjVar* checkFun = pag->getFunObjVar(fun);
1088 if (!checkFun)
1089 return;
1090 for (const CallICFGNode* callNode : pag->getCallSiteSet())
1091 {
1092 if (callNode->getCalledFunction() != checkFun)
1093 continue;
1094 std::vector<NodeID> queries;
1095 for (u32_t i = 0; i < callNode->arg_size(); ++i)
1096 queries.push_back(callNode->getArgument(i)->getId());
1097 const std::vector<NodeBS> aliases = getMayAliasesBatch(queries);
1098 assert(aliases.size() == queries.size() && "getMayAliasesBatch result count mismatch!");
1099 for (size_t i = 0; i < queries.size(); ++i)
1100 {
1101 const NodeID ptr = queries[i];
1102 NodeBS expected;
1103 for (SVFIR::iterator it = pag->begin(), eit = pag->end(); it != eit; ++it)
1104 {
1105 if (mayAlias(ptr, it->first))
1106 expected.set(it->first);
1107 }
1108 if (aliases[i] == expected && pta->getMayAliases(ptr) == expected)
1109 outs() << sucMsg("\t SUCCESS :") << "getMayAliases check <id:" << ptr << "> at ("
1110 << callNode->getSourceLoc() << ")\n";
1111 else
1112 {
1113 SVFUtil::errs() << errMsg("\t FAILURE :") << "getMayAliases check <id:" << ptr
1114 << "> at (" << callNode->getSourceLoc() << ")\n";
1115 assert(false && "getMayAliases disagrees with mayAlias!");
1116 }
1117 }
1118 }
1119}
1120
1121void Andersen::cluster(void) const
1122{
1123 assert(Options::MaxFieldLimit() == 0 && "Andersen::cluster: clustering for Andersen's is currently only supported in field-insensitive analysis");
1125 std::vector<std::pair<unsigned, unsigned>> keys;
1126 for (SVFIR::iterator pit = pag->begin(); pit != pag->end(); ++pit)
1127 {
1128 keys.push_back(std::make_pair(pit->first, 1));
1129 }
1130
1131 std::vector<std::pair<hclust_fast_methods, std::vector<NodeID>>> candidates;
1132 PointsTo::MappingPtr nodeMapping =
1133 std::make_shared<std::vector<NodeID>>(
1134 NodeIDAllocator::Clusterer::cluster(steens, keys, candidates, "aux-steens", print_stat)
1135 );
1136 PointsTo::MappingPtr reverseNodeMapping =
1137 std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::getReverseNodeMapping(*nodeMapping));
1138
1139 PointsTo::setCurrentBestNodeMapping(nodeMapping, reverseNodeMapping);
1140}
1141
1146{
1147 for (OrderedNodeSet::iterator nIter = this->getAllValidPtrs().begin();
1148 nIter != this->getAllValidPtrs().end(); ++nIter)
1149 {
1150 const SVFVar* node = getPAG()->getSVFVar(*nIter);
1151 if (getPAG()->isValidTopLevelPtr(node))
1152 {
1153 const PointsTo& pts = this->getPts(node->getId());
1154 outs() << "\nNodeID " << node->getId() << " ";
1155
1156 if (pts.empty())
1157 {
1158 outs() << "\t\tPointsTo: {empty}\n";
1159 }
1160 else
1161 {
1162 outs() << "\t\tPointsTo: { ";
1163
1164 multiset<u32_t> line;
1165 for (PointsTo::iterator it = pts.begin(), eit = pts.end();
1166 it != eit; ++it)
1167 {
1168 line.insert(*it);
1169 }
1170 for (multiset<u32_t>::const_iterator it = line.begin(); it != line.end(); ++it)
1171 {
1173 if (auto gepNode = pag->getGepObjVar(*it))
1174 outs() << gepNode->getBaseNode() << "_" << gepNode->getConstantFieldIdx() << " ";
1175 else
1176 outs() << *it << " ";
1177 else
1178 outs() << *it << " ";
1179 }
1180 outs() << "}\n";
1181 }
1182 }
1183 }
1184
1185 outs().flush();
1186}
unsigned u32_t
Definition CommandLine.h:18
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:576
#define TIMEINTERVAL
Definition SVFType.h:604
#define DGENERAL
Definition SVFType.h:582
#define DPAGBuild
Definition SVFType.h:584
#define DAndersen
Definition SVFType.h:595
cJSON * n
Definition cJSON.cpp:2558
static double timeOfSCCMerges
Definition Andersen.h:170
static u32_t numOfProcessedCopy
Number of processed Addr edge.
Definition Andersen.h:161
NodeBS & sccSubNodes(NodeID repId)
Definition Andersen.h:136
static u32_t numOfSCCDetection
Definition Andersen.h:168
static u32_t numOfSfrs
Number of processed Store edge.
Definition Andersen.h:165
void heapAllocatorViaIndCall(const CallICFGNode *cs, NodePairSet &cpySrcNodes)
Definition Andersen.cpp:387
virtual void finalize() override
Finalize analysis.
Definition Andersen.cpp:98
static double timeOfUpdateCallGraph
Definition Andersen.h:176
static u32_t numOfProcessedStore
Number of processed Load edge.
Definition Andersen.h:164
virtual void connectCaller2ForkedFunParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect forksites.
Definition Andersen.cpp:264
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
virtual bool updateCallGraph(const CallSiteToFunPtrMap &) override
Update call graph.
Definition Andersen.cpp:210
void printStat()
dump statistics
Definition Andersen.h:146
CallSite2DummyValPN callsite2DummyValPN
Definition Andersen.h:183
virtual void readPtsFromFile(const std::string &filename)
Definition Andersen.cpp:174
static u32_t numOfProcessedLoad
Number of processed Gep edge.
Definition Andersen.h:163
static double timeOfSCCDetection
Definition Andersen.h:169
NodeBS redundantGepNodes
Definition Andersen.h:156
virtual bool addCopyEdge(NodeID src, NodeID dst)=0
Add copy edge on constraint graph.
virtual void initialize() override
Initialize analysis.
Definition Andersen.cpp:82
~AndersenBase() override
Destructor.
Definition Andersen.cpp:73
virtual void analyze() override
Andersen analysis.
Definition Andersen.cpp:150
static u32_t numOfFieldExpand
Definition Andersen.h:166
static double timeOfProcessLoadStore
Definition Andersen.h:175
static u32_t numOfProcessedGep
Number of processed Copy edge.
Definition Andersen.h:162
static double timeOfProcessCopyGep
Definition Andersen.h:174
static u32_t MaxPointsToSetSize
Definition Andersen.h:173
virtual void solveConstraints()
Definition Andersen.cpp:109
virtual bool updateThreadCallGraph(const CallSiteToFunPtrMap &, NodePairSet &)
Update thread call graph.
Definition Andersen.cpp:244
static double timeOfCollapse
Definition Andersen.h:171
static u32_t AveragePointsToSetSize
Definition Andersen.h:172
virtual void solveAndwritePtsToFile(const std::string &filename)
Definition Andersen.cpp:185
ConstraintGraph * consCG
Constraint Graph.
Definition Andersen.h:181
void cleanConsCG(NodeID id)
remove redundant gepnodes in constraint graph
Definition Andersen.cpp:197
virtual void normalizePointsTo() override
Definition Andersen.cpp:414
NodeID sccRepNode(NodeID id) const override
SCC methods.
Definition Andersen.h:132
virtual void handleLoadStore(ConstraintNode *node)
Definition Andersen.cpp:518
virtual NodeBS getMayAliases(NodeID node)
Collect exactly the SVFIR nodes q for which mayAlias(node, q) holds.
Definition Andersen.cpp:938
void mergeSccNodes(NodeID repNodeId, const NodeBS &subNodes)
Merge sub node in a SCC cycle to their rep node.
Definition Andersen.cpp:756
virtual void processNode(NodeID nodeId)
Override WPASolver function in order to use the default solver.
Definition Andersen.cpp:477
virtual void initialize()
Initialize analysis.
Definition Andersen.cpp:438
virtual NodeStack & SCCDetect()
SCC detection.
Definition Andersen.cpp:852
virtual void mergeNodeToRep(NodeID nodeId, NodeID newRepId)
Merge sub node to its rep.
Definition Andersen.cpp:907
bool collapseNodePts(NodeID nodeId)
Definition Andersen.cpp:771
void dumpTopLevelPtsTo()
void updatePropaPts(NodeID dstId, NodeID srcId)
Handle propagated points-to set.
Definition Andersen.h:301
std::optional< NodeBS > collectMayAliasesFromIndex(const PointsTo &expandedPts)
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
void resetData()
Reset data.
Definition Andersen.h:218
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 unionPts(NodeID id, const PointsTo &target)
Definition Andersen.h:246
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
virtual bool processGepPts(const PointsTo &pts, const GepCGEdge *edge)
Definition Andersen.cpp:644
void mergeSccCycle()
Definition Andersen.cpp:732
virtual void processAddr(const AddrCGEdge *addr)
Definition Andersen.cpp:560
void updateNodeRepAndSubs(NodeID nodeId, NodeID newRepId)
Updates subnodes of its rep, and rep node of its subs.
Definition Andersen.cpp:917
virtual void finalize()
Finalize analysis.
Definition Andersen.cpp:452
void processAllAddr()
handling various constraints
Definition Andersen.cpp:546
virtual void cluster(void) const
virtual bool mergeSrcToTgt(NodeID srcId, NodeID tgtId)
Definition Andersen.cpp:876
virtual void collapsePWCNode(NodeID nodeId)
Collapse a field object into its base for field insensitive analysis.
Definition Andersen.cpp:708
virtual void validateSuccessTests(std::string fun)
Also check getMayAliases on the pointers that the alias tests use.
std::vector< NodeBS > getMayAliasesBatch(const std::vector< NodeID > &nodes)
Definition Andersen.cpp:972
bool collapseField(NodeID nodeId)
Definition Andersen.cpp:791
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)
const NodeSet & getRevPts(NodeID nodeId) override
virtual void clearPts(NodeID id, NodeID element)
Remove element from the points-to set of id.
void finalize() override
Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.
bool mayAlias(const PointsTo &pts1, const PointsTo &pts2)
Convenience bool wrappers: return true if the two operands may/must/partial alias.
virtual void expandFIObjs(const PointsTo &pts, PointsTo &expandedPts)
Expand FI objects.
virtual void onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap &callsites, CallEdgeMap &newForkEdges)
On the fly thread call graph construction respecting forksite.
virtual void onTheFlyCallGraphSolve(const CallSiteToFunPtrMap &callsites, CallEdgeMap &newEdges)
On the fly call graph construction.
PTData< NodeID, NodeSet, NodeID, PointsTo > PTDataTy
PTDataTy * getPTDataTy() const
Get points-to data structure.
virtual bool addPts(NodeID id, NodeID ptd)
const FunObjVar * getCalledFunction() const
Definition ICFGNode.h:501
const RetICFGNode * getRetICFGNode() const
Return callsite.
Definition ICFGNode.h:440
const std::string getSourceLoc() const override
Definition ICFGNode.h:571
bool isPWCNode() const
Whether a node involves in PWC, if so, all its points-to elements should become field-insensitive.
Definition ConsGNode.h:81
const_iterator outgoingLoadsEnd() const
Definition ConsGNode.h:194
const_iterator incomingAddrsBegin() const
Definition ConsGNode.h:181
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 incomingAddrsEnd() const
Definition ConsGNode.h:185
const_iterator outgoingLoadsBegin() const
Definition ConsGNode.h:190
void set(u32_t bit)
Sets bit in the CBV.
static const size_t WordSize
bool test(u32_t bit) const
Returns true if bit is set in this CBV.
bool isVarArg() const
NodeID getDstID() const
NodeID getSrcID() const
get methods of the components
IDToNodeMapTy::iterator iterator
APOffset getConstantFieldIdx() const
offset of the mem object
static std::vector< NodeID > getReverseNodeMapping(const std::vector< NodeID > &nodeMapping)
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="", bool printStat=true)
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 const Option< u32_t > AnderTimeLimit
Time limit for the Andersen's analyses.
Definition Options.h:71
static const Option< bool > PrintFieldWithBasePrefix
Definition Options.h:116
static const Option< std::string > ReadAnder
Definition Options.h:206
static const Option< bool > ClusterAnder
Whether to stage Andersen's with Steensgaard and cluster based on that data.
Definition Options.h:37
static const Option< u32_t > FsTimeLimit
Time limit for the main phase (i.e., the actual solving) of FS analyses.
Definition Options.h:68
static const Option< bool > PrintCGGraph
Definition Options.h:202
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
Definition Options.h:34
static const Option< std::string > WriteAnder
Definition Options.h:204
static const Option< bool > ConsCGDotGraph
Definition Options.h:200
virtual Map< DataSet, unsigned > getAllPts(bool liveOnly) const =0
virtual NodeBS getMayAliases(NodeID node)
bool isFieldInsensitive(NodeID id) const
bool print_stat
User input flags.
OrderedMap< const CallICFGNode *, FunctionSet > CallEdgeMap
virtual void initialize()
Initialization of a pointer analysis, including building symbol table and SVFIR etc.
bool containBlackHoleNode(const PointsTo &pts)
Determine whether a points-to contains a black hole or constant node.
PTAStat * stat
Statistics.
SVFIR * getPAG() const
OrderedNodeSet & getAllValidPtrs()
Get all Valid Pointers for resolution.
virtual void validateSuccessTests(std::string fun)
const CallSiteToFunPtrMap & getIndirectCallsites() const
Return all indirect callsites.
CallGraph * callgraph
Call graph used for pointer analysis.
void setObjFieldInsensitive(NodeID id)
SVFIR::CallSiteToFunPtrMap CallSiteToFunPtrMap
static SVFIR * pag
SVFIR.
bool empty() const
Returns true if set is empty.
Definition PointsTo.cpp:110
const_iterator end() const
Definition PointsTo.h:133
std::shared_ptr< std::vector< NodeID > > MappingPtr
Definition PointsTo.h:43
static void setCurrentBestNodeMapping(MappingPtr newCurrentBestNodeMapping, MappingPtr newCurrentBestReverseNodeMapping)
Definition PointsTo.cpp:383
u32_t count() const
Returns number of elements.
Definition PointsTo.cpp:123
const_iterator iterator
Definition PointsTo.h:41
void set(u32_t n)
Inserts n in the set.
Definition PointsTo.cpp:169
const_iterator begin() const
Definition PointsTo.h:129
bool intersects(const PointsTo &rhs) const
Returns true if this set and rhs share any elements.
Definition PointsTo.cpp:201
static MappingPtr getCurrentBestNodeMapping()
Definition PointsTo.cpp:373
GNodeStack & topoNodeStack()
Definition SCC.h:130
const NodeBS & subNodes(NodeID n) const
get all subnodes in one scc, if size is empty insert itself into the set
Definition SCC.h:196
std::vector< const ValVar * > ValVarList
Definition SVFIR.h:60
const SVFVar * getSVFVar(NodeID id) const
ObjVar/GepObjVar/BaseObjVar.
Definition SVFIR.h:136
Map< NodeID, NodeBS > MemObjToFieldsMap
Definition SVFIR.h:58
Map< GepOffset, NodeID > OffsetToGepVarMap
Definition SVFIR.h:72
NodeID getId() const
Get ID.
Definition SVFValue.h:158
virtual const SVFType * getType() const
Definition SVFValue.h:169
const std::string valueOnlyToString() const
Definition LLVMUtil.cpp:747
virtual bool isPointer() const
Check if this variable represents a pointer.
virtual const std::string toString() const
Get string representation.
SparseBitVectorIterator iterator
void set(unsigned Idx)
unsigned count() const
iterator begin() const
static Steensgaard * createSteensgaard(SVFIR *_pag)
Create an singleton instance.
Definition Steensgaard.h:36
const SVFVar * getFormalParmOfForkedFun(const FunObjVar *F) const
Return the formal parm of forked function (the first arg in pthread).
const ValVar * getActualParmAtForkSite(const CallICFGNode *inst) const
ThreadAPI * getThreadAPI() const
Thread API.
virtual void pushIntoWorklist(NodeID id)
Definition WPASolver.h:157
void setGraph(ConstraintGraph *g)
Definition WPASolver.h:79
virtual NodeStack & SCCDetect()
Definition WPASolver.h:87
std::string sucMsg(const std::string &msg)
Returns successful message by converting a string into green string output.
Definition SVFUtil.cpp:75
bool isHeapAllocExtFunViaRet(const FunObjVar *fun)
Return true if the call is a heap allocator/reallocator.
Definition SVFUtil.h:284
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
Definition SVFUtil.cpp:121
std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > cast(const Y &Val)
Definition Casting.h:360
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241
void stopAnalysisLimitTimer(void)
Stops analysis timer.
Definition SVFUtil.cpp:383
std::string errMsg(const std::string &msg)
Print error message by converting a string into red string output.
Definition SVFUtil.cpp:98
std::ostream & errs()
Overwrite llvm::errs().
Definition SVFUtil.h:64
void startAnalysisLimitTimer(unsigned timeLimit)
Starts analysis timer. timeLimit must be non-0. Timer must not be already set.
Definition SVFUtil.cpp:364
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
Definition SVFUtil.cpp:88
std::ostream & outs()
Overwrite llvm::outs().
Definition SVFUtil.h:58
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
s64_t APOffset
Definition GeneralType.h:80
SVFVar PAGNode
Definition IRGraph.h:40
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
Definition GeneralType.h:56
SparseBitVector NodeBS
Definition GeneralType.h:82
iter_range< typename GenericGraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Set< NodePair > NodePairSet
Definition GeneralType.h:88
unsigned u32_t
Definition GeneralType.h:67