[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,
>
> {{{#!hs
> $wa_r3UQ
>   :: GHC.Prim.Char#
>      -> GHC.Prim.State# GHC.Prim.RealWorld
>      -> (# GHC.Prim.State# GHC.Prim.RealWorld, () #)
> [GblId, Arity=2, Str=DmdType <S,1*U><L,U>]
> $wa_r3UQ =
>   \ (ww_s3TD :: GHC.Prim.Char#)
>     (w_s3TA [OS=OneShot] :: GHC.Prim.State# GHC.Prim.RealWorld) ->
>     case ww_s3TD of _ [Occ=Dead] {
>       __DEFAULT -> (# w_s3TA, GHC.Tuple.() #);
>       '$' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl2_r3Uv GHC.Types.True w_s3TA;
>       '&' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl4_r3Ux GHC.Types.True w_s3TA;
>       '+' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl6_r3Uz GHC.Types.True w_s3TA;
>       ',' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl8_r3UB GHC.Types.True w_s3TA;
>       '-' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl10_r3UD GHC.Types.True w_s3TA;
>       '.' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl12_r3UF GHC.Types.True w_s3TA;
>       ':' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl14_r3UH GHC.Types.True w_s3TA;
>       '=' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl16_r3UJ GHC.Types.True w_s3TA;
>       '@' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl18_r3UL GHC.Types.True w_s3TA;
>       '_' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl20_r3UN GHC.Types.True w_s3TA;
>       '~' ->
>         GHC.IO.Handle.Text.hPutStr2
>           GHC.IO.Handle.FD.stdout lvl22_r3UP GHC.Types.True w_s3TA
>     }
> }}}
>
> 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,

 {{{#!hs
 $wa_r3UQ
   :: GHC.Prim.Char#
      -> GHC.Prim.State# GHC.Prim.RealWorld
      -> (# GHC.Prim.State# GHC.Prim.RealWorld, () #)
 [GblId, Arity=2, Str=DmdType <S,1*U><L,U>]
 $wa_r3UQ =
   \ (ww_s3TD :: GHC.Prim.Char#)
     (w_s3TA [OS=OneShot] :: GHC.Prim.State# GHC.Prim.RealWorld) ->
     case ww_s3TD of _ [Occ=Dead] {
       __DEFAULT -> (# w_s3TA, GHC.Tuple.() #);
       '$' ->
         GHC.IO.Handle.Text.hPutStr2
           GHC.IO.Handle.FD.stdout lvl2_r3Uv GHC.Types.True w_s3TA;
 ...
       '_' ->
         GHC.IO.Handle.Text.hPutStr2
           GHC.IO.Handle.FD.stdout lvl20_r3UN GHC.Types.True w_s3TA;
       '~' ->
         GHC.IO.Handle.Text.hPutStr2
           GHC.IO.Handle.FD.stdout lvl22_r3UP GHC.Types.True w_s3TA
     }
 }}}

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

--

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