test/Transforms/IndVarSimplify/lftr-reuse.ll

   1 ; RUN: opt < %s -indvars -S | FileCheck %s
   2 ;
   3 ; Make sure that indvars can perform LFTR without a canonical IV.
   4
   5 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
   6
   7 ; Perform LFTR using the original pointer-type IV.
   8
   9 declare void @use(double %x)
  10
  11 ;  for(char* p = base; p < base + n; ++p) {
  12 ;    *p = p-base;
  13 ;  }
  14 define void @ptriv(i8* %base, i32 %n) nounwind {
  15 entry:
  16   %idx.ext = sext i32 %n to i64
  17   %add.ptr = getelementptr inbounds i8, i8* %base, i64 %idx.ext
  18   %cmp1 = icmp ult i8* %base, %add.ptr
  19   br i1 %cmp1, label %for.body, label %for.end
  20
  21 ; CHECK: for.body:
  22 ; CHECK: phi i8*
  23 ; CHECK-NOT: phi
  24 ; CHECK-NOT: add
  25 ; CHECK: icmp ne i8*
  26 ; CHECK: br i1
  27 for.body:
  28   %p.02 = phi i8* [ %base, %entry ], [ %incdec.ptr, %for.body ]
  29   ; cruft to make the IV useful
  30   %sub.ptr.lhs.cast = ptrtoint i8* %p.02 to i64
  31   %sub.ptr.rhs.cast = ptrtoint i8* %base to i64
  32   %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  33   %conv = trunc i64 %sub.ptr.sub to i8
  34   store i8 %conv, i8* %p.02
  35   %incdec.ptr = getelementptr inbounds i8, i8* %p.02, i32 1
  36   %cmp = icmp ult i8* %incdec.ptr, %add.ptr
  37   br i1 %cmp, label %for.body, label %for.end
  38
  39 for.end:
  40   ret void
  41 }
  42
  43 ; This test checks that SCEVExpander can handle an outer loop that has been
  44 ; simplified, and as a result the inner loop's exit test will be rewritten.
  45 define void @expandOuterRecurrence(i32 %arg) nounwind {
  46 entry:
  47   %sub1 = sub nsw i32 %arg, 1
  48   %cmp1 = icmp slt i32 0, %sub1
  49   br i1 %cmp1, label %outer, label %exit
  50
  51 ; CHECK: outer:
  52 ; CHECK: icmp slt
  53 outer:
  54   %i = phi i32 [ 0, %entry ], [ %i.inc, %outer.inc ]
  55   %sub2 = sub nsw i32 %arg, %i
  56   %sub3 = sub nsw i32 %sub2, 1
  57   %cmp2 = icmp slt i32 0, %sub3
  58   br i1 %cmp2, label %inner.ph, label %outer.inc
  59
  60 inner.ph:
  61   br label %inner
  62
  63 ; CHECK: inner:
  64 ; CHECK: br i1
  65 inner:
  66   %j = phi i32 [ 0, %inner.ph ], [ %j.inc, %inner ]
  67   %j.inc = add nsw i32 %j, 1
  68   %cmp3 = icmp slt i32 %j.inc, %sub3
  69   br i1 %cmp3, label %inner, label %outer.inc
  70
  71 ; CHECK: outer.inc:
  72 ; CHECK: icmp ne
  73 ; CHECK: br i1
  74 outer.inc:
  75   %i.inc = add nsw i32 %i, 1
  76   %cmp4 = icmp slt i32 %i.inc, %sub1
  77   br i1 %cmp4, label %outer, label %exit
  78
  79 exit:
  80   ret void
  81 }
  82
  83 ; Force SCEVExpander to look for an existing well-formed phi.
  84 ; Perform LFTR without generating extra preheader code.
  85 define void @guardedloop([0 x double]* %matrix, [0 x double]* %vector,
  86                          i32 %irow, i32 %ilead) nounwind {
  87 ; CHECK: entry:
  88 ; CHECK-NOT: zext
  89 ; CHECK-NOT: add
  90 ; CHECK: loop:
  91 ; CHECK: phi i64
  92 ; CHECK: phi i64
  93 ; CHECK-NOT: phi
  94 ; CHECK: icmp ne
  95 ; CHECK: br i1
  96 entry:
  97   %cmp = icmp slt i32 1, %irow
  98   br i1 %cmp, label %loop, label %return
  99
 100 loop:
 101   %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ]
 102   %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
 103   %diagidx = add nsw i32 %rowidx, %i
 104   %diagidxw = sext i32 %diagidx to i64
 105   %matrixp = getelementptr inbounds [0 x double], [0 x double]* %matrix, i32 0, i64 %diagidxw
 106   %v1 = load double, double* %matrixp
 107   call void @use(double %v1)
 108   %iw = sext i32 %i to i64
 109   %vectorp = getelementptr inbounds [0 x double], [0 x double]* %vector, i32 0, i64 %iw
 110   %v2 = load double, double* %vectorp
 111   call void @use(double %v2)
 112   %row.inc = add nsw i32 %rowidx, %ilead
 113   %i.inc = add nsw i32 %i, 1
 114   %cmp196 = icmp slt i32 %i.inc, %irow
 115   br i1 %cmp196, label %loop, label %return
 116
 117 return:
 118   ret void
 119 }
 120
 121 ; Avoid generating extra code to materialize a trip count. Skip LFTR.
 122 define void @unguardedloop([0 x double]* %matrix, [0 x double]* %vector,
 123                            i32 %irow, i32 %ilead) nounwind {
 124 entry:
 125   br label %loop
 126
 127 ; CHECK: entry:
 128 ; CHECK-NOT: zext
 129 ; CHECK-NOT: add
 130 ; CHECK: loop:
 131 ; CHECK: phi i64
 132 ; CHECK-NOT: phi
 133 ; CHECK: icmp slt
 134 ; CHECK: br i1
 135 loop:
 136   %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ]
 137   %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
 138   %diagidx = add nsw i32 %rowidx, %i
 139   %diagidxw = sext i32 %diagidx to i64
 140   %matrixp = getelementptr inbounds [0 x double], [0 x double]* %matrix, i32 0, i64 %diagidxw
 141   %v1 = load double, double* %matrixp
 142   %iw = sext i32 %i to i64
 143   %vectorp = getelementptr inbounds [0 x double], [0 x double]* %vector, i32 0, i64 %iw
 144   %v2 = load double, double* %vectorp
 145   %row.inc = add nsw i32 %rowidx, %ilead
 146   %i.inc = add nsw i32 %i, 1
 147   %cmp196 = icmp slt i32 %i.inc, %irow
 148   br i1 %cmp196, label %loop, label %return
 149
 150 return:
 151   ret void
 152 }
 153
 154 ; Remove %i which is only used by the exit test.
 155 ; Verify that SCEV can still compute a backedge count from the sign
 156 ; extended %n, used for pointer comparison by LFTR.
 157 ;
 158 ; TODO: Fix for PR13371 currently makes this impossible. See
 159 ; IndVarSimplify.cpp hasConcreteDef(). We may want to change to undef rules.
 160 define void @geplftr(i8* %base, i32 %x, i32 %y, i32 %n) nounwind {
 161 entry:
 162   %x.ext = sext i32 %x to i64
 163   %add.ptr = getelementptr inbounds i8, i8* %base, i64 %x.ext
 164   %y.ext = sext i32 %y to i64
 165   %add.ptr10 = getelementptr inbounds i8, i8* %add.ptr, i64 %y.ext
 166   %lim = add i32 %x, %n
 167   %cmp.ph = icmp ult i32 %x, %lim
 168   br i1 %cmp.ph, label %loop, label %exit
 169 ; CHECK-LABEL: @geplftr(
 170 ; CHECK: loop:
 171 ; CHECK: phi i8*
 172 ; DISABLE-NOT: phi      // This check is currently disabled
 173 ; CHECK: getelementptr
 174 ; CHECK: store
 175 ; DISABLE: icmp ne i8*  // This check is currently disabled
 176 ; CHECK: br i1
 177 loop:
 178   %i = phi i32 [ %x, %entry ], [ %inc, %loop ]
 179   %aptr = phi i8* [ %add.ptr10, %entry ], [ %incdec.ptr, %loop ]
 180   %incdec.ptr = getelementptr inbounds i8, i8* %aptr, i32 1
 181   store i8 3, i8* %aptr
 182   %inc = add i32 %i, 1
 183   %cmp = icmp ult i32 %inc, %lim
 184   br i1 %cmp, label %loop, label %exit
 185
 186 exit:
 187   ret void
 188 }
 189
 190 ; Exercise backedge taken count verification with a never-taken loop.
 191 define void @nevertaken() nounwind uwtable ssp {
 192 entry:
 193   br label %loop
 194 ; CHECK-LABEL: @nevertaken(
 195 ; CHECK: loop:
 196 ; CHECK-NOT: phi
 197 ; CHECK-NOT: add
 198 ; CHECK-NOT: icmp
 199 ; CHECK: exit:
 200 loop:
 201   %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
 202   %inc = add nsw i32 %i, 1
 203   %cmp = icmp sle i32 %inc, 0
 204   br i1 %cmp, label %loop, label %exit
 205
 206 exit:
 207   ret void
 208 }
 209
 210 ; Test LFTR on an IV whose recurrence start is a non-unit pointer type.
 211 define void @aryptriv([256 x i8]* %base, i32 %n) nounwind {
 212 entry:
 213   %ivstart = getelementptr inbounds [256 x i8], [256 x i8]* %base, i32 0, i32 0
 214   %ivend = getelementptr inbounds [256 x i8], [256 x i8]* %base, i32 0, i32 %n
 215   %cmp.ph = icmp ult i8* %ivstart, %ivend
 216   br i1 %cmp.ph, label %loop, label %exit
 217
 218 ; CHECK: loop:
 219 ; CHECK: phi i8*
 220 ; CHECK-NOT: phi
 221 ; CHECK: getelementptr
 222 ; CHECK: store
 223 ; CHECK: icmp ne i8*
 224 ; CHECK: br i1
 225 loop:
 226   %aptr = phi i8* [ %ivstart, %entry ], [ %incdec.ptr, %loop ]
 227   %incdec.ptr = getelementptr inbounds i8, i8* %aptr, i32 1
 228   store i8 3, i8* %aptr
 229   %cmp = icmp ult i8* %incdec.ptr, %ivend
 230   br i1 %cmp, label %loop, label %exit
 231
 232 exit:
 233   ret void
 234 }