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