Coverage Report

Created: 2020-02-15 09:57

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CoreEngine.cpp - Path-Sensitive Dataflow Engine --------------------===//
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 a generic engine for intraprocedural, path-sensitive,
10
//  dataflow analysis via graph reachability engine.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
15
#include "clang/AST/Expr.h"
16
#include "clang/AST/ExprCXX.h"
17
#include "clang/AST/Stmt.h"
18
#include "clang/AST/StmtCXX.h"
19
#include "clang/Analysis/AnalysisDeclContext.h"
20
#include "clang/Analysis/CFG.h"
21
#include "clang/Analysis/ProgramPoint.h"
22
#include "clang/Basic/LLVM.h"
23
#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
24
#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
25
#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
26
#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
27
#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
28
#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
29
#include "llvm/ADT/Optional.h"
30
#include "llvm/ADT/STLExtras.h"
31
#include "llvm/ADT/Statistic.h"
32
#include "llvm/Support/Casting.h"
33
#include "llvm/Support/ErrorHandling.h"
34
#include <algorithm>
35
#include <cassert>
36
#include <memory>
37
#include <utility>
38
39
using namespace clang;
40
using namespace ento;
41
42
#define DEBUG_TYPE "CoreEngine"
43
44
STATISTIC(NumSteps,
45
            "The # of steps executed.");
46
STATISTIC(NumReachedMaxSteps,
47
            "The # of times we reached the max number of steps.");
48
STATISTIC(NumPathsExplored,
49
            "The # of paths explored by the analyzer.");
50
51
//===----------------------------------------------------------------------===//
52
// Core analysis engine.
53
//===----------------------------------------------------------------------===//
54
55
static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts,
56
12.6k
                                                  SubEngine &subengine) {
57
12.6k
  switch (Opts.getExplorationStrategy()) {
58
304
    case ExplorationStrategyKind::DFS:
59
304
      return WorkList::makeDFS();
60
0
    case ExplorationStrategyKind::BFS:
61
0
      return WorkList::makeBFS();
62
0
    case ExplorationStrategyKind::BFSBlockDFSContents:
63
0
      return WorkList::makeBFSBlockDFSContents();
64
4
    case ExplorationStrategyKind::UnexploredFirst:
65
4
      return WorkList::makeUnexploredFirst();
66
12.3k
    case ExplorationStrategyKind::UnexploredFirstQueue:
67
12.3k
      return WorkList::makeUnexploredFirstPriorityQueue();
68
0
    case ExplorationStrategyKind::UnexploredFirstLocationQueue:
69
0
      return WorkList::makeUnexploredFirstPriorityLocationQueue();
70
0
  }
71
0
  llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");
72
0
}
73
74
CoreEngine::CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS,
75
                       AnalyzerOptions &Opts)
76
    : SubEng(subengine), WList(generateWorkList(Opts, subengine)),
77
12.6k
      BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {}
78
79
/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
80
bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
81
12.6k
                                   ProgramStateRef InitState) {
82
12.6k
  if (G.num_roots() == 0) { // Initialize the analysis by constructing
83
12.6k
    // the root if none exists.
84
12.6k
85
12.6k
    const CFGBlock *Entry = &(L->getCFG()->getEntry());
86
12.6k
87
12.6k
    assert(Entry->empty() && "Entry block must be empty.");
88
12.6k
89
12.6k
    assert(Entry->succ_size() == 1 && "Entry block must have 1 successor.");
90
12.6k
91
12.6k
    // Mark the entry block as visited.
92
12.6k
    FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
93
12.6k
                                             L->getDecl(),
94
12.6k
                                             L->getCFG()->getNumBlockIDs());
95
12.6k
96
12.6k
    // Get the solitary successor.
97
12.6k
    const CFGBlock *Succ = *(Entry->succ_begin());
98
12.6k
99
12.6k
    // Construct an edge representing the
100
12.6k
    // starting location in the function.
101
12.6k
    BlockEdge StartLoc(Entry, Succ, L);
102
12.6k
103
12.6k
    // Set the current block counter to being empty.
104
12.6k
    WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
105
12.6k
106
12.6k
    if (!InitState)
107
12.6k
      InitState = SubEng.getInitialState(L);
108
12.6k
109
12.6k
    bool IsNew;
110
12.6k
    ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
111
12.6k
    assert(IsNew);
112
12.6k
    G.addRoot(Node);
113
12.6k
114
12.6k
    NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
115
12.6k
    ExplodedNodeSet DstBegin;
116
12.6k
    SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
117
12.6k
118
12.6k
    enqueue(DstBegin);
119
12.6k
  }
