summaryrefslogtreecommitdiff
path: root/chapter32
diff options
context:
space:
mode:
Diffstat (limited to 'chapter32')
-rw-r--r--chapter32/README.md48
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java18
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java12
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java4
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java110
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java84
6 files changed, 239 insertions, 37 deletions
diff --git a/chapter32/README.md b/chapter32/README.md
index 4cb1d79b..d7ca40db 100644
--- a/chapter32/README.md
+++ b/chapter32/README.md
@@ -221,6 +221,54 @@ After these fixes, all 802 suite executions pass at log 8; 444 chapter tests and
34 focused worklist, scheduling, and memory tests pass at log 1. Existing spill
expectations are unchanged.
+### Dense MemMerge inputs
+
+`MemMergeNode` now keeps precise alias slices in a dense input list, with an
+`IntHashMap` from alias to input index and a reverse array for iteration.
+Alias order is preserved. Missing aliases use input 1, the bulk default.
+Deletion compacts the list and rebuilds the small map; graph copies own their
+maps. Bulk-Phi splitting and object loading use alias lookup rather than
+assuming an alias is an input index. The existing sparse object encoding remains
+compatible with the baseline compiler.
+
+This is deliberately a storage experiment. `_aliasLimit` retains the previous
+sparse extent for encoding and fold eligibility. The old `allDefault` test
+counts null holes as non-defaults; simply folding whenever the dense list is
+empty introduces additional optimizations. That separate trial altered code
+quality: graphical Tic-tac-toe's weighted spill score rose from 1085 to 1240
+with its rebuilt library. The retained version preserves the old folding
+behavior and matches baseline peephole counts, code sizes, and spill counts on
+all measured workloads.
+
+Against commit `8b80d94c`, the final interleaved comparison measured:
+
+| Workload | Compile time change | Compiler-thread allocation change |
+| --- | ---: | ---: |
+| sys library | -5.8% | -3.7% |
+| Clock | -2.1% | -10.8% |
+| Breakout | -2.9% | -6.4% |
+| Graphical tic-tac-toe | -0.5% | -5.3% |
+| HelloWorld | -0.6% | -4.5% |
+
+The timing improvement is modest; sub-percent differences are within noise.
+The structural reduction is much larger. After Lower, sys's live MemMerge input
+slots fall from 54,388 to 2,462, Clock's from 54,255 to 2,237, and Breakout's from
+61,286 to 2,592. These are input-slot counts, not total heap measurements; the
+maps and reverse arrays have their own cost.
+
+Measurements use Java 21, assertions at log10, two active processors, and a
+256 MiB initial / 2 GiB maximum heap. The compiler runs through object export,
+without gcc, linking, or execution. Isolated compiler class loaders alternate
+in one JVM; six measured rounds follow three warmups for each workload. Games
+read the same baseline sys objects. Time changes are medians of paired ratios;
+allocation uses ThreadMXBean. Earlier separate-process runs drifted enough that
+the interleaved comparison is the basis for the table.
+
+The full suite passes at log8; 444 chapter tests and 18 memory/import tests pass
+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`.
+
## Build and test
From `chapter32`, using the existing offline dependency caches:
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
index b168c4af..e1aee9aa 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
@@ -265,9 +265,10 @@ public class Serialize {
}
// Write out the input indices packed.
for( Node n : nodes ) {
- for( int j=0; j<n.nIns(); j++ ) {
+ int count = n instanceof MemMergeNode mem ? mem.packedSize() : n.nIns();
+ for( int j=0; j<count; j++ ) {
if( !writeInput(n,j,anodes) ) continue;
- Node def = n.in(j);
+ Node def = n instanceof MemMergeNode mem ? mem.packedInput(j) : n.in(j);
Integer idx = def==null ? Integer.valueOf(0) : anodes.get(def);
// Imported function constants retain their symbol, not a body.
if( idx==null && n instanceof FunPtrNode && j==1 ) idx=0;
@@ -500,19 +501,18 @@ public class Serialize {
// Node edges
for( Node n : nodes ) {
- int len = n.nIns();
+ int len = n instanceof MemMergeNode mem ? mem.readSize() : n.nIns();
for( int i = 0; i<len; i++ ) {
int idx = bais.packed2();
Node def = idx==0 ? null : nodes.at(idx-1);
// MemMerge precise aliases are encoded by their input slot.
// Remap populated file-local slots into this compilation's
// local alias numbering; null holes carry no identity.
- int local = i;
- if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) {
- if( def == null ) continue;
- local = aliases.map(fileAliases,i);
- }
- n.setDefX(local,def);
+ if( n instanceof MemMergeNode mem && i>=2 ) {
+ if( def==null ) continue;
+ int alias = i>=GlobalBits.RESERVED ? aliases.map(fileAliases,i) : i;
+ mem.alias(alias,def);
+ } else n.setDefX(i,def);
// Call's output[0] is always the CallEnd
if( n instanceof CallEndNode cend && i==0 ) {
var outs = cend.call()._outputs;
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
index b49163e7..f4d1e195 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
@@ -118,7 +118,7 @@ public class BulkMemPhiNode extends PhiNode {
} else if( m instanceof MemMergeNode mmm &&
mmm.in(1) instanceof BulkMemPhiNode bulk &&
bulk._aliases.get(alias) &&
- (alias >= mmm.nIns() || mmm.in(alias)==null) )
+ mmm.explicitAlias(alias)==null )
return false;
return true;
}
@@ -187,11 +187,9 @@ public class BulkMemPhiNode extends PhiNode {
// First explicit MemMerge slice still covered by this Phi. A user's slice
// may point to this Phi after a precise Phi folds; splitting is still valid.
private int missingAlias( MemMergeNode mmm ) {
- for( int alias=2; alias<mmm.nIns(); alias++ )
- if( mmm.in(alias)!=null &&
- mmm.alias(alias)!=mmm.in(1) &&
- !_aliases.get(alias) )
- return alias;
+ for( int i=2; i<mmm.nIns(); i++ )
+ if( mmm.in(i)!=null && mmm.in(i)!=mmm.in(1) && !_aliases.get(mmm.aliasAt(i)) )
+ return mmm.aliasAt(i);
return 0;
}
@@ -310,7 +308,7 @@ public class BulkMemPhiNode extends PhiNode {
static boolean checkMerge(MemMergeNode mmm) {
if( !(mmm.in(1) instanceof BulkMemPhiNode bulk) ) return true;
for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) )
- if( alias >= mmm.nIns() || mmm.in(alias)==null )
+ if( mmm.explicitAlias(alias)==null )
return false;
return true;
}
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index c4d55335..2ab76429 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -60,12 +60,12 @@ public class LoopNode extends RegionNode {
// executing. Keep synthetic nodes local; do not GVN into that graph.
Node top = ConstantNode.raw(Type.TOP);
top.setDef(0,fun);
- Node memout = new MemMergeNode();
+ MemMergeNode memout = new MemMergeNode();
memout.addDef(f); // placeholder for control
memout.addDef(top);
for( Node u : _outputs )
if( u instanceof PhiNode phi && phi._type.isa(TypeMem.BOT) )
- memout.addDef(phi);
+ memout.alias(memout.nIns(),phi);
memout.init();
Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr();
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
index 19420839..d5eaa743 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
@@ -8,30 +8,78 @@ import com.seaofnodes.simple.codegen.CodeGen;
import com.seaofnodes.simple.util.BAOS;
import com.seaofnodes.simple.type.*;
import com.seaofnodes.simple.util.Utils;
+import com.seaofnodes.simple.util.AryInt;
+import com.seaofnodes.simple.util.IntHashMap;
import java.util.*;
/**
- * Memory Merge - a merge of many aliases into a "fat memory". All aliases
- * are here, but most will be lazy - take the default fat memory.
+ * Memory merge: default bulk memory plus dense inputs for explicit alias slices.
*/
public class MemMergeNode extends Node {
public MemMergeNode( Node ...nodes) { super(nodes); _type = TypeMem.BOT; }
- public MemMergeNode(MemMergeNode mem) { super(mem); }
+ // Inputs 0/1 are control/default; the remaining inputs are dense precise slices.
+ // Keep alias order so graph walks retain the old sparse representation's order.
+ private AryInt _aliases;
+ private IntHashMap _aliasToInput;
+ private int _readSize;
+ // Retain the old sparse extent for encoding and fold eligibility, without its holes.
+ private int _aliasLimit=2;
+
+ public MemMergeNode(MemMergeNode mem) { super(mem); copyAliases(mem); _aliasLimit=mem._aliasLimit; }
+
+ private void copyAliases(MemMergeNode mem) {
+ if( mem._aliases==null ) return;
+ _aliases = new AryInt().addAll(mem._aliases);
+ _aliasToInput = new IntHashMap(0);
+ reindex();
+ }
+
+ @Override protected Object clone() throws CloneNotSupportedException {
+ MemMergeNode copy = (MemMergeNode)super.clone();
+ copy.copyAliases(this);
+ return copy;
+ }
+
+ public int aliasAt(int input) { return _aliases.at(input-2); }
+
+ // Explicit input, or null when the default supplies this alias.
+ public Node explicitAlias(int alias) {
+ int input = _aliasToInput==null ? 0 : _aliasToInput.get(alias);
+ return input==0 ? null : in(input);
+ }
+
+ // Preserve the existing sparse object encoding; input indices on disk are aliases.
+ public int packedSize() { return _aliasLimit; }
+ public int readSize() { return _readSize; }
+ public Node packedInput(int alias) { return alias<2 ? in(alias) : explicitAlias(alias); }
+
+ private void reindex() {
+ _aliasToInput.clear();
+ for( int i=0; i<_aliases.len(); i++ ) _aliasToInput.put(_aliases.at(i),i+2);
+ }
+
+ private void removeAlias(int input) {
+ setDef(input,null);
+ _inputs.remove(input);
+ _aliases.remove(input-2);
+ reindex();
+ }
@Override public Tag serialTag() { return Tag.MemMerge; }
public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) {
// A memory merge always has inputs. Zero escapes a wide alias table,
// preserving every existing nonzero single-byte count.
assert nIns()>0;
- baos.packed1(nIns()<=255 ? nIns() : 0);
- if( nIns()>255 ) baos.packed4(nIns());
+ baos.packed1(packedSize()<=255 ? packedSize() : 0);
+ if( packedSize()>255 ) baos.packed4(packedSize());
}
static Node make( BAOS bais ) {
int count=bais.packed1();
if( count==0 ) count=bais.packed4();
- Node mem=new MemMergeNode();
- mem.setDefX(count-1,null);
+ MemMergeNode mem=new MemMergeNode(null,null);
+ mem._readSize=count;
+ mem._aliasLimit=count;
return mem;
}
@@ -42,7 +90,7 @@ public class MemMergeNode extends Node {
protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
p.p("MEM[ ");
for( int j=2; j<nIns(); j++ ) {
- p.p(j);
+ p.p(aliasAt(j));
p.p(":");
Node n = in(j);
while( n instanceof ScopeNode loop ) {
@@ -93,7 +141,7 @@ public class MemMergeNode extends Node {
TypeMem mem = defmem;
for( int i=2; i<nIns(); i++ ) {
// Has this alias escaped?
- if( XInt.bit(mem._escAs,i) &&
+ if( XInt.bit(mem._escAs,aliasAt(i)) &&
in(i) != null && !in(i)._type.isHigh() ) {
mem = (TypeMem)mem.meet(in(i)._type);
}
@@ -104,11 +152,13 @@ public class MemMergeNode extends Node {
@Override public Node idealize() {
assert nIns() != 0 && in(1)!=null; // Always have a default. if( nIns()==0 ) return null;
- // Fold defaults into the default
- boolean progress=false, allDefault=true;
+ // Preserve the existing fold rule for this storage experiment: every alias
+ // slot must explicitly equal the default. Do not also change which empty
+ // aggregates fold away; that changes optimization order and spill decisions.
+ boolean progress=false, allDefault=nIns()==_aliasLimit;
for( int i=2; i<nIns(); i++ ) {
- if( in(1) == in(i) ) { setDef(i,null); progress=true; }
- else { allDefault=false; }
+ if( in(1)==in(i) ) { removeAlias(i--); progress=true; }
+ else allDefault=false;
}
// If not merging any memory (all memory is just the default)
@@ -124,8 +174,9 @@ public class MemMergeNode extends Node {
for( int i=2; i<mem.nIns(); i++ ) {
if( mem.in(i) != null ) {
// deeper default mem has a non-default
- if( i>=nIns() || in(i)==null )
- setDefX(i,mem.in(i));
+ int alias = mem.aliasAt(i);
+ if( explicitAlias(alias)==null )
+ alias(alias,mem.in(i));
}
}
CodeGen.CODE.add(mem.in(1));
@@ -140,12 +191,33 @@ public class MemMergeNode extends Node {
public Node in( Var v ) { return in(v._idx); }
public Node alias( int alias ) {
- assert !(in(1) instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) &&
- (alias >= nIns() || in(alias)==null));
- return alias < nIns() && in(alias)!=null ? in(alias) : in(1);
+ Node precise = explicitAlias(alias);
+ assert !(in(1) instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) && precise==null);
+ return precise==null ? in(1) : precise;
}
- public Node alias( int alias, Node st ) { return setDefX(alias,st); }
+ public Node alias( int alias, Node st ) {
+ if( alias==1 ) return setDef(1,st);
+ assert alias>1;
+ _aliasLimit=Math.max(_aliasLimit,alias+1);
+ int input = _aliasToInput==null ? 0 : _aliasToInput.get(alias);
+ if( st==null ) {
+ if( input!=0 ) removeAlias(input);
+ return st;
+ }
+ if( input!=0 ) return setDef(input,st);
+ if( _aliases==null ) {
+ _aliases = new AryInt();
+ _aliasToInput = new IntHashMap(0);
+ }
+ int pos = Arrays.binarySearch(_aliases._es,0,_aliases.len(),alias);
+ assert pos<0;
+ pos = -pos-1;
+ _aliases.insert(pos,alias);
+ for( int i=pos; i<_aliases.len(); i++ ) _aliasToInput.put(_aliases.at(i),i+2);
+ insertDef(pos+2,st);
+ return st;
+ }
// Now one-time do a useless-phi removal
void _useless( ) {
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java
new file mode 100644
index 00000000..cb17982e
--- /dev/null
+++ b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java
@@ -0,0 +1,84 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeMem;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class MemMergeTest {
+ @Test public void testDenseAliasesAndDefaults() {
+ CodeGen code = new CodeGen("");
+ Node defaults = code.con(TypeMem.START), value = code.con(TypeMem.BOT).keep();
+ MemMergeNode mem = new MemMergeNode(null,defaults);
+ mem.alias(10000,value);
+ mem.alias(2,value);
+ mem.alias(513,value);
+ assertEquals(5,mem.nIns());
+ assertEquals(2,mem.aliasAt(2));
+ assertEquals(513,mem.aliasAt(3));
+ assertEquals(10000,mem.aliasAt(4));
+ assertSame(value,mem.alias(10000));
+ assertSame(defaults,mem.alias(512));
+ assertEquals(10001,mem.packedSize());
+ assertNull(mem.packedInput(9999));
+ assertSame(value,mem.packedInput(10000));
+ mem.alias(513,null);
+ assertEquals(4,mem.nIns());
+ assertEquals(10000,mem.aliasAt(3));
+ assertSame(value,mem.alias(10000));
+ mem.alias(2,defaults);
+ assertSame(mem,mem.idealize());
+ assertEquals(3,mem.nIns());
+ assertSame(defaults,mem.alias(2));
+ // Removing/reinserting colliding keys must not leave tombstones or stale slots.
+ for( int i=0; i<100; i++ ) {
+ mem.alias(100+i*8,value);
+ mem.alias(100+i*8,null);
+ }
+ assertEquals(3,mem.nIns());
+ mem.alias(10000,defaults);
+ assertSame(mem,mem.idealize());
+ assertEquals(2,mem.nIns());
+ // Retain the sparse implementation's fold eligibility for this experiment.
+ assertNull(mem.idealize());
+ assertSame(defaults,new MemMergeNode(null,defaults).idealize());
+ value.unkeep();
+ }
+
+ @Test public void testIndependentCopyMaps() {
+ CodeGen code = new CodeGen("");
+ Node defaults = code.con(TypeMem.START), value = code.con(TypeMem.BOT);
+ MemMergeNode mem = new MemMergeNode(null,defaults);
+ mem.alias(200,value);
+ MemMergeNode copy = (MemMergeNode)mem.copyEmpty();
+ for( Node in : mem._inputs ) copy.addDef(in);
+ copy.alias(7,value);
+ assertEquals(3,mem.nIns());
+ assertEquals(4,copy.nIns());
+ assertSame(defaults,mem.alias(7));
+ assertSame(value,mem.alias(200));
+ copy.alias(200,null);
+ assertSame(value,mem.alias(200));
+ assertSame(defaults,copy.alias(200));
+ code._phase = CodeGen.Phase.Select;
+ MemMergeNode selected = new MemMergeNode(mem);
+ assertEquals(200,selected.aliasAt(2));
+ assertSame(value,selected.alias(200));
+ }
+
+ @Test public void testStackedMergesKeepOverrides() {
+ CodeGen code = new CodeGen("");
+ Node defaults = code.con(TypeMem.START), value = code.con(TypeMem.BOT), override = code.con(TypeMem.TOP);
+ MemMergeNode inner = new MemMergeNode(null,defaults);
+ inner.alias(8,value);
+ inner.alias(10000,value);
+ MemMergeNode outer = new MemMergeNode(null,inner);
+ outer.alias(10000,override);
+ assertSame(outer,outer.idealize());
+ assertEquals(4,outer.nIns());
+ assertSame(defaults,outer.in(1));
+ assertSame(value,outer.alias(8));
+ assertSame(override,outer.alias(10000));
+ }
+}