Chapter 10b: Splitting Memorylinear-chapter10b

12 files changed, 465 insertions, 38 deletions

diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java
index 7734f4df..3b5f2721 100644
--- a/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/src/main/java/com/seaofnodes/simple/Parser.java
@@ -33,6 +33,10 @@ public class Parser {
 
     public StopNode STOP;
 
+    // Field identities are independent of the memory graph and Start's tuple.
+    private final HashMap<String,Integer> _aliases = new HashMap<>();
+    private int _alias = 2;
+
     // The Lexer.  Thin wrapper over a byte[] buffer with a cursor.
     private final Lexer _lexer;
 
@@ -200,6 +204,8 @@ public class Parser {
         require("}");
         // Build and install the TypeStruct
         TypeStruct ts = TypeStruct.make(typeName, fields);
+        _aliases.put(typeName,_alias);
+        _alias += ts._fields.length;
         OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names
         return parseStatement();
     }
@@ -589,8 +595,10 @@ public class Parser {
     private Node newStruct( TypeStruct obj ) {
         Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep();
         Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole();
+        int alias = _aliases.get(obj._name);
         for( Field field : obj._fields ) {
-            mem(new StoreNode(field._fname, mem(), n, initValue).peephole());
+            store(field._fname,alias,n,initValue);
+            alias++;
         }
         return n.unkeep();
     }
@@ -599,6 +607,13 @@ public class Parser {
     private Node mem() { return _scope.lookup("$mem"); }
     private Node mem(Node n) { return _scope.update("$mem",n); }
 
+    private void store(String name, int alias, Node ptr, Node val) {
+        Node prior = mem().keep();
+        Node st = new StoreNode(name,alias,prior,ptr,val).peephole();
+        mem(new MemMergeNode(prior,alias,st).peephole());
+        prior.unkeep();
+    }
+
     /**
      * Parse postfix expression. For now this is just a field
      * expression, but in future could be array index too.
@@ -616,19 +631,20 @@ public class Parser {
         String name = requireId().intern();
         int idx = ptr._obj==null ? -1 : ptr._obj.find(name);
         if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'");
+        int alias = _aliases.get(ptr._obj._name)+idx;
 
         if( match("=") ) {
             // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment
             if( peek('=') ) _lexer._position--;
             else {
                 Node val = parseExpression();
-                mem(new StoreNode(name, mem(), expr, val).peephole());
+                store(name,alias,expr,val);
                 return expr;        // "obj.a = expr" returns the expression while updating memory
             }
         }
 
         Type declaredType = ptr._obj._fields[idx]._type;
-        return parsePostfix(new LoadNode(name, declaredType, mem(), expr).peephole());
+        return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole());
     }
 
     /**
diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
new file mode 100644
index 00000000..8d512f21
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java
@@ -0,0 +1,237 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+import java.util.BitSet;
+
+/**
+ * A Phi for bulk memory.  It covers all aliases except {@link #_aliases};
+ * those aliases must be represented by parallel precise MemPhis at the same
+ * program slice.
+ */
+public class BulkMemPhiNode extends PhiNode {
+
+    private static final BitSet EMPTY = new BitSet();
+
+    // Excluded Aliases; empty means NO exclusions.
+    // Each split clones the exclusions; published sets are never mutated.
+    public final BitSet _aliases;
+
+    public BulkMemPhiNode(String label, Node... inputs) {
+        this(label,EMPTY,inputs);
+    }
+
+    private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) {
+        super(label,TypeMem.BOT,inputs);
+        _aliases = aliases;
+    }
+
+    public boolean isSplit(int alias) { return _aliases.get(alias); }
+
+    @Override public String label() { return "BulkPhi"+_aliases; }
+
+    @Override
+    public Type compute() {
+        Type t = super.compute();
+        return t instanceof TypeMem mem ? mem :
+            t==Type.BOTTOM ? TypeMem.BOT :
+            TypeMem.TOP;
+    }
+
+    @Override
+    public Node idealize() {
+        Node progress = super.idealize();
+        if( progress != null ) return progress;
+        if( ((RegionNode)region()).inProgress() || region().nIns()<=1 )
+            return null;        // Input is in-progress
+
+        // "Peek through" a MemMerge that covers this alias set on its default
+        for( int i=1; i<nIns(); i++ )
+            if( in(i) instanceof MemMergeNode mmm && canPeek(mmm) ) {
+                setDef(i,IterPeeps.add(mmm.in(1)));
+                return this;
+            }
+
+        // If any input or output uses or defines a specific alias we cover,
+        // make a private MemPhi for it, and add it to the excluded list.
+        for( int i=1; i<nIns(); i++ ) {
+            int alias = inputAlias(in(i));
+            if( alias!=0 )
+                return slice(alias);
+        }
+
+        for( int i=0; i<_outputs.size(); i++ ) {
+            int alias = outputAlias(_outputs.get(i));
+            if( alias!=0 )
+                return slice(alias);
+        }
+
+        return null;
+    }
+
+    static public boolean checkMem(Node n, int alias) {
+        for( Node m : n._inputs )
+            // Bulk memory supplies this alias
+            if( m instanceof BulkMemPhiNode bulk ) {
+                if( bulk._aliases.get(alias) )
+                    return false;
+            } else if( m instanceof MemMergeNode mmm &&
+                       mmm.in(1) instanceof BulkMemPhiNode bulk &&
+                       bulk._aliases.get(alias) &&
+                       (alias >= mmm.nIns() || mmm.in(alias)==null) )
+                return false;
+        return true;
+    }
+
+
+    // True if the MemMerge has no precise slice still covered by this Phi.
+    private boolean canPeek(MemMergeNode mmm) {
+        return missingAlias(mmm,false)==0;
+    }
+
+    // Return an alias required by an input but still covered by this Phi, or 0.
+    private int inputAlias(Node n) {
+        return switch(n) {
+        case ProjNode proj -> 0;
+        case ConstantNode con -> 0;
+        case MemMergeNode mmm -> missingAlias(mmm,false);
+        case MemOpNode mem -> unsplit(mem._alias);
+        case BulkMemPhiNode bulk -> missingAlias(bulk);
+        default -> throw new AssertionError("Unexpected memory input "+n);
+        };
+    }
+
+    // Return an alias required by a user but still covered by this Phi, or 0.
+    private int outputAlias(Node use) {
+        // This decision depends backwards on an immediate user's alias/set.
+        // Normal graph-neighbor enqueueing flows from defs to uses, so retain
+        // an explicit forward dependency to revisit this Phi when the user
+        // sharpens.
+        use.addDepForwards(this);
+        return switch(use) {
+        case ScopeNode scope -> 0;
+        case MemMergeNode mmm -> missingAlias(mmm,true);
+        case BulkMemPhiNode bulk -> missingAlias(bulk);
+        case MemOpNode mem -> unsplit(mem._alias);
+        case MemPhiNode phi -> unsplit(phi._alias);
+        default -> {
+            assert use instanceof ReturnNode
+                : "Unexpected bulk-memory user "+use;
+            yield 0;
+        }
+        };
+    }
+
+    // Alias zero/one is bulk, and an already excluded precise alias cannot
+    // trigger another split of this Phi.
+    private int unsplit(int alias) {
+        if( alias <= 1 ) return 0;
+        assert !_aliases.get(alias);
+        return alias;
+    }
+
+    // First alias excluded by the neighboring bulk Phi but not by this one.
+    private int missingAlias(BulkMemPhiNode bulk) {
+        for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) )
+            if( !_aliases.get(alias) )
+                return alias;
+        return 0;
+    }
+
+    // First precise MemMerge slice still covered by this Phi.  When inspecting
+    // a user, ignore slots which point back to this Phi.
+    private int missingAlias(MemMergeNode mmm, boolean user) {
+        for( int alias=2; alias<mmm.nIns(); alias++ )
+            if( mmm.in(alias)!=null &&
+                mmm.alias(alias)!=mmm.in(1) &&
+                !_aliases.get(alias) )
+                { assert (!user || mmm.in(alias)!=this); return alias; }
+        return 0;
+    }
+
+    // Slice out given alias
+    private MemMergeNode slice( int alias ) {
+        assert !_aliases.get(alias);
+        // Inputs are the same; MemPhi will sharpen his own inputs.  If a
+        // parallel precise Phi already exists, reuse it instead of building a
+        // duplicate for the same Region/alias pair.
+        Node mem = precisePhi(alias);
+
+        BitSet aliases = ((BitSet)_aliases.clone());
+        aliases.set(alias);
+        BulkMemPhiNode bphi = new BulkMemPhiNode(_label,aliases);
+        for( int i=0; i<nIns(); i++ )
+            bphi.addDef(in(i));
+        // Installing bphi creates a new bulk user with a different exclusion
+        // set.  Queue the original memory inputs before bphi itself can peep
+        // away and hide those neighbor relationships.
+        for( int i=1; i<bphi.nIns(); i++ )
+            IterPeeps.add(bphi.in(i));
+        // Do not peephole bphi here, as BulkMemPhi can recursively start a
+        // second bulk rewrite before this one has finished.  Let the worklist
+        // discover any further splits
+        bphi.setType(TypeMem.BOT);
+        Node bulk = bphi;
+        IterPeeps.add(bulk);
+        IterPeeps.add(mem);
+        return aggregate(bulk,alias,mem);
+    }
+
+    // Build aggregate memory over a bulk Phi, preserving every precise slice
+    // which the bulk has already excluded.  The named alias is newly supplied
+    // (or replaces its old slice).
+    MemMergeNode aggregate(Node bulk, int alias, Node precise) {
+        MemMergeNode mmm = new MemMergeNode(bulk);
+        for( int old = _aliases.nextSetBit(0); old >= 0; old = _aliases.nextSetBit(old+1) )
+            { assert old != alias; mmm.alias(old,precisePhi(old));}
+        mmm.alias(alias,precise);
+        assert checkMerge(mmm);
+        return mmm;
+    }
+
+    // Find or make the precise Phi parallel to this bulk Phi at the same merge.
+    private Node precisePhi(int alias) {
+        MemPhiNode mphi = _findPhi(alias);
+        if( mphi!=null ) return mphi;
+
+        mphi = new MemPhiNode("$"+alias,alias);
+        mphi.addDef(region());
+        // Due to cycles, must set before calling peephole
+        mphi.setType(TypeMem.make(alias));
+        for( int i=1; i<nIns(); i++ )
+            mphi.addDef(IterPeeps.add(preciseInput(in(i),alias)));
+        return IterPeeps.add(mphi);
+    }
+
+    MemPhiNode _findPhi(int alias) {
+        for( Node use : region()._outputs )
+            if( use instanceof MemPhiNode mphi && mphi._alias==alias )
+                return mphi;
+        return null;
+    }
+
+    // Select an alias already split out of a predecessor's bulk memory.
+    private Node preciseInput(Node mem, int alias) {
+        if( mem instanceof MemMergeNode mmm )
+            return mmm.alias(alias);
+        if( mem instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) )
+            return bulk.precisePhi(alias);
+        return mem;
+    }
+
+    // Every alias excluded by a bulk default must be supplied explicitly.
+    static boolean checkMerge(MemMergeNode mmm) {
+        if( !(mmm.in(1) instanceof BulkMemPhiNode bulk) ) return true;
+        for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) )
+            if( alias >= mmm.nIns() || mmm.in(alias)==null )
+                return false;
+        return true;
+    }
+
+    @Override public boolean eq(Node n) {
+        return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n);
+    }
+
+    @Override int hash() { return _aliases.hashCode(); }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 54689283..55822722 100644
--- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -1,6 +1,9 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.Field;
 
 import java.util.BitSet;
 
