From b8bcd9c0e826c7cb0b45d1ae5a52a325d22fd048 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 15 Nov 2026 18:45:08 -0800 Subject: Make MemMerge inputs packed --- .../com/seaofnodes/simple/codegen/Serialize.java | 18 ++-- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 12 +-- .../java/com/seaofnodes/simple/node/LoopNode.java | 4 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 110 +++++++++++++++++---- 4 files changed, 107 insertions(+), 37 deletions(-) (limited to 'chapter32/src/main/java/com') 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= 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= 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 strs, HashMap types, IdentityHashMap 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 _print1(ExprPrinter p) { p.p("MEM[ "); for( int j=2; j=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( ) { -- cgit v1.2.3