fix(ir): key a Let's binders in scope order in alphaKey (#349) - #353

Closes #349.

The bug

Common-subexpression elimination (Language.PureScript.Backend.IR.CSE) finds repeated pure subexpressions in one function body and hoists them into a shared local binding. It decides what counts as a repeat by canonicalizing each candidate to a key: alphaKey drops annotations and renames every binder bound within the expression to a positional $key<n> name, so — in the words of its own documentation — "two expressions have equal keys iff they are alpha-equivalent up to annotations". References that are free in the expression keep their own names, because they belong to the enclosing scope and two occurrences only mean the same thing if they name the same outer binder.

Its Let case collected every binder name of the Let into one rename map up front, then canonicalized all the right-hand sides under that single map:

    Let ann binds body → do
      -- Under unique binders no Let name can be referenced before it is
      -- bound, so all the groupings can enter the rename map up front.
      renames' ←
        foldlM
          ( \rs name → do
              name' ← mint
              pure (Map.insert name name' rs)
          )
          renames
          (filter (/= discardName) (bindingNames =<< toList binds))

The IR's scoping rule is where that shortcut fails. Note [Sequential scoping of Let bindings] fixes Let scoping as sequential, like Scheme's let*: a Standalone binding (the IR's non-recursive grouping, as opposed to a RecursiveGroup) does not have its own name in scope in its right-hand side, so a reference to that name from its own right-hand side resolves to an outer binder. Because the binder's map entry was already present when its own right-hand side was walked, a free reference sharing that name got canonicalized as if it were bound.

The stated iff then breaks in the "misses an equality" direction. Take two expressions in a scope that already binds x:

let x = x in x     -- binds a fresh name to the outer x, returns it
let y = x in y     -- the same thing, under a different binder name

They are alpha-equivalent — they differ only in the name chosen for the binder, and the right-hand-side x is a free occurrence of the same outer binder in both. alphaEq, the IR's alpha-equivalence relation, agrees. alphaKey did not (this block and the one at the end of the next section are verbatim GHCi output, before and after the fix):

alphaEq a b     = True
alphaKey a == b = False
keyA = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "$key0"))) :| []) (Ref () (Local (Name "$key0")))
keyB = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "x"))) :| []) (Ref () (Local (Name "$key0")))

In keyA the free x had been swallowed into the positional namespace as $key0; in keyB the identical free reference correctly survived as x.

The fix

The map is now threaded through the groupings instead of hoisted, which is the shape freshenBinders (the traversal that alpha-renames an expression's binders before a copy of it is pasted elsewhere) and the LetValues case of alphaKey itself already use:

    -- The groupings bind sequentially, so the map grows left to right.
    Let ann binds body → do
      (renames', binds') ← mapAccumM keyGrouping renames binds
      Let ann binds' <$> go renames' body

keyGrouping splits on the grouping kind, so each right-hand side is canonicalized under exactly the map that is in scope for it:

    -- A Standalone binding is non-recursive: its RHS does not see its
    -- own binder, so the RHS is canonicalized under the incoming map and
    -- the binder enters only afterwards. A RHS reference sharing the
    -- binder's name is therefore an occurrence of an outer binder and
    -- keeps its name, as it must.
    Standalone (bindAnn, name, expr) → do
      expr' ← go renames expr
      (renames', name') ← bindMinted renames name
      pure (renames', Standalone (bindAnn, name', expr'))
    -- Every member of a recursive group is in scope in every member's
    -- RHS, so the whole group enters the map before any RHS is walked.
    RecursiveGroup members → do

The discard binder _ keeps its exemption, now in bindMinted: it is exempt from the IR's binder-uniqueness invariant, so one Let can bind it several times (magic-do's discard statements), and nothing may reference it, so it takes no positional name:

  bindMinted ∷ Map Name Name → Name → State Natural (Map Name Name, Name)
  bindMinted rs name
    | name == discardName = pure (rs, name)

The two expressions now key equally, matching alphaEq:

alphaKey a == b = True
keyA = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "x"))) :| []) (Ref () (Local (Name "$key0")))
keyB = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "x"))) :| []) (Ref () (Local (Name "$key0")))

