From a5fb3fb98c67ff0d2803ba7b6c0cd9933e7d7001 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Tue, 1 Oct 2024 16:37:14 -0700
Subject: Sharpen null checks

Look for chances to sharpen checks of all kinds, especially null checks.
Not terribly cheap check, probably needs a O(n^2) check
Fix a bunch gold test result spelling.
---
 .../com/seaofnodes/simple/node/RegionNode.java     | 56 ++++++++++++++++++
 .../main/java/com/seaofnodes/simple/type/Type.java |  1 +
 .../com/seaofnodes/simple/type/TypeInteger.java    |  8 ++-
 .../com/seaofnodes/simple/type/TypeMemPtr.java     |  1 +
 .../java/com/seaofnodes/simple/Chapter15Test.java  | 69 +++++++++++++++++++---
 5 files changed, 127 insertions(+), 8 deletions(-)

(limited to 'chapter15/src')

diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index d5105614..0c7cd1e4 100644
--- a/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter15/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -72,9 +72,65 @@ public class RegionNode extends CFGNode {
             p1.in(0) instanceof IfNode iff )
             return iff.ctrl();
 
+
+
+        // Look for direct uses of a guarded expression, and replace with the guard result.
+        if( !(idom() instanceof StartNode) && // Dead or dying
+            !(this instanceof LoopNode) ) {
+            VISIT.clear();
+            boolean progress = false;
+            outer:
+            for( int i=1; i<nIns(); i++ ) {
+                CFGNode idom = cfg(i);
+                while( !(idom instanceof CProjNode cproj) ) {
+                    idom = idom.idom();
+                    if( idom==null || idom.idepth() < idom().idepth() )
+                        continue outer;
+                }
+                if( cproj.cfg0() instanceof IfNode iff && cproj.compute()==Type.CONTROL ) {
+                    VISIT.set(iff.pred()._nid);
+                    for( Node out : _outputs )
+                        if( out instanceof PhiNode phi )
+                            progress |= walk(iff,cproj,phi.in(i));
+                }
+            }
+            if( progress )
+                return this;
+        }
+
         return null;
     }
 
+    // A walk that can be cutoff early
+    private static final BitSet VISIT = new BitSet();
+    private static boolean walk( IfNode iff, CProjNode cproj, Node n ) {
+        if( VISIT.get(n._nid) ) return false;
+        VISIT.set(n._nid);
+        if( n instanceof CFGNode ) return false;
+        if( n.in(0)!=null && n.cfg0().idepth() < iff.idepth() )
+            return false;
+        boolean progress = false;
+        Node pred = iff.pred();
+        for( int i=1; i<n.nIns(); i++ ) {
+            // Using a tested value
+            if( n.in(i) == pred && !(n instanceof CastNode) ) {
+                // Checking pred for T/F
+                Type t = pred._type;
+                Type tcast = cproj._idx==0 ? t.nonZero() : t.makeInit();
+                if( t!=tcast ) { // Progress to cast
+                    Node cast = new CastNode( tcast, cproj, pred ).peephole();
+                    n.setDef( i, cast );
+                    IterPeeps.add(n);
+                    progress = true;
+                }
+            }
+            if( n.in(i)!=null )
+                progress |= walk(iff,cproj,n.in(i));
+        }
+        return progress;
+    }
+
+
     private int findDeadInput() {
         for( int i=1; i<nIns(); i++ )
             if( in(i)._type==Type.XCONTROL )
diff --git a/chapter15/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter15/src/main/java/com/seaofnodes/simple/type/Type.java
index 983fcf98..989eff9e 100644
--- a/chapter15/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter15/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 nonZero() { return glb(); }
 
     // ----------------------------------------------------------
 
diff --git a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index fca3362e..042b4ba8 100644
--- a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -113,8 +113,14 @@ public class TypeInteger extends Type {
     }
 
     @Override public TypeInteger dual() { return make(_max,_min); }
-    @Override public Type glb() { return BOT; }
+    @Override public TypeInteger glb() { return BOT; }
     @Override public TypeInteger makeInit() { return ZERO; }
+    @Override public TypeInteger nonZero() {
+        if( isHigh() ) return this;
+        if( _min==0 ) return make(1,_max); // specifically good on BOOL
+        if( _max==0 ) return make(_min,-1);
+        return this;
+    }
     @Override int hash() { return (int)((_min ^ (_min>>32)) *(_max ^ (_max>>32))); }
     @Override
     public boolean eq( Type t ) {
diff --git a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
index 7743c80d..8b484235 100644
--- a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
+++ b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java
@@ -58,6 +58,7 @@ public class TypeMemPtr extends Type {
     @Override
     public TypeMemPtr glb() { return make(_obj.glb(),true); }
     @Override public TypeMemPtr makeInit() { return NULLPTR; }
+    @Override public Type nonZero() { return VOIDPTR; }
 
     @Override public boolean isHigh() { return this==TOP; }
 
diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index 62e865aa..ad3c6b3f 100644
--- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
@@ -22,7 +22,7 @@ return 3.14;
     }
 
     @Test
-    public void testBasic() {
+    public void testBasic1() {
         Parser parser = new Parser(
 """
 int[] is = new int[2];
@@ -65,12 +65,67 @@ return a[0];
         Parser parser = new Parser(
 """
 struct A { int i; }
-A[] a = new A[2];
+A?[] a = new A?[2];
 return a;
 """);
         StopNode stop = parser.parse(false).iterate(false);
-        assertEquals("return A[];", stop.toString());
-        assertEquals("Obj<A[]> {\n  #=2\n  []=null\n}", Evaluator.evaluate(stop, 0).toString());
+        assertEquals("return *A?[];", stop.toString());
+        assertEquals("Obj<*A?[]> {\n  #=2\n  []=null\n}", Evaluator.evaluate(stop, 0).toString());
+    }
+
+    @Test
+    public void testBasic5() {
+        Parser parser = new Parser(
+"""
+struct S { int x; flt y; }
+// A new S
+S s = new S; s.x=99; s.y = 3.14;
+
+// Double-d array of Ss.  Fill in one row.
+S?[]?[] iss = new S?[]?[2];
+iss[0] = new S?[7];
+iss[0][2] = s;
+
+// Now pull out the filled-in value, with null checks
+flt rez;
+S?[]? is = iss[arg];
+if( !is ) rez = 1.2;
+else {
+    S? i = is[2];
+    if( !i ) rez = 2.3;
+    else rez = i.y;
+}
+return rez;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Region118,1.2,Phi(Region115,2.3,.y));", stop.toString());
+        assertEquals(3.14, Evaluator.evaluate(stop, 0));
+    }
+
+    @Ignore
+    @Test
+    public void testBasic6() {
+        Parser parser = new Parser(
+"""
+struct S { int x; flt y; }
+// A new S
+S s = new S; s.x=99; s.y = 3.14;
+
+// Double-d array of Ss.  Fill in one row.
+S?[]?[] iss = new S?[]?[2];
+iss[0] = new S?[7];
+iss[0][2] = s;
+
+// Now pull out the filled-in value, with null checks
+flt rez = 1.2;
+if( iss[arg] )
+    if( iss[arg][2] )
+        rez = iss[arg][2].y;
+return rez;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Phi(Region122,Phi(Region118,.y,1.2),1.2);", stop.toString());
+        assertEquals(3.14, Evaluator.evaluate(stop, 0));
     }
 
     @Test
@@ -78,15 +133,15 @@ return a;
         Parser parser = new Parser(
 """
 // Can we define a forward-reference array?
-struct Tree { Tree[] _kids; }
+struct Tree { Tree?[] _kids; }
 Tree root = new Tree;
-root._kids = new Tree[2];
+root._kids = new Tree?[2];
 root._kids[0] = new Tree;
 return root;
 """);
         StopNode stop = parser.parse(false).iterate(false);
         assertEquals("return Tree;", stop.toString());
-        assertEquals("Obj<Tree> {\n  _kids=Obj<Tree[]> {\n  #=2\n  []=Obj<Tree> {\n  _kids=null\n}\n}\n}", Evaluator.evaluate(stop,  0).toString());
+        assertEquals("Obj<Tree> {\n  _kids=Obj<*Tree?[]> {\n  #=2\n  []=Obj<Tree> {\n  _kids=null\n}\n}\n}", Evaluator.evaluate(stop,  0).toString());
     }
 
 
-- 
cgit v1.2.3