[GHC] #10124: Simple case analyses generate too many branches

[GHC]

#10124: Simple case analyses generate too many branches
-------------------------------------+-------------------------------------
        Reporter:  bgamari           |                   Owner:
            Type:  bug               |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler          |                 Version:  7.8.4
      Resolution:                    |                Keywords:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |               Test Case:
      Blocked By:                    |                Blocking:
 Related Tickets:  #6135, #9661      |  Differential Revisions:
-------------------------------------+-------------------------------------

Comment (by nomeata):

 >  I'd agree that it seems better to avoid breaking up the case expression
 to begin with.

 Not sure if that helps, after all, we want to have good code even when the
 user writes a case statement to begin with:

 {{{
 myIsSpace ' ' = True
 myIsSpace '\n' = True
 myIsSpace '\t' = True
 myIsSpace _ = False
 }}}

 I would expect the compiler to (try to) create optimal code from this
 specification, whether it’s a linear list of condition, an if-then-else-
 tree or a jump table.


 I looked at the CG, which even has a pass to unify the common branches,
 but we need CMM first, so we have to generate some assembly. We currently
 unconditionally generate an if-then-else tree there, so it is hard to
 rewrite that into something smarter.

 Maybe the way forward would be to implement this todo from 11 years ago:
 {{{
 emitCmmLitSwitch :: CmmExpr                    -- Tag to switch on
                -> [(Literal, CmmAGraphScoped)] -- Tagged branches
                -> CmmAGraphScoped              -- Default branch (always)
                -> FCode ()                     -- Emit the code
 -- Used for general literals, whose size might not be a word,
 -- where there is always a default case, and where we don't know
 -- the range of values for certain.  For simplicity we always generate a
 tree.
 --
 -- ToDo: for integers we could do better here, perhaps by generalising
 -- mk_switch and using that.  --SDM 15/09/2004
 }}}

 For `emitCmmSwitch` there is already a case that generates a `CmmSwitch`
 statement, used when compiling to C. So we might want to try to create a
 `switch` statement also in `emitCmmLitSwitch` when compiling via LLVM, to
 leave it to the compiler.

 If we emit a switch statement in `emitCmmLitSwitch` unconditionally, then
 we can run the common block transformation first, and later, in a separate
 step replace the `CmmSwitch` by a tree of if-then-else statements, or by
 some branchless code, or whatever looks best by then. For LLVM, we might
 simply leave it as a switch statement.

 In order to do so, the type of `CmmSwitch` would have to support sparse
 switch statements better – it currently takes a `[Maybe Label]`.

 (Disclaimer: I don’t know much about code generation. If I’m not helpful
 here, just tell me :-))

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