From d5352268a0a1355262eed78e3263c18486fb9d8a Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 2 Oct 2026 11:20:00 -0700 Subject: Fix bug loop tree depth on inf loops --- .../com/seaofnodes/simple/codegen/BuildLRG.java | 9 ++- .../java/com/seaofnodes/simple/codegen/IFG.java | 3 + .../com/seaofnodes/simple/codegen/RegAlloc.java | 6 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 86 +++++++++++----------- .../java/com/seaofnodes/simple/node/LoopNode.java | 10 +-- 5 files changed, 65 insertions(+), 49 deletions(-) (limited to 'chapter25/src/main/java/com/seaofnodes') diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index aa33a7ec..0b314978 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; abstract public class BuildLRG { @@ -19,10 +20,12 @@ abstract public class BuildLRG { if( bb instanceof FunNode fun2 ) fun = fun2; for( Node n : bb.outs() ) { + // A synthetic never-exit value has no runtime definition. + if( n._type==Type.TOP ) continue; if( n instanceof PhiNode phi && !(phi._type instanceof TypeMem) ) { if( phi instanceof MachNode mach && mach.outregmap()==null ) continue; - // All Phi inputs end up with the same LRG. + // All real Phi inputs end up with the same LRG. // Pass 1: find any pre-existing LRG, to avoid make-then-Union a LRG LRG lrg = alloc.lrg(phi); if( lrg == null ) @@ -35,7 +38,9 @@ abstract public class BuildLRG { // Pass 2: everybody uses the same LRG lrg=alloc.union(lrg,phi); for( int i=phi instanceof ParmNode ? 2 : 1; i funs, StopNode stop) { _ltree = stop._ltree = CodeGen.CODE.XCTRL._ltree = new LoopTree((StartNode)this); Ary work = new Ary<>(FunNode.class); @@ -210,7 +210,7 @@ public abstract class CFGNode extends Node { work.push(fun); if(fun.in(1) instanceof StartCUNode start && start._pre==0 ) { start._pre = pre++; - start._ltree = _ltree; + start._ltree = start.cfg(1)._ltree = _ltree; post.set(start._nid); } }; @@ -224,6 +224,14 @@ public abstract class CFGNode extends Node { // Pre-walked? if( _pre!=0 ) return pre; _pre = pre++; + // Seed the function's outer tree before walking its body. Synthetic + // exits can be added before the post-order walk reaches the entry. + if( this instanceof FunNode ) _ltree = stop._ltree; + if( this instanceof ReturnNode ) { + _ltree = fun._ltree; + post.set(_nid); + return pre; // Stop/Start links describe the outside world, not a loop. + } // Pre-walk for( Node use : _outputs ) if( use instanceof CFGNode usecfg ) { @@ -233,46 +241,42 @@ public abstract class CFGNode extends Node { pre = usecfg._bltWalk( pre, use instanceof FunNode fuse ? fuse : fun, stop, post, work ); } - if( this instanceof ReturnNode ret ) { - ret._ltree = stop._ltree; - } else { - // Post-order work: find innermost loop - LoopTree inner = null, ltree; - for( Node use : _outputs ) { - if( !(use instanceof CFGNode usecfg) ) continue; - if( skip(usecfg) ) continue; - if( usecfg._type == Type.XCONTROL || // Do not walk dead control - usecfg._type == TypeTuple.IF_NEITHER ) // Nor dead IFs - continue; - // Child visited but not post-visited? - if( !post.get(usecfg._nid) ) { - // Must be a backedge to a LoopNode then - ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg); - } else { - // Take child's loop choice, which must exist - ltree = usecfg._ltree; - // If falling into a loop, use the target loop's parent instead - if( ltree._head == usecfg ) { - if( ltree._par == null ) - // This loop never had an If test choose to take its - // exit, i.e. it is a no-exit infinite loop. - ltree._par = ltree._head.forceExit(fun,stop)._ltree; - ltree = ltree._par; - } - } - // Sort inner loops. The decision point is some branch far removed - // from either loop head OR either backedge so requires pre-order - // numbers to figure out innermost. - if( inner == null ) { inner = ltree; continue; } - if( inner == ltree ) continue; // No change - LoopTree outer = ltree._head._pre > inner._head._pre ? inner : ltree; - inner = ltree._head._pre > inner._head._pre ? ltree : inner; - inner._par = outer; - } - // Set selected loop - if( inner!=null ) - _ltree = inner; + // Post-order work: find innermost loop + LoopTree inner = null, ltree; + for( Node use : _outputs ) { + if( !(use instanceof CFGNode usecfg) ) continue; + if( skip(usecfg) ) continue; + if( usecfg._type == Type.XCONTROL || // Do not walk dead control + usecfg._type == TypeTuple.IF_NEITHER ) // Nor dead IFs + continue; + // Child visited but not post-visited? + if( !post.get(usecfg._nid) ) { + // Must be a backedge to a LoopNode then + ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg); + } else { + // Take child's loop choice, which must exist + ltree = usecfg._ltree; + // If falling into a loop, use the target loop's parent instead + if( ltree._head == usecfg ) { + if( ltree._par == null ) + // This loop never had an If test choose to take its + // exit, i.e. it is a no-exit infinite loop. + ltree._par = ltree._head.forceExit(fun,stop)._ltree; + ltree = ltree._par; + } + } + // Sort inner loops. The decision point is some branch far removed + // from either loop head OR either backedge so requires pre-order + // numbers to figure out innermost. + if( inner == null ) { inner = ltree; continue; } + if( inner == ltree ) continue; // No change + LoopTree outer = ltree._head._pre > inner._head._pre ? inner : ltree; + inner = ltree._head._pre > inner._head._pre ? ltree : inner; + inner._par = outer; } + // Set selected loop + if( inner!=null ) + _ltree = inner; // Tag as post-walked post.set(_nid); return pre; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java index e8464353..df686bcf 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -31,7 +31,7 @@ public class LoopNode extends RegionNode { // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public StopNode forceExit( FunNode fun, StopNode stop ) { + public FunNode forceExit( FunNode fun, StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. @@ -40,7 +40,7 @@ public class LoopNode extends RegionNode { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { CFGNode other = iff.cproj(1-exit._idx); if( other!=null && other._ltree != _ltree && nested(_ltree,other._ltree) ) - return stop; // Found an exit, not an infinite loop + return fun; // Found an exit, not an infinite loop } x = x.idom(); } @@ -51,7 +51,7 @@ public class LoopNode extends RegionNode { setDef(2,t); // True continues loop, False (never) exits loop ReturnNode ret = fun.ret(); iff._ltree = t._ltree = _ltree; - ret._ltree = f._ltree = stop._ltree; + ret._ltree = f._ltree = fun._ltree; // Now fold control into the exit. Might have 1 valid exit, or an // XCtrl or a bunch of prior NeverNode exits. @@ -72,7 +72,7 @@ public class LoopNode extends RegionNode { expr instanceof PhiNode prez && prez.region()==r ) ) { // Nope, insert an aligned exit layer RegionNode r = new RegionNode(_loc,null,ctrl).init(); - ctrl = r; r._ltree = stop._ltree; + ctrl = r; r._ltree = fun._ltree; mem = new BulkMemPhiNode(r,mem).init(); expr = new PhiNode(r,expr).init(); } @@ -95,7 +95,7 @@ public class LoopNode extends RegionNode { CodeGen.CODE.add(CodeGen.CODE._start); CodeGen.CODE.add(mem); - return stop; + return fun; } private static boolean nested(LoopTree inner, LoopTree outer) { -- cgit v1.2.3