ExprEngineCallAndReturn.cpp revision 740d490593e0de8732a697c9f77b90ddd463863b
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/Calls.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 107 // The parent context might not be a stack frame, so make sure we 108 // look up the first enclosing stack frame. 109 const StackFrameContext *callerCtx = 110 calleeCtx->getParent()->getCurrentStackFrame(); 111 112 const Stmt *CE = calleeCtx->getCallSite(); 113 ProgramStateRef state = CEBNode->getState(); 114 // Find the last statement in the function and the corresponding basic block. 115 const Stmt *LastSt = 0; 116 const CFGBlock *Blk = 0; 117 llvm::tie(LastSt, Blk) = getLastStmt(CEBNode); 118 119 // Step 2: generate node with binded return value: CEBNode -> BindedRetNode. 120 121 // If the callee returns an expression, bind its value to CallExpr. 122 if (const ReturnStmt *RS = dyn_cast_or_null<ReturnStmt>(LastSt)) { 123 const LocationContext *LCtx = CEBNode->getLocationContext(); 124 SVal V = state->getSVal(RS, LCtx); 125 state = state->BindExpr(CE, callerCtx, V); 126 } 127 128 // Bind the constructed object value to CXXConstructExpr. 129 if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(CE)) { 130 loc::MemRegionVal This = 131 svalBuilder.getCXXThis(CCE->getConstructor()->getParent(), calleeCtx); 132 SVal ThisV = state->getSVal(This); 133 134 // Always bind the region to the CXXConstructExpr. 135 state = state->BindExpr(CCE, CEBNode->getLocationContext(), ThisV); 136 } 137 138 static SimpleProgramPointTag retValBindTag("ExprEngine : Bind Return Value"); 139 PostStmt Loc(LastSt, calleeCtx, &retValBindTag); 140 bool isNew; 141 ExplodedNode *BindedRetNode = G.getNode(Loc, state, false, &isNew); 142 BindedRetNode->addPredecessor(CEBNode, G); 143 if (!isNew) 144 return; 145 146 // Step 3: BindedRetNode -> CleanedNodes 147 // If we can find a statement and a block in the inlined function, run remove 148 // dead bindings before returning from the call. This is important to ensure 149 // that we report the issues such as leaks in the stack contexts in which 150 // they occurred. 151 ExplodedNodeSet CleanedNodes; 152 if (LastSt && Blk) { 153 NodeBuilderContext Ctx(getCoreEngine(), Blk, BindedRetNode); 154 currentBuilderContext = &Ctx; 155 // Here, we call the Symbol Reaper with 0 statement and caller location 156 // context, telling it to clean up everything in the callee's context 157 // (and it's children). We use LastStmt as a diagnostic statement, which 158 // which the PreStmtPurge Dead point will be associated. 159 removeDead(BindedRetNode, CleanedNodes, 0, callerCtx, LastSt, 160 ProgramPoint::PostStmtPurgeDeadSymbolsKind); 161 currentBuilderContext = 0; 162 } else { 163 CleanedNodes.Add(CEBNode); 164 } 165 166 for (ExplodedNodeSet::iterator I = CleanedNodes.begin(), 167 E = CleanedNodes.end(); I != E; ++I) { 168 169 // Step 4: Generate the CallExit and leave the callee's context. 170 // CleanedNodes -> CEENode 171 CallExitEnd Loc(CE, callerCtx); 172 bool isNew; 173 ExplodedNode *CEENode = G.getNode(Loc, (*I)->getState(), false, &isNew); 174 CEENode->addPredecessor(*I, G); 175 if (!isNew) 176 return; 177 178 // Step 5: Perform the post-condition check of the CallExpr and enqueue the 179 // result onto the work list. 180 // CEENode -> Dst -> WorkList 181 ExplodedNodeSet Dst; 182 NodeBuilderContext Ctx(Engine, calleeCtx->getCallSiteBlock(), CEENode); 183 SaveAndRestore<const NodeBuilderContext*> NBCSave(currentBuilderContext, 184 &Ctx); 185 SaveAndRestore<unsigned> CBISave(currentStmtIdx, calleeCtx->getIndex()); 186 187 getCheckerManager().runCheckersForPostStmt(Dst, CEENode, CE, *this, true); 188 189 // Enqueue the next element in the block. 190 for (ExplodedNodeSet::iterator PSI = Dst.begin(), PSE = Dst.end(); 191 PSI != PSE; ++PSI) { 192 Engine.getWorkList()->enqueue(*PSI, calleeCtx->getCallSiteBlock(), 193 calleeCtx->getIndex()+1); 194 } 195 } 196} 197 198static unsigned getNumberStackFrames(const LocationContext *LCtx) { 199 unsigned count = 0; 200 while (LCtx) { 201 if (isa<StackFrameContext>(LCtx)) 202 ++count; 203 LCtx = LCtx->getParent(); 204 } 205 return count; 206} 207 208// Determine if we should inline the call. 209bool ExprEngine::shouldInlineDecl(const Decl *D, ExplodedNode *Pred) { 210 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D); 211 const CFG *CalleeCFG = CalleeADC->getCFG(); 212 213 // It is possible that the CFG cannot be constructed. 214 // Be safe, and check if the CalleeCFG is valid. 215 if (!CalleeCFG) 216 return false; 217 218 if (getNumberStackFrames(Pred->getLocationContext()) 219 == AMgr.InlineMaxStackDepth) 220 return false; 221 222 if (Engine.FunctionSummaries->hasReachedMaxBlockCount(D)) 223 return false; 224 225 if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize) 226 return false; 227 228 // Do not inline variadic calls (for now). 229 if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { 230 if (BD->isVariadic()) 231 return false; 232 } 233 else if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 234 if (FD->isVariadic()) 235 return false; 236 } 237 238 return true; 239} 240 241bool ExprEngine::InlineCall(ExplodedNodeSet &Dst, 242 const CallExpr *CE, 243 ExplodedNode *Pred) { 244 if (!getAnalysisManager().shouldInlineCall()) 245 return false; 246 247 // if (!shouldInlineCallExpr(CE, this)) 248 // return false; 249 250 const StackFrameContext *CallerSFC = 251 Pred->getLocationContext()->getCurrentStackFrame(); 252 253 ProgramStateRef state = Pred->getState(); 254 const Expr *Callee = CE->getCallee(); 255 SVal CalleeVal = state->getSVal(Callee, Pred->getLocationContext()); 256 const Decl *D = 0; 257 const LocationContext *ParentOfCallee = 0; 258 259 if (const FunctionDecl *FD = CalleeVal.getAsFunctionDecl()) { 260 if (!FD->hasBody(FD)) 261 return false; 262 263 switch (CE->getStmtClass()) { 264 default: 265 break; 266 case Stmt::CXXMemberCallExprClass: 267 case Stmt::CallExprClass: { 268 D = FD; 269 break; 270 271 } 272 } 273 } else if (const BlockDataRegion *BR = 274 dyn_cast_or_null<BlockDataRegion>(CalleeVal.getAsRegion())) { 275 assert(CE->getStmtClass() == Stmt::CallExprClass); 276 const BlockDecl *BD = BR->getDecl(); 277 D = BD; 278 AnalysisDeclContext *BlockCtx = AMgr.getAnalysisDeclContext(BD); 279 ParentOfCallee = BlockCtx->getBlockInvocationContext(CallerSFC, 280 BD, 281 BR); 282 } else { 283 // This is case we don't handle yet. 284 return false; 285 } 286 287 if (!D || !shouldInlineDecl(D, Pred)) 288 return false; 289 290 if (!ParentOfCallee) 291 ParentOfCallee = CallerSFC; 292 293 // Construct a new stack frame for the callee. 294 AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D); 295 const StackFrameContext *CalleeSFC = 296 CalleeADC->getStackFrame(ParentOfCallee, CE, 297 currentBuilderContext->getBlock(), 298 currentStmtIdx); 299 300 CallEnter Loc(CE, CalleeSFC, Pred->getLocationContext()); 301 bool isNew; 302 if (ExplodedNode *N = G.getNode(Loc, state, false, &isNew)) { 303 N->addPredecessor(Pred, G); 304 if (isNew) 305 Engine.getWorkList()->enqueue(N); 306 } 307 return true; 308} 309 310static ProgramStateRef getReplayWithoutInliningState(ExplodedNode *&N, 311 const CallExpr *CE) { 312 void *ReplayState = N->getState()->get<ReplayWithoutInlining>(); 313 if (!ReplayState) 314 return 0; 315 const CallExpr *ReplayCE = reinterpret_cast<const CallExpr*>(ReplayState); 316 if (CE == ReplayCE) { 317 return N->getState()->remove<ReplayWithoutInlining>(); 318 } 319 return 0; 320} 321 322void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred, 323 ExplodedNodeSet &dst) { 324 // Perform the previsit of the CallExpr. 325 ExplodedNodeSet dstPreVisit; 326 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, CE, *this); 327 328 // Now evaluate the call itself. 329 class DefaultEval : public GraphExpander { 330 ExprEngine &Eng; 331 const CallExpr *CE; 332 public: 333 334 DefaultEval(ExprEngine &eng, const CallExpr *ce) 335 : Eng(eng), CE(ce) {} 336 virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) { 337 338 ProgramStateRef state = getReplayWithoutInliningState(Pred, CE); 339 340 // First, try to inline the call. 341 if (state == 0 && Eng.InlineCall(Dst, CE, Pred)) 342 return; 343 344 // First handle the return value. 345 StmtNodeBuilder Bldr(Pred, Dst, *Eng.currentBuilderContext); 346 347 // Get the callee. 348 const Expr *Callee = CE->getCallee()->IgnoreParens(); 349 if (state == 0) 350 state = Pred->getState(); 351 SVal L = state->getSVal(Callee, Pred->getLocationContext()); 352 353 // Figure out the result type. We do this dance to handle references. 354 // FIXME: This doesn't handle C++ methods, blocks, etc. 355 QualType ResultTy; 356 if (const FunctionDecl *FD = L.getAsFunctionDecl()) 357 ResultTy = FD->getResultType(); 358 else 359 ResultTy = CE->getType(); 360 361 if (CE->isGLValue()) 362 ResultTy = Eng.getContext().getPointerType(ResultTy); 363 364 // Conjure a symbol value to use as the result. 365 SValBuilder &SVB = Eng.getSValBuilder(); 366 unsigned Count = Eng.currentBuilderContext->getCurrentBlockCount(); 367 const LocationContext *LCtx = Pred->getLocationContext(); 368 SVal RetVal = SVB.getConjuredSymbolVal(0, CE, LCtx, ResultTy, Count); 369 370 // Generate a new state with the return value set. 371 state = state->BindExpr(CE, LCtx, RetVal); 372 373 // Invalidate the arguments. 374 if (const CXXMemberCallExpr *MemberCE = dyn_cast<CXXMemberCallExpr>(CE)) { 375 CXXMemberCall Call(MemberCE, state, LCtx); 376 state = Call.invalidateRegions(Count); 377 } else if (isa<BlockDataRegion>(L.getAsRegion())) { 378 BlockCall Call(CE, state, LCtx); 379 state = Call.invalidateRegions(Count); 380 } else { 381 FunctionCall Call(CE, state, LCtx); 382 state = Call.invalidateRegions(Count); 383 } 384 385 // And make the result node. 386 Bldr.generateNode(CE, Pred, state); 387 } 388 }; 389 390 // Finally, evaluate the function call. We try each of the checkers 391 // to see if the can evaluate the function call. 392 ExplodedNodeSet dstCallEvaluated; 393 DefaultEval defEval(*this, CE); 394 getCheckerManager().runCheckersForEvalCall(dstCallEvaluated, 395 dstPreVisit, 396 CE, *this, &defEval); 397 398 // Finally, perform the post-condition check of the CallExpr and store 399 // the created nodes in 'Dst'. 400 getCheckerManager().runCheckersForPostStmt(dst, dstCallEvaluated, CE, 401 *this); 402} 403 404void ExprEngine::VisitReturnStmt(const ReturnStmt *RS, ExplodedNode *Pred, 405 ExplodedNodeSet &Dst) { 406 407 ExplodedNodeSet dstPreVisit; 408 getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, RS, *this); 409 410 StmtNodeBuilder B(dstPreVisit, Dst, *currentBuilderContext); 411 412 if (RS->getRetValue()) { 413 for (ExplodedNodeSet::iterator it = dstPreVisit.begin(), 414 ei = dstPreVisit.end(); it != ei; ++it) { 415 B.generateNode(RS, *it, (*it)->getState()); 416 } 417 } 418} 419