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  Optional<int64_t> Out = G->getAllocator().identifyObject(this);
288  assert(Out && "Wrong allocator used");
289  assert(*Out % alignof(ExplodedNode) == 0 && "Wrong alignment information");
290  return *Out / alignof(ExplodedNode);
291 }
292 
294  return pred_size() == 1 && succ_size() == 1 &&
295  (*pred_begin())->getState()->getID() == getState()->getID();
296 }
297 
300  bool IsSink,
301  bool* IsNew) {
302  // Profile 'State' to determine if we already have an existing node.
303  llvm::FoldingSetNodeID profile;
304  void *InsertPos = nullptr;
305 
306  NodeTy::Profile(profile, L, State, IsSink);
307  NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
308 
309  if (!V) {
310  if (!FreeNodes.empty()) {
311  V = FreeNodes.back();
312  FreeNodes.pop_back();
313  }
314  else {
315  // Allocate a new node.
316  V = (NodeTy*) getAllocator().Allocate<NodeTy>();
317  }
318 
319  new (V) NodeTy(L, State, IsSink);
320 
322  ChangedNodes.push_back(V);
323 
324  // Insert the node into the node set and return it.
325  Nodes.InsertNode(V, InsertPos);
326  ++NumNodes;
327 
328  if (IsNew) *IsNew = true;
329  }
330  else
331  if (IsNew) *IsNew = false;
332 
333  return V;
334 }
335 
338  bool IsSink) {
339  NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
340  new (V) NodeTy(L, State, IsSink);
341  return V;
342 }
343 
344 std::unique_ptr<ExplodedGraph>
346  InterExplodedGraphMap *ForwardMap,
347  InterExplodedGraphMap *InverseMap) const {
348  if (Nodes.empty())
349  return nullptr;
350 
351  using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;
352  Pass1Ty Pass1;
353 
354  using Pass2Ty = InterExplodedGraphMap;
355  InterExplodedGraphMap Pass2Scratch;
356  Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;
357 
359 
360  // ===- Pass 1 (reverse DFS) -===
361  for (const auto Sink : Sinks)
362  if (Sink)
363  WL1.push_back(Sink);
364 
365  // Process the first worklist until it is empty.
366  while (!WL1.empty()) {
367  const ExplodedNode *N = WL1.pop_back_val();
368 
369  // Have we already visited this node? If so, continue to the next one.
370  if (!Pass1.insert(N).second)
371  continue;
372 
373  // If this is a root enqueue it to the second worklist.
374  if (N->Preds.empty()) {
375  WL2.push_back(N);
376  continue;
377  }
378 
379  // Visit our predecessors and enqueue them.
380  WL1.append(N->Preds.begin(), N->Preds.end());
381  }
382 
383  // We didn't hit a root? Return with a null pointer for the new graph.
384  if (WL2.empty())
385  return nullptr;
386 
387  // Create an empty graph.
388  std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
389 
390  // ===- Pass 2 (forward DFS to construct the new graph) -===
391  while (!WL2.empty()) {
392  const ExplodedNode *N = WL2.pop_back_val();
393 
394  // Skip this node if we have already processed it.
395  if (Pass2.find(N) != Pass2.end())
396  continue;
397 
398  // Create the corresponding node in the new graph and record the mapping
399  // from the old node to the new node.
400  ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State, N->isSink());
401  Pass2[N] = NewN;
402 
403  // Also record the reverse mapping from the new node to the old node.
404  if (InverseMap) (*InverseMap)[NewN] = N;
405 
406  // If this node is a root, designate it as such in the graph.
407  if (N->Preds.empty())
408  G->addRoot(NewN);
409 
410  // In the case that some of the intended predecessors of NewN have already
411  // been created, we should hook them up as predecessors.
412 
413  // Walk through the predecessors of 'N' and hook up their corresponding
414  // nodes in the new graph (if any) to the freshly created node.
415  for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
416  I != E; ++I) {
417  Pass2Ty::iterator PI = Pass2.find(*I);
418  if (PI == Pass2.end())
419  continue;
420 
421  NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
422  }
423 
424  // In the case that some of the intended successors of NewN have already
425  // been created, we should hook them up as successors. Otherwise, enqueue
426  // the new nodes from the original graph that should have nodes created
427  // in the new graph.
428  for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
429  I != E; ++I) {
430  Pass2Ty::iterator PI = Pass2.find(*I);
431  if (PI != Pass2.end()) {
432  const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
433  continue;
434  }
435 
436  // Enqueue nodes to the worklist that were marked during pass 1.
437  if (Pass1.count(*I))
438  WL2.push_back(*I);
439  }
440  }
441 
442  return G;
443 }
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:105
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:248
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, and its program state is the ...
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.