ExprEngineCallAndReturn.cpp revision 8919e688dc610d1f632a4d43f7f1489f67255476 
1//=-- ExprEngineCallAndReturn.cpp - Support for call/return -----*- 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 ExprEngine's support for calls and returns.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Analysis/Analyses/LiveVariables.h"
15#include "clang/StaticAnalyzer/Core/CheckerManager.h"
16#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
17#include "clang/StaticAnalyzer/Core/PathSensitive/Calls.h"
18#include "clang/AST/DeclCXX.h"
19#include "llvm/ADT/SmallSet.h"
20#include "llvm/Support/SaveAndRestore.h"
21
22using namespace clang;
23using namespace ento;
24
25static CallEventKind classifyCallExpr(const CallExpr *CE) {
26  if (isa<CXXMemberCallExpr>(CE))
27    return CE_CXXMember;
28
29  const CXXOperatorCallExpr *OpCE = dyn_cast<CXXOperatorCallExpr>(CE);
30  if (OpCE) {
31    const FunctionDecl *DirectCallee = CE->getDirectCallee();
32    if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(DirectCallee))
33      if (MD->isInstance())
34        return CE_CXXMemberOperator;
35  } else if (CE->getCallee()->getType()->isBlockPointerType()) {
36    return CE_Block;
37  }
38
39  return CE_Function;
40}
41
42void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
43  // Get the entry block in the CFG of the callee.
44  const StackFrameContext *calleeCtx = CE.getCalleeContext();
45  const CFG *CalleeCFG = calleeCtx->getCFG();
46  const CFGBlock *Entry = &(CalleeCFG->getEntry());
47
48  // Validate the CFG.
49  assert(Entry->empty());
50  assert(Entry->succ_size() == 1);
51
52  // Get the solitary sucessor.
53  const CFGBlock *Succ = *(Entry->succ_begin());
54
55  // Construct an edge representing the starting location in the callee.
56  BlockEdge Loc(Entry, Succ, calleeCtx);
57
58  ProgramStateRef state = Pred->getState();
59
60  // Construct a new node and add it to the worklist.
61  bool isNew;
62  ExplodedNode *Node = G.getNode(Loc, state, false, &isNew);
63  Node->addPredecessor(Pred, G);
64  if (isNew)
65    Engine.getWorkList()->enqueue(Node);
66}
67
68// Find the last statement on the path to the exploded node and the
69// corresponding Block.
70static std::pair<const Stmt*,
71                 const CFGBlock*> getLastStmt(const ExplodedNode *Node) {
72  const Stmt *S = 0;
73  const CFGBlock *Blk = 0;
74  const StackFrameContext *SF =
75          Node->getLocation().getLocationContext()->getCurrentStackFrame();
76  while (Node) {
77    const ProgramPoint &PP = Node->getLocation();
78    // Skip any BlockEdges, empty blocks, and the CallExitBegin node.
79    if (isa<BlockEdge>(PP) || isa<CallExitBegin>(PP) || isa<BlockEntrance>(PP)){
80      assert(Node->pred_size() == 1);
81      Node = *Node->pred_begin();
82      continue;
83    }
84    // If we reached the CallEnter, the function has no statements.
85    if (isa<CallEnter>(PP))
86      break;
87    if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) {
88      S = SP->getStmt();
89      // Now, get the enclosing basic block.
90      while (Node && Node->pred_size() >=1 ) {
91        const ProgramPoint &PP = Node->getLocation();
92        if (isa<BlockEdge>(PP) &&
93            (PP.getLocationContext()->getCurrentStackFrame() == SF)) {
94          BlockEdge &EPP = cast<BlockEdge>(PP);
95          Blk = EPP.getDst();
96          break;
97        }
98        Node = *Node->pred_begin();
99      }
100      break;
101    }
102    break;
103  }
104  return std::pair<const Stmt*, const CFGBlock*>(S, Blk);
105}
106
107/// The call exit is simulated with a sequence of nodes, which occur between
108/// CallExitBegin and CallExitEnd. The following operations occur between the
109/// two program points:
110/// 1. CallExitBegin (triggers the start of call exit sequence)
111/// 2. Bind the return value
112/// 3. Run Remove dead bindings to clean up the dead symbols from the callee.
113/// 4. CallExitEnd (switch to the caller context)
114/// 5. PostStmt<CallExpr>
115void ExprEngine::processCallExit(ExplodedNode *CEBNode) {
116  // Step 1 CEBNode was generated before the call.
117
118  const StackFrameContext *calleeCtx =
119      CEBNode->getLocationContext()->getCurrentStackFrame();
120
121  // The parent context might not be a stack frame, so make sure we
122  // look up the first enclosing stack frame.
123  const StackFrameContext *callerCtx =
124    calleeCtx->getParent()->getCurrentStackFrame();
125
126  const Stmt *CE = calleeCtx->getCallSite();
127  ProgramStateRef state = CEBNode->getState();
128  // Find the last statement in the function and the corresponding basic block.
129  const Stmt *LastSt = 0;
130  const CFGBlock *Blk = 0;
131  llvm::tie(LastSt, Blk) = getLastStmt(CEBNode);
132
133  // Step 2: generate node with bound return value: CEBNode -> BindedRetNode.
134
135  // If the callee returns an expression, bind its value to CallExpr.
136  if (CE) {
137    if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) {
138      const LocationContext *LCtx = CEBNode->getLocationContext();
139      SVal V = state->getSVal(RS, LCtx);
140      state = state->BindExpr(CE, calleeCtx->getParent(), V);
141    }
142
143    // Bind the constructed object value to CXXConstructExpr.
144    if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
145      loc::MemRegionVal This =
146        svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx);
147      SVal ThisV = state->getSVal(This);
148
149      // Always bind the region to the CXXConstructExpr.
150      state = state->BindExpr(CCE, calleeCtx->getParent(), ThisV);
151    }
152  }
153
154  // Step 3: BindedRetNode -> CleanedNodes
155  // If we can find a statement and a block in the inlined function, run remove
156  // dead bindings before returning from the call. This is important to ensure
157  // that we report the issues such as leaks in the stack contexts in which
158  // they occurred.
159  ExplodedNodeSet CleanedNodes;
160  if (LastSt && Blk) {
161    static SimpleProgramPointTag retValBind("ExprEngine : Bind Return Value");
162    PostStmt Loc(LastSt, calleeCtx, &retValBind);
163    bool isNew;
164    ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew);
165    BindedRetNode->addPredecessor(CEBNode, G);
166    if (!isNew)
167      return;
168
169    NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode);
170    currentBuilderContext = &Ctx;
171    // Here, we call the Symbol Reaper with 0 statement and caller location
172    // context, telling it to clean up everything in the callee's context
173    // (and it's children). We use LastStmt as a diagnostic statement, which
174    // which the PreStmtPurge Dead point will be associated.
175    removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt,
176               ProgramPoint::PostStmtPurgeDeadSymbolsKind);
177    currentBuilderContext = 0;
178  } else {
179    CleanedNodes.Add(CEBNode);
180  }
181
182  for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
183                                 E = CleanedNodes.end(); I != E; ++I) {
184
185    // Step 4: Generate the CallExit and leave the callee's context.
186    // CleanedNodes -> CEENode
187    CallExitEnd Loc(calleeCtx, callerCtx);
188    bool isNew;
189    ProgramStateRef CEEState = (*I == CEBNode) ? state : (*I)->getState();
190    ExplodedNode *CEENode = G.getNode(Loc, CEEState, false, &isNew);
191    CEENode->addPredecessor(*I, G);
192    if (!isNew)
193      return;
194
195    // Step 5: Perform the post-condition check of the CallExpr and enqueue the
196    // result onto the work list.
197    // CEENode -> Dst -> WorkList
198    ExplodedNodeSet Dst;
199    NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode);
200    SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext,
201        &Ctx);
202    SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex());
203
204    // FIXME: This needs to call PostCall.
205    // FIXME: If/when we inline Objective-C messages, this also needs to call
206    // PostObjCMessage.
207    if (CE)
208      getCheckerManager().runCheckersForPostStmt(Dst, CEENode, CE, *this, true);
209    else
210      Dst.Add(CEENode);
211
212    // Enqueue the next element in the block.
213    for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end();
214                                   PSI != PSE; ++PSI) {
215      Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(),
216                                    calleeCtx->getIndex()+1);
217    }
218  }
219}
220
221static unsigned getNumberStackFrames(const LocationContext *LCtx) {
222  unsigned count = 0;
223  while (LCtx) {
224    if (isa<StackFrameContext>(LCtx))
225      ++count;
226    LCtx = LCtx->getParent();
227  }
228  return count;
229}
230
231// Determine if we should inline the call.
232bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
233  AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
234  const CFG *CalleeCFG = CalleeADC->getCFG();
235
236  // It is possible that the CFG cannot be constructed.
237  // Be safe, and check if the CalleeCFG is valid.
238  if (!CalleeCFG)
239    return false;
240
241  if (getNumberStackFrames(Pred->getLocationContext())
242        == AMgr.InlineMaxStackDepth)
243    return false;
244
245  if (Engine.FunctionSummaries->hasReachedMaxBlockCount(D))
246    return false;
247
248  if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize)
249    return false;
250
251  // Do not inline variadic calls (for now).
252  if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
253    if (BD->isVariadic())
254      return false;
255  }
256  else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
257    if (FD->isVariadic())
258      return false;
259  }
260
261  // It is possible that the live variables analysis cannot be
262  // run.  If so, bail out.
263  if (!CalleeADC->getAnalysis<RelaxedLiveVariables>())
264    return false;
265
266  return true;
267}
268
269bool ExprEngine::inlineCall(ExplodedNodeSet &Dst,
270                            const CallEvent &Call,
271                            ExplodedNode *Pred) {
272  if (!getAnalysisManager().shouldInlineCall())
273    return false;
274
275  bool IsDynamicDispatch;
276  const Decl *D = Call.getDefinition(IsDynamicDispatch);
277  if (!D || IsDynamicDispatch)
278    return false;
279
280  const LocationContext *CurLC = Pred->getLocationContext();
281  const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
282  const LocationContext *ParentOfCallee = 0;
283
284  switch (Call.getKind()) {
285  case CE_Function:
286  case CE_CXXMember:
287  case CE_CXXMemberOperator:
288    // These are always at least possible to inline.
289    break;
290  case CE_CXXConstructor:
291  case CE_CXXDestructor:
292    // Do not inline constructors until we can really model destructors.
293    // This is unfortunate, but basically necessary for smart pointers and such.
294    return false;
295  case CE_CXXAllocator:
296    // Do not inline allocators until we model deallocators.
297    // This is unfortunate, but basically necessary for smart pointers and such.
298    return false;
299  case CE_Block: {
300    const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion();
301    assert(BR && "If we have the block definition we should have its region");
302    AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D);
303    ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC,
304                                                         cast<BlockDecl>(D),
305                                                         BR);
306    break;
307  }
308  case CE_ObjCMessage:
309    // These always use dynamic dispatch; enabling inlining means assuming
310    // that a particular method will be called at runtime.
311    llvm_unreachable("Dynamic dispatch should be handled above.");
312  }
313
314  if (!shouldInlineDecl(D, Pred))
315    return false;
316
317  if (!ParentOfCallee)
318    ParentOfCallee = CallerSFC;
319
320  // This may be NULL, but that's fine.
321  const Expr *CallE = Call.getOriginExpr();
322
323  // Construct a new stack frame for the callee.
324  AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
325  const StackFrameContext *CalleeSFC =
326    CalleeADC->getStackFrame(ParentOfCallee, CallE,
327                             currentBuilderContext->getBlock(),
328                             currentStmtIdx);
329
330  CallEnter Loc(CallE, CalleeSFC, CurLC);
331
332  // Construct a new state which contains the mapping from actual to
333  // formal arguments.
334  ProgramStateRef State = Pred->getState()->enterStackFrame(Call, CalleeSFC);
335
336  bool isNew;
337  if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
338    N->addPredecessor(Pred, G);
339    if (isNew)
340      Engine.getWorkList()->enqueue(N);
341  }
342  return true;
343}
344
345static ProgramStateRef getInlineFailedState(ExplodedNode *&N,
346                                            const Stmt *CallE) {
347  void *ReplayState = N->getState()->get<ReplayWithoutInlining>();
348  if (!ReplayState)
349    return 0;
350
351  assert(ReplayState == (const void*)CallE && "Backtracked to the wrong call.");
352  (void)CallE;
353
354  return N->getState()->remove<ReplayWithoutInlining>();
355}
356
357void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
358                               ExplodedNodeSet &dst) {
359  // Perform the previsit of the CallExpr.
360  ExplodedNodeSet dstPreVisit;
361  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this);
362
363  // Get the callee kind.
364  CallEventKind K = classifyCallExpr(CE);
365
366  // Evaluate the function call.  We try each of the checkers
367  // to see if the can evaluate the function call.
368  ExplodedNodeSet dstCallEvaluated;
369  for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
370       I != E; ++I) {
371    ProgramStateRef State = (*I)->getState();
372    const LocationContext *LCtx = (*I)->getLocationContext();
373
374    // Evaluate the call.
375    switch (K) {
376    case CE_Function:
377      evalCall(dstCallEvaluated, *I, FunctionCall(CE, State, LCtx));
378      break;
379    case CE_CXXMember:
380      evalCall(dstCallEvaluated, *I, CXXMemberCall(cast<CXXMemberCallExpr>(CE),
381                                                   State, LCtx));
382      break;
383    case CE_CXXMemberOperator:
384      evalCall(dstCallEvaluated, *I,
385               CXXMemberOperatorCall(cast<CXXOperatorCallExpr>(CE),
386                                     State, LCtx));
387      break;
388    case CE_Block:
389      evalCall(dstCallEvaluated, *I, BlockCall(CE, State, LCtx));
390      break;
391    default:
392      llvm_unreachable("Non-CallExpr CallEventKind");
393    }
394  }
395
396  // Finally, perform the post-condition check of the CallExpr and store
397  // the created nodes in 'Dst'.
398  // Note that if the call was inlined, dstCallEvaluated will be empty.
399  // The post-CallExpr check will occur in processCallExit.
400  getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
401                                             *this);
402}
403
404void ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
405                          const SimpleCall &Call) {
406  // Run any pre-call checks using the generic call interface.
407  ExplodedNodeSet dstPreVisit;
408  getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this);
409
410  // Actually evaluate the function call.  We try each of the checkers
411  // to see if the can evaluate the function call, and get a callback at
412  // defaultEvalCall if all of them fail.
413  ExplodedNodeSet dstCallEvaluated;
414  getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit,
415                                             Call, *this);
416
417  // Finally, run any post-call checks.
418  getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated,
419                                             Call, *this);
420}
421
422void ExprEngine::defaultEvalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
423                                 const CallEvent &Call) {
424  // Try to inline the call.
425  // The origin expression here is just used as a kind of checksum;
426  // for CallEvents that do not have origin expressions, this should still be
427  // safe.
428  const Expr *E = Call.getOriginExpr();
429  ProgramStateRef state = getInlineFailedState(Pred, E);
430  if (state == 0 && inlineCall(Dst, Call, Pred))
431    return;
432
433  // If we can't inline it, handle the return value and invalidate the regions.
434  NodeBuilder Bldr(Pred, Dst, *currentBuilderContext);
435
436  // Invalidate any regions touched by the call.
437  unsigned Count = currentBuilderContext->getCurrentBlockCount();
438  if (state == 0)
439    state = Pred->getState();
440  state = Call.invalidateRegions(Count, state);
441
442  // Conjure a symbol value to use as the result.
443  if (E) {
444    QualType ResultTy = Call.getResultType();
445    SValBuilder &SVB = getSValBuilder();
446    const LocationContext *LCtx = Pred->getLocationContext();
447    SVal RetVal = SVB.getConjuredSymbolVal(0, E, LCtx, ResultTy, Count);
448
449    state = state->BindExpr(E, LCtx, RetVal);
450  }
451
452  // And make the result node.
453  Bldr.generateNode(Call.getProgramPoint(), state, Pred);
454}
455
456void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
457                                 ExplodedNodeSet &Dst) {
458
459  ExplodedNodeSet dstPreVisit;
460  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this);
461
462  StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext);
463
464  if (RS->getRetValue()) {
465    for (ExplodedNodeSet::iterator it = dstPreVisit.begin(),
466                                  ei = dstPreVisit.end(); it != ei; ++it) {
467      B.generateNode(RS, *it, (*it)->getState());
468    }
469  }
470}
471