contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp

   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 #define DEBUG_TYPE "ExprEngine"
  15
  16 #include "clang/Analysis/Analyses/LiveVariables.h"
  17 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  20 #include "clang/AST/CXXInheritance.h"
  21 #include "clang/AST/DeclCXX.h"
  22 #include "clang/AST/ParentMap.h"
  23 #include "llvm/ADT/SmallSet.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Support/SaveAndRestore.h"
  26
  27 using namespace clang;
  28 using namespace ento;
  29
  30 STATISTIC(NumOfDynamicDispatchPathSplits,
  31   "The # of times we split the path due to imprecise dynamic dispatch info");
  32
  33 STATISTIC(NumInlinedCalls,
  34   "The # of times we inlined a call");
  35
  36 void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
  37   // Get the entry block in the CFG of the callee.
  38   const StackFrameContext *calleeCtx = CE.getCalleeContext();
  39   const CFG *CalleeCFG = calleeCtx->getCFG();
  40   const CFGBlock *Entry = &(CalleeCFG->getEntry());
  41
  42   // Validate the CFG.
  43   assert(Entry->empty());
  44   assert(Entry->succ_size() == 1);
  45
  46   // Get the solitary sucessor.
  47   const CFGBlock *Succ = *(Entry->succ_begin());
  48
  49   // Construct an edge representing the starting location in the callee.
  50   BlockEdge Loc(Entry, Succ, calleeCtx);
  51
  52   ProgramStateRef state = Pred->getState();
  53
  54   // Construct a new node and add it to the worklist.
  55   bool isNew;
  56   ExplodedNode *Node = G.getNode(Loc, state, false, &isNew);
  57   Node->addPredecessor(Pred, G);
  58   if (isNew)
  59     Engine.getWorkList()->enqueue(Node);
  60 }
  61
  62 // Find the last statement on the path to the exploded node and the
  63 // corresponding Block.
  64 static std::pair<const Stmt*,
  65                  const CFGBlock*> getLastStmt(const ExplodedNode *Node) {
  66   const Stmt *S = 0;
  67   const StackFrameContext *SF =
  68           Node->getLocation().getLocationContext()->getCurrentStackFrame();
  69
  70   // Back up through the ExplodedGraph until we reach a statement node in this
  71   // stack frame.
  72   while (Node) {
  73     const ProgramPoint &PP = Node->getLocation();
  74
  75     if (PP.getLocationContext()->getCurrentStackFrame() == SF) {
  76       if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) {
  77         S = SP->getStmt();
  78         break;
  79       } else if (const CallExitEnd *CEE = dyn_cast<CallExitEnd>(&PP)) {
  80         S = CEE->getCalleeContext()->getCallSite();
  81         if (S)
  82           break;
  83
  84         // If there is no statement, this is an implicitly-generated call.
  85         // We'll walk backwards over it and then continue the loop to find
  86         // an actual statement.
  87         const CallEnter *CE;
  88         do {
  89           Node = Node->getFirstPred();
  90           CE = Node->getLocationAs<CallEnter>();
  91         } while (!CE || CE->getCalleeContext() != CEE->getCalleeContext());
  92
  93         // Continue searching the graph.
  94       }
  95     } else if (const CallEnter *CE = dyn_cast<CallEnter>(&PP)) {
  96       // If we reached the CallEnter for this function, it has no statements.
  97       if (CE->getCalleeContext() == SF)
  98         break;
  99     }
 100
 101     if (Node->pred_empty())
 102       return std::pair<const Stmt*, const CFGBlock*>((Stmt*)0, (CFGBlock*)0);
 103
 104     Node = *Node->pred_begin();
 105   }
 106
 107   const CFGBlock *Blk = 0;
 108   if (S) {
 109     // Now, get the enclosing basic block.
 110     while (Node) {
 111       const ProgramPoint &PP = Node->getLocation();
 112       if (isa<BlockEdge>(PP) &&
 113           (PP.getLocationContext()->getCurrentStackFrame() == SF)) {
 114         BlockEdge &EPP = cast<BlockEdge>(PP);
 115         Blk = EPP.getDst();
 116         break;
 117       }
 118       if (Node->pred_empty())
 119         return std::pair<const Stmt*, const CFGBlock*>(S, (CFGBlock*)0);
 120
 121       Node = *Node->pred_begin();
 122     }
 123   }
 124
 125   return std::pair<const Stmt*, const CFGBlock*>(S, Blk);
 126 }
 127
 128 /// Adjusts a return value when the called function's return type does not
 129 /// match the caller's expression type. This can happen when a dynamic call
 130 /// is devirtualized, and the overridding method has a covariant (more specific)
 131 /// return type than the parent's method. For C++ objects, this means we need
 132 /// to add base casts.
 133 static SVal adjustReturnValue(SVal V, QualType ExpectedTy, QualType ActualTy,
 134                               StoreManager &StoreMgr) {
 135   // For now, the only adjustments we handle apply only to locations.
 136   if (!isa<Loc>(V))
 137     return V;
 138
 139   // If the types already match, don't do any unnecessary work.
 140   ExpectedTy = ExpectedTy.getCanonicalType();
 141   ActualTy = ActualTy.getCanonicalType();
 142   if (ExpectedTy == ActualTy)
 143     return V;
 144
 145   // No adjustment is needed between Objective-C pointer types.
 146   if (ExpectedTy->isObjCObjectPointerType() &&
 147       ActualTy->isObjCObjectPointerType())
 148     return V;
 149
 150   // C++ object pointers may need "derived-to-base" casts.
 151   const CXXRecordDecl *ExpectedClass = ExpectedTy->getPointeeCXXRecordDecl();
 152   const CXXRecordDecl *ActualClass = ActualTy->getPointeeCXXRecordDecl();
 153   if (ExpectedClass && ActualClass) {
 154     CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
 155                        /*DetectVirtual=*/false);
 156     if (ActualClass->isDerivedFrom(ExpectedClass, Paths) &&
 157         !Paths.isAmbiguous(ActualTy->getCanonicalTypeUnqualified())) {
 158       return StoreMgr.evalDerivedToBase(V, Paths.front());
 159     }
 160   }
 161
 162   // Unfortunately, Objective-C does not enforce that overridden methods have
 163   // covariant return types, so we can't assert that that never happens.
 164   // Be safe and return UnknownVal().
 165   return UnknownVal();
 166 }
 167
 168 void ExprEngine::removeDeadOnEndOfFunction(NodeBuilderContext& BC,
 169                                            ExplodedNode *Pred,
 170                                            ExplodedNodeSet &Dst) {
 171   NodeBuilder Bldr(Pred, Dst, BC);
 172
 173   // Find the last statement in the function and the corresponding basic block.
 174   const Stmt *LastSt = 0;
 175   const CFGBlock *Blk = 0;
 176   llvm::tie(LastSt, Blk) = getLastStmt(Pred);
 177   if (!Blk || !LastSt) {
 178     return;
 179   }
 180
 181   // If the last statement is return, everything it references should stay live.
 182   if (isa<ReturnStmt>(LastSt))
 183     return;
 184
 185   // Here, we call the Symbol Reaper with 0 stack context telling it to clean up
 186   // everything on the stack. We use LastStmt as a diagnostic statement, with
 187   // which the PreStmtPurgeDead point will be associated.
 188   currBldrCtx = &BC;
 189   removeDead(Pred, Dst, 0, 0, LastSt,
 190              ProgramPoint::PostStmtPurgeDeadSymbolsKind);
 191   currBldrCtx = 0;
 192 }
 193
 194 static bool wasDifferentDeclUsedForInlining(CallEventRef<> Call,
 195     const StackFrameContext *calleeCtx) {
 196   const Decl *RuntimeCallee = calleeCtx->getDecl();
 197   const Decl *StaticDecl = Call->getDecl();
 198   assert(RuntimeCallee);
 199   if (!StaticDecl)
 200     return true;
 201   return RuntimeCallee->getCanonicalDecl() != StaticDecl->getCanonicalDecl();
 202 }
 203
 204 /// The call exit is simulated with a sequence of nodes, which occur between
 205 /// CallExitBegin and CallExitEnd. The following operations occur between the
 206 /// two program points:
 207 /// 1. CallExitBegin (triggers the start of call exit sequence)
 208 /// 2. Bind the return value
 209 /// 3. Run Remove dead bindings to clean up the dead symbols from the callee.
 210 /// 4. CallExitEnd (switch to the caller context)
 211 /// 5. PostStmt<CallExpr>
 212 void ExprEngine::processCallExit(ExplodedNode *CEBNode) {
 213   // Step 1 CEBNode was generated before the call.
 214
 215   const StackFrameContext *calleeCtx =
 216       CEBNode->getLocationContext()->getCurrentStackFrame();
 217
 218   // The parent context might not be a stack frame, so make sure we
 219   // look up the first enclosing stack frame.
 220   const StackFrameContext *callerCtx =
 221     calleeCtx->getParent()->getCurrentStackFrame();
 222
 223   const Stmt *CE = calleeCtx->getCallSite();
 224   ProgramStateRef state = CEBNode->getState();
 225   // Find the last statement in the function and the corresponding basic block.
 226   const Stmt *LastSt = 0;
 227   const CFGBlock *Blk = 0;
 228   llvm::tie(LastSt, Blk) = getLastStmt(CEBNode);
 229
 230   // Generate a CallEvent /before/ cleaning the state, so that we can get the
 231   // correct value for 'this' (if necessary).
 232   CallEventManager &CEMgr = getStateManager().getCallEventManager();
 233   CallEventRef<> Call = CEMgr.getCaller(calleeCtx, state);
 234
 235   // Step 2: generate node with bound return value: CEBNode -> BindedRetNode.
 236
 237   // If the callee returns an expression, bind its value to CallExpr.
 238   if (CE) {
 239     if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) {
 240       const LocationContext *LCtx = CEBNode->getLocationContext();
 241       SVal V = state->getSVal(RS, LCtx);
 242
 243       // Ensure that the return type matches the type of the returned Expr.
 244       if (wasDifferentDeclUsedForInlining(Call, calleeCtx)) {
 245         QualType ReturnedTy =
 246           CallEvent::getDeclaredResultType(calleeCtx->getDecl());
 247         if (!ReturnedTy.isNull()) {
 248           if (const Expr *Ex = dyn_cast<Expr>(CE)) {
 249             V = adjustReturnValue(V, Ex->getType(), ReturnedTy,
 250                                   getStoreManager());
 251           }
 252         }
 253       }
 254
 255       state = state->BindExpr(CE, callerCtx, V);
 256     }
 257
 258     // Bind the constructed object value to CXXConstructExpr.
 259     if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
 260       loc::MemRegionVal This =
 261         svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx);
 262       SVal ThisV = state->getSVal(This);
 263
 264       // If the constructed object is a prvalue, get its bindings.
 265       // Note that we have to be careful here because constructors embedded
 266       // in DeclStmts are not marked as lvalues.
 267       if (!CCE->isGLValue())
 268         if (const MemRegion *MR = ThisV.getAsRegion())
 269           if (isa<CXXTempObjectRegion>(MR))
 270             ThisV = state->getSVal(cast<Loc>(ThisV));
 271
 272       state = state->BindExpr(CCE, callerCtx, ThisV);
 273     }
 274   }
 275
 276   // Step 3: BindedRetNode -> CleanedNodes
 277   // If we can find a statement and a block in the inlined function, run remove
 278   // dead bindings before returning from the call. This is important to ensure
 279   // that we report the issues such as leaks in the stack contexts in which
 280   // they occurred.
 281   ExplodedNodeSet CleanedNodes;
 282   if (LastSt && Blk && AMgr.options.AnalysisPurgeOpt != PurgeNone) {
 283     static SimpleProgramPointTag retValBind("ExprEngine : Bind Return Value");
 284     PostStmt Loc(LastSt, calleeCtx, &retValBind);
 285     bool isNew;
 286     ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew);
 287     BindedRetNode->addPredecessor(CEBNode, G);
 288     if (!isNew)
 289       return;
 290
 291     NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode);
 292     currBldrCtx = &Ctx;
 293     // Here, we call the Symbol Reaper with 0 statement and caller location
 294     // context, telling it to clean up everything in the callee's context
 295     // (and it's children). We use LastStmt as a diagnostic statement, which
 296     // which the PreStmtPurge Dead point will be associated.
 297     removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt,
 298                ProgramPoint::PostStmtPurgeDeadSymbolsKind);
 299     currBldrCtx = 0;
 300   } else {
 301     CleanedNodes.Add(CEBNode);
 302   }
 303
 304   for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
 305                                  E = CleanedNodes.end(); I != E; ++I) {
 306
 307     // Step 4: Generate the CallExit and leave the callee's context.
 308     // CleanedNodes -> CEENode
 309     CallExitEnd Loc(calleeCtx, callerCtx);
 310     bool isNew;
 311     ProgramStateRef CEEState = (*I == CEBNode) ? state : (*I)->getState();
 312     ExplodedNode *CEENode = G.getNode(Loc, CEEState, false, &isNew);
 313     CEENode->addPredecessor(*I, G);
 314     if (!isNew)
 315       return;
 316
 317     // Step 5: Perform the post-condition check of the CallExpr and enqueue the
 318     // result onto the work list.
 319     // CEENode -> Dst -> WorkList
 320     NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode);
 321     SaveAndRestore<const NodeBuilderContext*> NBCSave(currBldrCtx,
 322         &Ctx);
 323     SaveAndRestore<unsigned> CBISave(currStmtIdx, calleeCtx->getIndex());
 324
 325     CallEventRef<> UpdatedCall = Call.cloneWithState(CEEState);
 326
 327     ExplodedNodeSet DstPostCall;
 328     getCheckerManager().runCheckersForPostCall(DstPostCall, CEENode,
 329                                                *UpdatedCall, *this,
 330                                                /*WasInlined=*/true);
 331
 332     ExplodedNodeSet Dst;
 333     if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) {
 334       getCheckerManager().runCheckersForPostObjCMessage(Dst, DstPostCall, *Msg,
 335                                                         *this,
 336                                                         /*WasInlined=*/true);
 337     } else if (CE) {
 338       getCheckerManager().runCheckersForPostStmt(Dst, DstPostCall, CE,
 339                                                  *this, /*WasInlined=*/true);
 340     } else {
 341       Dst.insert(DstPostCall);
 342     }
 343
 344     // Enqueue the next element in the block.
 345     for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end();
 346                                    PSI != PSE; ++PSI) {
 347       Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(),
 348                                     calleeCtx->getIndex()+1);
 349     }
 350   }
 351 }
 352
 353 void ExprEngine::examineStackFrames(const Decl *D, const LocationContext *LCtx,
 354                                bool &IsRecursive, unsigned &StackDepth) {
 355   IsRecursive = false;
 356   StackDepth = 0;
 357
 358   while (LCtx) {
 359     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LCtx)) {
 360       const Decl *DI = SFC->getDecl();
 361
 362       // Mark recursive (and mutually recursive) functions and always count
 363       // them when measuring the stack depth.
 364       if (DI == D) {
 365         IsRecursive = true;
 366         ++StackDepth;
 367         LCtx = LCtx->getParent();
 368         continue;
 369       }
 370
 371       // Do not count the small functions when determining the stack depth.
 372       AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(DI);
 373       const CFG *CalleeCFG = CalleeADC->getCFG();
 374       if (CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize())
 375         ++StackDepth;
 376     }
 377     LCtx = LCtx->getParent();
 378   }
 379
 380 }
 381
 382 static bool IsInStdNamespace(const FunctionDecl *FD) {
 383   const DeclContext *DC = FD->getEnclosingNamespaceContext();
 384   const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC);
 385   if (!ND)
 386     return false;
 387
 388   while (const DeclContext *Parent = ND->getParent()) {
 389     if (!isa<NamespaceDecl>(Parent))
 390       break;
 391     ND = cast<NamespaceDecl>(Parent);
 392   }
 393
 394   return ND->getName() == "std";
 395 }
 396
 397 // Determine if we should inline the call.
 398 bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) {
 399   AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
 400   const CFG *CalleeCFG = CalleeADC->getCFG();
 401
 402   // It is possible that the CFG cannot be constructed.
 403   // Be safe, and check if the CalleeCFG is valid.
 404   if (!CalleeCFG)
 405     return false;
 406
 407   bool IsRecursive = false;
 408   unsigned StackDepth = 0;
 409   examineStackFrames(D, Pred->getLocationContext(), IsRecursive, StackDepth);
 410   if ((StackDepth >= AMgr.options.InlineMaxStackDepth) &&
 411        ((CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize())
 412          || IsRecursive))
 413     return false;
 414
 415   if (Engine.FunctionSummaries->hasReachedMaxBlockCount(D))
 416     return false;
 417
 418   if (CalleeCFG->getNumBlockIDs() > AMgr.options.InlineMaxFunctionSize)
 419     return false;
 420
 421   // Do not inline variadic calls (for now).
 422   if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
 423     if (BD->isVariadic())
 424       return false;
 425   }
 426   else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
 427     if (FD->isVariadic())
 428       return false;
 429   }
 430
 431   if (getContext().getLangOpts().CPlusPlus) {
 432     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
 433       // Conditionally allow the inlining of template functions.
 434       if (!getAnalysisManager().options.mayInlineTemplateFunctions())
 435         if (FD->getTemplatedKind() != FunctionDecl::TK_NonTemplate)
 436           return false;
 437
 438       // Conditionally allow the inlining of C++ standard library functions.
 439       if (!getAnalysisManager().options.mayInlineCXXStandardLibrary())
 440         if (getContext().getSourceManager().isInSystemHeader(FD->getLocation()))
 441           if (IsInStdNamespace(FD))
 442             return false;
 443     }
 444   }
 445
 446   // It is possible that the live variables analysis cannot be
 447   // run.  If so, bail out.
 448   if (!CalleeADC->getAnalysis<RelaxedLiveVariables>())
 449     return false;
 450
 451   return true;
 452 }
 453
 454 // The GDM component containing the dynamic dispatch bifurcation info. When
 455 // the exact type of the receiver is not known, we want to explore both paths -
 456 // one on which we do inline it and the other one on which we don't. This is
 457 // done to ensure we do not drop coverage.
 458 // This is the map from the receiver region to a bool, specifying either we
 459 // consider this region's information precise or not along the given path.
 460 namespace {
 461   enum DynamicDispatchMode {
 462     DynamicDispatchModeInlined = 1,
 463     DynamicDispatchModeConservative
 464   };
 465 }
 466 REGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap,
 467                                  CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *,
 468                                                              unsigned))
 469
 470 bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D,
 471                             NodeBuilder &Bldr, ExplodedNode *Pred,
 472                             ProgramStateRef State) {
 473   assert(D);
 474
 475   const LocationContext *CurLC = Pred->getLocationContext();
 476   const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
 477   const LocationContext *ParentOfCallee = 0;
 478
 479   AnalyzerOptions &Opts = getAnalysisManager().options;
 480
 481   // FIXME: Refactor this check into a hypothetical CallEvent::canInline.
 482   switch (Call.getKind()) {
 483   case CE_Function:
 484     break;
 485   case CE_CXXMember:
 486   case CE_CXXMemberOperator:
 487     if (!Opts.mayInlineCXXMemberFunction(CIMK_MemberFunctions))
 488       return false;
 489     break;
 490   case CE_CXXConstructor: {
 491     if (!Opts.mayInlineCXXMemberFunction(CIMK_Constructors))
 492       return false;
 493
 494     const CXXConstructorCall &Ctor = cast<CXXConstructorCall>(Call);
 495
 496     // FIXME: We don't handle constructors or destructors for arrays properly.
 497     const MemRegion *Target = Ctor.getCXXThisVal().getAsRegion();
 498     if (Target && isa<ElementRegion>(Target))
 499       return false;
 500
 501     // FIXME: This is a hack. We don't use the correct region for a new
 502     // expression, so if we inline the constructor its result will just be
 503     // thrown away. This short-term hack is tracked in <rdar://problem/12180598>
 504     // and the longer-term possible fix is discussed in PR12014.
 505     const CXXConstructExpr *CtorExpr = Ctor.getOriginExpr();
 506     if (const Stmt *Parent = CurLC->getParentMap().getParent(CtorExpr))
 507       if (isa<CXXNewExpr>(Parent))
 508         return false;
 509
 510     // Inlining constructors requires including initializers in the CFG.
 511     const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext();
 512     assert(ADC->getCFGBuildOptions().AddInitializers && "No CFG initializers");
 513     (void)ADC;
 514
 515     // If the destructor is trivial, it's always safe to inline the constructor.
 516     if (Ctor.getDecl()->getParent()->hasTrivialDestructor())
 517       break;
 518
 519     // For other types, only inline constructors if destructor inlining is
 520     // also enabled.
 521     if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
 522       return false;
 523
 524     // FIXME: This is a hack. We don't handle temporary destructors
 525     // right now, so we shouldn't inline their constructors.
 526     if (CtorExpr->getConstructionKind() == CXXConstructExpr::CK_Complete)
 527       if (!Target || !isa<DeclRegion>(Target))
 528         return false;
 529
 530     break;
 531   }
 532   case CE_CXXDestructor: {
 533     if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
 534       return false;
 535
 536     // Inlining destructors requires building the CFG correctly.
 537     const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext();
 538     assert(ADC->getCFGBuildOptions().AddImplicitDtors && "No CFG destructors");
 539     (void)ADC;
 540
 541     const CXXDestructorCall &Dtor = cast<CXXDestructorCall>(Call);
 542
 543     // FIXME: We don't handle constructors or destructors for arrays properly.
 544     const MemRegion *Target = Dtor.getCXXThisVal().getAsRegion();
 545     if (Target && isa<ElementRegion>(Target))
 546       return false;
 547
 548     break;
 549   }
 550   case CE_CXXAllocator:
 551     // Do not inline allocators until we model deallocators.
 552     // This is unfortunate, but basically necessary for smart pointers and such.
 553     return false;
 554   case CE_Block: {
 555     const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion();
 556     assert(BR && "If we have the block definition we should have its region");
 557     AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D);
 558     ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC,
 559                                                          cast<BlockDecl>(D),
 560                                                          BR);
 561     break;
 562   }
 563   case CE_ObjCMessage:
 564     if (!Opts.mayInlineObjCMethod())
 565       return false;
 566     if (!(getAnalysisManager().options.IPAMode == DynamicDispatch ||
 567           getAnalysisManager().options.IPAMode == DynamicDispatchBifurcate))
 568       return false;
 569     break;
 570   }
 571
 572   if (!shouldInlineDecl(D, Pred))
 573     return false;
 574
 575   if (!ParentOfCallee)
 576     ParentOfCallee = CallerSFC;
 577
 578   // This may be NULL, but that's fine.
 579   const Expr *CallE = Call.getOriginExpr();
 580
 581   // Construct a new stack frame for the callee.
 582   AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
 583   const StackFrameContext *CalleeSFC =
 584     CalleeADC->getStackFrame(ParentOfCallee, CallE,
 585                              currBldrCtx->getBlock(),
 586                              currStmtIdx);
 587
 588   CallEnter Loc(CallE, CalleeSFC, CurLC);
 589
 590   // Construct a new state which contains the mapping from actual to
 591   // formal arguments.
 592   State = State->enterStackFrame(Call, CalleeSFC);
 593
 594   bool isNew;
 595   if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
 596     N->addPredecessor(Pred, G);
 597     if (isNew)
 598       Engine.getWorkList()->enqueue(N);
 599   }
 600
 601   // If we decided to inline the call, the successor has been manually
 602   // added onto the work list so remove it from the node builder.
 603   Bldr.takeNodes(Pred);
 604
 605   NumInlinedCalls++;
 606
 607   // Mark the decl as visited.
 608   if (VisitedCallees)
 609     VisitedCallees->insert(D);
 610
 611   return true;
 612 }
 613
 614 static ProgramStateRef getInlineFailedState(ProgramStateRef State,
 615                                             const Stmt *CallE) {
 616   void *ReplayState = State->get<ReplayWithoutInlining>();
 617   if (!ReplayState)
 618     return 0;
 619
 620   assert(ReplayState == (const void*)CallE && "Backtracked to the wrong call.");
 621   (void)CallE;
 622
 623   return State->remove<ReplayWithoutInlining>();
 624 }
 625
 626 void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
 627                                ExplodedNodeSet &dst) {
 628   // Perform the previsit of the CallExpr.
 629   ExplodedNodeSet dstPreVisit;
 630   getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this);
 631
 632   // Get the call in its initial state. We use this as a template to perform
 633   // all the checks.
 634   CallEventManager &CEMgr = getStateManager().getCallEventManager();
 635   CallEventRef<> CallTemplate
 636     = CEMgr.getSimpleCall(CE, Pred->getState(), Pred->getLocationContext());
 637
 638   // Evaluate the function call.  We try each of the checkers
 639   // to see if the can evaluate the function call.
 640   ExplodedNodeSet dstCallEvaluated;
 641   for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
 642        I != E; ++I) {
 643     evalCall(dstCallEvaluated, *I, *CallTemplate);
 644   }
 645
 646   // Finally, perform the post-condition check of the CallExpr and store
 647   // the created nodes in 'Dst'.
 648   // Note that if the call was inlined, dstCallEvaluated will be empty.
 649   // The post-CallExpr check will occur in processCallExit.
 650   getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
 651                                              *this);
 652 }
 653
 654 void ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
 655                           const CallEvent &Call) {
 656   // WARNING: At this time, the state attached to 'Call' may be older than the
 657   // state in 'Pred'. This is a minor optimization since CheckerManager will
 658   // use an updated CallEvent instance when calling checkers, but if 'Call' is
 659   // ever used directly in this function all callers should be updated to pass
 660   // the most recent state. (It is probably not worth doing the work here since
 661   // for some callers this will not be necessary.)
 662
 663   // Run any pre-call checks using the generic call interface.
 664   ExplodedNodeSet dstPreVisit;
 665   getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this);
 666
 667   // Actually evaluate the function call.  We try each of the checkers
 668   // to see if the can evaluate the function call, and get a callback at
 669   // defaultEvalCall if all of them fail.
 670   ExplodedNodeSet dstCallEvaluated;
 671   getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit,
 672                                              Call, *this);
 673
 674   // Finally, run any post-call checks.
 675   getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated,
 676                                              Call, *this);
 677 }
 678
 679 ProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call,
 680                                             const LocationContext *LCtx,
 681                                             ProgramStateRef State) {
 682   const Expr *E = Call.getOriginExpr();
 683   if (!E)
 684     return State;
 685
 686   // Some method families have known return values.
 687   if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(&Call)) {
 688     switch (Msg->getMethodFamily()) {
 689     default:
 690       break;
 691     case OMF_autorelease:
 692     case OMF_retain:
 693     case OMF_self: {
 694       // These methods return their receivers.
 695       return State->BindExpr(E, LCtx, Msg->getReceiverSVal());
 696     }
 697     }
 698   } else if (const CXXConstructorCall *C = dyn_cast<CXXConstructorCall>(&Call)){
 699     return State->BindExpr(E, LCtx, C->getCXXThisVal());
 700   }
 701
 702   // Conjure a symbol if the return value is unknown.
 703   QualType ResultTy = Call.getResultType();
 704   SValBuilder &SVB = getSValBuilder();
 705   unsigned Count = currBldrCtx->blockCount();
 706   SVal R = SVB.conjureSymbolVal(0, E, LCtx, ResultTy, Count);
 707   return State->BindExpr(E, LCtx, R);
 708 }
 709
 710 // Conservatively evaluate call by invalidating regions and binding
 711 // a conjured return value.
 712 void ExprEngine::conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
 713                                       ExplodedNode *Pred, ProgramStateRef State) {
 714   State = Call.invalidateRegions(currBldrCtx->blockCount(), State);
 715   State = bindReturnValue(Call, Pred->getLocationContext(), State);
 716
 717   // And make the result node.
 718   Bldr.generateNode(Call.getProgramPoint(), State, Pred);
 719 }
 720
 721 void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred,
 722                                  const CallEvent &CallTemplate) {
 723   // Make sure we have the most recent state attached to the call.
 724   ProgramStateRef State = Pred->getState();
 725   CallEventRef<> Call = CallTemplate.cloneWithState(State);
 726
 727   if (!getAnalysisManager().shouldInlineCall()) {
 728     conservativeEvalCall(*Call, Bldr, Pred, State);
 729     return;
 730   }
 731   // Try to inline the call.
 732   // The origin expression here is just used as a kind of checksum;
 733   // this should still be safe even for CallEvents that don't come from exprs.
 734   const Expr *E = Call->getOriginExpr();
 735   ProgramStateRef InlinedFailedState = getInlineFailedState(State, E);
 736
 737   if (InlinedFailedState) {
 738     // If we already tried once and failed, make sure we don't retry later.
 739     State = InlinedFailedState;
 740   } else {
 741     RuntimeDefinition RD = Call->getRuntimeDefinition();
 742     const Decl *D = RD.getDecl();
 743     if (D) {
 744       if (RD.mayHaveOtherDefinitions()) {
 745         // Explore with and without inlining the call.
 746         if (getAnalysisManager().options.IPAMode == DynamicDispatchBifurcate) {
 747           BifurcateCall(RD.getDispatchRegion(), *Call, D, Bldr, Pred);
 748           return;
 749         }
 750
 751         // Don't inline if we're not in any dynamic dispatch mode.
 752         if (getAnalysisManager().options.IPAMode != DynamicDispatch) {
 753           conservativeEvalCall(*Call, Bldr, Pred, State);
 754           return;
 755         }
 756       }
 757
 758       // We are not bifurcating and we do have a Decl, so just inline.
 759       if (inlineCall(*Call, D, Bldr, Pred, State))
 760         return;
 761     }
 762   }
 763
 764   // If we can't inline it, handle the return value and invalidate the regions.
 765   conservativeEvalCall(*Call, Bldr, Pred, State);
 766 }
 767
 768 void ExprEngine::BifurcateCall(const MemRegion *BifurReg,
 769                                const CallEvent &Call, const Decl *D,
 770                                NodeBuilder &Bldr, ExplodedNode *Pred) {
 771   assert(BifurReg);
 772   BifurReg = BifurReg->StripCasts();
 773
 774   // Check if we've performed the split already - note, we only want
 775   // to split the path once per memory region.
 776   ProgramStateRef State = Pred->getState();
 777   const unsigned *BState =
 778                         State->get<DynamicDispatchBifurcationMap>(BifurReg);
 779   if (BState) {
 780     // If we are on "inline path", keep inlining if possible.
 781     if (*BState == DynamicDispatchModeInlined)
 782       if (inlineCall(Call, D, Bldr, Pred, State))
 783         return;
 784     // If inline failed, or we are on the path where we assume we
 785     // don't have enough info about the receiver to inline, conjure the
 786     // return value and invalidate the regions.
 787     conservativeEvalCall(Call, Bldr, Pred, State);
 788     return;
 789   }
 790
 791   // If we got here, this is the first time we process a message to this
 792   // region, so split the path.
 793   ProgramStateRef IState =
 794       State->set<DynamicDispatchBifurcationMap>(BifurReg,
 795                                                DynamicDispatchModeInlined);
 796   inlineCall(Call, D, Bldr, Pred, IState);
 797
 798   ProgramStateRef NoIState =
 799       State->set<DynamicDispatchBifurcationMap>(BifurReg,
 800                                                DynamicDispatchModeConservative);
 801   conservativeEvalCall(Call, Bldr, Pred, NoIState);
 802
 803   NumOfDynamicDispatchPathSplits++;
 804   return;
 805 }
 806
 807
 808 void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
 809                                  ExplodedNodeSet &Dst) {
 810
 811   ExplodedNodeSet dstPreVisit;
 812   getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this);
 813
 814   StmtNodeBuilder B(dstPreVisit, Dst, *currBldrCtx);
 815
 816   if (RS->getRetValue()) {
 817     for (ExplodedNodeSet::iterator it = dstPreVisit.begin(),
 818                                   ei = dstPreVisit.end(); it != ei; ++it) {
 819       B.generateNode(RS, *it, (*it)->getState());
 820     }
 821   }
 822 }