[NewGVN] Track simplification dependencies for phi-of-ops.

[fhahn]

Summary

If we are using a simplified value, we need to add an extra
dependency this value , because changes to the class of the
simplified value may require us to invalidate any decision based on
that value.

This is done by adding such values as additional users, however the
current code does not excludes temporary instructions.

At the moment, this means that we miss those dependencies for
phi-of-ops, because they are temporary instructions at this point. We
instead need to add the extra dependencies to the root instruction of
the phi-of-ops.

This patch pushes the responsibility of adding extra users to the
callers of createExpression & performSymbolicEvaluation. At those
points, it is clearer which real instruction to pick.

Alternatively we could either pass the 'real' instruction as additional
argument or use another map, but I think the approach in the patch makes
things a bit easier to follow.

Fixes PR35074.

[ruiling]

llvm/lib/Transforms/Scalar/NewGVN.cpp

1880–1906

I think we also need to return the PI->Condition as ExtraDep together with the expression for such cases, this is what I saw in the case PR49873 that we failed to mark the 'real' instruction (i.e. op-of-phi) depends on this predicate compare.

1914

Do we need to check that I is not a temp instruction before making it depends on other instruction? I think the I here may be a temp instruction if this is called from makePossiblePHIOfOps()->FindLeaderForInst()->performSymbolicEvaluation()->performSymbolicCmpEvaluation().

[fhahn]

Update performSymbolicCmpEvaluation to return ExprResult, so ExtraDeps created by the call to createExpression can be handled properly. Also add an assert to ExprResult to make sure ExtraDep is handled to the destructor.

[fhahn]

llvm/lib/Transforms/Scalar/NewGVN.cpp

1880–1906

Thanks, I'll give that a try, but I think it's worth to do this as follow-up patch.

1914

That's a good point, thanks! I updated performSymbolicCmpEvaluation to directly return ExprResult as well, so this case should also be handled properly in the caller now.

[fhahn]

Update addExtraUserTo to take AdditionalUsers instead of callback to simplify code.

[fhahn]

llvm/lib/Transforms/Scalar/NewGVN.cpp

1880–1906

I updated performSymbolicPredicateInfoEvaluation in D100560 to use the same approach to register additional dependencies for the predicate simplification.

[fhahn]

ping :)

[asbirlea]

I think it makes sense to add the users at the upper call level where the real instruction is known. Just one comment inline.

llvm/lib/Transforms/Scalar/NewGVN.cpp

692

For consistency with the rest of the GVN APIs, I wound't add this functionality inside ExprResult.
I think an API akin to addAdditionalUsers, which queries the ExprResult for the dependency field and adds the user would maintain this consistency. It can even call addAdditionalUsers after the first two checks; and in the dependent patch, it would also call addPredicateUsers.
What do you think?

[fhahn]

Replace addExtraUsers with an addAdditionalUsers variant that takes ExprResult as argument.

[fhahn]

llvm/lib/Transforms/Scalar/NewGVN.cpp

692

Thanks, I think that makes a lot of sense! I updated the patch to use a new addAdditionalUsers variant which takes a ExprResult argument. I'll update the other patches tomorrow, if that looks good.

[asbirlea]

Thank you! Looks good.

A note for the dependent patch, if it will also adds predicate users, perhaps the name addAdditionalUsers need not be overloaded (though addAdditionalAndPredicateUsers is a bit verbose).
If it makes sense to inline the predicate API into the new one, and remove it, I'd be ok with that.

llvm/lib/Transforms/Scalar/NewGVN.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
NewGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
       : F(F), DT(DT), TLI(TLI), AA(AA), MSSA(MSSA), AC(AC), DL(DL),
         PredInfo(std::make_unique<PredicateInfo>(F, *DT, *AC)),
         SQ(DL, TLI, DT, AC, /*CtxI=*/nullptr, /*UseInstrInfo=*/false,
            /*CanUseUndef=*/false) {}
 
   bool runGVN();
 
 private:
