Compiler: `Compiler::compile` is super-quadratic (~n^2.65) in statements per block — 200 call statements take 412 s; `compileCallArgSends` runs 13 backward-scan matchers per call (lib/Compiler.php:49687)

[PurHur]

Category

Foundation: · compiler throughput (why the spine takes hours and hello-world 17 s) · child of #36188

Problem

One function with N statements of str_pad(implode(",", array_map("strval", [1,2,3])), 5);, host PHP, master 4eed6a2785, Compiler::compile only:

statements	compile	ms / statement
50	9.65 s	193
100	66.9 s	669
200	411.9 s	2,059

Doubling the input costs 6.2–6.9x — ~n^2.65. Cause: compileCallArgSends() (lib/Compiler.php:49687, 6,431 lines) tries ~13 bespoke argument-producer matchers in sequence (:49695-49760), each doing backward linear scans over sibling ops (matchInlineCallArgProducer :23864, 2,165 lines; precedingInlineCallArgProducersBeforeCfgOp :29912, 823 lines; 151 for ($i …) / 108 for ($j …) index loops in the file). Nested calls multiply the scans. syncCfgProducerExprIndex() (:44478) additionally loops the entire $this->seen storage on every findCfgProducerExprForOperand (:44428). Phase split on lib/Block.php (3,823 lines): Compiler::compile 3,560 ms of 7,419 ms total.

This is the same class of defect as the argument-resolution heuristics that produced the silent wrong-output bugs of #23354 (24 of 43 programs): positional/backward heuristics instead of the SSA def-use information php-cfg already provides.

PHP implementation target

• Build one Operand → producing Op map per CFG block (the producer index at :44478 nearly is this) and resolve each call argument by def-use; delete matchers as they become dead. Stage behind PHP_COMPILER_CALLARG_DEFUSE=1 with an opcode-corpus differential (Printer::print md5 over ≥100 files in separate processes) until identical, then flip.
• Memoize syncCfgProducerExprIndex (skip when $this->seen count is unchanged).
• Add script/compile-scaling-probe.php (50/100/200/400 statements) to the bench gate: ms/statement must be flat.

Repro

./script/docker-exec.sh -- bash -lc 'source script/php-env.sh && for n in 50 100 200; do php -r "echo \"<?php function f(){\n\"; for(\$i=0;\$i<$n;\$i++) echo \"str_pad(implode(\\\",\\\", array_map(\\\"strval\\\", [1,2,3])), 5);\n\"; echo \"}\n\";" > build/scale$n.php; /usr/bin/time -f "$n stmts: %es" php bin/vm.php -l build/scale$n.php >/dev/null; done'

Done when

• 200-statement probe compiles in < 5 s; ms/statement flat across 50/100/200/400
• Opcode corpus md5 identical before/after on ≥ 100 files (lib/, ext/, examples/, spine sample); script/differential-sweep.sh VM + AOT unchanged; compliance name-sets unchanged
• compileCallArgSends < 1,000 lines; the deleted matchers listed in the PR

[PurHur]

claim: implementer-worker-lane-b — starting this run (lane overflow: #36143–#36148 closed; first open P0 #36224)

[PurHur]

Slice 1 PR: partial caches + scaling probe — not merge-ready (200-stmt probe still ~126s vs <5s done-when).

Measured on branch `0f16d30799` (Docker):

• 50 stmts: 3.36s (67 ms/stmt)
• 100 stmts: 19.11s (191 ms/stmt)
• 200 stmts: 125.64s (628 ms/stmt) — ~5% vs master 131.8s; still super-quadratic

Shipped: memoized `precedingInlineCallArgProducersBeforeCfgOp`, cfg call-index cache, incremental cfg producer indexing, `script/compile-scaling-probe.php`.

Next slice: def-use ARG_SEND must preserve sibling `FUNCCALL_EXEC_RETURN` slot ordinals (prototype `PHP_COMPILER_CALLARG_DEFUSE=1` changes md5 on nested str_pad/implode/array_map — reverted). Wire through `ensureDeferredSiblingInlineCallArgProducersCompiled` + `slotForSiblingInlineCallProducerExecReturnByExpr`, then delete matcher arms as corpus md5 stays identical.

Gates on slice 1: `make dev-verify-fast` OK, `make north-star5-verify-fast` OK.

[PurHur]

claim: implementer-worker-lane-c — continuing PR #36336 slice 2 (def-use fast path + syncCfgProducerExprIndex memo)

[PurHur]

Slice 2 pushed (ccdccc0 on PR #36336): bulk `cfgCallOpIndexInChildren` map + ~100 linear-scan/array_search call sites routed through O(1) lookup.

Scaling probe (Docker, `php script/compile-scaling-probe.php`):

stmts	time	ms/statement
50	3.4s	68
100	19.8s	198
200	126s	631

Still ~n^2.6 — done-when (<5s @ 200) not met. Profiling: ~300 `compileCallArgSends` calls per 100 stmts; cost/call grows O(N) with block size → bottleneck is inside `matchInlineCallArgProducer` / deferred sibling `compileExpr`, not index lookup alone.

Next slice: `PHP_COMPILER_CALLARG_DEFUSE=1` fast path wired through `ensureDeferredSiblingInlineCallArgProducersCompiled` + sibling EXEC_RETURN ordinals (reverted prototype changed slot md5).

Verified: `make dev-verify-fast` OK (aot-smoke 9/9, tier-0 diff 15/15); `make north-star5-verify-fast` OK.

[PurHur]

claim: implementer-worker-lane-c — continuing PR #36336 slice 3 (syncCfgProducerExprIndex memo + def-use fast path)

[PurHur]

claim: implementer-worker-lane-b — continuing open PR #36336 (compile scaling slice 1); lane overflow from closed #36143–#36148

[PurHur]

Slice 3 (this run) — pushed `c0a259e397` on PR #36336.

• Landed: `syncCfgProducerExprIndex` fingerprint short-circuit — skip the per-`findCfgProducerExprForOperand` walk over all seen blocks when block count + child counts unchanged.
• Not landed: `PHP_COMPILER_CALLARG_DEFUSE=1` whole-call fast path — even with `matchInlineCallArgProducer` + existing slot helpers, opcode md5 diverges on `FUNCCALL_EXEC_RETURN` slot ordinals (`$8` vs `$7`, etc.). Same class of failure as slice 1 revert; next slice must preserve `ensureDeferredSiblingInlineCallArgProducersCompiled` EXEC_RETURN ordering.

Scaling (Docker, unchanged vs slice 2): 50 stmt 3.3s, 100 stmt ~19s, 200 stmt ~126s — done-when (<5s @ 200) not met. PR not merge-ready.

Verified: `make dev-verify-fast` OK (aot-smoke 9/9, tier-0 diff 15/15).

Next: def-use fast path wired to sibling EXEC_RETURN ordinals from `ensureDeferredSibling`, or incremental preceding-producer index per cfg block (avoid O(callIndex) backward scan).