Replace the custom linked list in LeaderTableEntry with TinyPtrVector.

[resistor]

Summary

The purpose of the custom linked list was to optimize for the case
of a single-element list. It turns out that TinyPtrVector handles
the same basic scenario even better, reducing the size of
LeaderTableEntry by 33%, and requiring only log2(N) allocations
as the size of the list grows. The only downside is that we have
to store the Value's and BasicBlock's in separate vectors, which
is slightly awkward in a few cases. Fortunately that ends up being
entirely encapsulated inside helper functions.

[nikic]

It looks like this patch causes a crash when running llvm-test-suite: http://llvm-compile-time-tracker.com/show_error.php?commit=26fd1e7f5ce498fa4d9c28a8dd3e7235466fc03a

[nikic]

llvm/include/llvm/Transforms/Scalar/GVN.h

295

This looks incorrect in multiple ways. If we're at the first instruction, this will step before the begin iterator. And the end iterator is invalidated in either case. I think you need something like this:

VI = entry.Val.erase(VI);
BI = entry.BB.erase(BI);
VE = entry.Val.end();
continue;

llvm/lib/Transforms/Scalar/GVN.cpp

2113

Can be just return is_contained(entry.BB, BB)?

[resistor]

Address review feedback.

llvm/include/llvm/Transforms/Scalar/GVN.h

295

Doh!

llvm/lib/Transforms/Scalar/GVN.cpp

2113

Done

[nikic]

This still crashes when building llvm-test-suite: http://llvm-compile-time-tracker.com/show_error.php?commit=77bc69cedc32296847573390cf393827b6196d1f There must be something else wrong...

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

2109

Hm, I think this is inverted. The old code is a bit hard to understand, but what it's checking is that all BBs are BB, not that any is. So this should be:

return all_of(entry.BB, [BB](BasicBlock *EntryBB) { return EntryBB == BB; });

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

2109

You had that right in your initial version any my is_contained suggestion was wrong :)

[resistor]

Fix condition.wq

[resistor]

Fix accidentally walking off of the end of the BB vector.

[resistor]

Format

[nikic]

It looks like this change ends up being a slightly negative in terms of instruction count: http://llvm-compile-time-tracker.com/compare.php?from=bf1b81d076f89bd56e86189b013f27dcf4d73ae8&to=efa882a79c027d27f6deff14e75bd9f558dd95d0&stat=instructions

[resistor]

In D125205#3508443, @nikic wrote:

It looks like this change ends up being a slightly negative in terms of instruction count: http://llvm-compile-time-tracker.com/compare.php?from=bf1b81d076f89bd56e86189b013f27dcf4d73ae8&to=efa882a79c027d27f6deff14e75bd9f558dd95d0&stat=instructions

As far as I can tell, the only behavioral difference with the new version is the order of leaders in the table, which biases the candidates returned by findLeader. The hand-rolled linked listed used an unprincipled ordering: the first candidate found was always at the front of the list, but after candidates were in reverse order of discovery. The new version is currently storing them strictly in order of recovery. I can try doing a backwards search in findLeader, which would be more similar to the the old approach on average. Really, we should probably have a more principled heuristic for choosing amongst the leaders, but that seems out of scope for this change.

[resistor]

Replicate the leader table insertion ordering of the old linked list.

[resistor]

Ping

[asbirlea]

Changes LGTM with inline nits.
@nikic I have not verified compile time impact with the latest diff.

llvm/lib/Transforms/Scalar/GVN.cpp

2108–2109

s/entry/Entry

2131–2133

s/entry/Entry

2228–2230

s/entry/Entry

3040–3043

s/entry/Entry

[resistor]

Rebase and address lints

[nikic]

Compile-time still looks the same: https://llvm-compile-time-tracker.com/compare.php?from=c2eccc67ce07e9cb374eb0ecdb3038fcb8be08cd&to=1e9114984490b83d4665f12a11f84c83f50ca8f0&stat=instructions That is, mildly negative.

I think that this analysis isn't really correct:

It turns out that TinyPtrVector handles the same basic scenario even better, reducing the size of LeaderTableEntry by 33%, and requiring only log2(N) allocations as the size of the list grows.

For all practical purposes, the number of allocations in the previous implementation was zero, because a bump pointer allocator was used, which is essentially free. In the new scheme, we get real (global allocator) allocations whenever we have more than one entry.

It is true that for a single entry, the size is reduced by 33%. However, if we go to two elements, then we'll end up separately allocating two SmallVectors with 4 elements each, which means we use a total of 14 pointer-sized values instead of 6 (not counting any additional overhead the global allocator adds). So for 2 entries, we actually use more than twice as much memory. This gets better for 3 and 4 entries, and then again much worse at 5 entries, where we leave behind unused inline SmallVector storage.

