Coverage Report

Created: 2020-02-18 08:44

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
Line
Count
Source (jump to first uncovered line)
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
14
#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
15
#include "clang/AST/Expr.h"
16
#include "clang/AST/ExprObjC.h"
17
#include "clang/AST/ParentMap.h"
18
#include "clang/AST/Stmt.h"
19
#include "clang/Analysis/CFGStmtMap.h"
20
#include "clang/Analysis/ProgramPoint.h"
21
#include "clang/Analysis/Support/BumpVector.h"
22
#include "clang/Basic/LLVM.h"
23
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
24
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
25
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.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
42
36.7k
ExplodedGraph::ExplodedGraph() = default;
43
44
36.7k
ExplodedGraph::~ExplodedGraph() = default;
45
46
//===----------------------------------------------------------------------===//
47
// Node reclamation.
48
//===----------------------------------------------------------------------===//
49
50
936k
bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) {
51
936k
  if (!Ex->isLValue())
52
482k
    return false;
53
453k
  return isa<DeclRefExpr>(Ex) ||
54
453k
         
isa<MemberExpr>(Ex)142k
||
55
453k
         
isa<ObjCIvarRefExpr>(Ex)68.6k
;
56
453k
}
57
58
2.00M
bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
59
2.00M
  // First, we only consider nodes for reclamation of the following
60
2.00M
  // conditions apply:
61
2.00M
  //
62
2.00M
  // (1) 1 predecessor (that has one successor)
63
2.00M
  // (2) 1 successor (that has one predecessor)
64
2.00M
  //
65
2.00M
  // If a node has no successor it is on the "frontier", while a node
66
2.00M
  // with no predecessor is a root.
67
2.00M
  //
68
2.00M
  // After these prerequisites, we discard all "filler" nodes that
69
2.00M
  // are used only for intermediate processing, and are not essential
70
2.00M
  // for analyzer history:
71
2.00M
  //
72
2.00M
  // (a) PreStmtPurgeDeadSymbols
73
2.00M
  //
74
2.00M
  // We then discard all other nodes where *all* of the following conditions
75
2.00M
  // apply:
76
2.00M
  //
77
2.00M
  // (3) The ProgramPoint is for a PostStmt, but not a PostStore.
78
2.00M
  // (4) There is no 'tag' for the ProgramPoint.
79
2.00M
  // (5) The 'store' is the same as the predecessor.
80
2.00M
  // (6) The 'GDM' is the same as the predecessor.
81
2.00M
  // (7) The LocationContext is the same as the predecessor.
82
2.00M
  // (8) Expressions that are *not* lvalue expressions.
83
2.00M
  // (9) The PostStmt isn't for a non-consumed Stmt or Expr.
84
2.00M
  // (10) The successor is neither a CallExpr StmtPoint nor a CallEnter or
85
2.00M
  //      PreImplicitCall (so that we would be able to find it when retrying a
86
2.00M
  //      call with no inlining).
87
2.00M
  // FIXME: It may be safe to reclaim PreCall and PostCall nodes as well.
88
2.00M
89
2.00M
  // Conditions 1 and 2.
90
2.00M
  if (node->pred_size() != 1 || 
node->succ_size() != 11.99M
)
91
84.1k
    return false;
92
1.91M
93
1.91M
  const ExplodedNode *pred = *(node->pred_begin());
94
1.91M
  if (pred->succ_size() != 1)
95
63.1k
    return false;
96
1.85M
97
1.85M
  const ExplodedNode *succ = *(node->succ_begin());
98
1.85M
  if (succ->pred_size() != 1)
99
6.07k
    return false;
100
1.84M
101
1.84M
  // Now reclaim any nodes that are (by definition) not essential to
102
1.84M
  // analysis history and are not consulted by any client code.
103
1.84M
  ProgramPoint progPoint = node->getLocation();
104
1.84M
  if (progPoint.getAs<PreStmtPurgeDeadSymbols>())
105
231k
    return !progPoint.getTag();
106
1.61M
107
1.61M
  // Condition 3.
108
1.61M
  if (!progPoint.getAs<PostStmt>() || 
progPoint.getAs<PostStore>()1.13M
)
109
537k
    return false;
110
1.07M
111
1.07M
  // Condition 4.
112
1.07M
  if (progPoint.getTag())
113
78.2k
    return false;
114
1.00M
115
1.00M
  // Conditions 5, 6, and 7.
116
1.00M
  ProgramStateRef state = node->getState();
117
1.00M
  ProgramStateRef pred_state = pred->getState();