120
12.6k
121
12.6k
  // Check if we have a steps limit
122
12.6k
  bool UnlimitedSteps = Steps == 0;
123
12.6k
  // Cap our pre-reservation in the event that the user specifies
124
12.6k
  // a very large number of maximum steps.
125
12.6k
  const unsigned PreReservationCap = 4000000;
126
12.6k
  if(!UnlimitedSteps)
127
12.6k
    G.reserve(std::min(Steps,PreReservationCap));
128
12.6k
129
1.77M
  while (WList->hasWork()) {
130
1.75M
    if (!UnlimitedSteps) {
131
1.75M
      if (Steps == 0) {
132
11
        NumReachedMaxSteps++;
133
11
        break;
134
11
      }
135
1.75M
      --Steps;
136
1.75M
    }
137
1.75M
138
1.75M
    NumSteps++;
139
1.75M
140
1.75M
    const WorkListUnit& WU = WList->dequeue();
141
1.75M
142
1.75M
    // Set the current block counter.
143
1.75M
    WList->setBlockCounter(WU.getBlockCounter());
144
1.75M
145
1.75M
    // Retrieve the node.
146
1.75M
    ExplodedNode *Node = WU.getNode();
147
1.75M
148
1.75M
    dispatchWorkItem(Node, Node->getLocation(), WU);
149
1.75M
  }
150
12.6k
  SubEng.processEndWorklist();
151
12.6k
  return WList->hasWork();
152
12.6k
}
153
154
void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
155
1.75M
                                  const WorkListUnit& WU) {
156
1.75M
  // Dispatch on the location type.
157
1.75M
  switch (Loc.getKind()) {
158
266k
    case ProgramPoint::BlockEdgeKind:
159
266k
      HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
160
266k
      break;
161
0
162
150k
    case ProgramPoint::BlockEntranceKind:
163
150k
      HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
164
150k
      break;
165
0
166
0
    case ProgramPoint::BlockExitKind:
167
0
      assert(false && "BlockExit location never occur in forward analysis.");
168
0
      break;
169
0
170
63.7k
    case ProgramPoint::CallEnterKind:
171
63.7k
      HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
172
63.7k
      break;
173
0
174
77.9k
    case ProgramPoint::CallExitBeginKind:
175
77.9k
      SubEng.processCallExit(Pred);
176
77.9k
      break;
177
0
178
33
    case ProgramPoint::EpsilonKind: {
179
33
      assert(Pred->hasSinglePred() &&
180
33
             "Assume epsilon has exactly one predecessor by construction");
181
33
      ExplodedNode *PNode = Pred->getFirstPred();
182
33
      dispatchWorkItem(Pred, PNode->getLocation(), WU);
183
33
      break;
184
0
    }
185
1.19M
    default:
186
1.19M
      assert(Loc.getAs<PostStmt>() ||
187
1.19M
             Loc.getAs<PostInitializer>() ||
188
1.19M
             Loc.getAs<PostImplicitCall>() ||
189
1.19M
             Loc.getAs<CallExitEnd>() ||
190
1.19M
             Loc.getAs<LoopExit>() ||
191
1.19M
             Loc.getAs<PostAllocatorCall>());
192
1.19M
      HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
193
1.19M
      break;
194
1.75M
  }
195
1.75M
}
196
197
bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L,
198
                                                 unsigned Steps,
199
                                                 ProgramStateRef InitState,
200
0
                                                 ExplodedNodeSet &Dst) {
201
0
  bool DidNotFinish = ExecuteWorkList(L, Steps, InitState);
202
0
  for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E;
203
0
       ++I) {
204
0
    Dst.Add(*I);
205
0
  }
206
0
  return DidNotFinish;
207
0
}
208
209
266k
void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
210
266k
  const CFGBlock *Blk = L.getDst();
211
266k
  NodeBuilderContext BuilderCtx(*this, Blk, Pred);
212
266k
213
266k
  // Mark this block as visited.
214
266k
  const LocationContext *LC = Pred->getLocationContext();
215
266k
  FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
216
266k
                                           LC->getDecl(),
217
266k
                                           LC->getCFG()->getNumBlockIDs());
218
266k
219
266k
  // Display a prunable path note to the user if it's a virtual bases branch
220
266k
  // and we're taking the path that skips virtual base constructors.
221
266k
  if (L.getSrc()->getTerminator().isVirtualBaseBranch() &&
222
266k
      
L.getDst() == *L.getSrc()->succ_begin()155
) {
223
71
    ProgramPoint P = L.withTag(getNoteTags().makeNoteTag(
224
110
        [](BugReporterContext &, BugReport &) -> std::string {
225
110
          // TODO: Just call out the name of the most derived class
226
110
          // when we know it.
227
110
          return "Virtual base initialization skipped because "
228
110
                 "it has already been handled by the most derived class";
229
110
        }, /*IsPrunable=*/true));
230
71
    // Perform the transition.
231
71
    ExplodedNodeSet Dst;
232
71
    NodeBuilder Bldr(Pred, Dst, BuilderCtx);
233
71
    Pred = Bldr.generateNode(P, Pred->getState(), Pred);
234
71
    if (!Pred)
235
0
      return;
236
266k
  }
237
266k
238
266k
  // Check if we are entering the EXIT block.
239
266k
  if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
240
99.8k
    assert(L.getLocationContext()->getCFG()->getExit().empty() &&
241
99.8k
           "EXIT block cannot contain Stmts.");
242
99.8k
243
99.8k
    // Get return statement..
244
99.8k
    const ReturnStmt *RS = nullptr;
245
99.8k
    if (!L.getSrc()->empty()) {
246
87.8k
      CFGElement LastElement = L.getSrc()->back();
247
87.8k
      if (Optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) {
248
80.0k
        RS = dyn_cast<ReturnStmt>(LastStmt->getStmt());
249
80.0k
      } else 
if (Optional<CFGAutomaticObjDtor> 7.86k
AutoDtor7.86k
=
250
260
                 LastElement.getAs<CFGAutomaticObjDtor>()) {
251
260
        RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt());
252
260
      }
253
87.8k
    }
254
99.8k
255
99.8k
    // Process the final state transition.
256
99.8k
    SubEng.processEndOfFunction(BuilderCtx, Pred, RS);
257
99.8k
258
99.8k
    // This path is done. Don't enqueue any more nodes.
259
99.8k
    return;
260
99.8k
  }
261
166k
262
166k
  // Call into the SubEngine to process entering the CFGBlock.
263
166k
  ExplodedNodeSet dstNodes;
264
166k
  BlockEntrance BE(Blk, Pred->getLocationContext());
265
166k
  NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
266
166k
  SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred);
267
166k
268
166k
  // Auto-generate a node.
269
166k
  if (!nodeBuilder.hasGeneratedNodes()) {
270
165k
    nodeBuilder.generateNode(Pred->State, Pred);
271
165k
  }
272
166k
273
166k
  // Enqueue nodes onto the worklist.
274
166k
  enqueue(dstNodes);
275
166k
}
276
277
void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
278
150k
                                       ExplodedNode *Pred) {
279
150k
  // Increment the block counter.
280
150k
  const LocationContext *LC = Pred->getLocationContext();
281
150k
  unsigned BlockId = L.getBlock()->getBlockID();
282
150k
  BlockCounter Counter = WList->getBlockCounter();
283
150k
  Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(),
284
150k
                                           BlockId);
285
150k
  WList->setBlockCounter(Counter);
286
150k
287
150k
  // Process the entrance of the block.
288
150k
  if (Optional<CFGElement> E = L.getFirstElement()) {
289
136k
    NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
290
136k
    SubEng.processCFGElement(*E, Pred, 0, &Ctx);
291
136k
  }
292
13.3k
  else
293
13.3k
    HandleBlockExit(L.getBlock(), Pred);
294
150k
}
295
296
158k
void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
297
158k
  if (const Stmt *Term = B->getTerminatorStmt()) {
298
48.8k
    switch (Term->getStmtClass()) {
299
0
      default:
300
0
        llvm_unreachable("Analysis for this terminator not implemented.");
301
0
302
607
      case Stmt::CXXBindTemporaryExprClass:
303
607
        HandleCleanupTemporaryBranch(
304
607
            cast<CXXBindTemporaryExpr>(Term), B, Pred);
305
607
        return;
306
0
307
0
      // Model static initializers.
308
196
      case Stmt::DeclStmtClass:
309
196
        HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
310
196
        return;
311
0
312
11.0k
      case Stmt::BinaryOperatorClass: // '&&' and '||'
313
11.0k
        HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
314
11.0k
        return;
315
0
316
828
      case Stmt::BinaryConditionalOperatorClass:
317
828
      case Stmt::ConditionalOperatorClass:
318
828
        HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
319
828
                     Term, B, Pred);
320
828
        return;
321
828
322
828
        // FIXME: Use constant-folding in CFG construction to simplify this
323
828
        // case.
324
828
325
828
      case Stmt::ChooseExprClass:
326
0
        HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
327
0
        return;
328
828
329
828
      case Stmt::CXXTryStmtClass:
330
0
        // Generate a node for each of the successors.
331
0
        // Our logic for EH analysis can certainly be improved.
332
0
        for (CFGBlock::const_succ_iterator it = B->succ_begin(),
333
0
             et = B->succ_end(); it != et; ++it) {
334
0
          if (const CFGBlock *succ = *it) {
335
0
            generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
336
0
                         Pred->State, Pred);
337
0
          }
338
0
        }
339
0
        return;
340
828
341
828
      case Stmt::DoStmtClass:
342
205
        HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
343
205
        return;
344
828
345
828
      case Stmt::CXXForRangeStmtClass:
346
187
        HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
347
187
        return;
348
828
349
4.43k
      case Stmt::ForStmtClass:
350
4.43k
        HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
351
4.43k
        return;
352
828
353
828
      case Stmt::ContinueStmtClass:
354
349
      case Stmt::BreakStmtClass:
355
349
      case Stmt::GotoStmtClass:
356
349
        break;
357
349
358
20.2k
      case Stmt::IfStmtClass:
359
20.2k
        HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
360
20.2k
        return;
361
349
362
349
      case Stmt::IndirectGotoStmtClass: {
363
8
        // Only 1 successor: the indirect goto dispatch block.
364
8
        assert(B->succ_size() == 1);
365
8
366
8
        IndirectGotoNodeBuilder
367
8
           builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
368
8
                   *(B->succ_begin()), this);
369
8
370
8
        SubEng.processIndirectGoto(builder);
371
8
        return;
372
349
      }
373
349
374
444
      case Stmt::ObjCForCollectionStmtClass:
375
444
        // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
376
444
        //
377
444
        //  (1) inside a basic block, which represents the binding of the
378
444
        //      'element' variable to a value.
379
444
        //  (2) in a terminator, which represents the branch.
380
444
        //
381
444
        // For (1), subengines will bind a value (i.e., 0 or 1) indicating
382
444
        // whether or not collection contains any more elements.  We cannot
383
444
        // just test to see if the element is nil because a container can
384
444
        // contain nil elements.
385
444
        HandleBranch(Term, Term, B, Pred);
386
444
        return;
387
349
388
349
      case Stmt::SwitchStmtClass: {
389
239
        SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
390
239
                                    this);
391
239
392
239
        SubEng.processSwitch(builder);
393
239
        return;
394
349
      }
395
349
396
9.95k
      case Stmt::WhileStmtClass:
397
9.95k
        HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
398
9.95k
        return;
399
349
400
349
      case Stmt::GCCAsmStmtClass:
