Modulo-8 Canonicalization of Remaining-Bytes Tests in the Gleam Bit-Array Decision Tree

1. Introduction ¶

A compiler targeting multiple backends faces a persistent tension between front-end expressiveness and the economy of the generated code. Pattern matching, in particular, is a feature whose surface syntax remains uniform across backends but whose efficient compilation is highly target-specific. JavaScript lacks a native pattern-matching construct; consequently, a Gleam pattern must be lowered to a chain of conditional statements and indexing expressions evaluated by the host engine at runtime. The selection and grouping of these emitted conditions directly dictate both execution performance and code-size overhead.

Gleam supports first-class bit-array patterns inherited from Erlang [1]. A bit-array pattern decomposes a binary value into a sequence of segments, each consuming either a constant or variable number of bits. The exhaustiveness checker compiles these patterns into a decision tree following the formalisms of Maranget [2] and Pettersson [3]. On the JavaScript target, the leaves of this tree consist of predicate-and-extraction sequences over the input array’s bit length and binary content, while the internal nodes evaluate the cumulative bit offset and byte-alignment constraints.

This paper addresses a specific internal-node category: the remaining-bytes test, emitted when a pattern includes a residual segment specified to consume the remainder of the input as whole bytes. In such cases, the compiler emits a check of the form

where bitSize represents the total bit-length of the input array and $c$ is the cumulative bit offset accumulated by preceding constant-size segments. The quantity $\texttt{bitSize} - c$ defines the residual length; the test verifies whether this residual constitutes an integer number of bytes.

We observe that $c$ and $c \bmod 8$ are interchangeable for the purposes of this Boolean test. Because the unmodified compiler failed to normalize the constant modulo 8 prior to constructing the node, the downstream tree-merging logic was unable to identify structurally equivalent branches. Introducing this normalization requires modifying exactly one location in the decision-tree construction routine.

The remainder of this paper develops this observation, details its formal justification, measures its precise impact on generated JavaScript assets, and discusses the scope of the architectural intervention.

2. Related work ¶

2.1 Pattern matching compilation ¶

The redundancy elimination described here differs from traditional decision-tree optimization techniques in scope: it operates locally on a single test category and is derived from arithmetic identities rather than global tree-shape transformations. The broader literature addresses the global problem. Maranget [2] evaluates the trade-offs between compiled code size and worst-case test counts, a problem formalized by Pettersson [3]. Sestoft [4] demonstrates that decision trees can be rendered backtracking-free through deterministic construction heuristics.

2.2 Bit-array pattern matching ¶

Bit-pattern matching was introduced as a primitive feature in Erlang and formalized by Gustafsson and Sagonas [1]. Their work frames bit-array decision-tree compilation as an extension of the algebraic-data-type case and introduces optimizations to coalesce successive size checks when constraints are mutually compatible.

The optimization presented here represents an instance of this combinability property, lifted to an algebraic abstraction. This implementation originated during the investigation of a broader tree-reduction issue in the core Gleam compiler repository [5]; the modulo-8 normalization was subsequently isolated as a distinct, narrower optimization.

2.3 Canonical forms for redundancy elimination ¶

Compiler optimizations routinely rely on identifying when syntactically distinct expressions denote equivalent runtime values. Common subexpression elimination (CSE), value numbering, and partial-redundancy elimination (PRE) [6] depend on canonicalization passes to expose semantic equivalence.

The normalization applied here defines an equivalence class within a finite cyclic group (the integers modulo 8) using a uniform representative. This transformation enables downstream structural merging passes that were previously obstructed by surface-level variation in the literal terms.

2.4 Modular arithmetic in compilation ¶

Strength reduction, alignment analysis, and address arithmetic frequently exploit modular integer identities, as surveyed in standard compilation texts [7], [8]. Framing modular reduction as a canonicalizer prior to deduplication aligns with the term-rewriting tradition: establishing a normal form for terms in an algebra such that semantic equivalence implies syntactic identity [9]. Our normalization enforces a normal form on the constant parameter of the alignment test family, guaranteeing that equivalence maps directly to identity.

3. Background ¶

