Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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
10.8k
                                                  SubEngine &subengine) {
57
10.8k
  switch (Opts.getExplorationStrategy()) {
58
10.8k
    case ExplorationStrategyKind::DFS:
59
299
      return WorkList::makeDFS();
60
10.8k
    case ExplorationStrategyKind::BFS:
61
0
      return WorkList::makeBFS();
62
10.8k
    case ExplorationStrategyKind::BFSBlockDFSContents:
63
0
      return WorkList::makeBFSBlockDFSContents();
64
10.8k
    case ExplorationStrategyKind::UnexploredFirst:
65
4
      return WorkList::makeUnexploredFirst();
66
10.8k
    case ExplorationStrategyKind::UnexploredFirstQueue:
67
10.5k
      return WorkList::makeUnexploredFirstPriorityQueue();
68
10.8k
    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
10.8k
      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
10.8k
                                   ProgramStateRef InitState) {
82
10.8k
  if (G.num_roots() == 0) { // Initialize the analysis by constructing
83
10.8k
    // the root if none exists.
84
10.8k
85
10.8k
    const CFGBlock *Entry = &(L->getCFG()->getEntry());
86
10.8k
87
10.8k
    assert(Entry->empty() && "Entry block must be empty.");
88
10.8k
89
10.8k
    assert(Entry->succ_size() == 1 && "Entry block must have 1 successor.");
90
10.8k
91
10.8k
    // Mark the entry block as visited.
92
10.8k
    FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
93
10.8k
                                             L->getDecl(),
94
10.8k
                                             L->getCFG()->getNumBlockIDs());
95
10.8k
96
10.8k
    // Get the solitary successor.
97
10.8k
    const CFGBlock *Succ = *(Entry->succ_begin());
98
10.8k
99
10.8k
    // Construct an edge representing the
100
10.8k
    // starting location in the function.
101
10.8k
    BlockEdge StartLoc(Entry, Succ, L);
102
10.8k
103
10.8k
    // Set the current block counter to being empty.
104
10.8k
    WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
105
10.8k
106
10.8k
    if (!InitState)
107
10.8k
      InitState = SubEng.getInitialState(L);
108
10.8k
109
10.8k
    bool IsNew;
110
10.8k
    ExplodedNode *Node = G.getNode(StartLoc, InitState, false, &IsNew);
111
10.8k
    assert(IsNew);
112
10.8k
    G.addRoot(Node);
113
10.8k
114
10.8k
    NodeBuilderContext BuilderCtx(*this, StartLoc.getDst(), Node);
115
10.8k
    ExplodedNodeSet DstBegin;
116
10.8k
    SubEng.processBeginOfFunction(BuilderCtx, Node, DstBegin, StartLoc);
117
10.8k
118
10.8k
    enqueue(DstBegin);
119
10.8k
  }
120
10.8k
121
10.8k
  // Check if we have a steps limit
122
10.8k
  bool UnlimitedSteps = Steps == 0;
123
10.8k
  // Cap our pre-reservation in the event that the user specifies
124
10.8k
  // a very large number of maximum steps.
125
10.8k
  const unsigned PreReservationCap = 4000000;
126
10.8k
  if(!UnlimitedSteps)
127
10.8k
    G.reserve(std::min(Steps,PreReservationCap));
128
10.8k
129
1.27M
  while (WList->hasWork()) {
130
1.26M
    if (!UnlimitedSteps) {
131
1.26M
      if (Steps == 0) {
132
9
        NumReachedMaxSteps++;
133
9
        break;
134
9
      }
135
1.26M
      --Steps;
136
1.26M
    }
137
1.26M
138
1.26M
    NumSteps++;
139
1.26M
140
1.26M
    const WorkListUnit& WU = WList->dequeue();
141
1.26M
142
1.26M
    // Set the current block counter.
143
1.26M
    WList->setBlockCounter(WU.getBlockCounter());
144
1.26M
145
1.26M
    // Retrieve the node.
146
1.26M
    ExplodedNode *Node = WU.getNode();
147
1.26M
148
1.26M
    dispatchWorkItem(Node, Node->getLocation(), WU);
149
1.26M
  }
150
10.8k
  SubEng.processEndWorklist();
151
10.8k
  return WList->hasWork();
152
10.8k
}
153
154
void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
155
1.26M
                                  const WorkListUnit& WU) {
156
1.26M
  // Dispatch on the location type.
157
1.26M
  switch (Loc.getKind()) {
158
1.26M
    case ProgramPoint::BlockEdgeKind:
159
186k
      HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
160
186k
      break;
161
1.26M
162
1.26M
    case ProgramPoint::BlockEntranceKind:
163
114k
      HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
164
114k
      break;
165
1.26M
166
1.26M
    case ProgramPoint::BlockExitKind:
167
0
      assert(false && "BlockExit location never occur in forward analysis.");
168
0
      break;
169
1.26M
170
1.26M
    case ProgramPoint::CallEnterKind:
171
30.4k
      HandleCallEnter(Loc.castAs<CallEnter>(), Pred);
172
30.4k
      break;
173
1.26M
174
1.26M
    case ProgramPoint::CallExitBeginKind:
175
38.8k
      SubEng.processCallExit(Pred);
176
38.8k
      break;
177
1.26M
178
1.26M
    case ProgramPoint::EpsilonKind: {
179
31
      assert(Pred->hasSinglePred() &&
180
31
             "Assume epsilon has exactly one predecessor by construction");
181
31
      ExplodedNode *PNode = Pred->getFirstPred();
182
31
      dispatchWorkItem(Pred, PNode->getLocation(), WU);
183
31
      break;
184
1.26M
    }
185
1.26M
    default:
186
892k
      assert(Loc.getAs<PostStmt>() ||
187
892k
             Loc.getAs<PostInitializer>() ||
188
892k
             Loc.getAs<PostImplicitCall>() ||
189
892k
             Loc.getAs<CallExitEnd>() ||
190
892k
             Loc.getAs<LoopExit>() ||
191
892k
             Loc.getAs<PostAllocatorCall>());
192
892k
      HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
193
892k
      break;
194
1.26M
  }
195
1.26M
}
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
186k
void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
210
186k
  const CFGBlock *Blk = L.getDst();
