test/Analysis/ScalarEvolution/scev-aa.ll

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