[LazyValueInfo] Reduce memory usage

[ahatanak]

Summary

When the lattice value of a value is overdefined, LazyValueInfoCache inserts the lattice value into LazyValueInfoCache::ValueCache in addition to inserting it into OverDefinedCache. This isn't necessary and causes LazyValueInfo to use an excessive amount of memory in some cases.

This patch attempts to reduce memory usage of LazyValueInfo by avoiding inserting entries into LazyValueInfoCache::ValueCache when the lattice value type is overdefined. The memory usage decreases by 70 to 75% (from 1.5GB to 400MB) when I build one of the files in llvm.

[manmanren]

Hi Akira,

Thanks for working on this! The numbers look impressive.

I didn't really look into the patch but wonder if you can elaborate a little more on the issue.
When the lattice value of a value is overdefined, LazyValueInfoCache inserts the lattice value into LazyValueInfoCache::ValueCache in addition to inserting it into OverDefinedCache. This isn't necessary and causes LazyValueInfo to use an excessive amount of memory in some cases.
--> Is it possible to give a simple example where LazyValueInfo uses an excessive amount of memory?
--> Maybe a testing case?

Cheers,
Manman

[ahatanak]

--> Is it possible to give a simple example where LazyValueInfo uses an excessive amount of memory?

LazyValueInfoCache is inserting a large number of overdefined lattice values into ValueCache when the test case I have is compiled with opt. This is the stats I have:

4 - inserted lattice const
873 - inserted lattice constrange
280419 - inserted lattice nonconst
38308250 - inserted lattice overdefined

So 99% of the entries in ValueCache are overdefined. However, it isn't necessary to write overdefined values into ValueCache because OverDefinedCache keeps track of which values are overdefined in which basic blocks and, unlike const or constrange, overdefined doesn't need any of the information in LVILatticeVal (Val and Range).

I don't have a simple explanation as to why I'm seeing this behavior when I compile the particular test case yet.

--> Maybe a testing case?

The test case I have is a preprocessed file of lib/ARCMigrate/Transforms.cpp (from an internal branch of clang) from 2012. I'll see if I can come up with the exact command that exhibits the same behavior.

[ahatanak]

I tried compiling Transforms.cpp of r152020, but unfortunately clang (r255133) didn't exhibit an excessive memory usage (perhaps because some of the header files changed).

It seems that a large number of values are inserted into ValueCache because of the way LazyValueInfoCache gets the lattice value for a (basic block, value) pair. When LazyValueInfoCache needs a lattice value, it recursively visits the basic block's predecessors (it emulates recursion using a stack) until it gets an answer and inserts lattice values for all basic blocks that were visited.

[hfinkel]

LGTM.

lib/Analysis/LazyValueInfo.cpp

368 ↗

(On Diff #42325)

We should add a comment somewhere, maybe here, explaining that we insert overdefined values into their own cache to reduce memory overhead.

[ahatanak]

Thank you for the review.

I've added comments that explain why overdefined values are recorded in OverDefinedCache.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

if (!isa<UndefValue>(C))
       Res.markNotConstant(C);
     return Res;
   }
   static LVILatticeVal getRange(ConstantRange CR) {
     LVILatticeVal Res;
     Res.markConstantRange(CR);
     return Res;
   }
