From 207febef9924c8fa5391185e75d42a7ea480bb38 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Mon, 10 Aug 2026 11:11:18 -0700 Subject: Chapter 31: Software Drawing, Time, and Graphical Games 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 Co-authored-by: Claude Opus 5 --- src/main/java/com/seaofnodes/simple/README.md | 2 +- .../com/seaofnodes/simple/codegen/CodeGen.java | 6 +- .../com/seaofnodes/simple/codegen/ElfWriter.java | 15 +- .../com/seaofnodes/simple/codegen/Encoding.java | 10 +- .../com/seaofnodes/simple/codegen/IterPeeps.java | 4 +- .../com/seaofnodes/simple/codegen/ParseAll.java | 5 +- .../com/seaofnodes/simple/codegen/RegAlloc.java | 2 +- .../com/seaofnodes/simple/codegen/Serialize.java | 16 +- .../com/seaofnodes/simple/codegen/StaticData.java | 10 +- .../com/seaofnodes/simple/codegen/TypeCheck.java | 6 +- .../com/seaofnodes/simple/node/ArrayInitNode.java | 70 ++++++++ .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 24 ++- .../com/seaofnodes/simple/node/CallEndNode.java | 4 + .../java/com/seaofnodes/simple/node/CallNode.java | 12 ++ .../com/seaofnodes/simple/node/EscapeNode.java | 6 + .../java/com/seaofnodes/simple/node/Intrinsic.java | 119 +++++++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 26 +-- .../com/seaofnodes/simple/node/MemMergeNode.java | 16 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 3 +- src/main/java/com/seaofnodes/simple/node/Node.java | 4 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 4 + .../simple/node/cpus/arm/BitCastARM.java | 23 +++ .../com/seaofnodes/simple/node/cpus/arm/arm.java | 1 + .../simple/node/cpus/riscv/BitCastRISC.java | 23 +++ .../simple/node/cpus/riscv/SplitRISC.java | 2 +- .../seaofnodes/simple/node/cpus/riscv/riscv.java | 1 + .../simple/node/cpus/x86_64_v2/BitCastX86.java | 23 +++ .../simple/node/cpus/x86_64_v2/JmpX86.java | 27 ++- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 6 +- .../simple/node/cpus/x86_64_v2/NegFX86.java | 25 +++ .../simple/node/cpus/x86_64_v2/NegX86.java | 2 +- .../simple/node/cpus/x86_64_v2/NotX86.java | 2 +- .../simple/node/cpus/x86_64_v2/SetX86.java | 18 +- .../simple/node/cpus/x86_64_v2/StoreX86.java | 3 + .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 23 ++- .../com/seaofnodes/simple/parser/Allocations.java | 17 +- .../simple/parser/ArrayInitializers.java | 187 +++++++++++++++++++++ .../com/seaofnodes/simple/parser/Conversions.java | 2 +- .../com/seaofnodes/simple/parser/Declarations.java | 4 + .../com/seaofnodes/simple/parser/Expressions.java | 2 +- .../com/seaofnodes/simple/parser/Functions.java | 64 ++++++- .../java/com/seaofnodes/simple/parser/Lexer.java | 35 +++- .../com/seaofnodes/simple/parser/MethodAccess.java | 130 ++++++++++++++ .../java/com/seaofnodes/simple/parser/Parser.java | 12 +- .../java/com/seaofnodes/simple/parser/README.md | 15 +- .../com/seaofnodes/simple/parser/References.java | 13 +- .../com/seaofnodes/simple/parser/Statements.java | 1 + .../java/com/seaofnodes/simple/parser/Strings.java | 2 +- .../java/com/seaofnodes/simple/parser/Types.java | 11 +- .../java/com/seaofnodes/simple/parser/Var.java | 5 + .../com/seaofnodes/simple/parser/package-info.java | 2 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 15 +- src/main/java/com/seaofnodes/simple/type/Type.java | 2 +- .../com/seaofnodes/simple/type/TypeConAry.java | 147 +++++++++++----- .../com/seaofnodes/simple/type/TypeConAryB.java | 20 --- .../com/seaofnodes/simple/type/TypeConAryI.java | 16 -- .../java/com/seaofnodes/simple/type/TypeFloat.java | 8 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 9 +- .../com/seaofnodes/simple/type/TypeStruct.java | 11 +- 59 files changed, 1097 insertions(+), 176 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/node/ArrayInitNode.java create mode 100644 src/main/java/com/seaofnodes/simple/node/Intrinsic.java create mode 100644 src/main/java/com/seaofnodes/simple/node/cpus/arm/BitCastARM.java create mode 100644 src/main/java/com/seaofnodes/simple/node/cpus/riscv/BitCastRISC.java create mode 100644 src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/BitCastX86.java create mode 100644 src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegFX86.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java create mode 100644 src/main/java/com/seaofnodes/simple/parser/MethodAccess.java delete mode 100644 src/main/java/com/seaofnodes/simple/type/TypeConAryB.java delete mode 100644 src/main/java/com/seaofnodes/simple/type/TypeConAryI.java (limited to 'src/main/java/com/seaofnodes/simple') diff --git a/src/main/java/com/seaofnodes/simple/README.md b/src/main/java/com/seaofnodes/simple/README.md index af86f21e..a8916aa8 100644 --- a/src/main/java/com/seaofnodes/simple/README.md +++ b/src/main/java/com/seaofnodes/simple/README.md @@ -2,7 +2,7 @@ | Directory | Contents | | --- | --- | -| `parser/` | Recursive-descent grammar routines, lexing, name resolution, and construction of the initial IR. `Var` describes a lexical binding. See the [grammar map](../../../../../../docs/chapter30/30-grammar.md). | +| `parser/` | Recursive-descent grammar routines, lexing, name resolution, and construction of the initial IR. `Var` describes a lexical binding. See the [grammar map](../../../../../../docs/chapter31/31-grammar.md). | | `node/` | Sea-of-Nodes IR nodes: graph edges, type computation, and local peephole rewrites. | | `node/cpus/` | Machine-specific nodes and instruction selection support for `arm`, `riscv`, and `x86_64_v2`. | | `codegen/` | Compilation driver and passes: module loading, optimization, scheduling, register allocation, serialization, and machine-code emission. `IterPeeps` runs the peephole worklist. | diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index b4c93e1e..8618b47b 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -786,7 +786,11 @@ public class CodeGen { public boolean _asmLittle=true; public String asm() { return asm(new SB()).toString(); } SB asm(SB sb) { - ASMPrinter.print(sb,this); + if( _encodings.isEmpty() ) ASMPrinter.print(sb,this); + else for( var entry : _encodings.entrySet() ) { + sb.p("\n=== Compilation unit: ").p(entry.getKey()._cname).p(" ===\n"); + ASMPrinter.print(sb,this,entry.getValue()); + } return sb; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index fcf5c287..c5b25be0 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -318,11 +318,15 @@ public class ElfWriter { _strtab = new StringSection(); // place all the symbols + Encoding enc = _code._encoding; int nlocals = 1/*null*/+9/*number of sections*/+1/*Simple section*/; + int debugLocals=0; + for( StaticData.ObjectData obj : enc._data.objects.values() ) + if( !obj.external ) debugLocals+=obj.debugNames.size(); + nlocals+=debugLocals; SymbolSection symbols = new SymbolSection(nlocals); // we've already constructed these entire sections in the encoding phase - Encoding enc = _code._encoding; // Append ELF-only thunks to a copy. Export must not change instruction // offsets or the image used by the in-memory linker and emulators. BAOS textBits = new BAOS(enc._bits.toByteArray(),enc._bits.size()); @@ -402,10 +406,17 @@ public class ElfWriter { SimpleSection simple = new SimpleSection(_code._serial); // Write the local section header symbols - assert nlocals == 1+_sections._len; + assert nlocals == 1+_sections._len+debugLocals; symbols.symbol("",0,0,0); // Null symbol at index 0 for( Section s : _sections ) symbols.symbol(s._name, s._index, SYM_BIND_LOCAL, SYM_TYPE_SECTION, 0, s.size()); + // Local aliases describe the pooled object without changing linkage. + // Several source constants may name the same bytes. + for( StaticData.ObjectData obj : enc._data.objects.values() ) + if( !obj.external ) + for( String name : obj.debugNames ) + symbols.symbol(name,obj.readOnly ? rodata._index : rwdata._index, + SYM_BIND_LOCAL,SYM_TYPE_OBJECT,obj.offset,obj.size); int size = 64; // ELF header size // size of all section data diff --git a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index b07a8fec..eb62c36a 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -39,7 +39,9 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { public final BAOS _bits = new BAOS(); // Instructions / encodings public final BAOS _cpool = new BAOS(); // Constant r/o pool public final BAOS _sdata = new BAOS(); // Static r/w pool - public final HashMap _bigCons = new HashMap<>(); + // Relocations belong to instruction occurrences, including equal constant + // loads cloned by scheduling/register allocation. Structural keys lose sites. + public final IdentityHashMap _bigCons = new IdentityHashMap<>(); public final StaticData _data; public final HashMap _externalAddresses = new HashMap<>(); @@ -157,7 +159,7 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { // Nodes need "relocation" patching; things done after code is placed. // Record src and dst Nodes. - private final HashMap _internals = new HashMap<>(); + private final IdentityHashMap _internals = new IdentityHashMap<>(); // Source is a Call, destination in the Fun. public Encoding relo( CallNode call ) { FunNode fun = _code.link(call.tfp()); @@ -187,13 +189,13 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { } // External references only located by Strings a link-time - public final HashMap _externals = new HashMap<>(); + public final IdentityHashMap _externals = new IdentityHashMap<>(); public Encoding external( Node n, String extern ) { _externals.put(n,extern); return this; } - public final HashMap _externData = new HashMap<>(); + public final IdentityHashMap _externData = new IdentityHashMap<>(); public void externalData(Node n, String name) { _externData.put(n,name); } // Store t as a 32/64 bit constant in the code space; generate RIP-relative diff --git a/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java b/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java index 985cd4d2..f4acb729 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java @@ -65,8 +65,10 @@ public class IterPeeps { * Iterate peepholes and inlining to a fixed point */ public void iterate( CodeGen code ) { + assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code)); boolean didInline = false; Ary defer = new Ary<>(Node.class); + while( true ) { // Clean up everything that does not grow the code iteratePeeps(code); @@ -97,8 +99,6 @@ public class IterPeeps { // Run all the code-reduction and type-lifting peeps as possible private void iteratePeeps( CodeGen code ) { - assert !CodeGen.expensiveAssert(0) || (progressOnList(code, _work) && schedulableUses(code)); - Node n; while( (n = _work.pop()) != null ) { if( n.isDead() ) continue; diff --git a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 3306ff8f..882a0f8a 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -150,7 +150,8 @@ public abstract class ParseAll { } private static void addRequiredTypes(CodeGen code, CompUnit cunit) { - for( String typeName : code.P._requiredTypes ) { + for( var required : code.P._requiredTypes.entrySet() ) { + String typeName = required.getKey(); // A forward use can have been resolved later in this source file. if( Parser.TYPES.get(typeName) instanceof TypeStruct ts && !ts._fref ) continue; try { @@ -158,7 +159,7 @@ public abstract class ParseAll { if( xcunit != null ) cunit.addDep(xcunit); else - assert false : "expected to find required type"; + throw Parser.error("Unknown type '"+typeName+"'",required.getValue()); } catch( IOException ioe ) { throw new RuntimeException(ioe); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 3991cd48..1b335c50 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -215,7 +215,7 @@ public class RegAlloc { _deferredLoopSelf.clear(); for( byte round=0; !graphColor(round); round++ ) { split(round); - if( round >= 7 ) { + if( round >= 10 ) { FunNode fun = _cfg.at(0).fun(); throw new IllegalStateException("Register allocation failed after eight rounds in "+ (fun==null ? "" : fun.label())); diff --git a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index ae4ecb74..b168c4af 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -417,7 +417,7 @@ public class Serialize { assert elf._clz._name==strs[1/*skip null ptr*/]; for( Type type : types ) if( type instanceof TypeStruct ts ) - Parser.TYPES.put(ts._name,ts); + installType(ts); for( Type type : types ) { if( !(type instanceof TypeStruct ts) || !TypeStruct.startsClzPrefix(ts._name) ) continue; @@ -429,7 +429,7 @@ public class Serialize { elf._pubTypes = new TypeStruct[npubTypes]; for( int i=0; i debugNames = new TreeSet<>(); public int offset; + public String label() { return debugNames.isEmpty() ? symbol : String.join(", ",debugNames); } ObjectData(Type t, String name, boolean ro, boolean ext) { type=t; symbol=name; readOnly=ro; external=ext; alignment=t.alignment(); @@ -73,7 +76,12 @@ public final class StaticData { // Register before following fields: class objects may refer to each other. if( !obj.external && t instanceof TypeStruct ts ) for( Field f : ts._fields ) - if( !f._extern && f._t.isConstant() ) target(f._t); + if( !f._extern && f._t.isConstant() ) { + target(f._t); + if( clz && f._final && f._t instanceof TypeMemPtr ptr && + pointerConstant(ptr) && !isClass(ptr._obj) ) + object(ptr._obj).debugNames.add(ts._name.substring(TypeStruct.CLZ.length())+"."+f._fname); + } return obj; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index a86cd18a..418edaf6 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -21,12 +21,14 @@ abstract class TypeCheck { Ary errs = new Ary<>(Node.class); Ary constructs = new Ary<>(ConstructNode.class); Ary views = new Ary<>(InitViewNode.class); + Ary arrays = new Ary<>(ArrayInitNode.class); code._stop.walk( n -> { if( n.err() != null ) errs.add(n); if( n instanceof CLInitNode ) code.add(n); if( n instanceof ConstructNode con ) constructs.add(con); if( n instanceof InitViewNode view ) views.add(view); + if( n instanceof ArrayInitNode array ) arrays.add(array); return null; }); @@ -57,13 +59,15 @@ abstract class TypeCheck { if( !con.isDead() ) con.subsume(con.in(1)); for( InitViewNode view : views ) if( !view.isDead() ) view.subsume(view.in(1)); + for( ArrayInitNode array : arrays ) + if( !array.isDead() ) array.subsume(array.in(2)); } private static int errorRank(Node n) { // Bad memory access originates the error. Missing construction fields // in turn explain generic-scalar arithmetic further downstream. if( n instanceof MemOpNode && noBottomInputs(n) ) return 0; - if( n instanceof ConstructNode ) return 1; + if( n instanceof ConstructNode || n instanceof ArrayInitNode ) return 1; return noBottomInputs(n) ? 2 : 3; } diff --git a/src/main/java/com/seaofnodes/simple/node/ArrayInitNode.java b/src/main/java/com/seaofnodes/simple/node/ArrayInitNode.java new file mode 100644 index 00000000..c6ae90ea --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ArrayInitNode.java @@ -0,0 +1,70 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.parser.Lexer; +import com.seaofnodes.simple.parser.Parser; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; + +/** Source checks for array construction and its yielded elements. Erased by + * TypeCheck before serialization and scheduling. */ +public final class ArrayInitNode extends Node { + private final int _count; // List size, -1 for a generator, -2 for a yielded element. + private final Lexer _loc; + public ArrayInitNode(Node ctrl, Node mem, Node ptr, Node len, int count, Lexer loc, Ary values) { + super(ctrl,mem,ptr,len); + _count=count; _loc=loc; + for( Node value : values ) addDef(value); + } + public ArrayInitNode(Node ctrl, Node value, Lexer loc) { + super(ctrl,null,value); + _count=-2; _loc=loc; + } + @Override public String label() { return "ArrayInit"; } + @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p("arrayInit(").n(in(2)).p(")"); } + @Override public Type compute() { + if( in(0)._type != Type.CONTROL ) return Type.TOP; + Type ptr = in(2)._type; + if( _count < 0 ) return ptr; + // A list is strict in all its inputs. Wait for every input before + // choosing a constant payload or falling to the ordinary array type. + // Otherwise one SCCP worklist order can return PtrTop (or an array) + // before another unresolved input sends the result back up to Top. + if( ptr.isHigh() || in(3)._type.isHigh() ) return Type.TOP; + for( int i = 4; i < nIns(); i++ ) + if( in(i)._type.isHigh() ) return Type.TOP; + if( !(ptr instanceof TypeMemPtr tmp) ) return ptr; + Field body = tmp._obj.field("[]"); + if( body == null || !body._final || !(body._t instanceof TypeInteger storage) ) return ptr; + if( !(in(3)._type instanceof TypeInteger length) || !length.isConstant() || length.value() != _count ) return ptr; + long[] values = new long[_count]; + for( int i = 0; i < _count; i++ ) { + Type value = in(i+4)._type; + if( !(value instanceof TypeInteger integer) || !integer.isConstant() ) return ptr; + values[i] = integer.value(); + } + TypeConAry contents = TypeConAry.make(storage,values); + TypeStruct array = TypeStruct.makeAry(tmp._obj._name,tmp._obj.field("#")._alias,body._alias,contents); + // The surrounding ReadOnlyNode supplies the public view. Keep this + // node's access flags consistent when its contents cease to be constant. + return TypeMemPtr.make((byte)2,array,true).withAccess(tmp._ro); + } + @Override public Node idealize() { return null; } + @Override public Parser.ParseException err() { + if( in(0)._type==Type.XCONTROL ) return null; + if( _count==-2 ) + return TypeMemPtr.mayBePartial(in(2)._type) + ? Parser.error("Array initializer requires fully initialized elements",_loc) : null; + if( !(in(3)._type instanceof TypeInteger len) ) + return Parser.error("Array length must be an integer",_loc); + if( len.isConstant() && (len.value()<0 || len.value()>TypeInteger.U32._max) ) + return Parser.error("Array length is outside the u32 range",_loc); + if( _count>=0 && (!len.isConstant() || len.value()!=_count) ) + return Parser.error("Array initializer has "+_count+" elements; length must equal that constant",_loc); + for( int i=4; i