[GHC] #13282: Introduce fast path through simplifier for static bindings
#13282: Introduce fast path through simplifier for static bindings -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: Component: Compiler | Version: 8.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Compile-time Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- 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, a. Forbidding data cons in the head of a RULE's LHS b. Check the rule-base for matching rules matching a datacon as "static" -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13282 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13282: Introduce fast path through simplifier for static bindings -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * owner: (none) => bgamari -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13282#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13282: Introduce fast path through simplifier for static bindings -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (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. {{{#!hs a :: [Maybe a] a = [Nothing] }}} desugars to {{{#!hs 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? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13282#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13282: Introduce fast path through simplifier for static bindings -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (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. 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. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13282#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13282: Introduce fast path through simplifier for static bindings -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (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. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13282#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13282: Introduce fast path through simplifier for static bindings -------------------------------------+------------------------------------- Reporter: bgamari | Owner: bgamari Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (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. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13282#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC