Chapter 30: Text Formatting and Diagnosticslinear-chapter30

Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>

8 files changed, 81 insertions, 39 deletions

diff --git a/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
index 0b314978..8d0237ea 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
+++ b/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/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java
index 689ceceb..dbde2f8b 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java
+++ b/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/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/src/main/java/com/seaofnodes/simple/codegen/IFG.java
index d15e66da..6ad7c0ad 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/IFG.java
+++ b/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/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java
index 5fc002a1..2595b4ad 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java
+++ b/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/src/main/java/com/seaofnodes/simple/codegen/Machine.java b/src/main/java/com/seaofnodes/simple/codegen/Machine.java
index 3eee8fc3..6ccf6b19 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/Machine.java
+++ b/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/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java
index 5f8a0ec0..3306ff8f 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java
+++ b/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/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index f1aa18ef..3991cd48 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/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/src/main/java/com/seaofnodes/simple/codegen/SourceError.java b/src/main/java/com/seaofnodes/simple/codegen/SourceError.java
index f2f46146..5be0585f 100644
--- a/src/main/java/com/seaofnodes/simple/codegen/SourceError.java
+++ b/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();
     }
 }