diff options
65 files changed, 2070 insertions, 425 deletions
diff --git a/chapter22/Makefile b/chapter22/Makefile index 55d5e70a..33855ddf 100644 --- a/chapter22/Makefile +++ b/chapter22/Makefile @@ -138,6 +138,12 @@ tests: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag @$(JVM) org.junit.runner.JUnitCore $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap +spill-stats: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag + @[ -d build/objs ] || mkdir -p build/objs + @$(JVM) com.seaofnodes.simple.SpillStats + +.PHONY: spill-stats + fuzzer: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag @echo "fuzzing " $(test_cp) @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap diff --git a/chapter22/README.md b/chapter22/README.md index f31dcf19..bcb286d0 100644 --- a/chapter22/README.md +++ b/chapter22/README.md @@ -41,7 +41,7 @@ semantics - just the ability to nest type definitions. struct Outer { struct Inner { int in; - int pi = 3.14; + flt pi = 3.14; }; int out; }; @@ -53,6 +53,7 @@ need to be stored in each instances. Instead one copy is kept in a global space (not really a *class* object yet) and loaded from there. In this example: + - Instances of the `Outer` struct have a single `int` field `out`. - Instances of the `Inner` struct have a single `int` field `in`. - There exists a `Outer.Inner.pi` field in a global space with value `3.14`. @@ -68,7 +69,7 @@ We can now call external / FFI functions, and they are declared like any other variable except being assigned "C". Here is the binding for the libc `write` call: -`{ i32 fd, i32 buf, i32 len -> i32 } write = "C";` +`{ i32 fd, i64 buf, u32 len -> u32 } write = "C";` Any final variable assigned as "C" will be considered defined externally. The syntax of this might change slightly to avoid ambiguity with assign the same @@ -82,7 +83,8 @@ name `write` has to be unique when linking. The `sys` struct includes `libc` bindings, and any default library code including e.g. printing support and collections. As of this chapter it -includes minimal libc bindings and an easy print: +includes minimal libc bindings and an easy print. This excerpt shows the +parts used above: ```java // top-level default import @@ -91,7 +93,7 @@ struct sys { /** https://www.man7.org/linux/man-pages/man2/<libc call>.2.html */ struct libc { // fd buf len -> len - { i32 i64 i32 -> i32 } write = "C"; + { i32 i64 u32 -> u32 } write = "C"; // addr len prot flags fd off -> void* { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; // mmap flags @@ -105,8 +107,7 @@ struct sys { struct io { val p = { u8[~] str -> i64 ptr = str; // cast array base to i64 - i32 len = str#; // cast length to signed - return sys.libc.write(1,ptr,len); + return sys.libc.write(1,ptr,str#); }; }; }; @@ -166,29 +167,69 @@ The form ``` `0` ``` makes a `u8` value with the ASCII character `0`. ## Continuous Improvement -In the rush to get executable code from -[Chapters 19](https://github.com/SeaOfNodes/Simple/tree/linear-chapter19), -[Chapters 20](https://github.com/SeaOfNodes/Simple/tree/linear-chapter20), and -[Chapters 21](https://github.com/SeaOfNodes/Simple/tree/linear-chapter21), we -wrote a lot of code in a hurry. That also means we wrote a lot of bugs (sad -face), and will be paying the price for a few chapters. In this chapter we -also found and fixed a number of bugs, here's a sample: - -- x86 encoding bugs: -- - `imul` with immediate forms and `setXX` had incorrect `REX` forms. -- - x86 `div` was taking `RAX,RDX` as the second *input* register; they are already - hardwired as the *first* input register. -- - Many x86 ops that kill `flags` did not state so in the port. -- - Short forms for some x86 ops (e.g. using the `inc` vs `add+1`) -- Global Code Motion `ScheduleLate` missed visiting values only visible around - loop backedges; also was adding extra dependence edges between loads and - stores with different aliasing. -- Inlining would reset the **idepth** (as expected) but then use the existing - `CallNode` and `FunNode` that are *folding* but not yet peep'd away - leading - to incorrect **idepth** calculations. - -Many more bugs got fixed, but this sample should give an idea of the continuous -improvements going on. These happen because we have finally reached a point -where we can aggressive test again - we are writing Real (Simple) Code (tm) and -running it... and crashing on these bugs. Compilers are big, complex, beasties -and some amount of bugs and bug fixing is to be expected. +Executing larger programs exposes mistakes that graph-only tests can miss. +During the original development of this chapter, these included x86 instruction +encodings and flag clobbers, scheduling around loop backedges and memory stores, +and stale dominator depths during inlining. Corrections are being moved into the +earliest applicable chapters so readers can build on working compiler snapshots. +Native tests check both output and process exit status; emulator tests check the +returned values and memory as well as successful execution. + +## RegAlloc improvements: better color bias + +Chapter 21 introduced conservative copy coalescing. Here we improve the register +preferences used when related live ranges cannot coalesce. A copy chain can take +an already assigned register even at its terminal definition; a loop Phi prefers +its backedge's register, avoiding a move on each iteration when possible. + +When no live range is trivially colorable, cheap values make better spill +candidates. We favor a cloneable definition with distant or multiple uses over +one already adjacent to its only use, then callee-save values whose long spans +are cheap to split. Register order breaks ties between callee saves. These are +small preferences, not a general cost model. Grouping popular values by register +class is left for Chapter 23, cold loop splits for 24, and area/cost ranking for 25. + +Run `make spill-stats` in this directory. Each row below uses **this chapter's +compiler**, default worklist seed 123, and the same source/target combinations +as the earlier cohort. The Windows run combines x86 SystemV/Win64 and RISC-V/ARM +SystemV. Diagnostic graphs and mask regressions do not contribute to the totals. + +| Program cohort | Compilations | Split/move count | Loop-weighted count | +|---|---:|---:|---:| +| Chapter 20 | 39 | 324 | 443 | +| Chapter 21 | 52 | 447 | 986 | +| Chapter 22 | 24 | 67 | 67 | +| **Total** | **115** | **838** | **1,496** | + +`_spills` counts retained SplitNodes, including register moves; `_spillScaled` +weights each by `8^loopDepth`. These are compiler estimates, not measured runtime +memory traffic. The reporter also prints individual allocations and CPU/ABI sums. +Chapter 21's original `int age` person example is preserved as `person21`; this +chapter's `i32 age` version and revised infinite-loop example belong to cohort 22. + +For a controlled comparison, the same compiler and correctness fixes with +Chapter 21's color preferences and spill ordering produce 885 moves and 1,543 +weighted moves. This chapter saves **47 weighted moves (3.0%)**. RISC-V BrainFuck +improves from 42 to 28 and ARM from 34 to 28 in each of its two cohorts. Some +MergeSort cases and RISC-V Sieve each cost one more move. Summing the whole suite +shows whether those local tradeoffs pay off. + +The original Chapter 22 snapshot, which mixed several later heuristics, produced +854 moves and 1,736 weighted moves on these same 115 compilations. The corrected, +staged version saves 240 weighted moves (13.8%). Neither comparison should be +confused with comparing entire compiler chapters: lowering also changes. For +example, the frozen Chapter 20 String input has no explicit return, and Chapter +22's default-return handling eliminates that workload at the default seed. + +The full suite passes 416 tests plus the fuzzer; the statistics runner passes +55 selected tests. Routine backend comparisons use a fixed optimizer seed: +shuffling optimizer worklists should normalize to essentially the same graph, +so repeating allocation on those graphs adds little coverage. Use seed variation +when investigating optimizer normalization or worklist-order failures. + +Two pre-existing failures found during the review remain in the +[backport queue](../docs/chapter-backports.md): String fails during loop +analysis/scheduling at other optimizer seeds, and returning a function pointer +fails during relocation after Opto incorrectly deletes the referenced function. +Their reproductions and validation history are retained +there as separate correctness work. diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index e9b5eb2e..f4ce4366 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -40,8 +40,8 @@ abstract public class BuildLRG { int uidx = n.out(0)._inputs.find(n); RegMask mask1 = n.in (1) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(1))._mask; RegMask mask2 = n.in (2) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(2))._mask; - RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): alloc.lrg(n )._mask; - if( !mask1.overlap(masko) && mask2.overlap(masko) ) + RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): mach.outregmap(); + if( masko!=null && !mask1.overlap(masko) && mask2.overlap(masko) ) n.swap12(); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java index fdd4e2f9..1268db6a 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -207,20 +207,7 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - // Disallow clone-ables from killing registers. Just fail - // them and re-clone closer to target... so no kill. - // Special case for Intel XOR used to zero. - Node n = (Node)m; - CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0(); - if( m.isClone() && // Must be clonable - (n.nOuts()>1 || // Has many users OR - // Only 1 user but effective use is remote block - effUseBlk != n.cfg0() )) - // Then fail the clonable; it should split or move - alloc.fail(alloc.lrg((Node)m)); - // Else clonable cannot move - else if( !tlrg.sub(killMask) ) - alloc.fail(tlrg); + if( !tlrg.sub(killMask) ) alloc.fail(tlrg); } } } @@ -438,13 +425,13 @@ abstract public class IFG { private static int pickRiskyScore( LRG lrg ) { // Pick single-def clonables that are not right next to their single-use. // Failing to color these will clone them closer to their uses. - if( !lrg._multiDef && lrg._machDef.isClone() ) { - Node def = ((Node)lrg._machDef); - Node use = ((Node)lrg._machUse); + if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) { + Node def = (Node)lrg._machDef; + Node use = (Node)lrg._machUse; CFGNode cfg = def.cfg0(); - if( cfg != use.cfg0() || // Different blocks OR + if( lrg._multiUse || cfg != use.cfg0() || // Many uses or different blocks OR // Same block, but not close - cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) + cfg._outputs.find(def)+1 < cfg._outputs.find(use) ) return 1000000; } @@ -452,7 +439,7 @@ abstract public class IFG { // and very cheap to spill. if( lrg._machDef instanceof CalleeSaveNode ) return 1000000-2-lrg._mask.firstReg(); - if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && + if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) return 1000000-1; @@ -506,7 +493,7 @@ abstract public class IFG { private static int biasable(Node split) { if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1 - if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Yes biasable, advance is slot 1 + if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Prefer the backedge in loops if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 835ca2a5..c0be96f1 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -176,17 +176,35 @@ public class RegAlloc { if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } + // Optional diagnostic for values accidentally shared across functions. + //assert verifyFunctionLocalEdges(); + // Top driver: repeated rounds of coloring and splitting. byte round=0; while( !graphColor(round) ) { split(round); if( round >= 7 ) // Really expect to be done soon - throw Utils.TODO("Allocator taking too long"); + throw new IllegalStateException("Register allocation made no progress after eight rounds"); round++; } postColor(); // Remove no-op spills } + boolean verifyFunctionLocalEdges() { + for( CFGNode bb : _code._cfg ) { + if( bb instanceof StartNode ) continue; + FunNode fun = bb.fun(); + for( Node use : bb._outputs ) + if( use instanceof MachNode mach && !(use instanceof ParmNode) ) + for( int i=1; i<use.nIns(); i++ ) { + Node def = use.in(i); + if( def==null || mach.regmap(i)==null || def.cfg0()==null || def.cfg0() instanceof StartNode ) continue; + assert def.cfg0().fun()==fun : "Cross-function register edge: "+def.uniqueName()+" -> "+use.uniqueName()+" input "+i; + } + } + return true; + } + private boolean graphColor(byte round) { _failed.clear(); _lrgs.clear(); @@ -233,13 +251,11 @@ public class RegAlloc { if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && - (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) + (lrg._1regDefCnt + lrg._1regUseCnt) > 0 && + // A fixed-register clone with flexible uses must split at the uses. + !(lrg._1regDefCnt==1 && lrg._machDef.isClone() && lrg._1regUseCnt==0) ) return splitEmptyMaskSimple(round,lrg); - // Repeated single-reg uses from a single def. Special for archs - // with more fixed regs. - if( !lrg._multiDef && lrg._1regDefCnt <= 1 && lrg._1regUseCnt > 2 ) - if( splitEmptyMaskByUse(round,lrg) ) - return true; + // More complex conflicts use loop-boundary splitting. } // Generic split-by-loop depth. @@ -255,91 +271,20 @@ public class RegAlloc { // Split just after def if( lrg._1regDefCnt==1 && !lrg._machDef.isClone() ) - // Force must-split, even if a prior split same block because register - // conflicts. Example: + // An earlier copy is reusable only if no intervening clobber. + // Being in the same block alone is insufficient. Example: // alloc // V1/rax - forced by alloc // alloc // V2/rax - kills prior RAX // st4 [V1],len - No good, must split around - insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/); + insertAfterAndReplace(makeSplit("def/empty1",round,lrg),(Node)lrg._machDef,false); // Split just before use - if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) ) + if( lrg._1regUseCnt==1 ) insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg); return true; } - // Single-def live range with an empty mask. There are many single-reg - // uses. Theory is there's many repeats of the same reg amongst the uses. - // In of splitting once per use, start by splitting into groups based on - // required input register. - boolean splitEmptyMaskByUse( byte round, LRG lrg ) { - Node def = (Node)lrg._machDef; - - // Look at each use, and break into non-overlapping register classes. - Ary<RegMask> rclass = new Ary<>(RegMask.class); - boolean done=false; - int ncalls=0; - while( !done ) { - done = true; - for( Node use : def._outputs ) - if( use instanceof MachNode mach ) { - if( mach instanceof CallNode ) ncalls++; - for( int i=1; i<use.nIns(); i++ ) - if( use.in(i)==def ) - done = putIntoRegClass( rclass, mach.regmap(i) ); - } - } - - // See how many register classes we split into. Generally not - // productive to split like this across calls, which are going to kill - // all registers anyways. - if( rclass._len <= 1 || ncalls > 1 ) return false; - - // Split by class - Ary<Node> ns = new Ary<>(Node.class); - for( RegMask rmask : rclass ) { - ns.addAll(def._outputs); - Node split = makeSplit(def,"popular",round,lrg,rmask); - split.insertAfter( def ); - if( split.nIns()>1 ) split.setDef(1,def); - // all uses by class to split - for( int j=0; j < def._outputs._len; j++ ) { - Node use = def._outputs.at(j); - if( use instanceof MachNode mach && use!=split ) { - // Check all use inputs for n, in case there's several - for( int i = 1; i < use.nIns(); i++ ) - // Find a def input, and check register class - if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) { - RegMask m = mach.regmap( i ); - if( m!=null && mach.regmap( i ).overlap( rmask ) ) - // Modify use to use the split version specialized to this rclass - { use.setDefOrdered( i, split ); j--; break; } - } - } - } - ns.clear(); - } - return true; - } - - - // Put use into a register class, perhaps adding a class or perhaps - // narrowing a class (and causing a repeat) - private static boolean putIntoRegClass( Ary<RegMask> rclass, RegMask rmask ) { - for( int i=0; i<rclass._len; i++ ) { - RegMask omask = rclass.at(i); - if( omask.and(rmask) == omask ) return true; // Within the same register class - if( omask.overlap(rmask) ) { - rclass.set(i,new RegMask(omask.copy().and(rmask))); - return false; // Need go again - } - } - // Add a new class, no need to go again - rclass.push(rmask); - return true; - } - // Self conflicts require Phis (or two-address). // Insert a split after every def. boolean splitSelfConflict( byte round, LRG lrg ) { @@ -491,8 +436,8 @@ public class RegAlloc { void findAllLRG( LRG lrg ) { _ns.clear(); int wd = 0; - _ns.push((Node)lrg._machDef); - _ns.push((Node)lrg._machUse); + if( lrg._machDef!=null ) _ns.push((Node)lrg._machDef); + if( lrg._machUse!=null ) _ns.push((Node)lrg._machUse); while( wd < _ns._len ) { Node n = _ns.at(wd++); if( lrg(n)!=lrg ) continue; @@ -547,9 +492,9 @@ public class RegAlloc { } } - private Node makeSplit( Node def, String kind, byte round, LRG lrg, RegMask umask ) { - // Clone simple constants if possible - Node split = def instanceof MachNode mach && mach.isClone() && (umask==null || mach.outregmap().overlap(umask)) + private Node makeSplit( Node def, String kind, byte round, LRG lrg, RegMask use ) { + // A clone must be able to satisfy the use's register class. + Node split = def instanceof MachNode mach && mach.isClone() && (use==null || mach.outregmap().overlap(use)) ? mach.copy() : _code._mach.split(kind,round,lrg); _lrgs.put(split,lrg); @@ -615,10 +560,10 @@ public class RegAlloc { break; hi = hi.in(1); } - // Check no clobbers - for( int idx = j-1; bb.out(idx) != hi; idx++) { + // Walk backward from the later copy, including instructions without results. + for( int idx = j-1; bb.out(idx) != hi; idx--) { Node n = bb.out(idx); - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } lo.setDefOrdered(1,hi.in(1)); @@ -626,6 +571,12 @@ public class RegAlloc { } + private boolean clobbers(Node n, int reg) { + LRG lrg = lrg(n); + return lrg!=null && (lrg._reg==reg || lrg._reg==-1 && lrg._mask.size1() && lrg._mask.firstReg()==reg) || + n instanceof MachNode mach && mach.killmap()!=null && mach.killmap().test(reg); + } + public boolean sameBlockNoClobber( SplitNode split ) { Node def = split.in(1); CFGNode cfg = def.cfg0(); @@ -639,7 +590,7 @@ public class RegAlloc { Node n = cfg.out(idx); if( n==def0 ) return true; // No clobbers if( lrg(n) == lrg(def) ) return false; // Self conflict - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } throw Utils.TODO(); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index ec0c4e30..f73cd9a1 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -72,16 +72,12 @@ public class RegMask { : Long.numberOfTrailingZeros(_bits1)+64); } public short nextReg(short reg) { - if( reg<64 ) { - long bits0 = _bits0 >> (reg+1); - if( bits0!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits0)); - reg=64; + if( reg < 63 ) { + long bits0 = _bits0 & (-1L << (reg+1)); + if( bits0!=0 ) return (short)Long.numberOfTrailingZeros(bits0); } - long bits1 = _bits1 >> (reg-64+1); - if( bits1!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits1)); - return -1; + long bits1 = reg < 64 ? _bits1 : reg < 127 ? _bits1 & (-1L << (reg-63)) : 0; + return bits1==0 ? -1 : (short)(64+Long.numberOfTrailingZeros(bits1)); } boolean isEmpty() { return _bits0==0 && _bits1==0; } @@ -98,8 +94,8 @@ public class RegMask { // Has exactly 1 bit set public boolean size1() { - return ((_bits0 & -_bits0)==_bits0 && _bits1==0) || - ((_bits1 & -_bits1)==_bits1 && _bits0==0); + return !isEmpty() && (((_bits0 & -_bits0)==_bits0 && _bits1==0) || + ((_bits1 & -_bits1)==_bits1 && _bits0==0)); } // Cardinality diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java index 7305c4d9..f07389eb 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -26,7 +26,9 @@ public class StoreRISC extends MemOpRISC { if( i==1 ) return null; // mem if( i==2 ) return riscv.RMASK; // ptr // 2 - index - if( i==4 ) return riscv.MEM_MASK; // Wide mask to store GPR and FPR + if( i==4 ) return _sz >= '4' + ? riscv.MEM_MASK // Word/dword value in GPR or FPR + : riscv.RMASK; // Byte/short stores require a GPR return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 97586d87..9f80b1f5 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -66,7 +66,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base in GPR if( i==3 ) return x86_64_v2.RMASK; // index in GPR - if( i==4 ) return _sz >= 2 + if( i==4 ) return _sz >= '4' ? x86_64_v2.MEM_MASK // value in GPR or XMM : x86_64_v2.RMASK; // Bytes and shorts in GPR only return null; // Anti-dependence diff --git a/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 1e1a1dc3..bf809d2a 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -32,7 +32,7 @@ public class BrainFuckTest { assertEquals(brain_fuck.length(),A5.ld4s(ptr_arm)); for( int i=0; i<brain_fuck.length(); i++ ) - assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr+4+i)); + assertEquals(brain_fuck.charAt(i), A5.ld1z(ptr_arm+4+i)); } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 8c122e92..337d58ea 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,11 +1,10 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; -import java.io.IOException; -import java.nio.file.Files; -import java.nio.file.Path; import org.junit.Assert; import org.junit.Ignore; import org.junit.Test; @@ -29,6 +28,16 @@ return f(s); } + @org.junit.Rule public final org.junit.rules.ErrorCollector _errors = new org.junit.rules.ErrorCollector(); + + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } + @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } + @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } + @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } + @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } + @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } + @Test public void testPrintingRegisters() throws Exception { com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); } @@ -42,34 +51,36 @@ return f(s); assertEquals("0", Eval2.eval(code, 2)); } - static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src); + // Collect differences so every target runs; JUnit still fails the test. + private void testTarget(String src, String cpu, String os, int spills, String stop) { + _errors.checkSucceeds(() -> { testCPU(src,cpu,os,spills,stop); return null; }); + } + + static void testCPU(String src, String cpu, String os, int spills, String stop) { + CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); - if( stop != null ) - assertEquals(stop, code._stop.toString()); + SpillStats.record(code,"Chapter20",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); + if( stop!=null ) assertEquals(stop,code._stop.toString()); } - private static void testAllCPUs( String src, int spills, String stop ) { - testCPU(src,"x86_64_v2", "SystemV",spills,stop); - testCPU(src,"riscv" , "SystemV",spills,stop); - testCPU(src,"arm" , "SystemV",spills,stop); + private void testAllCPUs( String src, int spills, String stop ) { + testTarget(src,"x86_64_v2", "SystemV",spills,stop); + testTarget(src,"riscv" , "SystemV",spills,stop); + testTarget(src,"arm" , "SystemV",spills,stop); } @Test public void testAlloc0() { - testCPU("return new u8[arg];","x86_64_v2", "SystemV",3,"return [u8];"); - testCPU("return new u8[arg];","riscv" , "SystemV",5,"return [u8];"); - testCPU("return new u8[arg];","arm" , "SystemV",5,"return [u8];"); + testTarget("return new u8[arg];","x86_64_v2","SystemV",4,"return [u8];"); + testTarget("return new u8[arg];","riscv","SystemV",5,"return [u8];"); + testTarget("return new u8[arg];","arm","SystemV",5,"return [u8];"); } @Test public void testBasic1() { String src = "return arg | 2;"; - testCPU(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); - testCPU(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); - testCPU(src,"arm" , "SystemV",0,"return (ori,arg);"); + testTarget(src,"x86_64_v2", "SystemV",1,"return (ori,mov(arg));"); + testTarget(src,"riscv" , "SystemV",0,"return ( arg | #2 );"); + testTarget(src,"arm" , "SystemV",0,"return (ori,arg);"); } @Test @@ -85,56 +96,109 @@ val sqrt = { int x -> guess = next; } }; -int cast_int = arg+2; -return sqrt(arg) + sqrt(cast_int); +return sqrt(arg) + sqrt(arg+2); """; - testCPU(src,"x86_64_v2", "Win64" ,55,null); - testCPU(src,"riscv" , "SystemV",19,null); - testCPU(src,"arm" , "SystemV",19,null); + testTarget(src,"x86_64_v2", "SystemV",48,null); + testTarget(src,"riscv" , "SystemV",17,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test - public void testNewtonFloat() throws IOException { - String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) - + "flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0);"; - testCPU(src,"x86_64_v2", "SystemV",39,null); - testCPU(src,"riscv" , "SystemV",17,null); - testCPU(src,"arm" , "SystemV",18,null); + public void testNewtonFloat() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { flt x -> + flt guess = x; + while( 1 ) { + flt next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +flt farg = arg; +return sqrt(farg) + sqrt(farg+2.0); +"""; + testTarget(src,"x86_64_v2", "SystemV",23,null); + testTarget(src,"riscv" , "SystemV",18,null); + testTarget(src,"arm" , "SystemV",18,null); } @Test public void testAlloc2() { String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"; - testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); - testCPU(src,"riscv" , "SystemV", 6,"return .[];"); - testCPU(src,"arm" , "SystemV", 6,"return .[];"); + testTarget(src,"x86_64_v2","SystemV",3,"return .[];"); + testTarget(src,"riscv","SystemV",6,"return .[];"); + testTarget(src,"arm","SystemV",6,"return .[];"); } - - @Test - public void testArray1() throws IOException { - String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/array1.smp")); - testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); - testCPU(src,"riscv" , "SystemV", 8,"return (add,.[],(mul,.[],1000));"); - testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); + public void testArray1() { + String src = +""" +int[] !ary = new int[arg]; +// Fill [0,1,2,3,4,...] +for( int i=0; i<ary#; i++ ) + ary[i] = i; +// Fill [0,1,3,6,10,...] +for( int i=0; i<ary#-1; i++ ) + ary[i+1] += ary[i]; +return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 +"""; + testTarget(src,"x86_64_v2", "SystemV",9,"return .[];"); + testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); + testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } - @Test - public void testString() throws IOException { - String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); - testCPU(src,"x86_64_v2", "SystemV", 9,null); - testCPU(src,"riscv" , "SystemV", 5,null); - testCPU(src,"arm" , "SystemV", 3,null); + public void testString() { + String src = """ +struct String { + u8[] cs; + int _hashCode; +}; + +val equals = { String self, String s -> + if( self == s ) return true; + if( self.cs# != s.cs# ) return false; + for( int i=0; i< self.cs#; i++ ) + if( self.cs[i] != s.cs[i] ) + return false; + return true; +}; + +val hashCode = { String self -> + self._hashCode + ? self._hashCode + : (self._hashCode = _hashCodeString(self)); +}; + +val _hashCodeString = { String self -> + int hash=0; + if( self.cs ) { + for( int i=0; i< self.cs#; i++ ) + hash = hash*31 + self.cs[i]; + } + if( !hash ) hash = 123456789; + return hash; +}; + +String !s = new String { cs = new u8[17]; }; +s.cs[0] = 67; // C +s.cs[1] = 108; // l +hashCode(s); +"""; + testTarget(src,"x86_64_v2", "SystemV",0,null); + testTarget(src,"riscv" , "SystemV",0,null); + testTarget(src,"arm" , "SystemV",0,null); } @Test public void testCast() { String src = "struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1;"; - testCPU(src,"x86_64_v2", "SystemV",2,null); - testCPU(src,"riscv" , "SystemV",2,null); - testCPU(src,"arm" , "SystemV",2,null); + testTarget(src,"x86_64_v2","SystemV",1,null); + testTarget(src,"riscv","SystemV",2,null); + testTarget(src,"arm","SystemV",2,null); } @Test @@ -152,9 +216,9 @@ if (b2) if (b1) return 1; if (b1) return 2; return 0; """; - testCPU(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); - testCPU(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); - testCPU(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"x86_64_v2", "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"riscv" , "SystemV",0,"return Phi(Region,1,2,0);"); + testTarget(src,"arm" , "SystemV",0,"return Phi(Region,1,2,0);"); } @Test @@ -167,8 +231,126 @@ while (arg > 0) { } return arg; """; - testCPU(src,"x86_64_v2", "SystemV",3,null); - testCPU(src,"riscv" , "SystemV",2,null); - testCPU(src,"arm" , "SystemV",2,null); + testTarget(src,"x86_64_v2", "SystemV",3,null); + testTarget(src,"riscv" , "SystemV",2,null); + testTarget(src,"arm" , "SystemV",2,null); } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @Test + public void testBrainfuck() { + var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(java.nio.charset.StandardCharsets.UTF_8); + var encoded = new StringBuilder("u8[] !program = new u8[").append(program.length).append("];"); + for (int i = 0; i < program.length; i++) { + int value = program[i] & 0xFF; + encoded.append("program[").append(i).append("] = ").append(value).append(";"); + } + + String src = encoded + """ + +int d = 0; +u8[] !output = new u8[0]; +u8[] !data = new u8[100]; + +for( int pc = 0; pc < program#; pc++ ) { + var command = program[pc]; + if (command == 62) { + d++; + } else if (command == 60) { + d--; + } else if (command == 43) { + data[d]++; + } else if (command == 45) { + data[d]--; + } else if (command == 46) { + // Output a byte; increase the output array size + var old = output; + output = new u8[output# + 1]; + for( int i = 0; i < old#; i++ ) + output[i] = old[i]; + output[old#] = data[d]; // Add the extra byte on the end + } else if (command == 44) { + data[d] = 42; + } else if (command == 91) { + if (data[d] == 0) { + for( int d = 1; d > 0; ) { + command = program[++pc]; + if (command == 91) d++; + if (command == 93) d--; + } + } + } else if (command == 93) { + if (data[d]) { + for( int d = 1; d > 0; ) { + command = program[--pc]; + if (command == 93) d++; + if (command == 91) d--; + } + } + } +} +return output; +"""; + testTarget(src,"x86_64_v2", "SystemV",40,null); + testTarget(src,"riscv" , "SystemV",28,null); + testTarget(src,"arm" , "SystemV",28,null); + //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); + } + // Original Chapter 20 allocation workload, kept fixed for cohort comparisons. + @Test + public void testMergeSort() { + String src = +""" +// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort + +val merge_sort = { int[] a, int[] b, int n -> + copy_array(a, 0, n, b); + split_merge(a, 0, n, b); +}; + +val split_merge = { int[] b, int begin, int end, int[] a -> + if (end - begin <= 1) + return 0; + int middle = (end + begin) / 2; + split_merge(a, begin, middle, b); + split_merge(a, middle, end, b); + merge(b, begin, middle, end, a); + return 0; +}; + +val merge = { int[] b, int begin, int middle, int end, int[] a -> + int i = begin, j = middle; + + for (int k = begin; k < end; k++) { + // && and || + bool cond = false; + if (i < middle) { + if (j >= end) cond = true; + else if (a[i] <= a[j]) cond = true; + } + if (cond) b[k] = a[i++]; + else b[k] = a[j++]; + } +}; + +val copy_array = { int[] a, int begin, int end, int[] b -> + for (int k = begin; k < end; k++) + b[k] = a[k]; +}; + +int[] !a = new int[arg]; +int[] !b = new int[a#]; + +for (int i = 0; i < a#; i++) + a[i] = a# - i; + +merge_sort(a, b, a#); + +return a; +"""; + testTarget(src,"x86_64_v2", "SystemV",52,null); + testTarget(src,"riscv" , "SystemV",44,null); + testTarget(src,"arm" , "SystemV",44,null); +//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); + } + } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java new file mode 100644 index 00000000..4fddbb4b --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java @@ -0,0 +1,55 @@ +package com.seaofnodes.simple; + +import java.io.IOException; +import java.nio.file.*; +import org.junit.Test; + +// Revised Chapter 20 examples introduced with native encoding. +public class Chapter21AllocTest { + @Test + public void testNewtonInteger() { + String src = +""" +// Newtons approximation to the square root +val sqrt = { int x -> + int guess = x; + while( 1 ) { + int next = (x/guess + guess)/2; + if( next == guess ) return guess; + guess = next; + } +}; +return sqrt(arg) + sqrt(arg+2); +"""; + Chapter21Test.testCPU(src,"x86_64_v2", "Win64" ,48,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV",19,null); + Chapter21Test.testCPU(src,"arm" , "SystemV",19,null); + } + + @Test + public void testNewtonFloat() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) + + "flt farg = arg; return test_sqrt(farg) + test_sqrt(farg+2.0);"; + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",39,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV",17,null); + Chapter21Test.testCPU(src,"arm" , "SystemV",18,null); + } + + @Test + public void testArray1() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/array1.smp")); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",-1,"return .[];"); + Chapter21Test.testCPU(src,"riscv" , "SystemV", 8,"return (add,.[],(mul,.[],1000));"); + Chapter21Test.testCPU(src,"arm" , "SystemV", 5,"return (add,.[],(mul,.[],1000));"); + } + + + @Test + public void testString() throws IOException { + String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV", 3,null); + Chapter21Test.testCPU(src,"arm" , "SystemV", 3,null); + } + +} diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 13dd410e..72f79d6c 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -25,6 +26,53 @@ public class Chapter21Test { } + @Test public void testNarrowStores() throws IOException { + for( String type : new String[]{"i8","u8","i16","u16"} ) { + String src = "struct S { "+type+" x; }; S !s = new S; s.x = arg; return 0;"; + CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); + int stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.riscv.StoreRISC st ) { + stores++; + assertEquals("Byte/short stores have no FP encoding",-1,st.regmap(4).nextReg((short)31)); + } + assertEquals(1,stores); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu.regs[riscv.A0] = 0x8765; + assertEquals(0,cpu.step(100)); + assertEquals(type.endsWith("8") ? 0x65 : 0x8765, + type.endsWith("8") ? cpu.ld1z(1<<16) : cpu.ld2z(1<<16)); + code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"x86_64_v2",TestC.CALL_CONVENTION); + stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) { + stores++; + assertEquals("Byte/short stores have no XMM encoding",-1,st.regmap(4).nextReg((short)15)); + } + assertEquals(1,stores); + } + } + + @Test public void testNativeExitStatus() throws IOException { + Path source = Path.of("build/objs/nativeExit.c"); + Files.createDirectories(source.getParent()); + Files.writeString(source,"int main() { return 7; }\n"); + try { + TestC.gcc(source.toString(),null,null,false, + "build/objs/nativeExit"+(TestC.OS.startsWith("Windows") ? ".exe" : "")); + } catch( AssertionError error ) { + assertTrue(error.getMessage(),error.getMessage().contains("Program exit status")); + return; + } + fail("A failing native program must fail the test, even with empty stdout"); + } + + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } @Test public void testRisc64BitStore() { byte[] mem = new byte[24]; EvalRisc5 cpu = new EvalRisc5(mem,mem.length); @@ -63,11 +111,9 @@ public class Chapter21Test { } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + SpillStats.record(code,"Chapter21",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); } @@ -81,7 +127,7 @@ public class Chapter21Test { } @Test public void testInfinite() { - String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + String src = "struct S { int i; }; S !s = new S; while(1) s.i++;"; testCPU(src,"x86_64_v2", "SystemV",0,"return Top;"); testCPU(src,"riscv" , "SystemV",2,"return Top;"); testCPU(src,"arm" , "SystemV",2,"return Top;"); @@ -107,7 +153,7 @@ public class Chapter21Test { public void testString() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); testCPU(src,"x86_64_v2", "SystemV", 9,null); - testCPU(src,"riscv" , "SystemV", 5,null); + testCPU(src,"riscv" , "SystemV", 3,null); testCPU(src,"arm" , "SystemV", 3,null); } @@ -162,11 +208,11 @@ public class Chapter21Test { String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - TestC.run("sieve",sprimes, 257); + TestC.run("sieve",sprimes, 178); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. - EvalRisc5 R5 = TestRisc5.build("sieve", 100, 160, false); + EvalRisc5 R5 = TestRisc5.build("sieve", 100, 89, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) @@ -178,7 +224,7 @@ public class Chapter21Test { // Evaluate on ARM5 emulator; expect return of an array of primes in // the simulated heap. - EvalArm64 A5 = TestArm64.build("sieve", 100, 160, false); + EvalArm64 A5 = TestArm64.build("sieve", 100, 93, false); int trap_arm = A5.step(10000); assertEquals(0, trap_arm); int ary_arm = (int)A5.regs[arm.X0]; @@ -192,14 +238,14 @@ public class Chapter21Test { String fib = "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"; TestC.run("fib", fib, 24); - EvalRisc5 R5 = TestRisc5.build("fib", 9, 17, false); + EvalRisc5 R5 = TestRisc5.build("fib", 9, 16, false); int trap = R5.step(100); assertEquals(0,trap); // Return register A0 holds fib(8)==55 assertEquals(55,R5.regs[riscv.A0]); // arm - EvalArm64 A5 = TestArm64.build("fib", 9, 17, false); + EvalArm64 A5 = TestArm64.build("fib", 9, 16, false); int trap_arm = A5.step(100); assertEquals(0,trap_arm); // Return register X0 holds fib(8)==55 @@ -208,7 +254,7 @@ public class Chapter21Test { @Test public void testPerson() throws IOException { String person = "6\n"; - TestC.run("person", person, 0); + TestC.run("person21", person, 0); // Memory layout starting at PS: int ps = 1<<16; // Person array pointer starts at heap start @@ -219,7 +265,7 @@ public class Chapter21Test { int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; - EvalRisc5 R5 = TestRisc5.build("person", ps, 0, false); + EvalRisc5 R5 = TestRisc5.build("person21", ps, 0, false); R5.regs[riscv.A1] = 1; // Index 1 R5.st8(ps,3); // Length R5.st8(ps+1*8,p0); @@ -235,7 +281,7 @@ public class Chapter21Test { assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); - EvalArm64 A5 = TestArm64.build("person", ps, 0, false); + EvalArm64 A5 = TestArm64.build("person21", ps, 0, false); A5.regs[arm.X1] = 1; // Index 1 A5.st8(ps, 3); A5.st8(ps+1*8,p0); @@ -257,7 +303,7 @@ public class Chapter21Test { // than what Win64 allows - so Win64 gets a lot more spills here. String arg_count = "191.000000\n"; TestC.run("arg_count", arg_count, - TestC.CALL_CONVENTION.equals("Win64") ? 42 : 15); + TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", 0, 0, false); diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 394ba336..369e365e 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; import java.nio.file.Files; @@ -12,6 +13,13 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter22Test { + @Test public void testInfiniteReturn() { + String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + testCPU(src,"x86_64_v2","SystemV",0,"return Top;"); + testCPU(src,"riscv","SystemV",2,"return Top;"); + testCPU(src,"arm","SystemV",2,"return Top;"); + } + @Test @Ignore public void testJig() throws IOException { @@ -23,11 +31,9 @@ public class Chapter22Test { } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + SpillStats.record(code,"Chapter22",cpu,os); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); if( stop != null ) assertEquals(stop, code._stop.toString()); return code; diff --git a/chapter22/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter22/src/test/java/com/seaofnodes/simple/MergeSortTest.java index a1004fb5..82b1e58e 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -17,7 +17,7 @@ public class MergeSortTest { for( int prime : primes ) sb.p(prime).p(", "); String sprimes = sb.p("]").toString(); - TestC.run("sort", sprimes, 40); + TestC.run("sort", sprimes, 34); EvalRisc5 R5 = TestRisc5.build("src/test/java/com/seaofnodes/simple/progs", "sort", "merge_sort", 0, 36, false); diff --git a/chapter22/src/test/java/com/seaofnodes/simple/SpillStats.java b/chapter22/src/test/java/com/seaofnodes/simple/SpillStats.java new file mode 100644 index 00000000..82cffef8 --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -0,0 +1,71 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import java.util.Map; +import java.util.TreeMap; +import org.junit.runner.*; +import org.junit.runner.notification.*; + +// Run existing tests and sum actual allocations, including ones without goldens. +// Helpers call record after allocation; ordinary JUnit runs collect nothing. +public class SpillStats extends RunListener { + private static SpillStats ACTIVE; + private Description _test; + private int _qualityFailures; + private final Map<String,long[]> _totals = new TreeMap<>(); + + @Override public void testStarted(Description test) { _test = test; } + public static void record(CodeGen code, String cohort, String cpu, String abi) { + if( ACTIVE==null ) return; + String test = ACTIVE._test.getTestClass().getSimpleName()+"."+ACTIVE._test.getMethodName(); + for( String key : new String[]{cohort+","+cpu+","+abi,cohort+",ALL,ALL"} ) { + long[] sum = ACTIVE._totals.computeIfAbsent(key,k -> new long[3]); + sum[0]++; sum[1] += code._regAlloc._spills; sum[2] += code._regAlloc._spillScaled; + } + System.out.println("allocation,"+cohort+","+test+","+cpu+","+abi+","+ + code._regAlloc._spills+","+code._regAlloc._spillScaled); + } + + // The same native helpers serve old and new program cohorts. + public static void recordNative(CodeGen code, String cpu, String abi) { + String cohort = ACTIVE!=null && ACTIVE._test.getTestClass()==Chapter22Test.class + ? "Chapter22" : "Chapter21"; + record(code,cohort,cpu,abi); + } + + // Keep running every CPU and native result check when measuring quality. + // A changed golden still makes spill-stats fail at the end. + public static void checkSpills(int expected, int actual) { + if( expected==-1 ) return; + try { org.junit.Assert.assertEquals("Expect spills:",expected,actual,Math.max(1,expected>>3)); } + catch( AssertionError error ) { + if( ACTIVE==null ) throw error; + ACTIVE._qualityFailures++; + System.err.println(ACTIVE._test+": "+error.getMessage()); + } + } + + public static void main(String[] args) throws ClassNotFoundException { + if( args.length==0 ) args = new String[]{"Chapter20Test","Chapter21Test","Chapter21AllocTest","Chapter22Test","BrainFuckTest","MergeSortTest"}; + Class<?>[] tests = new Class<?>[args.length]; + for( int i=0; i<args.length; i++ ) + tests[i] = Class.forName("com.seaofnodes.simple."+args[i]); + ACTIVE = new SpillStats(); + JUnitCore junit = new JUnitCore(); + junit.addListener(ACTIVE); + Result result = junit.run(tests); + boolean passed = result.wasSuccessful() && ACTIVE._qualityFailures==0; + if( !result.wasSuccessful() ) System.out.println("FAILED test run: totals are not a complete comparison."); + else if( !passed ) System.out.println("Spill expectations differ; allocation and runtime checks passed."); + System.out.println("cohort,cpu,abi,allocations,splits,scaled"); + for( var row : ACTIVE._totals.entrySet() ) { + long[] sum = row.getValue(); + System.out.println(row.getKey()+","+sum[0]+","+sum[1]+","+sum[2]); + } + for( Failure failure : result.getFailures() ) System.err.println(failure.getTrace()); + System.out.println("Tests: "+result.getRunCount()+", failures: "+result.getFailureCount()); + System.out.println("Spill golden failures: "+ACTIVE._qualityFailures); + ACTIVE = null; + if( !passed ) System.exit(1); + } +} diff --git a/chapter22/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter22/src/test/java/com/seaofnodes/simple/TestArm64.java index 5d7d1361..edce92f3 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -21,13 +23,12 @@ public class TestArm64 { public static EvalArm64 build( String dir, String file, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); - CodeGen code = new CodeGen(src).driver("arm", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null); + SpillStats.recordNative(code,"arm","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded - int delta = spills>>3; - if( delta == 0 ) delta =1; - if( spills != -1 ) assertEquals("Expect spills:", spills, code._regAlloc._spillScaled, delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); // Image byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) diff --git a/chapter22/src/test/java/com/seaofnodes/simple/TestC.java b/chapter22/src/test/java/com/seaofnodes/simple/TestC.java index 93fa9b66..44c06128 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/TestC.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; import java.nio.file.Files; @@ -43,15 +44,13 @@ public abstract class TestC { String obj = bin+".o"; String exe = OS.startsWith("Windows") ? bin+".exe" : bin; // Compile simple, emit ELF - CodeGen code = new CodeGen(src).driver( CPU_PORT, simple_conv, obj); + CodeGen code = new CheckedCodeGen(src).driver( CPU_PORT, simple_conv, obj); + SpillStats.recordNative(code,CPU_PORT,simple_conv); String result = gcc(obj, c_conv, cfile, false, exe ); assertEquals(expected,result); // Allocation quality not degraded - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); } public static String gcc( String obj, String c_conv, String cfile, boolean stdin, String... args ) throws IOException { @@ -97,10 +96,9 @@ public abstract class TestC { ProcessBuilder smp = new ProcessBuilder(args); if( stdin ) smp.redirectInput(ProcessBuilder.Redirect.INHERIT); Process p = smp.start(); - try { exit = (byte)p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + try { exit = p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } result = new String(p.getInputStream().readAllBytes()); - if( exit!=0 ) - System.err.println("exec exit code: "+exit); + assertEquals("Program exit status",0,exit); return result; } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter22/src/test/java/com/seaofnodes/simple/TestRisc5.java index 041ed833..adb256eb 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.Node; @@ -20,14 +21,12 @@ public abstract class TestRisc5 { public static EvalRisc5 build( String dir, String file, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); - CodeGen code = new CodeGen(src).driver("riscv", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null); + SpillStats.recordNative(code,"riscv","SystemV"); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded - int delta = spills>>3; - if( delta==0 ) delta = 1; - if( spills != -1 ) - assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + SpillStats.checkSpills(spills,code._regAlloc._spillScaled); // Image byte[] image = new byte[1<<20]; // A megabyte (1024*1024 bytes) diff --git a/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..85de8b36 --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,208 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; + +// Small scheduled machine graphs isolate register constraints from peepholes. +public class RegAllocTestSupport { + private static final RegMask A = new RegMask(0), B = new RegMask(1); + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + final boolean _clone; + Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT; + } + @Override public String op() { return "testOp"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @Override public RegMask killmap() { return _kill; } + @Override public boolean isClone() { return _clone; } + @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + private static CodeGen graph() { + CodeGen code = new CodeGen(""); + code._mach = new x86_64_v2(code); + code._cfg.add(code._start); + return code; + } + + public static void masks() { + for( int reg : new int[]{0,63,64,65,127} ) { + RegMask mask = new RegMask(reg); + assertEquals(reg,mask.firstReg()); + assertEquals(1,mask.size()); + } + assertEquals(-1,new RegMask(0L).firstReg()); + assertFalse(new RegMask(0L).size1()); + RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1); + assertEquals(64,boundary.nextReg((short)63)); + assertEquals(127,boundary.nextReg((short)64)); + assertEquals(-1,boundary.nextReg((short)127)); + } + + public static void union() { + CodeGen code = graph(); + Op use = new Op(null,B,null,false,code._start); + LRG a = new LRG((short)1), b = new LRG((short)2); + a._mask = new RegMask(3L); + b._mask = new RegMask(6L); + b.machUse(use,(short)2,true); + LRG both = a.union(b); + assertNotNull(both._mask); + assertEquals(1,both._mask.firstReg()); + assertEquals(1,both._mask.size()); + assertSame(use,both._machUse); + assertEquals(2,both._uidx); + } + + public static void killWithoutResult() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,A,false,code._start); // Clobbers A, produces no value. + new Op(null,A,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + } + + public static void nullUseMask() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,null,false,code._start,def); // Scheduling dependency only. + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertTrue(IFG.build(0,alloc)); + } + + public static void cloneRegisterClass() { + for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) { + CodeGen code = graph(); + Op def = new Op(A,null,null,true,code._start); + Op use = new Op(null,required,null,false,code._start,def); + Op use2 = new Op(null,required,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses. + assertEquals(0,alloc.regnum(def)); + assertTrue(required.test(alloc.regnum(use.in(1)))); + assertTrue(required.test(alloc.regnum(use2.in(1)))); + assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void commutativePhi() { + CodeGen code = graph(); + Op a = new Op(A,null,null,false,code._start); + Op b = new Op(A,null,null,false,code._start); + Op add = new Op(A,A,null,false,code._start,a,b) { + @Override public boolean commutes() { return true; } + }; + RegionNode region = new RegionNode(null,code._start,code._start); + new PhiNode("sum",TypeInteger.BOT,region,add,a); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,new RegAlloc(code))); + } + + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. + public static class CheckedCodeGen extends CodeGen { + public CheckedCodeGen(String src) { super(src); } + @Override public CodeGen regAlloc() { + super.regAlloc(); + checkRegisters(this); + return this; + } + } + + public static void checkRegisters(CodeGen code) { + assertTrue(code._regAlloc.verifyFunctionLocalEdges()); + for( CFGNode bb : code._cfg ) + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach ) { + if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n))); + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i)))); + if( mach.twoAddress()!=0 ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress()))); + } + if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + } + } + + public static void copyClobber() throws Exception { + for( boolean killed : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode hi = code._mach.split("test",(byte)0,null); + hi.setDef(0,code._start); hi.setDef(1,def); + alloc.newLRG(hi)._reg=1; + new Op(null,null,killed ? A : null,false,code._start); + SplitNode lo = code._mach.split("test",(byte)0,null); + lo.setDef(0,code._start); lo.setDef(1,hi); + alloc.newLRG(lo)._reg=0; + Op use = new Op(null,A,null,false,code._start,lo); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame(killed ? lo : def,use.in(1)); + } + CodeGen pre = graph(); + RegAlloc uncolored = new RegAlloc(pre); + Op def0 = new Op(A,null,null,false,pre._start); + uncolored.newLRG(def0)._mask=A; + Op fixed = new Op(A,null,null,false,pre._start); + uncolored.newLRG(fixed)._mask=A; + SplitNode copy = pre._mach.split("test",(byte)0,null); + copy.setDef(0,pre._start); copy.setDef(1,def0); + assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); + } + + public static void coalescing() { + // Merge, incompatible masks, interference, capacity, and adjacency remapping. + for( int kind=0; kind<5; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + SplitNode copy = code._mach.split("test",(byte)0,null); + copy.setDef(0,code._start); copy.setDef(1,def); + Op use = new Op(null,new RegMask(3L),null,false,code._start,copy); + LRG from = alloc.newLRG(def), to = alloc.newLRG(copy); + from._mask = kind==1 ? A : new RegMask(3L); + to._mask = kind==1 ? B : new RegMask(3L); + from.machDef(def,false); from.machUse(copy,(short)1,false); + to.machDef(copy,false); to.machUse(use,(short)1,false); + LRG left = new LRG((short)100), right = new LRG((short)101); + if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); } + if( kind>=3 ) { + from.addNeighbor(left); left.addNeighbor(from); + if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); } + else { to.addNeighbor(left); left.addNeighbor(to); } + } + int fcnt=from.nadj(), tcnt=to.nadj(); + assertTrue(Coalesce.coalesce(0,alloc)); + if( kind==0 || kind==4 ) { + assertSame(def,use.in(1)); + assertSame(alloc.lrg(def),alloc.lrg(copy)); + assertSame(use,alloc.lrg(def)._machUse); + assertEquals(1,alloc.lrg(def)._uidx); + if( kind==4 ) { + assertEquals(1,left.nadj()); + assertSame(alloc.lrg(def),left._adj.at(0)); + assertSame(left,alloc.lrg(def)._adj.at(0)); + } + } else { + assertSame(copy,use.in(1)); + assertNotSame(alloc.lrg(def),alloc.lrg(copy)); + assertEquals(fcnt,from.nadj()); + assertEquals(tcnt,to.nadj()); + } + } + } + +} diff --git a/chapter22/src/test/java/com/seaofnodes/simple/progs/person21.c b/chapter22/src/test/java/com/seaofnodes/simple/progs/person21.c new file mode 100644 index 00000000..df95e1ca --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/progs/person21.c @@ -0,0 +1,34 @@ +#include <stdio.h> +#include <stdbool.h> +#include <stdlib.h> + +typedef struct Person { + int age; +} Person; + +typedef struct PersonArray { + unsigned int length; + int pad; + Person* data[]; +} PersonArray; + +__attribute__ ((CALL_CONV)) +extern void fcn(PersonArray* people, int index); + +int main() { + Person base[5] = {{25},{1},{18},{45},{60}}; + unsigned char buf[8+8*5]; + PersonArray* people_array = (PersonArray*)buf; + people_array->length=5; + for (int i=0; i<people_array->length; i++) people_array->data[i] = &base[i]; + + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + fcn(people_array, 1); + + printf("%d\n", people_array->data[1]->age); // expected: 6 + + return 0; +}
\ No newline at end of file diff --git a/chapter22/src/test/java/com/seaofnodes/simple/progs/person21.smp b/chapter22/src/test/java/com/seaofnodes/simple/progs/person21.smp new file mode 100644 index 00000000..9f0f5bea --- /dev/null +++ b/chapter22/src/test/java/com/seaofnodes/simple/progs/person21.smp @@ -0,0 +1,9 @@ +// -*-java-*- +struct Person { + int age; +}; + +val fcn = { Person?[] ps, int x -> + if( ps[x] ) + ps[x].age++; +};
\ No newline at end of file diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index e9b5eb2e..f4ce4366 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -40,8 +40,8 @@ abstract public class BuildLRG { int uidx = n.out(0)._inputs.find(n); RegMask mask1 = n.in (1) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(1))._mask; RegMask mask2 = n.in (2) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(2))._mask; - RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): alloc.lrg(n )._mask; - if( !mask1.overlap(masko) && mask2.overlap(masko) ) + RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): mach.outregmap(); + if( masko!=null && !mask1.overlap(masko) && mask2.overlap(masko) ) n.swap12(); } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 6dd6fbf1..bc14aadd 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -207,20 +207,7 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - // Disallow clone-ables from killing registers. Just fail - // them and re-clone closer to target... so no kill. - // Special case for Intel XOR used to zero. - Node n = (Node)m; - CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0(); - if( m.isClone() && // Must be clonable - (n.nOuts()>1 || // Has many users OR - // Only 1 user but effective use is remote block - effUseBlk != n.cfg0() )) - // Then fail the clonable; it should split or move - alloc.fail(alloc.lrg((Node)m)); - // Else clonable cannot move - else if( !tlrg.sub(killMask) ) - alloc.fail(tlrg); + if( !tlrg.sub(killMask) ) alloc.fail(tlrg); } } } @@ -438,13 +425,13 @@ abstract public class IFG { private static int pickRiskyScore( LRG lrg ) { // Pick single-def clonables that are not right next to their single-use. // Failing to color these will clone them closer to their uses. - if( !lrg._multiDef && lrg._machDef.isClone() ) { - Node def = ((Node)lrg._machDef); - Node use = ((Node)lrg._machUse); + if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) { + Node def = (Node)lrg._machDef; + Node use = (Node)lrg._machUse; CFGNode cfg = def.cfg0(); - if( cfg != use.cfg0() || // Different blocks OR + if( lrg._multiUse || cfg != use.cfg0() || // Many uses or different blocks OR // Same block, but not close - cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) + cfg._outputs.find(def)+1 < cfg._outputs.find(use) ) return 1000000; } @@ -452,7 +439,7 @@ abstract public class IFG { // and very cheap to spill. if( lrg._machDef instanceof CalleeSaveNode ) return 1000000-2-lrg._mask.firstReg(); - if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && + if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) return 1000000-1; @@ -506,7 +493,7 @@ abstract public class IFG { private static int biasable(Node split) { if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1 - if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Yes biasable, advance is slot 1 + if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Prefer the backedge in loops if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 10297a9a..adc198fc 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -176,17 +176,35 @@ public class RegAlloc { if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } + // Optional diagnostic for values accidentally shared across functions. + //assert verifyFunctionLocalEdges(); + // Top driver: repeated rounds of coloring and splitting. byte round=0; while( !graphColor(round) ) { split(round); if( round >= 7 ) // Really expect to be done soon - throw Utils.TODO("Allocator taking too long"); + throw new IllegalStateException("Register allocation made no progress after eight rounds"); round++; } postColor(); // Remove no-op spills } + boolean verifyFunctionLocalEdges() { + for( CFGNode bb : _code._cfg ) { + if( bb instanceof StartNode ) continue; + FunNode fun = bb.fun(); + for( Node use : bb._outputs ) + if( use instanceof MachNode mach && !(use instanceof ParmNode) ) + for( int i=1; i<use.nIns(); i++ ) { + Node def = use.in(i); + if( def==null || mach.regmap(i)==null || def.cfg0()==null || def.cfg0() instanceof StartNode ) continue; + assert def.cfg0().fun()==fun : "Cross-function register edge: "+def.uniqueName()+" -> "+use.uniqueName()+" input "+i; + } + } + return true; + } + private boolean graphColor(byte round) { _failed.clear(); _lrgs.clear(); @@ -233,7 +251,9 @@ public class RegAlloc { if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && - (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) + (lrg._1regDefCnt + lrg._1regUseCnt) > 0 && + // A fixed-register clone with flexible uses must split at the uses. + !(lrg._1regDefCnt==1 && lrg._machDef.isClone() && lrg._1regUseCnt==0) ) return splitEmptyMaskSimple(round,lrg); // Repeated single-reg uses from a single def. Special for archs // with more fixed regs. @@ -255,16 +275,16 @@ public class RegAlloc { // Split just after def if( lrg._1regDefCnt==1 && !lrg._machDef.isClone() ) - // Force must-split, even if a prior split same block because register - // conflicts. Example: + // An earlier copy is reusable only if no intervening clobber. + // Being in the same block alone is insufficient. Example: // alloc // V1/rax - forced by alloc // alloc // V2/rax - kills prior RAX // st4 [V1],len - No good, must split around - insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/); + insertAfterAndReplace(makeSplit("def/empty1",round,lrg),(Node)lrg._machDef,false); // Split just before use - if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) ) + if( lrg._1regUseCnt==1 ) insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg); return true; } @@ -491,8 +511,8 @@ public class RegAlloc { void findAllLRG( LRG lrg ) { _ns.clear(); int wd = 0; - _ns.push((Node)lrg._machDef); - _ns.push((Node)lrg._machUse); + if( lrg._machDef!=null ) _ns.push((Node)lrg._machDef); + if( lrg._machUse!=null ) _ns.push((Node)lrg._machUse); while( wd < _ns._len ) { Node n = _ns.at(wd++); if( lrg(n)!=lrg ) continue; @@ -615,10 +635,10 @@ public class RegAlloc { break; hi = hi.in(1); } - // Check no clobbers - for( int idx = j-1; bb.out(idx) != hi; idx++) { + // Walk backward from the later copy, including instructions without results. + for( int idx = j-1; bb.out(idx) != hi; idx--) { Node n = bb.out(idx); - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } lo.setDefOrdered(1,hi.in(1)); @@ -626,6 +646,12 @@ public class RegAlloc { } + private boolean clobbers(Node n, int reg) { + LRG lrg = lrg(n); + return lrg!=null && (lrg._reg==reg || lrg._reg==-1 && lrg._mask.size1() && lrg._mask.firstReg()==reg) || + n instanceof MachNode mach && mach.killmap()!=null && mach.killmap().test(reg); + } + public boolean sameBlockNoClobber( SplitNode split ) { Node def = split.in(1); CFGNode cfg = def.cfg0(); @@ -639,7 +665,7 @@ public class RegAlloc { Node n = cfg.out(idx); if( n==def0 ) return true; // No clobbers if( lrg(n) == lrg(def) ) return false; // Self conflict - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } throw Utils.TODO(); diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index c7dda1da..303bba9e 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -72,16 +72,12 @@ public class RegMask { : Long.numberOfTrailingZeros(_bits1)+64); } public short nextReg(short reg) { - if( reg<64 ) { - long bits0 = _bits0 >> (reg+1); - if( bits0!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits0)); - reg=64; + if( reg < 63 ) { + long bits0 = _bits0 & (-1L << (reg+1)); + if( bits0!=0 ) return (short)Long.numberOfTrailingZeros(bits0); } - long bits1 = _bits1 >> (reg-64+1); - if( bits1!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits1)); - return -1; + long bits1 = reg < 64 ? _bits1 : reg < 127 ? _bits1 & (-1L << (reg-63)) : 0; + return bits1==0 ? -1 : (short)(64+Long.numberOfTrailingZeros(bits1)); } boolean isEmpty() { return _bits0==0 && _bits1==0; } @@ -98,8 +94,8 @@ public class RegMask { // Has exactly 1 bit set public boolean size1() { - return ((_bits0 & -_bits0)==_bits0 && _bits1==0) || - ((_bits1 & -_bits1)==_bits1 && _bits0==0); + return !isEmpty() && (((_bits0 & -_bits0)==_bits0 && _bits1==0) || + ((_bits1 & -_bits1)==_bits1 && _bits0==0)); } // Cardinality diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java index d06c0c35..df83ce1c 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -26,7 +26,9 @@ public class StoreRISC extends MemOpRISC { if( i==1 ) return null; // mem if( i==2 ) return riscv.RMASK; // ptr // 2 - index - if( i==4 ) return riscv.MEM_MASK; // Wide mask to store GPR and FPR + if( i==4 ) return _sz >= '4' + ? riscv.MEM_MASK // Word/dword value in GPR or FPR + : riscv.RMASK; // Byte/short stores require a GPR return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 5f090717..20578467 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -66,7 +66,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base in GPR if( i==3 ) return x86_64_v2.RMASK; // index in GPR - if( i==4 ) return _sz >= 2 + if( i==4 ) return _sz >= '4' ? x86_64_v2.MEM_MASK // value in GPR or XMM : x86_64_v2.RMASK; // Bytes and shorts in GPR only return null; // Anti-dependence diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 8ce02220..15addc7b 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.print.ASMPrinter; @@ -29,6 +31,14 @@ return f(s); } + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } + @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } + @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } + @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } + @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } + @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } + @Test public void testPrintingRegisters() throws Exception { com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); } @@ -43,7 +53,7 @@ return f(s); } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src); + CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; @@ -88,7 +98,7 @@ val sqrt = { int x -> int cast_int = arg+2; return sqrt(arg) + sqrt(cast_int); """; - testCPU(src,"x86_64_v2", "Win64" ,55,null); + testCPU(src,"x86_64_v2", "Win64" ,48,null); testCPU(src,"riscv" , "SystemV",19,null); testCPU(src,"arm" , "SystemV",19,null); } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index db8e398a..9e73a9c0 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -12,6 +13,54 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } + + @Test public void testNarrowStores() throws IOException { + for( String type : new String[]{"i8","u8","i16","u16"} ) { + String src = "struct S { "+type+" x; }; S !s = new S; s.x = arg; return 0;"; + CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); + int stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.riscv.StoreRISC st ) { + stores++; + assertEquals("Byte/short stores have no FP encoding",-1,st.regmap(4).nextReg((short)31)); + } + assertEquals(1,stores); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu.regs[riscv.A0] = 0x8765; + assertEquals(0,cpu.step(100)); + assertEquals(type.endsWith("8") ? 0x65 : 0x8765, + type.endsWith("8") ? cpu.ld1z(1<<16) : cpu.ld2z(1<<16)); + code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"x86_64_v2",TestC.CALL_CONVENTION); + stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) { + stores++; + assertEquals("Byte/short stores have no XMM encoding",-1,st.regmap(4).nextReg((short)15)); + } + assertEquals(1,stores); + } + } + + @Test public void testNativeExitStatus() throws IOException { + Path source = Path.of("build/objs/nativeExit.c"); + Files.createDirectories(source.getParent()); + Files.writeString(source,"int main() { return 7; }\n"); + try { + TestC.gcc(source.toString(),null,null,false, + "build/objs/nativeExit"+(TestC.OS.startsWith("Windows") ? ".exe" : "")); + } catch( AssertionError error ) { + assertTrue(error.getMessage(),error.getMessage().contains("Program exit status")); + return; + } + fail("A failing native program must fail the test, even with empty stdout"); + } + @Test public void testArmSubtractRegisters() { EvalArm64 cpu = new EvalArm64(new byte[16],16); cpu.st4(0,0xCB020020); // SUB X0,X1,X2, no shift or flag update. @@ -64,7 +113,7 @@ public class Chapter21Test { } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 ) @@ -163,11 +212,11 @@ public class Chapter21Test { String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - TestC.run("sieve",sprimes, 257); + TestC.run("sieve",sprimes, 186); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. - EvalRisc5 R5 = TestRisc5.build("sieve", 100, 160, false); + EvalRisc5 R5 = TestRisc5.build("sieve", 100, 92, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) @@ -179,7 +228,7 @@ public class Chapter21Test { // Evaluate on ARM5 emulator; expect return of an array of primes in // the simulated heap. - EvalArm64 A5 = TestArm64.build("sieve", 100, 160, false); + EvalArm64 A5 = TestArm64.build("sieve", 100, 94, false); int trap_arm = A5.step(10000); assertEquals(0, trap_arm); int ary_arm = (int)A5.regs[arm.X0]; @@ -258,7 +307,7 @@ public class Chapter21Test { // than what Win64 allows - so Win64 gets a lot more spills here. String arg_count = "191.000000\n"; TestC.run("arg_count", arg_count, - TestC.CALL_CONVENTION.equals("Win64") ? 42 : 15); + TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", 0, 0, false); diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java index f6410b6a..d6f31ff6 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; import java.nio.file.Files; @@ -23,7 +24,7 @@ public class Chapter22Test { } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 ) diff --git a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 45acc62a..4bb8ded0 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -1,4 +1,6 @@ package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -90,7 +92,7 @@ var apply = { i64 x, { i64 -> u32 } fcn -> } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 ) diff --git a/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java index 5d7d1361..38fd2a85 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -21,7 +23,7 @@ public class TestArm64 { public static EvalArm64 build( String dir, String file, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); - CodeGen code = new CodeGen(src).driver("arm", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/chapter23/src/test/java/com/seaofnodes/simple/TestC.java b/chapter23/src/test/java/com/seaofnodes/simple/TestC.java index dbe9f02f..6edde562 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestC.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; @@ -58,7 +59,7 @@ public abstract class TestC { String obj = bin+".o"; String exe = OS.startsWith("Windows") ? bin+".exe" : bin; // Compile simple, emit ELF - CodeGen code = new CodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); + CodeGen code = new CheckedCodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); String result = gcc(obj, c_conv, cfile, false, exe ); assertEquals(expected,result); @@ -113,10 +114,9 @@ public abstract class TestC { ProcessBuilder smp = new ProcessBuilder(args); if( stdin ) smp.redirectInput(ProcessBuilder.Redirect.INHERIT); Process p = smp.start(); - try { exit = (byte)p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + try { exit = p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } result = new String(p.getInputStream().readAllBytes()); - if( exit!=0 ) - System.err.println("exec exit code: "+exit); + assertEquals("Program exit status",0,exit); return result; } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java index 041ed833..cb1c95e9 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.Node; @@ -20,7 +21,7 @@ public abstract class TestRisc5 { public static EvalRisc5 build( String dir, String file, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple String src = Files.readString(Path.of(dir+"/"+file+".smp")); - CodeGen code = new CodeGen(src).driver("riscv", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..b2d14a02 --- /dev/null +++ b/chapter23/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,209 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; + +// Small scheduled machine graphs isolate register constraints from peepholes. +public class RegAllocTestSupport { + private static final RegMask A = new RegMask(0), B = new RegMask(1); + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + final boolean _clone; + Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT; + } + @Override public String op() { return "testOp"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @Override public RegMask killmap() { return _kill; } + @Override public boolean isClone() { return _clone; } + @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + private static CodeGen graph() { + CodeGen code = new CodeGen(""); + code._mach = new x86_64_v2(code); + code._cfg.add(code._start); + return code; + } + + public static void masks() { + for( int reg : new int[]{0,63,64,65,127} ) { + RegMask mask = new RegMask(reg); + assertEquals(reg,mask.firstReg()); + assertEquals(1,mask.size()); + } + assertEquals(-1,new RegMask(0L).firstReg()); + assertFalse(new RegMask(0L).size1()); + RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1); + assertEquals(64,boundary.nextReg((short)63)); + assertEquals(127,boundary.nextReg((short)64)); + assertEquals(-1,boundary.nextReg((short)127)); + } + + public static void union() { + CodeGen code = graph(); + Op use = new Op(null,B,null,false,code._start); + LRG a = new LRG((short)1), b = new LRG((short)2); + a._mask = new RegMask(3L); + b._mask = new RegMask(6L); + b.machUse(use,(short)2,true); + LRG both = a.union(b); + assertNotNull(both._mask); + assertEquals(1,both._mask.firstReg()); + assertEquals(1,both._mask.size()); + assertSame(use,both._machUse); + assertEquals(2,both._uidx); + } + + public static void killWithoutResult() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,A,false,code._start); // Clobbers A, produces no value. + new Op(null,A,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + } + + public static void nullUseMask() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,null,false,code._start,def); // Scheduling dependency only. + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertTrue(IFG.build(0,alloc)); + } + + public static void cloneRegisterClass() { + for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) { + CodeGen code = graph(); + Op def = new Op(A,null,null,true,code._start); + Op use = new Op(null,required,null,false,code._start,def); + Op use2 = new Op(null,required,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses. + assertEquals(0,alloc.regnum(def)); + assertTrue(required.test(alloc.regnum(use.in(1)))); + assertTrue(required.test(alloc.regnum(use2.in(1)))); + assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void commutativePhi() { + CodeGen code = graph(); + Op a = new Op(A,null,null,false,code._start); + Op b = new Op(A,null,null,false,code._start); + Op add = new Op(A,A,null,false,code._start,a,b) { + @Override public boolean commutes() { return true; } + }; + RegionNode region = new RegionNode(null,code._start,code._start); + new PhiNode("sum",TypeInteger.BOT,region,add,a); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,new RegAlloc(code))); + } + + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. + public static class CheckedCodeGen extends CodeGen { + public CheckedCodeGen(String src) { super(src); } + public CheckedCodeGen(String src, TypeInteger arg) { super(src,arg); } + @Override public CodeGen regAlloc() { + super.regAlloc(); + checkRegisters(this); + return this; + } + } + + public static void checkRegisters(CodeGen code) { + assertTrue(code._regAlloc.verifyFunctionLocalEdges()); + for( CFGNode bb : code._cfg ) + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach ) { + if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n))); + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i)))); + if( mach.twoAddress()!=0 ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress()))); + } + if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + } + } + + public static void copyClobber() throws Exception { + for( boolean killed : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode hi = code._mach.split("test",(byte)0,null); + hi.setDef(0,code._start); hi.setDef(1,def); + alloc.newLRG(hi)._reg=1; + new Op(null,null,killed ? A : null,false,code._start); + SplitNode lo = code._mach.split("test",(byte)0,null); + lo.setDef(0,code._start); lo.setDef(1,hi); + alloc.newLRG(lo)._reg=0; + Op use = new Op(null,A,null,false,code._start,lo); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame(killed ? lo : def,use.in(1)); + } + CodeGen pre = graph(); + RegAlloc uncolored = new RegAlloc(pre); + Op def0 = new Op(A,null,null,false,pre._start); + uncolored.newLRG(def0)._mask=A; + Op fixed = new Op(A,null,null,false,pre._start); + uncolored.newLRG(fixed)._mask=A; + SplitNode copy = pre._mach.split("test",(byte)0,null); + copy.setDef(0,pre._start); copy.setDef(1,def0); + assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); + } + + public static void coalescing() { + // Merge, incompatible masks, interference, capacity, and adjacency remapping. + for( int kind=0; kind<5; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + SplitNode copy = code._mach.split("test",(byte)0,null); + copy.setDef(0,code._start); copy.setDef(1,def); + Op use = new Op(null,new RegMask(3L),null,false,code._start,copy); + LRG from = alloc.newLRG(def), to = alloc.newLRG(copy); + from._mask = kind==1 ? A : new RegMask(3L); + to._mask = kind==1 ? B : new RegMask(3L); + from.machDef(def,false); from.machUse(copy,(short)1,false); + to.machDef(copy,false); to.machUse(use,(short)1,false); + LRG left = new LRG((short)100), right = new LRG((short)101); + if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); } + if( kind>=3 ) { + from.addNeighbor(left); left.addNeighbor(from); + if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); } + else { to.addNeighbor(left); left.addNeighbor(to); } + } + int fcnt=from.nadj(), tcnt=to.nadj(); + assertTrue(Coalesce.coalesce(0,alloc)); + if( kind==0 || kind==4 ) { + assertSame(def,use.in(1)); + assertSame(alloc.lrg(def),alloc.lrg(copy)); + assertSame(use,alloc.lrg(def)._machUse); + assertEquals(1,alloc.lrg(def)._uidx); + if( kind==4 ) { + assertEquals(1,left.nadj()); + assertSame(alloc.lrg(def),left._adj.at(0)); + assertSame(left,alloc.lrg(def)._adj.at(0)); + } + } else { + assertSame(copy,use.in(1)); + assertNotSame(alloc.lrg(def),alloc.lrg(copy)); + assertEquals(fcnt,from.nadj()); + assertEquals(tcnt,to.nadj()); + } + } + } + +} diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index e9b5eb2e..f4ce4366 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -40,8 +40,8 @@ abstract public class BuildLRG { int uidx = n.out(0)._inputs.find(n); RegMask mask1 = n.in (1) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(1))._mask; RegMask mask2 = n.in (2) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(2))._mask; - RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): alloc.lrg(n )._mask; - if( !mask1.overlap(masko) && mask2.overlap(masko) ) + RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): mach.outregmap(); + if( masko!=null && !mask1.overlap(masko) && mask2.overlap(masko) ) n.swap12(); } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 6dd6fbf1..bc14aadd 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -207,20 +207,7 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - // Disallow clone-ables from killing registers. Just fail - // them and re-clone closer to target... so no kill. - // Special case for Intel XOR used to zero. - Node n = (Node)m; - CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0(); - if( m.isClone() && // Must be clonable - (n.nOuts()>1 || // Has many users OR - // Only 1 user but effective use is remote block - effUseBlk != n.cfg0() )) - // Then fail the clonable; it should split or move - alloc.fail(alloc.lrg((Node)m)); - // Else clonable cannot move - else if( !tlrg.sub(killMask) ) - alloc.fail(tlrg); + if( !tlrg.sub(killMask) ) alloc.fail(tlrg); } } } @@ -438,13 +425,13 @@ abstract public class IFG { private static int pickRiskyScore( LRG lrg ) { // Pick single-def clonables that are not right next to their single-use. // Failing to color these will clone them closer to their uses. - if( !lrg._multiDef && lrg._machDef.isClone() ) { - Node def = ((Node)lrg._machDef); - Node use = ((Node)lrg._machUse); + if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) { + Node def = (Node)lrg._machDef; + Node use = (Node)lrg._machUse; CFGNode cfg = def.cfg0(); - if( cfg != use.cfg0() || // Different blocks OR + if( lrg._multiUse || cfg != use.cfg0() || // Many uses or different blocks OR // Same block, but not close - cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) + cfg._outputs.find(def)+1 < cfg._outputs.find(use) ) return 1000000; } @@ -452,7 +439,7 @@ abstract public class IFG { // and very cheap to spill. if( lrg._machDef instanceof CalleeSaveNode ) return 1000000-2-lrg._mask.firstReg(); - if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && + if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) return 1000000-1; @@ -506,7 +493,7 @@ abstract public class IFG { private static int biasable(Node split) { if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1 - if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Yes biasable, advance is slot 1 + if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Prefer the backedge in loops if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 10297a9a..adc198fc 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -176,17 +176,35 @@ public class RegAlloc { if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } + // Optional diagnostic for values accidentally shared across functions. + //assert verifyFunctionLocalEdges(); + // Top driver: repeated rounds of coloring and splitting. byte round=0; while( !graphColor(round) ) { split(round); if( round >= 7 ) // Really expect to be done soon - throw Utils.TODO("Allocator taking too long"); + throw new IllegalStateException("Register allocation made no progress after eight rounds"); round++; } postColor(); // Remove no-op spills } + boolean verifyFunctionLocalEdges() { + for( CFGNode bb : _code._cfg ) { + if( bb instanceof StartNode ) continue; + FunNode fun = bb.fun(); + for( Node use : bb._outputs ) + if( use instanceof MachNode mach && !(use instanceof ParmNode) ) + for( int i=1; i<use.nIns(); i++ ) { + Node def = use.in(i); + if( def==null || mach.regmap(i)==null || def.cfg0()==null || def.cfg0() instanceof StartNode ) continue; + assert def.cfg0().fun()==fun : "Cross-function register edge: "+def.uniqueName()+" -> "+use.uniqueName()+" input "+i; + } + } + return true; + } + private boolean graphColor(byte round) { _failed.clear(); _lrgs.clear(); @@ -233,7 +251,9 @@ public class RegAlloc { if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && - (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) + (lrg._1regDefCnt + lrg._1regUseCnt) > 0 && + // A fixed-register clone with flexible uses must split at the uses. + !(lrg._1regDefCnt==1 && lrg._machDef.isClone() && lrg._1regUseCnt==0) ) return splitEmptyMaskSimple(round,lrg); // Repeated single-reg uses from a single def. Special for archs // with more fixed regs. @@ -255,16 +275,16 @@ public class RegAlloc { // Split just after def if( lrg._1regDefCnt==1 && !lrg._machDef.isClone() ) - // Force must-split, even if a prior split same block because register - // conflicts. Example: + // An earlier copy is reusable only if no intervening clobber. + // Being in the same block alone is insufficient. Example: // alloc // V1/rax - forced by alloc // alloc // V2/rax - kills prior RAX // st4 [V1],len - No good, must split around - insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/); + insertAfterAndReplace(makeSplit("def/empty1",round,lrg),(Node)lrg._machDef,false); // Split just before use - if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) ) + if( lrg._1regUseCnt==1 ) insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg); return true; } @@ -491,8 +511,8 @@ public class RegAlloc { void findAllLRG( LRG lrg ) { _ns.clear(); int wd = 0; - _ns.push((Node)lrg._machDef); - _ns.push((Node)lrg._machUse); + if( lrg._machDef!=null ) _ns.push((Node)lrg._machDef); + if( lrg._machUse!=null ) _ns.push((Node)lrg._machUse); while( wd < _ns._len ) { Node n = _ns.at(wd++); if( lrg(n)!=lrg ) continue; @@ -615,10 +635,10 @@ public class RegAlloc { break; hi = hi.in(1); } - // Check no clobbers - for( int idx = j-1; bb.out(idx) != hi; idx++) { + // Walk backward from the later copy, including instructions without results. + for( int idx = j-1; bb.out(idx) != hi; idx--) { Node n = bb.out(idx); - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } lo.setDefOrdered(1,hi.in(1)); @@ -626,6 +646,12 @@ public class RegAlloc { } + private boolean clobbers(Node n, int reg) { + LRG lrg = lrg(n); + return lrg!=null && (lrg._reg==reg || lrg._reg==-1 && lrg._mask.size1() && lrg._mask.firstReg()==reg) || + n instanceof MachNode mach && mach.killmap()!=null && mach.killmap().test(reg); + } + public boolean sameBlockNoClobber( SplitNode split ) { Node def = split.in(1); CFGNode cfg = def.cfg0(); @@ -639,7 +665,7 @@ public class RegAlloc { Node n = cfg.out(idx); if( n==def0 ) return true; // No clobbers if( lrg(n) == lrg(def) ) return false; // Self conflict - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } throw Utils.TODO(); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index c7dda1da..303bba9e 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -72,16 +72,12 @@ public class RegMask { : Long.numberOfTrailingZeros(_bits1)+64); } public short nextReg(short reg) { - if( reg<64 ) { - long bits0 = _bits0 >> (reg+1); - if( bits0!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits0)); - reg=64; + if( reg < 63 ) { + long bits0 = _bits0 & (-1L << (reg+1)); + if( bits0!=0 ) return (short)Long.numberOfTrailingZeros(bits0); } - long bits1 = _bits1 >> (reg-64+1); - if( bits1!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits1)); - return -1; + long bits1 = reg < 64 ? _bits1 : reg < 127 ? _bits1 & (-1L << (reg-63)) : 0; + return bits1==0 ? -1 : (short)(64+Long.numberOfTrailingZeros(bits1)); } boolean isEmpty() { return _bits0==0 && _bits1==0; } @@ -98,8 +94,8 @@ public class RegMask { // Has exactly 1 bit set public boolean size1() { - return ((_bits0 & -_bits0)==_bits0 && _bits1==0) || - ((_bits1 & -_bits1)==_bits1 && _bits0==0); + return !isEmpty() && (((_bits0 & -_bits0)==_bits0 && _bits1==0) || + ((_bits1 & -_bits1)==_bits1 && _bits0==0)); } // Cardinality diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java index d06c0c35..df83ce1c 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -26,7 +26,9 @@ public class StoreRISC extends MemOpRISC { if( i==1 ) return null; // mem if( i==2 ) return riscv.RMASK; // ptr // 2 - index - if( i==4 ) return riscv.MEM_MASK; // Wide mask to store GPR and FPR + if( i==4 ) return _sz >= '4' + ? riscv.MEM_MASK // Word/dword value in GPR or FPR + : riscv.RMASK; // Byte/short stores require a GPR return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 5f090717..20578467 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -66,7 +66,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base in GPR if( i==3 ) return x86_64_v2.RMASK; // index in GPR - if( i==4 ) return _sz >= 2 + if( i==4 ) return _sz >= '4' ? x86_64_v2.MEM_MASK // value in GPR or XMM : x86_64_v2.RMASK; // Bytes and shorts in GPR only return null; // Anti-dependence diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 760344ec..e668f90d 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; @@ -24,6 +26,14 @@ return f(s); } + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } + @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } + @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } + @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } + @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } + @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } + @Test public void testPrintingRegisters() throws Exception { com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); } @@ -38,7 +48,7 @@ return f(s); } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src); + CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; @@ -83,7 +93,7 @@ val sqrt = { int x -> int cast_int = arg+2; return sqrt(arg) + sqrt(cast_int); """; - testCPU(src,"x86_64_v2", "Win64" ,55,null); + testCPU(src,"x86_64_v2", "Win64" ,48,null); testCPU(src,"riscv" , "SystemV",19,null); testCPU(src,"arm" , "SystemV",19,null); } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 38029ee8..49c95fb8 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -12,6 +13,54 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } + + @Test public void testNarrowStores() throws IOException { + for( String type : new String[]{"i8","u8","i16","u16"} ) { + String src = "struct S { "+type+" x; }; S !s = new S; s.x = arg; return 0;"; + CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); + int stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.riscv.StoreRISC st ) { + stores++; + assertEquals("Byte/short stores have no FP encoding",-1,st.regmap(4).nextReg((short)31)); + } + assertEquals(1,stores); + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu.regs[riscv.A0] = 0x8765; + assertEquals(0,cpu.step(100)); + assertEquals(type.endsWith("8") ? 0x65 : 0x8765, + type.endsWith("8") ? cpu.ld1z(1<<16) : cpu.ld2z(1<<16)); + code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"x86_64_v2",TestC.CALL_CONVENTION); + stores=0; + for( var bb : code._cfg ) + for( var node : bb.outs() ) + if( node instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.StoreX86 st ) { + stores++; + assertEquals("Byte/short stores have no XMM encoding",-1,st.regmap(4).nextReg((short)15)); + } + assertEquals(1,stores); + } + } + + @Test public void testNativeExitStatus() throws IOException { + Path source = Path.of("build/objs/nativeExit.c"); + Files.createDirectories(source.getParent()); + Files.writeString(source,"int main() { return 7; }\n"); + try { + TestC.gcc(source.toString(),null,null,false, + "build/objs/nativeExit"+(TestC.OS.startsWith("Windows") ? ".exe" : "")); + } catch( AssertionError error ) { + assertTrue(error.getMessage(),error.getMessage().contains("Program exit status")); + return; + } + fail("A failing native program must fail the test, even with empty stdout"); + } + @Test public void testArmSubtractRegisters() { EvalArm64 cpu = new EvalArm64(new byte[16],16); cpu.st4(0,0xCB020020); // SUB X0,X1,X2, no shift or flag update. @@ -82,7 +131,7 @@ return new s0.v1; } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 ) @@ -323,11 +372,11 @@ val sieve = { int N -> String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - TestC.run(src, "sieve", null, sprimes, 257); + TestC.run(src, "sieve", null, sprimes, 186); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. - EvalRisc5 R5 = TestRisc5.build("sieve", src, 100, 160, false); + EvalRisc5 R5 = TestRisc5.build("sieve", src, 100, 92, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) @@ -339,7 +388,7 @@ val sieve = { int N -> // Evaluate on ARM5 emulator; expect return of an array of primes in // the simulated heap. - EvalArm64 A5 = TestArm64.build("sieve", src, 100, 160, false); + EvalArm64 A5 = TestArm64.build("sieve", src, 100, 94, false); int trap_arm = A5.step(10000); assertEquals(0, trap_arm); int ary_arm = (int)A5.regs[arm.X0]; @@ -450,7 +499,7 @@ val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, i """; String arg_count = "191.000000\n"; - TestC.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 42 : 15); + TestC.run(src, "arg_count", null, arg_count, TestC.CALL_CONVENTION.equals("Win64") ? 32 : 15); EvalRisc5 R5 = TestRisc5.build("no_stack_arg_count", src, 0, 4, false); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 78b9e7a1..fa9036d2 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; import java.nio.file.Files; @@ -39,7 +40,7 @@ fib(10); } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 ) diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 56a672aa..661d4f39 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -1,4 +1,6 @@ package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -90,7 +92,7 @@ public class Chapter23Test { static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 ) diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index a4fb5829..a1dd6eaa 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -1,4 +1,6 @@ package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -37,7 +39,7 @@ public class Chapter24Test { } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 ) diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java index a1c02ede..d0fdae0c 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -27,7 +29,7 @@ public class TestArm64 { // Compile and run a simple program public static EvalArm64 build( String dir, String src, String file, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("arm", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",null); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java b/chapter24/src/test/java/com/seaofnodes/simple/TestC.java index f1831929..aed9f844 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TestC.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; @@ -75,7 +76,7 @@ public abstract class TestC { String obj = bin+".o"; String exe = OS.startsWith("Windows") ? bin+".exe" : bin; // Compile simple, emit ELF - CodeGen code = new CodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); + CodeGen code = new CheckedCodeGen(src, arg).driver( CPU_PORT, simple_conv, obj); String result = gcc(obj, c_conv, cfile, false, exe ); assertEquals(expected,result); @@ -130,10 +131,9 @@ public abstract class TestC { ProcessBuilder smp = new ProcessBuilder(args); if( stdin ) smp.redirectInput(ProcessBuilder.Redirect.INHERIT); Process p = smp.start(); - try { exit = (byte)p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } + try { exit = p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } result = new String(p.getInputStream().readAllBytes()); - if( exit!=0 ) - System.err.println("exec exit code: "+exit); + assertEquals("Program exit status",0,exit); return result; } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java index a8f6817e..72a05c61 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.Node; @@ -26,7 +27,7 @@ public abstract class TestRisc5 { // Compile and run a simple program public static EvalRisc5 build( String dir, String src, String file, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("riscv", "SystemV",null); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",null); if( print ) { code.print_as_hex(); System.out.print(code.asm()); } // Allocation quality not degraded diff --git a/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..b2d14a02 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,209 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; + +// Small scheduled machine graphs isolate register constraints from peepholes. +public class RegAllocTestSupport { + private static final RegMask A = new RegMask(0), B = new RegMask(1); + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + final boolean _clone; + Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT; + } + @Override public String op() { return "testOp"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @Override public RegMask killmap() { return _kill; } + @Override public boolean isClone() { return _clone; } + @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + private static CodeGen graph() { + CodeGen code = new CodeGen(""); + code._mach = new x86_64_v2(code); + code._cfg.add(code._start); + return code; + } + + public static void masks() { + for( int reg : new int[]{0,63,64,65,127} ) { + RegMask mask = new RegMask(reg); + assertEquals(reg,mask.firstReg()); + assertEquals(1,mask.size()); + } + assertEquals(-1,new RegMask(0L).firstReg()); + assertFalse(new RegMask(0L).size1()); + RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1); + assertEquals(64,boundary.nextReg((short)63)); + assertEquals(127,boundary.nextReg((short)64)); + assertEquals(-1,boundary.nextReg((short)127)); + } + + public static void union() { + CodeGen code = graph(); + Op use = new Op(null,B,null,false,code._start); + LRG a = new LRG((short)1), b = new LRG((short)2); + a._mask = new RegMask(3L); + b._mask = new RegMask(6L); + b.machUse(use,(short)2,true); + LRG both = a.union(b); + assertNotNull(both._mask); + assertEquals(1,both._mask.firstReg()); + assertEquals(1,both._mask.size()); + assertSame(use,both._machUse); + assertEquals(2,both._uidx); + } + + public static void killWithoutResult() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,A,false,code._start); // Clobbers A, produces no value. + new Op(null,A,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + } + + public static void nullUseMask() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,null,false,code._start,def); // Scheduling dependency only. + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertTrue(IFG.build(0,alloc)); + } + + public static void cloneRegisterClass() { + for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) { + CodeGen code = graph(); + Op def = new Op(A,null,null,true,code._start); + Op use = new Op(null,required,null,false,code._start,def); + Op use2 = new Op(null,required,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses. + assertEquals(0,alloc.regnum(def)); + assertTrue(required.test(alloc.regnum(use.in(1)))); + assertTrue(required.test(alloc.regnum(use2.in(1)))); + assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void commutativePhi() { + CodeGen code = graph(); + Op a = new Op(A,null,null,false,code._start); + Op b = new Op(A,null,null,false,code._start); + Op add = new Op(A,A,null,false,code._start,a,b) { + @Override public boolean commutes() { return true; } + }; + RegionNode region = new RegionNode(null,code._start,code._start); + new PhiNode("sum",TypeInteger.BOT,region,add,a); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,new RegAlloc(code))); + } + + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. + public static class CheckedCodeGen extends CodeGen { + public CheckedCodeGen(String src) { super(src); } + public CheckedCodeGen(String src, TypeInteger arg) { super(src,arg); } + @Override public CodeGen regAlloc() { + super.regAlloc(); + checkRegisters(this); + return this; + } + } + + public static void checkRegisters(CodeGen code) { + assertTrue(code._regAlloc.verifyFunctionLocalEdges()); + for( CFGNode bb : code._cfg ) + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach ) { + if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n))); + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i)))); + if( mach.twoAddress()!=0 ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress()))); + } + if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + } + } + + public static void copyClobber() throws Exception { + for( boolean killed : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode hi = code._mach.split("test",(byte)0,null); + hi.setDef(0,code._start); hi.setDef(1,def); + alloc.newLRG(hi)._reg=1; + new Op(null,null,killed ? A : null,false,code._start); + SplitNode lo = code._mach.split("test",(byte)0,null); + lo.setDef(0,code._start); lo.setDef(1,hi); + alloc.newLRG(lo)._reg=0; + Op use = new Op(null,A,null,false,code._start,lo); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame(killed ? lo : def,use.in(1)); + } + CodeGen pre = graph(); + RegAlloc uncolored = new RegAlloc(pre); + Op def0 = new Op(A,null,null,false,pre._start); + uncolored.newLRG(def0)._mask=A; + Op fixed = new Op(A,null,null,false,pre._start); + uncolored.newLRG(fixed)._mask=A; + SplitNode copy = pre._mach.split("test",(byte)0,null); + copy.setDef(0,pre._start); copy.setDef(1,def0); + assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); + } + + public static void coalescing() { + // Merge, incompatible masks, interference, capacity, and adjacency remapping. + for( int kind=0; kind<5; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + SplitNode copy = code._mach.split("test",(byte)0,null); + copy.setDef(0,code._start); copy.setDef(1,def); + Op use = new Op(null,new RegMask(3L),null,false,code._start,copy); + LRG from = alloc.newLRG(def), to = alloc.newLRG(copy); + from._mask = kind==1 ? A : new RegMask(3L); + to._mask = kind==1 ? B : new RegMask(3L); + from.machDef(def,false); from.machUse(copy,(short)1,false); + to.machDef(copy,false); to.machUse(use,(short)1,false); + LRG left = new LRG((short)100), right = new LRG((short)101); + if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); } + if( kind>=3 ) { + from.addNeighbor(left); left.addNeighbor(from); + if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); } + else { to.addNeighbor(left); left.addNeighbor(to); } + } + int fcnt=from.nadj(), tcnt=to.nadj(); + assertTrue(Coalesce.coalesce(0,alloc)); + if( kind==0 || kind==4 ) { + assertSame(def,use.in(1)); + assertSame(alloc.lrg(def),alloc.lrg(copy)); + assertSame(use,alloc.lrg(def)._machUse); + assertEquals(1,alloc.lrg(def)._uidx); + if( kind==4 ) { + assertEquals(1,left.nadj()); + assertSame(alloc.lrg(def),left._adj.at(0)); + assertSame(left,alloc.lrg(def)._adj.at(0)); + } + } else { + assertSame(copy,use.in(1)); + assertNotSame(alloc.lrg(def),alloc.lrg(copy)); + assertEquals(fcnt,from.nadj()); + assertEquals(tcnt,to.nadj()); + } + } + } + +} 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 911e69f6..aa33a7ec 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -46,7 +46,7 @@ abstract public class BuildLRG { RegMask mask1 = n.in (1) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(1))._mask; RegMask mask2 = n.in (2) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(2))._mask; RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): mach.outregmap(); - if( !mask1.overlap(masko) && mask2.overlap(masko) ) + if( masko!=null && !mask1.overlap(masko) && mask2.overlap(masko) ) n.swap12(); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java index e4e9dd69..8d09b58c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -447,7 +447,7 @@ abstract public class IFG { // Pick single-def clonables that are not right next to their single-use. // Rank by the area recovered by cloning closer to the use. - if( !lrg._multiDef && lrg._machDef.isClone() && lrg._machUse != null ) { + if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) { Node def = ((Node)lrg._machDef); Node use = ((Node)lrg._machUse); CFGNode cfg = def.cfg0(); @@ -527,7 +527,7 @@ abstract public class IFG { private static int biasable(Node split) { if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1 - if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Yes biasable, advance is slot 1 + if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Prefer the backedge in loops if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index f8c96ff2..4a880a19 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -190,14 +190,14 @@ public class RegAlloc { while( !graphColor(round) ) { split(round); if( round >= 7 ) // Really expect to be done soon - throw Utils.TODO("Allocator taking too long"); + throw new IllegalStateException("Register allocation made no progress after eight rounds"); round++; } postColor(); // Remove no-op spills _done = true; } - private boolean verifyFunctionLocalEdges() { + boolean verifyFunctionLocalEdges() { for( CFGNode bb : _code._cfg ) for( Node use : bb._outputs ) { FunNode useFun = funOf(use); @@ -300,7 +300,9 @@ public class RegAlloc { if( lrg._mask.isEmpty() ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && - (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) + (lrg._1regDefCnt + lrg._1regUseCnt) > 0 && + // A fixed-register clone with flexible uses must split at the uses. + !(lrg._1regDefCnt==1 && lrg._machDef.isClone() && lrg._1regUseCnt==0) ) return splitEmptyMaskSimple(round,lrg); // Repeated single-reg uses from a single def. Special for archs // with more fixed regs. @@ -734,10 +736,10 @@ public class RegAlloc { break; hi = hi.in(1); } - // Check no clobbers - for( int idx = j-1; bb.out(idx) != hi; idx++) { + // Walk backward from the later copy, including instructions without results. + for( int idx = j-1; bb.out(idx) != hi; idx--) { Node n = bb.out(idx); - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } lo.setDefOrdered(1,hi.in(1)); @@ -745,6 +747,12 @@ public class RegAlloc { } + private boolean clobbers(Node n, int reg) { + LRG lrg = lrg(n); + return lrg!=null && (lrg._reg==reg || lrg._reg==-1 && lrg._mask.size1() && lrg._mask.firstReg()==reg) || + n instanceof MachNode mach && mach.killmap()!=null && mach.killmap().test(reg); + } + public boolean sameBlockNoClobber( SplitNode split ) { Node def = split.in(1); CFGNode cfg = def.cfg0(); @@ -758,7 +766,7 @@ public class RegAlloc { Node n = cfg.out(idx); if( n==def0 ) return true; // No clobbers if( lrg(n) == lrg(def) ) return false; // Self conflict - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } throw Utils.TODO("Should not reach here"); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index 81e47e8e..9cb9ec16 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -71,16 +71,12 @@ public class RegMask { : Long.numberOfTrailingZeros(_bits1)+64); } public short nextReg(short reg) { - if( reg<64 ) { - long bits0 = _bits0 >> (reg+1); - if( bits0!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits0)); - reg=64; + if( reg < 63 ) { + long bits0 = _bits0 & (-1L << (reg+1)); + if( bits0!=0 ) return (short)Long.numberOfTrailingZeros(bits0); } - long bits1 = _bits1 >> (reg-64+1); - if( bits1!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits1)); - return -1; + long bits1 = reg < 64 ? _bits1 : reg < 127 ? _bits1 & (-1L << (reg-63)) : 0; + return bits1==0 ? -1 : (short)(64+Long.numberOfTrailingZeros(bits1)); } boolean isEmpty() { return _bits0==0 && _bits1==0; } @@ -97,8 +93,8 @@ public class RegMask { // Has exactly 1 bit set public boolean size1() { - return ((_bits0 & -_bits0)==_bits0 && _bits1==0) || - ((_bits1 & -_bits1)==_bits1 && _bits0==0); + return !isEmpty() && (((_bits0 & -_bits0)==_bits0 && _bits1==0) || + ((_bits1 & -_bits1)==_bits1 && _bits0==0)); } // Cardinality diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 20619c1b..647b253e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -1,5 +1,7 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; + import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; @@ -23,6 +25,14 @@ return f(s); } + @Test public void testAllocatorMasks() { com.seaofnodes.simple.codegen.RegAllocTestSupport.masks(); } + @Test public void testAllocatorUnion() { com.seaofnodes.simple.codegen.RegAllocTestSupport.union(); } + @Test public void testAllocatorCopyClobber() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyClobber(); } + @Test public void testAllocatorCommutativePhi() { com.seaofnodes.simple.codegen.RegAllocTestSupport.commutativePhi(); } + @Test public void testAllocatorKills() { com.seaofnodes.simple.codegen.RegAllocTestSupport.killWithoutResult(); } + @Test public void testAllocatorDependencies() { com.seaofnodes.simple.codegen.RegAllocTestSupport.nullUseMask(); } + @Test public void testAllocatorCloneClass() { com.seaofnodes.simple.codegen.RegAllocTestSupport.cloneRegisterClass(); } + @Test public void testPrintingRegisters() throws Exception { com.seaofnodes.simple.codegen.PrintRegTestSupport.check(); } @@ -37,7 +47,7 @@ return f(s); } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src); + CodeGen code = new CheckedCodeGen(src); code.driver(CodeGen.Phase.RegAlloc,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; @@ -102,7 +112,7 @@ val _test_sqrt_noInline = { flt x -> }; flt farg = arg; return _test_sqrt_noInline(farg) + _test_sqrt_noInline(farg+2.0); """; - testCPU(src,"x86_64_v2", "SystemV",48,null); + testCPU(src,"x86_64_v2", "SystemV",40,null); testCPU(src,"riscv" , "SystemV",17,null); testCPU(src,"arm" , "SystemV",18,null); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index e8a9e700..e194829a 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; @@ -9,6 +10,8 @@ import org.junit.Test; import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } + @Test public void testArmSubtractRegisters() { EvalArm64 cpu = new EvalArm64(new byte[16],16); cpu.st4(0,0xCB020020); // SUB X0,X1,X2, no shift or flag update. @@ -79,7 +82,7 @@ return new _s0.v1; } static void testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) @@ -447,7 +450,7 @@ val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, i """; String arg_count = "191.000000\n"; - TestC.runC(src, "arg_count", arg_count, TestC.CALL_CONVENTION.equals("win64") ? 31 : 15); + TestC.runC(src, "arg_count", arg_count, TestC.CALL_CONVENTION.equals("win64") ? 35 : 15); EvalRisc5 R5 = TestRisc5.build( src, "addAll", 0, 4, false); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 96e7fce7..fde523cf 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -37,7 +38,7 @@ return new s0.v1; } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 0e6398ee..923395bf 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -1,4 +1,6 @@ package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -47,7 +49,7 @@ public class Chapter23Test { static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 1307d2ce..0abdfb3e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -1,4 +1,6 @@ package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -37,7 +39,7 @@ public class Chapter24Test { } static CodeGen testCPU( String src, String cpu, String os, int spills, String stop ) { - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); + CodeGen code = new CheckedCodeGen(src).driver(CodeGen.Phase.Encoding,cpu,os); int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java b/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java index 14864d64..d2c6cde4 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestArm64.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.FunNode; import com.seaofnodes.simple.node.cpus.arm.arm; @@ -14,7 +15,7 @@ public class TestArm64 { public static EvalArm64 build( String main, String src, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("arm", "SystemV",true,false); + CodeGen code = new CheckedCodeGen(src).driver("arm", "SystemV",true,false); // Allocation quality not degraded int delta = spills>>3; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java index 55c62c37..e0ee701a 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; @@ -118,7 +119,7 @@ public abstract class TestC { String obj = pathBase+".o"; String exe = pathBase+(OS.startsWith("Windows") ? ".exe" : ""); // Compile simple, emit ELF - CodeGen code = new CodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT); + CodeGen code = new CheckedCodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT); code.driver( CPU_PORT, simple_conv, false, cfile==null ); linkExe(obj, c_conv, cfile, linkObjs(externPaths), exe); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java b/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java index 658909ca..1de5e3bc 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestRisc5.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.node.FunNode; @@ -14,7 +15,7 @@ public abstract class TestRisc5 { public static EvalRisc5 build( String src, String main, int arg, int spills, boolean print ) throws IOException { // Compile and export Simple - CodeGen code = new CodeGen(src).driver("riscv", "SystemV",true,false); + CodeGen code = new CheckedCodeGen(src).driver("riscv", "SystemV",true,false); // Allocation quality not degraded int delta = spills>>3; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java new file mode 100644 index 00000000..5e1b276e --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -0,0 +1,212 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.x86_64_v2.x86_64_v2; +import com.seaofnodes.simple.type.TypeInteger; +import static org.junit.Assert.*; + +// Small scheduled machine graphs isolate register constraints from peepholes. +public class RegAllocTestSupport { + private static final RegMask A = new RegMask(0), B = new RegMask(1); + private static class Op extends MachConcreteNode { + final RegMask _def, _use, _kill; + final boolean _clone; + Op(RegMask def, RegMask use, RegMask kill, boolean clone, Node... ins) { + super(ins); _def=def; _use=use; _kill=kill; _clone=clone; _type=TypeInteger.BOT; + } + @Override public String op() { return "testOp"; } + @Override public RegMask outregmap() { return _def; } + @Override public RegMask regmap(int i) { return _use; } + @Override public RegMask killmap() { return _kill; } + @Override public boolean isClone() { return _clone; } + @Override public Node copy() { return new Op(_def,_use,_kill,_clone,(Node)null); } + @Override public void encoding(Encoding enc) { throw new AssertionError(); } + } + private static CodeGen graph() { + CodeGen code = new CodeGen(""); + code._mach = new x86_64_v2(code); + code._cfg.add(code._start); + return code; + } + + public static void masks() { + for( int reg : new int[]{0,63,64,65,127} ) { + RegMask mask = new RegMask(reg); + assertEquals(reg,mask.firstReg()); + assertEquals(1,mask.size()); + } + assertEquals(-1,new RegMask(0L).firstReg()); + assertFalse(new RegMask(0L).size1()); + RegMask boundary = new RegMask(Long.MIN_VALUE,Long.MIN_VALUE|1); + assertEquals(64,boundary.nextReg((short)63)); + assertEquals(127,boundary.nextReg((short)64)); + assertEquals(-1,boundary.nextReg((short)127)); + } + + public static void union() { + CodeGen code = graph(); + Op use = new Op(null,B,null,false,code._start); + LRG a = new LRG((short)1,null), b = new LRG((short)2,null); + a._mask = new RegMask(3L); + b._mask = new RegMask(6L); + b.machUse(use,(short)2,true); + LRG both = a.union(b); + assertNotNull(both._mask); + assertEquals(1,both._mask.firstReg()); + assertEquals(1,both._mask.size()); + assertSame(use,both._machUse); + assertEquals(2,both._uidx); + } + + public static void killWithoutResult() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,A,false,code._start); // Clobbers A, produces no value. + new Op(null,A,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + } + + public static void nullUseMask() { + CodeGen code = graph(); + Op def = new Op(A,null,null,false,code._start); + new Op(null,null,null,false,code._start,def); // Scheduling dependency only. + RegAlloc alloc = new RegAlloc(code); + assertTrue(BuildLRG.run(0,alloc)); + assertTrue(IFG.build(0,alloc)); + } + + public static void cloneRegisterClass() { + for( RegMask required : new RegMask[]{B,new RegMask(6L)} ) { + CodeGen code = graph(); + Op def = new Op(A,null,null,true,code._start); + Op use = new Op(null,required,null,false,code._start,def); + Op use2 = new Op(null,required,null,false,code._start,def); + RegAlloc alloc = new RegAlloc(code); + alloc.regAlloc(); // Re-cloning an A-only value cannot satisfy B/C uses. + assertEquals(0,alloc.regnum(def)); + assertTrue(required.test(alloc.regnum(use.in(1)))); + assertTrue(required.test(alloc.regnum(use2.in(1)))); + assertTrue(use.in(1) instanceof SplitNode); + } + } + + public static void commutativePhi() { + CodeGen code = graph(); + Op a = new Op(A,null,null,false,code._start); + Op b = new Op(A,null,null,false,code._start); + Op add = new Op(A,A,null,false,code._start,a,b) { + @Override public boolean commutes() { return true; } + }; + RegionNode region = new RegionNode(null,code._start,code._start); + new PhiNode("sum",region,add,a); + code._cfg.add(region); + assertTrue(BuildLRG.run(0,new RegAlloc(code))); + } + + // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. + public static class CheckedCodeGen extends CodeGen { + public CheckedCodeGen(String src) { super(src); } + public CheckedCodeGen(String modDir, String buildDir, com.seaofnodes.simple.util.Ary<String> externPaths, + String srcName, String src, long seed, boolean reset, TypeInteger arg) { + super(modDir,buildDir,externPaths,srcName,src,seed,reset,arg); + } + @Override public CodeGen regAlloc() { + super.regAlloc(); + checkRegisters(this); + return this; + } + } + + public static void checkRegisters(CodeGen code) { + assertTrue(code._regAlloc.verifyFunctionLocalEdges()); + for( CFGNode bb : code._cfg ) + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach ) { + if( code._regAlloc.regnum(n)>=0 && mach.outregmap()!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid,code._regAlloc.regnum(n)>=0 && mach.outregmap().test(code._regAlloc.regnum(n))); + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + if( n.in(i)!=null && code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i)!=null ) + assertTrue(n.getClass().getSimpleName()+"#"+n._nid+" input "+i,code._regAlloc.regnum(n.in(i))>=0 && mach.regmap(i).test(code._regAlloc.regnum(n.in(i)))); + if( mach.twoAddress()!=0 ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(mach.twoAddress()))); + } + if( n instanceof PhiNode && code._regAlloc.regnum(n)>=0 ) + for( int i=n instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) + assertEquals(code._regAlloc.regnum(n),code._regAlloc.regnum(n.in(i))); + } + } + + public static void copyClobber() throws Exception { + for( boolean killed : new boolean[]{false,true} ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def,null)._reg=0; + SplitNode hi = code._mach.split(null,"test",(byte)0); + hi.setDef(0,code._start); hi.setDef(1,def); + alloc.newLRG(hi,null)._reg=1; + new Op(null,null,killed ? A : null,false,code._start); + SplitNode lo = code._mach.split(null,"test",(byte)0); + lo.setDef(0,code._start); lo.setDef(1,hi); + alloc.newLRG(lo,null)._reg=0; + Op use = new Op(null,A,null,false,code._start,lo); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame(killed ? lo : def,use.in(1)); + } + CodeGen pre = graph(); + RegAlloc uncolored = new RegAlloc(pre); + Op def0 = new Op(A,null,null,false,pre._start); + uncolored.newLRG(def0,null)._mask=A; + Op fixed = new Op(A,null,null,false,pre._start); + uncolored.newLRG(fixed,null)._mask=A; + SplitNode copy = pre._mach.split(null,"test",(byte)0); + copy.setDef(0,pre._start); copy.setDef(1,def0); + assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); + } + + public static void coalescing() { + // Merge, incompatible masks, interference, capacity, and adjacency remapping. + for( int kind=0; kind<5; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(new RegMask(3L),null,null,false,code._start); + SplitNode copy = code._mach.split(null,"test",(byte)0); + copy.setDef(0,code._start); copy.setDef(1,def); + Op use = new Op(null,new RegMask(3L),null,false,code._start,copy); + LRG from = alloc.newLRG(def,null), to = alloc.newLRG(copy,null); + from._mask = kind==1 ? A : new RegMask(3L); + to._mask = kind==1 ? B : new RegMask(3L); + from.machDef(def,false); from.machUse(copy,(short)1,false); + to.machDef(copy,false); to.machUse(use,(short)1,false); + LRG left = new LRG((short)100,null), right = new LRG((short)101,null); + if( kind==2 ) { from.addNeighbor(to); to.addNeighbor(from); } + if( kind>=3 ) { + from.addNeighbor(left); left.addNeighbor(from); + if( kind==3 ) { to.addNeighbor(right); right.addNeighbor(to); } + else { to.addNeighbor(left); left.addNeighbor(to); } + } + int fcnt=from.nadj(), tcnt=to.nadj(); + assertTrue(Coalesce.coalesce(0,alloc)); + if( kind==0 || kind==4 ) { + assertSame(def,use.in(1)); + assertSame(alloc.lrg(def),alloc.lrg(copy)); + assertSame(use,alloc.lrg(def)._machUse); + assertEquals(1,alloc.lrg(def)._uidx); + if( kind==4 ) { + assertEquals(1,left.nadj()); + assertSame(alloc.lrg(def),left._adj.at(0)); + assertSame(left,alloc.lrg(def)._adj.at(0)); + } + } else { + assertSame(copy,use.in(1)); + assertNotSame(alloc.lrg(def),alloc.lrg(copy)); + assertEquals(fcnt,from.nadj()); + assertEquals(tcnt,to.nadj()); + } + } + } + +} diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 159bc9e6..b2fe0381 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -12,6 +12,61 @@ establish the review workflow. No renumbering is committed. Keep each correction's reduced failure, smallest patch, and test results together for review. +## Follow-ups exposed by the Chapter 22 allocator review + +- **Narrow-store register masks:** fixed locally in 22-24, with + `Chapter21Test.testNarrowStores`. Bring the x86 restriction to 20-21, + and the RISC-V restriction to 21; 19's masks and 20's RISC-V mask are + already general-register-only, and 25 already has both fixes. Byte/short stores + cannot consume XMM/FPR values. The old x86 `_sz >= 2` compares a character to + an integer and always accepts XMM; the intended threshold is `'4'`. RISC-V + previously accepted its full memory mask for every width. With Chapter 21's + bias in 22, `testSextSuccess` emitted an invalid FP byte store on RISC-V and + asserted in `StoreX86.encVal` on x86. Preserve cohort data when backporting: + correcting a mask can substantially change spill counts even without tuning. +- **FunPtrNode backport: defer until register allocation work is complete.** The + minimal reproducer is `return {->42;};`; `return sys.io.p;` fails for the same + reason. Both fail on x86, RISC-V, and ARM at the default seed 123. The first + iterative Opto pass preserves the target. The subsequent pruning loop in + `CodeGen.opto` equates no linked calls with no callers for anonymous and `sys.` + functions, clears their unknown-caller Start edge, and deletes their bodies. + Their function-address ConstantNodes have no edge to keep the bodies alive. + The returned pointer survives while its Return disappears from Stop. + + Instruction selection resets NIDs and never selects the deleted function, so + the linker still maps its pointer to an ideal FunNode. In the reduced anonymous + case that node is 256; the x86 machine graph has UID 19. `Encoding.relo` accepts + the stale target and `patchLocalRelocations` indexes `_opStart[256]`. Enlarging + the array would merely hide a missing function body and produce a wrong address. + + `val f = {->42;}; return f;` retains the named function and encodes on all three + targets. An isolated build that excludes anonymous functions from pruning also + encodes both anonymous reproductions, confirming the cause; it does not fix + escaped `sys.` addresses. Cliff's chosen direction is to investigate backporting + Chapter 25's `FunPtrNode`, whose edge to the function Return keeps the function + body alive. This supersedes the proposed address-reference scan. Leave both + examples as documented known failures while finishing the allocator chapters; + do not fold this reachability change into that work. + + After register allocation, find the earliest applicable chapter and carry the + function-pointer representation and its retention rules together: pointer + creation, Opto's unknown-caller pruning, instruction selection, global constant + cloning, and relocation must agree on the retained function. Adapt these to + each chapter without importing unrelated Chapter 25 module/escape machinery. + Validate a returned pointer by calling it, and cover library pointers and + genuinely unused helpers. Chapter 21 lacks this pruning pass and also treats a constant-only + default main differently, so its old encoding-only coverage was not equivalent. + Diagnostic logs are in `chapter22/build/funptr-review`; the reduced sources and + causal trace above are the durable reproduction. +- **String without an explicit return in 22:** use the unchanged source in + `Chapter20Test.testString`, with the same driver and seeds 0-29. All three CPUs + fail before allocation, in loop-tree construction or GCM (missing loop owner, + dead CallEnd, or a FunNode cast to LoopNode, depending on seed). The original + snapshot reproduces the same 90 failures; seed 123 folds the work away. Reduce + this around Chapter 22's default-return/dead-call handling before changing a + central reachability invariant. Do not count a different seed or added return + as fixing this input. + ## AOT class initialization: larger independent work Proposed on 2026-09-19; deferred behind the smaller BXX cleanup above. This is @@ -69,7 +124,7 @@ Chapter 25 suite, including `make -j 4 tests`. | Group | Eventual home | Why not in the small queue yet | |---|---|---| -| Register allocation and spilling | 20 onward | Chapters 20-21 correction/support passes complete locally; review Chapter 21 statistics before Chapter 22. Staged quality work remains below. | +| Register allocation and spilling | 20 onward | Shared corrections/support now carried through 25; staged allocator/cohort/README reviews are complete through 22, with 23 next. | | Conditional Store and array Load control | Memory/arrays chapters | Reproduce under the earlier alias model before extracting fixes from the new memory implementation. | | SCCP dependencies, function revival, reachability | 24; some foundations may fit 18 | Separate old-IR corrections from new Guard/Escape/BulkMemPhi and external-caller machinery. | | TypeScalar, numeric modes, guards, symbolic fields, open/forward types | Revisit earlier homes later | A connected incomplete-types architecture, including phase ordering and errors. | @@ -78,9 +133,10 @@ Chapter 25 suite, including `make -j 4 tests`. ## Register allocation: correctness first, staged improvements -Review on 2026-09-20. The staged plan follows; Chapters 20-21 -have since been implemented and validated as recorded below. Later snapshots -remain pending. Compared RegAlloc, BuildLRG, IFG, +Review on 2026-09-20. The staged plan follows; Chapters 20-22 +have since been implemented and validated as recorded below. Shared corrections +and test support have also been carried through 23-25; their quality/cohort/README +reviews remain pending. Compared RegAlloc, BuildLRG, IFG, LRG, Coalesce, RegMask, and split support across 20-25, with the original fix commits. Allocation starts in 20; 19 has instruction selection/register masks but no coloring allocator. Most changes are in 20->21 and 24->25. The 22->23 @@ -139,6 +195,13 @@ to add persistent deferral state to the first allocator chapter. - Record actual `_spills` and `_spillScaled` for each compilation, keyed by test, CPU, ABI, and fixed seed. Both count retained SplitNodes; `_spillScaled` weights each by `8^loopDepth`. These are move/split metrics, not solely memory traffic. +- Use one fixed optimizer seed for routine backend validation. Seeds shuffle + IterPeeps/Opto worklists, whose output should normalize modulo NIDs and equivalent + operand orderings; similar post-Opto graphs give little additional allocation, + scheduling, or encoding coverage. Reserve seed sweeps for optimizer/worklist + investigations or demonstrated order-sensitive failures. Inspect post-Opto + differences before multiplying backend runs. Prefer varied programs, register + constraints, targets/ABIs, and execution checks for allocator coverage. - Compare total scaled counts as the existing quality measure, and report raw totals plus the largest local changes. Report per CPU/ABI as well as the whole suite so a regression on one target is visible. Include compilations without @@ -153,14 +216,14 @@ to add persistent deferral state to the first allocator chapter. of the heuristic's exact spill count. - `splitBypass` originally scanned from `j-1` with `idx++` throughout 20-25, reaching its own destination and rejecting nonadjacent bypasses. Corrected - in 20-21 with intervening kill-mask checks and a regression; 22-25 remain pending. + through 25 with intervening kill-mask checks and a regression. Pre-color copy reuse also checks fixed-register definitions before they have an assigned `_reg`. Chapter 25 is not a complete correctness reference. Suggested execution order: support/measurement, small mask/LRG correctness fixes, constrained-register and self-conflict regressions/fixes, then one quality technique at a time. Run each affected snapshot's full suite at each -accepted boundary. Chapters 20-21 have now been implemented; stop for Cliff's review before 22. +accepted boundary. Chapters 20-22 have now been implemented; stop for Cliff's review before 23. Review each chapter's README along the way. Chapter 21's encoding discussion has been shortened, with the bit-level notes retained as a separate reference. End each README with its RegAlloc improvement, measured cohort table, and commentary; the Chapter 25 @@ -206,6 +269,66 @@ Historical results below are dated evidence, not a substitute for a fresh baseline. Logs live in ignored build directories and may no longer exist. Reusable implementation lessons are in `skills/chapter25-codex-notes.md`. +### Shared allocator fixes/support: forwarded through 25, 2026-09-20 + +At Cliff's request, carried the common Chapter 22 corrections into 23-25 in +this review batch, avoiding repeated chapter-by-chapter review of the same +changes. Preserved each later allocator's existing grouping, split-delay, and +area/cost choices; the staged quality/cohort/README reviews still resume at 23. + +The shared packet includes bounded register-mask iteration and nonempty +single-bit tests; commutative BuildLRG output fallback/null masks; resultless +kill handling; fixed-register clone progress; null sample/traversal guards; +and backward copy bypass with kill masks and uncolored fixed definitions. +Chapters 23-24 also receive the corrected clone adjacency/multiple-use test, +narrow-store masks, and native process exit-status assertions. Chapter 25 +already has the store/exit-status fixes and retains its module-aware verifier. + +Forwarded all eight RegAllocTestSupport diagnostic groups and Chapter20Test/ +Chapter21Test hooks. Generic allocation, encoding, native, and emulator helpers +use CheckedCodeGen, whose regAlloc override checks function ownership, register +masks, two-address constraints, and Phis immediately after allocation. Encoding +adds untyped branches and rewrites tail calls, so running these checks afterward +is too late: even Call.regmap may consult CFG.fun. This test-only hook preserves +25's driver serialization/import-unlink ordering. Chapter 22 uses the same hook. + +Unmodified destination baselines passed. Against their saved main classes, +five diagnostic groups fail in 23/24 (masks, resultless kills, clone progress, +commutative Phi fallback, copy clobbers), and three fail in 25 (masks, clone +progress, copy clobbers). All eight pass in all three corrected destinations. +Final `make -j 4 tests` passes 23: 428 + 1 fuzzer, 24: 451 + 1 fuzzer, +and 25: 459 tests across all six groups (8 + 386 + 34 + 18 + 1 + 12). +Chapter 22 still passes 416 + 1 fuzzer; its separate `make spill-stats` passes +55 tests / 115 allocations with the unchanged 838 raw / 1,496 weighted total. + +For this common-fix comparison, froze each destination's existing local program +suite and default seed. Included its Chapter20-24 allocator/native cases as +applicable, BrainFuck, and MergeSort; excluded diagnostic graphs/new regressions. +These are within-chapter before/after comparisons, not the historical cohort +rows needed for the later README reviews. In particular, 25's module suite is +covered by the full tests, not included in these spill sums. + +| Compiler / same local suite | Allocations | Raw before | Raw after | Weighted before | Weighted after | +|---|---:|---:|---:|---:|---:| +| 23 | 119 | 629 | 614 | 1,511 | 1,279 | +| 24 | 174 | 968 | 953 | 2,620 | 2,381 | +| 25 | 146 | 660 | 656 | 1,255 | 1,244 | + +| Compiler | ARM weighted | RISC-V weighted | x86 SystemV weighted | x86 Win64 weighted | +|---|---:|---:|---:|---:| +| 23 | 413 -> 343 | 417 -> 345 | 95 -> 95 | 586 -> 496 | +| 24 | 643 -> 573 | 647 -> 575 | 95 -> 95 | 1,235 -> 1,138 | +| 25 | 348 -> 347 | 346 -> 343 | 123 -> 114 | 438 -> 440 | + +Changed goldens only after measuring the aggregate: in 23/24, NewtonInteger +Win64 55 -> 48, Sieve Win64 257 -> 186 / RISC-V 160 -> 92 / ARM 160 -> 94, +and arg_count Win64 42 -> 32. In 25, NewtonFloat SystemV 48 -> 40 and arg_count +Win64 31 -> 35. That local increase is accepted against the overall reduction. +All measured cases now complete their legality, quality, native/emulator checks: +53 tests in 23, 77 in 24, and 67 in 25. Logs, original classes, and disposable +measurement sources are under each chapter's `build/forward-regalloc`. +The separate FunPtrNode reachability backport remains deferred as requested. + ### Inlined return typing and ARM emulator: corrected, 2026-09-20 The ARM seed-9 String failure was an optimizer bug: inlining can delete a FunNode @@ -235,6 +358,83 @@ Fresh baselines passed before edits. Full suites after correction: 20: 376+1; are excluded from spill measurements. Logs/reducers are in each affected chapter's ignored `build/arm-top`; the earlier chapter-by-chapter allocator review gate remains. +### Chapter 22 allocator: ready for review, 2026-09-20 + +Carried forward the corrected Chapter 21 allocator and its diagnostic checks, +retaining native frame/call support (`CallEndMach` in 22). Five inherited +regressions fail against the original 22 classes: mask iteration/empty masks, +resultless register kills, fixed-register clone progress, commutative Phi fallback, +and copy bypass across clobbers. All eight diagnostic groups pass now. + +Chapter 22 keeps the stronger copy-chain and loop-backedge color bias, and cheap +cloneable/callee-save spill ordering. Cloneable candidates must have samples; +coalescing can leave either absent. The adjacent-use test now compares +`defIndex+1 < useIndex`, not `defIndex < useIndex+1`, and treats multiple uses +explicitly. Popular-use grouping is removed for introduction in 23; cold loop +split deferral and area/cost ranking remain for 24 and 25. + +The native test helper had lost its exit-status assertion. Restored checking of +its full integer exit code; `testNativeExitStatus` proves an empty-output program +returning 7 fails. `testNarrowStores` first failed against the old RISC-V mask, +then against the old x86 mask; both now reject FP registers for byte/short stores, +and signed/unsigned RISC-V byte/short writes execute with the expected bytes. +These restrictions already exist in 25; remaining destinations are queued above. + +Preserved cohorts 20 and 21 rather than silently accepting changed inputs: +`person21` holds the original 64-bit age example, and `testInfiniteReturn` belongs +to 22 while the old loop remains in 21. Cohort 22 includes its new allocation +programs and repeated encoding/emulator compilations; diagnostic tests stay out. + +| Cohort, all using Chapter 22 | Compilations | Original splits | Current splits | Original weighted | Current weighted | +|---|---:|---:|---:|---:|---:| +| Chapter 20 | 39 | 322 | 324 | 448 | 443 | +| Chapter 21 | 52 | 465 | 447 | 1,221 | 986 | +| Chapter 22 | 24 | 67 | 67 | 67 | 67 | +| **Total** | **115** | **854** | **838** | **1,736** | **1,496** | + +The original full suite passed 399 tests plus the fuzzer. Its frozen-cohort run +completed all 115 allocations and execution checks, with 15 differences from +Chapter 21's spill expectations. The final `make -j 4 tests` passes 416 tests plus +the fuzzer; `make spill-stats` passes 55 tests, 115 allocations, and all quality, +register-legality, function-ownership, native, and emulator checks. Sources and +expectations were force-recompiled before checking. The README ends with the +cohort table and explains the metrics; its FFI examples now match `sys.smp`. + +A controlled ablation substitutes only Chapter 21's IFG bias/ordering, keeping +all other code and the new narrow-store restrictions fixed. It completes all +115 allocations and runtime checks: 885 splits / 1,543 weighted, versus 838 / +1,496 with the new preferences, a 47 weighted move (3.0%) improvement. The scratch +ablation expects 42 instead of 41 bytes for the x86 narrow-store example because +its chosen registers need an extra REX byte; runtime and mask checks remain on. +Quality differences are reported with nonzero exit status, not suppressed. + +| Target/ABI, all cohorts | Compilations | Chapter 21 preferences, weighted | Chapter 22 preferences, weighted | +|---|---:|---:|---:| +| x86 SystemV | 22 | 267 | 268 | +| x86 Win64 | 15 | 414 | 415 | +| RISC-V SystemV | 39 | 437 | 407 | +| ARM SystemV | 39 | 425 | 406 | + +Against the controlled ablation, BrainFuck saves 14 on RISC-V and 6 on ARM in +both cohorts; ARM `testAlloc2` saves 4. Several MergeSort variants and RISC-V Sieve +increase by one. Against the original mixed snapshot, Sieve saves 72 weighted +moves on each target and Win64 argCount saves 10. This shows why individual spill +goldens are reviewed against the aggregate rather than requiring every case to +improve. Chapter totals also reflect lowering: the frozen String example has no +explicit return and folds away at seed 123 in 22. + +The supplementary 13-program, three-target, 30-seed encoding sweep completes +990 of 1,170 compilations with register checks. The remaining 180 fail on String +(before allocation) and FltArg (relocation); the original classes reproduce all +180 and additionally fail five allocator diagnostic groups per seed. No new +program failures were introduced by the allocator work. The two source-level +failures are queued above, not hidden by changing inputs, seeds, or expectations. +Cliff clarified after this run that optimizer seed variation is not productive +routine allocator coverage: normalized post-Opto graphs should produce similar +backend work. Retain these historical reproductions, but use fixed-seed backend +validation going forward; seed variation belongs to optimizer investigations. +Stop for Cliff's review before starting Chapter 23. + ### Chapter 21 allocator: ready for review, 2026-09-20 Carries the Chapter 20 legality/progress/support fixes into 21 while retaining @@ -279,7 +479,7 @@ summarizes encoding/ELF, links the retained encoding reference, and ends with coalescing, both cohort rows, and the controlled comparison. Logs and isolated baseline/ablation sources are under `chapter21/build/regalloc-review` (ignored). The allocator changes remain confined to Chapter 21; the subsequent return/emulator -correction is recorded separately above. Chapter 22 allocator work awaits review. +correction is recorded separately above. Chapter 22 allocator work is recorded below the review heading. ### Chapter 20 allocator: ready for review, 2026-09-20 diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 49823027..d0151805 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -131,6 +131,14 @@ lessons rather than duplicating that history. Local increases are acceptable when offset elsewhere; report per-target and overall totals. `_spills` counts surviving SplitNodes, and `_spillScaled` weights those moves by `8^loopDepth`; neither means only memory stores. +- Use a fixed optimizer seed for routine allocator/scheduler/encoder validation. + Seeds shuffle IterPeeps/Opto worklists; optimization is intended to normalize + to the same graph modulo node IDs and equivalent operand orderings. Repeating + the backend on essentially the same graph adds little coverage. Reserve seed + sweeps for investigating optimizer normalization, missing dependencies, or a + demonstrated order-sensitive failure; inspect post-Opto graph differences + before expanding backend runs. Prefer distinct programs, register constraints, + targets/ABIs, and actual execution for backend coverage. - Separate allocation completion/register legality/runtime results from quality expectations. Reaching the round limit is a correctness bug; raising the limit or changing spill goldens does not prove progress fixed. Heuristics @@ -147,12 +155,28 @@ lessons rather than duplicating that history. membership, seeds, or targets when comparing chapters. - Chapter 20's corrected baseline costs one extra weighted move (354->355 over 39 compilations); document this as a correctness cost. Advanced quality - heuristics remain staged. Chapter 21 is now implemented; stop for Cliff's - review before 22. Its shortened README links the retained encoding reference. + heuristics remain staged. Chapters 20-22 are now implemented; common correctness + fixes and diagnostic hooks have also been forwarded through 25 at Cliff's request. + Resume the quality/cohort/README review at 23. Chapter 21's shortened README links the retained encoding reference. - Chapter 21 changed several inherited inputs/ABIs. Its Chapter20Test now freezes all 13 original programs; Chapter21AllocTest retains the four revised cases, counted with the native variants as cohort 21. On Windows the cohorts are 39 and 52 compilations. Preserve source/target membership when moving forward. +- Chapter 22 adds stronger copy-chain/backedge bias and cheap-spill ordering; + popular-use grouping remains for 23. Preserve `person21` (64-bit age) separately + from 22's narrower person example, and keep its revised infinite-loop input in + cohort 22. The Windows cohort counts are 39, 52, and 24. +- Validate the instruction masks independently of the chosen register: a broad + mask can hide behind favorable color bias. Byte/short x86 and RISC-V stores + must exclude floating-point registers. Size fields such as `_sz` may hold a + printable character: compare to `'4'`, not integer `2`. Chapters 22-24 now carry + 25's store restrictions; x86 20-21 and RISC-V 21 remain queued. +- The historical Chapter 22 seed sweep exposed failures outside allocation; + it is not a template for routine allocator validation. + Chapter 22's frozen String source fails before allocation and its returned + function-pointer case fails during relocation at seeds 0-29, on all targets. + Both reproduce in the original snapshot; report these failures explicitly. + Do not replace the seed or add a return merely to make the sweep green. - Use an ablation in the same compiler to measure each staged heuristic. Native ABI/lowering changes make the Chapter 20 and 21 totals different even with the same sources. In 21, coalescing saves 127 weighted moves, but deferring later @@ -174,6 +198,15 @@ lessons rather than duplicating that history. before coloring, a fixed-register definition can clobber despite `_reg==-1`. Cloning is valid only if its output mask can satisfy the use. A fixed-register clone with flexible uses needs use-side splits, not a no-op def-side path. +- Check function ownership and register masks immediately after allocation, + before encoding rewrites tail calls or adds untyped branches. Call.regmap can + itself depend on CFG.fun/idom. The test-only CheckedCodeGen override keeps + these checks at the right phase without changing the driver; in 25 this also + preserves ideal-graph serialization/import unlinking before instruction selection. +- Shared correctness/support can be forwarded as one review batch, while leaving + each chapter's quality heuristics and historical cohort/README review staged. + Compare each destination's unchanged local suite before/after for such a batch; + do not present those unequal local suites as the chapter progression table. - The staged plan and historical fix inventory are in `docs/chapter-backports.md`; its review is not evidence of completed backports. @@ -306,8 +339,9 @@ Consequences: - One-step idealization must preserve the type knowledge already established. `IterPeeps.progressOnList` and `Opto.worklistCheck` are invariant checks, not assertions to weaken. -- Worklist order must not affect semantics. Rotate deterministic seeds to - expose missing dependencies; never fix a bug by merely favoring one order. +- Worklist order must not affect semantics or prevent optimizer normalization. + Use deterministic seed variation when investigating missing dependencies or + order-sensitive optimization; never fix a bug by merely favoring one order. ## Functions and escape analysis @@ -317,6 +351,16 @@ Consequences: whether an error exists. Earlier snapshots keep separate Return nodes; they already accept dead mixed-type exits and do not enforce one common return type. +- Chapters 22-23's post-Opto name-based function pruning is not escape analysis: + no linked calls does not mean no callers when a function address survives. + In 22, `return {->42;};` and `return sys.io.p;` lose their bodies but retain + pointer constants and stale ideal linker targets, then fail in relocation after + machine NIDs reset. Diagnose retention before resizing relocation tables. A + named-function workaround or keeping only anonymous functions is insufficient + for the library-pointer case. Cliff wants Chapter 25's FunPtrNode investigated + as the backport, including the Return edge and callable-function retention + rules, after register allocation work is complete. Keep the Chapter 22 examples + as documented known failures until then; do not add an interim address scan. - A constant Simple function address must be a `FunPtrNode`, not an ordinary `ConstantNode`, so the pointer retains an edge to the function Return. - Before Opto, a live FunPtr keeps its function callable even if no Call is |