Transparently hooking into the STG stack to validate an escape analysis
Sebastian Graf
sgraf1337 at gmail.com
Thu Dec 16 16:29:19 UTC 2021
Hey Csaba,
After catching up on your talk and reflecting about it a bit, it seems
quite obvious that your tool is the right way to collect the data and
validate our analysis!
Even if meanwhile we decided that a "transparent stack frame" (which I
believe is something similar to what you are doing here
<https://github.com/grin-compiler/ghc-whole-program-compiler-project/blob/d3ed07d9f3167ad1afa01d1aa95aec2472b2708f/external-stg-interpreter/lib/Stg/Interpreter.hs#L130>,
with an explicit `argCount` which we do not know) is not the ideal
solution we've been looking for (for different reasons).
Essentially, we have two things
An escape analysis, implemented as an STG-to-STG pass that attaches a
boolean flag to each Id whether it "escapes its scope" (for a suitable
definition of that).
We'd like to implement it in a way that it would be reusable within GHC
with moderate effort (e.g., renaming Binder to Id or accounting for
different fields), operating on a module at a time rather than whole
program.The instrumentation that tries to measure how many heap objects
could be allocated on the stack. E.g., set a closure-specific flag
whenever the closure is entered, unset that bit (once) when we "leave
the scope" that defines the closure.
If my understanding is right, we could just implement this
"instrumentation" as a simple extra field to Closure
<https://github.com/grin-compiler/ghc-whole-program-compiler-project/blob/d3ed07d9f3167ad1afa01d1aa95aec2472b2708f/external-stg-interpreter/lib/Stg/Interpreter/Base.hs#L135>,
right? Neat!
A bit tangential: I see that your interpreter currently allocates a
fresh closure for let-no-escapes
<https://github.com/grin-compiler/ghc-whole-program-compiler-project/blob/d3ed07d9f3167ad1afa01d1aa95aec2472b2708f/external-stg-interpreter/lib/Stg/Interpreter.hs#L606>
when it could just re-use the closure of its defining scope. That would
skew our numbers somewhat compared to instrumenting GHC-compiled
programs, but I think we'd be able to work around that. I also wonder if
the semantics of your let-no-escapes are actually as typically specified
(operationally), in that a jump to a let-no-escape should also reset the
stack pointer. It should hardly matter for the programs that GHC
generates, though.
I would also be interested in knowing whether the +RTS -s "bytes
allocated in the heap" metric (very nearly) coincides with a similar
metric you could produce. It would be fantastic if that was the case!
Theoretically, that should be possible, right?
I think your interpreter work is very valuable to collect data we
otherwise would only be able to measure with a TickyTicky-based
approach. Nice!
Another, similar use case would be to identify the fraction of closures
that are only entered once. I remember that there was a ticky-based
patch with which Joachim used to measure this fraction
<https://gitlab.haskell.org/ghc/ghc/-/wikis/commentary/compiler/demand#instrumentation>
(and similarly validate the analysis results), but unfortunately it
couldn't end up in master. Ah, yes, we have a whole open ticket about
it: #10613 <https://gitlab.haskell.org/ghc/ghc/-/issues/10613>. In fact,
that instrumentation is also somewhat similar (adding a field to every
closure) as what we want to do.
Anyway, it seems like your work will be very valuable in replacing some
of the annoying ticky-based instrumentation ideas!
Maybe we can have a call some time this or next week to discuss details,
once Sebastian and I are more familiar with the code base?
Thanks for sticking with the project and doing all the hard work that
can build upon!
Sebastian
------ Originalnachricht ------
Von: "Csaba Hruska" <csaba.hruska at gmail.com>
An: "Sebastian Graf" <sgraf1337 at gmail.com>
Cc: "ghc-devs" <ghc-devs at haskell.org>; "Sebastian Scheper"
<sebastian.scheper at student.kit.edu>
Gesendet: 15.12.2021 16:16:27
Betreff: Re: Transparently hooking into the STG stack to validate an
escape analysis
>Hi,
>
>IMO the Cmm STG machine implementation is just too complex for student
>projects. It's not fun to work with at all.
>Why did you choose this approach?
>IMO the escape analysis development and validation would be much
>smoother and fun when you'd use the external STG interpreter.
>When you have a solid and working design of your analysis and
>transformations then you could implement it in GHC's native backend if
>it needs any changes at all.
>
>What do you think?
>Do you disagree?
>
>Have you seen my presentation about the stg interpreter?
>https://www.youtube.com/watch?v=Ey5OFPkxF_w
>
>Cheers,
>Csaba
>
>On Wed, Dec 8, 2021 at 11:20 AM Sebastian Graf <sgraf1337 at gmail.com>
>wrote:
>>Hi Devs,
>>
>>my master's student Sebastian and I (also Sebastian :)) are working on
>>an escape analysis in STG, see
>>https://gitlab.haskell.org/ghc/ghc/-/issues/16891#note_347903.
>>
>>We have a prototype for the escape analysis that we want to
>>validate/exploit now.
>>The original plan was to write the transformation that allocates
>>non-escaping objects on the STG stack. But that is quite tricky for
>>many reasons, one of them being treatment of the GC.
>>
>>This mail is rather lengthy, so I suggest you skip to "What we hope
>>could work" and see if you can answer it without the context I provide
>>below. If you can't, I would be very grateful if you were willing to
>>suffer through the exposition.
>>
>># Instrumentation
>>
>>So instead we thought about doing a (easily changed and thus
>>versatile) instrumentation-based approach:
>>Assign a sequence number to every instantiation (a term I will use to
>>mean "allocation of g's closure") of things that we our analysis
>>determines as escaping or non-escaping, such as STG's let bindings
>>(focusing on non-let-no-escape functions for now).
>>(One sequence number *per allocation* of the let binding's closure,
>>not based on its syntactic identity.)
>>Then, we set a bit in a (dynamically growing) global bit vector
>>whenever the let "RHS is entered" and then unset it when we "leave the
>>let-body". Example:
>>
>>f = \x y ->
>> let {
>> g = [y] \z -> y + z;
>> } in g x
>>
>>Here, our analysis could see that no instantiation (which I say
>>instead of "allocation of g's closure") of g will ever escape its
>>scope within f.
>>Our validation would give a fresh sequence number to the instantiation
>>of g whenever f is called and store it in g's closure (which we
>>arrange by piggy-backing on -prof and adding an additional field to
>>the profiling header).
>>Then, when g's RHS is entered, we set the bit in the global bit
>>vector, indicating "this instantiation of g might escape".
>>After leaving the RHS of g, we also leave the body of the defining
>>let, which means we unset the bit in the bit vector, meaning "every
>>use so far wasn't in an escaping scenario".
>>
>>So far so good. Modifying the code upon entering g takes a bit of
>>tinkering but can be done by building on TickyTicky in StgToCmm.
>>But what is not done so easily is inserting the continuation upon
>>entering the let that will unset the bit!
>>
>># What doesn't work: Modifying the Sequel
>>
>>At first, we tried to modify the sequel
>><https://gitlab.haskell.org/ghc/ghc/-/blob/4c6985cc91b9cf89b393f69c9a603e8df0aea9e0/compiler/GHC/StgToCmm/Monad.hs#L210-222>
>>of the let-body to an `AssignTo`.
>>That requires us to know the registers in which the let-body will
>>return its results, which in turn means we have to know the
>>representation of those results, so we have to write a function
>>`stgExprPrimRep :: GenStgExpr p -> [PrimRep]`.
>>Urgh! We were very surprised that there was no such function. And
>>while we tested our function, we very soon knew why. Consider the
>>following pattern synonym matcher:
>>
>>GHC.Natural.$mNatJ#
>> :: forall {rep :: GHC.Types.RuntimeRep} {r :: TYPE rep}.
>> GHC.Num.Natural.Natural
>> -> (GHC.Num.BigNat.BigNat -> r) -> ((# #) -> r) -> r
>> = {} \r [scrut_sBE cont_sBF fail_sBG]
>> case scrut_sBE of {
>> GHC.Num.Natural.NS _ -> fail_sBG GHC.Prim.(##);
>> GHC.Num.Natural.NB ds_sBJ ->
>> let {
>> sat_sBK :: GHC.Num.BigNat.BigNat
>> = CCCS GHC.Num.BigNat.BN#! [ds_sBJ];
>> } in cont_sBF sat_sBK;
>> };
>>
>>Note how its result is representation-polymorphic! It only works
>>because our machine implementation allows tail-calls.
>>It's obvious in hindsight that we could never write `stgExprPrimRep`
>>in such a way that it will work on the expression `cont_sBF sat_sBK`.
>>So the sequel approach seems infeasible.
>>
>># What we hope could work: A special stack frame
>>
>>The other alternative would be to insert a special continuation frame
>>on the stack when we enter the let-body (inspired by
>>stg_restore_cccs).
>>This continuation frame would simply push all registers (FP regs, GP
>>regs, Vec regs, ...) to the C stack, do its work (unsetting the bit),
>>then pop all registers again and jump to the topmost continuation on
>>the STG stack.
>>Example:
>>
>>f :: forall rep (r :: TYPE rep). Int# -> (Int# -> r) -> r
>>f = \x g ->
>> let {
>> h = [x] \a -> x + a;
>> } in
>> case h x of b {
>> __DEFAULT -> g b
>> }
>>
>>We are only interested in unsetting the bit for h here. Consider the
>>stack when entering the body of h.
>>
>>caller_of_f_cont_info <- Sp
>>
>>Now push our special continuation frame:
>>
>>caller_of_f_cont_info
>>seq_h
>>unset_bit_stk_info <- Sp
>>
>>E.g., the stack frame contains the info pointer and the sequence
>>number. (Btw., I hope I got the stack layout about right and this is
>>even possible)
>>Then, after we entered the continuation of the __DEFAULT alt, we do a
>>jump to g.
>>Plot twist: g returns an unboxed 8-tuple of `Int#`s (as
>>caller_of_f_cont_info knows, but f certainly doesn't!), so before it
>>returns it will push two args on the stack (correct?):
>>
>>caller_of_f_cont_info
>>seq_h
>>unset_bit_stk_info
>>unboxed tuple component 7
>>unboxed tuple component 8 <- Sp
>>
>>And then `g` jumps directly to the entry code for `unset_bit_stk_info`
>>(which does the register saving I mentioned), which absolutely can't
>>figure out from Sp alone where seq_h is.
>>Darn! I think Luite's recent work on the StgToByteCode had to work
>>around similar issues, I found this wiki page
>><https://gitlab.haskell.org/ghc/ghc-wiki-mirror/-/blob/master/Unboxed-Tuples-and-Sums-in-GHCi-bytecode.md#returning-a-tuple>.
>>But we aren't in a position where we know the representation of `r`
>>*at all*!
>>
>>So our idea was to scan the stack, beginning from `Sp`, until I find
>>`unset_bit_stk_info`, giving us the following situation:
>>
>>caller_of_f_cont_info
>>seq_h
>>unset_bit_stk_info <- Bp
>>unboxed tuple component 7
>>unboxed tuple component 8 <- Sp
>>
>>I suggestively named the register in which we store the result Bp in
>>analogy to the traditional base pointer. This information would be
>>enough to unset the bit at index seq_h
>>and then copy the unboxed tuple components 7 and 8 up by two words:
>>
>>caller_of_f_cont_info
>>unboxed tuple component 7
>>unboxed tuple component 8 <- Sp
>>
>>Then jump to caller_of_f_cont_info, which knows what to make of the
>>stack and the register state.
>>
>>The stack scanning is horrible and too brittle and slow for a
>>production setting, as any of the unboxed tuple components could have
>>the same bit pattern as `unset_bit_stk_info`.
>>We simply hope that is never the case and it's fine for the purposes
>>of a quick-and-dirty instrumentation.
>>
>>QUESTION 1: What do you think? Could this work? Can you anticipate pit
>>falls of this approach?
>>
>># What about Thunks and StgRhsCon?
>>
>>QUESTION 2: The instrumentation as described won't work for Thunks
>>(which are only entered once) and constructor applications (like
>>sat_sBK in the BigNat matcher above). Not sure how to change that
>>without incurring huge performance hits (by deactivating memoisation).
>>Ideas are welcome here.
>>
>>Thanks for reading this far. I hope you could follow and are now
>>fizzing with excitement because you have a much better idea of how to
>>do this and will let me know :)
>>
>>Sebastian
>>_______________________________________________
>>ghc-devs mailing list
>>ghc-devs at haskell.org
>>http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20211216/5ec3326f/attachment.html>
More information about the ghc-devs
mailing list