llvm/test/Analysis/BasicAA/recphi.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: Function: simple: 5 pointers, 0 call sites
   4 ; CHECK:         NoAlias:      float* %src1, float* %src2
   5 ; CHECK:         NoAlias:      float* %phi, float* %src1
   6 ; CHECK:         MayAlias:     float* %phi, float* %src2
   7 ; CHECK:         NoAlias:      float* %next, float* %src1
   8 ; CHECK:         MayAlias:     float* %next, float* %src2
   9 ; CHECK:         NoAlias:      float* %next, float* %phi
  10 ; CHECK:         NoAlias:      float* %g, float* %src1
  11 ; CHECK:         NoAlias:      float* %g, float* %src2
  12 ; CHECK:         NoAlias:      float* %g, float* %phi
  13 ; CHECK:         NoAlias:      float* %g, float* %next
  14 define void @simple(ptr %src1, ptr noalias %src2, i32 %n) nounwind {
  15 entry:
  16   load float, ptr %src1
  17   load float, ptr %src2
  18   br label %loop
  19
  20 loop:
  21   %phi = phi ptr [ %src2, %entry ], [ %next, %loop ]
  22   %idx = phi i32 [ 0, %entry ], [ %idxn, %loop ]
  23   %next = getelementptr inbounds float, ptr %phi, i32 1
  24   %g = getelementptr inbounds float, ptr %src1, i32 3
  25   %l = load float, ptr %phi
  26   load float, ptr %next
  27   %a = fadd float %l, 1.0
  28   store float %a, ptr %g
  29   %idxn = add nsw nuw i32 %idx, 1
  30   %cmp5 = icmp eq i32 %idxn, %n
  31   br i1 %cmp5, label %end, label %loop
  32
  33 end:
  34   ret void
  35 }
  36
  37 ; CHECK-LABEL: Function: notmust: 6 pointers, 0 call sites
  38 ; CHECK: MustAlias:     i8* %tab, [2 x i32]* %tab
  39 ; CHECK: PartialAlias (off -4): i32* %arrayidx, [2 x i32]* %tab
  40 ; CHECK: NoAlias:       i32* %arrayidx, i8* %tab
  41 ; CHECK: MustAlias:     i32* %tab, [2 x i32]* %tab
  42 ; CHECK: MustAlias:     i32* %tab, i8* %tab
  43 ; CHECK: NoAlias:       i32* %arrayidx, i32* %tab
  44 ; CHECK: MayAlias:      i32* %incdec.ptr.i, [2 x i32]* %tab
  45 ; CHECK: NoAlias:       i32* %incdec.ptr.i, i8* %tab
  46 ; CHECK: MayAlias:      i32* %arrayidx, i32* %incdec.ptr.i
  47 ; CHECK: NoAlias:       i32* %incdec.ptr.i, i32* %tab
  48 ; CHECK: MayAlias:      i32* %p.addr.05.i, [2 x i32]* %tab
  49 ; CHECK: MayAlias:      i32* %p.addr.05.i, i8* %tab
  50 ; CHECK: MayAlias:      i32* %arrayidx, i32* %p.addr.05.i
  51 ; CHECK: MayAlias:      i32* %p.addr.05.i, i32* %tab
  52 ; CHECK: NoAlias:       i32* %incdec.ptr.i, i32* %p.addr.05.i
  53 define i32 @notmust() nounwind {
  54 entry:
  55   %tab = alloca [2 x i32], align 4
  56   %ignore1 = load [2 x i32], ptr %tab
  57   %ignore2 = load i8, ptr %tab
  58   %arrayidx = getelementptr inbounds [2 x i32], ptr %tab, i32 0, i32 1
  59   store i32 0, ptr %arrayidx, align 4
  60   store i32 0, ptr %tab, align 4
  61   %0 = add i32 1, 1
  62   %cmp4.i = icmp slt i32 %0, 2
  63   br i1 %cmp4.i, label %while.body.i, label %f.exit
  64
  65 while.body.i: ; preds = %while.body.i, %entry
  66   %1 = phi i32 [ 1, %while.body.i ], [ %0, %entry ]
  67   %foo.06.i = phi i32 [ %sub.i, %while.body.i ], [ 2, %entry ]
  68   %p.addr.05.i = phi ptr [ %incdec.ptr.i, %while.body.i ], [ %tab, %entry ]
  69   %sub.i = sub nsw i32 %foo.06.i, %1
  70   %incdec.ptr.i = getelementptr inbounds i32, ptr %p.addr.05.i, i32 1
  71   %ignore3 = load i32, ptr %incdec.ptr.i
  72   store i32 %sub.i, ptr %p.addr.05.i, align 4
  73   %cmp.i = icmp sgt i32 %sub.i, 1
  74   br i1 %cmp.i, label %while.body.i, label %f.exit
  75
  76 f.exit: ; preds = %entry, %while.body.i
  77   %2 = load i32, ptr %tab, align 4
  78   %cmp = icmp eq i32 %2, 2
  79   %3 = load i32, ptr %arrayidx, align 4
  80   %cmp4 = icmp eq i32 %3, 1
  81   %or.cond = and i1 %cmp, %cmp4
  82   br i1 %or.cond, label %if.end, label %if.then
  83
  84 if.then: ; preds = %f.exit
  85   unreachable
  86
  87 if.end: ; preds = %f.exit
  88   ret i32 0
  89 }
  90
  91 ; CHECK-LABEL: Function: reverse: 6 pointers, 0 call sites
  92 ; CHECK: MustAlias:     i8* %tab, [10 x i32]* %tab
  93 ; CHECK: MustAlias:     i32* %tab, [10 x i32]* %tab
  94 ; CHECK: MustAlias:     i32* %tab, i8* %tab
  95 ; CHECK: PartialAlias (off -36):        i32* %arrayidx1, [10 x i32]* %tab
  96 ; CHECK: NoAlias:       i32* %arrayidx1, i8* %tab
  97 ; CHECK: NoAlias:       i32* %arrayidx1, i32* %tab
  98 ; CHECK: MayAlias:      i32* %incdec.ptr.i, [10 x i32]* %tab
  99 ; CHECK: MayAlias:      i32* %incdec.ptr.i, i8* %tab
 100 ; CHECK: MayAlias:      i32* %incdec.ptr.i, i32* %tab
 101 ; CHECK: MayAlias:      i32* %arrayidx1, i32* %incdec.ptr.i
 102 ; CHECK: MayAlias:      i32* %p.addr.05.i, [10 x i32]* %tab
 103 ; CHECK: MayAlias:      i32* %p.addr.05.i, i8* %tab
 104 ; CHECK: MayAlias:      i32* %p.addr.05.i, i32* %tab
 105 ; CHECK: MayAlias:      i32* %arrayidx1, i32* %p.addr.05.i
 106 ; CHECK: NoAlias:       i32* %incdec.ptr.i, i32* %p.addr.05.i
 107 define i32 @reverse() nounwind {
 108 entry:
 109   %tab = alloca [10 x i32], align 4
 110   %ignore1 = load [10 x i32], ptr %tab
 111   %ignore2 = load i8, ptr %tab
 112   store i32 0, ptr %tab, align 4
 113   %arrayidx1 = getelementptr inbounds [10 x i32], ptr %tab, i32 0, i32 9
 114   store i32 0, ptr %arrayidx1, align 4
 115   %0 = add i32 1, 1
 116   %cmp4.i = icmp slt i32 %0, 2
 117   br i1 %cmp4.i, label %while.body.i, label %f.exit
 118
 119 while.body.i: ; preds = %while.body.i, %entry
 120   %1 = phi i32 [ 1, %while.body.i ], [ %0, %entry ]
 121   %foo.06.i = phi i32 [ %sub.i, %while.body.i ], [ 2, %entry ]
 122   %p.addr.05.i = phi ptr [ %incdec.ptr.i, %while.body.i ], [ %arrayidx1, %entry ]
 123   %sub.i = sub nsw i32 %foo.06.i, %1
 124   %incdec.ptr.i = getelementptr inbounds i32, ptr %p.addr.05.i, i32 -1
 125   %ignore3 = load i32, ptr %incdec.ptr.i
 126   store i32 %sub.i, ptr %p.addr.05.i, align 4
 127   %cmp.i = icmp sgt i32 %sub.i, 1
 128   br i1 %cmp.i, label %while.body.i, label %f.exit
 129
 130 f.exit: ; preds = %entry, %while.body.i
 131   %2 = load i32, ptr %arrayidx1, align 4
 132   %cmp = icmp eq i32 %2, 2
 133   %3 = load i32, ptr %tab, align 4
 134   %cmp4 = icmp eq i32 %3, 1
 135   %or.cond = and i1 %cmp, %cmp4
 136   br i1 %or.cond, label %if.end, label %if.then
 137
 138 if.then: ; preds = %f.exit
 139   unreachable
 140
 141 if.end: ; preds = %f.exit
 142   ret i32 0
 143 }
 144
 145 ; CHECK-LABEL: Function: negative: 5 pointers, 1 call sites
 146 ; CHECK: PartialAlias (off -4): i16* %_tmp1, [3 x i16]* %int_arr.10
 147 ; CHECK: MayAlias:      [3 x i16]* %int_arr.10, i16* %ls1.9.0
 148 ; CHECK: MayAlias:      i16* %_tmp1, i16* %ls1.9.0
 149 ; CHECK: MayAlias:      i16* %_tmp7, [3 x i16]* %int_arr.10
 150 ; CHECK: MayAlias:      i16* %_tmp1, i16* %_tmp7
 151 ; CHECK: NoAlias:       i16* %_tmp7, i16* %ls1.9.0
 152 ; CHECK: PartialAlias (off -2): i16* %_tmp11, [3 x i16]* %int_arr.10
 153 ; CHECK: NoAlias:       i16* %_tmp1, i16* %_tmp11
 154 ; CHECK: MayAlias:      i16* %_tmp11, i16* %ls1.9.0
 155 ; CHECK: MayAlias:      i16* %_tmp11, i16* %_tmp7
 156 ; CHECK: NoModRef:  Ptr: [3 x i16]* %int_arr.10 <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 157 ; CHECK: NoModRef:  Ptr: i16* %_tmp1    <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 158 ; CHECK: Both ModRef:  Ptr: i16* %ls1.9.0       <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 159 ; CHECK: Both ModRef:  Ptr: i16* %_tmp7 <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 160 ; CHECK: NoModRef:  Ptr: i16* %_tmp11   <->  %_tmp16 = call i16 @call(i32 %_tmp13)
 161 define i16 @negative(i16 %argc.5.par) {
 162   %int_arr.10 = alloca [3 x i16], align 1
 163   load [3 x i16], ptr %int_arr.10
 164   %_tmp1 = getelementptr inbounds [3 x i16], ptr %int_arr.10, i16 0, i16 2
 165   load i16, ptr %_tmp1
 166   br label %bb1
 167
 168 bb1:                                              ; preds = %bb1, %0
 169   %i.7.0 = phi i16 [ 2, %0 ], [ %_tmp5, %bb1 ]
 170   %ls1.9.0 = phi ptr [ %_tmp1, %0 ], [ %_tmp7, %bb1 ]
 171   store i16 %i.7.0, ptr %ls1.9.0, align 1
 172   %_tmp5 = add nsw i16 %i.7.0, -1
 173   %_tmp7 = getelementptr i16, ptr %ls1.9.0, i16 -1
 174   load i16, ptr %_tmp7
 175   %_tmp9 = icmp sgt i16 %i.7.0, 0
 176   br i1 %_tmp9, label %bb1, label %bb3
 177
 178 bb3:                                              ; preds = %bb1
 179   %_tmp11 = getelementptr inbounds [3 x i16], ptr %int_arr.10, i16 0, i16 1
 180   %_tmp12 = load i16, ptr %_tmp11, align 1
 181   %_tmp13 = sext i16 %_tmp12 to i32
 182   %_tmp16 = call i16 @call(i32 %_tmp13)
 183   %_tmp18.not = icmp eq i16 %_tmp12, 1
 184   br i1 %_tmp18.not, label %bb5, label %bb4
 185
 186 bb4:                                              ; preds = %bb3
 187   ret i16 1
 188
 189 bb5:                                              ; preds = %bb3, %bb4
 190   ret i16 0
 191 }
 192
 193 ; CHECK-LABEL: Function: dynamic_offset
 194 ; CHECK: NoAlias:  i8* %a, i8* %p.base
 195 ; CHECK: MayAlias: i8* %p, i8* %p.base
 196 ; CHECK: NoAlias:  i8* %a, i8* %p
 197 ; CHECK: MayAlias: i8* %p.base, i8* %p.next
 198 ; CHECK: NoAlias:  i8* %a, i8* %p.next
 199 ; CHECK: MayAlias: i8* %p, i8* %p.next
 200 define void @dynamic_offset(i1 %c, ptr noalias %p.base) {
 201 entry:
 202   %a = alloca i8
 203   load i8, ptr %p.base
 204   load i8, ptr %a
 205   br label %loop
 206
 207 loop:
 208   %p = phi ptr [ %p.base, %entry ], [ %p.next, %loop ]
 209   %offset = call i16 @call(i32 0)
 210   %p.next = getelementptr inbounds i8, ptr %p, i16 %offset
 211   load i8, ptr %p
 212   load i8, ptr %p.next
 213   br i1 %c, label %loop, label %exit
 214
 215 exit:
 216   ret void
 217 }
 218
 219 ; TODO: Currently yields an asymmetric result.
 220 ; CHECK-LABEL: Function: symmetry
 221 ; CHECK: MayAlias:  i32* %p, i32* %p.base
 222 ; CHECK: MayAlias:  i32* %p.base, i32* %p.next
 223 ; CHECK: NoAlias:   i32* %p, i32* %p.next
 224 ; CHECK: MayAlias:  i32* %p.base, i32* %result
 225 ; CHECK: NoAlias:   i32* %p, i32* %result
 226 ; CHECK: MustAlias: i32* %p.next, i32* %result
 227 define ptr @symmetry(ptr %p.base, i1 %c) {
 228 entry:
 229   load i32, ptr %p.base
 230   br label %loop
 231
 232 loop:
 233   %p = phi ptr [ %p.base, %entry ], [ %p.next, %loop ]
 234   %p.next = getelementptr inbounds i32, ptr %p, i32 1
 235   load i32, ptr %p
 236   load i32, ptr %p.next
 237   br i1 %c, label %loop, label %exit
 238
 239 exit:
 240   %result = phi ptr [ %p.next, %loop ]
 241   load i32, ptr %result
 242   ret ptr %result
 243 }
 244
 245 ; FIXME: %a and %p.inner do not alias.
 246 ; CHECK-LABEL: Function: nested_loop
 247 ; CHECK: NoAlias:  i8* %a, i8* %p.base
 248 ; CHECK: NoAlias:  i8* %a, i8* %p.outer
 249 ; CHECK: MayAlias: i8* %a, i8* %p.inner
 250 ; CHECK: NoAlias:  i8* %a, i8* %p.inner.next
 251 ; CHECK: NoAlias:  i8* %a, i8* %p.outer.next
 252 define void @nested_loop(i1 %c, i1 %c2, ptr noalias %p.base) {
 253 entry:
 254   %a = alloca i8
 255   load i8, ptr %p.base
 256   load i8, ptr %a
 257   br label %outer_loop
 258
 259 outer_loop:
 260   %p.outer = phi ptr [ %p.base, %entry ], [ %p.outer.next, %outer_loop_latch ]
 261   load i8, ptr %p.outer
 262   br label %inner_loop
 263
 264 inner_loop:
 265   %p.inner = phi ptr [ %p.outer, %outer_loop ], [ %p.inner.next, %inner_loop ]
 266   %p.inner.next = getelementptr inbounds i8, ptr %p.inner, i64 1
 267   load i8, ptr %p.inner
 268   load i8, ptr %p.inner.next
 269   br i1 %c, label %inner_loop, label %outer_loop_latch
 270
 271 outer_loop_latch:
 272   %p.outer.next = getelementptr inbounds i8, ptr %p.inner, i64 10
 273   load i8, ptr %p.outer.next
 274   br i1 %c2, label %outer_loop, label %exit
 275
 276 exit:
 277   ret void
 278 }
 279
 280 ; Same as the previous test case, but avoiding phi of phi.
 281 ; CHECK-LABEL: Function: nested_loop2
 282 ; CHECK: NoAlias:  i8* %a, i8* %p.base
 283 ; CHECK: NoAlias:  i8* %a, i8* %p.outer
 284 ; CHECK: NoAlias:  i8* %a, i8* %p.outer.next
 285 ; CHECK: MayAlias: i8* %a, i8* %p.inner
 286 ; CHECK: NoAlias:  i8* %a, i8* %p.inner.next
 287 ; TODO: (a, p.inner) could be NoAlias
 288 define void @nested_loop2(i1 %c, i1 %c2, ptr noalias %p.base) {
 289 entry:
 290   %a = alloca i8
 291   load i8, ptr %p.base
 292   load i8, ptr %a
 293   br label %outer_loop
 294
 295 outer_loop:
 296   %p.outer = phi ptr [ %p.base, %entry ], [ %p.outer.next, %outer_loop_latch ]
 297   %p.outer.next = getelementptr inbounds i8, ptr %p.outer, i64 10
 298   load i8, ptr %p.outer
 299   load i8, ptr %p.outer.next
 300   br label %inner_loop
 301
 302 inner_loop:
 303   %p.inner = phi ptr [ %p.outer.next, %outer_loop ], [ %p.inner.next, %inner_loop ]
 304   %p.inner.next = getelementptr inbounds i8, ptr %p.inner, i64 1
 305   load i8, ptr %p.inner
 306   load i8, ptr %p.inner.next
 307   br i1 %c, label %inner_loop, label %outer_loop_latch
 308
 309 outer_loop_latch:
 310   br i1 %c2, label %outer_loop, label %exit
 311
 312 exit:
 313   ret void
 314 }
 315
 316 ; CHECK-LABEL: Function: nested_loop3
 317 ; CHECK: NoAlias:       i8* %a, i8* %p.base
 318 ; CHECK: NoAlias:       i8* %a, i8* %p.outer
 319 ; CHECK: NoAlias:       i8* %a, i8* %p.outer.next
 320 ; CHECK: NoAlias:       i8* %a, i8* %p.inner
 321 ; CHECK: NoAlias:       i8* %a, i8* %p.inner.next
 322 define void @nested_loop3(i1 %c, i1 %c2, ptr noalias %p.base) {
 323 entry:
 324   %a = alloca i8
 325   load i8, ptr %p.base
 326   load i8, ptr %a
 327   br label %outer_loop
 328
 329 outer_loop:
 330   %p.outer = phi ptr [ %p.base, %entry ], [ %p.outer.next, %outer_loop_latch ]
 331   %p.outer.next = getelementptr inbounds i8, ptr %p.outer, i64 10
 332   load i8, ptr %p.outer
 333   load i8, ptr %p.outer.next
 334   br label %inner_loop
 335
 336 inner_loop:
 337   %p.inner = phi ptr [ %p.outer, %outer_loop ], [ %p.inner.next, %inner_loop ]
 338   %p.inner.next = getelementptr inbounds i8, ptr %p.inner, i64 1
 339   load i8, ptr %p.inner
 340   load i8, ptr %p.inner.next
 341   br i1 %c, label %inner_loop, label %outer_loop_latch
 342
 343 outer_loop_latch:
 344   br i1 %c2, label %outer_loop, label %exit
 345
 346 exit:
 347   ret void
 348 }
 349
 350 ; CHECK-LABEL: Function: sibling_loop
 351 ; CHECK: NoAlias:       i8* %a, i8* %p.base
 352 ; CHECK: NoAlias:       i8* %a, i8* %p1
 353 ; CHECK: NoAlias:       i8* %a, i8* %p1.next
 354 ; CHECK: MayAlias:      i8* %a, i8* %p2
 355 ; CHECK: NoAlias:       i8* %a, i8* %p2.next
 356 ; TODO: %p2 does not alias %a
 357 define void @sibling_loop(i1 %c, i1 %c2, ptr noalias %p.base) {
 358 entry:
 359   %a = alloca i8
 360   load i8, ptr %p.base
 361   load i8, ptr %a
 362   br label %loop1
 363
 364 loop1:
 365   %p1 = phi ptr [ %p.base, %entry ], [ %p1.next, %loop1 ]
 366   %p1.next = getelementptr inbounds i8, ptr %p1, i64 10
 367   load i8, ptr %p1
 368   load i8, ptr %p1.next
 369   br i1 %c, label %loop1, label %loop2
 370
 371 loop2:
 372   %p2 = phi ptr [ %p1.next, %loop1 ], [ %p2.next, %loop2 ]
 373   %p2.next = getelementptr inbounds i8, ptr %p2, i64 1
 374   load i8, ptr %p2
 375   load i8, ptr %p2.next
 376   br i1 %c2, label %loop2, label %exit
 377
 378 exit:
 379   ret void
 380 }
 381
 382 ; CHECK-LABEL: Function: sibling_loop2
 383 ; CHECK: NoAlias:       i8* %a, i8* %p.base
 384 ; CHECK: NoAlias:       i8* %a, i8* %p1
 385 ; CHECK: NoAlias:       i8* %a, i8* %p1.next
 386 ; CHECK: NoAlias:       i8* %a, i8* %p2
 387 ; CHECK: NoAlias:       i8* %a, i8* %p2.next
 388 define void @sibling_loop2(i1 %c, i1 %c2, ptr noalias %p.base) {
 389 entry:
 390   %a = alloca i8
 391   load i8, ptr %p.base
 392   load i8, ptr %a
 393   br label %loop1
 394
 395 loop1:
 396   %p1 = phi ptr [ %p.base, %entry ], [ %p1.next, %loop1 ]
 397   %p1.next = getelementptr inbounds i8, ptr %p1, i64 10
 398   load i8, ptr %p1
 399   load i8, ptr %p1.next
 400   br i1 %c, label %loop1, label %loop2
 401
 402 loop2:
 403   %p2 = phi ptr [ %p1, %loop1 ], [ %p2.next, %loop2 ]
 404   %p2.next = getelementptr inbounds i8, ptr %p2, i64 1
 405   load i8, ptr %p2
 406   load i8, ptr %p2.next
 407   br i1 %c2, label %loop2, label %exit
 408
 409 exit:
 410   ret void
 411 }
 412
 413 ; CHECK: MustAlias: i8* %a, i8* %phi
 414 define void @phi_contains_self() {
 415 entry:
 416   %a = alloca i32
 417   load i8, ptr %a
 418   br label %loop
 419
 420 loop:
 421   %phi = phi ptr [ %phi, %loop ], [ %a, %entry ]
 422   load i8, ptr %phi
 423   br label %loop
 424 }
 425
 426 declare i16 @call(i32)