From 7e1deb4cbd52c7ebbec78e2ceeb35875e83c6e3a Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 29 Apr 2025 13:27:32 -0700 Subject: Minor bugs When passing AND receiving arguments on the stack (win64 passes only 4 args in registers, and requires backing stack store), the RA math was off. Bug triggered need for a stack-stack spill, now done. Inlining also hides the bug, since there are no large-argument calls afterwards. x86 store-immediate encoded an 8byte imm but the op only takes a 4byte imm. Making a 1-reg regmask with reg>64 math wrong. "popular constant" RA split would trigger when spanning calls; visit pattern for multi-users would then skip a user. Encoding would pad fun headers to 16bytes, then expand x86 short jumps to long jumps, messing up the padding. Call/End/Node visiting in RA would double-visit trailing projections. GCM not treating Calls as memory kills. --- .../com/seaofnodes/simple/codegen/BuildLRG.java | 2 +- .../com/seaofnodes/simple/codegen/Encoding.java | 2 -- .../simple/codegen/GlobalCodeMotion.java | 8 +++++--- .../java/com/seaofnodes/simple/codegen/IFG.java | 8 +++----- .../com/seaofnodes/simple/codegen/Machine.java | 8 ++++++-- .../com/seaofnodes/simple/codegen/RegAlloc.java | 23 ++++++++++++++-------- .../com/seaofnodes/simple/codegen/RegMask.java | 6 +++--- .../java/com/seaofnodes/simple/node/NewNode.java | 4 ++-- .../java/com/seaofnodes/simple/node/StoreNode.java | 8 +++++++- .../seaofnodes/simple/node/cpus/arm/CallARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/CallRRARM.java | 2 +- .../seaofnodes/simple/node/cpus/arm/ParmARM.java | 2 +- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 4 ++-- .../simple/node/cpus/riscv/CallRISC.java | 10 ++++------ .../simple/node/cpus/riscv/CallRRISC.java | 2 +- .../simple/node/cpus/riscv/ParmRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/riscv.java | 5 +++-- .../simple/node/cpus/x86_64_v2/CallRX86.java | 2 +- .../simple/node/cpus/x86_64_v2/CallX86.java | 2 +- .../simple/node/cpus/x86_64_v2/ParmX86.java | 2 +- .../simple/node/cpus/x86_64_v2/SplitX86.java | 11 +++++++++-- .../simple/node/cpus/x86_64_v2/StoreX86.java | 2 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 18 ++++++++--------- 23 files changed, 78 insertions(+), 57 deletions(-) (limited to 'chapter21/src/main/java/com') diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index a2bb21ed..e9b5eb2e 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -63,7 +63,7 @@ abstract public class BuildLRG { } // MultiNodes have projections which set registers - if( n instanceof MultiNode ) + if( n instanceof MultiNode && !(n instanceof CFGNode) ) for( Node proj : n.outs() ) if( proj instanceof MachNode ) defLRG(alloc,proj); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index d7057839..c35ea6a4 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -324,7 +324,6 @@ public class Encoding { if( !(bb instanceof MachNode mach0) ) _opStart[bb._nid] = _bits.size(); else if( bb instanceof FunNode fun ) { - padN(16,_bits); _fun = fun; // Currently encoding function _opStart[bb._nid] = _bits.size(); mach0.encoding( this ); @@ -338,7 +337,6 @@ public class Encoding { } } } - padN(16,_bits); } // -------------------------------------------------- diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 289d1786..40f827ec 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -167,6 +167,8 @@ public abstract class GlobalCodeMotion { !(memuse instanceof NewNode) && // Load-use directly defines memory (memuse._type instanceof TypeMem || + // Load-use directly defines memory + memuse instanceof CallNode || // Load-use indirectly defines memory (memuse._type instanceof TypeTuple tt && tt._types[ld._alias] instanceof TypeMem)) ) continue outer; @@ -277,9 +279,9 @@ public abstract class GlobalCodeMotion { lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); } break; // Loads do not cause anti-deps on other loads - case CallNode st: - assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); + case CallNode call: + assert late[call._nid]!=null; + lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call); break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. 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 81955779..fdd4e2f9 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -242,14 +242,12 @@ abstract public class IFG { private static void mergeLiveOut( RegAlloc alloc, CFGNode priorbb, int i ) { CFGNode bb = priorbb.cfg(i); if( bb == null ) return; // Start has no prior - if( !bb.blockHead() ) bb = bb.cfg0(); - //if( i==0 && !(bb instanceof StartNode) ) bb = bb.cfg0(); - assert bb.blockHead(); + while( !bb.blockHead() ) bb = bb.cfg0(); // Lazy get live-out set for bb - IdentityHashMap lrgs = BBOUTS.computeIfAbsent( bb, k -> new IdentityHashMap<>() ); + IdentityHashMap lrgs = BBOUTS.computeIfAbsent( bb, k -> new IdentityHashMap<>() ); - for( LRG lrg : TMP.keySet() ) { + for( LRG lrg : TMP.keySet() ) { Node def = TMP.get(lrg); // Effective def comes from phi input from prior block if( def instanceof PhiNode phi && phi.cfg0()==priorbb ) { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java index 1c12bfcb..2766414f 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Machine.java @@ -16,8 +16,12 @@ abstract public class Machine { public abstract long callerSave(); // List of never-save registers, e.g. RSP or a ZERO register if you have one public abstract long neverSave(); - // Call Argument Mask - public abstract RegMask callArgMask(TypeFunPtr tfp, int arg); + // Call Argument Mask. Passed in the function signature and argument + // number (2-based; 0 is for control and 1 for memory). Also passed in a 0 + // for the function itself, or for *outgoing* calls, the maximum stack slot + // given to the incoming function arguments (stack slots reserved for + // incoming arguments). + public abstract RegMask callArgMask(TypeFunPtr tfp, int arg, int maxArgSlot); // Return register mask, based on signature (GPR vs FPR) public abstract RegMask retMask(TypeFunPtr tfp); // Return PC register diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 49f057a3..3a99c097 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -262,7 +262,7 @@ public class RegAlloc { } // Single-def live range with an empty mask. There are many single-reg - // uses. Theory is there's many repeats if the same reg amongst the uses. + // 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 ) { @@ -271,26 +271,32 @@ public class RegAlloc { // Look at each use, and break into non-overlapping register classes. Ary 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( use instanceof MachNode mach ) { + if( mach instanceof CallNode ) ncalls++; for( int i=1; i 1 ) return false; - // Split by class + // Split by classh + Ary ns = new Ary<>(Node.class); for( RegMask rmask : rclass ) { + ns.addAll(def._outputs); Node split = makeSplit(def,"popular",round,lrg); 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); + for( Node use : ns ) { 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++ ) @@ -299,10 +305,11 @@ public class RegAlloc { 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; } + use.setDefOrdered( i, split ); } } } + ns.clear(); } return true; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index 79de3fbf..ec0c4e30 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -4,11 +4,11 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.SB; /** RegMask - * A "register mask" - 1 bit set for each allowed register. In addition + * A "register mask" - 1 bit set for each allowed register. In addition, * "stack slot" registers may be allowed, effectively making the set infinite. *

