Title: CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys · Issue #349 · purescript-lua/purescript-lua · GitHub
Open Graph Title: CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys · Issue #349 · purescript-lua/purescript-lua
X Title: CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys · Issue #349 · purescript-lua/purescript-lua
Description: 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 pos...
Open Graph Description: 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 bin...
X Description: 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 bin...
Opengraph URL: https://github.com/purescript-lua/purescript-lua/issues/349
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys","articleBody":"## Problem\n\nCommon-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\u003cn>` 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.\n\nIts `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:\n\n```haskell\n Let ann binds body → do\n -- Under unique binders no Let name can be referenced before it is\n -- bound, so all the groupings can enter the rename map up front.\n renames' ←\n foldlM\n ( \\rs name → do\n name' ← mint\n pure (Map.insert name name' rs)\n )\n renames\n (filter (/= discardName) (bindingNames =\u003c\u003c toList binds))\n let renameBound (bindAnn, name, expr) =\n (bindAnn,Map.findWithDefault name name renames',)\n \u003c$> go renames' expr\n Let ann \u003c$> traverse (traverse renameBound) binds \u003c*> go renames' body\n```\n\nThat 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.\n\nThe iff then breaks in the \"misses an equality\" direction. Take two expressions in a scope that already binds `x`:\n\n```\nlet x = x in x -- binds a fresh name to the outer x, returns it\nlet y = x in y -- the same thing, under a different binder name\n```\n\nThey 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:\n\n```\nalphaEq A B = True\nalphaKey A == B = False\nkeyA = Let () (Standalone ((),Name \"$key0\",Ref () (Local (Name \"$key0\"))) :| []) (Ref () (Local (Name \"$key0\")))\nkeyB = Let () (Standalone ((),Name \"$key0\",Ref () (Local (Name \"x\"))) :| []) (Ref () (Local (Name \"$key0\")))\n```\n\nIn `keyA` the free `x` has been swallowed into the positional namespace as `$key0`; in `keyB` the identical free reference correctly survives as `x`.\n\n## Impact\n\nOnly in the safe direction, and only on input the compiler does not currently produce.\n\nThe 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.\n\nAnd 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.\n\nWhat 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.\n\n## Approach\n\nThe 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.\n\n```haskell\n Let ann binds body → do\n (renames', binds') ← mapAccumM keyGrouping renames binds\n Let ann binds' \u003c$> go renames' body\n```\n\n`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.\n\n## Verification\n\nThe 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.\n\n## Prerequisites / Relations\n\nIndependent. #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.\n\n## Acceptance criteria\n\n- `let x = x in x` and `let y = x in y` receive equal `alphaKey` values, matching `alphaEq`.\n- A `Standalone` right-hand side is canonicalized before its own binder enters the map; a `RecursiveGroup`'s members all enter before any of theirs.\n- The discard binder `_` remains unrenamed and out of the map.\n","author":{"url":"https://github.com/Unisay","@type":"Person","name":"Unisay"},"datePublished":"2026-07-29T09:26:56Z","url":"https://github.com/purescript-lua/purescript-lua/issues/349"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:09b6be3a-079b-5e41-e33c-0c6ec5d82b3d |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | 8242:11EACE:7209B8:9A814F:6B00DB6F |
| html-safe-nonce | 00693a0a31fd2040d800c88b249b9226dba8b0628f838dcb37ce79fdd62e1322 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4MjQyOjExRUFDRTo3MjA5Qjg6OUE4MTRGOjZCMDBEQjZGIiwidmlzaXRvcl9pZCI6IjQ1MDM5NTY3ODU3NjExNDc3NTkiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | 1c387956c1108baf7b3042fcf994b55b61de0277fd35eebd90921acd6403e6ba |
| hovercard-subject-tag | issue:5007653905 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/purescript-lua/purescript-lua/349/issue_layout |
| twitter:image | https://opengraph.githubassets.com/33065e68185df949e8984e3c91f038269d03de36c850596a33c40c21f9987892/purescript-lua/purescript-lua/issues/349 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/33065e68185df949e8984e3c91f038269d03de36c850596a33c40c21f9987892/purescript-lua/purescript-lua/issues/349 |
| og:image:alt | 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 bin... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | Unisay |
| hostname | github.com |
| expected-hostname | github.com |
| None | 043c3f30fbcbe2c6c8e729e10cbbbc90c406546f9fbbb67c648d38f6b7d16daf |
| turbo-cache-control | no-preview |
| go-import | github.com/purescript-lua/purescript-lua git https://github.com/purescript-lua/purescript-lua.git |
| octolytics-dimension-user_id | 131581790 |
| octolytics-dimension-user_login | purescript-lua |
| octolytics-dimension-repository_id | 587200487 |
| octolytics-dimension-repository_nwo | purescript-lua/purescript-lua |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 587200487 |
| octolytics-dimension-repository_network_root_nwo | purescript-lua/purescript-lua |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 5425dc24e8bd8d6fca9641a12afc984825a43875 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width