Backport Opto speedups and Minus fix

5 files changed, 134 insertions, 46 deletions

diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java
index c78e732e..0c18863a 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java
@@ -2,6 +2,7 @@ package com.seaofnodes.simple.codegen;
 
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.IterPeeps.WorkList;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.Ary;
 import java.util.BitSet;
@@ -26,8 +27,11 @@ abstract public class Opto {
     public static void opto(CodeGen code) {
 
         // Reset Types before running the worklist algorithm
-        Ary<Type> oldTypes = new Ary<>(Type.class); // Used for asserts only
-        resetToTop(code,oldTypes);
+        Ary<Type> oldTypes = new Ary<>(Type.class);
+        WorkList<Node> deps = new WorkList<>();
+        WorkList<Node> changes = new WorkList<>();
+        Ary<Node> modes = new Ary<>(Node.class);
+        resetToTop(code,oldTypes,modes);
 
         // The whole-world assumption: we use it if compiling `main`, and not otherwise.
         // The assumption is no unknown callers into functions:
@@ -50,21 +54,27 @@ abstract public class Opto {
 
 
         // OPTIMISTIC INTERPROCEDURAL SCCP
-        sccp(code, oldTypes);
-        resolveNumericModes(code);
-        if( !code._iter._work.isEmpty() ) sccp(code, oldTypes);
+        sccp(code, oldTypes, changes, deps);
+        // Settle modes, then resume SCCP on affected nodes without resetting types.
+        // Any further type changes must still fall; BOTTOM results stay BOTTOM.
+        resolveNumericModes(code,modes);
+        if( !code._iter._work.isEmpty() ) sccp(code, oldTypes, changes, deps);
 
         // After SCCP add everything changed to the worklist and see if
         // peepholes can make more progress.
-        moveChangesToWorklist(code, oldTypes);
+        Node dep;
+        while( (dep=deps.pop())!=null ) code.add(dep);
+        moveChangesToWorklist(code, oldTypes, changes);
 
 
     }
 
     // Reset Types before running the worklist algorithm
-    private static void resetToTop(CodeGen code, Ary<Type> oldTypes ) {
+    private static void resetToTop(CodeGen code, Ary<Type> oldTypes, Ary<Node> modes ) {
         code._start.walk( x -> {
-                oldTypes.setX(x._nid,x._type); // Record original types for asserts
+                // SCCP adds call edges and default arguments, not numeric operations.
+                if( x instanceof ModeNode mode && mode.mode()==0 ) modes.push(x);
+                oldTypes.setX(x._nid,x._type); // Compare the final SCCP type with Iter's type
                 x._type = Type.TOP;            // Reset all Nodes to TOP
                 code._iter.add(x); // Visit everybody at least once; most Nodes produce better than TOP
                 // Unlink all existing (conservative) linkages.
@@ -127,7 +137,7 @@ abstract public class Opto {
     }
 
     // The core SCCP algorithm
-    private static void sccp( CodeGen code, Ary<Type> oldTypes ) {
+    private static void sccp( CodeGen code, Ary<Type> oldTypes, WorkList<Node> changes, WorkList<Node> deps ) {
         // Iter workList is empty at this point
         // OPTIMISTIC PASS
         Node n;
@@ -136,6 +146,8 @@ abstract public class Opto {
             if( n.isDead() ) continue;
             count++;
             Type oval = n._type, nval = n.compute();
+            // Filter candidates against the final SCCP type after convergence.
+            if( nval!=oldTypes.atX(n._nid) || n.isUnlocked() ) changes.push(n);
             if( oval == nval ) continue;
             assert oval.isa(nval);    // Types start high and always fall
             Type pesiVal = oldTypes.at(n._nid);
@@ -155,6 +167,9 @@ abstract public class Opto {
 
             // Since n._type changed, visit all output neighbors
             code._iter.addAll(n._outputs);
+            // SCCP consumes these without running peepholes. Save them for
+            // the following Iter pass before moving clears the dependency list.
+            for( int i=0; i<n.nDeps(); i++ ) deps.push(n.dep(i));
             n.moveDepsToWorklist(code._iter);
             // Quadratic (expensive) small-step assert
             assert check(code);
@@ -173,22 +188,28 @@ abstract public class Opto {
 
     // After SCCP add everything changed to the worklist and see if peepholes
     // can make more progress.
-    private static void moveChangesToWorklist(CodeGen code, Ary<Type> oldTypes) {
-        code._start.walk( x -> {
-                assert x.compute() == x._type;      // Hit the fixed point
-                assert x._nid >= oldTypes._len || x._type.isa(oldTypes.at(x._nid)); // Hit at least the bottom-up type
-                code._iter.add(x);
-                return null;
-            });
+    private static void moveChangesToWorklist(CodeGen code, Ary<Type> oldTypes, WorkList<Node> changes) {
+        Node n;
+        while( (n=changes.pop())!=null ) {
+            if( n.isDead() ) continue;
+            assert n.compute() == n._type; // Hit the fixed point.
+            Type old = oldTypes.atX(n._nid);
+            assert old==null || n._type.isa(old);
+            if( n._type!=old || n.isUnlocked() ) {
+                code.add(n);
+                code.addAll(n._inputs);
+                code.addAll(n._outputs);
+                n.moveDepsToWorklist();
+            }
+        }
     }
 
-    // Resolve arithmetic modes which are ambiguous only because they belong to
-    // a recursive component.  Float wins because integer operands can be
-    // converted to float.
-    private static void resolveNumericModes(CodeGen code) {
+    // Resolve modes left undecided by SCCP, following recursive inputs for
+    // evidence. Float wins because integer operands can be converted to float.
+    private static void resolveNumericModes(CodeGen code, Ary<Node> modes) {
         final BitSet visited = new BitSet();
-        code._stop.walk(n -> {
-            if( n instanceof ModeNode modeNode && modeNode.mode()==0 ) {
+        for( Node n : modes ) {
+            if( !n.isDead() && n instanceof ModeNode modeNode && modeNode.mode()==0 ) {
                 visited.clear();
                 visited.set(n._nid); // Inspect inputs, not Bool's integer result
                 int mode = 0;
@@ -197,17 +218,11 @@ abstract public class Opto {
                 // A closed recursive numeric component can have no remaining
                 // concrete evidence after SCCP, e.g. dead all-integer loops.
                 // With no float evidence, settle to integer.
-                if( mode == 0 )
-                    mode = 1;
-                if( mode != 0 )  {
-                    // If both evidence, FP wins
-                    modeNode.setMode((byte)((mode&2)==2 ? 2 : 1));
-                    code.add(n);
-                    code.addAll(n.outs());
-                }
+                modeNode.setMode((byte)((mode&2)==2 ? 2 : 1));
+                code.add(n);
+                code.addAll(n.outs());
             }
-            return null;
-        });
+        }
     }
 
     // Gather numeric evidence through Phi and interprocedural return cycles.
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 1ba57e85..f47a4fc6 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -114,7 +114,7 @@ public class FunNode extends RegionNode {
         }
 
         // Upgrade inferred or user-written return type to actual
-        if( _ret!=null && _ret._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) {
+        if( _ret!=null && addDep(_ret)._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) {
             setSig(_sig.makeFrom(tt.ret()));
             return this;
         }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 4d7e3ddb..6409ad21 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -2,7 +2,6 @@ package com.seaofnodes.simple.node;
 
 
 import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.Utils;
 import java.util.HashMap;
@@ -29,28 +28,27 @@ public class MinusNode extends Node implements ModeNode {
     @Override
     public Type compute() {
         Type t = in(1)._type;
+        // Constant array payloads lie below their element ranges in the lattice.
+        if( t instanceof TypeConAry ary ) t = ary.elem();
         if( t==null )
             return Type.TOP;
         if( t.isHigh() )
             return _mode==0 ? Type.TOP :
                 _mode==1 ? TypeInteger.TOP :
                 t instanceof TypeFloat ? t : TypeFloat.F64.dual();
-        byte mode = _mode;
-        if( mode==0 ) {
-            if( t instanceof TypeFloat   ) mode=2;
-            if( t instanceof TypeInteger ) mode=1;
-        }
-        if( mode==0 )
-            return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP;
-        if( mode==1 ) {
-            if( t instanceof TypeInteger i0 &&
-                i0._min != Long.MIN_VALUE && i0._max != Long.MIN_VALUE )
+        if( t instanceof TypeInteger i0 ) {
+            if( _mode==2 ) return TypeFloat.F64;
+            if( i0._min != Long.MIN_VALUE && i0._max != Long.MIN_VALUE )
                 return TypeInteger.make(-i0._max,-i0._min,i0._widen);
             return TypeInteger.BOT;
         }
-        if( t instanceof TypeFloat f )
+        if( t instanceof TypeFloat f ) {
+            if( _mode==1 ) return TypeInteger.BOT;
             return f.isConstant() ? TypeFloat.constant(-f.value()) : f;
-        return TypeFloat.F64;
+        }
+        // No numeric family is known. This must be below both integer and
+        // float results, in either analysis direction and with any mode.
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java
index 230593a8..77b1dd35 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -557,6 +557,8 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
     // probed to see if it can be inserted.  His edges are "locked", because
     // hacking his edges will change his hash.
     int _hash;
+    // Edge and mode edits remove the node from GVN, even if its type is unchanged.
+    public boolean isUnlocked() { return _hash==0; }
 
     // If the _hash is set, then the Node is in the GVN table; remove it.
     void unlock() {
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/MinusNodeTest.java b/chapter25/src/test/java/com/seaofnodes/simple/MinusNodeTest.java
new file mode 100644
index 00000000..497546df
--- /dev/null
+++ b/chapter25/src/test/java/com/seaofnodes/simple/MinusNodeTest.java
@@ -0,0 +1,73 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.node.ConstantNode;
+import com.seaofnodes.simple.node.MinusNode;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.type.*;
+import java.util.ArrayList;
+import java.util.Arrays;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class MinusNodeTest {
+    @Test public void testMonotoneCompute() {
+        CodeGen code = new CodeGen("return 0;");
+        // Type.gather also loads cached fixtures which do not survive later compiler resets.
+        ArrayList<Type> inputs = new ArrayList<>(Arrays.asList(
+            Type.BOTTOM,Type.CONTROL,Type.NIL,TypeScalar.BOT,TypePtr.PTR,
+            TypeMemPtr.BOT,TypeFunPtr.BOT,TypeMem.BOT,
+            TypeConAryB.make(new byte[]{1,2,3})));
+        TypeInteger.gather(inputs);
+        TypeFloat.gather(inputs);
+        int size = inputs.size();
+        for( int i=0; i<size; i++ ) inputs.add(inputs.get(i).dual());
+        for( long value : new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-1,1,Long.MAX_VALUE} )
+            inputs.add(TypeInteger.constant(value));
+        for( double value : new double[]{-0.0,0.0,-1.0,1.0,Double.NaN,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY} )
+            inputs.add(TypeFloat.constant(value));
+        Type[][] expected = new Type[3][inputs.size()];
+        for( CodeGen.Phase phase : new CodeGen.Phase[]{CodeGen.Phase.Parse,CodeGen.Phase.Iter,CodeGen.Phase.Opto,CodeGen.Phase.IterPostOpto} ) {
+            code.driver(phase);
+            for( byte mode=0; mode<3; mode++ ) {
+                // An isolated analysis input: vary its type without peepholes
+                // selecting a mode or folding the node under test.
+                Node input = new ConstantNode(Type.BOTTOM);
+                input.setDef(0,null);
+                MinusNode minus = new MinusNode(input,mode);
+                Type[] results = new Type[inputs.size()];
+                for( int i=0; i<inputs.size(); i++ ) {
+                    input._type = inputs.get(i);
+                    results[i] = minus.compute();
+                    if( phase==CodeGen.Phase.Parse ) expected[mode][i] = results[i];
+                    else assertSame("Phase changed compute",expected[mode][i],results[i]);
+                }
+                // The same order relation covers both falling SCCP types
+                // and rising Iter types, including crossing numeric families.
+                for( int i=0; i<inputs.size(); i++ )
+                    for( int j=0; j<inputs.size(); j++ )
+                        if( inputs.get(i).isa(inputs.get(j)) )
+                            assertTrue("mode="+mode+": "+inputs.get(i)+" -> "+inputs.get(j)+
+                                       " gave "+results[i]+" -> "+results[j],results[i].isa(results[j]));
+            }
+        }
+    }
+
+    @Test public void testUnresolvedInput() {
+        new CodeGen("return 0;").driver(CodeGen.Phase.Opto);
+        Node input = new ConstantNode(TypeInteger.TRUE);
+        MinusNode minus = new MinusNode(input);
+        assertSame(TypeInteger.constant(-1),minus.compute());
+        input._type = Type.BOTTOM;
+        assertSame(Type.BOTTOM,minus.compute());
+        minus.setMode((byte)1);
+        assertSame(Type.BOTTOM,minus.compute());
+    }
+
+    @Test public void testRecursiveFloat() {
+        CodeGen code = new CodeGen("val _neg = { int x -> x ? -_neg(x-1) : 1.0; }; return _neg(arg);")
+            .driver(CodeGen.Phase.TypeCheck);
+        for( int i=0; i<4; i++ )
+            assertEquals((i&1)==0 ? "1.0" : "-1.0",Eval2.eval(code,i));
+    }
+}