Fix encoding FIB

Use common utility for walking CFG chains of empty blocks

7 files changed, 37 insertions, 16 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 fa703edc..b4d5aefa 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -108,9 +108,7 @@ public class Encoding {
         return this;
     }
     public void jump( CFGNode jmp, CFGNode dst ) {
-        while( dst.nOuts() == 1 ) // Skip empty blocks
-            dst = dst.uctrl();
-        _internals.put(jmp,dst);
+        _internals.put(jmp,dst.uctrlSkipEmpty());
     }
 
 
@@ -235,7 +233,7 @@ public class Encoding {
             // 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.
-            if( t.nOuts()==1 ) {
+            if( t.nOuts()==1 && !invert ) {
                 _rpo_cfg(f,visit,rpo);
                 _rpo_cfg(t,visit,rpo);
             } else {
@@ -339,7 +337,7 @@ public class Encoding {
                 CFGNode bb = _code._cfg.at(i);
                 _opStart[bb._nid] += slide;
                 if( bb instanceof RIPRelSize riprel ) {
-                    CFGNode target = (CFGNode)bb.out(0);
+                    CFGNode target = ((CFGNode)bb.out(0)).uctrlSkipEmpty();
                     // Delta is from opStart to opStart.  X86 at least counts
                     // the delta from the opEnd, but we don't have the end until
                     // we decide the size - so the encSize has to deal
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 5c44f49f..f198e65c 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -55,6 +55,13 @@ public abstract class CFGNode extends Node {
         return c;
     }
 
+    // Used by the encoding / final BB layout
+    public CFGNode uctrlSkipEmpty() {
+        CFGNode x = this, y=null;
+        while( x.nOuts() == 1 && (y=x.uctrl())!=null ) // Skip empty blocks
+            x = y;
+        return x;
+    }
 
     // ------------------------------------------------------------------------
     /**
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 e7e7a25b..ef3c4fc8 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
@@ -56,9 +56,8 @@ public class BranchARM extends IfNode implements MachNode, RIPRelSize {
     @Override public void asm(CodeGen code, SB sb) {
         String src = code.reg(in(1));
         if( src!="flags" ) sb.p(src).p(" ");
-        CFGNode prj = cproj(0);
-        while( prj.nOuts() == 1 )
-            prj = prj.uctrl();  // Skip empty blocks
+        CFGNode prj = cproj(0).uctrlSkipEmpty();
+        if( !prj.blockHead() ) prj = prj.cfg0();
         sb.p(label(prj));
     }
     @Override public String comment() { return "L"+cproj(1)._nid; }
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 ef1792eb..438ba760 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
@@ -68,9 +68,8 @@ public class BranchRISC extends IfNode implements MachNode, RIPRelSize {
         String src1 = in(1)==null ? "#0" : code.reg(in(1));
         String src2 = in(2)==null ? "#0" : code.reg(in(2));
         sb.p(src1).p(" ").p(_bop).p(" ").p(src2).p(" ");
-        CFGNode prj = cproj(0);
-        while( prj.nOuts() == 1 )
-            prj = prj.uctrl();       // Skip empty blocks
+        CFGNode prj = cproj(0).uctrlSkipEmpty();
+        if( !prj.blockHead() ) prj = prj.cfg0();
         sb.p(label(prj));
     }
 }
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 a6e280d3..d77d4acd 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
@@ -32,8 +32,6 @@ public class JmpX86 extends IfNode implements MachNode, RIPRelSize {
         int op = x86_64_v2.jumpop(_bop);
         enc.add1(op-16);      // Short form jump
         enc.add1(0);          // Offset
-        //enc.add1(0x0F).add1(x86_64_v2.jumpop(_bop));
-        //enc.add4(0);            // Offset patched later
     }
 
     // Delta is from opcode start, but X86 measures from the end of the 2-byte encoding
@@ -59,9 +57,8 @@ public class JmpX86 extends IfNode implements MachNode, RIPRelSize {
     @Override public void asm(CodeGen code, SB sb) {
         String src = code.reg(in(1));
         if( src!="flags" ) sb.p(src).p(" ");
-        CFGNode prj = cproj(0); // 0 is True is jump target
-        while( prj.nOuts() == 1 && !(prj instanceof ReturnNode) )
-            prj = prj.uctrl(); // Skip empty blocks
+        CFGNode prj = cproj(0).uctrlSkipEmpty(); // 0 is True is jump target
+        if( !prj.blockHead() ) prj = prj.cfg0();
         sb.p(label(prj));
     }
 
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index e3b69593..b1b39d6a 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -23,6 +23,7 @@ public class Chapter21Test {
     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();
+        String s = code.asm();
         int delta = spills>>3;
         if( delta==0 ) delta = 1;
         assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta);
@@ -69,6 +70,13 @@ public class Chapter21Test {
         testCPU(src,"arm"      , "SystemV",5,"return (add,.[],(mul,.[],1000));");
     }
 
+    @Test
+    public void testFib() throws IOException {
+        String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/fib.smp"));
+        testCPU(src,"x86_64_v2", "SystemV",24,null);
+        testCPU(src,"riscv"    , "SystemV",16,null);
+        testCPU(src,"arm"      , "SystemV",16,null);
+    }
 
     @Test
     public void testExport() throws IOException {
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/fib.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/fib.smp
new file mode 100644
index 00000000..fd6ed218
--- /dev/null
+++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/fib.smp
@@ -0,0 +1,13 @@
+// -*- mode: java;  -*-
+val fib = {int n ->
+    int f1=1;
+    int f2=1;
+    while( n-- > 1 ){
+        int temp = f1+f2;
+        f1=f2;
+        f2=temp;
+    }
+    return f2;
+};
+
+fib(10);