invalidate idepth when inlining

Add fast idepth cache invalide using versioning.
Try not to hoist loop-invariant flags (or any single-register def) if it gets killed (and will spill next to use anyways).
Fix RISC store-of-zero (not encoded).
Fix ARM store-of-zero (disallowed).

10 files changed, 72 insertions, 14 deletions

diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 86cbfe97..3d2e6d6a 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -88,6 +88,24 @@ public class CodeGen {
     public  int getALIAS() { return _alias++; }
 
 
+    // idepths are cached and valid until *inserting* CFG edges (deleting is
+    // OK).  This happens with inlining, which bumps the version to bulk
+    // invalidate the idepth caches.
+    private int _iDepthVersion = 0;
+    public void invalidateIDepthCaches() { _iDepthVersion++; }
+    public boolean validIDepth(int idepth) {
+        if( idepth==0 ) return false;
+        if( _iDepthVersion==0 ) return true;
+        return (idepth%100)==_iDepthVersion;
+    }
+    public int iDepthAt(int idepth) {
+        return 100*idepth+_iDepthVersion;
+    }
+    public int iDepthFrom(int idepth) {
+        assert idepth==0 || validIDepth(idepth);
+        return idepth+100;
+    }
+
     // Popular visit bitset, declared here, so it gets reused all over
     public final BitSet _visit = new BitSet();
     public BitSet visit() { assert _visit.isEmpty(); return _visit; }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
index e904dc66..289d1786 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java
@@ -200,6 +200,33 @@ public abstract class GlobalCodeMotion {
         if( n instanceof MemOpNode load && load._isLoad )
             lca = find_anti_dep(lca,load,early,late);
 
+
+        // Nodes setting a single register and getting killed will stay close
+        // to the uses, since they will be forced to spill anyway.  The kill
+        // check is very weak, and some may be hoisted only to spill in the RA.
+        if( n instanceof MachNode mach ) {
+            RegMask out = mach.outregmap();
+            if( out!=null && out.size1() ) {
+                int reg = mach.outregmap().firstReg();
+                // Look for kills
+                outer:
+                for( CFGNode lca2=lca; lca2 != early; lca2 = lca2.idom() ) {
+                    if( lca2 instanceof MachNode mach2 ) {
+                        for( int i=1; i<lca2.nIns(); i++ ) {
+                            RegMask mask = mach2.regmap(i);
+                            if( mask!=null && mask.test(reg) ) {
+                                early = lca2 instanceof IfNode ? lca2.idom() : lca2;
+                                break outer;
+                            }
+                        }
+                        RegMask kill = mach2.killmap();
+                        if( kill != null )
+                            throw Utils.TODO();
+                    }
+                }
+            }
+        }
+
         // Walk up from the LCA to the early, looking for best place.  This is
         // the lowest execution frequency, approximated by least loop depth and
         // deepest control flow.
@@ -231,8 +258,9 @@ public abstract class GlobalCodeMotion {
     // Least loop depth first, then largest idepth
     private static boolean better( CFGNode lca, CFGNode best ) {
         return lca.loopDepth() < best.loopDepth() ||
-                lca instanceof NeverNode ||
-                (lca.idepth() > best.idepth() || best instanceof IfNode);
+            lca instanceof NeverNode ||
+            lca.idepth() > best.idepth() ||
+            best instanceof IfNode;
     }
 
     private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late) {
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index 56a33a26..7877f93a 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -3,6 +3,7 @@ package com.seaofnodes.simple.node;
 import com.seaofnodes.simple.Ary;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.type.*;
 import java.util.BitSet;
 import java.util.HashMap;
@@ -72,7 +73,9 @@ public abstract class CFGNode extends Node {
      * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
      */
     public int _idepth;
-    public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
+    public int idepth() {
+        return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth()));
+    }
 
     // Return the immediate dominator of this Node and compute dom tree depth.
     public CFGNode idom(Node dep) { return cfg(0); }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
index 47975833..f99a0b89 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -70,8 +70,9 @@ public class CallEndNode extends CFGNode implements MultiNode {
                     assert fun.in(1) instanceof StartNode && fun.in(2)==call;
                     // Disallow self-recursive inlining (loop unrolling by another name)
                     CFGNode idom = call;
-                    while( !(idom instanceof FunNode fun2) )
+                    while( !(idom instanceof FunNode) )
                         idom = idom.idom();
+                    // Inline?
                     if( idom != fun ) {
                         // Trivial inline: rewrite
                         _folding = true;
@@ -81,6 +82,9 @@ public class CallEndNode extends CFGNode implements MultiNode {
                         fun.setDef(2,call.ctrl());  // Bypass the Call;
                         fun.ret().setDef(3,null);   // Return is folding also
                         CodeGen.CODE.addAll(fun._outputs);
+                        // Inlining immediately blows all cache idepth fields past the inline point.
+                        // Bump the global version number invalidating them en-masse.
+                        CodeGen.CODE.invalidateIDepthCaches();
                         return this;
                     }
                 } else {
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java
index c477e125..b41a7e54 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -112,8 +112,11 @@ public class FunNode extends RegionNode {
         return null;
     }
 
-    // Bypass Region idom, always assume depth == 1, one more than Start
-    @Override public int idepth() { return (_idepth=1); }
+    // Bypass Region idom, always assume depth == 1, one more than Start,
+    // unless folding then just a ID on input#1
+    @Override public int idepth() {
+        return _folding ? super.idepth() : CodeGen.CODE.iDepthAt(1);
+    }
     // Bypass Region idom, always assume idom is Start
     @Override public CFGNode idom(Node dep) { return cfg(1); }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java
index cacf9c99..2fa070bc 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java
@@ -26,7 +26,9 @@ public class LoopNode extends RegionNode {
     }
 
     // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
-    @Override public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; }
+    public int idepth() {
+        return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth()));
+    }
     // Bypass Region idom, same as the default idom() using use in(1) instead of in(0)
     @Override public CFGNode idom(Node dep) { return entry(); }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 8c56feff..8f65d0e5 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -141,12 +141,13 @@ public class RegionNode extends CFGNode {
 
     // Immediate dominator of Region is a little more complicated.
     @Override public int idepth() {
-        if( _idepth!=0 ) return _idepth;
+        if( CodeGen.CODE.validIDepth(_idepth) )
+            return _idepth;
         int d=0;
         for( Node n : _inputs )
             if( n!=null )
-                d = Math.max(d,((CFGNode)n).idepth()+1);
-        return _idepth=d;
+                d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth()));
+        return _idepth = d;
     }
 
     @Override public CFGNode idom(Node dep) {
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 4bd76f50..f40203b4 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -51,7 +51,7 @@ public class StartNode extends LoopNode implements MultiNode {
     @Override public Node idealize() { return null; }
 
     // No immediate dominator, and idepth==0
-    @Override public int idepth() { return 0; }
+    @Override public int idepth() { return CodeGen.CODE.iDepthAt(0); }
     @Override public CFGNode idom(Node dep) { return null; }
 
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
index 104929f4..5056bc74 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
@@ -788,8 +788,7 @@ public class arm extends Machine {
     private static int off;
     private static Node idx;
     private Node st(StoreNode st) {
-        Node xval = st.val() instanceof ConstantNode con && con._con == TypeInteger.ZERO ? null : st.val();
-        return new StoreARM(address(st),st.ptr(),idx,off,xval);
+        return new StoreARM(address(st),st.ptr(),idx,off,st.val());
     }
 
     // Gather addressing mode bits prior to constructing.  This is a builder
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java
index d34d94fc..7305c4d9 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java
@@ -36,7 +36,7 @@ public class StoreRISC extends MemOpRISC {
         short ptr = enc.reg(ptr());
         int op = val >= riscv.F_OFFSET ? riscv.OP_STOREFP : riscv.OP_STORE;
         if( val >= riscv.F_OFFSET  ) val -= riscv.F_OFFSET;
-        enc.add4(riscv.s_type(op, func3()&7, ptr, val, _off));
+        enc.add4(riscv.s_type(op, func3()&7, ptr, val == -1 ? riscv.ZERO : val, _off));
     }
 
     @Override public void asm(CodeGen code, SB sb) {