Fix PR/33305. caused by trying to simplify expressions in phi of ops that should have no leaders.

[• dberlin]

Summary

After a discussion with Rekka, i believe this (or a small variant)
should fix the remaining phi-of-ops problems.

Rekka's algorithm for completeness relies on looking up expressions
that should have no leader, and expecting it to fail (IE looking up
expressions that can't exist in a predecessor, and expecting it to
find nothing).

Unfortunately, our simplifier outsmarts this by taking these "not
quite right" expressions, and simplifying them into other expressions
or walking through phis, etc. In the past, we've sometimes been able
to find leaders for them, incorrectly.

This change causes us to not use the simplifier on such
expressions. We determine safety by seeing if they depend on a phi
node dominated by our block.

This is not perfect, we can do better, but this should be a
"correctness start" that we can then improve. It also requires a
bunch of caching that i'll eventually like to eliminate.

The only thing i am not 100% positive on is whether it is safe to
apply constant folding. It looks like our constant folder will also
use computeknownbits to go walking through things, and i'm not
positive that is safe.

The right solution, longer term, is to make the query interface for
the instruction simplifier/constant folder have the flags we need, so
that we can keep most things going, but turn off the possibly-invalid
parts (threading through phis, etc).

My plan is to start with this patch, and see if anyone can find an
issue with constant folding. If so, we'll give up and scale it back
till we can change the query interface for the simplifier and use that.

[• dberlin]

The 33461 change is an example where i believe what we were doing is safe, but i want to see if we still find correctness bugs first :)

[• dberlin]

(In particular, i believe it may be correct to only care about phi nodes in the same block as the one we are trying to translate through, which would fix 33461 back to the better codegen)

[• dberlin]

Unfortunately, i can prove we have to give up rather than try to constant fold in this case.

Given:

for.body.i:
   %tmp1 = phi i1 [ true, %entry ], [ false, %cond.end.i ]
   %f.08.i = phi i32 [ 0, %entry ], [ %inc.i, %cond.end.i ]
   %mul.i = select i1 %cmp1.i, i32 %f.08.i, i32 0
   br i1 %tmp1, label %cond.end.i, label %cond.true.i

 cond.true.i:
   ;; Ensure we don't replace this divide with a phi of ops that merges the wrong loop iteration value
   %div.i = udiv i32 %mul.i, %f.08.i
   br label %cond.end.i

And trying to perform phi of ops on the udiv, the expression that normally can't be found is udiv i32 %mul.i, 0, even though that expression is 0.

(%mul.i can't exist in the entry predecessor).

If we don't fail phi of ops in that case, we may get the wrong answer.

So i'm going to rework this slightly (I've also moved to recursive DFS, and not try to check operands we translated).

I'm going to also test the cost of doing recursive translation on all the operands to see which turn out constant or have leaders (which is safe, but O(N) in the depth of the expression tree)

We can cache the translations as they can't change until the related operands change, and see how expensive it is in practice.

That will actually catch *more* cases than we do now.

[• dberlin]

• Update patch for correctness
• Add test

[• dberlin]

This also fixes PR 33432, i forgot to add it to the log :)
With the latest update it should be correct now.

The only case we now miss is where we could use a phi-of-ops we created earlier to get the values.
I will handle this case in a followup

[• dberlin]

• Update patch for correctness
• Add test
• NewGVN: Add debug message when we can't find a phi of ops operand but looked
• NewGVN: Revert now-unnecessary changes

[• dberlin]

This has now passed all testing i can throw at it, so i'm going to commit it in a day or two, but please feel free to do post-commit review :)

[• dberlin]

• NewGVN: Cleanup comments

[davide]

I gave a round of light testing to this during the morning and it didn't expose any significant issue.
I agree with your plan, this looks like a good starting point. I'm not exactly looking forward to seeing fuzzer generated crazy miscompiles, so I hope this sticks together.

include/llvm/ADT/PackedVector.h

60 ↗

(On Diff #113543)

This change slipped through the cracks.

lib/Transforms/Scalar/NewGVN.cpp

1800

I thought this part already went in

lib/Transforms/Scalar/NewGVN.cpp

DEBUG_COUNTER(PHIOfOpsCounter, "newgvn-phi",
               "Controls which instructions we create phi of ops for");
 // Currently store defining access refinement is too slow due to basicaa being
 // egregiously slow.  This flag lets us keep it working while we work on this
 // issue.
 static cl::opt<bool> EnableStoreRefinement("enable-store-refinement",
                                            cl::init(false), cl::Hidden);
 
 /// Currently, the generation "phi of ops" can result in correctness issues.
-static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(false),
+static cl::opt<bool> EnablePhiOfOps("enable-phi-of-ops", cl::init(true),
                                     cl::Hidden);
 
 //===----------------------------------------------------------------------===//
 //                                GVN Pass
 //===----------------------------------------------------------------------===//
 
 // Anchor methods.
 namespace llvm {
class NewGVN {
   // 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).
   // These mappings just store various data that would normally be part of the
   // IR.
   DenseSet<const Instruction *> PHINodeUses;
+  DenseMap<const Value *, bool> OpSafeForPHIOfOps;
   // Map a temporary instruction we created to a parent block.
   DenseMap<const Value *, BasicBlock *> TempToBlock;
   // Map between the already in-program instructions and the temporary phis we
   // created that they are known equivalent to.
   DenseMap<const Value *, PHINode *> RealToTemp;
   // In order to know when we should re-process instructions that have
   // phi-of-ops, we track the set of expressions that they needed as
   // leaders. When we discover new leaders for those expressions, we process the
NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
          const DataLayout &DL)
       : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), DL(DL),
         PredInfo(make_unique<PredicateInfo>(F, *DT, *AC)), SQ(DL, TLI, DT, AC) {
   }
   bool runGVN();
 
 private:
   // Expression handling.
-  const Expression *createExpression(Instruction *) const;
+  const Expression *createExpression(Instruction *, bool) const;
   const Expression *createBinaryExpression(unsigned, Type *, Value *,
                                            Value *) const;
   PHIExpression *createPHIExpression(Instruction *, bool &HasBackEdge,
                                      bool &OriginalOpsConstant) const;
   const DeadExpression *createDeadExpression() const;
   const VariableExpression *createVariableExpression(Value *) const;
   const ConstantExpression *createConstantExpression(Constant *) const;
   const Expression *createVariableOrConstant(Value *V) const;
CongruenceClass *createSingletonCongruenceClass(Value *Member) {
     CongruenceClass *CClass = createCongruenceClass(Member, nullptr);
     CClass->insert(Member);
     ValueToClass[Member] = CClass;
     return CClass;
   }
   void initializeCongruenceClasses(Function &F);
   const Expression *makePossiblePhiOfOps(Instruction *,
                                          SmallPtrSetImpl<Value *> &);
+  Value *findLeaderForInst(Instruction *ValueOp,
+                           SmallPtrSetImpl<Value *> &Visited,
+                           bool SafeToSimplify, MemoryAccess *MemAccess,
+                           Instruction *OrigInst, BasicBlock *PredBB);
+
+  bool OpIsSafeForPHIOfOps(Value *Op, Instruction *OrigInst,
+                           const BasicBlock *PHIBlock,
+                           SmallPtrSetImpl<const Value *> &);
   void addPhiOfOps(PHINode *Op, BasicBlock *BB, Instruction *ExistingValue);
   void removePhiOfOps(Instruction *I, PHINode *PHITemp);
 
   // Value number an Instruction or MemoryPhi.
   void valueNumberMemoryPhi(MemoryPhi *);
   void valueNumberInstruction(Instruction *);
 
   // Symbolic evaluation.
void convertClassToDFSOrdered(const CongruenceClass &,
                                 SmallPtrSetImpl<Instruction *> &) const;
   void convertClassToLoadsAndStores(const CongruenceClass &,
                                     SmallVectorImpl<ValueDFS> &) const;
 
   bool eliminateInstructions(Function &);
   void replaceInstruction(Instruction *, Value *);
   void markInstructionForDeletion(Instruction *);
   void deleteInstructionsInBlock(BasicBlock *);
-  Value *findPhiOfOpsLeader(const Expression *E, const BasicBlock *BB) const;
-
+  Value *findPHIOfOpsLeader(const Expression *E, const BasicBlock *BB) const;
   // New instruction creation.
   void handleNewInstruction(Instruction *){};
 
   // Various instruction touch utilities
   template <typename Map, typename KeyType, typename Func>
   void for_each_found(Map &, const KeyType &, Func);
   template <typename Map, typename KeyType>
   void touchAndErase(Map &, const KeyType &);
if (I)
                    << " expression " << *CC->getDefiningExpr() << "\n");
     NumGVNOpsSimplified++;
     deleteExpression(E);
     return CC->getDefiningExpr();
   }
   return nullptr;
 }
 
-const Expression *NewGVN::createExpression(Instruction *I) const {
+// Create a value expression from the instruction I, replacing operands with
+// their leadesr.  If SafeToSimplify is true, we use the instruction simplifier
+// to try to simplify the resulting expression.  It is not always safe to
+// simplify, see makePossiblePhiOfOps for why.
+const Expression *NewGVN::createExpression(Instruction *I,
+                                           bool SafeToSimplify) const {
   auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
 
   bool AllConstant = setBasicExpressionInfo(I, E);
 
   if (I->isCommutative()) {
     // Ensure that commutative instructions that only differ by a permutation
     // of their operands get the same value number by sorting the operand value
     // numbers.  Since all commutative instructions have two operands it is more
     // efficient to sort by hand rather than using, say, std::sort.
     assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
     if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
       E->swapOperands(0, 1);
   }
-
+  if (!SafeToSimplify)
+    return E;
   // Perform simplification.
   // TODO: Right now we only check to see if we get a constant result.
   // We may get a less than constant, but still better, result for
   // some operations.
   // IE
   //  add 0, x -> x
   //  and x, x -> x
   // We should handle this by simply rewriting the expression.
if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
       // (IE things like calloc).
       if (const auto *CoercionResult =
               performSymbolicLoadCoercion(LI->getType(), LoadAddressLeader, LI,
                                           DefiningInst, DefiningAccess))
         return CoercionResult;
     }
   }
 
-  const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader,
-                                             LI, DefiningAccess);
+  const auto *LE = createLoadExpression(LI->getType(), LoadAddressLeader, LI,
+                                        DefiningAccess);
   // If our MemoryLeader is not our defining access, add a use to the
   // MemoryLeader, so that we get reprocessed when it changes.
   if (LE->getMemoryLeader() != DefiningAccess)
     addMemoryUsers(LE->getMemoryLeader(), OriginalAccess);
   return LE;
 }
 
 const Expression *
const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
   // 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
+      // In phi of ops cases, we may have predicate info that we are evaluating
+      // in a different context.
+      if (!DT->dominates(PBranch->To, getBlockForValue(I)))
+        continue;
+      // TODO: Along the false edge, we may know more things too, like
+      // icmp of
       // same operands is false.
-      // TODO: We only handle actual comparison conditions below, not and/or.
+      // TODO: We only handle actual comparison conditions below, not
+      // and/or.
       auto *BranchCond = dyn_cast<CmpInst>(PBranch->Condition);
       if (!BranchCond)
         continue;
       auto *BranchOp0 = lookupOperandLeader(BranchCond->getOperand(0));
       auto *BranchOp1 = lookupOperandLeader(BranchCond->getOperand(1));
       auto BranchPredicate = BranchCond->getPredicate();
       if (shouldSwapOperands(BranchOp0, BranchOp1)) {
         std::swap(BranchOp0, BranchOp1);
if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
             return createConstantExpression(
                 ConstantInt::getTrue(CI->getType()));
           }
         }
       }
     }
   }
   // Create expression will take care of simplifyCmpInst
-  return createExpression(I);
+  return createExpression(I, true);
 }
 
 // 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.
 static bool alwaysAvailable(Value *V) {
   return isa<Constant>(V) || isa<Argument>(V);
 }
case Instruction::Call:
       break;
     case Instruction::Store:
       E = performSymbolicStoreEvaluation(I);
       break;
     case Instruction::Load:
       E = performSymbolicLoadEvaluation(I);
       break;
     case Instruction::BitCast: {
-      E = createExpression(I);
+      E = createExpression(I, true);
     } break;
     case Instruction::ICmp:
     case Instruction::FCmp: {
       E = performSymbolicCmpEvaluation(I);
     } break;
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
     case Instruction::FPExt:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::Select:
     case Instruction::ExtractElement:
     case Instruction::InsertElement:
     case Instruction::ShuffleVector:
     case Instruction::GetElementPtr:
-      E = createExpression(I);
+      E = createExpression(I, true);
       break;
     default:
       return nullptr;
     }
   }
   return E;
 }
 

 void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) {
   // Evaluate reachability of terminator instruction.
   BranchInst *BR;
   if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) {
     Value *Cond = BR->getCondition();
     Value *CondEvaluated = findConditionEquivalence(Cond);
     if (!CondEvaluated) {
       if (auto *I = dyn_cast<Instruction>(Cond)) {
-        const Expression *E = createExpression(I);
+        const Expression *E = createExpression(I, true);
         if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
           CondEvaluated = CE->getConstantValue();
         }
       } else if (isa<ConstantInt>(Cond)) {
         CondEvaluated = Cond;
       }
     }
     ConstantInt *CI;

 
 static bool okayForPHIOfOps(const Instruction *I) {
   if (!EnablePhiOfOps)
     return false;
   return isa<BinaryOperator>(I) || isa<SelectInst>(I) || isa<CmpInst>(I) ||
          isa<LoadInst>(I);
 }
 
+// Return true if this operand will be safe to pass to the simplifier if used as
+// part of a phi of ops instruction.
+//
+// The reason some operands are unsafe is that we are not trying to recursively
+// translate everything back through phi nodes.  We actually expect some lookups
+// of expressions to fail.  However, the simplifier itself sometimes tries to
+// look through phi nodes as it simplifies.  If we have translated one operand
+// through a phi node, and another not, the simplifier will now not realize it
+// is looking at things from two different loop iterations, and get wrong
+// answers.  An example of this is pr33185.
+bool NewGVN::OpIsSafeForPHIOfOps(Value *V, Instruction *OrigInst,
+                                 const BasicBlock *PHIBlock,
+                                 SmallPtrSetImpl<const Value *> &Visited) {
+  if (!isa<Instruction>(V))
+    return true;
+  auto OISIt = OpSafeForPHIOfOps.find(V);
+  if (OISIt != OpSafeForPHIOfOps.end())
+    return OISIt->second;
+  // Keep walking until we either dominate the phi block, or hit a phi, or run
+  // out of things to check.  Note the order of checks is important. PHIs that
+  // strictly dominate our phi block are okay.  FIXME: I believe this is too
+  // restrictive, and the proper check for phi nodes should be whether they
+  // are in the same block as our current phi node.
+  if (DT->properlyDominates(getBlockForValue(V), PHIBlock)) {
+    OpSafeForPHIOfOps.insert({V, true});
+    return true;
+  }
+  // PHI in the same block.
+  if (isa<PHINode>(V) && getBlockForValue(V) == PHIBlock) {
+    OpSafeForPHIOfOps.insert({V, false});
+    return false;
+  }
+  for (auto Op : cast<Instruction>(V)->operand_values()) {
+    if (!isa<Instruction>(Op))
+      continue;
+    // See if we already know the answer for this node.
+    auto OISIt = OpSafeForPHIOfOps.find(Op);
+    if (OISIt != OpSafeForPHIOfOps.end()) {
+      if (!OISIt->second) {
+        OpSafeForPHIOfOps.insert({V, false});
+        return false;
+      }
+    }
+    if (!Visited.insert(Op).second)
+      continue;
+    if (!OpIsSafeForPHIOfOps(Op, OrigInst, PHIBlock, Visited)) {
+      OpSafeForPHIOfOps.insert({V, false});
+      return false;
+    }
+  }
+  OpSafeForPHIOfOps.insert({V, true});
+  return true;
+}
+
+Value *NewGVN::findLeaderForInst(Instruction *ValueOp,
+                                 SmallPtrSetImpl<Value *> &Visited,
+                                 bool SafeToSimplify, MemoryAccess *MemAccess,
+                                 Instruction *OrigInst, BasicBlock *PredBB) {
+  unsigned IDFSNum = InstrToDFSNum(OrigInst);
+  // Make sure it's marked as a temporary instruction.
+  AllTempInstructions.insert(ValueOp);
+  // and make sure anything that tries to add it's DFS number is
+  // redirected to the instruction we are making a phi of ops
+  // for.
+  TempToBlock.insert({ValueOp, PredBB});
+  InstrDFS.insert({ValueOp, IDFSNum});
+
+  const Expression *E = SafeToSimplify
+                            ? performSymbolicEvaluation(ValueOp, Visited)
+                            : createExpression(ValueOp, false);
+  InstrDFS.erase(ValueOp);
+  AllTempInstructions.erase(ValueOp);
+  TempToBlock.erase(ValueOp);
+  if (MemAccess)
+    TempToMemory.erase(ValueOp);
+  if (!E)
+    return nullptr;
+  auto *FoundVal = findPHIOfOpsLeader(E, PredBB);
+  if (!FoundVal || FoundVal == OrigInst) {
+    ExpressionToPhiOfOps[E].insert(OrigInst);
+    return nullptr;
+  }
+  if (auto *SI = dyn_cast<StoreInst>(FoundVal))
+    FoundVal = SI->getValueOperand();
+  return FoundVal;
+}
+
 // When we see an instruction that is an op of phis, generate the equivalent phi
 // of ops form.
 const Expression *
 NewGVN::makePossiblePhiOfOps(Instruction *I,
                              SmallPtrSetImpl<Value *> &Visited) {
   if (!okayForPHIOfOps(I))
     return nullptr;
 
   if (!Visited.insert(I).second)
     return nullptr;
   // For now, we require the instruction be cycle free because we don't
   // *always* create a phi of ops for instructions that could be done as phi
   // of ops, we only do it if we think it is useful.  If we did do it all the
   // time, we could remove the cycle free check.
   if (!isCycleFree(I))
     return nullptr;
 
-  unsigned IDFSNum = InstrToDFSNum(I);
   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 = 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->getDefiningAccess()) &&
       MemAccess->getDefiningAccess()->getBlock() == I->getParent())
     return nullptr;
 
