llvm/test/Analysis/BasicAA/recphi.ll

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