diff options
Diffstat (limited to 'docs/regalloc-spills.md')
| -rw-r--r-- | docs/regalloc-spills.md | 81 |
1 files changed, 25 insertions, 56 deletions
diff --git a/docs/regalloc-spills.md b/docs/regalloc-spills.md index 4f738fe5..8e83f3ba 100644 --- a/docs/regalloc-spills.md +++ b/docs/regalloc-spills.md @@ -21,12 +21,12 @@ no encoder, so its dynamic cells are unavailable. There is no cross-cohort total <!-- spill-matrix:start --> | Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | Ch 25: Ops / RA / X | |---|---:|---:|---:|---:|---:|---:|---:| -| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 59,043 / 9,094 / 209 | -| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,233 / 219 / 533 | -| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 332 / 136 / 11 | -| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | 1,106 / 442 / 36 | -| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | 5,044 / 1,470 / 609 | -| Ch 25 | 2 / 12 | | | | | | 20 / 0 / 1,862 | +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 58,965 / 9,076 / 208 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,196 / 219 / 534 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 252 / 92 / 11 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | 864 / 358 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | 4,646 / 1,335 / 609 | +| Ch 25 | 2 / 12 | | | | | | 20 / 0 / 1,856 | <!-- spill-matrix:end --> Measured on Windows, 2026-10-07, using optimizer seed 123 for the historical @@ -64,60 +64,29 @@ answers, including nested equality at arguments 0-3, finite Newton results and Bubble Sort's complete output. The shared ISA tests and full Chapter 21-25 Make suites pass after the backend/evaluator corrections. -## Remaining differences after fixture cleanup +## Remaining initialization costs -The Chapter 24-to-25 comparison, using the same inputs and cases in each row: +Chapter 25 now places declared constant final fields directly in static data, +including function addresses, and omits their initialization stores. The same +fixed inputs and test cases give: | Cohort | Ch 24 Ops | Ch 25 Ops | Change | |---|---:|---:|---:| -| Ch 20 | 58,720 | 59,043 | +0.6% | -| Ch 21 | 6,325 | 6,233 | -1.5% | -| Ch 22 | 194 | 332 | +71.1% | -| Ch 23 | 630 | 1,106 | +75.6% | -| Ch 24 | 4,923 | 5,044 | +2.5% | - -Chapter 25 retains top-level bindings in the compilation unit's class object. -Initializing its fields generates stores, function-pointer constants and class -addresses, even when helper calls have already inlined and folded. Chapters -through 24 can eliminate these bindings as locals. Small programs make this -fixed initialization cost particularly visible. - -For example, `Chapter23Test.testAnd` takes 12 instructions per target in 24 and -32 in 25. The extra 20 are four field stores, four instructions materializing -two function pointers, ten materializing the class address at five uses -(including the hidden call argument), and two integer constants. The actual -short-circuit expression has already folded in both chapters. - -Across the entire Chapter 23 cohort, executed-node attribution accounts for -the **476** extra instructions: - -| Generated work | Instruction change | -|---|---:| -| Field stores | +126 | -| Function-pointer materialization | +108 | -| Pointer-address materialization | +240 | -| Integer constants | +50 | -| Allocator copies/spills/reloads | +2 | -| Unconditional jumps | +2 | -| Calls, prologues/returns, extensions and loads removed | -52 | - -Its RA subset rises **160 to 442**, comprising **224** extra pointer-address -rematerialization instructions, **56** extra integer rematerializations and -only **2** extra copies/spills/reloads. RA labels allocator-created code; it -does not mean all 282 extra instructions are stack traffic. `testAndPtr` also -loses a helper call per execution, so inlining has improved despite the larger -whole-program count. Moving constant initialization to static data would -remove much of this work; reusing class addresses could reduce the repeated -materialization. Neither optimization is included in this measurement update. - -Both Bubble Sort targets improve: RISC-V **2,062 / 591 to 1,877 / 493**, and -ARM **2,040 / 579 to 1,868 / 478** (Ops / RA). Together they save 357 instructions; -the other Chapter 24 cases add 478, leaving a net increase of 121. Newton -integer improves **136 / 36 to 116 / 17** across both targets. In the Chapter 20 -BrainFuck case, ARM adds 95 instructions: 88 net extra integer materializations -plus seven initialization instructions; its executed split count stays at 33. -These tables compare whole chapter compilers, including frontend and inlining -changes, rather than isolating allocator rankings. +| Ch 20 | 58,720 | 58,965 | +0.4% | +| Ch 21 | 6,325 | 6,196 | -2.0% | +| Ch 22 | 194 | 252 | +29.9% | +| Ch 23 | 630 | 864 | +37.1% | +| Ch 24 | 4,923 | 4,646 | -5.6% | + +Chapter 25 retains top-level bindings in its class object; earlier chapters can +eliminate them as locals. Mutable fields and final fields whose declarations +do not identify their exact constant still need runtime initialization. This +fixed cost remains visible in small programs even after helper calls inline. + +For cohort 23, the RA subset is 160 in Chapter 24 and 358 in Chapter 25. It +includes allocator-created constant/address rematerialization as well as copies +and stack traffic; it must not be read as a count of spills alone. These tables +compare whole chapter compilers, including frontend and inlining changes. ## Reproduce |