feat: fold case-of-known-constructor in the IR optimizer (#177)#209
Merged
Conversation
Two rewrite rules in optimizedExpressionM, the algebraic-type twin of the
record-projection fold (reduceObjectProp):
* ReflectCtor over a saturated sum-type constructor application folds to
the constructor's tag string. Constant folding and the
unreachable-branch rules then collapse the surrounding decision-tree
test to its live branch (GHC's KnownBranch).
* DataArgumentByIndex i over a saturated constructor application folds to
the i-th argument.
A constructor application is the curried unary-App spine the pattern
matcher builds; the fold fires only at exact saturation, so a partial
application stays a function. ReflectCtor folds for sum types only:
product constructors omit the $ctor row in codegen, so folding a
product-type tag read would invent a value the runtime reads as nil. Field
reads fold for either shape.
Discarded arguments are dropped, not evaluated -- the discipline
reduceObjectProp applies to discarded record fields and DCE applies to
unused bindings. A dropped argument cannot skip an Effect: effects are
unrun thunks here, run only when applied, so an effect that must run is the
kept field, never a dropped one; the only casualties are the pure
divergence or partiality DCE already elides. The folded value takes the
read node's own annotation, not the argument's, so a Just Always-annotated
foreign accessor cannot leak inlinability into the result.
Standalone impact is near zero -- the shapes appear once dictionary
specialization (#178/#180) inlines a constructor into a match -- so this
lands as the enabler those issues build on.
…ctor Nine example cases pin the fold decisions directly: the tag and field folds, a non-zero field index, the decision-tree collapse cascade, the declines (partial application, product-type tag read), the argument drop, and the annotation discipline (no leak from the kept argument, the read node's own annotation preserved). Two randomized properties stress the discard semantics the issue flags: across arbitrary arity, algebraic type, and argument content, a field read folds to exactly its argument (equality to the kept argument alone proves the siblings are dropped, not bound or duplicated) and a sum-type tag read folds to the tag string. Two pipeline tests -- the constructor twins of "record projection after inlining" -- prove both folds fire end to end through the full optimizer: inlining a single-use constructor binding into a field or tag read forms the redex mid-fixpoint, the fold reduces it, and DCE drops the emptied binding.
The #177 review flagged that reduceKnownConstructor's local spine unwinder was a third copy of the same four-line helper: MagicDo had `spine` and Uncurry had a local `unwind`, both peeling a curried unary-App spine into (head, arguments). Promote one polymorphic `unwindApp ∷ ∀ ann. RawExp ann → (RawExp ann, [RawExp ann])` to IR.Types, next to the `App` pattern synonym and Note [n-ary application], and use it from the optimizer, MagicDo, and Uncurry. Removing the optimizer's local copy orphaned its `pattern Abs`/`App` imports, so they go too. Two neighbouring local helpers in IR.Types (`bindParam`, `freshenParam`) gain the type signatures the shared helper's own local binding needed, keeping the module warning-free under -Wmissing-local-signatures.
A clean build carried a handful of pre-existing -W warnings unrelated to the #177 fold. Clear them so the whole build is warning-free: - -Wmissing-local-signatures: add signatures to the local helpers shadowParam (Linker), classify (IR), separator (Lua.Printer), and bindParam (DCE); - -Wunused-imports: drop `App` (FlattenDeepBinds spec) and Control.Monad.Trans.Except (Lua spec); - -Wname-shadowing: rename a local `ctor` in the IR spec that shadowed the imported constructor smart-constructor to `cfnCtor`.
Prefer `\_whatIsBeingDiscarded → …` over `const …`: the named-but-ignored binder documents what is being discarded, which `const` erases.
…-optimizer soundness property The shared Hedgehog generator emitted neither ReflectCtor/DataArgumentByIndex nor saturated constructor applications, so no property suite ever fuzzed constructor-shaped IR against the #177 case-of-known-constructor fold. Extend both `exp` and `scopedExpIn` with a saturated ctor-application shape (one argument per field; nullary ⇒ a bare Ctor) plus reflectCtor / dataArgumentByIndex wrappers. A Ctor node binds nothing and references no Scope entry, so every argument just reuses the incoming scope — the same category as application/if/object. This feeds every existing Gen.scopedExp / Gen.exp consumer (FloatIn, DCE, Uniquify, Linter, Types, the full-pipeline Optimizer prop), which now fuzz constructor shapes for free. Add one property running the full single-pass optimizedExpression over generated input: free references stay a subset (the fold drops discarded ctor arguments, so equality would be wrong) and the result stays well-scoped. Drop a now-surfaced redundant `pattern App` import in FlattenDeepBinds/Spec (App appears only in a comment) to keep the recompiled build warning-free.
Contributor
There was a problem hiding this comment.
Pull request overview
This PR adds “case-of-known-constructor” constant-folding to the IR optimizer so that tag reads (ReflectCtor) and field reads (DataArgumentByIndex) over syntactically known, saturated constructor applications can be reduced early in the IR pipeline, enabling downstream inlining/specialization cascades (per #177 and as a prerequisite for #178/#180).
Changes:
- Added an IR optimizer rewrite (
reduceKnownConstructor) that foldsReflectCtorover saturated sum-type constructor applications to the constructor tag string, and foldsDataArgumentByIndexto the selected argument. - Introduced a shared
unwindApphelper inIR.Typesand migrated multiple passes to reuse it (Optimizer, MagicDo, Uncurry). - Added targeted unit + property tests and end-to-end pipeline tests covering firing/declining cases, discard behavior, and annotation discipline; plus small cleanup/warning-suppression edits and a changelog fragment.
Reviewed changes
Copilot reviewed 15 out of 15 changed files in this pull request and generated no comments.
Show a summary per file
| File | Description |
|---|---|
| test/Language/PureScript/Backend/Lua/Spec.hs | Removes an unused import as part of cleanup. |
| test/Language/PureScript/Backend/IR/Spec.hs | Renames a local helper to avoid naming clashes and improve clarity in the test. |
| test/Language/PureScript/Backend/IR/Optimizer/Spec.hs | Adds extensive unit/property/pipeline tests for the new known-constructor folds (#177). |
| test/Language/PureScript/Backend/IR/FlattenDeepBinds/Spec.hs | Drops an unused pattern import after refactors. |
| lib/Language/PureScript/Backend/Lua/Printer.hs | Adds a local type signature (warning cleanup) for statement separation logic. |
| lib/Language/PureScript/Backend/IR/Uncurry.hs | Refactors saturated-site detection to use shared unwindApp. |
| lib/Language/PureScript/Backend/IR/Types.hs | Adds unwindApp utility for peeling unary-App spines; adds local signatures for warning cleanup. |
| lib/Language/PureScript/Backend/IR/Optimizer.hs | Implements reduceKnownConstructor and wires it into optimizedExpressionM rewrite sequencing. |
| lib/Language/PureScript/Backend/IR/MagicDo.hs | Reuses unwindApp and removes a duplicated local spine unwinder. |
| lib/Language/PureScript/Backend/IR/Linker.hs | Adds a local helper signature (warning cleanup). |
| lib/Language/PureScript/Backend/IR/DCE.hs | Adds a local helper signature (warning cleanup). |
| lib/Language/PureScript/Backend/IR.hs | Adds a local helper signature in data-declaration classification (warning cleanup). |
| changelog.d/20260708_090000_unisay_case_of_known_constructor.md | Documents the new optimizer capability and its motivation/constraints. |
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 #177. The enabler for the dictionary-specialization cascade (#178/#180 build on it).
What
Two rewrite rules in
optimizedExpressionM, the algebraic-type twin of the existing record-projection fold (reduceObjectProp):ReflectCtor (K a₁ … aₙ)over a saturated sum-type constructor application folds toK's tag string. Constant folding and the unreachable-branch rules then collapse the surrounding decision-tree test to its live branch (GHC's KnownBranch).DataArgumentByIndex i (K a₁ … aₙ)folds toaᵢ.Design points
Saturation. A constructor application is the curried unary-
Appspine the pattern matcher builds (App (… (App (Ctor …) a₁) …) aₙ); aCtornode holds field names, not arguments. The fold unwinds that spine and fires only at exact saturation (as many arguments as fields), so a partial application stays a function. A genuinely n-aryAppNctor application (which #201 will introduce) is left alone until then.Sum types only for the tag fold. Product constructors omit the
$ctorrow in codegen, so folding a product-type tag read to a string would invent a value the runtime reads asnil. Field reads fold for either shape, sincevalueᵢrows exist for both.Discard discipline. The issue asks for the
reduceObjectPropdiscipline, and I read its named precedent literally:reduceObjectPropdrops discarded record fields (the same call DCE makes on an unused binding), so these folds drop discarded arguments too. I checked this can't skip anEffect: effects are unrun thunks in this backend, run only when applied, so an effect that must run is the kept field, never a dropped one. The only casualties are the pure divergence or partiality that DCE already elides (andunsafePerformEffect, whose behavior under DCE is unsafe by contract and which a let-bind wouldn't save anyway). The folded value takes the read node's own annotation, not the argument's, so aJust Always-annotated foreign accessor can't leak inlinability into the result.Verification
expandscopedExpIngained a saturated constructor application (one argument per field, nullary ⇒ a bareCtor) plusreflectCtor/dataArgumentByIndexwrappers. ACtornode binds nothing and references no scope entry, so every argument reuses the incoming scope (the same category as application / if / object), well-scoped by construction. This feeds every existingGen.scopedExp/Gen.expconsumer (FloatIn, DCE, Uniquify, Linter, Types, and the full-pipeline Optimizer property), so ~10 property suites now fuzz constructor-shaped IR against these folds for free.optimizedExpressionover generated input (which, with the generator extension, actually fires the fold): free references stay a subset of the input's (the fold drops discarded ctor arguments, so equality would be wrong), and the result stays well-scoped. FloatIn's stricter "preserves free references" equality still holds, sincefloatInonly movesLets and drops nothing.-Wwarnings). No golden churn: as the issue predicts, the shapes don't occur in any existing golden, because they need specialization to bring a constructor inline to a match, so the standalone effect is nil and the value lands through Lift the pure subset of foreign values into the IR: primop nodes and an allowlist-driven lifter #178/Budgeted call-site inlining of dictionary methods to collapse non-Effect/ST monadic chains #180.spinein MagicDo, a localunwindin Uncurry), so one polymorphicunwindAppmoved toIR.Typesand all three passes now share it; a clean build's remaining pre-existing warnings (missing local signatures, unused imports, one shadowed name, a redundantpattern Appimport surfaced by the generator recompile) are cleared so the build is warning-free; and theUse consthlint hint is disabled repo-wide, since a named-but-ignored lambda binder (\_whatIsDiscarded → …) documents what is dropped whereconsterases it.