llvm-for-llvmta/test/Transforms/LoopIdiom/X86/left-shift-until-bittest.ll

; 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-prefixes=ALL,LZCNT %s
; RUN: opt -debugify -loop-idiom -mtriple=x86_64 -mcpu=corei7 < %s -S | FileCheck  --check-prefixes=ALL,NOLZCNT %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) {
; LZCNT-LABEL: @p0_i32(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG16:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META9:metadata !.*]], metadata !DIExpression()), [[DBG16]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG17:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG17]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG17]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG17]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG17]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG17]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG17]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG17]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG17]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG17]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG18:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG17]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG17]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG17]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG19:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG21:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG22:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG22]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG22]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG17]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG23:!dbg !.*]]
;
; NOLZCNT-LABEL: @p0_i32(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG16:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META9:metadata !.*]], metadata !DIExpression()), [[DBG16]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG17:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG18:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META11:metadata !.*]], metadata !DIExpression()), [[DBG18]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG19:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META12:metadata !.*]], metadata !DIExpression()), [[DBG19]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG20:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META13:metadata !.*]], metadata !DIExpression()), [[DBG20]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG21:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META15:metadata !.*]], metadata !DIExpression()), [[DBG21]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG22:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG18]]
; NOLZCNT-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) {
; LZCNT-LABEL: @p1_i16(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i16 1, [[BIT:%.*]], [[DBG32:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[BITMASK]], [[META26:metadata !.*]], metadata !DIExpression()), [[DBG32]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i16 [[BITMASK]], -1, [[DBG33:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i16 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG33]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i16 [[X:%.*]], [[BIT_MASK]], [[DBG33]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i16 @llvm.ctlz.i16(i16 [[X_MASKED]], i1 true), [[DBG33]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i16 16, [[X_MASKED_NUMLEADINGZEROS]], [[DBG33]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i16 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG33]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i16 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG33]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i16 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG33]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i16 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG33]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i16 [[X_CURR]], 1, [[DBG33]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG34:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i16 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG33]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i16 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG33]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[TMP0]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG33]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i16 [[TMP0]], [[BITMASK]], [[DBG35:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]]
; LZCNT-NEXT:    [[TMP1]] = shl i16 [[TMP0]], 1, [[DBG37:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[TMP1]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i16 [[LOOP_IV]], 1, [[DBG38:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i16 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG38]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG38]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG33]]
; LZCNT-NEXT:    ret i16 [[X_CURR_LCSSA]], [[DBG39:!dbg !.*]]
;
; NOLZCNT-LABEL: @p1_i16(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i16 1, [[BIT:%.*]], [[DBG32:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[BITMASK]], [[META26:metadata !.*]], metadata !DIExpression()), [[DBG32]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG33:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i16 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG34:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR]], [[META28:metadata !.*]], metadata !DIExpression()), [[DBG34]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i16 [[X_CURR]], [[BITMASK]], [[DBG35:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_CURR_BITMASKED]], [[META29:metadata !.*]], metadata !DIExpression()), [[DBG35]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i16 [[X_CURR_BITMASKED]], 0, [[DBG36:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META30:metadata !.*]], metadata !DIExpression()), [[DBG36]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i16 [[X_CURR]], 1, [[DBG37:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i16 [[X_NEXT]], [[META31:metadata !.*]], metadata !DIExpression()), [[DBG37]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG38:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i16 [ [[X_CURR]], [[LOOP]] ], [[DBG34]]
; NOLZCNT-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
}

; We don't particularly care whether %x.curr or %x.curr will live-out.
define i32 @p2_different_liveout(i32 %x, i32 %bit) {
; LZCNT-LABEL: @p2_different_liveout(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG47:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META42:metadata !.*]], metadata !DIExpression()), [[DBG47]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG48:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG48]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG48]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG48]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG48]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG48]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG48]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG48]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG48]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG48]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG49:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG48]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG48]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META43:metadata !.*]], metadata !DIExpression()), [[DBG48]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG50:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META44:metadata !.*]], metadata !DIExpression()), [[DBG50]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG51:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META45:metadata !.*]], metadata !DIExpression()), [[DBG51]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG52:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META46:metadata !.*]], metadata !DIExpression()), [[DBG52]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG53:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG53]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG53]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG52]]
; LZCNT-NEXT:    ret i32 [[X_NEXT_LCSSA]], [[DBG54:!dbg !.*]]
;
; NOLZCNT-LABEL: @p2_different_liveout(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG47:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META42:metadata !.*]], metadata !DIExpression()), [[DBG47]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG48:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG49:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META43:metadata !.*]], metadata !DIExpression()), [[DBG49]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG50:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META44:metadata !.*]], metadata !DIExpression()), [[DBG50]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG51:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META45:metadata !.*]], metadata !DIExpression()), [[DBG51]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG52:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META46:metadata !.*]], metadata !DIExpression()), [[DBG52]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG53:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG52]]
; NOLZCNT-NEXT:    ret i32 [[X_NEXT_LCSSA]], [[DBG54:!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 can liveout
define void @p3_constant_mask_24thbit(i32 %x, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p3_constant_mask_24thbit(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], 33554431, [[DBG61:!dbg !.*]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG61]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG61]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG61]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 24, [[X_MASKED_LEADINGONEPOS]], [[DBG61]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG61]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG61]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG61]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG62:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG61]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG61]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META57:metadata !.*]], metadata !DIExpression()), [[DBG61]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], 16777216, [[DBG63:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META58:metadata !.*]], metadata !DIExpression()), [[DBG63]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG64:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META59:metadata !.*]], metadata !DIExpression()), [[DBG64]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG65:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META60:metadata !.*]], metadata !DIExpression()), [[DBG65]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG66:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG66]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG66]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG61]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG65]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG67:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG68:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG69:!dbg !.*]]
;
; NOLZCNT-LABEL: @p3_constant_mask_24thbit(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG61:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG62:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META57:metadata !.*]], metadata !DIExpression()), [[DBG62]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 16777216, [[DBG63:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META58:metadata !.*]], metadata !DIExpression()), [[DBG63]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG64:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META59:metadata !.*]], metadata !DIExpression()), [[DBG64]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG65:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META60:metadata !.*]], metadata !DIExpression()), [[DBG65]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG66:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG62]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG65]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG67:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG68:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG69:!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:
  store i32 %x.curr, i32* %p0
  store i32 %x.next, i32* %p1
  ret void
}

define void @p4_constant_mask_15thbit(i32 %x, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p4_constant_mask_15thbit(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], 65535, [[DBG76:!dbg !.*]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG76]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG76]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG76]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 15, [[X_MASKED_LEADINGONEPOS]], [[DBG76]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG76]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG76]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG76]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG77:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG76]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG76]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META72:metadata !.*]], metadata !DIExpression()), [[DBG76]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], 32768, [[DBG78:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META73:metadata !.*]], metadata !DIExpression()), [[DBG78]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG79:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META74:metadata !.*]], metadata !DIExpression()), [[DBG79]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG80:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META75:metadata !.*]], metadata !DIExpression()), [[DBG80]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG81:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG81]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG81]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG76]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG80]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG82:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG83:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG84:!dbg !.*]]
;
; NOLZCNT-LABEL: @p4_constant_mask_15thbit(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG76:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG77:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META72:metadata !.*]], metadata !DIExpression()), [[DBG77]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 32768, [[DBG78:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META73:metadata !.*]], metadata !DIExpression()), [[DBG78]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG79:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META74:metadata !.*]], metadata !DIExpression()), [[DBG79]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG80:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META75:metadata !.*]], metadata !DIExpression()), [[DBG80]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG81:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG77]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG80]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG82:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG83:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG84:!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:
  store i32 %x.curr, i32* %p0
  store i32 %x.next, i32* %p1
  ret void
}

; All no-wrap flags can be kept on the shift.
define void @p5_nuw(i32 %x, i32 %bit, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p5_nuw(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG92:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META87:metadata !.*]], metadata !DIExpression()), [[DBG92]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG93:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG93]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG93]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG93]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG93]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG93]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG93]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG93]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl nuw i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG93]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl nuw i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG93]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG94:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG93]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG93]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META88:metadata !.*]], metadata !DIExpression()), [[DBG93]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG95:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META89:metadata !.*]], metadata !DIExpression()), [[DBG95]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG96:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META90:metadata !.*]], metadata !DIExpression()), [[DBG96]]
; LZCNT-NEXT:    [[TMP1]] = shl nuw i32 [[TMP0]], 1, [[DBG97:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META91:metadata !.*]], metadata !DIExpression()), [[DBG97]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG98:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG98]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG98]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG93]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG97]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG99:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG100:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG101:!dbg !.*]]
;
; NOLZCNT-LABEL: @p5_nuw(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG92:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META87:metadata !.*]], metadata !DIExpression()), [[DBG92]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG93:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG94:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META88:metadata !.*]], metadata !DIExpression()), [[DBG94]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG95:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META89:metadata !.*]], metadata !DIExpression()), [[DBG95]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG96:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META90:metadata !.*]], metadata !DIExpression()), [[DBG96]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl nuw i32 [[X_CURR]], 1, [[DBG97:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META91:metadata !.*]], metadata !DIExpression()), [[DBG97]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG98:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG94]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG97]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG99:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG100:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG101:!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 nuw 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 void @p6_nsw(i32 %x, i32 %bit, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p6_nsw(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG109:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META104:metadata !.*]], metadata !DIExpression()), [[DBG109]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG110:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG110]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG110]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG110]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG110]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG110]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG110]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG110]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl nsw i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG110]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl nsw i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG110]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG111:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG110]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG110]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META105:metadata !.*]], metadata !DIExpression()), [[DBG110]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG112:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META106:metadata !.*]], metadata !DIExpression()), [[DBG112]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG113:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META107:metadata !.*]], metadata !DIExpression()), [[DBG113]]
; LZCNT-NEXT:    [[TMP1]] = shl nsw i32 [[TMP0]], 1, [[DBG114:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META108:metadata !.*]], metadata !DIExpression()), [[DBG114]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG115:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG115]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG115]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG110]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG114]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG116:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG117:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG118:!dbg !.*]]
;
; NOLZCNT-LABEL: @p6_nsw(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG109:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META104:metadata !.*]], metadata !DIExpression()), [[DBG109]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG110:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG111:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META105:metadata !.*]], metadata !DIExpression()), [[DBG111]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG112:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META106:metadata !.*]], metadata !DIExpression()), [[DBG112]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG113:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META107:metadata !.*]], metadata !DIExpression()), [[DBG113]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl nsw i32 [[X_CURR]], 1, [[DBG114:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META108:metadata !.*]], metadata !DIExpression()), [[DBG114]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG115:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG111]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG114]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG116:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG117:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG118:!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 nsw 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 void @p7_nuwnsw(i32 %x, i32 %bit, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p7_nuwnsw(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG126:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META121:metadata !.*]], metadata !DIExpression()), [[DBG126]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG127:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG127]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG127]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG127]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG127]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG127]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG127]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG127]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl nuw nsw i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG127]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl nuw nsw i32 [[X]], [[LOOP_TRIPCOUNT]], [[DBG127]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG128:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG127]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG127]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META122:metadata !.*]], metadata !DIExpression()), [[DBG127]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG129:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META123:metadata !.*]], metadata !DIExpression()), [[DBG129]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG130:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META124:metadata !.*]], metadata !DIExpression()), [[DBG130]]
; LZCNT-NEXT:    [[TMP1]] = shl nuw nsw i32 [[TMP0]], 1, [[DBG131:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG131]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG132:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG132]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG132]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG127]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG131]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG133:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG134:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG135:!dbg !.*]]
;
; NOLZCNT-LABEL: @p7_nuwnsw(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG126:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META121:metadata !.*]], metadata !DIExpression()), [[DBG126]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG127:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG128:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META122:metadata !.*]], metadata !DIExpression()), [[DBG128]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG129:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META123:metadata !.*]], metadata !DIExpression()), [[DBG129]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG130:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META124:metadata !.*]], metadata !DIExpression()), [[DBG130]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl nuw nsw i32 [[X_CURR]], 1, [[DBG131:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META125:metadata !.*]], metadata !DIExpression()), [[DBG131]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG132:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG128]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG131]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG133:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG134:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG135:!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 nuw nsw 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 void @p8_constant_mask_signbit_noncanonical(i32 %x, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p8_constant_mask_signbit_noncanonical(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[X_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), [[DBG142:!dbg !.*]]
; LZCNT-NEXT:    [[X_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_NUMLEADINGZEROS]], [[DBG142]]
; LZCNT-NEXT:    [[X_LEADINGONEPOS:%.*]] = add i32 [[X_NUMACTIVEBITS]], -1, [[DBG142]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 31, [[X_LEADINGONEPOS]], [[DBG142]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG142]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG142]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG142]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG143:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG142]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG142]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META138:metadata !.*]], metadata !DIExpression()), [[DBG142]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], -2147483648, [[DBG144:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META139:metadata !.*]], metadata !DIExpression()), [[DBG144]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG145:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META140:metadata !.*]], metadata !DIExpression()), [[DBG145]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG146:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META141:metadata !.*]], metadata !DIExpression()), [[DBG146]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG147:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG147]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG147]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG142]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG146]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG148:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG149:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG150:!dbg !.*]]
;
; NOLZCNT-LABEL: @p8_constant_mask_signbit_noncanonical(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG142:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG143:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META138:metadata !.*]], metadata !DIExpression()), [[DBG143]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], -2147483648, [[DBG144:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META139:metadata !.*]], metadata !DIExpression()), [[DBG144]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG145:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META140:metadata !.*]], metadata !DIExpression()), [[DBG145]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG146:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META141:metadata !.*]], metadata !DIExpression()), [[DBG146]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG147:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG143]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG146]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG148:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG149:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG150:!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:
  store i32 %x.curr, i32* %p0
  store i32 %x.next, i32* %p1
  ret void
}

