Opened 5 years ago

Closed 14 months ago

#9441 closed feature request (fixed)

CSE should deal with letrec

Reported by: dfeuer Owned by: RolandSenn
Priority: normal Milestone:
Component: Compiler Version: 7.8.2
Keywords: CSE Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case: T9441a, T9441b, T9441c
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab: D5038 D5076
Wiki Page:

Description

If I redefine

{-# 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:

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):

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.

Change History (15)

comment:1 Changed 5 years ago by simonpj

Summary: Merge identical top-level expressions following simplification when it is safe to do soCSE should deal with letrec

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.

See the CSE wiki page

Simon

Last edited 5 years ago by simonpj (previous) (diff)

comment:2 Changed 4 years ago by thomie

Type of failure: None/UnknownRuntime performance bug

comment:3 Changed 3 years ago by dfeuer

Resolution: fixed
Status: newclosed

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!

comment:4 Changed 3 years ago by simonpj

Resolution: fixed
Status: closednew

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.

comment:5 Changed 3 years ago by simonpj

Keywords: CSE added

comment:6 Changed 15 months ago by RolandSenn

Owner: set to RolandSenn

I'll try to add the missing regression test.

comment:7 Changed 15 months ago by RolandSenn

Differential Rev(s): Phab: D5038
Status: newpatch
Test Case: T9441

Added missing regresssion test. See: https://phabricator.haskell.org/D5038

comment:8 Changed 15 months ago by RolandSenn

Test Case: T9441T9441a, T9441b, T9441c

comment:9 Changed 14 months ago by Krzysztof Gogolewski <krz.gogolewski@…>

In ec49b42b/ghc:

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

comment:10 Changed 14 months ago by monoidal

Resolution: fixed
Status: patchclosed

comment:11 Changed 14 months ago by RolandSenn

Owner: RolandSenn deleted
Resolution: fixed
Status: closednew

Reopen ticket to improve the tests according to the comments of @nomeata in https://phabricator.haskell.org/D5038

comment:12 Changed 14 months ago by RolandSenn

Owner: set to RolandSenn

comment:13 Changed 14 months ago by RolandSenn

Differential Rev(s): Phab: D5038Phab: D5038 D5076
Status: newpatch

comment:14 Changed 14 months ago by Krzysztof Gogolewski <krz.gogolewski@…>

In a08b285f/ghc:

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

comment:15 Changed 14 months ago by monoidal

Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.