diff options
Diffstat (limited to 'chapter29')
50 files changed, 1162 insertions, 371 deletions
diff --git a/chapter29/README.ja.md b/chapter29/README.ja.md index 54c7b5a6..8a3ff493 100644 --- a/chapter29/README.ja.md +++ b/chapter29/README.ja.md @@ -4,8 +4,8 @@ [前の章: 第28b章 — 分離コンパイル](../chapter28b/README.ja.md) -この章では、第28b章の言語と分離コンパイルの動作を保ちながら、コンパイラを -読みやすく、変更しやすく整理します。最初の変更は、3,000行を超えたパーサを +この章では、コンパイラを読みやすく、変更しやすく整理します。 +最初の変更は、3,000行を超えたパーサを 文法のまとまりに沿って `parser/` パッケージへ分割することです。 `Parser` がカーソル、スコープ、型の登録情報を持ち、各部品は `Parser P` を @@ -14,10 +14,21 @@ [パーサの構成（英語）](src/main/java/com/seaofnodes/simple/parser/README.md)と [文法と実装の対応表（英語）](docs/29-grammar.md)からコードをたどれます。 -初期化完了チェックは、構文解析後のヘルパー関数の Return を調べます。 -未初期化の必須フィールドを private memory に残すため、終了経路の別の一覧は不要です。 +インスタンスのフィールドは、初期化中も通常の Load と Store を使います。 +各終了経路のメモリは Return に統合し、最後に全フィールドを再格納する処理は行いません。 +未初期化のフィールドは `TypeScalar.BOT` で表し、meet でも未初期化の分岐が残ります。 +通常のメモリ型の前向き解析で初期化を確認します。詳細は `Construction.java` の +クラスコメントに記載しています。クラスのシングルトン初期化は従来の方式を維持します。 ソース上のプライバシー制約は今回は追加せず、[ロードマップ](../docs/roadmap.md)に残します。 +[構築グループの実験（英語）](docs/construction-groups.md)では、コンストラクタの +`C ^arg` 引数で未完成の参照を渡せます。未完成の引数を受け取る new の結果も未完成です。 +`TypeMemPtr` の修飾子を通常の型解析で伝播し、一時的な `ConstructNode` が +各 new の実引数から結果の修飾子を計算します。 +未完成のオブジェクトのフィールドは self 以外から読めず、通常の関数呼び出しには +完成した参照が必要です。フィールド要件の推論は後回しにし、対応するテストを保存しています。 +`^` を使うコンストラクタの分離コンパイルは未対応です。 + リポジトリのルートからビルドとテストを実行します。 ```sh diff --git a/chapter29/README.md b/chapter29/README.md index 15ddc1a9..28925606 100644 --- a/chapter29/README.md +++ b/chapter29/README.md @@ -4,8 +4,7 @@ English | [日本語](README.ja.md) [Previous: Chapter 28b — Separate Compilation](../chapter28b/README.md) -This chapter makes the compiler easier to read and change while preserving -Chapter 28b's language and separate-compilation behavior. It starts by breaking +This chapter makes the compiler easier to read and change. It starts by breaking the parser into grammar-sized pieces. Further cleanup belongs here; earlier chapters retain their teaching snapshots. @@ -35,21 +34,30 @@ other packages. `IterPeeps` now lives in `codegen/` beside the compilation passe ## Checking constructor completion -`addReturn` merges field values across exit paths. After `parseBody` finishes, -`Structs.parseInitializer` checks the completed helper Returns; no separate exit -maps survive scope teardown. Required fields without an assignment on every -returning path retain `TOP` in private memory. They emit no Store, so numeric -conversions cannot hide the missing assignment. - -The declaration initializer and user constructor have separate Returns. Check -the user constructor when present, or the declaration initializer for the default -constructor. The older same-named constructor binding can precede field -declarations; fields absent from its Return use the declaration initializer's -result. Nonreturning helpers require no completed object. Completion errors -point to the relevant helper's source location. - -`ConstructorCompletionTest` covers partial numeric assignments, early returns, -nonreturning paths, declaration defaults, and fields declared after constructors. +Instance fields use ordinary Loads and Stores during declaration initialization +and constructor execution. One hidden private-memory value flows through scope +merges and `addReturn`; field values are no longer copied into memory at exit. + +Fresh fields start at `TypeScalar.BOT`, which preserves a missing live arm at a +merge. Forward memory types supply the initialization proof at Loads and merged +Returns. Checks run after parsing and an optimistic type solve; there is no +separate initialization walk or field-state map. Class singleton initialization +retains its existing store-at-exit path. + +`ConstructorCompletionTest` covers partial assignments, early returns, loops, +declaration defaults and immediate field access, and the formerly disabled +required-number/nullable-default regression. The large comment on +[`Construction`](src/main/java/com/seaofnodes/simple/parser/Construction.java) +explains the type proof and the separate yes/no restriction on references. + +The [construction-group experiment](docs/construction-groups.md) adds `C ^arg` +constructor parameters. A new result is incomplete iff an actual argument is +incomplete. A `TypeMemPtr` qualifier propagates this through normal type flow; +a temporary `ConstructNode` types each new result from that call's arguments. +Only self may be read while incomplete; ordinary calls require completed +objects. Field sharpening and inferred requirements are deferred, +with their litmus tests preserved in `ConstructionRequirementsTest`. Separate +compilation of constructors using `^` remains unsupported. ## Further cleanup diff --git a/chapter29/docs/29-grammar.ja.md b/chapter29/docs/29-grammar.ja.md index 48251d9b..b7794410 100644 --- a/chapter29/docs/29-grammar.ja.md +++ b/chapter29/docs/29-grammar.ja.md @@ -41,7 +41,13 @@ structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; structMember : constructorDeclaration | methodDeclaration | statement ; // The constructor name must match the enclosing struct's name. -constructorDeclaration : 'new' IDENTIFIER '=' functionExpression ';' ; +constructorDeclaration : 'new' IDENTIFIER '=' constructorExpression ';' ; +constructorExpression : '{' constructorParameterList? '->' statement* '}' ; +constructorParameterList : (constructorParameter ','?)+ ; +constructorParameter : type '^'? bindingModifier? IDENTIFIER ; +// ^ accepts an unfinished struct reference; ? independently permits null. +// Only self may be read while incomplete; ^ arguments may be stored/forwarded. +// A new result is incomplete iff an actual argument is. See construction-groups.md. // A method is an ordinary fixed function binding in a struct definition. // The compiler supplies self; it is not written in parameterList. diff --git a/chapter29/docs/29-grammar.md b/chapter29/docs/29-grammar.md index 58c9b30c..cb231ce0 100644 --- a/chapter29/docs/29-grammar.md +++ b/chapter29/docs/29-grammar.md @@ -47,7 +47,13 @@ structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; structMember : constructorDeclaration | methodDeclaration | statement ; // The constructor name must match the enclosing struct's name. -constructorDeclaration : 'new' IDENTIFIER '=' functionExpression ';' ; +constructorDeclaration : 'new' IDENTIFIER '=' constructorExpression ';' ; +constructorExpression : '{' constructorParameterList? '->' statement* '}' ; +constructorParameterList : (constructorParameter ','?)+ ; +constructorParameter : type '^'? bindingModifier? IDENTIFIER ; +// ^ accepts an unfinished struct reference; ? independently permits null. +// Only self may be read while incomplete; ^ arguments may be stored/forwarded. +// A new result is incomplete iff an actual argument is. See construction-groups.md. // A method is an ordinary fixed function binding in a struct definition. // The compiler supplies self; it is not written in parameterList. diff --git a/chapter29/docs/construction-groups.md b/chapter29/docs/construction-groups.md new file mode 100644 index 00000000..c817626e --- /dev/null +++ b/chapter29/docs/construction-groups.md @@ -0,0 +1,131 @@ +# Construction: field types and incomplete references + +Instance constructors use ordinary field Loads and Stores. There are two checks: +whether a field has a value, and whether an object reference is usable outside +construction. Neither requires a collection of constructor-group identities. + +## Field initialization + +New produces private `TypeMem` containing the object's `TypeStruct`, with +`TypeScalar.BOT` for fresh fields. Defaults emit ordinary Stores: zero for an +ordinary integer, null for a nullable pointer, no Store for a required field. +An assignment strongly updates its field in private memory. Phi meets the +incoming memories; a missing live arm survives because `BOT.meet(7) == BOT`. +An initialized unknown integer has `TypeInteger.BOT`, not `TypeScalar.BOT`. +Arrays retain their language-level zero filling. + +One `#selfMem` binding carries this memory through scopes and returns. A Load +checks its incoming field type. Constructor completion checks the merged Return +memory; the explicit constructor receives the declaration initializer's merged +result, including early exits. There is no backwards initialization query, +per-field parser state, call-site snapshot, or store-all instance exit. + +After parsing closes loops and resolves names, `Iter.types` computes an +optimistic fixed point using the existing node types, compute methods, and +worklist, without graph rewrites. Optimism matters: an initialized field carried +unchanged around a loop must not remain stuck at a pessimistic BOT seed. Numeric +fields in loop memory widen as scalar loop values do. Constructor Loads remain +kept until checking, so an unused or folded result cannot hide an illegal read. +BOT describes the incoming field contents, not a taint on later computations. +Conversions and numeric Stores retain their existing declared-type bounds; +their narrowing cannot excuse the original Load, which is checked independently. + +Internal construction memory parameters use actual allocation/initializer call +edges; the hypothetical external caller does not supply their memory. They +retain their memory family when there are no live callers. Function-valued +fields retain their declared signatures in private summaries, avoiding repeated +unfolding of a constructor whose returned memory contains its own function field. +Class singleton initialization keeps its older store-at-exit implementation. + +## A yes/no rule for references + +`self` and incoming `C ^arg` constructor parameters are incomplete references. +`C? ^arg` also accepts null. The qualifier is permitted only on struct parameters +of explicit constructors, not on arrays or ordinary function parameters. + +- An allocation result is incomplete if any actual argument is incomplete. +- With only completed arguments, including null, the result is complete. +- An incomplete reference may be stored into self or passed to a `^` parameter. +- Ordinary calls and stores into other objects require completed references. +- Field lookup on an incomplete object is forbidden, except through self. + Exact local aliases of self share its current private memory. +- An object-reference field read from incomplete self is conservatively + incomplete. There is no inference of initialized-field requirements on `^` + arguments, nor permission to traverse a constructed member before its root + construction finishes. Arrays are already initialized and cannot receive + incomplete elements, so an initialized array field can be used normally. + +For example: + +```simple +struct Child { + Test.Parent? parent; + new Child = { Test.Parent? ^par -> parent = par; }; +}; +struct Parent { + Child child; + int~ payload; + new Parent = { int n -> + child = new Child(self); // Incomplete result: self is incomplete. + // child.parent is forbidden here. + payload = n; + }; +}; +val parent = new Parent(arg); +val local = new Child(parent); // Complete argument, complete result. +return local.parent==parent; // Lookup is allowed. +``` + +Here `Test` names the source unit. After the root Parent constructor completes, +the entire cycle is usable: all members have initialized their own fields, and +none could expose an incomplete reference to ordinary code during construction. +The Child constructor still treats its `^par` as incomplete when the actual +argument is complete; it may retain or forward it, but cannot read `par.payload`. +Field sharpening and inferred contracts are deliberately deferred. + +## Aliases and loops + +Incomplete is a property of a value, not just the current contents of a parser +Var. Consider `while (n--) { use(p); p = self; }`: the backedge introduces an +incomplete value after `use(p)` has been parsed. `TypeMemPtr._partial` carries +that restriction through ordinary forward typing. It is an independent +two-point lattice: meet ORs the restriction and dual complements it. Copies, +conversions, Stores, and Phis preserve it; a merge is incomplete if any live +input is incomplete. A `^` formal stays incomplete even when its known callers +are complete. The receiver's private memory identifies the own-self exception; +another incomplete pointer of the same class has no such permission. + +A small `ConstructNode` wraps each source `new`. Its runtime value is the +allocator result; its type adds the OR of that call's actual argument qualifiers. +This distinguishes `new Child(self)` from `new Child(null)` even when both call +the same constructor. Looking only at the shared callee Return would lose this +distinction. The node disappears after source checking, before lowering. + +A completed receiver gives a completed view of its pointer fields. Construction +may retain incomplete references but cannot publish them, so reaching the root +`new` boundary with complete arguments makes the entire reachable cycle usable. +There is no group identity or traversal to mark members complete. Conversely, +object-reference fields read through incomplete self remain conservative, even +if the particular stored reference was complete. + +The optimistic `Iter.types` solve also handles qualifier cycles. For +`p = null; while (n--) p = new Link(p);`, no input introduces incompleteness, +so `p` stays complete and a subsequent field read is allowed. A backedge carrying +self instead makes the Phi and its uses incomplete. + +`Construction` retains source operands and diagnostic sites until checking; +it stores no flow facts and performs no recursive Load/Phi/Call query. The old +root and allocation bitsets are gone. There are no field-requirement sets, +hidden `^` memory arguments, or runtime group objects. + +`ConstructionGroupTest` exercises cycles, complete/null arguments, prohibited +lookups/publication, aliases, branch merges, complete and incomplete loop +backedges, and declared restrictions with only complete callers, including an +uninlined constructor through machine encoding. `ConstructorCompletionTest`, +`FinalConstructionTest`, and `BoundaryTest` exercise field-memory semantics. +The former inferred-requirement litmus tests are preserved, explicitly deferred, +in `ConstructionRequirementsTest`. Separate compilation of `^` constructors is +still deliberately unsupported. The pointer qualifier has an object-file +representation, but importing and checking the full construction contract is +outside this experiment. Rebuild chapter 29 object files after the type-format +change. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java index 4085ebff..1f53d3e4 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -29,6 +29,25 @@ public abstract class Iter { assert !CodeGen.expensiveAssert() || Opto.fixedPointCheck(code); } + // Stabilize existing node types before releasing source error obligations. + // No rewrites: even an unused illegal Load must still be checked here. + public static void types(CodeGen code) { + // Definite initialization needs the optimistic solution around loops: + // an unchanged initialized field must not be stuck at its old BOT seed. + Ary<Node> typed = new Ary<>(Node.class); + code._start.walk(n -> { typed.add(n); n._type = Type.TOP; code.add(n); return null; }); + Node n; + while( (n = code._iter._work.pop())!=null ) { + if( n.isDead() ) continue; + Type t = n._type.meet(n.compute()); + if( t==n._type ) continue; + n._type = t; + code.addAll(n._outputs); + n.moveDepsToWorklist(); + } + code.addAll(typed); + } + private static Type iterEscapeReset(Type t) { if( t instanceof TypeMem mem ) return mem._one ? mem : mem.makeFrom(XInt.FULL,XInt.FULL); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 7fa4c662..2958332b 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -164,6 +164,7 @@ public abstract class ParseAll { // The complete public interface is now known. Keep this independent // of later graph/linker liveness so SCCP computations remain local and // monotonic. + code.P.checkConstruction(); code.freezePublicInterface(); } @@ -337,9 +338,11 @@ public abstract class ParseAll { // Add the new top-level loaded class Parser.TYPES.put(cunit._clz._name,cunit._clz); - Field inst = cunit._clz.field(cunit._name); - if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMem mem ) - Parser.TYPES.put(cunit._cname,mem._t); + // Layout belongs to the allocator's object result. An initializer's + // private-memory return no longer promises initialized field values. + Field inst = cunit._clz.field("<new>"); + if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMemPtr ptr ) + Parser.TYPES.put(cunit._cname,ptr._obj); } // Symbol not found in source code (or we would not be here). diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 4bb94183..ae4ecb74 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -38,6 +38,7 @@ public class Serialize { } static void serialize( CodeGen code ) { + code.P.checkConstructionSerializable(); // Anonymous functions also need names when another object refers to them. for( FunNode fun : code._linker ) if( fun!=null && !fun.isDead() && fun._name==null ) @@ -421,11 +422,9 @@ public class Serialize { if( !(type instanceof TypeStruct ts) || !TypeStruct.startsClzPrefix(ts._name) ) continue; String cname = ts._name.substring(TypeStruct.CLZ.length()); - int dot = cname.lastIndexOf('.'); - String name = dot == -1 ? cname : cname.substring(dot+1); - Field inst = ts.field(name.intern()); - if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMem mem && mem._t instanceof TypeStruct its ) - Parser.TYPES.put(cname,its); + Field inst = ts.field("<new>"); + if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMemPtr ptr ) + Parser.TYPES.put(cname,ptr._obj); } elf._pubTypes = new TypeStruct[npubTypes]; for( int i=0; i<npubTypes; i++ ) { diff --git a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index c9e53311..abd8628d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeScalar; import com.seaofnodes.simple.util.Ary; // Reject invalid optimized programs before lowering erases their source-level @@ -52,7 +53,7 @@ abstract class TypeCheck { private static boolean noBottomInputs(Node n) { for( Node def : n._inputs ) - if( def!=null && !(def instanceof FldOffNode) && def._type==Type.BOTTOM ) + if( def!=null && !(def instanceof FldOffNode) && (def._type==Type.BOTTOM || def._type==TypeScalar.BOT) ) return false; return true; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 16e9ec8d..2c6610e1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -117,10 +117,13 @@ public abstract class ArithNode extends Node implements ModeNode { if( t2 instanceof TypeConAry ary ) t2 = ary.elem(); if( t1==null || t2==null ) return Type.TOP; if( t1.isHigh() || t2.isHigh() ) return Type.TOP; + // Scalar.BOT is an unknown/uninitialized scalar, not an integer. + // Keep that family through arithmetic, including annihilators like *0. // Without numeric inputs, stay below both possible result families. // Pointer modes belong to comparisons, not arithmetic. if( !(t1 instanceof TypeInteger || t1 instanceof TypeFloat) || - !(t2 instanceof TypeInteger || t2 instanceof TypeFloat) ) return Type.BOTTOM; + !(t2 instanceof TypeInteger || t2 instanceof TypeFloat) ) + return t1.isa(TypeScalar.BOT) && t2.isa(TypeScalar.BOT) ? TypeScalar.BOT : Type.BOTTOM; byte mode = _mode==0 ? mode(t1,t2) : _mode; if( mode==1 ) { if( t1 instanceof TypeInteger x && @@ -128,7 +131,7 @@ public abstract class ArithNode extends Node implements ModeNode { return x.isConstant() && y.isConstant() ? con(x,y) : doOp(x,y).makeWide( (byte)Math.max(x._widen,y._widen) ); - return TypeInteger.BOT; + return TypeScalar.BOT; } // FP handling if( t1 instanceof TypeFloat f1 && t2 instanceof TypeFloat f2 && @@ -182,9 +185,9 @@ public abstract class ArithNode extends Node implements ModeNode { Node[] ns = new Node[lhs.nIns()]; ns[0] = lhs.in(0); for( int i=1; i<lhs.nIns(); i++ ) { - ns[i] = isCon(lhs,rhs,i) - ? ConstantNode.make(con(lhs.in(i)._type, rhs.in(i)._type)).peephole() - : copy(lhs.in(i), rhs.in(i)).peephole(); + // Let the copied operation's compute handle constants + // in its actual numeric family, including floats. + ns[i] = copy(lhs.in(i), rhs.in(i)).peephole(); } String label = lhs._label==rhs._label ? lhs._label : lhs._label + rhs._label; return new PhiNode(label, ns).peephole(); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 02d3e22e..203e2266 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -29,7 +29,7 @@ abstract public class BoolNode extends Node implements ModeNode { } @Override - public TypeInteger compute() { + public Type compute() { Type t1 = in(1)._type; Type t2 = in(2)._type; if( t1==null || t2==null ) @@ -37,9 +37,11 @@ abstract public class BoolNode extends Node implements ModeNode { // Exactly equals? if( t1.isHigh() || t2.isHigh() ) return (TypeInteger)BOOL.dual(); - if( in(1)==in(2) ) - // LT fails, both EQ and LE succeed - return this instanceof LT ? FALSE : TRUE; + if( t1==Type.BOTTOM || t2==Type.BOTTOM ) return Type.BOTTOM; + if( t1==TypeScalar.BOT || t2==TypeScalar.BOT ) return TypeScalar.BOT; + if( in(1)==in(2) && (t1 instanceof TypeInteger || t1 instanceof TypeNil) ) + // Floating x==x is not true when x may be NaN. + return this instanceof EQ || this instanceof LE ? TRUE : FALSE; byte mode = _mode==0 ? ArithNode.mode(t1,t2) : _mode; if( mode==0 ) return BOOL; @@ -71,9 +73,7 @@ abstract public class BoolNode extends Node implements ModeNode { @Override public Node idealize() { - // Compare of same - if( in(1)==in(2) ) - return this instanceof LT ? CodeGen.CODE.ZERO : ConstantNode.make(TRUE); + // Constant comparisons, including compare-of-same, belong in compute(). // Can we decide int vs flt? Type t1 = in(1)._type, t2 = in(2)._type; if( t1==null || t2==null ) @@ -136,8 +136,8 @@ abstract public class BoolNode extends Node implements ModeNode { @Override public Tag serialTag() { return Tag.NE; } public String op() { return "!="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { - if( i1==i2 && i1.isConstant() ) return TRUE; - if( i1._max < i2._min || i1._min > i2._max ) return FALSE; + if( i1==i2 && i1.isConstant() ) return FALSE; + if( i1._max < i2._min || i1._min > i2._max ) return TRUE; return BOOL; } @Override boolean doOp(double lhs, double rhs) { return lhs!=rhs; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java index 4024c5a9..9e130bb4 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java @@ -23,8 +23,8 @@ public class ConFldOffNode extends ConstantNode { public ConFldOffNode( TypeStruct ts, String fname ) { super(TypeInteger.BOT); _ts = ts; _fname = fname; } // Field offset for a known type (but unknown offset). - public static ConFldOffNode make( TypeStruct ts, String fname ) { - return (ConFldOffNode)new ConFldOffNode(ts,fname).peephole(); + public static Node make( TypeStruct ts, String fname ) { + return new ConFldOffNode(ts,fname).peephole(); } @Override public Tag serialTag() { throw Utils.TODO("should not reach here"); } @@ -37,20 +37,22 @@ public class ConFldOffNode extends ConstantNode { return p.p(label()); } - @Override public Node idealize() { + @Override public boolean isConst() { return false; } + + @Override public Type compute() { // Some array offsets are known early if( _ts.isAry() ) { // Length always at offset zero if( _fname==" len" ) - return CodeGen.CODE.ZERO; + return TypeInteger.ZERO; // The shift depends on the element if( _fname=="<<" ) - return Node.con(_ts.aryScale()); + return TypeInteger.constant(_ts.aryScale()); // The base depends on the layout (alignment for large elements may // involve padding) and MAY depend on the length if I go for // smaller array lengths. } - return null; + return _con; } // Convert field offset to an integer diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java new file mode 100644 index 00000000..52e3eb54 --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ConstructNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.print.ExprPrinter; + +/** The source new boundary. Own fields have been constructed, but an incomplete + * actual argument keeps this result incomplete. Unlike a callee's merged Return, + * this transfer describes one allocation site. Erased after source checks. */ +public class ConstructNode extends Node { + public ConstructNode(Node value, Ary<Node> args) { + super(null,value); + for( Node arg : args ) addDef(arg); + } + @Override public String label() { return "Construct"; } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("construct(").n(in(1)).p(")"); } + @Override public Type compute() { + Type t = in(1)._type; + if( !(t instanceof TypeMemPtr ptr) ) return t; + boolean partial = false; + for( int i = 2; i<nIns(); i++ ) partial |= TypeMemPtr.mayBePartial(in(i)._type); + return ptr.withPartial(partial); + } + @Override public Node idealize() { + return CodeGen.CODE._phase==CodeGen.Phase.Parse ? null : in(1); + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java index 81f46097..ee911398 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ConvertNode.java @@ -39,6 +39,7 @@ public class ConvertNode extends Node { @Override public Type compute() { Type src = val()._type; if( src.isHigh() ) return Type.TOP; + if( _dst instanceof TypeMemPtr ptr ) return ptr.withPartial(TypeMemPtr.mayBePartial(src)); if( !(_dst instanceof TypeMemPtr) && src.isa(_dst) ) return src; return _dst; } @@ -46,7 +47,8 @@ public class ConvertNode extends Node { @Override public Node idealize() { Type src = val()._type; if( src==Type.BOTTOM || src==Type.TOP ) return null; - if( (src.isa(_dst) && src.accessISA(_dst)) ) return val(); + Type dst = _dst instanceof TypeMemPtr ptr ? ptr.withPartial(TypeMemPtr.mayBePartial(src)) : _dst; + if( (src.isa(dst) && src.accessISA(dst)) ) return val(); // Managed arrays are represented by an object pointer, while C wants // the address of the first element. The representation cast itself is @@ -63,10 +65,10 @@ public class ConvertNode extends Node { return new ConvertNode(_dst,new ToIntegerNode(val()).peephole()); // Narrow integers produce the declared sign/zero extension. - if( src instanceof TypeInteger && _dst instanceof TypeInteger dst ) { - if( dst._min==0 ) - return new AndNode(null,val(),con(dst._max)); - int shift = Long.numberOfLeadingZeros(dst._max)-1; + if( src instanceof TypeInteger && _dst instanceof TypeInteger ti ) { + if( ti._min==0 ) + return new AndNode(null,val(),con(ti._max)); + int shift = Long.numberOfLeadingZeros(ti._max)-1; Node shf = con(shift); if( shf._type==TypeInteger.ZERO ) return val(); return new SarNode(null,new ShlNode(null,val(),shf.keep()).peephole(),shf.unkeep()); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 9aa8b311..4b09d2e9 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -76,6 +76,7 @@ public class LoadNode extends MemOpNode { return Type.BOTTOM; // Error in is error out if( !(ptr0 instanceof TypeMemPtr tmp) ) return scalar(mem._t); + if( tmp._partial && (!mem._one || mem._clz) ) return TypeScalar.BOT; if( tmp.nullable() ) return Type.BOTTOM; // Load from nil-able is error @@ -91,13 +92,19 @@ public class LoadNode extends MemOpNode { // Load member of constant array if( t instanceof TypeConAry ary ) t = ary.elem(); // TODO: if offset is known, can peek the constant - if( mem._alias==_alias ) + if( mem._one && !mem._clz && !tmp._obj.isAry() ) { + Field actual = mem._t instanceof TypeStruct ts ? ts.field(_name) : null; + t = mem._alias==_alias ? mem._t : actual==null ? TypeScalar.BOT : actual._t; + } else if( mem._alias==_alias ) t = t.join(mem._t); // A deeply read-only base produces a deeply read-only value. The // generic declared field type must not cast this information away. if( ptr0.isFinal() || readonly ) t = t.makeRO(); + // A completed receiver gives a completed view of its reachable fields. + // Through self, keep object references restricted until the root new. + if( t instanceof TypeMemPtr value ) t = value.withPartial(tmp._partial && !value._obj.isAry()); return scalar(t); } @@ -110,6 +117,7 @@ public class LoadNode extends MemOpNode { @Override public Node idealize() { + if( _type==TypeScalar.BOT ) return null; Node mem = mem(); Node ptr = ptr(); @@ -169,7 +177,9 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && + if( mem() instanceof PhiNode memphi && !(memphi instanceof ParmNode) && + (memphi instanceof MemPhiNode || (memphi._type instanceof TypeMem tm && tm._one)) && + memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && // Retain control on both copies only if it dominates both paths. // The Region itself, or a later range check, cannot move to its inputs. (in(0)==null || cfg0().domLCA(memphi.region().idom(this),this)==cfg0()) && @@ -203,6 +213,9 @@ public class LoadNode extends MemOpNode { // Load a flavored zero from a New private Node zero(NewNode nnn) { + // Object fields acquire values from their initializer's Stores. + // Only arrays expose calloc's zero-fill as a language-level default. + if( !nnn._ts.isAry() ) return new ConstantNode(TypeScalar.BOT).peephole(); Type zero = declaredType().makeZero(); assert zero.isa(_type); // Catch an uninitialized non-null field return castRO(new ConstantNode(zero).peephole()); @@ -246,7 +259,8 @@ public class LoadNode extends MemOpNode { if( esc.self()==ptr ) { mem=esc.priv(); break; } if( neverAlias(ptr,esc.self()) ) { mem=esc.pub(); break; } return null; - case MemPhiNode phi: + case PhiNode phi: + if( phi instanceof ParmNode || (!(phi instanceof MemPhiNode) && !(phi._type instanceof TypeMem tm && tm._one)) ) return null; addDep(phi.region()); // Only the original loop closes a successful cycle. Another // loop or an unfinished merge needs a separate proof. @@ -273,7 +287,7 @@ public class LoadNode extends MemOpNode { Node win=find(mem,ptr,stop,new BitSet()); if( win!=null ) { if( win==stop ) return value; - if( win instanceof MemPhiNode mp ) { + if( win instanceof PhiNode mp ) { PhiNode phi=new PhiNode(_name,mp.region()).keep(); for( int i=1; i<mp.nIns(); i++ ) phi.addDef(load(mp.in(i),ptr,stop,value)); return CodeGen.CODE.add(phi.unkeep().peephole()); @@ -311,6 +325,15 @@ public class LoadNode extends MemOpNode { return false; } + @Override public Parser.ParseException err() { + Parser.ParseException err = super.err(); + if( err!=null ) return err; + if( (in(0)==null || !in(0)._type.isHigh()) && _type==TypeScalar.BOT && + mem()._type instanceof TypeMem mem && mem._one && !mem._clz ) + return Parser.error("Field '"+_name+"' might not be initialized",_loc); + return null; + } + // Read-Only is a deep property, and cannot be cast-away private Node castRO(Node rez) { if( (ptr()._type.isFinal() || declaredType().isFinal()) && !rez._type.isFinal() ) diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 24ca6157..b453550d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -123,6 +123,9 @@ public abstract class MemOpNode extends TypeNode { // Already an error, but better error messages come from elsewhere if( ptr == Type.BOTTOM ) return null; if( ptr.isHigh() ) return null; // Assume it will fall to not-null + if( ptr instanceof TypeMemPtr p && p._partial && + !(mem()._type instanceof TypeMem m && m._one && !m._clz) ) + return Parser.error("Cannot access field '"+_name+"' through an incomplete object",_loc); // Better be a not-nil TMP if( !(ptr instanceof TypeMemPtr tmp && tmp.notNull()) ) return Parser.error( "Might be null accessing '" + _name + "'",_loc); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 4f4343d4..63d413d0 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -47,12 +47,12 @@ public class MinusNode extends Node implements ModeNode { return TypeInteger.BOT; } if( t instanceof TypeFloat f ) { - if( _mode==1 ) return TypeInteger.BOT; + if( _mode==1 ) return TypeScalar.BOT; return f.isConstant() ? TypeFloat.constant(-f.value()) : f; } // No numeric family is known. This must be below both integer and // float results, in either analysis direction and with any mode. - return Type.BOTTOM; + return t.isa(TypeScalar.BOT) ? TypeScalar.BOT : Type.BOTTOM; } @Override diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java index bb99cad5..04fcf1c2 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -16,6 +16,7 @@ public class MulNode extends ArithNode { @Override long doOp( long x, long y ) { return x * y; } @Override double doOp(double x, double y ) { return x * y; } @Override TypeInteger doOp(TypeInteger x, TypeInteger y) { + if( x==TypeInteger.ZERO || y==TypeInteger.ZERO ) return TypeInteger.ZERO; return TypeInteger.BOT; } @@ -26,6 +27,11 @@ public class MulNode extends ArithNode { Type t1 = lhs._type; Type t2 = rhs._type; + // Integer strength reductions require two integer operands. In + // particular Scalar.BOT * 0 must retain its unresolved input. + if( _mode!=1 || !(t1 instanceof TypeInteger && t2 instanceof TypeInteger) ) + return super.idealize(); + // Move constants to RHS: con*arg becomes arg*con if ( t1.isConstant() && !t2.isConstant() ) return swap12(); @@ -36,7 +42,7 @@ public class MulNode extends ArithNode { // canonicalize to (x*1) long c = i.value(); if( c==1 ) return lhs._type.isa(compute()) ? lhs : super.idealize(); - if( c==0 ) return CodeGen.CODE.ZERO; + // Zero is handled by compute(), before idealize(). // Mul by a power of 2, +/-1. Bit patterns more complex than this // are unlikely to win on an X86 vs the normal "imul", and so // become machine-specific. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/NewNode.java index d4df7a0b..96a237e1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -44,9 +44,9 @@ public class NewNode extends Node implements MultiNode { TypeStruct ts = _ts.isAry() ? _ts : _ts.makeInit(); return TypeTuple.make(TypeMemPtr.make(_ts), // Arrays get pre-zeroed by constructor. - // Objects start with default-zero memory for - // fields that can be zero-initialized. This is - // still private memory, so no aliases escape yet. + // Object fields start at Scalar.BOT; declaration + // defaults are explicit Stores. This is private + // memory, so no aliases escape yet. TypeMem.make(1,ts,true,false,false,null,null)); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/NotNode.java index 2328c287..c3a795c9 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -11,9 +11,10 @@ public class NotNode extends Node { @Override protected String format() { return "(!%1)"; } @Override - public TypeInteger compute() { + public Type compute() { Type t0 = in(1)._type; if( t0.isHigh() ) return (TypeInteger)TypeInteger.BOOL.dual(); + if( t0==Type.BOTTOM || t0==TypeScalar.BOT ) return t0; if( t0 == Type.NIL || t0 == TypeInteger.ZERO ) return TypeInteger.TRUE; if( t0 instanceof TypeNil tn && tn.notNull() ) return TypeInteger.FALSE; if( t0 instanceof TypeInteger i && (i._min > 0 || i._max < 0) ) return TypeInteger.FALSE; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 91c471c0..1d8bd484 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.codegen.Serialize; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; @@ -64,13 +65,18 @@ public class ParmNode extends PhiNode { @Override public Type compute() { if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; + return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_declaredType instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. - if( r.inProgress() || in(nIns()-1)==null ) + boolean privateMem = _idx==3 && _declaredType instanceof TypeMem mem && mem._one && !mem._clz; + if( privateMem && fun().unknownCallers() && nIns()==2 && CodeGen.CODE._phase!=CodeGen.Phase.Parse ) + return TypeMem.TOP; + if( (!privateMem && r.inProgress()) || in(nIns()-1)==null || (privateMem && fun().unknownCallers() && nIns()==2) ) return _declaredType; // Set type to local top of the starting type Type t = Type.TOP; - for( int i = 1; i < nIns(); i++ ) { + // Internal construction memory is supplied by allocation/initializer + // calls, not by the fictitious external caller used to keep a body live. + for( int i = privateMem && fun().unknownCallers() ? 2 : 1; i < nIns(); i++ ) { // If the region's control input is live, add this as a dependency // to the control because we can be peeped should it become dead. Type ctrl = addDep(r.in(i))._type; @@ -87,7 +93,12 @@ public class ParmNode extends PhiNode { // widening this Parm alone cannot stop f(x-1)+1 from growing its result. if( t instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) t = ti.same_but_slightly_wider_than(); - return t.join(_declaredType); + t = t.join(_declaredType); + // ^ is a restriction inside the constructor even if every currently + // known caller passes a complete object. Inlining may later remove it. + if( t instanceof TypeMemPtr ptr && _declaredType instanceof TypeMemPtr decl && decl._partial ) + t = ptr.withPartial(true); + return t==Type.TOP && _declaredType instanceof TypeMem ? TypeMem.TOP : t; } @Override diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 75d3ff13..a4aaaa07 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -19,6 +19,13 @@ public class PhiNode extends Node { _label = label; } public static PhiNode make(String label, Type minType, Node... inputs) { + if( minType instanceof TypeMem mem && mem._one ) { + // One object's memory travels as one value. Its unfinished loop + // Phi still belongs to the private-memory family. + PhiNode phi = new PhiNode(label,inputs); + phi._type = TypeMem.makePrivate(Type.BOTTOM); + return phi; + } return minType instanceof TypeMem mem ? mem._alias==1 ? new BulkMemPhiNode(label,inputs) @@ -67,7 +74,7 @@ public class PhiNode extends Node { return Type.TOP; // During parsing Phis have to be computed type pessimistically. if( r.inProgress() || in(nIns()-1)==null ) - return Type.BOTTOM; + return _type instanceof TypeMem mem && mem._one ? TypeMem.makePrivate(Type.BOTTOM) : Type.BOTTOM; // Set type to local top of the starting type Type t = Type.TOP; for( int i = 1; i < nIns(); i++ ) { @@ -94,7 +101,7 @@ public class PhiNode extends Node { return ti.same_but_slightly_wider_than(); } - return t; + return r instanceof LoopNode && t instanceof TypeMem mem ? mem.widen() : t; } @Override @@ -208,7 +215,7 @@ public class PhiNode extends Node { t = t.meet(ins[i]._type); } // Do not introduce an operand Phi mixing incompatible type families. - if( t==Type.BOTTOM ) { + if( t==Type.BOTTOM || t==TypeScalar.BOT ) { for( int i=1; i<ins.length; i++ ) addDep(ins[i]); cp.kill(); return null; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 8d0d56e9..eee1c150 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -142,7 +142,7 @@ public class RegionNode extends CFGNode { { addDep(use); if( data!=null ) addDep(data); return true; } } } else - { addDep(use); return true; } // Control user + { if( use!=null ) addDep(use); return true; } // Control user, including an external keep } return false; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 182adb19..f2972c91 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -77,22 +77,6 @@ public class ReturnNode extends CFGNode { if( ctrl()._type == Type.CONTROL && expr()._type == TypeScalar.BOT ) return Parser.error("Cannot return generic scalar",null); - // With no user constructor, <init> doubles as the public no-arg - // constructor. Required fields remain TOP in its private memory: a - // typed parser poison which deliberately emitted no Store or code. - if( ctrl()._type == Type.CONTROL && _fun.isInstance() ) { - TypeStruct self = ((TypeMemPtr)_fun.sig().arg(0))._obj; - if( !CodeGen.hasUserConstructor(self) && expr()._type instanceof TypeMem mem ) - for( Field fld : self._fields ) { - if( !(fld._t instanceof TypeNil tn && tn.notNull()) ) continue; - Type actual = mem._alias==1 && mem._t instanceof TypeStruct ts - ? ts.field(fld._fname)._t - : mem._alias==fld._alias ? mem._t : Type.TOP; - if( actual==Type.TOP || actual instanceof TypeNil atn && atn.nullable() ) - return Parser.error("'"+self._name+"' is not fully initialized, field '"+ - fld._fname+"' is only partially set in the constructor",null); - } - } return null; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 5fc2b8cd..1130cf44 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -209,9 +209,8 @@ public class ScopeNode extends MemMergeNode { return kx == -1 ? null : _kinds.at(kx); } - // Final fields are writable local values inside their own initializer or - // constructor. Final parameters, local variables, and captured bindings - // remain final. Use the same rule when deciding which loop Phis to build. + // Final fields are writable inside their own initializer or constructor. + // Final parameters, local variables, and captured bindings remain final. public boolean canInit(Var v) { int fx=enclosingFuncOrDecl(); Kind.Func fun=(Kind.Func)_kinds.at(fx); @@ -428,7 +427,6 @@ public class ScopeNode extends MemMergeNode { Var n = scope.var(i); if( n.isFRef() ) { // Loop body has forward refs Var v = new Var(nIns(),n._name,n.type(),n._final,n._loc,true); - v._uninit = n._uninit; _vars.add(v); addDef(scope.in(i)); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java index fe7d428c..47984ed6 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -88,15 +88,23 @@ public class StoreNode extends MemOpNode { // Sharpen memory value; required for narrowing stores where the parser // inserts zero/sign masking and somebody reads the TypeMem type. + // A source Load of an unwritten field is kept and checked separately; + // this declared bound does not excuse that earlier read. Type decl = declaredType(); + if( decl instanceof TypeMemPtr ptrType ) decl = ptrType.withPartial(TypeMemPtr.mayBePartial(val)); if( decl != Type.BOTTOM ) { assert decl != Type.TOP; val = val.join(decl); } + // A constructor can itself be a field. Its result memory contains + // that field again; retain the declared signature instead of unfolding + // successively sharper copies of its private-memory return type. + if( mem._one && decl instanceof TypeFunPtr ) val = decl; // A singleton class's final constant field lives in the static image. // Its precise memory slice is a constant too; ordinary peepholes can // replace this Store before scheduling or instruction selection. // A constant runtime value alone is not enough: mutable fields (notably // $init) still need their writes, and instance fields need allocation. Field fld = ptr._obj.field(_name); + if( fld==null && off() instanceof ConFldOffNode off ) fld = off._ts.field(_name); if( _alias!=1 && ptr._one && TypeStruct.startsClzPrefix(ptr._obj._name) && fld!=null && fld._final && decl.isConstant() ) return TypeMem.make(_alias,val,true,true,true,mem._escFs,mem._escAs).escapesFrom(val); @@ -106,7 +114,7 @@ public class StoreNode extends MemOpNode { // which is never does in a constructor. if( !_name.equals("[]") && mem._one ) // Just track the stored value - return TypeMem.make(_alias,val,true,false,_init,null,null).escapesFrom(val); + return TypeMem.make(_alias,val,true,false,fld==null ? _init : fld._final,null,null).escapesFrom(val); // Normal aliasing Store. assert mem._alias==1 || mem._alias==_alias; // Perfect aliasing @@ -319,6 +327,9 @@ public class StoreNode extends MemOpNode { public Parser.ParseException err() { Parser.ParseException err = super.err(); if( err != null ) return err; + if( TypeMemPtr.mayBePartial(val()._type) && + !(mem()._type instanceof TypeMem mem && mem._one && !mem._clz) ) + return Parser.error("Cannot store an incomplete object into an ordinary object",_loc); assert _size>0 || CodeGen.CODE._phase.ordinal() <= CodeGen.Phase.FinalizeIR.ordinal(); if( ptr()._type == Type.TOP ) // Dead store? return null; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java index 8405278c..b8db4f4c 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Allocations.java @@ -47,6 +47,7 @@ final class Allocations { if( clz==null ) throw P.error("Unknown struct type '" + ts._name + "'"); Field afld = clz.field("<new>"); + P.construction.allocation(afld==null ? null : (TypeFunPtr)afld._t,ctorArgs,P.loc()); Node alloc; if( afld != null ) { TypeFunPtr tfp = (TypeFunPtr)afld._t; @@ -67,7 +68,9 @@ final class Allocations { args.add(P.ctrl()); args.add(P.mem()); for( Node arg : ctorArgs ) args.add(arg.unkeep()); args.add(alloc); - return P.functions.functionCall(args); + Node result = P.functions.functionCall(args); + if( P.ctrl()._type==Type.XCONTROL ) return result; + return new ConstructNode(result,ctorArgs).peephole(); } private Ary<Node> constructorArgs() { @@ -83,7 +86,7 @@ final class Allocations { Field lenFld = ts.field("#" ); Field bodyFld = ts.field("[]"); - ConFldOffNode base = ConFldOffNode.make(ts, "[]"); + Node base = ConFldOffNode.make(ts, "[]"); int scale = ts.aryScale(); Node size = P.peep(new AddNode(base,P.peep(new ShlNode(null,len,P.con(scale))))); @@ -127,6 +130,11 @@ final class Allocations { // call this function; all layout, initialization and publication choices // are made here, where the complete struct and constructor are known. TypeFunPtr makeAllocator(TypeStruct ts, ReturnNode initRet, Field ctorFld) { + if( ctorFld==null ) { + Field legacy = ts.field(ts._name.substring(ts._name.lastIndexOf('.')+1).intern()); + if( legacy!=null && legacy._t instanceof TypeFunPtr sig && sig.nargs()>=2 && sig.arg(1) instanceof TypeMem ) + ctorFld = legacy; + } TypeFunPtr ctor = ctorFld==null ? null : (TypeFunPtr)ctorFld._t; int nargs = ctor==null ? 0 : ctor.nargs()-2; // Hide self and selfMem Type[] atypes = new Type[nargs]; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java new file mode 100644 index 00000000..799ca6fc --- /dev/null +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Construction.java @@ -0,0 +1,145 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.codegen.Iter; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; + +/** + * Field initialization is ordinary forward typing: New supplies Scalar.BOT + * fields in private memory, Store replaces a field, and Phi meets the incoming + * memories. Scalar.BOT survives a missing live arm; Integer.BOT describes an + * initialized integer. Loads and merged Returns inspect these types after the + * parser closes loops and compute() stabilizes. No backwards initialization walk. + * + * References have just a yes/no restriction. Constructor self and ^ parameters + * are incomplete. An allocation result is incomplete iff an actual argument is + * incomplete. Copies and Phis preserve this restriction. Only self may be read + * while incomplete; object-reference fields read from self conservatively remain + * incomplete. Arrays are born initialized and cannot contain incomplete refs. + * Ordinary calls and stores outside self require complete references. + * + * This permits cycles to be assembled but not traversed until the root new + * returns. A new with only complete arguments, including null, returns complete. + * A ^ formal is always restricted inside its constructor, even when a caller + * passes a complete argument. No field requirements are inferred. + * + * Incompleteness lives in TypeMemPtr, not a parser provenance graph. Ordinary + * Phis carry it around loops, conversions preserve it, and ConstructNode types + * each allocation result from its actual arguments. Source obligations retain + * their operands until the type fixed point, but hold no separate flow facts. + * + * The qualifier is a two-point lattice: complete meets incomplete to incomplete. + * Constructor self and ^ formals seed incomplete; a ^ formal stays restricted + * even if its known callers are complete. A ConstructNode wraps each source new + * and ORs the actual argument qualifiers. Thus new Child(self) is incomplete, + * while new Child(null) and new Child(oldParent) are complete, even though all + * three calls share the same constructor Return. The raw allocator result is + * complete after its own fields have been checked; ConstructNode adds the + * caller's restriction and disappears after source checking. + * + * Reading a pointer field through a completed receiver gives a completed view + * of that field too: its object's construction could only retain incomplete + * references from the enclosing construction. There is no group ID to clear. + * A read through incomplete self conservatively returns an incomplete reference + * (except initialized arrays), even when the stored value happens to be complete. + * Own-self access is identified by the receiver and its private memory, not by + * the nominal class: a ^ argument of the same class cannot use that exception. + * + * Iter.types also solves qualifier cycles optimistically. For p = null followed + * by p = new Link(p) in a loop, nothing introduces incompleteness, so the loop + * stays complete. A backedge carrying self makes the Phi and its uses incomplete. + * Both cases use the ordinary worklist; no recursive Load/Phi/Call query remains. + */ +final class Construction { + private final Parser P; + boolean _borrowed; // Source ^ parameters; separate compilation is still deferred. + private final Ary<Node> _kept = new Ary<>(Node.class); + private final Ary<Use> _uses = new Ary<>(Use.class); + private final Ary<LoadNode> _reads = new Ary<>(LoadNode.class); + Frame _frame; + + Construction(Parser P) { this.P = P; } + + static final class Frame { + final boolean _owner; + final Node _self; + Frame(boolean owner, Node self) { _owner = owner; _self = self; } + } + private record Use(Node ctrl, Node value, String operation, Lexer loc) {} + + Frame enter(FunNode fun, boolean owner) { + Frame old = _frame; + _frame = new Frame(owner,fun.parm(2)); + return old; + } + + private Node keep(Node n) { _kept.add(n.keep()); return n; } + + void complete(Node value, String operation, Lexer loc) { + if( !_frame._owner ) return; + _uses.add(new Use(keep(P.ctrl()),keep(value),operation,loc)); + } + + void ordinaryCall(Ary<Node> args, Lexer loc) { + TypeFunPtr sig = args.last()._type instanceof TypeFunPtr tfp ? tfp : null; + for( int i = 2; i<args.size()-1; i++ ) { + if( i==2 && sig!=null && sig.nargs()>0 && sig.arg(0)==TypePtr.PTR ) continue; + complete(args.at(i),"pass to an ordinary function",loc); + } + } + + Node memory(Node ptr, String field, Lexer loc) { + if( own(ptr) ) return selfMem(); + complete(ptr,"read field '"+field+"'",loc); + return P.mem(); + } + + Node loaded(LoadNode load) { + if( _frame._owner ) _reads.add((LoadNode)keep(load)); + return P.peep(load); + } + + void allocation(TypeFunPtr sig, Ary<Node> args, Lexer loc) { + if( !_frame._owner ) return; + for( int i = 0; i<args.size(); i++ ) + if( sig==null || i>=sig.nargs() || !(sig.arg(i) instanceof TypeMemPtr ptr && ptr._partial) ) + complete(args.at(i),"pass to a constructor parameter without '^'",loc); + } + + Node selfMem() { + Var mem = P._scope.lookup("#selfMem"); + return P._scope.in(P._scope.update(mem,null)); + } + + boolean own(Node ptr) { + while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr = ptr.in(1); + return _frame._owner && ptr==_frame._self; + } + + Node storeMemory(Node ptr) { return own(ptr) ? selfMem() : P.mem(); } + + void store(Node ptr, int alias, Node st, Node prior) { + if( own(ptr) ) P._scope.update("#selfMem",P.mergeAlias(prior,alias,st)); + else P.storeMem(st,alias,prior); + } + + void check() { + Iter.types(P._code); + for( LoadNode load : _reads ) + if( load.err()!=null ) throw load.err(); + for( Use use : _uses ) + if( !use.ctrl._type.isHigh() && TypeMemPtr.mayBePartial(use.value._type) ) + throw Parser.error("Cannot "+use.operation+" with an incomplete object",use.loc); + P.structs.checkInitFields(); + for( Node n : _kept ) n.unkeep(); + _kept.clear(); + _uses.clear(); + _reads.clear(); + } + + void checkSerializable() { + if( _borrowed ) + throw P.error("Separate compilation of constructors with '^' parameters is not supported yet"); + } +} diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java index 92e978b6..91955197 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Declarations.java @@ -65,7 +65,7 @@ final class Declarations { expr = externDecl(name,t); t = expr._type; // Upgrade declared type to the exact extern decl type } else if( P.structs.isConstructorDecl(name) ) { - expr = P.functions.parseConstructor(name); + expr = P.functions.parseConstructor(name,false); } else { expr = P.expressions.parseAssignment(); } @@ -126,7 +126,7 @@ final class Declarations { // Define a new name if( !P._scope.define(name,t,xfinal || fld_final,lift, loc) ) throw P.error("Redefining name '" + name + "'", loc); - P._scope.lookup(name)._uninit = uninit; + P.structs.declareField(P._scope.lookup(name),lift,uninit); return lift; } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java index d848b0e3..4d597b8d 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -35,32 +35,32 @@ final class Functions { // Parse other arguments P._lexer.skipWhiteSpace(); Lexer loc = P.loc(); // First argument location - parameters(ts,ids,finals); + parameters(ts,ids,finals,false); // Make a concrete function type, with a fidx TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),Type.BOTTOM,P._code.fidx(P._ref._cname)); ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); return new FunPtrNode(tfp,P._code._start,ret).peephole(); } - Node parseConstructor(String name) { + Node parseConstructor(String name, boolean explicit) { P.require("{"); Ary<Type> ts = new Ary<>(Type.class); Ary<String> ids = new Ary<>(String.class); BitSet finals = new BitSet(); TypeStruct self = P._scope.constructorSelf(); assert self != null; - ts.push(TypeMemPtr.make(Structs.constructorRecv(self))); + ts.push(TypeMemPtr.make(Structs.constructorRecv(self)).withPartial(true)); ids.push("self"); // Explicit constructors use the same hidden allocation arguments as // <init>: public memory is the call memory edge (index 1), followed by // self (index 2) and the private, unescaped object memory (index 3). - ts.push(TypeMem.makePrivate(self)); + ts.push(TypeMem.makePrivate(Type.BOTTOM)); ids.push("#selfMem"); P._lexer.skipWhiteSpace(); Lexer loc = P.loc(); - parameters(ts,ids,finals); - TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),TypeMem.makePrivate(self),P._code.fidx(P._ref._cname)); + parameters(ts,ids,finals,explicit); + TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),TypeMem.makePrivate(Type.BOTTOM),P._code.fidx(P._ref._cname)); Node[] preParse = P._scope.save(); ReturnNode ret = parseBody((self._name+"."+name).intern(),tfp,loc,finals,ids.asAry()); P._scope.restore(preParse); @@ -69,10 +69,16 @@ final class Functions { } // parameterList followed by the function arrow; callers seed hidden parameters. - private void parameters(Ary<Type> ts, Ary<String> ids, BitSet finals) { + private void parameters(Ary<Type> ts, Ary<String> ids, BitSet finals, boolean constructor) { while( true ) { Type t = P.types.parseType(); // Arg type if( t==null ) break; + if( P.match("^") ) { + if( !constructor || !(t instanceof TypeMemPtr ptr) || ptr._obj.isAry() ) + throw P.error("'^' requires a struct parameter of a constructor"); + t = ptr.withPartial(true); + P.construction._borrowed = true; + } finals.set(ids.size(),P.declarations.bindingFinal(t)); String id = P.requireId(); ts .push(t ); // Push type/arg pairs @@ -108,6 +114,7 @@ final class Functions { // Unkeep them all for( Node arg : args ) arg.unkeep(); + P.construction.ordinaryCall(args,site); return functionCall(args,site); } @@ -177,8 +184,8 @@ final class Functions { // - - If isInit, also incrementally extend the self-type. // If isInit // - upgrade and close the self-type - // - Gather fields and store values - // - <init> returns self, not last + // - Store class singleton fields; instance Stores already exist + // - <init> and user constructors return their current private memory // Unstack the {break,continue,return} scopes. ReturnNode parseBody( String funName, TypeFunPtr sig, Lexer loc, String[] ids) { @@ -200,8 +207,8 @@ final class Functions { int oldUID = P._code.UID(); // Used to approximate function size FunNode fun = enterFunction(funName,sig,loc,finals,ids); + Construction.Frame outerConstruction = P.construction.enter(fun,isCtor && !fun.isClz()); Node rpc = fun.parm(0); - if( isCtor && !isInit ) P.structs.constructorDefaults(typeName,fun,loc); if( fun.isClz() ) P.structs.beginClassInit(fun,loc); // Parse the function body. @@ -228,13 +235,13 @@ final class Functions { if( fun.isClz() ) { assert last!=null; } else if( isCtor ) { - last = fun.parm(3); + last = P.construction.selfMem(); } addReturn(last); // exit path is now dead (nothing live after a "return") } - if( isCtor ) - P.structs.upgradeSelfTypeAndStoreFields( typeName, fun.isClz(), self, fun.parm(3), isInit ); + if( isInit ) + P.structs.finishInitializer(typeName,fun.isClz(),self); // Build a return from the _returnScope. // Can be no returns for never-exit functions @@ -258,6 +265,7 @@ final class Functions { P.statements._continueScope = continueScope; P.statements._breakScope = breakScope; P._scope.pop(); + P.construction._frame = outerConstruction; return ret; } @@ -290,17 +298,19 @@ final class Functions { return fun; } Node addReturn(Node expr) { + if( P.construction._frame._owner ) expr = P.construction.selfMem(); expr.keep(); // Force the pending lazy bulk-memory Phi. P.mem(); // Force a pending lazy bulk-memory Phi - // For <init> and <clinit> - all fields in scope will be live-on-exit - // and stored into `self` and need to have lazy-phi's inserted. + // Class fields are still stored at exit. Instance fields already + // travel in expr's private memory; only their scope layout is retained. int lexN = P._scope.enclosingFuncOrDecl(); Kind.Func k = (Kind.Func)P._scope._kinds.at(lexN); if( FunNode.isInit(k._name) ) { int nestedLexSize = lexN+1 < P._scope.depth() ? P._scope._kinds.at(lexN+1)._lexSize : P._scope.nIns(); - for( int i = k._lexSize; i<nestedLexSize; i++ ) - P._scope.update(P._scope.var(i),null); + if( k._name.endsWith(".<clinit>") ) + for( int i = k._lexSize; i<nestedLexSize; i++ ) + P._scope.update(P._scope.var(i),null); if( _returnScope != null ) { Var vexpr = _returnScope._vars.pop(); Node oldX = _returnScope.removeLast(); @@ -312,12 +322,6 @@ final class Functions { _returnScope._vars.add(vexpr); _returnScope.addDef(oldX); } - } else if( P.structs.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 = P._scope._kinds.at(lexN-1)._lexSize+2; - for( int i = first; i<k._lexSize; i++ ) - P._scope.update(P._scope.var(i),null); } // No prior merge point? Just clone and hang on to it @@ -328,15 +332,12 @@ final class Functions { _returnScope.define("$expr", Conversions.inferredReturnType(expr._type), true, expr, null); } else { - // For <init> and <clinit> - ALL FIELDS IN LAST SCOPE are live - // and need to have lazy-phi's inserted. - - // And fields might not match.... will need matching Var/define with default values + // The initializer scopes have already been aligned above. int rlen = _returnScope.nIns()-1; RegionNode r = P.ctrl(new RegionNode(null, null,_returnScope.ctrl(), P._scope.ctrl()).init().keep()); _returnScope._merge(P._scope, r, rlen); Node oldExpr = _returnScope.in(rlen); - _returnScope.setDef(rlen,new PhiNode("$expr", r, oldExpr, expr).peephole()); + _returnScope.setDef(rlen,PhiNode.make("$expr",expr._type, r, oldExpr, expr).peephole()); P._code.add(r); _returnScope.ctrl(r.unkeep()); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java index ccc9ebdc..93c3932b 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -23,6 +23,10 @@ public class Parser { final Allocations allocations = new Allocations(this); final References references = new References(this); final Conversions conversions = new Conversions(this); + final Construction construction = new Construction(this); + + public void checkConstruction() { construction.check(); } + public void checkConstructionSerializable() { construction.checkSerializable(); } // Compile driver public final CodeGen _code; diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md b/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md index e3e94b97..d1125842 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/README.md @@ -15,11 +15,12 @@ productions to their entry points. | `Types.java` | Type syntax, qualified-name lookup, arrays, function types, and forward types. | | `Functions.java` | Function expressions, parameters, arguments, calls, and function entry/return graphs. | | `Structs.java` | Struct and constructor declarations, field discovery, and initialization checks. | +| `Construction.java` | Source checks for field initialization and incomplete references; its comment explains BOT fields, the TypeMemPtr qualifier, and allocation boundaries. | | `References.java` | Bare-name and field resolution, implicit receivers, assignments, and forward references. | | `Allocations.java` | Allocation expressions, strings, and declaration-side allocation helpers. | | `ControlFlow.java` | Guarded scope merging shared by `if`, `?:`, `&&`, and `||`. | | `Conversions.java` | Shared binding, field, and result conversions. | -| `Var.java` | Lexical binding metadata: name, type, scope slot, mutability, and initialization state. | +| `Var.java` | Lexical binding metadata: name, type, scope slot, and mutability. | Start with `Statements.parseStatement` or `Expressions.parseAssignment` to follow the grammar. Loop updates are parsed after their bodies, and declared constructor @@ -29,3 +30,7 @@ bodies after field discovery; `Lexer.skipTo` scans these deferred fragments. used by these components. Independent helpers live with their data: class-object names in `TypeStruct`, postfix operator encoding in `Lexer`, known field-offset creation in `ConFldOffNode.make`, and memory-alias labels in `ScopeNode.memName`. + +Instance constructor fields live in ordinary memory, with one hidden `#selfMem` +binding per activation. Forward field types use `TypeScalar.BOT` for missing +initialization; there are no per-field snapshots or store-all constructor exits. diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java index a22383cf..4851d8b5 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/References.java @@ -6,7 +6,6 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.ScopeNode.Kind; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; -import java.util.BitSet; /** Name and field access, receiver selection, and lvalue checks. */ final class References { @@ -63,20 +62,10 @@ final class References { return parseField(rvalue,id,pre); if( var._fref ) return P.expressions.parsePostfix(rvalue); - // A constructor may read the unfinished object, but each field it - // reads must already be initialized on every path. Read the current - // local value; other fields may still be waiting for their first write. - if( P.structs.inExplicitConstructor() && var._uninit && missingInit(rvalue,new BitSet()) ) - throw Parser.error("Field '"+id+"' might not be initialized",var._loc); - - // Check for an instance field load - int kx = P._scope.kindx(var); // Declaration scope - int fx = P._scope.enclosingFunction(); // Enclosing function scope - Kind kk = P._scope._kinds.at(kx); - Kind fk = P._scope._kinds.at(fx); - // Access instance field from 'self' - if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && fk instanceof Kind.Func method && !P.structs.inExplicitConstructor() ) - return parseField(P._scope.in(method._lexSize),id,pre); + Node fieldSelf = fieldSelf(var); + if( fieldSelf!=null ) return parseField(fieldSelf,id,pre); + int kx = P._scope.kindx(var); + int fx = P._scope.enclosingFunction(); // Check for a function-escaping variable; these require true // closures. Final constants are OK; final vars require a hidden var @@ -130,6 +119,19 @@ final class References { } Node assign(Var def, Node expr) { + Node self = fieldSelf(def); + if( self!=null ) { + TypeStruct ts = P.types.latestStruct(((TypeMemPtr)self._type)._obj); + Field fld = ts.field(def._name); + Node val = expr.keep(); + Node lift = P.conversions.convertExpr(val,def.type()); + Node mem = P.construction.storeMemory(self).keep(); + Node st = new StoreNode(P.loc(),fld._fname,fld._alias,fld._t,P.ctrl(),mem,self, + ConFldOffNode.make(ts,fld._fname),lift,P.construction.own(self)).peephole(); + P.construction.store(self,fld._alias,st,mem); + mem.unkeep(); + return val.unkeep(); + } String name = def._name; // Lift expression, based on type Type decl = def.type(); // Declared type @@ -141,23 +143,9 @@ final class References { int kx = P._scope.kindx(def); // Declaration scope int fx = P._scope.enclosingFunction(); // Enclosing function scope Kind kk = P._scope._kinds.at(kx); - Kind fk = P._scope._kinds.at(fx); - // Access instance field from 'self' - if( kx+1 == fx && kk instanceof Kind.Func inst && FunNode.isInstance(inst._name) && - fk instanceof Kind.Func method && !P.structs.inExplicitConstructor() ) { - // Named field offset on an unknown struct type - TypeMemPtr self = (TypeMemPtr)P._scope.var(fk._lexSize).type(); - TypeStruct sobj = (TypeStruct)Parser.TYPES.get(self._obj._name); - Field fld = sobj.field(name); - int alias = fld._alias; - Node ptr = P._scope.in(method._lexSize); - Node off = P.fldoff(ptr,name); - Node prior = P.mem().keep(); - Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), prior, ptr, off, lift, P.structs.inExplicitConstructor()).peephole().keep(); - P.storeMem(st,alias,prior); - st.unkeep(); - prior.unkeep(); - } + if( kx<fx && !(P.structs.inExplicitConstructor() && kx+1==fx && + kk instanceof Kind.Func owner && FunNode.isInstance(owner._name)) ) + P.construction.complete(lift,"store outside the construction group",P.loc()); lift.unkill(); // Return un-lifted expr @@ -181,7 +169,6 @@ final class References { } Node parseField(Node expr, String name, int pre, Lexer site) { - if( P.structs.inExplicitConstructor() && privateSelf(expr) ) return privateField(name,pre); // Keep expr across possible updates expr.keep(); @@ -246,16 +233,20 @@ final class References { if( pre==0 && P.matchOpx('=','=') ) { // Field assignment Node val = P.expressions.parseAssignment().keep(); + if( !P.construction.own(expr) ) { + P.construction.complete(expr,"write through an unfinished reference",site); + P.construction.complete(val,"store into an ordinary object",site); + } // Lift value for store Node lift = fld==null ? val : new ConvertNode(fld._t,val).peephole(); // Memory for store, post assignment expression - Node mem = P.mem(); + Node mem = P.construction.storeMemory(expr); // Store to field mem.keep(); - if( expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) + if( !P.construction.own(expr) && expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) throw P.error("Cannot modify final field '"+name+"'"); - Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), lift, false).peephole().keep(); - P.storeMem(st,alias,mem); + Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), lift, P.construction.own(expr)).peephole().keep(); + P.construction.store(expr,alias,st,mem); st.unkeep(); mem.unkeep(); @@ -263,26 +254,27 @@ final class References { } // Memory for load - Node mem = P.mem(); + Node mem = P.construction.memory(expr,name,site); // Loading from a constant array, the declared type is the // meet-over-elements and not the array itself. if( name=="[]" && decl instanceof TypeConAry conary ) decl = conary.elem(); // Load field - Node load = P.peep(new LoadNode(P.loc(),name, alias, P.ctrl(), mem, expr, off)); + Node load = P.construction.loaded(new LoadNode(P.loc(),name,alias,P.ctrl(),mem,expr,off)); // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; if( ch!=0 ) { + if( !P.construction.own(expr) ) P.construction.complete(expr,"write through an unfinished reference",site); if( fld!=null && decl==Type.BOTTOM ) throw P.error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor" ); Node op = P.expressions.opAssign(ch,load, decl ).keep(); mem.keep(); - if( expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) + if( !P.construction.own(expr) && expr._type instanceof TypeMemPtr view && view._ro && P.ctrl()._type!=Type.XCONTROL ) throw P.error("Cannot modify final field '"+name+"'"); - Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); - P.storeMem(st,alias,mem); + Node st = new StoreNode(P.loc(), name, alias, decl, P.ctrl(), mem, expr.unkeep(), off.unkeep(), op, P.construction.own(expr)).peephole().keep(); + P.construction.store(expr,alias,st,mem); st.unkeep(); mem.unkeep(); @@ -300,37 +292,14 @@ final class References { return P._scope.in(P._scope.update(P._scope.var(selfx),null)); } - private boolean privateSelf(Node ptr) { - while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr = ptr.in(1); - Node self = defaultSelf(); - while( self instanceof ConvertNode || self instanceof ReadOnlyNode || self instanceof GuardNode ) self = self.in(1); - return ptr==self; - } - - // An explicit self.x read sees the same current value as bare x. Loading - // the allocation here would miss updates still held in local SSA values. - private Node privateField(String name, int pre) { - int idx = P.structs.fieldVarIdxBefore(P._scope._kinds.at(P._scope.enclosingFuncOrDecl())._lexSize,name); - if( idx<0 ) throw P.error("Cannot resolve field '"+name+"'"); - Var v = P._scope.var(idx); - if( pre==0 && P.matchOpx('=','=') ) { - checkSharedFunction(v); - Node value = P.expressions.parseAssignment().keep(); - P._scope.update(v,P.conversions.convertExpr(value,v.type())); - return value.unkeep(); - } - Node value = P._scope.in(P._scope.update(v,null)); - if( v._uninit && missingInit(value,new BitSet()) ) - throw Parser.error("Field '"+name+"' might not be initialized",v._loc); - char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; - if( ch!=0 ) { - checkSharedFunction(v); - Node op = P.expressions.opAssign(ch,value,v.type()); - P._scope.update(v,op); - if( pre!=0 && Lexer.postfix(ch) ) value.unkeep(); - return pre==0 && Lexer.postfix(ch) ? value.unkeep() : op; - } - return P.expressions.parsePostfixMethod(value,defaultSelf()); + // Fields are lvalues in memory, including inside their initializer and + // explicit constructor. Scope slots retain declaration metadata only. + private Node fieldSelf(Var var) { + int kx = P._scope.kindx(var), fx = P._scope.enclosingFuncOrDecl(); + ScopeNode.Kind kind = P._scope._kinds.at(kx); + if( !(kind instanceof Kind.Func inst) || !FunNode.isInstance(inst._name) || var._idx<inst._lexSize+2 ) return null; + if( kx==fx || kx+1==fx ) return defaultSelf(); + return null; } private void checkSharedFunction(Var v) { @@ -338,20 +307,6 @@ final class References { throw P.error("Cannot reassign shared function '"+v._name+"'"); } - // A loop Phi is temporarily bottom before its backedge is parsed. That is - // not an unwritten field: follow its live inputs to the actual defaults. - private boolean missingInit(Node value, BitSet seen) { - if( value==null || seen.get(value._nid) ) return false; - seen.set(value._nid); - if( value instanceof PhiNode phi && !(value instanceof ParmNode) ) { - for( int i = 1; i<phi.nIns(); i++ ) - if( phi.region().in(i)!=null && phi.region().in(i)._type!=Type.XCONTROL && missingInit(phi.in(i),seen) ) - return true; - return false; - } - return !Structs.initialized(value._type); - } - Ary<FRefNode> resolve() { // All still-unresolved forward refs // should immediately resolve to a file-based name which is a Simple diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java index 57b43715..3360d85e 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Structs.java @@ -61,6 +61,8 @@ final class Structs { // This is basically sugar for "val CLZNAME = <init>" // and is a nicer version of updateSelfAsFieldsDiscovered. P._scope.define(typeName, sig, true, new FunPtrNode(sig,P._code._start,ret).peephole(), P.loc()); + Var binding = P._scope.lookup(typeName); + declareField(binding,P._scope.in(binding),false); P.require("}"); return P.require(P._code.ZERO,";"); @@ -81,7 +83,7 @@ final class Structs { if( _pendingCtor!=null ) throw P.error("Redefining constructor '"+name+"'"); _pendingCtor = new Constructor(name,P.loc()); // Parse the body after all field declarations are known, so self.x - // and x share a local slot even when x is declared below this body. + // and x resolve the same field even when x is declared below this body. P.require("{"); P._lexer.skipTo('{','}',"constructor body"); P.require("}"); @@ -101,7 +103,7 @@ final class Structs { private void defineConstructor(String name) { TypeStruct self = P._scope.constructorSelf(); - Node ctor = P.functions.parseConstructor(name); + Node ctor = P.functions.parseConstructor(name,true); TypeFunPtr sig = (TypeFunPtr)ctor._type; String clzName = TypeStruct.addClzPrefix(self._name); TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); @@ -139,7 +141,6 @@ final class Structs { // Struct decls look like function bodies. Parse function body normally. ReturnNode ret = P.functions.parseBody(fname,sig,P.loc(),ids); - if( !isClz ) checkInitFields(ret); // Unwind global state. P.ctrl(oldCtrl.unkeep()); P.mem (oldMem .unkeep()); @@ -149,13 +150,13 @@ final class Structs { // <cl/init> signature: { self arg/selfMem -> BOT/selfMem } // Self-memory is the rare *private* (never aliased) memory for the new object. private TypeFunPtr structInitSig( boolean isClz, TypeStruct tself ) { - // Private uninitialized memory from new object, no escaped values. - TypeMem privMem = isClz ? null : TypeMem.make(1,tself,true,isClz,false,null,null); - Type targ = isClz ? TypeInteger.BOT : privMem; + // One object, unknown contents. The signature must not promise that + // its declared field values have already been supplied. + Type targ = isClz ? TypeInteger.BOT : TypeMem.makePrivate(Type.BOTTOM); // Return for private memory has to name all escaped fields, which are not known yet. // Escape ALL fields, and sharpen later. - Type tret = isClz ? Type.BOTTOM : TypeMem.makePrivate(tself); - Type[] targs = new Type[]{ TypeMemPtr.make((byte)2,tself,isClz), targ }; + Type tret = isClz ? Type.BOTTOM : TypeMem.makePrivate(Type.BOTTOM); + Type[] targs = new Type[]{ TypeMemPtr.make((byte)2,tself,isClz).withPartial(!isClz), targ }; // FIDX for FREFs is in the global namespace, needs the correct clz name. String clzBare = tself._name; int order = 3; // 3 is always the <init> order, 2nd in the file just behind the <clinit> @@ -188,72 +189,58 @@ final class Structs { return nvar; } - void upgradeSelfTypeAndStoreFields( String typeName, boolean isClz, ParmNode self, ParmNode smem, boolean upgrade ) { + void finishInitializer( String typeName, boolean isClz, ParmNode self ) { int lex = P._scope.klast()._lexSize; assert P._scope.var(lex)._name=="self"; TypeStruct tself = (TypeStruct)Parser.TYPES.get(typeName); int base = lex+2; // Skip ctrl, mem - if( upgrade ) { - // Default <init>/<clinit> defines the struct and can sharpen fields. - // A named constructor only initializes the already-closed struct. - for( int i = 0; i<tself.nkids(); i++ ) { - Field tfld = tself._fields[i]; - int vidx = fieldVarIdx(base,tfld._fname); - if( vidx == -1 ) - continue; - Var v = P._scope.var(vidx); - // Forward-ref fields where placed in tself but will get promoted - // to an outer scope - and should not be in tself. - if( v._fref ) - tself = tself.remove(i--); - else if( v.type() != tfld._t ) { - assert v.type().isa(tfld._t); - tself = tself.replace( tfld.makeFrom( v.type() ) ); - } + // Default <init>/<clinit> defines the struct and can sharpen fields. + // A named constructor only initializes the already-closed struct. + for( int i = 0; i<tself.nkids(); i++ ) { + Field tfld = tself._fields[i]; + int vidx = fieldVarIdx(base,tfld._fname); + if( vidx == -1 ) + continue; + Var v = P._scope.var(vidx); + // Forward-ref fields where placed in tself but will get promoted + // to an outer scope - and should not be in tself. + if( v._fref ) + tself = tself.remove(i--); + else if( v.type() != tfld._t ) { + assert v.type().isa(tfld._t); + tself = tself.replace( tfld.makeFrom( v.type() ) ); } - - // Close Struct type after parsing struct body. - Parser.TYPES.put( tself._name, tself = tself.close() ); - // Improve self, selfMem types in scope. - // Class self-type is a singleton pointer. Instance <init> receives the - // broad allocation pointer, while private memory tracks initialized fields. - self._declaredType = self._type = isClz ? TypeMemPtr.make((byte)2,tself,true) : TypeMemPtr.make(constructorRecv(tself)); - FunNode fun = self.fun(); - fun.setSig(fun.sig().makeFrom(self._type,0)); - if( !isClz ) // <init> returns upgraded private memory - smem._declaredType = smem._type = TypeMem.makePrivate(tself); } + // Close Struct type after parsing struct body. + Parser.TYPES.put( tself._name, tself = tself.close() ); + // Improve the receiver type in scope. + // Class self-type is a singleton pointer. Instance <init> receives the + // broad allocation pointer, while private memory tracks initialized fields. + self._declaredType = self._type = isClz ? TypeMemPtr.make((byte)2,tself,true) : TypeMemPtr.make(constructorRecv(tself)).withPartial(true); + FunNode fun = self.fun(); + fun.setSig(fun.sig().makeFrom(self._type,0)); + // 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 if( P.functions._returnScope==null ) return; - // A MemMerge to gather field updates as stores. Classes update the - // normal public memory. <init> updates the private memory that got - // passed in - is treated like a normal argument and not like memory. - Node mmm = isClz ? P.functions._returnScope.mem(1) : smem; + // Class singleton fields retain their store-at-exit path. Instance + // initializers already returned their current private memory. + if( !isClz ) return; // Instance fields already have their Stores. + Node mmm = P.functions._returnScope.mem(1); // Store constructor results into fields for( int i = 0; i<tself.nkids(); i++ ) { Field fld = tself._fields[i]; - int vidx = upgrade - ? fieldVarIdx(base,fld._fname) - : fieldVarIdxBefore(lex,fld._fname); + int vidx = fieldVarIdx(base,fld._fname); if( vidx == -1 ) continue; Var v = P._scope.var(vidx); if( v._fref || v._extern!=0 ) continue; // C storage has no Simple initializer Node val = P.functions._returnScope.in(vidx); - // Preserve a missing field in the returned private memory. A - // numeric conversion would turn BOTTOM into an ordinary number - // type, hiding a path that never assigned the field. - if( !isClz && v._uninit && !initialized(val._type) ) { - TypeStruct missing = (TypeStruct)((TypeMem)smem._declaredType)._t; - smem._declaredType = smem._type = TypeMem.makePrivate(missing.addOrUpdate(fld.makeFrom(Type.TOP))); - continue; - } // A numeric merge can still be untyped while parsing. Retain its // declared conversion at the helper boundary, as assignments do. if( fld._t instanceof TypeInteger || fld._t instanceof TypeFloat ) @@ -266,18 +253,18 @@ final class Structs { } mmm = mmm.peephole(); - if( !isClz ) - // Stuff private mem into normal expression return value. - P.functions._returnScope.setDef(P.functions._returnScope.nIns()-1,mmm); - else - // Parser memory is one opaque whole-memory edge. Publish the - // completed class-field aggregate as the <clinit> return memory. - P.functions._returnScope.mem(mmm); - //_code.add(mmm); + P.functions._returnScope.mem(mmm); } // addReturn already merged every exit. Inspect the completed helpers, // after parsing has discovered all fields and torn down their scopes. + void checkInitFields() { + P._code._stop.walk(n -> { + if( n instanceof ReturnNode ret && ret.fun().isInstance() ) checkInitFields(ret); + return null; + }); + } + private void checkInitFields(ReturnNode init) { if( init.ctrl()._type.isHigh() || init.expr()._type.isHigh() ) return; TypeStruct ts = ((TypeMemPtr)init.fun().sig().arg(0))._obj; @@ -294,32 +281,33 @@ final class Structs { private void checkInitFields(TypeStruct ts, ReturnNode init, ReturnNode ret) { if( ret.ctrl()._type.isHigh() || ret.expr()._type.isHigh() ) return; - TypeStruct fields = (TypeStruct)((TypeMem)ret.expr()._type)._t; - TypeStruct defaults = (TypeStruct)((TypeMem)init.expr()._type)._t; for( Field fld : ts._fields ) { if( fld._extern ) continue; - Field actual = fields.field(fld._fname); - if( actual==null ) actual = defaults.field(fld._fname); - if( actual._t==Type.TOP ) + Type mem = ret.expr()._type; + Field actual = mem instanceof TypeMem tm && tm._t instanceof TypeStruct shape ? shape.field(fld._fname) : null; + if( actual==null || actual._t==TypeScalar.BOT || actual._t==Type.BOTTOM ) throw Parser.error("'"+ts._name+"' is not fully initialized, field '"+fld._fname+ (ret==init ? "' needs to be set in a constructor" : "' is only partially set in the constructor"),ret.fun()._loc); } } - // Seed the constructor-local SSA slots from the declaration initializer. - void constructorDefaults(String typeName, FunNode fun, Lexer loc) { - int lex = P._scope.klast()._lexSize; - TypeStruct shape = (TypeStruct)Parser.TYPES.get(typeName); - for( Field fld : shape._fields ) { - int idx = fieldVarIdxBefore(lex,fld._fname); - if( idx<0 ) continue; - Var v = P._scope.var(idx); - if( v._fref || v._extern!=0 || v._uninit || P._scope.in(v)._type.isConstant() ) continue; - Node value = P.conversions.convertExpr( - new LoadNode(loc,fld._fname,fld._alias,P.ctrl(),fun.parm(3),fun.parm(2),ConFldOffNode.make(shape,fld._fname)).peephole(),v.type()); - P._scope.update(v,value); - } + // Instance declarations establish field metadata and emit their default + // Stores immediately. Required fields emit no Store until assigned. + void declareField(Var var, Node value, boolean uninit) { + if( !(P._scope.klast() instanceof Kind.Func kind) || !FunNode.isInstance(kind._name) ) return; + TypeStruct self = P._scope.constructorSelf(); + TypeStruct shape = (TypeStruct)Parser.TYPES.get(self._name); + Field old = shape.field(var._name); + Field fld = old==null ? Field.make(var._name,var.type(),P._code.alias(P._ref._cname),var._final) : old.makeFrom(var.type()); + Parser.TYPES.put(shape._name,shape = shape.addOrUpdate(fld)); + if( uninit || var._extern!=0 ) return; + Node ptr = P.references.defaultSelf(); + Node mem = P.construction.selfMem().keep(); + Node st = new StoreNode(var._loc,fld._fname,fld._alias,fld._t,P.ctrl(),mem,ptr, + ConFldOffNode.make(shape,fld._fname),value,true).peephole(); + P.construction.store(ptr,fld._alias,st,mem); + mem.unkeep(); } void beginClassInit(FunNode fun, Lexer loc) { @@ -343,14 +331,6 @@ final class Structs { prior.unkeep(); } - // Required-field values must be initialized before conversion for storage. - static boolean initialized(Type t) { - // Can't be BOTTOM, that means explicit not initialized. - // Can't be high (initialized to an error) - // Can't be left null and declared not-null. - return t!=Type.BOTTOM && !t.isHigh() && (!(t instanceof TypeNil tn) || tn.notNull()); - } - private int fieldVarIdx( int base, String name ) { for( int i = base; i<P._scope.nIns(); i++ ) if( P._scope.var(i)._name == name ) @@ -358,16 +338,6 @@ final class Structs { return -1; } - // Named constructors update field Vars from the enclosing initializer - // scope. Constructor arguments and locals begin at limit and must not - // shadow the field state gathered into private memory. - int fieldVarIdxBefore( int limit, String name ) { - for( int i = limit-1; i>=0; i-- ) - if( P._scope.var(i)._name == name ) - return i; - return -1; - } - boolean isConstructorDecl(String name) { TypeStruct self = P._scope.constructorSelf(); return self != null && name == initFieldName(self._name); diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java index 970b5a50..3cb474b1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Types.java @@ -73,6 +73,7 @@ final class Types { // Check valid forward ref, after parsing all the type extra bits. // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax int old2 = P.pos(); + P.match("^"); // Constructor parameter qualifier; parsed by Functions. if( !P.match("!") ) P.match("~"); String id = P._lexer.matchId(); if( !(P.peek(',') || P.peek(';') || P.peek('=') || P.match("->")) || id==null ) diff --git a/chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java b/chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java index 7d3be3c2..ddbb91d8 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/parser/Var.java @@ -16,9 +16,6 @@ public class Var { private Type _type; // Declared type public boolean _final; // Final field public boolean _fref; // Forward ref - // Parser-only definite-initialization marker. The current binding's - // nullable type carries the path-sensitive state through SSA merges. - public boolean _uninit; public int _extern; // C storage alias; zero for ordinary variables public Lexer _loc; // Source location @@ -49,6 +46,6 @@ public class Var { } @Override public String toString() { - return (_fref ? "FREF " : "")+(_uninit ? "UNINIT " : "")+_type.toString()+(_final ? " ": " !")+_name; + return (_fref ? "FREF " : "")+_type.toString()+(_final ? " ": " !")+_name; } } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 278a3ea0..c72740a9 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -79,6 +79,15 @@ public class TypeMem extends Type { public static TypeMem makePrivate(Type t) { return make(1,t,true,false,false,escapeFIDX(XInt.EMPTY,t), escapeAlias(XInt.EMPTY,t)); } public TypeMem makeFrom(int alias) { return make(alias,_t,_one,_clz,_final,_escFs,_escAs); } + // Widen numeric fields at cyclic memory merges just as scalar Phis do. + public TypeMem widen() { + if( !_one || !(_t instanceof TypeStruct ts) ) return this; + TypeStruct wide = ts; + for( Field fld : ts._fields ) + if( fld._t instanceof TypeInteger ti && !ti.isHigh() && !ti.isConstant() ) + wide = wide.replace(fld.makeFrom(ti.same_but_slightly_wider_than())); + return wide==ts ? this : make(_alias,wide,_one,_clz,_final,_escFs,_escAs); + } public TypeMem makeFrom(int[] fidxes, int[] aliases) { return make(_alias,_t,_one,_clz,_final,fidxes,aliases); } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 175b1c63..943710d1 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -29,13 +29,16 @@ public class TypeMemPtr extends TypeNil { public TypeStruct _obj; // Deep read-only access through this pointer; independent of slot finality. public boolean _ro; + // This reference may still depend on unfinished construction. Independent + // two-point lattice: meet ORs the restriction, dual complements it. + public boolean _partial; public boolean _one; // Singleton pointer value; the pointer itself is constant. public boolean _pub; // Escaped/public pointer. False means constructor-private. private static final Ary<TypeMemPtr> FREE = new Ary<>(TypeMemPtr.class); private TypeMemPtr(byte nil, TypeStruct obj, boolean one, boolean pub) { super(TMEMPTR,nil); init(nil,obj,one,pub); } - private TypeMemPtr init(byte nil, TypeStruct obj, boolean one, boolean pub) { _nil=nil; _obj=obj; _ro=obj==TypeStruct.BOT; _one=one; _pub=pub; return this; } + private TypeMemPtr init(byte nil, TypeStruct obj, boolean one, boolean pub) { _nil = nil; _obj = obj; _ro = obj==TypeStruct.BOT; _partial = obj==TypeStruct.BOT; _one = one; _pub = pub; return this; } // Return a filled-in TypeMemPtr; either from free list or alloc new. static TypeMemPtr malloc(byte nil, TypeStruct obj, boolean one, boolean pub) { return FREE.isEmpty() ? new TypeMemPtr(nil,obj,one,pub) : FREE.pop().init(nil,obj,one,pub); @@ -46,10 +49,10 @@ public class TypeMemPtr extends TypeNil { return make(nil,obj,one,true); } public static TypeMemPtr make(byte nil, TypeStruct obj, boolean one, boolean pub) { - return make(nil,obj,one, pub,obj==TypeStruct.BOT); + return make(nil,obj,one,pub,obj==TypeStruct.BOT,obj==TypeStruct.BOT); } - private static TypeMemPtr make(byte nil, TypeStruct obj, boolean one, boolean pub, boolean ro) { - TypeMemPtr tmp = malloc(nil, obj, one, pub).access(ro); + private static TypeMemPtr make(byte nil, TypeStruct obj, boolean one, boolean pub, boolean ro, boolean partial) { + TypeMemPtr tmp = malloc(nil, obj, one, pub).access(ro).partial(partial); TypeMemPtr t2 = tmp.intern(); if( t2==tmp ) return tmp; return VISIT.isEmpty() ? t2.free(tmp) : t2.delayFree(tmp); @@ -72,21 +75,33 @@ public class TypeMemPtr extends TypeNil { public static TypeMemPtr makeNullable(TypeStruct obj) { return make((byte)3, obj); } public static TypeMemPtr makePrivate (TypeStruct obj) { return make((byte)2, obj, false, false); } - public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one, _pub,_ro); } + public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one, _pub,_ro,_partial); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } /** 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(_nil,_obj._makeStorage(),false,true,_ro); } - @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one, _pub,_ro); } + @Override TypeMemPtr _makeStorage() { return make(_nil,_obj._makeStorage(),false,true,_ro,_partial); } + @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one, _pub,_ro,_partial); } @Override public Type nonZero() { return makeFrom((byte)(_nil <= 1 ? 1 : 2)); } private TypeMemPtr access(boolean ro) { _ro=ro; return this; } + private TypeMemPtr partial(boolean partial) { _partial = partial; return this; } + + public TypeMemPtr withPartial(boolean partial) { + return partial==_partial ? this : make(_nil,_obj,_one,_pub,_ro,partial); + } + + // Conservative on unresolved scalar/pointer families; null is complete. + public static boolean mayBePartial(Type t) { + return t instanceof TypeMemPtr ptr ? ptr._partial + : t==Type.BOTTOM || t==TypeScalar.BOT || (t instanceof TypePtr && !t.isHigh()); + } public TypeMemPtr withAccess(boolean ro) { if( _ro==ro ) return this; TypeMemPtr ptr = malloc(_nil, _obj, _one, _pub); ptr._ro = ro; + ptr._partial = _partial; TypeMemPtr res = ptr.intern(); if( res==ptr ) return ptr; return VISIT.isEmpty() ? res.free(ptr) : res.delayFree(ptr); @@ -109,7 +124,7 @@ public class TypeMemPtr extends TypeNil { public static final TypeMemPtr NOTBOT = make((byte)2,TypeStruct.BOT); public static final TypeMemPtr TEST= make((byte)2, TypeStruct.TEST); - public static void gather(ArrayList<Type> ts) { ts.add(NOTBOT); ts.add(BOT); ts.add(TEST); ts.add(TEST.makeRO()); } + public static void gather(ArrayList<Type> ts) { ts.add(NOTBOT); ts.add(BOT); ts.add(TEST); ts.add(TEST.makeRO()); ts.add(TEST.withPartial(true)); ts.add(TEST.withPartial(true).makeRO()); } @Override public TypeNil xmeet(Type t) { @@ -118,28 +133,28 @@ public class TypeMemPtr extends TypeNil { // Can't keep _one if mixing two unequal singletons; the result is not // either singleton. Once either side is public, the meet is public. boolean one = _one && that._one && (_obj==that._obj || !(_obj.isConAry() || that._obj.isConAry())); - return make(xmeet0(that), (TypeStruct)_obj.meet(that._obj), one, _pub | that._pub,_ro | that._ro); + return make(xmeet0(that), (TypeStruct)_obj.meet(that._obj), one, _pub | that._pub,_ro | that._ro, _partial | that._partial); } @Override - TypeMemPtr xdual() { return malloc( dual0(), _obj.dual(), !_one, !_pub).access(!_ro); } + TypeMemPtr xdual() { return malloc( dual0(), _obj.dual(), !_one, !_pub).access(!_ro).partial(!_partial); } @Override TypeMemPtr rdual() { if( _dual!=null ) return dual(); assert !_terned; - TypeMemPtr d = malloc(dual0(), null, !_one, !_pub).access(!_ro); + TypeMemPtr d = malloc(dual0(), null, !_one, !_pub).access(!_ro).partial(!_partial); (_dual = d)._dual = this; // Cross link duals d._obj = _obj._terned ? _obj.dual() : _obj.rdual(); return d; } // RHS is NIL; do not deep-dual when crossing the center line - @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj,false,true,_ro); } + @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj,false,true,_ro,_partial); } @Override boolean _isConstant() { return _one; } @Override boolean _isFinal() { return _ro; } @Override TypeMemPtr _makeRO() { return withAccess(true); } - @Override TypeMemPtr _close( String name, HashMap<String, Type> TYPES ) { return malloc(_nil,_obj._close(name, TYPES ),_one,_pub).access(_ro); } + @Override TypeMemPtr _close( String name, HashMap<String, Type> TYPES ) { return malloc(_nil,_obj._close(name, TYPES ),_one,_pub).access(_ro).partial(_partial); } @Override Type _upgradeType(HashMap<String,Type> TYPES) { return makeFrom((TypeStruct)_obj._upgradeType(TYPES)); @@ -147,47 +162,48 @@ public class TypeMemPtr extends TypeNil { @Override public int log_size() { return 3; } // (1<<3)==8-byte pointers - @Override int hash() { return (_ro ? 8192 : 0) ^ _obj.hashCode() ^ super.hash() ^ (_one ? 2048 : 0) ^ (_pub ? 4096 : 0); } + @Override int hash() { return (_partial ? 16384 : 0) ^ (_ro ? 8192 : 0) ^ _obj.hashCode() ^ super.hash() ^ (_one ? 2048 : 0) ^ (_pub ? 4096 : 0); } @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _ro==ptr._ro && super.eq(ptr) && _one == ptr._one && _pub == ptr._pub && _obj == ptr._obj; + return _partial==ptr._partial && _ro==ptr._ro && super.eq(ptr) && _one == ptr._one && _pub == ptr._pub && _obj == ptr._obj; } @Override boolean cycle_eq(Type t) { if( t._type != TMEMPTR ) return false; TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _ro==ptr._ro && super.eq(ptr) && _one == ptr._one && _pub == ptr._pub && _obj.cycle_eq(ptr._obj); + return _partial==ptr._partial && _ro==ptr._ro && super.eq(ptr) && _one == ptr._one && _pub == ptr._pub && _obj.cycle_eq(ptr._obj); } @Override public int nkids() { return 1; } @Override public Type at( int idx ) { return _obj; } @Override public void set( int idx, Type t ) { _obj = (TypeStruct)t; } - // Reserve tags for null/not, one/general, public/private and read-only access - @Override int TAGOFF() { return 16; } + // Reserve tags for null/not, one/general, public/private and read-only and incomplete access + @Override int TAGOFF() { return 32; } @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { assert _nil>=2; baos.write(TAGOFFS[_type] + (_nil==2 ? 0 : 1) + (!_one ? 0 : 2) + (!_pub ? 0 : 4) - + (!_ro ? 0 : 8) ); + + (!_ro ? 0 : 8) + + (!_partial ? 0 : 16) ); } static TypeMemPtr packed( int tag, BAOS bais ) { - return malloc((byte)((tag&1)+2),null,(tag&2)==2,(tag&4)==4).access((tag&8)==8); + return malloc((byte)((tag&1)+2),null,(tag&2)==2,(tag&4)==4).access((tag&8)==8).partial((tag&16)==16); } @Override public String str() { if( this==BOT ) return "PtrBot"; if( this==TOP ) return "PtrTop"; if( this== NOTBOT) return "*void"; - return x()+"*"+(_obj==null?"---":_obj.str())+q(); + return (_partial ? "^" : "")+x()+"*"+(_obj==null?"---":_obj.str())+q(); } @Override SB _print(SB sb, BitSet visit, boolean html ) { if( this==BOT ) return sb.p("PtrBot"); if( this==TOP ) return sb.p("PtrTop"); if( this== NOTBOT) return sb.p("*void"); - return _obj.print(sb.p(x()).p("*"),visit,html).p(q()); + return _obj.print(sb.p(_partial ? "^" : "").p(x()).p("*"),visit,html).p(q()); } } diff --git a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 9c0c9693..d0ac55aa 100644 --- a/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter29/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -103,7 +103,7 @@ public class TypeStruct extends Type { for( Field f : _fields ) if( f._fname.charAt(0) != '_' && // Skip private fields. !hiddenInit(f) && // Skip private allocation helper. - f._t != Type.TOP ) // Skip uninit fields + f._t != Type.TOP && f._t != TypeScalar.TOP ) // Skip unreachable values xs[XInt.idx(f._alias)] |= XInt.mask(f._alias); return (_aliases=XInt.intern(xs)); } @@ -116,10 +116,10 @@ public class TypeStruct extends Type { assert _terned; int[] xs = XInt.EMPTY; for( Field f : _fields ) - if( f._fname.charAt(0) != '_' && // Skip private fields. - !hiddenInit(f) && // Skip private allocation helper. - f._t instanceof TypeFunPtr tfp ) // Looking for TFP - xs = XInt.meet(xs,tfp._fidxs); + if( f._fname.charAt(0) != '_' && !hiddenInit(f) ) { + if( f._t==TypeScalar.BOT || f._t==Type.BOTTOM ) return (_fidxs = XInt.FULL); + if( f._t instanceof TypeFunPtr tfp ) xs = XInt.meet(xs,tfp._fidxs); + } return (_fidxs = xs); } @@ -156,8 +156,7 @@ public class TypeStruct extends Type { Field[] fs = new Field[_fields.length]; for( int i=0; i<_fields.length; i++ ) { if( _fields[i]._extern ) { fs[i] = _fields[i]; continue; } - Type zero = _fields[i]._t.makeZero(); - fs[i] = _fields[i].makeFrom(_fields[i]._t != Type.BOTTOM && zero.isa(_fields[i]._t) ? zero : Type.TOP); + fs[i] = _fields[i].makeFrom(TypeScalar.BOT); } return make(_name,_open,_fref,fs); } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java index e912f224..b28a6af3 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/ArithNodeTest.java @@ -9,6 +9,29 @@ import org.junit.Test; import static org.junit.Assert.*; public class ArithNodeTest { + @Test public void testConstantFoldsRequireInitializedInputs() { + new CodeGen("return 0;"); + Node x = ConstantNode.seed(TypeScalar.BOT); + Node zero = ConstantNode.seed(TypeInteger.ZERO); + for( Node op : new Node[]{new MulNode(x,zero,(byte)1),new AndNode(null,x,zero), + new SubNode(x,x,(byte)1),new BoolNode.EQ(x,x,(byte)1), + new BoolNode.NE(x,x,(byte)1),new BoolNode.ULT(x,x),new NotNode(x)} ) { + assertSame(op.label(),TypeScalar.BOT,op.compute()); + Node replacement = op.idealize(); + assertTrue(op.label(),replacement==null || !replacement.compute().isConstant()); + } + // Once the family is known, compute owns the annihilator fold. + x._type = TypeInteger.BOT; + assertSame(TypeInteger.ZERO,new MulNode(x,zero,(byte)1).compute()); + assertSame(TypeInteger.TRUE,new BoolNode.EQ(x,x,(byte)1).compute()); + assertSame(TypeInteger.FALSE,new BoolNode.NE(x,x,(byte)1).compute()); + assertSame(TypeInteger.FALSE,new BoolNode.ULT(x,x).compute()); + x._type = TypeFloat.F64; + assertSame(TypeInteger.BOOL,new BoolNode.EQ(x,x,(byte)2).compute()); + x._type = TypeFloat.constant(Double.NaN); + assertSame(TypeInteger.FALSE,new BoolNode.EQ(x,x,(byte)2).compute()); + } + @Test public void testUnresolvedInput() { new CodeGen("return 0;").driver(CodeGen.Phase.Opto); Node lhs = ConstantNode.seed(TypeInteger.TRUE); @@ -16,9 +39,9 @@ public class ArithNodeTest { ArithNode add = new AddNode(lhs,rhs); assertSame(TypeInteger.constant(2),add.compute()); lhs._type = TypeScalar.BOT; - assertSame(Type.BOTTOM,add.compute()); + assertSame(TypeScalar.BOT,add.compute()); add.setMode((byte)1); - assertSame(Type.BOTTOM,add.compute()); + assertSame(TypeScalar.BOT,add.compute()); } @Test public void testFloatPrecision() { @@ -26,6 +49,10 @@ public class ArithNodeTest { assertEquals("1.6777217E7",Eval2.eval(code,16777216)); code = new CodeGen("f32 x = arg; f32 y = x+1.0; return y;").driver(CodeGen.Phase.TypeCheck); assertEquals("1.6777216E7",Eval2.eval(code,16777216)); + code = new CodeGen("flt x = 0.0; flt y = 0.0; if(arg) { x = 1.5; y = 3.5; } else { x = 2.5; y = 4.5; } return x+y;") + .driver(CodeGen.Phase.TypeCheck); + assertEquals("7.0",Eval2.eval(code,0)); + assertEquals("5.0",Eval2.eval(code,1)); } @Test public void testMonotoneCompute() { diff --git a/chapter29/src/test/java/com/seaofnodes/simple/BoundaryTest.java b/chapter29/src/test/java/com/seaofnodes/simple/BoundaryTest.java index de502371..10b7517e 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/BoundaryTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/BoundaryTest.java @@ -24,10 +24,7 @@ public class BoundaryTest { CodeGen code=new CodeGen(src).driver(CodeGen.Phase.LocalSched); assertEquals("2018",Eval2.eval(code,19)); assertEquals("0",Eval2.eval(code,0)); - code._stop.walk(n -> { - if( n instanceof StoreNode st ) assertEquals(0,st.cfg0().loopDepth()); - return null; - }); + // Private memory follows the loop; stores need not move to its exit. code=new CodeGen("struct Byte { new Byte={int n -> self.x=n; self.x+=3;}; u8 x; }; return new Byte(255).x;").driver(CodeGen.Phase.TypeCheck); assertEquals("2",Eval2.eval(code,0)); // data is still unset when the constructor reads and updates x. diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 2c9a69a7..1a954110 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -158,7 +158,7 @@ else return v; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Test.Vector2D; return MEM[ 2:___ 3:.x=0; 4:.y=0;]; return Test.Vector2D; ]", code.print()); + assertEquals("Stop[ return Test.Vector2D; return MemTop; return Test.Vector2D; ]", code.print()); } @Test @@ -196,7 +196,7 @@ while (arg) { return bar.a; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MEM[ 2:___ 3:.a=0;]; return Test.Bar; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MemTop; return Test.Bar; ]", code.print()); } @Test @@ -318,7 +318,7 @@ while( i.x < i.len ) { return sum; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MEM[ 2:___ 3:.x=0; 4:.len=0;]; return Test.Iter; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MemTop; return Test.Iter; ]", code.print()); } @@ -337,7 +337,7 @@ while(arg) { return ret; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MEM[ 2:___ 3:.v0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MemTop; return Test.s0; ]", code.print()); } @Test @@ -390,7 +390,7 @@ s0 b = new s0(); return a.x * 100 + b.x * 10 + cnt; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return 112; return MEM[ 2:___ 3:___ 4:.x=1;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return 112; return MemTop; return Test.s0; ]", code.print()); } @@ -433,7 +433,7 @@ else return new s0; if(new s0.f0) return 0; """); code.driver(CodeGen.Phase.TypeCheck); - assertEquals("Stop[ return Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return Test.s0; return MemTop; return Test.s0; ]", code.print()); } @Test @@ -461,7 +461,7 @@ s0 v1 = v0; return v1; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.s0; return MEM[ 2:___ 3:.f0=0;]; return Test.s0; ]", code.print()); + assertEquals("Stop[ return (const)Test.s0; return MemTop; return Test.s0; ]", code.print()); } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java index fae7611d..156e091d 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -101,7 +101,7 @@ N n = new N(new M); return n.next; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return (const)Test.M; return MEM[ 2:___ 3:.m=0;]; return Test.M; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:.next=Parm_m(Test.N.N,*Test.M {i64 !m; }); 8:.i=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:___ 8:.i=0;]; return Test.N; ]", code.print()); + assertEquals("Stop[ return (const)Test.M; return MemTop; return Test.M; return MemTop; return MemTop; return Test.N; ]", code.print()); } @Test diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter18Test.java index e5813eae..ecb2b934 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -347,7 +347,7 @@ for(;;) { } """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Top; return Parm_i(x,i64); ]", code.print()); + assertEquals("return Top;", code.print()); assertNull( Eval2.eval( code, 0 ) ); // Infinite loop, <clinit> never exits } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter19Test.java index d5fe207a..e6249d82 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -118,7 +118,7 @@ val hashCode = { !String self -> hashCode(new String("Hello, World!")); """; CodeGen code = new CodeGen(src).driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MEM[ 2:___ 3:___ 4:___ 5:.cs=Parm_s(Test.String.String,*[]u8[final]); 6:._hashCode=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:._hashCode=0;]; return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); + assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MemTop; return MemTop; return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); assertEquals("4029215624828139541", Eval2.eval(code, 2)); } diff --git a/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java new file mode 100644 index 00000000..cea6ca91 --- /dev/null +++ b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionGroupTest.java @@ -0,0 +1,135 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.parser.Parser; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ConstructionGroupTest { + private static final String CHILD = """ + struct Child { + Test.Parent? parent; + int value = 5; + new Child = { Test.Parent? ^par -> parent = par; }; + }; + val read = { Child c -> return c.value; }; + """; + + private String parent(String body) { + return CHILD+"struct Parent { Child child; int~ payload; new Parent = { int n -> "+body+" }; };"; + } + + private void rejects(String src, String message) { + try { + new CodeGen(src).parse(); + fail("Accepted: "+src); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().contains(message)); + } + } + + @Test public void testCyclesAndIndependentAllocations() { + String src = parent("val detached = new Child(null); payload = n+read(detached); child = new Child(self);")+ + "val p = new Parent(arg); val local = new Child(p); val par = local.parent; return (par ? par.payload : 0)+p.child.value;"; + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals("17",Eval2.eval(code,7)); + assertEquals("10",Eval2.eval(code,0)); + } + new CodeGen(src.replace("Child","Child_noInline")) + .driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION,true,false,0); + } + + @Test public void testNoIncompleteLookupOrEscape() { + // This lookup supplies a live result. Inlining must not turn self + // complete inside the body before checking the use of child. + rejects(parent("child = new Child(self); payload = child.parent==null;")+ + "return new Parent(arg).payload;","incomplete object"); + rejects(parent("payload = 1; child = new Child(self); int x = child.parent==null;")+"return 0;","incomplete object"); + rejects(parent("payload = 1; child = new Child(self); read(child);")+"return 0;","ordinary function"); + rejects(parent("payload = 1; child = new Child(self);").replace("parent = par;","parent = par; value = par.payload;")+ + "return 0;","incomplete object"); + rejects(""" + struct Box { Test.C? value; }; val box = new Box; + struct C { int~ x; new C = { -> box.value = self; x = 1; }; }; + return 0; + ""","ordinary object"); + rejects("struct C { C next = self; int~ x; new C = { -> int y = next.x; x = 7; }; }; return 0;", + "incomplete object"); + } + + @Test public void testAliasesAndLoopBackedges() { + String src = parent("val alias = self; alias.payload = n; child = new Child(alias);")+"return new Parent(arg).child.value;"; + assertEquals("5",Eval2.eval(new CodeGen(src).driver(CodeGen.Phase.TypeCheck),3)); + rejects(parent("payload = 1; child = new Child(self); Child? !c = null; while(n--) { if(c) read(c); c = child; }")+ + "return 0;","ordinary function"); + rejects(parent("payload = 1; child = new Child(self); Parent? !p = null; while(n--) { val c = new Child(p); read(c); p = self; }")+ + "return 0;","ordinary function"); + rejects(parent("payload = 1; child = new Child(self); val c = n ? new Child(null) : child; read(c);")+ + "return 0;","ordinary function"); + } + + @Test public void testConstructorOnlyQualifier() { + rejects("struct C {}; val f = { C ^c -> return 0; }; return 0;","constructor"); + rejects("struct C { new C = { int ^x -> }; }; return 0;","struct parameter"); + rejects(parent("payload = 1; child = new Child(self);").replace("^par","par")+"return 0;","without '^'"); + CodeGen code = new CodeGen(parent("payload = 1; child = new Child(self);")+"return 0;") + .driver(CodeGen.Phase.TypeCheck); + try { + code.serialize(); + fail("Exported a constructor qualifier without its contract"); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().contains("Separate compilation")); + } + } + + @Test public void testCompleteLoopAllocations() { + // Optimistic types prove the cycle p -> new Link(p) -> p complete. + String src = """ + struct Link { + Link? next; + int value = 5; + new Link = { Link? ^n -> next = n; }; + }; + struct Root { + Link head; + int value; + new Root = { int n -> + Link? !p = null; + while(n--) p = new Link(p); + if(!p) p = new Link(null); + value = p.value; + head = p; + }; + }; + val root = new Root(arg); + return root.value + root.head.value; + """; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("10",Eval2.eval(code,0)); + assertEquals("10",Eval2.eval(code,3)); + // Dead calls discard their arguments before a construction result exists. + assertEquals("0",Eval2.eval(new CodeGen(CHILD+"struct Parent {}; return 0; new Child(null);") + .driver(CodeGen.Phase.TypeCheck),0)); + } + + @Test public void testDeclaredQualifierAndOwnReceiver() { + // A complete caller does not grant permission to read a ^ formal. + rejects(""" + struct Parent { int payload = 7; }; + struct Child { + int value; + new Child = { Parent ^par -> value = par.payload; }; + }; + return new Child(new Parent).value; + ""","incomplete object"); + // The self exception belongs to the receiver, not every pointer of its class. + rejects(""" + struct C { + int !value; + new C = { !C? ^other -> if(other) other.value = 1; value = 2; }; + }; + return new C(new C(null)).value; + ""","incomplete object"); + } +} diff --git a/chapter29/src/test/java/com/seaofnodes/simple/ConstructionRequirementsTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionRequirementsTest.java new file mode 100644 index 00000000..c570e643 --- /dev/null +++ b/chapter29/src/test/java/com/seaofnodes/simple/ConstructionRequirementsTest.java @@ -0,0 +1,222 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.parser.Parser; +import org.junit.Test; +import static org.junit.Assert.*; + +@org.junit.Ignore("Deferred: inferred field requirements and incomplete-object traversal") +public class ConstructionRequirementsTest { + private static final String CHILD = """ + struct Child { + Test.Parent parent; + int~ width; + new Child = { Test.Parent ^par -> + parent = par; + width = par.width; + }; + }; + """; + + private String parent(String body) { + return CHILD+"struct Parent { Child child; int~ width; new Parent = { int n -> "+body.replace("arg","n")+" }; };"; + } + + private void rejects(String src, String message) { + try { + new CodeGen(src).parse(); + fail("Accepted: "+src); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().contains(message)); + } + } + + @Test public void testCycleAndRequiredField() { + String src = parent("width = arg+10; child = new Child(self);")+"return new Parent(arg).child.parent.child.width;"; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("17",Eval2.eval(code,7)); + assertEquals("10",Eval2.eval(code,0)); + code = new CodeGen(parent("width = arg+10; child = new Child(self);")+ + "val p = new Parent(arg); return new Child(p).parent.child.width;").driver(CodeGen.Phase.TypeCheck); + assertEquals("17",Eval2.eval(code,7)); + code = new CodeGen(CHILD+"struct Parent { int width = 10; Child child = new Child(self); }; return new Parent().child.width;") + .driver(CodeGen.Phase.TypeCheck); + assertEquals("10",Eval2.eval(code,0)); + rejects(parent("child = new Child(self); width = 10;")+"return 0;","requires initialized field 'width'"); + rejects(parent("if(arg) width = 10; child = new Child(self); width = 20;")+"return 0;","requires initialized field 'width'"); + code = new CodeGen(parent("child = new Child(self); width = 10;").replace("width = par.width;","width = 5;")+ + "return new Parent(arg).child.parent.width;").driver(CodeGen.Phase.TypeCheck); + assertEquals("10",Eval2.eval(code,0)); + // Even if the comparison folds using the non-null declared type, + // accessing child still requires that field to have been initialized. + rejects(parent("width = 10; child = new Child(self);").replace("width = par.width;","width = par.child==null;")+ + "return 0;","requires initialized field 'child'"); + } + + @Test public void testNoEscapeOrFieldLaundering() { + rejects("struct C { C next = self; int~ payload; new C = { -> payload = next.payload; }; }; return 0;", + "might not be initialized"); + CodeGen code = new CodeGen("struct C { C next = self; int payload; new C = { -> payload = 17; payload = next.payload; }; }; return new C().next.payload;") + .driver(CodeGen.Phase.TypeCheck); + assertEquals("17",Eval2.eval(code,0)); + rejects(""" + struct C { + C next; int~ payload; + new C = { -> next = self; payload = next.payload; }; + }; return 0; + ""","might not be initialized"); + rejects(parent("width = 10; child = new Child(self); use(child);")+ + "val use = { Child c -> return c.parent.width; }; return 0;","ordinary function"); + rejects(CHILD+""" + struct Parent { + Child child; int~ width; + new Parent = { -> width = 10; child = new Child(self); int x = child.parent.width; }; + }; return 0; + ""","Traversing an unfinished reference field"); + rejects(""" + struct C { + int x; + val get = { -> return x; }; + new C = { -> x = get(); }; + }; return 0; + ""","ordinary function"); + rejects(""" + struct Box { Test.C? value; }; val box = new Box; + struct C { new C = { -> box.value = self; }; }; return 0; + ""","ordinary object"); + } + + @Test public void testConstructorOnlyQualifier() { + rejects("struct C {}; val f = { C ^c -> return 0; }; return 0;","constructor"); + rejects("struct C { new C = { int ^x -> }; }; return 0;","struct parameter"); + String src = parent("width = 10; child = new Child(self);")+"return 0;"; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + try { + code.serialize(); + fail("Exported an unrecorded construction contract"); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().contains("Separate compilation")); + } + } + + @Test public void testTransitiveRequirementsAndAliases() { + String child = """ + struct Leaf { + int~ width; + new Leaf = { Test.Parent ^par -> val alias = par; width = alias.width; }; + }; + struct Child { + Test.Parent parent; Leaf leaf; + new Child = { Test.Parent ^par -> parent = par; leaf = new Leaf(par); }; + }; + """; + String parent = "struct Parent { Child child; int~ width; new Parent = { int n -> %s }; };"; + String good = child+parent.formatted("width = n+10; val alias = self; child = new Child(alias);"); + CodeGen code = new CodeGen(good+"return new Parent(arg).child.leaf.width;").driver(CodeGen.Phase.TypeCheck); + assertEquals("17",Eval2.eval(code,7)); + rejects(child+parent.formatted("child = new Child(self); width = 10;")+"return 0;", + "requires initialized field 'width'"); + } + + @Test public void testLoopsAndUninlinedConstructor() { + String src = parent("width = 1; for(int i = 0; i < arg; i++) width += 2; child = new Child(self);")+ + "return new Parent(arg).child.width;"; + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(src.replace("Child","Child_noInline"),seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals("7",Eval2.eval(code,3)); + assertEquals("1",Eval2.eval(code,0)); + } + new CodeGen(src.replace("Child","Child_noInline")) + .driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION,true,false,0); + rejects(parent("for(int i = 0; i < arg; i++) width = 2; child = new Child(self); width = 10;")+"return 0;", + "requires initialized field 'width'"); + // The assignment on the backedge introduces the unfinished alias + // after the call was parsed. It must not pass as an ordinary Child. + rejects(parent("width = 10; child = new Child(self); Child? !c = null; while(arg--) { use(c); c = child; }")+ + "val use = { Child? c -> return 0; }; return 0;","ordinary function"); + } + + @Test public void testNullableFieldAndDuplicateArguments() { + String src = """ + struct Child { + Test.Parent parent; int~ width; + new Child = { Test.Parent ^a, Test.Parent ^b -> + parent = a; width = a.width+b.width+(a.optional==null); + }; + }; + struct Parent { + Child child; int width; Child? optional; + new Parent = { -> width = 10; child = new Child(self,self); }; + }; + return new Parent().child.width; + """; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("21",Eval2.eval(code,0)); + } + + @Test public void testNullableUnfinishedParameter() { + String child = """ + struct Child { + Test.Parent? parent; int width; + new Child = { Test.Parent? ^par -> + parent = par; width = par ? par.width : 0; + }; + }; + val read = { Child c -> return c.width; }; + """; + String parent = """ + struct Parent { + Child child; int~ width; + new Parent = { int n -> + val detached = new Child(null); + width = n+read(detached); + child = new Child(self); + }; + }; + """; + CodeGen code = new CodeGen(child+parent+""" + val p = new Parent(arg); + val leaf = new Child(p); + return read(leaf)+read(p.child); + """).driver(CodeGen.Phase.TypeCheck); + assertEquals("14",Eval2.eval(code,7)); + assertEquals("0",Eval2.eval(code,0)); + rejects(child+parent.replace("width = n+read(detached);","").replace("child = new Child(self);", + "child = new Child(self); width = n;"),"requires initialized field 'width'"); + rejects(child+parent.replace("child = new Child(self);","child = new Child(self); read(child);"), + "ordinary function"); + try { + new CodeGen(child.replace("par ? par.width : 0","par.width")+parent+ + "return new Child(null).width;").driver(CodeGen.Phase.TypeCheck); + fail("Dereferenced null constructor argument"); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().toLowerCase().contains("null")); + } + } + + @Test public void testDistinctCallTimeMemory() { + String src = CHILD+""" + struct Parent { + Child child; Child second; int~ width; + new Parent = { int n -> + width = n+1; child = new Child(self); + width = n+2; second = new Child(self); + width = n+3; + }; + }; + val p = new Parent(arg); return p.child.width*100+p.second.width*10+p.width; + """; + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(src.replace("Child","Child_noInline"),seed,true).driver(CodeGen.Phase.TypeCheck); + assertEquals("123",Eval2.eval(code,0)); + assertEquals("456",Eval2.eval(code,3)); + } + new CodeGen(src.replace("Child","Child_noInline")) + .driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION,true,false,0); + String loop = parent("width = 1; child = new Child(self); for(int i = 0; i < arg; i++) { width += 1; child = new Child(self); } width += 10;")+ + "val p = new Parent(arg); return p.child.width*100+p.width;"; + CodeGen code = new CodeGen(loop.replace("Child","Child_noInline")).driver(CodeGen.Phase.TypeCheck); + assertEquals("414",Eval2.eval(code,3)); + assertEquals("111",Eval2.eval(code,0)); + } +} diff --git a/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java b/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java index 6a229a4f..cbb9ee37 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/ConstructorCompletionTest.java @@ -6,6 +6,48 @@ import org.junit.Test; import static org.junit.Assert.*; public class ConstructorCompletionTest { + @Test public void testFieldMemoryDuringInitialization() { + CodeGen code = new CodeGen(""" + struct A { + int x = 1; + x = 2; + int y = self.x; + new A = { -> self.x = 3; y += x; }; + }; + val a = new A; return a.x*10+a.y; + """).driver(CodeGen.Phase.TypeCheck); + assertEquals("35",Eval2.eval(code,0)); + code = new CodeGen(""" + struct A { + int[] data = new int[3]; + new A = { -> for(int i = 0; i < 3; i++) data[i] = i+1; }; + }; + return new A().data[2]; + """).driver(CodeGen.Phase.TypeCheck); + assertEquals("3",Eval2.eval(code,0)); + for( String body : new String[]{ + "int~ x; int y = x; new A = { -> x = 7; };", + "int~ x; int y = x*0; new A = { -> x = 7; };", + // Constructor entry includes the initializer's early return. + // Its later Store of 2 must not excuse the earlier read of x. + "int~ x; if(arg) return 0; x = 1; new A = { -> int y = x; x = 2; };" + } ) + try { + new CodeGen("struct A { "+body+" }; return 0;").parse(); + fail("Read a field before its constructor wrote it"); + } catch( Parser.ParseException e ) { + assertTrue(e.getMessage(),e.getMessage().contains("might not be initialized")); + } + } + + @Test public void testRequiredNumberBesideNullableDefault() { + CodeGen code = new CodeGen(""" + struct A { int~ x; A? p; new A = { -> x = 10; }; }; + return new A().x; + """).driver(CodeGen.Phase.TypeCheck); + assertEquals("10",Eval2.eval(code,0)); + } + private void rejects(String fields, String field, boolean explicit) { String src = "struct B {}; struct A { "+fields+" }; return 0;"; try { diff --git a/chapter29/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java b/chapter29/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java index 38b94693..66fdacc3 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.StoreNode; import org.junit.Test; import static org.junit.Assert.*; @@ -20,16 +19,12 @@ public class FinalConstructionTest { return new C(arg).get(); """; - @Test public void testFinalConstructorLocals() throws java.io.IOException { + @Test public void testFinalConstructorFields() throws java.io.IOException { var code=new CodeGen(LOOP).driver(CodeGen.Phase.LocalSched); assertEquals("1",Eval2.eval(code,0)); assertEquals("15",Eval2.eval(code,3)); assertEquals("63",Eval2.eval(code,5)); - code._stop.walk(n -> { - if( n instanceof StoreNode st && st._name.equals("x") ) - assertEquals("Final field writes belong after the loop",0,st.cfg0().loopDepth()); - return null; - }); + // Writes are ordinary Stores and may remain inside the loop. String[] sources={ "struct C { val x=1; new C={->x=1; x=2;}; }; return new C().x;", "struct C { int ~x; new C={int n -> self.x=1; for(int i=0;i<n;i++) self.x*=2;}; }; return new C(arg).x;", diff --git a/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java index b4055eef..68239396 100644 --- a/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter29/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -147,7 +147,7 @@ public class TypeTest { Assert.assertNotEquals(ptr1, ptr2); Assert.assertEquals(ptr1, ptr1.dual().dual()); - Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT).withAccess(false), ptr1.meet(ptr2nil)); + Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT).withAccess(false).withPartial(false), ptr1.meet(ptr2nil)); TypeMemPtr TOP = TypeMemPtr.TOP; TypeMemPtr BOT = TypeMemPtr.makeNullable(TypeStruct.BOT); @@ -156,7 +156,7 @@ public class TypeTest { Type PTR_meet_NULL = NULL.meet(PTR); Assert.assertEquals(BOT, PTR_meet_NULL); Type ptr1_meet_ptr2 = ptr1.meet(ptr2); - Assert.assertEquals(PTR.withAccess(false), ptr1_meet_ptr2); + Assert.assertEquals(PTR.withAccess(false).withPartial(false), ptr1_meet_ptr2); Type NULL_join_ptr1 = NULL.join(ptr1); Assert.assertEquals(TypePtr.XNPTR, NULL_join_ptr1); Type NULL_join_PTR = PTR.join(NULL); |