llvm/test/Transforms/LoopIdiom/X86/arithmetic-right-shift-until-zero.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -loop-idiom -mtriple=x86_64 -mcpu=core-avx2 < %s -S | FileCheck %s
   3
   4 declare void @escape_inner(i8, i8, i8, i1, i8)
   5 declare void @escape_outer(i8, i8, i8, i1, i8)
   6
   7 declare i8 @gen.i8()
   8
   9 ; Most basic pattern; Note that iff the shift amount is offset, said offsetting
  10 ; must not cause an overflow, but `add nsw` is fine.
  11 define i8 @p0(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
  12 ; CHECK-LABEL: @p0(
  13 ; CHECK-NEXT:  entry:
  14 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
  15 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
  16 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 0, [[EXTRAOFFSET:%.*]]
  17 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[TMP0]]
  18 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
  19 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
  20 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
  21 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  22 ; CHECK:       loop:
  23 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
  24 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
  25 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
  26 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
  27 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET]]
  28 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
  29 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
  30 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
  31 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
  32 ; CHECK:       end:
  33 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
  34 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
  35 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
  36 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
  37 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
  38 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
  39 ; CHECK-NEXT:    ret i8 [[IV_RES]]
  40 ;
  41 entry:
  42   br label %loop
  43
  44 loop:
  45   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
  46   %nbits = add nsw i8 %iv, %extraoffset
  47   %val.shifted = ashr i8 %val, %nbits
  48   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
  49   %iv.next = add i8 %iv, 1
  50
  51   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
  52
  53   br i1 %val.shifted.iszero, label %end, label %loop
  54
  55 end:
  56   %iv.res = phi i8 [ %iv, %loop ]
  57   %nbits.res = phi i8 [ %nbits, %loop ]
  58   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
  59   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
  60   %iv.next.res = phi i8 [ %iv.next, %loop ]
  61
  62   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
  63
  64   ret i8 %iv.res
  65 }
  66
  67 ; `add nuw` is also fine.
  68 define i8 @p1(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
  69 ; CHECK-LABEL: @p1(
  70 ; CHECK-NEXT:  entry:
  71 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
  72 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
  73 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 0, [[EXTRAOFFSET:%.*]]
  74 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[TMP0]]
  75 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
  76 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
  77 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
  78 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  79 ; CHECK:       loop:
  80 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
  81 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
  82 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
  83 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
  84 ; CHECK-NEXT:    [[NBITS:%.*]] = add nuw i8 [[IV]], [[EXTRAOFFSET]]
  85 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
  86 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
  87 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
  88 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
  89 ; CHECK:       end:
  90 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
  91 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
  92 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
  93 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
  94 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
  95 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
  96 ; CHECK-NEXT:    ret i8 [[IV_RES]]
  97 ;
  98 entry:
  99   br label %loop
 100
 101 loop:
 102   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 103   %nbits = add nuw i8 %iv, %extraoffset
 104   %val.shifted = ashr i8 %val, %nbits
 105   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 106   %iv.next = add i8 %iv, 1
 107
 108   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 109
 110   br i1 %val.shifted.iszero, label %end, label %loop
 111
 112 end:
 113   %iv.res = phi i8 [ %iv, %loop ]
 114   %nbits.res = phi i8 [ %nbits, %loop ]
 115   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 116   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 117   %iv.next.res = phi i8 [ %iv.next, %loop ]
 118
 119   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 120
 121   ret i8 %iv.res
 122 }
 123
 124 ; `sub nsw` is also fine.
 125 define i8 @p2(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 126 ; CHECK-LABEL: @p2(
 127 ; CHECK-NEXT:  entry:
 128 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
 129 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
 130 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[EXTRAOFFSET:%.*]]
 131 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
 132 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
 133 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
 134 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 135 ; CHECK:       loop:
 136 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
 137 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
 138 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
 139 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
 140 ; CHECK-NEXT:    [[NBITS:%.*]] = sub nsw i8 [[IV]], [[EXTRAOFFSET]]
 141 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
 142 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
 143 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
 144 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
 145 ; CHECK:       end:
 146 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
 147 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 148 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 149 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
 150 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 151 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 152 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 153 ;
 154 entry:
 155   br label %loop
 156
 157 loop:
 158   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 159   %nbits = sub nsw i8 %iv, %extraoffset
 160   %val.shifted = ashr i8 %val, %nbits
 161   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 162   %iv.next = add i8 %iv, 1
 163
 164   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 165
 166   br i1 %val.shifted.iszero, label %end, label %loop
 167
 168 end:
 169   %iv.res = phi i8 [ %iv, %loop ]
 170   %nbits.res = phi i8 [ %nbits, %loop ]
 171   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 172   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 173   %iv.next.res = phi i8 [ %iv.next, %loop ]
 174
 175   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 176
 177   ret i8 %iv.res
 178 }
 179
 180 ; But `sub nuw` is not fine..
 181 define i8 @n3(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 182 ; CHECK-LABEL: @n3(
 183 ; CHECK-NEXT:  entry:
 184 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 185 ; CHECK:       loop:
 186 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 187 ; CHECK-NEXT:    [[NBITS:%.*]] = sub nuw i8 [[IV]], [[EXTRAOFFSET:%.*]]
 188 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 189 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 190 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 191 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 192 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 193 ; CHECK:       end:
 194 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 195 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 196 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 197 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 198 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 199 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 200 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 201 ;
 202 entry:
 203   br label %loop
 204
 205 loop:
 206   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 207   %nbits = sub nuw i8 %iv, %extraoffset
 208   %val.shifted = ashr i8 %val, %nbits
 209   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 210   %iv.next = add i8 %iv, 1
 211
 212   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 213
 214   br i1 %val.shifted.iszero, label %end, label %loop
 215
 216 end:
 217   %iv.res = phi i8 [ %iv, %loop ]
 218   %nbits.res = phi i8 [ %nbits, %loop ]
 219   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 220   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 221   %iv.next.res = phi i8 [ %iv.next, %loop ]
 222
 223   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 224
 225   ret i8 %iv.res
 226 }
 227
 228 ; Likewise, plain `sub` is not fine.
 229 define i8 @n4(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 230 ; CHECK-LABEL: @n4(
 231 ; CHECK-NEXT:  entry:
 232 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 233 ; CHECK:       loop:
 234 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 235 ; CHECK-NEXT:    [[NBITS:%.*]] = sub i8 [[IV]], [[EXTRAOFFSET:%.*]]
 236 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 237 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 238 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 239 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 240 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 241 ; CHECK:       end:
 242 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 243 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 244 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 245 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 246 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 247 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 248 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 249 ;
 250 entry:
 251   br label %loop
 252
 253 loop:
 254   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 255   %nbits = sub i8 %iv, %extraoffset
 256   %val.shifted = ashr i8 %val, %nbits
 257   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 258   %iv.next = add i8 %iv, 1
 259
 260   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 261
 262   br i1 %val.shifted.iszero, label %end, label %loop
 263
 264 end:
 265   %iv.res = phi i8 [ %iv, %loop ]
 266   %nbits.res = phi i8 [ %nbits, %loop ]
 267   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 268   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 269   %iv.next.res = phi i8 [ %iv.next, %loop ]
 270
 271   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 272
 273   ret i8 %iv.res
 274 }
 275
 276 ; Likewise, plain `add` is not fine.
 277 define i8 @n5(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 278 ; CHECK-LABEL: @n5(
 279 ; CHECK-NEXT:  entry:
 280 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 281 ; CHECK:       loop:
 282 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 283 ; CHECK-NEXT:    [[NBITS:%.*]] = add i8 [[IV]], [[EXTRAOFFSET:%.*]]
 284 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 285 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 286 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 287 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 288 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 289 ; CHECK:       end:
 290 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 291 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 292 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 293 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 294 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 295 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 296 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 297 ;
 298 entry:
 299   br label %loop
 300
 301 loop:
 302   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 303   %nbits = add i8 %iv, %extraoffset
 304   %val.shifted = ashr i8 %val, %nbits
 305   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 306   %iv.next = add i8 %iv, 1
 307
 308   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 309
 310   br i1 %val.shifted.iszero, label %end, label %loop
 311
 312 end:
 313   %iv.res = phi i8 [ %iv, %loop ]
 314   %nbits.res = phi i8 [ %nbits, %loop ]
 315   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 316   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 317   %iv.next.res = phi i8 [ %iv.next, %loop ]
 318
 319   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 320
 321   ret i8 %iv.res
 322 }
 323
 324 ; Of course, we don't have to have an offset
 325 define i8 @p6(i8 %val, i8 %start) mustprogress {
 326 ; CHECK-LABEL: @p6(
 327 ; CHECK-NEXT:  entry:
 328 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
 329 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
 330 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nuw nsw i8 [[VAL_NUMACTIVEBITS]], 0
 331 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
 332 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nuw nsw i8 [[IV_FINAL]], [[START]]
 333 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
 334 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 335 ; CHECK:       loop:
 336 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
 337 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
 338 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
 339 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
 340 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[IV]]
 341 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
 342 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[IV]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
 343 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
 344 ; CHECK:       end:
 345 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
 346 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 347 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
 348 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 349 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[IV_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 350 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 351 ;
 352 entry:
 353   br label %loop
 354
 355 loop:
 356   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 357   %val.shifted = ashr i8 %val, %iv
 358   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 359   %iv.next = add i8 %iv, 1
 360
 361   call void @escape_inner(i8 %iv, i8 %iv, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 362
 363   br i1 %val.shifted.iszero, label %end, label %loop
 364
 365 end:
 366   %iv.res = phi i8 [ %iv, %loop ]
 367   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 368   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 369   %iv.next.res = phi i8 [ %iv.next, %loop ]
 370
 371   call void @escape_outer(i8 %iv.res, i8 %iv.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 372
 373   ret i8 %iv.res
 374 }
 375
 376 declare void @escape_inner.i7(i7, i7, i7, i1, i7)
 377 declare void @escape_outer.i7(i7, i7, i7, i1, i7)
 378
 379 ; Other bitwidths are fine also
 380 define i7 @p7(i7 %val, i7 %start, i7 %extraoffset) mustprogress {
 381 ; CHECK-LABEL: @p7(
 382 ; CHECK-NEXT:  entry:
 383 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i7 @llvm.ctlz.i7(i7 [[VAL:%.*]], i1 false)
 384 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i7 7, [[VAL_NUMLEADINGZEROS]]
 385 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i7 0, [[EXTRAOFFSET:%.*]]
 386 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i7 [[VAL_NUMACTIVEBITS]], [[TMP0]]
 387 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i7 @llvm.smax.i7(i7 [[VAL_NUMACTIVEBITS_OFFSET]], i7 [[START:%.*]])
 388 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i7 [[IV_FINAL]], [[START]]
 389 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i7 [[LOOP_BACKEDGETAKENCOUNT]], 1
 390 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 391 ; CHECK:       loop:
 392 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i7 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
 393 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i7 [[LOOP_IV]], 1
 394 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i7 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
 395 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i7 [[LOOP_IV]], [[START]]
 396 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i7 [[IV]], [[EXTRAOFFSET]]
 397 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i7 [[VAL]], [[NBITS]]
 398 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i7 [[IV]], 1
 399 ; CHECK-NEXT:    call void @escape_inner.i7(i7 [[IV]], i7 [[NBITS]], i7 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i7 [[IV_NEXT]])
 400 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
 401 ; CHECK:       end:
 402 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i7 [ [[IV_FINAL]], [[LOOP]] ]
 403 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i7 [ [[NBITS]], [[LOOP]] ]
 404 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i7 [ [[VAL_SHIFTED]], [[LOOP]] ]
 405 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
 406 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i7 [ [[IV_NEXT]], [[LOOP]] ]
 407 ; CHECK-NEXT:    call void @escape_outer.i7(i7 [[IV_RES]], i7 [[NBITS_RES]], i7 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i7 [[IV_NEXT_RES]])
 408 ; CHECK-NEXT:    ret i7 [[IV_RES]]
 409 ;
 410 entry:
 411   br label %loop
 412
 413 loop:
 414   %iv = phi i7 [ %start, %entry ], [ %iv.next, %loop ]
 415   %nbits = add nsw i7 %iv, %extraoffset
 416   %val.shifted = ashr i7 %val, %nbits
 417   %val.shifted.iszero = icmp eq i7 %val.shifted, 0
 418   %iv.next = add i7 %iv, 1
 419
 420   call void @escape_inner.i7(i7 %iv, i7 %nbits, i7 %val.shifted, i1 %val.shifted.iszero, i7 %iv.next)
 421
 422   br i1 %val.shifted.iszero, label %end, label %loop
 423
 424 end:
 425   %iv.res = phi i7 [ %iv, %loop ]
 426   %nbits.res = phi i7 [ %nbits, %loop ]
 427   %val.shifted.res = phi i7 [ %val.shifted, %loop ]
 428   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 429   %iv.next.res = phi i7 [ %iv.next, %loop ]
 430
 431   call void @escape_outer.i7(i7 %iv.res, i7 %nbits.res, i7 %val.shifted.res, i1 %val.shifted.iszero.res, i7 %iv.next.res)
 432
 433   ret i7 %iv.res
 434 }
 435
 436 ; Step must be 1
 437 define i8 @n8(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 438 ; CHECK-LABEL: @n8(
 439 ; CHECK-NEXT:  entry:
 440 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 441 ; CHECK:       loop:
 442 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 443 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
 444 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 445 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 446 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 2
 447 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 448 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 449 ; CHECK:       end:
 450 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 451 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 452 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 453 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 454 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 455 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 456 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 457 ;
 458 entry:
 459   br label %loop
 460
 461 loop:
 462   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 463   %nbits = add nsw i8 %iv, %extraoffset
 464   %val.shifted = ashr i8 %val, %nbits
 465   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 466   %iv.next = add i8 %iv, 2 ; not 1
 467
 468   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 469
 470   br i1 %val.shifted.iszero, label %end, label %loop
 471
 472 end:
 473   %iv.res = phi i8 [ %iv, %loop ]
 474   %nbits.res = phi i8 [ %nbits, %loop ]
 475   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 476   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 477   %iv.next.res = phi i8 [ %iv.next, %loop ]
 478
 479   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 480
 481   ret i8 %iv.res
 482 }
 483
 484 ; Cmp-br are commutable
 485 define i8 @t9(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 486 ; CHECK-LABEL: @t9(
 487 ; CHECK-NEXT:  entry:
 488 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
 489 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
 490 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 0, [[EXTRAOFFSET:%.*]]
 491 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[TMP0]]
 492 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
 493 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
 494 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
 495 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 496 ; CHECK:       loop:
 497 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
 498 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
 499 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
 500 ; CHECK-NEXT:    [[VAL_SHIFTED_ISNOTZERO:%.*]] = xor i1 [[LOOP_IVCHECK]], true
 501 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
 502 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET]]
 503 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
 504 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
 505 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISNOTZERO]], i8 [[IV_NEXT]])
 506 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
 507 ; CHECK:       end:
 508 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
 509 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 510 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 511 ; CHECK-NEXT:    [[VAL_SHIFTED_ISNOTZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISNOTZERO]], [[LOOP]] ]
 512 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 513 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISNOTZERO_RES]], i8 [[IV_NEXT_RES]])
 514 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 515 ;
 516 entry:
 517   br label %loop
 518
 519 loop:
 520   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 521   %nbits = add nsw i8 %iv, %extraoffset
 522   %val.shifted = ashr i8 %val, %nbits
 523   %val.shifted.isnotzero = icmp ne i8 %val.shifted, 0
 524   %iv.next = add i8 %iv, 1
 525
 526   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.isnotzero, i8 %iv.next)
 527
 528   br i1 %val.shifted.isnotzero, label %loop, label %end
 529
 530 end:
 531   %iv.res = phi i8 [ %iv, %loop ]
 532   %nbits.res = phi i8 [ %nbits, %loop ]
 533   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 534   %val.shifted.isnotzero.res = phi i1 [ %val.shifted.isnotzero, %loop ]
 535   %iv.next.res = phi i8 [ %iv.next, %loop ]
 536
 537   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.isnotzero.res, i8 %iv.next.res)
 538
 539   ret i8 %iv.res
 540 }
 541
 542 ; We want to exit once it becomes zero
 543 define i8 @n10(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 544 ; CHECK-LABEL: @n10(
 545 ; CHECK-NEXT:  entry:
 546 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 547 ; CHECK:       loop:
 548 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 549 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
 550 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 551 ; CHECK-NEXT:    [[VAL_SHIFTED_ISNOTZERO:%.*]] = icmp ne i8 [[VAL_SHIFTED]], 0
 552 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 553 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISNOTZERO]], i8 [[IV_NEXT]])
 554 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISNOTZERO]], label [[END:%.*]], label [[LOOP]]
 555 ; CHECK:       end:
 556 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 557 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 558 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 559 ; CHECK-NEXT:    [[VAL_SHIFTED_ISNOTZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISNOTZERO]], [[LOOP]] ]
 560 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 561 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISNOTZERO_RES]], i8 [[IV_NEXT_RES]])
 562 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 563 ;
 564 entry:
 565   br label %loop
 566
 567 loop:
 568   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 569   %nbits = add nsw i8 %iv, %extraoffset
 570   %val.shifted = ashr i8 %val, %nbits
 571   %val.shifted.isnotzero = icmp ne i8 %val.shifted, 0 ; not eq
 572   %iv.next = add i8 %iv, 1
 573
 574   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.isnotzero, i8 %iv.next)
 575
 576   br i1 %val.shifted.isnotzero, label %end, label %loop
 577
 578 end:
 579   %iv.res = phi i8 [ %iv, %loop ]
 580   %nbits.res = phi i8 [ %nbits, %loop ]
 581   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 582   %val.shifted.isnotzero.res = phi i1 [ %val.shifted.isnotzero, %loop ]
 583   %iv.next.res = phi i8 [ %iv.next, %loop ]
 584
 585   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.isnotzero.res, i8 %iv.next.res)
 586
 587   ret i8 %iv.res
 588 }
 589
 590 ; Once it compares zero, we want to exit, not exit when it compares non-zero
 591 define i8 @n11(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 592 ; CHECK-LABEL: @n11(
 593 ; CHECK-NEXT:  entry:
 594 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 595 ; CHECK:       loop:
 596 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 597 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
 598 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 599 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 600 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 601 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 602 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[LOOP]], label [[END:%.*]]
 603 ; CHECK:       end:
 604 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 605 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 606 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 607 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 608 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 609 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 610 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 611 ;
 612 entry:
 613   br label %loop
 614
 615 loop:
 616   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 617   %nbits = add nsw i8 %iv, %extraoffset
 618   %val.shifted = ashr i8 %val, %nbits
 619   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 620   %iv.next = add i8 %iv, 1
 621
 622   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 623
 624   br i1 %val.shifted.iszero, label %loop, label %end ; wrong destinations
 625
 626 end:
 627   %iv.res = phi i8 [ %iv, %loop ]
 628   %nbits.res = phi i8 [ %nbits, %loop ]
 629   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 630   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 631   %iv.next.res = phi i8 [ %iv.next, %loop ]
 632
 633   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 634
 635   ret i8 %iv.res
 636 }
 637
 638 ; We must be comparing with 0
 639 define i8 @n12(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 640 ; CHECK-LABEL: @n12(
 641 ; CHECK-NEXT:  entry:
 642 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 643 ; CHECK:       loop:
 644 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 645 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
 646 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 647 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 1
 648 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 649 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 650 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 651 ; CHECK:       end:
 652 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 653 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 654 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 655 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 656 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 657 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 658 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 659 ;
 660 entry:
 661   br label %loop
 662
 663 loop:
 664   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 665   %nbits = add nsw i8 %iv, %extraoffset
 666   %val.shifted = ashr i8 %val, %nbits
 667   %val.shifted.iszero = icmp eq i8 %val.shifted, 1 ; not 0
 668   %iv.next = add i8 %iv, 1
 669
 670   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 671
 672   br i1 %val.shifted.iszero, label %end, label %loop
 673
 674 end:
 675   %iv.res = phi i8 [ %iv, %loop ]
 676   %nbits.res = phi i8 [ %nbits, %loop ]
 677   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 678   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 679   %iv.next.res = phi i8 [ %iv.next, %loop ]
 680
 681   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 682
 683   ret i8 %iv.res
 684 }
 685
 686 ; Loop must have a single block.
 687 define i8 @n13(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 688 ; CHECK-LABEL: @n13(
 689 ; CHECK-NEXT:  entry:
 690 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 691 ; CHECK:       loop:
 692 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_END:%.*]] ]
 693 ; CHECK-NEXT:    br label [[LOOP_END]]
 694 ; CHECK:       loop.end:
 695 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
 696 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 697 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 698 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 699 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 700 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 701 ; CHECK:       end:
 702 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP_END]] ]
 703 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP_END]] ]
 704 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP_END]] ]
 705 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP_END]] ]
 706 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP_END]] ]
 707 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 708 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 709 ;
 710 entry:
 711   br label %loop
 712
 713 loop:
 714   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop.end ]
 715   br label %loop.end
 716
 717 loop.end:
 718   %nbits = add nsw i8 %iv, %extraoffset
 719   %val.shifted = ashr i8 %val, %nbits
 720   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 721   %iv.next = add i8 %iv, 1
 722
 723   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 724
 725   br i1 %val.shifted.iszero, label %end, label %loop
 726
 727 end:
 728   %iv.res = phi i8 [ %iv, %loop.end ]
 729   %nbits.res = phi i8 [ %nbits, %loop.end ]
 730   %val.shifted.res = phi i8 [ %val.shifted, %loop.end ]
 731   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop.end ]
 732   %iv.next.res = phi i8 [ %iv.next, %loop.end ]
 733
 734   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 735
 736   ret i8 %iv.res
 737 }
 738
 739 ; The comparison must have an equality predicate
 740 define i8 @n14(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 741 ; CHECK-LABEL: @n14(
 742 ; CHECK-NEXT:  entry:
 743 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 744 ; CHECK:       loop:
 745 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 746 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
 747 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 748 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp ult i8 [[VAL_SHIFTED]], 1
 749 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 750 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 751 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 752 ; CHECK:       end:
 753 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 754 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 755 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 756 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 757 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 758 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 759 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 760 ;
 761 entry:
 762   br label %loop
 763
 764 loop:
 765   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 766   %nbits = add nsw i8 %iv, %extraoffset
 767   %val.shifted = ashr i8 %val, %nbits
 768   %val.shifted.iszero = icmp ult i8 %val.shifted, 1 ; not `==0`
 769   %iv.next = add i8 %iv, 1
 770
 771   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 772
 773   br i1 %val.shifted.iszero, label %end, label %loop
 774
 775 end:
 776   %iv.res = phi i8 [ %iv, %loop ]
 777   %nbits.res = phi i8 [ %nbits, %loop ]
 778   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 779   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 780   %iv.next.res = phi i8 [ %iv.next, %loop ]
 781
 782   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 783
 784   ret i8 %iv.res
 785 }
 786
 787 ; offset computation can be commuted
 788 define i8 @t15(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 789 ; CHECK-LABEL: @t15(
 790 ; CHECK-NEXT:  entry:
 791 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
 792 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
 793 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 0, [[EXTRAOFFSET:%.*]]
 794 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[TMP0]]
 795 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
 796 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
 797 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
 798 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 799 ; CHECK:       loop:
 800 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
 801 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
 802 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
 803 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
 804 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[EXTRAOFFSET]], [[IV]]
 805 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
 806 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
 807 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
 808 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
 809 ; CHECK:       end:
 810 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
 811 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 812 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 813 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
 814 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 815 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 816 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 817 ;
 818 entry:
 819   br label %loop
 820
 821 loop:
 822   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 823   %nbits = add nsw i8 %extraoffset, %iv ; swapped order
 824   %val.shifted = ashr i8 %val, %nbits
 825   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 826   %iv.next = add i8 %iv, 1
 827
 828   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 829
 830   br i1 %val.shifted.iszero, label %end, label %loop
 831
 832 end:
 833   %iv.res = phi i8 [ %iv, %loop ]
 834   %nbits.res = phi i8 [ %nbits, %loop ]
 835   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 836   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 837   %iv.next.res = phi i8 [ %iv.next, %loop ]
 838
 839   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 840
 841   ret i8 %iv.res
 842 }
 843
 844 ; But for `sub nsw`, it is not commutable.
 845 define i8 @n16(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 846 ; CHECK-LABEL: @n16(
 847 ; CHECK-NEXT:  entry:
 848 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 849 ; CHECK:       loop:
 850 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 851 ; CHECK-NEXT:    [[NBITS:%.*]] = sub nsw i8 [[EXTRAOFFSET:%.*]], [[IV]]
 852 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 853 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 854 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 855 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 856 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 857 ; CHECK:       end:
 858 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 859 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 860 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 861 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 862 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 863 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 864 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 865 ;
 866 entry:
 867   br label %loop
 868
 869 loop:
 870   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 871   %nbits = sub nsw i8 %extraoffset, %iv
 872   %val.shifted = ashr i8 %val, %nbits
 873   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 874   %iv.next = add i8 %iv, 1
 875
 876   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 877
 878   br i1 %val.shifted.iszero, label %end, label %loop
 879
 880 end:
 881   %iv.res = phi i8 [ %iv, %loop ]
 882   %nbits.res = phi i8 [ %nbits, %loop ]
 883   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 884   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 885   %iv.next.res = phi i8 [ %iv.next, %loop ]
 886
 887   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 888
 889   ret i8 %iv.res
 890 }
 891
 892 ; The offset must be loop-invariant
 893 define i8 @n17(i8 %val, i8 %start) mustprogress {
 894 ; CHECK-LABEL: @n17(
 895 ; CHECK-NEXT:  entry:
 896 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 897 ; CHECK:       loop:
 898 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 899 ; CHECK-NEXT:    [[EXTRAOFFSET:%.*]] = call i8 @gen.i8()
 900 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET]]
 901 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 902 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 903 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 904 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 905 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 906 ; CHECK:       end:
 907 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 908 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 909 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 910 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 911 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 912 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 913 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 914 ;
 915 entry:
 916   br label %loop
 917
 918 loop:
 919   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 920   %extraoffset = call i8 @gen.i8()
 921   %nbits = add nsw i8 %iv, %extraoffset
 922   %val.shifted = ashr i8 %val, %nbits
 923   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 924   %iv.next = add i8 %iv, 1
 925
 926   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 927
 928   br i1 %val.shifted.iszero, label %end, label %loop
 929
 930 end:
 931   %iv.res = phi i8 [ %iv, %loop ]
 932   %nbits.res = phi i8 [ %nbits, %loop ]
 933   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 934   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 935   %iv.next.res = phi i8 [ %iv.next, %loop ]
 936
 937   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 938
 939   ret i8 %iv.res
 940 }
 941
 942 ; Likewise for `sub nsw`.
 943 define i8 @n18(i8 %val, i8 %start) mustprogress {
 944 ; CHECK-LABEL: @n18(
 945 ; CHECK-NEXT:  entry:
 946 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 947 ; CHECK:       loop:
 948 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 949 ; CHECK-NEXT:    [[EXTRAOFFSET:%.*]] = call i8 @gen.i8()
 950 ; CHECK-NEXT:    [[NBITS:%.*]] = sub nsw i8 [[IV]], [[EXTRAOFFSET]]
 951 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
 952 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
 953 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
 954 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
 955 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
 956 ; CHECK:       end:
 957 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
 958 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
 959 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
 960 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
 961 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
 962 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
 963 ; CHECK-NEXT:    ret i8 [[IV_RES]]
 964 ;
 965 entry:
 966   br label %loop
 967
 968 loop:
 969   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
 970   %extraoffset = call i8 @gen.i8()
 971   %nbits = sub nsw i8 %iv, %extraoffset
 972   %val.shifted = ashr i8 %val, %nbits
 973   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
 974   %iv.next = add i8 %iv, 1
 975
 976   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
 977
 978   br i1 %val.shifted.iszero, label %end, label %loop
 979
 980 end:
 981   %iv.res = phi i8 [ %iv, %loop ]
 982   %nbits.res = phi i8 [ %nbits, %loop ]
 983   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
 984   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
 985   %iv.next.res = phi i8 [ %iv.next, %loop ]
 986
 987   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
 988
 989   ret i8 %iv.res
 990 }
 991
 992 ; The "induction variable" must be in the loop header.
 993 define i8 @n19(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
 994 ; CHECK-LABEL: @n19(
 995 ; CHECK-NEXT:  entry:
 996 ; CHECK-NEXT:    br label [[LOOP_PREHEADER:%.*]]
 997 ; CHECK:       loop.preheader:
 998 ; CHECK-NEXT:    [[NOTIV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ]
 999 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1000 ; CHECK:       loop:
1001 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[LOOP_PREHEADER]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1002 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[NOTIV]], [[EXTRAOFFSET:%.*]]
1003 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
1004 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
1005 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
1006 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
1007 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
1008 ; CHECK:       end:
1009 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
1010 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
1011 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
1012 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
1013 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
1014 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
1015 ; CHECK-NEXT:    ret i8 [[IV_RES]]
1016 ;
1017 entry:
1018   br label %loop.preheader
1019
1020 loop.preheader:
1021   %notiv = phi i8 [ 0, %entry ]
1022   br label %loop
1023
1024 loop:
1025   %iv = phi i8 [ %start, %loop.preheader ], [ %iv.next, %loop ]
1026   %nbits = add nsw i8 %notiv, %extraoffset ; uses %notiv instead of %iv
1027   %val.shifted = ashr i8 %val, %nbits
1028   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
1029   %iv.next = add i8 %iv, 1
1030
1031   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
1032
1033   br i1 %val.shifted.iszero, label %end, label %loop
1034
1035 end:
1036   %iv.res = phi i8 [ %iv, %loop ]
1037   %nbits.res = phi i8 [ %nbits, %loop ]
1038   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
1039   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1040   %iv.next.res = phi i8 [ %iv.next, %loop ]
1041
1042   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
1043
1044   ret i8 %iv.res
1045 }
1046
1047 ; IV must really be a PHI
1048 define i8 @n20(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
1049 ; CHECK-LABEL: @n20(
1050 ; CHECK-NEXT:  entry:
1051 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1052 ; CHECK:       loop:
1053 ; CHECK-NEXT:    [[IV:%.*]] = add i8 0, 0
1054 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
1055 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
1056 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
1057 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
1058 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
1059 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
1060 ; CHECK:       end:
1061 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
1062 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
1063 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
1064 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
1065 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
1066 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
1067 ; CHECK-NEXT:    ret i8 [[IV_RES]]
1068 ;
1069 entry:
1070   br label %loop
1071
1072 loop:
1073   %iv = add i8 0, 0 ; again not IV
1074   %nbits = add nsw i8 %iv, %extraoffset
1075   %val.shifted = ashr i8 %val, %nbits
1076   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
1077   %iv.next = add i8 %iv, 1
1078
1079   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
1080
1081   br i1 %val.shifted.iszero, label %end, label %loop
1082
1083 end:
1084   %iv.res = phi i8 [ %iv, %loop ]
1085   %nbits.res = phi i8 [ %nbits, %loop ]
1086   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
1087   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1088   %iv.next.res = phi i8 [ %iv.next, %loop ]
1089
1090   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
1091
1092   ret i8 %iv.res
1093 }
1094
1095 ; The induction should be actually increasing IV
1096 define i8 @n21(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
1097 ; CHECK-LABEL: @n21(
1098 ; CHECK-NEXT:  entry:
1099 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1100 ; CHECK:       loop:
1101 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1102 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
1103 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
1104 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
1105 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 0, 1
1106 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
1107 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
1108 ; CHECK:       end:
1109 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
1110 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
1111 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
1112 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
1113 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
1114 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
1115 ; CHECK-NEXT:    ret i8 [[IV_RES]]
1116 ;
1117 entry:
1118   br label %loop
1119
1120 loop:
1121   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
1122   %nbits = add nsw i8 %iv, %extraoffset
1123   %val.shifted = ashr i8 %val, %nbits
1124   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
1125   %iv.next = add i8 0, 1 ; should be adding to IV
1126
1127   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
1128
1129   br i1 %val.shifted.iszero, label %end, label %loop
1130
1131 end:
1132   %iv.res = phi i8 [ %iv, %loop ]
1133   %nbits.res = phi i8 [ %nbits, %loop ]
1134   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
1135   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1136   %iv.next.res = phi i8 [ %iv.next, %loop ]
1137
1138   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
1139
1140   ret i8 %iv.res
1141 }
1142
1143 ; We should not just blindly look for add, we should look what IV actually uses.
1144 define i8 @n22(i8 %val, i8 %start, i8 %extraoffset) mustprogress {
1145 ; CHECK-LABEL: @n22(
1146 ; CHECK-NEXT:  entry:
1147 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
1148 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
1149 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 0, [[EXTRAOFFSET:%.*]]
1150 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[TMP0]]
1151 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
1152 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
1153 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
1154 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1155 ; CHECK:       loop:
1156 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1157 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
1158 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1159 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
1160 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET]]
1161 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
1162 ; CHECK-NEXT:    [[NOT_IV_NEXT:%.*]] = add i8 [[IV]], 1
1163 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
1164 ; CHECK-NEXT:    [[ALSO_IV_NEXT:%.*]] = add i8 [[IV]], 1
1165 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
1166 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1167 ; CHECK:       end:
1168 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
1169 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
1170 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
1171 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1172 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
1173 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
1174 ; CHECK-NEXT:    ret i8 [[IV_RES]]
1175 ;
1176 entry:
1177   br label %loop
1178
1179 loop:
1180   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
1181   %nbits = add nsw i8 %iv, %extraoffset
1182   %val.shifted = ashr i8 %val, %nbits
1183   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
1184   %not.iv.next = add i8 %iv, 1 ; not used by %iv
1185   %iv.next = add i8 %iv, 1
1186   %also.iv.next = add i8 %iv, 1 ; not used by %iv
1187
1188   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
1189
1190   br i1 %val.shifted.iszero, label %end, label %loop
1191
1192 end:
1193   %iv.res = phi i8 [ %iv, %loop ]
1194   %nbits.res = phi i8 [ %nbits, %loop ]
1195   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
1196   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1197   %iv.next.res = phi i8 [ %iv.next, %loop ]
1198
1199   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
1200
1201   ret i8 %iv.res
1202 }
1203
1204 define i8 @n23(i8 %start, i8 %extraoffset) mustprogress {
1205 ; CHECK-LABEL: @n23(
1206 ; CHECK-NEXT:  entry:
1207 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1208 ; CHECK:       loop:
1209 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1210 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
1211 ; CHECK-NEXT:    [[VAL:%.*]] = call i8 @gen.i8()
1212 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
1213 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
1214 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
1215 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
1216 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
1217 ; CHECK:       end:
1218 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
1219 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
1220 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
1221 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
1222 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
1223 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
1224 ; CHECK-NEXT:    ret i8 [[IV_RES]]
1225 ;
1226 entry:
1227   br label %loop
1228
1229 loop:
1230   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
1231   %nbits = add nsw i8 %iv, %extraoffset
1232   %val = call i8 @gen.i8()
1233   %val.shifted = ashr i8 %val, %nbits
1234   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
1235   %iv.next = add i8 %iv, 1
1236
1237   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
1238
1239   br i1 %val.shifted.iszero, label %end, label %loop
1240
1241 end:
1242   %iv.res = phi i8 [ %iv, %loop ]
1243   %nbits.res = phi i8 [ %nbits, %loop ]
1244   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
1245   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1246   %iv.next.res = phi i8 [ %iv.next, %loop ]
1247
1248   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
1249
1250   ret i8 %iv.res
1251 }
1252
1253 ; Tests with some small bit widths
1254 declare void @escape_inner.i1(i1, i1, i1, i1, i1)
1255 declare void @escape_outer.i1(i1, i1, i1, i1, i1)
1256 declare void @escape_inner.i2(i2, i2, i2, i1, i2)
1257 declare void @escape_outer.i2(i2, i2, i2, i1, i2)
1258 declare void @escape_inner.i3(i3, i3, i3, i1, i3)
1259 declare void @escape_outer.i3(i3, i3, i3, i1, i3)
1260
1261 define i1 @t24_nooffset_i1(i1 %val, i1 %start) mustprogress {
1262 ; CHECK-LABEL: @t24_nooffset_i1(
1263 ; CHECK-NEXT:  entry:
1264 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i1 @llvm.ctlz.i1(i1 [[VAL:%.*]], i1 false)
1265 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i1 true, [[VAL_NUMLEADINGZEROS]]
1266 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nuw nsw i1 [[VAL_NUMACTIVEBITS]], false
1267 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i1 @llvm.smax.i1(i1 [[VAL_NUMACTIVEBITS_OFFSET]], i1 [[START:%.*]])
1268 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nuw nsw i1 [[IV_FINAL]], [[START]]
1269 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i1 [[LOOP_BACKEDGETAKENCOUNT]], true
1270 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1271 ; CHECK:       loop:
1272 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1273 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i1 [[LOOP_IV]], true
1274 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i1 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1275 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i1 [[LOOP_IV]], [[START]]
1276 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i1 [[VAL]], [[IV]]
1277 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i1 [[IV]], true
1278 ; CHECK-NEXT:    call void @escape_inner.i1(i1 [[IV]], i1 [[IV]], i1 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i1 [[IV_NEXT]])
1279 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1280 ; CHECK:       end:
1281 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i1 [ [[IV_FINAL]], [[LOOP]] ]
1282 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i1 [ [[VAL_SHIFTED]], [[LOOP]] ]
1283 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1284 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i1 [ [[IV_NEXT]], [[LOOP]] ]
1285 ; CHECK-NEXT:    call void @escape_outer.i1(i1 [[IV_RES]], i1 [[IV_RES]], i1 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i1 [[IV_NEXT_RES]])
1286 ; CHECK-NEXT:    ret i1 [[IV_RES]]
1287 ;
1288 entry:
1289   br label %loop
1290
1291 loop:
1292   %iv = phi i1 [ %start, %entry ], [ %iv.next, %loop ]
1293   %val.shifted = ashr i1 %val, %iv
1294   %val.shifted.iszero = icmp eq i1 %val.shifted, 0
1295   %iv.next = add i1 %iv, 1
1296
1297   call void @escape_inner.i1(i1 %iv, i1 %iv, i1 %val.shifted, i1 %val.shifted.iszero, i1 %iv.next)
1298
1299   br i1 %val.shifted.iszero, label %end, label %loop
1300
1301 end:
1302   %iv.res = phi i1 [ %iv, %loop ]
1303   %val.shifted.res = phi i1 [ %val.shifted, %loop ]
1304   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1305   %iv.next.res = phi i1 [ %iv.next, %loop ]
1306
1307   call void @escape_outer.i1(i1 %iv.res, i1 %iv.res, i1 %val.shifted.res, i1 %val.shifted.iszero.res, i1 %iv.next.res)
1308
1309   ret i1 %iv.res
1310 }
1311 define i2 @t25_nooffset_i2(i2 %val, i2 %start) mustprogress {
1312 ; CHECK-LABEL: @t25_nooffset_i2(
1313 ; CHECK-NEXT:  entry:
1314 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i2 @llvm.ctlz.i2(i2 [[VAL:%.*]], i1 false)
1315 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw i2 -2, [[VAL_NUMLEADINGZEROS]]
1316 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nuw nsw i2 [[VAL_NUMACTIVEBITS]], 0
1317 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i2 @llvm.smax.i2(i2 [[VAL_NUMACTIVEBITS_OFFSET]], i2 [[START:%.*]])
1318 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nuw nsw i2 [[IV_FINAL]], [[START]]
1319 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i2 [[LOOP_BACKEDGETAKENCOUNT]], 1
1320 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1321 ; CHECK:       loop:
1322 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i2 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1323 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw i2 [[LOOP_IV]], 1
1324 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i2 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1325 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i2 [[LOOP_IV]], [[START]]
1326 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i2 [[VAL]], [[IV]]
1327 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i2 [[IV]], 1
1328 ; CHECK-NEXT:    call void @escape_inner.i2(i2 [[IV]], i2 [[IV]], i2 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i2 [[IV_NEXT]])
1329 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1330 ; CHECK:       end:
1331 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i2 [ [[IV_FINAL]], [[LOOP]] ]
1332 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i2 [ [[VAL_SHIFTED]], [[LOOP]] ]
1333 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1334 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i2 [ [[IV_NEXT]], [[LOOP]] ]
1335 ; CHECK-NEXT:    call void @escape_outer.i2(i2 [[IV_RES]], i2 [[IV_RES]], i2 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i2 [[IV_NEXT_RES]])
1336 ; CHECK-NEXT:    ret i2 [[IV_RES]]
1337 ;
1338 entry:
1339   br label %loop
1340
1341 loop:
1342   %iv = phi i2 [ %start, %entry ], [ %iv.next, %loop ]
1343   %val.shifted = ashr i2 %val, %iv
1344   %val.shifted.iszero = icmp eq i2 %val.shifted, 0
1345   %iv.next = add i2 %iv, 1
1346
1347   call void @escape_inner.i2(i2 %iv, i2 %iv, i2 %val.shifted, i1 %val.shifted.iszero, i2 %iv.next)
1348
1349   br i1 %val.shifted.iszero, label %end, label %loop
1350
1351 end:
1352   %iv.res = phi i2 [ %iv, %loop ]
1353   %val.shifted.res = phi i2 [ %val.shifted, %loop ]
1354   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1355   %iv.next.res = phi i2 [ %iv.next, %loop ]
1356
1357   call void @escape_outer.i2(i2 %iv.res, i2 %iv.res, i2 %val.shifted.res, i1 %val.shifted.iszero.res, i2 %iv.next.res)
1358
1359   ret i2 %iv.res
1360 }
1361 define i3 @t26_nooffset_i3(i3 %val, i3 %start) mustprogress {
1362 ; CHECK-LABEL: @t26_nooffset_i3(
1363 ; CHECK-NEXT:  entry:
1364 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i3 @llvm.ctlz.i3(i3 [[VAL:%.*]], i1 false)
1365 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i3 3, [[VAL_NUMLEADINGZEROS]]
1366 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nuw nsw i3 [[VAL_NUMACTIVEBITS]], 0
1367 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i3 @llvm.smax.i3(i3 [[VAL_NUMACTIVEBITS_OFFSET]], i3 [[START:%.*]])
1368 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nuw nsw i3 [[IV_FINAL]], [[START]]
1369 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i3 [[LOOP_BACKEDGETAKENCOUNT]], 1
1370 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1371 ; CHECK:       loop:
1372 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i3 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1373 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i3 [[LOOP_IV]], 1
1374 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i3 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1375 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i3 [[LOOP_IV]], [[START]]
1376 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i3 [[VAL]], [[IV]]
1377 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i3 [[IV]], 1
1378 ; CHECK-NEXT:    call void @escape_inner.i3(i3 [[IV]], i3 [[IV]], i3 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i3 [[IV_NEXT]])
1379 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1380 ; CHECK:       end:
1381 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i3 [ [[IV_FINAL]], [[LOOP]] ]
1382 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i3 [ [[VAL_SHIFTED]], [[LOOP]] ]
1383 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1384 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i3 [ [[IV_NEXT]], [[LOOP]] ]
1385 ; CHECK-NEXT:    call void @escape_outer.i3(i3 [[IV_RES]], i3 [[IV_RES]], i3 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i3 [[IV_NEXT_RES]])
1386 ; CHECK-NEXT:    ret i3 [[IV_RES]]
1387 ;
1388 entry:
1389   br label %loop
1390
1391 loop:
1392   %iv = phi i3 [ %start, %entry ], [ %iv.next, %loop ]
1393   %val.shifted = ashr i3 %val, %iv
1394   %val.shifted.iszero = icmp eq i3 %val.shifted, 0
1395   %iv.next = add i3 %iv, 1
1396
1397   call void @escape_inner.i3(i3 %iv, i3 %iv, i3 %val.shifted, i1 %val.shifted.iszero, i3 %iv.next)
1398
1399   br i1 %val.shifted.iszero, label %end, label %loop
1400
1401 end:
1402   %iv.res = phi i3 [ %iv, %loop ]
1403   %val.shifted.res = phi i3 [ %val.shifted, %loop ]
1404   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1405   %iv.next.res = phi i3 [ %iv.next, %loop ]
1406
1407   call void @escape_outer.i3(i3 %iv.res, i3 %iv.res, i3 %val.shifted.res, i1 %val.shifted.iszero.res, i3 %iv.next.res)
1408
1409   ret i3 %iv.res
1410 }
1411
1412 define i1 @t27_addnsw_i1(i1 %val, i1 %start, i1 %extraoffset) mustprogress {
1413 ; CHECK-LABEL: @t27_addnsw_i1(
1414 ; CHECK-NEXT:  entry:
1415 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i1 @llvm.ctlz.i1(i1 [[VAL:%.*]], i1 false)
1416 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i1 true, [[VAL_NUMLEADINGZEROS]]
1417 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i1 [[VAL_NUMACTIVEBITS]], [[EXTRAOFFSET:%.*]]
1418 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i1 @llvm.smax.i1(i1 [[VAL_NUMACTIVEBITS_OFFSET]], i1 [[START:%.*]])
1419 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i1 [[IV_FINAL]], [[START]]
1420 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i1 [[LOOP_BACKEDGETAKENCOUNT]], true
1421 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1422 ; CHECK:       loop:
1423 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1424 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i1 [[LOOP_IV]], true
1425 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i1 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1426 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i1 [[LOOP_IV]], [[START]]
1427 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i1 [[IV]], [[EXTRAOFFSET]]
1428 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i1 [[VAL]], [[NBITS]]
1429 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i1 [[IV]], true
1430 ; CHECK-NEXT:    call void @escape_inner.i1(i1 [[IV]], i1 [[NBITS]], i1 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i1 [[IV_NEXT]])
1431 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1432 ; CHECK:       end:
1433 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i1 [ [[IV_FINAL]], [[LOOP]] ]
1434 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i1 [ [[NBITS]], [[LOOP]] ]
1435 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i1 [ [[VAL_SHIFTED]], [[LOOP]] ]
1436 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1437 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i1 [ [[IV_NEXT]], [[LOOP]] ]
1438 ; CHECK-NEXT:    call void @escape_outer.i1(i1 [[IV_RES]], i1 [[NBITS_RES]], i1 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i1 [[IV_NEXT_RES]])
1439 ; CHECK-NEXT:    ret i1 [[IV_RES]]
1440 ;
1441 entry:
1442   br label %loop
1443
1444 loop:
1445   %iv = phi i1 [ %start, %entry ], [ %iv.next, %loop ]
1446   %nbits = add nsw i1 %iv, %extraoffset
1447   %val.shifted = ashr i1 %val, %nbits
1448   %val.shifted.iszero = icmp eq i1 %val.shifted, 0
1449   %iv.next = add i1 %iv, 1
1450
1451   call void @escape_inner.i1(i1 %iv, i1 %nbits, i1 %val.shifted, i1 %val.shifted.iszero, i1 %iv.next)
1452
1453   br i1 %val.shifted.iszero, label %end, label %loop
1454
1455 end:
1456   %iv.res = phi i1 [ %iv, %loop ]
1457   %nbits.res = phi i1 [ %nbits, %loop ]
1458   %val.shifted.res = phi i1 [ %val.shifted, %loop ]
1459   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1460   %iv.next.res = phi i1 [ %iv.next, %loop ]
1461
1462   call void @escape_outer.i1(i1 %iv.res, i1 %nbits.res, i1 %val.shifted.res, i1 %val.shifted.iszero.res, i1 %iv.next.res)
1463
1464   ret i1 %iv.res
1465 }
1466 define i2 @t28_addnsw_i2(i2 %val, i2 %start, i2 %extraoffset) mustprogress {
1467 ; CHECK-LABEL: @t28_addnsw_i2(
1468 ; CHECK-NEXT:  entry:
1469 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i2 @llvm.ctlz.i2(i2 [[VAL:%.*]], i1 false)
1470 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw i2 -2, [[VAL_NUMLEADINGZEROS]]
1471 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i2 0, [[EXTRAOFFSET:%.*]]
1472 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i2 [[VAL_NUMACTIVEBITS]], [[TMP0]]
1473 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i2 @llvm.smax.i2(i2 [[VAL_NUMACTIVEBITS_OFFSET]], i2 [[START:%.*]])
1474 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i2 [[IV_FINAL]], [[START]]
1475 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i2 [[LOOP_BACKEDGETAKENCOUNT]], 1
1476 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1477 ; CHECK:       loop:
1478 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i2 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1479 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw i2 [[LOOP_IV]], 1
1480 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i2 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1481 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i2 [[LOOP_IV]], [[START]]
1482 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i2 [[IV]], [[EXTRAOFFSET]]
1483 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i2 [[VAL]], [[NBITS]]
1484 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i2 [[IV]], 1
1485 ; CHECK-NEXT:    call void @escape_inner.i2(i2 [[IV]], i2 [[NBITS]], i2 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i2 [[IV_NEXT]])
1486 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1487 ; CHECK:       end:
1488 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i2 [ [[IV_FINAL]], [[LOOP]] ]
1489 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i2 [ [[NBITS]], [[LOOP]] ]
1490 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i2 [ [[VAL_SHIFTED]], [[LOOP]] ]
1491 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1492 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i2 [ [[IV_NEXT]], [[LOOP]] ]
1493 ; CHECK-NEXT:    call void @escape_outer.i2(i2 [[IV_RES]], i2 [[NBITS_RES]], i2 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i2 [[IV_NEXT_RES]])
1494 ; CHECK-NEXT:    ret i2 [[IV_RES]]
1495 ;
1496 entry:
1497   br label %loop
1498
1499 loop:
1500   %iv = phi i2 [ %start, %entry ], [ %iv.next, %loop ]
1501   %nbits = add nsw i2 %iv, %extraoffset
1502   %val.shifted = ashr i2 %val, %nbits
1503   %val.shifted.iszero = icmp eq i2 %val.shifted, 0
1504   %iv.next = add i2 %iv, 1
1505
1506   call void @escape_inner.i2(i2 %iv, i2 %nbits, i2 %val.shifted, i1 %val.shifted.iszero, i2 %iv.next)
1507
1508   br i1 %val.shifted.iszero, label %end, label %loop
1509
1510 end:
1511   %iv.res = phi i2 [ %iv, %loop ]
1512   %nbits.res = phi i2 [ %nbits, %loop ]
1513   %val.shifted.res = phi i2 [ %val.shifted, %loop ]
1514   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1515   %iv.next.res = phi i2 [ %iv.next, %loop ]
1516
1517   call void @escape_outer.i2(i2 %iv.res, i2 %nbits.res, i2 %val.shifted.res, i1 %val.shifted.iszero.res, i2 %iv.next.res)
1518
1519   ret i2 %iv.res
1520 }
1521 define i3 @t29_addnsw_i3(i3 %val, i3 %start, i3 %extraoffset) mustprogress {
1522 ; CHECK-LABEL: @t29_addnsw_i3(
1523 ; CHECK-NEXT:  entry:
1524 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i3 @llvm.ctlz.i3(i3 [[VAL:%.*]], i1 false)
1525 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i3 3, [[VAL_NUMLEADINGZEROS]]
1526 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i3 0, [[EXTRAOFFSET:%.*]]
1527 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i3 [[VAL_NUMACTIVEBITS]], [[TMP0]]
1528 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i3 @llvm.smax.i3(i3 [[VAL_NUMACTIVEBITS_OFFSET]], i3 [[START:%.*]])
1529 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i3 [[IV_FINAL]], [[START]]
1530 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i3 [[LOOP_BACKEDGETAKENCOUNT]], 1
1531 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1532 ; CHECK:       loop:
1533 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i3 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1534 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i3 [[LOOP_IV]], 1
1535 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i3 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1536 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i3 [[LOOP_IV]], [[START]]
1537 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i3 [[IV]], [[EXTRAOFFSET]]
1538 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i3 [[VAL]], [[NBITS]]
1539 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i3 [[IV]], 1
1540 ; CHECK-NEXT:    call void @escape_inner.i3(i3 [[IV]], i3 [[NBITS]], i3 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i3 [[IV_NEXT]])
1541 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1542 ; CHECK:       end:
1543 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i3 [ [[IV_FINAL]], [[LOOP]] ]
1544 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i3 [ [[NBITS]], [[LOOP]] ]
1545 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i3 [ [[VAL_SHIFTED]], [[LOOP]] ]
1546 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1547 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i3 [ [[IV_NEXT]], [[LOOP]] ]
1548 ; CHECK-NEXT:    call void @escape_outer.i3(i3 [[IV_RES]], i3 [[NBITS_RES]], i3 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i3 [[IV_NEXT_RES]])
1549 ; CHECK-NEXT:    ret i3 [[IV_RES]]
1550 ;
1551 entry:
1552   br label %loop
1553
1554 loop:
1555   %iv = phi i3 [ %start, %entry ], [ %iv.next, %loop ]
1556   %nbits = add nsw i3 %iv, %extraoffset
1557   %val.shifted = ashr i3 %val, %nbits
1558   %val.shifted.iszero = icmp eq i3 %val.shifted, 0
1559   %iv.next = add i3 %iv, 1
1560
1561   call void @escape_inner.i3(i3 %iv, i3 %nbits, i3 %val.shifted, i1 %val.shifted.iszero, i3 %iv.next)
1562
1563   br i1 %val.shifted.iszero, label %end, label %loop
1564
1565 end:
1566   %iv.res = phi i3 [ %iv, %loop ]
1567   %nbits.res = phi i3 [ %nbits, %loop ]
1568   %val.shifted.res = phi i3 [ %val.shifted, %loop ]
1569   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1570   %iv.next.res = phi i3 [ %iv.next, %loop ]
1571
1572   call void @escape_outer.i3(i3 %iv.res, i3 %nbits.res, i3 %val.shifted.res, i1 %val.shifted.iszero.res, i3 %iv.next.res)
1573
1574   ret i3 %iv.res
1575 }
1576
1577 define i1 @t30_addnuw_i1(i1 %val, i1 %start, i1 %extraoffset) mustprogress {
1578 ; CHECK-LABEL: @t30_addnuw_i1(
1579 ; CHECK-NEXT:  entry:
1580 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i1 @llvm.ctlz.i1(i1 [[VAL:%.*]], i1 false)
1581 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i1 true, [[VAL_NUMLEADINGZEROS]]
1582 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i1 [[VAL_NUMACTIVEBITS]], [[EXTRAOFFSET:%.*]]
1583 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i1 @llvm.smax.i1(i1 [[VAL_NUMACTIVEBITS_OFFSET]], i1 [[START:%.*]])
1584 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i1 [[IV_FINAL]], [[START]]
1585 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i1 [[LOOP_BACKEDGETAKENCOUNT]], true
1586 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1587 ; CHECK:       loop:
1588 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1589 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i1 [[LOOP_IV]], true
1590 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i1 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1591 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i1 [[LOOP_IV]], [[START]]
1592 ; CHECK-NEXT:    [[NBITS:%.*]] = add nuw i1 [[IV]], [[EXTRAOFFSET]]
1593 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i1 [[VAL]], [[NBITS]]
1594 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i1 [[IV]], true
1595 ; CHECK-NEXT:    call void @escape_inner.i1(i1 [[IV]], i1 [[NBITS]], i1 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i1 [[IV_NEXT]])
1596 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1597 ; CHECK:       end:
1598 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i1 [ [[IV_FINAL]], [[LOOP]] ]
1599 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i1 [ [[NBITS]], [[LOOP]] ]
1600 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i1 [ [[VAL_SHIFTED]], [[LOOP]] ]
1601 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1602 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i1 [ [[IV_NEXT]], [[LOOP]] ]
1603 ; CHECK-NEXT:    call void @escape_outer.i1(i1 [[IV_RES]], i1 [[NBITS_RES]], i1 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i1 [[IV_NEXT_RES]])
1604 ; CHECK-NEXT:    ret i1 [[IV_RES]]
1605 ;
1606 entry:
1607   br label %loop
1608
1609 loop:
1610   %iv = phi i1 [ %start, %entry ], [ %iv.next, %loop ]
1611   %nbits = add nuw i1 %iv, %extraoffset
1612   %val.shifted = ashr i1 %val, %nbits
1613   %val.shifted.iszero = icmp eq i1 %val.shifted, 0
1614   %iv.next = add i1 %iv, 1
1615
1616   call void @escape_inner.i1(i1 %iv, i1 %nbits, i1 %val.shifted, i1 %val.shifted.iszero, i1 %iv.next)
1617
1618   br i1 %val.shifted.iszero, label %end, label %loop
1619
1620 end:
1621   %iv.res = phi i1 [ %iv, %loop ]
1622   %nbits.res = phi i1 [ %nbits, %loop ]
1623   %val.shifted.res = phi i1 [ %val.shifted, %loop ]
1624   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1625   %iv.next.res = phi i1 [ %iv.next, %loop ]
1626
1627   call void @escape_outer.i1(i1 %iv.res, i1 %nbits.res, i1 %val.shifted.res, i1 %val.shifted.iszero.res, i1 %iv.next.res)
1628
1629   ret i1 %iv.res
1630 }
1631 define i2 @t31_addnuw_i2(i2 %val, i2 %start, i2 %extraoffset) mustprogress {
1632 ; CHECK-LABEL: @t31_addnuw_i2(
1633 ; CHECK-NEXT:  entry:
1634 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i2 @llvm.ctlz.i2(i2 [[VAL:%.*]], i1 false)
1635 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw i2 -2, [[VAL_NUMLEADINGZEROS]]
1636 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i2 0, [[EXTRAOFFSET:%.*]]
1637 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i2 [[VAL_NUMACTIVEBITS]], [[TMP0]]
1638 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i2 @llvm.smax.i2(i2 [[VAL_NUMACTIVEBITS_OFFSET]], i2 [[START:%.*]])
1639 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i2 [[IV_FINAL]], [[START]]
1640 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i2 [[LOOP_BACKEDGETAKENCOUNT]], 1
1641 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1642 ; CHECK:       loop:
1643 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i2 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1644 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw i2 [[LOOP_IV]], 1
1645 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i2 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1646 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i2 [[LOOP_IV]], [[START]]
1647 ; CHECK-NEXT:    [[NBITS:%.*]] = add nuw i2 [[IV]], [[EXTRAOFFSET]]
1648 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i2 [[VAL]], [[NBITS]]
1649 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i2 [[IV]], 1
1650 ; CHECK-NEXT:    call void @escape_inner.i2(i2 [[IV]], i2 [[NBITS]], i2 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i2 [[IV_NEXT]])
1651 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1652 ; CHECK:       end:
1653 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i2 [ [[IV_FINAL]], [[LOOP]] ]
1654 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i2 [ [[NBITS]], [[LOOP]] ]
1655 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i2 [ [[VAL_SHIFTED]], [[LOOP]] ]
1656 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1657 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i2 [ [[IV_NEXT]], [[LOOP]] ]
1658 ; CHECK-NEXT:    call void @escape_outer.i2(i2 [[IV_RES]], i2 [[NBITS_RES]], i2 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i2 [[IV_NEXT_RES]])
1659 ; CHECK-NEXT:    ret i2 [[IV_RES]]
1660 ;
1661 entry:
1662   br label %loop
1663
1664 loop:
1665   %iv = phi i2 [ %start, %entry ], [ %iv.next, %loop ]
1666   %nbits = add nuw i2 %iv, %extraoffset
1667   %val.shifted = ashr i2 %val, %nbits
1668   %val.shifted.iszero = icmp eq i2 %val.shifted, 0
1669   %iv.next = add i2 %iv, 1
1670
1671   call void @escape_inner.i2(i2 %iv, i2 %nbits, i2 %val.shifted, i1 %val.shifted.iszero, i2 %iv.next)
1672
1673   br i1 %val.shifted.iszero, label %end, label %loop
1674
1675 end:
1676   %iv.res = phi i2 [ %iv, %loop ]
1677   %nbits.res = phi i2 [ %nbits, %loop ]
1678   %val.shifted.res = phi i2 [ %val.shifted, %loop ]
1679   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1680   %iv.next.res = phi i2 [ %iv.next, %loop ]
1681
1682   call void @escape_outer.i2(i2 %iv.res, i2 %nbits.res, i2 %val.shifted.res, i1 %val.shifted.iszero.res, i2 %iv.next.res)
1683
1684   ret i2 %iv.res
1685 }
1686 define i3 @t32_addnuw_i3(i3 %val, i3 %start, i3 %extraoffset) mustprogress {
1687 ; CHECK-LABEL: @t32_addnuw_i3(
1688 ; CHECK-NEXT:  entry:
1689 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i3 @llvm.ctlz.i3(i3 [[VAL:%.*]], i1 false)
1690 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i3 3, [[VAL_NUMLEADINGZEROS]]
1691 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i3 0, [[EXTRAOFFSET:%.*]]
1692 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i3 [[VAL_NUMACTIVEBITS]], [[TMP0]]
1693 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i3 @llvm.smax.i3(i3 [[VAL_NUMACTIVEBITS_OFFSET]], i3 [[START:%.*]])
1694 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i3 [[IV_FINAL]], [[START]]
1695 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i3 [[LOOP_BACKEDGETAKENCOUNT]], 1
1696 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1697 ; CHECK:       loop:
1698 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i3 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1699 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i3 [[LOOP_IV]], 1
1700 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i3 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1701 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i3 [[LOOP_IV]], [[START]]
1702 ; CHECK-NEXT:    [[NBITS:%.*]] = add nuw i3 [[IV]], [[EXTRAOFFSET]]
1703 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i3 [[VAL]], [[NBITS]]
1704 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i3 [[IV]], 1
1705 ; CHECK-NEXT:    call void @escape_inner.i3(i3 [[IV]], i3 [[NBITS]], i3 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i3 [[IV_NEXT]])
1706 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1707 ; CHECK:       end:
1708 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i3 [ [[IV_FINAL]], [[LOOP]] ]
1709 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i3 [ [[NBITS]], [[LOOP]] ]
1710 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i3 [ [[VAL_SHIFTED]], [[LOOP]] ]
1711 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1712 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i3 [ [[IV_NEXT]], [[LOOP]] ]
1713 ; CHECK-NEXT:    call void @escape_outer.i3(i3 [[IV_RES]], i3 [[NBITS_RES]], i3 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i3 [[IV_NEXT_RES]])
1714 ; CHECK-NEXT:    ret i3 [[IV_RES]]
1715 ;
1716 entry:
1717   br label %loop
1718
1719 loop:
1720   %iv = phi i3 [ %start, %entry ], [ %iv.next, %loop ]
1721   %nbits = add nuw i3 %iv, %extraoffset
1722   %val.shifted = ashr i3 %val, %nbits
1723   %val.shifted.iszero = icmp eq i3 %val.shifted, 0
1724   %iv.next = add i3 %iv, 1
1725
1726   call void @escape_inner.i3(i3 %iv, i3 %nbits, i3 %val.shifted, i1 %val.shifted.iszero, i3 %iv.next)
1727
1728   br i1 %val.shifted.iszero, label %end, label %loop
1729
1730 end:
1731   %iv.res = phi i3 [ %iv, %loop ]
1732   %nbits.res = phi i3 [ %nbits, %loop ]
1733   %val.shifted.res = phi i3 [ %val.shifted, %loop ]
1734   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1735   %iv.next.res = phi i3 [ %iv.next, %loop ]
1736
1737   call void @escape_outer.i3(i3 %iv.res, i3 %nbits.res, i3 %val.shifted.res, i1 %val.shifted.iszero.res, i3 %iv.next.res)
1738
1739   ret i3 %iv.res
1740 }
1741
1742
1743 define i1 @t33_subnsw_i1(i1 %val, i1 %start, i1 %extraoffset) mustprogress {
1744 ; CHECK-LABEL: @t33_subnsw_i1(
1745 ; CHECK-NEXT:  entry:
1746 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i1 @llvm.ctlz.i1(i1 [[VAL:%.*]], i1 false)
1747 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i1 true, [[VAL_NUMLEADINGZEROS]]
1748 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i1 [[VAL_NUMACTIVEBITS]], [[EXTRAOFFSET:%.*]]
1749 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i1 @llvm.smax.i1(i1 [[VAL_NUMACTIVEBITS_OFFSET]], i1 [[START:%.*]])
1750 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i1 [[IV_FINAL]], [[START]]
1751 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i1 [[LOOP_BACKEDGETAKENCOUNT]], true
1752 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1753 ; CHECK:       loop:
1754 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i1 [ false, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1755 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i1 [[LOOP_IV]], true
1756 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i1 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1757 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i1 [[LOOP_IV]], [[START]]
1758 ; CHECK-NEXT:    [[NBITS:%.*]] = sub nsw i1 [[IV]], [[EXTRAOFFSET]]
1759 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i1 [[VAL]], [[NBITS]]
1760 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i1 [[IV]], true
1761 ; CHECK-NEXT:    call void @escape_inner.i1(i1 [[IV]], i1 [[NBITS]], i1 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i1 [[IV_NEXT]])
1762 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1763 ; CHECK:       end:
1764 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i1 [ [[IV_FINAL]], [[LOOP]] ]
1765 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i1 [ [[NBITS]], [[LOOP]] ]
1766 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i1 [ [[VAL_SHIFTED]], [[LOOP]] ]
1767 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1768 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i1 [ [[IV_NEXT]], [[LOOP]] ]
1769 ; CHECK-NEXT:    call void @escape_outer.i1(i1 [[IV_RES]], i1 [[NBITS_RES]], i1 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i1 [[IV_NEXT_RES]])
1770 ; CHECK-NEXT:    ret i1 [[IV_RES]]
1771 ;
1772 entry:
1773   br label %loop
1774
1775 loop:
1776   %iv = phi i1 [ %start, %entry ], [ %iv.next, %loop ]
1777   %nbits = sub nsw i1 %iv, %extraoffset
1778   %val.shifted = ashr i1 %val, %nbits
1779   %val.shifted.iszero = icmp eq i1 %val.shifted, 0
1780   %iv.next = add i1 %iv, 1
1781
1782   call void @escape_inner.i1(i1 %iv, i1 %nbits, i1 %val.shifted, i1 %val.shifted.iszero, i1 %iv.next)
1783
1784   br i1 %val.shifted.iszero, label %end, label %loop
1785
1786 end:
1787   %iv.res = phi i1 [ %iv, %loop ]
1788   %nbits.res = phi i1 [ %nbits, %loop ]
1789   %val.shifted.res = phi i1 [ %val.shifted, %loop ]
1790   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1791   %iv.next.res = phi i1 [ %iv.next, %loop ]
1792
1793   call void @escape_outer.i1(i1 %iv.res, i1 %nbits.res, i1 %val.shifted.res, i1 %val.shifted.iszero.res, i1 %iv.next.res)
1794
1795   ret i1 %iv.res
1796 }
1797 define i2 @t34_addnuw_i2(i2 %val, i2 %start, i2 %extraoffset) mustprogress {
1798 ; CHECK-LABEL: @t34_addnuw_i2(
1799 ; CHECK-NEXT:  entry:
1800 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i2 @llvm.ctlz.i2(i2 [[VAL:%.*]], i1 false)
1801 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw i2 -2, [[VAL_NUMLEADINGZEROS]]
1802 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i2 [[VAL_NUMACTIVEBITS]], [[EXTRAOFFSET:%.*]]
1803 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i2 @llvm.smax.i2(i2 [[VAL_NUMACTIVEBITS_OFFSET]], i2 [[START:%.*]])
1804 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i2 [[IV_FINAL]], [[START]]
1805 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i2 [[LOOP_BACKEDGETAKENCOUNT]], 1
1806 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1807 ; CHECK:       loop:
1808 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i2 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1809 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw i2 [[LOOP_IV]], 1
1810 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i2 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1811 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i2 [[LOOP_IV]], [[START]]
1812 ; CHECK-NEXT:    [[NBITS:%.*]] = sub nsw i2 [[IV]], [[EXTRAOFFSET]]
1813 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i2 [[VAL]], [[NBITS]]
1814 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i2 [[IV]], 1
1815 ; CHECK-NEXT:    call void @escape_inner.i2(i2 [[IV]], i2 [[NBITS]], i2 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i2 [[IV_NEXT]])
1816 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1817 ; CHECK:       end:
1818 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i2 [ [[IV_FINAL]], [[LOOP]] ]
1819 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i2 [ [[NBITS]], [[LOOP]] ]
1820 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i2 [ [[VAL_SHIFTED]], [[LOOP]] ]
1821 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1822 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i2 [ [[IV_NEXT]], [[LOOP]] ]
1823 ; CHECK-NEXT:    call void @escape_outer.i2(i2 [[IV_RES]], i2 [[NBITS_RES]], i2 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i2 [[IV_NEXT_RES]])
1824 ; CHECK-NEXT:    ret i2 [[IV_RES]]
1825 ;
1826 entry:
1827   br label %loop
1828
1829 loop:
1830   %iv = phi i2 [ %start, %entry ], [ %iv.next, %loop ]
1831   %nbits = sub nsw i2 %iv, %extraoffset
1832   %val.shifted = ashr i2 %val, %nbits
1833   %val.shifted.iszero = icmp eq i2 %val.shifted, 0
1834   %iv.next = add i2 %iv, 1
1835
1836   call void @escape_inner.i2(i2 %iv, i2 %nbits, i2 %val.shifted, i1 %val.shifted.iszero, i2 %iv.next)
1837
1838   br i1 %val.shifted.iszero, label %end, label %loop
1839
1840 end:
1841   %iv.res = phi i2 [ %iv, %loop ]
1842   %nbits.res = phi i2 [ %nbits, %loop ]
1843   %val.shifted.res = phi i2 [ %val.shifted, %loop ]
1844   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1845   %iv.next.res = phi i2 [ %iv.next, %loop ]
1846
1847   call void @escape_outer.i2(i2 %iv.res, i2 %nbits.res, i2 %val.shifted.res, i1 %val.shifted.iszero.res, i2 %iv.next.res)
1848
1849   ret i2 %iv.res
1850 }
1851 define i3 @t35_addnuw_i3(i3 %val, i3 %start, i3 %extraoffset) mustprogress {
1852 ; CHECK-LABEL: @t35_addnuw_i3(
1853 ; CHECK-NEXT:  entry:
1854 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i3 @llvm.ctlz.i3(i3 [[VAL:%.*]], i1 false)
1855 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i3 3, [[VAL_NUMLEADINGZEROS]]
1856 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i3 [[VAL_NUMACTIVEBITS]], [[EXTRAOFFSET:%.*]]
1857 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i3 @llvm.smax.i3(i3 [[VAL_NUMACTIVEBITS_OFFSET]], i3 [[START:%.*]])
1858 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i3 [[IV_FINAL]], [[START]]
1859 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i3 [[LOOP_BACKEDGETAKENCOUNT]], 1
1860 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1861 ; CHECK:       loop:
1862 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i3 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1863 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i3 [[LOOP_IV]], 1
1864 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i3 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1865 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i3 [[LOOP_IV]], [[START]]
1866 ; CHECK-NEXT:    [[NBITS:%.*]] = sub nsw i3 [[IV]], [[EXTRAOFFSET]]
1867 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i3 [[VAL]], [[NBITS]]
1868 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i3 [[IV]], 1
1869 ; CHECK-NEXT:    call void @escape_inner.i3(i3 [[IV]], i3 [[NBITS]], i3 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i3 [[IV_NEXT]])
1870 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1871 ; CHECK:       end:
1872 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i3 [ [[IV_FINAL]], [[LOOP]] ]
1873 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i3 [ [[NBITS]], [[LOOP]] ]
1874 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i3 [ [[VAL_SHIFTED]], [[LOOP]] ]
1875 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1876 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i3 [ [[IV_NEXT]], [[LOOP]] ]
1877 ; CHECK-NEXT:    call void @escape_outer.i3(i3 [[IV_RES]], i3 [[NBITS_RES]], i3 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i3 [[IV_NEXT_RES]])
1878 ; CHECK-NEXT:    ret i3 [[IV_RES]]
1879 ;
1880 entry:
1881   br label %loop
1882
1883 loop:
1884   %iv = phi i3 [ %start, %entry ], [ %iv.next, %loop ]
1885   %nbits = sub nsw i3 %iv, %extraoffset
1886   %val.shifted = ashr i3 %val, %nbits
1887   %val.shifted.iszero = icmp eq i3 %val.shifted, 0
1888   %iv.next = add i3 %iv, 1
1889
1890   call void @escape_inner.i3(i3 %iv, i3 %nbits, i3 %val.shifted, i1 %val.shifted.iszero, i3 %iv.next)
1891
1892   br i1 %val.shifted.iszero, label %end, label %loop
1893
1894 end:
1895   %iv.res = phi i3 [ %iv, %loop ]
1896   %nbits.res = phi i3 [ %nbits, %loop ]
1897   %val.shifted.res = phi i3 [ %val.shifted, %loop ]
1898   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1899   %iv.next.res = phi i3 [ %iv.next, %loop ]
1900
1901   call void @escape_outer.i3(i3 %iv.res, i3 %nbits.res, i3 %val.shifted.res, i1 %val.shifted.iszero.res, i3 %iv.next.res)
1902
1903   ret i3 %iv.res
1904 }
1905
1906 ; For ashr, we must have knowledge that the original loop is finite.
1907 define i8 @n36(i8 %val, i8 %start, i8 %extraoffset) {
1908 ; CHECK-LABEL: @n36(
1909 ; CHECK-NEXT:  entry:
1910 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1911 ; CHECK:       loop:
1912 ; CHECK-NEXT:    [[IV:%.*]] = phi i8 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
1913 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET:%.*]]
1914 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL:%.*]], [[NBITS]]
1915 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO:%.*]] = icmp eq i8 [[VAL_SHIFTED]], 0
1916 ; CHECK-NEXT:    [[IV_NEXT]] = add i8 [[IV]], 1
1917 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[VAL_SHIFTED_ISZERO]], i8 [[IV_NEXT]])
1918 ; CHECK-NEXT:    br i1 [[VAL_SHIFTED_ISZERO]], label [[END:%.*]], label [[LOOP]]
1919 ; CHECK:       end:
1920 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV]], [[LOOP]] ]
1921 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
1922 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
1923 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[VAL_SHIFTED_ISZERO]], [[LOOP]] ]
1924 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
1925 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
1926 ; CHECK-NEXT:    ret i8 [[IV_RES]]
1927 ;
1928 entry:
1929   br label %loop
1930
1931 loop:
1932   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
1933   %nbits = add nsw i8 %iv, %extraoffset
1934   %val.shifted = ashr i8 %val, %nbits
1935   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
1936   %iv.next = add i8 %iv, 1
1937
1938   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
1939
1940   br i1 %val.shifted.iszero, label %end, label %loop
1941
1942 end:
1943   %iv.res = phi i8 [ %iv, %loop ]
1944   %nbits.res = phi i8 [ %nbits, %loop ]
1945   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
1946   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
1947   %iv.next.res = phi i8 [ %iv.next, %loop ]
1948
1949   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
1950
1951   ret i8 %iv.res
1952 }
1953
1954 define i8 @p37(i8 %val, i8 %start, i8 %extraoffset) {
1955 ; CHECK-LABEL: @p37(
1956 ; CHECK-NEXT:  entry:
1957 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL:%.*]], i1 false)
1958 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
1959 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 0, [[EXTRAOFFSET:%.*]]
1960 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[TMP0]]
1961 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
1962 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
1963 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
1964 ; CHECK-NEXT:    br label [[LOOP:%.*]]
1965 ; CHECK:       loop:
1966 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
1967 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
1968 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
1969 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
1970 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET]]
1971 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
1972 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
1973 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
1974 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
1975 ; CHECK:       end:
1976 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
1977 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
1978 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
1979 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
1980 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
1981 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
1982 ; CHECK-NEXT:    ret i8 [[IV_RES]]
1983 ;
1984 entry:
1985   br label %loop
1986
1987 loop:
1988   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
1989   %nbits = add nsw i8 %iv, %extraoffset
1990   %val.shifted = ashr i8 %val, %nbits
1991   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
1992   %iv.next = add i8 %iv, 1
1993
1994   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
1995
1996   br i1 %val.shifted.iszero, label %end, label %loop, !llvm.loop !0
1997
1998 end:
1999   %iv.res = phi i8 [ %iv, %loop ]
2000   %nbits.res = phi i8 [ %nbits, %loop ]
2001   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
2002   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
2003   %iv.next.res = phi i8 [ %iv.next, %loop ]
2004
2005   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
2006
2007   ret i8 %iv.res
2008 }
2009 !0 = distinct !{!0, !1}
2010 !1 = !{!"llvm.loop.mustprogress"}
2011
2012 define i8 @p38(i8 %val.crude, i8 %start, i8 %extraoffset) {
2013 ; CHECK-LABEL: @p38(
2014 ; CHECK-NEXT:  entry:
2015 ; CHECK-NEXT:    [[VAL:%.*]] = and i8 [[VAL_CRUDE:%.*]], 127
2016 ; CHECK-NEXT:    [[VAL_NUMLEADINGZEROS:%.*]] = call i8 @llvm.ctlz.i8(i8 [[VAL]], i1 false)
2017 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS:%.*]] = sub nuw nsw i8 8, [[VAL_NUMLEADINGZEROS]]
2018 ; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 0, [[EXTRAOFFSET:%.*]]
2019 ; CHECK-NEXT:    [[VAL_NUMACTIVEBITS_OFFSET:%.*]] = add nsw i8 [[VAL_NUMACTIVEBITS]], [[TMP0]]
2020 ; CHECK-NEXT:    [[IV_FINAL:%.*]] = call i8 @llvm.smax.i8(i8 [[VAL_NUMACTIVEBITS_OFFSET]], i8 [[START:%.*]])
2021 ; CHECK-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub nsw i8 [[IV_FINAL]], [[START]]
2022 ; CHECK-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw nsw i8 [[LOOP_BACKEDGETAKENCOUNT]], 1
2023 ; CHECK-NEXT:    br label [[LOOP:%.*]]
2024 ; CHECK:       loop:
2025 ; CHECK-NEXT:    [[LOOP_IV:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ]
2026 ; CHECK-NEXT:    [[LOOP_IV_NEXT]] = add nuw nsw i8 [[LOOP_IV]], 1
2027 ; CHECK-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i8 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]]
2028 ; CHECK-NEXT:    [[IV:%.*]] = add nsw i8 [[LOOP_IV]], [[START]]
2029 ; CHECK-NEXT:    [[NBITS:%.*]] = add nsw i8 [[IV]], [[EXTRAOFFSET]]
2030 ; CHECK-NEXT:    [[VAL_SHIFTED:%.*]] = ashr i8 [[VAL]], [[NBITS]]
2031 ; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i8 [[IV]], 1
2032 ; CHECK-NEXT:    call void @escape_inner(i8 [[IV]], i8 [[NBITS]], i8 [[VAL_SHIFTED]], i1 [[LOOP_IVCHECK]], i8 [[IV_NEXT]])
2033 ; CHECK-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]]
2034 ; CHECK:       end:
2035 ; CHECK-NEXT:    [[IV_RES:%.*]] = phi i8 [ [[IV_FINAL]], [[LOOP]] ]
2036 ; CHECK-NEXT:    [[NBITS_RES:%.*]] = phi i8 [ [[NBITS]], [[LOOP]] ]
2037 ; CHECK-NEXT:    [[VAL_SHIFTED_RES:%.*]] = phi i8 [ [[VAL_SHIFTED]], [[LOOP]] ]
2038 ; CHECK-NEXT:    [[VAL_SHIFTED_ISZERO_RES:%.*]] = phi i1 [ [[LOOP_IVCHECK]], [[LOOP]] ]
2039 ; CHECK-NEXT:    [[IV_NEXT_RES:%.*]] = phi i8 [ [[IV_NEXT]], [[LOOP]] ]
2040 ; CHECK-NEXT:    call void @escape_outer(i8 [[IV_RES]], i8 [[NBITS_RES]], i8 [[VAL_SHIFTED_RES]], i1 [[VAL_SHIFTED_ISZERO_RES]], i8 [[IV_NEXT_RES]])
2041 ; CHECK-NEXT:    ret i8 [[IV_RES]]
2042 ;
2043 entry:
2044   %val = and i8 %val.crude, 127
2045   br label %loop
2046
2047 loop:
2048   %iv = phi i8 [ %start, %entry ], [ %iv.next, %loop ]
2049   %nbits = add nsw i8 %iv, %extraoffset
2050   %val.shifted = ashr i8 %val, %nbits
2051   %val.shifted.iszero = icmp eq i8 %val.shifted, 0
2052   %iv.next = add i8 %iv, 1
2053
2054   call void @escape_inner(i8 %iv, i8 %nbits, i8 %val.shifted, i1 %val.shifted.iszero, i8 %iv.next)
2055
2056   br i1 %val.shifted.iszero, label %end, label %loop
2057
2058 end:
2059   %iv.res = phi i8 [ %iv, %loop ]
2060   %nbits.res = phi i8 [ %nbits, %loop ]
2061   %val.shifted.res = phi i8 [ %val.shifted, %loop ]
2062   %val.shifted.iszero.res = phi i1 [ %val.shifted.iszero, %loop ]
2063   %iv.next.res = phi i8 [ %iv.next, %loop ]
2064
2065   call void @escape_outer(i8 %iv.res, i8 %nbits.res, i8 %val.shifted.res, i1 %val.shifted.iszero.res, i8 %iv.next.res)
2066
2067   ret i8 %iv.res
2068 }