NewGVN: Start making use of predicateinfo pass.

[• dberlin]

Summary

This begins using the predicateinfo pass in NewGVN.

[• dberlin]

We don't yet pass edge.ll because we don't handle switch statements in predicateinfo.
condprop.ll also has one silly testcase :)

[• dberlin]

• Update with fixes for botched logic

[• dberlin]

• Convert to early exit form for better formatting

[• dberlin]

• NewGVN: Update for ranking being committed

[davide]

THis needs some tests (unless there are some which are are XFAIL'D and now pass). Other than that, great to see this making progress =)
Some comments inline.

lib/Transforms/Scalar/NewGVN.cpp

867–895 ↗

(On Diff #88092)

I starred at this for long, and I think it's correct. I do also think you can simplify this to make it *slightly* more readable, at least in my opinion, removing the else after return.

903 ↗

(On Diff #88092)

s/Things/intrinsics/ (or instructions)? Also, full stop at the end of the comment I think (nit)

1110–1113 ↗

(On Diff #88092)

I'm not sure this is entirely right, do you have a test where this triggers so I can take a look?

1841 ↗

(On Diff #88092)

Any chance you can use something like unique_ptr<> instead of naked new (or something similar)?

2480–2481 ↗

(On Diff #88092)

s/it's/its/

[davide]

Marking as request changes so that I can keep track of what I need to review from the Phab UI

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

867–895 ↗

(On Diff #88092)

Yeah, i think, over time, we should try to move a lot of this logic to some central place.

Simplify* knows how to do a *lot* of it (and sadly, does it's own walking to try to figure out some cases), but it's a complex maze of twisty passages, and it's not clear to me how to shove predicate info into it in a sane way.

Most of these tests are covered by edge.ll, which we'll pass once the switch stuff goes in

903 ↗

(On Diff #88092)

Fixed.

1110–1113 ↗

(On Diff #88092)

This is from GVN:

02244 // If "A >= B" is known true, replace "A < B" with false everywhere.
02245 CmpInst::Predicate NotPred = Cmp->getInversePredicate();
02246 Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);

It does not restrict itself to equality predicates.

I'll grab the appropriate testcases, but the only cases i believe this could be false is somewhere in the land of floating point.

I also thought it was weird, but:

Looking at it from the perspective of truth tables, inverse predicate just returns a truth table that has true and false swapped.

So if the other comparison is false, and it has the same operands, the inverse predicate must be true (because every place that predicate has false in the truth table, this one has true)

1841 ↗

(On Diff #88092)

Yes, i'll fix

[• dberlin]

Also, i was kind of hoping to be able to make the testcases a non-issue by just passing them, but instead, for most, we are now passing 9/10 in a file, and there's no way to xfail the single testcase :(

I may move them into -xfail.ll tests for now or something, just so we have passing testcases.

Other suggestions welcome.

[davide]

In D29682#674650, @dberlin wrote:

Also, i was kind of hoping to be able to make the testcases a non-issue by just passing them, but instead, for most, we are now passing 9/10 in a file, and there's no way to xfail the single testcase :(

I may move them into -xfail.ll tests for now or something, just so we have passing testcases.

Other suggestions welcome.

Splitting the test seems the best strategy to me.

[davide]

This LGTM with the comments addressed. Feel free to commit without updating the review to phab.

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

882 ↗

(On Diff #88092)

For the record: The above part is true, but this is wrong.
It's only true for equality (ICMP_EQ and ICMP_NE)
After your comment below, I wrote a little fuzzer that tested every variant, and .... it flagged this (the part you mentioned below is definitely correct)
Trivial example:
%tmp3 = load i32, i32* %tmp, align 4
%tmp5 = icmp ult i32 %tmp3, 16

%tmp5 is false when equal.
That does not imply that tmp3 == 16.

The more i stare at this, the more unhappy i am that all this logic is not somewhere else.
I added it to my todo list to see about trying to plumb this through various parts of simplifyinst, which already has well tested logic for these simplifications, it just needs to know we know something about the value.

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

 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVNExpression.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/MemorySSA.h"
+#include "llvm/Transforms/Utils/PredicateInfo.h"
 #include <unordered_map>
 #include <utility>
 #include <vector>
 using namespace llvm;
 using namespace PatternMatch;
 using namespace llvm::GVNExpression;
-
 #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");

 class NewGVN : public FunctionPass {
   DominatorTree *DT;
   const DataLayout *DL;
   const TargetLibraryInfo *TLI;
   AssumptionCache *AC;
   AliasAnalysis *AA;
   MemorySSA *MSSA;
   MemorySSAWalker *MSSAWalker;
+  std::unique_ptr<PredicateInfo> PredInfo;
   BumpPtrAllocator ExpressionAllocator;
   ArrayRecycler<Value *> ArgRecycler;
 
   // Number of function arguments, used by ranking
   unsigned int NumFuncArgs;
 
   // 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;
 
+  // Mapping from predicate info we used to the instructions we used it with.
+  // In order to correctly ensure propagation, we must keep track of what
+  // comparisons we used, so that when the values of the comparisons change, we
+  // propagate the information to the places we used the comparison.
+  DenseMap<const Value *, SmallPtrSet<Instruction *, 2>> PredicateToUsers;
+
   // A table storing which memorydefs/phis represent a memory state provably
   // equivalent to another memory state.
   // We could use the congruence class machinery, but the MemoryAccess's are
   // abstract memory states, so they can only ever be equivalent to each other,
   // and not to constants, etc.
   DenseMap<const MemoryAccess *, CongruenceClass *> MemoryAccessToClass;
 
   // Expression to class mapping.

 
 private:
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
-
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 
   // Expression handling.
   const Expression *createExpression(Instruction *);
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *);
   PHIExpression *createPHIExpression(Instruction *);
   const VariableExpression *createVariableExpression(Value *);
   const ConstantExpression *createConstantExpression(Constant *);
+  const Expression *createVariableOrConstant(Value *V);
   const UnknownExpression *createUnknownExpression(Instruction *);
   const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *);
   LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
                                        MemoryAccess *);
   const CallExpression *createCallExpression(CallInst *, MemoryAccess *);
   const AggregateValueExpression *createAggregateValueExpression(Instruction *);
   bool setBasicExpressionInfo(Instruction *, BasicExpression *);
 
const Expression *checkSimplificationResults(Expression *, Instruction *,
                                                Value *);
   const Expression *performSymbolicEvaluation(Value *);
   const Expression *performSymbolicLoadEvaluation(Instruction *);
   const Expression *performSymbolicStoreEvaluation(Instruction *);
   const Expression *performSymbolicCallEvaluation(Instruction *);
   const Expression *performSymbolicPHIEvaluation(Instruction *);
   const Expression *performSymbolicAggrValueEvaluation(Instruction *);
   const Expression *performSymbolicCmpEvaluation(Instruction *);
+  const Expression *performSymbolicPredicateInfoEvaluation(Instruction *);
 
   // Congruence finding.
   Value *lookupOperandLeader(Value *) const;
   void performCongruenceFinding(Instruction *, const Expression *);
   void moveValueToNewCongruenceClass(Instruction *, CongruenceClass *,
                                      CongruenceClass *);
   bool setMemoryAccessEquivTo(MemoryAccess *From, CongruenceClass *To);
   MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const;
private:
   void deleteInstructionsInBlock(BasicBlock *);
 
   // New instruction creation.
   void handleNewInstruction(Instruction *){};
 
   // Various instruction touch utilities
   void markUsersTouched(Value *);
   void markMemoryUsersTouched(MemoryAccess *);
+  void markPredicateUsersTouched(Instruction *);
   void markLeaderChangeTouched(CongruenceClass *CC);
+  void addPredicateUsers(const PredicateBase *, Instruction *);
 
   // Utilities.
   void cleanupTables();
   std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
   void updateProcessedCount(Value *V);
   void verifyMemoryCongruency() const;
+  void verifyComparisons(Function &F);
   bool singleReachablePHIPath(const MemoryAccess *, const MemoryAccess *) const;
 };
 } // end anonymous namespace
 
 char NewGVN::ID = 0;
 
 // createGVNPass - The public interface to this file.
 FunctionPass *llvm::createNewGVNPass() { return new NewGVN(); }

 }
 
 const VariableExpression *NewGVN::createVariableExpression(Value *V) {
   auto *E = new (ExpressionAllocator) VariableExpression(V);
   E->setOpcode(V->getValueID());
   return E;
 }
 
+const Expression *NewGVN::createVariableOrConstant(Value *V) {
+  if (auto *C = dyn_cast<Constant>(V))
+    return createConstantExpression(C);
+  return createVariableExpression(V);
+}
+
 const ConstantExpression *NewGVN::createConstantExpression(Constant *C) {
   auto *E = new (ExpressionAllocator) ConstantExpression(C);
   E->setOpcode(C->getValueID());
   return E;
 }
 
 const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) {
   auto *E = new (ExpressionAllocator) UnknownExpression(I);
const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) {
   }
 
   const Expression *E =
       createLoadExpression(LI->getType(), LI->getPointerOperand(), LI,
                            lookupMemoryAccessEquiv(DefiningAccess));
   return E;
 }
 
+const Expression *
+NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) {
+  auto *PI = PredInfo->getPredicateInfoFor(I);
+  if (!PI)
+    return nullptr;
+
+  DEBUG(dbgs() << "Found predicate info from instruction !\n");
+  auto *CopyOf = I->getOperand(0);
+  auto *Cond = dyn_cast<Instruction>(PI->Condition);
+  if (!Cond)
+    return nullptr;
+
+  // If this a copy of the condition, it must be either true or false depending
+  // on the predicate info type and edge
+  if (CopyOf == Cond) {
+    addPredicateUsers(PI, I);
+    if (isa<PredicateAssume>(PI))
+      return createConstantExpression(ConstantInt::getTrue(Cond->getType()));
+    if (auto *PBranch = dyn_cast<PredicateBranch>(PI)) {
+      if (PBranch->TrueEdge)
+        return createConstantExpression(ConstantInt::getTrue(Cond->getType()));
+      return createConstantExpression(ConstantInt::getFalse(Cond->getType()));
+    }
+  }
+  // Not a copy of the condition, so see what the predicates tell us about this
+  // value.
+  // Not a copy of the condition, so see what the predicates tell us about this
+  // value.  First, though, we check to make sure the value is actually a copy
+  // of one of the condition operands. It's possible, in certain cases, for it
+  // to be a copy of a predicateinfo copy. In particular, if two branch
+  // operations use the same condition, and one branch dominates the other, we
+  // will end up with a copy of a copy.  This is currently a small deficiency in
+  // predicateinfo.   What will end up happening here is that we will value
+  // number both copies the same anyway.
+  if (CopyOf != Cond->getOperand(0) && CopyOf != Cond->getOperand(1)) {
+    DEBUG(dbgs() << "Copy is not of any condition operands!");
+    return nullptr;
+  }
+  Value *FirstOp = lookupOperandLeader(Cond->getOperand(0));
+  Value *SecondOp = lookupOperandLeader(Cond->getOperand(1));
+  bool SwappedOps = false;
+  // Sort the ops
+  if (shouldSwapOperands(FirstOp, SecondOp)) {
+    std::swap(FirstOp, SecondOp);
+    SwappedOps = true;
+  }
+
+  // Everything below relies on the condition being a comparison.
+  auto *Cmp = dyn_cast<CmpInst>(Cond);
+  CmpInst::Predicate Predicate =
+      SwappedOps ? Cmp->getSwappedPredicate() : Cmp->getPredicate();
+
+  if (isa<PredicateAssume>(PI)) {
+    // If the comparison is true when the operands are equal, then we know the
+    // operands are equal, because assumes must always be true.
+    if (CmpInst::isTrueWhenEqual(Predicate)) {
+      addPredicateUsers(PI, I);
+      return createVariableOrConstant(FirstOp);
+    }
+  }
+  if (const auto *PBranch = dyn_cast<PredicateBranch>(PI)) {
+    // If we are *not* a copy of the comparison, we may equal to the other
+    // operand when the predicate implies something about equality of
+    // operations.  In particular, if the comparison is true/false when the
+    // operands are equal, and we are on the right edge, we know this operation
+    // is equal to something.
+    if ((PBranch->TrueEdge && Predicate == CmpInst::ICMP_EQ) ||
+        (!PBranch->TrueEdge && Predicate == CmpInst::ICMP_NE)) {
+      addPredicateUsers(PI, I);
+      return createVariableOrConstant(FirstOp);
+    }
+    // Handle the special case of floating point.
+    if (((PBranch->TrueEdge && Predicate == CmpInst::FCMP_OEQ) ||
+         (!PBranch->TrueEdge && Predicate == CmpInst::FCMP_UNE)) &&
+        isa<ConstantFP>(FirstOp) && !cast<ConstantFP>(FirstOp)->isZero()) {
+      addPredicateUsers(PI, I);
+      return createConstantExpression(cast<Constant>(FirstOp));
+    }
+  }
+  return nullptr;
+}
+
 // Evaluate read only and pure calls, and create an expression result.
 const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) {
   auto *CI = cast<CallInst>(I);
-  if (AA->doesNotAccessMemory(CI))
+  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
+    // Instrinsics with the returned attribute are copies of arguments.
+    if (auto *ReturnedValue = II->getReturnedArgOperand()) {
+      if (II->getIntrinsicID() == Intrinsic::ssa_copy)
+        if (const auto *Result = performSymbolicPredicateInfoEvaluation(I))
+          return Result;
+      return createVariableOrConstant(ReturnedValue);
+    }
+  }
+  if (AA->doesNotAccessMemory(CI)) {
     return createCallExpression(CI, nullptr);
-  if (AA->onlyReadsMemory(CI)) {
+  } else if (AA->onlyReadsMemory(CI)) {
     MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(CI);
     return createCallExpression(CI, lookupMemoryAccessEquiv(DefiningAccess));
   }
   return nullptr;
 }
 
 // Update the memory access equivalence table to say that From is equal to To,
 // and return true if this is different from what already existed in the table.
if (HasUndef) {
           return E;
     }
 
     NumGVNPhisAllSame++;
     DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
                  << "\n");
     E->deallocateOperands(ArgRecycler);
     ExpressionAllocator.Deallocate(E);
-    if (auto *C = dyn_cast<Constant>(AllSameValue))
-      return createConstantExpression(C);
-    return createVariableExpression(AllSameValue);
+    return createVariableOrConstant(AllSameValue);
   }
   return E;
 }
 
 const Expression *NewGVN::performSymbolicAggrValueEvaluation(Instruction *I) {
   if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
     auto *II = dyn_cast<IntrinsicInst>(EI->getAggregateOperand());
     if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
             Opcode, EI->getType(), II->getArgOperand(0), II->getArgOperand(1));
       }
     }
   }
 
   return createAggregateValueExpression(I);
 }
 const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) {
-  CmpInst *CI = dyn_cast<CmpInst>(I);
-  // See if our operands are equal and that implies something.
+  auto *CI = dyn_cast<CmpInst>(I);
+  // See if our operands are equal to those of a previous predicate, and if so,
+  // if it implies true or false.
   auto Op0 = lookupOperandLeader(CI->getOperand(0));
   auto Op1 = lookupOperandLeader(CI->getOperand(1));
+  auto OurPredicate = CI->getPredicate();
+  if (shouldSwapOperands(Op1, Op0)) {
+    std::swap(Op0, Op1);
+    OurPredicate = CI->getSwappedPredicate();
+  }
+
+  // Avoid processing the same info twice
+  const PredicateBase *LastPredInfo = nullptr;
+
+  // See if we know something about the comparison itself, like it is the target
+  // of an assume.
+  auto *CmpPI = PredInfo->getPredicateInfoFor(I);
+  if (dyn_cast_or_null<PredicateAssume>(CmpPI))
+    return createConstantExpression(ConstantInt::getTrue(CI->getType()));
+
   if (Op0 == Op1) {
+    // This condition does not depend on predicates, no need to add users
     if (CI->isTrueWhenEqual())
       return createConstantExpression(ConstantInt::getTrue(CI->getType()));
     else if (CI->isFalseWhenEqual())
       return createConstantExpression(ConstantInt::getFalse(CI->getType()));
   }
+
+  // NOTE: Because we are comparing both operands here and below, and using
+  // previous comparisons, we rely on fact that predicateinfo knows to mark
+  // comparisons that use renamed operands as users of the earlier comparisons.
+  // It is *not* enough to just mark predicateinfo renamed operands as users of
+  // the earlier comparisons, because the *other* operand may have changed in a
+  // 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.
+
+  // *Currently* we only check one level of comparisons back, and only mark one
+  // level back as touched when changes appen .  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
+
+  // 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;
+      // 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(BranchOp1, BranchOp0)) {
+        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(OurPredicate,
+                                                  BranchPredicate)) {
+            addPredicateUsers(PI, I);
+            return createConstantExpression(
+                ConstantInt::getTrue(CI->getType()));
+          }
+
+          if (CmpInst::isImpliedFalseByMatchingCmp(OurPredicate,
+                                                   BranchPredicate)) {
+            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.
+            // FIXME: Double check this
+            return createConstantExpression(
+                ConstantInt::getTrue(CI->getType()));
+          }
+        }
+      }
+    }
+  }
+  // Create expression will take care of simplifyCmpInst
   return createExpression(I);
 }
 
 // Substitute and symbolize the value before value numbering.
 const Expression *NewGVN::performSymbolicEvaluation(Value *V) {
   const Expression *E = nullptr;
   if (auto *C = dyn_cast<Constant>(V))
     E = createConstantExpression(C);
void NewGVN::markMemoryUsersTouched(MemoryAccess *MA) {
   for (auto U : MA->users()) {
     if (auto *MUD = dyn_cast<MemoryUseOrDef>(U))
       TouchedInstructions.set(InstrDFS.lookup(MUD->getMemoryInst()));
     else
       TouchedInstructions.set(InstrDFS.lookup(U));
   }
 }
 
+// Add I to the set of users of a given predicate.
+void NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) {
+  if (auto *PBranch = dyn_cast<PredicateBranch>(PB))
+    PredicateToUsers[PBranch->Condition].insert(I);
+  else if (auto *PAssume = dyn_cast<PredicateBranch>(PB))
+    PredicateToUsers[PAssume->Condition].insert(I);
+}
+
+// Touch all the predicates that depend on this instruction.
+void NewGVN::markPredicateUsersTouched(Instruction *I) {
+  const auto Result = PredicateToUsers.find(I);
+  if (Result != PredicateToUsers.end())
+    for (auto *User : Result->second)
+      TouchedInstructions.set(InstrDFS.lookup(User));
+}
+
 // Touch the instructions that need to be updated after a congruence class has a
 // leader change, and mark changed values.
 void NewGVN::markLeaderChangeTouched(CongruenceClass *CC) {
   for (auto M : CC->Members) {
     if (auto *I = dyn_cast<Instruction>(M))
       TouchedInstructions.set(InstrDFS.lookup(I));
     LeaderChanges.insert(M);
   }
if (ClassChanged || LeaderChanged) {
     DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << E
                  << "\n");
 
     if (ClassChanged)
       moveValueToNewCongruenceClass(I, IClass, EClass);
     markUsersTouched(I);
     if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
       markMemoryUsersTouched(MA);
+    if (auto *CI = dyn_cast<CmpInst>(I))
+      markPredicateUsersTouched(CI);
   }
 }
 
 // Process the fact that Edge (from, to) is reachable, including marking
 // any newly reachable blocks and instructions for processing.
 void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
   // Check if the Edge was reachable before.
   if (ReachableEdges.insert({From, To}).second) {
#endif
   InstrDFS.clear();
   InstructionsToErase.clear();
 
   DFSToInstr.clear();
   BlockInstRange.clear();
   TouchedInstructions.clear();
   DominatedInstRange.clear();
   MemoryAccessToClass.clear();
+  PredicateToUsers.clear();
 }
 
 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
                                                        unsigned Start) {
   unsigned End = Start;
   if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) {
     InstrDFS[MemPhi] = End++;
     DFSToInstr.emplace_back(MemPhi);
if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
                      });
       assert(std::equal(PhiOpClasses.begin(), PhiOpClasses.end(),
                         PhiOpClasses.begin()) &&
              "All MemoryPhi arguments should be in the same class");
     }
   }
 }
 
