From 6e59fc1b71f2098c8baf90a6c54e5a33b7291e94 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 19 Sep 2026 22:31:42 -0700 Subject: Unify mixed-return checking and results Unify dominator caching. --- .../java/com/seaofnodes/simple/GlobalCodeMotion.java | 4 ++-- .../main/java/com/seaofnodes/simple/node/CFGNode.java | 19 +++++++++++++------ .../java/com/seaofnodes/simple/node/LoopNode.java | 2 +- .../java/com/seaofnodes/simple/node/RegionNode.java | 11 +++++------ .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- 5 files changed, 22 insertions(+), 16 deletions(-) (limited to 'chapter13/src/main/java/com/seaofnodes') diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 8a96e69c..865f7036 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -174,7 +174,7 @@ public abstract class GlobalCodeMotion { assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - 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 LoadNode load ) @@ -248,7 +248,7 @@ public abstract class GlobalCodeMotion { for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // 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 && Utils.find(st._inputs,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/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ba0fa4..07ff0b15 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -48,21 +48,28 @@ public abstract class CFGNode extends Node { *

* See {@link ...} */ - public int _idepth; - public int idepth() { return _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + public char _idepth; + public int idepth() { return _idepth!=0 ? _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"; + return _idepth = (char)depth; + } + // 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( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom(); - if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom(); + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = (dep==null ? lhs : (CFGNode)lhs.addDep(dep)).idom(); + if( comp <= 0 ) rhs = (dep==null ? rhs : (CFGNode)rhs.addDep(dep)).idom(); } return lhs; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..a0e988dd 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -28,7 +28,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 _idepth==0 ? (_idepth=idom().idepth()+1) : _idepth; } + @Override public int idepth() { return _idepth!=0 ? _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/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d5105614..fb934511 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -92,19 +92,18 @@ public class RegionNode extends CFGNode { // Immediate dominator of Region is a little more complicated. @Override public int idepth() { if( _idepth!=0 ) return _idepth; - int d=0; + int depth=0; for( Node n : _inputs ) if( n!=null ) - d = Math.max(d,((CFGNode)n).idepth()+1); - 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