From f4bd723d929e53475f7990374dca7b7dfcbbdc42 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 1 Nov 2026 10:33:55 -0800 Subject: Add Chapter 29 for tech debt cleanup with the parser split 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. --- .../src/test/java/com/seaofnodes/simple/Eval2.java | 567 +++++++++++++++++++++ 1 file changed, 567 insertions(+) create mode 100644 chapter29/src/test/java/com/seaofnodes/simple/Eval2.java (limited to 'chapter29/src/test/java/com/seaofnodes/simple/Eval2.java') 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 _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 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 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 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 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> 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 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 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 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(); + } + }; + } +} -- cgit v1.2.3