From 425f05826799e9da06a630187d2ad05c656266a1 Mon Sep 17 00:00:00 2001
From: Dibyendu Majumdar <mobile@majumdar.org.uk>
Date: Sun, 3 Dec 2023 23:23:04 +0000
Subject: Chapter 8: Lazy Phis, Break, Continue, and Evaluator

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
---
 .../java/com/seaofnodes/simple/node/AddNode.java   |  5 ++
 .../java/com/seaofnodes/simple/node/IfNode.java    |  2 +-
 .../java/com/seaofnodes/simple/node/LoopNode.java  |  3 +-
 src/main/java/com/seaofnodes/simple/node/Node.java | 11 +++-
 .../java/com/seaofnodes/simple/node/PhiNode.java   |  5 +-
 .../com/seaofnodes/simple/node/RegionNode.java     |  1 +
 .../java/com/seaofnodes/simple/node/ScopeNode.java | 68 +++++++++++++++-------
 7 files changed, 68 insertions(+), 27 deletions(-)

(limited to 'src/main/java/com/seaofnodes/simple/node')

diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 8f3e5a98..84a368fd 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -70,6 +70,11 @@ public class AddNode extends Node {
 
         // Now we only see (add add non)
 
+        // Dead data cycle; comes about from dead infinite loops.  Do nothing,
+        // the loop will peep as dead after a bit.
+        if( lhs.in(1) == lhs )
+            return null;
+
         // Do we have (x + con1) + con2?
         // Replace with (x + (con1+con2) which then fold the constants
         if( lhs.in(2)._type.isConstant() && t2.isConstant() )
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 0f414c08..23a8fafc 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -46,7 +46,7 @@ public class IfNode extends MultiNode {
             return prior instanceof ProjNode proj
               // Repeated test, dominated on one side.  Test result is the same.
               ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE)
-              : null;           // Repeated test not dominated on one side
+              : dom._type;      // Repeated test not dominated on one side
 
         return TypeTuple.IF_BOTH;
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index 81f707ec..c192bc20 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -16,7 +16,8 @@ public class LoopNode extends RegionNode {
 
     @Override
     public Type compute() {
-        return inProgress() ? Type.CONTROL : super.compute();
+        if( inProgress() ) return Type.CONTROL;
+        return entry()._type;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 35b07781..2d6d5ad5 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.IRPrinter;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
@@ -100,6 +101,7 @@ public abstract class Node {
     public final String print() {
         return _print0(new StringBuilder(), new BitSet()).toString();
     }
+
     // 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) {
@@ -138,6 +140,8 @@ public abstract class Node {
         sb.append("\n");
     }
 
+    public String p(int depth) { return IRPrinter.prettyPrint(this,depth); }
+
     public boolean isMultiHead() { return false; }
     public boolean isMultiTail() { return false; }
 
@@ -153,8 +157,6 @@ public abstract class Node {
 
     public int nIns() { return _inputs.size(); }
 
-    public Node out(int i) { return _outputs.get(i); }
-
     public int nOuts() { return _outputs.size(); }
 
     public boolean isUnused() { return nOuts() == 0; }
@@ -443,7 +445,10 @@ public abstract class Node {
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
      */
-    public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; }
+    public static void reset() {
+        UNIQUE_ID = 1;
+        _disablePeephole=false;
+    }
 
     /**
      * Debugging utility to find a Node by index
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 2a4ff52a..c7b5b357 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -85,10 +85,13 @@ public class PhiNode extends Node {
      */
     private Node singleUniqueInput() {
         Node live = null;
-        for( int i=1; i<nIns(); i++ )
+        for( int i=1; i<nIns(); i++ ) {
+            if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL )
+                return null;    // Dead entry loops just ignore and let the loop collapse
             if( region().in(i)._type != Type.XCONTROL && in(i) != this )
                 if( live == null || live == in(i) ) live = in(i);
                 else return null;
+        }
         return live;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index acaadaf1..453d028f 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -3,6 +3,7 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
+import java.util.Collection;
 import java.util.BitSet;
 
 public class RegionNode extends Node {
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index a4fcbe65..e5d03d93 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -39,6 +39,10 @@ public class ScopeNode extends Node {
         for( int j=0; j<nIns(); j++ ) {
             sb.append(names[j]).append(":");
             Node n = in(j);
+            while( n instanceof ScopeNode loop ) {
+                sb.append("Lazy_");
+                n = loop.in(j);
+            }
             n._print0(sb, visited).append(" ");
         }
         sb.setLength(sb.length()-1);
@@ -107,8 +111,18 @@ public class ScopeNode extends Node {
         var idx = syms.get(name);
         if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope
         Node old = in(idx);
-        // If n is null we are looking up rather than updating, hence return existing value
-        return n==null ? old : setDef(idx,n);
+        if( old instanceof ScopeNode loop ) {
+            // Lazy Phi!
+            old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region()
+                // Loop already has a real Phi, use it
+                ? loop.in(idx)
+                // Set real Phi in the loop head
+                // The phi takes its one input (no backedge yet) from a recursive
+                // lookup, which might have insert a Phi in every loop nest.
+                : loop.setDef(idx,new PhiNode(name,loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
+            setDef(idx,old);
+        }
+        return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer
     }
 
     public Node ctrl() { return in(0); }
@@ -131,6 +145,11 @@ public class ScopeNode extends Node {
      * tables), nor deep (would dup the Scope, the HashMap tables, but then
      * also the program Nodes).
      * <p>
+     * If the {@code loop} flag is set, the edges are filled in as the original
+     * Scope, as a indication of Lazy Phis at loop heads.  The goal here is to
+     * not make Phis at loop heads for variables which are never touched in the
+     * loop body.
+     * <p>
      * The new Scope is a full-fledged Node with proper use<->def edges.
      */
     public ScopeNode dup() { return dup(false); }
@@ -144,17 +163,10 @@ public class ScopeNode extends Node {
             dup._scopes.push(new HashMap<>(syms));
 
         dup.addDef(ctrl());      // Control input is just copied
-        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));
-            }
-        }
+        for( int i=1; i<nIns(); i++ )
+            // For lazy phis on loops we use a sentinel
+            // that will trigger phi creation on update
+            dup.addDef(loop ? this : in(i));
         return dup;
     }
 
@@ -172,7 +184,9 @@ public class ScopeNode extends Node {
         // Note that we skip i==0, which is bound to '$ctrl'
         for (int i = 1; i < nIns(); i++)
             if( in(i) != that.in(i) ) // No need for redundant Phis
-                setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole());
+                // If we are in lazy phi mode we need to a lookup
+                // by name as it will trigger a phi creation
+                setDef(i, new PhiNode(ns[i], r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
         that.kill();            // Kill merged scope
         return r.unkeep().peephole();
     }
@@ -184,14 +198,26 @@ public class ScopeNode extends Node {
         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);
+            if( back.in(i) != this ) {
+                PhiNode phi = (PhiNode)in(i);
+                assert phi.region()==ctrl && phi.in(2)==null;
+                phi.setDef(2,back.in(i));
+            }
+            if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also
+                exit.setDef(i,in(i));
         }
         back.kill();            // Loop backedge is dead
+        // Now one-time do a useless-phi removal
+        for( int i=1; i<nIns(); i++ ) {
+            if( in(i) instanceof PhiNode phi ) {
+                // Do an eager useless-phi removal
+                Node in = phi.peephole();
+                if( in != phi ) {
+                    phi.subsume(in);
+                    setDef(i,in); // Set the update back into Scope
+                }
+            }
+        }
+
     }
 }
-- 
cgit v1.2.3