Skip to content

Fold array-length and indexing on manifest array literals #225

Description

@Unisay

What

A pattern match on a fixed-length array whose scrutinee is a manifest array literal is decidable at compile time, but pslua leaves it as a runtime length check. For example case [10, 20] of [a, b] -> a + b; _ -> -1 compiles to:

local v = { [1] = 10, [2] = 20 }
if 2 == #(v) then return v[1] + v[2] else return -1 end

Every part is known statically: #v is 2, the guard is true, the reads are 10 and 20, the result is 30. It should fold to return 30.

Why it is not folded today

PatArrayLength lowers to if literalInt len == arrayLength(scrutinee) then ... else ... (in Backend.IR). The optimizer has no fold for arrayLength on a literal array, and none for indexing into one, so the length check stays a runtime # and the element reads stay runtime indexing.

Proposed transformations

Three small pieces, reusing the existing folds.

  1. arrayLength (LiteralArray xs) → literalInt (length xs). A LiteralArray codegens to a hole-free sequence {[1]=..., [2]=...}, so its length is exactly the element count. This is the cheap, independently useful one: any length of a literal array.
  2. index (LiteralArray xs) (literalInt i) → xs !! i for an in-range literal index.
  3. Propagate a known array literal through a let into its use sites, the array sibling of propagateKnownCtorThroughLet (Case-of-known-constructor through a let-bound scrutinee #214). The scrutinee v here is let-bound and read three times (one length, two indices), so it is not inlined as used-once; the literal has to be propagated for (1) and (2) to see it.

With those, the existing folds finish the job: 2 == 2 → true, removeUnreachableElseBranch, 10 + 20 → 30, leaving 30.

Caveat for (1): fold against the IR element count (length xs), which is exact, rather than reasoning about Lua's #. If a literal array could contain nil (the unit = nil quirk, avoided since prelude 7.2.0 where unit = {}), Lua's # on a table with a hole is unreliable; keying the fold to length xs sidesteps that entirely.

Test

Test-first. An Optimizer unit test: the shape above reduces to the integer literal, and a match on a non-literal array (a variable of unknown length) is left untouched.

Payoff

Small and niche. Matching a literal array you just built, with a fixed-length pattern and literal elements, is almost exclusively a synthetic or golden situation, so this is a completeness fix rather than a performance one. Piece (1) is the one genuinely reusable fold on its own; (2) and (3) mostly earn their keep together with it on this exact shape.

Metadata

Metadata

Assignees

Labels

OptimisationA Compiler Optimisationarea: irIR / optimizer / DCE / inliner

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions