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