Use minimal types for generated expressions

  We now use the minimal necessary bit width for the generated code. If
  operations might overflow (add/sub/mul) we will try to adjust the types in
  order to ensure a non-wrapping computation. If the type adjustment is not
  possible, thus the necessary type is bigger than the type value of
  --polly-max-expr-bit-width, we will use assumptions to verify the computation
  will not wrap. However, for run-time checks we cannot build assumptions but
  instead utilize overflow tracking intrinsics.

llvm-svn: 271878

7 files changed, 62 insertions, 41 deletions

diff --git a/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll b/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll
index 4bb9cee8335..f68df2283f2 100644
--- a/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/codegen_address_space.ll
@@ -40,5 +40,5 @@ for.end:                                          ; preds = %for.cond
 }
 
 ; CHECK: %polly.access.cast.A = bitcast [100 x i32] addrspace(5)* %A to i32 addrspace(5)*
-; CHECK: %polly.access.A = getelementptr i32, i32 addrspace(5)* %polly.access.cast.A, i64 0
+; CHECK: %polly.access.A = getelementptr i32, i32 addrspace(5)* %polly.access.cast.A, i1 false
 ; CHECK: %tmp2_p_scalar_ = load i32, i32 addrspace(5)* %polly.access.A, align 4, !alias.scope !0, !noalias !2
diff --git a/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md.ll b/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md.ll
index 9a86b7fb920..81aa8b2c16a 100644
--- a/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md.ll
@@ -54,19 +54,28 @@ for.end6:                                         ; preds = %for.cond
   ret i32 0
 }
 
-; WITHCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
-; WITHCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
-; WITHCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
-; WITHCONST:  %[[SUM2:[._a-zA-Z0-9]+]] = add nsw i64 %[[SUM1]], 5
-; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr i32, i32* getelementptr inbounds ([1040 x i32], [1040 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i64 %[[SUM2]]
+; WITHCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHCONST:  %[[IVOutSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVOut]] to i12
+; WITHCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i12 16, %[[IVOutSext]]
+; WITHCONST:  %[[IVInSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVIn]] to i9
+; WITHCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i9 2, %[[IVInSext]]
+; WITHCONST:  %[[MUL1Sext:[._a-zA-Z0-9]+]] = sext i12 %[[MUL1]] to i13
+; WITHCONST:  %[[MUL2Sext:[._a-zA-Z0-9]+]] = sext i9 %[[MUL2]] to i13
+; WITHCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i13 %[[MUL1Sext]], %[[MUL2Sext]]
+; WITHCONST:  %[[SUM1Sext:[._a-zA-Z0-9]+]] = sext i13 %[[SUM1]] to i14
+; WITHCONST:  %[[SUM2:[._a-zA-Z0-9]+]] = add nsw i14 %[[SUM1Sext]], 5
+; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr i32, i32* getelementptr inbounds ([1040 x i32], [1040 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i14 %[[SUM2]]
 ; WITHCONST:  store i32 100, i32* %[[ACC]]
 
-; WITHOUTCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHOUTCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHOUTCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
-; WITHOUTCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
-; WITHOUTCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
-; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr i32, i32* getelementptr inbounds ([1040 x i32], [1040 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i64 %[[SUM1]]
+; WITHOUTCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHOUTCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHOUTCONST:  %[[IVOutSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVOut]] to i12
+; WITHOUTCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i12 16, %[[IVOutSext]]
+; WITHOUTCONST:  %[[IVInSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVIn]] to i9
+; WITHOUTCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i9 2, %[[IVInSext]]
+; WITHOUTCONST:  %[[MUL1Sext:[._a-zA-Z0-9]+]] = sext i12 %[[MUL1]] to i13
+; WITHOUTCONST:  %[[MUL2Sext:[._a-zA-Z0-9]+]] = sext i9 %[[MUL2]] to i13
+; WITHOUTCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i13 %[[MUL1Sext]], %[[MUL2Sext]]
+; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr i32, i32* getelementptr inbounds ([1040 x i32], [1040 x i32]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i13 %[[SUM1]]
 ; WITHOUTCONST:  store i32 100, i32* %[[ACC]]
diff --git a/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md_float.ll b/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md_float.ll
index 942e4c488ee..dd4b962149a 100644
--- a/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md_float.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/codegen_simple_md_float.ll
@@ -51,19 +51,28 @@ for.end6:                                         ; preds = %for.cond
   ret void
 }
 
-; WITHCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
-; WITHCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
-; WITHCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
-; WITHCONST:  %[[SUM2:[._a-zA-Z0-9]+]] = add nsw i64 %[[SUM1]], 5
-; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr float, float* getelementptr inbounds ([1040 x float], [1040 x float]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i64 %[[SUM2]]
+; WITHCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHCONST:  %[[IVOutSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVOut]] to i12
+; WITHCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i12 16, %[[IVOutSext]]
+; WITHCONST:  %[[IVInSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVIn]] to i9
+; WITHCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i9 2, %[[IVInSext]]
+; WITHCONST:  %[[MUL1Sext:[._a-zA-Z0-9]+]] = sext i12 %[[MUL1]] to i13
+; WITHCONST:  %[[MUL2Sext:[._a-zA-Z0-9]+]] = sext i9 %[[MUL2]] to i13
+; WITHCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i13 %[[MUL1Sext]], %[[MUL2Sext]]
+; WITHCONST:  %[[SUM1Sext:[._a-zA-Z0-9]+]] = sext i13 %[[SUM1]] to i14
+; WITHCONST:  %[[SUM2:[._a-zA-Z0-9]+]] = add nsw i14 %[[SUM1Sext]], 5
+; WITHCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr float, float* getelementptr inbounds ([1040 x float], [1040 x float]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i14 %[[SUM2]]
 ; WITHCONST:  store float 1.000000e+02, float* %[[ACC]]
 
-; WITHOUTCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHOUTCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i64 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
-; WITHOUTCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i64 16, %[[IVOut]]
-; WITHOUTCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i64 2, %[[IVIn]]
-; WITHOUTCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i64 %[[MUL1]], %[[MUL2]]
-; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr float, float* getelementptr inbounds ([1040 x float], [1040 x float]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i64 %[[SUM1]]
+; WITHOUTCONST:  %[[IVOut:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHOUTCONST:  %[[IVIn:polly.indvar[0-9]*]] = phi i6 [ 0, %polly.loop_preheader{{[0-9]*}} ], [ %polly.indvar_next{{[0-9]*}}, %polly.{{[._a-zA-Z0-9]*}} ]
+; WITHOUTCONST:  %[[IVOutSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVOut]] to i12
+; WITHOUTCONST:  %[[MUL1:[._a-zA-Z0-9]+]] = mul nsw i12 16, %[[IVOutSext]]
+; WITHOUTCONST:  %[[IVInSext:[._a-zA-Z0-9]+]] = sext i6 %[[IVIn]] to i9
+; WITHOUTCONST:  %[[MUL2:[._a-zA-Z0-9]+]] = mul nsw i9 2, %[[IVInSext]]
+; WITHOUTCONST:  %[[MUL1Sext:[._a-zA-Z0-9]+]] = sext i12 %[[MUL1]] to i13
+; WITHOUTCONST:  %[[MUL2Sext:[._a-zA-Z0-9]+]] = sext i9 %[[MUL2]] to i13
+; WITHOUTCONST:  %[[SUM1:[._a-zA-Z0-9]+]] = add nsw i13 %[[MUL1Sext]], %[[MUL2Sext]]
+; WITHOUTCONST:  %[[ACC:[._a-zA-Z0-9]*]] = getelementptr float, float* getelementptr inbounds ([1040 x float], [1040 x float]* @A, i{{(32|64)}} 0, i{{(32|64)}} 0), i13 %[[SUM1]]
 ; WITHOUTCONST:  store float 1.000000e+02, float* %[[ACC]]
diff --git a/polly/test/Isl/CodeGen/MemAccess/different_types.ll b/polly/test/Isl/CodeGen/MemAccess/different_types.ll
index 527c6ceaa00..51bb3c2ac2a 100644
--- a/polly/test/Isl/CodeGen/MemAccess/different_types.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/different_types.ll
@@ -10,9 +10,11 @@
 ;    }
 
 ; CHECK: %polly.access.cast.A14 = bitcast float* %A to i32*
-; CHECK: %[[R1:[._0-9]*]] = sub nsw i64 0, %polly.indvar11
-; CHECK: %[[R2:[._0-9]*]] = add nsw i64 %[[R1]], 99
-; CHECK: %polly.access.A15 = getelementptr i32, i32* %polly.access.cast.A14, i64 %[[R2]]
+; CHECK: %[[R0:[._0-9]*]] = sext i8 %polly.indvar11 to i9
+; CHECK: %[[R1:[._0-9]*]] = sub nsw i9 0, %[[R0]]
+; CHECK: %[[R1s:[._0-9]*]] = sext i9 %[[R1]] to i10
+; CHECK: %[[R2:[._0-9]*]] = add nsw i10 %[[R1s]], 99
+; CHECK: %polly.access.A15 = getelementptr i32, i32* %polly.access.cast.A14, i10 %[[R2]]
 ; CHECK: %[[R3:[._0-9]*]] = bitcast i32* %polly.access.A15 to float*
 ; CHECK: %tmp14_p_scalar_ = load float, float* %[[R3]], align 4, !alias.scope !3, !noalias !4
 
diff --git a/polly/test/Isl/CodeGen/MemAccess/multiple_types.ll b/polly/test/Isl/CodeGen/MemAccess/multiple_types.ll
index 9a97e3f7385..53e319872cb 100644
--- a/polly/test/Isl/CodeGen/MemAccess/multiple_types.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/multiple_types.ll
@@ -12,20 +12,21 @@
 ;    }
 
 ; Short[0]
-; CHECK: %polly.access.Short10 = getelementptr i8, i8* %Short, i64 0
+; CHECK: %polly.access.Short10 = getelementptr i8, i8* %Short, i1 false
 ; CHECK: %24 = bitcast i8* %polly.access.Short10 to i16*
 ; CHECK: %tmp5_p_scalar_ = load i16, i16* %24
 
 ; Float[8 * i]
-; CHECK: %25 = mul nsw i64 8, %polly.indvar
-; CHECK: %polly.access.Float11 = getelementptr i8, i8* %Float, i64 %25
-; CHECK: %26 = bitcast i8* %polly.access.Float11 to float*
-; CHECK: %tmp11_p_scalar_ = load float, float* %26
+; CHECK: %26 = sext i8 %polly.indvar to i13
+; CHECK: %27 = mul nsw i13 8, %26
+; CHECK: %polly.access.Float11 = getelementptr i8, i8* %Float, i13 %27
+; CHECK: %28 = bitcast i8* %polly.access.Float11 to float*
+; CHECK: %tmp11_p_scalar_ = load float, float* %28
 
 ; Double[8]
-; CHECK: %polly.access.Double13 = getelementptr i8, i8* %Double, i64 8
-; CHECK: %27 = bitcast i8* %polly.access.Double13 to double*
-; CHECK: %tmp17_p_scalar_ = load double, double* %27
+; CHECK: %polly.access.Double13 = getelementptr i8, i8* %Double, i5 8
+; CHECK: %30 = bitcast i8* %polly.access.Double13 to double*
+; CHECK: %tmp17_p_scalar_ = load double, double* %30
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/Isl/CodeGen/MemAccess/simple_stride_test.ll b/polly/test/Isl/CodeGen/MemAccess/simple_stride_test.ll
index afa4fcaf610..937a526a7ca 100644
--- a/polly/test/Isl/CodeGen/MemAccess/simple_stride_test.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/simple_stride_test.ll
@@ -4,12 +4,12 @@
 ;    stride zero for B
 ;    stride one for A
 ;
-; CHECK:  %polly.access.B = getelementptr i32, i32* %B, i64 0
+; CHECK:  %polly.access.B = getelementptr i32, i32* %B, i1 false
 ; CHECK:  %[[BC:[._a-zA-Z0-9]*]] = bitcast i32* %polly.access.B to <1 x i32>*
 ; CHECK:  %[[LD:[._a-zA-Z0-9]*]] = load <1 x i32>, <1 x i32>* %[[BC]], align 8
 ; CHECK:  %[[SV:[._a-zA-Z0-9]*]] = shufflevector <1 x i32> %[[LD]], <1 x i32> %[[LD]], <16 x i32> zeroinitializer
 ;
-; CHECK:  %polly.access.A = getelementptr i32, i32* %A, i64 0
+; CHECK:  %polly.access.A = getelementptr i32, i32* %A, i5 0
 ; CHECK:  %[[VP:[._a-zA-Z0-9]*]] = bitcast i32* %polly.access.A to <16 x i32>*
 ; CHECK:  store <16 x i32> %[[SV]], <16 x i32>* %[[VP]], align 8
 ;
diff --git a/polly/test/Isl/CodeGen/MemAccess/update_access_functions.ll b/polly/test/Isl/CodeGen/MemAccess/update_access_functions.ll
index 63f2edac0f9..9a35a233142 100644
--- a/polly/test/Isl/CodeGen/MemAccess/update_access_functions.ll
+++ b/polly/test/Isl/CodeGen/MemAccess/update_access_functions.ll
@@ -3,7 +3,7 @@
 ; RUN:                 < %s -S | FileCheck %s
 
 ; CHECK: polly.stmt.loop2:
-; CHECK-NEXT:   %polly.access.A = getelementptr double, double* %A, i64 42
+; CHECK-NEXT:   %polly.access.A = getelementptr double, double* %A, i7 42
 ; CHECK-NEXT:   %val_p_scalar_ = load double, double* %polly.access.A
 
 ; CHECK: polly.stmt.loop3: