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. --- .../com/seaofnodes/simple/type/TypeConAry.java | 6 +- .../com/seaofnodes/simple/type/TypeConAryB.java | 3 - .../com/seaofnodes/simple/type/TypeConAryI.java | 4 +- .../com/seaofnodes/simple/type/TypeConAry.java | 12 ++-- .../com/seaofnodes/simple/type/TypeConAryB.java | 4 +- .../com/seaofnodes/simple/type/TypeConAryI.java | 6 +- .../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 +++---- .../test/java/com/seaofnodes/simple/TypeTest.java | 16 +++++ .../java/com/seaofnodes/simple/node/PhiNode.java | 5 +- .../main/java/com/seaofnodes/simple/type/Type.java | 4 +- .../com/seaofnodes/simple/type/TypeConAry.java | 74 ++++++++++---------- .../com/seaofnodes/simple/type/TypeConAryB.java | 10 ++- .../com/seaofnodes/simple/type/TypeConAryI.java | 12 ++-- .../com/seaofnodes/simple/type/TypeInteger.java | 21 +++--- .../test/java/com/seaofnodes/simple/TypeTest.java | 16 +++++ docs/chapter-backports.md | 7 +- graph/README.md | 19 +++-- skills/chapter25-codex-notes.md | 12 ++++ skills/graph-viewer-codex-notes.md | 23 +++--- 24 files changed, 210 insertions(+), 181 deletions(-) diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index 29496af6..692450d0 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.SB; import com.seaofnodes.simple.Utils; import java.util.ArrayList; import java.io.ByteArrayOutputStream; @@ -18,8 +17,9 @@ public class TypeConAry extends Type { public static final TypeConAry BOT = new TypeConAry(false,null).intern(); 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); } @Override public String str() { return (_any?"~":"") + "[]"; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java index c057c6a5..b56beb47 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.type; -import java.util.ArrayList; import java.util.Arrays; import java.io.ByteArrayOutputStream; @@ -10,10 +9,8 @@ public class TypeConAryB extends TypeConAry { 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 at(int idx) { return _ary[idx]; } @Override public int len() { return _ary.length; } - @Override public int alignment() { return 0; } @Override public String str() { return "[\""+new String(_ary)+"\"]"; } @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryB)t)._ary); } @Override int hash() { return Arrays.hashCode(_ary); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java index f888a93d..4859e839 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -1,13 +1,11 @@ package com.seaofnodes.simple.type; -import java.util.ArrayList; import java.util.Arrays; public class TypeConAryI extends TypeConAry { 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 ts) { ts.add(I123); } + static final TypeConAryI I123 = make(new int[]{1,2,3}); @Override public String str() { return "[i32]"; } @Override public int alignment() { return 2; } @Override boolean eq(Type t) { return Arrays.equals(_ary,((TypeConAryI)t)._ary); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index d4003f87..84cccd12 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.type; -import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; import java.io.ByteArrayOutputStream; import java.util.ArrayList; @@ -13,18 +12,19 @@ public class TypeConAry extends Type { // One of byte,short,int,long,float,double 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, A ary ) { super(TINT); _any = any; _ary = ary; } + public static final TypeConAry BOT = new TypeConAry(false,null).intern(); 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); } @Override public String str() { return (_any?"~":"") + "[]"; } @Override TypeConAry xdual() { if( _ary==null ) - return new TypeConAry(!_any,_type,null); + return new TypeConAry(!_any,null); return this; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java index 9e5f0a2d..75f08bef 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -1,16 +1,14 @@ package com.seaofnodes.simple.type; -import java.util.ArrayList; import java.util.Arrays; import java.io.ByteArrayOutputStream; public class TypeConAryB extends TypeConAry { - private TypeConAryB(byte[] bs) { super(false,TINT,bs); } + private TypeConAryB(byte[] bs) { super(false,bs); } public static TypeConAryB make( byte[] bs ) { return new TypeConAryB(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; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java index 924e3d73..577de82c 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java @@ -1,13 +1,11 @@ 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); } + 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 ts) { ts.add(I123); } + 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; } 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; } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java index 40264d1d..ba7d2a1e 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter24/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() { 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 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 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 _make(boolean any, byte widen); - @Override public String str() { return (_any?"~":"") + "[]"; } - @Override TypeConAry xdual() { return this; } + @Override TypeConAry 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 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 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 { - 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 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 { - 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 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 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 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; @@ -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() { diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 3cbd93c1..be0f8374 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -13,11 +13,6 @@ renumbering chapters is deferred. ## Pending corrections -- **B10: preserve integer widening in `nonZero`, Chapter 24.** Still missing: - `[0,255]` and `[-255,0]` with widening levels 1-3 become level zero. Chapter 25 - passes `_widen` to `make`; 24 does not. Widening first appears in 24, so 15-23's - older `nonZero` needs no patch. The previous audit established the type-level - discrepancy, not a loop-failure reproducer. Source: `51f1f8f4`. - **FunPtrNode lifetime backport, now next after the allocator review.** `return {->42;};` and `return sys.io.p;` fail during relocation in Chapter 22 on all three targets at seed 123. Opto's name-based pruning equates no linked @@ -218,6 +213,8 @@ Unresolved reproductions have been promoted to the pending queue above. | Completed work | Scope and evidence retained | |---|---| +| B10 and integer/constant-array widening | Widening starts in 24. Both 24-25 now use levels 0-3, dual widening `3-widen`, retained singleton widening, and widening on TypeConAry. `nonZero` preserves the coordinate. The same TypeTest regression and integer gather ranges run in both snapshots; before the backport, Chapter 24 fails the widening regression and lattice associativity. Loop Phis widen only below-center nonconstant ranges: widening an above-center range to level 1 then falling to zero at level 0 violated SCCP monotonicity in 24's existing `testCloneAnd` and `testInfinite`; both now pass, with the guard also in 25. | +| TypeConAry API backport and validation | 24-25 share the reduced raw `_make(any,widen)` API, integer meet dispatch through the distinct `TCONARY` tag, and gathered samples. Preserve 24's GLB hooks and ordinary byte stream; scalar envelopes and serialization stay in 25. Chapters 22-23 consolidate gather and remove redundant wrappers/arguments, retaining their pre-widening representations and needed sentinels. Full Make suites passed on 2026-09-26: 22 (428), 23 (450), 24 (480), 25 (474), each plus its fuzzer wrapper; all include TypeTest, and 25 rebuilt `sys.o`. Logs: `build/conary-backport-*` and `chapter25/build/conary-backport-25.log`. | | #254 subtraction zero identities | Require integer operands in 4-25 and resolved integer mode in 25. Preserve floating-point signed zero and subtraction diagnostics. `Chapter12Test.testSubZeroFloat` runs in 12-25; `Chapter22Test.testSubZeroTypeError` runs in 22-25. Against the original PR, the signed-zero test fails in 25 and the diagnostic test fails in 22-25. Full Make suites passed in every chapter 4-25 on 2026-09-25, including fresh `sys.o` compilation in 25. | | Short type extrema | Memory, struct and memory-pointer BOT/TOP names from 10; function-pointer names from 18. Exact types use shortcuts in ordinary, nested and HTML prints; precise types retain their details. Full Make suites in 10-20 and type/frontend suites in 21-25 passed; canonical/nested print checks passed in 10-25. | | Integer result types | Integer-op fallbacks in 4-13 and remaining unary cases through 17 retain integer types; 5's Phis meet their data-input types. Full Make suites in 4-17 passed, plus a chapter 5 snapshot check of Phi/Add types. Integer BOT starts in 4; later arithmetic already has typed fallbacks, with unresolved bimorphic modes preserved in 25. | diff --git a/graph/README.md b/graph/README.md index e79ff9e5..cb9ae1f1 100644 --- a/graph/README.md +++ b/graph/README.md @@ -273,17 +273,16 @@ before the parent replaces the arithmetic node. Function, loop and diamond membership comes from the compiler process; ELK lays out the supplied hierarchy. RPO is not a pending layout requirement. Placement can still shift substantially between rewrites. -Each visited frame currently retains a full snapshot and layout; bounded -history, checkpoints and deltas are also follow-up work. +Each visited frame currently retains a full snapshot and layout. -Pending graph work: +The viewer update task is complete as of 2026-09-26. Future considerations: -- Refine CFG placement with compilation-unit containers and fuller membership - for unfinished loops and paths leaving loops. -- Improve stable whole-graph placement across peepholes. Temporary neighborhoods - already preserve positions across each edit, animate it and return to the graph. -- For large compilations, add checkpoints and forward deltas with a bounded - cache of recent backward steps. +- Bounded history storage, checkpoints and deltas wait until an actual usage + issue warrants them. +- Stable whole-graph placement awaits viewing a larger program to establish what + is needed. Temporary neighborhoods already preserve positions across each edit. +- Compilation-unit containers remain deferred; unfinished-loop and exit-path + grouping is adequate for current use. ### Function, loop and diamond grouping @@ -411,7 +410,7 @@ Functions and compilation-unit boundaries. Shared grouping uses these existing IR facts to compute display membership. Scope bindings and constant lifetime edges are associations, so they need not constrain CFG layout. Types may be absent on newly constructed nodes. Node source locations -and delta encoding remain follow-up work. All chapters use the observer events +and delta encoding remain deferred possibilities. All chapters use the observer events described below. Make compiles these shared sources directly into each participating chapter's diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 64738421..1aac07a2 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -367,6 +367,18 @@ Consequences: ## Types and monotonicity +- Integer widening starts in Chapter 24. `nonZero()` preserves `_widen` when + narrowing a range. B10's correction is in 24, with `TypeTest.testNonZeroWidening` + in 24-25. Both now use widening 0-3 and dual widening `3-widen`, preserve + singleton widening, and give TypeConAry the same widening coordinate. Loop Phis + widen only below-center nonconstant ranges: above-center widening can fall to + an unwidened constant, violating SCCP monotonicity. Existing Chapter14/21 tests + exposed this during the backport. +- TypeConAry's `_make(any,widen)` shares the backing array and returns an + uninterned type. `xdual()` must leave interning to Type.intern's dual-pair setup; + ordinary factories and ymeet's widening replacement intern their results. + Chapters 24-25 use this API and a distinct array tag. Chapters 22-23 only receive + compatible cleanup; their sentinel-based representations predate widening. - Cyclic structural equality starts in Chapter 23. Chapters 9-22 compare interned children by identity and check type kinds in `Type.equals`. In recursive equality, leaf dispatch must also check `_type` before calling diff --git a/skills/graph-viewer-codex-notes.md b/skills/graph-viewer-codex-notes.md index 19fe3ec5..5b06bd6a 100644 --- a/skills/graph-viewer-codex-notes.md +++ b/skills/graph-viewer-codex-notes.md @@ -1,15 +1,17 @@ # Shared graph viewer: restart notes -Updated 2026-09-25. Read graph/README.md for the current design and protocol. +Updated 2026-09-26. Read graph/README.md for the current design and protocol. These are AI-facing continuity notes, not a new task list or authority to change -compiler semantics. Cliff reports the peephole animations, inlining display, and -TypeCheck diagnostics committed and working well as of 2026-09-25. +compiler semantics. Cliff declared the viewer task complete on 2026-09-26. +Peephole animations, inlining display, TypeCheck diagnostics, and arrow-key +playback are committed. Resume the independent bug-fix backport review from +docs/chapter-backports.md when requested. ## Working tree and latest change -Preserve existing dirty files. This checkout still reports earlier viewer changes -and untracked peep.js despite Cliff's report of commits; do not reconcile or -commit those files merely on the basis of these notes. +The working tree was clean when checked on 2026-09-26; the viewer changes, +including peep.js and arrow-key playback, are in a32e83c9. Preserve any later +unrelated dirty files. Latest request: Left/Right arrow keys perform the same actions as the Previous/Next buttons, including animation stages. Added outside inputs/editable content with @@ -143,10 +145,11 @@ capture server on an ephemeral port. Scratch helpers may disappear after cleanup ## Deferred work, not authorization to start -Cliff considers incomplete/exit-loop grouping adequate as is. Bounded history can -wait longer: mid-sized compiles slow the viewer, but it remains fine for demos. -Full graph snapshots currently remain cached. Stable whole-graph placement has no -agreed approach; compilation-unit containers remain deferred. +Cliff considers incomplete/exit-loop grouping adequate as is. Bounded history +storage waits until an actual usage issue warrants it; full graph snapshots +currently remain cached. Stable whole-graph placement awaits viewing a larger +program to establish what is needed. Compilation-unit containers remain deferred. +These are future considerations, not unfinished requirements of the completed task. Dead-field cleanup/interprocedural reverse liveness is explicitly deferred; do not revive the rejected whole-graph store sweep. Private-field syntax decisions belong in the parser, not optimization. -- cgit v1.2.3