diff options
Diffstat (limited to 'chapter23')
15 files changed, 173 insertions, 115 deletions
diff --git a/chapter23/README.md b/chapter23/README.md index 59ce0dc5..7dbe385b 100644 --- a/chapter23/README.md +++ b/chapter23/README.md @@ -204,44 +204,17 @@ print(hello); // Pass along the read-only version ``` What is the type of `hello`? It is the read-only type of `List`... and `List` is -a cyclic type. Let's look at `Type.makeRO`: - -```java -public final Type makeRO() { - if( isFinal() ) return this; // First check if already read-only - return recurOpen()._makeRO().recurClose(); -} -``` - -and `isFinal()`: - -```java -// Are all reachable struct Fields are final? -public final boolean isFinal() { return recurClose(recurOpen()._isFinal()); } -boolean _isFinal() { assert _type < TCYCLIC; return true; } -``` +a cyclic type. Follow the implementation of +[`Type.makeRO`, `isFinal`, and `_isFinal`](src/main/java/com/seaofnodes/simple/type/Type.java). We call `recurOpen()` to start/open the recursive walk, do the recursion calling `_isFinal()` and end/close the recursive walk, and return a boolean answer. `_isFinal()` is NOT Java final, and is overridden in the Type subclasses. -Most subclasses just forward the problem along: - -`@Override boolean _isFinal() { return _obj._isFinal(); }` - -until we hit `TypeStruct`: - -```java -@Override boolean _isFinal() { - if( _open ) return false; // May have more non-final fields - if( VISIT.containsKey(_uid) ) // Test: been here before? - return true; // Cycles assume final - VISIT.put(_uid,this); // Set: don't do this again - for( Field fld : _fields ) - if( !fld._isFinal() ) - return false; - return true; -} -``` +Subclasses implement the check for their own representation. For example, +[`TypeMemPtr._isFinal`](src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java) +reads the pointer's access permission, while +[`TypeStruct._isFinal`](src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +walks the fields and handles cycles. Here we see a common pattern in dealing with cycles: the **test-and-set**. We check for any hard and fast answers (open structs are never read-only; they are @@ -257,9 +230,9 @@ fields asking the same question recursively. For our example, we open the recursion (set a sentinel in `VISIT`), call `makeRO` on `struct List`, which then calls `_isFinal` which then checks the `_open` flag (not open), checks the `VISIT` (not visited), sets the -UID in `VISIT` and starts walking the fields. Fields check: - -`@Override boolean _isFinal() { return _final && _t._isFinal(); }` +UID in `VISIT` and starts walking the fields. +[`Field._isFinal`](src/main/java/com/seaofnodes/simple/type/Field.java) +checks both the field's binding and its type. The first field is `List*? !next`, which is not-final, so immediately returns `false`, which stops `_isFinal` on `List` and the whole `isFinal()` call returns @@ -283,31 +256,13 @@ You can see from the repeated UIDs that `List#2` happens twice... because List is cyclic. Now we do really need to make a cyclic type, and so our `makeRO()` call falls -into the next line: - -`return recurOpen()._makeRO().recurClose();`. +into the recursive path in +[`Type.makeRO`](src/main/java/com/seaofnodes/simple/type/Type.java). Once again `recurOpen` starts/opens our recursive walk, and then we call -`_makeRO()` which is overridden in every child Type class. Let's look at -`TypeStruct`s version: - -```java -// Make a read-only version -@Override TypeStruct _makeRO() { - // Check for already visited - TypeStruct ts = (TypeStruct)VISIT.get(_name); - if( ts!=null ) return ts; // Already visited - ts = recurPre(_name,_open); // Make a new type with blank fields - Field[] flds = ts._fields; - for( Field fld : flds ) fld._final = true; - - // Now start the recursion - for( int i=0; i<flds.length; i++ ) - flds[i].setType(_fields[i]._t._makeRO()); - - return ts; -} -``` +`_makeRO()` which is overridden in the child Type classes. Follow +[`TypeStruct._makeRO` and `recurPre`](src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +for the implementation. First up is the **test-and-set**. The **test** is by type name; we attempt to get a `List` TypeStruct from `VISIT`, and if successful we return early - @@ -357,8 +312,10 @@ struct List#12 { ``` At this point the recursion unwinds and we head into the complex -`Type.recurClose()`. You might try single-stepping through the code for a few -examples; the `TypeTest.testList` test builds these types. Here is a high +[`Type.recurClose()`](src/main/java/com/seaofnodes/simple/type/Type.java). +You might try single-stepping through +[`TypeTest.testList`](src/test/java/com/seaofnodes/simple/TypeTest.java), +which builds these types. Here is a high level summary: Copy all the visited types out of `VISIT` for easier management; we might find @@ -469,64 +426,36 @@ the old buffer after growth is outside this example. Appending ## RegAlloc improvements: grouping popular uses -Chapter 22 improved color preferences and cheap-spill ordering. This chapter +Chapter 22 improved color preferences and cheap-spill ordering. This chapter adds a way to split a popular value whose uses demand incompatible registers. For example, several shifts may need the same count register while another use -needs a different register. Sharing one copy for each compatible group can avoid -inserting a separate copy at every use. +needs a different register. Sharing one copy for each compatible group can +avoid inserting a separate copy at every use. The allocator applies this to a single-definition live range with an empty -register mask and more than two fixed-register uses. It intersects overlapping +register mask and more than two fixed-register uses. It intersects overlapping use masks into groups; narrowing a group keeps it compatible with its earlier -users, so one pass suffices. Disjoint masks start separate groups. It snapshots +users, so one pass suffices. Disjoint masks start separate groups. It snapshots distinct users before rewiring their inputs, ignores scheduling-only edges, and counts a call once even when the value supplies several arguments. Grouping declines values used by multiple calls, whose register kills tend to -undo the benefit of a shared copy. The usual loop-boundary splitting remains +undo the benefit of a shared copy. The usual loop-boundary splitting remains the fallback, including splitting an existing copy when all uses have the same -loop depth. Cold-first loop splitting is left for Chapter 24; area/cost spill +loop depth. Cold-first loop splitting is left for Chapter 24; area/cost spill ranking remains for Chapter 25. -Chapter 21's adjacent-copy forwarding also carries forward: after coloring, -a sole use in the next instruction can read the source register when its -operand mask permits it and no two-address tie is broken. The table below -includes this cleanup and the lazy memory forward port. Cohort 22 now also includes the two zero-move C return -ABI checks added since the earlier audit (26 entries instead of 24). - -Run `make spill-stats` in this directory. All rows below use **this chapter's -compiler**, seed 123, and frozen source/target combinations from each cohort. -The Windows run combines x86 SystemV/Win64 and RISC-V/ARM SystemV. Diagnostic -machine graphs are checked separately and do not contribute to the counts. - -| Program cohort | Compilations | Retained moves | Loop-weighted moves | -|---|---:|---:|---:| -| Chapter 20 | 39 | 323 | 442 | -| Chapter 21 | 52 | 433 | 965 | -| Chapter 22 | 26 | 67 | 67 | -| Chapter 23 | 30 | 78 | 225 | -| **Total** | **147** | **901** | **1,699** | - -`_spills` counts retained SplitNodes, including register moves; `_spillScaled` -weights them by `8^loopDepth`. These estimate compiler-generated moves, not -runtime memory traffic. The reporter prints individual compilations and sums -by CPU/ABI, and still reports failure when a spill expectation or execution -check fails. - -In the earlier audit, before adjacent-copy forwarding, disabling grouping produced -**the same 933 moves / 1,745 weighted moves**. The original grouping code also -has those totals. This suite therefore shows no spill improvement from grouping; -the reduced machine-graph regression exercises its compatibility and call rules, -including a null-mask crash in the old implementation. A plausible allocator -heuristic needs measurements on workloads that reach it before claiming a win. - -For the older cohorts alone, Chapter 22's compiler produced 838 moves / 1,496 -weighted moves; this compiler then produced 849 / 1,514. That comparison includes -changes outside allocation. In particular, Chapter 20's frozen String input -survives optimization here and costs 16 weighted moves; Chapter 22 eliminated -it at this seed. It would be misleading to attribute that difference to grouping. - -The original 64-bit `person21` and guarded `stringHash21` inputs preserve cohort -21. The revised String input and two encoding tests enabled in this chapter -belong to cohort 23. Keeping these cohorts fixed makes subsequent comparisons -meaningful even as the language and its tests grow. +Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each +cell is the sum of `_spillScaled`: retained split moves, including register +copies, weighted by loopDepth. Lower is better. **# tests counts +compilations** (program/CPU/ABI cases), including zero-spill cases, rather than +JUnit methods. The count and membership of each row stay fixed across columns. + +<!-- spill-matrix:start --> +| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | Ch 23 | +|---|---:|---:|---:|---:|---:| +| Ch 20 | 39 | 360 | 576 | 430 | 442 | +| Ch 21 | 52 | | 1,072 | 960 | 961 | +| Ch 22 | 26 | | | 63 | 63 | +| Ch 23 | 24 | | | | 103 | +<!-- spill-matrix:end --> diff --git a/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java index c873e74c..c4b96c5c 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -47,7 +47,12 @@ public class IterPeeps { private final WorkList<Node> _work; - public IterPeeps( long seed ) { _work = new WorkList<>(seed); } + private final WorkList<CallEndNode> _workInline; + + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } @SuppressWarnings("unchecked") public <N extends Node> N add( N n ) { return (N)_work.push(n); } @@ -58,12 +63,24 @@ public class IterPeeps { * Iterate peepholes to a fixed point */ public void iterate( CodeGen code ) { + while( true ) { + iteratePeeps(code); + CallEndNode cend; + while( (cend=_workInline.pop())!=null ) + if( cend.inlineSmall() ) break; + if( cend==null ) return; + } + } + + // Only try growing inlines once the shrinking peepholes reach a fixed point. + private void iteratePeeps( CodeGen code ) { assert progressOnList(code); int cnt=0; 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; if( obs != null ) obs.before(n); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter23/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index cdf12a12..e83e5cba 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -108,6 +108,99 @@ public class CallEndNode extends CFGNode implements MultiNode { return null; } + // Clone only tiny, straight-line boilerplate, after ordinary peeps settle. + // Larger bodies still use the existing single-caller, non-cloning inline. + public boolean inlineSmall() { + if( isDead() || _folding || nIns()!=2 || !(in(0) instanceof CallNode call) ) return false; + Node fptr = call.fptr(); + if( !(fptr instanceof ConstantNode) || + !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) ) + { addDep(fptr); return false; } + if( call.err()!=null ) return false; + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + if( fun._folding ) return false; + int len = smallBody(fun); + if( len==0 ) return false; + // All callers consume the three normal return projections. + for( Node use : _outputs ) + if( !((use instanceof ProjNode p && p._idx>=0 && p._idx<3) || + (use instanceof CProjNode cp && cp._idx==0)) ) return false; + + // Substitute control and arguments directly; no new function identity, + // parameter Phis, or return address is needed for this straight line. + Node[] copy = new Node[len]; + for( int i=0; i<len; i++ ) { + Node n = TINYBODY[i]; + copy[i] = n==fun ? call.ctrl() : + n instanceof ParmNode parm ? (parm._idx==0 ? null : call.arg(parm._idx)) : + n==ret ? null : n.copyEmpty(); + } + for( int i=0; i<len; i++ ) { + Node n = TINYBODY[i]; + if( n instanceof StoreNode || n instanceof MemMergeNode ) { + for( Node in : n._inputs ) copy[i].addDef(mapped(in,copy)); + CodeGen.CODE.add(copy[i]); + } + } + Node[] result = new Node[3]; + for( int i=0; i<3; i++ ) result[i] = mapped(ret.in(i),copy).keep(); + keep(); + call.unlink_all(); + CodeGen.CODE.add(fun); + CodeGen.CODE.addAll(fun._outputs); + // subsume kills each projection; retain CallEnd until all are replaced. + while( nOuts()>1 ) { + Node use = out(0)==null ? out(1) : out(0); + int idx = use instanceof ProjNode p ? p._idx : ((CProjNode)use)._idx; + CodeGen.CODE.addAll(use._outputs); + use.subsume(result[idx]); + } + unkill(); + for( Node n : result ) n.unkill(); + CodeGen.CODE.invalidateIDepthCaches(); + return true; + } + + private static Node mapped(Node n, Node[] copy) { + for( int i=0; i<copy.length; i++ ) + if( TINYBODY[i]==n ) return copy[i]; + return n; // Constants outside the body are shared. + } + + // Bounded recognition of initializer boilerplate. Walk uses from the entry + // and stop at Return, never following callers or constant inputs. This also + // avoids scanning sparse MemMerge input arrays while a large body shrinks. + // Watch this small prefix, including an unsupported node that may fold. + private static final Node[] TINYBODY = new Node[15]; // Tiny worklist + private int smallBody(FunNode fun) { + ReturnNode ret = fun.ret(); + for( Node in : ret._inputs ) + if( in!=null ) addDep(in); + if( ret.ctrl()!=fun ) return 0; + TINYBODY[0] = fun; + int len=1; + for( int i=0; i<len; i++ ) { + Node n = TINYBODY[i]; + addDep(n); + if( n==ret ) continue; + if( n instanceof ParmNode parm && parm.region()!=fun ) return 0; + if( n!=fun && !(n instanceof ParmNode) && + !(n instanceof StoreNode) && !(n instanceof MemMergeNode) ) + return 0; + if( n.nOuts()>TINYBODY.length ) return 0; + for( Node use : n._outputs ) { + if( use==null ) continue; + int j=0; + while( j<len && TINYBODY[j]!=use ) j++; + if( j<len ) continue; + if( len==TINYBODY.length ) { addDep(use); return 0; } + TINYBODY[len++] = use; + } + } + return len; + } + @Override public Node pcopy(int idx) { return _folding ? in(1).in(idx) : null; } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 041e0d06..ac3b81ec 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,11 +1,13 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter12Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index 23d0ef37..6377bc14 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -47,6 +48,7 @@ public class Chapter14FloatTest { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java index da7e50bc..c342eeed 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -2,12 +2,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter14Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 66a50d0f..d0a42ccf 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,7 @@ import static org.junit.Assert.*; public class Chapter15Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 692ac8d5..f73cbf57 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -1,12 +1,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter16Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 59bd3b0c..24dc0229 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -1,12 +1,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter17bTest { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java index e3dd222d..902344ed 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -115,6 +115,7 @@ public class Chapter18Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( @@ -454,7 +455,7 @@ if (i2i) return i2i(arg); return f2f(o)(1); """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,#2,#2); return Parm_i(i2i.o,i64); ]", code._stop.toString()); + assertEquals("Stop[ return Phi(Region,#2,1); return Parm_i(i2i.o,i64); ]", code._stop.toString()); assertEquals("1", Eval2.eval(code, 2)); } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java index d1e5fa70..23b45e46 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -8,6 +8,7 @@ import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -32,6 +33,7 @@ public class Chapter19Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen(""" diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 36f2f7b0..08a23ef0 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -92,6 +92,7 @@ return f(s); } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen("return 0;"); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java index 7f4b86d5..f3cc7512 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import java.io.IOException; import java.nio.file.*; +import org.junit.Ignore; import org.junit.Test; // Revised or newly enabled allocation examples in Chapter 23. @@ -14,6 +15,7 @@ public class Chapter23AllocTest { Chapter23Test.testCPU(src,"arm" , "SystemV", 1,null); } + @Ignore @Test public void testJig21() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); @@ -22,6 +24,7 @@ public class Chapter23AllocTest { Chapter23Test.testCPU(src,"arm" , "SystemV",-1,null); } + @Ignore @Test public void testJig22() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 58b8d3e4..0feaa5de 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -83,6 +83,7 @@ public class Chapter23Test { } } + @Ignore @Test public void testJig() throws IOException { String src = diff --git a/chapter23/src/test/java/com/seaofnodes/simple/progs/jig.smp b/chapter23/src/test/java/com/seaofnodes/simple/progs/jig.smp index f7a5d202..29987d8e 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/progs/jig.smp +++ b/chapter23/src/test/java/com/seaofnodes/simple/progs/jig.smp @@ -1,5 +1,5 @@ // -*- mode: java; -*- -val fib = {int n -> +val _fib = {int n -> int temp=0; int f1=1; int f2=1; @@ -13,4 +13,4 @@ val fib = {int n -> return f2; }; -fib(10); +_fib(10); |