summaryrefslogtreecommitdiff
path: root/chapter32
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-11-15 22:45:53 -0800
committerCliff Click <cliffc@acm.org>2026-11-15 22:45:53 -0800
commitec270802f05b93eccffa2e0fbfb9bd5dd63c9cb2 (patch)
tree911aa442589061f12de22982eee3505ed5716af0 /chapter32
parentb8bcd9c0e826c7cb0b45d1ae5a52a325d22fd048 (diff)
downloadSimple-ec270802f05b93eccffa2e0fbfb9bd5dd63c9cb2.tar.gz
Simple-ec270802f05b93eccffa2e0fbfb9bd5dd63c9cb2.zip
More cachingch32
and during RegAlloc, hang on to only a single fcn's BBs at a time
Diffstat (limited to 'chapter32')
-rw-r--r--chapter32/README.ja.md3
-rw-r--r--chapter32/README.md45
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java96
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java7
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java6
5 files changed, 106 insertions, 51 deletions
diff --git a/chapter32/README.ja.md b/chapter32/README.ja.md
index ac57b417..05c091ec 100644
--- a/chapter32/README.ja.md
+++ b/chapter32/README.ja.md
@@ -15,6 +15,9 @@
- 高価な検証の既定値を log 8 から log 10 に変更し、インライン化の各途中段階で繰り返していたスケジュール検証を削減します。
- 外部状態を読む依存関係を不透明な引数に限定し、定数引数の削除による無関係な利用側への通知を減らします。
呼び出しの切り離しで変更したパラメータは明示的に再処理します。
+- IFG の live-out マップと作業領域を関数ごとに持ち、スピルによる再試行の間だけ再利用します。
+ 過去のコンパイルの基本ブロックを保持し続けることがなくなります。
+ スピル候補の評価に使う関数の大きさも、彩色の試行ごとに一度だけ計算します。
測定ではワークリストからの peephole 呼び出しが約446万回から370万回へ、17.2%減少しました。
詳細な測定条件、実装の説明、残る調査対象は[英語版](README.md)を参照してください。
diff --git a/chapter32/README.md b/chapter32/README.md
index d7ca40db..b3fb09ea 100644
--- a/chapter32/README.md
+++ b/chapter32/README.md
@@ -269,6 +269,51 @@ with every-step verification. Raw measurements, saved compiler classes, and
reproduction commands are in `build/memmerge-dense/`; verification logs are in
`build/test-profile/dense-final-*.log`.
+## Match interference scratch lifetime to function allocation
+
+[RegAlloc](src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java) already
+allocates one function at a time, retrying after spills before moving to the
+next function. But [IFG](src/main/java/com/seaofnodes/simple/codegen/IFG.java)'s
+static `BBOUTS` retained basic-block keys from every previous allocation, even
+across compilations. Each interference build cleared all their live-out maps.
+Repeated sys compiles added 2,558 keys apiece, making later compiles slower.
+
+Each function now creates an IFG instance. Its live-out maps, temporary live
+set, and worklist survive that function's spill retries and become unreachable
+when allocation returns. The shared interference bitsets still reuse capacity:
+they contain live-range numbers, with no references to compiler graphs.
+
+Risky spill scoring also repeatedly walked the function's scheduled blocks to
+compute the same area. Coloring now computes that area once, after coalescing,
+and passes the integer to the scoring routines. A later spill retry recomputes
+it because splitting can change the schedule. An assertion checks that the
+live ranges being colored belong to the current function.
+
+Compared with `b8bcd9c0`, median compile times through object export were:
+
+| Workload | Before | After | RegAlloc before / after |
+| --- | ---: | ---: | ---: |
+| sys library | 1,290 ms | 913 ms | 494 / 91 ms |
+| Clock | 537 ms | 279 ms | 274 / 27 ms |
+| Breakout | 1,007 ms | 609 ms | 428 / 51 ms |
+| Graphical tic-tac-toe | 1,362 ms | 292 ms | 1,113 / 40 ms |
+
+These are repeated compilations: six measured rounds after three warmups,
+alternating isolated baseline and changed compiler class loaders. Each workload
+starts with fresh loaders. The old implementation accumulates block keys even
+during warmup, so these gains depend on compilation history; they are not
+single-shot CLI startup measurements. Java 21 uses two active processors,
+assertions at log10, and a 256 MiB initial / 2 GiB maximum heap. Both compilers
+read the same sys objects; gcc, linking, and native execution are excluded.
+HelloWorld remains about 69 ms, within measurement noise.
+
+Peephole counts, code sizes, and spill counts match in every benchmark pair.
+The final 26 objects, including sys submodules, have identical `.text` bytes.
+The full non-graphical suite passes all 805 test executions at log8, including
+the native allocator checks. Benchmark sources, saved baseline classes, raw
+timings, and follow-up JFR recordings are in `build/ifg-profile/`; the suite log
+is `build/test-profile/ifg-full.log`.
+
## Build and test
From `chapter32`, using the existing offline dependency caches:
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java
index 6ad7c0ad..a027263f 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java
@@ -8,18 +8,20 @@ import java.util.BitSet;
import java.util.IdentityHashMap;
// Interference Graph
-abstract public class IFG {
+public class IFG {
// Interference Graph Support
+ // Scratch for one function, reused across its spill retries.
// Map from a Basic Block to Live-Out: {a map from a Live Range to a Def}
- private static final IdentityHashMap<CFGNode,IdentityHashMap<LRG,Node>> BBOUTS = new IdentityHashMap<>();
- static void resetBBLiveOut() {
- for( IdentityHashMap<LRG,Node> bbout : BBOUTS.values() )
+ private final IdentityHashMap<CFGNode,IdentityHashMap<LRG,Node>> _bbouts = new IdentityHashMap<>();
+ private void resetBBLiveOut() {
+ for( IdentityHashMap<LRG,Node> bbout : _bbouts.values() )
bbout.clear();
}
- static final IdentityHashMap<LRG,Node> TMP = new IdentityHashMap<>();
+ private final IdentityHashMap<LRG,Node> _tmp = new IdentityHashMap<>();
- // Inteference Graph: Array of Bitsets
+ // Interference Graph: Array of Bitsets. Reuse capacity across functions;
+ // these contain only live-range numbers, not references to the graph.
static final Ary<BitSet> IFG = new Ary<>(BitSet.class);
static void resetIFG() {
for( BitSet bs : IFG )
@@ -42,10 +44,10 @@ abstract public class IFG {
}
- private static final Ary<CFGNode> WORK = new Ary<>(CFGNode.class);
- static void pushWork(CFGNode bb) {
- if( WORK.find(bb) == -1 )
- WORK.push(bb);
+ private final Ary<CFGNode> _work = new Ary<>(CFGNode.class);
+ private void pushWork(CFGNode bb) {
+ if( _work.find(bb) == -1 )
+ _work.push(bb);
}
// ------------------------------------------------------------------------
@@ -65,20 +67,20 @@ abstract public class IFG {
// - At block head, "push" the new live-out to prior blocks.
// - - If they pick up new live-outs, put them on the worklist.
- public static boolean build( int round, RegAlloc alloc ) {
+ public boolean build( int round, RegAlloc alloc ) {
// Reset all to empty
resetBBLiveOut();
resetIFG();
- WORK.clear();
+ _work.clear();
// Last block has nothing live out
for( CFGNode bb : alloc._cfg )
if( bb.blockHead())
- WORK.push( bb );
+ _work.push( bb );
// Process blocks until no more changes
- while( !WORK.isEmpty() )
- do_block(round,alloc,WORK.pop());
+ while( !_work.isEmpty() )
+ do_block(round,alloc,_work.pop());
if( alloc.success() )
convert2DAdjacency(alloc);
@@ -86,12 +88,12 @@ abstract public class IFG {
}
// Walk one block backwards, compute live-in from live-out, and build IFG
- static void do_block( int round, RegAlloc alloc, CFGNode bb ) {
+ private void do_block( int round, RegAlloc alloc, CFGNode bb ) {
assert bb.blockHead();
- IdentityHashMap<LRG,Node> live_out = BBOUTS.get(bb);
- TMP.clear();
+ IdentityHashMap<LRG,Node> live_out = _bbouts.get(bb);
+ _tmp.clear();
if( live_out != null )
- TMP.putAll(live_out); // Copy bits to temp
+ _tmp.putAll(live_out); // Copy bits to temp
// A backwards walk over instructions in the basic block
for( int inum = bb.nOuts()-1; inum >= 0; inum-- ) {
@@ -118,14 +120,14 @@ abstract public class IFG {
mergeLiveOut(alloc,bb,0);
}
- private static void do_node(RegAlloc alloc, Node n) {
+ private void do_node(RegAlloc alloc, Node n) {
// Defining means killing live LRG
LRG lrg = alloc.lrg(n);
if( lrg != null ) {
// Check for def-side self-conflict live ranges. These must split,
// and only happens during the first round a particular LRG splits.
selfConflict(alloc,n,lrg);
- TMP.remove(lrg); // Kill def
+ _tmp.remove(lrg); // Kill def
}
// Phis use and define the same live range, i.e. these LRGs already
@@ -141,7 +143,7 @@ abstract public class IFG {
// Interfere n with all live
if( lrg!=null ) {
// Interfere n with all live
- for( LRG tlrg : TMP.keySet() ) {
+ for( LRG tlrg : _tmp.keySet() ) {
assert tlrg.leader();
// Skip self
if( lrg != tlrg &&
@@ -177,7 +179,7 @@ abstract public class IFG {
selfConflict(alloc,def,lrg1);
// All operands are live together, regardless of their input order.
- TMP.put(lrg1,def);
+ _tmp.put(lrg1,def);
}
// Check fixed-register uses after gathering every operand. An indirect
@@ -191,9 +193,9 @@ abstract public class IFG {
RegMask ni_mask = m.regmap(i);
if( ni_mask!=null && ni_mask.size1() ) { // Must-use single register
// Search all current live
- for( LRG tlrg : TMP.keySet() ) {
+ for( LRG tlrg : _tmp.keySet() ) {
assert tlrg.leader();
- Node live = TMP.get(tlrg);
+ Node live = _tmp.get(tlrg);
if( live != def && live instanceof MachNode lmach && lmach.outregmap().overlap(ni_mask) ) {
// Deny the register, since it absolutely must be used here
if( !tlrg.clr(ni_mask.firstReg()) )
@@ -210,15 +212,15 @@ abstract public class IFG {
// Single-register defines *must* have their register; other live ranges
// *must* avoid this register, so instead of interfering we remove the
// single register from the other rmask.
- private static void kills( RegAlloc alloc, MachNode m ) {
+ private void kills( RegAlloc alloc, MachNode m ) {
RegMask killMask = m.killmap();
if( killMask==null ) return;
// Kill registers with all live
- for( LRG tlrg : TMP.keySet() ) {
+ for( LRG tlrg : _tmp.keySet() ) {
assert tlrg.leader();
// Always, tlrg cannot use kills
if( tlrg._mask.overlap(killMask) ) {
- Node live = TMP.get(tlrg);
+ Node live = _tmp.get(tlrg);
// Disallow clone-ables from living across killed registers.
// Fail them and let splitting re-clone closer to the target use.
if( live instanceof MachNode mach && mach.isClone() )
@@ -231,8 +233,8 @@ abstract public class IFG {
// Check for self-conflict live ranges. These must split, and only happens
// during the first round a particular LRG splits.
- private static void selfConflict(RegAlloc alloc, Node n, LRG lrg) {
- selfConflict(alloc,n,lrg,TMP.get(lrg));
+ private void selfConflict(RegAlloc alloc, Node n, LRG lrg) {
+ selfConflict(alloc,n,lrg,_tmp.get(lrg));
}
private static void selfConflict(RegAlloc alloc, Node n, LRG lrg, Node prior) {
if( prior!=null && prior != n ) {
@@ -242,17 +244,17 @@ abstract public class IFG {
}
}
- // Merge TMP into bb's live-out set; if changes put bb on WORK
- private static void mergeLiveOut( RegAlloc alloc, CFGNode priorbb, int i ) {
+ // Merge _tmp into bb's live-out set; if changes put bb on _work
+ private void mergeLiveOut( RegAlloc alloc, CFGNode priorbb, int i ) {
CFGNode bb = priorbb.cfg(i);
if( bb == null ) return; // Start has no prior
while( !bb.blockHead() ) bb = bb.cfg0();
// Lazy get live-out set for bb
- IdentityHashMap<LRG, Node> lrgs = BBOUTS.computeIfAbsent( bb, k -> new IdentityHashMap<>() );
+ IdentityHashMap<LRG, Node> lrgs = _bbouts.computeIfAbsent( bb, k -> new IdentityHashMap<>() );
- for( LRG lrg : TMP.keySet() ) {
- Node def = TMP.get(lrg);
+ for( LRG lrg : _tmp.keySet() ) {
+ Node def = _tmp.get(lrg);
// Effective def comes from phi input from prior block
if( def instanceof PhiNode phi && phi.cfg0()==priorbb ) {
assert i!=0;
@@ -306,6 +308,9 @@ abstract public class IFG {
// If there's no spare color we'll have to spill this at-risk live range.
public static boolean color(int round, RegAlloc alloc) {
+ // Coalescing is finished; splitting may change this area next round.
+ FunNode fun = alloc._cfg.at(0).fun();
+ int functionArea = functionArea(fun,alloc);
int maxlrg = alloc._LRGS.length, nlrgs=0;
for( int i=1; i<maxlrg; i++ )
if( alloc._LRGS[i] != null )
@@ -325,6 +330,7 @@ abstract public class IFG {
for( int i=0, j=0; i<maxlrg; i++ ) {
LRG lrg = alloc._LRGS[i];
if( lrg==null ) continue; // Unified lrgs are null here
+ assert lrg._fun==fun;
color_stack[j++] = lrg;
if( lrg.lowDegree() ) swap(color_stack, swork++, j-1);
}
@@ -332,7 +338,7 @@ abstract public class IFG {
// Pull all lrgs from IFG, in trivial order if possible
while( sptr < color_stack.length ) {
// Swap best color up front
- pickColor(color_stack,sptr,swork,alloc);
+ pickColor(color_stack,sptr,swork,functionArea);
// Pick a trivial lrg, and (temporarily) remove from the IFG.
LRG lrg = color_stack[sptr++];
@@ -388,10 +394,10 @@ abstract public class IFG {
}
// Pick LRG from color stack
- private static void pickColor(LRG[] color_stack, int sptr, int swork, RegAlloc alloc) {
+ private static void pickColor(LRG[] color_stack, int sptr, int swork, int functionArea) {
// Out of trivial colorable, pick an at-risk to pull
if( sptr==swork )
- swap(color_stack,sptr,pickRisky(color_stack,sptr,alloc));
+ swap(color_stack,sptr,pickRisky(color_stack,sptr,functionArea));
// When coloring, we'd like to give more choices; so when coloring we'd
// like to see the single-def first (since no choices anyway), then
// non-split related (so more live ranges get colored), then
@@ -426,12 +432,12 @@ abstract public class IFG {
// Pick a live range that hasn't already spilled, or has a single-def-
// single-use that are not adjacent.
- private static int pickRisky( LRG[] color_stack, int sptr, RegAlloc alloc ) {
+ private static int pickRisky( LRG[] color_stack, int sptr, int functionArea ) {
int best=sptr;
- int bestScore = pickRiskyScore(color_stack[best],alloc);
+ int bestScore = pickRiskyScore(color_stack[best],functionArea);
for( int i=sptr+1; i<color_stack.length; i++ ) {
if( bestScore == 1000000 ) return best; // Already max score
- int iScore = pickRiskyScore(color_stack[i],alloc);
+ int iScore = pickRiskyScore(color_stack[i],functionArea);
if( iScore > bestScore )
{ best = i; bestScore = iScore; }
}
@@ -446,16 +452,16 @@ abstract public class IFG {
//
// Picking a live range that is very close to coloring might allow it to
// color despite being risky.
- private static int pickRiskyScore( LRG lrg, RegAlloc alloc ) {
+ private static int pickRiskyScore( LRG lrg, int functionArea ) {
// Callee-save live ranges cover the whole function and are cheap to
// split. Rank scheduled area recovered against the loop-scaled cost
// of the def- and use-side moves.
if( lrg._machDef instanceof CalleeSaveNode )
- return areaScore(functionArea(lrg._fun,alloc),
+ return areaScore(functionArea,
splitCost((Node)lrg._machDef,(Node)lrg._machUse));
if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode &&
lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode )
- return areaScore(functionArea(lrg._fun,alloc),
+ return areaScore(functionArea,
splitCost(lrg._splitDef,lrg._splitUse));
// Pick single-def clonables that are not right next to their single-use.
@@ -465,7 +471,7 @@ abstract public class IFG {
Node use = ((Node)lrg._machUse);
CFGNode cfg = def.cfg0();
int area = cfg != use.cfg0()
- ? functionArea(lrg._fun,alloc)
+ ? functionArea
: cfg._outputs.find(use)-cfg._outputs.find(def)-1;
// A single-use function address can move next to its use without
// adding an instruction. Prefer that to saving a callee-save
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 303fd355..c3be4b71 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -213,8 +213,9 @@ public class RegAlloc {
}
private void allocateFunction() {
+ IFG ifg = new IFG();
_deferredLoopSelf.clear();
- for( byte round=0; !graphColor(round); round++ ) {
+ for( byte round=0; !graphColor(round,ifg); round++ ) {
split(round);
if( round >= 10 ) {
FunNode fun = _cfg.at(0).fun();
@@ -281,7 +282,7 @@ public class RegAlloc {
return cfg==null ? null : cfg.fun();
}
- private boolean graphColor(byte round) {
+ private boolean graphColor(byte round, IFG ifg) {
_failed.clear();
_lrgs.clear();
_lrg_num = 1;
@@ -291,7 +292,7 @@ public class RegAlloc {
// Build Live Ranges
BuildLRG.run(round,this) && // if no hard register conflicts
// Build Interference Graph
- IFG.build(round,this) && // If no self conflicts or uncolorable
+ ifg.build(round,this) && // If no self conflicts or uncolorable
// Conservative coalesce copies
Coalesce.coalesce(round,this) &&
// Color attempt
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
index edb2519c..ae935da0 100644
--- a/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
+++ b/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java
@@ -85,7 +85,7 @@ public class RegAllocTestSupport {
new Op(null,A,null,false,code._start,def);
RegAlloc alloc = new RegAlloc(code);
assertTrue(BuildLRG.run(0,alloc));
- assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc));
+ assertFalse("A live value cannot survive a register kill",new IFG().build(0,alloc));
}
public static void nullUseMask() {
@@ -95,7 +95,7 @@ public class RegAllocTestSupport {
new Op(null,null,null,false,code._start,def); // Scheduling dependency only.
RegAlloc alloc = new RegAlloc(code);
assertTrue(BuildLRG.run(0,alloc));
- assertTrue(IFG.build(0,alloc));
+ assertTrue(new IFG().build(0,alloc));
}
public static void independentFunctions() {
@@ -262,7 +262,7 @@ public class RegAllocTestSupport {
assertTrue(BuildLRG.run(0,alloc));
assertNull(alloc.lrg(top));
assertSame(alloc.lrg(def),alloc.lrg(phi));
- assertTrue(IFG.build(0,alloc));
+ assertTrue(new IFG().build(0,alloc));
alloc.insertBefore(phi,slot,"test",(byte)0,alloc.lrg(phi));
assertSame(top,phi.in(slot));
}