[LVI] Use DenseMap::find_as in LazyValueInfo.

[jlebar]

Summary

This lets us avoid creating and destroying a CallbackVH every time we
check the cache.

This is good for a 2% e2e speedup when compiling one of the large Eigen
tests at -O3.

FTR, I tried making the ValueCache hashtable one-level -- i.e., mapping
a pair (Value*, BasicBlock*) to a lattice value, and that didn't seem to
provide any additional improvement. Saving a word in LVILatticeVal by
merging the Tag and Val fields also didn't yield a speedup.

[rnk]

lib/Analysis/LazyValueInfo.cpp

417–418 ↗

(On Diff #62599)

This type is probably too large to use with DenseMap. I would expect that the keys would end up spaced out in memory, making lookup more expensive. Maybe try using a separate allocation for the value like this:

struct ValueCacheEntryTy {
  LVIValueHandle Handle;
  SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BBs;
};
DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;

On the other hand, maybe your 2% win is from avoiding separate allocation overhead. This is probably worth a quick benchmark, though.

[jlebar]

Use smaller values in the DenseMap.

Doesn't make a difference in my profile, but I agree that it's cleaner this way.

[rnk]

lgtm

IMO long term DenseMap should abstract this away from the user, so that large keys and values are stored in separate allocations. That's another story though.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

 //===----------------------------------------------------------------------===//
 //                          LazyValueInfoCache Decl
 //===----------------------------------------------------------------------===//
 
 namespace {
   /// A callback value handle updates the cache when values are erased.
   class LazyValueInfoCache;
   struct LVIValueHandle final : public CallbackVH {
+    // Needs to access getValPtr(), which is protected.
+    friend struct DenseMapInfo<LVIValueHandle>;
+
     LazyValueInfoCache *Parent;
 
     LVIValueHandle(Value *V, LazyValueInfoCache *P)
       : CallbackVH(V), Parent(P) { }
 
     void deleted() override;
     void allUsesReplacedWith(Value *V) override {
       deleted();
     }
   };
-}
+} // end anonymous namespace
 
 namespace {
   /// This is the cache kept by LazyValueInfo which
   /// maintains information about queries across the clients' queries.
   class LazyValueInfoCache {
     /// This is all of the cached block information for exactly one Value*.
     /// The entries are sorted by the BasicBlock* of the
     /// entries, allowing us to do a lookup with a binary search.
     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     /// memory overhead.
-    typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4>
-        ValueCacheEntryTy;
+    struct ValueCacheEntryTy {
+      ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
+      LVIValueHandle Handle;
+      SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
+    };
 
     /// This is all of the cached information for all values,
     /// mapped from Value* to key information.
-    std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
+    DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
 
     /// This tracks, on a per-block basis, the set of values that are
     /// over-defined at the end of that block.
     typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
         OverDefinedCacheTy;
     OverDefinedCacheTy OverDefinedCache;
 
     /// Keep track of all blocks that we have ever seen, so we
class LazyValueInfoCache {
 
     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
       SeenBlocks.insert(BB);
 
       // Insert over-defined values into their own cache to reduce memory
       // overhead.
       if (Result.isOverdefined())
         OverDefinedCache[BB].insert(Val);
-      else
-        lookup(Val)[BB] = Result;
+      else {
+        auto It = ValueCache.find_as(Val);
+        if (It == ValueCache.end()) {
+          ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
+          It = ValueCache.find_as(Val);
+          assert(It != ValueCache.end() && "Val was just added to the map!");
+        }
+        It->second->BlockVals[BB] = Result;
+      }
     }
 
   LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
   bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
                     LVILatticeVal &Result, Instruction *CxtI = nullptr);
   bool hasBlockValue(Value *Val, BasicBlock *BB);
 
   // These methods process one work item and may add more. A false value
   // returned means that the work item was not completely processed and must
   // be revisited after going through the new items.
   bool solveBlockValue(Value *Val, BasicBlock *BB);
   bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
   bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
   bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
                              BasicBlock *BB);
   bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI,
                                BasicBlock *BB);
   bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI,
                            BasicBlock *BB);
   void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
                                               Instruction *BBI);
 
   void solve();
 
-  ValueCacheEntryTy &lookup(Value *V) {
-    return ValueCache[LVIValueHandle(V, this)];
-  }
-
     bool isOverdefined(Value *V, BasicBlock *BB) const {
       auto ODI = OverDefinedCache.find(BB);
 
       if (ODI == OverDefinedCache.end())
         return false;
 
       return ODI->second.count(V);
     }
 
     bool hasCachedValueInfo(Value *V, BasicBlock *BB) {
       if (isOverdefined(V, BB))
         return true;
 
-      LVIValueHandle ValHandle(V, this);
-      auto I = ValueCache.find(ValHandle);
+      auto I = ValueCache.find_as(V);
       if (I == ValueCache.end())
         return false;
 
-      return I->second.count(BB);
+      return I->second->BlockVals.count(BB);
     }
 
     LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) {
       if (isOverdefined(V, BB))
         return LVILatticeVal::getOverdefined();
 
-      return lookup(V)[BB];
+      auto I = ValueCache.find_as(V);
+      if (I == ValueCache.end())
+        return LVILatticeVal();
+      auto BBI = I->second->BlockVals.find(BB);
+      if (BBI == I->second->BlockVals.end())
+        return LVILatticeVal();
+      return BBI->second;
     }
 
   public:
     /// This is the query interface to determine the lattice
     /// value for the specified Value* at the end of the specified block.
     LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
                                   Instruction *CxtI = nullptr);
 
if (I == SeenBlocks.end())
     return;
   SeenBlocks.erase(I);
 
   auto ODI = OverDefinedCache.find(BB);
   if (ODI != OverDefinedCache.end())
     OverDefinedCache.erase(ODI);
 
   for (auto &I : ValueCache)
-    I.second.erase(BB);
+    I.second->BlockVals.erase(BB);
 }
 
 void LazyValueInfoCache::solve() {
   while (!BlockValueStack.empty()) {
     std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
 
     if (solveBlockValue(e.second, e.first)) {