1 //==- GRCoreEngine.h - Path-Sensitive Dataflow Engine --------------*- 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 generic engine for intraprocedural, path-sensitive,
11 // dataflow analysis via graph reachability.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_ANALYSIS_GRENGINE
16 #define LLVM_CLANG_ANALYSIS_GRENGINE
18 #include "clang/AST/Expr.h"
19 #include "clang/GR/PathSensitive/ExplodedGraph.h"
20 #include "clang/GR/PathSensitive/GRWorkList.h"
21 #include "clang/GR/PathSensitive/GRBlockCounter.h"
22 #include "clang/GR/PathSensitive/GRSubEngine.h"
23 #include "llvm/ADT/OwningPtr.h"
27 //===----------------------------------------------------------------------===//
28 /// GRCoreEngine - Implements the core logic of the graph-reachability
29 /// analysis. It traverses the CFG and generates the ExplodedGraph.
30 /// Program "states" are treated as opaque void pointers.
31 /// The template class GRCoreEngine (which subclasses GRCoreEngine)
32 /// provides the matching component to the engine that knows the actual types
33 /// for states. Note that this engine only dispatches to transfer functions
34 /// at the statement and block-level. The analyses themselves must implement
35 /// any transfer function logic and the sub-expression level (if any).
37 friend class GRStmtNodeBuilder
;
38 friend class GRBranchNodeBuilder
;
39 friend class GRIndirectGotoNodeBuilder
;
40 friend class GRSwitchNodeBuilder
;
41 friend class GREndPathNodeBuilder
;
42 friend class GRCallEnterNodeBuilder
;
43 friend class GRCallExitNodeBuilder
;
46 typedef std::vector
<std::pair
<BlockEdge
, const ExplodedNode
*> >
50 GRSubEngine
& SubEngine
;
52 /// G - The simulation graph. Each node is a (location,state) pair.
53 llvm::OwningPtr
<ExplodedGraph
> G
;
55 /// WList - A set of queued nodes that need to be processed by the
56 /// worklist algorithm. It is up to the implementation of WList to decide
57 /// the order that nodes are processed.
60 /// BCounterFactory - A factory object for created GRBlockCounter objects.
61 /// These are used to record for key nodes in the ExplodedGraph the
62 /// number of times different CFGBlocks have been visited along a path.
63 GRBlockCounter::Factory BCounterFactory
;
65 /// The locations where we stopped doing work because we visited a location
67 BlocksAborted blocksAborted
;
69 void generateNode(const ProgramPoint
& Loc
, const GRState
* State
,
72 void HandleBlockEdge(const BlockEdge
& E
, ExplodedNode
* Pred
);
73 void HandleBlockEntrance(const BlockEntrance
& E
, ExplodedNode
* Pred
);
74 void HandleBlockExit(const CFGBlock
* B
, ExplodedNode
* Pred
);
75 void HandlePostStmt(const CFGBlock
* B
, unsigned StmtIdx
, ExplodedNode
*Pred
);
77 void HandleBranch(const Stmt
* Cond
, const Stmt
* Term
, const CFGBlock
* B
,
79 void HandleCallEnter(const CallEnter
&L
, const CFGBlock
*Block
,
80 unsigned Index
, ExplodedNode
*Pred
);
81 void HandleCallExit(const CallExit
&L
, ExplodedNode
*Pred
);
83 /// Get the initial state from the subengine.
84 const GRState
* getInitialState(const LocationContext
*InitLoc
) {
85 return SubEngine
.getInitialState(InitLoc
);
88 void ProcessEndPath(GREndPathNodeBuilder
& Builder
) {
89 SubEngine
.ProcessEndPath(Builder
);
92 void ProcessElement(const CFGElement E
, GRStmtNodeBuilder
& Builder
) {
93 SubEngine
.ProcessElement(E
, Builder
);
96 bool ProcessBlockEntrance(const CFGBlock
* Blk
, const ExplodedNode
*Pred
,
98 return SubEngine
.ProcessBlockEntrance(Blk
, Pred
, BC
);
102 void ProcessBranch(const Stmt
* Condition
, const Stmt
* Terminator
,
103 GRBranchNodeBuilder
& Builder
) {
104 SubEngine
.ProcessBranch(Condition
, Terminator
, Builder
);
108 void ProcessIndirectGoto(GRIndirectGotoNodeBuilder
& Builder
) {
109 SubEngine
.ProcessIndirectGoto(Builder
);
113 void ProcessSwitch(GRSwitchNodeBuilder
& Builder
) {
114 SubEngine
.ProcessSwitch(Builder
);
117 void ProcessCallEnter(GRCallEnterNodeBuilder
&Builder
) {
118 SubEngine
.ProcessCallEnter(Builder
);
121 void ProcessCallExit(GRCallExitNodeBuilder
&Builder
) {
122 SubEngine
.ProcessCallExit(Builder
);
126 GRCoreEngine(const GRCoreEngine
&); // Do not implement.
127 GRCoreEngine
& operator=(const GRCoreEngine
&);
130 /// Construct a GRCoreEngine object to analyze the provided CFG using
131 /// a DFS exploration of the exploded graph.
132 GRCoreEngine(GRSubEngine
& subengine
)
133 : SubEngine(subengine
), G(new ExplodedGraph()),
134 WList(GRWorkList::MakeBFS()),
135 BCounterFactory(G
->getAllocator()) {}
137 /// Construct a GRCoreEngine object to analyze the provided CFG and to
138 /// use the provided worklist object to execute the worklist algorithm.
139 /// The GRCoreEngine object assumes ownership of 'wlist'.
140 GRCoreEngine(GRWorkList
* wlist
, GRSubEngine
& subengine
)
141 : SubEngine(subengine
), G(new ExplodedGraph()), WList(wlist
),
142 BCounterFactory(G
->getAllocator()) {}
148 /// getGraph - Returns the exploded graph.
149 ExplodedGraph
& getGraph() { return *G
.get(); }
151 /// takeGraph - Returns the exploded graph. Ownership of the graph is
152 /// transfered to the caller.
153 ExplodedGraph
* takeGraph() { return G
.take(); }
155 /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
156 /// steps. Returns true if there is still simulation state on the worklist.
157 bool ExecuteWorkList(const LocationContext
*L
, unsigned Steps
,
158 const GRState
*InitState
);
159 void ExecuteWorkListWithInitialState(const LocationContext
*L
, unsigned Steps
,
160 const GRState
*InitState
,
161 ExplodedNodeSet
&Dst
);
163 // Functions for external checking of whether we have unfinished work
164 bool wasBlockAborted() const { return !blocksAborted
.empty(); }
165 bool hasWorkRemaining() const { return wasBlockAborted() || WList
->hasWork(); }
167 GRWorkList
*getWorkList() const { return WList
; }
169 BlocksAborted::const_iterator
blocks_aborted_begin() const {
170 return blocksAborted
.begin();
172 BlocksAborted::const_iterator
blocks_aborted_end() const {
173 return blocksAborted
.end();
177 class GRStmtNodeBuilder
{
185 bool PurgingDeadSymbols
;
187 bool HasGeneratedNode
;
188 ProgramPoint::Kind PointKind
;
191 const GRState
* CleanedState
;
194 typedef llvm::SmallPtrSet
<ExplodedNode
*,5> DeferredTy
;
197 void GenerateAutoTransition(ExplodedNode
* N
);
200 GRStmtNodeBuilder(const CFGBlock
* b
, unsigned idx
, ExplodedNode
* N
,
201 GRCoreEngine
* e
, GRStateManager
&mgr
);
203 ~GRStmtNodeBuilder();
205 ExplodedNode
* getBasePredecessor() const { return Pred
; }
207 // FIXME: This should not be exposed.
208 GRWorkList
*getWorkList() { return Eng
.WList
; }
210 void SetCleanedState(const GRState
* St
) {
214 GRBlockCounter
getBlockCounter() const { return Eng
.WList
->getBlockCounter();}
216 unsigned getCurrentBlockCount() const {
217 return getBlockCounter().getNumVisited(
218 Pred
->getLocationContext()->getCurrentStackFrame(),
222 ExplodedNode
* generateNode(PostStmt PP
,const GRState
* St
,ExplodedNode
* Pred
) {
223 HasGeneratedNode
= true;
224 return generateNodeInternal(PP
, St
, Pred
);
227 ExplodedNode
* generateNode(const Stmt
*S
, const GRState
*St
,
228 ExplodedNode
*Pred
, ProgramPoint::Kind K
) {
229 HasGeneratedNode
= true;
231 if (PurgingDeadSymbols
)
232 K
= ProgramPoint::PostPurgeDeadSymbolsKind
;
234 return generateNodeInternal(S
, St
, Pred
, K
, Tag
);
237 ExplodedNode
* generateNode(const Stmt
*S
, const GRState
*St
,
238 ExplodedNode
*Pred
) {
239 return generateNode(S
, St
, Pred
, PointKind
);
242 ExplodedNode
*generateNode(const ProgramPoint
&PP
, const GRState
* State
,
243 ExplodedNode
* Pred
) {
244 HasGeneratedNode
= true;
245 return generateNodeInternal(PP
, State
, Pred
);
249 generateNodeInternal(const ProgramPoint
&PP
, const GRState
* State
,
253 generateNodeInternal(const Stmt
* S
, const GRState
* State
, ExplodedNode
* Pred
,
254 ProgramPoint::Kind K
= ProgramPoint::PostStmtKind
,
255 const void *tag
= 0);
257 /// getStmt - Return the current block-level expression associated with
259 const Stmt
* getStmt() const {
260 CFGStmt CS
= B
[Idx
].getAs
<CFGStmt
>();
267 /// getBlock - Return the CFGBlock associated with the block-level expression
269 const CFGBlock
* getBlock() const { return &B
; }
271 unsigned getIndex() const { return Idx
; }
273 const GRState
* GetState(ExplodedNode
* Pred
) const {
274 if (Pred
== getBasePredecessor())
277 return Pred
->getState();
280 ExplodedNode
* MakeNode(ExplodedNodeSet
& Dst
, const Stmt
* S
,
281 ExplodedNode
* Pred
, const GRState
* St
) {
282 return MakeNode(Dst
, S
, Pred
, St
, PointKind
);
285 ExplodedNode
* MakeNode(ExplodedNodeSet
& Dst
, const Stmt
* S
,ExplodedNode
* Pred
,
286 const GRState
* St
, ProgramPoint::Kind K
);
288 ExplodedNode
* MakeSinkNode(ExplodedNodeSet
& Dst
, const Stmt
* S
,
289 ExplodedNode
* Pred
, const GRState
* St
) {
290 bool Tmp
= BuildSinks
;
292 ExplodedNode
* N
= MakeNode(Dst
, S
, Pred
, St
);
298 class GRBranchNodeBuilder
{
301 const CFGBlock
* DstT
;
302 const CFGBlock
* DstF
;
305 typedef llvm::SmallVector
<ExplodedNode
*,3> DeferredTy
;
311 bool InFeasibleFalse
;
314 GRBranchNodeBuilder(const CFGBlock
* src
, const CFGBlock
* dstT
,
315 const CFGBlock
* dstF
, ExplodedNode
* pred
, GRCoreEngine
* e
)
316 : Eng(*e
), Src(src
), DstT(dstT
), DstF(dstF
), Pred(pred
),
317 GeneratedTrue(false), GeneratedFalse(false),
318 InFeasibleTrue(!DstT
), InFeasibleFalse(!DstF
) {}
320 ~GRBranchNodeBuilder();
322 ExplodedNode
* getPredecessor() const { return Pred
; }
324 const ExplodedGraph
& getGraph() const { return *Eng
.G
; }
326 GRBlockCounter
getBlockCounter() const { return Eng
.WList
->getBlockCounter();}
328 ExplodedNode
* generateNode(const GRState
* State
, bool branch
);
330 const CFGBlock
* getTargetBlock(bool branch
) const {
331 return branch
? DstT
: DstF
;
334 void markInfeasible(bool branch
) {
336 InFeasibleTrue
= GeneratedTrue
= true;
338 InFeasibleFalse
= GeneratedFalse
= true;
341 bool isFeasible(bool branch
) {
342 return branch
? !InFeasibleTrue
: !InFeasibleFalse
;
345 const GRState
* getState() const {
346 return getPredecessor()->getState();
350 class GRIndirectGotoNodeBuilder
{
353 const CFGBlock
& DispatchBlock
;
358 GRIndirectGotoNodeBuilder(ExplodedNode
* pred
, const CFGBlock
* src
,
359 const Expr
* e
, const CFGBlock
* dispatch
, GRCoreEngine
* eng
)
360 : Eng(*eng
), Src(src
), DispatchBlock(*dispatch
), E(e
), Pred(pred
) {}
363 CFGBlock::const_succ_iterator I
;
365 friend class GRIndirectGotoNodeBuilder
;
366 iterator(CFGBlock::const_succ_iterator i
) : I(i
) {}
369 iterator
& operator++() { ++I
; return *this; }
370 bool operator!=(const iterator
& X
) const { return I
!= X
.I
; }
372 const LabelStmt
* getLabel() const {
373 return llvm::cast
<LabelStmt
>((*I
)->getLabel());
376 const CFGBlock
* getBlock() const {
381 iterator
begin() { return iterator(DispatchBlock
.succ_begin()); }
382 iterator
end() { return iterator(DispatchBlock
.succ_end()); }
384 ExplodedNode
* generateNode(const iterator
& I
, const GRState
* State
,
385 bool isSink
= false);
387 const Expr
* getTarget() const { return E
; }
389 const GRState
* getState() const { return Pred
->State
; }
392 class GRSwitchNodeBuilder
{
395 const Expr
* Condition
;
399 GRSwitchNodeBuilder(ExplodedNode
* pred
, const CFGBlock
* src
,
400 const Expr
* condition
, GRCoreEngine
* eng
)
401 : Eng(*eng
), Src(src
), Condition(condition
), Pred(pred
) {}
404 CFGBlock::const_succ_reverse_iterator I
;
406 friend class GRSwitchNodeBuilder
;
407 iterator(CFGBlock::const_succ_reverse_iterator i
) : I(i
) {}
410 iterator
& operator++() { ++I
; return *this; }
411 bool operator!=(const iterator
&X
) const { return I
!= X
.I
; }
412 bool operator==(const iterator
&X
) const { return I
== X
.I
; }
414 const CaseStmt
* getCase() const {
415 return llvm::cast
<CaseStmt
>((*I
)->getLabel());
418 const CFGBlock
* getBlock() const {
423 iterator
begin() { return iterator(Src
->succ_rbegin()+1); }
424 iterator
end() { return iterator(Src
->succ_rend()); }
426 const SwitchStmt
*getSwitch() const {
427 return llvm::cast
<SwitchStmt
>(Src
->getTerminator());
430 ExplodedNode
* generateCaseStmtNode(const iterator
& I
, const GRState
* State
);
432 ExplodedNode
* generateDefaultCaseNode(const GRState
* State
,
433 bool isSink
= false);
435 const Expr
* getCondition() const { return Condition
; }
437 const GRState
* getState() const { return Pred
->State
; }
440 class GREndPathNodeBuilder
{
446 bool HasGeneratedNode
;
449 GREndPathNodeBuilder(const CFGBlock
* b
, ExplodedNode
* N
, GRCoreEngine
* e
)
450 : Eng(*e
), B(*b
), Pred(N
), HasGeneratedNode(false) {}
452 ~GREndPathNodeBuilder();
454 GRWorkList
&getWorkList() { return *Eng
.WList
; }
456 ExplodedNode
* getPredecessor() const { return Pred
; }
458 GRBlockCounter
getBlockCounter() const {
459 return Eng
.WList
->getBlockCounter();
462 unsigned getCurrentBlockCount() const {
463 return getBlockCounter().getNumVisited(
464 Pred
->getLocationContext()->getCurrentStackFrame(),
468 ExplodedNode
* generateNode(const GRState
* State
, const void *tag
= 0,
469 ExplodedNode
*P
= 0);
471 void GenerateCallExitNode(const GRState
*state
);
473 const CFGBlock
* getBlock() const { return &B
; }
475 const GRState
* getState() const {
476 return getPredecessor()->getState();
480 class GRCallEnterNodeBuilder
{
483 const ExplodedNode
*Pred
;
485 // The call site. For implicit automatic object dtor, this is the trigger
489 // The context of the callee.
490 const StackFrameContext
*CalleeCtx
;
492 // The parent block of the CallExpr.
493 const CFGBlock
*Block
;
495 // The CFGBlock index of the CallExpr.
499 GRCallEnterNodeBuilder(GRCoreEngine
&eng
, const ExplodedNode
*pred
,
500 const Stmt
*s
, const StackFrameContext
*callee
,
501 const CFGBlock
*blk
, unsigned idx
)
502 : Eng(eng
), Pred(pred
), CE(s
), CalleeCtx(callee
), Block(blk
), Index(idx
) {}
504 const GRState
*getState() const { return Pred
->getState(); }
506 const LocationContext
*getLocationContext() const {
507 return Pred
->getLocationContext();
510 const Stmt
*getCallExpr() const { return CE
; }
512 const StackFrameContext
*getCalleeContext() const { return CalleeCtx
; }
514 const CFGBlock
*getBlock() const { return Block
; }
516 unsigned getIndex() const { return Index
; }
518 void generateNode(const GRState
*state
);
521 class GRCallExitNodeBuilder
{
523 const ExplodedNode
*Pred
;
526 GRCallExitNodeBuilder(GRCoreEngine
&eng
, const ExplodedNode
*pred
)
527 : Eng(eng
), Pred(pred
) {}
529 const ExplodedNode
*getPredecessor() const { return Pred
; }
531 const GRState
*getState() const { return Pred
->getState(); }
533 void generateNode(const GRState
*state
);
535 } // end clang namespace