From 8d6de0e10358fc197490cdacb10cbcedc18bb4f6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 23 Mar 2025 15:59:23 -0700 Subject: Coalesacing Fix bug IFG adding interference to from 1 reg live range, even if success in clearing reg Fix bug LRG merging when both masks have already been trimmed. Missing ARM stack adjust --- .../com/seaofnodes/simple/codegen/Coalesce.java | 119 +++++++++++++++++++++ .../java/com/seaofnodes/simple/codegen/IFG.java | 30 ++---- .../java/com/seaofnodes/simple/codegen/LRG.java | 6 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 2 + .../seaofnodes/simple/node/cpus/arm/FunARM.java | 25 ++++- .../seaofnodes/simple/node/cpus/arm/RetARM.java | 14 ++- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 14 +++ .../seaofnodes/simple/node/cpus/riscv/FunRISC.java | 2 +- .../simple/node/cpus/x86_64_v2/JmpX86.java | 2 +- 9 files changed, 188 insertions(+), 26 deletions(-) create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java (limited to 'chapter21/src/main/java') diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java new file mode 100644 index 00000000..7496ac3b --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java @@ -0,0 +1,119 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Ary; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.*; +import java.util.BitSet; +import java.util.IdentityHashMap; + +// Coalesce copies +abstract public class Coalesce { + + public static boolean coalesce( int round, RegAlloc alloc ) { + // Convert the 2-D array of bits (a 1-D array of BitSets) into an + // adjacency matrix. + int maxlrg = alloc._LRGS.length; + for( int i=1; i=0; lrg=ifg.nextSetBit(lrg+1) ) { + LRG lrg1 = alloc._LRGS[lrg]; + lrg0.addNeighbor(lrg1); + lrg1.addNeighbor(lrg0); + } + } + } + + // Walk all the splits, looking for coalesce chances + boolean progress = false; + for( CFGNode bb : alloc._code._cfg ) { + outer: + for( int j=0; j (v2._adj==null ? 0 : v2._adj._len) ) + { v1 = v2; v2 = alloc.lrg(n); } + int v2len = v2._adj==null ? 0 : v2._adj._len; + // See that they do not conflict (coalescing would make a self-conflict) + if( v1._adj!=null && v2._adj!=null && v1._mask.overlap(v2._mask) ) { + // Walk the smaller neighbors, and add to the larger. + // Check for direct conflicts along the way. + for( LRG v3 : v1._adj ) { + if( v3==v2 ) { + // Direct conflict, skip this LRG pair + v2._adj.setLen(v2len); + continue outer; + } + // Add missing LRGs from V1 to V2 + if( v2._adj.find(v3)== -1 ) + v2._adj.push(v3); + } + } + // Most constrained mask + RegMask mask = v1._mask==v2._mask ? v1._mask : v1._mask.copy().and(v2._mask); + // Check for capacity + if( (v2._adj==null ? 0 : v2._adj._len) >= mask.size() ) { + // Fails capacity, will not be trivial colorable + v2._adj.setLen(v2len); + continue; + } + + // Union lrgs. + progress = true; + + // Since `n` is dying, remove from the LRGS BEFORE doing + // the union; this will let the union code keep the + // matching bits from the other side, preserving some + // info for biased coloring + if( ov1. _machDef==n ) ov1. _machDef = null; + if( ov1._splitDef==n ) ov1._splitDef = null; + if( ov2. _machUse==n ) ov2. _machUse = null; + if( ov2._splitUse==n ) ov2._splitUse = null; + // Keep larger adjacency list. + Ary larger = v2._adj; + v2._adj = null; + + // Union lrgs. Swaps again, based on small lrg + LRG vWin = v1.union(v2); + vWin._adj = larger; + LRG vLose = v1.leader() ? v2 : v1; + + // LRGs below v2len were always in v2, but maybe not in v1. + // LRGs above v2len are in v1 but were not in v2. + + // Walk v2's neighbors, replacing vLose with vWin. + if( larger != null ) + for( LRG vn : larger ) { + int idx = vn._adj.find(vLose); + if( idx != -1 ) + vn._adj.del(idx); + if( vn._adj.find(vWin) == -1 ) + vn._adj.add(vWin); + } + } else { + + // Since `n` is dying, remove from the LRGS + if( v1. _machDef==n ) v1. _machDef=null; + if( v1. _machUse==n ) v1. _machUse=null; + if( v1._splitDef==n ) v1._splitDef=null; + if( v1._splitUse==n ) v1._splitUse=null; + } + + // Remove junk split + n.removeSplit(); + j--; + } + } + + if( progress ) + alloc.unify(); + + return true; + } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java index df5976a4..e85bce5d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -19,7 +19,7 @@ abstract public class IFG { static final IdentityHashMap TMP = new IdentityHashMap<>(); // Inteference Graph: Array of Bitsets - private static final Ary IFG = new Ary<>(BitSet.class); + static final Ary IFG = new Ary<>(BitSet.class); static void resetIFG() { for( BitSet bs : IFG ) if( bs!=null ) bs.clear(); @@ -148,9 +148,10 @@ abstract public class IFG { // last tlrg register at some point, either tlrg or lrg // must fail. If *n* (a subset of lrg) needs the single // last tlrg register then only tlrg must fail. - if( ((MachNode)n).outregmap().size1() && !tlrg.clr(lrg._mask.firstReg()) ) - alloc.fail(tlrg); - else addIFG(lrg,tlrg); // Add interference + if( ((MachNode)n).outregmap().size1() ) { + if( !tlrg.clr(lrg._mask.firstReg()) ) // Clear bit, no interference + alloc.fail(tlrg); // Clearing drives mask to empty + } else addIFG(lrg,tlrg); // Add interference } } @@ -281,22 +282,10 @@ abstract public class IFG { // If there's no spare color we'll have to spill this at-risk live range. public static boolean color(int round, RegAlloc alloc) { - - // Convert the 2-D array of bits (a 1-D array of BitSets) into an - // adjacency matrix. int maxlrg = alloc._LRGS.length, nlrgs=0; - for( int i=1; i=0; lrg=ifg.nextSetBit(lrg+1) ) { - LRG lrg1 = alloc._LRGS[lrg]; - lrg0.addNeighbor(lrg1); - lrg1.addNeighbor(lrg0); - } - } - } + for( int i=1; i 0 ? "addi" : "ret"; + } // Correct Nodes outside the normal edges @Override public void postSelect(CodeGen code) { FunNode fun = (FunNode)rpc().in(0); @@ -16,9 +18,17 @@ public class RetARM extends ReturnNode implements MachNode { @Override public RegMask regmap(int i) { return arm.retMask(_fun.sig(),i); } @Override public RegMask outregmap() { return null; } // RET - @Override public void encoding( Encoding enc ) { enc.add4(arm.ret(0b1101011001011111000000)); } + @Override public void encoding( Encoding enc ) { + int frameAdjust = ((FunARM)fun())._frameAdjust; + if( frameAdjust > 0 ) + enc.add4(arm.imm_inst(0b1001000100, (frameAdjust*-8)&0xFFF, arm.RSP, arm.RSP)); + enc.add4(arm.ret(0b1101011001011111000000)); + } @Override public void asm(CodeGen code, SB sb) { + int frameAdjust = ((FunARM)fun())._frameAdjust; + if( frameAdjust>0 ) + sb.p("rsp += #").p(frameAdjust*-8).p("\nret"); // Post code-gen, just print the "ret" if( code._phase.ordinal() <= CodeGen.Phase.RegAlloc.ordinal() ) // Prints return reg (either X0 or D0), RPC (always R30) and diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 4c3b3fc7..9ac5a718 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -418,6 +418,20 @@ public class arm extends Machine { } throw Utils.TODO(); // Pass on stack slot } + // Return the max stack slot used by this signature, or 0 + static short maxSlot( TypeFunPtr tfp ) { + // Count floats in signature up to index + int fcnt=0; + for( int i=0; i= XMMS.length ) + throw Utils.TODO(); + RegMask[] cargs = CALLINMASK; + if( tfp.nargs()-fcnt >= cargs.length ) + throw Utils.TODO(); + return 0; // No stack args + } static final long CALLEE_SAVE = 1L<