; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -debugify -loop-idiom -mtriple=x86_64 -mcpu=core-avx2 < %s -S | FileCheck --check-prefix=ALL %s
; RUN: opt -debugify -loop-idiom -mtriple=x86_64 -mcpu=corei7 < %s -S | FileCheck --check-prefix=ALL %s

declare i32 @gen32()
declare void @use32(i32)
declare void @use1(i1)
declare void @external_side_effect()

; The patterns here are all have the same base form:
;   while (!(x & (1U << bit)))
;     x <<= 1;
; .. which is an uncountable loop.
; We should transform it into it's countable form.

; Most basic example.
define i32 @p0_i32(i32 %x, i32 %bit) {
; ALL-LABEL: @p0_i32(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG16:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META9:metadata !.*]], metadata !DIExpression()), [[DBG16]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG17:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG18:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG18]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG19:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG21:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG22:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG18]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META11]], metadata !DIExpression()), [[DBG18]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG23:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Same, but in some other bit width.
define i16 @p1_i16(i16 %x, i16 %bit) {
; ALL-LABEL: @p1_i16(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i16 1, [[BIT:%.*]], [[DBG32:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i16 [[BITMASK]], [[META26:metadata !.*]], metadata !DIExpression()), [[DBG32]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG33:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i16 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG34:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG34]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i16 [[X_CURR]], [[BITMASK]], [[DBG35:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]]
; ALL-NEXT:    [[X_NEXT]] = shl i16 [[X_CURR]], 1, [[DBG37:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_NEXT]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG38:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG34]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR_LCSSA]], [[META28]], metadata !DIExpression()), [[DBG34]]
; ALL-NEXT:    ret i16 [[X_CURR_LCSSA]], [[DBG39:!dbg !.*]]
;
entry:
  %bitmask = shl i16 1, %bit
  br label %loop

loop:
  %x.curr = phi i16 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i16 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i16 %x.curr.bitmasked, 0
  %x.next = shl i16 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i16 %x.curr
}

