From 4391fcc03a214e6296e19ca42487de023ab12f6a Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 26 Sep 2026 16:02:24 -0700 Subject: bug fix widen Failed lattice law tests mixing constants and have wide type ints; or mixing wide ints and constant arrays. --- .../java/com/seaofnodes/simple/node/PhiNode.java | 5 +- .../main/java/com/seaofnodes/simple/type/Type.java | 3 + .../com/seaofnodes/simple/type/TypeConAry.java | 81 ++++++++++------------ .../com/seaofnodes/simple/type/TypeConAryB.java | 11 ++- .../com/seaofnodes/simple/type/TypeConAryI.java | 11 ++- .../com/seaofnodes/simple/type/TypeInteger.java | 26 +++---- 6 files changed, 68 insertions(+), 69 deletions(-) (limited to 'chapter24/src/main/java/com') diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 81af208c..cfeb1404 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -81,12 +81,13 @@ public class PhiNode extends Node { } Type newt = t.join( _minType ); - // phi loop widening part + // Above-center ranges may still fall to unwidened constants. + // Widen only below-center ranges to preserve monotonicity. if( region() instanceof LoopNode && // Only around loops newt instanceof TypeInteger newi && // Types changed and are falling (the optimistic case, expected to fall forever) newi != _type ) { - if( !newi.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) ) + if( !newi.isHigh() && !newi.isConstant() && (!(_type instanceof TypeInteger oldi) || newi._widen <= oldi._widen) ) return newi.same_but_slightly_wider_than(_minType); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java index fd474a84..b47de0a4 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/Type.java @@ -264,6 +264,9 @@ public class Type /*implements Cloneable*/ { // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this". if( is_simple() ) return this.xmeet(t ); if( t.is_simple() ) return t .xmeet(this); + // Constant arrays meet their integer element types. + 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); return Type.BOTTOM; // Mixing 2 unrelated types } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index c5543030..0bc264fc 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -1,53 +1,57 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.util.SB; -import com.seaofnodes.simple.util.Utils; import java.io.ByteArrayOutputStream; +import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; /** * Represents a constant array of primitives */ -public class TypeConAry extends Type { +public abstract class TypeConAry extends Type { 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, byte type, A ary ) { super(type); _any = any; _ary = ary; } - public static final TypeConAry BOT = new TypeConAry(false, TINT, null).intern(); + TypeConAry( boolean any, byte widen, A ary ) { super(TCONARY); _any = any; _widen = widen; _ary = ary; } public static void gather(ArrayList ts) { - ts.add(BOT); - 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 _make(boolean any, byte widen); - @Override public String str() { return (_any?"~":"") + "[]"; } - @Override TypeConAry xdual() { - if( _ary==null ) - return new TypeConAry(!_any,_type,null); - return this; - } + @Override TypeConAry xdual() { return _make( !_any, (byte)(3-_widen) ); } @Override Type xmeet(Type t) { - if( t instanceof TypeInteger ti ) return imeet(ti); TypeConAry ary = (TypeConAry)t; // Invariant - if( this==BOT ) return BOT; - if( ary ==BOT ) return BOT; - if( this==BOT.dual() ) return ary ; - if( ary ==BOT.dual() ) return this; - assert _ary!=ary._ary; // Already interned and this!=t + // 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 imeet( TypeInteger ti ) { - if( this==BOT.dual() ) return ti; - if( this==BOT ) return BOT; - Type elem = elem(); - if( !(elem instanceof TypeInteger) ) return BOTTOM; - if( ti.isHigh() && elem.isa(ti.dual()) ) - return this; - return elem.meet(ti); + + 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 extends Type { min = Math.min(min,at8(i)); max = Math.max(max,at8(i)); } - return TypeInteger.make(min,max); - } - public long at8(int idx) { throw Utils.TODO(); } - public int len() { throw Utils.TODO(); } - @Override public int log_size() { throw Utils.TODO(); } - public void write( ByteArrayOutputStream baos ) { throw Utils.TODO(); } - - @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; + return TypeInteger.make(min,max,_widen); } + public abstract long at8(int idx); + public abstract int len(); + @Override public abstract int log_size(); + public void write( ByteArrayOutputStream baos ) { throw Utils.TODO("Should not reach here: abstract constant array cannot be written"); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java index 9e5f0a2d..095cdeca 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -1,21 +1,20 @@ package com.seaofnodes.simple.type; -import java.util.ArrayList; -import java.util.Arrays; import java.io.ByteArrayOutputStream; +import java.util.Arrays; public class TypeConAryB extends TypeConAry { - private TypeConAryB(byte[] bs) { super(false,TINT,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 ts) { ts.add(ABC); ts.add(ABCD); } @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( ByteArrayOutputStream baos ) { baos.write(_ary,0,_ary.length); } } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java index 8228887e..b1b061de 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -1,17 +1,16 @@ package com.seaofnodes.simple.type; -import java.util.ArrayList; import java.util.Arrays; public class TypeConAryI extends TypeConAry { - private TypeConAryI(int[] bs) { super(false,TINT,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 ts) { ts.add(I123); } + 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/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index a0cb12cb..74fbfb9f 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -23,17 +23,13 @@ public class TypeInteger extends Type { private static final Ary 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); } @@ -83,7 +79,16 @@ public class TypeInteger extends Type { public final static TypeInteger FATBOOL = make(0,1,(byte)2); - public static void gather(ArrayList 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 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; @@ -147,21 +152,18 @@ public class TypeInteger extends Type { @Override public Type xmeet(Type other) { - if( other instanceof TypeConAry ary ) return ary.imeet(this); // Invariant from caller: 'this' != 'other' and same class (TypeInteger) TypeInteger i = (TypeInteger)other; // Contract 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; if( this==ZERO ) return null; // No sane answer - if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL - if( _max==0 ) return make(_min,-1); + if( _min==0 ) return make(1,Math.max(_max,1),_widen); // specifically good on BOOL + if( _max==0 ) return make(_min,-1,_widen); return this; } @Override public Type makeZero() { return ZERO; } -- cgit v1.2.3