[NewGVN] Use ExprResult to add extra predicate users.

[fhahn]

Summary

This patch updates performSymbolicPredicateInfoEvaluation to manage
registering additional dependencies using ExprResult. Similar to D99987,
this fixes an issues where we failed to track the correct dependency for
a phi-of-ops value, which is marked as temporary.

Fixes PR49873.

[fhahn]

rebased after landing 2b15262f89bc

[asbirlea]

Thanks, looks good.
Could you add the const to resolve the clang-tidy warning?

[ruiling]

Thanks for the fixing! The rebased version sounds good to go with fixing the minor clang-tidy warning.

llvm/lib/Transforms/Scalar/NewGVN.cpp

public:
 
   bool runGVN();
 
 private:
   /// Helper struct return a Expression with an optional extra dependency.
   struct ExprResult {
     const Expression *Expr;
     Value *ExtraDep;
+    const PredicateBase *PredDep;
 
-    ExprResult(const Expression *Expr, Value *ExtraDep = nullptr)
-        : Expr(Expr), ExtraDep(ExtraDep) {}
+    ExprResult(const Expression *Expr, Value *ExtraDep = nullptr,
+               const PredicateBase *PredDep = nullptr)
+        : Expr(Expr), ExtraDep(ExtraDep), PredDep(PredDep) {}
     ExprResult(const ExprResult &) = delete;
     ExprResult(ExprResult &&Other)
         : Expr(Other.Expr), ExtraDep(Other.ExtraDep) {
       Other.Expr = nullptr;
       Other.ExtraDep = nullptr;
     }
     ExprResult &operator=(const ExprResult &Other) = delete;
     ExprResult &operator=(ExprResult &&Other) = delete;
 
     ~ExprResult() { assert(!ExtraDep && "unhandled ExtraDep"); }
 
     operator bool() const { return Expr; }
 
-    static ExprResult none() { return {nullptr, nullptr}; }
+    static ExprResult none() { return {nullptr, nullptr, nullptr}; }
     static ExprResult some(const Expression *Expr, Value *ExtraDep = nullptr) {
-      return {Expr, ExtraDep};
+      return {Expr, ExtraDep, nullptr};
+    }
+    static ExprResult some(const Expression *Expr,
+                           const PredicateBase *PredDep) {
+      return {Expr, nullptr, PredDep};
+    }
+    static ExprResult some(const Expression *Expr, Value *ExtraDep,
+                           const PredicateBase *PredDep) {
+      return {Expr, ExtraDep, PredDep};
     }
   };
 
   // Expression handling.
   ExprResult createExpression(Instruction *) const;
   const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
                                            Instruction *) const;
 
private:
   ExprResult checkExprResults(Expression *, Instruction *, Value *) const;
   ExprResult performSymbolicEvaluation(Value *,
                                        SmallPtrSetImpl<Value *> &) const;
   const Expression *performSymbolicLoadCoercion(Type *, Value *, LoadInst *,
                                                 Instruction *,
                                                 MemoryAccess *) const;
   const Expression *performSymbolicLoadEvaluation(Instruction *) const;
   const Expression *performSymbolicStoreEvaluation(Instruction *) const;
-  const Expression *performSymbolicCallEvaluation(Instruction *) const;
+  ExprResult performSymbolicCallEvaluation(Instruction *) const;
   void sortPHIOps(MutableArrayRef<ValPair> Ops) const;
   const Expression *performSymbolicPHIEvaluation(ArrayRef<ValPair>,
                                                  Instruction *I,
                                                  BasicBlock *PHIBlock) const;
   const Expression *performSymbolicAggrValueEvaluation(Instruction *) const;
   ExprResult performSymbolicCmpEvaluation(Instruction *) const;
-  const Expression *performSymbolicPredicateInfoEvaluation(Instruction *) const;
+  ExprResult 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 *,
                                      CongruenceClass *, CongruenceClass *);
private:
   void touchAndErase(Map &, const KeyType &);
   void markUsersTouched(Value *);
   void markMemoryUsersTouched(const MemoryAccess *);
   void markMemoryDefTouched(const MemoryAccess *);
   void markPredicateUsersTouched(Instruction *);
   void markValueLeaderChangeTouched(CongruenceClass *CC);
   void markMemoryLeaderChangeTouched(CongruenceClass *CC);
   void markPhiOfOpsChanged(const Expression *E);
-  void addPredicateUsers(const PredicateBase *, Instruction *) const;
   void addMemoryUsers(const MemoryAccess *To, MemoryAccess *U) const;
   void addAdditionalUsers(Value *To, Value *User) const;
-  void addAdditionalUsers(ExprResult &Res, Value *User) const;
+  void addAdditionalUsers(ExprResult &Res, Instruction *User) const;
 
   // Main loop of value numbering
   void iterateTouchedInstructions();
 
   // Utilities.
   void cleanupTables();
   std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
   void updateProcessedCount(const Value *V);
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 *
+NewGVN::ExprResult
 NewGVN::performSymbolicPredicateInfoEvaluation(Instruction *I) const {
   auto *PI = PredInfo->getPredicateInfoFor(I);
   if (!PI)
-    return nullptr;
+    return ExprResult::none();
 
   LLVM_DEBUG(dbgs() << "Found predicate info from instruction !\n");
 
   const Optional<PredicateConstraint> &Constraint = PI->getConstraint();
   if (!Constraint)
-    return nullptr;
+    return ExprResult::none();
 
   CmpInst::Predicate Predicate = Constraint->Predicate;
   Value *CmpOp0 = I->getOperand(0);
   Value *CmpOp1 = Constraint->OtherOp;
 
   Value *FirstOp = lookupOperandLeader(CmpOp0);
   Value *SecondOp = lookupOperandLeader(CmpOp1);
   Value *AdditionallyUsedValue = CmpOp0;
 
   // Sort the ops.
   if (shouldSwapOperands(FirstOp, SecondOp)) {
     std::swap(FirstOp, SecondOp);
     Predicate = CmpInst::getSwappedPredicate(Predicate);
     AdditionallyUsedValue = CmpOp1;
   }
 
-  if (Predicate == CmpInst::ICMP_EQ) {
-    addPredicateUsers(PI, I);
-    addAdditionalUsers(AdditionallyUsedValue, I);
-    return createVariableOrConstant(FirstOp);
-  }
+  if (Predicate == CmpInst::ICMP_EQ)
+    return ExprResult::some(createVariableOrConstant(FirstOp),
+                            AdditionallyUsedValue, PI);
 
   // Handle the special case of floating point.
   if (Predicate == CmpInst::FCMP_OEQ && isa<ConstantFP>(FirstOp) &&
-      !cast<ConstantFP>(FirstOp)->isZero()) {
-    addPredicateUsers(PI, I);
-    addAdditionalUsers(AdditionallyUsedValue, I);
-    return createConstantExpression(cast<Constant>(FirstOp));
-  }
+      !cast<ConstantFP>(FirstOp)->isZero())
+    return ExprResult::some(createConstantExpression(cast<Constant>(FirstOp)),
+                            AdditionallyUsedValue, PI);
 
-  return nullptr;
+  return ExprResult::none();
 }
 
 // Evaluate read only and pure calls, and create an expression result.
-const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
+NewGVN::ExprResult NewGVN::performSymbolicCallEvaluation(Instruction *I) const {
   auto *CI = cast<CallInst>(I);
   if (auto *II = dyn_cast<IntrinsicInst>(I)) {
     // Intrinsics with the returned attribute are copies of arguments.
     if (auto *ReturnedValue = II->getReturnedArgOperand()) {
       if (II->getIntrinsicID() == Intrinsic::ssa_copy)
-        if (const auto *Result = performSymbolicPredicateInfoEvaluation(I))
-          return Result;
-      return createVariableOrConstant(ReturnedValue);
+        if (auto Res = performSymbolicPredicateInfoEvaluation(I))
+          return Res;
+      return ExprResult::some(createVariableOrConstant(ReturnedValue));
     }
   }
   if (AA->doesNotAccessMemory(CI)) {
-    return createCallExpression(CI, TOPClass->getMemoryLeader());
+    return ExprResult::some(
+        createCallExpression(CI, TOPClass->getMemoryLeader()));
   } else if (AA->onlyReadsMemory(CI)) {
     if (auto *MA = MSSA->getMemoryAccess(CI)) {
       auto *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(MA);
-      return createCallExpression(CI, DefiningAccess);
+      return ExprResult::some(createCallExpression(CI, DefiningAccess));
     } else // MSSA determined that CI does not access memory.
-      return createCallExpression(CI, TOPClass->getMemoryLeader());
+      return ExprResult::some(
+          createCallExpression(CI, TOPClass->getMemoryLeader()));
   }
-  return nullptr;
+  return ExprResult::none();
 }
 
 // Retrieve the memory class for a given MemoryAccess.
 CongruenceClass *NewGVN::getMemoryClass(const MemoryAccess *MA) const {
   auto *Result = MemoryAccessToClass.lookup(MA);
   assert(Result && "Should have found memory class");
   return Result;
 }
if (const auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI)) {
         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 ExprResult::some(
-                createConstantExpression(ConstantInt::getTrue(CI->getType())));
+                createConstantExpression(ConstantInt::getTrue(CI->getType())),
+                PI);
           }
 
           if (CmpInst::isImpliedFalseByMatchingCmp(BranchPredicate,
                                                    OurPredicate)) {
-            addPredicateUsers(PI, I);
             return ExprResult::some(
-                createConstantExpression(ConstantInt::getFalse(CI->getType())));
+                createConstantExpression(ConstantInt::getFalse(CI->getType())),
+                PI);
           }
         } 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 ExprResult::some(
-                createConstantExpression(ConstantInt::getFalse(CI->getType())));
+                createConstantExpression(ConstantInt::getFalse(CI->getType())),
+                PI);
           } else if (BranchPredicate ==
                      CmpInst::getInversePredicate(OurPredicate)) {
-            addPredicateUsers(PI, I);
             // Inverse predicate, we know the other was false, so this is true.
             return ExprResult::some(
-                createConstantExpression(ConstantInt::getTrue(CI->getType())));
+                createConstantExpression(ConstantInt::getTrue(CI->getType())),
+                PI);
           }
         }
       }
     }
   }
   // Create expression will take care of simplifyCmpInst
   return createExpression(I);
 }
case Instruction::PHI: {
       auto *PN = cast<PHINode>(I);
       for (unsigned i = 0; i < PN->getNumOperands(); ++i)
         Ops.push_back({PN->getIncomingValue(i), PN->getIncomingBlock(i)});
       // Sort to ensure the invariant createPHIExpression requires is met.
       sortPHIOps(Ops);
       E = performSymbolicPHIEvaluation(Ops, I, getBlockForValue(I));
     } break;
     case Instruction::Call:
-      E = performSymbolicCallEvaluation(I);
+      return performSymbolicCallEvaluation(I);
       break;
     case Instruction::Store:
       E = performSymbolicStoreEvaluation(I);
       break;
     case Instruction::Load:
       E = performSymbolicLoadEvaluation(I);
       break;
     case Instruction::BitCast:

 }
 
 void NewGVN::addAdditionalUsers(Value *To, Value *User) const {
   assert(User && To != User);
   if (isa<Instruction>(To))
     AdditionalUsers[To].insert(User);
 }
 
