Add Chapter 29 for tech debt cleanup with the parser splitmain

Keep Chapter 28b intact and carry the grammar-oriented parser package, Var move, IterPeeps move, and parser regression tests into Chapter 29. Defer privacy and exclude its experimental tests and fixture changes.

Register the chapter in the indexes, IntelliJ modules and run configurations, Maven reactor, roadmap, and linear-history publisher. Windows and Linux each pass 573 tests, release builds, 199 allocation replays, and 29 native checks.

1 files changed, 567 insertions, 0 deletions

diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter29/src/test/java/com/seaofnodes/simple/Eval2.java
new file mode 100644
index 00000000..6e5331b2
--- /dev/null
+++ b/chapter29/src/test/java/com/seaofnodes/simple/Eval2.java
@@ -0,0 +1,567 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.parser.Parser;
+import com.seaofnodes.simple.codegen.*;
+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.util.*;
+
+public abstract class Eval2 {
+
+    // A mapping from Node ID to evaluation data Object.
+    // Data Objects are a boxed Long or Double; or an Object[] of fields, which
+    // themselves are just more Objects.
+    private static class Frame {
+        private static int UID=1;
+
+        private final IdentityHashMap<Node,Object> _data;
+        private Frame _prior;   // Prior frame in this sequence, means when making a new frame we can find old stuff
+        private int _refcnt;    // TODO: Use this in a sentence (free/recycle unused stack frames)
+        final int _uid = UID++; // Debugging aid
+        Frame(Frame prior) {
+            _prior = prior;
+            if( prior!=null ) prior._refcnt++;
+            _data = new IdentityHashMap<>();
+            _refcnt = 1;
+        }
+
+        // Dec ref count
+        void dec() {
+            assert _refcnt>0;
+            if( --_refcnt == 0 ) {
+                Frame prior = _prior;
+                _prior = null;
+                _data.clear();
+                // TODO: FREE LIST?
+                if( prior!=null )
+                    prior.dec();
+            }
+        }
+
+        // Put a mapping from Node->Object
+        Node put(Node n, Object d) {
+            assert d!=null;
+            return put0(n,d);
+        }
+        // Put a mapping from Node->Object?
+        Node put0(Node n, Object d) {
+            assert _refcnt>0;
+            _data.put(n,d);
+            return n;
+        }
+        // Get a mapped Node, perhaps using the prior stack frame crawl
+        Object get(Node n) {
+            assert _refcnt>0;
+            Object d = _data.get(n);
+            return d != null ? d
+                : _prior == null ? null
+                : _prior.get(n);
+        }
+
+        // Short debugging print
+        public String p() {
+            return "#"+_uid + (_prior==null ? "" : " >> " + _prior.p());
+        }
+        // Long debugging print
+        @Override public String toString() {
+            String s = "";
+            if( _prior != null ) s+= _prior+" << ";
+            s += "#"+_uid+"[ ";
+            for( Node n : _data.keySet() )
+                s += n + ":" + _data.get(n) + ",";
+            s += "]";
+
+            return s;
+        }
+    }
+
+    // A Classic Continuation; the suspended caller and the control point to
+    // resume after a return.
+    private static class Continuation {
+        // Resume a CallEnd or a CLInit's successor, or exit at Stop.
+        final CFGNode _cc;
+
+        // Stack frame at the execution point.  Includes Continuations which
+        // recursively include other stack frames
+        final Frame _frame;
+
+        Continuation(CFGNode cc, Frame frame) {
+            _cc = cc;
+            _frame = frame;
+            assert _frame._refcnt >=0;
+            _frame._refcnt++;
+        }
+
+        boolean isStop() { return _cc instanceof StopNode; }
+
+        @Override public String toString() {
+            return _cc.toString();
+        }
+    }
+
+    // CodeGen has the linker tables
+    public static CodeGen CODE;
+
+    // Current active Frame, to avoid having to pass it everywhere
+    public static Frame F;
+
+    // Class pointers and initializer self parameters share one object per run.
+    private static final HashMap<String,Object[]> CLASSES = new HashMap<>();
+
+    public static String eval( CodeGen code, long arg ) { return eval(code,arg,1000); }
+    public static String eval( CodeGen code, long arg, int timeout ) {
+        code.driver(CodeGen.Phase.TypeCheck);
+        if( code._start.uctrl()==null ) return ""; // The empty program
+        SB trace = null; // new SB(); // TRACE, set to null for off, new SB() for on
+        // Set global, so don't have to pass everywhere
+        CODE = code;
+        // The normal driver schedules ideal IR without Lower or instruction
+        // selection. Objects loaded later are scheduled independently.
+        code.driver(CodeGen.Phase.LocalSched);
+        CLASSES.clear();
+
+        // Timer for when we run too long.  Ticks once per backedge or function call
+        int loopCnt = 0;
+
+        // Current value for each Node; boxed Long or Double; or an Object[] of
+        // fields, which themselves are just more Objects.
+        F = new Frame(null);
+
+        FunNode entry = (FunNode)code._start.uctrl();
+        VALUE_CACHE.setX(0,"$mem");
+        VALUE_CACHE.setX(1,classObject(((TypeMemPtr)entry.sig().arg(0))._obj));
+        VALUE_CACHE.setX(2,arg);
+        CFGNode BB = enter(entry,code._stop);
+        CFGNode prior = null;
+
+
+        // ------------
+        // Evaluate until exit or timeout.  Each outer loop step computes
+        // all data nodes under some new Control.
+        while( true ) {
+            if( BB==null ) return null;
+            traceCtrl(BB,trace);
+            if( trace!=null ) System.out.println(F.p());
+
+            // Parallel assign Phis
+            int i = BB instanceof RegionNode r
+                    ? parallelAssignPhis(r,prior,trace)
+                    : 0;
+
+            // Compute the data nodes until BB control
+            for( ; i < BB.nOuts(); i++ )
+                if( !(BB.out(i) instanceof CFGNode) )
+                    step(BB.out(i), trace);
+
+            // Find the next control target
+            prior = BB;
+            BB = BB.uctrl();      // Next unique control target
+            switch( prior ) {
+            case CallNode  call :  BB = call(call); break;
+            case CLInitNode init:  BB = call(init); break;
+            case NeverNode never:  BB = never.cproj(0); break; // Synthetic exit is never taken.
+            case IfNode    iff  :  Object p = val(iff.pred()); BB = iff.cproj( p==null || (p instanceof Long x && x==0L)  ? 1 : 0);  break;
+            case ReturnNode ret :  if( continuation(ret).isStop() ) return exit(ret); else BB = ret(ret); break;
+            case FunNode   fun  :  if( loopCnt++ > timeout ) return null;  break; // Timeout
+            case LoopNode  loop :  if( loopCnt++ > timeout ) return null;  break; // Timeout
+            case CallEndNode cend: break;
+            case CProjNode cproj:  break;
+            case RegionNode r   :  break;
+            default:               throw Utils.TODO("Eval control: "+prior.getClass().getSimpleName());
+            }
+            if( BB==null ) return null;
+            assert !BB.isDead();
+        }
+    }
+
+    // Scratch values for parallel Phi assignment and call arguments. Each use
+    // is consumed before the next block executes; loading only schedules code.
+    private static final Ary<Object> VALUE_CACHE = new Ary<>(Object.class);
+    static int parallelAssignPhis(RegionNode r, CFGNode prior, SB trace) {
+
+        // enter() assigned parameters, including the return continuation,
+        // from runtime arguments rather than the compiler's call graph.
+        if( r instanceof FunNode ) {
+            int i = 0;
+            while( i<r.nOuts() && r.out(i) instanceof ParmNode ) i++;
+            return i;
+        }
+
+        // Compute input path on Phis for this Region
+        int path = r._inputs.find( prior );
+
+        // Parallel assign Phis.  First parallel read and cache
+        int i;
+        for( i = 0; i < r.nOuts(); i++ ) {
+            // Due to scheduling, all Phis are first in the outputs; first
+            // non-Phi is the end of all Phis.
+            if( !(r.out(i) instanceof PhiNode phi) ) break;
+
+            VALUE_CACHE.setX(i,F.get(phi.in(path)));
+        }
+        // Parallel assign; might assign before read, so read from cache
+        for( int j=0; j < i; j++ )
+            traceData(F.put0(r.out(j),VALUE_CACHE.at(j)),trace);
+        // Return point in basic block past last Phi; the Phis have been
+        // evaluated here, and now we need to evaluate the rest of the block
+        return i;
+    }
+
+
+    // Make a call.
+    private static CFGNode call( CallNode call ) {
+        int nargs = call.nargs()+1; // Include memory.
+        for( int i = 0; i<nargs; i++ ) VALUE_CACHE.setX(i,val(call.in(i+1)));
+        return enter(CODE.link(tfp(call.fptr())),call.cend());
+    }
+
+    // Interpret the flag-test/call diamond that Lower would emit. The taken
+    // arm uses the ordinary call entry and RPC continuation. The initializer
+    // itself initializes its parent and sets its own $init flag.
+    private static CFGNode call(CLInitNode init) {
+        CompUnit cu = init.cu();
+        //if( cu==null ) return init.uctrl();
+        assert cu != null;      // Post-optimizer the remaining CLInits refer to real classes
+        Object[] obj = classObject(cu._clz);
+        if( obj[cu._clz.find("$init")].equals(1L) )
+            return init.uctrl(); // Class already initialized!
+        VALUE_CACHE.setX(0,"$mem");
+        VALUE_CACHE.setX(1,obj);
+        VALUE_CACHE.setX(2,0L);
+        return enter(CODE.link(cu),init.uctrl());
+    }
+
+
+    private static FunNode enter(FunNode fun, CFGNode continuation) {
+        // If we find a Summary, then this Fun's code never got loaded.
+        // Load it now.
+        if( fun.summary()!=null ) {
+            int fidx = fun.sig().fidx();
+            // Load the matching .o, and all its CompUnits, and all the
+            // included FunNodes, including a replacement for this one.
+            ElfReader elf = SummaryNode.load(CODE,fun);
+            // Object files contain checked ideal IR, before scheduling.  This is
+            // the first schedule for this object's bodies, even though the caller
+            // is already executing.  Schedule only the new graph: revisiting the
+            // caller could change nodes whose values live in an active Frame.
+            // No optimization, CLInit lowering, or finalization.
+            ListScheduler.sched(GlobalCodeMotion.forEval(CODE,(StartNode)elf._nodes.at(0),(StopNode)elf._nodes.last()));
+            // Get the new replacement FunNode
+            fun = CODE.link(fidx);
+        }
+        Continuation cont = new Continuation(continuation,F);
+        F=new Frame(F);
+        for( Node use : fun._outputs )
+            if( use instanceof ParmNode parm )
+                F.put0(parm,parm._idx==0 ? cont : VALUE_CACHE.at(parm._idx-1));
+        return fun;
+    }
+
+    private static CFGNode ret( ReturnNode ret ) {
+        // Fetch return expression value and continuation from current frame
+        Object rez = val(ret.expr());
+        Continuation cont = continuation(ret);
+        // Lower Frame reference count; might delete frame
+        F.dec();                // Lower ref count
+        // Install replacement Frame; set return result over the CallEnd
+        F = cont._frame;
+        if( cont._cc instanceof CallEndNode ) F.put0(cont._cc,rez);
+        return cont._cc;        // Resume after the call.
+    }
+
+    private static Continuation continuation(ReturnNode ret) {
+        return (Continuation)val(ret.rpc());
+    }
+
+    private static String exit( ReturnNode ret ) {
+        return prettyPrint(ret.expr()._type,val(ret.expr()));
+    }
+
+    // Take a worklist step: one data op from the current Control is updated.
+    private static void step(Node n, SB trace) {
+        if( n instanceof PhiNode ) return;
+        // Compute new value
+        F.put0(n,compute(n));
+        traceData(n,trace);
+        // Also do any following projections, which are not in the local schedule otherwise
+        if( n instanceof MultiNode )
+            for( Node use : n._outputs )
+                step(use,trace);
+    }
+
+    // From here down shamelessly copied from Evaluator, written by @Xmilia
+    private static Object compute( Node n ) {
+        return switch( n ) {
+        case AddNode      add  -> add.mode()==1
+            ? (Object)(x(add.in(1)) +  x(add.in(2)))
+            : (Object)(d(add.in(1)) +  d(add.in(2)));
+        case AndNode      and  -> x(and.in(1)) &  x(and.in(2));
+        case BoolNode.EQ  eq   -> Objects.equals(val(eq.in(1)), val(eq.in(2))) ? 1L : 0L; // Bool EQ supports pointers, nil, and integers
+        case BoolNode.LE  le   -> le.mode()==1
+            ? (x(le.in(1)) <= x(le.in(2)) ? 1L : 0L)
+            : (d(le.in(1)) <= d(le.in(2)) ? 1L : 0L);
+        case BoolNode.LT  lt   -> lt.mode()==1
+            ? (x(lt.in(1)) <  x(lt.in(2)) ? 1L : 0L)
+            : (d(lt.in(1)) <  d(lt.in(2)) ? 1L : 0L);
+        case GuardNode   guard -> val(guard.in(1));
+        case ConstantNode con  -> con(con._con);
+        case DivNode      div  -> div.mode()==1
+            ? (Object)(x(div.in(2))==0 ? 0L : x(div.in(1)) / x(div.in(2)))
+            : (Object)((d(div.in(2))==0 ? 0D : d(div.in(1))) / d(div.in(2)));
+        case EscapeNode   esc  -> esc(esc);
+        case FunPtrNode   fptr -> con(fptr._con);
+        case LoadNode     ld   -> load(ld);
+        case MemMergeNode merge-> "$mem";
+        case MinusNode    sub  -> sub.mode()==1 ? (Object)(- x(sub.in(1))) : (Object)(- d(sub.in(1)));
+        case MulNode      mul  -> mul.mode()==1
+            ? (Object)(x(mul.in(1)) *  x(mul.in(2)))
+            : (Object)(d(mul.in(1)) *  d(mul.in(2)));
+        case NewNode      alloc-> alloc(alloc);
+        case NotNode      not  -> not(not);
+        case OrNode       or   -> x(or .in(1)) |  x(or .in(2));
+        case ProjNode     proj -> proj._type instanceof TypeMem ? "$mem" : val(proj.in(0));
+        case ReadOnlyNode read -> val(read.in(1));
+        case SarNode      sar  -> x(sar.in(1)) >> x(sar.in(2));
+        case ShlNode      shl  -> x(shl.in(1)) << x(shl.in(2));
+        case ShrNode      shr  -> x(shr.in(1)) >>>x(shr.in(2));
+        case StoreNode    st   -> store(st);
+        case SubNode      sub  -> sub.mode()==1
+            ? (Object)(x(sub.in(1)) -  x(sub.in(2)))
+            : (Object)(d(sub.in(1)) -  d(sub.in(2)));
+        case RoundF32Node rnd  -> (double)(float)d(rnd.in(1));
+        case ToIntegerNode cvt -> (long)d(cvt.in(1));
+        case ToFloatNode  toflt-> (double)x(toflt.in(1));
+        case XorNode      xor  -> x(xor.in(1)) ^  x(xor.in(2));
+        default -> throw Utils.TODO();
+        };
+    }
+
+    // Fetch without unboxing, searching up-Frame
+    static Object val( Node n ) { return F.get(n); }
+    // Fetch and unbox as primitive long
+    static long   x( Node n ) { Object d = F.get(n); return d==null ? 0 : (Long)d;  }
+    // Fetch and unbox as primitive double
+    static double d( Node n ) { Object d = F.get(n); return d==null ? 0 : (Double)d;  }
+    // Fetch and unbox a function constant
+    static TypeFunPtr tfp(Node n) {
+        return (TypeFunPtr)F.get(n);
+    }
+
+    // Java box ints and floats.  Other things can just be null or some informative string
+    private static Object con( Type t ) {
+        return switch ( t ) {
+        case TypeInteger i -> i.isConstant() ? (Long  )i.value() : "INT";
+        case TypeFloat   f -> f.isConstant() ? (Double)f.value() : "FLT";
+        case TypeFunPtr tfp -> tfp;
+        case TypeMem mem -> "MEM";
+        case TypeMemPtr tmp -> {
+            if( tmp._obj.isAry() ) { // Constant array ptr
+                Type elem = tmp._obj.field("[]")._t;
+                if( elem instanceof TypeConAry con ) {
+                    Object[] xs = new Object[con.len()];
+                    for( int i=0; i<con.len(); i++ )
+                        xs[i] = con.at8(i);
+                    yield xs;
+                } else {
+                    // Generic constant array, used as a default input to a
+                    // function; should never execute.
+                    yield new Object[0];
+                }
+
+            } else if( Parser.startsClzPrefix(tmp._obj._name) ) {
+                yield classObject(tmp._obj);
+            } else {
+                // Constant object with all zeros
+                yield alloc(tmp._obj);
+            }
+        }
+        default -> null;
+        };
+    }
+
+    // Escapes of constant memory actually needs to set the memory
+    private static Object esc(EscapeNode esc) {
+        if( esc.priv() instanceof ConstantNode con ) {
+            TypeMem mem = (TypeMem)con._type;
+            Object val = con(mem._t);
+            TypeMemPtr tmp = (TypeMemPtr)esc.self()._type;
+            int idx = tmp._obj.findAlias(esc.fld()._alias);
+            Object[] fs = (Object[])val(esc.self());
+            if( tmp._obj.isAry() ) {
+                assert idx==0; // length field
+                assert (Long)val==fs.length;
+            } else {
+                fs[idx] = val;
+            }
+        }
+        return "$mem";
+    }
+
+
+    // Convert array size to array element count
+    private static int offToIdx( long off, TypeStruct t) {
+        off -= t.aryBase();
+        int scale = t.aryScale();
+        assert (off & ((1L << scale)-1)) == 0;
+        return (int)(off>>scale);
+    }
+
+    // Builds and returns a pointer Object
+    private static Object[] alloc(NewNode alloc) {
+        TypeStruct type = alloc._ts;
+        if( type.isAry() ) {
+            long sz = (Long)val(alloc.in(1));
+            long x = offToIdx(sz, type);
+            int n = (int)x;
+            if( n!=x || n<0 )
+                throw new NegativeArraySizeException(""+n);
+            Object[] ary = new Object[n]; // Array body
+            var elem = type._fields[1]._t;
+            if (elem instanceof TypeInteger) {
+                Arrays.fill( ary, 0L );
+            } else if (elem instanceof TypeFloat) {
+                Arrays.fill( ary, 0D );
+            } else {
+                assert elem instanceof TypeMemPtr || elem instanceof TypeFunPtr;
+            }
+            return ary;
+        }
+
+        return alloc(type);
+    }
+    private static Object[] alloc(TypeStruct type) {
+        assert !type.isAry();
+        int num = type._fields.length;
+        Object[] ptr = new Object[num];
+        for( int i=0; i<num; i++ )
+            ptr[i] = con(type._fields[i]._t.makeZero());
+        return ptr;
+    }
+
+    private static Object[] classObject(TypeStruct type) {
+        Object[] ptr = CLASSES.get(type._name);
+        if( ptr==null ) CLASSES.put(type._name,ptr=alloc(type));
+        return ptr;
+    }
+
+    private static Object not( NotNode not ) {
+        Object n = val(not.in(1));
+        return ( n==null || (n instanceof Double D && D==0.0) || n instanceof Long L && L==0 )
+            ? 1L : 0L;
+    }
+
+    private static Object load( LoadNode ld ) {
+        Object f = val(ld.ptr());
+        // Check for dense constant array
+        if( f instanceof TypeMemPtr tmp ) {
+            throw Utils.TODO();
+        }
+        Object[] fs = (Object[])f;
+        if( ld._name.equals("#") )
+            return (long)fs.length;
+        TypeMemPtr tmp = (TypeMemPtr)ld.ptr()._type;
+        int idx = tmp._obj.isAry()
+            ? offToIdx(x(ld.off()),tmp._obj)
+            : tmp._obj.find(ld._name);
+        return fs[idx];
+    }
+
+    private static Object store( StoreNode st ) {
+        if( st._name.equals("#") )
+            return "$mem";      // Eval stores the length in the java object[], no need to set it now
+        TypeMemPtr tmp = (TypeMemPtr)st.ptr()._type;
+        Object[] fs = (Object[])val(st.ptr());
+        int idx = tmp._obj.isAry()
+            ? offToIdx(x(st.off()),tmp._obj)
+            : tmp._obj.find(st._name);
+        Object val = val(st.val());
+        // Idealization can remove conversions already performed by the store.
+        Type type = st.declaredType();
+        if( type instanceof TypeInteger ti ) {
+            int shift = 64-(8 << st.log_size());
+            long x = (Long)val << shift;
+            val = ti._min < 0 ? x >> shift : x >>> shift;
+        } else if( type instanceof TypeFloat && st.log_size()==2 )
+            val = (double)(float)(double)(Double)val;
+        fs[idx] = val;
+        return "$mem";
+    }
+
+
+    // ------------------------------------------------------------------------
+    private static final IdentityHashMap<Object,Object> VISIT = new IdentityHashMap<>();
+
+
+    static void traceCtrl( CFGNode BB, SB sb ) {
+        if( sb==null ) return;
+        IRPrinter.printLine(BB,sb.p("--- "));
+        System.out.print(sb);
+        sb.clear();
+    }
+    static void traceData( Node n, SB sb ) {
+        if( sb==null ) return;
+        IRPrinter.printLine(n,sb).unchar();
+        _print( n._type, F.get(n), sb.p('\t'), VISIT );
+        System.out.println(sb);
+        sb.clear();
+        VISIT.clear();
+    }
+
+    // Use type to print x as a string.  Uses a new VISIT table so the debugger
+    // doesn't try to reuse VISIT if stopping mid-print.  The trace code reuses
+    // VISIT endlessly for some minor speed hope
+    static String prettyPrint( Type t, Object x ) { return _print(t,x,new SB(), new IdentityHashMap<>()).toString(); }
+    static SB _print( Type t, Object x, SB sb, IdentityHashMap<Object,Object> visit ) {
+        if( x instanceof String s ) return sb.p(s);
+        if( x == null ) return sb.p("null");
+        return switch( t ) {
+        case TypeInteger i -> sb.p(  (Long)x);
+        case TypeFloat   f -> sb.p((Double)x);
+        case TypeMemPtr tmp -> {
+            if( visit.containsKey(x) ) yield sb.p("$cyclic");
+            visit.put(x,x);
+
+            Object[] xs = (Object[])x; // Array of fields
+            if( tmp._obj.isAry() ) {
+                Type elem = tmp._obj._fields[1]._t;
+                if( elem.isa(TypeInteger.U8) ) {
+                    // Shortcut u8[] as a String
+                    for( Object o : xs )
+                        sb.p((char)(long)(Long)o);
+                } else {
+                    // Array of elements
+                    elem.print(sb).p("[ ");
+                    if( elem instanceof TypeConAry ) elem = TypeInteger.ZERO;
+                    for( Object o : xs )
+                        _print( elem, o, sb, visit ).p( "," );
+                    sb.unchar().p("]");
+                }
+            } else {
+                sb.p(tmp._obj._name).p("{");
+                Field[] flds = tmp._obj._fields;
+                for( int i=0; i<flds.length; i++ )
+                    _print( flds[i]._t,xs[i], sb.p(flds[i]._fname).p("="), visit ).p(",");
+                sb.unchar().p("}");
+            }
+            yield sb;
+        }
+        case TypeFunPtr tfp -> sb.p(x.toString());
+        case TypeRPC rpc -> sb.p(x.toString());
+        case TypeMem mem -> sb.p("$mem");
+        case TypeTuple tt -> {
+            if( tt._types.length>1 && tt._types[1] instanceof TypeMemPtr )
+                // Assume a NewNode
+                yield _print( tt._types[1], x, sb, visit );
+            throw Utils.TODO();
+        }
+        case Type tt -> {
+            if( tt == Type.NIL ) yield sb.p("null");
+            throw Utils.TODO();
+        }
+        };
+    }
+}