diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-03 14:03:48 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-03 14:03:48 -0700 |
| commit | 22df891893d30e9906d0b14fc3ae5d8e67d500b2 (patch) | |
| tree | 2bda142f92febc8b26f1cabd4bb0c46d1864f34b /chapter23 | |
| parent | c3958e34c0de21df52e57e47e4f47ffe6464f138 (diff) | |
| download | Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.tar.gz Simple-22df891893d30e9906d0b14fc3ae5d8e67d500b2.zip | |
Chapter renumber, and split ch 17
Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14].
Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly.
THe new immutable syntax is pushed through all later chapters
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++ ) |
