[GHC] #14206: Add bit deposit and bit extraction primops
#14206: Add bit deposit and bit extraction primops -------------------------------------+------------------------------------- Reporter: newhoggy | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- 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 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14206> 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 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: | -------------------------------------+------------------------------------- Comment (by bgamari): Indeed, it would be great to have these operations available. newhoggy, are you interested in offering a patch? I would be happy to advise. Let me know via email or IRC if you want to chat. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14206#comment:2> 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:
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): Yes, I'm interested in offering a patch, but I'm very new to this. Before I can make a contribution, I need a working build from source don't I? Starting there. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14206#comment:4> 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 bgamari): Yes, let's follow gcc. However, for better or worse GHC uses `-f` flags for machine characteristics (although perhaps this should change in the long-term). Perhaps just use `-fbmi2`? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14206#comment:6> 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: 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 Ben Gamari <ben@…>): In [changeset:"f5dc8ccc29429d0a1d011f62b6b430f6ae50290c/ghc" f5dc8ccc/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="f5dc8ccc29429d0a1d011f62b6b430f6ae50290c" Add new mbmi and mbmi2 compiler flags This adds support for the bit deposit and extraction operations provided by the BMI and BMI2 instruction set extensions on modern amd64 machines. Test Plan: Validate Reviewers: austin, simonmar, bgamari, hvr, goldfire, erikd Reviewed By: bgamari Subscribers: goldfire, erikd, trommler, newhoggy, rwbarton, thomie GHC Trac Issues: #14206 Differential Revision: https://phabricator.haskell.org/D4063 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14206#comment:8> 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 Ben Gamari <ben@…>): In [changeset:"f855769690eb998ea25818ee794714957852af48/ghc" f8557696/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="f855769690eb998ea25818ee794714957852af48" Add new mbmi and mbmi2 compiler flags This adds support for the bit deposit and extraction operations provided by the BMI and BMI2 instruction set extensions on modern amd64 machines. Implement x86 code generator for pdep and pext. Properly initialise bmiVersion field. pdep and pext test cases Fix pattern match for pdep and pext instructions Fix build of pdep and pext code for 32-bit architectures Test Plan: Validate Reviewers: austin, simonmar, bgamari, angerman Reviewed By: bgamari Subscribers: trommler, carter, angerman, thomie, rwbarton, newhoggy GHC Trac Issues: #14206 Differential Revision: https://phabricator.haskell.org/D4236 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14206#comment:10> 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
participants (1)
-
GHC