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