118
1.00M
  if (state->store != pred_state->store || 
state->GDM != pred_state->GDM984k
||
119
1.00M
      
progPoint.getLocationContext() != pred->getLocationContext()961k
)
120
38.7k
    return false;
121
961k
122
961k
  // All further checks require expressions. As per #3, we know that we have
123
961k
  // a PostStmt.
124
961k
  const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt());
125
961k
  if (!Ex)
126
30.2k
    return false;
127
931k
128
931k
  // Condition 8.
129
931k
  // Do not collect nodes for "interesting" lvalue expressions since they are
130
931k
  // used extensively for generating path diagnostics.
131
931k
  if (isInterestingLValueExpr(Ex))
132
382k
    return false;
133
548k
134
548k
  // Condition 9.
135
548k
  // Do not collect nodes for non-consumed Stmt or Expr to ensure precise
136
548k
  // diagnostic generation; specifically, so that we could anchor arrows
137
548k
  // pointing to the beginning of statements (as written in code).
138
548k
  const ParentMap &PM = progPoint.getLocationContext()->getParentMap();
139
548k
  if (!PM.isConsumedExpr(Ex))
140
28.6k
    return false;
141
520k
142
520k
  // Condition 10.
143
520k
  const ProgramPoint SuccLoc = succ->getLocation();
144
520k
  if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>())
145
511k
    if (CallEvent::isCallStmt(SP->getStmt()))
146
62.6k
      return false;
147
457k
148
457k
  // Condition 10, continuation.
149
457k
  if (SuccLoc.getAs<CallEnter>() || 
SuccLoc.getAs<PreImplicitCall>()452k
)
150
5.56k
    return false;
151
452k
152
452k
  return true;
153
452k
}
154
155
452k
void ExplodedGraph::collectNode(ExplodedNode *node) {
156
452k
  // Removing a node means:
157
452k
  // (a) changing the predecessors successor to the successor of this node
158
452k
  // (b) changing the successors predecessor to the predecessor of this node
159
452k
  // (c) Putting 'node' onto freeNodes.
160
452k
  assert(node->pred_size() == 1 || node->succ_size() == 1);
161
452k
  ExplodedNode *pred = *(node->pred_begin());
162
452k
  ExplodedNode *succ = *(node->succ_begin());
163
452k
  pred->replaceSuccessor(succ);
164
452k
  succ->replacePredecessor(pred);
165
452k
  FreeNodes.push_back(node);
166
452k
  Nodes.RemoveNode(node);
167
452k
  --NumNodes;
168
452k
  node->~ExplodedNode();
169
452k
}
170
171
1.16M
void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
172
1.16M
  if (ChangedNodes.empty())
173
0
    return;
174
1.16M
175
1.16M
  // Only periodically reclaim nodes so that we can build up a set of
176
1.16M
  // nodes that meet the reclamation criteria.  Freshly created nodes
177
1.16M
  // by definition have no successor, and thus cannot be reclaimed (see below).
178
1.16M
  assert(ReclaimCounter > 0);
179
1.16M
  if (--ReclaimCounter != 0)
180
1.16M
    return;
181
789
  ReclaimCounter = ReclaimNodeInterval;
182
789
183
789
  for (const auto node : ChangedNodes)
184
2.00M
    if (shouldCollect(node))
185
452k
      collectNode(node);
186
789
  ChangedNodes.clear();
187
789
}
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.
203
using ExplodedNodeVector = BumpVector<ExplodedNode *>;
204
using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;
205
206
5.74M
void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
207
5.74M
  assert(!V->isSink());
208
5.74M
  Preds.addNode(V, G);
209
5.74M
  V->Succs.addNode(this, G);
210
5.74M
}
211
212
904k
void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
213
904k
  assert(!getFlag());
214
904k
215
904k
  GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
216
904k
  assert(Storage.is<ExplodedNode *>());
217
904k
  Storage = node;
218
904k
  assert(Storage.is<ExplodedNode *>());
219
904k
}
220
221
11.4M
void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
222
11.4M
  assert(!getFlag());
223
11.4M
224
11.4M
  GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
225
11.4M
  if (Storage.isNull()) {
226
11.4M
    Storage = N;
227
11.4M
    assert(Storage.is<ExplodedNode *>());
228
11.4M
    return;
229
11.4M
  }
230
49.4k
231
49.4k
  ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>();