+  /// Helper struct return a Expression with an optional extra dependency.
+  struct ExprResult {
+    const Expression *Expr;
+    Value *ExtraDep;
+
+    ~ExprResult() { assert(!ExtraDep && "unhandled ExtraDep"); }
+
+    operator bool() const { return Expr; }
+
+    static ExprResult none() { return {nullptr, nullptr}; }
+    static ExprResult some(const Expression *Expr, Value *ExtraDep = nullptr) {
+      return {Expr, ExtraDep};
+    }
+
+    /// Add \p User as an additional user of ExtraDep, if it is set, using \p
+    /// AdditionalUsers.
+    void addExtraUserTo(
+        Instruction *User,
+        DenseMap<const Value *, SmallPtrSet<Value *, 2>> &AdditionalUsers) {
+      if (ExtraDep && ExtraDep != User && isa<Instruction>(ExtraDep))
+        AdditionalUsers[ExtraDep].insert(User);
+      ExtraDep = nullptr;
+    }
+  };
+
   // Expression handling.
-  const Expression *createExpression(Instruction *) const;
+  ExprResult createExpression(Instruction *) const;
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
                                            Instruction *) const;
 
   // Our canonical form for phi arguments is a pair of incoming value, incoming
   // basic block.
   using ValPair = std::pair<Value *, BasicBlock *>;
 
   PHIExpression *createPHIExpression(ArrayRef<ValPair>, const Instruction *,
private:
   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.
-  const Expression *checkSimplificationResults(Expression *, Instruction *,
-                                               Value *) const;
-  const Expression *performSymbolicEvaluation(Value *,
-                                              SmallPtrSetImpl<Value *> &) const;
+  ExprResult checkExprResults(Expression *, Instruction *, Value *) const;
+  ExprResult performSymbolicEvaluation(Value *,
   const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *,
                                                 Instruction *,
                                                 MemoryAccess *) const;
   const Expression *performSymbolicLoadEvaluation(Instruction *) const;
   const Expression *performSymbolicStoreEvaluation(Instruction *) const;
   const Expression *performSymbolicCallEvaluation(Instruction *) const;
   void sortPHIOps(MutableArrayRef<ValPair> Ops) const;
   const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>,
                                                  Instruction *I,
                                                  BasicBlock *PHIBlock) const;
   const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
-  const Expression *performSymbolicCmpEvaluation(Instruction *) const;
+  ExprResult performSymbolicCmpEvaluation(Instruction *) const;
   const Expression *performSymbolicPredicateInfoEvaluation(Instruction *) const;
 
   // Congruence finding.
   bool someEquivalentDominates(const Instruction *, const Instruction *) const;
   Value *lookupOperandLeader(Value *) const;
   CongruenceClass *getClassForExpression(const Expression *E) const;
   void performCongruenceFinding(Instruction *, const Expression *);
   void moveValueToNewCongruenceClass(Instruction *, const Expression *,
if (Instruction::isCommutative(Opcode)) {
     // efficient to sort by hand rather than using, say, std::sort.
     if (shouldSwapOperands(Arg1, Arg2))
       std::swap(Arg1, Arg2);
   }
   E->op_push_back(lookupOperandLeader(Arg1));
   E->op_push_back(lookupOperandLeader(Arg2));
 
   Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), SQ);
-  if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
-    return SimplifiedE;
+  if (auto Simplified = checkExprResults(E, I, V)) {
+    Simplified.addExtraUserTo(I, AdditionalUsers);
+    return Simplified.Expr;
+  }
   return E;
 }
 
 // Take a Value returned by simplification of Expression E/Instruction
 // I, and see if it resulted in a simpler expression. If so, return
 // that expression.
-const Expression *NewGVN::checkSimplificationResults(Expression *E,
-                                                     Instruction *I,
-                                                     Value *V) const {
+NewGVN::ExprResult NewGVN::checkExprResults(Expression *E, Instruction *I,
   if (!V)
-    return nullptr;
+    return ExprResult::none();
+
   if (auto *C = dyn_cast<Constant>(V)) {
     if (I)
       LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
                         << " constant " << *C << "\n");
     NumGVNOpsSimplified++;
     assert(isa<BasicExpression>(E) &&
            "We should always have had a basic expression here");
     deleteExpression(E);
-    return createConstantExpression(C);
+    return ExprResult::some(createConstantExpression(C));
   } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
     if (I)
       LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
                         << " variable " << *V << "\n");
     deleteExpression(E);
-    return createVariableExpression(V);
+    return ExprResult::some(createVariableExpression(V));
   }
 
   CongruenceClass *CC = ValueToClass.lookup(V);
   if (CC) {
     if (CC->getLeader() && CC->getLeader() != I) {
-      // If we simplified to something else, we need to communicate
-      // that we're users of the value we simplified to.
-      if (I != V) {
-        // Don't add temporary instructions to the user lists.
-        if (!AllTempInstructions.count(I))
-          addAdditionalUsers(V, I);
-      }
-      return createVariableOrConstant(CC->getLeader());
+      return ExprResult::some(createVariableOrConstant(CC->getLeader()), V);
     }
     if (CC->getDefiningExpr()) {
-      // If we simplified to something else, we need to communicate
-      // that we're users of the value we simplified to.
-      if (I != V) {
-        // Don't add temporary instructions to the user lists.
-        if (!AllTempInstructions.count(I))
-          addAdditionalUsers(V, I);
-      }
-
       if (I)
         LLVM_DEBUG(dbgs() << "Simplified " << *I << " to "
                           << " expression " << *CC->getDefiningExpr() << "\n");
       NumGVNOpsSimplified++;
       deleteExpression(E);
-      return CC->getDefiningExpr();
+      return ExprResult::some(CC->getDefiningExpr(), V);
     }
   }
 
-  return nullptr;
+  return ExprResult::none();
 }
 
 // Create a value expression from the instruction I, replacing operands with
 // their leaders.
 
-const Expression *NewGVN::createExpression(Instruction *I) const {
+NewGVN::ExprResult NewGVN::createExpression(Instruction *I) 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
if (auto *CI = dyn_cast<CmpInst>(I)) {
     E->setOpcode((CI->getOpcode() << 8) | Predicate);
     // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands
     assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
            "Wrong types on cmp instruction");
     assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
             E->getOperand(1)->getType() == I->getOperand(1)->getType()));
     Value *V =
         SimplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), SQ);
-    if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
-      return SimplifiedE;
+    if (auto Simplified = checkExprResults(E, I, V))
+      return Simplified;
   } else if (isa<SelectInst>(I)) {
     if (isa<Constant>(E->getOperand(0)) ||
         E->getOperand(1) == E->getOperand(2)) {
       assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
              E->getOperand(2)->getType() == I->getOperand(2)->getType());
       Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1),
                                     E->getOperand(2), SQ);
-      if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
-        return SimplifiedE;
+      if (auto Simplified = checkExprResults(E, I, V))
+        return Simplified;
     }
   } else if (I->isBinaryOp()) {
     Value *V =
         SimplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), SQ);
-    if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
-      return SimplifiedE;
+    if (auto Simplified = checkExprResults(E, I, V))
+      return Simplified;
   } else if (auto *CI = dyn_cast<CastInst>(I)) {
     Value *V =
         SimplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), SQ);
