Chapter 22: A Hello, World!linear-chapter22

Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>

5 files changed, 157 insertions, 74 deletions

diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 9ec3bc7b..adb71413 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -21,7 +21,7 @@ public class CodeGen {
         Opto,                   // Run ideal optimizations
         TypeCheck,              // Last check for bad programs
         LoopTree,               // Build a loop tree; break infinite loops
-        InstSelect,             // Convert to target hardware nodes
+        Select,                 // Convert to target hardware nodes
         Schedule,               // Global schedule (code motion) nodes
         LocalSched,             // Local schedule
         RegAlloc,               // Register allocation
@@ -35,6 +35,7 @@ public class CodeGen {
     public final String _src;
     // Compile-time known initial argument type
     public final TypeInteger _arg;
+
     // ---------------------------
     public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L ); }
     public CodeGen( String src, TypeInteger arg, long workListSeed ) {
@@ -54,14 +55,15 @@ public class CodeGen {
     public CodeGen driver( Phase phase ) { return driver(phase,null,null); }
     public CodeGen driver( Phase phase, String cpu, String callingConv ) {
         if( _phase==null )                       parse();
-        if( _phase.ordinal() < phase.ordinal() ) opto();
-        if( _phase.ordinal() < phase.ordinal() ) typeCheck();
-        if( _phase.ordinal() < phase.ordinal() ) loopTree();
-        if( _phase.ordinal() < phase.ordinal() && cpu != null ) instSelect(cpu,callingConv);
-        if( _phase.ordinal() < phase.ordinal() ) GCM();
-        if( _phase.ordinal() < phase.ordinal() ) localSched();
-        if( _phase.ordinal() < phase.ordinal() ) regAlloc();
-        if( _phase.ordinal() < phase.ordinal() ) encode();
+        int p1 = phase.ordinal();
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Opto      .ordinal() ) opto();
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.TypeCheck .ordinal() ) typeCheck();
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LoopTree  .ordinal() ) loopTree();
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Select    .ordinal() && cpu != null ) instSelect(cpu,callingConv);
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Schedule  .ordinal() ) GCM();
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LocalSched.ordinal() ) localSched();
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.RegAlloc  .ordinal() ) regAlloc();
+        if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Encoding  .ordinal() ) encode();
         return this;
     }
 
@@ -128,7 +130,7 @@ public class CodeGen {
         return TypeFunPtr.make((byte)2,sig,ret, 1L<<fidx );
     }
     // Signature for MAIN
