[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

struct AAValueSimplify : public StateWrapper<BooleanState, AbstractAttribute>,
 
   /// Return an IR position, see struct IRPosition.
   ///
   ///{
   IRPosition &getIRPosition() { return *this; }
   const IRPosition &getIRPosition() const { return *this; }
   ///}
 
-  /// 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;
+  /// Return the values assumed to be equivalent.
+  virtual const SmallSetVector<Value *, 4> &
+  getAssumedEquivalentValues() const = 0;
+
+  /// Return the constant assumed to be equivalent, if any.
+  virtual Constant *getAssumedEquivalentConstant() const = 0;
 
   /// 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;
 };

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/CaptureTracking.h"
 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
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;
-    CB.replaceAllUsesWith(&C);
-    return ChangeStatus::CHANGED;
-  };
-
   // If the assumed unique return value is an argument, annotate it.
   if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
     getIRPosition() = IRPosition::argument(*UniqueRVArg);
     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 =
-                ConstantExpr::getTruncOrBitCast(RVC, CB->getType());
-            Changed = ReplaceCallSiteUsersWith(*CB, *RVCCast) | Changed;
-          }
-    } else {
-      assert(isa<CallBase>(AnchorValue) &&
-             "Expcected a function or call base anchor!");
-      Constant *RVCCast =
-          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()) : "?") +
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 {
+    EquivalentValues.insert(&getAssociatedValue());
+    if (isa<Constant>(getAssociatedValue()))
+      indicateOptimisticFixpoint();
+  }
+
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
-    return getAssumed() ? (getKnown() ? "simplified" : "maybe-simple")
-                        : "not-simple";
+    return getAssumed()
+               ? "simplify(" + std::to_string(EquivalentValues.size()) + ")"
+               : "not-simplifiable";
   }
 
-  /// See AbstractAttribute::trackStatistics()
-  void trackStatistics() const override {}
+  /// See AAValueSimplify::getAssumedEquivalentValues()
+  const SmallSetVector<Value *, 4> &
+  getAssumedEquivalentValues() const override {
+    return EquivalentValues;
+  }
 
-  /// See AAValueSimplify::getAssumedSimplifiedValue()
-  Optional<Value *> getAssumedSimplifiedValue(Attributor &A) const override {
-    if (!getAssumed())
-      return const_cast<Value *>(&getAssociatedValue());
-    return SimplifiedAssociatedValue;
+  /// See AAValueSimplify::getAssumedEquivalentConstant()
+  Constant *getAssumedEquivalentConstant() const override {
+    return getAssumedEquivalentConstant(&getAssociatedValue());
   }
-  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.
+  /// 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)) {
+      EquivalentValues.insert(&V);
+      return true;
+    }
 
-    auto &ValueSimpifyAA = A.getAAFor<AAValueSimplify>(
-        QueryingAA, IRPosition::value(QueryingValue));
+    if (!VAA)
+        VAA = &A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V));
+    if (!VAA->isValidState())
+      return false;
+    EquivalentValues.set_union(VAA->getAssumedEquivalentValues());
+    return true;
+  }
 
-    Optional<Value *> QueryingValueSimplified =
-        ValueSimpifyAA.getAssumedSimplifiedValue(A);
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    // Limit the equivalent values to compatible ones.
+    if (!checkConsistency(A, /* IgnoreFixpoint */ true))
+      return ChangeStatus::UNCHANGED;
 
-    if (!QueryingValueSimplified.hasValue())
-      return true;
+    Value &OldValue = getAssociatedValue();
+    if (ImmutableCallSite ICS = ImmutableCallSite(OldValue.stripPointerCasts()))
+      if (ICS.isMustTailCall())
+        return ChangeStatus::UNCHANGED;
 
-    if (!QueryingValueSimplified.getValue())
-      return false;
+    Value *NewValue = getNewValue(&OldValue, getCtxI());
+    if (!NewValue)
+      return ChangeStatus::UNCHANGED;
 
-    Value &QueryingValueSimplifiedUnwrapped =
-        *QueryingValueSimplified.getValue();
+    DEBUG_WITH_TYPE("attributor-value-simplify",
+                    dbgs() << "[AAValueSimplify] Replace '" << OldValue
+                           << "' with '" << *NewValue << "'\n");
+    OldValue.replaceAllUsesWith(NewValue);
+    return ChangeStatus::CHANGED;
+  }
 
