[Attributor] Make value simplify stronger

[jdoerfert]

Summary

NOTE: This patch will be split in pieces.
NOTE: This is still under testing on the test-suite and tests need to be

     updated after intermediate changes.

This patch makes value simplify stronger and consolidates features 
present in AAReturnedValuesImpl before. The new algorithm does not try
to find a single value which is "simplified" but instead collects all
potential values.

In addition, this patch adds simple constant folding and instruction
folding logic.

The reason for this patch was the Adobe-C++/loop_unroll.cpp benchmark in
the test suite. The compile time with the old implementation was bad. A
test case in the spirit of loop_unroll.cpp was added here.

TODO: Other AAs and Attributor routines could use AAValueSimplify when
      they look at values. Similar to the select folding now in
      genericValueTraversal.

Use update_test_checks for value_simplify.ll with the following patches
applied and function signature printing enabled: D68851, D68850, D68819

[jdoerfert]

The first version was broken, really broken. This actually passed all the test
suite test (and SPEC2006) when I did the eval for the LLVM-DEV. However, it
needs to be rebased properly and split.

[merge_guards_bot]

Build result: FAILURE - Could not check out parent git hash "abffc7ed485859ac07ff447576b6e795f43a8e08". It was not found in the repository. Did you configure the "Parent Revision" in Phabricator properly? Trying to apply the patch to the master branch instead...

ERROR: arc patch failed with error code 1. Check build log for details.
Log files: console-log.txt, CMakeCache.txt

[jdoerfert]

Interesting ideas will be picked up, this code is dead though.

llvm/include/llvm/Transforms/IPO/Attributor.h

 /// An abstract interface for value simplify abstract attribute.
 struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute>,
                          public IRPosition {
   AAValueSimplify(const IRPosition &IRP) : IRPosition(IRP) {}
 
   /// Return an IR position, see struct IRPosition.
   const IRPosition &getIRPosition() const { return *this; }
 
+  /// Return the values assumed to be potentially becomming this one.
+  virtual const SmallPtrSetImpl<Value *> &
+  getAssumedPotentialValues() const = 0;
+
   /// Return an assumed simplified value if a single candidate is found. If
   /// there cannot be one, return original value. If it is not clear yet, return
   /// the Optional::NoneType.
-  virtual Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const = 0;
+  Optional<Value *> getAssumedSimplifiedValue() const {
+    const auto &APV = getAssumedPotentialValues();
+    if (APV.empty())
+      return None;
+    if (APV.size() == 1)
+      return *APV.begin();
+    return nullptr;
+  }
 
   /// Create an abstract attribute view for the position \p IRP.
   static AAValueSimplify &createForPosition(const IRPosition &IRP,
                                             Attributor &A);
 
   /// Unique ID (due to the unique address)
   static const char ID;
+
+  /// Return a value (which is potentially created!) that can replace
+  /// \p OldValue at the location \p IP, or nullptr if no such value is known.
+  virtual Value *getReplacementForAt(Value &OldValue,
+                                     Instruction *IP) const = 0;
 };
 
 struct AAHeapToStack : public StateWrapper<BooleanState, AbstractAttribute>,
                        public IRPosition {
   AAHeapToStack(const IRPosition &IRP) : IRPosition(IRP) {}
 
   /// Returns true if HeapToStack conversion is assumed to be possible.
   bool isAssumedHeapToStack() const { return getAssumed(); }

llvm/lib/Transforms/IPO/Attributor.cpp

 // that file for more information.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/Attributor.h"
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetOperations.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GlobalsModRef.h"
do {
     }
     if (NewV && NewV != V) {
       Worklist.push_back(NewV);
       continue;
     }
 
     // Look through select instructions, visit both potential values.
     if (auto *SI = dyn_cast<SelectInst>(V)) {
+      const auto &CondSimplifyAA = A.getAAFor<AAValueSimplify>(
+          QueryingAA, IRPosition::value(*SI->getCondition()),
+          /* TrackDependence */ false);
+      Optional<Value *> SimpleCond = CondSimplifyAA.getAssumedSimplifiedValue();
+      if (!SimpleCond.hasValue())
+        continue;
+      if (!SimpleCond.getValue() || !isa<Constant>(SimpleCond.getValue())) {
         Worklist.push_back(SI->getTrueValue());
         Worklist.push_back(SI->getFalseValue());
+      } else {
+        Worklist.push_back(cast<Constant>(SimpleCond.getValue())->isZeroValue()
+                               ? SI->getFalseValue()
+                               : SI->getTrueValue());
+      }
       continue;
     }
 
     // Look through phi nodes, visit all live operands.
     if (auto *PHI = dyn_cast<PHINode>(V)) {
       assert(LivenessAA &&
              "Expected liveness in the presence of instructions!");
       for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) {
ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
 
   if (!UniqueRV.hasValue() || !UniqueRV.getValue())
     return Changed;
 
   // Bookkeeping.
   STATS_DECLTRACK(UniqueReturnValue, FunctionReturn,
                   "Number of function with unique return");
 
-  // Callback to replace the uses of CB with the constant C.
-  auto ReplaceCallSiteUsersWith = [](CallBase &CB, Constant &C) {
-    if (CB.getNumUses() == 0 || CB.isMustTailCall())
-      return ChangeStatus::UNCHANGED;
-    replaceAllUsesWith(CB, C);
-    return ChangeStatus::CHANGED;
-  };
-
   // If the assumed unique return value is an argument, annotate it.
   if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
     // TODO: This should be handled differently!
     this->AnchorVal = UniqueRVArg;
     this->KindOrArgNo = UniqueRVArg->getArgNo();
     Changed = IRAttribute::manifest(A);
-  } else if (auto *RVC = dyn_cast<Constant>(UniqueRV.getValue())) {
-    // We can replace the returned value with the unique returned constant.
-    Value &AnchorValue = getAnchorValue();
-    if (Function *F = dyn_cast<Function>(&AnchorValue)) {
-      for (const Use &U : F->uses())
-        if (CallBase *CB = dyn_cast<CallBase>(U.getUser()))
-          if (CB->isCallee(&U)) {
-            Constant *RVCCast =
-                CB->getType() == RVC->getType()
-                    ? RVC
-                    : ConstantExpr::getTruncOrBitCast(RVC, CB->getType());
-            Changed = ReplaceCallSiteUsersWith(*CB, *RVCCast) | Changed;
-          }
-    } else {
-      assert(isa<CallBase>(AnchorValue) &&
-             "Expcected a function or call base anchor!");
-      Constant *RVCCast =
-          AnchorValue.getType() == RVC->getType()
-              ? RVC
-              : ConstantExpr::getTruncOrBitCast(RVC, AnchorValue.getType());
-      Changed = ReplaceCallSiteUsersWith(cast<CallBase>(AnchorValue), *RVCCast);
-    }
-    if (Changed == ChangeStatus::CHANGED)
-      STATS_DECLTRACK(UniqueConstantReturnValue, FunctionReturn,
-                      "Number of function returns replaced by constant return");
   }
 
   return Changed;
 }
 
 const std::string AAReturnedValuesImpl::getAsStr() const {
   return (isAtFixpoint() ? "returns(#" : "may-return(#") +
          (isValidState() ? std::to_string(getNumReturnValues()) : "?") +
static int64_t getKnownNonNullAndDerefBytesForUse(
   }
 
   return 0;
 }
 
 struct AANonNullImpl : AANonNull {
   AANonNullImpl(const IRPosition &IRP)
       : AANonNull(IRP),
-        NullIsDefined(NullPointerIsDefined(
+        NullIsDefined(
+            getAssociatedValue().getType()->isPointerTy()
+                ? NullPointerIsDefined(
                       getAnchorScope(),
-            getAssociatedValue().getType()->getPointerAddressSpace())) {}
+                      getAssociatedValue().getType()->getPointerAddressSpace())
+                : true) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
-    if (!NullIsDefined &&
+    // TODO: This should work on non-pointer values as well.
+    if (!getAssociatedValue().getType()->isPointerTy())
+      indicatePessimisticFixpoint();
+    else if (!NullIsDefined &&
              hasAttr({Attribute::NonNull, Attribute::Dereferenceable}))
       indicateOptimisticFixpoint();
     else if (isa<ConstantPointerNull>(getAssociatedValue()))
       indicatePessimisticFixpoint();
     else
       AANonNull::initialize(A);
   }
 
   /// See AAFromMustBeExecutedContext
identifyAliveSuccessors(Attributor &A, const InvokeInst &II,
   return UsedAssumedInformation;
 }
 
 static Optional<ConstantInt *>
 getAssumedConstant(Attributor &A, const Value &V, AbstractAttribute &AA,
                    bool &UsedAssumedInformation) {
   const auto &ValueSimplifyAA =
       A.getAAFor<AAValueSimplify>(AA, IRPosition::value(V));
-  Optional<Value *> SimplifiedV = ValueSimplifyAA.getAssumedSimplifiedValue(A);
+  Optional<Value *> SimplifiedV = ValueSimplifyAA.getAssumedSimplifiedValue();
   UsedAssumedInformation |= !ValueSimplifyAA.isKnown();
   if (!SimplifiedV.hasValue())
     return llvm::None;
   if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue()))
     return llvm::None;
   return dyn_cast_or_null<ConstantInt>(SimplifiedV.getValue());
 }
 
void trackStatistics() const override {
     STATS_DECLTRACK_CSRET_ATTR(nocapture)
   }
 };
 
 /// ------------------ Value Simplify Attribute ----------------------------
 struct AAValueSimplifyImpl : AAValueSimplify {
   AAValueSimplifyImpl(const IRPosition &IRP) : AAValueSimplify(IRP) {}
 
+  void initialize(Attributor &A) override {
+    Value &V = getAssociatedValue();
+    if (isa<Constant>(V) || V.use_empty())
+      indicatePessimisticFixpoint();
+  }
+
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
-    return getAssumed() ? (getKnown() ? "simplified" : "maybe-simple")
-                        : "not-simple";
+    return getAssumed()
+               ? "simplify(" + std::to_string(PotentialValues.size()) + ")"
+               : "not-simplifiable";
   }
 
-  /// See AbstractAttribute::trackStatistics()
-  void trackStatistics() const override {}
+  /// See AAValueSimplify::getAssumedPotentialValues()
+  const SmallPtrSetImpl<Value *> &getAssumedPotentialValues() const override {
+    return PotentialValues;
+  }
 
-  /// See AAValueSimplify::getAssumedSimplifiedValue()
-  Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const override {
-    if (!getAssumed())
-      return const_cast<Value *>(&getAssociatedValue());
-    return SimplifiedAssociatedValue;
+  /// Combine the equivalent value set with the equivalent values for \p V.
+  bool recurseAndCombined(Attributor &A, Value &V,
+                          const AAValueSimplify *VAA = nullptr) {
+    if (isa<Constant>(V)) {
+      if (!isa<UndefValue>(V))
+        PotentialValues.insert(&V);
+      return true;
+    }
+    if (!VAA)
+      VAA = &A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V));
+    Optional<Value *> ASV = VAA->getAssumedSimplifiedValue();
+    if (!ASV.hasValue())
+      return true;
+    if (!ASV.getValue())
+      return false;
+    if (!isa<UndefValue>(V))
+      PotentialValues.insert(ASV.getValue());
+    return true;
   }
-  void initialize(Attributor &A) override {}
 
-  /// Helper function for querying AAValueSimplify and updating candicate.
-  /// \param QueryingValue Value trying to unify with SimplifiedValue
-  /// \param AccumulatedSimplifiedValue Current simplification result.
-  static bool checkAndUpdate(Attributor &A, const AbstractAttribute &QueryingAA,
-                             Value &QueryingValue,
-                             Optional<Value *> &AccumulatedSimplifiedValue) {
-    // FIXME: Add a typecast support.
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    Value &OldValue = getAssociatedValue();
+    // Do not change must tail calls (for now).
+    // TODO: Modify must tail call chains.
+    if (ImmutableCallSite ICS = ImmutableCallSite(OldValue.stripPointerCasts()))
+      if (ICS.isMustTailCall())
+        return ChangeStatus::UNCHANGED;
 
-    auto &ValueSimpifyAA = A.getAAFor<AAValueSimplify>(
-        QueryingAA, IRPosition::value(QueryingValue));
+    Value *NewValue = getReplacementForAt(OldValue, getCtxI());
+    if (!NewValue)
+      return ChangeStatus::UNCHANGED;
 
-    Optional<Value *> QueryingValueSimplified =
-        ValueSimpifyAA.getAssumedSimplifiedValue(A);
+    DEBUG_WITH_TYPE("attributor-value-simplify",
+                    dbgs() << "[AAValueSimplify] Replace '" << OldValue
+                           << "' with '" << *NewValue << "'\n");
+    assert(!OldValue.use_empty());
+    bool AnyChange = false;
+    for (Use &U : OldValue.uses())
+      AnyChange |= A.changeUseAfterManifest(U, *NewValue);
+    return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
+  }
 
-    if (!QueryingValueSimplified.hasValue())
-      return true;
+  ChangeStatus indicatePessimisticFixpoint() override {
+    PotentialValues.clear();
+    PotentialValues.insert(&getAssociatedValue());
+    AAValueSimplify::indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
 
-    if (!QueryingValueSimplified.getValue())
-      return false;
+  virtual Value *getReplacementForAt(Value &OldValue,
+                                     Instruction *IP) const override {
+    if (isa<Constant>(OldValue)) {
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs() << "[AAValueSimplify] No new value necessary, '"
+                             << OldValue << "' is a constant!\n");
+      return nullptr;
+    }
 
-    Value &QueryingValueSimplifiedUnwrapped =
-        *QueryingValueSimplified.getValue();
+    Type *Ty = OldValue.getType();
 
-    if (isa<UndefValue>(QueryingValueSimplifiedUnwrapped))
-      return true;
+    // Check if we assume the value is dead or if we lack an assumed simplified
+    // value.
+    Optional<Value *> SimplifiedValue = getAssumedSimplifiedValue();
+    if (!SimplifiedValue.hasValue())
+      return UndefValue::get(Ty);
+    if (!SimplifiedValue.getValue())
+      return nullptr;
 
-    if (AccumulatedSimplifiedValue.hasValue())
-      return AccumulatedSimplifiedValue == QueryingValueSimplified;
+    // Check if the assumed simplified value is usable
+    Value *NewValue = SimplifiedValue.getValue();
+    if (!canBeUsedInstead(*NewValue))
+      return nullptr;
 
-    LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << QueryingValue
-                      << " is assumed to be "
-                      << QueryingValueSimplifiedUnwrapped << "\n");
+    // Do not replace a value "with itself".
+    if (NewValue == OldValue.stripPointerCasts())
+      return nullptr;
 
-    AccumulatedSimplifiedValue = QueryingValueSimplified;
-    return true;
+    // If there is no need for a cast we are done.
+    if (NewValue->getType() == Ty)
+      return NewValue;
+
+    auto *NewC = dyn_cast<Constant>(NewValue);
+    bool IsPtr = Ty->isPointerTy() && NewValue->getType()->isPointerTy();
+    if (!IP && !NewC) {
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs() << "[AAValueSimplify] New value '" << *NewValue
+                             << "' needs cast but no position provided.\n");
+      return nullptr;
     }
 
-  /// See AbstractAttribute::manifest(...).
-  ChangeStatus manifest(Attributor &A) override {
-    ChangeStatus Changed = ChangeStatus::UNCHANGED;
+    if (IsPtr) {
+      if (NewC)
+        return ConstantExpr::getPointerBitCastOrAddrSpaceCast(NewC, Ty);
+      if (Ty->getPointerAddressSpace() ==
+          NewValue->getType()->getPointerAddressSpace())
+        return new BitCastInst(NewValue, Ty, ".cast", IP);
+    }
 
-    if (!SimplifiedAssociatedValue.hasValue() ||
-        !SimplifiedAssociatedValue.getValue())
-      return Changed;
+    // TODO: Deal with other casts
+    DEBUG_WITH_TYPE("attributor-value-simplify",
+                    dbgs() << "[AAValueSimplify] New value '" << *NewValue
+                           << "' needs complex cast to " << *Ty << ".\n");
 
-    if (auto *C = dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())) {
-      // We can replace the AssociatedValue with the constant.
-      Value &V = getAssociatedValue();
-      if (!V.user_empty() && &V != C && V.getType() == C->getType()) {
-        LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << V << " -> " << *C
-                          << "\n");
-        replaceAllUsesWith(V, *C);
-        Changed = ChangeStatus::CHANGED;
-      }
-    }
+    return nullptr;
 
-    return Changed | AAValueSimplify::manifest(A);
+  /// Returns true if \p NewValue can be used in the scope of this AA.
+  bool canBeUsedInstead(Value &NewValue) const {
+    // Constants are valid everywhere.
+    if (isa<Constant>(NewValue))
+      return true;
+
+    // Check if the simplified value is an instruction or argument in the same
+    // scope as the anchor.
+    const IRPosition &IRP = getIRPosition();
+    if (auto *NewI = dyn_cast<Instruction>(&NewValue))
+      if (NewI->getFunction() == IRP.getAnchorScope())
+        return /* TODO: Dominance test! */ false;
+
+    // Arguments trivially dominate the function.
+    if (auto *NewArg = dyn_cast<Argument>(&NewValue))
+      return NewArg->getParent() == IRP.getAnchorScope();
+
+    return false;
   }
 
-protected:
-  // An assumed simplified value. Initially, it is set to Optional::None, which
-  // means that the value is not clear under current assumption. If in the
-  // pessimistic state, getAssumedSimplifiedValue doesn't return this value but
-  // returns orignal associated value.
-  Optional<Value *> SimplifiedAssociatedValue;
+  /// Values equivalent to the one represented by the AA.
+  /// TODO: Use the fact that we collect more than only a single one.
+  SmallPtrSet<Value *, 8> PotentialValues;
 };
 
 struct AAValueSimplifyArgument final : AAValueSimplifyImpl {
   AAValueSimplifyArgument(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {}
 
   void initialize(Attributor &A) override {
     AAValueSimplifyImpl::initialize(A);
     if (!getAssociatedFunction() || getAssociatedFunction()->isDeclaration())
       indicatePessimisticFixpoint();
     if (hasAttr({Attribute::InAlloca, Attribute::StructRet, Attribute::Nest},
                 /* IgnoreSubsumingPositions */ true))
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
-    // Byval is only replacable if it is readonly otherwise we would write into
+    // Byval is only replaceable if it is readonly otherwise we would write into
     // the replaced value and not the copy that byval creates implicitly.
+    // TODO: We can/should look into byval replacement separately.
     Argument *Arg = getAssociatedArgument();
     if (Arg->hasByValAttr()) {
       const auto &MemAA = A.getAAFor<AAMemoryBehavior>(*this, getIRPosition());
       if (!MemAA.isAssumedReadOnly())
         return indicatePessimisticFixpoint();
     }
 
-    bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
+    Optional<Value *> Before = getAssumedSimplifiedValue();
+    PotentialValues.clear();
 
     auto PredForCallSite = [&](AbstractCallSite ACS) {
       // Check if we have an associated argument or not (which can happen for
       // callback calls).
       Value *ArgOp = ACS.getCallArgOperand(getArgNo());
       if (!ArgOp)
         return false;
+
       // We can only propagate thread independent values through callbacks.
       // This is different to direct/indirect call sites because for them we
       // know the thread executing the caller and callee is the same. For
       // callbacks this is not guaranteed, thus a thread dependent value could
       // be different for the caller and callee, making it invalid to propagate.
-      if (ACS.isCallbackCall())
-        if (auto *C =dyn_cast<Constant>(ArgOp))
-          if (C->isThreadDependent())
-            return false;
-      return checkAndUpdate(A, *this, *ArgOp, SimplifiedAssociatedValue);
+      if (ACS.isCallbackCall() && isa<Constant>(ArgOp))
+        if (cast<Constant>(ArgOp)->isThreadDependent())
+
+      // Use the generic combiner function.
+      return recurseAndCombined(A, *ArgOp);
     };
 
     if (!A.checkForAllCallSites(PredForCallSite, *this, true))
       return indicatePessimisticFixpoint();
 
-    // If a candicate was found in this update, return CHANGED.
-    return HasValueBefore == SimplifiedAssociatedValue.hasValue()
-               ? ChangeStatus::UNCHANGED
-               : ChangeStatus ::CHANGED;
+    // If no new candidates were found in this update, return UNCHANGED.
+    Optional<Value *> After = getAssumedSimplifiedValue();
+    if (Before == After)
+      return ChangeStatus::UNCHANGED;
+
+    // If we don't have a single replacement candidate, give up for now.
+    if (After.hasValue() && !After.getValue())
+      return indicatePessimisticFixpoint();
+
+    return ChangeStatus::CHANGED;
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_ARG_ATTR(value_simplify)
   }
 };
 
 struct AAValueSimplifyReturned : AAValueSimplifyImpl {
   AAValueSimplifyReturned(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {}
 
+  void initialize(Attributor &A) override {
+    if (!getAssociatedFunction() || getAssociatedFunction()->isDeclaration())
+      indicatePessimisticFixpoint();
+  }
+
+  ChangeStatus indicatePessimisticFixpoint() override {
+    // Because there is no generic single "return value" we cannot fall back to
+    // anything known and need to indicate an invalid state instead.
+    PotentialValues.clear();
+    PotentialValues.insert(nullptr);
+    AAValueSimplify::indicatePessimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
-    bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
+    Optional<Value *> Before = getAssumedSimplifiedValue();
+    PotentialValues.clear();
 
-    auto PredForReturned = [&](Value &V) {
-      return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
+    // TODO: Use AAReturnedValues here.
+    auto PredForReturned = [&](Instruction &I) {
+      // Use the generic combiner function.
+      return recurseAndCombined(A, *cast<ReturnInst>(I).getOperand(0));
     };
+    if (!A.checkForAllInstructions(PredForReturned, *this, {Instruction::Ret}))
+      return indicatePessimisticFixpoint();
 
-    if (!A.checkForAllReturnedValues(PredForReturned, *this))
+    // If no new candidates were found in this update, return UNCHANGED.
+    Optional<Value *> After = getAssumedSimplifiedValue();
+    if (Before == After)
+      return ChangeStatus::UNCHANGED;
+
+    // If we don't have a single replacement candidate, give up for now.
+    if (After.hasValue() && !After.getValue())
       return indicatePessimisticFixpoint();
 
-    // If a candicate was found in this update, return CHANGED.
-    return HasValueBefore == SimplifiedAssociatedValue.hasValue()
-               ? ChangeStatus::UNCHANGED
-               : ChangeStatus ::CHANGED;
+    return ChangeStatus ::CHANGED;
+  }
+
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    Function *AssociatedFunction = getAssociatedFunction();
+    ChangeStatus Changed = ChangeStatus::UNCHANGED;
+    // TODO: Rework AAReturnedValues to not emit return instructions from other
+    //       functions and also not duplicate them. We should probably use
+    //       AAValueSimplify there as well.
+    auto RetValRepl = [&](Instruction &I) {
+      Value *OldValue = I.getOperand(0);
+      // TODO: Modify must tail call chains.
+      if (ImmutableCallSite ICS =
+              ImmutableCallSite(OldValue->stripPointerCasts()))
+        if (ICS.isMustTailCall())
+          return true;
+
+      Value *NewValue = getReplacementForAt(*OldValue, &I);
+      if (!NewValue)
+        return true;
+
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs()
+                          << "[AAValueSimplify] Replace '" << OldValue
+                          << "' with '" << *NewValue << "' in " << I << "\n");
+      if (A.changeUseAfterManifest(*I.op_begin(), *NewValue))
+        Changed = ChangeStatus::CHANGED;
+      return true;
+    };
+
+    A.checkForAllInstructions(RetValRepl, *this, {Instruction::Ret});
+
+    return Changed;
   }
+
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_FNRET_ATTR(value_simplify)
   }
 };
 
 struct AAValueSimplifyFloating : AAValueSimplifyImpl {
   AAValueSimplifyFloating(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {}
 
-  /// See AbstractAttribute::initialize(...).
-  void initialize(Attributor &A) override {
-    Value &V = getAnchorValue();
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    Optional<Value *> Before = getAssumedSimplifiedValue();
+    PotentialValues.clear();
 
-    // TODO: add other stuffs
-    if (isa<Constant>(V) || isa<UndefValue>(V))
-      indicatePessimisticFixpoint();
+    auto GetConstantForValue = [&](Value *V, bool &AllConst) -> Constant * {
+      if (Constant *COp = dyn_cast<Constant>(V))
+        return COp;
+      auto &VAA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(*V));
+      if (Constant *COp = dyn_cast_or_null<Constant>(
+              VAA.getReplacementForAt(*V, getCtxI())))
+        return COp;
+      AllConst = false;
+      return nullptr;
+    };
+
+    SmallVector<Value *, 4> GlobalPotentialValues;
+    auto GlobalVariableUseCB = [&](const Use &U, bool &Follow) {
+      if (isa<CastInst>(U.getUser())) {
+        Follow = true;
+        return true;
       }
 
-  /// See AbstractAttribute::updateImpl(...).
-  ChangeStatus updateImpl(Attributor &A) override {
-    bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
+      Follow = false;
+      if (isa<LoadInst>(U.getUser()))
+        return true;
+      auto *SI = dyn_cast<StoreInst>(U.getUser());
+      if (!SI || SI->getValueOperand() == U.get())
+        return false;
+      Value &V = *SI->getValueOperand();
+      if (!isa<Constant>(V))
+        return false;
+      if (!isa<UndefValue>(V))
+        GlobalPotentialValues.push_back(&V);
+      return true;
+    };
 
     auto VisitValueCB = [&](Value &V, BooleanState, bool Stripped) -> bool {
-      auto &AA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V));
-      if (!Stripped && this == &AA) {
-        // TODO: Look the instruction and check recursively.
-        LLVM_DEBUG(
-            dbgs() << "[Attributor][ValueSimplify] Can't be stripped more : "
-                   << V << "\n");
-        indicatePessimisticFixpoint();
-        return false;
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs()
+                          << "[AAValueSimplify] generic visit " << V << "\n");
+
+      auto &VAA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V));
+      if (Stripped || this != &VAA) {
+        // Use the generic combiner function.
+        return recurseAndCombined(A, V, &VAA);
       }
-      return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
+
+      Instruction *I = dyn_cast<Instruction>(&V);
+      if (!I) {
+        if (!isa<UndefValue>(V))
+          PotentialValues.insert(&V);
+        return true;
+      }
+
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs() << "[AAValueSimplify] Leaf reached (" << V
+                             << "), try folding\n");
+
+      bool AllConst = true;
+      SmallVector<Constant *, 4> COps;
+      for (Value *Op : I->operands())
+        COps.push_back(GetConstantForValue(Op, AllConst));
+
+      auto AddReplacement = [&](ArrayRef<Value *> Repls) {
+        DEBUG_WITH_TYPE("attributor-value-simplify", {
+          for (Value *Repl : Repls)
+            dbgs() << "[AAValueSimplify] Folding successful: " << *Repl << "\n";
+        });
+        for (Value *Repl : Repls)
+          if (!isa<UndefValue>(Repl))
+            PotentialValues.insert(Repl);
+      };
+
+      switch (I->getOpcode()) {
+      case Instruction::Load:
+        // If we load an undef pointer, we can simplify the load to an undef
+        // (which we don't track).
+        if (isa_and_nonnull<UndefValue>(COps[0]))
+          return true;
+        // If we load a null pointer and those are not defined, we can simplify
+        // the load to an undef (which we don't track).
+        if (COps[0] && COps[0]->isNullValue() &&
+            !NullPointerIsDefined(
+                I->getFunction(),
+                COps[0]->getType()->getPointerAddressSpace())) {
+          AddReplacement({UndefValue::get(COps[0]->getType())});
+          return true;
+        }
+        // If we load a global variable, check if all uses are OK and if so,
+        // the values stored plus the initializer can be potentially loaded
+        // values.
+        if (auto *GV = dyn_cast_or_null<GlobalVariable>(COps[0]))
+          if (GV->hasLocalLinkage(),
+              A.checkForAllUses(GlobalVariableUseCB, *this, *GV)) {
+            AddReplacement({GV->getInitializer()});
+            AddReplacement(GlobalPotentialValues);
+            return true;
+          }
+        break;
+      case Instruction::Select:
+        if (COps[0]) {
+          AddReplacement(COps[0]->isNullValue() ? I->getOperand(1)
+                                                : I->getOperand(0));
+          return true;
+        }
+        break;
+      case Instruction::ICmp: {
+        bool IsEq = cast<ICmpInst>(I)->getPredicate() == ICmpInst::ICMP_EQ;
+        // Check if one operand is `null` and one is assumed non-null.
+        for (unsigned u = 0; u <= 1 && !AllConst && IsEq; ++u) {
+          if (!COps[u] || !COps[u]->isNullValue())
+            continue;
+          const auto &OpNonNullAA = A.getAAFor<AANonNull>(
+              *this, IRPosition::value(*I->getOperand(1 - u)));
+          if (!OpNonNullAA.isAssumedNonNull())
+            continue;
+          AddReplacement({ConstantInt::getFalse(I->getType())});
+          return true;
+        }
+      }
+        LLVM_FALLTHROUGH;
+      case Instruction::FCmp:
+        if (AllConst) {
+          CmpInst *CmpI = cast<CmpInst>(I);
+          if (Value *Repl = ConstantFoldCompareInstOperands(
+                  CmpI->getPredicate(), COps[0], COps[1], A.getDataLayout())) {
+            AddReplacement({Repl});
+            return true;
+          }
+        }
+        break;
+      default:
+        if (AllConst) {
+          if (Value *Repl =
+                  ConstantFoldInstOperands(I, COps, A.getDataLayout())) {
+            AddReplacement({Repl});
+            return true;
+          }
+          // TODO: Check if we can reuse some logic or have to write our own
+          // for partially constant values.
+        }
+        break;
+      };
+
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs() << "[AAValueSimplify] Folding failed\n");
+      PotentialValues.insert(I);
+      return true;
     };
 
     if (!genericValueTraversal<AAValueSimplify, BooleanState>(
             A, getIRPosition(), *this, static_cast<BooleanState &>(*this),
             VisitValueCB))
       return indicatePessimisticFixpoint();
 
-    // If a candicate was found in this update, return CHANGED.
+    // If no new candidates were found in this update, return UNCHANGED.
+    Optional<Value *> After = getAssumedSimplifiedValue();
+    if (Before == After)
+      return ChangeStatus::UNCHANGED;
 
-    return HasValueBefore == SimplifiedAssociatedValue.hasValue()
-               ? ChangeStatus::UNCHANGED
-               : ChangeStatus ::CHANGED;
+    // If we don't have a single replacement candidate, give up for now.
+    if (After.hasValue() && !After.getValue())
+      return indicatePessimisticFixpoint();
+
+    return ChangeStatus::CHANGED;
   }
 
