diff options
| author | Cliff Click <cliffc@acm.org> | 2025-04-24 14:38:36 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-04-24 14:38:36 -0700 |
| commit | cadc530688041b5455e6251055754df6f4182aec (patch) | |
| tree | 1f83d6d9285adb0c10c9147da3e64700e8ea2820 /src/main/java/com/seaofnodes/simple/codegen | |
| parent | f6c0b12e6cc1af4879042c0426fc96532cdfddc3 (diff) | |
| download | Simple-linear-chapter21.tar.gz Simple-linear-chapter21.zip | |
Chapter 21: Instruction Encoding and ELFlinear-chapter21
Co-authored-by: Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com>
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/codegen')
16 files changed, 1692 insertions, 218 deletions
diff --git a/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index 88b49863..a2bb21ed 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.codegen; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeMem; @@ -27,7 +26,7 @@ abstract public class BuildLRG { break; // If none, make one. if( lrg==null ) lrg = alloc.newLRG(n); - if( phi instanceof MachNode mach ) defLRG(alloc,n); + if( phi instanceof MachNode ) defLRG(alloc,n); // Pass 2: everybody uses the same LRG lrg=alloc.union(lrg,phi); for( int i=phi instanceof ParmNode ? 2 : 1; i<n.nIns(); i++ ) @@ -55,8 +54,8 @@ abstract public class BuildLRG { if( n.in(i)!=null ) { LRG lrg2 = alloc.lrg(n.in(i)); if( lrg2 != null ) { // Anti-dep or other, no LRG - RegMask use_mask = mach.regmap(i); - if( !lrg2.machUse(mach,(short)i,use_mask.size1()).and(use_mask) ) + RegMask use_mask = mach.regmap(i); // use_mask is also null for anti-dep + if( use_mask!=null && !lrg2.machUse(mach,(short)i,use_mask.size1()).and(use_mask) ) alloc.fail(lrg2); // Empty register mask, must split } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java new file mode 100644 index 00000000..e2fac779 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java @@ -0,0 +1,105 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Ary; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.*; +import java.util.BitSet; +import java.util.IdentityHashMap; + +// Coalesce copies +abstract public class Coalesce { + + public static boolean coalesce( int round, RegAlloc alloc ) { + + // Walk all the splits, looking for coalesce chances + boolean progress = false; + for( CFGNode bb : alloc._code._cfg ) { + outer: + for( int j=0; j<bb.nOuts(); j++ ) { + Node n = bb.out(j); + if( !(n instanceof SplitNode) ) continue; + LRG v1 = alloc.lrg(n); + LRG v2 = alloc.lrg(n.in(1)); + if( v1 != v2 ) { + LRG ov1 = v1, ov2 = v2; + // Get the smaller neighbor count in v1 + if( v1.nadj() > v2.nadj() ) + { v1 = v2; v2 = alloc.lrg(n); } + int v2len = v2._adj==null ? 0 : v2._adj._len; + // See that they do not conflict (coalescing would make a self-conflict) + if( v1._adj!=null && v2._adj!=null && v1._mask.overlap(v2._mask) ) { + // Walk the smaller neighbors, and add to the larger. + // Check for direct conflicts along the way. + for( LRG v3 : v1._adj ) { + if( v3==v2 ) { + // Direct conflict, skip this LRG pair + v2._adj.setLen(v2len); + continue outer; + } + // Add missing LRGs from V1 to V2 + if( v2._adj.find(v3)== -1 ) + v2._adj.push(v3); + } + } + // Most constrained mask + RegMask mask = v1._mask==v2._mask ? v1._mask : v1._mask.copy().and(v2._mask); + // Check for capacity + if( v2.nadj() >= mask.size() ) { + // Fails capacity, will not be trivial colorable + if( v2._adj!=null ) v2._adj.setLen(v2len); + continue; + } + + // Union lrgs. + progress = true; + + // Since `n` is dying, remove from the LRGS BEFORE doing + // the union; this will let the union code keep the + // matching bits from the other side, preserving some + // info for biased coloring + if( ov1. _machDef==n ) ov1. _machDef = null; + if( ov1._splitDef==n ) ov1._splitDef = null; + if( ov2. _machUse==n ) ov2. _machUse = null; + if( ov2._splitUse==n ) ov2._splitUse = null; + // Keep larger adjacency list. + Ary<LRG> larger = v2._adj; + v2._adj = null; + + // Union lrgs. Swaps again, based on small lrg + LRG vWin = v1.union(v2); + vWin._adj = larger; + LRG vLose = v1.leader() ? v2 : v1; + + // LRGs below v2len were always in v2, but maybe not in v1. + // LRGs above v2len are in v1 but were not in v2. + + // Walk v2's neighbors, replacing vLose with vWin. + if( larger != null ) + for( LRG vn : larger ) { + int idx = vn._adj.find(vLose); + if( idx != -1 ) + vn._adj.del(idx); + if( vn._adj.find(vWin) == -1 ) + vn._adj.add(vWin); + } + } else { + + // Since `n` is dying, remove from the LRGS + if( v1. _machDef==n ) v1. _machDef=null; + if( v1. _machUse==n ) v1. _machUse=null; + if( v1._splitDef==n ) v1._splitDef=null; + if( v1._splitUse==n ) v1._splitUse=null; + } + + // Remove junk split + n.removeSplit(); + j--; + } + } + + if( progress ) + alloc.unify(); + + return true; + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index a1294890..86cbfe97 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -4,11 +4,14 @@ import com.seaofnodes.simple.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.print.*; import com.seaofnodes.simple.type.*; +import java.io.IOException; import java.util.BitSet; import java.util.HashMap; import java.util.IdentityHashMap; +@SuppressWarnings("unchecked") public class CodeGen { + public static final String PORTS = "com.seaofnodes.simple.node.cpus"; // Last created CodeGen as a global; used all over to avoid passing about a // "context". public static CodeGen CODE; @@ -17,11 +20,13 @@ public class CodeGen { Parse, // Parse ASCII text into Sea-of-Nodes IR Opto, // Run ideal optimizations TypeCheck, // Last check for bad programs + LoopTree, // Build a loop tree; break infinite loops InstSelect, // Convert to target hardware nodes Schedule, // Global schedule (code motion) nodes LocalSched, // Local schedule RegAlloc, // Register allocation Encoding, // Encoding + Export, // Export } public Phase _phase; @@ -46,6 +51,27 @@ public class CodeGen { } + // All passes up to Phase, except ELF + public CodeGen driver( Phase phase ) { return driver(phase,null,null); } + public CodeGen driver( Phase phase, String cpu, String callingConv ) { + if( _phase==null ) parse(); + if( _phase.ordinal() < phase.ordinal() ) opto(); + if( _phase.ordinal() < phase.ordinal() ) typeCheck(); + if( _phase.ordinal() < phase.ordinal() ) loopTree(); + if( _phase.ordinal() < phase.ordinal() && cpu != null ) instSelect(cpu,callingConv); + if( _phase.ordinal() < phase.ordinal() ) GCM(); + if( _phase.ordinal() < phase.ordinal() ) localSched(); + if( _phase.ordinal() < phase.ordinal() ) regAlloc(); + if( _phase.ordinal() < phase.ordinal() ) encode(); + return this; + } + + // Run all the phases through final ELF emission + public CodeGen driver( String cpu, String callingConv, String obj ) throws IOException { + return driver(Phase.Encoding,cpu,callingConv).exportELF(obj); + } + + // --------------------------- /** * A counter, for unique node id generation. Starting with value 1, to @@ -154,7 +180,7 @@ public class CodeGen { // --------------------------- // Last check for bad programs - int _tTypeCheck; + public int _tTypeCheck; public CodeGen typeCheck() { // Demand phase Opto for cleaning up dead control flow at least, // required for the following GCM. @@ -169,17 +195,42 @@ public class CodeGen { return this; } + // --------------------------- + // Build the loop tree; break never-exit loops + public int _tLoopTree; + public CodeGen loopTree() { + assert _phase.ordinal() <= Phase.TypeCheck.ordinal(); + _phase = Phase.LoopTree; + long t0 = System.currentTimeMillis(); + // Build the loop tree, fix never-exit loops + _start.buildLoopTree(_stop); + _tLoopTree = (int)(System.currentTimeMillis() - t0); + return this; + } // --------------------------- // Code generation CPU target public Machine _mach; - // + // Chosen calling convention (usually either Win64 or SystemV) public String _callingConv; + // Callee save registers + public RegMask _callerSave; + + // All returns have the following inputs: + // 0 - ctrl + // 1 - memory + // 2 - varies with returning GPR,FPR + // 3 - RPC + // 4+- Caller save registers + public RegMask[] _retMasks; + // Return Program Counter + public RegMask _rpcMask; // Convert to target hardware nodes public int _tInsSel; - public CodeGen instSelect( String base, String cpu, String callingConv ) { - assert _phase.ordinal() <= Phase.TypeCheck.ordinal(); + public CodeGen instSelect( String cpu, String callingConv ) { return instSelect(cpu,callingConv,PORTS); } + public CodeGen instSelect( String cpu, String callingConv, String base ) { + assert _phase.ordinal() == Phase.LoopTree.ordinal(); _phase = Phase.InstSelect; _callingConv = callingConv; @@ -188,9 +239,30 @@ public class CodeGen { // Look for CPU in fixed named place: // com.seaofnodes.simple.node.cpus."cpu"."cpu.class" String clzFile = base+"."+cpu+"."+cpu; - try { _mach = ((Class<Machine>) Class.forName( clzFile )).getDeclaredConstructor().newInstance(); } + try { _mach = ((Class<Machine>) Class.forName( clzFile )).getDeclaredConstructor(new Class[]{CodeGen.class}).newInstance(this); } catch( Exception e ) { throw new RuntimeException(e); } + // Build global copies of common register masks. + long callerSave = _mach.callerSave(); + long neverSave = _mach. neverSave(); + int maxReg = Math.min(64,_mach.regs().length); + assert maxReg>=64 || (-1L << maxReg & callerSave)==0; // No stack slots in callerSave + _callerSave = new RegMask(callerSave); + + // Build a Return RegMask array. All returns have the following inputs: + // 0 - ctrl + // 1 - memory + // 2 - varies with returning GPR,FPR + // 3 - RPC + // 4+- Caller save registers + _retMasks = new RegMask[(maxReg-_callerSave.size()-Long.bitCount( neverSave ))+4]; + for( int reg=0, i=4; reg<maxReg; reg++ ) + if( !_callerSave.test(reg) && ((1L<<reg)&neverSave)==0 ) + _retMasks[i++] = new RegMask(reg); + _rpcMask = new RegMask(_mach.rpc()); + _retMasks[3] = _rpcMask; + + // Convert to machine ops long t0 = System.currentTimeMillis(); _uid = 1; // All new machine nodes reset numbering @@ -226,7 +298,7 @@ public class CodeGen { for( int i=0; i < x.nIns(); i++ ) x._inputs.set(i, _instSelect(x.in(i),map) ); if( x instanceof MachNode mach ) - mach.postSelect(); // Post selection action + mach.postSelect(this); // Post selection action // Updates forward edges only. n._outputs.clear(); @@ -246,8 +318,8 @@ public class CodeGen { // --------------------------- - // Control Flow Graph in RPO order. - int _tGCM; + // Control Flow Graph in Reverse Post Order. + public int _tGCM; public Ary<CFGNode> _cfg = new Ary<>(CFGNode.class); // Global schedule (code motion) nodes @@ -257,8 +329,6 @@ public class CodeGen { _phase = Phase.Schedule; long t0 = System.currentTimeMillis(); - // Build the loop tree, fix never-exit loops - _start.buildLoopTree(_stop); GlobalCodeMotion.buildCFG(this); _tGCM = (int)(System.currentTimeMillis() - t0); if( show ) @@ -268,7 +338,7 @@ public class CodeGen { // --------------------------- // Local (basic block) scheduler phase, a classic list scheduler - int _tLocal; + public int _tLocal; public CodeGen localSched() { assert _phase == Phase.Schedule; _phase = Phase.LocalSched; @@ -281,7 +351,7 @@ public class CodeGen { // --------------------------- // Register Allocation - int _tRegAlloc; + public int _tRegAlloc; public RegAlloc _regAlloc; public CodeGen regAlloc() { assert _phase == Phase.LocalSched; @@ -292,31 +362,46 @@ public class CodeGen { _tRegAlloc = (int)(System.currentTimeMillis() - t0); return this; } - public String reg(Node n) { + + // Human readable register name + public String reg(Node n) { return reg(n,null); } + public String reg(Node n, FunNode fun) { if( _phase.ordinal() >= Phase.RegAlloc.ordinal() ) { - String s = _regAlloc.reg(n); + String s = _regAlloc.reg(n,fun); if( s!=null ) return s; } return "N"+ n._nid; } + // --------------------------- // Encoding - int _tEncode; + public int _tEncode; + public Encoding _encoding; // Encoding object + public void preEncode() { } // overridden by alternative ports public CodeGen encode() { assert _phase == Phase.RegAlloc; _phase = Phase.Encoding; long t0 = System.currentTimeMillis(); + _encoding = new Encoding(this); + preEncode(); + _encoding.encode(); + _tEncode = (int)(System.currentTimeMillis() - t0); + return this; + } - - //_tEncode = (int)(System.currentTimeMillis() - t0); - //throw Utils.TODO(); + // --------------------------- + // Exporting to external formats + public CodeGen exportELF(String fname) throws IOException { + assert _phase == Phase.Encoding; + _phase = Phase.Export; + if( fname == null ) new LinkMem(this).link(); // In memory patching + else new ElfFile(this).export(fname); // External ELF file return this; } - // Encoded binary, no relocation info - public byte[] binary() { throw Utils.TODO(); } // --------------------------- + public boolean _asmLittle=true; SB asm(SB sb) { return ASMPrinter.print(sb,this); } public String asm() { return asm(new SB()).toString(); } @@ -335,4 +420,44 @@ public class CodeGen { // Debugging helper public Node f(int idx) { return _stop.find(idx); } + + + String printCFG() { + if( _cfg==null ) return "no CFG"; + SB sb = new SB(); + for( CFGNode cfg : _cfg ) + IRPrinter.printLine(cfg,sb); + return sb.toString(); + } + + public static void print_as_hex(Encoding enc) { + for (byte b : enc._bits.toByteArray()) { + System.out.print(String.format("%02X", b)); + } + System.out.println(); + } + + public void print_as_hex() { + for (byte b : _encoding._bits.toByteArray()) { + System.out.print(String.format("%02X", b)); + } + System.out.println(); + } + + //// Debug purposes for now +// public CodeGen printENCODING() { +// ByteArrayOutputStream outputStream = new ByteArrayOutputStream(); +// +// for(Node bb : CodeGen.CODE._cfg) { +// for(Node n: bb.outs()) { +// if(n instanceof MachNode) { +// ((MachNode) n).encoding(E); +// } +// } +// } +// +// print_as_hex(outputStream); +// // Get the raw bytes from the output stream +// return this; +// } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfExpr.java b/src/main/java/com/seaofnodes/simple/codegen/ElfExpr.java new file mode 100644 index 00000000..9d9b8a1c --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfExpr.java @@ -0,0 +1,87 @@ +package com.seaofnodes.simple.codegen; + +import java.io.FileOutputStream; +import java.io.IOException; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; + +public class ElfExpr { + public static void main(String[] args) { + try (FileOutputStream fos = new FileOutputStream("hello.o")) { + ByteBuffer buffer = ByteBuffer.allocate(512); + buffer.order(ByteOrder.LITTLE_ENDIAN); + + // === ELF HEADER (64 bytes) === + buffer.put(new byte[]{ + 0x7F, 'E', 'L', 'F', // ELF Magic + 2, 1, 1, 0, // 64-bit, little-endian, version + 0, 0, 0, 0, 0, 0, 0, // ABI padding + 2, 0, // Type: Executable (ET_EXEC) + 0x3E, 0x00, // Machine: x86-64 + 1, 0, 0, 0, // ELF version + 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // Entry point + 0, 0, 0, 0, 0, 0, 0, 0, // Program header offset + 64, 0, 0, 0, 0, 0, 0, 0, // Section header offset + 0, 0, 0, 0, // Flags + 64, 0, // ELF header size + 0, 0, // Program header entry size + 0, 0, // Number of program header entries + 40, 0, // Section header entry size + 2, 0, // Number of section headers + 1, 0 // Section header string table index + }); + + // === .TEXT SECTION (Executable Code) === + byte[] textSection = { + // sys_write (write(1, message, 13)) + (byte) 0x48, (byte) 0xC7, (byte) 0xC0, 0x01, 0x00, 0x00, 0x00, // mov rax, 1 + (byte) 0x48, (byte) 0xC7, (byte) 0xC7, 0x01, 0x00, 0x00, 0x00, // mov rdi, 1 + (byte) 0x48, (byte) 0xBE, (byte)0x90, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // mov rsi, message + (byte) 0x48, (byte) 0xC7, (byte) 0xC2, 0x0D, 0x00, 0x00, 0x00, // mov rdx, 13 + (byte) 0x0F, (byte) 0x05, // syscall + + // sys_exit (exit(0)) + (byte) 0x48, (byte) 0xC7, (byte) 0xC0, 0x3C, 0x00, 0x00, 0x00, // mov rax, 60 + (byte) 0x48, (byte) 0x31, (byte) 0xFF, // xor rdi, rdi + (byte) 0x0F, (byte) 0x05 // syscall + }; + + // Append section data + buffer.position(256); + buffer.put(textSection); + + // === STRING MESSAGE (.data Section) === + byte[] message = "Hello, World!\n".getBytes(); + buffer.position(400); + buffer.put(message); + + // === SECTION HEADERS === + buffer.position(64); + + // Null Section (required as first entry) + buffer.put(new byte[40]); + + // .text Section + buffer.putInt(1); // Offset in section string table (".text") + buffer.putInt(1); // Type: SHT_PROGBITS + buffer.putLong(6); // Flags: Executable | Allocatable + buffer.putLong(0); // Virtual address + buffer.putLong(256); // Offset to section data + buffer.putLong(textSection.length); // Section size + buffer.putInt(0); // Link + buffer.putInt(0); // Info + buffer.putLong(4); // Address alignment + buffer.putLong(0); // No extra entries + + // === SECTION HEADER STRING TABLE === + buffer.position(500); + buffer.put(".text".getBytes()); + buffer.put((byte) 0x00); // Null terminator + + fos.write(buffer.array()); + System.out.println("ELF object file 'hello.o' created."); + } catch (IOException e) { + e.printStackTrace(); + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java new file mode 100644 index 00000000..746ecfed --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java @@ -0,0 +1,381 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.Encoding.BAOS; +import java.io.*; +import java.nio.ByteBuffer; +import java.nio.ByteOrder; +import java.util.HashMap; +import java.util.Map; + +public class ElfFile { + + final CodeGen _code; + Ary<Section> _sections = new Ary<>(Section.class); + + ElfFile( CodeGen code ) { _code = code; } + + public static int writeCString(DataSection strtab, String name) { + // place name in the string table + int pos = strtab._contents.size(); + byte[] name_bytes = name.getBytes(); + strtab._contents.write(name_bytes, 0, name_bytes.length); + // the strings are null terminated + strtab._contents.write(0); + return pos; + } + + public static void write4( ByteArrayOutputStream bits, int op ) { + bits.write(op ); + bits.write(op>> 8); + bits.write(op>>16); + bits.write(op>>24); + } + public static void write8( ByteArrayOutputStream bits, long i64 ) { + write4(bits, (int) i64 ); + write4(bits, (int)(i64>>32)); + } + + public static final int SYMBOL_SIZE = 4+1+1+2+8+8; + + public static final int SYM_BIND_LOCAL = 0; + public static final int SYM_BIND_GLOBAL = 1; + public static final int SYM_BIND_WEAK = 2; + + public static final int SYM_TYPE_NOTYPE = 0; + public static final int SYM_TYPE_OBJECT = 1; + public static final int SYM_TYPE_FUNC = 2; + public static final int SYM_TYPE_SECTION = 3; + + public static class Symbol { + String _name; + int _name_pos; + + // index in the symbol table + int _index; + + // which section is it in + int _parent; + + // depends on the symbol type + // TODO + int _value, _size; + + // top 4bits are the "bind", bottom 4 are "type" + int _info; + + // bind 1011 + // 00001111 + // 10110000 + + Symbol(String name, int parent, int bind, int type) { + _name = name; + _parent = parent; + _info = (bind << 4) | (type & 0xF); + } + + void writeHeader(ByteBuffer out) { + out.putInt(_name_pos); // name + out.put((byte) _info); // info + // default visibility + out.put((byte) 0); // other + out.putShort((short) _parent); // shndx + out.putLong(_value); // value + out.putLong(_size); // size + } + } + + public static final int SHF_WRITE = 1; + public static final int SHF_ALLOC = 2; + public static final int SHF_EXECINSTR = 4; + public static final int SHF_STRINGS = 32; + public static final int SHF_INFO_LINK = 64; + + public static final int SECTION_HDR_SIZE = 64; + abstract public static class Section { + String _name; + int _index; + + int _type, _flags; + int _link, _info; + + // where's the name in the string table + int _name_pos; + int _file_offset; + + Section(String name, int type) { + _name = name; + _type = type; + } + + void writeHeader(ByteBuffer out) { + out.putInt(_name_pos); // name + out.putInt(_type); // type + out.putLong(_flags); // flags + out.putLong(0); // addr + out.putLong(_file_offset); // offset + out.putLong(size()); // size + out.putInt(_link); // link + out.putInt(_info); // info + out.putLong(16); // addralign + if (_type == 2) { + out.putLong(SYMBOL_SIZE);// entsize + } else if (_type == 4) { + out.putLong(24); // entsize + } else { + out.putLong(0); // entsize + } + } + + abstract void write(ByteBuffer out); + abstract int size(); + } + + public static class SymbolSection extends Section { + Ary<Symbol> _symbols = new Ary<>(Symbol.class); + Ary<Symbol> _loc = new Ary<>(Symbol.class); + + SymbolSection(String name, int type) { + super(name, type); + } + + @Override + void writeHeader(ByteBuffer out) { + // points to string table section + _link = 1; + + // number of non-local symbols + _info = _loc.len() + 1; + + super.writeHeader(out); + } + + void push(Symbol s) { + if ((s._info >> 4) != SYM_BIND_LOCAL) { + _symbols.push(s); + } else { + _loc.push(s); + } + } + + @Override + void write(ByteBuffer out) { + // Index 0 both designates the first entry in the table and serves as the undefined symbol index + for( int i = 0; i < SYMBOL_SIZE/4; i++ ) { + out.putInt(0); + } + // index is already set + for( Symbol s : _loc ) { + s.writeHeader(out); + } + for( Symbol s : _symbols ) { + s.writeHeader(out); + } + } + + @Override + int size() { + return (1 + _symbols.len() + _loc.len()) * SYMBOL_SIZE; + } + } + + public static class DataSection extends Section { + ByteArrayOutputStream _contents; + + DataSection(String name, int type) { + super(name, type); + _contents = new ByteArrayOutputStream(); + } + + DataSection(String name, int type, ByteArrayOutputStream contents) { + super(name, type); + _contents = contents; + } + + @Override + void write(ByteBuffer out) { + out.put(_contents.toByteArray()); + } + + @Override + int size() { + return _contents.size(); + } + } + + private void pushSection(Section s) { + _sections.push(s); + // ELF is effectively "1-based", due to the NULL section + s._index = _sections._len; + } + + /* creates function and stores where it starts*/ + private final HashMap<TypeFunPtr,Symbol> _funcs = new HashMap<>(); + private void encodeFunctions(SymbolSection symbols, DataSection text) { + for( int i=0; i<_code._cfg._len; i++ ) { + if( !(_code._cfg.at(i) instanceof FunNode fun) ) continue; + // skip until the function ends + while( !(_code._cfg.at(i) instanceof ReturnNode ret) ) + i++; + int end = _code._encoding._opStart[ret._nid] + _code._encoding._opLen[ret._nid]; + + Symbol func = new Symbol(fun._name, text._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); + func._value = _code._encoding._opStart[fun._nid]; + func._size = end - func._value; + symbols.push(func); + _funcs.put(fun.sig(), func); + } + } + + public void export(String fname) throws IOException { + DataSection strtab = new DataSection(".strtab", 3 /* SHT_SYMTAB */); + // first byte is reserved for an empty string + strtab._contents.write(0); + pushSection(strtab); + + // place all the symbols + SymbolSection symbols = new SymbolSection(".symtab", 2 /* SHT_STRTAB */); + pushSection(symbols); + + // zero flag by default + // we've already constructed this entire section in the encoding phase + DataSection text = new DataSection(".text", 1 /* SHT_PROGBITS */, _code._encoding._bits); + text._flags = SHF_ALLOC | SHF_WRITE | SHF_EXECINSTR; + pushSection(text); + + // Build and write constant pool + BAOS cpool = new BAOS(); + Encoding enc = _code._encoding; + enc.writeConstantPool(cpool,false); + DataSection rdata = new DataSection(".rodata", 1 /* SHT_PROGBITS */, cpool); + rdata._flags = SHF_ALLOC; + pushSection(rdata); + + // populate function symbols + encodeFunctions(symbols, text); + + int idx = 1; + for( Section s : _sections ) { + Symbol sym = new Symbol(s._name, idx++, SYM_BIND_LOCAL, SYM_TYPE_SECTION); + // we can reuse the same name pos from the actual section + sym._name_pos = s._name_pos; + sym._size = s.size(); + symbols.push(sym); + } + + // calculate local index + int num = 1; + for( Symbol s : symbols._loc ) + s._index = num++; + // extra space for .rela.text + int start_global = num+1; // Add one to skip the final .rela.text local symbol + for( Symbol a: symbols._symbols ) + a._index = start_global++; + int bigConIdx = start_global; + start_global += enc._bigCons.size(); + + // create .text relocations + DataSection text_rela = new DataSection(".rela.text", 4 /* SHT_RELA */); + for( Node n : enc._externals.keySet()) { + int nid = n._nid; + String extern = enc._externals.get(n); + + Symbol sym = new Symbol(extern, 0, SYM_BIND_GLOBAL, SYM_TYPE_NOTYPE); + sym._index = start_global++; + symbols.push(sym); + + int offset = enc._opStart[nid] + enc._opLen[nid] - 4; + + // u64 offset + write8(text_rela._contents, offset); + // u64 info + write8(text_rela._contents, ((long)sym._index << 32L) | 4L /* PLT32 */); + // i64 addend + write8(text_rela._contents, -4); + } + + // Write relocations for the constant pool + for( Encoding.Relo relo : enc._bigCons.values() ) { + Symbol glob = new Symbol("GLOB$"+bigConIdx, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); + glob._value = relo._target; + glob._size = 1 << relo._t.log_size(); + glob._index = bigConIdx++; + symbols.push(glob); + write8(text_rela._contents, relo._opStart+relo._off); + write8(text_rela._contents, ((long)glob._index << 32L) | relo._elf ); + write8(text_rela._contents, -4); + } + + text_rela._flags = SHF_INFO_LINK; + text_rela._link = 2; + text_rela._info = text._index; + pushSection(text_rela); + + Symbol sym = new Symbol(text_rela._name, num++, SYM_BIND_LOCAL, SYM_TYPE_SECTION); + sym._name_pos = text_rela._name_pos; + sym._size = text_rela.size(); + symbols.push(sym); + + // populate string table + for( Section s : _sections ) { s._name_pos = writeCString(strtab, s._name); } + for( Symbol s : symbols._symbols ) { s._name_pos = writeCString(strtab, s._name); } + for( Symbol s : symbols._loc ) { s._name_pos = writeCString(strtab, s._name); } + + int size = 64; // ELF header + // size of all section data + for( Section s : _sections ) { + s._file_offset = size; + size += s.size(); + } + // headers go at the very end + int shdr_offset = size; + // there's a "null" section at the start of the section headers + size += SECTION_HDR_SIZE*(1 + _sections.len()); + + // System.out.printf("Hello %d, %d, %s\n", size, shdr_offset); + ByteBuffer out = ByteBuffer.allocate(size); + out.order(ByteOrder.LITTLE_ENDIAN); + + // ELF header + out.put(new byte[]{ 0x7F, 'E', 'L', 'F', 2, 1, 1, 0 }); + out.put(new byte[8]); + out.putShort((short)1 /* ET_REL */); // type + out.putShort((short)62 /* AMD64 */); // machine + out.putInt(1); // version + out.putLong(0); // entry + out.putLong(0); // phoff + out.putLong(shdr_offset); // shoff + out.putInt(0); // flags + out.putShort((short)64); // ehsize + out.putShort((short)0); // phentsize + out.putShort((short)0); // phnum + out.putShort((short)64); // shentsize + out.putShort((short) (1 + _sections.len())); // shnum + out.putShort((short)1); // shstrndx + + // raw section data + for( Section s : _sections ) { + s.write(out); + } + + // "null" section + for( int i = 0; i < 16; i++ ) { + out.putInt(0); + } + + for( Section s : _sections ) { + s.writeHeader(out); + } + assert out.position() == size; + + File file = new File(fname); + if( file.getParentFile()!=null ) + file.getParentFile().mkdirs(); + BufferedOutputStream bos = new BufferedOutputStream(new FileOutputStream(file)); + bos.write(out.array()); + bos.close(); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java new file mode 100644 index 00000000..d7057839 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -0,0 +1,475 @@ +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.print.IRPrinter; +import com.seaofnodes.simple.type.*; +import java.io.ByteArrayOutputStream; +import java.util.*; + + +/** + * Instruction encodings + * <p> + * 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). + * <p> + * There are also a bunch of generic utilities for managing bits and bytes + * common in all encodings. + */ +public class Encoding { + + // Top-level program graph structure + public final CodeGen _code; + + // Instruction bytes. The registers are encoded already. Relocatable data + // is in a fixed format depending on the kind of relocation. + + // - RIP-relative offsets into the same chunk are just encoded with their + // check relative offsets; no relocation info is required. + + // - Fixed address targets in the same encoding will be correct for a zero + // base; moving the entire encoding requires adding the new base address. + + // - RIP-relative to external chunks have a zero offset; the matching + // relocation info will be used to patch the correct value. + + 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 = new BAOS(); + + public int [] _opStart; // Start of opcodes, by _nid + public byte[] _opLen; // Length of opcodes, by _nid + + // Big Constant relocation info. + public static class Relo { + public final Node _op; + public final Type _t; // Constant type + public final byte _off; // Offset from start of opcode + public final byte _elf; // ELF relocation type, e.g. 2/PC32 + public int _target; // Where constant is finally placede + public int _opStart; // Opcode start + Relo( Node op, Type t, byte off, byte elf ) { + _op=op; _t=t; _off=off; _elf=elf; + } + } + public final HashMap<Node,Relo> _bigCons = new HashMap<>(); + + Encoding( CodeGen code ) { _code = code; } + + // Shortcut to the defining register + public short reg(Node n) { + return _code._regAlloc.regnum(n); + } + + public int read1(int idx) { + byte[] buf = _bits.buf(); + return (buf[idx]&0xFF); + } + public int read2(int idx) { + byte[] buf = _bits.buf(); + return (buf[idx]&0xFF) | (buf[idx+1]&0xFF) <<8; + } + public int read4(int idx) { + byte[] buf = _bits.buf(); + return (buf[idx]&0xFF) | (buf[idx+1]&0xFF) <<8 | (buf[idx+2]&0xFF)<<16 | (buf[idx+3]&0xFF)<<24; + } + public long read8(int idx) { + return (read4(idx) & 0xFFFFFFFFL) | read4(idx+4); + } + + // This buffer is invalid/moving until after all encodings are written + public byte[] bits() { return _bits.buf(); } + + // 4 byte little-endian write + public void patch4( int idx, int val ) { + byte[] buf = _bits.buf(); + buf[idx ] = (byte)(val ); + buf[idx+1] = (byte)(val>> 8); + buf[idx+2] = (byte)(val>>16); + buf[idx+3] = (byte)(val>>24); + } + + static void padN(int n, BAOS bits) { + while( (bits.size()+n-1 & -n) > bits.size() ) + bits.write(0); + } + + // Convenience for writing log-N + static void addN( int log, Type t, BAOS bits ) { + long x = t instanceof TypeInteger ti + ? ti.value() + : log==3 + ? Double.doubleToRawLongBits( ((TypeFloat)t).value()) + : Float.floatToRawIntBits((float)((TypeFloat)t).value()); + addN(log,x,bits); + } + static void addN( int log, long x, BAOS bits ) { + for( int i=0; i < 1<<log; i++ ) { + bits.write((int)x); + x >>= 8; + } + } + + public Encoding add1( int op ) { addN(0,op,_bits); return this; } + public Encoding add2( int op ) { addN(1,op,_bits); return this; } + public Encoding add4( int op ) { addN(2,op,_bits); return this; } + public Encoding add8(long op ) { addN(3,op,_bits); return this; } + + + // Nodes need "relocation" patching; things done after code is placed. + // Record src and dst Nodes. + private final HashMap<Node,CFGNode> _internals = new HashMap<>(); + // Source is a Call, destination in the Fun. + public Encoding relo( CallNode call ) { + _internals.put(call,_code.link(call.tfp())); + return this; + } + public Encoding relo( ConstantNode con ) { + TypeFunPtr tfp = (TypeFunPtr)con._con; + _internals.put(con,_code.link(tfp)); + return this; + } + public void jump( CFGNode jmp, CFGNode dst ) { + _internals.put(jmp,dst.uctrlSkipEmpty()); + } + + + final HashMap<Node,String> _externals = new HashMap<>(); + public Encoding external( Node call, String extern ) { + _externals.put(call,extern); + return this; + } + + // Store t as a 32/64 bit constant in the code space; generate RIP-relative + // addressing to load it + public void largeConstant( Node relo, Type t, int off, int elf ) { + assert t.isConstant(); + assert (byte)off == off; + assert (byte)elf == elf; + _bigCons.put(relo,new Relo(relo,t,(byte)off,(byte)elf)); + } + + // -------------------------------------------------- + void encode() { + // 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 Reverse Post Order but with more + // restrictions. + basicBlockLayout(); + + // Write encoding bits in order into a big byte array. + // Record opcode start and length. + writeEncodings(); + + // Short-form RIP-relative support: replace long encodings with short + // encodings and compact the code, changing all the offsets. + compactShortForm(); + + // Patch RIP-relative and local encodings now. + patchLocalRelocations(); + } + + // -------------------------------------------------- + // 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 Reverse Post Order but with more restrictions. + private void basicBlockLayout() { + IdentityHashMap<LoopNode,Ary<CFGNode>> rpos = new IdentityHashMap<>(); + Ary<CFGNode> rpo = new Ary<>(CFGNode.class); + rpos.put(_code._start.loop(),rpo); + BitSet visit = _code.visit(); + //IdentityHashMap<CFGNode,LoopNode> looptail = new IdentityHashMap<>(); + rpo.add(_code._stop); + for( Node n : _code._start._outputs ) + if( n instanceof FunNode fun ) { + int x = rpo._len; + //_rpo_cfg2(fun, visit, rpo, looptail); + _rpo_cfg(fun, visit, rpos ); + assert rpo.at(x) instanceof ReturnNode; + } + 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 + } + + + private void _rpo_cfg(CFGNode bb, BitSet visit, IdentityHashMap<LoopNode,Ary<CFGNode>> rpos ) { + if( bb==null || visit.get(bb._nid) ) return; + visit.set(bb._nid); + CFGNode next = bb.uctrl(); + + // Loops run an inner "rpo_cfg", then append the entire loop body in + // place. This keeps loop bodies completely contained, although if + // Some Day Later we have real profile data we ought to arrange the + // branch orderings based on frequency. + if( bb instanceof LoopNode loop ) { + Ary<CFGNode> body = new Ary<>(CFGNode.class); // Private RPO for the loop + rpos.put(loop.loop(),body); // Find it via loop tree + _rpo_cfg(next,visit,rpos); // RPO the loop + body.add(loop); // Include loop last (first in RPO) + Ary<CFGNode> outer = rpos.get(loop.cfg(1).loop()); + outer.addAll(body); // Append to original CFG + return; + } + + // IfNodes visit 2 sides, and may choose to reorder them in the RPO + if( bb instanceof IfNode iff ) { + // Pick out the T/F projections + CProjNode t = iff.cproj(0); + CProjNode f = iff.cproj(1); + // Invert the branch or not + if( shouldInvert(t,f,iff.loopDepth()) ) { + iff.negate(); + t.invert(); + f.invert(); + CProjNode tmp=f; f=t; t=tmp; // Swap t/f + } + + // Whichever side is visited first becomes last in the RPO. With + // no loops, visit the False side last (so True side first) so that + // 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. + _rpo_cfg(t,visit,rpos); // True side first + next = f; // False side last + } + + // If the *next* BB has already been visited, and we are not already a + // jump, we may need an unconditional forwards jump here + Ary<CFGNode> rpo = rpos.get(bb.loop()); + if( next!=null && visit.get(next._nid) && !(bb instanceof IfNode) ) { + boolean needJump = next instanceof LoopNode + // Empty blocks from an IF will invert the IF and backwards + // branch to the loop head. If not empty, or not an IF + // will need a jump. + ? (bb.nOuts()>1 || !(bb.cfg0() instanceof IfNode) ) + // Forwards jump. If all the blocks, in RPO order, to our + // target are empty, we will fall in and not need a jump. + : !backwardsEmptyScan(rpo,next); + if( needJump ) { + CFGNode jmp = _code._mach.jump(); + jmp._ltree = bb._ltree; + jmp.setDefX(0,bb); + next.setDef(next._inputs.find(bb),jmp); + rpo.add(jmp); + } + } + + _rpo_cfg(next,visit,rpos); + rpo.add(bb); + } + + // Should this test be inverted? + private static boolean shouldInvert(CFGNode t, CFGNode f, int bld) { + int tld = t.loopDepth(), fld = f.loopDepth(); + // These next two are symmetric and can happen in any order; if `tld < + // bld` is true, the `fld < bld` must be false, or else both directions + // exit the loop... and the IF test would not be in the loop. + + // true to exit a loop usually (and false falls into Yet Another Loop + // Block), invert if false is taking an empty backwards branch. + if( tld < bld ) return forwardsEmptyScan(f,bld); + // false to exit a loop, normally invert to true (except empty back) + if( fld < bld ) return !forwardsEmptyScan(t,bld); + + // Not exiting the loop; staying at this depth (or going deeper loop). + + // Jump/true to an empty backwards block + if( forwardsEmptyScan(t,bld) ) return false; + if( forwardsEmptyScan(f,bld) ) return true ; + + // Fall/false into a full block, Jump/true to an empty block. + if( f.nOuts()>1 && t.nOuts()==1 ) return false; + if( t.nOuts()>1 && f.nOuts()==1 ) return true ; + // Everything else equal, use pre-order + return t._pre > f._pre; + } + + // Do we continue forwards from 'c' to the Loop back edge, without doing + // anything else? Then this branch can directly jump to the loop head. + private static boolean forwardsEmptyScan( CFGNode c, int bld ) { + if( c.nOuts()!=1 || c.loopDepth()!=bld ) return false; + return c.uctrl() instanceof RegionNode cfg && + (cfg instanceof LoopNode || forwardsEmptyScan(cfg,bld)); + } + + // Is the CFG from "next" to the end empty? This means jumping to "next" + // will naturally fall into the end. + private static boolean backwardsEmptyScan(Ary<CFGNode> rpo, CFGNode next) { + for( int i=rpo._len-1; rpo.at(i)!=next; i-- ) + if( rpo.at(i).nOuts()!=1 ) + return false; + return true; + } + + // -------------------------------------------------- + // Write encoding bits in order into a big byte array. + // Record opcode start and length. + public FunNode _fun; // Currently encoding function + private void writeEncodings() { + _opStart= new int [_code.UID()]; + _opLen = new byte[_code.UID()]; + for( CFGNode bb : _code._cfg ) { + if( !(bb instanceof MachNode mach0) ) + _opStart[bb._nid] = _bits.size(); + else if( bb instanceof FunNode fun ) { + padN(16,_bits); + _fun = fun; // Currently encoding function + _opStart[bb._nid] = _bits.size(); + mach0.encoding( this ); + _opLen[bb._nid] = (byte) (_bits.size() - _opStart[bb._nid]); + } + for( Node n : bb._outputs ) { + if( n instanceof MachNode mach && !(n instanceof FunNode) ) { + _opStart[n._nid] = _bits.size(); + mach.encoding( this ); + _opLen[n._nid] = (byte) (_bits.size() - _opStart[n._nid]); + } + } + } + padN(16,_bits); + } + + // -------------------------------------------------- + // Short-form RIP-relative support: replace short encodings with long + // encodings and expand the code, changing all the offsets. + private void compactShortForm() { + int len = _code._cfg._len; + int[] oldStarts = new int[len]; + for( int i=0; i<len; i++ ) + oldStarts[i] = _opStart[_code._cfg.at(i)._nid]; + + // TODO: Rewrite this algo to use the small "_jmps" list of just the + // jumps instead of walking all blocks. + // TODO2: Allow short encodings on non-jumps. This algo doesn't + // really care jumps vs other rip-relative things. + + // Check the size of short jumps, adjust the block starts for a whole + // pass over all blocks. If some jumps go long, they might stretch the + // distance for other jumps, so another pass is needed. + int slide = -1; + while( slide != 0) { // While no fails + slide = 0; + for( int i=0; i<len; i++ ) { + CFGNode bb = _code._cfg.at(i); + // Functions pad to align 16 + if( bb instanceof FunNode ) { + int newStart = _opStart[bb._nid]+slide; + slide += (newStart+15 & -16)-newStart; + } + _opStart[bb._nid] += slide; + // Slide down all other (non-CFG) ops in the block + for( Node n : bb._outputs ) + if( n instanceof MachNode && !(n instanceof CFGNode) ) + _opStart[n._nid] += slide; + if( bb instanceof RIPRelSize riprel ) { + CFGNode target = (bb instanceof IfNode iff ? iff.cproj(0) : (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 + int delta = _opStart[target._nid] - _opStart[bb._nid]; + byte opLen = riprel.encSize(delta); + // Recorded size is smaller than the current size? + if( _opLen[bb._nid] < opLen ) { + // Start sliding the code down; record slide amount and new size + slide += opLen - _opLen[bb._nid]; + _opLen[bb._nid] = opLen; + } + } + } + } + + + // Copy/slide the bits to make space for all the longer branches + int grow = _opStart[_code._cfg.at(len-1)._nid] - oldStarts[len-1]; + if( grow > 0 ) { // If no short-form ops, nothing to do here + 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); + } + } + + + // -------------------------------------------------- + // Patch local encodings now + void patchLocalRelocations() { + // Walk the local code-address relocations + for( Node src : _internals.keySet() ) { + int start = _opStart[src._nid]; + Node dst = _internals.get(src); + int target = _opStart[dst._nid]; + ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start); + } + } + + // -------------------------------------------------- + // Write the constant pool into the BAOS and optionally patch locally + void writeConstantPool( BAOS bits, boolean patch ) { + padN(16,bits); + + HashMap<Type,Integer> targets = new HashMap<>(); + + // By log size + for( int log = 3; log >= 0; log-- ) { + // Write the 8-byte constants + for( Node op : _bigCons.keySet() ) { + Relo relo = _bigCons.get(op); + if( relo._t.log_size()==log ) { + // Map from relo to constant start and patch + Integer target = targets.get(relo._t); + if( target==null ) { + targets.put(relo._t,target = bits.size()); + // Put constant into code space. + if( relo._t instanceof TypeTuple tt ) // Constant tuples put all entries + for( Type tx : tt._types ) + addN(log,tx,bits); + else + addN(log,relo._t,bits); + } + relo._target = target; + relo._opStart= _opStart[op._nid]; + // Go ahead and locally patch in-memory + if( patch ) + ((RIPRelSize)op).patch(this, relo._opStart, _opLen[op._nid], relo._target - relo._opStart); + } + } + } + } + + + // A series of libc/external calls that Simple can link against in a JIT. + // Since no runtime in the JVM process, using magic numbers for the CPU + // emulators to pick up on. + public static int SENTINAL_CALLOC = -4; + + void patchGlobalRelocations() { + for( Node src : _externals.keySet() ) { + int start = _opStart[src._nid]; + String dst = _externals.get(src); + int target = switch( dst ) { + case "calloc" -> SENTINAL_CALLOC; + default -> throw Utils.TODO(); + }; + ((RIPRelSize)src).patch(this, start, _opLen[src._nid], target - start); + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 11c2b061..e904dc66 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -24,7 +24,7 @@ public abstract class GlobalCodeMotion { schedEarly(code); // Break up shared global constants by functions - breakUpGlobalConstants(code); + breakUpGlobalConstants(code._start); code._visit.clear(); schedLate (code); @@ -45,23 +45,28 @@ public abstract class GlobalCodeMotion { } // Break up shared global constants by functions - private static void breakUpGlobalConstants( CodeGen code ) { + private static void breakUpGlobalConstants( Node start ) { // For all global constants - for( int i=0; i< code._start.nOuts(); i++ ) { - Node con = code._start.out(i); + for( int i=0; i< start.nOuts(); i++ ) { + Node con = start.out(i); if( con instanceof MachNode mach && mach.isClone() ) { + breakUpGlobalConstants(con); // While constant has users in different functions while( true ) { // Find a function user, and another function FunNode fun = null; boolean done=true; for( Node use : con.outs() ) { - FunNode fun2 = use.cfg0().fun(); + FunNode fun2 = use instanceof ReturnNode ret ? ret.fun() : use.cfg0().fun(); if( fun==null || fun==fun2 ) fun=fun2; else { done=false; break; } } // Single function user, so this constant is not shared - if( done ) { i--; con.setDef(0,fun); break; } + if( done ) { + if( con.in(0)==start ) i--; + con.setDef(0,fun); + break; + } // Move function users to a private constant Node con2 = mach.copy(); // Private constant clone con2._inputs.set(0,null); // Preserve edge invariants from clone @@ -155,7 +160,7 @@ public abstract class GlobalCodeMotion { continue outer; // Nope, await all uses done // Loads need their memory inputs' uses also done - if( n instanceof LoadNode ld ) + if( n instanceof MemOpNode ld && ld._isLoad ) for( Node memuse : ld.mem()._outputs ) if( late[memuse._nid]==null && // New makes new memory, never crushes load memory @@ -175,8 +180,8 @@ public abstract class GlobalCodeMotion { if( def!=null && late[def._nid]==null ) { work.push(def); // if the def has a load use, maybe the load can fire - for( Node ld : def._outputs ) - if( ld instanceof LoadNode && late[ld._nid]==null ) + for( Node out : def._outputs ) + if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) work.push(ld); } } @@ -192,7 +197,7 @@ public abstract class GlobalCodeMotion { lca = use_block(n,use, late)._idom(lca,null); // Loads may need anti-dependencies, raising their LCA - if( n instanceof LoadNode load ) + if( n instanceof MemOpNode load && load._isLoad ) lca = find_anti_dep(lca,load,early,late); // Walk up from the LCA to the early, looking for best place. This is @@ -226,10 +231,11 @@ public abstract class GlobalCodeMotion { // Least loop depth first, then largest idepth private static boolean better( CFGNode lca, CFGNode best ) { return lca.loopDepth() < best.loopDepth() || + lca instanceof NeverNode || (lca.idepth() > best.idepth() || best instanceof IfNode); } - private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) { + private static CFGNode find_anti_dep(CFGNode lca, MemOpNode load, CFGNode early, CFGNode[] late) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) @@ -237,10 +243,12 @@ public abstract class GlobalCodeMotion { // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.mem()._outputs ) { switch( mem ) { - case StoreNode st: - assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); - break; + case MemOpNode st: + if( !st._isLoad ) { + assert late[mem._nid] != null; + lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); + } + break; // Loads do not cause anti-deps on other loads case CallNode st: assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); @@ -253,7 +261,6 @@ public abstract class GlobalCodeMotion { lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null); break; case NewNode st: break; - case LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return case MemMergeNode ret: break; // Mem uses now on ScopeMin case NeverNode never: break; @@ -264,16 +271,13 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { - // Walk store blocks "reach" from its scheduled location to its earliest - for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { - // Store and Load overlap, need anti-dependence - if( stblk._anti==load._nid ) { - lca = stblk._idom(lca,null); // Raise Loads LCA - if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, - st.addDef(load); // Add anti-dep as well - return lca; // Cap this stores' anti-dep to here - } + private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { + // Store and Load overlap, need anti-dependence + if( stblk._anti==load._nid ) { + lca = stblk._idom(lca,null); // Raise Loads LCA + if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, + st.addDef(load); // Add anti-dep as well + return lca; // Cap this stores' anti-dep to here } return lca; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 1f3186ff..81955779 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -19,7 +19,7 @@ abstract public class IFG { static final IdentityHashMap<LRG,Node> TMP = new IdentityHashMap<>(); // Inteference Graph: Array of Bitsets - private static final Ary<BitSet> IFG = new Ary<>(BitSet.class); + static final Ary<BitSet> IFG = new Ary<>(BitSet.class); static void resetIFG() { for( BitSet bs : IFG ) if( bs!=null ) bs.clear(); @@ -79,6 +79,8 @@ abstract public class IFG { while( !WORK.isEmpty() ) do_block(round,alloc,WORK.pop()); + if( alloc.success() ) + convert2DAdjacency(alloc); return alloc.success(); } @@ -125,18 +127,18 @@ abstract public class IFG { TMP.remove(lrg); // Kill def } + // Phis use and define the same live range, i.e. these LRGs already + // marked conflicted, no need to mark again if( n instanceof PhiNode ) return; - // A copy does not define a new value, and the src and dst can use the - // same register. Remove the input from TMP/liveout set before - // interfering. - //if( n instanceof MachNode m && m.isSplit() ) - // TMP.remove(alloc.lrg(n.in(1))); // Kill spill-use + + // Kill any killed registers; milli-code routines like New can kill + // will not being a CFG. + if( n instanceof MachNode m ) + kills(alloc,m); // Interfere n with all live if( lrg!=null ) { - if( n instanceof MachNode m ) - kills(alloc,m); // Interfere n with all live for( LRG tlrg : TMP.keySet() ) { assert tlrg.leader(); @@ -148,9 +150,10 @@ abstract public class IFG { // last tlrg register at some point, either tlrg or lrg // must fail. If *n* (a subset of lrg) needs the single // last tlrg register then only tlrg must fail. - if( lrg.size1() && !tlrg.clr(lrg._mask.firstReg()) ) - alloc.fail(tlrg); - else addIFG(lrg,tlrg); // Add interference + if( ((MachNode)n).outregmap().size1() ) { + if( !tlrg.clr(lrg._mask.firstReg()) ) // Clear bit, no interference + alloc.fail(tlrg); // Clearing drives mask to empty + } else addIFG(lrg,tlrg); // Add interference } } @@ -171,7 +174,7 @@ abstract public class IFG { // Look for a must-use single register conflicting with some other must-def. if( n instanceof MachNode m ) { RegMask ni_mask = m.regmap(i); - if( ni_mask.size1() ) { // Must-use single register + if( ni_mask!=null && ni_mask.size1() ) { // Must-use single register // Search all current live for( LRG tlrg : TMP.keySet() ) { assert tlrg.leader(); @@ -207,12 +210,17 @@ abstract public class IFG { // Disallow clone-ables from killing registers. Just fail // them and re-clone closer to target... so no kill. // Special case for Intel XOR used to zero. - if( m.isClone() ) + Node n = (Node)m; + CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0(); + if( m.isClone() && // Must be clonable + (n.nOuts()>1 || // Has many users OR + // Only 1 user but effective use is remote block + effUseBlk != n.cfg0() )) + // Then fail the clonable; it should split or move alloc.fail(alloc.lrg((Node)m)); - else if( !tlrg.sub(killMask) ) { - tlrg._killed = true; // Failed by a kill-mask + // Else clonable cannot move + else if( !tlrg.sub(killMask) ) alloc.fail(tlrg); - } } } } @@ -260,6 +268,24 @@ abstract public class IFG { } + static void convert2DAdjacency( RegAlloc alloc ) { + // Convert the 2-D array of bits (a 1-D array of BitSets) into an + // adjacency matrix. + int maxlrg = alloc._LRGS.length; + for( int i=1; i<maxlrg; i++ ) { + BitSet ifg = IFG.atX(i); + if( ifg != null ) { + LRG lrg0 = alloc._LRGS[i]; + for( int lrg = ifg.nextSetBit(0); lrg>=0; lrg=ifg.nextSetBit(lrg+1) ) { + LRG lrg1 = alloc._LRGS[lrg]; + lrg0.addNeighbor(lrg1); + lrg1.addNeighbor(lrg0); + } + } + } + } + + // ------------------------------------------------------------------------ // Color the inference graph. @@ -276,22 +302,10 @@ abstract public class IFG { // If there's no spare color we'll have to spill this at-risk live range. public static boolean color(int round, RegAlloc alloc) { - - // Convert the 2-D array of bits (a 1-D array of BitSets) into an - // adjacency matrix. int maxlrg = alloc._LRGS.length, nlrgs=0; - for( int i=1; i<maxlrg; i++ ) { - if( alloc._LRGS[i] != null ) nlrgs++; - BitSet ifg = IFG.atX(i); - if( ifg != null ) { - LRG lrg0 = alloc._LRGS[i]; - for( int lrg = ifg.nextSetBit(0); lrg>=0; lrg=ifg.nextSetBit(lrg+1) ) { - LRG lrg1 = alloc._LRGS[lrg]; - lrg0.addNeighbor(lrg1); - lrg1.addNeighbor(lrg0); - } - } - } + for( int i=1; i<maxlrg; i++ ) + if( alloc._LRGS[i] != null ) + nlrgs++; // Simplify @@ -407,7 +421,7 @@ abstract public class IFG { int best=sptr; int bestScore = pickRiskyScore(color_stack[best]); for( int i=sptr+1; i<color_stack.length; i++ ) { - if( bestScore == 999999 ) return best; // Already max score + if( bestScore == 1000000 ) return best; // Already max score int iScore = pickRiskyScore(color_stack[i]); if( iScore > bestScore ) { best = i; bestScore = iScore; } @@ -424,13 +438,25 @@ abstract public class IFG { // Picking a live range that is very close to coloring might allow it to // color despite being risky. private static int pickRiskyScore( LRG lrg ) { + // Pick single-def clonables that are not right next to their single-use. + // Failing to color these will clone them closer to their uses. + if( !lrg._multiDef && lrg._machDef.isClone() ) { + Node def = ((Node)lrg._machDef); + Node use = ((Node)lrg._machUse); + CFGNode cfg = def.cfg0(); + if( cfg != use.cfg0() || // Different blocks OR + // Same block, but not close + cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) + return 1000000; + } + // Always pick callee-save registers as being very large area recovered // and very cheap to spill. if( lrg._machDef instanceof CalleeSaveNode ) - return 999998; - if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && + return 1000000-2-lrg._mask.firstReg(); + if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) - return 999999; + return 1000000-1; // TODO: cost/benefit model. Perhaps counting loop-depth (freq) of def/use for cost // and "area" for benefit @@ -441,35 +467,39 @@ abstract public class IFG { if( mask.size1() ) return reg; // Check chain of splits up the def-chain. Take first allocated // register, and if it's available in the mask, take it. - Node defSplit = lrg._splitDef, useSplit = lrg._splitUse; - int tidx, cnt=0; + Node def = lrg._splitDef, use = lrg._splitUse; + int tidx=0, cnt=0; - while( (tidx=biasable(defSplit)) != 0 || biasable(useSplit) != 0 ) { + while( def != null || use != null ) { if( cnt++ > 10 ) break; - if( tidx != 0 ) { - short bias = biasColor( alloc, defSplit, mask ); + if( def != null ) { + short bias = biasColor( alloc, def, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) defSplit = null; // Kill this side, no more searching - } else defSplit = null; + if( bias == -2 ) def = null; // Kill this side, no more searching + else if( (tidx=biasable(def)) == 0 ) def = null; + } - if( biasable(useSplit) != 0 ) { - short bias = biasColor( alloc, useSplit, mask ); + if( use != null ) { + short bias = biasColor( alloc, use, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) useSplit = null; // Kill this side, no more searching - } else useSplit = null; + if( bias == -2 ) use = null; // Kill this side, no more searching + else if( biasable(use)==0 ) use = null; + } - if( defSplit != null ) { - short bias = biasColorNeighbors( alloc, defSplit, mask ); + if( def != null ) { + short bias = biasColorNeighbors( alloc, def, mask ); if( bias >= 0 ) return bias; // Advance def side - defSplit = defSplit.in(tidx); + def = def.in(tidx); + if( alloc.lrg(def)==null ) def=null; } - if( useSplit != null ) { - short bias = biasColorNeighbors( alloc, useSplit, mask ); + if( use != null ) { + short bias = biasColorNeighbors( alloc, use, mask ); if( bias >= 0 ) return bias; - useSplit = useSplit.out(0); + use = use.out(0); + if( biasable(use)==0 ) use=null; } } @@ -478,7 +508,7 @@ abstract public class IFG { private static int biasable(Node split) { if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1 - if( split instanceof PhiNode ) return 1; // Yes biasable, advance is slot 1 + if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Yes biasable, advance is slot 1 if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } @@ -503,7 +533,7 @@ abstract public class IFG { // Can I limit my own choices to valid neighbor choices? for( LRG alrg : slrg._adj ) { - int reg = alrg._reg; + short reg = alrg._reg; if( reg == -1 && alrg._mask.size1() ) reg = alrg._mask.firstReg(); if( reg != -1 ) { diff --git a/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/src/main/java/com/seaofnodes/simple/codegen/LRG.java index 394c4a01..ec254a2e 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/LRG.java +++ b/src/main/java/com/seaofnodes/simple/codegen/LRG.java @@ -2,6 +2,7 @@ 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 java.util.IdentityHashMap; @@ -37,16 +38,13 @@ public class LRG { // Count of single-register defs and uses short _1regDefCnt, _1regUseCnt; + // Count of all defs, uses. Mostly interested 1 vs many + boolean _multiDef, _multiUse; // A sample MachNode def in the live range public MachNode _machDef, _machUse; short _uidx; // _machUse input - // Mask set to empty via a kill-mask. This is usually a capacity kill, - // which means we need to split and spill into memory - which means even if - // the def-side has many registers, it MUST spill. - boolean _killed; - // Some splits used in biased coloring MachConcreteNode _splitDef, _splitUse; @@ -59,6 +57,8 @@ public class LRG { // Adjacent Live Range neighbors. Only valid during coloring Ary<LRG> _adj; + public int nadj() { return _adj==null ? 0 : _adj._len; } + void addNeighbor(LRG lrg) { if( _adj==null ) _adj = new Ary<>(LRG.class); _adj.push(lrg); @@ -77,7 +77,7 @@ public class LRG { } // More registers than neighbors - boolean lowDegree() { return (_adj==null ? 0 : _adj._len) < _mask.size(); } + boolean lowDegree() { return nadj() < _mask.size(); } LRG( short lrg ) { _lrg = lrg; _reg = -1; } @@ -121,29 +121,39 @@ public class LRG { if( _machDef==null ) { _machDef = lrg._machDef; } else if( lrg._machDef!=null ) { + if( _machDef != lrg._machDef ) _multiDef=true; if( _1regDefCnt==0 ) _machDef = lrg._machDef; else if( _machDef==lrg._machDef ) _1regDefCnt--; } _1regDefCnt += lrg._1regDefCnt; + _multiDef |= lrg._multiDef; if( _machUse==null ) { _machUse = lrg._machUse; + _uidx = lrg._uidx; } else if( lrg._machUse!=null ) { - if( _1regUseCnt==0 ) + if( _machUse != lrg._machUse ) _multiUse=true; + if( _1regUseCnt==0 ) { _machUse = lrg._machUse; + _uidx = lrg._uidx; + } else if( _machUse==lrg._machUse ) _1regUseCnt--; } _1regUseCnt += lrg._1regUseCnt; + _multiUse |= lrg._multiUse; // Fold deepest Split _splitDef = deepSplit(_splitDef,lrg._splitDef); _splitUse = deepSplit(_splitUse,lrg._splitUse); // Fold together masks - _mask = _mask.and(lrg._mask); + RegMask mask = _mask.and(lrg._mask); + if( mask==null ) + mask = _mask.copy().and(lrg._mask); + _mask = mask; return this; } @@ -153,6 +163,8 @@ public class LRG { // Record any Mach def for spilling heuristics LRG machDef( MachNode def, boolean size1 ) { + if( _machDef!=null && _machDef!=def ) + _multiDef = true; if( _machDef==null || size1 ) _machDef = def; if( size1 ) @@ -164,6 +176,8 @@ public class LRG { // Record any Mach use for spilling heuristics LRG machUse( MachNode use, short uidx, boolean size1 ) { + if( _machUse!=null && _machUse!=use ) + _multiUse = true; if( _machUse==null || size1 ) { _machUse = use; _uidx = uidx; } if( size1 ) diff --git a/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java new file mode 100644 index 00000000..e1e849e6 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/LinkMem.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.node.Node; + +// In-memory linking +public class LinkMem { + final CodeGen _code; + LinkMem( CodeGen code ) { _code = code; } + + public CodeGen link() { + Encoding enc = _code._encoding; + + // Patch external calls internally + enc.patchGlobalRelocations(); + + // Write any large constants into a constant pool; they + // are accessed by RIP-relative addressing. + enc.writeConstantPool(enc._bits,true); + + return _code; + } +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java index 1796ef7c..de4fadc4 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ListScheduler.java @@ -48,6 +48,9 @@ public abstract class ListScheduler { computeSingleRDef(bb,use); else computeSingleRDef(bb,n); + + if( n instanceof NewNode || n instanceof CallNode ) + bb.fun()._hasCalls = true; return this; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/src/main/java/com/seaofnodes/simple/codegen/Machine.java index 13d7abc1..1c12bfcb 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Machine.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Machine.java @@ -1,22 +1,93 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeFunPtr; abstract public class Machine { // Human readable machine name. Something like "x86-64" or "arm" or "risc5" public abstract String name(); + // Default opcode size for printing; 4 bytes for most 32-bit risc chips + public int defaultOpSize() { return 4; } // Human-readable name for a register number, e.g. "RAX" or "R0" - public abstract String reg( int reg ); + public abstract String[] regs(); // Create a split op; any register to any register, including stack slots public abstract SplitNode split( String kind, byte round, LRG lrg); - // List of caller-save registers - public abstract RegMask callerSave(); - // List of callee-save registers - public abstract RegMask calleeSave(); + // List of caller-save registers, as a 64bit mask + public abstract long callerSave(); + // List of never-save registers, e.g. RSP or a ZERO register if you have one + public abstract long neverSave(); + // Call Argument Mask + public abstract RegMask callArgMask(TypeFunPtr tfp, int arg); + // Return register mask, based on signature (GPR vs FPR) + public abstract RegMask retMask(TypeFunPtr tfp); + // Return PC register + public abstract int rpc(); // Return a MachNode unconditional branch public abstract CFGNode jump(); - // Break an infinite loop - public abstract IfNode never( CFGNode ctrl ); // Instruction select from ideal nodes public abstract Node instSelect( Node n ); + + /** Stack Slot Numbering + +RA gives all registers a number, starting at 0. Stack slots continue this +numbering going up from the last register number. Common register numbers are +0-15 for GPRs, 16-31 for FPRs, 32 for flags, and stack slots starting at +register#33 going up. These numbers are machine-specific, YMMV, etc; e.g. RPC +is only in stack slot 0 on X86; other cpus start with the rpc in a register +which may spill into any generic spill slot. + +For ease of reading and printing, stack slots start again at slot#0 - but +during RA they are actually biased by CPU.MAX_REG. + +Stack Layout during Reg Alloc: + + Slot Value Description + ---- ------- ----------- +MAXREG+ R+1 argR maxArgSlot(calleR tfp), can be 0 + ... +MAXREG+ 1 arg0 + ---- -- Caller ------ +MAXREG+ 0 RPC +MAXREG+ R+E+N PAD optional alignment + +MAXREG+ + Spills Caller Frame Space; N spills +MAXREG+ R+E+1 Spills + +MAXREG+ R+E argE maxArgSlot(calleE tfp), can be 0 + ... +MAXREG+ R+2 arg0 + ---- -- Callee ------- + ... + +Slots defined by maxArgSlot do not have to contain the actual passed argument; +they can be "shadow slots". If they exist, they are property of the frame / +FunNode where the TFP comes from. + +For a given calleR, there are generally many calleE's and they all share the +low-range stack slots. + +Example:, Win64, main(int arg) { calloc(1,size); } + + Post-Warp: SP+56 shadow-main-arg +Pre-alloc Post-Alloc SP+48 RPC +--- ------- ---------- ------------- +40 spill#3 SP+40 SP+40 spill#3 +39 spill#2 SP+32 "" +38 spill#1 SP+24 "" +37 spill#0 SP+16 "" spill#0 +36 shadow-calloc#size SP+ 8 SP+ 8 shadow-calloc#size +35 shadow-calloc#1 SP+ 0 SP+ 0 shadow-calloc#1 +--- --- FRAME BASE ---------- ---- FRAME BASE ------- +34 shadow-main-arg SP+56 +33 RPC SP+48 + + + */ + + + // Maximum stack slot (or 0) for the args in this TFP. This will include + // shadow slots if defined in the ABI, even if all arguments are passed in + // registers. + public abstract short maxArgSlot(TypeFunPtr tfp); + } diff --git a/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java b/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java new file mode 100644 index 00000000..777182dc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/RIPRelSize.java @@ -0,0 +1,14 @@ +package com.seaofnodes.simple.codegen; + +// This Node rip-relative encodings has sizes that vary by delta +public interface RIPRelSize { + // delta is the distance from the opcode *start* to the target start. Each + // hardware target adjusts as needed, X86 measures from the opcode *end* + // and small jumps are 2 bytes, so they'll need to subtract 2. + byte encSize(int delta); + + // Patch full encoding in. Used for both short and long forms. delta + // again is from the opcode *start*. + void patch( Encoding enc, int opStart, int opLen, int delta ); + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index badec740..e1051fc6 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.node.*; import java.util.Arrays; +import java.util.BitSet; import java.util.IdentityHashMap; /** @@ -129,11 +130,18 @@ public class RegAlloc { } // Printable register number for node n - String reg( Node n ) { + String reg( Node n ) { return reg(n,null); } + String reg( Node n, FunNode fun ) { LRG lrg = lrg(n); if( lrg==null ) return null; + // No register yet, use LRG if( lrg._reg == -1 ) return "V"+lrg._lrg; - return _code._mach.reg(lrg._reg); + // Chosen machine register unless stack-slot and past RA + String[] regs = _code._mach.regs(); + if( lrg._reg < regs.length || _code._phase.ordinal() <= CodeGen.Phase.RegAlloc.ordinal() || fun==null ) + return RegMask.reg(regs,lrg._reg); + // Stack-slot past RA uses the frame layout logic + return "[rsp+"+fun.computeStackOffset(_code,lrg._reg)+"]"; } // ----------------------- @@ -141,15 +149,31 @@ public class RegAlloc { public void regAlloc() { // Insert callee-save registers + String[] regs = _code._mach.regs(); + long neverSave= _code._mach.neverSave(); for( CFGNode bb : _code._cfg ) - if( bb instanceof FunNode fun ) - insertCalleeSave(fun); + if( bb instanceof FunNode fun ) { + ReturnNode ret = fun.ret(); + int len = Math.min(regs.length,64); + for( int reg=0; reg<len; reg++ ) + if( !_code._callerSave.test(reg) && ((1L<<reg)&neverSave)==0 ) { + ret.addDef(new CalleeSaveNode(fun,reg,regs[reg])); + assert ret.regmap(ret.nIns()-1).firstReg()==reg; + } + } + // Cache reg masks for New and Call + for( CFGNode bb : _code._cfg ) { + if( bb instanceof CallEndNode cend ) cend.cacheRegs(_code); + for( Node n : bb._outputs ) + if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); + } // Top driver: repeated rounds of coloring and splitting. byte round=0; while( !graphColor(round) ) { split(round); - assert round < 7; // Really expect to be done soon + if( round >= 7 ) // Really expect to be done soon + throw Utils.TODO("Allocator taking too long"); round++; } postColor(); // Remove no-op spills @@ -166,24 +190,12 @@ public class RegAlloc { BuildLRG.run(round,this) && // if no hard register conflicts // Build Interference Graph IFG.build(round,this) && // If no self conflicts or uncolorable + // Conservative coalesce copies + Coalesce.coalesce(round,this) && // Color attempt IFG.color(round,this); // If colorable } - // Insert callee-save registers. Walk the callee-save RegMask ignoring any - // Parms, then insert a Parm and an edge from the Ret to the Parm with the - // callee-save register. - private void insertCalleeSave( FunNode fun ) { - RegMask saves = _code._mach.calleeSave(); - ReturnNode ret = fun.ret(); - - for( short reg = saves.firstReg(); reg != -1; reg = saves.nextReg(reg) ) { - ret.addDef(new CalleeSaveNode(fun,reg,_code._mach.reg(reg))); - assert ((MachNode)ret).regmap(ret.nIns()-1).firstReg()==reg; - } - } - - // ----------------------- // Split conflicted live ranges. void split(byte round) { @@ -193,11 +205,15 @@ public class RegAlloc { // independently... which generally requires a full pass over the // program for each failing live range. i.e., might be a lot of // passes. - for( LRG lrg : _failed.keySet() ) + + // Sort, to avoid non-deterministic HashMap ordering + LRG[] splits = _failed.keySet().toArray(new LRG[0]); + Arrays.sort(splits, (x,y) -> x._lrg - y._lrg ); + for( LRG lrg : splits ) split(round,lrg); } - // Split this live range + // Split this live range, top level heuristic boolean split( byte round, LRG lrg ) { assert lrg.leader(); // Already rolled up @@ -206,13 +222,16 @@ public class RegAlloc { // Register mask when empty; split around defs and uses with limited // register masks. - if( lrg._mask.isEmpty() ) { + if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) return splitEmptyMaskSimple(round,lrg); - // Default to splitByLoop - //return splitEmptyMask(round,lrg); + // Repeated single-reg uses from a single def. Special for archs + // with more fixed regs. + if( !lrg._multiDef && lrg._1regDefCnt <= 1 && lrg._1regUseCnt > 2 ) + if( splitEmptyMaskByUse(round,lrg) ) + return true; } // Generic split-by-loop depth. @@ -235,39 +254,70 @@ public class RegAlloc { // alloc // V2/rax - kills prior RAX // st4 [V1],len - No good, must split around - makeSplit("def/empty1",round,lrg).insertAfter((Node)lrg._machDef, false/*true*/); + insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/); // Split just before use - if( lrg._1regUseCnt==1 ) + if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) ) insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg); return true; } - // Split live range with an empty mask. Specifically forces splits at - // single-register defs or uses everywhere. - boolean splitEmptyMask( byte round, LRG lrg ) { - findAllLRG(lrg); - // If no single-use or single-def, assume this is a complete register - // kill and force spilling everywhere. - boolean all = lrg._killed || (lrg._1regDefCnt + lrg._1regUseCnt)==0; - for( Node n : _ns ) { - if( !(n instanceof MachNode mach) ) continue; - // Find def of spilling live range; spilling everywhere, OR - // single-register DEF and not cloneable (since these will clone - // before every use) - if( lrg(n)==lrg && (all || (!mach.isClone() && mach.outregmap().size1() )) ) - makeSplit(n,"def/empty2",round,lrg).insertAfter(n,true); - // Find all uses - for( int i=1; i<n.nIns(); i++ ) { - Node def = n.in(i); - // Skip any new splits inserted just this pass - while( def instanceof SplitNode && lrg(def)==null ) - def = def.in(1); - // Main def (past splits) is of the spilling lrg, and spilling - // single-register USE (or everywhere) - if( lrg(def)==lrg && (all || mach.regmap(i).size1()) ) - insertBefore(n,i,"use/empty2",round,lrg); + // Single-def live range with an empty mask. There are many single-reg + // uses. Theory is there's many repeats if the same reg amongst the uses. + // In of splitting once per use, start by splitting into groups based on + // required input register. + boolean splitEmptyMaskByUse( byte round, LRG lrg ) { + Node def = (Node)lrg._machDef; + + // Look at each use, and break into non-overlapping register classes. + Ary<RegMask> rclass = new Ary<>(RegMask.class); + boolean done=false; + while( !done ) { + done = true; + for( Node use : def._outputs ) + if( use instanceof MachNode mach ) + for( int i=1; i<use.nIns(); i++ ) + if( use.in(i)==def ) + done = putIntoRegClass( rclass, mach.regmap(i) ); + } + + // See how many register classes we split into + if( rclass._len <= 1 ) return false; + + // Split by class + for( RegMask rmask : rclass ) { + Node split = makeSplit(def,"popular",round,lrg); + split.insertAfter( def ); + if( split.nIns()>1 ) split.setDef(1,def); + // all uses by class to split + for( int j=0; j < def._outputs._len; j++ ) { + Node use = def._outputs.at(j); + if( use instanceof MachNode mach && use!=split ) { + // Check all use inputs for n, in case there's several + for( int i = 1; i < use.nIns(); i++ ) + // Find a def input, and check register class + if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) + // Modify use to use the split version specialized to this rclass + { use.setDef( i, split ); j--; break; } + } + } + } + return true; + } + + + // Put use into a register class, perhaps adding a class or perhaps + // narrowing a class (and causing a repeat) + private static boolean putIntoRegClass( Ary<RegMask> rclass, RegMask rmask ) { + for( int i=0; i<rclass._len; i++ ) { + RegMask omask = rclass.at(i); + if( omask.and(rmask) == omask ) return true; // Within the same register class + if( omask.overlap(rmask) ) { + rclass.set(i,new RegMask(omask.copy().and(rmask))); + return false; // Need go again } } + // Add a new class, no need to go again + rclass.push(rmask); return true; } @@ -281,27 +331,28 @@ public class RegAlloc { // For all conflicts for( Node def : conflicts ) { assert lrg(def)==lrg; // Might be conflict use-side + // Split before each use that extends the live range; i.e. is a + // Phi or two-address + for( int i=0; i<def._outputs._len; i++ ) { + Node use = def.out(i); + if( (use instanceof PhiNode phi && + !(phi.region() instanceof LoopNode loop && phi.in(2)==def && def.cfg0().idepth() > loop.idepth() ) ) || + (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) ) + insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg ); + } // Split after the Phi which extends the LRG. Split also before // Phi slot 1 (and not all inputs), because Phis extend the live range. // TODO: split before all inputs (except the last; at least 1 split here must be extra) if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) { SplitNode split = makeSplit("def/self",round,lrg); - split.insertAfter(def,false); + insertAfterAndReplace(split,def,false); if( split.nOuts()==0 ) - split.kill(); + split.killOrdered(); insertBefore(phi,1,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range if( def instanceof MachNode mach && mach.twoAddress()!= 0 ) insertBefore(def,mach.twoAddress(),"use/self/two",round,lrg); - // Split before each use that extends the live range; i.e. is a - // Phi or two-address - for( int i=0; i<def._outputs._len; i++ ) { - Node use = def.out(i); - if( (use instanceof PhiNode phi && !(phi.region() instanceof LoopNode && phi.in(2)==def ) ) || - (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) ) - insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg ); - } } return true; } @@ -348,10 +399,10 @@ public class RegAlloc { (min==max || n.cfg0().loopDepth() <= min) ) { // Cloneable constants will be cloned at uses, not after def if( !(n instanceof MachNode mach && mach.isClone()) && - // Single user is already a split - !(n.nOuts()==1 && n.out(0) instanceof SplitNode) ) + // Single user is already a split adjacent + !(n.nOuts()==1 && n.out(0) instanceof SplitNode split && sameBlockNoClobber(split) ) ) // Split after def in min loop nest - makeSplit("def/loop",round,lrg).insertAfter(n,false); + insertAfterAndReplace( makeSplit("def/loop",round,lrg), n,true); } // PhiNodes check all CFG inputs @@ -362,20 +413,19 @@ public class RegAlloc { // splitting in inner loop or at loop border (min==max || phi.region().cfg(i).loopDepth() <= min) && // and not around the backedge of a loop (bad place to force a split, hard to remove) - !(phi.region() instanceof LoopNode && i==2) ) + !(phi.region() instanceof LoopNode && i==2 && (phi.in(i) instanceof PhiNode pp && pp.region()==phi.region())) ) // Split before phi-use in prior block insertBefore(phi,i, "use/loop/phi",round,lrg); } else { // Others check uses for( int i=1; i<n.nIns(); i++ ) { - if( lrgSame(n.in(i),lrg) && // This is a LRG use - // splitting in inner loop or at loop border - (min==max || n.cfg0().loopDepth() <= min) && - // Not a single-use split same block already - !(n.in(i) instanceof SplitNode && n.in(i).nOuts()==1 && n.cfg0()==n.in(i).cfg0()) ) + // This is a LRG use + // splitting in inner loop or at loop border + if( lrgSame( n.in( i ), lrg ) && + (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || n.cfg0().loopDepth() <= min) ) // Split before in this block - insertBefore( n, i, "use/loop/use", round,lrg ); + insertBefore( n, i, "use/loop/use", round,lrg, false ); } } } @@ -396,6 +446,22 @@ public class RegAlloc { int min = (int)ld; int max = (int)(ld>>32); int d = cfg.loopDepth(); + // if n will lower the min loop and is in the tail end of the loop + // header, splitting "around" the loop will not help. Treat n as being + // in the loop. + if( d < min ) { + if( cfg.uctrl() instanceof LoopNode loop && loop.entry()==cfg ) { + for( int i=cfg.nOuts()-2; i>=0; i-- ) { + Node out = cfg.out(i); + if( n==out ) + { d = loop.loopDepth(); break; } // Treat n as being "in the loop" + if( !((out instanceof MachNode mach && mach.isClone()) || out instanceof SplitNode ) ) + break; // Treat b as "normal", out of loop + } + } + } + + // lower min, raise max, and re-fold min = Math.min(min,d); max = Math.max(max,d); return ((long)max<<32) | min; @@ -421,12 +487,12 @@ public class RegAlloc { for( Node n : _ns ) assert !n.isDead(); } - void insertBefore(Node n, int i, String kind, byte round, LRG lrg) { + void insertBefore(Node n, int i, String kind, byte round, LRG lrg, boolean skip) { Node def = n.in(i); // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Def is a split ? - if( def instanceof SplitNode ) { + if( skip && def instanceof SplitNode ) { boolean singleReg = n instanceof MachNode mach && mach.regmap(i).size1(); // Same block, multiple registers, split is only used by n, // assume this is good enough and do not split again. @@ -435,9 +501,30 @@ public class RegAlloc { } makeSplit(def,kind,round,lrg).insertBefore(n, i); // Skip split-of-split same block - if( def instanceof SplitNode && cfg==def.cfg0() ) + if( skip && def instanceof SplitNode && cfg==def.cfg0() ) n.in(i).setDefOrdered(1,def.in(1)); } + void insertBefore(Node n, int i, String kind, byte round, LRG lrg) { + insertBefore(n,i,kind,round,lrg,true); + } + + // Replace uses of `def` with `split`, and insert `split` immediately after + // `def` in the basic block. + public void insertAfterAndReplace( Node split, Node def, boolean must ) { + split.insertAfter(def); + if( split.nIns()>1 ) split.setDef(1,def); + for( int j=def.nOuts()-1; j>=0; j-- ) { + Node use = def.out(j); + if( use==split ) continue; // Skip self + // Can we avoid a split of a split? 'this' split is used by + // another split in the same block. + if( !must && use instanceof SplitNode split2 && sameBlockNoClobber(split2) ) + continue; + int idx = use._inputs.find(def); + use.setDefOrdered(idx,split); + if( j < def.nOuts() ) j++; + } + } private Node makeSplit( Node def, String kind, byte round, LRG lrg ) { Node split = def instanceof MachNode mach && mach.isClone() @@ -456,11 +543,27 @@ public class RegAlloc { // ----------------------- // POST PASS: Remove empty spills that biased-coloring made private void postColor() { + int maxReg = -1; for( CFGNode bb : _code._cfg ) { // For all ops + if( bb instanceof FunNode fun ) + maxReg = -1; // Reset for new function + // Compute frame size, based on arguments and largest reg seen + if( bb instanceof ReturnNode ret ) + ret.fun().computeFrameAdjust(_code,maxReg); + // Raise frame size by max stack args passed, even if ignored + if( bb instanceof CallEndNode cend ) + maxReg = Math.max(maxReg,cend._xslot); + for( int j=0; j<bb.nOuts(); j++ ) { Node n = bb.out(j); - if( !(n instanceof SplitNode lo) ) continue; - int defreg = lrg(n )._reg; + if( lrg(n)!=null ) + maxReg = Math.max(maxReg,lrg(n)._reg+1); + // Raise frame size by max stack args passed to New + if( n instanceof NewNode nnn ) + maxReg = Math.max(maxReg,nnn._xslot); + + if( !(n instanceof SplitNode ) ) continue; + int defreg = lrg(n )._reg; int usereg = lrg(n.in(1))._reg; // Attempt to bypass split if( defreg != usereg && splitBypass(bb,j,n,defreg) ) @@ -499,4 +602,24 @@ public class RegAlloc { lo.setDefOrdered(1,hi.in(1)); return true; } + + + public boolean sameBlockNoClobber( SplitNode split ) { + Node def = split.in(1); + CFGNode cfg = def.cfg0(); + if( cfg != split.cfg0() ) return false; // Not same block + // Get multinode head + Node def0 = def instanceof ProjNode ? def.in(0) : def; + int defreg = lrg(def)._reg; + if( defreg == -1 ) defreg = lrg(def)._mask.firstReg(); + if( defreg == -1 ) return false; // no allowed registers -> clobbered + for( int idx = cfg._outputs.find(split) -1; idx >= 0; idx-- ) { + Node n = cfg.out(idx); + if( n==def0 ) return true; // No clobbers + if( lrg(n) == lrg(def) ) return false; // Self conflict + if( lrg(n)!=null && lrg(n)._reg == defreg ) + return false; // Clobbered + } + throw Utils.TODO(); + } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index f28805b5..79de3fbf 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -32,6 +32,7 @@ public class RegMask { } public RegMask(long bits ) { _bits0 = bits; } public RegMask(long bits0, long bits1 ) { _bits0 = bits0; _bits1 = bits1; } + public RegMask(RegMask r) { _bits0 = r._bits0; _bits1 = r._bits1; } private RegMask() { _bits0 = _bits1 = 0; } // AND, with copy-on-write if changing @@ -65,6 +66,7 @@ public class RegMask { public short firstReg() { + if( isEmpty() ) return -1; return (short)(_bits0 != 0 ? Long.numberOfTrailingZeros(_bits0) : Long.numberOfTrailingZeros(_bits1)+64); @@ -84,7 +86,7 @@ public class RegMask { boolean isEmpty() { return _bits0==0 && _bits1==0; } - boolean test( int reg ) { + public boolean test( int reg ) { return ((reg<64 ? (_bits0 >> reg) : (_bits1 >> (reg-64))) & 1) != 0; } @@ -108,35 +110,17 @@ public class RegMask { Machine mach = CodeGen.CODE._mach; if( _bits0==0 && _bits1==0 ) return sb.p("[]"); sb.p("["); + String[] regs = mach.regs(); for( int i=0; i<64; i++ ) if( ((_bits0 >> i)&1) != 0 ) - sb.p(mach.reg(i)).p(","); + sb.p(reg(regs,i)).p(","); for( int i=0; i<64; i++ ) if( ((_bits1 >> i)&1) != 0 ) - sb.p(mach.reg(i+64)).p(","); + sb.p(reg(regs,i+64)).p(","); return sb.unchar().p("]"); } -} -// Mutable regmask(writable) -class RegMaskRW extends RegMask { - public RegMaskRW(long x, long y) { super(x,y); } - // clears bit at position r. Returns true if the mask is still not empty. - public boolean clr(int r) { - if( r < 64 ) _bits0 &= ~(1L<<(r )); - else _bits1 &= ~(1L<<(r-64)); - return _bits0!=0 || _bits1!=0; - } - @Override RegMaskRW and( RegMask mask ) { - if( mask==null ) return this; - _bits0 &= mask._bits0; - _bits1 &= mask._bits1; - return this; - } - @Override RegMaskRW sub( RegMask mask ) { - if( mask==null ) return this; - _bits0 &= ~mask._bits0; - _bits1 &= ~mask._bits1; - return this; + public static String reg(String[] regs, int i) { + return i<regs.length ? regs[i] : "[stk#"+i+"]"; } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegMaskRW.java b/src/main/java/com/seaofnodes/simple/codegen/RegMaskRW.java new file mode 100644 index 00000000..1da9a3b1 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/RegMaskRW.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.codegen; + +// Mutable regmask(writable) +public class RegMaskRW extends RegMask { + public RegMaskRW(long x, long y) { super(x,y); } + // clears bit at position r. Returns true if the mask is still not empty. + public boolean clr(int r) { + if( r < 64 ) _bits0 &= ~(1L<<(r )); + else _bits1 &= ~(1L<<(r-64)); + return _bits0!=0 || _bits1!=0; + } + // sets bit at position r. + public void set(int r) { + if( r < 64 ) _bits0 |= (1L<<(r )); + else _bits1 |= (1L<<(r-64)); + } + @Override RegMaskRW and( RegMask mask ) { + if( mask==null ) return this; + _bits0 &= mask._bits0; + _bits1 &= mask._bits1; + return this; + } + @Override RegMaskRW sub( RegMask mask ) { + if( mask==null ) return this; + _bits0 &= ~mask._bits0; + _bits1 &= ~mask._bits1; + return this; + } + public RegMaskRW or( RegMask mask ) { + if( mask!=null ) { + _bits0 |= mask._bits0; + _bits1 |= mask._bits1; + } + return this; + } +} |