From 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 7 Oct 2026 19:10:51 -0700 Subject: Towrds getting RA spill counts comparable Ignore JIGs. Get test suites more conical, so reg alloc spill counts are comparable --- chapter23/README.md | 151 ++++++--------------- .../main/java/com/seaofnodes/simple/IterPeeps.java | 19 ++- .../com/seaofnodes/simple/node/CallEndNode.java | 93 +++++++++++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 2 + .../com/seaofnodes/simple/Chapter14FloatTest.java | 2 + .../java/com/seaofnodes/simple/Chapter14Test.java | 2 + .../java/com/seaofnodes/simple/Chapter15Test.java | 1 + .../java/com/seaofnodes/simple/Chapter16Test.java | 2 + .../java/com/seaofnodes/simple/Chapter17bTest.java | 2 + .../java/com/seaofnodes/simple/Chapter18Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 2 + .../java/com/seaofnodes/simple/Chapter20Test.java | 1 + .../com/seaofnodes/simple/Chapter23AllocTest.java | 3 + .../java/com/seaofnodes/simple/Chapter23Test.java | 1 + .../test/java/com/seaofnodes/simple/progs/jig.smp | 4 +- 15 files changed, 173 insertions(+), 115 deletions(-) (limited to 'chapter23') 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 +| 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 | + 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 _work; - public IterPeeps( long seed ) { _work = new WorkList<>(seed); } + private final WorkList _workInline; + + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } @SuppressWarnings("unchecked") public 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; i1 ) { + 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; iTINYBODY.length ) return 0; + for( Node use : n._outputs ) { + if( use==null ) continue; + int j=0; + while( j +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); -- cgit v1.2.3