CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys #349

Problem

Common-subexpression elimination groups repeated expressions by a canonical key. alphaKey in Language.PureScript.Backend.IR.CSE computes that key: it drops annotations and renames every binder bound within the expression to a positional $key<n> name, so — in the words of its own Haddock — "two expressions have equal keys iff they are alpha-equivalent up to annotations". Free references 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 collects every binder name of the Let into one rename map up front and then canonicalizes 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))
      let renameBound (bindAnn, name, expr) =
            (bindAnn,Map.findWithDefault name name renames',)
              <$> go renames' expr
      Let ann <$> traverse (traverse renameBound) binds <*> go renames' body

That is the exact shape #345 fixed in freshenBinders, the traversal that alpha-renames an expression's binders before a copy of it is pasted elsewhere — down to the wording of the comment, which until #347 ended (as in 'freshenBinders'). The comment names the precondition the shortcut needs, and the IR's scoping rule is where it fails. Note [Sequential scoping of Let bindings] says a Standalone binding is non-recursive: its own name is not 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 is already present when its own right-hand side is walked, a free reference sharing that name is canonicalized as if it were bound.

The 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 agrees. alphaKey does not:

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 has been swallowed into the positional namespace as $key0; in keyB the identical free reference correctly survives as x.

Impact

Only in the safe direction, and only on input the compiler does not currently produce.

The direction matters, so it is worth being explicit: a shadowed right-hand side maps to a key shape that correct canonicalization can never emit for a Standalone binding, namely a reference to the binder's own positional name in the binder's own right-hand side. So the bug can only make two alpha-equivalent expressions key differently — CSE declines a hoist it could have made — and never the reverse. It cannot merge two occurrences that mean different things.

And it does not fire today, for the same reason #345 had no effect on emitted code: uniquifyNames is the pipeline's entry pass and the only one whose stated precondition is merely wellScoped; 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 makes it worth closing anyway is that alphaKey is now the last name-resolving traversal in the IR that does not implement the sequential rule. Note [Sequential scoping of Let bindings] lists the traversals that must agree — countFreeRefs, alphaEq, the well-scopedness lint, qualifyTopRefs, uniquifyNamesInExpr — and freshenBinders joined them in #347. A pass reordering that puts CSE ahead of uniquification, or a property fed deliberately non-uniquified generated input the way IR Optimizer / inlines expressions referenced once is, turns a latent divergence into a visible one.

Approach

The same change #347 made to freshenBinders: thread the map through the groupings instead of hoisting it. A Standalone right-hand side is canonicalized under the incoming map and only then does its binder enter; a RecursiveGroup's members all enter before any of their right-hand sides is walked.

    Let ann binds body → do
      (renames', binds') ← mapAccumM keyGrouping renames binds
      Let ann binds' <$> go renames' body

freshenBinders after #347 is the working reference for both the grouping helper and the discard-binder exemption, which must survive here too: _ is exempt from the uniqueness invariant, one Let can bind it several times, and nothing references it, so it takes no rename. The LetValues case of alphaKey already threads correctly and needs no change.

Verification

The change is a no-op on globally-unique input, where the two orders agree, so the golden corpus should stay byte-identical — that is the check that no CSE decision depended on the hoisted behaviour. The existing CSE property keys alpha-equivalent expressions equally restricts itself to input the generators uniquify, so it cannot catch this; the red-first test is the pair above, which must key equally and currently does not.

Prerequisites / Relations

Independent. #345 is the same bug in freshenBinders, fixed by #347, which carries the reasoning and the shape of the fix; this was surfaced while implementing it.

Acceptance criteria

• let x = x in x and let y = x in y receive equal alphaKey values, matching alphaEq.
• A Standalone right-hand side is canonicalized before its own binder enters the map; a RecursiveGroup's members all enter before any of theirs.
• The discard binder _ remains unrenamed and out of the map.