Coverage Report

Created: 2020-11-24 06:42

/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
42.1k
ExplodedGraph::ExplodedGraph() = default;
43
44
42.1k
ExplodedGraph::~ExplodedGraph() = default;
45
46
//===----------------------------------------------------------------------===//
47
// Node reclamation.
48
//===----------------------------------------------------------------------===//
49
50
640k
bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) {
51
640k
  if (!Ex->isLValue())
52
335k
    return false;
53
304k
  return isa<DeclRefExpr>(Ex) || 
isa<MemberExpr>(Ex)90.9k
||
54
38.7k
         isa<ObjCIvarRefExpr>(Ex) || 
isa<ArraySubscriptExpr>(Ex)38.6k
;
55
304k
}
56
57
1.22M
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
1.22M
  if (node->pred_size() != 1 || 
node->succ_size() != 11.22M
)
90
69.0k
    return false;
91
92
1.15M
  const ExplodedNode *pred = *(node->pred_begin());
93
1.15M
  if (pred->succ_size() != 1)
94
52.8k
    return false;
95
96
1.10M
  const ExplodedNode *succ = *(node->succ_begin());
97
1.10M
  if (succ->pred_size() != 1)
98
4.19k
    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
1.09M
  ProgramPoint progPoint = node->getLocation();
103
1.09M
  if (progPoint.getAs<PreStmtPurgeDeadSymbols>())
104
130k
    return !progPoint.getTag();
105
106
  // Condition 3.
107
967k
  if (!progPoint.getAs<PostStmt>() || 
progPoint.getAs<PostStore>()748k
)
108
258k
    return false;
109
110
  // Condition 4.
111
709k
  if (progPoint.getTag())
112
39.5k
    return false;
113
114
  // Conditions 5, 6, and 7.
115
669k
  ProgramStateRef state = node->getState();
116
669k
  ProgramStateRef pred_state = pred->getState();
117
669k
  if (state->store != pred_state->store || 
state->GDM != pred_state->GDM658k
||
118
654k
      progPoint.getLocationContext() != pred->getLocationContext())
119
14.9k
    return false;
120
121
  // All further checks require expressions. As per #3, we know that we have
122
  // a PostStmt.
123
654k
  const Expr *Ex = dyn_cast<Expr>(progPoint.castAs<PostStmt>().getStmt());
124
654k
  if (!Ex)
125
19.1k
    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
635k
  if (isInterestingLValueExpr(Ex))
131
271k
    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
364k
  const ParentMap &PM = progPoint.getLocationContext()->getParentMap();
138
364k
  if (!PM.isConsumedExpr(Ex))
139
22.0k
    return false;
140
141
  // Condition 10.
142
341k
  const ProgramPoint SuccLoc = succ->getLocation();
143
341k
  if (Optional<StmtPoint> SP = SuccLoc.getAs<StmtPoint>())
144
338k
    if (CallEvent::isCallStmt(SP->getStmt()))
145
29.3k
      return false;
146
147
  // Condition 10, continuation.
148
312k
  if (SuccLoc.getAs<CallEnter>() || 
SuccLoc.getAs<PreImplicitCall>()312k
)
149
233
    return false;
150
151
312k
  return true;
152
312k
}
153
154
312k
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
312k
  assert(node->pred_size() == 1 || node->succ_size() == 1);
160
312k
  ExplodedNode *pred = *(node->pred_begin());
161
312k
  ExplodedNode *succ = *(node->succ_begin());
162
312k
  pred->replaceSuccessor(succ);
163
312k
  succ->replacePredecessor(pred);
164
312k
  FreeNodes.push_back(node);
165
312k
  Nodes.RemoveNode(node);
166
312k
  --NumNodes;
167
312k
  node->~ExplodedNode();
