[GHC] #9441: Merge identical top-level expressions following simplification when it is safe to do so
#9441: Merge identical top-level expressions following simplification when it is safe to do so -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Unknown | Type of failure: Blocked By: | None/Unknown Related Tickets: | Test Case: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- If I redefine {{{#!hs {-# INLINE reverse #-} reverse :: [a] -> [a] reverse xs = build $ \c n -> foldl (\a x -> x `c` a) n xs }}} and then write a couple test cases: {{{#!hs appRev xs ys = xs ++ reverse ys revAppRev xs ys = reverse xs ++ reverse ys }}} I end up getting some rather annoying code duplication (lots of stuff omitted from the following): {{{#!hs Rec { poly_go_r2v3 poly_go_r2v3 = \ @ a_a2nF ds_a2zc eta_Xl -> case ds_a2zc of _ { [] -> eta_Xl; : y_a2zh ys_a2zi -> poly_go_r2v3 ys_a2zi (: y_a2zh eta_Xl) } end Rec } reverse reverse = \ @ a_a2nF eta_B1 -> poly_go_r2v3 eta_B1 ([]) Rec { revAppRev2 revAppRev2 = \ @ a_a2y7 ds_a2zc eta_B1 -> case ds_a2zc of _ { [] -> eta_B1; : y_a2zh ys_a2zi -> revAppRev2 ys_a2zi (: y_a2zh eta_B1) } end Rec } Rec { revAppRev1 revAppRev1 = \ @ a_a2y7 ds_a2zc eta_B1 -> case ds_a2zc of _ { [] -> eta_B1; : y_a2zh ys_a2zi -> revAppRev1 ys_a2zi (: y_a2zh eta_B1) } end Rec } Rec { appRev1 appRev1 = \ @ a_a2xE ds_a2zc eta_B1 -> case ds_a2zc of _ { [] -> eta_B1; : y_a2zh ys_a2zi -> appRev1 ys_a2zi (: y_a2zh eta_B1) } end Rec } }}} The `reverse` function was inlined three times. In each case, there was no fusion, so `build` was inlined and the resulting copy of the `reverse` worker lifted to the top level. It would seem to me that once simplification is complete, it should be safe to merge all these copies into one. They are all `Rec {\ ... -> ...}` forms, so I don't think this has any potential to introduce undesirable sharing. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: Compiler | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: | Related Tickets: None/Unknown | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): The common subexpression elimination pass (CSE.lhs) doesn't deal with letrec at all, at the moment. We'd like this transformation: {{{ Rec { x = ...x... } ... Rec { y = ...y... } ===> rec { x = ...x... } ... NonRec { y = x } }}} Extending CSE to do this would be a good goal. It would make a good little project. Need to think about how to deal with mutual recursion too! (Or maybe dealing with a singleton `Rec` would do as a start.) The current CSE transform is quite compact and elegeant; I would regret some very hairy new code, and I hope there is a nice elegant way. Simon -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: new => closed * resolution: => fixed Comment: commit 55efc9718b520ef354e32c15c4b49cdfecce412f {{{ Author: Simon Peyton Jones <simonpj@microsoft.com> Date: Tue Feb 28 16:00:49 2017 -0500 Combine identical case alternatives in CSE See Note [Combine case alternatives] in CSE. This opportunity surfaced when I was was studying early inlining. It's easy (and cheap) to exploit, and sometimes makes a worthwhile saving. Reviewers: austin, bgamari Subscribers: thomie Differential Revision: https://phabricator.haskell.org/D3194 }}} This change seems to handle enough recursive cases to solve the problem in this case! -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * status: closed => new * resolution: fixed => Comment: Blimey you are right. Yes, this patch also implements CSE for recurive bindings, as described by `Note [CSE for recursive bindings]`. At least I wrote the Notes! A regression test would be good...re-opening just for that. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:4> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * keywords: => CSE -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:5> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RolandSenn): * owner: (none) => RolandSenn Comment: I'll try to add the missing regression test. -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:6> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: T9441 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | -------------------------------------+------------------------------------- Changes (by RolandSenn): * status: new => patch * testcase: => T9441 * differential: => Phab: D5038 Comment: Added missing regresssion test. See: [https://phabricator.haskell.org/D5038] -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:7> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | -------------------------------------+------------------------------------- Changes (by RolandSenn): * testcase: T9441 => T9441a, T9441b, T9441c -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:8> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Krzysztof Gogolewski <krz.gogolewski@…>): In [changeset:"ec49b42bbff4ee81c825a0facee26b13f1f297a7/ghc" ec49b42b/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="ec49b42bbff4ee81c825a0facee26b13f1f297a7" CSE should deal with letrec Summary: Add testcase for #9441 Test Plan: make test TESTS="T9441a T9441b T9441c" Reviewers: dfeuer, simonpj, thomie, austin, bgamari Reviewed By: dfeuer Subscribers: rwbarton, carter GHC Trac Issues: #9441 Differential Revision: https://phabricator.haskell.org/D5038 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:9> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | -------------------------------------+------------------------------------- Changes (by monoidal): * status: patch => closed * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:10> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | -------------------------------------+------------------------------------- Changes (by RolandSenn): * status: closed => new * owner: RolandSenn => (none) * resolution: fixed => Comment: Reopen ticket to improve the tests according to the comments of @nomeata in [https://phabricator.haskell.org/D5038] -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:11> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | -------------------------------------+------------------------------------- Changes (by RolandSenn): * owner: (none) => RolandSenn -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:12> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | D5076 -------------------------------------+------------------------------------- Changes (by RolandSenn): * status: new => patch * differential: Phab: D5038 => Phab: D5038 D5076 Comment: See: [https://phabricator.haskell.org/D5076] -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:13> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: patch Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | D5076 -------------------------------------+------------------------------------- Comment (by Krzysztof Gogolewski <krz.gogolewski@…>): In [changeset:"a08b285f74cd49196feb0f819d70ad0508689da3/ghc" a08b285f/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="a08b285f74cd49196feb0f819d70ad0508689da3" CSE should deal with letrec (#9441) Summary: Write tests with fewer lines. See comments of nomeata in https://phabricator.haskell.org/D5038. Test Plan: make test TESTS='T9441a T9441b T9441c' Reviewers: nomeata, dfeuer, bgamari Reviewed By: nomeata Subscribers: rwbarton, carter GHC Trac Issues: #9441 Differential Revision: https://phabricator.haskell.org/D5076 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:14> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#9441: CSE should deal with letrec -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: RolandSenn Type: feature request | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: fixed | Keywords: CSE Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Runtime | Test Case: T9441a, performance bug | T9441b, T9441c Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab: D5038 Wiki Page: | D5076 -------------------------------------+------------------------------------- Changes (by monoidal): * status: patch => closed * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9441#comment:15> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC