ExprEngineCallAndReturn.cpp revision 256ef642f8feef22fd53be7efa868e8e34752eed
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//=-- ExprEngineCallAndReturn.cpp - Support for call/return -----*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file defines ExprEngine's support for calls and returns. 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/CheckerManager.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Analysis/Support/SaveAndRestore.h" 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/DeclCXX.h" 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace clang; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace ento; 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) { 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the entry block in the CFG of the callee. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StackFrameContext *SFC = CE.getCalleeContext(); 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CFG *CalleeCFG = SFC->getCFG(); 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CFGBlock *Entry = &(CalleeCFG->getEntry()); 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Validate the CFG. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(Entry->empty()); 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(Entry->succ_size() == 1); 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the solitary sucessor. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CFGBlock *Succ = *(Entry->succ_begin()); 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Construct an edge representing the starting location in the callee. 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockEdge Loc(Entry, Succ, SFC); 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Construct a new state which contains the mapping from actual to 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // formal arguments. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ProgramState *state = Pred->getState()->enterStackFrame(SFC); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Construct a new node and add it to the worklist. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isNew; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Node = G.getNode(Loc, state, false, &isNew); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node->addPredecessor(Pred, G); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (isNew) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Engine.getWorkList()->enqueue(Node); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const ReturnStmt *getReturnStmt(const ExplodedNode *Node) { 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (Node) { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const ProgramPoint &PP = Node->getLocation(); 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Skip any BlockEdges. 55 if (isa<BlockEdge>(PP) || isa<CallExit>(PP)) { 56 assert(Node->pred_size() == 1); 57 Node = *Node->pred_begin(); 58 continue; 59 } 60 if (const StmtPoint *SP = dyn_cast<StmtPoint>(&PP)) { 61 const Stmt *S = SP->getStmt(); 62 return dyn_cast<ReturnStmt>(S); 63 } 64 break; 65 } 66 return 0; 67} 68 69void ExprEngine::processCallExit(ExplodedNode *Pred) { 70 const ProgramState *state = Pred->getState(); 71 const StackFrameContext *calleeCtx = 72 Pred->getLocationContext()->getCurrentStackFrame(); 73 const LocationContext *callerCtx = calleeCtx->getParent(); 74 const Stmt *CE = calleeCtx->getCallSite(); 75 76 // If the callee returns an expression, bind its value to CallExpr. 77 if (const ReturnStmt *RS = getReturnStmt(Pred)) { 78 const LocationContext *LCtx = Pred->getLocationContext(); 79 SVal V = state->getSVal(RS, LCtx); 80 state = state->BindExpr(CE, callerCtx, V); 81 } 82 83 // Bind the constructed object value to CXXConstructExpr. 84 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) { 85 const CXXThisRegion *ThisR = 86 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx); 87 88 SVal ThisV = state->getSVal(ThisR); 89 // Always bind the region to the CXXConstructExpr. 90 state = state->BindExpr(CCE, Pred->getLocationContext(), ThisV); 91 } 92 93 static SimpleProgramPointTag returnTag("ExprEngine : Call Return"); 94 PostStmt Loc(CE, callerCtx, &returnTag); 95 bool isNew; 96 ExplodedNode *N = G.getNode(Loc, state, false, &isNew); 97 N->addPredecessor(Pred, G); 98 if (!isNew) 99 return; 100 101 // Perform the post-condition check of the CallExpr. 102 ExplodedNodeSet Dst; 103 NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), N); 104 SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext, 105 &Ctx); 106 SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex()); 107 108 getCheckerManager().runCheckersForPostStmt(Dst, N, CE, *this); 109 110 // Enqueue the next element in the block. 111 for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end(); I != E; ++I) { 112 Engine.getWorkList()->enqueue(*I, 113 calleeCtx->getCallSiteBlock(), 114 calleeCtx->getIndex()+1); 115 } 116} 117 118bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, 119 const CallExpr *CE, 120 ExplodedNode *Pred) { 121 const ProgramState *state = Pred->getState(); 122 const Expr *Callee = CE->getCallee(); 123 const FunctionDecl *FD = 124 state->getSVal(Callee, Pred->getLocationContext()).getAsFunctionDecl(); 125 if (!FD || !FD->hasBody(FD)) 126 return false; 127 128 switch (CE->getStmtClass()) { 129 default: 130 // FIXME: Handle C++. 131 break; 132 case Stmt::CallExprClass: { 133 // Construct a new stack frame for the callee. 134 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(FD); 135 const StackFrameContext *CallerSFC = 136 Pred->getLocationContext()->getCurrentStackFrame(); 137 const StackFrameContext *CalleeSFC = 138 CalleeADC->getStackFrame(CallerSFC, CE, 139 currentBuilderContext->getBlock(), 140 currentStmtIdx); 141 142 CallEnter Loc(CE, CalleeSFC, Pred->getLocationContext()); 143 bool isNew; 144 ExplodedNode *N = G.getNode(Loc, state, false, &isNew); 145 N->addPredecessor(Pred, G); 146 if (isNew) 147 Engine.getWorkList()->enqueue(N); 148 return true; 149 } 150 } 151 return false; 152} 153 154static bool isPointerToConst(const ParmVarDecl *ParamDecl) { 155 QualType PointeeTy = ParamDecl->getOriginalType()->getPointeeType(); 156 if (PointeeTy != QualType() && PointeeTy.isConstQualified() && 157 !PointeeTy->isAnyPointerType() && !PointeeTy->isReferenceType()) { 158 return true; 159 } 160 return false; 161} 162 163// Try to retrieve the function declaration and find the function parameter 164// types which are pointers/references to a non-pointer const. 165// We do not invalidate the corresponding argument regions. 166static void findPtrToConstParams(llvm::SmallSet<unsigned, 1> &PreserveArgs, 167 const CallOrObjCMessage &Call) { 168 const Decl *CallDecl = Call.getDecl(); 169 if (!CallDecl) 170 return; 171 172 if (const FunctionDecl *FDecl = dyn_cast<FunctionDecl>(CallDecl)) { 173 for (unsigned Idx = 0, E = Call.getNumArgs(); Idx != E; ++Idx) { 174 if (FDecl && Idx < FDecl->getNumParams()) { 175 if (isPointerToConst(FDecl->getParamDecl(Idx))) 176 PreserveArgs.insert(Idx); 177 } 178 } 179 return; 180 } 181 182 if (const ObjCMethodDecl *MDecl = dyn_cast<ObjCMethodDecl>(CallDecl)) { 183 assert(MDecl->param_size() <= Call.getNumArgs()); 184 unsigned Idx = 0; 185 for (clang::ObjCMethodDecl::param_const_iterator 186 I = MDecl->param_begin(), E = MDecl->param_end(); I != E; ++I, ++Idx) { 187 if (isPointerToConst(*I)) 188 PreserveArgs.insert(Idx); 189 } 190 return; 191 } 192} 193 194const ProgramState * 195ExprEngine::invalidateArguments(const ProgramState *State, 196 const CallOrObjCMessage &Call, 197 const LocationContext *LC) { 198 SmallVector<const MemRegion *, 8> RegionsToInvalidate; 199 200 if (Call.isObjCMessage()) { 201 // Invalidate all instance variables of the receiver of an ObjC message. 202 // FIXME: We should be able to do better with inter-procedural analysis. 203 if (const MemRegion *MR = Call.getInstanceMessageReceiver(LC).getAsRegion()) 204 RegionsToInvalidate.push_back(MR); 205 206 } else if (Call.isCXXCall()) { 207 // Invalidate all instance variables for the callee of a C++ method call. 208 // FIXME: We should be able to do better with inter-procedural analysis. 209 // FIXME: We can probably do better for const versus non-const methods. 210 if (const MemRegion *Callee = Call.getCXXCallee().getAsRegion()) 211 RegionsToInvalidate.push_back(Callee); 212 213 } else if (Call.isFunctionCall()) { 214 // Block calls invalidate all captured-by-reference values. 215 SVal CalleeVal = Call.getFunctionCallee(); 216 if (const MemRegion *Callee = CalleeVal.getAsRegion()) { 217 if (isa<BlockDataRegion>(Callee)) 218 RegionsToInvalidate.push_back(Callee); 219 } 220 } 221 222 // Indexes of arguments whose values will be preserved by the call. 223 llvm::SmallSet<unsigned, 1> PreserveArgs; 224 findPtrToConstParams(PreserveArgs, Call); 225 226 for (unsigned idx = 0, e = Call.getNumArgs(); idx != e; ++idx) { 227 if (PreserveArgs.count(idx)) 228 continue; 229 230 SVal V = Call.getArgSVal(idx); 231 232 // If we are passing a location wrapped as an integer, unwrap it and 233 // invalidate the values referred by the location. 234 if (nonloc::LocAsInteger *Wrapped = dyn_cast<nonloc::LocAsInteger>(&V)) 235 V = Wrapped->getLoc(); 236 else if (!isa<Loc>(V)) 237 continue; 238 239 if (const MemRegion *R = V.getAsRegion()) { 240 // Invalidate the value of the variable passed by reference. 241 242 // Are we dealing with an ElementRegion? If the element type is 243 // a basic integer type (e.g., char, int) and the underlying region 244 // is a variable region then strip off the ElementRegion. 245 // FIXME: We really need to think about this for the general case 246 // as sometimes we are reasoning about arrays and other times 247 // about (char*), etc., is just a form of passing raw bytes. 248 // e.g., void *p = alloca(); foo((char*)p); 249 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 250 // Checking for 'integral type' is probably too promiscuous, but 251 // we'll leave it in for now until we have a systematic way of 252 // handling all of these cases. Eventually we need to come up 253 // with an interface to StoreManager so that this logic can be 254 // appropriately delegated to the respective StoreManagers while 255 // still allowing us to do checker-specific logic (e.g., 256 // invalidating reference counts), probably via callbacks. 257 if (ER->getElementType()->isIntegralOrEnumerationType()) { 258 const MemRegion *superReg = ER->getSuperRegion(); 259 if (isa<VarRegion>(superReg) || isa<FieldRegion>(superReg) || 260 isa<ObjCIvarRegion>(superReg)) 261 R = cast<TypedRegion>(superReg); 262 } 263 // FIXME: What about layers of ElementRegions? 264 } 265 266 // Mark this region for invalidation. We batch invalidate regions 267 // below for efficiency. 268 RegionsToInvalidate.push_back(R); 269 } else { 270 // Nuke all other arguments passed by reference. 271 // FIXME: is this necessary or correct? This handles the non-Region 272 // cases. Is it ever valid to store to these? 273 State = State->unbindLoc(cast<Loc>(V)); 274 } 275 } 276 277 // Invalidate designated regions using the batch invalidation API. 278 279 // FIXME: We can have collisions on the conjured symbol if the 280 // expression *I also creates conjured symbols. We probably want 281 // to identify conjured symbols by an expression pair: the enclosing 282 // expression (the context) and the expression itself. This should 283 // disambiguate conjured symbols. 284 unsigned Count = currentBuilderContext->getCurrentBlockCount(); 285 StoreManager::InvalidatedSymbols IS; 286 287 // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate 288 // global variables. 289 return State->invalidateRegions(RegionsToInvalidate, 290 Call.getOriginExpr(), Count, 291 &IS, &Call); 292 293} 294 295void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, 296 ExplodedNodeSet &dst) { 297 // Perform the previsit of the CallExpr. 298 ExplodedNodeSet dstPreVisit; 299 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 300 301 // Now evaluate the call itself. 302 class DefaultEval : public GraphExpander { 303 ExprEngine &Eng; 304 const CallExpr *CE; 305 public: 306 307 DefaultEval(ExprEngine &eng, const CallExpr *ce) 308 : Eng(eng), CE(ce) {} 309 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) { 310 // Should we inline the call? 311 if (Eng.getAnalysisManager().shouldInlineCall() && 312 Eng.InlineCall(Dst, CE, Pred)) { 313 return; 314 } 315 316 // First handle the return value. 317 StmtNodeBuilder Bldr(Pred, Dst, *Eng.currentBuilderContext); 318 319 // Get the callee. 320 const Expr *Callee = CE->getCallee()->IgnoreParens(); 321 const ProgramState *state = Pred->getState(); 322 SVal L = state->getSVal(Callee, Pred->getLocationContext()); 323 324 // Figure out the result type. We do this dance to handle references. 325 QualType ResultTy; 326 if (const FunctionDecl *FD = L.getAsFunctionDecl()) 327 ResultTy = FD->getResultType(); 328 else 329 ResultTy = CE->getType(); 330 331 if (CE->isLValue()) 332 ResultTy = Eng.getContext().getPointerType(ResultTy); 333 334 // Conjure a symbol value to use as the result. 335 SValBuilder &SVB = Eng.getSValBuilder(); 336 unsigned Count = Eng.currentBuilderContext->getCurrentBlockCount(); 337 SVal RetVal = SVB.getConjuredSymbolVal(0, CE, ResultTy, Count); 338 339 // Generate a new state with the return value set. 340 const LocationContext *LCtx = Pred->getLocationContext(); 341 state = state->BindExpr(CE, LCtx, RetVal); 342 343 // Invalidate the arguments. 344 state = Eng.invalidateArguments(state, CallOrObjCMessage(CE, state, LCtx), 345 LCtx); 346 347 // And make the result node. 348 Bldr.generateNode(CE, Pred, state); 349 } 350 }; 351 352 // Finally, evaluate the function call. We try each of the checkers 353 // to see if the can evaluate the function call. 354 ExplodedNodeSet dstCallEvaluated; 355 DefaultEval defEval(*this, CE); 356 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, 357 dstPreVisit, 358 CE, *this, &defEval); 359 360 // Finally, perform the post-condition check of the CallExpr and store 361 // the created nodes in 'Dst'. 362 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 363 *this); 364} 365 366void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 367 ExplodedNodeSet &Dst) { 368 369 ExplodedNodeSet dstPreVisit; 370 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this); 371 372 StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); 373 374 if (RS->getRetValue()) { 375 for (ExplodedNodeSet::iterator it = dstPreVisit.begin(), 376 ei = dstPreVisit.end(); it != ei; ++it) { 377 B.generateNode(RS, *it, (*it)->getState()); 378 } 379 } 380 else { 381 B.takeNodes(dstPreVisit); 382 } 383} 384