#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: | -------------------------------------+------------------------------------- Comment (by simonpj): Sounds useful to me. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14206#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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

#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: | -------------------------------------+------------------------------------- Comment (by newhoggy): Okay, successfully built master. Can start working on a patch. I'll base it on the popcnt patch. Question: Do I need a new ghc flag? gcc uses -mbmi2 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14206#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Comment (by newhoggy): I thought to use `-mbmi2` because there are already a bunch of `-m` flags. Would that be fine? {{{#!haskell ------ Machine dependent (-m<blah>) stuff --------------------------- , make_ord_flag defGhcFlag "msse" (noArg (\d -> d { sseVersion = Just SSE1 })) , make_ord_flag defGhcFlag "msse2" (noArg (\d -> d { sseVersion = Just SSE2 })) , make_ord_flag defGhcFlag "msse3" (noArg (\d -> d { sseVersion = Just SSE3 })) , make_ord_flag defGhcFlag "msse4" (noArg (\d -> d { sseVersion = Just SSE4 })) , make_ord_flag defGhcFlag "msse4.2" (noArg (\d -> d { sseVersion = Just SSE42 })) , make_ord_flag defGhcFlag "mavx" (noArg (\d -> d { avx = True })) , make_ord_flag defGhcFlag "mavx2" (noArg (\d -> d { avx2 = True })) , make_ord_flag defGhcFlag "mavx512cd" (noArg (\d -> d { avx512cd = True })) , make_ord_flag defGhcFlag "mavx512er" (noArg (\d -> d { avx512er = True })) , make_ord_flag defGhcFlag "mavx512f" (noArg (\d -> d { avx512f = True })) , make_ord_flag defGhcFlag "mavx512pf" (noArg (\d -> d { avx512pf = True })) }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14206#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14206: Add bit deposit and bit extraction primops -------------------------------------+------------------------------------- Reporter: newhoggy | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: fixed | 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: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => closed * resolution: => fixed * milestone: => 8.4.1 Comment: Thanks newhoggy! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14206#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14206: Add bit deposit and bit extraction primops -------------------------------------+------------------------------------- Reporter: newhoggy | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: fixed | 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Given that we had agreed to merge this for 8.4 I've merged it for the next alpha. Thanks again for sticking with this newhoggy! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14206#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler