Float bugs

Fix bug infinite loop finding.
Fix inf loops before printing graph.
Missing float unary negate .
Generator makes float exprs
Fix missing dep in LCA finding

15 files changed, 76 insertions, 22 deletions

diff --git a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
index 054a489c..4e0a31d5 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java
@@ -10,7 +10,6 @@ public abstract class GlobalCodeMotion {
     // Node.use(0) is always a block tail (either IfNode or head of the
     // following block).  There are no unreachable infinite loops.
     public static void buildCFG( StopNode stop ) {
-        fixLoops(stop);
         schedEarly();
         Parser.SCHEDULED = true;
         schedLate(Parser.START);
@@ -20,7 +19,7 @@ public abstract class GlobalCodeMotion {
     // Backwards walk on the CFG only, looking for unreachable code - which has
     // to be an infinite loop.  Insert a bogus never-taken exit to Stop, so the
     // loop becomes reachable.  Also, set loop nesting depth
-    private static void fixLoops(StopNode stop) {
+    static void fixLoops(StopNode stop) {
         // Backwards walk from Stop, looking for unreachable code
         BitSet visit = new BitSet();
         HashSet<CFGNode> unreach = new HashSet<>();
@@ -148,7 +147,7 @@ public abstract class GlobalCodeMotion {
         assert early != null;
         CFGNode lca = null;
         for( Node use : n._outputs )
-            lca = use_block(n,use, late).idom(lca);
+            lca = use_block(n,use, late)._idom(lca,null);
 
         // Loads may need anti-dependencies, raising their LCA
         if( n instanceof LoadNode load )
@@ -214,6 +213,7 @@ public abstract class GlobalCodeMotion {
                 break;
             case LoadNode ld: break; // Loads do not cause anti-deps on other loads
             case ReturnNode ret: break; // Load must already be ahead of Return
+            case NeverNode never: break;
             default: throw Utils.TODO();
             }
         }
@@ -226,7 +226,7 @@ public abstract class GlobalCodeMotion {
         for( ; stblk != defblk.idom(); stblk = stblk.idom() ) {
             // Store and Load overlap, need anti-dependence
             if( stblk._anti==load._nid ) {
-                lca = stblk.idom(lca); // Raise Loads LCA
+                lca = stblk._idom(lca,null); // Raise Loads LCA
                 if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved,
                     st.addDef(load);   // Add anti-dep as well
                 return lca;            // Cap this stores' anti-dep to here
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java
index b2b76777..121d0233 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -92,6 +92,8 @@ public abstract class IterPeeps {
                 n.kill();       // Just plain dead
         }
 
+        // Break infinite loops, forcing a Never-branch to exit
+        GlobalCodeMotion.fixLoops(stop);
         if( show )
             System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null));
         GlobalCodeMotion.buildCFG(stop);
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/Parser.java b/chapter12/src/main/java/com/seaofnodes/simple/Parser.java
index 4c62226b..cc1fb0df 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/Parser.java
@@ -429,6 +429,8 @@ public class Parser {
                 throw error("Undefined name '" + name + "'");
             _scope.update(name,expr);
         }
+        if( expr._type instanceof TypeInteger && t instanceof TypeFloat )
+            expr = expr.widen();
         if( !expr._type.isa(t) )
             throw error("Type " + expr._type.str() + " is not of declared type " + t.str());
         return expr;
@@ -564,7 +566,7 @@ public class Parser {
      * @return a unary expression {@link Node}, never {@code null}
      */
     private Node parseUnary() {
-        if (match("-")) return new MinusNode(parseUnary()).peephole();
+        if (match("-")) return new MinusNode(parseUnary()).widen().peephole();
         if (match("!")) return new   NotNode(parseUnary()).peephole();
         return parsePostfix(parsePrimary());
     }
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 4454a5ad..b9faeb32 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -76,8 +76,8 @@ abstract public class BoolNode extends Node {
     public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } BoolNode copyF() { return new LTF(null,null); }}
     public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } BoolNode copyF() { return new LEF(null,null); } }
 
-    public static class EQF extends BoolNode { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(double lhs, double rhs) { return lhs == rhs; } }
-    public static class LTF extends BoolNode { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(double lhs, double rhs) { return lhs <  rhs; } }
-    public static class LEF extends BoolNode { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } }
+    public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } }
+    public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <  rhs; } }
+    public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } }
 
 }
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index b605071b..07ba0fa4 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -52,16 +52,17 @@ public abstract class CFGNode extends Node {
     public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
 
     // Return the immediate dominator of this Node and compute dom tree depth.
-    public CFGNode idom() { return cfg(0); }
+    public CFGNode idom(Node dep) { return cfg(0); }
+    public final CFGNode idom() { return idom(null); }
 
     // Return the LCA of two idoms
-    public CFGNode idom(CFGNode rhs) {
+    public CFGNode _idom(CFGNode rhs, Node dep) {
         if( rhs==null ) return this;
         CFGNode lhs = this;
         while( lhs != rhs ) {
             var comp = lhs.idepth() - rhs.idepth();
-            if( comp >= 0 ) lhs = lhs.idom();
-            if( comp <= 0 ) rhs = rhs.idom();
+            if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom();
+            if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom();
         }
         return lhs;
     }
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index c662dee6..22862cb9 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -30,7 +30,7 @@ public class LoopNode extends RegionNode {
     // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
     @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
     // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
-    @Override public CFGNode idom() { return entry(); }
+    @Override public CFGNode idom(Node dep) { return entry(); }
 
     @Override public int loopDepth() {
         if( _loopDepth!=0 ) return _loopDepth; // Was already set
@@ -60,8 +60,11 @@ public class LoopNode extends RegionNode {
         // directly on the If) we found our exit.
         CFGNode x = back();
         while( x != this ) {
-            if( x instanceof CProjNode exit )
-                return;         // Found an exit, not an infinite loop
+            if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) {
+                Node other = iff.cproj(1-exit._idx);
+                if( !(other.out(0) instanceof LoopNode loop) || loop.entry()==exit )
+                    return;         // Found an exit, not an infinite loop
+            }
             x = x.idom();
         }
         // Found a no-exit loop.  Insert an exit
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MinusFNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MinusFNode.java
new file mode 100644
index 00000000..0853729d
--- /dev/null
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MinusFNode.java
@@ -0,0 +1,36 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeFloat;
+
+import java.util.BitSet;
+
+public class MinusFNode extends Node {
+    public MinusFNode(Node in) { super(null, in); }
+
+    @Override public String label() { return "MinusF"; }
+
+    @Override public String glabel() { return "-"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        in(1)._print0(sb.append("(-"), visited);
+        return sb.append(")");
+    }
+
+    @Override
+    public Type compute() {
+        if (in(1)._type instanceof TypeFloat i0)
+            return i0.isConstant() ? TypeFloat.constant(-i0.value()) : i0;
+        return TypeFloat.TOP.meet(in(1)._type);
+    }
+
+    @Override
+    public Node idealize() {
+        // -(-x) is x
+        if( in(1) instanceof MinusFNode minus )
+            return minus.in(1);
+
+        return null;
+    }
+}
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 9b687613..ae8e9e1b 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -33,4 +33,5 @@ public class MinusNode extends Node {
 
         return null;
     }
+    @Override Node copyF() { return new MinusFNode(null); }
 }
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index 379e140d..ac9c0045 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -9,4 +9,12 @@ public interface MultiNode extends OutNode {
                 return prj;
         return null;
     }
+
+    // Find a projection by index
+    default CProjNode cproj( int idx ) {
+        for( Node out : outs() )
+            if( out instanceof CProjNode prj && prj._idx==idx )
+                return prj;
+        return null;
+    }
 }
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/NeverNode.java
index f50d3503..e77ed653 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/NeverNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/NeverNode.java
@@ -3,6 +3,8 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.TypeInteger;
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeTuple;
+
 import java.util.BitSet;
 
 // "Never true" for infinite loop exits
@@ -13,7 +15,7 @@ public class NeverNode extends IfNode {
 
     @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append("Never"); }
 
-    @Override public Type compute() { return TypeInteger.BOT; }
+    @Override public Type compute() { return TypeTuple.IF_BOTH; }
 
     @Override public Node idealize() { return null; }
 }
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java
index 3af49dbf..03b3d5e0 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.IRPrinter;
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index a07dc140..535db980 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -100,7 +100,7 @@ public class PhiNode extends Node {
             if( in(2)._type == in(2)._type.makeInit() ) nullx = 2;
             if( nullx != -1 ) {
                 Node val = in(3-nullx);
-                if( region().idom() instanceof IfNode iff && iff.pred().addDep(this)==val ) {
+                if( region().idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) {
                     // Must walk the idom on the null side to make sure we hit False.
                     CFGNode idom = (CFGNode)region().in(nullx);
                     while( idom.in(0) != iff ) idom = idom.idom();
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index dcc7ccef..d5105614 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -99,12 +99,12 @@ public class RegionNode extends CFGNode {
         return _idepth=d;
     }
 
-    @Override public CFGNode idom() {
+    @Override public CFGNode idom(Node dep) {
         CFGNode lca = null;
         // Walk the LHS & RHS idom trees in parallel until they match, or either fails.
         // Because this does not cache, it can be linear in the size of the program.
         for( int i=1; i<nIns(); i++ )
-            lca = cfg(i).idom(lca);
+            lca = cfg(i)._idom(lca,dep);
         return lca;
     }
 
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 62fc8a6b..5f205ffd 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -75,7 +75,7 @@ public class StartNode extends CFGNode implements MultiNode {
 
     // No immediate dominator, and idepth==0
     @Override public int idepth() { return 0; }
-    @Override public CFGNode idom() { return null; }
+    @Override public CFGNode idom(Node dep) { return null; }
 
     @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { }
 
diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java
index 94b2ad6d..ab567bae 100644
--- a/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter12/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -59,7 +59,7 @@ public class StopNode extends CFGNode {
                 d = Math.max(d,((CFGNode)n).idepth()+1);
         return _idepth=d;
     }
-    @Override public CFGNode idom() { return null; }
+    @Override public CFGNode idom(Node dep) { return null; }
 
     @Override public int loopDepth() { return (_loopDepth=1); }