-void NewGVN::addAdditionalUsers(ExprResult &Res, Value *User) const {
+void NewGVN::addAdditionalUsers(ExprResult &Res, Instruction *User) const {
   if (Res.ExtraDep && Res.ExtraDep != User)
     addAdditionalUsers(Res.ExtraDep, User);
   Res.ExtraDep = nullptr;
+  if (Res.PredDep) {
+    if (auto *PBranch = dyn_cast<PredicateBranch>(Res.PredDep))
+      PredicateToUsers[PBranch->Condition].insert(User);
+    else if (auto *PAssume = dyn_cast<PredicateAssume>(Res.PredDep))
+      PredicateToUsers[PAssume->Condition].insert(User);
+  }
+  Res.PredDep = nullptr;
 }
 
 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::markMemoryUsersTouched(const MemoryAccess *MA) {
   if (isa<MemoryUse>(MA))
     return;
   for (auto U : MA->users())
     TouchedInstructions.set(MemoryToDFSNum(U));
   touchAndErase(MemoryToUsers, MA);
 }
 
-// Add I to the set of users of a given predicate.
-void NewGVN::addPredicateUsers(const PredicateBase *PB, Instruction *I) const {
-  // Don't add temporary instructions to the user lists.
-  if (AllTempInstructions.count(I))
-    return;
-
-  if (auto *PBranch = dyn_cast<PredicateBranch>(PB))
-    PredicateToUsers[PBranch->Condition].insert(I);
-  else if (auto *PAssume = dyn_cast<PredicateAssume>(PB))
-    PredicateToUsers[PAssume->Condition].insert(I);
-}
-
 // Touch all the predicates that depend on this instruction.
 void NewGVN::markPredicateUsersTouched(Instruction *I) {
   touchAndErase(PredicateToUsers, I);
 }
 
 // Mark users affected by a memory leader change.
 void NewGVN::markMemoryLeaderChangeTouched(CongruenceClass *CC) {
   for (auto M : CC->memory())

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

 latch:
   %iv.next = add i64 %iv, 1
   %ec = icmp ugt i64 %iv.next, %N
   br i1 %ec, label %header, label %exit
 
 exit:
   ret void
 }
+
+define void @pr49873_cmp_simplification_dependency(i32* %ptr, i1 %c.0) {
+; CHECK-LABEL: @pr49873_cmp_simplification_dependency(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_1:%.*]]
+; CHECK:       loop.1:
+; CHECK-NEXT:    br i1 [[C_0:%.*]], label [[LOOP_1_LATCH:%.*]], label [[LOOP_2:%.*]]
+; CHECK:       loop.2:
+; CHECK-NEXT:    [[I130:%.*]] = phi i32 [ [[I132:%.*]], [[LOOP_2]] ], [ 0, [[LOOP_1]] ]
+; CHECK-NEXT:    [[I132]] = add nuw i32 [[I130]], 1
+; CHECK-NEXT:    [[I133:%.*]] = load i32, i32* [[PTR:%.*]], align 4
+; CHECK-NEXT:    [[C_1:%.*]] = icmp ult i32 [[I132]], [[I133]]
+; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_2]], label [[LOOP_2_EXIT:%.*]]
+; CHECK:       loop.2.exit:
+; CHECK-NEXT:    br label [[LOOP_1_LATCH]]
+; CHECK:       loop.1.latch:
+; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[I133]], [[LOOP_2_EXIT]] ]
+; CHECK-NEXT:    [[C_2:%.*]] = icmp ult i32 1, [[DOTLCSSA]]
+; CHECK-NEXT:    br i1 [[C_2]], label [[LOOP_1]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop.1
+
+loop.1:
+  %i65 = add nuw i32 0, 1
+  br i1 %c.0, label %loop.1.latch, label %loop.2
+
+loop.2:
+  %i130 = phi i32 [ %i132, %loop.2 ], [ 0, %loop.1 ]
+  %i132 = add nuw i32 %i130, 1
+  %i133 = load i32, i32* %ptr, align 4
+  %c.1 = icmp ult i32 %i132, %i133
+  br i1 %c.1, label %loop.2, label %loop.2.exit
+
+loop.2.exit:
+  br label %loop.1.latch
+
+loop.1.latch:                                      ; preds = %loop.2.exit, %loop.1
+  %.lcssa = phi i32 [ 0, %loop.1 ], [ %i133, %loop.2.exit ]
+  %c.2 = icmp ult i32 %i65, %.lcssa
+  br i1 %c.2, label %loop.1, label %exit
+
+exit:
+  ret void
+}