define i32 @p2_constant_mask_24thbit(i32 %x) {
; ALL-LABEL: @p2_constant_mask_24thbit(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG46:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG47:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META42:metadata !.*]], metadata !DIExpression()), [[DBG47]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 16777216, [[DBG48:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META43:metadata !.*]], metadata !DIExpression()), [[DBG48]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG49:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META44:metadata !.*]], metadata !DIExpression()), [[DBG49]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG50:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META45:metadata !.*]], metadata !DIExpression()), [[DBG50]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG51:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG47]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META42]], metadata !DIExpression()), [[DBG47]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG52:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, 16777216
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

define i32 @p3_constant_mask_15thbit(i32 %x) {
; ALL-LABEL: @p3_constant_mask_15thbit(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG59:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG60:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META55:metadata !.*]], metadata !DIExpression()), [[DBG60]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 32768, [[DBG61:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META56:metadata !.*]], metadata !DIExpression()), [[DBG61]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG62:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META57:metadata !.*]], metadata !DIExpression()), [[DBG62]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG63:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META58:metadata !.*]], metadata !DIExpression()), [[DBG63]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG64:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG60]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META55]], metadata !DIExpression()), [[DBG60]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG65:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, 32768
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; We don't particularly care whether %x.curr or %x.curr will live-out.
define i32 @p4_different_liveout(i32 %x, i32 %bit) {
; ALL-LABEL: @p4_different_liveout(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG73:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META68:metadata !.*]], metadata !DIExpression()), [[DBG73]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG74:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG75:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META69:metadata !.*]], metadata !DIExpression()), [[DBG75]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG76:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META70:metadata !.*]], metadata !DIExpression()), [[DBG76]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG77:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META71:metadata !.*]], metadata !DIExpression()), [[DBG77]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG78:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META72:metadata !.*]], metadata !DIExpression()), [[DBG78]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG79:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG78]]
; ALL-NEXT:    ret i32 [[X_NEXT_LCSSA]], [[DBG80:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.next ; not %x.curr
}
; Even both of them being live-out is fine.
define void @p5_both_liveout(i32 %x, i32 %bit, i32* %p0, i32* %p1) {
; ALL-LABEL: @p5_both_liveout(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG88:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META83:metadata !.*]], metadata !DIExpression()), [[DBG88]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG89:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG90:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META84:metadata !.*]], metadata !DIExpression()), [[DBG90]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG91:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META85:metadata !.*]], metadata !DIExpression()), [[DBG91]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG92:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META86:metadata !.*]], metadata !DIExpression()), [[DBG92]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG93:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META87:metadata !.*]], metadata !DIExpression()), [[DBG93]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG94:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG90]]
; ALL-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG93]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META84]], metadata !DIExpression()), [[DBG90]]
; ALL-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG95:!dbg !.*]]
; ALL-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG96:!dbg !.*]]
; ALL-NEXT:    ret void, [[DBG97:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  store i32 %x.curr, i32* %p0
  store i32 %x.next, i32* %p1
  ret void
}

define i32 @p6_constant_mask_signbit_noncanonical(i32 %x) {
; ALL-LABEL: @p6_constant_mask_signbit_noncanonical(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG104:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG105:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META100:metadata !.*]], metadata !DIExpression()), [[DBG105]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], -2147483648, [[DBG106:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META101:metadata !.*]], metadata !DIExpression()), [[DBG106]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG107:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META102:metadata !.*]], metadata !DIExpression()), [[DBG107]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG108:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META103:metadata !.*]], metadata !DIExpression()), [[DBG108]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG109:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG105]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META100]], metadata !DIExpression()), [[DBG105]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG110:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, 2147483648
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

define i32 @p7_constant_mask_signbit_canonical(i32 %x) {
; ALL-LABEL: @p7_constant_mask_signbit_canonical(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG116:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG117:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META113:metadata !.*]], metadata !DIExpression()), [[DBG117]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG118:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META114:metadata !.*]], metadata !DIExpression()), [[DBG118]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG119:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META115:metadata !.*]], metadata !DIExpression()), [[DBG119]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG120:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG117]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META113]], metadata !DIExpression()), [[DBG117]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG121:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.isbitunset = icmp sgt i32 %x.curr, -1
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Check that loop backedge's cmp-br order is correctly handled
define i32 @p8(i32 %x, i32 %bit) {
; ALL-LABEL: @p8(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG129:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META124:metadata !.*]], metadata !DIExpression()), [[DBG129]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG130:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG131:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG131]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG132:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META126:metadata !.*]], metadata !DIExpression()), [[DBG132]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG133:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META127:metadata !.*]], metadata !DIExpression()), [[DBG133]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG134:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META128:metadata !.*]], metadata !DIExpression()), [[DBG134]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG135:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG131]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META125]], metadata !DIExpression()), [[DBG131]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG136:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp ne i32 %x.curr.bitmasked, 0 ; swapped predicate
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %end, label %loop ; swapped dests

end:
  ret i32 %x.curr
}

; `and` is commutative, so ensure that order is irrelevant
define i32 @p9(i32 %x, i32 %bit) {
; ALL-LABEL: @p9(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG144:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META139:metadata !.*]], metadata !DIExpression()), [[DBG144]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG145:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG146:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META140:metadata !.*]], metadata !DIExpression()), [[DBG146]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[X_CURR]], [[DBG147:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META141:metadata !.*]], metadata !DIExpression()), [[DBG147]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG148:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META142:metadata !.*]], metadata !DIExpression()), [[DBG148]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG149:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META143:metadata !.*]], metadata !DIExpression()), [[DBG149]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG150:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG146]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META140]], metadata !DIExpression()), [[DBG146]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG151:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %bitmask, %x.curr ; swapped
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; PHI node does not have any particular order for it's incomings,
; but check that the other order still works.
define i32 @p10(i32 %x, i32 %bit) {
; ALL-LABEL: @p10(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG159:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META154:metadata !.*]], metadata !DIExpression()), [[DBG159]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG160:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X_NEXT:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ], [[DBG161:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META155:metadata !.*]], metadata !DIExpression()), [[DBG161]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG162:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META156:metadata !.*]], metadata !DIExpression()), [[DBG162]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG163:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META157:metadata !.*]], metadata !DIExpression()), [[DBG163]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG164:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META158:metadata !.*]], metadata !DIExpression()), [[DBG164]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG165:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG161]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META155]], metadata !DIExpression()), [[DBG161]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG166:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x.next, %loop ], [ %x, %entry ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; ICmp-Br are commutative
define i32 @p11(i32 %x) {
; ALL-LABEL: @p11(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG172:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG173:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG173]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[X_CURR]], 0, [[DBG174:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META170:metadata !.*]], metadata !DIExpression()), [[DBG174]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG175:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META171:metadata !.*]], metadata !DIExpression()), [[DBG175]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG176:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG173]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META169]], metadata !DIExpression()), [[DBG173]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG177:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.isbitunset = icmp slt i32 %x.curr, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %end, label %loop

end:
  ret i32 %x.curr
}

;-------------------------------------------------------------------------------
; Negative tests

; The %bitmask must be outside of the loop.
define i32 @n12(i32 %x, i32 %bit) {
; ALL-LABEL: @n12(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG185:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG186:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META180:metadata !.*]], metadata !DIExpression()), [[DBG186]]
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG187:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META181:metadata !.*]], metadata !DIExpression()), [[DBG187]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG188:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META182:metadata !.*]], metadata !DIExpression()), [[DBG188]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG189:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META183:metadata !.*]], metadata !DIExpression()), [[DBG189]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG190:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META184:metadata !.*]], metadata !DIExpression()), [[DBG190]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG191:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG186]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META180]], metadata !DIExpression()), [[DBG186]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG192:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %bitmask = shl i32 1, %bit ; not loop-invariant
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; The %bitmask must be loop-invariant
define i32 @n13(i32 %x, i32 %bit) {
; ALL-LABEL: @n13(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG200:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG201:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META195:metadata !.*]], metadata !DIExpression()), [[DBG201]]
; ALL-NEXT:    [[BITMASK:%.*]] = call i32 @gen32(), [[DBG202:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META196:metadata !.*]], metadata !DIExpression()), [[DBG202]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG203:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META197:metadata !.*]], metadata !DIExpression()), [[DBG203]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG204:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META198:metadata !.*]], metadata !DIExpression()), [[DBG204]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG205:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META199:metadata !.*]], metadata !DIExpression()), [[DBG205]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG206:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG201]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META195]], metadata !DIExpression()), [[DBG201]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG207:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %bitmask = call i32 @gen32() ; really not loop-invariant
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; The %bitmask must be a left-shift of a single bit.
define i32 @n14(i32 %x, i32 %bit) {
; ALL-LABEL: @n14(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 2, [[BIT:%.*]], [[DBG215:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META210:metadata !.*]], metadata !DIExpression()), [[DBG215]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG216:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG217:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META211:metadata !.*]], metadata !DIExpression()), [[DBG217]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG218:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META212:metadata !.*]], metadata !DIExpression()), [[DBG218]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG219:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META213:metadata !.*]], metadata !DIExpression()), [[DBG219]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG220:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META214:metadata !.*]], metadata !DIExpression()), [[DBG220]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG221:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG217]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META211]], metadata !DIExpression()), [[DBG217]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG222:!dbg !.*]]
;
entry:
  %bitmask = shl i32 2, %bit ; not what we are looking for.
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Bad recurrence - should be a left-shift by 1.
define i32 @n15(i32 %x, i32 %bit) {
; ALL-LABEL: @n15(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG230:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META225:metadata !.*]], metadata !DIExpression()), [[DBG230]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG231:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG232:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META226:metadata !.*]], metadata !DIExpression()), [[DBG232]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG233:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META227:metadata !.*]], metadata !DIExpression()), [[DBG233]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG234:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META228:metadata !.*]], metadata !DIExpression()), [[DBG234]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 2, [[DBG235:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META229:metadata !.*]], metadata !DIExpression()), [[DBG235]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG236:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG232]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META226]], metadata !DIExpression()), [[DBG232]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG237:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 2 ; wrong shift amount.
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; The comparison is not what we are looking for.
define i32 @n16(i32 %x, i32 %bit) {
; ALL-LABEL: @n16(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG245:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META240:metadata !.*]], metadata !DIExpression()), [[DBG245]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG246:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG247:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META241:metadata !.*]], metadata !DIExpression()), [[DBG247]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG248:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META242:metadata !.*]], metadata !DIExpression()), [[DBG248]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], [[BITMASK]], [[DBG249:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META243:metadata !.*]], metadata !DIExpression()), [[DBG249]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG250:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META244:metadata !.*]], metadata !DIExpression()), [[DBG250]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG251:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG247]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META241]], metadata !DIExpression()), [[DBG247]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG252:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp ne i32 %x.curr.bitmasked, %bitmask ; should be `==0`
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; We should loop while %x.curr.bitmasked is 0, not exit when it is 0.
define i32 @n17(i32 %x, i32 %bit) {
; ALL-LABEL: @n17(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG260:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META255:metadata !.*]], metadata !DIExpression()), [[DBG260]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG261:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG262:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META256:metadata !.*]], metadata !DIExpression()), [[DBG262]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG263:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META257:metadata !.*]], metadata !DIExpression()), [[DBG263]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG264:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META258:metadata !.*]], metadata !DIExpression()), [[DBG264]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG265:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META259:metadata !.*]], metadata !DIExpression()), [[DBG265]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG266:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG262]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META256]], metadata !DIExpression()), [[DBG262]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG267:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %end, label %loop ; wrong order of successors

end:
  ret i32 %x.curr
}

