2c-color-size Size-bounded synthesis coloring — min/max regions for pass.abc

Step 0–1 of 2opt-incr: make pass.color synth produce regions that pass.abc can map within a 64 GB notebook by default, with no singleton partitions and no monster regions. Bounds are enforced by a new min=/max= size window; the sampled-RSS admission in pass.abc stays as the runtime backstop.

Baseline (XSCore, measured 2026-07-16)

• pass color synth --stats --top XSCore.XSCore lg:xs_core_lg: 42,176 partitions over 1,629 defs (17.6M per-def nodes; 23.0M flat); max 3,483,978 nodes (Rob.Rob, 15.1% of design), median 1, avg 417.6, 35,065 singletons, only 292 in the 1k–5k band. 3m19s.
• Why singletons: Color_synth pass 2 attaches only Flop/Latch/Fflop cuts to their din cone (color_synth.cpp:73-86); every Mult/Div/wide-Sum cut always opens a fresh region, and flops driven by IO/other flops, memories, and stateful subs do too.
• Why the monster: forward fan-out propagation + union-find welding collapses each big def's reconvergent comb cloud into one region (per-stage coloring on comb clouds is impossible — settled ruling).
• 91% of partitions (38,468) live inside the 483 defs ≥ 1000 nodes: within-def merge/split fixes those. The 1,146 defs < 1000 nodes hold 1.2% of design nodes (3,708 partitions) — reachable only by cross-hierarchy absorb (ruling 3).

Contract rulings (settled 2026-07-16)

• R1 — sizes are GATE-EQUIVALENTS, not node counts. Per-node weight estimates bit-blasted gates: bitwise/mux/Sum/comparator ≈ bits, Mult ≈ bits², flop ≈ bits, Get/Set_mask ≈ bits, blackboxed nodes (Div, Sub, default Memory) ≈ port bits. bits==0 (pre-bitwidth) degrades to weight 1 — same caveat as driver_bits. Rationale: ABC memory/runtime scales with bit-blasted gates; a 200k-node region of wide datapath would pass a node gate and still OOM.
• R2 — defaults min=1000, max=30000000 GE, enabled by default. max CORRECTED 2026-07-16 from 200000 after measurement (user ruling). The original 200000 was node arithmetic wearing a GE label: 200k × 9.6 KB/node ≈ 1.9 GB is right per NODE, but R1 makes the unit gate-equivalents and XSCore measures 421 GE/node (7.43e9 GE over 17.6M per-def nodes) — so 200k GE is ~475 nodes, a tiny region, and forces ≥37k regions arithmetically. Recalibrated in GE from the same data point: 221 GB / 7.43e9 GE ≈ 30 bytes/GE, so ~0.9 GB/region ≈ 30M GE. A bigger host raises it explicitly; 0 disables. Recorded in coloring_info params.
• R3 — below-min defs are absorbed into their parents. "Cluster to neighboring blocks as long as not passing max" (user ruling; hier=true is the default everywhere). Mechanism: selective structural inline of defs whose total GE < min (recursive, children-first), reusing the flatten.cpp machinery; then normal coloring + the size window cluster the absorbed logic with its neighbors under max. A Sub is a blackbox to ABC, so only inlining actually merges the logic.
• R4 — no acyclicity constraint. Verified: pass.partition/pass.abc/LEC/ cgen-Verilog tolerate inter-region comb cycles (no check exists anywhere). Merge/split reshapes regions freely; a quotient-DAG constraint is not maintained. Premise corrected 2026-07-16: the note that "cgen_sim errors only on REAL cross-module comb loops" is wrong — cgen_sim.cpp:1845 (comb-loop-through-instance) hard-errors on a quotient cycle with no bit-level cycle at all, because it emits one atomic cycle() per Sub (see inou/cgen/tests/comb_loop/README.md). The RULING still stands: no flow simulates a partitioned netlist (the partition tests go to Verilog + LEC, never sim), so this is documentation, not a constraint.
• Existing rulings that bind: per-def grain (colors live per unique def; ABC maps each (def, region) once regardless of instance count); pass.color flat stays literal (never subdivided); seeded/block-attr colorings win and must survive untouched (they are the future Pyrope partition-hint channel, and carry region_opts).