-    if (isa<UndefValue>(QueryingValueSimplifiedUnwrapped))
-      return true;
+  ChangeStatus indicatePessimisticFixpoint() override {
+    // We only know "optimistic" fixpoints for most AAValueSimplify
+    // instanciations. However, we revert to a known state if a pessimistic one
+    // is requested.
+    EquivalentValues.clear();
+    EquivalentValues.insert(&getAssociatedValue());
+    indicateOptimisticFixpoint();
+    return ChangeStatus::CHANGED;
+  }
 
-    if (AccumulatedSimplifiedValue.hasValue())
-      return AccumulatedSimplifiedValue == QueryingValueSimplified;
+protected:
 
-    LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << QueryingValue
-                      << " is assumed to be "
-                      << QueryingValueSimplifiedUnwrapped << "\n");
+  Constant *getAssumedEquivalentConstant(const Value *OldValue) const {
+    bool IsPtr = OldValue->getType()->isPointerTy();
 
-    AccumulatedSimplifiedValue = QueryingValueSimplified;
-    return true;
+    bool HasUndef = false;
+    // Constants are valid everywhere so we can deal with them first.
+    for (Value *EquivV : EquivalentValues)
+      if (auto *C = dyn_cast<Constant>(EquivV)) {
+        if (isa<UndefValue>(C)) {
+          HasUndef = true;
+          continue;
+        }
+        if (C->getType() == OldValue->getType())
+          return C;
+        if (IsPtr)
+          return ConstantExpr::getPointerCast(C, OldValue->getType());
+        // TODO: Deal with other casts
+        DEBUG_WITH_TYPE("attributor-value-simplify",
+                        dbgs() << "[AAValueSimplify] Equivalent constant '"
+                               << *C << "' needs complex cast.\n");
+      }
+
+    // If we only have undefs, we can use them.
+    if (HasUndef && EquivalentValues.size() == 1)
+      return UndefValue::get(OldValue->getType());
+    return nullptr;
   }
 
-  /// See AbstractAttribute::manifest(...).
-  ChangeStatus manifest(Attributor &A) override {
-    ChangeStatus Changed = ChangeStatus::UNCHANGED;
+  Value *getNewValue(Value *OldValue, Instruction *IP) {
+    DEBUG_WITH_TYPE("attributor-value-simplify",
+                    dbgs() << "[AAValueSimplify] Find new value for '"
+                           << *OldValue << "' @ "
+                           << (IP ? IP->getName() : "<none>") << "!\n");
+    // TODO IsDead query
+    if (OldValue->getNumUses() == 0)
+      return nullptr;
 
-    if (!SimplifiedAssociatedValue.hasValue() ||
-        !SimplifiedAssociatedValue.getValue())
-      return Changed;
-    Value &V = getAssociatedValue();
-    if (isa<Constant>(V))
-      return Changed;
+    if (isa<Constant>(OldValue)) {
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs() << "[AAValueSimplify] No new value necessary, '"
+                             << *OldValue << "' is a constant!\n");
+      return nullptr;
+    }
+
+    if (Constant *C = getAssumedEquivalentConstant(OldValue))
+      return C;
+
+    bool IsPtr = OldValue->getType()->isPointerTy();
+    for (Value *EquivV : EquivalentValues) {
+      // Do not replace a value "with itself".
+      if (OldValue == EquivV)
+        continue;
+      // Or with undef if we have other values.
+      // TODO: This is not necessarily an optimization but we go with it for
+      //       now and see if it helps or causes problems.
+      if (isa<UndefValue>(EquivV))
+        continue;
+
+      // Check if the simplified value is an instruction or argument in the same
+      // scope as the anchor.
+      if (canBeUsedInstead(*EquivV)) {
+        if (EquivV->getType() == OldValue->getType())
+          return EquivV;
+        if (!IP) {
+          DEBUG_WITH_TYPE("attributor-value-simplify",
+                          dbgs() << "[AAValueSimplify] EquivV '" << *EquivV
+                                 << "' needs cast but no position provided.\n");
+          continue;
+        }
+        if (IsPtr)
+          return new BitCastInst(EquivV, OldValue->getType(), ".cast", IP);
+        // TODO Deal with other casts
+        DEBUG_WITH_TYPE("attributor-value-simplify",
+                        dbgs() << "[AAValueSimplify] EquivV '" << *EquivV
+                               << "' needs complex cast.\n");
+      } else {
+        DEBUG_WITH_TYPE("attributor-value-simplify",
+                        dbgs() << "[AAValueSimplify] EquivV '" << *EquivV
+                               << "' not usable in scope.\n");
+      }
+    }
+
+    DEBUG_WITH_TYPE(
+        "attributor-value-simplify",
+        dbgs() << "[AAValueSimplify] No suitable new value found, looked at "
+               << EquivalentValues.size() << " candidates\n");
+    return nullptr;
+  }
 
-    if (auto *C = dyn_cast<Constant>(SimplifiedAssociatedValue.getValue())) {
-      // We can replace the AssociatedValue with the constant.
-      if (!V.user_empty() && &V != C && V.getType() == C->getType()) {
-        LLVM_DEBUG(dbgs() << "[Attributor][ValueSimplify] " << V << " -> " << *C
+  /// Verify the equivalent values are in a consistent state, that is there
+  /// might be an equivalence relation between all of them.
+  bool checkConsistency(Attributor &A, bool IgnoreFixpoint) {
+    DEBUG_WITH_TYPE("attributor-value-simplify",
+                    dbgs() << "[AAValueSimplify] Check consistency of "
+                           << static_cast<const AbstractAttribute &>(*this)
                            << "\n");
-        V.replaceAllUsesWith(C);
-        Changed = ChangeStatus::CHANGED;
+
+    if (EquivalentValues.size() < 2)
+      return true;
+
+    SmallPtrSet<Value *, 4> Copy;
+    Copy.insert(EquivalentValues.begin(), EquivalentValues.end());
+
+    for (Value *V : EquivalentValues) {
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs() << "[AAValueSimplify] - " << *V
+                             << " | #EV : " << Copy.size() << "\n");
+      if (V == &getAssociatedValue())
+        continue;
+
+      if (isa<Constant>(V)) {
+        if (isa<UndefValue>(V))
+          continue;
+
+        if (!Copy.count(V)) {
+          DEBUG_WITH_TYPE("attributor-value-simplify",
+                          dbgs() << "[AAValueSimplify] Constant EquivVal " << *V
+                                 << " not present anymore!\n");
+          return false;
+        }
+        Copy.clear();
+        Copy.insert(V);
+        continue;
       }
+
+      auto &VAA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(*V));
+      if (!VAA.isValidState())
+        return false;
+      if (!IgnoreFixpoint && !VAA.isAtFixpoint())
+        continue;
+
+      const auto &VEquivVals = VAA.getAssumedEquivalentValues();
+      DEBUG_WITH_TYPE("attributor-value-simplify",
+                      dbgs() << "[AAValueSimplify] - " << *V
+                             << " is equivalent to " << VEquivVals.size()
+                             << " values -> intersection\n");
+      set_intersect(Copy, VEquivVals);
     }
 
-    return Changed | AAValueSimplify::manifest(A);
+    DEBUG_WITH_TYPE("attributor-value-simplify",
+                    dbgs() << "[AAValueSimplify] Consistency result: "
+                           << Copy.size() << " of " << EquivalentValues.size()
+                           << "\n";);
+    return !Copy.empty();
   }
 
-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;
+  /// Returns true if \p NewValue can be used in the scope of this AA.
+  bool canBeUsedInstead(Value &NewValue) const {
+    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: Dominacne test! */ false;
+
+    if (auto *NewArg = dyn_cast<Argument>(&NewValue))
+      return NewArg->getParent() == IRP.getAnchorScope();
+
+    return false;
+  }
+
+  /// Values equivalent to the one represented by the AA.
+  SmallSetVector<Value *, 4> EquivalentValues;
 };
 
 struct AAValueSimplifyArgument final : AAValueSimplifyImpl {
   AAValueSimplifyArgument(const IRPosition &IRP) : AAValueSimplifyImpl(IRP) {}
 
+  void initialize(Attributor &A) override {
+    AAValueSimplifyImpl::initialize(A);
+    if (!getAssociatedFunction() || getAssociatedFunction()->isDeclaration())
+      indicatePessimisticFixpoint();
+  }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
-    bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
+    decltype(EquivalentValues) OldEquivalentValues = EquivalentValues;
+    EquivalentValues.clear();
 
     auto PredForCallSite = [&](AbstractCallSite ACS) {
       // Check if we have an associated argument or not (which can happen for
       // callback calls).
-      if (Value *ArgOp = ACS.getCallArgOperand(getArgNo()))
-        return checkAndUpdate(A, *this, *ArgOp, SimplifiedAssociatedValue);
+      Value *ArgOp = ACS.getCallArgOperand(getArgNo());
+      if (!ArgOp)
         return false;
+      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 candicates were found in this update, return UNCHANGED.
+    if (OldEquivalentValues == EquivalentValues)
+      return ChangeStatus::UNCHANGED;
+
+    // Limit the equivalent values to compatible ones.
+    if (!checkConsistency(A, /* IgnoreFixpoint */ false))
+      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 {}
+
+  ChangeStatus indicatePessimisticFixpoint() override {
+    // Because there is no "return value" we cannot fall back to anything known
+    // and need to indicate an invalid state instead.
+    EquivalentValues.clear();
+    return AAValueSimplify::indicatePessimisticFixpoint();
+  }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
-    bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
-
-    auto PredForReturned = [&](Value &V) {
-      return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
-    };
+    decltype(EquivalentValues) OldEquivalentValues = EquivalentValues;
+    EquivalentValues.clear();
 
+    auto PredForReturned = [&](Value &V) { return recurseAndCombined(A, V); };
     if (!A.checkForAllReturnedValues(PredForReturned, *this))
       return indicatePessimisticFixpoint();
 
-    // If a candicate was found in this update, return CHANGED.
-    return HasValueBefore == SimplifiedAssociatedValue.hasValue()
-               ? ChangeStatus::UNCHANGED
-               : ChangeStatus ::CHANGED;
+    // If no new candicates were found in this update, return UNCHANGED.
+    if (OldEquivalentValues == EquivalentValues)
+      return ChangeStatus::UNCHANGED;
+
+    // Limit the equivalent values to compatible ones.
+    if (!checkConsistency(A, /* IgnoreFixpoint */ false))
+      return indicatePessimisticFixpoint();
+
+    return ChangeStatus ::CHANGED;
+  }
+
+  /// See AbstractAttribute::manifest(...).
+  ChangeStatus manifest(Attributor &A) override {
+    // Limit the equivalent values to compatible ones.
+    if (!checkConsistency(A, /* IgnoreFixpoint */ true))
+      return ChangeStatus::UNCHANGED;
+
+    Function *AssociatedFunction = getAssociatedFunction();
+    ChangeStatus Changed = ChangeStatus::UNCHANGED;
+    auto RetValRepl = [&](Value &V,
+                          const SmallSetVector<ReturnInst *, 4> &ReturnInsts) {
+      for (ReturnInst *RI : ReturnInsts) {
+        if (RI->getFunction() != AssociatedFunction)
+          continue;
+        Value *OldValue = RI->getOperand(0);
+        if (ImmutableCallSite ICS = ImmutableCallSite(OldValue->stripPointerCasts()))
+          if (ICS.isMustTailCall())
+            continue;
+        Value *NewValue = getNewValue(OldValue, RI);
+        if (!NewValue)
+          continue;
+        DEBUG_WITH_TYPE("attributor-value-simplify",
+                        dbgs() << "[AAValueSimplify] Replace '" << OldValue
+                               << "' with '" << *NewValue << "' in " << *RI
+                               << "\n");
+        RI->setOperand(0, NewValue);
+        Changed = ChangeStatus::CHANGED;
+      }
+      return true;
+    };
+
+    A.checkForAllReturnedValuesAndReturnInsts(RetValRepl, *this);
+
+    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();
-
-    // TODO: add other stuffs
-    if (isa<Constant>(V) || isa<UndefValue>(V))
-      indicatePessimisticFixpoint();
+    if (isa<Constant>(getAssociatedValue()))
+      indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
-    bool HasValueBefore = SimplifiedAssociatedValue.hasValue();
+    decltype(EquivalentValues) OldEquivalentValues = EquivalentValues;
+    EquivalentValues.clear();
+
+    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 (VAA.isValidState())
+        if (Constant *COp = VAA.getAssumedEquivalentConstant())
+          return COp;
+      AllConst = false;
+      return nullptr;
+    };
 
     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();
+      auto &VAA = A.getAAFor<AAValueSimplify>(*this, IRPosition::value(V));
+      if (!VAA.isValidState())
         return false;
+      if (Stripped || this != &VAA)
+        return recurseAndCombined(A, V, &VAA);
+
+      EquivalentValues.insert(&V);
+
+      Instruction *I = dyn_cast<Instruction>(&V);
+      if (!I)
+        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));
+
+      Value *Repl = nullptr;
+      if (AllConst)
+        Repl = ConstantFoldInstOperands(I, COps, A.getDataLayout());
+      else {
+        switch (I->getOpcode()) {
+        case Instruction::Select:
+          if (COps[0])
+            Repl = COps[0]->isNullValue() ? I->getOperand(1) : I->getOperand(0);
+          break;
+        default:
+          // TODO: Check if we can reuse some logic or have to write our own
+          // for partially constant values.
+          break;
+        };
       }
