Push not through ordering comparisons to their complement - #313
Merged
Conversation
Extend foldPrimNot with the complement flip: not (a < b) rewrites to a >= b, and likewise for <=, >, >= (issue #238). The flip is exact only over a domain Lua orders totally, so it is gated on a literal operand of a NaN-free kind (Int, Char, or String) witnessing the comparison's type. A Float literal is no witness: the other operand can be NaN at runtime, where every Lua comparison is false, and the wrapped form is exactly PureScript's >= on Number (ordNumberImpl maps NaN to GT). The dominant beneficiary is the residual a > comparison leaves once its Ordering decision tree folds: not(n < 0) and n ~= 0 now emits as n >= 0 and n ~= 0 across the affected goldens; eval goldens are unchanged. The other half of issue #238, fusing one-armed boolean conditionals into and/or, already ships since issue #203 (reduceBooleanIf's half-literal cases).
Unisay
force-pushed
the
issue-238/boolean-peephole
branch
from
July 27, 2026 09:14
7a0d78a to
f031251
Compare
Unisay
marked this pull request as ready for review
July 27, 2026 09:24
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 #238.
Issue #238 asks for two boolean peepholes: fusing one-armed conditionals into
and/or, and pushingnotthrough the four ordering comparisons. The first half already ships:reduceBooleanIf(the IR rule that collapses anifwith boolean-literal branches into short-circuit operators) has coveredif p then b else false → p and bandif p then true else b → p or bsince #203, with tests under "collapses a half-literal boolean if to and/or". No evaluation-order gate is needed there because Lua'sand/orshort-circuit exactly like the branch did. This PR implements the second half.foldPrimNot(the constant-folding case for the IR's logical-notnode, which previously only folded a boolean literal and cancelled double negation) now pushesnotthrough an ordering primop to its complement:not (a < b)becomesa >= b, and likewise<=→>,>→<=,>=→<.The flip is not unconditionally sound, which is where the design effort went.
not (a < b) ⟷ a >= bholds only when the compared domain is totally ordered, and Lua numbers are not: every comparison against NaN is false. Worse, the wrapped form is exactly what PureScript'sNumbersemantics require. The prelude'sordNumberImplmaps NaN toGT(its body isif x < y then lt elseif x == y then eq else gt, and both tests are false for NaN), so PureScript'sNaN >= bis true, which the residualnot (NaN < b)computes correctly, while raw LuaNaN >= bis false. An ungated flip would change the observable output of a well-typed program.The gate: the rewrite fires only when one operand is a literal of a NaN-free kind —
Int,Char, orString. Under the optimizer's standing well-typedness assumption (Note [IR is assumed well-typed]) such a literal pins both operands' type to a domain Lua orders totally: well-typedIntvalues are integral doubles, and Lua's string order is total for any byte content — the flip needs only totality, not agreement with codepoint order, so unlike the ASCII-gated constant fold of #222 it covers non-ASCIICharliterals too. AFloatliteral is no witness (the other operand can still be NaN), and a comparison of two non-literals stays wrapped. The Lua-levelfoldNotEqual(which rewritesnot (a == b)toa ~= b— sound by definition of~=) is deliberately not extended: it also runs over raw hand-written FFI code, where no typing licence exists and a NaN can legitimately flow through an author'snot (a < b).The dominant beneficiary is the residual a
>comparison leaves behind once itsOrderingdecision tree folds (#180/#203):compare a b == GTcollapses tonot (a < b) and not (a == b). With the flip,Golden.Primops.Test/golden.luamoves fromto
and the same one-negation-per-site shrink lands in seven more goldens (JoinPoints, Loopification, MutualLoopification, NativeLoopsGuard, NativeLoopsST, CprResult, UncurryEffect).
Verification: seven focused optimizer tests, written and confirmed red before the implementation — one per flip direction and witness kind, the non-ASCII
Charcase, the two decline cases (no witness,Floatwitness), and the end-to-end collapse ofif (x < 0) then false else rtox >= 0 and r. One existing #203 expectation updated to the improved residual. All structural golden churn is exactly the flip shape shown above; the hand-verifiedeval/golden.txtoracles are untouched, which is the semantic safety net. Full suite green (1142 examples), and the "IR Optimizer" spec group was additionally re-run 66× with fresh seeds (the rule strictly removes onenotnode per firing, so it cannot loop with the fixpoint driver).