From 9fe7c6f9697b5bbf3041261fdc60040e75cc674f Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 15 Nov 2026 16:11:39 -0800 Subject: Split off chapter 31 Ch 32 will be focused on compiler performance issues. --- .../src/test/java/com/seaofnodes/simple/Eval2.java | 586 +++++++++++++++++++++ 1 file changed, 586 insertions(+) create mode 100644 chapter32/src/test/java/com/seaofnodes/simple/Eval2.java (limited to 'chapter32/src/test/java/com/seaofnodes/simple/Eval2.java') diff --git a/chapter32/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter32/src/test/java/com/seaofnodes/simple/Eval2.java new file mode 100644 index 00000000..d6d97ef1 --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/Eval2.java @@ -0,0 +1,586 @@ +package com.seaofnodes.simple; + +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<>(); + private static final IdentityHashMap ARRAYS = new IdentityHashMap<>(); + + 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(); + ARRAYS.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 ModNode mod -> mod.mode()==1 + ? (Object)(x(mod.in(2))==0 ? 0L : x(mod.in(1)) % x(mod.in(2))) + : (Object)(d(mod.in(1)) % d(mod.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 Intrinsic.F64BitsNode cast -> Double.doubleToRawLongBits(d(cast.in(1))); + case Intrinsic.F64FromBitsNode cast -> Double.longBitsToDouble(x(cast.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[] old=ARRAYS.get(tmp._obj); + if( old!=null ) yield old; + 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 = layout(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