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 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  15 #include "PrettyStackTraceLocationContext.h"
  16 #include "clang/AST/CXXInheritance.h"
  17 #include "clang/AST/DeclCXX.h"
  18 #include "clang/AST/ParentMap.h"
  19 #include "clang/Analysis/Analyses/LiveVariables.h"
  20 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  22 #include "llvm/ADT/SmallSet.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/Support/SaveAndRestore.h"
  25
  26 using namespace clang;
  27 using namespace ento;
  28
  29 #define DEBUG_TYPE "ExprEngine"
  30
  31 STATISTIC(NumOfDynamicDispatchPathSplits,
  32   "The # of times we split the path due to imprecise dynamic dispatch info");
  33
  34 STATISTIC(NumInlinedCalls,
  35   "The # of times we inlined a call");
  36
  37 STATISTIC(NumReachedInlineCountMax,
  38   "The # of times we reached inline count maximum");
  39
  40 void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
  41   // Get the entry block in the CFG of the callee.
  42   const StackFrameContext *calleeCtx = CE.getCalleeContext();
  43   PrettyStackTraceLocationContext CrashInfo(calleeCtx);
  44
  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 successor.
  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.
  70 static std::pair<const Stmt*,
  71                  const CFGBlock*> getLastStmt(const ExplodedNode *Node) {
  72   const Stmt *S = nullptr;
  73   const CFGBlock *Blk = nullptr;
  74   const StackFrameContext *SF =
  75           Node->getLocation().getLocationContext()->getCurrentStackFrame();
  76
  77   // Back up through the ExplodedGraph until we reach a statement node in this
  78   // stack frame.
  79   while (Node) {
  80     const ProgramPoint &PP = Node->getLocation();
  81
  82     if (PP.getLocationContext()->getCurrentStackFrame() == SF) {
  83       if (Optional<StmtPoint> SP = PP.getAs<StmtPoint>()) {
  84         S = SP->getStmt();
  85         break;
  86       } else if (Optional<CallExitEnd> CEE = PP.getAs<CallExitEnd>()) {
  87         S = CEE->getCalleeContext()->getCallSite();
  88         if (S)
  89           break;
  90
  91         // If there is no statement, this is an implicitly-generated call.
  92         // We'll walk backwards over it and then continue the loop to find
  93         // an actual statement.
  94         Optional<CallEnter> CE;
  95         do {
  96           Node = Node->getFirstPred();
  97           CE = Node->getLocationAs<CallEnter>();
  98         } while (!CE || CE->getCalleeContext() != CEE->getCalleeContext());
  99
 100         // Continue searching the graph.
 101       } else if (Optional<BlockEdge> BE = PP.getAs<BlockEdge>()) {
 102         Blk = BE->getSrc();
 103       }
 104     } else if (Optional<CallEnter> CE = PP.getAs<CallEnter>()) {
 105       // If we reached the CallEnter for this function, it has no statements.
 106       if (CE->getCalleeContext() == SF)
 107         break;
 108     }
 109
 110     if (Node->pred_empty())
 111       return std::make_pair(nullptr, nullptr);
 112
 113     Node = *Node->pred_begin();
 114   }
 115
 116   return std::make_pair(S, Blk);
 117 }
 118
 119 /// Adjusts a return value when the called function's return type does not
 120 /// match the caller's expression type. This can happen when a dynamic call
 121 /// is devirtualized, and the overridding method has a covariant (more specific)
 122 /// return type than the parent's method. For C++ objects, this means we need
 123 /// to add base casts.
 124 static SVal adjustReturnValue(SVal V, QualType ExpectedTy, QualType ActualTy,
 125                               StoreManager &StoreMgr) {
 126   // For now, the only adjustments we handle apply only to locations.
 127   if (!V.getAs<Loc>())
 128     return V;
 129
 130   // If the types already match, don't do any unnecessary work.
 131   ExpectedTy = ExpectedTy.getCanonicalType();
 132   ActualTy = ActualTy.getCanonicalType();
 133   if (ExpectedTy == ActualTy)
 134     return V;
 135
 136   // No adjustment is needed between Objective-C pointer types.
 137   if (ExpectedTy->isObjCObjectPointerType() &&
 138       ActualTy->isObjCObjectPointerType())
 139     return V;
 140
 141   // C++ object pointers may need "derived-to-base" casts.
 142   const CXXRecordDecl *ExpectedClass = ExpectedTy->getPointeeCXXRecordDecl();
 143   const CXXRecordDecl *ActualClass = ActualTy->getPointeeCXXRecordDecl();
 144   if (ExpectedClass && ActualClass) {
 145     CXXBasePaths Paths(/*FindAmbiguities=*/true, /*RecordPaths=*/true,
 146                        /*DetectVirtual=*/false);
 147     if (ActualClass->isDerivedFrom(ExpectedClass, Paths) &&
 148         !Paths.isAmbiguous(ActualTy->getCanonicalTypeUnqualified())) {
 149       return StoreMgr.evalDerivedToBase(V, Paths.front());
 150     }
 151   }
 152
 153   // Unfortunately, Objective-C does not enforce that overridden methods have
 154   // covariant return types, so we can't assert that that never happens.
 155   // Be safe and return UnknownVal().
 156   return UnknownVal();
 157 }
 158
 159 void ExprEngine::removeDeadOnEndOfFunction(NodeBuilderContext& BC,
 160                                            ExplodedNode *Pred,
 161                                            ExplodedNodeSet &Dst) {
 162   // Find the last statement in the function and the corresponding basic block.
 163   const Stmt *LastSt = nullptr;
 164   const CFGBlock *Blk = nullptr;
 165   std::tie(LastSt, Blk) = getLastStmt(Pred);
 166   if (!Blk || !LastSt) {
 167     Dst.Add(Pred);
 168     return;
 169   }
 170
 171   // Here, we destroy the current location context. We use the current
 172   // function's entire body as a diagnostic statement, with which the program
 173   // point will be associated. However, we only want to use LastStmt as a
 174   // reference for what to clean up if it's a ReturnStmt; otherwise, everything
 175   // is dead.
 176   SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
 177   const LocationContext *LCtx = Pred->getLocationContext();
 178   removeDead(Pred, Dst, dyn_cast<ReturnStmt>(LastSt), LCtx,
 179              LCtx->getAnalysisDeclContext()->getBody(),
 180              ProgramPoint::PostStmtPurgeDeadSymbolsKind);
 181 }
 182
 183 static bool wasDifferentDeclUsedForInlining(CallEventRef<> Call,
 184     const StackFrameContext *calleeCtx) {
 185   const Decl *RuntimeCallee = calleeCtx->getDecl();
 186   const Decl *StaticDecl = Call->getDecl();
 187   assert(RuntimeCallee);
 188   if (!StaticDecl)
 189     return true;
 190   return RuntimeCallee->getCanonicalDecl() != StaticDecl->getCanonicalDecl();
 191 }
 192
 193 /// Returns true if the CXXConstructExpr \p E was intended to construct a
 194 /// prvalue for the region in \p V.
 195 ///
 196 /// Note that we can't just test for rvalue vs. glvalue because
 197 /// CXXConstructExprs embedded in DeclStmts and initializers are considered
 198 /// rvalues by the AST, and the analyzer would like to treat them as lvalues.
 199 static bool isTemporaryPRValue(const CXXConstructExpr *E, SVal V) {
 200   if (E->isGLValue())
 201     return false;
 202
 203   const MemRegion *MR = V.getAsRegion();
 204   if (!MR)
 205     return false;
 206
 207   return isa<CXXTempObjectRegion>(MR);
 208 }
 209
 210 /// The call exit is simulated with a sequence of nodes, which occur between
 211 /// CallExitBegin and CallExitEnd. The following operations occur between the
 212 /// two program points:
 213 /// 1. CallExitBegin (triggers the start of call exit sequence)
 214 /// 2. Bind the return value
 215 /// 3. Run Remove dead bindings to clean up the dead symbols from the callee.
 216 /// 4. CallExitEnd (switch to the caller context)
 217 /// 5. PostStmt<CallExpr>
 218 void ExprEngine::processCallExit(ExplodedNode *CEBNode) {
 219   // Step 1 CEBNode was generated before the call.
 220   PrettyStackTraceLocationContext CrashInfo(CEBNode->getLocationContext());
 221   const StackFrameContext *calleeCtx =
 222       CEBNode->getLocationContext()->getCurrentStackFrame();
 223
 224   // The parent context might not be a stack frame, so make sure we
 225   // look up the first enclosing stack frame.
 226   const StackFrameContext *callerCtx =
 227     calleeCtx->getParent()->getCurrentStackFrame();
 228
 229   const Stmt *CE = calleeCtx->getCallSite();
 230   ProgramStateRef state = CEBNode->getState();
 231   // Find the last statement in the function and the corresponding basic block.
 232   const Stmt *LastSt = nullptr;
 233   const CFGBlock *Blk = nullptr;
 234   std::tie(LastSt, Blk) = getLastStmt(CEBNode);
 235
 236   // Generate a CallEvent /before/ cleaning the state, so that we can get the
 237   // correct value for 'this' (if necessary).
 238   CallEventManager &CEMgr = getStateManager().getCallEventManager();
 239   CallEventRef<> Call = CEMgr.getCaller(calleeCtx, state);
 240
 241   // Step 2: generate node with bound return value: CEBNode -> BindedRetNode.
 242
 243   // If the callee returns an expression, bind its value to CallExpr.
 244   if (CE) {
 245     if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) {
 246       const LocationContext *LCtx = CEBNode->getLocationContext();
 247       SVal V = state->getSVal(RS, LCtx);
 248
 249       // Ensure that the return type matches the type of the returned Expr.
 250       if (wasDifferentDeclUsedForInlining(Call, calleeCtx)) {
 251         QualType ReturnedTy =
 252           CallEvent::getDeclaredResultType(calleeCtx->getDecl());
 253         if (!ReturnedTy.isNull()) {
 254           if (const Expr *Ex = dyn_cast<Expr>(CE)) {
 255             V = adjustReturnValue(V, Ex->getType(), ReturnedTy,
 256                                   getStoreManager());
 257           }
 258         }
 259       }
 260
 261       state = state->BindExpr(CE, callerCtx, V);
 262     }
 263
 264     // Bind the constructed object value to CXXConstructExpr.
 265     if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) {
 266       loc::MemRegionVal This =
 267         svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx);
 268       SVal ThisV = state->getSVal(This);
 269
 270       // If the constructed object is a temporary prvalue, get its bindings.
 271       if (isTemporaryPRValue(CCE, ThisV))
 272         ThisV = state->getSVal(ThisV.castAs<Loc>());
 273
 274       state = state->BindExpr(CCE, callerCtx, ThisV);
 275     }
 276   }
 277
 278   // Step 3: BindedRetNode -> CleanedNodes
 279   // If we can find a statement and a block in the inlined function, run remove
 280   // dead bindings before returning from the call. This is important to ensure
 281   // that we report the issues such as leaks in the stack contexts in which
 282   // they occurred.
 283   ExplodedNodeSet CleanedNodes;
 284   if (LastSt && Blk && AMgr.options.AnalysisPurgeOpt != PurgeNone) {
 285     static SimpleProgramPointTag retValBind("ExprEngine", "Bind Return Value");
 286     PostStmt Loc(LastSt, calleeCtx, &retValBind);
 287     bool isNew;
 288     ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew);
 289     BindedRetNode->addPredecessor(CEBNode, G);
 290     if (!isNew)
 291       return;
 292
 293     NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode);
 294     currBldrCtx = &Ctx;
 295     // Here, we call the Symbol Reaper with 0 statement and callee location
 296     // context, telling it to clean up everything in the callee's context
 297     // (and its children). We use the callee's function body as a diagnostic
 298     // statement, with which the program point will be associated.
 299     removeDead(BindedRetNode, CleanedNodes, nullptr, calleeCtx,
 300                calleeCtx->getAnalysisDeclContext()->getBody(),
 301                ProgramPoint::PostStmtPurgeDeadSymbolsKind);
 302     currBldrCtx = nullptr;
 303   } else {
 304     CleanedNodes.Add(CEBNode);
 305   }
 306
 307   for (ExplodedNodeSet::iterator I = CleanedNodes.begin(),
 308                                  E = CleanedNodes.end(); I != E; ++I) {
 309
 310     // Step 4: Generate the CallExit and leave the callee's context.
 311     // CleanedNodes -> CEENode
 312     CallExitEnd Loc(calleeCtx, callerCtx);
 313     bool isNew;
 314     ProgramStateRef CEEState = (*I == CEBNode) ? state : (*I)->getState();
 315     ExplodedNode *CEENode = G.getNode(Loc, CEEState, false, &isNew);
 316     CEENode->addPredecessor(*I, G);
 317     if (!isNew)
 318       return;
 319
 320     // Step 5: Perform the post-condition check of the CallExpr and enqueue the
 321     // result onto the work list.
 322     // CEENode -> Dst -> WorkList
 323     NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode);
 324     SaveAndRestore<const NodeBuilderContext*> NBCSave(currBldrCtx,
 325         &Ctx);
 326     SaveAndRestore<unsigned> CBISave(currStmtIdx, calleeCtx->getIndex());
 327
 328     CallEventRef<> UpdatedCall = Call.cloneWithState(CEEState);
 329
 330     ExplodedNodeSet DstPostCall;
 331     getCheckerManager().runCheckersForPostCall(DstPostCall, CEENode,
 332                                                *UpdatedCall, *this,
 333                                                /*WasInlined=*/true);
 334
 335     ExplodedNodeSet Dst;
 336     if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) {
 337       getCheckerManager().runCheckersForPostObjCMessage(Dst, DstPostCall, *Msg,
 338                                                         *this,
 339                                                         /*WasInlined=*/true);
 340     } else if (CE) {
 341       getCheckerManager().runCheckersForPostStmt(Dst, DstPostCall, CE,
 342                                                  *this, /*WasInlined=*/true);
 343     } else {
 344       Dst.insert(DstPostCall);
 345     }
 346
 347     // Enqueue the next element in the block.
 348     for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end();
 349                                    PSI != PSE; ++PSI) {
 350       Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(),
 351                                     calleeCtx->getIndex()+1);
 352     }
 353   }
 354 }
 355
 356 void ExprEngine::examineStackFrames(const Decl *D, const LocationContext *LCtx,
 357                                bool &IsRecursive, unsigned &StackDepth) {
 358   IsRecursive = false;
 359   StackDepth = 0;
 360
 361   while (LCtx) {
 362     if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LCtx)) {
 363       const Decl *DI = SFC->getDecl();
 364
 365       // Mark recursive (and mutually recursive) functions and always count
 366       // them when measuring the stack depth.
 367       if (DI == D) {
 368         IsRecursive = true;
 369         ++StackDepth;
 370         LCtx = LCtx->getParent();
 371         continue;
 372       }
 373
 374       // Do not count the small functions when determining the stack depth.
 375       AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(DI);
 376       const CFG *CalleeCFG = CalleeADC->getCFG();
 377       if (CalleeCFG->getNumBlockIDs() > AMgr.options.getAlwaysInlineSize())
 378         ++StackDepth;
 379     }
 380     LCtx = LCtx->getParent();
 381   }
 382
 383 }
 384
 385 static bool IsInStdNamespace(const FunctionDecl *FD) {
 386   const DeclContext *DC = FD->getEnclosingNamespaceContext();
 387   const NamespaceDecl *ND = dyn_cast<NamespaceDecl>(DC);
 388   if (!ND)
 389     return false;
 390
 391   while (const DeclContext *Parent = ND->getParent()) {
 392     if (!isa<NamespaceDecl>(Parent))
 393       break;
 394     ND = cast<NamespaceDecl>(Parent);
 395   }
 396
 397   return ND->isStdNamespace();
 398 }
 399
 400 // The GDM component containing the dynamic dispatch bifurcation info. When
 401 // the exact type of the receiver is not known, we want to explore both paths -
 402 // one on which we do inline it and the other one on which we don't. This is
 403 // done to ensure we do not drop coverage.
 404 // This is the map from the receiver region to a bool, specifying either we
 405 // consider this region's information precise or not along the given path.
 406 namespace {
 407   enum DynamicDispatchMode {
 408     DynamicDispatchModeInlined = 1,
 409     DynamicDispatchModeConservative
 410   };
 411 }
 412 REGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap,
 413                                  CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *,
 414                                                              unsigned))
 415
 416 bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D,
 417                             NodeBuilder &Bldr, ExplodedNode *Pred,
 418                             ProgramStateRef State) {
 419   assert(D);
 420
 421   const LocationContext *CurLC = Pred->getLocationContext();
 422   const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
 423   const LocationContext *ParentOfCallee = CallerSFC;
 424   if (Call.getKind() == CE_Block &&
 425       !cast<BlockCall>(Call).isConversionFromLambda()) {
 426     const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion();
 427     assert(BR && "If we have the block definition we should have its region");
 428     AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D);
 429     ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC,
 430                                                          cast<BlockDecl>(D),
 431                                                          BR);
 432   }
 433
 434   // This may be NULL, but that's fine.
 435   const Expr *CallE = Call.getOriginExpr();
 436
 437   // Construct a new stack frame for the callee.
 438   AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D);
 439   const StackFrameContext *CalleeSFC =
 440     CalleeADC->getStackFrame(ParentOfCallee, CallE,
 441                              currBldrCtx->getBlock(),
 442                              currStmtIdx);
 443
 444
 445   CallEnter Loc(CallE, CalleeSFC, CurLC);
 446
 447   // Construct a new state which contains the mapping from actual to
 448   // formal arguments.
 449   State = State->enterStackFrame(Call, CalleeSFC);
 450
 451   bool isNew;
 452   if (ExplodedNode *N = G.getNode(Loc, State, false, &isNew)) {
 453     N->addPredecessor(Pred, G);
 454     if (isNew)
 455       Engine.getWorkList()->enqueue(N);
 456   }
 457
 458   // If we decided to inline the call, the successor has been manually
 459   // added onto the work list so remove it from the node builder.
 460   Bldr.takeNodes(Pred);
 461
 462   NumInlinedCalls++;
 463
 464   // Mark the decl as visited.
 465   if (VisitedCallees)
 466     VisitedCallees->insert(D);
 467
 468   return true;
 469 }
 470
 471 static ProgramStateRef getInlineFailedState(ProgramStateRef State,
 472                                             const Stmt *CallE) {
 473   const void *ReplayState = State->get<ReplayWithoutInlining>();
 474   if (!ReplayState)
 475     return nullptr;
 476
 477   assert(ReplayState == CallE && "Backtracked to the wrong call.");
 478   (void)CallE;
 479
 480   return State->remove<ReplayWithoutInlining>();
 481 }
 482
 483 void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
 484                                ExplodedNodeSet &dst) {
 485   // Perform the previsit of the CallExpr.
 486   ExplodedNodeSet dstPreVisit;
 487   getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this);
 488
 489   // Get the call in its initial state. We use this as a template to perform
 490   // all the checks.
 491   CallEventManager &CEMgr = getStateManager().getCallEventManager();
 492   CallEventRef<> CallTemplate
 493     = CEMgr.getSimpleCall(CE, Pred->getState(), Pred->getLocationContext());
 494
 495   // Evaluate the function call.  We try each of the checkers
 496   // to see if the can evaluate the function call.
 497   ExplodedNodeSet dstCallEvaluated;
 498   for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
 499        I != E; ++I) {
 500     evalCall(dstCallEvaluated, *I, *CallTemplate);
 501   }
 502
 503   // Finally, perform the post-condition check of the CallExpr and store
 504   // the created nodes in 'Dst'.
 505   // Note that if the call was inlined, dstCallEvaluated will be empty.
 506   // The post-CallExpr check will occur in processCallExit.
 507   getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE,
 508                                              *this);
 509 }
 510
 511 void ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
 512                           const CallEvent &Call) {
 513   // WARNING: At this time, the state attached to 'Call' may be older than the
 514   // state in 'Pred'. This is a minor optimization since CheckerManager will
 515   // use an updated CallEvent instance when calling checkers, but if 'Call' is
 516   // ever used directly in this function all callers should be updated to pass
 517   // the most recent state. (It is probably not worth doing the work here since
 518   // for some callers this will not be necessary.)
 519
 520   // Run any pre-call checks using the generic call interface.
 521   ExplodedNodeSet dstPreVisit;
 522   getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this);
 523
 524   // Actually evaluate the function call.  We try each of the checkers
 525   // to see if the can evaluate the function call, and get a callback at
 526   // defaultEvalCall if all of them fail.
 527   ExplodedNodeSet dstCallEvaluated;
 528   getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit,
 529                                              Call, *this);
 530
 531   // Finally, run any post-call checks.
 532   getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated,
 533                                              Call, *this);
 534 }
 535
 536 ProgramStateRef ExprEngine::bindReturnValue(const CallEvent &Call,
 537                                             const LocationContext *LCtx,
 538                                             ProgramStateRef State) {
 539   const Expr *E = Call.getOriginExpr();
 540   if (!E)
 541     return State;
 542
 543   // Some method families have known return values.
 544   if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(&Call)) {
 545     switch (Msg->getMethodFamily()) {
 546     default:
 547       break;
 548     case OMF_autorelease:
 549     case OMF_retain:
 550     case OMF_self: {
 551       // These methods return their receivers.
 552       return State->BindExpr(E, LCtx, Msg->getReceiverSVal());
 553     }
 554     }
 555   } else if (const CXXConstructorCall *C = dyn_cast<CXXConstructorCall>(&Call)){
 556     SVal ThisV = C->getCXXThisVal();
 557
 558     // If the constructed object is a temporary prvalue, get its bindings.
 559     if (isTemporaryPRValue(cast<CXXConstructExpr>(E), ThisV))
 560       ThisV = State->getSVal(ThisV.castAs<Loc>());
 561
 562     return State->BindExpr(E, LCtx, ThisV);
 563   }
 564
 565   // Conjure a symbol if the return value is unknown.
 566   QualType ResultTy = Call.getResultType();
 567   SValBuilder &SVB = getSValBuilder();
 568   unsigned Count = currBldrCtx->blockCount();
 569   SVal R = SVB.conjureSymbolVal(nullptr, E, LCtx, ResultTy, Count);
 570   return State->BindExpr(E, LCtx, R);
 571 }
 572
 573 // Conservatively evaluate call by invalidating regions and binding
 574 // a conjured return value.
 575 void ExprEngine::conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
 576                                       ExplodedNode *Pred,
 577                                       ProgramStateRef State) {
 578   State = Call.invalidateRegions(currBldrCtx->blockCount(), State);
 579   State = bindReturnValue(Call, Pred->getLocationContext(), State);
 580
 581   // And make the result node.
 582   Bldr.generateNode(Call.getProgramPoint(), State, Pred);
 583 }
 584
 585 enum CallInlinePolicy {
 586   CIP_Allowed,
 587   CIP_DisallowedOnce,
 588   CIP_DisallowedAlways
 589 };
 590
 591 static CallInlinePolicy mayInlineCallKind(const CallEvent &Call,
 592                                           const ExplodedNode *Pred,
 593                                           AnalyzerOptions &Opts) {
 594   const LocationContext *CurLC = Pred->getLocationContext();
 595   const StackFrameContext *CallerSFC = CurLC->getCurrentStackFrame();
 596   switch (Call.getKind()) {
 597   case CE_Function:
 598   case CE_Block:
 599     break;
 600   case CE_CXXMember:
 601   case CE_CXXMemberOperator:
 602     if (!Opts.mayInlineCXXMemberFunction(CIMK_MemberFunctions))
 603       return CIP_DisallowedAlways;
 604     break;
 605   case CE_CXXConstructor: {
 606     if (!Opts.mayInlineCXXMemberFunction(CIMK_Constructors))
 607       return CIP_DisallowedAlways;
 608
 609     const CXXConstructorCall &Ctor = cast<CXXConstructorCall>(Call);
 610
 611     // FIXME: We don't handle constructors or destructors for arrays properly.
 612     // Even once we do, we still need to be careful about implicitly-generated
 613     // initializers for array fields in default move/copy constructors.
 614     const MemRegion *Target = Ctor.getCXXThisVal().getAsRegion();
 615     if (Target && isa<ElementRegion>(Target))
 616       return CIP_DisallowedOnce;
 617
 618     // FIXME: This is a hack. We don't use the correct region for a new
 619     // expression, so if we inline the constructor its result will just be
 620     // thrown away. This short-term hack is tracked in <rdar://problem/12180598>
 621     // and the longer-term possible fix is discussed in PR12014.
 622     const CXXConstructExpr *CtorExpr = Ctor.getOriginExpr();
 623     if (const Stmt *Parent = CurLC->getParentMap().getParent(CtorExpr))
 624       if (isa<CXXNewExpr>(Parent))
 625         return CIP_DisallowedOnce;
 626
 627     // Inlining constructors requires including initializers in the CFG.
 628     const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext();
 629     assert(ADC->getCFGBuildOptions().AddInitializers && "No CFG initializers");
 630     (void)ADC;
 631
 632     // If the destructor is trivial, it's always safe to inline the constructor.
 633     if (Ctor.getDecl()->getParent()->hasTrivialDestructor())
 634       break;
 635
 636     // For other types, only inline constructors if destructor inlining is
 637     // also enabled.
 638     if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
 639       return CIP_DisallowedAlways;
 640
 641     // FIXME: This is a hack. We don't handle temporary destructors
 642     // right now, so we shouldn't inline their constructors.
 643     if (CtorExpr->getConstructionKind() == CXXConstructExpr::CK_Complete)
 644       if (!Target || !isa<DeclRegion>(Target))
 645         return CIP_DisallowedOnce;
 646
 647     break;
 648   }
 649   case CE_CXXDestructor: {
 650     if (!Opts.mayInlineCXXMemberFunction(CIMK_Destructors))
 651       return CIP_DisallowedAlways;
 652
 653     // Inlining destructors requires building the CFG correctly.
 654     const AnalysisDeclContext *ADC = CallerSFC->getAnalysisDeclContext();
 655     assert(ADC->getCFGBuildOptions().AddImplicitDtors && "No CFG destructors");
 656     (void)ADC;
 657
 658     const CXXDestructorCall &Dtor = cast<CXXDestructorCall>(Call);
 659
 660     // FIXME: We don't handle constructors or destructors for arrays properly.
 661     const MemRegion *Target = Dtor.getCXXThisVal().getAsRegion();
 662     if (Target && isa<ElementRegion>(Target))
 663       return CIP_DisallowedOnce;
 664
 665     break;
 666   }
 667   case CE_CXXAllocator:
 668     if (Opts.mayInlineCXXAllocator())
 669       break;
 670     // Do not inline allocators until we model deallocators.
 671     // This is unfortunate, but basically necessary for smart pointers and such.
 672     return CIP_DisallowedAlways;
 673   case CE_ObjCMessage:
 674     if (!Opts.mayInlineObjCMethod())
 675       return CIP_DisallowedAlways;
 676     if (!(Opts.getIPAMode() == IPAK_DynamicDispatch ||
 677           Opts.getIPAMode() == IPAK_DynamicDispatchBifurcate))
 678       return CIP_DisallowedAlways;
 679     break;
 680   }
 681
 682   return CIP_Allowed;
 683 }
 684
 685 /// Returns true if the given C++ class contains a member with the given name.
 686 static bool hasMember(const ASTContext &Ctx, const CXXRecordDecl *RD,
 687                       StringRef Name) {
 688   const IdentifierInfo &II = Ctx.Idents.get(Name);
 689   DeclarationName DeclName = Ctx.DeclarationNames.getIdentifier(&II);
 690   if (!RD->lookup(DeclName).empty())
 691     return true;
 692
 693   CXXBasePaths Paths(false, false, false);
 694   if (RD->lookupInBases(
 695           [DeclName](const CXXBaseSpecifier *Specifier, CXXBasePath &Path) {
 696             return CXXRecordDecl::FindOrdinaryMember(Specifier, Path, DeclName);
 697           },
 698           Paths))
 699     return true;
 700
 701   return false;
 702 }
 703
 704 /// Returns true if the given C++ class is a container or iterator.
 705 ///
 706 /// Our heuristic for this is whether it contains a method named 'begin()' or a
 707 /// nested type named 'iterator' or 'iterator_category'.
 708 static bool isContainerClass(const ASTContext &Ctx, const CXXRecordDecl *RD) {
 709   return hasMember(Ctx, RD, "begin") ||
 710          hasMember(Ctx, RD, "iterator") ||
 711          hasMember(Ctx, RD, "iterator_category");
 712 }
 713
 714 /// Returns true if the given function refers to a method of a C++ container
 715 /// or iterator.
 716 ///
 717 /// We generally do a poor job modeling most containers right now, and might
 718 /// prefer not to inline their methods.
 719 static bool isContainerMethod(const ASTContext &Ctx,
 720                               const FunctionDecl *FD) {
 721   if (const CXXMethodDecl *MD = dyn_cast<CXXMethodDecl>(FD))
 722     return isContainerClass(Ctx, MD->getParent());
 723   return false;
 724 }
 725
 726 /// Returns true if the given function is the destructor of a class named
 727 /// "shared_ptr".
 728 static bool isCXXSharedPtrDtor(const FunctionDecl *FD) {
 729   const CXXDestructorDecl *Dtor = dyn_cast<CXXDestructorDecl>(FD);
 730   if (!Dtor)
 731     return false;
 732
 733   const CXXRecordDecl *RD = Dtor->getParent();
 734   if (const IdentifierInfo *II = RD->getDeclName().getAsIdentifierInfo())
 735     if (II->isStr("shared_ptr"))
 736         return true;
 737
 738   return false;
 739 }
 740
 741 /// Returns true if the function in \p CalleeADC may be inlined in general.
 742 ///
 743 /// This checks static properties of the function, such as its signature and
 744 /// CFG, to determine whether the analyzer should ever consider inlining it,
 745 /// in any context.
 746 static bool mayInlineDecl(AnalysisDeclContext *CalleeADC,
 747                           AnalyzerOptions &Opts) {
 748   // FIXME: Do not inline variadic calls.
 749   if (CallEvent::isVariadic(CalleeADC->getDecl()))
 750     return false;
 751
 752   // Check certain C++-related inlining policies.
 753   ASTContext &Ctx = CalleeADC->getASTContext();
 754   if (Ctx.getLangOpts().CPlusPlus) {
 755     if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CalleeADC->getDecl())) {
 756       // Conditionally control the inlining of template functions.
 757       if (!Opts.mayInlineTemplateFunctions())
 758         if (FD->getTemplatedKind() != FunctionDecl::TK_NonTemplate)
 759           return false;
 760
 761       // Conditionally control the inlining of C++ standard library functions.
 762       if (!Opts.mayInlineCXXStandardLibrary())
 763         if (Ctx.getSourceManager().isInSystemHeader(FD->getLocation()))
 764           if (IsInStdNamespace(FD))
 765             return false;
 766
 767       // Conditionally control the inlining of methods on objects that look
 768       // like C++ containers.
 769       if (!Opts.mayInlineCXXContainerMethods())
 770         if (!Ctx.getSourceManager().isInMainFile(FD->getLocation()))
 771           if (isContainerMethod(Ctx, FD))
 772             return false;
 773
 774       // Conditionally control the inlining of the destructor of C++ shared_ptr.
 775       // We don't currently do a good job modeling shared_ptr because we can't
 776       // see the reference count, so treating as opaque is probably the best
 777       // idea.
 778       if (!Opts.mayInlineCXXSharedPtrDtor())
 779         if (isCXXSharedPtrDtor(FD))
 780           return false;
 781
 782     }
 783   }
 784
 785   // It is possible that the CFG cannot be constructed.
 786   // Be safe, and check if the CalleeCFG is valid.
 787   const CFG *CalleeCFG = CalleeADC->getCFG();
 788   if (!CalleeCFG)
 789     return false;
 790
 791   // Do not inline large functions.
 792   if (CalleeCFG->getNumBlockIDs() > Opts.getMaxInlinableSize())
 793     return false;
 794
 795   // It is possible that the live variables analysis cannot be
 796   // run.  If so, bail out.
 797   if (!CalleeADC->getAnalysis<RelaxedLiveVariables>())
 798     return false;
 799
 800   return true;
 801 }
 802
 803 bool ExprEngine::shouldInlineCall(const CallEvent &Call, const Decl *D,
 804                                   const ExplodedNode *Pred) {
 805   if (!D)
 806     return false;
 807
 808   AnalysisManager &AMgr = getAnalysisManager();
 809   AnalyzerOptions &Opts = AMgr.options;
 810   AnalysisDeclContextManager &ADCMgr = AMgr.getAnalysisDeclContextManager();
 811   AnalysisDeclContext *CalleeADC = ADCMgr.getContext(D);
 812
 813   // Temporary object destructor processing is currently broken, so we never
 814   // inline them.
 815   // FIXME: Remove this once temp destructors are working.
 816   if (isa<CXXDestructorCall>(Call)) {
 817     if ((*currBldrCtx->getBlock())[currStmtIdx].getAs<CFGTemporaryDtor>())
 818       return false;
 819   }
 820
 821   // The auto-synthesized bodies are essential to inline as they are
 822   // usually small and commonly used. Note: we should do this check early on to
 823   // ensure we always inline these calls.
 824   if (CalleeADC->isBodyAutosynthesized())
 825     return true;
 826
 827   if (!AMgr.shouldInlineCall())
 828     return false;
 829
 830   // Check if this function has been marked as non-inlinable.
 831   Optional<bool> MayInline = Engine.FunctionSummaries->mayInline(D);
 832   if (MayInline.hasValue()) {
 833     if (!MayInline.getValue())
 834       return false;
 835
 836   } else {
 837     // We haven't actually checked the static properties of this function yet.
 838     // Do that now, and record our decision in the function summaries.
 839     if (mayInlineDecl(CalleeADC, Opts)) {
 840       Engine.FunctionSummaries->markMayInline(D);
 841     } else {
 842       Engine.FunctionSummaries->markShouldNotInline(D);
 843       return false;
 844     }
 845   }
 846
 847   // Check if we should inline a call based on its kind.
 848   // FIXME: this checks both static and dynamic properties of the call, which
 849   // means we're redoing a bit of work that could be cached in the function
 850   // summary.
 851   CallInlinePolicy CIP = mayInlineCallKind(Call, Pred, Opts);
 852   if (CIP != CIP_Allowed) {
 853     if (CIP == CIP_DisallowedAlways) {
 854       assert(!MayInline.hasValue() || MayInline.getValue());
 855       Engine.FunctionSummaries->markShouldNotInline(D);
 856     }
 857     return false;
 858   }
 859
 860   const CFG *CalleeCFG = CalleeADC->getCFG();
 861
 862   // Do not inline if recursive or we've reached max stack frame count.
 863   bool IsRecursive = false;
 864   unsigned StackDepth = 0;
 865   examineStackFrames(D, Pred->getLocationContext(), IsRecursive, StackDepth);
 866   if ((StackDepth >= Opts.InlineMaxStackDepth) &&
 867       ((CalleeCFG->getNumBlockIDs() > Opts.getAlwaysInlineSize())
 868        || IsRecursive))
 869     return false;
 870
 871   // Do not inline large functions too many times.
 872   if ((Engine.FunctionSummaries->getNumTimesInlined(D) >
 873        Opts.getMaxTimesInlineLarge()) &&
 874        CalleeCFG->getNumBlockIDs() >=
 875        Opts.getMinCFGSizeTreatFunctionsAsLarge()) {
 876     NumReachedInlineCountMax++;
 877     return false;
 878   }
 879
 880   if (HowToInline == Inline_Minimal &&
 881       (CalleeCFG->getNumBlockIDs() > Opts.getAlwaysInlineSize()
 882       || IsRecursive))
 883     return false;
 884
 885   Engine.FunctionSummaries->bumpNumTimesInlined(D);
 886
 887   return true;
 888 }
 889
 890 static bool isTrivialObjectAssignment(const CallEvent &Call) {
 891   const CXXInstanceCall *ICall = dyn_cast<CXXInstanceCall>(&Call);
 892   if (!ICall)
 893     return false;
 894
 895   const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(ICall->getDecl());
 896   if (!MD)
 897     return false;
 898   if (!(MD->isCopyAssignmentOperator() || MD->isMoveAssignmentOperator()))
 899     return false;
 900
 901   return MD->isTrivial();
 902 }
 903
 904 void ExprEngine::defaultEvalCall(NodeBuilder &Bldr, ExplodedNode *Pred,
 905                                  const CallEvent &CallTemplate) {
 906   // Make sure we have the most recent state attached to the call.
 907   ProgramStateRef State = Pred->getState();
 908   CallEventRef<> Call = CallTemplate.cloneWithState(State);
 909
 910   // Special-case trivial assignment operators.
 911   if (isTrivialObjectAssignment(*Call)) {
 912     performTrivialCopy(Bldr, Pred, *Call);
 913     return;
 914   }
 915
 916   // Try to inline the call.
 917   // The origin expression here is just used as a kind of checksum;
 918   // this should still be safe even for CallEvents that don't come from exprs.
 919   const Expr *E = Call->getOriginExpr();
 920
 921   ProgramStateRef InlinedFailedState = getInlineFailedState(State, E);
 922   if (InlinedFailedState) {
 923     // If we already tried once and failed, make sure we don't retry later.
 924     State = InlinedFailedState;
 925   } else {
 926     RuntimeDefinition RD = Call->getRuntimeDefinition();
 927     const Decl *D = RD.getDecl();
 928     if (shouldInlineCall(*Call, D, Pred)) {
 929       if (RD.mayHaveOtherDefinitions()) {
 930         AnalyzerOptions &Options = getAnalysisManager().options;
 931
 932         // Explore with and without inlining the call.
 933         if (Options.getIPAMode() == IPAK_DynamicDispatchBifurcate) {
 934           BifurcateCall(RD.getDispatchRegion(), *Call, D, Bldr, Pred);
 935           return;
 936         }
 937
 938         // Don't inline if we're not in any dynamic dispatch mode.
 939         if (Options.getIPAMode() != IPAK_DynamicDispatch) {
 940           conservativeEvalCall(*Call, Bldr, Pred, State);
 941           return;
 942         }
 943       }
 944
 945       // We are not bifurcating and we do have a Decl, so just inline.
 946       if (inlineCall(*Call, D, Bldr, Pred, State))
 947         return;
 948     }
 949   }
 950
 951   // If we can't inline it, handle the return value and invalidate the regions.
 952   conservativeEvalCall(*Call, Bldr, Pred, State);
 953 }
 954
 955 void ExprEngine::BifurcateCall(const MemRegion *BifurReg,
 956                                const CallEvent &Call, const Decl *D,
 957                                NodeBuilder &Bldr, ExplodedNode *Pred) {
 958   assert(BifurReg);
 959   BifurReg = BifurReg->StripCasts();
 960
 961   // Check if we've performed the split already - note, we only want
 962   // to split the path once per memory region.
 963   ProgramStateRef State = Pred->getState();
 964   const unsigned *BState =
 965                         State->get<DynamicDispatchBifurcationMap>(BifurReg);
 966   if (BState) {
 967     // If we are on "inline path", keep inlining if possible.
 968     if (*BState == DynamicDispatchModeInlined)
 969       if (inlineCall(Call, D, Bldr, Pred, State))
 970         return;
 971     // If inline failed, or we are on the path where we assume we
 972     // don't have enough info about the receiver to inline, conjure the
 973     // return value and invalidate the regions.
 974     conservativeEvalCall(Call, Bldr, Pred, State);
 975     return;
 976   }
 977
 978   // If we got here, this is the first time we process a message to this
 979   // region, so split the path.
 980   ProgramStateRef IState =
 981       State->set<DynamicDispatchBifurcationMap>(BifurReg,
 982                                                DynamicDispatchModeInlined);
 983   inlineCall(Call, D, Bldr, Pred, IState);
 984
 985   ProgramStateRef NoIState =
 986       State->set<DynamicDispatchBifurcationMap>(BifurReg,
 987                                                DynamicDispatchModeConservative);
 988   conservativeEvalCall(Call, Bldr, Pred, NoIState);
 989
 990   NumOfDynamicDispatchPathSplits++;
 991   return;
 992 }
 993
 994
 995 void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred,
 996                                  ExplodedNodeSet &Dst) {
 997
 998   ExplodedNodeSet dstPreVisit;
 999   getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this);
1000
1001   StmtNodeBuilder B(dstPreVisit, Dst, *currBldrCtx);
1002
1003   if (RS->getRetValue()) {
1004     for (ExplodedNodeSet::iterator it = dstPreVisit.begin(),
1005                                   ei = dstPreVisit.end(); it != ei; ++it) {
1006       B.generateNode(RS, *it, (*it)->getState());
1007     }
1008   }
1009 }