-  /// See AbstractAttribute::trackStatistics()
+  /// See AbstractAttribute::trackStatistics().
   void trackStatistics() const override {
     STATS_DECLTRACK_FLOATING_ATTR(value_simplify)
   }
 };
 
 struct AAValueSimplifyFunction : AAValueSimplifyImpl {
   AAValueSimplifyFunction(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {}
 
-  /// See AbstractAttribute::initialize(...).
-  void initialize(Attributor &A) override {
-    SimplifiedAssociatedValue = &getAnchorValue();
-    indicateOptimisticFixpoint();
-  }
-  /// See AbstractAttribute::initialize(...).
+  /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     llvm_unreachable(
         "AAValueSimplify(Function|CallSite)::updateImpl will not be called");
   }
-  /// See AbstractAttribute::trackStatistics()
+
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    return ChangeStatus::UNCHANGED;
+  }
+
+  /// See AbstractAttribute::trackStatistics().
   void trackStatistics() const override {
-    STATS_DECLTRACK_FN_ATTR(value_simplify)
+    llvm_unreachable("AAValueSimplify(Function|CallSite)::trackStatistics will "
+                     "not be called");
   }
 };
 
+// TODO: Remove this as it can never be instantiated. This Will require a new
+//       createForPosition template.
 struct AAValueSimplifyCallSite : AAValueSimplifyFunction {
   AAValueSimplifyCallSite(const IRPosition &IRP)
       : AAValueSimplifyFunction(IRP) {}
-  /// See AbstractAttribute::trackStatistics()
-  void trackStatistics() const override {
-    STATS_DECLTRACK_CS_ATTR(value_simplify)
-  }
 };
 
-struct AAValueSimplifyCallSiteReturned : AAValueSimplifyReturned {
+struct AAValueSimplifyCallSiteReturned : AAValueSimplifyImpl {
   AAValueSimplifyCallSiteReturned(const IRPosition &IRP)
-      : AAValueSimplifyReturned(IRP) {}
+      : AAValueSimplifyImpl(IRP) {}
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    Optional<Value *> Before = getAssumedSimplifiedValue();
+    PotentialValues.clear();
+
+    // TODO: Once we have call site specific value information we can provide
+    //       call site specific liveness information and then it makes
+    //       sense to specialize attributes for call sites instead of
+    //       redirecting requests to the callee return value.
+    Function *F = getAssociatedFunction();
+    if (!F)
+      return indicatePessimisticFixpoint();
+
+    const IRPosition &RetPos = IRPosition::returned(*F);
+    auto &FnRetAA = A.getAAFor<AAValueSimplify>(*this, RetPos);
+    Optional<Value *> FnRetValOpt = FnRetAA.getAssumedSimplifiedValue();
+    if (FnRetValOpt.hasValue()) {
+      Value *FnRetVal = FnRetValOpt.getValue();
+      if (!FnRetVal)
+        return indicatePessimisticFixpoint();
+
+      // Copy equivalent values over but translate arguments of the callee to
+      // call site operands instead.
+      auto *CB = cast<CallBase>(getCtxI());
+      if (isa<Constant>(FnRetVal)) {
+        if (!isa<UndefValue>(FnRetVal))
+          PotentialValues.insert(FnRetVal);
+      } else if (auto *Arg = dyn_cast<Argument>(FnRetVal)) {
+        if (Arg->getParent() == CB->getCalledFunction()) {
+          // Use the generic combiner function.
+          if (!recurseAndCombined(A, *CB->getArgOperand(Arg->getArgNo())))
+            return indicatePessimisticFixpoint();
+        } else {
+          if (!isa<UndefValue>(FnRetVal))
+            PotentialValues.insert(FnRetVal);
+        }
+      } else {
+        return indicatePessimisticFixpoint();
+      }
+    }
+
+    // If no new candidates were found in this update, return UNCHANGED.
+    Optional<Value *> After = getAssumedSimplifiedValue();
+    if (Before == After)
+      return ChangeStatus::UNCHANGED;
 
+    // If we don't have a single replacement candidate, give up for now.
+    if (After.hasValue() && !After.getValue())
+      return indicatePessimisticFixpoint();
+
+    return ChangeStatus::CHANGED;
+  }
+
+  /// See AbstractAttribute::trackStatistics().
   void trackStatistics() const override {
     STATS_DECLTRACK_CSRET_ATTR(value_simplify)
   }
 };
+
 struct AAValueSimplifyCallSiteArgument : AAValueSimplifyFloating {
   AAValueSimplifyCallSiteArgument(const IRPosition &IRP)
       : AAValueSimplifyFloating(IRP) {}
 
+  /// See AbstractAttribute::trackStatistics().
   void trackStatistics() const override {
     STATS_DECLTRACK_CSARG_ATTR(value_simplify)
   }
 };
 
 /// ----------------------- Heap-To-Stack Conversion ---------------------------
 struct AAHeapToStackImpl : public AAHeapToStack {
   AAHeapToStackImpl(const IRPosition &IRP) : AAHeapToStack(IRP) {}
for (AbstractAttribute *AA : AllAbstractAttributes) {
 
     // Skip dead code.
     if (isAssumedDead(*AA, nullptr))
       continue;
     // Manifest the state and record if we changed the IR.
     ChangeStatus LocalChange = AA->manifest(*this);
     if (LocalChange == ChangeStatus::CHANGED && AreStatisticsEnabled())
       AA->trackStatistics();
+    LLVM_DEBUG({
+      if (LocalChange == ChangeStatus::CHANGED)
+        errs() << "MANIFEST: " << *AA << "\n";
+    });
 
     ManifestChange = ManifestChange | LocalChange;
 
     NumAtFixpoint++;
     NumManifested += (LocalChange == ChangeStatus::CHANGED);
   }
 
   (void)NumManifested;
   (void)NumAtFixpoint;
   LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
                     << " arguments while " << NumAtFixpoint
                     << " were in a valid fixpoint state\n");
 
   NumAttributesManifested += NumManifested;
   NumAttributesValidFixpoint += NumAtFixpoint;
 
   (void)NumFinalAAs;
   assert(
       NumFinalAAs == AllAbstractAttributes.size() &&
       "Expected the final number of abstract attributes to remain unchanged!");
 
