410 lines · plain
1; RUN: opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output %s 2>&1 | FileCheck %s2 3target datalayout = "p:64:64:64"4 5; %gep.idx and %gep.6 must-alias if %mul overflows (e.g. %idx == 52).6define void @may_overflow_mul_add_i8(ptr %ptr, i8 %idx) {7; CHECK-LABEL: Function: may_overflow_mul_add_i8: 3 pointers, 0 call sites8; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr9; CHECK-NEXT: PartialAlias (off -6): i8* %gep.6, [16 x i8]* %ptr10; CHECK-NEXT: MayAlias: i8* %gep.6, i8* %gep.idx11;12 load [16 x i8], ptr %ptr13 %mul = mul i8 %idx, 514 %add = add i8 %mul, 215 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %add16 store i8 0, ptr %gep.idx, align 117 %gep.6 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 618 store i8 1, ptr %gep.6, align 119 ret void20}21 22define void @nuw_nsw_mul_add_i8(ptr %ptr, i8 %idx) {23; CHECK-LABEL: Function: nuw_nsw_mul_add_i8: 3 pointers, 0 call sites24; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr25; CHECK-NEXT: PartialAlias (off -6): i8* %gep.6, [16 x i8]* %ptr26; CHECK-NEXT: NoAlias: i8* %gep.6, i8* %gep.idx27;28 load [16 x i8], ptr %ptr29 %mul = mul nuw nsw i8 %idx, 530 %add = add nuw nsw i8 %mul, 231 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %add32 store i8 0, ptr %gep.idx, align 133 %gep.6 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 634 store i8 1, ptr %gep.6, align 135 ret void36}37 38; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 52).39define void @may_overflow_mul_sub_i8(ptr %ptr, i8 %idx) {40; CHECK-LABEL: Function: may_overflow_mul_sub_i8: 3 pointers, 0 call sites41; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr42; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr43; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx44;45 load [16 x i8], ptr %ptr46 %mul = mul i8 %idx, 547 %sub = sub i8 %mul, 148 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %sub49 store i8 0, ptr %gep.idx, align 150 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 351 store i8 1, ptr %gep.3, align 152 ret void53}54 55define void @nuw_nsw_mul_sub_i8(ptr %ptr, i8 %idx) {56; CHECK-LABEL: Function: nuw_nsw_mul_sub_i8: 3 pointers, 0 call sites57; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr58; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr59; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx60;61 load [16 x i8], ptr %ptr62 %mul = mul nuw nsw i8 %idx, 563 %sub = sub nuw nsw i8 %mul, 164 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %sub65 store i8 0, ptr %gep.idx, align 166 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 367 store i8 1, ptr %gep.3, align 168 ret void69}70 71; %gep.idx and %gep.3 must-alias if %mul overflows72; (e.g. %idx == 3689348814741910323).73define void @may_overflow_mul_sub_i64(ptr %ptr, i64 %idx) {74; CHECK-LABEL: Function: may_overflow_mul_sub_i64: 3 pointers, 0 call sites75; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr76; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr77; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx78;79 load [16 x i8], ptr %ptr80 %mul = mul i64 %idx, 581 %sub = sub i64 %mul, 182 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub83 store i8 0, ptr %gep.idx, align 184 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 385 store i8 1, ptr %gep.3, align 186 ret void87}88 89define void @nuw_nsw_mul_sub_i64(ptr %ptr, i64 %idx) {90; CHECK-LABEL: Function: nuw_nsw_mul_sub_i64: 3 pointers, 0 call sites91; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr92; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr93; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx94;95 load [16 x i8], ptr %ptr96 %mul = mul nuw nsw i64 %idx, 597 %sub = sub nuw nsw i64 %mul, 198 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub99 store i8 0, ptr %gep.idx, align 1100 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3101 store i8 1, ptr %gep.3, align 1102 ret void103}104 105define void @only_nsw_mul_sub_i64(ptr %ptr, i64 %idx) {106; CHECK-LABEL: Function: only_nsw_mul_sub_i64: 3 pointers, 0 call sites107; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr108; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr109; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx110;111 load [16 x i8], ptr %ptr112 %mul = mul nsw i64 %idx, 5113 %sub = sub nsw i64 %mul, 1114 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub115 store i8 0, ptr %gep.idx, align 1116 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3117 store i8 1, ptr %gep.3, align 1118 ret void119}120 121define void @only_nuw_mul_sub_i64(ptr %ptr, i64 %idx) {122; CHECK-LABEL: Function: only_nuw_mul_sub_i64: 3 pointers, 0 call sites123; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr124; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr125; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx126;127 load [16 x i8], ptr %ptr128 %mul = mul nuw i64 %idx, 5129 %sub = sub nuw i64 %mul, 1130 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub131 store i8 0, ptr %gep.idx, align 1132 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3133 store i8 1, ptr %gep.3, align 1134 ret void135}136 137; Even though the mul and sub may overflow %gep.idx and %gep.3 cannot alias138; because we multiply by a power-of-2.139define void @may_overflow_mul_pow2_sub_i64(ptr %ptr, i64 %idx) {140; CHECK-LABEL: Function: may_overflow_mul_pow2_sub_i64: 3 pointers, 0 call sites141; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr142; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr143; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx144;145 load [16 x i8], ptr %ptr146 %mul = mul i64 %idx, 8147 %sub = sub i64 %mul, 1148 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub149 store i8 0, ptr %gep.idx, align 1150 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3151 store i8 1, ptr %gep.3, align 1152 ret void153}154 155; Multiplies by power-of-2 preserves modulo and the sub does not wrap.156define void @mul_pow2_sub_nsw_nuw_i64(ptr %ptr, i64 %idx) {157; CHECK-LABEL: Function: mul_pow2_sub_nsw_nuw_i64: 3 pointers, 0 call sites158; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr159; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr160; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx161;162 load [16 x i8], ptr %ptr163 %mul = mul i64 %idx, 8164 %sub = sub nuw nsw i64 %mul, 1165 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub166 store i8 0, ptr %gep.idx, align 1167 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3168 store i8 1, ptr %gep.3, align 1169 ret void170}171 172define void @may_overflow_shl_sub_i64(ptr %ptr, i64 %idx) {173; CHECK-LABEL: Function: may_overflow_shl_sub_i64: 3 pointers, 0 call sites174; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr175; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr176; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx177;178 load [16 x i8], ptr %ptr179 %mul = shl i64 %idx, 2180 %sub = sub i64 %mul, 1181 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub182 store i8 0, ptr %gep.idx, align 1183 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3184 store i8 1, ptr %gep.3, align 1185 ret void186}187 188define void @shl_sub_nsw_nuw_i64(ptr %ptr, i64 %idx) {189; CHECK-LABEL: Function: shl_sub_nsw_nuw_i64: 3 pointers, 0 call sites190; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr191; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr192; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx193;194 load [16 x i8], ptr %ptr195 %mul = shl i64 %idx, 3196 %sub = sub nsw nuw i64 %mul, 1197 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub198 store i8 0, ptr %gep.idx, align 1199 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3200 store i8 1, ptr %gep.3, align 1201 ret void202}203 204; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 110).205define void @may_overflow_i32_sext(ptr %ptr, i32 %idx) {206; CHECK-LABEL: Function: may_overflow_i32_sext: 3 pointers, 0 call sites207; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr208; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr209; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx210;211 load [16 x i8], ptr %ptr212 %mul = mul i32 %idx, 678152731213 %sub = sub i32 %mul, 1582356375214 %sub.ext = sext i32 %sub to i64215 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext216 store i8 0, ptr %gep.idx, align 1217 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3218 store i8 1, ptr %gep.3, align 1219 ret void220}221 222define void @nuw_nsw_i32_sext(ptr %ptr, i32 %idx) {223; CHECK-LABEL: Function: nuw_nsw_i32_sext: 3 pointers, 0 call sites224; CHECK-NEXT: NoAlias: i8* %gep.idx, [16 x i8]* %ptr225; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr226; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx227;228 load [16 x i8], ptr %ptr229 %mul = mul nuw nsw i32 %idx, 678152731230 %sub = sub nuw nsw i32 %mul, 1582356375231 %sub.ext = sext i32 %sub to i64232 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext233 store i8 0, ptr %gep.idx, align 1234 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3235 store i8 1, ptr %gep.3, align 1236 ret void237}238 239; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 110).240define void @may_overflow_i32_zext(ptr %ptr, i32 %idx) {241; CHECK-LABEL: Function: may_overflow_i32_zext: 3 pointers, 0 call sites242; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr243; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr244; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx245;246 load [16 x i8], ptr %ptr247 %mul = mul i32 %idx, 678152731248 %sub = sub i32 %mul, 1582356375249 %sub.ext = zext i32 %sub to i64250 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext251 store i8 0, ptr %gep.idx, align 1252 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3253 store i8 1, ptr %gep.3, align 1254 ret void255}256 257define void @nuw_nsw_i32_zext(ptr %ptr, i32 %idx) {258; CHECK-LABEL: Function: nuw_nsw_i32_zext: 3 pointers, 0 call sites259; CHECK-NEXT: NoAlias: i8* %gep.idx, [16 x i8]* %ptr260; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr261; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx262;263 load [16 x i8], ptr %ptr264 %mul = mul nuw nsw i32 %idx, 678152731265 %sub = sub nuw nsw i32 %mul, 1582356375266 %sub.ext = zext i32 %sub to i64267 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext268 store i8 0, ptr %gep.idx, align 1269 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3270 store i8 1, ptr %gep.3, align 1271 ret void272}273 274; %mul.1 and %sub.2 are equal, if %idx = 9, because %mul.1 overflows. Hence275; %gep.mul.1 and %gep.sub.2 may alias.276define void @may_overflow_pointer_diff(ptr %ptr, i64 %idx) {277; CHECK-LABEL: Function: may_overflow_pointer_diff: 3 pointers, 0 call sites278; CHECK-NEXT: MayAlias: i8* %gep.mul.1, [16 x i8]* %ptr279; CHECK-NEXT: MayAlias: i8* %gep.sub.2, [16 x i8]* %ptr280; CHECK-NEXT: MayAlias: i8* %gep.mul.1, i8* %gep.sub.2281;282 load [16 x i8], ptr %ptr283 %mul.1 = mul i64 %idx, 6148914691236517207284 %gep.mul.1 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %mul.1285 store i8 1, ptr %gep.mul.1, align 1286 %mul.2 = mul nsw i64 %idx, 3287 %sub.2 = sub nsw i64 %mul.2, 12288 %gep.sub.2= getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.2289 store i8 0, ptr %gep.sub.2, align 1290 291 ret void292}293 294; %gep.1 and %gep.idx may alias, e.g. if %idx.1 = 8 and %idx.2 == 2. %gep.idx is then295; (((18446744073709551614 * 8) % 2^64 + 6 * 2) % 2^64 + 10) % 2^64 == 6.296define void @may_overflow_mul_scale_neg(ptr %ptr, i64 %idx.1,i64 %idx.2) {297; CHECK-LABEL: Function: may_overflow_mul_scale_neg: 4 pointers, 2 call sites298; CHECK-NEXT: MustAlias: i8* %ptr, [200 x [6 x i8]]* %ptr299; CHECK-NEXT: PartialAlias (off -6): i8* %gep.1, [200 x [6 x i8]]* %ptr300; CHECK-NEXT: NoAlias: i8* %gep.1, i8* %ptr301; CHECK-NEXT: MayAlias: i8* %gep.idx, [200 x [6 x i8]]* %ptr302; CHECK-NEXT: MayAlias: i8* %gep.idx, i8* %ptr303; CHECK-NEXT: MayAlias: i8* %gep.1, i8* %gep.idx304;305 load [200 x [6 x i8]], ptr %ptr306 %idx.1.pos = icmp sge i64 %idx.1, 0307 call void @llvm.assume(i1 %idx.1.pos)308 %idx.2.pos = icmp sge i64 %idx.2, 0309 call void @llvm.assume(i1 %idx.2.pos)310 311 load i8, ptr %ptr312 %gep.1 = getelementptr i8, ptr %ptr, i64 6313 store i8 1, ptr %gep.1, align 1314 315 %mul.0 = mul i64 %idx.1, -2316 %add = add i64 %mul.0, 10317 %gep.idx = getelementptr [ 200 x [ 6 x i8 ] ], ptr %ptr, i64 0, i64 %idx.2, i64 %add318 store i8 0, ptr %gep.idx, align 1319 ret void320}321 322; If %v == 10581764700698480926, %idx == 917, so %gep.917 and %gep.idx may alias.323define i8 @mul_may_overflow_var_nonzero_minabsvarindex_one_index(ptr %arr, i8 %x, i64 %v) {324; CHECK-LABEL: Function: mul_may_overflow_var_nonzero_minabsvarindex_one_index: 4 pointers, 0 call sites325; CHECK-NEXT: MayAlias: [2000 x i8]* %arr, i8* %gep.idx326; CHECK-NEXT: PartialAlias (off 917): [2000 x i8]* %arr, i8* %gep.917327; CHECK-NEXT: MayAlias: i8* %gep.917, i8* %gep.idx328; CHECK-NEXT: MustAlias: [2000 x i8]* %arr, i8* %gep.0329; CHECK-NEXT: MayAlias: i8* %gep.0, i8* %gep.idx330; CHECK-NEXT: NoAlias: i8* %gep.0, i8* %gep.917331;332 load [2000 x i8], ptr %arr333 %or = or i64 %v, 1334 %idx = mul i64 %or, 1844674407370955335 %gep.idx = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i64 %idx336 %l = load i8, ptr %gep.idx337 %gep.917 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 917338 store i8 0, ptr %gep.917339 %gep.0 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 0340 store i8 0, ptr %gep.0341 ret i8 %l342}343 344define i8 @mul_nsw_var_nonzero_minabsvarindex_one_index(ptr %arr, i8 %x, i64 %v) {345; CHECK-LABEL: Function: mul_nsw_var_nonzero_minabsvarindex_one_index: 4 pointers, 0 call sites346; CHECK-NEXT: NoAlias: [2000 x i8]* %arr, i8* %gep.idx347; CHECK-NEXT: PartialAlias (off 917): [2000 x i8]* %arr, i8* %gep.917348; CHECK-NEXT: NoAlias: i8* %gep.917, i8* %gep.idx349; CHECK-NEXT: MustAlias: [2000 x i8]* %arr, i8* %gep.0350; CHECK-NEXT: NoAlias: i8* %gep.0, i8* %gep.idx351; CHECK-NEXT: NoAlias: i8* %gep.0, i8* %gep.917352;353 load [2000 x i8], ptr %arr354 %or = or i64 %v, 1355 %idx = mul nsw i64 %or, 1844674407370955356 %gep.idx = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i64 %idx357 %l = load i8, ptr %gep.idx358 %gep.917 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 917359 store i8 0, ptr %gep.917360 %gep.0 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 0361 store i8 0, ptr %gep.0362 ret i8 %l363}364 365define i8 @test_pr72831_may_wrap(i64 %off) {366; CHECK-LABEL: Function: test_pr72831_may_wrap: 2 pointers, 0 call sites367; CHECK-NEXT: MayAlias: i8* %gep, i8* %p368entry:369 %p = alloca [2 x i8], align 1370 %ext = zext i1 false to i64371 %add.1 = add nuw nsw i64 %off, 1372 %add.2 = add nuw nsw i64 %add.1, %ext373 %idx = shl i64 %add.2, 32374 %gep = getelementptr inbounds [2 x i8], ptr %p, i64 0, i64 %idx375 store i8 0, ptr %gep, align 1376 %l = load i8, ptr %p, align 1377 ret i8 %l378}379 380define i8 @test_pr72831_no_wrap(i64 %off) {381; CHECK-LABEL: Function: test_pr72831_no_wrap: 2 pointers, 0 call sites382; CHECK-NEXT: NoAlias: i8* %gep, i8* %p383entry:384 %p = alloca [2 x i8], align 1385 %ext = zext i1 false to i64386 %add.1 = add nuw nsw i64 %off, 1387 %add.2 = add nuw nsw i64 %add.1, %ext388 %idx = shl nsw nuw i64 %add.2, 32389 %gep = getelementptr inbounds [2 x i8], ptr %p, i64 0, i64 %idx390 store i8 0, ptr %gep, align 1391 %l = load i8, ptr %p, align 1392 ret i8 %l393}394 395declare void @llvm.assume(i1)396 397define i64 @mul_may_overflow_var_nonzero_minabsvarindex_two_index(i64 %arg, ptr %arg1) {398; CHECK-LABEL: Function: mul_may_overflow_var_nonzero_minabsvarindex_two_index399; CHECK-LABEL: MayAlias: i64* %getelementptr, i64* %getelementptr2400bb:401 %xor = xor i64 %arg, -9223372036854775808402 %getelementptr = getelementptr i64, ptr %arg1, i64 %xor403 %load = load i64, ptr %getelementptr, align 8404 %getelementptr2 = getelementptr i64, ptr %arg1, i64 %arg405 store i64 1, ptr %getelementptr2, align 8406 %load3 = load i64, ptr %getelementptr, align 8407 %mul = mul i64 %load, %load3408 ret i64 %mul409}410