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

3 Oct 2014

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

Comment (by dfeuer):

 Replying to [comment:1 jstolarek]:
...
After some thinking I don't think it's constant folding but more
 generally the special rules for `==#`. As promised here are some hints how
 to get started on this one:
1. Try to reproduce the problem with a simpler example, eg. using only
 two comparison primops and `orI#`. Try out different combinations of
 comparison primops. See also whether this happens for `andI#`. We want to
 be sure that this only depends on presence of `==#` and not other
 operators (don't forget `/=#`).
This happens with both `==#` and `/=#`. It does not appear to happen with
 the others. Furthermore, it appears to happen only when one of the
 arguments is known at compile time.
...
2. Once you have a smaller test case follow the transformation that GHC
 is performing to arrive at the result. Is it turning the simpler test case
 into the final result in one step or are there any intermediate steps?
There are intermediate steps, but it starts very early. For example,

 {{{#!hs
 --Desugar
 equals0AndEquals2
 equals0AndEquals2 =
   \ x_a1wL y_a1wM -> andI# (==# x_a1wL 0) (==# y_a1wM 2)

 == Gentle simplification ==>

 equals0AndEquals2
 equals0AndEquals2 =
   \ x_a1wL y_a1wM ->
     andI#
       (case x_a1wL of _ {
          __DEFAULT -> 0;
          0 -> 1
        })
       (case y_a1wM of _ {
          __DEFAULT -> 0;
          2 -> 1
        })

 -- Nothing changes for a bit ....
 == Simplifier phase 2 ==>

 equals0AndEquals2
 equals0AndEquals2 =
   \ x_a1wL y_a1wM ->
     case x_a1wL of _ {
       __DEFAULT -> 0;
       0 ->
         case y_a1wM of _ {
           __DEFAULT -> 0;
           2 -> 1
         }
     }
...
3. My guess would be that the culprit is `litEq` function in
 `PrelRules.lhs` module. The comment above it claims to do exactly what
 you've reported here. However, I'm not sure what the fix should be.
 Disabling this is probably not a good idea, since in some cases we really
 want that transformation to happen. We'd need to think more but first
 let's confirm whether `litEq` is the cause or not. You can verify that by
 disabling that rule and seeing whether the code compiles without branches.
I'm confident you're right, but I won't have time to do that experiment
 until after Yom Kippur. The comment says

 {{{
 -- 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
 }}}

 There are a couple `tagToEnum#` invocations missing there, but let's look
 at the whole process. We're presumably starting with

 {{{#!hs
 if (n == 3) || (n == 4) then e1 else e2
 }}}

 Expanding `if`,

 {{{#!hs
 case (n == 3) || (n == 4) of
   True -> e1
   False -> e2
 }}}

 Expanding `(||)`,

 {{{#!hs
 case (case n == 3 of {True -> True; False -> n == 4}) of
   True -> e1
   False -> e2
 }}}

 Case of case gets us

 {{{#!hs
 case n == 3 of
   True -> case True of {True -> e1; False -> e2}
   False -> case n == 4 of {True -> e1; False -> e2}
 }}}

 Case of known constructor or whatever it's called produces

 {{{#!hs
 case n == 3 of
   True -> e1
   False -> case n == 4 of
              True -> e1
              False -> e2
 }}}

 So we can get this far without knowing anything about what `(==)` means.
 Now let's add part of that knowledge:
 {{{#!hs
 case n# ==# 3# of
   1# -> e1
   0# -> case n# ==# 4# of
           1# -> e1
           0# -> e2
 }}}

 In this case, this is probably just fine, but I imagine the example is
 intended to suggest that there are (perhaps many) more tests, so that a
 different pattern matching strategy may be in order. I would venture to
 guess that what we want to do is attack it at this stage—recognizing that
 we're looking at nested case of `==#` with a shared operand.

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