3.1 Bit-arrays in Gleam ¶

A bit-array in Gleam is an immutable sequence of bits whose length is exposed at runtime. The language provides a pattern syntax to deconstruct such values:

case input {
  <<header:8, body:bytes-size(2), tail:bits>> -> ...
  _ -> ...
}

Each segment specifies an allocation type (int, bytes, bits) and a size constraint, which may be a constant, a variable bound earlier in the pattern match, or an arithmetic expression. The compiler must verify at each node in the decision tree that the input sequence retains sufficient bits to satisfy the active segment, that the constraint matches the absolute runtime length, and that the pointer respects byte alignment where required.

3.2 The decision-tree intermediate representation ¶

The exhaustiveness checker constructs a directed decision tree where internal nodes represent structural predicates and leaves dictate pattern-matching outcomes. For bit-arrays, these predicates include BitArrayTest::CatchAllIsBytes { size_so_far }, which is injected whenever a segment of type bytes with no explicit size specifier is matched to consume the remainder of the input. The formal semantics of this test are:

where size_so_far.constant represents the absolute bit offset accumulated by prior constant-size segments, and bitSize is the dynamic runtime length of the array. (The size_so_far structure additionally tracks variable-size segment inputs; this optimization isolates the constant component exclusively.)

3.3 The JavaScript backend ¶

The JavaScript backend lowers each CatchAllIsBytes node to a literal expression of the form (bitSize - c) % 8 === 0 in the emitted code, rendering $c$ as a numeric literal. The downstream decision-tree merging logic operates via structural comparison of expression trees, treating two CatchAllIsBytes nodes as identical if and only if their size_so_far.constant fields match exactly as integers. The backend contains no native semantic engine to evaluate mathematical equivalence.

Consequently, if two distinct patterns produce CatchAllIsBytes tests with constants $c_1 \neq c_2$ where $c_1 \equiv c_2 \pmod{8}$, the merging logic treats them as distinct nodes, forcing the code generator to emit duplicate Boolean tests under different syntactic signatures.

4. Problem statement ¶

Consider the following alternative patterns occurring within a single case expression:

<<_:8, rest:bytes>>      -> ...
<<_:16, rest:bytes>>     -> ...

Both paths terminate with a bytes catch-all segment requiring the remaining input to be byte-aligned. The first pattern accumulates an offset of $c_1 = 8$ prior to the catch-all; the second accumulates $c_2 = 16$. The intermediate representation constructs two distinct internal nodes:

The backend subsequently emits two discrete checks:

(bitSize - 8) % 8 === 0
(bitSize - 16) % 8 === 0

The first expression requires 23 characters, the second 24, resulting in 47 characters of raw Boolean logic excluding wrapping syntax, blocks, and logical conjunctions. At runtime, the JavaScript engine must evaluate both expressions independently, executing two integer subtractions, two modulus operations, and two strict equality tests.

Individually, both conditions are semantically equivalent to bitSize % 8 === 0 because both subtrahends are multiples of the modulus. Evaluated together, they constitute a redundant check obscured by syntactic variation. Because the tree merger evaluates nodes strictly on syntactic identity, it cannot coalesce these branches, resulting in bloated emitted assets.

5. The normalization ¶

Let $g(c)$ denote the smallest non-negative residue of $c$ modulo 8, that is, $g(c) = c \bmod 8$ with the convention $g(c) \in \{0, 1, 2, 3, 4, 5, 6, 7\}$. We apply the following proposition:

which follows directly from the congruence $c \equiv g(c) \pmod 8$ and the preservation of congruence under subtraction. The mapping

establishes a canonical normal form for parameter $c$ within the test family $\{(b - c) \bmod 8 = 0 : c \in \mathbb{Z}\}$.

The target routine resides in compiler-core/src/exhaustiveness.rs, in the RemainingBytes arm of the for-loop inside CaseToCompile::bit_array_to_tests. Prior to the change, that arm consumed previous_end directly without transformation:

ReadSize::RemainingBytes => tests.push_back(BitArrayTest::CatchAllIsBytes {
    size_so_far: previous_end.clone(),
}),

