[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

9 files changed, 94 insertions, 19 deletions

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
+}