From 4184b2e03401ad3818de9e1751d4e2897e8fcf71 Mon Sep 17 00:00:00 2001
From: Florian Hahn <flo@fhahn.com>
Date: Wed, 8 Apr 2020 15:23:58 +0100
Subject: [PATCH] [DSE,MSSA] Add additional test cases for multi-path
 elimination (NFC).

This adds additional test cases for more scenarios and also with objects
that are accessible after the functions return and allocas.
---
 .../MSSA/multiblock-memintrinsics.ll               | 183 +++++++++++++++++-
 .../MSSA/multiblock-multipath.ll                   | 211 ++++++++++++++++++++-
 2 files changed, 378 insertions(+), 16 deletions(-)

diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-memintrinsics.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-memintrinsics.ll
index 535bcd7..af45ec2 100644
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-memintrinsics.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-memintrinsics.ll
@@ -6,13 +6,16 @@ declare void @unknown_func()
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i1) nounwind
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
-define void @test19(i32* noalias %P) {
-; CHECK-LABEL: @test19(
+; Tests where the pointer/object is accessible after the function returns.
+
+; Overwriting store along one path to the exit.
+define void @accessible_after_return_1(i32* noalias %P, i1 %c) {
+; CHECK-LABEL: @accessible_after_return_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
 ; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
-; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
@@ -26,7 +29,7 @@ entry:
   %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
   %p3 = bitcast i32* %arrayidx0 to i8*
   call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
-  br i1 true, label %bb1, label %bb2
+  br i1 %c, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
@@ -37,15 +40,174 @@ bb3:
   ret void
 }
 
+; Post-dominating store.
+define void @accessible_after_return_2(i32* noalias %P, i1 %c) {
+; CHECK-LABEL: @accessible_after_return_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br label %bb3
+
+bb2:
+  %arrayidx2 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx2, align 4
+  br label %bb3
+
+bb3:
+  ret void
+}
 
-define void @test20(i32* noalias %P) {
-; CHECK-LABEL: @test20(
+; Stores along  both exit paths.
+define void @accessible_after_return_3(i32* noalias %P, i1 %c) {
+; CHECK-LABEL: @accessible_after_return_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P:%.*]], i64 1
 ; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
 ; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i8, i8* [[P3]], i64 4
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 24, i1 false)
-; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    ret void
+;
+entry:
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  ret void
+}
+
+
+; Tests where the pointer/object is *NOT* accessible after the function returns.
+
+; Overwriting store along one path to the exit.
+define void @alloca_1(i1 %c) {
+; CHECK-LABEL: @alloca_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[P_ALLOCA:%.*]] = alloca [32 x i32]
+; CHECK-NEXT:    [[P:%.*]] = bitcast [32 x i32]* [[P_ALLOCA]] to i32*
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %P.alloca = alloca [32 x i32]
+  %P = bitcast [32 x i32]* %P.alloca to i32*
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 %c, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br label %bb3
+bb3:
+  ret void
+}
+
+; Post-dominating store.
+define void @alloca_2(i1 %c) {
+; CHECK-LABEL: @alloca_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[P_ALLOCA:%.*]] = alloca [32 x i32]
+; CHECK-NEXT:    [[P:%.*]] = bitcast [32 x i32]* [[P_ALLOCA]] to i32*
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[P3]], i8 0, i64 28, i1 false)
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[ARRAYIDX1:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX1]], align 4
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[ARRAYIDX2:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    store i32 1, i32* [[ARRAYIDX2]], align 4
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %P.alloca = alloca [32 x i32]
+  %P = bitcast [32 x i32]* %P.alloca to i32*
+  %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
+  %p3 = bitcast i32* %arrayidx0 to i8*
+  call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx1, align 4
+  br label %bb3
+
+bb2:
+  %arrayidx2 = getelementptr inbounds i32, i32* %P, i64 1
+  store i32 1, i32* %arrayidx2, align 4
+  br label %bb3
+
+bb3:
+  ret void
+}
+
+; Stores along  both exit paths.
+define void @alloca_3(i1 %c) {
+; CHECK-LABEL: @alloca_3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[P_ALLOCA:%.*]] = alloca [32 x i32]
+; CHECK-NEXT:    [[P:%.*]] = bitcast [32 x i32]* [[P_ALLOCA]] to i32*
+; CHECK-NEXT:    [[ARRAYIDX0:%.*]] = getelementptr inbounds i32, i32* [[P]], i64 1
+; CHECK-NEXT:    [[P3:%.*]] = bitcast i32* [[ARRAYIDX0]] to i8*
+; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i8, i8* [[P3]], i64 4
+; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 4 [[TMP0]], i8 0, i64 24, i1 false)
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
@@ -56,14 +218,19 @@ define void @test20(i32* noalias %P) {
 ; CHECK-NEXT:    ret void
 ;
 entry:
+  %P.alloca = alloca [32 x i32]
+  %P = bitcast [32 x i32]* %P.alloca to i32*
   %arrayidx0 = getelementptr inbounds i32, i32* %P, i64 1
   %p3 = bitcast i32* %arrayidx0 to i8*
   call void @llvm.memset.p0i8.i64(i8* %p3, i8 0, i64 28, i32 4, i1 false)
-  br i1 true, label %bb1, label %bb2
+  br i1 %c, label %bb1, label %bb2
+
 bb1:
   br label %bb3
+
 bb2:
   br label %bb3
+
 bb3:
   %arrayidx1 = getelementptr inbounds i32, i32* %P, i64 1
   store i32 1, i32* %arrayidx1, align 4
diff --git a/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-multipath.ll b/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-multipath.ll
index a24ecd2..a5d7b24 100644
--- a/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-multipath.ll
+++ b/llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-multipath.ll
@@ -5,8 +5,10 @@ target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n32-S64"
 
 declare void @use(i32 *)
 
-define void @test4(i32* noalias %P, i1 %c1) {
-; CHECK-LABEL: @test4(
+; Tests where the pointer/object is accessible after the function returns.
+
+define void @accessible_after_return_1(i32* noalias %P, i1 %c1) {
+; CHECK-LABEL: @accessible_after_return_1(
 ; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
@@ -34,15 +36,15 @@ bb5:
   ret void
 }
 
-define void @test5(i32* noalias %P) {
-; CHECK-LABEL: @test5(
+define void @accessible_after_return_2(i32* noalias %P, i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @accessible_after_return_2(
 ; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
-; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    store i32 0, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB5:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    br i1 undef, label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    store i32 3, i32* [[P]]
 ; CHECK-NEXT:    br label [[BB5]]
@@ -54,13 +56,13 @@ define void @test5(i32* noalias %P) {
 ; CHECK-NEXT:    ret void
 ;
   store i32 1, i32* %P
-  br i1 true, label %bb1, label %bb2
+  br i1 %c.1, label %bb1, label %bb2
 bb1:
   store i32 0, i32* %P
   br label %bb5
 
 bb2:
-  br i1 undef, label %bb3, label %bb4
+  br i1 %c.2, label %bb3, label %bb4
 
 bb3:
   store i32 3, i32* %P
@@ -74,3 +76,196 @@ bb5:
   call void @use(i32* %P)
   ret void
 }
+
+define void @accessible_after_return_3(i32* noalias %P, i1 %c1) {
+; CHECK-LABEL: @accessible_after_return_3(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    call void @use(i32* [[P]])
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  store i32 0, i32* %P
+  br label %bb5
+
+bb2:
+  br label %bb5
+
+bb5:
+  call void @use(i32* %P)
+  ret void
+}
+
+define void @accessible_after_return_4(i32* noalias %P, i1 %c1) {
+; CHECK-LABEL: @accessible_after_return_4(
+; CHECK-NEXT:    store i32 1, i32* [[P:%.*]]
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @use(i32* [[P]])
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    ret void
+;
+  store i32 1, i32* %P
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  store i32 0, i32* %P
+  call void @use(i32* %P)
+  br label %bb5
+
+bb2:
+  br label %bb5
+
+bb5:
+  ret void
+}
+
+
+; Tests where the pointer/object is *NOT* accessible after the function returns.
+
+define void @alloca_1(i1 %c1) {
+; CHECK-LABEL: @alloca_1(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    store i32 3, i32* [[P]]
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    call void @use(i32* [[P]])
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32
+  store i32 1, i32* %P
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  store i32 0, i32* %P
+  br label %bb5
+bb2:
+  store i32 3, i32* %P
+  br label %bb5
+
+bb5:
+  call void @use(i32* %P)
+  ret void
+}
+
+define void @alloca_2(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @alloca_2(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[BB3:%.*]], label [[BB4:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    store i32 3, i32* [[P]]
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb4:
+; CHECK-NEXT:    store i32 5, i32* [[P]]
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    call void @use(i32* [[P]])
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32
+  store i32 1, i32* %P
+  br i1 %c.1, label %bb1, label %bb2
+
+bb1:
+  store i32 0, i32* %P
+  br label %bb5
+
+bb2:
+  br i1 %c.2, label %bb3, label %bb4
+
+bb3:
+  store i32 3, i32* %P
+  br label %bb5
+
+bb4:
+  store i32 5, i32* %P
+  br label %bb5
+
+bb5:
+  call void @use(i32* %P)
+  ret void
+}
+
+define void @alloca_3(i1 %c1) {
+; CHECK-LABEL: @alloca_3(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    call void @use(i32* [[P]])
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32
+  store i32 1, i32* %P
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  store i32 0, i32* %P
+  br label %bb5
+bb2:
+  br label %bb5
+
+bb5:
+  call void @use(i32* %P)
+  ret void
+}
+
+define void @alloca_4(i1 %c1) {
+; CHECK-LABEL: @alloca_4(
+; CHECK-NEXT:    [[P:%.*]] = alloca i32
+; CHECK-NEXT:    store i32 1, i32* [[P]]
+; CHECK-NEXT:    br i1 [[C1:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    store i32 0, i32* [[P]]
+; CHECK-NEXT:    call void @use(i32* [[P]])
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB5]]
+; CHECK:       bb5:
+; CHECK-NEXT:    ret void
+;
+  %P = alloca i32
+  store i32 1, i32* %P
+  br i1 %c1, label %bb1, label %bb2
+
+bb1:
+  store i32 0, i32* %P
+  call void @use(i32* %P)
+  br label %bb5
+
+bb2:
+  br label %bb5
+
+bb5:
+  ret void
+}
-- 
2.7.4