Home | History | Annotate | Download | only in ScalarEvolution
      1 ; RUN: opt < %s -scev-aa -aa-eval -print-all-alias-modref-info \
      2 ; RUN:   2>&1 | FileCheck %s
      3 
      4 ; At the time of this writing, -basicaa 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: Function: loop: 3 pointers, 0 call sites
     13 ; CHECK: NoAlias: double* %pi, double* %pi.next
     14 
     15 define void @loop(double* 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* %p, i64 %i
     23   %i.next = add i64 %i, 1
     24   %pi.next = getelementptr double* %p, i64 %i.next
     25   %x = load double* %pi
     26   %y = load double* %pi.next
     27   %z = fmul double %x, %y
     28   store double %z, double* %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: Function: nestedloop: 4 pointers, 0 call sites
     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(double* 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* %p, i64 %e
     62   %f = add i64 %i.next, %j
     63   %pi.next.j = getelementptr double* %p, i64 %f
     64   %x = load double* %pi.j
     65   %y = load double* %pi.next.j
     66   %z = fmul double %x, %y
     67   store double %z, double* %pi.j
     68 
     69   %o = add i64 %j, 91
     70   %g = add i64 %i, %o
     71   %pi.j.next = getelementptr double* %p, i64 %g
     72   %a = load double* %pi.j.next
     73   %b = fmul double %x, %a
     74   store double %b, double* %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: Function: nestedloop_more: 4 pointers, 0 call sites
     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(double* 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* %p, i64 %e
    119   %f = add i64 %i.next, %j
    120   %pi.next.j = getelementptr double* %p, i64 %f
    121   %x = load double* %pi.j
    122   %y = load double* %pi.next.j
    123   %z = fmul double %x, %y
    124   store double %z, double* %pi.j
    125 
    126   %o = add i64 %j, %n
    127   %g = add i64 %i, %o
    128   %pi.j.next = getelementptr double* %p, i64 %g
    129   %a = load double* %pi.j.next
    130   %b = fmul double %x, %a
    131   store double %b, double* %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: Function: foo: 7 pointers, 0 call sites
    153 ; CHECK: NoAlias: %struct.B* %B, i32* %Z
    154 ; CHECK: NoAlias: %struct.B* %B, %struct.B* %C
    155 ; CHECK: MustAlias: %struct.B* %C, i32* %Z
    156 ; CHECK: NoAlias: %struct.B* %B, i32* %X
    157 ; CHECK: MustAlias: i32* %X, i32* %Z
    158 ; CHECK: MustAlias: %struct.B* %C, i32* %Y
    159 ; CHECK: MustAlias: i32* %X, i32* %Y
    160 
    161 define void @foo() {
    162 entry:
    163   %A = alloca %struct.A
    164   %B = getelementptr %struct.A* %A, i32 0, i32 0
    165   %Q = bitcast %struct.B* %B to %struct.A*
    166   %Z = getelementptr %struct.A* %Q, i32 0, i32 1
    167   %C = getelementptr %struct.B* %B, i32 1
    168   %X = bitcast %struct.B* %C to i32*
    169   %Y = getelementptr %struct.A* %A, i32 0, i32 1
    170   ret void
    171 }
    172 
    173 ; CHECK: Function: bar: 7 pointers, 0 call sites
    174 ; CHECK: NoAlias: %struct.B* %N, i32* %P
    175 ; CHECK: NoAlias: %struct.B* %N, %struct.B* %R
    176 ; CHECK: MustAlias: %struct.B* %R, i32* %P
    177 ; CHECK: NoAlias: %struct.B* %N, i32* %W
    178 ; CHECK: MustAlias: i32* %P, i32* %W
    179 ; CHECK: MustAlias: %struct.B* %R, i32* %V
    180 ; CHECK: MustAlias: i32* %V, i32* %W
    181 
    182 define void @bar() {
    183   %M = alloca %struct.A
    184   %N = getelementptr %struct.A* %M, i32 0, i32 0
    185   %O = bitcast %struct.B* %N to %struct.A*
    186   %P = getelementptr %struct.A* %O, i32 0, i32 1
    187   %R = getelementptr %struct.B* %N, i32 1
    188   %W = bitcast %struct.B* %R to i32*
    189   %V = getelementptr %struct.A* %M, i32 0, i32 1
    190   ret void
    191 }
    192 
    193 ; CHECK: Function: nonnegative: 2 pointers, 0 call sites
    194 ; CHECK: NoAlias:  i64* %arrayidx, i64* %p
    195 
    196 define void @nonnegative(i64* %p) nounwind {
    197 entry:
    198   br label %for.body
    199 
    200 for.body:                                         ; preds = %entry, %for.body
    201   %i = phi i64 [ %inc, %for.body ], [ 0, %entry ] ; <i64> [#uses=2]
    202   %inc = add nsw i64 %i, 1                         ; <i64> [#uses=2]
    203   %arrayidx = getelementptr inbounds i64* %p, i64 %inc
    204   store i64 0, i64* %arrayidx
    205   %tmp6 = load i64* %p                            ; <i64> [#uses=1]
    206   %cmp = icmp slt i64 %inc, %tmp6                 ; <i1> [#uses=1]
    207   br i1 %cmp, label %for.body, label %for.end
    208 
    209 for.end:                                          ; preds = %for.body, %entry
    210   ret void
    211 }
    212 
    213 ; CHECK: 14 no alias responses
    214 ; CHECK: 26 may alias responses
    215 ; CHECK: 18 must alias responses
    216