232
49.4k
233
49.4k
  if (!V) {
234
45.5k
    // Switch from single-node to multi-node representation.
235
45.5k
    ExplodedNode *Old = Storage.get<ExplodedNode *>();
236
45.5k
237
45.5k
    BumpVectorContext &Ctx = G.getNodeAllocator();
238
45.5k
    V = G.getAllocator().Allocate<ExplodedNodeVector>();
239
45.5k
    new (V) ExplodedNodeVector(Ctx, 4);
240
45.5k
    V->push_back(Old, Ctx);
241
45.5k
242
45.5k
    Storage = V;
243
45.5k
    assert(!getFlag());
244
45.5k
    assert(Storage.is<ExplodedNodeVector *>());
245
45.5k
  }
246
49.4k
247
49.4k
  V->push_back(N, G.getNodeAllocator());
248
49.4k
}
249
250
8.28M
unsigned ExplodedNode::NodeGroup::size() const {
251
8.28M
  if (getFlag())
252
3.09k
    return 0;
253
8.28M
254
8.28M
  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
255
8.28M
  if (Storage.isNull())
256
48.4k
    return 0;
257
8.23M
  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
258
103k
    return V->size();
259
8.13M
  return 1;
260
8.13M
}
261
262
18.4M
ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {
263
18.4M
  if (getFlag())
264
3.31k
    return nullptr;
265
18.4M
266
18.4M
  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
267
18.4M
  if (Storage.isNull())
268
12.5k
    return nullptr;
269
18.4M
  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
270
11.2k
    return V->begin();
271
18.4M
  return Storage.getAddrOfPtr1();
272
18.4M
}
273
274
6.93M
ExplodedNode * const *ExplodedNode::NodeGroup::end() const {
275
6.93M
  if (getFlag())
276
3.31k
    return nullptr;
277
6.93M
278
6.93M
  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
279
6.93M
  if (Storage.isNull())
280
12.5k
    return nullptr;
281
6.92M
  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
282
9.90k
    return V->end();
283
6.91M
  return Storage.getAddrOfPtr1() + 1;
284
6.91M
}
285
286
1.52k
bool ExplodedNode::isTrivial() const {
287
1.52k
  return pred_size() == 1 && 
succ_size() == 11.51k
&&
288
1.52k
         
getFirstPred()->getState()->getID() == getState()->getID()1.43k
&&
289
1.52k
         
getFirstPred()->succ_size() == 1712
;
290
1.52k
}
291
292
142k
const CFGBlock *ExplodedNode::getCFGBlock() const {
293
142k
  ProgramPoint P = getLocation();
294
142k
  if (auto BEP = P.getAs<BlockEntrance>())
295
9.71k
    return BEP->getBlock();
296
132k
297
132k
  // Find the node's current statement in the CFG.
298
132k
  // FIXME: getStmtForDiagnostics() does nasty things in order to provide
299
132k
  // a valid statement for body farms, do we need this behavior here?
300
132k
  if (const Stmt *S = getStmtForDiagnostics())
301
128k
    return getLocationContext()
302
128k
        ->getAnalysisDeclContext()
303
128k
        ->getCFGStmtMap()
304
128k
        ->getBlock(S);
305
3.75k
306
3.75k
  return nullptr;
307
3.75k
}
308
309
static const LocationContext *
310
15.1k
findTopAutosynthesizedParentContext(const LocationContext *LC) {
311
15.1k
  assert(LC->getAnalysisDeclContext()->isBodyAutosynthesized());
312
15.1k
  const LocationContext *ParentLC = LC->getParent();
313
15.1k
  assert(ParentLC && "We don't start analysis from autosynthesized code");
314
15.1k
  while (ParentLC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
315
0
    LC = ParentLC;
316
0
    ParentLC = LC->getParent();
317
0
    assert(ParentLC && "We don't start analysis from autosynthesized code");
318
0
  }
319
15.1k
  return LC;
320
15.1k
}
321
322
2.69M
const Stmt *ExplodedNode::getStmtForDiagnostics() const {
323
2.69M
  // We cannot place diagnostics on autosynthesized code.
324
2.69M
  // Put them onto the call site through which we jumped into autosynthesized
325
2.69M
  // code for the first time.
326
2.69M
  const LocationContext *LC = getLocationContext();
327
2.69M
  if (LC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
328
15.1k
    // It must be a stack frame because we only autosynthesize functions.
329
15.1k
    return cast<StackFrameContext>(findTopAutosynthesizedParentContext(LC))
330
15.1k
        ->getCallSite();
331
15.1k
  }
332
2.67M
  // Otherwise, see if the node's program point directly points to a statement.
333
2.67M
  // FIXME: Refactor into a ProgramPoint method?
334
2.67M
  ProgramPoint P = getLocation();
335
2.67M
  if (auto SP = P.getAs<StmtPoint>())
336
2.36M
    return SP->getStmt();
337
312k
  if (auto BE = P.getAs<BlockEdge>())
338
117k
    return BE->getSrc()->getTerminatorStmt();
339
194k
  if (auto CE = P.getAs<CallEnter>())
340
2.15k
    return CE->getCallExpr();
341
192k
  if (auto CEE = P.getAs<CallExitEnd>())
342
39.8k
    return CEE->getCalleeContext()->getCallSite();
343
152k
  if (auto PIPP = P.getAs<PostInitializer>())
344
15.5k
    return PIPP->getInitializer()->getInit();
345
137k
  if (auto CEB = P.getAs<CallExitBegin>())
346
38.5k
    return CEB->getReturnStmt();
347
98.7k
  if (auto FEP = P.getAs<FunctionExitPoint>())
348
8.03k
    return FEP->getStmt();
349
90.7k
350
90.7k
  return nullptr;
351
90.7k
}
352
353
1.13k
const Stmt *ExplodedNode::getNextStmtForDiagnostics() const {
354
2.09k
  for (const ExplodedNode *N = getFirstSucc(); N; 
N = N->getFirstSucc()953
) {
355
1.93k
    if (const Stmt *S = N->getStmtForDiagnostics()) {
356
986
      // Check if the statement is '?' or '&&'/'||'.  These are "merges",
357
986
      // not actual statement points.
358
986
      switch (S->getStmtClass()) {
359
2
        case Stmt::ChooseExprClass:
360
2
        case Stmt::BinaryConditionalOperatorClass:
361
2
        case Stmt::ConditionalOperatorClass:
362
2
          continue;
363
67
        case Stmt::BinaryOperatorClass: {
364
67
          BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
365
67
          if (Op == BO_LAnd || Op == BO_LOr)
366
0
            continue;
367
67
          break;
368
67
        }
369
917
        default:
370
917
          break;
371
984
      }
372
984
      // We found the statement, so return it.
373
984
      return S;
374
984
    }
375
1.93k
  }
376
1.13k
377
1.13k
  
return nullptr153
;
378
1.13k
}
379
380
28
const Stmt *ExplodedNode::getPreviousStmtForDiagnostics() const {
381
32
  for (const ExplodedNode *N = getFirstPred(); N; 
N = N->getFirstPred()4
)
382
30
    if (const Stmt *S = N->getStmtForDiagnostics())
383
26
      return S;
384
28
385
28
  
return nullptr2
;
386
28
}
387
388
12.9k
const Stmt *ExplodedNode::getCurrentOrPreviousStmtForDiagnostics() const {
389
12.9k
  if (const Stmt *S = getStmtForDiagnostics())
390
12.9k
    return S;
391
28
392
28
  return getPreviousStmtForDiagnostics();
393
28
}
394
395
ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
396
                                     ProgramStateRef State,
