From 7aca34858eb886677bc179658a6fffbb5ae54f66 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Mon, 30 Oct 2023 10:15:49 -0700
Subject: Lots of improvements to graphviz

Merging common edges.
Phis of same Region align.
Phis use greek phi, and have a debug name.  Scope carries the debug name.  Phis are lightly colored.
Common math names for math prims.
Parse can optionally show the graph after closing the last scope.
---
 .../com/seaofnodes/simple/GraphVisualizer.java     | 22 ++++++++++++++++++++--
 .../main/java/com/seaofnodes/simple/Parser.java    |  7 ++++---
 .../java/com/seaofnodes/simple/node/AddNode.java   | 12 ++++++------
 .../java/com/seaofnodes/simple/node/BoolNode.java  |  3 +++
 .../java/com/seaofnodes/simple/node/DivNode.java   | 11 +++++------
 .../java/com/seaofnodes/simple/node/MinusNode.java |  9 ++++-----
 .../java/com/seaofnodes/simple/node/MulNode.java   |  9 ++++-----
 .../java/com/seaofnodes/simple/node/MultiNode.java |  4 +---
 .../main/java/com/seaofnodes/simple/node/Node.java |  5 +++++
 .../java/com/seaofnodes/simple/node/PhiNode.java   | 17 ++++++++---------
 .../com/seaofnodes/simple/node/RegionNode.java     |  8 ++------
 .../java/com/seaofnodes/simple/node/ScopeNode.java | 15 +++++++++------
 .../java/com/seaofnodes/simple/node/SubNode.java   |  9 ++++-----
 .../java/com/seaofnodes/simple/Chapter05Test.java  |  8 ++++----
 14 files changed, 79 insertions(+), 60 deletions(-)

