; 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 }