ExprEngineCallAndReturn.cpp revision 70cbf3cc09eb21db1108396d30a414ea66d842cc
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 // It is possible that the live variables analysis cannot be 244 // run. If so, bail out. 245 if (!CalleeADC->getAnalysis<RelaxedLiveVariables>()) 246 return false; 247 248 return true; 249} 250 251bool ExprEngine::inlineCall(ExplodedNodeSet &Dst, 252 const CallEvent &Call, 253 ExplodedNode *Pred) { 254 if (!getAnalysisManager().shouldInlineCall()) 255 return false; 256 257 const StackFrameContext *CallerSFC = 258 Pred->getLocationContext()->getCurrentStackFrame(); 259 260 const Decl *D = Call.getDecl(); 261 const LocationContext *ParentOfCallee = 0; 262 263 switch (Call.getKind()) { 264 case CE_Function: 265 case CE_CXXMember: 266 // These are always at least possible to inline. 267 break; 268 case CE_CXXConstructor: 269 // Do not inline constructors until we can model destructors. 270 // This is unfortunate, but basically necessary for smart pointers and such. 271 return false; 272 case CE_CXXAllocator: 273 // Do not inline allocators until we model deallocators. 274 // This is unfortunate, but basically necessary for smart pointers and such. 275 return false; 276 case CE_Block: { 277 const BlockDataRegion *BR = cast<BlockCall>(Call).getBlockRegion(); 278 if (!BR) 279 return false; 280 D = BR->getDecl(); 281 AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(D); 282 ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC, 283 cast<BlockDecl>(D), 284 BR); 285 break; 286 } 287 case CE_ObjCMessage: 288 case CE_ObjCPropertyAccess: 289 // These always use dynamic dispatch; enabling inlining means assuming 290 // that a particular method will be called at runtime. 291 return false; 292 } 293 294 if (!D || !shouldInlineDecl(D, Pred)) 295 return false; 296 297 if (!ParentOfCallee) 298 ParentOfCallee = CallerSFC; 299 300 const Expr *CallE = Call.getOriginExpr(); 301 assert(CallE && "It is not yet possible to have calls without statements"); 302 303 // Construct a new stack frame for the callee. 304 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D); 305 const StackFrameContext *CalleeSFC = 306 CalleeADC->getStackFrame(ParentOfCallee, CallE, 307 currentBuilderContext->getBlock(), 308 currentStmtIdx); 309 310 CallEnter Loc(CallE, CalleeSFC, Pred->getLocationContext()); 311 bool isNew; 312 if (ExplodedNode *N = G.getNode(Loc, Pred->getState(), false, &isNew)) { 313 N->addPredecessor(Pred, G); 314 if (isNew) 315 Engine.getWorkList()->enqueue(N); 316 } 317 return true; 318} 319 320static ProgramStateRef getInlineFailedState(ExplodedNode *&N, 321 const Stmt *CallE) { 322 void *ReplayState = N->getState()->get<ReplayWithoutInlining>(); 323 if (!ReplayState) 324 return 0; 325 const Stmt *ReplayCallE = reinterpret_cast<const Stmt *>(ReplayState); 326 if (CallE == ReplayCallE) { 327 return N->getState()->remove<ReplayWithoutInlining>(); 328 } 329 return 0; 330} 331 332void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, 333 ExplodedNodeSet &dst) { 334 // Perform the previsit of the CallExpr. 335 ExplodedNodeSet dstPreVisit; 336 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 337 338 // Get the callee kind. 339 const CXXMemberCallExpr *MemberCE = dyn_cast<CXXMemberCallExpr>(CE); 340 bool IsBlock = (MemberCE ? false 341 : CE->getCallee()->getType()->isBlockPointerType()); 342 343 // Evaluate the function call. We try each of the checkers 344 // to see if the can evaluate the function call. 345 ExplodedNodeSet dstCallEvaluated; 346 for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end(); 347 I != E; ++I) { 348 ProgramStateRef State = (*I)->getState(); 349 const LocationContext *LCtx = (*I)->getLocationContext(); 350 351 // Evaluate the call. 352 if (MemberCE) 353 evalCall(dstCallEvaluated, *I, CXXMemberCall(MemberCE, State, LCtx)); 354 else if (IsBlock) 355 evalCall(dstCallEvaluated, *I, BlockCall(CE, State, LCtx)); 356 else 357 evalCall(dstCallEvaluated, *I, FunctionCall(CE, State, LCtx)); 358 } 359 360 // Finally, perform the post-condition check of the CallExpr and store 361 // the created nodes in 'Dst'. 362 // Note that if the call was inlined, dstCallEvaluated will be empty. 363 // The post-CallExpr check will occur in processCallExit. 364 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 365 *this); 366} 367 368void ExprEngine::evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred, 369 const SimpleCall &Call) { 370 // Run any pre-call checks using the generic call interface. 371 ExplodedNodeSet dstPreVisit; 372 getCheckerManager().runCheckersForPreCall(dstPreVisit, Pred, Call, *this); 373 374 // Actually evaluate the function call. We try each of the checkers 375 // to see if the can evaluate the function call, and get a callback at 376 // defaultEvalCall if all of them fail. 377 ExplodedNodeSet dstCallEvaluated; 378 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, dstPreVisit, 379 Call, *this); 380 381 // Finally, run any post-call checks. 382 getCheckerManager().runCheckersForPostCall(Dst, dstCallEvaluated, 383 Call, *this); 384} 385 386void ExprEngine::defaultEvalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred, 387 const CallEvent &Call) { 388 // Try to inline the call. 389 ProgramStateRef state = 0; 390 const Expr *E = Call.getOriginExpr(); 391 if (E) { 392 state = getInlineFailedState(Pred, E); 393 if (state == 0 && inlineCall(Dst, Call, Pred)) 394 return; 395 } 396 397 // If we can't inline it, handle the return value and invalidate the regions. 398 StmtNodeBuilder Bldr(Pred, Dst, *currentBuilderContext); 399 400 // Invalidate any regions touched by the call. 401 unsigned Count = currentBuilderContext->getCurrentBlockCount(); 402 if (state == 0) 403 state = Pred->getState(); 404 state = Call.invalidateRegions(Count, state); 405 406 // Conjure a symbol value to use as the result. 407 assert(Call.getOriginExpr() && "Must have an expression to bind the result"); 408 QualType ResultTy = Call.getResultType(); 409 SValBuilder &SVB = getSValBuilder(); 410 const LocationContext *LCtx = Pred->getLocationContext(); 411 SVal RetVal = SVB.getConjuredSymbolVal(0, Call.getOriginExpr(), LCtx, 412 ResultTy, Count); 413 414 // And make the result node. 415 state = state->BindExpr(Call.getOriginExpr(), LCtx, RetVal); 416 Bldr.generateNode(Call.getOriginExpr(), Pred, state); 417} 418 419void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 420 ExplodedNodeSet &Dst) { 421 422 ExplodedNodeSet dstPreVisit; 423 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this); 424 425 StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); 426 427 if (RS->getRetValue()) { 428 for (ExplodedNodeSet::iterator it = dstPreVisit.begin(), 429 ei = dstPreVisit.end(); it != ei; ++it) { 430 B.generateNode(RS, *it, (*it)->getState()); 431 } 432 } 433} 434