aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--include/clang/AST/CFG.h25
-rw-r--r--include/clang/Analysis/FlowSensitive/DataflowSolver.h20
-rw-r--r--include/clang/Analysis/PathSensitive/BugReporter.h2
-rw-r--r--include/clang/Analysis/ProgramPoint.h153
-rw-r--r--lib/AST/CFG.cpp58
-rw-r--r--lib/Analysis/BugReporter.cpp7
-rw-r--r--lib/Analysis/GRCoreEngine.cpp20
-rw-r--r--lib/Analysis/GRExprEngine.cpp9
-rw-r--r--lib/Analysis/ProgramPoint.cpp64
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;
- }
-}