168
312k
}
169
170
960k
void ExplodedGraph::reclaimRecentlyAllocatedNodes() {
171
960k
  if (ChangedNodes.empty())
172
5
    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
960k
  assert(ReclaimCounter > 0);
178
960k
  if (--ReclaimCounter != 0)
179
959k
    return;
180
516
  ReclaimCounter = ReclaimNodeInterval;
181
182
516
  for (const auto node : ChangedNodes)
183
1.22M
    if (shouldCollect(node))
184
312k
      collectNode(node);
185
516
  ChangedNodes.clear();
186
516
}
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.
202
using ExplodedNodeVector = BumpVector<ExplodedNode *>;
203
using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;
204
205
5.93M
void ExplodedNode::addPredecessor(ExplodedNode *V, ExplodedGraph &G) {
206
5.93M
  assert(!V->isSink());
207
5.93M
  Preds.addNode(V, G);
208
5.93M
  V->Succs.addNode(this, G);
209
5.93M
}
210
211
624k
void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {
212
624k
  assert(!getFlag());
213
214
624k
  GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
215
624k
  assert(Storage.is<ExplodedNode *>());
216
624k
  Storage = node;
217
624k
  assert(Storage.is<ExplodedNode *>());
218
624k
}
219
220
11.8M
void ExplodedNode::NodeGroup::addNode(ExplodedNode *N, ExplodedGraph &G) {
221
11.8M
  assert(!getFlag());
222
223
11.8M
  GroupStorage &Storage = reinterpret_cast<GroupStorage&>(P);
224
11.8M
  if (Storage.isNull()) {
225
11.8M
    Storage = N;
226
11.8M
    assert(Storage.is<ExplodedNode *>());
227
11.8M
    return;
228
11.8M
  }
229
230
43.0k
  ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>();
231
232
43.0k
  if (!V) {
233
    // Switch from single-node to multi-node representation.
234
39.7k
    ExplodedNode *Old = Storage.get<ExplodedNode *>();
235
236
39.7k
    BumpVectorContext &Ctx = G.getNodeAllocator();
237
39.7k
    V = G.getAllocator().Allocate<ExplodedNodeVector>();
238
39.7k
    new (V) ExplodedNodeVector(Ctx, 4);
239
39.7k
    V->push_back(Old, Ctx);
240
241
39.7k
    Storage = V;
242
39.7k
    assert(!getFlag());
243
39.7k
    assert(Storage.is<ExplodedNodeVector *>());
244
39.7k
  }
245
246
43.0k
  V->push_back(N, G.getNodeAllocator());
247
43.0k
}
248
249
5.08M
unsigned ExplodedNode::NodeGroup::size() const {
250
5.08M
  if (getFlag())
251
2.75k
    return 0;
252
253
5.07M
  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
254
5.07M
  if (Storage.isNull())
255
39.2k
    return 0;
256
5.03M
  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
257
85.6k
    return V->size();
258
4.95M
  return 1;
259
4.95M
}
260
261
20.6M
ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {
262
20.6M
  if (getFlag())
263
3.58k
    return nullptr;
264
265
20.6M
  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
266
20.6M
  if (Storage.isNull())
267
14.9k
    return nullptr;
268
20.6M
  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
269
13.4k
    return V->begin();
270
20.6M
  return Storage.getAddrOfPtr1();
271
20.6M
}
272
273
9.02M
ExplodedNode * const *ExplodedNode::NodeGroup::end() const {
274
9.02M
  if (getFlag())
275
3.58k
    return nullptr;
276
277
9.02M
  const GroupStorage &Storage = reinterpret_cast<const GroupStorage &>(P);
278
9.02M
  if (Storage.isNull())
279
14.9k
    return nullptr;
280
9.00M
  if (ExplodedNodeVector *V = Storage.dyn_cast<ExplodedNodeVector *>())
281
12.1k
    return V->end();
282
8.99M
  return Storage.getAddrOfPtr1() + 1;
283
8.99M
}
284
285
1.84k
bool ExplodedNode::isTrivial() const {
286
1.84k
  return pred_size() == 1 && 
succ_size() == 11.83k
&&
287
1.74k
         getFirstPred()->getState()->getID() == getState()->getID() &&
288
928
         getFirstPred()->succ_size() == 1;
289
1.84k
}
290
291
147k
const CFGBlock *ExplodedNode::getCFGBlock() const {
292
147k
  ProgramPoint P = getLocation();
293
147k
  if (auto BEP = P.getAs<BlockEntrance>())
294
10.0k
    return BEP->getBlock();
295
296
  // Find the node's current statement in the CFG.
297
  // FIXME: getStmtForDiagnostics() does nasty things in order to provide
298
  // a valid statement for body farms, do we need this behavior here?
299
137k
  if (const Stmt *S = getStmtForDiagnostics())
300
133k
    return getLocationContext()
301
133k
        ->getAnalysisDeclContext()
302
133k
        ->getCFGStmtMap()
303
133k
        ->getBlock(S);
304
305
3.77k
  return nullptr;
306
3.77k
}
307
308
static const LocationContext *
309
15.1k
findTopAutosynthesizedParentContext(const LocationContext *LC) {
310
15.1k
  assert(LC->getAnalysisDeclContext()->isBodyAutosynthesized());
311
15.1k
  const LocationContext *ParentLC = LC->getParent();
312
15.1k
  assert(ParentLC && "We don't start analysis from autosynthesized code");
313
15.1k
  while (ParentLC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
314
0
    LC = ParentLC;
315
0
    ParentLC = LC->getParent();
316
0
    assert(ParentLC && "We don't start analysis from autosynthesized code");
317
0
  }
318
15.1k
  return LC;
319
15.1k
}
320
321
3.47M
const Stmt *ExplodedNode::getStmtForDiagnostics() const {
322
  // We cannot place diagnostics on autosynthesized code.
323
  // Put them onto the call site through which we jumped into autosynthesized
324
  // code for the first time.
325
3.47M
  const LocationContext *LC = getLocationContext();
326
3.47M
  if (LC->getAnalysisDeclContext()->isBodyAutosynthesized()) {
327
    // It must be a stack frame because we only autosynthesize functions.
328
15.1k
    return cast<StackFrameContext>(findTopAutosynthesizedParentContext(LC))
329
15.1k
        ->getCallSite();
330
15.1k
  }
331
  // Otherwise, see if the node's program point directly points to a statement.
332
  // FIXME: Refactor into a ProgramPoint method?
333
3.45M
  ProgramPoint P = getLocation();
334
3.45M
  if (auto SP = P.getAs<StmtPoint>())
335
3.04M
    return SP->getStmt();
336
417k
  if (auto BE = P.getAs<BlockEdge>())
337
157k
    return BE->getSrc()->getTerminatorStmt();
338
259k
  if (auto CE = P.getAs<CallEnter>())
339
2.20k
    return CE->getCallExpr();
340
257k
  if (auto CEE = P.getAs<CallExitEnd>())
341
55.1k
    return CEE->getCalleeContext()->getCallSite();
342
202k
  if (auto PIPP = P.getAs<PostInitializer>())
343
22.1k
    return PIPP->getInitializer()->getInit();
344
180k
  if (auto CEB = P.getAs<CallExitBegin>())
345
53.7k
    return CEB->getReturnStmt();
346
126k
  if (auto FEP = P.getAs<FunctionExitPoint>())
347
14.5k
    return FEP->getStmt();
348
349
112k
  return nullptr;
350
112k
}
351
352
1.18k
const Stmt *ExplodedNode::getNextStmtForDiagnostics() const {
353
2.18k
  for (const ExplodedNode *N = getFirstSucc(); N; 
N = N->getFirstSucc()996
) {
354
2.02k
    if (const Stmt *S = N->getStmtForDiagnostics()) {
355
      // Check if the statement is '?' or '&&'/'||'.  These are "merges",
356
      // not actual statement points.
357
1.03k
      switch (S->getStmtClass()) {
358
2
        case Stmt::ChooseExprClass:
359
2
        case Stmt::BinaryConditionalOperatorClass:
360
2
        case Stmt::ConditionalOperatorClass:
361
2
          continue;
362
67
        case Stmt::BinaryOperatorClass: {
363
67
          BinaryOperatorKind Op = cast<BinaryOperator>(S)->getOpcode();
364
67
          if (Op == BO_LAnd || Op == BO_LOr)
365
0
            continue;
366
67
          break;
367
67
        }
368
962
        default:
369
962
          break;
370
1.02k
      }
371
      // We found the statement, so return it.
372
1.02k
      return S;
373
1.02k
    }
374
2.02k
  }
375
376
156
  return nullptr;
377
1.18k
}
378
379
21
const Stmt *ExplodedNode::getPreviousStmtForDiagnostics() const {
380
25
  for (const ExplodedNode *N = getFirstPred(); N; 
N = N->getFirstPred()4
)
381
23
    if (const Stmt *S = N->getStmtForDiagnostics())
382
19
      return S;
383
384
2
  return nullptr;
385
21
}
386
387
15.8k
const Stmt *ExplodedNode::getCurrentOrPreviousStmtForDiagnostics() const {
388
15.8k
  if (const Stmt *S = getStmtForDiagnostics())
389
15.8k
    return S;
390
391
21
  return getPreviousStmtForDiagnostics();
392
21
}
393
394
ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
395
                                     ProgramStateRef State,