We modify this implementation to normalize size_so_far.constant to its modulo-8 representative before the test is inserted into the tree. The constant field has type BigInt (from the num_bigint crate), which implements Rem for shared references, making &normalized.constant % 8 valid and idiomatic Rust:

ReadSize::RemainingBytes => {
    // (bitSize - c) % 8 === 0 is equivalent to
    // (bitSize - (c % 8)) % 8 === 0 for any integer c,
    // because c ≡ c%8 (mod 8). This ensures
    // structurally identical JS checks regardless of
    // the accumulated offset.
    let mut normalized = previous_end.clone();
    normalized.constant = &normalized.constant % 8;
    tests.push_back(BitArrayTest::CatchAllIsBytes {
        size_so_far: normalized,
    });
}

The transformation introduces a minimal delta (+11 / -3 lines), adding an explicit mutable binding and a modular reduction step. Following this change, every CatchAllIsBytes predicate generated for a target variable guarantees a constant bounded within $[0, 7]$. Identical residues yield identical syntactic structures, allowing the downstream tree-merging pass to deduplicate the nodes without architectural modification.

Applying this to the example in Section 4, both branches now evaluate to $\texttt{CatchAllIsBytes}\{c = 0\}$. The JavaScript code generator explicitly detects when size_so_far.is_zero(), emitting bitSize % 8 === 0 directly rather than (bitSize - 0) % 8 === 0, so no subsequent simplification pass is involved. The alternation is decided by a single test rather than two.

6. Justification and generalizations ¶

6.1 Soundness ¶

The transformation relies on the integer congruence identity stated in Section 5. This identity holds across all integers and maps directly to JavaScript’s Number representation within the safe-integer bounds $[-(2^{53} - 1),\, 2^{53} - 1]$. Because runtime bit-array lengths in Gleam are strictly bounded by representable memory limits, the operations remain clear of the safe-integer boundary, ensuring arithmetic correctness.

6.2 Semantic transparency to other passes ¶

The normalization targets the literal constant component exclusively; the variable segment polynomial within size_so_far remains untouched. Downstream compilation components, including the generation passes that compute the exact absolute byte offsets for variable extraction, receive the original structural composition intact. This guarantees that data-extraction offsets remain correct while optimizing the alignment check.

6.3 Why modulo 8 specifically ¶

The selection of 8 as the operational modulus is mandated by the underlying target architecture: data storage is byte-addressed, the check assesses whether the residual bit-count forms a whole number of bytes, and the test node is strictly generated for bytes-typed matches. This property is validated in compiler-core/src/exhaustiveness.rs, where the ReadSize::RemainingBytes variant is only matched if the segment carries the explicit BitArrayOption::Bytes annotation (has_bytes_option()). A version of the optimization for hypothetical patterns over larger units would use the corresponding word size as modulus, but no such patterns exist in the current language surface.

6.4 Larger families of equivalence ¶

Reduction modulo 8 represents a localized instance of arithmetic canonicalization. More expansive strategies could evaluate intermediate byte-alignment boundaries, symbolic reduction of variable-contribution expressions, or algebraic cancellations over the residual size formulas. These implementations introduce significant architectural complexity and are deferred to future work (Section 9).

7. Effects on generated code ¶

7.1 Decision tree structure ¶

For the alternation <<_:8, rest:bytes>> and <<_:16, rest:bytes>> outlined in Section 4, the original compiler constructs a tree containing two adjacent internal nodes executing identical semantic checks. Figure 1 illustrates the structural transformation of the tree topology.

By ensuring the constants are equivalent under the modular reduction pass, the structural merger recognizes the nodes as identical, compressing the adjacent branches into a single shared test conditional.

7.2 Emitted JavaScript overhead ¶

The alignment-test payload transitions as follows:

• Before normalization, two separate expressions are emitted:
  • (bitSize - 8) % 8 === 0, occupying 23 characters, requiring one subtraction, one modulus, and one equality at runtime
  • (bitSize - 16) % 8 === 0, occupying 24 characters, requiring one subtraction, one modulus, and one equality at runtime
