diff options
Diffstat (limited to 'chapter25/src/main/java/com/seaofnodes/simple')
8 files changed, 267 insertions, 93 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 86e83372..6fc66e4f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -733,6 +733,8 @@ public class CodeGen { // make a machine node for "this". private Node _instSelect( Node n, IdentityHashMap<Node,Node> map ) { if( n==null ) return null; + if( n instanceof StoreNode st && StaticData.preinitialized(this,st) ) + return _instSelect(st.mem(),map); Node x = map.get(n); if( x !=null ) return x; // Been there, done that diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index 2681066e..d1326cee 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -30,9 +30,6 @@ public class CompUnit { //BAOS _serial; // Serialized IR for this ELF file Ary<CompUnit> _deps; // CompUnits that this CompUnit depends on - //// List of symbols exported by this compilation unit, and their Node - //// definitions. - //public HashMap<String,Node> _exported; // Per-Compilation-Unit Start/StopNodes, keeping alive all exported Nodes. // Null means no code loaded (yet). public StartCUNode _start; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index 7423edbd..1b6281b8 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -133,16 +133,22 @@ public class ElfWriter { // The relocations; 3 words per relocation public class ReloSection extends DataSection { ReloSection( int info ) { - super(".rela.text", SHT_RELA, SHF_INFO_LINK, 24/*entsize*/); + this(".rela.text",info); + } + ReloSection(String name,int info) { + super(name, SHT_RELA, SHF_INFO_LINK, 24/*entsize*/); _link = 2; _info = info; } void writeReloOffPlus(int offset, int symidx, byte relo) { + writeRelo(offset,symidx,relo,-4); + } + void writeRelo(int offset,int symidx,byte relo,long addend) { assert symidx > 0; write8(offset); write8(((long)symidx << 32L) | relo); - write8(-4); + write8(addend); } } @@ -287,7 +293,7 @@ public class ElfWriter { _strtab = new StringSection(); // place all the symbols - int nlocals = 1/*null*/+7/*number of sections*/+1/*Simple section*/; + int nlocals = 1/*null*/+9/*number of sections*/+1/*Simple section*/; SymbolSection symbols = new SymbolSection(nlocals); // we've already constructed these entire sections in the encoding phase @@ -324,12 +330,35 @@ public class ElfWriter { relocations.writeReloOffPlus(offset, symidx, (byte)2/*PC32*/); } - // Write relocations for the constant pool - String cpoolPrefix = _code.entryClinitName().replaceAll("[^A-Za-z0-9_$]", "_") + "$CPOOL$"; + // Stable function identities are also addressable from data, including + // anonymous functions which have no source-level exported name. + HashMap<String,Integer> dataSymbols=new HashMap<>(); + for( FunNode fun : _code._linker ) + if( fun!=null && !fun.isDead() && _code.owns(fun) && enc.opStart(fun)>=0 ) { + String name=_code._fidxs.symbol(fun.sig().fidx()); + dataSymbols.put(name,symbols.symbol(name,text._index,SYM_BIND_GLOBAL,SYM_TYPE_FUNC,enc.opStart(fun),0)); + } + for( StaticData.ObjectData obj : enc._data.objects.values() ) { + int section=obj.external ? 0 : obj.readOnly ? rodata._index : rwdata._index; + dataSymbols.put(obj.symbol,symbols.symbol(obj.symbol,section,SYM_BIND_GLOBAL,SYM_TYPE_OBJECT, + obj.external ? 0 : obj.offset,obj.external ? 0 : obj.size)); + } for( Encoding.Relo relo : enc._bigCons.values() ) { - DataSection data = relo.readOnly() ? rodata : rwdata; - int symidx = symbols.symbol(cpoolPrefix+symbols.gidx(), data._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC, relo._target, relo._t.size()); - relocations.writeReloOffPlus(relo._opStart+relo._off, symidx, relo._elf ); + StaticData.ObjectData obj=enc._data.object(relo._t); + relocations.writeReloOffPlus(relo._opStart+relo._off,dataSymbols.get(obj.symbol),relo._elf); + } + ReloSection roRelos=new ReloSection(".rela.rodata",rodata._index); + ReloSection rwRelos=new ReloSection(".rela.data",rwdata._index); + for( StaticData.Relocation relo : enc._data.relocations ) { + String name=enc._data.targetSymbol(relo.value()); + Integer sym=dataSymbols.get(name); + if( sym==null ) { + sym=symbols.symbol(name,0,SYM_BIND_GLOBAL,SYM_TYPE_NOTYPE); + dataSymbols.put(name,sym); + } + // AMD64 absolute 32/64-bit addresses; linker rejects overflow. + byte kind=(byte)(relo.logSize()==2 ? 10 : 1); + (relo.object().readOnly ? roRelos : rwRelos).writeRelo(relo.object().offset+relo.offset(),sym,kind,0); } // Create a "Simple" section for Simple types and ir diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 7cb92884..8e9b99db 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -41,6 +41,8 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { public final BAOS _cpool = new BAOS(); // Constant r/o pool public final BAOS _sdata = new BAOS(); // Static r/w pool public final HashMap<Node,Relo> _bigCons = new HashMap<>(); + public final StaticData _data; + public final HashMap<String,Integer> _externalAddresses = new HashMap<>(); // Big Constant relocation info. public static class Relo { @@ -70,6 +72,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { Encoding( CodeGen code ) { _code = code; + _data = new StaticData(this); } // Shortcut to the defining register @@ -217,10 +220,8 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // encodings and compact the code, changing all the offsets. compactShortForm(); - // Write the constant pool - writeConstantPool(_cpool,true ); - // Write the static memory - writeConstantPool(_sdata,false); + // Place pool objects and record relocations within their contents. + _data.write(); // Patch RIP-relative and local encodings now. patchLocalRelocations(); @@ -517,52 +518,6 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { } } - // -------------------------------------------------- - // Write the constant pool into the BAOS and optionally patch locally - void writeConstantPool( BAOS bits, boolean ro ) { - padN(16,bits); - - // radix sort the big constants by alignment - Ary<Relo>[] raligns = new Ary[5]; - for( Node op : _bigCons.keySet() ) { - Relo relo = _bigCons.get(op); - if( relo.readOnly() != ro ) - continue; - int align = relo._t.alignment(); - Ary<Relo> relos = raligns[align]==null ? (raligns[align]=new Ary<>(Relo.class)) : raligns[align]; - relos.add(relo); - } - - - // Types can be used more than once; collapse the dups - HashMap<Type,Integer> targets = new HashMap<>(); - - // By alignment - for( int align = raligns.length-1; align >= 0; align-- ) { - Ary<Relo> relos = raligns[align]; - if( relos == null ) continue; - for( Relo relo : relos ) { - // Map from relo to constant start and patch - Integer target = targets.get(relo._t); - if( target==null ) { - targets.put(relo._t,target = bits.size()); - // Write constant into constant pool - switch( relo._t ) { - case TypeTuple tt -> throw Utils.TODO("no tuples here, use structs instead"); - case TypeStruct ts -> addStruct(bits,ts); - // Simple primitive (e.g. larger int, float, function ptr) - default -> addN(align,relo._t,bits); - } - } - // Record target address and opcode start. - // Target is relative to the cpool/sdata start. - relo._target = target; - relo._opStart= opStart(relo._op); - } - } - - } - // Emit a single scalar as bits static void addN( int log, Type t, BAOS bits ) { long x = switch( t ) { @@ -577,36 +532,22 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { addN(log,x,bits); } - // Structs use internal field layout - private void addStruct( BAOS bits, TypeStruct ts ) { - // Field order by offset - int[] layout = ts.layout(); - int off=0; // offset in the struct - for( int fn=0; fn<ts._fields.length; fn++ ) { - Field f = ts._fields[layout[fn]]; - if( f._extern ) continue; - int foff = ts. offset(layout[fn]); - // Pad up to field - while( off < foff ) { bits.write(0); off++; }; - // Constant array fields are special - if( f._fname=="[]" ) { // Must be a constant array - ((TypeConAry)f._t).write(bits); - off += ((TypeConAry)f._t).len(); - } else { - int log = f._t.log_size(); - addN(log,f._t.isConstant() ? f._t : f._t.makeZero(),bits); - off += 1<<log; - } - } - } - - // A series of libc/external calls that Simple can link against in a JIT. // Since no runtime in the JVM process, using magic numbers for the CPU // emulators to pick up on. public static int SENTINEL_CALLOC = -4; public static int SENTINEL_WRITE = -8; + int externalAddress(String name) { + Integer address=_externalAddresses.get(name); + if( address!=null ) return address; + return switch(name) { + case "calloc" -> SENTINEL_CALLOC; + case "write" -> SENTINEL_WRITE; + default -> throw new IllegalArgumentException("Unresolved external function '"+name+"'"); + }; + } + void patchGlobalRelocations() { for( Node src : _externData.keySet() ) { String name = _externData.get(src); @@ -618,11 +559,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { for( Node src : _externals.keySet() ) { int start = opStart(src); String dst = _externals.get(src); - int target = switch( dst ) { - case "calloc" -> SENTINEL_CALLOC; - case "write" -> SENTINEL_WRITE ; - default -> throw Utils.TODO(); - }; + int target = externalAddress(dst); ((RIPRelSize)src).patch(this, start, opLen(src), target - start); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java index b0060024..bc9c9d39 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java @@ -129,6 +129,12 @@ public class GlobalBits { return next(clz,order); } + // Stable native symbol identity, independent of this compilation's dense IDs. + String owner(int local) { return _local2Clz.at(local); } + String symbol(int local) { + return _local2Clz.at(local)+"$F$"+_local2Order.at(local); + } + // Write out to BAOS enough bits to unwind the local back to global index void packed( BAOS baos, HashMap<String,Integer> strs ) { // Unwind a local index to the clz. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java index d249b80c..252b5bf0 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java @@ -23,10 +23,11 @@ public class LinkMem { // Patch local ops, e.g. loading float constants from the constant pool for( Node op : enc._bigCons.keySet() ) { Encoding.Relo relo = enc._bigCons.get(op); - int target = relo._target+(relo.readOnly() ? cpool : sdata); + int target = enc._data.address(enc._data.object(relo._t),cpool,sdata); ((RIPRelSize)relo._op).patch(enc, relo._opStart, enc.opLen(relo._op), target - relo._opStart); } + enc._data.link(cpool,sdata); return _code; } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/StaticData.java new file mode 100644 index 00000000..f9f16008 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/StaticData.java @@ -0,0 +1,195 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; +import java.util.*; + +// Pool objects have identity independently of their initial field values. +// References in their contents use the same symbols in ELF and emulator images. +public final class StaticData { + public static final class ObjectData { + public final Type type; + public final String symbol; + public final boolean readOnly, external; + public final int alignment, size; + public int offset; + ObjectData(Type t, String name, boolean ro, boolean ext) { + type=t; symbol=name; readOnly=ro; external=ext; + alignment=t.alignment(); + int align=1<<alignment; + size=t instanceof TypeStruct ts ? (Math.max(1,ts.size())+align-1)&-align : align; + } + } + public record Relocation(ObjectData object, int offset, int logSize, Type value) {} + + final Encoding enc; + final LinkedHashMap<Object,ObjectData> objects = new LinkedHashMap<>(); + final ArrayList<Relocation> relocations = new ArrayList<>(); + final String prefix; + + public ArrayList<ObjectData> entries() { + ArrayList<ObjectData> entries=new ArrayList<>(objects.values()); + entries.sort(Comparator.comparingInt((ObjectData obj) -> obj.alignment).reversed()); + return entries; + } + + StaticData(Encoding enc) { + this.enc=enc; + prefix=enc._code.entryClinitName()+"$DATA$"; + } + + static boolean isClass(Type t) { + return t instanceof TypeStruct ts && Parser.startsClzPrefix(ts._name); + } + + static CompUnit owner(CodeGen code,TypeStruct ts) { + return owner(code,ts._name.substring(Parser.CLZ.length())); + } + static CompUnit owner(CodeGen code,String name) { + if(name==null) return null; + CompUnit owner=null; + for( CompUnit cu : code._compunits.values() ) + if( cu._cname!=null && (name.equals(cu._cname) || name.startsWith(cu._cname+".")) && + (owner==null || cu._cname.length()>owner._cname.length()) ) owner=cu; + return owner; + } + + // A final field whose declaration already denotes this exact constant is + // available as that value to every ideal Load. Materialize it in the object + // image instead of emitting the redundant initializer Store. This lowering + // leaves serialized ideal IR intact, so imports retain their memory edges. + static boolean preinitialized(CodeGen code,StoreNode st) { + if( !(st.ptr()._type instanceof TypeMemPtr ptr) || !ptr._one || !isClass(ptr._obj) ) return false; + CompUnit owner=owner(code,ptr._obj); + if( owner==null || owner._src==null ) return false; + if( !(Parser.TYPES.get(ptr._obj._name) instanceof TypeStruct ts) ) return false; + Field fld=ts.field(st._name); + if( fld==null || !fld._final || !fld._t.isConstant() || !st.val()._type.isConstant() ) return false; + Type value=st.val()._type, declared=fld._t; + if( declared instanceof TypeFunPtr fp && value instanceof TypeFunPtr vp ) return fp.fidx()==vp.fidx(); + if( declared instanceof TypeMemPtr ptr0 && value instanceof TypeMemPtr ptr1 ) + return pointerConstant(ptr0) && ptr0._obj==ptr1._obj; + return declared==value; + } + + ObjectData object(Type t) { + Object key=isClass(t) ? ((TypeStruct)t)._name + : t instanceof TypeFunPtr fp ? functionSymbol(fp) : t; + ObjectData old=objects.get(key); + if( old!=null ) return old; + boolean clz=isClass(t); + if( clz && Parser.TYPES.get(((TypeStruct)t)._name) instanceof TypeStruct canonical ) t=canonical; + CompUnit owner=clz ? owner(enc._code,(TypeStruct)t) + : t instanceof TypeFunPtr fp ? owner(enc._code,enc._code._fidxs.owner(fp.fidx())) : null; + String symbol=clz ? ((TypeStruct)t)._name.substring(Parser.CLZ.length())+".$class" + : t instanceof TypeFunPtr fp ? functionSymbol(fp) : prefix+objects.size(); + ObjectData obj=new ObjectData(t,symbol,!clz && (!(t instanceof TypeStruct ts) || ts.isConstant()), + owner!=null && owner._src==null); + objects.put(key,obj); + // Register before following fields: class objects may refer to each other. + if( !obj.external && t instanceof TypeStruct ts ) + for( Field f : ts._fields ) + if( !f._extern && f._t.isConstant() ) target(f._t); + return obj; + } + + private static boolean pointerConstant(TypeMemPtr ptr) { + return ptr.notNull() && (isClass(ptr._obj) || (ptr._obj.isConstant() && (!ptr._obj.isAry() || ptr._obj.isConAry()))); + } + + private void target(Type t) { + if( t instanceof TypeMemPtr ptr && pointerConstant(ptr) ) object(ptr._obj); + if( t instanceof TypeFunPtr fp && fp.notNull() && + enc._code.link(fp)==null && !enc._code._externFunc.containsKey(fp.fidx()) ) + // A dead function still needs a unique non-null identity for comparisons. + object(fp); + } + + void write() { + ArrayList<Encoding.Relo> refs=new ArrayList<>(enc._bigCons.values()); + refs.sort(Comparator.comparingInt(r -> r._op._nid)); + for( Encoding.Relo ref : refs ) object(ref._t); + // Definitions belong to their compilation unit, even if every local use folded. + ArrayList<CompUnit> units=new ArrayList<>(enc._code._compunits.values()); + units.sort(Comparator.comparing(cu -> cu._cname==null ? "" : cu._cname)); + for( CompUnit cu : units ) if( cu._src!=null && cu._clz!=null ) object(cu._clz); + for( ObjectData obj : entries() ) { + if( obj.external ) continue; + BAOS bits=obj.readOnly ? enc._cpool : enc._sdata; + Encoding.padN(1<<obj.alignment,bits); + obj.offset=bits.size(); + if( obj.type instanceof TypeStruct ts ) writeStruct(obj,ts,bits); + else Encoding.addN(obj.alignment,obj.type,bits); + while( bits.size()<obj.offset+obj.size ) bits.write(0); + } + for( Encoding.Relo ref : refs ) { + ObjectData obj=object(ref._t); + ref._target=obj.offset; + ref._opStart=enc.opStart(ref._op); + } + } + + private void writeStruct(ObjectData obj, TypeStruct ts, BAOS bits) { + int[] layout=ts.layout(); + for( int idx : layout ) { + if( idx==ts._fields.length ) continue; + Field f=ts._fields[idx]; + if( f._extern ) continue; + int off=ts.offset(idx); + while( bits.size()<obj.offset+off ) bits.write(0); + if( f._fname.equals("[]") ) ((TypeConAry)f._t).write(bits); + else { + Type value=f._t.isConstant() ? f._t : f._t.makeZero(); + int log=f._t.log_size(); + Encoding.addN(log,value,bits); + if( (value instanceof TypeFunPtr fp && fp.notNull()) || + (value instanceof TypeMemPtr ptr && pointerConstant(ptr)) ) + relocations.add(new Relocation(obj,off,log,value)); + } + } + while( bits.size()<obj.offset+ts.size() ) bits.write(0); + } + + String functionSymbol(TypeFunPtr fp) { + String ext=enc._code._externFunc.get(fp.fidx()); + return ext!=null ? ext : enc._code._fidxs.symbol(fp.fidx()); + } + + String targetSymbol(Type value) { + if( value instanceof TypeMemPtr ptr ) return object(ptr._obj).symbol; + TypeFunPtr fp=(TypeFunPtr)value; + return enc._code.link(fp)==null && !enc._code._externFunc.containsKey(fp.fidx()) + ? object(fp).symbol : functionSymbol(fp); + } + + void link(int cpool, int sdata) { + for( Relocation rel : relocations ) { + long address; + if( rel.value instanceof TypeMemPtr ptr ) address=address(object(ptr._obj),cpool,sdata); + else { + TypeFunPtr fp=(TypeFunPtr)rel.value; + String ext=enc._code._externFunc.get(fp.fidx()); + FunNode fun=enc._code.link(fp); + if( ext!=null ) address=enc.externalAddress(ext); + else if( fun==null ) address=address(object(fp),cpool,sdata); + else { + if( !enc._code.owns(fun) ) throw new IllegalArgumentException("Unlinked function "+functionSymbol(fp)); + address=enc.opStart(fun); + } + } + // Emulator native-call sentinels are signed 32-bit addresses. + if( rel.logSize==2 && (address<Integer.MIN_VALUE || address>0xffff_ffffL) ) + throw new IllegalArgumentException("Function address outside 32 bits: "+address); + BAOS bits=rel.object.readOnly ? enc._cpool : enc._sdata; + int off=rel.object.offset+rel.offset; + for( int i=0; i<(1<<rel.logSize); i++ ) bits.buf()[off+i]=(byte)(address>>>(8*i)); + } + } + + int address(ObjectData obj,int cpool,int sdata) { + if( obj.external ) throw new IllegalArgumentException("Unlinked class object "+obj.symbol); + return obj.offset+(obj.readOnly ? cpool : sdata); + } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 994065d8..e8218afd 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -79,12 +79,19 @@ public final class ASMPrinter extends AssemblyAdapter<Node> { if( !encoded() ) return pools; int base=(codeEnd+15)&-16; if( _enc._cpool.size()>0 ) - pools.add(new Pool("Constant Pool",_enc._cpool.buf(),0,base,entries(_enc._bigCons.values(),true))); + pools.add(new Pool("Constant Pool",_enc._cpool.buf(),0,base,objects(true))); base=(base+_enc._cpool.size()+15)&-16; if( _enc._sdata.size()>0 ) - pools.add(new Pool("Static Data",_enc._sdata.buf(),0,base,entries(_enc._bigCons.values(),false))); + pools.add(new Pool("Static Data",_enc._sdata.buf(),0,base,objects(false))); return pools; } + private ArrayList<Data> objects(boolean ro) { + var data=new ArrayList<Data>(); + for( var obj : _enc._data.entries() ) + if( !obj.external && obj.readOnly==ro ) + data.add(new Data(obj,obj.symbol+": "+obj.type.str(),obj.alignment,obj.size)); + return data; + } // Retain this diagnostic entry point for checking that pool printing never lays out types. static int printConstantPool(int address, SB sb, BAOS bits, HashMap<Node,Encoding.Relo> relos, boolean ro, String name) { |