From e0992778a94ae7f5a8a56201a7ceba0a14ec1300 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 29 Dec 2024 09:29:07 -0800 Subject: Parallel assign Phis --- .../java/com/seaofnodes/simple/Chapter18Test.java | 20 +++ .../src/test/java/com/seaofnodes/simple/Eval2.java | 153 ++++++++++++--------- 2 files changed, 106 insertions(+), 67 deletions(-) (limited to 'chapter18/src/test/java/com') diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 15baccf7..c127d1cb 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -18,6 +18,26 @@ return 0; assertEquals("0", Eval2.eval(code, 0)); } + @Test + public void testPhiParalleAssign() { + CodeGen code = new CodeGen(""" +int a = 1; +int b = 2; +while(arg--) { + int t = a; + a = b; + b = t; +} +return a; +"""); + code.parse().opto().typeCheck().GCM(); + assertEquals("return Phi(Loop,1,Phi(Loop,2,Phi_a));", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("2", Eval2.eval(code, 1)); + assertEquals("1", Eval2.eval(code, 2)); + assertEquals("2", Eval2.eval(code, 3)); + } + // --------------------------------------------------------------- @Test diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java index 50b26464..f7f58f32 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java @@ -27,6 +27,9 @@ public abstract class Eval2 { // Start at the START CFGNode C = code._start, prior = null; + // Phi cache; size is limited to number of Phis at a merge point + Object[] phiCache = new Object[256]; + // Evaluate until we return or timeout. Each outer loop step computes // all data nodes under some new Control. SB sb = null; //new SB(); // TRACE @@ -38,8 +41,19 @@ public abstract class Eval2 { // 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); + + // Parallel assign Phis. First parallel read and cache + int i; + for( i = 0; i < C.nOuts(); i++ ) + if( C.out(i) instanceof PhiNode phi ) + phiCache[i] = isArg(phi) ? arg : val(phi.in(path)); + else break; + // Parallel assign; might assign before read, so read from cache + for( int j=0; j < i; j++ ) + DATA[C.out(j)._nid] = phiCache[j]; + // Now compute the rest of the nodes + for( ; i < C.nOuts(); i++ ) + step(C.out(i), sb, visit); // Find the next control target prior = C; @@ -58,74 +72,18 @@ public abstract class Eval2 { } - 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 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(); - } - }; + private static boolean isArg( PhiNode phi ) { + // Arg#2 into main. + // TODO: Needs some love for recursive main + return phi instanceof ParmNode parm && parm.fun()._sig==TypeFunPtr.MAIN && parm._idx==2; } // 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) { + private static void step(Node n, SB sb, IdentityHashMap visit) { // Only data nodes if( n instanceof CFGNode ) return; // Compute new value - DATA[n._nid] = compute(n,path,arg); + DATA[n._nid] = compute(n); // Trace if( sb!=null ) { IRPrinter.printLine(n,sb).unchar(); @@ -137,11 +95,11 @@ public abstract class Eval2 { // 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); + step(use,sb,visit); } // From here down shamelessly copied from Evaluator, written by @Xmilia - private static Object compute( Node n, int path, long arg ) { + private static Object compute( Node n ) { 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)); @@ -158,7 +116,6 @@ public abstract class Eval2 { 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)); @@ -179,6 +136,15 @@ public abstract class Eval2 { 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]; } + // Java box ints and floats. Other things can just be null or some informative string + 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; + } // Convert array size to array element count private static int offToIdx( long off, TypeStruct t) { @@ -241,4 +207,57 @@ public abstract class Eval2 { return "$mem"; } + + // 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 sb.p("$mem"); + case TypeTuple tt -> { + if( tt._types.length>1 && tt._types[1] instanceof TypeMemPtr ) + // Assume a NewNode + yield _print( tt._types[1], x, sb, visit ); + throw Utils.TODO(); + } + case Type tt -> { + if( tt == Type.NIL ) yield sb.p("null"); + throw Utils.TODO(); + } + }; + } } -- cgit v1.2.3