396
                                     bool IsSink,
397
2.44M
                                     bool* IsNew) {
398
  // Profile 'State' to determine if we already have an existing node.
399
2.44M
  llvm::FoldingSetNodeID profile;
400
2.44M
  void *InsertPos = nullptr;
401
402
2.44M
  NodeTy::Profile(profile, L, State, IsSink);
403
2.44M
  NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);
404
405
2.44M
  if (!V) {
406
2.43M
    if (!FreeNodes.empty()) {
407
308k
      V = FreeNodes.back();
408
308k
      FreeNodes.pop_back();
409
308k
    }
410
2.13M
    else {
411
      // Allocate a new node.
412
2.13M
      V = (NodeTy*) getAllocator().Allocate<NodeTy>();
413
2.13M
    }
414
415
2.43M
    ++NumNodes;
416
2.43M
    new (V) NodeTy(L, State, NumNodes, IsSink);
417
418
2.43M
    if (ReclaimNodeInterval)
419
2.43M
      ChangedNodes.push_back(V);
420
421
    // Insert the node into the node set and return it.
422
2.43M
    Nodes.InsertNode(V, InsertPos);
423
424
2.43M
    if (IsNew) *IsNew = true;
425
2.43M
  }
426
5.85k
  else
427
5.85k
    if (IsNew) *IsNew = false;
