From 300d2a9c3672acacc8bdd8d5370a424651a00571 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 18 Oct 2026 22:09:58 -0700 Subject: Cleanup & backport The phase rework, made new phases explicit and add them to the CodeGen driver. Fix the flag-spilling on X86 and ARM. Fix the GCM conservative anti-deps and backport. --- .../main/java/com/seaofnodes/simple/CodeGen.java | 112 +++++++++++---------- .../com/seaofnodes/simple/GlobalCodeMotion.java | 11 +- .../main/java/com/seaofnodes/simple/TypeCheck.java | 15 +++ .../simple/print/SimpleGraphObserver.java | 2 +- 4 files changed, 80 insertions(+), 60 deletions(-) create mode 100644 chapter18/src/main/java/com/seaofnodes/simple/TypeCheck.java (limited to 'chapter18/src/main/java') diff --git a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java index 864b3a1a..e5ac8530 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/CodeGen.java @@ -1,4 +1,4 @@ - package com.seaofnodes.simple; +package com.seaofnodes.simple; import com.seaofnodes.graph.GraphObserver; @@ -20,10 +20,45 @@ public class CodeGen { public enum Phase { - Parse, Opto, TypeCheck, Schedule, LocalSched, RegAlloc; + Parse, // Build ideal IR from source + Iter, // Pessimistic peepholes + TypeCheck, // Check the surviving ideal graph + LoopTree, // Discover loops and connect nonreturning paths + Schedule, // Global code motion + LocalSched; // Order instructions within blocks + } public Phase _phase; + // Run through target, skipping phases already completed. + public CodeGen driver(Phase target) { + step(target, Phase.Parse, this::parse); + step(target, Phase.Iter, this::iter); + step(target, Phase.TypeCheck, this::typeCheck); + step(target, Phase.LoopTree, this::loopTree); + step(target, Phase.Schedule, this::GCM); + step(target, Phase.LocalSched, this::localSched); + return this; + } + + private void step(Phase target, Phase next, Runnable work) { + if( next.ordinal()>target.ordinal() || (_phase!=null && _phase.ordinal()>=next.ordinal()) ) return; + work.run(); + } + + public final long[] _times = new long[Phase.values().length]; + private CodeGen phase(Phase next, boolean ordered, Runnable work) { + assert ordered : "Cannot run "+next+" after "+_phase; + _phase = next; + long t0 = System.currentTimeMillis(); + try { work.run(); } + finally { _times[next.ordinal()] = System.currentTimeMillis()-t0; } + if( _obs!=null ) _obs.phase(next.name()); + return this; + } + + + public final String _src; // Compile-time known initial argument type public final TypeInteger _arg; @@ -46,71 +81,38 @@ public class CodeGen { public CodeGen( String src ) { this(src,TypeInteger.BOT); } public CodeGen parse() { - assert _phase == null; - _phase = Phase.Parse; - _linker.clear(); - - P = new Parser(_src,_arg); - _stop = P.parse(); - _start = Parser.START; // Capture global start - if( _obs != null ) _obs.phase("Parse"); - P = null; // No longer parsing - return this; - } + return phase(Phase.Parse, _phase==null, () -> { + _linker.clear(); - public CodeGen opto() { - assert _phase == Phase.Parse; - _phase = Phase.Opto; - - // Optimization - IterPeeps.iterate(_stop); - - // TODO: - // Optimistic - if( _obs != null ) _obs.phase("Opto"); - return this; - } - - public CodeGen typeCheck() { - // Demand phase Opto for cleaning up dead control flow at least, - // required for the following GCM. - assert _phase == Phase.Opto; - _phase = Phase.TypeCheck; - - // Type check - Parser.ParseException err = _stop.walk(n -> { - Parser.ParseException msg = n.err(); - if( msg != null && _obs != null ) _obs.error(n, msg.getMessage()); - return msg; + P = new Parser(_src,_arg); + _stop = P.parse(); + _start = Parser.START; // Capture global start + P = null; // No longer parsing }); - if( err != null ) - throw err; - if( _obs != null ) _obs.phase("TypeCheck"); - return this; } + // Pessimistic peepholes reach a fixed point after parsing. + public CodeGen iter() { return phase(Phase.Iter, _phase==Phase.Parse, () -> IterPeeps.iterate(_stop)); } - public CodeGen GCM() { - assert _phase == Phase.TypeCheck; - _phase = Phase.Schedule; + public CodeGen typeCheck() { return phase(Phase.TypeCheck, _phase==Phase.Iter, () -> TypeCheck.run(this)); } - // Build the loop tree, fix never-exit loops - _start.buildLoopTree(_stop); + public CodeGen loopTree() { + return phase(Phase.LoopTree, _phase==Phase.TypeCheck, () -> _start.buildLoopTree(_stop)); + } - // TODO: - // loop unroll, peel, RCE, etc - GlobalCodeMotion.buildCFG(_start,_stop); - return this; + public CodeGen GCM() { + return phase(Phase.Schedule, _phase==Phase.LoopTree, () -> { + // TODO: + // loop unroll, peel, RCE, etc + GlobalCodeMotion.buildCFG(_start,_stop); + }); } // Local (basic block) scheduler phase, a classic list scheduler public CodeGen localSched() { - assert _phase == Phase.Schedule; - _phase = Phase.LocalSched; - ListScheduler.sched(this); - return this; - } + return phase(Phase.LocalSched, _phase==Phase.Schedule, () -> ListScheduler.sched(this)); + } // Reverse from a constant function pointer to the IR function being called public FunNode link( TypeFunPtr tfp ) { diff --git a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 8221ede1..2019b714 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -260,10 +260,11 @@ public abstract class GlobalCodeMotion { lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; case PhiNode phi: - // Repeat anti-dep for matching Phi inputs. - // No anti-dep edges but may raise the LCA. + // Inputs carrying different memory might overwrite this alias. + // Raise the LCA for those paths; unchanged memory does not + // clobber the load. No scheduling edge to the Phi. for( int i=1; i= defblk.idepth(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence if( anti[stblk._nid]==load._nid ) { lca = stblk.domLCA(lca,null); // Raise Loads LCA diff --git a/chapter18/src/main/java/com/seaofnodes/simple/TypeCheck.java b/chapter18/src/main/java/com/seaofnodes/simple/TypeCheck.java new file mode 100644 index 00000000..a41e4161 --- /dev/null +++ b/chapter18/src/main/java/com/seaofnodes/simple/TypeCheck.java @@ -0,0 +1,15 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.Parser; + +abstract class TypeCheck { + static void run(CodeGen code) { + Parser.ParseException err = code._stop.walk(n -> { + Parser.ParseException msg = n.err(); + if( msg != null && code._obs != null ) code._obs.error(n, msg.getMessage()); + return msg; + }); + if( err != null ) + throw err; + } +} diff --git a/chapter18/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/chapter18/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index b2dd3107..4db81c70 100644 --- a/chapter18/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/chapter18/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -17,7 +17,7 @@ public class SimpleGraphObserver extends GraphCapture { @Override protected void compile(String src) { _code = new CodeGen(src); _code._obs = this; - _code.parse().opto().typeCheck(); + _code.driver(CodeGen.Phase.TypeCheck); } @Override protected String phase() { return _code._phase.name(); } @Override protected int pos() { return _code.P != null ? _code.P.pos() : -1; } -- cgit v1.2.3