(limited to 'chapter05')

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
index 79d98792..903a0684 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/GraphVisualizer.java
@@ -32,6 +32,10 @@ public class GraphVisualizer {
 
         // Preserve node input order
         sb.append("\tordering=\"in\";\n");
+
+        // Merge multiple edges hitting the same node.  Makes common shared
+        // nodes much prettier to look at.
+        sb.append("\tconcentrate=\"true\";\n");
         
         // Just the Nodes first, in a cluster no edges
         nodes(sb, all);
@@ -59,7 +63,7 @@ public class GraphVisualizer {
             if( n instanceof ProjNode || n instanceof ScopeNode )
                 continue; // Do not emit, rolled into MultiNode or Scope cluster already
             sb.append("\t\t").append(n.uniqueName()).append(" [ ");
-            String lab = n.label();
+            String lab = n.glabel();
             if( n instanceof MultiNode ) {
                 // Make a box with the MultiNode on top, and all the projections on the bottom
                 sb.append("shape=plaintext label=<\n");
@@ -77,7 +81,7 @@ public class GraphVisualizer {
                         }
                         sb.append("<TD PORT=\"p").append(proj._idx).append("\"");
                         if( proj.isCFG() ) sb.append(" BGCOLOR=\"yellow\"");
-                        sb.append(">").append(proj.label()).append("</TD>");
+                        sb.append(">").append(proj.glabel()).append("</TD>");
                     }
                 }
                 if (doProjTable) {
@@ -93,10 +97,24 @@ public class GraphVisualizer {
                 // other nodes are ellipses, i.e. default shape
                 if( n.isCFG() )
                     sb.append("shape=box style=filled fillcolor=yellow ");
+                if( n instanceof PhiNode )
+                    sb.append("style=filled fillcolor=lightyellow ");
                 sb.append("label=\"").append(lab).append("\" ");
             }
             sb.append("];\n");
         }
+        
+        // Force Region & Phis to line up
+        for( Node n : all ) {
+          if( n instanceof RegionNode region ) {
+            sb.append("\t\t{ rank=same; ");
+            for( Node phi : region._outputs )
+              if( phi instanceof PhiNode )
+                sb.append(phi.uniqueName()).append(";");
+            sb.append("}\n");
+          }
+        }
+        
         sb.append("\t}\n");     // End Node cluster
     }
 
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index 92b1f0d5..9993c48c 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -86,7 +86,8 @@ public class Parser {
 
     private Node ctrl(Node n) { return _scope.ctrl(n); }
 
-    public StopNode parse() {
+    public StopNode parse() { return parse(false); }
+    public StopNode parse(boolean show) {
         _allScopes.push(_scope);
         _scope.push();
         try {
@@ -98,6 +99,7 @@ public class Parser {
         finally {
             _scope.pop();
             _allScopes.pop();
+            if( show ) showGraph();
         }
     }
 
@@ -135,7 +137,7 @@ public class Parser {
         else if (matchx("int")) return parseDecl();
         else if (match ("{"  )) return parseBlock();
         else if (matchx("if" )) return parseIf();
-        else if (matchx("#showGraph")) return showGraph();
+        else if (matchx("#showGraph")) return require(showGraph(),";");
         else return parseExpressionStatement();
     }
 
@@ -203,7 +205,6 @@ public class Parser {
      * @return {@code null}
      */
     private Node showGraph() {
-        require(";");
         System.out.println(new GraphVisualizer().generateDotOutput(this));
         return null;
     }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 1e9cc6c9..e4ed83a6 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -3,12 +3,11 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.*;
 
 public class AddNode extends Node {
-    public AddNode(Node lhs, Node rhs) {
-        super(null, lhs, rhs);
-    }
+    public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
-    @Override
-    public String label() { return "Add"; }
+    @Override public String label() { return "Add"; }
+    
+    @Override public String glabel() { return "+"; }
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
@@ -87,7 +86,8 @@ public class AddNode extends Node {
             // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
             for( int i=1; i<ns.length; i++ )
                 ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole();
-            return new AddNode(lhs.in(1),new PhiNode(ns).peephole());
+            String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
+            return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole());
         }
 
         // Now we sort along the spline via rotates, to gather similar things together.
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 250231f9..02eb7ce9 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -15,6 +15,9 @@ abstract public class BoolNode extends Node {
     @Override
     public String label() { return getClass().getSimpleName(); }
 
+    @Override
+    public String glabel() { return op(); }
+
     @Override
     StringBuilder _print1(StringBuilder sb) {
         in(1)._print0(sb.append("("));
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 1f562378..ae87deac 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -5,13 +5,12 @@ import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class DivNode extends Node {
-    public DivNode(Node lhs, Node rhs) {
-        super(null, lhs, rhs);
-    }
+    public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
+
+    @Override public String label() { return "Div"; }
+
+    @Override public String glabel() { return "//"; }
 
-    @Override
-    public String label() { return "Div"; }
-  
     @Override
     StringBuilder _print1(StringBuilder sb) {
         in(1)._print0(sb.append("("));
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 04084d0f..834f4c11 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -5,12 +5,11 @@ import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class MinusNode extends Node {
-    public MinusNode(Node in) {
-        super(null, in);
-    }
+    public MinusNode(Node in) { super(null, in); }
 
-    @Override
-    public String label() { return "Minus"; }
+    @Override public String label() { return "Minus"; }
+  
+    @Override public String glabel() { return "-"; }
   
     @Override
     StringBuilder _print1(StringBuilder sb) {
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
index e3e83b38..dcc21b2e 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -5,12 +5,11 @@ import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class MulNode extends Node {
-    public MulNode(Node lhs, Node rhs) {
-        super(null, lhs, rhs);
-    }
+    public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
-    @Override
-    public String label() { return "Mul"; }
+    @Override public String label() { return "Mul"; }
+  
+    @Override public String glabel() { return "*"; }
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 28d054a6..fe3fddf8 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -4,8 +4,6 @@ import com.seaofnodes.simple.type.Type;
 
 public abstract class MultiNode extends Node {
     
-    public MultiNode(Node... inputs) {
-        super(inputs);
-    }
+    public MultiNode(Node... inputs) { super(inputs); }
 
 }
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 dc4d7a33..e34b4cd5 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -62,10 +62,15 @@ public abstract class Node {
                 n._outputs.add( this );
     }
 
+    // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ"
     public abstract String label();
 
+    // Unique label for graph visualization, e.g. "Add12" or "Region30" or "EQ99"
     public String uniqueName() { return label() + _nid; }
 
+    // Graphical label, e.g. "+" or "Region" or "=="
+    public String glabel() { return label(); }
+    
     @Override
     public final String toString() {
         // TODO: This needs a lot of work
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 8e0c9a79..5eb110e7 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -5,14 +5,13 @@ import com.seaofnodes.simple.type.TypeBot;
 
 public class PhiNode extends Node {
 
-    public PhiNode(Node... inputs) {
-        super(inputs);
-    }
+    final String _label;
+    
+    public PhiNode(String label, Node... inputs) { super(inputs); _label = label; }
 
-    @Override
-    public String label() {
-        return "Phi";
-    }
+    @Override public String label() { return "Phi_"+_label; }
+
+    @Override public String glabel() { return "&phi;_"+_label; }
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
@@ -48,8 +47,8 @@ public class PhiNode extends Node {
                 lhss[i] = in(i).in(1);
                 rhss[i] = in(i).in(2);
             }
-            Node phi_lhs = new PhiNode(lhss).peephole();
-            Node phi_rhs = new PhiNode(rhss).peephole();
+            Node phi_lhs = new PhiNode(_label,lhss).peephole();
+            Node phi_rhs = new PhiNode(_label,rhss).peephole();
             return op.copy(phi_lhs,phi_rhs);
         }
 
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index d29cbd57..ae8724b9 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -4,14 +4,10 @@ import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeControl;
 
 public class RegionNode extends Node {
-    public RegionNode(Node... inputs) {
-        super(inputs);
-    }
+    public RegionNode(Node... inputs) { super(inputs); }
 
     @Override
-    public String label() {
-        return "Region";
-    }
+    public String label() { return "Region"; }
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
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 b3cca3da..b854c627 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -18,8 +18,10 @@ public class ScopeNode extends Node {
      */
     public final Stack<HashMap<String, Integer>> _scopes = new Stack<>();
 
-    @Override
-    public String label() { return "Scope"; }
+    // Reverse lookup for nicer graph printing
+    private final ArrayList<String> _rlabels = new ArrayList<>();
+    
+    @Override public String label() { return "Scope"; }
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
@@ -43,8 +45,7 @@ public class ScopeNode extends Node {
     @Override
     public TypeBot compute() { return TypeBot.BOTTOM; }
 
-    @Override
-    public Node idealize() { return null; }
+    @Override public Node idealize() { return null; }
 
     // Add an empty lexical scope
     public HashMap<String, Integer> push() {
@@ -62,6 +63,7 @@ public class ScopeNode extends Node {
         HashMap<String,Integer> scope = _scopes.lastElement();
         if( scope.put(name,nIns()) != null )
             return null;        // Double define
+        _rlabels.add(name);
         return add_def(n);
     }
 
@@ -105,9 +107,10 @@ public class ScopeNode extends Node {
     public ScopeNode dup() {
         ScopeNode dup = new ScopeNode();
         for( HashMap<String, Integer> tab : _scopes )
-            dup._scopes.push(new HashMap<String, Integer>(tab));
+            dup._scopes.push(new HashMap<>(tab));
         for( int i=0; i<nIns(); i++ )
             dup.add_def(in(i));
+        dup._rlabels.addAll(_rlabels);
         return dup;
     }
 
@@ -115,7 +118,7 @@ public class ScopeNode extends Node {
         RegionNode r = (RegionNode)ctrl(new RegionNode(ctrl(), that.ctrl()).peephole());
         for( int i=1; i<nIns(); i++ )
             if( in(1) != that.in(i) ) // No need for redundant Phis
-                set_def(i,new PhiNode(r, in(i), that.in(i)).peephole());
+                set_def(i,new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole());
         that.kill();            // Kill merged scope
         return r;
     }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
index e5939e1b..42ddc1c1 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -5,12 +5,11 @@ import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class SubNode extends Node {
-    public SubNode(Node lhs, Node rhs) {
-        super(null, lhs, rhs);
-    }
+    public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
-    @Override
-    public String label() { return "Sub"; }
+    @Override public String label() { return "Sub"; }
+
+    @Override public String glabel() { return "-"; }
 
     @Override
     StringBuilder _print1(StringBuilder sb) {
diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index a4bf89ec..cd350db5 100644
--- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -51,15 +51,15 @@ return c;
     
     @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;");
-        StopNode ret = parser.parse();
+        Parser parser = new Parser("int a=arg+1; int b=0; if( arg==1 ) b=a; else b=a+1; return a+b;");
+        StopNode ret = parser.parse(true);
         assertEquals("return ((arg*2)+Phi(Region20,2,3));", 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;");
-        StopNode ret = parser.parse();
+        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;");
+        StopNode ret = parser.parse(true);
         assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString());
     }
 
-- 
cgit v1.2.3