From 018379b0cf4e286ceacb1e39f34dd80f770e381e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 21 Apr 2025 14:18:23 -0700 Subject: Chapter 22: A Hello, World! MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> --- .../com/seaofnodes/simple/codegen/CodeGen.java | 59 ++++++---- .../com/seaofnodes/simple/codegen/ElfFile.java | 9 +- .../com/seaofnodes/simple/codegen/Encoding.java | 120 +++++++++++++++------ .../simple/codegen/GlobalCodeMotion.java | 17 ++- .../com/seaofnodes/simple/codegen/RegAlloc.java | 26 +++-- 5 files changed, 157 insertions(+), 74 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple/codegen') diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 9ec3bc7b..adb71413 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -21,7 +21,7 @@ public class CodeGen { Opto, // Run ideal optimizations TypeCheck, // Last check for bad programs LoopTree, // Build a loop tree; break infinite loops - InstSelect, // Convert to target hardware nodes + Select, // Convert to target hardware nodes Schedule, // Global schedule (code motion) nodes LocalSched, // Local schedule RegAlloc, // Register allocation @@ -35,6 +35,7 @@ public class CodeGen { public final String _src; // Compile-time known initial argument type public final TypeInteger _arg; + // --------------------------- public CodeGen( String src ) { this(src, TypeInteger.BOT, 123L ); } public CodeGen( String src, TypeInteger arg, long workListSeed ) { @@ -54,14 +55,15 @@ public class CodeGen { 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(); + int p1 = phase.ordinal(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Opto .ordinal() ) opto(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.TypeCheck .ordinal() ) typeCheck(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LoopTree .ordinal() ) loopTree(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Select .ordinal() && cpu != null ) instSelect(cpu,callingConv); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Schedule .ordinal() ) GCM(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.LocalSched.ordinal() ) localSched(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.RegAlloc .ordinal() ) regAlloc(); + if( _phase.ordinal() < p1 && _phase.ordinal() < Phase.Encoding .ordinal() ) encode(); return this; } @@ -128,7 +130,7 @@ public class CodeGen { return TypeFunPtr.make((byte)2,sig,ret, 1L<(); _instSelect( _stop, map ); _stop = ( StopNode)map.get(_stop ); - _start = (StartNode)map.get(_start); + StartNode start = (StartNode)map.get(_start); + _start = start==null ? new StartNode(_start) : start; _instOuts(_stop,visit()); _visit.clear(); _tInsSel = (int)(System.currentTimeMillis() - t0); @@ -317,8 +338,6 @@ public class CodeGen { if( x instanceof MachNode mach ) mach.postSelect(this); // Post selection action - // Updates forward edges only. - n._outputs.clear(); return x; } @@ -342,7 +361,7 @@ public class CodeGen { // Global schedule (code motion) nodes public CodeGen GCM() { return GCM(false); } public CodeGen GCM( boolean show) { - assert _phase.ordinal() <= Phase.InstSelect.ordinal(); + assert _phase.ordinal() <= Phase.Select.ordinal(); _phase = Phase.Schedule; long t0 = System.currentTimeMillis(); @@ -442,8 +461,10 @@ public class CodeGen { String printCFG() { if( _cfg==null ) return "no CFG"; SB sb = new SB(); - for( CFGNode cfg : _cfg ) - IRPrinter.printLine(cfg,sb); + for( CFGNode cfg : _cfg ) { + sb.fix(8,""+cfg._idepth); + IRPrinter.printLine( cfg, sb ); + } return sb.toString(); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java index 746ecfed..0eaaae7b 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfFile.java @@ -273,8 +273,6 @@ public class ElfFile { 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 */); @@ -298,10 +296,10 @@ public class ElfFile { // 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); + Symbol glob = new Symbol("CPOOL$"+start_global, rdata._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC); glob._value = relo._target; - glob._size = 1 << relo._t.log_size(); - glob._index = bigConIdx++; + glob._size = relo._t.size(); + glob._index = start_global++; symbols.push(glob); write8(text_rela._contents, relo._opStart+relo._off); write8(text_rela._contents, ((long)glob._index << 32L) | relo._elf ); @@ -313,6 +311,7 @@ public class ElfFile { text_rela._info = text._index; pushSection(text_rela); + // Final .rela.text symbol 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(); diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index c35ea6a4..db799b98 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -51,7 +51,7 @@ public class Encoding { 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 _target; // Where constant is finally placed public int _opStart; // Opcode start Relo( Node op, Type t, byte off, byte elf ) { _op=op; _t=t; _off=off; _elf=elf; @@ -140,8 +140,8 @@ public class Encoding { final HashMap _externals = new HashMap<>(); - public Encoding external( Node call, String extern ) { - _externals.put(call,extern); + public Encoding external( Node n, String extern ) { + _externals.put(n,extern); return this; } @@ -185,12 +185,10 @@ public class Encoding { Ary rpo = new Ary<>(CFGNode.class); rpos.put(_code._start.loop(),rpo); BitSet visit = _code.visit(); - //IdentityHashMap 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; } @@ -301,7 +299,7 @@ public class Encoding { 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)); + ((cfg instanceof LoopNode && cfg._ltree==c._ltree) || forwardsEmptyScan(cfg,bld)); } // Is the CFG from "next" to the end empty? This means jumping to "next" @@ -361,11 +359,6 @@ public class Encoding { slide = 0; for( int i=0; i 0 ) { // If no short-form ops, nothing to do here @@ -424,31 +434,71 @@ public class Encoding { void writeConstantPool( BAOS bits, boolean patch ) { padN(16,bits); + // radix sort the big constants by alignment + Ary[] raligns = new Ary[5]; + for( Node op : _bigCons.keySet() ) { + Relo relo = _bigCons.get(op); + int align = relo._t.alignment(); + Ary relos = raligns[align]==null ? (raligns[align]=new Ary<>(Relo.class)) : raligns[align]; + relos.add(relo); + } + + + // Types can be used more than once; collapse the dups HashMap 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); + // By alignment + for( int align = 4; align >= 0; align-- ) { + Ary relos = raligns[align]; + if( relos == null ) continue; + for( Relo relo : relos ) { + // Map from relo to constant start and patch + Integer target = targets.get(relo._t); + if( target==null ) { + targets.put(relo._t,target = bits.size()); + // Write constant into constant pool + switch( relo._t ) { + case TypeTuple tt -> cpool(align,bits,tt); + case TypeStruct ts -> cpool(bits,ts); + // Simple primitive (e.g. larger int, float) + default -> addN(align,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); } + // Record target address and opcode start + relo._target = target; + relo._opStart= _opStart[relo._op._nid]; + // Go ahead and locally patch in-memory + if( patch ) + ((RIPRelSize)relo._op).patch(this, relo._opStart, _opLen[relo._op._nid], relo._target - relo._opStart); + } + } + } + + // Constant tuples put all entries at same alignment + private void cpool(int align, BAOS bits, TypeTuple tt) { + for( Type tx : tt._types ) + addN(align,tx,bits); + } + + // Structs use internal field layout + private void cpool( BAOS bits, TypeStruct ts ) { + // Field order by offset + int[] layout = ts.layout(); + int off=0; // offset in the struct + for( int fn=0; fn SENTINAL_CALLOC; + case "calloc" -> SENTINEL_CALLOC; + case "write" -> SENTINEL_WRITE ; 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 40f827ec..04a119c2 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -32,7 +32,6 @@ public abstract class GlobalCodeMotion { // Post-Order of CFG private static void _rpo_cfg(CFGNode def, Node use, BitSet visit, Ary rpo) { - if( use instanceof CallNode call ) call.unlink_all(); if( !(use instanceof CFGNode cfg) || visit.get(cfg._nid) ) return; // Been there, done that if( def instanceof ReturnNode && use instanceof CallEndNode ) @@ -178,14 +177,22 @@ public abstract class GlobalCodeMotion { } // Walk all inputs and put on worklist, as their last-use might now be done - for( Node def : n._inputs ) - if( def!=null && late[def._nid]==null ) { + for( Node def : n._inputs ) { + if( def!=null && late[def._nid]==null ) work.push(def); - // if the def has a load use, maybe the load can fire + // if the def has a load use, maybe the load can fire + if( def!=null ) for( Node out : def._outputs ) if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) work.push(ld); + } + + if( n instanceof LoopNode loop ) { + for( Node phi : loop._outputs ) { + if( phi instanceof PhiNode && late[phi._nid]==null ) + work.push(phi); } + } } } @@ -274,7 +281,7 @@ public abstract class GlobalCodeMotion { for( Node mem : load.mem()._outputs ) { switch( mem ) { case MemOpNode st: - if( !st._isLoad ) { + if( !st._isLoad && load._alias == st._alias ) { assert late[mem._nid] != null; lca = anti_dep( load, late[mem._nid], mem.cfg0(), lca, st ); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index bd4cbf35..57d0d90c 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -163,7 +163,7 @@ public class RegAlloc { } // Cache reg masks for New and Call for( CFGNode bb : _code._cfg ) { - if( bb instanceof CallEndNode cend ) cend.cacheRegs(_code); + if( bb instanceof CallEndMach cend ) cend.cacheRegs(_code); for( Node n : bb._outputs ) if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } @@ -292,20 +292,21 @@ public class RegAlloc { Ary ns = new Ary<>(Node.class); for( RegMask rmask : rclass ) { ns.addAll(def._outputs); - Node split = makeSplit(def,"popular",round,lrg); + Node split = makeSplit(def,"popular",round,lrg,rmask); split.insertAfter( def ); if( split.nIns()>1 ) split.setDef(1,def); // all uses by class to split - for( Node use : ns ) { + 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 ) { + if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) { RegMask m = mach.regmap( i ); if( m!=null && mach.regmap( i ).overlap( rmask ) ) // Modify use to use the split version specialized to this rclass - use.setDefOrdered( i, split ); + { use.setDefOrdered( i, split ); j--; break; } } } } @@ -501,15 +502,17 @@ public class RegAlloc { Node def = n.in(i); // Effective block for use CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); + // Use-side RegMask, if available + RegMask umask = n instanceof MachNode mach ? mach.regmap(i) : null; // Def is a split ? if( skip && def instanceof SplitNode ) { - boolean singleReg = n instanceof MachNode mach && mach.regmap(i).size1(); + boolean singleReg = umask!=null && umask.size1(); // Same block, multiple registers, split is only used by n, // assume this is good enough and do not split again. if( cfg==def.cfg0() && def.nOuts()==1 && !singleReg ) return; } - makeSplit(def,kind,round,lrg).insertBefore(n, i); + makeSplit(def,kind,round,lrg,umask).insertBefore(n, i); // Skip split-of-split same block if( skip && def instanceof SplitNode && cfg==def.cfg0() ) n.in(i).setDefOrdered(1,def.in(1)); @@ -536,8 +539,9 @@ public class RegAlloc { } } - private Node makeSplit( Node def, String kind, byte round, LRG lrg ) { - Node split = def instanceof MachNode mach && mach.isClone() + private Node makeSplit( Node def, String kind, byte round, LRG lrg, RegMask umask ) { + // Clone simple constants if possible + Node split = def instanceof MachNode mach && mach.isClone() && (umask==null || mach.outregmap().overlap(umask)) ? mach.copy() : _code._mach.split(kind,round,lrg); _lrgs.put(split,lrg); @@ -555,13 +559,13 @@ public class RegAlloc { private void postColor() { int maxReg = -1; for( CFGNode bb : _code._cfg ) { // For all ops - if( bb instanceof FunNode fun ) + if( bb instanceof FunNode ) 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 ) + if( bb instanceof CallEndMach cend ) maxReg = Math.max(maxReg,cend._xslot); for( int j=0; j