diff options
13 files changed, 128 insertions, 39 deletions
diff --git a/chapter22/docs/examples/BubbleSort.smp b/chapter22/docs/examples/BubbleSort.smp index 70f45717..f6b30752 100644 --- a/chapter22/docs/examples/BubbleSort.smp +++ b/chapter22/docs/examples/BubbleSort.smp @@ -14,7 +14,7 @@ struct Scan { // Skip whitespace val skip = { Scan s -> - while( s.buf[s.x] <= 32 ) + while( s.buf[s.x] <= ' ' ) s.x++; }; @@ -53,7 +53,6 @@ val main = { -> // 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; @@ -63,24 +62,23 @@ val main = { -> // Print a list of numbers sys.io.p("[ "); - u8[] !buf = new u8[20]; + u8[] !junk = new u8[1]; for( int i=0; i<num; i++ ) { int x = ns[i]; if( !x ) { sys.io.p("0, "); continue; } - u32 log=0, q=x; - while( q>0 ) - { q/=10; log++; } - i32 raw=log; - sys.libc._exit(raw); - // for( int j=0, a=x; j<log; j++ ) { - // q = x/10; - // buf[log-j] = '0'+(x-q*10); - // x = q; - // } - // int raw = buf; - // sys.libc.write(1,raw,log); - // sys.io.p(", "); + int ten = 1, log = 0; + while( ten <= x ) { ten *= 10; log++; } + ten /= 10; + for( int i=0; i<log; i++ ) { + int q = x/ten; + int r = x - q*ten; + junk[0] = q+'0'; + sys.io.p(junk); + x = r; + ten /= 10; + } + sys.io.p(", "); } sys.io.p("]"); 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<len; i++ ) { CFGNode bb = _code._cfg.at(i); - // Functions pad to align 16 - if( bb instanceof FunNode ) { - int newStart = _opStart[bb._nid]+slide; - slide += (newStart+15 & -16)-newStart; - } _opStart[bb._nid] += slide; // Slide down all other (non-CFG) ops in the block for( Node n : bb._outputs ) @@ -387,6 +382,23 @@ public class Encoding { } + // Go again, inserting padding on function headers. Since no + // short-jumps span function headers, the padding will not make any + // short jumps fail. + for( int i=0; i<len; i++ ) { + CFGNode bb = _code._cfg.at(i); + // Functions pad to align 16 + if( bb instanceof FunNode ) { + int newStart = _opStart[bb._nid]+slide; + slide += (newStart+15 & -16)-newStart; + } + _opStart[bb._nid] += slide; + for( Node n : bb._outputs ) + if( n instanceof MachNode && !(n instanceof CFGNode) ) + _opStart[n._nid] += slide; + } + + // Copy/slide the bits to make space for all the longer branches int grow = _opStart[_code._cfg.at(len-1)._nid] - oldStarts[len-1]; if( grow > 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<<RAX) & ~(1L<<RDX)); static final long SPILLS = -(1L << MAX_REG); static final RegMask SPLIT_MASK = new RegMask(WR_BITS | FP_BITS /* | (1L<<FLAGS)*/ | SPILLS, -1L ); diff --git a/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 45f71e40..366ae376 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -22,10 +22,6 @@ public abstract class ASMPrinter { if( code._cfg.at(i) instanceof FunNode fun ) iadr = print(iadr,sb,code,fun,i); - // Skip padding - while( ((iadr+7) & -8) > 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; i<num; i++ ) { + int x = ns[i]; + if( !x ) { sys.io.p("0, "); continue; } + + u32 log=0, q=x; + while( q>0 ) + { q/=10; log++; } + i32 raw=log; + sys.libc._exit(raw); + // for( int j=0, a=x; j<log; j++ ) { + // q = x/10; + // buf[log-j] = '0'+(x-q*10); + // x = q; + // } + // int raw = buf; + // sys.libc.write(1,raw,log); + // sys.io.p(", "); + } + sys.io.p("]"); + + return num; }; |