commit a8d7f4c28bb7c82d09f317d3517c305bb4bee9f9
parent 7c59b98aaf9e129ef7277ef38782580f11ffd81f
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Tue, 16 Jun 2026 01:05:26 -0700
doc/OPT.md: O1 now runs linear move coalescing (O1.md W3); note landed O1 worklist
Diffstat:
1 file changed, 16 insertions(+), 7 deletions(-)
diff --git a/doc/OPT.md b/doc/OPT.md
@@ -259,7 +259,10 @@ improve the code are exactly these, none of which needs SSA:
loop-invariant immediates once in the entry block instead of per iteration.
- **`dead_def_elim_with_live`** — liveness-driven pre-RA dead-definition removal.
- **`regalloc_locations`** — point-bitmap linear-scan allocation, **without**
- live-range splitting or move coalescing (the O2-only quality knobs stay off).
+ live-range splitting. A *linear* move-coalescer (O1.md W3) now populates the
+ union-find (`opt_coalesce_parent`) before allocation so copy-related values
+ share a location; the O2-only quality knobs that stay off are live-range
+ splitting and the O(n²) conflict-**matrix** coalescer (`opt_coalesce_ranges`).
- **`mir_combine`** — post-RA peephole + addressing-mode synthesis (the same
`opt_combine` used in O2's SSA combine, here gated on physical-register
liveness). Its extension-folding also retires a ZEXT of a plain
@@ -272,7 +275,11 @@ improve the code are exactly these, none of which needs SSA:
collapse, and (LAYOUT mode) block reordering for fallthrough + loop rotation.
Everything else under §4 (`build_ssa`, `gvn`, `dse`, `licm`, `copy_prop`,
-`simplify`, live-range splitting, coalescing) is O2-only and never runs.
+`simplify`, live-range splitting, the O(n²) matrix coalescer) is O2-only and
+never runs. (Linear move coalescing *does* run at O1 — see `regalloc_locations`
+above and O1.md W3; only the splitting/matrix variants are O2-only.) The O1.md
+worklist (frame layout, remat, switch/cmp immediates, branch cleanup, inline cap)
+is landed; its passes are noted inline above and recorded in O1.md §5.
The reachability decision lives *outside* this pipeline, in the finalize sweep
(Section 1), identical on every architecture. At module finalization
@@ -453,11 +460,13 @@ transform or analysis; the file paths orient the reader.
- **Coalescing / allocation** (`src/opt/pass_coalesce.c`, `src/opt/pass_lower.c`):
`opt_regalloc_locations` is a point-bitmap linear-scan allocator producing the
canonical `Func.preg_locs` location table (hard reg or spill slot per PReg)
- without mutating HIR operands. The non-splitting form is the O1 path; when
- live-range splitting is enabled (the O2 quality path) it invokes
- move-related coalescing (`opt_coalesce_ranges`), which builds a bounded
- conflict matrix and merges only same-class, same-type values with compatible
- constraints and no range conflict — never an `IRF_NO_COALESCE` copy.
+ without mutating HIR operands. Two coalescers feed its union-find: the **O1
+ linear coalescer** `opt_coalesce_linear` (O1.md W3) merges copy-related values
+ using bounded per-root member lists + on-demand range-overlap tests (no
+ matrix), and `opt_verify_alloc` treats same-root PRegs as one value; the **O2
+ matrix coalescer** `opt_coalesce_ranges`, gated on live-range splitting, builds
+ a bounded conflict matrix. Both merge only same-class, same-type values with
+ compatible constraints and no range conflict — never an `IRF_NO_COALESCE` copy.
- **Jump / layout cleanup** (`src/opt/pass_jump.c`): `opt_jump_cleanup` in CFG
mode drops unreachable blocks and collapses unconditional-jump chains; in
LAYOUT mode it reorders blocks for fallthrough, rotates simple single-latch
