diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/codegen')
23 files changed, 3722 insertions, 1002 deletions
diff --git a/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index 2319714b..0b314978 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -15,11 +15,16 @@ abstract public class BuildLRG { // since it will not color, just split the conflicted ranges now). Returns // true if no hard-conflicts, although we still might not color. public static boolean run(int round, RegAlloc alloc) { - for( Node bb : alloc._code._cfg ) + FunNode fun = null; + for( Node bb : alloc._code._cfg ) { + if( bb instanceof FunNode fun2 ) + fun = fun2; for( Node n : bb.outs() ) { // A synthetic never-exit value has no runtime definition. if( n._type==Type.TOP ) continue; if( n instanceof PhiNode phi && !(phi._type instanceof TypeMem) ) { + if( phi instanceof MachNode mach && mach.outregmap()==null ) + continue; // All real Phi inputs end up with the same LRG. // Pass 1: find any pre-existing LRG, to avoid make-then-Union a LRG LRG lrg = alloc.lrg(phi); @@ -28,8 +33,8 @@ abstract public class BuildLRG { if( (lrg = alloc.lrg(phi.in(i))) != null ) break; // If none, make one. - if( lrg==null ) lrg = alloc.newLRG(n); - if( phi instanceof MachNode ) defLRG(alloc,n); + if( lrg==null ) lrg = alloc.newLRG(n,fun); + if( phi instanceof MachNode ) defLRG(alloc,n,fun); // Pass 2: everybody uses the same LRG lrg=alloc.union(lrg,phi); for( int i=phi instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) @@ -51,7 +56,7 @@ abstract public class BuildLRG { } // Define live range - defLRG(alloc,n); + defLRG(alloc,n,fun); // Now, look in the opposite direction. How are incoming // LRGs affected by this node: For all uses, make live lrgs @@ -71,8 +76,9 @@ abstract public class BuildLRG { if( n instanceof MultiNode && !(n instanceof CFGNode) ) for( Node proj : n.outs() ) if( proj instanceof MachNode ) - defLRG(alloc,proj); + defLRG(alloc,proj,fun); } + } // Collect live ranges alloc.unify(); @@ -80,12 +86,12 @@ abstract public class BuildLRG { return alloc.success(); } - private static void defLRG( RegAlloc alloc, Node n ) { + private static void defLRG( RegAlloc alloc, Node n, FunNode fun ) { MachNode mach = (MachNode)n; RegMask def_mask = mach.outregmap(); if( def_mask == null ) return; LRG lrg = mach.twoAddress() == 0 - ? alloc.newLRG(n) // Define a new LRG for N + ? alloc.newLRG(n,fun) // Define a new LRG for N : alloc.lrg2(n,mach.twoAddress()); // Use the matching 2-adr input // Record mask and mach if( !lrg.machDef(mach,def_mask.size1()).and(def_mask) ) diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index f3d3dee3..6fc66e4f 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -1,85 +1,293 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.graph.GraphObserver; - import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.Ary; -import com.seaofnodes.simple.util.SB; -import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.*; +import java.io.File; import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; import java.util.*; + +// Compile Driver for a Compilation Unit @SuppressWarnings("unchecked") public class CodeGen { - public GraphObserver<Node> _obs; - public static final String PORTS = "com.seaofnodes.simple.node.cpus"; - // Last created CodeGen as a global; used all over to avoid passing about a - // "context". + + // Last created CodeGen as a global; used all over to avoid passing about a "context". public static CodeGen CODE; + // Location of built-in CPU ports + public static final String PORTS = "com.seaofnodes.simple.node.cpus"; + + // Compile phases public enum Phase { Parse, // Parse ASCII text into Sea-of-Nodes IR + Iter, // Pessimistic peepholes after parse Opto, // Run ideal optimizations TypeCheck, // Last check for bad programs LoopTree, // Build a loop tree; break infinite loops + Serialize, // Serialize public IR for future compiles to link + Unlink, // Unlink call sites before machine code generation Select, // Convert to target hardware nodes Schedule, // Global schedule (code motion) nodes LocalSched, // Local schedule RegAlloc, // Register allocation Encoding, // Encoding Export, // Export + LastPhase // After last phase } public Phase _phase; + // Null for normal compilation; owned by this compilation, not a global viewer. + public GraphObserver<Node> _obs; + + /** True when tests deliberately randomize Iter worklist order. */ + public static boolean iterSeedOverridden() { return System.getProperty("simple.iter.seed") != null; } + + // Expensive assert sampling: + // -Dsimple.assert.expensive=0 disables these checks + // -Dsimple.assert.expensive=1 checks every step + // -Dsimple.assert.expensive=N checks once every 1<<N steps + private static final int EXPENSIVE_ASSERT_LOG = Integer.getInteger("simple.assert.expensive",8); + public static boolean expensiveAssert() { return EXPENSIVE_ASSERT_LOG > 0; } + public static boolean expensiveAssert( int trip ) { + if( EXPENSIVE_ASSERT_LOG <= 0 ) return false; + if( EXPENSIVE_ASSERT_LOG == 1 ) return true; + int shift = Math.min(EXPENSIVE_ASSERT_LOG,30); + return (trip & ((1<<shift)-1)) == 0; + } + + // --------------------------- + // Module Source Root + public final String _modDir; + // Module Build Root + public final String _buildDir; + // Search path from CWD for `.o` files containing external symbols and types. + // This can contain archives, zips and other .o file containers. + public final Ary<String> _externPaths; + + // Dotted path from module root to file containing the source, sans ".smp". + // e.g. module root: "sys", nested source name "sys.io". + public final String _srcName; + + // Only available for tests, otherwise source comes from the CompUnit + private final String _src; + + // Current Working Directory; default module base + private final String _cwd; + + // Compilation Units in this compile; one per source/object file + public HashMap<String,CompUnit> _compunits; + // Test shortcut for only one compilation unit + public CompUnit compunit() { + assert _compunits.size()==1; + for( CompUnit cu : _compunits.values() ) + return cu; + assert false : "no compilation unit"; + return null; + } + + // True when fidx is published through a public field of a public class. + // TypeStruct.fidxs() already excludes private (underscore) fields. + public boolean publicFIDX(int fidx) { + if( fidx < GlobalBits.RESERVED ) return false; + // A public class initializer is itself an external root; unlike + // constructors and methods, it is not reached through a class field. + FunNode fun = _linker.atX(fidx); + if( fun != null && fun.isClz() && fun.isPublic() ) + return true; + // Constructors and methods live on their class objects, including + // nested classes which do not have their own CompUnit. + for( Type t : Parser.TYPES.values() ) + if( t instanceof TypeStruct clz && + Parser.startsClzPrefix(clz._name) && + Parser.isPublicClassName(clz._name) && + resolvedClass(clz) && + publicClassFIDX(clz,fidx) ) + return true; + return false; + } + + private static boolean publicClassFIDX(TypeStruct clz, int fidx) { + boolean hasCtor = clz.field("<ctor>") != null; + for( Field fld : clz._fields ) + if( fld._fname.charAt(0)!='_' && fld._t instanceof TypeFunPtr tfp && + // With a user constructor, class:N.N is the private <init>. + !(hasCtor && clz.hiddenInit(fld)) && + XInt.bit(tfp._fidxs,fidx) ) + return true; + return false; + } + + public static boolean hasUserConstructor(TypeStruct self) { + Type t = Parser.TYPES.get(Parser.addClzPrefix(self._name)); + return t instanceof TypeStruct clz && clz.field("<ctor>") != null; + } + + // A forward reference gets a class object and constructor signature so + // parsing can proceed, but it has no callable definition yet. + private static boolean resolvedClass(TypeStruct clz) { + Type t = Parser.TYPES.get(clz._name.substring(Parser.CLZ.length())); + return !(t instanceof TypeStruct ts) || !ts._fref; + } + + private int[] _publicFIDXs, _publicAliases; + + /** + * Freeze the externally visible portion of the program after ParseAll has + * loaded every compilation unit and closed/upgraded all types. Later + * optimization can remove linker entries and create inline-only fidxs; + * neither operation changes this interface. + */ + void freezePublicInterface() { + assert _publicFIDXs==null && _publicAliases==null; + int[] fidxs = XInt.EMPTY; + for( int fidx=GlobalBits.RESERVED; fidx<_linker._len; fidx++ ) + if( publicFIDX(fidx) ) + fidxs = XInt.make(fidxs,fidx); + int[] aliases = XInt.EMPTY; + for( Type t : Parser.TYPES.values() ) + if( t instanceof TypeStruct clz && + Parser.startsClzPrefix(clz._name) && + Parser.isPublicClassName(clz._name) && + resolvedClass(clz) ) { + boolean hasCtor = clz.field("<ctor>") != null; + for( Field fld : clz._fields ) + if( fld._fname.charAt(0)!='_' && fld._t!=Type.TOP && + !(hasCtor && clz.hiddenInit(fld)) ) + aliases = XInt.make(aliases,fld._alias); + } + _publicFIDXs = fidxs; + _publicAliases = aliases; + } + + public int[] publicFIDXs() { assert _publicFIDXs !=null; return _publicFIDXs; } + public int[] publicAliases(){ assert _publicAliases!=null; return _publicAliases; } + public boolean publicInterfaceFrozen() { return _publicFIDXs != null; } + // --------------------------- - // Compilation source code - public final String _src; - // Compile-time known initial argument type - public final TypeInteger _arg; + + // Very common nodes, cached here + public final ConstantNode ZERO; + public final XCtrlNode XCTRL; + + public Node constant( Type t ) { + assert _phase==null || _phase.ordinal() <= Phase.Opto.ordinal(); + return ConstantNode.make(t).peephole(); + } + public ConstantNode con( Type t ) { return (ConstantNode)constant(t); } + public ConstantNode con( long con ) { return con==0 ? ZERO : con(TypeInteger.constant(con)); } + // --------------------------- - public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L, true ); } - public CodeGen( String src, TypeInteger arg) { this(src, arg==null ? TypeInteger.BOT : arg, 123L, true ); } + // Test setup; no module nor file with specific argument + public CodeGen( String src ) { this(src, 126L, true ); } + + // Test setup; no module nor file; can alter seed & argument; can re-run same CodeGen + public CodeGen( String src, Type arg ) { + this(null,null,null,null, src, 126L, true, arg); + } + // Test setup; no module nor file; can alter seed & argument; can re-run same CodeGen + public CodeGen( String src, long workListSeed, boolean resetTypes ) { + this(null,null,null,null, src, workListSeed, resetTypes, TypeInteger.BOT); + } - public CodeGen( String src, TypeInteger arg, long workListSeed, boolean reset ) { + // Generic CodeGen, including full module setup + public CodeGen( String modDir, String buildDir, Ary<String> externPaths, + String srcName, String src, long workListSeed, boolean resetTypes, Type arg ) { + // Public singleton to avoid passing about this state to a huge count + // of places. Probably becomes a TLS at some point. CODE = this; - if( reset ) Type.reset(); - _main = makeFun(TypeFunPtr.MAIN); - _phase = null; - _callingConv = null; - _start = new StartNode(arg); - _stop = new StopNode(src); + if( resetTypes ) Type.reset(); // Reset to recover from failed test + + _cwd = System.getProperty("user.dir")+"/"; + _modDir = modDir == null ? _cwd : modDir; + _buildDir = buildDir == null ? _cwd : buildDir; + _externPaths = externPaths; + _srcName = srcName; + _callingConv = null; // Calling convention + // Source code from test strings, not files _src = src; - _arg = arg; - _iter = new IterPeeps(workListSeed); - P = new Parser(this,arg); + // All the compilation units + _compunits = new HashMap<>(); + _phase = null; + // Start GVN table + _gvn = new HashMap<>(); + // Allow whole-suite worklist-order sweeps without rewriting the many + // explicit seeds used by tests and command-line compilation. + String iterSeed = System.getProperty("simple.iter.seed"); + _iter = new IterPeeps(iterSeed == null ? workListSeed : Long.parseLong(iterSeed)); + // End points of graph + _stop = new StopNode().init(); + _start = new StartNode(null,_stop,arg).init(); + ZERO = con(TypeInteger.ZERO).keep(); + XCTRL = new XCtrlNode().peephole().keep(); + P = new Parser(this); } - // All passes up to Phase, except ELF - public CodeGen driver( Phase phase ) { return driver(phase,null,null); } + // Run requested phases. + + // No code emission, just IR generation + public CodeGen driver( Phase phase ) { return driver(phase,null,null,false,false,0); } + // No object file writing, but code generation for a specific cpu/os pair (allows emulation) public CodeGen driver( Phase phase, String cpu, String callingConv ) { - if( _phase==null ) parse(); - int p1 = phase.ordinal(); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Opto .ordinal() ) opto(); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.TypeCheck .ordinal() ) typeCheck(); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LoopTree .ordinal() ) loopTree(); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Select .ordinal() && cpu != null ) instSelect(cpu,callingConv); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Schedule .ordinal() ) GCM(); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LocalSched.ordinal() ) localSched(); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.RegAlloc .ordinal() ) regAlloc(); - if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Encoding .ordinal() ) encode(); + if( phase.ordinal() < Phase.Export.ordinal() ) + // No code outputted + return driver(phase,cpu,callingConv,false,false,0); + if( _srcName == null ) + throw new RuntimeException("No source filename provided, so do not know how to name the obj file"); + boolean emitEntrySymbol = !_srcName.contains("."); + return driver( phase, cpu, callingConv, false, emitEntrySymbol, 0 ); + } + // Write an object file for a specific cpu/os pair + + public CodeGen driver( String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol ) { return driver(Phase.Export,cpu,callingConv,inMemory,emitEntrySymbol,0); } + // Generic driver + public CodeGen driver( Phase phase, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) { + int p1 = phase.ordinal(), p2 = _phase==null ? -1 : _phase.ordinal(); + if( p2 < p1 && p2 < Phase.Parse .ordinal() ) { parse(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.Iter .ordinal() ) { iter(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.Opto .ordinal() ) { opto(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.TypeCheck .ordinal() ) { typeCheck(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.LoopTree .ordinal() ) { loopTree(); p2 = dump(dump); } + if( p2 < p1 && p1 >= Phase.Encoding .ordinal() ) { unlinkImports(); p2 = dump(dump); } + if( p2 < p1 && p1 >= Phase.Encoding .ordinal() ) { serialize(); p2 = dump(dump); } // Include ideal graph in object file + if( p2 < p1 && p2 < Phase.Unlink .ordinal() ) { unlink(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.Select .ordinal() && cpu != null ) { instSelect(cpu,callingConv); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.Schedule .ordinal() ) { GCM(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.LocalSched.ordinal() ) { localSched();p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.RegAlloc .ordinal() ) { regAlloc(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.Encoding .ordinal() ) { encode(); p2 = dump(dump); } + if( p2 < p1 && p2 < Phase.Export .ordinal() ) { exportELF(inMemory,emitEntrySymbol); p2 = dump(dump); } return this; } - // Run all the phases through final ELF emission - public CodeGen driver( String cpu, String callingConv, String obj ) throws IOException { - return driver(Phase.Encoding,cpu,callingConv).exportELF(obj); + public String entryClinitName() { + return Parser.addClzPrefix(_srcName==null ? "Test" : _srcName)+".<clinit>"; } + // Verbose printing during compilation + private int dump(int dump) { + int p2 = _phase.ordinal(); + if( (dump & (1<<p2)) == 0 ) return p2; + + + if( (dump & (1<<30)) != 0 ) + System.err.println("After "+_phase+":"); + System.err.println(_phase.ordinal() >= Phase.LocalSched.ordinal() + ? asm(new SB()).toString() + : IRPrinter.prettyPrint(this)); + return p2; + } + + + // Record times by phase + public final long[] _times = new long[Phase.LastPhase.ordinal()]; // --------------------------- /** @@ -92,9 +300,45 @@ public class CodeGen { return _uid++; } - // Next available memory alias number - private int _alias = 2; // 0 is for control, 1 for memory - public int getALIAS() { return _alias++; } + + // These next fields all 2-way map some *global* program feature to a + // local dense index, suitable for packing in BitSets. The mapping takes a + // global value - always a {source file/class} name, and an order number + // counting up per feature in the same file. The dense local index can be + // different in different compilations. + + // The global info allows loading the same remote class info from different + // paths and aligning them. Example: Compiling A loads pre-compiled B and + // C, both of which load pre-compiled D. The 2 different D loads unify via + // this global info. + + // These mappings are all trivial identities when compiling one file; they + // only become complex when loading separately compiled code. + + // Compute local function index (FIDX) from global function info. This is + // called *in order* during parsing, and that order is part of the global + // unique mapping + public final GlobalBits _aliases = new GlobalBits(); + public int alias(String clz) { return _aliases.next(clz); } + + // C storage has one global alias per symbol, including across object files. + public int externAlias(String name) { return _aliases.next("C:"+name,GlobalBits.RESERVED); } + + // External data addresses supplied by an in-memory linker (image offsets). + public final HashMap<String,Integer> _externDataAddresses = new HashMap<>(); + + // Compute local function index (FIDX) from global function info. This is + // called *in order* during parsing, and that order is part of the global + // unique mapping + public final GlobalBits _fidxs = new GlobalBits(); + // Return local index for specific global file & order. Used to find fidxs for e.g. FREF class <init> fcns + public int fidx( String clz, int order ) { return _fidxs.next(clz, order); } + // New fidx in the current file + public int fidx( String clz ) { return fidx(clz, -1); } + + // Compute local RPC index from global RPC info, one per call + public final GlobalBits _rpcs = new GlobalBits(); + public int rpc( String clz ) { return _rpcs.next(clz); } // Inlining can insert CFG edges and invalidate cached depth ordering. @@ -109,34 +353,22 @@ public class CodeGen { public final BitSet _visit = new BitSet(); public BitSet visit() { assert _visit.isEmpty(); return _visit; } - // Start and stop; end points of the generated IR + // Start and Stop; end points of the generated IR public StartNode _start; public StopNode _stop; // Global Value Numbering. Hash over opcode and inputs; hits in this table // are structurally equal. - public final HashMap<Node,Node> _gvn = new HashMap<>(); + public final HashMap<Node,Node> _gvn; - // Source of unique function indices - private int _fidx =0; - public TypeFunPtr makeFun( TypeFunPtr fun ) { - int fidx = _fidx++; - assert fidx<64; // TODO: need a larger FIDX space - return fun.makeFrom(fidx); - } - // Signature for MAIN - public TypeFunPtr _main; - public void setMain(FunNode main) { - _main = main.sig(); - link(main); - } // Reverse from a constant function pointer to the IR function being called. // Error to call with a non-constant TFP public FunNode link( TypeFunPtr tfp ) { return link(tfp.fidx()); } - // Read-only diagnostic lookup; preserve stale entries. - public FunNode _link(TypeFunPtr tfp) { return _link(tfp.fidx()); } + // Read-only linker lookup, suitable for printers and debugger display. + // In particular, do not lazily remove a partially dead function. public FunNode _link(int fidx) { return _linker.atX(fidx); } - // Return the FunNode from a fidx, cleaning up dead entries. + public FunNode _link(TypeFunPtr tfp) { return _link(tfp.fidx()); } + // Return the FunNode from a fidx public FunNode link( int fidx ) { FunNode fun =_linker.atX(fidx); if( fun!=null && fun.isDead() ) { @@ -154,21 +386,49 @@ public class CodeGen { // "Linker" mapping from constant TypeFunPtrs to heads of function. These // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so // the return is not part of the match). - final Ary<FunNode> _linker = new Ary<>(FunNode.class); + public final Ary<FunNode> _linker = new Ary<>(FunNode.class); + // Extern function declarations; input is the FIDX assigned to the name. + final HashMap<Integer,String> _externFunc = new HashMap<>(); + public void externFunc(int fidx, String ex) { + assert !_externFunc.containsKey(fidx); + _externFunc.put(fidx,ex); + } + public String externFunc(int fidx) { return _externFunc.get(fidx); } + + public String funcName(int fidx ) { + FunNode fun = _link(fidx); + if( fun!=null ) return fun._name; + return externFunc(fidx); + } + + public boolean owns(FunNode fun) { + return fun._compunit != null && fun._compunit._src != null; + } + + + // --------------------------- // Parser object public final Parser P; // Parse ASCII text into Sea-of-Nodes IR - public int _tParse; public CodeGen parse() { assert _phase == null; _phase = Phase.Parse; long t0 = System.currentTimeMillis(); - P.parse(); - _tParse = (int)(System.currentTimeMillis() - t0); - if( _obs != null ) _obs.phase("Parse"); + Parser.TYPES.clear(); + Parser.TYPES.putAll(Parser.INIT_TYPES); + if( _src != null ) { + // No source file, just the source itself. + ParseAll.parseSource(this,_srcName==null ? "Test" : _srcName,_src); + } else { + // Path from module root to source file + ParseAll.parsePath(this,_srcName); + } + + _times[Phase.Parse.ordinal()] = System.currentTimeMillis() - t0; + if( _obs != null ) _obs.phase(_phase.name()); return this; } @@ -184,25 +444,89 @@ public class CodeGen { public void iterCnt() { if( !_midAssert ) _iter_cnt++; } public void iterNop() { if( !_midAssert ) _iter_nop_cnt++; } + // Pessimistic peepholes after parsing. This lifts loaded and parsed + // types before the optimistic Opto pass resets types and lets them fall. + public CodeGen iter() { + assert _phase == Phase.Parse; + _phase = Phase.Iter; + long t0 = System.currentTimeMillis(); + + // The phase shift closes all parser-in-progress states and freezes + // unknown external inputs. Imported nodes carry post-Opto escape + // precision, but Iter is a fresh pessimistic solve: memory escape + // summaries must restart at FULL so newly discovered private escapes + // can only be removed, never added. Seed the complete graph once. + boolean hasImports = _externPaths != null; + _start.walk(n -> { + if( !(n instanceof ConstantNode) ) + n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); + add(n); + return null; + }); + _iter.iterate(this); + // Expensive assert. + assert !expensiveAssert() || Opto.fixedPointCheck(this); + + _times[Phase.Iter.ordinal()] = System.currentTimeMillis() - t0; + if( _obs != null ) _obs.phase(_phase.name()); + return this; + } + + private static Type iterEscapeReset(Type t) { + if( t instanceof TypeMem mem ) + return mem._one ? mem : mem.makeFrom(XInt.FULL,XInt.FULL); + if( t instanceof TypeTuple tt ) { + TypeTuple rez = tt; + for( int i=0; i<tt._types.length; i++ ) { + Type tx = iterEscapeReset(tt._types[i]); + if( tx != tt._types[i] ) rez = rez.makeFrom(i,tx); + } + return rez; + } + return t; + } + + private static Type iterImportReset(Type t) { + if( t.isHigh() ) + return t.dual(); + if( t instanceof TypeMem mem ) + return TypeMem.make(mem._alias,iterImportReset(mem._t),mem._one,mem._clz,mem._final,XInt.FULL,XInt.FULL); + if( t instanceof TypeMemPtr ) + return t.makeStorage(); + if( t instanceof TypeStruct ) + return t.makeStorage(); + if( t instanceof TypeTuple tt ) { + TypeTuple rez = tt; + for( int i=0; i<tt._types.length; i++ ) { + Type tx = iterImportReset(tt._types[i]); + if( tx != tt._types[i] ) rez = rez.makeFrom(i,tx); + } + return rez; + } + return t; + } + + // Run ideal optimizations - public int _tOpto; public CodeGen opto() { - assert _phase == Phase.Parse; + if( _phase == Phase.Parse ) + iter(); + assert _phase == Phase.Iter; _phase = Phase.Opto; long t0 = System.currentTimeMillis(); Opto.opto(this); - _tOpto = (int)(System.currentTimeMillis() - t0); - if( _obs != null ) _obs.phase("Opto"); + _times[Phase.Opto.ordinal()] = System.currentTimeMillis() - t0; + if( _obs != null ) _obs.phase(_phase.name()); return this; } public <N extends Node> N add( N n ) { return _iter.add(n); } public void addAll( Ary<Node> ary ) { _iter.addAll(ary); } + public void addAll( Node n ) { _iter.add(n); _iter.addAll(n._inputs); } // --------------------------- // Last check for bad programs - public int _tTypeCheck; public CodeGen typeCheck() { // Demand phase Opto for cleaning up dead control flow at least, // required for the following GCM. @@ -210,38 +534,128 @@ public class CodeGen { _phase = Phase.TypeCheck; long t0 = System.currentTimeMillis(); - Parser.ParseException err = _stop.walk(n -> { - Parser.ParseException msg = n.err(); - if( msg != null && _obs != null ) _obs.error(n, msg.getMessage()); - return msg; - }); - _tTypeCheck = (int)(System.currentTimeMillis() - t0); - if( err != null ) + final Ary<Node> errs = new Ary<>(Node.class); + _stop.walk( n -> { + if( n.err() != null ) + errs.add(n); + return null; + }); + String unresolved = unresolvedTypeName(); + _times[Phase.TypeCheck.ordinal()] = System.currentTimeMillis() - t0; + if( !errs.isEmpty() ) { + // Prefer an originating error over a secondary error caused by a + // BOTTOM input. If all errors are downstream-poisoned, retain + // the old first-error behavior. + Node min = null; + for( Node n : errs ) + if( noBottomInputs(n) ) { + min = n; + break; + } + if( min==null ) + min = errs.at(0); + for( Node n : errs ) + if( n!=min && + noBottomInputs(n) && + ((n instanceof MemOpNode nmop && + min instanceof MemOpNode mmop && + nmop._loc.before(mmop._loc)) || + (n instanceof CFGNode ncfg && + min instanceof CFGNode mincfg && + ncfg.idepth() < mincfg.idepth())) ) + min = n; + if( _obs != null ) _obs.error(min, min.err().getMessage()); + throw min.err(); + } + if( unresolved != null ) { + var err = Parser.error("Unknown struct type '"+unresolved+"'",null); + if( _obs != null ) _obs.error(null, err.getMessage()); throw err; + } if( _obs != null ) _obs.phase("TypeCheck"); return this; } + private static boolean noBottomInputs(Node n) { + for( Node def : n._inputs ) + if( def!=null && !(def instanceof FldOffNode) && def._type==Type.BOTTOM ) + return false; + return true; + } + + // Forward-ref structs are open while parsing. They must all be resolved + // to closed structs before leaving type checking. + private String unresolvedTypeName() { + String[] unresolved = new String[1]; + _stop.walk(n -> { + TypeStruct ts = requiredStruct(n); + if( unresolved[0]==null && ts!=null && ts._fref ) + unresolved[0] = ts._name; + return null; + }); + return unresolved[0]; + } + + public static TypeStruct requiredStruct(Node n) { + if( n instanceof NewNode alloc ) return alloc._ts; + if( n instanceof ConFldOffNode off ) return off._ts; + if( n instanceof FldOffNode off && off.in(0)._type instanceof TypeMemPtr ptr ) return ptr._obj; + return null; + } + // --------------------------- // Build the loop tree; break never-exit loops - public int _tLoopTree; public CodeGen loopTree() { - assert _phase.ordinal() <= Phase.TypeCheck.ordinal(); + assert _phase.ordinal() <= Phase.Serialize.ordinal(); _phase = Phase.LoopTree; long t0 = System.currentTimeMillis(); // Build the loop tree, fix never-exit loops - _start.buildLoopTree(_start,_stop); - _tLoopTree = (int)(System.currentTimeMillis() - t0); + _start.buildLoopTree( _linker, _stop); + // Invariant theory: No more type or code changes after Opto. The + // LoopTree stuff is used to do layouts now, but not core opts. TODO: + // at some future date we'll do loop opts (e.g. peeling, unrolling) + // that will totally impact code shape, types and core opts - but this + // will be done in tandem with Opto changes. + //_iter.iterate(this); + _times[Phase.LoopTree.ordinal()] = System.currentTimeMillis() - t0; return this; } // --------------------------- + public BAOS _serial; + public void serialize() { + assert _phase.ordinal() <= Phase.Serialize.ordinal(); + _phase = Phase.Serialize; + long t0 = System.currentTimeMillis(); + // Does not change compiler phase; just records IR + Serialize.serialize(this); + _times[Phase.Serialize.ordinal()] = System.currentTimeMillis() - t0; + } + + // Unlink imported function bodies before serialization. Calls to them + // remain as normal calls through their function pointer, and codegen later + // turns them into external relocations. + private void unlinkImports() { + assert _phase.ordinal() <= Phase.Serialize.ordinal(); + for( FunNode fun : _linker ) { + if( fun==null || fun.isDead() || owns(fun) ) + continue; + for( int i=1; i<fun.nIns(); i++ ) + if( fun.in(i) instanceof CallNode call ) + call.unlink(fun,i--); + } + //_iter.iterate(this); + } + + // --------------------------- // Code generation CPU target public Machine _mach; // Chosen calling convention (usually either Win64 or SystemV) public String _callingConv; + public String _cCallingConv; // Callee save registers public RegMask _callerSave; + public RegMask _cCallerSave; // All returns have the following inputs: // 0 - ctrl @@ -254,10 +668,9 @@ public class CodeGen { public RegMask _rpcMask; // Convert to target hardware nodes - public int _tInsSel; public CodeGen instSelect( String cpu, String callingConv ) { return instSelect(cpu,callingConv,PORTS); } public CodeGen instSelect( String cpu, String callingConv, String base ) { - assert _phase.ordinal() == Phase.LoopTree.ordinal(); + assert _phase.ordinal() <= Phase.Unlink.ordinal(); _phase = Phase.Select; _callingConv = callingConv; @@ -269,12 +682,17 @@ public class CodeGen { try { _mach = ((Class<Machine>) Class.forName( clzFile )).getDeclaredConstructor(new Class[]{CodeGen.class}).newInstance(this); } catch( Exception e ) { throw new RuntimeException(e); } + _cCallingConv = _mach.cCallingConv(callingConv); + // Build global copies of common register masks. long callerSave = _mach.callerSave(); + long cCallerSave= _mach.callerSave(_cCallingConv); long neverSave = _mach. neverSave(); int maxReg = Math.min(64,_mach.regs().length); assert maxReg>=64 || (-1L << maxReg & callerSave)==0; // No stack slots in callerSave + assert maxReg>=64 || (-1L << maxReg & cCallerSave)==0; // No stack slots in cCallerSave _callerSave = new RegMask(callerSave); + _cCallerSave= new RegMask(cCallerSave); // Build a Return RegMask array. All returns have the following inputs: // 0 - ctrl @@ -294,12 +712,20 @@ public class CodeGen { _uid = 1; // All new machine nodes reset numbering var map = new IdentityHashMap<Node,Node>(); _instSelect( _stop, map ); - _stop = ( StopNode)map.get(_stop ); + _stop = (StopNode)map.get(_stop ); StartNode start = (StartNode)map.get(_start); _start = start==null ? new StartNode(_start) : start; _instOuts(_stop,visit()); _visit.clear(); - _tInsSel = (int)(System.currentTimeMillis() - t0); + + // Replace the CompUnit stop (and list of functions) + // with hardware-specific ones + for( CompUnit cu : _compunits.values() ) { + cu._start= (StartCUNode)map.get(cu._start); + cu._stop = (StopCUNode )map.get(cu._stop ); + } + + _times[Phase.Select.ordinal()] = System.currentTimeMillis() - t0; return this; } @@ -307,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 @@ -320,18 +748,33 @@ public class CodeGen { } // Produce a machine node from n; map it to flag as done so stops cycles. + if( n instanceof MemOpNode mem && mem.off() instanceof ExternOffsetNode off ) { + // External fields replace base+offset with symbol+0. Keep the ideal + // declaring type on the address for machine load/store width selection. + TypeMemPtr ptr = (TypeMemPtr)mem.ptr()._type; + n._inputs.set(2,new ExternNode(TypeMemPtr.make((byte)2,ptr._obj,true),off._extern)); + n._inputs.set(3,ConstantNode.raw(TypeInteger.ZERO)); + } map.put(n, x=_mach.instSelect(n) ); - // Stop retains the callable body. Its lifetime edge is not a machine operand. - if( n instanceof FunPtrNode ) x._inputs.pop(); + // Carry loop-tree and pre-order info across the ideal->mach transition + if( n instanceof CFGNode ncfg && x instanceof CFGNode xcfg ) { + xcfg._ltree = ncfg._ltree; + xcfg._pre = ncfg._pre; + } // Walk machine op and replace inputs with mapped inputs for( int i=0; i < x.nIns(); i++ ) x._inputs.set(i, _instSelect(x.in(i),map) ); - if( x instanceof MachNode mach ) + // Post selection action + if( x instanceof MachNode mach ) { + if( n instanceof ReturnNode ret ) + ((ReturnNode)mach)._fun = (FunNode)map.get(ret._fun); mach.postSelect(this); // Post selection action + } return x; } + // Walk all machine Nodes, and set their output edges private void _instOuts( Node n, BitSet visit ) { if( visit.get(n._nid) ) return; @@ -339,14 +782,100 @@ public class CodeGen { for( Node in : n._inputs ) if( in!=null ) { in._outputs.push(n); + // CallNode special: outputs are partially ordered; CallEnd in slot 0 + if( in instanceof CallNode call && n instanceof CallEndNode cend && call.out(0) != cend ) + call._outputs.swap(0,call.nOuts()-1); _instOuts(in,visit); } } + // --------------------------- + public void unlink() { + assert _phase.ordinal() <= Phase.Select.ordinal(); + _phase = Phase.Unlink; + long t0 = System.currentTimeMillis(); + + // The remaining passes assume all calls are unlinked; i.e. we are throwing + // away the Call Graph here. Functions only reachable from internal calls + // need to be re-hooked to stop/start less they go dead. + for( FunNode fun : _linker ) { + // Already linked to start, not going dead + if( fun==null || fun.isDead() ) + continue; + + // Imported functions are not emitted by this object. Unlink any + // concrete calls so they become normal external relocations. + if( !owns(fun) ) { + while( fun.nIns() > 1 ) { + if( fun.in(1) instanceof CallNode call ) + call.unlink(fun,1); + else + fun.removeDeadPath(1); + } + StartCUNode start = fun._compunit._start; + StopCUNode stop = fun._compunit._stop; + // Unhook the Stop->Return edge also + ReturnNode ret = fun.ret(); + int idx = stop._inputs.find(ret); + if( idx != -1 ) { + stop._inputs.del(idx); + ret.delUse(stop); + } + // + if( stop.nIns()==0 ) { + idx = _stop._inputs.find(stop); + if( idx != -1 ) + _stop.delDef(idx); + if( start.nIns() > 0 && start.in(0) != null ) + start.setDef(0,null); + if( start.nIns() > 1 && start.in(1) != null ) + start.setDef(1,null); + } + continue; + } + + // Insert the post-Opto code-generation hook. Unlike an Opto-time + // Start input, this no longer carries unknown-caller semantics. + ReturnNode ret = fun.ret(); + StartNode start = fun._compunit._start; + assert start!=null; + if( fun.nIns() <= 1 || fun.in(1) != start ) { + fun.insertDef(1,start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + parm.insertDef(1,ConstantNode.raw(parm._type)); + if( fun._compunit._stop._inputs.find(ret) == -1 ) + fun._compunit._stop.addDef(ret); + } + // Unlink from Call + for( int i=2; i<fun.nIns(); i++ ) + ((CallNode)fun.in(i)).unlink(fun,i--); + if( fun.rpc()==null ) { // Ensure valid RPC + // First make sure a valid RPC; single-call into multi-fun will have each + // function having a single call site, so the RPC becomes a constant and + // folds - but since multiple targets, the Call never inlines. Recreate a + // valid RPC so codegen (and Eval2) understands the calling convention. + ParmNode rpc = new ParmNode( "$rpc", 0, ret.rpc()._type, fun ); + rpc.addDef(ret.rpc()); + ret.setDef( 3, rpc.init() ); + } + } + + _stop.walk(n -> { + if( n instanceof CallEndNode cend ) + for( int i=1; i<cend.nIns(); i++ ) + if( cend.in(i) instanceof ReturnNode ) + cend.delDef(i--); + if( n instanceof CallNode call ) + call.unlink_all(); + return null; + }); + + _times[Phase.Unlink.ordinal()] = System.currentTimeMillis() - t0; + } // --------------------------- // Control Flow Graph in Reverse Post Order. - public int _tGCM; public Ary<CFGNode> _cfg = new Ary<>(CFGNode.class); // Global schedule (code motion) nodes @@ -356,27 +885,25 @@ public class CodeGen { long t0 = System.currentTimeMillis(); GlobalCodeMotion.buildCFG(this); - _tGCM = (int)(System.currentTimeMillis() - t0); + _times[Phase.Schedule.ordinal()] = System.currentTimeMillis() - t0; return this; } // --------------------------- // Local (basic block) scheduler phase, a classic list scheduler - public int _tLocal; public CodeGen localSched() { assert _phase == Phase.Schedule; _phase = Phase.LocalSched; long t0 = System.currentTimeMillis(); ListScheduler.sched(this); - _tLocal = (int)(System.currentTimeMillis() - t0); + _times[Phase.LocalSched.ordinal()] = System.currentTimeMillis() - t0; return this; } // --------------------------- // Register Allocation - public int _tRegAlloc; public RegAlloc _regAlloc; public CodeGen regAlloc() { assert _phase == Phase.LocalSched; @@ -384,15 +911,14 @@ public class CodeGen { long t0 = System.currentTimeMillis(); _regAlloc = new RegAlloc(this); _regAlloc.regAlloc(); - _tRegAlloc = (int)(System.currentTimeMillis() - t0); + _times[Phase.RegAlloc.ordinal()] = System.currentTimeMillis() - t0; return this; } - // Human readable register name - public String reg(Node n) { return reg(n,null); } - public String reg(Node n, FunNode fun) { + // Human-readable register name + public String reg(Node n) { if( _phase.ordinal() >= Phase.RegAlloc.ordinal() ) { - String s = _regAlloc.reg(n,fun); + String s = _regAlloc.reg(n); if( s!=null ) return s; } return "N"+ n._nid; @@ -401,50 +927,169 @@ public class CodeGen { // --------------------------- // Encoding - public int _tEncode; - public Encoding _encoding; // Encoding object - public void preEncode() { } // overridden by alternative ports + public Encoding _encoding; public CodeGen encode() { assert _phase == Phase.RegAlloc; _phase = Phase.Encoding; long t0 = System.currentTimeMillis(); - _encoding = new Encoding(this); - preEncode(); - _encoding.encode(); - _tEncode = (int)(System.currentTimeMillis() - t0); + + _encoding = new Encoding(this).encode(); + + _times[Phase.Encoding.ordinal()] = System.currentTimeMillis() - t0; return this; } // --------------------------- // Exporting to external formats - public CodeGen exportELF(String fname) throws IOException { + ElfWriter _elf; + public CodeGen exportELF( boolean inMemory, boolean emitEntrySymbol ) { assert _phase == Phase.Encoding; _phase = Phase.Export; - if( fname == null ) new LinkMem(this).link(); // In memory patching - else new ElfFile(this).export(fname); // External ELF file + long t0 = System.currentTimeMillis(); + if( _encoding!=null ) { + if( inMemory ) + new LinkMem(this).link(_encoding); // In memory patching + else + _elf = new ElfWriter(this).export(emitEntrySymbol); + } + _times[Phase.Export.ordinal()] = System.currentTimeMillis() - t0; return this; } + + // --------------------------- + + // Search a external path list, each path is recursively searched for .o + // files, which are partially loaded and searched for public symbols. + + // This is a state machine which lazily searches down the set of search + // paths until the requested module is class is found. + + // Map from external Strings to either partially read Simple ElfFile or ExternNode + public final HashMap<String,Object> _externSymbols = new HashMap<>(); + + // State machine elements; the outermost element is _externPaths + private int _extPathIdx; // Search index into the extern path list + private final Ary<File> _files = new Ary<>(File.class); // Files in the current extern path being searched + private int _extFileIdx; // Index into _files + + public ElfReader findExternalSimple( String name ) { + return findExternalSymbol(name) instanceof ElfReader elf ? elf : null; + } + + public ExternNode findExternal( String name ) { + return findExternalSymbol(name) instanceof ExternNode extern ? extern : null; + } + + // Search the search-path for the name; return an ElfReader if found in a + // Simple-made ELF; return an ExternNode if from another ELF, or null if + // not found. + private Object findExternalSymbol( String name ) { + // State Machine! + + while( true ) { + // Check for an immediate hit + switch( _externSymbols.get(name) ) { + + case ExternNode extern: + // Name maps to an ExternNode + return extern; + + case ElfReader elf: + return elf; + + case null: + // Name is unknown. Advance the file-system search, pulling + // out new ELF files from the search directory list and loading + // their published symbols. + + // The last directory was mined out, so get the next search + // directory and find all ELF-like files. + if( _extFileIdx >= _files._len ) { + if( _externPaths==null || _extPathIdx >= _externPaths._len ) + return null; // A true miss in the whole search path + loadExtPath(); // Load next batch file of files + break; + } + // Load and parse an ELF header + ElfReader elf = getElf(_files.at(_extFileIdx++)); + if( elf == null ) break; // Not an ELF + // Load public symbols from the ELF + elf.loadPublicSymbols(); + if( elf._strs==null ) break; // No .simple section with strings + // Put public symbol in global table; first names shadow all others + // Map from symbol string to ELFReader; most lookups + // will miss and no need to unpack ElfReader types + _externSymbols.putIfAbsent(elf._strs[1],elf); + for( String str : elf._strs ) + if( str.startsWith(Parser.CLZ) ) + _externSymbols.putIfAbsent(str,elf); + break; + + default: throw Utils.TODO("should not reach here"); + } + } + } + + // Load all the .o files in the next external path. + private void loadExtPath() { + _files.clear(); + _extFileIdx = 0; + String extpath = _externPaths.at(_extPathIdx++); + File f = new File(extpath); + if( !f.isAbsolute() ) + f = new File(_cwd+extpath); + fillExtFiles(f); + } + + // Recursive search (TODO: gzip, archives) and gather all .o files. + private void fillExtFiles(File dir) { + if( dir.isDirectory() ) + for( File f : dir.listFiles() ) + fillExtFiles(f); + else if( dir.getName().endsWith(".o") ) + _files.add(dir); + } + + // Map from object file names to ElfReaders + public final HashMap<String,ElfReader> _elfs = new HashMap<>(); + ElfReader getElf(File f) { + ElfReader elf = _elfs.get(f.getPath()); + if( elf != null ) + return elf; + _elfs.put(f.getPath(), elf = ElfReader.load(f,null)); + return elf; + } + // --------------------------- public boolean _asmLittle=true; - SB asm(SB sb) { return ASMPrinter.print(sb,this); } public String asm() { return asm(new SB()).toString(); } + SB asm(SB sb) { + ASMPrinter.print(sb,this); + return sb; + } // Testing shortcuts - public Node ctrl() { return _stop.ret().ctrl(); } - public Node expr() { return _stop.ret().expr(); } - public String print() { return _stop.print(); } + public Node ctrl() { return compunit()._stop.ret().ctrl(); } + public Node expr() { return compunit()._stop.ret().expr(); } + public String print() { return compunit()._stop.print(); } // Debugging helper @Override public String toString() { - return _phase.ordinal() > Phase.Schedule.ordinal() - ? IRPrinter._prettyPrint( this ) - : IRPrinter.prettyPrint(this); + if( _stop == null ) + return "No StopNode"; + return IRPrinter.prettyPrint(this); } // Debugging helper - public Node f(int idx) { return _stop.find(idx); } + public Node f(int idx) { + for( CompUnit cu : _compunits.values() ) { + Node n = (cu._stop == null ? _stop : cu._stop).find(idx); + if( n != null ) return n; + } + return null; + } String printCFG() { @@ -463,28 +1108,4 @@ public class CodeGen { } System.out.println(); } - - public void print_as_hex() { - for (byte b : _encoding._bits.toByteArray()) { - System.out.print(String.format("%02X", b)); - } - System.out.println(); - } - - //// Debug purposes for now -// public CodeGen printENCODING() { -// ByteArrayOutputStream outputStream = new ByteArrayOutputStream(); -// -// for(Node bb : CodeGen.CODE._cfg) { -// for(Node n: bb.outs()) { -// if(n instanceof MachNode) { -// ((MachNode) n).encoding(E); -// } -// } -// } -// -// print_as_hex(outputStream); -// // Get the raw bytes from the output stream -// return this; -// } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java new file mode 100644 index 00000000..d1326cee --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -0,0 +1,135 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.util.*; +import java.io.File; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import java.util.*; +import static com.seaofnodes.simple.codegen.CodeGen.CODE; + +// A compilation-unit, which is an external reference and source and object +// files. These are mirrored over a file system tree (so form a tree), both +// the source tree and build/object tree. +public class CompUnit { + public final CompUnit _par; // Parent, e.g. A/B + final String _fname; // Full slashed file name starting from module root, e.g. A/B/C + final public String _cname; // Full dotted class name starting from module root, e.g. A.B.C + final String _name; // Base name, e.g. C + final ExternNode _ext; // Found in external libs; e.g. libc + final File _smp; // Simple source file, e.g. module_root/A/B/C.smp + public final File _obj; // ELF output file, e.g. build/A/B/C.o + final public String _src; // Source code, from file or test case + //public Encoding _encoding; // Encoding for output + + public TypeStruct _clz; // The one TypeStruct being published + //BAOS _serial; // Serialized IR for this ELF file + Ary<CompUnit> _deps; // CompUnits that this CompUnit depends on + + // Per-Compilation-Unit Start/StopNodes, keeping alive all exported Nodes. + // Null means no code loaded (yet). + public StartCUNode _start; + public StopCUNode _stop ; + + + // Discovered source file. Source is loaded if required to parse, and null + // otherwise. + CompUnit( CompUnit par, String fname, String cname, String name ) throws IOException { + _par = par; + _fname= fname; + _cname= cname; + _name = name; + _ext = null; + _smp = new File( CODE. _modDir + "/" + fname + ".smp"); + _obj = new File( CODE._buildDir + "/" + fname + ".o" ); + + boolean mustCompile = _smp.exists() && // Has source to compile + ( !_obj.exists() || // No object file + _smp.lastModified() > _obj.lastModified() || // Out-of-date with source? + checkDependentObjs() ); // Out-of-date with other objs? + _src = mustCompile ? new String(Files.readAllBytes(_smp.toPath())) : null; + } + + // Test case. No source file. Source code passed in as a String. Fake + // class name. + CompUnit( String fname, String src ) { + _par = null; + _name = fname; + _fname= fname; + _cname= fname; + _ext = null; + _smp = null; + _obj = null; + _src = src; + } + + // External CompUnit, pulled in from an external library like libc + CompUnit( ExternNode ext, String symbol ) { + _par = null; + _name = symbol; + _fname= _name; + _cname= null; + _ext = ext; + _smp = null; + _obj = null; + _src = null; + } + + // External Simple object file, or namespace parent, found on an external search path. + CompUnit( File obj, CompUnit par, String fname, String cname, String name ) { + _par = par; + _name = name; + _fname= fname; + _cname= cname; + _ext = null; + _smp = null; + _obj = obj; + _src = null; + } + + // Return true if _obj is out-of-date relative to dependents. + private boolean checkDependentObjs() { + ElfReader elf = CODE.getElf(_obj); + elf.loadPublicSymbols(); + for( String dep : elf._deps ) { + File obj = new File(CODE._buildDir+"/"+dep+".o"); + if( obj.lastModified() > _obj.lastModified() ) // Out-of-date with deps? + return true; + } + return false; + } + + // Add a discovered dependency, for later writing out in an ELF file, ".simple" section + void addDep(CompUnit dep) { + if( _deps == null ) _deps = new Ary<>(CompUnit.class); + _deps.add(dep); + } + + public void addFun(CodeGen code, FunNode fun) { + assert fun.in(1)==_start; + _stop.addDef(fun.ret()); + code.add(_stop); + _stop.addDep(fun); + } + + void setStart(CodeGen code) { + _stop = new StopCUNode().init(); + _start = new StartCUNode(code._start,_stop, Type.BOTTOM, _fname).init(); + code._stop.addDef(_stop); + } + + + @Override public String toString() { + String x = "{"+_cname; + if( _smp!=null && _smp.exists()) x += ",hasSMP"; + if( _obj!=null && _obj.exists()) x += ",hasObj"; + if( _src!=null ) x += ",hasSrc"; + if( _ext != null ) x += ",isExt"; + x += "}"; + return x; + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfExpr.java b/src/main/java/com/seaofnodes/simple/codegen/ElfExpr.java deleted file mode 100644 index 9d9b8a1c..00000000 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfExpr.java +++ /dev/null @@ -1,87 +0,0 @@ -package com.seaofnodes.simple.codegen; - -import java.io.FileOutputStream; -import java.io.IOException; -import java.nio.ByteBuffer; -import java.nio.ByteOrder; - -public class ElfExpr { - public static void main(String[] args) { - try (FileOutputStream fos = new FileOutputStream("hello.o")) { - ByteBuffer buffer = ByteBuffer.allocate(512); - buffer.order(ByteOrder.LITTLE_ENDIAN); - - // === ELF HEADER (64 bytes) === - buffer.put(new byte[]{ - 0x7F, 'E', 'L', 'F', // ELF Magic - 2, 1, 1, 0, // 64-bit, little-endian, version - 0, 0, 0, 0, 0, 0, 0, // ABI padding - 2, 0, // Type: Executable (ET_EXEC) - 0x3E, 0x00, // Machine: x86-64 - 1, 0, 0, 0, // ELF version - 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // Entry point - 0, 0, 0, 0, 0, 0, 0, 0, // Program header offset - 64, 0, 0, 0, 0, 0, 0, 0, // Section header offset - 0, 0, 0, 0, // Flags - 64, 0, // ELF header size - 0, 0, // Program header entry size - 0, 0, // Number of program header entries - 40, 0, // Section header entry size - 2, 0, // Number of section headers - 1, 0 // Section header string table index - }); - - // === .TEXT SECTION (Executable Code) === - byte[] textSection = { - // sys_write (write(1, message, 13)) - (byte) 0x48, (byte) 0xC7, (byte) 0xC0, 0x01, 0x00, 0x00, 0x00, // mov rax, 1 - (byte) 0x48, (byte) 0xC7, (byte) 0xC7, 0x01, 0x00, 0x00, 0x00, // mov rdi, 1 - (byte) 0x48, (byte) 0xBE, (byte)0x90, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // mov rsi, message - (byte) 0x48, (byte) 0xC7, (byte) 0xC2, 0x0D, 0x00, 0x00, 0x00, // mov rdx, 13 - (byte) 0x0F, (byte) 0x05, // syscall - - // sys_exit (exit(0)) - (byte) 0x48, (byte) 0xC7, (byte) 0xC0, 0x3C, 0x00, 0x00, 0x00, // mov rax, 60 - (byte) 0x48, (byte) 0x31, (byte) 0xFF, // xor rdi, rdi - (byte) 0x0F, (byte) 0x05 // syscall - }; - - // Append section data - buffer.position(256); - buffer.put(textSection); - - // === STRING MESSAGE (.data Section) === - byte[] message = "Hello, World!\n".getBytes(); - buffer.position(400); - buffer.put(message); - - // === SECTION HEADERS === - buffer.position(64); - - // Null Section (required as first entry) - buffer.put(new byte[40]); - - // .text Section - buffer.putInt(1); // Offset in section string table (".text") - buffer.putInt(1); // Type: SHT_PROGBITS - buffer.putLong(6); // Flags: Executable | Allocatable - buffer.putLong(0); // Virtual address - buffer.putLong(256); // Offset to section data - buffer.putLong(textSection.length); // Section size - buffer.putInt(0); // Link - buffer.putInt(0); // Info - buffer.putLong(4); // Address alignment - buffer.putLong(0); // No extra entries - - // === SECTION HEADER STRING TABLE === - buffer.position(500); - buffer.put(".text".getBytes()); - buffer.put((byte) 0x00); // Null terminator - - fos.write(buffer.array()); - System.out.println("ELF object file 'hello.o' created."); - } catch (IOException e) { - e.printStackTrace(); - } - } -} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java deleted file mode 100644 index b6267600..00000000 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ /dev/null @@ -1,382 +0,0 @@ -package com.seaofnodes.simple.codegen; - -import com.seaofnodes.simple.*; -import com.seaofnodes.simple.codegen.Encoding.BAOS; -import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.Ary; -import java.io.*; -import java.nio.ByteBuffer; -import java.nio.ByteOrder; -import java.util.HashMap; -import java.util.Map; - -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; - - // bind 1011 - // 00001111 - // 10110000 - - 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 - // default visibility - 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(16); // 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); - Ary<Symbol> _loc = new Ary<>(Symbol.class); - - 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 = _loc.len() + 1; - - super.writeHeader(out); - } - - void push(Symbol s) { - if ((s._info >> 4) != SYM_BIND_LOCAL) { - _symbols.push(s); - } else { - _loc.push(s); - } - } - - @Override - 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); - } - // index is already set - for( Symbol s : _loc ) { - s.writeHeader(out); - } - for( Symbol s : _symbols ) { - s.writeHeader(out); - } - } - - @Override - int size() { - return (1 + _symbols.len() + _loc.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; - } - - /* creates function and stores where it starts*/ - private final HashMap<TypeFunPtr,Symbol> _funcs = new HashMap<>(); - private void encodeFunctions(SymbolSection symbols, DataSection text) { - for( int i=0; i<_code._cfg._len; i++ ) { - if( !(_code._cfg.at(i) instanceof FunNode fun) ) continue; - // skip until the function ends - while( !(_code._cfg.at(i) instanceof ReturnNode ret) ) - i++; - int end = _code._encoding._opStart[ret._nid] + _code._encoding._opLen[ret._nid]; - - if( fun._name==null ) continue; // Anonymous addresses are relocated within .text. - Symbol func = new Symbol(fun._name, text._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); - func._value = _code._encoding._opStart[fun._nid]; - func._size = end - func._value; - symbols.push(func); - _funcs.put(fun.sig(), func); - } - } - - public void export(String fname) throws IOException { - 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); - - // zero flag by default - // 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); - - // Build and write constant pool - BAOS cpool = new BAOS(); - Encoding enc = _code._encoding; - enc.writeConstantPool(cpool,false); - DataSection rdata = new DataSection(".rodata", 1 /* SHT_PROGBITS */, cpool); - rdata._flags = SHF_ALLOC; - pushSection(rdata); - - // populate function symbols - encodeFunctions(symbols, text); - - 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); - } - - // calculate local index - int num = 1; - for( Symbol s : symbols._loc ) - s._index = num++; - // extra space for .rela.text - int start_global = num+1; // Add one to skip the final .rela.text local symbol - 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 : enc._externals.keySet()) { - int nid = n._nid; - String extern = enc._externals.get(n); - - Symbol sym = new Symbol(extern, 0, SYM_BIND_GLOBAL, SYM_TYPE_NOTYPE); - sym._index = start_global++; - symbols.push(sym); - - int offset = enc._opStart[nid] + enc._opLen[nid] - 4; - - // u64 offset - write8(text_rela._contents, offset); - // u64 info - write8(text_rela._contents, ((long)sym._index << 32L) | 4L /* PLT32 */); - // i64 addend - write8(text_rela._contents, -4); - } - - // Write relocations for the constant pool - for( Encoding.Relo relo : enc._bigCons.values() ) { - Symbol glob = new Symbol("CPOOL$"+start_global, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); - glob._value = relo._target; - glob._size = relo._t.size(); - glob._index = start_global++; - symbols.push(glob); - write8(text_rela._contents, relo._opStart+relo._off); - write8(text_rela._contents, ((long)glob._index << 32L) | relo._elf ); - write8(text_rela._contents, -4); - } - - text_rela._flags = SHF_INFO_LINK; - text_rela._link = 2; - text_rela._info = text._index; - pushSection(text_rela); - - // Final .rela.text symbol - Symbol sym = new Symbol(text_rela._name, num++, SYM_BIND_LOCAL, SYM_TYPE_SECTION); - sym._name_pos = text_rela._name_pos; - sym._size = text_rela.size(); - symbols.push(sym); - - // 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); } - for( Symbol s : symbols._loc ) { s._name_pos = writeCString(strtab, s._name); } - - 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; - - File file = new File(fname); - if( file.getParentFile()!=null ) - file.getParentFile().mkdirs(); - BufferedOutputStream bos = new BufferedOutputStream(new FileOutputStream(file)); - bos.write(out.array()); - bos.close(); - } - -} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java new file mode 100644 index 00000000..534bb10f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java @@ -0,0 +1,234 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeMemPtr; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; +import com.seaofnodes.simple.util.Utils; +import java.io.*; +import java.nio.file.Files; +import java.util.HashMap; + +public class ElfReader { + + public final File _file; + public final byte[] _buf; + int _x; // Cursor into buffer + // ELF Header + public final ElfHeader _header; + // All sections + public final Section[] _sections; + // Simple section, if available + public final Section _simple; + // Byte array in/out stream - used as a reader + public final BAOS _bais; + // Compilation unit; written into FunNodes + public final CompUnit _compunit; + + // Strings from the Simple section, either small public set or whole set + public String[] _strs; + // Dependent file names + public String[] _deps; + // Only published symbol this file + public TypeStruct _clz; + // Canonical named types, distinct from optimized same-named graph states. + public TypeStruct[] _pubTypes; + // Nodes read in this Elf + public Ary<Node> _nodes; + + // Load an Elf file (mostly lazily) + public static ElfReader load( File f, CompUnit cu ) { + try { return new ElfReader(f,cu); } + catch( IOException ioe ) { return null; } + } + + // Load the Simple section from the ELF file + private ElfReader( File f, CompUnit cu ) throws IOException { + _file = f; + _compunit = cu; + _buf = Files.readAllBytes(f.toPath()); + _header = new ElfHeader(); + // No attempt is made to parse the program header table. + _sections = new Section[_header._shnum]; + for( int i=0; i<_header._shnum; i++ ) + _sections[i] = new Section(i); + + // Load section names + Section secstr = _sections[_header._shstrndx]; + for( Section sec : _sections ) + if( sec._type != 0 ) + sec._name = secstr.str(sec._noff); + + Section simple = null; + for( Section sec : _sections ) + if( ".simple".equals(sec._name) ) + simple = sec; + _simple = simple; + _bais = new BAOS(_buf, (int)_simple._offset); + } + + // For Serialize self-test + ElfReader( BAOS bais ) { + _file = null; + _compunit = null; + _buf = bais.buf(); + _header = null; + _sections = null; + _simple = null; + _bais = bais; + } + + // Load the public symbols and dependent objs, but not the whole IR + void loadPublicSymbols() { + // Check already loaded and cached + if( _strs == null && _simple != null ) + // Read only the published public strings, for speed purposes when + // scanning a large count of ELF files but getting hits in only a + // few of them. i.e. optimizing (prematurely?) for the traditional + // case of linking a small file against a large library + Serialize.read_public_strs(this); + } + + // Loads the entire IR + public TypeStruct loadSimple(CodeGen code) { + Serialize.readAll(code, this, code._aliases, code._fidxs, code._rpcs); + return _clz; + } + + // Loads strings, mappings, and types, but not Nodes. Used after the + // public-string scan finds a matching Simple ELF, so parsing can resolve + // imported field/array aliases before the full graph is linked in later. + public TypeStruct loadPublicTypes(CodeGen code) { + Serialize.readTypes(code, this, code._aliases, code._fidxs, code._rpcs); + return _clz; + } + + int u1() { return _buf[_x++]&0xFF; } + int magic() { // Big endian + return (u1() << 24) | (u1() << 16) | (u1() << 8) | u1(); + } + int u2() { return u1() | (u1()<<8); } // Little endian + int u4() { // Little endian + return u1() | (u1() << 8) | (u1() << 16) | (u1() << 24); + } + long u8() { return u4() | ((long)u4()<<32); } + void skip(int skip) { _x += skip; } + + + public class ElfHeader { + final int _magic; + final boolean _format32; // Format32 or format64 + final byte _osabi; + final boolean _little; // True if little endian, false if big endian + final char _type; + final char _machine; + final long _entry; // Process entry point + final long _phoff; // Program header table offset, from file start + final long _shoff; // Section header table offset, from file start + final int _flags; // Flags + final int _phnum; // Number of program header entries + final int _shentsize; + final int _shnum; // Number of section header entries + final int _shstrndx; // Section header index contains section names + + + ElfHeader() throws IOException { + _x = 0; + if( (_magic = magic()) != 0x7F454C46 ) bad("magic number",_magic); + byte EI_CLASS = (byte)u1(); + if( EI_CLASS != 1 && EI_CLASS != 2 ) bad("EI_CLASS",EI_CLASS); + _format32 = (EI_CLASS==1); + byte EI_DATA = (byte)u1(); + if( EI_DATA != 1 && EI_DATA != 2 ) bad("EI_DATA",EI_DATA); + _little = EI_DATA == 1; + if( u1() != 1 ) bad("version",1); + if( (_osabi=(byte)u1()) != 0 ) bad("EI_VERSION",_osabi); + byte abiversion = (byte)u1(); + if( abiversion != 0 ) bad("EI_ABIVERSION",abiversion); + skip(7); // Pad + + // Endian matters now + if( !_little ) throw new IOException("TODO: Big endian"); + if( (_type = (char)u2()) != 1 ) bad("ET_REL",_type); + if( (_machine = (char)u2()) != 0x3E ) bad("AMD x86-64",_machine); + int ver = u4(); + if( ver != 1 ) bad("Version",ver); + // Format32 matters now + if( _format32 ) bad("Format",1); + _entry = u8(); // Process entry point + _phoff = u8(); // Program header table offset + _shoff = u8(); // Section header table offset + _flags = u4(); // Flags + int ehsize = u2(); + if( ehsize != 0x40 ) bad("EHSIZE",ehsize); + int phentsize = u2(); + if( phentsize != 0x38 && phentsize != 0 ) bad("PHENTSIZE",phentsize); + _phnum = u2(); + _shentsize = u2(); + if( _shentsize != 0x40 ) bad("SHENTSIZE",_shentsize); + _shnum = u2(); + // String section + _shstrndx = u2(); + assert _x == ehsize; + } + } + + public class Section { + final int _noff; // Offset in string section for name + final int _type; // Section type + final long _flags; + final long _addr; // Offset in virtual mem, if loaded + final long _offset; // Offset in file + final long _size; // Size in bytes + final int _link; // Associated section index, varies + final int _info; // Varies + final byte _align; // Log2 alignment + final int _esize; // Element size, if non-zero + String _name; + + Section(int sidx) throws IOException { + _x = (int)(_header._shoff + (sidx * _header._shentsize)); + _noff = u4(); + _type = u4(); + _flags = u8(); + _addr = u8(); + _offset= u8(); + _size = u8(); + _link = u4(); + _info = u4(); + long align = u8(); + if( align==0 ) align=1; + _align = (byte)Long.numberOfTrailingZeros(align); + if( (1L << _align ) != align ) + throw new IOException("Bad section alignment: "+align); + _esize = (int)u8(); + } + + String str(int off) { + assert _type == 3/*SHT_STRTAB*/; // String table section header + int start = (int)(_offset+off); + int x = start; + while( _buf[x++] !=0 ) ; + return new String(_buf,start,x-start-1); + } + } + + private static void bad(String msg, int val) throws IOException { + throw new IOException("Bad "+msg+": "+val); + } + + + + //public TypeMemPtr lookup( String name ) { + // if( _simple == null ) return null; + // BAOS baos = new BAOS(_buf, (int)_simple._offset); + // Ary<String> strs = Serialize.read_strs(baos); + // + // + // + // Ary<Node> nodes = Serialize.read_types(baos); + // + // throw Utils.TODO("Elf load symbol "+name); + //} +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java new file mode 100644 index 00000000..1b6281b8 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -0,0 +1,431 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; +import java.io.*; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; +import java.util.HashMap; + +public class ElfWriter { + + final CodeGen _code; + Ary<Section> _sections; + StringSection _strtab; + + ElfWriter( CodeGen code ) { + _code = code; + } + + // ------------------------------------------------------------------------ + abstract public class Section { + static final int SHT_NULL = 0; + static final int SHT_PROGBITS= 1; + static final int SHT_SYMTAB = 2; + static final int SHT_STRTAB = 3; + static final int SHT_RELA = 4; + static final int SHT_SIMPLE = 10; // Simple section + + final String _name; + final int _type, _entsize, _index, _name_pos, _flags; + int _link, _info; + int _file_offset; + + Section(String name, int type, int entsize, int flags) { + _name = name; + _type = type; + _entsize = entsize; + _flags = flags; + _index = _sections._len; + _sections.push(this); + _name_pos = name.isEmpty() + ? 0 // Null section + : _strtab == null + ? 1 // StringSection + // All the other sections + : _strtab.writeCString(name); + } + + 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(16); // addralign + out.putLong(_entsize); // Fixed-size element size + } + + abstract void write(ByteBuffer out); + abstract int size(); + } + + // ------------------------------------------------------------------------ + // Generic data sections; carries about a BAOS for bits + public class DataSection extends Section { + static final int SHF_WRITE = 1; + static final int SHF_ALLOC = 2; + static final int SHF_EXECINSTR = 4; + static final int SHF_INFO_LINK = 64; + + final BAOS _contents; + + DataSection( String name, int type, int flags, int entsize ) { this(name, type, flags, entsize, new BAOS() ); } + DataSection( String name, int type, BAOS contents, int flags ) { this(name, type, flags, 0, contents ); } + private DataSection( String name, int type, int flags, int entsize, BAOS contents ) { + super(name, type, entsize, flags); + _contents = contents; + } + + @Override void write(ByteBuffer out) { out.put(_contents.toByteArray()); } + @Override int size() { return _contents.size(); } + public void write2( int op ) { + _contents.write(op ); + _contents.write(op>> 8); + } + public void write4( int op ) { + _contents.write(op ); + _contents.write(op>> 8); + _contents.write(op>>16); + _contents.write(op>>24); + } + public void write8( long i64 ) { + write4( (int) i64 ); + write4( (int)(i64>>32)); + } + + } + + // ------------------------------------------------------------------------ + // Section to collect and de-dup strings + public class StringSection extends DataSection { + final HashMap<String,Integer> _dedup = new HashMap<>(); + + StringSection() { + super(".strtab",SHT_STRTAB, 0, 0 ); + int emptyoff = writeCString(""); // Always empty string at offset 0 + assert emptyoff == 0; + int namepos = writeCString(".strtab"); + assert namepos == _name_pos; + } + + public int writeCString(String name) { + if( name==null ) return 0; // Anonymous functions have no name + Integer ii = _dedup.get(name); + if( ii != null ) return ii; + // place name in the string table + int pos = _contents.size(); + _dedup.put(name,pos); + byte[] name_bytes = name.getBytes(); + _contents.write(name_bytes); + // the strings are null terminated + _contents.write(0); + return pos; + } + } + + // ------------------------------------------------------------------------ + // The relocations; 3 words per relocation + public class ReloSection extends DataSection { + ReloSection( int info ) { + 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(addend); + } + } + + + // ------------------------------------------------------------------------ + // Symbols section; emit the symbols into the data section directly + public class SymbolSection extends DataSection { + public static final int SYMBOL_SIZE = 4+1+1+2+8+8; + final BAOS _globals; + final int _nlocals; + + SymbolSection(int nlocals) { + super(".symtab", SHT_SYMTAB, 0/*flags*/, SYMBOL_SIZE); + _globals = new BAOS(); + _nlocals = nlocals; + } + + // Global symbol index + int gidx() { return _nlocals+(_globals.size()/SYMBOL_SIZE); } + + public int symbol( String name, int shndx, int bind, int type, long value, long size ) { + int gidx = gidx(); // Global index before I write to _globals + BAOS baos = bind==SYM_BIND_GLOBAL ? _globals : _contents; + write4(baos,_strtab.writeCString(name)); + int info = (bind << 4) | (type & 0xF); + baos.write(info); + baos.write(0); // other/visibility + write2(baos,shndx); // section index + write8(baos,value); + write8(baos,size); + return bind==SYM_BIND_GLOBAL ? gidx : -99; + } + + public int symbol( String name, int shndx, int bind, int type ) { + return symbol(name,shndx,bind,type,0,0); + } + + // creates function and stores where it starts. + // Filters to just this class.obj file. + void encodeFunctions(StopNode stop, Encoding enc, int text_idx, boolean emitEntrySymbol) { + for( Node stopcu : stop._inputs ) { + for( Node ret : stopcu._inputs ) { + FunNode fun = ((ReturnNode)ret).fun(); + if( !_code.owns(fun) ) + continue; + int end = enc.opStart(fun.ret()) + enc.opLen(fun.ret()); + long value = enc.opStart(fun); + long size = end - value; + if( fun._name != null ) { // Anonymous functions have no name + // The C runtime owns `main` and adapts argc/argv into + // a normal Simple array. Keep the Simple function on + // its native ABI under a private entry symbol. + String name = emitEntrySymbol && "main".equals(fun._name) + ? "simple_main" + : fun._name; + symbol(name, text_idx, SYM_BIND_GLOBAL, SYM_TYPE_FUNC, value, size); + } + } + } + } + + // Insert a default-main for top-level compilations, if the top-level + // does not declare a main. + void symbolEntryClinit(int text_idx, Encoding enc) { + FunNode clinit = null; + String entryName = _code.entryClinitName(); + for( FunNode fun : _code._linker ) + if( fun != null && _code.owns(fun) ) { + if( "main".equals(fun._name) ) + return; // encodeFunctions exported this as simple_main + if( entryName.equals(fun._name) ) + clinit = fun; // Keep top-level entry, if we don't find an explicit main + } + // No top-level main, so the top-level clinit becomes a default main + if( clinit != null ) { + assert enc.opStart(clinit) == 0; + symbol("simple_main",text_idx, SYM_BIND_GLOBAL, SYM_TYPE_FUNC, enc.opStart(clinit), 0); + return; + } + throw new IllegalStateException("Missing entry <clinit> "+entryName); + } + + static void write2( BAOS bits, int op ) { + bits.write(op ); + bits.write(op>> 8); + } + static void write4( BAOS bits, int op ) { + bits.write(op ); + bits.write(op>> 8); + bits.write(op>>16); + bits.write(op>>24); + } + static void write8( BAOS bits, long i64 ) { + write4(bits, (int) i64 ); + write4(bits, (int)(i64>>32)); + } + + @Override + void writeHeader(ByteBuffer out) { + // points to string table section + _link = _strtab._index; + _info = _nlocals; + super.writeHeader(out); + } + + @Override void write(ByteBuffer out) { + out.put(_contents.toByteArray()); + out.put(_globals .toByteArray()); + } + @Override int size() { + return _contents.size() + _globals.size(); + } + } + + public static final int SYM_BIND_LOCAL = 0; + public static final int SYM_BIND_GLOBAL = 1; + + 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 final int SECTION_HDR_SIZE = 64; + + // ------------------------------------------------------------------------ + public class SimpleSection extends DataSection { + SimpleSection(BAOS serial) { super(".simple", SHT_SIMPLE, serial, 0); } + } + + + // ------------------------------------------------------------------------ + + public ElfWriter export(boolean emitEntrySymbol) { + // Sections are created in the order they are emitted. + _sections = new Ary<>(Section.class); + + // Null section + Section nullSection = new DataSection("",Section.SHT_NULL,0,0); + + // String section next; written out early and available to record/dedup + // strings for all remaining sections + _strtab = new StringSection(); + + // place all the symbols + 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 + Encoding enc = _code._encoding; + DataSection text = new DataSection(".text" , Section.SHT_PROGBITS, enc._bits , DataSection.SHF_ALLOC | DataSection.SHF_WRITE | DataSection.SHF_EXECINSTR ); + // Constant pool + DataSection rodata = new DataSection(".rodata", Section.SHT_PROGBITS, enc._cpool, DataSection.SHF_ALLOC ); + // Static/global pool + DataSection rwdata = new DataSection(".data" , Section.SHT_PROGBITS, enc._sdata, DataSection.SHF_ALLOC | DataSection.SHF_WRITE ); + + + // populate function symbols + symbols.encodeFunctions(_code._stop, _code._encoding, text._index, emitEntrySymbol); + // Export the source compilation unit <clinit> as the C runtime "main". + // Encoding keeps this function at text offset zero. + if( emitEntrySymbol ) + symbols.symbolEntryClinit(text._index,enc); + + // create external .text relocations + ReloSection relocations = new ReloSection(text._index); + + for( Node n : enc._externals.keySet()) { + String extern = enc._externals.get(n); + int symidx = symbols.symbol(extern, 0, SYM_BIND_GLOBAL, SYM_TYPE_NOTYPE); + int offset = enc.opStart(n) + enc.opLen(n) - 4; + relocations.writeReloOffPlus(offset, symidx, (byte)4/*PLT32*/); + } + + // Native ELF output is AMD64. Data addresses use PC32, not PLT calls. + for( Node n : enc._externData.keySet() ) { + String extern = enc._externData.get(n); + int symidx = symbols.symbol(extern, 0, SYM_BIND_GLOBAL, SYM_TYPE_OBJECT); + int offset = enc.opStart(n) + enc.opLen(n) - 4; + relocations.writeReloOffPlus(offset, symidx, (byte)2/*PC32*/); + } + + // 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() ) { + 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 + SimpleSection simple = new SimpleSection(_code._serial); + + // Write the local section header symbols + assert nlocals == 1+_sections._len; + symbols.symbol("",0,0,0); // Null symbol at index 0 + for( Section s : _sections ) + symbols.symbol(s._name, s._index, SYM_BIND_LOCAL, SYM_TYPE_SECTION, 0, s.size()); + + int size = 64; // ELF header size + // 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; + size += SECTION_HDR_SIZE*_sections.len(); + + 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) _sections.len()); // shnum + out.putShort((short) _strtab._index); // shstrndx + + // raw section data + for( Section s : _sections ) + s.write(out); + + // Section headers + for( Section s : _sections ) + s.writeHeader(out); + + assert out.position() == size; + + String objName = _code._buildDir + "/" + _code._srcName + ".o"; + File file = new File(objName); + if( file.getParentFile()!=null ) + file.getParentFile().mkdirs(); + try { + BufferedOutputStream bos = new BufferedOutputStream(new FileOutputStream(file)); + bos.write(out.array()); + bos.close(); + } catch( IOException ioe ) { + // Caller does not want to deal, but it is a failed compilation in any case + throw new RuntimeException(ioe); + } + // Reset for next ELF + _sections = null; + _strtab = null; + return this; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index b5a8e148..8e9b99db 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -1,12 +1,10 @@ package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.IRPrinter; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.Ary; -import com.seaofnodes.simple.util.SB; -import com.seaofnodes.simple.util.Utils; -import java.io.ByteArrayOutputStream; +import com.seaofnodes.simple.util.*; import java.util.*; @@ -24,11 +22,14 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // Top-level program graph structure public final CodeGen _code; + // CFG Nodes in RPO order, per-encoding. + public Ary<CFGNode> _cfg; + // Instruction bytes. The registers are encoded already. Relocatable data // is in a fixed format depending on the kind of relocation. // - RIP-relative offsets into the same chunk are just encoded with their - // check relative offsets; no relocation info is required. + // chunk relative offsets; no relocation info is required. // - Fixed address targets in the same encoding will be correct for a zero // base; moving the entire encoding requires adding the new base address. @@ -36,17 +37,12 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // - RIP-relative to external chunks have a zero offset; the matching // relocation info will be used to patch the correct value. - public static class BAOS extends ByteArrayOutputStream { - public byte[] buf() { return buf; } - void set( byte[] buf0, int count0 ) { buf=buf0; count=count0; } - }; - final public BAOS _bits = new BAOS(); - - public int [] _opStart; // Start of opcodes, by _nid - public byte[] _opLen; // Length of opcodes, by _nid - - // Function headers now padded when printing - public boolean _padFunHeads; + public final BAOS _bits = new BAOS(); // Instructions / encodings + 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 { @@ -56,17 +52,28 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { public final int _structSize; // Capture layout during encoding, not printing public final byte _off; // Offset from start of opcode public final byte _elf; // ELF relocation type, e.g. 2/PC32 - public int _target; // Where constant is finally placed - public int _opStart; // Opcode start + public int _target; // Where constant is finally placed + public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; _align = t.alignment(); _structSize = t instanceof TypeStruct ts ? ts.size() : 0; + _readOnly = readOnly(t); + } + public boolean readOnly() { return _readOnly; } + private final boolean _readOnly; + private static boolean readOnly(Type t) { + // Class initializers still write their fields, even when every + // final value is constant. Their storage must remain writable. + return !(t instanceof TypeStruct ts) || + (!Parser.startsClzPrefix(ts._name) && ts.isConstant()); } } - public final HashMap<Node,Relo> _bigCons = new HashMap<>(); - Encoding( CodeGen code ) { _code = code; } + Encoding( CodeGen code ) { + _code = code; + _data = new StaticData(this); + } // Shortcut to the defining register public short reg(Node n) { @@ -107,14 +114,6 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { } // 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); @@ -127,48 +126,91 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { public Encoding add4( int op ) { addN(2,op,_bits); return this; } public Encoding add8(long op ) { addN(3,op,_bits); return this; } + private final static int SENTINEL = -1; + private final IntHashMap _opStart = new IntHashMap(SENTINEL); + private final IntHashMap _opLen = new IntHashMap(SENTINEL); + + + // Read op start for n + public int opStart(Node n) { return _opStart.get(n._nid); } + // Read op length for n + public byte opLen (Node n) { return (byte)_opLen.get(n._nid); } + + // Set op start for n + public void opStart(Node n, int off) { + assert off != SENTINEL; + _opStart.put(n._nid,off); + } + + // Set op start for n + public void opStartAdd(Node n, int off) { + if( off==0 ) return; + int old = _opStart.get(n._nid); + assert old != SENTINEL && old+off != SENTINEL; + _opStart.put(n._nid,old+off); + } + + // Set op length for n + public void opLen(Node n, byte len) { + assert len != SENTINEL; + _opLen.put(n._nid,len); + } // Nodes need "relocation" patching; things done after code is placed. // Record src and dst Nodes. private final HashMap<Node,CFGNode> _internals = new HashMap<>(); // Source is a Call, destination in the Fun. public Encoding relo( CallNode call ) { - _internals.put(call,_code.link(call.tfp())); + FunNode fun = _code.link(call.tfp()); + if( fun != null && !_code.owns(fun) ) + _externals.put(call,fun._name); + else + _internals.put(call,fun); return this; } - public Encoding relo( ConstantNode con ) { - TypeFunPtr tfp = (TypeFunPtr)con._con; - _internals.put(con,_code.link(tfp)); + // Code address as a constant + public Encoding relo( FunPtrNode fptr ) { + TypeFunPtr tfp = (TypeFunPtr)fptr._type; + FunNode fun = _code.link(tfp); + if( fun != null && !_code.owns(fun) ) + _externals.put(fptr,fun._name); + else + _internals.put(fptr,fun); return this; } + // Local jump public void jump( CFGNode jmp, CFGNode dst ) { _internals.put(jmp,dst.uctrlSkipEmpty()); } - - final HashMap<Node,String> _externals = new HashMap<>(); + // External references only located by Strings a link-time + public final HashMap<Node,String> _externals = new HashMap<>(); public Encoding external( Node n, String extern ) { _externals.put(n,extern); return this; } + public final HashMap<Node,String> _externData = new HashMap<>(); + public void externalData(Node n, String name) { _externData.put(n,name); } + // Store t as a 32/64 bit constant in the code space; generate RIP-relative - // addressing to load it + // addressing to load it. Type is stored in either the .rodata or .data. public void largeConstant( Node relo, Type t, int off, int elf ) { - assert t.isConstant(); + // TODO: Any-old struct in the cpool + assert t.isConstant() || (t instanceof TypeStruct ts && Parser.startsClzPrefix(ts._name)); assert (byte)off == off; assert (byte)elf == elf; _bigCons.put(relo,new Relo(relo,t,(byte)off,(byte)elf)); } // -------------------------------------------------- - void encode() { + Encoding encode( ) { // Basic block layout: negate branches to keep blocks in-order; insert // unconditional jumps. Attempt to keep backwards branches taken, // forwards not-taken (this is the default prediction on most // hardware). Layout is still Reverse Post Order but with more // restrictions. - basicBlockLayout(); + basicBlockLayout( ); // Write encoding bits in order into a big byte array. // Record opcode start and length. @@ -178,8 +220,13 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // encodings and compact the code, changing all the offsets. compactShortForm(); + // Place pool objects and record relocations within their contents. + _data.write(); + // Patch RIP-relative and local encodings now. patchLocalRelocations(); + + return this; } // -------------------------------------------------- @@ -187,29 +234,48 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // unconditional jumps. Attempt to keep backwards branches taken, forwards // not-taken (this is the default prediction on most hardware). Layout is // still Reverse Post Order but with more restrictions. - private void basicBlockLayout() { + private void basicBlockLayout( ) { IdentityHashMap<LoopNode,Ary<CFGNode>> rpos = new IdentityHashMap<>(); - Ary<CFGNode> rpo = new Ary<>(CFGNode.class); - rpos.put(_code._start.loop(),rpo); + _cfg = new Ary<>(CFGNode.class); + rpos.put(_code._start.loop(),_cfg); BitSet visit = _code.visit(); - rpo.add(_code._stop); - FunNode main = _code.link(_code._main); - for( Node n : _code._start._outputs ) - if( n instanceof FunNode fun && fun != main ) { - int x = rpo._len; - _rpo_cfg(fun, visit, rpos ); - assert rpo.at(x) instanceof ReturnNode; + + // Do them all except the <clinit>s + Ary<FunNode> clinits = new Ary<>(FunNode.class); + FunNode entry = null; + String entryName = _code.entryClinitName(); + for( FunNode fun : _code._linker ) { + if( fun != null && !fun.isDead() && _code.owns(fun) ) { + if( fun.isClz() ) { + if( fun._name.equals(entryName) ) + entry = fun; + else + clinits.add(fun); + } else { + int x = _cfg._len; + _rpo_cfg(fun,visit,rpos); + assert _cfg.at(x) instanceof ReturnNode; + } } - // Do any main function last... so it lands at offset 0 in the RPO - if( main!=null ) - _rpo_cfg(main, visit, rpos ); - rpo.add(_code._start); + } + // Now the <clinit>s last, so when reversed they become first. The + // program entry <clinit> is last of all, so it lands at offset zero. + for( FunNode clinit : clinits ) { + int x = _cfg._len; + _rpo_cfg(clinit,visit,rpos); + assert _cfg.at(x) instanceof ReturnNode; + } + if( entry != null ) { + int x = _cfg._len; + _rpo_cfg(entry,visit,rpos); + assert _cfg.at(x) instanceof ReturnNode; + } + // Reverse in-place - for( int i=0; i< rpo.size()>>1; i++ ) - rpo.swap(i,rpo.size()-1-i); + for( int i=0; i< _cfg.size()>>1; i++ ) + _cfg.swap(i,_cfg.size()-1-i); visit.clear(); - _code._cfg = rpo; // Save the new ordering } @@ -283,7 +349,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { private static boolean shouldInvert(CFGNode t, CFGNode f, int bld) { int tld = t.loopDepth(), fld = f.loopDepth(); // These next two are symmetric and can happen in any order; if `tld < - // bld` is true, the `fld < bld` must be false, or else both directions + // bld` is true, then `fld < bld` must be false, or else both directions // exit the loop... and the IF test would not be in the loop. // true to exit a loop usually (and false falls into Yet Another Loop @@ -328,24 +394,26 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // -------------------------------------------------- // Write encoding bits in order into a big byte array. // Record opcode start and length. - public FunNode _fun; // Currently encoding function + + // Current function is used by the spill-op encodings to query the stack + // frame layout and get the spill offsets. private void writeEncodings() { - _opStart= new int [_code.UID()]; - _opLen = new byte[_code.UID()]; - for( CFGNode bb : _code._cfg ) { + for( CFGNode bb : _cfg ) { if( !(bb instanceof MachNode mach0) ) - _opStart[bb._nid] = _bits.size(); - else if( bb instanceof FunNode fun ) { - _fun = fun; // Currently encoding function - _opStart[bb._nid] = _bits.size(); + opStart(bb, _bits.size()); + else if( bb instanceof FunNode ) { + opStart(bb, _bits.size()); mach0.encoding( this ); - _opLen[bb._nid] = (byte) (_bits.size() - _opStart[bb._nid]); + opLen(bb, (byte) (_bits.size() - opStart(bb))); } for( Node n : bb._outputs ) { - if( n instanceof MachNode mach && !(n instanceof FunNode) ) { - _opStart[n._nid] = _bits.size(); + if( n instanceof MachNode mach && !(n instanceof FunNode) && + // FunPtrs are encoding in the block of their control, not + // the block of the ReturnNode input - which is also a CFG. + !(n instanceof FunPtrNode && bb instanceof ReturnNode) ) { + opStart(n, _bits.size()); mach.encoding( this ); - _opLen[n._nid] = (byte) (_bits.size() - _opStart[n._nid]); + opLen(n, (byte) (_bits.size() - opStart(n))); } } } @@ -355,10 +423,10 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // Short-form RIP-relative support: replace short encodings with long // encodings and expand the code, changing all the offsets. private void compactShortForm() { - int len = _code._cfg._len; + int len = _cfg._len; int[] oldStarts = new int[len]; for( int i=0; i<len; i++ ) - oldStarts[i] = _opStart[_code._cfg.at(i)._nid]; + oldStarts[i] = opStart(_cfg.at(i)); // TODO: Rewrite this algo to use the small "_jmps" list of just the // jumps instead of walking all blocks. @@ -372,24 +440,27 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { while( slide != 0) { // While no fails slide = 0; for( int i=0; i<len; i++ ) { - CFGNode bb = _code._cfg.at(i); - _opStart[bb._nid] += slide; + CFGNode bb = _cfg.at(i); + opStartAdd(bb, slide); // Slide down all other (non-CFG) ops in the block for( Node n : bb._outputs ) - if( n instanceof MachNode && !(n instanceof CFGNode) ) - _opStart[n._nid] += slide; + if( n instanceof MachNode && !(n instanceof CFGNode) && + // Match writeEncodings(): FunPtrs are encoded in the + // block of their control, not again at the Return. + !(n instanceof FunPtrNode && bb instanceof ReturnNode) ) + opStartAdd(n, slide); if( bb instanceof RIPRelSize riprel ) { CFGNode target = (bb instanceof IfNode iff ? iff.cproj(0) : (CFGNode)bb.out(0)).uctrlSkipEmpty(); // Delta is from opStart to opStart. X86 at least counts // the delta from the opEnd, but we don't have the end until // we decide the size - so the encSize has to deal - int delta = _opStart[target._nid] - _opStart[bb._nid]; + int delta = opStart(target) - opStart(bb); byte opLen = riprel.encSize(delta); // Recorded size is smaller than the current size? - if( _opLen[bb._nid] < opLen ) { + if( opLen(bb) < opLen ) { // Start sliding the code down; record slide amount and new size - slide += opLen - _opLen[bb._nid]; - _opLen[bb._nid] = opLen; + slide += opLen - opLen(bb); + opLen(bb, opLen); } } } @@ -400,21 +471,21 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // short-jumps span function headers, the padding will not make any // short jumps fail. for( int i=0; i<len; i++ ) { - CFGNode bb = _code._cfg.at(i); + CFGNode bb = _cfg.at(i); // Functions pad to align 16 if( bb instanceof FunNode ) { - int newStart = _opStart[bb._nid]+slide; + int newStart = opStart(bb)+slide; slide += (newStart+15 & -16)-newStart; } - _opStart[bb._nid] += slide; + opStartAdd(bb, slide); for( Node n : bb._outputs ) - if( n instanceof MachNode && !(n instanceof CFGNode) ) - _opStart[n._nid] += slide; + if( n instanceof MachNode && !(n instanceof CFGNode) && + !(n instanceof FunPtrNode && bb instanceof ReturnNode) ) + opStartAdd(n, slide); } - _padFunHeads = true; // Copy/slide the bits to make space for all the longer branches - int grow = _opStart[_code._cfg.at(len-1)._nid] - oldStarts[len-1]; + int grow = opStart(_cfg.at(len-1)) - oldStarts[len-1]; if( grow > 0 ) { // If no short-form ops, nothing to do here int end = _bits.size(); byte[] bits = new byte[end+grow]; @@ -422,7 +493,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { int start = oldStarts[i]; if( start==0 && i>1 ) continue; int oldStart = oldStarts[i]; - int newStart = _opStart[_code._cfg.at(i)._nid]; + int newStart = opStart(_cfg.at(i)); System.arraycopy(_bits.buf(),oldStart,bits,newStart,end-start); end = start; } @@ -437,103 +508,59 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { void patchLocalRelocations() { // Walk the local code-address relocations for( Node src : _internals.keySet() ) { - int start = _opStart[src._nid]; + int start = opStart(src); Node dst = _internals.get(src); - int target = _opStart[dst._nid]; - ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start); + // If function is entirely dead, only the function pointer remains + // and, it can only be used to test against zero or equals to + // another function pointer... i.e., there Is No Code Here. + int target = dst == null ? start : opStart(dst); + ((RIPRelSize)src).patch(this, start, opLen(src), target - start); } } - // -------------------------------------------------- - // Write the constant pool into the BAOS and optionally patch locally - void writeConstantPool( BAOS bits, boolean patch ) { - 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); - 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 = 4; 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 -> cpool(align,bits,tt); - case TypeStruct ts -> cpool(bits,ts); - // Simple primitive (e.g. larger int, float) - default -> addN(align,relo._t,bits); - } - } - // Record target address and opcode start - relo._target = target; - relo._opStart= _opStart[relo._op._nid]; - // Go ahead and locally patch in-memory - if( patch ) - ((RIPRelSize)relo._op).patch(this, relo._opStart, _opLen[relo._op._nid], relo._target - relo._opStart); - } - } - } - - // Constant tuples put all entries at same alignment - private void cpool(int align, BAOS bits, TypeTuple tt) { - for( Type tx : tt._types ) - addN(align,tx,bits); - } - - // Structs use internal field layout - private void cpool( 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]]; - 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,bits); - off += 1<<log; - } - } + // Emit a single scalar as bits + static void addN( int log, Type t, BAOS bits ) { + long x = switch( t ) { + case TypeInteger ti -> ti.value(); + case TypeFloat tf -> log==3 + ? Double.doubleToRawLongBits( tf.value()) + : Float.floatToRawIntBits((float)tf.value()); + case TypeFunPtr tfp -> 0; // These need to be relocated + case TypeMemPtr tmp -> 0; // These need to be relocated + default -> { if( t==Type.NIL ) yield 0; else throw Utils.TODO(); } + }; + addN(log,x,bits); } - // 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); + Integer target = _code._externDataAddresses.get(name); + if( target==null ) throw new IllegalArgumentException("Unresolved C data symbol '"+name+"'"); + int start = opStart(src); + ((RIPRelSize)src).patch(this,start,opLen(src),target-start); + } for( Node src : _externals.keySet() ) { - int start = _opStart[src._nid]; + 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(); - }; - ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start); + int target = externalAddress(dst); + ((RIPRelSize)src).patch(this, start, opLen(src), target - start); } } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java new file mode 100644 index 00000000..bc9c9d39 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java @@ -0,0 +1,177 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.util.*; +import java.util.HashMap; +import java.util.Arrays; +import java.util.Objects; + + +// This utility 2-way maps some *global* program feature to a local dense +// index, suitable for packing in BitSets. The mapping takes a global value - +// always a {source file/class} name and an order number counting up per +// feature in the same file. The dense local index can be different in +// different compilations. + +// The global info allows loading the same remote class info from different +// paths and aligning them. Example: Compiling A loads pre-compiled B and C, +// both of which load pre-compiled D. The 2 different D loads unify via this +// global info. + +// These mappings are all trivial identities when compiling one file; they +// only become complex when loading seperately compiled code. + +public class GlobalBits { + public static final int RESERVED = 2; + private final HashMap<String,int[]> _clzOrder2Local = new HashMap<>(); + private final Ary<String> _local2Clz = new Ary<>(String.class); + private final AryInt _local2Order = new AryInt(); + // Local dense index + private int _local; + + GlobalBits() { + _local = RESERVED; + // Reserved null-class bits are global identities and are never + // remapped. + int[] xs = new int[RESERVED]; + xs[0] = RESERVED; // Per-class next order counter + for( int i=0; i<RESERVED; i++ ) { + if( i > 0 ) xs[i] = i; + _local2Clz .setX(i,null); + _local2Order.setX(i,i); + } + _clzOrder2Local.put(null,xs); + } + + // Get a next local index for this clz + int next( String clz ) { return next(clz,-1); } + + // Given a clz and order, return an existing local index or make a new + // mapping and return that. + int next(String clz, int order ) { + // Get the per-clz Order->Local mapping + int[] xs = _clzOrder2Local.get(clz); + if( xs == null ) + xs = new int[]{RESERVED,1}; // Make, if it does not exist + // Caller does not have an order in mind, just take the next one stored + // in xs[0] + if( order == -1 ) + order = xs[0]++; + // Order exists from prior compilation, but not recorded locally + else if( order >= xs[0] ) + xs[0] = order+1; + // Grow as needed + while( xs.length <= order ) + xs = Arrays.copyOf(xs,xs.length*2); + // Have a local mapping already? + if( xs[order] != 0 ) + return xs[order]; + int local = _local++; + bind(local,clz,order); + return local; // The dense local index + } + + // Bind a specific dense local index to {clz,order}. Used by both fresh + // allocation and deserialization, where local indexes must not compact + // across holes because XInt bitsets are serialized against this space. + private void bind( int local, String clz, int order ) { + if( _local <= local ) + _local = local+1; + _local2Clz .setX(local,clz ); + _local2Order.setX(local,order); + + // Inline-only fidx holes are represented as {null,0}. They need the + // reverse mapping above, but no forward map because xs[0] is the + // per-class next-order counter. + if( clz==null && order==0 ) + return; + + int[] xs = _clzOrder2Local.get(clz); + if( xs == null ) + xs = new int[]{RESERVED,1}; + if( order >= xs[0] ) + xs[0] = order+1; + while( xs.length <= order ) + xs = Arrays.copyOf(xs,xs.length*2); + _clzOrder2Local.put(clz,xs); + xs[order] = local; + } + + // A file-local function that will inline, and never write to disk + public int nextInline( ) { + int local = _local++; + _local2Clz .setX(local,null); + _local2Order.setX(local,0); + return local; + } + // Get a next local index for the same clz as this old index + public int next( int old ) { return next(_local2Clz.at(old)); } + + // Map a file-local dense index to this compilation unit's local dense index. + public int map( GlobalBits fileBits, int fileLocal ) { + if( fileLocal >= fileBits._local2Clz.size() ) + throw new ArrayIndexOutOfBoundsException(""+fileLocal+" >= "+fileBits._local2Clz.size()); + return findOrNext(fileBits._local2Clz.at(fileLocal), fileBits._local2Order.at(fileLocal)); + } + + // Map a global {clz,order} to a local one; keep any existing mapping or + // make a new one as needed. + private int findOrNext(String clz, int order ) { + // Reserved null-class identities are not represented in xs[order], + // because xs[0] is the next-order counter. + if( clz==null && order < _local2Clz.size() && _local2Order.at(order)==order && _local2Clz.at(order)==null ) + return order; + int[] xs = _clzOrder2Local.get(clz); + if( xs != null && order < xs.length ) { + int local = xs[order]; + if( local < _local2Clz.size() && _local2Order.at(local)==order && Objects.equals(_local2Clz.at(local),clz) ) + return local; + } + 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. + baos.packed2(_local2Clz.size()); + for( int i=RESERVED; i<_local2Clz.size(); i++ ) { + String clz = _local2Clz.at(i); + baos.packed2(clz==null ? 0 : strs.get(clz)); + baos.packed2( _local2Order.at(i) ); + } + } + + void gather( HashMap<String,Integer> strs ) { + for( int i=RESERVED; i<_local2Clz.size(); i++ ) + Serialize.gather(strs,_local2Clz.at(i)); + } + + // Read in the BAIS bits needed to make a file-local -> global mapping + static GlobalBits packed( BAOS bais, String[] strs ) { + var gb = new GlobalBits(); + int n = bais.packed2(); + for( int i=RESERVED; i<n; i++ ) { + int sx = bais.packed2(); + String clz = strs[sx]; + if( clz.isEmpty() ) clz = null; + int order = bais.packed2(); + gb.bind(i,clz,order); + } + return gb; + } + + @Override public String toString() { + SB sb = new SB().p('['); + for( int i=0; i<_local2Clz.size(); i++ ) { + if( i > 0 ) sb.p(','); + sb.p(i).p(" <-> ").p(_local2Clz.at(i)).p('#').p(_local2Order.at(i)); + } + return sb.p(']').toString(); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 80d5d9bb..8eebc15b 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -27,16 +27,15 @@ public abstract class GlobalCodeMotion { breakUpGlobalConstants(code._start); code._visit.clear(); - schedLate (code); + schedLate(code); } // Post-Order of CFG private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary<CFGNode> rpo) { if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) return; // Been there, done that - if( def instanceof ReturnNode && use instanceof CallEndNode ) - return; - assert !( def instanceof CallNode && use instanceof FunNode ); // All calls unwired now + assert !( def instanceof ReturnNode && use instanceof CallEndNode ); // All calls unwired now + assert !( def instanceof CallNode && use instanceof FunNode ); // All calls unwired now visit.set(cfg._nid); for( Node useuse : cfg._outputs ) _rpo_cfg(cfg,useuse,visit,rpo); @@ -50,7 +49,7 @@ public abstract class GlobalCodeMotion { var cons = new ArrayList<Node>(); for( Node con : start._outputs ) if( con!=null && !(con instanceof CFGNode) && - (con.isConst() || (con instanceof MachNode mach && mach.outregmap()!=null)) ) { + (con.isConst() || con instanceof MachNode mach && mach.outregmap()!=null) ) { globals.put(con,true); cons.add(con.keep()); // Preserve original inputs while rewiring users. } @@ -61,6 +60,7 @@ public abstract class GlobalCodeMotion { if( use==null || globals.containsKey(use) ) continue; FunNode fun = useFun(use); if( fun==null ) continue; // Global metadata has no function owner. + assert CodeGen.CODE.owns(fun); var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); Node copy = cloneGlobal(con,fun,globals,local); for( int i=0; i<use.nIns(); i++ ) @@ -207,7 +207,6 @@ public abstract class GlobalCodeMotion { if( n instanceof MemOpNode load && load._isLoad ) lca = find_anti_dep(lca,load,early,late,anti); - // Walk up from the LCA to the early, looking for best place. This is // the lowest execution frequency, approximated by least loop depth and // deepest control flow. @@ -224,7 +223,8 @@ public abstract class GlobalCodeMotion { // Block of use. Normally from late[] schedule, except for Phis, which go // to the matching Region input. private static CFGNode use_block(Node n, Node use, CFGNode[] late) { - if( use instanceof ParmNode ) return late[use._nid]; + if( use instanceof ParmNode parm ) + return late[use._nid]; if( !(use instanceof PhiNode phi) ) return late[use._nid]; CFGNode found=null; @@ -245,7 +245,7 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } - // An allocation may consume a load's memory through a partial aggregate. + // A writer may consume a load's memory through an aggregate. private static void wakeLoads(Node def, CFGNode[] late, WorkList<Node> work, BitSet visit) { if( visit.get(def._nid) ) return; visit.set(def._nid); @@ -259,7 +259,7 @@ public abstract class GlobalCodeMotion { private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices - for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) + for( CFGNode cfg=lca; cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.antiDeps() ) { @@ -268,10 +268,14 @@ public abstract class GlobalCodeMotion { assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; - case CallNode st: + case EscapeNode st: assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; + case CallNode call: + assert late[call._nid]!=null; + lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call,anti); + break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. // No anti-dep edges but may raise the LCA. @@ -279,11 +283,7 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); break; - case NewNode st: - assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); - break; - default: throw Utils.TODO(); + default: throw Utils.TODO("Should not reach here"); } } return lca; diff --git a/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/src/main/java/com/seaofnodes/simple/codegen/IFG.java index bcd1957d..bcdb14bf 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -69,9 +69,9 @@ abstract public class IFG { // Reset all to empty resetBBLiveOut(); resetIFG(); + WORK.clear(); // Last block has nothing live out - assert WORK.isEmpty(); for( CFGNode bb : alloc._code._cfg ) if( bb.blockHead()) WORK.push( bb ); @@ -208,7 +208,13 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - if( !tlrg.sub(killMask) ) alloc.fail(tlrg); + Node live = TMP.get(tlrg); + // Disallow clone-ables from living across killed registers. + // Fail them and let splitting re-clone closer to the target use. + if( live instanceof MachNode mach && mach.isClone() ) + alloc.fail(tlrg); + else if( !tlrg.sub(killMask) ) + alloc.fail(tlrg); } } } @@ -316,7 +322,7 @@ abstract public class IFG { // Pull all lrgs from IFG, in trivial order if possible while( sptr < color_stack.length ) { // Swap best color up front - pickColor(color_stack,sptr,swork); + pickColor(color_stack,sptr,swork,alloc); // Pick a trivial lrg, and (temporarily) remove from the IFG. LRG lrg = color_stack[sptr++]; @@ -372,10 +378,10 @@ abstract public class IFG { } // Pick LRG from color stack - private static void pickColor(LRG[] color_stack, int sptr, int swork) { + private static void pickColor(LRG[] color_stack, int sptr, int swork, RegAlloc alloc) { // Out of trivial colorable, pick an at-risk to pull if( sptr==swork ) - swap(color_stack,sptr,pickRisky(color_stack,sptr)); + swap(color_stack,sptr,pickRisky(color_stack,sptr,alloc)); // When coloring, we'd like to give more choices; so when coloring we'd // like to see the single-def first (since no choices anyway), then // non-split related (so more live ranges get colored), then @@ -392,6 +398,7 @@ abstract public class IFG { swap(color_stack,sptr,bidx); // Pick best at sptr } + // Returns true if 'lrg' is better than 'best' private static boolean betterLRG( LRG best, LRG lrg ) { // If single-def varies, keep the not-single-def if( best.size1() != lrg.size1() ) @@ -399,18 +406,22 @@ abstract public class IFG { // If hasSplit varies, keep the hasSplit if( best.hasSplit() != lrg.hasSplit() ) return lrg.hasSplit(); + // If both are single register (so both sizes are 1), + // return a multi-use over a multi-def + if( best.size1() ) + return !best._multiUse && lrg._multiUse; // Keep large register count return best.size() < lrg.size(); } // Pick a live range that hasn't already spilled, or has a single-def- // single-use that are not adjacent. - private static int pickRisky( LRG[] color_stack, int sptr ) { + private static int pickRisky( LRG[] color_stack, int sptr, RegAlloc alloc ) { int best=sptr; - int bestScore = pickRiskyScore(color_stack[best]); + int bestScore = pickRiskyScore(color_stack[best],alloc); for( int i=sptr+1; i<color_stack.length; i++ ) { if( bestScore == 1000000 ) return best; // Already max score - int iScore = pickRiskyScore(color_stack[i]); + int iScore = pickRiskyScore(color_stack[i],alloc); if( iScore > bestScore ) { best = i; bestScore = iScore; } } @@ -425,30 +436,60 @@ abstract public class IFG { // // Picking a live range that is very close to coloring might allow it to // color despite being risky. - private static int pickRiskyScore( LRG lrg ) { + private static int pickRiskyScore( LRG lrg, RegAlloc alloc ) { + // Callee-save live ranges cover the whole function and are cheap to + // split. Rank scheduled area recovered against the loop-scaled cost + // of the def- and use-side moves. + if( lrg._machDef instanceof CalleeSaveNode ) + return areaScore(functionArea(lrg._fun,alloc), + splitCost((Node)lrg._machDef,(Node)lrg._machUse)); + if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && + lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) + return areaScore(functionArea(lrg._fun,alloc), + splitCost(lrg._splitDef,lrg._splitUse)); + // Pick single-def clonables that are not right next to their single-use. - // Failing to color these will clone them closer to their uses. + // Rank by the area recovered by cloning closer to the use. if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) { - Node def = (Node)lrg._machDef; - Node use = (Node)lrg._machUse; + Node def = ((Node)lrg._machDef); + Node use = ((Node)lrg._machUse); CFGNode cfg = def.cfg0(); - if( lrg._multiUse || cfg != use.cfg0() || // Many uses or different blocks OR - // Same block, but not close - cfg._outputs.find(def)+1 < cfg._outputs.find(use) ) + int area = cfg != use.cfg0() + ? functionArea(lrg._fun,alloc) + : cfg._outputs.find(use)-cfg._outputs.find(def)-1; + // A single-use function address can move next to its use without + // adding an instruction. Prefer that to saving a callee-save + // register just to hold the address. Stay in the same block and + // require a gap so the clone makes progress. + if( def instanceof FunPtrNode && !lrg._multiUse && + cfg == use.cfg0() && area > 0 ) return 1000000; + if( area > 0 ) + return areaScore(area,loopCost(use)); } - // Always pick callee-save registers as being very large area recovered - // and very cheap to spill. - if( lrg._machDef instanceof CalleeSaveNode ) - return 1000000-2-lrg._mask.firstReg(); - if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && - lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) - return 1000000-1; + // Default for ranges without a specific area/cost estimate. + return 1000 + (lrg._multiUse ? -100 : 0); + } + + private static int functionArea(FunNode fun, RegAlloc alloc) { + int area=0; + for( CFGNode bb : alloc._code._cfg ) + if( bb.fun()==fun ) + area += bb.nOuts(); + return area; + } + + private static int areaScore(int area, int cost) { + return 1000 + (area<<10)/cost; + } + + private static int splitCost(Node def, Node use) { + return loopCost(def) + (use==null ? 0 : loopCost(use)); + } - // TODO: cost/benefit model. Perhaps counting loop-depth (freq) of def/use for cost - // and "area" for benefit - return 1000; + private static int loopCost(Node n) { + return 1 << (n.cfg0().loopDepth()*3); } private static short biasColor( RegAlloc alloc, LRG lrg, short reg, RegMask mask ) { diff --git a/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/src/main/java/com/seaofnodes/simple/codegen/LRG.java index 009ddcdb..3a4596fe 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/LRG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/LRG.java @@ -56,6 +56,10 @@ public class LRG { // Adjacent Live Range neighbors. Only valid during coloring Ary<LRG> _adj; + // Function fully containing the live range; used to find the stack frame + // layout, for spill op offsets. + final public FunNode _fun; + public int nadj() { return _adj==null ? 0 : _adj._len; } void addNeighbor(LRG lrg) { @@ -78,7 +82,7 @@ public class LRG { // More registers than neighbors boolean lowDegree() { return nadj() < _mask.size(); } - LRG( short lrg ) { _lrg = lrg; _reg = -1; } + LRG( short lrg, FunNode fun ) { _lrg = lrg; _reg = -1; _fun = fun; } boolean leader() { return _leader == null; } @@ -114,6 +118,7 @@ public class LRG { } // Union `this` and `lrg`, folding together all stats. private LRG _union( LRG lrg ) { + assert _fun == lrg._fun; // Set U-F leader lrg._leader = this; // Fold together stats diff --git a/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java index 2415203d..252b5bf0 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java +++ b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; // In-memory linking @@ -8,16 +10,24 @@ public class LinkMem { final CodeGen _code; LinkMem( CodeGen code ) { _code = code; } - public CodeGen link() { - Encoding enc = _code._encoding; - + public CodeGen link(Encoding enc) { // Patch external calls internally enc.patchGlobalRelocations(); - // Write any large constants into a constant pool; they - // are accessed by RIP-relative addressing. - enc.writeConstantPool(enc._bits,true); + // Place constant pool after code, static data after constants + int code = 0; // Code start + int cpool = (enc._bits .size() + code + 15) & -16; // pad to 16 + int sdata = (enc._cpool.size() + cpool + 15) & -16; + + + // 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 = 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/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index ddf5a679..b6b3a22c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java @@ -28,7 +28,7 @@ public abstract class ListScheduler { } void free() { _n = null; FREE.push(this); } - static XSched get(Node n) { return n==null ? null : XS.get(n instanceof ProjNode && !(n.in(0) instanceof CallEndNode) ? n.in(0) : n); } + static XSched get(Node n) { return n==null ? null : XS.get(n instanceof ProjNode && !(n.in(0) instanceof CFGNode) ? n.in(0) : n); } private XSched init(CFGNode bb, Node n) { _n = n; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/src/main/java/com/seaofnodes/simple/codegen/Machine.java index a95faefc..3eee8fc3 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Machine.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Machine.java @@ -7,28 +7,42 @@ import com.seaofnodes.simple.type.TypeInteger; abstract public class Machine { // Human readable machine name. Something like "x86-64" or "arm" or "risc5" public abstract String name(); + // Default opcode size for printing; 4 bytes for most 32-bit risc chips public int defaultOpSize() { return 4; } + // Human-readable name for a register number, e.g. "RAX" or "R0" public abstract String[] regs(); - // Create a split op; any register to any register, including stack slots - public abstract SplitNode split( String kind, byte round, LRG lrg); + + // Create a split op; any register to any register, including stack slots. + // The FunNode holds the stack layout after RegAlloc, which in turn + // dictates the stack slot (the frame offset) for stack splits. + public abstract SplitNode split( LRG lrg, String kind, byte round ); + // List of caller-save registers, as a 64bit mask public abstract long callerSave(); + public long callerSave(String conv) { return callerSave(); } + // List of never-save registers, e.g. RSP or a ZERO register if you have one public abstract long neverSave(); + // Call Argument Mask. Passed in the function signature and argument // number (2-based; 0 is for control and 1 for memory). Also passed in a 0 // for the function itself, or for *outgoing* calls, the maximum stack slot // given to the incoming function arguments (stack slots reserved for // incoming arguments). public abstract RegMask callArgMask(TypeFunPtr tfp, int arg, int maxArgSlot); + public RegMask callArgMask(TypeFunPtr tfp, int arg, int maxArgSlot, String conv) { return callArgMask(tfp,arg,maxArgSlot); } + // Return register mask, based on signature (GPR vs FPR) public abstract RegMask retMask(TypeFunPtr tfp); + // Return PC register public abstract int rpc(); + // Return a MachNode unconditional branch public abstract CFGNode jump(); + // Instruction select from ideal nodes public abstract Node instSelect( Node n ); @@ -94,13 +108,18 @@ Pre-alloc Post-Alloc SP+48 RPC // shadow slots if defined in the ABI, even if all arguments are passed in // registers. public abstract short maxArgSlot(TypeFunPtr tfp); + public short maxArgSlot(TypeFunPtr tfp, String conv) { return maxArgSlot(tfp); } + + // Calling convention used for external C symbols. + public String cCallingConv(String callingConv) { return callingConv; } // Only the declared C result width describes the physical return register. // Simple functions already return canonical full-width integer values. protected static TypeInteger cReturn(ProjNode prj) { if( prj._idx==2 && prj.in(0) instanceof CallEndNode cend && - cend.call().fptr() instanceof ExternNode ext && - ((TypeFunPtr)ext._con).ret() instanceof TypeInteger ret && ret.log_size()<3 ) + cend.call().fptr()._type instanceof TypeFunPtr tfp && tfp.isConstant() && + CodeGen.CODE.externFunc(tfp.fidx())!=null && + tfp.ret() instanceof TypeInteger ret && ret.log_size()<3 ) return ret; return null; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Module.java b/src/main/java/com/seaofnodes/simple/codegen/Module.java new file mode 100644 index 00000000..a5d85dbc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Module.java @@ -0,0 +1,98 @@ +package com.seaofnodes.simple.codegen; + + +/*** + Modules!?!?!? + + Goal: under no circumstances can you load from an uninitialized variable + (although you can see default inits for fields that have defaults). + Goal: nested tree-structured name spaces, to control complexity. + Goal: field decl order within a file is fairly flexible. + + A Module a root-level SMP file, and the full file path must be provided on + the command line. All other Simple structs are relative to this file. + + Example: "simple /user/Dave/hello.smp" + + Defines a module "hello" in directory "/user/Dave", compiles and produces + a `hello` or `hello.exe` output file, and runs it. + + A SMP file has some <finit> file-init code which is static-global. + This code is executed on "first touch" of the file (defined below). + + Example: hello.smp contains: + sys.io.p("Hello World!"); + On first-touch, will print "Hello World!". + + A SMP file is a lexical scope, and code inside it can reference those names. + + Example: hello.smp contains: + val greet = "Hello World!"; // Declare file-scoped variable + sys.io.p(greet); // Reference file-scoped variable + + Static code is NOT allowed to have forward-references AND be executed + before the <finit> finishes initializing all variables. After var + initialization, a singleton instance of the implied file struct is made, + and then <finit> code can call anything. + + Example: + sys.io.p(greet); // Illegal forward reference + val greet = "Oops!"; + + Example: + val delay = { -> greet }; // Legal forward ref, but cannot execute (yet) + val greet = "Hello World!"; // Ref is resolved + sys.io.p(delay()); // Allowed to call delay() + val nprimes = { N -> + // compute number of primes < N + } + // Can otherwise execute any code in a <finit> + sys.io.p(nprimes(100)); + + Inside a directory, you can have sibling SMP files: + File hello.smp contains: + sys.io.p(I9A.GREETING); // File hello references sibling file I9A static globals + File I9A.smp contains: + val GREETING = translate("Hello World!"); + val translate = { str msg -> ... }; + + <finit> code cannot reference sibling files (nor child files, see below) + until all static variables are initialized. This prevents cyclic + initialization bugs, where file A uses vars from file B and vice-versa. + + File Chicken.smp contains: + val lay = Egg.hatch; // Illegal, defining var 'lay' after calling sibling Egg + File Egg.smp contains: + val hatch = Chicken.lay; // Illegal + + You can make cross references, if they get delayed until after all fields + are declared. + + File Chicken.smp contains: + int lay = 2; + lay = Egg.egg; + + File Egg.smp contains: + int egg = 3; + egg = Chicken.lay; + + The problem here, of course, is that you need to touch one of Chicken or + Egg first. + + + Inside a SMP file, you can define structs; structs are also a lexical + scope. Bare code in the struct is part of the struct's <init> and only + runs when an instance is created. Structs do not have static <clinit> (nor + <finit>). Structs <init> cannot have any forward references, and locally + declared functions cannot have both forward references and be executed (or + passed along to a possibly-executing function). + + In the same directory as a SMP file, Simple allows other directories with + names matching SMP files. Inside these dirs can be more SMP files that are + lexically nested, similar to embedded structs. + + +*/ + +public abstract class Module { +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index cd52aadd..132705aa 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -1,10 +1,12 @@ 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.Ary; +import com.seaofnodes.simple.util.Utils; + import java.util.Arrays; +import java.util.BitSet; // Optimistic Algorithm abstract public class Opto { @@ -24,38 +26,22 @@ abstract public class Opto { // get a fairly precise set of Call Graph edges between CallNodes and // FunNodes. public static void opto(CodeGen code) { - - // Pessimistic peephole optimization on a worklist - this completes - // whatever peepholes can run after parsing. - code._iter.iterate(code); - // Reset Types before running the worklist algorithm Ary<Type> oldTypes = new Ary<>(Type.class); // Used for asserts only resetToTop(code,oldTypes); - - // The whole-world assumption: we use it if compiling `main`, and not otherwise. - // The assumption is no unknown callers into functions: - // - during or past an Opto phase (but not before, since parse through - // pessimistic must assume somebody calls an unknown function which - // calls everybody). - // - Have a `main` to start tracing the Call Graph from - // - - True for most test cases - // - - False for lacking a main; we assume the linker will call all public functions - - // True if we can make the "whole world" assumption, which means we are - // compiling the program entry: `main`. - boolean wholeWorld = code.link(code._main) != null; - - - // If wholeWorld, remove the Start inputs to functions - they are not - // called unless they get linked (hence go dead and can be removed). - // If not wholeWorld, keep only public methods (and not the std lib). - unlinkStart(wholeWorld,code); - + unlinkStart(code); // OPTIMISTIC INTERPROCEDURAL SCCP sccp(code, oldTypes); + // SCCP can leave a recursive numeric component at BOTTOM with no + // arithmetic mode selected. Resolve the whole component from all + // available int/float evidence before IterPeeps consumes the types. + resolveNumericModes(code); + + if( !code._iter._work.isEmpty() ) + sccp(code, oldTypes); + // After SCCP add everything changed to the worklist and see if // peepholes can make more progress. moveChangesToWorklist(code, oldTypes); @@ -73,15 +59,23 @@ abstract public class Opto { // Propagate field size constants code._iter.iterate(code); - // Throw away the Call Graph - // The remaining passes assume all calls are unlinked; i.e. we are - // throwing away the Call Graph here. Functions only reachable from - // internal calls need to be re-hooked to stop/start less they go dead. - removeCallGraph(code); + // Retain surviving functions in their CompUnits for later code + // emission. Start inputs are semantic: they mean unknown callers. + for( FunNode fun : code._linker ) + if( fun != null && !fun.isDead() && !fun._type.isHigh() ) + keepInCompUnit(code,fun); + + for( CompUnit cu : code._compunits.values() ) { + ProjNode mem = cu._start.proj(1); + if( mem != null ) mem.unkeep(); + } // To help with testing, sort StopNode Returns by NID - Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid ); + for( Node stop : code._stop._inputs ) + Arrays.sort(stop._inputs._es,0,stop.nIns(), + (x,y) -> ((((ReturnNode)x).fun().isClz() ? -1 : x._nid) - + (((ReturnNode)y).fun().isClz() ? -1 : y._nid) )); } // Reset Types before running the worklist algorithm @@ -90,9 +84,6 @@ abstract public class Opto { oldTypes.setX(x._nid,x._type); // Record original types for asserts x._type = Type.TOP; // Reset all Nodes to TOP code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP - // Unlink all existing (conservative) linkages. - if( x instanceof CallNode call ) - call.unlink_all(); return null; } ); } @@ -101,44 +92,55 @@ abstract public class Opto { // If wholeWorld, remove the Start inputs to functions - they are not // called unless they get linked (hence go dead and can be removed). If // not wholeWorld, keep only public methods (and not the std lib). - private static void unlinkStart(boolean wholeWorld, CodeGen code) { - for( FunNode fun : code._linker ) { - if( fun != null && !fun.isDead() && !funIsPublic(code,wholeWorld,fun) ) { - assert fun.in(1)==code._start; // Start always in slot 1 - fun.removeDeadPath(1); - // By same logic, remove stop->return linkage, without - // remove the (now dead) ReturnNode; it awaits in limbo - // for the opto phase to link to some valid call - code._stop._inputs.del(code._stop._inputs.find(fun.ret())); - fun.ret().delUse(code._stop); - } + private static void unlinkStart(CodeGen code) { + // Keep the Start & Start.ProjMem alive even as we remove all uses + for( CompUnit cu : code._compunits.values() ) { + ProjNode mem = cu._start.proj(1); + if( mem!=null ) mem.keep(); } - } - // Function is public (callable from Start directly). - // - Always true for main - // - True for function addresses used as values - // - Otherwise false for stdlib or anonymous functions - // - Named functions use `!wholeWorld` - private static boolean funIsPublic( CodeGen code, boolean wholeWorld, FunNode fun ) { - // Always true for main - if( fun.sig().fidx() == code._main.fidx() ) return true; - // No escape analysis yet: a surviving address may be called from outside. - if( fun.hasPtr() ) return true; - // Never true for stdlib or anonymous functions - if( fun._name == null || fun._name.startsWith("sys.") ) - return false; - // Named functions (and not stdlib) are callable if not whole-world. - return !wholeWorld; + // Iterate the Stop-of-Stops + for( Node stop : code._stop._inputs ) { + for( int i=0; i<stop.nIns(); i++ ) { + ReturnNode ret = (ReturnNode)stop.in(i); + FunNode fun = ret.fun(); + // Start is a semantic unknown-caller edge. Public functions + // keep it; closed-world functions must be reached by a + // concrete Call edge discovered during SCCP. + if( !(code.owns(fun) && fun.isClz()) && + !code.publicFIDX(fun.sig().fidx()) && + fun.in(1) instanceof StartNode ) { + fun.removeDeadPath(1); + // Unhook from Stop without treating the ReturnNode as + // DEAD. It stays in limbo until Opto links when a caller + // is discovered (or not, and the function is really dead). + stop._inputs.del(i--); + ret.delUse(stop); + } + // Unlink the existing conservative call linkages. + for( int j=1; j<fun.nIns(); j++ ) + if( fun.in(j) instanceof CallNode call ) + call.unlink(fun,j--); + } + } } // As part of building a CallGraph, when opto finds a function ptr flowing // into a Call, link the Call and Fun. private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { if( tfp.nargs() != call.nargs() ) return; // Error calls hit this - for( long fidxs=tfp.fidxs(); fidxs!=0; fidxs=TypeFunPtr.nextFIDX(fidxs) ) { - int fidx = Long.numberOfTrailingZeros(fidxs); - FunNode fun = code.link(fidx); + int[] fidxs = tfp.fidxs(); + // An unresolved forward call can still carry the infinite, inferred + // function set into Opto. There is no finite call graph to link yet; + // type checking will report the unresolved reference afterwards. This + // can yet be valid if the call is eventually dead. + // `if( false ) frefCall(args);` + if( XInt.isHigh(fidxs) ) return; + for( int fidx = XInt.next(fidxs,0); fidx >=0; fidx = XInt.next(fidxs,fidx) ) { + // unlinkStart deliberately leaves uncalled functions in a + // temporarily dead limbo. A newly discovered call revives them; + // do not use the cleanup lookup which removes dead linker entries. + FunNode fun = code._link(fidx); // null here means an external function; i.e. this Call // calls to an outside library and all its arguments escape. if( fun != null && !call.linked(fun) ) { @@ -149,6 +151,56 @@ abstract public class Opto { } } + // Start added some FIDXs, the same functions now can be reached from start + // and called by anybody. Add the CG edges. + private static void linkStart( CodeGen code, TypeTuple tt ) { + TypeMem tmem = (TypeMem)tt._types[1]; + int[] fidxs = tmem._escFs; + if( XInt.isHigh(fidxs) ) { + // A scalar BOTTOM can flow into memory while compiling an error + // program. It exposes all public functions, not private fields. + for( FunNode fun : code._linker ) + if( fun != null && code.publicFIDX(fun.sig().fidx()) ) + linkStart(code,fun); + return; + } + for( int fidx = XInt.next(fidxs,0); fidx >=0; fidx = XInt.next(fidxs,fidx) ) { + FunNode fun = code._linker.atX(fidx); + if( fun==null ) assert code._externFunc.containsKey(fidx); + else linkStart(code,fun); + } + } + + // Function is now reachable by unknown callers through Start. The + // default inputs must therefore use conservative declared types. + private static void linkStart( CodeGen code, FunNode fun ) { + assert !fun.isDead(); + StartCUNode start = fun._compunit._start; + if( fun.nIns() < 2 ) { + assert fun.nIns() < 2 || fun.in(1) != start; + assert !start.isDead(); + keepInCompUnit(code,fun); + // Function is reachable by any *remote* caller who gets the pointer! + fun.insertDef(1,start); + code._iter.add(fun); + for( Node p : fun._outputs ) + if( p instanceof ParmNode parm ) { + Node defalt = parm._idx==1 ? start.proj(1) : ConstantNode.seed(parm._declaredType).peephole(); + parm.insertDef(1,defalt); + code.add(parm); + } + } + } + + // Keep a surviving function rooted in its compilation unit without + // claiming that it has unknown callers. + private static void keepInCompUnit(CodeGen code, FunNode fun) { + StopCUNode stop = fun._compunit._stop; + if( stop._inputs.find(fun.ret()) == -1 ) + code.add(stop).addDef(fun.ret()); + } + + // The core SCCP algorithm private static void sccp( CodeGen code, Ary<Type> oldTypes ) { // Iter workList is empty at this point @@ -160,108 +212,161 @@ abstract public class Opto { count++; Type oval = n._type, nval = n.compute(); if( oval == nval ) continue; - assert oval.isa(nval); // Types start high and always fall - Type pesiVal = oldTypes.at(n._nid); - assert nval.isa(pesiVal); // Never fall worse than the pessimistic pass + assert oval.isa(nval) : "Non-monotonic SCCP: "+n.getClass().getSimpleName()+"#"+n._nid+" "+n+" old="+oval+" new="+nval; // Types start high and always fall + Type pesiVal = oldTypes.atX(n._nid); + assert pesiVal==null || nval.isa(pesiVal) : "SCCP below pessimistic type: "+n.getClass().getSimpleName()+"#"+n._nid+" "+n+" pessimistic="+pesiVal+" new="+nval; // Never fall worse than the pessimistic pass n._type = nval; - // If a TFP adds a new function input to a call, link to the new Fun + // Now we have a series of stanzas where we lazily create the Call + // Graph - adding graph edges between every call site and called + // function, including external (unknown) callers. These edges are + // not in from the start because they are *too many*; we would get + // O(n^2) edges. So all along we have been treating them as + // "virtual" CFG edges - a FunNode taking a Start input is treated + // as if every call on the planet might call it. Now we make these + // CG edges *concrete*, adding them back as we discover that a call + // calls a particular function. + + // If a TFP adds a new function input to a call, link to the new + // Fun. This adds new edges to the graph allowing argument values + // to flow from calls into functions. The added edges are + // effectively a refined Call Graph. if( nval instanceof TypeFunPtr tfp ) { for( Node use : n._outputs ) if( !use._type.isHigh() && use instanceof CallNode call && call.fptr() == n ) linkCG(code,tfp,call); } - // Link a Call which becomes alive - if( n instanceof CallNode call && oval.isHigh() && !nval.isHigh() && call.fptr()._type instanceof TypeFunPtr ) + // Link a Call which becomes alive. Like above, adds new Call + // Graph edges to the graph. + if( n instanceof CallNode call && nval == Type.CONTROL && call.fptr()._type instanceof TypeFunPtr ) linkCG(code,call.tfp(),call); + // If an otherwise-dead function pointer escapes, any future linked + // caller might find and call it. Force the function to be alive + // and called by Start. + if( n instanceof StartNode ) + linkStart(code,(TypeTuple)n._type); + // Since n._type changed, visit all output neighbors code._iter.addAll(n._outputs); n.moveDepsToWorklist(code._iter); - // Quadratic (expensive) small-step assert - assert check(code); + // Quadratic (expensive) small-step assert. + assert !CodeGen.expensiveAssert(count) || worklistCheck(code); } } - // Quadratic (expensive) small-step assert - private static boolean check(CodeGen code) { - code._start.walk( x -> { + // Quadratic (expensive) fixed-point assert + public static boolean fixedPointCheck(CodeGen code) { + return fixedPointCheck(code,code._stop); + } + public static boolean fixedPointCheck(CodeGen code, Node root) { + root.walk( x -> { Type xval = x.compute(); - assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )); + assert xval == x._type; return null; }); return true; } + // Quadratic (expensive) small-step assert for SCCP, where changed nodes + // may already be on the worklist. + private static boolean worklistCheck(CodeGen code) { + code._midAssert = true; + Node root = code._start; + root.walk( x -> { + Type xval = x.compute(); + assert xval == x._type || (x._type.isa( xval ) && code._iter._work.on( x )) + : "Non-monotonic or missed SCCP work: "+x.getClass().getSimpleName()+"#"+x._nid+" "+x+" old="+x._type+" new="+xval; + return null; + }); + code._midAssert = false; + return true; + } + // After SCCP add everything changed to the worklist and see if peepholes // can make more progress. private static void moveChangesToWorklist(CodeGen code, Ary<Type> oldTypes) { code._start.walk( x -> { assert x.compute() == x._type; // Hit the fixed point assert x._nid >= oldTypes._len || x._type.isa(oldTypes.at(x._nid)); // Hit at least the bottom-up type - code._iter.add(x); + code.add(x); return null; }); } + // Resolve arithmetic modes which are ambiguous only because they belong to + // a recursive component. Float wins because integer operands can be + // converted to float. + private static void resolveNumericModes(CodeGen code) { + final BitSet visited = new BitSet(); + code._stop.walk(n -> { + if( n instanceof ModeNode modeNode && modeNode.mode()==0 ) { + visited.clear(); + visited.set(n._nid); // Inspect inputs, not Bool's integer result + int mode = 0; + for( int i=1; i<n.nIns(); i++ ) + mode |= numericEvidence(n.in(i),visited); + // A closed recursive numeric component can have no remaining + // concrete evidence after SCCP, e.g. dead all-integer loops. + // With no float evidence, settle to integer. + if( mode == 0 ) + mode = 1; + if( mode != 0 ) { + // If both evidence, FP wins + modeNode.setMode((byte)((mode&2)==2 ? 2 : 1)); + code.add(n); + code.addAll(n.outs()); + } + } + return null; + }); + } + + // Gather numeric evidence through Phi and interprocedural return cycles. + // The visited set makes self- and mutually-recursive calls finite. + private static int numericEvidence(Node n, BitSet visited) { + if( n == null ) return 0; + if( visited.get(n._nid) ) return 0; + visited.set(n._nid); + + Type t = n._type; + if( t instanceof TypeFloat ) return 2; + if( t instanceof TypeInteger ) return 1; + if( t!=Type.BOTTOM && !(t instanceof TypeTuple) ) + return 0; // Something unrelated, like a ptr + + int evidence = 0; + assert !(n instanceof ConvertNode); // No test case + switch( n ) { + case ModeNode modeNode when modeNode.mode() != 0 -> { return modeNode.mode(); } + case ModeNode modeNode -> {} + case PhiNode phi -> {} + case ReturnNode ret -> {} + case ProjNode proj when proj.in(0) instanceof CallEndNode cend -> { + for( int i=1; i<cend.nIns(); i++ ) + evidence |= numericEvidence(cend.in(i),visited); + } + default -> { return 0; } + } + for( int i=1; i<n.nIns(); i++ ) + evidence |= numericEvidence(n.in(i),visited); + + return evidence; + } + + // Freeze field sizes; do struct layouts; convert field offsets into // constants. private static void fieldSizes( CodeGen code ) { for( int i=0; i<code._start.nOuts(); i++ ) { Node use = code._start.out(i); if( use instanceof ConFldOffNode off ) { - TypeMemPtr tmp = (TypeMemPtr) Parser.TYPES.get(off._name); - off.subsume( off.asOffset(tmp._obj) ); + Node con = off.asOffset(); + assert con != null; // Can be null for trying to reference missing field + off.subsume( con ); i--; } } } - - // The remaining passes assume all calls are unlinked; i.e. we are throwing - // away the Call Graph here. Functions only reachable from internal calls - // need to be re-hooked to stop/start less they go dead. - private static void removeCallGraph(CodeGen code) { - code._start.walk( x -> { - // Unlink all existing (conservative) linkages. - if( x instanceof CallNode call ) { - for( Node y : call._outputs ) { - // Keep function alive and hooked to Start so it gets - // codegen'd. Function is callable by this call via - // TFP, although perhaps not by any other means. - if( y instanceof FunNode fun && !(fun.in(1) instanceof StartNode) ) { - ParmNode rpc = fun.rpc(); - if( rpc==null ) // Ensure valid RPC - rpc = makeRPC(fun); - // Insert a hook to Start and Stop - fun.insertDef(1,code._start); - for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) - parm.insertDef(1,ConstantNode.make(parm._type).peephole()); - code._stop.addDef(fun.ret()); - } - } - call.unlink_all(); - } - return null; - } ); - - } - - // Make a valid Parm RPC. - // First make sure a valid RPC; single-call into multi-fun will have each - // function having a single call site, so the RPC becomes a constant and - // folds - but since multiple targets, the Call never inlines. Recreate a - // valid RPC so codegen (and Eval2) understands the calling convention. - private static ParmNode makeRPC( FunNode fun ) { - ParmNode rpc = new ParmNode("$rpc",0,fun.ret().rpc()._type,fun); - for( int i=1; i<fun.nIns(); i++ ) { - CallEndNode cend = ((CallNode)fun.in(i)).cend(); - rpc.addDef(ConstantNode.make(cend._rpc).peephole()); - } - fun.ret().setDef(3,rpc.init()); - return rpc; - } - - } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java new file mode 100644 index 00000000..90309328 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -0,0 +1,396 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.print.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.*; +import java.io.File; +import java.io.IOException; +import java.util.*; + +// Parse a given file, and all its dependencies +public abstract class ParseAll { + + // Worklist of symbols to search and files to parse + private static final Ary<CompUnit> WORK = new Ary<>(CompUnit.class); + + private static final Ary<CompUnit> NEEDS_LOAD = new Ary<>(CompUnit.class); + + // Return a compilation unit (cached or new). If new, it does not necessarily + // need to be compiled. + public static CompUnit makeCUnit( CodeGen code, CompUnit par, String name ) throws IOException { + return makeCUnit(code,par,name,null,false); + } + + private static CompUnit makeCUnit( CodeGen code, CompUnit par, String name, File obj ) throws IOException { + return makeCUnit(code,par,name,obj,obj!=null); + } + + private static CompUnit makeCUnit( CodeGen code, CompUnit par, String name, File obj, boolean external ) throws IOException { + // Slashed file name? Move leading parts into parent CUs. + int idx = name.indexOf("/"); + if( idx >= 0 ) { + String head = name.substring(0,idx); + CompUnit sub = makeCUnit(code,par,head,external ? externalObj(code,par,head) : null,external); + return makeCUnit(code,sub,name.substring(idx+1).intern(),obj,external); + } + + String fname = par==null ? name : (par._fname + "/" + name).intern(); + CompUnit cunit = code._compunits.get(fname); + if( cunit != null ) return cunit; + String cname = par==null ? name : (par._cname + "." + name).intern(); + code._compunits.put(fname, cunit = external ? new CompUnit(obj,par,fname,cname,name) : new CompUnit(par,fname,cname,name)); + return cunit; + } + + // Parse a top-level string, used for e.g. testing + static void parseSource( CodeGen code, String src ) { + parseSource(code,"Test",src); + } + + // Parse a top-level string with an explicit compilation-unit name. + static void parseSource( CodeGen code, String fname, String src ) { + CompUnit cunit = new CompUnit(fname,src); + code._compunits.put(cunit._fname,cunit); + parseAll(code,cunit); + } + + // module_root/.../src.smp is source file name. + static void parsePath(CodeGen code, String fname) { + try { + // Split and build the parent-path down to the source file. + CompUnit cu = makeCUnit( code, null, fname ); + // Compile this CompUnit + parseAll(code,cu); + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + } + + private static void parseAll(CodeGen code, CompUnit cunit) { + WORK.clear(); // Cleanup from prior tests + NEEDS_LOAD.clear(); + // Prime the pump with the first CompUnit + WORK.add(cunit); + // Work through all unparsed compilation units and parse + while( !WORK.isEmpty() ) { + CompUnit cu = WORK.remove(0); + // No source code? Means we do not need to parse, but instead need to load the symbols as-if we parsed + if( cu._src==null || cu._src.isEmpty() ) + loadDeps(code,cu); // Load recursive dependents + else + parseOne( code, cu ); // Parse + } + + // Load all pre-compiled CompUnits + for( CompUnit cu : NEEDS_LOAD ) + loadCompUnit(code,cu); + if( !NEEDS_LOAD.isEmpty() ) + code._stop.walk(n -> { + if( n instanceof CallNode ) + code.add(n); + return null; + }); + + // Many types will have been declared cyclically either internally or + // across multiple compilation units. + + // Close over all recursive types, and upgrade TYPES + Ary<TypeStruct> ary = new Ary<>(TypeStruct.class); + for( Type t : Parser.TYPES.values() ) + if( t instanceof TypeStruct ts ) + ary.add(ts); + TypeStruct[] tss = Type.closeOver(ary.asAry(),Parser.TYPES); + for( TypeStruct ts : tss ) + Parser.TYPES.put(ts._name,ts); + for( CompUnit cu : code._compunits.values() ) + if( cu._ext==null ) + cu._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cu._cname)); + + // Walk over all Nodes, and upgrade the internal constants to the + // closed-over types. + code._stop.walk( (Node n) -> { + n.upgradeType(Parser.TYPES); + if( n instanceof FRefNode fref ) { + boolean alloc = fref._name.endsWith(".<new>"); + String clzName = alloc + ? fref._name.substring(0,fref._name.length()-".<new>".length()).intern() + : fref._name; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + if( clz == null ) + return null; + Node con; + if( alloc ) { + Field ctor = clz.field("<new>"); + if( ctor == null || !(ctor._t instanceof TypeFunPtr tfp) ) { + String name = clzName.startsWith(Parser.CLZ) + ? clzName.substring(Parser.CLZ.length()) : clzName; + int dot = name.lastIndexOf('.'); + throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); + } + FunNode fun = code.link(tfp); + if( fun == null ) return null; + con = new FunPtrNode(tfp,code._start,fun.ret()).peephole(); + } else { + // Class pointer constant: + TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); + con = code.con(clzptr); + } + // Replace and optimize + fref.addDef(con); + code.add(fref); + } + // Adds sort by NIDs, which just got shuffled + if( n instanceof AddNode add ) + code.add(add); + return null; + } ); + + // The complete public interface is now known. Keep this independent + // of later graph/linker liveness so SCCP computations remain local and + // monotonic. + code.freezePublicInterface(); + } + + // Parse one Simple source code file. Add all the FRefs produced to the worklist. + private static void parseOne( CodeGen code, CompUnit cunit ) { + cunit.setStart(code); + // Parse a source file, return missing external references + Ary<FRefNode> frefs = code.P.parse(cunit); + + // Find all missing external references, or complain. This can trigger more parses. + while( !frefs.isEmpty() ) { + FRefNode fref = frefs.remove(0); + // Symbol not found in source code (or we would not be here). + // Search the module for the fref + try { + CompUnit xcunit = findCUnitModule(code,cunit,fref._name); + if( xcunit == null ) + xcunit = findCUnitExternalSimple(code,fref._name); + if( xcunit != null ) { + // Replace the FRef with the discovered class name. + fref._name = Parser.addClzPrefix(xcunit._cname); + cunit.addDep(xcunit); + } else { + throw new RuntimeException("Undefined name '" + fref._name +"'"); + } + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + } + addRequiredTypes(code,cunit); + } + + private static void addRequiredTypes(CodeGen code, CompUnit cunit) { + LinkedHashSet<String> required = new LinkedHashSet<>(); + code._stop.walk(n -> { + TypeStruct ts = CodeGen.requiredStruct(n); + if( ts!=null && ts._fref ) required.add(ts._name); + return null; + }); + for( String typeName : required ) { + try { + CompUnit xcunit = findRequiredType(code,cunit,typeName); + if( xcunit != null ) + cunit.addDep(xcunit); + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + } + } + + private static CompUnit findRequiredType(CodeGen code, CompUnit cunit, String typeName) throws IOException { + for( CompUnit cu = cunit; cu != null; cu = cu._par ) { + String symbol = typeName.startsWith(cu._cname+".") + ? typeName.substring(cu._cname.length()+1) + : typeName; + CompUnit xcunit = findCUnitModule(code,cu,symbol); + if( xcunit != null ) + return xcunit; + } + return findCUnitExternalSimple(code,typeName); + } + + // Load the public symbols for this CompUnit, and add dependent CompUnits to the NEEDS_LOAD list. + private static void loadDeps(CodeGen code, CompUnit cunit) { + // Load IR after parsing + if( NEEDS_LOAD.find(cunit) != -1 ) + return; // Already on the to-be-loaded list? + try { + NEEDS_LOAD.add(cunit); + // Load dependent classes + ElfReader elf = ElfReader.load(cunit._obj,cunit); + elf.loadPublicSymbols(); + for( String fname : elf._deps ) { + // Check CompUnit for being up to date + CompUnit sub = makeCUnit(code,null,fname,null/*depObj(code,cunit,fname)*/); + // If not seen before or out of date, parse the new nested cunit + if( sub._clz == null && sub._par == null ) + WORK.add(sub); + } + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + } + + private static File depObj(CodeGen code, CompUnit cunit, String fname) { + if( cunit._smp != null ) + return null; + ElfReader elf = code.findExternalSimple(Parser.addClzPrefix(fname.replace('/','.'))); + if( elf == null ) + throw new RuntimeException("Cannot find external Simple dependency '"+fname+"'"); + return elf._file; + } + + private static File externalObj(CodeGen code, CompUnit par, String name) { + String cname = par==null ? name : par._cname + "." + name; + ElfReader elf = code.findExternalSimple(Parser.addClzPrefix(cname)); + return elf == null ? null : elf._file; + } + + private static void loadCompUnit(CodeGen code, CompUnit cunit) { + // Expecting a previously compiled object file + assert cunit._obj != null; + // Extract published symbols and put them in the internal tables; + // cross-references will pick them up there. + ElfReader elf = ElfReader.load(cunit._obj,cunit); + cunit._clz = elf.loadSimple(code); + StartNode lstart = (StartNode)elf._nodes.at(0); + StopNode lstop = ( StopNode)elf._nodes.last(); + + // Add all new loaded functions to the linker table + for( Node n : lstop._inputs ) { + StopCUNode stop = (StopCUNode)n; + StartCUNode start = stop.start(); + CompUnit cu = code._compunits.get(start._fname); + cu._start = start; + cu._stop = stop ; + + for( Node ret : stop._inputs ) { + FunNode fun = ((ReturnNode)ret).fun(); + code.link(fun); + } + } + + // Hook the new code into the existing code graph + for( Node lstopcu : lstop._inputs ) + code._stop.addDef(lstopcu); + lstart.subsume(code._start); + + // Add the new top-level loaded class + Parser.TYPES.put(cunit._clz._name,cunit._clz); + Field inst = cunit._clz.field(cunit._name); + if( inst != null ) // Also the instance type, if a constructor exists + Parser.TYPES.put(cunit._cname, ((TypeMem)((TypeFunPtr)inst._t)._ret)._t); + } + + // Symbol not found in source code (or we would not be here). + // Search the module for the fref + public static CompUnit findCompUnitOrThrow(CodeGen code, CompUnit cu, String symbol) { + CompUnit cu2 = findCompUnit(code,cu,symbol); + if( cu2 != null ) return cu2; + throw new RuntimeException("Undefined name '" + symbol +"'"); + } + + public static CompUnit findCompUnit(CodeGen code, CompUnit cu, String symbol) { + // Symbol not found in source code (or we would not be here). + // Search the module for the fref + try { + CompUnit local = findCUnitModule(code,cu,symbol); + if( local != null ) + return local; + return findCUnitExternalSimple(code,symbol); + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + } + + // Find the symbol in module, starting from cunit. This searches up the nested + // class chain and sideways 1 step, so that any prefix of the class chain can + // be skipped as a shortcut. Symbol can have dotted names, which then go + // down into classes. e.g. + // A/X/Y exists. + // A/B contains X.Y, which is a shortcut for A.X.Y + + // However if A/B contains "Y", the search would be for A.B.Y then A.Y both of + // which do not exist. + private static CompUnit findCUnitModule( CodeGen code, CompUnit cunit, String symbol ) throws IOException { + if( cunit == null ) // Ran off top of module scope? + return null; // Failed search + + // Check self + if( cunit._name.equals(symbol) ) + return cunit; + + // If symbol is itself nested (has embedded dots), move the leading part + // over to the CompUnit path. So e.g.: + // CompUnit{A.B}, Symbol="X.Y" + // becomes + // CompUnit{A.B.X}, Symbol="Y" + int dotIdx = symbol.indexOf("."); + if( dotIdx != -1 ) { + String pre = symbol.substring(0,dotIdx); + String rest = symbol.substring(dotIdx+1 ); + String fname = cunit._fname + "/" + pre; + File f = new File( code._modDir + "/" + fname + ".smp" ); + if( f.exists() ) { + CompUnit sub = makeCUnit(code,cunit,pre); + // Note that "sub" itself is not put on the to-be-parsed-list. We're + // referring to a child class and do not need to parse the middles. + CompUnit dcunit = findCUnitModule(code,sub,rest); + if( dcunit != null ) + return dcunit; // Nested dot search found cunit + } + } + + // Look in mod / fname / name / symbol.smp + String fname = cunit._fname + "/" + symbol; + File f = new File( code._modDir + "/" + fname + ".smp" ); + if( f.exists() ) { + CompUnit sub = makeCUnit(code,cunit,symbol); + // If not seen before or out of date, parse the new nested cunit + if( sub._clz == null && WORK.find(sub) == -1 ) + WORK.add(sub); + return sub; + } + + // Look up the scope + return findCUnitModule( code, cunit._par, symbol ); + } + + // Search external Simple objects only. C linkage uses explicit "C" + // declarations, which produce ExternNodes and are resolved by the linker. + public static CompUnit findCUnitExternalSimple( CodeGen code, String symbol ) { + String clzName = symbol.startsWith(Parser.CLZ) ? symbol : Parser.addClzPrefix(symbol); + String cname = clzName.substring(Parser.CLZ.length()); + String fname = cname.replace('.','/'); + + CompUnit cunit = code._compunits.get(fname); + if( cunit != null ) + return cunit; + + ElfReader elf = code.findExternalSimple(clzName); + if( elf == null ) + return null; + + try { + cunit = makeCUnit(code,null,fname,elf._file); + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + ElfReader typedElf = ElfReader.load(cunit._obj,cunit); + TypeStruct clz = typedElf == null ? null : typedElf.loadPublicTypes(code); + if( clz != null ) + Parser.TYPES.put(clz._name,clz); + else + clz = (TypeStruct)Parser.TYPES.get(clzName); + if( clz == null ) + Parser.TYPES.put(clzName,clz = TypeStruct.make(clzName,true)); + cunit._clz = clz; + if( WORK.find(cunit) == -1 && NEEDS_LOAD.find(cunit) == -1 ) + WORK.add(cunit); + return cunit; + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java b/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java index 777182dc..48319006 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java @@ -3,7 +3,7 @@ package com.seaofnodes.simple.codegen; // This Node rip-relative encodings has sizes that vary by delta public interface RIPRelSize { // delta is the distance from the opcode *start* to the target start. Each - // hardware target adjusts as needed, X86 measures from the opcode *end* + // hardware target adjusts as needed. X86 measures from the opcode *end* // and small jumps are 2 bytes, so they'll need to subtract 2. byte encSize(int delta); diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 7e826661..1ce68080 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -57,6 +57,8 @@ public class RegAlloc { public int _spills, _spillScaled; + private boolean _done; + // ----------------------- // Live ranges with self-conflicts or no allowed registers private final IdentityHashMap<LRG,String> _failed = new IdentityHashMap<>(); @@ -68,6 +70,7 @@ public class RegAlloc { _failed.put(lrg,""); } boolean success() { return _failed.isEmpty(); } + public boolean done() { return _done; } // ----------------------- @@ -76,16 +79,16 @@ public class RegAlloc { short _lrg_num; // Define a new LRG, and assign n - LRG newLRG( Node n ) { + LRG newLRG( Node n, FunNode fun ) { LRG lrg = lrg(n); if( lrg!=null ) return lrg; - lrg = new LRG(_lrg_num++); + lrg = new LRG(_lrg_num++, fun); LRG old = _lrgs.put(n,lrg); assert old==null; return lrg; } // LRG for n - LRG lrg( Node n ) { + public LRG lrg( Node n ) { LRG lrg = _lrgs.get(n); if( lrg==null ) return null; LRG lrg2 = lrg.find(); @@ -142,18 +145,19 @@ public class RegAlloc { } // Printable register number for node n - String reg( Node n ) { return reg(n,null); } - String reg( Node n, FunNode fun ) { + String reg( Node n ) { LRG lrg = _lrg(n); - if( lrg==null ) return null; + return lrg==null ? null : reg(lrg); + } + String reg( LRG lrg ) { // No register yet, use LRG if( lrg._reg == -1 ) return "V"+lrg._lrg; // Chosen machine register unless stack-slot and past RA String[] regs = _code._mach.regs(); - if( lrg._reg < regs.length || _code._phase.ordinal() <= CodeGen.Phase.RegAlloc.ordinal() || fun==null ) + if( lrg._reg < regs.length || _code._phase.ordinal() <= CodeGen.Phase.RegAlloc.ordinal() || lrg._fun==null ) return RegMask.reg(regs,lrg._reg); // Stack-slot past RA uses the frame layout logic - return "[rsp+"+fun.computeStackOffset(_code,lrg._reg)+"]"; + return "[rsp+"+lrg._fun.computeStackOffset(_code,lrg._reg)+"]"; } // ----------------------- @@ -179,8 +183,7 @@ public class RegAlloc { for( Node n : bb._outputs ) if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } - - // Optional diagnostic for values accidentally shared across functions. + // Expensive assert: useful when chasing cross-function allocator edges. //assert verifyFunctionLocalEdges(); // Top driver: repeated rounds of coloring and splitting. @@ -192,23 +195,66 @@ public class RegAlloc { round++; } postColor(); // Remove no-op spills + _done = true; } boolean verifyFunctionLocalEdges() { - for( CFGNode bb : _code._cfg ) { - if( bb instanceof StartNode ) continue; - FunNode fun = bb.fun(); - for( Node use : bb._outputs ) - if( use instanceof MachNode mach && !(use instanceof ParmNode) ) - for( int i=1; i<use.nIns(); i++ ) { - Node def = use.in(i); - if( def==null || mach.regmap(i)==null || def.cfg0()==null || def.cfg0() instanceof StartNode ) continue; - assert def.cfg0().fun()==fun : "Cross-function register edge: "+def.uniqueName()+" -> "+use.uniqueName()+" input "+i; - } - } + for( CFGNode bb : _code._cfg ) + for( Node use : bb._outputs ) { + FunNode useFun = funOf(use); + for( int i=1; i<use.nIns(); i++ ) { + Node def = use.in(i); + if( def==null || def.isConst() || allowedCrossFunctionEdge(use,i,def) ) + continue; + FunNode defFun = funOf(def); + if( defFun != null && useFun != null && defFun != useFun ) + throw new AssertionError(crossFunctionMessage(def,defFun,use,useFun,i)); + } + } return true; } + private static String crossFunctionMessage(Node def, FunNode defFun, Node use, FunNode useFun, int idx) { + StringBuilder sb = new StringBuilder("Cross-function value edge: "); + sb.append(def.uniqueName()).append("(").append(defFun.label()).append(") -> ") + .append(use.uniqueName()).append("(").append(useFun.label()).append(") input ").append(idx) + .append(" def=").append(def).append(" use=").append(use).append("\n all uses:"); + for( Node out : def.outs() ) { + FunNode outFun = funOf(out); + sb.append("\n ").append(out.uniqueName()).append("(") + .append(outFun==null ? "?" : outFun.label()).append(")"); + } + return sb.toString(); + } + + private static boolean allowedCrossFunctionEdge(Node use, int idx, Node def) { + // Function metadata/control edges are not value live ranges. + if( use instanceof FunNode || use instanceof StopNode || use instanceof StopCUNode ) + return true; + // Return-linked function pointers carry function identity/lifetime, not + // an allocator value flowing from the callee body into this function. + if( use instanceof FunPtrNode && def instanceof ReturnNode ) + return true; + // Parm defaults and call-linked argument edges are the entry protocol; + // BuildLRG also skips Parm input 1. + if( use instanceof ParmNode ) + return true; + // Linked CallEnd -> Return edges should be gone before RegAlloc, but + // diagnose allocator value edges rather than call graph metadata here. + if( use instanceof CallEndNode && def instanceof ReturnNode ) + return true; + return false; + } + + private static FunNode funOf(Node n) { + if( n instanceof ParmNode parm ) return parm.fun(); + if( n instanceof ReturnNode ret ) return ret.fun(); + if( n instanceof FunNode fun ) return fun; + if( n instanceof CFGNode cfg ) return cfg.fun(); + CFGNode cfg = n.cfg0(); + return cfg==null ? null : cfg.fun(); + } + private boolean graphColor(byte round) { _failed.clear(); _lrgs.clear(); @@ -252,7 +298,7 @@ public class RegAlloc { // Register mask when empty; split around defs and uses with limited // register masks. - if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { + if( lrg._mask.isEmpty() ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && (lrg._1regDefCnt + lrg._1regUseCnt) > 0 && @@ -265,6 +311,10 @@ public class RegAlloc { if( splitEmptyMaskByUse(round,lrg) ) return true; } + if( lrg._mask.isEmpty() && lrg._multiDef && lrg._1regUseCnt > 1 && lrg._1regDefCnt <= 1 ) { + if( splitEmptyMaskSingleUses(round,lrg) ) + return true; + } // Generic split-by-loop depth. return splitByLoop(round,lrg); @@ -277,18 +327,20 @@ public class RegAlloc { // single-register. Split after the def and before the use. Does not // require a full pass. + // Compute def nOuts *before* replacing those uses with a split + int defNouts = ((Node)lrg._machDef).nOuts(); // Split just after def if( lrg._1regDefCnt==1 && !lrg._machDef.isClone() ) - // An earlier copy is reusable only if no intervening clobber. - // Being in the same block alone is insufficient. Example: + // Force must-split, even if a prior split same block because register + // conflicts. Example: // alloc // V1/rax - forced by alloc // alloc // V2/rax - kills prior RAX // st4 [V1],len - No good, must split around - insertAfterAndReplace(makeSplit("def/empty1",round,lrg),(Node)lrg._machDef,false); + insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/); // Split just before use - if( lrg._1regUseCnt==1 ) + if( lrg._machUse!=null && (lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && defNouts==1)) ) insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg); return true; } @@ -331,6 +383,27 @@ public class RegAlloc { return true; } + // Empty-mask live range with several direct single-register uses, often + // through a Phi with multiple defs. Split those uses directly instead of + // doing a loop-depth split, which might keep isolating the wrong edge. + boolean splitEmptyMaskSingleUses( byte round, LRG lrg ) { + findAllLRG(lrg); + if( _ns._len <= 5 ) + return false; + boolean progress = false; + for( Node n : _ns ) { + if( !(n instanceof MachNode mach) ) continue; + for( int i=1; i<n.nIns(); i++ ) { + RegMask use = mach.regmap(i); + if( use != null && use.size1() && lrg(n.in(i))==lrg ) { + insertBefore(n,i,"use/emptyN",round,lrg); + progress = true; + } + } + } + return progress; + } + // Narrowing preserves all earlier users of a class; new classes are disjoint. // Each use contains its first overlapping class, so one pass suffices. private static void putIntoRegClass( Ary<RegMask> rclass, RegMask rmask ) { @@ -439,9 +512,11 @@ public class RegAlloc { int min = (int)ld; int max = (int)(ld>>32); - - // If the minLoopDepth is less than the maxLoopDepth: for-all defs and - // uses, if at minLoopDepth or lower, split after def and before use. + boolean emptyMulti = lrg._mask.isEmpty() && lrg._multiDef && lrg._1regDefCnt <= 1 && + (lrg._1regUseCnt > 1 || _ns._len > 5); + // Multi-def empty-mask conflicts need the hot/deep side isolated from + // fixed register uses. Ordinary pressure splits keep the old shallow + // boundary behavior. for( Node n : _ns ) { if( n instanceof SplitNode && min!=max ) continue; // Ignoring splits; since spilling need to split in a deeper loop if( n.isDead() ) continue; // Some Cloneable went dead by other spill changes @@ -452,7 +527,7 @@ public class RegAlloc { if( lrg(n)==lrg && // This is a LRG def // At loop boundary, or splitting in inner loop - (min==max || n.cfg0().loopDepth() <= min) ) { + (min==max || (emptyMulti ? n.cfg0().loopDepth() >= max : n.cfg0().loopDepth() <= min)) ) { // Cloneable constants will be cloned at uses, not after def if( !(n instanceof MachNode mach && mach.isClone()) && // Single user is already a split adjacent @@ -467,7 +542,7 @@ public class RegAlloc { // No split in front of a split if( !(n.in(i) instanceof SplitNode) && // splitting in inner loop or at loop border - (min==max || phi.region().cfg(i).loopDepth() <= min) && + (min==max || (emptyMulti ? phi.region().cfg(i).loopDepth() >= max : phi.region().cfg(i).loopDepth() <= min)) && // and not around the backedge of a loop (bad place to force a split, hard to remove) !(phi.region() instanceof LoopNode && i==2 && (phi.in(i) instanceof PhiNode pp && pp.region()==phi.region())) ) // Split before phi-use in prior block @@ -479,7 +554,8 @@ public class RegAlloc { // This is a LRG use // splitting in inner loop or at loop border if( lrgSame( n.in( i ), lrg ) && - (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || n.cfg0().loopDepth() <= min) ) + (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || + (emptyMulti ? n.cfg0().loopDepth() >= max : n.cfg0().loopDepth() <= min)) ) // Split before in this block insertBefore( n, i, "use/loop/use", round,lrg, false ); } @@ -528,8 +604,8 @@ public class RegAlloc { void findAllLRG( LRG lrg ) { _ns.clear(); int wd = 0; - if( lrg._machDef!=null ) _ns.push((Node)lrg._machDef); - if( lrg._machUse!=null ) _ns.push((Node)lrg._machUse); + if( lrg._machDef != null ) _ns.push((Node)lrg._machDef); + if( lrg._machUse != null ) _ns.push((Node)lrg._machUse); while( wd < _ns._len ) { Node n = _ns.at(wd++); if( lrg(n)!=lrg ) continue; @@ -590,12 +666,12 @@ public class RegAlloc { // Clone simple constants if possible Node split = def instanceof MachNode mach && mach.isClone() && (umask==null || mach.outregmap().overlap(umask)) ? mach.copy() - : _code._mach.split(kind,round,lrg); + : _code._mach.split(lrg,kind,round); _lrgs.put(split,lrg); return split; } private SplitNode makeSplit( String kind, byte round, LRG lrg ) { - SplitNode split = _code._mach.split(kind,round,lrg); + SplitNode split = _code._mach.split(lrg,kind,round); _lrgs.put(split,lrg); return split; } @@ -699,6 +775,6 @@ public class RegAlloc { if( clobbers(n,defreg) ) return false; // Clobbered } - throw Utils.TODO(); + throw Utils.TODO("Should not reach here"); } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index 303bba9e..9cb9ec16 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -33,7 +33,6 @@ public class RegMask { public RegMask(long bits ) { _bits0 = bits; } public RegMask(long bits0, long bits1 ) { _bits0 = bits0; _bits1 = bits1; } public RegMask(RegMask r) { _bits0 = r._bits0; _bits1 = r._bits1; } - private RegMask() { _bits0 = _bits1 = 0; } // AND, with copy-on-write if changing RegMask and( RegMask mask ) { diff --git a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java new file mode 100644 index 00000000..27253c5e --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -0,0 +1,614 @@ +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.*; +import java.util.*; + +abstract public class Serialize { + + static void serialize( CodeGen code ) { + + // Get all Nodes in a sane order + Ary<Node> nodes = nodeOrder(code); + + // Array of dependent file names + HashSet<String> xdeps = new HashSet<>(); + for( CompUnit cu : code._compunits.values() ) { + if( cu._deps != null ) + for( CompUnit cudep : cu._deps ) + xdeps.add(cudep._fname); + } + String[] deps = xdeps.toArray(new String[xdeps.size()]); + + // Top-level clazz being reported + String topName = code._srcName == null ? "Test" : code._srcName; + CompUnit top = code._compunits.get(topName); + TypeStruct clz = top._clz; + + // Preserve which same-named structs are the source-level declarations. + // Optimized graph types can carry sharper field states (e.g. len==0), + // and cannot be used to reconstruct this mapping during loading. + TreeMap<String,TypeStruct> named = new TreeMap<>(); + for( Type type : Parser.TYPES.values() ) + if( type instanceof TypeStruct ts ) + named.put(ts._name,ts); + TypeStruct[] pubTypes = named.values().toArray(new TypeStruct[0]); + + // Compress into bytes + BAOS baos = write(nodes, clz, pubTypes, deps, code._aliases, code._fidxs, code._rpcs, code._externFunc); + + // --- Expensive bijection assert + if( false ) { + // Inflate into POJOs; renumbers everything + ElfReader elf = new ElfReader(new BAOS(baos.toByteArray())); + readAll(code,elf, code._aliases, code._fidxs, code._rpcs); + BAOS baos2 = write(elf._nodes,elf._clz,elf._pubTypes,elf._deps, code._aliases, code._fidxs, code._rpcs, code._externFunc); + + // Bi-jection + for( int i=0; i<baos.size(); i++ ) + assert baos.buf()[i]==baos2.buf()[i] : "bijection mismatch at "+i+": "+(baos.buf()[i]&0xFF)+" != "+(baos2.buf()[i]&0xFF); + assert baos.size()==baos2.size() : "bijection size mismatch: "+baos.size()+" != "+baos2.size(); + } + // --- Expensive bijection assert + + // Record serialized IR for later ELF writing + code._serial = baos; + } + + // -------------------------------------------------- + static BAOS write(Ary<Node> nodes, TypeStruct clz, TypeStruct[] pubTypes, String[] depobjs, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs, HashMap<Integer,String> externFunc) { + // Initialize the mapping from bits/tags to types + Type.TAGOFFS(); + + BAOS baos = new BAOS(); + // A - Print the C0DE header. The format is not versioned yet. + baos.write('C').write('0').write('D').write('E'); + + // Count unique Types + var types = new HashMap<Type,Integer>(); + // Count published types *first*, so can align with published strings + types.put(Type.TOP,0); + types.put( clz, types.size() ); + // Have to visit the innards specially, since they did not get the + // normal recursive visit when first touching a type, because the + // published types are packed early to align with their string names so + // lookup in ElfReader can be fast. + for( int i=0; i<clz.nkids(); i++ ) + clz.at(i).gather(types); + // Gather types from all sources + for( Node n : nodes ) { + n._type.gather(types); + if( n instanceof CallEndNode cend ) cend._rpc.gather(types); + if( n instanceof FunNode fun ) fun.sig().gather(types); + if( n instanceof ParmNode parm ) parm._declaredType.gather(types); + if( n instanceof TypeNode con ) con._con .gather(types); + } + // Only record canonical declarations already reachable from this + // object's graph. Pulling unrelated parser types into this closure + // can include open or partially built types from other units. + Ary<TypeStruct> writtenPubs = new Ary<>(TypeStruct.class); + for( TypeStruct ts : pubTypes ) + if( types.containsKey(ts) ) + writtenPubs.add(ts); + // Radix sort by Type ID# + Type[] atypes = new Type[types.size()]; + for( Type t : types.keySet() ) + atypes[types.get(t)] = t; + + // Count all unique Strings + var strs = new HashMap<String,Integer>(); + strs.put("",0); // Null string is always 0 + // Find and count *published* Strings first + gather(strs,clz._name); + // Find and count dependent object file string names + if( depobjs != null ) + for( String fname : depobjs ) + gather(strs,fname); + // Count strings from all types + for( Type t : atypes ) { + if( t instanceof Field fld ) gather(strs,fld._fname); + if( t instanceof TypeStruct ts ) gather(strs,ts . _name); + } + // Count strings used by local->global bit mappings. + aliases.gather(strs); + fidxs .gather(strs); + rpcs .gather(strs); + for( String extern : externFunc.values() ) + gather(strs,extern); + // Count strings from nodes + for( Node n : nodes ) + n.gather(strs); + // Radix sort by string ID# + String[] astrs = new String[strs.size()]; + for( String s : strs.keySet() ) + astrs[strs.get(s)] = s; + + // Check that published strings and types align + assert astrs[1] == ((TypeStruct)atypes[1])._name; + if( depobjs != null ) + for( int i=0; i<depobjs.length; i++ ) + assert astrs[1+i+1] == depobjs[i]; + + + // B - Write unique strings + baos.packed4(depobjs==null ? 0 : depobjs.length); + baos.packed4(strs.size()); + // Write in ID# order; the first depobjs.length of these are dependent strings + for( String s : astrs ) + baos.packedS(s); + + // B.2 - Write the local->global mappings + aliases.packed(baos,strs); + fidxs .packed(baos,strs); + rpcs .packed(baos,strs); + ArrayList<Integer> externFidxs = new ArrayList<>(externFunc.keySet()); + Collections.sort(externFidxs); + baos.packed2(externFidxs.size()); + for( int fidx : externFidxs ) { + baos.packed2(fidx); + baos.packed2(strs.get(externFunc.get(fidx))); + } + + // C - Write unique Types + baos.packed4(atypes.length); + baos.packed2(writtenPubs._len); + for( TypeStruct ts : writtenPubs ) + baos.packed4(types.get(ts)); + // Write Types in ID# order, no children + for( Type t : atypes ) + t.packed(baos,strs); + // Write Types in ID# order, only child IDs + for( Type t : atypes ) { + int nkids = t.nkids(); + for( int i=0; i<nkids; i++ ) + baos.packed4(types.get(t.at(i))); + } + + + // D - Write the nodes. Since this is expected to be the bulk of the + // data, we might want to explore various options. + + // How many nodes? + baos.packed4(nodes._len); + + // Radix sort by Node ID#, new compressed NIDs + IdentityHashMap<Node,Integer> anodes = new IdentityHashMap<>(); + for( Node n : nodes ) + anodes.put(n,anodes.size()+1); // +1 bias, reserve 0 for null + // First cut: 1 byte opcode, optional per-node info, includes variable nIns + for( Node n : nodes ) { + baos.packed1(n.serialTag().ordinal()); + baos.packed2(types.get(n._type)); + n.packed(baos,strs,types,anodes); + } + // Write out the input indices packed. + for( Node n : nodes ) { + for( int j=0; j<n.nIns(); j++ ) { + Node def = n.in(j); + Integer idx = def==null ? Integer.valueOf(0) : anodes.get(def); + assert idx != null : "Missing serialized input for "+n+" input "+j+" def "+def; + baos.packed2(idx); + } + if( n instanceof FunNode fun ) + baos.packed2(anodes.get(fun.ret())); + } + + return baos; + } + public static <T> void gather( HashMap<T,Integer> strs, T s) { + if( s!=null && !strs.containsKey(s) ) + strs.put(s,strs.size()); + } + public static void gather( AryInt is, int s) { + if( is.atX(s)==0 ) { + int cnt=0; + for( int i=1; i<is._len; i++ ) + if( is._es[i] != 0 ) + cnt++; + is.setX(s,cnt+1); + } + } + + // Returned array of *public* strings only. + static void read_public_strs(ElfReader elf) { + BAOS bais = elf._bais; + Type.TAGOFFS(); + + // A - Read a header + if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='E' ) + throw new IllegalArgumentException("Unsupported serialized IR format; rebuild the object file"); + + // B - Packed read of #strings, then strings + int ndependents = bais.packed4(); // Number of dependent object files + int nstrs = bais.packed4(); // Total number of strings + String[] strs = new String[nstrs]; + for( int i=0; i<nstrs; i++ ) + strs[i] = bais.packedS(); + elf._strs = strs; + + // Collect dependent file names + elf._deps = new String[ndependents]; + for( int i=0; i<ndependents; i++ ) + elf._deps[i] = strs[1+i+1]; + } + + // -------------------------------------------------- + record TypeRead(Type[] types, String[] strs, GlobalBits fileAliases, GlobalBits fileFidxs, GlobalBits fileRpcs) {} + + static TypeRead readTypes( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { + BAOS bais = elf._bais; + // Initialize the mapping from bits/tags to types + Type.TAGOFFS(); + + // If not read the strings already, read them now + String[] strs = elf._strs; + if( strs == null ) { + // A - Read a header + if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != 'E' ) + throw new IllegalArgumentException( "Unsupported serialized IR format; rebuild the object file" ); + + // B - Packed read of #strings, then strings + int ndependents = bais.packed4(); // Number of dependent object files + int nstrs = bais.packed4(); // Total number of strings + elf._strs = strs = new String[nstrs]; + for( int i = 0; i < nstrs; i++ ) + strs[i] = bais.packedS(); + + // Collect dependent file names + elf._deps = new String[ndependents]; + for( int i = 0; i < ndependents; i++ ) + elf._deps[i] = strs[1 + i + 1]; + } + + // B.2 - Read the local->global mappings. Further down we will map + // Elf file-local -> global, then global -> CodeGen.CODE local + GlobalBits fileAliases = GlobalBits.packed(bais,strs); + GlobalBits fileFidxs = GlobalBits.packed(bais,strs); + GlobalBits fileRpcs = GlobalBits.packed(bais,strs); + int nexterns = bais.packed2(); + for( int i=0; i<nexterns; i++ ) { + int fileFidx = bais.packed2(); + String extern = strs[bais.packed2()]; + int fidx = fileFidx < GlobalBits.RESERVED ? fileFidx : fidxs.map(fileFidxs,fileFidx); + String old = code.externFunc(fidx); + if( old == null ) + code.externFunc(fidx,extern); + else + assert old.equals(extern); + } + + + // C - Packed read of #types, then types + int ntypes = bais.packed4(); + int npubTypes = bais.packed2(); + int[] pubTypeIds = new int[npubTypes]; + for( int i=0; i<npubTypes; i++ ) + pubTypeIds[i] = bais.packed4(); + Type[] types = Type.packed(bais,strs,ntypes, Parser.TYPES, + fileAliases,aliases, + fileFidxs ,fidxs, + fileRpcs ,rpcs); + + // aliases.set(0,0); + // Check and collect first published symbols map to TypeStructs + elf._clz = (TypeStruct)types[1/*skip zero*/]; + assert elf._clz._name==strs[1/*skip null ptr*/]; + for( Type type : types ) + if( type instanceof TypeStruct ts ) + Parser.TYPES.put(ts._name,ts); + for( Type type : types ) { + if( !(type instanceof TypeStruct ts) || !Parser.startsClzPrefix(ts._name) ) + continue; + String cname = ts._name.substring(Parser.CLZ.length()); + int dot = cname.lastIndexOf('.'); + String name = dot == -1 ? cname : cname.substring(dot+1); + Field inst = ts.field(name.intern()); + if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMem mem && mem._t instanceof TypeStruct its ) + Parser.TYPES.put(cname,its); + } + elf._pubTypes = new TypeStruct[npubTypes]; + for( int i=0; i<npubTypes; i++ ) { + TypeStruct ts = elf._pubTypes[i] = (TypeStruct)types[pubTypeIds[i]]; + Parser.TYPES.put(ts._name,ts); + } + return new TypeRead(types,strs,fileAliases,fileFidxs,fileRpcs); + } + + static void readAll( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { + BAOS bais = elf._bais; + TypeRead tread = readTypes(code, elf, aliases, fidxs, rpcs); + Type[] types = tread.types(); + String[] strs = tread.strs(); + GlobalBits fileAliases = tread.fileAliases(); + + // D - Read the nodes + + // Number of nodes + int num = bais.packed4(); + // Packed array of nodes + Ary<Node> nodes = new Ary<>(Node.class); + CompUnit cu = null; + for( int i=0; i<num; i++ ) { + Node.Tag tag = Node.Tag.VALS[bais.packed1()]; + Type t = types[bais.packed2()]; + Node n = tag.make(bais,strs,types,fileAliases,aliases); + n._type = t; + nodes.push(n); + // A little extra for FunNodes + if( n instanceof StartCUNode startcu ) { + cu = code._compunits.get(startcu._fname==null ? (code._srcName==null ? "Test" : code._srcName) : startcu._fname); + assert cu != null; + } + if( n instanceof StopCUNode stopcu ) { + cu = null; + } + if( n instanceof FunNode fun ) { + assert cu != null; + fun._compunit = cu; + } + if( n instanceof ExternNode ext && ext._con instanceof TypeFunPtr tfp && tfp.isConstant() ) { + String old = code.externFunc(tfp.fidx()); + if( old == null ) + code.externFunc(tfp.fidx(), ext._extern); + else + assert old.equals(ext._extern); + } + } + + // Node edges + for( Node n : nodes ) { + int len = n.nIns(); + for( int i=0; i<len; i++ ) { + 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. + int local = i; + if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { + if( def == null ) continue; + local = aliases.map(fileAliases,i); + } + n.setDefX(local,def); + // Call's output[0] is always the CallEnd + if( n instanceof CallEndNode cend && i==0 ) { + var outs = cend.call()._outputs; + outs.swap(0,outs._len-1); + } + } + // A little extra for FunNodes + if( n instanceof FunNode fun ) { + // Return is hooked like an edge + ReturnNode ret = (ReturnNode)nodes.at(bais.packed2()-1); + fun.setRet(ret); + ret._fun = fun; + } + } + // Add edge from Start to Stop + StartNode start = (StartNode)nodes.at(0); + StopNode stop = (StopNode)nodes.last(); + start.setDef(1,stop); + + assert check(code,nodes); + elf._nodes = nodes; + } + + // Check loaded types and nodes are consistent + private static boolean check( CodeGen code, Ary<Node> nodes ) { + // Loaded nodes are complete, unlike nodes still being built by the + // parser. Recompute them with post-parse semantics. The compilation- + // unit Stop is the exception: its escape type depends on the complete + // program's public interface, which ParseAll freezes only after every + // compilation unit has been loaded. + boolean good = true; + CodeGen.Phase phase = code._phase; + code._phase = CodeGen.Phase.Opto; + try { + for( Node n : nodes ) { + if( n instanceof StopCUNode && !code.publicInterfaceFrozen() ) + continue; + Type nval = n.compute(); + if( nval != n._type ) { + System.err.println("Node "+n+" read in as "+n._type+" but computes as "+nval); + good = false; + } + } + } finally { + code._phase = phase; + } + return good; + } + + // -------------------------------------------------- + public static Ary<Node> nodeOrder( CodeGen code, CompUnit cu ) { + assert code._start._ltree != null; // Uses loop tree + BitSet visit = code.visit(); + Ary<Node> nodes = new Ary<>(Node.class); + visit.set(code._stop._nid); + // Walk all listed functions, in this single compilation unit + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && fun._compunit == cu ) + _funWalk(fun,nodes,visit); + + // Just constants used by the listed functions + Ary<Node> cons = new Ary<>(Node.class); + cons.add(code._start); + for( Node n : code._start._outputs ) { + if( n instanceof ConstantNode con && !visit.get(con._nid) ) { + for( Node use : con.outs() ) { + // PtrToInt is another zero-code value rooted at a global + // constant. Its array-body Add is the value used by the + // function, so include that extra link in the ownership + // test as well. + if( use instanceof PtrToIntNode ptr ) + for( Node add : ptr.outs() ) { + for( Node addUse : add.outs() ) + conUsed(add,addUse,visit,cons); + conUsed(ptr,add,visit,cons); + } + // Constant used by somebody, so flag for output + conUsed(con,use,visit,cons); + } + } + } + // StartCU and memory projection + cons.add(cu._start); + for( Node n : cu._start._outputs ) + if( n instanceof ProjNode ) cons.add(n); + // All the innards of functions + cons.addAll(nodes); + // StopCU, Stop + cons.add(cu._stop); + cons.add(code._stop); + visit.clear(); + return cons; + } + + private static void conUsed( Node con, Node use, BitSet visit, Ary<Node> cons ) { + if( use == null || !visit.get(use._nid) || visit.get(con._nid) ) return; + cons.add(con); + visit.set(con._nid); + } + + // -------------------------------------------------- + public static Ary<Node> nodeOrder( CodeGen code ) { + assert code._start._ltree != null; // Uses loop tree + Ary<Node> nodes = new Ary<>(Node.class); + BitSet visit = code.visit(); + nodes.add(code._start); + + // All the global constants + for( Node n : code._start._outputs ) { + if( n.isConst() ) { + visit.set( n._nid ); + nodes.add( n ); + // Special for Cast:BOT + for( Node cast : n._outputs ) + if( cast != null && cast.nIns() == 2 && cast.in( 0 ) == null ) { + visit.set( cast._nid ); + nodes.add( cast ); + // Array pointer conversion adds the body offset after + // the zero-code PtrToInt. Both nodes are global-value + // descendants of the constant and otherwise have no + // function-local root from which to walk them. + if( cast instanceof PtrToIntNode ) + for( Node add : cast.outs() ) + if( add instanceof AddNode && !visit.get(add._nid) ) { + visit.set(add._nid); + nodes.add(add); + } + } + } + } + + // All the CompUnits + for( CompUnit cu : code._compunits.values() ) { + // Whole CompUnits have no users, went dead + if( cu._start != null && !cu._start.isDead() ) { + nodes.add(cu._start); + // Memory proj + nodes.add(cu._start.proj(1)); + // All the functions, including internal ones, in comp-unit order + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && fun._compunit == cu ) + _funWalk(fun,nodes,visit); + nodes.add(cu._stop); + } + } + + nodes.add(code._stop); + visit.clear(); + return nodes; + } + + // Walk and print whole functions at a time, in CG order + private static void _funWalk( FunNode fun, Ary<Node> rpo, BitSet visit ) { + int start = rpo._len; + _funRPO(fun,rpo,visit); + int len = rpo._len - start; + for( int i=0; i< len>>1; i++ ) + rpo.swap(start+i,start+len-1-i); + } + + // Walk and gather RPO nodes. + private static void _funRPO(Node n, Ary<Node> rpo, BitSet visit ) { + if( visit.get(n._nid) ) return; // Been there, done that + visit.set(n._nid); // Stop recursion + // Walk outputs ordered + if( n instanceof CFGNode ncfg ) { + // If nodes walk outer loops before inner, so they hit the + // Return first, so Return is at the bottom of the RPO. + if( n instanceof IfNode iff ) { + CProjNode c0 = iff.cproj(0); + CProjNode c1 = iff.cproj(1); + if( c0._ltree.depth() > c1._ltree.depth() ) + { c0 = c1; c1 = iff.cproj(0); } + _funRPO(c0,rpo,visit); + _funRPO(c1,rpo,visit); + } else if( n instanceof StopNode ) { + // nothing + } else { + // CFG to CFG before CFG to data + for( Node use : n._outputs ) + if( use instanceof CFGNode usecfg && !ncfg.skip(usecfg) ) // Do not walk from Call to Fun + _funRPO(use,rpo,visit); + } + // Walk CFG to data eventually + for( Node use : n._outputs ) + if( !(use instanceof CFGNode) ) + _funRPO(use,rpo,visit); + } else { + // Do not walk from a non-CFG to a CFG; CFGs walk to CFGs to + // preserve CFG order. Do not walk *into* Phis; wait for the + // Region to walk the Phis (otherwise you visit some of the + // Phis ahead of others forcing the Phis to be spread around). + for( Node use : n._outputs ) { + if( use!=null && !(use instanceof CFGNode) && !(use instanceof PhiNode) ) + _funRPO(use,rpo,visit); + } + } + + // If parent is a Multi, do not add (yet). + // If self is a Multi, add self and children. + if( multiChild(n) || n instanceof CallEndNode ) { + // nothing; delay until Multi-head or CallNode + } else if( n instanceof MultiNode ) { + // Now lump all multi/projections together + printMulti(n,rpo); + } else if( n instanceof CallNode call ) { + printMulti(call.cend(),rpo); + rpo.add(call); + } else if( n instanceof RegionNode ) { + // Now lump all Phis together + int old = rpo._len; + for( Node use : n._outputs ) + if( use instanceof PhiNode ) + rpo.add(use); + // Sort by label? Want Phis before control outputs + Arrays.sort( rpo._es, old, rpo._len, (x,y) -> y.label().compareTo(x.label()) ); + rpo.add(n); + } else if( n instanceof StopNode ) { + // nothing + } else { + rpo.add(n); // Post-order add + } + } + + private static boolean multiChild(Node n) { + return n instanceof Proj || n instanceof PhiNode; + } + + private static void printMulti(Node n, Ary<Node> rpo) { + // Now lump all multi/projections together + for( Node use : n._outputs ) + rpo.add(use); + // Sort by projection order + if( !(n instanceof StartNode) ) + Arrays.sort( rpo._es,rpo._len-n.nOuts(),rpo._len, + (x,y) -> x instanceof ProjNode px && y instanceof ProjNode py ? (py.idx() - px.idx()) : (y._nid - x._nid) ); + rpo.add(n); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java new file mode 100644 index 00000000..f9f16008 --- /dev/null +++ b/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); + } +} |