[MustExecute] Forward iterate over conditional branches

Summary:
If a conditional branch is encountered we can try to find a join block
where the execution is known to continue. This means finding a suitable
block, e.g., the immediate post dominator of the conditional branch, and
proofing control will always reach that block.

This patch implements different techniques that work with and without
provided analysis.

Reviewers: uenoku, sstefan1, hfinkel

Subscribers: hiraditya, bollu, llvm-commits

Tags: #llvm

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

1 files changed, 221 insertions, 11 deletions

diff --git a/llvm/test/Transforms/FunctionAttrs/nonnull.ll b/llvm/test/Transforms/FunctionAttrs/nonnull.ll
index 9a7eb114eae..657ef7152eb 100644
--- a/llvm/test/Transforms/FunctionAttrs/nonnull.ll
+++ b/llvm/test/Transforms/FunctionAttrs/nonnull.ll
@@ -1,3 +1,4 @@
+; 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
@@ -159,7 +160,7 @@ define void @test13_helper() {
   ret void
 }
 define internal void @test13(i8* %a, i8* %b, i8* %c) {
-; ATTRIBUTOR: define internal void @test13(i8* nocapture nonnull readnone %a, i8* nocapture readnone %b, i8* nocapture readnone %c) 
+; ATTRIBUTOR: define internal void @test13(i8* nocapture nonnull readnone %a, i8* nocapture readnone %b, i8* nocapture readnone %c)
   ret void
 }
 
@@ -172,7 +173,7 @@ declare nonnull i8* @nonnull()
 ; * Argument
 ; 1. In f1:bb6, %arg can be marked with nonnull because of the comparison in bb1
 ; 2. Because f2 is internal function, f2(i32* %arg) -> @f2(i32* nonnull %arg)
-; 3. In f1:bb4 %tmp5 is nonnull and f3 is internal function. 
+; 3. In f1:bb4 %tmp5 is nonnull and f3 is internal function.
 ;    Then, f3(i32* %arg) -> @f3(i32* nonnull %arg)
 ; 4. We get nonnull in whole f1 call sites so f1(i32* %arg) -> @f1(i32* nonnull %arg)
 
@@ -208,21 +209,21 @@ bb9:                                              ; preds = %bb4, %bb
 }
 
 define internal i32* @f2(i32* %arg) {
-; FIXME: missing nonnull. It should be nonnull @f2(i32* nonnull %arg) 
+; FIXME: missing nonnull. It should be nonnull @f2(i32* nonnull %arg)
 ; ATTRIBUTOR: define internal nonnull i32* @f2(i32* readonly %arg)
 bb:
 
-; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg) 
+; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg)
 ; ATTRIBUTOR:   %tmp = tail call nonnull i32* @f1(i32* readonly %arg)
   %tmp = tail call i32* @f1(i32* %arg)
   ret i32* %tmp
 }
 
 define dso_local noalias i32* @f3(i32* %arg) {
-; FIXME: missing nonnull. It should be nonnull @f3(i32* nonnull readonly %arg) 
+; FIXME: missing nonnull. It should be nonnull @f3(i32* nonnull readonly %arg)
 ; ATTRIBUTOR: define dso_local noalias i32* @f3(i32* nocapture readonly %arg)
 bb:
-; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg) 
+; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg)
 ; ATTRIBUTOR:   %tmp = call i32* @f1(i32* readonly %arg)
   %tmp = call i32* @f1(i32* %arg)
   ret i32* null
@@ -266,8 +267,7 @@ if.else:
 ; fun1(nonnull %a)
 ; We can say that %a is nonnull
 define void @f17(i8* %a, i8 %c) {
-; FIXME: missing nonnull on %a
-; ATTRIBUTOR: define void @f17(i8* %a, i8 %c)
+; ATTRIBUTOR: define void @f17(i8* nonnull %a, i8 %c)
   %cmp = icmp eq i8 %c, 0
   br i1 %cmp, label %if.then, label %if.else
 if.then:
@@ -292,8 +292,7 @@ cont:
 ; fun1(nonnull %a)
 
 define void @f18(i8* %a, i8* %b, i8 %c) {
-; FIXME: missing nonnull on %a
-; ATTRIBUTOR: define void @f18(i8* %a, i8* %b, i8 %c)
+; ATTRIBUTOR: define void @f18(i8* nonnull %a, i8* %b, i8 %c)
   %cmp1 = icmp eq i8 %c, 0
   br i1 %cmp1, label %if.then, label %if.else
 if.then:
@@ -477,7 +476,7 @@ define i8 @parent7(i8* %a) {
 declare i32 @esfp(...)
 
 define i1 @parent8(i8* %a, i8* %bogus1, i8* %b) personality i8* bitcast (i32 (...)* @esfp to i8*){
-; BOTH-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b) 
+; BOTH-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b)
 ; BOTH-NEXT:  entry:
 ; FNATTR-NEXT:    invoke void @use2nonnull(i8* %a, i8* %b)
 ; ATTRIBUTOR-NEXT:    invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b)
@@ -579,5 +578,216 @@ 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);
+;  }
+;  return g(nonnull u);
+;}
+declare void @h(i32*) willreturn nounwind
+declare i32 @g(i32*) willreturn nounwind
+define i32 @nonnull_exec_ctx_1(i32* %a, i32 %b) {
+; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1
+; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3
+; FNATTR-NEXT:  en:
+; FNATTR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; FNATTR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; FNATTR:       ex:
+; FNATTR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; FNATTR-NEXT:    ret i32 [[TMP5]]
+; FNATTR:       hd:
+; FNATTR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ]
+; FNATTR-NEXT:    tail call void @h(i32* [[A]])
+; FNATTR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; FNATTR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; FNATTR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1
+; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #5
+; ATTRIBUTOR-NEXT:  en:
+; ATTRIBUTOR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; ATTRIBUTOR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; ATTRIBUTOR:       ex:
+; ATTRIBUTOR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; ATTRIBUTOR-NEXT:    ret i32 [[TMP5]]
+; ATTRIBUTOR:       hd:
+; ATTRIBUTOR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ]
+; ATTRIBUTOR-NEXT:    tail call void @h(i32* [[A]])
+; ATTRIBUTOR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; ATTRIBUTOR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; ATTRIBUTOR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+en:
+  %tmp3 = icmp eq i32 %b, 0
+  br i1 %tmp3, label %ex, label %hd
+
+ex:
+  %tmp5 = tail call i32 @g(i32* nonnull %a)
+  ret i32 %tmp5
+
+hd:
+  %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+  tail call void @h(i32* %a)
+  %tmp8 = add nuw i32 %tmp7, 1
+  %tmp9 = icmp eq i32 %tmp8, %b
+  br i1 %tmp9, label %ex, label %hd
+}
+
+define i32 @nonnull_exec_ctx_1b(i32* %a, i32 %b) {
+; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1b
+; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3
+; FNATTR-NEXT:  en:
+; FNATTR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; FNATTR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; FNATTR:       ex:
+; FNATTR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; FNATTR-NEXT:    ret i32 [[TMP5]]
+; FNATTR:       hd:
+; FNATTR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ]
+; FNATTR-NEXT:    tail call void @h(i32* [[A]])
+; FNATTR-NEXT:    br label [[HD2]]
+; FNATTR:       hd2:
+; FNATTR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; FNATTR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; FNATTR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1b
+; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #5
+; ATTRIBUTOR-NEXT:  en:
+; ATTRIBUTOR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; ATTRIBUTOR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; ATTRIBUTOR:       ex:
+; ATTRIBUTOR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; ATTRIBUTOR-NEXT:    ret i32 [[TMP5]]
+; ATTRIBUTOR:       hd:
+; ATTRIBUTOR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ]
+; ATTRIBUTOR-NEXT:    tail call void @h(i32* [[A]])
+; ATTRIBUTOR-NEXT:    br label [[HD2]]
+; ATTRIBUTOR:       hd2:
+; ATTRIBUTOR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; ATTRIBUTOR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; ATTRIBUTOR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+en:
+  %tmp3 = icmp eq i32 %b, 0
+  br i1 %tmp3, label %ex, label %hd
+
+ex:
+  %tmp5 = tail call i32 @g(i32* nonnull %a)
+  ret i32 %tmp5
+
+hd:
+  %tmp7 = phi i32 [ %tmp8, %hd2 ], [ 0, %en ]
+  tail call void @h(i32* %a)
+  br label %hd2
+
+hd2:
+  %tmp8 = add nuw i32 %tmp7, 1
+  %tmp9 = icmp eq i32 %tmp8, %b
+  br i1 %tmp9, label %ex, label %hd
+}
+
+define i32 @nonnull_exec_ctx_2(i32* %a, i32 %b) willreturn nounwind {
+; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2
+; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #2
+; FNATTR-NEXT:  en:
+; FNATTR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; FNATTR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; FNATTR:       ex:
+; FNATTR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; FNATTR-NEXT:    ret i32 [[TMP5]]
+; FNATTR:       hd:
+; FNATTR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ]
+; FNATTR-NEXT:    tail call void @h(i32* [[A]])
+; FNATTR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; FNATTR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; FNATTR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2
+; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3
+; ATTRIBUTOR-NEXT:  en:
+; ATTRIBUTOR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; ATTRIBUTOR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; ATTRIBUTOR:       ex:
+; ATTRIBUTOR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; ATTRIBUTOR-NEXT:    ret i32 [[TMP5]]
+; ATTRIBUTOR:       hd:
+; ATTRIBUTOR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ]
+; ATTRIBUTOR-NEXT:    tail call void @h(i32* nonnull [[A]])
+; ATTRIBUTOR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; ATTRIBUTOR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; ATTRIBUTOR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+en:
+  %tmp3 = icmp eq i32 %b, 0
+  br i1 %tmp3, label %ex, label %hd
+
+ex:
+  %tmp5 = tail call i32 @g(i32* nonnull %a)
+  ret i32 %tmp5
+
+hd:
+  %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ]
+  tail call void @h(i32* %a)
+  %tmp8 = add nuw i32 %tmp7, 1
+  %tmp9 = icmp eq i32 %tmp8, %b
+  br i1 %tmp9, label %ex, label %hd
+}
+
+define i32 @nonnull_exec_ctx_2b(i32* %a, i32 %b) willreturn nounwind {
+; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2b
+; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #2
+; FNATTR-NEXT:  en:
+; FNATTR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; FNATTR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; FNATTR:       ex:
+; FNATTR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; FNATTR-NEXT:    ret i32 [[TMP5]]
+; FNATTR:       hd:
+; FNATTR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ]
+; FNATTR-NEXT:    tail call void @h(i32* [[A]])
+; FNATTR-NEXT:    br label [[HD2]]
+; FNATTR:       hd2:
+; FNATTR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; FNATTR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; FNATTR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2b
+; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3
+; ATTRIBUTOR-NEXT:  en:
+; ATTRIBUTOR-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0
+; ATTRIBUTOR-NEXT:    br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]]
+; ATTRIBUTOR:       ex:
+; ATTRIBUTOR-NEXT:    [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]])
+; ATTRIBUTOR-NEXT:    ret i32 [[TMP5]]
+; ATTRIBUTOR:       hd:
+; ATTRIBUTOR-NEXT:    [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ]
+; ATTRIBUTOR-NEXT:    tail call void @h(i32* nonnull [[A]])
+; ATTRIBUTOR-NEXT:    br label [[HD2]]
+; ATTRIBUTOR:       hd2:
+; ATTRIBUTOR-NEXT:    [[TMP8]] = add nuw i32 [[TMP7]], 1
+; ATTRIBUTOR-NEXT:    [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]]
+; ATTRIBUTOR-NEXT:    br i1 [[TMP9]], label [[EX]], label [[HD]]
+;
+en:
+  %tmp3 = icmp eq i32 %b, 0
+  br i1 %tmp3, label %ex, label %hd
+
+ex:
+  %tmp5 = tail call i32 @g(i32* nonnull %a)
+  ret i32 %tmp5
+
+hd:
+  %tmp7 = phi i32 [ %tmp8, %hd2 ], [ 0, %en ]
+  tail call void @h(i32* %a)
+  br label %hd2
+
+hd2:
+  %tmp8 = add nuw i32 %tmp7, 1
+  %tmp9 = icmp eq i32 %tmp8, %b
+  br i1 %tmp9, label %ex, label %hd
+}
+
 attributes #0 = { "null-pointer-is-valid"="true" }
 attributes #1 = { nounwind willreturn}