401
1
        assert(cast<GCCAsmStmt>(Term)->isAsmGoto() && "Encountered GCCAsmStmt without labels");
402
1
        // TODO: Handle jumping to labels
403
1
        return;
404
110k
    }
405
110k
  }
406
110k
407
110k
  if (B->getTerminator().isVirtualBaseBranch()) {
408
155
    HandleVirtualBaseBranch(B, Pred);
409
155
    return;
410
155
  }
411
110k
412
110k
  assert(B->succ_size() == 1 &&
413
110k
         "Blocks with no terminator should have at most 1 successor.");
414
110k
415
110k
  generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
416
110k
               Pred->State, Pred);
417
110k
}
418
419
63.7k
void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
420
63.7k
  NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
421
63.7k
  SubEng.processCallEnter(BuilderCtx, CE, Pred);
422
63.7k
}
423
424
void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
425
47.4k
                                const CFGBlock * B, ExplodedNode *Pred) {
426
47.4k
  assert(B->succ_size() == 2);
427
47.4k
  NodeBuilderContext Ctx(*this, B, Pred);
428
47.4k
  ExplodedNodeSet Dst;
429
47.4k
  SubEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()),
430
47.4k
                       *(B->succ_begin() + 1));
431
47.4k
  // Enqueue the new frontier onto the worklist.
432
47.4k
  enqueue(Dst);
433
47.4k
}
434
435
void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
436
                                              const CFGBlock *B,
437
607
                                              ExplodedNode *Pred) {
438
607
  assert(B->succ_size() == 2);
439
607
  NodeBuilderContext Ctx(*this, B, Pred);
440
607
  ExplodedNodeSet Dst;
441
607
  SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
442
607
                                       *(B->succ_begin() + 1));
443
607
  // Enqueue the new frontier onto the worklist.
444
607
  enqueue(Dst);
445
607
}
446
447
void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
448
196
                                  ExplodedNode *Pred) {
449
196
  assert(B->succ_size() == 2);
450
196
  NodeBuilderContext Ctx(*this, B, Pred);
451
196
  ExplodedNodeSet Dst;
452
196
  SubEng.processStaticInitializer(DS, Ctx, Pred, Dst,
453
196
                                  *(B->succ_begin()), *(B->succ_begin()+1));
454
196
  // Enqueue the new frontier onto the worklist.
455
196
  enqueue(Dst);
456
196
}
457
458
void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
459
1.19M
                                ExplodedNode *Pred) {
460
1.19M
  assert(B);
461
1.19M
  assert(!B->empty());
462
1.19M
463
1.19M
  if (StmtIdx == B->size())
464
145k
    HandleBlockExit(B, Pred);
465
1.05M
  else {
466
1.05M
    NodeBuilderContext Ctx(*this, B, Pred);
467
1.05M
    SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
468
1.05M
  }
469
1.19M
}
470
471
void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
472
155
                                         ExplodedNode *Pred) {
473
155
  const LocationContext *LCtx = Pred->getLocationContext();
474
155
  if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
475
133
          LCtx->getStackFrame()->getCallSite())) {
476
133
    switch (CallerCtor->getConstructionKind()) {
477
71
    case CXXConstructExpr::CK_NonVirtualBase:
478
71
    case CXXConstructExpr::CK_VirtualBase: {
479
71
      BlockEdge Loc(B, *B->succ_begin(), LCtx);
480
71
      HandleBlockEdge(Loc, Pred);
481
71
      return;
482
71
    }
483
71
    default:
484
62
      break;
485
84
    }
486
84
  }
487
84
488
84
  // We either don't see a parent stack frame because we're in the top frame,
489
84
  // or the parent stack frame doesn't initialize our virtual bases.
490
84
  BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);
491
84
  HandleBlockEdge(Loc, Pred);
