test/Transforms/IndVarSimplify/iv-widen.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -indvars -S | FileCheck %s
   3 ; RUN: opt < %s -S -passes='lcssa,loop-simplify,require<targetir>,require<scalar-evolution>,require<domtree>,loop(indvars)' | FileCheck %s
   4
   5 ; Provide legal integer types.
   6 target datalayout = "n8:16:32:64"
   7
   8
   9 target triple = "x86_64-apple-darwin"
  10
  11 declare void @use(i64 %x)
  12
  13 ; Only one phi now.
  14 ; One trunc for the gep.
  15 ; One trunc for the dummy() call.
  16 define void @loop_0(i32* %a) {
  17 ; CHECK-LABEL: @loop_0(
  18 ; CHECK-NEXT:  Prologue:
  19 ; CHECK-NEXT:    br i1 undef, label [[B18_PREHEADER:%.*]], label [[B6:%.*]]
  20 ; CHECK:       B18.preheader:
  21 ; CHECK-NEXT:    br label [[B18:%.*]]
  22 ; CHECK:       B18:
  23 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 0, [[B18_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[B24:%.*]] ]
  24 ; CHECK-NEXT:    call void @use(i64 [[INDVARS_IV]])
  25 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
  26 ; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[INDVARS_IV]] to i32
  27 ; CHECK-NEXT:    [[O:%.*]] = getelementptr i32, i32* [[A:%.*]], i32 [[TMP0]]
  28 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[O]]
  29 ; CHECK-NEXT:    [[T:%.*]] = icmp eq i32 [[V]], 0
  30 ; CHECK-NEXT:    br i1 [[T]], label [[EXIT24:%.*]], label [[B24]]
  31 ; CHECK:       B24:
  32 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], 20
  33 ; CHECK-NEXT:    br i1 [[T2]], label [[B6_LOOPEXIT:%.*]], label [[B18]]
  34 ; CHECK:       B6.loopexit:
  35 ; CHECK-NEXT:    br label [[B6]]
  36 ; CHECK:       B6:
  37 ; CHECK-NEXT:    ret void
  38 ; CHECK:       exit24:
  39 ; CHECK-NEXT:    [[DOT02_LCSSA_WIDE:%.*]] = phi i64 [ [[INDVARS_IV]], [[B18]] ]
  40 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[DOT02_LCSSA_WIDE]] to i32
  41 ; CHECK-NEXT:    call void @dummy(i32 [[TMP1]])
  42 ; CHECK-NEXT:    unreachable
  43 ;
  44 Prologue:
  45   br i1 undef, label %B18, label %B6
  46
  47 B18:                                        ; preds = %B24, %Prologue
  48   %.02 = phi i32 [ 0, %Prologue ], [ %tmp33, %B24 ]
  49   %tmp23 = zext i32 %.02 to i64
  50   call void @use(i64 %tmp23)
  51   %tmp33 = add i32 %.02, 1
  52   %o = getelementptr i32, i32* %a, i32 %.02
  53   %v = load i32, i32* %o
  54   %t = icmp eq i32 %v, 0
  55   br i1 %t, label %exit24, label %B24
  56
  57 B24:                                        ; preds = %B18
  58   %t2 = icmp eq i32 %tmp33, 20
  59   br i1 %t2, label %B6, label %B18
  60
  61 B6:                                       ; preds = %Prologue
  62   ret void
  63
  64 exit24:                      ; preds = %B18
  65   call void @dummy(i32 %.02)
  66   unreachable
  67 }
  68
  69 ; Make sure that dead zext is removed and no widening happens.
  70 define void @loop_0_dead(i32* %a) {
  71 ; CHECK-LABEL: @loop_0_dead(
  72 ; CHECK-NEXT:  Prologue:
  73 ; CHECK-NEXT:    br i1 undef, label [[B18_PREHEADER:%.*]], label [[B6:%.*]]
  74 ; CHECK:       B18.preheader:
  75 ; CHECK-NEXT:    br label [[B18:%.*]]
  76 ; CHECK:       B18:
  77 ; CHECK-NEXT:    [[DOT02:%.*]] = phi i32 [ [[TMP33:%.*]], [[B24:%.*]] ], [ 0, [[B18_PREHEADER]] ]
  78 ; CHECK-NEXT:    [[TMP33]] = add nuw i32 [[DOT02]], 1
  79 ; CHECK-NEXT:    [[O:%.*]] = getelementptr i32, i32* [[A:%.*]], i32 [[DOT02]]
  80 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[O]]
  81 ; CHECK-NEXT:    [[T:%.*]] = icmp eq i32 [[V]], 0
  82 ; CHECK-NEXT:    br i1 [[T]], label [[EXIT24:%.*]], label [[B24]]
  83 ; CHECK:       B24:
  84 ; CHECK-NEXT:    [[T2:%.*]] = icmp eq i32 [[TMP33]], 20
  85 ; CHECK-NEXT:    br i1 [[T2]], label [[B6_LOOPEXIT:%.*]], label [[B18]]
  86 ; CHECK:       B6.loopexit:
  87 ; CHECK-NEXT:    br label [[B6]]
  88 ; CHECK:       B6:
  89 ; CHECK-NEXT:    ret void
  90 ; CHECK:       exit24:
  91 ; CHECK-NEXT:    [[DOT02_LCSSA:%.*]] = phi i32 [ [[DOT02]], [[B18]] ]
  92 ; CHECK-NEXT:    call void @dummy(i32 [[DOT02_LCSSA]])
  93 ; CHECK-NEXT:    unreachable
  94 ;
  95 Prologue:
  96   br i1 undef, label %B18, label %B6
  97
  98 B18:                                        ; preds = %B24, %Prologue
  99   %.02 = phi i32 [ 0, %Prologue ], [ %tmp33, %B24 ]
 100   %tmp23 = zext i32 %.02 to i64
 101   %tmp33 = add i32 %.02, 1
 102   %o = getelementptr i32, i32* %a, i32 %.02
 103   %v = load i32, i32* %o
 104   %t = icmp eq i32 %v, 0
 105   br i1 %t, label %exit24, label %B24
 106
 107 B24:                                        ; preds = %B18
 108   %t2 = icmp eq i32 %tmp33, 20
 109   br i1 %t2, label %B6, label %B18
 110
 111 B6:                                       ; preds = %Prologue
 112   ret void
 113
 114 exit24:                      ; preds = %B18
 115   call void @dummy(i32 %.02)
 116   unreachable
 117 }
 118
 119 define void @loop_1(i32 %lim) {
 120 ; CHECK-LABEL: @loop_1(
 121 ; CHECK-NEXT:  entry:
 122 ; CHECK-NEXT:    [[ENTRY_COND:%.*]] = icmp ne i32 [[LIM:%.*]], 0
 123 ; CHECK-NEXT:    br i1 [[ENTRY_COND]], label [[LOOP_PREHEADER:%.*]], label [[LEAVE:%.*]]
 124 ; CHECK:       loop.preheader:
 125 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[LIM]] to i64
 126 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 127 ; CHECK:       loop:
 128 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[LOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ]
 129 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 130 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], -1
 131 ; CHECK-NEXT:    call void @dummy.i64(i64 [[TMP1]])
 132 ; CHECK-NEXT:    [[BE_COND:%.*]] = icmp ult i64 [[INDVARS_IV_NEXT]], [[TMP0]]
 133 ; CHECK-NEXT:    br i1 [[BE_COND]], label [[LOOP]], label [[LEAVE_LOOPEXIT:%.*]]
 134 ; CHECK:       leave.loopexit:
 135 ; CHECK-NEXT:    br label [[LEAVE]]
 136 ; CHECK:       leave:
 137 ; CHECK-NEXT:    ret void
 138 ;
 139   entry:
 140   %entry.cond = icmp ne i32 %lim, 0
 141   br i1 %entry.cond, label %loop, label %leave
 142
 143   loop:
 144
 145   %iv = phi i32 [ 1, %entry ], [ %iv.inc, %loop ]
 146   %iv.inc = add i32 %iv, 1
 147   %iv.inc.sub = add i32 %iv, -1
 148   %iv.inc.sub.zext = zext i32 %iv.inc.sub to i64
 149   call void @dummy.i64(i64 %iv.inc.sub.zext)
 150   %be.cond = icmp ult i32 %iv.inc, %lim
 151   br i1 %be.cond, label %loop, label %leave
 152
 153   leave:
 154   ret void
 155 }
 156
 157 declare void @dummy(i32)
 158 declare void @dummy.i64(i64)
 159
 160
 161 define void @loop_2(i32 %size, i32 %nsteps, i32 %hsize, i32* %lined, i8 %tmp1) {
 162 ; CHECK-LABEL: @loop_2(
 163 ; CHECK-NEXT:  entry:
 164 ; CHECK-NEXT:    [[CMP215:%.*]] = icmp sgt i32 [[SIZE:%.*]], 1
 165 ; CHECK-NEXT:    [[BC0:%.*]] = bitcast i32* [[LINED:%.*]] to i8*
 166 ; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[SIZE]] to i64
 167 ; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[HSIZE:%.*]] to i64
 168 ; CHECK-NEXT:    [[TMP2:%.*]] = sext i32 [[NSTEPS:%.*]] to i64
 169 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 170 ; CHECK:       for.body:
 171 ; CHECK-NEXT:    [[INDVARS_IV7:%.*]] = phi i64 [ [[INDVARS_IV_NEXT8:%.*]], [[FOR_INC:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 172 ; CHECK-NEXT:    [[TMP3:%.*]] = mul nsw i64 [[INDVARS_IV7]], [[TMP0]]
 173 ; CHECK-NEXT:    [[TMP4:%.*]] = add nsw i64 [[TMP3]], [[TMP1]]
 174 ; CHECK-NEXT:    br i1 [[CMP215]], label [[FOR_BODY2_PREHEADER:%.*]], label [[FOR_INC]]
 175 ; CHECK:       for.body2.preheader:
 176 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[SIZE]] to i64
 177 ; CHECK-NEXT:    br label [[FOR_BODY2:%.*]]
 178 ; CHECK:       for.body2:
 179 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[FOR_BODY2_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY2]] ]
 180 ; CHECK-NEXT:    [[TMP5:%.*]] = add nsw i64 [[TMP4]], [[INDVARS_IV]]
 181 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[BC0]], i64 [[TMP5]]
 182 ; CHECK-NEXT:    store i8 [[TMP1:%.*]], i8* [[ADD_PTR]], align 1
 183 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
 184 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 185 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[FOR_BODY2]], label [[FOR_BODY3_PREHEADER:%.*]]
 186 ; CHECK:       for.body3.preheader:
 187 ; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[TMP4]] to i32
 188 ; CHECK-NEXT:    [[TMP7:%.*]] = zext i32 [[TMP6]] to i64
 189 ; CHECK-NEXT:    [[WIDE_TRIP_COUNT5:%.*]] = zext i32 [[SIZE]] to i64
 190 ; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
 191 ; CHECK:       for.body3:
 192 ; CHECK-NEXT:    [[INDVARS_IV2:%.*]] = phi i64 [ 1, [[FOR_BODY3_PREHEADER]] ], [ [[INDVARS_IV_NEXT3:%.*]], [[FOR_BODY3]] ]
 193 ; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw i64 [[TMP7]], [[INDVARS_IV2]]
 194 ; CHECK-NEXT:    [[ADD_PTR2:%.*]] = getelementptr inbounds i8, i8* [[BC0]], i64 [[TMP8]]
 195 ; CHECK-NEXT:    store i8 [[TMP1]], i8* [[ADD_PTR2]], align 1
 196 ; CHECK-NEXT:    [[INDVARS_IV_NEXT3]] = add nuw nsw i64 [[INDVARS_IV2]], 1
 197 ; CHECK-NEXT:    [[EXITCOND6:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT3]], [[WIDE_TRIP_COUNT5]]
 198 ; CHECK-NEXT:    br i1 [[EXITCOND6]], label [[FOR_BODY3]], label [[FOR_INC_LOOPEXIT:%.*]]
 199 ; CHECK:       for.inc.loopexit:
 200 ; CHECK-NEXT:    br label [[FOR_INC]]
 201 ; CHECK:       for.inc:
 202 ; CHECK-NEXT:    [[INDVARS_IV_NEXT8]] = add nuw nsw i64 [[INDVARS_IV7]], 1
 203 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i64 [[INDVARS_IV_NEXT8]], [[TMP2]]
 204 ; CHECK-NEXT:    br i1 [[CMP]], label [[FOR_BODY]], label [[FOR_END_LOOPEXIT:%.*]]
 205 ; CHECK:       for.end.loopexit:
 206 ; CHECK-NEXT:    ret void
 207 ;
 208 entry:
 209   %cmp215 = icmp sgt i32 %size, 1
 210   %bc0 = bitcast i32* %lined to i8*
 211   br label %for.body
 212
 213 for.body:
 214   %j = phi i32 [ 0, %entry ], [ %inc6, %for.inc ]
 215   %mul = mul nsw i32 %j, %size
 216   %add = add nsw i32 %mul, %hsize
 217   br i1 %cmp215, label %for.body2, label %for.inc
 218
 219 ; check that the induction variable of the inner loop has been widened after indvars.
 220 for.body2:
 221   %k = phi i32 [ %inc, %for.body2 ], [ 1, %for.body ]
 222   %add4 = add nsw i32 %add, %k
 223   %idx.ext = sext i32 %add4 to i64
 224   %add.ptr = getelementptr inbounds i8, i8* %bc0, i64 %idx.ext
 225   store i8 %tmp1, i8* %add.ptr, align 1
 226   %inc = add nsw i32 %k, 1
 227   %cmp2 = icmp slt i32 %inc, %size
 228   br i1 %cmp2, label %for.body2, label %for.body3
 229
 230 ; check that the induction variable of the inner loop has been widened after indvars.
 231 for.body3:
 232   %l = phi i32 [ %inc2, %for.body3 ], [ 1, %for.body2 ]
 233   %add5 = add nuw i32 %add, %l
 234   %idx.ext2 = zext i32 %add5 to i64
 235   %add.ptr2 = getelementptr inbounds i8, i8* %bc0, i64 %idx.ext2
 236   store i8 %tmp1, i8* %add.ptr2, align 1
 237   %inc2 = add nsw i32 %l, 1
 238   %cmp3 = icmp slt i32 %inc2, %size
 239   br i1 %cmp3, label %for.body3, label %for.inc
 240
 241 for.inc:
 242   %inc6 = add nsw i32 %j, 1
 243   %cmp = icmp slt i32 %inc6, %nsteps
 244   br i1 %cmp, label %for.body, label %for.end.loopexit
 245
 246 for.end.loopexit:
 247   ret void
 248 }