[Git][ghc/ghc][wip/sjakobi/T25233] X86 NCG: use btr/bts/btc for single-bit operations

7 Jul 2026


      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.

    

Simon Jakobi (＠sjakobi2)

tags

participants (1)