llvm/test/Analysis/ScalarEvolution/scev-aa.ll

   1 ; RUN: opt -disable-output < %s -aa-pipeline=scev-aa -passes=aa-eval -print-all-alias-modref-info \
   2 ; RUN:   2>&1 | FileCheck %s
   3
   4 ; At the time of this writing, misses the example of the form
   5 ; A[i+(j+1)] != A[i+j], which can arise from multi-dimensional array references,
   6 ; and the example of the form A[0] != A[i+1], where i+1 is known to be positive.
   7
   8 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
   9
  10 ; p[i] and p[i+1] don't alias.
  11
  12 ; CHECK-LABEL: Function: loop
  13 ; CHECK: NoAlias: double* %pi, double* %pi.next
  14
  15 define void @loop(ptr nocapture %p, i64 %n) nounwind {
  16 entry:
  17   %j = icmp sgt i64 %n, 0
  18   br i1 %j, label %bb, label %return
  19
  20 bb:
  21   %i = phi i64 [ 0, %entry ], [ %i.next, %bb ]
  22   %pi = getelementptr double, ptr %p, i64 %i
  23   %i.next = add i64 %i, 1
  24   %pi.next = getelementptr double, ptr %p, i64 %i.next
  25   %x = load double, ptr %pi
  26   %y = load double, ptr %pi.next
  27   %z = fmul double %x, %y
  28   store double %z, ptr %pi
  29   %exitcond = icmp eq i64 %i.next, %n
  30   br i1 %exitcond, label %return, label %bb
  31
  32 return:
  33   ret void
  34 }
  35
  36 ; Slightly more involved: p[j][i], p[j][i+1], and p[j+1][i] don't alias.
  37
  38 ; CHECK-LABEL: Function: nestedloop
  39 ; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
  40 ; CHECK: NoAlias: double* %pi.j, double* %pi.j.next
  41 ; CHECK: NoAlias: double* %pi.j.next, double* %pi.next.j
  42
  43 define void @nestedloop(ptr nocapture %p, i64 %m) nounwind {
  44 entry:
  45   %k = icmp sgt i64 %m, 0
  46   br i1 %k, label %guard, label %return
  47
  48 guard:
  49   %l = icmp sgt i64 91, 0
  50   br i1 %l, label %outer.loop, label %return
  51
  52 outer.loop:
  53   %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
  54   br label %bb
  55
  56 bb:
  57   %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
  58   %i.next = add i64 %i, 1
  59
  60   %e = add i64 %i, %j
  61   %pi.j = getelementptr double, ptr %p, i64 %e
  62   %f = add i64 %i.next, %j
  63   %pi.next.j = getelementptr double, ptr %p, i64 %f
  64   %x = load double, ptr %pi.j
  65   %y = load double, ptr %pi.next.j
  66   %z = fmul double %x, %y
  67   store double %z, ptr %pi.j
  68
  69   %o = add i64 %j, 91
  70   %g = add i64 %i, %o
  71   %pi.j.next = getelementptr double, ptr %p, i64 %g
  72   %a = load double, ptr %pi.j.next
  73   %b = fmul double %x, %a
  74   store double %b, ptr %pi.j.next
  75
  76   %exitcond = icmp eq i64 %i.next, 91
  77   br i1 %exitcond, label %outer.latch, label %bb
  78
  79 outer.latch:
  80   %j.next = add i64 %j, 91
  81   %h = icmp eq i64 %j.next, %m
  82   br i1 %h, label %return, label %outer.loop
  83
  84 return:
  85   ret void
  86 }
  87
  88 ; Even more involved: same as nestedloop, but with a variable extent.
  89 ; When n is 1, p[j+1][i] does alias p[j][i+1], and there's no way to
  90 ; prove whether n will be greater than 1, so that relation will always
  91 ; by MayAlias. The loop is guarded by a n > 0 test though, so
  92 ; p[j+1][i] and p[j][i] can theoretically be determined to be NoAlias,
  93 ; however the analysis currently doesn't do that.
  94 ; TODO: Make the analysis smarter and turn that MayAlias into a NoAlias.
  95
  96 ; CHECK-LABEL: Function: nestedloop_more
  97 ; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
  98 ; CHECK: MayAlias: double* %pi.j, double* %pi.j.next
  99
 100 define void @nestedloop_more(ptr nocapture %p, i64 %n, i64 %m) nounwind {
 101 entry:
 102   %k = icmp sgt i64 %m, 0
 103   br i1 %k, label %guard, label %return
 104
 105 guard:
 106   %l = icmp sgt i64 %n, 0
 107   br i1 %l, label %outer.loop, label %return
 108
 109 outer.loop:
 110   %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
 111   br label %bb
 112
 113 bb:
 114   %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
 115   %i.next = add i64 %i, 1
 116
 117   %e = add i64 %i, %j
 118   %pi.j = getelementptr double, ptr %p, i64 %e
 119   %f = add i64 %i.next, %j
 120   %pi.next.j = getelementptr double, ptr %p, i64 %f
 121   %x = load double, ptr %pi.j
 122   %y = load double, ptr %pi.next.j
 123   %z = fmul double %x, %y
 124   store double %z, ptr %pi.j
 125
 126   %o = add i64 %j, %n
 127   %g = add i64 %i, %o
 128   %pi.j.next = getelementptr double, ptr %p, i64 %g
 129   %a = load double, ptr %pi.j.next
 130   %b = fmul double %x, %a
 131   store double %b, ptr %pi.j.next
 132
 133   %exitcond = icmp eq i64 %i.next, %n
 134   br i1 %exitcond, label %outer.latch, label %bb
 135
 136 outer.latch:
 137   %j.next = add i64 %j, %n
 138   %h = icmp eq i64 %j.next, %m
 139   br i1 %h, label %return, label %outer.loop
 140
 141 return:
 142   ret void
 143 }
 144
 145 ; ScalarEvolution expands field offsets into constants, which allows it to
 146 ; do aggressive analysis. Contrast this with BasicAA, which works by
 147 ; recognizing GEP idioms.
 148
 149 %struct.A = type { %struct.B, i32, i32 }
 150 %struct.B = type { double }
 151
 152 ; CHECK-LABEL: Function: foo
 153 ; CHECK-DAG: NoAlias: %struct.B* %A, i32* %Z
 154 ; CHECK-DAG: NoAlias: %struct.B* %A, %struct.B* %C
 155 ; CHECK-DAG: MustAlias: %struct.B* %C, i32* %Z
 156 ; CHECK-DAG: NoAlias: %struct.B* %A, i32* %C
 157 ; CHECK-DAG: MustAlias: i32* %C, i32* %Z
 158 ; CHECK-DAG: MustAlias: %struct.B* %C, i32* %Y
 159 ; CHECK-DAG: MustAlias: i32* %C, i32* %Y
 160
 161 define void @foo() {
 162 entry:
 163   %A = alloca %struct.A
 164   %Z = getelementptr %struct.A, ptr %A, i32 0, i32 1
 165   %C = getelementptr %struct.B, ptr %A, i32 1
 166   %Y = getelementptr %struct.A, ptr %A, i32 0, i32 1
 167   load %struct.B, ptr %A
 168   load %struct.B, ptr %C
 169   load i32, ptr %C
 170   load i32, ptr %Y
 171   load i32, ptr %Z
 172   ret void
 173 }
 174
 175 ; CHECK-LABEL: Function: bar
 176 ; CHECK-DAG: NoAlias: %struct.B* %M, i32* %P
 177 ; CHECK-DAG: NoAlias: %struct.B* %M, %struct.B* %R
 178 ; CHECK-DAG: MustAlias: i32* %P, %struct.B* %R
 179 ; CHECK-DAG: NoAlias: %struct.B* %M, i32* %R
 180 ; CHECK-DAG: MustAlias: i32* %P, i32* %R
 181 ; CHECK-DAG: MustAlias: %struct.B* %R, i32* %V
 182 ; CHECK-DAG: MustAlias: i32* %R, i32* %V
 183
 184 define void @bar() {
 185   %M = alloca %struct.A
 186   %P = getelementptr %struct.A, ptr %M, i32 0, i32 1
 187   %R = getelementptr %struct.B, ptr %M, i32 1
 188   %V = getelementptr %struct.A, ptr %M, i32 0, i32 1
 189   load %struct.B, ptr %M
 190   load %struct.B, ptr %R
 191   load i32, ptr %P
 192   load i32, ptr %V
 193   load i32, ptr %R
 194   ret void
 195 }
 196
 197 ; CHECK: Function: nonnegative: 2 pointers, 0 call sites
 198 ; CHECK: NoAlias:  i64* %arrayidx, i64* %p
 199
 200 define void @nonnegative(ptr %p) nounwind {
 201 entry:
 202   br label %for.body
 203
 204 for.body:                                         ; preds = %entry, %for.body
 205   %i = phi i64 [ %inc, %for.body ], [ 0, %entry ] ; <i64> [#uses=2]
 206   %inc = add nsw i64 %i, 1                         ; <i64> [#uses=2]
 207   %arrayidx = getelementptr inbounds i64, ptr %p, i64 %inc
 208   store i64 0, ptr %arrayidx
 209   %tmp6 = load i64, ptr %p                            ; <i64> [#uses=1]
 210   %cmp = icmp slt i64 %inc, %tmp6                 ; <i1> [#uses=1]
 211   br i1 %cmp, label %for.body, label %for.end
 212
 213 for.end:                                          ; preds = %for.body, %entry
 214   ret void
 215 }
 216
 217 ; CHECK-LABEL: Function: test_no_dom: 3 pointers, 0 call sites
 218 ; CHECK: MayAlias:      double* %addr1, double* %data
 219 ; CHECK: NoAlias:       double* %addr2, double* %data
 220 ; CHECK: MayAlias:      double* %addr1, double* %addr2
 221
 222 ; In this case, checking %addr1 and %add2 involves two addrecs in two
 223 ; different loops where neither dominates the other.  This used to crash
 224 ; because we expected the arguments to an AddExpr to have a strict
 225 ; dominance order.
 226 define void @test_no_dom(ptr %data) {
 227 entry:
 228   load double, ptr %data
 229   br label %for.body
 230
 231 for.body:
 232   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]
 233   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 234   br i1 undef, label %subloop1, label %subloop2
 235
 236 subloop1:
 237   %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]
 238   %iv1.next = add i32 %iv1, 1
 239   %addr1 = getelementptr double, ptr %data, i32 %iv1
 240   store double 0.0, ptr %addr1
 241   %cmp1 = icmp slt i32 %iv1, 200
 242   br i1 %cmp1, label %subloop1, label %for.latch
 243
 244 subloop2:
 245   %iv2 = phi i32 [400, %for.body], [%iv2.next, %subloop2]
 246   %iv2.next = add i32 %iv2, 1
 247   %addr2 = getelementptr double, ptr %data, i32 %iv2
 248   store double 0.0, ptr %addr2
 249   %cmp2 = icmp slt i32 %iv2, 600
 250   br i1 %cmp2, label %subloop2, label %for.latch
 251
 252 for.latch:
 253   br label %for.body
 254
 255 for.end:
 256   ret void
 257 }
 258
 259 declare ptr @get_addr(i32 %i)
 260
 261 ; CHECK-LABEL: Function: test_no_dom2: 3 pointers, 2 call sites
 262 ; CHECK: MayAlias:      double* %addr1, double* %data
 263 ; CHECK: MayAlias:      double* %addr2, double* %data
 264 ; CHECK: MayAlias:      double* %addr1, double* %addr2
 265
 266 ; In this case, checking %addr1 and %add2 involves two addrecs in two
 267 ; different loops where neither dominates the other.  This is analogous
 268 ; to test_no_dom, but involves SCEVUnknown as opposed to SCEVAddRecExpr.
 269 define void @test_no_dom2(ptr %data) {
 270 entry:
 271   load double, ptr %data
 272   br label %for.body
 273
 274 for.body:
 275   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]
 276   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 277   br i1 undef, label %subloop1, label %subloop2
 278
 279 subloop1:
 280   %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]
 281   %iv1.next = add i32 %iv1, 1
 282   %addr1 = call ptr @get_addr(i32 %iv1)
 283   store double 0.0, ptr %addr1
 284   %cmp1 = icmp slt i32 %iv1, 200
 285   br i1 %cmp1, label %subloop1, label %for.latch
 286
 287 subloop2:
 288   %iv2 = phi i32 [400, %for.body], [%iv2.next, %subloop2]
 289   %iv2.next = add i32 %iv2, 1
 290   %addr2 = call ptr @get_addr(i32 %iv2)
 291   store double 0.0, ptr %addr2
 292   %cmp2 = icmp slt i32 %iv2, 600
 293   br i1 %cmp2, label %subloop2, label %for.latch
 294
 295 for.latch:
 296   br label %for.body
 297
 298 for.end:
 299   ret void
 300 }
 301
 302
 303 ; CHECK-LABEL: Function: test_dom: 3 pointers, 0 call sites
 304 ; CHECK: MayAlias:      double* %addr1, double* %data
 305 ; CHECK: NoAlias:       double* %addr2, double* %data
 306 ; CHECK: NoAlias:       double* %addr1, double* %addr2
 307
 308 ; This is a variant of test_non_dom where the second subloop is
 309 ; dominated by the first.  As a result of that, we can nest the
 310 ; addrecs and cancel out the %data base pointer.
 311 define void @test_dom(ptr %data) {
 312 entry:
 313   load double, ptr %data
 314   br label %for.body
 315
 316 for.body:
 317   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]
 318   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
 319   br label %subloop1
 320
 321 subloop1:
 322   %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]
 323   %iv1.next = add i32 %iv1, 1
 324   %addr1 = getelementptr double, ptr %data, i32 %iv1
 325   store double 0.0, ptr %addr1
 326   %cmp1 = icmp slt i32 %iv1, 200
 327   br i1 %cmp1, label %subloop1, label %subloop2
 328
 329 subloop2:
 330   %iv2 = phi i32 [400, %subloop1], [%iv2.next, %subloop2]
 331   %iv2.next = add i32 %iv2, 1
 332   %addr2 = getelementptr double, ptr %data, i32 %iv2
 333   store double 0.0, ptr %addr2
 334   %cmp2 = icmp slt i32 %iv2, 600
 335   br i1 %cmp2, label %subloop2, label %for.latch
 336
 337 for.latch:
 338   br label %for.body
 339
 340 for.end:
 341   ret void
 342 }