492
84
}
493
494
/// generateNode - Utility method to generate nodes, hook up successors,
495
///  and add nodes to the worklist.
496
void CoreEngine::generateNode(const ProgramPoint &Loc,
497
                              ProgramStateRef State,
498
110k
                              ExplodedNode *Pred) {
499
110k
  bool IsNew;
500
110k
  ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
501
110k
502
110k
  if (Pred)
503
110k
    Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
504
0
  else {
505
0
    assert(IsNew);
506
0
    G.addRoot(Node); // 'Node' has no predecessor.  Make it a root.
507
0
  }
508
110k
509
110k
  // Only add 'Node' to the worklist if it was freshly generated.
510
110k
  if (IsNew) 
WList->enqueue(Node)110k
;
511
110k
}
512
513
void CoreEngine::enqueueStmtNode(ExplodedNode *N,
514
1.12M
                                 const CFGBlock *Block, unsigned Idx) {
515
1.12M
  assert(Block);
516
1.12M
  assert(!N->isSink());
517
1.12M
518
1.12M
  // Check if this node entered a callee.
519
1.12M
  if (N->getLocation().getAs<CallEnter>()) {
520
0
    // Still use the index of the CallExpr. It's needed to create the callee
521
0
    // StackFrameContext.
522
0
    WList->enqueue(N, Block, Idx);
523
0
    return;
524
0
  }
525
1.12M
526
1.12M
  // Do not create extra nodes. Move to the next CFG element.
527
1.12M
  if (N->getLocation().getAs<PostInitializer>() ||
528
1.12M
      
N->getLocation().getAs<PostImplicitCall>()1.11M
||
529
1.12M
      
N->getLocation().getAs<LoopExit>()1.10M
) {
530
14.7k
    WList->enqueue(N, Block, Idx+1);
531
14.7k
    return;
532
14.7k
  }
533
1.10M
534
1.10M
  if (N->getLocation().getAs<EpsilonPoint>()) {
535
33
    WList->enqueue(N, Block, Idx);
536
33
    return;
537
33
  }
538
1.10M
539
1.10M
  if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
540
703
    WList->enqueue(N, Block, Idx+1);
541
703
    return;
542
703
  }
543
1.10M
544
1.10M
  // At this point, we know we're processing a normal statement.
545
1.10M
  CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
546
1.10M
  PostStmt Loc(CS.getStmt(), N->getLocationContext());
547
1.10M
548
1.10M
  if (Loc == N->getLocation().withTag(nullptr)) {
549
488k
    // Note: 'N' should be a fresh node because otherwise it shouldn't be
550
488k
    // a member of Deferred.
551
488k
    WList->enqueue(N, Block, Idx+1);
552
488k
    return;
553
488k
  }
554
619k
555
619k
  bool IsNew;
556
619k
  ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
557
619k
  Succ->addPredecessor(N, G);
558
619k
559
619k
  if (IsNew)
560
619k
    WList->enqueue(Succ, Block, Idx+1);
561
619k
}
562
563
ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
564
77.9k
                                                    const ReturnStmt *RS) {
565
77.9k
  // Create a CallExitBegin node and enqueue it.
566
77.9k
  const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext());
567
77.9k
568
77.9k
  // Use the callee location context.
569
77.9k
  CallExitBegin Loc(LocCtx, RS);
570
77.9k
571
77.9k
  bool isNew;
572
77.9k
  ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
573
77.9k
  Node->addPredecessor(N, G);
574
77.9k
  return isNew ? Node : 
nullptr0
;
575
77.9k
}
576
577
291k
void CoreEngine::enqueue(ExplodedNodeSet &Set) {
578
291k
  for (const auto I : Set)
579
321k
    WList->enqueue(I);
580
291k
}
581
582
void CoreEngine::enqueue(ExplodedNodeSet &Set,
583
1.19M
                         const CFGBlock *Block, unsigned Idx) {
584
1.19M
  for (const auto I : Set)
585
1.12M
    enqueueStmtNode(I, Block, Idx);
586
1.19M
}
587
588
99.8k
void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
589
99.8k
  for (auto I : Set) {
590
98.9k
    // If we are in an inlined call, generate CallExitBegin node.
591
98.9k
    if (I->getLocationContext()->getParent()) {
592
77.9k
      I = generateCallExitBeginNode(I, RS);
593
77.9k
      if (I)
594
77.9k
        WList->enqueue(I);
595
77.9k
    } else {
596
20.9k
      // TODO: We should run remove dead bindings here.
597
20.9k
      G.addEndOfPath(I);
598
20.9k
      NumPathsExplored++;
599
20.9k
    }
600
98.9k
  }
