Simon Jakobi pushed to branch wip/sjakobi/T25233 at Glasgow Haskell Compiler / GHC Commits: 69637171 by Simon Jakobi at 2026-08-14T10:44:22+02:00 X86 NCG: use btr/bts/btc for single-bit operations Previously the Cmm patterns x & ~(1 << i) x | (1 << i) x ^ (1 << i) compiled to mov/shl/not/and-style sequences of 3-4 instructions. Now they compile to a single btr, bts or btc, matching what C compilers produce. When the bit index is a literal, constant folding has already collapsed these patterns into ones with a literal mask, such as x & 0xfffffeffffffffff for x & ~(1 << 40). Such masks are now also compiled to a bit-test instruction when they don't fit in an imm32 and would otherwise have to be loaded into a register first. For a variable bit index, this applies only when the shift is unchecked (uncheckedShiftL#, Data.Bits.unsafeShiftL): the bounds-checked shiftL used by e.g. the default clearBit/setBit/complementBit implementations wraps the shift in a bounds mask that this optimisation does not see through. With a literal index, the bounds mask is constant-folded away, so the checked operations benefit too. See Note [Bit-test instructions] in GHC.CmmToAsm.X86.CodeGen. Fixes #25233. Assisted-by: Claude Fable 5 - - - - - 7 changed files: - + changelog.d/ncg-x86-bit-test-instructions - compiler/GHC/CmmToAsm/X86/CodeGen.hs - compiler/GHC/CmmToAsm/X86/Instr.hs - compiler/GHC/CmmToAsm/X86/Ppr.hs - + testsuite/tests/codeGen/should_gen_asm/T25233.asm - + testsuite/tests/codeGen/should_gen_asm/T25233.hs - testsuite/tests/codeGen/should_gen_asm/all.T Changes: ===================================== changelog.d/ncg-x86-bit-test-instructions ===================================== @@ -0,0 +1,20 @@ +section: compiler +synopsis: The x86 native code generator now uses the bit-test instructions + ``btr``/``bts``/``btc`` to clear, set or complement a single bit +description: + Cmm patterns such as ``x & ~(1 << i)``, ``x | (1 << i)`` and + ``x ^ (1 << i)`` now compile to a single ``btr``/``bts``/``btc`` + instruction instead of a mov/shl/not/and-style sequence, matching what C + compilers produce. The same applies to the literal masks that constant + folding produces from these patterns when ``i`` is constant, in the cases + where the mask doesn't fit in an imm32 operand. + + For a variable bit index this applies only when the shift is unchecked, + as with ``uncheckedShiftL#`` or ``Data.Bits.unsafeShiftL``. The + bounds-checked ``shiftL`` — used, for example, by the default + implementations of ``clearBit``, ``setBit`` and ``complementBit`` — + wraps the shift in a bounds mask that this optimisation does not see + through. With a literal index, the bounds mask is constant-folded away, + so the checked operations benefit too. +mrs: !16311 +issues: #25233 ===================================== compiler/GHC/CmmToAsm/X86/CodeGen.hs ===================================== @@ -1442,6 +1442,44 @@ getRegister' platform is32Bit (CmmMachOp mop [x]) = do -- unary MachOps (PUNPCKLQDQ fmt (OpReg dst) dst) ) +-- Use the bit-test instructions btr/bts/btc for clearing, setting and +-- complementing a single, variable bit: e.g. x .&. complement (1 `shiftL` i) +-- is btr. See Note [Bit-test instructions]. +getRegister' _ is32Bit (CmmMachOp (MO_And w) [x, CmmMachOp (MO_Not _) [y]]) + | Just i <- singleBit_maybe y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTR x i +getRegister' _ is32Bit (CmmMachOp (MO_And w) [CmmMachOp (MO_Not _) [y], x]) + | Just i <- singleBit_maybe y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTR x i +getRegister' _ is32Bit (CmmMachOp (MO_Or w) [x, y]) + | Just i <- singleBit_maybe y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTS x i +getRegister' _ is32Bit (CmmMachOp (MO_Or w) [y, x]) + | Just i <- singleBit_maybe y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTS x i +getRegister' _ is32Bit (CmmMachOp (MO_Xor w) [x, y]) + | Just i <- singleBit_maybe y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTC x i +getRegister' _ is32Bit (CmmMachOp (MO_Xor w) [y, x]) + | Just i <- singleBit_maybe y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTC x i + +-- The same operations with a literal bit index: constant folding has turned +-- the mask itself into a literal, so use a bit-test instruction whenever the +-- mask does not fit in an imm32. See Note [Bit-test instructions]. +getRegister' platform is32Bit (CmmMachOp (MO_And w) [x, CmmLit lit@(CmmInt m _)]) + | Just i <- clearBitLit_maybe w m, bitTestOpWidthOK is32Bit w + , not (is32BitLit platform lit) + = genBitTestImmCode (intFormat w) BTR x i +getRegister' platform is32Bit (CmmMachOp (MO_Or w) [x, CmmLit lit@(CmmInt m _)]) + | Just i <- setBitLit_maybe w m, bitTestOpWidthOK is32Bit w + , not (is32BitLit platform lit) + = genBitTestImmCode (intFormat w) BTS x i +getRegister' platform is32Bit (CmmMachOp (MO_Xor w) [x, CmmLit lit@(CmmInt m _)]) + | Just i <- setBitLit_maybe w m, bitTestOpWidthOK is32Bit w + , not (is32BitLit platform lit) + = genBitTestImmCode (intFormat w) BTC x i + getRegister' platform is32Bit (CmmMachOp mop [x, y]) = do -- dyadic MachOps sse4_1 <- sse4_1Enabled sse4_2 <- sse4_2Enabled @@ -5883,6 +5921,100 @@ genTrivialCode rep instr a b = do instr b_op dst return (Any rep code) +{- 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 + + x & ~(1 << i) ==> btr i, x (#25233) + +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). + +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: +constant folding has already turned the whole mask into a literal. If that +mask fits in an imm32, an ordinary and/or/xor with an immediate is at least +as good; 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 bit offset. + +We restrict the pattern to W32 and native-width W64: the instructions do not +exist at width 8, and sub-word Cmm operations at W8/W16 are rare enough that +they are not worth the extra care. +-} + +-- | Match @1 << i@, returning @i@. +-- +-- The returned expression is always at word width ('machOpArgReps' fixes +-- shift amounts at 'wordWidth'). See Note [Bit-test instructions]. +singleBit_maybe :: CmmExpr -> Maybe CmmExpr +singleBit_maybe (CmmMachOp (MO_Shl _) [CmmLit (CmmInt 1 _), i]) = Just i +singleBit_maybe _ = Nothing + +-- | If exactly one bit of @m@, taken at width @w@, is set, return its index. +-- +-- See Note [Bit-test instructions]. +setBitLit_maybe :: Width -> Integer -> Maybe Int +setBitLit_maybe w m + | popCount m' == 1 = Just (countTrailingZeros m') + | otherwise = Nothing + where + -- w <= W64 in this X86-specific code, so a Word64 suffices. + m' = fromInteger (narrowU w m) :: Word64 + +-- | If exactly one bit of @m@, taken at width @w@, is clear, return its +-- index. +-- +-- See Note [Bit-test instructions]. +clearBitLit_maybe :: Width -> Integer -> Maybe Int +clearBitLit_maybe w m = setBitLit_maybe w (complement m) + +bitTestOpWidthOK :: Bool -> Width -> Bool +bitTestOpWidthOK is32Bit w = w == W32 || (w == W64 && not is32Bit) + +-- | Generate code for @dst := x@ followed by a bit-test instruction +-- (btr/bts/btc) with bit offset @i@. +-- +-- Analogous to 'genTrivialCode', but the offset operand must be a register, +-- not memory. See Note [Bit-test instructions]. +genBitTestCode :: Format -> (Format -> Operand -> Operand -> Instr) + -> CmmExpr -> CmmExpr -> NatM Register +genBitTestCode rep instr x i = do + (i_reg, i_code) <- getNonClobberedReg i + x_code <- getAnyReg x + tmp <- getNewRegNat rep + let + -- As in genTrivialCode, 'i' must stay alive across the computation of + -- 'x' into dst, so save it in a temporary if dst holds 'i'. + code dst + | dst == i_reg = + i_code `appOL` + unitOL (MOV rep (OpReg i_reg) (OpReg tmp)) `appOL` + x_code dst `snocOL` + instr rep (OpReg tmp) (OpReg dst) + | otherwise = + i_code `appOL` + x_code dst `snocOL` + instr rep (OpReg i_reg) (OpReg dst) + return (Any rep code) + +-- | Generate code for @dst := x@ followed by a bit-test instruction +-- (btr/bts/btc) with an immediate bit offset. +-- +-- See Note [Bit-test instructions]. +genBitTestImmCode :: Format -> (Format -> Operand -> Operand -> Instr) + -> CmmExpr -> Int -> NatM Register +genBitTestImmCode rep instr x i = do + x_code <- getAnyReg x + let code dst = x_code dst `snocOL` instr rep (OpImm (ImmInt i)) (OpReg dst) + return (Any rep code) + regClashesWithOp :: Reg -> Operand -> Bool reg `regClashesWithOp` OpReg reg2 = reg == reg2 reg `regClashesWithOp` OpAddr amode = any (==reg) (addrModeRegs amode) ===================================== compiler/GHC/CmmToAsm/X86/Instr.hs ===================================== @@ -193,6 +193,12 @@ data Instr | SHLD Format Operand{-amount-} Operand Operand | BT Format Imm Operand + -- | Bit test-and-reset + | BTR Format Operand{- ^ bit offset (imm/reg) -} Operand + -- | Bit set + | BTS Format Operand{- ^ bit offset (imm/reg) -} Operand + -- | Bit complement + | BTC Format Operand{- ^ bit offset (imm/reg) -} Operand | NOP @@ -496,6 +502,9 @@ regUsageOfInstr platform instr 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 []) + BTR fmt off dst -> usageRM fmt off dst + BTS fmt off dst -> usageRM fmt off dst + BTC fmt off dst -> usageRM fmt off dst PUSH fmt op -> mkRUR (use_R fmt op []) POP fmt op -> mkRU [] (def_W fmt op) @@ -830,6 +839,9 @@ patchRegsOfInstr platform instr env 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 + 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 TEST fmt src dst -> patch2 (TEST fmt) src dst CMP fmt src dst -> patch2 (CMP fmt) src dst PUSH fmt op -> patch1 (PUSH fmt) op ===================================== compiler/GHC/CmmToAsm/X86/Ppr.hs ===================================== @@ -862,6 +862,15 @@ pprInstr platform i = case i of BT format imm src -> pprFormatImmOp (text "bt") format imm src + BTR format off dst + -> pprFormatOpOp (text "btr") format off dst + + BTS format off dst + -> pprFormatOpOp (text "bts") format off dst + + BTC format off dst + -> pprFormatOpOp (text "btc") format off dst + CMP format src dst | isFloatFormat format -> pprFormatOpOp (text "ucomi") format src dst -- SSE2 | otherwise -> pprFormatOpOp (text "cmp") format src dst ===================================== testsuite/tests/codeGen/should_gen_asm/T25233.asm ===================================== @@ -0,0 +1,9 @@ +btrq +btsq +btcq +btrl +btsl +btcl +btrq $40, +btsq $40, +btcq $40, ===================================== testsuite/tests/codeGen/should_gen_asm/T25233.hs ===================================== @@ -0,0 +1,39 @@ +{-# LANGUAGE MagicHash #-} + +-- Check that clearing/setting/complementing a single, variable bit +-- uses the btr/bts/btc instructions (#25233). +module T25233 where + +import GHC.Exts + +myClearBit :: Word# -> Int# -> Word# +myClearBit x i = x `and#` not# (1## `uncheckedShiftL#` i) + +mySetBit :: Word# -> Int# -> Word# +mySetBit x i = x `or#` (1## `uncheckedShiftL#` i) + +myComplementBit :: Word# -> Int# -> Word# +myComplementBit x i = x `xor#` (1## `uncheckedShiftL#` i) + +myClearBit32 :: Word32# -> Int# -> Word32# +myClearBit32 x i = + x `andWord32#` notWord32# (wordToWord32# 1## `uncheckedShiftLWord32#` i) + +mySetBit32 :: Word32# -> Int# -> Word32# +mySetBit32 x i = x `orWord32#` (wordToWord32# 1## `uncheckedShiftLWord32#` i) + +myComplementBit32 :: Word32# -> Int# -> Word32# +myComplementBit32 x i = + x `xorWord32#` (wordToWord32# 1## `uncheckedShiftLWord32#` i) + +-- With a constant bit index >= 32, the mask constant-folds to a literal +-- that does not fit in an imm32, so a bit-test instruction with an +-- immediate offset is used. +myClearBit40 :: Word# -> Word# +myClearBit40 x = x `and#` not# (1## `uncheckedShiftL#` 40#) + +mySetBit40 :: Word# -> Word# +mySetBit40 x = x `or#` (1## `uncheckedShiftL#` 40#) + +myComplementBit40 :: Word# -> Word# +myComplementBit40 x = x `xor#` (1## `uncheckedShiftL#` 40#) ===================================== testsuite/tests/codeGen/should_gen_asm/all.T ===================================== @@ -23,6 +23,8 @@ test('avx512-int64-minmax', [unless(arch('x86_64'), skip), when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-mavx512vl']) test('avx512-word64-minmax', [unless(arch('x86_64'), skip), when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-mavx512vl']) +test('T25233', [unless(arch('x86_64'), skip), + when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-O']) is_aarch64_codegen = [ unless(arch('aarch64'), skip), when(unregisterised(), skip), View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/6963717182f0070c6c041f71a2812169... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/6963717182f0070c6c041f71a2812169... 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