From d32f97238c903765dec4e9a9f3cbfa5fd12cded6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 25: Modules, Separate Compilation, and SSA Construction Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- src/main/java/com/seaofnodes/simple/IterPeeps.java | 199 ++++++++++++++++----- 1 file changed, 159 insertions(+), 40 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/IterPeeps.java') diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index a3b66e09..e65ef6d9 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -1,12 +1,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Opto; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.node.*; import java.util.Arrays; import java.util.BitSet; +import java.util.IdentityHashMap; import java.util.Random; /** @@ -38,7 +40,7 @@ import java.util.Random; *
  • Our strong invariant is that for all Nodes, either they are on the worklist * OR no peephole applies. This invariant is easy to check, although expensive. * Basically the normal "iterate peepholes to a fixed point" is linear, and this - * check is linear at each peephole step... so quadratic overall. Its a useful + * check is linear at each peephole step... so quadratic overall. It's a useful * assert, but one we can disable once the overall algorithm is stable - and * then turn it back on again when some new set of peepholes is misbehaving. * The code for this is turned on in `IterPeeps.iterate` as `assert @@ -48,11 +50,11 @@ import java.util.Random; public class IterPeeps { public final WorkList _work; - - private final WorkList _workInline; + final WorkList _workInline; + private int _cnt; public IterPeeps( long seed ) { - _work = new WorkList<>(seed); + _work = new WorkList<>(seed); _workInline = new WorkList<>(seed); } @@ -62,36 +64,53 @@ public class IterPeeps { public void addAll( Ary ary ) { _work.addAll(ary); } /** - * Iterate peepholes to a fixed point + * Iterate peepholes and inlining to a fixed point */ public void iterate( CodeGen code ) { + boolean didInline = false; + Ary defer = new Ary<>(Node.class); while( true ) { + // Clean up everything that does not grow the code iteratePeeps(code); + + // Pick an inline candidate, no real heuristic, first come, first served + boolean inlined = false; CallEndNode cend; - while( (cend=_workInline.pop())!=null ) - if( cend.inlineSmall() ) break; - if( cend==null ) return; + while( (cend=_workInline.pop()) != null) { + if( cend.isDead() ) continue; + byte inline = cend.maybeInline(); + if( inline == -1 ) defer.add(cend); + if( inline > 0 ) { + inlined = true; + break; + } + } + // Inlined, run peeps until clean again + if( inlined ) { didInline = true; continue; } + // No more candidates, check the defer list + if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress + // Some inlining happened, retry all the "try again after cleanup" calls + didInline = false; + code.addAll(defer); + defer.clear(); } } - // Only try growing inlines once the shrinking peepholes reach a fixed point. + // Run all the code-reduction and type-lifting peeps as possible private void iteratePeeps( CodeGen code ) { - assert progressOnList(code, _work, true); - int cnt=0; + assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code)); Node n; while( (n=_work.pop()) != null ) { if( n.isDead() ) continue; - if( n instanceof CallEndNode cend ) _workInline.push(cend); - cnt++; // Useful for debugging, searching which peephole broke things - var obs = CodeGen.CODE._obs; + _cnt++; // Useful for debugging, searching which peephole broke things + var obs = code._obs; // Collect peephole neighbors for graph display if( obs != null ) obs.before(n); Node x = n.peepholeOpt(); + if( n instanceof CallEndNode cend ) + _workInline.push(cend); if( x != null ) { - if( x.isDead() ) { - if( obs != null ) obs.after(n, x, true); - continue; - } + assert !x.isDead(); // Peepholes return alive answers // peepholeOpt can return brand-new nodes, needing an initial type set if( x._type==null ) x.setType(x.compute()); // Changes require neighbors onto the worklist @@ -101,22 +120,31 @@ public class IterPeeps { // Everybody gets a free "go again" in case they didn't get // made in their final form. _work.push(x); + // A self-returning peephole can have rewritten its input + // edges. The new defs gained a user and may have + // backwards, user-sensitive peepholes of their own. + for( Node z : x._inputs ) _work.push(z); // If the result is not self, revisit all inputs (because // there's a new user), and replace in the graph. if( x != n ) { - for( Node z : n. _inputs ) _work.push(z); + //for( Node z : n. _inputs ) _work.push(z); for( Node z : x._outputs ) _work.push(z); n.subsume(x); } } // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); - assert progressOnList(code, _work, true); // Very expensive assert + // Very expensive assert. + assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code)); } - if( n.isUnused() && !(n instanceof StopNode) ) + boolean unused = n.isUnused(); + if( unused ) { + assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies n.kill(); // Just plain dead - if( obs != null ) obs.after(n, x, true); + } + if( obs != null ) obs.after(n, x!=null ? x : unused ? n : null, true); } + assert !CodeGen.expensiveAssert(0) || schedulableUses(code); } @@ -133,27 +161,112 @@ public class IterPeeps { // {@link #Node.addDep} which is a side effect in an assert. The {@link // #midAssert} is used to stop this side effect. // Pessimistic solver assert - public static boolean progressOnList(CodeGen code, WorkList list, boolean dir ) { + public static boolean progressOnList(CodeGen code, WorkList list ) { code._midAssert = true; Node changed = code._stop.walk( n -> { - Node m = n; + // Ignore most in-progress things + if( n.iskeep() ) return null; + // Types must be forwards, even if on the worklist. Type nval = n.compute(); - if( (!n.iskeep() || n._nid<=8) && // Types must be forwards, even if on worklist - ( dir - ? nval.isa(n._type) // Pesi: new value lifts over old - : n._type.isa(nval) // Opto: new value falls over old - ) ) { - if( list.on(n) ) return null; - m = n.peepholeOpt(); - if( m==null ) return null; + assert nval.isa(n._type) : "Non-monotonic peep: "+n+"#"+n._nid+" old="+n._type+" new="+nval+" inputs="+inputTypes(n)+" peep="+n; + if( list.on(n) ) + return null; // On worklist is ok! + if( n instanceof CallEndNode cend ) { + if( code._iter._workInline.on(cend) ) + return null; // On inline worklist is ok! + assert cend.maybeInline() <= 0 : "Inline fired and not on worklist, CallEndNode#"+cend._nid; } - System.err.println("BREAK HERE FOR BUG"); + // Off list: must be live, in GVN table, and no peeps. + assert n.nOuts() > 0 : "Unused live node: "+n; + assert code._gvn.get(n)==n : "Not in GVN table: "+n; + Node m = n.peepholeOpt(); + assert m==null : "Peep fired and not on worklist, "+n.getClass().getSimpleName()+"#"+n._nid+" -> "+m; return m; }); code._midAssert = false; return changed==null; } + private static String inputTypes(Node n) { + StringBuilder sb = new StringBuilder("["); + for( Node in : n._inputs ) + sb.append(in==null ? "null" : in.getClass().getSimpleName()+"#"+in._nid+"="+in+":"+in._type+":keep="+in.iskeep()).append(','); + return sb.append(']').toString(); + } + + // GCM assumes every movable node can be placed no earlier than its inputs + // and no later than the LCA of its uses. Catch graphs where a use escapes + // above an input-defined branch before the later scheduling pass walks off + // the top of the idom tree. + private static final IdentityHashMap earlyCache = new IdentityHashMap<>(); + private static final BitSet VISIT = new BitSet(); + public static boolean schedulableUses(CodeGen code) { + earlyCache.clear(); + Node bad = code._stop.walk( n -> { + if( n.iskeep() || n.isDead() || n.isConst() || + n instanceof CFGNode || n instanceof PhiNode || n instanceof ProjNode ) + return null; + assert VISIT.isEmpty(); + CFGNode early = CFGNode.earlyCFG(n,earlyCache,VISIT); + VISIT.clear(); + if( early == null ) return null; + CFGNode lca = null; + for( Node use : n._outputs ) { + CFGNode ublk = useBlock(n,use); + if( ublk != null ) + lca = ublk.domLCA(lca,null); + } + if( lca == null ) return null; + if( !early.sameFun(lca) ) return null; + assert early.dominates(lca,null) : badSchedule(n,early,lca); + return null; + }); + return bad == null; + } + + private static CFGNode useBlock(Node n, Node use) { + if( use == null ) + return null; + if( use instanceof PhiNode phi ) { + CFGNode found = null; + for( int i=1; i= phi.region().nIns() ) + return null; + found = phi.region().cfg(i).domLCA(found,null); + } + return found; + } + return CFGNode.safeCFG(use); + } + + private static String badSchedule(Node n, CFGNode early, CFGNode lca) { + StringBuilder sb = new StringBuilder("Unschedulable data node ") + .append(n.getClass().getSimpleName()).append('#').append(n._nid) + .append(" early=").append(cfg(early)) + .append(" use-lca=").append(cfg(lca)) + .append(" node=").append(n).append("\ninputs:"); + for( int i=0; i