diff options
8 files changed, 150 insertions, 79 deletions
diff --git a/chapter15/src/main/java/com/seaofnodes/simple/Parser.java b/chapter15/src/main/java/com/seaofnodes/simple/Parser.java index 65bc82ea..b3b1f3c5 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/Parser.java @@ -489,8 +489,13 @@ public class Parser { // Convert the type name to a type. Type t0 = TYPES.get(tname); Type t1 = t0==null ? TypeStruct.BOT : t0; // Null: assume a forward ref type - //while( match("[]") ) - // t1 = TypeArray.make(t1); + while( match("[]") ) { + Type t2 = TYPES.get("[]"+tname); + if( t2==null ) { + TYPES.put("[]"+tname,t1 = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t1,ALIAS++)); + START.addMemProj((TypeStruct)t1, _scope); // Insert memory edges + } + } Type t2 = t1 instanceof TypeStruct obj ? TypeMemPtr.make(obj,match("?")) : t1; // Check no forward ref @@ -668,12 +673,12 @@ public class Parser { String typeName = _lexer.matchId(); if( typeName==null ) throw error("Expected a type"); Type t = TYPES.get(typeName); - //if( match("[") ) - // return require(newArray(t),"]"); + if( match("[") ) + return require(newArray(t),"]"); if( t instanceof TypeStruct obj ) { if( obj._fields==null ) throw error("Unknown struct type '" + typeName + "'"); - return newStruct(obj); + return newStruct(obj,con(obj.offset(obj._fields.length))); } throw error("Cannot allocate a "+t); } @@ -687,11 +692,11 @@ public class Parser { /** * Return a NewNode with pre-zeroed memory */ - private Node newStruct(TypeStruct obj) { + private Node newStruct(TypeStruct obj, Node size) { Field[] fs = obj._fields; Node[] ns = new Node[2+fs.length]; ns[0] = ctrl(); - ns[1] = con(obj.offsets()[fs.length]); + ns[1] = size; for( int i = 0; i < fs.length; i++ ) ns[i+2] = memAlias(fs[i]._alias); Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole(); @@ -701,10 +706,15 @@ public class Parser { } private Node newArray(Type t) { - Node len = parseExpression(); - //TypeArray tary = TypeArray.make(t,TypeInteger.BOT); - //return new NewArrayNode(tary,ctrl(),len).peephole(); - throw Utils.TODO(); + Node len = parseExpression().keep(); + TypeStruct ary = (TypeStruct)TYPES.get("[]"+t.str()); + 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 + memAlias(alias,new StoreNode("#",alias,TypeInteger.BOT,memAlias(alias),ptr,con( ary.offset(0) ), len.unkeep(), true ).peephole()); + return ptr; } // We set up memory aliases by inserting special vars in the scope these // variables are prefixed by $ so they cannot be referenced in Simple code. @@ -720,13 +730,16 @@ public class Parser { * * <pre> * expr ('.' IDENTIFIER)* [ = expr ] + * expr # * expr ('[' expr ']')* = [ = expr ] * </pre> */ private Node parsePostfix(Node expr) { - String name = "[]"; - if( match(".") ) name = requireId().intern(); - else if( !match("[") ) return expr; // No postfix + String name = null; + if( match(".") ) name = requireId().intern(); + else if( match("#") ) name = "#"; + else if( match("[") ) name = "[]"; + else return expr; // No postfix // Sanity check expr for being a reference if( !(expr._type instanceof TypeMemPtr ptr) ) @@ -736,14 +749,20 @@ public class Parser { // Sanity check field name for existing TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); if( base == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - int idx = base.find(name); - if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + int fidx = base.find(name); + if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); // Get field type and layout offset - Field f = base._fields[idx]; - Node off = con(base.offsets()[idx]); - if( name.equals("[]") ) - throw Utils.TODO(); // Array index math + Field f = base._fields[fidx]; + Node off; + if( name.equals("[]") ) { + // Array index math + Node idx = require(parseExpression(),"]"); + off = new AddNode(con(base.aryBase()),new ShlNode(idx,con(base.aryScale())).peephole()).peephole(); + } else { + // Hardwired field offset + off = con(base.offset(fidx)); + } if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 0567db6e..3048e2d9 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -47,7 +47,7 @@ public class LoadNode extends MemOpNode { // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() ) { // Must check same object + ptr() == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } @@ -64,7 +64,8 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && + off() instanceof ConstantNode ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. @@ -83,7 +84,7 @@ public class LoadNode extends MemOpNode { Node px = phi.in(idx); if( px==null ) return false; if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) { px.addDep(this); return true; } - if( px instanceof StoreNode st1 && ptr()==st1.ptr() ) { px.addDep(this); return true; } + if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } return false; } } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java index f1e6e84b..75db67fd 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -11,7 +11,7 @@ import java.util.BitSet; */ public class NewNode extends Node implements MultiNode { - TypeMemPtr _ptr; + public TypeMemPtr _ptr; public NewNode(TypeMemPtr ptr, Node... nodes) { super(nodes); diff --git a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeArray.java b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeArray.java deleted file mode 100644 index 8bfbff30..00000000 --- a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeArray.java +++ /dev/null @@ -1,37 +0,0 @@ -package com.seaofnodes.simple.type; - -import com.seaofnodes.simple.Utils; -import java.util.ArrayList; - -/** - * Represents an array type - */ -public class TypeArray extends TypeStruct { - - // An Array has a type and a size; the size is any integer type. - // The type can be any scalar type, so not e.g. TypeMem. - - private TypeArray(TypeInteger len, int lenAlias, Type body, int bodyAlias) { - super(TARRAY, "array", new Field[]{Field.make("#",lenAlias,len), Field.make("[]",bodyAlias,body)}); - } - - // All fields directly listed - public static TypeArray make(TypeInteger len, int lenAlias, Type body, int bodyAlias) { return new TypeArray(len,lenAlias,body,bodyAlias).intern(); } - public static TypeArray make(int lenAlias, Type body, int bodyAlias) { return make(TypeInteger.BOT,lenAlias,body,bodyAlias); } - - //public static final TypeArray BOT = make(Type.BOTTOM,TypeInteger.BOT); - //public static final TypeArray FLTS = make(TypeFloat.BOT,TypeInteger.U32); - // - //public static void gather(ArrayList<Type> ts) { ts.add(BOT); ts.add(FLTS); } - - //@Override - //public StringBuilder print(StringBuilder sb) { - // _type.print(sb).append("["); - // _len .print(sb).append("]"); - // return sb; - //} - // - //@Override public String str() { - // return _type.str() + "[" + _len.str() + "]"; - //} -} diff --git a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index e7794e14..9e38e025 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -24,26 +24,37 @@ public class TypeStruct extends Type { public final String _name; public final Field[] _fields; - TypeStruct(byte t, String name, Field[] fields) { - super(t); + TypeStruct(String name, Field[] fields) { + super(TSTRUCT); _name = name; _fields = fields; } // All fields directly listed - public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(TSTRUCT, name, fields).intern(); } + public static TypeStruct make(String name, Field... fields) { return new TypeStruct(name, fields).intern(); } public static final TypeStruct TOP = make("$TOP",new Field[0]); public static final TypeStruct BOT = make("$BOT",new Field[0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); // Forward-ref version - public static TypeStruct make(String name) { return make(name, null); } + public static TypeStruct make(String name) { return make(name, (Field[])null); } + + // Array + public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { + String name = "[]" + body.str(); + return make("[]" + body.str(), + Field.make("#" , lenAlias,len ), + Field.make("[]",bodyAlias,body)); + } // 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 void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } + + 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); } public int find(String fname) { for( int i=0; i<_fields.length; i++ ) @@ -150,11 +161,26 @@ public class TypeStruct extends Type { @Override public String str() { return _name; } + public boolean isAry() { return _fields.length==2 && _fields[1]._fname.equals("[]"); } + + public int aryBase() { + assert isAry(); + if( _offs==null ) _offs = offsets(); + return _offs[1]; + } + public int aryScale() { + assert isAry(); + return _fields[1]._type.log_size(); + } + + // Field offsets as packed byte offsets private int[] _offs; // Lazily computed and not part of the type semantics - public int[] offsets() { // Field byte offsets - if( _offs != null ) return _offs; - + public int offset(int idx) { + if( _offs==null ) _offs = offsets(); + return _offs[idx]; + } + private int[] offsets() { // Field byte offsets // Compute a layout for a collection of fields assert _fields != null; // No forward refs // Compute a layout @@ -166,7 +192,7 @@ public class TypeStruct extends Type { int[] offs = new int[4]; for( int i=3; i>=0; i-- ) { offs[i] = off; - off += cnts[i]<<(i+3); + off += cnts[i]<<i; } // Assign offsets to all fields. // Really a hidden radix sort. @@ -174,10 +200,10 @@ public class TypeStruct extends Type { for( Field f : _fields ) { int log = f._type.log_size(); _offs[idx++] = offs[log]; // Field offset - offs[log] += 1<<(log+3); // Next field offset at same alignment - cnts[log]--; // Count down, should be all zero at end + offs[log] += 1<<log; // Next field offset at same alignment + cnts[log]--; // Count down, should be all zero at end } - _offs[_fields.length] = (off+63)& ~63; // Round out to max alignment + _offs[_fields.length] = (off+7)& ~7; // Round out to max alignment return _offs; } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java index f884f18d..15465677 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -21,7 +21,7 @@ return 3.14; assertEquals(3.14, Evaluator.evaluate(stop, 0)); } - @Ignore @Test + @Test public void testBasic() { Parser parser = new Parser( """ @@ -34,6 +34,30 @@ return is[1]; } @Test + public void testRollingSum() { + Parser parser = new Parser( +""" +int[] ary = new int[arg]; +// Fill [0,1,2,3,4,...] +int i=0; +while( i < ary# ) { + ary[i] = i; + i = i+1; +} +// Fill [0,1,3,6,10,...] +i=0; +while( i < ary# - 1 ) { + ary[i+1] = ary[i+1] + ary[i]; + i = i+1; +} +return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 +"""); + StopNode stop = parser.parse(false).iterate(true); + assertEquals("return (.[]+(.[]*1000));", stop.toString()); + assertEquals(1006L, Evaluator.evaluate(stop, 4)); + } + + @Test public void testBad0() { Parser parser = new Parser( """ diff --git a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index b897af7d..40d73b19 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -85,8 +85,21 @@ public class Evaluator { private Object alloc(NewNode alloc) { TypeTuple tt = alloc.compute(); TypeStruct type = ((TypeMemPtr)tt._types[1])._obj; + Object[] body=null; + if( type.isAry() ) { + long sz = (Long)val(alloc.in(1)); + int base = alloc._ptr._obj.aryBase(); + int scale = alloc._ptr._obj.aryScale(); + long n = (sz-base)>>scale; + body = new Object[(int)n+1]; // Array body + body[0] = n; // Array length + } else { + body = new Object[type._fields.length]; + } Object[] mems = new Object[type._fields.length+2]; - mems[1] = new Obj(type,new Object[type._fields.length]); + // mems[0] is control + mems[1] = new Obj(type,body); // the ref + // mems[2+...] are memory aliases return mems; } @@ -94,7 +107,17 @@ public class Evaluator { var from = (Obj)val(load.ptr()); var off = val(load.off()); var idx = getFieldIndex(from.struct, load, (Long)off); - return from.fields[idx]; + if( idx==1 && from.struct.isAry() ) { + long len = (Long)from.fields[0]; + int base = from.struct.aryBase(); + int scale = from.struct.aryScale(); + long i = ((Long)off - base)>>scale; + if( i < 0 || i >= len ) + throw new RuntimeException("Array index out of bounds " + off + " <= " + len); + return from.fields[(int)i+1]; + + } else + return from.fields[idx]; } private Object store(StoreNode store) { @@ -102,7 +125,17 @@ public class Evaluator { var off = val(store.off()); var val = val(store.val()); var idx = getFieldIndex(to.struct, store, (Long)off); - to.fields[idx] = val; + if( idx==1 && to.struct.isAry() ) { + long len = (Long)to.fields[0]; + int base = to.struct.aryBase(); + int scale = to.struct.aryScale(); + long i = ((Long)off - base)>>scale; + if( i < 0 || i >= len ) + throw new RuntimeException("Array index out of bounds " + off + " <= " + len); + to.fields[(int)i+1] = val; + + } else + to.fields[idx] = val; return null; } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index fd8fdb8d..59c15d3f 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -155,7 +155,10 @@ public class Scheduler { * @return true if all placed inputs are before this node. */ private boolean isValid(NodeData data) { - return data.node._inputs.stream().map(i->i==null?null:d(i)).map(d->d==null||d.users>0?null:d.block).allMatch(d->d==null||dom(d, data.block)==d); + return data.node._inputs.stream() + .map(i->i==null?null:d(i)) + .map(d->d==null||d.users>0?null:d.block) + .allMatch(d->d==null||dom(d, data.block)==d); } /** @@ -399,7 +402,9 @@ public class Scheduler { } } if (!(node instanceof ReturnNode)) - for (Node n:node._outputs) if (n!=null && n instanceof CFGNode && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + for (Node n : node._outputs) + if(n instanceof CFGNode && isCFGNodeReady(n) && d(n).block == null) + queue.push(d(n)); var b = block; for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b)); } |