1d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis//==- CoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-// 21eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump// 3f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// The LLVM Compiler Infrastructure 4f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 5f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// This file is distributed under the University of Illinois Open Source 6f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// License. See LICENSE.TXT for details. 7f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 8f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===// 9f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 10f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// This file defines a generic engine for intraprocedural, path-sensitive, 11f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// dataflow analysis via graph reachability engine. 12f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek// 13f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek//===----------------------------------------------------------------------===// 14f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 15131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks#define DEBUG_TYPE "CoreEngine" 16131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks 179b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 18f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include "clang/AST/Expr.h" 1946eaf7789a1059a7b42b7dbd183150c72df5738fTed Kremenek#include "clang/AST/StmtCXX.h" 2055fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" 2155fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 22f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include "llvm/ADT/DenseMap.h" 23131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks#include "llvm/ADT/Statistic.h" 2455fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "llvm/Support/Casting.h" 25131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks 26f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekusing namespace clang; 279ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 28f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 29df19fe7cafcb02859efeb6963cddeafef4350ddfAnna ZaksSTATISTIC(NumSteps, 30df19fe7cafcb02859efeb6963cddeafef4350ddfAnna Zaks "The # of steps executed."); 31131579f198f9cc9e6405adbe6159110c283ec5a4Anna ZaksSTATISTIC(NumReachedMaxSteps, 32131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks "The # of times we reached the max number of steps."); 33638e2d31fceed041e7e16aada4188c94cb5797bbAnna ZaksSTATISTIC(NumPathsExplored, 34638e2d31fceed041e7e16aada4188c94cb5797bbAnna Zaks "The # of paths explored by the analyzer."); 35131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks 36e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 37e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek// Worklist classes for exploration of reachable states. 38e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 39e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 40d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisWorkList::Visitor::~Visitor() {} 413e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek 42f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremeneknamespace { 43d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass DFS : public WorkList { 445f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<WorkListUnit,20> Stack; 45f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 46f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek virtual bool hasWork() const { 47f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return !Stack.empty(); 48f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 49f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 5055825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual void enqueue(const WorkListUnit& U) { 51f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Stack.push_back(U); 52f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 53f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 5455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual WorkListUnit dequeue() { 55f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek assert (!Stack.empty()); 56d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const WorkListUnit& U = Stack.back(); 57f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Stack.pop_back(); // This technically "invalidates" U, but we are fine. 58f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return U; 59f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 603e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek 6155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual bool visitItemsInWorkList(Visitor &V) { 625f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner for (SmallVectorImpl<WorkListUnit>::iterator 633e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek I = Stack.begin(), E = Stack.end(); I != E; ++I) { 6455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek if (V.visit(*I)) 653e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek return true; 663e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek } 673e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek return false; 683e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek } 69f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 71d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisclass BFS : public WorkList { 72d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis std::deque<WorkListUnit> Queue; 738ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenekpublic: 748ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek virtual bool hasWork() const { 758ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek return !Queue.empty(); 768ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek } 771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual void enqueue(const WorkListUnit& U) { 798d0f528afd9fcb9ebb8ccb4b8a529a05375b628eJordan Rose Queue.push_back(U); 808ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek } 811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8255825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual WorkListUnit dequeue() { 83d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkListUnit U = Queue.front(); 843e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek Queue.pop_front(); 858ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek return U; 868ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek } 873e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek 8855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual bool visitItemsInWorkList(Visitor &V) { 89d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis for (std::deque<WorkListUnit>::iterator 903e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek I = Queue.begin(), E = Queue.end(); I != E; ++I) { 9155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek if (V.visit(*I)) 923e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek return true; 933e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek } 943e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek return false; 953e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek } 968ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek}; 971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 98f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end anonymous namespace 99f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 100d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis// Place the dstor for WorkList here because it contains virtual member 101ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek// functions, and we the code for the dstor generated in one compilation unit. 102d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios KyrtzidisWorkList::~WorkList() {} 103ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 10455825aa2d88fe82bf3622f195046ae48532d3106Ted KremenekWorkList *WorkList::makeDFS() { return new DFS(); } 10555825aa2d88fe82bf3622f195046ae48532d3106Ted KremenekWorkList *WorkList::makeBFS() { return new BFS(); } 106f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 107e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremeneknamespace { 108d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis class BFSBlockDFSContents : public WorkList { 109d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis std::deque<WorkListUnit> Queue; 1105f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner SmallVector<WorkListUnit,20> Stack; 111e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek public: 112e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek virtual bool hasWork() const { 113e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek return !Queue.empty() || !Stack.empty(); 114e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 1151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 11655825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual void enqueue(const WorkListUnit& U) { 1177a95de68c093991047ed8d339479ccad51b88663David Blaikie if (U.getNode()->getLocation().getAs<BlockEntrance>()) 1183e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek Queue.push_front(U); 119e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek else 120e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek Stack.push_back(U); 121e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 1221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 12355825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual WorkListUnit dequeue() { 124e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek // Process all basic blocks to completion. 125e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek if (!Stack.empty()) { 126d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const WorkListUnit& U = Stack.back(); 127e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek Stack.pop_back(); // This technically "invalidates" U, but we are fine. 128e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek return U; 129e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 1301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 131e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek assert(!Queue.empty()); 132e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek // Don't use const reference. The subsequent pop_back() might make it 133e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek // unsafe. 134d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis WorkListUnit U = Queue.front(); 1353e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek Queue.pop_front(); 1361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return U; 137e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 13855825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek virtual bool visitItemsInWorkList(Visitor &V) { 1395f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner for (SmallVectorImpl<WorkListUnit>::iterator 1403e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek I = Stack.begin(), E = Stack.end(); I != E; ++I) { 14155825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek if (V.visit(*I)) 1423e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek return true; 1433e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek } 144d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis for (std::deque<WorkListUnit>::iterator 1453e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek I = Queue.begin(), E = Queue.end(); I != E; ++I) { 14655825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek if (V.visit(*I)) 1473e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek return true; 1483e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek } 1493e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek return false; 1503e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek } 1513e47b486f200d2b4cfb069c6f0d20fe5cf189fcdTed Kremenek 152e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek }; 153e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek} // end anonymous namespace 154e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 15555825aa2d88fe82bf3622f195046ae48532d3106Ted KremenekWorkList* WorkList::makeBFSBlockDFSContents() { 156e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek return new BFSBlockDFSContents(); 157e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek} 158e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 159e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 160e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek// Core analysis engine. 161e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 162102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 163f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 164d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidisbool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, 1658bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef InitState) { 1661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 167f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek if (G->num_roots() == 0) { // Initialize the analysis by constructing 168f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // the root if none exists. 1691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1709c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Entry = &(L->getCFG()->getEntry()); 1711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump assert (Entry->empty() && 173f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek "Entry block must be empty."); 1741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 175f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek assert (Entry->succ_size() == 1 && 176f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek "Entry block must have 1 successor."); 1771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 178e62f048960645b79363408fdead53fec2a063c52Anna Zaks // Mark the entry block as visited. 179e62f048960645b79363408fdead53fec2a063c52Anna Zaks FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(), 180e62f048960645b79363408fdead53fec2a063c52Anna Zaks L->getDecl(), 181e62f048960645b79363408fdead53fec2a063c52Anna Zaks L->getCFG()->getNumBlockIDs()); 182e62f048960645b79363408fdead53fec2a063c52Anna Zaks 183f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Get the solitary successor. 1849c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Succ = *(Entry->succ_begin()); 1851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 186f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Construct an edge representing the 187f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // starting location in the function. 18825e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu BlockEdge StartLoc(Entry, Succ, L); 1891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1908e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Set the current block counter to being empty. 1918e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1932ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu if (!InitState) 1942ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu // Generate the root. 1957771406ac3c58d77468d9d176262ad7ae7ff5050Ted Kremenek generateNode(StartLoc, SubEng.getInitialState(L), 0); 1962ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu else 197d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek generateNode(StartLoc, InitState, 0); 198f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 1991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 200cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care // Check if we have a steps limit 201cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care bool UnlimitedSteps = Steps == 0; 202cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care 203cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care while (WList->hasWork()) { 204cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care if (!UnlimitedSteps) { 205131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks if (Steps == 0) { 206131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks NumReachedMaxSteps++; 207cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care break; 208131579f198f9cc9e6405adbe6159110c283ec5a4Anna Zaks } 209cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care --Steps; 210cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care } 211cf9ce13774dad86f780d84cd41e6bd64c039324aTom Care 212df19fe7cafcb02859efeb6963cddeafef4350ddfAnna Zaks NumSteps++; 213df19fe7cafcb02859efeb6963cddeafef4350ddfAnna Zaks 21455825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek const WorkListUnit& WU = WList->dequeue(); 2151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2168e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Set the current block counter. 2178e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek WList->setBlockCounter(WU.getBlockCounter()); 2188e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 2198e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Retrieve the node. 2209c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Node = WU.getNode(); 2211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2225903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks dispatchWorkItem(Node, Node->getLocation(), WU); 2235903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks } 2245903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks SubEng.processEndWorklist(hasWorkRemaining()); 2255903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks return WList->hasWork(); 2265903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks} 227e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 2285903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaksvoid CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc, 2295903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks const WorkListUnit& WU) { 2305903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks // Dispatch on the location type. 2315903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks switch (Loc.getKind()) { 2325903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks case ProgramPoint::BlockEdgeKind: 2337a95de68c093991047ed8d339479ccad51b88663David Blaikie HandleBlockEdge(Loc.castAs<BlockEdge>(), Pred); 2345903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks break; 2355903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks 2365903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks case ProgramPoint::BlockEntranceKind: 2377a95de68c093991047ed8d339479ccad51b88663David Blaikie HandleBlockEntrance(Loc.castAs<BlockEntrance>(), Pred); 2385903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks break; 2395903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks 2405903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks case ProgramPoint::BlockExitKind: 2415903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks assert (false && "BlockExit location never occur in forward analysis."); 2425903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks break; 2435903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks 2445903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks case ProgramPoint::CallEnterKind: { 2457a95de68c093991047ed8d339479ccad51b88663David Blaikie CallEnter CEnter = Loc.castAs<CallEnter>(); 2465903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks SubEng.processCallEnter(CEnter, Pred); 2475903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks break; 2485903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks } 249102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 2500b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks case ProgramPoint::CallExitBeginKind: 2515903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks SubEng.processCallExit(Pred); 2525903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks break; 253102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 2545903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks case ProgramPoint::EpsilonKind: { 2555903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks assert(Pred->hasSinglePred() && 2565903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks "Assume epsilon has exactly one predecessor by construction"); 2575903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks ExplodedNode *PNode = Pred->getFirstPred(); 2585903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks dispatchWorkItem(Pred, PNode->getLocation(), WU); 2595903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks break; 260f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 2615903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks default: 2627a95de68c093991047ed8d339479ccad51b88663David Blaikie assert(Loc.getAs<PostStmt>() || 2637a95de68c093991047ed8d339479ccad51b88663David Blaikie Loc.getAs<PostInitializer>() || 2647a95de68c093991047ed8d339479ccad51b88663David Blaikie Loc.getAs<PostImplicitCall>() || 2657a95de68c093991047ed8d339479ccad51b88663David Blaikie Loc.getAs<CallExitEnd>()); 2665903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred); 2675903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks break; 268f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 269f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 270f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 271253955ca25c7e7049963b5db613c0cd15d66e4f8Anna Zaksbool CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 27218c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek unsigned Steps, 2738bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef InitState, 27418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNodeSet &Dst) { 275253955ca25c7e7049963b5db613c0cd15d66e4f8Anna Zaks bool DidNotFinish = ExecuteWorkList(L, Steps, InitState); 276626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek for (ExplodedGraph::eop_iterator I = G->eop_begin(), 277626719bd2c09e27fe7c182724a812d27f59e3819Ted Kremenek E = G->eop_end(); I != E; ++I) { 2782ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu Dst.Add(*I); 2792ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu } 280253955ca25c7e7049963b5db613c0cd15d66e4f8Anna Zaks return DidNotFinish; 2812ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu} 2822ce43c8f43254a9edea53a20dc0e69195bc82ae0Zhongxing Xu 2839c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { 2841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2859c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock *Blk = L.getDst(); 286c03a39e16762627b421247b12a2658be630a3300Anna Zaks NodeBuilderContext BuilderCtx(*this, Blk, Pred); 2871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 288e62f048960645b79363408fdead53fec2a063c52Anna Zaks // Mark this block as visited. 289e62f048960645b79363408fdead53fec2a063c52Anna Zaks const LocationContext *LC = Pred->getLocationContext(); 290e62f048960645b79363408fdead53fec2a063c52Anna Zaks FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(), 291e62f048960645b79363408fdead53fec2a063c52Anna Zaks LC->getDecl(), 292e62f048960645b79363408fdead53fec2a063c52Anna Zaks LC->getCFG()->getNumBlockIDs()); 293e62f048960645b79363408fdead53fec2a063c52Anna Zaks 2941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Check if we are entering the EXIT block. 295cb74d720b89b68bb2ecf2827d0e2eb66d236ab85Zhongxing Xu if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 2961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 297cb74d720b89b68bb2ecf2827d0e2eb66d236ab85Zhongxing Xu assert (L.getLocationContext()->getCFG()->getExit().size() == 0 298cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek && "EXIT block cannot contain Stmts."); 299f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 30011062b118476368fa5b294954713e5df97d8599fTed Kremenek // Process the final state transition. 301b355be838a22a511d078504b2277f70aea52ca85Anna Zaks SubEng.processEndOfFunction(BuilderCtx, Pred); 302f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 303f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // This path is done. Don't enqueue any more nodes. 304f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return; 305f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 3066a6719a3a11087b48d9f1a4eb08b3bd43cb05a65Ted Kremenek 307c03a39e16762627b421247b12a2658be630a3300Anna Zaks // Call into the SubEngine to process entering the CFGBlock. 30827c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek ExplodedNodeSet dstNodes; 30927c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek BlockEntrance BE(Blk, Pred->getLocationContext()); 310c03a39e16762627b421247b12a2658be630a3300Anna Zaks NodeBuilderWithSinks nodeBuilder(Pred, dstNodes, BuilderCtx, BE); 311b355be838a22a511d078504b2277f70aea52ca85Anna Zaks SubEng.processCFGBlockEntrance(L, nodeBuilder, Pred); 31227c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 313c03a39e16762627b421247b12a2658be630a3300Anna Zaks // Auto-generate a node. 314c03a39e16762627b421247b12a2658be630a3300Anna Zaks if (!nodeBuilder.hasGeneratedNodes()) { 315c03a39e16762627b421247b12a2658be630a3300Anna Zaks nodeBuilder.generateNode(Pred->State, Pred); 31627c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek } 31727c54e57c4a012dcdf2b40cf985b70d0b9caa69eTed Kremenek 318c03a39e16762627b421247b12a2658be630a3300Anna Zaks // Enqueue nodes onto the worklist. 319c03a39e16762627b421247b12a2658be630a3300Anna Zaks enqueue(dstNodes); 320f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 321f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 3229c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid CoreEngine::HandleBlockEntrance(const BlockEntrance &L, 3239c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred) { 3241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3258e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Increment the block counter. 326e62f048960645b79363408fdead53fec2a063c52Anna Zaks const LocationContext *LC = Pred->getLocationContext(); 327e62f048960645b79363408fdead53fec2a063c52Anna Zaks unsigned BlockId = L.getBlock()->getBlockID(); 328d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis BlockCounter Counter = WList->getBlockCounter(); 329e62f048960645b79363408fdead53fec2a063c52Anna Zaks Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(), 330e62f048960645b79363408fdead53fec2a063c52Anna Zaks BlockId); 3318e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek WList->setBlockCounter(Counter); 3321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Process the entrance of the block. 334b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGElement> E = L.getFirstElement()) { 335c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks NodeBuilderContext Ctx(*this, L.getBlock(), Pred); 336b07805485c603be3d8011f72611465324c9e664bDavid Blaikie SubEng.processCFGElement(*E, Pred, 0, &Ctx); 337f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 3381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump else 339425c08c53ccbfb84e52129406b259ec59da22e64Ted Kremenek HandleBlockExit(L.getBlock(), Pred); 340f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 341f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 3429c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { 3431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3449c378f705405d37f49795d5e915989de774fe11fTed Kremenek if (const Stmt *Term = B->getTerminator()) { 3457d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek switch (Term->getStmtClass()) { 3467d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek default: 347b219cfc4d75f0a03630b7c4509ef791b7e97b2c8David Blaikie llvm_unreachable("Analysis for this terminator not implemented."); 3481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3490f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek // Model static initializers. 3500f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek case Stmt::DeclStmtClass: 3510f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek HandleStaticInit(cast<DeclStmt>(Term), B, Pred); 3520f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek return; 3530f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek 354f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek case Stmt::BinaryOperatorClass: // '&&' and '||' 355f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 356f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 35856ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall case Stmt::BinaryConditionalOperatorClass: 359f233d48cfc513b045e2c2cfca5c175220fbd0a82Ted Kremenek case Stmt::ConditionalOperatorClass: 36056ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall HandleBranch(cast<AbstractConditionalOperator>(Term)->getCond(), 36156ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall Term, B, Pred); 362f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 364f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek // FIXME: Use constant-folding in CFG construction to simplify this 365f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek // case. 3661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 367f233d48cfc513b045e2c2cfca5c175220fbd0a82Ted Kremenek case Stmt::ChooseExprClass: 368f233d48cfc513b045e2c2cfca5c175220fbd0a82Ted Kremenek HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 369f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 371337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek case Stmt::CXXTryStmtClass: { 372337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek // Generate a node for each of the successors. 373337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek // Our logic for EH analysis can certainly be improved. 374337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek for (CFGBlock::const_succ_iterator it = B->succ_begin(), 375337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek et = B->succ_end(); it != et; ++it) { 376337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek if (const CFGBlock *succ = *it) { 377337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek generateNode(BlockEdge(B, succ, Pred->getLocationContext()), 378337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek Pred->State, Pred); 379337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek } 380337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek } 381337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek return; 382337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek } 383337e4dbc6859589b8878146a88bebf754e916702Ted Kremenek 384f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek case Stmt::DoStmtClass: 385f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 386f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 38846eaf7789a1059a7b42b7dbd183150c72df5738fTed Kremenek case Stmt::CXXForRangeStmtClass: 38946eaf7789a1059a7b42b7dbd183150c72df5738fTed Kremenek HandleBranch(cast<CXXForRangeStmt>(Term)->getCond(), Term, B, Pred); 39046eaf7789a1059a7b42b7dbd183150c72df5738fTed Kremenek return; 39146eaf7789a1059a7b42b7dbd183150c72df5738fTed Kremenek 3927d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek case Stmt::ForStmtClass: 3937d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 394f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 396a58e833c81a95e76c3a96fc982810d148537531bTed Kremenek case Stmt::ContinueStmtClass: 397a58e833c81a95e76c3a96fc982810d148537531bTed Kremenek case Stmt::BreakStmtClass: 3981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump case Stmt::GotoStmtClass: 3997d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek break; 4001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 401f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek case Stmt::IfStmtClass: 402f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 403f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 4041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 405754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek case Stmt::IndirectGotoStmtClass: { 406754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek // Only 1 successor: the indirect goto dispatch block. 407754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek assert (B->succ_size() == 1); 4081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 409d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis IndirectGotoNodeBuilder 410754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 411754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek *(B->succ_begin()), this); 4121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4137771406ac3c58d77468d9d176262ad7ae7ff5050Ted Kremenek SubEng.processIndirectGoto(builder); 414754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek return; 415754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek } 4161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 417af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek case Stmt::ObjCForCollectionStmtClass: { 418af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 419af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // 420af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // (1) inside a basic block, which represents the binding of the 421af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // 'element' variable to a value. 422af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // (2) in a terminator, which represents the branch. 423af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // 424af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // For (1), subengines will bind a value (i.e., 0 or 1) indicating 425af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // whether or not collection contains any more elements. We cannot 426af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // just test to see if the element is nil because a container can 427af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // contain nil elements. 428af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek HandleBranch(Term, Term, B, Pred); 429af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek return; 430af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek } 4311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 432daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek case Stmt::SwitchStmtClass: { 433d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 434031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu this); 4351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4367771406ac3c58d77468d9d176262ad7ae7ff5050Ted Kremenek SubEng.processSwitch(builder); 437daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return; 438daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 4391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4407d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek case Stmt::WhileStmtClass: 4417d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 442f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 4437d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek } 4447d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek } 445f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek 446f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek assert (B->succ_size() == 1 && 447f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek "Blocks with no terminator should have at most 1 successor."); 4481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 449d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek generateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 45025e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu Pred->State, Pred); 451f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 452f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 4539c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid CoreEngine::HandleBranch(const Stmt *Cond, const Stmt *Term, 4549c378f705405d37f49795d5e915989de774fe11fTed Kremenek const CFGBlock * B, ExplodedNode *Pred) { 4557771406ac3c58d77468d9d176262ad7ae7ff5050Ted Kremenek assert(B->succ_size() == 2); 456c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks NodeBuilderContext Ctx(*this, B, Pred); 4571aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks ExplodedNodeSet Dst; 4581aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks SubEng.processBranch(Cond, Term, Ctx, Pred, Dst, 459a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks *(B->succ_begin()), *(B->succ_begin()+1)); 4601aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks // Enqueue the new frontier onto the worklist. 4611aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks enqueue(Dst); 4627d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek} 4637d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek 4640f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek 4650f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenekvoid CoreEngine::HandleStaticInit(const DeclStmt *DS, const CFGBlock *B, 4660f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek ExplodedNode *Pred) { 4670f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek assert(B->succ_size() == 2); 4680f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek NodeBuilderContext Ctx(*this, B, Pred); 4690f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek ExplodedNodeSet Dst; 4700f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek SubEng.processStaticInitializer(DS, Ctx, Pred, Dst, 4710f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek *(B->succ_begin()), *(B->succ_begin()+1)); 4720f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek // Enqueue the new frontier onto the worklist. 4730f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek enqueue(Dst); 4740f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek} 4750f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek 4760f5c5c60e9806d13f0907cd99d7204ffab0e08f7Ted Kremenek 4779c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid CoreEngine::HandlePostStmt(const CFGBlock *B, unsigned StmtIdx, 4789c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Pred) { 479a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks assert(B); 480a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks assert(!B->empty()); 481f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 482425c08c53ccbfb84e52129406b259ec59da22e64Ted Kremenek if (StmtIdx == B->size()) 483425c08c53ccbfb84e52129406b259ec59da22e64Ted Kremenek HandleBlockExit(B, Pred); 484f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek else { 485c9003c89c7aead1686aba89c8e3ddcea1f2bec54Anna Zaks NodeBuilderContext Ctx(*this, B, Pred); 486ebae6d0209e1ec3d5ea14f9e63bd0d740218ed14Anna Zaks SubEng.processCFGElement((*B)[StmtIdx], Pred, StmtIdx, &Ctx); 487f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 488f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 489f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 490d048c6ef5b6cfaa0cecb8cc1d4bdace32ed21d07Ted Kremenek/// generateNode - Utility method to generate nodes, hook up successors, 491f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek/// and add nodes to the worklist. 4929c378f705405d37f49795d5e915989de774fe11fTed Kremenekvoid CoreEngine::generateNode(const ProgramPoint &Loc, 4938bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef State, 49418c66fdc3c4008d335885695fe36fb5353c5f672Ted Kremenek ExplodedNode *Pred) { 4951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 496f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek bool IsNew; 4976800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks ExplodedNode *Node = G->getNode(Loc, State, false, &IsNew); 4981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (Pred) 5005fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor. 501f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek else { 502f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek assert (IsNew); 503f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek G->addRoot(Node); // 'Node' has no predecessor. Make it a root. 504f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 5051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 506f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Only add 'Node' to the worklist if it was freshly generated. 50755825aa2d88fe82bf3622f195046ae48532d3106Ted Kremenek if (IsNew) WList->enqueue(Node); 508f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 509f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 510dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaksvoid CoreEngine::enqueueStmtNode(ExplodedNode *N, 511dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks const CFGBlock *Block, unsigned Idx) { 512cdcc653642d4ac9255c574fabe74a48149e06733Anna Zaks assert(Block); 513dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks assert (!N->isSink()); 514dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 515dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks // Check if this node entered a callee. 5167a95de68c093991047ed8d339479ccad51b88663David Blaikie if (N->getLocation().getAs<CallEnter>()) { 517dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks // Still use the index of the CallExpr. It's needed to create the callee 518dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks // StackFrameContext. 519dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks WList->enqueue(N, Block, Idx); 520dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks return; 521dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks } 522dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 523dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks // Do not create extra nodes. Move to the next CFG element. 5247a95de68c093991047ed8d339479ccad51b88663David Blaikie if (N->getLocation().getAs<PostInitializer>() || 5257a95de68c093991047ed8d339479ccad51b88663David Blaikie N->getLocation().getAs<PostImplicitCall>()) { 526dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks WList->enqueue(N, Block, Idx+1); 527dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks return; 528dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks } 529dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 5307a95de68c093991047ed8d339479ccad51b88663David Blaikie if (N->getLocation().getAs<EpsilonPoint>()) { 5315903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks WList->enqueue(N, Block, Idx); 5325903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks return; 5335903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks } 5345903a373db3d27794c90b25687e0dd6adb0e497dAnna Zaks 5359198c71a626e2f0d29d92152832f3e80f4af59b3Jordan Rose // At this point, we know we're processing a normal statement. 536fdf6a279c9a75c778eba382d9a156697092982a1David Blaikie CFGStmt CS = (*Block)[Idx].castAs<CFGStmt>(); 5379198c71a626e2f0d29d92152832f3e80f4af59b3Jordan Rose PostStmt Loc(CS.getStmt(), N->getLocationContext()); 538dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 539dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks if (Loc == N->getLocation()) { 540dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks // Note: 'N' should be a fresh node because otherwise it shouldn't be 541dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks // a member of Deferred. 542dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks WList->enqueue(N, Block, Idx+1); 543dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks return; 544dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks } 545dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 546dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks bool IsNew; 5476800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks ExplodedNode *Succ = G->getNode(Loc, N->getState(), false, &IsNew); 548dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks Succ->addPredecessor(N, *G); 549dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 550dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks if (IsNew) 551dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks WList->enqueue(Succ, Block, Idx+1); 552dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks} 553dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 5540b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna ZaksExplodedNode *CoreEngine::generateCallExitBeginNode(ExplodedNode *N) { 5550b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks // Create a CallExitBegin node and enqueue it. 5564d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks const StackFrameContext *LocCtx 5574d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks = cast<StackFrameContext>(N->getLocationContext()); 5584d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks 559bed28ac1d1463adca3ecf24fca5c30646fa9dbb2Sylvestre Ledru // Use the callee location context. 560852aa0d2c5d2d1faf2d77b5aa3c0848068a342c5Jordan Rose CallExitBegin Loc(LocCtx); 5614d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks 5624d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks bool isNew; 5636800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks ExplodedNode *Node = G->getNode(Loc, N->getState(), false, &isNew); 5644d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks Node->addPredecessor(N, *G); 5654d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks return isNew ? Node : 0; 5664d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks} 5674d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks 5684d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks 569dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaksvoid CoreEngine::enqueue(ExplodedNodeSet &Set) { 570dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks for (ExplodedNodeSet::iterator I = Set.begin(), 571dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks E = Set.end(); I != E; ++I) { 572a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks WList->enqueue(*I); 573a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks } 574a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks} 575a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks 576dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaksvoid CoreEngine::enqueue(ExplodedNodeSet &Set, 577dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks const CFGBlock *Block, unsigned Idx) { 578dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks for (ExplodedNodeSet::iterator I = Set.begin(), 579dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks E = Set.end(); I != E; ++I) { 580dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks enqueueStmtNode(*I, Block, Idx); 581dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks } 582dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks} 583dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 5844d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaksvoid CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set) { 5854d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks for (ExplodedNodeSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) { 5864d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks ExplodedNode *N = *I; 5870b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks // If we are in an inlined call, generate CallExitBegin node. 5884d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks if (N->getLocationContext()->getParent()) { 5890b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks N = generateCallExitBeginNode(N); 5904d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks if (N) 5914d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks WList->enqueue(N); 592638e2d31fceed041e7e16aada4188c94cb5797bbAnna Zaks } else { 5930b3ade86a1c60cf0c7b56aa238aff458eb7f5974Anna Zaks // TODO: We should run remove dead bindings here. 5944d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks G->addEndOfPath(N); 595638e2d31fceed041e7e16aada4188c94cb5797bbAnna Zaks NumPathsExplored++; 596638e2d31fceed041e7e16aada4188c94cb5797bbAnna Zaks } 5974d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks } 5984d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks} 5994d2ae4a70336dc2aa11389b34946be152bb454c9Anna Zaks 600dd7ddf2b2296f95e7591ca3f9791f0eb9a15ee42Anna Zaks 60199ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid NodeBuilder::anchor() { } 60299ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 603f05aac8472d8ed081a361a218fd14d59ddc91b85Anna ZaksExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, 6048bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef State, 605319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks ExplodedNode *FromN, 606319a9184d5ca9f77622b45ae15c08f6b9ce01621Anna Zaks bool MarkAsSink) { 6074e82d3cf6fd4c907265e3fa3aac0a835c35dc759Anna Zaks HasGeneratedNodes = true; 608f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks bool IsNew; 6096800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks ExplodedNode *N = C.Eng.G->getNode(Loc, State, MarkAsSink, &IsNew); 610a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks N->addPredecessor(FromN, *C.Eng.G); 6111aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks Frontier.erase(FromN); 6122d950b15b2b2b650b102ecf0c6b50b45e0cb6a8aAnna Zaks 6132d950b15b2b2b650b102ecf0c6b50b45e0cb6a8aAnna Zaks if (!IsNew) 6142d950b15b2b2b650b102ecf0c6b50b45e0cb6a8aAnna Zaks return 0; 615f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 6166800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks if (!MarkAsSink) 6171aae01a8308d2f8e31adab3f4d7ac35543aac680Anna Zaks Frontier.Add(N); 618f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 6192d950b15b2b2b650b102ecf0c6b50b45e0cb6a8aAnna Zaks return N; 620f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks} 621f05aac8472d8ed081a361a218fd14d59ddc91b85Anna Zaks 62299ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid NodeBuilderWithSinks::anchor() { } 62399ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 624aa0aeb1cbe117db68d35700cb3a34aace0f99b99Anna ZaksStmtNodeBuilder::~StmtNodeBuilder() { 625cca79db2ea94f71fb088f4b0f104cef8bedf8ff2Anna Zaks if (EnclosingBldr) 626cca79db2ea94f71fb088f4b0f104cef8bedf8ff2Anna Zaks for (ExplodedNodeSet::iterator I = Frontier.begin(), 627cca79db2ea94f71fb088f4b0f104cef8bedf8ff2Anna Zaks E = Frontier.end(); I != E; ++I ) 628cca79db2ea94f71fb088f4b0f104cef8bedf8ff2Anna Zaks EnclosingBldr->addNodes(*I); 629868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu} 630868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu 63199ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid BranchNodeBuilder::anchor() { } 63299ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 6338bef8238181a30e52dea380789a7e2d760eac532Ted KremenekExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, 634a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks bool branch, 635a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks ExplodedNode *NodePred) { 636520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek // If the branch has been marked infeasible we should not generate a node. 637520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (!isFeasible(branch)) 638520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek return NULL; 6391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 640a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks ProgramPoint Loc = BlockEdge(C.Block, branch ? DstT:DstF, 641a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks NodePred->getLocationContext()); 642a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); 643a19f4af7a94835ce4693bfe12d6270754e79eb56Anna Zaks return Succ; 6447d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek} 64571c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek 646c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 64718c66fdc3c4008d335885695fe36fb5353c5f672Ted KremenekIndirectGotoNodeBuilder::generateNode(const iterator &I, 6488bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef St, 6496800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink) { 650754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek bool IsNew; 6519c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 6526800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Pred->getLocationContext()), St, 6536800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks IsSink, &IsNew); 6545fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(Pred, *Eng.G); 6551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6566800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks if (!IsNew) 6576800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks return 0; 6581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6596800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks if (!IsSink) 6606800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Eng.WList->enqueue(Succ); 6611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6626800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks return Succ; 663754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek} 664daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 665daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 666c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 66718c66fdc3c4008d335885695fe36fb5353c5f672Ted KremenekSwitchNodeBuilder::generateCaseStmtNode(const iterator &I, 6688bef8238181a30e52dea380789a7e2d760eac532Ted Kremenek ProgramStateRef St) { 669daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 670daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek bool IsNew; 6719c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 6726800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Pred->getLocationContext()), St, 6736800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks false, &IsNew); 6745fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(Pred, *Eng.G); 6756800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks if (!IsNew) 6766800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks return 0; 6776800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks 6786800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Eng.WList->enqueue(Succ); 6796800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks return Succ; 680daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek} 681daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 682daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 683c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 6848bef8238181a30e52dea380789a7e2d760eac532Ted KremenekSwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, 6856800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks bool IsSink) { 686daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek // Get the block for the default case. 687e4c6675cccbaac991843def43072687bca50d989Ted Kremenek assert(Src->succ_rbegin() != Src->succ_rend()); 6889c378f705405d37f49795d5e915989de774fe11fTed Kremenek CFGBlock *DefaultBlock = *Src->succ_rbegin(); 6891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 690e4c6675cccbaac991843def43072687bca50d989Ted Kremenek // Sanity check for default blocks that are unreachable and not caught 691e4c6675cccbaac991843def43072687bca50d989Ted Kremenek // by earlier stages. 692e4c6675cccbaac991843def43072687bca50d989Ted Kremenek if (!DefaultBlock) 693e4c6675cccbaac991843def43072687bca50d989Ted Kremenek return NULL; 694e4c6675cccbaac991843def43072687bca50d989Ted Kremenek 695daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek bool IsNew; 6969c378f705405d37f49795d5e915989de774fe11fTed Kremenek ExplodedNode *Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock, 6976800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Pred->getLocationContext()), St, 6986800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks IsSink, &IsNew); 6995fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(Pred, *Eng.G); 7001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7016800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks if (!IsNew) 7026800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks return 0; 7031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7046800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks if (!IsSink) 7056800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks Eng.WList->enqueue(Succ); 7061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7076800ba622e4edf287801ac69c42c61e7e294b06bAnna Zaks return Succ; 708daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek} 709