summaryrefslogtreecommitdiff
path: root/chapter32/src/main/java/com
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-11-16 10:18:30 -0800
committerCliff Click <cliffc@acm.org>2026-11-16 10:18:30 -0800
commit51a029304d8105b201bdfb81a7692b8a1b16b028 (patch)
tree32f5312796aebf0b857eb9a7042249c9e08a334a /chapter32/src/main/java/com
parentc21026c5377429b11e285d251439407074fe3cd1 (diff)
downloadSimple-51a029304d8105b201bdfb81a7692b8a1b16b028.tar.gz
Simple-51a029304d8105b201bdfb81a7692b8a1b16b028.zip
Packing Serialize tighter
Diffstat (limited to 'chapter32/src/main/java/com')
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java23
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java21
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java5
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java33
4 files changed, 49 insertions, 33 deletions
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 e1aee9aa..9c43e029 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java
@@ -103,8 +103,10 @@ public class Serialize {
Type startType = TypeTuple.make(Type.CONTROL,stopType.mem(),((StartNode)nodes.at(0)).arg());
BAOS baos = new BAOS();
- // A - Print the C0DE header. The format is not versioned yet.
- baos.write('C').write('0').write('D').write('E');
+ // A - Print the C0DE header; last byte is the version number.
+ // Format 2: gradual packed ints, UTF-8 strings, sparse MemMerge edges,
+ // and wider singleton function IDs. Reject old cached objects clearly.
+ baos.write('C').write('0').write('D').write('2');
// Count unique Types
var types = new HashMap<Type,Integer>();
@@ -265,10 +267,12 @@ public class Serialize {
}
// Write out the input indices packed.
for( Node n : nodes ) {
- int count = n instanceof MemMergeNode mem ? mem.packedSize() : n.nIns();
+ int count = n.nIns();
for( int j=0; j<count; j++ ) {
if( !writeInput(n,j,anodes) ) continue;
- Node def = n instanceof MemMergeNode mem ? mem.packedInput(j) : n.in(j);
+ if( n instanceof MemMergeNode mem && j>=2 )
+ baos.packed2(mem.aliasAt(j));
+ Node def = 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;
@@ -331,7 +335,7 @@ public class Serialize {
Type.TAGOFFS();
// A - Read a header
- if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='E' )
+ if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='2' )
throw new IllegalArgumentException("Unsupported serialized IR format; rebuild the object file");
// B - Packed read of #strings, then strings
@@ -364,7 +368,7 @@ public class Serialize {
String[] strs = elf._strs;
if( strs == null ) {
// A - Read a header
- if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != 'E' )
+ if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != '2' )
throw new IllegalArgumentException( "Unsupported serialized IR format; rebuild the object file" );
// B - Packed read of #strings, then strings
@@ -503,14 +507,13 @@ public class Serialize {
for( Node n : nodes ) {
int len = n instanceof MemMergeNode mem ? mem.readSize() : n.nIns();
for( int i = 0; i<len; i++ ) {
+ int fileAlias = n instanceof MemMergeNode && i>=2 ? bais.packed2() : 0;
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.
+ // Remap only explicit slices; omitted aliases use the default.
if( n instanceof MemMergeNode mem && i>=2 ) {
if( def==null ) continue;
- int alias = i>=GlobalBits.RESERVED ? aliases.map(fileAliases,i) : i;
+ int alias = aliases.map(fileAliases,fileAlias);
mem.alias(alias,def);
} else n.setDefX(i,def);
// Call's output[0] is always the CallEnd
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 d5eaa743..a077e14b 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
@@ -24,7 +24,7 @@ public class MemMergeNode extends Node {
private AryInt _aliases;
private IntHashMap _aliasToInput;
private int _readSize;
- // Retain the old sparse extent for encoding and fold eligibility, without its holes.
+ // Retain the old sparse extent for fold eligibility, without its holes.
private int _aliasLimit=2;
public MemMergeNode(MemMergeNode mem) { super(mem); copyAliases(mem); _aliasLimit=mem._aliasLimit; }
@@ -50,10 +50,8 @@ public class MemMergeNode extends Node {
return input==0 ? null : in(input);
}
- // Preserve the existing sparse object encoding; input indices on disk are aliases.
- public int packedSize() { return _aliasLimit; }
+ // The reader has not wired the dense inputs yet.
public int readSize() { return _readSize; }
- public Node packedInput(int alias) { return alias<2 ? in(alias) : explicitAlias(alias); }
private void reindex() {
_aliasToInput.clear();
@@ -68,18 +66,17 @@ public class MemMergeNode extends Node {
}
@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(packedSize()<=255 ? packedSize() : 0);
- if( packedSize()>255 ) baos.packed4(packedSize());
+ // Keep the extent even if its last precise slice was removed. Edges
+ // are dense: control/default followed by explicit (alias,input) pairs.
+ baos.packed4(_aliasLimit);
+ baos.packed2(nIns());
}
static Node make( BAOS bais ) {
- int count=bais.packed1();
- if( count==0 ) count=bais.packed4();
+ int limit=bais.packed4(), count=bais.packed2();
+ assert 2<=count && count<=limit;
MemMergeNode mem=new MemMergeNode(null,null);
mem._readSize=count;
- mem._aliasLimit=count;
+ mem._aliasLimit=limit;
return mem;
}
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
index 19ec5019..c6f53022 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
@@ -248,7 +248,7 @@ public class TypeFunPtr extends TypeNil {
@Override int TAGOFF() { return 8; }
@Override public void packed( BAOS baos, HashMap<String,Integer> strs ) {
assert _open; // Open: Passing extra args is fine, and extras ignored.
- if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx() < 64 ) {
+ if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx()<=65535 ) {
baos.write(TAGOFFS[_type] + nargs());
baos.packed2(fidx());
} else {
@@ -259,8 +259,7 @@ public class TypeFunPtr extends TypeNil {
}
static TypeFunPtr packed( int tag, BAOS bais ) {
if( tag < 6 ) {
- int fidx = bais.read();
- assert fidx < 64; // Need a larger fidx space
+ int fidx = bais.packed2();
return malloc((byte)2,true,new Type[tag],null, XInt.make(fidx));
}
byte nil = (byte)(tag==6 ? 2 : 3);
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java b/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java
index a4d1f183..c47d386c 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple.util;
//import java.util.HashMap;
import java.util.Arrays;
+import java.nio.charset.StandardCharsets;
// "ByteArrayOutputStream", and Input Stream and not synchronized and has
// matching pack/unpack strategies.
@@ -125,15 +126,29 @@ public class BAOS {
return x==0xFF ? read2() : x;
}
- // Write a packed i32
+ // Signed zigzag varint: -64..63 use one byte, -8192..8191 two,
+ // and the full int range needs at most five. Seven payload bits per byte.
public void packed4(int x) {
- ((-127 <= x && x <= 127 ) ? write(x) : write(-128).write4(x)).histo(x);
+ histo(x);
+ int bits = (x<<1) ^ (x>>31);
+ while( (bits & ~127)!=0 ) {
+ write((bits & 127) | 128);
+ bits >>>= 7;
+ }
+ write(bits);
}
// Read a packed i32
public int packed4() {
- int x = _buf[_len++]; // Signed byte read
- return x== -128 ? read4() : x;
+ int bits=0;
+ for( int shift=0; shift<32; shift+=7 ) {
+ int b = read();
+ if( shift==28 && (b & 0xF0)!=0 )
+ throw new IllegalArgumentException("Packed int overflow");
+ bits |= (b & 127)<<shift;
+ if( (b & 128)==0 ) return (bits>>>1) ^ -(bits & 1);
+ }
+ throw new IllegalArgumentException("Unterminated packed int");
}
// Write a packed i64
@@ -148,14 +163,16 @@ public class BAOS {
}
public void packedS(String s) {
- packed4(s.length());
- for( int i=0; i<s.length(); i++ )
- packed4(s.charAt(i));
+ // Strings are bytes, not signed packed integers. Keep ASCII at one
+ // byte per character and agree on the representation of non-ASCII.
+ byte[] utf8 = s.getBytes(StandardCharsets.UTF_8);
+ packed4(utf8.length);
+ write(utf8);
}
public String packedS() {
int len = packed4();
- String s = new String(_buf,_len,len).intern();
+ String s = new String(_buf,_len,len,StandardCharsets.UTF_8).intern();
_len += len;
return s;
}