[GHC] #10120: Unnecessary code duplication from case analysis

[GHC]

#10120: Unnecessary code duplication from case analysis
-------------------------------------+-------------------------------------
        Reporter:  bgamari           |                   Owner:
            Type:  bug               |                  Status:  new
        Priority:  normal            |               Milestone:
       Component:  Compiler          |                 Version:  7.10.1-rc2
      Resolution:                    |                Keywords:
Operating System:  Unknown/Multiple  |            Architecture:
 Type of failure:  Runtime           |  Unknown/Multiple
  performance bug                    |               Test Case:
      Blocked By:                    |                Blocking:
 Related Tickets:                    |  Differential Revisions:
-------------------------------------+-------------------------------------
Description changed by bgamari:

Old description:

> Consider a case analysis like this,
>
> {{{#!hs
> predicate c =
>        c == '-' || c == '_' || c == '.' || c == '~' || c == ':'
>     || c == '@' || c == '&' || c == '=' || c == '+' || c == '$' || c ==
> ','
>
> f x | predicate x = do_something
> f x = do_something_else
> main = f 'a'
> }}}
>
> GHC in some cases appears to produce Core for this example by
> constructing a case analysis on `x`, replicating `do_something` in every
> branch (generated by GHC 7.10),
>
> {{{#!hs
> $wa_r3UQ =
>   \ ww_s3TC w_s3Tz ->
>     case ww_s3TC of _ {
>       __DEFAULT -> (# w_s3Tz, () #);
>       '$' -> hPutStr2 stdout lvl2_r3Uv True w_s3Tz;
>       '&' -> hPutStr2 stdout lvl4_r3Ux True w_s3Tz;
>       ...
>       '_' -> hPutStr2 stdout lvl20_r3UN True w_s3Tz;
>       '~' -> hPutStr2 stdout lvl22_r3UP True w_s3Tz
>     }
> }}}
>
> This seems to be sub-optimal for instruction cache efficiency, the number
> of branches in generated machine code, code size, and understandability
> of the resulting Core. I would have expected something like,
>
> {{{#!hs
> f x =
>     let p = pred x
>     in case p of
>           True  -> do_something
>           False -> do_something_else
> }}}

New description:

 Consider a case analysis like this,

 {{{#!hs
 predicate c =
        c == '-' || c == '_' || c == '.' || c == '~' || c == ':'
     || c == '@' || c == '&' || c == '=' || c == '+' || c == '$' || c ==
 ','

 f x | predicate x = do_something
 f x = do_something_else
 main = f 'a'
 }}}

 GHC in some cases appears to produce Core for this example by constructing
 a case analysis on `x`, replicating `do_something` in every branch
 (generated by GHC 7.10),

 {{{#!hs
 $wa_r3UQ =
   \ ww_s3TC w_s3Tz ->
     case ww_s3TC of _ {
       __DEFAULT -> (# w_s3Tz, () #);
       '$' -> hPutStr2 stdout lvl2_r3Uv True w_s3Tz;
       '&' -> hPutStr2 stdout lvl4_r3Ux True w_s3Tz;
       ...
       '_' -> hPutStr2 stdout lvl20_r3UN True w_s3Tz;
       '~' -> hPutStr2 stdout lvl22_r3UP True w_s3Tz
     }
 }}}

 In some cases where `do_something` is large this can lead to a substantial
 increase in code size.

 There are really two issues here,

  1. That a branch-y case analysis is being used for a boolean condition
  2. That `do_something` is being inlined into each branch

 This seems to be sub-optimal for instruction cache efficiency, the number
 of branches in generated machine code, and understandability of the
 resulting Core.

 I would have expected something like,

 {{{#!hs
 f x =
     let p = pred x
     in case p of
           True  -> do_something
           False -> do_something_else
 }}}

--

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