arrays with loads and stores

No range-checking yet.
Length is "ary#"
TypeStruct with special "[]" field is an array
Fix some eager push-load-thru phi

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;
     }