diff options
Diffstat (limited to 'chapter23')
51 files changed, 1350 insertions, 1206 deletions
diff --git a/chapter23/README.md b/chapter23/README.md index debbf6dc..ee17f9f2 100644 --- a/chapter23/README.md +++ b/chapter23/README.md @@ -46,7 +46,7 @@ Also in this chapter we revisit our Types and make some major changes: etc; only the implementation details change. -The lazy memory model from Chapter 10b continues through the new type system. +The lazy memory model from Chapter 11 continues through the new type system. BulkMemPhi/MemPhi discover aliases during optimization. Each New covers only instance fields; class-wide (`_one`) fields are excluded from its partial memory. Field offsets stay symbolic until layout, and Loads retain cyclic field types @@ -69,10 +69,10 @@ Let's look at our `String.indexOf` example above. Here we define a `String` with an `indexOf` method; a hidden argument string `self` is passed in and searched. What is the type of `struct String`? -`struct String { u8[~] buf; { String self, u8 c -> int } indexOf; }` +`struct String { u8[~] buf; { !String !self, u8 c -> int } indexOf; }` It is the type named `String` with a field `u8[~] buf` and a final assigned -constant field `indexOf`, itself with type `{ String self, u8 c -> int }`. +constant field `indexOf`, itself with type `{ !String !self, u8 c -> int }`. i.e., the type of `String` has a reference to itself, nested inside the type of `indexOf`.... i.e. `String`'s type is *cyclic*. @@ -100,7 +100,7 @@ Here's an example, a Linked List with a Java `Object` or a C `void*` payload: ```java struct List { - List next; + !List !next; Object payload; // equivalently for C: void* } // Then walk a collection of ints and build a List: @@ -180,7 +180,7 @@ alternatives) but it is a great tutorial data structure. ```java struct List { - List? !next; // Next pointer or null + !List? !next; // Next pointer or null str !name; // Payload }; ``` @@ -322,7 +322,7 @@ of simplicity we choose to approximate our types to only a single instance of In this example on first visit of `List` we will miss in `VISIT`. The next call to `ts = recurPre(_name,_open)` does common shared pre-recursive work: we make a new `TypeStruct` and **set** it in the `VISIT` table. The new `TypeStruct` -is a blank version of `List` with all fields attached; we force these fields to +is a blank version of `List` with all !fields !attached; we force these fields to be final right away but they are missing their types: ``` diff --git a/chapter23/docs/examples/BubbleSort.smp b/chapter23/docs/examples/BubbleSort.smp index 4352c47a..938e3181 100644 --- a/chapter23/docs/examples/BubbleSort.smp +++ b/chapter23/docs/examples/BubbleSort.smp @@ -5,7 +5,7 @@ // // Bubble sort, with reading (parsing) and writing (formatting) the data. -val sort = { sys.aryi64 nums -> +val sort = { !sys.aryi64 nums -> var done = false; while( !done ) { done = true; diff --git a/chapter23/src/main/java/com/seaofnodes/simple/Parser.java b/chapter23/src/main/java/com/seaofnodes/simple/Parser.java index 2dc83905..fa6568ab 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/Parser.java @@ -189,6 +189,10 @@ public class Parser { * Parses a function body, assuming the header is parsed. */ private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, String... ids) { + return parseFunctionBody(sig, loc, null, ids); + } + + private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String... ids) { // If this is a method, record & restore the existing struct fields, // which are also the struct initializers. The method might update // mutable fields, so when the function parse is done reset back to @@ -232,7 +236,7 @@ public class Parser { // All args, "as-if" called externally for( int i=0; i<ids.length; i++ ) { Type t = sig.arg(i); - _scope.define(ids[i], t, false, new ParmNode(ids[i],i+2,t,fun,con(t)).peephole(), loc); + _scope.define(ids[i], t, finals==null ? t instanceof TypeNil : finals.get(i), new ParmNode(ids[i],i+2,t,fun,con(t)).peephole(), loc); } // Parse the body @@ -662,30 +666,31 @@ public class Parser { if( _scope.in(def._idx)._type!=Type.TOP && def._final && // Inside an allocation, final assign is OK, outside nope. // The alloc() call added the allocation scope - !(_scope.inAllocation() && def._idx >= _scope._kinds.last(-1)._lexSize) ) + !_scope.canInit(def) ) throw error("Cannot reassign final '"+name+"'"); // Parse assignment expression Node expr = parseAsgn(); // Lift expression, based on type - Node lift = liftExpr(expr.keep(), def.type(), def._final, true); + Node lift = liftExpr(expr.keep(), def.type(), true); // Update _scope.update(name,lift); // Return un-lifted expr return expr.unkeep(); } - // Make finals deep; widen ints to floats; narrow wide int types. + // Apply declared access permissions; widen floats and narrow integers. // Early error if types do not match variable. - private Node liftExpr( Node expr, Type t, boolean xfinal, boolean isLoad ) { + private Node liftExpr( Node expr, Type t, boolean isLoad ) { if( expr._type instanceof TypeMemPtr tmp && TYPES.get(tmp._obj._name).isFRef() ) throw error("Must define forward ref "+tmp._obj._name); - // Final is deep on ptrs - if( xfinal && t instanceof TypeMemPtr tmp ) { - t = tmp.makeRO(); + // Read-only access is deep; a fixed binding alone does not remove access. + if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) { expr = peep(new ReadOnlyNode(expr)); } + if( !expr._type.accessISA(t) ) + throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); // Auto-widen array to i64 (cast ptr to raw int bits) if( t == TypeInteger.BOT && expr._type instanceof TypeMemPtr tmp && tmp._obj.isAry() ) expr = peep(new AddNode(peep(new CastNode(t,ctrl(),expr)),off(tmp._obj,"[]"))); @@ -699,7 +704,7 @@ public class Parser { else if( et instanceof TypeInteger && t instanceof TypeInteger ) et=t; // Type is sane - if( et!=Type.BOTTOM && !et.shallowISA(t) ) + if( et!=Type.BOTTOM && (!et.shallowISA(t) || !et.accessISA(t)) ) expr = peep(new CastNode(t,null,expr)); return expr; } @@ -730,43 +735,54 @@ public class Parser { return require(n,";"); } - /** Parse final: [!]var['=' asgn] + // Widen a reassignable binding without discarding the initializer's + // permissions. Lattice glb includes readonly memory and is too broad here. + private Type inferredType(Type t) { + if( t instanceof TypeMemPtr tmp ) { + if( tmp._obj.isAry() ) { + Type elem = tmp._obj._fields[1]._t; + if( elem instanceof TypeConAry ) + elem = ((TypeMemPtr)TYPES.get(tmp._obj._name))._obj._fields[1]._t; + return typeAry(elem,tmp._obj._fields[1]._final).withAccess(tmp._ro).makeNullable(); + } + Type base = TYPES.get(tmp._obj._name); + TypeMemPtr ptr = (TypeMemPtr)base; + return ptr.withAccess(tmp._ro).makeNullable(); + } + return t.glb(false); + } + + // The binding modifier sits immediately before the name. It never + // changes permissions on the referenced object. + private boolean bindingFinal(Type t) { + if( match("!") ) return false; + if( match("~") ) return true; + return t==Type.TOP || t instanceof TypeNil; + } + + /** Parse final: [!|~]var['=' asgn] */ private Node parseDeclaration(Type t) { assert t!=null; // Has var/val instead of a user-declared type boolean inferType = t==Type.TOP || t==Type.BOTTOM; - boolean hasBang = match("!"); + boolean xfinal = bindingFinal(t); Lexer loc = loc(); String name = requireId(); // Optional initializing expression follows - boolean xfinal = false; - boolean fld_final = false; // Field is final, but not deeply final + boolean fld_final = false; // Fixed field independent of pointee access + boolean initialized = match("="); Node expr; - if( match("=") ) { + if( initialized ) { expr = isExternDecl() ? externDecl(name,t) : parseAsgn(); - // TOP means val and val is always final - xfinal = (t==Type.TOP) || - expr instanceof ExternNode || - // BOTTOM is var and var is always not-final - (t!=Type.BOTTOM && - // no Bang AND - !hasBang && - // Locals are not-final by default - !_scope.inFunction() && - // not-null (expecting null to be set to not-null) - expr._type != Type.NIL && - // Pointers are final by default; int/flt are not-final by default. - (t instanceof TypeNil)); - // var/val, then type comes from expression if( inferType ) { if( expr._type==Type.NIL ) throw error("a not-null/non-zero expression"); t = expr._type; - if( !xfinal ) t = t.glb(false); // Widen if not final + if( !xfinal ) t = inferredType(t); // Widen if not final } // expr is a constant function if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { @@ -785,23 +801,20 @@ public class Parser { // Nullable pointers get a NIL; not-null get a TOP which // signals that they *must* be initialized in the constructor. case TypeNil tn -> tn.nullable() ? NIL : con(Type.TOP); - case TypeInteger ti -> ZERO; - case TypeFloat tf -> con(TypeFloat.FZERO); + case TypeInteger ti -> xfinal ? con(Type.TOP) : ZERO; + case TypeFloat tf -> con(xfinal ? Type.TOP : TypeFloat.FZERO); // Bottom signals type inference: they must be initialized in // the constructor and that's when we'll discover the type. case Type tt -> { assert tt==Type.BOTTOM; yield con(tt); } }; // Nullable fields are set in the constructor, but remain shallow final. // e.g. final pointer to a r/w array - if( t instanceof TypeNil tn && !tn.nullable() && !hasBang ) + if( t instanceof TypeNil tn && !tn.nullable() && xfinal ) fld_final = true; } // Lift expression, based on type - Node lift = liftExpr(expr, t, xfinal, true); - // Rebuild the deep RO 't', not returned from liftExpr - if( xfinal && t instanceof TypeMemPtr tmp ) - t = tmp.makeRO(); + Node lift = liftExpr(expr, t, true); // Lift type to the declaration. This will report as an error later if // we cannot lift the type. @@ -810,6 +823,7 @@ public class Parser { // Define a new name if( !_scope.define(name,t,xfinal || fld_final,lift, loc) ) throw error("Redefining name '" + name + "'", loc); + _scope.lookup(name)._init = initialized; return lift; } @@ -841,7 +855,7 @@ public class Parser { while( nvar < _scope._vars._len ) { Var v = _scope.var(nvar++); if( !v.isFRef() ) { - ts = ts.add( Field.make( v._name, v.type(), _code.getALIAS(), v._final, v._final && _scope.in( v._idx )._type != Type.TOP ) ); + ts = ts.add( Field.make( v._name, v.type(), _code.getALIAS(), v._final, v._final && v._init && _scope.in( v._idx )._type != Type.TOP ) ); TYPES.put( typeName, TypeMemPtr.make( ts ) ); } } @@ -885,12 +899,14 @@ public class Parser { // t = int|i8|i16|i32|i64|u8|u16|u32|u64|byte|bool | flt|f32|f64 | val | var | struct[?] private Type type() { int old1 = pos(); + boolean writable = match("!"); + boolean readonly = !writable && match("~"); // Only type with a leading `{` is a function pointer... if( peek('{') ) return typeFunPtr(); // Otherwise you get a type name String tname = _lexer.matchId(); - if( tname==null ) return null; + if( tname==null ) return posT(old1); // Convert the type name to a type. Type t0 = TYPES.get(tname); @@ -913,6 +929,13 @@ public class Parser { // Still no type found? Assume forward reference Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.open(tname)) :t0; // Null: assume a forward ref type + // A qualifier before the name applies to the struct reference, not + // to an enclosing array. Arrays have their own [] / [~] qualifier. + if( t1 instanceof TypeMemPtr tmp ) { + if( readonly || !writable ) t1 = tmp.makeRO(); + } else if( writable || readonly ) + return posT(old1); + // Nest arrays and '?' as needed Type t2 = t1; while( true ) { @@ -922,7 +945,7 @@ public class Parser { if( tmp.nullable() ) throw error("Type "+t2+" already allows null"); t2 = tmp.makeNullable(); } else if( match("[~]") ) { - t2 = typeAry(t2,true); + t2 = typeAry(t2,true).makeRO(); } else if( match("[]") ) { t2 = typeAry(t2,false); } else @@ -934,13 +957,13 @@ public class Parser { // Check valid forward ref, after parsing all the type extra bits. // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax int old2 = pos(); - match("!"); + if( !match("!") ) match("~"); String id = _lexer.matchId(); if( !(peek(',') || peek(';') || match("->")) || id==null ) return posT(old1); // Reset lexer to reparse pos(old2); // Reset lexer to reparse // Yes a forward ref, so declare it - TYPES.put(tname,t1); + TYPES.put(tname,((TypeMemPtr)t1).withAccess(false)); // Return the (array, final) type return t2; } @@ -954,10 +977,9 @@ public class Parser { if( ta==null ) // Remember final version TYPES.put(tname, ta = TypeMemPtr.make( TypeStruct.makeAry(tname,TypeInteger.U32,_code.getALIAS(),t,_code.getALIAS(),true) )); - Field elem = ta._obj.field("[]"); - if( elem._final == efinal ) - return ta; - return TypeMemPtr.make( ta._obj.replace(elem.makeFrom(efinal))); + // Reuse aliases, but preserve this occurrence's element permissions. + TypeStruct ary = ta._obj; + return TypeMemPtr.make(TypeStruct.makeAry(tname,TypeInteger.U32,ary._fields[0]._alias,t,ary._fields[1]._alias,efinal)); } // A function type is `{ type... -> type }` or `{ type }`. @@ -1197,7 +1219,8 @@ public class Parser { Type t = type(); if( t!=null ) { if( peek('.') ) - return parsePostfix(con(t)); + // A namespace lookup is not a reference declaration. + return parsePostfix(con(TYPES.get(((TypeMemPtr)t)._obj._name))); //pos(pos); // TODO: not a `type.fld` //return null; throw Utils.TODO(); @@ -1307,7 +1330,7 @@ public class Parser { }; // Convert to float ops, or narrow int types; error if not declared type. // Also, if postfix LHS is still keep() - return liftExpr(peep(op.widen()),t,false,true); + return liftExpr(peep(op.widen()),t,true); } @@ -1423,7 +1446,7 @@ public class Parser { // array body. TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[]u8", TypeInteger.constant(s.length()), lenAlias, con, elemAlias, true),true); assert str.isConstant(); - return con(str); + return con(str.makeRO()); } // Memory is one hidden SSA variable, including across branches and loops. @@ -1431,6 +1454,8 @@ public class Parser { private void mem(Node n) { _scope.mem(n); } private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { + if( !init && ptr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) + throw error("Cannot modify final field '"+name+"'"); Node prior = mem().keep(); Node st = new StoreNode(loc(),name,alias,glb,prior,ptr,off,val,init); st.setDef(0,ctrl); @@ -1483,7 +1508,8 @@ public class Parser { // Find the field from the Type. Lookup in the base object field names. TypeMemPtr ptr2 = (TypeMemPtr)TYPES.get(ptr._obj._name); - ptr = (TypeMemPtr)ptr.join(ptr2);// Upgrade to latest TYPES + if( !ptr._obj.isAry() ) + ptr = ptr.makeFrom((TypeStruct)ptr._obj.join(ptr2._obj)); // Resolve the shape, retaining access. TypeStruct base = ptr._obj; int fidx = base.find(name); if( fidx == -1 ) @@ -1506,7 +1532,7 @@ public class Parser { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( matchOpx('=','=') ) { Node val = parseAsgn().keep(); - Node lift = liftExpr( val, tf, f._final, false ); + Node lift = liftExpr( val, tf, false ); store(name,f._alias,tf,expr.unkeep(),off.unkeep(),lift,false,base.isAry() ? ctrl() : null); return val.unkeep(); // "obj.a = expr" returns the expression while updating memory @@ -1583,6 +1609,7 @@ public class Parser { private Node func() { Ary<Type> ts = new Ary<>(Type.class); Ary<String> ids = new Ary<>(String.class); + java.util.BitSet finals = new java.util.BitSet(); // Defined in constructor? Add `self` argument. "static" calls still // add a `self` they just ignore it. @@ -1599,6 +1626,7 @@ public class Parser { while( true ) { Type t = type(); // Arg type if( t==null ) break; + finals.set(ids.size(),bindingFinal(t)); String id = requireId(); ts .push(t ); // Push type/arg pairs ids.push(id); @@ -1607,7 +1635,7 @@ public class Parser { require("->"); // Make a concrete function type, with a fidx TypeFunPtr tfp = _code.makeFun(TypeFunPtr.make(false,false,ts.asAry(),Type.BOTTOM)); - ReturnNode ret = parseFunctionBody(tfp,loc,ids.asAry()); + ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); return new FunPtrNode(ret._fun.sig(),ret).peephole(); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/Var.java b/chapter23/src/main/java/com/seaofnodes/simple/Var.java index 14295395..e13b85c5 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/Var.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/Var.java @@ -13,6 +13,7 @@ public class Var { // promotions. public int _idx; // index in containing scope private Type _type; // Declared type + public boolean _init; // Explicit declaration initializer public boolean _final; // Final field public boolean _fref; // Forward ref public Parser.Lexer _loc; // Source location diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java index 215e3c78..f66d1f71 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -162,7 +162,7 @@ public class CallNode extends CFGNode { // Check for args for( int i=0; i<tfp.nargs(); i++ ) - if( !arg(i+2)._type.isa(tfp.arg(i)) ) { + if( !arg(i+2)._type.isa(tfp.arg(i)) || !arg(i+2)._type.accessISA(tfp.arg(i)) ) { cend().addDep(arg(i+2)); // Upgrading arg type may allow inlining return Parser.error( "Argument #" + i + " isa " + arg(i+2)._type + ", but must be a " + tfp.arg(i), _loc ); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java index 08d72e35..4e93f3e6 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -49,7 +49,7 @@ public class CastNode extends Node { @Override public Node idealize() { - return in(1)._type.isa(_t) ? in(1) : null; + return in(1)._type.isa(_t) && in(1)._type.accessISA(_t) ? in(1) : null; } @Override diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 31844741..0a9dae59 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -64,7 +64,7 @@ public class LoadNode extends MemOpNode { } // Lift from declared type and memory input t = t.join(_declaredType).join(MemMergeNode.contents(mem(),_alias,this)); - if( _declaredType.isFinal() ) + if( ptr()._type.isFinal() || _declaredType.isFinal() ) t = t.makeRO(); // Deep final applied return t; } @@ -227,7 +227,7 @@ public class LoadNode extends MemOpNode { // Read-Only is a deep property, and cannot be cast-away private Node castRO(Node rez) { - if( ptr()._type.isFinal() && !rez._type.isFinal() ) + if( (ptr()._type.isFinal() || _declaredType.isFinal()) && !rez._type.isFinal() ) return new ReadOnlyNode(rez).peephole(); return rez; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index ad173bc3..8d924b96 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -36,7 +36,9 @@ public class MemMergeNode extends Node { // join it with the incoming contents for all previously allocated objects. // Phis use their cached types, so this query does not recurse around loops. static Type contents(Node mem, int alias, Node dep) { - dep.addDep(mem); + // A loop memory Phi can also be a user of the querying Store. + // Its type changing still needs to revisit this query. + dep.addDepForwards(mem); if( mem instanceof CastNode cast ) return contents(cast.in(1),alias,dep); if( mem instanceof MemMergeNode merge ) return contents(merge.alias(alias),alias,dep); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 88d1a7ef..af5d900b 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -80,8 +80,8 @@ public class PhiNode extends Node { // Can upgrade minType even while in-progress if( _minType instanceof TypeMemPtr tmp && _minType.isFRef() ) { TypeMemPtr tmp2 = (TypeMemPtr)CodeGen.CODE.P.TYPES.get(tmp._obj._name); - if( tmp2!=null && tmp2 != _minType ) { - _minType = tmp2; + if( tmp2!=null && tmp2._obj != tmp._obj ) { + _minType = tmp.makeFrom(tmp2._obj); return this; } } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index cd5ab6ff..307fc0f9 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -137,6 +137,15 @@ public class ScopeNode extends Node { } + // Allocation fields live in the scope immediately outside the constructor + // block. Nested blocks retain that permission; surrounding bindings do not. + public boolean canInit(Var v) { + for( int i=_kinds._len-1; i>0; i-- ) + if( _kinds.at(i) instanceof Kind.Alloc ) + return v._idx >= _kinds.at(i-1)._lexSize && v._idx < _kinds.at(i)._lexSize; + return false; + } + public boolean inConstructor() { return _kinds.last() instanceof Kind.Define; } public boolean inAllocation () { return _kinds.last() instanceof Kind.Alloc ; } public boolean inFunction () { return _kinds.last() instanceof Kind.Func ; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java index def61478..5d3e10e5 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -127,7 +127,7 @@ public class StoreNode extends MemOpNode { if( ptr()._type == Type.TOP ) return null; // Dead store TypeMemPtr tmp = (TypeMemPtr)ptr()._type; - if( tmp._obj.field(_name)._final && !_init ) + if( (tmp._ro || tmp._obj.field(_name)._final) && !_init ) return Parser.error("Cannot modify final field '"+_name+"'",_loc); return null; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter23/src/main/java/com/seaofnodes/simple/type/Field.java index b2b2deca..1f22cb05 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/Field.java @@ -99,7 +99,7 @@ public class Field extends Type { @Override boolean _isConstant() { return _t._isConstant(); } @Override boolean _isFinal() { return _final && _t._isFinal(); } - @Override Field _makeRO() { return _final ? this : make(_fname, _t._makeRO(),_alias,true,_one); } + @Override Field _makeRO() { return make(_fname, _t._makeRO(),_alias,true,_one); } boolean isGLB2() { return _final && _t._isGLB(true); } Field glb2() { Type glb = _t._glb(true); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter23/src/main/java/com/seaofnodes/simple/type/Type.java index fe0c33f3..3f115c3f 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/Type.java @@ -326,6 +326,10 @@ public class Type /*implements Cloneable*/ { // Make a zero version of this type, 0 for integers and null for pointers. public Type makeZero() { return Type.NIL; } + // Writable array slots are invariant in their element access permissions. + // Otherwise an alias could insert a readonly pointer into a writable slot. + public boolean accessISA(Type dst) { return true; } + // Is forward-reference public boolean isFRef() { return false; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index ffbc71da..ad744c8f 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -26,11 +26,14 @@ public class TypeMemPtr extends TypeNil { // (TOP ,true ) - a nil public TypeStruct _obj; + // Deep read-only access through this pointer; independent of slot finality. + public boolean _ro; + public boolean _one; // Singleton instance private static final Ary<TypeMemPtr> FREE = new Ary<>(TypeMemPtr.class); private TypeMemPtr(byte nil, TypeStruct obj, boolean one) { super(TMEMPTR,nil); init(nil,obj,one); } - private TypeMemPtr init(byte nil, TypeStruct obj, boolean one) { _nil=nil; _obj=obj; _one=one; return this; } + private TypeMemPtr init(byte nil, TypeStruct obj, boolean one) { _nil=nil; _obj=obj; _ro=obj==TypeStruct.BOT; _one=one; return this; } // Return a filled-in TypeMemPtr; either from free list or alloc new. private static TypeMemPtr malloc(byte nil, TypeStruct obj, boolean one) { return FREE.isEmpty() ? new TypeMemPtr(nil,obj,one) : FREE.pop().init(nil,obj,one); @@ -38,7 +41,10 @@ public class TypeMemPtr extends TypeNil { // All fields directly listed public static TypeMemPtr make(byte nil, TypeStruct obj, boolean one) { - TypeMemPtr tmp = malloc(nil, obj, one); + return make(nil,obj,one,obj==TypeStruct.BOT); + } + private static TypeMemPtr make(byte nil, TypeStruct obj, boolean one, boolean ro) { + TypeMemPtr tmp = malloc(nil, obj, one).access(ro); TypeMemPtr t2 = tmp.intern(); if( t2==tmp ) return tmp; return VISIT.isEmpty() ? t2.free(tmp) : t2.delayFree(tmp); @@ -58,9 +64,30 @@ public class TypeMemPtr extends TypeNil { public static TypeMemPtr make (TypeStruct obj) { return make((byte)2, obj); } public static TypeMemPtr makeNullable(TypeStruct obj) { return make((byte)3, obj); } - public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one); } + public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one,_ro); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } - @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one); } + @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one,_ro); } + + private TypeMemPtr access(boolean ro) { _ro=ro; return this; } + + public TypeMemPtr withAccess(boolean ro) { + if( _ro==ro ) return this; + TypeMemPtr ptr = malloc(_nil, _obj, _one); + ptr._ro = ro; + TypeMemPtr res = ptr.intern(); + if( res==ptr ) return ptr; + return VISIT.isEmpty() ? res.free(ptr) : res.delayFree(ptr); + } + + // Writable slots can load and store references, so their element access + // must agree in both directions. A read-only outer view can weaken access. + @Override public boolean accessISA(Type dst) { + if( !(dst instanceof TypeMemPtr ptr) ) return true; + if( _ro && !ptr._ro ) return false; + if( ptr._ro || _obj._fields==null || ptr._obj._fields==null || !_obj.isAry() || !ptr._obj.isAry() ) return true; + Type a = _obj._fields[1]._t, b = ptr._obj._fields[1]._t; + return a.accessISA(b) && b.accessISA(a); + } // An abstract pointer, pointing to either a Struct or an Array. // Can also be null or not, so 4 choices {TOP,BOT} x {nil,not} @@ -69,35 +96,35 @@ 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); } + public static void gather(ArrayList<Type> ts) { ts.add(NOTBOT); ts.add(BOT); ts.add(TEST); ts.add(TEST.makeRO()); } @Override public TypeNil xmeet(Type t) { TypeMemPtr that = (TypeMemPtr) t; assert !isFree() && !that.isFree(); - return make(xmeet0(that), (TypeStruct)_obj.meet(that._obj), _one & that._one); + return make(xmeet0(that), (TypeStruct)_obj.meet(that._obj), _one & that._one,_ro | that._ro); } @Override - TypeMemPtr xdual() { return malloc( dual0(), _obj.dual(), _one); } + TypeMemPtr xdual() { return malloc( dual0(), _obj.dual(), _one).access(!_ro); } @Override TypeMemPtr rdual() { if( _dual!=null ) return dual(); assert !_terned; - TypeMemPtr d = malloc(dual0(), null, _one); + TypeMemPtr d = malloc(dual0(), null, _one).access(!_ro); (_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); } + @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj,false,_ro); } @Override boolean _isConstant() { return _one && _obj._isConstant(); } - @Override boolean _isFinal() { return _obj._isFinal(); } - @Override TypeMemPtr _makeRO() { return makeFrom(_obj._makeRO()); } - @Override boolean _isGLB(boolean mem) { return _obj.isGLB2(); } - @Override TypeMemPtr _glb(boolean mem) { return make((byte)3,_obj.glb2()); } + @Override boolean _isFinal() { return _ro; } + @Override TypeMemPtr _makeRO() { return withAccess(true); } + @Override boolean _isGLB(boolean mem) { return _ro && _nil==3 && !_one && _obj.isGLB2(); } + @Override TypeMemPtr _glb(boolean mem) { return make((byte)3,_obj.glb2(),false,true); } @Override TypeMemPtr _close() { return makeFrom(_obj._close()); } @@ -105,7 +132,7 @@ public class TypeMemPtr extends TypeNil { @Override public boolean shallowISA( Type t ) { if( !(t instanceof TypeMemPtr that) ) return false; if( this==that ) return true; - if( xmeet0(that)!=that._nil ) return false; + if( xmeet0(that)!=that._nil || (_ro && !that._ro) ) return false; if( _obj==that._obj ) return true; if( _obj._name.equals(that._obj._name) ) return true; // Shallow, do not follow matching names, just assume ok @@ -117,16 +144,16 @@ public class TypeMemPtr extends TypeNil { @Override public int log_size() { return 3; } // (1<<3)==8-byte pointers - @Override int hash() { return _obj.hashCode() ^ super.hash() ^ (_one ? 2048 : 0); } + @Override int hash() { return (_ro ? 8192 : 0) ^ _obj.hashCode() ^ super.hash() ^ (_one ? 2048 : 0); } @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return super.eq(ptr) && _one == ptr._one && _obj == ptr._obj; + return _ro==ptr._ro && super.eq(ptr) && _one == ptr._one && _obj == ptr._obj; } @Override boolean cycle_eq(Type t) { if( t._type != TMEMPTR ) return false; TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return super.eq(ptr) && _one == ptr._one && _obj.cycle_eq(ptr._obj); + return _ro==ptr._ro && super.eq(ptr) && _one == ptr._one && _obj.cycle_eq(ptr._obj); } @Override int nkids() { return 1; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index dc796ffd..f065126a 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -87,9 +87,10 @@ public class TypeStruct extends Type { return (TypeStruct)recurOpen()._close().recurClose(); } @Override TypeStruct _close() { - TypeStruct ts = (TypeStruct)VISIT.get(_name); + Object key = isAry() ? _uid : _name; + TypeStruct ts = (TypeStruct)VISIT.get(key); if( ts!=null ) return ts; - ts = recurPre(_name,false); + ts = recurPre(key,false); Field[] flds = ts._fields; // Now start the recursion diff --git a/chapter23/src/main/smp/sys.smp b/chapter23/src/main/smp/sys.smp index cda93abe..6a6d3ca3 100644 --- a/chapter23/src/main/smp/sys.smp +++ b/chapter23/src/main/smp/sys.smp @@ -154,7 +154,7 @@ struct sys { // parseAryI64 & aryi64.str are bijections modulo whitespace. // Returns null if the parse failed. val parseAryI64 = { u8[~] str -> - sys.Scan !s = new sys.Scan{ buf = str; }; + !sys.Scan !s = new sys.Scan{ buf = str; }; if( !s.match('[') ) return null; // Array of parsed results var nums = new sys.aryi64{ buf=new i64[1]; }; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 121e8a22..0f4ca169 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -25,7 +25,7 @@ public class Chapter10Test { // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ struct Point { int x; }; - Point?[] !points = new Point?[2]; + !Point?[] !points = new !Point?[2]; points[arg] = new Point { x = 42; }; Point? p = points[1]; """; @@ -117,7 +117,7 @@ struct Foo { int x; }; Foo? foo = null; -Bar !bar = new Bar; +!Bar !bar = new Bar; bar.a = 1; bar.a = 2; return bar.a; @@ -130,7 +130,7 @@ return bar.a; public void testExample() { CodeGen code = new CodeGen(""" struct Vector2D { int x; int y; }; -Vector2D !v = new Vector2D; +!Vector2D !v = new Vector2D; v.x = 1; if (arg) v.y = 2; @@ -169,7 +169,7 @@ arg=0+new s0.0; public void testLoop() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar !bar = new Bar; +!Bar !bar = new Bar; while (arg) { bar.a = bar.a + 2; arg = arg + 1; @@ -184,7 +184,7 @@ return bar.a; public void testIf() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar !bar = new Bar; +!Bar !bar = new Bar; if (arg) bar = null; bar.a = 1; return bar.a; @@ -197,7 +197,7 @@ return bar.a; public void testIf2() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar? !bar = null; +!Bar? !bar = null; if (arg) bar = new Bar; bar.a = 1; return bar.a; @@ -210,7 +210,7 @@ return bar.a; public void testIf3() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar bar = null; +!Bar !bar = null; if (arg) bar = null; bar.a = 1; return bar.a; @@ -223,7 +223,7 @@ return bar.a; public void testIfOrNull() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar? !bar = new Bar; +!Bar? !bar = new Bar; if (arg) bar = null; if( bar ) bar.a = 1; return bar; @@ -237,7 +237,7 @@ return bar; CodeGen code = new CodeGen( """ struct Bar { int a; }; -Bar? !bar = new Bar; +!Bar? !bar = new Bar; if (arg) bar = null; int rez = 3; if( !bar ) rez=4; @@ -252,7 +252,7 @@ return rez; public void testWhileWithNullInside() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0? !v0 = new s0; +!s0? !v0 = new s0; int ret = 0; while(arg) { ret = v0.v0; @@ -273,7 +273,7 @@ struct s0 { int v0; }; s0? v1=new s0; -s0? v1; +!s0? !v1; v1=new s0; """); try { code.parse(); fail(); } @@ -289,7 +289,7 @@ struct Iter { int x; int len; }; -Iter !i = new Iter; +!Iter !i = new Iter; i.len = arg; int sum=0; while( i.x < i.len ) { @@ -307,9 +307,9 @@ return sum; public void test1() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0 !ret = new s0; +!s0 !ret = new s0; while(arg) { - s0 !v0 = new s0; + !s0 !v0 = new s0; v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; @@ -325,8 +325,8 @@ return ret; public void test2() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0 !ret = new s0; -s0 !v0 = new s0; +!s0 !ret = new s0; +!s0 !v0 = new s0; while(arg) { v0.v0 = arg; arg = arg-1; @@ -344,9 +344,9 @@ return ret; public void test3() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0 !ret = new s0; +!s0 !ret = new s0; while(arg < 10) { - s0 !v0 = new s0; + !s0 !v0 = new s0; if (arg == 5) ret=v0; arg = arg + 1; } @@ -423,7 +423,7 @@ s0 v1 = v0; return v1; """); code.parse().opto(); - assertEquals("return s0;", code.print()); + assertEquals("return (const)s0;", code.print()); } @@ -473,9 +473,9 @@ return 0; @Test public void testReadBeforeStores() { var code = new CodeGen(""" struct S { int x; int y; }; - S !a = new S; S !b = new S; + !S !a = new S; !S !b = new S; a.x = 11; b.x = 22; - S !p = a; if (arg) p = b; + !S !p = a; if (arg) p = b; int before = p.x; a.y = 55; b.y = 66; a.x = 33; b.x = 44; @@ -488,7 +488,7 @@ return 0; static final String NESTED_MEMORY = """ struct S { int x; int y; int z; }; - S !s = new S; + !S !s = new S; s.x = 5; s.y = 7; s.z = 11; while (arg > 0) { s.x = s.x + 1; @@ -517,7 +517,7 @@ return 0; @Test public void testMemoryAtEarlyReturns() { var code = new CodeGen(""" struct S { int x; int y; int z; }; - S !s = new S; + !S !s = new S; s.x = 3; s.y = 5; s.z = 7; if (arg) { s.x = 11; s.z = 13; return s; } s.y = 17; @@ -532,9 +532,9 @@ return 0; @Test public void testKeepLoadsAtMerge() { var code = new CodeGen(""" struct S { int x; }; - S !a = new S; S !b = new S; + !S !a = new S; !S !b = new S; a.x = arg; b.x = arg+1; - S !p = a; S !q = b; + !S !p = a; !S !q = b; if (arg<0) { p=b; q=a; } int v; if (arg>1) v=p.x; else v=q.x; @@ -551,7 +551,7 @@ return 0; @Test public void testDropStores() { var code = new CodeGen(""" struct S { int x; }; - S !s = new S; + !S !s = new S; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().opto(); @@ -564,9 +564,9 @@ return 0; @Test public void testKeepReadsBeforeWrites() { var code = new CodeGen(""" struct S { int x; int y; }; - S !a = new S; S !b = new S; + !S !a = new S; !S !b = new S; a.x=arg; b.x=arg+1; - S !p=a; S !q=b; + !S !p=a; !S !q=b; if (arg<0) { p=b; q=a; } int v; if (arg>1) { v=p.x; p.x=41; p.y=5; } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter10bTest.java deleted file mode 100644 index f2b83cdd..00000000 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter10bTest.java +++ /dev/null @@ -1,60 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.codegen.*; -import com.seaofnodes.simple.node.*; -import org.junit.Test; -import static org.junit.Assert.*; - -public class Chapter10bTest { - @Test public void testIndependentField() { - var code = new CodeGen(""" - struct S { int x; int y; }; - S !s = new S; - s.x = 42; - while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } - return s.x; - """).parse().opto(); - var stop = code._stop; - assertEquals("return 42;",stop.toString()); - assertEquals("42",Eval2.eval(code,5)); - assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); - } - - @Test public void testParallelMemoryPhis() { - var code = new CodeGen(""" - struct S { int x; int y; int z; }; - S !a = new S; S !b = new S; - S !p = a; if (arg) p = b; - while (arg > 0) { - a.x = p.x + arg; - a.y = p.y + 2; - a.z = p.z + 3; - arg = arg - 1; - } - return a; - """).parse().opto(); - var stop = code._stop; - int[] phis = {0}; - stop.walk(n -> { - if (n instanceof MemPhiNode) phis[0]++; - if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) - for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) - assertTrue(a<m.nIns() && m.in(a)!=null); - assertFalse(n instanceof PhiNode && n.isMem() && - !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode)); - return null; - }); - assertTrue(phis[0]>=3); - assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4)); - } - - @Test public void testLateSliceWorklist() { - // Seed 97 exposed a store selecting a bulk predecessor without queuing - // it. Keep both the worklist assertion and the final heap check. - for (int seed : new int[]{0,97,123,456}) { - var code = new CodeGen(Chapter10Test.NESTED_MEMORY,com.seaofnodes.simple.type.TypeInteger.BOT,seed,false).parse(); - code.opto(); - assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); - } - } -} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 272d66c8..e93da54b 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,553 +1,60 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.print.IRPrinter; - +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; import org.junit.Test; -import static org.junit.Assert.assertEquals; +import static org.junit.Assert.*; public class Chapter11Test { - - // A placeholder test used to rapidly rotate through fuzzer produced issues - @Test - public void testFuzzer() { - CodeGen code = new CodeGen( -""" -while(---- -arg) { - while(-arg) { - while(-----arg*---0) { - int N=--false==false<--arg; - while(N<-4==N) { - N=N+N; - } - } - { - int kzEl_r7EYz = (3*----0!=-arg) < (37*--97!=0/arg==arg) <= -(--arg!=0); - while(kzEl_r7EYz<---1) { - kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24; - if(7) continue; - kzEl_r7EYz=false; - if(-kzEl_r7EYz+arg<-3) continue; - else { - while(kzEl_r7EYz) continue; - arg=----3; - kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz); - int v2uF_4ba=9; - } - } - } - int pjcp7rv=arg; - { - int m2ya3=--arg-pjcp7rv; - while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) { - m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true); - while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) { - pjcp7rv=-3+-arg; - break; - } - while(-3) { - while(67+0-61) m2ya3=m2ya3; - if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23; - else pjcp7rv=----89; - while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1; - while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62; - } - break; - } - } - { - int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg); - while(arg<-arg) { - arg=arg+--arg; - { - while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33); - pjcp7rv=11; - int c=pjcp7rv; - if(--107) break; - else break; - } - } - } - pjcp7rv=pjcp7rv; - int aR0Wkua=-pjcp7rv==pjcp7rv; - { - if(-0!=-0) while(-true) break; - else { - while(aR0Wkua) pjcp7rv=-0/pjcp7rv; - pjcp7rv=pjcp7rv; - } - } - } - if(-arg) { - { - int Isdlt0fr91=0!=arg; - while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) { - Isdlt0fr91=Isdlt0fr91+-1!=true; - if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91; - int i=---arg<---arg!=--40; - { - int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0; - while(jVX43Ln4Dm<--(3-3)) { - jVX43Ln4Dm=jVX43Ln4Dm+-0<25; - i=24<--(jVX43Ln4Dm); - } - } - i=(arg!=----false>=7); - int Te=5>-arg; - break; - } - } - arg=arg!=--true/arg; - { - int UX=arg; - while(UX<-3*arg) { - UX=UX+arg/-1; - arg=-3--(-UX- -47<arg==--arg==arg)/arg- -UX>=-arg; - if(---12) while(-UX) break; - break; - } - } - continue; - } - if(arg) arg=--0; - else if(1) continue; - int DtTlhjYq=19==arg; - { - arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq); - if(---arg) continue; - else { - int Zsl=40; - while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) { - Zsl=Zsl+arg; - } - } - if((arg)) if(-DtTlhjYq) { - } - else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false; - else { - int lwbF=arg>=0; - while(lwbF<57) { - lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg; - arg=----0+0; - while(49) break; - if(true) DtTlhjYq=-----arg; - DtTlhjYq=0!=-----(0); - } - } - arg=---arg!=DtTlhjYq/--0; - DtTlhjYq=-DtTlhjYq/(--arg<arg); - if(32) { - int q=-DtTlhjYq; - while(q<arg*(0*q)/0) { - q=q+DtTlhjYq; - DtTlhjYq=arg; - } - } - else if(--arg) if(15) break; - else arg=0==arg<=-55>DtTlhjYq; - else { - } - DtTlhjYq=-0; - { - while((0)<-arg) DtTlhjYq=-DtTlhjYq; - } - if(30/--(arg)>=0) DtTlhjYq=-0>=arg; - else { - int Y2wcIQJ=--DtTlhjYq*---11; - if(arg==arg) { - Y2wcIQJ=-----Y2wcIQJ; - Y2wcIQJ=Y2wcIQJ<7; - if(DtTlhjYq) arg=arg; - else break; - while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3; - } - continue; - } - arg=DtTlhjYq; - arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq; - arg=51+---(-true)!=arg!=----1==-DtTlhjYq; - if(11<=arg) if((arg)+79<32+(-arg)) continue; - else if(true==DtTlhjYq) break; - break; - } -} -if(arg!=62==arg) { - while(---arg) { - { - int bhmDacPM=arg/arg; - while(bhmDacPM<arg) { - bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7; - arg=-0; - arg=bhmDacPM>=-arg+-arg; - break; - } - } - int arg=true; - arg=arg<=arg; - { - int KlC=30; - while(KlC<-2) { - KlC=KlC+-1!=25<=-KlC>KlC>----0; - int Ij=arg>=-arg<=---10; - { - int LAbgurVa2R=-arg!=Ij; - while(LAbgurVa2R<-true) { - LAbgurVa2R=LAbgurVa2R+Ij; - KlC=-LAbgurVa2R; - Ij=42*(-Ij>true); - while(Ij) arg=KlC; - KlC=-----7>-(--KlC<--7)==-LAbgurVa2R; - } - } - int a=Ij<=-KlC; - if(Ij) { - int r1W=a!=-false; - } - else { - arg=56>=Ij; - while(54) break; - arg=8>=-(a<--Ij)/a>=-a-KlC; - } - int Yt_T=KlC; - arg=KlC; - } - } - if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg; - else if(----arg) continue; - if(-arg-arg) { - arg=-(-arg)*--(-3)<(-7==-arg----arg); - { - int arg=arg; - while(arg<-0>arg==-arg-(-arg>1+11)) { - arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg; - } - } - arg=-arg+arg; - arg=--47+-arg<1>arg*(-arg==-arg- -0>3); - arg=(----arg)!=arg+--59; - arg=- -4+arg==-(arg)-arg; - } - else { - while(--true-----true*-25+-18>arg>=-----(-arg)---13) { - arg=-0+--true<false; - continue; - } - arg=true<=arg; - break; - } - arg=arg*22<--(0+-arg); - { - continue; + @Test public void testIndependentField() { + var code = new CodeGen(""" + struct S { int x; int y; }; + !S !s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().opto(); + var stop = code._stop; + assertEquals("return 42;",stop.toString()); + assertEquals("42",Eval2.eval(code,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var code = new CodeGen(""" + struct S { int x; int y; int z; }; + !S !a = new S; !S !b = new S; + !S !p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().opto(); + var stop = code._stop; + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a<m.nIns() && m.in(a)!=null); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode)); + return null; + }); + assertTrue(phis[0]>=3); + assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4)); + } + + @Test public void testLateSliceWorklist() { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var code = new CodeGen(Chapter10Test.NESTED_MEMORY,com.seaofnodes.simple.type.TypeInteger.BOT,seed,false).parse(); + code.opto(); + assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); } } - arg=1*---((3<=true)==---2); - arg=7+-(-1); - return arg+--true; -} -else { - int o3ypEsewxM=-(---arg); - int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg; - int L=-arg; - int B4mHcrf=---vzXB; - int oZWGdzZl=-o3ypEsewxM; - int K6tQqa1=11; - while(0!=--L) { - int sdZfTM=vzXB*true+K6tQqa1; - while(sdZfTM<false) { - sdZfTM=sdZfTM+arg; - sdZfTM=oZWGdzZl; - K6tQqa1=-K6tQqa1; - arg=---K6tQqa1; - while((3+-K6tQqa1)<oZWGdzZl) { - if(-----(-1)) sdZfTM=-false; - {} - } - K6tQqa1=vzXB!=-(B4mHcrf+-7>false); - sdZfTM=vzXB; - } - } - L=false; - while(31) B4mHcrf=arg; - oZWGdzZl=-0<--oZWGdzZl<=--2; - if(K6tQqa1>=20<=46) { - if(-1+-L) if(oZWGdzZl) { - int wmhv=-----0; - } - int arg=0; - o3ypEsewxM=---(oZWGdzZl); - return -oZWGdzZl/0; - } - else if(arg) { - int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM; - return -K6tQqa1; - } - else { - if(---0) { - {} - {} - } - return o3ypEsewxM; - } -} -"""); - code.parse().opto().typeCheck().GCM(); - assertEquals("return 9;", code.print()); - } - - - @Test - public void testPrimes() { - CodeGen code = new CodeGen( -""" -if( arg < 2 ) return 0; -int primeCount = 1; -int prime = 3; -while( prime <= arg ) { - int isPrime = 1; - // Check for even case, so the next loop need only check odds - if( (prime/2)*2 == prime ) - continue; - // Check odds up to sqrt of prime - int j = 3; - while( j*j <= prime ) { - if( (prime/j)*j == prime ) { - isPrime = 0; - break; - } - j = j + 2; - } - if( isPrime ) - primeCount = primeCount + 1; - prime = prime + 2; -} -return primeCount; -"""); - code.parse().opto(); - assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi_primeCount,(Phi_primeCount+1))));", code.print()); - assertEquals("0", Eval2.eval(code, 1)); // No primes 1 or below - assertEquals("1", Eval2.eval(code, 2)); // 2 - assertEquals("2", Eval2.eval(code, 3)); // 2, 3 - assertEquals("2", Eval2.eval(code, 4)); // 2, 3 - assertEquals("3", Eval2.eval(code, 5)); // 2, 3, 5 - assertEquals("4", Eval2.eval(code, 10)); // 2, 3, 5, 7 - } - - @Test - public void testAntiDeps1() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v=new S; -v.f = 2; -int i=new S.f; -i=v.f; -if (arg) v.f=1; -return i; -"""); - code.parse().opto(); - assertEquals("return 2;", code.print()); - assertEquals("2", Eval2.eval(code, 0)); - assertEquals("2", Eval2.eval(code, 1)); - } - - @Test - public void testAntiDeps2() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -v.f = arg; -S !t = new S; -int i = 0; -if (arg) { - if (arg+1) v = t; - i = v.f; -} else { - v.f = 2; -} -return i; -"""); - code.parse().opto(); - assertEquals("return Phi(Region,.f,0);", code.print()); - } - - @Test - public void testAntiDeps3() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v0 = new S; -S? v1; -if (arg) v1 = new S; -if (v1) { - v0.f = v1.f; -} else { - v0.f = 2; -} -return v0; -"""); - code.parse().opto(); - assertEquals("return S;", code.print()); - } - - - @Test - public void testAntiDeps4() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -v.f = arg; -S t = new S; -int i = v.f; -if (arg+1) arg= 0; -while (arg) v.f = 2; -return i; -"""); - code.parse().opto(); - assertEquals("return arg;", code.print()); - } - - @Test - public void testAntiDeps5() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -while(1) { - while(arg+1) { arg=arg-1; } - if (arg) break; - v.f = 2; -} -return v; -"""); - code.parse().opto(); - assertEquals("return S;", code.print()); - } - - @Test - public void testAntiDeps6() { - CodeGen code = new CodeGen( -""" -struct s { int v; }; -s !ptr=new s; -while( -arg ) - ptr = new s; -while(1) - arg = arg+ptr.v; -"""); - code.parse().opto(); - assertEquals("return Top;", code.print()); - } - - @Test - public void testAntiDeps7() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -S t = new S; -int i = v.f; -while (arg) { - v.f = arg; - arg = arg-1; -} -return i; -"""); - code.parse().opto(); - assertEquals("return 0;", code.print()); - } - - @Test - public void testAntiDeps8() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -S t = new S; -while(arg) { - arg=arg-1; - int f = v.f; - v.f = 2; - if (arg) arg = f; - else v.f = 3; -} -return arg; -"""); - code.parse().opto(); - assertEquals("return 0;", code.print()); - } - - @Test - public void testAntiDeps9() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -S t = new S; -if (arg) { - v.f=2; - int i=t.f; - v.f=i; -} -return v; -"""); - code.parse().opto(); - assertEquals("return S;", code.print()); - } - - @Test - public void testExample2() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -int i = arg; -while (arg > 0) { - int j = i/3; - if (arg == 5) - v.f = j; - arg = arg - 1; -} -return v; - """); - code.parse().opto(); - //assertEquals("return new S;", code.print()); - } - - @Test - public void testScheduleUse() { - CodeGen code = new CodeGen( -""" -int v0=0; -while(0>=0) { - u1 v1=0; - v1=v0; - if(v1*0) - v0=-v1; -} -return 0; -"""); - code.parse().opto(); - assertEquals("return Top;", code.print()); - } - - @Test - public void testLoopCarriedDep() { - CodeGen code = new CodeGen( -""" -u32 v0=0; -{ - int v1=0; - while(v1) { - v1=1>>>v0!=0; - v0=v1/0; - } - return v1; -} -"""); - code.parse().opto(); - assertEquals("return 0;", code.print()); - } - } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java index c50be559..8e9aaed6 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,82 +1,281 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter12Test { - @Test public void testSubZeroFloat() { - var code = new CodeGen("flt x = arg; return 0-x;").parse().opto().typeCheck(); - // Compare strings so +0.0 and -0.0 remain distinct. - assertEquals("0.0", Eval2.eval(code,0)); - assertEquals("-1.0", Eval2.eval(code,1)); + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } - @Test public void testDeadNumericReturns() { - for( String[] test : new String[][] { - {"if(1) return 7; else return 2.5;", "7"}, - {"if(0) return 7; else return 2.5;", "2.5"}, - {"return 7; return 2.5;", "7"}, - {"return 2.5; return 7;", "2.5"} - } ) { - String src = test[0]; - var code = new CodeGen(src).parse().opto().typeCheck(); - assertEquals(src,test[1],Eval2.eval(code,0)); - } + @Test + public void testLinkedList0() { + CodeGen code = new CodeGen( +""" +struct LLI { !LLI? !next; int i; }; +!LLI? !head = null; +while( arg ) { + !LLI !x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +return head.next.i; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } } + @Test + public void testLinkedList1() { + CodeGen code = new CodeGen( +""" +struct LLI { !LLI? !next; int q; }; +!LLI? !head = null; +while( arg ) { + !LLI !x = new LLI; + x.next = head; + x.q = arg; + head = x; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.q; +"""); + code.parse().opto().typeCheck(); + assertEquals("return Phi(Region,0,1,.q);", code.print()); + assertEquals("2", Eval2.eval(code, 3)); + } @Test - public void testJig() { + public void testCoRecur() { CodeGen code = new CodeGen( """ -return 3.14; +struct int0 { int i; !flt0? !f; }; +struct flt0 { flt f; !int0? !i; }; +!int0 !i0 = new int0; +i0.i = 17; +!flt0 !f0 = new flt0; +f0.f = 3.14; +i0.f = f0; +f0.i = i0; +return f0.i.f.i.i; """); code.parse().opto(); - assertEquals("return 3.14;", code.print()); - assertEquals("3.14", Eval2.eval(code, 0)); + assertEquals("return 17;", code.print()); } @Test - public void testFloat() { + public void testNullRef0() { CodeGen code = new CodeGen( """ -return 3.14; +struct N { !N? !next; int i; }; +N n = new N; +return n.next; """); code.parse().opto(); - assertEquals("return 3.14;", code.print()); - assertEquals("3.14", Eval2.eval(code, 0)); + assertEquals("return null;", code.print()); } @Test - public void testSquareRoot() { + public void testNullRef1() { CodeGen code = new CodeGen( """ -flt guess = arg; -while( 1 ) { - flt next = (arg/guess + guess)/2; - if( next == guess ) break; - guess = next; -} -return guess; +struct M { int m; }; +struct N { !M !next; int i; }; +N n = new N { next = new M; }; +return n.next; +"""); + code.parse().opto(); + assertEquals("return (const)M;", code.print()); + } + + @Test + public void testNullRef2() { + CodeGen code = new CodeGen( +""" +struct M { int m; }; +struct N { !M !next; int i; }; +N n = new N { next = null; }; +return n.next; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } + } + + @Test + public void testNullRef3() { + CodeGen code = new CodeGen( +""" +struct N { !N? !next; int i; }; +!N !n = new N; +n.i = 3.14; +return n.i; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Type 3.14 is not of declared type i64",e.getMessage()); } + } + + @Test + public void testNullRef4() { + CodeGen code = new CodeGen("return -null-5/null-5;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot '//' null",e.getMessage()); } + } + + @Test public void testNullRef5() { + CodeGen code = new CodeGen("return null+42;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot '+' null",e.getMessage()); } + } + + @Test + public void testEmpty() { + CodeGen code = new CodeGen( +""" +struct S{}; +return 0; """); code.parse().opto(); - assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print()); - assertEquals("3.0", Eval2.eval(code, 9)); - assertEquals("1.414213562373095", Eval2.eval(code, 2)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test - public void testFPOps() { + public void testForwardRef0() { CodeGen code = new CodeGen( """ -flt x = arg; -return x+1==x; +struct S1 { !S2? !s; }; +return new S2; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } + } + + @Test + public void testForwardRef1() { + CodeGen code = new CodeGen( +""" +struct S1 { !S2? !s; }; +struct S2 { int x; }; +return new S1.s=new S2; """); code.parse().opto(); - assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); - assertEquals("0", Eval2.eval(code, 1)); + assertEquals("return S2;", code.print()); + } + + @Test + public void testcheckNull() { + CodeGen code = new CodeGen( +""" +struct I { int i; }; +struct P { !I? !pi; }; +!P !p1 = new P; +!P !p2 = new P; +p2.pi = new I; +p2.pi.i = 2; +if (arg) p1 = new P; +return p1.pi.i + 1; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + } + + @Test + public void testCoRecur2() { + CodeGen code = new CodeGen( +""" +struct A { !B? !f0; !C? !f1; }; !A !a = new A; +struct B { !C? !f0; !A? !f1; }; !B !b = new B; +struct C { !A? !f0; !B? !f1; }; !C !c = new C; + +a.f0=b; a.f1=c; +b.f0=c; b.f1=a; +c.f0=a; c.f1=b; + +return a.f0.f1.f0.f1.f0; + +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return B;", code._stop.toString()); + assertEquals("B{f0=C},f1=A{f0=$cyclic,f1=$cyclic}}", Eval2.eval(code, 0)); + } + + @Test + public void testCoRecur3() { + CodeGen code = new CodeGen( +""" +struct A { !L? !a; !T? !b; !F? !c; }; !A !a = new A; +struct B { !M? !a; !U? !b; !G? !c; }; !B !b = new B; +struct C { !N? !a; !V? !b; !H? !c; }; !C !c = new C; +struct D { !O? !a; !W? !b; !I? !c; }; !D !d = new D; +struct E { !P? !a; !X? !b; !J? !c; }; !E !e = new E; +struct F { !Q? !a; !Y? !b; !K? !c; }; !F !f = new F; +struct G { !R? !a; !Z? !b; !L? !c; }; !G !g = new G; +struct H { !S? !a; !A? !b; !M? !c; }; !H !h = new H; +struct I { !T? !a; !B? !b; !N? !c; }; !I !i = new I; +struct J { !U? !a; !C? !b; !O? !c; }; !J !j = new J; +struct K { !V? !a; !D? !b; !P? !c; }; !K !k = new K; +struct L { !W? !a; !E? !b; !Q? !c; }; !L !l = new L; +struct M { !X? !a; !F? !b; !R? !c; }; !M !m = new M; +struct N { !Y? !a; !G? !b; !S? !c; }; !N !n = new N; +struct O { !Z? !a; !H? !b; !T? !c; }; !O !o = new O; +struct P { !A? !a; !I? !b; !U? !c; }; !P !p = new P; +struct Q { !B? !a; !J? !b; !V? !c; }; !Q !q = new Q; +struct R { !C? !a; !K? !b; !W? !c; }; !R !r = new R; +struct S { !D? !a; !L? !b; !X? !c; }; !S !s = new S; +struct T { !E? !a; !M? !b; !Y? !c; }; !T !t = new T; +struct U { !F? !a; !N? !b; !Z? !c; }; !U !u = new U; +struct V { !G? !a; !O? !b; !A? !c; }; !V !v = new V; +struct W { !H? !a; !P? !b; !B? !c; }; !W !w = new W; +struct X { !I? !a; !Q? !b; !C? !c; }; !X !x = new X; +struct Y { !J? !a; !R? !b; !D? !c; }; !Y !y = new Y; +struct Z { !K? !a; !S? !b; !E? !c; }; !Z !z = new Z; + +a.a=l; a.b=t; a.c=f; +b.a=m; b.b=u; b.c=g; +c.a=n; c.b=v; c.c=h; +d.a=o; d.b=w; d.c=i; +e.a=p; e.b=x; e.c=j; +f.a=q; f.b=y; f.c=k; +g.a=r; g.b=z; g.c=l; +h.a=s; h.b=a; h.c=m; +i.a=t; i.b=b; i.c=n; +j.a=u; j.b=c; j.c=o; +k.a=v; k.b=d; k.c=p; +l.a=w; l.b=e; l.c=q; +m.a=x; m.b=f; m.c=r; +n.a=y; n.b=g; n.c=s; +o.a=z; o.b=h; o.c=t; +p.a=a; p.b=i; p.c=u; +q.a=b; q.b=j; q.c=v; +r.a=c; r.b=k; r.c=w; +s.a=d; s.b=l; s.c=x; +t.a=e; t.b=m; t.c=y; +u.a=f; u.b=n; u.c=z; +v.a=g; v.b=o; v.c=a; +w.a=h; w.b=p; w.c=b; +x.a=i; x.b=q; x.c=c; +y.a=j; y.b=r; y.c=d; +z.a=k; z.b=s; z.c=e; + +return a.b.c.a.b.c.a.b.c.a.b.c.a.b.c.a.b.c; + +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return R;", code._stop.toString()); + assertEquals("R{a=C{a=N},b=V},c=H}},b=K{a=$cyclic,b=D{a=O},b=W},c=I}},c=P}},c=$cyclic}", Eval2.eval(code, 0)); } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 4e1db3b4..63f1d12c 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -1,281 +1,553 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; + + import org.junit.Test; import static org.junit.Assert.assertEquals; -import static org.junit.Assert.fail; public class Chapter13Test { + + // A placeholder test used to rapidly rotate through fuzzer produced issues @Test - public void testJig() { + public void testFuzzer() { CodeGen code = new CodeGen( """ -return 3.14; +while(---- -arg) { + while(-arg) { + while(-----arg*---0) { + int N=--false==false<--arg; + while(N<-4==N) { + N=N+N; + } + } + { + int kzEl_r7EYz = (3*----0!=-arg) < (37*--97!=0/arg==arg) <= -(--arg!=0); + while(kzEl_r7EYz<---1) { + kzEl_r7EYz=kzEl_r7EYz+kzEl_r7EYz*arg>=24; + if(7) continue; + kzEl_r7EYz=false; + if(-kzEl_r7EYz+arg<-3) continue; + else { + while(kzEl_r7EYz) continue; + arg=----3; + kzEl_r7EYz=-(-----arg*1>-kzEl_r7EYz); + int v2uF_4ba=9; + } + } + } + int pjcp7rv=arg; + { + int m2ya3=--arg-pjcp7rv; + while(m2ya3<-----pjcp7rv>=pjcp7rv+--pjcp7rv!=---pjcp7rv!=-arg<---(-m2ya3)>m2ya3<=-----true>14!=--m2ya3) { + m2ya3=m2ya3+-(--0<=false<pjcp7rv/arg<=-true); + while((--m2ya3)<--arg<-----arg*false!=arg<pjcp7rv*arg) { + pjcp7rv=-3+-arg; + break; + } + while(-3) { + while(67+0-61) m2ya3=m2ya3; + if(----pjcp7rv==---(---arg)) pjcp7rv=0!=-23; + else pjcp7rv=----89; + while(m2ya3!=m2ya3<pjcp7rv) m2ya3=1; + while(--arg<=pjcp7rv) pjcp7rv=-32<=-m2ya3+62; + } + break; + } + } + { + int arg=-1<-9!=(-arg>=-pjcp7rv>=arg<=arg); + while(arg<-arg) { + arg=arg+--arg; + { + while((--93)--pjcp7rv*-pjcp7rv+arg) arg=0-(6>=(--(---41/(0))!=--pjcp7rv)>=---2*33); + pjcp7rv=11; + int c=pjcp7rv; + if(--107) break; + else break; + } + } + } + pjcp7rv=pjcp7rv; + int aR0Wkua=-pjcp7rv==pjcp7rv; + { + if(-0!=-0) while(-true) break; + else { + while(aR0Wkua) pjcp7rv=-0/pjcp7rv; + pjcp7rv=pjcp7rv; + } + } + } + if(-arg) { + { + int Isdlt0fr91=0!=arg; + while(Isdlt0fr91<-Isdlt0fr91==-Isdlt0fr91+true) { + Isdlt0fr91=Isdlt0fr91+-1!=true; + if(-arg) if(--arg<=Isdlt0fr91) Isdlt0fr91=-Isdlt0fr91; + int i=---arg<---arg!=--40; + { + int jVX43Ln4Dm=-(6)==-Isdlt0fr91/----0; + while(jVX43Ln4Dm<--(3-3)) { + jVX43Ln4Dm=jVX43Ln4Dm+-0<25; + i=24<--(jVX43Ln4Dm); + } + } + i=(arg!=----false>=7); + int Te=5>-arg; + break; + } + } + arg=arg!=--true/arg; + { + int UX=arg; + while(UX<-3*arg) { + UX=UX+arg/-1; + arg=-3--(-UX- -47<arg==--arg==arg)/arg- -UX>=-arg; + if(---12) while(-UX) break; + break; + } + } + continue; + } + if(arg) arg=--0; + else if(1) continue; + int DtTlhjYq=19==arg; + { + arg=--DtTlhjYq<=(DtTlhjYq/---DtTlhjYq<=-DtTlhjYq); + if(---arg) continue; + else { + int Zsl=40; + while(Zsl<--Zsl--false>((Zsl))==Zsl!=--DtTlhjYq-DtTlhjYq-DtTlhjYq) { + Zsl=Zsl+arg; + } + } + if((arg)) if(-DtTlhjYq) { + } + else while(((2)==3*arg/DtTlhjYq)<=0==---arg) return false; + else { + int lwbF=arg>=0; + while(lwbF<57) { + lwbF=lwbF+--(-arg+lwbF)>=-2>=arg!=arg; + arg=----0+0; + while(49) break; + if(true) DtTlhjYq=-----arg; + DtTlhjYq=0!=-----(0); + } + } + arg=---arg!=DtTlhjYq/--0; + DtTlhjYq=-DtTlhjYq/(--arg<arg); + if(32) { + int q=-DtTlhjYq; + while(q<arg*(0*q)/0) { + q=q+DtTlhjYq; + DtTlhjYq=arg; + } + } + else if(--arg) if(15) break; + else arg=0==arg<=-55>DtTlhjYq; + else { + } + DtTlhjYq=-0; + { + while((0)<-arg) DtTlhjYq=-DtTlhjYq; + } + if(30/--(arg)>=0) DtTlhjYq=-0>=arg; + else { + int Y2wcIQJ=--DtTlhjYq*---11; + if(arg==arg) { + Y2wcIQJ=-----Y2wcIQJ; + Y2wcIQJ=Y2wcIQJ<7; + if(DtTlhjYq) arg=arg; + else break; + while(-arg!=-31==(false<=-15>=-DtTlhjYq+--6*-----Y2wcIQJ<=---arg!=-Y2wcIQJ<=---0<-arg*--Y2wcIQJ)) DtTlhjYq=arg!=3; + } + continue; + } + arg=DtTlhjYq; + arg=--3/(---arg)>=80>=-DtTlhjYq<=DtTlhjYq; + arg=51+---(-true)!=arg!=----1==-DtTlhjYq; + if(11<=arg) if((arg)+79<32+(-arg)) continue; + else if(true==DtTlhjYq) break; + break; + } +} +if(arg!=62==arg) { + while(---arg) { + { + int bhmDacPM=arg/arg; + while(bhmDacPM<arg) { + bhmDacPM=bhmDacPM+80*((-bhmDacPM)/---bhmDacPM>1)<bhmDacPM-2!=7; + arg=-0; + arg=bhmDacPM>=-arg+-arg; + break; + } + } + int arg=true; + arg=arg<=arg; + { + int KlC=30; + while(KlC<-2) { + KlC=KlC+-1!=25<=-KlC>KlC>----0; + int Ij=arg>=-arg<=---10; + { + int LAbgurVa2R=-arg!=Ij; + while(LAbgurVa2R<-true) { + LAbgurVa2R=LAbgurVa2R+Ij; + KlC=-LAbgurVa2R; + Ij=42*(-Ij>true); + while(Ij) arg=KlC; + KlC=-----7>-(--KlC<--7)==-LAbgurVa2R; + } + } + int a=Ij<=-KlC; + if(Ij) { + int r1W=a!=-false; + } + else { + arg=56>=Ij; + while(54) break; + arg=8>=-(a<--Ij)/a>=-a-KlC; + } + int Yt_T=KlC; + arg=KlC; + } + } + if(----false/--arg/12+-----0) if(-9+-arg) while(arg!=(arg)) arg=--1>=-71-arg!=---(--arg*11+102)/--arg; + else if(----arg) continue; + if(-arg-arg) { + arg=-(-arg)*--(-3)<(-7==-arg----arg); + { + int arg=arg; + while(arg<-0>arg==-arg-(-arg>1+11)) { + arg=arg+6-arg!=--0>---30>=---arg<=arg/(3)+---arg; + } + } + arg=-arg+arg; + arg=--47+-arg<1>arg*(-arg==-arg- -0>3); + arg=(----arg)!=arg+--59; + arg=- -4+arg==-(arg)-arg; + } + else { + while(--true-----true*-25+-18>arg>=-----(-arg)---13) { + arg=-0+--true<false; + continue; + } + arg=true<=arg; + break; + } + arg=arg*22<--(0+-arg); + { + continue; + } + } + arg=1*---((3<=true)==---2); + arg=7+-(-1); + return arg+--true; +} +else { + int o3ypEsewxM=-(---arg); + int vzXB=(-(---11<=--o3ypEsewxM>=--0))<=-0/-arg; + int L=-arg; + int B4mHcrf=---vzXB; + int oZWGdzZl=-o3ypEsewxM; + int K6tQqa1=11; + while(0!=--L) { + int sdZfTM=vzXB*true+K6tQqa1; + while(sdZfTM<false) { + sdZfTM=sdZfTM+arg; + sdZfTM=oZWGdzZl; + K6tQqa1=-K6tQqa1; + arg=---K6tQqa1; + while((3+-K6tQqa1)<oZWGdzZl) { + if(-----(-1)) sdZfTM=-false; + {} + } + K6tQqa1=vzXB!=-(B4mHcrf+-7>false); + sdZfTM=vzXB; + } + } + L=false; + while(31) B4mHcrf=arg; + oZWGdzZl=-0<--oZWGdzZl<=--2; + if(K6tQqa1>=20<=46) { + if(-1+-L) if(oZWGdzZl) { + int wmhv=-----0; + } + int arg=0; + o3ypEsewxM=---(oZWGdzZl); + return -oZWGdzZl/0; + } + else if(arg) { + int yKk5=B4mHcrf>=4>K6tQqa1<-B4mHcrf/o3ypEsewxM; + return -K6tQqa1; + } + else { + if(---0) { + {} + {} + } + return o3ypEsewxM; + } +} """); - code.parse().opto(); - assertEquals("return 3.14;", code.print()); - assertEquals("3.14", Eval2.eval(code, 0)); + code.parse().opto().typeCheck().GCM(); + assertEquals("return 9;", code.print()); } + @Test - public void testLinkedList0() { + public void testPrimes() { CodeGen code = new CodeGen( """ -struct LLI { LLI? next; int i; }; -LLI? !head = null; -while( arg ) { - LLI !x = new LLI; - x.next = head; - x.i = arg; - head = x; - arg = arg-1; +if( arg < 2 ) return 0; +int primeCount = 1; +int prime = 3; +while( prime <= arg ) { + int isPrime = 1; + // Check for even case, so the next loop need only check odds + if( (prime/2)*2 == prime ) + continue; + // Check odds up to sqrt of prime + int j = 3; + while( j*j <= prime ) { + if( (prime/j)*j == prime ) { + isPrime = 0; + break; + } + j = j + 2; + } + if( isPrime ) + primeCount = primeCount + 1; + prime = prime + 2; } -return head.next.i; +return primeCount; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } + code.parse().opto(); + assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi_primeCount,(Phi_primeCount+1))));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); // No primes 1 or below + assertEquals("1", Eval2.eval(code, 2)); // 2 + assertEquals("2", Eval2.eval(code, 3)); // 2, 3 + assertEquals("2", Eval2.eval(code, 4)); // 2, 3 + assertEquals("3", Eval2.eval(code, 5)); // 2, 3, 5 + assertEquals("4", Eval2.eval(code, 10)); // 2, 3, 5, 7 } @Test - public void testLinkedList1() { + public void testAntiDeps1() { CodeGen code = new CodeGen( """ -struct LLI { LLI? next; int q; }; -LLI? !head = null; -while( arg ) { - LLI !x = new LLI; - x.next = head; - x.q = arg; - head = x; - arg = arg-1; -} -if( !head ) return 0; -LLI? next = head.next; -if( next==null ) return 1; -return next.q; +struct S { int f; }; +!S !v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; """); - code.parse().opto().typeCheck(); - assertEquals("return Phi(Region,0,1,.q);", code.print()); - assertEquals("2", Eval2.eval(code, 3)); + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertEquals("2", Eval2.eval(code, 0)); + assertEquals("2", Eval2.eval(code, 1)); } @Test - public void testCoRecur() { + public void testAntiDeps2() { CodeGen code = new CodeGen( """ -struct int0 { int i; flt0? f; }; -struct flt0 { flt f; int0? i; }; -int0 !i0 = new int0; -i0.i = 17; -flt0 !f0 = new flt0; -f0.f = 3.14; -i0.f = f0; -f0.i = i0; -return f0.i.f.i.i; +struct S { int f; }; +!S !v = new S; +v.f = arg; +!S !t = new S; +int i = 0; +if (arg) { + if (arg+1) v = t; + i = v.f; +} else { + v.f = 2; +} +return i; """); code.parse().opto(); - assertEquals("return 17;", code.print()); + assertEquals("return Phi(Region,.f,0);", code.print()); } @Test - public void testNullRef0() { + public void testAntiDeps3() { CodeGen code = new CodeGen( """ -struct N { N? next; int i; }; -N n = new N; -return n.next; +struct S { int f; }; +!S !v0 = new S; +!S? !v1; +if (arg) v1 = new S; +if (v1) { + v0.f = v1.f; +} else { + v0.f = 2; +} +return v0; """); code.parse().opto(); - assertEquals("return null;", code.print()); + assertEquals("return S;", code.print()); } + @Test - public void testNullRef1() { + public void testAntiDeps4() { CodeGen code = new CodeGen( """ -struct M { int m; }; -struct N { M next; int i; }; -N n = new N { next = new M; }; -return n.next; +struct S { int f; }; +!S !v = new S; +v.f = arg; +S t = new S; +int i = v.f; +if (arg+1) arg= 0; +while (arg) v.f = 2; +return i; """); code.parse().opto(); - assertEquals("return (const)M;", code.print()); + assertEquals("return arg;", code.print()); } @Test - public void testNullRef2() { + public void testAntiDeps5() { CodeGen code = new CodeGen( """ -struct M { int m; }; -struct N { M next; int i; }; -N n = new N { next = null; }; -return n.next; +struct S { int f; }; +!S !v = new S; +while(1) { + while(arg+1) { arg=arg-1; } + if (arg) break; + v.f = 2; +} +return v; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } + code.parse().opto(); + assertEquals("return S;", code.print()); } @Test - public void testNullRef3() { + public void testAntiDeps6() { CodeGen code = new CodeGen( """ -struct N { N? next; int i; }; -N !n = new N; -n.i = 3.14; -return n.i; +struct s { int v; }; +!s !ptr=new s; +while( -arg ) + ptr = new s; +while(1) + arg = arg+ptr.v; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Type 3.14 is not of declared type i64",e.getMessage()); } - } - - @Test - public void testNullRef4() { - CodeGen code = new CodeGen("return -null-5/null-5;"); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot '//' null",e.getMessage()); } - } - - @Test public void testNullRef5() { - CodeGen code = new CodeGen("return null+42;"); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot '+' null",e.getMessage()); } + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test - public void testEmpty() { + public void testAntiDeps7() { CodeGen code = new CodeGen( """ -struct S{}; -return 0; +struct S { int f; }; +!S !v = new S; +S t = new S; +int i = v.f; +while (arg) { + v.f = arg; + arg = arg-1; +} +return i; """); code.parse().opto(); assertEquals("return 0;", code.print()); - assertEquals("0", Eval2.eval(code, 0)); } @Test - public void testForwardRef0() { + public void testAntiDeps8() { CodeGen code = new CodeGen( """ -struct S1 { S2? s; }; -return new S2; +struct S { int f; }; +!S !v = new S; +S t = new S; +while(arg) { + arg=arg-1; + int f = v.f; + v.f = 2; + if (arg) arg = f; + else v.f = 3; +} +return arg; """); - try { code.parse().opto(); fail(); } - catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test - public void testForwardRef1() { + public void testAntiDeps9() { CodeGen code = new CodeGen( """ -struct S1 { S2? s; }; -struct S2 { int x; }; -return new S1.s=new S2; +struct S { int f; }; +!S !v = new S; +S t = new S; +if (arg) { + v.f=2; + int i=t.f; + v.f=i; +} +return v; """); code.parse().opto(); - assertEquals("return S2;", code.print()); + assertEquals("return S;", code.print()); } @Test - public void testcheckNull() { + public void testExample2() { CodeGen code = new CodeGen( """ -struct I { int i; }; -struct P { I? pi; }; -P !p1 = new P; -P !p2 = new P; -p2.pi = new I; -p2.pi.i = 2; -if (arg) p1 = new P; -return p1.pi.i + 1; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } +struct S { int f; }; +!S !v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; + """); + code.parse().opto(); + //assertEquals("return new S;", code.print()); } @Test - public void testCoRecur2() { + public void testScheduleUse() { CodeGen code = new CodeGen( """ -struct A { B? f0; C? f1; }; A !a = new A; -struct B { C? f0; A? f1; }; B !b = new B; -struct C { A? f0; B? f1; }; C !c = new C; - -a.f0=b; a.f1=c; -b.f0=c; b.f1=a; -c.f0=a; c.f1=b; - -return a.f0.f1.f0.f1.f0; - +int v0=0; +while(0>=0) { + u1 v1=0; + v1=v0; + if(v1*0) + v0=-v1; +} +return 0; """); - code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("return B;", code._stop.toString()); - assertEquals("B{f0=C},f1=A{f0=$cyclic,f1=$cyclic}}", Eval2.eval(code, 0)); + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test - public void testCoRecur3() { + public void testLoopCarriedDep() { CodeGen code = new CodeGen( """ -struct A { L? a; T? b; F? c; }; A !a = new A; -struct B { M? a; U? b; G? c; }; B !b = new B; -struct C { N? a; V? b; H? c; }; C !c = new C; -struct D { O? a; W? b; I? c; }; D !d = new D; -struct E { P? a; X? b; J? c; }; E !e = new E; -struct F { Q? a; Y? b; K? c; }; F !f = new F; -struct G { R? a; Z? b; L? c; }; G !g = new G; -struct H { S? a; A? b; M? c; }; H !h = new H; -struct I { T? a; B? b; N? c; }; I !i = new I; -struct J { U? a; C? b; O? c; }; J !j = new J; -struct K { V? a; D? b; P? c; }; K !k = new K; -struct L { W? a; E? b; Q? c; }; L !l = new L; -struct M { X? a; F? b; R? c; }; M !m = new M; -struct N { Y? a; G? b; S? c; }; N !n = new N; -struct O { Z? a; H? b; T? c; }; O !o = new O; -struct P { A? a; I? b; U? c; }; P !p = new P; -struct Q { B? a; J? b; V? c; }; Q !q = new Q; -struct R { C? a; K? b; W? c; }; R !r = new R; -struct S { D? a; L? b; X? c; }; S !s = new S; -struct T { E? a; M? b; Y? c; }; T !t = new T; -struct U { F? a; N? b; Z? c; }; U !u = new U; -struct V { G? a; O? b; A? c; }; V !v = new V; -struct W { H? a; P? b; B? c; }; W !w = new W; -struct X { I? a; Q? b; C? c; }; X !x = new X; -struct Y { J? a; R? b; D? c; }; Y !y = new Y; -struct Z { K? a; S? b; E? c; }; Z !z = new Z; - -a.a=l; a.b=t; a.c=f; -b.a=m; b.b=u; b.c=g; -c.a=n; c.b=v; c.c=h; -d.a=o; d.b=w; d.c=i; -e.a=p; e.b=x; e.c=j; -f.a=q; f.b=y; f.c=k; -g.a=r; g.b=z; g.c=l; -h.a=s; h.b=a; h.c=m; -i.a=t; i.b=b; i.c=n; -j.a=u; j.b=c; j.c=o; -k.a=v; k.b=d; k.c=p; -l.a=w; l.b=e; l.c=q; -m.a=x; m.b=f; m.c=r; -n.a=y; n.b=g; n.c=s; -o.a=z; o.b=h; o.c=t; -p.a=a; p.b=i; p.c=u; -q.a=b; q.b=j; q.c=v; -r.a=c; r.b=k; r.c=w; -s.a=d; s.b=l; s.c=x; -t.a=e; t.b=m; t.c=y; -u.a=f; u.b=n; u.c=z; -v.a=g; v.b=o; v.c=a; -w.a=h; w.b=p; w.c=b; -x.a=i; x.b=q; x.c=c; -y.a=j; y.b=r; y.c=d; -z.a=k; z.b=s; z.c=e; - -return a.b.c.a.b.c.a.b.c.a.b.c.a.b.c.a.b.c; - +u32 v0=0; +{ + int v1=0; + while(v1) { + v1=1>>>v0!=0; + v0=v1/0; + } + return v1; +} """); - code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("return R;", code._stop.toString()); - assertEquals("R{a=C{a=N},b=V},c=H}},b=K{a=$cyclic,b=D{a=O},b=W},c=I}},c=P}},c=$cyclic}", Eval2.eval(code, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); } + } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java new file mode 100644 index 00000000..009beb0b --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -0,0 +1,82 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter14FloatTest { + @Test public void testSubZeroFloat() { + var code = new CodeGen("flt x = arg; return 0-x;").parse().opto().typeCheck(); + // Compare strings so +0.0 and -0.0 remain distinct. + assertEquals("0.0", Eval2.eval(code,0)); + assertEquals("-1.0", Eval2.eval(code,1)); + } + + @Test public void testDeadNumericReturns() { + for( String[] test : new String[][] { + {"if(1) return 7; else return 2.5;", "7"}, + {"if(0) return 7; else return 2.5;", "2.5"}, + {"return 7; return 2.5;", "7"}, + {"return 2.5; return 7;", "2.5"} + } ) { + String src = test[0]; + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(src,test[1],Eval2.eval(code,0)); + } + } + + + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testFloat() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testSquareRoot() { + CodeGen code = new CodeGen( +""" +flt guess = arg; +while( 1 ) { + flt next = (arg/guess + guess)/2; + if( next == guess ) break; + guess = next; +} +return guess; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print()); + assertEquals("3.0", Eval2.eval(code, 9)); + assertEquals("1.414213562373095", Eval2.eval(code, 2)); + } + + @Test + public void testFPOps() { + CodeGen code = new CodeGen( +""" +flt x = arg; +return x+1==x; +"""); + code.parse().opto(); + assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); + } +} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 7af35b56..da7e50bc 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -93,7 +93,7 @@ return b; CodeGen code = new CodeGen( """ struct Foo { u1 b; }; -Foo !f = new Foo; +!Foo !f = new Foo; f.b = 123; return f.b; """); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 6ba4e2b1..66a50d0f 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -25,8 +25,8 @@ return 3.14; public void testCyclic() { CodeGen code = new CodeGen( """ -struct C { C? l; }; -C !c = new C; +struct C { !C? !l; }; +!C !c = new C; c.l = c; return c; """); @@ -98,7 +98,7 @@ return a[0]; CodeGen code = new CodeGen( """ struct A { int i; }; -A?[] !a = new A?[2]; +!A?[] !a = new !A?[2]; return a; """); code.parse().opto(); @@ -112,16 +112,16 @@ return a; """ struct S { int x; flt y; }; // A new S -S !s = new S; s.x=99; s.y = 3.14; +!S !s = new S; s.x=99; s.y = 3.14; // Double-d array of Ss. Fill in one row. -S?[]?[] !iss = new S?[]?[2]; -iss[0] = new S?[7]; +!S?[]?[] !iss = new !S?[]?[2]; +iss[0] = new !S?[7]; iss[0][2] = s; // Now pull out the filled-in value, with null checks flt rez; -S?[]? is = iss[arg]; +!S?[]? is = iss[arg]; if( !is ) rez = 1.2; else { S? i = is[2]; @@ -142,11 +142,11 @@ return rez; """ struct S { int x; flt y; }; // A new S -S !s = new S; s.x=99; s.y = 3.14; +!S !s = new S; s.x=99; s.y = 3.14; // Double-d array of Ss. Fill in one row. -S?[]?[] !iss = new S?[]?[2]; -iss[0] = new S?[7]; +!S?[]?[] !iss = new !S?[]?[2]; +iss[0] = new !S?[7]; iss[0][2] = s; // Now pull out the filled-in value, with null checks @@ -167,9 +167,9 @@ return rez;"""); CodeGen code = new CodeGen( """ // Can we define a forward-reference array? -struct Tree { Tree?[]? _kids; }; -Tree !root = new Tree; -root._kids = new Tree?[2]; // NO BANG SO ARRAY IS OF IMMUTABLE TREES???? +struct Tree { !Tree?[]? !_kids; }; +!Tree !root = new Tree; +root._kids = new !Tree?[2]; // NO BANG SO ARRAY IS OF IMMUTABLE TREES???? root._kids[0] = new Tree; return root; """); @@ -182,7 +182,7 @@ return root; public void testNestedStructAddMemProj() { CodeGen code = new CodeGen( """ -struct S { int a; int[] b; }; +struct S { int a; int[] !b; }; return 0; """); code.parse().opto(); @@ -227,8 +227,8 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 CodeGen code = new CodeGen( """ struct S {int i; flt f;}; -S !s1 = new S; -S !s2 = new S; +!S !s1 = new S; +!S !s2 = new S; s2.i = 3; s2.f = 2.0; if (arg) s1 = new S; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 57ec5508..692ac8d5 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -42,31 +42,6 @@ return x+y; assertEquals("5", Eval2.eval(code, 0)); } -// @Test -// public void testFinal0() { -// CodeGen code = new CodeGen( -//""" -//int !x=2; -//x=3; -//return x; -//"""); -// try { code.parse().opto(); fail(); } -// catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } -// } - - @Test - public void testFinal1() { - CodeGen code = new CodeGen( -""" -int x=2, y=3; -if( arg ) { int x = y; x = x*x; y=x; } // Shadow final x -return y; -"""); - code.parse().opto(); - assertEquals("return Phi(Region,9,3);", code.print()); - assertEquals("3", Eval2.eval(code, 0)); - assertEquals("9", Eval2.eval(code, 1)); - } @Test public void testConstruct0() { @@ -81,18 +56,6 @@ return z.x; } @Test - public void testConstruct1() { - CodeGen code = new CodeGen(""" -struct X { int !x; }; -X z = new X { x=3; }; -return z.x; -"""); - code.parse().opto(); - assertEquals("return 3;", code.print()); - assertEquals("3", Eval2.eval(code, 0)); - } - - @Test public void testConstruct2() { CodeGen code = new CodeGen(""" struct X { int x=3; }; @@ -106,83 +69,11 @@ return z.x; @Test - public void testStructFinal0() { - CodeGen code = new CodeGen(""" -struct Point { int !x, !y; }; -Point p = new Point { x=3; y=4; }; -return p; -"""); - code.parse().opto(); - assertEquals("return Point;", code.print()); - assertEquals("Point{x=3,y=4}", Eval2.eval(code, 0)); - } - - @Test - public void testStructFinal1() { - CodeGen code = new CodeGen(""" -struct Point { int x=3, y=4; }; -val p = new Point { x=5; y=6; }; -p.x++; -return p; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } - } - - @Test - public void testStructFinal2() { - CodeGen code = new CodeGen(""" -struct Point { int x=3, y=4; }; -val p = new Point; -p.x++; -return p; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } - } - - @Test - public void testStructFinal3() { - for( String fields : new String[] { "var x; var y;", "int[] x;", "int[] !x;" } ) { - String src = "struct Point { "+fields+" }; Point p = new Point; p.x++; return p;"; - try { new CodeGen(src).parse().opto(); fail(fields); } - catch( Exception e ) { assertEquals("'Point' is not fully initialized, field 'x' needs to be set in a constructor",e.getMessage()); } - } - } - - @Test - public void testStructFinal4() { - CodeGen code = new CodeGen(""" -struct Point { val x=3; val y=4; }; -Point p = new Point; -p.x++; -return p; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } - } - - @Test - public void testStructFinal5() { - CodeGen code = new CodeGen(""" -struct Point { var x=3; var y=4; }; -Point !p = new Point; -p.x++; -return p; -"""); - code.parse().opto(); - assertEquals("return Point;", code.print()); - assertEquals("Point{x=4,y=4}", Eval2.eval(code, 0)); - } - - // Same as the Chapter13 test with the same name, but using the new - // constructor syntax - @Test public void testLinkedList1() { CodeGen code = new CodeGen( """ -struct LLI { LLI? next; int i; }; -LLI? !head = null; +struct LLI { !LLI? !next; int i; }; +!LLI? !head = null; while( arg ) { head = new LLI { next=head; i=arg; }; arg = arg-1; @@ -203,8 +94,8 @@ return next.i; public void testLinkedList2() { CodeGen code = new CodeGen( """ -struct LLI { LLI? next; int i; }; -LLI? !head = null; +struct LLI { !LLI? !next; int i; }; +!LLI? !head = null; while( arg ) { head = new LLI { next=head; @@ -256,13 +147,13 @@ return new Square; static final String CONSTRUCTOR_MEMORY = """ struct S { int x; int y; }; struct T { int z=arg+40; }; - T !t = new T; - S !a = new S { x=11; y=7; }; - S !b = new S { x=22; y=9; }; - S !p=a; + !T !t = new T; + !S !a = new S { x=11; y=7; }; + !S !b = new S { x=22; y=9; }; + !S !p=a; if (arg) p=b; int before=p.x; - S !c = new S { + !S !c = new S { x=p.x+1; { int i=0; while (i<2) { p.y=p.y+1; i=i+1; } } y=p.y; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter17aTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17aTest.java new file mode 100644 index 00000000..8597b799 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17aTest.java @@ -0,0 +1,106 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter17aTest { + + @Test + public void testFinal1() { + CodeGen code = new CodeGen( +""" +int x=2, y=3; +if( arg ) { int x = y; x = x*x; y=x; } // Shadow final x +return y; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,9,3);", code.print()); + assertEquals("3", Eval2.eval(code, 0)); + assertEquals("9", Eval2.eval(code, 1)); + } + + @Test + public void testConstruct1() { + CodeGen code = new CodeGen(""" +struct X { int ~x; }; +X z = new X { x=3; }; +return z.x; +"""); + code.parse().opto(); + assertEquals("return 3;", code.print()); + assertEquals("3", Eval2.eval(code, 0)); + } + + @Test + public void testStructFinal0() { + CodeGen code = new CodeGen(""" +struct Point { int ~x, ~y; }; +Point p = new Point { x=3; y=4; }; +return p; +"""); + code.parse().opto(); + assertEquals("return (const)Point;", code.print()); + assertEquals("Point{x=3,y=4}", Eval2.eval(code, 0)); + } + + @Test + public void testStructFinal1() { + CodeGen code = new CodeGen(""" +struct Point { int x=3, y=4; }; +~Point p = new Point { x=5; y=6; }; +p.x++; +return p; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal2() { + CodeGen code = new CodeGen(""" +struct Point { int x=3, y=4; }; +~Point p = new Point; +p.x++; +return p; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal3() { + for( String fields : new String[] { "var x; var y;", "int[] !x;", "int[] !x;" } ) { + String src = "struct Point { "+fields+" }; Point p = new Point; p.x++; return p;"; + try { new CodeGen(src).parse().opto(); fail(fields); } + catch( Exception e ) { assertEquals("'Point' is not fully initialized, field 'x' needs to be set in a constructor",e.getMessage()); } + } + } + + @Test + public void testStructFinal4() { + CodeGen code = new CodeGen(""" +struct Point { val x=3; val y=4; }; +Point p = new Point; +p.x++; +return p; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal5() { + CodeGen code = new CodeGen(""" +struct Point { var x=3; var y=4; }; +!Point !p = new Point; +p.x++; +return p; +"""); + code.parse().opto(); + assertEquals("return Point;", code.print()); + assertEquals("Point{x=4,y=4}", Eval2.eval(code, 0)); + } + +} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 37208308..813fc4c2 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -5,7 +5,7 @@ import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; -public class Chapter17Test { +public class Chapter17bTest { @Test public void testJig() { @@ -80,7 +80,7 @@ return xs[0]; public void testInc5() { CodeGen code = new CodeGen(""" struct S { u16 x; }; -S !s = new S; +!S !s = new S; s.x--; return s.x; """); @@ -156,33 +156,33 @@ return s.x; } @Test public void testVar4() { - CodeGen code = new CodeGen("struct S{int x;}; S? s; s=new S; s.x++; return s.x; // Ok, no initializer so x is mutable "); + CodeGen code = new CodeGen("struct S{int x;}; !S? !s; s=new S; s.x++; return s.x; // Ok, no initializer so x is mutable "); code.parse().opto(); assertEquals("return 1;", code.print()); assertEquals("1", Eval2.eval(code, 0)); } @Test public void testVar5() { - CodeGen code = new CodeGen("struct S{int x;}; S? s; s=new S{x=3;}; s.x++; return s.x; // Ok, no initializer so x is mutable "); + CodeGen code = new CodeGen("struct S{int x;}; !S? !s; s=new S{x=3;}; s.x++; return s.x; // Ok, no initializer so x is mutable "); code.parse().opto(); assertEquals("return 4;", code.print()); assertEquals("4", Eval2.eval(code, 0)); } @Test public void testVar6() { - CodeGen code = new CodeGen("struct S{int x;}; val s = new S; s.x++; return s.x; // Error initializer so x is immutable "); + CodeGen code = new CodeGen("struct S{int x;}; ~S s = new S; s.x++; return s.x; // Error initializer so x is immutable "); try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @Test public void testVar7() { - CodeGen code = new CodeGen("struct S{int x;}; val s = new S{x=3;}; s.x++; return s.x; // Error initializer so x is immutable "); + CodeGen code = new CodeGen("struct S{int x;}; ~S s = new S{x=3;}; s.x++; return s.x; // Error initializer so x is immutable "); try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @Test public void testVar8() { - CodeGen code = new CodeGen("struct S{int x;}; S !s=new S; s.x++; return s.x; // Ok, has '!' so s.x is mutable "); + CodeGen code = new CodeGen("struct S{int x;}; !S !s=new S; s.x++; return s.x; // Ok, has '!' so s.x is mutable "); code.parse().opto(); assertEquals("return 1;", code.print()); assertEquals("1", Eval2.eval(code, 0)); @@ -196,7 +196,7 @@ return s.x; } @Test public void testVar10() { - CodeGen code = new CodeGen("struct S{int x;}; val s=new S; s.x++; return s.x; // Error, has val so x is immutable "); + CodeGen code = new CodeGen("struct S{int x;}; ~S s=new S; s.x++; return s.x; // Error, has val so x is immutable "); try { code.parse().opto().typeCheck(); fail(); } catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } } @@ -204,15 +204,15 @@ return s.x; @Test public void testVar11() { CodeGen code = new CodeGen(""" struct Bar { int x; }; -Bar !bar = new Bar; +!Bar !bar = new Bar; bar.x = 3; // Ok, bar is mutable -struct Foo { Bar? !bar; int y; }; -Foo !foo = new Foo { bar = bar; }; +struct Foo { !Bar? !bar; int y; }; +!Foo !foo = new Foo { bar = bar; }; foo.bar = bar; // Ok foo is mutable foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable -val xfoo = foo; // Throw away mutability +~Foo xfoo = foo; // Throw away mutability xfoo.bar.x++; // Error, cannot mutate through xfoo return xfoo.bar.x; """); @@ -223,15 +223,15 @@ return xfoo.bar.x; @Test public void testVar12() { CodeGen code = new CodeGen(""" struct Bar { int x; }; -Bar !bar = new Bar; +!Bar !bar = new Bar; bar.x = 3; // Ok, bar is mutable -struct Foo { Bar? !bar; int y; }; -Foo !foo = new Foo; +struct Foo { !Bar? !bar; int y; }; +!Foo !foo = new Foo; foo.bar = bar; // Ok bar is mutable foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable -val xfoo = foo; // Throw away mutability +~Foo xfoo = foo; // Throw away mutability int x4 = xfoo.bar.x; // Ok to read through xfoo, gets 4 foo.bar.x++; // Bumps to 5 int x5 = xfoo.bar.x; // Ok to read through xfoo, gets 5 @@ -256,7 +256,7 @@ int i,i++; public void testVar14() { CodeGen code = new CodeGen(""" struct B {}; -struct A { B b; }; +struct A { !B !b; }; A x = new A { return b; // read before init b = new B; @@ -270,7 +270,7 @@ A x = new A { public void testVar15() { CodeGen code = new CodeGen(""" struct B {}; -struct A { B b; }; +struct A { !B !b; }; return new A { if (arg) b = new B; // Constructor ends with partial init of b }.b; @@ -285,7 +285,7 @@ return new A { """ struct S{}; val x = 1; -val s = new S{x = 2;}; +~S s = new S{x = 2;}; return x; """ ); @@ -300,10 +300,10 @@ return x; struct Person { bool focused; }; -val focus = { Person p -> +val focus = { !Person p -> p.focused = true; }; -Person me; // Person !me = new Person; +!Person !me; // !Person !me = new Person; focus(me); return me; """ @@ -364,7 +364,7 @@ return b ? b.x++ + b.x++ : -1; public void testTrinary4() { // This test case will benefit from an unzipping transformation CodeGen code = new CodeGen(""" -struct Bar { Bar? next; int x; }; +struct Bar { !Bar? !next; int x; }; var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" """); @@ -479,8 +479,8 @@ for(;;arg++;) {} public void testForward0() { CodeGen code = new CodeGen(""" struct A{ - B? f1; - B? f2; + !B? !f1; + !B? !f2; }; return new A; """); @@ -493,13 +493,13 @@ return new A; public void testForward1() { CodeGen code = new CodeGen(""" struct A { - B?[]? nil_array_of_b; - B?[] array_of_b; + !B?[]? !nil_array_of_b; + !B?[] !array_of_b; }; -return new A{array_of_b = new B?[0]; }.array_of_b; +return new A{array_of_b = new !B?[0]; }.array_of_b; """); code.parse().opto(); - assertEquals("return (const)[]*B?;", code.print()); + assertEquals("return []*B?;", code.print()); assertEquals("*B {... }?[]", Eval2.eval(code,0)); } @@ -507,8 +507,8 @@ return new A{array_of_b = new B?[0]; }.array_of_b; @Test public void testLinkedList2() { CodeGen code = new CodeGen(""" -struct LLI { LLI? next; int i; }; -LLI? !head = null; +struct LLI { !LLI? !next; int i; }; +!LLI? !head = null; while( arg-- ) head = new LLI { next=head; i=arg; }; int sum=0; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 91a0b700..e3dd222d 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -272,7 +272,7 @@ return 2; public void testFcn8() { CodeGen code = new CodeGen( """ -{int -> int}? i2i = null; +{int -> int}? !i2i = null; var id = {{int->int} f-> return f;}; for(;;) { if (i2i) return i2i(arg); @@ -290,7 +290,7 @@ for(;;) { public void testFcn9() { CodeGen code = new CodeGen( """ -{int -> int}? i2i = null; +{int -> int}? !i2i = null; for(;;) { if (i2i) return i2i(arg); var x = {int i-> return i;}; @@ -311,13 +311,13 @@ struct Person { int age; }; -val fcn = { Person?[] ps, int x -> +val fcn = { !Person?[] !ps, int x -> val tmp = ps[x]; if( ps[x] ) ps[x].age++; }; -var ps = new Person?[2]; +var ps = new !Person?[2]; ps[0] = new Person; ps[1] = new Person; return fcn(ps,1); @@ -382,7 +382,7 @@ struct S { {int} f = { -> x(); return 0; }; // Do not let fref x be a field }; val x = { -> return 1; }; -S? s = null; +!S? !s = null; for(;;) { if (s) return s.x; } @@ -431,7 +431,7 @@ struct S { { int } f = { -> return x(); }; }; val x = { -> return 1; }; -S? s = null; +!S? !s = null; for(;;) { if (s) return s.f; } @@ -465,7 +465,7 @@ return f2f(o)(1); struct Person { int coffee_count; }; -Person !p = new Person; +!Person !p = new Person; p.coffee_count += 1; return p.coffee_count; """); @@ -476,10 +476,10 @@ return p.coffee_count; static final String CALL_MEMORY = """ struct S { int x; int y; }; - val bump = { S s, int d -> int old=s.x; s.x=old+d; return old; }; - S !a = new S { x=10; y=7; }; - S !b = new S { x=20; y=9; }; - S !p=a; if (arg) p=b; + val bump = { !S !s, int d -> int old=s.x; s.x=old+d; return old; }; + !S !a = new S { x=10; y=7; }; + !S !b = new S { x=20; y=9; }; + !S !p=a; if (arg) p=b; int before=p.x; int old=bump(p,3); int after=p.x; @@ -505,13 +505,13 @@ return p.coffee_count; static final String RECURSIVE_MEMORY = """ struct S { int x; }; - val rec = { S s, int n -> + val rec = { !S !s, int n -> if (n==0) return s.x; int before=s.x; s.x=before+1; return before+rec(s,n-1); }; - S !s=new S { x=10; }; + !S !s=new S { x=10; }; int value=rec(s,arg); return value*100+s.x; """; @@ -524,12 +524,12 @@ return p.coffee_count; static final String INLINE_MEMORY = """ struct S { int x; int y; }; - val make = { S s -> + val make = { !S s -> S t = new S { x=s.x+1; y=3; }; s.y=9; return t; }; - S !a = new S { x=arg+40; y=7; }; + !S !a = new S { x=arg+40; y=7; }; S t=make(a); return a.x*10000+a.y*100+t.x+t.y; """; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 7ac16a93..c388726c 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -225,7 +225,7 @@ return sum;"""); public void testAlloc1() { CodeGen code = new CodeGen( """ -struct S { int a; S? c; }; +struct S { int a; !S? !c; }; return new S;"""); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return S;", code.print()); @@ -399,8 +399,8 @@ return sq(arg) + sq(3); @Test public void testFoldedReadBeforeWrites() { var code = new CodeGen(""" struct S { int x; }; - S !a = new S { x=11; }; S !b = new S { x=22; }; - S !p = a; if( arg ) p = b; + !S !a = new S { x=11; }; !S !b = new S { x=22; }; + !S !p = a; if( arg ) p = b; int before = p.x + arg; a.x=33; b.x=44; return before; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 8dce8629..36f2f7b0 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -18,7 +18,7 @@ public class Chapter20Test { // A real integer return merged with a synthetic exit. "if(arg) while(1) {} return arg+1;", // TOP must not widen a non-null pointer or constrain a float register. - "struct S { int x; }; S !s=new S; if(arg) while(1) {} return s;", + "struct S { int x; }; !S !s=new S; if(arg) while(1) {} return s;", "if(arg) while(1) {} return 1.5;", // Several synthetic exits into the same return. "if(arg==1) while(1) {} if(arg==2) while(1) {} return arg+3;", @@ -26,7 +26,7 @@ public class Chapter20Test { "while(1) { arg+=1; }", "if(arg) while(1) {} while(1) {}", // Loop-carried memory and scalar self-conflicts exercise spilling. - "struct S { int x; int y; }; S !a=new S; if(arg) while(1) { a.x+=arg; a.y+=a.x; } return a.x+a.y;" + "struct S { int x; int y; }; !S !a=new S; if(arg) while(1) { a.x+=arg; a.y+=a.x; } return a.x+a.y;" }; for( String target : new String[]{"x86_64_v2","riscv","arm"} ) for( String src : sources ) { @@ -47,7 +47,7 @@ public class Chapter20Test { @Test public void testNarrowStoreMasks() { for( String type : new String[]{"i8","u8","i16","u16"} ) { - CodeGen code = new CodeGen("struct S { "+type+" x; }; S !s=new S; s.x=arg; return 0;") + CodeGen code = new CodeGen("struct S { "+type+" x; }; !S !s=new S; s.x=arg; return 0;") .driver(CodeGen.Phase.RegAlloc,"x86_64_v2","SystemV"); int stores=0; for( var bb : code._cfg ) @@ -63,9 +63,9 @@ public class Chapter20Test { @Test public void testInlinedReturnValue() { String src = """ struct S { int x; }; -val f = { S s -> s.x = g(); }; +val f = { !S s -> s.x = g(); }; val g = { -> 123; }; -S !s = new S; +!S !s = new S; return f(s); """; // The entry of g can disappear before its Return is folded into f. @@ -203,11 +203,11 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 public void testString() { String src = """ struct String { - u8[] cs; + u8[] !cs; int _hashCode; }; -val equals = { String self, String s -> +val equals = { !String !self, !String s -> if( self == s ) return true; if( self.cs# != s.cs# ) return false; for( int i=0; i< self.cs#; i++ ) @@ -216,13 +216,13 @@ val equals = { String self, String s -> return true; }; -val hashCode = { String self -> +val hashCode = { !String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { String self -> +val _hashCodeString = { !String self -> int hash=0; if( self.cs ) { for( int i=0; i< self.cs#; i++ ) @@ -232,7 +232,7 @@ val _hashCodeString = { String self -> return hash; }; -String !s = new String { cs = new u8[17]; }; +!String !s = new String { cs = new u8[17]; }; s.cs[0] = 67; // C s.cs[1] = 108; // l hashCode(s); @@ -351,12 +351,12 @@ return output; """ // based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort -val merge_sort = { int[] a, int[] b, int n -> +val merge_sort = { int[] !a, int[] !b, int n -> copy_array(a, 0, n, b); split_merge(a, 0, n, b); }; -val split_merge = { int[] b, int begin, int end, int[] a -> +val split_merge = { int[] !b, int begin, int end, int[] a -> if (end - begin <= 1) return 0; int middle = (end + begin) / 2; @@ -366,7 +366,7 @@ val split_merge = { int[] b, int begin, int end, int[] a -> return 0; }; -val merge = { int[] b, int begin, int middle, int end, int[] a -> +val merge = { int[] !b, int begin, int middle, int end, int[] a -> int i = begin, j = middle; for (int k = begin; k < end; k++) { @@ -381,7 +381,7 @@ val merge = { int[] b, int begin, int middle, int end, int[] a -> } }; -val copy_array = { int[] a, int begin, int end, int[] b -> +val copy_array = { int[] !a, int begin, int end, int[] b -> for (int k = begin; k < end; k++) b[k] = a[k]; }; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 7e82e37c..ebfcb146 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -20,8 +20,8 @@ public class Chapter21Test { @Test public void testReadBeforeConditionalStore() { var code = new CodeGen(""" - struct S { int x; }; S !a=new S; S !b=new S; - a.x=10; b.x=20; S !p=a; if(arg&1) p=b; + struct S { int x; }; !S !a=new S; !S !b=new S; + a.x=10; b.x=20; !S !p=a; if(arg&1) p=b; int sum=0; for(int i=0; i<6; i++) { sum+=a.x; @@ -222,7 +222,7 @@ public class Chapter21Test { @Test public void testNarrowStores() throws IOException { for( String type : new String[]{"i8","u8","i16","u16"} ) { - String src = "struct S { "+type+" x; }; S !s = new S; s.x = arg; return 0;"; + String src = "struct S { "+type+" x; }; !S !s = new S; s.x = arg; return 0;"; CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); int stores=0; for( var bb : code._cfg ) @@ -335,7 +335,7 @@ public class Chapter21Test { } @Test public void testInfinite() { - String src = "struct S { int i; }; S !s = new S; while(1) s.i++;"; + String src = "struct S { int i; }; !S !s = new S; while(1) s.i++;"; testCPU(src,"x86_64_v2", "SystemV",0,"return Top;"); testCPU(src,"riscv" , "SystemV",2,"return Top;"); testCPU(src,"arm" , "SystemV",2,"return Top;"); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 46457b40..f81a1300 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -180,7 +180,7 @@ public class Chapter22Test { } @Test public void testInfiniteReturn() { - String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + String src = "struct S { int i; }; !S !s = new S; while(1) s.i++; return s.i;"; testCPU(src,"x86_64_v2","SystemV",0,"return Top;"); testCPU(src,"riscv","SystemV",2,"return Top;"); testCPU(src,"arm","SystemV",2,"return Top;"); @@ -214,7 +214,7 @@ public class Chapter22Test { @Test public void testSextFail() throws IOException { String src = """ struct Person { i32 age;}; -Person !p = new Person; +!Person !p = new Person; p.age = (arg<<17)>>17; return 0; """; @@ -238,7 +238,7 @@ return 0; String src = """ struct Person { i32 age;}; - Person !p = new Person; + !Person !p = new Person; p.age = (arg<<48)>>48; return 0; """; @@ -262,7 +262,7 @@ return 0; String src = """ // Should fold away sign extend struct Person { i8 age;}; -Person !p = new Person; +!Person !p = new Person; p.age = (arg<<48)>>48; return 0; """; @@ -332,12 +332,12 @@ return 0; @Test public void testCoRecur() { String src = """ -struct A { B? b; C? c; i64 ax; val az = x*2; }; -struct B { A? a; C? c; f32 bx; val bz = x*3; }; -struct C { A? a; B? b; f64 cx; val cz = x*x; }; -A !aa = new A{ ax=17; }; -B !bb = new B{ bx=3.14; a = aa; }; -C !cc = new C{ cx=2.73; a = aa; b = bb; }; +struct A { !B? !b; !C? !c; i64 ax; val az = x*2; }; +struct B { !A? !a; !C? !c; f32 bx; val bz = x*3; }; +struct C { !A? !a; !B? !b; f64 cx; val cz = x*x; }; +!A !aa = new A{ ax=17; }; +!B !bb = new B{ bx=3.14; a = aa; }; +!C !cc = new C{ cx=2.73; a = aa; b = bb; }; aa.b = bb; aa.c = cc; bb.c = cc; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 10d27ac8..7ed65745 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -57,7 +57,7 @@ public class Chapter23Test { public void testOrRhsLoopMemory() throws IOException { checkOrRhsLoop(""" struct S { int f; }; - S !s = new S; + !S !s = new S; int result = (arg & 1) || (new S { while (s.f < 3) s.f++; s.f++; @@ -149,7 +149,7 @@ var apply = { i64 x, { i64 -> u32 } fcn -> public void testAndPtr() throws IOException { String src = """ -struct S { S? fld; }; +struct S { !S? !fld; }; val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; return ptr && ptr.fld ? "true" : "false"; """; @@ -238,21 +238,21 @@ return ptr && ptr.fld ? "true" : "false"; // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace - val skip = { Scan s -> + val skip = { !Scan s -> while( s.buf[s.x] <= ' ' ) s.x++; }; // Peek a character; if matched consume it, else false. - val peek = { Scan s, u8 c -> + val peek = { !Scan !s, u8 c -> skip(s); if( s.buf[s.x] != c ) return false; s.x++; return true; }; }; -Scan !s = new Scan{ buf = " q"; }; +!Scan !s = new Scan{ buf = " q"; }; return Scan.peek(s,'q'); """; @@ -269,7 +269,7 @@ return Scan.peek(s,'q'); // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -277,12 +277,12 @@ struct Scan { return self; }; }; -val s = new Scan{ buf = " q"; }; +~Scan s = new Scan{ buf = " q"; }; return s.skip().x; """; try { new CodeGen(src).parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Argument #0 isa *Scan {i64 x; *[]u8 buf; { *Scan -> *Scan {i64 !x; *[]u8 buf; {21} skip; } #21} skip; }, but must be a *Scan {i64 !x; *[]u8 buf; ... }",e.getMessage()); } + catch( Exception e ) { org.junit.Assert.assertTrue(e.getMessage().startsWith("Argument #0 isa")); } }; @@ -293,7 +293,7 @@ return s.skip().x; // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -304,7 +304,7 @@ struct Scan { buf[x++]==ch; }; }; -Scan !s = new Scan{ buf = " [1,2]"; }; +!Scan !s = new Scan{ buf = " [1,2]"; }; return s.require('['); """; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java b/chapter23/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java index 0d67d3c5..48f739cf 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java @@ -73,7 +73,7 @@ public class CompoundAssignmentTest { @Test public void testFields() { for (String op : OPS) { long expected = apply(op, -8, 3); - check("struct S { int x; }; S !s=new S; s.x=arg; int r=(s.x " + + check("struct S { int x; }; !S !s=new S; s.x=arg; int r=(s.x " + op + " 3); return s.x*10+r;", -8, expected*11); } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index 611d8184..6388228e 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -32,8 +32,8 @@ public class MemoryEncodingTest { """, // One possibly aliasing arm must reject the unchanged-memory proof. """ - struct S { int x; }; S !a=new S; S !b=new S; - a.x=10; b.x=20; S !p=a; if(arg&1) p=b; + struct S { int x; }; !S !a=new S; !S !b=new S; + a.x=10; b.x=20; !S !p=a; if(arg&1) p=b; int sum=0; for(int i=0; i<6; i++) { if(i==2) p.x=30; @@ -44,8 +44,8 @@ public class MemoryEncodingTest { """, // Unchanged memory does not imply an unchanged loop-carried pointer. """ - struct S { int x; }; S !a=new S; S !b=new S; - a.x=10; b.x=20; S !p=a; int sum=0; + struct S { int x; }; !S !a=new S; !S !b=new S; + a.x=10; b.x=20; !S !p=a; int sum=0; for(int i=0; i<6; i++) { if(i==2) a.x=30; sum+=p.x; @@ -55,7 +55,7 @@ public class MemoryEncodingTest { """, // All arms fold, but their values differ: build a value Phi. """ - struct S { int x; }; S !a=new S; a.x=1; int sum=0; + struct S { int x; }; !S !a=new S; a.x=1; int sum=0; for(int i=0; i<6; i++) { sum+=a.x; if(i&1) a.x=2; @@ -146,7 +146,7 @@ public class MemoryEncodingTest { for( String target : new String[]{"x86_64_v2","riscv","arm"} ) { CodeGen code = new CodeGen(""" struct S { int x; int y; }; - S !a=new S; + !S !a=new S; if( arg ) while( 1 ) { a.x+=arg; a.y+=a.x; } return a.x+a.y; """).driver(CodeGen.Phase.LoopTree); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/MutabilityTest.java b/chapter23/src/test/java/com/seaofnodes/simple/MutabilityTest.java new file mode 100644 index 00000000..7ae80314 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/MutabilityTest.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple; + +import org.junit.Test; +import static org.junit.Assert.*; +import com.seaofnodes.simple.codegen.CodeGen; + +public class MutabilityTest { + private static void ok(String src, String result) { + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(result,Eval2.eval(code,0)); + } + private static void bad(String src) { + try { + new CodeGen(src).parse().opto().typeCheck(); + } catch( RuntimeException expected ) { + String msg = expected.getMessage(); + assertTrue("Expected a permission error, got: "+expected, + msg!=null && (msg.contains("final") || msg.contains("not of declared type") || msg.contains("Cannot store") || msg.contains("Argument #"))); + return; + } + fail("Accepted forbidden write: "+src); + } + + @Test public void testIndependentBindingsAndViews() { + ok("struct P { int x; }; !P ~p=new P; p.x=7; return p.x;", "7"); + ok("struct P { int x; }; ~P !p=new P{x=3;}; p=new P{x=7;}; return p.x;", "7"); + bad("struct P { int x; }; !P ~p=new P; p=new P; return 0;"); + bad("struct P { int x; }; ~P !p=new P; p.x=7; return 0;"); + bad("int ~x=3; x=7; return x;"); + ok("int !x=3; x=7; return x;", "7"); + } + + @Test public void testDeepViewAndAliases() { + ok("struct P { int x; }; !P ~p=new P; ~P ~r=p; p.x=7; return r.x;", "7"); + bad("struct P { int x; }; struct Box { !P p; }; !P q=new P; Box b=new Box{p=q;}; b.p.x=7; return 0;"); + bad("struct P { int x; }; P p=new P; !P q=p; q.x=7; return 0;"); + bad("struct P { P? next; int x; }; !P p=new P{next=new P;}; p.next.x=7; return 0;"); + bad("struct P { !P? next; int x; }; P p=new P{next=new P;}; p.next.x=7; return 0;"); + } + + @Test public void testInferencePreservesAccess() { + ok("struct P { int x; }; val p=new P; p.x=7; return p.x;", "7"); + bad("struct P { int x; }; val p=new P; p=new P; return 0;"); + bad("struct P { int x; }; P p=new P; var q=p; q.x=7; return 0;"); + } + + @Test public void testParameterPermissions() { + ok("struct P { int x; }; val f={ !P p -> p.x=7; return p.x; }; return f(new P);", "7"); + ok("val f={ int ~x -> return x; }; return f(7);", "7"); + bad("val f={ int ~x -> x=7; return x; }; return f(3);"); + bad("struct P { int x; }; val f={ P p -> p.x=7; return p.x; }; return f(new P);"); + bad("struct P { int x; }; val f={ !P p -> p.x=7; return p.x; }; P p=new P; return f(p);"); + bad("struct P { int x; }; val f={ P?[] a -> return a#; }; !P?[] a=new !P?[1]; return f(a);"); + } + + @Test public void testConstructorScope() { + ok("struct P { int ~x; }; P p=new P{if(arg) x=3; else x=7;}; return p.x;", "7"); + bad("int ~outer=1; struct P { int x; }; P p=new P{outer=7;}; return outer;"); + bad("struct P { int x; }; P p=new P{int ~local=1; local=7;}; return p.x;"); + } + + @Test public void testArrayLayers() { + bad("struct P { int x; }; !P?[] rw=new !P?[1]; P?[] ro=rw; rw[0]=new P; ro[0].x=7; return 0;"); + ok("u8[] a=new u8[2]; a[0]=7; return a[0];", "7"); + ok("struct P { int x; }; P?[] a=new P?[1]; a[0]=new P{x=7;}; return a[0].x;", "7"); + bad("struct P { int x; }; P?[] a=new P?[1]; a[0]=new P; a[0].x=7; return 0;"); + ok("struct P { int x; }; !P?[] a=new !P?[1]; a[0]=new P; a[0].x=7; return a[0].x;", "7"); + bad("u8[~] a=new u8[1]; a[0]=7; return 0;"); + ok("u8[~]?[] rows=new u8[~]?[1]; rows[0]=new u8[1]; return rows#;", "1"); + bad("u8[~]?[] rows=new u8[~]?[1]; rows[0]=new u8[1]; rows[0][0]=7; return 0;"); + bad("u8[]?[~] rows=new u8[]?[1]; rows[0]=new u8[1]; return 0;"); + } +} diff --git a/chapter23/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter23/src/test/java/com/seaofnodes/simple/SchedulerTest.java index ca29bf84..3b19857a 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -25,7 +25,7 @@ public class SchedulerTest { struct S { int f; } -S !v=new S; +!S !v=new S; v.f = 2; int i=v.f; if (arg) v.f=1; @@ -42,7 +42,7 @@ return i; struct S { int f; }; -S !v0=new S; +!S !v0=new S; if(arg) v0.f=1; return v0; """); @@ -58,7 +58,7 @@ return v0; struct S { int f; }; -S !v=new S; +!S !v=new S; v.f = 2; int i=new S.f; i=v.f; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter23/src/test/java/com/seaofnodes/simple/TypeTest.java index 40264d1d..b21af9ee 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -80,13 +80,13 @@ public class TypeTest { Assert.assertNotEquals(ptr1, ptr2); Type p1glb = ptr1.glb(false); Assert.assertNotEquals(ptr1, p1glb ); - Type p1nro = ptr1nil.makeRO(); - Assert.assertEquals(p1nro, p1glb); + Assert.assertTrue(((TypeMemPtr)p1glb)._ro); + Assert.assertTrue(ptr1nil.isa(p1glb)); Assert.assertEquals(ptr1, ptr1.dual().dual()); Assert.assertTrue(p1glb.makeRO().isa( ptr1.dual().glb(false))); - Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT), ptr1.meet(ptr2nil)); - Assert.assertEquals(p1glb, ptr1.meet(TypeNil.NIL).makeRO()); + Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT).withAccess(false), ptr1.meet(ptr2nil)); + Assert.assertEquals(ptr1nil, ptr1.meet(TypeNil.NIL)); TypeMemPtr TOP = TypeMemPtr.TOP; TypeMemPtr BOT = TypeMemPtr.makeNullable(TypeStruct.BOT); @@ -95,7 +95,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, ptr1_meet_ptr2); + Assert.assertEquals(PTR.withAccess(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); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter23/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 7d9e6483..6ec066e9 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -452,7 +452,7 @@ public class ScriptGenerator { for (int i=0; i<fields.length; i++) { var fieldName = getRandomName(); var type = getType(true); - printIndentation().append(type.name).append(" ").append(fieldName).append(";\n"); + printIndentation().append(declType(type)).append(" !").append(fieldName).append(";\n"); fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct); } indentation -= INDENTATION; @@ -649,15 +649,17 @@ public class ScriptGenerator { return 0; } - /** - * Generate a declaration statement. - * @return 0 - */ + // This generator mutates references and fields; request both permissions. + private static String declType(Type type) { + return (type instanceof TypeStruct || type instanceof TypeNullable ? "!" : "") + type.name; + } + + /** Generate a declaration statement. */ public int genDecl() { var type = getType(); var name = getVarName(); // Always make them mutable - sb.append(generateInvalid() ? getRandomName() : type.name).append(" !").append(name); + sb.append(generateInvalid() ? getRandomName() : declType(type)).append(" !").append(name); if (!(type instanceof TypeNullable) || random.nextBoolean()) { sb.append("="); genExpression(type, true, type==TYPE_BOOL); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp index b18dfd16..52bfe29b 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp @@ -1,7 +1,7 @@ // -*- mode: java; -*- struct S { int f; }; var v0 = new S; -S? v1; +!S? !v1; if (arg) v1 = new S; if (v1) { v0.f = v1.f; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/large.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/large.smp index 7f151f60..73271e66 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/large.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/large.smp @@ -9,7 +9,7 @@ struct stbi__context { u32 img_x, img_y; int img_n, img_out_n; - stbi_io_callbacks io; + !stbi_io_callbacks !io; u8[]io_user_data; int read_from_callbacks; @@ -25,7 +25,7 @@ struct stbi__context { { stbi__context -> u8 } stbi__get8 = "C"; -val sample = { stbi__context s, int pal_len -> +val sample = { !stbi__context !s, int pal_len -> var palette = new u8[1024]; for (int i=0; i < pal_len; ++i) { palette[i*4+3] = 0; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/person.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/person.smp index 507fb83b..94e2cdde 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/person.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/person.smp @@ -3,7 +3,7 @@ struct Person { i32 age; }; -val fcn = { Person?[] ps, int x -> +val fcn = { !Person?[] ps, int x -> if( ps[x] ) ps[x].age++; };
\ No newline at end of file diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp index 9f0f5bea..b5e6ee90 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/person21.smp @@ -3,7 +3,7 @@ struct Person { int age; }; -val fcn = { Person?[] ps, int x -> +val fcn = { !Person?[] ps, int x -> if( ps[x] ) ps[x].age++; };
\ No newline at end of file diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/ptrand.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/ptrand.smp index 9d7bce88..8b8af571 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/ptrand.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/ptrand.smp @@ -1,4 +1,4 @@ -struct S { S? fld; }; +struct S { !S? !fld; }; val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; if( ptr && ptr.fld ) { diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/riscv_load.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/riscv_load.smp index 67369feb..1a36fb99 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/riscv_load.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/riscv_load.smp @@ -1,4 +1,4 @@ struct Person { i32 age;}; -Person !p = new Person; +!Person !p = new Person; p.age += arg; return p.age; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_1.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_1.smp index cfb3fbcc..57b37477 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_1.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_1.smp @@ -1,4 +1,4 @@ struct Person {i64 age;} -Person !p = new Person; +!Person !p = new Person; p.age += arg; return p.age; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_fold_away.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_fold_away.smp index 0cf70392..7d7fdce7 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_fold_away.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_fold_away.smp @@ -1,5 +1,5 @@ // Should fold away sign extend struct Person { i8 age;}; -Person !p = new Person; +!Person !p = new Person; p.age = (arg<<48)>>48; return 0;
\ No newline at end of file diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away.smp index 48cc6409..4d6ca3a3 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away.smp @@ -1,4 +1,4 @@ struct Person { i32 age;}; -Person !p = new Person; +!Person !p = new Person; p.age = (arg<<17)>>17; return 0;
\ No newline at end of file diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away_2.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away_2.smp index 3120429b..5c96c060 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away_2.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/sext_str_not_fold_away_2.smp @@ -1,4 +1,4 @@ struct Person { i32 age;}; -Person !p = new Person; +!Person !p = new Person; p.age = (arg<<48)>>48; return 0;
\ No newline at end of file diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash.smp index 3fa2174c..7344fcdd 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash.smp @@ -5,7 +5,7 @@ struct String { }; // Compare two Strings -val equals = { String self, String s -> +val equals = { !String !self, !String s -> if( self == s ) return true; if( self.cs# != s.cs# ) return false; for( int i=0; i< self.cs#; i++ ) @@ -15,13 +15,13 @@ val equals = { String self, String s -> }; // Return the String hashCode (cached, and never 0) -val hashCode = { String self -> +val hashCode = { !String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { String self -> +val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) hash = hash*31 + self.cs[i]; diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp index dafa7456..257f79f9 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/stringHash21.smp @@ -5,7 +5,7 @@ struct String { }; // Compare two Strings -val equals = { String self, String s -> +val equals = { !String !self, !String s -> if( self == s ) return true; if( self.cs# != s.cs# ) return false; for( int i=0; i< self.cs#; i++ ) @@ -15,13 +15,13 @@ val equals = { String self, String s -> }; // Return the String hashCode (cached, and never 0) -val hashCode = { String self -> +val hashCode = { !String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { String self -> +val _hashCodeString = { !String self -> int hash=0; if( self.cs ) for( int i=0; i< self.cs#; i++ ) |