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