#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