Last of the major pieces to NewGVN - yay!

[• dberlin]

Summary

NewGVN: Handle equivalence between phi of ops and op of phis.

This makes our GVN mostly-complete. It would be complete, modulo some
deliberate choices we make. This means it detects roughly all herband
equivalences in polynomial time, including cases notoriously hard for
other GVN's to detect. It also detects a very large swath of the
cases we currently rely on instcombine to detect that involve folding
upwards through phis.

I am still doing benchmarking, tweaking, and testing. on our current
approach, but this was getting large enough to throw up here.

Fixes PR 31125, 31463, PR 31868

[• dberlin]

• Add some more comments

[Prazek]

Good job! How many of old gvn tests are still failing with newgvn?

include/llvm/Transforms/Scalar/GVNExpression.h

487

member initialization instead? (bool AllRealOps = false;)

lib/Transforms/Scalar/NewGVN.cpp

1734

does this comment still hold?

1818–1819

The second if expression seems to be cheaper, and they seems to be independent. What about switching them?

2031

debug?

[• dberlin]

In D32151#728967, @Prazek wrote:

Good job! How many of old gvn tests are still failing with newgvn?

Of them:

1. NewGVN passes all but one or two subtest of each of them.
2. Most of them are things we need to fix in other infrastructure (IE be able to have simplification use value numbering to ignore blocks, etc).
3. The one significant one is that we don't insert inequalities temporarily, which means that we don't eliminate opposite icmps that are not branches.

IE we will handle:

if (a)
  if (!a)

but not:
icmp a == b
icmp a != b

NewGVN is actually on by default for a number of significant LLVM users at this point :)
It also has 15 tests that *GVN* doesn't pass.

Our goal was never to try to get every GVN test before we turned it on by default, only not regress performance :)
Most people already felt GVN did too much.
I suspect we will meet that goal.

[Prazek]

In D32151#729291, @dberlin wrote:

In D32151#728967, @Prazek wrote:

Good job! How many of old gvn tests are still failing with newgvn?

Of them:

1. NewGVN passes all but one or two subtest of each of them.
2. Most of them are things we need to fix in other infrastructure (IE be able to have simplification use value numbering to ignore blocks, etc).
3. The one significant one is that we don't insert inequalities temporarily, which means that we don't eliminate opposite icmps that are not branches.

IE we will handle:

if (a)
  if (!a)

but not:
icmp a == b
icmp a != b

NewGVN is actually on by default for a number of significant LLVM users at this point :)
It also has 15 tests that *GVN* doesn't pass.

Our goal was never to try to get every GVN test before we turned it on by default, only not regress performance :)
Most people already felt GVN did too much.
I suspect we will meet that goal.

Awesome news! I will try to fix the MemorySSA to support invariant.groups, but for that I will need your help (see the mail) :)

[davide]

This is really nice =)
I'll do some performance testing myself tomorrow, some comments in the meanwhile.

lib/Transforms/Scalar/NewGVN.cpp

714–718

I see how you're looking at the RPO ordering to determine if it's a backedge, but for people reading the code for the first time, maybe we can add a longer comment (maybe an example?)

730–732

Style'ish, ternary operator (up to you, can be a later cleanup).

2031

DEBUG or comment out.

2076

I think hiding getMemoryAccess in an helper is nice, but can be split.

3345

unrelated?

3350

unrelated?

[• dberlin]

Still tracking down all the bugs this exposes elsewhere (last count, 1 BasicAA bug, 2 instructionsimplify bugs, etc).
sigh.

[• dberlin]

• First version of rewritten, on-demand, phi of ops. Gets rid of need for most temp instructions.

This passes bootstrap and test. I'm tuning it (we are likely to have to tune the amount of selects and adds it handles to not screw up iv analysis, etc).

[• dberlin]

Oh look, i accidentally git add'd a diff file.
Just ignore it.

[• dberlin]

(I also will clean up the dead code you see in some places)

[davide]

I'm running tests on this one during the week.

[• dberlin]

• Updated to not hash expressions twice.

[davide]

LGTM. I think we can iterate on this in tree. Thank you so much for this piece of work!

lib/Analysis/BasicAliasAnalysis.cpp

686–688 ↗

(On Diff #98192)

This is unrelated (but you already anticipated).

lib/Transforms/Scalar/NewGVN.cpp

2357–2359

I starred at this very closely and I think it's correct.

include/llvm/Transforms/Scalar/GVNExpression.h

public:
   int_op_inserter &operator*() { return *this; }
   int_op_inserter &operator++() { return *this; }
   int_op_inserter &operator++(int) { return *this; }
 };
 
 class PHIExpression final : public BasicExpression {
 private:
   BasicBlock *BB;
+  // True if all the operands of this phi expression actually exist in the
+  // program, as opposed to having been temporarily created by GVN.
+  bool AllRealOps;
 
 public:
   PHIExpression(unsigned NumOperands, BasicBlock *B)
-      : BasicExpression(NumOperands, ET_Phi), BB(B) {}
+      : BasicExpression(NumOperands, ET_Phi), BB(B), AllRealOps(false) {}
   PHIExpression() = delete;
   PHIExpression(const PHIExpression &) = delete;
   PHIExpression &operator=(const PHIExpression &) = delete;
   ~PHIExpression() override;
 
   static bool classof(const Expression *EB) {
     return EB->getExpressionType() == ET_Phi;
   }
 
+  bool isAllRealOps() const { return AllRealOps; }
+  void setAllRealOps(bool B) { AllRealOps = B; }
+
   bool equals(const Expression &Other) const override {
     if (!this->BasicExpression::equals(Other))
       return false;
     const PHIExpression &OE = cast<PHIExpression>(Other);
     return BB == OE.BB;
   }
 
   hash_code getHashValue() const override {

lib/Transforms/Scalar/NewGVN.cpp

 /// get updated properly.  In constrast, the sparse algorithm we use *also*
 /// tracks what operations have a given value number (IE it also tracks the
 /// reverse mapping from value number -> operations with that value number), so
 /// that it only needs to reprocess the instructions that are affected when
 /// something's value number changes.  The rest of the algorithm is devoted to
 /// performing symbolic evaluation, forward propagation, and simplification of
 /// operations based on the value numbers deduced so far.
 ///
+/// In order to make the GVN complete, we use a technique derived from
+/// "Detection of Redundant Expressions: A Complete and Polynomial-time
+/// Algorithm in SSA" by R.R. Pai.  The source of incompleteness in most SSA
+/// based GVN algorithms is related to their inability to detect equivalence
+/// between phi of ops (IE phi(a+b, c+d)) and op of phis (phi(a,c) + phi(b, d)).
+/// We resolve this issue by generating the equivalent "phi of ops" form for
+/// each
+/// op of phis we see, in a way that only takes polynomial time to resolve.
+///
 /// We also do not perform elimination by using any published algorithm.  All
 /// published algorithms are O(Instructions). Instead, we use a technique that
 /// is O(number of operations with the same value number), enabling us to skip
 /// trying to eliminate things that have unique value numbers.
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/NewGVN.h"
 #include "llvm/ADT/BitVector.h"

 }
 }
 
 // Tarjan's SCC finding algorithm with Nuutila's improvements
 // SCCIterator is actually fairly complex for the simple thing we want.
 // It also wants to hand us SCC's that are unrelated to the phi node we ask
 // about, and have us process them there or risk redoing work.
 // Graph traits over a filter iterator also doesn't work that well here.
