Opened 8 years ago

Last modified 2 years ago

#5344 new feature request

CSE should look through coercions

Reported by: reinerp Owned by:
Priority: low Milestone:
Component: Compiler Version: 7.0.3
Keywords: CSE Cc: slyfox
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

This is probably a known limitation of the CSE pass, but there doesn't appear to be a ticket so I'll make one.

Consider the module:

module M where

newtype Id a = Id a

f (a, b) = (Id a, b)

g (a, b) = (a, b)

Compiling this with ghc -ddump-simpl -dsuppress-all -O2, we get

g = \ (@ t_adf) (@ t1_adg) (ds_ddl :: (t_adf, t1_adg)) -> ds_ddl

f =
  \ (@ t_adi) (@ a_adj) (ds_ddn :: (a_adj, t_adi)) ->
    case ds_ddn of _ { (a_aaW, b_aaX) -> (a_aaW `cast` ..., b_aaX) }

We see that g shares its argument tuple, but f allocates a new copy of it. Ideally f would also share its argument tuple, and would look like this:

f = \ (@ t_adi) (@ a_adj) (ds_ddn :: (a_adj, t_adi)) -> ds_ddn `cast` ...

Change History (8)

comment:1 Changed 8 years ago by igloo

Milestone: 7.6.1
Owner: set to simonpj

Simon, does this seem feasible?

comment:2 Changed 8 years ago by simonpj

Milestone: 7.6.1_|_

You want to answer the question "Are these two expressions e1, e2 equal modulo a coercion, so that e1 = e2 |> co?" I'm sure it's possible to do that, but I don't see how to do it efficiently.

Nice idea, though!

I'll milestone for bottom unless someone comes up with a plausible implementation.

Simon

comment:3 Changed 4 years ago by slyfox

Cc: slyfox added

comment:4 Changed 3 years ago by nomeata

Resolution: duplicate
Status: newclosed

I think this is covered as good as it can be for now by doing CSE on STG, where the coercion is gone (see #9291).

comment:5 Changed 3 years ago by rwbarton

Hah, you confused me by writing this comment before updating #9291 :)

This example seems easier than the original example in #9291 though, since f can be expressed using a cast as a well-typed program in the current Core language. All else being equal, it seems better to do the CSE earlier rather than later, though I'm not sure whether it makes an actual difference in practice.

comment:6 Changed 3 years ago by nomeata

Indeed it is easier as it can done by task. But I still believe type-changing CSE on the Core level is a research paper quality problem (and an interesting one!). We could keep this ticket open for that point in the design space, so if you want, feel free to reopen.

comment:7 Changed 3 years ago by rwbarton

Owner: simonpj deleted
Priority: normallow
Resolution: duplicate
Status: closednew

OK, I think reopening (with milestone _|_) is appropriate then. Also setting priority to low in view of this case being handled by #9291; to be re-raised if someone comes up with a compelling reason to do the CSE earlier.

comment:8 Changed 2 years ago by ezyang

Keywords: CSE added; cse removed
Note: See TracTickets for help on using tickets.