; We should loop while %x.curr.bitmasked is 0, not while it is not 0.
define i32 @n18(i32 %x, i32 %bit) {
; ALL-LABEL: @n18(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG275:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META270:metadata !.*]], metadata !DIExpression()), [[DBG275]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG276:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG277:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META271:metadata !.*]], metadata !DIExpression()), [[DBG277]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG278:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META272:metadata !.*]], metadata !DIExpression()), [[DBG278]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG279:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META273:metadata !.*]], metadata !DIExpression()), [[DBG279]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG280:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META274:metadata !.*]], metadata !DIExpression()), [[DBG280]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG281:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG277]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META271]], metadata !DIExpression()), [[DBG277]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG282:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp ne i32 %x.curr.bitmasked, 0 ; wrong predicate
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; PHI node is not a recurrence
define i32 @n19(i32 %x, i32 %bit) {
; ALL-LABEL: @n19(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG290:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META285:metadata !.*]], metadata !DIExpression()), [[DBG290]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG291:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X:%.*]], [[META286:metadata !.*]], metadata !DIExpression()), [[DBG292:!dbg !.*]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X]], [[BITMASK]], [[DBG293:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META287:metadata !.*]], metadata !DIExpression()), [[DBG293]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG294:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META288:metadata !.*]], metadata !DIExpression()), [[DBG294]]
; ALL-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], 1, [[DBG295:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META289:metadata !.*]], metadata !DIExpression()), [[DBG295]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG296:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    ret i32 [[X]], [[DBG297:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x, %loop ] ; should use %x.next when coming from %loop
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Masking wrong value
define i32 @n20(i32 %x, i32 %bit) {
; ALL-LABEL: @n20(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG305:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META300:metadata !.*]], metadata !DIExpression()), [[DBG305]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG306:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG307:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META301:metadata !.*]], metadata !DIExpression()), [[DBG307]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X]], [[BITMASK]], [[DBG308:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META302:metadata !.*]], metadata !DIExpression()), [[DBG308]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG309:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META303:metadata !.*]], metadata !DIExpression()), [[DBG309]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG310:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META304:metadata !.*]], metadata !DIExpression()), [[DBG310]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG311:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG307]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META301]], metadata !DIExpression()), [[DBG307]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG312:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x, %bitmask ; should use %x.curr, not %x
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Checking wrong value
define i32 @n21(i32 %x, i32 %bit) {
; ALL-LABEL: @n21(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG320:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META315:metadata !.*]], metadata !DIExpression()), [[DBG320]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG321:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG322:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META316:metadata !.*]], metadata !DIExpression()), [[DBG322]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG323:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META317:metadata !.*]], metadata !DIExpression()), [[DBG323]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR]], 0, [[DBG324:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META318:metadata !.*]], metadata !DIExpression()), [[DBG324]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG325:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META319:metadata !.*]], metadata !DIExpression()), [[DBG325]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG326:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG322]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META316]], metadata !DIExpression()), [[DBG322]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG327:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr, 0 ; should be checking %x.curr.bitmasked
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Shifting wrong value
define i32 @n22(i32 %x, i32 %bit) {
; ALL-LABEL: @n22(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG335:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META330:metadata !.*]], metadata !DIExpression()), [[DBG335]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG336:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG337:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META331:metadata !.*]], metadata !DIExpression()), [[DBG337]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG338:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META332:metadata !.*]], metadata !DIExpression()), [[DBG338]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG339:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META333:metadata !.*]], metadata !DIExpression()), [[DBG339]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X]], 1, [[DBG340:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META334:metadata !.*]], metadata !DIExpression()), [[DBG340]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG341:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG337]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META331]], metadata !DIExpression()), [[DBG337]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG342:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x, 1 ; should be shifting %x.curr
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Bit mask is not a power of 2
define i32 @n23(i32 %x) {
; ALL-LABEL: @n23(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG349:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG350:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META345:metadata !.*]], metadata !DIExpression()), [[DBG350]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 16777215, [[DBG351:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META346:metadata !.*]], metadata !DIExpression()), [[DBG351]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG352:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META347:metadata !.*]], metadata !DIExpression()), [[DBG352]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG353:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META348:metadata !.*]], metadata !DIExpression()), [[DBG353]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG354:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG350]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META345]], metadata !DIExpression()), [[DBG350]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG355:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, 16777215 ; not a power of 2
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Bit mask is not a power of 2
define i32 @n24(i32 %x) {
; ALL-LABEL: @n24(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG362:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG363:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META358:metadata !.*]], metadata !DIExpression()), [[DBG363]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 384, [[DBG364:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META359:metadata !.*]], metadata !DIExpression()), [[DBG364]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG365:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META360:metadata !.*]], metadata !DIExpression()), [[DBG365]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG366:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META361:metadata !.*]], metadata !DIExpression()), [[DBG366]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG367:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG363]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META358]], metadata !DIExpression()), [[DBG363]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG368:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, 384 ; not a power of 2
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; Bit mask is not a power of 2
define i32 @n25(i32 %x) {
; ALL-LABEL: @n25(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG375:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG376:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META371:metadata !.*]], metadata !DIExpression()), [[DBG376]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 32896, [[DBG377:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META372:metadata !.*]], metadata !DIExpression()), [[DBG377]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG378:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META373:metadata !.*]], metadata !DIExpression()), [[DBG378]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG379:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META374:metadata !.*]], metadata !DIExpression()), [[DBG379]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG380:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG376]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META371]], metadata !DIExpression()), [[DBG376]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG381:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, 32896 ; not a power of 2
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

;-------------------------------------------------------------------------------
; Tests with extra cruft.

; If loop body has any extra instructions we don't want to deal with it.
define i32 @n26(i32 %x, i32 %bit) {
; ALL-LABEL: @n26(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG389:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META384:metadata !.*]], metadata !DIExpression()), [[DBG389]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG390:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG391:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META385:metadata !.*]], metadata !DIExpression()), [[DBG391]]
; ALL-NEXT:    call void @external_side_effect(), [[DBG392:!dbg !.*]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG393:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META386:metadata !.*]], metadata !DIExpression()), [[DBG393]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG394:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META387:metadata !.*]], metadata !DIExpression()), [[DBG394]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG395:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META388:metadata !.*]], metadata !DIExpression()), [[DBG395]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG396:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG391]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META385]], metadata !DIExpression()), [[DBG391]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG397:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  call void @external_side_effect() ; not part of idiom.
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

define i32 @n27(i32 %x) {
; ALL-LABEL: @n27(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG403:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG404:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META400:metadata !.*]], metadata !DIExpression()), [[DBG404]]
; ALL-NEXT:    call void @external_side_effect(), [[DBG405:!dbg !.*]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG406:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META401:metadata !.*]], metadata !DIExpression()), [[DBG406]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG407:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META402:metadata !.*]], metadata !DIExpression()), [[DBG407]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG408:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG404]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META400]], metadata !DIExpression()), [[DBG404]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG409:!dbg !.*]]
;
entry:
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  call void @external_side_effect() ; not part of idiom.
  %x.curr.isbitunset = icmp sgt i32 %x.curr, -1
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  ret i32 %x.curr
}

