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 /chapter18 | |
| 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 'chapter18')
29 files changed, 1526 insertions, 1105 deletions
diff --git a/chapter18/#README.md# b/chapter18/#README.md# new file mode 100644 index 00000000..6d570d21 --- /dev/null +++ b/chapter18/#README.md# @@ -0,0 +1,274 @@ +# Chapter 18: Functions + +[Previous: Chapter 17b](../chapter17b/README.md) | +[Next: Chapter 19](../chapter19/README.md) + + +# Table of Contents + +1. [FunctionTypes](#function-and-rpc-types) +2. [Return Program Counters](#return-program-counters) +3. [Functions](#functions) +4. [CodeGen - The Compile Driver](#codegen---the-compile-driver) +5. [Graph Visualizer](#graph-visualizer) +6. [Memory across functions](#memory-across-functions) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter18) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter17b...linear-chapter18) it to the previous chapter. + +I hardly know where to begin! So many things changed here, mostly as indirect +consequences of supporting functions. + +Highlights of the changes: + +- Function types, and a rework of the type lattice diagrams. +- Return Program Counter types, or Return PC or RPC for short. +- A distinguished `null` which can be used for functions, RPCs and struct pointers. +- Functions themselves can be parsed and evaluated; recursive functions are supported. +- Function calls work, call sites can link, and functions can be inlined. +- The top-level is now a call to function `main`, and this changed most tests. +- A top-level compile driver, which enforces optimization steps. +- A local scheduler. +- A new evaluator which relies on code motion, both global and local. +- A graphic animated viewer for peepholes. + +Functions are *not* closures in this chapter; that brings about far more +changes and subtle complexities than sensible for such a large chapter. + +Functions can only refer to out of scope variables if they are some final +constant. This generally includes e.g. recursive function pointers. + + +## Function and RPC Types + +``` +{ argtype, argtype, ... -> rettype } +``` + +A leading `{` character denotes the start of a function or function type, then +a list of argument types, and an arrow `->` and the return type. + +Function variables are normal variables and assigned the same way: + +`functiontype fcn = function-typed-expr;` + +and function typed variables can be inferred, so `val` and `var` on the left +hand side is fine: + +`val sq = { int x -> x*x; };` + +Internally, functions have a `TypeTuple` for the arguments, a return `Type`, +and a *function index* spelled as `fidx` in the code. Function indices are +small dense integers, one per unique function. They are mapped 1-to-1 to the +final code address of the generated function code. + +Function pointers can refer to more than one function with the same signature, +and the `TypeFunPtr` tracks this as a bit set with the same tuple for signature +and return. + +Function types can be `null` just like references. + +Functions cannot return `void` (there is no `void` in Simple), but they can +return `null` and have their return value ignored. A syntactic sugar for void +returns may be added in the future. + + +### Return Program Counters + +Just like functions have a unique "function index" mapped one to one with +function start addresses, call sites generate a unique "return program +counter", one per unique call site. These are required for the evaluator to return +from functions without itself relying on the implementing language's +(e.g. Java) stack. This is the type for such values and `TypeRPC` is very +similar to a `TypeFunPtr` except that the signature doesn't matter. + +In spirit, this is part of a `continuation` and would be required to do IR +analysis of a hypothetical `call/cc` operation. That is outside our current +scope, so for now these are only used in the evaluator. + + +## Functions + +Functions themselves use the same syntax as function types, but filled in: + +``` +{ flt x, flt y -> // Signature + sqrt(x*x+y*y); // Body +} +``` + +Used in a declaration statement: +``` +// TYPE VAR = EXPR +{flt,flt->flt} dist = { flt x, flt y -> + sqrt(x*x+y*y); // BODY +} +``` + +With `var`: +``` +var dist = { flt x, flt y -> sqrt(x*x+y*y); } +``` + +Functions are called in the usual way: +`dist( 1.2, 2.3 ) // yields 2.59422435` + +Functions can have zero arguments, in which case the `->` argument separator is +optional. This allows any section of code to be "thunked" by wrapping it in +`{}`. + +`just5 = { -> 5 } // With arrow` + +`just5 = { 5 } // Without arrow` + +Called: +`just5() // Returns 5` + +Functions are always anonymous. When finally assigned to a variable, they will +pick up the variable name for debugging and display purposes, but this has no +semantic meaning. Here is a function variable referring to more than one +anonymous function; the resulting function either doubles or squares: + +`val fcn = arg ? { int x -> x+x; } : { int x -> x*x; };` + +`fcn(3) // Prints either 6 or 9, depending on arg` + +Functions can be recursive: +``` +val fact = { int n -> + n <=1 ? n : n*fact(n-1); +}; +return fact(4); // Returns 4! or 24 +``` + +You can early return as normal out of functions: +``` +val find = { int[] es, int e -> + for( int i=0; i<es#; i++ ) + if( es[i] == e ) + return i; // Found matching element, return the index + return -1; // Return -1 for not-found +}; +return find; +``` + +`FunNodes` define functions, have a pointer to the one `ReturnNode` (which +itself has a back pointer to the `Fun`), extend a `RegionNode` and are followed +by `ParmNodes` which themselves extend `PhiNodes`. All `Calls` which reach a +`Fun` (*link*) merge all their arguments into the `Parms`; there is an extra `Parm` for +memory and for the return point back to the `CallEnd`: a RPC. So a `Fun` is +basically a fancy merge point, merging all calls that *link* here. + +Unlike prior chapters, all the `returns` from a single function are gathered +together into a single `ReturnNode` point, and they must all be of the same +general type. `Returns` take in a Control, a Memory, a return value, and the +`RPC` that was handed to the function when called. + +When looking at the returned IR, the `StopNode` now reports one return for each +function, including `main`: +`Stop[ return find; return Phi(Region,int,-1); ]` + + +### Calls + +Calls have the usual syntax: `fcn(3)`. Internally a `CallNode` takes in +Control, Memory, all the normal arguments, and a hidden last argument which is +the function pointer. For calls to named functions this last argument will be +a `ConstantNode` of the named function type, but in general it can be the +result of any function-typed expression. + +The call arguments passed to the matching `ParmNode`s in the function, +with the `Call`s constant `RPC` being passed to the matching RPC `Parm`. + +After a `Call` is a `CallEndNode`, internally abbreviated as `cend`. The +`CallEnd` will take the `Call` as an input, and also every *linked* function: +functions the call-site *knows* it will call. This will be expanded later to +be a conservative approximation to the *Call Graph*, with each `CallEnd` +*linked* to every function it *may* call; if a function is not linked it can +not be called from here. This requires a global analysis (fast, cheap, +incremental, and global), shows up in [Chapter24](../chapter19/README.md), +[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation). +So for the moment we only link exact constant functions. + +If a call site is linked to a single function, and that single function is only +called by this one call site (its function pointer is only used here, obvious +from GVN) then the function inlines in the IR. + +Like `Start`, `CallEnd`s are followed by projections for Control, Memory and the return value. + + + +## CodeGen - The Compile Driver + +There is now a top-level compile driver that enforces a phase ordering, and +allows multiple compilations; the Fuzzer uses this to compare various generated +programs. The phases (for now) are: + +- *Parse* - Convert program text to Simple IR +- *Opto* - General optimizations; for now iterate peepholes. +- *TypeCheck* - Error checking after all types have propagated. This mostly + reports on failed null checks. +- *Schedule* - Global Code Motion scheduler. After this phase, all nodes belong + in some basic block, with the normal suspect CFGNodes being basic blocks. +- *LocalSched* - a local scheduler. It's completely naive, except it enforces + some required rules: Phis appear at block heads, branches at block exits. + There's room in the algorithm for a much more sophisticated list scheduler. + The `Eval2` evaluator requires this information. +- *RegAlloc* - Not implemented (yet). + +Several globals moved from the Parser to CodeGen, and probably several others +ought to move here. + +There is a very nice `toString()` here; hovering over the `code` variable in +the debug window will pretty-print the IR "as if" globally scheduled, and the +code becomes very readable. + + +## Eval2 - A new Evaluator + +There is now a second evaluator that uses the scheduling information to +evaluate in a very straightforward way. Essentially the normal IR nodes are +treated like a special "machine instruction set" with infinite registers, and a +globally correct schedule. This evaluator supports functions and calls (and +recursive calls). + + +## Graph Visualizer + +Run `make view`, type your program in the text box, and click **Compile** +(or press **Ctrl+Enter**). Use the Left/Right arrow keys to step through graph +construction and optimization. See the [shared viewer guide](../graph/README.md). + +Nodes use colors and shapes for their graph roles: control, data, memory, Phis, +and scopes. This palette is distinct from the type-lattice diagrams. The viewer +also displays `ScopeNode`s, +which only exist for the Parser but are actual Nodes and have `use->def` edges +into the IR. + +## Memory across functions + +Each function has one `$mem` parameter and the parser keeps one memory binding. +Branches, loops, and multiple returns merge whole memory with BulkMemPhi. Field +uses discover precise MemPhis, while MemMerge packages a default memory state +and its alias overrides. MemMerge is an ordinary graph node; it no longer doubles +as a mutable parser alias table. + +| Boundary | Memory convention | +|---|---| +| Function entry | Parm 1 carries whole memory; heap contents are unknown | +| Call inputs | `{ctrl, $mem, arguments..., function pointer}` | +| CallEnd outputs | `{ctrl, $mem, value}` | +| Return inputs | `{ctrl, $mem, value, rpc}` | +| New inputs | `{ctrl, $mem, size, field values...}` | +| New outputs | `{ptr, $mem}`, covering only the allocated struct's aliases | + +A function may receive an existing object, so its entry memory cannot be treated +as an empty heap. Calls conservatively affect every alias. The returned memory +becomes the caller's new whole-memory state; there is no per-function alias +summary. Trivial inlining removes this boundary and lets the ordinary memory +rewrites see through the function body. + +Scheduling follows the relevant alias through MemMerge when looking for writes +or calls that must follow a Load. Calls end their basic block, so moving the Load +before that terminator supplies the required order without appending scheduling +edges to the argument list. Phi factoring keeps the simple one-step Load guard; +a direct Call user blocks that rewrite. diff --git a/chapter18/README.md b/chapter18/README.md index 5691059f..7482eafb 100644 --- a/chapter18/README.md +++ b/chapter18/README.md @@ -1,6 +1,6 @@ # Chapter 18: Functions -[Previous: Chapter 17](../chapter17/README.md) | +[Previous: Chapter 17b](../chapter17b/README.md) | [Next: Chapter 19](../chapter19/README.md) @@ -13,7 +13,7 @@ 5. [Graph Visualizer](#graph-visualizer) 6. [Memory across functions](#memory-across-functions) -You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter18) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter17...linear-chapter18) it to the previous chapter. +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter18) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter17b...linear-chapter18) it to the previous chapter. I hardly know where to begin! So many things changed here, mostly as indirect consequences of supporting functions. @@ -86,6 +86,12 @@ analysis of a hypothetical `call/cc` operation. That is outside our current scope, so for now these are only used in the evaluator. +Parameters use the explicit declaration syntax from +[Chapter 17a](../chapter17a/README.md): `!Point p` allows writes through a fixed +parameter binding, `Point !p` allows reassignment of a read-only reference, +and `int ~limit` fixes a primitive parameter. Inferred `var`/`val` parameters +are not supported. + ## Functions Functions themselves use the same syntax as function types, but filled in: @@ -183,16 +189,19 @@ After a `Call` is a `CallEndNode`, internally abbreviated as `cend`. The `CallEnd` will take the `Call` as an input, and also every *linked* function: functions the call-site *knows* it will call. This will be expanded later to be a conservative approximation to the *Call Graph*, with each `CallEnd` -*linked* to every function it *may* call; if a function is not linked it can not -be called from here. This requires a global analysis (fast, cheap, -incremental, and global), not in this chapter. So for the moment we only -link exact constant functions. +*linked* to every function it *may* call; if a function is not linked it can +not be called from here. This requires a global analysis (fast, cheap, +incremental, and global) which shows up in [Chapter24](../chapter19/README.md), +[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation). +So for the moment we only link exact constant functions. If a call site is linked to a single function, and that single function is only called by this one call site (its function pointer is only used here, obvious from GVN) then the function inlines in the IR. -`CallEnd`s are followed by projections for Control, Memory and the return value. +[edit note: needs before/after graph of trivial inlining] + +Like `Start`, `CallEnd`s are followed by projections for Control, Memory and the return value. diff --git a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java index 1b13a735..fb8e9a52 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/Parser.java @@ -175,6 +175,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) { // Stack parser state on the local Java stack, and unstack it later Node oldctrl = ctrl().keep(); Node oldmem = _scope.mem().keep(); @@ -211,7 +215,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 @@ -612,24 +616,23 @@ public class Parser { // outside the constructor need to check the final bit. if( _scope.in(def._idx)._type!=Type.TOP && def._final && // Inside a constructor, final assign is OK, outside nope - !(_scope.inCon() && def._idx >= _scope._lexSize.last()) ) + !_scope.canInit(def) ) throw error("Cannot reassign final '"+name+"'"); // Lift expression, based on type - Node lift = liftExpr(expr.keep(), def.type(), def._final); + Node lift = liftExpr(expr.keep(), def.type()); // 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 ) { + private Node liftExpr( Node expr, Type t ) { assert !(expr._type instanceof TypeMemPtr tmp) || !tmp.isFRef(); - // 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)); } // Auto-widen int to float @@ -637,7 +640,7 @@ public class Parser { // Auto-narrow wide ints to narrow ints expr = zsMask(expr,t); // Type is sane - if( expr._type!=Type.BOTTOM && !expr._type.shallowISA(t) ) + if( expr._type!=Type.BOTTOM && (!expr._type.shallowISA(t) || !expr._type.accessISA(t)) ) throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); return expr; } @@ -665,37 +668,45 @@ 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 ) { + Type base = TYPES.get(tmp._obj._name); + TypeMemPtr ptr = (TypeMemPtr)base; + return (tmp._ro ? ptr.makeRO() : ptr).makeNullable(); + } + return t.glb(); + } + + // 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; Node expr; if( match("=") ) { expr = parseAsgn(); - // TOP means val and val is always final - xfinal = (t==Type.TOP) || - // BOTTOM is var and var is always not-final - (t!=Type.BOTTOM && - // no Bang AND - !hasBang && - // 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(); // Widen if not final + if( !xfinal ) t = inferredType(t); // Widen if not final } if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) tfp.setName(name); @@ -711,8 +722,8 @@ 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); } @@ -720,10 +731,7 @@ public class Parser { } // Lift expression, based on type - Node lift = liftExpr(expr, t, xfinal); - - if( xfinal && t instanceof TypeMemPtr tmp ) - t = tmp.makeRO(); + Node lift = liftExpr(expr, t); // Lift type to the declaration. This will report as an error later if // we cannot lift the type. @@ -787,12 +795,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); @@ -801,6 +811,13 @@ public class Parser { return posT(old1); if( t0 == Type.BOTTOM || t0 == Type.TOP ) return t0; // var/val type inference Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(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 ) { @@ -809,6 +826,9 @@ public class Parser { throw error("Type "+t0+" cannot be null"); if( tmp.nullable() ) throw error("Type "+t2+" already allows null"); t2 = tmp.makeNullable(); + } else if( match("[~]") ) { + TypeMemPtr ary = typeAry(t2); + t2 = ary.makeFrom(ary._obj.makeRO()).makeRO(); } else if( match("[]") ) { t2 = typeAry(t2); } else @@ -820,7 +840,7 @@ 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(';')) ) return posT(old1); @@ -828,7 +848,7 @@ public class Parser { if( id==null ) return posT(old1); // Reset lexer to reparse // Yes a forward ref, so declare it - TYPES.put(tname,t1); + TYPES.put(tname,((TypeMemPtr)t1).withAccess(false)); return t2; } @@ -838,7 +858,15 @@ public class Parser { throw error("Arrays of reference types must always be nullable"); String tname = "["+t.str()+"]"; Type ta = TYPES.get(tname); - if( ta != null ) return (TypeMemPtr)ta; + if( ta != null ) { + TypeStruct ary = ((TypeMemPtr)ta)._obj; + // Keep the original shallow struct reference. Resolving a recursive + // struct must not expand its array element type on each lookup. + if( t instanceof TypeMemPtr ptr && (ptr._obj._fields==null || !ptr._obj.isAry()) && + ary._fields[1]._type instanceof TypeMemPtr old ) + t = old.withAccess(ptr._ro); + return TypeMemPtr.make(TypeStruct.makeAry(TypeInteger.BOT,ary._fields[0]._alias,t,ary._fields[1]._alias)); + } // Need make an array type. TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); assert ts.str().equals(tname); @@ -1108,7 +1136,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); + return liftExpr(peep(op.widen()),t); } @@ -1231,6 +1259,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); @@ -1269,7 +1299,7 @@ public class Parser { // Sanity check field name for existing TypeMemPtr tmp = (TypeMemPtr)TYPES.get(ptr._obj._name); if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr + "'"); - TypeStruct base = tmp._obj; + TypeStruct base = ptr._obj.isAry() ? ptr._obj : tmp._obj; int fidx = base.find(name); if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); @@ -1290,7 +1320,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 ); + Node lift = liftExpr( val, tf ); 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 @@ -1347,11 +1377,13 @@ 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(); _lexer.skipWhiteSpace(); Lexer loc = loc(); // First argument location 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); @@ -1360,7 +1392,7 @@ public class Parser { require("->"); // Make a concrete function type, with a fidx TypeFunPtr tfp = TypeFunPtr.makeFun(TypeTuple.make(ts.asAry()),Type.BOTTOM); - ReturnNode ret = parseFunctionBody(tfp,loc,ids.asAry()); + ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); return con(ret._fun.sig()); } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java index 442a22e5..10b04b38 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -133,7 +133,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)) ) return Parser.error( "Argument #"+i+" isa "+arg(i+2)._type+", but must be a "+tfp.arg(i), _loc); return null; diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 0fab82c3..edde1dc1 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -56,8 +56,9 @@ public class LoadNode extends MemOpNode { Type t = MemMergeNode.contents(mem(),_alias,this); // Update declared forward ref to the actual. if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) - _declaredType = tmp; - return err()==null ? _declaredType.join(t) : _declaredType; + _declaredType = tmp.withAccess(((TypeMemPtr)_declaredType)._ro); + Type rez = err()==null ? _declaredType.join(t) : _declaredType; + return ptr()._type.isFinal() || _declaredType.isFinal() ? rez.makeRO() : rez; } @Override @@ -72,13 +73,13 @@ public class LoadNode extends MemOpNode { if( mem() instanceof StoreNode st && _alias==st._alias && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect - return st.val(); + return castRO(st.val()); } // Simple Load-after-New on same address. if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && ptr == nnn.proj(0) ) // Must check same object - return nnn.in(nnn.findAlias(_alias)); // Load from New init + return castRO(nnn.in(nnn.findAlias(_alias))); // Load from New init // Load-after-Store on same address, but bypassing provably unrelated // stores. This is a more complex superset of the above two peeps. @@ -199,7 +200,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/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java index c96255b1..114a652a 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/Node.java @@ -588,9 +588,8 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { private static final BitSet WVISIT = new BitSet(); final public <E> E walk( Function<Node,E> pred ) { assert WVISIT.isEmpty(); - E rez = _walk(pred); - WVISIT.clear(); - return rez; + try { return _walk(pred); } + finally { WVISIT.clear(); } } private <E> E _walk( Function<Node,E> pred ) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 5801cdf5..de199d2d 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -124,6 +124,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)==Kind.Constructor ) + return v._idx >= _lexSize.at(i-1) && v._idx < _lexSize.at(i); + return false; + } + public boolean inCon() { return _kinds.last() == Kind.Constructor; } // Is v outside any current function scope? @@ -208,7 +217,7 @@ public class ScopeNode extends Node { : loop.setDef(v._idx,PhiNode.make(v._name, v.lazyGLB(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } - assert !v._final || st==null; + assert !v._final || st==null || canInit(v); if( st!=null ) setDef(v._idx,st); // Set new value return v; } diff --git a/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java index ba367a67..3c0b0e73 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -122,7 +122,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 && !"[]".equals(_name) ) + if( tmp._ro || (tmp._obj.field(_name)._final && !"[]".equals(_name)) ) return Parser.error("Cannot modify final field '"+_name+"'",_loc); Type t = val()._type; return _init || t.isa(_declaredType) ? null : Parser.error("Cannot store "+t+" into field "+_declaredType+" "+_name,_loc); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java index ffa9d2a6..c93f82e7 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Field.java @@ -34,7 +34,7 @@ public class Field extends Type { public Field makeFrom( Type type ) { return type == _type ? this : new Field(_fname,type,_alias,_final).intern(); } - @Override public Field makeRO() { return _final ? this : make(_fname,_type.makeRO(),_alias,true); } + @Override public Field makeRO() { return isFinal() ? this : make(_fname,_type.makeRO(),_alias,true); } @Override public boolean isFinal() { return _final && _type.isFinal(); } public static final Field TEST = make("test",Type.NIL,-2,false); diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java index b6757ef2..34f54be8 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java @@ -202,6 +202,10 @@ public class Type { /** Compute greatest lower bound in the lattice */ public Type glb() { return Type.BOTTOM; } + // 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/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 9ea24b97..61b020cb 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -25,20 +25,41 @@ public class TypeMemPtr extends TypeNil { // (TOP ,true ) - a nil public final TypeStruct _obj; + // Deep read-only access through this pointer; independent of slot finality. + public boolean _ro; + private TypeMemPtr(byte nil, TypeStruct obj) { super(TMEMPTR,nil); assert obj!=null; _obj = obj; + _ro = obj==TypeStruct.BOT; } static TypeMemPtr make(byte nil, TypeStruct obj) { return new TypeMemPtr(nil, obj).intern(); } public static TypeMemPtr makeNullable(TypeStruct obj) { return make((byte)3, obj); } public static TypeMemPtr make(TypeStruct obj) { return new TypeMemPtr((byte)2, obj).intern(); } - public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj); } + public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj).withAccess(_ro); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } - @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil,_obj); } - @Override public TypeMemPtr makeRO() { return makeFrom(_obj.makeRO()); } - @Override public boolean isFinal() { return _obj.isFinal(); } + @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil,_obj).withAccess(_ro); } + @Override public TypeMemPtr makeRO() { return withAccess(true); } + @Override public boolean isFinal() { return _ro; } + + public TypeMemPtr withAccess(boolean ro) { + if( _ro==ro ) return this; + TypeMemPtr ptr = new TypeMemPtr(_nil, _obj); + ptr._ro = ro; + return ptr.intern(); + } + + // 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]._type, b = ptr._obj._fields[1]._type; + 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} @@ -47,43 +68,43 @@ 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; - return TypeMemPtr.make(xmeet0(that), (TypeStruct)_obj.meet(that._obj)); + return TypeMemPtr.make(xmeet0(that), (TypeStruct)_obj.meet(that._obj)).withAccess(_ro | that._ro); } @Override - public TypeMemPtr dual() { return TypeMemPtr.make( dual0(), _obj.dual()); } + public TypeMemPtr dual() { return TypeMemPtr.make( dual0(), _obj.dual()).withAccess(!_ro); } // RHS is NIL; do not deep-dual when crossing the centerline - @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj); } + @Override Type meet0() { return _nil==3 ? this : make((byte)3,_obj).withAccess(_ro); } // True if this "isa" t up to named structures @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 throw Utils.TODO(); // return _obj.shallowISA(that._obj); } - @Override public TypeMemPtr glb() { return make((byte)3,_obj.glb()); } + @Override public TypeMemPtr glb() { return make((byte)3,_obj.glb()).withAccess(true); } // Is forward-reference @Override public boolean isFRef() { return _obj.isFRef(); } @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers - @Override int hash() { return _obj.hashCode() ^ super.hash(); } + @Override int hash() { return (_ro ? 8192 : 0) ^ _obj.hashCode() ^ super.hash(); } @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _obj == ptr._obj && super.eq(ptr); + return _ro==ptr._ro && _obj == ptr._obj && super.eq(ptr); } @Override public String str() { diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java index d0d33663..bcae373b 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -24,7 +24,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]; """; @@ -100,7 +100,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; @@ -113,7 +113,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; @@ -152,7 +152,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; @@ -167,7 +167,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; @@ -180,7 +180,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; @@ -206,7 +206,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; @@ -220,7 +220,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; @@ -235,7 +235,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; @@ -256,7 +256,7 @@ struct s0 { int v0; }; s0? v1=new s0; -s0? v1; +!s0? !v1; v1=new s0; """); try { code.parse(); fail(); } @@ -272,7 +272,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 ) { @@ -290,9 +290,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; @@ -308,8 +308,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; @@ -327,9 +327,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; } @@ -454,9 +454,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; @@ -469,7 +469,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; @@ -498,7 +498,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; @@ -513,9 +513,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; @@ -532,7 +532,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(); @@ -545,9 +545,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/chapter18/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter10bTest.java deleted file mode 100644 index 01bce801..00000000 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter10bTest.java +++ /dev/null @@ -1,65 +0,0 @@ -package com.seaofnodes.simple; - -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() throws ReflectiveOperationException { - // 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).parse(); - var field = IterPeeps.class.getDeclaredField("WORK"); - field.setAccessible(true); - Object work = field.get(null); - field = work.getClass().getDeclaredField("_R"); - field.setAccessible(true); - ((java.util.Random)field.get(work)).setSeed(seed); - code.opto(); - assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); - } - } -} diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 2d7d46f7..01e37a43 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,553 +1,65 @@ package com.seaofnodes.simple; - +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; - } + @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() throws ReflectiveOperationException { + // 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).parse(); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + code.opto(); + assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); } } - 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().typeCheck().GCM(); - assertEquals("return Phi(Region,9,Top,Top,Top,Top);", 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(Region,(Phi_primeCount+1),Phi_primeCount))));", 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/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 1e7bfc6b..fc5b37d9 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,83 +1,260 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; -import org.junit.Ignore; 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 'i'",e.getMessage()); } } + @Test + public void testLinkedList1() { + 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( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.i; +"""); + code.parse().opto(); + assertEquals("return Phi(Region,0,1,.i);", 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 Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0f));", code.print()); - assertEquals("3.0", Eval2.eval(code, 9)); - assertEquals("1.414213562373095", Eval2.eval(code, 2)); + assertEquals("return (const)M;", code.print()); } @Test - public void testFPOps() { + public void testNullRef2() { CodeGen code = new CodeGen( """ -flt x = arg; -return x+1==x; +struct M { int m; }; +struct N { !M !next; int i; }; +N n = new N { next = null; } +return n.next; +"""); + try { code.parse().opto(); 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(); fail(); } + catch( Exception e ) { assertEquals("Type 3.14 is not of declared type int",e.getMessage()); } + } + + @Test + public void testNullRef4() { + CodeGen code = new CodeGen("-null-5/null-5;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot 'Add' 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 'Add' null",e.getMessage()); } + } + + @Test + public void testEmpty() { + CodeGen code = new CodeGen( +""" +struct S{}; """); code.parse().opto(); - assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); - assertEquals("0", Eval2.eval(code, 1)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } + + @Test + public void testForwardRef0() { + CodeGen code = new CodeGen( +""" +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 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 { !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{a=Y{a=J{a=U{a=F{a=Q{a=B{a=M{a=X{a=I{a=T{a=E{a=P{a=A{a=L{a=W{a=H{a=S{a=D{a=O{a=Z{a=K{a=V{a=G{a=$cyclic,b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic}", Eval2.eval(code, 0)); + } + } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java index de722026..584377e4 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -1,260 +1,553 @@ package com.seaofnodes.simple; + 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 Phi(Region,9,Top,Top,Top,Top);", 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 'i'",e.getMessage()); } + code.parse().opto(); + assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi(Region,(Phi_primeCount+1),Phi_primeCount))));", 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 i; }; -LLI? !head = null; -while( arg ) { - LLI !x = new LLI; - x.next = head; - x.i = arg; - head = x; - arg = arg-1; -} -if( !head ) return 0; -LLI? next = head.next; -if( next==null ) return 1; -return next.i; +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 Phi(Region,0,1,.i);", code.print()); - assertEquals("2", Eval2.eval(code, 3)); + 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(); 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(); fail(); } - catch( Exception e ) { assertEquals("Type 3.14 is not of declared type int",e.getMessage()); } + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test - public void testNullRef4() { - CodeGen code = new CodeGen("-null-5/null-5;"); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot 'Add' 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 'Add' null",e.getMessage()); } + 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 testEmpty() { + public void testAntiDeps8() { CodeGen code = new CodeGen( """ -struct S{}; +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()); - assertEquals("0", Eval2.eval(code, 0)); } @Test - public void testForwardRef0() { + public void testAntiDeps9() { CodeGen code = new CodeGen( """ -struct S1 { S2? s; }; -return 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; """); - try { code.parse().opto(); fail(); } - catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } + code.parse().opto(); + assertEquals("return S;", code.print()); } @Test - public void testForwardRef1() { + public void testExample2() { 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; +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 S2;", code.print()); + //assertEquals("return new S;", code.print()); } @Test - public void testcheckNull() { + public void testScheduleUse() { 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; +int v0=0; +while(0>=0) { + u1 v1=0; + v1=v0; + if(v1*0) + v0=-v1; +} +return 0; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test - public void testCoRecur2() { + 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{a=Y{a=J{a=U{a=F{a=Q{a=B{a=M{a=X{a=I{a=T{a=E{a=P{a=A{a=L{a=W{a=H{a=S{a=D{a=O{a=Z{a=K{a=V{a=G{a=$cyclic,b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic},b=$cyclic,c=$cyclic}", Eval2.eval(code, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); } } diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java new file mode 100644 index 00000000..7b065411 --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -0,0 +1,83 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; +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)/2.0f));", 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/chapter18/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter14Test.java index a3025001..a40dbce1 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter18/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/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 1c6e5ae7..00917345 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -20,8 +20,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; """); @@ -93,7 +93,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(); @@ -107,16 +107,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]; @@ -137,11 +137,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 @@ -160,9 +160,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; """); @@ -175,7 +175,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(); @@ -252,8 +252,8 @@ return rez; 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/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 3dd37f33..4ff87095 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -43,31 +43,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() { @@ -82,18 +57,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; }; @@ -107,83 +70,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 (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(); fail(); } - catch( Exception e ) { assertEquals("Cannot reassign final '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; @@ -204,8 +95,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; @@ -257,13 +148,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/chapter18/src/test/java/com/seaofnodes/simple/Chapter17aTest.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17aTest.java new file mode 100644 index 00000000..ab92d439 --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17aTest.java @@ -0,0 +1,107 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +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(); fail(); } + catch( Exception e ) { assertEquals("Cannot reassign final '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/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 8ec95f33..e64d5b27 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -4,7 +4,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() { @@ -81,7 +81,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; """); @@ -157,14 +157,14 @@ 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)); @@ -183,7 +183,7 @@ return s.x; } @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)); @@ -197,7 +197,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()); } } @@ -205,15 +205,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 """); try { code.parse().opto().typeCheck(); fail(); } @@ -223,15 +223,15 @@ xfoo.bar.x++; // Error, cannot mutate through xfoo @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; @@ -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?[] not_array_of_b = new B?[0]; + !B?[]? !nil_array_of_b; + !B?[] not_array_of_b = new !B?[0]; }; return new A.not_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.not_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/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java index c08bc5b2..c4d5b9ac 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -280,7 +280,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); @@ -299,7 +299,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;}; @@ -365,7 +365,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; } @@ -414,7 +414,7 @@ struct S { { int } f = { -> return x(); }; }; val x = { -> return 1; }; -S? s = null; +!S? !s = null; for(;;) { if (s) return s.f; } @@ -448,7 +448,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; """); @@ -459,10 +459,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; @@ -488,13 +488,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; """; @@ -507,12 +507,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/chapter18/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java b/chapter18/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java index f78e1b21..860827d7 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java +++ b/chapter18/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/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java index d48449d5..a352530f 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -12,12 +12,12 @@ public class MergeSortTest { """ // 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; @@ -27,7 +27,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++) { @@ -42,7 +42,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/chapter18/src/test/java/com/seaofnodes/simple/MutabilityTest.java b/chapter18/src/test/java/com/seaofnodes/simple/MutabilityTest.java new file mode 100644 index 00000000..0861424f --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/MutabilityTest.java @@ -0,0 +1,72 @@ +package com.seaofnodes.simple; + +import org.junit.Test; +import static org.junit.Assert.*; + +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/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java index d50c302a..d29166a7 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -24,7 +24,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; @@ -41,7 +41,7 @@ return i; struct S { int f; }; -S !v0=new S; +!S !v0=new S; if(arg) v0.f=1; return v0; """); @@ -57,7 +57,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/chapter18/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter18/src/test/java/com/seaofnodes/simple/TypeTest.java index d94f5b5a..dee033bc 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -56,12 +56,12 @@ public class TypeTest { Assert.assertNotEquals(ptr1, ptr2); Assert.assertNotEquals(ptr1, ptr1.glb()); - Assert.assertEquals(ptr1nil.makeRO(), ptr1.glb()); + Assert.assertEquals(ptr1nil.makeFrom(s1.glb()).makeRO(), ptr1.glb()); Assert.assertEquals(ptr1, ptr1.dual().dual()); - Assert.assertEquals(ptr1.glb().makeRO(), ptr1.dual().glb()); - Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT), ptr1.meet(ptr2nil)); - Assert.assertEquals(ptr1.glb(), ptr1.meet(TypeNil.NIL).makeRO()); + Assert.assertEquals(ptr1.glb().makeFrom(s1.dual().glb()), ptr1.dual().glb()); + 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); @@ -70,7 +70,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/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 86dbe66a..d061a656 100644 --- a/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter18/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -479,7 +479,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; @@ -676,15 +676,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); |
