It would be nice to factor out the common tails, e.g. by branching to

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): the first tail already emitted. Branches can be expensive, so this might not be a clear win. Have you measured the effect? (You can do that without modifying GHC: Just get your hands on the assembly file, make the changes you want to see, and compare.) The other idea, detecting blocks that are equal up-to a constant, sounds fun. But again, the question is: Is it worth it? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Across an entire module I think there are quite a lot of code blocks that are byte-for-byte identical; i.e. no extra branch or "equal up to constant" required. I wonder if we could simply gather stats on the top 100 code-blocks, put them into the RTS, and use them whenever we come across one? I bet that'd be highly effective; but I do not have data to back up my claim. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

...

It would be nice to factor out the common tails, e.g. by branching to

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:2 nomeata]: the first tail already emitted.

Branches can be expensive, so this might not be a clear win. Have you

measured the effect? (You can do that without modifying GHC: Just get your hands on the assembly file, make the changes you want to see, and compare.) These will probably be short, known branches. Since more ''relevant'' code now can reside in the instruction cache, I expect less misses and no prediction failures.

The other idea, detecting blocks that are equal up-to a constant, sounds

fun. But again, the question is: Is it worth it? Well, it makes code straight-line and branchless. Eliminates jump-tables. Shrinks code size. Which one of these is a penalty? ;-) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:7 heisenbug]:

`-fcmm-elim-common-blocks` helps a bit, but many equal ones are not caught:

Turns out c-b-e is a local optimisation, i.e. per procedure. We need a global one to crack this. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): It's hard to review code without a spec, or even some input/output examples. And an overview Note to explain the goal and how the impl works would be useful. Based on a very quick look, it seems that you hope to branch from one `CmmProc` to a label in another. That's a huge thing to do, because it messes up all dataflow analyses, which expect to be able to see all the places that jump to a block (e.g. constant propagation). I'm 99% sure that you can't translate it into LLVM. Before you invest a lot more effort, can we debate the goal? There are others on ghc-devs who know about this back-end stuff. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by nomeata): * cc: nomeata (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by heisenbug): Replying to [comment:13 jp.rider63]:

What's the status of this? I'd be interested in contributing to the implementation if it's helpful.

There is a branch in my GHC fork on github: https://github.com/ggreif/ghc/tree/wip/global-cmm-cbe It does not work with `ghc --make` because the assembly files contain local labels. Concatenating all assembly files might work, but I have not tried it yet. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by jp.rider63): Yes, I was slightly confused about the CBE discussion, but it seems somewhat related. FYI, this is my [https://github.com/bos/aeson/pull/599 motivating example]. The speedup I thought was happening due to eliminating common tails actually turned out to be from (lack of) inlining on someone else's machine. Either way, I think it makes sense to benchmark performance differences and see if this change is worthwhile. Even if performance is similar, it might be worth implementing to reduce code size. For my use case, one optimization that might help more is creating lookup tables when matching on `Word8`. Maybe I'll create another ticket for that in the future. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by AndreasK): I think this can be solved in two steps: ---- Change the Cmm generation for case statements: Currently we generate cmm of the sort {{{ ... case 1: goto foo; ... foo: Register = Value return(Register) }}} Instead we could inline this when generating the switch. {{{ #include "Cmm.h" test_entry() { switch [1 .. 8] R2 { case 1 : {R1 = 0; return();} ... case 8 : {R1 = 8; return();} } } }}} From what I've seen this hopefully won't change the generated assembly since GHC does this already when compiling the switch in the cases I looked at. ---- The second step would be to change the Assembly generated to something like the listing in [comment:17 the comment above]. I imagine a way to do that would be to: * Check if * Assignments are into the same register. * The rest of the code is the same * Collect all the constants, put them into a lookup table and generate assembly that uses the lookup table like [comment:17 above]. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => CodeGen Old description:

Compile this code to CMM {{{#!hs data Small = S1 | S2 | S3 | S4 deriving (Show, Enum)

data Big = B1 | B2 | B3 | B4 | B5 | B6 | B7 | B8 | B9 | B10 deriving (Show, Enum)

{-# NOINLINE quux #-} quux B1 = 'a' quux B2 = 'b' quux B3 = 'c' quux B4 = 'd' quux B5 = 'e' quux B6 = 'f' quux B7 = 'g' quux B8 = 'h' quux B9 = 'i' quux B10 = 'j'

{-# NOINLINE qaax #-} qaax B1 = 'a' qaax B2 = 'b' qaax B3 = 'c' qaax B4 = 'd' qaax B5 = 'e'

qaax B7 = 'g' qaax B8 = 'h' qaax B9 = 'i' qaax B10 = 'j'

{-# NOINLINE foo #-} foo B1 = S1 foo B2 = S2 foo B3 = S3 foo B4 = S4

{-# NOINLINE bar #-} bar S1 = B1 bar S2 = B2 bar S3 = B3 bar S4 = B4

main = do print $ take 100000 (repeat (foo <$> [B1 .. B4])) print $ take 100000 (repeat (bar <$> [S1 .. S4])) print $ take 100000 (repeat (quux <$> [B1 .. B10])) print $ qaax B1 }}}

When `Char` or ''enum-like'' ADT is returned, I see lots of case branches, which only differ in the first instruction.

E.g. {{{ c30l: // global R1 = stg_CHARLIKE_closure+1649; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30m: // global R1 = stg_CHARLIKE_closure+1665; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; u30Z: // global if (_c30p::I64 < 9) goto c30n; else goto c30o; c30n: // global R1 = stg_CHARLIKE_closure+1681; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30o: // global R1 = stg_CHARLIKE_closure+1697; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; }}}

It would be nice to factor out the common tails, e.g. by branching to the first tail already emitted.

Bonus points for rewriting switch tables to contain the above numbers and compile to a lookup + common code.

This is what I am talking about:

{{{ c307: // global _s2ON::P64 = R1; _c30j::P64 = _s2ON::P64 & 7; switch [1 .. 7] _c30j::P64 { case 1 : goto c30d; case 2 : goto c30e; case 3 : goto c30f; case 4 : goto c30g; case 5 : goto c30h; ... }

... c30h: // global R1 = stg_CHARLIKE_closure+1617; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30g: // global R1 = stg_CHARLIKE_closure+1601; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30f: // global R1 = stg_CHARLIKE_closure+1585; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30e: // global R1 = stg_CHARLIKE_closure+1569; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30d: // global R1 = stg_CHARLIKE_closure+1553; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; }}}

There should be an array [1553, 1569, 1585, ...] and each case should be the same: {{{ R1 = stg_CHARLIKE_closure; R1 = R1 + array[tag]; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; }}}

New description: Compile this code to CMM {{{#!hs data Small = S1 | S2 | S3 | S4 deriving (Show, Enum) data Big = B1 | B2 | B3 | B4 | B5 | B6 | B7 | B8 | B9 | B10 deriving (Show, Enum) {-# NOINLINE quux #-} quux B1 = 'a' quux B2 = 'b' quux B3 = 'c' quux B4 = 'd' quux B5 = 'e' quux B6 = 'f' quux B7 = 'g' quux B8 = 'h' quux B9 = 'i' quux B10 = 'j' {-# NOINLINE qaax #-} qaax B1 = 'a' qaax B2 = 'b' qaax B3 = 'c' qaax B4 = 'd' qaax B5 = 'e' qaax B7 = 'g' qaax B8 = 'h' qaax B9 = 'i' qaax B10 = 'j' {-# NOINLINE foo #-} foo B1 = S1 foo B2 = S2 foo B3 = S3 foo B4 = S4 {-# NOINLINE bar #-} bar S1 = B1 bar S2 = B2 bar S3 = B3 bar S4 = B4 main = do print $ take 100000 (repeat (foo <$> [B1 .. B4])) print $ take 100000 (repeat (bar <$> [S1 .. S4])) print $ take 100000 (repeat (quux <$> [B1 .. B10])) print $ qaax B1 }}} When `Char` or ''enum-like'' ADT is returned, I see lots of case branches, which only differ in the first instruction. E.g. {{{ c30l: // global R1 = stg_CHARLIKE_closure+1649; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30m: // global R1 = stg_CHARLIKE_closure+1665; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; u30Z: // global if (_c30p::I64 < 9) goto c30n; else goto c30o; c30n: // global R1 = stg_CHARLIKE_closure+1681; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30o: // global R1 = stg_CHARLIKE_closure+1697; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; }}} It would be nice to factor out the common tails, e.g. by branching to the first tail already emitted. Bonus points for rewriting switch tables to contain the above numbers and compile to a lookup + common code. This is what I am talking about: {{{ c307: // global _s2ON::P64 = R1; _c30j::P64 = _s2ON::P64 & 7; switch [1 .. 7] _c30j::P64 { case 1 : goto c30d; case 2 : goto c30e; case 3 : goto c30f; case 4 : goto c30g; case 5 : goto c30h; ... } ... c30h: // global R1 = stg_CHARLIKE_closure+1617; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30g: // global R1 = stg_CHARLIKE_closure+1601; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30f: // global R1 = stg_CHARLIKE_closure+1585; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30e: // global R1 = stg_CHARLIKE_closure+1569; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; c30d: // global R1 = stg_CHARLIKE_closure+1553; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; }}} There should be an array [1553, 1569, 1585, ...] and each case should be the same: {{{ R1 = stg_CHARLIKE_closure; R1 = R1 + array[tag]; Sp = Sp + 8; call (P64[Sp])(R1) args: 8, res: 0, upd: 8; }}} See also #14666 -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14372: CMM contains a bunch of tail-merging opportunities -------------------------------------+------------------------------------- Reporter: heisenbug | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #14666 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sjakobi): * cc: sjakobi (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14372#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler