From d15e43400bb7c7d0d27257d4c907206257c912b3 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 16 Mar 2025 10:41:20 -0700 Subject: Unconditional jumps --- .../java/com/seaofnodes/simple/node/CFGNode.java | 3 +- .../com/seaofnodes/simple/codegen/Encoding.java | 14 +++++++-- .../java/com/seaofnodes/simple/node/AddFNode.java | 2 +- .../java/com/seaofnodes/simple/node/AddNode.java | 2 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 2 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 6 +++- .../java/com/seaofnodes/simple/node/CProjNode.java | 2 +- .../com/seaofnodes/simple/node/CallEndNode.java | 2 +- .../java/com/seaofnodes/simple/node/CallNode.java | 2 +- .../java/com/seaofnodes/simple/node/CastNode.java | 2 +- .../com/seaofnodes/simple/node/ConstantNode.java | 2 +- .../java/com/seaofnodes/simple/node/CtrlNode.java | 2 +- .../java/com/seaofnodes/simple/node/DivFNode.java | 2 +- .../java/com/seaofnodes/simple/node/DivNode.java | 2 +- .../java/com/seaofnodes/simple/node/FRefNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 2 +- .../com/seaofnodes/simple/node/LogicalNode.java | 2 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 2 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 2 +- .../com/seaofnodes/simple/node/MinusFNode.java | 2 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulFNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulNode.java | 2 +- .../java/com/seaofnodes/simple/node/NewNode.java | 2 +- .../main/java/com/seaofnodes/simple/node/Node.java | 2 +- .../java/com/seaofnodes/simple/node/NotNode.java | 2 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 2 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 2 +- .../com/seaofnodes/simple/node/ReadOnlyNode.java | 2 +- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../com/seaofnodes/simple/node/RoundF32Node.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 2 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 2 +- .../com/seaofnodes/simple/node/StructNode.java | 2 +- .../java/com/seaofnodes/simple/node/SubFNode.java | 2 +- .../java/com/seaofnodes/simple/node/SubNode.java | 2 +- .../com/seaofnodes/simple/node/ToFloatNode.java | 2 +- .../java/com/seaofnodes/simple/node/XCtrlNode.java | 2 +- .../seaofnodes/simple/node/cpus/arm/BranchARM.java | 8 +++--- .../simple/node/cpus/riscv/BranchRISC.java | 7 ++--- .../simple/node/cpus/riscv/UJmpRISC.java | 33 ++++++++++++++++++++++ .../simple/node/cpus/x86_64_v2/JmpX86.java | 14 ++++----- .../simple/node/cpus/x86_64_v2/UJmpX86.java | 26 +++++++++++------ .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 8 ++---- .../java/com/seaofnodes/simple/Chapter21Test.java | 2 +- 49 files changed, 122 insertions(+), 77 deletions(-) create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/UJmpRISC.java diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java index c5cd95f0..37d08fb0 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -170,12 +170,11 @@ public abstract class CFGNode extends Node { return pre; } - boolean skip(CFGNode usecfg) { + private boolean skip(CFGNode usecfg) { // Only walk control users that are alive. // Do not walk from a Call to linked Fun's. return usecfg instanceof XCtrlNode || (this instanceof CallNode && usecfg instanceof FunNode) || (this instanceof ReturnNode && usecfg instanceof CallEndNode); } - } 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 ccb68fee..d004bb31 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -50,7 +50,7 @@ public class Encoding { return _code._regAlloc.regnum(n); } - public void add1( int op ) { _bits.write(op); } + public Encoding add1( int op ) { _bits.write(op); return this; } // Little endian write of a 32b opcode public void add4( int op ) { @@ -85,7 +85,7 @@ public class Encoding { assert t.isConstant(); // TODO: } - public void jump( IfNode jmp, CProjNode target ) { + public void jump( CFGNode jmp, CFGNode target ) { // TDOO: also support 1-byte offset and short jump and compressing the binary // TODO: record and patch } @@ -124,12 +124,20 @@ public class Encoding { // minimizes actual branches, takes advantage of fall-through edges, and // tries to help simple branch predictions: back branches are predicted // taken, forward not-taken. - private static void _rpo_cfg(CFGNode bb, BitSet visit, Ary rpo) { + private void _rpo_cfg(CFGNode bb, BitSet visit, Ary 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(); + // If the *next* BB has already been visited, we require an + // unconditional backwards jump here + if( visit.get(next._nid) ) { + CFGNode jmp = _code._mach.jump(); + jmp.setDefX(0,bb); + next.setDef(next._inputs.find(bb),jmp); + rpo.add(jmp); + } _rpo_cfg(next,visit,rpo); } else { boolean invert = false; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java index 7d4e2910..792da62e 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/AddFNode.java @@ -13,7 +13,7 @@ public class AddFNode extends Node { @Override public String glabel() { return "+"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { + public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); in(2)._print0(sb.append("+"), visited); return sb.append(")"); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java index bc65e79a..01d31aa2 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -15,7 +15,7 @@ public class AddNode extends Node { @Override public String glabel() { return "+"; } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { + public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); in(2)._print0(sb.append("+"), visited); return sb.append(")"); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java index e6b87ce8..f5f6a1de 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -21,7 +21,7 @@ abstract public class BoolNode extends Node { public String glabel() { return op(); } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { + public StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("("), visited); in(2)._print0(sb.append(op()), visited); return sb.append(")"); 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 86d4a52b..5c44f49f 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -170,7 +170,7 @@ public abstract class CFGNode extends Node { return pre; } - boolean skip(CFGNode usecfg) { + private boolean skip(CFGNode usecfg) { // Only walk control users that are alive. // Do not walk from a Call to linked Fun's. return usecfg instanceof XCtrlNode || @@ -178,4 +178,8 @@ public abstract class CFGNode extends Node { (this instanceof ReturnNode && usecfg instanceof CallEndNode); } + + public String label( CFGNode target ) { + return (target instanceof LoopNode ? "LOOP" : "L")+target._nid; + } } 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 f0a8e78a..d95ea227 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -24,7 +24,7 @@ public class CProjNode extends CFGNode { @Override public String label() { return _label; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } + @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } @Override public boolean blockHead() { return true; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 03a4462d..c98b2ff9 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -23,7 +23,7 @@ public class CallEndNode extends CFGNode implements MultiNode { public CallNode call() { return (CallNode)in(0); } @Override - StringBuilder _print1(StringBuilder sb, BitSet visited) { + public StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("cend( "); sb.append( in(0) instanceof CallNode ? "Call, " : "----, "); for( int i=1; i 1; // Should optimize jmp to empty targets + sb.p(label(target)); + } +} 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 ae5635b8..d15c0177 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 @@ -11,10 +11,8 @@ public class JmpX86 extends IfNode implements MachNode { super(iff); _bop = bop; } - @Override public String op() { return "j"+_bop; } @Override public String label() { return op(); } - @Override public void postSelect() { Node set = in(1); Node cmp = set.in(1); @@ -31,19 +29,17 @@ public class JmpX86 extends IfNode implements MachNode { // Encoding is appended into the byte array; size is returned @Override public void encoding( Encoding enc ) { enc.jump(this,cproj(0)); - // common opcode - enc.add1(0x0F); - enc.add1(x86_64_v2.jumpop(_bop)); + enc.add1(0x0F).add1(x86_64_v2.jumpop(_bop)); enc.add4(0); // Offset patched later } @Override public void asm(CodeGen code, SB sb) { String src = code.reg(in(1)); - if( src!="flags" ) sb.p(src); - Node prj = cproj(0); // 0 is True is jump target + if( src!="flags" ) sb.p(src).p(" "); + CFGNode prj = cproj(0); // 0 is True is jump target while( prj.nOuts() == 1 ) - prj = prj.out(0); // Skip empty blocks - sb.p(prj instanceof LoopNode ? " LOOP" : " L").p(prj._nid); + prj = prj.uctrl(); // Skip empty blocks + 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/x86_64_v2/UJmpX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/UJmpX86.java index 6d52df9d..a6e51856 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/UJmpX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/UJmpX86.java @@ -3,22 +3,30 @@ package com.seaofnodes.simple.node.cpus.x86_64_v2; import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import java.util.BitSet; // unconditional jump -// E9 cd JMP rel32 -public class UJmpX86 implements MachNode { +public class UJmpX86 extends CFGNode implements MachNode { UJmpX86() { } @Override public String op() { return "jmp"; } + @Override public String label() { return op(); } + @Override public StringBuilder _print1( StringBuilder sb, BitSet visited ) { + return sb.append("jmp "); + } @Override public RegMask regmap(int i) {return null; } @Override public RegMask outregmap() { return null; } - // Encoding is appended into the byte array; size is returned + @Override public Type compute() { throw Utils.TODO(); } + @Override public Node idealize() { throw Utils.TODO(); } @Override public void encoding( Encoding enc ) { - //enc.jump(); - //// E9 cd JMP rel32 - //enc.add1(0xE9); - //enc.add4(0); - throw Utils.TODO(); + enc.jump(this,uctrl()); + // E9 cd JMP rel32 + enc.add1(0xE9).add4(0); } - @Override public void asm(CodeGen code, SB sb) { } + @Override public void asm(CodeGen code, SB sb) { + CFGNode target = uctrl(); + assert target.nOuts() > 1; // Should optimize jmp to empty targets + sb.p(label(target)); + } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 8cd7128d..70d03a12 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -312,15 +312,13 @@ public class x86_64_v2 extends Machine { } // Create a split op; any register to any register, including stack slots - @Override - public SplitNode split(String kind, byte round, LRG lrg) { + @Override public SplitNode split(String kind, byte round, LRG lrg) { return new SplitX86(kind, round); } // Return a MachNode unconditional branch - @Override - public CFGNode jump() { - throw Utils.TODO(); + @Override public CFGNode jump() { + return new UJmpX86(); } // Break an infinite loop diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index eee4ceb7..648edbe1 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -78,6 +78,6 @@ return sqrt(farg) + sqrt(farg+2.0); """; testCPU(src,"x86_64_v2", "SystemV",3,"return .[];"); testCPU(src,"riscv" , "SystemV",1,"return (add,.[],(mul,.[],1000));"); - testCPU(src,"arm" , "SystemV",1,"return (add,.[],(muli,.[]));"); + testCPU(src,"arm" , "SystemV",1,"return (add,.[],(mul,.[],1000));"); } } -- cgit v1.2.3