1 ; RUN: opt < %s -separate-const-offset-from-gep -reassociate-geps-verify-no-dead-code -S | FileCheck %s 2 3 ; Several unit tests for -separate-const-offset-from-gep. The transformation 4 ; heavily relies on TargetTransformInfo, so we put these tests under 5 ; target-specific folders. 6 7 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 8 ; target triple is necessary; otherwise TargetTransformInfo rejects any 9 ; addressing mode. 10 target triple = "nvptx64-unknown-unknown" 11 12 %struct.S = type { float, double } 13 14 @struct_array = global [1024 x %struct.S] zeroinitializer, align 16 15 @float_2d_array = global [32 x [32 x float]] zeroinitializer, align 4 16 17 ; We should not extract any struct field indices, because fields in a struct 18 ; may have different types. 19 define double* @struct(i32 %i) { 20 entry: 21 %add = add nsw i32 %i, 5 22 %idxprom = sext i32 %add to i64 23 %p = getelementptr inbounds [1024 x %struct.S], [1024 x %struct.S]* @struct_array, i64 0, i64 %idxprom, i32 1 24 ret double* %p 25 } 26 ; CHECK-LABEL: @struct( 27 ; CHECK: getelementptr [1024 x %struct.S], [1024 x %struct.S]* @struct_array, i64 0, i64 %{{[a-zA-Z0-9]+}}, i32 1 28 29 ; We should be able to trace into sext(a + b) if a + b is non-negative 30 ; (e.g., used as an index of an inbounds GEP) and one of a and b is 31 ; non-negative. 32 define float* @sext_add(i32 %i, i32 %j) { 33 entry: 34 %0 = add i32 %i, 1 35 %1 = sext i32 %0 to i64 ; inbound sext(i + 1) = sext(i) + 1 36 %2 = add i32 %j, -2 37 ; However, inbound sext(j + -2) != sext(j) + -2, e.g., j = INT_MIN 38 %3 = sext i32 %2 to i64 39 %p = getelementptr inbounds [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %1, i64 %3 40 ret float* %p 41 } 42 ; CHECK-LABEL: @sext_add( 43 ; CHECK-NOT: = add 44 ; CHECK: add i32 %j, -2 45 ; CHECK: sext 46 ; CHECK: getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %{{[a-zA-Z0-9]+}}, i64 %{{[a-zA-Z0-9]+}} 47 ; CHECK: getelementptr inbounds float, float* %{{[a-zA-Z0-9]+}}, i64 32 48 49 ; We should be able to trace into sext/zext if it can be distributed to both 50 ; operands, e.g., sext (add nsw a, b) == add nsw (sext a), (sext b) 51 ; 52 ; This test verifies we can transform 53 ; gep base, a + sext(b +nsw 1), c + zext(d +nuw 1) 54 ; to 55 ; gep base, a + sext(b), c + zext(d); gep ..., 1 * 32 + 1 56 define float* @ext_add_no_overflow(i64 %a, i32 %b, i64 %c, i32 %d) { 57 %b1 = add nsw i32 %b, 1 58 %b2 = sext i32 %b1 to i64 59 %i = add i64 %a, %b2 ; i = a + sext(b +nsw 1) 60 %d1 = add nuw i32 %d, 1 61 %d2 = zext i32 %d1 to i64 62 %j = add i64 %c, %d2 ; j = c + zext(d +nuw 1) 63 %p = getelementptr inbounds [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %i, i64 %j 64 ret float* %p 65 } 66 ; CHECK-LABEL: @ext_add_no_overflow( 67 ; CHECK: [[BASE_PTR:%[a-zA-Z0-9]+]] = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %{{[a-zA-Z0-9]+}}, i64 %{{[a-zA-Z0-9]+}} 68 ; CHECK: getelementptr inbounds float, float* [[BASE_PTR]], i64 33 69 70 ; Verifies we handle nested sext/zext correctly. 71 define void @sext_zext(i32 %a, i32 %b, float** %out1, float** %out2) { 72 entry: 73 %0 = add nsw nuw i32 %a, 1 74 %1 = sext i32 %0 to i48 75 %2 = zext i48 %1 to i64 ; zext(sext(a +nsw nuw 1)) = zext(sext(a)) + 1 76 %3 = add nsw i32 %b, 2 77 %4 = sext i32 %3 to i48 78 %5 = zext i48 %4 to i64 ; zext(sext(b +nsw 2)) != zext(sext(b)) + 2 79 %p1 = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %2, i64 %5 80 store float* %p1, float** %out1 81 %6 = add nuw i32 %a, 3 82 %7 = zext i32 %6 to i48 83 %8 = sext i48 %7 to i64 ; sext(zext(a +nuw 3)) = zext(a +nuw 3) = zext(a) + 3 84 %9 = add nsw i32 %b, 4 85 %10 = zext i32 %9 to i48 86 %11 = sext i48 %10 to i64 ; sext(zext(b +nsw 4)) != zext(b) + 4 87 %p2 = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %8, i64 %11 88 store float* %p2, float** %out2 89 ret void 90 } 91 ; CHECK-LABEL: @sext_zext( 92 ; CHECK: [[BASE_PTR_1:%[a-zA-Z0-9]+]] = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %{{[a-zA-Z0-9]+}}, i64 %{{[a-zA-Z0-9]+}} 93 ; CHECK: getelementptr float, float* [[BASE_PTR_1]], i64 32 94 ; CHECK: [[BASE_PTR_2:%[a-zA-Z0-9]+]] = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %{{[a-zA-Z0-9]+}}, i64 %{{[a-zA-Z0-9]+}} 95 ; CHECK: getelementptr float, float* [[BASE_PTR_2]], i64 96 96 97 ; Similar to @ext_add_no_overflow, we should be able to trace into s/zext if 98 ; its operand is an OR and the two operands of the OR have no common bits. 99 define float* @sext_or(i64 %a, i32 %b) { 100 entry: 101 %b1 = shl i32 %b, 2 102 %b2 = or i32 %b1, 1 ; (b << 2) and 1 have no common bits 103 %b3 = or i32 %b1, 4 ; (b << 2) and 4 may have common bits 104 %b2.ext = zext i32 %b2 to i64 105 %b3.ext = sext i32 %b3 to i64 106 %i = add i64 %a, %b2.ext 107 %j = add i64 %a, %b3.ext 108 %p = getelementptr inbounds [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %i, i64 %j 109 ret float* %p 110 } 111 ; CHECK-LABEL: @sext_or( 112 ; CHECK: [[BASE_PTR:%[a-zA-Z0-9]+]] = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %{{[a-zA-Z0-9]+}}, i64 %{{[a-zA-Z0-9]+}} 113 ; CHECK: getelementptr inbounds float, float* [[BASE_PTR]], i64 32 114 115 ; The subexpression (b + 5) is used in both "i = a + (b + 5)" and "*out = b + 116 ; 5". When extracting the constant offset 5, make sure "*out = b + 5" isn't 117 ; affected. 118 define float* @expr(i64 %a, i64 %b, i64* %out) { 119 entry: 120 %b5 = add i64 %b, 5 121 %i = add i64 %b5, %a 122 %p = getelementptr inbounds [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %i, i64 0 123 store i64 %b5, i64* %out 124 ret float* %p 125 } 126 ; CHECK-LABEL: @expr( 127 ; CHECK: [[BASE_PTR:%[a-zA-Z0-9]+]] = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %{{[a-zA-Z0-9]+}}, i64 0 128 ; CHECK: getelementptr inbounds float, float* [[BASE_PTR]], i64 160 129 ; CHECK: store i64 %b5, i64* %out 130 131 ; d + sext(a +nsw (b +nsw (c +nsw 8))) => (d + sext(a) + sext(b) + sext(c)) + 8 132 define float* @sext_expr(i32 %a, i32 %b, i32 %c, i64 %d) { 133 entry: 134 %0 = add nsw i32 %c, 8 135 %1 = add nsw i32 %b, %0 136 %2 = add nsw i32 %a, %1 137 %3 = sext i32 %2 to i64 138 %i = add i64 %d, %3 139 %p = getelementptr inbounds [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i64 %i 140 ret float* %p 141 } 142 ; CHECK-LABEL: @sext_expr( 143 ; CHECK: sext i32 144 ; CHECK: sext i32 145 ; CHECK: sext i32 146 ; CHECK: getelementptr inbounds float, float* %{{[a-zA-Z0-9]+}}, i64 8 147 148 ; Verifies we handle "sub" correctly. 149 define float* @sub(i64 %i, i64 %j) { 150 %i2 = sub i64 %i, 5 ; i - 5 151 %j2 = sub i64 5, %j ; 5 - i 152 %p = getelementptr inbounds [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %i2, i64 %j2 153 ret float* %p 154 } 155 ; CHECK-LABEL: @sub( 156 ; CHECK: %[[j2:[a-zA-Z0-9]+]] = sub i64 0, %j 157 ; CHECK: [[BASE_PTR:%[a-zA-Z0-9]+]] = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 %i, i64 %[[j2]] 158 ; CHECK: getelementptr inbounds float, float* [[BASE_PTR]], i64 -155 159 160 %struct.Packed = type <{ [3 x i32], [8 x i64] }> ; <> means packed 161 162 ; Verifies we can emit correct uglygep if the address is not natually aligned. 163 define i64* @packed_struct(i32 %i, i32 %j) { 164 entry: 165 %s = alloca [1024 x %struct.Packed], align 16 166 %add = add nsw i32 %j, 3 167 %idxprom = sext i32 %add to i64 168 %add1 = add nsw i32 %i, 1 169 %idxprom2 = sext i32 %add1 to i64 170 %arrayidx3 = getelementptr inbounds [1024 x %struct.Packed], [1024 x %struct.Packed]* %s, i64 0, i64 %idxprom2, i32 1, i64 %idxprom 171 ret i64* %arrayidx3 172 } 173 ; CHECK-LABEL: @packed_struct( 174 ; CHECK: [[BASE_PTR:%[a-zA-Z0-9]+]] = getelementptr [1024 x %struct.Packed], [1024 x %struct.Packed]* %s, i64 0, i64 %{{[a-zA-Z0-9]+}}, i32 1, i64 %{{[a-zA-Z0-9]+}} 175 ; CHECK: [[CASTED_PTR:%[a-zA-Z0-9]+]] = bitcast i64* [[BASE_PTR]] to i8* 176 ; CHECK: %uglygep = getelementptr inbounds i8, i8* [[CASTED_PTR]], i64 100 177 ; CHECK: bitcast i8* %uglygep to i64* 178 179 ; We shouldn't be able to extract the 8 from "zext(a +nuw (b + 8))", 180 ; because "zext(b + 8) != zext(b) + 8" 181 define float* @zext_expr(i32 %a, i32 %b) { 182 entry: 183 %0 = add i32 %b, 8 184 %1 = add nuw i32 %a, %0 185 %i = zext i32 %1 to i64 186 %p = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i64 %i 187 ret float* %p 188 } 189 ; CHECK-LABEL: zext_expr( 190 ; CHECK: getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i64 %i 191 192 ; Per http://llvm.org/docs/LangRef.html#id181, the indices of a off-bound gep 193 ; should be considered sign-extended to the pointer size. Therefore, 194 ; gep base, (add i32 a, b) != gep (gep base, i32 a), i32 b 195 ; because 196 ; sext(a + b) != sext(a) + sext(b) 197 ; 198 ; This test verifies we do not illegitimately extract the 8 from 199 ; gep base, (i32 a + 8) 200 define float* @i32_add(i32 %a) { 201 entry: 202 %i = add i32 %a, 8 203 %p = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i32 %i 204 ret float* %p 205 } 206 ; CHECK-LABEL: @i32_add( 207 ; CHECK: getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i64 %{{[a-zA-Z0-9]+}} 208 ; CHECK-NOT: getelementptr 209 210 ; Verifies that we compute the correct constant offset when the index is 211 ; sign-extended and then zero-extended. The old version of our code failed to 212 ; handle this case because it simply computed the constant offset as the 213 ; sign-extended value of the constant part of the GEP index. 214 define float* @apint(i1 %a) { 215 entry: 216 %0 = add nsw nuw i1 %a, 1 217 %1 = sext i1 %0 to i4 218 %2 = zext i4 %1 to i64 ; zext (sext i1 1 to i4) to i64 = 15 219 %p = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i64 %2 220 ret float* %p 221 } 222 ; CHECK-LABEL: @apint( 223 ; CHECK: [[BASE_PTR:%[a-zA-Z0-9]+]] = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i64 %{{[a-zA-Z0-9]+}} 224 ; CHECK: getelementptr float, float* [[BASE_PTR]], i64 15 225 226 ; Do not trace into binary operators other than ADD, SUB, and OR. 227 define float* @and(i64 %a) { 228 entry: 229 %0 = shl i64 %a, 2 230 %1 = and i64 %0, 1 231 %p = getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array, i64 0, i64 0, i64 %1 232 ret float* %p 233 } 234 ; CHECK-LABEL: @and( 235 ; CHECK: getelementptr [32 x [32 x float]], [32 x [32 x float]]* @float_2d_array 236 ; CHECK-NOT: getelementptr 237 238 ; The code that rebuilds an OR expression used to be buggy, and failed on this 239 ; test. 240 define float* @shl_add_or(i64 %a, float* %ptr) { 241 ; CHECK-LABEL: @shl_add_or( 242 entry: 243 %shl = shl i64 %a, 2 244 %add = add i64 %shl, 12 245 %or = or i64 %add, 1 246 ; CHECK: [[OR:%or[0-9]*]] = add i64 %shl, 1 247 ; ((a << 2) + 12) and 1 have no common bits. Therefore, 248 ; SeparateConstOffsetFromGEP is able to extract the 12. 249 ; TODO(jingyue): We could reassociate the expression to combine 12 and 1. 250 %p = getelementptr float, float* %ptr, i64 %or 251 ; CHECK: [[PTR:%[a-zA-Z0-9]+]] = getelementptr float, float* %ptr, i64 [[OR]] 252 ; CHECK: getelementptr float, float* [[PTR]], i64 12 253 ret float* %p 254 ; CHECK-NEXT: ret 255 } 256 257 ; The source code used to be buggy in checking 258 ; (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) 259 ; where AccumulativeByteOffset is signed but ElementTypeSizeOfGEP is unsigned. 260 ; The compiler would promote AccumulativeByteOffset to unsigned, causing 261 ; unexpected results. For example, while -64 % (int64_t)24 != 0, 262 ; -64 % (uint64_t)24 == 0. 263 %struct3 = type { i64, i32 } 264 %struct2 = type { %struct3, i32 } 265 %struct1 = type { i64, %struct2 } 266 %struct0 = type { i32, i32, i64*, [100 x %struct1] } 267 define %struct2* @sign_mod_unsign(%struct0* %ptr, i64 %idx) { 268 ; CHECK-LABEL: @sign_mod_unsign( 269 entry: 270 %arrayidx = add nsw i64 %idx, -2 271 ; CHECK-NOT: add 272 %ptr2 = getelementptr inbounds %struct0, %struct0* %ptr, i64 0, i32 3, i64 %arrayidx, i32 1 273 ; CHECK: [[PTR:%[a-zA-Z0-9]+]] = getelementptr %struct0, %struct0* %ptr, i64 0, i32 3, i64 %idx, i32 1 274 ; CHECK: [[PTR1:%[a-zA-Z0-9]+]] = bitcast %struct2* [[PTR]] to i8* 275 ; CHECK: getelementptr inbounds i8, i8* [[PTR1]], i64 -64 276 ; CHECK: bitcast 277 ret %struct2* %ptr2 278 ; CHECK-NEXT: ret 279 } 280