-    public TypeFunPtr _main = makeFun(TypeTuple.MAIN,Type.BOTTOM);
+    public final TypeFunPtr _main = makeFun(TypeTuple.MAIN,Type.BOTTOM);
     // Reverse from a constant function pointer to the IR function being called
     public FunNode link( TypeFunPtr tfp ) {
         assert tfp.isConstant();
@@ -183,6 +185,25 @@ public class CodeGen {
 
         // Pessimistic peephole optimization on a worklist
         _iter.iterate(this);
+
+        // Not really a true optimistic pass, but look for unlinked functions.
+        // This can be removed, which may trigger another round of pessimistic.
+        // This is the point where we flip from a virtual Call Graph (any call
+        // can call any function) to having a correct (but conservative) CG.
+
+        FunNode main = link(_main);
+        for( int i=0; i<_start.nOuts(); i++ ) {
+            Node use = _start.out(i);
+            if( use instanceof FunNode fun &&
+                fun.nIns()==2 && fun.in(1)==_start && fun != main &&
+                    (fun._name==null || fun._name.startsWith("sys.")) ) {
+                add(fun).setDef(1,Parser.XCTRL);
+                addAll(fun._outputs);
+                i--;
+            }
+        }
+        _iter.iterate(this);
+
         _tOpto = (int)(System.currentTimeMillis() - t0);
 
         // TODO:
@@ -220,7 +241,7 @@ public class CodeGen {
         _phase = Phase.LoopTree;
         long t0 = System.currentTimeMillis();
         // Build the loop tree, fix never-exit loops
-        _start.buildLoopTree(_stop);
+        _start.buildLoopTree(_start,_stop);
         _tLoopTree = (int)(System.currentTimeMillis() - t0);
         return this;
     }
@@ -248,7 +269,7 @@ public class CodeGen {
     public CodeGen instSelect( String cpu, String callingConv ) { return instSelect(cpu,callingConv,PORTS); }
     public CodeGen instSelect( String cpu, String callingConv, String base ) {
         assert _phase.ordinal() == Phase.LoopTree.ordinal();
-        _phase = Phase.InstSelect;
+        _phase = Phase.Select;
 
         _callingConv = callingConv;
 
@@ -279,14 +300,14 @@ public class CodeGen {
         _rpcMask = new RegMask(_mach.rpc());
         _retMasks[3] = _rpcMask;
 
-
         // Convert to machine ops
         long t0 = System.currentTimeMillis();
         _uid = 1;               // All new machine nodes reset numbering
         var map = new IdentityHashMap<Node,Node>();
         _instSelect( _stop, map );
         _stop  = ( StopNode)map.get(_stop );
-        _start = (StartNode)map.get(_start);
+        StartNode start = (StartNode)map.get(_start);
+        _start = start==null ? new StartNode(_start) : start;
         _instOuts(_stop,visit());
         _visit.clear();
         _tInsSel = (int)(System.currentTimeMillis() - t0);
@@ -317,8 +338,6 @@ public class CodeGen {
         if( x instanceof MachNode mach )
             mach.postSelect(this);  // Post selection action
 
-        // Updates forward edges only.
-        n._outputs.clear();
         return x;
     }
 
@@ -342,7 +361,7 @@ public class CodeGen {
     // Global schedule (code motion) nodes
     public CodeGen GCM() { return GCM(false); }
     public CodeGen GCM( boolean show) {
-        assert _phase.ordinal() <= Phase.InstSelect.ordinal();
+        assert _phase.ordinal() <= Phase.Select.ordinal();
         _phase = Phase.Schedule;
         long t0 = System.currentTimeMillis();
 
@@ -442,8 +461,10 @@ public class CodeGen {
     String printCFG() {
         if( _cfg==null ) return "no CFG";
         SB sb = new SB();
-        for( CFGNode cfg : _cfg )
-            IRPrinter.printLine(cfg,sb);
+        for( CFGNode cfg : _cfg ) {
+            sb.fix(8,""+cfg._idepth);
+            IRPrinter.printLine( cfg, sb );
+        }
         return sb.toString();
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
index 746ecfed..0eaaae7b 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
@@ -273,8 +273,6 @@ public class ElfFile {
         int start_global = num+1; // Add one to skip the final .rela.text local symbol
         for( Symbol a: symbols._symbols )
             a._index = start_global++;
-        int bigConIdx = start_global;
-        start_global += enc._bigCons.size();
 
         // create .text relocations
         DataSection text_rela = new DataSection(".rela.text", 4 /* SHT_RELA */);
@@ -298,10 +296,10 @@ public class ElfFile {
 
         // Write relocations for the constant pool
         for( Encoding.Relo relo : enc._bigCons.values() ) {
-            Symbol glob = new Symbol("GLOB$"+bigConIdx, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC);
+            Symbol glob = new Symbol("CPOOL$"+start_global, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC);
             glob._value = relo._target;
-            glob._size = 1 << relo._t.log_size();
-            glob._index = bigConIdx++;
+            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 );
@@ -313,6 +311,7 @@ public class ElfFile {
         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();
diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
index c35ea6a4..db799b98 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -51,7 +51,7 @@ public class Encoding {
         public final Type _t;          // Constant type
         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 placede
+        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;
@@ -140,8 +140,8 @@ public class Encoding {
 
 
     final HashMap<Node,String> _externals = new HashMap<>();
-    public Encoding external( Node call, String extern ) {
-        _externals.put(call,extern);
+    public Encoding external( Node n, String extern ) {
+        _externals.put(n,extern);
         return this;
     }
 
@@ -185,12 +185,10 @@ public class Encoding {
         Ary<CFGNode> rpo = new Ary<>(CFGNode.class);
         rpos.put(_code._start.loop(),rpo);
         BitSet visit = _code.visit();
-        //IdentityHashMap<CFGNode,LoopNode> looptail = new IdentityHashMap<>();
         rpo.add(_code._stop);
         for( Node n : _code._start._outputs )
             if( n instanceof FunNode fun ) {
                 int x = rpo._len;
-                //_rpo_cfg2(fun, visit, rpo, looptail);
                 _rpo_cfg(fun, visit, rpos );
                 assert rpo.at(x) instanceof ReturnNode;
             }
@@ -301,7 +299,7 @@ public class Encoding {
     private static boolean forwardsEmptyScan( CFGNode c, int bld ) {
         if( c.nOuts()!=1 || c.loopDepth()!=bld ) return false;
         return c.uctrl() instanceof RegionNode cfg &&
-            (cfg instanceof LoopNode || forwardsEmptyScan(cfg,bld));
+            ((cfg instanceof LoopNode && cfg._ltree==c._ltree) || forwardsEmptyScan(cfg,bld));
     }
 
     // Is the CFG from "next" to the end empty?  This means jumping to "next"
@@ -361,11 +359,6 @@ public class Encoding {
             slide = 0;
             for( int i=0; i<len; i++ ) {
                 CFGNode bb = _code._cfg.at(i);
-                // Functions pad to align 16
-                if( bb instanceof FunNode ) {
-                    int newStart = _opStart[bb._nid]+slide;
-                    slide += (newStart+15 & -16)-newStart;
-                }
                 _opStart[bb._nid] += slide;
                 // Slide down all other (non-CFG) ops in the block
                 for( Node n : bb._outputs )
@@ -389,6 +382,23 @@ public class Encoding {
         }
 
 
+        // Go again, inserting padding on function headers.  Since no
+        // 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);
+            // Functions pad to align 16
+            if( bb instanceof FunNode ) {
+                int newStart = _opStart[bb._nid]+slide;
+                slide += (newStart+15 & -16)-newStart;
+            }
+            _opStart[bb._nid] += slide;
+            for( Node n : bb._outputs )
+                if( n instanceof MachNode && !(n instanceof CFGNode) )
+                    _opStart[n._nid] += slide;
+        }
+
+
         // Copy/slide the bits to make space for all the longer branches
         int grow = _opStart[_code._cfg.at(len-1)._nid] - oldStarts[len-1];
         if( grow > 0 ) {        // If no short-form ops, nothing to do here
@@ -424,31 +434,71 @@ public class Encoding {
     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 log size
-        for( int log = 3; log >= 0; log-- ) {
-            // Write the 8-byte constants
-            for( Node op : _bigCons.keySet() ) {
-                Relo relo = _bigCons.get(op);
-                if( relo._t.log_size()==log ) {
-                    // Map from relo to constant start and patch
-                    Integer target = targets.get(relo._t);
-                    if( target==null ) {
-                        targets.put(relo._t,target = bits.size());
-                        // Put constant into code space.
-                        if( relo._t instanceof TypeTuple tt ) // Constant tuples put all entries
-                            for( Type tx : tt._types )
-                                addN(log,tx,bits);
-                        else
-                            addN(log,relo._t,bits);
+        // 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);
                     }
-                    relo._target = target;
-                    relo._opStart= _opStart[op._nid];
-                    // Go ahead and locally patch in-memory
-                    if( patch )
-                        ((RIPRelSize)op).patch(this, relo._opStart, _opLen[op._nid], relo._target - relo._opStart);
                 }
+                // 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
+                ts._con.write(bits); // Write the constant array bits
+                off += ts._con.len();
+            } else {
+                int log = f._type.log_size();
+                if( f._fname=="#" )  addN(log,ts._con.len(),bits); // Must be a constant array
+                else                 addN(log,f._type      ,bits);
+                off += 1<<log;
             }
         }
     }
@@ -457,14 +507,16 @@ public class Encoding {
     // 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 SENTINAL_CALLOC = -4;
+    public static int SENTINEL_CALLOC = -4;
+    public static int SENTINEL_WRITE  = -8;
 
     void patchGlobalRelocations() {
         for( Node src : _externals.keySet() ) {
             int start  = _opStart[src._nid];
             String dst =  _externals.get(src);
             int target = switch( dst ) {
-            case "calloc" -> SENTINAL_CALLOC;
+            case "calloc" -> SENTINEL_CALLOC;
+            case "write"  -> SENTINEL_WRITE ;
             default -> throw Utils.TODO();
             };
             ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start);
diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
index 40f827ec..04a119c2 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
@@ -32,7 +32,6 @@ public abstract class GlobalCodeMotion {
 
     // Post-Order of CFG
     private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary<CFGNode> rpo) {
-        if( use instanceof CallNode call ) call.unlink_all();
         if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) )
             return;             // Been there, done that
         if( def instanceof ReturnNode && use instanceof CallEndNode )
@@ -178,14 +177,22 @@ public abstract class GlobalCodeMotion {
             }
 
             // Walk all inputs and put on worklist, as their last-use might now be done
-            for( Node def : n._inputs )
-                if( def!=null && late[def._nid]==null ) {
+            for( Node def : n._inputs ) {
+                if( def!=null && late[def._nid]==null )
                     work.push(def);
-                    // if the def has a load use, maybe the load can fire
+                // if the def has a load use, maybe the load can fire
+                if( def!=null )
                     for( Node out : def._outputs )
                         if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null )
                             work.push(ld);
+            }
+
+            if( n instanceof LoopNode loop ) {
+                for( Node phi : loop._outputs ) {
+                    if( phi instanceof PhiNode && late[phi._nid]==null )
+                        work.push(phi);
                 }
+            }
         }
     }
 
@@ -274,7 +281,7 @@ public abstract class GlobalCodeMotion {
         for( Node mem : load.mem()._outputs ) {
             switch( mem ) {
             case MemOpNode st:
-                if( !st._isLoad ) {
+                if( !st._isLoad && load._alias == st._alias ) {
                     assert late[mem._nid] != null;
                     lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st );
                 }
diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index bd4cbf35..57d0d90c 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -163,7 +163,7 @@ public class RegAlloc {
             }
         // Cache reg masks for New and Call
         for( CFGNode bb : _code._cfg ) {
-            if( bb instanceof CallEndNode cend ) cend.cacheRegs(_code);
+            if( bb instanceof CallEndMach cend ) cend.cacheRegs(_code);
             for( Node n : bb._outputs )
                 if( n instanceof NewNode nnn ) nnn.cacheRegs(_code);
         }
@@ -292,20 +292,21 @@ public class RegAlloc {
         Ary<Node> ns = new Ary<>(Node.class);
         for( RegMask rmask : rclass ) {
             ns.addAll(def._outputs);
-            Node split = makeSplit(def,"popular",round,lrg);
+            Node split = makeSplit(def,"popular",round,lrg,rmask);
             split.insertAfter( def );
             if( split.nIns()>1 ) split.setDef(1,def);
             // all uses by class to split
-            for( Node use : ns ) {
+            for( int j=0; j < def._outputs._len; j++ ) {
+                Node use = def._outputs.at(j);
                 if( use instanceof MachNode mach && use!=split ) {
                     // Check all use inputs for n, in case there's several
                     for( int i = 1; i < use.nIns(); i++ )
                         // Find a def input, and check register class
-                        if( use.in( i ) == def ) {
+                        if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) {
                             RegMask m = mach.regmap( i );
                             if( m!=null && mach.regmap( i ).overlap( rmask ) )
                                 // Modify use to use the split version specialized to this rclass
-                                use.setDefOrdered( i, split );
+                                { use.setDefOrdered( i, split ); j--; break; }
                         }
                 }
             }
@@ -501,15 +502,17 @@ public class RegAlloc {
         Node def = n.in(i);
         // Effective block for use
         CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0();
+        // Use-side RegMask, if available
+        RegMask umask = n instanceof MachNode mach ? mach.regmap(i) : null;
         // Def is a split ?
         if( skip && def instanceof SplitNode ) {
-            boolean singleReg = n instanceof MachNode mach && mach.regmap(i).size1();
+            boolean singleReg = umask!=null && umask.size1();
             // Same block, multiple registers, split is only used by n,
             // assume this is good enough and do not split again.
             if( cfg==def.cfg0() && def.nOuts()==1 && !singleReg )
                 return;
         }
-        makeSplit(def,kind,round,lrg).insertBefore(n, i);
+        makeSplit(def,kind,round,lrg,umask).insertBefore(n, i);
         // Skip split-of-split same block
         if( skip && def instanceof SplitNode && cfg==def.cfg0() )
             n.in(i).setDefOrdered(1,def.in(1));
@@ -536,8 +539,9 @@ public class RegAlloc {
         }
     }
 
-    private Node makeSplit( Node def, String kind, byte round, LRG lrg ) {
-        Node split = def instanceof MachNode mach && mach.isClone()
+    private Node makeSplit( Node def, String kind, byte round, LRG lrg, RegMask umask ) {
+        // 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);
         _lrgs.put(split,lrg);
@@ -555,13 +559,13 @@ public class RegAlloc {
     private void postColor() {
         int maxReg = -1;
         for( CFGNode bb : _code._cfg ) { // For all ops
-            if( bb instanceof FunNode fun )
+            if( bb instanceof FunNode )
                 maxReg = -1;   // Reset for new function
             // Compute frame size, based on arguments and largest reg seen
             if( bb instanceof ReturnNode ret )
                 ret.fun().computeFrameAdjust(_code,maxReg);
             // Raise frame size by max stack args passed, even if ignored
-            if( bb instanceof CallEndNode cend )
+            if( bb instanceof CallEndMach cend )
                 maxReg = Math.max(maxReg,cend._xslot);
 
             for( int j=0; j<bb.nOuts(); j++ ) {