1 //===-- ExprEngine.h - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a meta-engine for path-sensitive dataflow analysis that
11 // is built on CoreEngine, but provides the boilerplate to execute transfer
12 // functions and build the ExplodedGraph at the expression level.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CLANG_GR_EXPRENGINE
17 #define LLVM_CLANG_GR_EXPRENGINE
19 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
24 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
25 #include "clang/AST/Expr.h"
26 #include "clang/AST/Type.h"
30 class AnalysisDeclContextManager;
32 class CXXConstructExpr;
35 class CXXTemporaryObjectExpr;
37 class MaterializeTemporaryExpr;
38 class ObjCAtSynchronizedStmt;
39 class ObjCForCollectionStmt;
43 class AnalysisManager;
44 class CallOrObjCMessage;
47 class ExprEngine : public SubEngine {
48 AnalysisManager &AMgr;
50 AnalysisDeclContextManager &AnalysisDeclContexts;
54 /// G - the simulation graph.
57 /// StateMgr - Object that manages the data for all created states.
58 ProgramStateManager StateMgr;
60 /// SymMgr - Object that manages the symbol information.
61 SymbolManager& SymMgr;
63 /// svalBuilder - SValBuilder object that creates SVals from expressions.
64 SValBuilder &svalBuilder;
66 /// EntryNode - The immediate predecessor node.
67 ExplodedNode *EntryNode;
69 /// CleanedState - The state for EntryNode "cleaned" of all dead
70 /// variables and symbols (as determined by a liveness analysis).
71 ProgramStateRef CleanedState;
73 /// currentStmt - The current block-level statement.
74 const Stmt *currentStmt;
75 unsigned int currentStmtIdx;
76 const NodeBuilderContext *currentBuilderContext;
78 /// Obj-C Class Identifiers.
79 IdentifierInfo* NSExceptionII;
82 Selector* NSExceptionInstanceRaiseSelectors;
85 /// Whether or not GC is enabled in this analysis.
88 /// The BugReporter associated with this engine. It is important that
89 /// this object be placed at the very end of member variables so that its
90 /// destructor is called before the rest of the ExprEngine is destroyed.
94 ExprEngine(AnalysisManager &mgr, bool gcEnabled,
95 SetOfConstDecls *VisitedCallees,
96 FunctionSummariesTy *FS);
100 /// Returns true if there is still simulation state on the worklist.
101 bool ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) {
102 return Engine.ExecuteWorkList(L, Steps, 0);
105 /// Execute the work list with an initial state. Nodes that reaches the exit
106 /// of the function are added into the Dst set, which represent the exit
107 /// state of the function call. Returns true if there is still simulation
108 /// state on the worklist.
109 bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
110 ProgramStateRef InitState,
111 ExplodedNodeSet &Dst) {
112 return Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst);
115 /// getContext - Return the ASTContext associated with this analysis.
116 ASTContext &getContext() const { return AMgr.getASTContext(); }
118 virtual AnalysisManager &getAnalysisManager() { return AMgr; }
120 CheckerManager &getCheckerManager() const {
121 return *AMgr.getCheckerManager();
124 SValBuilder &getSValBuilder() { return svalBuilder; }
126 BugReporter& getBugReporter() { return BR; }
128 const NodeBuilderContext &getBuilderContext() {
129 assert(currentBuilderContext);
130 return *currentBuilderContext;
133 bool isObjCGCEnabled() { return ObjCGCEnabled; }
135 const Stmt *getStmt() const;
137 void GenerateAutoTransition(ExplodedNode *N);
138 void enqueueEndOfPath(ExplodedNodeSet &S);
139 void GenerateCallExitNode(ExplodedNode *N);
141 /// ViewGraph - Visualize the ExplodedGraph created by executing the
143 void ViewGraph(bool trim = false);
145 void ViewGraph(ExplodedNode** Beg, ExplodedNode** End);
147 /// getInitialState - Return the initial state used for the root vertex
148 /// in the ExplodedGraph.
149 ProgramStateRef getInitialState(const LocationContext *InitLoc);
151 ExplodedGraph& getGraph() { return G; }
152 const ExplodedGraph& getGraph() const { return G; }
154 /// processCFGElement - Called by CoreEngine. Used to generate new successor
155 /// nodes by processing the 'effects' of a CFG element.
156 void processCFGElement(const CFGElement E, ExplodedNode *Pred,
157 unsigned StmtIdx, NodeBuilderContext *Ctx);
159 void ProcessStmt(const CFGStmt S, ExplodedNode *Pred);
161 void ProcessInitializer(const CFGInitializer I, ExplodedNode *Pred);
163 void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred);
165 void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
166 ExplodedNode *Pred, ExplodedNodeSet &Dst);
167 void ProcessBaseDtor(const CFGBaseDtor D,
168 ExplodedNode *Pred, ExplodedNodeSet &Dst);
169 void ProcessMemberDtor(const CFGMemberDtor D,
170 ExplodedNode *Pred, ExplodedNodeSet &Dst);
171 void ProcessTemporaryDtor(const CFGTemporaryDtor D,
172 ExplodedNode *Pred, ExplodedNodeSet &Dst);
174 /// Called by CoreEngine when processing the entrance of a CFGBlock.
175 virtual void processCFGBlockEntrance(const BlockEdge &L,
176 NodeBuilderWithSinks &nodeBuilder);
178 /// ProcessBranch - Called by CoreEngine. Used to generate successor
179 /// nodes by processing the 'effects' of a branch condition.
180 void processBranch(const Stmt *Condition, const Stmt *Term,
181 NodeBuilderContext& BuilderCtx,
183 ExplodedNodeSet &Dst,
184 const CFGBlock *DstT,
185 const CFGBlock *DstF);
187 /// processIndirectGoto - Called by CoreEngine. Used to generate successor
188 /// nodes by processing the 'effects' of a computed goto jump.
189 void processIndirectGoto(IndirectGotoNodeBuilder& builder);
191 /// ProcessSwitch - Called by CoreEngine. Used to generate successor
192 /// nodes by processing the 'effects' of a switch statement.
193 void processSwitch(SwitchNodeBuilder& builder);
195 /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
196 /// nodes when the control reaches the end of a function.
197 void processEndOfFunction(NodeBuilderContext& BC);
199 /// Generate the entry node of the callee.
200 void processCallEnter(CallEnter CE, ExplodedNode *Pred);
202 /// Generate the first post callsite node.
203 void processCallExit(ExplodedNode *Pred);
205 /// Called by CoreEngine when the analysis worklist has terminated.
206 void processEndWorklist(bool hasWorkRemaining);
208 /// evalAssume - Callback function invoked by the ConstraintManager when
209 /// making assumptions about state values.
210 ProgramStateRef processAssume(ProgramStateRef state, SVal cond,bool assumption);
212 /// wantsRegionChangeUpdate - Called by ProgramStateManager to determine if a
213 /// region change should trigger a processRegionChanges update.
214 bool wantsRegionChangeUpdate(ProgramStateRef state);
216 /// processRegionChanges - Called by ProgramStateManager whenever a change is made
217 /// to the store. Used to update checkers that track region values.
219 processRegionChanges(ProgramStateRef state,
220 const StoreManager::InvalidatedSymbols *invalidated,
221 ArrayRef<const MemRegion *> ExplicitRegions,
222 ArrayRef<const MemRegion *> Regions,
223 const CallOrObjCMessage *Call);
225 /// printState - Called by ProgramStateManager to print checker-specific data.
226 void printState(raw_ostream &Out, ProgramStateRef State,
227 const char *NL, const char *Sep);
229 virtual ProgramStateManager& getStateManager() { return StateMgr; }
231 StoreManager& getStoreManager() { return StateMgr.getStoreManager(); }
233 ConstraintManager& getConstraintManager() {
234 return StateMgr.getConstraintManager();
237 // FIXME: Remove when we migrate over to just using SValBuilder.
238 BasicValueFactory& getBasicVals() {
239 return StateMgr.getBasicVals();
241 const BasicValueFactory& getBasicVals() const {
242 return StateMgr.getBasicVals();
245 // FIXME: Remove when we migrate over to just using ValueManager.
246 SymbolManager& getSymbolManager() { return SymMgr; }
247 const SymbolManager& getSymbolManager() const { return SymMgr; }
249 // Functions for external checking of whether we have unfinished work
250 bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); }
251 bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); }
252 bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); }
254 const CoreEngine &getCoreEngine() const { return Engine; }
257 /// Visit - Transfer function logic for all statements. Dispatches to
258 /// other functions that handle specific kinds of statements.
259 void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst);
261 /// VisitArraySubscriptExpr - Transfer function for array accesses.
262 void VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *Ex,
264 ExplodedNodeSet &Dst);
266 /// VisitAsmStmt - Transfer function logic for inline asm.
267 void VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, ExplodedNodeSet &Dst);
269 /// VisitBlockExpr - Transfer function logic for BlockExprs.
270 void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
271 ExplodedNodeSet &Dst);
273 /// VisitBinaryOperator - Transfer function logic for binary operators.
274 void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred,
275 ExplodedNodeSet &Dst);
278 /// VisitCall - Transfer function for function calls.
279 void VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
280 ExplodedNodeSet &Dst);
282 /// VisitCast - Transfer function logic for all casts (implicit and explicit).
283 void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred,
284 ExplodedNodeSet &Dst);
286 /// VisitCompoundLiteralExpr - Transfer function logic for compound literals.
287 void VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
288 ExplodedNode *Pred, ExplodedNodeSet &Dst);
290 /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs.
291 void VisitCommonDeclRefExpr(const Expr *DR, const NamedDecl *D,
292 ExplodedNode *Pred, ExplodedNodeSet &Dst);
294 /// VisitDeclStmt - Transfer function logic for DeclStmts.
295 void VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
296 ExplodedNodeSet &Dst);
298 /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose
299 void VisitGuardedExpr(const Expr *Ex, const Expr *L, const Expr *R,
300 ExplodedNode *Pred, ExplodedNodeSet &Dst);
302 void VisitInitListExpr(const InitListExpr *E, ExplodedNode *Pred,
303 ExplodedNodeSet &Dst);
305 /// VisitLogicalExpr - Transfer function logic for '&&', '||'
306 void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
307 ExplodedNodeSet &Dst);
309 /// VisitMemberExpr - Transfer function for member expressions.
310 void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
311 ExplodedNodeSet &Dst);
313 /// Transfer function logic for ObjCAtSynchronizedStmts.
314 void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
315 ExplodedNode *Pred, ExplodedNodeSet &Dst);
317 /// Transfer function logic for computing the lvalue of an Objective-C ivar.
318 void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred,
319 ExplodedNodeSet &Dst);
321 /// VisitObjCForCollectionStmt - Transfer function logic for
322 /// ObjCForCollectionStmt.
323 void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
324 ExplodedNode *Pred, ExplodedNodeSet &Dst);
326 void VisitObjCMessage(const ObjCMessage &msg, ExplodedNode *Pred,
327 ExplodedNodeSet &Dst);
329 /// VisitReturnStmt - Transfer function logic for return statements.
330 void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred,
331 ExplodedNodeSet &Dst);
333 /// VisitOffsetOfExpr - Transfer function for offsetof.
334 void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred,
335 ExplodedNodeSet &Dst);
337 /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof.
338 void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
339 ExplodedNode *Pred, ExplodedNodeSet &Dst);
341 /// VisitUnaryOperator - Transfer function logic for unary operators.
342 void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred,
343 ExplodedNodeSet &Dst);
345 /// Handle ++ and -- (both pre- and post-increment).
346 void VisitIncrementDecrementOperator(const UnaryOperator* U,
348 ExplodedNodeSet &Dst);
350 void VisitCXXCatchStmt(const CXXCatchStmt *CS, ExplodedNode *Pred,
351 ExplodedNodeSet &Dst);
353 void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
354 ExplodedNodeSet & Dst);
356 void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *expr,
357 ExplodedNode *Pred, ExplodedNodeSet &Dst);
359 void VisitCXXConstructExpr(const CXXConstructExpr *E, const MemRegion *Dest,
360 ExplodedNode *Pred, ExplodedNodeSet &Dst);
362 void VisitCXXDestructor(const CXXDestructorDecl *DD,
363 const MemRegion *Dest, const Stmt *S,
364 ExplodedNode *Pred, ExplodedNodeSet &Dst);
366 void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
367 ExplodedNodeSet &Dst);
369 void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred,
370 ExplodedNodeSet &Dst);
372 /// Create a C++ temporary object for an rvalue.
373 void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
375 ExplodedNodeSet &Dst);
377 /// Synthesize CXXThisRegion.
378 const CXXThisRegion *getCXXThisRegion(const CXXRecordDecl *RD,
379 const StackFrameContext *SFC);
381 const CXXThisRegion *getCXXThisRegion(const CXXMethodDecl *decl,
382 const StackFrameContext *frameCtx);
384 /// evalEagerlyAssume - Given the nodes in 'Src', eagerly assume symbolic
385 /// expressions of the form 'x != 0' and generate new nodes (stored in Dst)
386 /// with those assumptions.
387 void evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
390 std::pair<const ProgramPointTag *, const ProgramPointTag*>
391 getEagerlyAssumeTags();
393 SVal evalMinus(SVal X) {
394 return X.isValid() ? svalBuilder.evalMinus(cast<NonLoc>(X)) : X;
397 SVal evalComplement(SVal X) {
398 return X.isValid() ? svalBuilder.evalComplement(cast<NonLoc>(X)) : X;
403 SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
404 NonLoc L, NonLoc R, QualType T) {
405 return svalBuilder.evalBinOpNN(state, op, L, R, T);
408 SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
409 NonLoc L, SVal R, QualType T) {
410 return R.isValid() ? svalBuilder.evalBinOpNN(state,op,L, cast<NonLoc>(R), T) : R;
413 SVal evalBinOp(ProgramStateRef ST, BinaryOperator::Opcode Op,
414 SVal LHS, SVal RHS, QualType T) {
415 return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T);
419 void evalObjCMessage(StmtNodeBuilder &Bldr, const ObjCMessage &msg,
420 ExplodedNode *Pred, ProgramStateRef state,
423 ProgramStateRef invalidateArguments(ProgramStateRef State,
424 const CallOrObjCMessage &Call,
425 const LocationContext *LC);
427 ProgramStateRef MarkBranch(ProgramStateRef state,
428 const Stmt *Terminator,
429 const LocationContext *LCtx,
432 /// evalBind - Handle the semantics of binding a value to a specific location.
433 /// This method is used by evalStore, VisitDeclStmt, and others.
434 void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred,
435 SVal location, SVal Val, bool atDeclInit = false);
438 // FIXME: 'tag' should be removed, and a LocationContext should be used
440 // FIXME: Comment on the meaning of the arguments, when 'St' may not
441 // be the same as Pred->state, and when 'location' may not be the
442 // same as state->getLValue(Ex).
443 /// Simulate a read of the result of Ex.
444 void evalLoad(ExplodedNodeSet &Dst,
445 const Expr *NodeEx, /* Eventually will be a CFGStmt */
446 const Expr *BoundExpr,
450 const ProgramPointTag *tag = 0,
451 QualType LoadTy = QualType());
453 // FIXME: 'tag' should be removed, and a LocationContext should be used
455 void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE,
456 ExplodedNode *Pred, ProgramStateRef St, SVal TargetLV, SVal Val,
457 const ProgramPointTag *tag = 0);
459 void evalLoadCommon(ExplodedNodeSet &Dst,
460 const Expr *NodeEx, /* Eventually will be a CFGStmt */
465 const ProgramPointTag *tag,
468 // FIXME: 'tag' should be removed, and a LocationContext should be used
470 void evalLocation(ExplodedNodeSet &Dst,
471 const Stmt *NodeEx, /* This will eventually be a CFGStmt */
474 ProgramStateRef St, SVal location,
475 const ProgramPointTag *tag, bool isLoad);
477 bool shouldInlineDecl(const FunctionDecl *FD, ExplodedNode *Pred);
478 bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred);
480 bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC);
483 /// Traits for storing the call processing policy inside GDM.
484 /// The GDM stores the corresponding CallExpr pointer.
485 struct ReplayWithoutInlining{};
487 struct ProgramStateTrait<ReplayWithoutInlining> :
488 public ProgramStatePartialTrait<void*> {
489 static void *GDMIndex() { static int index = 0; return &index; }
492 } // end ento namespace
494 } // end clang namespace