I don't know what the actual distribution of the number of entries is, but it's not really clear whether the new implementation uses less memory or is more performant in practice.

I assume that there was some kind of motivation for making this change and you observed better resource utilization for some workload?

llvm/include/llvm/Transforms/Scalar/GVN.h

 
 #ifndef LLVM_TRANSFORMS_SCALAR_GVN_H
 #define LLVM_TRANSFORMS_SCALAR_GVN_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Compiler.h"
 #include <cstdint>
 #include <utility>
private:
   LoopInfo *LI = nullptr;
   MemorySSAUpdater *MSSAU = nullptr;
 
   ValueTable VN;
 
   /// A mapping from value numbers to lists of Value*'s that
   /// have that value number.  Use findLeader to query it.
   struct LeaderTableEntry {
-    Value *Val;
-    const BasicBlock *BB;
-    LeaderTableEntry *Next;
+    TinyPtrVector<Value *> Val;
+    TinyPtrVector<const BasicBlock *> BB;
   };
   DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
-  BumpPtrAllocator TableAllocator;
 
   // Block-local map of equivalent values to their leader, does not
   // propagate to any successors. Entries added mid-block are applied
   // to the remaining instructions in the block.
   SmallMapVector<Value *, Value *, 4> ReplaceOperandsWithMap;
   SmallVector<Instruction *, 8> InstrsToErase;
 
   // Map the block to reversed postorder traversal number. It is used to
private:
   bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT,
                const TargetLibraryInfo &RunTLI, AAResults &RunAA,
                MemoryDependenceResults *RunMD, LoopInfo *LI,
                OptimizationRemarkEmitter *ORE, MemorySSA *MSSA = nullptr);
 
   /// Push a new Value to the LeaderTable onto the list for its value number.
   void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
     LeaderTableEntry &Curr = LeaderTable[N];
-    if (!Curr.Val) {
-      Curr.Val = V;
-      Curr.BB = BB;
-      return;
-    }
-
-    LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
-    Node->Val = V;
-    Node->BB = BB;
-    Node->Next = Curr.Next;
-    Curr.Next = Node;
+    Curr.Val.push_back(V);
+    Curr.BB.push_back(BB);
   }
 
   /// Scan the list of values corresponding to a given
   /// value number, and remove the given instruction if encountered.
   void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