* For smaller and simpler machines it suffices to make such masks an i64 or - * i128 (64 or 128 bit integers), and this presentation is by far the better + * i128 (64- or 128-bit integers), and this presentation is by far the better * way to go... if all register allocations can fit in this bit limitation. * The allocator will need bits for stack-based parameters and for splits * which cannot get a register. For a 32-register machine like the X86, add 1 @@ -28,7 +28,7 @@ public class RegMask { public RegMask(int bit) { if( bit < 64 ) _bits0 = 1L<0 ) throw Utils.TODO(); return new RegMask(MAX_REG + 1 + (idx - 2)); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java index b9d4fa8d..1a74f817 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallRX86.java @@ -12,7 +12,7 @@ public class CallRX86 extends CallNode implements MachNode { @Override public RegMask regmap(int i) { return i==_inputs._len ? x86_64_v2.WMASK // Function call target - : x86_64_v2.callInMask(tfp(),i); // Normal argument + : x86_64_v2.callInMask(tfp(),i,fun()._maxArgSlot); // Normal argument } @Override public RegMask outregmap() { return null; } @Override public void encoding( Encoding enc ) { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java index f6e67fb4..c97037e2 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CallX86.java @@ -20,7 +20,7 @@ public class CallX86 extends CallNode implements MachNode, RIPRelSize { @Override public String label() { return op(); } @Override public String name() { return _name; } @Override public TypeFunPtr tfp() { return _tfp; } - @Override public RegMask regmap(int i) { return x86_64_v2.callInMask(_tfp,i); } + @Override public RegMask regmap(int i) { return x86_64_v2.callInMask(_tfp,i,fun()._maxArgSlot); } @Override public RegMask outregmap() { return null; } @Override public int nargs() { return nIns()-2; } // Minus control, memory, fptr diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java index 7a6dbb13..5cfdd804 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ParmX86.java @@ -9,7 +9,7 @@ public class ParmX86 extends ParmNode implements MachNode { final RegMask _rmask; ParmX86( ParmNode parm ) { super(parm); - _rmask = x86_64_v2.callInMask(fun().sig(),_idx); + _rmask = x86_64_v2.callInMask(fun().sig(),_idx,1/*RPC*/); } @Override public RegMask regmap(int i) { return null; } @Override public RegMask outregmap() { return _rmask; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java index f965157b..960ea6f8 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SplitX86.java @@ -49,9 +49,16 @@ public class SplitX86 extends SplitNode { // Stack spills if( dst >= x86_64_v2.MAX_REG ) { - if( src >= x86_64_v2.MAX_REG ) - throw Utils.TODO(); // Very rare stack-stack move int off = enc._fun.computeStackOffset(enc._code,dst); + if( src >= x86_64_v2.MAX_REG ) { + // Rare stack-stack move. push [RSP+soff]; pop [RSP+doff] + int soff = enc._fun.computeStackOffset(enc._code,src); + enc.add1(0xFF); + x86_64_v2.indirectAdr(0, (short)-1/*index*/, (short)x86_64_v2.RSP, soff, 6, enc); + enc.add1(0x8F); + x86_64_v2.indirectAdr(0, (short)-1/*index*/, (short)x86_64_v2.RSP, off, 0, enc); + return; + } StoreX86.encVal(enc, srcX ? TypeFloat.F64 : TypeInteger.BOT, (short)x86_64_v2.RSP, (short)-1/*index*/, src, off, 0); return; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java index c906c3f2..76fb4e8d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java @@ -44,7 +44,7 @@ public class StoreX86 extends MemOpX86 { case 0: enc.add1(_imm); break; case 1: enc.add2(_imm); break; case 2: enc.add4(_imm); break; - case 3: enc.add8(_imm); break; + case 3: enc.add4(_imm); break; // Limit of a 4 byte immediate } } else { encVal(enc,_declaredType,ptr,idx,src,_off,_scale); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 23c12ae7..2b7fddb1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -185,13 +185,13 @@ public class x86_64_v2 extends Machine { // Map from function signature and argument index to register. // Used to set input registers to CallNodes, and ParmNode outputs. - @Override public RegMask callArgMask( TypeFunPtr tfp, int idx ) { return callInMask(tfp,idx); } - static RegMask callInMask( TypeFunPtr tfp, int idx ) { + @Override public RegMask callArgMask( TypeFunPtr tfp, int idx, int maxArgSlot ) { return callInMask(tfp,idx,maxArgSlot); } + static RegMask callInMask( TypeFunPtr tfp, int idx, int maxArgSlot ) { if( idx==0 ) return RPC_MASK; if( idx==1 ) return null; return switch( CodeGen.CODE._callingConv ) { - case "SystemV" -> callSys5 (tfp,idx); - case "Win64" -> callWin64(tfp,idx); + case "SystemV" -> callSys5 (tfp,idx,maxArgSlot); + case "Win64" -> callWin64(tfp,idx,maxArgSlot); default -> throw Utils.TODO(); }; } @@ -230,11 +230,11 @@ public class x86_64_v2 extends Machine { R09_MASK, }; - static RegMask callWin64(TypeFunPtr tfp, int idx ) { + static RegMask callWin64(TypeFunPtr tfp, int idx, int maxArgSlot ) { // idx 2,3,4,5 passed in registers, with stack slot mirrors. // idx >= 6 passed on stack, starting at slot#1 (#0 reserved for RPC). if( idx >= 6 ) - return new RegMask(MAX_REG+1/*RPC*/+(idx-2)); + return new RegMask(MAX_REG+maxArgSlot+(idx-2)); return tfp.arg(idx-2) instanceof TypeFloat ? XMMS8 [idx-2] : WIN64_CALL[idx-2]; @@ -271,7 +271,7 @@ public class x86_64_v2 extends Machine { R09_MASK, }; - static RegMask callSys5(TypeFunPtr tfp, int idx ) { + static RegMask callSys5(TypeFunPtr tfp, int idx, int maxArgSlot ) { // First 6 integers passed in registers: rdi,rsi,rdx,rcx,r08,r09 // First 8 floats passed in registers: xmm0-xmm7 int icnt=0, fcnt=0; // Count of ints, floats @@ -281,8 +281,8 @@ public class x86_64_v2 extends Machine { } int nstk = Math.max(icnt-6,0)+Math.max(fcnt-8,0); return tfp.arg(idx-2) instanceof TypeFloat - ? fcnt<8 ? XMMS8 [fcnt] : new RegMask(MAX_REG+1/*RPC*/+nstk) - : icnt<6 ? SYS5_CALL[icnt] : new RegMask(MAX_REG+1/*RPC*/+nstk); + ? fcnt<8 ? XMMS8 [fcnt] : new RegMask(MAX_REG+maxArgSlot+nstk) + : icnt<6 ? SYS5_CALL[icnt] : new RegMask(MAX_REG+maxArgSlot+nstk); } static short maxArgSlotSys5(TypeFunPtr tfp) { int icnt=0, fcnt=0; // Count of ints, floats -- cgit v1.2.3