feat(optimizer): distribute an accessor or application into if branches - #334
Merged
Conversation
…es (#243) A cheap eliminator applied to an IfThenElse scrutinee — a field, index, length or tag read, or a call — distributes into both arms, so the conditional leaves expression position (an IIFE in the generated Lua) and the pushed operation reaches the arms where the constructor, projection and beta folds fire. Arms are never duplicated; an application's arguments are the only duplicated operands, gated by isInlinableValue (pure, bounded, binder-free to re-emit). Subsumes the fold-gated tag-read distribution of reduceKnownConstructor (issue #180): a tag read now distributes over any conditional, folding in whichever arms turn out to be constructors, so reflectFoldsThrough is gone. Golden fallout: NativeLoopsGuard and TailRecM2Shadow move only in IR (the Lua-level foldCallThroughScopeCall backstop had already produced the distributed Lua); UncurryEffect improves — distributing the effect-run application exposes the self tail call in both arms and loopification now turns countdown into a while-true loop. New golden DistributeIntoIf pins the projection fold, the opaque-record push, the beta-redex payoff, and the declined non-trivial argument, with an eval oracle.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Closes #243.
Adds
pushEliminatorIntoIfBranchesto the IR optimizer's rewrite chain: an eliminator applied to a conditional scrutinee — a record field read (ObjectProp), an array read or length (ArrayIndex/ArrayLength), a constructor tag or field read (ReflectCtor/DataArgumentByIndex), or a saturated call (AppN) — distributes into both arms,(if p then a else b).f ==> if p then a.f else b.fand(if p then f else g) x ==> if p then f x else g x. Without the push the conditional sits in expression position, which codegen wraps in an immediately-invoked function (IIFE) allocated and called per evaluation, and the eliminator never reaches the arms where the constructor, projection, and beta folds fire.The new golden
Golden.DistributeIntoIfshows all the shapes. A projection over a conditional of known records used to compile to an IIFE plus a field read off its result:and now distributes, folds each arm's read, and lands in statement position:
A call over a conditional of lambdas was already handled late, at the Lua level, by
foldCallThroughScopeCall(the backstop that pushes an applied scope call into its return sites) — but that runs after all IR folds, so it left un-reduced beta redexes allocating a closure per call:Distributed at the IR level instead, the pushed call meets
betaReducein the arms:The arms themselves are never duplicated — each receives one copy of the eliminator — so no gate on the arms is needed. The only syntactically duplicated operands are an application's arguments, admitted by
isInlinableValue(references, scalar literals, cheap projection chains: pure and bounded to re-emit, and binder-free, so the copies cannot break the unique-binders invariant). Only the arm that runs evaluates its argument copy, and evaluation order — condition, then arm, then arguments — is the same in both forms. A call whose argument does real work is declined, pinned by the golden'sapplyExpensive(its argument is a call,weigh(n)), which keeps its IIFE verbatim. The unrestricted transformation (arbitrary consumer contexts) needs the join points of #234 to avoid duplicating the consumer; this rewrite is deliberately the duplication-free subset.The rule subsumes the fold-gated tag-read distribution that
reduceKnownConstructorcarried since #180 (fire only when every branch folds to a tag string): a tag read now distributes over any conditional and folds in whichever arms turn out to be constructors, so thereflectFoldsThroughguard is deleted. TheEq-against-literal push of #203 keeps its own rule and fold gate unchanged.Golden fallout, all with eval outputs unchanged:
NativeLoopsGuardandTailRecM2Shadowmove only in IR — their effect-run applications(if b then act else pure unit)(run)now distribute at the IR level, producing exactly the Lua the late backstop already produced.UncurryEffectgenuinely improves: distributing the effect-run application turns each arm into a direct tail call, and loopification (which requires the self call in tail position) now convertscountdowninto awhile trueloop:where before the recursion hid behind the conditional-callee shape and stayed a stack-consuming self call:
Verification: ten focused unit specs (written and confirmed red first) cover each eliminator kind, the fold cascades, and the declined non-trivial argument both through the pipeline and as a direct guard pin; the new golden carries a hand-written eval oracle checked against real execution; the full suite is green, the
IR Optimizergroup was seed-stressed 12 runs without a failure or hang, andbench/cicounters are unchanged against the committed oracles.