+  AAMap.clear();
+
   // Set of functions for which we modified the content such that it might
   // impact the call graph.
   SmallPtrSet<Function *, 8> CGModifiedFunctions;
 
   // Delete stuff at the end to avoid invalid references and a nice order.
   {
     LLVM_DEBUG(dbgs() << "\n[Attributor] Delete at least "
                       << ToBeDeletedFunctions.size() << " functions and "
ChangeStatus Attributor::run() {
   // Rewrite the functions as requested during manifest.
   ManifestChange = ManifestChange | rewriteFunctionSignatures();
 
   if (VerifyMaxFixpointIterations &&
       IterationCounter != MaxFixpointIterations) {
     errs() << "\n[Attributor] Fixpoint iteration done after: "
            << IterationCounter << "/" << MaxFixpointIterations
            << " iterations\n";
-    llvm_unreachable("The fixpoint was not reached with exactly the number of "
-                     "specified iterations!");
+    //llvm_unreachable("The fixpoint was not reached with exactly the number of "
+                     //"specified iterations!");
   }
 
   for (Function *Fn : CGModifiedFunctions)
     CGUpdater.reanalyzeFunction(*Fn);
 
   return ManifestChange;
 }
 
if (!ReturnType->isVoidTy()) {
     // though it is an argument attribute.
     getOrCreateAAFor<AAReturnedValues>(FPos);
 
     IRPosition RetPos = IRPosition::returned(F);
 
     // Every returned value might be dead.
     getOrCreateAAFor<AAIsDead>(RetPos);
 
-    // Every function might be simplified.
+    // Return instructions/values might be simplified.
     getOrCreateAAFor<AAValueSimplify>(RetPos);
 
     if (ReturnType->isPointerTy()) {
 
       // Every function with pointer return type might be marked align.
       getOrCreateAAFor<AAAlign>(RetPos);
 
       // Every function with pointer return type might be marked nonnull.
if (Function *Callee = CS.getCalledFunction()) {
       if (!AnnotateDeclarationCallSites && Callee->isDeclaration())
         return true;
 
       if (!Callee->getReturnType()->isVoidTy() && !CS->use_empty()) {
         IRPosition CSRetPos = IRPosition::callsite_returned(CS);
 
         // Call site return values might be dead.
         getOrCreateAAFor<AAIsDead>(CSRetPos);
+
+        // Call site return values might be simplified.
+        getOrCreateAAFor<AAValueSimplify>(CSRetPos);
       }
 
       for (int i = 0, e = Callee->arg_size(); i < e; i++) {
 
         IRPosition CSArgPos = IRPosition::callsite_argument(CS, i);
 
         // Every call site argument might be dead.
         getOrCreateAAFor<AAIsDead>(CSArgPos);

llvm/test/Transforms/Attributor/nonnull.ll

 declare i32 @esfp(...)
 
 define i1 @parent8(i8* %a, i8* %bogus1, i8* %b) personality i8* bitcast (i32 (...)* @esfp to i8*){
 ; ATTRIBUTOR-LABEL: @parent8(i8* nonnull %a, i8* nocapture nofree readnone %bogus1, i8* nonnull %b)
 ; ATTRIBUTOR-NEXT:  entry:
 ; ATTRIBUTOR-NEXT:    invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b)
 ; ATTRIBUTOR-NEXT:    to label %cont unwind label %exc
 ; ATTRIBUTOR:       cont:
-; ATTRIBUTOR-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %b, null
-; ATTRIBUTOR-NEXT:    ret i1 [[NULL_CHECK]]
+; ATTRIBUTOR-NEXT:    ret i1 false
 ; ATTRIBUTOR:       exc:
 ; ATTRIBUTOR-NEXT:    [[LP:%.*]] = landingpad { i8*, i32 }
 ; ATTRIBUTOR-NEXT:    filter [0 x i8*] zeroinitializer
 ; ATTRIBUTOR-NEXT:    unreachable
 
 entry:
   invoke void @use2nonnull(i8* %a, i8* %b)
   to label %cont unwind label %exc

 8:                                                ; preds = %8, %4
   %9 = phi i32 [ 1, %4 ], [ %10, %8 ]
   tail call void @sink(i32* %6)
   %10 = add nuw nsw i32 %9, 1
   %11 = icmp eq i32 %10, %1
   br i1 %11, label %7, label %8
 }
 
+; Make sure that if load/store happened, the pointer is nonnull. Taken from D71177.
+
+define i32 @test_null_after_store(i32* %0) {
+; CHECK-LABEL: @test_null_after_store(
+; CHECK-NEXT:    store i32 123, i32* %0, align 4
+; CHECK-NEXT:    ret i32 2
+  store i32 123, i32* %0, align 4
+  %2 = icmp eq i32* %0, null
+  %3 = select i1 %2, i32 1, i32 2
+  ret i32 %3
+}
+
+define i32 @test_null_after_load(i32* %0) {
+; CHECK-LABEL: @test_null_after_load(
+; CHECK-NEXT:    ret i32 1
+  %2 = load i32, i32* %0, align 4
+  %3 = icmp eq i32* %0, null
+  %4 = select i1 %3, i32 %2, i32 1
+  ret i32 %4
+}
+
+; Make sure that different address space does not affect null pointer check.
+
+define i32 @test_null_after_store_addrspace(i32 addrspace(1)* %0) {
+; CHECK-LABEL: @test_null_after_store_addrspace(
+; CHECK-NEXT:    store i32 123, i32 addrspace(1)* %0, align 4
+; CHECK-NEXT:    %2 = icmp eq i32 addrspace(1)* %0, null
+; CHECK-NEXT:    %3 = select i1 %2, i32 1, i32 2
+; CHECK-NEXT:    ret i32 %3
+  store i32 123, i32 addrspace(1)* %0, align 4
+  %2 = icmp eq i32 addrspace(1)* %0, null
+  %3 = select i1 %2, i32 1, i32 2
+  ret i32 %3
+}
+
+define i32 @test_null_after_load_addrspace(i32 addrspace(1)* %0) {
+; CHECK-LABEL: @test_null_after_load_addrspace(
+; CHECK-NEXT:    %2 = load i32, i32 addrspace(1)* %0, align 4
+; CHECK-NEXT:    %3 = icmp eq i32 addrspace(1)* %0, null
+; CHECK-NEXT:    %4 = select i1 %3, i32 %2, i32 1
+; CHECK-NEXT     ret i32 %4
+  %2 = load i32, i32 addrspace(1)* %0, align 4
+  %3 = icmp eq i32 addrspace(1)* %0, null
+  %4 = select i1 %3, i32 %2, i32 1
+  ret i32 %4
+}
+
+; Make sure if store happened after the check, nullptr check is not removed.
+
+declare i8* @func(i64)
+
+define i8* @test_load_store_after_check(i8* %0) {
+; CHECK-LABEL: @test_load_store_after_check(
+entry:
+; CHECK: @func
+  %1 = call i8* @func(i64 0)
+; CHECK: icmp eq
+  %null_check = icmp eq i8* %1, null
+; CHECK: br i1
+  br i1 %null_check, label %return, label %if.end
+
+if.end:
+; CHECK: store
+  store i8 7, i8* %1
+  br label %return
+
+return:
+; CHECK: phi
+  %retval.0 = phi i8* [ %1, %if.end ], [ null, %entry ]
+  ret i8* %retval.0
+}
+
 attributes #0 = { "null-pointer-is-valid"="true" }
 attributes #1 = { nounwind willreturn}

llvm/test/Transforms/Attributor/returned.ll

 }
 define i32 @exact(i32* %a) {
   %c0 = call i32 @non_exact_0()
   %c1 = call i32 @non_exact_1(i32 1)
   %c2 = call i32 @non_exact_2(i32 2)
   %c3 = call i32* @non_exact_3(i32* %a)
 ; We can use the information of the weak function non_exact_3 because it was
 ; given to us and not derived (the alignment of the returned argument).
-; ATTRIBUTOR:  %c4 = load i32, i32* %c3, align 32
   %c4 = load i32, i32* %c3
-; FIXME: %c2 and %c3 should be replaced but not %c0 or %c1!
+; Make sure not to replace %c0 or %c1!
+; ATTRIBUTOR:  %c4 = load i32, i32* %a
 ; ATTRIBUTOR:  %add1 = add i32 %c0, %c1
-; ATTRIBUTOR:  %add2 = add i32 %add1, %c2
+; ATTRIBUTOR:  %add2 = add i32 %add1, 2
 ; ATTRIBUTOR:  %add3 = add i32 %add2, %c4
   %add1 = add i32 %c0, %c1
   %add2 = add i32 %add1, %c2
   %add3 = add i32 %add2, %c4
   ret i32 %add3
 }
 
 @G = external global i8

llvm/test/Transforms/Attributor/value-simplify.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
 ; RUN: opt -attributor --attributor-disable=false -attributor-annotate-decl-cs -S < %s | FileCheck %s
 ; TODO: Add max-iteration check
 
 ; Disable update test checks and enable it where required.
 ; UTC_ARGS: --turn off
 
 ; ModuleID = 'value-simplify.ll'
 source_filename = "value-simplify.ll"
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
 declare void @f(i32)
 
 ; Test1: Replace argument with constant
 define internal void @test1(i32 %a) {
-; CHECK: tail call void @f(i32 1)
+; CHECK-LABEL: define {{[^@]+}}@test1
+; CHECK-SAME: (i32 [[A:%.*]])
+; CHECK-NEXT:    tail call void @f(i32 1)
+; CHECK-NEXT:    ret void
+;
   tail call void @f(i32 %a)
   ret void
 }
 
 define void @test1_helper() {
+; CHECK-LABEL: define {{[^@]+}}@test1_helper()
+; CHECK-NEXT:    tail call void @test1(i32 1)
+; CHECK-NEXT:    ret void
+;
   tail call void @test1(i32 1)
   ret void
 }
 
 ; TEST 2 : Simplify return value
 define i32 @return0() {
+; CHECK-LABEL: define {{[^@]+}}@return0()
+; CHECK-NEXT:    ret i32 0
+;
   ret i32 0
 }
 
 define i32 @return1() {
+; CHECK-LABEL: define {{[^@]+}}@return1()
+; CHECK-NEXT:    ret i32 1
+;
   ret i32 1
 }
 
-; CHECK: define i32 @test2_1(i1 %c)
 define i32 @test2_1(i1 %c) {
+; CHECK-LABEL: define {{[^@]+}}@test2_1
+; CHECK-SAME: (i1 [[C:%.*]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ]
+; CHECK-NEXT:    ret i32 1
+;
   br i1 %c, label %if.true, label %if.false
 if.true:
   %call = tail call i32 @return0()
 
-; FIXME: %ret0 should be replaced with i32 1.
-; CHECK: %ret0 = add i32 0, 1
   %ret0 = add i32 %call, 1
   br label %end
 if.false:
   %ret1 = tail call i32 @return1()
   br label %end
 end:
 
 ; FIXME: %ret should be replaced with i32 1.
-; CHECK: %ret = phi i32 [ %ret0, %if.true ], [ 1, %if.false ]
   %ret = phi i32 [ %ret0, %if.true ], [ %ret1, %if.false ]
 
 ; FIXME: ret i32 1
-; CHECK: ret i32 %ret
   ret i32 %ret
 }
 
 
 
-; CHECK: define i32 @test2_2(i1 %c)
 define i32 @test2_2(i1 %c) {
 ; FIXME: %ret should be replaced with i32 1.
+; CHECK-LABEL: define {{[^@]+}}@test2_2
+; CHECK-SAME: (i1 [[C:%.*]])
+; CHECK-NEXT:    ret i32 1
+;
   %ret = tail call i32 @test2_1(i1 %c)
 ; FIXME: ret i32 1
-; CHECK: ret i32 %ret
   ret i32 %ret
 }
 
 declare void @use(i32)
-; CHECK: define void @test3(i1 %c)
 define void @test3(i1 %c) {
+; CHECK-LABEL: define {{[^@]+}}@test3
+; CHECK-SAME: (i1 [[C:%.*]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if.true:
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ]
+; CHECK-NEXT:    tail call void @use(i32 1)
+; CHECK-NEXT:    ret void
+;
   br i1 %c, label %if.true, label %if.false
 if.true:
   br label %end
 if.false:
   %ret1 = tail call i32 @return1()
   br label %end
 end:
 
-; CHECK: %r = phi i32 [ 1, %if.true ], [ 1, %if.false ]
   %r = phi i32 [ 1, %if.true ], [ %ret1, %if.false ]
 
-; CHECK: tail call void @use(i32 1)
   tail call void @use(i32 %r)
   ret void
 }
 
 define void @test-select-phi(i1 %c) {
+; CHECK-LABEL: define {{[^@]+}}@test-select-phi
+; CHECK-SAME: (i1 [[C:%.*]])
+; CHECK-NEXT:    tail call void @use(i32 1)
+; CHECK-NEXT:    [[SELECT_NOT_SAME:%.*]] = select i1 [[C]], i32 1, i32 0
+; CHECK-NEXT:    tail call void @use(i32 [[SELECT_NOT_SAME]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if-true:
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if-false:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI_SAME:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[PHI_NOT_SAME:%.*]] = phi i32 [ 0, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[PHI_SAME_PROP:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ 1, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[PHI_SAME_UNDEF:%.*]] = phi i32 [ 1, [[IF_TRUE]] ], [ undef, [[IF_FALSE]] ]
+; CHECK-NEXT:    [[SELECT_NOT_SAME_UNDEF:%.*]] = select i1 [[C]], i32 [[PHI_NOT_SAME]], i32 undef
+; CHECK-NEXT:    tail call void @use(i32 1)
+; CHECK-NEXT:    tail call void @use(i32 [[PHI_NOT_SAME]])
+; CHECK-NEXT:    tail call void @use(i32 1)
+; CHECK-NEXT:    tail call void @use(i32 1)
+; CHECK-NEXT:    tail call void @use(i32 [[SELECT_NOT_SAME_UNDEF]])
+; CHECK-NEXT:    ret void
+;
   %select-same = select i1 %c, i32 1, i32 1
-  ; CHECK: tail call void @use(i32 1)
   tail call void @use(i32 %select-same)
 
   %select-not-same = select i1 %c, i32 1, i32 0
-  ; CHECK: tail call void @use(i32 %select-not-same)
   tail call void @use(i32 %select-not-same)
   br i1 %c, label %if-true, label %if-false
 if-true:
   br label %end
 if-false:
   br label %end
 end:
   %phi-same = phi i32 [ 1, %if-true ], [ 1, %if-false ]
   %phi-not-same = phi i32 [ 0, %if-true ], [ 1, %if-false ]
   %phi-same-prop = phi i32 [ 1, %if-true ], [ %select-same, %if-false ]
   %phi-same-undef = phi i32 [ 1, %if-true ], [ undef, %if-false ]
   %select-not-same-undef = select i1 %c, i32 %phi-not-same, i32 undef
 
 
-  ; CHECK: tail call void @use(i32 1)
   tail call void @use(i32 %phi-same)
 
-  ; CHECK: tail call void @use(i32 %phi-not-same)
   tail call void @use(i32 %phi-not-same)
 
-  ; CHECK: tail call void @use(i32 1)
   tail call void @use(i32 %phi-same-prop)
 
-  ; CHECK: tail call void @use(i32 1)
   tail call void @use(i32 %phi-same-undef)
 
-  ; CHECK: tail call void @use(i32 %select-not-same-undef)
   tail call void @use(i32 %select-not-same-undef)
 
   ret void
 
 }
 
 define i32 @ipccp1(i32 %a) {
 ; CHECK-LABEL: define {{[^@]+}}@ipccp1

 define i32 @ipccp3() {
 ; CHECK-LABEL: define {{[^@]+}}@ipccp3() #1
 ; CHECK-NEXT:    [[R:%.*]] = call i32 @ipccp3i(i32 7) #1
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %r = call i32 @ipccp3i(i32 7)
   ret i32 %r
 }
+<<<<<<< HEAD
 
 ; UTC_ARGS: --turn on
 
 ; Do not touch complicated arguments (for now)
 %struct.X = type { i8* }
 define internal i32* @test_inalloca(i32* inalloca %a) {
 ; CHECK-LABEL: define {{[^@]+}}@test_inalloca
 ; CHECK-SAME: (i32* inalloca noalias nofree returned writeonly [[A:%.*]])

 ; CHECK-NEXT:    call void @test_byval(%struct.X* nofree nonnull align 8 dereferenceable(8) @S)
 ; CHECK-NEXT:    ret void
 ;
   call void @test_byval(%struct.X* @S)
   ret void
 }
 
 ; UTC_ARGS: --turn off
+||||||| parent of d2d3c463f81... [Attributor] Make value simplify stronger
+=======
+
+define internal i32 @rec0(i32 %a0) {
+; CHECK-LABEL: define {{[^@]+}}@rec0
+; CHECK-SAME: (i32 returned [[A0:%.*]])
+; CHECK-NEXT:    ret i32 [[A0]]
+;
+  ret i32 %a0
+}
+
+define internal i32 @rec1(i1 %c, i32 %a1) {
+; CHECK-LABEL: define {{[^@]+}}@rec1
+; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A1:%.*]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if-true:
+; CHECK-NEXT:    [[REC0:%.*]] = call i32 @rec0(i32 [[A1]])
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if-false:
+; CHECK-NEXT:    [[REC1:%.*]] = call i32 @rec1(i1 true, i32 [[A1]])
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI_SAME:%.*]] = phi i32 [ [[REC0]], [[IF_TRUE]] ], [ [[REC1]], [[IF_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[PHI_SAME]]
+;
+  br i1 %c, label %if-true, label %if-false
+if-true:
+  %rec0 = call i32 @rec0(i32 %a1)
+  br label %end
+if-false:
+  %rec1 = call i32 @rec1(i1 true, i32 %a1)
+  br label %end
+end:
+  %phi-same = phi i32 [ %rec0, %if-true ], [ %rec1, %if-false ]
+  ret i32 %phi-same
+}
+
+define internal i32 @rec2(i1 %c, i32 %a2) {
+; CHECK-LABEL: define {{[^@]+}}@rec2
+; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A2:%.*]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if-true:
+; CHECK-NEXT:    [[REC1:%.*]] = call i32 @rec1(i1 [[C]], i32 [[A2]])
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if-false:
+; CHECK-NEXT:    [[REC2:%.*]] = call i32 @rec2(i1 true, i32 [[A2]])
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI_SAME:%.*]] = phi i32 [ [[REC1]], [[IF_TRUE]] ], [ [[REC2]], [[IF_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[PHI_SAME]]
+;
+  br i1 %c, label %if-true, label %if-false
+if-true:
+  %rec1 = call i32 @rec1(i1 %c, i32 %a2)
+  br label %end
+if-false:
+  %rec2 = call i32 @rec2(i1 true, i32 %a2)
+  br label %end
+end:
+  %phi-same = phi i32 [ %rec1, %if-true ], [ %rec2, %if-false ]
+  ret i32 %phi-same
+}
+
+define internal i32 @rec3(i1 %c, i32 %a3) {
+; CHECK-LABEL: define {{[^@]+}}@rec3
+; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A3:%.*]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if-true:
+; CHECK-NEXT:    [[REC2:%.*]] = call i32 @rec2(i1 [[C]], i32 [[A3]])
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if-false:
+; CHECK-NEXT:    [[REC3:%.*]] = call i32 @rec3(i1 true, i32 [[A3]])
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI_SAME:%.*]] = phi i32 [ [[REC2]], [[IF_TRUE]] ], [ [[REC3]], [[IF_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[PHI_SAME]]
+;
+  br i1 %c, label %if-true, label %if-false
+if-true:
+  %rec2 = call i32 @rec2(i1 %c, i32 %a3)
+  br label %end
+if-false:
+  %rec3 = call i32 @rec3(i1 true, i32 %a3)
+  br label %end
+end:
+  %phi-same = phi i32 [ %rec2, %if-true ], [ %rec3, %if-false ]
+  ret i32 %phi-same
+}
+
+define internal i32 @rec4(i1 %c, i32 %a4) {
+; CHECK-LABEL: define {{[^@]+}}@rec4
+; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A4:%.*]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if-true:
+; CHECK-NEXT:    [[REC3:%.*]] = call i32 @rec3(i1 [[C]], i32 [[A4]])
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if-false:
+; CHECK-NEXT:    [[REC4:%.*]] = call i32 @rec4(i1 true, i32 [[A4]])
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI_SAME:%.*]] = phi i32 [ [[REC3]], [[IF_TRUE]] ], [ [[REC4]], [[IF_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[PHI_SAME]]
+;
+  br i1 %c, label %if-true, label %if-false
+if-true:
+  %rec3 = call i32 @rec3(i1 %c, i32 %a4)
+  br label %end
+if-false:
+  %rec4 = call i32 @rec4(i1 true, i32 %a4)
+  br label %end
+end:
+  %phi-same = phi i32 [ %rec3, %if-true ], [ %rec4, %if-false ]
+  ret i32 %phi-same
+}
+
+define internal i32 @rec5(i1 %c, i32 %a5) {
+; CHECK-LABEL: define {{[^@]+}}@rec5
+; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A5:%.*]])
+; CHECK-NEXT:    br i1 [[C]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
+; CHECK:       if-true:
+; CHECK-NEXT:    [[REC4:%.*]] = call i32 @rec4(i1 [[C]], i32 [[A5]])
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if-false:
+; CHECK-NEXT:    [[REC5:%.*]] = call i32 @rec5(i1 true, i32 [[A5]])
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI_SAME:%.*]] = phi i32 [ [[REC4]], [[IF_TRUE]] ], [ [[REC5]], [[IF_FALSE]] ]
+; CHECK-NEXT:    ret i32 [[PHI_SAME]]
+;
+  br i1 %c, label %if-true, label %if-false
+if-true:
+  %rec4 = call i32 @rec4(i1 %c, i32 %a5)
+  br label %end
+if-false:
+  %rec5 = call i32 @rec5(i1 true, i32 %a5)
+  br label %end
+end:
+  %phi-same = phi i32 [ %rec4, %if-true ], [ %rec5, %if-false ]
+  ret i32 %phi-same
+}
+
+define i32 @rec_caller(i1 %c, i32 %a_init) {
+; CHECK-LABEL: define {{[^@]+}}@rec_caller
+; CHECK-SAME: (i1 [[C:%.*]], i32 returned [[A_INIT:%.*]])
+; CHECK-NEXT:    ret i32 [[A_INIT]]
+;
+  %call = call i32 @rec5(i1 %c, i32 %a_init)
+  ret i32 %call
+}
+
+define i32 @loop_no_const(i32 %N) {
+; CHECK-LABEL: define {{[^@]+}}@loop_no_const
+; CHECK-SAME: (i32 [[N:%.*]])
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[A_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[ADD]] = add nsw i32 [[A_0]], [[I_0]]
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i32 [[A_0]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %a.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %a.0, %i.0
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %a.0
+}
+
+define i32 @alternating_in_loop(i32 %N) {
+; CHECK-LABEL: define {{[^@]+}}@alternating_in_loop
+; CHECK-SAME: (i32 [[N:%.*]])
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[A_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; CHECK-NEXT:    [[A_0A:%.*]] = mul nsw i32 1, [[A_0]]
+; CHECK-NEXT:    [[A_0B:%.*]] = sub nsw i32 0, [[A_0A]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[SUB]] = sub nsw i32 1, [[A_0]]
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[A_0]], [[A_0B]]
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %a.0 = phi i32 [ 0, %entry ], [ %sub, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %a.0a = mul nsw i32 1, %a.0
+  %a.0b = sub nsw i32 0, %a.0a
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %sub = sub nsw i32 1, %a.0
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  %add = add i32 %a.0, %a.0b
+  ret i32 %add
+}
+
+define i32 @const_in_loop1(i32 %N) {
+; CHECK-LABEL: define {{[^@]+}}@const_in_loop1
+; CHECK-SAME: (i32 [[N:%.*]])
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[A_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 0, [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %a.0 = phi i32 [ 0, %entry ], [ %mul, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %mul = mul nsw i32 %a.0, %a.0
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %a.0
+}
+
+define i32 @const_in_loop2(i32 %N) {
+; CHECK-LABEL: define {{[^@]+}}@const_in_loop2
+; CHECK-SAME: (i32 [[N:%.*]])
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[A_0:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 1, [[FOR_INC:%.*]] ]
+; CHECK-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[I_0]], [[N]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br label [[FOR_INC]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret i32 1
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %a.0 = phi i32 [ 1, %entry ], [ %mul, %for.inc ]
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %cmp = icmp slt i32 %i.0, %N
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %mul = mul nsw i32 %a.0, %a.0
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %inc = add nsw i32 %i.0, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret i32 %a.0
+}
+>>>>>>> d2d3c463f81... [Attributor] Make value simplify stronger

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
 ;
 ; Test cases specifically designed for the "returned" argument attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 ;
 
 ; TEST SCC test returning an integer value argument
 ;
-;
 ; FNATTR: define i32 @sink_r0(i32 returned %r)
 ; FNATTR: define i32 @scc_r1(i32 %a, i32 %r, i32 %b)
 ; FNATTR: define i32 @scc_r2(i32 %a, i32 %b, i32 %r)
 ; FNATTR: define i32 @scc_rX(i32 %a, i32 %b, i32 %r)
 ;
 ;
 ; int scc_r1(int a, int b, int r);
 ; int scc_r2(int a, int b, int r);

llvm/test/Transforms/FunctionAttrs/nonnull.ll

 
 ; Local analysis, but going through a self recursive phi
 define i8* @test6a() {
 entry:
   %ret = call i8* @ret_nonnull()
   br label %loop
 loop:
   %phi = phi i8* [%ret, %entry], [%phi, %loop]
-  br i1 undef, label %loop, label %exit
+  br i1 false, label %loop, label %exit
 exit:
   ret i8* %phi
 }
 
 define i8* @test6b(i1 %c) {
 entry:
   %ret = call i8* @ret_nonnull()
   br label %loop