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

27 Feb 2015

      #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 ]
$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 ]
 $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