From 05afabd5152b06295e16c65b5a249229a4ead996 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 9 May 2025 21:05:24 -0700 Subject: Bugs for BubbleSort Encoding picking up extra function padding if needing another round for X86 short jumps. GCM failed to late schedule around loop backedges. X86 Div was using AX/DX as *source* registers. X86 kills more flags. --- .../com/seaofnodes/simple/codegen/Encoding.java | 22 ++++-- .../simple/codegen/GlobalCodeMotion.java | 14 +++- .../com/seaofnodes/simple/codegen/RegAlloc.java | 2 +- .../simple/node/cpus/x86_64_v2/CmpX86.java | 6 ++ .../simple/node/cpus/x86_64_v2/DivX86.java | 2 +- .../simple/node/cpus/x86_64_v2/ImmX86.java | 1 + .../simple/node/cpus/x86_64_v2/RegX86.java | 1 + .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 2 + .../com/seaofnodes/simple/print/ASMPrinter.java | 4 -- .../java/com/seaofnodes/simple/BrainFuckTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 2 +- .../test/java/com/seaofnodes/simple/progs/jig.smp | 79 ++++++++++++++++++++-- 12 files changed, 114 insertions(+), 23 deletions(-) (limited to 'chapter22/src') diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index 7a43f099..db799b98 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -359,11 +359,6 @@ public class Encoding { slide = 0; for( int i=0; i 0 ) { // If no short-form ops, nothing to do here diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 7e0a58ac..04a119c2 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -177,14 +177,22 @@ public abstract class GlobalCodeMotion { } // Walk all inputs and put on worklist, as their last-use might now be done - for( Node def : n._inputs ) - if( def!=null && late[def._nid]==null ) { + for( Node def : n._inputs ) { + if( def!=null && late[def._nid]==null ) work.push(def); - // if the def has a load use, maybe the load can fire + // if the def has a load use, maybe the load can fire + if( def!=null ) for( Node out : def._outputs ) if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) work.push(ld); + } + + if( n instanceof LoopNode loop ) { + for( Node phi : loop._outputs ) { + if( phi instanceof PhiNode && late[phi._nid]==null ) + work.push(phi); } + } } } 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 68b55f6f..57d0d90c 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -559,7 +559,7 @@ public class RegAlloc { private void postColor() { int maxReg = -1; for( CFGNode bb : _code._cfg ) { // For all ops - if( bb instanceof FunNode fun ) + if( bb instanceof FunNode ) maxReg = -1; // Reset for new function // Compute frame size, based on arguments and largest reg seen if( bb instanceof ReturnNode ret ) diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java index 06a36d99..3e4200c0 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpX86.java @@ -9,6 +9,12 @@ public class CmpX86 extends MachConcreteNode implements MachNode { @Override public String op() { return "cmp"; } @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; } + // This one is marginal: cloning a Cmp[reg,reg] means stretching the + // lifetimes of 2 normal registers in exchange for shortening a flags + // register lifetime. Spilling flags is (probably) relatively expensive + // compared to some normal registers - and those normal registers might not + // be spilling! + @Override public boolean isClone() { return true; } @Override public void encoding( Encoding enc ) { short dst = enc.reg(in(1)); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java index 87b8b0c3..06f001b0 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/DivX86.java @@ -8,7 +8,7 @@ public class DivX86 extends MachConcreteNode implements MachNode { DivX86( Node div ) { super(div); } @Override public String op() { return "div"; } @Override public RegMask regmap(int i) { - return (i==1) ? x86_64_v2.RAX_MASK : x86_64_v2.RMASK; + return (i==1) ? x86_64_v2.RAX_MASK : x86_64_v2.DIV_MASK; } @Override public RegMask outregmap() { return x86_64_v2.RAX_MASK; } @Override public RegMask killmap() { return x86_64_v2.RDX_MASK; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java index 760d6805..9e602b47 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/ImmX86.java @@ -15,6 +15,7 @@ public abstract class ImmX86 extends MachConcreteNode implements MachNode { @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } @Override public RegMask outregmap() { return x86_64_v2.WMASK; } @Override public int twoAddress() { return 1; } + @Override public RegMask killmap() { return x86_64_v2.FLAGS_MASK; } abstract int opcode(); abstract int mod(); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java index 0997644d..a4a6a814 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/RegX86.java @@ -8,6 +8,7 @@ public abstract class RegX86 extends MachConcreteNode { RegX86( Node add ) { super(add); } @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } @Override public RegMask outregmap() { return x86_64_v2.WMASK; } + @Override public RegMask killmap() { return x86_64_v2.FLAGS_MASK; } @Override public int twoAddress() { return 1; } abstract int opcode(); @Override public void encoding( Encoding enc ) { diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 60e10d79..94c1511a 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -43,6 +43,8 @@ public class x86_64_v2 extends Machine { static RegMask XMASK = new RegMask(FP_BITS); static RegMask FLAGS_MASK = new RegMask(FLAGS); static RegMask RPC_MASK = new RegMask(RPC); + // Divide mask: exclude RDX:RAX + static RegMask DIV_MASK = new RegMask(RD_BITS & ~(1L< iadr ) - iadr++; - // constant pool iadr = (iadr+15)&-16; // pad to 16 Encoding enc = code._encoding; diff --git a/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 2733620e..1e1a1dc3 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -16,7 +16,7 @@ public class BrainFuckTest { String brain_fuck = "Hello World!\n"; TestC.run("brain_fuck", brain_fuck, 40); - EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 44, false); + EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 28, false); int trap = R5.step(100000); assertEquals(0,trap); int ptr = (int)R5.regs[riscv.A0]; diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 55ab97ca..304fb1cf 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -16,7 +16,7 @@ public class Chapter22Test { @Test @Ignore public void testJig() throws IOException { //String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); - String src = Files.readString(Path.of("doc/examples/BubbleSort.smp")); + String src = Files.readString(Path.of("docs/examples/BubbleSort.smp")); testCPU(src,"x86_64_v2", "Win64" ,-1,null); testCPU(src,"riscv" , "SystemV",-1,null); testCPU(src,"arm" , "SystemV",-1,null); diff --git a/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp b/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp index 0f28dfce..70f45717 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp +++ b/chapter22/src/test/java/com/seaofnodes/simple/progs/jig.smp @@ -1,23 +1,88 @@ // -*- mode: java; -*- + val _exit = { u8[~] msg -> sys.io.p(msg); sys.libc._exit(1); }; +val usage = { -> _exit("stdin must look like [4, 3, 2, 1]"); }; +// Scanner struct Scan { int !x; u8[~] buf; }; +// Skip whitespace +val skip = { Scan s -> + while( s.buf[s.x] <= 32 ) + s.x++; +}; + +// Require specific syntax or usage +val require = { Scan s, u8 c -> + skip(s); + if( s.buf[s.x++] != c ) + usage(); +}; + +val peek = { Scan s, u8 c -> + skip(s); + if( s.buf[s.x] != c ) return false; + s.x++; + return true; +}; + +val number = { Scan s -> + skip(s); + i32 n = 0; + while( '0' <= s.buf[s.x] & s.buf[s.x] <= '9' ) + n = n*10 + (s.buf[s.x++] - '0'); + return n; +}; + // Read from stdin a line of the form "[ 4, 3, 2, 1]" and print it sorted. val main = { -> Scan !s = new Scan{ buf = sys.io.stdin(); }; - var junk = new u8[1]; - while( s.x < s.buf# ) { - sys.io.p("scan "); - junk[0] = s.buf[s.x++]; - sys.io.p(junk); - }; - return 0; + require(s,'['); + // Array of parsed results + int[] !ns = new int[16]; + i32 num = 0; + // Parse a list of numbers + if( !peek(s,']') ) { // Handle the empty list + // Parse "123, " until a something else + while( s.x < s.buf# ) { + int n = number(s); + i32 q=n; + ns[num++] = n; + if( !peek(s,',') ) + break; + }; + require(s,']'); // Close the list + } + + // Print a list of numbers + sys.io.p("[ "); + u8[] !buf = new u8[20]; + for( int i=0; i0 ) + { q/=10; log++; } + i32 raw=log; + sys.libc._exit(raw); + // for( int j=0, a=x; j