Skip to content

Push not through ordering comparisons to their complement - #313

Merged
Unisay merged 1 commit into
mainfrom
issue-238/boolean-peephole
Jul 27, 2026
Merged

Push not through ordering comparisons to their complement#313
Unisay merged 1 commit into
mainfrom
issue-238/boolean-peephole

Conversation

@Unisay

@Unisay Unisay commented Jul 27, 2026

Copy link
Copy Markdown
Collaborator

Closes #238.

Issue #238 asks for two boolean peepholes: fusing one-armed conditionals into and/or, and pushing not through the four ordering comparisons. The first half already ships: reduceBooleanIf (the IR rule that collapses an if with boolean-literal branches into short-circuit operators) has covered if p then b else false → p and b and if p then true else b → p or b since #203, with tests under "collapses a half-literal boolean if to and/or". No evaluation-order gate is needed there because Lua's and/or short-circuit exactly like the branch did. This PR implements the second half.

foldPrimNot (the constant-folding case for the IR's logical-not node, which previously only folded a boolean literal and cancelled double negation) now pushes not through an ordering primop to its complement: not (a < b) becomes a >= b, and likewise <=>, ><=, >=<.

The flip is not unconditionally sound, which is where the design effort went. not (a < b) ⟷ a >= b holds 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's Number semantics require. The prelude's ordNumberImpl maps NaN to GT (its body is if x < y then lt elseif x == y then eq else gt, and both tests are false for NaN), so PureScript's NaN >= b is true, which the residual not (NaN < b) computes correctly, while raw Lua NaN >= b is 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, or String. 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-typed Int values 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-ASCII Char literals too. A Float literal is no witness (the other operand can still be NaN), and a comparison of two non-literals stays wrapped. The Lua-level foldNotEqual (which rewrites not (a == b) to a ~= 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's not (a < b).

The dominant beneficiary is the residual a > comparison leaves behind once its Ordering decision tree folds (#180/#203): compare a b == GT collapses to not (a < b) and not (a == b). With the flip, Golden.Primops.Test/golden.lua moves from

if not(n < 0) and n ~= 0 then acc, n = acc + n, n - 1 else return acc end

to

if n >= 0 and n ~= 0 then acc, n = acc + n, n - 1 else return acc end

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 Char case, the two decline cases (no witness, Float witness), and the end-to-end collapse of if (x < 0) then false else r to x >= 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-verified eval/golden.txt oracles 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 one not node per firing, so it cannot loop with the fixpoint driver).

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
Unisay force-pushed the issue-238/boolean-peephole branch from 7a0d78a to f031251 Compare July 27, 2026 09:14
@Unisay Unisay self-assigned this Jul 27, 2026
@Unisay
Unisay marked this pull request as ready for review July 27, 2026 09:24
@Unisay
Unisay merged commit 374887c into main Jul 27, 2026
2 checks passed
@Unisay
Unisay deleted the issue-238/boolean-peephole branch July 27, 2026 09:24
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.

Boolean peephole: short-circuit fusion and push not through all ordering comparisons

1 participant