Skip to content

feat: fold case-of-known-constructor in the IR optimizer (#177)#209

Merged
Unisay merged 6 commits into
mainfrom
issue-177/case-of-known-ctor
Jul 8, 2026
Merged

feat: fold case-of-known-constructor in the IR optimizer (#177)#209
Unisay merged 6 commits into
mainfrom
issue-177/case-of-known-ctor

Conversation

@Unisay

@Unisay Unisay commented Jul 8, 2026

Copy link
Copy Markdown
Collaborator

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 to K'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 to aᵢ.

Design points

Saturation. A constructor application is the curried unary-App spine the pattern matcher builds (App (… (App (Ctor …) a₁) …) aₙ); a Ctor node 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-ary AppN ctor application (which #201 will introduce) is left alone until then.

Sum types only for the tag fold. Product constructors omit the $ctor row in codegen, so folding a product-type tag read to a string would invent a value the runtime reads as nil. Field reads fold for either shape, since valueᵢ rows exist for both.

Discard discipline. The issue asks for the reduceObjectProp discipline, and I read its named precedent literally: reduceObjectProp drops 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 an Effect: 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 (and unsafePerformEffect, 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 a Just Always-annotated foreign accessor can't leak inlinability into the result.

Verification

  • Nine example cases pin the fold decisions directly (both folds, non-zero index, the collapse cascade, both declines, the argument drop, the annotation discipline).
  • Two randomized properties (100 inputs each) 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) and a sum-type tag read folds to the tag string.
  • Two pipeline tests, the constructor twins of the existing "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 shared IR generator now emits the constructor shapes. Both exp and scopedExpIn gained a saturated constructor application (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 reuses the incoming scope (the same category as application / if / object), well-scoped by construction. This feeds every existing Gen.scopedExp / Gen.exp consumer (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.
  • A new property runs the full single-pass optimizedExpression over 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, since floatIn only moves Lets and drops nothing.
  • Full suite green (648 examples), hlint clean, and the whole build is warning-free (clean rebuild carries zero -W warnings). 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.
  • Post-review cleanup: the fold's spine unwinder turned out to be a third copy of the same helper (spine in MagicDo, a local unwind in Uncurry), so one polymorphic unwindApp moved to IR.Types and all three passes now share it; a clean build's remaining pre-existing warnings (missing local signatures, unused imports, one shadowed name, a redundant pattern App import surfaced by the generator recompile) are cleared so the build is warning-free; and the Use const hlint hint is disabled repo-wide, since a named-but-ignored lambda binder (\_whatIsDiscarded → …) documents what is dropped where const erases it.

Unisay added 5 commits July 8, 2026 09:26
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.
@Unisay Unisay requested a review from Copilot July 8, 2026 08:43
@Unisay Unisay self-assigned this Jul 8, 2026
@Unisay Unisay marked this pull request as ready for review July 8, 2026 08:43
…-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.

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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 folds ReflectCtor over saturated sum-type constructor applications to the constructor tag string, and folds DataArgumentByIndex to the selected argument.
  • Introduced a shared unwindApp helper in IR.Types and 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.

Copilot AI left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Pull request overview

Copilot reviewed 15 out of 15 changed files in this pull request and generated no new comments.

@Unisay Unisay closed this Jul 8, 2026
@Unisay Unisay reopened this Jul 8, 2026
@Unisay Unisay assigned Unisay and unassigned Unisay Jul 8, 2026
@Unisay Unisay merged commit 62f29a7 into main Jul 8, 2026
3 checks passed
@Unisay Unisay deleted the issue-177/case-of-known-ctor branch July 8, 2026 09:23
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Fold ReflectCtor and DataArgumentByIndex over known constructor applications (case-of-known-constructor)

2 participants