-    if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
-      return SimplifiedE;
+    if (auto Simplified = checkExprResults(E, I, V))
+      return Simplified;
   } else if (isa<GetElementPtrInst>(I)) {
     Value *V = SimplifyGEPInst(
         E->getType(), ArrayRef<Value *>(E->op_begin(), E->op_end()), SQ);
-    if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
-      return SimplifiedE;
+    if (auto Simplified = checkExprResults(E, I, V))
+      return Simplified;
   } else if (AllConstant) {
     // We don't bother trying to simplify unless all of the operands
     // were constant.
     // TODO: There are a lot of Simplify*'s we could call here, if we
     // wanted to.  The original motivating case for this code was a
     // zext i1 false to i8, which we don't have an interface to
     // simplify (IE there is no SimplifyZExt).
 
     SmallVector<Constant *, 8> C;
     for (Value *Arg : E->operands())
       C.emplace_back(cast<Constant>(Arg));
 
     if (Value *V = ConstantFoldInstOperands(I, C, DL, TLI))
-      if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
-        return SimplifiedE;
+      if (auto Simplified = checkExprResults(E, I, V))
+        return Simplified;
   }
-  return E;
+  return ExprResult::some(E);
 }
 
 const AggregateValueExpression *
 NewGVN::createAggregateValueExpression(Instruction *I) const {
   if (auto *II = dyn_cast<InsertValueInst>(I)) {
     auto *E = new (ExpressionAllocator)
         AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
     setBasicExpressionInfo(I, E);
if (WO && EI->getNumIndices() == 1 && *EI->idx_begin() == 0)
       // expression.
       return createBinaryExpression(WO->getBinaryOp(), EI->getType(),
                                     WO->getLHS(), WO->getRHS(), I);
   }
 
   return createAggregateValueExpression(I);
 }
 
-const Expression *NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
+NewGVN::ExprResult NewGVN::performSymbolicCmpEvaluation(Instruction *I) const {
   assert(isa<CmpInst>(I) && "Expected a cmp instruction.");
 
   auto *CI = cast<CmpInst>(I);
   // See if our operands are equal to those of a previous predicate, and if so,
   // if it implies true or false.
   auto Op0 = lookupOperandLeader(CI->getOperand(0));
   auto Op1 = lookupOperandLeader(CI->getOperand(1));
   auto OurPredicate = CI->getPredicate();
   if (shouldSwapOperands(Op0, Op1)) {
     std::swap(Op0, Op1);
     OurPredicate = CI->getSwappedPredicate();
   }
 
   // Avoid processing the same info twice.
   const PredicateBase *LastPredInfo = nullptr;
   // See if we know something about the comparison itself, like it is the target
   // of an assume.
   auto *CmpPI = PredInfo->getPredicateInfoFor(I);
   if (dyn_cast_or_null<PredicateAssume>(CmpPI))
-    return createConstantExpression(ConstantInt::getTrue(CI->getType()));
+    return ExprResult::some(
+        createConstantExpression(ConstantInt::getTrue(CI->getType())));
 
   if (Op0 == Op1) {
     // This condition does not depend on predicates, no need to add users
     if (CI->isTrueWhenEqual())
-      return createConstantExpression(ConstantInt::getTrue(CI->getType()));
+      return ExprResult::some(
+          createConstantExpression(ConstantInt::getTrue(CI->getType())));
     else if (CI->isFalseWhenEqual())
-      return createConstantExpression(ConstantInt::getFalse(CI->getType()));
+      return ExprResult::some(
+          createConstantExpression(ConstantInt::getFalse(CI->getType())));
   }
 
   // NOTE: Because we are comparing both operands here and below, and using
   // previous comparisons, we rely on fact that predicateinfo knows to mark
   // comparisons that use renamed operands as users of the earlier comparisons.
   // It is *not* enough to just mark predicateinfo renamed operands as users of
   // the earlier comparisons, because the *other* operand may have changed in a
   // previous iteration.
if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
       if (shouldSwapOperands(BranchOp0, BranchOp1)) {
         std::swap(BranchOp0, BranchOp1);
         BranchPredicate = BranchCond->getSwappedPredicate();
       }
       if (BranchOp0 == Op0 && BranchOp1 == Op1) {
         if (PBranch->TrueEdge) {
           // If we know the previous predicate is true and we are in the true
           // edge then we may be implied true or false.
           if (CmpInst::isImpliedTrueByMatchingCmp(BranchPredicate,
                                                   OurPredicate)) {
             addPredicateUsers(PI, I);
-            return createConstantExpression(
-                ConstantInt::getTrue(CI->getType()));
+            return ExprResult::some(
+                createConstantExpression(ConstantInt::getTrue(CI->getType())));
           }
 
           if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate,
                                                    OurPredicate)) {
             addPredicateUsers(PI, I);
-            return createConstantExpression(
-                ConstantInt::getFalse(CI->getType()));
+            return ExprResult::some(
+                createConstantExpression(ConstantInt::getFalse(CI->getType())));
           }
         } else {
           // Just handle the ne and eq cases, where if we have the same
           // operands, we may know something.
           if (BranchPredicate == OurPredicate) {
             addPredicateUsers(PI, I);
             // Same predicate, same ops,we know it was false, so this is false.
-            return createConstantExpression(
-                ConstantInt::getFalse(CI->getType()));
+            return ExprResult::some(
+                createConstantExpression(ConstantInt::getFalse(CI->getType())));
           } else if (BranchPredicate ==
                      CmpInst::getInversePredicate(OurPredicate)) {
             addPredicateUsers(PI, I);
             // Inverse predicate, we know the other was false, so this is true.
-            return createConstantExpression(
-                ConstantInt::getTrue(CI->getType()));
+            return ExprResult::some(
+                createConstantExpression(ConstantInt::getTrue(CI->getType())));
           }
         }
       }
     }
   }
   // Create expression will take care of simplifyCmpInst
   return createExpression(I);
 }
 
 // Substitute and symbolize the value before value numbering.
