llvm/test/Analysis/BasicAA/gep-modulo.ll

   1 ; RUN: opt -basic-aa -aa-eval -print-all-alias-modref-info -disable-output %s 2>&1 | FileCheck %s
   2
   3 target datalayout = "p:64:64:64"
   4
   5 ; %gep.idx and %gep.6 must-alias if %mul overflows (e.g. %idx == 52).
   6 define 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
  21 define 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).
  37 define 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
  52 define 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).
  69 define 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
  84 define 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
  99 define 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
 114 define 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.
 131 define 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.
 147 define 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
 162 define 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
 177 define 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).
 193 define 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
 209 define 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).
 226 define 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
 242 define 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.
 260 define 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
 277 ; %gep.1 and %gep.idx may alias, e.g. if %idx.1 = 8 and %idx.2 == 2. %gep.idx is then
 278 ;  (((18446744073709551614 * 8) % 2^64 + 6 * 2) % 2^64 + 10) % 2^64 == 6.
 279 define void @may_overflow_mul_scale_neg([200 x [ 6 x i8]]* %ptr, i64 %idx.1,i64 %idx.2) {
 280 ; CHECK-LABEL: Function: may_overflow_mul_scale_neg: 4 pointers, 2 call sites
 281 ; CHECK-NEXT:  MustAlias:   [200 x [6 x i8]]* %ptr, i8* %bc
 282 ; CHECK-NEXT:  PartialAlias (off 6):    [200 x [6 x i8]]* %ptr, i8* %gep.1
 283 ; CHECK-NEXT:  NoAlias: i8* %bc, i8* %gep.1
 284 ; CHECK-NEXT:  MayAlias:    [200 x [6 x i8]]* %ptr, i8* %gep.idx
 285 ; CHECK-NEXT:  MayAlias: i8* %bc, i8* %gep.idx
 286 ; CHECK-NEXT:  MayAlias: i8* %gep.1, i8* %gep.idx
 287 ;
 288   %idx.1.pos = icmp sge i64 %idx.1, 0
 289   call void @llvm.assume(i1 %idx.1.pos)
 290   %idx.2.pos = icmp sge i64 %idx.2, 0
 291   call void @llvm.assume(i1 %idx.2.pos)
 292
 293   %bc = bitcast [ 200 x [ 6 x i8 ] ]* %ptr to i8*
 294   %gep.1 = getelementptr i8, i8* %bc, i64 6
 295   store i8 1, i8* %gep.1, align 1
 296
 297   %mul.0 = mul i64 %idx.1, -2
 298   %add = add i64 %mul.0, 10
 299   %gep.idx = getelementptr [ 200 x [ 6 x i8 ] ], [ 200 x [ 6 x i8 ] ]* %ptr, i64 0, i64 %idx.2, i64 %add
 300   store i8 0, i8* %gep.idx, align 1
 301   ret void
 302 }
 303
 304 declare void @llvm.assume(i1)