CoreEngine.cpp revision 868e78d59d2dfaf9cda511925e5a58f3a712db96
1af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek//==- GRCoreEngine.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 151309f9a3b225ea846e5822691c39a77423125505Ted Kremenek#include "clang/Checker/PathSensitive/GRCoreEngine.h" 161309f9a3b225ea846e5822691c39a77423125505Ted Kremenek#include "clang/Checker/PathSensitive/GRExprEngine.h" 17f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include "clang/AST/Expr.h" 18f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include "llvm/Support/Casting.h" 19f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include "llvm/ADT/DenseMap.h" 20f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek#include <vector> 21e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek#include <queue> 22f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 23f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekusing llvm::cast; 24f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekusing llvm::isa; 25f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekusing namespace clang; 26f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 27e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 28e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek// Worklist classes for exploration of reachable states. 29e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 30e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 31f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremeneknamespace { 32ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass DFS : public GRWorkList { 33f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek llvm::SmallVector<GRWorkListUnit,20> Stack; 34f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenekpublic: 35f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek virtual bool hasWork() const { 36f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return !Stack.empty(); 37f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 38f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 39f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek virtual void Enqueue(const GRWorkListUnit& U) { 40f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Stack.push_back(U); 41f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 42f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 43f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek virtual GRWorkListUnit Dequeue() { 44f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek assert (!Stack.empty()); 45f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek const GRWorkListUnit& U = Stack.back(); 46f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Stack.pop_back(); // This technically "invalidates" U, but we are fine. 47f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return U; 48f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 49f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek}; 501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 51ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass BFS : public GRWorkList { 528ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek std::queue<GRWorkListUnit> Queue; 538ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenekpublic: 548ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek virtual bool hasWork() const { 558ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek return !Queue.empty(); 568ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek } 571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 588ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek virtual void Enqueue(const GRWorkListUnit& U) { 598ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek Queue.push(U); 608ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek } 611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 628ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek virtual GRWorkListUnit Dequeue() { 638ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek // Don't use const reference. The subsequent pop_back() might make it 648ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek // unsafe. 651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump GRWorkListUnit U = Queue.front(); 668ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek Queue.pop(); 678ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek return U; 688ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek } 698ff59e832591eaa5f3be9885857e71bbcb3da77cTed Kremenek}; 701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 71f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} // end anonymous namespace 72f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 73ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek// Place the dstor for GRWorkList here because it contains virtual member 74ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek// functions, and we the code for the dstor generated in one compilation unit. 75ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed KremenekGRWorkList::~GRWorkList() {} 76ee98546b0d5f3439c4a590b0d7d1545af794a0ecTed Kremenek 778ff59e832591eaa5f3be9885857e71bbcb3da77cTed KremenekGRWorkList *GRWorkList::MakeDFS() { return new DFS(); } 788ff59e832591eaa5f3be9885857e71bbcb3da77cTed KremenekGRWorkList *GRWorkList::MakeBFS() { return new BFS(); } 79f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 80e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremeneknamespace { 81ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnam class BFSBlockDFSContents : public GRWorkList { 82e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek std::queue<GRWorkListUnit> Queue; 83e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek llvm::SmallVector<GRWorkListUnit,20> Stack; 84e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek public: 85e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek virtual bool hasWork() const { 86e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek return !Queue.empty() || !Stack.empty(); 87e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 89e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek virtual void Enqueue(const GRWorkListUnit& U) { 90e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek if (isa<BlockEntrance>(U.getNode()->getLocation())) 91e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek Queue.push(U); 92e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek else 93e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek Stack.push_back(U); 94e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 96e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek virtual GRWorkListUnit Dequeue() { 97e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek // Process all basic blocks to completion. 98e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek if (!Stack.empty()) { 99e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek const GRWorkListUnit& U = Stack.back(); 100e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek Stack.pop_back(); // This technically "invalidates" U, but we are fine. 101e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek return U; 102e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 1031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 104e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek assert(!Queue.empty()); 105e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek // Don't use const reference. The subsequent pop_back() might make it 106e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek // unsafe. 1071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump GRWorkListUnit U = Queue.front(); 108e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek Queue.pop(); 1091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return U; 110e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek } 111e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek }; 112e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek} // end anonymous namespace 113e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 114e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed KremenekGRWorkList* GRWorkList::MakeBFSBlockDFSContents() { 115e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek return new BFSBlockDFSContents(); 116e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek} 117e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 118e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 119e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek// Core analysis engine. 120e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek//===----------------------------------------------------------------------===// 121031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xuvoid GRCoreEngine::ProcessEndPath(GREndPathNodeBuilder& Builder) { 1220111f575b968e423dccae439e501225b8314b257Zhongxing Xu SubEngine.ProcessEndPath(Builder); 1230111f575b968e423dccae439e501225b8314b257Zhongxing Xu} 1240111f575b968e423dccae439e501225b8314b257Zhongxing Xu 125852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenekvoid GRCoreEngine::ProcessStmt(CFGElement E, GRStmtNodeBuilder& Builder) { 126852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek SubEngine.ProcessStmt(E, Builder); 1270111f575b968e423dccae439e501225b8314b257Zhongxing Xu} 1280111f575b968e423dccae439e501225b8314b257Zhongxing Xu 129d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xubool GRCoreEngine::ProcessBlockEntrance(CFGBlock* Blk, const ExplodedNode *Pred, 1301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump GRBlockCounter BC) { 131d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu return SubEngine.ProcessBlockEntrance(Blk, Pred, BC); 1320111f575b968e423dccae439e501225b8314b257Zhongxing Xu} 1330111f575b968e423dccae439e501225b8314b257Zhongxing Xu 1340111f575b968e423dccae439e501225b8314b257Zhongxing Xuvoid GRCoreEngine::ProcessBranch(Stmt* Condition, Stmt* Terminator, 135031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GRBranchNodeBuilder& Builder) { 1361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump SubEngine.ProcessBranch(Condition, Terminator, Builder); 1370111f575b968e423dccae439e501225b8314b257Zhongxing Xu} 138e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 139031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xuvoid GRCoreEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) { 1400111f575b968e423dccae439e501225b8314b257Zhongxing Xu SubEngine.ProcessIndirectGoto(Builder); 1410111f575b968e423dccae439e501225b8314b257Zhongxing Xu} 1420111f575b968e423dccae439e501225b8314b257Zhongxing Xu 143031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xuvoid GRCoreEngine::ProcessSwitch(GRSwitchNodeBuilder& Builder) { 1440111f575b968e423dccae439e501225b8314b257Zhongxing Xu SubEngine.ProcessSwitch(Builder); 1450111f575b968e423dccae439e501225b8314b257Zhongxing Xu} 146031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu 147102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorvoid GRCoreEngine::ProcessCallEnter(GRCallEnterNodeBuilder &Builder) { 148102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor SubEngine.ProcessCallEnter(Builder); 149102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor} 150102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 151102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorvoid GRCoreEngine::ProcessCallExit(GRCallExitNodeBuilder &Builder) { 152102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor SubEngine.ProcessCallExit(Builder); 153102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor} 154102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 155f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. 15625e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xubool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) { 1571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 158f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek if (G->num_roots() == 0) { // Initialize the analysis by constructing 159f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // the root if none exists. 1601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 161cc0255383f96a557c36923f602819bdb0cdd2761Zhongxing Xu CFGBlock* Entry = &(L->getCFG()->getEntry()); 1621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1631eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump assert (Entry->empty() && 164f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek "Entry block must be empty."); 1651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 166f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek assert (Entry->succ_size() == 1 && 167f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek "Entry block must have 1 successor."); 1681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 169f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Get the solitary successor. 1701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump CFGBlock* Succ = *(Entry->succ_begin()); 1711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 172f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Construct an edge representing the 173f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // starting location in the function. 17425e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu BlockEdge StartLoc(Entry, Succ, L); 1751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1768e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Set the current block counter to being empty. 1778e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); 1781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 179f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Generate the root. 18017fd8632dcda97022a51effc24060eacdad9dbe0Zhongxing Xu GenerateNode(StartLoc, getInitialState(L), 0); 181f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 1821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 183f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek while (Steps && WList->hasWork()) { 184f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek --Steps; 185f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek const GRWorkListUnit& WU = WList->Dequeue(); 1861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1878e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Set the current block counter. 1888e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek WList->setBlockCounter(WU.getBlockCounter()); 1898e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek 1908e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Retrieve the node. 191c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Node = WU.getNode(); 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 193f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Dispatch on the location type. 194f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek switch (Node->getLocation().getKind()) { 195e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek case ProgramPoint::BlockEdgeKind: 196f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node); 197f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek break; 1981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 199f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek case ProgramPoint::BlockEntranceKind: 200f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node); 201f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek break; 2021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 203f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek case ProgramPoint::BlockExitKind: 204425c08c53ccbfb84e52129406b259ec59da22e64Ted Kremenek assert (false && "BlockExit location never occur in forward analysis."); 205f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek break; 206e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek 207102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor case ProgramPoint::CallEnterKind: 208102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor HandleCallEnter(cast<CallEnter>(Node->getLocation()), WU.getBlock(), 209102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor WU.getIndex(), Node); 210102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor break; 211102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 212102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor case ProgramPoint::CallExitKind: 213102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor HandleCallExit(cast<CallExit>(Node->getLocation()), Node); 214102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor break; 215102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 216e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek default: 217e1efd4de8685e0785daf9cab227f7a21cfc9c80bTed Kremenek assert(isa<PostStmt>(Node->getLocation())); 218f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(), 219f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek WU.getIndex(), Node); 2201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump break; 221f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 222f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 2231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 224f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return WList->hasWork(); 225f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 226f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 227102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorvoid GRCoreEngine::HandleCallEnter(const CallEnter &L, const CFGBlock *Block, 228102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor unsigned Index, ExplodedNode *Pred) { 229102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor GRCallEnterNodeBuilder Builder(*this, Pred, L.getCallExpr(), L.getCallee(), 230102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Block, Index); 231102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ProcessCallEnter(Builder); 232102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor} 233102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 234102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorvoid GRCoreEngine::HandleCallExit(const CallExit &L, ExplodedNode *Pred) { 235102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor GRCallExitNodeBuilder Builder(*this, Pred); 236102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ProcessCallExit(Builder); 237102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor} 2380111f575b968e423dccae439e501225b8314b257Zhongxing Xu 2390111f575b968e423dccae439e501225b8314b257Zhongxing Xuvoid GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) { 2401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 241f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek CFGBlock* Blk = L.getDst(); 2421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Check if we are entering the EXIT block. 244cb74d720b89b68bb2ecf2827d0e2eb66d236ab85Zhongxing Xu if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { 2451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 246cb74d720b89b68bb2ecf2827d0e2eb66d236ab85Zhongxing Xu assert (L.getLocationContext()->getCFG()->getExit().size() == 0 247cb48b9c9c3c95f2650b74530264c288d1f58c73cTed Kremenek && "EXIT block cannot contain Stmts."); 248f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 24911062b118476368fa5b294954713e5df97d8599fTed Kremenek // Process the final state transition. 250031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GREndPathNodeBuilder Builder(Blk, Pred, this); 25111062b118476368fa5b294954713e5df97d8599fTed Kremenek ProcessEndPath(Builder); 252f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 253f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // This path is done. Don't enqueue any more nodes. 254f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return; 255f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 2566a6719a3a11087b48d9f1a4eb08b3bd43cb05a65Ted Kremenek 2576a6719a3a11087b48d9f1a4eb08b3bd43cb05a65Ted Kremenek // FIXME: Should we allow ProcessBlockEntrance to also manipulate state? 2581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 259d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu if (ProcessBlockEntrance(Blk, Pred, WList->getBlockCounter())) 26025e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), Pred->State, Pred); 261f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 262f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 2630111f575b968e423dccae439e501225b8314b257Zhongxing Xuvoid GRCoreEngine::HandleBlockEntrance(const BlockEntrance& L, 264031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* Pred) { 2651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2668e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek // Increment the block counter. 2678e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek GRBlockCounter Counter = WList->getBlockCounter(); 268d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Counter = BCounterFactory.IncrementCount(Counter, 269d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu Pred->getLocationContext()->getCurrentStackFrame(), 270d9e0c0fc47d5881a609ec34372d554e3652db66cZhongxing Xu L.getBlock()->getBlockID()); 2718e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek WList->setBlockCounter(Counter); 2721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // Process the entrance of the block. 274852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek if (CFGElement E = L.getFirstElement()) { 2751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this, 276031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu SubEngine.getStateManager()); 277852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek ProcessStmt(E, Builder); 278f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 2791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump else 280425c08c53ccbfb84e52129406b259ec59da22e64Ted Kremenek HandleBlockExit(L.getBlock(), Pred); 281f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 282f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 2830111f575b968e423dccae439e501225b8314b257Zhongxing Xuvoid GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* Pred) { 2841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2857d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek if (Stmt* Term = B->getTerminator()) { 2867d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek switch (Term->getStmtClass()) { 2877d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek default: 2887d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek assert(false && "Analysis for this terminator not implemented."); 2897d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek break; 2901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 291f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek case Stmt::BinaryOperatorClass: // '&&' and '||' 292f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred); 293f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 2941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 295f233d48cfc513b045e2c2cfca5c175220fbd0a82Ted Kremenek case Stmt::ConditionalOperatorClass: 296f233d48cfc513b045e2c2cfca5c175220fbd0a82Ted Kremenek HandleBranch(cast<ConditionalOperator>(Term)->getCond(), Term, B, Pred); 297f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 2981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 299f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek // FIXME: Use constant-folding in CFG construction to simplify this 300f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek // case. 3011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 302f233d48cfc513b045e2c2cfca5c175220fbd0a82Ted Kremenek case Stmt::ChooseExprClass: 303f233d48cfc513b045e2c2cfca5c175220fbd0a82Ted Kremenek HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred); 304f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 306f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek case Stmt::DoStmtClass: 307f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred); 308f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3107d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek case Stmt::ForStmtClass: 3117d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred); 312f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 314a58e833c81a95e76c3a96fc982810d148537531bTed Kremenek case Stmt::ContinueStmtClass: 315a58e833c81a95e76c3a96fc982810d148537531bTed Kremenek case Stmt::BreakStmtClass: 3161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump case Stmt::GotoStmtClass: 3177d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek break; 3181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 319f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek case Stmt::IfStmtClass: 320f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred); 321f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 323754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek case Stmt::IndirectGotoStmtClass: { 324754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek // Only 1 successor: the indirect goto dispatch block. 325754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek assert (B->succ_size() == 1); 3261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 327031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GRIndirectGotoNodeBuilder 328754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), 329754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek *(B->succ_begin()), this); 3301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 331754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek ProcessIndirectGoto(builder); 332754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek return; 333754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek } 3341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 335af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek case Stmt::ObjCForCollectionStmtClass: { 336af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // In the case of ObjCForCollectionStmt, it appears twice in a CFG: 337af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // 338af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // (1) inside a basic block, which represents the binding of the 339af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // 'element' variable to a value. 340af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // (2) in a terminator, which represents the branch. 341af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // 342af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // For (1), subengines will bind a value (i.e., 0 or 1) indicating 343af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // whether or not collection contains any more elements. We cannot 344af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // just test to see if the element is nil because a container can 345af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek // contain nil elements. 346af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek HandleBranch(Term, Term, B, Pred); 347af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek return; 348af3374187c47acea45706eab6744be6b1c66a856Ted Kremenek } 3491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 350daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek case Stmt::SwitchStmtClass: { 351031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GRSwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), 352031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu this); 3531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 354daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek ProcessSwitch(builder); 355daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return; 356daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 3571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3587d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek case Stmt::WhileStmtClass: 3597d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred); 360f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek return; 3617d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek } 3627d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek } 363f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek 364f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek assert (B->succ_size() == 1 && 365f81086940024c8fd1c6497800386e88fd313a3d3Ted Kremenek "Blocks with no terminator should have at most 1 successor."); 3661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()), 36825e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu Pred->State, Pred); 369f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 370f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 3710111f575b968e423dccae439e501225b8314b257Zhongxing Xuvoid GRCoreEngine::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B, 3720111f575b968e423dccae439e501225b8314b257Zhongxing Xu ExplodedNode* Pred) { 3737d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek assert (B->succ_size() == 2); 3747d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek 375031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GRBranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1), 376031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu Pred, this); 3771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3787d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek ProcessBranch(Cond, Term, Builder); 3797d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek} 3807d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek 3810111f575b968e423dccae439e501225b8314b257Zhongxing Xuvoid GRCoreEngine::HandlePostStmt(const PostStmt& L, CFGBlock* B, 382c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu unsigned StmtIdx, ExplodedNode* Pred) { 3831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 384f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek assert (!B->empty()); 385f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 386425c08c53ccbfb84e52129406b259ec59da22e64Ted Kremenek if (StmtIdx == B->size()) 387425c08c53ccbfb84e52129406b259ec59da22e64Ted Kremenek HandleBlockExit(B, Pred); 388f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek else { 3891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump GRStmtNodeBuilder Builder(B, StmtIdx, Pred, this, 390031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu SubEngine.getStateManager()); 391160760e6326cf525bc48adf7fa1d414a049ba1f0Ted Kremenek ProcessStmt((*B)[StmtIdx], Builder); 392f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 393f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 394f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 395f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek/// GenerateNode - Utility method to generate nodes, hook up successors, 396f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek/// and add nodes to the worklist. 3971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpvoid GRCoreEngine::GenerateNode(const ProgramPoint& Loc, 3980111f575b968e423dccae439e501225b8314b257Zhongxing Xu const GRState* State, ExplodedNode* Pred) { 3991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 400f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek bool IsNew; 40138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu ExplodedNode* Node = G->getNode(Loc, State, &IsNew); 4021eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (Pred) 4045fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Node->addPredecessor(Pred, *G); // Link 'Node' with its predecessor. 405f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek else { 406f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek assert (IsNew); 407f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek G->addRoot(Node); // 'Node' has no predecessor. Make it a root. 408f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 4091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 410f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Only add 'Node' to the worklist if it was freshly generated. 4118e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek if (IsNew) WList->Enqueue(Node); 412f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 413f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 414031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGRStmtNodeBuilder::GRStmtNodeBuilder(CFGBlock* b, unsigned idx, 415031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* N, GRCoreEngine* e, 416031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu GRStateManager &mgr) 41725108a5d52a302d9319099001ea50e7c684669a3Zhongxing Xu : Eng(*e), B(*b), Idx(idx), Pred(N), Mgr(mgr), Auditor(0), 418031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu PurgingDeadSymbols(false), BuildSinks(false), HasGeneratedNode(false), 419031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu PointKind(ProgramPoint::PostStmtKind), Tag(0) { 420f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Deferred.insert(N); 42125108a5d52a302d9319099001ea50e7c684669a3Zhongxing Xu CleanedState = Pred->getState(); 422f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 423f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 424031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGRStmtNodeBuilder::~GRStmtNodeBuilder() { 425f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 426b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek if (!(*I)->isSink()) 427f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek GenerateAutoTransition(*I); 428f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 429f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 430031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xuvoid GRStmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) { 431b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek assert (!N->isSink()); 4321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 433102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Check if this node entered a callee. 434102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor if (isa<CallEnter>(N->getLocation())) { 435102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Still use the index of the CallExpr. It's needed to create the callee 436102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // StackFrameContext. 437102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Eng.WList->Enqueue(N, B, Idx); 438102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor return; 439102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 440102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 44125e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu PostStmt Loc(getStmt(), N->getLocationContext()); 4421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 443f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek if (Loc == N->getLocation()) { 444f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // Note: 'N' should be a fresh node because otherwise it shouldn't be 445f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek // a member of Deferred. 446f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Eng.WList->Enqueue(N, B, Idx+1); 447f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return; 448f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 4491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 450f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek bool IsNew; 45138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew); 4525fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(N, *Eng.G); 453f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 454f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek if (IsNew) 455f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Eng.WList->Enqueue(Succ, B, Idx+1); 456f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 457f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek 458868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing XuExplodedNode* GRStmtNodeBuilder::MakeNode(ExplodedNodeSet& Dst, Stmt* S, 459868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu ExplodedNode* Pred, const GRState* St, 460868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu ProgramPoint::Kind K) { 461868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu const GRState* PredState = GetState(Pred); 462868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu 463868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu // If the state hasn't changed, don't generate a new node. 464868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu if (!BuildSinks && St == PredState && Auditor == 0) { 465868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu Dst.Add(Pred); 466868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu return NULL; 467868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu } 468868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu 469868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu ExplodedNode* N = generateNode(S, St, Pred, K); 470868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu 471868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu if (N) { 472868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu if (BuildSinks) 473868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu N->markAsSink(); 474868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu else { 475868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu if (Auditor && Auditor->Audit(N, Mgr)) 476868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu N->markAsSink(); 477868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu 478868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu Dst.Add(N); 479868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu } 480868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu } 481868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu 482868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu return N; 483868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu} 484868e78d59d2dfaf9cda511925e5a58f3a712db96Zhongxing Xu 485b4b817d704287836b52b34369009e682f208aa2bTed Kremenekstatic ProgramPoint GetProgramPoint(const Stmt *S, ProgramPoint::Kind K, 486b4b817d704287836b52b34369009e682f208aa2bTed Kremenek const LocationContext *LC, const void *tag){ 487331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek switch (K) { 488331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek default: 489b4b817d704287836b52b34369009e682f208aa2bTed Kremenek assert(false && "Unhandled ProgramPoint kind"); 490b4b817d704287836b52b34369009e682f208aa2bTed Kremenek case ProgramPoint::PreStmtKind: 491b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PreStmt(S, LC, tag); 492331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek case ProgramPoint::PostStmtKind: 493b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PostStmt(S, LC, tag); 494b4b817d704287836b52b34369009e682f208aa2bTed Kremenek case ProgramPoint::PreLoadKind: 495b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PreLoad(S, LC, tag); 496331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek case ProgramPoint::PostLoadKind: 497b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PostLoad(S, LC, tag); 498b4b817d704287836b52b34369009e682f208aa2bTed Kremenek case ProgramPoint::PreStoreKind: 499b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PreStore(S, LC, tag); 500bf4e419d996bf42e4933cada610d973a0fcc40ebTed Kremenek case ProgramPoint::PostStoreKind: 501b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PostStore(S, LC, tag); 5027090d5465de7ca620da16211cf886edf1edc1f1fTed Kremenek case ProgramPoint::PostLValueKind: 503b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PostLValue(S, LC, tag); 504331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek case ProgramPoint::PostPurgeDeadSymbolsKind: 505b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return PostPurgeDeadSymbols(S, LC, tag); 506331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek } 507331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek} 508331b0ac44b9eb0ffcba66b4f3f3f9adb27c2434fTed Kremenek 509c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 510b4b817d704287836b52b34369009e682f208aa2bTed KremenekGRStmtNodeBuilder::generateNodeInternal(const Stmt* S, const GRState* state, 511c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred, 5121670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek ProgramPoint::Kind K, 5131670e403c48f3af4fceff3f6773a0e1cfc6c4eb3Ted Kremenek const void *tag) { 514b4b817d704287836b52b34369009e682f208aa2bTed Kremenek 515cb74d720b89b68bb2ecf2827d0e2eb66d236ab85Zhongxing Xu const ProgramPoint &L = GetProgramPoint(S, K, Pred->getLocationContext(),tag); 516b4b817d704287836b52b34369009e682f208aa2bTed Kremenek return generateNodeInternal(L, state, Pred); 51758e899b336c63fa25d4cc8986d97a40933cded9bTed Kremenek} 51858e899b336c63fa25d4cc8986d97a40933cded9bTed Kremenek 519c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 520031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGRStmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc, 52138b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu const GRState* State, 522c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Pred) { 523f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek bool IsNew; 52438b02b912e1a55c912f603c4369431264d36a381Zhongxing Xu ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew); 5255fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek N->addPredecessor(Pred, *Eng.G); 526f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Deferred.erase(Pred); 5271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 528f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek if (IsNew) { 529f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek Deferred.insert(N); 530f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek return N; 531f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek } 5321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return NULL; 534f24af5bc2e01ca8e7396ed997378a77fddfa521eTed Kremenek} 5357d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek 536031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuExplodedNode* GRBranchNodeBuilder::generateNode(const GRState* State, 537031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool branch) { 5381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 539520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek // If the branch has been marked infeasible we should not generate a node. 540520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (!isFeasible(branch)) 541520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek return NULL; 5421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5437d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek bool IsNew; 5441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 545c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing Xu ExplodedNode* Succ = 54625e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu Eng.G->getNode(BlockEdge(Src,branch ? DstT:DstF,Pred->getLocationContext()), 54725e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu State, &IsNew); 5481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5495fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(Pred, *Eng.G); 5501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 551520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek if (branch) 552520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek GeneratedTrue = true; 553520035439d7133064325c4df6378c5a8f2f05539Ted Kremenek else 5541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump GeneratedFalse = true; 5551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 556b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek if (IsNew) { 5573b4f6702860208692f6ef28401e68de4e3ff9af9Ted Kremenek Deferred.push_back(Succ); 558b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return Succ; 559b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek } 5601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 561b38911f16b4943548db6a3695fc6ae23070b25d2Ted Kremenek return NULL; 5627d7fe6d539b3bdb1701835223cca306c325614a7Ted Kremenek} 56371c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek 564031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGRBranchNodeBuilder::~GRBranchNodeBuilder() { 565031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu if (!GeneratedTrue) generateNode(Pred->State, true); 566031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu if (!GeneratedFalse) generateNode(Pred->State, false); 5671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5683b4f6702860208692f6ef28401e68de4e3ff9af9Ted Kremenek for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I) 5698e49dd6e7e73b275a74338a5127a524f0765303cTed Kremenek if (!(*I)->isSink()) Eng.WList->Enqueue(*I); 57071c29bdc931bc49644c581ec7d698f0dbf01a0aaTed Kremenek} 571754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 572754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek 573c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 574031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGRIndirectGotoNodeBuilder::generateNode(const iterator& I, const GRState* St, 575031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu bool isSink) { 576754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek bool IsNew; 5771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 57925e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu Pred->getLocationContext()), St, &IsNew); 5801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5815fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(Pred, *Eng.G); 5821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 583754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek if (IsNew) { 5841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 585754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek if (isSink) 586754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek Succ->markAsSink(); 587754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek else 588754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek Eng.WList->Enqueue(Succ); 5891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 590754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek return Succ; 591754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek } 5921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 593754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek return NULL; 594754607e7cff2d902d9af8b771409449fb2f8d2bfTed Kremenek} 595daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 596daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 597c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 598031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGRSwitchNodeBuilder::generateCaseStmtNode(const iterator& I, const GRState* St){ 599daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 600daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek bool IsNew; 6011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 60225e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(), 60325e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu Pred->getLocationContext()), St, &IsNew); 6045fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(Pred, *Eng.G); 6051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 606daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek if (IsNew) { 607daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek Eng.WList->Enqueue(Succ); 608daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return Succ; 609daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 6101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 611daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return NULL; 612daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek} 613daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 614daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek 615c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 616031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGRSwitchNodeBuilder::generateDefaultCaseNode(const GRState* St, bool isSink) { 6171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 618daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek // Get the block for the default case. 619daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek assert (Src->succ_rbegin() != Src->succ_rend()); 620daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek CFGBlock* DefaultBlock = *Src->succ_rbegin(); 6211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 622daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek bool IsNew; 6231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 62425e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock, 62525e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu Pred->getLocationContext()), St, &IsNew); 6265fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Succ->addPredecessor(Pred, *Eng.G); 6271eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 628daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek if (IsNew) { 629daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek if (isSink) 630daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek Succ->markAsSink(); 631daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek else 632daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek Eng.WList->Enqueue(Succ); 6331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 634daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return Succ; 635daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek } 6361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 637daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek return NULL; 638daeb9a7376830d637e02b5bc51faf4750a7bce70Ted Kremenek} 63911062b118476368fa5b294954713e5df97d8599fTed Kremenek 640031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGREndPathNodeBuilder::~GREndPathNodeBuilder() { 64111062b118476368fa5b294954713e5df97d8599fTed Kremenek // Auto-generate an EOP node if one has not been generated. 642102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor if (!HasGeneratedNode) { 643102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // If we are in an inlined call, generate CallExit node. 644102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor if (Pred->getLocationContext()->getParent()) 645102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor GenerateCallExitNode(Pred->State); 646102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor else 647102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor generateNode(Pred->State); 648102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor } 64911062b118476368fa5b294954713e5df97d8599fTed Kremenek} 65011062b118476368fa5b294954713e5df97d8599fTed Kremenek 651c5619d901a68dc27a9e310a6a831f03efebcd950Zhongxing XuExplodedNode* 652031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing XuGREndPathNodeBuilder::generateNode(const GRState* State, const void *tag, 653031ccc0555a82afc2e8afe29e19dd57ff204e2deZhongxing Xu ExplodedNode* P) { 6541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump HasGeneratedNode = true; 65511062b118476368fa5b294954713e5df97d8599fTed Kremenek bool IsNew; 6561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B, 65825e695b2d574d919cc1bbddf3a2efe073d449b1cZhongxing Xu Pred->getLocationContext(), tag), State, &IsNew); 6591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6605fe4d9deb543a19f557e3d85c5f33867af97cd96Ted Kremenek Node->addPredecessor(P ? P : Pred, *Eng.G); 6611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 66211062b118476368fa5b294954713e5df97d8599fTed Kremenek if (IsNew) { 66311062b118476368fa5b294954713e5df97d8599fTed Kremenek Eng.G->addEndOfPath(Node); 6644f28515992dfd851ce482803d8f3174d667e7cdbTed Kremenek return Node; 66511062b118476368fa5b294954713e5df97d8599fTed Kremenek } 6661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6674f28515992dfd851ce482803d8f3174d667e7cdbTed Kremenek return NULL; 66811062b118476368fa5b294954713e5df97d8599fTed Kremenek} 669102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 670102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorvoid GREndPathNodeBuilder::GenerateCallExitNode(const GRState *state) { 671102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor HasGeneratedNode = true; 672102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Create a CallExit node and enqueue it. 673102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const StackFrameContext *LocCtx 674102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor = cast<StackFrameContext>(Pred->getLocationContext()); 675102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const Stmt *CE = LocCtx->getCallSite(); 676102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 677102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Use the the callee location context. 678102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor CallExit Loc(CE, LocCtx); 679102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 680102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor bool isNew; 681102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); 682102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Node->addPredecessor(Pred, *Eng.G); 683102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 684102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor if (isNew) 685102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Eng.WList->Enqueue(Node); 686102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor} 687102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 688102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 689102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorvoid GRCallEnterNodeBuilder::GenerateNode(const GRState *state, 690102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const LocationContext *LocCtx) { 691102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Get the callee entry block. 692102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *Entry = &(LocCtx->getCFG()->getEntry()); 693102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor assert(Entry->empty()); 694102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor assert(Entry->succ_size() == 1); 695102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 696102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Get the solitary successor. 697102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const CFGBlock *SuccB = *(Entry->succ_begin()); 698102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 699102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Construct an edge representing the starting location in the callee. 700102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor BlockEdge Loc(Entry, SuccB, LocCtx); 701102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 702102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor bool isNew; 703102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); 704102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G); 705102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 706102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor if (isNew) 707102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Eng.WList->Enqueue(Node); 708102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor} 709102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 710102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregorvoid GRCallExitNodeBuilder::GenerateNode(const GRState *state) { 711102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor // Get the callee's location context. 712102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor const StackFrameContext *LocCtx 713102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor = cast<StackFrameContext>(Pred->getLocationContext()); 714102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor 715102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor PostStmt Loc(LocCtx->getCallSite(), LocCtx->getParent()); 716102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor bool isNew; 717102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew); 718102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G); 719102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor if (isNew) 720102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor Eng.WList->Enqueue(Node, *const_cast<CFGBlock*>(LocCtx->getCallSiteBlock()), 721102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor LocCtx->getIndex() + 1); 722102acd5369bbb17c0d6ab868af376671acff7a93Douglas Gregor} 723