diff options
Diffstat (limited to 'chapter23/src/main/java/com')
10 files changed, 39 insertions, 48 deletions
diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 6c958f32..02ade2c1 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -94,22 +94,12 @@ 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; + // Inlining can insert CFG edges and invalidate cached depth ordering. + private char _iDepthVersion; + public char iDepthVersion() { return _iDepthVersion; } + public void invalidateIDepthCaches() { + assert _iDepthVersion < Character.MAX_VALUE : "Dominator cache version exceeds 65535"; + ++_iDepthVersion; } // Popular visit bitset, declared here, so it gets reused all over @@ -484,7 +474,7 @@ public class CodeGen { if( _cfg==null ) return "no CFG"; SB sb = new SB(); for( CFGNode cfg : _cfg ) { - sb.fix(8,""+cfg._idepth); + sb.fix(8,""+(int)cfg._idepth); IRPrinter.printLine( cfg, sb ); } return sb.toString(); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index d9c7a6ad..144a9f8e 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -203,7 +203,7 @@ public abstract class GlobalCodeMotion { CFGNode lca = null; for( Node use : n._outputs ) if( use != null ) - lca = use_block(n,use, late)._idom(lca,null); + lca = use_block(n,use, late).domLCA(lca,null); // Loads may need anti-dependencies, raising their LCA if( n instanceof MemOpNode load && load._isLoad ) @@ -257,7 +257,7 @@ public abstract class GlobalCodeMotion { CFGNode found=null; for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==n ) - found = phi.region().cfg(i)._idom(found,null); + found = phi.region().cfg(i).domLCA(found,null); assert found!=null; return found; @@ -311,7 +311,7 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA + lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java index b9c70e5f..d9452b6d 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -36,6 +36,7 @@ public abstract class CFGNode extends Node { super(cfg); if( cfg != null ) { _idepth = cfg._idepth; + _idepthVersion = cfg._idepthVersion; _ltree = cfg._ltree; _pre = cfg._pre; } @@ -72,24 +73,32 @@ public abstract class CFGNode extends Node { * <p> * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ - public int _idepth; - public int idepth() { - return CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); + public char _idepth; + public char _idepthVersion; + public int idepth() { return validIDepth() ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + _idepthVersion = CodeGen.CODE.iDepthVersion(); + return _idepth = (char)depth; } + final boolean validIDepth() { return _idepth!=0 && _idepthVersion==CodeGen.CODE.iDepthVersion(); } + + // Return the immediate dominator of this Node and compute dom tree depth. public CFGNode idom(Node dep) { return cfg(0); } public final CFGNode idom() { return idom(null); } // Return the LCA of two idoms - public CFGNode _idom(CFGNode rhs, Node dep) { + public CFGNode domLCA(CFGNode rhs, Node dep) { if( rhs==null ) return this; CFGNode lhs = this; while( lhs != rhs ) { - var comp = lhs.idepth() - rhs.idepth(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom(); if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom(); - if( lhs==null || rhs==null ) return null; } return lhs; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java index 4bd0fd97..3ef486f8 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -122,9 +122,7 @@ public class FunNode extends RegionNode { // 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); - } + @Override public int idepth() { return _folding ? super.idepth() : 1; } // Bypass Region idom, always assume idom is Start @Override public CFGNode idom(Node dep) { return _folding && nIns()==3 ? cfg(2) : (nIns()>1 ? cfg(1) : null); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java index b58ea498..ec6260c0 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -87,7 +87,7 @@ public class LoadNode extends MemOpNode { for( Node memuse : mem._outputs ) // Find a prior load, has same mem,ptr,off but higher ctrl if( memuse != this && memuse instanceof LoadNode ld && ptr==ld.ptr() && off()==ld.off() && - cfg0()!=null && cfg0()._idom(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier + cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; // Load-after-Store on same address, but bypassing provably unrelated diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java index fc50e17f..6c69a56e 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -26,9 +26,7 @@ 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 CodeGen.CODE.validIDepth(_idepth) ? _idepth : (_idepth=CodeGen.CODE.iDepthFrom(idom().idepth())); - } + @Override public int idepth() { return validIDepth() ? _idepth : cacheIDepth(entry().idepth()+1); } // 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/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 2b467a8c..42b23633 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -141,21 +141,19 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { - if( CodeGen.CODE.validIDepth(_idepth) ) - return _idepth; - int d=0; + if( validIDepth() ) return _idepth; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,CodeGen.CODE.iDepthFrom(((CFGNode)n).idepth())); - return _idepth = d; + depth = Math.max(depth,((CFGNode)n).idepth()+1); + return cacheIDepth(depth); } @Override public CFGNode idom(Node dep) { CFGNode lca = null; - // Walk the LHS & RHS idom trees in parallel until they match, or either fails. - // Because this does not cache, it can be linear in the size of the program. + // Recompute from predecessors: CFG edits can change the dominator. for( int i=1; i<nIns(); i++ ) - lca = cfg(i)._idom(lca,dep); + lca = cfg(i).domLCA(lca,dep); return lca; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 7971733a..95303994 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -80,8 +80,7 @@ public class ReturnNode extends CFGNode { return ctrl().getClass() == RegionNode.class && ((RegionNode)ctrl()).inProgress(); } - // Gather parse-time return types for error reporting - private Type mt = Type.TOP; + // Remember parsed type kinds for diagnostics; the optimized expression decides validity. private boolean ti=false, tf=false, tp=false, tn=false; // Add a return exit to the current parsing function @@ -90,7 +89,6 @@ public class ReturnNode extends CFGNode { // Gather parse-time return types for error reporting Type t = expr._type; - mt = mt.meet(t); ti |= t instanceof TypeInteger x; tf |= t instanceof TypeFloat x; tp |= t instanceof TypeMemPtr x; @@ -116,7 +114,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { - return expr()._type/*mt*/==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; + return expr()._type==Type.BOTTOM ? mixerr(ti,tf,tp,tn,_fun._loc) : null; } static Parser.ParseException mixerr( boolean ti, boolean tf, boolean tp, boolean tn, Parser.Lexer loc ) { diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java index e3806de7..6ed2acd3 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -50,7 +50,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 CodeGen.CODE.iDepthAt(0); } + @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java index 4b03bf4e..98a8d4c3 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -66,10 +66,10 @@ public class StopNode extends CFGNode { } @Override public int idepth() { - if( _idepth!=0 ) return _idepth; + if( validIDepth() ) return _idepth; int d=0; for( Node ret : _inputs ) d = Math.max(d,((ReturnNode)ret).idepth()+1); - return _idepth=d; + return cacheIDepth(d); } } |