Compile pipeline deals with functions

Pretty-print functions.
GCM deals with functions.
Tighten linker API.
CallEnd asserts harder proper graph.
Eval2 makes (non recursive) function calls
Peeps infer sharper function return sigs.

19 files changed, 290 insertions, 131 deletions

diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
index 51a6e78e..9588fb01 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java
@@ -20,8 +20,10 @@ public class CodeGen {
     public  StopNode _stop ;
 
 
-    // "Linker" mapping from constant TypeFunPtrs to heads of function
-    public final HashMap<TypeFunPtr,FunNode> _linker = new HashMap<>();
+    // "Linker" mapping from constant TypeFunPtrs to heads of function.  These
+    // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so
+    // the return is not part of the match).
+    private final HashMap<TypeFunPtr,FunNode> _linker = new HashMap<>();
 
 
     // Last created CodeGen as a global, for easier debugging prints
@@ -87,13 +89,23 @@ public class CodeGen {
         return this;
     }
 
-     public CodeGen localSched() {
+    // Local (basic block) scheduler phase, a classic list scheduler
+    public CodeGen localSched() {
         assert _phase == Phase.Schedule;
         _phase = Phase.LocalSched;
         ListScheduler.sched(this);
         return this;
      }
 
+    // Reverse from a constant function pointer to the IR function being called
+    public FunNode link( TypeFunPtr tfp ) {
+        assert tfp.isConstant();
+        return _linker.get(tfp.makeFrom(Type.BOTTOM));
+    }
+
+    public void link(FunNode fun) {
+        _linker.put(fun.sig().makeFrom(Type.BOTTOM),fun);
+    }
 
     // Testing shortcuts
     Node ctrl() { return _stop.ret().ctrl(); }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index f1593a81..bacbd538 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -24,7 +24,7 @@ public abstract class GlobalCodeMotion {
     private static void schedEarly(StartNode start) {
         ArrayList<CFGNode> rpo = new ArrayList<>();
         BitSet visit = new BitSet();
-        _rpo_cfg(start, visit, rpo);
+        _rpo_cfg(null, start, visit, rpo);
         // Reverse Post-Order on CFG
         for( int j=rpo.size()-1; j>=0; j-- ) {
             CFGNode cfg = rpo.get(j);
@@ -39,12 +39,14 @@ public abstract class GlobalCodeMotion {
     }
 
     // Post-Order of CFG
-    private static void _rpo_cfg(Node n, BitSet visit, ArrayList<CFGNode> rpo) {
-        if( !(n instanceof CFGNode cfg) || visit.get(cfg._nid) )
+    private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, ArrayList<CFGNode> rpo) {
+        if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) )
             return;             // Been there, done that
+        if( def instanceof CallNode && cfg instanceof FunNode )
+            return;           // Ignore linked function calls
         visit.set(cfg._nid);
-        for( Node use : cfg._outputs )
-            _rpo_cfg(use,visit,rpo);
+        for( Node useuse : cfg._outputs )
+            _rpo_cfg(cfg,useuse,visit,rpo);
         rpo.add(cfg);
     }
 
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
index adf67d8b..870a890b 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/IRPrinter.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.TypeFunPtr;
 import java.util.ArrayList;
 import java.util.BitSet;
 import java.util.HashMap;
@@ -31,13 +32,6 @@ public class IRPrinter {
         return sb.p("\n");
     }
 
-    private static SB nodeId(SB sb, Node n) {
-        sb.p("%%%d".formatted(n._nid));
-        if (n instanceof ProjNode proj) {
-            sb.p(".").p(proj._idx);
-        }
-        return sb;
-    }
 
     public static String prettyPrint(Node node, int depth) {
         return CodeGen.CODE._phase.ordinal() > CodeGen.Phase.Schedule.ordinal()
@@ -61,14 +55,24 @@ public class IRPrinter {
             Node n = rpos.get(i);
             if( n instanceof CFGNode || n.isMultiHead() ) {
                 if( !gap ) sb.p("\n"); // Blank before multihead
+                if( n instanceof FunNode fun ) {
+                    TypeFunPtr sig = fun.sig();
+                    sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).p("----------------------\n");
+                }
                 printLine( n, sb );         // Print head
                 while( --i >= 0 ) {
                     Node t = rpos.get(i);
                     if( !t.isMultiTail() ) { i++; break; }
                     printLine( t, sb );
                 }
-                sb.p("\n"); // Blank after multitail
-                gap = true;
+                if( n instanceof ReturnNode ret ) {
+                    TypeFunPtr sig = ret.fun().sig();
+                    sig.print(sb.p("--- ").p(sig._name==null ? "" : sig._name).p(" "),false).p("----------------------\n");
+                }
+                if( !(n instanceof CallNode) ) {
+                    sb.p("\n"); // Blank after multitail
+                    gap = true;
+                }
             } else {
                 printLine( n, sb );
                 gap = false;
@@ -87,15 +91,20 @@ public class IRPrinter {
         // First walk the CFG, then everything
         if( n instanceof CFGNode ) {
             for( Node use : n._outputs )
-                if( use instanceof CFGNode && use.nOuts() >= 1 &&
-                    !(use._outputs.get( 0 ) instanceof LoopNode) )
+                // Follow CFG, not across call/function borders, and not around backedges
+                if( use instanceof CFGNode && !(n instanceof CallNode && use instanceof FunNode) &&
+                    use.nOuts() >= 1 &&  !(use._outputs.get(0) instanceof LoopNode) )
                     postOrd(use, n, rpos,visit,bfs);
             for( Node use : n._outputs )
-                if( use instanceof CFGNode )
+                // Follow CFG, not across call/function borders
+                if( use instanceof CFGNode && !(n instanceof CallNode && use instanceof FunNode) )
                     postOrd(use,n,rpos,visit,bfs);
         }
+        // Follow all outputs
         for( Node use : n._outputs )
-            if( use != null )
+            if( use != null &&
+                !(n instanceof CallNode && use instanceof FunNode) &&
+                (n instanceof FunNode || !(use instanceof ParmNode)) )
                 postOrd(use, n, rpos,visit,bfs);
         // Post-order
         rpos.add(n);
@@ -247,7 +256,9 @@ public class IRPrinter {
                 !(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) )
+                !(node instanceof FunNode && def instanceof CallNode) &&
+                !(node instanceof ParmNode && !(def instanceof FunNode))
+            )
                 _walk(ds,ns,def,d-1);
     }
 
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
index 79d5ce4a..49667ecc 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java
@@ -150,32 +150,15 @@ 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, 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());
+
+        ctrl(XCTRL);
+        _scope.mem(new ScopeMinNode(false));
 
         // Parse whole program, as-if function header "{ int arg -> body }"
-        ReturnNode ret = parseFunctionBody("main",TypeFunPtr.MAIN,"arg");
-        CodeGen.CODE._linker.put(TypeFunPtr.MAIN,ret.fun());
-        //main.peephole();
-        //if( cend.peephole() != null )
-        //    IterPeeps.addAll(cend._outputs);
+        ReturnNode ret = parseFunctionBody(TypeFunPtr.MAIN,"arg");
 
         if( !_lexer.isEOF() ) throw _errorSyntax("unexpected");
 
@@ -194,9 +177,12 @@ public class Parser {
     /**
      *  Parses a function body, assuming the header is parsed.
      */
-    private ReturnNode parseFunctionBody(String name, TypeFunPtr sig, String... ids) {
-        sig.setName(name);
-        FunNode fun = _fun = (FunNode)peep(new FunNode(START,sig,name));
+    private ReturnNode parseFunctionBody(TypeFunPtr sig, String... ids) {
+        Node oldctrl = ctrl().keep();
+        Node oldmem  = _scope.mem().keep();
+        FunNode oldfun  = _fun;
+
+        FunNode fun = _fun = (FunNode)peep(new FunNode(START,sig));
 
         // Build a multi-exit return point for all function returns
         RegionNode r = new RegionNode(null,null);
@@ -232,11 +218,7 @@ public class Parser {
 
         // Last expression is the return
         if( ctrl()._type==Type.CONTROL )
-            STOP.addReturn(ctrl(), _scope.mem().merge(), last, fun);
-
-        // Function scope ends
-        _scope.pop();
-        _fun = null;
+            fun.addReturn(ctrl(), _scope.mem().merge(), last);
 
         // Pop off the inProgress node on the multi-exit Region merge
         assert r.inProgress();
@@ -249,7 +231,23 @@ public class Parser {
         ret.setDef(1,rmem.peephole());
         ret.setDef(2,rrez.peephole());
         ret.setDef(0,r.peephole());
-        return (ReturnNode)ret.peephole();
+        ret = (ReturnNode)ret.peephole();
+
+        // Function scope ends
+        _scope.pop();
+        _fun = oldfun;
+        // Reset control and memory to pre-function parsing days
+        ctrl(oldctrl.unkeep());
+        _scope.mem(oldmem.unkeep());
+
+        // Once function body is complete, install in linker table.  Linker
+        // matches on declared args and exact fidx, and ignores the return
+        // (because the fidx will only match the exact single function).  The
+        // normal TFP interning ALSO matches on return, so wipe out the return
+        // for this arg+fidx only match.
+        CodeGen.CODE.link(fun);
+
+        return ret;
     }
 
     /**
@@ -582,7 +580,7 @@ public class Parser {
         var expr = require(parseAsgn(), ";");
         // Need default memory, since it can be lazy, need to force
         // a non-lazy Phi
-        STOP.addReturn(ctrl(), _scope.mem().merge(), expr, _fun);
+        _fun.addReturn(ctrl(), _scope.mem().merge(), expr);
         ctrl(XCTRL);            // Kill control
         return expr;
     }
@@ -694,6 +692,8 @@ public class Parser {
                     throw error("a not-null/non-zero expression");
                 t = expr._type.glb();
             }
+            if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() )
+                tfp.setName(name);
 
         } else {
             if( inferType && !_scope.inCon() )
@@ -1039,7 +1039,7 @@ public class Parser {
         if( matchx("null" ) ) return NIL;
         if( match ("("    ) ) return require(parseAsgn(), ")");
         if( matchx("new"  ) ) return alloc();
-        if( match ("{"    ) ) return func();
+        if( match ("{"    ) ) return require(func(),"}");
         // Expect an identifier now
         ScopeMinNode.Var n = requireLookupId("an identifier or expression");
         Node rvalue = _scope.in(n);
@@ -1191,25 +1191,17 @@ public class Parser {
      *     expr ('.' IDENTIFIER)* [ = expr ]
      *     expr #
      *     expr ('[' expr ']')* = [ = expr ]
+     *     expr '(' [args,]* ')'
      * </pre>
      */
     private Node parsePostfix(Node expr) {
-        String name = null;
+        String name;
         if( match(".") )      name = requireId();
         else if( match("#") ) name = "#";
         else if( match("[") ) name = "[]";
+        else if( match("(") ) return require(functionCall(expr),")");
         else return expr;       // No postfix
 
-        // Happens when parsing known dead code, which often has other typing
-        // issues.  Since the code is dead, possibly due to inlining, lets not
-        // spoil the user experience with error messages.
-        //if( ctrl()._type==Type.XCONTROL ) {
-        //    if( expr.isUnused() ) expr.kill(); // Losing last use of expr
-        //    // Exit out via parsing the trailing expression
-        //    return matchOpx( '=', '=' ) ? parseAsgn() : parsePostfix( con( Type.TOP ) );
-        //}
-
-        //
         if( expr._type==Type.NIL )
             throw error("Accessing unknown field '" + name + "' from 'null'");
 
@@ -1298,7 +1290,7 @@ public class Parser {
     }
 
     /**
-     * Parse a function; the leading '{' is already parsed.
+     * Parse a function body; the caller will parse the surrounding "{}"
      *
      * <pre>
      *     { [type arg,]* -> expr }
@@ -1306,7 +1298,6 @@ public class Parser {
      * </pre>
      */
     private Node func() {
-        int old = pos();        // Record lexer position
         Ary<Type> ts = new Ary<>(Type.class);
         Ary<String> ids = new Ary<>(String.class);
         while( true ) {
@@ -1320,7 +1311,53 @@ public class Parser {
         require("->");
         // Make a concrete function type, with a fidx
         TypeFunPtr tfp = TypeFunPtr.makeFun(TypeTuple.make(ts.asAry()),Type.BOTTOM);
-        return parseFunctionBody(null,tfp,ids.asAry());
+        ReturnNode ret = parseFunctionBody(tfp,ids.asAry());
+        return con(ret._fun.sig());
+    }
+
+    /**
+     *  Parse function call arguments; caller will parse the surrounding "()"
+     * <pre>
+     *   ( arg* )
+     * </pre>
+     */
+    private Node functionCall(Node expr) {
+        if( expr._type == Type.NIL )
+            throw error("Calling a null function pointer");
+        if( !(expr._type instanceof TypeFunPtr tfp) )
+            throw error("Expected a function but got "+expr._type.str());
+        expr.keep();            // Keep while parsing args
+
+        Ary<Node> args = new Ary<Node>(Node.class);
+        args.push(null);        // Space for ctrl,mem
+        args.push(null);
+        while( !peek(')') ) {
+            Node arg = parseAsgn();
+            if( arg==null ) break;
+            args.push(arg.keep());
+            if( !match(",") ) break;
+        }
+        // Control & memory after parsing args
+        args.set(0,ctrl().keep());
+        args.set(1,_scope.mem().merge().keep());
+        args.push(expr);        // Function pointer
+        // Unkeep them all
+        for( Node arg : args )
+            arg.unkeep();
+        // Into the call
+        CallNode call = (CallNode)new CallNode(args.asAry()).peephole();
+
+        // Post-call setup
+        CallEndNode cend = (CallEndNode)new CallEndNode(call).peephole();
+        // Control from CallEnd
+        ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole());
+        // Memory from CallEnd
+        ScopeMinNode mem = new ScopeMinNode(true);
+        mem.addDef(null);       // Alias#0
+        mem.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole());
+        _scope.mem(mem);
+        // Call result
+        return new ProjNode(cend,2,null).peephole();
     }
 
     /**
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 78071920..a3bb1ae9 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -95,22 +95,23 @@ public abstract class CFGNode extends Node {
         _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this);
         _bltWalk(2,null,stop, new BitSet());
     }
-    private int _bltWalk(int pre, FunNode fun, StopNode stop, BitSet post) {
+    int _bltWalk( int pre, FunNode fun, StopNode stop, BitSet post ) {
         // Pre-walked?
         if( _pre!=0 ) return pre;
         _pre = pre++;
         // Pre-walk
         for( Node use : _outputs )
-            if( use instanceof CFGNode usecfg && !(usecfg instanceof XCtrlNode) )
+            if( use instanceof CFGNode usecfg && !skip(usecfg) )
                 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;
-            if( usecfg._type == Type.XCONTROL ) continue; // Dead, only possible if peeps disabled
-            if( usecfg._type == TypeTuple.IF_NEITHER ) continue; // Dead again
+            if( skip(usecfg) ) continue;
+            if( usecfg._type == Type.XCONTROL ||       // Do not walk dead control
+                usecfg._type == TypeTuple.IF_NEITHER ) // Nor dead IFs
+                continue;
             // Child visited but not post-visited?
             if( !post.get(usecfg._nid) ) {
                 // Must be a backedge to a LoopNode then
@@ -143,4 +144,11 @@ public abstract class CFGNode extends Node {
         post.set(_nid);
         return pre;
     }
+
+    boolean skip(CFGNode usecfg) {
+        // Only walk control users that are alive.
+        // Do not walk from a Call to linked Fun's.
+        return usecfg instanceof XCtrlNode || (this instanceof CallNode && usecfg instanceof FunNode);
+    }
+
 }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 31c245f9..578d7f87 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -3,8 +3,7 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.Utils;
-import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeFunPtr;
+import com.seaofnodes.simple.type.*;
 import java.util.BitSet;
 
 /**
@@ -19,6 +18,7 @@ public class CallEndNode extends CFGNode implements MultiNode {
 
     @Override
     public String label() { return "CallEnd"; }
+    @Override public boolean isMultiHead() { return true; }
     @Override public boolean blockHead() { return true; }
 
     CallNode call() { return (CallNode)in(0); }
@@ -36,10 +36,8 @@ public class CallEndNode extends CFGNode implements MultiNode {
 
     @Override
     public Type compute() {
-        for( Node n : _inputs )
-            if( n!=null && n._type==Type.CONTROL )
-                return Type.CONTROL;
-        return Type.XCONTROL;
+        Type ret = call().fptr()._type instanceof TypeFunPtr tfp ? tfp.ret() : Type.BOTTOM;
+        return TypeTuple.make(call()._type,TypeMem.BOT,ret);
     }
 
     @Override
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 3ec1cd0c..b836188c 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java
@@ -21,7 +21,7 @@ public class CallNode extends CFGNode {
         String fname = null;
         Node fptr = fptr();
         if( fptr._type instanceof TypeFunPtr tfp && tfp.isConstant() )
-            fname = CodeGen.CODE._linker.get(tfp)._name;
+            fname = tfp._name;
         if( fname==null ) fptr._print0(sb,visited);
         else sb.append(fname);
         sb.append("( ");
@@ -36,14 +36,32 @@ public class CallNode extends CFGNode {
     // Args mapped 1-to-1 on inputs
     Node arg(int idx) { return in(idx); }
     // args from input 2 to last
-    Node fptr() { return _inputs.last(); }
+    public Node fptr() { return _inputs.last(); }
 
     // Find the Call End from the Call
-    CallEndNode cend() {
+    public CallEndNode cend() {
         // Always in use slot 0
-        return (CallEndNode)out(0);
+        if( nOuts()>0 && out(0) instanceof CallEndNode cend ) {
+            assert _cend()==cend;
+            return cend;
+        } else {
+            assert _cend()==null;
+            return null;
+        }
+    }
+    private CallEndNode _cend() {
+        CallEndNode cend=null;
+        for( Node n : _outputs )
+            if( n instanceof CallEndNode cend0 )
+                { assert cend == null; cend = cend0; }
+        return cend;
     }
 
+    // Get the one control following; error to call with more than one e.g. an
+    // IfNode or other multi-way branch.
+    @Override public CFGNode uctrl() { return cend(); }
+
+
     @Override
     public Type compute() {
         return ctrl()._type;
@@ -51,6 +69,9 @@ public class CallNode extends CFGNode {
 
     @Override
     public Node idealize() {
+        CallEndNode cend = cend();
+        if( cend==null ) return null; // Still building
+
         // Link: call calls target function.  Linking makes the target FunNode
         // point to this Call, and all his Parms point to the call arguments;
         // also the CallEnd points to the Return.
@@ -58,11 +79,12 @@ public class CallNode extends CFGNode {
             // If fidxs is negative, then infinite unknown functions
             long fidxs = tfp.fidxs();
             if( fidxs > 0 ) {
+                // Wipe out the return which matching in the linker table
                 // Walk the (63 max) bits and link
                 for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) {
                     int fidx = Long.numberOfTrailingZeros(fidxs);
                     TypeFunPtr tfp0 = tfp.makeFrom(fidx);
-                    FunNode fun = CodeGen.CODE._linker.get(tfp0);
+                    FunNode fun = CodeGen.CODE.link(tfp0);
                     if( fun!=null && !fun._folding && !linked(fun) )
                         link(fun);
                 }
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 94d7eff7..c6d318bd 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeFunPtr;
 
@@ -9,14 +10,13 @@ public class FunNode extends RegionNode {
     // When set true, this Call/CallEnd/Fun/Return is being trivially inlined
     boolean _folding;
 
-    public final TypeFunPtr _sig; // Initial signature
-    public String _name;        // Debug label, optional
-    private ReturnNode _ret;     // Return pointer
+    private TypeFunPtr _sig;    // Initial signature
+    private ReturnNode _ret;    // Return pointer
 
-    public FunNode( StartNode start, TypeFunPtr sig, String name ) { super(null,start); _sig=sig; _name=name; }
+    public FunNode( StartNode start, TypeFunPtr sig ) { super(null,start); _sig=sig; }
 
     @Override
-    public String label() { return _name; }
+    public String label() { return _sig._name; }
 
     // Find the one CFG user from Fun.  It's not always the Return, but always
     // the Return *is* a CFG user of Fun.
@@ -28,9 +28,20 @@ public class FunNode extends RegionNode {
         return null;
     }
 
+    // Cannot create the Return and Fun at the same time; one has to be first.
+    // So setting the return requires a second step.
     public void setRet(ReturnNode ret) { _ret=ret; }
     ReturnNode ret() { assert _ret!=null; return _ret; }
 
+    // Signature can improve over time
+    public TypeFunPtr sig() { return _sig; }
+    void setSig( TypeFunPtr sig ) {
+        assert sig.isa(_sig);
+        if( _sig != sig )
+            IterPeeps.add(this);
+        _sig = sig;
+    }
+
     @Override
     public Type compute() {
         // Only dead if no callers after SCCP
@@ -58,4 +69,7 @@ public class FunNode extends RegionNode {
     public boolean unknownCallers() { return in(1) instanceof StartNode; }
 
     @Override public boolean inProgress() { return unknownCallers(); }
+
+    // Add a new function exit point.
+    public void addReturn(Node ctrl, Node mem, Node rez) {  _ret.addReturn(ctrl,mem,rez);  }
 }
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 f139e4ca..784b9146 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ParmNode.java
@@ -22,9 +22,9 @@ public class ParmNode extends PhiNode {
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        if( fun()._name.equals("main") && _label.equals("arg") )
+        if( "main".equals(fun().sig()._name) && _label.equals("arg") )
             return sb.append("arg");
-        sb.append(_label).append("(");
+        sb.append("Parm_").append(_label).append("(");
         for( Node in : _inputs ) {
             if (in == null) sb.append("____");
             else in._print0(sb, visited);
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 9519f5ec..ea211dd2 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -24,7 +24,12 @@ public class ProjNode extends Node implements MultiUse {
     @Override public int idx() { return _idx; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); }
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        if( _label != null )  return sb.append(_label);
+        if( in(0) instanceof CallEndNode cend && cend.call()!=null )
+            return cend.call()._print0(sb,visited);
+        return sb.append("LONELY PROJ");
+    }
 
     @Override public CFGNode cfg0() {
         return in(0) instanceof CFGNode cfg ? cfg : in(0).cfg0();
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 5232cfbb..adff7a89 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -38,6 +38,9 @@ public class ReturnNode extends CFGNode {
         return sb.append(";");
     }
 
+    // No one unique control follows; can be many call end sites
+    @Override public CFGNode uctrl() { return null; }
+
     @Override
     public Type compute() {
         if( inProgress() ) return TypeTuple.RET; // In progress
@@ -46,6 +49,14 @@ public class ReturnNode extends CFGNode {
 
     @Override public Node idealize() {
         if( inProgress() ) return null;
+
+        // Upgrade signature based on return type
+        Type ret = expr()._type;
+        TypeFunPtr fcn = _fun.sig();
+        assert ret.isa(fcn.ret());
+        if( ret != fcn.ret() )
+            _fun.setSig(fcn.makeFrom(ret));
+
         // If dead (cant be reached; infinite loop), kill the exit values
         if( ctrl()._type==Type.XCONTROL &&
             !(mem() instanceof ConstantNode && expr() instanceof ConstantNode) ) {
@@ -54,6 +65,7 @@ public class ReturnNode extends CFGNode {
             setDef(2,top);
             return this;
         }
+
         return null;
     }
 
@@ -104,8 +116,7 @@ public class ReturnNode extends CFGNode {
         SB sb = new SB().p("No common type amongst ");
         if( ti ) sb.p("int and ");
         if( tf ) sb.p("f64 and ");
-        if( tp ) sb.p("reference and ");
-        if( !tp && tn ) sb.p("nil and ");
+        if( tp || tn ) sb.p("reference and ");
         return sb.unchar(5).toString();
     }
 }
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 ebf650fc..8482b003 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java
@@ -53,7 +53,7 @@ public class ScopeMinNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        sb.append("MEM[ ");
+        sb.append(_inProgress ? "Merge[" : "MEM[ ");
         for( int j=2; j<nIns(); j++ ) {
             sb.append(j);
             sb.append(":");
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 008a910f..8210a484 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -37,7 +37,7 @@ public class StartNode extends LoopNode implements MultiNode {
         // Find "main", its the start.
         CFGNode C = null;
         for( Node use : _outputs )
-            if( use instanceof FunNode fun && fun._sig==TypeFunPtr.MAIN )
+            if( use instanceof FunNode fun && fun.sig().isa(TypeFunPtr.MAIN) )
                 { assert C==null; C = fun; }
         return C;
     }
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 fb78f720..009296e8 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -60,12 +60,4 @@ public class StopNode extends CFGNode {
             d = Math.max(d,((ReturnNode)ret).idepth()+1);
         return _idepth=d;
     }
-
-    // Add a new function exit point.  Validates Parsers function borders, then
-    // hands off to the guaranteed return.
-    public void addReturn(Node ctrl, Node mem, Node rez, FunNode fun) {
-        ReturnNode ret = (ReturnNode)_inputs.last();
-        assert ret.fun()==fun && ret.inProgress();
-        ret.addReturn(ctrl,mem,rez);
-    }
 }
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
index 6acd6798..d5652f12 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
@@ -37,8 +37,9 @@ public class TypeFunPtr extends TypeNil {
 
     static TypeFunPtr make( byte nil, TypeTuple sig, Type ret, long fidxs ) { return new TypeFunPtr(nil,sig,ret,fidxs).intern(); }
     public static TypeFunPtr make( boolean nil, TypeTuple sig, Type ret ) { return make((byte)(nil ? 3 : 2),sig,ret,-1); }
-    @Override TypeFunPtr makeFrom( byte nil ) { return nil==_nil ? this : make(nil,_sig,_ret,_fidxs); }
-    public TypeFunPtr makeFrom( int fidx ) { return make(_nil,_sig,_ret,1L<<fidx); }
+    @Override TypeFunPtr makeFrom( byte nil ) { return  nil ==_nil   ? this : make( nil,_sig,_ret,   _fidxs).setName(_name); }
+    public TypeFunPtr makeFrom( int fidx ) { return 1L<<fidx==_fidxs ? this : make(_nil,_sig,_ret,1L<<fidx ).setName(_name); }
+    public TypeFunPtr makeFrom( Type ret ) { return     ret ==_ret   ? this : make(_nil,_sig, ret,   _fidxs).setName(_name); }
 
     // Compute "function indices": FIDX
     private static final HashMap<TypeTuple,Integer> FIDXS = new HashMap<>();
@@ -56,7 +57,7 @@ public class TypeFunPtr extends TypeNil {
     public static TypeFunPtr BOT   = make((byte)3,TypeTuple.BOT,Type.BOTTOM,-1);
     public static TypeFunPtr TEST  = make((byte)2,TypeTuple.TEST,TypeInteger.BOT,1);
     public static TypeFunPtr TEST0 = make((byte)3,TypeTuple.TEST,TypeInteger.BOT,3);
-    public static TypeFunPtr MAIN  = makeFun(TypeTuple.MAIN,Type.BOTTOM);
+    public static TypeFunPtr MAIN  = makeFun(TypeTuple.MAIN,Type.BOTTOM).setName("main");
     public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(TEST0); ts.add(BOT); ts.add(MAIN); }
 
     @Override
@@ -71,7 +72,7 @@ public class TypeFunPtr extends TypeNil {
     // RHS is NIL
     @Override public Type meet0() { return _nil==3 ? this : make((byte)3,_sig,_ret,_fidxs); }
 
-    @Override public TypeFunPtr glb() { throw Utils.TODO(); }
+    @Override public TypeFunPtr glb() { return make(_nil,_sig,_ret,-1); }
 
     @Override public boolean isConstant() { return _nil==2 && Long.bitCount(_fidxs)==1; }
 
@@ -79,6 +80,7 @@ public class TypeFunPtr extends TypeNil {
 
     public Type arg(int i) { return _sig._types[i]; }
     public long fidxs() { return _fidxs; }
+    public Type ret() { return _ret; }
 
     @Override
     int hash() { return Utils.fold(_sig.hashCode() ^ _ret.hashCode() ^ _fidxs ^ super.hash()); }
@@ -89,19 +91,22 @@ public class TypeFunPtr extends TypeNil {
         return _sig == ptr._sig  && _ret == ptr._ret && _fidxs == ptr._fidxs && super.eq(ptr);
     }
 
-    public void setName(String name) {
+    public TypeFunPtr setName(String name) {
+        if( name==null ) return this;
         assert _name==null || _name.equals(name);
         assert _fidxs > 0 && Long.bitCount(_fidxs) == 1;
         _name = name;
+        return this;
     }
 
     @Override public String str() { return print(new SB()).toString(); }
-    @Override public SB  print(SB sb) { return _print(sb,false); }
-    @Override public SB gprint(SB sb) { return _print(sb,true ); }
+    @Override public SB  print(SB sb) { return _print(sb,false,true); }
+    public SB print(SB sb, boolean n) { return _print(sb,false,n); }
+    @Override public SB gprint(SB sb) { return _print(sb,true ,true); }
     private static SB _print(SB sb, boolean g, Type t) { return g ? t.gprint(sb) : t.print(sb); }
-    private SB _print(SB sb, boolean g) {
+    private SB _print(SB sb, boolean g, boolean n) {
         sb.p(x()).p("{ ");
-        if( _name!=null ) sb.p(_name);
+        if( n && _name!=null ) sb.p(_name);
         else {
             for( Type t : _sig._types )
                 _print(sb,g,t).p(" ");
diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java
index 7063ef26..6fc2cc98 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java
@@ -51,17 +51,29 @@ return x2;
         assertEquals("null", Eval2.eval(code, 0 ) );
     }
 
-    @Ignore @Test
+    @Test
     public void testFcn0() {
         CodeGen code = new CodeGen("""
 {int -> int}? sq = { int x ->
-    x*x
+    x*x;
 };
 return sq;
 """);
         code.parse().opto();
-        assertEquals("return fcn;", code._stop.toString());
-        assertEquals("1", Eval2.eval(code, 0));
+        assertEquals("Stop[ return { sq}; return (Parm_x(sq,int)*x); ]", code._stop.toString());
+        assertEquals("{ sq}", Eval2.eval(code, 3));
     }
 
+    @Test
+    public void testFcn1() {
+        CodeGen code = new CodeGen("""
+var sq = { int x ->
+    x*x;
+};
+return sq(2)+sq(3);
+""");
+        code.parse().opto();
+        assertEquals("Stop[ return (sq( 3)+sq( 2)); return (Parm_x(sq,int,3,2)*x); ]", code._stop.toString());
+        assertEquals("13", 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
index 0e5e86a4..ea69bc52 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/Eval2.java
@@ -4,6 +4,7 @@ import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.node.*;
 
 import java.util.Arrays;
+import java.util.Stack;
 import java.util.IdentityHashMap;
 import java.util.Objects;
 
@@ -30,6 +31,9 @@ public abstract class Eval2 {
         // Phi cache; size is limited to number of Phis at a merge point
         Object[] phiCache = new Object[256];
 
+        Stack<CallEndNode> stack = new Stack<>();
+
+
         // Evaluate until we return or timeout.  Each outer loop step computes
         // all data nodes under some new Control.
         SB sb = null; // new SB(); // TRACE
@@ -68,27 +72,46 @@ public abstract class Eval2 {
             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 CallNode  call :  C = call(code,call,stack); break;
+            case CallEndNode cend: break;
             case CProjNode cproj:  break;
-                // TODO: Need a Call-stack here
-            case ReturnNode ret:   return prettyPrint(ret.expr()._type,val(ret.expr()));
+            case FunNode   fun  :  if( loopCnt++ > timeout ) return null;  break; // Timeout
+            case IfNode    iff  :  Object p = val(iff.pred()); C = iff.cproj( p==null || (p instanceof Long x && x==0L)  ? 1 : 0);  break;
+            case LoopNode  loop :  if( loopCnt++ > timeout ) return null;  break; // Timeout
+            case RegionNode r   :  break;
+            case ReturnNode ret :
+                Node expr = ret.expr();
+                if( stack.isEmpty() )
+                    return prettyPrint(expr._type,val(expr));
+                DATA[ret._nid] = val(expr);
+                C = stack.pop();
+                DATA[C._nid] = DATA[ret._nid];
+                break;
             default:               throw Utils.TODO();
             }
         }
+    }
+
 
+    // Make a call.
+    private static CFGNode call( CodeGen code, CallNode call, Stack<CallEndNode> stack ) {
+        stack.push(call.cend());
+        // TODO: Stack and unstack all DATA boxes readable by recursive functions
+        return code.link(tfp(call.fptr()));
+    }
+
+    private static String exit(ReturnNode ret) {
+        return prettyPrint(ret.expr()._type,val(ret.expr()));
     }
 
     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;
+        return phi instanceof ParmNode parm && parm.fun().sig().isa(TypeFunPtr.MAIN) && parm._idx==2;
     }
 
     // Take a worklist step: one data op from the current Control is updated.
-    private static void step(Node n, SB sb, IdentityHashMap visit) {
+    private static void step(Node n, SB sb, IdentityHashMap<Object,Object> visit) {
         // Only data nodes
         if( n instanceof CFGNode )  return;
         // Compute new value
@@ -150,13 +173,19 @@ 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];  }
+    // Fetch and unbox a TypeFunPtr
+    static TypeFunPtr tfp(Node n) { return (TypeFunPtr)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";
-        //
+        if( t instanceof TypeMemPtr tmp )
+            throw Utils.TODO();
+        if( t instanceof TypeFunPtr tfp )
+            { assert tfp.isConstant(); return tfp; }
+        // Things like Type.NIL, or TypeMem
         return null;
     }
 
@@ -223,8 +252,8 @@ public abstract class Eval2 {
 
 
     // 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 ) {
+    static String prettyPrint( Type t, Object x ) { return _print(t,x,new SB(), new IdentityHashMap<>()).toString(); }
+    static SB _print( Type t, Object x, SB sb, IdentityHashMap<Object,Object> visit ) {
         if( x instanceof String s ) return sb.p(s);
         if( x == null ) return sb.p("null");
         return switch( t ) {
@@ -261,6 +290,7 @@ public abstract class Eval2 {
             }
             yield sb;
         }
+        case TypeFunPtr tfp -> sb.p(x.toString());
         case TypeMem mem -> sb.p("$mem");
         case TypeTuple tt -> {
             if( tt._types.length>1 && tt._types[1] instanceof TypeMemPtr )
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 ff9eb1b1..8e25b133 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -344,7 +344,7 @@ public class Evaluator {
                 assert block != null;
                 for (; i < block.nodes().length; i++) {
                     if (!(block.nodes()[i] instanceof PhiNode phi)) break;
-                    var val = region instanceof FunNode fun && fun._name.equals("main") && ((ParmNode)phi)._idx==2 && exit==1
+                    var val = region instanceof FunNode fun && "main".equals(fun.sig()._name) && ((ParmNode)phi)._idx==2 && exit==1
                             ? parameter
                             : val(phi.in(exit));
                     phiCache.add(val);
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 3cf63e0f..52d8f3e3 100644
--- a/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
+++ b/chapter18/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java
@@ -503,12 +503,12 @@ public class Scheduler {
     /**
      * Find the CFG output of a node
      * @param node The node
-     * @return THe CFG output of the node.
+     * @return The CFG output of the node.
      */
     private static CFGNode findSingleCFGOut(Node node) {
         if (node instanceof StartNode) {
             for(var n:node._outputs)
-                if (n instanceof FunNode fun && fun._name.equals("main"))
+                if (n instanceof FunNode fun && "main".equals(fun.sig()._name) )
                    return fun;
             return null;
         }