Change field mutability

Fields & locals with an initializer are immutable by default; those without are mutable.  Make mutable with `!`.  Fields are always mutable in a constructor.
Add a trinary `pred ? then : else` syntax.
SubNode retains as much precision as AddNode.
Sharpen some asserts and error cases.
Limit Load node cloning if the ptr is not obvious.

12 files changed, 125 insertions, 69 deletions

diff --git a/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java
index 96ae350e..81b89513 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.Type;
 
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -113,9 +114,12 @@ public abstract class IterPeeps {
         MID_ASSERT = true;
         int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT;
         Node changed = stop.walk( n -> {
-                if( WORK.on(n) ) return null;
-                Node m = n.peepholeOpt();
-                if( m==null ) return null;
+                Node m = n;
+                if( n.compute().isa(n._type) ) { // Types must be forwards, even if on worklist
+                    if( WORK.on(n) ) return null;
+                    m = n.peepholeOpt();
+                    if( m==null ) return null;
+                }
                 System.err.println("BREAK HERE FOR BUG");
                 return m;
             });
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
index fac012a4..371bddf1 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java
@@ -150,7 +150,7 @@ public class Parser {
     public static Node find(int nid) { return START.find(nid); }
 
     private Node ctrl() { return _scope.ctrl(); }
-    private Node ctrl(Node n) { return _scope.ctrl(n); }
+    private <N extends Node> N ctrl(N n) { return _scope.ctrl(n); }
 
     public StopNode parse() { return parse(false); }
     public StopNode parse(boolean show) {
@@ -165,7 +165,7 @@ public class Parser {
         _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, new  ProjNode(START, 2, ScopeNode.ARG0).peephole());
 
         // Parse whole program
-        parseBlock();
+        parseBlock(false);
 
         if( ctrl()._type==Type.CONTROL )
             STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole());
@@ -189,9 +189,9 @@ public class Parser {
      * Does not parse the opening or closing '{}'
      * @return a {@link Node} or {@code null}
      */
-    private Node parseBlock() {
+    private Node parseBlock(boolean inCon) {
         // Enter a new scope
-        _scope.push();
+        _scope.push(inCon);
         while (!peek('}') && !_lexer.isEOF())
             parseStatement();
         // Exit scope
@@ -210,7 +210,7 @@ public class Parser {
     private Node parseStatement() {
         if( false ) return null;
         else if (matchx("return")  ) return parseReturn();
-        else if (match ("{")       ) return require(parseBlock(),"}");
+        else if (match ("{")       ) return require(parseBlock(false),"}");
         else if (matchx("if")      ) return parseIf();
         else if (matchx("while")   ) return parseWhile();
         else if (matchx("break")   ) return parseBreak();
@@ -324,7 +324,7 @@ public class Parser {
             return cur;
         // toScope is either the break scope, or a scope that was created here
         assert toScope._lexSize.size() <= _breakScope._lexSize.size();
-        toScope.ctrl(toScope.mergeScopes(cur));
+        toScope.ctrl(toScope.mergeScopes(cur).peephole());
         return toScope;
     }
 
@@ -342,9 +342,16 @@ public class Parser {
      * @return a {@link Node}, never {@code null}
      */
     private Node parseIf() {
-        require("(");
         // Parse predicate
-        var pred = require(parseExpression(), ")").keep();
+        require("(");
+        var pred = require(parseExpression(), ")");
+        return parseTrinary(pred,true,"else");
+    }
+
+    // Parse a conditional expression, merging results.
+    private Node parseTrinary( Node pred, boolean stmt, String fside ) {
+        pred.keep();
+
         // IfNode takes current control and predicate
         Node ifNode = new IfNode(ctrl(), pred).peephole();
         // Setup projection nodes
@@ -359,19 +366,24 @@ public class Parser {
         // Parse the true side
         ctrl(ifT.unkeep());     // set ctrl token to ifTrue projection
         _scope.upcast(ifT,pred,false); // Up-cast predicate
-        parseStatement();       // Parse true-side
+        Node lhs = stmt ? parseStatement() : parseExpression().keep(); // Parse true-side
         ScopeNode tScope = _scope;
 
         // Parse the false side
         _scope = fScope;        // Restore scope, then parse else block if any
         ctrl(ifF.unkeep());     // Ctrl token is now set to ifFalse projection
-        _scope.upcast(ifF,pred,true); // Up-cast predicate
-        if (matchx("else")) {
-            parseStatement();
+        // 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);
+        boolean doRHS = match(fside);
+        Node rhs = doRHS
+            ? (stmt ? parseStatement() : parseExpression())
+            : (stmt ? null             : con(lhs._type.makeZero()));
+        if( doRHS )
             fScope = _scope;
-        }
         pred.unkeep();
 
+        // Check for `if(pred) int x=17;`
         if( tScope.nIns() != ndefs || fScope.nIns() != ndefs )
             throw error("Cannot define a new name on one arm of an if");
 
@@ -379,10 +391,12 @@ public class Parser {
         _scope = tScope;
         _xScopes.pop();       // Discard pushed from graph display
 
-        return ctrl(tScope.mergeScopes(fScope));
+        RegionNode r = ctrl(tScope.mergeScopes(fScope));
+        Node ret = stmt ? r : new PhiNode("",lhs._type.meet(rhs._type),r,lhs,rhs).peephole();
+        r.peephole();
+        return ret;
     }
 
-
     /**
      * Parses a return statement; "return" already parsed.
      * The $ctrl edge is killed.
@@ -410,42 +424,39 @@ public class Parser {
 
     /** Parse: name [=expr]
      */
-    private Node parseAsgn(Type t, boolean xfinal) {
-        boolean isDecl = t!=null; // Having a type is a declaration, missing one is updating a prior name
+    // t==null          ==>> re-assign: !final, expr=parse(), t:=def ._type
+    // t==TOP           ==>> value    :  final, expr=parse(), t:=expr._type
+    // t==BOT           ==>> variable : !final, expr=parse(), t:=expr._type
+    // t==type && !expr ==>> declaratn: !final, expr=makeInit; t:=type;
+    // t==type &&  expr ==>> declaratn:  final=inCon && noBang, expr=parse() ; t:=type;
+    private Node parseAsgn(Type t, boolean hasBang) {
+        boolean isDecl = t!=null;
         int old = _lexer._position;
         String name = requireId();
-        Node expr;
-        if( peek(';') || peek(',') ) {
-            // Bare "name" is not allowed
-            if( t==null ) throw errorSyntax("expression");
-            // Does this declaration need an initializer and not getting one?
-            Type init = xfinal || t instanceof TypeMemPtr tmp && !tmp._nil
-                // Must be initialized in the "new" constructor
-                ? Type.TOP
-                // Else takes the default
-                : t.makeInit();
-            // "var" and "val" require an expression to infer
-            if( init == null ) throw errorSyntax("expression");
-            expr = con(init);
-
-        } else if( !match("=") ) {     // Something else
-            _lexer._position = old;
-            return null;
-        } else
-            expr = parseExpression();
+
+        boolean hasType = t!=null && t!=Type.TOP && t!=Type.BOTTOM; // User written type
+        boolean hasExpr = !(peek(';') || peek(','));   // Expression follows
+        if( hasExpr && !match("=") )                   // Something else
+            { _lexer._position = old;  return null; }
+        if( !hasExpr && t==Type.BOTTOM )  throw errorSyntax("expression");
+        Node expr = hasExpr ? parseExpression() : con(t.makeInit());
+        boolean xfinal = t==Type.TOP || (hasType && hasExpr && !hasBang && _scope.inCon());
 
         // Defining a new variable vs updating an old one
-        if( !isDecl ) { // Assigning over an existing name
-            // Lookup
+        if( t==null ) {
+            // Lookup old variable
             ScopeMinNode.Var def = _scope.lookup(name);
             if( def==null )
                 throw error("Undefined name '" + name + "'");
             // TOP fields are for late-initialized fields; these have never
             // been written to, and this must be the final write.  Other writes
-            // need to check the final bit.
-            if( _scope.in(def._idx)._type!=Type.TOP && def._final )
+            // outside the constructor need to check the final bit.
+            if( _scope.in(def._idx)._type!=Type.TOP && def._final && !_scope.inCon() )
                 throw error("Cannot reassign final '"+name+"'");
             t = def.type(); // Declared field type
+        } else if( !hasType && hasExpr ) {
+            // Discovered type from expression
+            t = expr._type.glb();
         }
 
         // Auto-widen int to float
@@ -475,10 +486,7 @@ public class Parser {
     /** Parse final: [!]asgn
      */
     private Node parseFinal(Type t) {
-        // TOP is a "val" marker - uses type inference for a "value", i.e. a final.
-        // BOT is a "var" marker - uses type inference for a "variable", i.e. not final
-        boolean xfinal = t==Type.TOP || (t!=null && match("!"));
-        return parseAsgn(t,xfinal);
+        return parseAsgn(t,match("!"));
     }
 
     /**
@@ -526,7 +534,7 @@ public class Parser {
             throw errorSyntax("struct '" + typeName + "' cannot be redefined");
 
         // A Block scope parse, and inspect the scope afterward for fields.
-        _scope.push();
+        _scope.push(true);
         require("{");
         while (!peek('}') && !_lexer.isEOF())
             parseStatement();
@@ -562,6 +570,9 @@ public class Parser {
         if( tname==null ) return null;
         // Convert the type name to a type.
         Type t0 = TYPES.get(tname);
+        // No new types as keywords
+        if( t0 == null && KEYWORDS.contains(tname) )
+          { _lexer._position = old1; return null; }
         Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) : t0; // Null: assume a forward ref type
         // Nest arrays and '?' as needed
         while( true ) {
@@ -616,11 +627,14 @@ public class Parser {
      * Parse an expression of the form:
      *
      * <pre>
-     *     expr : compareExpr
+     *     expr : bitwise [? expr [: expr]]
      * </pre>
      * @return an expression {@link Node}, never {@code null}
      */
-    private Node parseExpression() { return parseBitwise(); }
+    private Node parseExpression() {
+        Node expr = parseBitwise();
+        return match("?") ? parseTrinary(expr,false,":") : expr;
+    }
 
     /**
      * Parse an bitwise expression
@@ -823,7 +837,7 @@ public class Parser {
             for( int i=0; i<fs.length; i++ )
                 _scope.define(fs[i]._fname, fs[i]._type, fs[i]._final, s.in(i));
             // Parse the constructor body
-            parseBlock();
+            parseBlock(true);
             require("}");
             init = _scope._inputs;
         }
@@ -948,6 +962,8 @@ public class Parser {
 
         // 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 val = zsMask(inc,f._type);
             Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false);
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java
index f3b213fb..0834a381 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -36,7 +36,7 @@ public class AddNode extends Node {
         return TypeInteger.BOT;
     }
 
-    private static boolean overflow( long x, long y ) {
+    static boolean overflow( long x, long y ) {
         if( (x ^    y ) < 0 ) return false; // unequal signs, never overflow
         return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow
     }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index 9e9d6970..3513f265 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -28,15 +28,6 @@ public abstract class CFGNode extends Node {
     // Block head is Start, Region, CProj, but not e.g. If, Return, Stop
     public boolean blockHead() { return false; }
 
-    // Should be exactly 1 tail from a block head
-    public CFGNode blockTail() {
-        assert blockHead();
-        for( Node n : _outputs )
-            if( n instanceof CFGNode cfg )
-                return cfg;
-        return null;
-    }
-
     // ------------------------------------------------------------------------
     /**
      * Immediate dominator tree depth, used to approximate a real IDOM during
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 2c0afda2..555b9ae4 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -87,6 +87,8 @@ public class LoadNode extends MemOpNode {
                         break outer; // Cannot tell, ptr not related to New
                     mem = nnn1.in(_alias);// Bypass unrelated New
                     break;
+                } else if( mproj.in(0) instanceof StartNode ) {
+                    break outer;
                 } else throw Utils.TODO();
             default:
                 throw Utils.TODO();
@@ -101,7 +103,11 @@ public class LoadNode extends MemOpNode {
         //   else       ptr.x = e1;                    : e1;
         //   val = ptr.x;                   ptr.x = val;
         if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 &&
-            off() instanceof ConstantNode ) {
+            // Offset can be hoisted
+            off() instanceof ConstantNode &&
+            // Pointer can be hoisted
+            hoistPtr(ptr,memphi)  ) {
+
             // Profit on RHS/Loop backedge
             if( profit(memphi,2) ||
                 // Else must not be a loop to count profit on LHS.
@@ -125,6 +131,25 @@ public class LoadNode extends MemOpNode {
             ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode;
     }
 
+    private static boolean hoistPtr(Node ptr, PhiNode memphi ) {
+        // Can I hoist ptr above the Region?
+        if( !(memphi.region() instanceof RegionNode r) )
+            return false;       // Dead or dying Region/Phi
+        // If ptr from same Region, then yes, just use hoisted split pointers
+        if( ptr instanceof PhiNode pphi && pphi.region() == r )
+            return true;
+
+        // No, so can we lift this ptr?
+        CFGNode cptr = ptr.cfg0();
+        if( cptr != null )
+            // Pointer is controlled high
+            // TODO: Really needs to be the LCA of all inputs is high
+            return cptr.idepth() <= r.idepth();
+
+        // Dunno without a longer walk
+        return false;
+    }
+
     // Profitable if we find a matching Store on this Phi arm.
     private boolean profit(PhiNode phi, int idx) {
         Node px = phi.in(idx);
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 c67fb910..35dbc19e 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -153,7 +153,7 @@ public abstract class Node implements OutNode {
      * @param new_def the new definition
      * @return new_def for flow coding
      */
-    public Node setDef(int idx, Node new_def ) {
+    public <N extends Node> N setDef(int idx, N new_def ) {
         unlock();
         Node old_def = in(idx);
         if( old_def == new_def ) return new_def; // No change
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 f7446c51..2fc495c5 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -29,9 +29,11 @@ public class ScopeNode extends ScopeMinNode {
     // Since of each nested lexical scope
     public final Ary<Integer> _lexSize;
 
+    // True if parsing inside of a constructor
+    public final Ary<Boolean> _inCons;
 
     // A new ScopeNode
-    public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); }
+    public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); _inCons = new Ary<>(Boolean.class); }
 
     @Override public String label() { return "Scope"; }
 
@@ -75,17 +77,24 @@ public class ScopeNode extends ScopeMinNode {
      *
      * @return Node that was bound
      */
-    public Node ctrl(Node n) { return setDef(0,n); }
+    public <N extends Node> N ctrl(N n) { return setDef(0,n); }
 
-    public void push() {
+    public void push() { push(false); }
+    public void push(boolean inCon) {
+        assert _lexSize._len==_inCons._len;
         _lexSize.push(_vars.size());
+        _inCons.push(inCon);
     }
     public void pop() {
+        assert _lexSize._len==_inCons._len;
         int n = _lexSize.pop();
+        _inCons.pop();
         popUntil(n);
         _vars.setLen(n);
     }
 
+    public boolean inCon() { return _inCons.last(); }
+
     // Find name in reverse, return an index into _vars or -1.  Linear scan
     // instead of hashtable, but probably doesn't matter until the scan
     // typically hits many dozens of variables.
@@ -180,6 +189,7 @@ public class ScopeNode extends ScopeMinNode {
         // 3) Ensure that the order of defs is the same to allow easy merging
         dup._vars.addAll(_vars);
         dup._lexSize.addAll(_lexSize);
+        dup._inCons .addAll(_inCons );
         dup.addDef(ctrl());     // Control input is just copied
 
         // Memory input is a shallow copy
@@ -208,13 +218,13 @@ public class ScopeNode extends ScopeMinNode {
      * @param that The ScopeNode to be merged into this
      * @return A new node representing the merge point
      */
-    public Node mergeScopes(ScopeNode that) {
+    public RegionNode mergeScopes(ScopeNode that) {
         RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep());
         mem()._merge(that.mem(),r);
         this ._merge(that      ,r);
         that.kill();            // Kill merged scope
         IterPeeps.add(r);
-        return r.unkeep().peephole();
+        return r.unkeep();
     }
 
     private void _merge(ScopeNode that, RegionNode r) {
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 009fb30e..5d6c2643 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -29,6 +29,11 @@ public class SubNode extends Node {
             t2 instanceof TypeInteger i2 ) {
             if (i1.isConstant() && i2.isConstant())
                 return TypeInteger.constant(i1.value()-i2.value());
+            // Fold ranges like {2-3} - {0-1} into {1-3}.
+            if( !AddNode.overflow(i1._min,-i2._max) &&
+                !AddNode.overflow(i1._max,-i2._min) &&
+                i2._min != Long.MIN_VALUE  )
+                return TypeInteger.make(i1._min-i2._max,i1._max-i2._min);
         }
         // Sub of same is 0
         if( in(1)==in(2) )
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java
index 7467be79..e454f48f 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -82,6 +82,7 @@ public class Type {
     public StringBuilder typeName( StringBuilder sb) { return print(sb); }
 
     public Type makeInit() { return null; }
+    public Type makeZero() { return null; }
     public Type nonZero() { return glb(); }
 
     // ----------------------------------------------------------
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
index dc36c082..37f6ce71 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java
@@ -108,6 +108,7 @@ public class TypeFloat extends Type {
     public Type glb() { return BOT; }
 
     @Override public TypeFloat makeInit() { return ZERO; }
+    @Override public TypeFloat makeZero() { return ZERO; }
 
     @Override
     int hash() { return (int)(Double.hashCode(_con) ^ _sz); }
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index b475055d..06848dc7 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -81,6 +81,7 @@ public class TypeInteger extends Type {
         if( this==I16 || this==U16              ) return 1; // 1<<1 == 2 bytes
         if( this==I32 || this==U32              ) return 2; // 1<<2 == 4 bytes
         if( this==BOT                           ) return 3; // 1<<3 == 8 bytes
+        if( isHighOrConst() ) return 0;
         throw Utils.TODO();
     }
 
@@ -115,6 +116,7 @@ public class TypeInteger extends Type {
     @Override public TypeInteger dual() { return make(_max,_min); }
     @Override public TypeInteger glb() { return BOT; }
     @Override public TypeInteger makeInit() { return ZERO; }
+    @Override public TypeInteger makeZero() { return ZERO; }
     @Override public TypeInteger nonZero() {
         if( isHigh() ) return this;
         if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
index 449bf89e..cc4b9fcd 100644
--- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
+++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
@@ -59,7 +59,8 @@ public class TypeMemPtr extends Type {
     public TypeMemPtr glb() { return make(_obj.glb(),true); }
     // Is forward-reference
     @Override public boolean isFRef() { return _obj.isFRef(); }
-    @Override public TypeMemPtr makeInit() { return NULLPTR; }
+    @Override public Type makeInit() { return _nil ? NULLPTR : Type.TOP; }
+    @Override public Type makeZero() { return NULLPTR; }
     @Override public Type nonZero() { return VOIDPTR; }
 
     @Override public boolean isHigh() { return this==TOP; }