summaryrefslogtreecommitdiff
path: root/chapter32/src
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
parentc21026c5377429b11e285d251439407074fe3cd1 (diff)
downloadSimple-51a029304d8105b201bdfb81a7692b8a1b16b028.tar.gz
Simple-51a029304d8105b201bdfb81a7692b8a1b16b028.zip
Packing Serialize tighter
Diffstat (limited to 'chapter32/src')
-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
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java58
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java5
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java36
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java20
8 files changed, 165 insertions, 36 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;
}
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java b/chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java
new file mode 100644
index 00000000..03e53b6d
--- /dev/null
+++ b/chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java
@@ -0,0 +1,58 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.type.PackedTypeTestSupport;
+import com.seaofnodes.simple.util.BAOS;
+import java.util.Random;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class BAOSTest {
+ @Test public void packedIntBoundaries() {
+ int[] values={Integer.MIN_VALUE,-134217729,-134217728,-1048577,-1048576,
+ -8193,-8192,-65,-64,-1,0,1,63,64,8191,8192,1048575,1048576,
+ 134217727,134217728,Integer.MAX_VALUE};
+ int[] widths={5,5,4,4,3,3,2,2,1,1,1,1,1,2,2,3,3,4,4,5,5};
+ BAOS out=new BAOS();
+ for( int i=0; i<values.length; i++ ) {
+ int before=out.size();
+ out.packed4(values[i]);
+ assertEquals("width of "+values[i],widths[i],out.size()-before);
+ }
+ BAOS in=new BAOS(out.toByteArray());
+ for( int value : values ) assertEquals(value,in.packed4());
+ assertEquals(out.size(),in.size());
+ out.clear();
+ out.packed4(-65); out.packed4(64);
+ assertArrayEquals(new byte[]{(byte)0x81,1,(byte)0x80,1},out.toByteArray());
+ }
+
+ @Test public void packedIntsAndStrings() {
+ Random random=new Random(123);
+ int[] values=new int[10000];
+ BAOS out=new BAOS();
+ for( int i=0; i<values.length; i++ ) out.packed4(values[i]=random.nextInt());
+ String[] strings={"","ASCII stays compact", "\u0000", "caf\u00e9 \u65e5\u672c\u8a9e \uD83D\uDE00", "x".repeat(8192)};
+ for( String s : strings ) out.packedS(s);
+ out.packed8(Long.MIN_VALUE);
+ BAOS in=new BAOS(out.toByteArray());
+ for( int value : values ) assertEquals(value,in.packed4());
+ for( String s : strings ) assertEquals(s,in.packedS());
+ assertEquals(Long.MIN_VALUE,in.packed8());
+ assertEquals(out.size(),in.size());
+ }
+
+ @Test public void rejectPackedIntOverflow() {
+ for( byte last : new byte[]{0x10,(byte)0x80} ) {
+ BAOS in=new BAOS(new byte[]{(byte)0x80,(byte)0x80,(byte)0x80,(byte)0x80,last});
+ try { in.packed4(); fail("overflow accepted"); }
+ catch( IllegalArgumentException expected ) { assertTrue(expected.getMessage().contains("overflow")); }
+ }
+ }
+
+ @Test public void wideSingletonFunctionIds() {
+ new CodeGen("");
+ for( int id : new int[]{2,63,64,254,255,256,1024,65535} )
+ PackedTypeTestSupport.singleton(id);
+ }
+}
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java
index cb17982e..253bce0b 100644
--- a/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java
+++ b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java
@@ -20,9 +20,8 @@ public class MemMergeTest {
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));
+ assertNull(mem.explicitAlias(9999));
+ assertSame(value,mem.explicitAlias(10000));
mem.alias(513,null);
assertEquals(4,mem.nIns());
assertEquals(10000,mem.aliasAt(3));
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java b/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java
index 1c278791..404201e3 100644
--- a/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java
+++ b/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java
@@ -10,6 +10,42 @@ import org.junit.Test;
import static org.junit.Assert.*;
public class SeparateCompilationTest {
+ @Test public void testSparseWideMemoryImport() throws Exception {
+ Path build=Path.of("build/objs/separate");
+ Files.createDirectories(build);
+ Path lib=Files.createTempDirectory(build,"wide-memory-");
+ StringBuilder source=new StringBuilder("int f0=7;\n");
+ for( int i=1; i<300; i++ ) source.append("int f").append(i).append("=0;\n");
+ source.append("val touch={int n -> f299+=n; return f0+f299;};");
+ new CodeGen(null,lib.toString(),null,"Wide",source.toString(),123,true,TypeInteger.BOT)
+ .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false);
+ var paths=new Ary<>(new String[]{lib.toString()});
+ CodeGen code=new CodeGen(null,null,paths,"WideEval","return Wide.touch((arg<<32)>>32);",123,true,TypeInteger.BOT)
+ .driver(CodeGen.Phase.TypeCheck);
+ assertEquals("12",Eval2.eval(code,5));
+ TestC.run("return Wide.touch(5)==12 ? 0 : 1;","wide_memory_client",paths,
+ TestC.CALL_CONVENTION,null,null,"",-1);
+ }
+
+ @Test public void testOldObjectFormatRequestsRebuild() throws Exception {
+ Path build=Path.of("build/objs/separate");
+ Files.createDirectories(build);
+ Path lib=Files.createTempDirectory(build,"old-format-");
+ new CodeGen(null,lib.toString(),null,"Old","val value=7;",123,true,TypeInteger.BOT)
+ .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false);
+ Path file=lib.resolve("Old.o");
+ ElfReader elf=ElfReader.load(file.toFile(),null);
+ byte[] bytes=Files.readAllBytes(file);
+ bytes[elf._bais.size()+3]='E'; // Previous C0DE header, before format 2.
+ Files.write(file,bytes);
+ try {
+ ElfReader.load(file.toFile(),null).loadPublicTypes(new CodeGen(""));
+ fail("old format accepted");
+ } catch( IllegalArgumentException expected ) {
+ assertTrue(expected.getMessage().contains("rebuild the object file"));
+ }
+ }
+
@Test public void testImportedReadOnlyPrimitiveArray() throws Exception {
Path build=Path.of("build/objs/separate");
Files.createDirectories(build);
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java b/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java
new file mode 100644
index 00000000..c218e98b
--- /dev/null
+++ b/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java
@@ -0,0 +1,20 @@
+package com.seaofnodes.simple.type;
+
+import com.seaofnodes.simple.util.BAOS;
+import java.util.HashMap;
+import static org.junit.Assert.*;
+
+public class PackedTypeTestSupport {
+ public static void singleton(int id) {
+ Type.TAGOFFS();
+ TypeFunPtr fun=TypeFunPtr.make((byte)2,true,new Type[0],TypeInteger.BOT,XInt.make(id));
+ BAOS out=new BAOS();
+ fun.packed(out,new HashMap<>());
+ assertEquals(id<=254 ? 2 : 4,out.size());
+ BAOS in=new BAOS(out.toByteArray());
+ TypeFunPtr copy=(TypeFunPtr)Type.packed(in,new String[]{""});
+ assertEquals(id,copy.fidx());
+ assertEquals(0,copy.nargs());
+ assertEquals(out.size(),in.size());
+ }
+}