diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h
--- a/llvm/include/llvm/Transforms/IPO/Attributor.h
+++ b/llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -1134,10 +1134,8 @@
       const function_ref<bool(Value &, const SmallPtrSetImpl<ReturnInst *> &)>
           &Pred) const = 0;
 
-  using iterator = DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>>::iterator;
   using const_iterator =
       DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>>::const_iterator;
-  virtual llvm::iterator_range<iterator> returned_values() = 0;
   virtual llvm::iterator_range<const_iterator> returned_values() const = 0;
 
   virtual size_t getNumReturnValues() const = 0;
diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp
--- a/llvm/lib/Transforms/IPO/Attributor.cpp
+++ b/llvm/lib/Transforms/IPO/Attributor.cpp
@@ -683,13 +683,18 @@
   /// return instructions that might return them.
   DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> ReturnedValues;
 
+  /// Mapping to remember the number of returned values for a AAReturnedValues
+  /// object such that we can avoid updates if nothing changed.
+  DenseMap<const AAReturnedValues *, unsigned> NumReturnedValuesPerKnownAA;
+
+  /// Set of unresolved calls returned by the associated function.
   SmallPtrSet<CallBase *, 8> UnresolvedCalls;
 
   /// State flags
   ///
   ///{
-  bool IsFixed;
-  bool IsValidState;
+  bool IsFixed = false;
+  bool IsValidState = true;
   ///}
 
 public:
@@ -736,10 +741,6 @@
   /// See AbstractAttribute::updateImpl(Attributor &A).
   ChangeStatus updateImpl(Attributor &A) override;
 
-  llvm::iterator_range<iterator> returned_values() override {
-    return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
-  }
-
   llvm::iterator_range<const_iterator> returned_values() const override {
     return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
   }
@@ -775,7 +776,6 @@
   /// See AbstractState::indicateOptimisticFixpoint(...).
   ChangeStatus indicateOptimisticFixpoint() override {
     IsFixed = true;
-    IsValidState &= true;
     return ChangeStatus::UNCHANGED;
   }
 
@@ -976,6 +976,15 @@
     if (Unresolved)
       continue;
 
+    // Now track transitively returned values.
+    unsigned &NumRetAA = NumReturnedValuesPerKnownAA[&RetValAA];
+    if (NumRetAA == RetValAA.getNumReturnValues()) {
+      LLVM_DEBUG(dbgs() << "[AAReturnedValues] Skip RetValAA as it has not "
+                           "changed since it was seen last\n");
+      continue;
+    }
+    NumRetAA = RetValAA.getNumReturnValues();
+
     for (auto &RetValAAIt : RetValAA.returned_values()) {
       Value *RetVal = RetValAAIt.first;
       if (Argument *Arg = dyn_cast<Argument>(RetVal)) {
@@ -1617,6 +1626,9 @@
       Instruction *I = const_cast<Instruction *>(NRC);
       BasicBlock *BB = I->getParent();
       Instruction *SplitPos = I->getNextNode();
+      // TODO: mark stuff before unreachable instructions as dead.
+      if (!I->isTerminator() && isa<UnreachableInst>(SplitPos))
+        continue;
 
       if (auto *II = dyn_cast<InvokeInst>(I)) {
         // If we keep the invoke the split position is at the beginning of the
@@ -1634,6 +1646,7 @@
             if (AANoUnw.isAssumedNoUnwind()) {
               LLVM_DEBUG(dbgs()
                          << "[AAIsDead] Replace invoke with call inst\n");
+
               // We do not need an invoke (II) but instead want a call followed
               // by an unreachable. However, we do not remove II as other
               // abstract attributes might have it cached as part of their
@@ -2676,6 +2689,37 @@
 
     CallSite CS(&I);
     if (CS && CS.getCalledFunction()) {
+      Function *Callee = CS.getCalledFunction();
+      Type *ReturnType = Callee->getReturnType();
+      if (!ReturnType->isVoidTy()) {
+
+        checkAndRegisterAA<AAReturnedValuesCallSite>(
+            IRPosition::callsite_function(CS), *this, Whitelist);
+
+        if (ReturnType->isPointerTy()) {
+          IRPosition RetPos = IRPosition::callsite_returned(CS);
+
+          // Every function with pointer call site return type might be marked
+          // align.
+          checkAndRegisterAA<AAAlignCallSiteReturned>(RetPos, *this, Whitelist);
+
+          // Every function with pointer call site return type might be marked
+          // nonnull.
+          checkAndRegisterAA<AANonNullCallSiteReturned>(RetPos, *this,
+                                                        Whitelist);
+
+          // Every function with pointer call site return type might be marked
+          // noalias.
+          checkAndRegisterAA<AANoAliasCallSiteReturned>(RetPos, *this,
+                                                        Whitelist);
+
+          // Every function with pointer call site return type might be marked
+          // dereferenceable.
+          checkAndRegisterAA<AADereferenceableCallSiteReturned>(RetPos, *this,
+                                                                Whitelist);
+        }
+      }
+
       for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
         if (!CS.getArgument(i)->getType()->isPointerTy())
           continue;
diff --git a/llvm/test/Transforms/FunctionAttrs/align.ll b/llvm/test/Transforms/FunctionAttrs/align.ll
--- a/llvm/test/Transforms/FunctionAttrs/align.ll
+++ b/llvm/test/Transforms/FunctionAttrs/align.ll
@@ -88,7 +88,7 @@
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %1
-; ATTRIBUTOR: %4 = tail call i8* @f2(i8* nonnull align 8 dereferenceable(1) @a1)
+; ATTRIBUTOR: %4 = tail call nonnull align 8 dereferenceable(1) i8* @f2(i8* nonnull align 8 dereferenceable(1) @a1)
   %4 = tail call i8* @f2(i8* nonnull @a1)
   br label %5
 
@@ -105,12 +105,12 @@
 
 ; <label>:3:                                      ; preds = %1
 
-; ATTRIBUTOR: %4 = tail call i8* @f1(i8* nonnull align 8 dereferenceable(1) %0)
+; ATTRIBUTOR: %4 = tail call nonnull align 8 dereferenceable(1) i8* @f1(i8* nonnull align 8 dereferenceable(1) %0)
   %4 = tail call i8* @f1(i8* nonnull %0)
   br label %7
 
 ; <label>:5:                                      ; preds = %1
-; ATTRIBUTOR: %6 = tail call i8* @f3(i8* nonnull align 16 dereferenceable(1) @a2)
+; ATTRIBUTOR: %6 = tail call nonnull align 8 dereferenceable(1) i8* @f3(i8* nonnull align 16 dereferenceable(1) @a2)
   %6 = tail call i8* @f3(i8* nonnull @a2)
   br label %7
 
@@ -126,7 +126,7 @@
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %1
-; ATTRIBUTOR: %4 = tail call i8* @f1(i8* nonnull align 16 dereferenceable(1) @a2)
+; ATTRIBUTOR: %4 = tail call nonnull align 8 dereferenceable(1) i8* @f1(i8* nonnull align 16 dereferenceable(1) @a2)
   %4 = tail call i8* @f1(i8* nonnull @a2)
   br label %5
 
diff --git a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll
--- a/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll
+++ b/llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll
@@ -90,7 +90,7 @@
 define i32* @srec16(i32* %a) #0 {
 entry:
   %call = call i32* @srec16(i32* %a)
-; CHECK:      %call = call i32* @srec16(i32* %a)
+; CHECK:      %call = call noalias nonnull align 536870912 dereferenceable(4294967295) i32* @srec16(i32* %a)
 ; CHECK-NEXT: unreachable
   %call1 = call i32* @srec16(i32* %call)
   %call2 = call i32* @srec16(i32* %call1)
diff --git a/llvm/test/Transforms/FunctionAttrs/liveness.ll b/llvm/test/Transforms/FunctionAttrs/liveness.ll
--- a/llvm/test/Transforms/FunctionAttrs/liveness.ll
+++ b/llvm/test/Transforms/FunctionAttrs/liveness.ll
@@ -12,130 +12,9 @@
 
 declare i32 @bar() nosync readnone
 
-; CHECK: Function Attrs: nofree norecurse nounwind uwtable willreturn
-define i32 @volatile_load(i32*) norecurse nounwind uwtable {
-  %2 = load volatile i32, i32* %0, align 4
-  ret i32 %2
-}
-
-; CHECK: Function Attrs: nofree norecurse nosync nounwind uwtable willreturn
-; CHECK-NEXT: define internal i32 @internal_load(i32* nonnull %0)
-define internal i32 @internal_load(i32*) norecurse nounwind uwtable {
-  %2 = load i32, i32* %0, align 4
-  ret i32 %2
-}
-; TEST 1: Only first block is live.
-
-; CHECK: Function Attrs: nofree noreturn nosync nounwind
-; CHECK-NEXT: define i32 @first_block_no_return(i32 %a, i32* nonnull %ptr1, i32* %ptr2)
-define i32 @first_block_no_return(i32 %a, i32* nonnull %ptr1, i32* %ptr2) #0 {
-entry:
-  call i32 @internal_load(i32* %ptr1)
-  ; CHECK: call i32 @internal_load(i32* nonnull %ptr1)
-  call void @no_return_call()
-  ; CHECK: call void @no_return_call()
-  ; CHECK-NEXT: unreachable
-  %cmp = icmp eq i32 %a, 0
-  br i1 %cmp, label %cond.true, label %cond.false
-
-cond.true:                                        ; preds = %entry
-  call i32 @internal_load(i32* %ptr2)
-  ; CHECK: call i32 @internal_load(i32* %ptr2)
-  %load = call i32 @volatile_load(i32* %ptr1)
-  call void @normal_call()
-  %call = call i32 @foo()
-  br label %cond.end
-
-cond.false:                                       ; preds = %entry
-  call void @normal_call()
-  %call1 = call i32 @bar()
-  br label %cond.end
-
-cond.end:                                         ; preds = %cond.false, %cond.true
-  %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
-  ret i32 %cond
-}
-
-; TEST 2: cond.true is dead, but cond.end is not, since cond.false is live
-
-; This is just an example. For example we can put a sync call in a
-; dead block and check if it is deduced.
-
-; CHECK: Function Attrs: nosync
-; CHECK-NEXT: define i32 @dead_block_present(i32 %a, i32* %ptr1)
-define i32 @dead_block_present(i32 %a, i32* %ptr1) #0 {
-entry:
-  %cmp = icmp eq i32 %a, 0
-  br i1 %cmp, label %cond.true, label %cond.false
-
-cond.true:                                        ; preds = %entry
-  call void @no_return_call()
-  ; CHECK: call void @no_return_call()
-  ; CHECK-NEXT: unreachable
-  %call = call i32 @volatile_load(i32* %ptr1)
-  br label %cond.end
-
-cond.false:                                       ; preds = %entry
-  call void @normal_call()
-  %call1 = call i32 @bar()
-  br label %cond.end
-
-cond.end:                                         ; preds = %cond.false, %cond.true
-  %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
-  ret i32 %cond
-}
-
-; TEST 3: both cond.true and cond.false are dead, therfore cond.end is dead as well.
-
-define i32 @all_dead(i32 %a) #0 {
-entry:
-  %cmp = icmp eq i32 %a, 0
-  br i1 %cmp, label %cond.true, label %cond.false
-
-cond.true:                                        ; preds = %entry
-  call void @no_return_call()
-  ; CHECK: call void @no_return_call()
-  ; CHECK-NEXT: unreachable
-  %call = call i32 @foo()
-  br label %cond.end
-
-cond.false:                                       ; preds = %entry
-  call void @no_return_call()
-  ; CHECK: call void @no_return_call()
-  ; CHECK-NEXT: unreachable
-  %call1 = call i32 @bar()
-  br label %cond.end
-
-cond.end:                                         ; preds = %cond.false, %cond.true
-  %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
-  ret i32 %cond
-}
 
 declare i32 @__gxx_personality_v0(...)
 
-; TEST 4: All blocks are live.
-
-; CHECK: define i32 @all_live(i32 %a)
-define i32 @all_live(i32 %a) #0 {
-entry:
-  %cmp = icmp eq i32 %a, 0
-  br i1 %cmp, label %cond.true, label %cond.false
-
-cond.true:                                        ; preds = %entry
-  call void @normal_call()
-  %call = call i32 @foo_noreturn()
-  br label %cond.end
-
-cond.false:                                       ; preds = %entry
-  call void @normal_call()
-  %call1 = call i32 @bar()
-  br label %cond.end
-
-cond.end:                                         ; preds = %cond.false, %cond.true
-  %cond = phi i32 [ %call, %cond.true ], [ %call1, %cond.false ]
-  ret i32 %cond
-}
-
 ; TEST 5 noreturn invoke instruction with a unreachable normal successor block.
 
 ; CHECK: define i32 @invoke_noreturn(i32 %a)
@@ -171,143 +50,3 @@
   ret i32 0
 }
 
-; TEST 4.1 noreturn invoke instruction replaced by a call and an unreachable instruction
-; put after it.
-
-; CHECK: define i32 @invoke_noreturn_nounwind(i32 %a)
-define i32 @invoke_noreturn_nounwind(i32 %a) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
-entry:
-  %cmp = icmp eq i32 %a, 0
-  br i1 %cmp, label %cond.true, label %cond.false
-
-cond.true:                                        ; preds = %entry
-  call void @normal_call()
-  %call = invoke i32 @foo_noreturn_nounwind() to label %continue
-            unwind label %cleanup
-  ; CHECK:      call void @normal_call()
-  ; CHECK-NEXT: call i32 @foo_noreturn_nounwind()
-  ; CHECK-NEXT: unreachable
-
-  ; We keep the invoke around as other attributes might have references to it.
-  ; CHECK:       cond.true.split:                                  ; No predecessors!
-  ; CHECK-NEXT:      invoke i32 @foo_noreturn_nounwind()
-
-cond.false:                                       ; preds = %entry
-  call void @normal_call()
-  %call1 = call i32 @bar()
-  br label %cond.end
-
-cond.end:                                         ; preds = %cond.false, %continue
-  %cond = phi i32 [ %call, %continue ], [ %call1, %cond.false ]
-  ret i32 %cond
-
-continue:
-  br label %cond.end
-
-cleanup:
-  %res = landingpad { i8*, i32 }
-  catch i8* null
-  ret i32 0
-}
-
-; TEST 6: Undefined behvior, taken from LangRef.
-; FIXME: Should be able to detect undefined behavior.
-
-; CHECK: define void @ub(i32* %0)
-define void @ub(i32* %0) {
-  %poison = sub nuw i32 0, 1           ; Results in a poison value.
-  %still_poison = and i32 %poison, 0   ; 0, but also poison.
-  %poison_yet_again = getelementptr i32, i32* %0, i32 %still_poison
-  store i32 0, i32* %poison_yet_again  ; Undefined behavior due to store to poison.
-  ret void
-}
-
-define void @inf_loop() #0 {
-entry:
-  br label %while.body
-
-while.body:                                       ; preds = %entry, %while.body
-  br label %while.body
-}
-
-; TEST 7: Infinite loop.
-; FIXME: Detect infloops, and mark affected blocks dead.
-
-define i32 @test5(i32, i32) #0 {
-  %3 = icmp sgt i32 %0, %1
-  br i1 %3, label %cond.if, label %cond.elseif
-
-cond.if:                                                ; preds = %2
-  %4 = tail call i32 @bar()
-  br label %cond.end
-
-cond.elseif:                                                ; preds = %2
-  call void @inf_loop()
-  %5 = icmp slt i32 %0, %1
-  br i1 %5, label %cond.end, label %cond.else
-
-cond.else:                                                ; preds = %cond.elseif
-  %6 = tail call i32 @foo()
-  br label %cond.end
-
-cond.end:                                               ; preds = %cond.if, %cond.else, %cond.elseif
-  %7 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ]
-  ret i32 %7
-}
-
-define void @rec() #0 {
-entry:
-  call void @rec()
-  ret void
-}
-
-; TEST 8: Recursion
-; FIXME: everything after first block should be marked dead
-; and unreachable should be put after call to @rec().
-
-define i32 @test6(i32, i32) #0 {
-  call void @rec()
-  %3 = icmp sgt i32 %0, %1
-  br i1 %3, label %cond.if, label %cond.elseif
-
-cond.if:                                                ; preds = %2
-  %4 = tail call i32 @bar()
-  br label %cond.end
-
-cond.elseif:                                                ; preds = %2
-  call void @rec()
-  %5 = icmp slt i32 %0, %1
-  br i1 %5, label %cond.end, label %cond.else
-
-cond.else:                                                ; preds = %cond.elseif
-  %6 = tail call i32 @foo()
-  br label %cond.end
-
-cond.end:                                               ; preds = %cond.if, %cond.else, %cond.elseif
-  %7 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ]
-  ret i32 %7
-}
-; TEST 9: Recursion
-; FIXME: contains recursive call to itself in cond.elseif block
-
-define i32 @test7(i32, i32) #0 {
-  %3 = icmp sgt i32 %0, %1
-  br i1 %3, label %cond.if, label %cond.elseif
-
-cond.if:                                                ; preds = %2
-  %4 = tail call i32 @bar()
-  br label %cond.end
-
-cond.elseif:                                                ; preds = %2
-  %5 = tail call i32 @test7(i32 %0, i32 %1)
-  %6 = icmp slt i32 %0, %1
-  br i1 %6, label %cond.end, label %cond.else
-
-cond.else:                                                ; preds = %cond.elseif
-  %7 = tail call i32 @foo()
-  br label %cond.end
-
-cond.end:                                               ; preds = %cond.if, %cond.else, %cond.elseif
-  %8 = phi i32 [ %1, %cond.elseif ], [ 0, %cond.else ], [ 0, %cond.if ]
-  ret i32 %8
-}
diff --git a/llvm/test/Transforms/FunctionAttrs/nonnull.ll b/llvm/test/Transforms/FunctionAttrs/nonnull.ll
--- a/llvm/test/Transforms/FunctionAttrs/nonnull.ll
+++ b/llvm/test/Transforms/FunctionAttrs/nonnull.ll
@@ -192,7 +192,7 @@
 
 bb4:                                              ; preds = %bb1
   %tmp5 = getelementptr inbounds i32, i32* %arg, i64 1
-; ATTRIBUTOR: %tmp5b = tail call i32* @f3(i32* nonnull %tmp5)
+; ATTRIBUTOR: %tmp5b = tail call noalias i32* @f3(i32* nonnull %tmp5)
   %tmp5b = tail call i32* @f3(i32* %tmp5)
   br label %bb9
 
@@ -223,7 +223,7 @@
 ; ATTRIBUTOR: define dso_local noalias i32* @f3(i32* %arg)
 bb:
 ; FIXME: missing nonnull. It should be @f1(i32* nonnull %arg) 
-; ATTRIBUTOR:   %tmp = call i32* @f1(i32* %arg)
+; ATTRIBUTOR:   %tmp = call nonnull i32* @f1(i32* %arg)
   %tmp = call i32* @f1(i32* %arg)
   ret i32* null
 }