NewGVN: Move leaders around properly to ensure we have a canonical dominating leader. Fixes PR 31613.

[• dberlin]

Summary

This is a testcase where phi node cycling happens, and because we do
not order the leaders by domination or anything similar, the leader
keeps changing.

Using std::set for the members is too expensive, and we actually don't
need them sorted all the time, only at leader changes.

We could keep both a set and a vector, and keep them mostly sorted and
resort as necessary, or use a set and a fibheap, but all of this seems
premature.

After running some statistics, we are able to avoid the vast majority
of sorting by keeping a "next leader" field. Most congruence classes only have
leader changes once or twice during GVN.

[• dberlin]

• Update testcase with comment, revert gratuitous formatting change

[• dberlin]

Also, this was 3-staged on darwin and linux

lib/Transforms/Scalar/NewGVN.cpp

331–332

These are only ever called with instructions, and doing this saves us a ton of work in the new work on moveValueToNewCongruenceClass.

I can split out the change if we want.

1079

(IE the reverse check)

[davide]

Some comments inline, this looks correct but I'd like to run some tests tomorrow morning once I'm back to my workstation. Quick question, I can see how a set/vector can help here but I didn't think about the fib heap. Why did you mention such a variant and not let's say binomial/trinomial?

lib/Transforms/Scalar/NewGVN.cpp

148

~0U ?

1074

~0U ?

1080–1084

Can you please add a messahge to this assertion?

1131

X can probably be passed by reference?
I'm always in doubt with auto (I try to never rely on the implicit referenceness/pointerness of auto and always be explicit to avoid accidental copies)

1203

spurious whiteline

1220

auto *

1562–1563

unrelated I assume?

test/Transforms/NewGVN/pr31613.ll

68

this moduleId here crept in?

[• dberlin]

In D28594#643719, @davide wrote:

Some comments inline, this looks correct but I'd like to run some tests tomorrow morning once I'm back to my workstation. Quick question, I can see how a set/vector can help here but I didn't think about the fib heap. Why did you mention such a variant and not let's say binomial/trinomial?

Fibheaps have O(1) insert/delete. We don't want to pay any cost until we actually extract. So when we add/remove members, we just do that, and then when we actually change leaders, we pay the cost of extracting the min.
You could also use weak rank heaps.

(Note that delete on a fibheap/rank paired heap is basically tombstoning by just "decrease-key to negative infinity", special case them on extract/etc)

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

1131

The members are already value *'s :)

1562–1563

Yes, i'll revert it.

[• dberlin]

• Fix for review comments and revert spurious formatting changes

[davide]

Did my testing, LGTM, let's try to get this in before the branch =)

lib/Transforms/Scalar/NewGVN.cpp

 #define DEBUG_TYPE "newgvn"
 
 STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
 STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
 STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
 STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
 STATISTIC(NumGVNMaxIterations,
           "Maximum Number of iterations it took to converge GVN");
