diff options
| author | Cliff Click <cliffc@acm.org> | 2026-09-28 09:23:27 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-09-28 09:23:27 -0700 |
| commit | 8212a66ff27e56531e0b48807088f1c544d75756 (patch) | |
| tree | d1a1cdbf1ae790ddd8378714d4325a84b90bfc17 /chapter25 | |
| parent | 3d226b49e1cd23b41fd9baf3917f751973c1ad11 (diff) | |
| download | Simple-8212a66ff27e56531e0b48807088f1c544d75756.tar.gz Simple-8212a66ff27e56531e0b48807088f1c544d75756.zip | |
Check un-init not-null constructor fields
Propagate BOT inputs; Arith, Load.
CallEnd inlining, the FUnPtr dies early.
Load asserts when loading against uninit not-null field.
Keep not-nill state for storage class.
Clean up Node.peep as constant.
Diffstat (limited to 'chapter25')
16 files changed, 132 insertions, 80 deletions
diff --git a/chapter25/docs/examples/BubbleSort.smp b/chapter25/docs/examples/BubbleSort.smp index ef92c29e..1b3b83e6 100644 --- a/chapter25/docs/examples/BubbleSort.smp +++ b/chapter25/docs/examples/BubbleSort.smp @@ -5,7 +5,7 @@ // Bubble sort, with reading (parsing) and writing (formatting) the data. val sort = { sys.aryi64 nums -> - var more = nums; + sys.aryi64?! more = nums; while( more ) { more = null; for( var i = 0; i < nums.len-1; i++ ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index a54eca73..e65ef6d9 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -104,7 +104,7 @@ public class IterPeeps { while( (n=_work.pop()) != null ) { if( n.isDead() ) continue; _cnt++; // Useful for debugging, searching which peephole broke things - var obs = code._obs; + var obs = code._obs; // Collect peephole neighbors for graph display if( obs != null ) obs.before(n); Node x = n.peepholeOpt(); if( n instanceof CallEndNode cend ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index 05685418..af5af514 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -101,6 +101,9 @@ public class Parser { ScopeNode _returnScope; // Merge all the function exits here Ary<FRefNode> _frefs; // Forward refs created during this parse TypeStruct _ctorOpenStruct; // Open struct being initialized by an allocation constructor block. + // Constructor exit types survive scope teardown until all fields are known. + // A null entry denotes a constructor with no returning path. + private ArrayList<IdentityHashMap<Var,Type>> _ctorExits; // Mapping from a type name to a Type. The string name matches // `type.str()` call. @@ -389,6 +392,19 @@ public class Parser { smem._declaredType = smem._type = TypeMem.makePrivate(tself); } + if( !upgrade ) { + IdentityHashMap<Var,Type> exit = null; + if( _returnScope!=null && !_returnScope.ctrl()._type.isHigh() ) { + exit = new IdentityHashMap<>(); + int first = _scope._kinds.at(_scope.depth()-2)._lexSize+2; + for( int i=first; i<lex; i++ ) + exit.put(_scope.var(i),_returnScope.in(i)._type); + } + _ctorExits.add(exit); + } else if( !isClz ) { + checkInitFields(tself,base); + } + // When can _returnScope be null here? A never-exit constructor will // not have any returns, and thus no need to gather values and store // them into the (never) constructed object @@ -412,13 +428,11 @@ public class Parser { Var v = _scope.var(vidx); if( v._fref ) continue; // Forward refs not declared here // NewNode's TOP field is the zero-code poison for a required - // field. The parser Var retains the typed nullable state for - // early-read diagnostics; only a user constructor writes memory. - if( upgrade && v._uninit ) continue; + // field. Leave it alone unless the declaration body supplied a + // value; otherwise a user constructor must initialize it. Node val = _returnScope.in(vidx); - if( !upgrade && v._uninit && val._type instanceof TypeNil tn && tn.nullable() ) - throw error("'"+tself._name+"' is not fully initialized, field '"+ - fld._fname+"' is only partially set in the constructor",v._loc); + if( upgrade && v._uninit && + !(val._type instanceof TypeNil tn && tn.notNull() && !val._type.isHigh()) ) continue; // Store value into extended struct Node prior = mmm.keep(); Node st = peep(new StoreNode(null, fld._fname, fld._alias, fld._t, null, prior, self, off(tself,fld._fname), val, fld._final)); @@ -437,6 +451,28 @@ public class Parser { //_code.add(mmm); } + // Validate each user constructor, or an implicit empty one, before the + // declaration scope goes away. Later fields use their declaration defaults. + private void checkInitFields(TypeStruct ts, int base) { + if( _returnScope==null || _returnScope.ctrl()._type.isHigh() ) return; + boolean implicit = _ctorExits.isEmpty(); + if( implicit ) _ctorExits.add(new IdentityHashMap<>()); + for( IdentityHashMap<Var,Type> exit : _ctorExits ) { + if( exit==null ) continue; + for( Field fld : ts._fields ) { + int idx = fieldVarIdx(base,fld._fname); + if( idx == -1 ) continue; + Var v = _scope.var(idx); + if( !v._uninit || v._fref ) continue; + Type t = exit.getOrDefault(v,_returnScope.in(idx)._type); + if( !(t instanceof TypeNil tn && tn.notNull() && !t.isHigh()) ) + throw error("'"+ts._name+"' is not fully initialized, field '"+fld._fname+ + (implicit ? "' needs to be set in a constructor" : + "' is only partially set in the constructor"),v._loc); + } + } + } + private int fieldVarIdx( int base, String name ) { for( int i=base; i<_scope.nIns(); i++ ) if( _scope.var(i)._name == name ) @@ -460,8 +496,7 @@ public class Parser { } private boolean inExplicitConstructor() { - if( !(_scope.klast() instanceof Kind.Func func) ) - return false; + Kind.Func func = (Kind.Func)_scope._kinds.at(_scope.enclosingFuncOrDecl()); return isExplicitConstructorName(func._name); } @@ -886,6 +921,12 @@ public class Parser { _returnScope._vars.add(vexpr); _returnScope.addDef(oldX); } + } else if( isExplicitConstructorName(k._name) ) { + // Field bindings live in the enclosing declaration, not among the + // constructor's arguments/locals. Force lazy Phis on every exit. + int first = _scope._kinds.at(lexN-1)._lexSize+2; + for( int i=first; i<k._lexSize; i++ ) + _scope.update(_scope.var(i),null); } // No prior merge point? Just clone and hang on to it @@ -1268,6 +1309,8 @@ public class Parser { // Parse a struct declaration (not an allocation); file-level is a class-init, and scope structs are normal private ReturnNode parseStruct( boolean isClz, String typeName ) { + var oldExits = _ctorExits; + _ctorExits = new ArrayList<>(); // Record & restore global state set during parsing the <init> code Node oldCtrl= _scope.ctrl().keep(); Node oldMem = _scope.mem ().keep(); @@ -1289,6 +1332,7 @@ public class Parser { // Struct decls look like function bodies. Parse function body normally. ReturnNode ret = _parseFunctionBody(fname,sig,loc(),ids); + _ctorExits = oldExits; // Unwind global state. ctrl(oldCtrl.unkeep()); mem (oldMem .unkeep()); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 60f00854..bb370a56 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -110,12 +110,9 @@ public abstract class ArithNode extends Node implements ModeNode { @Override public final Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1==null || t2==null ) - return Type.TOP; - if( t1.isHigh() || t2.isHigh() ) - return _mode==0 ? Type.TOP : - _mode==1 ? TypeInteger.TOP : - TypeFloat.F64.dual(); + if( t1==null || t2==null ) return Type.TOP; + if( t1.isHigh() || t2.isHigh() ) return Type.TOP; + if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; byte mode = _mode==0 ? mode(t1,t2) : _mode; if( mode==0 ) return CodeGen.CODE._phase.ordinal() < CodeGen.Phase.Opto.ordinal() ? Type.BOTTOM : Type.TOP; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 3c6506b9..d2286c09 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -85,7 +85,7 @@ public class CallEndNode extends CFGNode implements MultiNode { // Mid-fold, just take the one single callers' return type if( _folding ) { TypeTuple tt = (TypeTuple)in(1)._type; - return tt.makeFrom(2,tt.ret().join(tfp._ret)); + return tt.makeFrom(2,tt.ret()); } // Here, if I can figure out I've linked *all* callers, then I can meet diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java index d37655b6..bd80a74b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -48,12 +48,15 @@ public class LoadNode extends MemOpNode { if( mem._t == Type.TOP ) return TypeScalar.TOP; if( ptr0 == Type.NIL ) - return TypeScalar.TOP; - if( !(ptr0 instanceof TypeMemPtr ptr) ) + return Type.BOTTOM; // Load from nil is error + if( ptr0 == Type.BOTTOM ) + return Type.BOTTOM; // Error in is error out + if( !(ptr0 instanceof TypeMemPtr tmp) ) return scalar(mem._t); + if( tmp.nullable() ) + return Type.BOTTOM; // Load from nil-able is error // Load field from object - TypeMemPtr tmp = ptr; Field pfld = tmp._obj.field(_name); // No field? Open objects might yet get the field when falling; // closed objects with missing field are an error. @@ -110,11 +113,6 @@ public class LoadNode extends MemOpNode { if( _alias == 1 ) return null; - if( mem instanceof MemMergeNode merge ) { - setDef(1,merge.alias(_alias)); - return this; - } - // Simple Load-after-Store on same address. if( mem instanceof StoreNode st && ptr == st.nnptr() && @@ -124,15 +122,16 @@ public class LoadNode extends MemOpNode { return extend(st.val()); } - //// Expose the same effective memory input already observed by compute. - //if( mem != mem() ) { - // for( Node ld : mem._outputs ) - // if( ld instanceof LoadNode ) - // CodeGen.CODE.add(ld); - // if( mem instanceof BulkMemPhiNode ) CodeGen.CODE.add(mem); - // setDef(1,mem); - // return this; - //} + if( mem instanceof MemMergeNode merge ) { + setDef(1,merge.alias(_alias)); + // In support of uplifting control to a prior dominating load, if + // we move our memory, recheck other loads to see if they can hoist. + for( Node use : in(1).outs() ) + if( use instanceof LoadNode ld && use != this && ptr == ld.ptr() ) + CodeGen.CODE.add(ld); + + return this; + } // Uplift control to a prior dominating load. for( Node memuse : mem._outputs ) @@ -167,18 +166,21 @@ public class LoadNode extends MemOpNode { // Assume related addDep(phi); break outer; - //case ConstantNode con: - // // Load from constant memory - // if( con._con instanceof TypeMem tmem ) + case ConstantNode con: + // Load from constant memory + if( con._con instanceof TypeMem tmem ) + throw Utils.TODO("need to see a test case"); // return ConstantNode.make(tmem._t); - // break outer; // Assume shortly dead + break outer; // Assume shortly dead case ProjNode mproj: // Memory projection switch( mproj.in(0) ) { case NewNode nnn1: // Direct load from fresh zero/default-filled allocation. Type decl = declaredType(); assert decl!=Type.BOTTOM; - return ConstantNode.make(decl.makeZero()); + Type zero = decl.makeZero(); + assert zero.isa(_type); // Catch bug uninitialized null field + return ConstantNode.make(zero); case CallEndNode cend: addDep(mproj); break outer; // TODO: Bypass no-alias call default: throw Utils.TODO("Should not reach here"); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java index e2148244..e77b0c0a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java @@ -488,18 +488,8 @@ public abstract class Node implements Cloneable { // Compute initial or improved Type Type old = setType(compute()); - // Replace constant computations from non-constants with a constant - // node. If peeps are disabled, still allow high Phis to collapse; - // they typically come from dead Regions, and we want the Region to - // collapse, which requires the Phis to die first. + // Replace constant computations from non-constants with a constant node. if( !isConst() && !(this instanceof ParmNode parm && parm.inProgress()) && - // A high Load through a bad pointer still owns the source error; - // do not replace it with an unlocated constant before typeCheck. - !(this instanceof LoadNode && err()!=null) && - // A CallEnd can be temporarily high while optimistic call-graph - // linking is still discovering its target Returns. Its result - // projections must remain attached so they can sharpen later. - !(this instanceof ProjNode proj && proj.in(0) instanceof CallEndNode && _type.isHigh()) && _type.isHighOrConst() ) return ConstantNode.make(_type).peephole(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 12a94906..2683ddf5 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -260,7 +260,8 @@ public class StoreNode extends MemOpNode { Parser.ParseException err = super.err(); if( err != null ) return err; assert _size>0 || CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.Opto.ordinal(); - assert ptr()._type != Type.TOP; + if( ptr()._type == Type.TOP ) // Dead store? + return null; TypeMemPtr tmp = (TypeMemPtr)ptr()._type; Field f = tmp._obj.field(_name); if( f!=null && f._final && !_init ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 540f36ff..cfd213b7 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -71,7 +71,7 @@ public class TypeMemPtr extends TypeNil { /** Inferred mutable local: nullable, public and non-singleton. */ public TypeMemPtr makeVar() { return (TypeMemPtr)makeStorage(); } /** Public-memory shape: nullable and non-singleton, preserving the referent. */ - @Override TypeMemPtr _makeStorage() { return make((byte)3,_obj._makeStorage(),false,true); } + @Override TypeMemPtr _makeStorage() { return make(_nil,_obj._makeStorage(),false,true); } @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one, _pub); } @Override public Type nonZero() { return makeFrom((byte)(_nil <= 1 ? 1 : 2)); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 029e28b8..f41a1904 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -68,6 +68,7 @@ public class Chapter10Test { public void testNullGuardErrors() { for( String body : new String[] { "return p.x;", + "if (p == null) return p.x; return -1;", "if (!!points) return p.x; return -1;", "if (!!p) { int x = p.x; } return p.x;" } ) { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 4d273aff..24552062 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -182,7 +182,7 @@ return root; public void testNestedStructAddMemProj() { CodeGen code = new CodeGen( """ -struct _S { int a; int[] b; }; +struct _S { int a; int[] b; new _S = { int[] ary -> b=ary; }; }; return 0; """); code.parse().opto(); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java index faba6451..79aecbff 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -268,15 +268,38 @@ A x = new A; @Test public void testVar15() { - CodeGen code = new CodeGen(""" -struct B {}; -struct A { B b; new A = { -> - if (arg) b = new B; // Constructor ends with partial init of b -}; }; -return (new A).b; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("'Test.A' is not fully initialized, field 'b' is only partially set in the constructor",e.getMessage()); } + for( String fields : new String[] { + "B b; new A = { -> if (arg) b = new B; };", + "B b; new A = { -> if (arg) return 0; b = new B; };", + "B b; new A = { B b -> b = new B; };", // Argument shadows field + "new A = { -> }; B b;", // Field declared later + } ) { + CodeGen code = new CodeGen("struct B {}; struct A { "+fields+" }; return 0;"); + try { code.parse(); fail(fields); } + catch( Parser.ParseException e ) { assertEquals("'Test.A' is not fully initialized, field 'b' is only partially set in the constructor",e.getMessage()); } + } + } + + @Test + public void testDefaultConstructorFields() { + for( String field : new String[] { "B b;", "B !b;" } ) { + CodeGen code = new CodeGen("struct B {}; struct A { "+field+" }; return new A;"); + try { code.parse(); fail(field); } + catch( Parser.ParseException e ) { assertEquals("'Test.A' is not fully initialized, field 'b' needs to be set in a constructor",e.getMessage()); } + } + for( String fields : new String[] { + "B b = new B;", + "B b; b = new B;", + "new A = { -> }; B b = new B;", + "B b; new A = { -> if (arg) { b = new B; return 0; } b = new B; };", + } ) { + CodeGen code = new CodeGen("struct B {}; struct A { "+fields+" }; return new A.b != null;"); + code.parse().opto().typeCheck(); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("1",Eval2.eval(code,1)); + } + // No returning path means no object can escape uninitialized. + new CodeGen("struct B {}; struct A { B b; new A = { -> while (true) {} }; }; return 0;").parse(); } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index a9f7dde7..5ea198ef 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -195,6 +195,7 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 struct String { u8[] cs; int _hashCode; + new String = { u8[] data -> cs=data; }; }; // Compare two Strings @@ -222,9 +223,9 @@ val _hashCodeString = { String self -> return hash; }; """; - testCPU(src,"x86_64_v2", "SystemV",18,null); - testCPU(src,"riscv" , "SystemV", 7,null); - testCPU(src,"arm" , "SystemV", 8,null); + testCPU(src,"x86_64_v2", "SystemV",21,null); + testCPU(src,"riscv" , "SystemV",10,null); + testCPU(src,"arm" , "SystemV",10,null); } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 9f37be49..4307a3b6 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -292,6 +292,7 @@ return v0; struct String { u8[] cs; int _hashCode; + new String = { u8[] data -> cs=data; }; }; // Compare two Strings @@ -319,9 +320,9 @@ val _hashCodeString = { String self -> return hash; }; """; - testCPU(src,"x86_64_v2", "SystemV",18,null); - testCPU(src,"riscv" , "SystemV", 7,null); - testCPU(src,"arm" , "SystemV", 8,null); + testCPU(src,"x86_64_v2", "SystemV",21,null); + testCPU(src,"riscv" , "SystemV",10,null); + testCPU(src,"arm" , "SystemV",10,null); } @Test public void testStringExport() throws IOException { @@ -330,6 +331,7 @@ val _hashCodeString = { String self -> struct String { u8[] cs; int _hashCode; + new String = { u8[] data -> cs=data; }; }; // Compare two Strings @@ -357,7 +359,7 @@ val _hashCodeString = { String self -> return hash; }; """; - TestC.runC(src, "stringHash", "",18); + TestC.runC(src, "stringHash", "",21); } @Test public void testLoop2() { diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index 0ac55a9e..41225097 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -29,16 +29,7 @@ public class Chapter25Test { @Ignore @Test public void testJig() { - String src =" while(1?!0:arg++) {"; - String src2 = """ -int v0=0^0; - while(1) { - arg=v0++&0; - int v2=0; - if(v0) - if(v0) v2=0; - } - """; + String src = "struct I { int x; }; struct F { I p; }; return new F.p.x;"; CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); assertEquals("2",Eval2.eval(code,0)); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 66bc4717..68bbe918 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -18,7 +18,7 @@ public class FuzzerWrap { -148471672577312953L, // bulk mem -5037182906211190034L, // dead Guard control -6359653295501938199L, // monotonicity, escape is dead - 6506797708065910879L, // missing ModeNode._mode is optimistic + 6506797708065910879L, // required field without a user constructor 650692970082394944L, // recursive bulk mem split 8335100609598232836L, // ternary result killed by region cleanup 2520958273643234516L, // nested guard merge |
