Simon Jakobi pushed to branch wip/sjakobi/T25233 at Glasgow Haskell Compiler / GHC

Commits:

9 changed files:

Changes:

  • changelog.d/ncg-x86-bit-test-instructions
    1 
    +section: compiler
    2 
    +synopsis: The x86 native code generator now uses the bit-test instructions
    3 
    +  ``btr``/``bts``/``btc`` to clear, set or complement a single bit
    4 
    +description:
    5 
    +  Cmm patterns such as ``x & ~(1 << i)``, ``x | (1 << i)`` and
    6 
    +  ``x ^ (1 << i)`` now compile to a single ``btr``/``bts``/``btc``
    7 
    +  instruction instead of a mov/shl/not/and-style sequence, matching what C
    8 
    +  compilers produce. The same applies to the literal masks that constant
    9 
    +  folding produces from these patterns when ``i`` is constant, in the cases
    10 
    +  where the mask doesn't fit in an imm32 operand.
    11 
    +
    12 
    +  For a variable bit index this applies only when the shift is unchecked,
    13 
    +  as with ``uncheckedShiftL#`` or ``Data.Bits.unsafeShiftL``. The
    14 
    +  bounds-checked ``shiftL`` — used, for example, by the default
    15 
    +  implementations of ``clearBit``, ``setBit`` and ``complementBit`` —
    16 
    +  wraps the shift in a bounds mask that this optimisation does not see
    17 
    +  through. With a literal index, the bounds mask is constant-folded away,
    18 
    +  so the checked operations benefit too.
    19 
    +mrs: !16311
    20 
    +issues: #25233

  • compiler/GHC/CmmToAsm/X86/CodeGen.hs
    ... ... @@ -1442,6 +1442,22 @@ getRegister' platform is32Bit (CmmMachOp mop [x]) = do -- unary MachOps
    1442 1442 
                                         (PUNPCKLQDQ fmt (OpReg dst) dst)
    1443 1443 
                                         )
    1444 1444
    1445 
    +-- Use the bit-test instructions btr/bts/btc for clearing, setting and
    1446 
    +-- complementing a single bit: e.g. x .&. complement (1 `shiftL` i) is btr.
    1447 
    +-- See Note [Bit-test instructions].
    1448 
    +getRegister' platform is32Bit (CmmMachOp (MO_And w) [x, y])
    1449 
    +  | bitTestOpWidthOK is32Bit w
    1450 
    +  , Just (opnd, ix) <- clearBitArgs_maybe platform w x y
    1451 
    +  = genBitTestCode (intFormat w) BTR opnd ix
    1452 
    +getRegister' platform is32Bit (CmmMachOp (MO_Or w) [x, y])
    1453 
    +  | bitTestOpWidthOK is32Bit w
    1454 
    +  , Just (opnd, ix) <- setBitArgs_maybe platform w x y
    1455 
    +  = genBitTestCode (intFormat w) BTS opnd ix
    1456 
    +getRegister' platform is32Bit (CmmMachOp (MO_Xor w) [x, y])
    1457 
    +  | bitTestOpWidthOK is32Bit w
    1458 
    +  , Just (opnd, ix) <- setBitArgs_maybe platform w x y
    1459 
    +  = genBitTestCode (intFormat w) BTC opnd ix
    1460 
    +
    1445 1461 
     getRegister' platform is32Bit (CmmMachOp mop [x, y]) = do -- dyadic MachOps
    1446 1462 
       sse4_1 <- sse4_1Enabled
    1447 1463 
       sse4_2 <- sse4_2Enabled
    ... ... @@ -5883,6 +5899,140 @@ genTrivialCode rep instr a b = do
    5883 5899 
                     instr b_op dst
    5884 5900 
       return (Any rep code)
    5885 5901
    5902 
    +{- Note [Bit-test instructions]
    5903 
    +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    5904 
    +x86 has dedicated instructions for clearing (btr), setting (bts) and
    5905 
    +complementing (btc) a single bit whose index is given in a register.  We use
    5906 
    +them for Cmm patterns such as
    5907 
    +
    5908 
    +  x & ~(1 << i)     ==>     btr i, x       (#25233)
    5909 
    +
    5910 
    +replacing a mov/shl/not/and sequence with a single instruction.  The
    5911 
    +shift-count register operand of shl is masked modulo the operand width, and
    5912 
    +the bit-offset register operand of btr/bts/btc is masked the same way, so
    5913 
    +the replacement is faithful even for out-of-range i (where the Cmm shift is
    5914 
    +in any case undefined).
    5915 
    +
    5916 
    +The bit-offset operand of these instructions must be an immediate or a
    5917 
    +register.  When the bit index is a literal, no shift reaches the NCG:
    5918 
    +constant folding has already turned the whole mask into a literal.  If that
    5919 
    +mask fits in an imm32, we keep the ordinary and/or/xor with an immediate:
    5920 
    +it has the same latency and better throughput (more execution ports) than
    5921 
    +the bit-test instructions,  and at worst two bytes of extra code size for bit
    5922 
    +indices 7..30.
    5923 
    +But a W64 mask touching the upper bits, e.g. ~(1 << 40), would have to be moved
    5924 
    +into a register first.  For such masks we recognise the folded literal itself
    5925 
    +(exactly one bit clear resp. set) and emit btr/bts/btc with an immediate
    5926 
    +bit offset.
    5927 
    +
    5928 
    +We restrict the pattern to W32 and native-width W64: the instructions do not
    5929 
    +exist at width 8, and sub-word Cmm operations at W8/W16 are rare enough that
    5930 
    +they are not worth the extra care.
    5931 
    +-}
    5932 
    +
    5933 
    +-- | Match @1 << i@, returning @i@.
    5934 
    +--
    5935 
    +-- The returned expression is always at word width ('machOpArgReps' fixes
    5936 
    +-- shift amounts at 'wordWidth'). See Note [Bit-test instructions].
    5937 
    +singleBit_maybe :: CmmExpr -> Maybe CmmExpr
    5938 
    +singleBit_maybe (CmmMachOp (MO_Shl _) [CmmLit (CmmInt 1 _), i]) = Just i
    5939 
    +singleBit_maybe _ = Nothing
    5940 
    +
    5941 
    +-- | If exactly one bit of @m@, taken at width @w@, is set, return its index.
    5942 
    +--
    5943 
    +-- See Note [Bit-test instructions].
    5944 
    +setBitLit_maybe :: Width -> Integer -> Maybe Int
    5945 
    +setBitLit_maybe w m
    5946 
    +  | popCount m' == 1 = Just (countTrailingZeros m')
    5947 
    +  | otherwise        = Nothing
    5948 
    +  where
    5949 
    +    -- w <= W64 in this X86-specific code, so a Word64 suffices.
    5950 
    +    m' = fromInteger (narrowU w m) :: Word64
    5951 
    +
    5952 
    +-- | If exactly one bit of @m@, taken at width @w@, is clear, return its
    5953 
    +-- index.
    5954 
    +--
    5955 
    +-- See Note [Bit-test instructions].
    5956 
    +clearBitLit_maybe :: Width -> Integer -> Maybe Int
    5957 
    +clearBitLit_maybe w m = setBitLit_maybe w (complement m)
    5958 
    +
    5959 
    +bitTestOpWidthOK :: Bool -> Width -> Bool
    5960 
    +bitTestOpWidthOK is32Bit w = w == W32 || (w == W64 && not is32Bit)
    5961 
    +
    5962 
    +-- | The bit-offset operand of a bit-test instruction (btr/bts/btc).
    5963 
    +data BitIndex
    5964 
    +  = BitIndexReg CmmExpr  -- ^ variable index, computed into a register
    5965 
    +  | BitIndexImm Int      -- ^ literal index, emitted as an immediate
    5966 
    +
    5967 
    +-- | Match the operands of a single-bit set or complement operation: one
    5968 
    +-- operand is a mask @1 << i@, or a literal with exactly one bit set that
    5969 
    +-- does not fit in an imm32. Returns the other operand and the bit index.
    5970 
    +--
    5971 
    +-- Both operand orders are matched: constant folding canonicalizes literals
    5972 
    +-- to the right (see 'GHC.Cmm.Opt.cmmMachOpFoldM'), but e.g. hand-written
    5973 
    +-- .cmm code reaches the NCG unfolded.
    5974 
    +--
    5975 
    +-- See Note [Bit-test instructions].
    5976 
    +setBitArgs_maybe :: Platform -> Width -> CmmExpr -> CmmExpr
    5977 
    +                 -> Maybe (CmmExpr, BitIndex)
    5978 
    +setBitArgs_maybe platform w x y = go x y `mplus` go y x
    5979 
    +  where
    5980 
    +    go opnd mask
    5981 
    +      | Just i <- singleBit_maybe mask
    5982 
    +      = Just (opnd, BitIndexReg i)
    5983 
    +      | CmmLit lit@(CmmInt m _) <- mask
    5984 
    +      , Just i <- setBitLit_maybe w m
    5985 
    +      , not (is32BitLit platform lit)
    5986 
    +      = Just (opnd, BitIndexImm i)
    5987 
    +      | otherwise
    5988 
    +      = Nothing
    5989 
    +
    5990 
    +-- | As 'setBitArgs_maybe', for a single-bit clear operation: the mask is
    5991 
    +-- @~(1 << i)@, or a literal with exactly one bit clear.
    5992 
    +clearBitArgs_maybe :: Platform -> Width -> CmmExpr -> CmmExpr
    5993 
    +                   -> Maybe (CmmExpr, BitIndex)
    5994 
    +clearBitArgs_maybe platform w x y = go x y `mplus` go y x
    5995 
    +  where
    5996 
    +    go opnd mask
    5997 
    +      | CmmMachOp (MO_Not _) [b] <- mask
    5998 
    +      , Just i <- singleBit_maybe b
    5999 
    +      = Just (opnd, BitIndexReg i)
    6000 
    +      | CmmLit lit@(CmmInt m _) <- mask
    6001 
    +      , Just i <- clearBitLit_maybe w m
    6002 
    +      , not (is32BitLit platform lit)
    6003 
    +      = Just (opnd, BitIndexImm i)
    6004 
    +      | otherwise
    6005 
    +      = Nothing
    6006 
    +
    6007 
    +-- | Generate code for @dst := x@ followed by a bit-test instruction
    6008 
    +-- (btr/bts/btc).
    6009 
    +--
    6010 
    +-- See Note [Bit-test instructions].
    6011 
    +genBitTestCode :: Format -> (Format -> Operand -> Operand -> Instr)
    6012 
    +               -> CmmExpr -> BitIndex -> NatM Register
    6013 
    +genBitTestCode rep instr x (BitIndexImm i) = do
    6014 
    +  x_code <- getAnyReg x
    6015 
    +  let code dst = x_code dst `snocOL` instr rep (OpImm (ImmInt i)) (OpReg dst)
    6016 
    +  return (Any rep code)
    6017 
    +genBitTestCode rep instr x (BitIndexReg i) = do
    6018 
    +  (i_reg, i_code) <- getNonClobberedReg i
    6019 
    +  x_code <- getAnyReg x
    6020 
    +  tmp <- getNewRegNat rep
    6021 
    +  let
    6022 
    +     -- As in genTrivialCode, 'i' must stay alive across the computation of
    6023 
    +     -- 'x' into dst, so save it in a temporary if dst holds 'i'.
    6024 
    +     code dst
    6025 
    +        | dst == i_reg =
    6026 
    +                i_code `appOL`
    6027 
    +                unitOL (MOV rep (OpReg i_reg) (OpReg tmp)) `appOL`
    6028 
    +                x_code dst `snocOL`
    6029 
    +                instr rep (OpReg tmp) (OpReg dst)
    6030 
    +        | otherwise =
    6031 
    +                i_code `appOL`
    6032 
    +                x_code dst `snocOL`
    6033 
    +                instr rep (OpReg i_reg) (OpReg dst)
    6034 
    +  return (Any rep code)
    6035 
    +
    5886 6036 
     regClashesWithOp :: Reg -> Operand -> Bool
    5887 6037 
     reg `regClashesWithOp` OpReg reg2   = reg == reg2
    5888 6038 
     reg `regClashesWithOp` OpAddr amode = any (==reg) (addrModeRegs amode)

  • compiler/GHC/CmmToAsm/X86/Instr.hs
    ... ... @@ -193,6 +193,12 @@ data Instr
    193 193 
             | SHLD        Format Operand{-amount-} Operand Operand
    194 194
    195 195 
             | BT          Format Imm Operand
    196 
    +        -- | Bit test-and-reset
    197 
    +        | BTR         Format Operand{- ^ bit offset (imm/reg) -} Operand
    198 
    +        -- | Bit set
    199 
    +        | BTS         Format Operand{- ^ bit offset (imm/reg) -} Operand
    200 
    +        -- | Bit complement
    201 
    +        | BTC         Format Operand{- ^ bit offset (imm/reg) -} Operand
    196 202 
             | NOP
    197 203
    198 204
    ... ... @@ -496,6 +502,9 @@ regUsageOfInstr platform instr
    496 502 
         SHLD   fmt imm dst1 dst2 -> usageRMM fmt imm dst1 dst2
    497 503 
         SHRD   fmt imm dst1 dst2 -> usageRMM fmt imm dst1 dst2
    498 504 
         BT     fmt _   src    -> mkRUR (use_R fmt src [])
    505 
    +    BTR    fmt off dst    -> usageRM fmt off dst
    506 
    +    BTS    fmt off dst    -> usageRM fmt off dst
    507 
    +    BTC    fmt off dst    -> usageRM fmt off dst
    499 508
    500 509 
         PUSH   fmt op         -> mkRUR (use_R fmt op [])
    501 510 
         POP    fmt op         -> mkRU [] (def_W fmt op)
    ... ... @@ -830,6 +839,9 @@ patchRegsOfInstr platform instr env
    830 839 
         SHLD fmt imm dst1 dst2 -> patch2 (SHLD fmt imm) dst1 dst2
    831 840 
         SHRD fmt imm dst1 dst2 -> patch2 (SHRD fmt imm) dst1 dst2
    832 841 
         BT   fmt imm src     -> patch1 (BT  fmt imm) src
    842 
    +    BTR  fmt off dst     -> patch2 (BTR fmt) off dst
    843 
    +    BTS  fmt off dst     -> patch2 (BTS fmt) off dst
    844 
    +    BTC  fmt off dst     -> patch2 (BTC fmt) off dst
    833 845 
         TEST fmt src dst     -> patch2 (TEST fmt) src dst
    834 846 
         CMP  fmt src dst     -> patch2 (CMP  fmt) src dst
    835 847 
         PUSH fmt op          -> patch1 (PUSH fmt) op

  • compiler/GHC/CmmToAsm/X86/Ppr.hs
    ... ... @@ -862,6 +862,15 @@ pprInstr platform i = case i of
    862 862 
        BT format imm src
    863 863 
           -> pprFormatImmOp (text "bt") format imm src
    864 864
    865 
    +   BTR format off dst
    866 
    +      -> pprFormatOpOp (text "btr") format off dst
    867 
    +
    868 
    +   BTS format off dst
    869 
    +      -> pprFormatOpOp (text "bts") format off dst
    870 
    +
    871 
    +   BTC format off dst
    872 
    +      -> pprFormatOpOp (text "btc") format off dst
    873 
    +
    865 874 
        CMP format src dst
    866 875 
          | isFloatFormat format -> pprFormatOpOp (text "ucomi") format src dst -- SSE2
    867 876 
          | otherwise            -> pprFormatOpOp (text "cmp")   format src dst

  • testsuite/tests/codeGen/should_gen_asm/T25233.asm
    1 
    +btrq
    2 
    +btsq
    3 
    +btcq
    4 
    +btrl
    5 
    +btsl
    6 
    +btcl
    7 
    +btrq $40,
    8 
    +btsq $40,
    9 
    +btcq $40,

  • testsuite/tests/codeGen/should_gen_asm/T25233.hs
    1 
    +{-# LANGUAGE MagicHash #-}
    2 
    +
    3 
    +-- Check that clearing/setting/complementing a single, variable bit
    4 
    +-- uses the btr/bts/btc instructions (#25233).
    5 
    +module T25233 where
    6 
    +
    7 
    +import GHC.Exts
    8 
    +
    9 
    +myClearBit :: Word# -> Int# -> Word#
    10 
    +myClearBit x i = x `and#` not# (1## `uncheckedShiftL#` i)
    11 
    +
    12 
    +mySetBit :: Word# -> Int# -> Word#
    13 
    +mySetBit x i = x `or#` (1## `uncheckedShiftL#` i)
    14 
    +
    15 
    +myComplementBit :: Word# -> Int# -> Word#
    16 
    +myComplementBit x i = x `xor#` (1## `uncheckedShiftL#` i)
    17 
    +
    18 
    +myClearBit32 :: Word32# -> Int# -> Word32#
    19 
    +myClearBit32 x i =
    20 
    +  x `andWord32#` notWord32# (wordToWord32# 1## `uncheckedShiftLWord32#` i)
    21 
    +
    22 
    +mySetBit32 :: Word32# -> Int# -> Word32#
    23 
    +mySetBit32 x i = x `orWord32#` (wordToWord32# 1## `uncheckedShiftLWord32#` i)
    24 
    +
    25 
    +myComplementBit32 :: Word32# -> Int# -> Word32#
    26 
    +myComplementBit32 x i =
    27 
    +  x `xorWord32#` (wordToWord32# 1## `uncheckedShiftLWord32#` i)
    28 
    +
    29 
    +-- With a constant bit index >= 32, the mask constant-folds to a literal
    30 
    +-- that does not fit in an imm32, so a bit-test instruction with an
    31 
    +-- immediate offset is used.
    32 
    +myClearBit40 :: Word# -> Word#
    33 
    +myClearBit40 x = x `and#` not# (1## `uncheckedShiftL#` 40#)
    34 
    +
    35 
    +mySetBit40 :: Word# -> Word#
    36 
    +mySetBit40 x = x `or#` (1## `uncheckedShiftL#` 40#)
    37 
    +
    38 
    +myComplementBit40 :: Word# -> Word#
    39 
    +myComplementBit40 x = x `xor#` (1## `uncheckedShiftL#` 40#)

  • testsuite/tests/codeGen/should_gen_asm/T25233b.asm
    1 
    +btrq $40,
    2 
    +btsq $40,
    3 
    +btcq $40,

  • testsuite/tests/codeGen/should_gen_asm/T25233b.cmm
    1 
    +#include "Cmm.h"
    2 
    +
    3 
    +// Single-bit literal masks written on the left of the operator. Constant
    4 
    +// folding canonicalizes literals to the right, so these shapes only reach
    5 
    +// the NCG from hand-written Cmm like this (#25233).
    6 
    +
    7 
    +clearBit40 (W_ x) {
    8 
    +    return ((0xFFFFFEFFFFFFFFFF :: bits64) & x);
    9 
    +}
    10 
    +
    11 
    +setBit40 (W_ x) {
    12 
    +    return ((0x10000000000 :: bits64) | x);
    13 
    +}
    14 
    +
    15 
    +complementBit40 (W_ x) {
    16 
    +    return ((0x10000000000 :: bits64) ^ x);
    17 
    +}

  • testsuite/tests/codeGen/should_gen_asm/all.T
    ... ... @@ -23,6 +23,10 @@ test('avx512-int64-minmax', [unless(arch('x86_64'), skip),
    23 23 
                                  when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-mavx512vl'])
    24 24 
     test('avx512-word64-minmax', [unless(arch('x86_64'), skip),
    25 25 
                                   when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-mavx512vl'])
    26 
    +test('T25233', [unless(arch('x86_64'), skip),
    27 
    +                when(unregisterised(), skip)], compile_grep_asm, ['hs', True, '-O'])
    28 
    +test('T25233b', [unless(arch('x86_64'), skip),
    29 
    +                 when(unregisterised(), skip)], compile_grep_asm, ['cmm', True, ''])
    26 30 
     is_aarch64_codegen = [
    27 31 
         unless(arch('aarch64'), skip),
    28 32 
         when(unregisterised(), skip),

    • —
    View it on GitLab.
    You're receiving this email because of your account on gitlab.haskell.org. Manage all notifications · Help Notification message regarding https://gitlab.haskell.org/ghc/ghc/-/commit/05c9684dd907f81aaff6e42e5e16e45c01e36738 at 1788351301