NewGVN: Clean up how we handle the INITIAL class so that everything in it is dead or unreachable, as it should be.

[• dberlin]

Summary

This lets us verify, more than we do now, that we didn't screw up
value numbering.

[• dberlin]

Add test cases

Updating D29842: NewGVN: Clean up how we handle the INITIAL class so that everything in

it is dead or unreachable, as it should be.

[davide]

No brainer. LGTM. I also like the name "top class" better.

[davide]

I'm under the impression that this will be *very* useful to catch outstanding bugs, if any.

lib/Transforms/Scalar/NewGVN.cpp

const CallExpression *NewGVN::createCallExpression(CallInst *CI,
   setBasicExpressionInfo(CI, E);
   return E;
 }
 
 // See if we have a congruence class and leader for this operand, and if so,
 // return it. Otherwise, return the operand itself.
 Value *NewGVN::lookupOperandLeader(Value *V) const {
   CongruenceClass *CC = ValueToClass.lookup(V);
-  if (CC && (CC != InitialClass))
+  if (CC) {
+    // Everything in INITIAL is represneted by undef, as it can be any value.
+    // We do have to make sure we get the type right though, so we can't set the
+    // RepLeader to undef.
+    if (CC == InitialClass)
+      return UndefValue::get(V->getType());
     return CC->RepStoredValue ? CC->RepStoredValue : CC->RepLeader;
+  }
+
   return V;
 }
 
 MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const {
   auto *CC = MemoryAccessToClass.lookup(MA);
   if (CC && CC->RepMemoryAccess)
     return CC->RepMemoryAccess;
   // FIXME: We need to audit all the places that current set a nullptr To, and
if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
         break;
       }
 
       if (Opcode != 0) {
         // Intrinsic recognized. Grab its args to finish building the
         // expression.
         assert(II->getNumArgOperands() == 2 &&
                "Expect two args for recognised intrinsics.");
-        return createBinaryExpression(Opcode, EI->getType(),
-                                      II->getArgOperand(0),
-                                      II->getArgOperand(1));
+        return createBinaryExpression(
+            Opcode, EI->getType(), II->getArgOperand(0), II->getArgOperand(1));
       }
     }
   }
 
   return createAggregateValueExpression(I);
 }
 const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) {
   CmpInst *CI = dyn_cast<CmpInst>(I);
if (OldClass->Members.empty() && OldClass != InitialClass) {
     if (OldClass->StoreCount > 0 && OldClass->RepMemoryAccess == StoreAccess) {
       DEBUG(dbgs() << "Kicking everything out of class " << OldClass->ID
                    << " because memory access leader changed");
       for (auto Member : OldClass->Members)
         ExpressionToClass.erase(ValueToExpression.lookup(Member));
     }
 
     // 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
+    // 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, ~0U};
     } else {
if (OldClass->Members.empty() && OldClass != InitialClass) {
     markLeaderChangeTouched(OldClass);
   }
 }
 
 // Perform congruence finding on a given value numbering expression.
 void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
   ValueToExpression[I] = E;
   // This is guaranteed to return something, since it will at least find
-  // INITIAL.
+  // TOP.
 
   CongruenceClass *IClass = ValueToClass[I];
   assert(IClass && "Should have found a IClass");
   // Dead classes should have been eliminated from the mapping.
   assert(!IClass->Dead && "Found a dead class");
 
   CongruenceClass *EClass;
   if (const auto *VE = dyn_cast<VariableExpression>(E)) {
if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) {
     // This also may be a memory defining terminator, in which case, set it
     // equivalent to nothing.
     if (MemoryAccess *MA = MSSA->getMemoryAccess(TI))
       setMemoryAccessEquivTo(MA, nullptr);
   }
 }
 
 // The algorithm initially places the values of the routine in the INITIAL
-// congruence
-// class. The leader of INITIAL is the undetermined value `TOP`.
+// congruence class. The leader of INITIAL is the undetermined value `TOP`.
 // When the algorithm has finished, values still in INITIAL are unreachable.
 void NewGVN::initializeCongruenceClasses(Function &F) {
   // FIXME now i can't remember why this is 2
   NextCongruenceNum = 2;
   // Initialize all other instructions to be in INITIAL class.
   CongruenceClass::MemberSet InitialValues;
   InitialClass = createCongruenceClass(nullptr, nullptr);
   InitialClass->RepMemoryAccess = MSSA->getLiveOnEntryDef();
   for (auto &B : F) {
     if (auto *MP = MSSA->getMemoryAccess(&B))
       MemoryAccessToClass[MP] = InitialClass;
 
     for (auto &I : B) {
+      // Don't insert void terminators into the class
+      if (!isa<TerminatorInst>(I) || !I.getType()->isVoidTy()) {
         InitialValues.insert(&I);
         ValueToClass[&I] = InitialClass;
+      }
       // All memory accesses are equivalent to live on entry to start. They must
       // be initialized to something so that initial changes are noticed. For
       // the maximal answer, we initialize them all to be the same as
       // liveOnEntry.  Note that to save time, we only initialize the
       // MemoryDef's for stores and all MemoryPhis to be equal.  Right now, no
       // other expression can generate a memory equivalence.  If we start
       // handling memcpy/etc, we can expand this.
       if (isa<StoreInst>(&I)) {
if (!I->isTerminator()) {
     const auto *Symbolized = performSymbolicEvaluation(I);
     // If we couldn't come up with a symbolic expression, use the unknown
     // expression
     if (Symbolized == nullptr)
       Symbolized = createUnknownExpression(I);
     performCongruenceFinding(I, Symbolized);
   } else {
     // Handle terminators that return values. All of them produce values we
-    // don't currently understand.
+    // don't currently understand.  We don't place non-value producing
+    // terminators in a class.
     if (!I->getType()->isVoidTy()) {
       auto *Symbolized = createUnknownExpression(I);
       performCongruenceFinding(I, Symbolized);
     }
     processOutgoingEdges(dyn_cast<TerminatorInst>(I), I->getParent());
   }
 }
 
for (auto &B : F) {
     }
   }
 
   for (CongruenceClass *CC : CongruenceClasses) {
     // Track the equivalent store info so we can decide whether to try
     // dead store elimination.
     SmallVector<ValueDFS, 8> PossibleDeadStores;
 
-    // FIXME: We should eventually be able to replace everything still
-    // in the initial class with undef, as they should be unreachable.
-    // Right now, initial still contains some things we skip value
-    // numbering of (UNREACHABLE's, for example).
-    if (CC == InitialClass || CC->Dead)
+    if (CC->Dead)
       continue;
+    // Everything still in the INITIAL class is unreachable or dead.
+    if (CC == InitialClass) {
+      // Assert everything is unreachable or dead
+      for (auto M : CC->Members)
+        assert((!ReachableBlocks.count(cast<Instruction>(M)->getParent()) ||
+                InstructionsToErase.count(cast<Instruction>(M))) &&
+               "Everything in INITIAL should be unreachable or dead at this "
+               "point");
+      continue;
+    }
+
     assert(CC->RepLeader && "We should have had a leader");
 
     // If this is a leader that is always available, and it's a
     // constant or has no equivalences, just replace everything with
     // it. We then update the congruence class with whatever members
     // are left.
     Value *Leader = CC->RepStoredValue ? CC->RepStoredValue : CC->RepLeader;
     if (alwaysAvailable(Leader)) {