Add in-memory linker

Encoding supports writing cpool to either Elf or in memory
ElfFile writes constant pool

5 files changed, 102 insertions, 119 deletions

diff --git a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java
index e1120a2f..219c3c44 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java
@@ -144,7 +144,25 @@ public class Parser {
 
         // Parse whole program, as-if function header "{ int arg -> body }"
         parseFunctionBody(_code._main,loc(),"arg");
-        _code.link(_code._main)._name = "main";
+
+        // Kill an empty default main.  Keep only if it was explicitly defined
+        // (programmer asked for a "main") or it has stuff (i.e. beginner
+        // default main).
+        FunNode main = _code.link(_code._main);
+        StopNode stop = _code._stop;
+        if( main.ret().expr() instanceof ConstantNode && main.ret().mem().in(0)==main  && stop.nIns() > 1 ) {
+            // Kill an empty default main; so it does not attempt to put a
+            // "main" in any final ELF file
+            stop.delDef(stop._inputs.find(main.ret()));
+        } else {
+            // We have a non-empty default main.
+            // Check for an explicit main
+            for( Node n : stop._inputs )
+                if( n instanceof FunNode fun && fun._name.equals("main") )
+                    // Found an explicit "main" AND we have a default "main"
+                    throw error("Cannot define both an explicit main and a default main");
+            main._name = "main";
+        }
 
         if( !_lexer.isEOF() ) throw _errorSyntax("unexpected");
 
@@ -154,7 +172,7 @@ public class Parser {
         for( StructNode init : INITS.values() )
             init.unkeep().kill();
         INITS.clear();
-        _code._stop.peephole();
+        stop.peephole();
         if( show ) showGraph();
     }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 32c41b16..64ea8201 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -4,7 +4,6 @@ import com.seaofnodes.simple.*;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.print.*;
 import com.seaofnodes.simple.type.*;
-import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.util.BitSet;
 import java.util.HashMap;
@@ -327,8 +326,8 @@ public class CodeGen {
     public CodeGen exportELF(String fname) throws IOException {
         assert _phase == Phase.Encoding;
         _phase = Phase.Export;
-        ElfFile obj = new ElfFile(this);
-        obj.export(fname);
+        if( fname == null ) new LinkMem(this).link(); // In memory patching
+        else new ElfFile(this).export(fname); // External ELF file
         return this;
     }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
index 6aed0fae..223911ba 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
@@ -3,11 +3,11 @@ package com.seaofnodes.simple.codegen;
 import com.seaofnodes.simple.*;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.codegen.Encoding.BAOS;
 import java.io.*;
 import java.nio.ByteBuffer;
 import java.nio.ByteOrder;
 import java.util.HashMap;
-import java.util.Map;
 
 public class ElfFile {
 
@@ -118,7 +118,7 @@ public class ElfFile {
             out.putLong(size());       // size
             out.putInt(_link);         // link
             out.putInt(_info);         // info
-            out.putLong(1);            // addralign
+            out.putLong(16);           // addralign
             if (_type == 2) {
                 out.putLong(SYMBOL_SIZE);// entsize
             } else if (_type == 4) {
@@ -160,7 +160,7 @@ public class ElfFile {
         }
 
         @Override
-            void write(ByteBuffer out) {
+        void write(ByteBuffer out) {
             // Index 0 both designates the first entry in the table and serves as the undefined symbol index
             for( int i = 0; i < SYMBOL_SIZE/4; i++ ) {
                 out.putInt(0);
@@ -175,7 +175,7 @@ public class ElfFile {
         }
 
         @Override
-            int size() {
+        int size() {
             return (1 + _symbols.len() + _loc.len()) * SYMBOL_SIZE;
         }
     }
@@ -244,7 +244,10 @@ public class ElfFile {
         text._flags = SHF_ALLOC | SHF_WRITE | SHF_EXECINSTR;
         pushSection(text);
 
-        DataSection rdata = new DataSection(".rodata", 1 /* SHT_PROGBITS */);
+        // Build and write constant pool
+        BAOS cpool = new BAOS();
+        _code._encoding.writeConstantPool(cpool,false);
+        DataSection rdata = new DataSection(".rodata", 1 /* SHT_PROGBITS */, cpool);
         rdata._flags = SHF_ALLOC;
         pushSection(rdata);
 
@@ -262,13 +265,12 @@ public class ElfFile {
 
         // calculate local index
         int num = 1;
-        for( Symbol s : symbols._loc ) {
+        for( Symbol s : symbols._loc )
             s._index = num++;
-        }
         int start_global = symbols._loc.size();
-        for(Symbol a: symbols._symbols) {
+        for(Symbol a: symbols._symbols)
             a._index = start_global++;
-        }
+
         // create .text relocations
         DataSection text_rela = new DataSection(".rela.text", 4 /* SHT_RELA */);
         for( Node n : _code._encoding._externals.keySet()) {
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
index 065a555f..0f9aac89 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -44,6 +44,9 @@ public class Encoding {
     public int [] _opStart;     // Start  of opcodes, by _nid
     public byte[] _opLen;       // Length of opcodes, by _nid
 
+    // Big Constant relocation info
+    public final HashMap<Node,Type> _bigCons = new HashMap<>();
+
     Encoding( CodeGen code ) { _code = code; }
 
     // Shortcut to the defining register
@@ -51,23 +54,6 @@ public class Encoding {
         return _code._regAlloc.regnum(n);
     }
 
-    public Encoding add1( int op ) { _bits.write(op); return this; }
-
-    public void add2( int op ) {
-        _bits.write(op    );
-        _bits.write(op>> 8);
-    }
-    // Little endian write of a 32b opcode
-    public void add4( int op ) {
-        _bits.write(op    );
-        _bits.write(op>> 8);
-        _bits.write(op>>16);
-        _bits.write(op>>24);
-    }
-    public void add8( long i64 ) {
-        add4((int) i64     );
-        add4((int)(i64>>32));
-    }
     public int read1(int idx) {
         byte[] buf = _bits.buf();
         return (buf[idx]&0xFF);
@@ -96,11 +82,32 @@ public class Encoding {
         buf[idx+3] = (byte)(val>>24);
     }
 
-    void pad(int n) {
-        while( (_bits.size()+n-1 & -n) > _bits.size() )
-            _bits.write(0);
+    static void padN(int n, BAOS bits) {
+        while( (bits.size()+n-1 & -n) > bits.size() )
+            bits.write(0);
     }
 
+    // Convenience for writing log-N
+    static void addN( int log, Type t, BAOS bits ) {
+        long x = t instanceof TypeInteger ti
+            ? ti.value()
+            : log==3
+            ? Double.doubleToRawLongBits(    ((TypeFloat)t).value())
+            : Float.floatToRawIntBits((float)((TypeFloat)t).value());
+        addN(log,x,bits);
+    }
+    static void addN( int log, long x, BAOS bits ) {
+        for( int i=0; i < 1<<log; i++ ) {
+            bits.write((int)x);
+            x >>= 8;
+        }
+    }
+
+    public Encoding add1( int op ) { addN(0,op,_bits); return this; }
+    public Encoding add2( int op ) { addN(1,op,_bits); return this; }
+    public Encoding add4( int op ) { addN(2,op,_bits); return this; }
+    public Encoding add8(long op ) { addN(3,op,_bits); return this; }
+
 
     // Nodes need "relocation" patching; things done after code is placed.
     // Record src and dst Nodes.
@@ -128,7 +135,6 @@ public class Encoding {
 
     // Store t as a 32/64 bit constant in the code space; generate RIP-relative
     // addressing to load it
-    public final HashMap<Node,Type> _bigCons = new HashMap<>();
     public void largeConstant( Node relo, Type t ) {
         assert t.isConstant();
         _bigCons.put(relo,t);
@@ -148,13 +154,6 @@ public class Encoding {
         // Short-form RIP-relative support: replace long encodings with short
         // encodings and compact the code, changing all the offsets.
         compactShortForm();
-
-        // Write any large constants into a constant pool; they
-        // are accessed by RIP-relative addressing.
-        writeConstantPool(true);
-
-        // Patch RIP-relative and local encodings now.
-        patchLocalRelocations();
     }
 
     // Basic block layout: invert branches to keep blocks in-order; insert
@@ -277,7 +276,7 @@ public class Encoding {
             if( !(bb instanceof MachNode mach0) )
                 _opStart[bb._nid] = _bits.size();
             else if( bb instanceof FunNode fun ) {
-                pad(16);
+                padN(16,_bits);
                 _fun = fun;     // Currently encoding function
                 _opStart[bb._nid] = _bits.size();
                 mach0.encoding( this );
@@ -291,7 +290,7 @@ public class Encoding {
                 }
             }
         }
-        pad(16);
+        padN(16,_bits);
     }
 
     // Short-form RIP-relative support: replace short encodings with long
@@ -315,6 +314,11 @@ public class Encoding {
             slide = 0;
             for( int i=0; i<len; i++ ) {
                 CFGNode bb = _code._cfg.at(i);
+                // Functions pad to align 16
+                if( bb instanceof FunNode ) {
+                    int newStart = _opStart[bb._nid]+slide;
+                    slide += (newStart+15 & -16)-newStart;
+                }
                 _opStart[bb._nid] += slide;
                 if( bb instanceof RIPRelSize riprel ) {
                     CFGNode target = ((CFGNode)bb.out(0)).uctrlSkipEmpty();
@@ -332,12 +336,6 @@ public class Encoding {
                     }
                 }
             }
-
-            // CPool padding is non-linear; in rare cases padding can force a
-            // larger size...  which will shrink the padding and allow the
-            // short form to work.  Too bad.
-            if( !_cpool.isEmpty() )
-                pad(8);
         }
 
 
@@ -358,18 +356,16 @@ public class Encoding {
         }
     }
 
-    // Write the constant pool; either into the code space
-    // and patch locally, or into another BAOS for emission
-    // to the ELF file.
-    public final HashMap<Node,Integer> _cpool = new HashMap<>();
-    public final BAOS _cbits = new BAOS();
-    private void writeConstantPool(boolean elf) {
+
+    // Write the constant pool into the BAOS and optionally patch locally
+    void writeConstantPool( BAOS bits, boolean patch ) {
         HashSet<Type> ts = new HashSet<>();
         for( Type t : _bigCons.values() ) {
             if( ts.contains(t) )
                 throw Utils.TODO(); // Dup!  Compress!
             ts.add(t);
         }
+        padN(16,bits);
 
         // By log size
         for( int log = 3; log >= 0; log-- ) {
@@ -377,82 +373,32 @@ public class Encoding {
             for( Node relo : _bigCons.keySet() ) {
                 Type t = _bigCons.get(relo);
                 if( t.log_size()==log ) {
-                    // Map from relo to constant start
-                    // Else local patch
-                    int target = _bits.size();
-                    int start = _opStart[relo._nid];
-                    ((RIPRelSize)relo).patch(this, start, _opLen[relo._nid], target - start);
-                    if( t instanceof TypeTuple tt ) {
+                    // Map from relo to constant start and patch
+                    if( patch ) {
+                        int target = _bits.size();
+                        int start = _opStart[relo._nid];
+                        ((RIPRelSize)relo).patch(this, start, _opLen[relo._nid], target - start);
+                    }
+                    // Put constant into code space.
+                    if( t instanceof TypeTuple tt ) // Constant tuples put all entries
                         for( Type tx : tt._types )
-                            addN(log,tx);
-                    } else
-                        addN(log,t);
-                    //if( elf ) _cbits.write8(x);
-                    //else {
-                    //}
+                            addN(log,tx,bits);
+                    else
+                        addN(log,t,bits);
                 }
             }
         }
     }
 
-    private void addN( int log, Type t ) {
-        long x = t instanceof TypeInteger ti
-            ? ti.value()
-            : log==3
-            ? Double.doubleToRawLongBits(    ((TypeFloat)t).value())
-            : Float.floatToRawIntBits((float)((TypeFloat)t).value());
-        switch(log) {
-        case 0: add1((int)x); break;
-        case 1: add2((int)x); break;
-        case 2: add4((int)x); break;
-        case 3: add8(     x); break;
-        }
-    }
-
 
     // Patch local encodings now
-    private void patchLocalRelocations() {
+    void patchLocalRelocations() {
         // Walk the local code-address relocations
         for( Node src : _internals.keySet() ) {
-            Node dst = _internals.get(src);
+            Node dst =  _internals.get(src);
             int target = _opStart[dst._nid];
             int start  = _opStart[src._nid];
             ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start);
         }
-
-        for( Node src : _cpool.keySet() ) {
-            int target = _cpool.get(src);
-            int start = _opStart[src._nid];
-            ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start);
-        }
-    }
-
-
-    // Actual stack layout is up to each CPU.
-    // X86, with too many args & spills:
-    // | CALLER |
-    // |  argN  | // slot 1, required by callER
-    // +--------+
-    // |  RPC   | // slot 0, required by callER
-    // | callee | // slot 3, callEE
-    // | callee | // slot 2, callEE
-    // |  PAD16 |
-    // +--------+
-
-    // RISC/ARM, with too many args & spills:
-    // | CALLER |
-    // |  argN  | // slot 0, required by callER
-    // +--------+
-    // | callee | // slot 3, callEE: might be RPC
-    // | callee | // slot 2, callEE
-    // | callee | // slot 1, callEE
-    // |  PAD16 |
-    // +--------+
-    private void frameSize() {
-        for( Node n : _code._start.outs() ) {
-            if( n instanceof FunNode fun ) {
-                throw Utils.TODO();
-            }
-        }
     }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java
new file mode 100644
index 00000000..35d2008a
--- /dev/null
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java
@@ -0,0 +1,18 @@
+package com.seaofnodes.simple.codegen;
+
+// In-memory linking
+public class LinkMem {
+    final CodeGen _code;
+    LinkMem( CodeGen code ) { _code = code; }
+
+    public CodeGen link() {
+        // Write any large constants into a constant pool; they
+        // are accessed by RIP-relative addressing.
+        _code._encoding.writeConstantPool(_code._encoding._bits,true);
+
+        // Patch RIP-relative and local encodings now.
+        _code._encoding.patchLocalRelocations();
+
+        return _code;
+    }
+}