ELF exporting (but in Chapter 21) (#173)

* Updated ELF exporting code, added function relocations

* added big constants (only floats currently)

4 files changed, 418 insertions, 2 deletions

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 1e778aa7..a2c836a8 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -25,6 +25,7 @@ public class CodeGen {
         LocalSched,             // Local schedule
         RegAlloc,               // Register allocation
         Encoding,               // Encoding
+        Export,                 // Export
     }
     public Phase _phase;
 
@@ -296,6 +297,14 @@ public class CodeGen {
         return this;
     }
 
+    public CodeGen exportELF() {
+        assert _phase == Phase.Encoding;
+        _phase = Phase.Export;
+        ElfFile obj = new ElfFile(this);
+        obj.export();
+        return this;
+    }
+
     public static void print_as_hex(Encoding enc) {
         for (byte b : enc._bits.toByteArray()) {
             System.out.print(String.format("%02X", b));
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
new file mode 100644
index 00000000..b263ea6b
--- /dev/null
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
@@ -0,0 +1,386 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+
+import java.util.Map;
+import java.util.HashMap;
+import java.nio.ByteBuffer;
+import java.nio.ByteOrder;
+import java.io.IOException;
+import java.io.FileOutputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.BufferedOutputStream;
+
+public class ElfFile {
+
+    final CodeGen _code;
+    Ary<Section> _sections = new Ary<>(Section.class);
+
+    ElfFile( CodeGen code ) { _code = code; }
+
+    public static int writeCString(DataSection strtab, String name) {
+        // place name in the string table
+        int pos = strtab._contents.size();
+        byte[] name_bytes = name.getBytes();
+        strtab._contents.write(name_bytes, 0, name_bytes.length);
+        // the strings are null terminated
+        strtab._contents.write(0);
+        return pos;
+    }
+
+    public static void write4( ByteArrayOutputStream bits, int op ) {
+        bits.write(op    );
+        bits.write(op>> 8);
+        bits.write(op>>16);
+        bits.write(op>>24);
+    }
+    public static void write8( ByteArrayOutputStream bits, long i64 ) {
+        write4(bits, (int) i64     );
+        write4(bits, (int)(i64>>32));
+    }
+
+    public static final int SYMBOL_SIZE = 4+1+1+2+8+8;
+
+    public static final int SYM_BIND_LOCAL   = 0;
+    public static final int SYM_BIND_GLOBAL  = 1;
+    public static final int SYM_BIND_WEAK    = 2;
+
+    public static final int SYM_TYPE_NOTYPE  = 0;
+    public static final int SYM_TYPE_OBJECT  = 1;
+    public static final int SYM_TYPE_FUNC    = 2;
+    public static final int SYM_TYPE_SECTION = 3;
+
+    public static class Symbol {
+        String _name;
+        int _name_pos;
+
+        // index in the symbol table
+        int _index;
+
+        // which section is it in
+        int _parent;
+
+        // depends on the symbol type
+        //   TODO
+        int _value, _size;
+
+        // top 4bits are the "bind", bottom 4 are "type"
+        int _info;
+
+        Symbol(String name, int parent, int bind, int type) {
+            _name = name;
+            _parent = parent;
+            _info = (bind << 4) | (type & 0xF);
+        }
+
+        void writeHeader(ByteBuffer out) {
+            out.putInt(_name_pos);         // name
+            out.put((byte) _info);         // info
+            out.put((byte) 0);             // other
+            out.putShort((short) _parent); // shndx
+            out.putLong(_value);           // value
+            out.putLong(_size);            // size
+        }
+    }
+
+    public static final int SHF_WRITE     = 1;
+    public static final int SHF_ALLOC     = 2;
+    public static final int SHF_EXECINSTR = 4;
+    public static final int SHF_STRINGS   = 32;
+    public static final int SHF_INFO_LINK = 64;
+
+    public static final int SECTION_HDR_SIZE = 64;
+    abstract public static class Section {
+        String _name;
+        int _index;
+
+        int _type, _flags;
+        int _link, _info;
+
+        // where's the name in the string table
+        int _name_pos;
+        int _file_offset;
+
+        Section(String name, int type) {
+            _name = name;
+            _type = type;
+        }
+
+        void writeHeader(ByteBuffer out) {
+            out.putInt(_name_pos);     // name
+            out.putInt(_type);         // type
+            out.putLong(_flags);       // flags
+            out.putLong(0);            // addr
+            out.putLong(_file_offset); // offset
+            out.putLong(size());       // size
+            out.putInt(_link);         // link
+            out.putInt(_info);         // info
+            out.putLong(1);            // addralign
+            if (_type == 2) {
+                out.putLong(SYMBOL_SIZE);// entsize
+            } else if (_type == 4) {
+                out.putLong(24);         // entsize
+            } else {
+                out.putLong(0);          // entsize
+            }
+        }
+
+        abstract void write(ByteBuffer out);
+        abstract int size();
+    }
+
+    public static class SymbolSection extends Section {
+        Ary<Symbol> _symbols = new Ary<>(Symbol.class);
+        int _nonlocal_symbols;
+
+        SymbolSection(String name, int type) {
+            super(name, type);
+        }
+
+        @Override
+            void writeHeader(ByteBuffer out) {
+            // points to string table section
+            _link = 1;
+
+            // number of non-local symbols
+            _info = _nonlocal_symbols;
+
+            super.writeHeader(out);
+        }
+
+        void push(Symbol s) {
+            if ((s._info >> 4) != SYM_BIND_LOCAL) {
+                _nonlocal_symbols += 1;
+            }
+
+            _symbols.push(s);
+            // symbols are effectively "1-based" (NULL symbol)
+            s._index = _symbols.len();
+        }
+
+        @Override
+            void write(ByteBuffer out) {
+            for( int i = 0; i < SYMBOL_SIZE/4; i++ ) {
+                out.putInt(0);
+            }
+
+            for( Symbol s : _symbols ) {
+                s.writeHeader(out);
+            }
+        }
+
+        @Override
+            int size() {
+            return (1 + _symbols.len()) * SYMBOL_SIZE;
+        }
+    }
+
+    public static class DataSection extends Section {
+        ByteArrayOutputStream _contents;
+
+        DataSection(String name, int type) {
+            super(name, type);
+            _contents = new ByteArrayOutputStream();
+        }
+
+        DataSection(String name, int type, ByteArrayOutputStream contents) {
+            super(name, type);
+            _contents = contents;
+        }
+
+        @Override
+            void write(ByteBuffer out) {
+            out.put(_contents.toByteArray());
+        }
+
+        @Override
+            int size() {
+            return _contents.size();
+        }
+    }
+
+    private void pushSection(Section s) {
+        _sections.push(s);
+        // ELF is effectively "1-based", due to the NULL section
+        s._index = _sections._len;
+    }
+
+    private final HashMap<TypeFunPtr,Symbol> _funcs = new HashMap<>();
+    private void encodeFunctions(SymbolSection symbols, DataSection text) {
+        int func_start = 0;
+        for( int i=0; i<_code._cfg._len; i++ ) {
+            Node bb = _code._cfg.at(i);
+            if( bb instanceof FunNode f ) {
+                // skip until the function ends
+                while( !(_code._cfg.at(i) instanceof ReturnNode) ) {
+                    i++;
+                }
+
+                Node r = _code._cfg.at(i);
+                int end = _code._encoding._opStart[r._nid] + _code._encoding._opLen[r._nid];
+
+                Symbol func = new Symbol(f._name, text._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC);
+                func._size = end - func_start;
+                func._value = func_start;
+                symbols.push(func);
+                _funcs.put(f.sig(), func);
+
+                // next function starts where the last one ends
+                func_start = end;
+            }
+        }
+    }
+
+    public final HashMap<Type,Symbol> _bigCons = new HashMap<>();
+    private void encodeConstants(SymbolSection symbols, DataSection rdata) {
+        int cnt = 0;
+        for (Map.Entry<Node,Type> e : _code._encoding._bigCons.entrySet()) {
+            if (_bigCons.get(e.getValue()) != null) {
+                continue;
+            }
+
+            Symbol glob = new Symbol("GLOB$"+cnt, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC);
+            glob._value = rdata._contents.size();
+            symbols.push(glob);
+
+            Type t = e.getValue();
+            if ( t instanceof TypeFloat tf ) {
+                write8(rdata._contents, Double.doubleToLongBits(tf._con));
+            } else {
+                throw Utils.TODO();
+            }
+
+            glob._size = rdata._contents.size() - glob._value;
+            _bigCons.put(e.getValue(), glob);
+            cnt++;
+        }
+    }
+
+    public void export() {
+        DataSection strtab = new DataSection(".strtab", 3 /* SHT_SYMTAB */);
+        // first byte is reserved for an empty string
+        strtab._contents.write(0);
+        pushSection(strtab);
+
+        // place all the symbols
+        SymbolSection symbols = new SymbolSection(".symtab", 2 /* SHT_STRTAB */);
+        pushSection(symbols);
+
+        // we've already constructed this entire section in the encoding phase
+        DataSection text = new DataSection(".text", 1 /* SHT_PROGBITS */, _code._encoding._bits);
+        text._flags = SHF_ALLOC | SHF_WRITE | SHF_EXECINSTR;
+        pushSection(text);
+
+        DataSection rdata = new DataSection(".rodata", 1 /* SHT_PROGBITS */);
+        rdata._flags = SHF_ALLOC;
+        pushSection(rdata);
+
+        // populate function symbols
+        encodeFunctions(symbols, text);
+        // populate big constants
+        encodeConstants(symbols, rdata);
+
+        // create .text relocations
+        DataSection text_rela = new DataSection(".rela.text", 4 /* SHT_RELA */);
+        for (Map.Entry<Node,TypeFunPtr> e : _code._encoding._funcRelos.entrySet()) {
+            int nid    = e.getKey()._nid;
+            int sym_id = _funcs.get(e.getValue())._index;
+            int offset = _code._encoding._opStart[nid] + _code._encoding._opLen[nid] - 4;
+
+            // u64 offset
+            write8(text_rela._contents, offset);
+            // u64 info
+            write8(text_rela._contents, ((long)sym_id << 32L) | 4L /* PLT32 */);
+            // i64 addend
+            write8(text_rela._contents, -4);
+        }
+        // relocations to constants
+        for (Map.Entry<Node,Type> e : _code._encoding._bigCons.entrySet()) {
+            int nid    = e.getKey()._nid;
+            int sym_id = _bigCons.get(e.getValue())._index;
+            int offset = _code._encoding._opStart[nid] + _code._encoding._opLen[nid] - 4;
+
+            // u64 offset
+            write8(text_rela._contents, offset);
+            // u64 info
+            write8(text_rela._contents, ((long)sym_id << 32L) | 1L /* PC32 */);
+            // i64 addend
+            write8(text_rela._contents, -4);
+        }
+        text_rela._flags = SHF_INFO_LINK;
+        text_rela._link = 2;
+        text_rela._info = text._index;
+        pushSection(text_rela);
+
+        // populate string table
+        for( Section s : _sections ) { s._name_pos = writeCString(strtab, s._name); }
+        for( Symbol s : symbols._symbols ) { s._name_pos = writeCString(strtab, s._name); }
+
+        int idx = 1;
+        for( Section s : _sections ) {
+            Symbol sym = new Symbol(s._name, idx++, SYM_BIND_LOCAL, SYM_TYPE_SECTION);
+            // we can reuse the same name pos from the actual section
+            sym._name_pos = s._name_pos;
+            sym._size = s.size();
+            symbols.push(sym);
+        }
+
+        int size = 64; // ELF header
+        // size of all section data
+        for( Section s : _sections ) {
+            s._file_offset = size;
+            size += s.size();
+        }
+        // headers go at the very end
+        int shdr_offset = size;
+        // there's a "null" section at the start of the section headers
+        size += SECTION_HDR_SIZE*(1 + _sections.len());
+
+        // System.out.printf("Hello %d, %d, %s\n", size, shdr_offset);
+        ByteBuffer out = ByteBuffer.allocate(size);
+        out.order(ByteOrder.LITTLE_ENDIAN);
+
+        // ELF header
+        out.put(new byte[]{ 0x7F, 'E', 'L', 'F', 2, 1, 1, 0 });
+        out.put(new byte[8]);
+        out.putShort((short)1 /* ET_REL */); // type
+        out.putShort((short)62 /* AMD64 */); // machine
+        out.putInt(1);                // version
+        out.putLong(0);               // entry
+        out.putLong(0);               // phoff
+        out.putLong(shdr_offset);     // shoff
+        out.putInt(0);                // flags
+        out.putShort((short)64);      // ehsize
+        out.putShort((short)0);       // phentsize
+        out.putShort((short)0);       // phnum
+        out.putShort((short)64);      // shentsize
+        out.putShort((short) (1 + _sections.len())); // shnum
+        out.putShort((short)1);       // shstrndx
+
+        // raw section data
+        for( Section s : _sections ) {
+            s.write(out);
+        }
+
+        // "null" section
+        for( int i = 0; i < 16; i++ ) {
+            out.putInt(0);
+        }
+
+        for( Section s : _sections ) {
+            s.writeHeader(out);
+        }
+        assert out.position() == size;
+
+        try {
+            BufferedOutputStream bos = new BufferedOutputStream(new FileOutputStream("a.o"));
+            bos.write(out.array());
+            bos.close();
+        } catch (IOException e) {
+            e.printStackTrace();
+        }
+    }
+
+}
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 5d7266aa..6ddaa1f4 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -52,6 +52,7 @@ public class Encoding {
         _bits = new BAOS();
         _bigCons = new HashMap<>();
         _jmps = new HashMap<>();
+        _funcRelos = new HashMap<>();
     }
 
     // Shortcut to the defining register
@@ -94,8 +95,9 @@ public class Encoding {
     // call back with `ReloNode.patch(byte[],src_offset,TFP,dst_offset)`
     // X86 gets a special pass for expanding short jumps.
 
+    public final HashMap<Node,TypeFunPtr> _funcRelos;
     public void relo( Node relo, TypeFunPtr t ) {
-        // TODO: record call relocation info
+        _funcRelos.put(relo, t);
     }
     public void relo( NewNode nnn ) {
         // TODO: record alloc relocation info
@@ -103,7 +105,7 @@ public class Encoding {
     // Store t as a 32/64 bit constant in the code space; generate RIP-relative
     // addressing to load it
 
-    private final HashMap<Node,Type> _bigCons;
+    public final HashMap<Node,Type> _bigCons;
     public void largeConstant( Node relo, Type t ) {
         assert t.isConstant();
         _bigCons.put(relo,t);
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 648edbe1..ad1f39b2 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -80,4 +80,23 @@ return sqrt(farg) + sqrt(farg+2.0);
         testCPU(src,"riscv"    , "SystemV",1,"return (add,.[],(mul,.[],1000));");
         testCPU(src,"arm"      , "SystemV",1,"return (add,.[],(mul,.[],1000));");
     }
+
+    @Test
+    public void testExport() {
+        CodeGen code = new CodeGen(
+            """
+// Newtons approximation to the square root
+val sqrt = { flt x ->
+    flt guess = x;
+    while( 1 ) {
+        flt next = (x/guess + guess)/2;
+        if( next == guess ) return guess;
+        guess = next;
+    }
+};
+flt farg = arg;
+return sqrt(farg) + sqrt(farg+2.0);
+            """);
+        code.parse().opto().typeCheck().instSelect(PORTS, "x86_64_v2", "SystemV").GCM().localSched().regAlloc().encode().exportELF();
+    }
 }