+STATISTIC(NumGVNLeaderChanges, "Number of leader changes");
+STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes");
+STATISTIC(NumGVNAvoidedSortedLeaderChanges,
+          "Number of avoided sorted leader changes");
 
 //===----------------------------------------------------------------------===//
 //                                GVN Pass
 //===----------------------------------------------------------------------===//
 
 // Anchor methods.
 namespace llvm {
 namespace GVNExpression {
struct CongruenceClass {
   // True if this class has no members left.  This is mainly used for assertion
   // purposes, and for skipping empty classes.
   bool Dead = false;
 
   // Number of stores in this congruence class.
   // This is used so we can detect store equivalence changes properly.
   int StoreCount = 0;
 
+  // The most dominating leader after our current leader, because the member set
+  // is not sorted and is expensive to keep sorted all the time.
+  std::pair<Value *, unsigned int> NextLeader = {nullptr, ~0};
+
   explicit CongruenceClass(unsigned ID) : ID(ID) {}
   CongruenceClass(unsigned ID, Value *Leader, const Expression *E)
       : ID(ID), RepLeader(Leader), DefiningExpr(E) {}
 };
 
 namespace llvm {
 template <> struct DenseMapInfo<const Expression *> {
   static const Expression *getEmptyKey() {
private:
   bool setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To);
   const Expression *performSymbolicAggrValueEvaluation(Instruction *,
                                                        const BasicBlock *);
 
   // Congruence finding.
   // Templated to allow them to work both on BB's and BB-edges.
   template <class T>
   Value *lookupOperandLeader(Value *, const User *, const T &) const;
-  void performCongruenceFinding(Value *, const Expression *);
-  void moveValueToNewCongruenceClass(Value *, CongruenceClass *,
+  void performCongruenceFinding(Instruction *, const Expression *);
+  void moveValueToNewCongruenceClass(Instruction *, CongruenceClass *,
                                      CongruenceClass *);
   // Reachability handling.
   void updateReachableEdge(BasicBlock *, BasicBlock *);
   void processOutgoingEdges(TerminatorInst *, BasicBlock *);
   bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const;
   Value *findConditionEquivalence(Value *, BasicBlock *) const;
   MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const;
 
for (auto M : CC->Members) {
     if (auto *I = dyn_cast<Instruction>(M))
       TouchedInstructions.set(InstrDFS[I]);
     LeaderChanges.insert(M);
   }
 }
 
 // Move a value, currently in OldClass, to be part of NewClass
 // Update OldClass for the move (including changing leaders, etc)
-void NewGVN::moveValueToNewCongruenceClass(Value *V, CongruenceClass *OldClass,
+void NewGVN::moveValueToNewCongruenceClass(Instruction *I,
+                                           CongruenceClass *OldClass,
                                            CongruenceClass *NewClass) {
-  DEBUG(dbgs() << "New congruence class for " << V << " is " << NewClass->ID
+  DEBUG(dbgs() << "New congruence class for " << I << " is " << NewClass->ID
                << "\n");
-  OldClass->Members.erase(V);
-  NewClass->Members.insert(V);
-  if (isa<StoreInst>(V)) {
+
+  if (I == OldClass->NextLeader.first)
+    OldClass->NextLeader = {nullptr, ~0};
+
+  // The new instruction and new class leader may either be siblings in the
+  // dominator tree, or the new class leader should dominate the new member
+  // instruction.  We simply check that the member instruction does not properly
+  // dominate the new class leader.
+  assert(
+      !isa<Instruction>(NewClass->RepLeader) || !NewClass->RepLeader ||
+      I == NewClass->RepLeader ||
+      !DT->properlyDominates(
+          I->getParent(), cast<Instruction>(NewClass->RepLeader)->getParent()));
+
+  if (NewClass->RepLeader != I) {
+    auto DFSNum = InstrDFS.lookup(I);
+    if (DFSNum < NewClass->NextLeader.second)
+      NewClass->NextLeader = {I, DFSNum};
+  }
+
+  OldClass->Members.erase(I);
+  NewClass->Members.insert(I);
+  if (isa<StoreInst>(I)) {
     --OldClass->StoreCount;
     assert(OldClass->StoreCount >= 0);
     ++NewClass->StoreCount;
     assert(NewClass->StoreCount > 0);
   }
 
-  ValueToClass[V] = NewClass;
+  ValueToClass[I] = NewClass;
   // See if we destroyed the class or need to swap leaders.
   if (OldClass->Members.empty() && OldClass != InitialClass) {
     if (OldClass->DefiningExpr) {
       OldClass->Dead = true;
       DEBUG(dbgs() << "Erasing expression " << OldClass->DefiningExpr
                    << " from table\n");
       ExpressionToClass.erase(OldClass->DefiningExpr);
     }
-  } else if (OldClass->RepLeader == V) {
+  } else if (OldClass->RepLeader == I) {
     // When the leader changes, the value numbering of
     // everything may change due to symbolization changes, so we need to
     // reprocess.
+    DEBUG(dbgs() << "Leader change!\n");
+    ++NumGVNLeaderChanges;
+    // We don't need to sort members if there is only 1, and we don't care about
+    // sorting the initial class because everything either gets out of it or is
+    // unreachable.
+    if (OldClass->Members.size() == 1 || OldClass == InitialClass) {
       OldClass->RepLeader = *(OldClass->Members.begin());
+    } else if (OldClass->NextLeader.first) {
+      ++NumGVNAvoidedSortedLeaderChanges;
+      OldClass->RepLeader = OldClass->NextLeader.first;
+      OldClass->NextLeader = {nullptr, ~0};
+    } else {
+      ++NumGVNSortedLeaderChanges;
+      // TODO: If this ends up to slow, we can maintain a dual structure for
+      // member testing/insertion, or keep things mostly sorted, and sort only
+      // here, or ....
+      std::pair<Value *, unsigned> MinDFS = {nullptr, ~0};
+      for (const auto X : OldClass->Members) {
+        auto DFSNum = InstrDFS.lookup(X);
+        if (DFSNum < MinDFS.second)
+          MinDFS = {X, DFSNum};
+      }
+      OldClass->RepLeader = MinDFS.first;
+    }
     markLeaderChangeTouched(OldClass);
   }
 }
 
 // Perform congruence finding on a given value numbering expression.
-void NewGVN::performCongruenceFinding(Value *V, const Expression *E) {
-  ValueToExpression[V] = E;
+void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
+  ValueToExpression[I] = E;
   // This is guaranteed to return something, since it will at least find
   // INITIAL.
 
-  CongruenceClass *VClass = ValueToClass[V];
-  assert(VClass && "Should have found a vclass");
+  CongruenceClass *IClass = ValueToClass[I];
+  assert(IClass && "Should have found a IClass");
   // Dead classes should have been eliminated from the mapping.
-  assert(!VClass->Dead && "Found a dead class");
+  assert(!IClass->Dead && "Found a dead class");
 
   CongruenceClass *EClass;
   if (const auto *VE = dyn_cast<VariableExpression>(E)) {
     EClass = ValueToClass[VE->getVariableValue()];
   } else {
     auto lookupResult = ExpressionToClass.insert({E, nullptr});
 
     // If it's not in the value table, create a new congruence class.
     if (lookupResult.second) {
       CongruenceClass *NewClass = createCongruenceClass(nullptr, E);
       auto place = lookupResult.first;
       place->second = NewClass;
 
       // Constants and variables should always be made the leader.
       if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
         NewClass->RepLeader = CE->getConstantValue();
       } else if (const auto *SE = dyn_cast<StoreExpression>(E)) {
         StoreInst *SI = SE->getStoreInst();
         NewClass->RepLeader =
             lookupOperandLeader(SI->getValueOperand(), SI, SI->getParent());
       } else {
-        NewClass->RepLeader = V;
+        NewClass->RepLeader = I;
       }
       assert(!isa<VariableExpression>(E) &&
              "VariableExpression should have been handled already");
 
       EClass = NewClass;
-      DEBUG(dbgs() << "Created new congruence class for " << *V
+      DEBUG(dbgs() << "Created new congruence class for " << *I
                    << " using expression " << *E << " at " << NewClass->ID
                    << " and leader " << *(NewClass->RepLeader) << "\n");
       DEBUG(dbgs() << "Hash value was " << E->getHashValue() << "\n");
     } else {
       EClass = lookupResult.first->second;
       if (isa<ConstantExpression>(E))
         assert(isa<Constant>(EClass->RepLeader) &&
                "Any class with a constant expression should have a "
                "constant leader");
 
       assert(EClass && "Somehow don't have an eclass");
 
       assert(!EClass->Dead && "We accidentally looked up a dead class");
     }
   }
-  bool ClassChanged = VClass != EClass;
-  bool LeaderChanged = LeaderChanges.erase(V);
+  bool ClassChanged = IClass != EClass;
+  bool LeaderChanged = LeaderChanges.erase(I);
   if (ClassChanged || LeaderChanged) {
     DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << E
                  << "\n");
 
     if (ClassChanged)
+      moveValueToNewCongruenceClass(I, IClass, EClass);
 
-      moveValueToNewCongruenceClass(V, VClass, EClass);
-
-
-    markUsersTouched(V);
-    if (auto *I = dyn_cast<Instruction>(V)) {
-      if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
-        // If this is a MemoryDef, we need to update the equivalence table. If
-        // we determined the expression is congruent to a different memory
-        // state, use that different memory state.  If we determined it didn't,
-        // we update that as well.  Right now, we only support store
-        // expressions.
-        if (!isa<MemoryUse>(MA) && isa<StoreExpression>(E) &&
-            EClass->Members.size() != 1) {
-          auto *DefAccess = cast<StoreExpression>(E)->getDefiningAccess();
-          setMemoryAccessEquivTo(MA, DefAccess != MA ? DefAccess : nullptr);
-        } else {
-          setMemoryAccessEquivTo(MA, nullptr);
-        }
-        markMemoryUsersTouched(MA);
-      }
-    }
-  } else if (StoreInst *SI = dyn_cast<StoreInst>(V)) {
+    markUsersTouched(I);
+  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
     // There is, sadly, one complicating thing for stores.  Stores do not
     // produce values, only consume them.  However, in order to make loads and
     // stores value number the same, we ignore the value operand of the store.
     // But the value operand will still be the leader of our class, and thus, it
     // may change.  Because the store is a use, the store will get reprocessed,
     // but nothing will change about it, and so nothing above will catch it
     // (since the class will not change).  In order to make sure everything ends
     // up okay, we need to recheck the leader of the class.  Since stores of
if (auto *FirstDef = dyn_cast<MemoryUseOrDef>(First)) {
     if (Okay)
       return singleReachablePHIPath(cast<MemoryAccess>(OperandList[0]), Second);
     return false;
   }
 }
 
 // Verify the that the memory equivalence table makes sense relative to the
 // congruence classes.  Note that this checking is not perfect, and is currently
-// subject to very rare false negatives. It is only useful for testing/debugging.
+// subject to very rare false negatives. It is only useful for testing and
+// debugging.
 void NewGVN::verifyMemoryCongruency() const {
   // Anything equivalent in the memory access table should be in the same
   // congruence class.
 
   // Filter out the unreachable and trivially dead entries, because they may
   // never have been updated if the instructions were not processed.
   auto ReachableAccessPred =
       [&](const std::pair<const MemoryAccess *, MemoryAccess *> Pair) {
for (auto KV : Filtered) {
     // Unreachable instructions may not have changed because we never process
     // them.
     if (!ReachableBlocks.count(KV.first->getBlock()))
       continue;
     if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
       auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second);
       if (FirstMUD && SecondMUD)
         assert((singleReachablePHIPath(FirstMUD, SecondMUD) ||
                 ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
-                       ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
-                   "The instructions for these memory operations should have "
-                   "been in the same congruence class or reachable through"
-                   "a single argument phi");
     } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
 
       // We can only sanely verify that MemoryDefs in the operand list all have
       // the same class.
       auto ReachableOperandPred = [&](const Use &U) {
         return ReachableBlocks.count(FirstMP->getIncomingBlock(U)) &&
                isa<MemoryDef>(U);
 

test/Transforms/NewGVN/pr31613.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+;; Both of these tests are tests of phi nodes that end up all equivalent to each other
+;; Without proper leader ordering, we will end up cycling the leader between all of them and never converge.
+
+define void @foo() {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP:%.*]] = phi i32 [ 0, [[BB:%.*]] ], [ 1, [[BB18:%.*]] ]
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br i1 undef, label [[BB18]], label [[BB7:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB9:%.*]]
+; CHECK:       bb9:
+; CHECK-NEXT:    br i1 undef, label [[BB2]], label [[BB11:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    br i1 undef, label [[BB16:%.*]], label [[BB14:%.*]]
+; CHECK:       bb14:
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb16:
+; CHECK-NEXT:    br label [[BB7]]
+; CHECK:       bb18:
+; CHECK-NEXT:    br label [[BB1]]
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb18, %bb
+  %tmp = phi i32 [ 0, %bb ], [ 1, %bb18 ]
+  br label %bb2
+
+bb2:                                              ; preds = %bb9, %bb1
+  %tmp3 = phi i32 [ %tmp, %bb1 ], [ %tmp8, %bb9 ]
+  br label %bb4
+
+bb4:                                              ; preds = %bb14, %bb2
+  %tmp5 = phi i32 [ %tmp3, %bb2 ], [ %tmp15, %bb14 ]
+  br i1 undef, label %bb18, label %bb7
+
+bb7:                                              ; preds = %bb16, %bb4
+  %tmp8 = phi i32 [ %tmp17, %bb16 ], [ %tmp5, %bb4 ]
+  br label %bb9
+
+bb9:                                              ; preds = %bb7
+  br i1 undef, label %bb2, label %bb11
+
+bb11:                                             ; preds = %bb9
+  br i1 undef, label %bb16, label %bb14
+
+bb14:                                             ; preds = %bb11
+  %tmp15 = phi i32 [ %tmp8, %bb11 ]
+  br label %bb4
+
+bb16:                                             ; preds = %bb11
+  %tmp17 = phi i32 [ %tmp8, %bb11 ]
+  br label %bb7
+
+bb18:                                             ; preds = %bb4
+  br label %bb1
+}
+; ModuleID = 'pr31613-3.ll'
+
+%struct.a = type {}
+%struct.b = type {}
+
+declare void @c.d.p(i64, i8*)
+
+define void @e() {
+; CHECK-LABEL: @e(
+; CHECK-NEXT:    [[F:%.*]] = alloca i32
+; CHECK-NEXT:    store i32 undef, i32* [[F]], !g !0
+; CHECK-NEXT:    br label [[H:%.*]]
+; CHECK:       h:
+; CHECK-NEXT:    call void @c.d.p(i64 8, i8* undef)
+; CHECK-NEXT:    [[I:%.*]] = load i32, i32* [[F]]
+; CHECK-NEXT:    [[J:%.*]] = load i32, i32* null
+; CHECK-NEXT:    [[K:%.*]] = icmp eq i32 [[I]], [[J]]
+; CHECK-NEXT:    br i1 [[K]], label [[L:%.*]], label [[Q:%.*]]
+; CHECK:       l:
+; CHECK-NEXT:    br label [[R:%.*]]
+; CHECK:       q:
+; CHECK-NEXT:    [[M:%.*]] = load [[STRUCT_A*:%.*]], [[STRUCT_A**:%.*]] null
+; CHECK-NEXT:    br label [[R]]
+; CHECK:       r:
+; CHECK-NEXT:    switch i32 undef, label [[N:%.*]] [
+; CHECK-NEXT:    i32 0, label [[S:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       s:
+; CHECK-NEXT:    store i32 undef, i32* [[F]], !g !0
+; CHECK-NEXT:    br label [[H]]
+; CHECK:       n:
+; CHECK-NEXT:    [[O:%.*]] = load [[STRUCT_A*]], [[STRUCT_A**]] null
+; CHECK-NEXT:    ret void
+;
+  %f = alloca i32
+  store i32 undef, i32* %f, !g !0
+  br label %h
+
+h:                                                ; preds = %s, %0
+  call void @c.d.p(i64 8, i8* undef)
+  %i = load i32, i32* %f
+  %j = load i32, i32* null
+  %k = icmp eq i32 %i, %j
+  br i1 %k, label %l, label %q
+
+l:                                                ; preds = %h
+  br label %r
+
+q:                                                ; preds = %h
+  %m = load %struct.a*, %struct.a** null
+  %1 = bitcast %struct.a* %m to %struct.b*
+  br label %r
+
+r:                                                ; preds = %q, %l
+  switch i32 undef, label %n [
+  i32 0, label %s
+  ]
+
+s:                                                ; preds = %r
+  store i32 undef, i32* %f, !g !0
+  br label %h
+
+n:                                                ; preds = %r
+  %o = load %struct.a*, %struct.a** null
+  %2 = bitcast %struct.a* %o to %struct.b*
+  ret void
+}
+
+!0 = !{}