clang  6.0.0svn
ExplodedGraph.cpp
Go to the documentation of this file.
1 //=-- ExplodedGraph.cpp - Local, Path-Sens. "Exploded Graph" -*- C++ -*------=//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the template classes ExplodedNode and ExplodedGraph,
11 // which represent a path-sensitive, intra-procedural "exploded graph."
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "clang/AST/ParentMap.h"
17 #include "clang/AST/Stmt.h"
20 #include "llvm/ADT/DenseSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 
24 using namespace clang;
25 using namespace ento;
26 
27 //===----------------------------------------------------------------------===//
28 // Node auditing.
29 //===----------------------------------------------------------------------===//
30 
31 // An out of line virtual method to provide a home for the class vtable.
33 
34 #ifndef NDEBUG
36 #endif
37 
39 #ifndef NDEBUG
40  NodeAuditor = A;
41 #endif
42 }
43 
44 //===----------------------------------------------------------------------===//
45 // Cleanup.
46 //===----------------------------------------------------------------------===//
47 
49  : NumNodes(0), ReclaimNodeInterval(0) {}
50 
52 
53 //===----------------------------------------------------------------------===//
54 // Node reclamation.
55 //===----------------------------------------------------------------------===//
56 
58  if (!Ex->isLValue())
59  return false;
60  return isa<DeclRefExpr>(Ex) ||
61  isa<MemberExpr>(Ex) ||
62  isa<ObjCIvarRefExpr>(Ex);
63 }
64 
65 bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
66  // First, we only consider nodes for reclamation of the following
67  // conditions apply:
68  //
69  // (1) 1 predecessor (that has one successor)
70  // (2) 1 successor (that has one predecessor)
71  //
72  // If a node has no successor it is on the "frontier", while a node
73  // with no predecessor is a root.
74  //
75  // After these prerequisites, we discard all "filler" nodes that
76  // are used only for intermediate processing, and are not essential
77  // for analyzer history:
78  //
79  // (a) PreStmtPurgeDeadSymbols
80  //
81  // We then discard all other nodes where *all* of the following conditions
82  // apply:
83  //
84  // (3) The ProgramPoint is for a PostStmt, but not a PostStore.
85  // (4) There is no 'tag' for the ProgramPoint.
86  // (5) The 'store' is the same as the predecessor.
87  // (6) The 'GDM' is the same as the predecessor.
88  // (7) The LocationContext is the same as the predecessor.
89  // (8) Expressions that are *not* lvalue expressions.
90  // (9) The PostStmt isn't for a non-consumed Stmt or Expr.
91  // (10) The successor is neither a CallExpr StmtPoint nor a CallEnter or
92  // PreImplicitCall (so that we would be able to find it when retrying a
93  // call with no inlining).
94  // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well.
95 
96  // Conditions 1 and 2.
97  if (node->pred_size() != 1 || node->succ_size() != 1)
98  return false;
99 
100  const ExplodedNode *pred = *(node->pred_begin());
101  if (pred->succ_size() != 1)
102  return false;
103 
104  const ExplodedNode *succ = *(node->succ_begin());
105  if (succ->pred_size() != 1)
106  return false;
107 
108  // Now reclaim any nodes that are (by definition) not essential to
109  // analysis history and are not consulted by any client code.
110  ProgramPoint progPoint = node->getLocation();
111  if (progPoint.getAs<PreStmtPurgeDeadSymbols>())
112  return !progPoint.getTag();
113 
114  // Condition 3.
115  if (!progPoint.getAs<PostStmt>() || progPoint.getAs<PostStore>())
116  return false;
117 
118  // Condition 4.
119  if (progPoint.getTag())
120  return false;
121 
122  // Conditions 5, 6, and 7.
123  ProgramStateRef state = node->getState();
124  ProgramStateRef pred_state = pred->getState();
125  if (state->store != pred_state->store || state->GDM != pred_state->GDM ||
126  progPoint.getLocationContext() != pred->getLocationContext())
127  return false;
128 
129  // All further checks require expressions. As per #3, we know that we have
130  // a PostStmt.
131  const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt());
132  if (!Ex)
133  return false;
134 
135  // Condition 8.
136  // Do not collect nodes for "interesting" lvalue expressions since they are
137  // used extensively for generating path diagnostics.
138  if (isInterestingLValueExpr(Ex))
139  return false;
140 
141  // Condition 9.
142  // Do not collect nodes for non-consumed Stmt or Expr to ensure precise
143  // diagnostic generation; specifically, so that we could anchor arrows
144  // pointing to the beginning of statements (as written in code).
145  ParentMap &PM = progPoint.getLocationContext()->getParentMap();
146  if (!PM.isConsumedExpr(Ex))
147  return false;
148 
149  // Condition 10.
150  const ProgramPoint SuccLoc = succ->getLocation();
151  if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>())
152  if (CallEvent::isCallStmt(SP->getStmt()))
153  return false;
154 
155  // Condition 10, continuation.
156  if (SuccLoc.getAs<CallEnter>() || SuccLoc.getAs<PreImplicitCall>())
157  return false;
158 
159  return true;
160 }
161 
162 void ExplodedGraph::collectNode(ExplodedNode *node) {
163  // Removing a node means:
164  // (a) changing the predecessors successor to the successor of this node
165  // (b) changing the successors predecessor to the predecessor of this node
166  // (c) Putting 'node' onto freeNodes.
167  assert(node->pred_size() == 1 || node->succ_size() == 1);
168  ExplodedNode *pred = *(node->pred_begin());
169  ExplodedNode *succ = *(node->succ_begin());
170  pred->replaceSuccessor(succ);
171  succ->replacePredecessor(pred);
172  FreeNodes.push_back(node);
173  Nodes.RemoveNode(node);
174  --NumNodes;
175  node->~ExplodedNode();
176 }
177 
179  if (ChangedNodes.empty())
180  return;
181 
182  // Only periodically reclaim nodes so that we can build up a set of
183  // nodes that meet the reclamation criteria. Freshly created nodes
184  // by definition have no successor, and thus cannot be reclaimed (see below).
185  assert(ReclaimCounter > 0);
186  if (--ReclaimCounter != 0)
187  return;
189 
190  for (NodeVector::iterator it = ChangedNodes.begin(), et = ChangedNodes.end();
191  it != et; ++it) {
192  ExplodedNode *node = *it;
193  if (shouldCollect(node))
194  collectNode(node);
195  }
196  ChangedNodes.clear();
197 }
198 
199 //===----------------------------------------------------------------------===//
200 // ExplodedNode.
201 //===----------------------------------------------------------------------===//
202 
203 // An NodeGroup's storage type is actually very much like a TinyPtrVector:
204 // it can be either a pointer to a single ExplodedNode, or a pointer to a
205 // BumpVector allocated with the ExplodedGraph's allocator. This allows the
206 // common case of single-node NodeGroups to be implemented with no extra memory.
207 //
208 // Consequently, each of the NodeGroup methods have up to four cases to handle:
209 // 1. The flag is set and this group does not actually contain any nodes.
210 // 2. The group is empty, in which case the storage value is null.
211 // 3. The group contains a single node.
212 // 4. The group contains more than one node.
214 typedef llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *> GroupStorage;
215 
217  assert (!V->isSink());
218  Preds.addNode(V, G);
219  V->Succs.addNode(this, G);
220 #ifndef NDEBUG
221  if (NodeAuditor) NodeAuditor->AddEdge(V, this);
222 #endif
223 }
224 
225 void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
226  assert(!getFlag());
227 
228  GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
229  assert(Storage.is<ExplodedNode *>());
230  Storage = node;
231  assert(Storage.is<ExplodedNode *>());
232 }
233 
234 void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
235  assert(!getFlag());
236 
237  GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
238  if (Storage.isNull()) {
239  Storage = N;
240  assert(Storage.is<ExplodedNode *>());
241  return;
242  }
243 
244  ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>();
245 
246  if (!V) {
247  // Switch from single-node to multi-node representation.
248  ExplodedNode *Old = Storage.get<ExplodedNode *>();
249 
251  V = G.getAllocator().Allocate<ExplodedNodeVector>();
252  new (V) ExplodedNodeVector(Ctx, 4);
253  V->push_back(Old, Ctx);
254 
255  Storage = V;
256  assert(!getFlag());
257  assert(Storage.is<ExplodedNodeVector *>());
258  }
259 
260  V->push_back(N, G.getNodeAllocator());
261 }
262 
263 unsigned ExplodedNode::NodeGroup::size() const {
264  if (getFlag())
265  return 0;
266 
267  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
268  if (Storage.isNull())
269  return 0;
270  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
271  return V->size();
272  return 1;
273 }
274 
275 ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {
276  if (getFlag())
277  return nullptr;
278 
279  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
280  if (Storage.isNull())
281  return nullptr;
282  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
283  return V->begin();
284  return Storage.getAddrOfPtr1();
285 }
286 
287 ExplodedNode * const *ExplodedNode::NodeGroup::end() const {
288  if (getFlag())
289  return nullptr;
290 
291  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
292  if (Storage.isNull())
293  return nullptr;
294  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
295  return V->end();
296  return Storage.getAddrOfPtr1() + 1;
297 }
298 
301  bool IsSink,
302  bool* IsNew) {
303  // Profile 'State' to determine if we already have an existing node.
304  llvm::FoldingSetNodeID profile;
305  void *InsertPos = nullptr;
306 
307  NodeTy::Profile(profile, L, State, IsSink);
308  NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
309 
310  if (!V) {
311  if (!FreeNodes.empty()) {
312  V = FreeNodes.back();
313  FreeNodes.pop_back();
314  }
315  else {
316  // Allocate a new node.
317  V = (NodeTy*) getAllocator().Allocate<NodeTy>();
318  }
319 
320  new (V) NodeTy(L, State, IsSink);
321 
323  ChangedNodes.push_back(V);
324 
325  // Insert the node into the node set and return it.
326  Nodes.InsertNode(V, InsertPos);
327  ++NumNodes;
328 
329  if (IsNew) *IsNew = true;
330  }
331  else
332  if (IsNew) *IsNew = false;
333 
334  return V;
335 }
336 
339  bool IsSink) {
340  NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
341  new (V) NodeTy(L, State, IsSink);
342  return V;
343 }
344 
345 std::unique_ptr<ExplodedGraph>
347  InterExplodedGraphMap *ForwardMap,
348  InterExplodedGraphMap *InverseMap) const {
349 
350  if (Nodes.empty())
351  return nullptr;
352 
353  typedef llvm::DenseSet<const ExplodedNode*> Pass1Ty;
354  Pass1Ty Pass1;
355 
356  typedef InterExplodedGraphMap Pass2Ty;
357  InterExplodedGraphMap Pass2Scratch;
358  Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
359 
361 
362  // ===- Pass 1 (reverse DFS) -===
363  for (ArrayRef<const NodeTy *>::iterator I = Sinks.begin(), E = Sinks.end();
364  I != E; ++I) {
365  if (*I)
366  WL1.push_back(*I);
367  }
368 
369  // Process the first worklist until it is empty.
370  while (!WL1.empty()) {
371  const ExplodedNode *N = WL1.pop_back_val();
372 
373  // Have we already visited this node? If so, continue to the next one.
374  if (!Pass1.insert(N).second)
375  continue;
376 
377  // If this is a root enqueue it to the second worklist.
378  if (N->Preds.empty()) {
379  WL2.push_back(N);
380  continue;
381  }
382 
383  // Visit our predecessors and enqueue them.
384  WL1.append(N->Preds.begin(), N->Preds.end());
385  }
386 
387  // We didn't hit a root? Return with a null pointer for the new graph.
388  if (WL2.empty())
389  return nullptr;
390 
391  // Create an empty graph.
392  std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
393 
394  // ===- Pass 2 (forward DFS to construct the new graph) -===
395  while (!WL2.empty()) {
396  const ExplodedNode *N = WL2.pop_back_val();
397 
398  // Skip this node if we have already processed it.
399  if (Pass2.find(N) != Pass2.end())
400  continue;
401 
402  // Create the corresponding node in the new graph and record the mapping
403  // from the old node to the new node.
404  ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State, N->isSink());
405  Pass2[N] = NewN;
406 
407  // Also record the reverse mapping from the new node to the old node.
408  if (InverseMap) (*InverseMap)[NewN] = N;
409 
410  // If this node is a root, designate it as such in the graph.
411  if (N->Preds.empty())
412  G->addRoot(NewN);
413 
414  // In the case that some of the intended predecessors of NewN have already
415  // been created, we should hook them up as predecessors.
416 
417  // Walk through the predecessors of 'N' and hook up their corresponding
418  // nodes in the new graph (if any) to the freshly created node.
419  for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
420  I != E; ++I) {
421  Pass2Ty::iterator PI = Pass2.find(*I);
422  if (PI == Pass2.end())
423  continue;
424 
425  NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
426  }
427 
428  // In the case that some of the intended successors of NewN have already
429  // been created, we should hook them up as successors. Otherwise, enqueue
430  // the new nodes from the original graph that should have nodes created
431  // in the new graph.
432  for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
433  I != E; ++I) {
434  Pass2Ty::iterator PI = Pass2.find(*I);
435  if (PI != Pass2.end()) {
436  const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
437  continue;
438  }
439 
440  // Enqueue nodes to the worklist that were marked during pass 1.
441  if (Pass1.count(*I))
442  WL2.push_back(*I);
443  }
444  }
445 
446  return G;
447 }
448 
unsigned ReclaimCounter
Counter to determine when to reclaim nodes.
ExplodedNode *const * succ_iterator
NodeVector FreeNodes
A list of nodes that can be reused.
unsigned NumNodes
NumNodes - The number of nodes in the graph.
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:585
StringRef P
Represents a point after we ran remove dead bindings BEFORE processing the given statement.
Definition: ProgramPoint.h:442
Represents a program point just before an implicit call event.
Definition: ProgramPoint.h:552
const ProgramStateRef & getState() const
bool isConsumedExpr(Expr *E) const
Definition: ParentMap.cpp:159
NodeVector ChangedNodes
A list of recently allocated nodes that can potentially be recycled.
LineState State
BumpVector< ExplodedNode * > ExplodedNodeVector
succ_iterator succ_begin()
Represents a program point after a store evaluation.
Definition: ProgramPoint.h:400
std::unique_ptr< ExplodedGraph > trim(ArrayRef< const NodeTy *> Nodes, InterExplodedGraphMap *ForwardMap=nullptr, InterExplodedGraphMap *InverseMap=nullptr) const
Creates a trimmed version of the graph that only contains paths leading to the given nodes...
void addPredecessor(ExplodedNode *V, ExplodedGraph &G)
addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...
i32 captured_struct **param SharedsTy A type which contains references the shared variables *param Shareds Context with the list of shared variables from the p *TaskFunction *param Data Additional data for task generation like final * state
unsigned succ_size() const
const LocationContext * getLocationContext() const
std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const
unsigned pred_size() const
ExplodedNode * createUncachedNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false)
Create a node for a (Location, State) pair, but don&#39;t store it for deduplication later.
llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap
Expr - This represents one expression.
Definition: Expr.h:106
static ExplodedNode::Auditor * NodeAuditor
static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)
ExplodedNode * getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)
Retrieve the node associated with a (Location,State) pair, where the &#39;Location&#39; is a ProgramPoint in ...
ParentMap & getParentMap() const
ExplodedNode *const * pred_iterator
unsigned ReclaimNodeInterval
Determines how often nodes are reclaimed.
T castAs() const
Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type...
Definition: ProgramPoint.h:140
static bool isCallStmt(const Stmt *S)
Returns true if this is a statement is a function or method call of some kind.
Definition: CallEvent.cpp:270
llvm::FoldingSet< ExplodedNode > Nodes
Nodes - The nodes in the graph.
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
bool isLValue() const
isLValue - True if this expression is an "l-value" according to the rules of the current language...
Definition: Expr.h:249
void push_back(const_reference Elt, BumpVectorContext &C)
Definition: BumpVector.h:160
Dataflow Directional Tag Classes.
BumpVectorContext & getNodeAllocator()
virtual void AddEdge(ExplodedNode *Src, ExplodedNode *Dst)=0
void reclaimRecentlyAllocatedNodes()
Reclaim "uninteresting" nodes created since the last time this method was called. ...
const ProgramPointTag * getTag() const
Definition: ProgramPoint.h:177
static void SetAuditor(Auditor *A)
const LocationContext * getLocationContext() const
Definition: ProgramPoint.h:179
pred_iterator pred_begin()
llvm::BumpPtrAllocator & getAllocator()
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:151
static bool isInterestingLValueExpr(const Expr *Ex)
Returns true if nodes for the given expression kind are always kept around.
llvm::PointerUnion< ExplodedNode *, ExplodedNodeVector * > GroupStorage