Chapter 7: While Statementlinear-chapter07

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

18 files changed, 220 insertions, 62 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index b37785f6..8f3e5a98 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.*;
 
+import java.util.BitSet;
+
 public class AddNode extends Node {
     public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -10,9 +12,9 @@ public class AddNode extends Node {
     @Override public String glabel() { return "+"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("+"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("+"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index a9ec6838..0c32d50d 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 abstract public class BoolNode extends Node {
 
     public BoolNode(Node lhs, Node rhs) {
@@ -18,9 +20,9 @@ abstract public class BoolNode extends Node {
     public String glabel() { return op(); }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append(op()));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append(op()), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 1086037d..13006bfb 100644
--- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 /**
  * A Constant node represents a constant value.  At present, the only constants
  * that we allow are integer literals; therefore Constants contain an integer
@@ -29,10 +31,12 @@ public class ConstantNode extends Node {
     public String uniqueName() { return "Con_" + _nid; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
         return _con._print(sb);
     }
 
+    @Override public boolean isMultiTail() { return true; }
+
     @Override
     public Type compute() { return _con; }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 519a8c8a..7207fd48 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class DivNode extends Node {
     public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -11,9 +13,9 @@ public class DivNode extends Node {
     @Override public String glabel() { return "//"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("/"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("/"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 34846e99..0f414c08 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -4,6 +4,8 @@ import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.type.TypeTuple;
 
+import java.util.BitSet;
+
 public class IfNode extends MultiNode {
 
     public IfNode(Node ctrl, Node pred) {
@@ -14,12 +16,13 @@ public class IfNode extends MultiNode {
     public String label() { return "If"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
         sb.append("if( ");
-        return in(1)._print0(sb).append(" )");
+        return in(1)._print0(sb, visited).append(" )");
     }
 
     @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { return true; }
 
     public Node ctrl() { return in(0); }
     public Node pred() { return in(1); }
@@ -27,7 +30,8 @@ public class IfNode extends MultiNode {
     @Override
     public Type compute() {
         // If the If node is not reachable then neither is any following Proj
-        if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER;
+        if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM )
+            return TypeTuple.IF_NEITHER;
         // If constant is 0 then false branch is reachable
         // Else true branch is reachable
         if (pred()._type instanceof TypeInteger ti && ti.isConstant()) {
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
new file mode 100644
index 00000000..81f707ec
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -0,0 +1,28 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+import java.util.BitSet;
+
+public class LoopNode extends RegionNode {
+
+    public LoopNode( Node entry ) { super(null,entry,null); }
+
+    Node entry() { return in(1); }
+    Node back () { return in(2); }
+
+    @Override
+    public String label() { return "Loop"; }
+
+    @Override
+    public Type compute() {
+        return inProgress() ? Type.CONTROL : super.compute();
+    }
+
+    @Override
+    public Node idealize() {
+        return inProgress() ? null : super.idealize();
+    }
+
+    @Override Node idom() { return entry(); }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 0d59ef25..3d944fd4 100644
--- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class MinusNode extends Node {
     public MinusNode(Node in) { super(null, in); }
 
@@ -11,8 +13,8 @@ public class MinusNode extends Node {
     @Override public String glabel() { return "-"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("(-"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("(-"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 0380c079..2e701a4e 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class MulNode extends Node {
     public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -11,9 +13,9 @@ public class MulNode extends Node {
     @Override public String glabel() { return "*"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("*"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("*"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 97ba68ab..35b07781 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -98,18 +98,51 @@ public abstract class Node {
     // tik-tok style; the common _print0 calls the per-Node _print1, which
     // calls back to _print0;
     public final String print() {
-        return _print0(new StringBuilder()).toString();
+        return _print0(new StringBuilder(), new BitSet()).toString();
     }
-    // This is the common print: check for DEAD and print "DEAD" else call the
-    // per-Node print1.
-    final StringBuilder _print0(StringBuilder sb) {
+    // This is the common print: check for repeats, check for DEAD and print
+    // "DEAD" else call the per-Node print1.
+    final StringBuilder _print0(StringBuilder sb, BitSet visited) {
+        if (visited.get(_nid))
+            return sb.append(label());
+        visited.set(_nid);
         return isDead()
             ? sb.append(uniqueName()).append(":DEAD")
-            : _print1(sb);
+            : _print1(sb, visited);
+    }
+    // Every Node implements this; a partial-line recursive print
+    abstract StringBuilder _print1(StringBuilder sb, BitSet visited);
+
+
+    // Print a node on 1 line, columnar aligned, as:
+    // NNID NNAME DDEF DDEF  [[  UUSE UUSE  ]]  TYPE
+    // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt
+    public void _printLine(StringBuilder sb ) {
+        sb.append("%4d %-7.7s ".formatted(_nid,label()));
+        if( _inputs==null ) {
+            sb.append("DEAD\n");
+            return;
+        }
+        for( Node def : _inputs )
+            sb.append(def==null ? "____ " : "%4d ".formatted(def._nid));
+        for( int i = _inputs.size(); i<3; i++ )
+            sb.append("     ");
+        sb.append(" [[  ");
+        for( Node use : _outputs )
+            sb.append("%4d ".formatted(use._nid));
+        int lim = 5 - Math.max(_inputs.size(),3);
+        for( int i = _outputs.size(); i<lim; i++ )
+            sb.append("     ");
+        sb.append(" ]]  ");
+        if( _type!= null ) _type._print(sb);
+        sb.append("\n");
     }
-    // Every Node implements this.
-    abstract StringBuilder _print1(StringBuilder sb);
 
+    public boolean isMultiHead() { return false; }
+    public boolean isMultiTail() { return false; }
+
+    // ------------------------------------------------------------------------
+    // Graph Node & Edge manipulation
 
     /**
      * Gets the ith input node
@@ -230,6 +263,20 @@ public abstract class Node {
     public <N extends Node> N keep() { return addUse(null); }
     // Remove bogus null.
     public <N extends Node> N unkeep() { delUse(null); return (N)this; }
+
+
+    // Replace self with nnn in the graph, making 'this' go dead
+    void subsume( Node nnn ) {
+        assert nnn!=this;
+        while( nOuts() > 0 ) {
+            Node n = _outputs.removeLast();
+            int idx = Utils.find(n._inputs, this);
+            n._inputs.set(idx,nnn);
+            nnn.addUse(n);
+        }
+        kill();
+    }
+
     // ------------------------------------------------------------------------
     // Graph-based optimizations
 
diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java
index e3683646..39df410d 100644
--- a/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class NotNode extends Node {
     public NotNode(Node in) { super(null, in); }
 
@@ -11,8 +13,8 @@ public class NotNode extends Node {
     @Override public String glabel() { return "!"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("(!"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("(!"), visited);
         return sb.append(")");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 15088e08..2a4ff52a 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 public class PhiNode extends Node {
 
     final String _label;
@@ -13,19 +15,27 @@ public class PhiNode extends Node {
     @Override public String glabel() { return "&phi;_"+_label; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        if( region().inProgress() )
+            sb.append("Z");
         sb.append("Phi(");
-        for( Node in : _inputs )
-            in._print0(sb).append(",");
+        for( Node in : _inputs ) {
+            if (in == null) sb.append("____");
+            else in._print0(sb, visited);
+            sb.append(",");
+        }
         sb.setLength(sb.length()-1);
         sb.append(")");
         return sb;
     }
 
-    Node region() { return in(0); }
+    RegionNode region() { return (RegionNode)in(0); }
+    @Override public boolean isMultiTail() { return true; }
 
     @Override
     public Type compute() {
+        if( !(region() instanceof RegionNode r) || r.inProgress() )
+            return Type.BOTTOM;
         Type t = Type.TOP;
         for (int i = 1; i < nIns(); i++)
             t = t.meet(in(i)._type);
@@ -34,6 +44,9 @@ public class PhiNode extends Node {
 
     @Override
     public Node idealize() {
+        if( !(region() instanceof RegionNode r ) || r.inProgress() )
+            return null;
+
         // If we have only a single unique input, become it.
         Node live = singleUniqueInput();
         if (live != null)
@@ -79,5 +92,10 @@ public class PhiNode extends Node {
         return live;
     }
 
-
+    @Override
+    boolean allCons() {
+        if( !(region() instanceof RegionNode r) || r.inProgress() )
+            return false;
+        return super.allCons();
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 85f28037..3c3f73b8 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeTuple;
 
+import java.util.BitSet;
+
 public class ProjNode extends Node {
 
     // Which slice of the incoming multi-part value
@@ -21,9 +23,10 @@ public class ProjNode extends Node {
     public String label() { return _label; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) { return sb.append(_label); }
+    StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); }
 
     @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
+    @Override public boolean isMultiTail() { return in(0).isMultiHead(); }
 
     public MultiNode ctrl() { return (MultiNode)in(0); }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index bb7998a3..acaadaf1 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -3,21 +3,26 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 public class RegionNode extends Node {
-    public RegionNode(Node... inputs) { super(inputs); }
+
+    public RegionNode(Node... nodes) { super(nodes); }
 
     @Override
     public String label() { return "Region"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
         return sb.append(label()).append(_nid);
     }
 
     @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { return true; }
 
     @Override
     public Type compute() {
+        if( inProgress() ) return Type.CONTROL;
         Type t = Type.XCONTROL;
         for (int i = 1; i < nIns(); i++)
             t = t.meet(in(i)._type);
@@ -26,6 +31,7 @@ public class RegionNode extends Node {
 
     @Override
     public Node idealize() {
+        if( inProgress() ) return null;
         int path = findDeadInput();
         if( path != 0 ) {
             for( Node phi : _outputs )
@@ -72,4 +78,9 @@ public class RegionNode extends Node {
         _idepth = lhs._idepth+1;
         return (_idom=lhs);
     }
+
+    // True if last input is null
+    public final boolean inProgress() {
+        return in(nIns()-1) == null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 6130d050..312058b9 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.*;
 
+import java.util.BitSet;
+
 /**
  * The Return node has two inputs.  The first input is a control node and the
  * second is the data node that supplies the return value.
@@ -24,8 +26,8 @@ public class ReturnNode extends Node {
     public String label() { return "Return"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        return expr()._print0(sb.append("return ")).append(";");
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        return expr()._print0(sb.append("return "), visited).append(";");
     }
 
     @Override public boolean isCFG() { return true; }
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index a7a04a42..a4fcbe65 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -33,22 +33,16 @@ public class ScopeNode extends Node {
     @Override public String label() { return "Scope"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        sb.append(label());
-        for( HashMap<String,Integer> scope : _scopes ) {
-            sb.append("[");
-            boolean first=true;
-            for( String name : scope.keySet() ) {
-                if( !first ) sb.append(", ");
-                first=false;
-                sb.append(name).append(":");
-                Node n = in(scope.get(name));
-                if( n==null ) sb.append("null");
-                else n._print0(sb);
-            }
-            sb.append("]");
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        sb.append("Scope[ ");
+        String[] names = reverseNames();
+        for( int j=0; j<nIns(); j++ ) {
+            sb.append(names[j]).append(":");
+            Node n = in(j);
+            n._print0(sb, visited).append(" ");
         }
-        return sb;
+        sb.setLength(sb.length()-1);
+        return sb.append("]");
     }
 
     /**
@@ -139,7 +133,8 @@ public class ScopeNode extends Node {
      * <p>
      * The new Scope is a full-fledged Node with proper use<->def edges.
      */
-    public ScopeNode dup() {
+    public ScopeNode dup() { return dup(false); }
+    public ScopeNode dup(boolean loop) {
         ScopeNode dup = new ScopeNode();
         // Our goals are:
         // 1) duplicate the name bindings of the ScopeNode across all stack levels
@@ -147,9 +142,19 @@ public class ScopeNode extends Node {
         // 3) Ensure that the order of defs is the same to allow easy merging
         for( HashMap<String,Integer> syms : _scopes )
             dup._scopes.push(new HashMap<>(syms));
+
         dup.addDef(ctrl());      // Control input is just copied
-        for( int i=1; i<nIns(); i++ )
-            dup.addDef(in(i));
+        for( int i=1; i<nIns(); i++ ) {
+            if ( !loop ) { dup.addDef(in(i)); }
+            else {
+                String[] names = reverseNames(); // Get the variable names
+                // Create a phi node with second input as null - to be filled in
+                // by endLoop() below
+                dup.addDef(new PhiNode(names[i], ctrl(), in(i), null).peephole());
+                // Ensure our node has the same phi in case we created one
+                setDef(i, dup.in(i));
+            }
+        }
         return dup;
     }
 
@@ -172,4 +177,21 @@ public class ScopeNode extends Node {
         return r.unkeep().peephole();
     }
 
+    // Merge the backedge scope into this loop head scope
+    // We set the second input to the phi from the back edge (i.e. loop body)
+    public void endLoop(ScopeNode back, ScopeNode exit ) {
+        Node ctrl = ctrl();
+        assert ctrl instanceof LoopNode loop && loop.inProgress();
+        ctrl.setDef(2,back.ctrl());
+        for( int i=1; i<nIns(); i++ ) {
+            PhiNode phi = (PhiNode)in(i);
+            assert phi.region()==ctrl && phi.in(2)==null;
+            phi.setDef(2,back.in(i));
+            // Do an eager useless-phi removal
+            Node in = phi.peephole();
+            if( in != phi )
+                phi.subsume(in);
+        }
+        back.kill();            // Loop backedge is dead
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index c5a45876..01f1485a 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeTuple;
 
+import java.util.BitSet;
+
 /**
  * The Start node represents the start of the function.  For now, we do not
  * have any inputs to Start because our function does not yet accept
@@ -24,11 +26,12 @@ public class StartNode extends MultiNode {
     public String label() { return "Start"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
       return sb.append(label());
     }
 
     @Override public boolean isCFG() { return true; }
+    @Override public boolean isMultiHead() { return true; }
 
     @Override
     public TypeTuple compute() { return _args; }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 01574dc7..417790d9 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -2,6 +2,8 @@ package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
 
+import java.util.BitSet;
+
 public class StopNode extends Node {
     public StopNode(Node... inputs) {
         super(inputs);
@@ -13,11 +15,11 @@ public class StopNode extends Node {
     }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        if( ret()!=null ) return ret()._print0(sb);
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        if( ret()!=null ) return ret()._print0(sb, visited);
         sb.append("Stop[ ");
         for( Node ret : _inputs )
-            ret._print0(sb).append(" ");
+            ret._print0(sb, visited).append(" ");
         return sb.append("]");
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 475b3790..af66b950 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeInteger;
 
+import java.util.BitSet;
+
 public class SubNode extends Node {
     public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); }
 
@@ -11,9 +13,9 @@ public class SubNode extends Node {
     @Override public String glabel() { return "-"; }
 
     @Override
-    StringBuilder _print1(StringBuilder sb) {
-        in(1)._print0(sb.append("("));
-        in(2)._print0(sb.append("-"));
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("("), visited);
+        in(2)._print0(sb.append("-"), visited);
         return sb.append(")");
     }