; In-loop instructions should not have uses outside of the loop.
define i32 @n28(i32 %x, i32 %bit) {
; ALL-LABEL: @n28(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG417:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META412:metadata !.*]], metadata !DIExpression()), [[DBG417]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG418:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG419:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META413:metadata !.*]], metadata !DIExpression()), [[DBG419]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG420:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META414:metadata !.*]], metadata !DIExpression()), [[DBG420]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG421:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META415:metadata !.*]], metadata !DIExpression()), [[DBG421]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG422:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META416:metadata !.*]], metadata !DIExpression()), [[DBG422]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG423:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG419]]
; ALL-NEXT:    [[X_CURR_BITMASKED_LCSSA:%.*]] = phi i32 [ [[X_CURR_BITMASKED]], [[LOOP]] ], [[DBG420]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META413]], metadata !DIExpression()), [[DBG419]]
; ALL-NEXT:    call void @use32(i32 [[X_CURR_BITMASKED_LCSSA]]), [[DBG424:!dbg !.*]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG425:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  call void @use32(i32 %x.curr.bitmasked)
  ret i32 %x.curr
}
define i32 @n29(i32 %x, i32 %bit) {
; ALL-LABEL: @n29(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG433:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META428:metadata !.*]], metadata !DIExpression()), [[DBG433]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG434:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG435:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META429:metadata !.*]], metadata !DIExpression()), [[DBG435]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG436:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META430:metadata !.*]], metadata !DIExpression()), [[DBG436]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG437:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META431:metadata !.*]], metadata !DIExpression()), [[DBG437]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG438:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META432:metadata !.*]], metadata !DIExpression()), [[DBG438]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG439:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG435]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET_LCSSA:%.*]] = phi i1 [ [[X_CURR_ISBITUNSET]], [[LOOP]] ], [[DBG437]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_LCSSA]], [[META429]], metadata !DIExpression()), [[DBG435]]
; ALL-NEXT:    call void @use1(i1 [[X_CURR_ISBITUNSET_LCSSA]]), [[DBG440:!dbg !.*]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG441:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ %x, %entry ], [ %x.next, %loop ]
  %x.curr.bitmasked = and i32 %x.curr, %bitmask
  %x.curr.isbitunset = icmp eq i32 %x.curr.bitmasked, 0
  %x.next = shl i32 %x.curr, 1
  br i1 %x.curr.isbitunset, label %loop, label %end

end:
  call void @use1(i1 %x.curr.isbitunset)
  ret i32 %x.curr
}