211
186k
  NodeBuilderContext BuilderCtx(*this, Blk, Pred);
212
186k
213
186k
  // Mark this block as visited.
214
186k
  const LocationContext *LC = Pred->getLocationContext();
215
186k
  FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
216
186k
                                           LC->getDecl(),
217
186k
                                           LC->getCFG()->getNumBlockIDs());
218
186k
219
186k
  // Display a prunable path note to the user if it's a virtual bases branch
220
186k
  // and we're taking the path that skips virtual base constructors.
221
186k
  if (L.getSrc()->getTerminator().isVirtualBaseBranch() &&
222
186k
      
L.getDst() == *L.getSrc()->succ_begin()149
) {
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
186k
  }
237
186k
238
186k
  // Check if we are entering the EXIT block.
239
186k
  if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
240
57.5k
    assert(L.getLocationContext()->getCFG()->getExit().empty() &&
241
57.5k
           "EXIT block cannot contain Stmts.");
242
57.5k
243
57.5k
    // Get return statement..
244
57.5k
    const ReturnStmt *RS = nullptr;
245
57.5k
    if (!L.getSrc()->empty()) {
246
53.9k
      CFGElement LastElement = L.getSrc()->back();
247
53.9k
      if (Optional<CFGStmt> LastStmt = LastElement.getAs<CFGStmt>()) {
248
49.3k
        RS = dyn_cast<ReturnStmt>(LastStmt->getStmt());
249
49.3k
      } else 
if (Optional<CFGAutomaticObjDtor> 4.59k
AutoDtor4.59k
=
250
248
                 LastElement.getAs<CFGAutomaticObjDtor>()) {
251
248
        RS = dyn_cast<ReturnStmt>(AutoDtor->getTriggerStmt());
252
248
      }
253
53.9k
    }
254
57.5k
255
57.5k
    // Process the final state transition.
256
57.5k
    SubEng.processEndOfFunction(BuilderCtx, Pred, RS);
257
57.5k
258
57.5k
    // This path is done. Don't enqueue any more nodes.
259
57.5k
    return;
260
57.5k
  }
261
129k
262
129k
  // Call into the SubEngine to process entering the CFGBlock.
263
129k
  ExplodedNodeSet dstNodes;
264
129k
  BlockEntrance BE(Blk, Pred->getLocationContext());
265
129k
  NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
266
129k
  SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred);
267
129k
268
129k
  // Auto-generate a node.
269
129k
  if (!nodeBuilder.hasGeneratedNodes()) {
270
127k
    nodeBuilder.generateNode(Pred->State, Pred);
271
127k
  }
272
129k
273
129k
  // Enqueue nodes onto the worklist.
274
129k
  enqueue(dstNodes);
