+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: !16639

+issues: #27688

+-- 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)

+

+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)) != 0      ==>     bt i, x; jc

+  x & ~(1 << i)            ==>     btr i, x

+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).

+indices 7..30.  Likewise a single-bit test keeps 'test' with an immediate:

+test+jcc macro-fuse into one uop, bt+jcc do not.

+(exactly one bit clear resp. set) and emit bt/btr/bts/btc with an immediate

+-- | 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.

+-- | 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.

+        -- | Bit test

+        | BT          Format Operand{- ^ bit offset (imm/reg) -} Operand

+    BT     fmt off src    -> mkRUR (use_R fmt off $! use_R fmt src [])

+    BT   fmt off src     -> patch2 (BT  fmt) off src

+   BT format off src

+      -> pprFormatOpOp (text "bt") format off src

+btq %

+btl %

+btq $40,

+{-# 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#

+btq %

+setc

+setae

+btq $40,

+#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);

+}

+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, ''])