From d452758bb6b59340528a26def9ecc24b329d4ecf Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Tue, 16 Sep 2008 18:44:52 +0000 Subject: [PATCH] ProgramPoint now takes the space of two pointers instead of one. This change was motivated because it became clear that the number of subclasses of ProgramPoint would expand and we ran out of bits to represent a pointer variant. As a plus of this change, BlockEdge program points can now be represented explicitly without using a cache of CFGBlock* pairs in CFG. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@56245 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/CFG.h | 25 +-- .../Analysis/FlowSensitive/DataflowSolver.h | 20 +-- .../Analysis/PathSensitive/BugReporter.h | 2 +- include/clang/Analysis/ProgramPoint.h | 153 ++++++++++-------- lib/AST/CFG.cpp | 58 ------- lib/Analysis/BugReporter.cpp | 7 +- lib/Analysis/GRCoreEngine.cpp | 20 +-- lib/Analysis/GRExprEngine.cpp | 9 +- lib/Analysis/ProgramPoint.cpp | 64 -------- 9 files changed, 117 insertions(+), 241 deletions(-) delete mode 100644 lib/Analysis/ProgramPoint.cpp diff --git a/include/clang/AST/CFG.h b/include/clang/AST/CFG.h index 1d82ee2da5..2f3183c533 100644 --- a/include/clang/AST/CFG.h +++ b/include/clang/AST/CFG.h @@ -284,7 +284,7 @@ public: //===--------------------------------------------------------------------===// CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0), - BlkExprMap(NULL), BlkEdgeSet(NULL) {}; + BlkExprMap(NULL) {}; ~CFG(); @@ -304,26 +304,9 @@ private: // It represents a map from Expr* to integers to record the set of // block-level expressions and their "statement number" in the CFG. void* BlkExprMap; - - /// BlkEdgeSet - An opaque pointer to prevent inclusion of FoldingSet.h. - /// The set contains std::pair objects that have - /// stable references for use by the 'BlockEdge' class. This set is intended - /// to be sparse, as it only contains edges whether both the source - /// and destination block have multiple successors/predecessors. - void* BlkEdgeSet; - - /// Alloc - An internal allocator used for BlkEdgeSet. - llvm::BumpPtrAllocator Alloc; - - friend class BlockEdge; - - /// getBlockEdgeImpl - Utility method used by the class BlockEdge. The CFG - /// stores a set of interned std::pair that can - /// be used by BlockEdge to refer to edges that cannot be represented - /// by a single pointer. - const std::pair* getBlockEdgeImpl(const CFGBlock* B1, - const CFGBlock* B2); - + + /// Alloc - An internal allocator. + llvm::BumpPtrAllocator Alloc; }; } // end namespace clang diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h index b7cb1f8a06..169417c3d2 100644 --- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h +++ b/include/clang/Analysis/FlowSensitive/DataflowSolver.h @@ -69,12 +69,12 @@ template <> struct ItrTraits { static StmtItr StmtBegin(const CFGBlock* B) { return B->begin(); } static StmtItr StmtEnd(const CFGBlock* B) { return B->end(); } - static BlockEdge PrevEdge(CFG& cfg, const CFGBlock* B, const CFGBlock* Prev) { - return BlockEdge(cfg,Prev,B); + static BlockEdge PrevEdge(const CFGBlock* B, const CFGBlock* Prev) { + return BlockEdge(Prev, B); } - static BlockEdge NextEdge(CFG& cfg, const CFGBlock* B, const CFGBlock* Next) { - return BlockEdge(cfg,B,Next); + static BlockEdge NextEdge(const CFGBlock* B, const CFGBlock* Next) { + return BlockEdge(B, Next); } }; @@ -92,12 +92,12 @@ template <> struct ItrTraits { static StmtItr StmtBegin(const CFGBlock* B) { return B->rbegin(); } static StmtItr StmtEnd(const CFGBlock* B) { return B->rend(); } - static BlockEdge PrevEdge(CFG& cfg, const CFGBlock* B, const CFGBlock* Prev) { - return BlockEdge(cfg,B,Prev); + static BlockEdge PrevEdge(const CFGBlock* B, const CFGBlock* Prev) { + return BlockEdge(B, Prev); } - static BlockEdge NextEdge(CFG& cfg, const CFGBlock* B, const CFGBlock* Next) { - return BlockEdge(cfg,Next,B); + static BlockEdge NextEdge(const CFGBlock* B, const CFGBlock* Next) { + return BlockEdge(Next, B); } }; } // end namespace dataflow @@ -237,7 +237,7 @@ private: for (PrevBItr I=ItrTraits::PrevBegin(B),E=ItrTraits::PrevEnd(B); I!=E; ++I){ typename EdgeDataMapTy::iterator EI = - M.find(ItrTraits::PrevEdge(cfg,B,*I)); + M.find(ItrTraits::PrevEdge(B, *I)); if (EI != M.end()) { if (firstMerge) { @@ -287,7 +287,7 @@ private: // forward/backward analysis respectively) void UpdateEdges(CFG& cfg, const CFGBlock* B, ValTy& V) { for (NextBItr I=ItrTraits::NextBegin(B), E=ItrTraits::NextEnd(B); I!=E; ++I) - UpdateEdgeValue(ItrTraits::NextEdge(cfg,B,*I),V,*I); + UpdateEdgeValue(ItrTraits::NextEdge(B, *I),V,*I); } /// UpdateEdgeValue - Update the value associated with a given edge. diff --git a/include/clang/Analysis/PathSensitive/BugReporter.h b/include/clang/Analysis/PathSensitive/BugReporter.h index dddc81cc40..0cf6567652 100644 --- a/include/clang/Analysis/PathSensitive/BugReporter.h +++ b/include/clang/Analysis/PathSensitive/BugReporter.h @@ -57,7 +57,7 @@ public: }; class BugTypeCacheLocation : public BugType { - llvm::SmallPtrSet CachedErrors; + llvm::SmallSet CachedErrors; public: BugTypeCacheLocation() {} virtual ~BugTypeCacheLocation() {} diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h index ecb4f742c7..0ea5365692 100644 --- a/include/clang/Analysis/ProgramPoint.h +++ b/include/clang/Analysis/ProgramPoint.h @@ -25,38 +25,67 @@ namespace clang { class ProgramPoint { public: - enum Kind { BlockEntranceKind=0, - PostStmtKind=1, PostLoadKind=2, PostPurgeDeadSymbolsKind=3, - BlockExitKind=4, BlockEdgeSrcKind=5, BlockEdgeDstKind=6, - BlockEdgeAuxKind=7 }; -protected: - uintptr_t Data; + enum Kind { BlockEdgeKind=0, BlockEntranceKind, BlockExitKind, + // Keep the following three together and in this order. + PostStmtKind, PostLoadKind, PostPurgeDeadSymbolsKind }; - ProgramPoint(const void* Ptr, Kind k) { - setRawData(Ptr, k); +private: + std::pair Data; + +protected: + ProgramPoint(const void* P, Kind k) + : Data(reinterpret_cast(P), (uintptr_t) k) {} + + ProgramPoint(const void* P1, const void* P2) + : Data(reinterpret_cast(P1) | 0x1, + reinterpret_cast(P2)) {} + +protected: + void* getData1NoMask() const { + assert (getKind() != BlockEdgeKind); + return reinterpret_cast(Data.first); } - ProgramPoint() : Data(0) {} + void* getData1() const { + assert (getKind() == BlockEdgeKind); + return reinterpret_cast(Data.first & ~0x1); + } - void setRawData(const void* Ptr, Kind k) { - assert ((reinterpret_cast(const_cast(Ptr)) & 0x7) == 0 - && "Address must have at least an 8-byte alignment."); - - Data = reinterpret_cast(const_cast(Ptr)) | k; + void* getData2() const { + assert (getKind() == BlockEdgeKind); + return reinterpret_cast(Data.second); } public: - unsigned getKind() const { return Data & 0x7; } - void* getRawPtr() const { return reinterpret_cast(Data & ~0x7); } - void* getRawData() const { return reinterpret_cast(Data); } + + uintptr_t getKind() const { + return Data.first & 0x1 ? (uintptr_t) BlockEdgeKind : Data.second; + } + + // For use with DenseMap. + unsigned getHashValue() const { + std::pair P(reinterpret_cast(Data.first), + reinterpret_cast(Data.second)); + return llvm::DenseMapInfo >::getHashValue(P); + } static bool classof(const ProgramPoint*) { return true; } - bool operator==(const ProgramPoint & RHS) const { return Data == RHS.Data; } - bool operator!=(const ProgramPoint& RHS) const { return Data != RHS.Data; } + + bool operator==(const ProgramPoint & RHS) const { + return Data == RHS.Data; + } + + bool operator!=(const ProgramPoint& RHS) const { + return Data != RHS.Data; + } + + bool operator<(const ProgramPoint& RHS) const { + return Data < RHS.Data; + } void Profile(llvm::FoldingSetNodeID& ID) const { - ID.AddInteger(getKind()); - ID.AddPointer(getRawPtr()); + ID.AddPointer(reinterpret_cast(Data.first)); + ID.AddPointer(reinterpret_cast(Data.second)); } }; @@ -65,7 +94,7 @@ public: BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {} CFGBlock* getBlock() const { - return reinterpret_cast(getRawPtr()); + return reinterpret_cast(getData1NoMask()); } Stmt* getFirstStmt() const { @@ -83,7 +112,7 @@ public: BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {} CFGBlock* getBlock() const { - return reinterpret_cast(getRawPtr()); + return reinterpret_cast(getData1NoMask()); } Stmt* getLastStmt() const { @@ -107,7 +136,7 @@ protected: public: PostStmt(const Stmt* S) : ProgramPoint(S, PostStmtKind) {} - Stmt* getStmt() const { return (Stmt*) getRawPtr(); } + Stmt* getStmt() const { return (Stmt*) getData1NoMask(); } static bool classof(const ProgramPoint* Location) { unsigned k = Location->getKind(); @@ -134,26 +163,22 @@ public: }; class BlockEdge : public ProgramPoint { - typedef std::pair BPair; public: - BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2); - - /// This ctor forces the BlockEdge to be constructed using an explicitly - /// allocated pair object that is stored in the CFG. This is usually - /// used to construct edges representing jumps using computed gotos. - BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2, bool) - : ProgramPoint(cfg.getBlockEdgeImpl(B1, B2), BlockEdgeAuxKind) {} - - - CFGBlock* getSrc() const; - CFGBlock* getDst() const; + BlockEdge(const CFGBlock* B1, const CFGBlock* B2) + : ProgramPoint(B1, B2) {} + + CFGBlock* getSrc() const { + return static_cast(getData1()); + } + + CFGBlock* getDst() const { + return static_cast(getData2()); + } static bool classof(const ProgramPoint* Location) { - unsigned k = Location->getKind(); - return k >= BlockEdgeSrcKind && k <= BlockEdgeAuxKind; + return Location->getKind() == BlockEdgeKind; } }; - } // end namespace clang @@ -163,32 +188,30 @@ namespace llvm { // Traits specialization for DenseMap template <> struct DenseMapInfo { - static inline clang::ProgramPoint getEmptyKey() { - uintptr_t x = - reinterpret_cast(DenseMapInfo::getEmptyKey()) & ~0x7; - - return clang::BlockEntrance(reinterpret_cast(x)); - } - - static inline clang::ProgramPoint getTombstoneKey() { - uintptr_t x = - reinterpret_cast(DenseMapInfo::getTombstoneKey()) & ~0x7; - - return clang::BlockEntrance(reinterpret_cast(x)); - } - - static unsigned getHashValue(const clang::ProgramPoint& Loc) { - return DenseMapInfo::getHashValue(Loc.getRawData()); - } - - static bool isEqual(const clang::ProgramPoint& L, - const clang::ProgramPoint& R) { - return L == R; - } - - static bool isPod() { - return true; - } +static inline clang::ProgramPoint getEmptyKey() { + uintptr_t x = + reinterpret_cast(DenseMapInfo::getEmptyKey()) & ~0x7; + return clang::BlockEntrance(reinterpret_cast(x)); +} + +static inline clang::ProgramPoint getTombstoneKey() { + uintptr_t x = + reinterpret_cast(DenseMapInfo::getTombstoneKey()) & ~0x7; + return clang::BlockEntrance(reinterpret_cast(x)); +} + +static unsigned getHashValue(const clang::ProgramPoint& Loc) { + return Loc.getHashValue(); +} + +static bool isEqual(const clang::ProgramPoint& L, + const clang::ProgramPoint& R) { + return L == R; +} + +static bool isPod() { + return true; +} }; } // end namespace llvm diff --git a/lib/AST/CFG.cpp b/lib/AST/CFG.cpp index 78c8dca423..b18f90497f 100644 --- a/lib/AST/CFG.cpp +++ b/lib/AST/CFG.cpp @@ -1212,70 +1212,12 @@ unsigned CFG::getNumBlkExprs() { } } -//===----------------------------------------------------------------------===// -// Internal Block-Edge Set; used for modeling persistent -// pairs for use with ProgramPoint. -//===----------------------------------------------------------------------===// - -typedef std::pair BPairTy; - -namespace llvm { - template<> struct FoldingSetTrait { - static void Profile(const BPairTy* X, FoldingSetNodeID& profile) { - profile.AddPointer(X->first); - profile.AddPointer(X->second); - } - }; -} - -typedef llvm::FoldingSetNodeWrapper PersistPairTy; -typedef llvm::FoldingSet BlkEdgeSetTy; - -const std::pair* -CFG::getBlockEdgeImpl(const CFGBlock* B1, const CFGBlock* B2) { - - if (!BlkEdgeSet) - BlkEdgeSet = new BlkEdgeSetTy(); - - BlkEdgeSetTy* p = static_cast(BlkEdgeSet); - - // Profile the edges. - llvm::FoldingSetNodeID profile; - void* InsertPos; - - profile.AddPointer(B1); - profile.AddPointer(B2); - - PersistPairTy* V = p->FindNodeOrInsertPos(profile, InsertPos); - - if (!V) { - assert (llvm::AlignOf::Alignment_LessEqual_8Bytes); - - // Allocate the pair, forcing an 8-byte alignment. - BPairTy* pair = (BPairTy*) Alloc.Allocate(sizeof(*pair), 8); - - new (pair) BPairTy(const_cast(B1), - const_cast(B2)); - - // Allocate the meta data to store the pair in the FoldingSet. - PersistPairTy* ppair = (PersistPairTy*) Alloc.Allocate(); - new (ppair) PersistPairTy(pair); - - p->InsertNode(ppair, InsertPos); - - return pair; - } - - return V->getValue(); -} - //===----------------------------------------------------------------------===// // Cleanup: CFG dstor. //===----------------------------------------------------------------------===// CFG::~CFG() { delete reinterpret_cast(BlkExprMap); - delete reinterpret_cast(BlkEdgeSet); } //===----------------------------------------------------------------------===// diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp index 7e3db7aba4..b163eea1b8 100644 --- a/lib/Analysis/BugReporter.cpp +++ b/lib/Analysis/BugReporter.cpp @@ -689,13 +689,10 @@ bool BugTypeCacheLocation::isCached(BugReport& R) { } bool BugTypeCacheLocation::isCached(ProgramPoint P) { - - void* p = P.getRawData(); - - if (CachedErrors.count(p)) + if (CachedErrors.count(P)) return true; - CachedErrors.insert(p); + CachedErrors.insert(P); return false; } diff --git a/lib/Analysis/GRCoreEngine.cpp b/lib/Analysis/GRCoreEngine.cpp index a7e1458e7a..84a8d5522d 100644 --- a/lib/Analysis/GRCoreEngine.cpp +++ b/lib/Analysis/GRCoreEngine.cpp @@ -69,7 +69,7 @@ bool GRCoreEngineImpl::ExecuteWorkList(unsigned Steps) { // Construct an edge representing the // starting location in the function. - BlockEdge StartLoc(getCFG(), Entry, Succ); + BlockEdge StartLoc(Entry, Succ); // Set the current block counter to being empty. WList->setBlockCounter(BCounterFactory.GetEmptyCounter()); @@ -230,7 +230,7 @@ void GRCoreEngineImpl::HandleBlockExit(CFGBlock * B, ExplodedNodeImpl* Pred) { assert (B->succ_size() == 1 && "Blocks with no terminator should have at most 1 successor."); - GenerateNode(BlockEdge(getCFG(),B,*(B->succ_begin())), Pred->State, Pred); + GenerateNode(BlockEdge(B, *(B->succ_begin())), Pred->State, Pred); } void GRCoreEngineImpl::HandleBranch(Expr* Cond, Stmt* Term, CFGBlock * B, @@ -350,8 +350,7 @@ ExplodedNodeImpl* GRBranchNodeBuilderImpl::generateNodeImpl(const void* State, bool IsNew; ExplodedNodeImpl* Succ = - Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src, branch ? DstT : DstF), - State, &IsNew); + Eng.G->getNodeImpl(BlockEdge(Src, branch ? DstT : DstF), State, &IsNew); Succ->addPredecessor(Pred); @@ -382,8 +381,7 @@ GRIndirectGotoNodeBuilderImpl::generateNodeImpl(const Iterator& I, bool IsNew; ExplodedNodeImpl* Succ = - Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src, I.getBlock(), true), - St, &IsNew); + Eng.G->getNodeImpl(BlockEdge(Src, I.getBlock()), St, &IsNew); Succ->addPredecessor(Pred); @@ -407,9 +405,8 @@ GRSwitchNodeBuilderImpl::generateCaseStmtNodeImpl(const Iterator& I, bool IsNew; - ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src, - I.getBlock()), - St, &IsNew); + ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Src, I.getBlock()), + St, &IsNew); Succ->addPredecessor(Pred); if (IsNew) { @@ -431,9 +428,8 @@ GRSwitchNodeBuilderImpl::generateDefaultCaseNodeImpl(const void* St, bool IsNew; - ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Eng.getCFG(), Src, - DefaultBlock), - St, &IsNew); + ExplodedNodeImpl* Succ = Eng.G->getNodeImpl(BlockEdge(Src, DefaultBlock), + St, &IsNew); Succ->addPredecessor(Pred); if (IsNew) { diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp index d8c0320d66..aa5ab6af7f 100644 --- a/lib/Analysis/GRExprEngine.cpp +++ b/lib/Analysis/GRExprEngine.cpp @@ -2324,17 +2324,16 @@ template static void AddSources(std::vector& Sources, ITERATOR I, ITERATOR E) { - llvm::SmallPtrSet CachedSources; + llvm::SmallSet CachedSources; for ( ; I != E; ++I ) { GRExprEngine::NodeTy* N = GetGraphNode(I); - void* p = N->getLocation().getRawData(); + ProgramPoint P = N->getLocation(); - if (CachedSources.count(p)) + if (CachedSources.count(P)) continue; - CachedSources.insert(p); - + CachedSources.insert(P); Sources.push_back(N); } } diff --git a/lib/Analysis/ProgramPoint.cpp b/lib/Analysis/ProgramPoint.cpp deleted file mode 100644 index d95680ff38..0000000000 --- a/lib/Analysis/ProgramPoint.cpp +++ /dev/null @@ -1,64 +0,0 @@ -//= ProgramPoint.cpp - Program Points for Path-Sensitive Analysis --*- C++ -*-// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements methods for subclasses of ProgramPoint. -// -//===----------------------------------------------------------------------===// - -#include "clang/AST/CFG.h" -#include "clang/Analysis/ProgramPoint.h" - -using namespace clang; - -BlockEdge::BlockEdge(CFG& cfg, const CFGBlock* B1, const CFGBlock* B2) { - if (B1->succ_size() == 1) { - assert (*(B1->succ_begin()) == B2); - setRawData(B1, BlockEdgeSrcKind); - } - else if (B2->pred_size() == 1) { - assert (*(B2->pred_begin()) == B1); - setRawData(B2, BlockEdgeDstKind); - } - else - setRawData(cfg.getBlockEdgeImpl(B1,B2), BlockEdgeAuxKind); -} - -CFGBlock* BlockEdge::getSrc() const { - switch (getKind()) { - default: - assert (false && "Invalid BlockEdgeKind."); - return NULL; - - case BlockEdgeSrcKind: - return reinterpret_cast(getRawPtr()); - - case BlockEdgeDstKind: - return *(reinterpret_cast(getRawPtr())->pred_begin()); - - case BlockEdgeAuxKind: - return reinterpret_cast(getRawPtr())->first; - } -} - -CFGBlock* BlockEdge::getDst() const { - switch (getKind()) { - default: - assert (false && "Invalid BlockEdgeKind."); - return NULL; - - case BlockEdgeSrcKind: - return *(reinterpret_cast(getRawPtr())->succ_begin()); - - case BlockEdgeDstKind: - return reinterpret_cast(getRawPtr()); - - case BlockEdgeAuxKind: - return reinterpret_cast(getRawPtr())->second; - } -} -- 2.40.0