Static Value-Flow Analysis
Loading...
Searching...
No Matches
ThreadCallGraph.cpp
Go to the documentation of this file.
1//===- ThreadCallGraph.cpp -- Call graph considering thread fork/join---------//
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 * ThreadCallGraph.cpp
25 *
26 * Created on: Jul 12, 2014
27 * Author: Yulei Sui, Peng Di, Ding Ye
28 */
29
31#include "Util/ThreadAPI.h"
32#include "Graphs/PAG.h"
34#include "Graphs/CallGraph.h"
35
36using namespace SVF;
37using namespace SVFUtil;
38
44{
46 DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Building ThreadCallGraph\n"));
47}
48
50{
51 for (const auto& entry : callinstToThreadJoinEdgesMap)
52 for (ThreadJoinEdge* edge : entry.second)
53 delete edge;
54}
55
56const std::string ThreadForkEdge::toString() const
57{
58 std::string str;
59 std::stringstream rawstr(str);
60 rawstr << "ThreadForkEdge ";
61 rawstr << "CallSiteID: " << getCallSiteID();
62 rawstr << " srcNodeID " << getSrcID() << " (fun: " << getSrcNode()->getFunction()->getName() << ")";
63 rawstr << " dstNodeID " << getDstID() << " (fun: " << getDstNode()->getFunction()->getName() << ")";
64 return rawstr.str();
65}
66
67const std::string ThreadJoinEdge::toString() const
68{
69 std::string str;
70 std::stringstream rawstr(str);
71 rawstr << "ThreadJoinEdge ";
72 rawstr << "CallSiteID: " << getCallSiteID();
73 rawstr << " srcNodeID " << getSrcID() << " (fun: " << getSrcNode()->getFunction()->getName() << ")";
74 rawstr << " dstNodeID " << getDstID() << " (fun: " << getDstNode()->getFunction()->getName() << ")";
75 return rawstr.str();
76}
77
78/*
79 * Update call graph using pointer analysis results
80 * (1) resolve function pointers for non-fork calls
81 * (2) resolve function pointers for fork sites
82 * (3) resolve function pointers for parallel_for sites
83 */
85{
86
87 PointerAnalysis::CallEdgeMap::const_iterator iter = pta->getIndCallMap().begin();
88 PointerAnalysis::CallEdgeMap::const_iterator eiter = pta->getIndCallMap().end();
89 for (; iter != eiter; iter++)
90 {
91 const CallICFGNode* cs = iter->first;
92 const CallGraph::FunctionSet &functions = iter->second;
93 for (CallGraph::FunctionSet::const_iterator func_iter =
94 functions.begin(); func_iter != functions.end(); func_iter++)
95 {
96 const FunObjVar* callee = *func_iter;
97 this->addIndirectCallGraphEdge(cs, cs->getCaller(), callee);
98 }
99 }
100
101 // Fork sites
102 for (CallSiteSet::const_iterator it = forksitesBegin(), eit = forksitesEnd(); it != eit; ++it)
103 {
104 const ValVar* forkedval = tdAPI->getForkedFun(*it);
105 if(SVFUtil::dyn_cast<FunValVar>(forkedval)==nullptr)
106 {
107 PAG* pag = pta->getPAG();
108 const NodeBS targets = pta->getPts(forkedval->getId()).toNodeBS();
109 for (NodeBS::iterator ii = targets.begin(), ie = targets.end(); ii != ie; ii++)
110 {
111 if(const ObjVar* objPN = pag->getObjVar(*ii))
112 {
113 const BaseObjVar* obj = pag->getBaseObject(objPN->getId());
114 if(obj->isFunction())
115 {
116 const FunObjVar* svfCallee = SVFUtil::cast<FunObjVar>(obj)->getFunction();
117 this->addIndirectForkEdge(*it, svfCallee);
118 }
119 }
120 }
121 }
122 }
123}
124
125
130{
132
133 for (CallSiteSet::const_iterator it = joinsitesBegin(), eit = joinsitesEnd(); it != eit; ++it)
134 {
135 const SVFVar* jointhread = tdAPI->getJoinedThread(*it);
136 // find its corresponding fork sites first
137 CallSiteSet forkset;
138 for (CallSiteSet::const_iterator it = forksitesBegin(), eit = forksitesEnd(); it != eit; ++it)
139 {
140 const SVFVar* forkthread = tdAPI->getForkedThread(*it);
141 if (tdAPI->isAliasedForkJoin(pta, forkthread, jointhread, aliasCache))
142 {
143 forkset.insert(*it);
144 }
145 }
149 if (forkset.empty())
150 continue;
151 addDirectJoinEdge(*it,forkset);
152 }
153}
154
159{
160
162 const FunValVar* funValvar = SVFUtil::dyn_cast<FunValVar>(tdAPI->getForkedFun(cs));
163 const FunObjVar* forkee = funValvar->getFunction();
164 assert(forkee && "callee does not exist");
166 CallSiteID csId = addCallSite(cs, callee->getFunction());
167
168 if (!hasGraphEdge(caller, callee, CallGraphEdge::TDForkEdge, csId))
169 {
170 assert(cs->getCaller() == caller->getFunction() && "callee instruction not inside caller??");
171
172 ThreadForkEdge* edge = new ThreadForkEdge(caller, callee, csId);
173 edge->addDirectCallSite(cs);
174
175 addEdge(edge);
176 addThreadForkEdgeSetMap(cs, edge);
177 return true;
178 }
179 else
180 return false;
181}
182
187{
189 CallGraphNode* callee = getCallGraphNode(calleefun);
190
191 CallSiteID csId = addCallSite(cs, callee->getFunction());
192
193 if (!hasGraphEdge(caller, callee, CallGraphEdge::TDForkEdge, csId))
194 {
195 assert(cs->getCaller() == caller->getFunction() && "callee instruction not inside caller??");
196
197 ThreadForkEdge* edge = new ThreadForkEdge(caller, callee, csId);
198 edge->addInDirectCallSite(cs);
199
200 addEdge(edge);
201 addThreadForkEdgeSetMap(cs, edge);
202 return true;
203 }
204 else
205 return false;
206}
207
215{
216
217 CallGraphNode* joinFunNode = getCallGraphNode(cs->getCaller());
218
219 for (CallSiteSet::const_iterator it = forkset.begin(), eit = forkset.end(); it != eit; ++it)
220 {
221 // The start routine(s) joined here are exactly the targets of the fork
222 // edges already resolved for this fork site (direct, or indirect via
223 // points-to in updateCallGraph). Reuse them rather than re-resolving the
224 // fork target from getForkedFun, which is not a FunValVar for an indirect
225 // fork (function pointer). An unresolved fork site simply has no edges.
226 if (!hasThreadForkEdge(*it))
227 continue;
228 for (ForkEdgeSet::const_iterator eit2 = getForkEdgeBegin(*it),
229 eeit2 = getForkEdgeEnd(*it); eit2 != eeit2; ++eit2)
230 {
231 CallGraphNode* threadRoutineFunNode = (*eit2)->getDstNode();
232 CallSiteID csId = addCallSite(cs, threadRoutineFunNode->getFunction());
233
234 if (!hasThreadJoinEdge(cs,joinFunNode,threadRoutineFunNode, csId))
235 {
236 assert(cs->getCaller() == joinFunNode->getFunction() && "callee instruction not inside caller??");
237 ThreadJoinEdge* edge = new ThreadJoinEdge(joinFunNode,threadRoutineFunNode,csId);
238 edge->addDirectCallSite(cs);
239
240 addThreadJoinEdgeSetMap(cs, edge);
241 }
242 }
243 }
244}
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:576
#define DGENERAL
Definition SVFType.h:582
bool isFunction() const
object attributes methods
void addInDirectCallSite(const CallICFGNode *call)
Definition CallGraph.cpp:61
void addDirectCallSite(const CallICFGNode *call)
Add direct and indirect callsite.
Definition CallGraph.cpp:55
CallSiteID getCallSiteID() const
Get direct and indirect calls.
Definition CallGraph.h:83
const FunObjVar * getFunction() const
Get function of this call node.
Definition CallGraph.h:191
void addIndirectCallGraphEdge(const CallICFGNode *cs, const FunObjVar *callerFun, const FunObjVar *calleeFun)
Add indirect call edges.
CallGraphEdge * hasGraphEdge(CallGraphEdge *cgEdge) const
Whether we have already created this call graph edge.
void addEdge(CallGraphEdge *edge)
Add call graph edge.
Definition CallGraph.h:296
const CallGraphNode * getCallGraphNode(const std::string &name) const
Get call graph node.
CallSiteID addCallSite(const CallICFGNode *cs, const FunObjVar *callee)
Add CallSiteID.
Definition CallGraph.h:279
CallGraph(CGEK k=NormCallGraph)
Constructor.
Set< const FunObjVar * > FunctionSet
Definition CallGraph.h:247
const FunObjVar * getCaller() const
Return callsite.
Definition ICFGNode.h:453
virtual const FunObjVar * getFunction() const
Get containing function, or null for globals/constants.
const FunObjVar * getDefFunForMultipleModule() const
virtual const FunObjVar * getFunction() const
Get containing function, or null for globals/constants.
Definition PAG.h:46
const BaseObjVar * getBaseObject(NodeID id) const
Definition PAG.h:499
const ObjVar * getObjVar(NodeID id) const
Definition PAG.h:150
virtual const PointsTo & getPts(NodeID ptr)=0
Get points-to targets of a pointer. It needs to be implemented in child class.
CallEdgeMap & getIndCallMap()
Get callees from an indirect callsite.
NodeBS toNodeBS() const
Returns this points-to set as a NodeBS.
Definition PointsTo.cpp:325
NodeID getId() const
Get ID.
Definition SVFValue.h:158
virtual const std::string & getName() const
Definition SVFValue.h:184
SparseBitVectorIterator iterator
iterator begin() const
CallSiteSet::const_iterator forksitesEnd() const
bool addDirectForkEdge(const CallICFGNode *cs)
Add direct/indirect thread fork edges.
virtual ~ThreadCallGraph()
Destructor.
CallSiteSet::const_iterator forksitesBegin() const
Fork sites iterators.
void updateJoinEdge(PointerAnalysis *pta)
Update join edge using pointer analysis results.
CallSiteSet::const_iterator joinsitesEnd() const
bool hasThreadJoinEdge(const CallICFGNode *cs) const
Get call graph edge via call instruction.
void addThreadJoinEdgeSetMap(const CallICFGNode *cs, ThreadJoinEdge *edge)
map call instruction to its PTACallGraphEdge map
ForkEdgeSet::const_iterator getForkEdgeEnd(const CallICFGNode *cs) const
ForkEdgeSet::const_iterator getForkEdgeBegin(const CallICFGNode *cs) const
void addDirectJoinEdge(const CallICFGNode *cs, const CallSiteSet &forksite)
Add thread join edges.
bool addIndirectForkEdge(const CallICFGNode *cs, const FunObjVar *callee)
bool hasThreadForkEdge(const CallICFGNode *cs) const
Get call graph edge via call instruction.
CallSiteSet::const_iterator joinsitesBegin() const
Join sites iterators.
ThreadAPI * getThreadAPI() const
Thread API.
void addThreadForkEdgeSetMap(const CallICFGNode *cs, ThreadForkEdge *edge)
map call instruction to its PTACallGraphEdge map
void updateCallGraph(PointerAnalysis *pta)
Update call graph using pointer results.
ThreadCallGraph(const CallGraph &cg)
Constructor.
ThreadAPI * tdAPI
Thread API.
CallInstToJoinEdgesMap callinstToThreadJoinEdgesMap
Map a call instruction to its corresponding join edges.
virtual const std::string toString() const
virtual const std::string toString() const
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
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
unsigned CallSiteID
Definition GeneralType.h:78
SparseBitVector NodeBS
Definition GeneralType.h:82
If fork join the same thread.
Definition ThreadAPI.h:158