[Attributor] Make liveness "edge-based"

Summary:
If control is transferred to a successor is the key question when it
comes to liveness. The new implementation puts that question in the
focus and thereby providing a clean way to assume certain CFG edges are
dead or instructions will not transfer control.

Reviewers: sstefan1, uenoku

Subscribers: hiraditya, bollu, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D69605

10 files changed, 280 insertions, 145 deletions

diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp
index e18e4ccefc7..899944a65c3 100644
--- a/llvm/lib/Transforms/IPO/Attributor.cpp
+++ b/llvm/lib/Transforms/IPO/Attributor.cpp
@@ -2166,8 +2166,8 @@ struct AAIsDeadFloating : public AAIsDeadValueImpl {
     Value &V = getAssociatedValue();
     if (auto *I = dyn_cast<Instruction>(&V))
       if (wouldInstructionBeTriviallyDead(I)) {
-          A.deleteAfterManifest(*I);
-          return ChangeStatus::CHANGED;
+        A.deleteAfterManifest(*I);
+        return ChangeStatus::CHANGED;
       }
 
     if (V.use_empty())
@@ -2295,37 +2295,17 @@ struct AAIsDeadFunction : public AAIsDead {
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     const Function *F = getAssociatedFunction();
-    if (F && !F->isDeclaration())
-      exploreFromEntry(A, F);
-  }
-
-  void exploreFromEntry(Attributor &A, const Function *F) {
-    ToBeExploredPaths.insert(&(F->getEntryBlock().front()));
-
-    for (size_t i = 0; i < ToBeExploredPaths.size(); ++i)
-      if (const Instruction *NextNoReturnI =
-              findNextNoReturn(A, ToBeExploredPaths[i]))
-        NoReturnCalls.insert(NextNoReturnI);
-
-    // Mark the block live after we looked for no-return instructions.
-    assumeLive(A, F->getEntryBlock());
+    if (F && !F->isDeclaration()) {
+      ToBeExploredFrom.insert(&F->getEntryBlock().front());
+      assumeLive(A, F->getEntryBlock());
+    }
   }
 
-  /// Find the next assumed noreturn instruction in the block of \p I starting
-  /// from, thus including, \p I.
-  ///
-  /// The caller is responsible to monitor the ToBeExploredPaths set as new
-  /// instructions discovered in other basic block will be placed in there.
-  ///
-  /// \returns The next assumed noreturn instructions in the block of \p I
-  ///          starting from, thus including, \p I.
-  const Instruction *findNextNoReturn(Attributor &A, const Instruction *I);
-
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" +
-           std::to_string(getAssociatedFunction()->size()) + "][#NRI " +
-           std::to_string(NoReturnCalls.size()) + "]";
+           std::to_string(getAssociatedFunction()->size()) + "][#TBEP " +
+           std::to_string(ToBeExploredFrom.size()) + "]";
   }
 
   /// See AbstractAttribute::manifest(...).
@@ -2346,8 +2326,15 @@ struct AAIsDeadFunction : public AAIsDead {
     // function allows to catch asynchronous exceptions.
     bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
 
-    for (const Instruction *NRC : NoReturnCalls) {
-      Instruction *I = const_cast<Instruction *>(NRC);
+    for (const Instruction *ExploreEndI : ToBeExploredFrom) {
+      auto *CB = dyn_cast<CallBase>(ExploreEndI);
+      if (!CB)
+        continue;
+      const auto &NoReturnAA =
+          A.getAAFor<AANoReturn>(*this, IRPosition::callsite_function(*CB));
+      if (!NoReturnAA.isAssumedNoReturn())
+        continue;
+      Instruction *I = const_cast<Instruction *>(ExploreEndI);
       BasicBlock *BB = I->getParent();
       Instruction *SplitPos = I->getNextNode();
       // TODO: mark stuff before unreachable instructions as dead.
@@ -2460,8 +2447,14 @@ struct AAIsDeadFunction : public AAIsDead {
     if (!AssumedLiveBlocks.count(I->getParent()))
       return true;
 
-    // If it is not after a noreturn call, than it is live.
-    return isAfterNoReturn(I);
+    // If it is not after a liveness barrier it is live.
+    const Instruction *PrevI = I->getPrevNode();
+    while (PrevI) {
+      if (ToBeExploredFrom.count(PrevI))
+        return true;
+      PrevI = PrevI->getPrevNode();
+    }
+    return false;
   }
 
   /// See AAIsDead::isKnownDead(Instruction *I).
@@ -2469,9 +2462,6 @@ struct AAIsDeadFunction : public AAIsDead {
     return getKnown() && isAssumedDead(I);
   }
 
-  /// Check if instruction is after noreturn call, in other words, assumed dead.
-  bool isAfterNoReturn(const Instruction *I) const;
-
   /// Determine if \p F might catch asynchronous exceptions.
   static bool mayCatchAsynchronousExceptions(const Function &F) {
     return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F);
@@ -2479,9 +2469,9 @@ struct AAIsDeadFunction : public AAIsDead {
 
   /// Assume \p BB is (partially) live now and indicate to the Attributor \p A
   /// that internal function called from \p BB should now be looked at.
-  void assumeLive(Attributor &A, const BasicBlock &BB) {
+  bool assumeLive(Attributor &A, const BasicBlock &BB) {
     if (!AssumedLiveBlocks.insert(&BB).second)
-      return;
+      return false;
 
     // We assume that all of BB is (probably) live now and if there are calls to
     // internal functions we will assume that those are now live as well. This
@@ -2492,124 +2482,194 @@ struct AAIsDeadFunction : public AAIsDead {
         if (const Function *F = ICS.getCalledFunction())
           if (F->hasLocalLinkage())
             A.markLiveInternalFunction(*F);
+    return true;
   }
 
-  /// Collection of to be explored paths.
-  SmallSetVector<const Instruction *, 8> ToBeExploredPaths;
+  /// Collection of instructions that need to be explored again, e.g., we
+  /// did assume they do not transfer control to (one of their) successors.
+  SmallSetVector<const Instruction *, 8> ToBeExploredFrom;
 
   /// Collection of all assumed live BasicBlocks.
   DenseSet<const BasicBlock *> AssumedLiveBlocks;
-
-  /// Collection of calls with noreturn attribute, assumed or knwon.
-  SmallSetVector<const Instruction *, 4> NoReturnCalls;
 };
 
-bool AAIsDeadFunction::isAfterNoReturn(const Instruction *I) const {
-  const Instruction *PrevI = I->getPrevNode();
-  while (PrevI) {
-    if (NoReturnCalls.count(PrevI))
-      return true;
-    PrevI = PrevI->getPrevNode();
-  }
+static bool
+identifyAliveSuccessors(Attributor &A, const CallBase &CB,
+                        AbstractAttribute &AA,
+                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
+  const IRPosition &IPos = IRPosition::callsite_function(CB);
+
+  const auto &NoReturnAA = A.getAAFor<AANoReturn>(AA, IPos);
+  if (NoReturnAA.isAssumedNoReturn())
+    return true;
+  if (CB.isTerminator())
+    AliveSuccessors.push_back(&CB.getSuccessor(0)->front());
+  else
+    AliveSuccessors.push_back(CB.getNextNode());
   return false;
 }
 
-const Instruction *AAIsDeadFunction::findNextNoReturn(Attributor &A,
-                                                      const Instruction *I) {
-  const BasicBlock *BB = I->getParent();
-  const Function &F = *BB->getParent();
-
-  // Flag to determine if we can change an invoke to a call assuming the callee
-  // is nounwind. This is not possible if the personality of the function allows
-  // to catch asynchronous exceptions.
-  bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
-
-  // TODO: We should have a function that determines if an "edge" is dead.
-  //       Edges could be from an instruction to the next or from a terminator
-  //       to the successor. For now, we need to special case the unwind block
-  //       of InvokeInst below.
-
-  while (I) {
-    ImmutableCallSite ICS(I);
-
-    if (ICS) {
-      const IRPosition &IPos = IRPosition::callsite_function(ICS);
-      // Regarless of the no-return property of an invoke instruction we only
-      // learn that the regular successor is not reachable through this
-      // instruction but the unwind block might still be.
-      if (auto *Invoke = dyn_cast<InvokeInst>(I)) {
-        // Use nounwind to justify the unwind block is dead as well.
-        const auto &AANoUnw = A.getAAFor<AANoUnwind>(*this, IPos);
-        if (!Invoke2CallAllowed || !AANoUnw.isAssumedNoUnwind()) {
-          assumeLive(A, *Invoke->getUnwindDest());
-          ToBeExploredPaths.insert(&Invoke->getUnwindDest()->front());
-        }
-      }
-
-      const auto &NoReturnAA = A.getAAFor<AANoReturn>(*this, IPos);
-      if (NoReturnAA.isAssumedNoReturn())
-        return I;
+static bool
+identifyAliveSuccessors(Attributor &A, const InvokeInst &II,
+                        AbstractAttribute &AA,
+                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
+  bool UsedAssumedInformation =
+      identifyAliveSuccessors(A, cast<CallBase>(II), AA, AliveSuccessors);
+
+  // First, determine if we can change an invoke to a call assuming the
+  // callee is nounwind. This is not possible if the personality of the
+  // function allows to catch asynchronous exceptions.
+  if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*II.getFunction())) {
+    AliveSuccessors.push_back(&II.getUnwindDest()->front());
+  } else {
+    const IRPosition &IPos = IRPosition::callsite_function(II);
+    const auto &AANoUnw = A.getAAFor<AANoUnwind>(AA, IPos);
+    if (!AANoUnw.isAssumedNoUnwind()) {
+      AliveSuccessors.push_back(&II.getUnwindDest()->front());
+      UsedAssumedInformation = true;
     }
-
-    I = I->getNextNode();
   }
+  return UsedAssumedInformation;
+}
+
+static Optional<ConstantInt *> getAssumedConstant(Attributor &A, const Value &V,
+                                                  AbstractAttribute &AA) {
+  const auto &ValueSimplifyAA =
+      A.getAAFor<AAValueSimplify>(AA, IRPosition::value(V));
+  Optional<Value *> SimplifiedV = ValueSimplifyAA.getAssumedSimplifiedValue(A);
+  if (!SimplifiedV.hasValue())
+    return llvm::None;
+  if (isa_and_nonnull<UndefValue>(SimplifiedV.getValue()))
+    return llvm::None;
+  return dyn_cast_or_null<ConstantInt>(SimplifiedV.getValue());
+}
 
-  // get new paths (reachable blocks).
-  for (const BasicBlock *SuccBB : successors(BB)) {
-    assumeLive(A, *SuccBB);
-    ToBeExploredPaths.insert(&SuccBB->front());
+static bool
+identifyAliveSuccessors(Attributor &A, const BranchInst &BI,
+                        AbstractAttribute &AA,
+                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
+  bool UsedAssumedInformation = false;
+  if (BI.getNumSuccessors() == 1) {
+    AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
+  } else {
+    Optional<ConstantInt *> CI = getAssumedConstant(A, *BI.getCondition(), AA);
+    if (!CI.hasValue()) {
+      // No value yet, assume both edges are dead.
+    } else if (CI.getValue()) {
+      const BasicBlock *SuccBB =
+          BI.getSuccessor(1 - CI.getValue()->getZExtValue());
+      AliveSuccessors.push_back(&SuccBB->front());
+      UsedAssumedInformation = true;
+    } else {
+      AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
+      AliveSuccessors.push_back(&BI.getSuccessor(1)->front());
+    }
   }
+  return UsedAssumedInformation;
+}
 
-  // No noreturn instruction found.
-  return nullptr;
+static bool
+identifyAliveSuccessors(Attributor &A, const SwitchInst &SI,
+                        AbstractAttribute &AA,
+                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
+  bool UsedAssumedInformation = false;
+    Optional<ConstantInt *> CI = getAssumedConstant(A, *SI.getCondition(), AA);
+  if (!CI.hasValue()) {
+    // No value yet, assume all edges are dead.
+  } else if (CI.getValue()) {
+    for (auto &CaseIt : SI.cases()) {
+      if (CaseIt.getCaseValue() == CI.getValue()) {
+        AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front());
+        UsedAssumedInformation = true;
+        break;
+      }
+    }
+  } else {
+    for (const BasicBlock *SuccBB : successors(SI.getParent()))
+      AliveSuccessors.push_back(&SuccBB->front());
+  }
+  return UsedAssumedInformation;
 }
 
 ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
-  ChangeStatus Status = ChangeStatus::UNCHANGED;
+  ChangeStatus Change = ChangeStatus::UNCHANGED;
 
-  // Temporary collection to iterate over existing noreturn instructions. This
-  // will alow easier modification of NoReturnCalls collection
-  SmallVector<const Instruction *, 8> NoReturnChanged;
+  LLVM_DEBUG(dbgs() << "[AAIsDead] Live [" << AssumedLiveBlocks.size() << "/"
+                    << getAssociatedFunction()->size() << "] BBs and "
+                    << ToBeExploredFrom.size() << " exploration points\n");
 
-  for (const Instruction *I : NoReturnCalls)
-    NoReturnChanged.push_back(I);
+  // Copy and clear the list of instructions we need to explore from. It is
+  // refilled with instructions the next update has to look at.
+  SmallVector<const Instruction *, 8> Worklist(ToBeExploredFrom.begin(),
+                                               ToBeExploredFrom.end());
+  decltype(ToBeExploredFrom) NewToBeExploredFrom;
+
+  SmallVector<const Instruction *, 8> AliveSuccessors;
+  while (!Worklist.empty()) {
+    const Instruction *I = Worklist.pop_back_val();
+    LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n");
 
-  for (const Instruction *I : NoReturnChanged) {
-    size_t Size = ToBeExploredPaths.size();
+    AliveSuccessors.clear();
 
-    const Instruction *NextNoReturnI = findNextNoReturn(A, I);
-    if (NextNoReturnI != I) {
-      Status = ChangeStatus::CHANGED;
-      NoReturnCalls.remove(I);
-      if (NextNoReturnI)
-        NoReturnCalls.insert(NextNoReturnI);
+    bool UsedAssumedInformation = false;
+    switch (I->getOpcode()) {
+    // TODO: look for (assumed) UB to backwards propagate "deadness".
+    default:
+      if (I->isTerminator()) {
+        for (const BasicBlock *SuccBB : successors(I->getParent()))
+          AliveSuccessors.push_back(&SuccBB->front());
+      } else {
+        AliveSuccessors.push_back(I->getNextNode());
+      }
+      break;
+    case Instruction::Call:
+      UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I),
+                                                       *this, AliveSuccessors);
+      break;
+    case Instruction::Invoke:
+      UsedAssumedInformation = identifyAliveSuccessors(A, cast<InvokeInst>(*I),
+                                                       *this, AliveSuccessors);
+      break;
+    case Instruction::Br:
+      UsedAssumedInformation = identifyAliveSuccessors(A, cast<BranchInst>(*I),
+                                                       *this, AliveSuccessors);
+      break;
+    case Instruction::Switch:
+      UsedAssumedInformation = identifyAliveSuccessors(A, cast<SwitchInst>(*I),
+                                                       *this, AliveSuccessors);
+      break;
     }
 
-    // Explore new paths.
-    while (Size != ToBeExploredPaths.size()) {
-      Status = ChangeStatus::CHANGED;
-      if (const Instruction *NextNoReturnI =
-              findNextNoReturn(A, ToBeExploredPaths[Size++]))
-        NoReturnCalls.insert(NextNoReturnI);
+    if (UsedAssumedInformation)
+      NewToBeExploredFrom.insert(I);
+    else
+      Change = ChangeStatus::CHANGED;
+
+    LLVM_DEBUG(dbgs() << "[AAIsDead] #AliveSuccessors: "
+                      << AliveSuccessors.size() << " UsedAssumedInformation: "
+                      << UsedAssumedInformation << "\n");
+
+    for (const Instruction *AliveSuccessor : AliveSuccessors) {
+      if (!I->isTerminator()) {
+        assert(AliveSuccessors.size() == 1 &&
+               "Non-terminator expected to have a single successor!");
+        Worklist.push_back(AliveSuccessor);
+      } else {
+        if (assumeLive(A, *AliveSuccessor->getParent()))
+          Worklist.push_back(AliveSuccessor);
+      }
     }
   }
 
-  LLVM_DEBUG(dbgs() << "[AAIsDead] AssumedLiveBlocks: "
-                    << AssumedLiveBlocks.size() << " Total number of blocks: "
-                    << getAssociatedFunction()->size() << "\n");
+  ToBeExploredFrom = std::move(NewToBeExploredFrom);
 
   // If we know everything is live there is no need to query for liveness.
-  if (NoReturnCalls.empty() &&
-      getAssociatedFunction()->size() == AssumedLiveBlocks.size()) {
-    // Indicating a pessimistic fixpoint will cause the state to be "invalid"
-    // which will cause the Attributor to not return the AAIsDead on request,
-    // which will prevent us from querying isAssumedDead().
-    indicatePessimisticFixpoint();
-    assert(!isValidState() && "Expected an invalid state!");
-    Status = ChangeStatus::CHANGED;
-  }
-
-  return Status;
+  // Instead, indicating a pessimistic fixpoint will cause the state to be
+  // "invalid" and all queries to be answered conservatively.
+  if (ToBeExploredFrom.empty() &&
+      getAssociatedFunction()->size() == AssumedLiveBlocks.size())
+    return indicatePessimisticFixpoint();
+  return Change;
 }
 
 /// Liveness information for a call sites.
diff --git a/llvm/test/Transforms/FunctionAttrs/align.ll b/llvm/test/Transforms/FunctionAttrs/align.ll
index f4cb54289ca..aa1197c7931 100644
--- a/llvm/test/Transforms/FunctionAttrs/align.ll
+++ b/llvm/test/Transforms/FunctionAttrs/align.ll
@@ -1,5 +1,5 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; 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
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll
index cb598180bc2..021c4df533e 100644
--- a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll
+++ b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll
@@ -1,4 +1,4 @@
-; 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=6 -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-capture" argument attribute.
 ; We use FIXME's to indicate problems and missing attributes.
diff --git a/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll b/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll
index b9139c5571a..7ba16a15f75 100644
--- a/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll
+++ b/llvm/test/Transforms/FunctionAttrs/fn_noreturn.ll
@@ -1,4 +1,4 @@
-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
 ;
 ; Test cases specifically designed for the "no-return" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.
diff --git a/llvm/test/Transforms/FunctionAttrs/internal-noalias.ll b/llvm/test/Transforms/FunctionAttrs/internal-noalias.ll
index 30667ef13f6..9b340442711 100644
--- a/llvm/test/Transforms/FunctionAttrs/internal-noalias.ll
+++ b/llvm/test/Transforms/FunctionAttrs/internal-noalias.ll
@@ -1,4 +1,4 @@
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 
 define dso_local i32 @visible(i32* noalias %A, i32* noalias %B) #0 {
 entry:
diff --git a/llvm/test/Transforms/FunctionAttrs/liveness.ll b/llvm/test/Transforms/FunctionAttrs/liveness.ll
index cde910f2c2e..b62f81b4873 100644
--- a/llvm/test/Transforms/FunctionAttrs/liveness.ll
+++ b/llvm/test/Transforms/FunctionAttrs/liveness.ll
@@ -1,4 +1,5 @@
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=5 -S < %s | FileCheck %s
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=6 -S < %s | FileCheck %s
 
 declare void @no_return_call() nofree noreturn nounwind readnone
 
@@ -687,19 +688,19 @@ define void @live_with_dead_entry_lp() personality i8* bitcast (i32 (...)* @__gx
 ; CHECK:      define void @live_with_dead_entry_lp(
 ; CHECK-NEXT: entry:
 ; CHECK-NEXT:   invoke void @blowup()
-; CHECK-NEXT:           to label %live_with_dead_entry.dead unwind label %lp1
+; CHECK-NEXT:           to label %live_with_dead_entry.dead1 unwind label %lp1
 ; CHECK:      lp1:                                              ; preds = %entry
 ; CHECK-NEXT:   %lp = landingpad { i8*, i32 }
 ; CHECK-NEXT:           catch i8* null
 ; CHECK-NEXT:   invoke void @blowup()
-; CHECK-NEXT:           to label %live_with_dead_entry.dead1 unwind label %lp2
+; CHECK-NEXT:           to label %live_with_dead_entry.dead unwind label %lp2
 ; CHECK:      lp2:                                              ; preds = %lp1
 ; CHECK-NEXT:   %0 = landingpad { i8*, i32 }
 ; CHECK-NEXT:           catch i8* null
 ; CHECK-NEXT:   br label %live_with_dead_entry
-; CHECK:      live_with_dead_entry.dead:                        ; preds = %entry
+; CHECK:      live_with_dead_entry.dead:
 ; CHECK-NEXT:   unreachable
-; CHECK:      live_with_dead_entry.dead1:                       ; preds = %lp1
+; CHECK:      live_with_dead_entry.dead1:
 ; CHECK-NEXT:   unreachable
 ; CHECK:      live_with_dead_entry:                             ; preds = %lp2
 ; CHECK-NEXT:   ret void
diff --git a/llvm/test/Transforms/FunctionAttrs/nonnull.ll b/llvm/test/Transforms/FunctionAttrs/nonnull.ll
index 7e766da9d07..07c40e7d8ef 100644
--- a/llvm/test/Transforms/FunctionAttrs/nonnull.ll
+++ b/llvm/test/Transforms/FunctionAttrs/nonnull.ll
@@ -1,7 +1,8 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR
-; RUN: opt -S -passes=function-attrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=8 -S < %s | FileCheck %s --check-prefixes=BOTH,ATTRIBUTOR
+; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR,OLD
+; RUN: opt -S -passes=function-attrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR,OLD
+; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefixes=BOTH,OLD,ATTRIBUTOR,ATTRIBUTOR_OPM
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=7 -S < %s | FileCheck %s --check-prefixes=BOTH,ATTRIBUTOR,ATTRIBUTOR_NPM
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
@@ -195,16 +196,17 @@ bb4:                                              ; preds = %bb1
   %tmp5 = getelementptr inbounds i32, i32* %arg, i64 1
 ; ATTRIBUTOR: %tmp5b = tail call i32* @f3(i32* nonnull %tmp5)
   %tmp5b = tail call i32* @f3(i32* %tmp5)
+  %tmp5c = getelementptr inbounds i32, i32* %tmp5b, i64 -1
   br label %bb9
 
 bb6:                                              ; preds = %bb1
 ; FIXME: missing nonnull. It should be @f2(i32* nonnull %arg)
-; ATTRIBUTOR: %tmp7 = tail call nonnull i32* @f2(i32* readonly %arg)
+; ATTRIBUTOR: %tmp7 = tail call nonnull i32* @f2(i32* %arg)
   %tmp7 = tail call i32* @f2(i32* %arg)
   ret i32* %tmp7
 
 bb9:                                              ; preds = %bb4, %bb
-  %tmp10 = phi i32* [ %tmp5, %bb4 ], [ inttoptr (i64 4 to i32*), %bb ]
+  %tmp10 = phi i32* [ %tmp5c, %bb4 ], [ inttoptr (i64 4 to i32*), %bb ]
   ret i32* %tmp10
 }
 
@@ -214,7 +216,7 @@ define internal i32* @f2(i32* %arg) {
 bb:
 
 ; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg)
-; ATTRIBUTOR:   %tmp = tail call nonnull i32* @f1(i32* readonly %arg)
+; ATTRIBUTOR:   %tmp = tail call nonnull i32* @f1(i32* %arg)
   %tmp = tail call i32* @f1(i32* %arg)
   ret i32* %tmp
 }
@@ -224,7 +226,7 @@ define dso_local noalias i32* @f3(i32* %arg) {
 ; ATTRIBUTOR: define dso_local noalias nonnull i32* @f3(i32* readonly %arg)
 bb:
 ; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg)
-; ATTRIBUTOR:   %tmp = call nonnull i32* @f1(i32* readonly %arg)
+; ATTRIBUTOR:   %tmp = call nonnull i32* @f1(i32* %arg)
   %tmp = call i32* @f1(i32* %arg)
   ret i32* %tmp
 }
@@ -578,7 +580,6 @@ define void @make_live(i32* nonnull dereferenceable(8) %a) {
   ret void
 }
 
-
 ;int f(int *u, int n){
 ;  for(int i = 0;i<n;i++){
 ;    h(u);
diff --git a/llvm/test/Transforms/FunctionAttrs/noreturn_async.ll b/llvm/test/Transforms/FunctionAttrs/noreturn_async.ll
index b7e9b0f4058..e06a13f40c5 100644
--- a/llvm/test/Transforms/FunctionAttrs/noreturn_async.ll
+++ b/llvm/test/Transforms/FunctionAttrs/noreturn_async.ll
@@ -1,4 +1,4 @@
-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
 ;
 ; This file is the same as noreturn_sync.ll but with a personality which
 ; indicates that the exception handler *can* catch asynchronous exceptions. As
diff --git a/llvm/test/Transforms/FunctionAttrs/noreturn_sync.ll b/llvm/test/Transforms/FunctionAttrs/noreturn_sync.ll
index 8e583cf9bc4..423a369f704 100644
--- a/llvm/test/Transforms/FunctionAttrs/noreturn_sync.ll
+++ b/llvm/test/Transforms/FunctionAttrs/noreturn_sync.ll
@@ -1,4 +1,4 @@
-; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=3 -S < %s | FileCheck %s
+; RUN: opt -functionattrs -attributor -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s
 ;
 ; This file is the same as noreturn_async.ll but with a personality which
 ; indicates that the exception handler *cannot* catch asynchronous exceptions.
diff --git a/llvm/test/Transforms/FunctionAttrs/value-simplify.ll b/llvm/test/Transforms/FunctionAttrs/value-simplify.ll
index 2fbfa6cfa6b..29686f1eb7d 100644
--- a/llvm/test/Transforms/FunctionAttrs/value-simplify.ll
+++ b/llvm/test/Transforms/FunctionAttrs/value-simplify.ll
@@ -1,3 +1,4 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -attributor --attributor-disable=false -S < %s | FileCheck %s
 ; TODO: Add max-iteration check
 ; ModuleID = 'value-simplify.ll'
@@ -119,3 +120,75 @@ end:
   ret void
 
 }
+
+define i32 @ipccp1(i32 %a) {
+; CHECK-LABEL: define {{[^@]+}}@ipccp1
+; CHECK-SAME: (i32 returned [[A:%.*]]) #0
+; CHECK-NEXT:    br i1 true, label [[T:%.*]], label [[F:%.*]]
+; CHECK:       t:
+; CHECK-NEXT:    ret i32 [[A:%.*]]
+; CHECK:       f:
+; CHECK-NEXT:    unreachable
+;
+  br i1 true, label %t, label %f
+t:
+  ret i32 %a
+f:
+  %r = call i32 @ipccp1(i32 5)
+  ret i32 %r
+}
+
+define internal i1 @ipccp2i(i1 %a) {
+; CHECK-LABEL: define {{[^@]+}}@ipccp2i
+; CHECK-SAME: (i1 returned [[A:%.*]]) #0
+; CHECK-NEXT:    br i1 true, label [[T:%.*]], label [[F:%.*]]
+; CHECK:       t:
+; CHECK-NEXT:    ret i1 true
+; CHECK:       f:
+; CHECK-NEXT:    unreachable
+;
+  br i1 %a, label %t, label %f
+t:
+  ret i1 %a
+f:
+  %r = call i1 @ipccp2i(i1 false)
+  ret i1 %r
+}
+
+define i1 @ipccp2() {
+; CHECK-LABEL: define {{[^@]+}}@ipccp2() #1
+; CHECK-NEXT:    [[R:%.*]] = call i1 @ipccp2i(i1 true) #0
+; CHECK-NEXT:    ret i1 [[R]]
+;
+  %r = call i1 @ipccp2i(i1 true)
+  ret i1 %r
+}
+
+define internal i32 @ipccp3i(i32 %a) {
+; CHECK-LABEL: define {{[^@]+}}@ipccp3i
+; CHECK-SAME: (i32 [[A:%.*]]) #1
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[A:%.*]], 7
+; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[F:%.*]]
+; CHECK:       t:
+; CHECK-NEXT:    ret i32 [[A]]
+; CHECK:       f:
+; CHECK-NEXT:    [[R:%.*]] = call i32 @ipccp3i(i32 5) #1
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %c = icmp eq i32 %a, 7
+  br i1 %c, label %t, label %f
+t:
+  ret i32 %a
+f:
+  %r = call i32 @ipccp3i(i32 5)
+  ret i32 %r
+}
+
+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
+}