+  SmallPtrSet<const Value *, 10> VisitedOps;
   // Convert op of phis to phi of ops
   for (auto &Op : I->operands()) {
-    // TODO: We can't handle expressions that must be recursively translated
-    // IE
-    // a = phi (b, c)
-    // f = use a
-    // g = f + phi of something
-    // To properly make a phi of ops for g, we'd have to properly translate and
-    // use the instruction for f.  We should add this by splitting out the
-    // instruction creation we do below.
-    if (isa<Instruction>(Op) && PHINodeUses.count(cast<Instruction>(Op)))
-      return nullptr;
     if (!isa<PHINode>(Op))
       continue;
     auto *OpPHI = cast<PHINode>(Op);
     // No point in doing this for one-operand phis.
     if (OpPHI->getNumOperands() == 1)
       continue;
     if (!DebugCounter::shouldExecute(PHIOfOpsCounter))
       return nullptr;
     SmallVector<std::pair<Value *, BasicBlock *>, 4> Ops;
     auto *PHIBlock = getBlockForValue(OpPHI);
     for (auto PredBB : OpPHI->blocks()) {
       Value *FoundVal = nullptr;
       // We could just skip unreachable edges entirely but it's tricky to do
       // with rewriting existing phi nodes.
       if (ReachableEdges.count({PredBB, PHIBlock})) {
         // Clone the instruction, create an expression from it, and see if we
         // have a leader.
         Instruction *ValueOp = I->clone();
         if (MemAccess)
           TempToMemory.insert({ValueOp, MemAccess});
-
+        bool SafeForPHIOfOps = true;
+        VisitedOps.clear();
         for (auto &Op : ValueOp->operands()) {
+          auto *OrigOp = &*Op;
           Op = Op->DoPHITranslation(PHIBlock, PredBB);
           // When this operand changes, it could change whether there is a
           // leader for us or not.
           addAdditionalUsers(Op, I);
-        }
-        // Make sure it's marked as a temporary instruction.
-        AllTempInstructions.insert(ValueOp);
-        // and make sure anything that tries to add it's DFS number is
-        // redirected to the instruction we are making a phi of ops
-        // for.
-        InstrDFS.insert({ValueOp, IDFSNum});
-        const Expression *E = performSymbolicEvaluation(ValueOp, Visited);
-        InstrDFS.erase(ValueOp);
-        AllTempInstructions.erase(ValueOp);
+          // If we phi-translated the op, it must be safe.
+          SafeForPHIOfOps = SafeForPHIOfOps &&
+                            (Op != OrigOp ||
+                             OpIsSafeForPHIOfOps(Op, I, PHIBlock, VisitedOps));
+        }
+        // FIXME: For those things that are not safe We could generate
+        // expressions all the way down, and see if this comes out to a
+        // constant.  For anything where that is true, and unsafe, we should
+        // have made a phi-of-ops (or value numbered it equivalent to something)
+        // for the pieces already.
+        FoundVal = !SafeForPHIOfOps
+                       ? nullptr
+                       : findLeaderForInst(ValueOp, Visited, SafeForPHIOfOps,
+                                           MemAccess, I, PredBB);
         ValueOp->deleteValue();
-        if (MemAccess)
-          TempToMemory.erase(ValueOp);
-        if (!E)
+        if (!FoundVal)
           return nullptr;
-        FoundVal = findPhiOfOpsLeader(E, PredBB);
-        if (!FoundVal) {
-          ExpressionToPhiOfOps[E].insert(I);
-          return nullptr;
-        }
-        if (auto *SI = dyn_cast<StoreInst>(FoundVal))
-          FoundVal = SI->getValueOperand();
       } else {
         DEBUG(dbgs() << "Skipping phi of ops operand for incoming block "
                      << getBlockName(PredBB)
                      << " because the block is unreachable\n");
         FoundVal = UndefValue::get(I->getType());
       }
 
       Ops.push_back({FoundVal, PredBB});
       DEBUG(dbgs() << "Found phi of ops operand " << *FoundVal << " in "
                    << getBlockName(PredBB) << "\n");
     }
     auto *ValuePHI = RealToTemp.lookup(I);
     bool NewPHI = false;
     if (!ValuePHI) {
-      ValuePHI = PHINode::Create(I->getType(), OpPHI->getNumOperands());
+      ValuePHI =
+          PHINode::Create(I->getType(), OpPHI->getNumOperands(), "phiofops");
       addPhiOfOps(ValuePHI, PHIBlock, I);
       NewPHI = true;
       NumGVNPHIOfOpsCreated++;
     }
     if (NewPHI) {
       for (auto PHIOp : Ops)
         ValuePHI->addIncoming(PHIOp.first, PHIOp.second);
     } else {
void NewGVN::cleanupTables() {
   ExpressionToClass.clear();
   ValueToExpression.clear();
   RealToTemp.clear();
   AdditionalUsers.clear();
   ExpressionToPhiOfOps.clear();
   TempToBlock.clear();
   TempToMemory.clear();
   PHIOfOpsPHIs.clear();
+  PHINodeUses.clear();
+  OpSafeForPHIOfOps.clear();
   ReachableBlocks.clear();
   ReachableEdges.clear();
 #ifndef NDEBUG
   ProcessedCount.clear();
 #endif
   InstrDFS.clear();
   InstructionsToErase.clear();
   DFSToInstr.clear();

 
 private:
   SmallVector<Value *, 8> ValueStack;
   SmallVector<std::pair<int, int>, 8> DFSStack;
 };
 }
 
 // Given a value and a basic block we are trying to see if it is available in,
-// see if the value has a leader available in that block.
-Value *NewGVN::findPhiOfOpsLeader(const Expression *E,
+// see if the value has a leader available in that block, and that will dominate
+// OrigInst.
+Value *NewGVN::findPHIOfOpsLeader(const Expression *E,
                                   const BasicBlock *BB) const {
   // It would already be constant if we could make it constant
   if (auto *CE = dyn_cast<ConstantExpression>(E))
     return CE->getConstantValue();
   if (auto *VE = dyn_cast<VariableExpression>(E))
     return VE->getVariableValue();
 
   auto *CC = ExpressionToClass.lookup(E);
   if (!CC)
     return nullptr;
   if (alwaysAvailable(CC->getLeader()))
     return CC->getLeader();
 
   for (auto Member : *CC) {
     auto *MemberInst = dyn_cast<Instruction>(Member);
     // Anything that isn't an instruction is always available.
     if (!MemberInst)
       return Member;
     // If we are looking for something in the same block as the member, it must
-    // be a leader because this function is looking for operands for a phi node.
-    if (MemberInst->getParent() == BB ||
-        DT->dominates(MemberInst->getParent(), BB)) {
+    // occur before OrigInst to be valid.  Otherwise, we may pull the wrong
+    // version over a loop backedge.  Similarly, we have to ensure it is not in
+    // a block dominated by OrigInst, or else we can't guarantee that it isn't
+    // dependent on it.
+    if (DT->dominates(MemberInst->getParent(), BB))
       return Member;
-    }
-  }
   return nullptr;
 }
 
 bool NewGVN::eliminateInstructions(Function &F) {
   // This is a non-standard eliminator. The normal way to eliminate is
   // to walk the dominator tree in order, keeping track of available
   // values, and eliminating them.  However, this is mildly
   // pointless. It requires doing lookups on every instruction,

test/Transforms/NewGVN/completeness.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basicaa -newgvn -enable-phi-of-ops=true -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:         [[PHIOFOPS:%.*]] = phi i32 [ 75, [[TMP4]] ], [ 105, [[TMP5]] ]
 ; CHECK-NEXT:    [[DOT0:%.*]] = phi i32 [ 5, [[TMP4]] ], [ 7, [[TMP5]] ]
-; CHECK-NEXT:    ret i32 [[TMP7]]
+; CHECK-NEXT:    ret i32 [[PHIOFOPS]]
 ;
   %3 = icmp ne i32 %0, 0
   br i1 %3, label %4, label %5
 
 ; <label>:4:                                      ; preds = %2
   br label %6
 
 ; <label>:5:                                      ; preds = %2

 }
 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:    [[PHIOFOPS:%.*]] = phi i32 [ -877, [[ENTRY:%.*]] ], [ 113, [[DELAY]] ]
 ; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1000, [[ENTRY]] ], [ 10, [[DELAY]] ]
-; CHECK-NEXT:    ret i32 [[TMP0]]
+; CHECK-NEXT:    ret i32 [[PHIOFOPS]]
 ;
 
 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:    [[PHIOFOPS:%.*]] = 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]]
+; CHECK-NEXT:    ret <2 x i32> [[PHIOFOPS]]
 ;
 
 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:    [[PHIOFOPS:%.*]] = 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]]
+; CHECK-NEXT:    ret <2 x i32> [[PHIOFOPS]]
 ;
 
 entry:
   br i1 %which, label %final, label %delay
 
 delay:
   br label %final
 

 ; 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:    [[PHIOFOPS:%.*]] = 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:    store i64 [[PHIOFOPS]], 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]]

 }
 
 ;; 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 [ true, %entry-block ], [ false, [[CORE:%.*]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ false, %entry-block ], [ true, [[CORE]] ]
+; CHECK-NEXT:    [[PHIOFOPS1:%.*]] = phi i1 [ true, %entry-block ], [ false, [[CORE:%.*]] ]
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i1 [ false, %entry-block ], [ true, [[CORE]] ]
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i8 [ 0, %entry-block ], [ 1, [[CORE]] ]
 ; CHECK-NEXT:    store volatile i8 0, i8* [[ADDR:%.*]]
-; CHECK-NEXT:    br i1 [[TMP0]], label %busy-wait-phi-0, label [[EXIT:%.*]]
+; CHECK-NEXT:    br i1 [[PHIOFOPS1]], 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 [[TMP1]], label [[TRAP:%.*]], label %main-loop
+; CHECK-NEXT:    br i1 [[PHIOFOPS]], 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
 

 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB2:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB6:%.*]]
 ; CHECK:       bb6:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ -13, [[BB2]] ], [ [[TMP11:%.*]], [[BB6]] ]
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i32 [ -13, [[BB2]] ], [ [[TMP11:%.*]], [[BB6]] ]
 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i32 [ 1, [[BB2]] ], [ [[TMP8:%.*]], [[BB6]] ]
 ; CHECK-NEXT:    [[TMP8]] = add nuw nsw i32 [[TMP7]], 1
 ; CHECK-NEXT:    [[TMP11]] = add i32 -14, [[TMP8]]
 ; CHECK-NEXT:    br label [[BB6]]
 ;
 bb:
   br label %bb1
 

test/Transforms/NewGVN/pr33185.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -newgvn -S %s | FileCheck %s
 
 @a = local_unnamed_addr global i32 9, align 4
 @.str4 = private unnamed_addr constant [6 x i8] c"D:%d\0A\00", align 1
 
-define i32 @main() local_unnamed_addr {
-; CHECK-LABEL: @main(
+define i32 @test1() local_unnamed_addr {
+; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[CMP1_I:%.*]] = icmp ne i32 [[TMP]], 0
 ; CHECK-NEXT:    br label [[FOR_BODY_I:%.*]]
 ; CHECK:       for.body.i:
 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ false, [[COND_END_I:%.*]] ]
 ; CHECK-NEXT:    [[F_08_I:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC_I:%.*]], [[COND_END_I]] ]
 ; CHECK-NEXT:    [[MUL_I:%.*]] = select i1 [[CMP1_I]], i32 [[F_08_I]], i32 0

 fn1.exit:
   %cond.i.lcssa = phi i32 [ %cond.i, %cond.end.i ]
   %call4= tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0), i32 %cond.i.lcssa)
   ret i32 0
 }
 
 declare i32 @printf(i8* nocapture readonly, ...)
 
