Optimizations for Dependent Symbol tracking (as per Ted's code review for r137309):
1) Change SymbolDependTy map to keep pointers as data. And other small tweaks like making the DenseMap smaller 64->16 elements; remove removeSymbolDependencies() as it will probably not be used.
2) Do not mark dependents live more then once.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@137401 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
index dc3d15b..55ef111 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
@@ -91,7 +91,7 @@
};
typedef const SymbolData* SymbolRef;
-typedef llvm::SmallVector<SymbolRef, 1> SymbolRefSmallVectorTy;
+typedef llvm::SmallVector<SymbolRef, 2> SymbolRefSmallVectorTy;
/// A symbol representing the value of a MemRegion.
class SymbolRegionValue : public SymbolData {
@@ -358,7 +358,7 @@
class SymbolManager {
typedef llvm::FoldingSet<SymExpr> DataSetTy;
- typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy> SymbolDependTy;
+ typedef llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy*> SymbolDependTy;
DataSetTy DataSet;
/// Stores the extra dependencies between symbols: the data should be kept
@@ -372,7 +372,8 @@
public:
SymbolManager(ASTContext& ctx, BasicValueFactory &bv,
llvm::BumpPtrAllocator& bpalloc)
- : SymbolCounter(0), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
+ : SymbolDependencies(16), SymbolCounter(0),
+ BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
~SymbolManager();
@@ -423,9 +424,6 @@
/// The dependent symbol should stay alive as long as the primary is alive.
void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
- /// \brief Drop all user-added dependencies on the primary symbol.
- void removeSymbolDependencies(const SymbolRef Primary);
-
const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
ASTContext &getContext() { return Ctx; }
@@ -433,10 +431,16 @@
};
class SymbolReaper {
+ enum SymbolStatus {
+ NotProcessed,
+ HaveMarkedDependents
+ };
+
typedef llvm::DenseSet<SymbolRef> SymbolSetTy;
+ typedef llvm::DenseMap<SymbolRef, SymbolStatus> SymbolMapTy;
typedef llvm::DenseSet<const MemRegion *> RegionSetTy;
- SymbolSetTy TheLiving;
+ SymbolMapTy TheLiving;
SymbolSetTy MetadataInUse;
SymbolSetTy TheDead;
diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp
index b4a0d69..ba8504c 100644
--- a/lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -231,7 +231,13 @@
return R->getValueType();
}
-SymbolManager::~SymbolManager() {}
+SymbolManager::~SymbolManager() {
+ for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(),
+ E = SymbolDependencies.end(); I != E; ++I) {
+ delete I->second;
+ }
+
+}
bool SymbolManager::canSymbolicate(QualType T) {
T = T.getCanonicalType();
@@ -250,11 +256,15 @@
void SymbolManager::addSymbolDependency(const SymbolRef Primary,
const SymbolRef Dependent) {
- SymbolDependencies[Primary].push_back(Dependent);
-}
-
-void SymbolManager::removeSymbolDependencies(const SymbolRef Primary) {
- SymbolDependencies.erase(Primary);
+ SymbolDependTy::iterator I = SymbolDependencies.find(Primary);
+ SymbolRefSmallVectorTy *dependencies = 0;
+ if (I == SymbolDependencies.end()) {
+ dependencies = new SymbolRefSmallVectorTy();
+ SymbolDependencies[Primary] = dependencies;
+ } else {
+ dependencies = I->second;
+ }
+ dependencies->push_back(Dependent);
}
const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
@@ -262,20 +272,29 @@
SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
if (I == SymbolDependencies.end())
return 0;
- return &I->second;
+ return I->second;
}
void SymbolReaper::markDependentsLive(SymbolRef sym) {
+ // Do not mark dependents more then once.
+ SymbolMapTy::iterator LI = TheLiving.find(sym);
+ assert(LI != TheLiving.end() && "The primary symbol is not live.");
+ if (LI->second == HaveMarkedDependents)
+ return;
+ LI->second = HaveMarkedDependents;
+
if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(),
E = Deps->end(); I != E; ++I) {
+ if (TheLiving.find(*I) != TheLiving.end())
+ continue;
markLive(*I);
}
}
}
void SymbolReaper::markLive(SymbolRef sym) {
- TheLiving.insert(sym);
+ TheLiving[sym] = NotProcessed;
TheDead.erase(sym);
markDependentsLive(sym);
}