397
                                     bool IsSink,
398
3.06M
                                     bool* IsNew) {
399
3.06M
  // Profile 'State' to determine if we already have an existing node.
400
3.06M
  llvm::FoldingSetNodeID profile;
401
3.06M
  void *InsertPos = nullptr;
402
3.06M
403
3.06M
  NodeTy::Profile(profile, L, State, IsSink);
404
3.06M
  NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
405
3.06M
406
3.06M
  if (!V) {
407
3.06M
    if (!FreeNodes.empty()) {
408
449k
      V = FreeNodes.back();
409
449k
      FreeNodes.pop_back();
410
449k
    }
411
2.61M
    else {
412
2.61M
      // Allocate a new node.
413
2.61M
      V = (NodeTy*) getAllocator().Allocate<NodeTy>();
414
2.61M
    }
415
3.06M
416
3.06M
    ++NumNodes;
417
3.06M
    new (V) NodeTy(L, State, NumNodes, IsSink);
418
3.06M
419
3.06M
    if (ReclaimNodeInterval)
420
3.06M
      ChangedNodes.push_back(V);
421
3.06M
422
3.06M
    // Insert the node into the node set and return it.
423
3.06M
    Nodes.InsertNode(V, InsertPos);
424
3.06M
425
3.06M
    if (IsNew) *IsNew = true;
426
3.06M
  }
427
7.56k
  else
428
7.56k
    if (IsNew) *IsNew = false;
429
3.06M
430
3.06M
  return V;
431
3.06M
}
432
433
ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
434
                                                ProgramStateRef State,
435
                                                int64_t Id,
436
2.70M
                                                bool IsSink) {
437
2.70M
  NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
438
2.70M
  new (V) NodeTy(L, State, Id, IsSink);
439
2.70M
  return V;
440
2.70M
}
441
442
std::unique_ptr<ExplodedGraph>
443
ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
444
                    InterExplodedGraphMap *ForwardMap,
