Opened 3 years ago

Last modified 2 years ago

#13282 new feature request

Introduce fast path through simplifier for static bindings

Reported by: bgamari Owned by: bgamari
Priority: normal Milestone:
Component: Compiler Version: 8.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

It's not uncommon for early simplifier runs to float out a large number of "static data" bindings from a user program to the top-level. Here we will consider a top-level binding to be "static" if its RHS consists of a data constructor applied to zero or more other static bindings. This floating is quite helpful as static top-levels are represented easily as static code in object code. It also opens an interesting possibility: we know (with a few potential caveats discussed later) no further simplification of these bindings is possible.

However, the simplifier currently does not take advantage of this latter fact: currently the simplifier will dutifully rebuild all bindings on every iteration. This work is wasted effort.

I think it would be helpful to track the "static-ness" of top-level bindings and teach the simplifier and various analyses to ignore bindings so-marked.

Also, there is one caveat here: it is currently possible for users to write rules whose LHSs are headed by a data constructor. This means that further simplification of the bindings which we deemed above as "static" is possible. There are two ways of dealing with this,

  1. Forbidding data cons in the head of a RULE's LHS
  2. Check the rule-base for matching rules matching a datacon as "static"

Change History (5)

comment:1 Changed 3 years ago by bgamari

Owner: set to bgamari

comment:2 Changed 3 years ago by rwbarton

Here we will consider a top-level binding to be "static" if its RHS consists of a data constructor applied to zero or more other static bindings.

Minor amendments:

  • I think you only intend to allow saturated data constructor applications; though I'm not sure.
  • Literals should also be considered static.
  • What about type applications of polymorphic data constructors to type variables? E.g.
a :: [Maybe a]
a = [Nothing]

desugars to

a :: forall a. [Maybe a]
a = \ (@ a1) -> : @ (Maybe a1) (Nothing @ a1) ([] @ (Maybe a1))

and it's static in the sense that it will be represented by static closures; but at the Core level, it involves a type variable a1. Do you consider this "static" in your sense?

comment:3 Changed 3 years ago by bgamari

Minor amendments:

  • I think you only intend to allow saturated data constructor applications; though I'm not sure.
  • Literals should also be considered static.

Yes, I should have been more precise. I believe the right check is exprIsConLike_maybe and verifying that all of the value arguments are themselves binders or literals.

What about type applications of polymorphic data constructors to type variables? E.g.

That is an interesting point; I think there is a reasonable argument to be made for considering type lambdas as static as well. There is also an argument for casts and coercions.

This isn't what the patch (which has been a bit trickier than I thought due to unfoldings getting zapped in various unexpected places) currently implements though.

Last edited 3 years ago by bgamari (previous) (diff)

comment:4 Changed 2 years ago by dfeuer

Ben, what's the status of the patch currently? Can you put it up on Phabricator and link here? Now that rules on datacons are banned, this should be safe to do.

comment:5 Changed 2 years ago by bgamari

The patch is the wip/simplifier-static branch in my GitHub fork. I can't remember the precise status, but I do recall that the numbers weren't terribly promising.

Note: See TracTickets for help on using tickets.