Chapter 25: Modules, Separate Compilation, and SSA Constructionlinear

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

3 files changed, 228 insertions, 1 deletions

diff --git a/src/main/java/com/seaofnodes/simple/util/BAOS.java b/src/main/java/com/seaofnodes/simple/util/BAOS.java
new file mode 100644
index 00000000..61ce7387
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/util/BAOS.java
@@ -0,0 +1,162 @@
+package com.seaofnodes.simple.util;
+
+import java.util.HashMap;
+import java.util.Arrays;
+
+// "ByteArrayOutputStream", and Input Stream and not synchronized and has
+// matching pack/unpack strategies.
+public class BAOS {
+
+    private byte[] _buf;
+    private int _len;
+
+    public BAOS() { _buf = new byte[1]; }
+    public BAOS(byte[] buf) { _buf = buf; }
+    public BAOS(byte[] buf, int x) { _buf = buf; _len = x; }
+
+    public byte[] toByteArray() {
+        return Arrays.copyOf(_buf,_len);
+    }
+
+    public byte[] buf() { return _buf; }
+    public int size() { return _len; }
+    public void set( byte[] buf, int len ) { _buf=buf; _len=len; }
+    public void clear() { _len=0; }
+
+    // -----------------------------------------------------------------------
+    // Basic read, write (expand)
+
+    private void grow(int len) {
+        while( _len+len >= _buf.length )
+            _buf = Arrays.copyOf(_buf,_buf.length*2);
+    }
+
+    // Write a byte, grow as needed; silent chop
+    public BAOS write(int b) {
+        grow(1);
+        _buf[_len++] = (byte)b; // Silent chop
+        return this;
+    }
+
+    // Read an UNSIGNED bytes at INDEX, AIOOBE if off end
+    public int read1(int idx) { return _buf[idx] & 0xFF; }
+
+    // Read an UNSIGNED byte, AIOOBE if off end
+    public int read() { return read1(_len++); }
+
+    // write 2 bytes
+    public BAOS write2( int x ) {
+        grow(2);
+        _buf[_len++] = (byte)(x>> 0);
+        _buf[_len++] = (byte)(x>> 8);
+        return this;
+    }
+
+    // Read a u16 in 2 bytes
+    public int read2(int idx) { return read1(idx) | (read1(idx+1)<<8);  }
+    public int read2() { int rez = read2(_len); _len+=2; return rez; }
+
+    // write 4 bytes
+    public BAOS write4( int x ) {
+        grow(4);
+        _buf[_len++] = (byte)(x>> 0);
+        _buf[_len++] = (byte)(x>> 8);
+        _buf[_len++] = (byte)(x>>16);
+        _buf[_len++] = (byte)(x>>24);
+        return this;
+    }
+
+    // Read a i32 in 4 bytes
+    public int read4(int idx) { return read2(idx) | (read2(idx+2)<<16);  }
+    public int read4() { int rez = read4(_len); _len+=4; return rez; }
+
+    // write 8 bytes
+    public BAOS write8( long x ) {
+        write4((int) x     );
+        write4((int)(x>>32));
+        return this;
+    }
+
+    // Read a i64 in 8 bytes
+    public long read8(int idx) { return ((long)read4(idx) & 0xFFFFFFFFL) | ((long)read4(idx+4)<<32); }
+    public long read8() { long rez = read8(_len); _len+=8; return rez; }
+
+    // Write byte array
+    public void write( byte[] bs ) {
+        grow(bs.length);
+        System.arraycopy(bs,0,_buf,_len,bs.length);
+        _len += bs.length;
+    }
+
+    // Read/fill byte array
+    public byte[] read( byte[] bs ) {
+        System.arraycopy(_buf,_len,bs,0,bs.length);
+        _len += bs.length;
+        return bs;
+    }
+
+    // -----------------------------------------------------------------------
+    // Write a packed integer to the BAOS.  Track a histogram to make more
+    // intelligent choices in the future.
+    private static final HashMap<Long,Integer> PACKED_HISTOGRAM = new HashMap<>();
+    private BAOS histo(long x) {
+        Integer cnt = PACKED_HISTOGRAM.get(x);
+        PACKED_HISTOGRAM.put(x,cnt==null ? 1 : cnt+1);
+        return this;
+    }
+
+    // Write a u8 (checked)
+    public void packed1(int x) {
+        assert 0 <= x && x <= 255;
+        histo(x).write(x);
+    }
+
+    public int packed1() { return read(); }
+
+    // Write a u16 (checked)
+    public void packed2(int x) {
+        assert 0 <= x && x <= 65535;
+        (( x <= 254 ) ? write(x) : write(0xFF).write2(x)).histo(x);
+    }
+
+    // Read a packed u16
+    public int packed2() {
+        int x = read();
+        return x==0xFF ? read2() : x;
+    }
+
+    // Write a packed i32
+    public void packed4(int x) {
+        ((-127 <= x && x <= 127 ) ? write(x) : write(-128).write4(x)).histo(x);
+    }
+
+    // Read a packed i32
+    public int packed4() {
+        int x = _buf[_len++];   // Signed byte read
+        return x== -128 ? read4() : x;
+    }
+
+    // Write a packed i64
+    public void packed8(long x) {
+        ((-127 <= x && x <= 127 ) ? write((int)x) : write(-128).write8(x)).histo(x);
+    }
+
+    // Read a packed i64
+    public long packed8() {
+        int x = _buf[_len++];   // Signed byte read
+        return x== -128 ? read8() : x;
+    }
+
+    public void packedS(String s) {
+        packed4(s.length());
+        for( int i=0; i<s.length(); i++ )
+            packed4(s.charAt(i));
+    }
+
+    public String packedS() {
+        int len = packed4();
+        String s = new String(_buf,_len,len).intern();
+        _len += len;
+        return s;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/util/IntHashMap.java b/src/main/java/com/seaofnodes/simple/util/IntHashMap.java
new file mode 100644
index 00000000..55aaa9f9
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/util/IntHashMap.java
@@ -0,0 +1,65 @@
+package com.seaofnodes.simple.util;
+
+import java.util.Arrays;
+
+// Int-Int Hash Map
+public class IntHashMap {
+    private int[] _es;
+    private int _size;
+    private final int _sentinel;
+
+    // Pick a sentinel value; not allowed for keys or values.  Sentinel is
+    // returned on a miss.  Writing sentinel counts as a remove.
+    public IntHashMap(int sentinel) {
+        _sentinel = sentinel;
+        _es = new int[4];
+        Arrays.fill(_es,sentinel);
+    }
+
+    public int size() { return _size; }
+    public void clear() {
+        _size = 0;
+        Arrays.fill(_es,_sentinel);
+    }
+
+    private int cap() { return _es.length>>1; }
+
+    public int put( int key, int val ) {
+        int slot = probe(key);
+        int old = _es[(slot<<1)+1];
+        if( old == _sentinel && val != _sentinel ) _size++;
+        if( old != _sentinel && val == _sentinel ) _size--;
+        // Check cap
+        if( _size > ((cap()>>1) + (cap()>>2)) ) {
+            grow();
+            slot = probe(key);
+        }
+
+        _es[ slot<<1   ] = key;
+        _es[(slot<<1)+1] = val;
+        return old;
+    }
+
+    public int get( int key ) {
+        int slot = probe(key);
+        return _es[(slot<<1)+1];
+    }
+
+    int probe( int key ) {
+        int mask = cap()-1;
+        int slot = key & mask;
+        while( _es[slot<<1] != _sentinel && _es[slot<<1] != key )
+            slot = (slot + (key|1)) & mask;
+        return slot;
+    }
+
+    // Double underlying array size
+    private void grow() {
+        int[] old = _es;
+        _es = new int[_es.length<<1];
+        Arrays.fill(_es,_sentinel);
+        for( int i=0; i<old.length; i+=2 )
+            if( old[i] != _sentinel )
+                put(old[i],old[i+1]);
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/util/SB.java b/src/main/java/com/seaofnodes/simple/util/SB.java
index d7afd6eb..cc59f2a6 100644
--- a/src/main/java/com/seaofnodes/simple/util/SB.java
+++ b/src/main/java/com/seaofnodes/simple/util/SB.java
@@ -42,7 +42,7 @@ public final class SB {
   // 4 bytes, 8 hex digits, 32 bits, Big Endian
   public SB hex4(int s) { return hex2(s>>16).hex2(s); }
   // 8 bytes, 16 hex digits, 64 bits, Big Endian
-    public SB hex8(long s) { return hex4((int)(s>>32)).hex4((int)s); }
+  public SB hex8(long s) { return hex4((int)(s>>32)).hex4((int)s); }
 
   // Fixed width field
   public SB fix( int sz, String s ) {