428
429
2.44M
  return V;
430
2.44M
}
431
432
ExplodedNode *ExplodedGraph::createUncachedNode(const ProgramPoint &L,
433
                                                ProgramStateRef State,
434
                                                int64_t Id,
435
3.52M
                                                bool IsSink) {
436
3.52M
  NodeTy *V = (NodeTy *) getAllocator().Allocate<NodeTy>();
437
3.52M
  new (V) NodeTy(L, State, Id, IsSink);
438
3.52M
  return V;
439
3.52M
}
440
441
std::unique_ptr<ExplodedGraph>
442
ExplodedGraph::trim(ArrayRef<const NodeTy *> Sinks,
443
                    InterExplodedGraphMap *ForwardMap,
444
14.2k
                    InterExplodedGraphMap *InverseMap) const {
445
14.2k
  if (Nodes.empty())
446
0
    return nullptr;
447
448
14.2k
  using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;
449
14.2k
  Pass1Ty Pass1;
450
451
14.2k
  using Pass2Ty = InterExplodedGraphMap;
452
14.2k
  InterExplodedGraphMap Pass2Scratch;
453
14.2k
  Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : 
Pass2Scratch1
;
454
455
14.2k
  SmallVector<const ExplodedNode*, 10> WL1, WL2;
456
457
  // ===- Pass 1 (reverse DFS) -===
458
14.2k
  for (const auto Sink : Sinks)
459
15.3k
    if (Sink)
460
15.3k
      WL1.push_back(Sink);
461
462
  // Process the first worklist until it is empty.
463
1.85M
  while (!WL1.empty()) {
464
1.84M
    const ExplodedNode *N = WL1.pop_back_val();
465
466
    // Have we already visited this node?  If so, continue to the next one.
467
1.84M
    if (!Pass1.insert(N).second)
468
1.92k
      continue;
469
470
    // If this is a root enqueue it to the second worklist.
471
1.84M
    if (N->Preds.empty()) {
472
14.2k
      WL2.push_back(N);
473
14.2k
      continue;
474
14.2k
    }
475
476
    // Visit our predecessors and enqueue them.
477
1.82M
    WL1.append(N->Preds.begin(), N->Preds.end());
478
1.82M
  }
479
480
  // We didn't hit a root? Return with a null pointer for the new graph.
481
14.2k
  if (WL2.empty())
482
0
    return nullptr;
483
484
  // Create an empty graph.
485
14.2k
  std::unique_ptr<ExplodedGraph> G = MakeEmptyGraph();
486
487
  // ===- Pass 2 (forward DFS to construct the new graph) -===
488
1.85M
  while (!WL2.empty()) {
489
1.84M
    const ExplodedNode *N = WL2.pop_back_val();
490
491
    // Skip this node if we have already processed it.
492
1.84M
    if (Pass2.find(N) != Pass2.end())
493
9
      continue;
494
495
    // Create the corresponding node in the new graph and record the mapping
496
    // from the old node to the new node.
497
1.84M
    ExplodedNode *NewN = G->createUncachedNode(N->getLocation(), N->State,
498
1.84M
                                               N->getID(), N->isSink());
499
1.84M
    Pass2[N] = NewN;
500
501
    // Also record the reverse mapping from the new node to the old node.
502
1.84M
    if (InverseMap) 
(*InverseMap)[NewN] = N0
;
503
504
    // If this node is a root, designate it as such in the graph.
505
1.84M
    if (N->Preds.empty())
506
14.2k
      G->addRoot(NewN);
507
508
    // In the case that some of the intended predecessors of NewN have already
509
    // been created, we should hook them up as predecessors.
510
511
    // Walk through the predecessors of 'N' and hook up their corresponding
512
    // nodes in the new graph (if any) to the freshly created node.
513
1.84M
    for (ExplodedNode::pred_iterator I = N->Preds.begin(), E = N->Preds.end();
514
3.66M
         I != E; 
++I1.82M
) {
515
1.82M
      Pass2Ty::iterator PI = Pass2.find(*I);
516
1.82M
      if (PI == Pass2.end())
517
772
        continue;
518
519
1.82M
      NewN->addPredecessor(const_cast<ExplodedNode *>(PI->second), *G);
520
1.82M
    }
521
522
    // In the case that some of the intended successors of NewN have already
523
    // been created, we should hook them up as successors.  Otherwise, enqueue
524
    // the new nodes from the original graph that should have nodes created
525
    // in the new graph.
526
1.84M
    for (ExplodedNode::succ_iterator I = N->Succs.begin(), E = N->Succs.end();
527
3.68M
         I != E; 
++I1.84M
) {
528
1.84M
      Pass2Ty::iterator PI = Pass2.find(*I);
529
1.84M
      if (PI != Pass2.end()) {
530
772
        const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);
531
772
        continue;
532
772
      }
533
534
      // Enqueue nodes to the worklist that were marked during pass 1.
535
1.84M
      if (Pass1.count(*I))
536
1.82M
        WL2.push_back(*I);
537
1.84M
    }
538
1.84M
  }
539
540
14.2k
  return G;
541
14.2k
}