diff options
Diffstat (limited to 'chapter18/src')
46 files changed, 1066 insertions, 612 deletions
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java index 184b6f9c..79d817f8 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -1,14 +1,13 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.util.*; +import java.util.HashMap; public class CodeGen { public enum Phase { - Parse, Opto, TypeCheck, Schedule, RegAlloc; + Parse, Opto, TypeCheck, Schedule, LocalSched, RegAlloc; } public Phase _phase; @@ -20,6 +19,11 @@ public class CodeGen { public StartNode _start; public StopNode _stop ; + + // "Linker" mapping from constant TypeFunPtrs to heads of function + public final HashMap<TypeFunPtr,FunNode> _linker = new HashMap<>(); + + // Last created CodeGen as a global, for easier debugging prints public static CodeGen CODE; @@ -30,6 +34,8 @@ public class CodeGen { public CodeGen parse(boolean disable) { assert _phase == null; _phase = Phase.Parse; + _linker.clear(); + P = new Parser(_src,_arg); Node._disablePeephole = disable; _stop = P.parse(); @@ -51,7 +57,7 @@ public class CodeGen { } public CodeGen typeCheck() { - assert _phase == Phase.Opto; + assert _phase == Phase.Opto || _phase == Phase.Parse; _phase = Phase.TypeCheck; // Type check @@ -62,8 +68,8 @@ public class CodeGen { } - public CodeGen codegen() { return codegen(false); } - public CodeGen codegen(boolean show) { + public CodeGen GCM() { return GCM(false); } + public CodeGen GCM( boolean show) { assert _phase == Phase.TypeCheck; _phase = Phase.Schedule; @@ -74,14 +80,23 @@ public class CodeGen { // TODO: // loop unroll, peel, RCE, etc - GlobalCodeMotion.buildCFG(_start,_stop); - - _phase = Phase.RegAlloc; - return this; } + public CodeGen localSched() { + assert _phase == Phase.Schedule; + _phase = Phase.LocalSched; + ListScheduler.sched(this); + return this; + } + + + // Testing shortcuts + Node ctrl() { return _stop.ret().ctrl(); } + Node expr() { return _stop.ret().expr(); } + String print() { return _stop.print(); } + // Debugging helper @Override public String toString() { return _stop.p(9999); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 7ce12091..6b0956ca 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -54,7 +54,7 @@ public abstract class GlobalCodeMotion { visit.set(n._nid); // Schedule not-pinned not-CFG inputs before self. Since skipping // Pinned, this never walks the backedge of Phis (and thus spins around - // a data-only loop, eventually attempting relying on some pre-visited- + // a data-only loop), eventually attempting relying on some pre-visited- // not-post-visited data op with no scheduled control. for( Node def : n._inputs ) if( def!=null && !(def instanceof PhiNode) ) @@ -65,7 +65,7 @@ public abstract class GlobalCodeMotion { CFGNode early = Parser.START; // Maximally early, lowest idepth if( n.in(0) instanceof CFGNode cfg ) early = cfg; for( int i=1; i<n.nIns(); i++ ) - if( n.in(i).cfg0().idepth() > early.idepth() ) + if( n.in(i)!=null && n.in(i).cfg0().idepth() > early.idepth() ) early = n.in(i).cfg0(); // Latest/deepest input n.setDef(0,early); // First place this can go } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java index 4f422a25..adf67d8b 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -import java.lang.StringBuilder; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; @@ -11,33 +10,31 @@ public class IRPrinter { // Print a node on 1 line, columnar aligned, as: // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt - public static void printLine( Node n, StringBuilder sb ) { - sb.append("%4d %-7.7s ".formatted(n._nid,n.label())); - if( n._inputs==null ) { - sb.append("DEAD\n"); - return; - } + public static SB printLine( Node n, SB sb ) { + sb.p("%4d %-7.7s ".formatted(n._nid,n.label())); + if( n._inputs==null ) + return sb.p("DEAD\n"); for( Node def : n._inputs ) - sb.append(def==null ? "____" : "%4d".formatted(def._nid)) + sb.p(def==null ? "____" : "%4d".formatted(def._nid)) // Lazy Phi indicator - .append(n instanceof ScopeMinNode && def instanceof ScopeMinNode ? "^" : " "); + .p(n instanceof ScopeMinNode && def instanceof ScopeMinNode ? "^" : " "); for( int i = n._inputs.size(); i<4; i++ ) - sb.append(" "); - sb.append(" [[ "); + sb.p(" "); + sb.p(" [[ "); for( Node use : n._outputs ) - sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); + sb.p(use==null ? "____ " : "%4d ".formatted(use._nid)); int lim = 6 - Math.max(n._inputs.size(),4); for( int i = n._outputs.size(); i<lim; i++ ) - sb.append(" "); - sb.append(" ]] "); - if( n._type!= null ) sb.append(n._type.str()); - sb.append("\n"); + sb.p(" "); + sb.p(" ]] "); + if( n._type!= null ) sb.p(n._type.str()); + return sb.p("\n"); } - private static StringBuilder nodeId(StringBuilder sb, Node n) { - sb.append("%%%d".formatted(n._nid)); + private static SB nodeId(SB sb, Node n) { + sb.p("%%%d".formatted(n._nid)); if (n instanceof ProjNode proj) { - sb.append(".").append(proj._idx); + sb.p(".").p(proj._idx); } return sb; } @@ -58,19 +55,19 @@ public class IRPrinter { for( int i=bfs._lim; i< bfs._bfs.size(); i++ ) postOrd( bfs._bfs.get(i), null, rpos, visit, bfs._bs); // Reverse the post-order walk - StringBuilder sb = new StringBuilder(); + SB sb = new SB(); boolean gap=false; for( int i=rpos.size()-1; i>=0; i-- ) { Node n = rpos.get(i); if( n instanceof CFGNode || n.isMultiHead() ) { - if( !gap ) sb.append("\n"); // Blank before multihead + if( !gap ) sb.p("\n"); // Blank before multihead printLine( n, sb ); // Print head while( --i >= 0 ) { Node t = rpos.get(i); if( !t.isMultiTail() ) { i++; break; } printLine( t, sb ); } - sb.append("\n"); // Blank after multitail + sb.p("\n"); // Blank after multitail gap = true; } else { printLine( n, sb ); @@ -180,7 +177,7 @@ public class IRPrinter { } } // Print by block with least idepth - StringBuilder sb = new StringBuilder(); + SB sb = new SB(); Ary<Node> bns = new Ary<>(Node.class); while( !ds.isEmpty() ) { CFGNode blk = null; @@ -193,16 +190,15 @@ public class IRPrinter { ns.remove(blk); // Print block header - sb.append("%-13.13s".formatted(label(blk)+":")); - sb.append( " ".repeat(4) ).append(" [[ "); + sb.p("%-13.13s".formatted(label(blk)+":")); + sb.p( " ".repeat(4) ).p(" [[ "); if( blk instanceof StartNode ) ; else if( blk instanceof RegionNode || blk instanceof StopNode ) for( int i=(blk instanceof StopNode ? 3 : 1); i<blk.nIns(); i++ ) label(sb,blk.cfg(i)); else label(sb,blk.cfg(0)); - sb.append(" ]] \n"); - sb.append(d); + sb.p(" ]] \n"); printLine(blk,sb); // Collect block contents that are in the depth limit @@ -234,20 +230,21 @@ public class IRPrinter { } } } - sb.append("\n"); + sb.p("\n"); } return sb.toString(); } private static void _walk( HashMap<Integer,Integer> ds, ArrayList<Node> ns, Node node, int d ) { Integer nd = ds.get(node._nid); - if( nd!=null && d >= nd ) return; // Been there, done that + if( nd!=null && d <= nd ) return; // Been there, done that Integer old = ds.put(node._nid,d) ; if( old == null ) ns.add(node); if( d == 0 ) return; // Depth cutoff for( Node def : node._inputs ) if( def != null && + !(node instanceof LoopNode loop && loop.back()==def) && // Don't walk into or out of functions !(node instanceof CallEndNode && def instanceof ReturnNode) && !(node instanceof FunNode && def instanceof CallNode) ) @@ -258,12 +255,11 @@ public class IRPrinter { if( blk instanceof StartNode ) return "START"; return (blk instanceof LoopNode ? "LOOP" : "L")+blk._nid; } - static void label( StringBuilder sb, CFGNode blk ) { + static void label( SB sb, CFGNode blk ) { if( !blk.blockHead() ) blk = blk.cfg(0); - sb.append( "%-9.9s ".formatted( label( blk ) ) ); + sb.p( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, StringBuilder sb, Ary<Node> bns, int i, HashMap<Integer,Integer> ds, ArrayList<Node> ns ) { - sb.append(ds.get(n._nid)); + static void printLine( Node n, SB sb, Ary<Node> bns, int i, HashMap<Integer,Integer> ds, ArrayList<Node> ns ) { printLine( n, sb ); if( i != -1 ) bns.del(i); ds.remove(n._nid); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java index a321b13e..998bd4f0 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -182,6 +182,7 @@ public abstract class IterPeeps { * True if Node is on the WorkList */ boolean on( E x ) { return _on.get(x._nid); } + boolean isEmpty() { return _len==0; } /** * Removes a random Node from the WorkList; null if WorkList is empty diff --git a/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java b/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java new file mode 100644 index 00000000..252a8f8e --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/ListScheduler.java @@ -0,0 +1,110 @@ + package com.seaofnodes.simple; + +import com.seaofnodes.simple.IterPeeps.WorkList; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.*; + +public abstract class ListScheduler { + + private static final BitSet VISIT = new BitSet(); + private static int[] BCNTS; + public static void sched( CodeGen code ) { + assert VISIT.isEmpty(); + BCNTS = new int[Node.UID()]; + walk(code._start,VISIT); + VISIT.clear(); + } + + // Visit all CFG nodes + static void walk( CFGNode cfg, BitSet visit ) { + if( visit.get(cfg._nid) ) return; + visit.set(cfg._nid); + local(cfg); + for( Node n : cfg._outputs ) + if( n instanceof CFGNode c ) + walk(c,visit); + } + + // Local schedule this one CFG + static void local( CFGNode bb ) { + if( !bb.blockHead() || bb instanceof StopNode ) return; + Node[] uses = bb._outputs._es; + int ulen = bb._outputs._len; + + // Count block-locals + for( int i=0; i<ulen; i++ ) { + Node use = uses[i]; + if( use.in(0)==bb && !(use instanceof PhiNode) ) { + // Normal basic block member: in(0)==bb and not a Phi + for( Node def : use._inputs ) + // Has defs from same block? Then block-local inputs + if( def != null && def.cfg0()==bb ) // Same block? + BCNTS[use._nid]++; // Raise block-local input count + } + } + + // Nodes are ready if they are not used by other nodes in this block. + // Move ready up front. We will never look at remaining nodes, later + // nodes are found by looking at users of ready nodes. + int ready = 0; + for( int i=0; i<ulen; i++ ) + if( BCNTS[uses[i]._nid]==0 ) // No block-local inputs? + uses[ready++] = uses[i]; // Move into ready set + assert ready > 0; + + // Classic list scheduler. Behind sched is scheduled. Between sched + // and ready have zero counts and are ready to schedule. Ahead of + // ready is undefined. + // + // As nodes are scheduled, the nodes they use decrement their _bcnt. Once + // that gets to 0, all the nodes using it are scheduled, so it's ready. + int sched = 0; + while( sched < ulen ) { + assert sched < ready : "Scheduling nodes that are not ready. Probably due to duplicate nodes in the user list."; + int pick = best(uses, sched,ready); // Pick best + Node best = uses[pick]; // Swap best to head of ready + uses[pick] = uses[sched]; + uses[sched++] = best; // And move it into the scheduled set + // Lower ready count of users + for( Node use : best._outputs ) + if( use instanceof ProjNode ) { + for( Node useuse : use._outputs ) + ready = ready(bb,useuse,ready); + } else + ready = ready(bb, use,ready); + } + } + + private static int ready(CFGNode bb, Node use, int ready) { + if( use != null && use.in(0)==bb && !(use instanceof PhiNode) ) { + assert BCNTS[use._nid] >= 1; + if( --BCNTS[use._nid] == 0 ) + bb._outputs._es[ready++] = use; // Became ready, move into ready set + } + return ready; + } + + + // Pick best between sched and ready. + private static int best( Node[] uses, int sched, int ready ) { + int pick = sched; + int score = score(uses[pick]); + for( int i=sched+1; i<ready; i++ ) { + int nscore = score(uses[i]); + if( nscore > score ) + { score = nscore; pick = i; } + } + return pick; + } + + // Highest score wins. Max at 1000, min at 10, except specials. + private static int score( Node n ) { + if( n.isMultiTail() ) return 1001; // Pinned just behind the multi-head + if( n instanceof CFGNode ) return n instanceof ReturnNode ? 2 : 1; // Pinned at block exit + + // Nothing special + return 500; + } + +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index f6bf71a9..ac497fe8 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -98,16 +98,12 @@ public class Parser { // Mapping from a type name to the constructor for a Type. public final HashMap<String, StructNode> INITS; - // "Linker" mapping from constant TypeFunPtrs to heads of function - public static final HashMap<TypeFunPtr,FunNode> LINKER = new HashMap<>(); - public Parser(String source) { this(source, TypeInteger.BOT); } public Parser(String source, TypeInteger arg) { Node.reset(); IterPeeps.reset(); - LINKER.clear(); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; @@ -154,38 +150,38 @@ public class Parser { public StopNode parse() { return parse(false); } public StopNode parse(boolean show) { _xScopes.push(_scope); - // Enter a new scope for the initial control and arguments - _scope.push(); - Node ctrl = new CProjNode(START, 0, ScopeNode.CTRL).peephole(); - Node pmem = new ProjNode(START, 1, ScopeNode.MEM0).peephole(); - Node arg = new ProjNode(START, 2, ScopeNode.ARG0).peephole(); - ScopeMinNode mem = new ScopeMinNode(); - mem.addDef(null); - mem.addDef(pmem); - _scope.define(ScopeNode.CTRL, Type.CONTROL , false, ctrl); - _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, mem ); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, arg ); - - // Call main - CallNode main = (CallNode)new CallNode(ctrl,pmem,arg,con(TypeFunPtr.MAIN)).peephole(); - // Call End - CallEndNode cend = (CallEndNode)new CallEndNode(main).peephole(); - STOP.addDef(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); - STOP.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); - STOP.addDef(new ProjNode(cend,2,ScopeNode.ARG0).peephole()); + //// Enter a new scope for the initial control and arguments + //_scope.push(); + //Node ctrl = new CProjNode(START, 0, ScopeNode.CTRL).peephole(); + //Node pmem = new ProjNode(START, 1, ScopeNode.MEM0).peephole(); + //Node arg = new ProjNode(START, 2, ScopeNode.ARG0).peephole(); + //ScopeMinNode mem = new ScopeMinNode(); + //mem.addDef(null); + //mem.addDef(pmem); + _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null); + _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, null); + _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null); + // + //// Call main + //CallNode main = (CallNode)new CallNode(ctrl,pmem,arg,con(TypeFunPtr.MAIN)).peephole(); + //// Call End + //CallEndNode cend = (CallEndNode)new CallEndNode(main).peephole(); + //STOP.addDef(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); + //STOP.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); + //STOP.addDef(new ProjNode(cend,2,ScopeNode.ARG0).peephole()); // Parse whole program, as-if function header "{ int arg -> body }" ReturnNode ret = parseFunctionBody("main",TypeFunPtr.MAIN,"arg"); - LINKER.put(TypeFunPtr.MAIN,ret.fun()); - main.peephole(); - if( cend.peephole() != null ) - IterPeeps.addAll(cend._outputs); + CodeGen.CODE._linker.put(TypeFunPtr.MAIN,ret.fun()); + //main.peephole(); + //if( cend.peephole() != null ) + // IterPeeps.addAll(cend._outputs); if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); // Clean up and reset - _scope.kill(); _xScopes.pop(); + _scope.kill(); for( StructNode init : INITS.values() ) init.unkeep().kill(); INITS.clear(); @@ -208,6 +204,7 @@ public class Parser { PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null); PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null); ReturnNode ret = new ReturnNode(r, rmem, rrez, fun); + fun.setRet(ret); assert ret.inProgress(); STOP.addDef(ret); @@ -217,10 +214,9 @@ public class Parser { _scope.push(); ctrl(fun); // Scope control from function // Private mem alias tracking per function - ScopeMinNode startMem = _scope.mem(); - ScopeMinNode mem = new ScopeMinNode(); + ScopeMinNode mem = new ScopeMinNode(true); mem.addDef(null); // Alias#0 - mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,startMem).peephole()); // All aliases + mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All aliases _scope.mem(mem); // All args, "as-if" called externally for( int i=0; i<ids.length; i++ ) { @@ -236,7 +232,7 @@ public class Parser { // Last expression is the return if( ctrl()._type==Type.CONTROL ) - STOP.addReturn(ctrl(), _scope.mem(), last, fun); + STOP.addReturn(ctrl(), _scope.mem().merge(), last, fun); // Function scope ends _scope.pop(); @@ -581,7 +577,9 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseAsgn(), ";"); - STOP.addReturn(ctrl(), _scope.mem(), expr, _fun); + // Need default memory, since it can be lazy, need to force + // a non-lazy Phi + STOP.addReturn(ctrl(), _scope.mem().merge(), expr, _fun); ctrl(XCTRL); // Kill control return expr; } @@ -1043,26 +1041,36 @@ public class Parser { // Check for assign-update, x += e0; char ch = _lexer.matchOperAssign(); if( ch==0 ) return rvalue; + + // the rvalue is an l-value now; it will be updated + Node lhs = rvalue.keep(); if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); + // RHS of the update + Node rhs = + (byte)ch == 1 ? con( 1) : // var++ + (byte)ch == -1 ? con(-1) : // var-- + parseAsgn(); // var op= rhs + // Widen RHS int to a RHS float + rhs = widenInt(rhs,n.type()); + // Complain a RHS float into a LHS int + if( !rhs._type.isa(n.type()) ) + throw error("Type " + rhs._type.str() + " is not of declared type " + n.type().str()); + Node op = switch(ch) { - case '+' -> new AddNode(rvalue,null); - case '-' -> new SubNode(rvalue,null); - case '*' -> new MulNode(rvalue,null); - case '/' -> new DivNode(rvalue,null); - case 1 -> new AddNode(rvalue,con( 1)); - case (char)-1 -> new AddNode(rvalue,con(-1)); - default -> throw Utils.TODO(); + case 1, (char)-1, + '+' -> new AddNode(lhs,rhs); + case '-' -> new SubNode(lhs,rhs); + case '*' -> new MulNode(lhs,rhs); + case '/' -> new DivNode(lhs,rhs); + default -> throw Utils.TODO(); }; - // Return pre-value (x+=1) or post-value (x++) - boolean pre = op.in(2)==null; - // Parse RHS argument as needed - if( pre ) - { op.keep().setDef(2,parseAsgn()); op.unkeep(); } - else rvalue.keep(); // Keep post-value across peeps - op = zsMask(peep(op),n.type()); + + op = zsMask(peep(op.widen()),n.type()); _scope.update(n,op); - return pre ? op : rvalue.unkeep(); + // Return pre-value (x+=1) or post-value (x++) + lhs.unkeep(); + return (byte)ch== 1 || (byte)ch== -1 ? lhs : op; } ScopeMinNode.Var requireLookupId(String msg) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java index bed4eb17..bacc1935 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -28,6 +28,17 @@ public abstract class CFGNode extends Node { // Block head is Start, Region, CProj, but not e.g. If, Return, Stop public boolean blockHead() { return false; } + // Get the one control following; error to call with more than one e.g. an + // IfNode or other multi-way branch. + public CFGNode uctrl() { + CFGNode c = null; + for( Node n : _outputs ) + if( n instanceof CFGNode cfg ) + { assert c==null; c = cfg; } + return c; + } + + // ------------------------------------------------------------------------ /** * Immediate dominator tree depth, used to approximate a real IDOM during @@ -90,13 +101,14 @@ public abstract class CFGNode extends Node { _pre = pre++; // Pre-walk for( Node use : _outputs ) - if( use instanceof CFGNode usecfg ) + if( use instanceof CFGNode usecfg && !(usecfg instanceof XCtrlNode) ) pre = usecfg._bltWalk(pre,use instanceof FunNode fuse ? fuse : fun,stop,post); // Post-order work: find innermost loop LoopTree inner = null, ltree; for( Node use : _outputs ) { if( !(use instanceof CFGNode usecfg) ) continue; + if( usecfg instanceof XCtrlNode ) continue; // Child visited but not post-visited? if( !post.get(usecfg._nid) ) { // Must be a backedge to a LoopNode then diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java index 0839ad2c..3ec1cd0c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; @@ -21,7 +21,7 @@ public class CallNode extends CFGNode { String fname = null; Node fptr = fptr(); if( fptr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) - fname = Parser.LINKER.get(tfp)._name; + fname = CodeGen.CODE._linker.get(tfp)._name; if( fname==null ) fptr._print0(sb,visited); else sb.append(fname); sb.append("( "); @@ -62,7 +62,7 @@ public class CallNode extends CFGNode { for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) { int fidx = Long.numberOfTrailingZeros(fidxs); TypeFunPtr tfp0 = tfp.makeFrom(fidx); - FunNode fun = Parser.LINKER.get(tfp0); + FunNode fun = CodeGen.CODE._linker.get(tfp0); if( fun!=null && !fun._folding && !linked(fun) ) link(fun); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 406b20ca..e54797a5 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -19,12 +19,18 @@ import java.util.BitSet; * The Constant's value is the value stored in it. */ public class ConstantNode extends Node { - Type _con; + public final Type _con; public ConstantNode( Type type ) { super(Parser.START); _con = type; } + public static Node make( Type type ) { + if( type==Type. CONTROL ) return new CtrlNode(); + if( type==Type.XCONTROL ) return new XCtrlNode(); + return new ConstantNode(type); + } + @Override public String label() { return "#"+_con; } @@ -37,6 +43,7 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } + @Override public boolean isConst() { return true; } @Override public Type compute() { return _con; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java new file mode 100644 index 00000000..162417bb --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CtrlNode.java @@ -0,0 +1,14 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; + +public class CtrlNode extends CFGNode { + public CtrlNode() { super(Parser.START); } + @Override public String label() { return "Ctrl"; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Cctrl"); } + @Override public boolean isConst() { return true; } + @Override public Type compute() { return Type.CONTROL; } + @Override public Node idealize() { return null; } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java index 9087926e..94d7eff7 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -9,24 +9,27 @@ public class FunNode extends RegionNode { // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; - TypeFunPtr _sig; // Initial signature may be missing return - String _name; // Debug label, optional + public final TypeFunPtr _sig; // Initial signature + public String _name; // Debug label, optional + private ReturnNode _ret; // Return pointer public FunNode( StartNode start, TypeFunPtr sig, String name ) { super(null,start); _sig=sig; _name=name; } @Override public String label() { return _name; } - ReturnNode ret() { - ReturnNode ret=null; + // Find the one CFG user from Fun. It's not always the Return, but always + // the Return *is* a CFG user of Fun. + @Override public CFGNode uctrl() { for( Node n : _outputs ) - if( n instanceof ReturnNode ret0 ) { - assert ret==null || ret==ret0; // Found more than one return - ret=ret0; - } - return ret; + if( n instanceof CFGNode cfg && + (cfg instanceof RegionNode || cfg.cfg0()==this) ) + return cfg; + return null; } + public void setRet(ReturnNode ret) { _ret=ret; } + ReturnNode ret() { assert _ret!=null; return _ret; } @Override public Type compute() { @@ -36,12 +39,23 @@ public class FunNode extends RegionNode { @Override public Node idealize() { + // When can we assume no callers? Or no other callers (except main)? + // In a partial compilation, we assume Start gets access to any/all + // top-level public structures and recursively what they point to. + // This in turn is valid arguments to every callable function. + // + // In a total compilation, we can start from Start and keep things + // more contained. + + // If no default/unknown caller, use the normal RegionNode ideal rules // to collapse - if( inProgress() ) return null; + if( unknownCallers() ) return null; return super.idealize(); } // Always in-progress until we run out of unknown callers - @Override public boolean inProgress() { return in(1) instanceof StartNode; } + public boolean unknownCallers() { return in(1) instanceof StartNode; } + + @Override public boolean inProgress() { return unknownCallers(); } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java index dcd2d4c7..1e6b2878 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -26,6 +26,9 @@ public class IfNode extends CFGNode implements MultiNode { public Node ctrl() { return in(0); } public Node pred() { return in(1); } + // No one unique control follows + @Override public CFGNode uctrl() { return null; } + @Override public Type compute() { // If the If node is not reachable then neither is any following Proj diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 33420eb9..3f2ae149 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -58,17 +58,13 @@ public class LoopNode extends RegionNode { setDef(2,f); // Now fold control into the exit - if( fun!=null ) - throw Utils.TODO(); - - // If not in a function, look for a last-level merge point; - // make if not there. - RegionNode ctrl = stop.ctrl() instanceof RegionNode r ? r : new RegionNode(null,stop.ctrl()); - PhiNode mem = stop.mem () instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode("",stop.mem ()._type,ctrl,stop.mem ()); - PhiNode expr = stop.expr() instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode("",stop.expr()._type,ctrl,stop.expr()); - if( stop.ctrl()!=ctrl ) stop.setDef(0,ctrl); - if( stop.mem ()!=mem ) stop.setDef(1,mem ); - if( stop.expr()!=expr ) stop.setDef(2,expr); + ReturnNode ret = fun.ret(); + RegionNode ctrl = ret.ctrl() instanceof RegionNode r ? r : new RegionNode(null,ret.ctrl()); + PhiNode mem = ret.mem () instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.mem ()); + PhiNode expr = ret.expr() instanceof PhiNode phi && phi.in(0)==ctrl ? phi : new PhiNode(ctrl,ret.expr()); + if( ret.ctrl()!=ctrl ) ret.setDef(0,ctrl); + if( ret.mem ()!=mem ) ret.setDef(1,mem ); + if( ret.expr()!=expr ) ret.setDef(2,expr); Node top = new ConstantNode(Type.TOP).peephole(); ctrl.addDef(t ); mem .addDef(top); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java index 6369fb01..cc7a1d13 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java @@ -114,6 +114,7 @@ public abstract class Node { public boolean isMultiHead() { return false; } public boolean isMultiTail() { return false; } + public boolean isConst () { return false; } // ------------------------------------------------------------------------ // Graph Node & Edge manipulation @@ -337,8 +338,8 @@ public abstract class Node { Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if( !(this instanceof ConstantNode) && !(this instanceof XCtrlNode) && _type.isHighOrConst() ) - return (_type==Type.XCONTROL ? new XCtrlNode() : new ConstantNode(_type)).peepholeOpt(); + if( _type.isHighOrConst() && !isConst() ) + return ConstantNode.make(_type).peepholeOpt(); // Global Value Numbering if( _hash==0 ) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 136494b5..f139e4ca 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -7,7 +7,7 @@ import java.util.BitSet; public class ParmNode extends PhiNode { // Argument indices are mapped one-to-one on CallNode inputs - final int _idx; // Argument index + public final int _idx; // Argument index public ParmNode(String label, int idx, Type declaredType, Node... inputs) { super(label,declaredType,inputs); @@ -18,7 +18,7 @@ public class ParmNode extends PhiNode { @Override public String glabel() { return _label; } - FunNode fun() { return (FunNode)in(0); } + public FunNode fun() { return (FunNode)in(0); } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6dd4f57d..91334b6c 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -8,7 +8,7 @@ import java.util.BitSet; public class PhiNode extends Node { - final String _label; + public final String _label; // The Phi type we compute must stay within the domain of the Phi. // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. @@ -16,6 +16,14 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public PhiNode(RegionNode r, Node sample) { + super(r); + _label = ""; + _declaredType = sample._type; + while( nIns() < r.nIns() ) + addDef(sample); + } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override public String glabel() { return "φ_"+_label; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index b305a96e..35563d6e 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -1,8 +1,7 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.type.*; - import java.util.BitSet; /** @@ -16,14 +15,16 @@ import java.util.BitSet; */ public class ReturnNode extends CFGNode { + public final FunNode _fun; public ReturnNode(Node ctrl, Node mem, Node data, FunNode fun) { - super(ctrl, mem, data, fun); + super(ctrl, mem, data); + _fun = fun; } public Node ctrl() { return in(0); } public Node mem () { return in(1); } public Node expr() { return in(2); } - public FunNode fun() { return (FunNode)in(3); } + public FunNode fun() { return _fun; } @Override public String label() { return "Return"; } @@ -31,7 +32,6 @@ public class ReturnNode extends CFGNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("return "); - if( expr()==null ) return sb.append("INPROGRESS"); expr()._print0(sb, visited); return sb.append(";"); } @@ -45,7 +45,7 @@ public class ReturnNode extends CFGNode { @Override public Node idealize() { return null; } public boolean inProgress() { - return ctrl() instanceof RegionNode r && r.inProgress(); + return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } // Add a return exit to the current parsing function diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java index f5a33890..f29ed20b 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -11,6 +11,8 @@ import static com.seaofnodes.simple.Utils.TODO; /* */ public class ScopeMinNode extends Node { + public final boolean _inProgress; + /** The tracked fields are now complex enough to deserve a array-of-structs layout */ public static class Var { @@ -39,8 +41,12 @@ public class ScopeMinNode extends Node { } } - public ScopeMinNode() { _type = TypeMem.BOT; } + public ScopeMinNode(boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } + + // If being used by a Scope, this is "in progress" from the Parser. + // Otherwise its a memory merge + boolean inProgress() { return _inProgress; } @Override public String label() { return "ALLMEM"; } @Override public boolean isMem() { return true; } @@ -63,6 +69,17 @@ public class ScopeMinNode extends Node { return sb.append("]"); } + // Make a memory merge: no longer a Scope really, tracking memory state but + // not related to the parser in any way. + public Node merge() { + // Force default memory to not be lazy + ScopeMinNode merge = new ScopeMinNode(false); + for( Node n : _inputs ) + merge.addDef(n); + merge._mem(1,null); + return merge.peephole(); + } + @Override public Type compute() { return TypeMem.BOT; } @@ -127,13 +144,13 @@ public class ScopeMinNode extends Node { // Fill in the backedge of any inserted Phis void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { - for( int i=2; i<back.nIns(); i++ ) { - if( back.in(i) != scope ) { - PhiNode phi = (PhiNode)in(i); - assert phi.region()==scope.ctrl() && phi.in(2)==null; - phi.setDef(2,back.in(i)); // Fill backedge + Node exit_def = exit.alias(1); + for( int i=1; i<back.nIns(); i++ ) { + if( in(i) instanceof PhiNode phi && phi.region()==scope.ctrl() ) { + assert phi.in(2)==null; + phi.setDef(2,back.in(i)==scope ? phi : back.in(i)); // Fill backedge } - if( exit.alias(i) == scope ) // Replace a lazy-phi on the exit path also + if( exit_def == scope ) // Replace a lazy-phi on the exit path also exit.alias(i,in(i)); } } @@ -155,16 +172,7 @@ public class ScopeMinNode extends Node { } } - // If being used by a Scope, this is "in progress" from the Parser. - // Once no more scope users, this is just a memory-merge. - boolean inProgress() { - for( Node n : _outputs ) - if( n instanceof ScopeNode scope ) - return true; - return false; - } - @Override boolean eq( Node n ) { - return this==n || !inProgress(); + return this==n || !_inProgress; } } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 8685e66b..e4a4ddc0 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -3,7 +3,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.*; import java.util.*; -import static com.seaofnodes.simple.Utils.TODO; /** * The Scope node is purely a parser helper - it tracks names to nodes with a @@ -33,6 +32,7 @@ public class ScopeNode extends ScopeMinNode { // A new ScopeNode public ScopeNode() { + super(true); _vars = new Ary<>(Var .class); _lexSize= new Ary<>(Integer.class); _inCons = new Ary<>(Boolean.class); @@ -113,8 +113,8 @@ public class ScopeNode extends ScopeMinNode { * Create a new variable name in the current scope */ public boolean define( String name, Type declaredType, boolean xfinal, Node init ) { - assert name.charAt(0)!='$' || _lexSize.size()==1; // Later scopes do not define memory - if( _lexSize._len > 1 ) + assert _lexSize.isEmpty() || name.charAt(0)!='$' ; // Later scopes do not define memory + if( _lexSize._len > 0 ) for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) if( _vars.get(i)._name.equals(name) ) return false; // Double define @@ -203,7 +203,7 @@ public class ScopeNode extends ScopeMinNode { dup.addDef(ctrl()); // Control input is just copied // Memory input is a shallow copy - ScopeMinNode memdup = new ScopeMinNode(), mem = mem(); + ScopeMinNode memdup = new ScopeMinNode(true), mem = mem(); memdup.addDef(null); memdup.addDef(loop ? this : mem.in(1)); for( int i=2; i<mem.nIns(); i++ ) diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java index ab6e4931..008a910f 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -29,7 +29,19 @@ public class StartNode extends LoopNode implements MultiNode { @Override public boolean isMultiHead() { return true; } @Override public boolean blockHead() { return true; } - @Override public CFGNode cfg0() { return this; } + @Override public CFGNode cfg0() { return null; } + + // Get the one control following; error to call with more than one e.g. an + // IfNode or other multi-way branch. For Start, its "main" + @Override public CFGNode uctrl() { + // Find "main", its the start. + CFGNode C = null; + for( Node use : _outputs ) + if( use instanceof FunNode fun && fun._sig==TypeFunPtr.MAIN ) + { assert C==null; C = fun; } + return C; + } + @Override public TypeTuple compute() { return TypeTuple.make(Type.CONTROL,TypeMem.TOP,_arg); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java index 4b91f1eb..fb78f720 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -22,7 +22,6 @@ public class StopNode extends CFGNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { // For the sake of many old tests, and single value prints as "return val" - if( nIns() == 3 ) return expr()._print0(sb.append("return "),visited).append(";"); if( ret()!=null ) return ret()._print0(sb,visited); sb.append("Stop[ "); for( Node ret : _inputs ) @@ -33,14 +32,10 @@ public class StopNode extends CFGNode { @Override public boolean blockHead() { return true; } - public CFGNode ctrl() { return (CFGNode)in(0); } - public Node mem () { return in(1); } - public Node expr() { return in(2); } - // If a single Return, return it. // Otherwise, null because ambiguous. public ReturnNode ret() { - return nIns()==4 && in(3) instanceof ReturnNode ret ? ret : null; + return nIns()==1 && in(0) instanceof ReturnNode ret ? ret : null; } @Override @@ -51,7 +46,7 @@ public class StopNode extends CFGNode { @Override public Node idealize() { int len = nIns(); - for( int i=3; i<nIns(); i++ ) + for( int i=0; i<nIns(); i++ ) if( ((ReturnNode)in(i)).fun()==null ) delDef(i--); if( len != nIns() ) return this; @@ -61,9 +56,8 @@ public class StopNode extends CFGNode { @Override public int idepth() { if( _idepth!=0 ) return _idepth; int d=0; - for( Node n : _inputs ) - if( n instanceof CFGNode cfg ) - d = Math.max(d,cfg.idepth()+1); + for( Node ret : _inputs ) + d = Math.max(d,((ReturnNode)ret).idepth()+1); return _idepth=d; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java index 682930e0..b591718d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -34,7 +34,7 @@ public class SubFNode extends Node { Node lhs = in(1); Type t2 = in(2)._type; - // Sub of 1. + // Sub of 0. if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) return lhs; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java index 83779dd2..3c6a5df3 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -5,9 +5,11 @@ import com.seaofnodes.simple.type.Type; import java.util.BitSet; public class XCtrlNode extends CFGNode { - public XCtrlNode( ) { super(Parser.START); } + public XCtrlNode() { super(Parser.START); } @Override public String label() { return "Xctrl"; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Xctrl"); } + @Override public boolean isConst() { return true; } + @Override public boolean isMultiTail() { return true; } @Override public Type compute() { return Type.XCONTROL; } @Override public Node idealize() { return null; } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index f21b9afa..2995e89c 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -1,9 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; -import org.junit.Ignore; import java.nio.charset.StandardCharsets; @@ -67,7 +65,7 @@ for( int pc = 0; pc < program#; pc++ ) { } return output; """); - code.parse().opto().typeCheck().codegen(); - assertEquals("Hello World!\n", Evaluator.evaluate(code._stop, 0, 10000).toString()); + code.parse().opto().typeCheck().GCM(); + assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 7f111039..224a5f01 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -10,8 +10,8 @@ public class Chapter01Test { @Test public void testSimpleProgram() { - CodeGen code = new CodeGen("return 1;").parse().opto(); - Node expr = code._stop.expr(); + CodeGen code = new CodeGen("return 1;").parse(); + Node expr = code.expr(); if( expr instanceof ConstantNode con ) { assertEquals(code._start,con.in(0)); assertEquals(TypeInteger.constant(1), con._type); @@ -52,7 +52,7 @@ public class Chapter01Test { @Test public void testNotBad3() { // this test used to fail in chapter 1 - assertEquals("return 12;", new CodeGen("return - -12;").parse().opto()._stop.print()); + assertEquals("return 12;", new CodeGen("return - -12;").parse()._stop.print()); } @Test @@ -68,7 +68,7 @@ public class Chapter01Test { @Test public void testNotBad5() { // this test used to fail in chapter 1 - assertEquals("return -100;", new CodeGen("return -100;").parse().opto()._stop.print()); + assertEquals("return -100;", new CodeGen("return -100;").parse()._stop.print()); } @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java index c85bec6f..4254f0a6 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -12,49 +12,49 @@ public class Chapter02Test { public void testParseGrammar() { CodeGen code = new CodeGen("return 1+2*3+-5;"); code.parse(true); // Disable peepholes - assertEquals("return Phi(Region,((1+(2*3))+(-5)));", code._stop.ret().print()); + assertEquals("return Phi(Region,((1+(2*3))+(-5)));", code.print()); } @Test public void testAddPeephole() { CodeGen code = new CodeGen("return 1+2;"); - code.parse().opto(); - assertEquals("return 3;", code._stop.print()); + code.parse(); + assertEquals("return 3;", code.print()); } @Test public void testSubPeephole() { CodeGen code = new CodeGen("return 1-2;"); - code.parse().opto(); - assertEquals("return -1;", code._stop.print()); + code.parse(); + assertEquals("return -1;", code.print()); } @Test public void testMulPeephole() { CodeGen code = new CodeGen("return 2*3;"); - code.parse().opto(); - assertEquals("return 6;", code._stop.print()); + code.parse(); + assertEquals("return 6;", code.print()); } @Test public void testDivPeephole() { CodeGen code = new CodeGen("return 6/3;"); - code.parse().opto(); - assertEquals("return 2;", code._stop.print()); + code.parse(); + assertEquals("return 2;", code.print()); } @Test public void testMinusPeephole() { CodeGen code = new CodeGen("return 6/-3;"); - code.parse().opto(); - assertEquals("return -2;", code._stop.print()); + code.parse(); + assertEquals("return -2;", code.print()); } @Test public void testExample() { CodeGen code = new CodeGen("return 1+2*3+-5;"); - code.parse().opto(); - assertEquals("return 2;", code._stop.print()); + code.parse(); + assertEquals("return 2;", code.print()); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 9a97d5b8..2e45ee2a 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -9,41 +9,41 @@ public class Chapter03Test { @Test public void testVarDecl() { CodeGen code = new CodeGen("int a=1; return a;"); - code.parse().opto(); assertEquals("return 1;", code._stop.print()); + code.parse(); assertEquals("return 1;", code.print()); } @Test public void testVarAdd() { CodeGen code = new CodeGen("int a=1; int b=2; return a+b;"); - code.parse().opto(); - assertEquals("return 3;", code._stop.print()); + code.parse(); + assertEquals("return 3;", code.print()); } @Test public void testVarScope() { CodeGen code = new CodeGen("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); - code.parse().opto(); - assertEquals("return 4;", code._stop.print()); + code.parse(); + assertEquals("return 4;", code.print()); } @Test public void testVarScopeNoPeephole() { CodeGen code = new CodeGen("int a=1; int b=2; int !c=0; { int b=3; c=a+b; } return c; "); code.parse(true); - assertEquals("return Phi(Region,(1+3));", code._stop.print()); + assertEquals("return Phi(Region,(1+3));", code.print()); } @Test public void testVarDist() { CodeGen code = new CodeGen("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); "); - code.parse().opto(); - assertEquals("return 8;", code._stop.print()); + code.parse(); + assertEquals("return 8;", code.print()); } @Test public void testSelfAssign() { try { - new CodeGen("int a=a; return a;").parse().opto(); + new CodeGen("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Undefined name 'a'",e.getMessage()); @@ -53,7 +53,7 @@ public class Chapter03Test { @Test public void testBad1() { try { - new CodeGen("int a=1; int b=2; int !c=0; { int b=3; c=a+b;").parse().opto(); + new CodeGen("int a=1; int b=2; int !c=0; { int b=3; c=a+b;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Syntax error, expected }: ",e.getMessage()); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java index c4073fef..27d42c43 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; +import org.junit.Ignore; import static org.junit.Assert.*; @@ -11,100 +12,101 @@ public class Chapter04Test { @Test public void testPeephole() { CodeGen code = new CodeGen("return 1+arg+2; "); - code.parse().opto(); - assertEquals("return (arg+3);", code._stop.print()); + code.parse(); + assertEquals("return (arg+3);", code.print()); } @Test public void testPeephole2() { CodeGen code = new CodeGen("return (1+arg)+2;"); - code.parse().opto(); - assertEquals("return (arg+3);", code._stop.print()); + code.parse(); + assertEquals("return (arg+3);", code.print()); } @Test public void testAdd0() { CodeGen code = new CodeGen("return 0+arg;"); - code.parse().opto(); - assertEquals("return arg;", code._stop.print()); + code.parse(); + assertEquals("return arg;", code.print()); } @Test public void testAddAddMul() { CodeGen code = new CodeGen("return arg+0+arg;"); - code.parse().opto(); - assertEquals("return (arg*2);", code._stop.print()); + code.parse(); + assertEquals("return (arg*2);", code.print()); } @Test public void testPeephole3() { CodeGen code = new CodeGen("return 1+arg+2+arg+3; "); - code.parse().opto(); - assertEquals("return ((arg*2)+6);", code._stop.print()); + code.parse(); + assertEquals("return ((arg*2)+6);", code.print()); } @Test public void testMul1() { CodeGen code = new CodeGen("return 1*arg;"); - code.parse().opto(); - assertEquals("return arg;", code._stop.print()); + code.parse(); + assertEquals("return arg;", code.print()); } @Test public void testVarArg() { CodeGen code = new CodeGen("return arg; "); - code.parse().opto(); - assertTrue(code._stop.ctrl() instanceof CProjNode); - assertTrue(code._stop.expr() instanceof ProjNode); + code.parse(); + assertTrue(code.ctrl() instanceof FunNode); + assertTrue(code.expr() instanceof ParmNode); } - @Test + // Adding functions means `main` does not constant fold the incoming arg value + @Ignore @Test public void testConstantArg() { CodeGen code = new CodeGen("return arg; ", TypeInteger.constant(2)); - code.parse().opto(); - assertEquals("return 2;", code._stop.print()); + code.parse(); + assertEquals("return 2;", code.expr().in(1).toString()); } @Test public void testCompEq() { CodeGen code = new CodeGen("return 3==3; "); - code.parse().opto(); - assertEquals("return 1;", code._stop.print()); + code.parse(); + assertEquals("return 1;", code.print()); } @Test public void testCompEq2() { CodeGen code = new CodeGen("return 3==4; "); - code.parse().opto(); - assertEquals("return 0;", code._stop.print()); + code.parse(); + assertEquals("return 0;", code.print()); } @Test public void testCompNEq() { CodeGen code = new CodeGen("return 3!=3; "); - code.parse().opto(); - assertEquals("return 0;", code._stop.print()); + code.parse(); + assertEquals("return 0;", code.print()); } @Test public void testCompNEq2() { CodeGen code = new CodeGen("return 3!=4; "); - code.parse().opto(); - assertEquals("return 1;", code._stop.print()); + code.parse(); + assertEquals("return 1;", code.print()); } @Test public void testBug1() { CodeGen code = new CodeGen("int a=arg+1; int !b=a; b=1; return a+2; "); - code.parse().opto(); - assertEquals("return (arg+3);", code._stop.print()); + code.parse(); + assertEquals("return (arg+3);", code.print()); } @Test public void testBug2() { CodeGen code = new CodeGen("int !a=arg+1; a=a; return a; "); - code.parse().opto(); - assertEquals("return (arg+1);", code._stop.print()); + code.parse(); + assertEquals("return (arg+1);", code.print()); } @Test @@ -120,8 +122,8 @@ public class Chapter04Test { @Test public void testBug4() { CodeGen code = new CodeGen("return -arg;"); - code.parse().opto(); - assertEquals("return (-arg);", code._stop.print()); + code.parse(); + assertEquals("return (-arg);", code.print()); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter05Test.java index bf074d0a..3bea9b9a 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -20,7 +20,7 @@ else { return a; """); code.parse().opto(); - assertEquals("return Phi(Region,(arg+2),(arg-3));", code._stop.toString()); + assertEquals("return Phi(Region,(arg+2),(arg-3));", code.print()); } @Test @@ -36,7 +36,7 @@ if (arg == 1) { return c; """); code.parse().opto(); - assertEquals("return Phi(Region,4,3);", code._stop.toString()); + assertEquals("return Phi(Region,4,3);", code.print()); } @Test @@ -49,7 +49,7 @@ else return 4; """); code.parse(); - assertEquals("return Phi(Region,3,4);", code._stop.expr().in(0).in(1).toString()); + assertEquals("return Phi(Region,3,4);", code.print()); } @Test @@ -64,7 +64,7 @@ else b=a+1; return a+b;"""); code.parse().opto(); - assertEquals("return ((arg*2)+Phi(Region,2,3));", code._stop.toString()); + assertEquals("return ((arg*2)+Phi(Region,2,3));", code.print()); } @Test @@ -79,7 +79,7 @@ else a=b+1; return a+b;"""); code.parse().opto(); - assertEquals("return ((Phi(Region,(arg*2),arg)+arg)+Phi(Region,4,5));", code._stop.toString()); + assertEquals("return ((Phi(Region,(arg*2),arg)+arg)+Phi(Region,4,5));", code.print()); } @Test @@ -99,7 +99,7 @@ else return a; """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Region,2,3),Phi(Region,4,5));", code._stop.toString()); + assertEquals("return Phi(Region,Phi(Region,2,3),Phi(Region,4,5));", code.print()); } @Test @@ -115,7 +115,7 @@ if( arg==0 ) return arg+a+b; """); code.parse().opto(); - assertEquals("return ((arg+Phi(Region,1,0))+Phi(Region,2,0));", code._stop.toString()); + assertEquals("return ((arg+Phi(Region,1,0))+Phi(Region,2,0));", code.print()); } @Test @@ -130,13 +130,13 @@ if( arg==1 ) return a; """); code.parse().opto(); - assertEquals("return (arg==Phi(Region,3,2));", code._stop.toString()); + assertEquals("return (arg==Phi(Region,3,2));", code.print()); } @Test public void testTrue() { StopNode stop = new Parser("return true;").parse(); - assertEquals("return 1;",stop.expr().in(0).in(1).toString()); + assertEquals("return 1;",stop.ret().print()); } @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 02814501..2107cdb0 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -10,14 +10,13 @@ public class Chapter06Test { @Test public void testPeepholeReturn() { - CodeGen code = new CodeGen( -""" + CodeGen code = new CodeGen(""" if( true ) return 2; return 1; """); code.parse().opto(); - assertEquals("return 2;", code._stop.toString()); - assertTrue(code._stop.in(0) instanceof CProjNode); + assertEquals("return 2;", code.print()); + assertTrue(code.ctrl() instanceof FunNode); } @Test @@ -30,7 +29,7 @@ if (arg) return (arg < a) < 3; // Because (arg < a) is a bool/uint1/[0-1], its always less than 3 """); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); + assertEquals("return 1;", code.print()); } @Test @@ -45,8 +44,8 @@ else return a; """); code.parse().opto(); - assertEquals("return 2;", code._stop.toString()); - assertTrue(code._stop.in(0) instanceof CProjNode); + assertEquals("return 2;", code.print()); + assertTrue(code.ctrl() instanceof FunNode); } @Test @@ -66,7 +65,7 @@ else return b; """); code.parse().opto(); - assertEquals("return Phi(Region,42,5);", code._stop.toString()); + assertEquals("return Phi(Region,42,5);", code.print()); } @Test @@ -85,13 +84,14 @@ else b=5; return b;"""); code.parse().opto(); - assertEquals("return Phi(Region,2,5);", code._stop.toString()); + assertEquals("return Phi(Region,2,5);", code.print()); } @Test public void testMerge3With2() { CodeGen code = new CodeGen( """ +arg=2; int a=1; if( arg==1 ) if( arg==2 ) @@ -105,13 +105,14 @@ else return a; """, TypeInteger.constant(2)); code.parse().opto(); - assertEquals("return 5;", code._stop.toString()); + assertEquals("return 5;", code.print()); } @Test public void testMerge3With1() { CodeGen code = new CodeGen( """ +arg=1; int a=1; if( arg==1 ) if( arg==2 ) @@ -125,7 +126,7 @@ else return a; """, TypeInteger.constant(1)); code.parse().opto(); - assertEquals("return 3;", code._stop.toString()); + assertEquals("return 3;", code.print()); } @Test @@ -145,13 +146,14 @@ else return a; """); code.parse().opto(); - assertEquals("return Phi(Region,3,Phi(Region,4,5));", code._stop.toString()); + assertEquals("return Phi(Region,3,Phi(Region,4,5));", code.print()); } @Test public void testMerge3Peephole1() { CodeGen code = new CodeGen( """ +arg=1; int a=1; if( arg==1 ) if( 1==2 ) @@ -165,13 +167,14 @@ else return a; """, TypeInteger.constant(1)); code.parse().opto(); - assertEquals("return 3;", code._stop.toString()); + assertEquals("return 3;", code.print()); } @Test public void testMerge3Peephole3() { CodeGen code = new CodeGen( """ +arg=3; int a=1; if( arg==1 ) if( 1==2 ) @@ -185,7 +188,7 @@ else return a; """, TypeInteger.constant(3)); code.parse().opto(); - assertEquals("return 4;", code._stop.toString()); + assertEquals("return 4;", code.print()); } @Test @@ -201,13 +204,14 @@ if( arg ) { return a+b; """); code.parse().opto(); - assertEquals("return Phi(Region,4,1);", code._stop.toString()); + assertEquals("return Phi(Region,4,1);", code.print()); } @Test public void testDemo1True() { CodeGen code = new CodeGen(""" +arg=1; int a = 0; int b = 1; if( arg ) { @@ -218,12 +222,13 @@ if( arg ) { return a+b; """, TypeInteger.constant(1)); code.parse().opto(); - assertEquals("return 4;", code._stop.toString()); + assertEquals("return 4;", code.print()); } @Test public void testDemo1False() { CodeGen code = new CodeGen(""" +arg=0; int a = 0; int b = 1; if( arg ) { @@ -234,7 +239,7 @@ if( arg ) { return a+b; """, TypeInteger.constant(0)); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); + assertEquals("return 1;", code.print()); } @Test @@ -252,13 +257,14 @@ if( arg ) { return a+b+c; """); code.parse().opto(); - assertEquals("return (Phi(Region,Phi(Region,2,3),0)+Phi(Region,3,1));", code._stop.toString()); + assertEquals("return (Phi(Region,Phi(Region,2,3),0)+Phi(Region,3,1));", code.print()); } @Test public void testDemo2True() { CodeGen code = new CodeGen(""" +arg=1; int a = 0; int b = 1; int c = 0; @@ -271,12 +277,13 @@ if( arg ) { return a+b+c; """, TypeInteger.constant(1)); code.parse().opto(); - assertEquals("return 6;", code._stop.toString()); + assertEquals("return 6;", code.print()); } @Test public void testDemo2arg2() { CodeGen code = new CodeGen(""" +arg=2; int a = 0; int b = 1; int c = 0; @@ -289,7 +296,7 @@ if( arg ) { return a+b+c; """, TypeInteger.constant(2)); code.parse().opto(); - assertEquals("return 5;", code._stop.toString()); + assertEquals("return 5;", code.print()); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter07Test.java index aad6a765..7cef0d9c 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -18,8 +18,8 @@ return arg; """); Node._disablePeephole = true; code.parse(); - assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code._stop.expr().in(0).in(1).toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -36,7 +36,7 @@ if(arg){}else{ return a; """); code.parse().opto(); - assertEquals("return Phi(Region,1,Phi(Loop,1,(Phi_a+1)));", code._stop.toString()); + assertEquals("return Phi(Region,1,Phi(Loop,1,(Phi_a+1)));", code.print()); } @Test @@ -56,7 +56,7 @@ while(i < arg) { return sum; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,Phi(Loop,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", code._stop.toString()); + assertEquals("return Phi(Loop,0,Phi(Loop,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", code.print()); } @Test @@ -73,8 +73,8 @@ return b; """); Node._disablePeephole = true; code.parse(); - assertEquals("return Phi(Loop,2,Phi(Region,Phi_b,4));", code._stop.expr().in(0).in(1).toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,2,Phi(Region,Phi_b,4));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -93,8 +93,8 @@ while(a < 10) { return b; """); code.parse().opto(); - assertEquals("return Phi(Loop,2,(Phi(Region,Phi_b,4)+1));", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,2,(Phi(Region,Phi_b,4)+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @@ -111,8 +111,8 @@ return a; """); Node._disablePeephole = true; code.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code._stop.expr().in(0).in(1).toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -128,8 +128,8 @@ while(a < 10) { return a; """); code.parse().opto(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test @@ -142,8 +142,8 @@ return a; """); Node._disablePeephole = true; code.parse(); - assertEquals("return Phi(Loop,1,2);", code._stop.expr().in(0).in(1).toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,2);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -156,8 +156,8 @@ while(arg) a = 2; return a; """); code.parse().opto(); - assertEquals("return Phi(Loop,1,2);", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,2);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test @@ -173,8 +173,8 @@ return a; """); Node._disablePeephole = true; code.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code._stop.expr().in(0).in(1).toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -190,8 +190,8 @@ while(a < 10) { return a; """); code.parse().opto(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test @@ -208,8 +208,8 @@ return a; """); Node._disablePeephole = true; code.parse(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code._stop.expr().in(0).in(1).toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -226,8 +226,8 @@ while(a < 10) { return a; """); code.parse().opto(); - assertEquals("return Phi(Loop,1,(Phi_a+3));", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,(Phi_a+3));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 831a3272..03a2c50a 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; @@ -23,10 +24,10 @@ while(arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add),Add);", code._stop.toString()); - assertTrue(code._stop.in(0) instanceof RegionNode); - Assert.assertEquals(5L, Evaluator.evaluate(code._stop, 1)); - Assert.assertEquals(10L, Evaluator.evaluate(code._stop, 6)); + assertEquals("return Phi(Region,Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); + Assert.assertEquals( "5", Eval2.eval(code, 1)); + Assert.assertEquals("10", Eval2.eval(code, 6)); } @@ -46,8 +47,8 @@ while(arg < 10) { return a; """); code.parse().opto(); - assertEquals("return Phi(Loop,1,Phi(Region,Phi_a,(Phi_a+1)));", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,1,Phi(Region,Phi_a,(Phi_a+1)));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @@ -65,8 +66,8 @@ while(arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof RegionNode); + assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); } @Test @@ -81,8 +82,8 @@ while(arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof RegionNode); + assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); } @@ -100,8 +101,8 @@ while(arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @@ -117,8 +118,8 @@ while(arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", code.print()); + assertTrue(code.ctrl() instanceof CProjNode); } @Test @@ -133,14 +134,14 @@ while( arg < 10 ) { return arg; """); code.parse().opto(); - assertEquals("return arg;", code._stop.toString()); + assertEquals("return arg;", code.print()); } @Test public void testRegress2() { CodeGen code = new CodeGen("if(1) return 0; else while(arg>- -arg) arg=arg+1; return 0;"); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -168,7 +169,7 @@ while(arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return arg;", code._stop.toString()); + assertEquals("return arg;", code.print()); } @Test @@ -185,8 +186,8 @@ while(arg < 10) { return a; """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Loop,1,(Phi_a+1)),Add);", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof RegionNode); + assertEquals("return Phi(Region,Phi(Loop,1,(Phi_a+1)),Add);", code.print()); + assertTrue(code.ctrl() instanceof RegionNode); } @Test @@ -201,8 +202,8 @@ while(1) { return a; """); code.parse().opto(); - assertEquals("return (Phi(Loop,1,Add)+1);", code._stop.toString()); - assertTrue(code._stop.ctrl() instanceof CProjNode prj && prj._idx==1 ); + assertEquals("return (Phi(Loop,1,Add)+1);", code.print()); + assertTrue(code.ctrl() instanceof CProjNode prj && prj._idx==1 ); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 27cd2be7..5b764013 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,35 +41,31 @@ else { return x; """); code.parse().opto(); - assertEquals("return Phi(Region,(arg*2),(Mul+1));", code._stop.toString()); - Assert.assertEquals(2L, Evaluator.evaluate(code._stop, 1)); - Assert.assertEquals(23L, Evaluator.evaluate(code._stop, 11)); + assertEquals("return Phi(Region,(arg*2),(Mul+1));", code.print()); + Assert.assertEquals( "2", Eval2.eval(code, 1)); + Assert.assertEquals("23", Eval2.eval(code, 11)); } @Test public void testGVN2() { - CodeGen code = new CodeGen( - """ -return arg*arg-arg*arg; - """); + CodeGen code = new CodeGen("return arg*arg-arg*arg;"); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - Assert.assertEquals(0L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return 0;", code.print()); + Assert.assertEquals("0", Eval2.eval(code, 1, 1)); } @Test public void testWorklist1() { - CodeGen code = new CodeGen( - """ + CodeGen code = new CodeGen(""" int step = 1; while (arg < 10) { arg = arg + step + 1; } return arg; - """); +"""); code.parse().opto(); - assertEquals("return Phi(Loop,arg,(Phi_arg+2));", code._stop.toString()); - Assert.assertEquals(11L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return Phi(Loop,arg,(Phi_arg+2));", code.print()); + Assert.assertEquals("11", Eval2.eval(code, 1)); } @Test @@ -85,8 +81,8 @@ while (arg < 10) { return arg; """); code.parse().opto(); - assertEquals("return Phi(Loop,arg,(Phi_arg+4));", code._stop.toString()); - Assert.assertEquals(13L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return Phi(Loop,arg,(Phi_arg+4));", code.print()); + Assert.assertEquals("13", Eval2.eval(code, 1)); } @Test @@ -114,7 +110,7 @@ while (arg) { return arg; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -132,14 +128,14 @@ while(v1+arg) { } """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test public void testWhile0() { CodeGen code = new CodeGen("while(0) continue; if(0) arg=0;"); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -151,7 +147,7 @@ if(0) while(0) { } """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @@ -159,14 +155,14 @@ if(0) while(0) { public void testPrecedence() { CodeGen code = new CodeGen("return 3-1+2;"); code.parse().opto(); - assertEquals("return 4;", code._stop.toString()); + assertEquals("return 4;", code.print()); } @Test public void testSwap2() { CodeGen code = new CodeGen("return 1+(1+1);"); code.parse().opto(); - assertEquals("return 3;", code._stop.toString()); + assertEquals("return 3;", code.print()); } @@ -184,7 +180,7 @@ while(arg) { return a; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(-(Phi_a+3)));", code._stop.toString()); + assertEquals("return Phi(Loop,0,(-(Phi_a+3)));", code.print()); } @Test @@ -198,7 +194,7 @@ int v0=0!=0<-0; return -0+0+0; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @@ -206,14 +202,14 @@ return -0+0+0; public void testFuzz2() { CodeGen code = new CodeGen("return 0+-0;"); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test public void testFuzz3() { CodeGen code = new CodeGen("int v0=0; while(0==69) while(v0) return 0;"); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -225,7 +221,7 @@ while(1) { } """); code.parse().opto(); - assertEquals("return Top;", code._stop.toString()); + assertEquals("return Top;", code.print()); } @Test @@ -247,7 +243,7 @@ while(1) { return 0!=0; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -259,7 +255,7 @@ while(0==1) while(v0) v0=1+v0; """); code.parse().opto(); - assertEquals("return ~int;", code._stop.toString()); + assertEquals("return ~int;", code.print()); } @Test @@ -275,14 +271,14 @@ while(1) return v1+v0; """); code.parse().opto(); - assertEquals("return Top;", code._stop.toString()); + assertEquals("return Top;", code.print()); } @Test public void testFuzz8() { CodeGen code = new CodeGen("while(arg) arg = arg - 1; return arg;"); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 461c8ed8..1f6df190 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,7 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -30,7 +28,7 @@ int r = g+h; return p-r; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -50,7 +48,7 @@ bar.a = 2; return bar.a; """); code.parse().opto(); - assertEquals("return 2;", code._stop.toString()); + assertEquals("return 2;", code.print()); } @Test @@ -66,7 +64,7 @@ else return v; """); code.parse().opto(); - assertEquals("return Vector2D;", code._stop.toString()); + assertEquals("return Vector2D;", code.print()); } @Test @@ -104,7 +102,7 @@ while (arg) { return bar.a; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(Phi_a+2));", code._stop.toString()); + assertEquals("return Phi(Loop,0,(Phi_a+2));", code.print()); } @Test @@ -156,7 +154,7 @@ if( bar ) bar.a = 1; return bar; """); code.parse().opto(); - assertEquals("return Phi(Region,null,Bar);", code._stop.toString()); + assertEquals("return Phi(Region,null,Bar);", code.print()); } @Test @@ -172,7 +170,7 @@ else bar.a = 1; return rez; """); code.parse().opto(); - assertEquals("return Phi(Region,4,3);", code._stop.toString()); + assertEquals("return Phi(Region,4,3);", code.print()); } @Test @@ -226,7 +224,7 @@ while( i.x < i.len ) { return sum; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", code._stop.toString()); + assertEquals("return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", code.print()); } @@ -245,7 +243,7 @@ while(arg) { return ret; """); code.parse().opto(); - assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code._stop.toString()); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); } @Test @@ -263,7 +261,7 @@ while(arg) { return ret; """); code.parse().opto(); - assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code._stop.toString()); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); } @@ -280,7 +278,7 @@ while(arg < 10) { return ret; """); code.parse().opto(); - assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code._stop.toString()); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", code.print()); } @Test @@ -291,8 +289,8 @@ return new s0; int v0=null.f0; """); code.parse().opto(); - assertEquals("return s0;", code._stop.toString()); - assertEquals("Obj<s0>{f0=0}", Evaluator.evaluate(code._stop, 0).toString()); + assertEquals("return s0;", code.print()); + assertEquals("s0{f0=0}", Eval2.eval(code, 0)); } @Test @@ -308,7 +306,7 @@ if(0) { } """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -322,7 +320,7 @@ else return new s0; if(new s0.f0) return 0; """); code.parse().opto(); - assertEquals("return s0;", code._stop.toString()); + assertEquals("return s0;", code.print()); } @Test @@ -350,7 +348,7 @@ s0 v1 = v0; return v1; """); code.parse().opto(); - assertEquals("return (const)s0;", code._stop.toString()); + assertEquals("return (const)s0;", code.print()); } @@ -382,7 +380,7 @@ while(0) {} } """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -393,7 +391,7 @@ while(v0) continue; return 0; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 2854941f..0b24bd5d 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import org.junit.Test; @@ -290,8 +289,8 @@ else { } } """); - code.parse().opto().typeCheck().codegen(); - assertEquals("return Phi(Region,9,Top,Top,Top,Top);", code._stop.toString()); + code.parse().opto().typeCheck().GCM(); + assertEquals("return Phi(Region,9,Top,Top,Top,Top);", code.print()); } @@ -323,13 +322,13 @@ while( prime <= arg ) { return primeCount; """); code.parse().opto(); - assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi(Region,(Phi_primeCount+1),Phi_primeCount))));", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 1)); // No primes 1 or below - assertEquals(1L, Evaluator.evaluate(code._stop, 2)); // 2 - assertEquals(2L, Evaluator.evaluate(code._stop, 3)); // 2, 3 - assertEquals(2L, Evaluator.evaluate(code._stop, 4)); // 2, 3 - assertEquals(3L, Evaluator.evaluate(code._stop, 5)); // 2, 3, 5 - assertEquals(4L, Evaluator.evaluate(code._stop, 10)); // 2, 3, 5, 7 + assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi(Region,(Phi_primeCount+1),Phi_primeCount))));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); // No primes 1 or below + assertEquals("1", Eval2.eval(code, 2)); // 2 + assertEquals("2", Eval2.eval(code, 3)); // 2, 3 + assertEquals("2", Eval2.eval(code, 4)); // 2, 3 + assertEquals("3", Eval2.eval(code, 5)); // 2, 3, 5 + assertEquals("4", Eval2.eval(code, 10)); // 2, 3, 5, 7 } @Test @@ -345,9 +344,9 @@ if (arg) v.f=1; return i; """); code.parse().opto(); - assertEquals("return 2;", code._stop.toString()); - assertEquals(2L, Evaluator.evaluate(code._stop, 0)); - assertEquals(2L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return 2;", code.print()); + assertEquals("2", Eval2.eval(code, 0)); + assertEquals("2", Eval2.eval(code, 1)); } @Test @@ -368,7 +367,7 @@ if (arg) { return i; """); code.parse().opto(); - assertEquals("return Phi(Region,.f,0);", code._stop.toString()); + assertEquals("return Phi(Region,.f,0);", code.print()); } @Test @@ -387,7 +386,7 @@ if (v1) { return v0; """); code.parse().opto(); - assertEquals("return S;", code._stop.toString()); + assertEquals("return S;", code.print()); } @@ -405,7 +404,7 @@ while (arg) v.f = 2; return i; """); code.parse().opto(); - assertEquals("return arg;", code._stop.toString()); + assertEquals("return arg;", code.print()); } @Test @@ -422,7 +421,7 @@ while(1) { return v; """); code.parse().opto(); - assertEquals("return S;", code._stop.toString()); + assertEquals("return S;", code.print()); } @Test @@ -437,7 +436,7 @@ while(1) arg = arg+ptr.v; """); code.parse().opto(); - assertEquals("return Top;", code._stop.toString()); + assertEquals("return Top;", code.print()); } @Test @@ -455,7 +454,7 @@ while (arg) { return i; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -475,7 +474,7 @@ while(arg) { return arg; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -493,7 +492,7 @@ if (arg) { return v; """); code.parse().opto(); - assertEquals("return S;", code._stop.toString()); + assertEquals("return S;", code.print()); } @Test @@ -512,7 +511,7 @@ while (arg > 0) { return v; """); code.parse().opto(); - //assertEquals("return new S;", code._stop.toString()); + //assertEquals("return new S;", code.print()); } @Test @@ -529,7 +528,7 @@ while(0>=0) { return 0; """); code.parse().opto(); - assertEquals("return Top;", code._stop.toString()); + assertEquals("return Top;", code.print()); } @Test @@ -547,7 +546,7 @@ u32 v0=0; } """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java index b5b6405c..21df8205 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -15,8 +15,8 @@ public class Chapter12Test { return 3.14; """); code.parse().opto(); - assertEquals("return 3.14;", code._stop.toString()); - assertEquals(3.14, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test @@ -26,8 +26,8 @@ return 3.14; return 3.14; """); code.parse().opto(); - assertEquals("return 3.14;", code._stop.toString()); - assertEquals(3.14, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test @@ -43,9 +43,9 @@ while( 1 ) { return guess; """); code.parse().opto(); - assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0f));", code._stop.toString()); - assertEquals(3.0, Evaluator.evaluate(code._stop, 9)); - assertEquals(1.414213562373095, Evaluator.evaluate(code._stop, 2)); + assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0f));", code.print()); + assertEquals("3.0", Eval2.eval(code, 9)); + assertEquals("1.414213562373095", Eval2.eval(code, 2)); } @Test @@ -56,7 +56,7 @@ flt x = arg; return x+1==x; """); code.parse().opto(); - assertEquals("return ((flt)arg==(ToFloat+1.0f));", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java index ca811a2a..645c066a 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -13,8 +12,8 @@ public class Chapter13Test { return 3.14; """); code.parse().opto(); - assertEquals("return 3.14;", code._stop.toString()); - assertEquals(3.14, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test @@ -55,8 +54,8 @@ if( next==null ) return 1; return next.i; """); code.parse().opto(); - assertEquals("return Phi(Region,0,1,.i);", code._stop.toString()); - assertEquals(2L, Evaluator.evaluate(code._stop, 3)); + assertEquals("return Phi(Region,0,1,.i);", code.print()); + assertEquals("2", Eval2.eval(code, 3)); } @Test @@ -74,7 +73,7 @@ f0.i = i0; return f0.i.f.i.i; """); code.parse().opto(); - assertEquals("return 17;", code._stop.toString()); + assertEquals("return 17;", code.print()); } @Test @@ -86,7 +85,7 @@ N n = new N; return n.next; """); code.parse().opto(); - assertEquals("return null;", code._stop.toString()); + assertEquals("return null;", code.print()); } @Test @@ -99,7 +98,7 @@ N n = new N { next = new M; }; return n.next; """); code.parse().opto(); - assertEquals("return (const)M;", code._stop.toString()); + assertEquals("return (const)M;", code.print()); } @Test @@ -135,8 +134,8 @@ return n.i; struct S{}; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test @@ -159,7 +158,7 @@ struct S2 { int x; }; return new S1.s=new S2; """); code.parse().opto(); - assertEquals("return S2;", code._stop.toString()); + assertEquals("return S2;", code.print()); } @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 41fb546d..a3025001 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; @@ -16,8 +15,8 @@ public class Chapter14Test { return 3.14; """); code.parse().opto(); - assertEquals("return 3.14;", code._stop.toString()); - assertEquals(3.14, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test @@ -32,8 +31,8 @@ if( b > 2 ) c = 1; return c; """); code.parse().opto(); - assertEquals("return 99;", code._stop.toString()); - assertEquals(99L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 99;", code.print()); + assertEquals("99", Eval2.eval(code, 0)); } @Test @@ -45,8 +44,8 @@ b = b + 456;// Truncate return b; """); code.parse().opto(); - assertEquals("return 67;", code._stop.toString()); - assertEquals(67L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 67;", code.print()); + assertEquals("67", Eval2.eval(code, 0)); } @@ -59,7 +58,7 @@ while( b ) b = b + 456;// Truncate return b; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -72,8 +71,8 @@ u1 c = b; // No more truncate needed return c; """); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test @@ -85,8 +84,8 @@ b = b+456 & 31; // Precedence return b; """); code.parse().opto(); - assertEquals("return 3;", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); } @Test @@ -99,8 +98,8 @@ f.b = 123; return f.b; """); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test @@ -111,8 +110,8 @@ i8 b = 255; // Chopped return b; // Sign extend """); code.parse().opto(); - assertEquals("return -1;", code._stop.toString()); - assertEquals(-1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return -1;", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); } @Test @@ -124,9 +123,9 @@ b = b + 1;// Truncate return b; """); code.parse().opto(); - assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); - assertEquals(-128L, Evaluator.evaluate(code._stop, 127)); + assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", code.print()); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("-128", Eval2.eval(code, 127)); } @Test @@ -138,8 +137,8 @@ int c = 123456789 & mask; return c; // """); code.parse().opto(); - assertEquals("return 52501;", code._stop.toString()); - assertEquals(52501L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 52501;", code.print()); + assertEquals("52501", Eval2.eval(code, 0)); } @Test @@ -149,8 +148,8 @@ return c; // return (arg | 123 ^ 456) >>> 1; """); code.parse().opto(); - assertEquals("return (((arg|123)^456)>>>1);", code._stop.toString()); - assertEquals(217L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return (((arg|123)^456)>>>1);", code.print()); + assertEquals("217", Eval2.eval(code, 0)); } @Test @@ -175,8 +174,8 @@ while(v1) break; return v1; """); code.parse().opto(); - assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test @@ -194,8 +193,8 @@ if(0&0>>>0) { return v0; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test @@ -220,8 +219,8 @@ f32 ff32 = 3.141592653589793; if( ff32 != 3.1415927410125732) return 5; return 0; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java index fc9624d8..86f5007d 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -1,7 +1,5 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import static org.junit.Assert.*; @@ -14,8 +12,8 @@ public class Chapter15Test { return 3.14; """); code.parse().opto(); - assertEquals("return 3.14;", code._stop.toString()); - assertEquals(3.14, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @Test @@ -28,8 +26,8 @@ c.l = c; return c; """); code.parse().opto(); - assertEquals("return C;", code._stop.toString()); - assertEquals("Obj<C>@1{l=obj@1}", Evaluator.evaluate(code._stop, 0).toString()); + assertEquals("return C;", code.print()); + assertEquals("C{l=$cyclic}", Eval2.eval(code, 0)); } @Test @@ -47,8 +45,8 @@ output[i] = 1; return output; """); code.parse().opto(); - assertEquals("return [u8];", code._stop.toString()); - assertEquals("\u0001", Evaluator.evaluate(code._stop, 0).toString()); + assertEquals("return [u8];", code.print()); + assertEquals("\u0001", Eval2.eval(code, 0)); } @Test @@ -59,8 +57,8 @@ int[] is = new int[2]; return is[1]; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test @@ -72,8 +70,8 @@ int[] is2 = new int[2]; return is[1]; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test @@ -86,8 +84,8 @@ a[1] = 2; return a[0]; """); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test @@ -99,8 +97,8 @@ A?[] !a = new A?[2]; return a; """); code.parse().opto(); - assertEquals("return [*A?];", code._stop.toString()); - assertEquals("Obj<[*A?]>{#=2,[]=[null,null]}", Evaluator.evaluate(code._stop, 0).toString()); + assertEquals("return [*A?];", code.print()); + assertEquals("*A {int !i; }?[ null,null]", Eval2.eval(code, 0)); } @Test @@ -128,9 +126,9 @@ else { return rez; """); code.parse().opto(); - assertEquals("return Phi(Region,1.2,Phi(Region,2.3,3.14));", code._stop.toString()); - assertEquals(3.14, Evaluator.evaluate(code._stop, 0)); - assertEquals(1.2 , Evaluator.evaluate(code._stop, 1)); + assertEquals("return Phi(Region,1.2,Phi(Region,2.3,.y));", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + assertEquals("1.2", Eval2.eval(code, 1)); } @Test @@ -169,8 +167,8 @@ root._kids[0] = new Tree; return root; """); code.parse().opto(); - assertEquals("return Tree;", code._stop.toString()); - assertEquals("Obj<Tree>{_kids=Obj<[*Tree?]>{#=2,[]=[Obj<Tree>{_kids=null},null]}}", Evaluator.evaluate(code._stop, 0).toString()); + assertEquals("return Tree;", code.print()); + assertEquals("Tree{_kids=*Tree?[ Tree{_kids=null},null]}", Eval2.eval(code, 0)); } @Test @@ -181,7 +179,7 @@ struct S { int a; int[] b; }; return 0; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @Test @@ -204,8 +202,8 @@ while( i < ary# - 1 ) { return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """); code.parse().opto(); - assertEquals("return (.[]+(.[]*1000));", code._stop.toString()); - assertEquals(1006L, Evaluator.evaluate(code._stop, 4)); + assertEquals("return (.[]+(.[]*1000));", code.print()); + assertEquals("1006", Eval2.eval(code, 4)); } @Test @@ -245,13 +243,8 @@ while( j < nprimes ) { return rez; """); code.parse().opto(); - assertEquals("return [int];", code._stop.toString()); - Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(code._stop, 20); - assertEquals("[int] {int #; int ![]; }",obj.struct().toString()); - long nprimes = (Long)obj.fields()[0]; - long[] primes = new long[]{2,3,5,7,11,13,17,19}; - for( int i=0; i<nprimes; i++ ) - assertEquals(primes[i],(long)(Long)obj.fields()[i+1]); + assertEquals("return [int];", code.print()); + assertEquals("int[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20)); } @Test @@ -267,8 +260,8 @@ if (arg) s1 = new S; return s1.i + s1.f; """); code.parse().opto(); - assertEquals("return ((flt).i+.f);", code._stop.toString()); - assertEquals(0.0, Evaluator.evaluate(code._stop, 0)); + assertEquals("return ((flt).i+.f);", code.print()); + assertEquals("0.0", Eval2.eval(code, 0)); } @@ -311,11 +304,11 @@ int[] is = new int[arg]; return is[1]; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 4)); - try { Evaluator.evaluate(code._stop,0); } + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 4)); + try { Eval2.eval(code,0); } catch( ArrayIndexOutOfBoundsException e ) { assertEquals("Array index 1 out of bounds for array length 0",e.getMessage()); } - try { Evaluator.evaluate(code._stop,-1); } + try { Eval2.eval(code,-1); } catch( NegativeArraySizeException e ) { assertEquals("-1",e.getMessage()); } } @@ -341,8 +334,8 @@ while(v5+(0&0)) { return v1; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test @@ -356,7 +349,7 @@ int v8=0; while(0<--1>>>---(v7*0==v8)) {} """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } @@ -380,6 +373,6 @@ else { } """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); + assertEquals("return 0;", code.print()); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 255a721a..ad3dc690 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -15,8 +15,8 @@ public class Chapter16Test { return 3.14; """); code.parse().opto(); - assertEquals("return 3.14;", code._stop.toString()); - assertEquals(3.14, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } @@ -28,8 +28,8 @@ int x, y; return x+y; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test public void testMulti1() { @@ -39,8 +39,8 @@ int x=2, y=x+1; return x+y; """); code.parse().opto(); - assertEquals("return 5;", code._stop.toString()); - assertEquals(5L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 5;", code.print()); + assertEquals("5", Eval2.eval(code, 0)); } // @Test @@ -64,9 +64,9 @@ if( arg ) { int x = y; x = x*x; y=x; } // Shadow final x return y; """); code.parse().opto(); - assertEquals("return Phi(Region,9,3);", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 0)); - assertEquals(9L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return Phi(Region,9,3);", code.print()); + assertEquals("3", Eval2.eval(code, 0)); + assertEquals("9", Eval2.eval(code, 1)); } @Test @@ -77,8 +77,8 @@ X z = new X; return z.x; """); code.parse().opto(); - assertEquals("return 3;", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); } @Test @@ -89,8 +89,8 @@ X z = new X { x=3; }; return z.x; """); code.parse().opto(); - assertEquals("return 3;", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); } @Test @@ -101,8 +101,8 @@ X z = new X { x = 4; }; return z.x; """); code.parse().opto(); - assertEquals("return 4;", code._stop.toString()); - assertEquals(4L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @@ -114,8 +114,8 @@ Point p = new Point { x=3; y=4; }; return p; """); code.parse().opto(); - assertEquals("return (const)Point;", code._stop.toString()); - assertEquals("Obj<Point>{x=3,y=4}", Evaluator.evaluate(code._stop, 0).toString()); + assertEquals("return (const)Point;", code.print()); + assertEquals("Point{x=3,y=4}", Eval2.eval(code, 0)); } @Test @@ -175,8 +175,8 @@ p.x++; return p; """); code.parse().opto(); - assertEquals("return Point;", code._stop.toString()); - assertEquals("Obj<Point>{x=4,y=4}", Evaluator.evaluate(code._stop, 0).toString()); + assertEquals("return Point;", code.print()); + assertEquals("Point{x=4,y=4}", Eval2.eval(code, 0)); } // Same as the Chapter13 test with the same name, but using the new @@ -197,10 +197,10 @@ if( !next ) return 1; return next.i; """); code.parse().opto(); - assertEquals("return Phi(Region,0,1,.i);", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); - assertEquals(1L, Evaluator.evaluate(code._stop, 1)); - assertEquals(2L, Evaluator.evaluate(code._stop, 3)); + assertEquals("return Phi(Region,0,1,.i);", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + assertEquals("2", Eval2.eval(code, 3)); } @Test @@ -228,10 +228,10 @@ if( !next ) return 1; return next.i; """); code.parse().opto(); - assertEquals("return Phi(Region,0,1,.i);", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); - assertEquals(1L, Evaluator.evaluate(code._stop, 1)); - assertEquals(2L, Evaluator.evaluate(code._stop, 11)); + assertEquals("return Phi(Region,0,1,.i);", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + assertEquals("2", Eval2.eval(code, 11)); } @Test @@ -253,8 +253,8 @@ struct Square { return new Square; """); code.parse().opto(); - assertEquals("return Square;", code._stop.toString()); - assertEquals("Obj<Square>{side=3.0,diag=1.7320508075688772}", Evaluator.evaluate(code._stop, 3).toString()); - assertEquals("Obj<Square>{side=4.0,diag=2.0}", Evaluator.evaluate(code._stop, 4).toString()); + assertEquals("return Square;", code.print()); + assertEquals("Square{side=3.0,diag=1.7320508075688772}", Eval2.eval(code, 3)); + assertEquals("Square{side=4.0,diag=2.0}", Eval2.eval(code, 4)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java index 06eb150d..4bcb9daa 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -1,9 +1,6 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -18,8 +15,8 @@ return i; //return 3.14; """); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @@ -30,8 +27,8 @@ return i; return arg++; """); code.parse().opto(); - assertEquals("return arg;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return arg;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test @@ -40,8 +37,8 @@ return arg++; return arg+++arg++; """); code.parse().opto(); - assertEquals("return ((arg*2)+1);", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return ((arg*2)+1);", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test @@ -51,8 +48,8 @@ return arg+++arg++; return -arg---arg--; """); code.parse().opto(); - assertEquals("return (-((arg*2)+-1));", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return (-((arg*2)+-1));", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test @@ -64,8 +61,8 @@ xs[1]++; return xs[0]; """); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 2)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 2)); } @Test @@ -76,8 +73,8 @@ xs[0]--; return xs[0]; """); code.parse().opto(); - assertEquals("return 255;", code._stop.toString()); - assertEquals(255L, Evaluator.evaluate(code._stop, 2)); + assertEquals("return 255;", code.print()); + assertEquals("255", Eval2.eval(code, 2)); } @Test @@ -89,34 +86,49 @@ s.x--; return s.x; """); code.parse().opto(); - assertEquals("return 65535;", code._stop.toString()); - assertEquals(65535L, Evaluator.evaluate(code._stop, 2)); + assertEquals("return 65535;", code.print()); + assertEquals("65535", Eval2.eval(code, 2)); } @Test public void testInc6() { CodeGen code = new CodeGen("return --arg;"); code.parse().opto(); - assertEquals("return (arg+-1);", code._stop.toString()); - assertEquals(-1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return (arg+-1);", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); } @Test public void testInc7() { CodeGen code = new CodeGen("u8 x=0; return --x;"); code.parse().opto(); - assertEquals("return 255;", code._stop.toString()); - assertEquals(255L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 255;", code.print()); + assertEquals("255", Eval2.eval(code, 0)); } @Test public void testInc8() { CodeGen code = new CodeGen("int x; x+=2; return x+=3;"); code.parse().opto(); - assertEquals("return 5;", code._stop.toString()); - assertEquals(5L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 5;", code.print()); + assertEquals("5", Eval2.eval(code, 0)); } + @Test + public void testInc9() { + CodeGen code = new CodeGen("flt x = 1.5; x++; return x;"); + code.parse().opto(); + assertEquals("return 2.5f;", code.print()); + assertEquals("2.5", Eval2.eval(code, 0)); + } + + @Test public void testInt10() { + CodeGen code = new CodeGen("flt x = 1.5; x++; int i = x; return i;"); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Type 2.5f is not of declared type int",e.getMessage()); } + } + + // --------------------------------------------------------------- @Test public void testVar0() { CodeGen code = new CodeGen("var d; return d;"); @@ -133,29 +145,29 @@ return s.x; @Test public void testVar2() { CodeGen code = new CodeGen("int x; x=3; x++; return x; // Ok, no initializer so x is mutable "); code.parse().opto(); - assertEquals("return 4;", code._stop.toString()); - assertEquals(4L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @Test public void testVar3() { CodeGen code = new CodeGen("int x=3; x++; return x; // Ok, primitive so x is mutable despite initializer "); code.parse().opto(); - assertEquals("return 4;", code._stop.toString()); - assertEquals(4L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @Test public void testVar4() { CodeGen code = new CodeGen("struct S{int x;}; S s; s=new S; s.x++; return s.x; // Ok, no initializer so x is mutable "); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testVar5() { CodeGen code = new CodeGen("struct S{int x;}; S s; s=new S{x=3;}; s.x++; return s.x; // Ok, no initializer so x is mutable "); code.parse().opto(); - assertEquals("return 4;", code._stop.toString()); - assertEquals(4L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 4;", code.print()); + assertEquals("4", Eval2.eval(code, 0)); } @Test public void testVar6() { @@ -173,15 +185,15 @@ return s.x; @Test public void testVar8() { CodeGen code = new CodeGen("struct S{int x;}; S !s=new S; s.x++; return s.x; // Ok, has '!' so s.x is mutable "); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testVar9() { CodeGen code = new CodeGen("struct S{int x;}; var s=new S; s.x++; return s.x; // Ok, has var so s.x is mutable "); code.parse().opto(); - assertEquals("return 1;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 1;", code.print()); + assertEquals("1", Eval2.eval(code, 0)); } @Test public void testVar10() { @@ -226,8 +238,8 @@ int x5 = xfoo.bar.x; // Ok to read through xfoo, gets 5 return x4*10+x5; """); code.parse().opto(); - assertEquals("return 45;", code._stop.toString()); - assertEquals(45L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 45;", code.print()); + assertEquals("45", Eval2.eval(code, 0)); } @Test @@ -235,7 +247,7 @@ return x4*10+x5; CodeGen code = new CodeGen(""" int i,i++; """); - try { code.parse().opto(); fail(); } + try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Redefining name 'i'",e.getMessage()); } } @@ -274,9 +286,9 @@ return new A { return arg ? 1 : 2; """); code.parse().opto(); - assertEquals("return Phi(Region,1,2);", code._stop.toString()); - assertEquals(2L, Evaluator.evaluate(code._stop, 0)); - assertEquals(1L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return Phi(Region,1,2);", code.print()); + assertEquals("2", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); } @Test @@ -285,8 +297,8 @@ return arg ? 1 : 2; return arg ? 0 : arg; """); code.parse().opto(); - assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test @@ -297,9 +309,9 @@ var b = arg ? new Bar : null; return b ? b.x++ + b.x++ : -1; """); code.parse().opto(); - assertEquals("return Phi(Region,1,-1);", code._stop.toString()); - assertEquals(-1L, Evaluator.evaluate(code._stop, 0)); - assertEquals( 1L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return Phi(Region,((.x*2)+1),-1);", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); } @Test @@ -310,9 +322,9 @@ var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1; """); code.parse().opto(); - assertEquals("return Phi(Region,1,-1);", code._stop.toString()); - assertEquals(-1L, Evaluator.evaluate(code._stop, 0)); - assertEquals( 1L, Evaluator.evaluate(code._stop, 1)); + assertEquals("return Phi(Region,((.x*2)+1),-1);", code.print()); + assertEquals("-1", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); } @Test @@ -324,10 +336,10 @@ var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" """); code.parse().opto(); - assertEquals("return Phi(Region,Phi(Region,.x,.x),0);", code._stop.toString()); - assertEquals( 0L, Evaluator.evaluate(code._stop, 0)); - assertEquals( 1L, Evaluator.evaluate(code._stop, 1)); - assertEquals( 2L, Evaluator.evaluate(code._stop, 2)); + assertEquals("return Phi(Region,Phi(Region,.x,.x),0);", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + assertEquals("2", Eval2.eval(code, 2)); } @Test @@ -337,8 +349,8 @@ flt f=arg?1:1.2; return f; // missing widening """); code.parse().opto(); - assertEquals("return Phi(Region,1.0f,1.2);", code._stop.toString()); - assertEquals(1.2, Evaluator.evaluate(code._stop, 0)); + assertEquals("return Phi(Region,1.0f,1.2);", code.print()); + assertEquals("1.2", Eval2.eval(code, 0)); } // --------------------------------------------------------------- @@ -351,9 +363,9 @@ for( int i=0; i<arg; i++ ) return sum; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 3)); - assertEquals(45L, Evaluator.evaluate(code._stop, 10)); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print()); + assertEquals("3", Eval2.eval(code, 3)); + assertEquals("45", Eval2.eval(code, 10)); } @Test public void testFor1() { @@ -364,9 +376,9 @@ for( ; i<arg; i++ ) return sum; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 3)); - assertEquals(45L, Evaluator.evaluate(code._stop, 10)); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print()); + assertEquals("3", Eval2.eval(code, 3)); + assertEquals("45", Eval2.eval(code, 10)); } @Test public void testFor2() { @@ -379,9 +391,9 @@ for( int i=0; ; i++ ) { return sum; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 3)); - assertEquals(45L, Evaluator.evaluate(code._stop, 10)); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print()); + assertEquals("3", Eval2.eval(code, 3)); + assertEquals("45", Eval2.eval(code, 10)); } @Test public void testFor3() { @@ -392,9 +404,9 @@ for( int i=0; i<arg; ) return sum; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code._stop.toString()); - assertEquals(3L, Evaluator.evaluate(code._stop, 3)); - assertEquals(45L, Evaluator.evaluate(code._stop, 10)); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print()); + assertEquals("3", Eval2.eval(code, 3)); + assertEquals("45", Eval2.eval(code, 10)); } @Test public void testFor4() { @@ -429,8 +441,8 @@ struct A{ return new A; """); code.parse().opto(); - assertEquals("return A;", code._stop.toString()); - assertEquals("Obj<A>{f1=null,f2=null}", Evaluator.evaluate(code._stop).toString()); + assertEquals("return A;", code.print()); + assertEquals("A{f1=null,f2=null}", Eval2.eval(code,0)); } @Test @@ -443,8 +455,8 @@ struct A{ return new A.not_array_of_b; """); code.parse().opto(); - assertEquals("return (const)[*B?];", code._stop.toString()); - assertEquals("Obj<[*B?]>{#=0,[]=[]}", Evaluator.evaluate(code._stop).toString()); + assertEquals("return (const)[*B?];", code.print()); + assertEquals("*B?[]", Eval2.eval(code,0)); } // --------------------------------------------------------------- @@ -462,8 +474,8 @@ for( ; ptr; ptr = ptr.next ) return sum; """); code.parse().opto(); - assertEquals("return Phi(Loop,0,(Phi_sum+.i));", code._stop.toString()); - assertEquals(45L, Evaluator.evaluate(code._stop, 10)); + assertEquals("return Phi(Loop,0,(Phi_sum+.i));", code.print()); + assertEquals("45", Eval2.eval(code, 10)); } @Test @@ -492,14 +504,9 @@ for( int j=0; j<nprimes; j++ ) rez[j] = primes[j]; return rez; """); - code.parse().opto(); - assertEquals("return [int];", code._stop.toString()); - Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(code._stop, 20); - assertEquals("[int] {int #; int ![]; }",obj.struct().toString()); - long nprimes = (Long)obj.fields()[0]; - long[] primes = new long[]{2,3,5,7,11,13,17,19}; - for( int i=0; i<nprimes; i++ ) - assertEquals(primes[i],(long)(Long)obj.fields()[i+1]); + code.parse().opto().typeCheck().GCM(); + assertEquals("return [int];", code.print()); + assertEquals("int[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 938feab0..15baccf7 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import org.junit.Ignore; @@ -11,17 +10,14 @@ public class Chapter18Test { @Test public void testJig() { - CodeGen code = new CodeGen( -""" -0 ; + CodeGen code = new CodeGen(""" +return 0; """); - code.parse().opto(); + code.parse().opto().typeCheck().GCM(); assertEquals("return 0;", code._stop.toString()); - assertEquals(0L, Evaluator.evaluate(code._stop, 0)); + assertEquals("0", Eval2.eval(code, 0)); } - /* - */ // --------------------------------------------------------------- @Test @@ -32,7 +28,7 @@ return x2; """); code.parse().opto(); assertEquals("return null;", code._stop.toString()); - assertNull( Evaluator.evaluate( code._stop, 0 ) ); + assertEquals("null", Eval2.eval(code, 0 ) ); } @Ignore @Test @@ -45,7 +41,7 @@ return sq; """); code.parse().opto(); assertEquals("return fcn;", code._stop.toString()); - assertEquals(1L, Evaluator.evaluate(code._stop, 0)); + assertEquals("1", Eval2.eval(code, 0)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java new file mode 100644 index 00000000..50b26464 --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java @@ -0,0 +1,244 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.node.*; + +import java.util.Arrays; +import java.util.IdentityHashMap; +import java.util.Objects; + +public abstract class Eval2 { + + private static Object[] DATA; + public static String eval( CodeGen code, long arg ) { return eval(code,arg,1000); } + public static String eval( CodeGen code, long arg, int timeout ) { + if( code._phase.ordinal() < CodeGen.Phase.TypeCheck .ordinal() ) code.typeCheck(); + if( code._phase.ordinal() < CodeGen.Phase.Schedule .ordinal() ) code.GCM(); + if( code._phase.ordinal() < CodeGen.Phase.LocalSched.ordinal() ) code.localSched(); + + + // 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. + DATA = new Object[Node.UID()]; + + // Start at the START + CFGNode C = code._start, prior = null; + + // Evaluate until we return or timeout. Each outer loop step computes + // all data nodes under some new Control. + SB sb = null; //new SB(); // TRACE + IdentityHashMap visit = new IdentityHashMap(); + while( true ) { + // Compute input path on Phis for this Region, + // or path is invalid for non-Region + int path = C instanceof RegionNode r ? r._inputs.find( prior ) : -1; + + // Run the worklist dry, computing data nodes under control of C + if( sb!=null ) { IRPrinter.printLine(C,sb.p("--- ")); System.out.print(sb); sb.clear(); } + for( Node use : C._outputs ) + step(use, path, arg, sb, visit); + + // Find the next control target + prior = C; + C = C.uctrl(); // Next unique control target + switch( prior ) { + case FunNode fun : if( loopCnt++ > timeout ) return null; break; // Timeout + case LoopNode loop: if( loopCnt++ > timeout ) return null; break; // Timeout + case IfNode iff: C = iff.cproj( val(iff.pred())==null || (val(iff.pred()) instanceof Long x && x==0L) ? 1 : 0); break; + case RegionNode r: break; + case CProjNode cproj: break; + // TODO: Need a Call-stack here + case ReturnNode ret: return prettyPrint(ret.expr()._type,val(ret.expr())); + default: throw Utils.TODO(); + } + } + + } + + private static Object con( Type t ) { + if( t instanceof TypeInteger i ) + return i.isConstant() ? (Long)i.value() : "INT"; + if( t instanceof TypeFloat f ) + return f.isConstant() ? (Double)f.value() : "FLT"; + // + return null; + } + + // Use type to print x as a string + 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); + // Since never can close the type cycle, without cyclic types, have + // to handle FRefs even here + if( tmp.isFRef() ) + tmp = tmp.makeFrom(((TypeMemPtr)Parser.TYPES.get(tmp._obj._name))._obj); + + Object[] xs = (Object[])x; // Array of fields + if( tmp._obj.isAry() ) { + Type elem = tmp._obj._fields[1]._type; + if( elem == 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("[ "); + 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]._type,xs[i], sb.p(flds[i]._fname).p("="), visit ).p(","); + sb.unchar().p("}"); + } + yield sb; + } + 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(); + } + }; + } + + // Take a worklist step: one data op from the current Control is updated. + private static void step(Node n, int path, long arg, SB sb, IdentityHashMap visit) { + // Only data nodes + if( n instanceof CFGNode ) return; + // Compute new value + DATA[n._nid] = compute(n,path,arg); + // Trace + if( sb!=null ) { + IRPrinter.printLine(n,sb).unchar(); + _print( n._type, DATA[n._nid], sb.p('\t'), visit ); + System.out.println(sb); + sb.clear(); + visit.clear(); + } + // Also do any following projections, which are not in the local schedule otherwise + if( n instanceof MultiNode ) + for( Node use : n._outputs ) + step(use,-1,arg,sb,visit); + } + + // From here down shamelessly copied from Evaluator, written by @Xmilia + private static Object compute( Node n, int path, long arg ) { + return switch( n ) { + case AddFNode adf -> d(adf.in(1)) + d(adf.in(2)); + case AddNode add -> x(add.in(1)) + x(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 -> x( le.in(1)) <= x(le .in(2)) ? 1L : 0L; + case BoolNode.LT lt -> x( lt.in(1)) < x(lt .in(2)) ? 1L : 0L; + case CastNode cast -> val(cast.in(1)); + case ConstantNode con -> con(con._con); + case DivFNode dvf -> d(dvf.in(2))==0 ? 0D : d(dvf.in(1)) / d(dvf.in(2)); + case DivNode div -> x(div.in(2))==0 ? 0L : x(div.in(1)) / x(div.in(2)); + case LoadNode ld -> load(ld); + case MinusNode sub -> - x(sub.in(1)); + case MulNode mul -> x(mul.in(1)) * x(mul.in(2)); + case NewNode alloc -> alloc(alloc); + case OrNode or -> x(or .in(1)) | x(or .in(2)); + case PhiNode phi -> phi instanceof ParmNode parm && parm.fun()._sig==TypeFunPtr.MAIN && parm._idx==2 ? arg : val(phi.in(path)); + 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 ScopeMinNode merge-> "$mem"; + 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 -> x(sub.in(1)) - x(sub.in(2)); + 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 + static Object val( Node n ) { return DATA[n._nid]; } + // Fetch and unbox as primitive long + static long x( Node n ) { return DATA[n._nid]==null ? 0 : (Long) DATA[n._nid]; } + // Fetch and unbox as primitive double + static double d( Node n ) { return DATA[n._nid]==null ? 0 : (Double)DATA[n._nid]; } + + // Convert array size to array element count + private static int offToIdx( long off, TypeStruct t) { + off -= t.aryBase(); + int scale = t.aryScale(); + long mask = (1L << scale)-1; + assert (off & mask) == 0; + return (int)(off>>scale); + } + + // Builds and returns a pointer Object + private static Object alloc(NewNode alloc) { + TypeStruct type = alloc._ptr._obj; + 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]._type; + if (elem instanceof TypeInteger) { + Arrays.fill( ary, 0L ); + } else if (elem instanceof TypeFloat) { + Arrays.fill( ary, 0D ); + } else { + assert elem instanceof TypeMemPtr; + } + // Length value + //body[0] = vall(alloc.in(2+2)); + return ary; + } + + int num = type._fields.length; + Object[] ptr = new Object[num]; + for( int i=0; i<num; i++ ) + ptr[i] = val(alloc.in(2+i+num)); + return ptr; + } + + private static Object load( LoadNode ld ) { + TypeMemPtr tmp = (TypeMemPtr)ld.ptr()._type; + Object[] fs = (Object[])val(ld.ptr()); + if( ld._name.equals("#") ) + return (long)fs.length; + 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 ) { + 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()); + fs[idx] = val; + return "$mem"; + } + +} diff --git a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index ab413ed2..ff9eb1b1 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -269,9 +269,8 @@ public class Evaluator { private Object cons(ConstantNode cons) { var type = cons.compute(); - if (type instanceof TypeInteger i) return i.value(); + if (type instanceof TypeInteger i) return i.isConstant() ? i.value() : Integer.MAX_VALUE; if (type instanceof TypeFloat i) return i.value(); - assert type == Type.NIL; return null; } @@ -333,7 +332,6 @@ public class Evaluator { case null: return Status.FALLTHROUGH; case ReturnNode ret : return val(ret .expr()); - case StopNode stop: return val(stop.expr()); case IfNode ifn: block = block.next()[isTrue(val(ifn.in(1))) ? 0 : 1]; if (block == null) return Status.FALLTHROUGH; @@ -345,8 +343,11 @@ public class Evaluator { block = block.next()[0]; assert block != null; for (; i < block.nodes().length; i++) { - if (!(block.nodes()[i] instanceof PhiNode)) break; - phiCache.add(val(block.nodes()[i].in(exit))); + if (!(block.nodes()[i] instanceof PhiNode phi)) break; + var val = region instanceof FunNode fun && fun._name.equals("main") && ((ParmNode)phi)._idx==2 && exit==1 + ? parameter + : val(phi.in(exit)); + phiCache.add(val); } for (i=0; i<phiCache.size(); i++) { values[block.nodes()[i]._nid] = phiCache.get(i); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 8b13f12f..3cf63e0f 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -87,6 +87,9 @@ public class Scheduler { this.entry = entry; this.prev = prev; } + BasicBlock(Node entry, BasicBlock prev) { + this(entry,prev.depth+1,prev); + } } @@ -358,25 +361,28 @@ public class Scheduler { var queue = new Stack<NodeData>(); var phiQueue = new Stack<NodeData>(); queue.push(d(start)); - int depth = 0; while (!queue.isEmpty()) { var data = queue.pop(); var node = data.node; assert node instanceof CFGNode; BasicBlock block = switch (node) { - case StartNode s -> new BasicBlock(s, depth++); - case LoopNode l -> new BasicBlock(l, depth++, d(l.in(1)).block); + case StartNode s -> new BasicBlock(s, 0); + case LoopNode l -> new BasicBlock(l, d(l.in(1)).block); case RegionNode r -> { var prev = new ArrayList<BasicBlock>(); + int depth = 0; for(int i=1; i<r.nIns(); i++) { - od(r.in(i)).ifPresent(d->prev.add(d.block)); + if( !od(r.in(i)).isPresent() ) continue; + BasicBlock bb = d(r.in(i)).block; + prev.add(bb); + depth = Math.max(depth,bb.depth); } - yield new BasicBlock(r, depth++, prev.toArray(BasicBlock[]::new)); + yield new BasicBlock(r, depth+1, prev.toArray(BasicBlock[]::new)); } case IfNode i -> d(i.in(0)).block; case ReturnNode ret -> d(ret .in(0)).block; - case StopNode stop -> d(stop.in(0)).block; - default -> new BasicBlock(node, depth++, d(node.in(0)).block); + case CallNode call -> throw Utils.TODO(); + default -> new BasicBlock(node, d(node.in(0)).block); }; data.block = block; if (node instanceof RegionNode r) { @@ -392,10 +398,17 @@ public class Scheduler { } } } - if( !(node instanceof ReturnNode) && !(node instanceof StopNode) ) + if( node instanceof FunNode fun ) { + // Cannot find CFG user from fun via a naive search, because always find + // Return but Return is not always the one CFG user. + CFGNode n = fun.uctrl(); + assert isCFGNodeReady(n) && d(n).block==null; + queue.push(d(n)); + } else if( !(node instanceof ReturnNode) ) { for (Node n : node._outputs) if(n instanceof CFGNode && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + } var b = block; for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b)); } @@ -440,7 +453,7 @@ public class Scheduler { var data = cfgQueue.pop(); node = data.node; assert node instanceof CFGNode; - if (!(node instanceof ReturnNode) && !(node instanceof StopNode) ) { + if (!(node instanceof ReturnNode) ) { for (var out : node._outputs) if (out!=null && out instanceof CFGNode && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } for (var in : node._inputs) if(in!=null && !(in instanceof CFGNode) && isNotXCtrl(in)) markAlive(dataQueue, in, false); @@ -492,16 +505,16 @@ public class Scheduler { * @param node The node * @return THe CFG output of the node. */ - private static Node findSingleCFGOut(Node node) { + private static CFGNode findSingleCFGOut(Node node) { if (node instanceof StartNode) { - for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p; + for(var n:node._outputs) + if (n instanceof FunNode fun && fun._name.equals("main")) + return fun; return null; } - // From start, a Call, or one of many functions - if( node instanceof CProjNode c && c.in(0) instanceof StartNode ) - return c.out(0); + if( node instanceof FunNode fun ) return fun.uctrl(); assert node._outputs.stream().filter(x -> x instanceof CFGNode).limit(2).count()<=1; - for(var n:node._outputs) if(n instanceof CFGNode) return n; + for(var n:node._outputs) if(n instanceof CFGNode cfg) return cfg; return null; } @@ -544,7 +557,6 @@ public class Scheduler { break; } if (last instanceof ReturnNode) break; - if( last instanceof StopNode ) break; if (last instanceof IfNode if_) { for(var out:if_._outputs) if (out instanceof CFGNode && blocks.get(out) == null) queue.push(d(out)); break; @@ -557,7 +569,6 @@ public class Scheduler { case IfNode i -> new Block(arr, i, -1, new Block[2]); case RegionNode r -> new Block(arr, r, r._inputs.find(prev), new Block[1]); case ReturnNode r -> new Block(arr, r , -1, new Block[0]); - case StopNode stop-> new Block(arr, stop, -1, new Block[0]); default -> throw new AssertionError("Unexpected block exit node"); }); } @@ -572,7 +583,7 @@ public class Scheduler { block.next[0] = blocks.get(r); break; default: - assert block.exit instanceof ReturnNode || block.exit instanceof StopNode; + assert block.exit instanceof ReturnNode; } } // And return the block for the start node. diff --git a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index 1efe270c..81977522 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.CodeGen; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import java.io.OutputStream; @@ -129,7 +128,10 @@ class FuzzerUtils { var code = new CodeGen(script); Node._disablePeephole = !runPeeps; code.parse(); - return runPeeps ? code.opto().typeCheck().codegen()._stop : code._stop; + if( runPeeps ) code.opto(); + code.typeCheck(); + if( runPeeps ) code.GCM(); // Fixup infinite loops + return code._stop; } finally { NodeWalkVisit.clear(); System.setErr(err); |