Chapter 23: Methods and Revisiting Typeslinear-chapter23

11 files changed, 77 insertions, 51 deletions

diff --git a/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java
index e2fac779..689ceceb 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java
@@ -1,8 +1,8 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Ary;
-import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.Utils;
 import java.util.BitSet;
 import java.util.IdentityHashMap;
 
diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index adb71413..caa7ff44 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -1,13 +1,14 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.*;
+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 java.io.IOException;
-import java.util.BitSet;
-import java.util.HashMap;
-import java.util.IdentityHashMap;
+import java.util.*;
 
 @SuppressWarnings("unchecked")
 public class CodeGen {
@@ -37,9 +38,11 @@ public class CodeGen {
     public final TypeInteger _arg;
 
     // ---------------------------
-    public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L ); }
-    public CodeGen( String src, TypeInteger arg, long workListSeed ) {
+    public CodeGen( String src ) { this(src, TypeInteger.BOT, 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);
@@ -119,18 +122,15 @@ public class CodeGen {
     // are structurally equal.
     public final HashMap<Node,Node> _gvn = new HashMap<>();
 
-    // Compute "function indices": FIDX.
-    // Each new request at the same signature gets a new FIDX.
-    private final HashMap<TypeTuple,Integer> FIDXS = new HashMap<>();
-    public TypeFunPtr makeFun( TypeTuple sig, Type ret ) {
-        Integer i = FIDXS.get(sig);
-        int fidx = i==null ? 0 : i;
-        FIDXS.put(sig,fidx+1);  // Track count per sig
+    //
+    private int _fidx =0;
+    public TypeFunPtr makeFun( TypeFunPtr fun ) {
+        int fidx = _fidx++;
         assert fidx<64;         // TODO: need a larger FIDX space
-        return TypeFunPtr.make((byte)2,sig,ret, 1L<<fidx );
+        return fun.makeFrom(fidx);
     }
     // Signature for MAIN
-    public final TypeFunPtr _main = makeFun(TypeTuple.MAIN,Type.BOTTOM);
+    public final TypeFunPtr _main;
     // Reverse from a constant function pointer to the IR function being called
     public FunNode link( TypeFunPtr tfp ) {
         assert tfp.isConstant();
@@ -186,24 +186,44 @@ public class CodeGen {
         // Pessimistic peephole optimization on a worklist
         _iter.iterate(this);
 
+        // OPTIMISTIC PASS GOES HERE
+
         // 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.
+        int progress = 0;
+        while( progress != _start.nOuts() ) {
+            progress = _start.nOuts();
+            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);
+        }
 
-        FunNode main = link(_main);
+        // Freeze field sizes; do struct layouts; convert field offsets into
+        // constants.
         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);
+            if( use instanceof ConFldOffNode off ) {
+                TypeMemPtr tmp = (TypeMemPtr) Parser.TYPES.get(off._name);
+                off.subsume( off.asOffset(tmp._obj) );
                 i--;
             }
         }
         _iter.iterate(this);
 
+        // To help with testing, sort StopNode returns by NID
+        Arrays.sort(_stop._inputs._es,0,_stop.nIns(),(x,y) -> x._nid - y._nid );
+
         _tOpto = (int)(System.currentTimeMillis() - t0);
 
         // TODO:
@@ -212,7 +232,7 @@ public class CodeGen {
         // loop unroll, peel, RCE, etc
         return this;
     }
-    public <N extends Node> N add( N n ) { return (N)_iter.add(n); }
+    public <N extends Node> N add( N n ) { return _iter.add(n); }
     public void addAll( Ary<Node> ary ) { _iter.addAll(ary); }
 
 
diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
index 0eaaae7b..8f9e2981 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java
@@ -1,9 +1,10 @@
 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.codegen.Encoding.BAOS;
+import com.seaofnodes.simple.util.Ary;
 import java.io.*;
 import java.nio.ByteBuffer;
 import java.nio.ByteOrder;
diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
index db799b98..1065cd9f 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -1,11 +1,11 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Ary;
-import com.seaofnodes.simple.SB;
-import com.seaofnodes.simple.Utils;
 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 java.util.*;
 
@@ -45,6 +45,9 @@ public class Encoding {
     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;
+
     // Big Constant relocation info.
     public static class Relo {
         public final Node _op;
@@ -290,6 +293,9 @@ public class Encoding {
         // Fall/false into a full block, Jump/true to an empty block.
         if( f.nOuts()>1 && t.nOuts()==1 ) return false;
         if( t.nOuts()>1 && f.nOuts()==1 ) return true ;
+        // Jump to a merge point, assuming other things are jumping there as well
+        if( f.out(0) instanceof RegionNode ) return true ;
+        if( t.out(0) instanceof RegionNode ) return false;
         // Everything else equal, use pre-order
         return t._pre > f._pre;
     }
@@ -397,7 +403,7 @@ public class Encoding {
                 if( n instanceof MachNode && !(n instanceof CFGNode) )
                     _opStart[n._nid] += 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];
@@ -414,6 +420,7 @@ public class Encoding {
             }
             _bits.set(bits,bits.length);
         }
+
     }
 
 
@@ -492,12 +499,11 @@ public class Encoding {
             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();
+                ((TypeConAry)f._t).write(bits);
+                off += ((TypeConAry)f._t).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);
+                int log = f._t.log_size();
+                addN(log,f._t,bits);
                 off += 1<<log;
             }
         }
diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
index 04a119c2..520a18a3 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
@@ -1,10 +1,10 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Ary;
 import com.seaofnodes.simple.IterPeeps.WorkList;
-import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.Utils;
 import java.util.*;
 
 public abstract class GlobalCodeMotion {
diff --git a/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/src/main/java/com/seaofnodes/simple/codegen/IFG.java
index fdd4e2f9..6dd6fbf1 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/IFG.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/IFG.java
@@ -1,8 +1,8 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Ary;
-import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.Utils;
 import java.util.BitSet;
 import java.util.IdentityHashMap;
 
diff --git a/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/src/main/java/com/seaofnodes/simple/codegen/LRG.java
index ec254a2e..009ddcdb 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/LRG.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/LRG.java
@@ -1,10 +1,9 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Ary;
-import com.seaofnodes.simple.SB;
-import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.*;
-
+import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.SB;
+import com.seaofnodes.simple.util.Utils;
 import java.util.IdentityHashMap;
 
 /** A Live Range
diff --git a/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java
index e1e849e6..2415203d 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java
@@ -1,7 +1,7 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.util.Utils;
 
 // In-memory linking
 public class LinkMem {
diff --git a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java
index de4fadc4..ddf5a679 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java
@@ -1,10 +1,10 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Ary;
 import com.seaofnodes.simple.IterPeeps.WorkList;
-import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.Utils;
 import java.util.*;
 
 public abstract class ListScheduler {
diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 57d0d90c..da521082 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -1,7 +1,7 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Ary;
-import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.Utils;
 import com.seaofnodes.simple.node.*;
 import java.util.Arrays;
 import java.util.BitSet;
@@ -398,8 +398,8 @@ public class RegAlloc {
         // If the minLoopDepth is less than the maxLoopDepth: for-all defs and
         // uses, if at minLoopDepth or lower, split after def and before use.
         for( Node n : _ns ) {
-            if( n instanceof SplitNode ) continue; // Ignoring splits; since spilling need to split in a deeper loop
-            if( n.isDead() ) continue; // Some Clonable went dead by other spill changes
+            if( n instanceof SplitNode && min!=max ) continue; // Ignoring splits; since spilling need to split in a deeper loop
+            if( n.isDead() ) continue; // Some Cloneable went dead by other spill changes
             // If this is a 2-address commutable op (e.g. AddX86, MulX86) and the rhs has only a single user,
             // commute the inputs... which chops the LHS live ranges' upper bound to just the RHS.
             if( n instanceof MachNode mach && lrg(n)==lrg && mach.twoAddress()==1 && mach.commutes() && n.in(2).nOuts()==1 )
diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
index ec0c4e30..c7dda1da 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
+++ b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
@@ -1,7 +1,7 @@
 package com.seaofnodes.simple.codegen;
 
-import com.seaofnodes.simple.Utils;
-import com.seaofnodes.simple.SB;
+import com.seaofnodes.simple.util.SB;
+import com.seaofnodes.simple.util.Utils;
 
 /** RegMask
  *  A "register mask" - 1 bit set for each allowed register.  In addition,