Much more robust guarded expression upcasting

Region does not print id, making all test cases much more stable (and slightly weaker).
NotNode gets more precise compute

5 files changed, 129 insertions, 63 deletions

diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
index 371bddf1..799e0629 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
@@ -2,7 +2,6 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
-import static com.seaofnodes.simple.Utils.TODO;
 
 import java.util.*;
 
@@ -91,7 +90,7 @@ public class Parser {
     public final Stack<ScopeNode> _xScopes = new Stack<>();
 
     ScopeNode _continueScope;
-    ScopeNode _breakScope;
+    ScopeNode _breakScope;      // Merge all the while-breaks here
 
     // Mapping from a type name to a Type.  The string name matches
     // `type.str()` call.  No TypeMemPtrs are in here, because Simple does not
@@ -169,7 +168,7 @@ public class Parser {
 
         if( ctrl()._type==Type.CONTROL )
             STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole());
-        _scope.pop();
+        _scope.kill();
         _xScopes.pop();
         for( StructNode init : INITS.values() )
             init.unkeep().kill();
@@ -269,7 +268,7 @@ public class Parser {
         // the loop predicate.  Note that body Scope is still our current scope.
         ctrl(ifF);
         _xScopes.push(_breakScope = _scope.dup());
-        _breakScope.upcast(ifF,pred,true); // Up-cast predicate
+        _breakScope.addGuards(ifF,pred,true); // Up-cast predicate
 
         // No continues yet
         _continueScope = null;
@@ -277,8 +276,9 @@ public class Parser {
         // Parse the true side, which corresponds to loop body
         // Our current scope is the body Scope
         ctrl(ifT.unkeep());     // set ctrl token to ifTrue projection
-        _scope.upcast(ifT,pred,false); // Up-cast predicate
+        _scope.addGuards(ifT,pred,false); // Up-cast predicate
         parseStatement();       // Parse loop body
+        _scope.removeGuards(ifT);
 
         // Merge the loop bottom into other continue statements
         if (_continueScope != null) {
@@ -330,8 +330,17 @@ public class Parser {
 
     private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); }
 
-    private Node parseBreak   () { checkLoopActive(); return (   _breakScope = require(jumpTo(    _breakScope ),";"));  }
     private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";"));  }
