1f4a2713aSLionel Sambuc //==- CoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-//
2f4a2713aSLionel Sambuc //
3f4a2713aSLionel Sambuc // The LLVM Compiler Infrastructure
4f4a2713aSLionel Sambuc //
5f4a2713aSLionel Sambuc // This file is distributed under the University of Illinois Open Source
6f4a2713aSLionel Sambuc // License. See LICENSE.TXT for details.
7f4a2713aSLionel Sambuc //
8f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
9f4a2713aSLionel Sambuc //
10f4a2713aSLionel Sambuc // This file defines a generic engine for intraprocedural, path-sensitive,
11f4a2713aSLionel Sambuc // dataflow analysis via graph reachability engine.
12f4a2713aSLionel Sambuc //
13f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
14f4a2713aSLionel Sambuc
15f4a2713aSLionel Sambuc #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
16f4a2713aSLionel Sambuc #include "clang/AST/Expr.h"
17*0a6a1f1dSLionel Sambuc #include "clang/AST/ExprCXX.h"
18f4a2713aSLionel Sambuc #include "clang/AST/StmtCXX.h"
19f4a2713aSLionel Sambuc #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
20f4a2713aSLionel Sambuc #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
21f4a2713aSLionel Sambuc #include "llvm/ADT/DenseMap.h"
22f4a2713aSLionel Sambuc #include "llvm/ADT/Statistic.h"
23f4a2713aSLionel Sambuc #include "llvm/Support/Casting.h"
24f4a2713aSLionel Sambuc
25f4a2713aSLionel Sambuc using namespace clang;
26f4a2713aSLionel Sambuc using namespace ento;
27f4a2713aSLionel Sambuc
28*0a6a1f1dSLionel Sambuc #define DEBUG_TYPE "CoreEngine"
29*0a6a1f1dSLionel Sambuc
30f4a2713aSLionel Sambuc STATISTIC(NumSteps,
31f4a2713aSLionel Sambuc "The # of steps executed.");
32f4a2713aSLionel Sambuc STATISTIC(NumReachedMaxSteps,
33f4a2713aSLionel Sambuc "The # of times we reached the max number of steps.");
34f4a2713aSLionel Sambuc STATISTIC(NumPathsExplored,
35f4a2713aSLionel Sambuc "The # of paths explored by the analyzer.");
36f4a2713aSLionel Sambuc
37f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
38f4a2713aSLionel Sambuc // Worklist classes for exploration of reachable states.
39f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
40f4a2713aSLionel Sambuc
~Visitor()41f4a2713aSLionel Sambuc WorkList::Visitor::~Visitor() {}
42f4a2713aSLionel Sambuc
43f4a2713aSLionel Sambuc namespace {
44f4a2713aSLionel Sambuc class DFS : public WorkList {
45f4a2713aSLionel Sambuc SmallVector<WorkListUnit,20> Stack;
46f4a2713aSLionel Sambuc public:
hasWork() const47*0a6a1f1dSLionel Sambuc bool hasWork() const override {
48f4a2713aSLionel Sambuc return !Stack.empty();
49f4a2713aSLionel Sambuc }
50f4a2713aSLionel Sambuc
enqueue(const WorkListUnit & U)51*0a6a1f1dSLionel Sambuc void enqueue(const WorkListUnit& U) override {
52f4a2713aSLionel Sambuc Stack.push_back(U);
53f4a2713aSLionel Sambuc }
54f4a2713aSLionel Sambuc
dequeue()55*0a6a1f1dSLionel Sambuc WorkListUnit dequeue() override {
56f4a2713aSLionel Sambuc assert (!Stack.empty());
57f4a2713aSLionel Sambuc const WorkListUnit& U = Stack.back();
58f4a2713aSLionel Sambuc Stack.pop_back(); // This technically "invalidates" U, but we are fine.
59f4a2713aSLionel Sambuc return U;
60f4a2713aSLionel Sambuc }
61f4a2713aSLionel Sambuc
visitItemsInWorkList(Visitor & V)62*0a6a1f1dSLionel Sambuc bool visitItemsInWorkList(Visitor &V) override {
63f4a2713aSLionel Sambuc for (SmallVectorImpl<WorkListUnit>::iterator
64f4a2713aSLionel Sambuc I = Stack.begin(), E = Stack.end(); I != E; ++I) {
65f4a2713aSLionel Sambuc if (V.visit(*I))
66f4a2713aSLionel Sambuc return true;
67f4a2713aSLionel Sambuc }
68f4a2713aSLionel Sambuc return false;
69f4a2713aSLionel Sambuc }
70f4a2713aSLionel Sambuc };
71f4a2713aSLionel Sambuc
72f4a2713aSLionel Sambuc class BFS : public WorkList {
73f4a2713aSLionel Sambuc std::deque<WorkListUnit> Queue;
74f4a2713aSLionel Sambuc public:
hasWork() const75*0a6a1f1dSLionel Sambuc bool hasWork() const override {
76f4a2713aSLionel Sambuc return !Queue.empty();
77f4a2713aSLionel Sambuc }
78f4a2713aSLionel Sambuc
enqueue(const WorkListUnit & U)79*0a6a1f1dSLionel Sambuc void enqueue(const WorkListUnit& U) override {
80f4a2713aSLionel Sambuc Queue.push_back(U);
81f4a2713aSLionel Sambuc }
82f4a2713aSLionel Sambuc
dequeue()83*0a6a1f1dSLionel Sambuc WorkListUnit dequeue() override {
84f4a2713aSLionel Sambuc WorkListUnit U = Queue.front();
85f4a2713aSLionel Sambuc Queue.pop_front();
86f4a2713aSLionel Sambuc return U;
87f4a2713aSLionel Sambuc }
88f4a2713aSLionel Sambuc
visitItemsInWorkList(Visitor & V)89*0a6a1f1dSLionel Sambuc bool visitItemsInWorkList(Visitor &V) override {
90f4a2713aSLionel Sambuc for (std::deque<WorkListUnit>::iterator
91f4a2713aSLionel Sambuc I = Queue.begin(), E = Queue.end(); I != E; ++I) {
92f4a2713aSLionel Sambuc if (V.visit(*I))
93f4a2713aSLionel Sambuc return true;
94f4a2713aSLionel Sambuc }
95f4a2713aSLionel Sambuc return false;
96f4a2713aSLionel Sambuc }
97f4a2713aSLionel Sambuc };
98f4a2713aSLionel Sambuc
99f4a2713aSLionel Sambuc } // end anonymous namespace
100f4a2713aSLionel Sambuc
101f4a2713aSLionel Sambuc // Place the dstor for WorkList here because it contains virtual member
102f4a2713aSLionel Sambuc // functions, and we the code for the dstor generated in one compilation unit.
~WorkList()103f4a2713aSLionel Sambuc WorkList::~WorkList() {}
104f4a2713aSLionel Sambuc
makeDFS()105f4a2713aSLionel Sambuc WorkList *WorkList::makeDFS() { return new DFS(); }
makeBFS()106f4a2713aSLionel Sambuc WorkList *WorkList::makeBFS() { return new BFS(); }
107f4a2713aSLionel Sambuc
108f4a2713aSLionel Sambuc namespace {
109f4a2713aSLionel Sambuc class BFSBlockDFSContents : public WorkList {
110f4a2713aSLionel Sambuc std::deque<WorkListUnit> Queue;
111f4a2713aSLionel Sambuc SmallVector<WorkListUnit,20> Stack;
112f4a2713aSLionel Sambuc public:
hasWork() const113*0a6a1f1dSLionel Sambuc bool hasWork() const override {
114f4a2713aSLionel Sambuc return !Queue.empty() || !Stack.empty();
115f4a2713aSLionel Sambuc }
116f4a2713aSLionel Sambuc
enqueue(const WorkListUnit & U)117*0a6a1f1dSLionel Sambuc void enqueue(const WorkListUnit& U) override {
118f4a2713aSLionel Sambuc if (U.getNode()->getLocation().getAs<BlockEntrance>())
119f4a2713aSLionel Sambuc Queue.push_front(U);
120f4a2713aSLionel Sambuc else
121f4a2713aSLionel Sambuc Stack.push_back(U);
122f4a2713aSLionel Sambuc }
123f4a2713aSLionel Sambuc
dequeue()124*0a6a1f1dSLionel Sambuc WorkListUnit dequeue() override {
125f4a2713aSLionel Sambuc // Process all basic blocks to completion.
126f4a2713aSLionel Sambuc if (!Stack.empty()) {
127f4a2713aSLionel Sambuc const WorkListUnit& U = Stack.back();
128f4a2713aSLionel Sambuc Stack.pop_back(); // This technically "invalidates" U, but we are fine.
129f4a2713aSLionel Sambuc return U;
130f4a2713aSLionel Sambuc }
131f4a2713aSLionel Sambuc
132f4a2713aSLionel Sambuc assert(!Queue.empty());
133f4a2713aSLionel Sambuc // Don't use const reference. The subsequent pop_back() might make it
134f4a2713aSLionel Sambuc // unsafe.
135f4a2713aSLionel Sambuc WorkListUnit U = Queue.front();
136f4a2713aSLionel Sambuc Queue.pop_front();
137f4a2713aSLionel Sambuc return U;
138f4a2713aSLionel Sambuc }
visitItemsInWorkList(Visitor & V)139*0a6a1f1dSLionel Sambuc bool visitItemsInWorkList(Visitor &V) override {
140f4a2713aSLionel Sambuc for (SmallVectorImpl<WorkListUnit>::iterator
141f4a2713aSLionel Sambuc I = Stack.begin(), E = Stack.end(); I != E; ++I) {
142f4a2713aSLionel Sambuc if (V.visit(*I))
143f4a2713aSLionel Sambuc return true;
144f4a2713aSLionel Sambuc }
145f4a2713aSLionel Sambuc for (std::deque<WorkListUnit>::iterator
146f4a2713aSLionel Sambuc I = Queue.begin(), E = Queue.end(); I != E; ++I) {
147f4a2713aSLionel Sambuc if (V.visit(*I))
148f4a2713aSLionel Sambuc return true;
149f4a2713aSLionel Sambuc }
150f4a2713aSLionel Sambuc return false;
151f4a2713aSLionel Sambuc }
152f4a2713aSLionel Sambuc
153f4a2713aSLionel Sambuc };
154f4a2713aSLionel Sambuc } // end anonymous namespace
155f4a2713aSLionel Sambuc
makeBFSBlockDFSContents()156f4a2713aSLionel Sambuc WorkList* WorkList::makeBFSBlockDFSContents() {
157f4a2713aSLionel Sambuc return new BFSBlockDFSContents();
158f4a2713aSLionel Sambuc }
159f4a2713aSLionel Sambuc
160f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
161f4a2713aSLionel Sambuc // Core analysis engine.
162f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
163f4a2713aSLionel Sambuc
164f4a2713aSLionel Sambuc /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
ExecuteWorkList(const LocationContext * L,unsigned Steps,ProgramStateRef InitState)165f4a2713aSLionel Sambuc bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
166f4a2713aSLionel Sambuc ProgramStateRef InitState) {
167f4a2713aSLionel Sambuc
168*0a6a1f1dSLionel Sambuc if (G.num_roots() == 0) { // Initialize the analysis by constructing
169f4a2713aSLionel Sambuc // the root if none exists.
170f4a2713aSLionel Sambuc
171f4a2713aSLionel Sambuc const CFGBlock *Entry = &(L->getCFG()->getEntry());
172f4a2713aSLionel Sambuc
173f4a2713aSLionel Sambuc assert (Entry->empty() &&
174f4a2713aSLionel Sambuc "Entry block must be empty.");
175f4a2713aSLionel Sambuc
176f4a2713aSLionel Sambuc assert (Entry->succ_size() == 1 &&
177f4a2713aSLionel Sambuc "Entry block must have 1 successor.");
178f4a2713aSLionel Sambuc
179f4a2713aSLionel Sambuc // Mark the entry block as visited.
180f4a2713aSLionel Sambuc FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(),
181f4a2713aSLionel Sambuc L->getDecl(),
182f4a2713aSLionel Sambuc L->getCFG()->getNumBlockIDs());
183f4a2713aSLionel Sambuc
184f4a2713aSLionel Sambuc // Get the solitary successor.
185f4a2713aSLionel Sambuc const CFGBlock *Succ = *(Entry->succ_begin());
186f4a2713aSLionel Sambuc
187f4a2713aSLionel Sambuc // Construct an edge representing the
188f4a2713aSLionel Sambuc // starting location in the function.
189f4a2713aSLionel Sambuc BlockEdge StartLoc(Entry, Succ, L);
190f4a2713aSLionel Sambuc
191f4a2713aSLionel Sambuc // Set the current block counter to being empty.
192f4a2713aSLionel Sambuc WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
193f4a2713aSLionel Sambuc
194f4a2713aSLionel Sambuc if (!InitState)
195f4a2713aSLionel Sambuc // Generate the root.
196*0a6a1f1dSLionel Sambuc generateNode(StartLoc, SubEng.getInitialState(L), nullptr);
197f4a2713aSLionel Sambuc else
198*0a6a1f1dSLionel Sambuc generateNode(StartLoc, InitState, nullptr);
199f4a2713aSLionel Sambuc }
200f4a2713aSLionel Sambuc
201f4a2713aSLionel Sambuc // Check if we have a steps limit
202f4a2713aSLionel Sambuc bool UnlimitedSteps = Steps == 0;
203f4a2713aSLionel Sambuc
204f4a2713aSLionel Sambuc while (WList->hasWork()) {
205f4a2713aSLionel Sambuc if (!UnlimitedSteps) {
206f4a2713aSLionel Sambuc if (Steps == 0) {
207f4a2713aSLionel Sambuc NumReachedMaxSteps++;
208f4a2713aSLionel Sambuc break;
209f4a2713aSLionel Sambuc }
210f4a2713aSLionel Sambuc --Steps;
211f4a2713aSLionel Sambuc }
212f4a2713aSLionel Sambuc
213f4a2713aSLionel Sambuc NumSteps++;
214f4a2713aSLionel Sambuc
215f4a2713aSLionel Sambuc const WorkListUnit& WU = WList->dequeue();
216f4a2713aSLionel Sambuc
217f4a2713aSLionel Sambuc // Set the current block counter.
218f4a2713aSLionel Sambuc WList->setBlockCounter(WU.getBlockCounter());
219f4a2713aSLionel Sambuc
220f4a2713aSLionel Sambuc // Retrieve the node.
221f4a2713aSLionel Sambuc ExplodedNode *Node = WU.getNode();
222f4a2713aSLionel Sambuc
223f4a2713aSLionel Sambuc dispatchWorkItem(Node, Node->getLocation(), WU);
224f4a2713aSLionel Sambuc }
225f4a2713aSLionel Sambuc SubEng.processEndWorklist(hasWorkRemaining());
226f4a2713aSLionel Sambuc return WList->hasWork();
227f4a2713aSLionel Sambuc }
228f4a2713aSLionel Sambuc
dispatchWorkItem(ExplodedNode * Pred,ProgramPoint Loc,const WorkListUnit & WU)229f4a2713aSLionel Sambuc void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
230f4a2713aSLionel Sambuc const WorkListUnit& WU) {
231f4a2713aSLionel Sambuc // Dispatch on the location type.
232f4a2713aSLionel Sambuc switch (Loc.getKind()) {
233f4a2713aSLionel Sambuc case ProgramPoint::BlockEdgeKind:
234f4a2713aSLionel Sambuc HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred);
235f4a2713aSLionel Sambuc break;
236f4a2713aSLionel Sambuc
237f4a2713aSLionel Sambuc case ProgramPoint::BlockEntranceKind:
238f4a2713aSLionel Sambuc HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred);
239f4a2713aSLionel Sambuc break;
240f4a2713aSLionel Sambuc
241f4a2713aSLionel Sambuc case ProgramPoint::BlockExitKind:
242f4a2713aSLionel Sambuc assert (false && "BlockExit location never occur in forward analysis.");
243f4a2713aSLionel Sambuc break;
244f4a2713aSLionel Sambuc
245f4a2713aSLionel Sambuc case ProgramPoint::CallEnterKind: {
246f4a2713aSLionel Sambuc CallEnter CEnter = Loc.castAs<CallEnter>();
247f4a2713aSLionel Sambuc SubEng.processCallEnter(CEnter, Pred);
248f4a2713aSLionel Sambuc break;
249f4a2713aSLionel Sambuc }
250f4a2713aSLionel Sambuc
251f4a2713aSLionel Sambuc case ProgramPoint::CallExitBeginKind:
252f4a2713aSLionel Sambuc SubEng.processCallExit(Pred);
253f4a2713aSLionel Sambuc break;
254f4a2713aSLionel Sambuc
255f4a2713aSLionel Sambuc case ProgramPoint::EpsilonKind: {
256f4a2713aSLionel Sambuc assert(Pred->hasSinglePred() &&
257f4a2713aSLionel Sambuc "Assume epsilon has exactly one predecessor by construction");
258f4a2713aSLionel Sambuc ExplodedNode *PNode = Pred->getFirstPred();
259f4a2713aSLionel Sambuc dispatchWorkItem(Pred, PNode->getLocation(), WU);
260f4a2713aSLionel Sambuc break;
261f4a2713aSLionel Sambuc }
262f4a2713aSLionel Sambuc default:
263f4a2713aSLionel Sambuc assert(Loc.getAs<PostStmt>() ||
264f4a2713aSLionel Sambuc Loc.getAs<PostInitializer>() ||
265f4a2713aSLionel Sambuc Loc.getAs<PostImplicitCall>() ||
266f4a2713aSLionel Sambuc Loc.getAs<CallExitEnd>());
267f4a2713aSLionel Sambuc HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
268f4a2713aSLionel Sambuc break;
269f4a2713aSLionel Sambuc }
270f4a2713aSLionel Sambuc }
271f4a2713aSLionel Sambuc
ExecuteWorkListWithInitialState(const LocationContext * L,unsigned Steps,ProgramStateRef InitState,ExplodedNodeSet & Dst)272f4a2713aSLionel Sambuc bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L,
273f4a2713aSLionel Sambuc unsigned Steps,
274f4a2713aSLionel Sambuc ProgramStateRef InitState,
275f4a2713aSLionel Sambuc ExplodedNodeSet &Dst) {
276f4a2713aSLionel Sambuc bool DidNotFinish = ExecuteWorkList(L, Steps, InitState);
277*0a6a1f1dSLionel Sambuc for (ExplodedGraph::eop_iterator I = G.eop_begin(), E = G.eop_end(); I != E;
278*0a6a1f1dSLionel Sambuc ++I) {
279f4a2713aSLionel Sambuc Dst.Add(*I);
280f4a2713aSLionel Sambuc }
281f4a2713aSLionel Sambuc return DidNotFinish;
282f4a2713aSLionel Sambuc }
283f4a2713aSLionel Sambuc
HandleBlockEdge(const BlockEdge & L,ExplodedNode * Pred)284f4a2713aSLionel Sambuc void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) {
285f4a2713aSLionel Sambuc
286f4a2713aSLionel Sambuc const CFGBlock *Blk = L.getDst();
287f4a2713aSLionel Sambuc NodeBuilderContext BuilderCtx(*this, Blk, Pred);
288f4a2713aSLionel Sambuc
289f4a2713aSLionel Sambuc // Mark this block as visited.
290f4a2713aSLionel Sambuc const LocationContext *LC = Pred->getLocationContext();
291f4a2713aSLionel Sambuc FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(),
292f4a2713aSLionel Sambuc LC->getDecl(),
293f4a2713aSLionel Sambuc LC->getCFG()->getNumBlockIDs());
294f4a2713aSLionel Sambuc
295f4a2713aSLionel Sambuc // Check if we are entering the EXIT block.
296f4a2713aSLionel Sambuc if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
297f4a2713aSLionel Sambuc
298f4a2713aSLionel Sambuc assert (L.getLocationContext()->getCFG()->getExit().size() == 0
299f4a2713aSLionel Sambuc && "EXIT block cannot contain Stmts.");
300f4a2713aSLionel Sambuc
301f4a2713aSLionel Sambuc // Process the final state transition.
302f4a2713aSLionel Sambuc SubEng.processEndOfFunction(BuilderCtx, Pred);
303f4a2713aSLionel Sambuc
304f4a2713aSLionel Sambuc // This path is done. Don't enqueue any more nodes.
305f4a2713aSLionel Sambuc return;
306f4a2713aSLionel Sambuc }
307f4a2713aSLionel Sambuc
308f4a2713aSLionel Sambuc // Call into the SubEngine to process entering the CFGBlock.
309f4a2713aSLionel Sambuc ExplodedNodeSet dstNodes;
310f4a2713aSLionel Sambuc BlockEntrance BE(Blk, Pred->getLocationContext());
311f4a2713aSLionel Sambuc NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE);
312f4a2713aSLionel Sambuc SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred);
313f4a2713aSLionel Sambuc
314f4a2713aSLionel Sambuc // Auto-generate a node.
315f4a2713aSLionel Sambuc if (!nodeBuilder.hasGeneratedNodes()) {
316f4a2713aSLionel Sambuc nodeBuilder.generateNode(Pred->State, Pred);
317f4a2713aSLionel Sambuc }
318f4a2713aSLionel Sambuc
319f4a2713aSLionel Sambuc // Enqueue nodes onto the worklist.
320f4a2713aSLionel Sambuc enqueue(dstNodes);
321f4a2713aSLionel Sambuc }
322f4a2713aSLionel Sambuc
HandleBlockEntrance(const BlockEntrance & L,ExplodedNode * Pred)323f4a2713aSLionel Sambuc void CoreEngine::HandleBlockEntrance(const BlockEntrance &L,
324f4a2713aSLionel Sambuc ExplodedNode *Pred) {
325f4a2713aSLionel Sambuc
326f4a2713aSLionel Sambuc // Increment the block counter.
327f4a2713aSLionel Sambuc const LocationContext *LC = Pred->getLocationContext();
328f4a2713aSLionel Sambuc unsigned BlockId = L.getBlock()->getBlockID();
329f4a2713aSLionel Sambuc BlockCounter Counter = WList->getBlockCounter();
330f4a2713aSLionel Sambuc Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(),
331f4a2713aSLionel Sambuc BlockId);
332f4a2713aSLionel Sambuc WList->setBlockCounter(Counter);
333f4a2713aSLionel Sambuc
334f4a2713aSLionel Sambuc // Process the entrance of the block.
335f4a2713aSLionel Sambuc if (Optional<CFGElement> E = L.getFirstElement()) {
336f4a2713aSLionel Sambuc NodeBuilderContext Ctx(*this, L.getBlock(), Pred);
337f4a2713aSLionel Sambuc SubEng.processCFGElement(*E, Pred, 0, &Ctx);
338f4a2713aSLionel Sambuc }
339f4a2713aSLionel Sambuc else
340f4a2713aSLionel Sambuc HandleBlockExit(L.getBlock(), Pred);
341f4a2713aSLionel Sambuc }
342f4a2713aSLionel Sambuc
HandleBlockExit(const CFGBlock * B,ExplodedNode * Pred)343f4a2713aSLionel Sambuc void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) {
344f4a2713aSLionel Sambuc
345f4a2713aSLionel Sambuc if (const Stmt *Term = B->getTerminator()) {
346f4a2713aSLionel Sambuc switch (Term->getStmtClass()) {
347f4a2713aSLionel Sambuc default:
348f4a2713aSLionel Sambuc llvm_unreachable("Analysis for this terminator not implemented.");
349f4a2713aSLionel Sambuc
350*0a6a1f1dSLionel Sambuc case Stmt::CXXBindTemporaryExprClass:
351*0a6a1f1dSLionel Sambuc HandleCleanupTemporaryBranch(
352*0a6a1f1dSLionel Sambuc cast<CXXBindTemporaryExpr>(B->getTerminator().getStmt()), B, Pred);
353*0a6a1f1dSLionel Sambuc return;
354*0a6a1f1dSLionel Sambuc
355f4a2713aSLionel Sambuc // Model static initializers.
356f4a2713aSLionel Sambuc case Stmt::DeclStmtClass:
357f4a2713aSLionel Sambuc HandleStaticInit(cast<DeclStmt>(Term), B, Pred);
358f4a2713aSLionel Sambuc return;
359f4a2713aSLionel Sambuc
360f4a2713aSLionel Sambuc case Stmt::BinaryOperatorClass: // '&&' and '||'
361f4a2713aSLionel Sambuc HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
362f4a2713aSLionel Sambuc return;
363f4a2713aSLionel Sambuc
364f4a2713aSLionel Sambuc case Stmt::BinaryConditionalOperatorClass:
365f4a2713aSLionel Sambuc case Stmt::ConditionalOperatorClass:
366f4a2713aSLionel Sambuc HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(),
367f4a2713aSLionel Sambuc Term, B, Pred);
368f4a2713aSLionel Sambuc return;
369f4a2713aSLionel Sambuc
370f4a2713aSLionel Sambuc // FIXME: Use constant-folding in CFG construction to simplify this
371f4a2713aSLionel Sambuc // case.
372f4a2713aSLionel Sambuc
373f4a2713aSLionel Sambuc case Stmt::ChooseExprClass:
374f4a2713aSLionel Sambuc HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
375f4a2713aSLionel Sambuc return;
376f4a2713aSLionel Sambuc
377f4a2713aSLionel Sambuc case Stmt::CXXTryStmtClass: {
378f4a2713aSLionel Sambuc // Generate a node for each of the successors.
379f4a2713aSLionel Sambuc // Our logic for EH analysis can certainly be improved.
380f4a2713aSLionel Sambuc for (CFGBlock::const_succ_iterator it = B->succ_begin(),
381f4a2713aSLionel Sambuc et = B->succ_end(); it != et; ++it) {
382f4a2713aSLionel Sambuc if (const CFGBlock *succ = *it) {
383f4a2713aSLionel Sambuc generateNode(BlockEdge(B, succ, Pred->getLocationContext()),
384f4a2713aSLionel Sambuc Pred->State, Pred);
385f4a2713aSLionel Sambuc }
386f4a2713aSLionel Sambuc }
387f4a2713aSLionel Sambuc return;
388f4a2713aSLionel Sambuc }
389f4a2713aSLionel Sambuc
390f4a2713aSLionel Sambuc case Stmt::DoStmtClass:
391f4a2713aSLionel Sambuc HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
392f4a2713aSLionel Sambuc return;
393f4a2713aSLionel Sambuc
394f4a2713aSLionel Sambuc case Stmt::CXXForRangeStmtClass:
395f4a2713aSLionel Sambuc HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred);
396f4a2713aSLionel Sambuc return;
397f4a2713aSLionel Sambuc
398f4a2713aSLionel Sambuc case Stmt::ForStmtClass:
399f4a2713aSLionel Sambuc HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
400f4a2713aSLionel Sambuc return;
401f4a2713aSLionel Sambuc
402f4a2713aSLionel Sambuc case Stmt::ContinueStmtClass:
403f4a2713aSLionel Sambuc case Stmt::BreakStmtClass:
404f4a2713aSLionel Sambuc case Stmt::GotoStmtClass:
405f4a2713aSLionel Sambuc break;
406f4a2713aSLionel Sambuc
407f4a2713aSLionel Sambuc case Stmt::IfStmtClass:
408f4a2713aSLionel Sambuc HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
409f4a2713aSLionel Sambuc return;
410f4a2713aSLionel Sambuc
411f4a2713aSLionel Sambuc case Stmt::IndirectGotoStmtClass: {
412f4a2713aSLionel Sambuc // Only 1 successor: the indirect goto dispatch block.
413f4a2713aSLionel Sambuc assert (B->succ_size() == 1);
414f4a2713aSLionel Sambuc
415f4a2713aSLionel Sambuc IndirectGotoNodeBuilder
416f4a2713aSLionel Sambuc builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
417f4a2713aSLionel Sambuc *(B->succ_begin()), this);
418f4a2713aSLionel Sambuc
419f4a2713aSLionel Sambuc SubEng.processIndirectGoto(builder);
420f4a2713aSLionel Sambuc return;
421f4a2713aSLionel Sambuc }
422f4a2713aSLionel Sambuc
423f4a2713aSLionel Sambuc case Stmt::ObjCForCollectionStmtClass: {
424f4a2713aSLionel Sambuc // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
425f4a2713aSLionel Sambuc //
426f4a2713aSLionel Sambuc // (1) inside a basic block, which represents the binding of the
427f4a2713aSLionel Sambuc // 'element' variable to a value.
428f4a2713aSLionel Sambuc // (2) in a terminator, which represents the branch.
429f4a2713aSLionel Sambuc //
430f4a2713aSLionel Sambuc // For (1), subengines will bind a value (i.e., 0 or 1) indicating
431f4a2713aSLionel Sambuc // whether or not collection contains any more elements. We cannot
432f4a2713aSLionel Sambuc // just test to see if the element is nil because a container can
433f4a2713aSLionel Sambuc // contain nil elements.
434f4a2713aSLionel Sambuc HandleBranch(Term, Term, B, Pred);
435f4a2713aSLionel Sambuc return;
436f4a2713aSLionel Sambuc }
437f4a2713aSLionel Sambuc
438f4a2713aSLionel Sambuc case Stmt::SwitchStmtClass: {
439f4a2713aSLionel Sambuc SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
440f4a2713aSLionel Sambuc this);
441f4a2713aSLionel Sambuc
442f4a2713aSLionel Sambuc SubEng.processSwitch(builder);
443f4a2713aSLionel Sambuc return;
444f4a2713aSLionel Sambuc }
445f4a2713aSLionel Sambuc
446f4a2713aSLionel Sambuc case Stmt::WhileStmtClass:
447f4a2713aSLionel Sambuc HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
448f4a2713aSLionel Sambuc return;
449f4a2713aSLionel Sambuc }
450f4a2713aSLionel Sambuc }
451f4a2713aSLionel Sambuc
452f4a2713aSLionel Sambuc assert (B->succ_size() == 1 &&
453f4a2713aSLionel Sambuc "Blocks with no terminator should have at most 1 successor.");
454f4a2713aSLionel Sambuc
455f4a2713aSLionel Sambuc generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
456f4a2713aSLionel Sambuc Pred->State, Pred);
457f4a2713aSLionel Sambuc }
458f4a2713aSLionel Sambuc
HandleBranch(const Stmt * Cond,const Stmt * Term,const CFGBlock * B,ExplodedNode * Pred)459f4a2713aSLionel Sambuc void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term,
460f4a2713aSLionel Sambuc const CFGBlock * B, ExplodedNode *Pred) {
461f4a2713aSLionel Sambuc assert(B->succ_size() == 2);
462f4a2713aSLionel Sambuc NodeBuilderContext Ctx(*this, B, Pred);
463f4a2713aSLionel Sambuc ExplodedNodeSet Dst;
464f4a2713aSLionel Sambuc SubEng.processBranch(Cond, Term, Ctx, Pred, Dst,
465f4a2713aSLionel Sambuc *(B->succ_begin()), *(B->succ_begin()+1));
466f4a2713aSLionel Sambuc // Enqueue the new frontier onto the worklist.
467f4a2713aSLionel Sambuc enqueue(Dst);
468f4a2713aSLionel Sambuc }
469f4a2713aSLionel Sambuc
HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr * BTE,const CFGBlock * B,ExplodedNode * Pred)470*0a6a1f1dSLionel Sambuc void CoreEngine::HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
471*0a6a1f1dSLionel Sambuc const CFGBlock *B,
472*0a6a1f1dSLionel Sambuc ExplodedNode *Pred) {
473*0a6a1f1dSLionel Sambuc assert(B->succ_size() == 2);
474*0a6a1f1dSLionel Sambuc NodeBuilderContext Ctx(*this, B, Pred);
475*0a6a1f1dSLionel Sambuc ExplodedNodeSet Dst;
476*0a6a1f1dSLionel Sambuc SubEng.processCleanupTemporaryBranch(BTE, Ctx, Pred, Dst, *(B->succ_begin()),
477*0a6a1f1dSLionel Sambuc *(B->succ_begin() + 1));
478*0a6a1f1dSLionel Sambuc // Enqueue the new frontier onto the worklist.
479*0a6a1f1dSLionel Sambuc enqueue(Dst);
480*0a6a1f1dSLionel Sambuc }
481f4a2713aSLionel Sambuc
HandleStaticInit(const DeclStmt * DS,const CFGBlock * B,ExplodedNode * Pred)482f4a2713aSLionel Sambuc void CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B,
483f4a2713aSLionel Sambuc ExplodedNode *Pred) {
484f4a2713aSLionel Sambuc assert(B->succ_size() == 2);
485f4a2713aSLionel Sambuc NodeBuilderContext Ctx(*this, B, Pred);
486f4a2713aSLionel Sambuc ExplodedNodeSet Dst;
487f4a2713aSLionel Sambuc SubEng.processStaticInitializer(DS, Ctx, Pred, Dst,
488f4a2713aSLionel Sambuc *(B->succ_begin()), *(B->succ_begin()+1));
489f4a2713aSLionel Sambuc // Enqueue the new frontier onto the worklist.
490f4a2713aSLionel Sambuc enqueue(Dst);
491f4a2713aSLionel Sambuc }
492f4a2713aSLionel Sambuc
493f4a2713aSLionel Sambuc
HandlePostStmt(const CFGBlock * B,unsigned StmtIdx,ExplodedNode * Pred)494f4a2713aSLionel Sambuc void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx,
495f4a2713aSLionel Sambuc ExplodedNode *Pred) {
496f4a2713aSLionel Sambuc assert(B);
497f4a2713aSLionel Sambuc assert(!B->empty());
498f4a2713aSLionel Sambuc
499f4a2713aSLionel Sambuc if (StmtIdx == B->size())
500f4a2713aSLionel Sambuc HandleBlockExit(B, Pred);
501f4a2713aSLionel Sambuc else {
502f4a2713aSLionel Sambuc NodeBuilderContext Ctx(*this, B, Pred);
503f4a2713aSLionel Sambuc SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx);
504f4a2713aSLionel Sambuc }
505f4a2713aSLionel Sambuc }
506f4a2713aSLionel Sambuc
507f4a2713aSLionel Sambuc /// generateNode - Utility method to generate nodes, hook up successors,
508f4a2713aSLionel Sambuc /// and add nodes to the worklist.
generateNode(const ProgramPoint & Loc,ProgramStateRef State,ExplodedNode * Pred)509f4a2713aSLionel Sambuc void CoreEngine::generateNode(const ProgramPoint &Loc,
510f4a2713aSLionel Sambuc ProgramStateRef State,
511f4a2713aSLionel Sambuc ExplodedNode *Pred) {
512f4a2713aSLionel Sambuc
513f4a2713aSLionel Sambuc bool IsNew;
514*0a6a1f1dSLionel Sambuc ExplodedNode *Node = G.getNode(Loc, State, false, &IsNew);
515f4a2713aSLionel Sambuc
516f4a2713aSLionel Sambuc if (Pred)
517*0a6a1f1dSLionel Sambuc Node->addPredecessor(Pred, G); // Link 'Node' with its predecessor.
518f4a2713aSLionel Sambuc else {
519f4a2713aSLionel Sambuc assert (IsNew);
520*0a6a1f1dSLionel Sambuc G.addRoot(Node); // 'Node' has no predecessor. Make it a root.
521f4a2713aSLionel Sambuc }
522f4a2713aSLionel Sambuc
523f4a2713aSLionel Sambuc // Only add 'Node' to the worklist if it was freshly generated.
524f4a2713aSLionel Sambuc if (IsNew) WList->enqueue(Node);
525f4a2713aSLionel Sambuc }
526f4a2713aSLionel Sambuc
enqueueStmtNode(ExplodedNode * N,const CFGBlock * Block,unsigned Idx)527f4a2713aSLionel Sambuc void CoreEngine::enqueueStmtNode(ExplodedNode *N,
528f4a2713aSLionel Sambuc const CFGBlock *Block, unsigned Idx) {
529f4a2713aSLionel Sambuc assert(Block);
530f4a2713aSLionel Sambuc assert (!N->isSink());
531f4a2713aSLionel Sambuc
532f4a2713aSLionel Sambuc // Check if this node entered a callee.
533f4a2713aSLionel Sambuc if (N->getLocation().getAs<CallEnter>()) {
534f4a2713aSLionel Sambuc // Still use the index of the CallExpr. It's needed to create the callee
535f4a2713aSLionel Sambuc // StackFrameContext.
536f4a2713aSLionel Sambuc WList->enqueue(N, Block, Idx);
537f4a2713aSLionel Sambuc return;
538f4a2713aSLionel Sambuc }
539f4a2713aSLionel Sambuc
540f4a2713aSLionel Sambuc // Do not create extra nodes. Move to the next CFG element.
541f4a2713aSLionel Sambuc if (N->getLocation().getAs<PostInitializer>() ||
542f4a2713aSLionel Sambuc N->getLocation().getAs<PostImplicitCall>()) {
543f4a2713aSLionel Sambuc WList->enqueue(N, Block, Idx+1);
544f4a2713aSLionel Sambuc return;
545f4a2713aSLionel Sambuc }
546f4a2713aSLionel Sambuc
547f4a2713aSLionel Sambuc if (N->getLocation().getAs<EpsilonPoint>()) {
548f4a2713aSLionel Sambuc WList->enqueue(N, Block, Idx);
549f4a2713aSLionel Sambuc return;
550f4a2713aSLionel Sambuc }
551f4a2713aSLionel Sambuc
552*0a6a1f1dSLionel Sambuc if ((*Block)[Idx].getKind() == CFGElement::NewAllocator) {
553*0a6a1f1dSLionel Sambuc WList->enqueue(N, Block, Idx+1);
554*0a6a1f1dSLionel Sambuc return;
555*0a6a1f1dSLionel Sambuc }
556*0a6a1f1dSLionel Sambuc
557f4a2713aSLionel Sambuc // At this point, we know we're processing a normal statement.
558f4a2713aSLionel Sambuc CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>();
559f4a2713aSLionel Sambuc PostStmt Loc(CS.getStmt(), N->getLocationContext());
560f4a2713aSLionel Sambuc
561*0a6a1f1dSLionel Sambuc if (Loc == N->getLocation().withTag(nullptr)) {
562f4a2713aSLionel Sambuc // Note: 'N' should be a fresh node because otherwise it shouldn't be
563f4a2713aSLionel Sambuc // a member of Deferred.
564f4a2713aSLionel Sambuc WList->enqueue(N, Block, Idx+1);
565f4a2713aSLionel Sambuc return;
566f4a2713aSLionel Sambuc }
567f4a2713aSLionel Sambuc
568f4a2713aSLionel Sambuc bool IsNew;
569*0a6a1f1dSLionel Sambuc ExplodedNode *Succ = G.getNode(Loc, N->getState(), false, &IsNew);
570*0a6a1f1dSLionel Sambuc Succ->addPredecessor(N, G);
571f4a2713aSLionel Sambuc
572f4a2713aSLionel Sambuc if (IsNew)
573f4a2713aSLionel Sambuc WList->enqueue(Succ, Block, Idx+1);
574f4a2713aSLionel Sambuc }
575f4a2713aSLionel Sambuc
generateCallExitBeginNode(ExplodedNode * N)576f4a2713aSLionel Sambuc ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N) {
577f4a2713aSLionel Sambuc // Create a CallExitBegin node and enqueue it.
578f4a2713aSLionel Sambuc const StackFrameContext *LocCtx
579f4a2713aSLionel Sambuc = cast<StackFrameContext>(N->getLocationContext());
580f4a2713aSLionel Sambuc
581f4a2713aSLionel Sambuc // Use the callee location context.
582f4a2713aSLionel Sambuc CallExitBegin Loc(LocCtx);
583f4a2713aSLionel Sambuc
584f4a2713aSLionel Sambuc bool isNew;
585*0a6a1f1dSLionel Sambuc ExplodedNode *Node = G.getNode(Loc, N->getState(), false, &isNew);
586*0a6a1f1dSLionel Sambuc Node->addPredecessor(N, G);
587*0a6a1f1dSLionel Sambuc return isNew ? Node : nullptr;
588f4a2713aSLionel Sambuc }
589f4a2713aSLionel Sambuc
590f4a2713aSLionel Sambuc
enqueue(ExplodedNodeSet & Set)591f4a2713aSLionel Sambuc void CoreEngine::enqueue(ExplodedNodeSet &Set) {
592f4a2713aSLionel Sambuc for (ExplodedNodeSet::iterator I = Set.begin(),
593f4a2713aSLionel Sambuc E = Set.end(); I != E; ++I) {
594f4a2713aSLionel Sambuc WList->enqueue(*I);
595f4a2713aSLionel Sambuc }
596f4a2713aSLionel Sambuc }
597f4a2713aSLionel Sambuc
enqueue(ExplodedNodeSet & Set,const CFGBlock * Block,unsigned Idx)598f4a2713aSLionel Sambuc void CoreEngine::enqueue(ExplodedNodeSet &Set,
599f4a2713aSLionel Sambuc const CFGBlock *Block, unsigned Idx) {
600f4a2713aSLionel Sambuc for (ExplodedNodeSet::iterator I = Set.begin(),
601f4a2713aSLionel Sambuc E = Set.end(); I != E; ++I) {
602f4a2713aSLionel Sambuc enqueueStmtNode(*I, Block, Idx);
603f4a2713aSLionel Sambuc }
604f4a2713aSLionel Sambuc }
605f4a2713aSLionel Sambuc
enqueueEndOfFunction(ExplodedNodeSet & Set)606f4a2713aSLionel Sambuc void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set) {
607f4a2713aSLionel Sambuc for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) {
608f4a2713aSLionel Sambuc ExplodedNode *N = *I;
609f4a2713aSLionel Sambuc // If we are in an inlined call, generate CallExitBegin node.
610f4a2713aSLionel Sambuc if (N->getLocationContext()->getParent()) {
611f4a2713aSLionel Sambuc N = generateCallExitBeginNode(N);
612f4a2713aSLionel Sambuc if (N)
613f4a2713aSLionel Sambuc WList->enqueue(N);
614f4a2713aSLionel Sambuc } else {
615f4a2713aSLionel Sambuc // TODO: We should run remove dead bindings here.
616*0a6a1f1dSLionel Sambuc G.addEndOfPath(N);
617f4a2713aSLionel Sambuc NumPathsExplored++;
618f4a2713aSLionel Sambuc }
619f4a2713aSLionel Sambuc }
620f4a2713aSLionel Sambuc }
621f4a2713aSLionel Sambuc
622f4a2713aSLionel Sambuc
anchor()623f4a2713aSLionel Sambuc void NodeBuilder::anchor() { }
624f4a2713aSLionel Sambuc
generateNodeImpl(const ProgramPoint & Loc,ProgramStateRef State,ExplodedNode * FromN,bool MarkAsSink)625f4a2713aSLionel Sambuc ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc,
626f4a2713aSLionel Sambuc ProgramStateRef State,
627f4a2713aSLionel Sambuc ExplodedNode *FromN,
628f4a2713aSLionel Sambuc bool MarkAsSink) {
629f4a2713aSLionel Sambuc HasGeneratedNodes = true;
630f4a2713aSLionel Sambuc bool IsNew;
631*0a6a1f1dSLionel Sambuc ExplodedNode *N = C.Eng.G.getNode(Loc, State, MarkAsSink, &IsNew);
632*0a6a1f1dSLionel Sambuc N->addPredecessor(FromN, C.Eng.G);
633f4a2713aSLionel Sambuc Frontier.erase(FromN);
634f4a2713aSLionel Sambuc
635f4a2713aSLionel Sambuc if (!IsNew)
636*0a6a1f1dSLionel Sambuc return nullptr;
637f4a2713aSLionel Sambuc
638f4a2713aSLionel Sambuc if (!MarkAsSink)
639f4a2713aSLionel Sambuc Frontier.Add(N);
640f4a2713aSLionel Sambuc
641f4a2713aSLionel Sambuc return N;
642f4a2713aSLionel Sambuc }
643f4a2713aSLionel Sambuc
anchor()644f4a2713aSLionel Sambuc void NodeBuilderWithSinks::anchor() { }
645f4a2713aSLionel Sambuc
~StmtNodeBuilder()646f4a2713aSLionel Sambuc StmtNodeBuilder::~StmtNodeBuilder() {
647f4a2713aSLionel Sambuc if (EnclosingBldr)
648f4a2713aSLionel Sambuc for (ExplodedNodeSet::iterator I = Frontier.begin(),
649f4a2713aSLionel Sambuc E = Frontier.end(); I != E; ++I )
650f4a2713aSLionel Sambuc EnclosingBldr->addNodes(*I);
651f4a2713aSLionel Sambuc }
652f4a2713aSLionel Sambuc
anchor()653f4a2713aSLionel Sambuc void BranchNodeBuilder::anchor() { }
654f4a2713aSLionel Sambuc
generateNode(ProgramStateRef State,bool branch,ExplodedNode * NodePred)655f4a2713aSLionel Sambuc ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State,
656f4a2713aSLionel Sambuc bool branch,
657f4a2713aSLionel Sambuc ExplodedNode *NodePred) {
658f4a2713aSLionel Sambuc // If the branch has been marked infeasible we should not generate a node.
659f4a2713aSLionel Sambuc if (!isFeasible(branch))
660*0a6a1f1dSLionel Sambuc return nullptr;
661f4a2713aSLionel Sambuc
662f4a2713aSLionel Sambuc ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF,
663f4a2713aSLionel Sambuc NodePred->getLocationContext());
664f4a2713aSLionel Sambuc ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred);
665f4a2713aSLionel Sambuc return Succ;
666f4a2713aSLionel Sambuc }
667f4a2713aSLionel Sambuc
668f4a2713aSLionel Sambuc ExplodedNode*
generateNode(const iterator & I,ProgramStateRef St,bool IsSink)669f4a2713aSLionel Sambuc IndirectGotoNodeBuilder::generateNode(const iterator &I,
670f4a2713aSLionel Sambuc ProgramStateRef St,
671f4a2713aSLionel Sambuc bool IsSink) {
672f4a2713aSLionel Sambuc bool IsNew;
673*0a6a1f1dSLionel Sambuc ExplodedNode *Succ =
674*0a6a1f1dSLionel Sambuc Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
675*0a6a1f1dSLionel Sambuc St, IsSink, &IsNew);
676*0a6a1f1dSLionel Sambuc Succ->addPredecessor(Pred, Eng.G);
677f4a2713aSLionel Sambuc
678f4a2713aSLionel Sambuc if (!IsNew)
679*0a6a1f1dSLionel Sambuc return nullptr;
680f4a2713aSLionel Sambuc
681f4a2713aSLionel Sambuc if (!IsSink)
682f4a2713aSLionel Sambuc Eng.WList->enqueue(Succ);
683f4a2713aSLionel Sambuc
684f4a2713aSLionel Sambuc return Succ;
685f4a2713aSLionel Sambuc }
686f4a2713aSLionel Sambuc
687f4a2713aSLionel Sambuc
688f4a2713aSLionel Sambuc ExplodedNode*
generateCaseStmtNode(const iterator & I,ProgramStateRef St)689f4a2713aSLionel Sambuc SwitchNodeBuilder::generateCaseStmtNode(const iterator &I,
690f4a2713aSLionel Sambuc ProgramStateRef St) {
691f4a2713aSLionel Sambuc
692f4a2713aSLionel Sambuc bool IsNew;
693*0a6a1f1dSLionel Sambuc ExplodedNode *Succ =
694*0a6a1f1dSLionel Sambuc Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()),
695*0a6a1f1dSLionel Sambuc St, false, &IsNew);
696*0a6a1f1dSLionel Sambuc Succ->addPredecessor(Pred, Eng.G);
697f4a2713aSLionel Sambuc if (!IsNew)
698*0a6a1f1dSLionel Sambuc return nullptr;
699f4a2713aSLionel Sambuc
700f4a2713aSLionel Sambuc Eng.WList->enqueue(Succ);
701f4a2713aSLionel Sambuc return Succ;
702f4a2713aSLionel Sambuc }
703f4a2713aSLionel Sambuc
704f4a2713aSLionel Sambuc
705f4a2713aSLionel Sambuc ExplodedNode*
generateDefaultCaseNode(ProgramStateRef St,bool IsSink)706f4a2713aSLionel Sambuc SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St,
707f4a2713aSLionel Sambuc bool IsSink) {
708f4a2713aSLionel Sambuc // Get the block for the default case.
709f4a2713aSLionel Sambuc assert(Src->succ_rbegin() != Src->succ_rend());
710f4a2713aSLionel Sambuc CFGBlock *DefaultBlock = *Src->succ_rbegin();
711f4a2713aSLionel Sambuc
712f4a2713aSLionel Sambuc // Sanity check for default blocks that are unreachable and not caught
713f4a2713aSLionel Sambuc // by earlier stages.
714f4a2713aSLionel Sambuc if (!DefaultBlock)
715*0a6a1f1dSLionel Sambuc return nullptr;
716f4a2713aSLionel Sambuc
717f4a2713aSLionel Sambuc bool IsNew;
718*0a6a1f1dSLionel Sambuc ExplodedNode *Succ =
719*0a6a1f1dSLionel Sambuc Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()),
720*0a6a1f1dSLionel Sambuc St, IsSink, &IsNew);
721*0a6a1f1dSLionel Sambuc Succ->addPredecessor(Pred, Eng.G);
722f4a2713aSLionel Sambuc
723f4a2713aSLionel Sambuc if (!IsNew)
724*0a6a1f1dSLionel Sambuc return nullptr;
725f4a2713aSLionel Sambuc
726f4a2713aSLionel Sambuc if (!IsSink)
727f4a2713aSLionel Sambuc Eng.WList->enqueue(Succ);
728f4a2713aSLionel Sambuc
729f4a2713aSLionel Sambuc return Succ;
730f4a2713aSLionel Sambuc }
731