1; RUN: opt -basic-aa -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([16 x i8]* %ptr, i8 %idx) { 7; CHECK-LABEL: Function: may_overflow_mul_add_i8: 3 pointers, 0 call sites 8; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 9; CHECK-NEXT: PartialAlias (off 6): [16 x i8]* %ptr, i8* %gep.6 10; CHECK-NEXT: MayAlias: i8* %gep.6, i8* %gep.idx 11; 12 %mul = mul i8 %idx, 5 13 %add = add i8 %mul, 2 14 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i8 %add 15 store i8 0, i8* %gep.idx, align 1 16 %gep.6 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 6 17 store i8 1, i8* %gep.6, align 1 18 ret void 19} 20 21define void @nuw_nsw_mul_add_i8([16 x i8]* %ptr, i8 %idx) { 22; CHECK-LABEL: Function: nuw_nsw_mul_add_i8: 3 pointers, 0 call sites 23; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 24; CHECK-NEXT: PartialAlias (off 6): [16 x i8]* %ptr, i8* %gep.6 25; CHECK-NEXT: NoAlias: i8* %gep.6, i8* %gep.idx 26; 27 %mul = mul nuw nsw i8 %idx, 5 28 %add = add nuw nsw i8 %mul, 2 29 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i8 %add 30 store i8 0, i8* %gep.idx, align 1 31 %gep.6 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 6 32 store i8 1, i8* %gep.6, align 1 33 ret void 34} 35 36; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 52). 37define void @may_overflow_mul_sub_i8([16 x i8]* %ptr, i8 %idx) { 38; CHECK-LABEL: Function: may_overflow_mul_sub_i8: 3 pointers, 0 call sites 39; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 40; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 41; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 42; 43 %mul = mul i8 %idx, 5 44 %sub = sub i8 %mul, 1 45 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i8 %sub 46 store i8 0, i8* %gep.idx, align 1 47 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 3 48 store i8 1, i8* %gep.3, align 1 49 ret void 50} 51 52define void @nuw_nsw_mul_sub_i8([16 x i8]* %ptr, i8 %idx) { 53; CHECK-LABEL: Function: nuw_nsw_mul_sub_i8: 3 pointers, 0 call sites 54; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 55; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 56; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 57; 58 %mul = mul nuw nsw i8 %idx, 5 59 %sub = sub nuw nsw i8 %mul, 1 60 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i8 %sub 61 store i8 0, i8* %gep.idx, align 1 62 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 3 63 store i8 1, i8* %gep.3, align 1 64 ret void 65} 66 67; %gep.idx and %gep.3 must-alias if %mul overflows 68; (e.g. %idx == 3689348814741910323). 69define void @may_overflow_mul_sub_i64([16 x i8]* %ptr, i64 %idx) { 70; CHECK-LABEL: Function: may_overflow_mul_sub_i64: 3 pointers, 0 call sites 71; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 72; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 73; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 74; 75 %mul = mul i64 %idx, 5 76 %sub = sub i64 %mul, 1 77 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 78 store i8 0, i8* %gep.idx, align 1 79 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 80 store i8 1, i8* %gep.3, align 1 81 ret void 82} 83 84define void @nuw_nsw_mul_sub_i64([16 x i8]* %ptr, i64 %idx) { 85; CHECK-LABEL: Function: nuw_nsw_mul_sub_i64: 3 pointers, 0 call sites 86; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 87; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 88; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 89; 90 %mul = mul nuw nsw i64 %idx, 5 91 %sub = sub nuw nsw i64 %mul, 1 92 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 93 store i8 0, i8* %gep.idx, align 1 94 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 95 store i8 1, i8* %gep.3, align 1 96 ret void 97} 98 99define void @only_nsw_mul_sub_i64([16 x i8]* %ptr, i64 %idx) { 100; CHECK-LABEL: Function: only_nsw_mul_sub_i64: 3 pointers, 0 call sites 101; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 102; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 103; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 104; 105 %mul = mul nsw i64 %idx, 5 106 %sub = sub nsw i64 %mul, 1 107 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 108 store i8 0, i8* %gep.idx, align 1 109 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 110 store i8 1, i8* %gep.3, align 1 111 ret void 112} 113 114define void @only_nuw_mul_sub_i64([16 x i8]* %ptr, i64 %idx) { 115; CHECK-LABEL: Function: only_nuw_mul_sub_i64: 3 pointers, 0 call sites 116; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 117; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 118; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 119; 120 %mul = mul nuw i64 %idx, 5 121 %sub = sub nuw i64 %mul, 1 122 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 123 store i8 0, i8* %gep.idx, align 1 124 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 125 store i8 1, i8* %gep.3, align 1 126 ret void 127} 128 129; Even though the mul and sub may overflow %gep.idx and %gep.3 cannot alias 130; because we multiply by a power-of-2. 131define void @may_overflow_mul_pow2_sub_i64([16 x i8]* %ptr, i64 %idx) { 132; CHECK-LABEL: Function: may_overflow_mul_pow2_sub_i64: 3 pointers, 0 call sites 133; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 134; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 135; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 136; 137 %mul = mul i64 %idx, 8 138 %sub = sub i64 %mul, 1 139 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 140 store i8 0, i8* %gep.idx, align 1 141 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 142 store i8 1, i8* %gep.3, align 1 143 ret void 144} 145 146; Multiplies by power-of-2 preserves modulo and the sub does not wrap. 147define void @mul_pow2_sub_nsw_nuw_i64([16 x i8]* %ptr, i64 %idx) { 148; CHECK-LABEL: Function: mul_pow2_sub_nsw_nuw_i64: 3 pointers, 0 call sites 149; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 150; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 151; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 152; 153 %mul = mul i64 %idx, 8 154 %sub = sub nuw nsw i64 %mul, 1 155 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 156 store i8 0, i8* %gep.idx, align 1 157 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 158 store i8 1, i8* %gep.3, align 1 159 ret void 160} 161 162define void @may_overflow_shl_sub_i64([16 x i8]* %ptr, i64 %idx) { 163; CHECK-LABEL: Function: may_overflow_shl_sub_i64: 3 pointers, 0 call sites 164; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 165; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 166; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 167; 168 %mul = shl i64 %idx, 2 169 %sub = sub i64 %mul, 1 170 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 171 store i8 0, i8* %gep.idx, align 1 172 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 173 store i8 1, i8* %gep.3, align 1 174 ret void 175} 176 177define void @shl_sub_nsw_nuw_i64([16 x i8]* %ptr, i64 %idx) { 178; CHECK-LABEL: Function: shl_sub_nsw_nuw_i64: 3 pointers, 0 call sites 179; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 180; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 181; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 182; 183 %mul = shl i64 %idx, 3 184 %sub = sub nsw nuw i64 %mul, 1 185 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub 186 store i8 0, i8* %gep.idx, align 1 187 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 3 188 store i8 1, i8* %gep.3, align 1 189 ret void 190} 191 192; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 110). 193define void @may_overflow_i32_sext([16 x i8]* %ptr, i32 %idx) { 194; CHECK-LABEL: Function: may_overflow_i32_sext: 3 pointers, 0 call sites 195; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 196; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 197; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 198; 199 %mul = mul i32 %idx, 678152731 200 %sub = sub i32 %mul, 1582356375 201 %sub.ext = sext i32 %sub to i64 202 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub.ext 203 store i8 0, i8* %gep.idx, align 1 204 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 3 205 store i8 1, i8* %gep.3, align 1 206 ret void 207} 208 209define void @nuw_nsw_i32_sext([16 x i8]* %ptr, i32 %idx) { 210; CHECK-LABEL: Function: nuw_nsw_i32_sext: 3 pointers, 0 call sites 211; CHECK-NEXT: NoAlias: [16 x i8]* %ptr, i8* %gep.idx 212; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 213; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 214; 215 %mul = mul nuw nsw i32 %idx, 678152731 216 %sub = sub nuw nsw i32 %mul, 1582356375 217 %sub.ext = sext i32 %sub to i64 218 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub.ext 219 store i8 0, i8* %gep.idx, align 1 220 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 3 221 store i8 1, i8* %gep.3, align 1 222 ret void 223} 224 225; %gep.idx and %gep.3 must-alias if %mul overflows (e.g. %idx == 110). 226define void @may_overflow_i32_zext([16 x i8]* %ptr, i32 %idx) { 227; CHECK-LABEL: Function: may_overflow_i32_zext: 3 pointers, 0 call sites 228; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.idx 229; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 230; CHECK-NEXT: MayAlias: i8* %gep.3, i8* %gep.idx 231; 232 %mul = mul i32 %idx, 678152731 233 %sub = sub i32 %mul, 1582356375 234 %sub.ext = zext i32 %sub to i64 235 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub.ext 236 store i8 0, i8* %gep.idx, align 1 237 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 3 238 store i8 1, i8* %gep.3, align 1 239 ret void 240} 241 242define void @nuw_nsw_i32_zext([16 x i8]* %ptr, i32 %idx) { 243; CHECK-LABEL: Function: nuw_nsw_i32_zext: 3 pointers, 0 call sites 244; CHECK-NEXT: NoAlias: [16 x i8]* %ptr, i8* %gep.idx 245; CHECK-NEXT: PartialAlias (off 3): [16 x i8]* %ptr, i8* %gep.3 246; CHECK-NEXT: NoAlias: i8* %gep.3, i8* %gep.idx 247; 248 %mul = mul nuw nsw i32 %idx, 678152731 249 %sub = sub nuw nsw i32 %mul, 1582356375 250 %sub.ext = zext i32 %sub to i64 251 %gep.idx = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub.ext 252 store i8 0, i8* %gep.idx, align 1 253 %gep.3 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i32 3 254 store i8 1, i8* %gep.3, align 1 255 ret void 256} 257 258; %mul.1 and %sub.2 are equal, if %idx = 9, because %mul.1 overflows. Hence 259; %gep.mul.1 and %gep.sub.2 may alias. 260define void @may_overflow_pointer_diff([16 x i8]* %ptr, i64 %idx) { 261; CHECK-LABEL: Function: may_overflow_pointer_diff: 3 pointers, 0 call sites 262; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.mul.1 263; CHECK-NEXT: MayAlias: [16 x i8]* %ptr, i8* %gep.sub.2 264; CHECK-NEXT: MayAlias: i8* %gep.mul.1, i8* %gep.sub.2 265; 266 %mul.1 = mul i64 %idx, 6148914691236517207 267 %gep.mul.1 = getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %mul.1 268 store i8 1, i8* %gep.mul.1, align 1 269 %mul.2 = mul nsw i64 %idx, 3 270 %sub.2 = sub nsw i64 %mul.2, 12 271 %gep.sub.2= getelementptr [16 x i8], [16 x i8]* %ptr, i32 0, i64 %sub.2 272 store i8 0, i8* %gep.sub.2, align 1 273 274 ret void 275} 276