From 2c7e86d4350ed115922e80e6bfc1aef30a881f75 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Sat, 28 Oct 2023 16:18:02 -0700
Subject: Parser gather Returns in the Stop

Return returns a tuple of control & result
GraphViz works with multi-Scopes and Scopes do not double-print uid.
Proj also does not print uid in golden test results, because every time we add a new early node, the final results change node id so fail golden test.
---
 .../com/seaofnodes/simple/GraphVisualizer.java     |  2 +-
 .../main/java/com/seaofnodes/simple/Parser.java    | 11 ++-
 .../main/java/com/seaofnodes/simple/node/Node.java |  2 +-
 .../java/com/seaofnodes/simple/node/ProjNode.java  |  2 +-
 .../com/seaofnodes/simple/node/ReturnNode.java     |  5 +-
 .../java/com/seaofnodes/simple/node/ScopeNode.java |  2 +-
 .../java/com/seaofnodes/simple/node/StopNode.java  | 12 ++-
 .../java/com/seaofnodes/simple/type/TypeTuple.java |  2 +-
 .../java/com/seaofnodes/simple/Chapter05Test.java  | 95 ++++++++++++----------
 9 files changed, 78 insertions(+), 55 deletions(-)

(limited to 'chapter05/src')

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index b7e561e1..79d98792 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -122,7 +122,7 @@ public class GraphVisualizer {
         sb.append( "\t}\n".repeat( level ) ); // End all Scope clusters
     }
 
-    private String makeScopeName(ScopeNode sn, int level) { return sn.label() + "_" + level; }
+    private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; }
     private String makePortName(String scopeName, String varName) { return scopeName + "_" + varName; }
 
     // Walk the node edges
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index 4225e67b..3e832610 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -29,6 +29,9 @@ public class Parser {
      */
     public static StartNode START;
 
+    public StopNode STOP;
+
+    // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
     private final Lexer _lexer;
 
     /**
@@ -57,6 +60,7 @@ public class Parser {
         _scope = new ScopeNode();
         START = new StartNode(new Type[]{ Type.CONTROL, arg });
         START.peephole();
+        STOP = new StopNode();
     }
 
     public Parser(String source) {
@@ -69,13 +73,14 @@ public class Parser {
 
     private Node ctrl(Node n) { return _scope.ctrl(n); }
 
-    public ReturnNode parse() {
+    public StopNode parse() {
         _allScopes.push(_scope);
         _scope.push();
         try {
             _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole());
             _scope.define("arg", new ProjNode(START, 1, "arg").peephole());
-            return (ReturnNode) parseBlock();
+            parseBlock();
+            return STOP;
         }
         finally {
             _scope.pop();
@@ -164,7 +169,7 @@ public class Parser {
      */
     private Node parseReturn() {
         var expr = require(parseExpression(), ";");
-        Node ret = new ReturnNode(ctrl(), expr);
+        Node ret = STOP.add_def(new ReturnNode(ctrl(), expr).peephole());
         ctrl(null);             // Kill control
         return ret;
     }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
index 382d41ae..49426c26 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -206,7 +206,7 @@ public abstract class Node {
      * @param new_def the new definition, appended to the end of existing definitions
      * @return new_def for flow coding
      */
-    Node add_def(Node new_def) {
+  public Node add_def(Node new_def) {
         // Add use->def edge
         _inputs.add(new_def);
         // If new def is not null, add the corresponding def->use edge
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index c9b1ec07..8e223e93 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -22,7 +22,7 @@ public class ProjNode extends Node {
     public String label() { return _label; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) { return sb.append(_label).append(_nid); }
+    StringBuilder _print1(StringBuilder sb) { return sb.append(_label); }
 
     @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
 
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 681bd175..e20d01e5 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.*;
 
 /**
  * The Return node has two inputs.  The first input is a control node and the
@@ -33,7 +32,7 @@ public class ReturnNode extends Node {
   
     @Override
     public Type compute() {
-        return expr().compute();
+      return new TypeTuple(TypeControl.CONTROL,expr()._type);
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index f09eeef5..b3cca3da 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -105,7 +105,7 @@ public class ScopeNode extends Node {
     public ScopeNode dup() {
         ScopeNode dup = new ScopeNode();
         for( HashMap<String, Integer> tab : _scopes )
-            dup._scopes.push((HashMap<String, Integer>) tab.clone());
+            dup._scopes.push(new HashMap<String, Integer>(tab));
         for( int i=0; i<nIns(); i++ )
             dup.add_def(in(i));
         return dup;
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
index b0c851a2..df5e09ef 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -15,10 +15,20 @@ public class StopNode extends Node {
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
-        return sb;
+        if( ret()!=null ) return ret()._print0(sb);
+        sb.append("Stop[ ");
+        for( Node ret : _inputs )
+            ret._print0(sb).append(" ");
+        return sb.append("]");
     }
 
     @Override public boolean isCFG() { return true; }
+
+    // If a single Return, return it.
+    // Otherwise, null because ambiguous.
+    public ReturnNode ret() {
+        return nIns()==1 ? (ReturnNode)in(0) : null;
+    }
     
     @Override
     public Type compute() {
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 4d7a79bc..80d09884 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -4,7 +4,7 @@ public class TypeTuple extends Type {
   
     public final Type[] _types;
 
-    public TypeTuple(Type[] _types) {
+    public TypeTuple(Type... _types) {
         this._types = _types;
     }
 
diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 496b3ff5..e59d1dbd 100644
--- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -23,8 +23,8 @@ else {
 return a;
 #showGraph;
 """);
-        ReturnNode ret = parser.parse();
-        assertEquals("return Phi(Region16,(arg4+2),(arg4-3));", ret.toString());
+        StopNode ret = parser.parse();
+        assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString());
     }
   
     @Test
@@ -38,22 +38,29 @@ if (arg == 1) {
 }
 return c;
                 """, TypeInteger.BOT);
-        ReturnNode ret = parser.parse();
-        assertEquals("return Phi(Region15,4,3);", ret.toString());
+        StopNode ret = parser.parse();
+        assertEquals("return Phi(Region16,4,3);", ret.toString());
+    }
+    
+    @Test
+    public void testChapter5Return2() {
+        Parser parser = new Parser("if( arg==1 ) return 3; else return 4; #showGraph;", TypeInteger.BOT);
+        StopNode stop = parser.parse();
+        assertEquals("Stop[ return 3; return 4; ]", stop.toString());
     }
     
     @Test
     public void testChapter5IfMergeB() {
         Parser parser = new Parser("int a=arg+1; int b=0; if( arg==1 ) b=a; else b=a+1; return a+b; #showGraph;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return ((arg4+1)+Phi(Region19,(arg4+1),(arg4+2)));", ret.toString());
+        StopNode ret = parser.parse();
+        assertEquals("return ((arg+1)+Phi(Region20,(arg+1),(arg+2)));", ret.toString());
     }
 
     @Test
     public void testChapter5IfMerge2() {
         Parser parser = new Parser("int a=arg+1; int b=arg+2; if( arg==1 ) b=b+a; else a=b+1; return a+b; #showGraph;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return (Phi(Region30,(arg4+1),(arg4+3))+Phi(Region30,((arg4*2)+3),(arg4+2)));", ret.toString());
+        StopNode ret = parser.parse();
+        assertEquals("return (Phi(Region31,(arg+1),(arg+3))+Phi(Region31,((arg*2)+3),(arg+2)));", ret.toString());
     }
       
     @Test
@@ -79,49 +86,50 @@ return c;
     @Test
     public void testChapter4Peephole() {
         Parser parser = new Parser("return 1+arg+2; #showGraph;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return (arg4+3);", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testChapter4Peephole2() {
         Parser parser = new Parser("return (1+arg)+2;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return (arg4+3);", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testChapter4Add0() {
         Parser parser = new Parser("return 0+arg;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return arg4;", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return arg;", ret.print());
     }
 
     @Test
     public void testChapter4AddAddMul() {
         Parser parser = new Parser("return arg+0+arg;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return (arg4*2);", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return (arg*2);", ret.print());
     }
   
     @Test
     public void testChapter4Peephole3() {
         Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return ((arg4*2)+6);", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return ((arg*2)+6);", ret.print());
     }
 
     @Test
     public void testChapter4Mul1() {
         Parser parser = new Parser("return 1*arg;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return arg4;", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return arg;", ret.print());
     }
   
     @Test
     public void testChapter4VarArg() {
         Parser parser = new Parser("return arg; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode stop = parser.parse();
+        ReturnNode ret = stop.ret();
         assertTrue(ret.in(0) instanceof ProjNode);
         assertTrue(ret.in(1) instanceof ProjNode);
     }
@@ -129,70 +137,70 @@ return c;
     @Test
     public void testChapter4ConstantArg() {
         Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2));
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @Test
     public void testChapter4CompEq() {
         Parser parser = new Parser("return 3==3; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testChapter4CompEq2() {
         Parser parser = new Parser("return 3==4; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testChapter4CompNEq() {
         Parser parser = new Parser("return 3!=3; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 0;", ret.print());
     }
 
     @Test
     public void testChapter4CompNEq2() {
         Parser parser = new Parser("return 3!=4; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testChapter4Bug1() {
         Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return (arg4+3);", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+3);", ret.print());
     }
 
     @Test
     public void testChapter4Bug2() {
         Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;");
-        ReturnNode ret = parser.parse();
-        assertEquals("return (arg4+1);", ret.print());
+        StopNode ret = parser.parse();
+        assertEquals("return (arg+1);", ret.print());
     }
 
     @Test
     public void testVarDecl() {
         Parser parser = new Parser("int a=1; return a;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 1;", ret.print());
     }
 
     @Test
     public void testVarAdd() {
         Parser parser = new Parser("int a=1; int b=2; return a+b;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 3;", ret.print());
     }
 
     @Test
     public void testVarScope() {
         Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 4;", ret.print());
     }
 
@@ -200,7 +208,7 @@ return c;
     public void testVarScopeNoPeephole() {
         Node._disablePeephole = true;
         Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         Node._disablePeephole = false;
         assertEquals("return (1+3);", ret.print());
     }
@@ -208,7 +216,7 @@ return c;
     @Test
     public void testVarDist() {
         Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 8;", ret.print());
     }
 
@@ -226,7 +234,7 @@ return c;
     public void testChapter2ParseGrammar() {
         Node._disablePeephole = true; // disable peephole so we can observe full graph
         Parser parser = new Parser("return 1+2*3+-5;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return (1+((2*3)+(-5)));", ret.print());
         GraphVisualizer gv = new GraphVisualizer();
         System.out.println(gv.generateDotOutput(parser));
@@ -236,42 +244,42 @@ return c;
     @Test
     public void testChapter2AddPeephole() {
         Parser parser = new Parser("return 1+2;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 3;", ret.print());
     }
 
     @Test
     public void testChapter2SubPeephole() {
         Parser parser = new Parser("return 1-2;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return -1;", ret.print());
     }
 
     @Test
     public void testChapter2MulPeephole() {
         Parser parser = new Parser("return 2*3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 6;", ret.print());
     }
 
     @Test
     public void testChapter2DivPeephole() {
         Parser parser = new Parser("return 6/3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
     }
 
     @Test
     public void testChapter2MinusPeephole() {
         Parser parser = new Parser("return 6/-3;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return -2;", ret.print());
     }
 
     @Test
     public void testChapter2Example() {
         Parser parser = new Parser("return 1+2*3+-5;");
-        ReturnNode ret = parser.parse();
+        StopNode ret = parser.parse();
         assertEquals("return 2;", ret.print());
         GraphVisualizer gv = new GraphVisualizer();
         System.out.println(gv.generateDotOutput(parser));
@@ -280,8 +288,9 @@ return c;
     @Test
     public void testSimpleProgram() {
         Parser parser = new Parser("return 1;");
-        ReturnNode ret = parser.parse();
+        StopNode stop = parser.parse();
         StartNode start = Parser.START;
+        ReturnNode ret = (ReturnNode)stop.in(0);
         
         assertTrue(ret.ctrl() instanceof ProjNode);
         Node expr = ret.expr();
-- 
cgit v1.2.3