diff options
Diffstat (limited to 'chapter21/src/main/java/com/seaofnodes')
11 files changed, 78 insertions, 17 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/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index e1051fc6..49f057a3 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -295,9 +295,12 @@ public class RegAlloc { // Check all use inputs for n, in case there's several for( int i = 1; i < use.nIns(); i++ ) // Find a def input, and check register class - if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) - // Modify use to use the split version specialized to this rclass - { use.setDef( i, split ); j--; break; } + if( use.in( i ) == def ) { + RegMask m = mach.regmap( i ); + if( m!=null && mach.regmap( i ).overlap( rmask ) ) + // Modify use to use the split version specialized to this rclass + { use.setDefOrdered( i, split ); j--; break; } + } } } } 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) { |