First cut BB layout

12 files changed, 111 insertions, 34 deletions

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 d7a19e2a..86cf9daa 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -1,8 +1,10 @@
 package com.seaofnodes.simple.codegen;
 
 import com.seaofnodes.simple.Utils;
+import com.seaofnodes.simple.Ary;
 import com.seaofnodes.simple.node.*;
 import java.io.ByteArrayOutputStream;
+import java.util.BitSet;
 
 
 /**
@@ -46,15 +48,66 @@ public class Encoding {
         // that minimizes actual branches, takes advantage of fall-through
         // edges, and tries to help simple branch predictions: back branches
         // are predicted taken, forward not-taken.
+        Ary<CFGNode> rpo = new Ary<>(CFGNode.class);
+        BitSet visit = _code.visit();
+        for( Node n : _code._start._outputs )
+            if( n instanceof FunNode fun )
+                _rpo_cfg(fun, visit, rpo);
+        rpo.add(_code._start);
+        // Reverse in-place
+        for( int i=0; i< rpo.size()>>1; i++ )
+            rpo.swap(i,rpo.size()-1-i);
+        visit.clear();
+        _code._cfg = rpo;       // Save the new ordering
+
+        // Write encoding bits in order
+        //for( CFGNode bb : _code._cfg )
+        //    for( Node n : bb._outputs )
+        //        if( n instanceof MachNode mach )
+        //            throw Utils.TODO();
+    }
 
-
-
-
-        // Write bits in order
-        for( CFGNode bb : _code._cfg )
-            for( Node n : bb._outputs )
-                if( n instanceof MachNode mach )
-                    throw Utils.TODO();
+    // Post-Order of CFG
+    private static void _rpo_cfg(CFGNode bb, BitSet visit, Ary<CFGNode> rpo) {
+        if( visit.get(bb._nid) ) return;
+        visit.set(bb._nid);
+        if( bb.nOuts()==0 ) return; // StopNode
+        if( !(bb instanceof IfNode iff) ) {
+            CFGNode next = bb instanceof ReturnNode ? (CFGNode)bb.out(bb.nOuts()-1) : bb.uctrl();
+            _rpo_cfg(next,visit,rpo);
+        } else {
+            // Pick out the T/F projections
+            CProjNode t = (CProjNode)bb.out(bb.nOuts()-1);
+            CProjNode f = (CProjNode)bb.out(bb.nOuts()-2);
+            if( t._idx==1 ) { CProjNode tmp=f; f=t; t=tmp; }
+            int tld = t.loopDepth(), fld = f.loopDepth(), bld = bb.loopDepth();
+            // Decide entering or exiting a loop
+            if( tld==bld ) {
+                // if T is empty, keep
+                if( t.nOuts()>1 &&
+                    // Else swap so T is forward and exits, while F falls into next loop block
+                    ((fld<bld && t.out(0)!=t.loop()) ||
+                     // Jump to an empty block and fall into a busy block
+                     (fld==bld && f.nOuts()==1)) ) {
+                    // Invert test and Proj fields
+                    iff.invert();
+                    t.invert();
+                    f.invert();
+                    CProjNode tmp=f; f=t; t=tmp; // Swap t/f
+                } // Else nothing
+            } else if( tld > bld ) { // True enters a deeper loop
+                throw Utils.TODO();
+            } // Else True exits a loop, always forward and good
+
+            // Always visit the False side last (so True side first), so that
+            // when the False RPO visit returns, the IF is immediately next.
+            // When the RPO is reversed, the fall-through path will always be
+            // following the IF.
+            _rpo_cfg(t,visit,rpo);
+            _rpo_cfg(f,visit,rpo);
+        }
+        rpo.add(bb);
     }
 
+
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index c5cd95f0..86d4a52b 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -100,7 +100,7 @@ public abstract class CFGNode extends Node {
     public int loopDepth() { return _ltree==null ? 0 : _ltree.depth(); }
 
     LoopTree _ltree;
-    int _pre;                   // Pre-order numbers for loop tree finding
+    public int _pre;            // Pre-order numbers for loop tree finding
     private static class LoopTree {
         LoopTree _par;
         final LoopNode _head;
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java
index adc4e66f..f0a8e78a 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java
@@ -10,10 +10,10 @@ import java.util.BitSet;
 public class CProjNode extends CFGNode {
 
     // Which slice of the incoming multipart value
-    public final int _idx;
+    public int _idx;
 
     // Debugging label
-    public final String _label;
+    public String _label;
 
     public CProjNode(Node ctrl, int idx, String label) {
         super(ctrl);
@@ -53,6 +53,12 @@ public class CProjNode extends CFGNode {
         return ((MultiNode)ctrl()).pcopy(_idx);
     }
 
+    // Only called during basic-block layout, inverts a T/F CProj
+    public void invert() {
+        _label = _idx == 0 ? "False" : "True";
+        _idx = 1-_idx;
+    }
+
     @Override
     boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java
index e04522b0..c65e9a3b 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.IterPeeps;
 import com.seaofnodes.simple.type.*;
@@ -64,4 +65,19 @@ public class IfNode extends CFGNode implements MultiNode {
         return null;
     }
 
+    // MachNode variants need to support this and invert the conditional test.
+    // The following CProjs will be inverted by the caller.
+    public void invert() { throw Utils.TODO(); }
+
+    public static String invert( String bop ) {
+        return switch( bop ) {
+        case "<"  -> ">=";
+        case "<=" -> ">" ;
+        case "==" -> "!=";
+        case "!=" -> "==";
+        case ">"  -> "<=";
+        case ">=" -> "<" ;
+        default -> throw Utils.TODO();
+        };
+    }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java
index 7655df40..d4a384d1 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/AndARM.java
@@ -11,16 +11,11 @@ import com.seaofnodes.simple.node.Node;
 import java.io.ByteArrayOutputStream;
 
 public class AndARM extends MachConcreteNode implements MachNode {
-    AndARM(Node and) {
-        super(and);
-    }
+    AndARM(Node and) { super(and); }
 
     // Register mask allowed on input i.
     // This is the normal calling convention
-    @Override public RegMask regmap(int i) {
-        assert i==1 || i==2;
-        return arm.RMASK;
-    }
+    @Override public RegMask regmap(int i) { return arm.RMASK; }
 
     // Register mask allowed as a result.  0 for no register.
     @Override public RegMask outregmap() { return arm.RMASK; }
@@ -35,4 +30,5 @@ public class AndARM extends MachConcreteNode implements MachNode {
     @Override public void asm(CodeGen code, SB sb){
         sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" & ").p(code.reg(in(2)));
     }
+    @Override public String op() { return "and"; }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/BranchARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/BranchARM.java
index 1a5108cf..66a6a9ae 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/BranchARM.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/BranchARM.java
@@ -4,13 +4,11 @@ import com.seaofnodes.simple.*;
 import com.seaofnodes.simple.codegen.CodeGen;
 import com.seaofnodes.simple.codegen.RegMask;
 import com.seaofnodes.simple.node.*;
-
 import java.io.ByteArrayOutputStream;
 
-
 // Jump on flags, uses flags
 public class BranchARM extends IfNode implements MachNode{
-    final String _bop;
+    String _bop;
     BranchARM(IfNode iff, String bop ) {
         super(iff);
         _bop = bop;
@@ -45,4 +43,5 @@ public class BranchARM extends IfNode implements MachNode{
     @Override public String comment() {
         return "L"+cproj(1)._nid+", L"+cproj(0)._nid;
     }
+    @Override public void invert() { _bop = invert(_bop); }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndRISC.java
index ca00bc98..4defc1b0 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndRISC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/AndRISC.java
@@ -10,10 +10,8 @@ import java.io.ByteArrayOutputStream;
 import java.util.BitSet;
 import java.lang.StringBuilder;
 
-public class AndRISC extends MachConcreteNode implements MachNode{
-    AndRISC(Node and) {
-        super(and);
-    }
+public class AndRISC extends MachConcreteNode implements MachNode {
+    AndRISC(Node and) { super(and); }
 
     // Register mask allowed on input i.
     // This is the normal calling convention
@@ -35,4 +33,5 @@ public class AndRISC extends MachConcreteNode implements MachNode{
     @Override public void asm(CodeGen code, SB sb) {
         sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" & ").p(code.reg(in(2)));
     }
+    @Override public String op() { return "and"; }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BranchRISC.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BranchRISC.java
index 6a1cf7dc..f6168d8e 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BranchRISC.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BranchRISC.java
@@ -9,7 +9,7 @@ import java.util.BitSet;
 
 // Conditional branch such as: BEQ
 public class BranchRISC extends IfNode implements MachNode {
-    final String _bop;
+    String _bop;
     // label is obtained implicitly
     BranchRISC( IfNode iff, String bop, Node n1, Node n2 ) {
         super(iff);
@@ -44,4 +44,6 @@ public class BranchRISC extends IfNode implements MachNode {
     @Override public String comment() {
         return "L"+cproj(1)._nid+", L"+cproj(0)._nid;
     }
+
+    @Override public void invert() { _bop = invert(_bop); }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java
index d7fb3613..24a88846 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/AndX86.java
@@ -6,10 +6,8 @@ import com.seaofnodes.simple.codegen.RegMask;
 import com.seaofnodes.simple.node.*;
 import java.io.ByteArrayOutputStream;
 
-public class AndX86  extends MachConcreteNode implements MachNode{
-    AndX86(Node and) {
-        super(and);
-    }
+public class AndX86  extends MachConcreteNode implements MachNode {
+    AndX86(Node and) { super(and); }
     // Register mask allowed on input i.
     // This is the normal calling convention
     @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.WMASK; }
@@ -29,6 +27,5 @@ public class AndX86  extends MachConcreteNode implements MachNode{
     @Override public void asm(CodeGen code, SB sb) {
         sb.p(code.reg(this)).p(" = ").p(code.reg(in(1))).p(" & ").p(code.reg(in(2)));;
     }
-
     @Override public String op() { return "and"; }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java
index 173f9ee7..0f6c8fa7 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java
@@ -10,7 +10,7 @@ import java.io.ByteArrayOutputStream;
 
 // Jump on flags, uses flags
 public class JmpX86 extends IfNode implements MachNode {
-    final String _bop;
+    String _bop;
     JmpX86( IfNode iff, String bop ) {
         super(iff);
         _bop = bop;
@@ -45,4 +45,6 @@ public class JmpX86 extends IfNode implements MachNode {
     @Override public String comment() {
         return "L"+cproj(1)._nid+", L"+cproj(0)._nid;
     }
+
+    @Override public void invert() { _bop = invert(_bop); }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
index 72da53bf..a7a0bce0 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
@@ -99,7 +99,13 @@ public abstract class ASMPrinter {
         // to this block.  Until the post-reg-alloc block layout cleanup, we
         // need to assume a jump.  There's no real hardware op here, yet.
         if( n instanceof RegionNode cfg && !(n instanceof FunNode) ) {
-            if( code._cfg.at(cfgidx+1) == n ) return iadr; // Fall-through, no branch
+            while( true ) {
+                CFGNode next = code._cfg.at(++cfgidx);
+                if( next == n ) return iadr; // Fall-through, no branch
+                if( next.nOuts()>1 )
+                    break;      // Has code in the block, need to jump around
+                // No code in the block, can fall through it
+            }
             sb.hex4(iadr++).p(" ").fix(encWidth,"??").p("  ").fix(opWidth,"JMP").p(" ").fix(argWidth,label(cfg)).nl();
             return iadr;
         }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
index 008f5e0c..70d8dfe4 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java
@@ -20,7 +20,8 @@ public class Chapter20Test {
 
     static void testCPU( String src, String cpu, String os, int spills, String stop ) {
         CodeGen code = new CodeGen(src);
-        code.parse().opto().typeCheck().instSelect(PORTS,cpu,os).GCM().localSched().regAlloc().encode();
+        code.parse().opto().typeCheck().instSelect(PORTS,cpu,os).GCM().localSched().regAlloc();
+        code.encode();
         int delta = spills>>3;
         if( delta==0 ) delta = 1;
         assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta);