Floats let bindings

[mikesol]

Floats let bindings when strictness allows. This makes it easier to reason about BackendSemantics because, when we case on something, there's a higher chance that its subtree won't have closures from let bindings.

[natefaubion]

I'm assuming the top-level special case is to avoid turning

foo = { a: let x = ... in bar x }

into

foo = let x = ... in let $0 = bar x in { a: $0 }

Because at the top-level it is still advantageous to deref into these structures. If we float here, then it may prevent access into otherwise statically known fields. Is that correct?

If so, I have a few thoughts:

• One is that we just float at the top-level where these floated bindings become additional top-level bindings. The downside here is that it can potentially create a lot of additional top-level bindings that need to be exported. I don't know if this is actually a problem. This would require some interface changes as an optimized binding could emit multiple bindings, which may incur an additional rewrite at the end. This rewrite could be done as part of freeze potentially, so I don't think it would be an additional pass.
• We could still provide access to static fields in this case through an alternative ExternImpl. For example, currently we have ExternDict, which is a top-level record. We could have a variation of this that goes through the lets and only exposes the fields which have no dependencies on such let bindings. This would be straightforward to do with the usage analysis that's already there.
• Is immediate top-level syntax the actual designation we want? I could see top-level evaluation in general as a useful context. For example, you could have an annotation stating that some binding should be evaluated as much as possible up-to a lambda (this is what prepack is). Top-level syntax to me seems only useful for this particular artifact, so I'd like to explore other options that might make sense.

---

Additionally, on main, I've merged a --timing flag to help judge the effects of various changes. Running npm run build in backend-es being my main benchmark. This change seems to add several seconds to the build time to me (about 15% total slowdown), which I assume is related to the Free encoding. I think that it's a cleverly terse way of expressing this, but I suspect it's quite heavyweight at runtime. In general, I am avoiding abstractions like these in favor of straightline cases and loops (as much as possible) to keep performance relatively predictable.

Edit: I think an additional reason it might be slow is that this is relying on traverse, which build balanced tree of effects, where in the case of let bindings we always want right associated continuations. So we have to essentially build the intermediate Free tree, and then another pass to rewrite the tree to be right associated (resume), and then build the actual continuations. If this was just a foldr like in the other cases, and how I had suggested, this would be one shot.

[natefaubion]

Can you remind why this is specifically done in eval? Is this only because of recursive eval? In the past I asked if we could unify let floating into a single pass as right now it's split between eval and build. The reason I ask, is that let floating in eval is somewhat problematic because you'll have these steps:

• build initial syntax
• eval to floated lets
• build syntax for inline analysis
• eval to float back in bindings

Whereas if let floating is done only in build you would be able to float and do inline analysis in the same pass, only requiring the one subsequent eval. This makes me question if efficient let floating should all be done in build rather how we are splitting it now.

[natefaubion]

FWIW, I think the main reason why we couldn't do all floating in eval is because evalAssocLet is not recursive. It only floats out the immediate let, rather than recursively floating out lets within the binding.

[mikesol]

Ah, I knew I had forgotten something. In the original PR I had done this: https://github.com/mikesol/purescript-backend-optimizer/blob/63fca1f8d71c888a4250d4ba76b8c77b3a9f3007/src/PureScript/Backend/Optimizer/Semantics.purs#L583C1-L594C15. I just added it back for completenesses sake to evaluate the approach in full, I'll address your question about build in a second comment.

[mikesol]

Can you remind why this is specifically done in eval? Is this only because of recursive eval?

Yeah, that's why. I had tried to put everything into eval (including the rewrites) but, for some reason, I couldn't replicate the behavior of the rewrite rule during the eval stage. We can try adding it back (on the Let branch of eval) and see what goes awry.

The issue with putting it all in build if I remember correctly is that lets don't move upward in one pass. For example, if I have:

let x = 42 in {a: {b: {c:{d:{e:{f:let y=43 in y+x}}}}}}

Obv this example would get inlined anyway but imagine that it didn't and the optimizer chose let floating. This approach, with the newly minded recursive evalAssocLet, makes the let bubble up during the first eval pass, whereas doing it in build would ratchet it up one level per pass IIRC.

So to summarize:

• I'm definitely open to ditching the free monad approach in favor of something that doesn't have two passes. I'm sure there's a way to do this, I just couldn't think of it immediately and free monads make stuff easier to write and read at the expense of bad performance.
• I'm ok with putting all this logic into build if we can avoid the situation where there are many more runs of optimize as the binding moves up the tree.

[natefaubion]

Obv this example would get inlined anyway but imagine that it didn't and the optimizer chose let floating. This approach, with the newly minded recursive evalAssocLet, makes the let bubble up during the first eval pass, whereas doing it in build would ratchet it up one level per pass IIRC.

I don't think this is necessarily true:

• build record with f, float the let out of the record.
• build record with e, float the floated let out of the record.
• Continue...

If it's not floating in one pass (floating is bubbling lets bottom up), then that just seems to be that you're missing other floating rules within build, such as when you build an array.

But now that I think about it, I'm not sure if this works well with levels. If you pull out multiple lets in a record/array, they will all have the same levels (since they are essentially parallel evaluation contexts), so you can't naively just put them in the same block, as the references won't make any sense any more, you would have to do additional book keeping to propagate levels to the right places, which... is exactly what eval is doing. So that makes me think that floating should be in eval, and we should make a left recursive evalAssocLet, which I think would obviate the need for the build rewrites.

[natefaubion]

I think before moving forward more with this, I myself would like to take some time to understand and reason about eval-based let floating with regards to eliminating the build rewrite constraints in it's own PR.

[mikesol]

Ready for review 👍

[natefaubion]

I haven't forgotten about this, and this is something I want to integrate. This PR handles the top-level flattening of recursive binding groups by encoding information in the name and parsing it back out later. This is not something I want to merge, but I assume it was done to avoid refactoring this module. I've been working on this refactoring in some WIP commits, but I have not fully completed it yet due to life demands. I will try to get back to it as soon as I can.

[mikesol]

No worries!

I'm still a fan of the idea, but I stopped working on it because the stringly-typed programming felt icky and I wasn't sure about a clean way to refactor. If you've found a path forward there then that's great!

Mike Solomon C.E.O. @Meeshkan https://www.meeshkan.com

Sent via Superhuman ( @.*** )

On Fri, Sep 22, 2023 at 01:52:56, Nathan Faubion < @.*** > wrote:

I haven't forgotten about this, and this is something I want to integrate. This PR handles the top-level flattening of recursive binding groups by encoding information in the name and parsing it back out later. This is not something I want to merge, but I assume it was done to avoid refactoring this module. I've been working on this refactoring in some WIP commits, but I have not fully completed it yet due to life demands. I will try to get back to it as soon as I can.

— Reply to this email directly, view it on GitHub ( https://github.com/aristanetworks/purescript-backend-optimizer/pull/76#issuecomment-1730452466 ) , or unsubscribe ( https://github.com/notifications/unsubscribe-auth/AAEAIJXDRCQNUX2PTPZIE4TX3TAMRANCNFSM6AAAAAA25YMHN4 ). You are receiving this because you authored the thread. Message ID: <aristanetworks/purescript-backend-optimizer/pull/76/c1730452466 @ github. com>