+;; Variant of the above where we have made the udiv available in each predecessor with the wrong values.
+;; In the entry block, it is always 0, so we don't try to create a leader there, only in %cond.end.i.
+;; We should not create a phi of ops for it using these leaders.
+;; A correct phi of ops for this udiv would be phi(0, 1), which we are not smart enough to figure out.
+;; If we reuse the incorrect leaders, we will get phi(0, 0).
+define i32 @test2() local_unnamed_addr {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP:%.*]] = load i32, i32* @a, align 4
+; CHECK-NEXT:    [[CMP1_I:%.*]] = icmp ne i32 [[TMP]], 0
+; CHECK-NEXT:    br label [[FOR_BODY_I:%.*]]
+; CHECK:       for.body.i:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ false, [[COND_END_I:%.*]] ]
+; CHECK-NEXT:    [[F_08_I:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC_I:%.*]], [[COND_END_I]] ]
+; CHECK-NEXT:    [[MUL_I:%.*]] = select i1 [[CMP1_I]], i32 [[F_08_I]], i32 0
+; CHECK-NEXT:    br i1 [[TMP1]], label [[COND_END_I]], label [[COND_TRUE_I:%.*]]
+; CHECK:       cond.true.i:
+; CHECK-NEXT:    [[DIV_I:%.*]] = udiv i32 [[MUL_I]], [[F_08_I]]
+; CHECK-NEXT:    br label [[COND_END_I]]
+; CHECK:       cond.end.i:
+; CHECK-NEXT:    [[COND_I:%.*]] = phi i32 [ [[DIV_I]], [[COND_TRUE_I]] ], [ 0, [[FOR_BODY_I]] ]
+; CHECK-NEXT:    [[INC_I]] = add nuw nsw i32 [[F_08_I]], 1
+; CHECK-NEXT:    [[CALL5:%.*]] = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0), i32 0)
+; CHECK-NEXT:    [[EXITCOND_I:%.*]] = icmp eq i32 [[INC_I]], 4
+; CHECK-NEXT:    br i1 [[EXITCOND_I]], label [[FN1_EXIT:%.*]], label [[FOR_BODY_I]]
+; CHECK:       fn1.exit:
+; CHECK-NEXT:    [[CALL4:%.*]] = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0), i32 [[COND_I]])
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %tmp = load i32, i32* @a, align 4
+  %cmp1.i = icmp ne i32 %tmp, 0
+  br label %for.body.i
+
+for.body.i:
+  %tmp1 = phi i1 [ true, %entry ], [ false, %cond.end.i ]
+  %f.08.i = phi i32 [ 0, %entry ], [ %inc.i, %cond.end.i ]
+  %mul.i = select i1 %cmp1.i, i32 %f.08.i, i32 0
+  br i1 %tmp1, label %cond.end.i, label %cond.true.i
+
+cond.true.i:
+  ;; Ensure we don't replace this divide with a phi of ops that merges the wrong loop iteration value
+  %div.i = udiv i32 %mul.i, %f.08.i
+  br label %cond.end.i
+
+cond.end.i:
+  %cond.i = phi i32 [ %div.i, %cond.true.i ], [ 0, %for.body.i ]
+  %inc.i = add nuw nsw i32 %f.08.i, 1
+  %test = udiv i32 %mul.i, %inc.i
+  %call5= tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0), i32 %test)
+  %exitcond.i = icmp eq i32 %inc.i, 4
+  br i1 %exitcond.i, label %fn1.exit, label %for.body.i
+
+fn1.exit:
+  %cond.i.lcssa = phi i32 [ %cond.i, %cond.end.i ]
+  %call4= tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([6 x i8], [6 x i8]* @.str4, i64 0, i64 0), i32 %cond.i.lcssa)
+  ret i32 0
+}
+
+

test/Transforms/NewGVN/pr33305.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -newgvn -S %s | FileCheck %s
+; Ensure we do not incorrect do phi of ops
+source_filename = "/Users/dannyb/sources/llvm-clean/debug-build/pr33305.c"
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.12.0"
+
+@a = common global i32 0, align 4
+@b = local_unnamed_addr global i32* @a, align 8
+@e = local_unnamed_addr global i32 -1, align 4
+@g = local_unnamed_addr global i32 1, align 4
+@c = common local_unnamed_addr global i32 0, align 4
+@f = common local_unnamed_addr global i32 0, align 4
+@h = common local_unnamed_addr global i32 0, align 4
+@str = private unnamed_addr constant [5 x i8] c"fine\00"
+@str.2 = private unnamed_addr constant [8 x i8] c"Screwed\00"
+
+; Function Attrs: nounwind optsize ssp uwtable
+define i32 @main() local_unnamed_addr #0 {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[DOTPR_I:%.*]] = load i32, i32* @c, align 4, !tbaa !3
+; CHECK-NEXT:    [[CMP13_I:%.*]] = icmp slt i32 [[DOTPR_I]], 1
+; CHECK-NEXT:    br i1 [[CMP13_I]], label [[FOR_COND1_PREHEADER_LR_PH_I:%.*]], label [[ENTRY_FOR_END9_I_CRIT_EDGE:%.*]]
+; CHECK:       entry.for.end9.i_crit_edge:
+; CHECK-NEXT:    [[DOTPRE:%.*]] = load i32, i32* @h, align 4, !tbaa !3
+; CHECK-NEXT:    br label [[FOR_END9_I:%.*]]
+; CHECK:       for.cond1.preheader.lr.ph.i:
+; CHECK-NEXT:    [[G_PROMOTED14_I:%.*]] = load i32, i32* @g, align 4, !tbaa !3
+; CHECK-NEXT:    br label [[FOR_COND1_PREHEADER_I:%.*]]
+; CHECK:       for.cond1.preheader.i:
+; CHECK-NEXT:    [[INC816_I:%.*]] = phi i32 [ [[DOTPR_I]], [[FOR_COND1_PREHEADER_LR_PH_I]] ], [ [[INC8_I:%.*]], [[FOR_INC7_I:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[G_PROMOTED14_I]], [[FOR_COND1_PREHEADER_LR_PH_I]] ], [ 0, [[FOR_INC7_I]] ]
+; CHECK-NEXT:    br label [[FOR_BODY3_I:%.*]]
+; CHECK:       for.body3.i:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ false, [[FOR_COND1_PREHEADER_I]] ], [ true, [[LOR_END_I:%.*]] ]
+; CHECK-NEXT:    [[INC12_I:%.*]] = phi i32 [ 0, [[FOR_COND1_PREHEADER_I]] ], [ [[INC_I:%.*]], [[LOR_END_I]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ [[TMP0]], [[FOR_COND1_PREHEADER_I]] ], [ 0, [[LOR_END_I]] ]
+; CHECK-NEXT:    [[TOBOOL_I:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    [[OR_COND_I:%.*]] = and i1 [[TMP1]], [[TOBOOL_I]]
+; CHECK-NEXT:    br i1 [[OR_COND_I]], label [[LOR_END_I]], label [[LOR_RHS_I:%.*]]
+; CHECK:       lor.rhs.i:
+; CHECK-NEXT:    [[LNOT_I:%.*]] = xor i1 [[TOBOOL_I]], true
+; CHECK-NEXT:    [[LNOT_EXT_I:%.*]] = zext i1 [[LNOT_I]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* @e, align 4, !tbaa !3
+; CHECK-NEXT:    [[XOR_I:%.*]] = xor i32 [[TMP3]], [[LNOT_EXT_I]]
+; CHECK-NEXT:    store i32 [[XOR_I]], i32* @e, align 4, !tbaa !3
+; CHECK-NEXT:    br label [[LOR_END_I]]
+; CHECK:       lor.end.i:
+; CHECK-NEXT:    [[INC_I]] = add nuw nsw i32 [[INC12_I]], 1
+; CHECK-NEXT:    [[EXITCOND_I:%.*]] = icmp eq i32 [[INC_I]], 2
+; CHECK-NEXT:    br i1 [[EXITCOND_I]], label [[FOR_INC7_I]], label [[FOR_BODY3_I]]
+; CHECK:       for.inc7.i:
+; CHECK-NEXT:    [[INC8_I]] = add nsw i32 [[INC816_I]], 1
+; CHECK-NEXT:    [[CMP_I:%.*]] = icmp slt i32 [[INC816_I]], 0
+; CHECK-NEXT:    br i1 [[CMP_I]], label [[FOR_COND1_PREHEADER_I]], label [[FOR_COND_FOR_END9_CRIT_EDGE_I:%.*]]
+; CHECK:       for.cond.for.end9_crit_edge.i:
+; CHECK-NEXT:    store i32 0, i32* @g, align 4, !tbaa !3
+; CHECK-NEXT:    store i32 2, i32* @h, align 4, !tbaa !3
+; CHECK-NEXT:    store i32 [[INC8_I]], i32* @c, align 4, !tbaa !3
+; CHECK-NEXT:    br label [[FOR_END9_I]]
+; CHECK:       for.end9.i:
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i32 [ [[DOTPRE]], [[ENTRY_FOR_END9_I_CRIT_EDGE]] ], [ 2, [[FOR_COND_FOR_END9_CRIT_EDGE_I]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = load i32*, i32** @b, align 8, !tbaa !7
+; CHECK-NEXT:    store i32 [[TMP4]], i32* [[TMP5]], align 4, !tbaa !3
+; CHECK-NEXT:    [[TMP6:%.*]] = load i32, i32* @e, align 4, !tbaa !3
+; CHECK-NEXT:    [[CMP10_I:%.*]] = icmp slt i32 [[TMP6]], -1
+; CHECK-NEXT:    br i1 [[CMP10_I]], label [[IF_THEN_I:%.*]], label [[FN1_EXIT:%.*]]
+; CHECK:       if.then.i:
+; CHECK-NEXT:    [[TMP7:%.*]] = load i32, i32* @f, align 4, !tbaa !3
+; CHECK-NEXT:    store i32 [[TMP7]], i32* [[TMP5]], align 4, !tbaa !3
+; CHECK-NEXT:    br label [[FN1_EXIT]]
+; CHECK:       fn1.exit:
+; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* @a, align 4, !tbaa !3
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TMP8]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[PUTS2:%.*]] = tail call i32 @puts(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @str.2, i64 0, i64 0))
+; CHECK-NEXT:    tail call void @abort() #4
+; CHECK-NEXT:    unreachable
+; CHECK:       if.end:
+; CHECK-NEXT:    [[PUTS:%.*]] = tail call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @str, i64 0, i64 0))
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %.pr.i = load i32, i32* @c, align 4, !tbaa !3
+  %cmp13.i = icmp slt i32 %.pr.i, 1
+  br i1 %cmp13.i, label %for.cond1.preheader.lr.ph.i, label %entry.for.end9.i_crit_edge
+
+entry.for.end9.i_crit_edge:                       ; preds = %entry
+  %.pre = load i32, i32* @h, align 4, !tbaa !3
+  br label %for.end9.i
+
+for.cond1.preheader.lr.ph.i:                      ; preds = %entry
+  %g.promoted14.i = load i32, i32* @g, align 4, !tbaa !3
+  br label %for.cond1.preheader.i
+
+for.cond1.preheader.i:                            ; preds = %for.inc7.i, %for.cond1.preheader.lr.ph.i
+  %inc816.i = phi i32 [ %.pr.i, %for.cond1.preheader.lr.ph.i ], [ %inc8.i, %for.inc7.i ]
+  %0 = phi i32 [ %g.promoted14.i, %for.cond1.preheader.lr.ph.i ], [ 0, %for.inc7.i ]
+  br label %for.body3.i
+
+for.body3.i:                                      ; preds = %lor.end.i, %for.cond1.preheader.i
+  %1 = phi i1 [ false, %for.cond1.preheader.i ], [ true, %lor.end.i ]
+  %inc12.i = phi i32 [ 0, %for.cond1.preheader.i ], [ %inc.i, %lor.end.i ]
+  %2 = phi i32 [ %0, %for.cond1.preheader.i ], [ 0, %lor.end.i ]
+  %tobool.i = icmp ne i32 %2, 0
+  %or.cond.i = and i1 %1, %tobool.i
+  br i1 %or.cond.i, label %lor.end.i, label %lor.rhs.i
+
+lor.rhs.i:                                        ; preds = %for.body3.i
+  %lnot.i = xor i1 %tobool.i, true
+  %lnot.ext.i = zext i1 %lnot.i to i32
+  %3 = load i32, i32* @e, align 4, !tbaa !3
+  %xor.i = xor i32 %3, %lnot.ext.i
+  store i32 %xor.i, i32* @e, align 4, !tbaa !3
+  br label %lor.end.i
+
+lor.end.i:                                        ; preds = %lor.rhs.i, %for.body3.i
+  %inc.i = add nuw nsw i32 %inc12.i, 1
+  %exitcond.i = icmp eq i32 %inc.i, 2
+  br i1 %exitcond.i, label %for.inc7.i, label %for.body3.i
+
+for.inc7.i:                                       ; preds = %lor.end.i
+  %inc8.i = add nsw i32 %inc816.i, 1
+  %cmp.i = icmp slt i32 %inc816.i, 0
+  br i1 %cmp.i, label %for.cond1.preheader.i, label %for.cond.for.end9_crit_edge.i
+
+for.cond.for.end9_crit_edge.i:                    ; preds = %for.inc7.i
+  store i32 0, i32* @g, align 4, !tbaa !3
+  store i32 2, i32* @h, align 4, !tbaa !3
+  store i32 %inc8.i, i32* @c, align 4, !tbaa !3
+  br label %for.end9.i
+
+for.end9.i:                                       ; preds = %entry.for.end9.i_crit_edge, %for.cond.for.end9_crit_edge.i
+  %4 = phi i32 [ %.pre, %entry.for.end9.i_crit_edge ], [ 2, %for.cond.for.end9_crit_edge.i ]
+  %5 = load i32*, i32** @b, align 8, !tbaa !7
+  store i32 %4, i32* %5, align 4, !tbaa !3
+  %6 = load i32, i32* @e, align 4, !tbaa !3
+  %cmp10.i = icmp slt i32 %6, -1
+  br i1 %cmp10.i, label %if.then.i, label %fn1.exit
+
+if.then.i:                                        ; preds = %for.end9.i
+  %7 = load i32, i32* @f, align 4, !tbaa !3
+  store i32 %7, i32* %5, align 4, !tbaa !3
+  br label %fn1.exit
+
+fn1.exit:                                         ; preds = %if.then.i, %for.end9.i
+  %8 = load i32, i32* @a, align 4, !tbaa !3
+  %tobool = icmp eq i32 %8, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %fn1.exit
+  %puts2 = tail call i32 @puts(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @str.2, i64 0, i64 0))
+  tail call void @abort() #3
+  unreachable
+
+if.end:                                           ; preds = %fn1.exit
+  %puts = tail call i32 @puts(i8* getelementptr inbounds ([5 x i8], [5 x i8]* @str, i64 0, i64 0))
+  ret i32 0
+}
+
+; Function Attrs: noreturn nounwind optsize
+declare void @abort() local_unnamed_addr #1
+
+; Function Attrs: nounwind
+declare i32 @puts(i8* nocapture readonly) local_unnamed_addr #2
+
+attributes #0 = { nounwind optsize ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { noreturn nounwind optsize "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind }
+attributes #3 = { noreturn nounwind optsize }
+
+!llvm.module.flags = !{!0, !1}
+!llvm.ident = !{!2}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{i32 7, !"PIC Level", i32 2}
+!2 = !{!"clang version 5.0.0 (http://llvm.org/git/clang.git e97b4dda83fd49e0218ea06ba4e37796a81b2027) (/Users/dannyb/sources/llvm-clean b38f051979e4ac2aa6513e40046d120fd472cb96)"}
+!3 = !{!4, !4, i64 0}
+!4 = !{!"int", !5, i64 0}
+!5 = !{!"omnipotent char", !6, i64 0}
+!6 = !{!"Simple C/C++ TBAA"}
+!7 = !{!8, !8, i64 0}
+!8 = !{!"any pointer", !5, i64 0}

test/Transforms/NewGVN/pr33432.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -newgvn -S %s | FileCheck %s
+; Ensure we do not incorrect do phi of ops
+@d = external local_unnamed_addr global i32, align 4
+
+define void @patatino() {
+; CHECK-LABEL: @patatino(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* @d, align 4
+; CHECK-NEXT:    br label [[FOR_END10:%.*]]
+; CHECK:       for.end10:
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[TMP0]], 8
+; CHECK-NEXT:    br i1 undef, label [[IF_END:%.*]], label [[FOR_END10]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %0 = load i32, i32* @d, align 4
+  br label %for.end10
+
+for.end10:
+  %f.0 = phi i32 [ undef, %entry ], [ 8, %for.end10 ]
+  %or = or i32 %0, %f.0
+  %mul12 = mul nsw i32 %or, undef
+  br i1 undef, label %if.end, label %for.end10
+
+if.end:
+  ret void
+}
+

test/Transforms/NewGVN/pr33461.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ;; Ensure the store verifier is not overzealous
 ; RUN: opt -newgvn -enable-phi-of-ops=true -S %s | FileCheck %s
 @b = external global i16, align 2
 
 define void @patatino() {
 ; CHECK-LABEL: @patatino(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 false, label [[FOR_COND1:%.*]], label [[FOR_INC:%.*]]
 ; CHECK:       for.cond1:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i16 [ [[INC:%.*]], [[FOR_INC]] ], [ undef, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    store i16 [[TMP0]], i16* @b, align 2
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i16 [ [[INC:%.*]], [[FOR_INC]] ], [ undef, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    store i16 [[PHIOFOPS]], i16* @b, align 2
 ; CHECK-NEXT:    br label [[FOR_INC]]
 ; CHECK:       for.inc:
-; CHECK-NEXT:    [[TMP1:%.*]] = load i16, i16* @b, align 2
-; CHECK-NEXT:    [[INC]] = add i16 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = load i16, i16* @b, align 2
+; CHECK-NEXT:    [[INC]] = add i16 [[TMP0]], 1
 ; CHECK-NEXT:    store i16 [[INC]], i16* @b, align 2
 ; CHECK-NEXT:    br label [[FOR_COND1]]
 ;
 entry:
   br i1 false, label %for.cond1, label %for.inc
 
 for.cond1:
   %e.0 = phi i16* [ %e.1, %for.inc ], [ null, %entry ]

test/Transforms/NewGVN/pr34135.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -newgvn -enable-phi-of-ops=true -S | FileCheck %s
+;; Make sure we don't incorrectly use predicateinfo to simplify phi of ops cases
+source_filename = "pr34135.ll"
+
+define void @snork(i32 %arg) {
+; CHECK-LABEL: @snork(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = sext i32 [[ARG:%.*]] to i64
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ 0, [[BB:%.*]] ], [ [[TMP3:%.*]], [[BB1]] ]
+; CHECK-NEXT:    [[TMP3]] = add i64 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp slt i64 [[TMP3]], [[TMP]]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[BB1]], label [[BB7:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp sgt i64 [[TMP]], 1
+; CHECK-NEXT:    br i1 [[TMP6]], label [[BB7]], label [[BB9:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb9:
+; CHECK-NEXT:    unreachable
+;
+bb:
+  %tmp = sext i32 %arg to i64
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %bb
+  %tmp2 = phi i64 [ 0, %bb ], [ %tmp3, %bb1 ]
+  %tmp3 = add i64 %tmp2, 1
+  %tmp4 = icmp slt i64 %tmp3, %tmp
+  br i1 %tmp4, label %bb1, label %bb7
+
+bb5:                                              ; preds = %bb7
+  %tmp6 = icmp sgt i64 %tmp8, 1
+  br i1 %tmp6, label %bb7, label %bb9
+
+bb7:                                              ; preds = %bb5, %bb1
+  %tmp8 = phi i64 [ undef, %bb5 ], [ %tmp, %bb1 ]
+  br label %bb5
+
+bb9:                                              ; preds = %bb5
+  unreachable
+}