Re: [GHC] #9661: Branchless ==# is compiled to branchy code

13 Oct 2014

      #9661: Branchless ==# is compiled to branchy code
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  feature     |           Status:  new
  request                            |        Milestone:
              Priority:  normal      |          Version:  7.9
             Component:  Compiler    |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Unknown
  Unknown/Multiple                   |       Blocked By:
       Type of failure:  Runtime     |  Related Tickets:
  performance bug                    |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 As Jan says, `n ==# 3#` is transformed into a case expression by `litEq`.
 The comment says
 {{{
 -- This stuff turns
 --      n ==# 3#
 -- into
 --      case n of
 --        3# -> True
 --        m  -> False
 --
 -- This is a Good Thing, because it allows case-of case things
 -- to happen, and case-default absorption to happen.  For
 -- example:
 --
 --      if (n ==# 3#) || (n ==# 4#) then e1 else e2
 -- will transform to
 --      case n of
 --        3# -> e1
 --        4# -> e1
 --        m  -> e2
 }}}
 So a chain of equality comparisons will turn into a table-driven jump in
 the end, which is a good thing.  On the other hand, generating branch
 nests is a bad thing.

 Arguably, the Big Reason for wanting the tables is for source programs
 like this:
 {{{
 f 0# = e1
 f 1# = e2
 f 2# = e3
 ...
 f _ = en
 }}}
 Here we really would like to generate a single case with many
 alternatives.  When compiled, without `litEq`, it'd look like
 {{{
 f x = case (x ==# 0#) of
         1# -> e1  -- True branch
         _  -> case (x ==# 1#) of
                 1# -> e2  -- True branch
                 _ -> ..etc..
 }}}
 (I'm omitting the annoying `tagToEnum` clutter, see #6135.)

 So perhaps `litEq` should apply only ''when in the context of a `case`
 expression that immediately scrutinises its result''.  So `litEq` would
 become
 {{{
    case (a ==# k) of 1# -> e1; _ -> e2
 --->
    case a of { k -> e1; _ -> e2 }
 }}}
 Annoyingly, the `CoreSyn.RuleFun` API for built-in rules does not give
 access to the context of an application (the `SimplCont`), but it would
 not be hard to make it do so.

 So if that is the right rewrite, then it'd be another useful project for
 someone.

 Simon

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9661#comment:12
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler