summaryrefslogtreecommitdiff
path: root/chapter29/src/test/java/com/seaofnodes/simple/Eval2.java
diff options
context:
space:
mode:
Diffstat (limited to 'chapter29/src/test/java/com/seaofnodes/simple/Eval2.java')
-rw-r--r--chapter29/src/test/java/com/seaofnodes/simple/Eval2.java567
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();
+ }
+ };
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-11-02 13:18:52 +0000