92 consCG->dump(
"consCG_initial");
102 consCG->dump(
"consCG_final");
177 if (!filename.empty())
189 if (!filename.empty())
192 if (!filename.empty())
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! ");
213 double cgUpdateStart =
stat->getClk();
218 for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end();
221 for (FunctionSet::iterator cit = it->second.begin(),
222 ecit = it->second.end();
231 for (NodePairSet::iterator it = cpySrcNodes.begin(),
232 eit = cpySrcNodes.end();
238 double cgUpdateEnd =
stat->getClk();
241 return ((!newEdges.empty()) || hasNewForkEdges);
249 for (CallEdgeMap::iterator it = newForkEdges.begin(), eit = newForkEdges.end(); it != eit; it++)
251 for (FunctionSet::iterator cit = it->second.begin(),
252 ecit = it->second.end();
258 return !newForkEdges.empty();
286 cpySrcNodes.insert(std::make_pair(srcAA, dstFA));
309 if (
pag->funHasRet(F) &&
pag->callsiteHasRet(retBlockNode))
311 const PAGNode* cs_return =
pag->getCallSiteRet(retBlockNode);
312 const PAGNode* fun_return =
pag->getFunRet(F);
319 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
328 if (
pag->hasCallSiteArgsMap(callBlockNode) &&
pag->hasFunArgsList(F))
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)
341 if (csArgIt == csArgEit)
346 const PAGNode *cs_arg = *csArgIt ;
347 const PAGNode *fun_arg = *funArgIt;
356 cpySrcNodes.insert(std::make_pair(srcAA,dstFA));
366 for (; csArgIt != csArgEit; ++csArgIt)
368 const PAGNode *cs_arg = *csArgIt;
374 cpySrcNodes.insert(std::make_pair(vnAA,vaF));
379 if(csArgIt != csArgEit)
391 const PAGNode* cs_return =
pag->getCallSiteRet(retBlockNode);
411 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
425 assert(gepNode &&
"Not a gep node in redundantGepNodes set");
427 GepObjVarMap.erase(std::make_pair(base, apOffset));
428 memToFieldsMap[base].reset(
n);
484 double insertStart =
stat->getClk();
486 double insertEnd =
stat->getClk();
489 double propStart =
stat->getClk();
491 double propEnd =
stat->getClk();
522 getPts(nodeId).end(); piter != epiter; ++piter)
581 if (
pag->isConstantObj(node) ||
pag->getSVFVar(load->
getDstID())->isPointer() ==
false)
601 if (
pag->isConstantObj(node) ||
pag->getSVFVar(store->
getSrcID())->isPointer() ==
false)
623 bool changed =
unionPts(dst, srcPts);
656 if (
consCG->isBlkObjOrConstantObj(o))
665 consCG->addNodeToBeCollapsed(
consCG->getBaseObjVarID(o));
670 tmpDstPts.
set(baseId);
686 NodeID fieldSrcPtdNode =
consCG->getGepObjVar(o, normalGepEdge->getAccessPath().getConstantStructFldIdx());
687 tmpDstPts.
set(fieldSrcPtdNode);
692 assert(
false &&
"Andersen::processGepPts: New type GEP edge type?");
719 while (
consCG->hasNodesToBeCollapsed())
736 while (!topoOrder.empty())
738 NodeID repNodeId = topoOrder.top();
743 if (subNodes.
count() > 1)
760 NodeID subNodeId = *nodeIt;
761 if (subNodeId != repNodeId)
773 bool changed =
false;
797 if (
consCG->isBlkObjOrConstantObj(nodeId))
800 bool changed =
false;
802 double start =
stat->getClk();
810 NodeBS & allFields =
consCG->getAllFieldsObjVars(baseId);
813 NodeID fieldId = *fieldIt;
814 if (fieldId != baseId)
818 for (
const NodeID o : revPts)
830 if (fieldId != baseRepNodeId)
839 if (
consCG->isPWCNode(baseRepNodeId))
843 double end =
stat->getClk();
856 double sccStart =
stat->getClk();
858 double sccEnd =
stat->getClk();
862 double mergeStart =
stat->getClk();
866 double mergeEnd =
stat->getClk();
888 bool pwc =
consCG->moveEdgesToRepNode(node,
consCG->getConstraintNode(newRepId));
900 consCG->removeConstraintNode(node);
911 consCG->setPWCNode(newRepId);
919 consCG->setRep(nodeId,newRepId);
928 consCG->setRep(subId,newRepId);
931 consCG->setSubs(newRepId,repSubs);
932 consCG->resetSubs(nodeId);
945 return std::move(*aliases);
951 const NodeID candidate = it->first;
952 if (queryPointsToBlackHole)
954 aliases.
set(candidate);
962 aliases.
set(candidate);
974 std::vector<NodeBS> results;
975 results.reserve(
nodes.size());
977 size_t cachedMembers = 0;
979 constexpr size_t maxCachedSets = 256;
980 constexpr size_t maxCachedMembers = 1 << 20;
984 auto cached = answers.find(pts);
985 if (cached != answers.end())
987 results.push_back(cached->second);
992 const size_t members =
static_cast<size_t>(pts.
count()) + aliases.
count();
993 if (members > maxCachedMembers)
995 results.push_back(std::move(aliases));
998 if (answers.size() == maxCachedSets || cachedMembers > maxCachedMembers - members)
1003 auto inserted = answers.emplace(pts, std::move(aliases));
1004 cachedMembers += members;
1005 results.push_back(inserted.first->second);
1026 return std::nullopt;
1029 const u32_t nodeBound =
pag->getTotalNodeNum();
1030 for (
NodeID object : expandedPts)
1032 objects.
set(
object);
1033 const NodeID base =
pag->getBaseObjVarID(
object);
1036 objects |=
pag->getAllFieldsObjVars(base);
1038 objects.
set(
pag->getBlackHoleNode());
1040 const size_t wordCount = (
static_cast<size_t>(nodeBound) +
1043 for (
NodeID object : objects)
1051 if (!representatives.
test(representative) &&
1052 getPts(representative).test(
object))
1053 representatives.
set(representative);
1061 for (
NodeID representative : representatives)
1064 answer.
set(subNode);
1072 if (
pag->hasGNode(
id))
1092 if (callNode->getCalledFunction() != checkFun)
1094 std::vector<NodeID> queries;
1095 for (
u32_t i = 0; i < callNode->arg_size(); ++i)
1096 queries.push_back(callNode->getArgument(i)->getId());
1098 assert(aliases.size() == queries.size() &&
"getMayAliasesBatch result count mismatch!");
1099 for (
size_t i = 0; i < queries.size(); ++i)
1101 const NodeID ptr = queries[i];
1106 expected.
set(it->first);
1108 if (aliases[i] == expected && pta->
getMayAliases(ptr) == expected)
1109 outs() <<
sucMsg(
"\t SUCCESS :") <<
"getMayAliases check <id:" << ptr <<
"> at ("
1110 << callNode->getSourceLoc() <<
")\n";
1114 <<
"> at (" << callNode->getSourceLoc() <<
")\n";
1115 assert(
false &&
"getMayAliases disagrees with mayAlias!");
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;
1128 keys.push_back(std::make_pair(pit->first, 1));
1131 std::vector<std::pair<hclust_fast_methods, std::vector<NodeID>>> candidates;
1133 std::make_shared<std::vector<NodeID>>(
1147 for (OrderedNodeSet::iterator nIter = this->
getAllValidPtrs().begin();
1151 if (
getPAG()->isValidTopLevelPtr(node))
1154 outs() <<
"\nNodeID " << node->
getId() <<
" ";
1158 outs() <<
"\t\tPointsTo: {empty}\n";
1162 outs() <<
"\t\tPointsTo: { ";
1164 multiset<u32_t> line;
1170 for (multiset<u32_t>::const_iterator it = line.begin(); it != line.end(); ++it)
1173 if (
auto gepNode =
pag->getGepObjVar(*it))
1174 outs() << gepNode->getBaseNode() <<
"_" << gepNode->getConstantFieldIdx() <<
" ";
1176 outs() << *it <<
" ";
1178 outs() << *it <<
" ";
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
static double timeOfSCCMerges
static u32_t numOfProcessedCopy
Number of processed Addr edge.
NodeBS & sccSubNodes(NodeID repId)
static u32_t numOfSCCDetection
static u32_t numOfSfrs
Number of processed Store edge.
void heapAllocatorViaIndCall(const CallICFGNode *cs, NodePairSet &cpySrcNodes)
virtual void finalize() override
Finalize analysis.
static double timeOfUpdateCallGraph
static u32_t numOfProcessedStore
Number of processed Load edge.
virtual void connectCaller2ForkedFunParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect forksites.
virtual void connectCaller2CalleeParams(const CallICFGNode *cs, const FunObjVar *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect callsites.
static u32_t numOfProcessedAddr
Statistics.
virtual bool updateCallGraph(const CallSiteToFunPtrMap &) override
Update call graph.
void printStat()
dump statistics
CallSite2DummyValPN callsite2DummyValPN
virtual void readPtsFromFile(const std::string &filename)
static u32_t numOfProcessedLoad
Number of processed Gep edge.
static double timeOfSCCDetection
virtual bool addCopyEdge(NodeID src, NodeID dst)=0
Add copy edge on constraint graph.
virtual void initialize() override
Initialize analysis.
~AndersenBase() override
Destructor.
virtual void analyze() override
Andersen analysis.
static u32_t numOfFieldExpand
static double timeOfProcessLoadStore
static u32_t numOfProcessedGep
Number of processed Copy edge.
static double timeOfProcessCopyGep
static u32_t MaxPointsToSetSize
virtual void solveConstraints()
virtual bool updateThreadCallGraph(const CallSiteToFunPtrMap &, NodePairSet &)
Update thread call graph.
static double timeOfCollapse
static u32_t AveragePointsToSetSize
virtual void solveAndwritePtsToFile(const std::string &filename)
ConstraintGraph * consCG
Constraint Graph.
void cleanConsCG(NodeID id)
remove redundant gepnodes in constraint graph
virtual void normalizePointsTo() override
NodeID sccRepNode(NodeID id) const override
SCC methods.
virtual void handleLoadStore(ConstraintNode *node)
virtual NodeBS getMayAliases(NodeID node)
Collect exactly the SVFIR nodes q for which mayAlias(node, q) holds.
void mergeSccNodes(NodeID repNodeId, const NodeBS &subNodes)
Merge sub node in a SCC cycle to their rep node.
virtual void processNode(NodeID nodeId)
Override WPASolver function in order to use the default solver.
virtual void initialize()
Initialize analysis.
virtual NodeStack & SCCDetect()
SCC detection.
virtual void mergeNodeToRep(NodeID nodeId, NodeID newRepId)
Merge sub node to its rep.
bool collapseNodePts(NodeID nodeId)
void updatePropaPts(NodeID dstId, NodeID srcId)
Handle propagated points-to set.
std::optional< NodeBS > collectMayAliasesFromIndex(const PointsTo &expandedPts)
virtual void computeDiffPts(NodeID id)
Handle diff points-to set.
virtual bool addCopyEdge(NodeID src, NodeID dst)
Add copy edge on constraint graph.
void resetData()
Reset data.
virtual const PointsTo & getDiffPts(NodeID id)
virtual bool processGep(NodeID node, const GepCGEdge *edge)
virtual void handleCopyGep(ConstraintNode *node)
virtual bool unionPts(NodeID id, const PointsTo &target)
virtual bool processLoad(NodeID node, const ConstraintEdge *load)
virtual const PointsTo & getPts(NodeID id)
Operation of points-to set.
void collapseFields()
collapse positive weight cycles of a graph
virtual bool processStore(NodeID node, const ConstraintEdge *load)
virtual bool processCopy(NodeID node, const ConstraintEdge *edge)
virtual bool processGepPts(const PointsTo &pts, const GepCGEdge *edge)
virtual void processAddr(const AddrCGEdge *addr)
void updateNodeRepAndSubs(NodeID nodeId, NodeID newRepId)
Updates subnodes of its rep, and rep node of its subs.
virtual void finalize()
Finalize analysis.
void processAllAddr()
handling various constraints
virtual void cluster(void) const
virtual bool mergeSrcToTgt(NodeID srcId, NodeID tgtId)
virtual void collapsePWCNode(NodeID nodeId)
Collapse a field object into its base for field insensitive analysis.
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)
bool collapseField(NodeID nodeId)
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
const RetICFGNode * getRetICFGNode() const
Return callsite.
const std::string getSourceLoc() const override
bool isPWCNode() const
Whether a node involves in PWC, if so, all its points-to elements should become field-insensitive.
const_iterator outgoingLoadsEnd() const
const_iterator incomingAddrsBegin() const
const ConstraintEdge::ConstraintEdgeSetTy & getGepOutEdges() const
const_iterator incomingStoresBegin() const
const_iterator incomingStoresEnd() const
ConstraintEdge::ConstraintEdgeSetTy::const_iterator const_iterator
const ConstraintEdge::ConstraintEdgeSetTy & getCopyOutEdges() const
const_iterator incomingAddrsEnd() const
const_iterator outgoingLoadsBegin() const
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.
NodeID getSrcID() const
get methods of the components
IDToNodeMapTy::const_iterator const_iterator
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.
static const Option< bool > PrintFieldWithBasePrefix
static const Option< std::string > ReadAnder
static const Option< bool > ClusterAnder
Whether to stage Andersen's with Steensgaard and cluster based on that data.
static const Option< u32_t > FsTimeLimit
Time limit for the main phase (i.e., the actual solving) of FS analyses.
static const Option< bool > PrintCGGraph
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
static const Option< std::string > WriteAnder
static const Option< bool > ConsCGDotGraph
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.
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
bool empty() const
Returns true if set is empty.
const_iterator end() const
std::shared_ptr< std::vector< NodeID > > MappingPtr
static void setCurrentBestNodeMapping(MappingPtr newCurrentBestNodeMapping, MappingPtr newCurrentBestReverseNodeMapping)
u32_t count() const
Returns number of elements.
void set(u32_t n)
Inserts n in the set.
const_iterator begin() const
bool intersects(const PointsTo &rhs) const
Returns true if this set and rhs share any elements.
static MappingPtr getCurrentBestNodeMapping()
GNodeStack & topoNodeStack()
const NodeBS & subNodes(NodeID n) const
get all subnodes in one scc, if size is empty insert itself into the set
std::vector< const ValVar * > ValVarList
const SVFVar * getSVFVar(NodeID id) const
ObjVar/GepObjVar/BaseObjVar.
Map< NodeID, NodeBS > MemObjToFieldsMap
Map< GepOffset, NodeID > OffsetToGepVarMap
NodeID getId() const
Get ID.
virtual const SVFType * getType() const
const std::string valueOnlyToString() const
virtual bool isPointer() const
Check if this variable represents a pointer.
virtual const std::string toString() const
Get string representation.
SparseBitVectorIterator iterator
static Steensgaard * createSteensgaard(SVFIR *_pag)
Create an singleton instance.
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.
SCC * getSCCDetector() const
virtual void pushIntoWorklist(NodeID id)
virtual void initWorklist()
void setGraph(ConstraintGraph *g)
virtual NodeStack & SCCDetect()
u32_t iterationForPrintStat
virtual void solveWorklist()
std::string sucMsg(const std::string &msg)
Returns successful message by converting a string into green string output.
bool isHeapAllocExtFunViaRet(const FunObjVar *fun)
Return true if the call is a heap allocator/reallocator.
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > cast(const Y &Val)
LLVM_NODISCARD bool isa(const Y &Val)
void stopAnalysisLimitTimer(void)
Stops analysis timer.
std::string errMsg(const std::string &msg)
Print error message by converting a string into red string output.
std::ostream & errs()
Overwrite llvm::errs().
void startAnalysisLimitTimer(unsigned timeLimit)
Starts analysis timer. timeLimit must be non-0. Timer must not be already set.
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
std::ostream & outs()
Overwrite llvm::outs().
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
std::stack< NodeID > NodeStack
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
iter_range< typename GenericGraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Set< NodePair > NodePairSet