path: root/src/test/java/com/seaofnodes/simple/Eval2.java

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();
        }
        };
    }
}