Test

Red first, at the level the bug manifests: two lambdas that differ only in a Let binder name are one alpha-equivalence class, so CSE must hoist them into one shared $cse0 binding. Wrapping each in a lambda is what makes it a candidate — lambda literals are one of the pass's effect-free candidate classes, a bare Let is not.

  it "hoists Lets whose Standalone RHS references an outer binder (#349)" do
    let shadowing name =
          abstraction (paramNamed (Name "$p")) $
            lets
              (pure (Standalone (noAnn, Name name, refLocal (Name "x"))))
              (refLocal (Name name))
        expr = application (application f (shadowing "x")) (shadowing "y")
        expected =
          lets
            (pure (bind0 (shadowing "x")))
            (application (application f cse0) cse0)
    cseExpression expr `shouldBe` expected

Verbatim failure on the parent commit — the pass returned the input unchanged, declining the hoist:

  1) CSE hoists Lets whose Standalone RHS references an outer binder (#349)
       expected: Let Nothing (Standalone (Nothing, Name "$cse0", AbsN Nothing (ParamNamed Nothing (Name "$p") :| []) (Let Nothing (Standalone (Nothing, Name "x", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "x"))))) :| []) (AppN Nothing (AppN Nothing (Ref Nothing (Local (Name "f"))) (Ref Nothing (Local (Name "$cse0")) :| [])) (Ref Nothing (Local (Name "$cse0")) :| []))
        but got: AppN Nothing (AppN Nothing (Ref Nothing (Local (Name "f"))) (AbsN Nothing (ParamNamed Nothing (Name "$p") :| []) (Let Nothing (Standalone (Nothing, Name "x", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "x")))) :| [])) (AbsN Nothing (ParamNamed Nothing (Name "$p") :| []) (Let Nothing (Standalone (Nothing, Name "y", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "y")))) :| [])

A second test pins the contrasting branch, which the fix must not disturb: a RecursiveGroup member's right-hand side does see its own binder, so two self-referencing groups differing only in the member name are alpha-equivalent and must still be shared. It is green on both sides of the fix — it guards the branch the rewrite introduces.

The existing property CSE / keys alpha-equivalent expressions equally cannot catch any of this: it draws generated expressions and uniquifies them, so it never presents a shadowed shape.

Impact on emitted code: none

The golden corpus is byte-identical — no golden.ir or golden.lua moved — which is the check that no CSE decision depended on the hoisted behaviour. Two independent reasons:

The direction of the bug was safe. A shadowed right-hand side keyed to a shape correct canonicalization can never emit for a Standalone binding, namely a reference to the binder's own positional name inside the binder's own right-hand side. So the bug could only make two alpha-equivalent expressions key differently — CSE declining a hoist it could have made — and never merge two occurrences that mean different things.

And it did not fire at all. uniquifyNames is the pipeline's entry pass, and every pass behind it, CSE included, declares passRequires = guc — the global-uniqueness condition, under which every binder in the program has a distinct name and no free reference can collide with one.

What the fix buys is that alphaKey no longer depends on that condition for correct name resolution. It was the last name-resolving traversal in the IR that did not implement the sequential rule; freshenBinders was the same bug (#345, fixed in #347). A pass reordering that puts CSE ahead of uniquification, or a property fed deliberately non-uniquified input the way IR Optimizer / inlines expressions referenced once is, would turn a latent divergence into a visible one. The module's == GUC section and alphaKey's documentation are updated to say what GUC is still load-bearing for (the exactness of the hoist-point scope guard) and what it no longer is.

Verification

cabal test all green — 1236 examples, 0 failures — with no golden churn. fourmolu and hlint clean; the two touched modules recompile with no warnings. The Hedgehog-driven groups were stressed with fresh seeds: --match "CSE" and --match "IR Optimizer", 12 runs each, all green.