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