-// This SCC finder is specialized to walk use-def chains, and only follows instructions,
+// This SCC finder is specialized to walk use-def chains, and only follows
+// instructions,
 // not generic values (arguments, etc).
 struct TarjanSCC {
 
   TarjanSCC() : Components(1) {}
 
   void Start(const Instruction *Start) {
     if (Root.lookup(Start) == 0)
       FindSCC(Start);
void FindSCC(const Instruction *I) {
     for (auto &Op : I->operands()) {
       if (auto *InstOp = dyn_cast<Instruction>(Op)) {
         if (Root.lookup(Op) == 0)
           FindSCC(InstOp);
         if (!InComponent.count(Op))
           Root[I] = std::min(Root.lookup(I), Root.lookup(Op));
       }
     }
-    // See if we really were the root of a component, by seeing if we still have our DFSNumber.
-    // If we do, we are the root of the component, and we have completed a component. If we do not,
+    // See if we really were the root of a component, by seeing if we still have
+    // our DFSNumber.
+    // If we do, we are the root of the component, and we have completed a
+    // component. If we do not,
     // we are not the root of a component, and belong on the component stack.
     if (Root.lookup(I) == OurDFS) {
       unsigned ComponentID = Components.size();
       Components.resize(Components.size() + 1);
       auto &Component = Components.back();
       Component.insert(I);
       DEBUG(dbgs() << "Component root is " << *I << "\n");
       InComponent.insert(I);
class NewGVN {
   // equivalent to everything.
   CongruenceClass *TOPClass;
   std::vector<CongruenceClass *> CongruenceClasses;
   unsigned NextCongruenceNum;
 
   // Value Mappings.
   DenseMap<Value *, CongruenceClass *> ValueToClass;
   DenseMap<Value *, const Expression *> ValueToExpression;
+  // Value PHI handling, used to make equivalence between phi(op, op) and
+  // op(phi, phi).
+  DenseMap<const Value *, BasicBlock *> TempToBlock;
+  DenseMap<const Value *, Value *> RealToTemp;
+  DenseMap<const Value *, Value *> TempToReal;
+  DenseMap<const BasicBlock *, SmallVector<Instruction *, 8>> PHIOfOpsOps;
+  DenseMap<const BasicBlock *, SmallVector<Instruction *, 8>> PHIOfOpsPHIs;
+  DenseMap<const Instruction *, MemoryUseOrDef *> TempToMemory;
+  DenseMap<const MemoryAccess *, SmallPtrSet<Instruction *, 8>>
+      MemoryToTempUsers;
+  DenseSet<Instruction *> AllTempInstructions;
 
   // 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;
   // Mapping from MemoryAccess we used to the MemoryAccess we used it with.  Has
   // the same reasoning as PredicateToUsers.  When we skip MemoryAccesses for
NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
         PredInfo(make_unique<PredicateInfo>(F, *DT, *AC)) {}
   bool runGVN();
 
 private:
   // Expression handling.
   const Expression *createExpression(Instruction *);
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *);
   PHIExpression *createPHIExpression(Instruction *, bool &HasBackedge,
-                                     bool &AllConstant);
+                                     bool &OriginalOpsConstant);
   const VariableExpression *createVariableExpression(Value *);
   const ConstantExpression *createConstantExpression(Constant *);
   const Expression *createVariableOrConstant(Value *V);
   const UnknownExpression *createUnknownExpression(Instruction *);
   const StoreExpression *createStoreExpression(StoreInst *,
                                                const MemoryAccess *);
   LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
                                        const MemoryAccess *);
private:
 
   CongruenceClass *createSingletonCongruenceClass(Value *Member) {
     CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
     CClass->insert(Member);
     ValueToClass[Member] = CClass;
     return CClass;
   }
   void initializeCongruenceClasses(Function &F);
+  bool makePossiblePhiOfOps(Instruction *, bool);
+  void addPhiOfOpsOrOp(Instruction *Op, SmallVectorImpl<Instruction *> &Vect,
+                       BasicBlock *BB, MemoryUseOrDef *MemAccess,
+                       Value *ExistingValue = nullptr);
 
   // Value number an Instruction or MemoryPhi.
   void valueNumberMemoryPhi(MemoryPhi *);
   void valueNumberInstruction(Instruction *);
 
   // Symbolic evaluation.
   const Expression *checkSimplificationResults(Expression *, Instruction *,
                                                Value *);
private:
   void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U);
 
   // Main loop of value numbering
   void iterateTouchedInstructions();
 
   // Utilities.
   void cleanupTables();
   std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
-  void updateProcessedCount(Value *V);
+  void updateProcessedCount(const Value *V);
   void verifyMemoryCongruency() const;
   void verifyIterationSettled(Function &F);
   bool singleReachablePHIPath(const MemoryAccess *, const MemoryAccess *) const;
   BasicBlock *getBlockForValue(Value *V) const;
   void deleteExpression(const Expression *E);
+  MemoryUseOrDef *getMemoryAccess(const Instruction *) const;
+  MemoryPhi *getMemoryAccess(const BasicBlock *) const;
+  template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
   unsigned InstrToDFSNum(const Value *V) const {
     assert(isa<Instruction>(V) && "This should not be used for MemoryAccesses");
     return InstrDFS.lookup(V);
   }
 
   unsigned InstrToDFSNum(const MemoryAccess *MA) const {
     return MemoryToDFSNum(MA);
   }
   Value *InstrFromDFSNum(unsigned DFSNum) { return DFSToInstr[DFSNum]; }
   // Given a MemoryAccess, return the relevant instruction DFS number.  Note:
   // This deliberately takes a value so it can be used with Use's, which will
   // auto-convert to Value's but not to MemoryAccess's.
   unsigned MemoryToDFSNum(const Value *MA) const {
     assert(isa<MemoryAccess>(MA) &&
            "This should not be used with instructions");
     return isa<MemoryUseOrDef>(MA)
                ? InstrToDFSNum(cast<MemoryUseOrDef>(MA)->getMemoryInst())
                : InstrDFS.lookup(MA);
   }
   bool isCycleFree(const PHINode *PN);
-  template <class T, class Range> T *getMinDFSOfRange(const Range &) const;
+  bool isBackedge(BasicBlock *From, BasicBlock *To) const;
   // Debug counter info.  When verifying, we have to reset the value numbering
   // debug counter to the same state it started in to get the same results.
   std::pair<int, int> StartingVNCounter;
 };
 } // end anonymous namespace
 
 template <typename T>
 static bool equalsLoadStoreHelper(const T &LHS, const Expression &RHS) {
if (!equalsLoadStoreHelper(*this, Other))
     return false;
   // Make sure that store vs store includes the value operand.
   if (const auto *S = dyn_cast<StoreExpression>(&Other))
     if (getStoredValue() != S->getStoredValue())
       return false;
   return true;
 }
 
+// Determine if the edge From->To is a backedge
+bool NewGVN::isBackedge(BasicBlock *From, BasicBlock *To) const {
+  if (From == To)
+    return true;
+  auto *FromDTN = DT->getNode(From);
+  auto *ToDTN = DT->getNode(To);
+  return RPOOrdering.lookup(FromDTN) >= RPOOrdering.lookup(ToDTN);
+}
+
 #ifndef NDEBUG
 static std::string getBlockName(const BasicBlock *B) {
   return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, nullptr);
 }
 #endif
 
+// Get a MemoryAccess for an instruction, fake or real.
+MemoryUseOrDef *NewGVN::getMemoryAccess(const Instruction *I) const {
+  auto *Result = MSSA->getMemoryAccess(I);
+  if (Result)
+    return Result;
+  return TempToMemory.lookup(I);
+}
+
+// Get a MemoryPhi for a basic block. These are all real.
+MemoryPhi *NewGVN::getMemoryAccess(const BasicBlock *BB) const {
+  return MSSA->getMemoryAccess(BB);
+}
+
 // Get the basic block from an instruction/memory value.
 BasicBlock *NewGVN::getBlockForValue(Value *V) const {
-  if (auto *I = dyn_cast<Instruction>(V))
-    return I->getParent();
-  else if (auto *MP = dyn_cast<MemoryPhi>(V))
-    return MP->getBlock();
-  llvm_unreachable("Should have been able to figure out a block for our value");
-  return nullptr;
+  if (auto *I = dyn_cast<Instruction>(V)) {
+    auto *Parent = I->getParent();
+    if (Parent)
+      return Parent;
+    Parent = TempToBlock.lookup(V);
+    assert(Parent && "Every fake instruction should have a block");
+    return Parent;
+  }
+
+  auto *MP = dyn_cast<MemoryPhi>(V);
+  assert(MP && "Should have been an instruction or a MemoryPhi");
 }
 
 // Delete a definitely dead expression, so it can be reused by the expression
 // allocator.  Some of these are not in creation functions, so we have to accept
 // const versions.
 void NewGVN::deleteExpression(const Expression *E) {
   assert(isa<BasicExpression>(E));
   auto *BE = cast<BasicExpression>(E);
   const_cast<BasicExpression *>(BE)->deallocateOperands(ArgRecycler);
   ExpressionAllocator.Deallocate(E);
 }
-
 PHIExpression *NewGVN::createPHIExpression(Instruction *I, bool &HasBackedge,
-                                           bool &AllConstant) {
-  BasicBlock *PHIBlock = I->getParent();
+                                           bool &OriginalOpsConstant) {
+  BasicBlock *PHIBlock = getBlockForValue(I);
   auto *PN = cast<PHINode>(I);
   auto *E =
       new (ExpressionAllocator) PHIExpression(PN->getNumOperands(), PHIBlock);
 
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
   E->setType(I->getType());
   E->setOpcode(I->getOpcode());
 
-  unsigned PHIRPO = RPOOrdering.lookup(DT->getNode(PHIBlock));
-
   // Filter out unreachable phi operands.
   auto Filtered = make_filter_range(PN->operands(), [&](const Use &U) {
     return ReachableEdges.count({PN->getIncomingBlock(U), PHIBlock});
   });
-
-  std::transform(Filtered.begin(), Filtered.end(), op_inserter(E),
-                 [&](const Use &U) -> Value * {
-                   auto *BB = PN->getIncomingBlock(U);
-                   auto *DTN = DT->getNode(BB);
-                   if (RPOOrdering.lookup(DTN) >= PHIRPO)
-                     HasBackedge = true;
-                   AllConstant &= isa<UndefValue>(U) || isa<Constant>(U);
+  bool AllRealOps = true;
+  std::transform(
+      Filtered.begin(), Filtered.end(), op_inserter(E),
+        HasBackedge = HasBackedge || isBackedge(BB, PHIBlock);
+        OriginalOpsConstant =
+            OriginalOpsConstant && (isa<UndefValue>(U) || isa<Constant>(U));
 
-                   // Don't try to transform self-defined phis.
-                   if (U == PN)
-                     return PN;
-                   return lookupOperandLeader(U);
-                 });
+        if (U == PN) {
+          AllRealOps = false;
+        }
+
+        Value *LOL = lookupOperandLeader(U);
+        AllRealOps = AllRealOps &&
+                     (isa<Constant>(LOL) ||
+                      (isa<Instruction>(LOL) &&
+                       !AllTempInstructions.count(cast<Instruction>(LOL))));
+        return LOL;
+
+  E->setAllRealOps(AllRealOps);
   return E;
 }
 
 // Set basic expression info (Arguments, type, opcode) for Expression
 // E from Instruction I in block B.
 bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E) {
   bool AllConstant = true;
   if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
     E->setType(GEP->getSourceElementType());
   else
     E->setType(I->getType());
   E->setOpcode(I->getOpcode());
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
 
   // Transform the operand array into an operand leader array, and keep track of
   // whether all members are constant.
   std::transform(I->op_begin(), I->op_end(), op_inserter(E), [&](Value *O) {
     auto Operand = lookupOperandLeader(O);
-    AllConstant &= isa<Constant>(Operand);
+    AllConstant = AllConstant && isa<Constant>(Operand);
     return Operand;
   });
 
   return AllConstant;
 }
 
 const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
                                                  Value *Arg1, Value *Arg2) {
const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI,
   // load have the same value, and thus, it isn't clobbering the load).
   return E;
 }
 
 const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I) {
   // Unlike loads, we never try to eliminate stores, so we do not check if they
   // are simple and avoid value numbering them.
   auto *SI = cast<StoreInst>(I);
-  auto *StoreAccess = MSSA->getMemoryAccess(SI);
+  auto *StoreAccess = getMemoryAccess(SI);
   // Get the expression, if any, for the RHS of the MemoryDef.
   const MemoryAccess *StoreRHS = StoreAccess->getDefiningAccess();
   if (EnableStoreRefinement)
     StoreRHS = MSSAWalker->getClobberingMemoryAccess(StoreAccess);
   // If we bypassed the use-def chains, make sure we add a use.
   if (StoreRHS != StoreAccess->getDefiningAccess())
     addMemoryUsers(StoreRHS, StoreAccess);
 
if (SI->isSimple()) {
     // Also check if our value operand is defined by a load of the same memory
     // location, and the memory state is the same as it was then (otherwise, it
     // could have been overwritten later. See test32 in
     // transforms/DeadStoreElimination/simple.ll).
     if (auto *LI =
             dyn_cast<LoadInst>(lookupOperandLeader(SI->getValueOperand()))) {
       if ((lookupOperandLeader(LI->getPointerOperand()) ==
            lookupOperandLeader(SI->getPointerOperand())) &&
-          (lookupMemoryLeader(MSSA->getMemoryAccess(LI)->getDefiningAccess()) ==
+          (lookupMemoryLeader(getMemoryAccess(LI)->getDefiningAccess()) ==
            StoreRHS))
         return createVariableExpression(LI);
     }
   }
 
   // If the store is not equivalent to anything, value number it as a store that
   // produces a unique memory state (instead of using it's MemoryUse, we use
   // it's MemoryDef).
const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I) {
   // eliminate the loads themselves.
   if (!LI->isSimple())
     return nullptr;
 
   Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand());
   // Load of undef is undef.
   if (isa<UndefValue>(LoadAddressLeader))
     return createConstantExpression(UndefValue::get(LI->getType()));
-
-  MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(I);
+  MemoryAccess *OriginalAccess = getMemoryAccess(I);
+  MemoryAccess *DefiningAccess =
+      MSSAWalker->getClobberingMemoryAccess(OriginalAccess);
 
   if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
     if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
       Instruction *DefiningInst = MD->getMemoryInst();
       // If the defining instruction is not reachable, replace with undef.
       if (!ReachableBlocks.count(DefiningInst->getParent()))
         return createConstantExpression(UndefValue::get(LI->getType()));
       // This will handle stores and memory insts.  We only do if it the
if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
         }
       }
     }
   }
   // Create expression will take care of simplifyCmpInst
   return createExpression(I);
 }
 
+// Return true if V is a value that will always be available (IE can
+// be placed anywhere) in the function.  We don't do globals here
+// because they are often worse to put in place.
+// TODO: Separate cost from availability
+static bool alwaysAvailable(Value *V) {
+  return isa<Constant>(V) || isa<Argument>(V);
+}
+
 // 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);
   else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
     E = createVariableExpression(V);
   } else {
else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
     case Instruction::ShuffleVector:
     case Instruction::GetElementPtr:
       E = createExpression(I);
       break;
     default:
       return nullptr;
     }
   }
+  // For the moment, we only make op of phis to be equivalent to phi of ops if
+  // the op of phis has generated something better.  Once we have finished
+  // completeness, we should be able to always convert one to the other.
+  if (auto *RTV = RealToTemp.lookup(V)) {
+    if (E && !isa<ConstantExpression>(E) && !isa<VariableExpression>(E)) {
+      auto *LOL = lookupOperandLeader(RTV);
+      if (alwaysAvailable(LOL))
+        return createVariableOrConstant(lookupOperandLeader(RTV));
+      auto *PHIE =
+          dyn_cast_or_null<PHIExpression>(ValueToExpression.lookup(RTV));
+      if (PHIE && PHIE->isAllRealOps())
+        return createVariableOrConstant(RTV);
+    }
+  }
+
   return E;
 }
 
 void NewGVN::markUsersTouched(Value *V) {
   // Now mark the users as touched.
   for (auto *User : V->users()) {
     assert(isa<Instruction>(User) && "Use of value not within an instruction?");
     TouchedInstructions.set(InstrToDFSNum(User));
void NewGVN::markMemoryDefTouched(const MemoryAccess *MA) {
   TouchedInstructions.set(MemoryToDFSNum(MA));
 }
 
 void NewGVN::markMemoryUsersTouched(const MemoryAccess *MA) {
   if (isa<MemoryUse>(MA))
     return;
   for (auto U : MA->users())
     TouchedInstructions.set(MemoryToDFSNum(U));
+  const auto TempResult = MemoryToTempUsers.find(MA);
+  if (TempResult != MemoryToTempUsers.end())
+    for (auto *User : TempResult->second)
+      TouchedInstructions.set(InstrToDFSNum(User));
+
   const auto Result = MemoryToUsers.find(MA);
   if (Result != MemoryToUsers.end()) {
     for (auto *User : Result->second)
       TouchedInstructions.set(MemoryToDFSNum(User));
     MemoryToUsers.erase(Result);
   }
 }
 

 const MemoryAccess *NewGVN::getNextMemoryLeader(CongruenceClass *CC) const {
   // TODO: If this ends up to slow, we can maintain a next memory leader like we
   // do for regular leaders.
   // Make sure there will be a leader to find
   assert((CC->getStoreCount() > 0 || !CC->memory_empty()) &&
          "Can't get next leader if there is none");
   if (CC->getStoreCount() > 0) {
     if (auto *NL = dyn_cast_or_null<StoreInst>(CC->getNextLeader().first))
-      return MSSA->getMemoryAccess(NL);
+      return getMemoryAccess(NL);
     // Find the store with the minimum DFS number.
     auto *V = getMinDFSOfRange<Value>(make_filter_range(
         *CC, [&](const Value *V) { return isa<StoreInst>(V); }));
-    return MSSA->getMemoryAccess(cast<StoreInst>(V));
+    return getMemoryAccess(cast<StoreInst>(V));
   }
   assert(CC->getStoreCount() == 0);
 
   // Given our assertion, hitting this part must mean
   // !OldClass->memory_empty()
   if (CC->memory_size() == 1)
     return *CC->memory_begin();
   return getMinDFSOfRange<const MemoryPhi>(CC->memory());

 
 // Move a value, currently in OldClass, to be part of NewClass
 // Update OldClass and NewClass for the move (including changing leaders, etc).
 void NewGVN::moveValueToNewCongruenceClass(Instruction *I, const Expression *E,
                                            CongruenceClass *OldClass,
                                            CongruenceClass *NewClass) {
   if (I == OldClass->getNextLeader().first)
     OldClass->resetNextLeader();
+  OldClass->erase(I);
+  NewClass->insert(I);
 
   // It's possible, though unlikely, for us to discover equivalences such
   // that the current leader does not dominate the old one.
   // This statistic tracks how often this happens.
   // We assert on phi nodes when this happens, currently, for debugging, because
   // we want to make sure we name phi node cycles properly.
   if (isa<Instruction>(NewClass->getLeader()) && NewClass->getLeader() &&
       I != NewClass->getLeader()) {
     auto *IBB = I->getParent();
     auto *NCBB = cast<Instruction>(NewClass->getLeader())->getParent();
     bool Dominated =
         IBB == NCBB && InstrToDFSNum(I) < InstrToDFSNum(NewClass->getLeader());
     Dominated = Dominated || DT->properlyDominates(IBB, NCBB);
     if (Dominated) {
       ++NumGVNNotMostDominatingLeader;
+#if 0
       assert(
           !isa<PHINode>(I) &&
           "New class for instruction should not be dominated by instruction");
+#endif
     }
   }
 
   if (NewClass->getLeader() != I)
     NewClass->addPossibleNextLeader({I, InstrToDFSNum(I)});
 
-  OldClass->erase(I);
-  NewClass->insert(I);
   // Handle our special casing of stores.
   if (auto *SI = dyn_cast<StoreInst>(I)) {
     OldClass->decStoreCount();
     // Okay, so when do we want to make a store a leader of a class?
     // If we have a store defined by an earlier load, we want the earlier load
     // to lead the class.
     // If we have a store defined by something else, we want the store to lead
     // the class so everything else gets the "something else" as a value.
if (NewClass->getStoreCount() == 0 && !NewClass->getStoredValue()) {
       // We rely on the code below handling the MemoryAccess change.
     }
     NewClass->incStoreCount();
   }
   // True if there is no memory instructions left in a class that had memory
   // instructions before.
 
   // If it's not a memory use, set the MemoryAccess equivalence
-  auto *InstMA = dyn_cast_or_null<MemoryDef>(MSSA->getMemoryAccess(I));
+  auto *InstMA = dyn_cast_or_null<MemoryDef>(getMemoryAccess(I));
   bool InstWasMemoryLeader = InstMA && OldClass->getMemoryLeader() == InstMA;
   if (InstMA)
     moveMemoryToNewCongruenceClass(I, InstMA, OldClass, NewClass);
   ValueToClass[I] = NewClass;
   // See if we destroyed the class or need to swap leaders.
   if (OldClass->empty() && OldClass != TOPClass) {
     if (OldClass->getDefiningExpr()) {
       DEBUG(dbgs() << "Erasing expression " << OldClass->getDefiningExpr()
if (lookupResult.second) {
       assert(!EClass->isDead() && "We accidentally looked up a dead class");
     }
   }
   bool ClassChanged = IClass != EClass;
   bool LeaderChanged = LeaderChanges.erase(I);
   if (ClassChanged || LeaderChanged) {
     DEBUG(dbgs() << "New class " << EClass->getID() << " for expression " << *E
                  << "\n");
-    if (ClassChanged)
+    if (ClassChanged) {
       moveValueToNewCongruenceClass(I, E, IClass, EClass);
+      if (auto *VTR = TempToReal.lookup(I))
+        TouchedInstructions.set(InstrToDFSNum(VTR));
+    }
+
     markUsersTouched(I);
-    if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
+    if (MemoryAccess *MA = 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.
if (ReachableBlocks.insert(To).second) {
       DEBUG(dbgs() << "Block " << getBlockName(To)
                    << " was reachable, but new edge {" << getBlockName(From)
                    << "," << getBlockName(To) << "} to it found\n");
 
       // We've made an edge reachable to an existing block, which may
       // impact predicates. Otherwise, only mark the phi nodes as touched, as
       // they are the only thing that depend on new edges. Anything using their
       // values will get propagated to if necessary.
-      if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(To))
+      if (MemoryAccess *MemPhi = getMemoryAccess(To))
         TouchedInstructions.set(InstrToDFSNum(MemPhi));
 
       auto BI = To->begin();
       while (isa<PHINode>(BI)) {
         TouchedInstructions.set(InstrToDFSNum(&*BI));
         ++BI;
       }
     }
if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) {
     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
       BasicBlock *TargetBlock = TI->getSuccessor(i);
       updateReachableEdge(B, TargetBlock);
     }
 
     // This also may be a memory defining terminator, in which case, set it
     // equivalent only to itself.
     //
-    auto *MA = MSSA->getMemoryAccess(TI);
+    auto *MA = getMemoryAccess(TI);
     if (MA && !isa<MemoryUse>(MA)) {
       auto *CC = ensureLeaderOfMemoryClass(MA);
       if (setMemoryClass(MA, CC))
         markMemoryUsersTouched(MA);
     }
   }
 }
 
+void NewGVN::addPhiOfOpsOrOp(Instruction *Op,
+                             SmallVectorImpl<Instruction *> &Vect,
+                             BasicBlock *BB, MemoryUseOrDef *MemAccess,
+                             Value *ExistingValue) {
+  AllTempInstructions.insert(Op);
+  Vect.push_back(Op);
+  TempToBlock[Op] = BB;
+  if (MemAccess) {
+    TempToMemory[Op] = MemAccess;
+    MemoryToTempUsers[MemAccess->getDefiningAccess()].insert(Op);
+  }
+  if (ExistingValue) {
+    RealToTemp[ExistingValue] = Op;
+    TempToReal[Op] = ExistingValue;
+  }
+}
+
+// When we see an instruction that is an op of phis, generate the equivalent phi
+// of ops form.
+bool NewGVN::makePossiblePhiOfOps(Instruction *I, bool HasBackedge) {
+  if (!isa<BinaryOperator>(I) && !isa<LoadInst>(I) && !isa<CmpInst>(I))
+    return false;
+  // Pretty much all of the instructions we can convert to phi of ops over a
+  // backedge that are adds, are really induction variables, and those are
+  // pretty much pointless to convert.  This is very coarse-grained for a
+  // test, so if we do find some value, we can change it later.
+  // But otherwise, what can happen is we convert the induction variable from
+  //
+  // i = phi (0, tmp)
+  // tmp = i + 1
+  //
+  // to
+  // i = phi (0, tmpphi)
+  // tmpphi = phi(1, tmpphi+1)
+  //
+  // Which we don't want to happen.
+  // We could just avoid this for all non-cycle free phis, and we made go that route.
+  if (HasBackedge && I->getOpcode() == Instruction::Add)
+    return false;
+
+  SmallPtrSet<const Value *, 8> ProcessedPHIs;
+  // TODO: We don't do phi translation on memory accesses because it's
+  // complicated. For a load, we'd need to be able to simulate a new memoryuse,
+  // which we don't have a good way of doing ATM.
+  auto *MemAccess = MSSA->getMemoryAccess(I);
+  // If the memory operation is defined by a memory operation this block that
+  // isn't a MemoryPhi, transforming the pointer backwards through a scalar phi
+  // can't
+  // help, as it would still be killed by that memory operation.
+  if (MemAccess && !isa<MemoryPhi>(MemAccess) &&
+      MemAccess->getDefiningAccess()->getBlock() == I->getParent())
+    return false;
+  // Convert op of phis to phi of ops
+  for (auto &Op : I->operands()) {
+    if (!isa<PHINode>(Op))
+      continue;
+    auto *OpPHI = cast<PHINode>(Op);
+    auto *PHIBlock = getBlockForValue(OpPHI);
+    PHINode *ValuePHI = PHINode::Create(I->getType(), OpPHI->getNumOperands());
+    addPhiOfOpsOrOp(ValuePHI, PHIOfOpsPHIs[PHIBlock], PHIBlock, nullptr, I);
+    for (auto PredBB : OpPHI->blocks()) {
+      Instruction *ValueOp = I->clone();
+      addPhiOfOpsOrOp(ValueOp, PHIOfOpsOps[PredBB], PredBB, MemAccess);
+      for (auto &Op : ValueOp->operands())
+        Op = Op->DoPHITranslation(PHIBlock, PredBB);
+      ValuePHI->addIncoming(ValueOp, PredBB);
+      DEBUG(dbgs() << "Created phi of ops operand " << *ValueOp << " in "
+                   << getBlockName(PredBB) << "\n");
+    }
+    DEBUG(dbgs() << "Created phi of ops " << *ValuePHI << " for " << *I
+                 << "\n");
+    return true;
+  }
+  return false;
+}
+
 // The algorithm initially places the values of the routine in the TOP
 // congruence class. The leader of TOP is the undetermined value `undef`.
 // When the algorithm has finished, values still in TOP are unreachable.
 void NewGVN::initializeCongruenceClasses(Function &F) {
   NextCongruenceNum = 0;
 
   // Note that even though we use the live on entry def as a representative
   // MemoryAccess, it is *not* the same as the actual live on entry def. We
   // have no real equivalemnt to undef for MemoryAccesses, and so we really
   // should be checking whether the MemoryAccess is top if we want to know if it
   // is equivalent to everything.  Otherwise, what this really signifies is that
   // the access "it reaches all the way back to the beginning of the function"
 
   // Initialize all other instructions to be in TOP class.
   TOPClass = createCongruenceClass(nullptr, nullptr);
   TOPClass->setMemoryLeader(MSSA->getLiveOnEntryDef());
   //  The live on entry def gets put into it's own class
   MemoryAccessToClass[MSSA->getLiveOnEntryDef()] =
       createMemoryClass(MSSA->getLiveOnEntryDef());
 
-  for (auto &B : F) {
+  // Set of instructions already considered for conversion to phi of ops
+  SmallPtrSet<const User *, 8> VisitedPhiOfOps;
+  for (auto DTN : nodes(DT)) {
+    BasicBlock *BB = DTN->getBlock();
     // All MemoryAccesses 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.
-    auto *MemoryBlockDefs = MSSA->getBlockDefs(&B);
+    auto *MemoryBlockDefs = MSSA->getBlockDefs(BB);
     if (MemoryBlockDefs)
       for (const auto &Def : *MemoryBlockDefs) {
         MemoryAccessToClass[&Def] = TOPClass;
         auto *MD = dyn_cast<MemoryDef>(&Def);
         // Insert the memory phis into the member list.
         if (!MD) {
           const MemoryPhi *MP = cast<MemoryPhi>(&Def);
           TOPClass->memory_insert(MP);
           MemoryPhiState.insert({MP, MPS_TOP});
         }
 
         if (MD && isa<StoreInst>(MD->getMemoryInst()))
           TOPClass->incStoreCount();
       }
-    for (auto &I : B) {
+    bool HasBackedge = llvm::any_of(predecessors(BB), [&](BasicBlock *Pred) {
+      return isBackedge(Pred, BB);
+    });
+
+    for (auto &I : *BB) {
+      // TODO: Move to helper
+      if (isa<PHINode>(&I))
+        for (auto *U : I.users())
+          if (auto *UInst = dyn_cast<Instruction>(U))
+            if (!isInstructionTriviallyDead(UInst, TLI) &&
+                VisitedPhiOfOps.insert(U).second)
+              makePossiblePhiOfOps(UInst, HasBackedge);
+
       // Don't insert void terminators into the class. We don't value number
       // them, and they just end up sitting in TOP.
       if (isa<TerminatorInst>(I) && I.getType()->isVoidTy())
         continue;
       TOPClass->insert(&I);
       ValueToClass[&I] = TOPClass;
     }
   }
 
+  for (const auto &BlockOps : PHIOfOpsOps) {
+    for (auto &Op : BlockOps.second) {
+      TOPClass->insert(Op);
+      ValueToClass[Op] = TOPClass;
+    }
+  }
+  for (const auto &BlockPHIs : PHIOfOpsPHIs) {
+    for (auto &PHI : BlockPHIs.second) {
+      TOPClass->insert(PHI);
+      ValueToClass[PHI] = TOPClass;
+    }
+  }
+
   // Initialize arguments to be in their own unique congruence classes
   for (auto &FA : F.args())
     createSingletonCongruenceClass(&FA);
 }
 
 void NewGVN::cleanupTables() {
   for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) {
     DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->getID()
                  << " has " << CongruenceClasses[i]->size() << " members\n");
     // Make sure we delete the congruence class (probably worth switching to
     // a unique_ptr at some point.
     delete CongruenceClasses[i];
     CongruenceClasses[i] = nullptr;
   }
 
+  // Destroy the value expressions
+  SmallVector<Instruction *, 8> TempInst(AllTempInstructions.begin(),
+                                         AllTempInstructions.end());
+  AllTempInstructions.clear();
+
+  // We have to drop all references for everything first, so there are no uses
+  // left as we delete them.
+  for (auto *I : TempInst) {
+    I->dropAllReferences();
+  }
+
+  while (!TempInst.empty()) {
+    auto *I = TempInst.back();
+    TempInst.pop_back();
+    delete I;
+  }
+
   ValueToClass.clear();
   ArgRecycler.clear(ExpressionAllocator);
   ExpressionAllocator.Reset();
   CongruenceClasses.clear();
   ExpressionToClass.clear();
   ValueToExpression.clear();
+  RealToTemp.clear();
+  TempToReal.clear();
+  TempToBlock.clear();
+  TempToMemory.clear();
+  MemoryToTempUsers.clear();
+  PHIOfOpsOps.clear();
+  PHIOfOpsPHIs.clear();
   ReachableBlocks.clear();
   ReachableEdges.clear();
 #ifndef NDEBUG
   ProcessedCount.clear();
 #endif
   InstrDFS.clear();
   InstructionsToErase.clear();
   DFSToInstr.clear();
   BlockInstRange.clear();
   TouchedInstructions.clear();
   MemoryAccessToClass.clear();
   PredicateToUsers.clear();
   MemoryToUsers.clear();
 }
 
+// Assign local DFS number mapping to instructions, and leave space for Value
+// PHI's.
 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
                                                        unsigned Start) {
   unsigned End = Start;
-  if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) {
+  if (MemoryAccess *MemPhi = getMemoryAccess(B)) {
     InstrDFS[MemPhi] = End++;
     DFSToInstr.emplace_back(MemPhi);
   }
 
+  // Value PHIs go first.
+  const auto PHIResult = PHIOfOpsPHIs.find(B);
+  if (PHIResult != PHIOfOpsPHIs.end()) {
+    const auto &Ops = PHIResult->second;
+    for (auto I : Ops) {
+      InstrDFS[I] = End++;
+      DFSToInstr.push_back(I);
+    }
+  }
+
+  // Then the real block goes next.
   for (auto &I : *B) {
     // There's no need to call isInstructionTriviallyDead more than once on
     // an instruction. Therefore, once we know that an instruction is dead
     // we change its DFS number so that it doesn't get value numbered.
     if (isInstructionTriviallyDead(&I, TLI)) {
       InstrDFS[&I] = 0;
       DEBUG(dbgs() << "Skipping trivially dead instruction " << I << "\n");
       markInstructionForDeletion(&I);
       continue;
     }
-
     InstrDFS[&I] = End++;
     DFSToInstr.emplace_back(&I);
   }
 
+  // And lastly, any value expressions we may need.
+  const auto OpResult = PHIOfOpsOps.find(B);
+  if (OpResult != PHIOfOpsOps.end()) {
+    const auto &Ops = OpResult->second;
+    for (auto I : Ops) {
+      InstrDFS[I] = End++;
+      DFSToInstr.push_back(I);
+    }
+  }
+
   // All of the range functions taken half-open ranges (open on the end side).
   // So we do not subtract one from count, because at this point it is one
   // greater than the last instruction.
   return std::make_pair(Start, End);
 }
 
-void NewGVN::updateProcessedCount(Value *V) {
+void NewGVN::updateProcessedCount(const Value *V) {
 #ifndef NDEBUG
   if (ProcessedCount.count(V) == 0) {
     ProcessedCount.insert({V, 1});
   } else {
     ++ProcessedCount[V];
     assert(ProcessedCount[V] < 100 &&
            "Seem to have processed the same Value a lot");
   }
if (!I->isTerminator()) {
     if (DebugCounter::shouldExecute(VNCounter)) {
       Symbolized = performSymbolicEvaluation(I);
     } else {
       // Mark the instruction as unused so we don't value number it again.
       InstrDFS[I] = 0;
     }
     // If we couldn't come up with a symbolic expression, use the unknown
     // expression
-    if (Symbolized == nullptr) {
+    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.  We don't place non-value producing
     // terminators in a class.
     if (!I->getType()->isVoidTy()) {
       auto *Symbolized = createUnknownExpression(I);
       performCongruenceFinding(I, Symbolized);

 // until the set of touched instructions is completely empty.
 void NewGVN::iterateTouchedInstructions() {
   unsigned int Iterations = 0;
   // Figure out where touchedinstructions starts
   int FirstInstr = TouchedInstructions.find_first();
   // Nothing set, nothing to iterate, just return.
   if (FirstInstr == -1)
     return;
-  BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
+  const BasicBlock *LastBlock = getBlockForValue(InstrFromDFSNum(FirstInstr));
   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;
       }
 
       Value *V = InstrFromDFSNum(InstrNum);
-      BasicBlock *CurrBlock = getBlockForValue(V);
+      const BasicBlock *CurrBlock = getBlockForValue(V);
 
       // If we hit a new block, do reachability processing.
       if (CurrBlock != LastBlock) {
         LastBlock = CurrBlock;
         bool BlockReachable = ReachableBlocks.count(CurrBlock);
         const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
 
         // If it's not reachable, erase any touched instructions and move on.
for (auto &B : RPOT) {
     auto *Node = DT->getNode(B);
     if (Node->getChildren().size() > 1)
       std::sort(Node->begin(), Node->end(),
                 [&](const DomTreeNode *A, const DomTreeNode *B) {
                   return RPOOrdering[A] < RPOOrdering[B];
                 });
   }
 
+  // This must happen after we initialize RPO but before we assign DFS numbers.
+  initializeCongruenceClasses(F);
+
   // Now a standard depth first ordering of the domtree is equivalent to RPO.
-  auto DFI = df_begin(DT->getRootNode());
-  for (auto DFE = df_end(DT->getRootNode()); DFI != DFE; ++DFI) {
-    BasicBlock *B = DFI->getBlock();
+  for (auto DTN : depth_first(DT->getRootNode())) {
+    BasicBlock *B = DTN->getBlock();
     const auto &BlockRange = assignDFSNumbers(B, ICount);
     BlockInstRange.insert({B, BlockRange});
     ICount += BlockRange.second - BlockRange.first;
   }
 
-  // Handle forward unreachable blocks and figure out which blocks
-  // have single preds.
-  for (auto &B : F) {
-    // Assign numbers to unreachable blocks.
-    if (!DFI.nodeVisited(DT->getNode(&B))) {
-      const auto &BlockRange = assignDFSNumbers(&B, ICount);
-      BlockInstRange.insert({&B, BlockRange});
-      ICount += BlockRange.second - BlockRange.first;
-    }
-  }
-
   TouchedInstructions.resize(ICount);
   // Ensure we don't end up resizing the expressionToClass map, as
   // that can be quite expensive. At most, we have one expression per
   // instruction.
   ExpressionToClass.reserve(ICount);
 
   // Initialize the touched instructions to include the entry block.
   const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
   TouchedInstructions.set(InstRange.first, InstRange.second);
+  DEBUG(dbgs() << "Block " << getBlockName(&F.getEntryBlock())
+               << " marked reachable\n");
   ReachableBlocks.insert(&F.getEntryBlock());
 
-  initializeCongruenceClasses(F);
   iterateTouchedInstructions();
   verifyMemoryCongruency();
   verifyIterationSettled(F);
 
   Changed |= eliminateInstructions(F);
 
   // Delete all instructions marked for deletion.
   for (Instruction *ToErase : InstructionsToErase) {
     if (!ToErase->use_empty())
       ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
 
+    if (ToErase->getParent())
       ToErase->eraseFromParent();
   }
 
   // Delete all unreachable blocks.
   auto UnreachableBlockPred = [&](const BasicBlock &BB) {
     return !ReachableBlocks.count(&BB);
   };
 
   for (auto &BB : make_filter_range(F, UnreachableBlockPred)) {
     DEBUG(dbgs() << "We believe block " << getBlockName(&BB)
                  << " is unreachable\n");
     deleteInstructionsInBlock(&BB);
     Changed = true;
   }
 
   cleanupTables();
   return Changed;
 }
 
-// Return true if V is a value that will always be available (IE can
-// be placed anywhere) in the function.  We don't do globals here
-// because they are often worse to put in place.
-// TODO: Separate cost from availability
-static bool alwaysAvailable(Value *V) {
-  return isa<Constant>(V) || isa<Argument>(V);
-}
-
 struct NewGVN::ValueDFS {
   int DFSIn = 0;
   int DFSOut = 0;
   int LocalNum = 0;
   // Only one of Def and U will be set.
   // The bool in the Def tells us whether the Def is the stored value of a
   // store.
   PointerIntPair<Value *, 1, bool> Def;
for (auto &U : Def->uses()) {
         // Put the phi node uses in the incoming block.
         BasicBlock *IBlock;
         if (auto *P = dyn_cast<PHINode>(I)) {
           IBlock = P->getIncomingBlock(U);
           // Make phi node users appear last in the incoming block
           // they are from.
           VDUse.LocalNum = InstrDFS.size() + 1;
         } else {
-          IBlock = I->getParent();
+          IBlock = getBlockForValue(I);
           VDUse.LocalNum = InstrToDFSNum(I);
         }
 
         // Skip uses in unreachable blocks, as we're going
         // to delete them.
         if (ReachableBlocks.count(IBlock) == 0)
           continue;
 
if (!ReachableBlocks.count(&B)) {
               Operand.set(UndefValue::get(Phi.getType()));
         }
       }
     }
   }
 
   // Map to store the use counts
   DenseMap<const Value *, unsigned int> UseCounts;
-  for (CongruenceClass *CC : reverse(CongruenceClasses)) {
+  for (auto *CC : reverse(CongruenceClasses)) {
     // Track the equivalent store info so we can decide whether to try
     // dead store elimination.
     SmallVector<ValueDFS, 8> PossibleDeadStores;
     SmallPtrSet<Instruction *, 8> ProbablyDead;
     if (CC->isDead() || CC->empty())
       continue;
     // Everything still in the TOP class is unreachable or dead.
     if (CC == TOPClass) {
if (alwaysAvailable(Leader)) {
           int MemberDFSOut = VD.DFSOut;
           Value *Def = VD.Def.getPointer();
           bool FromStore = VD.Def.getInt();
           Use *U = VD.U;
           // We ignore void things because we can't get a value from them.
           if (Def && Def->getType()->isVoidTy())
             continue;
 
+          if (AllTempInstructions.count(dyn_cast_or_null<Instruction>(Def))) {
+            // If this is a value phi and all operands are real, insert it into
+            // the program and remove from temp instruction list.
+            auto *PHIE =
+                dyn_cast_or_null<PHIExpression>(ValueToExpression.lookup(Def));
+            if (!PHIE || !PHIE->isAllRealOps())
+              continue;
+            auto *DefInst = cast<Instruction>(Def);
+            AllTempInstructions.erase(DefInst);
+            auto *DefBlock = getBlockForValue(Def);
+            DEBUG(dbgs() << "Inserting fully real phi of ops" << *Def
+                         << " into block "
+                         << getBlockName(getBlockForValue(Def)) << "\n");
+            DefInst->insertBefore(&DefBlock->front());
+          }
+
           if (EliminationStack.empty()) {
             DEBUG(dbgs() << "Elimination Stack is empty\n");
           } else {
             DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
                          << EliminationStack.dfs_back().first << ","
                          << EliminationStack.dfs_back().second << ")\n");
           }
 
if (CC->getStoreCount() > 0) {
         DEBUG(dbgs() << "Marking dead store " << *Member
                      << " that is dominated by " << *Leader << "\n");
         markInstructionForDeletion(Member);
         CC->erase(Member);
         ++NumGVNDeadStores;
       }
     }
   }
-
   return AnythingReplaced;
 }
 
 // This function provides global ranking of operations so that we can place them
 // in a canonical order.  Note that rank alone is not necessarily enough for a
 // complete ordering, as constants all have the same rank.  However, generally,
 // we will simplify an operation with all constants so that it doesn't matter
 // what order they appear in.

test/Transforms/NewGVN/completeness.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"
+
+define i32 @test1(i32, i8**) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP4:%.*]], label [[TMP5:%.*]]
+; CHECK:         br label [[TMP6:%.*]]
+; CHECK:         br label [[TMP6]]
+; CHECK:         [[TMP7:%.*]] = phi i32 [ 75, [[TMP4]] ], [ 105, [[TMP5]] ]
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 5, [[TMP4]] ], [ 7, [[TMP5]] ]
+; CHECK-NEXT:    ret i32 [[TMP7]]
+;
+  %3 = icmp ne i32 %0, 0
+  br i1 %3, label %4, label %5
+
+; <label>:4:                                      ; preds = %2
+  br label %6
+
+; <label>:5:                                      ; preds = %2
+  br label %6
+
+; <label>:6:                                      ; preds = %5, %4
+  %.0 = phi i32 [ 5, %4 ], [ 7, %5 ]
+  %7 = mul nsw i32 %.0, 15
+  ret i32 %7
+}
+
+define i32 @test2(i32) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP2]], label [[TMP3:%.*]], label [[TMP4:%.*]]
+; CHECK:         br label [[TMP5:%.*]]
+; CHECK:         br label [[TMP5]]
+; CHECK:         [[DOT01:%.*]] = phi i32 [ 3, [[TMP3]] ], [ 2, [[TMP4]] ]
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 2, [[TMP3]] ], [ 3, [[TMP4]] ]
+; CHECK-NEXT:    ret i32 5
+;
+  %2 = icmp ne i32 %0, 0
+  br i1 %2, label %3, label %4
+
+; <label>:3:                                      ; preds = %1
+  br label %5
+
+; <label>:4:                                      ; preds = %1
+  br label %5
+
+; <label>:5:                                      ; preds = %4, %3
+  %.01 = phi i32 [ 3, %3 ], [ 2, %4 ]
+  %.0 = phi i32 [ 2, %3 ], [ 3, %4 ]
+  %6 = add nsw i32 %.01, %.0
+  ret i32 %6
+}
+define i32 @test3(i1 %which) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
+; CHECK:       delay:
+; CHECK-NEXT:    br label [[FINAL]]
+; CHECK:       final:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ -877, [[ENTRY:%.*]] ], [ 113, [[DELAY]] ]
+; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1000, [[ENTRY]] ], [ 10, [[DELAY]] ]
+; CHECK-NEXT:    ret i32 [[TMP0]]
+;
+
+entry:
+  br i1 %which, label %final, label %delay
+
+delay:
+  br label %final
+
+final:
+  %A = phi i32 [ 1000, %entry ], [ 10, %delay ]
+  %value = sub i32 123, %A
+  ret i32 %value
+}
+
+define <2 x i32> @test3vec(i1 %which) {
+; CHECK-LABEL: @test3vec(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
+; CHECK:       delay:
+; CHECK-NEXT:    br label [[FINAL]]
+; CHECK:       final:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i32> [ <i32 -877, i32 -877>, [[ENTRY:%.*]] ], [ <i32 113, i32 113>, [[DELAY]] ]
+; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 1000, i32 1000>, [[ENTRY]] ], [ <i32 10, i32 10>, [[DELAY]] ]
+; CHECK-NEXT:    ret <2 x i32> [[TMP0]]
+;
+
+entry:
+  br i1 %which, label %final, label %delay
+
+delay:
+  br label %final
+
+final:
+  %A = phi <2 x i32> [ <i32 1000, i32 1000>, %entry ], [ <i32 10, i32 10>, %delay ]
+  %value = sub <2 x i32> <i32 123, i32 123>, %A
+  ret <2 x i32> %value
+}
+
+define <2 x i32> @test3vec2(i1 %which) {
+; CHECK-LABEL: @test3vec2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[WHICH:%.*]], label [[FINAL:%.*]], label [[DELAY:%.*]]
+; CHECK:       delay:
+; CHECK-NEXT:    br label [[FINAL]]
+; CHECK:       final:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i32> [ <i32 -877, i32 -2167>, [[ENTRY:%.*]] ], [ <i32 113, i32 303>, [[DELAY]] ]
+; CHECK-NEXT:    [[A:%.*]] = phi <2 x i32> [ <i32 1000, i32 2500>, [[ENTRY]] ], [ <i32 10, i32 30>, [[DELAY]] ]
+; CHECK-NEXT:    ret <2 x i32> [[TMP0]]
+;
+
+entry:
+  br i1 %which, label %final, label %delay
+
+delay:
+  br label %final
+
+final:
+  %A = phi <2 x i32> [ <i32 1000, i32 2500>, %entry ], [ <i32 10, i32 30>, %delay ]
+  %value = sub <2 x i32> <i32 123, i32 333>, %A
+  ret <2 x i32> %value
+}
+
+;; This example is a bit contrived because we can't create fake memoryuses, so we use two loads in the if blocks
+define i32 @test4(i32, i8**, i32* noalias, i32* noalias) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:    store i32 5, i32* [[TMP2:%.*]], align 4
+; CHECK-NEXT:    store i32 7, i32* [[TMP3:%.*]], align 4
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i32 [[TMP0:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP5]], label [[TMP6:%.*]], label [[TMP7:%.*]]
+; CHECK:         br label [[TMP8:%.*]]
+; CHECK:         br label [[TMP8]]
+; CHECK:         [[DOT01:%.*]] = phi i32 [ 5, [[TMP6]] ], [ 7, [[TMP7]] ]
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32* [ [[TMP2]], [[TMP6]] ], [ [[TMP3]], [[TMP7]] ]
+; CHECK-NEXT:    [[TMP9:%.*]] = load i32, i32* [[DOT0]], align 4
+; CHECK-NEXT:    [[TMP10:%.*]] = mul nsw i32 [[TMP9]], 15
+; CHECK-NEXT:    [[TMP11:%.*]] = mul nsw i32 [[TMP10]], [[DOT01]]
+; CHECK-NEXT:    ret i32 [[TMP11]]
+;
+  store i32 5, i32* %2, align 4
+  store i32 7, i32* %3, align 4
+  %5 = icmp ne i32 %0, 0
+  br i1 %5, label %6, label %8
+
+; <label>:6:                                      ; preds = %4
+  %7 = load i32, i32* %2, align 4
+  br label %10
+
+; <label>:8:                                      ; preds = %4
+  %9 = load i32, i32* %3, align 4
+  br label %10
+
+; <label>:10:                                     ; preds = %8, %6
+  %.01 = phi i32 [ %7, %6 ], [ %9, %8 ]
+  %.0 = phi i32* [ %2, %6 ], [ %3, %8 ]
+  %11 = load i32, i32* %.0, align 4
+  %12 = mul nsw i32 %11, 15
+  %13 = mul nsw i32 %12, %.01
+  ret i32 %13
+}
+
+@global = common global [100 x i64] zeroinitializer, align 16
+@global.1 = common global [100 x i64] zeroinitializer, align 16
+define i64 @test5(i64 %arg) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = alloca i64, align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i64 [[ARG:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP1]], label [[BB28:%.*]], label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB7:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i64 [[TMP9:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP6]], label [[BB27:%.*]], label [[BB7]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP8:%.*]] = phi i64 [ [[ARG]], [[BB2]] ], [ [[TMP9]], [[BB5]] ]
+; CHECK-NEXT:    [[TMP9]] = add nsw i64 [[TMP8]], -1
+; CHECK-NEXT:    [[TMP10:%.*]] = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global, i64 0, i64 0), align 16
+; CHECK-NEXT:    [[TMP11:%.*]] = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global.1, i64 0, i64 0), align 16
+; CHECK-NEXT:    [[TMP12:%.*]] = mul nsw i64 [[TMP11]], [[TMP10]]
+; CHECK-NEXT:    [[TMP13:%.*]] = icmp eq i64 [[TMP12]], 0
+; CHECK-NEXT:    br i1 [[TMP13]], label [[BB5]], label [[BB14:%.*]]
+; CHECK:       bb14:
+; CHECK-NEXT:    br label [[BB15:%.*]]
+; CHECK:       bb15:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i64 [ [[TMP25:%.*]], [[BB15]] ], [ [[TMP12]], [[BB14]] ]
+; CHECK-NEXT:    [[TMP16:%.*]] = phi i64 [ [[TMP24:%.*]], [[BB15]] ], [ [[TMP11]], [[BB14]] ]
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i64 [ [[TMP22:%.*]], [[BB15]] ], [ [[TMP10]], [[BB14]] ]
+; CHECK-NEXT:    [[TMP18:%.*]] = phi i64 [ [[TMP20:%.*]], [[BB15]] ], [ 0, [[BB14]] ]
+; CHECK-NEXT:    store i64 [[TMP0]], i64* [[TMP]], align 8
+; CHECK-NEXT:    [[TMP20]] = add nuw nsw i64 [[TMP18]], 1
+; CHECK-NEXT:    [[TMP21:%.*]] = getelementptr inbounds [100 x i64], [100 x i64]* @global, i64 0, i64 [[TMP20]]
+; CHECK-NEXT:    [[TMP22]] = load i64, i64* [[TMP21]], align 8
+; CHECK-NEXT:    [[TMP23:%.*]] = getelementptr inbounds [100 x i64], [100 x i64]* @global.1, i64 0, i64 [[TMP20]]
+; CHECK-NEXT:    [[TMP24]] = load i64, i64* [[TMP23]], align 8
+; CHECK-NEXT:    [[TMP25]] = mul nsw i64 [[TMP24]], [[TMP22]]
+; CHECK-NEXT:    [[TMP26:%.*]] = icmp eq i64 [[TMP20]], [[TMP25]]
+; CHECK-NEXT:    br i1 [[TMP26]], label [[BB4:%.*]], label [[BB15]]
+; CHECK:       bb27:
+; CHECK-NEXT:    br label [[BB28]]
+; CHECK:       bb28:
+; CHECK-NEXT:    ret i64 0
+;
+bb:
+  %tmp = alloca i64, align 8
+  %tmp1 = icmp eq i64 %arg, 0
+  br i1 %tmp1, label %bb28, label %bb2
+
+bb2:                                              ; preds = %bb
+  %tmp3 = bitcast i64* %tmp to i8*
+  br label %bb7
+
+bb4:                                              ; preds = %bb15
+  br label %bb5
+
+bb5:                                              ; preds = %bb7, %bb4
+  %tmp6 = icmp eq i64 %tmp9, 0
+  br i1 %tmp6, label %bb27, label %bb7
+
+bb7:                                              ; preds = %bb5, %bb2
+  %tmp8 = phi i64 [ %arg, %bb2 ], [ %tmp9, %bb5 ]
+  %tmp9 = add nsw i64 %tmp8, -1
+  %tmp10 = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global, i64 0, i64 0), align 16
+  %tmp11 = load i64, i64* getelementptr inbounds ([100 x i64], [100 x i64]* @global.1, i64 0, i64 0), align 16
+  %tmp12 = mul nsw i64 %tmp11, %tmp10
+  %tmp13 = icmp eq i64 %tmp12, 0
+  br i1 %tmp13, label %bb5, label %bb14
+
+bb14:                                             ; preds = %bb7
+  br label %bb15
+
+bb15:                                             ; preds = %bb15, %bb14
+  %tmp16 = phi i64 [ %tmp24, %bb15 ], [ %tmp11, %bb14 ]
+  %tmp17 = phi i64 [ %tmp22, %bb15 ], [ %tmp10, %bb14 ]
+  %tmp18 = phi i64 [ %tmp20, %bb15 ], [ 0, %bb14 ]
+;; This multiply is an op of phis which is really equivalent to phi(tmp25, tmp12)
+  %tmp19 = mul nsw i64 %tmp16, %tmp17
+  store i64 %tmp19, i64* %tmp, align 8
+  %tmp20 = add nuw nsw i64 %tmp18, 1
+  %tmp21 = getelementptr inbounds [100 x i64], [100 x i64]* @global, i64 0, i64 %tmp20
+  %tmp22 = load i64, i64* %tmp21, align 8
+  %tmp23 = getelementptr inbounds [100 x i64], [100 x i64]* @global.1, i64 0, i64 %tmp20
+  %tmp24 = load i64, i64* %tmp23, align 8
+  %tmp25 = mul nsw i64 %tmp24, %tmp22
+  %tmp26 = icmp eq i64 %tmp20, %tmp25
+  br i1 %tmp26, label %bb4, label %bb15
+
+bb27:                                             ; preds = %bb5
+  br label %bb28
+
+bb28:                                             ; preds = %bb27, %bb
+  ret i64 0
+}
+
+;; These icmps are all equivalent to phis of constants
+define i8 @test6(i8* %addr) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:  entry-block:
+; CHECK-NEXT:    br label %main-loop
+; CHECK:       main-loop:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, %entry-block ], [ true, [[CORE:%.*]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ true, %entry-block ], [ false, [[CORE]] ]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i8 [ 0, %entry-block ], [ 1, [[CORE]] ]
+; CHECK-NEXT:    store volatile i8 0, i8* [[ADDR:%.*]]
+; CHECK-NEXT:    br i1 [[TMP1]], label %busy-wait-phi-0, label [[EXIT:%.*]]
+; CHECK:       busy-wait-phi-0:
+; CHECK-NEXT:    [[LOAD:%.*]] = load volatile i8, i8* [[ADDR]]
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp eq i8 [[LOAD]], 0
+; CHECK-NEXT:    br i1 [[ICMP]], label %busy-wait-phi-0, label [[CORE]]
+; CHECK:       core:
+; CHECK-NEXT:    br i1 [[TMP0]], label [[TRAP:%.*]], label %main-loop
+; CHECK:       trap:
+; CHECK-NEXT:    ret i8 1
+; CHECK:       exit:
+; CHECK-NEXT:    ret i8 0
+;
+entry-block:
+  br label %main-loop
+
+main-loop:
+  %phi = phi i8 [ 0, %entry-block ], [ 1, %core ]
+  %switch_0 = icmp eq i8 %phi, 0
+  store volatile i8 0, i8* %addr
+  br i1 %switch_0, label %busy-wait-phi-0, label %exit
+
+busy-wait-phi-0:
+  %load = load volatile i8, i8* %addr
+  %icmp = icmp eq i8 %load, 0
+  br i1 %icmp, label %busy-wait-phi-0, label %core
+
+core:
+  %switch_1 = icmp eq i8 %phi, 1
+  br i1 %switch_1, label %trap, label %main-loop
+
+trap:
+  ret i8 1
+
+exit:
+  ret i8 0
+}
+

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-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:         [[TMP6:%.*]] = phi i32 [ 15, [[TMP4]] ], [ 10, [[TMP2:%.*]] ]
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP2]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP7:%.*]], label [[TMP8:%.*]]
+; CHECK:         br label [[TMP8]]
+; CHECK:         [[DOT1:%.*]] = phi i32 [ [[TMP6]], [[TMP7]] ], [ [[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
   %5 = load i32, i32* %0, align 4

 ;; which requires value numbering MemoryPhi properly to resolve.
 define i32 @foo2(i32*, i32)  {
 ; 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:         [[TMP7:%.*]] = phi i32 [ 15, [[TMP4]] ], [ 10, [[TMP5]] ]
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 10, [[TMP4]] ], [ 5, [[TMP5]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[TMP8:%.*]], label [[TMP9:%.*]]
+; CHECK:         br label [[TMP9]]
+; CHECK:         [[DOT1:%.*]] = phi i32 [ [[TMP7]], [[TMP8]] ], [ [[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
   %5 = load i32, i32* %0, align 4