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 
processCallEnter(CallEnter CE,ExplodedNode * Pred)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*,
getLastStmt(const ExplodedNode * Node)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.
adjustReturnValue(SVal V,QualType ExpectedTy,QualType ActualTy,StoreManager & StoreMgr)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 
removeDeadOnEndOfFunction(NodeBuilderContext & BC,ExplodedNode * Pred,ExplodedNodeSet & Dst)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 
wasDifferentDeclUsedForInlining(CallEventRef<> Call,const StackFrameContext * calleeCtx)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.
isTemporaryPRValue(const CXXConstructExpr * E,SVal V)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>
processCallExit(ExplodedNode * CEBNode)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 
examineStackFrames(const Decl * D,const LocationContext * LCtx,bool & IsRecursive,unsigned & StackDepth)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 
IsInStdNamespace(const FunctionDecl * FD)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 }
REGISTER_TRAIT_WITH_PROGRAMSTATE(DynamicDispatchBifurcationMap,CLANG_ENTO_PROGRAMSTATE_MAP (const MemRegion *,unsigned))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 
getInlineFailedState(ProgramStateRef State,const Stmt * CallE)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 
VisitCallExpr(const CallExpr * CE,ExplodedNode * Pred,ExplodedNodeSet & dst)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 
evalCall(ExplodedNodeSet & Dst,ExplodedNode * Pred,const CallEvent & Call)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 
bindReturnValue(const CallEvent & Call,const LocationContext * LCtx,ProgramStateRef State)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.
conservativeEvalCall(const CallEvent & Call,NodeBuilder & Bldr,ExplodedNode * Pred,ProgramStateRef State)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 
mayInlineCallKind(const CallEvent & Call,const ExplodedNode * Pred,AnalyzerOptions & Opts)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.
hasMember(const ASTContext & Ctx,const CXXRecordDecl * RD,StringRef 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'.
isContainerClass(const ASTContext & Ctx,const CXXRecordDecl * RD)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.
isContainerMethod(const ASTContext & Ctx,const FunctionDecl * FD)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".
isCXXSharedPtrDtor(const FunctionDecl * FD)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.
mayInlineDecl(AnalysisDeclContext * CalleeADC,AnalyzerOptions & Opts)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 
shouldInlineCall(const CallEvent & Call,const Decl * D,const ExplodedNode * Pred)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 
isTrivialObjectAssignment(const CallEvent & Call)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 
defaultEvalCall(NodeBuilder & Bldr,ExplodedNode * Pred,const CallEvent & CallTemplate)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 
BifurcateCall(const MemRegion * BifurReg,const CallEvent & Call,const Decl * D,NodeBuilder & Bldr,ExplodedNode * Pred)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 
VisitReturnStmt(const ReturnStmt * RS,ExplodedNode * Pred,ExplodedNodeSet & Dst)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 }
1010