+// Re-evaluate all the comparisons after value numbering and ensure they don't
+// change. If they changed, we didn't mark them touched properly.
+void NewGVN::verifyComparisons(Function &F) {
+#ifndef NDEBUG
+  for (auto &BB : F) {
+    if (!ReachableBlocks.count(&BB))
+      continue;
+    for (auto &I : BB) {
+      if (InstructionsToErase.count(&I))
+        continue;
+      if (isa<CmpInst>(&I)) {
+        auto *CurrentVal = ValueToClass.lookup(&I);
+        valueNumberInstruction(&I);
+        assert(CurrentVal == ValueToClass.lookup(&I) &&
+               "Re-evaluating comparison changed value");
+      }
+    }
+  }
+#endif
+}
+
 // This is the main transformation entry point.
 bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
                     TargetLibraryInfo *_TLI, AliasAnalysis *_AA,
                     MemorySSA *_MSSA) {
   bool Changed = false;
   NumFuncArgs = F.arg_size();
   DT = _DT;
   AC = _AC;
   TLI = _TLI;
   AA = _AA;
   MSSA = _MSSA;
+  PredInfo = make_unique<PredicateInfo>(F, *DT, *AC);
   DL = &F.getParent()->getDataLayout();
   MSSAWalker = MSSA->getWalker();
 
   // Count number of instructions for sizing of hash tables, and come
   // up with a global dfs numbering for instructions.
   unsigned ICount = 1;
   // Add an empty instruction to account for the fact that we start at 1
   DFSToInstr.emplace_back(nullptr);
-  // Note: We want RPO traversal of the blocks, which is not quite the same as
-  // dominator tree order, particularly with regard whether backedges get
-  // visited first or second, given a block with multiple successors.
+  // Note: We want ideal RPO traversal of the blocks, which is not quite the
+  // same as dominator tree order, particularly with regard whether backedges
+  // get visited first or second, given a block with multiple successors.
   // If we visit in the wrong order, we will end up performing N times as many
   // iterations.
   // The dominator tree does guarantee that, for a given dom tree node, it's
   // parent must occur before it in the RPO ordering. Thus, we only need to sort
   // the siblings.
   DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
   ReversePostOrderTraversal<Function *> RPOT(&F);
   unsigned Counter = 0;
bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
   initializeCongruenceClasses(F);
 
   unsigned int Iterations = 0;
   // We start out in the entry block.
   BasicBlock *LastBlock = &F.getEntryBlock();
   while (TouchedInstructions.any()) {
     ++Iterations;
     // Walk through all the instructions in all the blocks in RPO.
+    // TODO: As we hit a new block, we should push and pop equalities into a
+    // table lookupOperandLeader can use, to catch things PredicateInfo
+    // might miss, like edge-only equivalences.
     for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
          InstrNum = TouchedInstructions.find_next(InstrNum)) {
 
       // This instruction was found to be dead. We don't bother looking
       // at it again.
       if (InstrNum == 0) {
         TouchedInstructions.reset(InstrNum);
         continue;
for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
       // Reset after processing (because we may mark ourselves as touched when
       // we propagate equalities).
       TouchedInstructions.reset(InstrNum);
     }
   }
   NumGVNMaxIterations = std::max(NumGVNMaxIterations.getValue(), Iterations);
 #ifndef NDEBUG
   verifyMemoryCongruency();
+  verifyComparisons(F);
 #endif
+
   Changed |= eliminateInstructions(F);
 
   // Delete all instructions marked for deletion.
   for (Instruction *ToErase : InstructionsToErase) {
     if (!ToErase->use_empty())
       ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
 
     ToErase->eraseFromParent();
if (alwaysAvailable(Leader)) {
           // popping until we are back within a DFS scope that
           // dominates the current member.
           // Then, what happens depends on a few factors
           // If the stack is now empty, we need to push
           // If we have a constant or a local equivalence we want to
           // start using, we also push.
           // Otherwise, we walk along, processing members who are
           // dominated by this scope, and eliminate them.
-          bool ShouldPush =
-              Member && (EliminationStack.empty() || isa<Constant>(Member));
+          bool ShouldPush = Member && EliminationStack.empty();
           bool OutOfScope =
               !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
 
           if (OutOfScope || ShouldPush) {
             // Sync to our current scope.
             EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
-            ShouldPush |= Member && EliminationStack.empty();
+            bool ShouldPush = Member && EliminationStack.empty();
             if (ShouldPush) {
               EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
             }
           }
 
           // If we get to this point, and the stack is empty we must have a use
           // with nothing we can use to eliminate it, just skip it.
           if (EliminationStack.empty())
if (alwaysAvailable(Leader)) {
             continue;
 
           DEBUG(dbgs() << "Found replacement " << *Result << " for "
                        << *MemberUse->get() << " in " << *(MemberUse->getUser())
                        << "\n");
 
           // If we replaced something in an instruction, handle the patching of
           // metadata.
-          if (auto *ReplacedInst = dyn_cast<Instruction>(MemberUse->get()))
+          if (auto *ReplacedInst = dyn_cast<Instruction>(MemberUse->get())) {
+            // Skip this if we are replacing predicateinfo with its original
+            // operand, as we already know we can just drop it.
+            auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
+            if (!PI || Result != PI->OriginalOp)
               patchReplacementInstruction(ReplacedInst, Result);
+          }
 
           assert(isa<Instruction>(MemberUse->getUser()));
           MemberUse->set(Result);
           AnythingReplaced = true;
         }
       }
     }
 

 }
 
 // This is a function that says whether two commutative operations should
 // have their order swapped when canonicalizing.
 bool NewGVN::shouldSwapOperands(const Value *A, const Value *B) const {
   // Because we only care about a total ordering, and don't rewrite expressions
   // in this order, we order by rank, which will give a strict weak ordering to
   // everything but constants, and then we order by pointer address.
-    return std::make_pair(getRank(A), A) > std::make_pair(getRank(B), B);
 }

llvm/trunk/test/Transforms/NewGVN/condprop.ll

-; XFAIL: *
 ; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s
 
-@a = external global i32    ; <i32*> [#uses=7]
-
-; CHECK-LABEL: @test1(
-define i32 @test1() nounwind {
-entry:
-  %0 = load i32, i32* @a, align 4
-  %1 = icmp eq i32 %0, 4
-  br i1 %1, label %bb, label %bb1
-
-bb:   ; preds = %entry
-  br label %bb8
-
-bb1:    ; preds = %entry
-  %2 = load i32, i32* @a, align 4
-  %3 = icmp eq i32 %2, 5
-  br i1 %3, label %bb2, label %bb3
-
-bb2:    ; preds = %bb1
-  br label %bb8
-
-bb3:    ; preds = %bb1
-  %4 = load i32, i32* @a, align 4
-  %5 = icmp eq i32 %4, 4
-; CHECK: br i1 false, label %bb4, label %bb5
-  br i1 %5, label %bb4, label %bb5
-
-bb4:    ; preds = %bb3
-  %6 = load i32, i32* @a, align 4
-  %7 = add i32 %6, 5
-  br label %bb8
-
-bb5:    ; preds = %bb3
-  %8 = load i32, i32* @a, align 4
-  %9 = icmp eq i32 %8, 5
-; CHECK: br i1 false, label %bb6, label %bb7
-  br i1 %9, label %bb6, label %bb7
-
-bb6:    ; preds = %bb5
-  %10 = load i32, i32* @a, align 4
-  %11 = add i32 %10, 4
-  br label %bb8
-
-bb7:    ; preds = %bb5
-  %12 = load i32, i32* @a, align 4
-  br label %bb8
-
-bb8:    ; preds = %bb7, %bb6, %bb4, %bb2, %bb
-  %.0 = phi i32 [ %12, %bb7 ], [ %11, %bb6 ], [ %7, %bb4 ], [ 4, %bb2 ], [ 5, %bb ]
-  br label %return
-
-return:   ; preds = %bb8
-  ret i32 %.0
-}
 
 declare void @foo(i1)
 declare void @bar(i32)
 
 ; CHECK-LABEL: @test3(
 define void @test3(i32 %x, i32 %y) {
   %xz = icmp eq i32 %x, 0
   %yz = icmp eq i32 %y, 0

 ; CHECK: call void @bar(i32 0)
   ret void
 nope:
   call void @foo(i1 %z)
 ; CHECK: call void @foo(i1 false)
   ret void
 }
 
-; CHECK-LABEL: @test4(
-define void @test4(i1 %b, i32 %x) {
-  br i1 %b, label %sw, label %case3
-sw:
-  switch i32 %x, label %default [
-    i32 0, label %case0
-    i32 1, label %case1
-    i32 2, label %case0
-    i32 3, label %case3
-    i32 4, label %default
-  ]
-default:
-; CHECK: default:
-  call void @bar(i32 %x)
-; CHECK: call void @bar(i32 %x)
-  ret void
-case0:
-; CHECK: case0:
-  call void @bar(i32 %x)
-; CHECK: call void @bar(i32 %x)
-  ret void
-case1:
-; CHECK: case1:
-  call void @bar(i32 %x)
-; CHECK: call void @bar(i32 1)
-  ret void
-case3:
-; CHECK: case3:
-  call void @bar(i32 %x)
-; CHECK: call void @bar(i32 %x)
-  ret void
-}
-
 ; CHECK-LABEL: @test5(
 define i1 @test5(i32 %x, i32 %y) {
   %cmp = icmp eq i32 %x, %y
   br i1 %cmp, label %same, label %different
 
 same:
   %cmp2 = icmp ne i32 %x, %y
 ; CHECK: ret i1 false
   ret i1 %cmp2
 
 different:
   %cmp3 = icmp eq i32 %x, %y
 ; CHECK: ret i1 false
   ret i1 %cmp3
 }
 
-; CHECK-LABEL: @test6(
-define i1 @test6(i32 %x, i32 %y) {
-  %cmp2 = icmp ne i32 %x, %y
-  %cmp = icmp eq i32 %x, %y
-  %cmp3 = icmp eq i32 %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-; CHECK: ret i1 false
-  ret i1 %cmp2
-
-different:
-; CHECK: ret i1 false
-  ret i1 %cmp3
-}
-
-; CHECK-LABEL: @test6_fp(
-define i1 @test6_fp(float %x, float %y) {
-  %cmp2 = fcmp une float %x, %y
-  %cmp = fcmp oeq float %x, %y
-  %cmp3 = fcmp oeq float  %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-; CHECK: ret i1 false
-  ret i1 %cmp2
-
-different:
-; CHECK: ret i1 false
-  ret i1 %cmp3
-}
 
 ; CHECK-LABEL: @test7(
 define i1 @test7(i32 %x, i32 %y) {
   %cmp = icmp sgt i32 %x, %y
   br i1 %cmp, label %same, label %different
 
 same:
   %cmp2 = icmp sle i32 %x, %y
; CHECK: ret i1 false
   ret i1 %cmp2
 
 different:
   %cmp3 = fcmp ogt float %x, %y
 ; CHECK: ret i1 false
   ret i1 %cmp3
 }
 
-; CHECK-LABEL: @test8(
-define i1 @test8(i32 %x, i32 %y) {
-  %cmp2 = icmp sle i32 %x, %y
-  %cmp = icmp sgt i32 %x, %y
-  %cmp3 = icmp sgt i32 %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-; CHECK: ret i1 false
-  ret i1 %cmp2
-
-different:
-; CHECK: ret i1 false
-  ret i1 %cmp3
-}
-
-; CHECK-LABEL: @test8_fp(
-define i1 @test8_fp(float %x, float %y) {
-  %cmp2 = fcmp ule float %x, %y
-  %cmp = fcmp ogt float %x, %y
-  %cmp3 = fcmp ogt float %x, %y
-  br i1 %cmp, label %same, label %different
-
-same:
-; CHECK: ret i1 false
-  ret i1 %cmp2
-
-different:
-; CHECK: ret i1 false
-  ret i1 %cmp3
-}
-
 ; PR1768
 ; CHECK-LABEL: @test9(
 define i32 @test9(i32 %i, i32 %j) {
   %cmp = icmp eq i32 %i, %j
   br i1 %cmp, label %cond_true, label %ret
 
 cond_true:
   %diff = sub i32 %i, %j

llvm/trunk/test/Transforms/NewGVN/predicates.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -basicaa -newgvn -S < %s | FileCheck %s
+
+; Function Attrs: noinline norecurse nounwind readonly ssp uwtable
+define i32 @mp_unsgn_cmp(i32 %n, i32* nocapture readonly %in1, i32* nocapture readonly %in2) local_unnamed_addr {
+; CHECK-LABEL: @mp_unsgn_cmp(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP11:%.*]] = icmp sgt i32 [[N:%.*]], -1
+; CHECK-NEXT:    br i1 [[CMP11]], label [[FOR_INC_PREHEADER:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       for.inc.preheader:
+; CHECK-NEXT:    br label [[FOR_INC:%.*]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[STOREMERGE2:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_INC]] ], [ 0, [[FOR_INC_PREHEADER]] ]
+; CHECK-NEXT:    [[IDXPROM:%.*]] = sext i32 [[STOREMERGE2]] to i64
+; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[IN1:%.*]], i64 [[IDXPROM]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds i32, i32* [[IN2:%.*]], i64 [[IDXPROM]]
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[ARRAYIDX4]], align 4
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[STOREMERGE2]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[STOREMERGE2]], [[N]]
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[SUB]], 0
+; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP2]], [[CMP1]]
+; CHECK-NEXT:    br i1 [[OR_COND]], label [[FOR_INC]], label [[FOR_END:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[CMP5:%.*]] = icmp sgt i32 [[SUB]], 0
+; CHECK-NEXT:    br i1 [[CMP5]], label [[IF_END8:%.*]], label [[IF_ELSE]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[SUB1_LCSSA4:%.*]] = phi i32 [ [[SUB]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[CMP6:%.*]] = icmp slt i32 [[SUB1_LCSSA4]], 0
+; CHECK-NEXT:    [[DOTSUB1_LCSSA:%.*]] = select i1 [[CMP6]], i32 -1, i32 [[SUB1_LCSSA4]]
+; CHECK-NEXT:    ret i32 [[DOTSUB1_LCSSA]]
+; CHECK:       if.end8:
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  %cmp11 = icmp sgt i32 %n, -1
+  br i1 %cmp11, label %for.inc.preheader, label %if.else
+
+for.inc.preheader:                                ; preds = %entry
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.inc.preheader, %for.inc
+  %storemerge2 = phi i32 [ %inc, %for.inc ], [ 0, %for.inc.preheader ]
+  %idxprom = sext i32 %storemerge2 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %in1, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx4 = getelementptr inbounds i32, i32* %in2, i64 %idxprom
+  %1 = load i32, i32* %arrayidx4, align 4
+  %sub = sub nsw i32 %0, %1
+  %inc = add nsw i32 %storemerge2, 1
+  %cmp1 = icmp slt i32 %storemerge2, %n
+  %cmp2 = icmp eq i32 %sub, 0
+  %or.cond = and i1 %cmp2, %cmp1
+;; This is a self-critical edge to for.inc. If we insert predicate info on it, we will insert
+;; predicateinfo at the end of this block, and think it dominates everthing using only dfs
+;; numbers, instead of proper edge dominance.  We would then proceed to propagate the true value
+;; of sub == 0 everywhere, making this function only ever return 0.
+  br i1 %or.cond, label %for.inc, label %for.end
+
+for.end:                                          ; preds = %for.inc
+  %sub.lcssa = phi i32 [ %sub, %for.inc ]
+  %cmp5 = icmp sgt i32 %sub.lcssa, 0
+  br i1 %cmp5, label %if.end8, label %if.else
+
+if.else:                                          ; preds = %entry, %for.end
+  %sub1.lcssa4 = phi i32 [ %sub.lcssa, %for.end ], [ 0, %entry ]
+  %cmp6 = icmp slt i32 %sub1.lcssa4, 0
+  %.sub1.lcssa = select i1 %cmp6, i32 -1, i32 %sub1.lcssa4
+  ret i32 %.sub1.lcssa
+
+if.end8:                                          ; preds = %for.end
+  ret i32 1
+}
+
+
+;; This test will generate a copy of a copy of predicateinfo to the multiple uses
+;; of branch conditions below.  Make sure we don't try to extract operand info.
+; Function Attrs: uwtable
+define fastcc void @barney() {
+; CHECK-LABEL: @barney(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB22:%.*]]
+; CHECK:       bb22:
+; CHECK-NEXT:    br i1 undef, label [[BB29:%.*]], label [[BB35:%.*]]
+; CHECK:       bb29:
+; CHECK-NEXT:    br i1 true, label [[BB33:%.*]], label [[BB35]]
+; CHECK:       bb33:
+; CHECK-NEXT:    br i1 true, label [[BB35]], label [[BB35]]
+; CHECK:       bb35:
+; CHECK-NEXT:    unreachable
+;
+bb:
+  br label %bb22
+bb22:                                             ; preds = %bb21
+  %tmp23 = icmp eq i32 undef, 2
+  br i1 %tmp23, label %bb29, label %bb35
+
+
+bb29:                                             ; preds = %bb28
+  br i1 %tmp23, label %bb33, label %bb35
+
+
+bb33:                                             ; preds = %bb31
+  br i1 %tmp23, label %bb35, label %bb35
+
+
+bb35:                                             ; preds = %bb33, %bb29, %bb22
+  unreachable
+}
+

llvm/trunk/test/Transforms/NewGVN/storeoverstore.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -newgvn -S < %s | FileCheck %s
 ; RUN: opt -passes=newgvn -S -o - %s | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ;; All the loads in this testcase are useless, but it requires understanding that repeated
 ;; stores of the same value do not change the memory state to eliminate them.
 
 define i32 @foo(i32*, i32)  {
-; CHECK-LABEL: @foo
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:    store i32 5, i32* [[TMP0:%.*]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP1:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]]
+; CHECK:         br label [[TMP5]]
+; CHECK:         [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP2:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP6:%.*]], label [[TMP8:%.*]]
+; CHECK:         [[TMP7:%.*]] = add nsw i32 [[DOT0]], 5
+; CHECK-NEXT:    br label [[TMP8]]
+; CHECK:         [[DOT1:%.*]] = phi i32 [ [[TMP7]], [[TMP6]] ], [ [[DOT0]], [[TMP5]] ]
+; CHECK-NEXT:    ret i32 [[DOT1]]
+;
   store i32 5, i32* %0, align 4
   %3 = icmp ne i32 %1, 0
   br i1 %3, label %4, label %7
 
 ; <label>:4:                                      ; preds = %2
-; CHECK-NOT: load
   %5 = load i32, i32* %0, align 4
-; CHECK-NOT: add
   %6 = add nsw i32 5, %5
   br label %7
 
 ; <label>:7:                                      ; preds = %4, %2
   %.0 = phi i32 [ %6, %4 ], [ 5, %2 ]
-; CHECK: phi i32 [ 10, %4 ], [ 5, %2 ]
   store i32 5, i32* %0, align 4
-; CHECK-NOT: icmp
   %8 = icmp ne i32 %1, 0
-; CHECK: br i1 %3
   br i1 %8, label %9, label %12
 
 ; <label>:9:                                      ; preds = %7
-; CHECK-NOT: load
   %10 = load i32, i32* %0, align 4
-; CHECK: add nsw i32 %.0, 5
   %11 = add nsw i32 %.0, %10
   br label %12
 
 ; <label>:12:                                     ; preds = %9, %7
   %.1 = phi i32 [ %11, %9 ], [ %.0, %7 ]
   ret i32 %.1
 }
 
 ;; This is similar to the above, but it is a conditional store of the same value
 ;; which requires value numbering MemoryPhi properly to resolve.
 define i32 @foo2(i32*, i32)  {
-; CHECK-LABEL: @foo2
+; CHECK-LABEL: @foo2(
+; CHECK-NEXT:    store i32 5, i32* [[TMP0:%.*]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP1:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]]
+; CHECK:         br label [[TMP6:%.*]]
+; CHECK:         br label [[TMP6]]
+; CHECK:         [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP5]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP7:%.*]], label [[TMP9:%.*]]
+; CHECK:         [[TMP8:%.*]] = add nsw i32 [[DOT0]], 5
+; CHECK-NEXT:    br label [[TMP9]]
+; CHECK:         [[DOT1:%.*]] = phi i32 [ [[TMP8]], [[TMP7]] ], [ [[DOT0]], [[TMP6]] ]
+; CHECK-NEXT:    ret i32 [[DOT1]]
+;
   store i32 5, i32* %0, align 4
   %3 = icmp ne i32 %1, 0
   br i1 %3, label %4, label %7
 
 ; <label>:4:                                      ; preds = %2
-; CHECK-NOT: load
   %5 = load i32, i32* %0, align 4
-; CHECK-NOT: add
   %6 = add nsw i32 5, %5
   br label %8
 
 ; <label>:7:                                      ; preds = %2
   store i32 5, i32* %0, align 4
   br label %8
 
 ; <label>:8:                                      ; preds = %7, %4
-; CHECK: phi i32 [ 10, %4 ], [ 5, %5 ]
   %.0 = phi i32 [ %6, %4 ], [ 5, %7 ]
-; CHECK-NOT: icmp
   %9 = icmp ne i32 %1, 0
-; CHECK: br i1 %3
   br i1 %9, label %10, label %13
 
 ; <label>:10:                                     ; preds = %8
-; CHECK-NOT: load
   %11 = load i32, i32* %0, align 4
-; CHECK: add nsw i32 %.0, 5
   %12 = add nsw i32 %.0, %11
   br label %13
 
 ; <label>:13:                                     ; preds = %10, %8
   %.1 = phi i32 [ %12, %10 ], [ %.0, %8 ]
   ret i32 %.1
 }