#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | 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: | -------------------------------------+------------------------------------- Old description:

In #14222 it was noted that something appears to be broken in `CmmCommonBlockElim`. Consider the program from that ticket, {{{#!hs module T14221 where

import Data.Text as T

isNumeric :: Text -> Bool isNumeric t = T.all isNumeric' t && T.any isNumber t where isNumber c = '0' <= c && c <= '9' isNumeric' c = isNumber c || c == 'e' || c == 'E' || c == '.' || c == '-' || c == '+' }}} This program produces six copies of a block of the form, {{{#!c c6JT: R2 = I64[R1 + 7]; R1 = P64[Sp + 8]; Sp = Sp + 16; call $wloop_all_s6CQ_info(R2, R1) args: 8, res: 0, upd: 8; }}} in the `-ddump-opt-cmm` output, which are manifest in the assembler as, {{{#!asm block_c6JT_info: _c6JT: movq 7(%rbx),%r14 movq 8(%rbp),%rbx addq $16,%rbp jmp $wloop_all_s6CQ_info }}}

CBE really ought to be catching these.

New description: In #14222 it was noted that something appears to be broken in `CmmCommonBlockElim`. Consider the program from that ticket, {{{#!hs module T14221 where import Data.Text as T isNumeric :: Text -> Bool isNumeric t = T.all isNumeric' t && T.any isNumber t where isNumber c = '0' <= c && c <= '9' isNumeric' c = isNumber c || c == 'e' || c == 'E' || c == '.' || c == '-' || c == '+' }}} This program produces six copies of a block of the form, {{{ c6JT: R2 = I64[R1 + 7]; R1 = P64[Sp + 8]; Sp = Sp + 16; call $wloop_all_s6CQ_info(R2, R1) args: 8, res: 0, upd: 8; }}} in the `-ddump-opt-cmm` output, which are manifest in the assembler as, {{{#!asm block_c6JT_info: _c6JT: movq 7(%rbx),%r14 movq 8(%rbp),%rbx addq $16,%rbp jmp $wloop_all_s6CQ_info }}} CBE really ought to be catching these. -- Comment (by bgamari): I had a quick look at this; it turns out that the reason that CBE doesn't work is 73f836f5d57a3106029b573c42f83d2039d21d89, which modifies the hash function to include local registers. This may sound familiar to you, nomeata, as you wrote it to address #10397. Sadly this means that our ability to CBE is quite limited. It seems like we should likely revisit this decision. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | 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): OK, so now we are back to: why doesn't CBE eliminate the common blocks? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | 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 bgamari): One option would be to run CBE **after** register allocation; this would make it significantly more likely that two structurally similar blocks would look similar to CBE. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | 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): OK, got it. Yes, totally. CBE should be insensitive to alpha-renaming of local register. One way to do this would be for the hashing function to be sensitive to binding sites. Concretely, suppose that we had {{{ hashInstrs :: HashEnv -> [Instruction] -> HashCode type HashEnv = (Map LocalReg HashCode, Int) }}} Now we could have {{{ hashInstrs (env, next) (Load reg expr : instrs) = hashInstrs (extendEnv env reg next, next+1) instrs `hashPlus` hashExpr env expr ... hashExpr env (LocalReg r) | Just hc <- lookupEnv env r = hc | otherwise = hashLocalReg r -- as now }}} The mapping tells what hashcode to use for a local register. We deBruijn- number all binding sites as we come across them, mapping them to 1, 2, 3, etc. Now we'll be insensitive to what name is chosen. I think we already have a function that, for an instruction, says what local regs it assigns to. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: patch Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * related: => #9157 Comment: It turns out this was also previously reported as #9157. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: patch Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973 Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Ben I forgot to mention this. In `CmmExpr` you'll find `foldLocalRegsDefd`, which is, I think, precisely what you need to answer the question "which local regs does this node define". It would be much better to use it than to duplicate the logic into `hash_node` and `eqMiddleWith`. Might you look at doing that? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: patch Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"9aa73892e10e90a1799b9277da593e816a827364/ghc" 9aa73892/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="9aa73892e10e90a1799b9277da593e816a827364" cmm/CBE: Use foldLocalRegsDefd Simonpj suggested this as a follow-on to #14226 to avoid code duplication. This also gives us the ability to CBE cases involving foreign calls for free. Test Plan: Validate Reviewers: austin, simonmar, simonpj Reviewed By: simonpj Subscribers: michalt, simonpj, rwbarton, thomie GHC Trac Issues: #14226 Differential Revision: https://phabricator.haskell.org/D3999 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: closed Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Changes (by bgamari): * keywords: => newcomer -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: closed Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Comment (by michalt): Replying to [comment:16 nomeata]:

[...] Should they? Does maybe the `_s3YJ::P64 = _s3YJ::P64;` throw CBE off?

Hmm.. Interesting. I'd expect that with the recent patch from bgamari this should be commoned up. Is this the final cmm or is it the input to `CmmCommonBlockElim`? (asking because sometimes the sinking pass can expose more opportunities for `CmmCommonBlockElim`, but we run sinking pass *after* eliminating common blocks; example: #12915) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:17 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: closed Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Comment (by nomeata): It’s the ouptut of `-ddump-cmm-cbe` -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: closed Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Resolution: fixed | Keywords: newcomer Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Comment (by AndreasK): Replying to [comment:14 bgamari]:

This should now be resolved.

Rather, I think we could improve the `switch` lowering: currently we lower this as a chain of branches. I suspect this is the sort of case where we might benefit from instead using a jump table.

Measuring this idea and, if it pays off, implementing it might be an interesting project for someone looking to get their hands dirty in the NCG.

According to the comments in `CmmSwitch.hs` jump tables only make sense when the gaps between entries are smaller than 7 and the table has at least 5 elements which isn't the case here. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: | CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Changes (by bgamari): * status: closed => new * resolution: fixed => Comment: I've not yet investigated but I can certainly do so. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: bug | Status: new Priority: high | Milestone: 8.6.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: | CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Changes (by bgamari): * owner: (none) => bgamari * milestone: 8.4.1 => 8.6.1 Comment: I'll need to take a look at this. Unfortunately it likely won't happen before 8.4.1. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: bug | Status: new Priority: high | Milestone: 8.6.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: | CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157, #14754 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"50adbd7c5fe5894d3e6e2a58b353ed07e5f8949d/ghc" 50adbd7c/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="50adbd7c5fe5894d3e6e2a58b353ed07e5f8949d" cmm: Revert more aggressive CBE due to #14226 Trac #14226 noted that the C-- CBE pass frequently fails to common up semantically identical blocks due to the differences in local register naming. These patches fixed this by making the pass consider equality up to alpha-renaming. However, the new logic failed to consider the possibility that local register naming *may* matter across multiple blocks. This lead to the regression #14754. I'll need to do a bit of thinking on a proper solution to this but in the meantime I'm reverting all four patches. This reverts commit a27056f9823f8bbe2302f1924b3ab38fd6752e37. This reverts commit 6f990c54f922beae80362fe62426beededc21290. This reverts commit 9aa73892e10e90a1799b9277da593e816a827364. This reverts commit 7920a7d9c53083b234e060a3e72f00b601a46808. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: bug | Status: new Priority: high | Milestone: 8.6.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: | CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157, #14754 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Comment (by bgamari):

1) Fix the approach using alpha renaming by actually checking liveness on entry and exit for each variable. (to only consider variables that are not live across blocks) The disadvantage is that this would be quite a bit more costly.

2) Don't improve CBE itself, but run it a second time after the sinking

Right, I briefly considered implementing this. I don't expect it will be absurdly expensive: all we need to know is which variables are mentioned in only one block. However, I do wonder how much this will actually improve code. Presumably there are cases where this will be *too* conservative. pass - this might get rid of some of the cases from this ticket (e.g., the one from comment:6) The advantage is that this would also fix #12915; the disadvantage: this might not be always as effective as option 1). Mmm, interesting idea. This would certainly be worth a try. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: michalt Type: bug | Status: new Priority: high | Milestone: 8.6.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: | CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157, #14754 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Changes (by bgamari): * owner: bgamari => michalt Comment: Happily, michalt may be looking into this later this week. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:31 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: michalt Type: bug | Status: new Priority: high | Milestone: 8.6.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: | CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157, #14754 | Differential Rev(s): Phab:D3973, Wiki Page: | Phab:D3999 -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"d5c4d46a62ce6a0cfa6440344f707136eff18119/ghc" d5c4d46a/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="d5c4d46a62ce6a0cfa6440344f707136eff18119" CmmPipeline: add a second pass of CmmCommonBlockElim The sinking pass often gets rid of unnecessary registers registers/assignements exposing more opportunities for CBE, so this commit adds a second round of CBE after the sinking pass and should fix #12915 (and some examples in #14226). Nofib results: * Binary size: 0.9% reduction on average * Compile allocations: 0.7% increase on average * Runtime: noisy, two separate runs of nofib showed a tiny reduction on average, (~0.2-0.3%), but I think this is mostly noise * Compile time: very noisy, but generally within +/- 0.5% (one run faster, one slower) One interesting part of this change is that running CBE invalidates results of proc-point analysis. But instead of re-doing the whole analysis, we can use the map that CBE creates for replacing/comparing block labels (maps a redundant label to a useful one) to update the results of proc-point analysis. This lowers the overhead compared to the previous experiment in #12915. Signed-off-by: Michal Terepeta Test Plan: ./validate Reviewers: bgamari, simonmar Reviewed By: simonmar Subscribers: rwbarton, thomie, carter GHC Trac Issues: #12915, #14226 Differential Revision: https://phabricator.haskell.org/D4417 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:33 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14226: Common Block Elimination pass doesn't eliminate common blocks -------------------------------------+------------------------------------- Reporter: bgamari | Owner: michalt Type: bug | Status: new Priority: high | Milestone: 8.8.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: | CodeGen Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9157, #14754, | Differential Rev(s): Phab:D3973, #14989 | Phab:D3999 Wiki Page: | -------------------------------------+------------------------------------- Comment (by sgraf): Note that I posted a solution in https://ghc.haskell.org/trac/ghc/ticket/14989#comment:2: Just recompute proc points after the transformation. There's no reason we couldn't have this now other than that it will probably eat more CPU time than the quick (but broken) fixup. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14226#comment:36 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler