summaryrefslogtreecommitdiff
path: root/src/main/java/com/seaofnodes/simple/codegen
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-08-10 11:11:18 -0700
committerCliff Click <cliffc@acm.org>2026-10-24 15:56:44 -0700
commit741d78b6e840c88b7b183010c812ad982b342da1 (patch)
tree84a75eb7ad351bffd20cd5fb152bab032b74271c /src/main/java/com/seaofnodes/simple/codegen
parent8d90d2292bbdb23596849c3c3d1cda2f6cad783e (diff)
downloadSimple-linear-chapter28a.tar.gz
Simple-linear-chapter28a.zip
Chapter 28a: Modules and Lazy Class Initializationlinear-chapter28a
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki <jun784@gmail.com> Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/codegen')
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java20
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java214
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/CodeGen.java597
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/CompUnit.java98
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/ElfExpr.java87
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/ElfFile.java382
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java460
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/Encoding.java371
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java90
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java57
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java71
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/IFG.java91
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/InstSelect.java80
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/Iter.java38
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/LRG.java7
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/LinkMem.java22
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/LocalIds.java33
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/Machine.java26
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/Opto.java218
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/ParseAll.java285
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java2
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java150
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/RegMask.java1
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/SourceError.java49
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/StaticData.java177
-rw-r--r--src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java61
27 files changed, 2532 insertions, 1157 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/ClassInitDependencies.java b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
new file mode 100644
index 00000000..6c70b71d
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
@@ -0,0 +1,214 @@
+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.*;
+
+// Search for Class Initialization Cycles.
+
+// Done after Opto, so dead code does not make a cycle.
+
+// Build the inits-graph, a call-graph plus CLInits plus class parents.
+
+// (1) Scan all functions f, building _edges[f][]: the set of <cinit> fcns from
+// CompUnits from CLInitNodes, and the set of fcn call targets in f and the
+// class parent. These are all reported as fidxs (ints).
+//
+// (2) Walk the _edges graph using Tarjans SCC. Reject cycles containing more
+// than one <clinit>.
+//
+// (3) Report on <clinit> cycles
+//
+public class ClassInitDependencies {
+ private final CodeGen _code;
+ // Function FIDX -> callees, touched initializers, and parent initializer.
+ public final int[][] _edgess;
+ private final int[] _pres;
+ private final int[] _lows;
+ private final int[] _stk ;
+ private int _sp;
+
+
+ // Build once; tests can inspect the graph independently of cycle checking.
+ public ClassInitDependencies( CodeGen code ) {
+ _code = code;
+ assert code._phase.ordinal() >= CodeGen.Phase.IterPostOpto.ordinal();
+ _pres = new int[code._linker._len];
+ _lows = new int[code._linker._len];
+ _stk = new int[code._linker._len];
+
+ //
+ BitSet visit = code.visit(); // Visit set per-fcn
+ Ary<CFGNode> work = new Ary<>(CFGNode.class); // Worklist per-fcn
+ IntHashMap iset = new IntHashMap(0); // dedup hash set per-fcn
+ _edgess = new int[code._linker._len][];
+
+ // For all functions, build the _edges array
+ for( FunNode fun : code._linker )
+ if( fun!=null && !fun.isDead() )
+ // Visit function and collect direct class touches and callees
+ _edgess[fun.sig().fidx()] = walk(code,fun,work,iset,visit,null);
+ visit.clear();
+ }
+
+ // Return the outgoing init edge set for this function
+ private static int[] walk( CodeGen code, FunNode fun, Ary<CFGNode> work, IntHashMap iset, BitSet visit,
+ Ary<Parser.Lexer> sites) {
+ // Walk function body, looking for outgoing init edges
+ assert iset .isEmpty(); // int hash set for de-dup
+ assert visit.isEmpty(); // needs a visit set, because loops
+ assert work .isEmpty(); // needs a worklist, because DAG, parallel explore paths
+
+ // Children classes always dependent on parents
+ if( fun.isClz() && fun._compunit._par != null )
+ iset.put(code.link(fun._compunit._par).sig().fidx(),1);
+
+ work.push(fun);
+ while( !work.isEmpty() ) {
+ CFGNode cfg = work.pop();
+ if( visit.get(cfg._nid) ) continue; // Been there, done that
+ visit.set(cfg._nid);
+ assert !cfg._type.isHigh();
+ // Do not walk off end of function
+ if( cfg instanceof ReturnNode ) continue;
+
+ // CLInit adds a class init requirement to this function
+ // (plus all parent classes)
+ if( cfg instanceof CLInitNode init ) {
+ FunNode clz = code.link(init.cu()); // <clinit> referred to
+ iset.put(clz.sig().fidx(),1); // Add to edge set
+ if( sites!=null && sites.atX(clz.sig().fidx())==null ) sites.setX(clz.sig().fidx(),init._loc);
+ }
+
+ // Calls union all their fptr fidxs into the callee set
+ if( cfg instanceof CallNode call && call.fptr()._type instanceof TypeFunPtr fp ) {
+ assert !XInt.isHigh(fp.fidxs()) && fp.nfcns()>0; // Call is alive with valid targets
+ // Union call targets into the callee set
+ for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) ) {
+ iset.put(dstx,1);
+ if( sites!=null && sites.atX(dstx)==null ) sites.setX(dstx,call._loc);
+ }
+ }
+
+ // Forward recursion to walk the whole function
+ for( Node use : cfg._outputs ) {
+ // Do not walk into another function
+ if( !(use instanceof CFGNode cfg1) || use instanceof FunNode || use instanceof StopNode ) continue;
+ // Expect control flow edge is sensible
+ assert (use instanceof RegionNode r && r._inputs.find(cfg)>0) || use.in(0)==cfg;
+ if( !visit.get(cfg1._nid) ) // Small speed opt
+ work.add(cfg1);
+ }
+ }
+
+ visit.clear();
+ int[] edges = iset.isEmpty() ? null : iset.keySet();
+ iset.clear();
+ return edges;
+ }
+
+ // Return an error string, or null if no cycle contains multiple clinits.
+ public String check() {
+ Arrays.fill(_pres,0);
+ _sp = 0;
+ _pres[0] = 1; // Preorders stored in pres[0] and start at 1
+
+ int idx = -1;
+ for( int fidx = 1; fidx < _edgess.length; fidx++ )
+ if( _pres[fidx] == 0 && // Already visited
+ (idx = scc(fidx)) != -1 ) // And found a cycle
+ return report(idx); // Report cycle
+ return null;
+ }
+
+ // Every internal edge of an SCC belongs to a cycle. Print all of them:
+ // stack order is not a path, and enumerating all cycle paths can explode.
+ // This bookkeeping and formatting are only needed on an error.
+ private String report(int idx) {
+ BitSet members = new BitSet();
+ for( int i=idx; i<_sp; i++ ) members.set(_stk[i]);
+ SB sb = new SB().p("Cyclic class initialization:");
+ // Recover one surviving source site per edge only after finding an
+ // error. A representative touch is enough; runtime first-touch order
+ // need not be statically known. Lexer snapshots retain the source CU
+ // even when the node has been inlined into a different function.
+ Ary<CFGNode> work = new Ary<>(CFGNode.class);
+ IntHashMap iset = new IntHashMap(0);
+ BitSet visit = new BitSet();
+ Ary<Parser.Lexer> sites = new Ary<>(Parser.Lexer.class);
+ for( int i=idx; i<_sp; i++ ) {
+ int src = _stk[i];
+ FunNode fun = _code.link(src);
+ Arrays.fill(sites._es,null);
+ sites.clear();
+ walk(_code,fun,work,iset,visit,sites);
+ if( _edgess[src]!=null )
+ for( int dst : _edgess[src] )
+ if( members.get(dst) ) {
+ sb.p("\n ").p(name(src)).p(" -> ").p(name(dst));
+ Parser.Lexer loc = sites.atX(dst);
+ if( loc!=null && loc._cu!=null )
+ sb.p('\n').p(SourceError.format(loc._cu,loc.pos(),"cyclic class initialization"));
+ else if( fun.isClz() && fun._compunit._par==_code.link(dst)._compunit )
+ sb.p("\n parent initialization requirement");
+ }
+ }
+ return sb.toString();
+ }
+
+ private String name(int fidx) {
+ FunNode fun = _code.link(fidx);
+ String owner=fun._compunit._cname;
+ if( fun.isClz() ) return owner;
+ String label=fun.label();
+ return (label.startsWith(owner+".") ? label : owner+"."+label)+" [fidx "+fidx+"]";
+ }
+
+ // Tarjan SCC
+ int scc( int fidx ) {
+ // Assign pre-order number
+ _lows[fidx] = _pres[fidx] = _pres[0]++;
+ _stk[_sp++] = fidx;
+ // walk outbound edges
+ if( _edgess[fidx]!=null ) {
+ for( int edge : _edgess[fidx] ) {
+ if( edge >= _pres.length ) continue; // Out of bounds happens when calling C fcns
+ if( _pres[edge] == 0 ) { // Not visited
+ int idx = scc(edge);
+ if( idx != -1 ) return idx; // Found a cycle
+ _lows[fidx] = Math.min(_lows[fidx],_lows[edge]);
+ } else if( _edgess[edge]!=null && onStk(edge) ) {
+ _lows[fidx] = Math.min(_lows[fidx],_pres[edge]);
+ }
+ }
+ }
+ // Found a cycle
+ if( _lows[fidx] == _pres[fidx] ) {
+ int idx = find(fidx);
+ if( hasClzCycle(idx) )
+ return idx; // Found a class cycle
+ // Pop stack, including fidx
+ _sp = idx;
+ }
+ return -1; // No cycle
+ }
+
+ private int find(int e) {
+ for( int i=0; i<_sp; i++ ) if( _stk[i] == e ) return i;
+ return -1;
+ }
+ private boolean onStk(int e) { return find(e) != -1; }
+
+ private boolean hasClzCycle(int idx) {
+ int clinits = 0;
+ for( int i=idx; i<_sp; i++ ) {
+ FunNode fun = _code.link(_stk[i]);
+ if( fun!=null && fun.isClz() && ++clinits > 1 )
+ return true;
+ }
+ return false;
+ }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index d3895b08..e6bace8c 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -1,120 +1,322 @@
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 java.io.IOException;
+import com.seaofnodes.simple.util.*;
+import java.io.File;
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, // Build ideal IR from source
- Iter, // Pessimistic peepholes
- Opto, // Optimistic interprocedural SCCP
+ Parse, // Parse ASCII text into Sea-of-Nodes IR
+ Iter, // Pessimistic peepholes after parse
+ Opto, // SCCP, numeric modes, seed the peephole worklist
IterPostOpto, // Peepholes and inlining using SCCP results
- FinalizeIR, // Finish function cleanup and layouts
- TypeCheck, // Check the surviving ideal graph
- LoopTree, // Discover loops and connect nonreturning paths
- Select, // Select machine instructions
- Schedule, // Global code motion
- LocalSched, // Order instructions within blocks
- RegAlloc, // Assign registers and stack slots
- Encoding, // Encode instructions
- Export; // Link in memory or write ELF
-
+ FinalizeIR, // Field layout, offset cleanup, function/CU roots
+ TypeCheck, // Last check for bad programs
+ Lower, // Expand checked class initialization to ordinary IR
+ LoopTree, // Build a loop tree; break infinite loops
+ 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;
+ // Slashed path from source root to the entry file, without ".smp".
+ 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;
+
+ // Source files discovered in this invocation. All live initializers
+ // participate in cycle checking, including fully inlined bodies.
+ 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 class or instance field.
+ public boolean publicFIDX(int fidx) {
+ if( fidx < LocalIds.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;
+ // Include instance methods even while their constant function fields
+ // are stored in each instance rather than on the class object.
+ for( Type t : Parser.TYPES.values() )
+ if( t instanceof TypeStruct clz &&
+ Parser.startsClzPrefix(clz._name) &&
+ Parser.isPublicClassName(clz._name) &&
+ resolvedClass(clz) ) {
+ if( publicFieldFIDX(clz,fidx) ) return true;
+ Type self = Parser.TYPES.get(clz._name.substring(Parser.CLZ.length()));
+ if( self instanceof TypeStruct ts && publicFieldFIDX(ts,fidx) ) return true;
+ }
+ return false;
+ }
+
+ private static boolean publicFieldFIDX(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=LocalIds.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; }
- // Run through target, skipping phases already completed.
- public CodeGen driver(Phase target) { return driver(target,null,null); }
- public CodeGen driver(Phase target, String cpu, String callingConv) { return driver(target,cpu,callingConv,0); }
- public CodeGen driver(Phase target, String cpu, String callingConv, int dump) {
- if( target.ordinal()>=Phase.RegAlloc.ordinal() && cpu==null && _mach==null )
- throw new IllegalArgumentException("Machine code requires a CPU target");
- if( target==Phase.Export ) throw new IllegalArgumentException("Use exportELF with an output file or null for memory linking");
- step(target, Phase.Parse, this::parse, dump);
- step(target, Phase.Iter, this::iter, dump);
- step(target, Phase.Opto, this::opto, dump);
+ // ---------------------------
+
+ // Very common nodes, cached here
+ public final ConstantNode ZERO;
+ public final XCtrlNode XCTRL;
+
+ public Node constant( Type t ) {
+ assert _phase==null || _phase.ordinal() <= Phase.Lower.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)); }
+
+
+ // ---------------------------
+ // 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, 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, src, workListSeed, resetTypes, TypeInteger.BOT);
+ }
+
+ // Generic CodeGen, including full module setup
+ public CodeGen( String modDir, String buildDir,
+ 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( resetTypes ) Type.reset(); // Reset to recover from failed test
+
+ _cwd = System.getProperty("user.dir")+"/";
+ _modDir = modDir == null ? _cwd : modDir;
+ _buildDir = buildDir == null ? _cwd : buildDir;
+ _srcName = srcName;
+ _callingConv = null; // Calling convention
+ // Source code from test strings, not files
+ _src = src;
+ // 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);
+ }
+
+
+ // Run the requested phases. ELF output contains machine code and data.
+
+ // 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.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); }
+
+ // The Generic driver
+ public CodeGen driver( Phase target, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) {
+ // Parse the entry source and discover all referenced source files.
+ step(target, Phase.Parse, this::parse, dump);
+ // Run peepholes to a fixed point
+ step(target, Phase.Iter, this::iter, dump);
+ // Run SCCP (and resolve int/flt expressions)
+ step(target, Phase.Opto, this::opto, dump);
+ // Run peepholes to a fixed point again, on the better types.
step(target, Phase.IterPostOpto, this::iterPostOpto, dump);
- step(target, Phase.FinalizeIR, this::finalizeIR, dump);
- step(target, Phase.TypeCheck, this::typeCheck, dump);
- step(target, Phase.LoopTree, this::loopTree, dump);
+ // Field layouts; field symbols become constant offsets
+ step(target, Phase.FinalizeIR, this::finalizeIR, dump);
+ // Final error check - bad programs fail here
+ step(target, Phase.TypeCheck, this::typeCheck, dump);
+ // Replace "fat" nodes with their exploded explicit IR; this can
+ // introduce CFG diamonds
+ step(target, Phase.Lower, this::lower, dump);
+ // Compute the loop-tree, used for approximating exec frequencies for
+ // scheduling and register allocation
+ step(target, Phase.LoopTree, this::loopTree, dump);
+ // Instruction selection
step(target, Phase.Select, () -> instSelect(cpu,callingConv), dump);
- step(target, Phase.Schedule, this::GCM, dump);
- step(target, Phase.LocalSched, this::localSched, dump);
- step(target, Phase.RegAlloc, this::regAlloc, dump);
- step(target, Phase.Encoding, this::encode, dump);
+ // Global Code Motion
+ step(target, Phase.Schedule, this::GCM, dump);
+ // Local (basic block only) scheduling
+ step(target, Phase.LocalSched, this::localSched, dump);
+ // Register allocation
+ step(target, Phase.RegAlloc, this::regAlloc, dump);
+ // Encode machine instructions into bits
+ step(target, Phase.Encoding, this::encode, dump);
+ // Export machine code and data into one ELF file
+ step(target, Phase.Export, () -> exportELF(inMemory,emitEntrySymbol), dump);
return this;
}
+ // The driver names the order; optional phases decide locally whether to run.
private void step(Phase target, Phase next, Runnable work, int dump) {
- if( next.ordinal()>target.ordinal() || (_phase!=null && _phase.ordinal()>=next.ordinal()) ) return;
+ if( next.ordinal() > target.ordinal() || (_phase!=null && _phase.ordinal()>=next.ordinal()) ) return;
Phase prior = _phase;
work.run();
- if( _phase!=prior && (dump & (1<<_phase.ordinal()))!=0 ) {
- if( (dump & (1<<30))!=0 ) System.err.println("After "+_phase+":");
- System.err.println(this);
- }
+ if( _phase!=prior ) dump(dump);
}
- public final long[] _times = new long[Phase.values().length];
- private CodeGen phase(Phase next, boolean ordered, Runnable work) {
+ // All phase entry points share ordering checks, timing, and viewer notification.
+ // Record elapsed time even on failure, but report completion only on success.
+ CodeGen phase(Phase next, boolean ordered, Runnable work) {
assert ordered : "Cannot run "+next+" after "+_phase;
_phase = next;
long t0 = System.currentTimeMillis();
- try { work.run(); }
- finally { _times[next.ordinal()] = System.currentTimeMillis()-t0; }
- if( _obs!=null ) _obs.phase(next.name());
+ work.run(); // Do The Phase
+ _times[next.ordinal()] = System.currentTimeMillis() - t0;
+ if( _obs!=null ) _obs.phase(next.name()); // Record for viewer
return this;
}
-
- // ---------------------------
- // Compilation source code
- public final String _src;
- // Compile-time known initial argument type
- public final TypeInteger _arg;
-
- // ---------------------------
- 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 ); }
-
- public CodeGen( String src, TypeInteger arg, long workListSeed, boolean reset ) {
- CODE = this;
- if( reset ) Type.reset();
- _main = makeFun(TypeFunPtr.MAIN);
- _phase = null;
- _callingConv = null;
- _start = new StartNode(arg);
- _stop = new StopNode(src);
- _start.setDef(1,_stop);
- _src = src;
- _arg = arg;
- _iter = new IterPeeps(workListSeed);
- P = new Parser(this,arg);
+ public String entryClinitName() {
+ return Parser.addClzPrefix(_srcName==null ? "Test" : _srcName.replace('/','.'))+".<clinit>";
}
-
- // 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);
+ // Verbose printing during compilation
+ private void dump(int dump) {
+ int p2 = _phase.ordinal();
+ if( (dump & (1<<p2)) == 0 ) return;
+ 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));
}
+ // Record times by phase
+ public final long[] _times = new long[Phase.LastPhase.ordinal()];
+
// ---------------------------
/**
* A counter, for unique node id generation. Starting with value 1, to
@@ -126,9 +328,30 @@ 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++; }
+
+ // Allocate dense alias/function/call IDs within this invocation.
+ // Class slots let a forward reference reserve an initializer's identity.
+ public final LocalIds _aliases = new LocalIds();
+ 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,LocalIds.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 LocalIds _fidxs = new LocalIds();
+ // 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 LocalIds _rpcs = new LocalIds();
+ public int rpc( String clz ) { return _rpcs.next(clz); }
// Inlining can insert CFG edges and invalidate cached depth ordering.
@@ -143,41 +366,35 @@ 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;
- // Native calls are exposure roots even on paths with no live Return.
- public final Ary<CallNode> _calls = new Ary<>(CallNode.class);
// 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++;
- 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() ) {
_linker.setX(fidx,null); fun = null; }
return fun;
}
+ // Return the <clinit> for a CompUnit
+ public FunNode link( CompUnit cu ) {
+ for( FunNode fun : _linker )
+ if( fun!=null && fun._compunit == cu && fun.isClz() )
+ return fun;
+ return null;
+ }
// Insert linker mapping from constant function signature to the function
// being called.
@@ -189,32 +406,34 @@ 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);
+ public final Ary<CallNode> _calls = new Ary<>(CallNode.class);
- // Native symbols belong to function identities, not to one ExternNode.
- // Selection and spill copies can turn that node into an ordinary constant.
- private final HashMap<TypeFunPtr,String> _externs = new HashMap<>();
- public void externFunc(TypeFunPtr tfp, String name) { _externs.put(tfp.makeFrom(Type.BOTTOM),name); }
- public String externFunc(TypeFunPtr tfp) { return _externs.get(tfp.makeFrom(Type.BOTTOM)); }
+ // 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 CodeGen parse() {
- return phase(Phase.Parse, _phase==null, () -> {
- P.parse();
- // Close the declarations as a group before replacing old forward
- // shapes in the graph. A can mention B before B mentions A; both
- // must use the same complete cycle, including through functions.
- HashMap<String,Type> closed = new HashMap<>();
- for( var entry : Parser.TYPES.entrySet() )
- if( entry.getValue() instanceof TypeMemPtr ptr && !ptr._obj._open )
- closed.put(entry.getKey(),ptr.makeFrom(ptr._obj.close(Parser.TYPES)));
- Parser.TYPES.putAll(closed);
- _start.walk(n -> { n.upgradeType(Parser.TYPES); return null; });
- });
- }
+ public CodeGen parse() { return phase(Phase.Parse, _phase==null, () -> ParseAll.parse(this,_src)); }
// ---------------------------
@@ -228,37 +447,63 @@ public class CodeGen {
public void iterCnt() { if( !_midAssert ) _iter_cnt++; }
public void iterNop() { if( !_midAssert ) _iter_nop_cnt++; }
- // Pessimistic peepholes reach a fixed point after parsing.
- public CodeGen iter() { return phase(Phase.Iter, _phase==Phase.Parse, () -> _iter.iterate(this)); }
+ // Pessimistic peepholes after parsing. This lifts loaded and parsed
+ // types before the optimistic Opto pass resets types and lets them fall.
+ public CodeGen iter() { return phase(Phase.Iter, _phase==Phase.Parse, () -> Iter.run(this)); }
- // SCCP computes types and queues changed nodes; Iter applies their rewrites.
+ // SCCP and numeric-mode resolution; leave cleanup work queued for Iter.
public CodeGen opto() { return phase(Phase.Opto, _phase==Phase.Iter, () -> Opto.opto(this)); }
+
public CodeGen iterPostOpto() { return phase(Phase.IterPostOpto, _phase==Phase.Opto, () -> _iter.iterate(this)); }
public CodeGen finalizeIR() { return phase(Phase.FinalizeIR, _phase==Phase.IterPostOpto, () -> FinalizeIR.run(this)); }
+
+ // Root a surviving function without claiming that it has unknown callers.
+ void keepInCompUnit(FunNode fun) {
+ StopCUNode stop = fun._compunit._stop;
+ if( stop._inputs.find(fun.ret()) == -1 )
+ add(stop).addDef(fun.ret());
+ }
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 CodeGen typeCheck() { return phase(Phase.TypeCheck, _phase==Phase.FinalizeIR, () -> TypeCheck.run(this)); }
+ public static TypeStruct requiredStruct(Node n) {
+ // CNC: remove? cleanup?
+ 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;
+ }
+
+ // ---------------------------
+ // TypeCheck queued surviving CLInits during its existing error walk.
+ public CodeGen lower() {
+ return phase(Phase.Lower, _phase==Phase.TypeCheck, () -> _iter.iterate(this));
+ }
+
// ---------------------------
// Build the loop tree; break never-exit loops
public CodeGen loopTree() {
- return phase(Phase.LoopTree, _phase==Phase.TypeCheck, () -> {
- // Build the loop tree, fix never-exit loops
- _start.buildLoopTree(_start,_stop);
- });
+ return phase(Phase.LoopTree, _phase==Phase.Lower, () -> { _start.buildLoopTree(_linker,_stop); FinishCalls.run(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
@@ -273,11 +518,11 @@ public class CodeGen {
// Convert to target hardware nodes
public CodeGen instSelect( String cpu, String callingConv ) { return instSelect(cpu,callingConv,PORTS); }
public CodeGen instSelect( String cpu, String callingConv, String base ) {
- if( cpu==null ) return this;
- return phase(Phase.Select, _phase==Phase.LoopTree,
- () -> new InstSelect(this).run(cpu,callingConv,base));
+ return InstSelect.select(this,cpu,callingConv,base);
}
+ // ---------------------------
+
// ---------------------------
// Control Flow Graph in Reverse Post Order.
@@ -285,17 +530,12 @@ public class CodeGen {
// Global schedule (code motion) nodes
public CodeGen GCM() {
- return phase(Phase.Schedule, (_phase==Phase.LoopTree || _phase==Phase.Select), () -> {
- GlobalCodeMotion.buildCFG(this);
-
- });
+ return phase(Phase.Schedule, (_phase==Phase.LoopTree || _phase==Phase.Select), () -> GlobalCodeMotion.buildCFG(this));
}
// ---------------------------
// Local (basic block) scheduler phase, a classic list scheduler
- public CodeGen localSched() {
- return phase(Phase.LocalSched, _phase==Phase.Schedule, () -> ListScheduler.sched(this));
- }
+ public CodeGen localSched() { return phase(Phase.LocalSched, _phase==Phase.Schedule, () -> ListScheduler.sched(this)); }
// ---------------------------
@@ -308,11 +548,10 @@ public class CodeGen {
});
}
- // 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;
@@ -321,50 +560,50 @@ public class CodeGen {
// ---------------------------
// Encoding
- public Encoding _encoding; // Encoding object
- public void preEncode() { } // overridden by alternative ports
- public CodeGen encode() {
- return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> {
- _encoding = new Encoding(this);
- preEncode();
- _encoding.encode();
- });
- }
+ public Encoding _encoding;
+ public CodeGen encode() { return phase(Phase.Encoding, _phase==Phase.RegAlloc, () -> _encoding = new Encoding(this).encode()); }
// ---------------------------
// Exporting to external formats
- public CodeGen exportELF(String fname) throws IOException {
- assert _phase==Phase.Encoding;
- _phase=Phase.Export;
- long t0=System.currentTimeMillis();
- try {
- if( fname == null ) new LinkMem(this).link(); // In memory patching
- else new ElfFile(this).export(fname); // External ELF file
- } finally { _times[Phase.Export.ordinal()]=System.currentTimeMillis()-t0; }
- if( _obs!=null ) _obs.phase(Phase.Export.name());
- return this;
+ ElfWriter _elf;
+ public CodeGen exportELF( boolean inMemory, boolean emitEntrySymbol ) {
+ return phase(Phase.Export, _phase==Phase.Encoding, () -> {
+ if( inMemory ) new LinkMem(this).link(_encoding);
+ else _elf = new ElfWriter(this).export(emitEntrySymbol);
+ });
}
+
// ---------------------------
+
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() {
@@ -383,28 +622,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..c8b0a82c
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java
@@ -0,0 +1,98 @@
+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 source file and its class. Parent links follow the source directory 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 File _smp; // Simple source file, e.g. module_root/A/B/C.smp
+ final public String _src; // Source code, from file or test case
+
+ public String sourceFile() {
+ return _smp!=null ? _smp.getAbsolutePath() : null;
+ }
+
+ public TypeStruct _clz; // The one TypeStruct being published
+
+ // _deps records units required for types, code, or class references,
+ // without requiring their initializers to run. These source
+ // dependencies may form a cycle.
+ Ary<CompUnit> _deps;
+
+ // 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;
+ _smp = source(fname);
+
+ _src = _smp.exists() ? Files.readString(_smp.toPath()) : null;
+ }
+
+ // The bundled library is ordinary source. A local sys tree can replace it;
+ // this chapter never loads Simple code from an object file.
+ static File source(String fname) {
+ File file=new File(CODE._modDir,fname+".smp");
+ if( file.exists() || !(fname.equals("sys") || fname.startsWith("sys/")) ) return file;
+ return new File("src/main/smp",fname+".smp");
+ }
+
+ // 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;
+ _smp = null;
+ _src = src;
+ }
+
+ // Record source discovery without adding an initialization edge.
+ 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( _src!=null ) x += ",hasSrc";
+ 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/ElfWriter.java b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java
new file mode 100644
index 00000000..c52209dd
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java
@@ -0,0 +1,460 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeFunPtr;
+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;
+
+ 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_LOCAL ? _contents : _globals;
+ 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_LOCAL ? -99 : gidx;
+ }
+
+ 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_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 final int SECTION_HDR_SIZE = 64;
+
+ // ------------------------------------------------------------------------
+
+
+ // ------------------------------------------------------------------------
+
+ // Native code can live above 4G, outside our four-byte function pointers.
+ // Give address-taken natives a low entry which tail-jumps through the PLT.
+ // A weak, stable name makes references from separate objects agree on one
+ // entry. Do not patch references straight to the local copy: that would
+ // bypass the linker's choice and break pointer equality across objects.
+ private int nativeEntry(String name, HashMap<String,Integer> entries,
+ DataSection text, SymbolSection symbols, ReloSection relos) {
+ Integer old = entries.get(name);
+ if( old!=null ) return old;
+ int offset = text.size();
+ text._contents.write(0xE9); // jmp rel32; preserve arguments and return address
+ text.write4(0);
+ int target = symbols.symbol(name,0,SYM_BIND_GLOBAL,SYM_TYPE_FUNC);
+ relos.writeReloOffPlus(offset+1,target,(byte)4/*PLT32*/);
+ int entry = symbols.symbol("__simple_native$"+name,text._index,
+ SYM_BIND_WEAK,SYM_TYPE_FUNC,offset,5);
+ entries.put(name,entry);
+ return entry;
+ }
+
+ 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*/;
+ SymbolSection symbols = new SymbolSection(nlocals);
+
+ // we've already constructed these entire sections in the encoding phase
+ Encoding enc = _code._encoding;
+ // Append ELF-only thunks to a copy. Export must not change instruction
+ // offsets or the image used by the in-memory linker and emulators.
+ BAOS textBits = new BAOS(enc._bits.toByteArray(),enc._bits.size());
+ DataSection text = new DataSection(".text" , Section.SHT_PROGBITS, textBits, 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);
+ HashMap<String,Integer> nativeEntries = new HashMap<>();
+
+ for( Node n : enc._externals.keySet()) {
+ String extern = enc._externals.get(n);
+ boolean nativeAddress = n instanceof FunPtrNode &&
+ _code.externFunc(((TypeFunPtr)n._type).fidx())!=null;
+ int symidx = nativeAddress
+ ? nativeEntry(extern,nativeEntries,text,symbols,relocations)
+ : symbols.symbol(extern,0,SYM_BIND_GLOBAL,SYM_TYPE_FUNC);
+ int offset = enc.opStart(n) + enc.opLen(n) - 4;
+ // Address materialization and static fields name the same thunk;
+ // direct calls still go straight to the native symbol's PLT entry.
+ relocations.writeReloOffPlus(offset,symidx,(byte)(nativeAddress ? 2/*PC32*/ : 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());
+ String nativeName=relo.value() instanceof TypeFunPtr fp ? _code.externFunc(fp.fidx()) : null;
+ Integer sym=nativeName==null ? dataSymbols.get(name)
+ : nativeEntry(nativeName,nativeEntries,text,symbols,relocations);
+ 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
+
+ // 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 019e3892..06bf14f5 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,52 +126,95 @@ 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;
- // A native address has no local FunNode. Keep its symbol even after
- // selection or a spill copy has replaced the original ExternNode.
- String name = _code.externFunc(tfp);
- if( name!=null ) return external(con,name);
- _internals.put(con,_code.link(tfp));
+ // Code address as a constant
+ public Encoding relo( FunPtrNode fptr ) {
+ TypeFunPtr tfp = (TypeFunPtr)fptr._type;
+ // Native functions have no local FunNode, but are still callable.
+ // Do not treat their addresses as identities of deleted functions.
+ String nativeName = _code.externFunc(tfp.fidx());
+ if( nativeName!=null ) return external(fptr,nativeName);
+ 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.
@@ -182,8 +224,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;
}
// --------------------------------------------------
@@ -191,29 +238,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
}
@@ -287,7 +353,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
@@ -332,24 +398,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)));
}
}
}
@@ -359,10 +427,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.
@@ -376,24 +444,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);
}
}
}
@@ -404,21 +475,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];
@@ -426,7 +497,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;
}
@@ -441,103 +512,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/FinalizeIR.java b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
index 4adb2fa4..923486c6 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/FinalizeIR.java
@@ -1,80 +1,44 @@
package com.seaofnodes.simple.codegen;
-import com.seaofnodes.simple.Parser;
import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.*;
import java.util.Arrays;
-// Settle layouts and detach the analyzed call graph before the backend.
+// Comnpute field layouts only after SCCP and its peepholes converge.
+// Keep surviving functions rooted without introducing unknown callers.
abstract class FinalizeIR {
static void run(CodeGen code) {
- fieldSizes(code);
- code._iter.iterate(code);
- // The external-world cycle is an analysis edge, not runtime control.
- // Freeze its facts before replacing call edges with emission roots.
- code._stop.close();
- code._start.close();
- removeCallGraph(code);
- Arrays.sort(code._stop._inputs._es,0,code._stop.nIns(),(x,y) -> x._nid - y._nid);
- }
-
- // Freeze field sizes; do struct layouts; convert field offsets into
- // constants.
- private static void fieldSizes( CodeGen code ) {
+ // Compute field layouts and replace symbolic field offsets by constants.
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 : off._ts._name+"."+off._fname;
+ 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();
+ code._iter.iterate(code); // Propagate field offsets and clean up.
+
+ // Retain surviving functions for emission without adding unknown callers.
+ for( FunNode fun : code._linker )
+ if( fun != null ) {
+ // A folded static function field can leave a detached body
+ // with internal cycles. It has no callers; later phases must
+ // not revive it merely because its nodes are still allocated.
+ if( fun.isDead() || fun._type.isHigh() ) {
+ code._linker.set(fun.sig().fidx(),null);
+ continue;
}
- 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());
+ code.keepInCompUnit(fun);
+ }
+ for( CompUnit cu : code._compunits.values() ) {
+ ProjNode mem = cu._start.proj(1);
+ if( mem != null ) code.add(mem.unkeep());
}
- fun.ret().setDef(3,rpc.init());
- return rpc;
+ // Stable print order: initializers first, then other Returns by 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) ));
}
-
-
}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java b/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java
new file mode 100644
index 00000000..7ba696d3
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java
@@ -0,0 +1,57 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.*;
+
+// Detach analysis call edges after building the loop tree. Every live body
+// belongs to this invocation; preserve it for scheduling and emission.
+abstract class FinishCalls {
+
+
+ static void run(CodeGen code) {
+
+ // 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 : code._linker ) {
+ // Already linked to start, not going dead
+ if( fun==null || fun.isDead() )
+ 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() );
+ }
+ }
+
+ code._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;
+ });
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
index 9be662e8..4477025b 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._mach==null || 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++ )
@@ -142,8 +142,9 @@ public abstract class GlobalCodeMotion {
// Record Load NIDs at all their CFG block choices, then check against
// Store block choices to force a Load above an anti-dependent Store.
int[] anti = new int[code.UID()];
+ Ary<Node> antideps = new Ary<>(Node.class);
// Breadth-first scheduling
- breadth(code._stop,ns,late,anti);
+ breadth(code._stop,ns,late,anti, antideps);
// Copy the best placement choice into the control slot
for( int i=0; i<late.length; i++ )
@@ -151,7 +152,7 @@ public abstract class GlobalCodeMotion {
ns[i].setDef(0,late[i]);
}
- private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti) {
+ private static void breadth(Node stop, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) {
// Things on the worklist have some (but perhaps not all) uses done.
WorkList<Node> work = new WorkList<>();
work.push(stop);
@@ -172,12 +173,12 @@ public abstract class GlobalCodeMotion {
// Loads need their memory inputs' uses also done
if( n instanceof MemOpNode ld && ld._isLoad )
- for( Node memuse : ld.antiDeps() )
+ for( Node memuse : ld.antiDeps(antideps) )
if( late[memuse._nid]==null )
continue outer;
// All uses done, schedule
- _doSchedLate(n,ns,late,anti);
+ _doSchedLate(n,ns,late,anti,antideps);
}
// A use just finished; reconsider its inputs and waiting loads,
@@ -194,7 +195,7 @@ public abstract class GlobalCodeMotion {
}
}
- private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti) {
+ private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late, int[] anti, Ary<Node> antideps) {
// Walk uses, gathering the LCA (Least Common Ancestor) of uses
CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0();
assert early != null;
@@ -205,8 +206,7 @@ public abstract class GlobalCodeMotion {
// Loads may need anti-dependencies, raising their LCA
if( n instanceof MemOpNode load && load._isLoad )
- lca = find_anti_dep(lca,load,early,late,anti);
-
+ lca = find_anti_dep(lca,load,early,late,anti, antideps);
// Walk up from the LCA to the early, looking for best place. This is
// the lowest execution frequency, approximated by least loop depth and
@@ -224,7 +224,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,46 +246,37 @@ 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);
for( Node out : def._outputs )
if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) work.push(ld);
- if( def instanceof MemMergeNode || def instanceof EscapeNode )
+ if( def instanceof MemMergeNode )
for( int i=1; i<def.nIns(); i++ )
if( def.in(i)!=null ) wakeLoads(def.in(i),late,work,visit);
}
- private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti) {
+ private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late, int[] anti, Ary<Node> antideps) {
// 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() ) {
- switch( mem ) {
- case MemOpNode st:
- assert late[st._nid]!=null;
- lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti);
- break;
- case CallNode st:
- assert late[st._nid]!=null;
- lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti);
- break;
- case PhiNode phi:
+ for( Node mem : load.antiDeps(antideps) ) {
+ if( mem instanceof PhiNode phi ) {
// Inputs carrying different memory might overwrite this alias.
- // Raise the LCA for those paths; unchanged memory does not
- // clobber the load. No scheduling edge to the Phi.
+ // Raise the LCA for those paths; the unchanged-memory paths
+ // do not clobber the load. No scheduling edge to the Phi.
for( int i=1; i<phi.nIns(); i++ )
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();
+ } else {
+ // Hunt for clobbering stores
+ assert mem instanceof MemOpNode || mem instanceof EscapeNode ||
+ mem instanceof CallNode || mem instanceof CLInitNode;
+ assert late[mem._nid]!=null;
+ lca = anti_dep(load,late[mem._nid],mem.cfg0(),lca,mem,anti);
}
}
return lca;
@@ -294,14 +286,15 @@ public abstract class GlobalCodeMotion {
private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) {
// A conditional writer can precede the load without dominating its late block.
// Walk back to the first overlap with the load's placement range.
- // Another Phi input need not be dominated by this memory definition.
- // Include its depth, and retain the sentinel for an entry's null idom.
+ // A different Phi input need not be dominated by this memory's
+ // definition. Stop at its depth rather than looking for that ancestor.
+ // Retain the sentinel too: a function entry has a null idom.
for( ; stblk != defblk.idom() && stblk.idepth() >= defblk.idepth(); stblk = stblk.idom() ) {
// Store and Load overlap, need anti-dependence
if( anti[stblk._nid]==load._nid ) {
lca = stblk.domLCA(lca,null); // Raise Loads LCA
if( lca == stblk && st != null && !(st instanceof CallNode) && st._inputs.find(load) == -1 ) // And if something moved,
- st.addDef(load); // Add anti-dep as well; Calls already end their block.
+ st.addDef(load); // Add anti-dep as well (calls already end their block)
return lca; // Cap this stores' anti-dep to here
}
}
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/InstSelect.java b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java
index b0351c98..db35d524 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java
@@ -1,30 +1,43 @@
package com.seaofnodes.simple.codegen;
import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
import java.util.BitSet;
import java.util.IdentityHashMap;
-// Replace ideal nodes with machine nodes, then rebuild the copied graph's uses.
+// Replace ideal nodes with machine nodes while preserving CFG/loop metadata.
+// Selection also owns target ABI masks and rebuilding the copied graph's uses.
class InstSelect {
private final CodeGen _code;
- InstSelect(CodeGen code) { _code=code; }
+ private InstSelect(CodeGen code) { _code=code; }
- @SuppressWarnings("unchecked")
- void run(String cpu, String callingConv, String base) {
+ static CodeGen select(CodeGen code, String cpu, String callingConv, String base) {
+ // Ideal evaluation schedules the ideal graph without a CPU port.
+ if( cpu==null ) return code;
+ return code.phase(CodeGen.Phase.Select, code._phase==CodeGen.Phase.LoopTree,
+ () -> new InstSelect(code).run(cpu,callingConv,base));
+ }
+
+ private void run(String cpu, String callingConv, String base) {
_code._callingConv = callingConv;
// Look for CPU in fixed named place:
// com.seaofnodes.simple.node.cpus."cpu"."cpu.class"
String clzFile = base+"."+cpu+"."+cpu;
- try { _code._mach = ((Class<Machine>) Class.forName( clzFile )).getDeclaredConstructor(new Class[]{CodeGen.class}).newInstance(_code); }
+ try { _code._mach = Class.forName(clzFile).asSubclass(Machine.class).getDeclaredConstructor(CodeGen.class).newInstance(_code); }
catch( Exception e ) { throw new RuntimeException(e); }
+ _code._cCallingConv = _code._mach.cCallingConv(callingConv);
+
// Build global copies of common register masks.
long callerSave = _code._mach.callerSave();
+ long cCallerSave= _code._mach.callerSave(_code._cCallingConv);
long neverSave = _code._mach. neverSave();
int maxReg = Math.min(64,_code._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
_code._callerSave = new RegMask(callerSave);
+ _code._cCallerSave= new RegMask(cCallerSave);
// Build a Return RegMask array. All returns have the following inputs:
// 0 - ctrl
@@ -43,11 +56,18 @@ class InstSelect {
_code._uid = 1; // All new machine nodes reset numbering
var map = new IdentityHashMap<Node,Node>();
_instSelect( _code._stop, map );
- _code._stop = ( StopNode)map.get(_code._stop );
+ _code._stop = (StopNode)map.get(_code._stop );
StartNode start = (StartNode)map.get(_code._start);
_code._start = start==null ? new StartNode(_code._start) : start;
_instOuts(_code._stop,_code.visit());
_code._visit.clear();
+
+ // Replace the CompUnit stop (and list of functions)
+ // with hardware-specific ones
+ for( CompUnit cu : _code._compunits.values() ) {
+ cu._start= (StartCUNode)map.get(cu._start);
+ cu._stop = (StopCUNode )map.get(cu._stop );
+ }
}
private Node _instSelect( Node n, IdentityHashMap<Node,Node> map ) {
@@ -65,14 +85,28 @@ class InstSelect {
}
// Produce a machine node from n; map it to flag as done so stops cycles.
- map.put(n, x=select(n) );
- // Stop retains the callable body. Its lifetime edge is not a machine operand.
- if( n instanceof FunPtrNode ) x._inputs.pop();
+ 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=_code._mach.instSelect(n) );
+ // 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(_code); // Post selection action
+ }
return x;
}
@@ -83,30 +117,10 @@ class InstSelect {
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);
}
}
-
-
- private Node select(Node n) {
- if( n instanceof EscapeNode esc ) return new EscapeMach(esc);
- if( n instanceof GuardNode guard ) return new GuardMach(guard);
- if( n instanceof PtrToIntNode ptr ) return new PtrToIntMach(ptr);
- Node op = n;
- if( n instanceof ModeNode mode && mode.mode()==2 ) {
- // Adapt to the existing CPU selectors. As with machine expansion,
- // copy inputs without adding uses to the old graph; _instOuts
- // rebuilds reverse edges after selection has finished.
- op = switch(n) {
- case AddNode add -> new AddFNode(add);
- case SubNode sub -> new SubFNode(sub);
- case MulNode mul -> new MulFNode(mul);
- case DivNode div -> new DivFNode(div);
- case MinusNode neg -> new MinusFNode(neg);
- default -> n;
- };
- op._type = n._type;
- }
- return _code._mach.instSelect(op);
- }
}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/src/main/java/com/seaofnodes/simple/codegen/Iter.java
new file mode 100644
index 00000000..1ffd9737
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/Iter.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+
+// Establish a pessimistic fixed point after parsing. Later Iter runs
+// reuse the worklist and types produced by the preceding phase.
+abstract class Iter {
+ static void run(CodeGen code) {
+ // Close parser-in-progress states. Seed a fresh pessimistic solve;
+ // exposure sets start at FULL and can only shrink during Iter.
+ code._start.walk(n -> {
+ if( !(n instanceof ConstantNode) )
+ n._type = iterEscapeReset(n._type);
+ code.add(n);
+ return null;
+ });
+ code._iter.iterate(code);
+ // Expensive assert.
+ assert !CodeGen.expensiveAssert() || Opto.fixedPointCheck(code);
+ }
+
+ 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;
+ }
+
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/src/main/java/com/seaofnodes/simple/codegen/LRG.java
index 0c36ae2b..fdde8838 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; }
public RegMask useMask() { return _machUse==null ? null : _machUse.regmap(_uidx); }
@@ -80,7 +84,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; }
@@ -116,6 +120,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/LocalIds.java b/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java
new file mode 100644
index 00000000..462248dd
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java
@@ -0,0 +1,33 @@
+package com.seaofnodes.simple.codegen;
+
+import java.util.HashMap;
+import java.util.Arrays;
+
+// Dense IDs for this invocation. A class slot can be reserved before its file
+// is parsed; every later reference to that slot gets the same ID.
+public class LocalIds {
+ public static final int RESERVED=2;
+ private int _next=RESERVED;
+ private final com.seaofnodes.simple.util.Ary<String> _owners=new com.seaofnodes.simple.util.Ary<>(String.class);
+ private final HashMap<String,int[]> _slots=new HashMap<>();
+
+ public int next(String owner) { return next(owner,-1); }
+ public int next(String owner, int slot) {
+ int[] ids=_slots.get(owner);
+ if( ids==null ) ids=new int[]{RESERVED,1};
+ if( slot==-1 ) slot=ids[0]++;
+ else if( slot>=ids[0] ) ids[0]=slot+1;
+ if( slot>=ids.length ) ids=Arrays.copyOf(ids,Math.max(slot+1,ids.length*2));
+ if( ids[slot]==0 ) { ids[slot]=_next++; _owners.setX(ids[slot],owner); }
+ _slots.put(owner,ids);
+ return ids[slot];
+ }
+ public String owner(int id) { return _owners.atX(id); }
+ public String symbol(int id) { return owner(id)+".$fun"+id; }
+ public int nextInline() { return _next++; }
+ public int next(int old) {
+ int id=_next++;
+ _owners.setX(id,owner(old));
+ return id;
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/src/main/java/com/seaofnodes/simple/codegen/Machine.java
index 7ca465ba..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,17 @@ 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()._type instanceof TypeFunPtr tfp &&
- CodeGen.CODE.externFunc(tfp)!=null &&
+ 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/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
index 3c34b44c..4db277df 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java
@@ -1,9 +1,9 @@
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 java.util.BitSet;
// Optimistic Algorithm
@@ -24,36 +24,25 @@ abstract public class Opto {
// get a fairly precise set of Call Graph edges between CallNodes and
// FunNodes.
public static void opto(CodeGen code) {
-
// Reset Types before running the worklist algorithm
Ary<Type> oldTypes = new Ary<>(Type.class); // Used for asserts only
resetToTop(code,oldTypes);
-
- // Main seeds a whole program. Without main, named exported functions
- // seed discovery. Either way, escaping addresses can add more unknown
- // callers as Start and Stop reach their shared fixed point.
- 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);
- ProjNode startMem=code._start.proj(1);
- if( startMem!=null ) { startMem.unkeep(); code.add(startMem); }
+ 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);
-
-
}
// Reset Types before running the worklist algorithm
@@ -62,9 +51,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;
} );
}
@@ -73,48 +59,56 @@ 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) {
- ProjNode startMem=code._start.proj(1);
- if( startMem!=null ) startMem.keep();
- 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
- // - 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;
- // Hidden allocation helpers are never external entry points.
- if( fun._constructor ) return false;
- // Taking an address does not expose it. Stop discovers escapes from
- // reachable returns and memory; linkStart restores only those callers.
- // 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. Initializers,
+ // including private ones, are called by opaque CLInit
+ // obligations whose Call edges are introduced only in Lower.
+ if( !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
- if( XInt.isHigh(tfp.fidxs()) ) return;
- for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) {
- // A disconnected function can still be revived by a discovered
- // call or escaping address. Do not clean the linker entry here.
+ 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.
@@ -126,24 +120,47 @@ abstract public class Opto {
}
}
- // Exposure is a call edge from the unknown world. Restore conservative
- // declared arguments, never the narrower values inferred from known calls.
- private static void linkStart(CodeGen code, TypeTuple state) {
- for( FunNode fun : code._linker ) {
- if( fun==null || fun.isDead() || fun._constructor || fun.unknownCallers() ||
- !XInt.bit(state.mem()._escFs,fun.sig().fidx()) ) continue;
- fun.insertDef(1,code._start);
- if( !code._stop._inputs.contains(fun.ret()) ) code._stop.addDef(fun.ret());
- code.add(fun); code.add(code._stop);
- for( Node n : fun._outputs )
- if( n instanceof ParmNode parm ) {
- Node def=parm._idx==1 ? code._start.proj(1) : new ConstantNode(parm._declaredType).peephole();
- parm.insertDef(1,def);
+ // 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.unknownCallers() ) {
+ assert !start.isDead();
+ code.keepInCompUnit(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);
}
}
}
+
// The core SCCP algorithm
private static void sccp( CodeGen code, Ary<Type> oldTypes ) {
// Iter workList is empty at this point
@@ -155,50 +172,85 @@ abstract public class Opto {
count++;
Type oval = n._type, nval = n.compute();
if( oval == nval ) continue;
- assert oval.isa(nval) : n.label()+"#"+n._nid+" old="+oval+" new="+nval; // Types start high and always fall
+ 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) : n.label()+"#"+n._nid+" pessimistic="+pesiVal+" new="+nval; // Never fall worse than the pessimistic pass
+ 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( n instanceof StartNode && nval instanceof TypeTuple tt ) linkStart(code,tt);
+ // 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 ))
- : x.label()+"#"+x._nid+" old="+x._type+" new="+xval+" queued="+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;
});
}
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..171d9923
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java
@@ -0,0 +1,285 @@
+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 {
+
+ static void parse(CodeGen code, String src) {
+ Parser.TYPES.clear();
+ Parser.TYPES.putAll(Parser.INIT_TYPES);
+ if( src != null ) {
+ // No source file, just the source itself.
+ parseSource(code,code._srcName==null ? "Test" : code._srcName,src);
+ } else {
+ // Path from module root to source file
+ parsePath(code,code._srcName);
+ }
+ }
+
+ // Worklist of symbols to search and files to parse
+ private static final Ary<CompUnit> WORK = 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 {
+ int idx=name.indexOf('/');
+ if( idx>=0 ) return makeCUnit(code,makeCUnit(code,par,name.substring(0,idx)),name.substring(idx+1));
+ String fname=par==null ? name : par._fname+"/"+name;
+ CompUnit cu=code._compunits.get(fname);
+ if( cu==null ) {
+ String cname=par==null ? name : par._cname+"."+name;
+ code._compunits.put(fname,cu=new CompUnit(par,fname,cname,name));
+ }
+ return cu;
+ }
+
+
+ // 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 enqueue(CompUnit cu) {
+ if( cu._par!=null ) enqueue(cu._par);
+ if( cu._start==null && WORK.find(cu)==-1 ) WORK.add(cu);
+ }
+
+ private static void parseAll(CodeGen code, CompUnit cunit) {
+ WORK.clear(); // Cleanup from prior tests
+ // Prime the pump with the first CompUnit
+ enqueue(cunit);
+ // Work through all unparsed compilation units and parse
+ while( !WORK.isEmpty() ) {
+ CompUnit cu = WORK.remove(0);
+ if( cu._src==null )
+ throw new RuntimeException("Missing source file '"+cu._fname+".smp'");
+ parseOne(code,cu);
+ }
+
+ // 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() )
+ 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 ) {
+ // 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);
+ else
+ assert false : "expected to find required type";
+ } 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 null;
+ }
+
+
+ // 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 null;
+ } 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 ) {
+ if( !symbol.equals("sys") || !CompUnit.source("sys").exists() ) return null;
+ CompUnit sys=makeCUnit(code,null,"sys");
+ enqueue(sys);
+ return sys;
+ }
+
+ // 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 = CompUnit.source(fname);
+ if( f.exists() ) {
+ CompUnit sub = makeCUnit(code,cunit,pre);
+ // enqueue also parses parents: their initialization must precede a child.
+ 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 = CompUnit.source(fname);
+ 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 )
+ enqueue(sub);
+ return sub;
+ }
+
+ // Look up the scope
+ return findCUnitModule( code, cunit._par, symbol );
+ }
+
+
+}
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 565fa6ba..ac792988 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 split && !split.isNonStackSplit() && min!=max ) continue; // Ordinary splits already reach stack storage.
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/SourceError.java b/src/main/java/com/seaofnodes/simple/codegen/SourceError.java
new file mode 100644
index 00000000..f2f46146
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/SourceError.java
@@ -0,0 +1,49 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.util.SB;
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Path;
+
+/** Format one parser byte offset. Source is read and text built only on error. */
+public abstract class SourceError {
+ public static String format(CompUnit cu, int pos, String message) {
+ String file=cu.sourceFile();
+ String name=file==null ? cu._fname+".smp" : file;
+ byte[] source;
+ try {
+ source=cu._src!=null ? cu._src.getBytes(StandardCharsets.UTF_8)
+ : file==null ? null : Files.readAllBytes(Path.of(file));
+ } catch( IOException ex ) { source=null; }
+ if( source==null || pos<0 || pos>source.length )
+ return name+": error: "+message+" (source unavailable at byte offset "+pos+")";
+
+ int line=1, start=0;
+ for( int i=0; i<pos; i++ )
+ if( source[i]=='\n' ) { line++; start=i+1; }
+ int end=pos;
+ while( end<source.length && source[end]!='\n' ) end++;
+ if( end>start && source[end-1]=='\r' ) end--;
+ int point=Math.min(pos,end);
+ String before=new String(source,start,point-start,StandardCharsets.UTF_8);
+ String text=new String(source,start,end-start,StandardCharsets.UTF_8);
+ int column=before.codePointCount(0,before.length())+1;
+ SB sb=new SB().p(name).p(':').p(line).p(':').p(column).p(": error: ").p(message).p("\n ");
+ int width=0, caret=0;
+ for( int i=0; i<text.length(); ) {
+ if( i==before.length() ) caret=width;
+ int ch=text.codePointAt(i);
+ if( ch=='\t' ) {
+ int spaces=8-(width%8);
+ for( int j=0; j<spaces; j++ ) sb.p(' ');
+ width+=spaces;
+ } else { sb.p(new String(Character.toChars(ch))); width++; }
+ i+=Character.charCount(ch);
+ }
+ if( before.length()==text.length() ) caret=width;
+ sb.p("\n ");
+ for( int i=0; i<caret; i++ ) sb.p('-');
+ return sb.p('^').toString();
+ }
+}
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..616753d4
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java
@@ -0,0 +1,177 @@
+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;
+ }
+
+ ObjectData object(Type t) {
+ Object key=isClass(t) ? ((TypeStruct)t)._name
+ : t instanceof TypeFunPtr fp ? functionSymbol(fp) : t;
+ ObjectData old=objects.get(key);
+ if( old!=null ) return old;
+ boolean clz=isClass(t);
+ if( clz && Parser.TYPES.get(((TypeStruct)t)._name) instanceof TypeStruct canonical ) t=canonical;
+ CompUnit owner=clz ? owner(enc._code,(TypeStruct)t)
+ : t instanceof TypeFunPtr fp ? owner(enc._code,enc._code._fidxs.owner(fp.fidx())) : null;
+ String symbol=clz ? ((TypeStruct)t)._name.substring(Parser.CLZ.length())+".$class"
+ : t instanceof TypeFunPtr fp ? functionSymbol(fp) : prefix+objects.size();
+ ObjectData obj=new ObjectData(t,symbol,!clz && (!(t instanceof TypeStruct ts) || ts.isConstant()),
+ owner!=null && owner._src==null);
+ objects.put(key,obj);
+ // Register before following fields: class objects may refer to each other.
+ if( !obj.external && t instanceof TypeStruct ts )
+ for( Field f : ts._fields )
+ if( !f._extern && f._t.isConstant() ) target(f._t);
+ return obj;
+ }
+
+ private static boolean pointerConstant(TypeMemPtr ptr) {
+ return ptr.notNull() && (isClass(ptr._obj) || (ptr._obj.isConstant() && (!ptr._obj.isAry() || ptr._obj.isConAry())));
+ }
+
+ private void target(Type t) {
+ if( t instanceof TypeMemPtr ptr && pointerConstant(ptr) ) object(ptr._obj);
+ if( t instanceof TypeFunPtr fp && fp.notNull() &&
+ enc._code.link(fp)==null && !enc._code._externFunc.containsKey(fp.fidx()) )
+ // A dead function still needs a unique non-null identity for comparisons.
+ object(fp);
+ }
+
+ void write() {
+ ArrayList<Encoding.Relo> refs=new ArrayList<>(enc._bigCons.values());
+ refs.sort(Comparator.comparingInt(r -> r._op._nid));
+ for( Encoding.Relo ref : refs ) object(ref._t);
+ // Definitions belong to their compilation unit, even if every local use folded.
+ ArrayList<CompUnit> units=new ArrayList<>(enc._code._compunits.values());
+ units.sort(Comparator.comparing(cu -> cu._cname==null ? "" : cu._cname));
+ for( CompUnit cu : units ) if( cu._src!=null && cu._clz!=null ) object(cu._clz);
+ for( ObjectData obj : entries() ) {
+ if( obj.external ) continue;
+ BAOS bits=obj.readOnly ? enc._cpool : enc._sdata;
+ Encoding.padN(1<<obj.alignment,bits);
+ obj.offset=bits.size();
+ if( obj.type instanceof TypeStruct ts ) writeStruct(obj,ts,bits);
+ else Encoding.addN(obj.alignment,obj.type,bits);
+ while( bits.size()<obj.offset+obj.size ) bits.write(0);
+ }
+ for( Encoding.Relo ref : refs ) {
+ ObjectData obj=object(ref._t);
+ ref._target=obj.offset;
+ ref._opStart=enc.opStart(ref._op);
+ }
+ }
+
+ private void writeStruct(ObjectData obj, TypeStruct ts, BAOS bits) {
+ int[] layout=ts.layout();
+ for( int idx : layout ) {
+ if( idx==ts._fields.length ) continue;
+ Field f=ts._fields[idx];
+ if( f._extern ) continue;
+ int off=ts.offset(idx);
+ while( bits.size()<obj.offset+off ) bits.write(0);
+ if( f._fname.equals("[]") ) ((TypeConAry)f._t).write(bits);
+ else {
+ Type value=f._t.isConstant() ? f._t : f._t.makeZero();
+ int log=f._t.log_size();
+ Encoding.addN(log,value,bits);
+ if( (value instanceof TypeFunPtr fp && fp.notNull()) ||
+ (value instanceof TypeMemPtr ptr && pointerConstant(ptr)) )
+ relocations.add(new Relocation(obj,off,log,value));
+ }
+ }
+ while( bits.size()<obj.offset+ts.size() ) bits.write(0);
+ }
+
+ String functionSymbol(TypeFunPtr fp) {
+ String ext=enc._code._externFunc.get(fp.fidx());
+ return ext!=null ? ext : enc._code._fidxs.symbol(fp.fidx());
+ }
+
+ String targetSymbol(Type value) {
+ if( value instanceof TypeMemPtr ptr ) return object(ptr._obj).symbol;
+ TypeFunPtr fp=(TypeFunPtr)value;
+ return enc._code.link(fp)==null && !enc._code._externFunc.containsKey(fp.fidx())
+ ? object(fp).symbol : functionSymbol(fp);
+ }
+
+ void link(int cpool, int sdata) {
+ for( Relocation rel : relocations ) {
+ long address;
+ if( rel.value instanceof TypeMemPtr ptr ) address=address(object(ptr._obj),cpool,sdata);
+ else {
+ TypeFunPtr fp=(TypeFunPtr)rel.value;
+ String ext=enc._code._externFunc.get(fp.fidx());
+ FunNode fun=enc._code.link(fp);
+ if( ext!=null ) address=enc.externalAddress(ext);
+ else if( fun==null ) address=address(object(fp),cpool,sdata);
+ else {
+ if( !enc._code.owns(fun) ) throw new IllegalArgumentException("Unlinked function "+functionSymbol(fp));
+ address=enc.opStart(fun);
+ }
+ }
+ // Emulator native-call sentinels are signed 32-bit addresses.
+ if( rel.logSize==2 && (address<Integer.MIN_VALUE || address>0xffff_ffffL) )
+ throw new IllegalArgumentException("Function address outside 32 bits: "+address);
+ BAOS bits=rel.object.readOnly ? enc._cpool : enc._sdata;
+ int off=rel.object.offset+rel.offset;
+ for( int i=0; i<(1<<rel.logSize); i++ ) bits.buf()[off+i]=(byte)(address>>>(8*i));
+ }
+ }
+
+ int address(ObjectData obj,int cpool,int sdata) {
+ if( obj.external ) throw new IllegalArgumentException("Unlinked class object "+obj.symbol);
+ return obj.offset+(obj.readOnly ? cpool : sdata);
+ }
+}
diff --git a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java
index 7dadb4d2..9b4b0995 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java
@@ -5,34 +5,47 @@ import com.seaofnodes.simple.node.*;
import com.seaofnodes.simple.type.Type;
import com.seaofnodes.simple.util.Ary;
+// Reject invalid optimized programs before lowering erases their source-level
+// obligations. Queue surviving CLInits during the same walk for Lower's Iter.
abstract class TypeCheck {
static void run(CodeGen code) {
- Ary<Node> errs = new Ary<>(Node.class);
- code._stop.walk(n -> {
- if( n.err()!=null ) errs.add(n);
- return null;
- });
- if( errs.isEmpty() ) return;
+ // Check for class-init cycles first; such a cycle can prevent other
+ // things from resolving types. The dependency graph is temporary.
+ String clzInitCycle = new ClassInitDependencies(code).check();
+ if( clzInitCycle != null )
+ throw Parser.error(clzInitCycle,null);
- // Publication is a producer check. Report an incomplete object before
- // its users complain about values or permissions inherited from it.
- for( Node n : errs )
- if( n instanceof EscapeNode ) throw n.err();
+ Ary<Node> errs = new Ary<>(Node.class);
+ code._stop.walk( n -> {
+ if( n.err() != null )
+ errs.add(n);
+ if( n instanceof CLInitNode ) code.add(n);
+ return null;
+ });
- // A bad Load now produces BOTTOM. Report the bad access before a
- // Convert or arithmetic use that merely received its failed result.
- Node first = errs.at(0);
- for( Node n : errs )
- if( noBottomInputs(n) ) { first=n; break; }
- for( Node n : errs )
- if( noBottomInputs(n) &&
- ((n instanceof MemOpNode nm && first instanceof MemOpNode fm &&
- nm._loc!=null && nm._loc.before(fm._loc)) ||
- (n instanceof CFGNode nc && first instanceof CFGNode fc && nc.idepth()<fc.idepth())) )
- first=n;
- Parser.ParseException err = first.err();
- if( code._obs!=null ) code._obs.error(first,err.getMessage());
- throw err;
+ 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( code._obs != null ) code._obs.error(min, min.err().getMessage());
+ throw min.err();
+ }
}
private static boolean noBottomInputs(Node n) {