• After normalization, a single shared expression is emitted:
  • bitSize % 8 === 0, occupying 17 characters, requiring one modulus and one equality at runtime

The combined payload contracts from 47 characters and six arithmetic operations to 17 characters and two arithmetic operations: a 64% character reduction and a 67% operation reduction within the alignment-check sub-expression alone.

7.3 Asymptotic behavior ¶

Generalizing, suppose a case expression contains $K$ alternatives whose constant-size segments before the residual bytes catch-all sum, in each alternative, to a distinct multiple of 8 (that is, $c_k = 8 m_k$ for $k = 1, \ldots, K$ with $m_k$ pairwise distinct positive integers). Before normalization the decision tree contains $K$ distinct CatchAllIsBytes nodes; the JavaScript output emits $K$ distinct alignment checks, each evaluated independently at runtime. After normalization, all $K$ nodes carry the constant $0$ and coalesce into a single shared check. The character-count saving on the alignment-check sub-expression is:

which for small $m_k$ scales linearly in $K$ at roughly 24 characters per duplicate, less the 17-character cost of the surviving shared check. The runtime saving is the elimination of $K - 1$ subtraction-modulus-equality triples per evaluation of the alternation. The normalization is monotone with respect to the downstream merger: a structural comparison that previously failed now succeeds, and no comparison that previously succeeded is disrupted.

7.4 Empirical verification ¶

We did not conduct an aggregate measurement across a representative corpus of real-world Gleam packages. The structural guarantee is that on any program in which two byte-aligned catch-all tests previously appeared as distinct expressions, the post-normalization output contains strictly fewer expressions, and all other downstream transformations are preserved. In the test corpus accompanying the change, the snapshot files for the JavaScript backend’s bit-array tests required regeneration to reflect the absence of the duplicated checks; the regeneration was committed separately from the optimization itself for review legibility.

8. Implementation notes ¶

8.1 Modularity and locality ¶

The change touches a single location, the RemainingBytes arm of the segment-loop in CaseToCompile’s test-construction routine, and a single statement within that arm. There are no new types, no new helper functions, no new fields on existing structures. The patch contains 11 insertions and 3 deletions, ensuring minimal maintainability overhead.

8.2 Test snapshot regeneration ¶

The decision-tree-driven JavaScript code generator is tested by snapshot comparison on a moderately large corpus of bit-array patterns. Fifteen of these snapshots embedded the old, un-normalized form of the catch-all check and required mechanical update. We regenerated the snapshots in a single commit separate from the optimization itself. The two-commit structure was retained in the final history because the snapshot diff would otherwise have inflated the optimization commit and obscured the fact that it is a two-line semantic change.

8.3 Subsystem interactions ¶

The optimization executes within the localized scope of CatchAllIsBytes processing. It does not interact with variable-size segment handling, the optional byte-aligned annotations, or the bits-typed catch-all (whose semantics permits a non-byte-aligned residue and to which no modulo-8 test applies). Existing test suites pass without regressions.

9. Discussion ¶

9.1 Scope management and unbundling ¶

The form of the change presented here is not the form in which it was first proposed. An earlier draft contained two further changes: a generic simplify() post-pass on the constructed decision tree, intended to coalesce branches with structurally identical bodies, and a modification to the split-order heuristic that prefers CatchAllIsBytes tests as discriminators when available. Reviewers observed that the split-order modification appeared to produce larger generated code on several patterns in the existing test corpus, with no clearly compensating benefit on others. The simplify() post-pass, once the split-order change was reverted, produced no observable improvement on the test corpus; its theoretical motivation was sound, but its empirical case was insufficient.

The decision was to ship the modulo-8 normalization alone. This was the only one of the three changes whose benefit could be characterized in closed form (Section 6.1) and whose empirical effect on generated code was unambiguously positive. The two larger changes were dropped from the patch and are recorded as candidates for future work, to be revisited only with corpus data sufficient to demonstrate net improvement.

We mention the episode because it reflects a discipline that is sometimes left implicit in compiler-engineering practice: shipping a small, demonstrably correct optimization rather than waiting until a larger and less defensible bundle is ready. The smaller change reaches users sooner; its effects can be measured in isolation; and the larger changes, once revisited, can be evaluated against the new baseline rather than against the original.

9.2 Upstream canonicalization patterns ¶

The optimization is a small instance of a recurring compiler pattern. Many transformations that operate on intermediate-representation graphs do so by structural identity: two nodes with identical structure, in some inductive sense, are merged. The transformation succeeds or fails depending on whether equivalent nodes are also structurally identical. When the equivalence is finer than the structural identity, an upstream canonicalization is required.

The modulo-8 reduction is this canonicalization: the equivalence class is “constants congruent modulo 8 in the alignment test”, the canonical representative is the smallest non-negative residue, and the deduplication that was previously masked by surface variation now succeeds. In its specific form the optimization saves a few JavaScript instructions per affected program; in its general form it is an instance of a discipline that compiler authors apply to every level of representation when they hope to deduplicate by syntactic comparison.

9.3 Limitations ¶

Three limitations bound the work.

Single test category. The normalization addresses only CatchAllIsBytes. Other test categories in the bit-array decision tree, including the variable-size constraints whose handling involves more elaborate symbolic reasoning, are not subject to it. We do not claim this coverage is complete; we claim only that this particular redundancy is now eliminated.

No measurement of aggregate effect. We do not present a quantitative measurement of bytes saved across a representative corpus, as discussed in Section 7.4.

Deferred broader optimizations. The two transformations dropped from the original draft, the simplify() post-pass and the split-order heuristic, remain unimplemented. Their empirical case is unclear, and we do not advance an opinion in either direction. Future work might revisit them under a measurement methodology adequate to discriminate among hypotheses about pattern shape.

10. Conclusion ¶

We described a modular-arithmetic normalization in the Gleam compiler’s bit-array decision-tree construction that eliminates a class of duplicate JavaScript checks previously emitted for byte-aligned remaining-bytes patterns. The optimization is justified by an elementary congruence, costs two additional lines of executable code and the modification of one existing line, and admits a closed-form correctness argument. We discussed the decision to ship the normalization independently of two larger and less defensible optimizations originally bundled with it, and argued that the unbundling reflects a discipline appropriate to landing changes in a mature compiler. The work is a concrete instance of a recurring compiler principle: canonicalizing upstream of a structural-deduplication pass reduces generated-code size more reliably than adding semantic reasoning to the merger itself.

References ¶

[1] P. Gustafsson and K. Sagonas, “Efficient Manipulation of Binary Data Using Pattern Matching,” Journal of Functional Programming, vol. 16, no. 1, pp. 35–74, Jan. 2006. DOI: 10.1017/S095679680500564X

[2] L. Maranget, “Compiling Pattern Matching to Good Decision Trees,” in Proceedings of the 2008 ACM SIGPLAN Workshop on ML, pp. 35–46, 2008. DOI: 10.1145/1411304.1411319

[3] M. Pettersson, “A Term Pattern-Match Compiler Inspired by Finite Automata Theory,” in Proceedings of the 4th International Conference on Compiler Construction (CC ‘92), Lecture Notes in Computer Science, vol. 641, pp. 258–270, Springer, 1992.

[4] P. Sestoft, “ML Pattern Match Compilation and Partial Evaluation,” in Partial Evaluation, Lecture Notes in Computer Science, vol. 1110, pp. 446–464, Springer, 1996.

[5] Gleam Compiler Issue #4524: Optimise decision tree for bit arrays, gleam-lang/gleam GitHub repository, opened 2024. Available: https://github.com/gleam-lang/gleam/issues/4524

[6] J. Knoop, O. Rüthing, and B. Steffen, “Lazy Code Motion,” in Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation (PLDI ‘92), pp. 224–234, 1992. DOI: 10.1145/143095.143136

[7] A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed. Boston: Pearson/Addison-Wesley, 2007.

[8] S. S. Muchnick, Advanced Compiler Design and Implementation. San Francisco: Morgan Kaufmann, 1997.

[9] F. Baader and T. Nipkow, Term Rewriting and All That. Cambridge: Cambridge University Press, 1998.