ExprEngineCallAndReturn.cpp revision 0b3ade86a1c60cf0c7b56aa238aff458eb7f5974
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/CheckerManager.h" 15#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 17#include "clang/AST/DeclCXX.h" 18#include "llvm/ADT/SmallSet.h" 19#include "llvm/Support/SaveAndRestore.h" 20 21using namespace clang; 22using namespace ento; 23 24void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) { 25 // Get the entry block in the CFG of the callee. 26 const StackFrameContext *calleeCtx = CE.getCalleeContext(); 27 const CFG *CalleeCFG = calleeCtx->getCFG(); 28 const CFGBlock *Entry = &(CalleeCFG->getEntry()); 29 30 // Validate the CFG. 31 assert(Entry->empty()); 32 assert(Entry->succ_size() == 1); 33 34 // Get the solitary sucessor. 35 const CFGBlock *Succ = *(Entry->succ_begin()); 36 37 // Construct an edge representing the starting location in the callee. 38 BlockEdge Loc(Entry, Succ, calleeCtx); 39 40 // Construct a new state which contains the mapping from actual to 41 // formal arguments. 42 const LocationContext *callerCtx = Pred->getLocationContext(); 43 ProgramStateRef state = Pred->getState()->enterStackFrame(callerCtx, 44 calleeCtx); 45 46 // Construct a new node and add it to the worklist. 47 bool isNew; 48 ExplodedNode *Node = G.getNode(Loc, state, false, &isNew); 49 Node->addPredecessor(Pred, G); 50 if (isNew) 51 Engine.getWorkList()->enqueue(Node); 52} 53 54// Find the last statement on the path to the exploded node and the 55// corresponding Block. 56static std::pair<const Stmt*, 57 const CFGBlock*> getLastStmt(const ExplodedNode *Node) { 58 const Stmt *S = 0; 59 const CFGBlock *Blk = 0; 60 const StackFrameContext *SF = 61 Node->getLocation().getLocationContext()->getCurrentStackFrame(); 62 while (Node) { 63 const ProgramPoint &PP = Node->getLocation(); 64 // Skip any BlockEdges, empty blocks, and the CallExitBegin node. 65 if (isa<BlockEdge>(PP) || isa<CallExitBegin>(PP) || isa<BlockEntrance>(PP)){ 66 assert(Node->pred_size() == 1); 67 Node = *Node->pred_begin(); 68 continue; 69 } 70 // If we reached the CallEnter, the function has no statements. 71 if (isa<CallEnter>(PP)) 72 break; 73 if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) { 74 S = SP->getStmt(); 75 // Now, get the enclosing basic block. 76 while (Node && Node->pred_size() >=1 ) { 77 const ProgramPoint &PP = Node->getLocation(); 78 if (isa<BlockEdge>(PP) && 79 (PP.getLocationContext()->getCurrentStackFrame() == SF)) { 80 BlockEdge &EPP = cast<BlockEdge>(PP); 81 Blk = EPP.getDst(); 82 break; 83 } 84 Node = *Node->pred_begin(); 85 } 86 break; 87 } 88 break; 89 } 90 return std::pair<const Stmt*, const CFGBlock*>(S, Blk); 91} 92 93/// The call exit is simulated with a sequence of nodes, which occur between 94/// CallExitBegin and CallExitEnd. The following operations occur between the 95/// two program points: 96/// 1. CallExitBegin (triggers the start of call exit sequence) 97/// 2. Bind the return value 98/// 3. Run Remove dead bindings to clean up the dead symbols from the callee. 99/// 4. CallExitEnd (switch to the caller context) 100/// 5. PostStmt<CallExpr> 101void ExprEngine::processCallExit(ExplodedNode *CEBNode) { 102 // Step 1 CEBNode was generated before the call. 103 104 const StackFrameContext *calleeCtx = 105 CEBNode->getLocationContext()->getCurrentStackFrame(); 106 const LocationContext *callerCtx = calleeCtx->getParent(); 107 const Stmt *CE = calleeCtx->getCallSite(); 108 ProgramStateRef state = CEBNode->getState(); 109 // Find the last statement in the function and the corresponding basic block. 110 const Stmt *LastSt = 0; 111 const CFGBlock *Blk = 0; 112 llvm::tie(LastSt, Blk) = getLastStmt(CEBNode); 113 114 // Step 2: generate node with binded return value: CEBNode -> BindedRetNode. 115 116 // If the callee returns an expression, bind its value to CallExpr. 117 if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) { 118 const LocationContext *LCtx = CEBNode->getLocationContext(); 119 SVal V = state->getSVal(RS, LCtx); 120 state = state->BindExpr(CE, callerCtx, V); 121 } 122 123 // Bind the constructed object value to CXXConstructExpr. 124 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) { 125 const CXXThisRegion *ThisR = 126 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx); 127 128 SVal ThisV = state->getSVal(ThisR); 129 // Always bind the region to the CXXConstructExpr. 130 state = state->BindExpr(CCE, CEBNode->getLocationContext(), ThisV); 131 } 132 133 static SimpleProgramPointTag retValBindTag("ExprEngine : Bind Return Value"); 134 PostStmt Loc(LastSt, calleeCtx, &retValBindTag); 135 bool isNew; 136 ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew); 137 BindedRetNode->addPredecessor(CEBNode, G); 138 if (!isNew) 139 return; 140 141 // Step 3: BindedRetNode -> CleanedNodes 142 // If we can find a statement and a block in the inlined function, run remove 143 // dead bindings before returning from the call. This is important to ensure 144 // that we report the issues such as leaks in the stack contexts in which 145 // they occurred. 146 ExplodedNodeSet CleanedNodes; 147 if (LastSt && Blk) { 148 NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode); 149 currentBuilderContext = &Ctx; 150 // Here, we call the Symbol Reaper with 0 statement and caller location 151 // context, telling it to clean up everything in the callee's context 152 // (and it's children). We use LastStmt as a diagnostic statement, which 153 // which the PreStmtPurge Dead point will be associated. 154 removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt, 155 ProgramPoint::PostStmtPurgeDeadSymbolsKind); 156 currentBuilderContext = 0; 157 } 158 159 for (ExplodedNodeSet::iterator I = CleanedNodes.begin(), 160 E = CleanedNodes.end(); I != E; ++I) { 161 162 // Step 4: Generate the CallExit and leave the callee's context. 163 // CleanedNodes -> CEENode 164 CallExitEnd Loc(CE, callerCtx); 165 bool isNew; 166 ExplodedNode *CEENode = G.getNode(Loc, (*I)->getState(), false, &isNew); 167 CEENode->addPredecessor(*I, G); 168 if (!isNew) 169 return; 170 171 // Step 5: Perform the post-condition check of the CallExpr and enqueue the 172 // result onto the work list. 173 // CEENode -> Dst -> WorkList 174 ExplodedNodeSet Dst; 175 NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode); 176 SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext, 177 &Ctx); 178 SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex()); 179 180 getCheckerManager().runCheckersForPostStmt(Dst, CEENode, CE, *this, true); 181 182 // Enqueue the next element in the block. 183 for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end(); 184 PSI != PSE; ++PSI) { 185 Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(), 186 calleeCtx->getIndex()+1); 187 } 188 } 189} 190 191static unsigned getNumberStackFrames(const LocationContext *LCtx) { 192 unsigned count = 0; 193 while (LCtx) { 194 if (isa<StackFrameContext>(LCtx)) 195 ++count; 196 LCtx = LCtx->getParent(); 197 } 198 return count; 199} 200 201// Determine if we should inline the call. 202bool ExprEngine::shouldInlineDecl(const FunctionDecl *FD, ExplodedNode *Pred) { 203 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(FD); 204 const CFG *CalleeCFG = CalleeADC->getCFG(); 205 206 // It is possible that the CFG cannot be constructed. 207 // Be safe, and check if the CalleeCFG is valid. 208 if (!CalleeCFG) 209 return false; 210 211 if (getNumberStackFrames(Pred->getLocationContext()) 212 == AMgr.InlineMaxStackDepth) 213 return false; 214 215 if (Engine.FunctionSummaries->hasReachedMaxBlockCount(FD)) 216 return false; 217 218 if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize) 219 return false; 220 221 return true; 222} 223 224// For now, skip inlining variadic functions. 225// We also don't inline blocks. 226static bool shouldInlineCallExpr(const CallExpr *CE, ExprEngine *E) { 227 if (!E->getAnalysisManager().shouldInlineCall()) 228 return false; 229 QualType callee = CE->getCallee()->getType(); 230 const FunctionProtoType *FT = 0; 231 if (const PointerType *PT = callee->getAs<PointerType>()) 232 FT = dyn_cast<FunctionProtoType>(PT->getPointeeType()); 233 else if (const BlockPointerType *BT = callee->getAs<BlockPointerType>()) { 234 // FIXME: inline blocks. 235 // FT = dyn_cast<FunctionProtoType>(BT->getPointeeType()); 236 (void) BT; 237 return false; 238 } 239 // If we have no prototype, assume the function is okay. 240 if (!FT) 241 return true; 242 243 // Skip inlining of variadic functions. 244 return !FT->isVariadic(); 245} 246 247bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, 248 const CallExpr *CE, 249 ExplodedNode *Pred) { 250 if (!shouldInlineCallExpr(CE, this)) 251 return false; 252 253 ProgramStateRef state = Pred->getState(); 254 const Expr *Callee = CE->getCallee(); 255 const FunctionDecl *FD = 256 state->getSVal(Callee, Pred->getLocationContext()).getAsFunctionDecl(); 257 if (!FD || !FD->hasBody(FD)) 258 return false; 259 260 switch (CE->getStmtClass()) { 261 default: 262 // FIXME: Handle C++. 263 break; 264 case Stmt::CallExprClass: { 265 if (!shouldInlineDecl(FD, Pred)) 266 return false; 267 268 // Construct a new stack frame for the callee. 269 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(FD); 270 const StackFrameContext *CallerSFC = 271 Pred->getLocationContext()->getCurrentStackFrame(); 272 const StackFrameContext *CalleeSFC = 273 CalleeADC->getStackFrame(CallerSFC, CE, 274 currentBuilderContext->getBlock(), 275 currentStmtIdx); 276 277 CallEnter Loc(CE, CalleeSFC, Pred->getLocationContext()); 278 bool isNew; 279 if (ExplodedNode *N = G.getNode(Loc, state, false, &isNew)) { 280 N->addPredecessor(Pred, G); 281 if (isNew) 282 Engine.getWorkList()->enqueue(N); 283 } 284 return true; 285 } 286 } 287 return false; 288} 289 290static bool isPointerToConst(const ParmVarDecl *ParamDecl) { 291 QualType PointeeTy = ParamDecl->getOriginalType()->getPointeeType(); 292 if (PointeeTy != QualType() && PointeeTy.isConstQualified() && 293 !PointeeTy->isAnyPointerType() && !PointeeTy->isReferenceType()) { 294 return true; 295 } 296 return false; 297} 298 299// Try to retrieve the function declaration and find the function parameter 300// types which are pointers/references to a non-pointer const. 301// We do not invalidate the corresponding argument regions. 302static void findPtrToConstParams(llvm::SmallSet<unsigned, 1> &PreserveArgs, 303 const CallOrObjCMessage &Call) { 304 const Decl *CallDecl = Call.getDecl(); 305 if (!CallDecl) 306 return; 307 308 if (const FunctionDecl *FDecl = dyn_cast<FunctionDecl>(CallDecl)) { 309 const IdentifierInfo *II = FDecl->getIdentifier(); 310 311 // List the cases, where the region should be invalidated even if the 312 // argument is const. 313 if (II) { 314 StringRef FName = II->getName(); 315 // - 'int pthread_setspecific(ptheread_key k, const void *)' stores a 316 // value into thread local storage. The value can later be retrieved with 317 // 'void *ptheread_getspecific(pthread_key)'. So even thought the 318 // parameter is 'const void *', the region escapes through the call. 319 // - funopen - sets a buffer for future IO calls. 320 // - ObjC functions that end with "NoCopy" can free memory, of the passed 321 // in buffer. 322 // - Many CF containers allow objects to escape through custom 323 // allocators/deallocators upon container construction. 324 // - NSXXInsertXX, for example NSMapInsertIfAbsent, since they can 325 // be deallocated by NSMapRemove. 326 if (FName == "pthread_setspecific" || 327 FName == "funopen" || 328 FName.endswith("NoCopy") || 329 (FName.startswith("NS") && 330 (FName.find("Insert") != StringRef::npos)) || 331 Call.isCFCGAllowingEscape(FName)) 332 return; 333 } 334 335 for (unsigned Idx = 0, E = Call.getNumArgs(); Idx != E; ++Idx) { 336 if (FDecl && Idx < FDecl->getNumParams()) { 337 if (isPointerToConst(FDecl->getParamDecl(Idx))) 338 PreserveArgs.insert(Idx); 339 } 340 } 341 return; 342 } 343 344 if (const ObjCMethodDecl *MDecl = dyn_cast<ObjCMethodDecl>(CallDecl)) { 345 assert(MDecl->param_size() <= Call.getNumArgs()); 346 unsigned Idx = 0; 347 for (clang::ObjCMethodDecl::param_const_iterator 348 I = MDecl->param_begin(), E = MDecl->param_end(); I != E; ++I, ++Idx) { 349 if (isPointerToConst(*I)) 350 PreserveArgs.insert(Idx); 351 } 352 return; 353 } 354} 355 356ProgramStateRef 357ExprEngine::invalidateArguments(ProgramStateRef State, 358 const CallOrObjCMessage &Call, 359 const LocationContext *LC) { 360 SmallVector<const MemRegion *, 8> RegionsToInvalidate; 361 362 if (Call.isObjCMessage()) { 363 // Invalidate all instance variables of the receiver of an ObjC message. 364 // FIXME: We should be able to do better with inter-procedural analysis. 365 if (const MemRegion *MR = Call.getInstanceMessageReceiver(LC).getAsRegion()) 366 RegionsToInvalidate.push_back(MR); 367 368 } else if (Call.isCXXCall()) { 369 // Invalidate all instance variables for the callee of a C++ method call. 370 // FIXME: We should be able to do better with inter-procedural analysis. 371 // FIXME: We can probably do better for const versus non-const methods. 372 if (const MemRegion *Callee = Call.getCXXCallee().getAsRegion()) 373 RegionsToInvalidate.push_back(Callee); 374 375 } else if (Call.isFunctionCall()) { 376 // Block calls invalidate all captured-by-reference values. 377 SVal CalleeVal = Call.getFunctionCallee(); 378 if (const MemRegion *Callee = CalleeVal.getAsRegion()) { 379 if (isa<BlockDataRegion>(Callee)) 380 RegionsToInvalidate.push_back(Callee); 381 } 382 } 383 384 // Indexes of arguments whose values will be preserved by the call. 385 llvm::SmallSet<unsigned, 1> PreserveArgs; 386 findPtrToConstParams(PreserveArgs, Call); 387 388 for (unsigned idx = 0, e = Call.getNumArgs(); idx != e; ++idx) { 389 if (PreserveArgs.count(idx)) 390 continue; 391 392 SVal V = Call.getArgSVal(idx); 393 394 // If we are passing a location wrapped as an integer, unwrap it and 395 // invalidate the values referred by the location. 396 if (nonloc::LocAsInteger *Wrapped = dyn_cast<nonloc::LocAsInteger>(&V)) 397 V = Wrapped->getLoc(); 398 else if (!isa<Loc>(V)) 399 continue; 400 401 if (const MemRegion *R = V.getAsRegion()) { 402 // Invalidate the value of the variable passed by reference. 403 404 // Are we dealing with an ElementRegion? If the element type is 405 // a basic integer type (e.g., char, int) and the underlying region 406 // is a variable region then strip off the ElementRegion. 407 // FIXME: We really need to think about this for the general case 408 // as sometimes we are reasoning about arrays and other times 409 // about (char*), etc., is just a form of passing raw bytes. 410 // e.g., void *p = alloca(); foo((char*)p); 411 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 412 // Checking for 'integral type' is probably too promiscuous, but 413 // we'll leave it in for now until we have a systematic way of 414 // handling all of these cases. Eventually we need to come up 415 // with an interface to StoreManager so that this logic can be 416 // appropriately delegated to the respective StoreManagers while 417 // still allowing us to do checker-specific logic (e.g., 418 // invalidating reference counts), probably via callbacks. 419 if (ER->getElementType()->isIntegralOrEnumerationType()) { 420 const MemRegion *superReg = ER->getSuperRegion(); 421 if (isa<VarRegion>(superReg) || isa<FieldRegion>(superReg) || 422 isa<ObjCIvarRegion>(superReg)) 423 R = cast<TypedRegion>(superReg); 424 } 425 // FIXME: What about layers of ElementRegions? 426 } 427 428 // Mark this region for invalidation. We batch invalidate regions 429 // below for efficiency. 430 RegionsToInvalidate.push_back(R); 431 } else { 432 // Nuke all other arguments passed by reference. 433 // FIXME: is this necessary or correct? This handles the non-Region 434 // cases. Is it ever valid to store to these? 435 State = State->unbindLoc(cast<Loc>(V)); 436 } 437 } 438 439 // Invalidate designated regions using the batch invalidation API. 440 441 // FIXME: We can have collisions on the conjured symbol if the 442 // expression *I also creates conjured symbols. We probably want 443 // to identify conjured symbols by an expression pair: the enclosing 444 // expression (the context) and the expression itself. This should 445 // disambiguate conjured symbols. 446 unsigned Count = currentBuilderContext->getCurrentBlockCount(); 447 StoreManager::InvalidatedSymbols IS; 448 449 // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate 450 // global variables. 451 return State->invalidateRegions(RegionsToInvalidate, 452 Call.getOriginExpr(), Count, LC, 453 &IS, &Call); 454 455} 456 457static ProgramStateRef getReplayWithoutInliningState(ExplodedNode *&N, 458 const CallExpr *CE) { 459 void *ReplayState = N->getState()->get<ReplayWithoutInlining>(); 460 if (!ReplayState) 461 return 0; 462 const CallExpr *ReplayCE = reinterpret_cast<const CallExpr*>(ReplayState); 463 if (CE == ReplayCE) { 464 return N->getState()->remove<ReplayWithoutInlining>(); 465 } 466 return 0; 467} 468 469void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, 470 ExplodedNodeSet &dst) { 471 // Perform the previsit of the CallExpr. 472 ExplodedNodeSet dstPreVisit; 473 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 474 475 // Now evaluate the call itself. 476 class DefaultEval : public GraphExpander { 477 ExprEngine &Eng; 478 const CallExpr *CE; 479 public: 480 481 DefaultEval(ExprEngine &eng, const CallExpr *ce) 482 : Eng(eng), CE(ce) {} 483 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) { 484 485 ProgramStateRef state = getReplayWithoutInliningState(Pred, CE); 486 487 // First, try to inline the call. 488 if (state == 0 && Eng.InlineCall(Dst, CE, Pred)) 489 return; 490 491 // First handle the return value. 492 StmtNodeBuilder Bldr(Pred, Dst, *Eng.currentBuilderContext); 493 494 // Get the callee. 495 const Expr *Callee = CE->getCallee()->IgnoreParens(); 496 if (state == 0) 497 state = Pred->getState(); 498 SVal L = state->getSVal(Callee, Pred->getLocationContext()); 499 500 // Figure out the result type. We do this dance to handle references. 501 QualType ResultTy; 502 if (const FunctionDecl *FD = L.getAsFunctionDecl()) 503 ResultTy = FD->getResultType(); 504 else 505 ResultTy = CE->getType(); 506 507 if (CE->isLValue()) 508 ResultTy = Eng.getContext().getPointerType(ResultTy); 509 510 // Conjure a symbol value to use as the result. 511 SValBuilder &SVB = Eng.getSValBuilder(); 512 unsigned Count = Eng.currentBuilderContext->getCurrentBlockCount(); 513 const LocationContext *LCtx = Pred->getLocationContext(); 514 SVal RetVal = SVB.getConjuredSymbolVal(0, CE, LCtx, ResultTy, Count); 515 516 // Generate a new state with the return value set. 517 state = state->BindExpr(CE, LCtx, RetVal); 518 519 // Invalidate the arguments. 520 state = Eng.invalidateArguments(state, CallOrObjCMessage(CE, state, LCtx), 521 LCtx); 522 523 // And make the result node. 524 Bldr.generateNode(CE, Pred, state); 525 } 526 }; 527 528 // Finally, evaluate the function call. We try each of the checkers 529 // to see if the can evaluate the function call. 530 ExplodedNodeSet dstCallEvaluated; 531 DefaultEval defEval(*this, CE); 532 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, 533 dstPreVisit, 534 CE, *this, &defEval); 535 536 // Finally, perform the post-condition check of the CallExpr and store 537 // the created nodes in 'Dst'. 538 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 539 *this); 540} 541 542void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 543 ExplodedNodeSet &Dst) { 544 545 ExplodedNodeSet dstPreVisit; 546 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this); 547 548 StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); 549 550 if (RS->getRetValue()) { 551 for (ExplodedNodeSet::iterator it = dstPreVisit.begin(), 552 ei = dstPreVisit.end(); it != ei; ++it) { 553 B.generateNode(RS, *it, (*it)->getState()); 554 } 555 } 556} 557