Simon Jakobi pushed to branch wip/sjakobi/T27688-bt-single-bit-tests at Glasgow Haskell Compiler / GHC Commits: 342dc80c by Simon Jakobi at 2026-09-05T23:22:20+02:00 X86 NCG: use bt for single-bit tests Previously the Cmm patterns (x & (1 << i)) != 0 (x & (1 << i)) == 0 compiled to a mov/shl/and/test sequence pinning the shift count to %cl. Now they compile to a single bt, whose carry flag feeds the branch or setcc directly, matching what C compilers produce. As for btr/bts/btc, a literal single-bit mask that does not fit in an imm32 (e.g. x & (1 << 40)) is also tested with bt, with an immediate bit offset. Masks that do fit keep using test, since test+jcc macro-fuse and bt+jcc do not. The same restriction as for btr/bts/btc applies: a variable bit index is only recognised when the shift is unchecked. Data.Bits.testBit on Int and Word goes through the bounds-checked shiftL, whose bounds mask this pattern does not see through, so it does not benefit yet. See Note [Bit-test instructions] in GHC.CmmToAsm.X86.CodeGen. Closes #27688. Assisted-by: Claude Fable 5.1 - - - - - 9 changed files: - + changelog.d/ncg-x86-bt-single-bit-tests - compiler/GHC/CmmToAsm/X86/CodeGen.hs - compiler/GHC/CmmToAsm/X86/Instr.hs - compiler/GHC/CmmToAsm/X86/Ppr.hs - + testsuite/tests/codeGen/should_gen_asm/T27688.asm - + testsuite/tests/codeGen/should_gen_asm/T27688.hs - + testsuite/tests/codeGen/should_gen_asm/T27688b.asm - + testsuite/tests/codeGen/should_gen_asm/T27688b.cmm - testsuite/tests/codeGen/should_gen_asm/all.T Changes: ===================================== changelog.d/ncg-x86-bt-single-bit-tests ===================================== @@ -0,0 +1,15 @@ +section: compiler +synopsis: The x86 native code generator now uses the bit-test instruction + ``bt`` to test a single bit +description: + Cmm patterns such as ``(x & (1 << i)) != 0`` and ``(x & (1 << i)) == 0`` + now compile to a single ``bt`` instruction, whose carry flag feeds the + conditional branch directly, instead of a mov/shl/and/test sequence, + matching what C compilers produce. The same applies to a literal mask + that doesn't fit in an imm32 operand, such as ``x & (1 << 40)``. + + As for ``btr``/``bts``/``btc``, a variable bit index benefits only when + the shift is unchecked. The bounds mask added by the checked ``shiftL``, + and hence by the default ``Data.Bits.testBit``, hides the pattern. +mrs: !0 +issues: #27688 ===================================== compiler/GHC/CmmToAsm/X86/CodeGen.hs ===================================== @@ -3945,6 +3945,24 @@ condIntCode' platform cond (CmmLoad x ty _) (CmmLit lit) -- return (CondCode False cond code) +-- single-bit test, e.g. (x & (1 << i)) != 0 +-- see Note [Bit-test instructions] +condIntCode' platform cond (CmmMachOp (MO_And w) [x, y]) (CmmLit (CmmInt 0 _)) + | Just bt_cond <- bitTestCond cond + , bitTestOpWidthOK (target32Bit platform) w + , Just (opnd, ix) <- setBitArgs_maybe platform w x y + , let fmt = intFormat w + = case ix of + BitIndexImm i -> do + (x_reg, x_code) <- getSomeReg opnd + return $ CondCode False bt_cond $ + x_code `snocOL` BT fmt (OpImm (ImmInt i)) (OpReg x_reg) + BitIndexReg i -> do + (i_reg, i_code) <- getNonClobberedReg i + (x_reg, x_code) <- getSomeReg opnd + return $ CondCode False bt_cond $ + i_code `appOL` x_code `snocOL` BT fmt (OpReg i_reg) (OpReg x_reg) + -- anything vs zero, using a mask -- TODO: Add some sanity checking!!!! condIntCode' platform cond (CmmMachOp (MO_And _) [x,o2]) (CmmLit (CmmInt 0 ty)) @@ -5901,17 +5919,18 @@ genTrivialCode rep instr a b = do {- Note [Bit-test instructions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -x86 has dedicated instructions for clearing (btr), setting (bts) and -complementing (btc) a single bit whose index is given in a register. We use -them for Cmm patterns such as +x86 has dedicated instructions for testing (bt), clearing (btr), setting +(bts) and complementing (btc) a single bit whose index is given in a +register. We use them for Cmm patterns such as - x & ~(1 << i) ==> btr i, x (#25233) + (x & (1 << i)) != 0 ==> bt i, x; jc + x & ~(1 << i) ==> btr i, x -replacing a mov/shl/not/and sequence with a single instruction. The -shift-count register operand of shl is masked modulo the operand width, and -the bit-offset register operand of btr/bts/btc is masked the same way, so -the replacement is faithful even for out-of-range i (where the Cmm shift is -in any case undefined). +replacing a mov/shl/and/test or mov/shl/not/and sequence with a single +instruction. The shift-count register operand of shl is masked modulo the +operand width, and the bit-offset register operand of the bit-test +instructions is masked the same way, so the replacement is faithful even for +out-of-range i (where the Cmm shift is in any case undefined). The bit-offset operand of these instructions must be an immediate or a register. When the bit index is a literal, no shift reaches the NCG: @@ -5919,10 +5938,11 @@ constant folding has already turned the whole mask into a literal. If that mask fits in an imm32, we keep the ordinary and/or/xor with an immediate: it has the same latency and better throughput (more execution ports) than the bit-test instructions, and at worst two bytes of extra code size for bit -indices 7..30. +indices 7..30. Likewise a single-bit test keeps 'test' with an immediate: +test+jcc macro-fuse into one uop, bt+jcc do not. But a W64 mask touching the upper bits, e.g. ~(1 << 40), would have to be moved into a register first. For such masks we recognise the folded literal itself -(exactly one bit clear resp. set) and emit btr/bts/btc with an immediate +(exactly one bit clear resp. set) and emit bt/btr/bts/btc with an immediate bit offset. We restrict the pattern to W32 and native-width W64: the instructions do not @@ -5959,14 +5979,25 @@ clearBitLit_maybe w m = setBitLit_maybe w (complement m) bitTestOpWidthOK :: Bool -> Width -> Bool bitTestOpWidthOK is32Bit w = w == W32 || (w == W64 && not is32Bit) --- | The bit-offset operand of a bit-test instruction (btr/bts/btc). +-- | The condition to branch on after @bt@, for a @mask != 0@ ('NE') or +-- @mask == 0@ ('EQQ') comparison. 'Nothing' for any other condition. +-- +-- @bt@ reports the tested bit in CF, so we branch on 'CARRY' or 'GEU' +-- rather than on ZF via 'NE' or 'EQQ'. +bitTestCond :: Cond -> Maybe Cond +bitTestCond NE = Just CARRY +bitTestCond EQQ = Just GEU +bitTestCond _ = Nothing + +-- | The bit-offset operand of a bit-test instruction. data BitIndex = BitIndexReg CmmExpr -- ^ variable index, computed into a register | BitIndexImm Int -- ^ literal index, emitted as an immediate --- | Match the operands of a single-bit set or complement operation: one --- operand is a mask @1 << i@, or a literal with exactly one bit set that --- does not fit in an imm32. Returns the other operand and the bit index. +-- | Match the operands of a single-bit set, complement or test operation: +-- one operand is a mask @1 << i@, or a literal with exactly one bit set +-- that does not fit in an imm32. Returns the other operand and the bit +-- index. -- -- Both operand orders are matched, e.g. @x | (1 << i)@ and @(1 << i) | x@. -- ===================================== compiler/GHC/CmmToAsm/X86/Instr.hs ===================================== @@ -192,7 +192,8 @@ data Instr | SHRD Format Operand{-amount-} Operand Operand | SHLD Format Operand{-amount-} Operand Operand - | BT Format Imm Operand + -- | Bit test + | BT Format Operand{- ^ bit offset (imm/reg) -} Operand -- | Bit test-and-reset | BTR Format Operand{- ^ bit offset (imm/reg) -} Operand -- | Bit set @@ -501,7 +502,7 @@ regUsageOfInstr platform instr SHR fmt imm dst -> usageRM fmt imm dst SHLD fmt imm dst1 dst2 -> usageRMM fmt imm dst1 dst2 SHRD fmt imm dst1 dst2 -> usageRMM fmt imm dst1 dst2 - BT fmt _ src -> mkRUR (use_R fmt src []) + BT fmt off src -> mkRUR (use_R fmt off $! use_R fmt src []) BTR fmt off dst -> usageRM fmt off dst BTS fmt off dst -> usageRM fmt off dst BTC fmt off dst -> usageRM fmt off dst @@ -838,7 +839,7 @@ patchRegsOfInstr platform instr env SHR fmt imm dst -> patch1 (SHR fmt imm) dst SHLD fmt imm dst1 dst2 -> patch2 (SHLD fmt imm) dst1 dst2 SHRD fmt imm dst1 dst2 -> patch2 (SHRD fmt imm) dst1 dst2 - BT fmt imm src -> patch1 (BT fmt imm) src + BT fmt off src -> patch2 (BT fmt) off src BTR fmt off dst -> patch2 (BTR fmt) off dst BTS fmt off dst -> patch2 (BTS fmt) off dst BTC fmt off dst -> patch2 (BTC fmt) off dst ===================================== compiler/GHC/CmmToAsm/X86/Ppr.hs ===================================== @@ -859,8 +859,8 @@ pprInstr platform i = case i of SHRD format src dst1 dst2 -> pprShift2 (text "shrd") format src dst1 dst2 - BT format imm src - -> pprFormatImmOp (text "bt") format imm src + BT format off src + -> pprFormatOpOp (text "bt") format off src BTR format off dst -> pprFormatOpOp (text "btr") format off dst @@ -1250,16 +1250,6 @@ pprInstr platform i = case i of FmtInt64 -> text "q" pprBroadcastFormat _ = panic "Scalar Format invading vector operation" - pprFormatImmOp :: Line doc -> Format -> Imm -> Operand -> doc - pprFormatImmOp name format imm op1 - = line $ hcat [ - pprMnemonic name format, - char '$', - pprImm platform imm, - comma, - pprOperand platform format op1 - ] - pprFormatOp_ :: Line doc -> Format -> Operand -> doc pprFormatOp_ name format op1 = line $ hcat [ ===================================== testsuite/tests/codeGen/should_gen_asm/T27688.asm ===================================== @@ -0,0 +1,3 @@ +btq % +btl % +btq $40, ===================================== testsuite/tests/codeGen/should_gen_asm/T27688.hs ===================================== @@ -0,0 +1,30 @@ +{-# LANGUAGE MagicHash #-} + +-- Check that testing a single, variable bit uses the bt instruction +-- (#27688). +module T27688 where + +import GHC.Exts + +testBitNe :: Word# -> Int# -> Int# +testBitNe x i = + if isTrue# ((x `and#` (1## `uncheckedShiftL#` i)) `neWord#` 0##) + then 1# else 2# + +testBitEq :: Word# -> Int# -> Int# +testBitEq x i = + if isTrue# ((x `and#` (1## `uncheckedShiftL#` i)) `eqWord#` 0##) + then 1# else 2# + +testBit32 :: Word32# -> Int# -> Int# +testBit32 x i = + if isTrue# ((x `andWord32#` (wordToWord32# 1## `uncheckedShiftLWord32#` i)) + `neWord32#` wordToWord32# 0##) + then 1# else 2# + +-- With a constant bit index >= 32, the mask constant-folds to a literal +-- that does not fit in an imm32, so bt with an immediate offset is used. +testBit40 :: Word# -> Int# +testBit40 x = + if isTrue# ((x `and#` (1## `uncheckedShiftL#` 40#)) `neWord#` 0##) + then 1# else 2# ===================================== testsuite/tests/codeGen/should_gen_asm/T27688b.asm ===================================== @@ -0,0 +1,4 @@ +btq % +setc +setae +btq $40, ===================================== testsuite/tests/codeGen/should_gen_asm/T27688b.cmm ===================================== @@ -0,0 +1,21 @@ +#include "Cmm.h" + +// Single-bit tests whose result is used as a value rather than as a branch +// condition, a literal mask that does not fit in an imm32, and the mask on +// the left of the operator (#27688). + +testBitValue (W_ x, W_ i) { + return ((x & (1 << i)) != 0); +} + +testBitValueEq (W_ x, W_ i) { + return ((x & (1 << i)) == 0); +} + +testBit40 (W_ x) { + return (((0x10000000000 :: bits64) & x) != 0); +} + +testBitLeft (W_ x, W_ i) { + return (((1 << i) & x) != 0); +} ===================================== testsuite/tests/codeGen/should_gen_asm/all.T ===================================== @@ -27,6 +27,10 @@ test('T25233', [unless(arch('x86_64'), skip), when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-O']) test('T25233b', [unless(arch('x86_64'), skip), when(unregisterised(), skip)], compile_grep_asm, ['cmm', True, '']) +test('T27688', [unless(arch('x86_64'), skip), + when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-O']) +test('T27688b', [unless(arch('x86_64'), skip), + when(unregisterised(), skip)], compile_grep_asm, ['cmm', True, '']) is_aarch64_codegen = [ unless(arch('aarch64'), skip), when(unregisterised(), skip), View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/342dc80cfd6695fa7c6c4aea785abd2f... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/342dc80cfd6695fa7c6c4aea785abd2f... You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications: https://gitlab.haskell.org/-/profile/notifications | Help: https://gitlab.haskell.org/help