diff options
-rw-r--r-- | include/clang/AST/CFG.h | 25 | ||||
-rw-r--r-- | include/clang/Analysis/FlowSensitive/DataflowSolver.h | 20 | ||||
-rw-r--r-- | include/clang/Analysis/PathSensitive/BugReporter.h | 2 | ||||
-rw-r--r-- | include/clang/Analysis/ProgramPoint.h | 153 | ||||
-rw-r--r-- | lib/AST/CFG.cpp | 58 | ||||
-rw-r--r-- | lib/Analysis/BugReporter.cpp | 7 | ||||
-rw-r--r-- | lib/Analysis/GRCoreEngine.cpp | 20 | ||||
-rw-r--r-- | lib/Analysis/GRExprEngine.cpp | 9 | ||||
-rw-r--r-- | lib/Analysis/ProgramPoint.cpp | 64 |
9 files changed, 117 insertions, 241 deletions
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<CFGBlock*,CFGBlock*> 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<CFGBlock*,CFGBlock*> that can - /// be used by BlockEdge to refer to edges that cannot be represented - /// by a single pointer. - const std::pair<CFGBlock*,CFGBlock*>* 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<forward_analysis_tag> { 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<backward_analysis_tag> { 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<void*,10> CachedErrors; + llvm::SmallSet<ProgramPoint,10> 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<uintptr_t,uintptr_t> Data; + +protected: + ProgramPoint(const void* P, Kind k) + : Data(reinterpret_cast<uintptr_t>(P), (uintptr_t) k) {} + + ProgramPoint(const void* P1, const void* P2) + : Data(reinterpret_cast<uintptr_t>(P1) | 0x1, + reinterpret_cast<uintptr_t>(P2)) {} + +protected: + void* getData1NoMask() const { + assert (getKind() != BlockEdgeKind); + return reinterpret_cast<void*>(Data.first); } - ProgramPoint() : Data(0) {} + void* getData1() const { + assert (getKind() == BlockEdgeKind); + return reinterpret_cast<void*>(Data.first & ~0x1); + } - void setRawData(const void* Ptr, Kind k) { - assert ((reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) & 0x7) == 0 - && "Address must have at least an 8-byte alignment."); - - Data = reinterpret_cast<uintptr_t>(const_cast<void*>(Ptr)) | k; + void* getData2() const { + assert (getKind() == BlockEdgeKind); + return reinterpret_cast<void*>(Data.second); } public: - unsigned getKind() const { return Data & 0x7; } - void* getRawPtr() const { return reinterpret_cast<void*>(Data & ~0x7); } - void* getRawData() const { return reinterpret_cast<void*>(Data); } + + uintptr_t getKind() const { + return Data.first & 0x1 ? (uintptr_t) BlockEdgeKind : Data.second; + } + + // For use with DenseMap. + unsigned getHashValue() const { + std::pair<void*,void*> P(reinterpret_cast<void*>(Data.first), + reinterpret_cast<void*>(Data.second)); + return llvm::DenseMapInfo<std::pair<void*,void*> >::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<void*>(Data.first)); + ID.AddPointer(reinterpret_cast<void*>(Data.second)); } }; @@ -65,7 +94,7 @@ public: BlockEntrance(const CFGBlock* B) : ProgramPoint(B, BlockEntranceKind) {} CFGBlock* getBlock() const { - return reinterpret_cast<CFGBlock*>(getRawPtr()); + return reinterpret_cast<CFGBlock*>(getData1NoMask()); } Stmt* getFirstStmt() const { @@ -83,7 +112,7 @@ public: BlockExit(const CFGBlock* B) : ProgramPoint(B, BlockExitKind) {} CFGBlock* getBlock() const { - return reinterpret_cast<CFGBlock*>(getRawPtr()); + return reinterpret_cast<CFGBlock*>(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<CFGBlock*,CFGBlock*> 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<CFGBlock*>(getData1()); + } + + CFGBlock* getDst() const { + return static_cast<CFGBlock*>(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<clang::ProgramPoint> { - static inline clang::ProgramPoint getEmptyKey() { - uintptr_t x = - reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; - - return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); - } - - static inline clang::ProgramPoint getTombstoneKey() { - uintptr_t x = - reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; - - return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); - } - - static unsigned getHashValue(const clang::ProgramPoint& Loc) { - return DenseMapInfo<void*>::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<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7; + return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x)); +} + +static inline clang::ProgramPoint getTombstoneKey() { + uintptr_t x = + reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7; + return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(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 @@ -1213,69 +1213,11 @@ unsigned CFG::getNumBlkExprs() { } //===----------------------------------------------------------------------===// -// Internal Block-Edge Set; used for modeling persistent <CFGBlock*,CFGBlock*> -// pairs for use with ProgramPoint. -//===----------------------------------------------------------------------===// - -typedef std::pair<CFGBlock*,CFGBlock*> BPairTy; - -namespace llvm { - template<> struct FoldingSetTrait<BPairTy*> { - static void Profile(const BPairTy* X, FoldingSetNodeID& profile) { - profile.AddPointer(X->first); - profile.AddPointer(X->second); - } - }; -} - -typedef llvm::FoldingSetNodeWrapper<BPairTy*> PersistPairTy; -typedef llvm::FoldingSet<PersistPairTy> BlkEdgeSetTy; - -const std::pair<CFGBlock*,CFGBlock*>* -CFG::getBlockEdgeImpl(const CFGBlock* B1, const CFGBlock* B2) { - - if (!BlkEdgeSet) - BlkEdgeSet = new BlkEdgeSetTy(); - - BlkEdgeSetTy* p = static_cast<BlkEdgeSetTy*>(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<BPairTy>::Alignment_LessEqual_8Bytes); - - // Allocate the pair, forcing an 8-byte alignment. - BPairTy* pair = (BPairTy*) Alloc.Allocate(sizeof(*pair), 8); - - new (pair) BPairTy(const_cast<CFGBlock*>(B1), - const_cast<CFGBlock*>(B2)); - - // Allocate the meta data to store the pair in the FoldingSet. - PersistPairTy* ppair = (PersistPairTy*) Alloc.Allocate<PersistPairTy>(); - new (ppair) PersistPairTy(pair); - - p->InsertNode(ppair, InsertPos); - - return pair; - } - - return V->getValue(); -} - -//===----------------------------------------------------------------------===// // Cleanup: CFG dstor. //===----------------------------------------------------------------------===// CFG::~CFG() { delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); - delete reinterpret_cast<BlkEdgeSetTy*>(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 <typename ITERATOR> static void AddSources(std::vector<GRExprEngine::NodeTy*>& Sources, ITERATOR I, ITERATOR E) { - llvm::SmallPtrSet<void*,10> CachedSources; + llvm::SmallSet<ProgramPoint,10> 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<CFGBlock*>(getRawPtr()); - - case BlockEdgeDstKind: - return *(reinterpret_cast<CFGBlock*>(getRawPtr())->pred_begin()); - - case BlockEdgeAuxKind: - return reinterpret_cast<BPair*>(getRawPtr())->first; - } -} - -CFGBlock* BlockEdge::getDst() const { - switch (getKind()) { - default: - assert (false && "Invalid BlockEdgeKind."); - return NULL; - - case BlockEdgeSrcKind: - return *(reinterpret_cast<CFGBlock*>(getRawPtr())->succ_begin()); - - case BlockEdgeDstKind: - return reinterpret_cast<CFGBlock*>(getRawPtr()); - - case BlockEdgeAuxKind: - return reinterpret_cast<BPair*>(getRawPtr())->second; - } -} |