CSE should deal with letrec

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.

Trac metadata

Trac field	Value
Version	7.8.2
Type	FeatureRequest
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture

changed weight to 5

added Tfeature request Trac import labels

changed title from Merge identical top-level expressions following simplification when it is safe to do so to CSE 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

Trac metadata

Trac field	Value
TypeOfFailure	OtherFailure → RuntimePerformance

closed

commit 55efc971

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!

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

reopened

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.

Trac metadata

Trac field	Value
Resolution	ResolvedFixed → Unresolved

added CSE label

assigned to @RolandSenn

I'll try to add the missing regression test.

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

Trac metadata

Trac field	Value
Test case	- → T9441
Differential revisions	- → D5038

Trac metadata

Trac field	Value
Test case	T9441 → T9441a, T9441b, T9441c

mentioned in commit ec49b42b

closed

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

reopened

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

Trac metadata

Trac field	Value
Resolution	ResolvedFixed → Unresolved

See: https://phabricator.haskell.org/D5076

Trac metadata

Trac field	Value
Differential revisions	D5038 → D5038, D5076

mentioned in commit a08b285f

closed

Trac metadata

Trac field	Value
Resolution	Unresolved → ResolvedFixed

added Pnormal label