bug fix widen

Failed lattice law tests mixing constants and have wide type ints; or mixing wide ints and constant arrays.

7 files changed, 77 insertions, 65 deletions

diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 09c55cde..a4c73472 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -85,10 +85,11 @@ public class PhiNode extends Node {
             }
         }
 
-        // phi loop widening part
+        // Above-center ranges may still fall to unwidened constants.
+        // Widen only below-center ranges to preserve monotonicity.
         if( r instanceof LoopNode && // Only around loops
             t instanceof TypeInteger ti && // Only widen integers
-            !ti.isConstant() ) {  // No need to widen constants
+            !ti.isHigh() && !ti.isConstant() ) {  // Only widen live ranges
             // Widen, to prevent infinite falling of TypeIntegers
             return ti.same_but_slightly_wider_than();
         }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java
index 39203a09..d1af6ca8 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -272,8 +272,8 @@ public class Type /*implements Cloneable*/ {
         if(   is_simple() ) return this.xmeet(t   );
         if( t.is_simple() ) return t   .xmeet(this);
         // TypeConAry meet its element type is OK
-        if( this instanceof TypeConAry tcon && tcon.elemT() == t._type ) return tcon.ymeet(t);
-        if( t    instanceof TypeConAry tcon && tcon.elemT() ==   _type ) return tcon.ymeet(this);
+        if( this instanceof TypeConAry tcon && t    instanceof TypeInteger ti ) return tcon.ymeet(ti);
+        if( t    instanceof TypeConAry tcon && this instanceof TypeInteger ti ) return tcon.ymeet(ti);
         // Two distinct scalar families meet at the scalar envelope.
         if( this instanceof TypeScalar scalar0 && t instanceof TypeScalar scalar1 )
             return scalar0.smeet(scalar1);
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java
index 29e65c94..c9093e3b 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java
@@ -1,6 +1,5 @@
 package com.seaofnodes.simple.type;
 
-import com.seaofnodes.simple.util.AryInt;
 import com.seaofnodes.simple.util.BAOS;
 import com.seaofnodes.simple.util.Utils;
 import java.util.ArrayList;
@@ -11,39 +10,48 @@ import java.util.HashMap;
  */
 public abstract class TypeConAry<A> extends TypeScalar {
     boolean _any;
-    // One of byte,short,int,long,float,double array
+    byte _widen;
+    // One of byte or int array
     public final A _ary;
 
-    TypeConAry( boolean any, A ary ) { super(TCONARY); _any = any; _ary = ary; }
+    TypeConAry( boolean any, byte widen, A ary ) { super(TCONARY); _any = any; _widen = widen; _ary = ary; }
     public static void gather(ArrayList<Type> ts) {
-        TypeConAryB.gather(ts);
-        TypeConAryI.gather(ts);
+        ts.add(TypeConAryB.ABC);
+        ts.add(TypeConAryB.ABCD);
+        ts.add(TypeConAryI.I123);
     }
+    // Fresh, uninterned type sharing this array; xdual must not intern.
+    abstract TypeConAry<A> _make(boolean any, byte widen);
 
-    @Override public String str() { return (_any?"~":"") + "[]"; }
-    @Override TypeConAry xdual() { return this; }
+    @Override TypeConAry<A> xdual() { return _make( !_any, (byte)(3-_widen) ); }
 
     @Override Type xmeet(Type t) {
         TypeConAry ary = (TypeConAry)t; // Invariant
-        assert _ary!=ary._ary;  // Already interned and this!=t
-        // Unrelated constant arrays
+        // Same base array but different?
+        if( _equals(ary) )
+            // Return array with larger widen
+            return _widen >= ary._widen ? this : ary;
+        // Unrelated constant arrays, falls to some int range
         return elem().meet(ary.elem());
     }
 
-    Type ymeet( Type t ) {
-        if( t instanceof TypeInteger ti ) {
-            // if i can isa *each* element, then maybe can keep.
-            // no good to i.isa(elem()) because fails the dual
-            boolean fail = false;
-            for( int j=0; j<len(); j++ )
-                if( !ti.isa(TypeInteger.constant(at8(j))) )
-                    { fail=true; break; }
-            Type e = elem();
-            if( fail )
-                return ti.meet(e);
-            return this;
-        }
-        throw Utils.TODO("Should not reach here: constant array meet with non-element type");
+    Type ymeet( TypeInteger ti ) {
+        // if i can isa *each* element, then maybe can keep.
+        // no good to i.isa(elem()) because fails the dual
+        for( int j=0; j<len(); j++ )
+            if( !ti.isa(TypeInteger.make(at8(j),at8(j),ti._widen)) )
+                return ti.meet(elem());
+        byte widen = (byte)Math.max(_widen,ti._widen);
+        return widen==_widen ? this : _make(_any,widen).intern();
+    }
+
+    private boolean _equals(TypeConAry ary) {
+        int len = len();
+        if( len != ary.len() ) return false;
+        for( int i=0; i<len; i++ )
+            if( at8(i) != ary.at8(i) )
+                return false;
+        return true;
     }
 
     @Override public boolean isHigh() { return this==TOP; }
@@ -61,13 +69,11 @@ public abstract class TypeConAry<A> extends TypeScalar {
             min = Math.min(min,at8(i));
             max = Math.max(max,at8(i));
         }
-        return TypeInteger.make(min,max);
+        return TypeInteger.make(min,max,_widen);
     }
-    // Generic element _type
-    public int elemT() { return TBOT; }
-    public long at8(int idx) { throw Utils.TODO("Should not reach here: abstract constant array has no elements"); }
-    public int len() { throw Utils.TODO("Should not reach here: abstract constant array has no length"); }
-    @Override public int log_size() { throw Utils.TODO("Should not reach here: abstract constant array has no element size"); }
+    public abstract long at8(int idx);
+    public abstract int len();
+    @Override public abstract int log_size();
     public void write( BAOS baos ) { throw Utils.TODO("Should not reach here: abstract constant array cannot be written"); }
 
     // Reserve tags for u8 array
@@ -81,14 +87,4 @@ public abstract class TypeConAry<A> extends TypeScalar {
     static TypeConAry packed( int tag, BAOS bais ) {
         return TypeConAryB.make(bais.read(new byte[bais.packed4()]));
     }
-
-    @Override boolean eq(Type t) {
-        return t instanceof TypeConAry ary && _any==ary._any && ary._ary==null;
-    }
-
-    @Override int hash() {
-        assert _ary==null;
-        return _any ? 1024 : 0;
-    }
-
 }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java
index bd2827ed..5877c309 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java
@@ -1,22 +1,20 @@
 package com.seaofnodes.simple.type;
 
 import com.seaofnodes.simple.util.BAOS;
-import java.util.ArrayList;
 import java.util.Arrays;
 
 public class TypeConAryB extends TypeConAry<byte[]> {
-    private TypeConAryB(byte[] bs) { super(false,bs); }
-    public static TypeConAryB make( byte[] bs ) { return new TypeConAryB(bs).intern(); }
+    private TypeConAryB(boolean any, byte widen, byte[] bs) { super(any,widen,bs); }
+    @Override TypeConAryB _make( boolean any, byte widen ) { return new TypeConAryB(any,widen,_ary); }
+    public static TypeConAryB make( byte[] bs ) { return new TypeConAryB(false,(byte)0,bs).intern(); }
     public static TypeConAryB make( String s ) { return make(s.getBytes()); }
     static final TypeConAryB ABC  = make("abc");
     static final TypeConAryB ABCD = make("abcd");
-    public static void gather(ArrayList<Type> ts) { ts.add(ABC); ts.add(ABCD); }
-    @Override public int elemT() { return TINT; }
     @Override public long at8(int idx) { return _ary[idx]; }
     @Override public int len() { return _ary.length; }
     @Override public int log_size() { return 0; }
     @Override public String str() { return "[\""+new String(_ary)+"\"]"; }
-    @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && Arrays.equals(_ary,ary._ary); }
+    @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); }
     @Override int hash() { return Arrays.hashCode(_ary); }
     @Override public void write( BAOS baos ) { baos.write(_ary); }
 }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java
index bb2ab83c..b1b061de 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java
@@ -1,18 +1,16 @@
 package com.seaofnodes.simple.type;
 
-import java.util.ArrayList;
 import java.util.Arrays;
 
 public class TypeConAryI extends TypeConAry<int[]> {
-    private TypeConAryI(int[] bs) { super(false,bs); }
-    public static TypeConAryI make( int[] bs ) { return new TypeConAryI(bs).intern(); }
-    private static final TypeConAryI I123  = make(new int[]{1,2,3});
-    public static void gather(ArrayList<Type> ts) { ts.add(I123); }
-    @Override public int elemT() { return TINT; }
+    private TypeConAryI(boolean any, byte widen, int[] bs) { super(any,widen,bs); }
+    public static TypeConAryI make( int[] bs ) { return new TypeConAryI(false,(byte)0,bs).intern(); }
+    @Override TypeConAryI _make( boolean any, byte widen ) { return new TypeConAryI(any,widen,_ary); }
+    static final TypeConAryI I123 = make(new int[]{1,2,3});
     @Override public long at8(int idx) { return _ary[idx]; }
     @Override public int len() { return _ary.length; }
     @Override public int log_size() { return 2; }
     @Override public String str() { return "[i32]"; }
-    @Override boolean eq(Type t) { return t instanceof TypeConAryI ary && Arrays.equals(_ary,ary._ary); }
+    @Override boolean eq(Type t) { return t instanceof TypeConAryI ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); }
     @Override int hash() { return Arrays.hashCode(_ary); }
 }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 1306a39a..a0c2266d 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -25,17 +25,13 @@ public class TypeInteger extends TypeScalar {
     private static final Ary<TypeInteger> FREE = new Ary<>(TypeInteger.class);
     private TypeInteger(long min, long max, byte widen) { super(TINT); init(min,max,widen); }
     private TypeInteger init(long min, long max, byte widen) {
-        // Constants must always have a widen value of zero.  Widening is only
-        // meaningful for ranges of values - which otherwide can increase in
-        // range size indefinitely.
-        assert min!=max || widen==0; // Constants always zero widen
         _min = min; _max = max; _widen=widen;
         return this;
     }
     public static TypeInteger malloc(long lo, long hi, byte widen) { return FREE.isEmpty() ? new TypeInteger(lo,hi,widen) : FREE.pop().init(lo,hi,widen); }
     public static TypeInteger make(long lo, long hi) { return make(lo,hi,(byte)0); }
     public static TypeInteger make(long lo, long hi, byte widen) {
-        TypeInteger i = malloc(lo,hi,lo==hi ? 0 : widen);
+        TypeInteger i = malloc(lo,hi,widen);
         TypeInteger t2 = i.intern();
         return t2==i ? i : t2.free(i);
     }
@@ -85,7 +81,16 @@ public class TypeInteger extends TypeScalar {
 
     public final static TypeInteger FATBOOL = make(0,1,(byte)2);
 
-    public static void gather(ArrayList<Type> ts) { ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); ts.add(ZERO); ts.add(FATBOOL); }
+    public static void gather(ArrayList<Type> ts) {
+        ts.add(I32); ts.add(BOT); ts.add(U1); ts.add(I1); ts.add(U8); ts.add(ZERO); ts.add(FATBOOL);
+        // Ranges before and after excluding zero, at each widening level.
+        for( byte widen=0; widen<=3; widen++ ) {
+            ts.add(make(0,255,widen));
+            ts.add(make(1,255,widen));
+            ts.add(make(-255,0,widen));
+            ts.add(make(-255,-1,widen));
+        }
+    }
 
     @Override public String str() {
         if( _isConstant() ) return ""+_min;
@@ -157,9 +162,7 @@ public class TypeInteger extends TypeScalar {
         return make(Math.min(_min,i._min), Math.max(_max,i._max), (byte)Math.max(_widen,i._widen));
     }
 
-    @Override TypeInteger xdual() {
-        return _min==_max ? this : malloc(_max,_min,(byte)(-_widen));
-    }
+    @Override TypeInteger xdual() {  return malloc(_max,_min,(byte)(3-_widen));  }
 
     @Override public TypeInteger nonZero() {
         if( isHigh() ) return this;
diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java
index b83cc9e6..b9cba5e8 100644
--- a/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -7,6 +7,22 @@ import static org.junit.Assert.assertSame;
 
 public class TypeTest {
 
+    // Removing zero must not reset the widening history of a remaining range.
+    @Test public void testNonZeroWidening() {
+        for( byte widen=0; widen<=3; widen++ ) {
+            TypeInteger pos = TypeInteger.make(0,255,widen).nonZero();
+            TypeInteger neg = TypeInteger.make(-255,0,widen).nonZero();
+            Assert.assertEquals("positive range widening",widen,pos._widen);
+            Assert.assertEquals("negative range widening",widen,neg._widen);
+            assertSame(TypeInteger.make(1,255,widen),pos);
+            assertSame(TypeInteger.make(-255,-1,widen),neg);
+            // Singleton ranges retain their widening level too.
+            assertSame(TypeInteger.make(1,1,widen),TypeInteger.make(0,1,widen).nonZero());
+            assertSame(TypeInteger.make(-1,-1,widen),TypeInteger.make(-1,0,widen).nonZero());
+        }
+        Assert.assertNull(TypeInteger.ZERO.nonZero());
+    }
+
     // Struct hashes omit field types, so interning compares unlike leaf kinds.
     @Test
     public void testCyclicLeafKinds() {