Design

• Where: a shared size-window engine (new pass/color file, sibling of color_common) operating on the per-def Node2Id before apply_coloring. Wired into synth first; other algorithms can opt in later. pass.partition/pass.abc need no changes: they already consume colors as regions (= connected components of same-color nodes).
• Region graph: normalize ids to connected components (the split_continuous union-find), then build region vertices (weight = Σ GE) and edges (weight = Σ crossing driver bits).
• Merge-small (kills the 35k singletons): Best-Choice agglomeration (ISPD'05): priority queue of adjacent pairs scored connectivity/(size_a+size_b); while a region < min has a neighbor and the merge stays ≤ max, take the best pair. Deterministic tie-breaks (min color id); seeded ids excluded; cross-flop merges allowed (register=true handles multi-stage regions, and singleton flop/arith chains need it).
• Split-large (kills the 3.48M monster): for each region > max, decompose its subgraph into MFFC micro-clusters (Cong DAC'94: disjoint, duplication-free, never splits a fanout-free cone — keeps per-region ABC quality), then run the SAME agglomeration with the max cap; topological-order chunking (Kernighan'71-style) is the guaranteed-terminating fallback (an MFFC > max, or a pathologically dense cluster graph).
• Absorb pass (R3): before coloring, post-order walk; a bodied def with total GE < min is inlined into every instantiation site (dotted-prefix names, colors recomputed after); blackboxes/liberty cells skipped. Persisted through --emit-dir so pass.abc sees the same structure. Absorbed-def count reported in --stats. Instance multiplication is measured in the acceptance run; add a size×instances guard only if a pathological case shows up.
• Ids: fresh deterministic ids per final region, keeping the "one color = one region = one __c<id> module" contract (diagnose_colors) intact; algorithm ids still shift above seeded base.
• Reporting: --stats gains GE sizes (max/min/avg/median), a size histogram, under-min / over-max counts (should be 0 post-pass except def-bound leftovers), and absorbed-def count. params_json records min/max.

Literature anchors (survey 2026-07-16, session notes)

• Consensus recipe for bounded-size netlist partitioning with min cut: cone/MFFC micro-clusters → heavy-edge greedy agglomeration under a size window → optional FM polish (Cong'94; Best-Choice ISPD'05; METIS HEM; Verilator V3Partition as production proof). No new dependency needed — k-way partitioners are the wrong shape (fixed k, epsilon balance, no min; hMETIS/PaToH license-blocked; VieCut in-tree is 2-way global min-cut, unbalanced).
• Practice: Yosys/ABC cut at flops per module; ABC never partitions for synthesis (priority-cuts mapping is linear-memory, ~150–200 B/AIG-node); Quartus publishes a ≥~2,000 LE partition floor; Vivado sweet spot ~10k LUTs; DC canon = register outputs, keep comb cones together. Cutting at big arithmetic is sound for an AIG/ABC backend (Booth/CSA internals gain nothing from neighbors) though it forfeits DC-style datapath fusion.
• QoR loss concentrates at boundary placement, not size (FPL'06: 2→4.5% area as partitions shrink; PRflow: leaf QoR survives, bandwidth at boundaries dominates) — hence connectivity-scored merging.
• LiveSynth 1k–5k gate band = incremental resynthesis grain (2opt-incr E splits to that band later); this task's 200k-GE max is the memory-fit full-synthesis ceiling.

Landed (2026-07-16) — measured on XSCore

A–E landed; the acceptance numbers below are -c opt, pass color synth --top XSCore.XSCore --stats. Both shape goals hold: the 35k singletons and the 3.48M-node monster are gone.

• Region count does NOT drop to ~1000. That estimate assumed GE ≈ nodes. At 421 GE/node the design is 7.43e9 GE, so max alone sets an arithmetic floor of total/max regions. 61k regions is the honest number for a 30M cap; the count is driven by min and by what merge-small can legally reach, not by the cap.
• Where the GE actually is (measured, per-def sums): mux 3.45e9 (6.47M nodes, avg 532 bits), get_mask 2.22e9 (4.80M nodes, avg 464), and 514M, shl 328M, set_mask 265M (36k nodes, avg 7366), sra 264M, or 227M. Mult is only 8.6M over 7,162 nodes and Sub only 4.1M over 4,190 — the datapath WIDTH is the whole story, not the multipliers. 1.77M nodes weigh 1k–10k GE each and hold 63% of the total.
• The 26 over-max regions under the old default were all single Memory nodes (up to 11.6M GE): a whole-array update bus is size*bits wide, and R1 charges a blackbox its port bits. Indivisible — no split can fix one — so they would have made pass.abc admission FATAL the whole run. Worth revisiting: with memory=false (the default) ABC never opens a Memory, so charging it millions of GE over-prices the one thing that costs ABC nothing.
• Absorb is far more destructive than min suggests. At min=1000 it inlines 259 defs; at min=5M it inlines 1,489 of 1,629 and the hierarchy is gone. On small designs (every def under min) it flattens the whole thing — which is why lhd_partition_hier_test now pins absorb=false, and why absorb= exists as its own switch.

Subtasks

• A. GE weight metric. ge_weight(node) shared helper (graph/node_util or color_common); unit tests for the formula and the bits==0 degradation.
• B. Options + stats. min=/max= labels on pass.color (from_chars + fatal like pass.abc.memory_budget_mb; 0=off), params_json, GE in Def_color_sizes, histogram + under/over counts in Color_stats.
• C. Size-window engine. Region graph + Best-Choice merge-small + MFFC split-large + topo-chunk fallback + deterministic renumber. Wired into Color_synth::label between merge_ids() and apply_coloring.
• D. Absorb below-min defs. Selective inline (flatten.cpp reuse), post-order, emit-dir persisted; stats reporting. Verify hier-LEC def pairing and post-abc LEC name stability on an absorbed design.
• E. Tests. Raw algorithm stays pinned with min=0 max=0 (color_synth_test updated); new tests: no region under min unless def-bound, none over max, determinism, seeded untouched, absorb (multi-parent, stateful tiny def, blackbox skipped).
• F. Acceptance + calibration. Rob.Rob alone through pass.abc first, then full XSCore color+abc on the 64 GB notebook with defaults: admission must never fire; record RSS peak vs GE per region to calibrate bytes/GE; tune defaults if needed; update 2opt-incr E and pass help text.

Risks / notes

• memory=true lowering runs inside pass.abc AFTER coloring and inflates a region past max (lowered flops/muxes inherit the memory's color); admission is the backstop. Future: weight Memory by entries×width when lowering is requested.
• Absorb duplicates a tiny def's logic per instance site (mapping dedup lost); bounded by the min threshold (≤1k GE each) but measure the aggregate on XSCore.
• Cross-clock-domain merges are allowed v1 (flow does no retiming; each flop is rewired to its own clock on read-back); revisit if multiclock synthesis lands.
• A REAL intra-region comb cycle is broken unsoundly (const0 + warning) by the bit-blast fixpoint — pre-existing pathology, unchanged by this task, but merges can move a formerly cross-region cycle inside one region where ABC sees it.
• Region count on XSCore with 200k-GE max will be ~1000+: sequential pass.abc wall-clock is hours; parallel per-region synthesis is 2opt-incr B, not this task.

Future (hooks left in place)

• FM boundary refinement pass over the final regions (cut-bits polish).
• Timing-driven grow/split to the 1k–5k band (2opt-incr E) once QoR feedback exists.
• Pyrope partition-hint attributes riding the existing seeded/block-attr channel (seeded regions already win over the algorithm and carry region_opts).
• Instance-count-aware absorb guard; GE-aware memory weights.