diff options
Diffstat (limited to 'chapter15/src/main/java/com')
5 files changed, 82 insertions, 73 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; } |