[GHC] #14206: Add bit deposit and bit extraction primops

[GHC]

#14206: Add bit deposit and bit extraction primops
-------------------------------------+-------------------------------------
        Reporter:  newhoggy          |                Owner:  (none)
            Type:  feature request   |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.2.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------
Description changed by newhoggy:

Old description:

> Modern CPUs (on x86, Haswell and newer) have a PDEP instruction for
> efficient bit deposit and a PEXT instruction for efficient bit
> extraction. These instructions can be used to implement various data
> structures.
>
> I propose we add the following set of primops
>
> {{{#!hs
> pdep8#  :: Word#   -> Word#   -> Word#
> pdep16# :: Word#   -> Word#   -> Word#
> pdep32# :: Word#   -> Word#   -> Word#
> pdep64# :: Word64# -> Word64# -> Word64#
> pdep#   :: Word#   -> Word#   -> Word#
>
> pext8#  :: Word#   -> Word#   -> Word#
> pext16# :: Word#   -> Word#   -> Word#
> pext32# :: Word#   -> Word#   -> Word#
> pext64# :: Word64# -> Word64# -> Word64#
> pext#   :: Word#   -> Word#   -> Word#
> }}}
>
> Each primop compiles into either a single PDEP/PEXT instruction or a call
> to some fallback function, implemented in C.
>
> For reference, see the following library that implements FFI wrapper
> 32-bit and 64-bit functions for these instructions:
>
> https://github.com/haskell-works/hw-prim-bits

New description:

 Modern CPUs (on x86, Haswell and newer) have a PDEP instruction for
 efficient bit deposit and a PEXT instruction for efficient bit extraction.
 These instructions can be used to implement various data structures.

 I propose we add the following set of primops

 {{{#!hs
 pdep8#  :: Word#   -> Word#   -> Word#
 pdep16# :: Word#   -> Word#   -> Word#
 pdep32# :: Word#   -> Word#   -> Word#
 pdep64# :: Word64# -> Word64# -> Word64#
 pdep#   :: Word#   -> Word#   -> Word#

 pext8#  :: Word#   -> Word#   -> Word#
 pext16# :: Word#   -> Word#   -> Word#
 pext32# :: Word#   -> Word#   -> Word#
 pext64# :: Word64# -> Word64# -> Word64#
 pext#   :: Word#   -> Word#   -> Word#
 }}}

 Each primop compiles into either a single PDEP/PEXT instruction or a call
 to some fallback function, implemented in C.

 For reference, see the following library that implements FFI wrapper for
 32-bit and 64-bit functions for these instructions:

 https://github.com/haskell-works/hw-prim-bits

--

-- 
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14206#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler