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, () #)
$wa_r3UQ =
  \ (ww_s3TD :: GHC.Prim.Char#)
    (w_s3TA :: GHC.Prim.State# GHC.Prim.RealWorld) ->
    case ww_s3TD of _ {
      __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
}}}
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
   :: GHC.Prim.Char#
      -> GHC.Prim.State# GHC.Prim.RealWorld
      -> (# GHC.Prim.State# GHC.Prim.RealWorld, () #)
 $wa_r3UQ =
   \ (ww_s3TD :: GHC.Prim.Char#)
     (w_s3TA :: GHC.Prim.State# GHC.Prim.RealWorld) ->
     case ww_s3TD of _ {
       __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:3
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler