(catching up) Really great work. Mostly minor comments inline.
On Aug 9, 2012, at 3:55 PM, Jordan Rose <[email protected]> wrote: > Author: jrose > Date: Thu Aug 9 17:55:51 2012 > New Revision: 161636 > > URL: http://llvm.org/viewvc/llvm-project?rev=161636&view=rev > Log: > [analyzer] Cluster bindings in RegionStore by base region. > > This should speed up activities that need to access bindings by cluster, > such as invalidation and dead-bindings cleaning. In some cases all we save > is the cost of building the region cluster map, but other times we can > actually avoid traversing the rest of the store. > > In casual testing, this produced a speedup of nearly 10% analyzing SQLite, > with /less/ memory used. > > Modified: > cfe/trunk/lib/StaticAnalyzer/Core/MemRegion.cpp > cfe/trunk/lib/StaticAnalyzer/Core/RegionStore.cpp > cfe/trunk/test/Analysis/ivars.m > > Modified: cfe/trunk/lib/StaticAnalyzer/Core/MemRegion.cpp > URL: > http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/MemRegion.cpp?rev=161636&r1=161635&r2=161636&view=diff > ============================================================================== > --- cfe/trunk/lib/StaticAnalyzer/Core/MemRegion.cpp (original) > +++ cfe/trunk/lib/StaticAnalyzer/Core/MemRegion.cpp Thu Aug 9 17:55:51 2012 > @@ -1052,10 +1052,17 @@ > case CXXThisRegionKind: > case StringRegionKind: > case VarRegionKind: > - case ObjCIvarRegionKind: > case CXXTempObjectRegionKind: > goto Finish; > > + case ObjCIvarRegionKind: > + // This is a little strange, but it's a compromise between > + // ObjCIvarRegions having unknown compile-time offsets (when using the > + // non-fragile runtime) and yet still being distinct, non-overlapping > + // regions. Thus we treat them as "like" base regions for the purposes > + // of computing offsets. > + goto Finish; > + This is unrelated. Please keep these in a separate commit. ... > } > } > } > @@ -414,14 +430,11 @@ > template <typename DERIVED> > class ClusterAnalysis { > protected: > - typedef BumpVector<BindingKey> RegionCluster; > - typedef llvm::DenseMap<const MemRegion *, RegionCluster *> ClusterMap; > - llvm::DenseMap<const RegionCluster*, unsigned> Visited; > - typedef SmallVector<std::pair<const MemRegion *, RegionCluster*>, 10> > - WorkList; > + typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> > ClusterMap; > + typedef SmallVector<const MemRegion *, 10> WorkList; > + > + llvm::SmallPtrSet<const ClusterBindings *, 16> Visited; Why the switch from a DenseMap to a SmallPtrSet? Did this show up for some reason as a performance issue? > > - BumpVectorContext BVC; > - ClusterMap ClusterM; > WorkList WL; > > RegionStoreManager &RM; > @@ -432,6 +445,10 @@ > > const bool includeGlobals; > > + const ClusterBindings *getCluster(const MemRegion *R) { > + return B.lookup(R); > + } > + > public: > ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr, > RegionBindings b, const bool includeGlobals) > @@ -441,59 +458,36 @@ > > RegionBindings getRegionBindings() const { return B; } > > - RegionCluster &AddToCluster(BindingKey K) { > - const MemRegion *R = K.getRegion(); > - const MemRegion *baseR = R->getBaseRegion(); > - RegionCluster &C = getCluster(baseR); > - C.push_back(K, BVC); > - static_cast<DERIVED*>(this)->VisitAddedToCluster(baseR, C); > - return C; > - } > - > bool isVisited(const MemRegion *R) { > - return (bool) Visited[&getCluster(R->getBaseRegion())]; > - } > - > - RegionCluster& getCluster(const MemRegion *R) { > - RegionCluster *&CRef = ClusterM[R]; > - if (!CRef) { > - void *Mem = BVC.getAllocator().template Allocate<RegionCluster>(); > - CRef = new (Mem) RegionCluster(BVC, 10); > - } > - return *CRef; > + return Visited.count(getCluster(R)); > } > > void GenerateClusters() { > - // Scan the entire set of bindings and make the region clusters. > + // Scan the entire set of bindings and record the region clusters. > for (RegionBindings::iterator RI = B.begin(), RE = B.end(); RI != RE; > ++RI){ > - RegionCluster &C = AddToCluster(RI.getKey()); > - if (const MemRegion *R = RI.getData().getAsRegion()) { > - // Generate a cluster, but don't add the region to the cluster > - // if there aren't any bindings. > - getCluster(R->getBaseRegion()); > - } > - if (includeGlobals) { > - const MemRegion *R = RI.getKey().getRegion(); > - if (isa<NonStaticGlobalSpaceRegion>(R->getMemorySpace())) > - AddToWorkList(R, C); > - } > + const MemRegion *Base = RI.getKey(); > + > + const ClusterBindings &Cluster = RI.getData(); > + assert(!Cluster.isEmpty() && "Empty clusters should be removed"); > + static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster); > + > + if (includeGlobals) > + if (isa<NonStaticGlobalSpaceRegion>(Base->getMemorySpace())) > + AddToWorkList(Base, &Cluster); > } > } > > - bool AddToWorkList(const MemRegion *R, RegionCluster &C) { > - if (unsigned &visited = Visited[&C]) > - return false; > - else > - visited = 1; > + bool AddToWorkList(const MemRegion *R, const ClusterBindings *C) { > + if (C) { > + if (Visited.count(C)) > + return false; > + Visited.insert(C); > + } If Visited was still a DenseMap this lookup-and-modify would require only one lookup, and a modify of the value in place. These are minor. The rest of the patch looks straightforward. Great work! _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