-    LeaderTableEntry *Prev = nullptr;
-    LeaderTableEntry *Curr = &LeaderTable[N];
-
-    while (Curr && (Curr->Val != I || Curr->BB != BB)) {
-      Prev = Curr;
-      Curr = Curr->Next;
-    }
-
-    if (!Curr)
-      return;
-
-    if (Prev) {
-      Prev->Next = Curr->Next;
-    } else {
-      if (!Curr->Next) {
-        Curr->Val = nullptr;
-        Curr->BB = nullptr;
+    LeaderTableEntry &entry = LeaderTable[N];
+    assert(entry.BB.size() == entry.Val.size());
+    auto VI = entry.Val.begin();
+    auto VE = entry.Val.end();
+    auto BI = entry.BB.begin();
+    while (VI != VE) {
+      if (*VI == I && *BI == BB) {
+        VI = entry.Val.erase(VI);
+        BI = entry.BB.erase(BI);
+        VE = entry.Val.end();
       } else {
-        LeaderTableEntry *Next = Curr->Next;
-        Curr->Val = Next->Val;
-        Curr->BB = Next->BB;
-        Curr->Next = Next->Next;
+        ++VI;
+        ++BI;
       }
     }
   }
 
   // List of critical edges to be split between iterations.
   SmallVector<std::pair<Instruction *, unsigned>, 4> toSplit;
 
   // Helper functions of redundant load elimination
   bool processLoad(LoadInst *L);
   bool processNonLocalLoad(LoadInst *L);
   bool processAssumeIntrinsic(AssumeInst *II);
 
   /// Given a local dependency (Def or Clobber) determine if a value is
   /// available for the load.  Returns true if an value is known to be
   /// available and populates Res.  Returns false otherwise.
   bool AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,

llvm/lib/Transforms/Scalar/GVN.cpp

GVNPass::ValueTable::assignExpNewValueNum(Expression &Exp) {
   }
   return {e, CreateNewValNum};
 }
 
 /// Return whether all the values related with the same \p num are
 /// defined in \p BB.
 bool GVNPass::ValueTable::areAllValsInBB(uint32_t Num, const BasicBlock *BB,
                                          GVNPass &Gvn) {
-  LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
-  while (Vals && Vals->BB == BB)
-    Vals = Vals->Next;
-  return !Vals;
+  const LeaderTableEntry &entry = Gvn.LeaderTable[Num];
+  return all_of(entry.BB, [BB](const BasicBlock *EntryBB) { return EntryBB == BB; });
 }
 
 /// Wrap phiTranslateImpl to provide caching functionality.
 uint32_t GVNPass::ValueTable::phiTranslate(const BasicBlock *Pred,
                                            const BasicBlock *PhiBlock,
                                            uint32_t Num, GVNPass &Gvn) {
   auto FindRes = PhiTranslateTable.find({Num, Pred});
   if (FindRes != PhiTranslateTable.end())
     return FindRes->second;
   uint32_t NewNum = phiTranslateImpl(Pred, PhiBlock, Num, Gvn);
   PhiTranslateTable.insert({{Num, Pred}, NewNum});
   return NewNum;
 }
 
 // Return true if the value number \p Num and NewNum have equal value.
 // Return false if the result is unknown.
 bool GVNPass::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
                                            const BasicBlock *Pred,
                                            const BasicBlock *PhiBlock,
                                            GVNPass &Gvn) {
   CallInst *Call = nullptr;
-  LeaderTableEntry *Vals = &Gvn.LeaderTable[Num];
-  while (Vals) {
-    Call = dyn_cast<CallInst>(Vals->Val);
+  const LeaderTableEntry &entry = Gvn.LeaderTable[Num];
+  for (Value *Val : entry.Val) {
+    Call = dyn_cast<CallInst>(Val);
     if (Call && Call->getParent() == PhiBlock)
       break;
-    Vals = Vals->Next;
   }
 
   if (AA->doesNotAccessMemory(Call))
     return true;
 
   if (!MD || !AA->onlyReadsMemory(Call))
     return false;
 

 }
 
 // In order to find a leader for a given value number at a
 // specific basic block, we first obtain the list of all Values for that number,
 // and then scan the list to find one whose block dominates the block in
 // question.  This is fast because dominator tree queries consist of only
 // a few comparisons of DFS numbers.
 Value *GVNPass::findLeader(const BasicBlock *BB, uint32_t num) {
-  LeaderTableEntry Vals = LeaderTable[num];
-  if (!Vals.Val) return nullptr;
+  const LeaderTableEntry &entry = LeaderTable[num];
+  if (entry.Val.empty())
+    return nullptr;
 
   Value *Val = nullptr;
-  if (DT->dominates(Vals.BB, BB)) {
-    Val = Vals.Val;
-    if (isa<Constant>(Val)) return Val;
+  for (size_t i = 0, e = entry.Val.size(); i != e; ++i) {
+    if (DT->dominates(entry.BB[i], BB)) {
+      if (isa<Constant>(entry.Val[i]))
+        return entry.Val[i];
+      if (!Val)
+        Val = entry.Val[i];
     }
-
-  LeaderTableEntry* Next = Vals.Next;
-  while (Next) {
-    if (DT->dominates(Next->BB, BB)) {
-      if (isa<Constant>(Next->Val)) return Next->Val;
-      if (!Val) Val = Next->Val;
-    }
-
-    Next = Next->Next;
   }
 
   return Val;
 }
 
 /// There is an edge from 'Src' to 'Dst'.  Return
 /// true if every path from the entry block to 'Dst' passes via this edge.  In
 /// particular 'Dst' must not be reachable via another edge from 'Src'.
bool GVNPass::iterateOnFunction(Function &F) {
 
   return Changed;
 }
 
 void GVNPass::cleanupGlobalSets() {
   VN.clear();
   LeaderTable.clear();
   BlockRPONumber.clear();
-  TableAllocator.Reset();
   ICF->clear();
   InvalidBlockRPONumbers = true;
 }
 
 /// Verify that the specified instruction does not occur in our
 /// internal data structures.
 void GVNPass::verifyRemoved(const Instruction *Inst) const {
   VN.verifyRemoved(Inst);
 
   // Walk through the value number scope to make sure the instruction isn't
   // ferreted away in it.
   for (const auto &I : LeaderTable) {
-    const LeaderTableEntry *Node = &I.second;
-    assert(Node->Val != Inst && "Inst still in value numbering scope!");
-
-    while (Node->Next) {
-      Node = Node->Next;
-      assert(Node->Val != Inst && "Inst still in value numbering scope!");
+    const LeaderTableEntry &entry = I.second;
+    for (Value *Val : entry.Val) {
+      (void)Val;
+      assert(Val != Inst && "Inst still in value numbering scope!");
     }
   }
 }
 
 /// BB is declared dead, which implied other blocks become dead as well. This
 /// function is to add all these blocks to "DeadBlocks". For the dead blocks'
 /// live successors, update their phi nodes by replacing the operands
 /// corresponding to dead blocks with UndefVal.