define void @p9_constant_mask_signbit_canonical(i32 %x, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p9_constant_mask_signbit_canonical(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[X_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), [[DBG156:!dbg !.*]]
; LZCNT-NEXT:    [[X_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_NUMLEADINGZEROS]], [[DBG156]]
; LZCNT-NEXT:    [[X_LEADINGONEPOS:%.*]] = add i32 [[X_NUMACTIVEBITS]], -1, [[DBG156]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 31, [[X_LEADINGONEPOS]], [[DBG156]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG156]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG156]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG156]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG157:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG156]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG156]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META153:metadata !.*]], metadata !DIExpression()), [[DBG156]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[TMP0]], -1, [[DBG158:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META154:metadata !.*]], metadata !DIExpression()), [[DBG158]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG159:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META155:metadata !.*]], metadata !DIExpression()), [[DBG159]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG160:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG160]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG160]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG156]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG159]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG161:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG162:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG163:!dbg !.*]]
;
; NOLZCNT-LABEL: @p9_constant_mask_signbit_canonical(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG156:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG157:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META153:metadata !.*]], metadata !DIExpression()), [[DBG157]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG158:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META154:metadata !.*]], metadata !DIExpression()), [[DBG158]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG159:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META155:metadata !.*]], metadata !DIExpression()), [[DBG159]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG160:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG157]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG159]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG161:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG162:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG163:!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:
  store i32 %x.curr, i32* %p0
  store i32 %x.next, i32* %p1
  ret void
}

