diff options
Diffstat (limited to 'chapter30/src/main/java/com/seaofnodes/simple/codegen')
8 files changed, 81 insertions, 39 deletions
diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index 0b314978..8d0237ea 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -16,7 +16,7 @@ abstract public class BuildLRG { // true if no hard-conflicts, although we still might not color. public static boolean run(int round, RegAlloc alloc) { FunNode fun = null; - for( Node bb : alloc._code._cfg ) { + for( Node bb : alloc._cfg ) { if( bb instanceof FunNode fun2 ) fun = fun2; for( Node n : bb.outs() ) { diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java index 689ceceb..dbde2f8b 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java @@ -13,7 +13,7 @@ abstract public class Coalesce { // Walk all the splits, looking for coalesce chances boolean progress = false; - for( CFGNode bb : alloc._code._cfg ) { + for( CFGNode bb : alloc._cfg ) { outer: for( int j=0; j<bb.nOuts(); j++ ) { Node n = bb.out(j); diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/IFG.java index d15e66da..6ad7c0ad 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -72,7 +72,7 @@ abstract public class IFG { WORK.clear(); // Last block has nothing live out - for( CFGNode bb : alloc._code._cfg ) + for( CFGNode bb : alloc._cfg ) if( bb.blockHead()) WORK.push( bb ); @@ -164,6 +164,10 @@ abstract public class IFG { // Also record use-side spills for biased coloring. // Then make all inputs live. for( int i=1; i<n.nIns(); i++ ) { + // Metadata and scheduling dependencies do not consume registers. + // In particular, a static call's hidden class argument has no ABI + // location and must not keep its constant live across other calls. + if( ((MachNode)n).regmap(i)==null ) continue; Node def = n.in(i); if( def==null ) continue; LRG lrg1 = alloc.lrg(def); @@ -480,7 +484,7 @@ abstract public class IFG { private static int functionArea(FunNode fun, RegAlloc alloc) { int area=0; - for( CFGNode bb : alloc._code._cfg ) + for( CFGNode bb : alloc._cfg ) if( bb.fun()==fun ) area += bb.nOuts(); return area; diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java index 5fc002a1..2595b4ad 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java @@ -85,13 +85,7 @@ class InstSelect { } // Produce a machine node from n; map it to flag as done so stops cycles. - if( n instanceof MemOpNode mem && mem.off() instanceof ExternOffsetNode off ) { - // External fields replace base+offset with symbol+0. Keep the ideal - // declaring type on the address for machine load/store width selection. - TypeMemPtr ptr = (TypeMemPtr)mem.ptr()._type; - n._inputs.set(2,new ExternNode(TypeMemPtr.make((byte)2,ptr._obj,true),off._extern)); - n._inputs.set(3,ConstantNode.raw(TypeInteger.ZERO)); - } + if( n instanceof MemOpNode mem ) Machine.externalAddress(mem); map.put(n, x=_code._mach.instSelect(n) ); // Carry loop-tree and pre-order info across the ideal->mach transition if( n instanceof CFGNode ncfg && x instanceof CFGNode xcfg ) { diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/Machine.java index 3eee8fc3..6ccf6b19 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/Machine.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/Machine.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.type.TypeMemPtr; abstract public class Machine { // Human readable machine name. Something like "x86-64" or "arm" or "risc5" @@ -46,6 +47,17 @@ abstract public class Machine { // Instruction select from ideal nodes public abstract Node instSelect( Node n ); + // Lower external fields before selecting a memory operation, including + // loads absorbed into another instruction rather than selected separately. + public static void externalAddress(MemOpNode mem) { + if( mem.off() instanceof ExternOffsetNode off ) { + // Retain the declaring type for load/store width selection. + TypeMemPtr ptr = (TypeMemPtr)mem.ptr()._type; + mem._inputs.set(2,new ExternNode(TypeMemPtr.make((byte)2,ptr._obj,true),off._extern)); + mem._inputs.set(3,ConstantNode.raw(TypeInteger.ZERO)); + } + } + /** Stack Slot Numbering RA gives all registers a number, starting at 0. Stack slots continue this diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 5f8a0ec0..3306ff8f 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -140,7 +140,7 @@ public abstract class ParseAll { fref._name = TypeStruct.addClzPrefix(xcunit._cname); cunit.addDep(xcunit); } else { - throw new RuntimeException("Undefined name '" + fref._name +"'"); + throw fref.err(); } } catch( IOException ioe ) { throw new RuntimeException(ioe); @@ -297,14 +297,6 @@ public abstract class ParseAll { Parser.TYPES.put(cunit._cname,ptr._obj); } - // Symbol not found in source code (or we would not be here). - // Search the module for the fref - public static CompUnit findCompUnitOrThrow(CodeGen code, CompUnit cu, String symbol) { - CompUnit cu2 = findCompUnit(code,cu,symbol); - if( cu2 != null ) return cu2; - throw new RuntimeException("Undefined name '" + symbol +"'"); - } - public static CompUnit findCompUnit(CodeGen code, CompUnit cu, String symbol) { // Symbol not found in source code (or we would not be here). // Search the module for the fref @@ -328,8 +320,15 @@ public abstract class ParseAll { // However if A/B contains "Y", the search would be for A.B.Y then A.Y both of // which do not exist. private static CompUnit findCUnitModule( CodeGen code, CompUnit cunit, String symbol ) throws IOException { - if( cunit == null ) // Ran off top of module scope? - return null; // Failed search + if( cunit == null ) { + // The module root is also a namespace. In particular, a root + // client can resolve sys.text from source, without installed .o's. + String fname=symbol.replace('.','/'); + if( !new File(code._modDir+"/"+fname+".smp").exists() ) return null; + CompUnit root=makeCUnit(code,null,fname); + if( root._clz==null && WORK.find(root)==-1 ) enqueue(root); + return root; + } // Check self if( cunit._name.equals(symbol) ) diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index f1aa18ef..3991cd48 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -54,6 +54,8 @@ public class RegAlloc { // Top-level program graph structure final CodeGen _code; + // Scheduled blocks of the function currently being allocated. + Ary<CFGNode> _cfg; public int _spills, _spillScaled; @@ -161,7 +163,7 @@ public class RegAlloc { } // ----------------------- - RegAlloc( CodeGen code ) { _code = code; } + RegAlloc( CodeGen code ) { _code = code; _cfg = code._cfg; } public void regAlloc() { // Insert callee-save registers @@ -186,18 +188,41 @@ public class RegAlloc { // Expensive assert: useful when chasing cross-function allocator edges. //assert verifyFunctionLocalEdges(); - // Top driver: repeated rounds of coloring and splitting. - byte round=0; - while( !graphColor(round) ) { - split(round); - if( round >= 7 ) // Really expect to be done soon - throw new IllegalStateException("Register allocation made no progress after eight rounds"); - round++; + // Each function owns its retry budget. Keep completed assignments while + // reusing the live-range and interference scratch space for the next. + IdentityHashMap<Node,LRG> colored = new IdentityHashMap<>(); + _cfg = new Ary<>(CFGNode.class); + for( CFGNode bb : _code._cfg ) { + if( bb instanceof FunNode && !_cfg.isEmpty() ) { + allocateFunction(); + colored.putAll(_lrgs); + _cfg.clear(); + } + _cfg.add(bb); } + if( !_cfg.isEmpty() ) { + allocateFunction(); + colored.putAll(_lrgs); + } + _lrgs.clear(); + _lrgs.putAll(colored); + _cfg = _code._cfg; postColor(); // Remove no-op spills _done = true; } + private void allocateFunction() { + _deferredLoopSelf.clear(); + for( byte round=0; !graphColor(round); round++ ) { + split(round); + if( round >= 7 ) { + FunNode fun = _cfg.at(0).fun(); + throw new IllegalStateException("Register allocation failed after eight rounds in "+ + (fun==null ? "<root>" : fun.label())); + } + } + } + boolean verifyFunctionLocalEdges() { for( CFGNode bb : _code._cfg ) for( Node use : bb._outputs ) { @@ -477,7 +502,10 @@ public class RegAlloc { split.killOrdered(); } for( int i=1; i<(deferred.containsKey(phi) ? 2 : phi.nIns()); i++ ) - if( i==1 || sharedPhiInput(phi,i) ) + // Backedges may be joined indirectly through two-address + // chains, even when their input nodes are distinct. After + // the cold-only attempt, isolate those inputs as well. + if( i==1 || phi.region() instanceof LoopNode || sharedPhiInput(phi,i) ) insertBefore(phi,i,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range @@ -653,9 +681,8 @@ public class RegAlloc { return; } 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)); + // Keep the def-side transfer: a kill between the two copies may be + // exactly why this range split. Coalescing can join them when safe. } void insertBefore(Node n, int i, String kind, byte round, LRG lrg) { insertBefore(n,i,kind,round,lrg,true); diff --git a/chapter30/src/main/java/com/seaofnodes/simple/codegen/SourceError.java b/chapter30/src/main/java/com/seaofnodes/simple/codegen/SourceError.java index f2f46146..5be0585f 100644 --- a/chapter30/src/main/java/com/seaofnodes/simple/codegen/SourceError.java +++ b/chapter30/src/main/java/com/seaofnodes/simple/codegen/SourceError.java @@ -16,6 +16,10 @@ public abstract class SourceError { source=cu._src!=null ? cu._src.getBytes(StandardCharsets.UTF_8) : file==null ? null : Files.readAllBytes(Path.of(file)); } catch( IOException ex ) { source=null; } + return format(name,source,pos,message); + } + + public static String format(String name, byte[] source, int pos, String message) { if( source==null || pos<0 || pos>source.length ) return name+": error: "+message+" (source unavailable at byte offset "+pos+")"; @@ -28,22 +32,24 @@ public abstract class SourceError { int point=Math.min(pos,end); String before=new String(source,start,point-start,StandardCharsets.UTF_8); String text=new String(source,start,end-start,StandardCharsets.UTF_8); - int column=before.codePointCount(0,before.length())+1; - SB sb=new SB().p(name).p(':').p(line).p(':').p(column).p(": error: ").p(message).p("\n "); + SB excerpt=new SB(); int width=0, caret=0; for( int i=0; i<text.length(); ) { if( i==before.length() ) caret=width; int ch=text.codePointAt(i); if( ch=='\t' ) { int spaces=8-(width%8); - for( int j=0; j<spaces; j++ ) sb.p(' '); + for( int j=0; j<spaces; j++ ) excerpt.p(' '); width+=spaces; - } else { sb.p(new String(Character.toChars(ch))); width++; } + } else { excerpt.p(new String(Character.toChars(ch))); width++; } i+=Character.charCount(ch); } if( before.length()==text.length() ) caret=width; + // Emacs compilation mode defaults to display columns, with 8-column tabs. + SB sb=new SB().p(name).p(':').p(line).p(':').p(caret+1).p(": error: ").p(message) + .p("\n ").p(excerpt.toString()); sb.p("\n "); - for( int i=0; i<caret; i++ ) sb.p('-'); + for( int i=0; i<caret; i++ ) sb.p('_'); return sb.p('^').toString(); } } |