275
129k
}
276
277
void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
278
114k
                                       ExplodedNode *Pred) {
279
114k
  // Increment the block counter.
280
114k
  const LocationContext *LC = Pred->getLocationContext();
281
114k
  unsigned BlockId = L.getBlock()->getBlockID();
282
114k
  BlockCounter Counter = WList->getBlockCounter();
283
114k
  Counter = BCounterFactory.IncrementCount(Counter, LC->getStackFrame(),
284
114k
                                           BlockId);
285
114k
  WList->setBlockCounter(Counter);
286
114k
287
114k
  // Process the entrance of the block.
288
114k
  if (Optional<CFGElement> E = L.getFirstElement()) {
289
101k
    NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
290
101k
    SubEng.processCFGElement(*E, Pred, 0, &Ctx);
291
101k
  }
292
13.0k
  else
293
13.0k
    HandleBlockExit(L.getBlock(), Pred);
294
114k
}
295
296
119k
void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
297
119k
  if (const Stmt *Term = B->getTerminatorStmt()) {
298
42.6k
    switch (Term->getStmtClass()) {
299
42.6k
      default:
300
0
        llvm_unreachable("Analysis for this terminator not implemented.");
301
42.6k
302
42.6k
      case Stmt::CXXBindTemporaryExprClass:
303
358
        HandleCleanupTemporaryBranch(
304
358
            cast<CXXBindTemporaryExpr>(Term), B, Pred);
305
358
        return;
306
42.6k
307
42.6k
      // Model static initializers.
308
42.6k
      case Stmt::DeclStmtClass:
309
194
        HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
310
194
        return;
311
42.6k
312
42.6k
      case Stmt::BinaryOperatorClass: // '&&' and '||'
313
10.7k
        HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
314
10.7k
        return;
315
42.6k
316
42.6k
      case Stmt::BinaryConditionalOperatorClass:
317
816
      case Stmt::ConditionalOperatorClass:
318
816
        HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
319
816
                     Term, B, Pred);
320
816
        return;
321
816
322
816
        // FIXME: Use constant-folding in CFG construction to simplify this
323
816
        // case.
324
816
325
816
      case Stmt::ChooseExprClass:
326
0
        HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
327
0
        return;
328
816
329
816
      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
816
341
816
      case Stmt::DoStmtClass:
342
193
        HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
343
193
        return;
344
816
345
816
      case Stmt::CXXForRangeStmtClass:
346
94
        HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
347
94
        return;
348
816
349
4.31k
      case Stmt::ForStmtClass:
350
4.31k
        HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
351
4.31k
        return;
352
816
353
816
      case Stmt::ContinueStmtClass:
354
345
      case Stmt::BreakStmtClass:
355
345
      case Stmt::GotoStmtClass:
356
345
        break;
357
345
358
14.9k
      case Stmt::IfStmtClass:
359
14.9k
        HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
360
14.9k
        return;
361
345
362
345
      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
345
      }
373
345
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
345
388
345
      case Stmt::SwitchStmtClass: {
389
238
        SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
390
238
                                    this);
391
238
392
238
        SubEng.processSwitch(builder);
393
238
        return;
394
345
      }
395
345
396
9.91k
      case Stmt::WhileStmtClass:
397
9.91k
        HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
398
9.91k
        return;
399
345
400
345
      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
76.7k
    }
405
76.7k
  }
406
76.7k
407
76.7k
  if (B->getTerminator().isVirtualBaseBranch()) {
408
149
    HandleVirtualBaseBranch(B, Pred);
409
149
    return;
410
149
  }
411
76.5k
412
76.5k
  assert(B->succ_size() == 1 &&
413
76.5k
         "Blocks with no terminator should have at most 1 successor.");
414
76.5k
415
76.5k
  generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
416
76.5k
               Pred->State, Pred);
417
76.5k
}
418
419
30.4k
void CoreEngine::HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred) {
420
30.4k
  NodeBuilderContext BuilderCtx(*this, CE.getEntry(), Pred);
421
30.4k
  SubEng.processCallEnter(BuilderCtx, CE, Pred);
422
30.4k
}
423
424
void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
425
41.4k
                                const CFGBlock * B, ExplodedNode *Pred) {
426
41.4k
  assert(B->succ_size() == 2);
427
41.4k
  NodeBuilderContext Ctx(*this, B, Pred);
428
41.4k
  ExplodedNodeSet Dst;
429
41.4k
  SubEng.processBranch(Cond, Ctx, Pred, Dst, *(B->succ_begin()),
430
41.4k
                       *(B->succ_begin() + 1));
431
41.4k
  // Enqueue the new frontier onto the worklist.
432
41.4k
  enqueue(Dst);
433
41.4k
}
434
435
void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
436
                                              const CFGBlock *B,
437
358
                                              ExplodedNode *Pred) {
438
358
  assert(B->succ_size() == 2);
439
358
  NodeBuilderContext Ctx(*this, B, Pred);
440
358
  ExplodedNodeSet Dst;
441
358
  SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
442
358
                                       *(B->succ_begin() + 1));
443
358
  // Enqueue the new frontier onto the worklist.
444
358
  enqueue(Dst);
445
358
}
446
447
void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
448
194
                                  ExplodedNode *Pred) {
449
194
  assert(B->succ_size() == 2);
450
194
  NodeBuilderContext Ctx(*this, B, Pred);
451
194
  ExplodedNodeSet Dst;
452
194
  SubEng.processStaticInitializer(DS, Ctx, Pred, Dst,
453
194
                                  *(B->succ_begin()), *(B->succ_begin()+1));
454
194
  // Enqueue the new frontier onto the worklist.
455
194
  enqueue(Dst);
456
194
}
457
458
void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
459
892k
                                ExplodedNode *Pred) {
460
892k
  assert(B);
461
892k
  assert(!B->empty());
462
892k
463
892k
  if (StmtIdx == B->size())
464
105k
    HandleBlockExit(B, Pred);
465
786k
  else {
466
786k
    NodeBuilderContext Ctx(*this, B, Pred);
467
786k
    SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
468
786k
  }
469
892k
}
470
471
void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B,
472
149
                                         ExplodedNode *Pred) {
473
149
  const LocationContext *LCtx = Pred->getLocationContext();
474
149
  if (const auto *CallerCtor = dyn_cast_or_null<CXXConstructExpr>(
475
133
          LCtx->getStackFrame()->getCallSite())) {
476
133
    switch (CallerCtor->getConstructionKind()) {
477
133
    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
78
    }
486
78
  }
487
78
488
78
  // We either don't see a parent stack frame because we're in the top frame,
489
78
  // or the parent stack frame doesn't initialize our virtual bases.
490
78
  BlockEdge Loc(B, *(B->succ_begin() + 1), LCtx);
491
78
  HandleBlockEdge(Loc, Pred);
492
78
}
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
76.5k
                              ExplodedNode *Pred) {
499
76.5k
  bool IsNew;
500
76.5k
  ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
501
76.5k
502
76.5k
  if (Pred)
503
76.5k
    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
76.5k
509
76.5k
  // Only add 'Node' to the worklist if it was freshly generated.
510
76.5k
  if (IsNew) WList->enqueue(Node);
511
76.5k
}
512
513
void CoreEngine::enqueueStmtNode(ExplodedNode *N,
514
855k
                                 const CFGBlock *Block, unsigned Idx) {
515
855k
  assert(Block);
516
855k
  assert(!N->isSink());
517
855k
518
855k
  // Check if this node entered a callee.
519
855k
  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
855k
526
855k
  // Do not create extra nodes. Move to the next CFG element.
527
855k
  if (N->getLocation().getAs<PostInitializer>() ||
528
855k
      
N->getLocation().getAs<PostImplicitCall>()845k
||
529
855k
      
N->getLocation().getAs<LoopExit>()845k
) {
530
10.9k
    WList->enqueue(N, Block, Idx+1);
531
10.9k
    return;
532
10.9k
  }
533
844k
534
844k
  if (N->getLocation().getAs<EpsilonPoint>()) {
535
31
    WList->enqueue(N, Block, Idx);
536
31
    return;
537
31
  }
538
844k
539
844k
  if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
540
685
    WList->enqueue(N, Block, Idx+1);
541
685
    return;
542
685
  }
543
844k
544
844k
  // At this point, we know we're processing a normal statement.
545
844k
  CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
546
844k
  PostStmt Loc(CS.getStmt(), N->getLocationContext());
547
844k
548
844k
  if (Loc == N->getLocation().withTag(nullptr)) {
549
330k
    // Note: 'N' should be a fresh node because otherwise it shouldn't be
550
330k
    // a member of Deferred.
551
330k
    WList->enqueue(N, Block, Idx+1);
552
330k
    return;
553
330k
  }
554
513k
555
513k
  bool IsNew;
556
513k
  ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
557
513k
  Succ->addPredecessor(N, G);
558
513k
559
513k
  if (IsNew)
560
513k
    WList->enqueue(Succ, Block, Idx+1);