define void @p10_x_is_not_one(i32 %bit, i32* %p0, i32* %p1) {
; LZCNT-LABEL: @p10_x_is_not_one(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG171:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META166:metadata !.*]], metadata !DIExpression()), [[DBG171]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG172:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG172]]
; LZCNT-NEXT:    [[DOTMASKED:%.*]] = and i32 2, [[BIT_MASK]], [[DBG172]]
; LZCNT-NEXT:    [[DOTMASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[DOTMASKED]], i1 true), [[DBG172]]
; LZCNT-NEXT:    [[DOTMASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[DOTMASKED_NUMLEADINGZEROS]], [[DBG172]]
; LZCNT-NEXT:    [[DOTMASKED_LEADINGONEPOS:%.*]] = add i32 [[DOTMASKED_NUMACTIVEBITS]], -1, [[DBG172]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[DOTMASKED_LEADINGONEPOS]], [[DBG172]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG172]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 2, [[LOOP_BACKEDGETAKENCOUNT]], [[DBG172]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG172]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG173:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG172]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ 2, [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG172]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META167:metadata !.*]], metadata !DIExpression()), [[DBG172]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG174:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META168:metadata !.*]], metadata !DIExpression()), [[DBG174]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG175:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG175]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG176:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META170:metadata !.*]], metadata !DIExpression()), [[DBG176]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG177:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG177]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG177]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG172]]
; LZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG176]]
; LZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG178:!dbg !.*]]
; LZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG179:!dbg !.*]]
; LZCNT-NEXT:    ret void, [[DBG180:!dbg !.*]]
;
; NOLZCNT-LABEL: @p10_x_is_not_one(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG171:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META166:metadata !.*]], metadata !DIExpression()), [[DBG171]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG172:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG173:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META167:metadata !.*]], metadata !DIExpression()), [[DBG173]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG174:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META168:metadata !.*]], metadata !DIExpression()), [[DBG174]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG175:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META169:metadata !.*]], metadata !DIExpression()), [[DBG175]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG176:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META170:metadata !.*]], metadata !DIExpression()), [[DBG176]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG177:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG173]]
; NOLZCNT-NEXT:    [[X_NEXT_LCSSA:%.*]] = phi i32 [ [[X_NEXT]], [[LOOP]] ], [[DBG176]]
; NOLZCNT-NEXT:    store i32 [[X_CURR_LCSSA]], i32* [[P0:%.*]], align 4, [[DBG178:!dbg !.*]]
; NOLZCNT-NEXT:    store i32 [[X_NEXT_LCSSA]], i32* [[P1:%.*]], align 4, [[DBG179:!dbg !.*]]
; NOLZCNT-NEXT:    ret void, [[DBG180:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

loop:
  %x.curr = phi i32 [ 2, %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
}

; Check that loop backedge's cmp-br order is correctly handled
define i32 @p11(i32 %x, i32 %bit) {
; LZCNT-LABEL: @p11(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG188:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META183:metadata !.*]], metadata !DIExpression()), [[DBG188]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG189:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG189]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG189]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG189]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG189]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG189]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG189]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG189]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG189]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG189]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG190:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG189]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG189]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META184:metadata !.*]], metadata !DIExpression()), [[DBG189]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG191:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META185:metadata !.*]], metadata !DIExpression()), [[DBG191]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG192:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META186:metadata !.*]], metadata !DIExpression()), [[DBG192]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG193:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META187:metadata !.*]], metadata !DIExpression()), [[DBG193]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG194:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG194]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG194]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG189]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG195:!dbg !.*]]
;
; NOLZCNT-LABEL: @p11(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG188:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META183:metadata !.*]], metadata !DIExpression()), [[DBG188]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG189:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG190:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META184:metadata !.*]], metadata !DIExpression()), [[DBG190]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG191:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META185:metadata !.*]], metadata !DIExpression()), [[DBG191]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG192:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META186:metadata !.*]], metadata !DIExpression()), [[DBG192]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG193:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META187:metadata !.*]], metadata !DIExpression()), [[DBG193]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG194:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG190]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG195:!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 @p12(i32 %x, i32 %bit) {
; LZCNT-LABEL: @p12(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG203:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META198:metadata !.*]], metadata !DIExpression()), [[DBG203]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG204:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG204]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG204]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG204]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG204]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG204]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG204]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG204]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG204]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG204]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG205:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG204]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG204]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META199:metadata !.*]], metadata !DIExpression()), [[DBG204]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[TMP0]], [[DBG206:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META200:metadata !.*]], metadata !DIExpression()), [[DBG206]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG207:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META201:metadata !.*]], metadata !DIExpression()), [[DBG207]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG208:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META202:metadata !.*]], metadata !DIExpression()), [[DBG208]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG209:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG209]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG209]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG204]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG210:!dbg !.*]]
;
; NOLZCNT-LABEL: @p12(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG203:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META198:metadata !.*]], metadata !DIExpression()), [[DBG203]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG204:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG205:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META199:metadata !.*]], metadata !DIExpression()), [[DBG205]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[BITMASK]], [[X_CURR]], [[DBG206:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META200:metadata !.*]], metadata !DIExpression()), [[DBG206]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG207:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META201:metadata !.*]], metadata !DIExpression()), [[DBG207]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG208:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META202:metadata !.*]], metadata !DIExpression()), [[DBG208]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG209:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG205]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG210:!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 @p13(i32 %x, i32 %bit) {
; LZCNT-LABEL: @p13(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG218:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META213:metadata !.*]], metadata !DIExpression()), [[DBG218]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG219:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG219]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG219]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG219]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG219]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG219]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG219]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG219]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG219]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG219]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG220:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG219]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[TMP1:%.*]], [[LOOP]] ], [ [[X]], [[ENTRY]] ], [[DBG219]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META214:metadata !.*]], metadata !DIExpression()), [[DBG219]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG221:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META215:metadata !.*]], metadata !DIExpression()), [[DBG221]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG222:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META216:metadata !.*]], metadata !DIExpression()), [[DBG222]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG223:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META217:metadata !.*]], metadata !DIExpression()), [[DBG223]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG224:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG224]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG224]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG219]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG225:!dbg !.*]]
;
; NOLZCNT-LABEL: @p13(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG218:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META213:metadata !.*]], metadata !DIExpression()), [[DBG218]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG219:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X_NEXT:%.*]], [[LOOP]] ], [ [[X:%.*]], [[ENTRY:%.*]] ], [[DBG220:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META214:metadata !.*]], metadata !DIExpression()), [[DBG220]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG221:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META215:metadata !.*]], metadata !DIExpression()), [[DBG221]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG222:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META216:metadata !.*]], metadata !DIExpression()), [[DBG222]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG223:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META217:metadata !.*]], metadata !DIExpression()), [[DBG223]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG224:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG220]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG225:!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 @p14(i32 %x) {
; LZCNT-LABEL: @p14(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[X_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), [[DBG231:!dbg !.*]]
; LZCNT-NEXT:    [[X_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_NUMLEADINGZEROS]], [[DBG231]]
; LZCNT-NEXT:    [[X_LEADINGONEPOS:%.*]] = add i32 [[X_NUMACTIVEBITS]], -1, [[DBG231]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 31, [[X_LEADINGONEPOS]], [[DBG231]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG231]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG231]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG231]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG232:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG231]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG231]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META228:metadata !.*]], metadata !DIExpression()), [[DBG231]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[TMP0]], 0, [[DBG233:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META229:metadata !.*]], metadata !DIExpression()), [[DBG233]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG234:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META230:metadata !.*]], metadata !DIExpression()), [[DBG234]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG235:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG235]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG235]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG231]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG236:!dbg !.*]]
;
; NOLZCNT-LABEL: @p14(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG231:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG232:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META228:metadata !.*]], metadata !DIExpression()), [[DBG232]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp slt i32 [[X_CURR]], 0, [[DBG233:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META229:metadata !.*]], metadata !DIExpression()), [[DBG233]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG234:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META230:metadata !.*]], metadata !DIExpression()), [[DBG234]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG235:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG232]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG236:!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 @n15(i32 %x, i32 %bit) {
; ALL-LABEL: @n15(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG244:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG245:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META239:metadata !.*]], metadata !DIExpression()), [[DBG245]]
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG246:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META240:metadata !.*]], metadata !DIExpression()), [[DBG246]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG247:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META241:metadata !.*]], metadata !DIExpression()), [[DBG247]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG248:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META242:metadata !.*]], metadata !DIExpression()), [[DBG248]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG249:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META243:metadata !.*]], metadata !DIExpression()), [[DBG249]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG250:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG245]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG251:!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 @n16(i32 %x, i32 %bit) {
; ALL-LABEL: @n16(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG259:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG260:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META254:metadata !.*]], metadata !DIExpression()), [[DBG260]]
; ALL-NEXT:    [[BITMASK:%.*]] = call i32 @gen32(), [[DBG261:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META255:metadata !.*]], metadata !DIExpression()), [[DBG261]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG262:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META256:metadata !.*]], metadata !DIExpression()), [[DBG262]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG263:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META257:metadata !.*]], metadata !DIExpression()), [[DBG263]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG264:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META258:metadata !.*]], metadata !DIExpression()), [[DBG264]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG265:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG260]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG266:!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 @n17(i32 %x, i32 %bit) {
; ALL-LABEL: @n17(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 2, [[BIT:%.*]], [[DBG274:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META269:metadata !.*]], metadata !DIExpression()), [[DBG274]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG275:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG276:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META270:metadata !.*]], metadata !DIExpression()), [[DBG276]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG277:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META271:metadata !.*]], metadata !DIExpression()), [[DBG277]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG278:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META272:metadata !.*]], metadata !DIExpression()), [[DBG278]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG279:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META273:metadata !.*]], metadata !DIExpression()), [[DBG279]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG280:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG276]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG281:!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 @n18(i32 %x, i32 %bit) {
; ALL-LABEL: @n18(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG289:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META284:metadata !.*]], metadata !DIExpression()), [[DBG289]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG290:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG291:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META285:metadata !.*]], metadata !DIExpression()), [[DBG291]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG292:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META286:metadata !.*]], metadata !DIExpression()), [[DBG292]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG293:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META287:metadata !.*]], metadata !DIExpression()), [[DBG293]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 2, [[DBG294:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META288:metadata !.*]], metadata !DIExpression()), [[DBG294]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG295:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG291]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG296:!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 @n19(i32 %x, i32 %bit) {
; ALL-LABEL: @n19(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG304:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META299:metadata !.*]], metadata !DIExpression()), [[DBG304]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG305:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG306:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META300:metadata !.*]], metadata !DIExpression()), [[DBG306]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG307:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META301:metadata !.*]], metadata !DIExpression()), [[DBG307]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], [[BITMASK]], [[DBG308:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META302:metadata !.*]], metadata !DIExpression()), [[DBG308]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG309:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META303:metadata !.*]], metadata !DIExpression()), [[DBG309]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG310:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG306]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG311:!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 @n20(i32 %x, i32 %bit) {
; ALL-LABEL: @n20(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG319:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META314:metadata !.*]], metadata !DIExpression()), [[DBG319]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG320:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG321:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META315:metadata !.*]], metadata !DIExpression()), [[DBG321]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG322:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META316:metadata !.*]], metadata !DIExpression()), [[DBG322]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG323:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META317:metadata !.*]], metadata !DIExpression()), [[DBG323]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG324:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META318:metadata !.*]], metadata !DIExpression()), [[DBG324]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[END:%.*]], label [[LOOP]], [[DBG325:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG321]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG326:!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 @n21(i32 %x, i32 %bit) {
; ALL-LABEL: @n21(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG334:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META329:metadata !.*]], metadata !DIExpression()), [[DBG334]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG335:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG336:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META330:metadata !.*]], metadata !DIExpression()), [[DBG336]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG337:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META331:metadata !.*]], metadata !DIExpression()), [[DBG337]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp ne i32 [[X_CURR_BITMASKED]], 0, [[DBG338:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META332:metadata !.*]], metadata !DIExpression()), [[DBG338]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG339:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META333:metadata !.*]], metadata !DIExpression()), [[DBG339]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG340:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG336]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG341:!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 @n22(i32 %x, i32 %bit) {
; ALL-LABEL: @n22(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG349:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META344:metadata !.*]], metadata !DIExpression()), [[DBG349]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG350:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X:%.*]], [[META345:metadata !.*]], metadata !DIExpression()), [[DBG351:!dbg !.*]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X]], [[BITMASK]], [[DBG352:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META346:metadata !.*]], metadata !DIExpression()), [[DBG352]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG353:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META347:metadata !.*]], metadata !DIExpression()), [[DBG353]]
; ALL-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X]], 1, [[DBG354:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META348:metadata !.*]], metadata !DIExpression()), [[DBG354]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG355:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    ret i32 [[X]], [[DBG356:!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 @n23(i32 %x, i32 %bit) {
; ALL-LABEL: @n23(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG364:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META359:metadata !.*]], metadata !DIExpression()), [[DBG364]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG365:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG366:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META360:metadata !.*]], metadata !DIExpression()), [[DBG366]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X]], [[BITMASK]], [[DBG367:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META361:metadata !.*]], metadata !DIExpression()), [[DBG367]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG368:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META362:metadata !.*]], metadata !DIExpression()), [[DBG368]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG369:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META363:metadata !.*]], metadata !DIExpression()), [[DBG369]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG370:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG366]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG371:!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 @n24(i32 %x, i32 %bit) {
; ALL-LABEL: @n24(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG379:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META374:metadata !.*]], metadata !DIExpression()), [[DBG379]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG380:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG381:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META375:metadata !.*]], metadata !DIExpression()), [[DBG381]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG382:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META376:metadata !.*]], metadata !DIExpression()), [[DBG382]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR]], 0, [[DBG383:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META377:metadata !.*]], metadata !DIExpression()), [[DBG383]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG384:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META378:metadata !.*]], metadata !DIExpression()), [[DBG384]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG385:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG381]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG386:!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 @n25(i32 %x, i32 %bit) {
; ALL-LABEL: @n25(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG394:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META389:metadata !.*]], metadata !DIExpression()), [[DBG394]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG395:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG396:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META390:metadata !.*]], metadata !DIExpression()), [[DBG396]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG397:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META391:metadata !.*]], metadata !DIExpression()), [[DBG397]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG398:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META392:metadata !.*]], metadata !DIExpression()), [[DBG398]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X]], 1, [[DBG399:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META393:metadata !.*]], metadata !DIExpression()), [[DBG399]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG400:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG396]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG401:!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 @n26(i32 %x) {
; ALL-LABEL: @n26(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG408:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG409:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META404:metadata !.*]], metadata !DIExpression()), [[DBG409]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 16777215, [[DBG410:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META405:metadata !.*]], metadata !DIExpression()), [[DBG410]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG411:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META406:metadata !.*]], metadata !DIExpression()), [[DBG411]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG412:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META407:metadata !.*]], metadata !DIExpression()), [[DBG412]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG413:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG409]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG414:!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 @n27(i32 %x) {
; ALL-LABEL: @n27(
; ALL-NEXT:  entry:
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG421:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG422:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META417:metadata !.*]], metadata !DIExpression()), [[DBG422]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 384, [[DBG423:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META418:metadata !.*]], metadata !DIExpression()), [[DBG423]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG424:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META419:metadata !.*]], metadata !DIExpression()), [[DBG424]]
; ALL-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG425:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META420:metadata !.*]], metadata !DIExpression()), [[DBG425]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG426:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG422]]
; ALL-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG427:!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 @n28(i32 %x) {
; ALL-LABEL: @n28(
; ALL-NEXT:  entry:
; 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]], [[META430:metadata !.*]], metadata !DIExpression()), [[DBG435]]
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], 32896, [[DBG436:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META431: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]], [[META432: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]], [[META433: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:    ret i32 [[X_CURR_LCSSA]], [[DBG440:!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 @n29(i32 %x, i32 %bit) {
; LZCNT-LABEL: @n29(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG448:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META443:metadata !.*]], metadata !DIExpression()), [[DBG448]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG449:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG449]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG449]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG449]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG449]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG449]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG449]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG449]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG449]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG449]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG450:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG449]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG449]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META444:metadata !.*]], metadata !DIExpression()), [[DBG449]]
; LZCNT-NEXT:    call void @external_side_effect(), [[DBG451:!dbg !.*]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG452:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META445:metadata !.*]], metadata !DIExpression()), [[DBG452]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG453:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META446:metadata !.*]], metadata !DIExpression()), [[DBG453]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG454:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META447:metadata !.*]], metadata !DIExpression()), [[DBG454]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG455:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG455]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG455]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG449]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG456:!dbg !.*]]
;
; NOLZCNT-LABEL: @n29(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG448:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META443:metadata !.*]], metadata !DIExpression()), [[DBG448]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG449:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG450:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META444:metadata !.*]], metadata !DIExpression()), [[DBG450]]
; NOLZCNT-NEXT:    call void @external_side_effect(), [[DBG451:!dbg !.*]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG452:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META445:metadata !.*]], metadata !DIExpression()), [[DBG452]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG453:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META446:metadata !.*]], metadata !DIExpression()), [[DBG453]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG454:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META447:metadata !.*]], metadata !DIExpression()), [[DBG454]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG455:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG450]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG456:!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 @n30(i32 %x) {
; LZCNT-LABEL: @n30(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[X_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 true), [[DBG462:!dbg !.*]]
; LZCNT-NEXT:    [[X_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_NUMLEADINGZEROS]], [[DBG462]]
; LZCNT-NEXT:    [[X_LEADINGONEPOS:%.*]] = add i32 [[X_NUMACTIVEBITS]], -1, [[DBG462]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 31, [[X_LEADINGONEPOS]], [[DBG462]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG462]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG462]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG462]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG463:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG462]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG462]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META459:metadata !.*]], metadata !DIExpression()), [[DBG462]]
; LZCNT-NEXT:    call void @external_side_effect(), [[DBG464:!dbg !.*]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[TMP0]], -1, [[DBG465:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META460:metadata !.*]], metadata !DIExpression()), [[DBG465]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG466:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META461:metadata !.*]], metadata !DIExpression()), [[DBG466]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG467:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG467]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG467]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG462]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG468:!dbg !.*]]
;
; NOLZCNT-LABEL: @n30(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG462:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG463:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META459:metadata !.*]], metadata !DIExpression()), [[DBG463]]
; NOLZCNT-NEXT:    call void @external_side_effect(), [[DBG464:!dbg !.*]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp sgt i32 [[X_CURR]], -1, [[DBG465:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META460:metadata !.*]], metadata !DIExpression()), [[DBG465]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG466:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META461:metadata !.*]], metadata !DIExpression()), [[DBG466]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG467:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG463]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG468:!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 @n31(i32 %x, i32 %bit) {
; LZCNT-LABEL: @n31(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG476:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META471:metadata !.*]], metadata !DIExpression()), [[DBG476]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG477:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG477]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG477]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG477]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG477]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG477]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG477]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG477]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG477]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG477]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG478:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG477]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG477]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META472:metadata !.*]], metadata !DIExpression()), [[DBG477]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG479:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META473:metadata !.*]], metadata !DIExpression()), [[DBG479]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG480:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META474:metadata !.*]], metadata !DIExpression()), [[DBG480]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG481:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META475:metadata !.*]], metadata !DIExpression()), [[DBG481]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG482:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG482]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG482]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG477]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED_LCSSA:%.*]] = phi i32 [ [[X_CURR_BITMASKED]], [[LOOP]] ], [[DBG479]]
; LZCNT-NEXT:    call void @use32(i32 [[X_CURR_BITMASKED_LCSSA]]), [[DBG483:!dbg !.*]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG484:!dbg !.*]]
;
; NOLZCNT-LABEL: @n31(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG476:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META471:metadata !.*]], metadata !DIExpression()), [[DBG476]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG477:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG478:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META472:metadata !.*]], metadata !DIExpression()), [[DBG478]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG479:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META473:metadata !.*]], metadata !DIExpression()), [[DBG479]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG480:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META474:metadata !.*]], metadata !DIExpression()), [[DBG480]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG481:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META475:metadata !.*]], metadata !DIExpression()), [[DBG481]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG482:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG478]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED_LCSSA:%.*]] = phi i32 [ [[X_CURR_BITMASKED]], [[LOOP]] ], [[DBG479]]
; NOLZCNT-NEXT:    call void @use32(i32 [[X_CURR_BITMASKED_LCSSA]]), [[DBG483:!dbg !.*]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG484:!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 @n32(i32 %x, i32 %bit) {
; LZCNT-LABEL: @n32(
; LZCNT-NEXT:  entry:
; LZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG492:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META487:metadata !.*]], metadata !DIExpression()), [[DBG492]]
; LZCNT-NEXT:    [[BIT_LOWBITMASK:%.*]] = add i32 [[BITMASK]], -1, [[DBG493:!dbg !.*]]
; LZCNT-NEXT:    [[BIT_MASK:%.*]] = or i32 [[BIT_LOWBITMASK]], [[BITMASK]], [[DBG493]]
; LZCNT-NEXT:    [[X_MASKED:%.*]] = and i32 [[X:%.*]], [[BIT_MASK]], [[DBG493]]
; LZCNT-NEXT:    [[X_MASKED_NUMLEADINGZEROS:%.*]] = call i32 @llvm.ctlz.i32(i32 [[X_MASKED]], i1 true), [[DBG493]]
; LZCNT-NEXT:    [[X_MASKED_NUMACTIVEBITS:%.*]] = sub i32 32, [[X_MASKED_NUMLEADINGZEROS]], [[DBG493]]
; LZCNT-NEXT:    [[X_MASKED_LEADINGONEPOS:%.*]] = add i32 [[X_MASKED_NUMACTIVEBITS]], -1, [[DBG493]]
; LZCNT-NEXT:    [[LOOP_BACKEDGETAKENCOUNT:%.*]] = sub i32 [[BIT]], [[X_MASKED_LEADINGONEPOS]], [[DBG493]]
; LZCNT-NEXT:    [[LOOP_TRIPCOUNT:%.*]] = add nuw i32 [[LOOP_BACKEDGETAKENCOUNT]], 1, [[DBG493]]
; LZCNT-NEXT:    [[X_CURR:%.*]] = shl i32 [[X]], [[LOOP_BACKEDGETAKENCOUNT]], [[DBG493]]
; LZCNT-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG493]]
; LZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG494:!dbg !.*]]
; LZCNT:       loop:
; LZCNT-NEXT:    [[LOOP_IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[LOOP_IV_NEXT:%.*]], [[LOOP]] ], [[DBG493]]
; LZCNT-NEXT:    [[TMP0:%.*]] = phi i32 [ [[X]], [[ENTRY]] ], [ [[TMP1:%.*]], [[LOOP]] ], [[DBG493]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP0]], [[META488:metadata !.*]], metadata !DIExpression()), [[DBG493]]
; LZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[TMP0]], [[BITMASK]], [[DBG495:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META489:metadata !.*]], metadata !DIExpression()), [[DBG495]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG496:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META490:metadata !.*]], metadata !DIExpression()), [[DBG496]]
; LZCNT-NEXT:    [[TMP1]] = shl i32 [[TMP0]], 1, [[DBG497:!dbg !.*]]
; LZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[TMP1]], [[META491:metadata !.*]], metadata !DIExpression()), [[DBG497]]
; LZCNT-NEXT:    [[LOOP_IV_NEXT]] = add nuw i32 [[LOOP_IV]], 1, [[DBG498:!dbg !.*]]
; LZCNT-NEXT:    [[LOOP_IVCHECK:%.*]] = icmp eq i32 [[LOOP_IV_NEXT]], [[LOOP_TRIPCOUNT]], [[DBG498]]
; LZCNT-NEXT:    br i1 [[LOOP_IVCHECK]], label [[END:%.*]], label [[LOOP]], [[DBG498]]
; LZCNT:       end:
; LZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG493]]
; LZCNT-NEXT:    [[X_CURR_ISBITUNSET_LCSSA:%.*]] = phi i1 [ [[X_CURR_ISBITUNSET]], [[LOOP]] ], [[DBG496]]
; LZCNT-NEXT:    call void @use1(i1 [[X_CURR_ISBITUNSET_LCSSA]]), [[DBG499:!dbg !.*]]
; LZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG500:!dbg !.*]]
;
; NOLZCNT-LABEL: @n32(
; NOLZCNT-NEXT:  entry:
; NOLZCNT-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG492:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META487:metadata !.*]], metadata !DIExpression()), [[DBG492]]
; NOLZCNT-NEXT:    br label [[LOOP:%.*]], [[DBG493:!dbg !.*]]
; NOLZCNT:       loop:
; NOLZCNT-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP]] ], [[DBG494:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META488:metadata !.*]], metadata !DIExpression()), [[DBG494]]
; NOLZCNT-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG495:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META489:metadata !.*]], metadata !DIExpression()), [[DBG495]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG496:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META490:metadata !.*]], metadata !DIExpression()), [[DBG496]]
; NOLZCNT-NEXT:    [[X_NEXT]] = shl i32 [[X_CURR]], 1, [[DBG497:!dbg !.*]]
; NOLZCNT-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META491:metadata !.*]], metadata !DIExpression()), [[DBG497]]
; NOLZCNT-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG498:!dbg !.*]]
; NOLZCNT:       end:
; NOLZCNT-NEXT:    [[X_CURR_LCSSA:%.*]] = phi i32 [ [[X_CURR]], [[LOOP]] ], [[DBG494]]
; NOLZCNT-NEXT:    [[X_CURR_ISBITUNSET_LCSSA:%.*]] = phi i1 [ [[X_CURR_ISBITUNSET]], [[LOOP]] ], [[DBG496]]
; NOLZCNT-NEXT:    call void @use1(i1 [[X_CURR_ISBITUNSET_LCSSA]]), [[DBG499:!dbg !.*]]
; NOLZCNT-NEXT:    ret i32 [[X_CURR_LCSSA]], [[DBG500:!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
}

; %x.curr is not a PHI node
define i32 @n33(i32 %x, i32 %bit, i32 %x.curr) {
; ALL-LABEL: @n33(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG507:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META503:metadata !.*]], metadata !DIExpression()), [[DBG507]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG508:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR:%.*]], [[BITMASK]], [[DBG509:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META504:metadata !.*]], metadata !DIExpression()), [[DBG509]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG510:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META505:metadata !.*]], metadata !DIExpression()), [[DBG510]]
; ALL-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG511:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META506:metadata !.*]], metadata !DIExpression()), [[DBG511]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG512:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    ret i32 [[X_CURR]], [[DBG513:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br label %loop

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
}

; %x.curr is a PHI node in a wrong block
define i32 @n34(i32 %bit, i1 %c, i32 %x0, i32 %x1) {
; ALL-LABEL: @n34(
; ALL-NEXT:  entry:
; ALL-NEXT:    [[BITMASK:%.*]] = shl i32 1, [[BIT:%.*]], [[DBG521:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[BITMASK]], [[META516:metadata !.*]], metadata !DIExpression()), [[DBG521]]
; ALL-NEXT:    br i1 [[C:%.*]], label [[BB0:%.*]], label [[BB1:%.*]], [[DBG522:!dbg !.*]]
; ALL:       bb0:
; ALL-NEXT:    br label [[MERGE:%.*]], [[DBG523:!dbg !.*]]
; ALL:       bb1:
; ALL-NEXT:    br label [[MERGE]], [[DBG524:!dbg !.*]]
; ALL:       merge:
; ALL-NEXT:    [[X_CURR:%.*]] = phi i32 [ [[X0:%.*]], [[BB0]] ], [ [[X1:%.*]], [[BB1]] ], [[DBG525:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR]], [[META517:metadata !.*]], metadata !DIExpression()), [[DBG525]]
; ALL-NEXT:    br label [[LOOP:%.*]], [[DBG526:!dbg !.*]]
; ALL:       loop:
; ALL-NEXT:    [[X_CURR_BITMASKED:%.*]] = and i32 [[X_CURR]], [[BITMASK]], [[DBG527:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_CURR_BITMASKED]], [[META518:metadata !.*]], metadata !DIExpression()), [[DBG527]]
; ALL-NEXT:    [[X_CURR_ISBITUNSET:%.*]] = icmp eq i32 [[X_CURR_BITMASKED]], 0, [[DBG528:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i1 [[X_CURR_ISBITUNSET]], [[META519:metadata !.*]], metadata !DIExpression()), [[DBG528]]
; ALL-NEXT:    [[X_NEXT:%.*]] = shl i32 [[X_CURR]], 1, [[DBG529:!dbg !.*]]
; ALL-NEXT:    call void @llvm.dbg.value(metadata i32 [[X_NEXT]], [[META520:metadata !.*]], metadata !DIExpression()), [[DBG529]]
; ALL-NEXT:    br i1 [[X_CURR_ISBITUNSET]], label [[LOOP]], label [[END:%.*]], [[DBG530:!dbg !.*]]
; ALL:       end:
; ALL-NEXT:    ret i32 [[X_CURR]], [[DBG531:!dbg !.*]]
;
entry:
  %bitmask = shl i32 1, %bit
  br i1 %c, label %bb0, label %bb1

bb0:
  br label %merge
bb1:
  br label %merge

merge:
  %x.curr = phi i32 [ %x0, %bb0 ], [ %x1, %bb1 ]
  br label %loop

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
}