@@ -15,11 +18,11 @@ public class LoadNode extends MemOpNode {
      * Load a value from a ptr.field.
      *
      * @param name  The field we are loading
-     * @param memSlice The whole-memory node - this is updated after a Store
+     * @param memSlice The memory alias node - this is updated after a Store
      * @param memPtr The ptr to the struct from where we load a field
      */
-    public LoadNode(String name, Type glb, Node memSlice, Node memPtr) {
-        super(name, memSlice, memPtr, null);
+    public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) {
+        super(name, alias, memSlice, memPtr, null);
         _declaredType = glb;
     }
 
@@ -36,10 +39,16 @@ public class LoadNode extends MemOpNode {
 
     @Override
     public Node idealize() {
+        if( mem() instanceof MemMergeNode merge ) {
+            setDef(1,IterPeeps.add(merge.alias(_alias)));
+            return this;
+        }
+
 
         // Simple Load-after-Store on same address.
         if( mem() instanceof StoreNode st &&
-            ptr() == st.ptr() && _name.equals(st._name) ) { // Must check same object
+            ptr() == st.ptr() && _alias==st._alias ) { // Must check same object
+            assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
             return st.val();
         }
 
@@ -50,13 +59,13 @@ 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 MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) {
             // Profit on RHS/Loop backedge
             if( profit(memphi,2) ||
                 // Else must not be a loop to count profit on LHS.
                 (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) {
-                Node ld1 = new LoadNode(_name,_declaredType,memphi.in(1),ptr()).peephole();
-                Node ld2 = new LoadNode(_name,_declaredType,memphi.in(2),ptr()).peephole();
+                Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole();
+                Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole();
                 return new PhiNode(_name,_type,memphi.region(),ld1,ld2);
             }
         }
@@ -67,6 +76,6 @@ public class LoadNode extends MemOpNode {
     // Profitable if we find a matching Store on this Phi arm.
     private boolean profit(PhiNode phi, int idx) {
         Node px = phi.in(idx);
-        return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _name.equals(st1._name);
+        return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias;
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
new file mode 100644
index 00000000..d7fed402
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java
@@ -0,0 +1,60 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+import java.util.BitSet;
+
+/** All memory: a default slice and explicit overrides for individual aliases. */
+public class MemMergeNode extends Node {
+    public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; }
+    public MemMergeNode(Node bulk, int alias, Node precise) {
+        this(bulk);
+        alias(alias,precise);
+    }
+
+    public Node alias(int alias) {
+        Node n = alias < nIns() ? in(alias) : null;
+        assert n!=null || !(in(1) instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias);
+        return n==null ? in(1) : n;
+    }
+
+    public void alias(int alias, Node mem) {
+        assert alias > 1;
+        while( nIns()<=alias ) addDef(null);
+        setDef(alias,mem);
+    }
+
+    @Override public String label() { return "MemMerge"; }
+    @Override public boolean isMem() { return true; }
+    @Override public Type compute() { return TypeMem.BOT; }
+    @Override StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        sb.append("MEM[");
+        for( int i=1; i<nIns(); i++ )
+            if( in(i)!=null ) {
+                sb.append(i==1 ? "default:" : i+":");
+                in(i)._print0(sb,visited).append(" ");
+            }
+        return sb.append("]");
+    }
+
+    @Override public Node idealize() {
+        boolean progress=false, allDefault=true;
+        for( int i=2; i<nIns(); i++ ) {
+            if( in(i)==in(1) ) { setDef(i,null); progress=true; }
+            if( in(i)!=null ) allDefault=false;
+        }
+        if( allDefault ) return in(1);
+
+        if( in(1) instanceof MemMergeNode mem ) {
+            for( int i=2; i<mem.nIns(); i++ )
+                if( mem.in(i)!=null && (i>=nIns() || in(i)==null) )
+                    alias(i,mem.in(i));
+            IterPeeps.add(mem.in(1));
+            setDef(1,mem.in(1));
+            return this;
+        }
+        assert BulkMemPhiNode.checkMerge(this);
+        return progress ? this : null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
index d811e71a..08e08bbf 100644
--- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.type.Field;
 import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeMemPtr;
 
@@ -9,10 +10,12 @@ import com.seaofnodes.simple.type.TypeMemPtr;
 public abstract class MemOpNode extends Node {
 
     public final String _name;
+    public final int _alias;
 
-    public MemOpNode(String name, Node memSlice, Node memPtr, Node value) {
+    public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
         super(null, memSlice, memPtr, value);
         _name  = name;
+        _alias = alias;
     }
 
     public Node mem() { return in(1); }
@@ -21,11 +24,11 @@ public abstract class MemOpNode extends Node {
     @Override
     boolean eq(Node n) {
         MemOpNode mem = (MemOpNode)n; // Invariant
-        return _name.equals(mem._name);
+        return _alias==mem._alias;    // When comparing types error to use "equals"; always use "=="
     }
 
     @Override
-    int hash() { return _name.hashCode(); }
+    int hash() { return _alias; }
 
     @Override
     String err() {
diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
new file mode 100644
index 00000000..c806bede
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java
@@ -0,0 +1,36 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.IterPeeps;
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeMem;
+
+/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */
+public class MemPhiNode extends PhiNode {
+    public final int _alias;
+
+    public MemPhiNode(String label, int alias, Node... inputs) {
+        super(label,TypeMem.make(alias),inputs);
+        assert alias > 1;
+        _alias = alias;
+    }
+
+    @Override public String label() { return "MemPhi_"+_alias; }
+
+    @Override public Type compute() {
+        assert BulkMemPhiNode.checkMem(this,_alias);
+        Type t = super.compute();
+        return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias);
+    }
+
+    @Override public Node idealize() {
+        for( int i=1; i<nIns(); i++ )
+            if( in(i) instanceof MemMergeNode mem ) {
+                setDef(i,IterPeeps.add(mem.alias(_alias)));
+                return this;
+            }
+        return super.idealize();
+    }
+
+    @Override boolean eq(Node n) { return _alias==((MemPhiNode)n)._alias && super.eq(n); }
+    @Override int hash() { return _alias; }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index eb6c1697..f4972f96 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -450,6 +450,14 @@ public abstract class Node {
      * being added must benefit from this node being peepholed.
      */
     Node addDep( Node dep ) {
+        return addDep(dep,false);
+    }
+
+    // A bulk Phi inspects its users' partitions. Def-to-use propagation does
+    // not revisit that producer when an immediate user's partition changes.
+    Node addDepForwards(Node dep) { return addDep(dep,true); }
+
+    private Node addDep(Node dep, boolean forwards) {
         // Running peepholes during the big assert cannot have side effects
         // like adding dependencies.
         if( IterPeeps.midAssert() ) return this;
@@ -457,8 +465,8 @@ public abstract class Node {
         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( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors
-        if( Utils.find(_outputs,dep)!= -1 ) return this;
+        if( !forwards && Utils.find(_inputs,dep) != -1 ) return this;
+        if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this;
         _deps.add(dep);
         return this;
     }
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index bdf50847..650edd6b 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -16,6 +16,10 @@ public class PhiNode extends Node {
 
     public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label;  assert declaredType!=null; _declaredType = declaredType; }
 
+    public static PhiNode make(String label, Type type, Node... inputs) {
+        return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs);
+    }
+
     @Override public String label() { return "Phi_"+_label; }
 
     @Override
@@ -71,7 +75,7 @@ public class PhiNode extends Node {
         //   Phi(op(A,B),op(Q,R),op(X,Y)) becomes
         //     op(Phi(A,Q,X), Phi(B,R,Y)).
         Node op = in(1);
-        if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) {
+        if( !isMem() && op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) {
             Node[] lhss = new Node[nIns()];
             Node[] rhss = new Node[nIns()];
             lhss[0] = rhss[0] = in(0); // Set Region
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 455f4b3a..b931e862 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -129,7 +129,7 @@ public class ScopeNode extends Node {
                 // 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,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
+                : loop.setDef(idx,PhiNode.make(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole());
             setDef(idx,old);
         }
         return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer
@@ -207,7 +207,7 @@ public class ScopeNode extends Node {
             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, new PhiNode(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
+                setDef(i, PhiNode.make(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole());
         that.kill();            // Kill merged scope
         IterPeeps.add(r);
         return r.unkeep().peephole();
diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index 4bc67c3c..b752aad5 100644
--- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -1,5 +1,7 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.*;
 
 import java.util.BitSet;
@@ -12,12 +14,12 @@ public class StoreNode extends MemOpNode {
 
     /**
      * @param name The struct field we are assigning to
-     * @param memSlice The whole-memory node - this is updated after a Store
+     * @param memSlice The memory alias node - this is updated after a Store
      * @param memPtr The ptr to the struct where we will store a value
      * @param value Value to be stored
      */
-    public StoreNode(String name, Node memSlice, Node memPtr, Node value) {
-        super(name, memSlice, memPtr, value);
+    public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) {
+        super(name, alias, memSlice, memPtr, value);
     }
 
     @Override
@@ -32,19 +34,25 @@ public class StoreNode extends MemOpNode {
     }
 
     @Override
-    public Type compute() { return TypeMem.BOT; }
+    public Type compute() { return TypeMem.make(_alias); }
 
     @Override
     public Node idealize() {
+        if( mem() instanceof MemMergeNode merge ) {
+            setDef(1,IterPeeps.add(merge.alias(_alias)));
+            return this;
+        }
+
 
         // Simple store-after-store on same address.  Should pick up the
         // required init-store being stomped by a first user store.
         if( mem() instanceof StoreNode st &&
-            ptr()==st.ptr() && _name.equals(st._name) &&  // Must check same object
+            ptr()==st.ptr() && _alias==st._alias &&  // Must check same object
             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) ) {
+            assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect
             setDef(1,st.mem());
             return this;
         }
diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java
index bd9cf458..93e27c76 100644
--- a/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -34,7 +34,7 @@ public class Type {
     static final byte TSIMPLE = 4; // End of the Simple Types
     static final byte TINT    = 5; // All Integers; see TypeInteger
     static final byte TTUPLE  = 6; // Tuples; finite collections of unrelated Types, kept in parallel
-    static final byte TMEM    = 7; // Whole-memory token
+    static final byte TMEM    = 7; // All memory (alias 0) or A slice of memory - with specific alias
     static final byte TMEMPTR = 8; // Memory pointer type
     static final byte TSTRUCT = 9; // Structs; tuples with named fields
     static final byte TFLD    =10; // Fields into struct
diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
index d921bac3..b6fc8824 100644
--- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java
+++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java
@@ -1,20 +1,66 @@
 package com.seaofnodes.simple.type;
 
+import com.seaofnodes.simple.Utils;
+import java.lang.Long;
+import java.util.BitSet;
 import java.util.ArrayList;
 
-/** A token for all memory; field values are not tracked in its type. */
+
+/**
+ * Represents a slice of memory corresponding to a set of aliases
+ */
 public class TypeMem extends Type {
-    private final boolean _high;
-    private TypeMem(boolean high) { super(TMEM); _high = high; }
-    public static final TypeMem TOP = new TypeMem(true ).intern();
-    public static final TypeMem BOT = new TypeMem(false).intern();
-
-    public static void gather(ArrayList<Type> ts) { ts.add(BOT); }
-    @Override TypeMem xmeet(Type t) { return BOT; }
-    @Override public Type dual() { return _high ? BOT : TOP; }
-    @Override public Type glb() { return BOT; }
-    @Override int hash() { return _high ? 1 : 2; }
-    @Override boolean eq(Type t) { return _high==((TypeMem)t)._high; }
-    @Override public StringBuilder print(StringBuilder sb) { return sb.append(_high ? "MemTop" : "MemBot"); }
+
+    // Which slice of memory?
+    //  0 means TOP, no slice.
+    // -1 means BOT, all memory.
+    //  N means slice#N.
+    private final int _alias;
+
+    private TypeMem(int alias) { super(TMEM); _alias = alias; }
+
+    public static TypeMem make(int alias) { return new TypeMem(alias).intern(); }
+    public static final TypeMem TOP = make( 0);
+    public static final TypeMem BOT = make(-1);
+
+
+    public static void gather(ArrayList<Type> ts) { ts.add(make(1)); ts.add(BOT); }
+
+    @Override
+    TypeMem xmeet(Type t) {
+        TypeMem that = (TypeMem) t; // Invariant: TypeMem and unequal
+        return _alias==0 ? that : (that._alias==0 ? this : BOT);
+    }
+
+    @Override
+    public Type dual() {
+        if( _alias== 0 ) return BOT;
+        if( _alias==-1 ) return TOP;
+        return this;
+    }
+
+    @Override
+    public Type glb() { return TypeMem.BOT; }
+
+    @Override
+    int hash() { return 9876543 + _alias; }
+
+    @Override
+    boolean eq(Type t) {
+        TypeMem that = (TypeMem) t; // Invariant
+        return _alias == that._alias;
+    }
+
+    @Override
+    public StringBuilder print(StringBuilder sb) {
+        if( this==BOT ) return sb.append("MemBot");
+        if( this==TOP ) return sb.append("MemTop");
+        return sb.append("MEM#").append( switch(_alias) {
+            case  0 -> "TOP";
+            case -1 -> "BOT";
+            default -> ""+_alias;
+            });
+    }
+
     @Override public String str() { return print(new StringBuilder()).toString(); }
 }