llvm/test/Analysis/BasicAA/gep-nuw-alias.ll

   1 ; RUN: opt < %s -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
   2
   3 ; CHECK-LABEL: test_no_lower_bound
   4 ;
   5 ; CHECK-DAG: MayAlias: i32* %a, i32* %b
   6 define void @test_no_lower_bound(ptr %p, i64 %i) {
   7   %a = getelementptr i8, ptr %p, i64 4
   8   %b = getelementptr nuw i8, ptr %p, i64 %i
   9
  10   load i32, ptr %a
  11   load i32, ptr %b
  12
  13   ret void
  14 }
  15
  16 ; CHECK-LABEL: test_lower_bound_lt_size
  17 ;
  18 ; CHECK-DAG: MayAlias: i32* %a, i32* %b
  19 define void @test_lower_bound_lt_size(ptr %p, i64 %i) {
  20   %a = getelementptr i8, ptr %p
  21   %add = getelementptr nuw i8, ptr %p, i64 2
  22   %b = getelementptr nuw i8, ptr %add, i64 %i
  23
  24   load i32, ptr %a
  25   load i32, ptr %b
  26
  27   ret void
  28 }
  29
  30 ; CHECK-LABEL: test_lower_bound_ge_size
  31 ;
  32 ; CHECK-DAG: NoAlias: i32* %a, i32* %b
  33 define void @test_lower_bound_ge_size(ptr %p, i64 %i) {
  34   %a = getelementptr i8, ptr %p
  35   %add = getelementptr nuw i8, ptr %p, i64 4
  36   %b = getelementptr nuw i8, ptr %add, i64 %i
  37
  38   load i32, ptr %a
  39   load i32, ptr %b
  40
  41   ret void
  42 }
  43
  44 ; CHECK-LABEL: test_not_all_nuw
  45 ;
  46 ; If part of the addressing is done with non-nuw GEPs, we can't use properties
  47 ; implied by the last GEP with the whole offset. In this case, the calculation
  48 ; of %add (%p + 4) could wrap the pointer index type, such that %add +<nuw> %i
  49 ; could still alias with %p.
  50 ;
  51 ; CHECK-DAG: MayAlias: i32* %a, i32* %b
  52 define void @test_not_all_nuw(ptr %p, i64 %i) {
  53   %a = getelementptr i8, ptr %p
  54   %add = getelementptr i8, ptr %p, i64 4
  55   %b = getelementptr nuw i8, ptr %add, i64 %i
  56
  57   load i32, ptr %a
  58   load i32, ptr %b
  59
  60   ret void
  61 }
  62
  63 ; CHECK-LABEL: test_multi_step_not_all_nuw
  64 ;
  65 ; CHECK-DAG: MayAlias: i32* %a, i32* %b
  66 define void @test_multi_step_not_all_nuw(ptr %p, i64 %i, i64 %j, i64 %k) {
  67   %a = getelementptr i8, ptr %p
  68   %add = getelementptr i8, ptr %p, i64 4
  69   %step1 = getelementptr i8, ptr %add, i64 %i
  70   %step2 = getelementptr i8, ptr %step1, i64 %j
  71   %b = getelementptr nuw i8, ptr %step2, i64 %k
  72
  73   load i32, ptr %a
  74   load i32, ptr %b
  75
  76   ret void
  77 }
  78
  79 ; CHECK-LABEL: test_multi_step_all_nuw
  80 ;
  81 ; CHECK-DAG: NoAlias: i32* %a, i32* %b
  82 define void @test_multi_step_all_nuw(ptr %p, i64 %i, i64 %j, i64 %k) {
  83   %a = getelementptr i8, ptr %p
  84   %add = getelementptr nuw i8, ptr %p, i64 4
  85   %step1 = getelementptr nuw i8, ptr %add, i64 %i
  86   %step2 = getelementptr nuw i8, ptr %step1, i64 %j
  87   %b = getelementptr nuw i8, ptr %step2, i64 %k
  88
  89   load i32, ptr %a
  90   load i32, ptr %b
  91
  92   ret void
  93 }
  94
  95 %struct = type { i64, [2 x i32], i64 }
  96
  97 ; CHECK-LABEL: test_struct_no_nuw
  98 ;
  99 ; The array access may alias with the struct elements before and after, because
 100 ; we cannot prove that (%arr + %i) does not alias with the base pointer %p.
 101 ;
 102 ; CHECK-DAG: MayAlias: i32* %arrayidx, i64* %st
 103 ; CHECK-DAG: NoAlias: i64* %after, i64* %st
 104 ; CHECK-DAG: MayAlias: i64* %after, i32* %arrayidx
 105
 106 define void @test_struct_no_nuw(ptr %st, i64 %i) {
 107   %arr = getelementptr i8, ptr %st, i64 8
 108   %arrayidx = getelementptr [2 x i32], ptr %arr, i64 0, i64 %i
 109   %after = getelementptr i8, ptr %st, i64 16
 110
 111   load i64, ptr %st
 112   load i32, ptr %arrayidx
 113   load i64, ptr %after
 114
 115   ret void
 116 }
 117
 118 ; CHECK-LABEL: test_struct_nuw
 119 ;
 120 ; We can prove that the array access does not alias with struct element before,
 121 ; because we can prove that (%arr +<nuw> %i) does not wrap the pointer index
 122 ; type (add nuw). The array access may still alias with the struct element
 123 ; after, as the add nuw property does not preclude this.
 124 ;
 125 ; CHECK-DAG: NoAlias: i32* %arrayidx, i64* %st
 126 ; CHECK-DAG: NoAlias: i64* %after, i64* %st
 127 ; CHECK-DAG: MayAlias: i64* %after, i32* %arrayidx
 128
 129 define void @test_struct_nuw(ptr %st, i64 %i) {
 130   %arr = getelementptr nuw i8, ptr %st, i64 8
 131   %arrayidx = getelementptr nuw [2 x i32], ptr %arr, i64 0, i64 %i
 132   %after = getelementptr nuw i8, ptr %st, i64 16
 133
 134   load i64, ptr %st
 135   load i32, ptr %arrayidx
 136   load i64, ptr %after
 137
 138   ret void
 139 }
 140
 141 ; CHECK-LABEL: constant_offset_overflow
 142 ;
 143 ; If subtraction of constant offsets could overflow in an unsigned sense, we
 144 ; cannot prove the lower bound between the GEPs and so they may still alias.
 145 ;
 146 ; CHECK-DAG: MayAlias: i32* %a, i32* %b
 147
 148 define void @constant_offset_overflow(ptr %p, i64 %i) {
 149   %a = getelementptr i8, ptr %p, i64 -8
 150   %add = getelementptr nuw i8, ptr %p, i64 4
 151   %b = getelementptr nuw i8, ptr %add, i64 %i
 152
 153   load i32, ptr %a
 154   load i32, ptr %b
 155
 156   ret void
 157 }
 158
 159 ; CHECK-LABEL: equal_var_idx_noalias
 160 ;
 161 ; If GEPs have equal variable indices, we can prove NoAlias when the Scale of
 162 ; the RHS GEP is greater, as in this scenario the constant lower bound holds.
 163 ;
 164 ; CHECK-DAG: NoAlias: i32* %a, i32* %b
 165
 166 define void @equal_var_idx_noalias(ptr %p, i64 %i) {
 167   %a = getelementptr i8, ptr %p, i64 %i
 168
 169   %add = getelementptr nuw i8, ptr %p, i64 4
 170   %b = getelementptr nuw i16, ptr %add, i64 %i
 171
 172   load i32, ptr %a
 173   load i32, ptr %b
 174
 175   ret void
 176 }
 177
 178 ; CHECK-LABEL: equal_var_idx_alias
 179 ;
 180 ; If GEPs have equal variable indices, we cannot prove NoAlias when the Scale of
 181 ; the RHS GEP is ult Scale of the LHS GEP.
 182 ;
 183 ; CHECK-DAG: MayAlias: i32* %a, i32* %b
 184
 185 define void @equal_var_idx_alias(ptr %p, i64 %i) {
 186   %a = getelementptr i32, ptr %p, i64 %i
 187
 188   %add = getelementptr nuw i8, ptr %p, i64 4
 189   %b = getelementptr nuw i16, ptr %add, i64 %i
 190
 191   load i32, ptr %b
 192   load i32, ptr %a
 193
 194   ret void
 195 }
 196
 197 ; CHECK-LABEL: both_var_idx
 198 ;
 199 ; If the RHS GEP has unmatched variable indices, we cannot prove a constant
 200 ; lower bound between GEPs.
 201 ;
 202 ; CHECK-DAG: MayAlias: i32* %a, i32* %b
 203
 204 define void @both_var_idx(ptr %p, i64 %i, i64 %j) {
 205   %a = getelementptr i8, ptr %p, i64 %i
 206
 207   %add = getelementptr nuw i8, ptr %p, i64 4
 208   %b = getelementptr nuw i8, ptr %add, i64 %j
 209
 210   load i32, ptr %a
 211   load i32, ptr %b
 212
 213   ret void
 214 }
 215
 216 ; CHECK-LABEL: add_no_nuw
 217 ; CHECK: MayAlias: i8* %gep, i8* %p
 218 define i8 @add_no_nuw(ptr %p, i64 %n) {
 219   store i8 3, ptr %p
 220
 221   %add = add i64 %n, 1
 222   %gep = getelementptr nuw i8, ptr %p, i64 %add
 223   %val = load i8, ptr %gep
 224   ret i8 %val
 225 }
 226
 227 ; CHECK-LABEL: add_nuw
 228 ; CHECK: NoAlias: i8* %gep, i8* %p
 229 define i8 @add_nuw(ptr %p, i64 %n) {
 230   store i8 3, ptr %p
 231
 232   %add = add nuw i64 %n, 1
 233   %gep = getelementptr nuw i8, ptr %p, i64 %add
 234   %val = load i8, ptr %gep
 235   ret i8 %val
 236 }
 237
 238 ; CHECK-LABEL: add_no_nuw
 239 ; CHECK: MayAlias: i8* %gep, i16* %p
 240 define i8 @add_no_nuw_scale(ptr %p, i64 %n) {
 241   store i16 3, ptr %p
 242
 243   %add = add i64 %n, 1
 244   %gep = getelementptr nuw i16, ptr %p, i64 %add
 245   %val = load i8, ptr %gep
 246   ret i8 %val
 247 }
 248
 249 ; CHECK-LABEL: add_nuw
 250 ; CHECK: NoAlias: i8* %gep, i16* %p
 251 define i8 @add_nuw_scale(ptr %p, i64 %n) {
 252   store i16 3, ptr %p
 253
 254   %add = add nuw i64 %n, 1
 255   %gep = getelementptr nuw i16, ptr %p, i64 %add
 256   %val = load i8, ptr %gep
 257   ret i8 %val
 258 }
 259
 260 ; CHECK-LABEL: sub_nuw
 261 ; CHECK: MayAlias: i8* %gep, i8* %p
 262 define i8 @sub_nuw(ptr %p, i64 %n) {
 263   store i8 3, ptr %p
 264
 265   %add = sub nuw i64 %n, 1
 266   %gep = getelementptr nuw i8, ptr %p, i64 %add
 267   %val = load i8, ptr %gep
 268   ret i8 %val
 269 }
 270
 271 ; CHECK-LABEL: mul_no_nuw
 272 ; CHECK: MayAlias: i8* %gep, i16* %p
 273 define i8 @mul_no_nuw(ptr %p, i64 %n) {
 274   store i16 3, ptr %p
 275
 276   %add = add nuw i64 %n, 1
 277   %mul = mul i64 %add, 2
 278   %gep = getelementptr nuw i8, ptr %p, i64 %mul
 279   %val = load i8, ptr %gep
 280   ret i8 %val
 281 }
 282
 283 ; CHECK-LABEL: mul_nuw
 284 ; CHECK: NoAlias: i8* %gep, i16* %p
 285 define i8 @mul_nuw(ptr %p, i64 %n) {
 286   store i16 3, ptr %p
 287
 288   %add = add nuw i64 %n, 1
 289   %mul = mul nuw i64 %add, 2
 290   %gep = getelementptr nuw i8, ptr %p, i64 %mul
 291   %val = load i8, ptr %gep
 292   ret i8 %val
 293 }
 294
 295 ; CHECK-LABEL: shl_no_nuw
 296 ; CHECK: MayAlias: i8* %gep, i16* %p
 297 define i8 @shl_no_nuw(ptr %p, i64 %n) {
 298   store i16 3, ptr %p
 299
 300   %add = add nuw i64 %n, 1
 301   %shl = shl i64 %add, 1
 302   %gep = getelementptr nuw i8, ptr %p, i64 %shl
 303   %val = load i8, ptr %gep
 304   ret i8 %val
 305 }
 306
 307 ; CHECK-LABEL: shl_nuw
 308 ; CHECK: NoAlias: i8* %gep, i16* %p
 309 define i8 @shl_nuw(ptr %p, i64 %n) {
 310   store i16 3, ptr %p
 311
 312   %add = add nuw i64 %n, 1
 313   %shl = shl nuw i64 %add, 1
 314   %gep = getelementptr nuw i8, ptr %p, i64 %shl
 315   %val = load i8, ptr %gep
 316   ret i8 %val
 317 }