From 22318a9654f4a6c3f26e6ad6800a875c16f472a2 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 31 Mar 2025 15:24:16 -0700 Subject: Fix encoding FIB Use common utility for walking CFG chains of empty blocks --- .../main/java/com/seaofnodes/simple/codegen/Encoding.java | 8 +++----- .../src/main/java/com/seaofnodes/simple/node/CFGNode.java | 7 +++++++ .../java/com/seaofnodes/simple/node/cpus/arm/BranchARM.java | 5 ++--- .../com/seaofnodes/simple/node/cpus/riscv/BranchRISC.java | 5 ++--- .../com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java | 7 ++----- .../src/test/java/com/seaofnodes/simple/Chapter21Test.java | 8 ++++++++ chapter21/src/test/java/com/seaofnodes/simple/progs/fib.smp | 13 +++++++++++++ 7 files changed, 37 insertions(+), 16 deletions(-) create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/fib.smp 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); -- cgit v1.2.3