From d3bc904d9d44bd9ad1e1b6e72c5f9c1a8c428f0b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 16 Apr 2025 13:56:16 -0700 Subject: Fix risc5 branch invert Had conditions on forced invert mixed up. Sometimes need both a negate and a swap. rename invert as negate. --- .../com/seaofnodes/simple/codegen/Encoding.java | 7 ++-- .../java/com/seaofnodes/simple/node/IfNode.java | 8 ++--- .../seaofnodes/simple/node/cpus/arm/BranchARM.java | 2 +- .../com/seaofnodes/simple/node/cpus/arm/arm.java | 18 ++-------- .../simple/node/cpus/riscv/BranchRISC.java | 12 ++++--- .../seaofnodes/simple/node/cpus/riscv/riscv.java | 42 +++++++++++++--------- .../simple/node/cpus/x86_64_v2/JmpX86.java | 2 +- 7 files changed, 43 insertions(+), 48 deletions(-) (limited to 'chapter21/src/main/java/com') 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 395b3d46..5ff2836e 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -1,7 +1,6 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.Ary; -import com.seaofnodes.simple.SB; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; @@ -154,7 +153,7 @@ public class Encoding { } void encode() { - // Basic block layout: invert branches to keep blocks in-order; insert + // Basic block layout: negate branches to keep blocks in-order; insert // unconditional jumps. Attempt to keep backwards branches taken, // forwards not-taken (this is the default prediction on most // hardware). Layout is still RPO but with more restrictions. @@ -172,7 +171,7 @@ public class Encoding { patchLocalRelocations(); } - // Basic block layout: invert branches to keep blocks in-order; insert + // Basic block layout: negate branches to keep blocks in-order; insert // unconditional jumps. Attempt to keep backwards branches taken, // forwards not-taken (this is the default prediction on most // hardware). Layout is still RPO but with more restrictions. @@ -247,7 +246,7 @@ public class Encoding { } // always forward and good // Invert test and Proj fields if( invert ) { - iff.invert(); + iff.negate(); t.invert(); f.invert(); CProjNode tmp=f; f=t; t=tmp; // Swap t/f 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 9bb269d5..5b26f23d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -2,10 +2,8 @@ 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.*; import java.util.BitSet; -import java.util.HashSet; public class IfNode extends CFGNode implements MultiNode { @@ -67,12 +65,12 @@ public class IfNode extends CFGNode implements MultiNode { return null; } - // MachNode variants need to support this and invert the conditional test. + // MachNode variants need to support this and negate the conditional test. // The following CProjs will be inverted by the caller. - public void invert() { throw Utils.TODO(); } + public void negate() { throw Utils.TODO(); } // Negate the sense of a test - public static String invert( String bop ) { + public static String negate( String bop ) { return switch( bop ) { case "<" -> ">="; case "<=" -> ">" ; 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 4b8bd687..b36a395b 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 @@ -27,7 +27,7 @@ public class BranchARM extends IfNode implements MachNode, RIPRelSize { @Override public RegMask regmap(int i) { assert i==1; return arm.FLAGS_MASK; } @Override public RegMask outregmap() { return null; } - @Override public void invert() { _bop = invert(_bop); } + @Override public void negate() { _bop = negate(_bop); } @Override public void encoding( Encoding enc ) { // Assuming that condition flags are already set. These flags are set diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 782a3cae..ca3d096b 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -4,7 +4,6 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import java.io.ByteArrayOutputStream; public class arm extends Machine { public arm( CodeGen code ) { @@ -213,17 +212,6 @@ public class arm extends Machine { SXTX, // base+ s64 index [<< logsize] } - static public String invert(String op) { - return switch (op) { - case "==" -> "!="; - case "!=" -> "=="; - case ">" -> "<="; - case "<" -> ">="; - case ">=" -> "<"; - case "<=" -> ">"; - default -> throw new IllegalStateException("Unexpected value: " + op); - }; - } public enum COND { EQ, NE, @@ -618,12 +606,10 @@ public class arm extends Machine { private Node cmp(BoolNode bool){ Node cmp = _cmp(bool); - return new SetARM(cmp, invert(bool.op())); + return new SetARM(cmp, IfNode.negate(bool.op())); } private Node _cmp(BoolNode bool) { - if( bool instanceof BoolNode.EQF || - bool instanceof BoolNode.LTF || - bool instanceof BoolNode.LEF ) + if( bool.isFloat() ) return new CmpFARM(bool); return bool.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti ? new CmpIARM(bool, (int)ti.value()) 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 6b1568f2..44ff4e8b 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 @@ -21,11 +21,13 @@ public class BranchRISC extends IfNode implements MachNode, RIPRelSize { @Override public String comment() { return "L"+cproj(1)._nid; } @Override public RegMask regmap(int i) { return riscv.RMASK; } @Override public RegMask outregmap() { return null; } - @Override public void invert() { - if( _bop.equals("<") || _bop.equals("<=") ) - swap12(); // Cannot invert the test, so swap the operands - else - _bop = invert(_bop); + @Override public void negate() { + _bop = negate(_bop); + // Cannot encode ">" or "<=", so flip these + if( _bop.equals(">") || _bop.equals("<=") ) { + swap12(); // Cannot negate the test, so swap the operands + _bop = swap(_bop); // Swap test to match + } } @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 103fff0d..47d1db75 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -32,14 +32,24 @@ public class riscv extends Machine { public static final int F_OFFSET = 32; static final String[] REGS = new String[] { - "zero","rpc" , "sp" , "s12" , "s13" , "t0" , "t1" , "t2" , - "s0" , "s1" , "a0" , "a1" , "a2" , "a3" , "a4" , "a5" , - "a6" , "a7" , "s2" , "s3" , "s4" , "s5" , "s6" , "s7" , - "s8" , "s9" , "s10" , "s11" , "t3" , "t4" , "t5" , "t6" , - "f0" , "f1" , "f2" , "f3" , "f4" , "f5" , "f6" , "f7" , - "fs0" , "fs1" , "fa0" , "fa1" , "fa2" , "fa3" , "fa4" , "fa5" , - "fa6" , "fa7" , "fs2" , "fs3" , "fs4" , "fs5" , "fs6" , "fs7" , - "fs8" , "fs9" , "fs10", "fs11", "ft8" , "ft9" , "ft10", "ft11" + "zero","rpc" , "rsp" , "s12" , "s13" , "t0" , "t1" , "t2" , + "s0" , "s1" , "a0" , "a1" , "a2" , "a3" , "a4" , "a5" , + "a6" , "a7" , "s2" , "s3" , "s4" , "s5" , "s6" , "s7" , + "s8" , "s9" , "s10" , "s11" , "t3" , "t4" , "t5" , "t6" , + "f0" , "f1" , "f2" , "f3" , "f4" , "f5" , "f6" , "f7" , + "fs0" , "fs1" , "fa0" , "fa1" , "fa2" , "fa3" , "fa4" , "fa5" , + "fa6" , "fa7" , "fs2" , "fs3" , "fs4" , "fs5" , "fs6" , "fs7" , + "fs8" , "fs9" , "fs10", "fs11", "ft8" , "ft9" , "ft10", "ft11" + // Register-based naming hella easier to debug than "official" register + // names when single-stepping in debugger. + //"zero", "r1" , "rsp" , "r3" , "r4" , "r5" , "r6" , "r7" , + //"r8" , "r9" , "r10" , "r11", "r12", "r13", "r14", "r15", + //"r16" , "r17" , "r18" , "r19", "r20", "r21", "r22", "r23", + //"r24" , "r25" , "r26" , "r27", "r28", "r29", "r30", "r31", + //"f0" , "f1" , "f2" , "f3" , "f4" , "f5" , "f6" , "f7" , + //"fs0" , "fs1" , "fa0" , "fa1" , "fa2" , "fa3" , "fa4" , "fa5" , + //"fa6" , "fa7" , "fs2" , "fs3" , "fs4" , "fs5" , "fs6" , "fs7" , + //"fs8" , "fs9" , "fs10", "fs11", "ft8" , "ft9" , "ft10", "ft11" }; @Override public String[] regs() { return REGS; } @@ -226,7 +236,7 @@ public class riscv extends Machine { case "==" -> 0x0; case "!=" -> 0x1; case "<" -> 0x4; - case "<=" -> 0x5; + case ">=" -> 0x5; case "u<" -> 0x6; case "u<=" -> 0x7; default -> throw Utils.TODO(); @@ -360,7 +370,7 @@ public class riscv extends Machine { } private Node add(AddNode add) { - if( add.in(2) instanceof ConstantNode off && off._con instanceof TypeInteger ti && imm12(ti) ) + if( add.in(2) instanceof ConstantNode off2 && off2._con instanceof TypeInteger ti && imm12(ti) ) return new AddIRISC(add, (int)ti.value(),true); return new AddRISC(add); } @@ -393,11 +403,11 @@ public class riscv extends Machine { // Only < and y - swap; y < x - // x >= y - swap and invert; !(x < y); `slt tmp=y,x;` then NOT. + // x >= y - swap and negate; !(x < y); `slt tmp=y,x;` then NOT. // x != y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` then NOT. // The ">", ">=" and "!=" in Simple include a NotNode, which can be @@ -407,8 +417,8 @@ public class riscv extends Machine { return switch( bool.op() ) { case "<" -> bool.in(2) instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm12(ti) ? new SetIRISC(bool, (int)ti.value(),false) - : new SetRISC(bool, false); - // x <= y - flip and invert; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` + : new SetRISC(bool, false); + // x <= y - flip and negate; !(y < x); `slt tmp=y,x; xori dst=tmp,#1` case "<=" -> new XorIRISC(new SetRISC(bool.swap12(), false),1); // x == y - sub and vs0 == `sub tmp=x-y; sltu dst=tmp,#1` case "==" -> new SetIRISC(new SubRISC(bool),1,true); @@ -448,8 +458,8 @@ public class riscv extends Machine { if( iff.in(1) instanceof BoolNode bool && !bool.isFloat() ) { // if less than or equal switch inputs String bop = bool.op(); - if( bop.equals(">=") || bop.equals(">") ) - return new BranchRISC(iff, IfNode.invert(bop), bool.in(2), bool.in(1)); + if( bop.equals("<=") || bop.equals(">") ) + return new BranchRISC(iff, IfNode.swap(bop), bool.in(2), bool.in(1)); return new BranchRISC(iff, bop, bool.in(1), bool.in(2)); } // Vs zero 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 51e7f061..d7acf8b8 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 @@ -26,7 +26,7 @@ public class JmpX86 extends IfNode implements MachNode, RIPRelSize { } @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.FLAGS_MASK; } @Override public RegMask outregmap() { return null; } - @Override public void invert() { _bop = invert(_bop); } + @Override public void negate() { _bop = negate(_bop); } @Override public void encoding( Encoding enc ) { if( in(1)!=null ) { -- cgit v1.2.3