-      return checkAndUpdate(A, *this, V, SimplifiedAssociatedValue);
+      DEBUG_WITH_TYPE("attributor-value-simplify", {
+        if (Repl)
+          dbgs() << "[AAValueSimplify] Folding successful: " << *Repl << "\n";
+      });
+
+      if (Repl)
+        EquivalentValues.insert(Repl);
+      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 candicates were found in this update, return UNCHANGED.
+    if (OldEquivalentValues == EquivalentValues)
+      return ChangeStatus::UNCHANGED;
 
-    return HasValueBefore == SimplifiedAssociatedValue.hasValue()
-               ? ChangeStatus::UNCHANGED
-               : ChangeStatus ::CHANGED;
+    // Limit the equivalent values to compatible ones.
+    if (!checkConsistency(A, /* IgnoreFixpoint */ false))
+      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(...).
+  void initialize(Attributor &A) override { indicateOptimisticFixpoint(); }
+
+  /// 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 {
+    decltype(EquivalentValues) OldEquivalentValues = EquivalentValues;
+    EquivalentValues.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);
+    if (!FnRetAA.isValidState())
+      return indicatePessimisticFixpoint();
+
+    // Copy equivalent values over but translate arguments of the callee to call
+    // site operands instead.
+    auto *CB = cast<CallBase>(getCtxI());
+    for (Value *EquivV : FnRetAA.getAssumedEquivalentValues()) {
+      if (auto *Arg = dyn_cast<Argument>(EquivV)) {
+        if (Arg->getParent() == CB->getCalledFunction()) {
+          if (!recurseAndCombined(A, *CB->getArgOperand(Arg->getArgNo())))
+            return indicatePessimisticFixpoint();
+          continue;
+        }
+      }
+      EquivalentValues.insert(EquivV);
+    }
+
+    // If no new candicates were found in this update, return UNCHANGED.
+    if (OldEquivalentValues == EquivalentValues)
+      return ChangeStatus::UNCHANGED;
+
+    // Limit the equivalent values to compatible ones.
+    if (!checkConsistency(A, /* IgnoreFixpoint */ false))
+      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) {}
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.
void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   auto CallSitePred = [&](Instruction &I) -> bool {
     CallSite CS(&I);
     if (Function *Callee = CS.getCalledFunction()) {
       if (!Callee->getReturnType()->isVoidTy()) {
         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/FunctionAttrs/arg_nocapture.ll

-; RUN: opt -functionattrs -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=10 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=11 -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-capture" argument attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; TEST comparison against NULL
 ;

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 ; RUN: opt -attributor -attributor-manifest-internal -attributor-disable=false -functionattrs -S < %s | FileCheck %s --check-prefix=BOTH
 ;
 ; 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
 ;

 }
 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
+; ATTRIBUTOR:  %c4 = load i32, i32* %a
   %c4 = load i32, i32* %c3
 ; FIXME: %c2 and %c3 should be replaced but not %c0 or %c1!
 ; 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/FunctionAttrs/value-simplify.ll

-; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s
-; TODO: Add max-iteration check
-; ModuleID = 'value-simplify.ll'
-source_filename = "value-simplify.ll"
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=15 < %s | FileCheck %s
 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:    [[CALL:%.*]] = tail call i32 @return0()
+; CHECK-NEXT:    [[RET0:%.*]] = add i32 0, 1
+; CHECK-NEXT:    br label [[END:%.*]]
+; CHECK:       if.false:
+; CHECK-NEXT:    [[RET1:%.*]] = tail call i32 @return1()
+; 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:%.*]] = tail call i32 @test2_1(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:    [[RET1:%.*]] = tail call i32 @return1()
+; 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:    [[SELECT_SAME:%.*]] = select i1 [[C]], i32 1, i32 1
+; 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 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:    [[CALL:%.*]] = call i32 @rec5(i1 [[C]], i32 [[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:    [[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:    ret i32 [[A_0]]
+;
+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 ]
+  %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
+  ret i32 %a.0
+}
+
+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:    [[MUL:%.*]] = mul nsw i32 0, 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 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:    [[MUL:%.*]] = mul nsw i32 1, 1
+; 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
+}

llvm/test/Transforms/FunctionAttrs/willreturn.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=4 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases specifically designed for the "willreturn" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.