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