Index: llvm/include/llvm/Transforms/IPO/Attributor.h
===================================================================
--- llvm/include/llvm/Transforms/IPO/Attributor.h
+++ llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -2646,6 +2646,13 @@
     return F.hasPersonalityFn() && !canSimplifyInvokeNoUnwind(&F);
   }
 
+  /// Return assumed live successors of a given basic block.
+  /// This is specifically useful in AAReachability.
+  virtual const_succ_iterator
+  getNextAssumedLiveSuccessor(const_succ_iterator It) const {
+    return It++;
+  }
+
   /// See AbstractAttribute::getName()
   const std::string getName() const override { return "AAIsDead"; }
 
Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp
===================================================================
--- llvm/lib/Transforms/IPO/AttributorAttributes.cpp
+++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp
@@ -3094,6 +3094,26 @@
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override;
 
+  /// Returns an iterator that corresponds to the next assumed live successor.
+  /// If there is not such successor, returns the end iterator.
+  const_succ_iterator
+  getNextAssumedLiveSuccessor(const_succ_iterator It) const override {
+    const BasicBlock *BB = It.getSource();
+    assert(It != succ_end(BB) &&
+           "The given iterator must not be end iterator!");
+    if (!getAssumed())
+      return ++It;
+    while (++It != succ_end(BB)) {
+      auto AssumedLiveSuccessorsIt = AssumedLiveSuccessors.find(BB);
+      if (AssumedLiveSuccessorsIt == AssumedLiveSuccessors.end())
+        return It;
+      const BasicBlock *SuccBB = *It;
+      if (AssumedLiveSuccessorsIt->second->count(SuccBB))
+        return It;
+    }
+    return It;
+  }
+
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {}
 
@@ -3171,6 +3191,10 @@
   /// Collection of instructions that are known to not transfer control.
   SmallSetVector<const Instruction *, 8> KnownDeadEnds;
 
+  /// Collection of all assumed live successors for each block
+  DenseMap<const BasicBlock *, std::unique_ptr<DenseSet<const BasicBlock *>>>
+      AssumedLiveSuccessors;
+
   /// Collection of all assumed live BasicBlocks.
   DenseSet<const BasicBlock *> AssumedLiveBlocks;
 };
@@ -3267,6 +3291,40 @@
   return UsedAssumedInformation;
 }
 
+static bool identifyAliveSuccessorsForInstruction(
+    Attributor &A, const Instruction &I, AbstractAttribute &AA,
+    SmallVectorImpl<const Instruction *> &AliveSuccessors) {
+  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), AA, AliveSuccessors);
+    break;
+  case Instruction::Invoke:
+    UsedAssumedInformation =
+        identifyAliveSuccessors(A, cast<InvokeInst>(I), AA, AliveSuccessors);
+    break;
+  case Instruction::Br:
+    UsedAssumedInformation =
+        identifyAliveSuccessors(A, cast<BranchInst>(I), AA, AliveSuccessors);
+    break;
+  case Instruction::Switch:
+    UsedAssumedInformation =
+        identifyAliveSuccessors(A, cast<SwitchInst>(I), AA, AliveSuccessors);
+    break;
+  }
+  return UsedAssumedInformation;
+}
+
 ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
   ChangeStatus Change = ChangeStatus::UNCHANGED;
 
@@ -3288,34 +3346,8 @@
 
     AliveSuccessors.clear();
 
-    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;
-    }
+    bool UsedAssumedInformation =
+        identifyAliveSuccessorsForInstruction(A, *I, *this, AliveSuccessors);
 
     if (UsedAssumedInformation) {
       NewToBeExploredFrom.insert(I);
@@ -3331,6 +3363,16 @@
                       << UsedAssumedInformation << "\n");
 
     for (const Instruction *AliveSuccessor : AliveSuccessors) {
+      // if successor belongs to different basic block, record the edge.
+      if (I->getParent() != AliveSuccessor->getParent()) {
+        auto AssumedLiveSuccessorsInsertResult =
+            AssumedLiveSuccessors.insert(std::make_pair(
+                I->getParent(), std::unique_ptr<DenseSet<const BasicBlock *>>(
+                                    new DenseSet<const BasicBlock *>())));
+        AssumedLiveSuccessorsInsertResult.first->second->insert(
+            AliveSuccessor->getParent());
+      }
+
       if (!I->isTerminator()) {
         assert(AliveSuccessors.size() == 1 &&
                "Non-terminator expected to have a single successor!");