test/Analysis/ScalarEvolution/scev-aa.ll

   1 ; RUN: opt -disable-output < %s -disable-basicaa -scev-aa -aa-eval -print-all-alias-modref-info \
   2 ; RUN:   2>&1 | FileCheck %s
   3 ; RUN: opt -disable-output < %s -aa-pipeline=scev-aa -passes=aa-eval -print-all-alias-modref-info \
   4 ; RUN:   2>&1 | FileCheck %s
   5
   6 ; At the time of this writing, -basicaa misses the example of the form
   7 ; A[i+(j+1)] != A[i+j], which can arise from multi-dimensional array references,
   8 ; and the example of the form A[0] != A[i+1], where i+1 is known to be positive.
   9
  10 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
  11
  12 ; p[i] and p[i+1] don't alias.
  13
  14 ; CHECK: Function: loop: 3 pointers, 0 call sites
  15 ; CHECK: NoAlias: double* %pi, double* %pi.next
  16
  17 define void @loop(double* nocapture %p, i64 %n) nounwind {
  18 entry:
  19   %j = icmp sgt i64 %n, 0
  20   br i1 %j, label %bb, label %return
  21
  22 bb:
  23   %i = phi i64 [ 0, %entry ], [ %i.next, %bb ]
  24   %pi = getelementptr double, double* %p, i64 %i
  25   %i.next = add i64 %i, 1
  26   %pi.next = getelementptr double, double* %p, i64 %i.next
  27   %x = load double, double* %pi
  28   %y = load double, double* %pi.next
  29   %z = fmul double %x, %y
  30   store double %z, double* %pi
  31   %exitcond = icmp eq i64 %i.next, %n
  32   br i1 %exitcond, label %return, label %bb
  33
  34 return:
  35   ret void
  36 }
  37
  38 ; Slightly more involved: p[j][i], p[j][i+1], and p[j+1][i] don't alias.
  39
  40 ; CHECK: Function: nestedloop: 4 pointers, 0 call sites
  41 ; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
  42 ; CHECK: NoAlias: double* %pi.j, double* %pi.j.next
  43 ; CHECK: NoAlias: double* %pi.j.next, double* %pi.next.j
  44
  45 define void @nestedloop(double* nocapture %p, i64 %m) nounwind {
  46 entry:
  47   %k = icmp sgt i64 %m, 0
  48   br i1 %k, label %guard, label %return
  49
  50 guard:
  51   %l = icmp sgt i64 91, 0
  52   br i1 %l, label %outer.loop, label %return
  53
  54 outer.loop:
  55   %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
  56   br label %bb
  57
  58 bb:
  59   %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
  60   %i.next = add i64 %i, 1
  61
  62   %e = add i64 %i, %j
  63   %pi.j = getelementptr double, double* %p, i64 %e
  64   %f = add i64 %i.next, %j
  65   %pi.next.j = getelementptr double, double* %p, i64 %f
  66   %x = load double, double* %pi.j
  67   %y = load double, double* %pi.next.j
  68   %z = fmul double %x, %y
  69   store double %z, double* %pi.j
  70
  71   %o = add i64 %j, 91
  72   %g = add i64 %i, %o
  73   %pi.j.next = getelementptr double, double* %p, i64 %g
  74   %a = load double, double* %pi.j.next
  75   %b = fmul double %x, %a
  76   store double %b, double* %pi.j.next
  77
  78   %exitcond = icmp eq i64 %i.next, 91
  79   br i1 %exitcond, label %outer.latch, label %bb
  80
  81 outer.latch:
  82   %j.next = add i64 %j, 91
  83   %h = icmp eq i64 %j.next, %m
  84   br i1 %h, label %return, label %outer.loop
  85
  86 return:
  87   ret void
  88 }
  89
  90 ; Even more involved: same as nestedloop, but with a variable extent.
  91 ; When n is 1, p[j+1][i] does alias p[j][i+1], and there's no way to
  92 ; prove whether n will be greater than 1, so that relation will always
  93 ; by MayAlias. The loop is guarded by a n > 0 test though, so
  94 ; p[j+1][i] and p[j][i] can theoretically be determined to be NoAlias,
  95 ; however the analysis currently doesn't do that.
  96 ; TODO: Make the analysis smarter and turn that MayAlias into a NoAlias.
  97
  98 ; CHECK: Function: nestedloop_more: 4 pointers, 0 call sites
  99 ; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
 100 ; CHECK: MayAlias: double* %pi.j, double* %pi.j.next
 101
 102 define void @nestedloop_more(double* nocapture %p, i64 %n, i64 %m) nounwind {
 103 entry:
 104   %k = icmp sgt i64 %m, 0
 105   br i1 %k, label %guard, label %return
 106
 107 guard:
 108   %l = icmp sgt i64 %n, 0
 109   br i1 %l, label %outer.loop, label %return
 110
 111 outer.loop:
 112   %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
 113   br label %bb
 114
 115 bb:
 116   %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
 117   %i.next = add i64 %i, 1
 118
 119   %e = add i64 %i, %j
 120   %pi.j = getelementptr double, double* %p, i64 %e
 121   %f = add i64 %i.next, %j
 122   %pi.next.j = getelementptr double, double* %p, i64 %f
 123   %x = load double, double* %pi.j
 124   %y = load double, double* %pi.next.j
 125   %z = fmul double %x, %y
 126   store double %z, double* %pi.j
 127
 128   %o = add i64 %j, %n
 129   %g = add i64 %i, %o
 130   %pi.j.next = getelementptr double, double* %p, i64 %g
 131   %a = load double, double* %pi.j.next
 132   %b = fmul double %x, %a
 133   store double %b, double* %pi.j.next
 134
 135   %exitcond = icmp eq i64 %i.next, %n
 136   br i1 %exitcond, label %outer.latch, label %bb
 137
 138 outer.latch:
 139   %j.next = add i64 %j, %n
 140   %h = icmp eq i64 %j.next, %m
 141   br i1 %h, label %return, label %outer.loop
 142
 143 return:
 144   ret void
 145 }
 146
 147 ; ScalarEvolution expands field offsets into constants, which allows it to
 148 ; do aggressive analysis. Contrast this with BasicAA, which works by
 149 ; recognizing GEP idioms.
 150
 151 %struct.A = type { %struct.B, i32, i32 }
 152 %struct.B = type { double }
 153
 154 ; CHECK: Function: foo: 7 pointers, 0 call sites
 155 ; CHECK: NoAlias: %struct.B* %B, i32* %Z
 156 ; CHECK: NoAlias: %struct.B* %B, %struct.B* %C
 157 ; CHECK: MustAlias: %struct.B* %C, i32* %Z
 158 ; CHECK: NoAlias: %struct.B* %B, i32* %X
 159 ; CHECK: MustAlias: i32* %X, i32* %Z
 160 ; CHECK: MustAlias: %struct.B* %C, i32* %Y
 161 ; CHECK: MustAlias: i32* %X, i32* %Y
 162
 163 define void @foo() {
 164 entry:
 165   %A = alloca %struct.A
 166   %B = getelementptr %struct.A, %struct.A* %A, i32 0, i32 0
 167   %Q = bitcast %struct.B* %B to %struct.A*
 168   %Z = getelementptr %struct.A, %struct.A* %Q, i32 0, i32 1
 169   %C = getelementptr %struct.B, %struct.B* %B, i32 1
 170   %X = bitcast %struct.B* %C to i32*
 171   %Y = getelementptr %struct.A, %struct.A* %A, i32 0, i32 1
 172   ret void
 173 }
 174
 175 ; CHECK: Function: bar: 7 pointers, 0 call sites
 176 ; CHECK: NoAlias: %struct.B* %N, i32* %P
 177 ; CHECK: NoAlias: %struct.B* %N, %struct.B* %R
 178 ; CHECK: MustAlias: %struct.B* %R, i32* %P
 179 ; CHECK: NoAlias: %struct.B* %N, i32* %W
 180 ; CHECK: MustAlias: i32* %P, i32* %W
 181 ; CHECK: MustAlias: %struct.B* %R, i32* %V
 182 ; CHECK: MustAlias: i32* %V, i32* %W
 183
 184 define void @bar() {
 185   %M = alloca %struct.A
 186   %N = getelementptr %struct.A, %struct.A* %M, i32 0, i32 0
 187   %O = bitcast %struct.B* %N to %struct.A*
 188   %P = getelementptr %struct.A, %struct.A* %O, i32 0, i32 1
 189   %R = getelementptr %struct.B, %struct.B* %N, i32 1
 190   %W = bitcast %struct.B* %R to i32*
 191   %V = getelementptr %struct.A, %struct.A* %M, i32 0, i32 1
 192   ret void
 193 }
 194
 195 ; CHECK: Function: nonnegative: 2 pointers, 0 call sites
 196 ; CHECK: NoAlias:  i64* %arrayidx, i64* %p
 197
 198 define void @nonnegative(i64* %p) nounwind {
 199 entry:
 200   br label %for.body
 201
 202 for.body:                                         ; preds = %entry, %for.body
 203   %i = phi i64 [ %inc, %for.body ], [ 0, %entry ] ; <i64> [#uses=2]
 204   %inc = add nsw i64 %i, 1                         ; <i64> [#uses=2]
 205   %arrayidx = getelementptr inbounds i64, i64* %p, i64 %inc
 206   store i64 0, i64* %arrayidx
 207   %tmp6 = load i64, i64* %p                            ; <i64> [#uses=1]
 208   %cmp = icmp slt i64 %inc, %tmp6                 ; <i1> [#uses=1]
 209   br i1 %cmp, label %for.body, label %for.end
 210
 211 for.end:                                          ; preds = %for.body, %entry
 212   ret void
 213 }
 214
 215 ; CHECK: 14 no alias responses
 216 ; CHECK: 26 may alias responses
 217 ; CHECK: 18 must alias responses