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.

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;
 };