[GHC] #15754: Move free variable computation to after STG passes
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by bgamari: Old description: New description: Currently (we believe) `CoreToStg` is responsible for computing free variables. However, later STG transformations may invalidate this information. It would make more sense to defer FV computation until the end of the STG pipeline. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * cc: osa1 (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sgraf): I was under the impression that because free vars are inherently part of the STG syntax (vs. some binder annotation like in Core), correct free variable information would be an invariant on STG terms. So the lambda lifting optimisation I implemented on STG (#9476) relies on correct free variable information being available (and makes sure to update it after the transformation). Instead of deferring computation of free variables, how about having other transformations maintain this particular invariant of STG syntax? Or introduce a `StgFV` pass that can be used by other passes if we really want to abandon that invariant, but then we could (should?) get rid of mention in syntax. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * cc: sgraf (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by osa1): * related: => #9718 Comment: So, for #9718 I'm working on a large Stg refactoring that fixes this ticket too. I'll add the detailed refactoring plan in #9718. Basically the proposal is we do analyses as late as possible, and for free variables we do the analysis right before code generation. But if late lambda lifting uses this information then that's not going to work, we need to do it earlier, and then make sure (perhaps only in debug builds or with a flag) that late lambda lift correctly updates free variables of closures. Because lll (late lambda lift) will be the first pass that'll need the free variables I think we should compute it right before the pass. That means (depending on when we're running lll) some passes may not have the information. In that case perhaps it's better to remove the fvs list from the syntax, and pass it around in an environment. Alternatively we could keep it in the syntax, do the computation in CoreToStg, and run a sanity check after each pass to make sure the information remains correct. However this means that a pass that doesn't need the information, but incidentally updates it (we currently don't have such a pass) will have to deal with the fvs field. Not sure if this is a huge concern right now.. Any thoughts? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Free-var info is inherently fragile, and is easily regenerated. It's a bit like `OccInfo` on a binder in `Core`. Best, I think, to generate it where needed, and explicitly nuke it in any pass that can't easily guarantee to preserve it. I suppose we could have a type index to specify whether or not the FV info was in there. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by sgraf): LLL will run as late as possible, ideally immediately before going to Cmm. It's pretty easy for LLL to maintain FV information accurately, I'd say, so generating it once (or as needed) would still be feasible. I'm still not sure if it's a good idea to store free variable information ''directly in STG syntax'' if we only guarantee the implied invariants immediately after StgFV is run. Sort of the same problem which is solved by Trees to grow in the frontend. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):
That's probably what Simon alludes to in comment:6 by suggesting a type index to solve this.
Yes. Even without the full glory of TTG we could have something like this: {{{ data GenStgRhs pass = StgRhsClosure CostCentreStack -- CCS to be attached (default is CurrentCCS) StgBinderInfo -- Info about how this binder is used (see below) (XRhsClosure pass) -- non-global free vars; a list, rather than -- a set, because order is important !UpdateFlag -- ReEntrant | Updatable | SingleEntry [StgBndr pass] -- arguments; if empty, then not a function; -- as above, order is important. (GenStgExpr pass) -- body type instance XRhsClosure pass where XRhsCLosure JustBeforeCodeGen = [Id] XRhsClosure _ = () }}} Now `GenStgRhs JustBeforeCodeGen` has free-var info, but `GenStgRhs OtherPass` does not. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 #15867 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * related: #9718 => #9718 #15867 Comment: #15867 has shown that there are at least `StgUnarise` and `StgCse` that are a little careless wrt. duplicates in the FV list. So removing the field altogether makes sense. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 #15867 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Another invariant that the code generator needs is (I believe) that every let-binder has a distinct unique. We can't re-use the same unique, even in a different scope, let alone shadowing. Why? Because (I believe) that the code generator uses these uniques to generate unique top level labels for the entry code and info table for the closure. Now, it's probably the case that they are unique anyway; but we should either * Write this down as a invariant of STG, or * Establish this invariant in the immediately-before-codegen pass that gets the free vars right, or * Not assume it in the code generator Sebastian, are you planning to work on this free-var change? Thanks. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 #15867 | Differential Rev(s): Phab:D5324 Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * status: new => patch * differential: => Phab:D5324 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 #15867 | Differential Rev(s): Phab:D5324 Wiki Page: | -------------------------------------+------------------------------------- Comment (by osa1): Note that Phab:D5324 does not address comment:10, which we may want to track in another ticket. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
Note that Phab:D5324 does not address comment:10, which we may want to
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: patch Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 #15867 | Differential Rev(s): Phab:D5324 #15901 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * related: #9718 #15867 => #9718 #15867 #15901 Comment: Replying to [comment:12 osa1]: track in another ticket. This is now tracked in #15901. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#15754: Move free variable computation to after STG passes
-------------------------------------+-------------------------------------
Reporter: bgamari | Owner: (none)
Type: bug | Status: patch
Priority: normal | Milestone: 8.8.1
Component: Compiler | Version: 8.6.1
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
| Unknown/Multiple
Type of failure: None/Unknown | Test Case:
Blocked By: | Blocking:
Related Tickets: #9718 #15867 | Differential Rev(s): Phab:D5324
#15901 |
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Sebastian Graf
#15754: Move free variable computation to after STG passes -------------------------------------+------------------------------------- Reporter: bgamari | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.6.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: #9718 #15867 | Differential Rev(s): Phab:D5324 #15901 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by sgraf): * status: patch => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/15754#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC