[NewGVN] Minor cleanups

[nikic]

Summary

This patch implements a number of minor cleanups in NewGVN. If desired I can split this up further.

• In setMemoryClass(), assert that the memory access is already in MemoryAccessToClass. Previously the code simply did nothing if it was not in the map, which is confusing.
• Add a missing deleteExpression() in PHI Evaluation.
• Simplify handling of the false edge of branch predicates. We can handle this the same way as the true edge with an inverted predicate. This is both more general and simpler than the previous code.
• Fix a copy&paste mistake in addPredicateUsers which caused assumes() to not be handled. I think that due to the specific circumstances of the use, this did not cause issues.
• Simplify SwitchInst edge processing. Don't create an unused SwitchEdges map and handle default+cases the same. This code was probably doing something more prior to the introduction of PredicateInfo and this got left behind.
• Fix some comments.

[fhahn]

lib/Transforms/Scalar/NewGVN.cpp

1930–1939

Nit: no braces for one statements blocks.

[nikic]

Address nit.

[• dberlin]

Simplify handling of the false edge of branch predicates. We can handle this the same way as the true edge with an inverted predicate. This is both more general and simpler than the previous code.

I swear we have had an issue with an edge case that made this not true in
the past, which is what led to the current code.

If you've actually 3 stage bootstrapped clang+llvm and tested this, i'm
okay with it for now.

[nikic]

Applied trivial parts of this in rL364129 and rL364130. Abandoning the rest as I don't do clang bootstraps.

lib/Transforms/Scalar/NewGVN.cpp

assert(NewClass &&
          "Every MemoryAccess should be getting mapped to a non-null class");
   LLVM_DEBUG(dbgs() << "Setting " << *From);
   LLVM_DEBUG(dbgs() << " equivalent to congruence class ");
   LLVM_DEBUG(dbgs() << NewClass->getID()
                     << " with current MemoryAccess leader ");
   LLVM_DEBUG(dbgs() << *NewClass->getMemoryLeader() << "\n");
 
   auto LookupResult = MemoryAccessToClass.find(From);
+  assert(LookupResult != MemoryAccessToClass.end() &&
+         "MemoryAccess not in MemoryAccessToClass table");
+
   bool Changed = false;
-  // If it's already in the table, see if the value changed.
-  if (LookupResult != MemoryAccessToClass.end()) {
-    auto *OldClass = LookupResult->second;
-    if (OldClass != NewClass) {
-      // If this is a phi, we have to handle memory member updates.
-      if (auto *MP = dyn_cast<MemoryPhi>(From)) {
-        OldClass->memory_erase(MP);
-        NewClass->memory_insert(MP);
-        // This may have killed the class if it had no non-memory members
-        if (OldClass->getMemoryLeader() == From) {
-          if (OldClass->definesNoMemory()) {
-            OldClass->setMemoryLeader(nullptr);
-          } else {
-            OldClass->setMemoryLeader(getNextMemoryLeader(OldClass));
-            LLVM_DEBUG(dbgs() << "Memory class leader change for class "
-                              << OldClass->getID() << " to "
-                              << *OldClass->getMemoryLeader()
-                              << " due to removal of a memory member " << *From
-                              << "\n");
-            markMemoryLeaderChangeTouched(OldClass);
-          }
-        }
-      }
-      // It wasn't equivalent before, and now it is.
-      LookupResult->second = NewClass;
-      Changed = true;
-    }
-  }
 
   return Changed;
 }
 
 // Determine if a instruction is cycle-free.  That means the values in the
 // instruction don't depend on any expressions that can change value as a result
 // of the instruction.  For example, a non-cycle free instruction would be v =
 // phi(0, v+1).
NewGVN::performSymbolicPHIEvaluation(ArrayRef<ValPair> PHIOps,
   // If we are left with no operands, it's dead.
   if (Filtered.begin() == Filtered.end()) {
     // If it has undef at this point, it means there are no-non-undef arguments,
     // and thus, the value of the phi node must be undef.
     if (HasUndef) {
       LLVM_DEBUG(
           dbgs() << "PHI Node " << *I
                  << " has no non-undef arguments, valuing it as undef\n");
+      deleteExpression(E);
       return createConstantExpression(UndefValue::get(I->getType()));
     }
 
     LLVM_DEBUG(dbgs() << "No arguments of PHI node " << *I << " are live\n");
     deleteExpression(E);
     return createDeadExpression();
   }
   Value *AllSameValue = *(Filtered.begin());
const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
   // previous iteration.
   // Example:
   // icmp slt %a, %b
   // %b.0 = ssa.copy(%b)
   // false branch:
   // icmp slt %c, %b.0
 
   // %c and %a may start out equal, and thus, the code below will say the second
-  // %icmp is false.  c may become equal to something else, and in that case the
-  // %second icmp *must* be reexamined, but would not if only the renamed
-  // %operands are considered users of the icmp.
+  // icmp is false.  c may become equal to something else, and in that case the
+  // second icmp *must* be reexamined, but would not if only the renamed
+  // operands are considered users of the icmp.
 
   // *Currently* we only check one level of comparisons back, and only mark one
   // level back as touched when changes happen.  If you modify this code to look
   // back farther through comparisons, you *must* mark the appropriate
-  // comparisons as users in PredicateInfo.cpp, or you will cause bugs.  See if
-  // we know something just from the operands themselves
+  // comparisons as users in PredicateInfo.cpp, or you will cause bugs.
 
   // See if our operands have predicate info, so that we may be able to derive
   // something from a previous comparison.
   for (const auto &Op : CI->operands()) {
     auto *PI = PredInfo->getPredicateInfoFor(Op);
     if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
       if (PI == LastPredInfo)
         continue;
       LastPredInfo = PI;
       // In phi of ops cases, we may have predicate info that we are evaluating
       // in a different context.
       if (!DT->dominates(PBranch->To, getBlockForValue(I)))
         continue;
-      // TODO: Along the false edge, we may know more things too, like
-      // icmp of
-      // same operands is false.
       // TODO: We only handle actual comparison conditions below, not
       // and/or.
       auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
       if (!BranchCond)
         continue;
       auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
       auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
       auto BranchPredicate = BranchCond->getPredicate();
       if (shouldSwapOperands(BranchOp0, BranchOp1)) {
         std::swap(BranchOp0, BranchOp1);
         BranchPredicate = BranchCond->getSwappedPredicate();
       }
       if (BranchOp0 == Op0 && BranchOp1 == Op1) {
-        if (PBranch->TrueEdge) {
-          // If we know the previous predicate is true and we are in the true
-          // edge then we may be implied true or false.
-          if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate,
-                                                  OurPredicate)) {
-            addPredicateUsers(PI, I);
-            return createConstantExpression(
-                ConstantInt::getTrue(CI->getType()));
-          }
+        if (!PBranch->TrueEdge)
+          BranchPredicate = CmpInst::getInversePredicate(BranchPredicate);
+
+        // Check if one predicate implies anything about the other.
 
-          if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate,
-                                                   OurPredicate)) {
-            addPredicateUsers(PI, I);
-            return createConstantExpression(
-                ConstantInt::getFalse(CI->getType()));
-          }
-        } else {
-          // Just handle the ne and eq cases, where if we have the same
-          // operands, we may know something.
-          if (BranchPredicate == OurPredicate) {
-            addPredicateUsers(PI, I);
-            // Same predicate, same ops,we know it was false, so this is false.
-            return createConstantExpression(
-                ConstantInt::getFalse(CI->getType()));
-          } else if (BranchPredicate ==
-                     CmpInst::getInversePredicate(OurPredicate)) {
-            addPredicateUsers(PI, I);
-            // Inverse predicate, we know the other was false, so this is true.
-            return createConstantExpression(
-                ConstantInt::getTrue(CI->getType()));
-          }
-        }
       }
     }
   }
   // Create expression will take care of simplifyCmpInst
   return createExpression(I);
 }
 
 // Substitute and symbolize the value before value numbering.

 // Add I to the set of users of a given predicate.
 void NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) const {
   // Don't add temporary instructions to the user lists.
   if (AllTempInstructions.count(I))
     return;
 
   if (auto *PBranch = dyn_cast<PredicateBranch>(PB))
     PredicateToUsers[PBranch->Condition].insert(I);
-  else if (auto *PAssume = dyn_cast<PredicateBranch>(PB))
+  else if (auto *PAssume = dyn_cast<PredicateAssume>(PB))
     PredicateToUsers[PAssume->Condition].insert(I);
 }
 
 // Touch all the predicates that depend on this instruction.
 void NewGVN::markPredicateUsersTouched(Instruction *I) {
   touchAndErase(PredicateToUsers, I);
 }
 
if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
                           << " evaluated to false\n");
         updateReachableEdge(B, FalseSucc);
       }
     } else {
       updateReachableEdge(B, TrueSucc);
       updateReachableEdge(B, FalseSucc);
     }
   } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
-    // For switches, propagate the case values into the case
-    // destinations.
-
-    // Remember how many outgoing edges there are to every successor.
-    SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
-
     Value *SwitchCond = SI->getCondition();
     Value *CondEvaluated = findConditionEquivalence(SwitchCond);
-    // See if we were able to turn this switch statement into a constant.
     if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
+      // If we know the switch target, mark it as reachable
       auto *CondVal = cast<ConstantInt>(CondEvaluated);
-      // We should be able to get case value for this.
       auto Case = *SI->findCaseValue(CondVal);
-      if (Case.getCaseSuccessor() == SI->getDefaultDest()) {
-        // We proved the value is outside of the range of the case.
-        // We can't do anything other than mark the default dest as reachable,
-        // and go home.
-        updateReachableEdge(B, SI->getDefaultDest());
-        return;
-      }
-      // Now get where it goes and mark it reachable.
       BasicBlock *TargetBlock = Case.getCaseSuccessor();
       updateReachableEdge(B, TargetBlock);
     } else {
       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
         BasicBlock *TargetBlock = SI->getSuccessor(i);
-        ++SwitchEdges[TargetBlock];
         updateReachableEdge(B, TargetBlock);
       }
     }
   } else {
     // Otherwise this is either unconditional, or a type we have no
     // idea about. Just mark successors as reachable.
     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
       BasicBlock *TargetBlock = TI->getSuccessor(i);