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