Simon Jakobi pushed to branch wip/sjakobi/T25233 at Glasgow Haskell Compiler / GHC Commits: 8ff2e0e0 by Simon Jakobi at 2026-07-07T18:42:24+02:00 X86 NCG: use btr/bts/btc for single-bit operations Lower the Cmm patterns x & ~(1 << i) ==> btr i, x x | (1 << i) ==> bts i, x x ^ (1 << i) ==> btc i, x (with non-literal i) to x86 bit-test instructions instead of a mov/shl/not/and-style sequence. This makes e.g. clearBit on Word compile to a single instruction, matching what C compilers produce. See Note [Bit-test instructions] in GHC.CmmToAsm.X86.CodeGen. Closes #25233 Assisted-by: Claude Fable 5 - - - - - 6 changed files: - 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: ===================================== compiler/GHC/CmmToAsm/X86/CodeGen.hs ===================================== @@ -1442,6 +1442,28 @@ 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 w') [y]]) + | w == w', Just i <- isSingleBit w y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTR x i +getRegister' _ is32Bit (CmmMachOp (MO_And w) [CmmMachOp (MO_Not w') [y], x]) + | w == w', Just i <- isSingleBit w y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTR x i +getRegister' _ is32Bit (CmmMachOp (MO_Or w) [x, y]) + | Just i <- isSingleBit w y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTS x i +getRegister' _ is32Bit (CmmMachOp (MO_Or w) [y, x]) + | Just i <- isSingleBit w y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTS x i +getRegister' _ is32Bit (CmmMachOp (MO_Xor w) [x, y]) + | Just i <- isSingleBit w y, bitTestOpWidthOK is32Bit w + = genBitTestCode (intFormat w) BTC x i +getRegister' _ is32Bit (CmmMachOp (MO_Xor w) [y, x]) + | Just i <- isSingleBit w y, bitTestOpWidthOK is32Bit w + = genBitTestCode (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 +5905,68 @@ 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. We only use them when the bit index is a non-literal expression: +when i is a literal, constant folding has already turned the mask into a +literal, and an ordinary and/or/xor with an immediate is at least as good. + +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@ with a non-literal @i@, returning @i@. +-- See Note [Bit-test instructions]. +isSingleBit :: Width -> CmmExpr -> Maybe CmmExpr +isSingleBit w (CmmMachOp (MO_Shl w') [CmmLit (CmmInt 1 _), i]) + | w == w', not (isLit i) = Just i + where + isLit (CmmLit {}) = True + isLit _ = False +isSingleBit _ _ = Nothing + +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) + 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,11 @@ data Instr | SHLD Format Operand{-amount-} Operand Operand | BT Format Imm Operand + -- Bit test-and-reset/set/complement; the bit offset must be an + -- immediate or a register (not memory). + | BTR Format Operand{-bit offset-} Operand + | BTS Format Operand{-bit offset-} Operand + | BTC Format Operand{-bit offset-} Operand | NOP @@ -496,6 +501,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 +838,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,3 @@ +btrq +btsq +btcq ===================================== testsuite/tests/codeGen/should_gen_asm/T25233.hs ===================================== @@ -0,0 +1,16 @@ +{-# 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) ===================================== 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/8ff2e0e01d9e6f4f2f786b2ec846e92f... -- View it on GitLab: https://gitlab.haskell.org/ghc/ghc/-/commit/8ff2e0e01d9e6f4f2f786b2ec846e92f... You're receiving this email because of your account on gitlab.haskell.org.