[GHC] #14226: Common Block Elimination pass doesn't eliminate common blocks
#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: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- 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. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226> 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: | -------------------------------------+------------------------------------- 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 bgamari): Oh, actually, never mind. On further reflection I suppose CBE actually must look at local registers since they may be live across blocks. Indeed nomeata's patch was merely a change in the hash, which is an optimization, not a change in the behavior of the pass. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:2> 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): Well, because we have an extremely narrow definition of "common". Namely, to be the same two blocks must be syntactically identical, including local register names. I don't know how often this happens in practice, but I'd imagine not terribly often. I think the criterion that you would ideally want is equivalence up to alpha renaming of local registers; unfortunately this would likely be considerably more costly to check for. This makes me wonder whether we shouldn't just try to avoid duplicating the blocks to begin with (e.g. addressing #14222 earlier in the compilation pipeline). -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:4> 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 bgamari): To make my objection in comment:4 more concrete, consider that you have the following two blocks (from the example in #14226), {{{ c2VZ: // global _c2Yd::I64 = _s2Se::I64 + 1; _s2Sx::I64 = _c2Yd::I64; _s2Se::I64 = _s2Sx::I64; goto c2TE; c2VY: // global _c2Yb::I64 = _s2Se::I64 + 1; _s2Sw::I64 = _c2Yb::I64; _s2Se::I64 = _s2Sw::I64; goto c2TE; }}} They differ in only two local register names, both of which are dead outside of their respective blocks. Ignoring the fact that the sinking pass should eliminate both intermediate locals, it seems to me like CBE should really consider these blocks to be duplicates. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:6> 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: | Differential Rev(s): Phab:D3973 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch * differential: => Phab:D3973 Comment: Phab:D3973 implements the equivalence-up-to-alpha-renaming idea described above. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:8> 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 Ben Gamari <ben@…>): In [changeset:"7920a7d9c53083b234e060a3e72f00b601a46808/ghc" 7920a7d/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="7920a7d9c53083b234e060a3e72f00b601a46808" cmm/CBE: Collapse blocks equivalent up to alpha renaming of local registers As noted in #14226, the common block elimination pass currently implements an extremely strict equivalence relation, demanding that two blocks are equivalent including the names of their local registers. This is quite restrictive and severely hampers the effectiveness of the pass. Here we allow the CBE pass to collapse blocks which are equivalent up to alpha renaming of locally-bound local registers. This is completely safe and catches many more duplicate blocks. Test Plan: Validate Reviewers: austin, simonmar, michalt Reviewed By: michalt Subscribers: rwbarton, thomie GHC Trac Issues: #14226 Differential Revision: https://phabricator.haskell.org/D3973 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:10> 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 -------------------------------------+------------------------------------- Changes (by bgamari): * differential: Phab:D3973 => Phab:D3973, Phab:D3999 Comment: Suggestion in comment:11 done in Phab:D3999. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:12> 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 <ben@…>): 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: 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: patch => closed * resolution: => fixed Comment: This should now be resolved. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:14> 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 nomeata): I see these two blocks not being commoned up: {{{ c4bx: // global I64[_s3Yp::P64] = stg_MUT_ARR_PTRS_FROZEN0_info; // CmmStore _s3YJ::P64 = _s3Yp::P64; // CmmAssign _s3YJ::P64 = _s3YJ::P64; // CmmAssign I64[Hp - 48] = GHC.Types.I#_con_info; // CmmStore I64[Hp - 40] = _s3Yj::I64; // CmmStore _c4bX::P64 = Hp - 47; // CmmAssign I64[Hp - 32] = GHC.Arr.Array_con_info; // CmmStore P64[Hp - 24] = Database.idatabase1_closure+1; // CmmStore P64[Hp - 16] = _c4bX::P64; // CmmStore P64[Hp - 8] = _s3YJ::P64; // CmmStore I64[Hp] = _s3Yq::I64; // CmmStore _c4bY::P64 = Hp - 31; // CmmAssign _s3YW::P64 = _c4bY::P64; // CmmAssign goto c4b9; // CmmBranch }}} and {{{ c4bD: // global I64[_s3Yp::P64] = stg_MUT_ARR_PTRS_FROZEN0_info; // CmmStore _s3Yy::P64 = _s3Yp::P64; // CmmAssign _s3Yy::P64 = _s3Yy::P64; // CmmAssign I64[Hp - 48] = GHC.Types.I#_con_info; // CmmStore I64[Hp - 40] = _s3Yj::I64; // CmmStore _c4bZ::P64 = Hp - 47; // CmmAssign I64[Hp - 32] = GHC.Arr.Array_con_info; // CmmStore P64[Hp - 24] = Database.idatabase1_closure+1; // CmmStore P64[Hp - 16] = _c4bZ::P64; // CmmStore P64[Hp - 8] = _s3Yy::P64; // CmmStore I64[Hp] = _s3Yq::I64; // CmmStore _c4c0::P64 = Hp - 31; // CmmAssign _s3YW::P64 = _c4c0::P64; // CmmAssign goto c4b9; // CmmBranch }}} Should they? Does maybe the `_s3YJ::P64 = _s3YJ::P64;` throw CBE off? (This is from nofib’s `fem` with commit d871321ce20e – not sure how useful this commit ID is, as it is from a rebasing branch and so far it only lives on Phabricator.) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:16> 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 bgamari): Indeed it's hard to say much without knowing with certainty that this is the code that CBE looks at. That being said, I believe that the CBE implementation should be able to deal with `CmmAssign`s of the form `x=x` since it compares the RHSs up to alpha equivalence. It would of course be good to check this, however. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:18> 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 bgamari): Interesting; would you like to investigate or should I? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:20> 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: closed Priority: high | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 (CodeGen) | Keywords: newcomer, Resolution: fixed | 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 simonpj): * keywords: newcomer => newcomer, CodeGen Comment: What's the status here? -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:22> 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: (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 michalt): * cc: michalt (added) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:24> 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 -------------------------------------+------------------------------------- Changes (by bgamari): * related: #9157 => #9157, #14754 Comment: Sadly I'll need to revert the above patches due to #14754. I'll have another look at this post-8.4. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:26> 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 <ben@…>): 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 michalt): :( I can currently think of two options: 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 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). -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:28> 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.
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.
2) Don't improve CBE itself, but run it a second time after the sinking 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: 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 michalt): Replying to [comment:29 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.
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.
2) Don't improve CBE itself, but run it a second time after the sinking 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.
I did a small experiment with this: https://ghc.haskell.org/trac/ghc/ticket/12915#comment:5 (I'm wondering if we could improve the CBE to be a bit cheaper, e.g., by improving hashing) -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:30> 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 <ben@…>): In [changeset:"4e513bf758c32804fc71b98215f96e8481697a36/ghc" 4e513bf/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="4e513bf758c32804fc71b98215f96e8481697a36" CBE: re-introduce bgamari's fixes During some recent work on CBE we discovered that `zipWith` is used to check for equality, but that doesn't quite work if lists are of different lengths! This was fixed by bgamari, but unfortunately the fix had to be rolled back due to other changes in CBE in 50adbd7c5fe5894d3e6e2a58b353ed07e5f8949d. Since I wanted to have another look at CBE anyway, we agreed that the first thing to do would be to re-introduce the fix. Sadly I don't have any actual test case that would exercise this. Signed-off-by: Michal Terepeta <michal.terepeta@gmail.com> Test Plan: ./validate Reviewers: bgamari, simonmar Reviewed By: bgamari Subscribers: rwbarton, thomie, carter GHC Trac Issues: #14226 Differential Revision: https://phabricator.haskell.org/D4387 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:32> 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 <ben@…>): 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 <michal.terepeta@gmail.com> 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: | -------------------------------------+------------------------------------- Changes (by AndreasK): * related: #9157, #14754 => #9157, #14754, #14989 Comment: For anyone wondering this has been reverted because of issues with ProcPoint invariants. See #14989 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14226#comment:35> 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
participants (1)
-
GHC