ExprEngineCallAndReturn.cpp revision 242384ddb0e0b65dd7e9e0ac0cf3c31cf98b06a6
12a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner//=-- ExprEngineCallAndReturn.cpp - Support for call/return -----*- C++ -*-===// 2ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 36fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// The LLVM Compiler Infrastructure 46fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7ea61c358720aa6c7a159d51658b34276316aa841Misha Brukman// 86fbcc26f1460eaee4e0eb8b426fc1ff0c7af11beJohn Criswell//===----------------------------------------------------------------------===// 92a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner// 102a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner// This file defines ExprEngine's support for calls and returns. 112a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner// 122a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner//===----------------------------------------------------------------------===// 132a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner 142a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner#include "clang/StaticAnalyzer/Core/CheckerManager.h" 152a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 162a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 172a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner#include "clang/AST/DeclCXX.h" 182a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner 192a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattnerusing namespace clang; 202a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattnerusing namespace ento; 212a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner 222a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattnernamespace { 232a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner // Trait class for recording returned expression in the state. 242a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner struct ReturnExpr { 25d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke static int TagInt; 26d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke typedef const Stmt *data_type; 272a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner }; 282a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner int ReturnExpr::TagInt; 29a6900c7ad9752a27e2e3b1bd78b2af3b1381176dDan Gohman} 30794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 31d27df628cc6fa29605fa221a2f0b03b4592caf03Dan Gohmanvoid ExprEngine::processCallEnter(CallEnterNodeBuilder &B) { 322a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner const ProgramState *state = 332a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner B.getState()->enterStackFrame(B.getCalleeContext()); 342a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner B.generateNode(state); 352a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner} 362a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner 37d27df628cc6fa29605fa221a2f0b03b4592caf03Dan Gohmanvoid ExprEngine::processCallExit(ExplodedNode *Pred) { 382a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner const ProgramState *state = Pred->getState(); 392a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner const StackFrameContext *calleeCtx = 40d27df628cc6fa29605fa221a2f0b03b4592caf03Dan Gohman Pred->getLocationContext()->getCurrentStackFrame(); 412a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner const Stmt *CE = calleeCtx->getCallSite(); 422a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner 43efb9b813fa74d3134dd185df10f6577ceab72bcdChris Lattner // If the callee returns an expression, bind its value to CallExpr. 44d27df628cc6fa29605fa221a2f0b03b4592caf03Dan Gohman const Stmt *ReturnedExpr = state->get<ReturnExpr>(); 45efb9b813fa74d3134dd185df10f6577ceab72bcdChris Lattner if (ReturnedExpr) { 462a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner const LocationContext *LCtx = Pred->getLocationContext(); 472a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner SVal RetVal = state->getSVal(ReturnedExpr, LCtx); 48d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke state = state->BindExpr(CE, LCtx, RetVal); 49d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke // Clear the return expr GDM. 502a4a095e5788be7967c0ac311efc269bc87e80b3Chris Lattner state = state->remove<ReturnExpr>(); 51 } 52 53 // Bind the constructed object value to CXXConstructExpr. 54 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) { 55 const CXXThisRegion *ThisR = 56 getCXXThisRegion(CCE->getConstructor()->getParent(), calleeCtx); 57 58 SVal ThisV = state->getSVal(ThisR); 59 // Always bind the region to the CXXConstructExpr. 60 state = state->BindExpr(CCE, Pred->getLocationContext(), ThisV); 61 } 62 63 64 PostStmt Loc(CE, calleeCtx->getParent()); 65 bool isNew; 66 ExplodedNode *N = G.getNode(Loc, state, false, &isNew); 67 N->addPredecessor(Pred, G); 68 if (!isNew) 69 return; 70 71 // Perform the post-condition check of the CallExpr. 72 ExplodedNodeSet Dst; 73 getCheckerManager().runCheckersForPostStmt(Dst, N, CE, *this); 74 75 // Enqueue the next element in the block. 76 for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end(); I != E; ++I) { 77 Engine.getWorkList()->enqueue(*I, 78 calleeCtx->getCallSiteBlock(), 79 calleeCtx->getIndex()+1); 80 } 81} 82 83static bool isPointerToConst(const ParmVarDecl *ParamDecl) { 84 QualType PointeeTy = ParamDecl->getOriginalType()->getPointeeType(); 85 if (PointeeTy != QualType() && PointeeTy.isConstQualified() && 86 !PointeeTy->isAnyPointerType() && !PointeeTy->isReferenceType()) { 87 return true; 88 } 89 return false; 90} 91 92// Try to retrieve the function declaration and find the function parameter 93// types which are pointers/references to a non-pointer const. 94// We do not invalidate the corresponding argument regions. 95static void findPtrToConstParams(llvm::SmallSet<unsigned, 1> &PreserveArgs, 96 const CallOrObjCMessage &Call) { 97 const Decl *CallDecl = Call.getDecl(); 98 if (!CallDecl) 99 return; 100 101 if (const FunctionDecl *FDecl = dyn_cast<FunctionDecl>(CallDecl)) { 102 for (unsigned Idx = 0, E = Call.getNumArgs(); Idx != E; ++Idx) { 103 if (FDecl && Idx < FDecl->getNumParams()) { 104 if (isPointerToConst(FDecl->getParamDecl(Idx))) 105 PreserveArgs.insert(Idx); 106 } 107 } 108 return; 109 } 110 111 if (const ObjCMethodDecl *MDecl = dyn_cast<ObjCMethodDecl>(CallDecl)) { 112 assert(MDecl->param_size() <= Call.getNumArgs()); 113 unsigned Idx = 0; 114 for (clang::ObjCMethodDecl::param_const_iterator 115 I = MDecl->param_begin(), E = MDecl->param_end(); I != E; ++I, ++Idx) { 116 if (isPointerToConst(*I)) 117 PreserveArgs.insert(Idx); 118 } 119 return; 120 } 121} 122 123const ProgramState * 124ExprEngine::invalidateArguments(const ProgramState *State, 125 const CallOrObjCMessage &Call, 126 const LocationContext *LC) { 127 SmallVector<const MemRegion *, 8> RegionsToInvalidate; 128 129 if (Call.isObjCMessage()) { 130 // Invalidate all instance variables of the receiver of an ObjC message. 131 // FIXME: We should be able to do better with inter-procedural analysis. 132 if (const MemRegion *MR = Call.getInstanceMessageReceiver(LC).getAsRegion()) 133 RegionsToInvalidate.push_back(MR); 134 135 } else if (Call.isCXXCall()) { 136 // Invalidate all instance variables for the callee of a C++ method call. 137 // FIXME: We should be able to do better with inter-procedural analysis. 138 // FIXME: We can probably do better for const versus non-const methods. 139 if (const MemRegion *Callee = Call.getCXXCallee().getAsRegion()) 140 RegionsToInvalidate.push_back(Callee); 141 142 } else if (Call.isFunctionCall()) { 143 // Block calls invalidate all captured-by-reference values. 144 SVal CalleeVal = Call.getFunctionCallee(); 145 if (const MemRegion *Callee = CalleeVal.getAsRegion()) { 146 if (isa<BlockDataRegion>(Callee)) 147 RegionsToInvalidate.push_back(Callee); 148 } 149 } 150 151 // Indexes of arguments whose values will be preserved by the call. 152 llvm::SmallSet<unsigned, 1> PreserveArgs; 153 findPtrToConstParams(PreserveArgs, Call); 154 155 for (unsigned idx = 0, e = Call.getNumArgs(); idx != e; ++idx) { 156 if (PreserveArgs.count(idx)) 157 continue; 158 159 SVal V = Call.getArgSVal(idx); 160 161 // If we are passing a location wrapped as an integer, unwrap it and 162 // invalidate the values referred by the location. 163 if (nonloc::LocAsInteger *Wrapped = dyn_cast<nonloc::LocAsInteger>(&V)) 164 V = Wrapped->getLoc(); 165 else if (!isa<Loc>(V)) 166 continue; 167 168 if (const MemRegion *R = V.getAsRegion()) { 169 // Invalidate the value of the variable passed by reference. 170 171 // Are we dealing with an ElementRegion? If the element type is 172 // a basic integer type (e.g., char, int) and the underlying region 173 // is a variable region then strip off the ElementRegion. 174 // FIXME: We really need to think about this for the general case 175 // as sometimes we are reasoning about arrays and other times 176 // about (char*), etc., is just a form of passing raw bytes. 177 // e.g., void *p = alloca(); foo((char*)p); 178 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) { 179 // Checking for 'integral type' is probably too promiscuous, but 180 // we'll leave it in for now until we have a systematic way of 181 // handling all of these cases. Eventually we need to come up 182 // with an interface to StoreManager so that this logic can be 183 // appropriately delegated to the respective StoreManagers while 184 // still allowing us to do checker-specific logic (e.g., 185 // invalidating reference counts), probably via callbacks. 186 if (ER->getElementType()->isIntegralOrEnumerationType()) { 187 const MemRegion *superReg = ER->getSuperRegion(); 188 if (isa<VarRegion>(superReg) || isa<FieldRegion>(superReg) || 189 isa<ObjCIvarRegion>(superReg)) 190 R = cast<TypedRegion>(superReg); 191 } 192 // FIXME: What about layers of ElementRegions? 193 } 194 195 // Mark this region for invalidation. We batch invalidate regions 196 // below for efficiency. 197 RegionsToInvalidate.push_back(R); 198 } else { 199 // Nuke all other arguments passed by reference. 200 // FIXME: is this necessary or correct? This handles the non-Region 201 // cases. Is it ever valid to store to these? 202 State = State->unbindLoc(cast<Loc>(V)); 203 } 204 } 205 206 // Invalidate designated regions using the batch invalidation API. 207 208 // FIXME: We can have collisions on the conjured symbol if the 209 // expression *I also creates conjured symbols. We probably want 210 // to identify conjured symbols by an expression pair: the enclosing 211 // expression (the context) and the expression itself. This should 212 // disambiguate conjured symbols. 213 unsigned Count = currentBuilderContext->getCurrentBlockCount(); 214 StoreManager::InvalidatedSymbols IS; 215 216 // NOTE: Even if RegionsToInvalidate is empty, we may still invalidate 217 // global variables. 218 return State->invalidateRegions(RegionsToInvalidate, 219 Call.getOriginExpr(), Count, 220 &IS, &Call); 221 222} 223 224void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, 225 ExplodedNodeSet &dst) { 226 // Perform the previsit of the CallExpr. 227 ExplodedNodeSet dstPreVisit; 228 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 229 230 // Now evaluate the call itself. 231 class DefaultEval : public GraphExpander { 232 ExprEngine &Eng; 233 const CallExpr *CE; 234 public: 235 236 DefaultEval(ExprEngine &eng, const CallExpr *ce) 237 : Eng(eng), CE(ce) {} 238 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) { 239 // Should we inline the call? 240 if (Eng.getAnalysisManager().shouldInlineCall() && 241 Eng.InlineCall(Dst, CE, Pred)) { 242 return; 243 } 244 245 // First handle the return value. 246 StmtNodeBuilder Bldr(Pred, Dst, *Eng.currentBuilderContext); 247 248 // Get the callee. 249 const Expr *Callee = CE->getCallee()->IgnoreParens(); 250 const ProgramState *state = Pred->getState(); 251 SVal L = state->getSVal(Callee, Pred->getLocationContext()); 252 253 // Figure out the result type. We do this dance to handle references. 254 QualType ResultTy; 255 if (const FunctionDecl *FD = L.getAsFunctionDecl()) 256 ResultTy = FD->getResultType(); 257 else 258 ResultTy = CE->getType(); 259 260 if (CE->isLValue()) 261 ResultTy = Eng.getContext().getPointerType(ResultTy); 262 263 // Conjure a symbol value to use as the result. 264 SValBuilder &SVB = Eng.getSValBuilder(); 265 unsigned Count = Eng.currentBuilderContext->getCurrentBlockCount(); 266 SVal RetVal = SVB.getConjuredSymbolVal(0, CE, ResultTy, Count); 267 268 // Generate a new state with the return value set. 269 const LocationContext *LCtx = Pred->getLocationContext(); 270 state = state->BindExpr(CE, LCtx, RetVal); 271 272 // Invalidate the arguments. 273 state = Eng.invalidateArguments(state, CallOrObjCMessage(CE, state, LCtx), 274 LCtx); 275 276 // And make the result node. 277 Bldr.generateNode(CE, Pred, state); 278 } 279 }; 280 281 // Finally, evaluate the function call. We try each of the checkers 282 // to see if the can evaluate the function call. 283 ExplodedNodeSet dstCallEvaluated; 284 DefaultEval defEval(*this, CE); 285 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, 286 dstPreVisit, 287 CE, *this, &defEval); 288 289 // Finally, perform the post-condition check of the CallExpr and store 290 // the created nodes in 'Dst'. 291 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 292 *this); 293} 294 295void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 296 ExplodedNodeSet &Dst) { 297 ExplodedNodeSet Src; 298 { 299 StmtNodeBuilder Bldr(Pred, Src, *currentBuilderContext); 300 if (const Expr *RetE = RS->getRetValue()) { 301 // Record the returned expression in the state. It will be used in 302 // processCallExit to bind the return value to the call expr. 303 { 304 static SimpleProgramPointTag tag("ExprEngine: ReturnStmt"); 305 const ProgramState *state = Pred->getState(); 306 state = state->set<ReturnExpr>(RetE); 307 Pred = Bldr.generateNode(RetE, Pred, state, false, &tag); 308 } 309 // We may get a NULL Pred because we generated a cached node. 310 if (Pred) { 311 Bldr.takeNodes(Pred); 312 ExplodedNodeSet Tmp; 313 Visit(RetE, Pred, Tmp); 314 Bldr.addNodes(Tmp); 315 } 316 } 317 } 318 319 getCheckerManager().runCheckersForPreStmt(Dst, Src, RS, *this); 320} 321