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

2 Mar 2015

      #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):

 Would could go further and expect
 {{{
 f =
   \ a_s3EH ->
     case a_s3EH of _ { I# ds_s3EJ ->
     case ds_s3EJ of _ {
       __DEFAULT -> x;
       1 -> y;
       5 -> y;
       8 -> y;
       9 -> y;
       11 -> y;
       19 -> y
     }
     }
 }}}
 to be replaced by
 {{{
 f =
   \ a_s3EH ->
     case a_s3EH of _ { I# ds_s3EJ ->
     let p! = some_branchless_formula_involving ds_s3EJ
     case p of _ {
       __DEFAULT -> x;
       1 -> y;
     }
     }
 }}}
 where `some_branchless_formula_involving` could be any expression that is
 `1` for `1,5,8,9,11,19` – whether it is a disjunction of equalities or
 some fancy bit-fiddling magic.

 Even more general, how about turning
 {{{
 f =
   \ a_s3EH ->
     case a_s3EH of _ { I# ds_s3EJ ->
     case ds_s3EJ of _ {
       __DEFAULT -> x;
       1 -> y;
       5 -> y;
       8 -> z;
       9 -> y;
       11 -> z;
       19 -> z
     }
     }
 }}}
 into
 {{{
 f =
   \ a_s3EH ->
     case a_s3EH of _ { I# ds_s3EJ ->
     let p! = some_branchless_formula_involving ds_s3EJ
     case p of _ {
       __DEFAULT -> x;
       1 -> y;
       2 -> z;
     }
     }
 }}}

 This would generate one branch per unique right-hand-side of a `->`,
 instead of one branch per literal matched against.

 Not sure if Core is the right place for this, though – it feels more like
 instruction selection in the code generator.

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