+  static LVILatticeVal getOverdefined() {
+    LVILatticeVal Res;
+    Res.markOverdefined();
+    return Res;
+  }
   
   bool isUndefined() const     { return Tag == undefined; }
   bool isConstant() const      { return Tag == constant; }
   bool isNotConstant() const   { return Tag == notconstant; }
   bool isConstantRange() const { return Tag == constantrange; }
   bool isOverdefined() const   { return Tag == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");

 
 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;
 
     /// This is all of the cached information for all values,
     /// mapped from Value* to key information.
     std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
 
     /// This tracks, on a per-block basis, the set of values that are
-    /// over-defined at the end of that block.  This is required
-    /// for cache updating.
+    /// 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
     /// don't spend time removing unused blocks from our caches.
     DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
 
class LazyValueInfoCache {
     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
     const DataLayout &DL; ///< A mandatory DataLayout
     DominatorTree *DT;    ///< An optional DT pointer.
 
     friend struct LVIValueHandle;
 
     void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
       SeenBlocks.insert(BB);
-      lookup(Val)[BB] = Result;
+
+      // Insert over-defined values into their own cache to reduce memory
+      // overhead.
       if (Result.isOverdefined())
         OverDefinedCache[BB].insert(Val);
+      else
+        lookup(Val)[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);
 
void mergeAssumeBlockValueConstantRange(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);
+      if (I == ValueCache.end())
+        return false;
+
+      return I->second.count(BB);
+    }
+
+    LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) {
+      if (isOverdefined(V, BB))
+        return LVILatticeVal::getOverdefined();
+
+      return lookup(V)[BB];
+    }
+    
   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);
 
     /// This is the query interface to determine the lattice
     /// value for the specified Value* at the specified instruction (generally

 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)) {
       // The work item was completely processed.
       assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
-      assert(lookup(e.second).count(e.first) && "Result should be in cache!");
+      assert(hasCachedValueInfo(e.second, e.first) &&
+             "Result should be in cache!");
 
       BlockValueStack.pop();
       BlockValueSet.erase(e);
     } else {
       // More work needs to be done before revisiting.
       assert(BlockValueStack.top() != e && "Stack should have been pushed!");
     }
   }
 }
 
 bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
   // If already a constant, there is nothing to compute.
   if (isa<Constant>(Val))
     return true;
 
-  LVIValueHandle ValHandle(Val, this);
-  auto I = ValueCache.find(ValHandle);
-  if (I == ValueCache.end()) return false;
-  return I->second.count(BB);
+  return hasCachedValueInfo(Val, BB);
 }
 
 LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val))
     return LVILatticeVal::get(VC);
 
   SeenBlocks.insert(BB);
-  return lookup(Val)[BB];
+  return getCachedValueInfo(Val, BB);
 }
 
 static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
   switch (BBI->getOpcode()) {
   default: break;
   case Instruction::Load:
   case Instruction::Call:
   case Instruction::Invoke:
static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
   // cause us to throw away those facts.
   return LVILatticeVal();
 }
 
 bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
   if (isa<Constant>(Val))
     return true;
 
-  if (lookup(Val).count(BB)) {
+  if (hasCachedValueInfo(Val, BB)) {
     // If we have a cached value, use that.
     DEBUG(dbgs() << "  reuse BB '" << BB->getName()
-                 << "' val=" << lookup(Val)[BB] << '\n');
+                 << "' val=" << getCachedValueInfo(Val, BB) << '\n');
 
     // Since we're reusing a cached value, we don't need to update the
     // OverDefinedCache. The cache will have been properly updated whenever the
     // cached value was inserted.
     return true;
   }
 
   // Hold off inserting this value into the Cache in case we have to return
for (Value *V : ValsToClear) {
       // If a value was marked overdefined in OldSucc, and is here too...
       auto OI = OverDefinedCache.find(ToUpdate);
       if (OI == OverDefinedCache.end())
         continue;
       SmallPtrSetImpl<Value *> &ValueSet = OI->second;
       if (!ValueSet.count(V))
         continue;
 
-      // Remove it from the caches.
-      ValueCacheEntryTy &Entry = ValueCache[LVIValueHandle(V, this)];
-      ValueCacheEntryTy::iterator CI = Entry.find(ToUpdate);
-
-      assert(CI != Entry.end() && "Couldn't find entry to update?");
-      Entry.erase(CI);
       ValueSet.erase(V);
       if (ValueSet.empty())
         OverDefinedCache.erase(OI);
 
       // If we removed anything, then we potentially need to update
       // blocks successors too.
       changed = true;
     }