From 5eb00d3306e6e8738b8033c5ba8401770f9d7ffd Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 17 Sep 2026 15:15:00 -0700 Subject: Backport x86 Not encoding --- .../simple/node/cpus/x86_64_v2/NotX86.java | 17 +++--- .../seaofnodes/simple/codegen/X86EncodingTest.java | 65 ++++++++++++++++++++++ .../simple/node/cpus/x86_64_v2/NotX86.java | 17 +++--- .../seaofnodes/simple/codegen/X86EncodingTest.java | 44 +++++++++++++++ .../simple/node/cpus/x86_64_v2/NotX86.java | 17 +++--- .../seaofnodes/simple/codegen/X86EncodingTest.java | 44 +++++++++++++++ .../simple/node/cpus/x86_64_v2/NotX86.java | 17 +++--- .../seaofnodes/simple/codegen/X86EncodingTest.java | 44 +++++++++++++++ docs/chapter-backports.md | 1 - 9 files changed, 225 insertions(+), 41 deletions(-) diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java index b23249b8..2d611931 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -17,23 +17,20 @@ public class NotX86 extends MachConcreteNode implements MachNode { short dst = enc.reg(this ); short src = enc.reg(in(1)); - // Pre-zero using XOR dst,dst; since zero'd will not have a - // byte-dependency from the setz. Can skip REX is dst is low 8, makes - // this a 32b xor, which will also zero the high bits. - if( dst >= 8 ) enc.add1(x86_64_v2.rex(dst, dst, 0)); - enc.add1(0x33); // opcode - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); - // test rdi,rdi enc.add1(x86_64_v2.rex(src, src, 0)); enc.add1(0x85); enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, src, src)); - // setz (sete dil) - enc.add1(x86_64_v2.rex(dst, 0, 0)); + // setz dstb; then zero-extend the low byte into the full register. + if( dst >= 4 ) enc.add1(x86_64_v2.rex(0, dst, 0, false)); enc.add1(0x0F); enc.add1(0x94); - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, 0)); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 0, dst)); + if( dst >= 4 ) enc.add1(x86_64_v2.rex(dst, dst, 0, false)); + enc.add1(0x0F); + enc.add1(0xB6); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/chapter21/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java index 03a57675..368c243b 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java @@ -1,10 +1,55 @@ package com.seaofnodes.simple.codegen; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86; import org.junit.Test; import static org.junit.Assert.*; public class X86EncodingTest { + + @Test + public void testLogicalNotRegisters() { + CodeGen code = new CodeGen("return !arg;") + .driver(CodeGen.Phase.InstSelect, "x86_64_v2", "SystemV"); + var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null); + assertNotNull("Must exercise logical not", not); + int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}}; + // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping + // registers, low-byte registers requiring REX, and extended registers. + String[] expected = { + "4885c00f94c00fb6c0", "4885c90f94c10fb6c9", + "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9", + "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9", + "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff" + }; + for (int i = 0; i < registers.length; i++) { + int dst = registers[i][0], src = registers[i][1]; + var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src); + not.encoding(enc); + assertArrayEquals("Logical not dst=" + dst + ", src=" + src, + java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray()); + } + } + + @Test + public void testLogicalNotExecution() throws java.io.IOException { + var dir = java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"), + "val logicalNot = { int x -> return !x; };"); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """ + #include + extern long long logicalNot(long long); + int main(void) { + long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32}; + for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++) + if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1; + return 0; + } + """); + com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1); + } @Test public void testMemoryCompare64Immediate32() { for (int immediate : new int[]{123456789, -123456789}) { @@ -29,4 +74,24 @@ public class X86EncodingTest { assertEquals(0x94, enc.read1(start + 10)); } } + + /** Exercise instruction encoders with explicit registers, independent of allocator choices. */ + private static class FixedRegisterEncoding extends Encoding { + private final Node _dst, _src; + private final short _dstReg, _srcReg; + + FixedRegisterEncoding(CodeGen code, Node dst, int dstReg, Node src, int srcReg) { + super(code); + _dst = dst; + _src = src; + _dstReg = (short)dstReg; + _srcReg = (short)srcReg; + } + + @Override public short reg(Node n) { + if (n == _dst) return _dstReg; + if (n == _src) return _srcReg; + throw new AssertionError("Unexpected register lookup"); + } + } } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java index b23249b8..2d611931 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -17,23 +17,20 @@ public class NotX86 extends MachConcreteNode implements MachNode { short dst = enc.reg(this ); short src = enc.reg(in(1)); - // Pre-zero using XOR dst,dst; since zero'd will not have a - // byte-dependency from the setz. Can skip REX is dst is low 8, makes - // this a 32b xor, which will also zero the high bits. - if( dst >= 8 ) enc.add1(x86_64_v2.rex(dst, dst, 0)); - enc.add1(0x33); // opcode - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); - // test rdi,rdi enc.add1(x86_64_v2.rex(src, src, 0)); enc.add1(0x85); enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, src, src)); - // setz (sete dil) - enc.add1(x86_64_v2.rex(dst, 0, 0)); + // setz dstb; then zero-extend the low byte into the full register. + if( dst >= 4 ) enc.add1(x86_64_v2.rex(0, dst, 0, false)); enc.add1(0x0F); enc.add1(0x94); - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, 0)); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 0, dst)); + if( dst >= 4 ) enc.add1(x86_64_v2.rex(dst, dst, 0, false)); + enc.add1(0x0F); + enc.add1(0xB6); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/chapter22/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java index 389f0363..0914d916 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java @@ -2,12 +2,56 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86; import com.seaofnodes.simple.node.cpus.x86_64_v2.MulIX86; import org.junit.Test; import static org.junit.Assert.*; public class X86EncodingTest { + @Test + public void testLogicalNotRegisters() { + CodeGen code = new CodeGen("return !arg;") + .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV"); + var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null); + assertNotNull("Must exercise logical not", not); + int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}}; + // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping + // registers, low-byte registers requiring REX, and extended registers. + String[] expected = { + "4885c00f94c00fb6c0", "4885c90f94c10fb6c9", + "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9", + "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9", + "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff" + }; + for (int i = 0; i < registers.length; i++) { + int dst = registers[i][0], src = registers[i][1]; + var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src); + not.encoding(enc); + assertArrayEquals("Logical not dst=" + dst + ", src=" + src, + java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray()); + } + } + + @Test + public void testLogicalNotExecution() throws java.io.IOException { + var dir = java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"), + "val logicalNot = { int x -> return !x; };"); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """ + #include + extern long long logicalNot(long long); + int main(void) { + long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32}; + for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++) + if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1; + return 0; + } + """); + com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1); + } + @Test public void testMultiplyImmediateRegisters() { // Destination, source, expected REX and ModRM. Cross the register-8 diff --git a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java index d9056be9..7db80299 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -17,23 +17,20 @@ public class NotX86 extends MachConcreteNode implements MachNode { short dst = enc.reg(this ); short src = enc.reg(in(1)); - // Pre-zero using XOR dst,dst; since zero'd will not have a - // byte-dependency from the setz. Can skip REX is dst is low 8, makes - // this a 32b xor, which will also zero the high bits. - if( dst >= 8 ) enc.add1(x86_64_v2.rex(dst, dst, 0)); - enc.add1(0x33); // opcode - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); - // test rdi,rdi enc.add1(x86_64_v2.rex(src, src, 0)); enc.add1(0x85); enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, src, src)); - // setz (sete dil) - enc.add1(x86_64_v2.rex(dst, 0, 0)); + // setz dstb; then zero-extend the low byte into the full register. + if( dst >= 4 ) enc.add1(x86_64_v2.rex(0, dst, 0, false)); enc.add1(0x0F); enc.add1(0x94); - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, 0)); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 0, dst)); + if( dst >= 4 ) enc.add1(x86_64_v2.rex(dst, dst, 0, false)); + enc.add1(0x0F); + enc.add1(0xB6); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter23/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/chapter23/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java index 389f0363..0914d916 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java @@ -2,12 +2,56 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86; import com.seaofnodes.simple.node.cpus.x86_64_v2.MulIX86; import org.junit.Test; import static org.junit.Assert.*; public class X86EncodingTest { + @Test + public void testLogicalNotRegisters() { + CodeGen code = new CodeGen("return !arg;") + .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV"); + var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null); + assertNotNull("Must exercise logical not", not); + int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}}; + // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping + // registers, low-byte registers requiring REX, and extended registers. + String[] expected = { + "4885c00f94c00fb6c0", "4885c90f94c10fb6c9", + "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9", + "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9", + "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff" + }; + for (int i = 0; i < registers.length; i++) { + int dst = registers[i][0], src = registers[i][1]; + var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src); + not.encoding(enc); + assertArrayEquals("Logical not dst=" + dst + ", src=" + src, + java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray()); + } + } + + @Test + public void testLogicalNotExecution() throws java.io.IOException { + var dir = java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"), + "val logicalNot = { int x -> return !x; };"); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """ + #include + extern long long logicalNot(long long); + int main(void) { + long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32}; + for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++) + if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1; + return 0; + } + """); + com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1); + } + @Test public void testMultiplyImmediateRegisters() { // Destination, source, expected REX and ModRM. Cross the register-8 diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java index d9056be9..7db80299 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -17,23 +17,20 @@ public class NotX86 extends MachConcreteNode implements MachNode { short dst = enc.reg(this ); short src = enc.reg(in(1)); - // Pre-zero using XOR dst,dst; since zero'd will not have a - // byte-dependency from the setz. Can skip REX is dst is low 8, makes - // this a 32b xor, which will also zero the high bits. - if( dst >= 8 ) enc.add1(x86_64_v2.rex(dst, dst, 0)); - enc.add1(0x33); // opcode - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); - // test rdi,rdi enc.add1(x86_64_v2.rex(src, src, 0)); enc.add1(0x85); enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, src, src)); - // setz (sete dil) - enc.add1(x86_64_v2.rex(dst, 0, 0)); + // setz dstb; then zero-extend the low byte into the full register. + if( dst >= 4 ) enc.add1(x86_64_v2.rex(0, dst, 0, false)); enc.add1(0x0F); enc.add1(0x94); - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, 0)); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 0, dst)); + if( dst >= 4 ) enc.add1(x86_64_v2.rex(dst, dst, 0, false)); + enc.add1(0x0F); + enc.add1(0xB6); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java b/chapter24/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java index 389f0363..0914d916 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/codegen/X86EncodingTest.java @@ -2,12 +2,56 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.cpus.x86_64_v2.CmpMemX86; +import com.seaofnodes.simple.node.cpus.x86_64_v2.NotX86; import com.seaofnodes.simple.node.cpus.x86_64_v2.MulIX86; import org.junit.Test; import static org.junit.Assert.*; public class X86EncodingTest { + @Test + public void testLogicalNotRegisters() { + CodeGen code = new CodeGen("return !arg;") + .driver(CodeGen.Phase.Select, "x86_64_v2", "SystemV"); + var not = code._stop.walk(n -> n instanceof NotX86 ? (NotX86)n : null); + assertNotNull("Must exercise logical not", not); + int[][] registers = {{0,0}, {1,1}, {7,7}, {9,9}, {1,9}, {9,1}, {6,0}, {15,8}}; + // TEST src,src; SETZ dstb; MOVZX dst32,dstb. Include overlapping + // registers, low-byte registers requiring REX, and extended registers. + String[] expected = { + "4885c00f94c00fb6c0", "4885c90f94c10fb6c9", + "4885ff400f94c7400fb6ff", "4d85c9410f94c1450fb6c9", + "4d85c90f94c10fb6c9", "4885c9410f94c1450fb6c9", + "4885c0400f94c6400fb6f6", "4d85c0410f94c7450fb6ff" + }; + for (int i = 0; i < registers.length; i++) { + int dst = registers[i][0], src = registers[i][1]; + var enc = new FixedRegisterEncoding(code, not, dst, not.in(1), src); + not.encoding(enc); + assertArrayEquals("Logical not dst=" + dst + ", src=" + src, + java.util.HexFormat.of().parseHex(expected[i]), enc._bits.toByteArray()); + } + } + + @Test + public void testLogicalNotExecution() throws java.io.IOException { + var dir = java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.smp"), + "val logicalNot = { int x -> return !x; };"); + java.nio.file.Files.writeString(dir.resolve("x86LogicalNot.c"), """ + #include + extern long long logicalNot(long long); + int main(void) { + long long inputs[] = {0, 1, -1, LLONG_MIN, LLONG_MAX, 1LL << 32}; + for (unsigned i = 0; i < sizeof(inputs)/sizeof(inputs[0]); i++) + if (logicalNot(inputs[i]) != (inputs[i] == 0)) return 1; + return 0; + } + """); + com.seaofnodes.simple.TestC.run("build/objs", "x86LogicalNot", "", -1); + } + @Test public void testMultiplyImmediateRegisters() { // Destination, source, expected REX and ModRM. Cross the register-8 diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index b01afa10..9761bade 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -19,7 +19,6 @@ the correction into the chapter's representation, not the entire modern file. | ID | Change | Proposed destination | Scope and acceptance evidence | |---|---|---|---| -| B03 | Correct x86 logical-not encoding | 21 through 24 | `NotX86`: preserve a shared source/destination until after testing; correct SETcc operand fields and zero-extend its byte result. Check zero/nonzero, overlapping registers, and byte registers requiring REX. Exclude Not/Phi optimizations. | | B04 | Preserve comparison results while releasing parser temporaries | 24 | `parseComparison` lifetime fix in `414931c8`. Reduce seed `-8212834489697770130`; exclude unrelated `` cleanup in that commit. | | B05 | Preserve RHS control, memory, and local updates in logical OR | 23 through 24; **audit** earliest implementation | Chapter 25 `parseIf` retains `_scope` for the false-side `||` expression. Test scalar and field updates and short-circuit behavior. Avoid importing GuardNode. | | B06 | Decode string escapes; reject unknown/truncated escapes | 22 through 24 | Literal scanner only. Check newline, tab, carriage return, backslash, quote, NUL, and malformed input. | -- cgit v1.2.3