ExprEngineCallAndReturn.cpp revision 7fa9b4f258636d89342eda28f21a986c8ac353b1
1294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//=-- ExprEngineCallAndReturn.cpp - Support for call/return -----*- C++ -*-===//
2294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
3294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//                     The LLVM Compiler Infrastructure
4294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
5294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// This file is distributed under the University of Illinois Open Source
6294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek// License. See LICENSE.TXT for details.
7294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
8294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//===----------------------------------------------------------------------===//
9294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
10294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//  This file defines ExprEngine's support for calls and returns.
11294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//
12294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek//===----------------------------------------------------------------------===//
13294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
14294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek#include "clang/StaticAnalyzer/Core/CheckerManager.h"
15294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
16e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h"
17294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek#include "clang/AST/DeclCXX.h"
184a5f724538cbc275370c9504e8169ce92503256cBenjamin Kramer#include "llvm/ADT/SmallSet.h"
194a5f724538cbc275370c9504e8169ce92503256cBenjamin Kramer#include "llvm/Support/SaveAndRestore.h"
20294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
21294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenekusing namespace clang;
22294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenekusing namespace ento;
23294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
243070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenekvoid ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
253070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Get the entry block in the CFG of the callee.
260849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  const StackFrameContext *calleeCtx = CE.getCalleeContext();
270849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  const CFG *CalleeCFG = calleeCtx->getCFG();
283070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  const CFGBlock *Entry = &(CalleeCFG->getEntry());
293070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
303070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Validate the CFG.
313070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  assert(Entry->empty());
323070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  assert(Entry->succ_size() == 1);
333070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
343070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Get the solitary sucessor.
353070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  const CFGBlock *Succ = *(Entry->succ_begin());
363070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
373070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Construct an edge representing the starting location in the callee.
380849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  BlockEdge Loc(Entry, Succ, calleeCtx);
393070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
403070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Construct a new state which contains the mapping from actual to
413070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // formal arguments.
420849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  const LocationContext *callerCtx = Pred->getLocationContext();
438bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek  ProgramStateRef state = Pred->getState()->enterStackFrame(callerCtx,
440849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek                                                                calleeCtx);
453070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek
463070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  // Construct a new node and add it to the worklist.
473070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  bool isNew;
483070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  ExplodedNode *Node = G.getNode(Loc, state, false, &isNew);
493070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  Node->addPredecessor(Pred, G);
503070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek  if (isNew)
513070e13dca5bbefa32acb80ce4a7b217a6220983Ted Kremenek    Engine.getWorkList()->enqueue(Node);
52294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek}
53294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
540b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks// Find the last statement on the path to the exploded node and the
550b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks// corresponding Block.
560b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaksstatic std::pair<const Stmt*,
570b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                 const CFGBlock*> getLastStmt(const ExplodedNode *Node) {
580b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const Stmt *S = 0;
590b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const CFGBlock *Blk = 0;
600b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const StackFrameContext *SF =
610b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks          Node->getLocation().getLocationContext()->getCurrentStackFrame();
62256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  while (Node) {
63256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    const ProgramPoint &PP = Node->getLocation();
640b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Skip any BlockEdges, empty blocks, and the CallExitBegin node.
650b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    if (isa<BlockEdge>(PP) || isa<CallExitBegin>(PP) || isa<BlockEntrance>(PP)){
66256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek      assert(Node->pred_size() == 1);
67256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek      Node = *Node->pred_begin();
68256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek      continue;
690b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    }
700b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // If we reached the CallEnter, the function has no statements.
710b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    if (isa<CallEnter>(PP))
720b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      break;
73256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) {
740b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      S = SP->getStmt();
750b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      // Now, get the enclosing basic block.
760b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      while (Node && Node->pred_size() >=1 ) {
770b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks        const ProgramPoint &PP = Node->getLocation();
780b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks        if (isa<BlockEdge>(PP) &&
790b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks            (PP.getLocationContext()->getCurrentStackFrame() == SF)) {
800b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks          BlockEdge &EPP = cast<BlockEdge>(PP);
810b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks          Blk = EPP.getDst();
820b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks          break;
830b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks        }
840b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks        Node = *Node->pred_begin();
850b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      }
860b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      break;
87256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    }
88256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    break;
89256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  }
900b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  return std::pair<const Stmt*, const CFGBlock*>(S, Blk);
91256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek}
92256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
930b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// The call exit is simulated with a sequence of nodes, which occur between
940b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// CallExitBegin and CallExitEnd. The following operations occur between the
950b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// two program points:
960b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 1. CallExitBegin (triggers the start of call exit sequence)
970b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 2. Bind the return value
980b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 3. Run Remove dead bindings to clean up the dead symbols from the callee.
990b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 4. CallExitEnd (switch to the caller context)
1000b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks/// 5. PostStmt<CallExpr>
1010b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaksvoid ExprEngine::processCallExit(ExplodedNode *CEBNode) {
1020b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // Step 1 CEBNode was generated before the call.
1030b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1040b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const StackFrameContext *calleeCtx =
1050b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      CEBNode->getLocationContext()->getCurrentStackFrame();
1067fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
1077fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  // The parent context might not be a stack frame, so make sure we
1087fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  // look up the first enclosing stack frame.
1097fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  const StackFrameContext *callerCtx =
1107fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    calleeCtx->getParent()->getCurrentStackFrame();
1117fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
112294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  const Stmt *CE = calleeCtx->getCallSite();
1130b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  ProgramStateRef state = CEBNode->getState();
1140b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // Find the last statement in the function and the corresponding basic block.
1150b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const Stmt *LastSt = 0;
1160b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  const CFGBlock *Blk = 0;
1170b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  llvm::tie(LastSt, Blk) = getLastStmt(CEBNode);
1180b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1190b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // Step 2: generate node with binded return value: CEBNode -> BindedRetNode.
1200b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
121294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // If the callee returns an expression, bind its value to CallExpr.
1220b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) {
1230b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    const LocationContext *LCtx = CEBNode->getLocationContext();
124256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    SVal V = state->getSVal(RS, LCtx);
125256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    state = state->BindExpr(CE, callerCtx, V);
126294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  }
1270b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
128294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // Bind the constructed object value to CXXConstructExpr.
129294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
130294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    const CXXThisRegion *ThisR =
1310b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks        getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx);
1320b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
133294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    SVal ThisV = state->getSVal(ThisR);
134294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    // Always bind the region to the CXXConstructExpr.
1350b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    state = state->BindExpr(CCE, CEBNode->getLocationContext(), ThisV);
136294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  }
1370b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1380b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  static SimpleProgramPointTag retValBindTag("ExprEngine : Bind Return Value");
1390b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  PostStmt Loc(LastSt, calleeCtx, &retValBindTag);
140894212e9510299abb203801e014fec76b7926a05Ted Kremenek  bool isNew;
1410b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew);
1420b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  BindedRetNode->addPredecessor(CEBNode, G);
143894212e9510299abb203801e014fec76b7926a05Ted Kremenek  if (!isNew)
144894212e9510299abb203801e014fec76b7926a05Ted Kremenek    return;
1450b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1460b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // Step 3: BindedRetNode -> CleanedNodes
1470b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // If we can find a statement and a block in the inlined function, run remove
1480b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // dead bindings before returning from the call. This is important to ensure
1490b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // that we report the issues such as leaks in the stack contexts in which
1500b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  // they occurred.
1510b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  ExplodedNodeSet CleanedNodes;
1520b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  if (LastSt && Blk) {
1530b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode);
1540b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    currentBuilderContext = &Ctx;
1550b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Here, we call the Symbol Reaper with 0 statement and caller location
1560b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // context, telling it to clean up everything in the callee's context
1570b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // (and it's children). We use LastStmt as a diagnostic statement, which
1580b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // which the PreStmtPurge Dead point will be associated.
1590b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt,
1600b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks               ProgramPoint::PostStmtPurgeDeadSymbolsKind);
1610b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    currentBuilderContext = 0;
1620b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  }
1630b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1640b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks  for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
1650b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                                 E = CleanedNodes.end(); I != E; ++I) {
1660b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1670b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Step 4: Generate the CallExit and leave the callee's context.
1680b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // CleanedNodes -> CEENode
1690b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    CallExitEnd Loc(CE, callerCtx);
1700b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    bool isNew;
1710b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    ExplodedNode *CEENode = G.getNode(Loc, (*I)->getState(), false, &isNew);
1720b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    CEENode->addPredecessor(*I, G);
1730b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    if (!isNew)
1740b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      return;
1750b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1760b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Step 5: Perform the post-condition check of the CallExpr and enqueue the
1770b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // result onto the work list.
1780b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // CEENode -> Dst -> WorkList
1790b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    ExplodedNodeSet Dst;
1800b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode);
1810b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext,
1820b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks        &Ctx);
1830b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex());
1840b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1850b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    getCheckerManager().runCheckersForPostStmt(Dst, CEENode, CE, *this, true);
1860b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks
1870b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    // Enqueue the next element in the block.
1880b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end();
1890b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                                   PSI != PSE; ++PSI) {
1900b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks      Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(),
1910b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks                                    calleeCtx->getIndex()+1);
1920b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks    }
193242384ddb0e0b65dd7e9e0ac0cf3c31cf98b06a6Ted Kremenek  }
194294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek}
195294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
1960849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenekstatic unsigned getNumberStackFrames(const LocationContext *LCtx) {
1970849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  unsigned count = 0;
1980849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  while (LCtx) {
1990849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek    if (isa<StackFrameContext>(LCtx))
2000849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek      ++count;
2010849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek    LCtx = LCtx->getParent();
2020849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  }
2030849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek  return count;
2040849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek}
2050849ade4bb3e90c2fc0ce01ccd330f76f91da732Ted Kremenek
2066cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks// Determine if we should inline the call.
2077fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenekbool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
2087fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
2096cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks  const CFG *CalleeCFG = CalleeADC->getCFG();
2106cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks
21101561d1039bfdda61edd20eed939011a8632c7c7Ted Kremenek  // It is possible that the CFG cannot be constructed.
21201561d1039bfdda61edd20eed939011a8632c7c7Ted Kremenek  // Be safe, and check if the CalleeCFG is valid.
21301561d1039bfdda61edd20eed939011a8632c7c7Ted Kremenek  if (!CalleeCFG)
21401561d1039bfdda61edd20eed939011a8632c7c7Ted Kremenek    return false;
21501561d1039bfdda61edd20eed939011a8632c7c7Ted Kremenek
2166cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks  if (getNumberStackFrames(Pred->getLocationContext())
2176cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks        == AMgr.InlineMaxStackDepth)
2186cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks    return false;
2196cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks
2207fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  if (Engine.FunctionSummaries->hasReachedMaxBlockCount(D))
2213bbd8cd831788c506f2980293eb3c7e1b3ca2501Anna Zaks    return false;
2223bbd8cd831788c506f2980293eb3c7e1b3ca2501Anna Zaks
2236cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks  if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize)
2246cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks    return false;
2256cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks
2266cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks  return true;
2276cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks}
2286cc0969ab37c614d6cf496f2ed6d2fca397a0133Anna Zaks
2295903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks// For now, skip inlining variadic functions.
2305903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks// We also don't inline blocks.
2315903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaksstatic bool shouldInlineCallExpr(const CallExpr *CE, ExprEngine *E) {
2325903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  if (!E->getAnalysisManager().shouldInlineCall())
2335903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks    return false;
2345903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  QualType callee = CE->getCallee()->getType();
2355903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  const FunctionProtoType *FT = 0;
2365903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  if (const PointerType *PT = callee->getAs<PointerType>())
2375903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks    FT = dyn_cast<FunctionProtoType>(PT->getPointeeType());
2385903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  else if (const BlockPointerType *BT = callee->getAs<BlockPointerType>()) {
2397fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    FT = dyn_cast<FunctionProtoType>(BT->getPointeeType());
2405903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  }
2415903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  // If we have no prototype, assume the function is okay.
2425903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  if (!FT)
2435903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks    return true;
2445903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks
2455903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  // Skip inlining of variadic functions.
2465903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  return !FT->isVariadic();
2475903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks}
2485903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks
249256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenekbool ExprEngine::InlineCall(ExplodedNodeSet &Dst,
250256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek                            const CallExpr *CE,
251256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek                            ExplodedNode *Pred) {
2525903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  if (!shouldInlineCallExpr(CE, this))
2535903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks    return false;
2545903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks
2557fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  const StackFrameContext *CallerSFC =
2567fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    Pred->getLocationContext()->getCurrentStackFrame();
2577fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
2588bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek  ProgramStateRef state = Pred->getState();
259256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  const Expr *Callee = CE->getCallee();
2607fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  SVal CalleeVal = state->getSVal(Callee, Pred->getLocationContext());
2617fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  const Decl *D = 0;
2627fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  const LocationContext *ParentOfCallee = 0;
263256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
2647fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  if (const FunctionDecl *FD = CalleeVal.getAsFunctionDecl()) {
2657fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    if (!FD->hasBody(FD))
2667fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek      return false;
2677fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
2687fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    switch (CE->getStmtClass()) {
2697fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek      default:
2707fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek        // FIXME: Handle C++.
2717fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek        break;
2727fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek      case Stmt::CallExprClass: {
2737fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek        D = FD;
2747fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek        break;
2757fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
276d9b795524eb3dc035523f82f135d0a8adf15cd72Ted Kremenek      }
277256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    }
2787fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  } else if (const BlockDataRegion *BR =
2797fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek              dyn_cast_or_null<BlockDataRegion>(CalleeVal.getAsRegion())) {
2807fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    assert(CE->getStmtClass() == Stmt::CallExprClass);
2817fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    const BlockDecl *BD = BR->getDecl();
2827fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    D = BD;
2837fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(BD);
2847fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC,
2857fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek                                                         BD,
2867fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek                                                         BR);
2877fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  } else {
2887fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    // This is case we don't handle yet.
2897fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    return false;
290256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  }
2917fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
2927fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  if (!D || !shouldInlineDecl(D, Pred))
2937fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    return false;
2947fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
2957fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  if (!ParentOfCallee)
2967fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    ParentOfCallee = CallerSFC;
2977fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
2987fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  // Construct a new stack frame for the callee.
2997fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
3007fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  const StackFrameContext *CalleeSFC =
3017fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    CalleeADC->getStackFrame(ParentOfCallee, CE,
3027fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek                             currentBuilderContext->getBlock(),
3037fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek                             currentStmtIdx);
3047fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek
3057fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  CallEnter Loc(CE, CalleeSFC, Pred->getLocationContext());
3067fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  bool isNew;
3077fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  if (ExplodedNode *N = G.getNode(Loc, state, false, &isNew)) {
3087fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    N->addPredecessor(Pred, G);
3097fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek    if (isNew)
3107fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek      Engine.getWorkList()->enqueue(N);
3117fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  }
3127fa9b4f258636d89342eda28f21a986c8ac353b1Ted Kremenek  return true;
313256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek}
314256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
3152cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaksstatic bool isPointerToConst(const ParmVarDecl *ParamDecl) {
3162cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  QualType PointeeTy = ParamDecl->getOriginalType()->getPointeeType();
3172cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  if (PointeeTy != QualType() && PointeeTy.isConstQualified() &&
3182cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks      !PointeeTy->isAnyPointerType() && !PointeeTy->isReferenceType()) {
3192cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    return true;
3202cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  }
3212cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  return false;
3222cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks}
3232cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks
3242cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks// Try to retrieve the function declaration and find the function parameter
3252cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks// types which are pointers/references to a non-pointer const.
3262cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks// We do not invalidate the corresponding argument regions.
3272cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaksstatic void findPtrToConstParams(llvm::SmallSet<unsigned, 1> &PreserveArgs,
3282cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks                       const CallOrObjCMessage &Call) {
3292cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  const Decl *CallDecl = Call.getDecl();
3302cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  if (!CallDecl)
3312cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    return;
3322cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks
3332cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  if (const FunctionDecl *FDecl = dyn_cast<FunctionDecl>(CallDecl)) {
3340d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks    const IdentifierInfo *II = FDecl->getIdentifier();
3350d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks
3360d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks    // List the cases, where the region should be invalidated even if the
3370d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks    // argument is const.
3380d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks    if (II) {
3390d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks      StringRef FName = II->getName();
34007d39a479cf8f20294407e749f9933da34ebecb7Anna Zaks      //  - 'int pthread_setspecific(ptheread_key k, const void *)' stores a
34107d39a479cf8f20294407e749f9933da34ebecb7Anna Zaks      // value into thread local storage. The value can later be retrieved with
3420d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks      // 'void *ptheread_getspecific(pthread_key)'. So even thought the
3430d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks      // parameter is 'const void *', the region escapes through the call.
344ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks      //  - funopen - sets a buffer for future IO calls.
34507d39a479cf8f20294407e749f9933da34ebecb7Anna Zaks      //  - ObjC functions that end with "NoCopy" can free memory, of the passed
34607d39a479cf8f20294407e749f9933da34ebecb7Anna Zaks      // in buffer.
347ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks      // - Many CF containers allow objects to escape through custom
348ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks      // allocators/deallocators upon container construction.
34962a5c34ddc54696725683f6c5af1c8e1592c5c38Anna Zaks      // - NSXXInsertXX, for example NSMapInsertIfAbsent, since they can
35062a5c34ddc54696725683f6c5af1c8e1592c5c38Anna Zaks      // be deallocated by NSMapRemove.
351aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks      // - Any call that has a callback as one of the arguments.
35207d39a479cf8f20294407e749f9933da34ebecb7Anna Zaks      if (FName == "pthread_setspecific" ||
353ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks          FName == "funopen" ||
354ca23eb212c78ac5bc62d0881635579dbe7095639Anna Zaks          FName.endswith("NoCopy") ||
35562a5c34ddc54696725683f6c5af1c8e1592c5c38Anna Zaks          (FName.startswith("NS") &&
35662a5c34ddc54696725683f6c5af1c8e1592c5c38Anna Zaks            (FName.find("Insert") != StringRef::npos)) ||
357aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks          Call.isCFCGAllowingEscape(FName) ||
358aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks          Call.hasNonZeroCallbackArg())
3590d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks        return;
3600d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks    }
3610d389b819c33bdf0375694a8f141c8f02e002b18Anna Zaks
3622cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    for (unsigned Idx = 0, E = Call.getNumArgs(); Idx != E; ++Idx) {
3632cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks      if (FDecl && Idx < FDecl->getNumParams()) {
3642cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks        if (isPointerToConst(FDecl->getParamDecl(Idx)))
3652cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks          PreserveArgs.insert(Idx);
3662cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks      }
3672cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    }
3682cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    return;
3692cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  }
3702cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks
3712cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  if (const ObjCMethodDecl *MDecl = dyn_cast<ObjCMethodDecl>(CallDecl)) {
3722cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    assert(MDecl->param_size() <= Call.getNumArgs());
3732cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    unsigned Idx = 0;
374aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks
375aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks    if (Call.hasNonZeroCallbackArg())
376aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks      return;
377aca0ac58d2ae80d764e3832456667d7322445e0cAnna Zaks
3782cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    for (clang::ObjCMethodDecl::param_const_iterator
3792cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks         I = MDecl->param_begin(), E = MDecl->param_end(); I != E; ++I, ++Idx) {
3802cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks      if (isPointerToConst(*I))
3812cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks        PreserveArgs.insert(Idx);
3822cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    }
3832cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    return;
3842cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  }
3852cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks}
3862cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks
3878bef8238181a30e52dea380789a7e2d760eac532Ted KremenekProgramStateRef
3888bef8238181a30e52dea380789a7e2d760eac532Ted KremenekExprEngine::invalidateArguments(ProgramStateRef State,
389e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose                                const CallOrObjCMessage &Call,
390e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose                                const LocationContext *LC) {
391e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  SmallVector<const MemRegion *, 8> RegionsToInvalidate;
392e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
393e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  if (Call.isObjCMessage()) {
394e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // Invalidate all instance variables of the receiver of an ObjC message.
395e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // FIXME: We should be able to do better with inter-procedural analysis.
396e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    if (const MemRegion *MR = Call.getInstanceMessageReceiver(LC).getAsRegion())
397e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      RegionsToInvalidate.push_back(MR);
398e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
399e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  } else if (Call.isCXXCall()) {
400e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // Invalidate all instance variables for the callee of a C++ method call.
401e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // FIXME: We should be able to do better with inter-procedural analysis.
402e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // FIXME: We can probably do better for const versus non-const methods.
403e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    if (const MemRegion *Callee = Call.getCXXCallee().getAsRegion())
404e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      RegionsToInvalidate.push_back(Callee);
405e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
406e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  } else if (Call.isFunctionCall()) {
407e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // Block calls invalidate all captured-by-reference values.
4082cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    SVal CalleeVal = Call.getFunctionCallee();
4092cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    if (const MemRegion *Callee = CalleeVal.getAsRegion()) {
410e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      if (isa<BlockDataRegion>(Callee))
411e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        RegionsToInvalidate.push_back(Callee);
412e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    }
413e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  }
414e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
4152cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  // Indexes of arguments whose values will be preserved by the call.
4162cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  llvm::SmallSet<unsigned, 1> PreserveArgs;
4172cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks  findPtrToConstParams(PreserveArgs, Call);
4182cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks
419e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  for (unsigned idx = 0, e = Call.getNumArgs(); idx != e; ++idx) {
4202cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks    if (PreserveArgs.count(idx))
4212cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks      continue;
4222cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks
423e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    SVal V = Call.getArgSVal(idx);
424e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
425e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // If we are passing a location wrapped as an integer, unwrap it and
426e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    // invalidate the values referred by the location.
427e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    if (nonloc::LocAsInteger *Wrapped = dyn_cast<nonloc::LocAsInteger>(&V))
428e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      V = Wrapped->getLoc();
429e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    else if (!isa<Loc>(V))
430e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      continue;
431e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
432e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    if (const MemRegion *R = V.getAsRegion()) {
433e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // Invalidate the value of the variable passed by reference.
434e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
435e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // Are we dealing with an ElementRegion?  If the element type is
4362cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks      // a basic integer type (e.g., char, int) and the underlying region
437e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // is a variable region then strip off the ElementRegion.
438e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // FIXME: We really need to think about this for the general case
439e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      //   as sometimes we are reasoning about arrays and other times
440e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      //   about (char*), etc., is just a form of passing raw bytes.
441e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      //   e.g., void *p = alloca(); foo((char*)p);
442e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
443e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        // Checking for 'integral type' is probably too promiscuous, but
444e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        // we'll leave it in for now until we have a systematic way of
445e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        // handling all of these cases.  Eventually we need to come up
446e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        // with an interface to StoreManager so that this logic can be
4472cbe791d3e9b26f30196c4852da75d9ad67b4ad9Anna Zaks        // appropriately delegated to the respective StoreManagers while
448e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        // still allowing us to do checker-specific logic (e.g.,
449e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        // invalidating reference counts), probably via callbacks.
450e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        if (ER->getElementType()->isIntegralOrEnumerationType()) {
451e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose          const MemRegion *superReg = ER->getSuperRegion();
452e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose          if (isa<VarRegion>(superReg) || isa<FieldRegion>(superReg) ||
453e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose              isa<ObjCIvarRegion>(superReg))
454e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose            R = cast<TypedRegion>(superReg);
455e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        }
456e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose        // FIXME: What about layers of ElementRegions?
457e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      }
458e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
459e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // Mark this region for invalidation.  We batch invalidate regions
460e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // below for efficiency.
461e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      RegionsToInvalidate.push_back(R);
462e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    } else {
463e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // Nuke all other arguments passed by reference.
464e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // FIXME: is this necessary or correct? This handles the non-Region
465e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      //  cases.  Is it ever valid to store to these?
466e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      State = State->unbindLoc(cast<Loc>(V));
467e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose    }
468e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  }
469e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
470e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  // Invalidate designated regions using the batch invalidation API.
471e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
472e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  // FIXME: We can have collisions on the conjured symbol if the
473e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  //  expression *I also creates conjured symbols.  We probably want
474e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  //  to identify conjured symbols by an expression pair: the enclosing
475e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  //  expression (the context) and the expression itself.  This should
476e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  //  disambiguate conjured symbols.
477ebae6d0209e1ec3d5ea14f9e63bd0d740218ed14Anna Zaks  unsigned Count = currentBuilderContext->getCurrentBlockCount();
478e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  StoreManager::InvalidatedSymbols IS;
479e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
480e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate
481e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  //  global variables.
482e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose  return State->invalidateRegions(RegionsToInvalidate,
4833133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek                                  Call.getOriginExpr(), Count, LC,
484eb31a76d1cdaaf8874c549dc6bd964ff270d3822Anna Zaks                                  &IS, &Call);
485e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
486e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose}
487e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
4885903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaksstatic ProgramStateRef getReplayWithoutInliningState(ExplodedNode *&N,
4895903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks                                                     const CallExpr *CE) {
4905903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  void *ReplayState = N->getState()->get<ReplayWithoutInlining>();
4915903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  if (!ReplayState)
4925903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks    return 0;
4935903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  const CallExpr *ReplayCE = reinterpret_cast<const CallExpr*>(ReplayState);
4945903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  if (CE == ReplayCE) {
4955903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks    return N->getState()->remove<ReplayWithoutInlining>();
49610520d76044e8fff71d414f30c21b449fd104960Ted Kremenek  }
4975903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks  return 0;
49810520d76044e8fff71d414f30c21b449fd104960Ted Kremenek}
49910520d76044e8fff71d414f30c21b449fd104960Ted Kremenek
500294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenekvoid ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
501294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek                               ExplodedNodeSet &dst) {
502294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // Perform the previsit of the CallExpr.
503294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  ExplodedNodeSet dstPreVisit;
504294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this);
505294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
506294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // Now evaluate the call itself.
507294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  class DefaultEval : public GraphExpander {
508294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    ExprEngine &Eng;
509294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    const CallExpr *CE;
510294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  public:
511294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
512294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    DefaultEval(ExprEngine &eng, const CallExpr *ce)
513294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    : Eng(eng), CE(ce) {}
514294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) {
5155903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks
5165903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks      ProgramStateRef state = getReplayWithoutInliningState(Pred, CE);
5175903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks
5185903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks      // First, try to inline the call.
5195903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks      if (state == 0 && Eng.InlineCall(Dst, CE, Pred))
520294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek        return;
521500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
522500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      // First handle the return value.
523aa0aeb1cbe117db68d35700cb3a34aace0f99b99Anna Zaks      StmtNodeBuilder Bldr(Pred, Dst, *Eng.currentBuilderContext);
524500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
525500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      // Get the callee.
526294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek      const Expr *Callee = CE->getCallee()->IgnoreParens();
5275903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks      if (state == 0)
5285903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks        state = Pred->getState();
5295eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek      SVal L = state->getSVal(Callee, Pred->getLocationContext());
530500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
531500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      // Figure out the result type. We do this dance to handle references.
532500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      QualType ResultTy;
533500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      if (const FunctionDecl *FD = L.getAsFunctionDecl())
534500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose        ResultTy = FD->getResultType();
535500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      else
536500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose        ResultTy = CE->getType();
537500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
538591b5f53c0e11d87401b4804bb1be1a53f95c619Anna Zaks      if (CE->isGLValue())
539500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose        ResultTy = Eng.getContext().getPointerType(ResultTy);
540500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
541500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      // Conjure a symbol value to use as the result.
542500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose      SValBuilder &SVB = Eng.getSValBuilder();
543ebae6d0209e1ec3d5ea14f9e63bd0d740218ed14Anna Zaks      unsigned Count = Eng.currentBuilderContext->getCurrentBlockCount();
5443133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek      const LocationContext *LCtx = Pred->getLocationContext();
5453133f79cf451e6302dd05262b4bb53a3e4fd6300Ted Kremenek      SVal RetVal = SVB.getConjuredSymbolVal(0, CE, LCtx, ResultTy, Count);
546500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
547e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // Generate a new state with the return value set.
5485eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek      state = state->BindExpr(CE, LCtx, RetVal);
549e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose
550e38dd95dddb8f1b38469c8d0e28aa1c660489324Jordy Rose      // Invalidate the arguments.
5515eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek      state = Eng.invalidateArguments(state, CallOrObjCMessage(CE, state, LCtx),
5525eca482fe895ea57bc82410222e6426c09e63284Ted Kremenek                                      LCtx);
553500abad7edfcc2409b18dd616cdbc28a094926f5Jordy Rose
554fe27971d54d26997149d6b84057f04ff398d1d5dJordy Rose      // And make the result node.
555ebae6d0209e1ec3d5ea14f9e63bd0d740218ed14Anna Zaks      Bldr.generateNode(CE, Pred, state);
556294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    }
557294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  };
558294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
559294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // Finally, evaluate the function call.  We try each of the checkers
560294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // to see if the can evaluate the function call.
561294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  ExplodedNodeSet dstCallEvaluated;
562294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  DefaultEval defEval(*this, CE);
563294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  getCheckerManager().runCheckersForEvalCall(dstCallEvaluated,
564294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek                                             dstPreVisit,
565294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek                                             CE, *this, &defEval);
566294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
567294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // Finally, perform the post-condition check of the CallExpr and store
568294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  // the created nodes in 'Dst'.
569294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
570294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek                                             *this);
571294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek}
572294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek
573294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenekvoid ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
574294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek                                 ExplodedNodeSet &Dst) {
575256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
576256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  ExplodedNodeSet dstPreVisit;
577256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this);
578256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
579256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext);
580256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek
581256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek  if (RS->getRetValue()) {
582256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek    for (ExplodedNodeSet::iterator it = dstPreVisit.begin(),
583256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek                                  ei = dstPreVisit.end(); it != ei; ++it) {
584256ef642f8feef22fd53be7efa868e8e34752eedTed Kremenek      B.generateNode(RS, *it, (*it)->getState());
585294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek    }
586294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek  }
587294fd0a62b95f512637910bf85c7efa6c2354b50Ted Kremenek}
588