+    private Node parseBreak   () {
+        checkLoopActive();
+        // At the time of the break, and loop-exit conditions are only valid if
+        // they are ALSO valid at the break.  It is the intersection of
+        // conditions here, not the union.
+        _breakScope.removeGuards(_breakScope.ctrl());
+        _breakScope = require(jumpTo(_breakScope ),";");
+        _breakScope.addGuards(_breakScope.ctrl(), null, false);
+        return _breakScope;
+    }
 
     /**
      * Parses a statement
@@ -365,8 +374,10 @@ public class Parser {
 
         // Parse the true side
         ctrl(ifT.unkeep());     // set ctrl token to ifTrue projection
-        _scope.upcast(ifT,pred,false); // Up-cast predicate
+        _scope.addGuards(ifT,pred,false); // Up-cast predicate
         Node lhs = stmt ? parseStatement() : parseExpression().keep(); // Parse true-side
+        _scope.removeGuards(ifT);
+
         ScopeNode tScope = _scope;
 
         // Parse the false side
@@ -374,11 +385,12 @@ public class Parser {
         ctrl(ifF.unkeep());     // Ctrl token is now set to ifFalse projection
         // Up-cast predicate, even if not else clause, because predicate can
         // remain true if the true clause exits: `if( !ptr ) return 0; return ptr.fld;`
-        _scope.upcast(ifF,pred,true);
+        _scope.addGuards(ifF,pred,true);
         boolean doRHS = match(fside);
         Node rhs = doRHS
             ? (stmt ? parseStatement() : parseExpression())
             : (stmt ? null             : con(lhs._type.makeZero()));
+        _scope.removeGuards(ifF);
         if( doRHS )
             fScope = _scope;
         pred.unkeep();
@@ -392,7 +404,7 @@ public class Parser {
         _xScopes.pop();       // Discard pushed from graph display
 
         RegionNode r = ctrl(tScope.mergeScopes(fScope));
-        Node ret = stmt ? r : new PhiNode("",lhs._type.meet(rhs._type),r,lhs,rhs).peephole();
+        Node ret = stmt ? r : peep(new PhiNode("",lhs._type.meet(rhs._type),r,lhs,rhs));
         r.peephole();
         return ret;
     }
@@ -461,7 +473,7 @@ public class Parser {
 
         // Auto-widen int to float
         if( expr._type instanceof TypeInteger && t instanceof TypeFloat )
-            expr = new ToFloatNode(expr).peephole();
+            expr = peep(new ToFloatNode(expr));
         // Auto-narrow wide ints to narrow ints
         expr = zsMask(expr,t);
         // Auto-deepen forward ref types
@@ -653,7 +665,7 @@ public class Parser {
             else if( match("^") ) lhs = new XorNode(lhs,null);
             else break;
             lhs.setDef(2,parseComparison());
-            lhs = lhs.peephole();
+            lhs = peep(lhs);
         }
         return lhs;
     }
@@ -681,9 +693,9 @@ public class Parser {
             else break;
             // Peepholes can fire, but lhs is already "hooked", kept alive
             lhs.setDef(idx,parseShift());
-            lhs = lhs.widen().peephole();
+            lhs = peep(lhs.widen());
             if( negate )        // Extra negate for !=
-                lhs = new NotNode(lhs).peephole();
+                lhs = peep(new NotNode(lhs));
         }
         return lhs;
     }
@@ -705,7 +717,7 @@ public class Parser {
             else if( match(">>") ) lhs = new SarNode(lhs,null);
             else break;
             lhs.setDef(2,parseAddition());
-            lhs = lhs.widen().peephole();
+            lhs = peep(lhs.widen());
         }
         return lhs;
     }
@@ -726,7 +738,7 @@ public class Parser {
             else if( match("-") ) lhs = new SubNode(lhs,null);
             else break;
             lhs.setDef(2,parseMultiplication());
-            lhs = lhs.widen().peephole();
+            lhs = peep(lhs.widen());
         }
         return lhs;
     }
@@ -747,7 +759,7 @@ public class Parser {
             else if( match("/") ) lhs = new DivNode(lhs,null);
             else break;
             lhs.setDef(2,parseUnary());
-            lhs = lhs.widen().peephole();
+            lhs = peep(lhs.widen());
         }
         return lhs;
     }
@@ -761,8 +773,8 @@ public class Parser {
      * @return a unary expression {@link Node}, never {@code null}
      */
     private Node parseUnary() {
-        if (match("-")) return new MinusNode(parseUnary()).widen().peephole();
-        if (match("!")) return new   NotNode(parseUnary()).peephole();
+        if (match("-")) return peep(new MinusNode(parseUnary()).widen());
+        if (match("!")) return peep(new   NotNode(parseUnary()));
         return parsePostfix(parsePrimary());
     }
 
@@ -787,7 +799,7 @@ public class Parser {
         if( matchx("++") || matchx("--") ) {
             if( n._final )
                 throw error("Cannot reassign final '"+n._name+"'");
-            _scope.update(n,new AddNode(rvalue,con( _lexer.peek(-1)=='+' ? 1 : -1)).peephole());
+            _scope.update(n,peep(new AddNode(rvalue,con( _lexer.peek(-1)=='+' ? 1 : -1))));
         }
         return rvalue.unkeep();
     }
@@ -882,7 +894,7 @@ public class Parser {
     private Node newArray(TypeStruct ary, Node len) {
         int base = ary.aryBase ();
         int scale= ary.aryScale();
-        Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole();
+        Node size = peep(new AddNode(con(base),peep(new ShlNode(len,con(scale)))));
         ALTMP.clear();  ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit()));
         return newStruct(ary,size,0,ALTMP);
     }
@@ -935,7 +947,7 @@ public class Parser {
 
         Node off = (name.equals("[]")       // If field is an array body
             // Array index math
-            ? new AddNode(con(base.aryBase()),new ShlNode(require(parseExpression(),"]"),con(base.aryScale())).peephole()).peephole()
+            ? peep(new AddNode(con(base.aryBase()),peep(new ShlNode(require(parseExpression(),"]"),con(base.aryScale())))))
             // Struct field offsets are hardwired
             : con(base.offset(fidx))).keep();
 
@@ -958,20 +970,20 @@ public class Parser {
         // Structs don't need this; they only need a NPE check which is
         // done via the type system.
         if( base.isAry() ) load.setDef(0,ctrl());
-        load = load.peephole();
+        load = peep(load);
 
         // ary[idx]++
         if( matchx("++") || matchx("--") ) {
             if( f._final && !f._fname.equals("[]") )
                 throw error("Cannot reassign final '"+f._fname+"'");
-            Node inc = new AddNode(load,con( _lexer.peek(-1)=='+' ? 1 : -1)).peephole();
+            Node inc = peep(new AddNode(load,con( _lexer.peek(-1)=='+' ? 1 : -1)));
             Node val = zsMask(inc,f._type);
             Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false);
             // Arrays include control, as a proxy for a safety range check.
             // Structs don't need this; they only need a NPE check which is
             // done via the type system.
             if( base.isAry() )  st.setDef(0,ctrl());
-            memAlias(f._alias, st.peephole());
+            memAlias(f._alias, peep(st));
             // And use the original loaded value as the result
         }
         if( off.unkeep().isDead() ) off.kill();
@@ -987,16 +999,16 @@ public class Parser {
             if( !(val._type instanceof TypeFloat tval && t instanceof TypeFloat t0 && !tval.isa(t0)) )
                 return val;
             // Float rounding
-            return new RoundF32Node(val).peephole();
+            return peep(new RoundF32Node(val));
         }
         if( t0._min==0 )        // Unsigned
-            return new AndNode(val,con(t0._max)).peephole();
+            return peep(new AndNode(val,con(t0._max)));
         // Signed extension
         int shift = Long.numberOfLeadingZeros(t0._max)-1;
         Node shf = con(shift);
         if( shf._type==TypeInteger.ZERO )
             return val;
-        return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole();
+        return peep(new SarNode(peep(new ShlNode(val,shf.keep())),shf.unkeep()));
     }
 
 
@@ -1011,6 +1023,10 @@ public class Parser {
     private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); }
     public static Node con( long con ) { return con(TypeInteger.constant(con));  }
     public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole();  }
+    public Node peep( Node n ) {
+        // Peephole, then improve with lexically scoped guards
+        return _scope.upcastGuard(n.peephole());
+    }
 
     //////////////////////////////////
     // Utilities for lexical analysis
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java
index 35dbc19e..3827fdac 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -267,6 +267,10 @@ public abstract class Node implements OutNode {
     }
     // Test "keep" status
     public boolean iskeep() { return _outputs.find(null) != -1; }
+    public void unkill() {
+        if( unkeep().isUnused() )
+            kill();
+    }
 
 
     // Replace self with nnn in the graph, making 'this' go dead
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java
index ffd3e01e..664d7c7b 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java
@@ -28,15 +28,14 @@ public class NotNode extends Node {
             // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot
             // If input in null then true
             // If input is not null ptr then false
-            if( p0 == TypeMemPtr.TOP  )    return TypeInteger.TOP;
-            if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.constant(1);
-            if( !p0._nil )                 return TypeInteger.constant(0);
-            return TypeInteger.BOT;
+            if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.TRUE;
+            if( !p0._nil )                 return TypeInteger.FALSE;
+            return TypeInteger.BOOL;
         case Type t:
             if( t0.getClass() != Type.class )
                 // Only doing NOT on ints and ptrs
                 throw Utils.TODO();
-            return t0==Type.TOP ? Type.TOP : Type.BOTTOM;
+            return TypeInteger.BOOL;
         }
     }
 
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index a55bb479..9e0f46cb 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -18,7 +18,7 @@ public class RegionNode extends CFGNode {
 
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        return sb.append(label()).append(_nid);
+        return sb.append(label());
     }
 
     @Override public boolean isMultiHead() { return true; }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 2fc495c5..5a735515 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -32,12 +32,19 @@ public class ScopeNode extends ScopeMinNode {
     // True if parsing inside of a constructor
     public final Ary<Boolean> _inCons;
 
+    // Extra guards; tested predicates and casted results
+    private final Ary<Node> _guards;
+
     // A new ScopeNode
-    public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); _inCons = new Ary<>(Boolean.class); }
+    public ScopeNode() {
+        _vars   = new Ary<>(Var    .class);
+        _lexSize= new Ary<>(Integer.class);
+        _inCons = new Ary<>(Boolean.class);
+        _guards = new Ary<>(Node   .class);
+    }
 
     @Override public String label() { return "Scope"; }
 
-
     @Override
     StringBuilder _print1(StringBuilder sb, BitSet visited) {
         sb.append("Scope[ ");
@@ -187,9 +194,15 @@ public class ScopeNode extends ScopeMinNode {
         // 1) duplicate the name bindings of the ScopeNode across all stack levels
         // 2) Make the new ScopeNode a user of all the nodes bound
         // 3) Ensure that the order of defs is the same to allow easy merging
-        dup._vars.addAll(_vars);
+        dup._vars   .addAll(_vars   );
         dup._lexSize.addAll(_lexSize);
         dup._inCons .addAll(_inCons );
+        dup._guards .addAll(_guards );
+        // The dup'd guards all need dup'd keepers, to keep proper accounting
+        // when later removing all guards
+        for( Node n : _guards )
+            if( !(n instanceof CFGNode) )
+                n.keep();
         dup.addDef(ctrl());     // Control input is just copied
 
         // Memory input is a shallow copy
@@ -274,44 +287,78 @@ public class ScopeNode extends ScopeMinNode {
 
     // Up-casting: using the results of an If to improve a value.
     // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null.
-
-    // This Scope looks for direct variable uses, or certain simple
-    // combinations, and replaces the variable with the upcast variant.
-    public Node upcast( Node ctrl, Node pred, boolean invert ) {
-        if( ctrl._type == Type.XCONTROL || pred.isDead() )
-            return null; // Dead, do not do anything
+    public void addGuards( Node ctrl, Node pred, boolean invert ) {
+        assert ctrl instanceof CFGNode;
+        _guards.add(ctrl);      // Marker to distinguish 0,1,2 guards
+        // add pred & its cast to the normal input list, with special Vars
+        if( ctrl._type == Type.XCONTROL || pred==null || pred.isDead() )
+            return;           // Dead, do not add any guards
         // Invert the If conditional
         if( invert )
             pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole());
-
-        // Direct use of a value as predicate.  This is a zero/null test.
-        if( _inputs.find(pred) != -1 ) {
-            if( !(pred._type instanceof TypeMemPtr tmp) )
-                // Must be an `int`, since int and ptr are the only two value types
-                // being tested. No representation for a generic not-null int, so no upcast.
-                return null;
-            if( tmp.isa(TypeMemPtr.VOIDPTR) )
-                return null;    // Already not-null, no reason to upcast
-            // Upcast the ptr to not-null ptr, and replace in scope
-            return replace(pred,new CastNode(TypeMemPtr.VOIDPTR,ctrl,pred).peephole());
+        // This is a zero/null test.
+        // Compute the positive test type.
+        Type tnz   = pred._type.nonZero();
+        Type tcast = tnz.join(pred._type);
+        if( tcast != pred._type ) {
+            Node cast = new CastNode(tnz,ctrl,pred.keep()).peephole().keep();
+            _guards.add(pred);
+            _guards.add(cast);
+            replace(pred,cast);
         }
 
+        // Compute the negative test type.
         if( pred instanceof NotNode not ) {
-            // Direct use of a !value as predicate.  This is a zero/null test.
-            if( _inputs.find(not.in(1)) != -1 ) {
-                Type tinit = not.in(1)._type.makeInit();
-                if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast
-                return replace(not.in(1), new ConstantNode(tinit).peephole());
+            Node npred = not.in(1);
+            Type tzero = npred._type.makeZero();
+            Type tzcast= tzero.join(npred._type);
+            if( tzcast != npred._type ) {
+                Node cast = new CastNode(tzero,ctrl,npred.keep()).peephole().keep();
+                _guards.add(npred);
+                _guards.add( cast);
+                replace(npred,cast);
             }
         }
-        // Apr/9/2024: Attempted to replace X with Y if guarded by a test of
-        // X==Y.  This didn't seem to help very much, or at least in the test
-        // cases seen so far was a very minor help.
+    }
 
-        // No upcast
-        return null;
+    // Remove matching pred/cast pairs from this guarded region.
+    public void removeGuards( Node ctrl ) {
+        assert ctrl instanceof CFGNode;
+        // 0,1 or 2 guards
+        while( true ) {
+            Node g = _guards.pop();
+            if( g == ctrl ) break;
+            if( g instanceof CFGNode ) continue;
+            g            .unkill(); // Pop/kill cast
+            _guards.pop().unkill(); // Pop/kill pred
+        }
     }
 
+    // If we find a guarded instance of pred, replace with the upcasted version
+    public Node upcastGuard( Node pred ) {
+        // If finding an instanceof pred, replace with cast.
+        // Otherwise, just pred itself.
+        int i = _guards._len;
+        while( i > 0 ) {
+            Node  cast = _guards.at(--i);
+            if( cast instanceof CFGNode ) continue; // Marker between guard sets
+            Node xpred = _guards.at(--i);
+            if( xpred == pred )
+                return cast;
+        }
+        return pred;
+    }
+
+    // Kill guards also
+    @Override public void kill() {
+        for( Node n : _guards )
+            if( !(n instanceof CFGNode) )
+                n.unkill();
+        _guards.clear();
+        super.kill();
+    }
+
+
     private Node replace( Node old, Node cast ) {
         assert old!=null && old!=cast;
         for( int i=0; i<nIns(); i++ )