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