Implement new CLZ and CTZ primops (re #9340)

Authored by hvr.
Tags
None
Subscribers
None
Tokens
"Evil Spooky Haunted Tree" token, awarded by austin.

Description

Implement new CLZ and CTZ primops (re Trac #9340)

This implements the new primops

clz#, clz32#, clz64#,
ctz#, ctz32#, ctz64#

which provide efficient implementations of the popular
count-leading-zero and count-trailing-zero respectively
(see testcase for a pure Haskell reference implementation).

On x86, NCG as well as LLVM generates code based on the BSF/BSR
instructions (which need extra logic to make the 0-case well-defined).

Test Plan: validate and succesful tests on i686 and amd64

Reviewers: rwbarton, simonmar, ezyang, austin

Subscribers: simonmar, relrod, ezyang, carter

Differential Revision: https://phabricator.haskell.org/D144

GHC Trac Issues: Trac #9340

Details

Group Auditors
Restricted Owners Package
Restricted Owners Package
Committed
hvrAug 14 2014, 4:34 AM
Differential Revision
D144: Implement new CLZ and CTZ primops (re #9340)
Parents
rGHC6b5ea617dcd1: Remove out of date TODO
Branches
Unknown
Tags
Unknown
Build Status
Buildable 440
Build 441: GHC Continuous Integration (amd64/Linux)