ExprEngineCallAndReturn.cpp revision c36b30c92c78b95fd29fb5d9d6214d737b3bcb02
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  case CE_ObjCPropertyAccess:
310    // These always use dynamic dispatch; enabling inlining means assuming
311    // that a particular method will be called at runtime.
312    llvm_unreachable("Dynamic dispatch should be handled above.");
313  }
314
315  if (!shouldInlineDecl(D, Pred))
316    return false;
317
318  if (!ParentOfCallee)
319    ParentOfCallee = CallerSFC;
320
321  // This may be NULL, but that's fine.
322  const Expr *CallE = Call.getOriginExpr();
323
324  // Construct a new stack frame for the callee.
325  AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
326  const StackFrameContext *CalleeSFC =
327    CalleeADC->getStackFrame(ParentOfCallee, CallE,
328                             currentBuilderContext->getBlock(),
329                             currentStmtIdx);
330
331  CallEnter Loc(CallE, CalleeSFC, CurLC);
332
333  // Construct a new state which contains the mapping from actual to
334  // formal arguments.
335  ProgramStateRef State = Pred->getState()->enterStackFrame(Call, CalleeSFC);
336
337  bool isNew;
338  if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
339    N->addPredecessor(Pred, G);
340    if (isNew)
341      Engine.getWorkList()->enqueue(N);
342  }
343  return true;
344}
345
346static ProgramStateRef getInlineFailedState(ExplodedNode *&N,
347                                            const Stmt *CallE) {
348  void *ReplayState = N->getState()->get<ReplayWithoutInlining>();
349  if (!ReplayState)
350    return 0;
351
352  assert(ReplayState == (const void*)CallE && "Backtracked to the wrong call.");
353  (void)CallE;
354
355  return N->getState()->remove<ReplayWithoutInlining>();
356}
357
358void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
359                               ExplodedNodeSet &dst) {
360  // Perform the previsit of the CallExpr.
361  ExplodedNodeSet dstPreVisit;
362  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this);
363
364  // Get the callee kind.
365  CallEventKind K = classifyCallExpr(CE);
366
367  // Evaluate the function call.  We try each of the checkers
368  // to see if the can evaluate the function call.
369  ExplodedNodeSet dstCallEvaluated;
370  for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
371       I != E; ++I) {
372    ProgramStateRef State = (*I)->getState();
373    const LocationContext *LCtx = (*I)->getLocationContext();
374
375    // Evaluate the call.
376    switch (K) {
377    case CE_Function:
378      evalCall(dstCallEvaluated, *I, FunctionCall(CE, State, LCtx));
379      break;
380    case CE_CXXMember:
381      evalCall(dstCallEvaluated, *I, CXXMemberCall(cast<CXXMemberCallExpr>(CE),
382                                                   State, LCtx));
383      break;
384    case CE_CXXMemberOperator:
385      evalCall(dstCallEvaluated, *I,
386               CXXMemberOperatorCall(cast<CXXOperatorCallExpr>(CE),
387                                     State, LCtx));
388      break;
389    case CE_Block:
390      evalCall(dstCallEvaluated, *I, BlockCall(CE, State, LCtx));
391      break;
392    default:
393      llvm_unreachable("Non-CallExpr CallEventKind");
394    }
395  }
396
397  // Finally, perform the post-condition check of the CallExpr and store
398  // the created nodes in 'Dst'.
399  // Note that if the call was inlined, dstCallEvaluated will be empty.
400  // The post-CallExpr check will occur in processCallExit.
401  getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
402                                             *this);
403}
404
405void ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
406                          const SimpleCall &Call) {
407  // Run any pre-call checks using the generic call interface.
408  ExplodedNodeSet dstPreVisit;
409  getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this);
410
411  // Actually evaluate the function call.  We try each of the checkers
412  // to see if the can evaluate the function call, and get a callback at
413  // defaultEvalCall if all of them fail.
414  ExplodedNodeSet dstCallEvaluated;
415  getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit,
416                                             Call, *this);
417
418  // Finally, run any post-call checks.
419  getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated,
420                                             Call, *this);
421}
422
423void ExprEngine::defaultEvalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
424                                 const CallEvent &Call) {
425  // Try to inline the call.
426  // The origin expression here is just used as a kind of checksum;
427  // for CallEvents that do not have origin expressions, this should still be
428  // safe.
429  const Expr *E = Call.getOriginExpr();
430  ProgramStateRef state = getInlineFailedState(Pred, E);
431  if (state == 0 && inlineCall(Dst, Call, Pred))
432    return;
433
434  // If we can't inline it, handle the return value and invalidate the regions.
435  NodeBuilder Bldr(Pred, Dst, *currentBuilderContext);
436
437  // Invalidate any regions touched by the call.
438  unsigned Count = currentBuilderContext->getCurrentBlockCount();
439  if (state == 0)
440    state = Pred->getState();
441  state = Call.invalidateRegions(Count, state);
442
443  // Conjure a symbol value to use as the result.
444  if (E) {
445    QualType ResultTy = Call.getResultType();
446    SValBuilder &SVB = getSValBuilder();
447    const LocationContext *LCtx = Pred->getLocationContext();
448    SVal RetVal = SVB.getConjuredSymbolVal(0, E, LCtx, ResultTy, Count);
449
450    state = state->BindExpr(E, LCtx, RetVal);
451  }
452
453  // And make the result node.
454  Bldr.generateNode(Call.getProgramPoint(), state, Pred);
455}
456
457void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
458                                 ExplodedNodeSet &Dst) {
459
460  ExplodedNodeSet dstPreVisit;
461  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this);
462
463  StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext);
464
465  if (RS->getRetValue()) {
466    for (ExplodedNodeSet::iterator it = dstPreVisit.begin(),
467                                  ei = dstPreVisit.end(); it != ei; ++it) {
468      B.generateNode(RS, *it, (*it)->getState());
469    }
470  }
471}
472