601
99.8k
}
602
603
0
void NodeBuilder::anchor() {}
604
605
ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
606
                                            ProgramStateRef State,
607
                                            ExplodedNode *FromN,
608
1.97M
                                            bool MarkAsSink) {
609
1.97M
  HasGeneratedNodes = true;
610
1.97M
  bool IsNew;
611
1.97M
  ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
612
1.97M
  N->addPredecessor(FromN, C.Eng.G);
613
1.97M
  Frontier.erase(FromN);
614
1.97M
615
1.97M
  if (!IsNew)
616
7.54k
    return nullptr;
617
1.96M
618
1.96M
  if (!MarkAsSink)
619
1.96M
    Frontier.Add(N);
620
1.96M
621
1.96M
  return N;
622
1.96M
}
623
624
0
void NodeBuilderWithSinks::anchor() {}
625
626
3.24M
StmtNodeBuilder::~StmtNodeBuilder() {
627
3.24M
  if (EnclosingBldr)
628
0
    for (const auto I : Frontier)
629
0
      EnclosingBldr->addNodes(I);
630
3.24M
}
631
632
0
void BranchNodeBuilder::anchor() {}
633
634
ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
635
                                              bool branch,
636
79.4k
                                              ExplodedNode *NodePred) {
637
79.4k
  // If the branch has been marked infeasible we should not generate a node.
638
79.4k
  if (!isFeasible(branch))
639
0
    return nullptr;
640
79.4k
641
79.4k
  ProgramPoint Loc = BlockEdge(C.Block, branch ? 
DstT41.4k
:
DstF37.9k
,
642
79.4k
                               NodePred->getLocationContext());
643
79.4k
  ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
644
79.4k
  return Succ;
645
79.4k
}
646
647
ExplodedNode*
648
IndirectGotoNodeBuilder::generateNode(const iterator &I,
649
                                      ProgramStateRef St,
650
8
                                      bool IsSink) {
651
8
  bool IsNew;
652
8
  ExplodedNode *Succ =
653
8
      Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
654
8
                    St, IsSink, &IsNew);
655
8
  Succ->addPredecessor(Pred, Eng.G);
656
8
657
8
  if (!IsNew)
658
0
    return nullptr;
659
8
660
8
  if (!IsSink)
661
8
    Eng.WList->enqueue(Succ);
662
8
663
8
  return Succ;
664
8
}
665
666
ExplodedNode*
667
SwitchNodeBuilder::generateCaseStmtNode(const iterator &I,
668
387
                                        ProgramStateRef St) {
669
387
  bool IsNew;
670
387
  ExplodedNode *Succ =
671
387
      Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
672
387
                    St, false, &IsNew);
673
387
  Succ->addPredecessor(Pred, Eng.G);
674
387
  if (!IsNew)
675
0
    return nullptr;
676
387
677
387
  Eng.WList->enqueue(Succ);
678
387
  return Succ;
679
387
}
680
681
ExplodedNode*
682
SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
683
149
                                           bool IsSink) {
684
149
  // Get the block for the default case.
685
149
  assert(Src->succ_rbegin() != Src->succ_rend());
686
149
  CFGBlock *DefaultBlock = *Src->succ_rbegin();
687
149
688
149
  // Sanity check for default blocks that are unreachable and not caught
689
149
  // by earlier stages.
690
149
  if (!DefaultBlock)
691
0
    return nullptr;
692
149
693
149
  bool IsNew;
694
149
  ExplodedNode *Succ =
695
149
      Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
696
149
                    St, IsSink, &IsNew);
697
149
  Succ->addPredecessor(Pred, Eng.G);
698
149
699
149
  if (!IsNew)
700
0
    return nullptr;
701
149
702
149
  if (!IsSink)
703
149
    Eng.WList->enqueue(Succ);
704
149
705
149
  return Succ;
706
149
}