445
12.0k
                    InterExplodedGraphMap *InverseMap) const {
446
12.0k
  if (Nodes.empty())
447
0
    return nullptr;
448
12.0k
449
12.0k
  using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;
450
12.0k
  Pass1Ty Pass1;
451
12.0k
452
12.0k
  using Pass2Ty = InterExplodedGraphMap;
453
12.0k
  InterExplodedGraphMap Pass2Scratch;
454
12.0k
  Pass2Ty &Pass2 = ForwardMap ? 
*ForwardMap12.0k
:
Pass2Scratch1
;
455
12.0k
456
12.0k
  SmallVector<const ExplodedNode*, 10> WL1, WL2;
457
12.0k
458
12.0k
  // ===- Pass 1 (reverse DFS) -===
459
12.0k
  for (const auto Sink : Sinks)
460
12.9k
    if (Sink)
461
12.9k
      WL1.push_back(Sink);
462
12.0k
463
12.0k
  // Process the first worklist until it is empty.
464
1.42M
  while (!WL1.empty()) {
465
1.41M
    const ExplodedNode *N = WL1.pop_back_val();
466
1.41M
467
1.41M
    // Have we already visited this node?  If so, continue to the next one.
468
1.41M
    if (!Pass1.insert(N).second)
469
1.61k
      continue;
470
1.41M
471
1.41M
    // If this is a root enqueue it to the second worklist.
472
1.41M
    if (N->Preds.empty()) {
473
12.0k
      WL2.push_back(N);
474
12.0k
      continue;
475
12.0k
    }
476
1.40M
477
1.40M
    // Visit our predecessors and enqueue them.
478
1.40M
    WL1.append(N->Preds.begin(), N->Preds.end());
479
1.40M
  }
480
12.0k
481
12.0k
  // We didn't hit a root? Return with a null pointer for the new graph.
482
12.0k
  if (WL2.empty())
483
0
    return nullptr;
484
12.0k
485
12.0k
  // Create an empty graph.
486
12.0k
  std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
487
12.0k
488
12.0k
  // ===- Pass 2 (forward DFS to construct the new graph) -===
489
1.42M
  while (!WL2.empty()) {
490
1.41M
    const ExplodedNode *N = WL2.pop_back_val();
491
1.41M
492
1.41M
    // Skip this node if we have already processed it.
493
1.41M
    if (Pass2.find(N) != Pass2.end())
494
9
      continue;
495
1.41M
496
1.41M
    // Create the corresponding node in the new graph and record the mapping
497
1.41M
    // from the old node to the new node.
498
1.41M
    ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State,
499
1.41M
                                               N->getID(), N->isSink());
500
1.41M
    Pass2[N] = NewN;
501
1.41M
502
1.41M
    // Also record the reverse mapping from the new node to the old node.
503
1.41M
    if (InverseMap) 
(*InverseMap)[NewN] = N0
;
504
1.41M
505
1.41M
    // If this node is a root, designate it as such in the graph.
506
1.41M
    if (N->Preds.empty())
507
12.0k
      G->addRoot(NewN);
508
1.41M
509
1.41M
    // In the case that some of the intended predecessors of NewN have already
510
1.41M
    // been created, we should hook them up as predecessors.
511
1.41M
512
1.41M
    // Walk through the predecessors of 'N' and hook up their corresponding
513
1.41M
    // nodes in the new graph (if any) to the freshly created node.
514
1.41M
    for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
515
2.82M
         I != E; 
++I1.40M
) {
516
1.40M
      Pass2Ty::iterator PI = Pass2.find(*I);
517
1.40M
      if (PI == Pass2.end())
518
722
        continue;
519
1.40M
520
1.40M
      NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
521
1.40M
    }
522
1.41M
523
1.41M
    // In the case that some of the intended successors of NewN have already
524
1.41M
    // been created, we should hook them up as successors.  Otherwise, enqueue
525
1.41M
    // the new nodes from the original graph that should have nodes created
526
1.41M
    // in the new graph.
527
1.41M
    for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
528
2.83M
         I != E; 
++I1.42M
) {
529
1.42M
      Pass2Ty::iterator PI = Pass2.find(*I);
530
1.42M
      if (PI != Pass2.end()) {
531
722
        const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
532
722
        continue;
533
722
      }
534
1.41M
535
1.41M
      // Enqueue nodes to the worklist that were marked during pass 1.
536
1.41M
      if (Pass1.count(*I))
537
1.40M
        WL2.push_back(*I);
538
1.41M
    }
539
1.41M
  }
540
12.0k
541
12.0k
  return G;
542
12.0k
}