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.

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

class NewGVN : public FunctionPass {
   AssumptionCache *AC;
   AliasAnalysis *AA;
   MemorySSA *MSSA;
   MemorySSAWalker *MSSAWalker;
   BumpPtrAllocator ExpressionAllocator;
   ArrayRecycler<Value *> ArgRecycler;
 
   // Congruence class info.
+
+  // This class is called INITIAL in the paper. It is the class everything
+  // startsout in, and represents any value. Being an optimistic analysis,
+  // anything in the INITIAL class has the value TOP, which is indeterminate and
+  // equivalent to everything.
   CongruenceClass *InitialClass;
   std::vector<CongruenceClass *> CongruenceClasses;
   unsigned NextCongruenceNum;
 
   // Value Mappings.
   DenseMap<Value *, CongruenceClass *> ValueToClass;
   DenseMap<Value *, const Expression *> ValueToExpression;
 
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) {
+#ifndef NDEBUG
+      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");
+#endif
+      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)) {

llvm/trunk/test/Transforms/NewGVN/basic-cyclic-opt.ll

bb21:                                             ; preds = %bb14
   %tmp22 = add nsw i32 %i.0, 1
   br label %bb4
 
 bb23:                                             ; preds = %bb4
   ret i32 %p.0
 }
 
 ;; This is an irreducible test case that will cause a memoryphi node loop
-;; in the two block.
-;; it's equivalent to something like
+;; in the two blocks.
+;; It's equivalent to something like
 ;; *a = 0
 ;; if (<....>) goto loopmiddle
 ;; loopstart:
 ;; loopmiddle:
 ;; load *a
 ;; *a = 0
 ;; if (<....>) goto loopstart otherwise goto loopend
 ;; loopend:
 ;; load *a
 ;; add the results of the loads
 ;; return them
 ;;
 ;; Both loads should equal 0, but it requires being
 ;; completely optimistic about MemoryPhis, otherwise
 ;; we will not be able to see through the cycle.
-define i8 @quux(i8* noalias %arg, i8* noalias %arg2) {
-; CHECK-LABEL: @quux(
+define i8 @irreducible_memoryphi(i8* noalias %arg, i8* noalias %arg2) {
+; CHECK-LABEL: @irreducible_memoryphi(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    store i8 0, i8* [[ARG:%.*]]
 ; CHECK-NEXT:    br i1 undef, label [[BB2:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB3:%.*]]
 ; CHECK:       bb3:
bb2:                                              ; preds = %bb1, %bb
   store i8 0, i8 *%arg
   br i1 undef, label %bb1, label %bb3
 
 bb3:                                              ; preds = %bb2
   %tmp = load i8, i8* %arg
   %tmp3 = add i8 %tmp, %tmp2
   ret i8 %tmp3
 }
+;; This is an irreducible test case that will cause a phi node loop
+;; in the two blocks
+;;
+;; It should return 0, but it requires being
+;; completely optimistic about phis, otherwise
+;; we will not be able to see through the cycle.
+define i32 @irreducible_phi(i32 %arg) {
+; CHECK-LABEL: @irreducible_phi(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br i1 undef, label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i32 0
+;
+bb:
+  %tmp = add i32 0, %arg
+  br i1 undef, label %bb2, label %bb1
+
+bb1:                                              ; preds = %bb2, %bb
+  %phi1 = phi i32 [%tmp, %bb], [%phi2, %bb2]
+  br label %bb2
+
+bb2:                                              ; preds = %bb1, %bb
+  %phi2 = phi i32 [%tmp, %bb], [%phi1, %bb1]
+  br i1 undef, label %bb1, label %bb3
+
+bb3:                                              ; preds = %bb2
+  ; This should be zero
+  %tmp3 = sub i32 %tmp, %phi2
+  ret i32 %tmp3
+}
 attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
 
 !llvm.ident = !{!0, !0, !0}
 
 !0 = !{!"Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn)"}