ExprEngineCallAndReturn.cpp revision d4aeb8050a1d0fe47c53a73361c8b0b8ac310f46
1//=-- ExprEngineCallAndReturn.cpp - Support for call/return -----*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines ExprEngine's support for calls and returns. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/Analysis/Analyses/LiveVariables.h" 15#include "clang/StaticAnalyzer/Core/CheckerManager.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/Calls.h" 18#include "clang/AST/DeclCXX.h" 19#include "llvm/ADT/SmallSet.h" 20#include "llvm/Support/SaveAndRestore.h" 21 22using namespace clang; 23using namespace ento; 24 25void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) { 26 // Get the entry block in the CFG of the callee. 27 const StackFrameContext *calleeCtx = CE.getCalleeContext(); 28 const CFG *CalleeCFG = calleeCtx->getCFG(); 29 const CFGBlock *Entry = &(CalleeCFG->getEntry()); 30 31 // Validate the CFG. 32 assert(Entry->empty()); 33 assert(Entry->succ_size() == 1); 34 35 // Get the solitary sucessor. 36 const CFGBlock *Succ = *(Entry->succ_begin()); 37 38 // Construct an edge representing the starting location in the callee. 39 BlockEdge Loc(Entry, Succ, calleeCtx); 40 41 // Construct a new state which contains the mapping from actual to 42 // formal arguments. 43 const LocationContext *callerCtx = Pred->getLocationContext(); 44 ProgramStateRef state = Pred->getState()->enterStackFrame(callerCtx, 45 calleeCtx); 46 47 // Construct a new node and add it to the worklist. 48 bool isNew; 49 ExplodedNode *Node = G.getNode(Loc, state, false, &isNew); 50 Node->addPredecessor(Pred, G); 51 if (isNew) 52 Engine.getWorkList()->enqueue(Node); 53} 54 55// Find the last statement on the path to the exploded node and the 56// corresponding Block. 57static std::pair<const Stmt*, 58 const CFGBlock*> getLastStmt(const ExplodedNode *Node) { 59 const Stmt *S = 0; 60 const CFGBlock *Blk = 0; 61 const StackFrameContext *SF = 62 Node->getLocation().getLocationContext()->getCurrentStackFrame(); 63 while (Node) { 64 const ProgramPoint &PP = Node->getLocation(); 65 // Skip any BlockEdges, empty blocks, and the CallExitBegin node. 66 if (isa<BlockEdge>(PP) || isa<CallExitBegin>(PP) || isa<BlockEntrance>(PP)){ 67 assert(Node->pred_size() == 1); 68 Node = *Node->pred_begin(); 69 continue; 70 } 71 // If we reached the CallEnter, the function has no statements. 72 if (isa<CallEnter>(PP)) 73 break; 74 if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) { 75 S = SP->getStmt(); 76 // Now, get the enclosing basic block. 77 while (Node && Node->pred_size() >=1 ) { 78 const ProgramPoint &PP = Node->getLocation(); 79 if (isa<BlockEdge>(PP) && 80 (PP.getLocationContext()->getCurrentStackFrame() == SF)) { 81 BlockEdge &EPP = cast<BlockEdge>(PP); 82 Blk = EPP.getDst(); 83 break; 84 } 85 Node = *Node->pred_begin(); 86 } 87 break; 88 } 89 break; 90 } 91 return std::pair<const Stmt*, const CFGBlock*>(S, Blk); 92} 93 94/// The call exit is simulated with a sequence of nodes, which occur between 95/// CallExitBegin and CallExitEnd. The following operations occur between the 96/// two program points: 97/// 1. CallExitBegin (triggers the start of call exit sequence) 98/// 2. Bind the return value 99/// 3. Run Remove dead bindings to clean up the dead symbols from the callee. 100/// 4. CallExitEnd (switch to the caller context) 101/// 5. PostStmt<CallExpr> 102void ExprEngine::processCallExit(ExplodedNode *CEBNode) { 103 // Step 1 CEBNode was generated before the call. 104 105 const StackFrameContext *calleeCtx = 106 CEBNode->getLocationContext()->getCurrentStackFrame(); 107 108 // The parent context might not be a stack frame, so make sure we 109 // look up the first enclosing stack frame. 110 const StackFrameContext *callerCtx = 111 calleeCtx->getParent()->getCurrentStackFrame(); 112 113 const Stmt *CE = calleeCtx->getCallSite(); 114 ProgramStateRef state = CEBNode->getState(); 115 // Find the last statement in the function and the corresponding basic block. 116 const Stmt *LastSt = 0; 117 const CFGBlock *Blk = 0; 118 llvm::tie(LastSt, Blk) = getLastStmt(CEBNode); 119 120 // Step 2: generate node with binded return value: CEBNode -> BindedRetNode. 121 122 // If the callee returns an expression, bind its value to CallExpr. 123 if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) { 124 const LocationContext *LCtx = CEBNode->getLocationContext(); 125 SVal V = state->getSVal(RS, LCtx); 126 state = state->BindExpr(CE, callerCtx, V); 127 } 128 129 // Bind the constructed object value to CXXConstructExpr. 130 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) { 131 loc::MemRegionVal This = 132 svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx); 133 SVal ThisV = state->getSVal(This); 134 135 // Always bind the region to the CXXConstructExpr. 136 state = state->BindExpr(CCE, CEBNode->getLocationContext(), ThisV); 137 } 138 139 static SimpleProgramPointTag retValBindTag("ExprEngine : Bind Return Value"); 140 PostStmt Loc(LastSt, calleeCtx, &retValBindTag); 141 bool isNew; 142 ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew); 143 BindedRetNode->addPredecessor(CEBNode, G); 144 if (!isNew) 145 return; 146 147 // Step 3: BindedRetNode -> CleanedNodes 148 // If we can find a statement and a block in the inlined function, run remove 149 // dead bindings before returning from the call. This is important to ensure 150 // that we report the issues such as leaks in the stack contexts in which 151 // they occurred. 152 ExplodedNodeSet CleanedNodes; 153 if (LastSt && Blk) { 154 NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode); 155 currentBuilderContext = &Ctx; 156 // Here, we call the Symbol Reaper with 0 statement and caller location 157 // context, telling it to clean up everything in the callee's context 158 // (and it's children). We use LastStmt as a diagnostic statement, which 159 // which the PreStmtPurge Dead point will be associated. 160 removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt, 161 ProgramPoint::PostStmtPurgeDeadSymbolsKind); 162 currentBuilderContext = 0; 163 } else { 164 CleanedNodes.Add(CEBNode); 165 } 166 167 for (ExplodedNodeSet::iterator I = CleanedNodes.begin(), 168 E = CleanedNodes.end(); I != E; ++I) { 169 170 // Step 4: Generate the CallExit and leave the callee's context. 171 // CleanedNodes -> CEENode 172 CallExitEnd Loc(CE, callerCtx); 173 bool isNew; 174 ExplodedNode *CEENode = G.getNode(Loc, (*I)->getState(), false, &isNew); 175 CEENode->addPredecessor(*I, G); 176 if (!isNew) 177 return; 178 179 // Step 5: Perform the post-condition check of the CallExpr and enqueue the 180 // result onto the work list. 181 // CEENode -> Dst -> WorkList 182 ExplodedNodeSet Dst; 183 NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode); 184 SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext, 185 &Ctx); 186 SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex()); 187 188 getCheckerManager().runCheckersForPostStmt(Dst, CEENode, CE, *this, true); 189 190 // Enqueue the next element in the block. 191 for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end(); 192 PSI != PSE; ++PSI) { 193 Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(), 194 calleeCtx->getIndex()+1); 195 } 196 } 197} 198 199static unsigned getNumberStackFrames(const LocationContext *LCtx) { 200 unsigned count = 0; 201 while (LCtx) { 202 if (isa<StackFrameContext>(LCtx)) 203 ++count; 204 LCtx = LCtx->getParent(); 205 } 206 return count; 207} 208 209// Determine if we should inline the call. 210bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) { 211 // FIXME: default constructors don't have bodies. 212 if (!D->hasBody()) 213 return false; 214 215 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D); 216 const CFG *CalleeCFG = CalleeADC->getCFG(); 217 218 // It is possible that the CFG cannot be constructed. 219 // Be safe, and check if the CalleeCFG is valid. 220 if (!CalleeCFG) 221 return false; 222 223 if (getNumberStackFrames(Pred->getLocationContext()) 224 == AMgr.InlineMaxStackDepth) 225 return false; 226 227 if (Engine.FunctionSummaries->hasReachedMaxBlockCount(D)) 228 return false; 229 230 if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize) 231 return false; 232 233 // Do not inline variadic calls (for now). 234 if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { 235 if (BD->isVariadic()) 236 return false; 237 } 238 else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 239 if (FD->isVariadic()) 240 return false; 241 } 242 243 // Do not inline constructors until we can model destructors. 244 // This is unfortunate, but basically necessary for smart pointers and such. 245 if (isa<CXXConstructorDecl>(D)) 246 return false; 247 248 // It is possible that the live variables analysis cannot be 249 // run. If so, bail out. 250 if (!CalleeADC->getAnalysis<RelaxedLiveVariables>()) 251 return false; 252 253 return true; 254} 255 256bool ExprEngine::inlineCall(ExplodedNodeSet &Dst, 257 const CallEvent &Call, 258 ExplodedNode *Pred) { 259 if (!getAnalysisManager().shouldInlineCall()) 260 return false; 261 262 const StackFrameContext *CallerSFC = 263 Pred->getLocationContext()->getCurrentStackFrame(); 264 265 const Decl *D = Call.getDecl(); 266 const LocationContext *ParentOfCallee = 0; 267 268 switch (Call.getKind()) { 269 case CE_Function: 270 case CE_CXXConstructor: 271 case CE_CXXMember: 272 // These are always at least possible to inline. 273 break; 274 case CE_Block: { 275 const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion(); 276 if (!BR) 277 return false; 278 D = BR->getDecl(); 279 AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D); 280 ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC, 281 cast<BlockDecl>(D), 282 BR); 283 break; 284 } 285 case CE_ObjCMessage: 286 case CE_ObjCPropertyAccess: 287 // These always use dynamic dispatch; enabling inlining means assuming 288 // that a particular method will be called at runtime. 289 return false; 290 } 291 292 if (!D || !shouldInlineDecl(D, Pred)) 293 return false; 294 295 if (!ParentOfCallee) 296 ParentOfCallee = CallerSFC; 297 298 const Expr *CallE = Call.getOriginExpr(); 299 assert(CallE && "It is not yet possible to have calls without statements"); 300 301 // Construct a new stack frame for the callee. 302 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D); 303 const StackFrameContext *CalleeSFC = 304 CalleeADC->getStackFrame(ParentOfCallee, CallE, 305 currentBuilderContext->getBlock(), 306 currentStmtIdx); 307 308 CallEnter Loc(CallE, CalleeSFC, Pred->getLocationContext()); 309 bool isNew; 310 if (ExplodedNode *N = G.getNode(Loc, Pred->getState(), false, &isNew)) { 311 N->addPredecessor(Pred, G); 312 if (isNew) 313 Engine.getWorkList()->enqueue(N); 314 } 315 return true; 316} 317 318static ProgramStateRef getInlineFailedState(ExplodedNode *&N, 319 const Stmt *CallE) { 320 void *ReplayState = N->getState()->get<ReplayWithoutInlining>(); 321 if (!ReplayState) 322 return 0; 323 const Stmt *ReplayCallE = reinterpret_cast<const Stmt *>(ReplayState); 324 if (CallE == ReplayCallE) { 325 return N->getState()->remove<ReplayWithoutInlining>(); 326 } 327 return 0; 328} 329 330void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, 331 ExplodedNodeSet &dst) { 332 // Perform the previsit of the CallExpr. 333 ExplodedNodeSet dstPreVisit; 334 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 335 336 // Get the callee kind. 337 const CXXMemberCallExpr *MemberCE = dyn_cast<CXXMemberCallExpr>(CE); 338 bool IsBlock = (MemberCE ? false 339 : CE->getCallee()->getType()->isBlockPointerType()); 340 341 // Evaluate the function call. We try each of the checkers 342 // to see if the can evaluate the function call. 343 ExplodedNodeSet dstCallEvaluated; 344 for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end(); 345 I != E; ++I) { 346 ProgramStateRef State = (*I)->getState(); 347 const LocationContext *LCtx = (*I)->getLocationContext(); 348 349 // Evaluate the call. 350 if (MemberCE) 351 evalCall(dstCallEvaluated, *I, CXXMemberCall(MemberCE, State, LCtx)); 352 else if (IsBlock) 353 evalCall(dstCallEvaluated, *I, BlockCall(CE, State, LCtx)); 354 else 355 evalCall(dstCallEvaluated, *I, FunctionCall(CE, State, LCtx)); 356 } 357 358 // Finally, perform the post-condition check of the CallExpr and store 359 // the created nodes in 'Dst'. 360 // Note that if the call was inlined, dstCallEvaluated will be empty. 361 // The post-CallExpr check will occur in processCallExit. 362 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 363 *this); 364} 365 366void ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred, 367 const SimpleCall &Call) { 368 // Run any pre-call checks using the generic call interface. 369 ExplodedNodeSet dstPreVisit; 370 getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this); 371 372 // Actually evaluate the function call. We try each of the checkers 373 // to see if the can evaluate the function call, and get a callback at 374 // defaultEvalCall if all of them fail. 375 ExplodedNodeSet dstCallEvaluated; 376 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit, 377 Call, *this); 378 379 // Finally, run any post-call checks. 380 getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated, 381 Call, *this); 382} 383 384void ExprEngine::defaultEvalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred, 385 const CallEvent &Call) { 386 // Try to inline the call. 387 ProgramStateRef state = 0; 388 const Expr *E = Call.getOriginExpr(); 389 if (E) { 390 state = getInlineFailedState(Pred, E); 391 if (state == 0 && inlineCall(Dst, Call, Pred)) 392 return; 393 } 394 395 // If we can't inline it, handle the return value and invalidate the regions. 396 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 397 398 // Invalidate any regions touched by the call. 399 unsigned Count = currentBuilderContext->getCurrentBlockCount(); 400 if (state == 0) 401 state = Pred->getState(); 402 state = Call.invalidateRegions(Count, state); 403 404 // Conjure a symbol value to use as the result. 405 assert(Call.getOriginExpr() && "Must have an expression to bind the result"); 406 QualType ResultTy = Call.getResultType(); 407 SValBuilder &SVB = getSValBuilder(); 408 const LocationContext *LCtx = Pred->getLocationContext(); 409 SVal RetVal = SVB.getConjuredSymbolVal(0, Call.getOriginExpr(), LCtx, 410 ResultTy, Count); 411 412 // And make the result node. 413 state = state->BindExpr(Call.getOriginExpr(), LCtx, RetVal); 414 Bldr.generateNode(Call.getOriginExpr(), Pred, state); 415} 416 417void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 418 ExplodedNodeSet &Dst) { 419 420 ExplodedNodeSet dstPreVisit; 421 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this); 422 423 StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); 424 425 if (RS->getRetValue()) { 426 for (ExplodedNodeSet::iterator it = dstPreVisit.begin(), 427 ei = dstPreVisit.end(); it != ei; ++it) { 428 B.generateNode(RS, *it, (*it)->getState()); 429 } 430 } 431} 432