#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

#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

#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 :: 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 = \ 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 }}} -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10120#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: -------------------------------------+------------------------------------- Comment (by nomeata): The GHC 7.8 code looks good to me – I would expect later stages in the pipeline to make good code from such a case on an enumeration type. Did you have a look at the actual generated code for that? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10120#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: -------------------------------------+------------------------------------- Comment (by bgamari): nomeata, This is my toy example, {{{#!hs predicate c = c == '-' || c == '_' || c == '.' || c == '~' || c == ':' || c == '@' || c == '&' || c == '=' || c == '+' || c == '$' || c == ',' f x | predicate x = print x f x = return () {-# NOINLINE f #-} main = f 'a' }}} This was derived from https://github.com/aristidb/http- types/blob/4c9fc3d136b2bc18fe126adc3902dd7e7685ae62/Network/HTTP/Types/URI.hs (in particular `urlEncodeBuilder`'s check of `unreservedPI'`. Here GHC doesn't inline the bodies but it does create a unique body for each branch of the case, {{{#!hs case ipv1_ijS6 of wild3_X1h { __DEFAULT -> ... __word 36 -> lvl_rkUl `cast` ...; __word 38 -> lvl1_rkUm `cast` ...; __word 43 -> lvl2_rkUn `cast` ...; __word 44 -> lvl3_rkUo `cast` ...; __word 45 -> lvl4_rkUp `cast` ...; __word 46 -> lvl5_rkUq `cast` ...; __word 58 -> lvl6_rkUr `cast` ...; __word 61 -> lvl7_rkUs `cast` ...; __word 64 -> lvl8_rkUt `cast` ...; __word 95 -> lvl9_rkUu `cast` ...; __word 126 -> lvl10_rkUv `cast` ... } }}} Where each of the branches looks like this, {{{#!hs lvl2_rkUn :: forall r_ij1U. Data.ByteString.Builder.Internal.BuildStep r_ij1U -> Data.ByteString.Builder.Internal.BufferRange -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, Data.ByteString.Builder.Internal.BuildSignal r_ij1U #) lvl2_rkUn = \ (@ r_ij1U) (eta_ij1V :: Data.ByteString.Builder.Internal.BuildStep r_ij1U) (eta1_ij1W :: Data.ByteString.Builder.Internal.BufferRange) (eta2_ij1X :: GHC.Prim.State# GHC.Prim.RealWorld) -> case eta1_ij1W of _ { Data.ByteString.Builder.Internal.BufferRange dt_ij27 dt1_ij28 -> case GHC.Prim.tagToEnum# (GHC.Prim.<# (GHC.Prim.minusAddr# dt1_ij28 dt_ij27) 1) of _ { False -> case GHC.Prim.writeWord8OffAddr# dt_ij27 0 (__word 43) eta2_ij1X of s2_ij40 { __DEFAULT -> ((eta_ij1V (Data.ByteString.Builder.Internal.BufferRange (GHC.Prim.plusAddr# dt_ij27 1) dt1_ij28)) `cast` ...) s2_ij40 }; True -> (# eta2_ij1X, Data.ByteString.Builder.Internal.BufferFull 1 dt_ij27 ((\ (ds_ij2P :: Data.ByteString.Builder.Internal.BufferRange) (eta3_ij2Q :: GHC.Prim.State# GHC.Prim.RealWorld) -> case ds_ij2P of _ { Data.ByteString.Builder.Internal.BufferRange dt3_ij2T dt4_ij2U -> case GHC.Prim.writeWord8OffAddr# dt3_ij2T 0 (__word 43) eta3_ij2Q of s2_ij40 { __DEFAULT -> ((eta_ij1V (Data.ByteString.Builder.Internal.BufferRange (GHC.Prim.plusAddr# dt3_ij2T 1) dt4_ij2U)) `cast` ...) s2_ij40 } }) `cast` ...) #) } } }}} differing only in the `(__word 43)` terms. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10120#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: -------------------------------------+------------------------------------- Comment (by bgamari): Well, of course there's always a `{-# NOINLINE pred #-}` pragma. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10120#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: -------------------------------------+------------------------------------- Comment (by simonpj): I don't yet understand #10124, but I've left a comment there. Meanwhile, what remains of this ticket? What do you expect/want GHC to do, under what circumstances? Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10120#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler