Skip to content

repsel: deforestation hides the record-producer shape from the Ptr<Shape> element rule #7150

Description

@proggeramlug

#7034 §3 (PR #7149) proves an element-shape-proven local array from the
shape const a: C[] = []; … a.push(new C(…)); … and then promotes the pushed
producer and every in-bounds a[i] binding to Ptr<Shape>.

It does not fire on benchmarks/app-patterns/kernels/batch.ts — the workload
the representation exists for — and the reason is not any of its five
conjuncts. perry-transform/src/deforest has already rewritten the producer
before the analysis runs.
--trace hir --focus buildRows on main:

- buildRows (params: 2, …)
    param n (id=14): Number
    param __deforest_out (id=44): Array(Named("Row"))
    [0] For { … body: [Let { id: 17, name: "row", init: New { class_name: "Row", … } },
                       Expr(ArrayPush { array_id: 44, value: LocalGet(17) })] }

const rows: Row[] = [] and return rows are gone; the array is a
parameter, and a parameter array has no provenance (the caller could pass
anything, and its array may be aliased). So row's push is still an escape.

This matters more than one workload. Deforestation's documented trigger
(deforest/mod.rs) is exactly

function f() { const out = []; /* pushes */ return out; }

— the canonical record-producing function, and item 7 of its transform list
rewrites even non-consumer call sites to const all = []; f(args, all);. So
every producer of that shape in a module where deforestation fires is
invisible to Ptr<Shape>'s element rule
, and the two passes are working
against each other: deforestation removes an allocation, the element rule
removes a guard diamond, and today you cannot have both.

Options, in ascending order of scope

  1. Order the passes. Run the element analysis on pre-deforestation HIR and
    carry the facts forward. Cheapest if fact identity survives the rewrite;
    needs checking that local ids do.
  2. Teach the rule about __deforest_out. The parameter is
    compiler-synthesized and the transform knows where the array is allocated
    (it inserts the allocation at the call site). That provenance could be
    recorded as a fact on the parameter. This is the honest fix but it means
    trusting a transform-inserted parameter, which needs its own soundness
    argument — in particular the caller's array must satisfy E1/E3 at the call
    site, and there may be several call sites.
  3. Generalise to array parameters via repsel row 1: scoping Ptr<Shape> beyond locals — measured, promotion is 0 on the motivating workload; build --opt-report (#6952) first #7034 §1's clone-and-route, with
    containment replaced by all-call-sites-agree. Subsumes (2) and is the
    general answer, but it is the call argument position and much larger.

Measure first: how many modules in the corpus have deforestation firing on a
function whose local array would otherwise satisfy E1-E5? That number decides
between (1) and (3).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions