[GHC] #6135: Unboxed Booleans

[GHC]

#6135: Unboxed Booleans
-------------------------------------+-------------------------------------
        Reporter:  benl              |                Owner:  (none)
            Type:  feature request   |               Status:  closed
        Priority:  normal            |            Milestone:  7.8.1
       Component:  Compiler          |              Version:  7.4.1
      Resolution:  fixed             |             Keywords:  datacon-tags
Operating System:  Unknown/Multiple  |         Architecture:
                                     |  Unknown/Multiple
 Type of failure:  None/Unknown      |            Test Case:
                                     |  primops/should_run/T6135
      Blocked By:  8103, 8103        |             Blocking:
 Related Tickets:  #605              |  Differential Rev(s):
       Wiki Page:  PrimBool          |
-------------------------------------+-------------------------------------
Changes (by bgamari):

 * keywords:   => datacon-tags


Old description:

> Right now the only way to compare two integers is with primops that
> produce boxed bools:
>
> {{{
> <#  :: Int# -> Int# -> Bool
> ==# :: Int# -> Int# -> Bool
> }}}
>
> To consume the resulting {{{Bool}}} we need a case-expression, which
> introduces branches into the core IR and object code. Case expressions
> are bad in the presence of heavy inlining because case-of-case performed
> by the GHC simplifier tends to duplicate code (like in DPH and Repa
> programs). Mis-predicted branches are bad in object code because they
> stall the pipeline.
>

> Consider the following expression:
> {{{
>  case  x <# 0# || x >=# aWidth
>     || y <# 0# || y >=# aHeight of
>   True  -> ...
>   False -> ...
> }}}
>
> This is very common in array programming. Ideally, it should turn into
> some straight-line code to compute the flag, and then a single branch
> instruction once we've worked out what alternative to take. However, as
> the only way to consume the {{{Bool}}}s produced by the comparisons is to
> introduce more case expressions, we end up with *four* cases in the core
> IR.
>
> What I want is this:
> {{{
> data Bool#
> (.<#)  :: Int#  -> Int#  -> Bool#
> (.==#) :: Int#  -> Int#  -> Bool#
> (.||#) :: Bool# -> Bool# -> Bool#
>
> case    x .<# 0# .||# x .>=# aWidth
>    .||# y .<# 0# .||# y .>=# aHeight of
>  True#  -> ...
>  False# -> ...
> }}}
>
> Bool# is the type of one bit integers. I can compute with them
> algebraically and be sure that I'll get at most one branch instruction in
> the resulting object code.

New description:

 Right now the only way to compare two integers is with primops that
 produce boxed bools:

 {{{#!hs
 <#  :: Int# -> Int# -> Bool
 ==# :: Int# -> Int# -> Bool
 }}}

 To consume the resulting {{{Bool}}} we need a case-expression, which
 introduces branches into the core IR and object code. Case expressions are
 bad in the presence of heavy inlining because case-of-case performed by
 the GHC simplifier tends to duplicate code (like in DPH and Repa
 programs). Mis-predicted branches are bad in object code because they
 stall the pipeline.


 Consider the following expression:
 {{{#!hs
  case  x <# 0# || x >=# aWidth
     || y <# 0# || y >=# aHeight of
   True  -> ...
   False -> ...
 }}}

 This is very common in array programming. Ideally, it should turn into
 some straight-line code to compute the flag, and then a single branch
 instruction once we've worked out what alternative to take. However, as
 the only way to consume the {{{Bool}}}s produced by the comparisons is to
 introduce more case expressions, we end up with *four* cases in the core
 IR.

 What I want is this:
 {{{#!hs
 data Bool#
 (.<#)  :: Int#  -> Int#  -> Bool#
 (.==#) :: Int#  -> Int#  -> Bool#
 (.||#) :: Bool# -> Bool# -> Bool#

 case    x .<# 0# .||# x .>=# aWidth
    .||# y .<# 0# .||# y .>=# aHeight of
  True#  -> ...
  False# -> ...
 }}}

 Bool# is the type of one bit integers. I can compute with them
 algebraically and be sure that I'll get at most one branch instruction in
 the resulting object code.

--

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