#9340: Implement new `clz` inline primop -------------------------------------+------------------------------------- Reporter: hvr | Owner: Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: primop clz (CodeGen) | Operating System: Unknown/Multiple Resolution: | Type of failure: None/Unknown Differential Revisions: | Test Case: Architecture: | Blocking: Unknown/Multiple | Difficulty: Unknown | Blocked By: | Related Tickets: | -------------------------------------+------------------------------------- Old description:

From a draft for #9281, I had to use a C FFI and using a gcc/clang `__builtin` to get access to the [http://en.wikipedia.org/wiki/Find_first_set CLZ instruction]:

{{{#!hs -- | Compute base-2 log of 'Word#' ​-- ​-- This is internally implemented as count-leading-zeros machine instruction. ​foreign import ccall unsafe "integer_gmp_word_log2" wordLog2# :: Word# -> Int# }}}

{{{#!c HsWord integer_gmp_word_log2(HsWord x) ​{ ​#if (SIZEOF_HSWORD) == (SIZEOF_INT) ​ return x ? (WORD_SIZE_IN_BITS-1) - __builtin_clz(x) : -1; ​#elif (SIZEOF_HSWORD) == (SIZEOF_LONG) ​ return x ? (WORD_SIZE_IN_BITS-1) - __builtin_clzl(x) : -1; ​#elif (SIZEOF_HSWORD) == (SIZEOF_LONG_LONG) ​ return x ? (WORD_SIZE_IN_BITS-1) - __builtin_clzll(x) : -1; ​#else ​# error unsupported SIZEOF_HSWORD ​#endif ​} }}}

Since a `clz`-like operation should be available on most cpus GHC should expose that as a primop ({{{clz# :: Word# -> Int#}}}).

New description: From a draft for #9281, I had to use a C FFI and using a gcc/clang `__builtin` to get access to the [http://en.wikipedia.org/wiki/Find_first_set CLZ instruction]: {{{#!hs -- | Compute base-2 log of 'Word#' -- -- This is internally implemented as count-leading-zeros machine instruction. foreign import ccall unsafe "integer_gmp_word_log2" wordLog2# :: Word# -> Int# }}} {{{#!c HsWord integer_gmp_word_log2(HsWord x) { #if (SIZEOF_HSWORD) == (SIZEOF_INT) return x ? (WORD_SIZE_IN_BITS-1) - __builtin_clz(x) : -1; #elif (SIZEOF_HSWORD) == (SIZEOF_LONG) return x ? (WORD_SIZE_IN_BITS-1) - __builtin_clzl(x) : -1; #elif (SIZEOF_HSWORD) == (SIZEOF_LONG_LONG) return x ? (WORD_SIZE_IN_BITS-1) - __builtin_clzll(x) : -1; #else # error unsupported SIZEOF_HSWORD #endif } }}} Since a `clz`-like operation should be available on most cpus GHC should expose that as a primop ({{{clz# :: Word# -> Int#}}}). -- Comment (by hvr): (remove hidden Unicode characters in code blocks) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9340#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9340: Implement new `clz` inline primop -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: patch request | Milestone: 7.10.1 Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: primop clz (CodeGen) | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D144 | -------------------------------------+------------------------------------- Changes (by hvr): * status: new => patch * differential: => Phab:D144 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9340#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9340: Implement new `clz` inline primop -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: patch request | Milestone: 7.10.1 Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: primop clz (CodeGen) | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D144 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"3669b60cb0b24e22563bfe624aab4aba369cbfca/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="3669b60cb0b24e22563bfe624aab4aba369cbfca" Add bit scan {forward,reverse} insns to x86 NCG This is a pre-requisite for implementing count-{leading,trailing}-zero prim-ops (re #9340) Reviewers: ezyang, rwbarton, simonmar, austin Subscribers: simonmar, relrod, ezyang, carter Differential Revision: https://phabricator.haskell.org/D141 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9340#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9340: Implement new `clz` inline primop -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: primop clz ctz (CodeGen) | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D144 | -------------------------------------+------------------------------------- Changes (by hvr): * keywords: primop clz => primop clz ctz * status: patch => closed * resolution: => fixed Comment: I consider this ticket resolved. The next step will be to expose those primops via `Data.Bits` (see Phab:D158 for a draft-patch which still needs to go through the library proposal process) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9340#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9340: Implement new `clz` inline primop -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: primop clz ctz (CodeGen) | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #9532 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D144 | -------------------------------------+------------------------------------- Changes (by hvr): * related: => #9532 Comment: See #9532 for the related `Data.Bits` CLZ/CTZ interface ticket -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9340#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9340: Implement new `clz` inline primop -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: primop clz ctz (CodeGen) | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #9532 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D144 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"612f3d120c65a461a4ad7f212d67bdae005f4975/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="612f3d120c65a461a4ad7f212d67bdae005f4975" Implement optimized NCG `MO_Ctz W64` op for i386 (#9340) Summary: This is an optimization to the CTZ primops introduced for #9340 Previously we called out to `hs_ctz64`, but we can actually generate better hand-tuned code while avoiding the FFI ccall. With this patch, the code {-# LANGUAGE MagicHash #-} module TestClz0 where import GHC.Prim ctz64 :: Word64# -> Word# ctz64 x = ctz64# x results in the following assembler generated by NCG on i386: TestClz.ctz64_info: movl (%ebp),%eax movl 4(%ebp),%ecx movl %ecx,%edx orl %eax,%edx movl $64,%edx je _nAO bsf %ecx,%ecx addl $32,%ecx bsf %eax,%eax cmovne %eax,%ecx movl %ecx,%edx _nAO: movl %edx,%esi addl $8,%ebp jmp *(%ebp) For comparision, here's what LLVM 3.4 currently generates: 000000fc : fc: 0f bc 45 04 bsf 0x4(%ebp),%eax 100: b9 20 00 00 00 mov $0x20,%ecx 105: 0f 45 c8 cmovne %eax,%ecx 108: 83 c1 20 add $0x20,%ecx 10b: 8b 45 00 mov 0x0(%ebp),%eax 10e: 8b 55 08 mov 0x8(%ebp),%edx 111: 0f bc f0 bsf %eax,%esi 114: 85 c0 test %eax,%eax 116: 0f 44 f1 cmove %ecx,%esi 119: 83 c5 08 add $0x8,%ebp 11c: ff e2 jmp *%edx Reviewed By: austin Auditors: simonmar Differential Revision: https://phabricator.haskell.org/D163 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9340#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler