CoreEngine.cpp revision 638e2d31fceed041e7e16aada4188c94cb5797bb 
1//==- CoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file defines a generic engine for intraprocedural, path-sensitive,
11//  dataflow analysis via graph reachability engine.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "CoreEngine"
16
17#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
18#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
19#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
20#include "clang/Index/TranslationUnit.h"
21#include "clang/AST/Expr.h"
22#include "clang/AST/StmtCXX.h"
23#include "llvm/Support/Casting.h"
24#include "llvm/ADT/DenseMap.h"
25#include "llvm/ADT/Statistic.h"
26
27using namespace clang;
28using namespace ento;
29
30STATISTIC(NumReachedMaxSteps,
31            "The # of times we reached the max number of steps.");
32STATISTIC(NumPathsExplored,
33            "The # of paths explored by the analyzer.");
34
35//===----------------------------------------------------------------------===//
36// Worklist classes for exploration of reachable states.
37//===----------------------------------------------------------------------===//
38
39WorkList::Visitor::~Visitor() {}
40
41namespace {
42class DFS : public WorkList {
43  SmallVector<WorkListUnit,20> Stack;
44public:
45  virtual bool hasWork() const {
46    return !Stack.empty();
47  }
48
49  virtual void enqueue(const WorkListUnit& U) {
50    Stack.push_back(U);
51  }
52
53  virtual WorkListUnit dequeue() {
54    assert (!Stack.empty());
55    const WorkListUnit& U = Stack.back();
56    Stack.pop_back(); // This technically "invalidates" U, but we are fine.
57    return U;
58  }
59
60  virtual bool visitItemsInWorkList(Visitor &V) {
61    for (SmallVectorImpl<WorkListUnit>::iterator
62         I = Stack.begin(), E = Stack.end(); I != E; ++I) {
63      if (V.visit(*I))
64        return true;
65    }
66    return false;
67  }
68};
69
70class BFS : public WorkList {
71  std::deque<WorkListUnit> Queue;
72public:
73  virtual bool hasWork() const {
74    return !Queue.empty();
75  }
76
77  virtual void enqueue(const WorkListUnit& U) {
78    Queue.push_front(U);
79  }
80
81  virtual WorkListUnit dequeue() {
82    WorkListUnit U = Queue.front();
83    Queue.pop_front();
84    return U;
85  }
86
87  virtual bool visitItemsInWorkList(Visitor &V) {
88    for (std::deque<WorkListUnit>::iterator
89         I = Queue.begin(), E = Queue.end(); I != E; ++I) {
90      if (V.visit(*I))
91        return true;
92    }
93    return false;
94  }
95};
96
97} // end anonymous namespace
98
99// Place the dstor for WorkList here because it contains virtual member
100// functions, and we the code for the dstor generated in one compilation unit.
101WorkList::~WorkList() {}
102
103WorkList *WorkList::makeDFS() { return new DFS(); }
104WorkList *WorkList::makeBFS() { return new BFS(); }
105
106namespace {
107  class BFSBlockDFSContents : public WorkList {
108    std::deque<WorkListUnit> Queue;
109    SmallVector<WorkListUnit,20> Stack;
110  public:
111    virtual bool hasWork() const {
112      return !Queue.empty() || !Stack.empty();
113    }
114
115    virtual void enqueue(const WorkListUnit& U) {
116      if (isa<BlockEntrance>(U.getNode()->getLocation()))
117        Queue.push_front(U);
118      else
119        Stack.push_back(U);
120    }
121
122    virtual WorkListUnit dequeue() {
123      // Process all basic blocks to completion.
124      if (!Stack.empty()) {
125        const WorkListUnit& U = Stack.back();
126        Stack.pop_back(); // This technically "invalidates" U, but we are fine.
127        return U;
128      }
129
130      assert(!Queue.empty());
131      // Don't use const reference.  The subsequent pop_back() might make it
132      // unsafe.
133      WorkListUnit U = Queue.front();
134      Queue.pop_front();
135      return U;
136    }
137    virtual bool visitItemsInWorkList(Visitor &V) {
138      for (SmallVectorImpl<WorkListUnit>::iterator
139           I = Stack.begin(), E = Stack.end(); I != E; ++I) {
140        if (V.visit(*I))
141          return true;
142      }
143      for (std::deque<WorkListUnit>::iterator
144           I = Queue.begin(), E = Queue.end(); I != E; ++I) {
145        if (V.visit(*I))
146          return true;
147      }
148      return false;
149    }
150
151  };
152} // end anonymous namespace
153
154WorkList* WorkList::makeBFSBlockDFSContents() {
155  return new BFSBlockDFSContents();
156}
157
158//===----------------------------------------------------------------------===//
159// Core analysis engine.
160//===----------------------------------------------------------------------===//
161
162/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
163bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
164                                   ProgramStateRef InitState) {
165
166  if (G->num_roots() == 0) { // Initialize the analysis by constructing
167    // the root if none exists.
168
169    const CFGBlock *Entry = &(L->getCFG()->getEntry());
170
171    assert (Entry->empty() &&
172            "Entry block must be empty.");
173
174    assert (Entry->succ_size() == 1 &&
175            "Entry block must have 1 successor.");
176
177    // Get the solitary successor.
178    const CFGBlock *Succ = *(Entry->succ_begin());
179
180    // Construct an edge representing the
181    // starting location in the function.
182    BlockEdge StartLoc(Entry, Succ, L);
183
184    // Set the current block counter to being empty.
185    WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
186
187    if (!InitState)
188      // Generate the root.
189      generateNode(StartLoc, SubEng.getInitialState(L), 0);
190    else
191      generateNode(StartLoc, InitState, 0);
192  }
193
194  // Check if we have a steps limit
195  bool UnlimitedSteps = Steps == 0;
196
197  while (WList->hasWork()) {
198    if (!UnlimitedSteps) {
199      if (Steps == 0) {
200        NumReachedMaxSteps++;
201        break;
202      }
203      --Steps;
204    }
205
206    const WorkListUnit& WU = WList->dequeue();
207
208    // Set the current block counter.
209    WList->setBlockCounter(WU.getBlockCounter());
210
211    // Retrieve the node.
212    ExplodedNode *Node = WU.getNode();
213
214    // Dispatch on the location type.
215    switch (Node->getLocation().getKind()) {
216      case ProgramPoint::BlockEdgeKind:
217        HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node);
218        break;
219
220      case ProgramPoint::BlockEntranceKind:
221        HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node);
222        break;
223
224      case ProgramPoint::BlockExitKind:
225        assert (false && "BlockExit location never occur in forward analysis.");
226        break;
227
228      case ProgramPoint::CallEnterKind: {
229        CallEnter CEnter = cast<CallEnter>(Node->getLocation());
230        if (AnalyzedCallees)
231          if (const CallExpr* CE =
232              dyn_cast_or_null<CallExpr>(CEnter.getCallExpr()))
233            if (const Decl *CD = CE->getCalleeDecl())
234              AnalyzedCallees->insert(CD);
235        SubEng.processCallEnter(CEnter, Node);
236        break;
237      }
238
239      case ProgramPoint::CallExitKind:
240        SubEng.processCallExit(Node);
241        break;
242
243      default:
244        assert(isa<PostStmt>(Node->getLocation()) ||
245               isa<PostInitializer>(Node->getLocation()));
246        HandlePostStmt(WU.getBlock(), WU.getIndex(), Node);
247        break;
248    }
249  }
250
251  SubEng.processEndWorklist(hasWorkRemaining());
252  return WList->hasWork();
253}
254
255void CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L,
256                                                 unsigned Steps,
257                                                 ProgramStateRef InitState,
258                                                 ExplodedNodeSet &Dst) {
259  ExecuteWorkList(L, Steps, InitState);
260  for (ExplodedGraph::eop_iterator I = G->eop_begin(),
261                                   E = G->eop_end(); I != E; ++I) {
262    Dst.Add(*I);
263  }
264}
265
266void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
267
268  const CFGBlock *Blk = L.getDst();
269  NodeBuilderContext BuilderCtx(*this, Blk, Pred);
270
271  // Check if we are entering the EXIT block.
272  if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
273
274    assert (L.getLocationContext()->getCFG()->getExit().size() == 0
275            && "EXIT block cannot contain Stmts.");
276
277    // Process the final state transition.
278    SubEng.processEndOfFunction(BuilderCtx);
279
280    // This path is done. Don't enqueue any more nodes.
281    return;
282  }
283
284  // Call into the SubEngine to process entering the CFGBlock.
285  ExplodedNodeSet dstNodes;
286  BlockEntrance BE(Blk, Pred->getLocationContext());
287  NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
288  SubEng.processCFGBlockEntrance(nodeBuilder);
289
290  // Auto-generate a node.
291  if (!nodeBuilder.hasGeneratedNodes()) {
292    nodeBuilder.generateNode(Pred->State, Pred);
293  }
294
295  // Enqueue nodes onto the worklist.
296  enqueue(dstNodes);
297
298  // Make sink nodes as exhausted.
299  const SmallVectorImpl<ExplodedNode*> &Sinks =  nodeBuilder.getSinks();
300  for (SmallVectorImpl<ExplodedNode*>::const_iterator
301         I =Sinks.begin(), E = Sinks.end(); I != E; ++I) {
302    blocksExhausted.push_back(std::make_pair(L, *I));
303  }
304}
305
306void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
307                                       ExplodedNode *Pred) {
308
309  // Increment the block counter.
310  BlockCounter Counter = WList->getBlockCounter();
311  Counter = BCounterFactory.IncrementCount(Counter,
312                             Pred->getLocationContext()->getCurrentStackFrame(),
313                                           L.getBlock()->getBlockID());
314  WList->setBlockCounter(Counter);
315
316  // Process the entrance of the block.
317  if (CFGElement E = L.getFirstElement()) {
318    NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
319    SubEng.processCFGElement(E, Pred, 0, &Ctx);
320  }
321  else
322    HandleBlockExit(L.getBlock(), Pred);
323}
324
325void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
326
327  if (const Stmt *Term = B->getTerminator()) {
328    switch (Term->getStmtClass()) {
329      default:
330        llvm_unreachable("Analysis for this terminator not implemented.");
331
332      case Stmt::BinaryOperatorClass: // '&&' and '||'
333        HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
334        return;
335
336      case Stmt::BinaryConditionalOperatorClass:
337      case Stmt::ConditionalOperatorClass:
338        HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
339                     Term, B, Pred);
340        return;
341
342        // FIXME: Use constant-folding in CFG construction to simplify this
343        // case.
344
345      case Stmt::ChooseExprClass:
346        HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
347        return;
348
349      case Stmt::CXXTryStmtClass: {
350        // Generate a node for each of the successors.
351        // Our logic for EH analysis can certainly be improved.
352        for (CFGBlock::const_succ_iterator it = B->succ_begin(),
353             et = B->succ_end(); it != et; ++it) {
354          if (const CFGBlock *succ = *it) {
355            generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
356                         Pred->State, Pred);
357          }
358        }
359        return;
360      }
361
362      case Stmt::DoStmtClass:
363        HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
364        return;
365
366      case Stmt::CXXForRangeStmtClass:
367        HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
368        return;
369
370      case Stmt::ForStmtClass:
371        HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
372        return;
373
374      case Stmt::ContinueStmtClass:
375      case Stmt::BreakStmtClass:
376      case Stmt::GotoStmtClass:
377        break;
378
379      case Stmt::IfStmtClass:
380        HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
381        return;
382
383      case Stmt::IndirectGotoStmtClass: {
384        // Only 1 successor: the indirect goto dispatch block.
385        assert (B->succ_size() == 1);
386
387        IndirectGotoNodeBuilder
388           builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
389                   *(B->succ_begin()), this);
390
391        SubEng.processIndirectGoto(builder);
392        return;
393      }
394
395      case Stmt::ObjCForCollectionStmtClass: {
396        // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
397        //
398        //  (1) inside a basic block, which represents the binding of the
399        //      'element' variable to a value.
400        //  (2) in a terminator, which represents the branch.
401        //
402        // For (1), subengines will bind a value (i.e., 0 or 1) indicating
403        // whether or not collection contains any more elements.  We cannot
404        // just test to see if the element is nil because a container can
405        // contain nil elements.
406        HandleBranch(Term, Term, B, Pred);
407        return;
408      }
409
410      case Stmt::SwitchStmtClass: {
411        SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
412                                    this);
413
414        SubEng.processSwitch(builder);
415        return;
416      }
417
418      case Stmt::WhileStmtClass:
419        HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
420        return;
421    }
422  }
423
424  assert (B->succ_size() == 1 &&
425          "Blocks with no terminator should have at most 1 successor.");
426
427  generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
428               Pred->State, Pred);
429}
430
431void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
432                                const CFGBlock * B, ExplodedNode *Pred) {
433  assert(B->succ_size() == 2);
434  NodeBuilderContext Ctx(*this, B, Pred);
435  ExplodedNodeSet Dst;
436  SubEng.processBranch(Cond, Term, Ctx, Pred, Dst,
437                       *(B->succ_begin()), *(B->succ_begin()+1));
438  // Enqueue the new frontier onto the worklist.
439  enqueue(Dst);
440}
441
442void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
443                                  ExplodedNode *Pred) {
444  assert(B);
445  assert(!B->empty());
446
447  if (StmtIdx == B->size())
448    HandleBlockExit(B, Pred);
449  else {
450    NodeBuilderContext Ctx(*this, B, Pred);
451    SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
452  }
453}
454
455/// generateNode - Utility method to generate nodes, hook up successors,
456///  and add nodes to the worklist.
457void CoreEngine::generateNode(const ProgramPoint &Loc,
458                              ProgramStateRef State,
459                              ExplodedNode *Pred) {
460
461  bool IsNew;
462  ExplodedNode *Node = G->getNode(Loc, State, false, &IsNew);
463
464  if (Pred)
465    Node->addPredecessor(Pred, *G);  // Link 'Node' with its predecessor.
466  else {
467    assert (IsNew);
468    G->addRoot(Node);  // 'Node' has no predecessor.  Make it a root.
469  }
470
471  // Only add 'Node' to the worklist if it was freshly generated.
472  if (IsNew) WList->enqueue(Node);
473}
474
475void CoreEngine::enqueueStmtNode(ExplodedNode *N,
476                                 const CFGBlock *Block, unsigned Idx) {
477  assert(Block);
478  assert (!N->isSink());
479
480  // Check if this node entered a callee.
481  if (isa<CallEnter>(N->getLocation())) {
482    // Still use the index of the CallExpr. It's needed to create the callee
483    // StackFrameContext.
484    WList->enqueue(N, Block, Idx);
485    return;
486  }
487
488  // Do not create extra nodes. Move to the next CFG element.
489  if (isa<PostInitializer>(N->getLocation())) {
490    WList->enqueue(N, Block, Idx+1);
491    return;
492  }
493
494  const CFGStmt *CS = (*Block)[Idx].getAs<CFGStmt>();
495  const Stmt *St = CS ? CS->getStmt() : 0;
496  PostStmt Loc(St, N->getLocationContext());
497
498  if (Loc == N->getLocation()) {
499    // Note: 'N' should be a fresh node because otherwise it shouldn't be
500    // a member of Deferred.
501    WList->enqueue(N, Block, Idx+1);
502    return;
503  }
504
505  bool IsNew;
506  ExplodedNode *Succ = G->getNode(Loc, N->getState(), false, &IsNew);
507  Succ->addPredecessor(N, *G);
508
509  if (IsNew)
510    WList->enqueue(Succ, Block, Idx+1);
511}
512
513ExplodedNode *CoreEngine::generateCallExitNode(ExplodedNode *N) {
514  // Create a CallExit node and enqueue it.
515  const StackFrameContext *LocCtx
516                         = cast<StackFrameContext>(N->getLocationContext());
517  const Stmt *CE = LocCtx->getCallSite();
518
519  // Use the the callee location context.
520  CallExit Loc(CE, LocCtx);
521
522  bool isNew;
523  ExplodedNode *Node = G->getNode(Loc, N->getState(), false, &isNew);
524  Node->addPredecessor(N, *G);
525  return isNew ? Node : 0;
526}
527
528
529void CoreEngine::enqueue(ExplodedNodeSet &Set) {
530  for (ExplodedNodeSet::iterator I = Set.begin(),
531                                 E = Set.end(); I != E; ++I) {
532    WList->enqueue(*I);
533  }
534}
535
536void CoreEngine::enqueue(ExplodedNodeSet &Set,
537                         const CFGBlock *Block, unsigned Idx) {
538  for (ExplodedNodeSet::iterator I = Set.begin(),
539                                 E = Set.end(); I != E; ++I) {
540    enqueueStmtNode(*I, Block, Idx);
541  }
542}
543
544void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set) {
545  for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) {
546    ExplodedNode *N = *I;
547    // If we are in an inlined call, generate CallExit node.
548    if (N->getLocationContext()->getParent()) {
549      N = generateCallExitNode(N);
550      if (N)
551        WList->enqueue(N);
552    } else {
553      G->addEndOfPath(N);
554      NumPathsExplored++;
555    }
556  }
557}
558
559
560void NodeBuilder::anchor() { }
561
562ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
563                                            ProgramStateRef State,
564                                            ExplodedNode *FromN,
565                                            bool MarkAsSink) {
566  HasGeneratedNodes = true;
567  bool IsNew;
568  ExplodedNode *N = C.Eng.G->getNode(Loc, State, MarkAsSink, &IsNew);
569  N->addPredecessor(FromN, *C.Eng.G);
570  Frontier.erase(FromN);
571
572  if (!IsNew)
573    return 0;
574
575  if (!MarkAsSink)
576    Frontier.Add(N);
577
578  return N;
579}
580
581void NodeBuilderWithSinks::anchor() { }
582
583StmtNodeBuilder::~StmtNodeBuilder() {
584  if (EnclosingBldr)
585    for (ExplodedNodeSet::iterator I = Frontier.begin(),
586                                   E = Frontier.end(); I != E; ++I )
587      EnclosingBldr->addNodes(*I);
588}
589
590void BranchNodeBuilder::anchor() { }
591
592ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
593                                              bool branch,
594                                              ExplodedNode *NodePred) {
595  // If the branch has been marked infeasible we should not generate a node.
596  if (!isFeasible(branch))
597    return NULL;
598
599  ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
600                               NodePred->getLocationContext());
601  ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
602  return Succ;
603}
604
605ExplodedNode*
606IndirectGotoNodeBuilder::generateNode(const iterator &I,
607                                      ProgramStateRef St,
608                                      bool IsSink) {
609  bool IsNew;
610  ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
611                                      Pred->getLocationContext()), St,
612                                      IsSink, &IsNew);
613  Succ->addPredecessor(Pred, *Eng.G);
614
615  if (!IsNew)
616    return 0;
617
618  if (!IsSink)
619    Eng.WList->enqueue(Succ);
620
621  return Succ;
622}
623
624
625ExplodedNode*
626SwitchNodeBuilder::generateCaseStmtNode(const iterator &I,
627                                        ProgramStateRef St) {
628
629  bool IsNew;
630  ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
631                                      Pred->getLocationContext()), St,
632                                      false, &IsNew);
633  Succ->addPredecessor(Pred, *Eng.G);
634  if (!IsNew)
635    return 0;
636
637  Eng.WList->enqueue(Succ);
638  return Succ;
639}
640
641
642ExplodedNode*
643SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
644                                           bool IsSink) {
645  // Get the block for the default case.
646  assert(Src->succ_rbegin() != Src->succ_rend());
647  CFGBlock *DefaultBlock = *Src->succ_rbegin();
648
649  // Sanity check for default blocks that are unreachable and not caught
650  // by earlier stages.
651  if (!DefaultBlock)
652    return NULL;
653
654  bool IsNew;
655  ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock,
656                                      Pred->getLocationContext()), St,
657                                      IsSink, &IsNew);
658  Succ->addPredecessor(Pred, *Eng.G);
659
660  if (!IsNew)
661    return 0;
662
663  if (!IsSink)
664    Eng.WList->enqueue(Succ);
665
666  return Succ;
667}
668