CoreEngine.cpp revision 9198c71a626e2f0d29d92152832f3e80f4af59b3
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//==- CoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This file defines a generic engine for intraprocedural, path-sensitive, 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// dataflow analysis via graph reachability engine. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_TYPE "CoreEngine" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/Expr.h" 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/AST/StmtCXX.h" 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/Casting.h" 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/DenseMap.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "llvm/ADT/Statistic.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace clang; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using namespace ento; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)STATISTIC(NumSteps, 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "The # of steps executed."); 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)STATISTIC(NumReachedMaxSteps, 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) "The # of times we reached the max number of steps."); 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)STATISTIC(NumPathsExplored, 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "The # of paths explored by the analyzer."); 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Worklist classes for exploration of reachable states. 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WorkList::Visitor::~Visitor() {} 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class DFS : public WorkList { 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallVector<WorkListUnit,20> Stack; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool hasWork() const { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return !Stack.empty(); 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void enqueue(const WorkListUnit& U) { 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Stack.push_back(U); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual WorkListUnit dequeue() { 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (!Stack.empty()); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WorkListUnit& U = Stack.back(); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Stack.pop_back(); // This technically "invalidates" U, but we are fine. 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return U; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool visitItemsInWorkList(Visitor &V) { 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (SmallVectorImpl<WorkListUnit>::iterator 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I = Stack.begin(), E = Stack.end(); I != E; ++I) { 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (V.visit(*I)) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class BFS : public WorkList { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::deque<WorkListUnit> Queue; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool hasWork() const { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return !Queue.empty(); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void enqueue(const WorkListUnit& U) { 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Queue.push_back(U); 802a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual WorkListUnit dequeue() { 832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) WorkListUnit U = Queue.front(); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Queue.pop_front(); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return U; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 882a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) virtual bool visitItemsInWorkList(Visitor &V) { 892a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (std::deque<WorkListUnit>::iterator 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) I = Queue.begin(), E = Queue.end(); I != E; ++I) { 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (V.visit(*I)) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // end anonymous namespace 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Place the dstor for WorkList here because it contains virtual member 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// functions, and we the code for the dstor generated in one compilation unit. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WorkList::~WorkList() {} 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WorkList *WorkList::makeDFS() { return new DFS(); } 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)WorkList *WorkList::makeBFS() { return new BFS(); } 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class BFSBlockDFSContents : public WorkList { 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::deque<WorkListUnit> Queue; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SmallVector<WorkListUnit,20> Stack; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual bool hasWork() const { 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return !Queue.empty() || !Stack.empty(); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void enqueue(const WorkListUnit& U) { 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (isa<BlockEntrance>(U.getNode()->getLocation())) 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Queue.push_front(U); 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Stack.push_back(U); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual WorkListUnit dequeue() { 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Process all basic blocks to completion. 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!Stack.empty()) { 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WorkListUnit& U = Stack.back(); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Stack.pop_back(); // This technically "invalidates" U, but we are fine. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return U; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(!Queue.empty()); 1322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Don't use const reference. The subsequent pop_back() might make it 1332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // unsafe. 1342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) WorkListUnit U = Queue.front(); 1352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Queue.pop_front(); 1362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return U; 1372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) virtual bool visitItemsInWorkList(Visitor &V) { 1392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (SmallVectorImpl<WorkListUnit>::iterator 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) I = Stack.begin(), E = Stack.end(); I != E; ++I) { 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (V.visit(*I)) 1422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 1432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (std::deque<WorkListUnit>::iterator 1452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) I = Queue.begin(), E = Queue.end(); I != E; ++I) { 1462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (V.visit(*I)) 1472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return true; 1482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return false; 1502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 1512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) }; 1532a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} // end anonymous namespace 1542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)WorkList* WorkList::makeBFSBlockDFSContents() { 1562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return new BFSBlockDFSContents(); 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Core analysis engine. 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef InitState) { 1662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (G->num_roots() == 0) { // Initialize the analysis by constructing 1682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // the root if none exists. 1692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const CFGBlock *Entry = &(L->getCFG()->getEntry()); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (Entry->empty() && 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Entry block must be empty."); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (Entry->succ_size() == 1 && 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Entry block must have 1 successor."); 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Mark the entry block as visited. 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(), 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) L->getDecl(), 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) L->getCFG()->getNumBlockIDs()); 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the solitary successor. 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CFGBlock *Succ = *(Entry->succ_begin()); 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Construct an edge representing the 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // starting location in the function. 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockEdge StartLoc(Entry, Succ, L); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Set the current block counter to being empty. 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!InitState) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Generate the root. 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) generateNode(StartLoc, SubEng.getInitialState(L), 0); 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) generateNode(StartLoc, InitState, 0); 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check if we have a steps limit 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool UnlimitedSteps = Steps == 0; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (WList->hasWork()) { 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!UnlimitedSteps) { 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Steps == 0) { 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NumReachedMaxSteps++; 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --Steps; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NumSteps++; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WorkListUnit& WU = WList->dequeue(); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Set the current block counter. 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->setBlockCounter(WU.getBlockCounter()); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Retrieve the node. 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Node = WU.getNode(); 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dispatchWorkItem(Node, Node->getLocation(), WU); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processEndWorklist(hasWorkRemaining()); 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return WList->hasWork(); 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const WorkListUnit& WU) { 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Dispatch on the location type. 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (Loc.getKind()) { 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ProgramPoint::BlockEdgeKind: 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBlockEdge(cast<BlockEdge>(Loc), Pred); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ProgramPoint::BlockEntranceKind: 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBlockEntrance(cast<BlockEntrance>(Loc), Pred); 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ProgramPoint::BlockExitKind: 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (false && "BlockExit location never occur in forward analysis."); 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 2442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case ProgramPoint::CallEnterKind: { 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CallEnter CEnter = cast<CallEnter>(Loc); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processCallEnter(CEnter, Pred); 2472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 2482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ProgramPoint::CallExitBeginKind: 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processCallExit(Pred); 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case ProgramPoint::EpsilonKind: { 2552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assert(Pred->hasSinglePred() && 2562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) "Assume epsilon has exactly one predecessor by construction"); 2572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedNode *PNode = Pred->getFirstPred(); 2582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) dispatchWorkItem(Pred, PNode->getLocation(), WU); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(isa<PostStmt>(Loc) || 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) isa<PostInitializer>(Loc) || 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) isa<PostImplicitCall>(Loc) || 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) isa<CallExitEnd>(Loc)); 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned Steps, 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef InitState, 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNodeSet &Dst) { 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool DidNotFinish = ExecuteWorkList(L, Steps, InitState); 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (ExplodedGraph::eop_iterator I = G->eop_begin(), 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = G->eop_end(); I != E; ++I) { 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Dst.Add(*I); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return DidNotFinish; 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CFGBlock *Blk = L.getDst(); 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeBuilderContext BuilderCtx(*this, Blk, Pred); 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Mark this block as visited. 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const LocationContext *LC = Pred->getLocationContext(); 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(), 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LC->getDecl(), 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LC->getCFG()->getNumBlockIDs()); 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check if we are entering the EXIT block. 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (L.getLocationContext()->getCFG()->getExit().size() == 0 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) && "EXIT block cannot contain Stmts."); 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Process the final state transition. 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processEndOfFunction(BuilderCtx); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This path is done. Don't enqueue any more nodes. 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Call into the SubEngine to process entering the CFGBlock. 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNodeSet dstNodes; 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockEntrance BE(Blk, Pred->getLocationContext()); 3102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processCFGBlockEntrance(L, nodeBuilder); 3122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Auto-generate a node. 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!nodeBuilder.hasGeneratedNodes()) { 3152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) nodeBuilder.generateNode(Pred->State, Pred); 3162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Enqueue nodes onto the worklist. 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enqueue(dstNodes); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Pred) { 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Increment the block counter. 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const LocationContext *LC = Pred->getLocationContext(); 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned BlockId = L.getBlock()->getBlockID(); 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockCounter Counter = WList->getBlockCounter(); 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(), 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) BlockId); 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->setBlockCounter(Counter); 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Process the entrance of the block. 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (CFGElement E = L.getFirstElement()) { 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processCFGElement(E, Pred, 0, &Ctx); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBlockExit(L.getBlock(), Pred); 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (const Stmt *Term = B->getTerminator()) { 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (Term->getStmtClass()) { 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) llvm_unreachable("Analysis for this terminator not implemented."); 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case Stmt::BinaryOperatorClass: // '&&' and '||' 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::BinaryConditionalOperatorClass: 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::ConditionalOperatorClass: 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Term, B, Pred); 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FIXME: Use constant-folding in CFG construction to simplify this 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // case. 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::ChooseExprClass: 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::CXXTryStmtClass: { 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Generate a node for each of the successors. 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Our logic for EH analysis can certainly be improved. 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (CFGBlock::const_succ_iterator it = B->succ_begin(), 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) et = B->succ_end(); it != et; ++it) { 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (const CFGBlock *succ = *it) { 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) generateNode(BlockEdge(B, succ, Pred->getLocationContext()), 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Pred->State, Pred); 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::DoStmtClass: 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::CXXForRangeStmtClass: 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::ForStmtClass: 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case Stmt::ContinueStmtClass: 3922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case Stmt::BreakStmtClass: 3932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case Stmt::GotoStmtClass: 3942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) break; 3952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 3962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case Stmt::IfStmtClass: 3972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 3982a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 3992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4002a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case Stmt::IndirectGotoStmtClass: { 4012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Only 1 successor: the indirect goto dispatch block. 4022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assert (B->succ_size() == 1); 4032a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndirectGotoNodeBuilder 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *(B->succ_begin()), this); 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processIndirectGoto(builder); 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::ObjCForCollectionStmtClass: { 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (1) inside a basic block, which represents the binding of the 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 'element' variable to a value. 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (2) in a terminator, which represents the branch. 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For (1), subengines will bind a value (i.e., 0 or 1) indicating 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // whether or not collection contains any more elements. We cannot 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // just test to see if the element is nil because a container can 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // contain nil elements. 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(Term, Term, B, Pred); 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) case Stmt::SwitchStmtClass: { 4282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 4292a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) this); 4302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SubEng.processSwitch(builder); 4322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Stmt::WhileStmtClass: 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (B->succ_size() == 1 && 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Blocks with no terminator should have at most 1 successor."); 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Pred->State, Pred); 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 4492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const CFGBlock * B, ExplodedNode *Pred) { 4502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assert(B->succ_size() == 2); 4512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) NodeBuilderContext Ctx(*this, B, Pred); 4522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedNodeSet Dst; 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SubEng.processBranch(Cond, Term, Ctx, Pred, Dst, 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *(B->succ_begin()), *(B->succ_begin()+1)); 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Enqueue the new frontier onto the worklist. 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) enqueue(Dst); 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Pred) { 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(B); 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(!B->empty()); 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (StmtIdx == B->size()) 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HandleBlockExit(B, Pred); 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else { 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NodeBuilderContext Ctx(*this, B, Pred); 4682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 4692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 4702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// generateNode - Utility method to generate nodes, hook up successors, 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// and add nodes to the worklist. 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::generateNode(const ProgramPoint &Loc, 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef State, 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Pred) { 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsNew; 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Node = G->getNode(Loc, State, false, &IsNew); 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Pred) 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor. 4832a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert (IsNew); 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) G->addRoot(Node); // 'Node' has no predecessor. Make it a root. 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Only add 'Node' to the worklist if it was freshly generated. 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsNew) WList->enqueue(Node); 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::enqueueStmtNode(ExplodedNode *N, 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const CFGBlock *Block, unsigned Idx) { 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(Block); 4952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) assert (!N->isSink()); 4962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Check if this node entered a callee. 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (isa<CallEnter>(N->getLocation())) { 4992a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Still use the index of the CallExpr. It's needed to create the callee 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // StackFrameContext. 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->enqueue(N, Block, Idx); 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Do not create extra nodes. Move to the next CFG element. 5062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (isa<PostInitializer>(N->getLocation()) || 5072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) isa<PostImplicitCall>(N->getLocation())) { 5082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) WList->enqueue(N, Block, Idx+1); 5092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return; 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (isa<EpsilonPoint>(N->getLocation())) { 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->enqueue(N, Block, Idx); 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // At this point, we know we're processing a normal statement. 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGStmt CS = cast<CFGStmt>((*Block)[Idx]); 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PostStmt Loc(CS.getStmt(), N->getLocationContext()); 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (Loc == N->getLocation()) { 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Note: 'N' should be a fresh node because otherwise it shouldn't be 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a member of Deferred. 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->enqueue(N, Block, Idx+1); 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsNew; 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Succ = G->getNode(Loc, N->getState(), false, &IsNew); 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Succ->addPredecessor(N, *G); 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsNew) 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->enqueue(Succ, Block, Idx+1); 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N) { 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create a CallExitBegin node and enqueue it. 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const StackFrameContext *LocCtx 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = cast<StackFrameContext>(N->getLocationContext()); 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Use the callee location context. 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CallExitBegin Loc(LocCtx); 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isNew; 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Node = G->getNode(Loc, N->getState(), false, &isNew); 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node->addPredecessor(N, *G); 5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return isNew ? Node : 0; 5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5502a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5512a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void CoreEngine::enqueue(ExplodedNodeSet &Set) { 5522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (ExplodedNodeSet::iterator I = Set.begin(), 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) E = Set.end(); I != E; ++I) { 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) WList->enqueue(*I); 5552a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 5562a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CoreEngine::enqueue(ExplodedNodeSet &Set, 5592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const CFGBlock *Block, unsigned Idx) { 5602a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (ExplodedNodeSet::iterator I = Set.begin(), 5612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) E = Set.end(); I != E; ++I) { 5622a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) enqueueStmtNode(*I, Block, Idx); 5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5642a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 5652a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 5662a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set) { 5672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) { 5682a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedNode *N = *I; 5692a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If we are in an inlined call, generate CallExitBegin node. 5702a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (N->getLocationContext()->getParent()) { 5712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) N = generateCallExitBeginNode(N); 5722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (N) 5732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) WList->enqueue(N); 5742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } else { 5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO: We should run remove dead bindings here. 5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) G->addEndOfPath(N); 5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NumPathsExplored++; 5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void NodeBuilder::anchor() { } 5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef State, 5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *FromN, 5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool MarkAsSink) { 5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HasGeneratedNodes = true; 5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsNew; 5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *N = C.Eng.G->getNode(Loc, State, MarkAsSink, &IsNew); 5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) N->addPredecessor(FromN, *C.Eng.G); 5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Frontier.erase(FromN); 5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsNew) 5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!MarkAsSink) 5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Frontier.Add(N); 6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return N; 6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void NodeBuilderWithSinks::anchor() { } 6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)StmtNodeBuilder::~StmtNodeBuilder() { 6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (EnclosingBldr) 6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (ExplodedNodeSet::iterator I = Frontier.begin(), 6092a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) E = Frontier.end(); I != E; ++I ) 6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EnclosingBldr->addNodes(*I); 6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BranchNodeBuilder::anchor() { } 6142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 6162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool branch, 6172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ExplodedNode *NodePred) { 6182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // If the branch has been marked infeasible we should not generate a node. 6192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (!isFeasible(branch)) 6202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return NULL; 6212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 6232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) NodePred->getLocationContext()); 6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Succ; 6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ExplodedNode* 6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)IndirectGotoNodeBuilder::generateNode(const iterator &I, 6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef St, 6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsSink) { 6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsNew; 6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Pred->getLocationContext()), St, 6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IsSink, &IsNew); 6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Succ->addPredecessor(Pred, *Eng.G); 6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsNew) 6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsSink) 6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Eng.WList->enqueue(Succ); 6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Succ; 6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ExplodedNode* 6495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 6505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ProgramStateRef St) { 6515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsNew; 6535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 6545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Pred->getLocationContext()), St, 6555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) false, &IsNew); 6565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Succ->addPredecessor(Pred, *Eng.G); 6575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsNew) 6585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 6595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Eng.WList->enqueue(Succ); 6615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Succ; 6625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ExplodedNode* 6665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 6675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsSink) { 6685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get the block for the default case. 6695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(Src->succ_rbegin() != Src->succ_rend()); 6705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock *DefaultBlock = *Src->succ_rbegin(); 6712a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 6722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Sanity check for default blocks that are unreachable and not caught 6735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // by earlier stages. 6745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!DefaultBlock) 6755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 6765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsNew; 6785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock, 6795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Pred->getLocationContext()), St, 6805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IsSink, &IsNew); 6815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Succ->addPredecessor(Pred, *Eng.G); 6825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsNew) 6845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 6855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsSink) 6875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Eng.WList->enqueue(Succ); 6885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Succ; 6905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)