1; RUN: opt -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output %s 2>&1 | FileCheck %s 2 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 sites 8; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 9; CHECK-NEXT: PartialAlias (off -6): i8* %gep.6, [16 x i8]* %ptr 10; CHECK-NEXT: MayAlias: i8* %gep.6, i8* %gep.idx 11; 12 load [16 x i8], ptr %ptr 13 %mul = mul i8 %idx, 5 14 %add = add i8 %mul, 2 15 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %add 16 store i8 0, ptr %gep.idx, align 1 17 %gep.6 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 6 18 store i8 1, ptr %gep.6, align 1 19 ret void 20} 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 sites 24; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 25; CHECK-NEXT: PartialAlias (off -6): i8* %gep.6, [16 x i8]* %ptr 26; CHECK-NEXT: NoAlias: i8* %gep.6, i8* %gep.idx 27; 28 load [16 x i8], ptr %ptr 29 %mul = mul nuw nsw i8 %idx, 5 30 %add = add nuw nsw i8 %mul, 2 31 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %add 32 store i8 0, ptr %gep.idx, align 1 33 %gep.6 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 6 34 store i8 1, ptr %gep.6, align 1 35 ret void 36} 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 sites 41; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 42; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 43; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 44; 45 load [16 x i8], ptr %ptr 46 %mul = mul i8 %idx, 5 47 %sub = sub i8 %mul, 1 48 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %sub 49 store i8 0, ptr %gep.idx, align 1 50 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3 51 store i8 1, ptr %gep.3, align 1 52 ret void 53} 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 sites 57; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 58; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 59; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 60; 61 load [16 x i8], ptr %ptr 62 %mul = mul nuw nsw i8 %idx, 5 63 %sub = sub nuw nsw i8 %mul, 1 64 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i8 %sub 65 store i8 0, ptr %gep.idx, align 1 66 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3 67 store i8 1, ptr %gep.3, align 1 68 ret void 69} 70 71; %gep.idx and %gep.3 must-alias if %mul overflows 72; (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 sites 75; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 76; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 77; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 78; 79 load [16 x i8], ptr %ptr 80 %mul = mul i64 %idx, 5 81 %sub = sub i64 %mul, 1 82 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 83 store i8 0, ptr %gep.idx, align 1 84 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 85 store i8 1, ptr %gep.3, align 1 86 ret void 87} 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 sites 91; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 92; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 93; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 94; 95 load [16 x i8], ptr %ptr 96 %mul = mul nuw nsw i64 %idx, 5 97 %sub = sub nuw nsw i64 %mul, 1 98 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 99 store i8 0, ptr %gep.idx, align 1 100 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 101 store i8 1, ptr %gep.3, align 1 102 ret void 103} 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 sites 107; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 108; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 109; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 110; 111 load [16 x i8], ptr %ptr 112 %mul = mul nsw i64 %idx, 5 113 %sub = sub nsw i64 %mul, 1 114 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 115 store i8 0, ptr %gep.idx, align 1 116 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 117 store i8 1, ptr %gep.3, align 1 118 ret void 119} 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 sites 123; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 124; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 125; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 126; 127 load [16 x i8], ptr %ptr 128 %mul = mul nuw i64 %idx, 5 129 %sub = sub nuw i64 %mul, 1 130 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 131 store i8 0, ptr %gep.idx, align 1 132 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 133 store i8 1, ptr %gep.3, align 1 134 ret void 135} 136 137; Even though the mul and sub may overflow %gep.idx and %gep.3 cannot alias 138; 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 sites 141; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 142; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 143; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 144; 145 load [16 x i8], ptr %ptr 146 %mul = mul i64 %idx, 8 147 %sub = sub i64 %mul, 1 148 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 149 store i8 0, ptr %gep.idx, align 1 150 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 151 store i8 1, ptr %gep.3, align 1 152 ret void 153} 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 sites 158; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 159; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 160; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 161; 162 load [16 x i8], ptr %ptr 163 %mul = mul i64 %idx, 8 164 %sub = sub nuw nsw i64 %mul, 1 165 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 166 store i8 0, ptr %gep.idx, align 1 167 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 168 store i8 1, ptr %gep.3, align 1 169 ret void 170} 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 sites 174; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 175; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 176; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 177; 178 load [16 x i8], ptr %ptr 179 %mul = shl i64 %idx, 2 180 %sub = sub i64 %mul, 1 181 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 182 store i8 0, ptr %gep.idx, align 1 183 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 184 store i8 1, ptr %gep.3, align 1 185 ret void 186} 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 sites 190; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 191; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 192; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 193; 194 load [16 x i8], ptr %ptr 195 %mul = shl i64 %idx, 3 196 %sub = sub nsw nuw i64 %mul, 1 197 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub 198 store i8 0, ptr %gep.idx, align 1 199 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 3 200 store i8 1, ptr %gep.3, align 1 201 ret void 202} 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 sites 207; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 208; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 209; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 210; 211 load [16 x i8], ptr %ptr 212 %mul = mul i32 %idx, 678152731 213 %sub = sub i32 %mul, 1582356375 214 %sub.ext = sext i32 %sub to i64 215 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext 216 store i8 0, ptr %gep.idx, align 1 217 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3 218 store i8 1, ptr %gep.3, align 1 219 ret void 220} 221 222define void @nuw_nsw_i32_sext(ptr %ptr, i32 %idx) { 223; CHECK-LABEL: Function: nuw_nsw_i32_sext: 3 pointers, 0 call sites 224; CHECK-NEXT: NoAlias: i8* %gep.idx, [16 x i8]* %ptr 225; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 226; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 227; 228 load [16 x i8], ptr %ptr 229 %mul = mul nuw nsw i32 %idx, 678152731 230 %sub = sub nuw nsw i32 %mul, 1582356375 231 %sub.ext = sext i32 %sub to i64 232 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext 233 store i8 0, ptr %gep.idx, align 1 234 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3 235 store i8 1, ptr %gep.3, align 1 236 ret void 237} 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 sites 242; CHECK-NEXT: MayAlias: i8* %gep.idx, [16 x i8]* %ptr 243; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 244; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 245; 246 load [16 x i8], ptr %ptr 247 %mul = mul i32 %idx, 678152731 248 %sub = sub i32 %mul, 1582356375 249 %sub.ext = zext i32 %sub to i64 250 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext 251 store i8 0, ptr %gep.idx, align 1 252 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3 253 store i8 1, ptr %gep.3, align 1 254 ret void 255} 256 257define void @nuw_nsw_i32_zext(ptr %ptr, i32 %idx) { 258; CHECK-LABEL: Function: nuw_nsw_i32_zext: 3 pointers, 0 call sites 259; CHECK-NEXT: NoAlias: i8* %gep.idx, [16 x i8]* %ptr 260; CHECK-NEXT: PartialAlias (off -3): i8* %gep.3, [16 x i8]* %ptr 261; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 262; 263 load [16 x i8], ptr %ptr 264 %mul = mul nuw nsw i32 %idx, 678152731 265 %sub = sub nuw nsw i32 %mul, 1582356375 266 %sub.ext = zext i32 %sub to i64 267 %gep.idx = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.ext 268 store i8 0, ptr %gep.idx, align 1 269 %gep.3 = getelementptr [16 x i8], ptr %ptr, i32 0, i32 3 270 store i8 1, ptr %gep.3, align 1 271 ret void 272} 273 274; %mul.1 and %sub.2 are equal, if %idx = 9, because %mul.1 overflows. Hence 275; %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 sites 278; CHECK-NEXT: MayAlias: i8* %gep.mul.1, [16 x i8]* %ptr 279; CHECK-NEXT: MayAlias: i8* %gep.sub.2, [16 x i8]* %ptr 280; CHECK-NEXT: MayAlias: i8* %gep.mul.1, i8* %gep.sub.2 281; 282 load [16 x i8], ptr %ptr 283 %mul.1 = mul i64 %idx, 6148914691236517207 284 %gep.mul.1 = getelementptr [16 x i8], ptr %ptr, i32 0, i64 %mul.1 285 store i8 1, ptr %gep.mul.1, align 1 286 %mul.2 = mul nsw i64 %idx, 3 287 %sub.2 = sub nsw i64 %mul.2, 12 288 %gep.sub.2= getelementptr [16 x i8], ptr %ptr, i32 0, i64 %sub.2 289 store i8 0, ptr %gep.sub.2, align 1 290 291 ret void 292} 293 294; %gep.1 and %gep.idx may alias, e.g. if %idx.1 = 8 and %idx.2 == 2. %gep.idx is then 295; (((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 sites 298; CHECK-NEXT: MustAlias: i8* %ptr, [200 x [6 x i8]]* %ptr 299; CHECK-NEXT: PartialAlias (off -6): i8* %gep.1, [200 x [6 x i8]]* %ptr 300; CHECK-NEXT: NoAlias: i8* %gep.1, i8* %ptr 301; CHECK-NEXT: MayAlias: i8* %gep.idx, [200 x [6 x i8]]* %ptr 302; CHECK-NEXT: MayAlias: i8* %gep.idx, i8* %ptr 303; CHECK-NEXT: MayAlias: i8* %gep.1, i8* %gep.idx 304; 305 load [200 x [6 x i8]], ptr %ptr 306 %idx.1.pos = icmp sge i64 %idx.1, 0 307 call void @llvm.assume(i1 %idx.1.pos) 308 %idx.2.pos = icmp sge i64 %idx.2, 0 309 call void @llvm.assume(i1 %idx.2.pos) 310 311 load i8, ptr %ptr 312 %gep.1 = getelementptr i8, ptr %ptr, i64 6 313 store i8 1, ptr %gep.1, align 1 314 315 %mul.0 = mul i64 %idx.1, -2 316 %add = add i64 %mul.0, 10 317 %gep.idx = getelementptr [ 200 x [ 6 x i8 ] ], ptr %ptr, i64 0, i64 %idx.2, i64 %add 318 store i8 0, ptr %gep.idx, align 1 319 ret void 320} 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 sites 325; CHECK-NEXT: MayAlias: [2000 x i8]* %arr, i8* %gep.idx 326; CHECK-NEXT: PartialAlias (off 917): [2000 x i8]* %arr, i8* %gep.917 327; CHECK-NEXT: MayAlias: i8* %gep.917, i8* %gep.idx 328; CHECK-NEXT: MustAlias: [2000 x i8]* %arr, i8* %gep.0 329; CHECK-NEXT: MayAlias: i8* %gep.0, i8* %gep.idx 330; CHECK-NEXT: NoAlias: i8* %gep.0, i8* %gep.917 331; 332 load [2000 x i8], ptr %arr 333 %or = or i64 %v, 1 334 %idx = mul i64 %or, 1844674407370955 335 %gep.idx = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i64 %idx 336 %l = load i8, ptr %gep.idx 337 %gep.917 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 917 338 store i8 0, ptr %gep.917 339 %gep.0 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 0 340 store i8 0, ptr %gep.0 341 ret i8 %l 342} 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 sites 346; CHECK-NEXT: NoAlias: [2000 x i8]* %arr, i8* %gep.idx 347; CHECK-NEXT: PartialAlias (off 917): [2000 x i8]* %arr, i8* %gep.917 348; CHECK-NEXT: NoAlias: i8* %gep.917, i8* %gep.idx 349; CHECK-NEXT: MustAlias: [2000 x i8]* %arr, i8* %gep.0 350; CHECK-NEXT: NoAlias: i8* %gep.0, i8* %gep.idx 351; CHECK-NEXT: NoAlias: i8* %gep.0, i8* %gep.917 352; 353 load [2000 x i8], ptr %arr 354 %or = or i64 %v, 1 355 %idx = mul nsw i64 %or, 1844674407370955 356 %gep.idx = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i64 %idx 357 %l = load i8, ptr %gep.idx 358 %gep.917 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 917 359 store i8 0, ptr %gep.917 360 %gep.0 = getelementptr inbounds [2000 x i8], ptr %arr, i32 0, i32 0 361 store i8 0, ptr %gep.0 362 ret i8 %l 363} 364 365define i8 @test_pr72831_may_wrap(i64 %off) { 366; CHECK-LABEL: Function: test_pr72831_may_wrap: 2 pointers, 0 call sites 367; CHECK-NEXT: MayAlias: i8* %gep, i8* %p 368entry: 369 %p = alloca [2 x i8], align 1 370 %ext = zext i1 false to i64 371 %add.1 = add nuw nsw i64 %off, 1 372 %add.2 = add nuw nsw i64 %add.1, %ext 373 %idx = shl i64 %add.2, 32 374 %gep = getelementptr inbounds [2 x i8], ptr %p, i64 0, i64 %idx 375 store i8 0, ptr %gep, align 1 376 %l = load i8, ptr %p, align 1 377 ret i8 %l 378} 379 380define i8 @test_pr72831_no_wrap(i64 %off) { 381; CHECK-LABEL: Function: test_pr72831_no_wrap: 2 pointers, 0 call sites 382; CHECK-NEXT: NoAlias: i8* %gep, i8* %p 383entry: 384 %p = alloca [2 x i8], align 1 385 %ext = zext i1 false to i64 386 %add.1 = add nuw nsw i64 %off, 1 387 %add.2 = add nuw nsw i64 %add.1, %ext 388 %idx = shl nsw nuw i64 %add.2, 32 389 %gep = getelementptr inbounds [2 x i8], ptr %p, i64 0, i64 %idx 390 store i8 0, ptr %gep, align 1 391 %l = load i8, ptr %p, align 1 392 ret i8 %l 393} 394 395declare void @llvm.assume(i1) 396