-const Expression *
+NewGVN::ExprResult
 NewGVN::performSymbolicEvaluation(Value *V,
                                   SmallPtrSetImpl<Value *> &Visited) const {
+
   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 {
     // TODO: memory intrinsics.
     // TODO: Some day, we should do the forward propagation and reassociation
else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
     case Instruction::Store:
       E = performSymbolicStoreEvaluation(I);
       break;
     case Instruction::Load:
       E = performSymbolicLoadEvaluation(I);
       break;
     case Instruction::BitCast:
     case Instruction::AddrSpaceCast:
-      E = createExpression(I);
+      return createExpression(I);
       break;
     case Instruction::ICmp:
     case Instruction::FCmp:
-      E = performSymbolicCmpEvaluation(I);
+      return performSymbolicCmpEvaluation(I);
       break;
     case Instruction::FNeg:
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
     case Instruction::FSub:
     case Instruction::Mul:
     case Instruction::FMul:
else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
     case Instruction::FPTrunc:
     case Instruction::FPExt:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::Select:
     case Instruction::ExtractElement:
     case Instruction::InsertElement:
     case Instruction::GetElementPtr:
-      E = createExpression(I);
+      return createExpression(I);
       break;
     case Instruction::ShuffleVector:
       // FIXME: Add support for shufflevector to createExpression.
-      return nullptr;
+      return ExprResult::none();
     default:
-      return nullptr;
+      return ExprResult::none();
     }
   }
-  return E;
+  return ExprResult::some(E);
 }
 
 // Look up a container of values/instructions in a map, and touch all the
 // instructions in the container.  Then erase value from the map.
 template <typename Map, typename KeyType>
 void NewGVN::touchAndErase(Map &M, const KeyType &Key) {
   const auto Result = M.find_as(Key);
   if (Result != M.end()) {

 void NewGVN::processOutgoingEdges(Instruction *TI, BasicBlock *B) {
   // Evaluate reachability of terminator instruction.
   Value *Cond;
   BasicBlock *TrueSucc, *FalseSucc;
   if (match(TI, m_Br(m_Value(Cond), TrueSucc, FalseSucc))) {
     Value *CondEvaluated = findConditionEquivalence(Cond);
     if (!CondEvaluated) {
       if (auto *I = dyn_cast<Instruction>(Cond)) {
-        const Expression *E = createExpression(I);
-        if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
+        auto Res = createExpression(I);
+        if (const auto *CE = dyn_cast<ConstantExpression>(Res.Expr)) {
           CondEvaluated = CE->getConstantValue();
+          Res.addExtraUserTo(I, AdditionalUsers);
+        } else {
+          // Did not use simplification result, no need to add the extra
+          // dependency.
+          Res.ExtraDep = nullptr;
         }
       } else if (isa<ConstantInt>(Cond)) {
         CondEvaluated = Cond;
       }
     }
     ConstantInt *CI;
     if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
       if (CI->isOne()) {
Value *NewGVN::findLeaderForInst(Instruction *TransInst,
   // Make sure it's marked as a temporary instruction.
   AllTempInstructions.insert(TransInst);
   // 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({TransInst, PredBB});
   InstrDFS.insert({TransInst, IDFSNum});
 
-  const Expression *E = performSymbolicEvaluation(TransInst, Visited);
+  auto Res = performSymbolicEvaluation(TransInst, Visited);
+  const Expression *E = Res.Expr;
+  Res.addExtraUserTo(OrigInst, AdditionalUsers);
   InstrDFS.erase(TransInst);
   AllTempInstructions.erase(TransInst);
   TempToBlock.erase(TransInst);
   if (MemAccess)
     TempToMemory.erase(TransInst);
   if (!E)
     return nullptr;
   auto *FoundVal = findPHIOfOpsLeader(E, OrigInst, PredBB);

 // Value number a single instruction, symbolically evaluating, performing
 // congruence finding, and updating mappings.
 void NewGVN::valueNumberInstruction(Instruction *I) {
   LLVM_DEBUG(dbgs() << "Processing instruction " << *I << "\n");
   if (!I->isTerminator()) {
     const Expression *Symbolized = nullptr;
     SmallPtrSet<Value *, 2> Visited;
     if (DebugCounter::shouldExecute(VNCounter)) {
-      Symbolized = performSymbolicEvaluation(I, Visited);
+      auto Res = performSymbolicEvaluation(I, Visited);
+      Symbolized = Res.Expr;
+      Res.addExtraUserTo(I, AdditionalUsers);
+
       // Make a phi of ops if necessary
       if (Symbolized && !isa<ConstantExpression>(Symbolized) &&
           !isa<VariableExpression>(Symbolized) && PHINodeUses.count(I)) {
         auto *PHIE = makePossiblePHIOfOps(I, Visited);
         // If we created a phi of ops, use it.
         // If we couldn't create one, make sure we don't leave one lying around
         if (PHIE) {
           Symbolized = PHIE;

llvm/test/Transforms/NewGVN/phi-of-ops-simplification-dependencies.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -newgvn -S %s | FileCheck %s
+
+declare void @use.i16(i16*)
+declare void @use.i32(i32)
+
+; Test cases from PR35074, where the simplification dependencies need to be
+; tracked for phi-of-ops root instructions.
+
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[Y_0:%.*]], [[FOR_INC6:%.*]] ]
+; CHECK-NEXT:    [[Y_0]] = phi i32 [ 1, [[ENTRY]] ], [ [[INC7:%.*]], [[FOR_INC6]] ]
+; CHECK-NEXT:    br i1 undef, label [[FOR_INC6]], label [[FOR_BODY_LR_PH:%.*]]
+; CHECK:       for.body.lr.ph:
+; CHECK-NEXT:    br label [[FOR_BODY4:%.*]]
+; CHECK:       for.body4:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[PHIOFOPS]], [[Y_0]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_END:%.*]], label [[FOR_BODY4_1:%.*]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+; CHECK:       for.inc6:
+; CHECK-NEXT:    [[INC7]] = add nuw nsw i32 [[Y_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.body4.1:
+; CHECK-NEXT:    [[INC_1:%.*]] = add nuw nsw i32 [[Y_0]], 1
+; CHECK-NEXT:    tail call void @use.i32(i32 [[INC_1]])
+; CHECK-NEXT:    br label [[FOR_END]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc6, %entry
+  %y.0 = phi i32 [ 1, %entry ], [ %inc7, %for.inc6 ]
+  br i1 undef, label %for.inc6, label %for.body.lr.ph
+
+for.body.lr.ph:                                   ; preds = %for.cond
+  %sub = add nsw i32 %y.0, -1
+  br label %for.body4
+
+for.body4:                                        ; preds = %for.body.lr.ph
+  %cmp = icmp ugt i32 %sub, %y.0
+  br i1 %cmp, label %for.end, label %for.body4.1
+
+for.end:                                          ; preds = %for.body4.1, %for.body4
+  ret void
+
+for.inc6:                                         ; preds = %for.cond
+  %inc7 = add nuw nsw i32 %y.0, 1
+  br label %for.cond
+
+for.body4.1:                                      ; preds = %for.body4
+  %inc.1 = add nuw nsw i32 %y.0, 1
+  tail call void @use.i32(i32 %inc.1)
+  br label %for.end
+}
+
+define void @test2(i1 %c, i16* %ptr, i64 %N) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[HEADER:%.*]]
+; CHECK:       header:
+; CHECK-NEXT:    [[PHIOFOPS:%.*]] = phi i64 [ -1, [[ENTRY:%.*]] ], [ [[IV:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[IV]] = phi i64 [ [[IV_NEXT:%.*]], [[LATCH]] ], [ 0, [[ENTRY]] ]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i64 [[IV]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[LATCH]], label [[LOR_RHS:%.*]]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    [[IV_ADD_1:%.*]] = add i64 [[IV]], 1
+; CHECK-NEXT:    [[IDX_1:%.*]] = getelementptr inbounds i16, i16* [[PTR:%.*]], i64 [[IV_ADD_1]]
+; CHECK-NEXT:    call void @use.i16(i16* [[IDX_1]])
+; CHECK-NEXT:    ret void
+; CHECK:       if.else:
+; CHECK-NEXT:    [[IDX_2:%.*]] = getelementptr inbounds i16, i16* [[PTR]], i64 [[PHIOFOPS]]
+; CHECK-NEXT:    call void @use.i16(i16* [[IDX_2]])
+; CHECK-NEXT:    br label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[IV_NEXT]] = add i64 [[IV]], 1
+; CHECK-NEXT:    [[EC:%.*]] = icmp ugt i64 [[IV_NEXT]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[EC]], label [[HEADER]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %header
+
+header:                                         ; preds = %for.inc, %entry
+  %iv = phi i64 [ %iv.next, %latch ], [ 0, %entry ]
+  br i1 %c, label %if.then, label %if.else
+
+if.then:
+  %cmp1 = icmp eq i64 %iv, 0
+  br i1 %cmp1, label %latch, label %lor.rhs
+
+lor.rhs:                                          ; preds = %if.then
+  %iv.add.1 = add i64 %iv, 1
+  %idx.1 = getelementptr inbounds i16, i16* %ptr, i64 %iv.add.1
+  call void @use.i16(i16* %idx.1)
+  ret void
+
+if.else:
+  %iv.sub.1 = add i64 %iv, -1
+  %idx.2 = getelementptr inbounds i16, i16* %ptr, i64 %iv.sub.1
+  call void @use.i16(i16* %idx.2)
+  br label %latch
+
+latch:
+  %iv.next = add i64 %iv, 1
+  %ec = icmp ugt i64 %iv.next, %N
+  br i1 %ec, label %header, label %exit
+
+exit:
+  ret void
+}