Problem
The CoreFn case compiler is already a decision-tree compiler with redundant-test pruning (Note [Compiling case expressions to decision trees], MatchHistory), but the history only covers PatCtor: constructor patterns consult it before emitting a tag test, while every literal pattern — PatInteger, PatString, PatBoolean, PatChar, PatFloating, PatArrayLength — emits its eq test unconditionally, recording nothing (IR.hs mkClause: the literal arms vs the PatCtor arm).
Repro: Data.String.CodePoints.codePointAt (clauses codePointAt 0 "" = … / codePointAt 0 s = …). Clause 2 tests 0 == v, fails on its second pattern, falls through to clause 3 — which re-tests 0 == v although the answer is known in both branches. The compiled golden shows the redundant nested test with a dead then branch in the else arm.
A second, related gap: the history holds a single slot per scrutinee (Map Exp (CtorName, Bool)), so negative knowledge does not accumulate — after A fails and B fails, the record about A is overwritten, and pruning is lossy for sum types with three or more constructors.
Approach
Extend MatchHistory to literal tests with mutual-exclusivity semantics, same as constructors: after a positive v == 0, a repeated v == 0 prunes to success and v == 1 prunes to failure; after a negative v == 0, a repeated v == 0 prunes to failure and v == 1 is unknown and gets emitted. Generalize the store from one slot to accumulated knowledge per scrutinee (Map Exp (Map Tested Bool)), fixing the lossy-negatives limitation in the same move.
Prerequisites / Relations
No prerequisites; independent in the dependency graph. Relates to #172, which would register the code-size reduction. The out-of-scope future work below notes an interaction with the #178/#179/#180 inlining cascades, but this issue does not depend on them.
Verification / Measurement
The redundant 0 == v retest in Data.String.CodePoints.codePointAt (clause 3 re-testing what clause 2 already decided) disappears: the golden no longer shows the nested test with a dead then branch in the else arm. For sum types with three or more constructors, accumulated negative knowledge prunes the now-known tag retests that the single-slot history used to re-emit. Code-size effect tracked by #172.
Future work (out of scope here)
Redundancy the case compiler cannot see and therefore cannot prune: conditions already established around code spliced in by the inlining cascades (#178, #179, #180), repeated tests across separate case expressions on the same scrutinee (history lives within one mkCase), and guard expressions. If #172 shows these matter in practice, a separate IR-level predicate-propagation pass picks them up; until then this issue covers the observed cases.
Problem
The CoreFn case compiler is already a decision-tree compiler with redundant-test pruning (Note [Compiling case expressions to decision trees],
MatchHistory), but the history only coversPatCtor: constructor patterns consult it before emitting a tag test, while every literal pattern —PatInteger,PatString,PatBoolean,PatChar,PatFloating,PatArrayLength— emits itseqtest unconditionally, recording nothing (IR.hsmkClause: the literal arms vs the PatCtor arm).Repro:
Data.String.CodePoints.codePointAt(clausescodePointAt 0 "" = …/codePointAt 0 s = …). Clause 2 tests0 == v, fails on its second pattern, falls through to clause 3 — which re-tests0 == valthough the answer is known in both branches. The compiled golden shows the redundant nested test with a deadthenbranch in theelsearm.A second, related gap: the history holds a single slot per scrutinee (
Map Exp (CtorName, Bool)), so negative knowledge does not accumulate — afterAfails andBfails, the record aboutAis overwritten, and pruning is lossy for sum types with three or more constructors.Approach
Extend
MatchHistoryto literal tests with mutual-exclusivity semantics, same as constructors: after a positivev == 0, a repeatedv == 0prunes to success andv == 1prunes to failure; after a negativev == 0, a repeatedv == 0prunes to failure andv == 1is unknown and gets emitted. Generalize the store from one slot to accumulated knowledge per scrutinee (Map Exp (Map Tested Bool)), fixing the lossy-negatives limitation in the same move.Prerequisites / Relations
No prerequisites; independent in the dependency graph. Relates to #172, which would register the code-size reduction. The out-of-scope future work below notes an interaction with the #178/#179/#180 inlining cascades, but this issue does not depend on them.
Verification / Measurement
The redundant
0 == vretest inData.String.CodePoints.codePointAt(clause 3 re-testing what clause 2 already decided) disappears: the golden no longer shows the nested test with a deadthenbranch in theelsearm. For sum types with three or more constructors, accumulated negative knowledge prunes the now-known tag retests that the single-slot history used to re-emit. Code-size effect tracked by #172.Future work (out of scope here)
Redundancy the case compiler cannot see and therefore cannot prune: conditions already established around code spliced in by the inlining cascades (#178, #179, #180), repeated tests across separate case expressions on the same scrutinee (history lives within one
mkCase), and guard expressions. If #172 shows these matter in practice, a separate IR-level predicate-propagation pass picks them up; until then this issue covers the observed cases.