561
513k
}
562
563
ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N,
564
38.8k
                                                    const ReturnStmt *RS) {
565
38.8k
  // Create a CallExitBegin node and enqueue it.
566
38.8k
  const auto *LocCtx = cast<StackFrameContext>(N->getLocationContext());
567
38.8k
568
38.8k
  // Use the callee location context.
569
38.8k
  CallExitBegin Loc(LocCtx, RS);
570
38.8k
571
38.8k
  bool isNew;
572
38.8k
  ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
573
38.8k
  Node->addPredecessor(N, G);
574
38.8k
  return isNew ? Node : 
nullptr0
;
575
38.8k
}
576
577
212k
void CoreEngine::enqueue(ExplodedNodeSet &Set) {
578
212k
  for (const auto I : Set)
579
237k
    WList->enqueue(I);
580
212k
}
581
582
void CoreEngine::enqueue(ExplodedNodeSet &Set,
583
888k
                         const CFGBlock *Block, unsigned Idx) {
584
888k
  for (const auto I : Set)
585
855k
    enqueueStmtNode(I, Block, Idx);
586
888k
}
587
588
57.5k
void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS) {
589
57.5k
  for (auto I : Set) {
590
56.6k
    // If we are in an inlined call, generate CallExitBegin node.
591
56.6k
    if (I->getLocationContext()->getParent()) {
592
38.8k
      I = generateCallExitBeginNode(I, RS);
593
38.8k
      if (I)
594
38.8k
        WList->enqueue(I);
595
38.8k
    } else {
596
17.8k
      // TODO: We should run remove dead bindings here.
597
17.8k
      G.addEndOfPath(I);
598
17.8k
      NumPathsExplored++;
599
17.8k
    }
600
56.6k
  }
601
57.5k
}
602
603
0
void NodeBuilder::anchor() {}
604
605
ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
606
                                            ProgramStateRef State,
607
                                            ExplodedNode *FromN,
608
1.44M
                                            bool MarkAsSink) {
609
1.44M
  HasGeneratedNodes = true;
610
1.44M
  bool IsNew;
611
1.44M
  ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
612
1.44M
  N->addPredecessor(FromN, C.Eng.G);
613
1.44M
  Frontier.erase(FromN);
614
1.44M
615
1.44M
  if (!IsNew)
616
5.99k
    return nullptr;
617
1.43M
618
1.43M
  if (!MarkAsSink)
619
1.43M
    Frontier.Add(N);
620
1.43M
621
1.43M
  return N;
622
1.43M
}
623
624
0
void NodeBuilderWithSinks::anchor() {}
625
626
2.41M
StmtNodeBuilder::~StmtNodeBuilder() {
627
2.41M
  if (EnclosingBldr)
628
0
    for (const auto I : Frontier)
629
0
      EnclosingBldr->addNodes(I);
630
2.41M
}
631
632
0
void BranchNodeBuilder::anchor() {}
633
634
ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
635
                                              bool branch,
636
68.1k
                                              ExplodedNode *NodePred) {
637
68.1k
  // If the branch has been marked infeasible we should not generate a node.
638
68.1k
  if (!isFeasible(branch))
639
0
    return nullptr;
640
68.1k
641
68.1k
  ProgramPoint Loc = BlockEdge(C.Block, branch ? 
DstT35.5k
:
DstF32.6k
,
642
68.1k
                               NodePred->getLocationContext());
643
68.1k
  ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
644
68.1k
  return Succ;
645
68.1k
}
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
382
                                        ProgramStateRef St) {
669
382
  bool IsNew;
670
382
  ExplodedNode *Succ =
671
382
      Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
672
382
                    St, false, &IsNew);
673
382
  Succ->addPredecessor(Pred, Eng.G);
674
382
  if (!IsNew)
675
0
    return nullptr;
676
382
677
382
  Eng.WList->enqueue(Succ);
678
382
  return Succ;
679
382
}
680
681
ExplodedNode*
682
SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
683
148
                                           bool IsSink) {
684
148
  // Get the block for the default case.
685
148
  assert(Src->succ_rbegin() != Src->succ_rend());
686
148
  CFGBlock *DefaultBlock = *Src->succ_rbegin();
687
148
688
148
  // Sanity check for default blocks that are unreachable and not caught
689
148
  // by earlier stages.
690
148
  if (!DefaultBlock)
691
0
    return nullptr;
692
148
693
148
  bool IsNew;
694
148
  ExplodedNode *Succ =
695
148
      Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
696
148
                    St, IsSink, &IsNew);
697
148
  Succ->addPredecessor(Pred, Eng.G);
698
148
699
148
  if (!IsNew)
700
0
    return nullptr;
701
148
702
148
  if (!IsSink)
703
148
    Eng.WList->enqueue(Succ);
704
148
705
148
  return Succ;
706
148
}