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

[GHC]

#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:              |
-------------------------------------+-------------------------------------
Changes (by rwbarton):

 * type:  bug => feature request


Comment:

 I think GHC is doing the right thing here, or at least not the wrong
 thing.

 It's wrong to think of `(==#)` as "branchless equality". It's just a
 function whose value is `1#` if its arguments are equal, and `0#` if they
 aren't. This fact needs to be visible to GHC in order to optimize code
 like
 {{{#!hs
 f :: Int -> (Int,Int)
 f x = if x == 0        -- defined in terms of ==#
       then (x', 1)     -- here GHC can inline and then constant-fold x' to
 257
       else (x-1, x')
   where x' = 1000 * x + 257
 }}}
 and this is the purpose of the `litEq` rule. As a result, GHC may not
 output assembly containing the number of branches that you intended. This
 is the normal function of an optimizing compiler; if GHC was not free to
 replace your program with an equivalent one, then users would be forced to
 perform all kinds of optimizations by hand to get efficient code.

 I would note that this behavior is not specific to GHC. If you compile
 this C program with gcc (Debian 4.9.1-14) at optimization level `-O1` or
 higher
 {{{#!c
 void g();
 void h();
 void f(int x)
 {
   if ((x == 0) OR (x == 5))
     g();
   else
     h();
 }
 }}}
 you will get identical assembly output (with two branches, not an `or`
 instruction) whether you set `-DOR=|` or `-DOR=||`. So C does not give you
 control over branchlessness either.

 I understand that depending on the characteristics of the input, the
 "branchless" code may be faster (e.g. for the C function above, `x`
 randomly drawn from the set 0 (49%), 5 (49%), 10 (2%)). However, with
 certain other distributions of the input value, the "branchy" version is
 likely to be faster. So there is no right or wrong answer here.

 In general it takes a lot of engineering effort to get a compiler to
 reliably produce two different optimized outputs for two different
 programs that it can see are semantically identical. In this case maybe
 there is an easy solution: add a new `secretlyEquality#` which is the same
 as `(==#)`, but where that fact is hidden from GHC for long enough for
 `secretlyEquality#` to survive the stages that transform `(==#)`
 unscathed. This approach is intrinsically somewhat fragile (for example,
 the LLVM backend may introduce additional branches anyways), but it has
 the merit of ease of implementation.

 In any case, I would like to see some benchmarks showing that there are
 performance gains to be had in real programs from control over
 branchlessness before expending any effort on implementation.

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