From 309da044c29f7f5e92f00aca911e69c8bfad7caf Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 16 Mar 2025 22:03:51 -0700 Subject: short-form x86 encodings --- .../com/seaofnodes/simple/codegen/Encoding.java | 95 ++++++++++++++++++---- .../com/seaofnodes/simple/codegen/RIPRelSize.java | 6 ++ .../simple/node/cpus/x86_64_v2/JmpX86.java | 11 ++- .../simple/node/cpus/x86_64_v2/UJmpX86.java | 10 ++- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 6 +- .../java/com/seaofnodes/simple/BrainFuckTest.java | 6 +- 6 files changed, 108 insertions(+), 26 deletions(-) create mode 100644 chapter21/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java (limited to 'chapter21') 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 d004bb31..b0fda2e1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -1,20 +1,23 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Utils; 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.TypeFunPtr; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeFunPtr; import java.io.ByteArrayOutputStream; +import java.util.Arrays; import java.util.BitSet; +import java.util.HashMap; /** * Instruction encodings - * + *

* This class holds the encoding bits, plus the relocation information needed * to move the code to a non-zero offset, or write to an external file (ELF). - * + *

* There are also a bunch of generic utilities for managing bits and bytes * common in all encodings. */ @@ -35,14 +38,20 @@ public class Encoding { // - RIP-relative to external chunks have a zero offset; the matching // relocation info will be used to patch the correct value. - public class BAOS extends ByteArrayOutputStream { public byte[] buf() { return buf; } }; + public static class BAOS extends ByteArrayOutputStream { + public byte[] buf() { return buf; } + void set( byte[] buf0, int count0 ) { buf=buf0; count=count0; } + }; final public BAOS _bits; - public byte[] _opLen; + public int [] _opStart; // Start of opcodes, by _nid + public byte[] _opLen; // Length of opcodes, by _nid Encoding( CodeGen code ) { _code = code; _bits = new BAOS(); + _bigCons = new HashMap<>(); + _jmps = new HashMap<>(); } // Shortcut to the defining register @@ -81,42 +90,55 @@ public class Encoding { } // Store t as a 32/64 bit constant in the code space; generate RIP-relative // addressing to load it + + private final HashMap _bigCons; public void largeConstant( Node relo, Type t ) { assert t.isConstant(); + _bigCons.put(relo,t); // TODO: } + private final HashMap _jmps; public void jump( CFGNode jmp, CFGNode target ) { // TDOO: also support 1-byte offset and short jump and compressing the binary // TODO: record and patch } void encode() { - // Basic block layout + // Basic block layout: invert branches to keep blocks in-order; insert + // unconditional jumps. Layout is still RPO but with more restrictions. Ary rpo = new Ary<>(CFGNode.class); BitSet visit = _code.visit(); for( Node n : _code._start._outputs ) if( n instanceof FunNode fun ) _rpo_cfg(fun, visit, rpo); rpo.add(_code._start); + // Reverse in-place for( int i=0; i< rpo.size()>>1; i++ ) rpo.swap(i,rpo.size()-1-i); visit.clear(); _code._cfg = rpo; // Save the new ordering - _opLen = new byte[_code.UID()]; // Write encoding bits in order - for( CFGNode bb : _code._cfg ) - for( Node n : bb._outputs ) + _opStart= new int [_code.UID()]; + _opLen = new byte[_code.UID()]; // Used during ASM printing + for( CFGNode bb : _code._cfg ) { + if( bb instanceof CProjNode ) _opStart[bb._nid] = _bits.size(); + for( Node n : bb._outputs ) { if( n instanceof MachNode mach ) { - int off = _bits.size(); - mach.encoding(this); - _opLen[n._nid] = (byte)(_bits.size()-off); + _opStart[n._nid] = _bits.size(); + mach.encoding( this ); + _opLen[n._nid] = (byte) (_bits.size() - _opStart[n._nid]); } + } + } System.out.println(_code.asm()); + + compactShortForm(); + // Patch RIP-relative encodings now - //throw Utils.TODO(); + throw Utils.TODO(); } // Basic block layout. Now that RegAlloc is finished, no more spill code @@ -181,4 +203,49 @@ public class Encoding { } + // Short-form RIP-relative support + void compactShortForm() { + int len = _code._cfg._len; + int[] oldStarts = new int[len]; + for( int i=0; i 0 ) { + int end = _bits.size(); + byte[] bits = new byte[end+grow]; + for( int i=len-1; i>=0; i-- ) { + int start = oldStarts[i]; + if( start==0 && i>1 ) continue; + int oldStart = oldStarts[i]; + int newStart = _opStart[_code._cfg.at(i)._nid]; + System.arraycopy(_bits.buf(),oldStart,bits,newStart,end-start); + end = start; + } + _bits.set(bits,bits.length); + } + } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java new file mode 100644 index 00000000..36f36b5a --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java @@ -0,0 +1,6 @@ +package com.seaofnodes.simple.codegen; + +// This Node rip-relative encodings has sizes that vary by delta +public interface RIPRelSize { + byte encSize(int delta); +} 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 d15c0177..b307cbd6 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 @@ -5,7 +5,7 @@ import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; // Jump on flags, uses flags -public class JmpX86 extends IfNode implements MachNode { +public class JmpX86 extends IfNode implements MachNode, RIPRelSize { String _bop; JmpX86( IfNode iff, String bop ) { super(iff); @@ -29,10 +29,15 @@ 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)); - enc.add1(0x0F).add1(x86_64_v2.jumpop(_bop)); - enc.add4(0); // Offset patched later + 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 } + @Override public byte encSize(int delta) { return (byte)(x86_64_v2.imm8(delta-2) ? 2 : 6); } + @Override public void asm(CodeGen code, SB sb) { String src = code.reg(in(1)); if( src!="flags" ) sb.p(src).p(" "); 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 a6e51856..e77acfa3 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 @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.Type; import java.util.BitSet; // unconditional jump -public class UJmpX86 extends CFGNode implements MachNode { +public class UJmpX86 extends CFGNode implements MachNode, RIPRelSize { UJmpX86() { } @Override public String op() { return "jmp"; } @Override public String label() { return op(); } @@ -20,10 +20,14 @@ public class UJmpX86 extends CFGNode implements MachNode { @Override public Node idealize() { throw Utils.TODO(); } @Override public void encoding( Encoding enc ) { enc.jump(this,uctrl()); - // E9 cd JMP rel32 - enc.add1(0xE9).add4(0); + // Short-form jump + enc.add1(0xEB).add1(0); + //// E9 cd JMP rel32 + //enc.add1(0xE9).add4(0); } + @Override public byte encSize(int delta) { return (byte)(x86_64_v2.imm8(delta) ? 2 : 6); } + @Override public void asm(CodeGen code, SB sb) { CFGNode target = uctrl(); assert target.nOuts() > 1; // Should optimize jmp to empty targets 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 70d03a12..8f29c06e 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 @@ -63,10 +63,10 @@ public class x86_64_v2 extends Machine { }; // opcode included here - // 0F 84 cd JE rel32 + // 0F 84 cd JE rel32 // 0F 85 cd JNE rel32 - // 0F 8F cd JG rel32 - // 0F 8C cd JL rel32 + // 0F 8F cd JG rel32 + // 0F 8C cd JL rel32 // 0F 8E cd JLE rel32 // 0F 8D cd JGE rel32 static public int jumpop(String op) { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index dd1f2372..8b23a0ca 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -63,9 +63,9 @@ for( int pc = 0; pc < program#; pc++ ) { } return output; """; - Chapter20Test.testCPU(src,"x86_64_v2", "SystemV",28,null); - Chapter20Test.testCPU(src,"riscv" , "SystemV",14,null); - Chapter20Test.testCPU(src,"arm" , "SystemV",12,null); + Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",28,null); + Chapter21Test.testCPU(src,"riscv" , "SystemV",14,null); + Chapter21Test.testCPU(src,"arm" , "SystemV",12,null); //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); } } -- cgit v1.2.3