diff options
49 files changed, 1568 insertions, 610 deletions
@@ -59,7 +59,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 13](docs/chapter13/README.md): Global Code Motion - Scheduling. * [Chapter 14](docs/chapter14/README.md): Numeric types: floats, narrow integers, ranges and rounding to `f32`. * [Chapter 15](docs/chapter15/README.md): One dimensional static length array type, with array loads and stores. -* Chapter 16: Constructors +* [Chapter 16](docs/chapter16/README.md): Constructors * Chapter 17a: Binding mutability, reference permissions, and deep read-only views. * Chapter 17b: Syntax sugar: `var`, `val`, `x+=y`, `for(init; test; next) body` * Chapter 18: Functions and calls. diff --git a/docs/chapter16/16-grammar.md b/docs/chapter16/16-grammar.md new file mode 100644 index 00000000..7da725e9 --- /dev/null +++ b/docs/chapter16/16-grammar.md @@ -0,0 +1,130 @@ +# Grammar for Chapter 16 + +```antlrv4 +grammar SimpleLanguage; + +program : block EOF ; + +block : statement+ ; + + +statement + : '{' block '}' + | returnStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + | structDeclaration + | expressionStatement + ; + + +returnStatement : 'return' expression ';' ; + +ifStatement : 'if' '(' expression ')' statement ('else' statement)? ; + +whileStatement : 'while' '(' expression ')' statement ; + +breakStatement : 'break' ';' ; + +continueStatement : 'continue' ';' ; + + +structDeclaration : 'struct' IDENTIFIER '{' block '}' ; + +expressionStatement + : type IDENTIFIER ';' + | type IDENTIFIER '=' expression ';' + | IDENTIFIER '=' expression ';' + | expression + ; + +PRIMTYPE + : 'int' + | 'i8' + | 'i16' + | 'i32' + | 'i64' + | 'u8' + | 'u16' + | 'u32' + | 'flt' + | 'f32' + | 'f64' + | 'bool' + ; + +type + : PRIMTYPE + | typeName '?'? + | typeName nestedArray+ + ; + +nestedArray : '?'? '[]'* ; + +typeName : IDENTIFIER ; + + +expression : bitWiseExpression ; + +bitWiseExpression + : comparisonExpression ( '&' | '|' | '^' ) comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!='| '>'| '<'| '>='| '<=') shiftExpression)* + ; + +shiftExpression + : additiveExpression ( '<<' | '>>>' | '>>' ) additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression postAssign + ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | '(' expression ')' + | 'true' + | 'false' + | 'null' + | newExpression + | IDENTIFIER + ; + +newExpression + : 'new' IDENTIFIER [ '{' block '}' ] + | 'new' IDENTIFIER '[' expression ']' + ; + +postAssign : postFix [ '=' expression ] | [ '#' ]; + +postFix + : '.' IDENTIFIER postFix + | '[' expression ']' postFix + ; + + +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; + +INTEGER_LITERAL + : [1-9]DIGIT* + | [0] + ; + +NON_DIGIT: [a-zA-Z_]; +DIGIT: [0-9]; +``` diff --git a/docs/chapter16/Makefile b/docs/chapter16/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter16/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter16/README.md b/docs/chapter16/README.md new file mode 100644 index 00000000..c55de47f --- /dev/null +++ b/docs/chapter16/README.md @@ -0,0 +1,131 @@ +# Chapter 16: Constructors + +[Previous: Chapter 15](../chapter15/README.md) | +[Next: Chapter 17a](../chapter17a/README.md) + +# Table of Contents + +1. [Constructors](#constructors) +2. [Initialization code](#initialization-code) +3. [Multiple Decls](#multiple-declarations-of-the-same-type) +4. [Memory through constructors](#memory-through-constructors) + +This chapter adds field defaults and constructor blocks. Chapter 17a will add +fixed bindings and read-only access, using these constructors to initialize them. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter16) 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-chapter15...linear-chapter16) it to the previous chapter. + +## Constructors + +A big problem with the [Chapter 12](../chapter12/README.md) refs is that +not-null fields always start out `null`. This is fixed in this chapter, where +a *constructor* syntax is required to initialize not-null fields. + +Fields are initialized in three ways: + +1. A default zero/null initialization for fields that allow it. No special + syntax is required. +``` +int x; // x is initialized to 0 +struct Ref { Ref? ptr; }; // Instances of Ref will have ptr initialized to null +return new Ref.ptr; // Returns a null +``` + +2. The type declaration can specify an initial value. Later allocations will + start with this value. +``` +int x = 5; // x is initialized to 5 +struct Point { int x=1; int y=1; }; // Point x and y will start as 1, not 0 +return new Point.x; // Returns a 1 +``` + +3. The allocation can specify an initial value. + +``` +struct Point { int x=1; int y=1; }; // Point x and y will start as 1, not 0 +return new Point { x=3; }.x; // Returns a 3 +``` + +Not-null fields *must* be initialized before first use and before the +end of the allocation. They can be initialized in either the declaration or +allocation. They do not start with the default value, although the +initialization can be to the default. + +``` +struct Person { u8[] name; }; +return new Person; // ERROR: 'Person' is not fully initialized, field 'name' needs to be set in a constructor +``` + + +## Initialization code + +The parser allows a full Block statement to be parsed in either the type +declaration or the allocation. Any amount of code is legal, including +`while` loops and `return`s. + +``` +struct Square { + flt side = arg; + flt diag = arg*arg/2; + // Newton's approximation to the square root, computed in a constructor. + // The actual allocation will copy in this result as the initial + // value for 'diag'. + while( 1 ) { + // The next-guess variable "next" is not a field in Square, + // because it does not appear at the top level + flt next = (side/diag + diag)/2; + if( next == diag ) break; + diag = next; + } +}; +return new Square; +``` + +Another example: + +``` +struct Buffer { + if( arg < 0 || arg > 1000000 ) + return null; // Size out of bounds + u8[] buffer = new u8[arg]; +}; +return new Buffer; +``` + + +### Multiple declarations of the same type + +Also new this chapter is allowing multiple declarations with the same type, as +is commonly seen in other languages: + +``` +int x,y; // Two int variables declared +struct Point { int x,y,z; }; // Three fields declared +``` + +## Memory through constructors + +The lazy memory partitioning from [Chapter 11](../chapter11/README.md) continues +through constructors. The parser tracks one `$mem` variable alongside its scalar +variables. Branches and loops merge that binding with BulkMemPhi; field access +splits out precise MemPhis when needed. The variable records for declared types live in ScopeNode. There is no separate parser table of memory aliases. + +A constructor computes its field values before the allocation. Reads, writes, +and loops in its body update the same `$mem` binding as ordinary code. New then +takes `{ctrl, $mem, size, field values...}` and produces `{ptr, $mem}`. The input +memory is a partial MemMerge containing the struct's aliases; the output memory +covers those same aliases. A whole-memory MemMerge preserves unrelated slices. +Arrays use the same layout, supplying their length and default element value as +initializer inputs. + +A Load from its own New can use the matching initializer input. Alias contents +combine the initializer's type with incoming contents from older objects, so a +new object does not erase facts or effects for existing objects. Loads bypass +only allocations proven to be distinct. Scheduling follows partial aggregates +when establishing read-before-write order. + +Sharing one allocation memory result makes Store-to-New folding more +conservative: the existing sole-use check now sees users of every covered +alias. This can leave a field Load where separate memory projections previously +allowed a constant fold. Phi factoring also retains the simple one-step Load +safety check. diff --git a/src/main/java/com/seaofnodes/simple/Ary.java b/src/main/java/com/seaofnodes/simple/Ary.java new file mode 100644 index 00000000..8654d41e --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/Ary.java @@ -0,0 +1,217 @@ +package com.seaofnodes.simple; + +import java.lang.StringBuilder; +import java.lang.reflect.Array; +import java.util.*; + +// ArrayList with saner syntax +public class Ary<E> extends AbstractList<E> implements List<E> { + public E[] _es; + public int _len; + + public Ary(E[] es) { this(es,es.length); } + public Ary(E[] es, int len) { if( es.length==0 ) es=Arrays.copyOf(es,1); _es=es; _len=len; } + @SuppressWarnings("unchecked") + public Ary(Class<E> clazz) { this((E[]) Array.newInstance(clazz, 1),0); } + + /** @return list is empty */ + public boolean isEmpty() { return _len==0; } + /** @return active list length */ + public int len() { return _len; } + public int size() { return len(); } + + /** @param i element index + * @return element being returned; throws if OOB + * @exception AIOOBE if !(0 <= i < _len) + */ + public E get( int i ) { return at(i); } + public E at( int i ) { + range_check(i); + return _es[i]; + } + + /** @return last element */ + public E last( ) { return at(_len-1); } + + /** Add element in amortized constant time + * @param e Element to add at end of list + **/ + public E push( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + return (_es[_len++] = e); + } + /** @return remove and return last element */ + public E pop( ) { + range_check(0); + return _es[--_len]; + } + @Override public E removeLast() { return pop(); } + + + /** Add element in amortized constant time + * @param e Element to add at end of list + * @return true */ + public boolean add( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + _es[_len++] = e; + return true; + } + + ///** Slow, linear-time, element insert. Preserves order. + // * @param i index to insert at, between 0 and _len inclusive. + // * @param e Element to insert + // */ + //public void insert( int i, E e ) { + // if( i < 0 || i>_len ) + // throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + // if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + // System.arraycopy(_es,i,_es,i+1,(_len++)-i); + // _es[i] = e; + //} + + /** Fast, constant-time, element removal. Does not preserve order + * @param i element to be removed + * @return element removed */ + public E del( int i ) { + range_check(i); + E tmp = _es[i]; + _es[i]=_es[--_len]; + return tmp; + } + + ///** Element removal, using '=='. Does not preserve order. + // * @param e element to be removed + // * @return element removed */ + //public E del( E e ) { + // for( int i=0; i<_len; i++ ) { + // E tmp = _es[i]; + // if( tmp==e ) { + // _es[i]=_es[--_len]; + // return tmp; + // } + // } + // return null; + //} + + /** Slow, linear-time, element removal. Preserves order. + * @param i element to be removed + * @return element removed */ + @Override public E remove( int i ) { + range_check(i); + E e = _es[i]; + System.arraycopy(_es,i+1,_es,i,(--_len)-i); + return e; + } + + /** Remove all elements */ + public void clear( ) { _len=0; } + + /** Set existing element + * @param i element to set + * @param e value to set + * @return old value + * @exception AIOOBE if !(0 <= i < _len) + */ + public E set( int i, E e ) { + range_check(i); + E old = _es[i]; + _es[i] = e; + return old; + } + + public Ary<E> setLen( int len ) { + if( len > _len ) + while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + _len = len; + while( _es.length > (len<<1) ) // Shrink if hugely too large + _es = Arrays.copyOf(_es,_es.length>>1); + Arrays.fill(_es,len,_es.length,null); + return this; + } + + /** @param c Collection to be added */ + public boolean addAll( Collection<? extends E> c ) { + if( c==null ) return false; + for( E e : c ) add(e); + return true; + } + public Ary<E> addAll( Iterable<? extends E> it ) { for( E e : it ) add(e); return this; } + + /** @param es Array to be added */ + public <F extends E> Ary<E> addAll( F[] es ) { + if( es==null || es.length==0 ) return this; + while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(es,0,_es,_len,es.length); + _len += es.length; + return this; + } + + /** @param c Collection to be added */ + public Ary<E> addAll( Ary<? extends E> c ) { + if( c==null || c._len==0 ) return this; + while( _len+c._len > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(c._es,0,_es,_len,c._len); + _len += c._len; + return this; + } + + /** @return compact array version */ + public E[] asAry() { return Arrays.copyOf(_es,_len); } + + /** Sorts in-place + * @param c Comparator to sort by */ + public void sort_update(Comparator<? super E> c ) { Arrays.sort(_es, 0, _len, c); } + + /** Find the first matching element using ==, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param e Element to find + * @return index of first matching element, or -1 if none */ + public int find( E e ) { + for( int i=0; i<_len; i++ ) if( _es[i]==e ) return i; + return -1; + } + + + /** @return an iterator */ + @Override public Iterator<E> iterator() { return new Iter(); } + private class Iter implements Iterator<E> { + int _i=0; + @Override public boolean hasNext() { return _i<_len; } + @Override public E next() { return _es[_i++]; } + } + + @Override public String toString() { + StringBuilder sb = new StringBuilder().append('{'); + for( int i=0; i<_len; i++ ) { + if( i>0 ) sb.append(','); + if( _es[i] != null ) sb.append(_es[i].toString()); + } + return sb.append('}').toString(); + } + + private void range_check( int i ) { + if( i < 0 || i>=_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + } + + // Note that the hashCode() and equals() are not invariant to changes in the + // underlying array. If the hashCode() is used (e.g., inserting into a + // HashMap) and the then the array changes, the hashCode() will change also. + @Override public boolean equals( Object o ) { + if( this==o ) return true; + if( !(o instanceof Ary ary) ) return false; + if( _len != ary._len ) return false; + if( _es == ary._es ) return true; + for( int i=0; i<_len; i++ ) + if( !(_es[i]==null ? (ary._es[i] == null) : _es[i].equals(ary._es[i])) ) + return false; + return true; + } + @Override public int hashCode( ) { + int sum=_len; + for( int i=0; i<_len; i++ ) + sum += _es[i]==null ? 0 : _es[i].hashCode(); + return sum; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index d17ec3b6..bb109fc9 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -66,7 +66,7 @@ public abstract class GlobalCodeMotion { // Reverse Post-Order on CFG for( int j=rpo.size()-1; j>=0; j-- ) { CFGNode cfg = rpo.get(j); - cfg.loopDepth(); + cfg.loopDepth(); // Pre-compute loop depth for( Node n : cfg._inputs ) _schedEarly(n,visit); // In dead infinite loops, entire code blocks may be unreachable @@ -98,7 +98,7 @@ public abstract class GlobalCodeMotion { // Schedule inputs first, except Phis: following their backedges would // enter a data cycle before its control has been scheduled. for( Node def : n._inputs ) - if( def!=null ) + if( def!=null && !(def instanceof PhiNode) ) _schedEarly(def,visit); // An existing edge 0 already supplies control (or a Phi/Proj binding). if( n.in(0)==null ) { @@ -143,7 +143,7 @@ public abstract class GlobalCodeMotion { // All uses done? for( Node use : n._outputs ) - if( use!=null && late[use._nid]==null ) + if( use!=null && late[use._nid]==null && !(use instanceof PhiNode) ) continue outer; // Nope, await all uses done // Loads need their memory inputs' uses also done @@ -262,11 +262,11 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) { // Preserve the full store range for the earlier evaluator scheduler. // It places nodes independently of GCM and may hoist this store. - for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { + for( ; stblk != defblk; stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence - if( anti[stblk._nid]==load._nid ) { + if( !(stblk instanceof IfNode) && anti[stblk._nid]==load._nid ) { lca = stblk.domLCA(lca,null); // Raise Loads LCA - if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, + if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here } diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 7075d526..cabc4a15 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -50,7 +50,7 @@ public abstract class IterPeeps { return (N)WORK.push(n); } - public static void addAll( ArrayList<Node> ary ) { + public static void addAll( Ary<Node> ary ) { WORK.addAll(ary); } @@ -176,7 +176,7 @@ public abstract class IterPeeps { return x; } - public void addAll( ArrayList<E> ary ) { + public void addAll( Ary<E> ary ) { for( E n : ary ) push(n); } diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index a0c15ae3..deb359ce 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -4,12 +4,13 @@ import com.seaofnodes.graph.GraphObserver; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import static com.seaofnodes.simple.Utils.TODO; import java.util.*; /** * The Parser converts a Simple source program to the Sea of Nodes intermediate - * representation directly in one pass. There is no intermediate Abstract + * representation directly in one pass. There is no intermediate Abstract * Syntax Tree structure. * <p> * This is a simple recursive descent parser. All lexical analysis is done here as well. @@ -103,36 +104,27 @@ public class Parser { // Mapping from a type name to a Type. The string name matches // `type.str()` call. No TypeMemPtrs are in here, because Simple does not // have C-style '*ptr' references. - public static HashMap<String, Type> TYPES = new HashMap<>(); + public final HashMap<String, Type> TYPES; + + // Mapping from a type name to the constructor for a Type. + public final HashMap<String, StructNode> INITS; + public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); IterPeeps.reset(); - TYPES.clear(); - TYPES.put("bool",TypeInteger.U1 ); - TYPES.put("byte",TypeInteger.U8 ); - TYPES.put("f32" ,TypeFloat .B32); - TYPES.put("f64" ,TypeFloat .BOT); - TYPES.put("flt" ,TypeFloat .BOT); - TYPES.put("i16" ,TypeInteger.I16); - TYPES.put("i32" ,TypeInteger.I32); - TYPES.put("i64" ,TypeInteger.BOT); - TYPES.put("i8" ,TypeInteger.I8 ); - TYPES.put("int" ,TypeInteger.BOT); - TYPES.put("u1" ,TypeInteger.U1 ); - TYPES.put("u16" ,TypeInteger.U16); - TYPES.put("u32" ,TypeInteger.U32); - TYPES.put("u8" ,TypeInteger.U8 ); SCHEDULED = false; _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; - START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg }); + START = new StartNode(arg); STOP = new StopNode(source); ZERO = con(0).keep(); XCTRL= new XCtrlNode().peephole().keep(); ALIAS = 2; // alias 0 for the control, 1 for memory + TYPES = defaultTypes(); + INITS = new HashMap<>(); } public Parser(String source) { @@ -142,28 +134,49 @@ public class Parser { @Override public String toString() { return _lexer.toString(); } - String src() { return new String( _lexer._input ); } + public static HashMap<String, Type> defaultTypes() { + return new HashMap<>() {{ + put("bool",TypeInteger.U1 ); + put("byte",TypeInteger.U8 ); + put("f32" ,TypeFloat .B32); + put("f64" ,TypeFloat .BOT); + put("flt" ,TypeFloat .BOT); + put("i16" ,TypeInteger.I16); + put("i32" ,TypeInteger.I32); + put("i64" ,TypeInteger.BOT); + put("i8" ,TypeInteger.I8 ); + put("int" ,TypeInteger.BOT); + put("u1" ,TypeInteger.U1 ); + put("u16" ,TypeInteger.U16); + put("u32" ,TypeInteger.U32); + put("u8" ,TypeInteger.U8 ); + }}; + } // Debugging utility to find a Node by index public static Node find(int nid) { return START.find(nid); } private Node ctrl() { return _scope.ctrl(); } - private Node ctrl(Node n) { return _scope.ctrl(n); } public StopNode parse() { _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); - _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole()); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); - _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); + _scope.define(ScopeNode.CTRL, Type.CONTROL , false, new CProjNode(START, 0, ScopeNode.CTRL).peephole()); + _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, new ProjNode(START, 1, ScopeNode.MEM0).peephole()); + _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); + + // Parse whole program parseBlock(); if( ctrl()._type==Type.CONTROL ) STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole()); _scope.pop(); _xScopes.pop(); + for( StructNode init : INITS.values() ) + init.unkeep().kill(); + INITS.clear(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); STOP.peephole(); return STOP; @@ -210,48 +223,6 @@ public class Parser { // to ambiguity else return parseExpressionStatement(); } - - /** - * Parse a struct field. - * <pre> - * type IDENTIFIER ; - * </pre> - */ - private Field parseField() { - Type t = type(); - if( t==null ) - throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); - return require(Field.make(requireId().intern(),ALIAS++,t),";"); - } - - /** - * Parse a struct declaration, and return the following statement. - * Only allowed in top level scope. - * Structs cannot be redefined. - * - * @return The statement following the struct - */ - private Node parseStruct() { - if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); - String typeName = requireId(); - Type t = TYPES.get(typeName); - if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) ) - throw errorSyntax("struct '" + typeName + "' cannot be redefined"); - // Parse a collection of fields - ArrayList<Field> fields = new ArrayList<>(); - require("{"); - while (!peek('}') && !_lexer.isEOF()) { - Field field = parseField(); - if (fields.contains(field)) throw errorSyntax("Field '" + field + "' already defined in struct '" + typeName + "'"); - fields.add(field); - } - require("}"); - // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fields.toArray(new Field[fields.size()])); - TYPES.put(typeName, TypeMemPtr.make(ts)); - return parseStatement(); - } - /** * Parses a while statement * @@ -332,6 +303,8 @@ public class Parser { // At exit the false control is the current control, and // the scope is the exit scope after the exit test. + _xScopes.pop(); + _xScopes.push(exit); return _scope = exit; } @@ -340,15 +313,15 @@ public class Parser { ctrl(XCTRL); // Kill current scope // Prune nested lexical scopes that have depth > than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth - while( cur._idxs.size() > _breakScope._idxs.size() ) + while( cur._lexSize.size() > _breakScope._lexSize.size() ) cur.pop(); // If this is a continue then first time the target is null // So we just use the pruned current scope as the base for the // "continue" - if (toScope == null) + if( toScope == null ) return cur; // toScope is either the break scope, or a scope that was created here - assert toScope._idxs.size() <= _breakScope._idxs.size(); + assert toScope._lexSize.size() <= _breakScope._lexSize.size(); toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -427,43 +400,39 @@ public class Parser { - /** - * Parses an expression statement or a declaration statement where type is a struct - * - * <pre> - * name; // Error - * type name; // Define name with default initial value - * type name = expr; // Define name with given initial value - * name = expr; // Reassign existing - * expr // Something else - * </pre> - * @return an expression {@link Node}, never {@code null} + /** Parse: name [=expr] */ - private Node parseExpressionStatement() { + private Node parseAsgn(Type t) { + boolean isDecl = t!=null; // Having a type is a declaration, missing one is updating a prior name int old = _lexer._position; - Type t = type(); String name = requireId(); Node expr; - if( match(";") ) { // Assign a default value - // No type and no expr is an error + if( peek(';') || peek(',') ) { + // Bare "name" is not allowed if( t==null ) throw errorSyntax("expression"); - expr = new ConstantNode(t.makeInit()).peephole(); - } else if( match("=") ) { // Assign "= expr;" - expr = require(parseExpression(), ";"); - } else { // Neither, so just a normal expression parse + // Does this declaration need an initializer and not getting one? + Type init = t instanceof TypeMemPtr tmp && !tmp._nil + // Must be initialized in the "new" constructor + ? Type.TOP + // Else takes the default + : t.makeInit(); + expr = con(init); + + } else if( !match("=") ) { // Something else _lexer._position = old; - return require(parseExpression(),";"); - } + return null; + } else + expr = parseExpression(); // Defining a new variable vs updating an old one - if( t != null ) { - if( _scope.define(name,t,expr) == null ) - throw error("Redefining name '" + name + "'"); - } else { - if( _scope.lookup(name)==null ) + if( !isDecl ) { // Assigning over an existing name + // Lookup + ScopeNode.Var def = _scope.lookup(name); + if( def==null ) throw error("Undefined name '" + name + "'"); - t = _scope.lookupDeclaredType(name); + t = def._type; // Declared field type } + // Auto-widen int to float if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) expr = new ToFloatNode(expr).peephole(); @@ -476,9 +445,86 @@ public class Parser { // Type is sane if( !e.isa(t) ) throw error("Type " + e.str() + " is not of declared type " + t.str()); - return _scope.update(name,expr); + + if( isDecl ) { + if( !_scope.define(name,t,false,expr) ) + throw error("Redefining name '" + name + "'"); + } else + _scope.update(name,expr); + return expr; } + /** + * Parses an expression statement or a declaration statement where type is a struct + * + * <pre> + * type decl [, decl]*; // Define many names with the same type + * asgn; // Assign or load a variable + * expr; // Something else + * name; // Bare name is an error + + * </pre> + * @return an expression {@link Node}, never {@code null} + */ + private Node parseExpressionStatement() { + Node n; + Type t = type(); + if( t != null ) { + // Parse comma-separated declarations + n = parseAsgn(t); + while( match(",") ) + n = parseAsgn(t); + + // Parse "asgn;" which is just "name = expr;" + } else if( ( n = parseAsgn(null)) == null ) { + // Something else + n = parseExpression(); + } + return require(n,";"); + } + + + /** + * Parse a struct declaration, and return the following statement. + * Only allowed in top level scope. + * Structs cannot be redefined. + * + * @return The statement following the struct + */ + private Node parseStruct() { + if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); + String typeName = requireId(); + Type t = TYPES.get(typeName); + if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) ) + throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + + // A Block scope parse, and inspect the scope afterward for fields. + _scope.push(); + require("{"); + while (!peek('}') && !_lexer.isEOF()) + parseStatement(); + + // Grab the declarations and build fields and a Struct + int lexlen = _scope._lexSize.last(); + int varlen = _scope._vars._len; + StructNode s = new StructNode(); + Field[] fs = new Field[varlen-lexlen]; + for( int i=lexlen; i<varlen; i++ ) { + s.addDef(_scope.in(i)); + ScopeNode.Var v = _scope._vars.at(i); + fs[i-lexlen] = Field.make(v._name,v._type,ALIAS++,v._final); + } + TypeStruct ts = s._ts = TypeStruct.make(typeName, fs); + TYPES.put(typeName, TypeMemPtr.make(ts)); + INITS.put(typeName,s.peephole().keep()); + // Done with struct/block scope + require("}"); + require(";"); + _scope.pop(); + return null; + } + + // Parse and return a type or null. Valid types always are followed by an // 'id' which the caller must parse. This lets us distinguish forward ref // types (which ARE valid here) from local vars in an (optional) forward @@ -527,11 +573,12 @@ public class Parser { private TypeMemPtr typeAry( Type t ) { if( t instanceof TypeMemPtr tmp && !tmp._nil ) throw error("Arrays of reference types must always be nullable"); - String tname = t.str()+"[]"; + String tname = "["+t.str()+"]"; Type ta = TYPES.get(tname); if( ta != null ) return (TypeMemPtr)ta; // Need make an array type. TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); + assert ts.str().equals(tname); TypeMemPtr tary = TypeMemPtr.make(ts); TYPES.put(tname,tary); return tary; @@ -691,50 +738,89 @@ public class Parser { if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; - if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); - if( matchx("new") ) { - Type t = type(); - if( t==null ) throw error("Expected a type"); - if( match("[") ) { - Node len = parseExpression().keep(); - if( !(len._type instanceof TypeInteger) ) - throw error("Cannot allocate an array with length "+len._type); - require("]"); - TypeMemPtr tmp = typeAry(t); - return newArray(tmp._obj,len); - } - if( t instanceof TypeMemPtr tmp ) { - TypeStruct obj = tmp._obj; - if( obj._fields==null ) - throw error("Unknown struct type '" + obj._name + "'"); - if( obj.isAry() ) - throw Utils.TODO(); // Missing array length - return newStruct(obj,con(obj.offset(obj._fields.length))); - } - throw error("Cannot allocate a "+t.str()); - } + if( matchx("null" ) ) return con(TypeMemPtr.NULLPTR); + if( matchx("new" ) ) return alloc(); + // Expect an identifier now String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); - Node n = _scope.lookup(name); - if( n!=null ) return n; + ScopeNode.Var n = _scope.lookup(name); + if( n!=null ) return _scope.in(n); throw error("Undefined name '" + name + "'"); } /** - * Return a NewNode with pre-zeroed memory + Parse an allocation + */ + private Node alloc() { + Type t = type(); + if( t==null ) throw error("Expected a type"); + // Parse ary[ length_expr ] + if( match("[") ) { + Node len = parseExpression().keep(); + if( !(len._type instanceof TypeInteger) ) + throw error("Cannot allocate an array with length "+len._type); + require("]"); + TypeMemPtr tmp = typeAry(t); + return newArray(tmp._obj,len); + } + + if( !(t instanceof TypeMemPtr tmp) ) + throw error("Cannot allocate a "+t.str()); + + // Parse new struct { default_initialization } + StructNode s = INITS.get(tmp._obj._name); + if( s==null ) throw error("Unknown struct type '" + tmp._obj._name + "'"); + + Field[] fs = s._ts._fields; + // if the object is fully initialized, we can skip a block here. + // Check for constructor block: + boolean hasConstructor = match("{"); + Ary<Node> init=s._inputs; int idx=0; + if( hasConstructor ) { + idx = _scope.nIns(); + // Push a scope, and pre-assign all struct fields. + _scope.push(); + for( int i=0; i<fs.length; i++ ) + _scope.define(fs[i]._fname, fs[i]._type, fs[i]._final, s.in(i)); + // Parse the constructor body + parseBlock(); + require("}"); + init = _scope._inputs; + } + // Check that all fields are initialized + for( int i=idx; i<init.size(); i++ ) + if( init.get(i)._type == Type.TOP ) + throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor"); + Node ptr = newStruct(tmp._obj, con(tmp._obj.offset(fs.length)), idx, init ); + if( hasConstructor ) + _scope.pop(); + return ptr; + } + + + /** + * Return a NewNode initialized memory. + * @param obj is the declared type, with GLB fields + * @param init is a collection of initialized fields */ - private Node newStruct(TypeStruct obj, Node size) { + private Node newStruct( TypeStruct obj, Node size, int idx, Ary<Node> init ) { + Field[] fs = obj._fields; + if( fs==null ) + throw error("Unknown struct type '" + obj._name + "'"); Node prior = mem().keep(); - // No default: only the aliases initialized by this allocation. MemMergeNode input = new MemMergeNode(null); - for( Field f : obj._fields ) - input.alias(f._alias,prior); - Node nnn = new NewNode(TypeMemPtr.make(obj),ctrl(),input.peephole(),size).peephole().keep(); + for( Field f : fs ) input.alias(f._alias,prior); + // Constructor values follow control, memory, and allocation size. + Node[] ns = new Node[3+fs.length]; + ns[0] = ctrl(); + ns[1] = input.peephole(); + ns[2] = size; + for( int i=0; i<fs.length; i++ ) ns[3+i] = init.get(idx+i); + Node nnn = new NewNode(TypeMemPtr.make(obj),ns).peephole().keep(); Node ptr = new ProjNode(nnn,0,obj._name).peephole().keep(); Node out = new ProjNode(nnn,1,"$mem").peephole().keep(); MemMergeNode after = new MemMergeNode(prior); - for( Field f : obj._fields ) - after.alias(f._alias,out); + for( Field f : fs ) after.alias(f._alias,out); mem(after.peephole()); out.unkeep(); nnn.unkeep(); @@ -742,19 +828,20 @@ public class Parser { return ptr.unkeep(); } + private static final Ary<Node> ALTMP = new Ary<>(Node.class); private Node newArray(TypeStruct ary, Node len) { int base = ary.aryBase (); int scale= ary.aryScale(); Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole(); - Node ptr = newStruct(ary,size); - int alias = ary._fields[0]._alias; // Length alias - store("#",alias,TypeInteger.BOT,ptr,con(ary.offset(0)),len.unkeep(),true,null); + ALTMP.clear(); ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit())); + Node ptr = newStruct(ary,size,0,ALTMP); + len.unkeep(); return ptr; } // Memory is one hidden SSA variable, including across branches and loops. - private Node mem() { return _scope.lookup("$mem"); } - private Node mem(Node n) { return _scope.update("$mem",n); } + private Node mem() { return _scope.mem(); } + 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) { Node prior = mem().keep(); @@ -785,48 +872,45 @@ public class Parser { // Sanity check expr for being a reference if( !(expr._type instanceof TypeMemPtr ptr) ) throw error("Expected reference but got " + expr._type.str()); - if( ptr == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); - if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + + // Happens when parsing known dead code, which often has other typing + // issues. Since the code is dead, possibly due to inlining, lets not + // spoil the user experience with error messages. + if( ctrl()._type==Type.XCONTROL ) + // Exit out via parsing the trailing expression + return matchOpx('=','=') ? parseExpression() : parsePostfix(con(Type.TOP)); + // 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.str() + "'"); TypeStruct base = tmp._obj; int fidx = base.find(name); if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - expr.keep(); // Get field type and layout offset from base type and field index fidx Field f = base._fields[fidx]; // Field from field index - Node off; - if( name.equals("[]") ) { // If field is an array body - // Array index math - Node idx = require(parseExpression(),"]"); - Node shl = new ShlNode(idx,con(base.aryScale())).peephole(); - off = new AddNode(con(base.aryBase()),shl).peephole(); - } else { // Else normal struct field - // Hardwired field offset - off = con(base.offset(fidx)); - } - if( match("=") ) { - // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment - if( peek('=') ) _lexer._position--; - else { - off.keep(); - Node val = parseExpression(); - // Auto-truncate when storing to narrow fields - val = zsMask(val,f._type).keep(); - // Array control stands in for the future bounds check. - store(name,f._alias,f._type,expr.unkeep(),off.unkeep(),val,false,base.isAry() ? ctrl() : null); - return val.unkeep(); // "obj.a = expr" returns the expression while updating memory - } + expr.keep(); + Node off = name.equals("[]") // If field is an array body + // Array index math + ? new AddNode(con(base.aryBase()),new ShlNode(require(parseExpression(),"]"),con(base.aryScale())).peephole()).peephole() + // Struct field offsets are hardwired + : con(base.offset(fidx)); + + // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment + if( matchOpx('=','=') ) { + off.keep(); + Node val = zsMask(parseExpression(),f._type).keep(); + // Array control stands in for the future bounds check. + store(name,f._alias,f._type,expr.unkeep(),off.unkeep(),val,false,base.isAry() ? ctrl() : null); + return val.unkeep(); } Node load = new LoadNode(name, f._alias, f._type.glb(), mem(), expr.unkeep(), off); // Arrays include control, as a proxy for a safety range check // Structs don't need this; they only need a NPE check which is // done via the type system. - if( base.isAry() ) load.setDef(0,ctrl()); + //if( base.isAry() ) load.setDef(0,ctrl()); return parsePostfix(load.peephole()); } @@ -859,13 +943,9 @@ public class Parser { * floatLiteral: [digits].[digits]?[e [digits]]? * </pre> */ - private ConstantNode parseLiteral() { - return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); - } - - public static Node con( long con ) { - return new ConstantNode(TypeInteger.constant(con)).peephole(); - } + private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); } + public static Node con( long con ) { return con(TypeInteger.constant(con)); } + public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole(); } ////////////////////////////////// // Utilities for lexical analysis @@ -874,6 +954,7 @@ public class Parser { private boolean match (String syntax) { return _lexer.match (syntax); } // Match must be "exact", not be followed by more id letters private boolean matchx(String syntax) { return _lexer.matchx(syntax); } + private boolean matchOpx(char c0, char c1) { return _lexer.matchOpx(c0,c1); } // Return true and do NOT skip if 'ch' is next private boolean peek(char ch) { return _lexer.peek(ch); } private boolean peekIsId() { return _lexer.peekIsId(); } @@ -993,6 +1074,13 @@ public class Parser { _position -= syntax.length(); return false; } + boolean matchOpx(char c0, char c1) { + skipWhiteSpace(); + if( _position+1 >= _input.length || _input[_position]!=c0 || _input[_position+1]==c1 ) + return false; + _position++; + return true; + } private boolean peek(char ch) { skipWhiteSpace(); diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index 1f223bcb..bd03d6cb 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -14,8 +14,11 @@ public class AndNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()&i1.value()); // Sharpen allowed bits if either value is narrowed diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 70340f7f..f21894dc 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -38,8 +38,8 @@ public class IfNode extends CFGNode implements MultiNode { return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable - if (t instanceof TypeInteger ti && ti.isConstant()) - return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + if( t.isConstant() ) + return t.makeInit()==t ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index b0517a4c..8d604b28 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -2,9 +2,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.*; import java.util.BitSet; import java.util.ArrayList; @@ -74,8 +74,8 @@ public class LoadNode extends MemOpNode { // 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 new ConstantNode(_declaredType.makeInit()); + ptr == nnn.proj(0) ) // Must check same object + return 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. @@ -98,12 +98,12 @@ public class LoadNode extends MemOpNode { // Pointers cannot overlap mem = st.mem(); // Proved never equal break; - case PhiNode phi: - break outer; // Assume related + case PhiNode phi: break outer; // Assume related + case ConstantNode top: break outer; // Assume shortly dead case ProjNode mproj: if( mproj.in(0) instanceof NewNode nnn1 ) { if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) - return new ConstantNode(_declaredType.makeInit()); // Load from a New + return nnn1.in(nnn1.findAlias(_alias)); // Load from New init if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) break outer; // Cannot tell, ptr not related to New mem = nnn1.mem();// Bypass unrelated New @@ -148,7 +148,6 @@ public class LoadNode extends MemOpNode { ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode; } - // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index a4b105c9..faf456de 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -30,7 +30,7 @@ public class MemMergeNode extends Node { setDef(alias,mem); } - // Scalar contents of one alias. New's struct supplies the initialized type; + // Scalar contents of one alias. New's field inputs supply the initialized type; // join it with the incoming contents for all previously allocated objects. // Phis use their cached types, so this query does not recurse around loops. static Type contents(Node mem, int alias, Node dep) { @@ -40,7 +40,8 @@ public class MemMergeNode extends Node { if( mem instanceof ProjNode proj && proj.in(0) instanceof NewNode nnn ) { assert proj._idx==1 && nnn.field(alias)!=null; nnn.addDep(dep); - return contents(nnn.mem(),alias,dep).meet(nnn.field(alias)._type.makeInit()); + Node init = nnn.in(nnn.findAlias(alias)).addDep(dep); + return contents(nnn.mem(),alias,dep).meet(init._type); } // There are no heap arguments in this chapter. Before the first New, // the set of allocated objects (and hence stored values) is empty. diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index b403c2bf..a9ac07e6 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -19,6 +19,8 @@ public class MulNode extends Node { return TypeInteger.TOP; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { + if( i1==TypeInteger.ZERO || i2==TypeInteger.ZERO) + return TypeInteger.ZERO; if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()*i2.value()); } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index f92d3cdf..51341c41 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -4,19 +4,22 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; -/** Allocate and zero an object. Inputs {ctrl, $mem, size}; results {ptr, $mem}. +/** Allocate and initialize an object. Inputs {ctrl, $mem, size, fields...}; + * results {ptr, $mem}. * The memory input and result cover only the aliases in the allocated struct. */ public class NewNode extends Node implements MultiNode { public final TypeMemPtr _ptr; - public NewNode(TypeMemPtr ptr, Node ctrl, Node mem, Node size) { - super(ctrl,mem,size); - assert ctrl._type==Type.CONTROL || ctrl._type==Type.XCONTROL; - assert mem._type instanceof TypeMem; - assert size._type instanceof TypeInteger; + public NewNode(TypeMemPtr ptr, Node... nodes) { + super(nodes); _ptr = ptr; + assert nodes.length==3+ptr._obj._fields.length; + assert nodes[0]._type==Type.CONTROL || nodes[0]._type==Type.XCONTROL; + assert nodes[1]._type instanceof TypeMem; + assert nodes[2]._type instanceof TypeInteger; + for( int i=3; i<nodes.length; i++ ) assert nodes[i]._type!=null; } public Node mem() { return in(1); } @@ -29,13 +32,18 @@ public class NewNode extends Node implements MultiNode { } @Override public String label() { - return "new_" + (_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str()); + return "new_"+(_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str()); } - @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("new ").p(_ptr._obj.str()); } + // Find matching alias input + int findAlias(int alias) { + return 3+_ptr._obj.findAlias(alias); + } + + @Override public TypeTuple compute() { return TypeTuple.make(_ptr,TypeMem.BOT); diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 541c8eb1..fa25b58a 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -4,12 +4,12 @@ import com.seaofnodes.print.BaseNode; import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; - import java.util.*; import java.util.function.Function; @@ -25,9 +25,9 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * <p> * Generally fixed length, ordered, nulls allowed, no unused trailing space. * Ordering is required because e.g. "a/b" is different from "b/a". - * The first input (offset 0) is often a {@link #isCFG} node. + * The first input (offset 0) is often a {@link CFGNode} node. */ - public ArrayList<Node> _inputs; + public Ary<Node> _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -38,7 +38,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public ArrayList<Node> _outputs; + public Ary<Node> _outputs; /** * Current computed type for this Node. This value changes as the graph @@ -56,9 +56,9 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable protected Node(Node... inputs) { super(UNIQUE_ID++); // allocate unique dense ID - _inputs = new ArrayList<>(); + _inputs = new Ary<>(Node.class); Collections.addAll(_inputs,inputs); - _outputs = new ArrayList<>(); + _outputs = new Ary<>(Node.class); for( Node n : _inputs ) if( n != null ) n.addUse( this ); @@ -84,7 +84,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } - @Override public ArrayList<Node> outs() { return _outputs; } + @Override public Ary<Node> outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -125,7 +125,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def moveDepsToWorklist(); - // Return self for easy flow-coding + // Return new_def for easy flow-coding return new_def; } @@ -136,13 +136,19 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable Node delDef(int idx) { unlock(); Node old_def = in(idx); - Utils.del(_inputs, idx); + _inputs.del(idx); if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def old_def.moveDepsToWorklist(); return this; } + // Insert the numbered input, sliding other inputs to the right + Node insertDef(int idx, Node new_def) { + _inputs.add(idx,null); + return setDef(idx,new_def); + } + /** * Add a new def to an existing Node. Keep the edges correct by * adding the corresponding <em>def->use</em> edge. @@ -167,17 +173,17 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { - Utils.del(_outputs, Utils.find(_outputs, use)); + _outputs.del(_outputs.find(use)); moveDepsToWorklist(); // User-count and anti-dependence queries can now change. return _outputs.isEmpty(); } - // Shortcut for "popping" n nodes. A "pop" is basically a + // Shortcut for "popping" until n nodes. A "pop" is basically a // setDef(last,null) followed by lowering the nIns() count. - void popN(int n) { + void popUntil(int n) { unlock(); - for( int i=0; i<n; i++ ) { - Node old_def = _inputs.removeLast(); + while( nIns() > n ) { + Node old_def = _inputs.pop(); if( old_def != null && // If it exists and old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -214,7 +220,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable // Remove bogus null. public <N extends Node> N unkeep() { delUse(null); return (N)this; } // Test "keep" status - public boolean iskeep() { return Utils.find(_outputs,null) != -1; } + public boolean iskeep() { return _outputs.find(null) != -1; } // Replace self with nnn in the graph, making 'this' go dead public void subsume( Node nnn ) { @@ -222,7 +228,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable while( nOuts() > 0 ) { Node n = _outputs.removeLast(); n.unlock(); - int idx = Utils.find(n._inputs, this); + int idx = n._inputs.find(this); n._inputs.set(idx,nnn); n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); @@ -398,7 +404,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable // on a node some distance away, and if that node ever changes we should // retry the peephole. Track a set of Nodes dependent on `this`, and // revisit them if `this` changes. - ArrayList<Node> _deps; + Ary<Node> _deps; public int nDeps() { return _deps == null ? 0 : _deps.size(); } public Node dep(int idx) { return _deps.get(idx); } @@ -421,10 +427,10 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable if( IterPeeps.midAssert() ) return this; var obs = IterPeeps.midAssert() ? null : Parser.PARSER == null ? null : Parser.PARSER._obs; if( obs != null ) obs.dep(this, dep); - if( _deps==null ) _deps = new ArrayList<>(); - if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list - if( !forwards && Utils.find(_inputs,dep) != -1 ) return this; - if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this; + if( _deps==null ) _deps = new Ary<>(Node.class); + if( _deps .find(dep) != -1 ) return this; // Already on list + if( !forwards && _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors + if( !forwards && _outputs.find(dep) != -1 ) return this; _deps.add(dep); return this; } @@ -554,8 +560,8 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable try { n = (Node)clone(); } catch( CloneNotSupportedException e ) { throw new AssertionError(e); } n._nid = UNIQUE_ID++; - n._inputs = new ArrayList<>(); - n._outputs = new ArrayList<>(); + n._inputs = new Ary<>(Node.class); + n._outputs = new Ary<>(Node.class); n._deps = null; n._hash = 0; return n; diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index 2e89f013..e388f4a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -16,7 +16,7 @@ public class NotNode extends Node { Type t0 = in(1)._type; if( t0.isHigh() ) return TypeInteger.BOOL.dual(); switch( t0 ) { - case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOT); + case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOOL); case TypeFloat i0: return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : TypeInteger.BOT; case TypeMemPtr p0: diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index 5badd015..5be31b88 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -14,8 +14,11 @@ public class OrNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()|i1.value()); } diff --git a/src/main/java/com/seaofnodes/simple/node/OutNode.java b/src/main/java/com/seaofnodes/simple/node/OutNode.java index 7e531145..dbac136b 100644 --- a/src/main/java/com/seaofnodes/simple/node/OutNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OutNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import java.util.ArrayList; +import com.seaofnodes.simple.Ary; public interface OutNode { - ArrayList<Node> outs(); + Ary<Node> outs(); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index ea5eeb89..8479b4dc 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -39,7 +39,7 @@ public class PhiNode extends Node { @Override public Type compute() { if( !(region() instanceof RegionNode r) ) - return region()._type==Type.XCONTROL ? Type.TOP : _type; + return region()._type==Type.XCONTROL ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. if( r.inProgress() ) return _declaredType; // Set type to local top of the starting type diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d4f73ddf..08f48a08 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -103,7 +103,7 @@ public class RegionNode extends CFGNode { // A walk that can be cutoff early private static final BitSet VISIT = new BitSet(); - private static boolean walk( IfNode iff, CProjNode cproj, Node n ) { + private boolean walk( IfNode iff, CProjNode cproj, Node n ) { if( VISIT.get(n._nid) ) return false; VISIT.set(n._nid); if( n instanceof CFGNode ) return false; @@ -111,6 +111,7 @@ public class RegionNode extends CFGNode { return false; boolean progress = false; Node pred = iff.pred(); + if( pred._type.isHighOrConst() ) return false; // This will collapse the IF already for( int i=1; i<n.nIns(); i++ ) { // Using a tested value if( n.in(i) == pred && !(n instanceof CastNode) ) { @@ -122,7 +123,7 @@ public class RegionNode extends CFGNode { n.setDef( i, cast ); IterPeeps.add(n); progress = true; - } + } else pred.addDep( this ); } if( n.in(i)!=null ) progress |= walk(iff,cproj,n.in(i)); diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 161cc7d6..eff33954 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -10,7 +10,7 @@ public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { // A synthetic never-taken loop exit has no source scope. - super(ctrl, scope == null ? null : scope.lookup("$mem"), data); + super(ctrl, scope == null ? null : scope.mem(), data); } public Node ctrl() { return in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index 65151598..44233b3d 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -14,8 +14,13 @@ public class SarNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1) { + if( i0 == TypeInteger.ZERO ) + return TypeInteger.ZERO; if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()>>i1.value()); if( i1.isConstant() ) { diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 36a5060b..84937ad7 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -3,14 +3,13 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.type.*; import java.util.*; /** * The Scope node is purely a parser helper - it tracks names to nodes with a - * stack of scopes. + * stack of variable records. */ public class ScopeNode extends Node { @@ -20,43 +19,68 @@ public class ScopeNode extends Node { */ public static final String CTRL = "$ctrl"; public static final String ARG0 = "arg"; + public static final String MEM0 = "$mem"; - /** - * Map variable names to Scope input edge + /** The tracked fields are now complex enough to deserve an array-of-structs layout */ - public final Stack<HashMap<String, Integer>> _idxs; + public static class Var { + public final int _idx; + public final String _name; + public final Type _type; + public final boolean _final; + public Var(int idx, String name, Type type, boolean xfinal) { + _idx = idx; + _name = name; + _type = type; + _final = xfinal; + } + } + + public Node in(Var v) { return in(v._idx); } + + @Override public Type compute() { return Type.BOTTOM; } + @Override public Node idealize() { return null; } + + // All active/live variables in all nested scopes, all run together + public final Ary<Var> _vars; + + // Size of each nested lexical scope + public final Ary<Integer> _lexSize; - /** - * Map variable names to declared Type - */ - final Stack<HashMap<String, Type>> _decls; // A new ScopeNode - public ScopeNode() { - _idxs = new Stack<>(); - _decls= new Stack<>(); - _type = Type.BOTTOM; - } + public ScopeNode() { _type = Type.BOTTOM; _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } @Override public String label() { return "Scope"; } + @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { p.p("Scope[ "); - String[] names = reverseNames(); - for( int j=0; j<nIns(); j++ ) { - p.p(names[j]).p(":"); - Node n = in(j); + int j=1; + for( int i=0; i<nIns(); i++ ) { + if( j < _lexSize._len && i == _lexSize.at(j) ) { p.p("| "); j++; } + Var v = _vars.get(i); + p.p(v._type); + p.p(" "); + if( v._final ) p.p("!"); + p.p(v._name); + p.p("="); + Node n = in(i); while( n instanceof ScopeNode loop ) { p.p("Lazy_"); - n = loop.in(j); + n = loop.in(i); } - p.n(n).p(" "); + p.n(n); + p.p(", "); } - return p.unchar(' ').p("]"); + return p.unchar(", ").p("]"); } + public Node ctrl() { return in(0); } + public Node mem() { return in(lookup(MEM0)); } + public void mem(Node n) { update(MEM0,n); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -70,91 +94,79 @@ public class ScopeNode extends Node { */ public Node ctrl(Node n) { return setDef(0,n); } - /** - * Recover the names for all variable bindings. - * The result is an array of names that is aligned with the - * inputs to the Node. - * - * This is an expensive operation. - */ - public String[] reverseNames() { - String[] names = new String[nIns()]; - for( HashMap<String,Integer> syms : _idxs ) - for( String name : syms.keySet() ) - names[syms.get(name)] = name; - return names; + public void push() { + _lexSize.push(_vars.size()); + } + public void pop() { + int n = _lexSize.pop(); + popUntil(n); + _vars.setLen(n); } - @Override public Type compute() { return Type.BOTTOM; } - - @Override public Node idealize() { return null; } - - public void push() { _idxs.push(new HashMap<>()); _decls.push(new HashMap<>()); } - public void pop() { popN(_idxs.pop().size()); _decls.pop(); } + // Find name in reverse, return an index into _vars or -1. Linear scan + // instead of hashtable, but probably doesn't matter until the scan + // typically hits many dozens of variables. + int find( String name ) { + for( int i=_vars.size()-1; i>=0; i-- ) + if( _vars.get(i)._name.equals(name) ) + return i; + return -1; + } /** * Create a new variable name in the current scope */ - public Node define( String name, Type declaredType, Node n ) { - HashMap<String,Integer> syms = _idxs.lastElement(); - _decls.lastElement().put(name,declaredType); - if( syms.put(name,nIns()) != null ) - return null; // Double define - return addDef(n); + public boolean define( String name, Type declaredType, boolean xfinal, Node init ) { + assert name.charAt(0)!='$' || _lexSize.size()==1; // Later scopes do not define memory + if( _lexSize._len > 1 ) + for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) + if( _vars.get(i)._name.equals(name) ) + return false; // Double define + _vars.add(new Var(nIns(),name,declaredType,xfinal)); + addDef(init); + return true; } /** * Lookup a name in all scopes starting from most deeply nested. * * @param name Name to be looked up - * @see #update(String, Node, int) + * @return null if not found, or the implementing Node */ - public Node lookup( String name ) { return update(name,null,_idxs.size()-1); } + public Var lookup( String name ) { + int idx = find(name); + // -1 is missed in all scopes, not found + return idx == -1 ? null : _update(_vars.at(idx),null); + } + /** * If the name is present in any scope, then redefine else null * * @param name Name being redefined * @param n The node to bind to the name */ - public Node update( String name, Node n ) { return update(name,n,_idxs.size()-1); } - /** - * Both recursive lookup and update. - * <p> - * A shared implementation allows us to create lazy phis both during - * lookups and updates; the lazy phi creation is part of chapter 8. - * - * @param name Name whose binding is being updated or looked up - * @param n If null, do a lookup, else update binding - * @param nestingLevel The starting nesting level - * @return node being looked up, or the one that was updated - */ - private Node update( String name, Node n, int nestingLevel ) { - if( nestingLevel<0 ) return null; // Missed in all scopes, not found - var syms = _idxs.get(nestingLevel); // Get the symbol table for nesting level - var idx = syms.get(name); - if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope - Node old = in(idx); + public void update( String name, Node n ) { + int idx = find(name); + assert idx>=0; + _update(_vars.at(idx),n); + } + + Var _update( ScopeNode.Var v, Node st ) { + Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! - old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + Node def = loop.in(v._idx); + old = def instanceof PhiNode phi && loop.ctrl()==phi.region() // Loop already has a real Phi, use it - ? loop.in(idx) + ? def // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(idx,PhiNode.make(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); - setDef(idx,old); + : loop.setDef(v._idx,PhiNode.make(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + setDef(v._idx,old); } - return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer - } - - // Return declared type for a variable - public Type lookupDeclaredType( String name ) { - for( int i=_decls.size(); i>0; i-- ) { - Type t = _decls.get(i-1).get(name); - if( t != null ) return t; - } - return null; + if( st!=null ) setDef(v._idx,st); // Set new value + return v; } /** @@ -177,15 +189,12 @@ public class ScopeNode extends Node { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - for( HashMap<String,Integer> syms : _idxs ) - dup._idxs.push(new HashMap<>(syms)); - for( HashMap<String,Type> ts : _decls ) - dup._decls.push(ts); // Types don't change, just keep stacks aligned - + dup._vars.addAll(_vars); + dup._lexSize.addAll(_lexSize); dup.addDef(ctrl()); // Control input is just copied + + // Memory is one binding, with the same lazy loop Phi as scalar names. for( int i=1; i<nIns(); i++ ) - // For lazy phis on loops we use a sentinel - // that will trigger phi creation on update dup.addDef(loop ? this : in(i)); return dup; } @@ -200,35 +209,53 @@ public class ScopeNode extends Node { */ public Node mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); - String[] ns = reverseNames(); - // Note that we skip i==0, which is bound to '$ctrl' - for (int i = 1; i < nIns(); i++) - if( in(i) != that.in(i) ) // No need for redundant Phis - // If we are in lazy phi mode we need to a lookup - // by name as it will trigger a phi creation - setDef(i, PhiNode.make(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + _merge(that,r); that.kill(); // Kill merged scope IterPeeps.add(r); return r.unkeep().peephole(); } - // Merge the backedge scope into this loop head scope + private void _merge(ScopeNode that, RegionNode r) { + for( int i = 1; i < nIns(); i++) + if( in(i) != that.in(i) ) { // No need for redundant Phis + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + Var v = _vars.at(i); + Node lhs = this.in(this._update(v,null)); + Node rhs = that.in(that._update(v,null)); + setDef(i, PhiNode.make(v._name, v._type, r, lhs, rhs).peephole()); + } + } + + // peephole the backedge scope into this loop head scope // We set the second input to the phi from the back edge (i.e. loop body) public void endLoop(ScopeNode back, ScopeNode exit ) { Node ctrl = ctrl(); assert ctrl instanceof LoopNode loop && loop.inProgress(); ctrl.setDef(2,back.ctrl()); + + _endLoop(this,back,exit); + back.kill(); // Loop backedge is dead + // Now one-time do a useless-phi removal + _useless(); + } + + // Fill in the backedge of any inserted Phis + void _endLoop( ScopeNode scope, Node back, Node exit ) { for( int i=1; i<nIns(); i++ ) { - if( back.in(i) != this ) { + if( back.in(i) != scope ) { PhiNode phi = (PhiNode)in(i); - assert phi.region()==ctrl && phi.in(2)==null; - phi.setDef(2,back.in(i)); + assert phi.region()==scope.ctrl() && phi.in(2)==null; + phi.setDef(2,back.in(i)); // Fill backedge } - if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also + if( exit.in(i) == scope ) // Replace a lazy-phi on the exit path also exit.setDef(i,in(i)); } - back.kill(); // Loop backedge is dead - // Now one-time do a useless-phi removal + } + + + // Now one-time do a useless-phi removal + void _useless( ) { for( int i=1; i<nIns(); i++ ) { if( in(i) instanceof PhiNode phi ) { // Do an eager useless-phi removal @@ -242,10 +269,8 @@ public class ScopeNode extends Node { } } } - } - // Up-casting: using the results of an If to improve a value. // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null. @@ -265,7 +290,7 @@ public class ScopeNode extends Node { pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); // Direct use of a value as predicate. This is a zero/null test. - if( Utils.find(_inputs, pred) != -1 ) { + if( _inputs.find(pred) != -1 ) { if( !(pred._type instanceof TypeMemPtr tmp) ) // Must be an `int`, since int and ptr are the only two value types // being tested. No representation for a generic not-null int, so no upcast. @@ -278,7 +303,7 @@ public class ScopeNode extends Node { if( pred instanceof NotNode not ) { // Direct use of a !value as predicate. This is a zero/null test. - if( Utils.find(_inputs, not.in(1)) != -1 ) { + if( _inputs.find(not.in(1)) != -1 ) { Type tinit = not.in(1)._type.makeInit(); if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast return replace(not.in(1), new ConstantNode(tinit).peephole()); diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 278c8390..4d673056 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -14,8 +14,13 @@ public class ShlNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { + if( i0 == TypeInteger.ZERO ) + return TypeInteger.ZERO; if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()<<i1.value()); } @@ -32,7 +37,7 @@ public class ShlNode extends Node { if( (shl.value()&63)==0 ) return lhs; // (x + c) << i => (x << i) + (c << i) - if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() ) { + if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 70fd630d..bc6881f1 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -14,8 +14,13 @@ public class ShrNode extends Node { @Override public Type compute() { - if (in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if (t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { + if( i0 == TypeInteger.ZERO ) + return TypeInteger.ZERO; if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()>>>i1.value()); } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 812305d5..23830a18 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -5,16 +5,14 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; import java.util.BitSet; import java.util.HashSet; +import static com.seaofnodes.simple.Utils.TODO; /** Start supplies control, whole memory, and the argument, in that order. */ public class StartNode extends CFGNode implements MultiNode { - private final TypeTuple _args; + final Type _arg; - public StartNode(Type[] args) { - super(); - _type = _args = TypeTuple.make(args); - } + public StartNode(Type arg) { super(); _arg = arg; _type = compute(); } @Override public String label() { return "Start"; } @@ -26,11 +24,11 @@ public class StartNode extends CFGNode implements MultiNode { @Override public boolean blockHead() { return true; } @Override public CFGNode cfg0() { return this; } - @Override - public TypeTuple compute() { return _args; } + @Override public TypeTuple compute() { + return TypeTuple.make(Type.CONTROL,TypeMem.BOT,_arg); + } - @Override - public Node idealize() { return null; } + @Override public Node idealize() { return null; } // No immediate dominator, and idepth==0 @Override public int idepth() { return 0; } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 485491c0..8eb104a7 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -64,23 +64,48 @@ public class StoreNode extends MemOpNode { ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. - st.checkNoUseBeyond(this) ) { + checkOnlyUse(st) ) { assert _name.equals(st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } + // Simple store-after-new on same address. Should pick up the + // an init-store being stomped by a first user store. + if( mem() instanceof ProjNode st && st .in(0) instanceof NewNode nnn && + ptr() instanceof ProjNode ptr && ptr.in(0) == nnn && + ptr()._type instanceof TypeMemPtr tmp && // No bother if weird dead pointers + // Cannot fold a store of a single element over the array body initializer value + !(tmp._obj.isAry() && tmp._obj._fields[1]._alias==_alias) && + // Very sad strong cutout: val has to be legal to hoist to a New + // input, which means it cannot depend on the New. Many many + // things are legal here but difficult to check without doing a + // full dominator check. Example failure: + // "struct C { C? c; }; C self = new C { c=self; }" + val()._type.isHighOrConst() && + // Must have exactly one use of "this" or you get weird + // non-serializable memory effects in the worse case. + checkOnlyUse(st) && + // Folding away a broken store + err()==null ) { + nnn.setDef(nnn.findAlias(_alias),val()); + // Must retype the NewNode + nnn ._type = nnn. compute(); + mem()._type = mem().compute(); + return st; + } + return null; } - // Check that `this` has no uses beyond `that` - private boolean checkNoUseBeyond(Node that) { - if( nOuts()==1 ) return true; + // Check that "mem" has no uses except "this" + private boolean checkOnlyUse(Node mem) { + if( mem.nOuts()==1 ) return true; // Add deps on the other uses (can be e.g. ScopeNode mid-parse) so that // when the other uses go away we can retry. - for( Node use : _outputs ) - if( use != that ) - use.addDep(that); + for( Node use : mem._outputs ) + if( use != this ) + use.addDep(this); return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/StructNode.java b/src/main/java/com/seaofnodes/simple/node/StructNode.java new file mode 100644 index 00000000..429b49cc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -0,0 +1,45 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; + +import com.seaofnodes.simple.type.*; + +/** + * Build a compound object + */ +public class StructNode extends Node { + + public TypeStruct _ts; + + @Override public String label() { return _ts==null ? "STRUCT?" : _ts.str(); } + + @Override + protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { + if( _ts==null ) return p.p("STRUCT?"); + p.p(_ts._name).p(" {"); + for( int i=0; i<nIns(); i++ ) { + p.p(_ts._fields[i]._fname).p(":"); + p.p(in(i)==null ? Type.BOTTOM : in(i)._type); + p.p("; "); + } + return p.unchar("; ").p("}"); + } + + @Override + public TypeStruct compute() { + if( _ts==null ) return TypeStruct.BOT; + Field[] fs = new Field[_ts._fields.length]; + for( int i=0; i<fs.length; i++ ) + fs[i] = _ts._fields[i].makeFrom(in(i)==null ? Type.TOP : in(i)._type); + return TypeStruct.make(_ts._name,fs); + } + + @Override + public Node idealize() { return null; } + + @Override + boolean eq(Node n) { return _ts == ((StructNode)n)._ts; } + + @Override + int hash() { return _ts==null ? 0 : _ts.hashCode(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index 0521cc52..ef7273b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -14,8 +14,11 @@ public class XorNode extends Node { @Override public Type compute() { - if( in(1)._type instanceof TypeInteger i0 && - in(2)._type instanceof TypeInteger i1 ) { + Type t1 = in(1)._type, t2 = in(2)._type; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; + if( t1 instanceof TypeInteger i0 && + t2 instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) return TypeInteger.constant(i0.value()^i1.value()); } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index e2bf366d..d023e1e7 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,11 +6,12 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 15's view of the IR; browser, transport and layout are shared. */ +/** Chapter 16's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { - @Override protected String[] edgeNames(Node n) { - return n instanceof ScopeNode scope && n.nIns()!=0 ? scope.reverseNames() : null; + @Override protected String edgeName(Node n, int i) { + return n instanceof ScopeNode scope && i < scope._vars.size() + ? scope._vars.get(i)._name : null; } @Override protected int projectionIndex(Node n) { return n instanceof ProjNode p ? p._idx : n instanceof CProjNode p ? p._idx : -1; } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 450922d7..0d6fce44 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 15's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 16's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index 5e674132..e2c0aa59 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -12,52 +12,59 @@ public class Field extends Type { // Field name public final String _fname; - // Unique memory alias - public final int _alias; // Type of the field public final Type _type; + // Unique memory alias, not sensibly part of a "type" but very convenient here. + public final int _alias; + // Field must be written to exactly once, no more, no less + public final boolean _final; - private Field(String fname, int alias, Type type ) { + private Field(String fname, Type type, int alias, boolean xfinal ) { super(TFLD); _fname = fname; - _alias = alias; _type = type; + _alias = alias; + _final = xfinal; } // Make with existing alias - public static Field make( String fname, int alias, Type type ) { - return new Field(fname,alias,type).intern(); + public static Field make( String fname, Type type, int alias, boolean xfinal ) { + return new Field(fname,type,alias,xfinal).intern(); + } + public Field makeFrom( Type type ) { + return new Field(_fname,type,_alias,_final).intern(); } - public static final Field TEST = make("test",-2,TypeInteger.ZERO); + public static final Field TEST = make("test",TypeInteger.ZERO,-2,false); public static void gather(ArrayList<Type> ts) { ts.add(TEST); } @Override Field xmeet( Type that ) { Field fld = (Field)that; // Invariant assert _fname.equals(fld._fname); assert _alias==fld._alias; - return make(_fname,_alias,_type.meet(fld._type)); + assert _final==fld._final; + return make(_fname,_type.meet(fld._type),_alias,_final); } @Override - public Field dual() { return make(_fname,_alias,_type.dual()); } + public Field dual() { return make(_fname,_type.dual(),_alias,_final); } @Override public Field glb() { - return make(_fname,_alias,_type.glb()); + return make(_fname,_type.glb(),_alias,_final); } // Override in subclasses - int hash() { return _fname.hashCode() ^ _type.hashCode() ^ _alias; } + int hash() { return _fname.hashCode() ^ _type.hashCode() ^ _alias ^ (_final ? 1024 : 0); } boolean eq(Type t) { Field f = (Field)t; - return _fname.equals(f._fname) && _alias==f._alias && _type==f._type; + return _fname.equals(f._fname) && _type==f._type && _alias==f._alias && _final==f._final; } @Override public StringBuilder print( StringBuilder sb ) { - return _type.print(sb.append(_fname).append(":").append(_alias).append(" : ")); + return _type.print(sb.append(_final?"!":"").append(_fname).append(":").append(_alias).append(" : ")); } @Override public String str() { return _fname; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 042b4ba8..b475055d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -117,7 +117,7 @@ public class TypeInteger extends Type { @Override public TypeInteger makeInit() { return ZERO; } @Override public TypeInteger nonZero() { if( isHigh() ) return this; - if( _min==0 ) return make(1,_max); // specifically good on BOOL + if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL if( _max==0 ) return make(_min,-1); return this; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index ceba733d..9b628bea 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -61,6 +61,8 @@ public class TypeMemPtr extends Type { @Override public Type nonZero() { return VOIDPTR; } @Override public boolean isHigh() { return this==TOP; } + @Override public boolean isConstant() { return this==NULLPTR; } + @Override public boolean isHighOrConst() { return this==TOP || this==NULLPTR; } @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 922b7914..75f24c03 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -41,21 +41,22 @@ public class TypeStruct extends Type { // Array public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { assert !(body instanceof TypeMemPtr tmp && !tmp._nil); - return make(body.str() + "[]", - Field.make("#" , lenAlias,len ), - Field.make("[]",bodyAlias,body)); + return make("[" + body.str() + "]", + Field.make("#" ,len , lenAlias,true), + Field.make("[]",body,bodyAlias,true)); } // A pair of self-cyclic types private static final TypeStruct S1F = make("S1"); private static final TypeStruct S2F = make("S2"); - public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", -1, TypeInteger.BOT), Field.make("s2",-2,TypeMemPtr.make(S2F,false)) }); - private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", -3, TypeFloat .BOT), Field.make("s1",-4,TypeMemPtr.make(S1F,false)) }); + public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) }); private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeFloat.BOT,-2); public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); } + // Find field index by name public int find(String fname) { for( int i=0; i<_fields.length; i++ ) if( _fields[i]._fname.equals(fname) ) @@ -63,6 +64,15 @@ public class TypeStruct extends Type { return -1; } + // Find field index by alias + public int findAlias( int alias ) { + for( int i=0; i<_fields.length; i++ ) + if( _fields[i]._alias==alias ) + return i; + return -1; + } + + @Override Type xmeet(Type t) { TypeStruct that = (TypeStruct) t; @@ -152,10 +162,10 @@ public class TypeStruct extends Type { if( this==TOP ) return sb.append("StructTop"); sb.append(_name); if( _fields == null ) return sb; // Forward reference struct, just print the name - sb.append(" {\n"); + sb.append(" {"); for( Field f : _fields ) { sb.append(" ").append(f._fname).append(" :"); - f._type.print(sb).append(";\n"); + f._type.print(sb).append("; "); } return sb.append("}"); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 59ddf34b..a34c64db 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -7,15 +7,17 @@ public class TypeTuple extends Type { public final Type[] _types; private TypeTuple(Type[] types) { super(TTUPLE); _types = types; } - public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); } + public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); } - private static TypeTuple TEST = make(TypeInteger.BOT,TypeMemPtr.TEST); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); } + private static final TypeTuple TEST = make(TypeInteger.BOT,TypeMemPtr.TEST); + public static final TypeTuple START = make(Type.CONTROL,TypeMem.TOP,TypeInteger.BOT); + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(START); } @Override Type xmeet(Type other) { TypeTuple tt = (TypeTuple)other; // contract from xmeet - assert _types.length == tt._types.length; + if( _types.length != tt._types.length ) + return BOTTOM; Type[] ts = new Type[_types.length]; for( int i=0; i<_types.length; i++ ) ts[i] = _types[i].meet(tt._types[i]); diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index a5e3a9e0..0b8be64b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,10 +1,7 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.StopNode; -import com.seaofnodes.simple.node.LoadNode; -import com.seaofnodes.simple.node.StoreNode; import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.*; import java.util.BitSet; import org.junit.Test; import static org.junit.Assert.assertEquals; @@ -29,9 +26,7 @@ public class Chapter10Test { private static final String NULLABLE_POINT_SOURCE = """ struct Point { int x; }; Point?[] points = new Point?[2]; - Point point = new Point; - point.x = 42; - points[arg] = point; + points[arg] = new Point { x = 42; }; Point? p = points[1]; """; @@ -101,10 +96,10 @@ return p-r; struct Bar { int a; int b; -} +}; struct Foo { int x; -} +}; Foo? foo = null; Bar bar = new Bar; bar.a = 1; @@ -118,7 +113,7 @@ return bar.a; @Test public void testExample() { Parser parser = new Parser(""" -struct Vector2D { int x; int y; } +struct Vector2D { int x; int y; }; Vector2D v = new Vector2D; v.x = 1; if (arg) @@ -136,7 +131,7 @@ return v; Parser parser = new Parser(""" struct s0 { int v0; -} +}; s0? v1=null; int v3=v1.zAicm; """); @@ -147,7 +142,7 @@ int v3=v1.zAicm; @Test public void testBug2() { Parser parser = new Parser(""" -struct s0 { int v0; } +struct s0 { int v0; }; arg=0+new s0.0; """); try { parser.parse(); fail(); } @@ -157,7 +152,7 @@ arg=0+new s0.0; @Test public void testLoop() { Parser parser = new Parser(""" -struct Bar { int a; } +struct Bar { int a; }; Bar bar = new Bar; while (arg) { bar.a = bar.a + 2; @@ -166,13 +161,13 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop17,0,(Phi_a+2));", stop.toString()); } @Test public void testIf() { Parser parser = new Parser(""" -struct Bar { int a; } +struct Bar { int a; }; Bar bar = new Bar; if (arg) bar = null; bar.a = 1; @@ -185,7 +180,7 @@ return bar.a; @Test public void testIf2() { Parser parser = new Parser(""" -struct Bar { int a; } +struct Bar { int a; }; Bar? bar = null; if (arg) bar = new Bar; bar.a = 1; @@ -198,7 +193,7 @@ return bar.a; @Test public void testIf3() { Parser parser = new Parser(""" -struct Bar { int a; } +struct Bar { int a; }; Bar bar = null; if (arg) bar = null; bar.a = 1; @@ -211,21 +206,21 @@ return bar.a; @Test public void testIfOrNull() { Parser parser = new Parser(""" -struct Bar { int a; } +struct Bar { int a; }; Bar? bar = new Bar; if (arg) bar = null; if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region36,(*void)Phi(Region22,null,Bar),null);", stop.toString()); + assertEquals("return Phi(Region38,(*void)Phi(Region24,null,Bar),null);", stop.toString()); } @Test public void testIfOrNull2() { Parser parser = new Parser( """ -struct Bar { int a; } +struct Bar { int a; }; Bar? bar = new Bar; if (arg) bar = null; int rez = 3; @@ -234,13 +229,13 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region42,4,3);", stop.toString()); + assertEquals("return Phi(Region44,4,3);", stop.toString()); } @Test public void testWhileWithNullInside() { Parser parser = new Parser(""" -struct s0 {int v0;} +struct s0 {int v0;}; s0? v0 = new s0; int ret = 0; while(arg) { @@ -260,7 +255,7 @@ return ret; Parser parser = new Parser(""" struct s0 { int v0; -} +}; s0? v1=new s0; s0? v1; v1=new s0; @@ -277,7 +272,7 @@ v1=new s0; struct Iter { int x; int len; -} +}; Iter i = new Iter; i.len = arg; int sum=0; @@ -288,16 +283,14 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop19,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop22,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } - - @Test public void test1() { Parser parser = new Parser(""" -struct s0 {int v0;} +struct s0 {int v0;}; s0 ret = new s0; while(arg) { s0 v0 = new s0; @@ -309,13 +302,13 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,s0,Phi(Region42,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop17,s0,Phi(Region44,s0,Phi_ret));", stop.toString()); } @Test public void test2() { Parser parser = new Parser(""" -struct s0 {int v0;} +struct s0 {int v0;}; s0 ret = new s0; s0 v0 = new s0; while(arg) { @@ -327,14 +320,14 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop21,s0,Phi(Region43,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop23,s0,Phi(Region45,s0,Phi_ret));", stop.toString()); } @Test public void test3() { Parser parser = new Parser(""" -struct s0 {int v0;} +struct s0 {int v0;}; s0 ret = new s0; while(arg < 10) { s0 v0 = new s0; @@ -344,21 +337,19 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,s0,Phi(Region39,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop17,s0,Phi(Region41,s0,Phi_ret));", stop.toString()); } @Test public void testBug3() { Parser parser = new Parser(""" -struct s0 { - int f0; -} -if(0>=0) return new s0; +struct s0 { int f0; }; return new s0; int v0=null.f0; """); - try { parser.parse(); fail(); } - catch( Exception e ) { assertEquals("Accessing unknown field 'f0' from 'null'", e.getMessage()); } + StopNode stop = parser.parse().iterate(); + assertEquals("return s0;", stop.toString()); + assertEquals("Obj<s0>{f0=0}", Evaluator.evaluate(stop, 0).toString()); } @Test @@ -382,7 +373,7 @@ if(0) { Parser parser = new Parser(""" struct s0 { int f0; -} +}; if(0) return 0; else return new s0; if(new s0.f0) return 0; @@ -409,7 +400,7 @@ return 0; @Test public void testBug7() { Parser parser = new Parser(""" -struct s0 { int f0; } +struct s0 { int f0; }; s0 v0 = new s0; while(v0.f0) {} s0 v1 = v0; @@ -464,7 +455,7 @@ return 0; @Test public void testReadBeforeStores() { var stop = new Parser(""" - struct S { int x; int y; } + struct S { int x; int y; }; S a = new S; S b = new S; a.x = 11; b.x = 22; S p = a; if (arg) p = b; @@ -478,7 +469,7 @@ return 0; } static final String NESTED_MEMORY = """ - struct S { int x; int y; int z; } + struct S { int x; int y; int z; }; S s = new S; s.x = 5; s.y = 7; s.z = 11; while (arg > 0) { @@ -509,7 +500,7 @@ return 0; @Test public void testMemoryAtEarlyReturns() { var stop = new Parser(""" - struct S { int x; int y; int z; } + struct S { int x; int y; int z; }; S s = new S; s.x = 3; s.y = 5; s.z = 7; if (arg) { s.x = 11; s.z = 13; return s; } @@ -525,7 +516,7 @@ return 0; @Test public void testKeepLoadsAtMerge() { StopNode stop = new Parser(""" - struct S { int x; } + struct S { int x; }; S a = new S; S b = new S; a.x = arg; b.x = arg+1; S p = a; S q = b; @@ -543,7 +534,7 @@ return 0; @Test public void testDropStores() { StopNode stop = new Parser(""" - struct S { int x; } + struct S { int x; }; S s = new S; if (arg) s.x=arg+1; else s.x=arg+2; return s; @@ -555,7 +546,7 @@ return 0; @Test public void testKeepReadsBeforeWrites() { StopNode stop = new Parser(""" - struct S { int x; int y; } + struct S { int x; int y; }; S a = new S; S b = new S; a.x=arg; b.x=arg+1; S p=a; S q=b; diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 5f92c9c1..e009c6b6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -8,7 +8,7 @@ import static org.junit.Assert.*; public class Chapter11Test { @Test public void testIndependentField() { var stop = new Parser(""" - struct S { int x; int y; } + struct S { int x; int y; }; S s = new S; s.x = 42; while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } @@ -21,7 +21,7 @@ public class Chapter11Test { @Test public void testParallelMemoryPhis() { var stop = new Parser(""" - struct S { int x; int y; int z; } + 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) { diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index e885deb3..22976058 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -2,7 +2,6 @@ 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; @@ -23,7 +22,7 @@ return 3.14; public void testLinkedList0() { Parser parser = new Parser( """ -struct LLI { LLI? next; int i; } +struct LLI { LLI? next; int i; }; LLI? head = null; while( arg ) { LLI x = new LLI; @@ -42,7 +41,7 @@ return head.next.i; public void testLinkedList1() { Parser parser = new Parser( """ -struct LLI { LLI? next; int i; } +struct LLI { LLI? next; int i; }; LLI? head = null; while( arg ) { LLI x = new LLI; @@ -65,8 +64,8 @@ return next.i; public void testCoRecur() { Parser parser = new Parser( """ -struct int0 { int i; flt0? f; } -struct flt0 { flt f; int0? i; } +struct int0 { int i; flt0? f; }; +struct flt0 { flt f; int0? i; }; int0 i0 = new int0; i0.i = 17; flt0 f0 = new flt0; @@ -83,7 +82,7 @@ return f0.i.f.i.i; public void testNullRef0() { Parser parser = new Parser( """ -struct N { N next; int i; } +struct N { N? next; int i; }; N n = new N; return n.next; """); @@ -95,33 +94,33 @@ return n.next; public void testNullRef1() { Parser parser = new Parser( """ -struct N { N next; int i; } -N n = new N; -n.next = new N; +struct M { int m; }; +struct N { M next; int i; }; +N n = new N { next = new M; }; return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return N;", stop.toString()); + assertEquals("return M;", stop.toString()); } @Test public void testNullRef2() { Parser parser = new Parser( """ -struct N { N next; int i; } -N n = new N; -n.next = null; +struct M { int m; }; +struct N { M next; int i; }; +N n = new N { next = null; } return n.next; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); } + catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } } @Test public void testNullRef3() { Parser parser = new Parser( """ -struct N { N next; int i; } +struct N { N? next; int i; }; N n = new N; n.i = 3.14; return n.i; @@ -158,7 +157,7 @@ struct S{}; public void testForwardRef0() { Parser parser = new Parser( """ -struct S1 { S2 s; } +struct S1 { S2 s; }; return new S2; """); try { parser.parse().iterate(); fail(); } @@ -169,8 +168,8 @@ return new S2; public void testForwardRef1() { Parser parser = new Parser( """ -struct S1 { S2? s; } -struct S2 { int x; } +struct S1 { S2? s; }; +struct S2 { int x; }; return new S1.s=new S2; """); StopNode stop = parser.parse().iterate(); @@ -181,8 +180,8 @@ return new S1.s=new S2; public void testcheckNull() { Parser parser = new Parser( """ -struct I {int i;} -struct P {I pi;} +struct I {int i;}; +struct P { I? pi; }; P p1 = new P; P p2 = new P; p2.pi = new I; diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 3373a1aa..c749aba6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -293,7 +293,7 @@ else { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; return 0; ]", stop.toString()); + assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString()); } @@ -338,7 +338,7 @@ return primeCount; public void testAntiDeps1() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v=new S; v.f = 2; int i=new S.f; @@ -356,7 +356,7 @@ return i; public void testAntiDeps2() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v = new S; v.f = arg; S t = new S; @@ -370,14 +370,14 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region46,.f,0);", stop.toString()); + assertEquals("return Phi(Region48,.f,0);", stop.toString()); } @Test public void testAntiDeps3() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v0 = new S; S? v1; if (arg) v1 = new S; @@ -397,7 +397,7 @@ return v0; public void testAntiDeps4() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v = new S; v.f = arg; S t = new S; @@ -414,7 +414,7 @@ return i; public void testAntiDeps5() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v = new S; while(1) { while(arg+1) { arg=arg-1; } @@ -431,7 +431,7 @@ return v; public void testAntiDeps6() { Parser parser = new Parser( """ -struct s { int v; } +struct s { int v; }; s ptr=new s; while( -arg ) ptr = new s; @@ -446,7 +446,7 @@ while(1) public void testAntiDeps7() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v = new S; S t = new S; int i = v.f; @@ -464,7 +464,7 @@ return i; public void testAntiDeps8() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v = new S; S t = new S; while(arg) { @@ -477,14 +477,14 @@ while(arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop21,arg,Phi(Region48,.f,0));", stop.toString()); + assertEquals("return Phi(Loop23,arg,Phi(Region50,.f,0));", stop.toString()); } @Test public void testAntiDeps9() { Parser parser = new Parser( """ -struct S { int f; } +struct S { int f; }; S v = new S; S t = new S; if (arg) { @@ -501,8 +501,8 @@ return v; @Test public void testExample2() { Parser parser = new Parser( - """ -struct S { int f; } +""" +struct S { int f; }; S v = new S; int i = arg; while (arg > 0) { @@ -516,4 +516,39 @@ return v; StopNode stop = parser.parse().iterate(); //assertEquals("return new S;", stop.toString()); } + + @Test + public void testScheduleUse() { + Parser parser = new Parser( +""" +int v0=0; +while(0>=0) { + u1 v1=0; + v1=v0; + if(v1*0) + v0=-v1; +} +return 0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testLoopCarriedDep() { + Parser parser = new Parser( +""" +u32 v0=0; +{ + int v1=0; + while(v1) { + v1=1>>>v0!=0; + v0=v1/0; + } +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index d64423de..03a02795 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -93,7 +93,7 @@ return b; public void testRefLoad() { Parser parser = new Parser( """ -struct Foo { u1 b; } +struct Foo { u1 b; }; Foo f = new Foo; f.b = 123; return f.b; @@ -166,6 +166,39 @@ return arg; } @Test + public void testCloneAnd() { + Parser parser = new Parser(""" +int v0=0; +u32 v1 = 1&(1<<arg)&(1<<arg); +while(arg) v1=-v0; +while(v1) break; +return v1; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (Phi(Loop17,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testAndHigh() { + Parser parser = new Parser(""" +int v0=0; +if(0&0>>>0) { + while(0) { + u8 v1=0; + v0=0>>>0; + v1=arg; + while(v1+0) {} + } +} +return v0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testTypes() { Parser parser = new Parser( """ diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 8f9d2d14..643b45e7 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -4,81 +4,15 @@ import com.seaofnodes.simple.evaluator.Evaluator; import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import org.junit.Ignore; - -import java.nio.charset.StandardCharsets; - import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter15Test { - @Test public void testPartialAllocationMemory() { - StopNode stop = new Parser(""" - struct Other { int a; int b; int c; } - struct S { int x; flt y; S? next; } - Other other = new Other; - other.c = 7; - S a = new S; - a.x = arg; - a.y = 1.5; - S b = new S; - // S's aliases are global identities, not tuple or input positions. - // Bypass b's zeroing for a, preserving the unrelated Other slice. - return a.x + a.y + b.x + b.y + other.c; - """).parse().iterate(); - assertEquals(8.5, Evaluator.evaluate(stop,0)); - assertEquals(12.5, Evaluator.evaluate(stop,4)); - - stop = new Parser(""" - struct S { int x; flt y; S? next; } - S a = new S; S b = new S; - S p = a; if (arg) p = b; - // The memory result carries distinct int, float and pointer facts. - if (p.next != null) return 99; - return p.x + p.y; - """).parse().iterate(); - assertEquals("return 0.0;",stop.toString()); - assertEquals(0.0,Evaluator.evaluate(stop,1)); - } - - @Test public void testReadAcrossAllocation() { - StopNode stop = new Parser(""" - struct S { int x; } - S a = new S; S b = new S; - a.x = 11; b.x = 22; - S p = a; if (arg) p = b; - int before = p.x; - S c = new S; - a.x = 33; b.x = 44; - // The partial input to c must not hide the read/write ordering. - // p can alias either object, so node inequality cannot bypass New. - return before*100 + p.x + c.x; - """).parse().iterate(); - assertEquals(1133L,Evaluator.evaluate(stop,0)); - assertEquals(2244L,Evaluator.evaluate(stop,1)); - } - - @Test public void testAllocationInLoop() { - StopNode stop = new Parser(""" - struct S { int x; flt y; S? next; } - S old = new S; old.x = 7; - S last = old; - while (arg > 0) { - S fresh = new S; - fresh.x = last.x + 1; - fresh.next = last; - last = fresh; - arg = arg - 1; - } - return old.x*100 + last.x; - """).parse().iterate(); - assertEquals(707L,Evaluator.evaluate(stop,0)); - assertEquals(712L,Evaluator.evaluate(stop,5)); - } - @Test public void testJig() { - Parser parser = new Parser(""" + Parser parser = new Parser( +""" return 3.14; """); StopNode stop = parser.parse().iterate(); @@ -87,29 +21,10 @@ return 3.14; } @Test - public void testLifetime() { - Parser parser = new Parser(""" -u8[] b = new u8[5]; -if (arg) { - b[0] = b[0] + 1; -} else { - b[1] = b[1] * 2; -} -return b[0] + b[1]; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region72,1,0);", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - } - - @Test public void testCyclic() { Parser parser = new Parser( """ -struct C { - C? l; -} +struct C { C? l; }; C c = new C; c.l = c; return c; @@ -134,7 +49,7 @@ output[i] = 1; return output; """); StopNode stop = parser.parse().iterate(); - assertEquals("return u8[];", stop.toString()); + assertEquals("return [u8];", stop.toString()); assertEquals("\u0001", Evaluator.evaluate(stop, 0).toString()); } @@ -181,20 +96,20 @@ return a[0]; public void testBasic4() { Parser parser = new Parser( """ -struct A { int i; } +struct A { int i; }; A?[] a = new A?[2]; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return *A?[];", stop.toString()); - assertEquals("Obj<*A?[]>{#=2,[]=[null,null]}", Evaluator.evaluate(stop, 0).toString()); + assertEquals("return [*A?];", stop.toString()); + assertEquals("Obj<[*A?]>{#=2,[]=[null,null]}", Evaluator.evaluate(stop, 0).toString()); } @Test public void testBasic5() { Parser parser = new Parser( """ -struct S { int x; flt y; } +struct S { int x; flt y; }; // A new S S s = new S; s.x=99; s.y = 3.14; @@ -215,8 +130,10 @@ else { return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region122,1.2,Phi(Region119,2.3,.y));", stop.toString()); + // Shared allocation memory prevents folding the field Store into New. + assertEquals("return Phi(Region121,1.2,Phi(Region118,2.3,.y));", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); + assertEquals(1.2 , Evaluator.evaluate(stop, 1)); } @Ignore @@ -224,7 +141,7 @@ return rez; public void testBasic6() { Parser parser = new Parser( """ -struct S { int x; flt y; } +struct S { int x; flt y; }; // A new S S s = new S; s.x=99; s.y = 3.14; @@ -250,7 +167,7 @@ return rez; Parser parser = new Parser( """ // Can we define a forward-reference array? -struct Tree { Tree?[] _kids; } +struct Tree { Tree?[]? _kids; }; Tree root = new Tree; root._kids = new Tree?[2]; root._kids[0] = new Tree; @@ -258,17 +175,14 @@ return root; """); StopNode stop = parser.parse().iterate(); assertEquals("return Tree;", stop.toString()); - assertEquals("Obj<Tree>{_kids=Obj<*Tree?[]>{#=2,[]=[Obj<Tree>{_kids=null},null]}}", Evaluator.evaluate(stop, 0).toString()); + assertEquals("Obj<Tree>{_kids=Obj<[*Tree?]>{#=2,[]=[Obj<Tree>{_kids=null},null]}}", Evaluator.evaluate(stop, 0).toString()); } @Test public void testNestedStructAddMemProj() { Parser parser = new Parser( """ -struct S { - int a; - int[] b; -} +struct S { int a; int[] b; }; return 0; """); StopNode stop = parser.parse(); @@ -338,9 +252,9 @@ while( j < nprimes ) { return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return int[];", stop.toString()); + assertEquals("return [int];", stop.toString()); Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(stop, 20); - assertEquals("int[] {\n # :int;\n [] :int;\n}",obj.struct().toString()); + assertEquals("[int] { # :int; [] :int; }",obj.struct().toString()); long nprimes = (Long)obj.fields()[0]; long[] primes = new long[]{2,3,5,7,11,13,17,19}; for( int i=0; i<nprimes; i++ ) @@ -351,7 +265,7 @@ return rez; public void testNewNodeInit() { Parser parser = new Parser( """ -struct S {int i; flt f;} +struct S {int i; flt f;}; S s1 = new S; S s2 = new S; s2.i = 3; @@ -382,7 +296,7 @@ return new flt; int is = new int[2]; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Type *int[] is not of declared type int",e.getMessage()); } + catch( Exception e ) { assertEquals("Type *[int] is not of declared type int",e.getMessage()); } } @Test @@ -412,4 +326,67 @@ return is[1]; catch( NegativeArraySizeException e ) { assertEquals("-1",e.getMessage()); } } + @Test + public void testProgress() { + Parser parser = new Parser(""" +i8 v1=0&0; +u8 v2=0; +byte v4=0; +if(0) {} +while(v2<0) { + v4=0-v1; + break; +} +int v5=0&0; +while(v5+(0&0)) { + int v7=0&0; + while(v7) + v4=0>>>v5; + while(v1) + return 0; +} +return v1; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testSharpNot() { + Parser parser = new Parser( +""" +if(0>>0) {} +while(0) {} +u32 v7=0; +int v8=0; +while(0<--1>>>---(v7*0==v8)) {} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + + + @Test + public void testProgress2() { + Parser parser = new Parser( +""" +if(1) {} +else { + while(arg>>>0&0>>>0) {} + byte v3=0>>>0; + while(0) {} + int v7=0>>>0; + while(v7<0>>>0) { + while(0+v7<=0) if(1) arg=-12; + if(arg) { + v3=arg+v3+0; + arg=0; + } + } +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/src/test/java/com/seaofnodes/simple/Chapter16Test.java new file mode 100644 index 00000000..0f5a5a16 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -0,0 +1,189 @@ +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 Chapter16Test { + + @Test + public void testRequiredReference() { + for( String fields : new String[] { "int[] x;" } ) { + String src = "struct Point { "+fields+" }; Point p = new Point; p.x=p.x+1; return p;"; + try { new Parser(src).parse().iterate(); 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 testJig() { + Parser parser = new Parser( +""" +return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + + @Test + public void testMulti0() { + Parser parser = new Parser( +""" +int x, y; +return x+y; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + @Test + public void testMulti1() { + Parser parser = new Parser( +""" +int x=2, y=x+1; +return x+y; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 5;", stop.toString()); + assertEquals(5L, Evaluator.evaluate(stop, 0)); + } + + + + + + @Test + public void testConstruct0() { + Parser parser = new Parser(""" +struct X { int x=3; }; +X z = new X; +return z.x; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3;", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 0)); + } + + + + @Test + public void testConstruct2() { + Parser parser = new Parser(""" +struct X { int x=3; }; +X z = new X { x = 4; }; +return z.x; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + assertEquals(4L, Evaluator.evaluate(stop, 0)); + } + + + + + // Same as the Chapter13 test with the same name, but using the new + // constructor syntax + @Test + public void testLinkedList1() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; }; +LLI? head = null; +while( arg ) { + head = new LLI { next=head; i=arg; }; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( !next ) return 1; +return next.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 1)); + assertEquals(2L, Evaluator.evaluate(stop, 3)); + } + + @Test + public void testLinkedList2() { + Parser parser = new Parser( +""" +struct LLI { LLI? next; int i; }; +LLI? head = null; +while( arg ) { + head = new LLI { + next=head; + // Any old code in the constructor + int tmp=arg; + while( arg > 10 ) { + tmp = tmp + arg; + arg = arg - 1; + } + i=tmp; + }; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( !next ) return 1; +return next.i; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 1)); + assertEquals(2L, Evaluator.evaluate(stop, 11)); + } + + @Test + public void testSquare() { + Parser parser = new Parser( +""" +struct Square { + flt side = arg; + // Newtons approximation to the square root, computed in a constructor. + // The actual allocation will copy in this result as the initial + // value for 'diag'. + flt diag = arg*arg/2; + while( 1 ) { + flt next = (side/diag + diag)/2; + if( next == diag ) break; + diag = next; + } +}; +return new Square; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Square;", stop.toString()); + assertEquals("Obj<Square>{side=3.0,diag=1.7320508075688772}", Evaluator.evaluate(stop, 3).toString()); + assertEquals("Obj<Square>{side=4.0,diag=2.0}", Evaluator.evaluate(stop, 4).toString()); + } + 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; + if (arg) p=b; + int before=p.x; + 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; + }; + p.x=33; + return before*10000+c.x*100+c.y+t.z; + """; + + @Test public void testConstructorMemory() { + StopNode stop = new Parser(CONSTRUCTOR_MEMORY).parse().iterate(); + assertEquals(111249L,Evaluator.evaluate(stop,0)); + assertEquals(222352L,Evaluator.evaluate(stop,1)); + } +} diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 52c2a014..2c98f405 100644 --- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -1,10 +1,9 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.fuzzer.Fuzzer; -import org.junit.Test; +import java.util.Random; import org.junit.Ignore; - - +import org.junit.Test; import static org.junit.Assert.assertTrue; /** @@ -39,6 +38,15 @@ public class FuzzerWrap { } + @Test @Ignore + public void fuzzPeepsRandom() { + Random R = new Random(System.currentTimeMillis()); + var fuzzer = new Fuzzer(); + for (int i=0; i<100; i++) + fuzzer.fuzzPeeps(R.nextLong()); + assertTrue(fuzzer.noExceptions()); + } + @Test @Ignore public void fuzzPeepTiming() { diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java index ad595822..4b692f51 100644 --- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -40,7 +40,7 @@ return i; Parser parser = new Parser(""" struct S { int f; -} +}; S v0=new S; if(arg) v0.f=1; return v0; @@ -56,7 +56,7 @@ return v0; Parser parser = new Parser(""" struct S { int f; -} +}; S v=new S; v.f = 2; int i=new S.f; diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index cb45a0d7..6f7409cd 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -13,11 +13,11 @@ public class TypeTest { @Test public void testTypeAdHoc() { TypeStruct s1 = TypeStruct.make("s1", new Field[]{ - Field.make("a",-1, TypeInteger.BOT), - Field.make("b",-2, TypeInteger.BOT) }); + Field.make("a", TypeInteger.BOT,-1, false), + Field.make("b", TypeInteger.BOT,-2, false) }); TypeStruct s2 = TypeStruct.make("s2", new Field[]{ - Field.make("a",-3, TypeInteger.BOT), - Field.make("b",-4, TypeInteger.BOT) }); + Field.make("a", TypeInteger.BOT,-3, false), + Field.make("b", TypeInteger.BOT,-4, false) }); Assert.assertEquals(s1, s1.glb()); Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 9eed23de..3eb406eb 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -100,7 +100,7 @@ public class Evaluator { } @Override public String toString() { - if (struct._name.equals("u8[]")) { + if (struct._name.equals("[u8]")) { var sb = new StringBuilder(); for (int i=struct._fields.length-1; i<fields.length; i++) { var v = fields[i]; @@ -192,28 +192,20 @@ public class Evaluator { if( n < 0 ) throw new NegativeArraySizeException(""+n); body = new Object[(int)n+1]; // Array body - var c = type._fields[type._fields.length-1]._type; - if (c instanceof TypeInteger) { - for (int i=0; i<n; i++) body[i+type._fields.length-1] = 0L; - } else if (c instanceof TypeFloat) { - for (int i = 0; i < n; i++) body[i+type._fields.length-1] = 0D; + var elem = type._fields[1]._type; + if (elem instanceof TypeInteger) { + for (int i=0; i<n; i++) body[i+1] = 0L; + } else if (elem instanceof TypeFloat) { + for (int i = 0; i < n; i++) body[i+1] = 0D; } else { - assert c instanceof TypeMemPtr; + assert elem instanceof TypeMemPtr; } - num = type._fields.length-1; + // Length value + body[0] = vall(alloc.in(3)); } else { - body = new Object[type._fields.length]; - num = type._fields.length; - } - for (int i=0; i<num; i++) { - var c = type._fields[i]._type; - if (c instanceof TypeInteger) { - body[i] = 0L; - } else if (c instanceof TypeFloat) { - body[i] = 0D; - } else { - assert c instanceof TypeMemPtr; - } + body = new Object[num = type._fields.length]; + for (int i=0; i<num; i++) + body[i] = val(alloc.in(3+i)); } return new Object[]{new Obj(type,body),MEMORY}; } diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 125f2f5e..afcc700f 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -557,7 +557,7 @@ public class Scheduler { blocks.put(first, switch(last) { case null -> new Block(arr, null, -1, new Block[0]); case IfNode i -> new Block(arr, i, -1, new Block[2]); - case RegionNode r -> new Block(arr, r, Utils.find(r._inputs, prev), new Block[1]); + case RegionNode r -> new Block(arr, r, r._inputs.find(prev), new Block[1]); case ReturnNode r -> new Block(arr, r, -1, new Block[0]); default -> throw new AssertionError("Unexpected block exit node"); }); diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 7cd854bf..d3cbb0ee 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -109,7 +109,7 @@ public class ScriptGenerator { static { new Parser("", TypeInteger.BOT); - for( var e : Parser.TYPES.entrySet() ) { + for( var e : Parser.defaultTypes().entrySet() ) { if( e.getValue() instanceof TypeInteger ) { INTTYPES.add(new TypeInt(e.getKey())); } |