From b5b972aec72eeafe9e044704b3b6741a7362bb9b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 5 Jan 2025 12:53:52 -0800 Subject: Finalize function semantics Rename ScopeMin to MergeMem. Move Var to its own file. Allow out-of-scope id lookups in functions, as long as its a final constant. This allows e.g. factorial to find "fact" as an out-of-scope final constant function. --- .../java/com/seaofnodes/simple/Chapter18Test.java | 96 ++++++++++++++-------- .../src/test/java/com/seaofnodes/simple/Eval2.java | 41 +++++---- .../com/seaofnodes/simple/evaluator/Evaluator.java | 4 +- 3 files changed, 84 insertions(+), 57 deletions(-) (limited to 'chapter18/src/test/java/com/seaofnodes') diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 39da0c72..75ad301e 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -1,26 +1,27 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; import org.junit.Test; -import org.junit.Ignore; - import static org.junit.Assert.*; +import static org.junit.Assert.fail; +import org.junit.Ignore; public class Chapter18Test { @Test public void testJig() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" return 0; """); - code.parse(true).opto().typeCheck().GCM(); + code.parse(false).opto().typeCheck().GCM(); assertEquals("return 0;", code._stop.toString()); assertEquals("0", Eval2.eval(code, 0)); } @Test public void testPhiParalleAssign() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" int a = 1; int b = 2; while(arg--) { @@ -42,7 +43,8 @@ return a; // --------------------------------------------------------------- @Test public void testType0() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" {int -> int}? x2 = null; // null function ptr return x2; """); @@ -53,7 +55,8 @@ return x2; @Test public void testFcn0() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" {int -> int}? sq = { int x -> x*x; }; @@ -66,7 +69,8 @@ return sq; @Test public void testFcn1() { - CodeGen code = new CodeGen(""" + CodeGen code = new CodeGen( +""" var sq = { int x -> x*x; }; @@ -77,9 +81,48 @@ return sq(arg)+sq(3); assertEquals("13", Eval2.eval(code, 2)); } - // Recursive factorial test + // Function scope test @Test public void testFcn2() { + CodeGen code = new CodeGen( +""" +int cnt=1; +return { -> cnt; }; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Variable 'cnt' is out of function scope and must be a final constant",e.getMessage()); } + } + + // Function scope test + @Test + public void testFcn3() { + CodeGen code = new CodeGen( +""" +val cnt=2; +return { -> cnt; }(); +"""); + code.parse().opto(); + assertEquals("return 2;", code._stop.toString()); + assertEquals("2", Eval2.eval(code, 0)); + } + + // Function variables + @Test + public void testFcn4() { + CodeGen code = new CodeGen( +""" +var fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; +return fcn(3); +"""); + code.parse().opto(); + assertEquals("Stop[ return Phi(Region,{ int -> int #1},{ int -> int #2})( 3); return (Parm_x(null,int)*x); return (Parm_x(null,int)*2); ]", code._stop.toString()); + assertEquals("6", Eval2.eval(code, 0)); + assertEquals("9", Eval2.eval(code, 1)); + } + + // Recursive factorial test + @Test + public void testFcn5() { CodeGen code = new CodeGen("val fact = { int x -> x <= 1 ? 1 : x*fact(x-1); }; return fact(arg);"); code.parse().opto(); assertEquals("Stop[ return fact( arg); return Phi(Region,1,(Parm_x(fact,int,arg,(x-1))*fact( Sub))); ]", code._stop.toString()); @@ -90,34 +133,21 @@ return sq(arg)+sq(3); assertEquals("24", Eval2.eval(code, 4)); } - - + // Mutual recursion. Fails without SCCP to lift the recursive return types. @Ignore @Test - public void testFcn3() { + public void testFcn6() { CodeGen code = new CodeGen( """ -val counter = { -> - int cnt; - val rez = new {int}?[2]; - rez[0] = { -> cnt; }; - rez[1] = { -> ++cnt; }; - return rez; -}; -val A = counter(); -val B = counter(); -int[] rez = new int[5]; -rez[0] = A[0](); // Value of counter A -rez[1] = A[1](); // Increment counter A -rez[2] = B[0](); // Value of counter B -B[1](); // Increment B -B[1](); // Increment B -rez[3] = B[0](); // Value of counter B -rez[4] = A[0]() * 10 + B[0](); -return rez; +val is_even = { int x -> x ? is_odd (x-1) : true ; }; +val is_odd = { int x -> x ? is_even(x-1) : false; }; +return is_even(arg); """); code.parse().opto(); - assertEquals("Stop[ return (const)[int]; return (const)[{ -> int #ALL}?]; return 0; return 1; ]", code._stop.toString()); - assertEquals("13", Eval2.eval(code, 0)); + assertEquals("Stop[ return is_even( arg); return Phi(Region,Phi(Region,is_even( ((Parm_x(is_even,int,arg,Sub)-1)-1)),0),1); ]", code._stop.toString()); + assertEquals("1", Eval2.eval(code, 0)); + assertEquals("0", Eval2.eval(code, 1)); + assertEquals("1", Eval2.eval(code, 2)); + assertEquals("0", Eval2.eval(code, 3)); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java index 757699e4..66b5c28b 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java @@ -132,18 +132,9 @@ public abstract class Eval2 { // Return from main hits Stop F.put(BB,new Closure(code._stop,F)); - // Set incoming arg into main - FunNode main = (FunNode)code._start.uctrl(); - assert main.sig().isa(TypeFunPtr.MAIN); - for( Node use : main._outputs ) - if( use instanceof ParmNode parm && parm._idx==2 ) { - parm.setDef(1,new ConstantNode( TypeInteger.constant( arg ) ).init() ); - F.put( parm.in(1), arg ); - } - // ------------ - // Evaluate until we exit or timeout. Each outer loop step computes + // Evaluate until exit or timeout. Each outer loop step computes // all data nodes under some new Control. while( true ) { traceCtrl(BB,trace); @@ -184,19 +175,26 @@ public abstract class Eval2 { // Compute input path on Phis for this Region int path = r._inputs.find( prior ); + // Parameters read from prior frame, Phis from local frame + Frame frame = (r instanceof FunNode ? F._prior : F); + boolean isMain = r instanceof FunNode fun && fun.sig().isa(TypeFunPtr.MAIN); // Parallel assign Phis. First parallel read and cache int i; - for( i = 0; i < r.nOuts(); i++ ) - if( r.out(i) instanceof PhiNode phi ) - // Parameters read from prior frame, Phis from local frame - PHICACHE[i] = (r instanceof FunNode ? F._prior : F) - .get( (phi instanceof ParmNode parm && parm._idx==0) - // RPC reads the Call directly - ? phi.region().in(path) - // Phis read from path input - : phi.in(path)); - else break; + for( i = 0; i < r.nOuts(); i++ ) { + if( !(r.out(i) instanceof PhiNode phi) ) break; + if( isMain && phi instanceof ParmNode parm && parm._idx==2 ) + PHICACHE[i] = arg; // Reading the initial arguments to main() + else { + Node n = phi instanceof ParmNode parm + // RPC reads the Call directly; + // Parms may not be linked, so read call args directly + ? (parm._idx==0 ? prior : prior.in(parm._idx)) + // Phis read from path input + : phi.in(path); + PHICACHE[i] = frame.get(n); + } + } // Parallel assign; might assign before read, so read from cache for( int j=0; j < i; j++ ) traceData(F.put0(r.out(j),PHICACHE[j]),trace); @@ -204,6 +202,7 @@ public abstract class Eval2 { return i; } + // Make a call. private static CFGNode call( CallNode call ) { // Set up the Return PC and return frame (which is just the current frame). @@ -271,7 +270,7 @@ public abstract class Eval2 { 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 MemMergeNode 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); 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 8e25b133..92b424df 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -4,8 +4,6 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.lang.invoke.MethodHandle; -import java.lang.invoke.MethodHandles; import java.util.*; public class Evaluator { @@ -307,7 +305,7 @@ public class Evaluator { case NewNode alloc -> alloc(alloc); case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; - case ScopeMinNode mem -> null; + case MemMergeNode mem -> null; case ReadOnlyNode ro -> val(ro.in(1)); case CallNode call -> Utils.TODO(); // should not reach here, go the IfNode route default -> throw new AssertionError("Unexpected node " + node); -- cgit v1.2.3