diff options
| author | Cliff Click <cliffc@acm.org> | 2026-08-10 11:11:18 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-11-14 16:23:39 -0800 |
| commit | 207febef9924c8fa5391185e75d42a7ea480bb38 (patch) | |
| tree | 68ec6225a89fa1178c32fdf659b9b4f2c3327288 /src/main/java/com/seaofnodes | |
| parent | 259f60b105eb770bc6f7e3bd36d91f2b217e9315 (diff) | |
| download | Simple-207febef9924c8fa5391185e75d42a7ea480bb38.tar.gz Simple-207febef9924c8fa5391185e75d42a7ea480bb38.zip | |
Chapter 31: Software Drawing, Time, and Graphical Gameslinear
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>
Diffstat (limited to 'src/main/java/com/seaofnodes')
59 files changed, 1097 insertions, 176 deletions
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<Node,Relo> _bigCons = new HashMap<>(); + // Relocations belong to instruction occurrences, including equal constant + // loads cloned by scheduling/register allocation. Structural keys lose sites. + public final IdentityHashMap<Node,Relo> _bigCons = new IdentityHashMap<>(); public final StaticData _data; public final HashMap<String,Integer> _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<Node,CFGNode> _internals = new HashMap<>(); + private final IdentityHashMap<Node,CFGNode> _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<Node,String> _externals = new HashMap<>(); + public final IdentityHashMap<Node,String> _externals = new IdentityHashMap<>(); public Encoding external( Node n, String extern ) { _externals.put(n,extern); return this; } - public final HashMap<Node,String> _externData = new HashMap<>(); + public final IdentityHashMap<Node,String> _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<Node> 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 ? "<root>" : 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<npubTypes; i++ ) { TypeStruct ts = elf._pubTypes[i] = (TypeStruct)types[pubTypeIds[i]]; - Parser.TYPES.put(ts._name,ts); + installType(ts); } elf._functions = new FunctionSummary[bais.packed4()]; for( int i = 0; i<elf._functions.length; i++ ) { @@ -444,6 +444,18 @@ public class Serialize { return elf._types = new TypeRead(types,strs,fileAliases,fileFidxs,fileRpcs); } + private static void installType(TypeStruct ts) { + // TYPES names the mutable array declaration. Read-only arrays in + // imported signatures keep their own types, but must not replace that + // declaration: closeOver looks up its mutable variant by name. + if( ts.isConAry() ) { + TypeConAry ary=(TypeConAry)ts.field("[]")._t; + ts=TypeStruct.makeAry(ts._name,TypeInteger.U32,ts.field("#")._alias, + ary.storageType(),ts.field("[]")._alias,false); + } else if( ts.isAry() ) ts = ts.replace(ts.field("[]").makeFrom(false)); + Parser.TYPES.put(ts._name,ts); + } + static void readAll( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { BAOS bais = elf._bais; TypeRead tread = readTypes(code, elf, aliases, fidxs, rpcs); diff --git a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java index 5d1a519b..3d3a40dd 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/StaticData.java +++ b/src/main/java/com/seaofnodes/simple/codegen/StaticData.java @@ -14,7 +14,10 @@ public final class StaticData { public final String symbol; public final boolean readOnly, external; public final int alignment, size; + // Source names are aliases, not part of the object's pooling identity. + final TreeSet<String> 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<Node> errs = new Ary<>(Node.class); Ary<ConstructNode> constructs = new Ary<>(ConstructNode.class); Ary<InitViewNode> views = new Ary<>(InitViewNode.class); + Ary<ArrayInitNode> 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<Node> 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<Node> _print1(ExprPrinter<Node> 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<nIns(); i++ ) + if( TypeMemPtr.mayBePartial(in(i)._type) ) + return Parser.error("Array initializer requires fully initialized elements",_loc); + return null; + } + @Override public boolean eq(Node n) { return this==n; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index 130b631c..b49163e7 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -261,15 +261,35 @@ public class BulkMemPhiNode extends PhiNode { mphi = new MemPhiNode(ScopeNode.memName(alias),alias); mphi.addDef(region()); // Due to cycles, must set before calling peephole - // Splitting preserves the bulk Phi's established escape bound. Starting - // at BOT would temporarily invent escapes when the new slice is merged. + // An escaped slice must preserve the bulk Phi's established bound. + // An unescaped slice was excluded from that summary: include the + // facts hidden in predecessor slices before wiring any cyclic Phis. TypeMem old = (TypeMem)_type; + if( !XInt.bit(old._escAs,alias) ) + old = (TypeMem)old.meet(sliceBound(this,alias,new BitSet())); mphi.setType(TypeMem.make(alias,old._t,old._one,old._clz,false,old._escFs,old._escAs)); for( int i=1; i<nIns(); i++ ) mphi.addDef(CodeGen.CODE.add(preciseInput(in(i),alias))); return CodeGen.CODE.add(mphi); } + // A bulk summary ignores unescaped slots in MemMerge inputs. Follow the + // same slots that splitting will expose, including across loop backedges. + // A visited cycle contributes TOP; its incoming definitions supply the bound. + private static TypeMem sliceBound(Node mem, int alias, BitSet visit) { + if( visit.get(mem._nid) ) return TypeMem.TOP; + visit.set(mem._nid); + if( mem instanceof MemMergeNode merge ) + return sliceBound(merge.alias(alias),alias,visit); + if( mem instanceof BulkMemPhiNode bulk ) { + TypeMem bound = TypeMem.TOP; + for( int i = 1; i < bulk.nIns(); i++ ) + bound = (TypeMem)bound.meet(sliceBound(bulk.in(i),alias,visit)); + return bound; + } + return mem._type instanceof TypeMem bound ? bound : TypeMem.BOT; + } + MemPhiNode _findPhi(int alias) { for( Node use : region().outs() ) if( use instanceof MemPhiNode mphi && mphi._alias==alias ) diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index b5156c2d..108dd024 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -85,6 +85,8 @@ public class CallEndNode extends CFGNode implements MultiNode { return ftype.isHigh() ? TypeTuple.STATE.dual() : TypeTuple.STATE; // Mid-fold, just take the inlined callee's return. if( _folding ) return in(1)._type; + TypeTuple intrinsic=Intrinsic.compute(call,this); + if( intrinsic!=null ) return intrinsic; // The outside continuation reads Start directly: Call can remain // CONTROL while its possible returned identities change. @@ -135,6 +137,8 @@ public class CallEndNode extends CFGNode implements MultiNode { } public byte maybeInline() { + byte intrinsic=Intrinsic.tryInline(this); + if( intrinsic>0 ) return intrinsic; byte inline = inlineCandidate(false); if( CodeGen.CODE._midAssert ) return inline; diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index ac5e4eee..9e9c5224 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -97,6 +97,7 @@ public class CallNode extends CFGNode { if( _type!=Type.CONTROL ) return TypeMem.BOT; if( !(fptr()._type instanceof TypeFunPtr) ) return fptr()._type.isHigh() ? TypeMem.START : TypeMem.BOT; + if( Intrinsic.pure(this) ) return TypeMem.START; if( !external() ) return TypeMem.START; Type input = dep.addDepForwards(mem())._type; TypeMem escaped = input instanceof TypeMem m ? m : input.isHigh() ? TypeMem.TOP : TypeMem.BOT; @@ -241,6 +242,8 @@ public class CallNode extends CFGNode { return Parser.error("Expected a function, but found " + fptr()._type, _loc); if( !tfp.notNull() ) return Parser.error( "Might be null calling "+tfp, _loc); + Parser.ParseException intrinsic=Intrinsic.err(this); + if( intrinsic!=null ) return intrinsic; if( nargs() != tfp.nargs() ) return Parser.error( "Expecting "+(tfp.nargs()-1)+" arguments, but found "+(nargs()-1), _loc); @@ -253,6 +256,15 @@ public class CallNode extends CFGNode { // Constructors return private memory and carry hidden self and // selfMem arguments ahead of the source-level arguments. int argno = i - (tfp.ret() instanceof TypeMem ? 2 : 0); + // Access qualifiers are not shown by the structural type dump. + // Report the differing permission instead of two huge shapes. + if( arg(i+2)._type instanceof TypeMemPtr actual && actual._ro && + tfp.arg(i) instanceof TypeMemPtr formal && !formal._ro ) { + String who = i == 0 ? name() == null ? "Receiver" : "Receiver for method '"+name()+"'" + : "Argument #"+argno; + return Parser.error(who+" is read-only "+actual._obj.str()+ + "; expected writable "+formal._obj.str(),_loc); + } return Parser.error( "Argument #" + argno + " isa " + arg(i+2)._type + ", but must be a " + tfp.arg(i), _loc ); } diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index 57340609..a8a6151c 100644 --- a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -64,6 +64,10 @@ public class EscapeNode extends TypeNode { @Override public Type compute() { + // A static constant array has no private heap writes to publish. + // This depends on its type, regardless of which node produced it. + if( self()!=null && self()._type instanceof TypeMemPtr ptr && + ptr.isConstant() && ptr._obj.isConAry() ) return pub()._type; if( priv()._type.isHigh() ) return TypeMem.TOP; if( pub ()._type.isHigh() ) return TypeMem.TOP; TypeMem mpriv = (TypeMem)priv()._type; @@ -100,6 +104,8 @@ public class EscapeNode extends TypeNode { } @Override public Node idealize() { + if( self()._type instanceof TypeMemPtr ptr && ptr.isConstant() && ptr._obj.isConAry() ) + return pub(); // Sharpen private memory input if( priv() instanceof MemMergeNode mmm ) { setDef(2,mmm.alias(fld()._alias)); diff --git a/src/main/java/com/seaofnodes/simple/node/Intrinsic.java b/src/main/java/com/seaofnodes/simple/node/Intrinsic.java new file mode 100644 index 00000000..82626507 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/Intrinsic.java @@ -0,0 +1,119 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.parser.Parser; +import com.seaofnodes.simple.type.*; + +// Fixed-semantics C functions. Recognition, effects and expansion live here; +// Call/CallEnd only delegate. These symbols also have ordinary C definitions +// for calls whose target is not known at compile time. +public final class Intrinsic { + private Intrinsic() {} + + private enum Op { + F64_BITS("simple_f64_bits",TypeFloat.F64,TypeInteger.BOT,true), + F64_FROM_BITS("simple_f64_from_bits",TypeInteger.BOT,TypeFloat.F64,true); + + final String symbol; + final Type arg, ret; + final boolean pure; + Op(String symbol, Type arg, Type ret, boolean pure) { + this.symbol=symbol; this.arg=arg; this.ret=ret; this.pure=pure; + } + boolean signature(TypeFunPtr fp) { + // Slot zero is the implicit receiver, omitted by the C ABI. + return fp.nargs()==2 && fp.arg(1)==arg && fp.ret()==ret; + } + Expansion expand(CallNode call) { + Node value=switch(this) { + case F64_BITS -> new F64BitsNode(call.arg(3)).peephole(); + case F64_FROM_BITS -> new F64FromBitsNode(call.arg(3)).peephole(); + }; + return new Expansion(call.ctrl(),call.mem(),value); + } + } + + private static Op lookup(CallNode call) { + if( !(call.fptr()._type instanceof TypeFunPtr fp) || !fp.notNull() || !fp.isConstant() ) return null; + String symbol=CodeGen.CODE.externFunc(fp.fidx()); + if( symbol==null ) return null; // A Simple function with this name is ordinary code. + for( Op op : Op.values() ) if( op.symbol.equals(symbol) ) return op; + return null; + } + + public static Parser.ParseException err(CallNode call) { + Op op=lookup(call); + return op==null || op.signature(call.tfp()) ? null : Parser.error( + "Intrinsic '"+op.symbol+"' requires { "+op.arg.str()+" -> "+op.ret.str()+" }",call._loc); + } + + // Both initial operations are pure and expose no references. Future atomic + // operations need their own memory/escape semantics, not this passthrough. + public static boolean pure(CallNode call) { + Op op=lookup(call); + return op!=null && op.pure && op.signature(call.tfp()); + } + + public static TypeTuple compute(CallNode call, Node dep) { + if( !pure(call) ) return null; + return TypeTuple.make(Type.CONTROL,dep.addDep(call.mem())._type,call.tfp().ret()); + } + + // An expansion replaces the complete call state, even for a pure value op. + private record Expansion(Node control, Node memory, Node value) { + void replace(CallEndNode end) { + Node[] state={control,memory,value}; + for( Node n : state ) n.keep(); + end.keep(); + for( Node use : end._outputs.asAry() ) { + if( use==null ) continue; // Our temporary keep. + assert use instanceof Proj; + use.subsume(state[((Proj)use).idx()]); + } + end.unkill(); + for( Node n : state ) n.unkill(); + CodeGen.CODE.invalidateIDepthCaches(); + } + } + + // Same cheap-inlining worklist as ordinary functions, but no body/Return, + // cloning, size heuristic, or import loading is needed. + public static byte tryInline(CallEndNode end) { + if( end.folding() || !(end.in(0) instanceof CallNode call) ) return 0; + Op op=lookup(call); + if( op==null || !op.signature(call.tfp()) || call.nargs()!=call.tfp().nargs() || + !end.goodArgs(call,call.tfp()) ) return 0; + if( !CodeGen.CODE._midAssert ) op.expand(call).replace(end); + return 1; + } + + public abstract static class BitCastNode extends Node { + BitCastNode(Node value) { super(null,value); } + public abstract boolean toBits(); + @Override public Type compute() { + Type input=in(1)._type; + Type result=toBits() ? TypeInteger.BOT : TypeFloat.F64; + if( input.isHigh() ) return result.dual(); + if( toBits() && input instanceof TypeFloat f && f.isConstant() ) + return TypeInteger.constant(Double.doubleToRawLongBits(f.value())); + if( !toBits() && input instanceof TypeInteger i && i.isConstant() ) + return TypeFloat.constant(Double.longBitsToDouble(i.value())); + return result; + } + @Override public Node idealize() { + return in(1) instanceof BitCastNode cast && cast.toBits()!=toBits() ? cast.in(1) : null; + } + } + public static final class F64BitsNode extends BitCastNode { + public F64BitsNode(Node value) { super(value); } + @Override public boolean toBits() { return true; } + @Override public Tag serialTag() { return Tag.F64Bits; } + @Override protected String format() { return "f64Bits(%1)"; } + } + public static final class F64FromBitsNode extends BitCastNode { + public F64FromBitsNode(Node value) { super(value); } + @Override public boolean toBits() { return false; } + @Override public Tag serialTag() { return Tag.F64FromBits; } + @Override protected String format() { return "f64FromBits(%1)"; } + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index eb78ed1f..14efa315 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -98,7 +98,15 @@ public class LoadNode extends MemOpNode { t = mem._alias==_alias ? mem._t : actual==null ? TypeScalar.BOT : actual._t; } else if( mem._alias==_alias ) t = t.join(mem._t); - if( !mem._one ) t = mem.outside(t); + // A final method's identity comes from its declaration, not from an + // unknown outside writer. It remains callable on a local object even + // when that function has never escaped to outside code. + if( !mem._one ) { + Type declared = Parser.TYPES.get(tmp._obj._name); + Field field = declared instanceof TypeStruct obj ? obj.field(_name) : null; + if( !(field != null && field._final && field._t instanceof TypeFunPtr fun && fun.isConstant()) ) + t = mem.outside(t); + } // Store forwarding is also a value fact during SCCP. Waiting for the // later rewrite can turn a known non-null stored pointer into a // nullable declaration, then BOTTOM at the next dereference. @@ -364,15 +372,13 @@ public class LoadNode extends MemOpNode { if( ptr instanceof PhiNode pphi && pphi.region() == r ) return true; - // No, so can we lift this ptr? - CFGNode cptr = ptr.cfg0(); - if( cptr != null ) - // Pointer is controlled high - // TODO: Really needs to be the LCA of all inputs is high - return cptr.idepth() <= r.idepth(); - - // Dunno without a longer walk - return false; + // Each copied Load needs its pointer before the Region, including + // a loop's entry arm. input 0 alone misses floating Loads whose own + // pointer was produced inside the loop. + CFGNode pinned = ptr.cfg0(); + if( pinned==null || pinned.idepth()>r.idepth() ) return false; + CFGNode cptr = ptr instanceof PhiNode phi ? phi.region() : CFGNode.earlyCFG(ptr); + return cptr==null || cptr.dominates(r.idom(memphi),memphi); } @Override public Parser.ParseException err() { diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index aa3f6d57..19420839 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -20,8 +20,20 @@ public class MemMergeNode extends Node { public MemMergeNode( Node ...nodes) { super(nodes); _type = TypeMem.BOT; } public MemMergeNode(MemMergeNode mem) { super(mem); } @Override public Tag serialTag() { return Tag.MemMerge; } - public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { baos.packed1(nIns()); } - static Node make( BAOS bais ) { Node mem = new MemMergeNode(); mem.setDefX(bais.packed1()-1,null); return mem; } + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + // A memory merge always has inputs. Zero escapes a wide alias table, + // preserving every existing nonzero single-byte count. + assert nIns()>0; + baos.packed1(nIns()<=255 ? nIns() : 0); + if( nIns()>255 ) baos.packed4(nIns()); + } + static Node make( BAOS bais ) { + int count=bais.packed1(); + if( count==0 ) count=bais.packed4(); + Node mem=new MemMergeNode(); + mem.setDefX(count-1,null); + return mem; + } @Override public String label() { return "ALLMEM"; } @Override public boolean isMem() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 35183380..bce11b50 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -94,7 +94,8 @@ public abstract class MemOpNode extends TypeNode { if( !(ptr()._type instanceof TypeMemPtr tmp) ) return Type.BOTTOM; Field fld = tmp._obj.field(_name); - return fld == null || fld._t == null ? Type.BOTTOM : fld._t; + return fld == null || fld._t == null ? Type.BOTTOM : + fld._t instanceof TypeConAry ary ? ary.storageType() : fld._t; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return _printMach(p); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 2815dfba..d4c0794c 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -77,7 +77,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { New,Never,Not,Or,Parm,Phi,Proj,PtrToInt, ReadOnly,Return,Region,RoundF32, Sar,Shl,Shr,Start,StartCU,StopCU,Stop,Store,Sub, - ToInteger,ToFloat,XCtrl,Xor; + ToInteger,ToFloat,XCtrl,Xor,F64Bits,F64FromBits; public static final Tag[] VALS = values(); public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { return switch(this) { @@ -103,6 +103,8 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { case Sub -> new SubNode(null,null,(byte)bais.packed1()); case ToFloat-> new ToFloatNode(null); case ToInteger-> new ToIntegerNode(null); + case F64Bits-> new Intrinsic.F64BitsNode(null); + case F64FromBits-> new Intrinsic.F64FromBitsNode(null); case XCtrl -> new XCtrlNode(); case Xor -> { int mode=bais.packed1(); assert mode==1; yield new XorNode(null,null,null); } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 010d5f61..204e0c4b 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -243,6 +243,10 @@ public class StoreNode extends MemOpNode { private byte storageType() { if( !(ptr()._type instanceof TypeMemPtr tmp) ) return 0; + // Completing a forward declaration changes TYPES without changing + // this Store's inputs. Wait for the pointer's type upgrade, which + // queues its users, before consulting the completed declaration. + if( tmp._obj._fref ) return 0; TypeStruct obj = (TypeStruct)Parser.TYPES.get(tmp._obj._name); Field fld = obj.field(_name); if( fld == null || fld._t == null ) diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/BitCastARM.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/BitCastARM.java new file mode 100644 index 00000000..ec57b3f8 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/BitCastARM.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node.cpus.arm; + +import com.seaofnodes.isa.Arm64; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.util.SB; + +// A representation move, with no arithmetic, rounding, or flag changes. +public class BitCastARM extends MachConcreteNode implements MachNode { + private final boolean _toBits; + BitCastARM(Intrinsic.BitCastNode cast) { super(cast); _toBits=cast.toBits(); } + @Override public String op() { return _toBits ? "f64bits" : "f64frombits"; } + @Override public RegMask regmap(int i) { assert i==1; return _toBits ? arm.DMASK : arm.RMASK; } + @Override public RegMask outregmap() { return _toBits ? arm.WMASK : arm.DMASK; } + @Override public void encoding(Encoding enc) { + enc.add4(Arm64.f_mov_general(Arm64.OP_FMOV,0b01,0,_toBits ? 0b110 : 0b111, + enc.reg(in(1))-(_toBits ? arm.D_OFFSET : 0), + enc.reg(this)-(_toBits ? 0 : arm.D_OFFSET))); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = bits ").p(code.reg(in(1))); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index ee7b0fc3..2d47edf5 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -350,6 +350,7 @@ public class arm extends Machine { case StoreNode st -> st(st); case SubNode sub -> sub.mode()==2 ? new SubFARM(sub) : sub(sub); case ToFloatNode tfn -> new I2F8ARM(tfn); + case Intrinsic.BitCastNode cast -> new BitCastARM(cast); case ToIntegerNode cvt -> new F8ToIARM(cvt); case XorNode xor -> xor(xor); diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BitCastRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BitCastRISC.java new file mode 100644 index 00000000..141ff7d5 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/BitCastRISC.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node.cpus.riscv; + +import com.seaofnodes.isa.RiscV; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.util.SB; + +// A representation move, with no arithmetic, rounding, or flag changes. +public class BitCastRISC extends MachConcreteNode implements MachNode { + private final boolean _toBits; + BitCastRISC(Intrinsic.BitCastNode cast) { super(cast); _toBits=cast.toBits(); } + @Override public String op() { return _toBits ? "f64bits" : "f64frombits"; } + @Override public RegMask regmap(int i) { assert i==1; return _toBits ? riscv.FMASK : riscv.RMASK; } + @Override public RegMask outregmap() { return _toBits ? riscv.WMASK : riscv.FMASK; } + @Override public void encoding(Encoding enc) { + enc.add4(RiscV.r_type(RiscV.OP_FP, + enc.reg(this)-(_toBits ? 0 : riscv.F_OFFSET),0, + enc.reg(in(1))-(_toBits ? riscv.F_OFFSET : 0),0,_toBits ? 0b1110001 : 0b1111001)); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = bits ").p(code.reg(in(1))); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SplitRISC.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SplitRISC.java index d455337b..de754393 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SplitRISC.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/SplitRISC.java @@ -47,7 +47,7 @@ public class SplitRISC extends SplitNode { // FPR->FPR src -= riscv.F_OFFSET; dst -= riscv.F_OFFSET; - enc.add4(RiscV.r_type(RiscV.OP_FP, dst, 0b000, src, src, 0b0010101)); // dst = FMIN(src,src) + enc.add4(RiscV.r_type(RiscV.OP_FP, dst, 0b000, src, src, 0b0010001)); // FSGNJ.D preserves NaN bits. } else if(!srcX && dstX) { //GPR->FPR // fmv.d.x diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 378955a5..976d1a52 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -254,6 +254,7 @@ public class riscv extends Machine { case StoreNode st -> st(st); case SubNode sub -> sub.mode()==2 ? new SubFRISC(sub) : sub(sub); case ToFloatNode tfn -> i2f8(tfn); + case Intrinsic.BitCastNode cast -> new BitCastRISC(cast); case ToIntegerNode cvt -> new F8ToIRISC(cvt); case XorNode xor -> xor(xor); diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/BitCastX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/BitCastX86.java new file mode 100644 index 00000000..bf550032 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/BitCastX86.java @@ -0,0 +1,23 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.isa.X86; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.util.SB; + +// A representation move, with no arithmetic, rounding, or flag changes. +public class BitCastX86 extends MachConcreteNode implements MachNode { + private final boolean _toBits; + BitCastX86(Intrinsic.BitCastNode cast) { super(cast); _toBits=cast.toBits(); } + @Override public String op() { return _toBits ? "f64bits" : "f64frombits"; } + @Override public RegMask regmap(int i) { assert i==1; return _toBits ? x86_64_v2.XMASK : x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return _toBits ? x86_64_v2.WMASK : x86_64_v2.XMASK; } + @Override public void encoding(Encoding enc) { + X86.move(enc,!_toBits,_toBits, + enc.reg(this)-(_toBits ? 0 : x86_64_v2.XMM_OFFSET), + enc.reg(in(1))-(_toBits ? x86_64_v2.XMM_OFFSET : 0)); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" = bits ").p(code.reg(in(1))); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java index 10cee059..ae725659 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/JmpX86.java @@ -9,6 +9,7 @@ import com.seaofnodes.simple.util.Utils; // Jump on flags, uses flags public class JmpX86 extends IfNode implements MachNode, RIPRelSize { String _bop; + boolean _unsigned, _floating, _unorderedTaken; JmpX86( IfNode iff, String bop ) { super(iff); _bop = bop; @@ -23,29 +24,47 @@ public class JmpX86 extends IfNode implements MachNode, RIPRelSize { if( set instanceof SetX86 setx && (cmp instanceof CmpX86 || cmp instanceof CmpIX86 || cmp instanceof CmpMemX86 || cmp instanceof CmpFX86) ) { _inputs.set( 1, cmp ); _bop = setx._bop; + _unsigned = setx._unsigned; + _floating = cmp instanceof CmpFX86; + _unorderedTaken = _bop.equals("!="); } else throw Utils.TODO(); } @Override public RegMask regmap(int i) { assert i==1; return x86_64_v2.FLAGS_MASK; } @Override public RegMask outregmap() { return null; } - @Override public void negate() { _bop = negate(_bop); } + @Override public void negate() { + _bop = negate(_bop); + if( _floating ) _unorderedTaken = !_unorderedTaken; + } + + private int condition() { return x86_64_v2.jumpop(_bop,_unsigned)&15; } @Override public void encoding( Encoding enc ) { if( in(1)==null && _bop=="!=" ) return; - X86.branch(enc,in(1)==null ? -1 : x86_64_v2.jumpop(_bop)&15); + // UCOMISD sets CF/ZF/PF, not signed-integer SF/OF. Handle unordered + // separately, including when layout has negated the original test. + if( _floating ) { + if( _unorderedTaken ) enc.add1(0x0F).add1(0x8A).add4(0); // JP target + else enc.add1(0x7A).add1(0); // JP past the ordered jump + } + X86.branch(enc,in(1)==null ? -1 : condition()); enc.jump(this,cproj(0)); } // Delta is from opcode start, but X86 measures from the end of the 2-byte encoding @Override public byte encSize(int delta) { if( in(1)==null && _bop=="!=" ) return 0; - return X86.branchSize(delta,in(1)!=null); + int prefix = !_floating ? 0 : _unorderedTaken ? 6 : 2; + return (byte)(prefix + X86.branchSize(delta-prefix,in(1)!=null)); } // Delta is from opcode start @Override public void patch( Encoding enc, int opStart, int opLen, int delta ) { assert !(in(1)==null && _bop=="!="); - X86.patchBranch(enc.bits(),opStart,opLen,delta,in(1)==null ? -1 : x86_64_v2.jumpop(_bop)&15); + int prefix = !_floating ? 0 : _unorderedTaken ? 6 : 2; + if( _floating ) + X86.patchBranch(enc.bits(),opStart,prefix,_unorderedTaken ? delta : opLen,10); + X86.patchBranch(enc.bits(),opStart+prefix,opLen-prefix,delta-prefix,in(1)==null ? -1 : condition()); } @Override public void asm(CodeGen code, SB sb) { diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index fcca7f8f..b0ecd685 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -67,9 +67,9 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base in GPR if( i==3 ) return x86_64_v2.RMASK; // index in GPR - if( i==4 ) return _sz >= '4' - ? x86_64_v2.MEM_MASK // value in GPR or XMM - : x86_64_v2.RMASK; // Bytes and shorts in GPR only + // Integer arithmetic and comparisons require a GPR value operand. + // Only StoreX86 has alternate encodings that accept XMM values. + if( i==4 ) return x86_64_v2.RMASK; return null; // Anti-dependence } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegFX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegFX86.java new file mode 100644 index 00000000..61662fd2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegFX86.java @@ -0,0 +1,25 @@ +package com.seaofnodes.simple.node.cpus.x86_64_v2; + +import com.seaofnodes.isa.X86; +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeFloat; +import com.seaofnodes.simple.util.SB; + +// Flip the sign bit, preserving signed zero, infinities, and NaN payloads. +public class NegFX86 extends MachConcreteNode implements MachNode { + NegFX86(MinusNode neg) { + super(neg); + addDef(new FltX86(new ConstantNode(TypeFloat.constant(-0.0)),null)); + } + @Override public String op() { return "negf"; } + @Override public RegMask regmap(int i) { assert i==1 || i==2; return x86_64_v2.XMASK; } + @Override public RegMask outregmap() { return x86_64_v2.XMASK; } + @Override public int twoAddress() { return 1; } + @Override public void encoding(Encoding enc) { + X86.sse(enc,0x66,0x0F57,false,enc.reg(this)-x86_64_v2.XMM_OFFSET,enc.reg(in(2))-x86_64_v2.XMM_OFFSET); + } + @Override public void asm(CodeGen code, SB sb) { + sb.p(code.reg(this)).p(" ^= ").p(code.reg(in(2))).p(" // sign bit"); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegX86.java index 86610f6d..4494985d 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NegX86.java @@ -9,7 +9,7 @@ public class NegX86 extends MachConcreteNode implements MachNode { NegX86(MinusNode not) { super(not); } @Override public String op() { return "neg"; } @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } - @Override public RegMask outregmap() { return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } @Override public RegMask killmap() { return x86_64_v2.FLAGS_MASK; } @Override public int twoAddress() { return 1; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java index 1e4e7c26..1291cf78 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -9,7 +9,7 @@ public class NotX86 extends MachConcreteNode implements MachNode { NotX86(NotNode not) { super(not); } @Override public String op() { return "not"; } @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; } - @Override public RegMask outregmap() { return x86_64_v2.RMASK; } + @Override public RegMask outregmap() { return x86_64_v2.WMASK; } @Override public RegMask killmap() { return x86_64_v2.FLAGS_MASK; } @Override public void encoding( Encoding enc ) { diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java index 864c1b55..bcc4880b 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/SetX86.java @@ -4,7 +4,6 @@ import com.seaofnodes.isa.X86; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.util.SB; -import com.seaofnodes.simple.util.Utils; // Corresponds to the x86 instruction "sete && setne". // Use result of comparison without jump. @@ -25,15 +24,14 @@ public class SetX86 extends MachConcreteNode implements MachNode { @Override public RegMask outregmap() { return x86_64_v2.WMASK; } @Override public void encoding( Encoding enc ) { - int op=switch (_bop) { - case "==" -> 0x94; // SETE - case "<" -> _unsigned ? 0x92 : 0x9C; // SETB /SETL - case "<=" -> _unsigned ? 0x96 : 0x9E; // SETBE/SETLE - case ">=" -> _unsigned ? 0x93 : 0x9D; // SETAE/SETGE - case ">" -> _unsigned ? 0x97 : 0x9F; // SETA /SETG - default -> throw Utils.TODO(); - }; - X86.set(enc,op&15,enc.reg(this)); + int dst=enc.reg(this); + if( in(1) instanceof CmpFX86 ) { + // MOV preserves comparison flags; unordered is true only for !=. + X86.unary(enc,0xC7,0,dst); + enc.add4(_bop.equals("!=") ? 1 : 0); + enc.add1(0x7A).add1(dst>=4 ? 8 : 6); // JP past SETcc/MOVZX + } + X86.set(enc,x86_64_v2.jumpop(_bop,_unsigned)&15,dst); } @Override public void asm(CodeGen code, SB sb) { diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java index 9ffa25fc..8dfd31e7 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/StoreX86.java @@ -25,6 +25,9 @@ public class StoreX86 extends MemOpX86 { } // Register mask allowed as a result. 0 for no register. @Override public RegMask outregmap() { return null; } + @Override public RegMask regmap(int i) { + return i==4 && _sz>='4' ? x86_64_v2.MEM_MASK : super.regmap(i); + } @Override public void encoding( Encoding enc ) { short ptr=enc.reg(ptr()), idx=enc.reg(idx()), src=enc.reg(val()); if( src==-1 ) X86.storeImm(enc,Integer.numberOfTrailingZeros(_sz-'0'),_imm,ptr,idx,_off,_scale); diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 3d71b4ea..dc15b185 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -87,6 +87,18 @@ public class x86_64_v2 extends Machine { default -> throw new IllegalArgumentException("Too many arguments"); }; } + static int jumpop(String op, boolean unsigned) { + if( !unsigned ) return jumpop(op); + return switch( op ) { + case "==" -> 0x84; + case "!=" -> 0x85; + case "<" -> 0x82; + case "<=" -> 0x86; + case ">" -> 0x87; + case ">=" -> 0x83; + default -> throw new IllegalArgumentException(op); + }; + } // Limit of float args passed in registers static RegMask[] XMMS8 = new RegMask[]{ @@ -282,6 +294,7 @@ public class x86_64_v2 extends Machine { public Node instSelect(Node n) { return switch (n) { case AddNode add -> add(add); + case Intrinsic.BitCastNode cast -> new BitCastX86(cast); case AndNode and -> and(and); case BoolNode bool -> cmp(bool); case CLInitNode init -> new CLInitNode(init); @@ -298,10 +311,7 @@ public class x86_64_v2 extends Machine { case IfNode iff -> jmp(iff); case LoadNode ld -> ld(ld); case MemMergeNode mem -> new MemMergeNode(mem); - case MinusNode neg -> { - if( neg.mode()==2 ) throw Utils.TODO(); - yield new NegX86(neg); - } + case MinusNode neg -> neg.mode()==2 ? new NegFX86(neg) : new NegX86(neg); case MulNode mul -> mul.mode()==2 ? new MulFX86(mul) : mul(mul); case NewNode nnn -> new NewX86(nnn); case NotNode not -> new NotX86(not); @@ -370,8 +380,9 @@ public class x86_64_v2 extends Machine { private Node _lea(Node add, Node base, Node idx, int off) { int scale = 0; - if( base instanceof ShlNode && !(idx instanceof ShlNode) ) - throw Utils.TODO(); // Bug in canonicalization, should on RHS + if( base instanceof ShlNode && !(idx instanceof ShlNode) ) { + Node tmp = base; base = idx; idx = tmp; + } if( idx instanceof ShlNode shift && shift.in(2) instanceof ConstantNode shfcon && shfcon._con instanceof TypeInteger tscale && 0 <= tscale.value() && tscale.value() <= 3 ) { idx = shift.in(1); diff --git a/src/main/java/com/seaofnodes/simple/parser/Allocations.java b/src/main/java/com/seaofnodes/simple/parser/Allocations.java index 861f95b6..64234045 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Allocations.java +++ b/src/main/java/com/seaofnodes/simple/parser/Allocations.java @@ -25,11 +25,20 @@ final class Allocations { } // Parse ary[ length_expr ] if( P.match("[") ) { - if( !t.makeZero().isa(t) ) - throw Parser.error("Cannot allocate a non-nullable, since arrays are always zero/null filled",site); + boolean readonly = P.match("~"); + if( P.match("]") ) { + P.require("{"); + return P.arrays.parse(t,readonly,null,site); + } Node len = P.expressions.parseAssignment().keep(); P.require("]"); + if( P.match("{") ) return P.arrays.parse(t,readonly,len,site); + if( !t.makeZero().isa(t) ) + throw Parser.error("Cannot allocate a non-nullable, since arrays are always zero/null filled",site); + if( readonly ) return new ReadOnlyNode(allocArray(P.types.typeAry(t,true),len)).peephole(); return allocArray(P.types.typeAry(t,false),len); + } else if( t instanceof TypeMemPtr ary && ary._obj.isAry() && P.match("{") ) { + return P.arrays.parse(ary._obj.field("[]")._t,ary._ro,null,site); } else { if( !(t instanceof TypeMemPtr tmp) ) throw Parser.error("Cannot allocate a "+t.str(),site); @@ -101,8 +110,6 @@ final class Allocations { // TODO: Needs runtime check. Node st = P.peep(new StoreNode(null, "#", 1, TypeInteger.U32, null, smem, self, ConFldOffNode.make(ts,"#"), len.unkeep(), true)); - // TODO: Allow add-on "constructor" to init the array elements - Node prior = P.mem(); Node esc = P.peep(new EscapeNode(lenFld,self,st,prior)); P.mem(P.mergeAlias(prior,lenFld._alias,esc)); @@ -117,7 +124,7 @@ final class Allocations { TypeStruct ts = P.types.typeAry(TypeInteger.U8,true); int lenAlias = ts.field("#" )._alias; int elemAlias = ts.field("[]")._alias; - TypeConAryB body = TypeConAryB.make(s); + TypeConAry body = TypeConAry.make(s); TypeInteger slen = TypeInteger.constant(s.length); // Make a TMP, not-null (byte)2, singleton (true) (requires text // strings are hash-interned), with a TypeStruct having a constant diff --git a/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java b/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java new file mode 100644 index 00000000..079853cd --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/parser/ArrayInitializers.java @@ -0,0 +1,187 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.ScopeNode.Kind; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; + +/** Array construction keeps the destination private until all elements exist. + * A generator is a scoped, immediately executed loop body, not an escaping closure. */ +final class ArrayInitializers { + private final Parser P; + Frame _frame; + + static final class Frame { + final Kind.Block _kind; + final int _depth; + final Var _value; + ScopeNode _returns; + Frame(Kind.Block kind, int depth, Var value) { + _kind=kind; _depth=depth; _value=value; + } + } + + ArrayInitializers(Parser P) { this.P=P; } + + // Opening brace consumed; an absent length means a list with inferred size. + Node parse(Type elem, boolean readonly, Node len, Lexer site) { + int pos=P.pos(); + Type indexType=P.types.parseType(); + String index=indexType==null ? null : P._lexer.matchId(); + boolean generator=index!=null && P.match("->"); + if( !generator ) P.pos(pos); + if( generator && Parser.KEYWORDS.contains(index) ) + throw Parser.error("Expected an array index name",site); + if( generator && (indexType!=TypeInteger.BOT && indexType!=TypeInteger.I32 && indexType!=TypeInteger.U32) ) + throw Parser.error("Array generator index must be int, i64, or u32",site); + if( generator && len==null ) + throw Parser.error("Array generator requires a length",site); + + Ary<Node> values=new Ary<>(Node.class); + if( !generator ) { + if( !P.peek('}') ) do { + values.add(P.conversions.convertExpr(P.expressions.parseAssignment(),elem).keep()); + } while( P.match(",") && !P.peek('}') ); + P.require("}"); + if( len==null ) len=P.con(values.size()).keep(); + } + + TypeStruct ts=P.types.typeAry(elem,readonly); + Field body=ts.field("[]"), length=ts.field("#"); + Node size=new AddNode(ConFldOffNode.make(ts,"[]"), + new ShlNode(null,len,P.con(ts.aryScale())).peephole()).peephole(); + NewNode alloc=new NewNode(ts,P.ctrl(),size).init(); + Node self=new ProjNode(alloc,0,ts.str()).init().keep(); + Node mem=new ProjNode(alloc,1,"#arrayMem").init().keep(); + Node slen=new StoreNode(site,"#",length._alias,TypeInteger.U32,null,mem,self, + ConFldOffNode.make(ts,"#"),len,true).peephole().keep(); + + if( generator ) { + mem=generator(ts,self,mem,len,index,indexType,site); + } else { + for( int i=0; i<values.size(); i++ ) { + Node st=store(ts,self,mem,P.con(i),values.at(i),site).keep(); + mem.unkeep(); + mem=st; + } + } + + Node result=new ArrayInitNode(P.ctrl(),mem,self,len, + generator ? -1 : values.size(),site,values).peephole().keep(); + Node prior=P.mem(); + P.mem(P.mergeAlias(prior,length._alias,new EscapeNode(length,result,slen.unkeep(),prior).peephole())); + prior=P.mem(); + P.mem(P.mergeAlias(prior,body._alias,new EscapeNode(body,result,mem,prior).peephole())); + mem.unkeep(); self.unkeep(); len.unkeep(); + for( Node value : values ) value.unkeep(); + result.unkeep(); + return readonly ? new ReadOnlyNode(result).peephole() : result; + } + + private Node store(TypeStruct ts, Node self, Node mem, Node idx, Node value, Lexer site) { + Field fld=ts.field("[]"); + Node off=new AddNode(ConFldOffNode.make(ts,"[]"), + new ShlNode(null,idx,P.con(ts.aryScale())).peephole()).peephole(); + return new StoreNode(site,"[]",fld._alias,fld._t,P.ctrl(),mem,self,off,value,true).peephole(); + } + + private Var define(String name, Type type, boolean fin, Node value, Lexer site) { + if( !P._scope.define(name,type,fin,value,site) ) throw Parser.error("Duplicate name '"+name+"'",site); + return P._scope.lookup(name); + } + + private Node read(Var var) { return P._scope.in(P._scope.update(var,null)); } + + private Node generator(TypeStruct ts, Node self, Node mem, Node len, String name, + Type indexType, Lexer site) { + Frame outer=_frame; + ScopeNode oldBreak=P.statements._breakScope, oldContinue=P.statements._continueScope; + P.statements._breakScope=P.statements._continueScope=null; + Kind.Block kind=new Kind.Block(); + P._scope.push(kind); + // The counter stays wide even when the source index is a narrow int. + // The private memory and result slots cannot be named in source. + Var counter=define("$arrayIndex",TypeInteger.BOT,false,P.con(0),site); + Var memory=define("$arrayMem",TypeMem.makePrivate(Type.BOTTOM),false,mem.unkeep(),site); + Var result=define("$arrayValue",ts.field("[]")._t,false,P.con(Type.TOP),site); + _frame=new Frame(kind,P._scope.depth(),result); + + P.ctrl(new LoopNode(site,null,P.ctrl()).peephole()); + ScopeNode head=P._scope.keep(); + P._xScopes.push(P._scope=P._scope.dup(true)); + Node idx=read(counter).keep(); + Node pred=new BoolNode.LT(idx,len).peephole().keep(); + Node iff=new IfNode(P.ctrl(),pred).peephole().keep(); + CFGNode yes=new CProjNode(iff,0,"True").peephole().keep(); + CFGNode no=(CFGNode)new CProjNode(iff.unkeep(),1,"False").peephole(); + P.ctrl(no); + ScopeNode exit=P._scope.dup(); + P._xScopes.push(exit); + exit.addGuards(no,pred,true); + P.ctrl(yes.unkeep()); + P._scope.addGuards(yes,pred.unkeep(),false); + + P._scope.push(new Kind.Block()); + define(name,indexType,true,new ConvertNode(indexType,idx).peephole(),site); + Node last=P._code.ZERO; + while( !P.peek('}') && !P._lexer.isEOF() ) { + P._code.add(last); + last=P.statements.parseStatement(); + } + P.require("}"); + if( P.ctrl()._type!=Type.XCONTROL ) addReturn(last); + P._scope.pop(); + if( _frame._returns!=null ) { + P._scope.kill(); + P._scope=_frame._returns; + } + Node value=read(result); + // The loop starts with the whole private array memory. Keep that shape + // on the backedge too: mixing it with an element slice yields BOTTOM, + // which would falsely publish every function when the array escapes. + Node prior=read(memory).keep(); + Node st=store(ts,self,prior,idx,value,site); + P._scope.update(memory,P.mergeAlias(prior.unkeep(),ts.field("[]")._alias,st)); + P._scope.update(counter,new AddNode(idx.unkeep(),P.con(1)).peephole()); + P._scope.removeGuards(yes); + head.balanceLoopFRefs(P._scope); + exit.balanceLoopFRefs(P._scope); + head.endLoop(P._scope,exit); + head.unkeep().kill(); + P._xScopes.pop(); + P._xScopes.pop(); + if( !P._xScopes.isEmpty() ) { P._xScopes.pop(); P._xScopes.push(exit); } + P._scope=exit; + Node done=read(memory).keep(); + P._scope.pop(); + _frame=outer; + P.statements._breakScope=oldBreak; + P.statements._continueScope=oldContinue; + return done; + } + + Node addReturn(Node expr) { + Node value=P.conversions.convertExpr(expr,_frame._value.type()); + value=new ArrayInitNode(P.ctrl(),value,P.loc()).peephole().keep(); + P.mem(); // Materialize lazy memory before cloning a return path. + ScopeNode cur=P._scope.dup(); + // Saved paths share Var records with the active scope. Drop locals + // without promoting them, then copy forward references explicitly. + while( cur.depth()>_frame._depth ) cur._pop(); + cur.balanceLoopFRefs(P._scope); + cur.update(_frame._value,value.unkeep()); + if( _frame._returns==null ) _frame._returns=cur; + else { + _frame._returns.balanceLoopFRefs(cur); + cur.balanceLoopFRefs(_frame._returns); + _frame._returns.ctrl(_frame._returns.mergeScopes(cur,P.loc()).peephole()); + } + P.ctrl(P._code.XCTRL); + return P._code.ZERO; + } + + void checkAssignment(Var var, Lexer site) { + if( _frame!=null && var._idx<_frame._kind._lexSize ) + throw Parser.error("Cannot assign captured local '"+var._name+"' in an array generator",site); + } +} diff --git a/src/main/java/com/seaofnodes/simple/parser/Conversions.java b/src/main/java/com/seaofnodes/simple/parser/Conversions.java index fa11311d..72247ca6 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Conversions.java +++ b/src/main/java/com/seaofnodes/simple/parser/Conversions.java @@ -37,7 +37,7 @@ final class Conversions { case TypeFloat tf -> TypeFloat.F64; case TypeMemPtr tmp -> tmp.makeVar(); case TypeFunPtr tfp -> tfp; - case TypeConAry<?> a -> a; + case TypeConAry a -> a; case TypePtr ptr -> TypePtr.PTR; case TypeScalar ts -> TypeScalar.BOT; default -> t; diff --git a/src/main/java/com/seaofnodes/simple/parser/Declarations.java b/src/main/java/com/seaofnodes/simple/parser/Declarations.java index 13fa59b8..473a7c24 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Declarations.java +++ b/src/main/java/com/seaofnodes/simple/parser/Declarations.java @@ -91,6 +91,10 @@ final class Declarations { // expr is a constant function if( t instanceof TypeFunPtr decl && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { t = decl.makeFrom(tfp.fidx()); + // The explicit signature specifies source parameters/return; + // the receiver of a method body is still inferred. + if( expr instanceof FunPtrNode && P.structs.inStructDeclaration() ) + t = ((TypeFunPtr)t).makeFrom(tfp.arg(0),0); FunNode fun = P._code.link(tfp); if( fun != null ) fun.setName(name); // Assign debug name to Simple function diff --git a/src/main/java/com/seaofnodes/simple/parser/Expressions.java b/src/main/java/com/seaofnodes/simple/parser/Expressions.java index 247d974e..6486aba8 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Expressions.java +++ b/src/main/java/com/seaofnodes/simple/parser/Expressions.java @@ -400,7 +400,7 @@ final class Expressions { * Parse integer literal * * <pre> - * integerLiteral: [1-9][0-9]* | [0] + * integerLiteral: [1-9][0-9]* | 0[0-7]* | 0[xX][0-9a-fA-F]+ * floatLiteral: [digits].[digits]?[e [digits]]?[f]? * </pre> */ diff --git a/src/main/java/com/seaofnodes/simple/parser/Functions.java b/src/main/java/com/seaofnodes/simple/parser/Functions.java index 5175acc6..84bd509e 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Functions.java +++ b/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -14,6 +14,11 @@ final class Functions { // Merge all function exits here. ScopeNode _returnScope; + // Instance method headers are available immediately; their bodies need + // the complete field scope, just like explicitly declared constructors. + private record Method(FunPtrNode ptr, Lexer body, Lexer loc, BitSet finals, String[] ids) {} + private Ary<Method> _methods; + Functions(Parser P) { this.P = P; } /** @@ -29,6 +34,7 @@ final class Functions { Ary<String> ids = new Ary<>(String.class); BitSet finals = new BitSet(); Type self = P.types.implicitSelfType(); + if( P.structs.inStructDeclaration() ) self = self.makeRO(); ts.push(self); ids.push(self == TypePtr.PTR ? "#self" : "self"); @@ -38,10 +44,49 @@ final class Functions { parameters(ts,ids,finals,false); // Make a concrete function type, with a fidx TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),Type.BOTTOM,P._code.fidx(P._ref._cname)); + if( P.structs.inStructDeclaration() ) { + FunPtrNode ptr = (FunPtrNode)new FunPtrNode(tfp,P._code._start,null).peephole().keep(); + _methods.push(new Method(ptr,P.loc(),loc,finals,ids.asAry())); + P._lexer.skipTo('{','}',"method body"); + return ptr; + } ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); return new FunPtrNode(tfp,P._code._start,ret).peephole(); } + private void finishMethods() { + if( _methods == null ) return; + Ary<Method> methods = _methods; + Lexer after = P._lexer; + for( Method method : methods ) { + P._lexer = new Lexer(method.body()); + TypeFunPtr sig = (TypeFunPtr)method.ptr()._con; + ReturnNode ret = parseFunctionBody(sig,method.loc(),method.finals(),method.ids()); + method.ptr().setDef(1,ret); + P.require("}"); + } + Ary<FunNode> functions = new Ary<>(FunNode.class); + for( Method method : methods ) functions.add(method.ptr().fun()); + MethodAccess.infer(functions); + for( Method method : methods ) { + ReturnNode ret = method.ptr().ret(); + TypeFunPtr sig = ret.fun().sig(); + method.ptr().peephole(); + // Declarations saw the header before its FunNode existed. + for( Var var : P._scope._vars ) + if( var.type() instanceof TypeFunPtr tfp && tfp.isConstant() && tfp.fidx() == sig.fidx() ) { + ret.fun().setName(var._name); + var.refineType(var.type().join(method.ptr()._type)); + TypeStruct self = P._scope.constructorSelf(); + TypeStruct shape = (TypeStruct)Parser.TYPES.get(self._name); + Parser.TYPES.put(shape._name,shape.replace(shape.field(var._name).makeFrom(var.type()))); + break; + } + method.ptr().unkeep(); + } + P._lexer = after; + } + Node parseConstructor(String name, boolean explicit) { P.require("{"); Ary<Type> ts = new Ary<>(Type.class); @@ -198,9 +243,13 @@ final class Functions { } ReturnNode parseBody( String funName, TypeFunPtr sig, Lexer loc, BitSet finals, String[] ids) { + ArrayInitializers.Frame outerArray = P.arrays._frame; + P.arrays._frame = null; Structs.Constructor outerCtor = P.structs._pendingCtor; P.structs._pendingCtor = null; boolean isInit = FunNode.isInit(funName); + Ary<Method> outerMethods = _methods; + _methods = FunNode.isInstance(funName) ? new Ary<>(Method.class) : null; boolean isCtor = isInit || P.structs.isExplicitConstructorName(funName); String typeName = isCtor ? ((TypeMemPtr)sig._sig[0])._obj._name : null; @@ -233,7 +282,11 @@ final class Functions { nvar = P.structs.updateSelfAsFieldsDiscovered( typeName, nvar ); } - if( isInit ) P.structs.finishConstructor(); + if( isInit ) { + finishMethods(); + P.structs.finishConstructor(); + } + _methods = outerMethods; P.structs._pendingCtor = outerCtor; ParmNode self = fun.parm(2); @@ -275,6 +328,7 @@ final class Functions { P.statements._breakScope = breakScope; P._scope.pop(); P.construction._frame = outerConstruction; + P.arrays._frame = outerArray; return ret; } @@ -300,8 +354,14 @@ final class Functions { // All args, "as-if" called externally for( int i = 0; i<ids.length; i++ ) { Type t = sig.arg(i); + // Parse an implicit receiver with write access, then infer the + // public requirement from its uses once every method is present. + if( i == 0 && ids[0].equals("self") && !FunNode.isInit(funName) && + !(sig.ret() instanceof TypeMem) && t instanceof TypeMemPtr ptr ) + t = ptr.withAccess(false); // Args take a default input if called from Start/external-world - Node parm = new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(fun.defaultArg(i)).peephole()).peephole(); + Type seed = i == 0 && t instanceof TypeMemPtr ? t : fun.defaultArg(i); + Node parm = new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(seed).peephole()).peephole(); if( t instanceof TypeMemPtr ptr && ptr._partial ) parm = new ConstructNode(parm).peephole(); P._scope.define(ids[i], t, (i==0 && ids[0]=="self") || (finals!=null && finals.get(i)), parm, loc); } diff --git a/src/main/java/com/seaofnodes/simple/parser/Lexer.java b/src/main/java/com/seaofnodes/simple/parser/Lexer.java index 5e4b7311..62dd054e 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Lexer.java +++ b/src/main/java/com/seaofnodes/simple/parser/Lexer.java @@ -239,6 +239,7 @@ public class Lexer { // Return a constant Type, either TypeInteger or TypeFloat Type parseNumber() { Lexer start=new Lexer(this); + if( isHex() ) return parseInteger(parseNumberString(),16,2,start); int old = _position; int len = isLongOrDouble(); boolean f32 = peek()=='f'; @@ -250,7 +251,7 @@ public class Lexer { return TypeFloat.constant(Float.parseFloat(literal)); if( len > 0 ) { if( len > 1 && _input[old]=='0' ) - throw Parser.error("Syntax error: integer values cannot start with '0'",start); + return parseInteger(literal,8,0,start); long i = Long.parseLong(literal); return TypeInteger.constant(i); } @@ -262,6 +263,11 @@ public class Lexer { } private String parseNumberString() { int old = _position; + if( isHex() ) { + _position += 2; + while( isIdLetter(peek()) ) inc(); + return new String(_input,old,_position-old); + } int len = Math.abs(isLongOrDouble()); if( peek()=='f' ) { nextChar(); @@ -270,6 +276,24 @@ public class Lexer { return new String(_input,old,len); } + private boolean isHex() { + return peek()=='0' && _position+1<_input.length && (peek(1)=='x' || peek(1)=='X'); + } + + private TypeInteger parseInteger(String literal, int radix, int prefix, Lexer start) { + String kind = radix==16 ? "Hexadecimal" : "Octal"; + if( literal.length()==prefix ) + throw Parser.error(kind+" integer literal requires at least one digit",start); + for( int i=prefix; i<literal.length(); i++ ) + if( Character.digit(literal.charAt(i),radix)<0 ) + throw Parser.error("Invalid "+kind.toLowerCase()+" integer literal '"+literal+"'",start); + try { + return TypeInteger.constant(Long.parseUnsignedLong(literal.substring(prefix),radix)); + } catch( NumberFormatException ex ) { + throw Parser.error(kind+" integer literal exceeds 64 bits",start); + } + } + // Return +len that ends a long // Return -len that ends a double private int isLongOrDouble() { @@ -381,14 +405,19 @@ public class Lexer { precision = formatNumber(site); } char kind=nextChar(); - if( "diuoxXfFeEgGaAcsb".indexOf(kind)<0 ) + if( "diuoxXfFeEgGaAcsbt".indexOf(kind)<0 ) throw Parser.error("Expected a string format: %(expression), %d(expression), or %%",site); boolean number="diuoxXfFeEgGaA".indexOf(kind)>=0; if( !number && (flags&~1)!=0 || "uoxX".indexOf(kind)>=0 && (flags&6)!=0 || "diu".indexOf(kind)>=0 && (flags&8)!=0 ) throw Parser.error("Invalid flags for %"+kind,site); - if( precision>=0 && (kind=='c' || kind=='b') ) + if( precision>=0 && (kind=='c' || kind=='b' || kind=='t') ) throw Parser.error("Precision is not supported for %"+kind,site); + if( kind=='t' && peek()!='(' ) { + int style="FrRMDT".indexOf(nextChar()); + if( style<0 ) throw Parser.error("Expected a time format: %t, %tF, %tr, %tR, %tM, %tD, or %tT",site); + flags |= style<<8; + } if( peek()!='(' ) throw Parser.error("Expected '(' after string format %"+kind,site); inc(); return new Format(kind,flags,width,precision,site); diff --git a/src/main/java/com/seaofnodes/simple/parser/MethodAccess.java b/src/main/java/com/seaofnodes/simple/parser/MethodAccess.java new file mode 100644 index 00000000..099ba036 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/parser/MethodAccess.java @@ -0,0 +1,130 @@ +package com.seaofnodes.simple.parser; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.Ary; +import java.util.ArrayDeque; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Collections; +import java.util.IdentityHashMap; +import java.util.Set; + +/** Infer the access required through an instance method's receiver. */ +final class MethodAccess { + private final FunNode _fun; + private final Set<Node> _aliases = Collections.newSetFromMap(new IdentityHashMap<>()); + private final Set<MethodAccess> _calls = new HashSet<>(); + private boolean _writes; + + private MethodAccess(FunNode fun) { _fun = fun; } + + static void infer(Ary<FunNode> functions) { + HashMap<Integer,MethodAccess> methods = new HashMap<>(); + for( FunNode fun : functions ) methods.put(fun.sig().fidx(),new MethodAccess(fun)); + for( MethodAccess method : methods.values() ) method.scan(methods); + boolean changed; + do { + changed = false; + for( MethodAccess method : methods.values() ) + if( !method._writes ) + for( MethodAccess callee : method._calls ) + if( callee._writes ) { method._writes = true; changed = true; break; } + } while( changed ); + for( MethodAccess method : methods.values() ) method.finish(); + } + + private void scan(HashMap<Integer,MethodAccess> methods) { + if( _fun.parm(2) == null ) return; // Unused receiver. + ArrayDeque<Node> work = new ArrayDeque<>(); + work.add(_fun.parm(2)); + while( !work.isEmpty() ) { + Node value = work.remove(); + if( !_aliases.add(value) ) continue; + for( Node use : value._outputs ) { + if( use == null || use instanceof ReadOnlyNode ) continue; + if( use instanceof StoreNode store ) { + if( store.ptr() == value || store.val() == value ) _writes = true; + } else if( use instanceof CallNode call ) { + for( int i = 2; i < call.nIns()-1; i++ ) + if( call.in(i) == value ) call(call,i-2,methods); + } else if( use instanceof ReturnNode ret ) { + // Returning a writable alias must not grant write access + // to an object reached through a read-only receiver. + if( ret.expr() == value ) _writes = true; + } else if( use instanceof LoadNode load && load.ptr() == value ) { + Type type = type(load); + if( type instanceof TypeMemPtr ptr ) { + if( !ptr._ro ) work.add(load); + } else if( type == Type.BOTTOM || type == TypeScalar.BOT ) _writes = true; + } else if( use instanceof PhiNode || use instanceof GuardNode ) { + work.add(use); + } else if( use instanceof ConvertNode convert ) { + if( !(convert.dst() instanceof TypeMemPtr ptr && ptr._ro) ) _writes = true; + } else if( use instanceof BoolNode || use instanceof NotNode || + use instanceof FldOffNode || use instanceof ScopeNode || use instanceof CLInitNode ) { + // Comparisons and field offsets do not expose write access. + } else { + // Includes raw-address casts and unrecognized escapes. + _writes = true; + } + } + } + } + + private void call(CallNode call, int arg, HashMap<Integer,MethodAccess> methods) { + // Every member of this struct is now declared. An unresolved bare + // function name belongs to an outer scope, whose hidden slot is not self. + if( arg == 0 && call.fptr() instanceof FRefNode ) return; + Type type = type(call.fptr()); + if( !(type instanceof TypeFunPtr sig) || arg >= sig.nargs() ) { _writes = true; return; } + if( arg == 0 && sig.arg(0) == TypePtr.PTR ) return; + if( arg == 0 ) { + if( XInt.isHigh(sig.fidxs()) ) { _writes = true; return; } + for( int fidx = XInt.next(sig.fidxs(),-1); fidx >= 0; fidx = XInt.next(sig.fidxs(),fidx) ) { + MethodAccess local = methods.get(fidx); + if( local != null ) _calls.add(local); + else { + FunNode target = CodeGen.CODE.link(fidx); + Type receiver = target == null ? sig.arg(0) : target.sig().arg(0); + if( !(receiver instanceof TypeMemPtr ptr && ptr._ro) ) _writes = true; + } + } + return; + } + if( !(sig.arg(arg) instanceof TypeMemPtr ptr && ptr._ro) ) _writes = true; + } + + private static Type type(Node value) { + // Flow types can still be BOTTOM while the parser discovers fields. + if( value instanceof LoadNode load ) { + TypeStruct obj = load.off() instanceof ConFldOffNode off ? off._ts : + type(load.ptr()) instanceof TypeMemPtr ptr ? ptr._obj : null; + if( obj != null ) { + if( !obj.isAry() && Parser.TYPES.get(obj._name) instanceof TypeStruct latest ) obj = latest; + Field field = obj.field(load._name); + if( field != null ) return field._t; + } + } + return value._type; + } + + private void finish() { + ParmNode self = _fun.parm(2); + if( self == null ) return; + TypeMemPtr receiver = ((TypeMemPtr)self._declaredType).withAccess(!_writes); + _fun.setSig(_fun.sig().makeFrom(receiver,0)); + if( _writes ) return; + self._declaredType = receiver; + self.setDef(1,ConstantNode.seed(receiver).peephole()); + // These parser-time assumptions are settled before Iter/SCCP. No + // writable alias escapes a method classified as read-only. + for( Node alias : _aliases ) + if( alias._type instanceof TypeMemPtr ptr ) { + alias._type = ptr.makeRO(); + CodeGen.CODE.add(alias); + CodeGen.CODE.addAll(alias._outputs); + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/parser/Parser.java b/src/main/java/com/seaofnodes/simple/parser/Parser.java index 0cf3c0e7..9c18385d 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Parser.java +++ b/src/main/java/com/seaofnodes/simple/parser/Parser.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import java.util.HashMap; import java.util.HashSet; -import java.util.LinkedHashSet; +import java.util.LinkedHashMap; import java.util.Stack; /** Source-unit entry point and shared cursor, scope, and IR utilities. @@ -21,6 +21,7 @@ public class Parser { final Functions functions = new Functions(this); final Structs structs = new Structs(this); final Allocations allocations = new Allocations(this); + final ArrayInitializers arrays = new ArrayInitializers(this); final References references = new References(this); final Conversions conversions = new Conversions(this); final Construction construction = new Construction(this); @@ -91,7 +92,7 @@ public class Parser { public final Stack<ScopeNode> _xScopes = new Stack<>(); // Layouts needed by field accesses in this source file. Resolve after // parsing, since a later local struct declaration can satisfy the use. - public final LinkedHashSet<String> _requiredTypes = new LinkedHashSet<>(); + public final LinkedHashMap<String,Lexer> _requiredTypes = new LinkedHashMap<>(); // Mapping from a type name to a Type. The string name matches // `type.str()` call. @@ -120,6 +121,11 @@ public class Parser { public final Lexer _loc; ParseException( String msg, Lexer loc ) { super(msg); _loc = loc==null ? null : new Lexer(loc); } public String diagnostic() { return _loc==null ? getMessage() : _loc.diagnostic(getMessage()); } + // JUnit and uncaught-exception reporters use these entry points rather + // than the CLI's diagnostic(). Source errors should retain their source + // excerpt and caret there too. getMessage() stays stable for callers. + @Override public void printStackTrace(java.io.PrintStream out) { out.println(diagnostic()); } + @Override public void printStackTrace(java.io.PrintWriter out) { out.println(diagnostic()); } } public Parser(CodeGen code ) { @@ -265,7 +271,7 @@ public class Parser { // Field offset for an unknown type public Node fldoff( Node n, String name ) { if( n._type instanceof TypeMemPtr ptr && ptr._obj._fref ) - _requiredTypes.add(ptr._obj._name); + _requiredTypes.putIfAbsent(ptr._obj._name,loc()); return new FldOffNode(n,name,loc()).peephole(); } public Node peep( Node n ) { diff --git a/src/main/java/com/seaofnodes/simple/parser/README.md b/src/main/java/com/seaofnodes/simple/parser/README.md index cee1d64a..48cf13c8 100644 --- a/src/main/java/com/seaofnodes/simple/parser/README.md +++ b/src/main/java/com/seaofnodes/simple/parser/README.md @@ -2,7 +2,7 @@ The parser builds Sea-of-Nodes IR directly. Each component shares the cursor, active scope, and compilation state through its `Parser P` reference; there is no intermediate -AST. The [grammar map](../../../../../../../docs/chapter30/30-grammar.md) connects language +AST. The [grammar map](../../../../../../../docs/chapter31/31-grammar.md) connects language productions to their entry points. | File | Responsibility | @@ -14,6 +14,7 @@ productions to their entry points. | `Declarations.java` | Bindings, initializers, mutability modifiers, and native declarations. | | `Types.java` | Type syntax, qualified-name lookup, arrays, function types, and forward types. | | `Functions.java` | Function expressions, parameters, arguments, calls, and function entry/return graphs. | +| `MethodAccess.java` | Infers whether an instance method needs writable access through its receiver. | | `Structs.java` | Struct and constructor declarations, field discovery, and initialization Stores. | | `Construction.java` | Selects private self memory during parsing; its comment explains BOT fields, the TypeMemPtr qualifier, and checks deferred to TypeCheck. | | `References.java` | Bare-name and field resolution, implicit receivers, assignments, and forward references. | @@ -23,8 +24,16 @@ productions to their entry points. | `Var.java` | Lexical binding metadata: name, type, scope slot, and mutability. | Start with `Statements.parseStatement` or `Expressions.parseAssignment` to follow -the grammar. Loop updates are parsed after their bodies, and declared constructor -bodies after field discovery; `Lexer.skipTo` scans these deferred fragments. +the grammar. Loop updates are parsed after their bodies. Instance method headers +are parsed immediately, but their bodies and declared constructor bodies wait +until all fields are known. Methods can therefore use fields declared later in +the struct. `Lexer.skipTo` scans these deferred fragments. + +Method receivers accept read-only access unless the body needs writable access. +The check follows aliases, child references, array elements, and calls between +methods. Writing an independent argument does not require a writable receiver. +Returning or storing a writable receiver alias also requires writable access; +an explicit read-only view can be exposed without that requirement. `Parser` keeps the short cursor, scope/memory, IR-building, and diagnostic helpers used by these components. Independent helpers live with their data: class-object diff --git a/src/main/java/com/seaofnodes/simple/parser/References.java b/src/main/java/com/seaofnodes/simple/parser/References.java index 6335bad2..7724103e 100644 --- a/src/main/java/com/seaofnodes/simple/parser/References.java +++ b/src/main/java/com/seaofnodes/simple/parser/References.java @@ -120,6 +120,7 @@ final class References { return P.expressions.parsePostfixMethod(P.construction.view(rvalue),P._scope.in(P._scope.update(P._scope.var(selfx),null))); } // Assign-update direct into Scope + P.arrays.checkAssignment(var,site); if( var._final && !P._scope.canInit(var) ) throw Parser.error("Cannot reassign final '"+var._name+"'",site); checkSharedFunction(var); @@ -130,6 +131,7 @@ final class References { } void checkAssignment(Var def, Lexer site) { + if( fieldSelf(def)==null ) P.arrays.checkAssignment(def,site); String name = def._name; // A final field may receive its first value in its constructor. if( P._scope.in(def._idx)._type!=Type.TOP && def._final && @@ -278,7 +280,7 @@ final class References { // Check for assign-update, "ptr.fld += expr" or "ary[idx]++" char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; if( ch!=0 ) { - if( fld!=null && decl==Type.BOTTOM ) + if( fld!=null && decl==Type.BOTTOM && !ts._fref ) throw Parser.error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor",site ); Node op = P.expressions.opAssign(ch,load, decl ).keep(); mem.keep(); @@ -306,10 +308,15 @@ final class References { // Fields are lvalues in memory, including inside their initializer and // explicit constructor. Scope slots retain declaration metadata only. private Node fieldSelf(Var var) { - int kx = P._scope.kindx(var), fx = P._scope.enclosingFuncOrDecl(); + int kx = P._scope.kindx(var); ScopeNode.Kind kind = P._scope._kinds.at(kx); if( !(kind instanceof Kind.Func inst) || !FunNode.isInstance(inst._name) || var._idx<inst._lexSize+2 ) return null; - if( kx==fx || kx+1==fx ) return defaultSelf(); + // Nested functions have their own receiver parameter. Resolve fields + // through it even across intervening function and block scopes. + Node self = defaultSelf(); + Type owner = P._scope.var(inst._lexSize).type(); + if( self._type instanceof TypeMemPtr ptr && owner instanceof TypeMemPtr declared && + ptr._obj._name.equals(declared._obj._name) ) return self; return null; } diff --git a/src/main/java/com/seaofnodes/simple/parser/Statements.java b/src/main/java/com/seaofnodes/simple/parser/Statements.java index 707202ab..0c2a25f7 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Statements.java +++ b/src/main/java/com/seaofnodes/simple/parser/Statements.java @@ -78,6 +78,7 @@ final class Statements { */ private Node parseReturn() { var expr = P.require(P.expressions.parseAssignment(), ";"); + if( P.arrays._frame!=null ) return P.arrays.addReturn(expr); return P.functions.addReturn(expr); } diff --git a/src/main/java/com/seaofnodes/simple/parser/Strings.java b/src/main/java/com/seaofnodes/simple/parser/Strings.java index 5bf76585..be913371 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Strings.java +++ b/src/main/java/com/seaofnodes/simple/parser/Strings.java @@ -32,7 +32,7 @@ final class Strings { Node strings=P.references.member(text,"string",fmt.site()).keep(); fptr=new FormatNode(value,ints.unkeep(),floats.unkeep(),strings.unkeep(),fmt.site()).peephole(); } else { - String family="diuoxXcb".indexOf(fmt.kind())>=0 ? "integer" : fmt.kind()=='s' ? "string" : "floating"; + String family="diuoxXcb".indexOf(fmt.kind())>=0 ? "integer" : fmt.kind()=='s' ? "string" : fmt.kind()=='t' ? "time" : "floating"; fptr=P.references.member(text,family,fmt.site()); } call(text,fptr,fmt.site(),builder,value.unkeep(),P.con(fmt.kind() | fmt.flags()<<8), diff --git a/src/main/java/com/seaofnodes/simple/parser/Types.java b/src/main/java/com/seaofnodes/simple/parser/Types.java index 827518fd..501924f0 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Types.java +++ b/src/main/java/com/seaofnodes/simple/parser/Types.java @@ -37,6 +37,12 @@ final class Types { if( t0==Type.BOTTOM || t0==Type.TOP ) return t0; // var/val tname = typeName(tname).intern(); t0 = Parser.TYPES.get(tname); + // Bare forward types use the same file-relative name as `new`. + // A later sibling declaration must complete this very type. + if( t0 == null && tname.indexOf('.') == -1 ) { + tname = fullTypeName(tname); + t0 = Parser.TYPES.get(tname); + } } Type t1 = t0==null ? TypeStruct.forward(tname) : t0; @@ -135,9 +141,8 @@ final class Types { Type implicitSelfType() { TypeStruct self = P._scope.constructorSelf(); - // Ordinary instance methods accept the declared object shape. The - // constructor-only receiver starts at the low/default field values, - // and is built explicitly by parseConstructor(). + // Function types without a body must allow for writes. Function + // expressions can infer a weaker requirement in MethodAccess. return self == null ? TypePtr.PTR : TypeMemPtr.make(self); } diff --git a/src/main/java/com/seaofnodes/simple/parser/Var.java b/src/main/java/com/seaofnodes/simple/parser/Var.java index ddbb91d8..5361148f 100644 --- a/src/main/java/com/seaofnodes/simple/parser/Var.java +++ b/src/main/java/com/seaofnodes/simple/parser/Var.java @@ -33,6 +33,11 @@ public class Var { public Type type() { return _type; } public Type _type() { return _type; } // ScopeNode printer needs to have no side effects + void refineType(Type type) { + assert type.isa(_type) : _name+": "+_type+" -> "+type; + _type = type; + } + // Forward reference variables (not types) must be BOTTOM and // distinct from inferred variables public boolean isFRef() { return _fref; } diff --git a/src/main/java/com/seaofnodes/simple/parser/package-info.java b/src/main/java/com/seaofnodes/simple/parser/package-info.java index c886f72a..73ebec2e 100644 --- a/src/main/java/com/seaofnodes/simple/parser/package-info.java +++ b/src/main/java/com/seaofnodes/simple/parser/package-info.java @@ -7,7 +7,7 @@ * use-side name/field resolution; Allocations, ControlFlow, and Conversions * contain their shared IR construction. Lexer also supplies location snapshots. * - * <p>See {@code chapter30/docs/30-grammar.md} for the production-to-method map. + * <p>See {@code chapter31/docs/31-grammar.md} for the production-to-method map. * Evaluation order and scope lifetimes are explicit: loop updates and declared * constructor bodies are the two deferred source fragments. There is no AST. */ diff --git a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index e8218afd..e4d1659d 100644 --- a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -10,19 +10,22 @@ import com.seaofnodes.simple.type.*; import java.util.ArrayList; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.util.BAOS; -import java.util.HashMap; +import java.util.Map; /** Machine-specific facts; traversal, columns and byte display live in print/. */ public final class ASMPrinter extends AssemblyAdapter<Node> { private final CodeGen _code; private final Encoding _enc; - private ASMPrinter(CodeGen code) { + private ASMPrinter(CodeGen code, Encoding enc) { super(new IRPrinter()); _code=code; - _enc=code._encoding; + _enc=enc; } public static SB print(SB sb, CodeGen code) { - return sb.p(new com.seaofnodes.print.ASMPrinter<>(new ASMPrinter(code)).print()); + return print(sb,code,code._encoding); + } + public static SB print(SB sb, CodeGen code, Encoding enc) { + return sb.p(new com.seaofnodes.print.ASMPrinter<>(new ASMPrinter(code,enc)).print()); } @Override public ArrayList<Node> blocks() { var blocks=new ArrayList<Node>(); @@ -89,11 +92,11 @@ public final class ASMPrinter extends AssemblyAdapter<Node> { var data=new ArrayList<Data>(); for( var obj : _enc._data.entries() ) if( !obj.external && obj.readOnly==ro ) - data.add(new Data(obj,obj.symbol+": "+obj.type.str(),obj.alignment,obj.size)); + data.add(new Data(obj,obj.label()+": "+obj.type.str(),obj.alignment,obj.size)); return data; } // Retain this diagnostic entry point for checking that pool printing never lays out types. - static int printConstantPool(int address, SB sb, BAOS bits, HashMap<Node,Encoding.Relo> relos, + static int printConstantPool(int address, SB sb, BAOS bits, Map<Node,Encoding.Relo> relos, boolean ro, String name) { sb.p(com.seaofnodes.print.ASMPrinter.pool(new Pool(name,bits.buf(),0,address,entries(relos.values(),ro)))); return address+bits.size(); diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 0f655f49..2e228494 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -531,7 +531,7 @@ public class Type /*implements Cloneable*/ { // tag-space except for the first tag-space which uses 1 tag for // multiple Types instead of 1 Type having multiple tags. Has to // be ordered to match _type enum. - for( Type t : new Type[]{Type.XNIL,TypeScalar.BOT,TypePtr.PTR,TypeInteger.BOT,TypeFloat.F64,TypeConAryB.ABC,TypeRPC.BOT,TypeMemPtr.BOT,TypeFunPtr.BOT,TypeMem.BOT,Field.BOT,TypeStruct.BOT,TypeTuple.BOT} ) + for( Type t : new Type[]{Type.XNIL,TypeScalar.BOT,TypePtr.PTR,TypeInteger.BOT,TypeFloat.F64,TypeConAry.ABC,TypeRPC.BOT,TypeMemPtr.BOT,TypeFunPtr.BOT,TypeMem.BOT,Field.BOT,TypeStruct.BOT,TypeTuple.BOT} ) TAGOFFS[t._type+1] = TAGOFFS[t._type] + t.TAGOFF(); assert TAGOFFS[TMAX] <= 255; return TAGOFFS; diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index 9cb23e09..c10f09aa 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -1,33 +1,48 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.BAOS; -import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; +import java.util.Arrays; import java.util.HashMap; /** - * Represents a constant array of primitives + * Constant integer contents with an explicit storage width and signedness. */ -public abstract class TypeConAry<A> extends TypeScalar { +public final class TypeConAry extends TypeScalar { boolean _any; byte _widen; - // One of byte or int array - public final A _ary; + private final TypeInteger _storage; + private final long[] _ary; - TypeConAry( boolean any, byte widen, A ary ) { super(TCONARY); _any = any; _widen = widen; _ary = ary; } + private TypeConAry(boolean any, byte widen, TypeInteger storage, long[] ary) { + super(TCONARY); + _any=any; _widen=widen; _storage=storage; _ary=ary; + } + static final TypeConAry ABC=make("abc"); + static final TypeConAry ABCD=make("abcd"); public static void gather(ArrayList<Type> ts) { - ts.add(TypeConAryB.make("")); - ts.add(TypeConAryB.ABC); - ts.add(TypeConAryB.ABCD); - ts.add(TypeConAryI.I123); + ts.add(make("")); + ts.add(ABC); + ts.add(ABCD); + ts.add(make(TypeInteger.I32,new long[]{1,2,3})); + ts.add(make(TypeInteger.U16,new long[]{0,65535})); + ts.add(make(TypeInteger.BOT,new long[]{Long.MIN_VALUE,Long.MAX_VALUE})); + for( TypeInteger storage : STORAGE ) { + ts.add(make(storage,new long[0])); + ts.add(make(storage,new long[]{0,1})); + } } // Fresh, uninterned type sharing this array; xdual must not intern. - abstract TypeConAry<A> _make(boolean any, byte widen); + private TypeConAry _make(boolean any, byte widen) { + return new TypeConAry(any,widen,_storage,_ary); + } - @Override TypeConAry<A> xdual() { return _make( !_any, (byte)(3-_widen) ); } + @Override TypeConAry xdual() { return _make( !_any, (byte)(3-_widen) ); } @Override Type xmeet(Type t) { TypeConAry ary = (TypeConAry)t; // Invariant + if( len()==0 ) return emptyMeet(ary); + if( ary.len()==0 ) return ary.emptyMeet(this); // Same base array but different? if( _equals(ary) ) // Return array with larger widen @@ -37,15 +52,7 @@ public abstract class TypeConAry<A> extends TypeScalar { } Type ymeet( TypeInteger ti ) { - // Empty arrays have no observed elements: use the storage bounds. - // Check both endpoints just as the loop checks a nonempty body; - // retaining high integer inputs here preserves lattice duality. - if( len()==0 ) { - TypeInteger bound=emptyElem(); - if( !ti.isa(TypeInteger.make(bound._min,bound._min,ti._widen)) || - !ti.isa(TypeInteger.make(bound._max,bound._max,ti._widen)) ) - return ti.meet(bound); - } + if( len()==0 ) return emptyMeet(ti); // if i can isa *each* element, then maybe can keep. // no good to i.isa(elem()) because fails the dual for( int j=0; j<len(); j++ ) @@ -56,12 +63,21 @@ public abstract class TypeConAry<A> extends TypeScalar { } private boolean _equals(TypeConAry ary) { - int len = len(); - if( len != ary.len() ) return false; - for( int i=0; i<len; i++ ) - if( at8(i) != ary.at8(i) ) - return false; - return true; + return _storage==ary._storage && (len()!=0 || _any==ary._any) && Arrays.equals(_ary,ary._ary); + } + @Override boolean eq(Type t) { return t instanceof TypeConAry ary && _widen==ary._widen && _equals(ary); } + @Override int hash() { return Arrays.hashCode(_ary)^_storage.hashCode()^(len()==0 && _any ? 1231 : 0); } + @Override public String str() { + boolean text=_storage==TypeInteger.U8; + for( long value : _ary ) + if( value<32 || value>126 ) { text=false; break; } + if( !text ) { + String range=elem().str(); + return range.startsWith("[") ? range : "["+range+"]"; + } + byte[] bytes = new byte[len()]; + for( int i=0; i<bytes.length; i++ ) bytes[i]=(byte)_ary[i]; + return "[\""+new String(bytes)+"\"]"; } @Override public boolean isHigh() { return this==TOP; } @@ -70,8 +86,6 @@ public abstract class TypeConAry<A> extends TypeScalar { // Meet-over-elements type public Type elem() { - if( _ary==null ) - return _any ? Type.TOP : BOTTOM; int len = len(); long min = Long.MAX_VALUE; if( len==0 ) return emptyElem(); @@ -83,23 +97,80 @@ public abstract class TypeConAry<A> extends TypeScalar { return TypeInteger.make(min,max,_widen); } private TypeInteger emptyElem() { - return log_size()==0 ? TypeInteger.make(0,255,_widen) - : TypeInteger.make(Integer.MIN_VALUE,Integer.MAX_VALUE,_widen); + TypeInteger storage=storageType(); + return _any ? TypeInteger.make(storage._min,storage._max,_widen) + : TypeInteger.make(storage._max,storage._min,_widen); + } + // Keep the empty payload distinct from its element bound. It sits just + // above the storage dual; its own dual sits just below the storage bound. + // This makes it a subtype of every constant array within those bounds, + // while preserving meet/join symmetry with ordinary integer ranges. + private Type emptyMeet(Type t) { + Type bound=emptyElem(); + if( t.isa(bound) && (_any || t!=bound) ) return this; + return bound.meet(t); } - public abstract long at8(int idx); - public abstract int len(); - @Override public abstract int log_size(); - public void write( BAOS baos ) { throw Utils.TODO("Should not reach here: abstract constant array cannot be written"); } + public TypeInteger storageType() { return _storage; } + public long at8(int idx) { return _ary[idx]; } + public int len() { return _ary.length; } + @Override public int log_size() { return _storage.log_size(); } + public void write( BAOS baos ) { + for( int i=0; i<len(); i++ ) { + long value=at8(i); + for( int b=0; b<(1<<log_size()); b++ ) baos.write((byte)(value >>> (8*b))); + } + } + + /** Canonical contents, independent of the node which discovered them. */ + public static TypeConAry make(TypeInteger storage, long[] values) { + long[] copy=values.clone(); + int shift=64-(8<<storage.log_size()); + for( int i=0; i<copy.length; i++ ) + copy[i]=storage._min<0 ? (copy[i]<<shift)>>shift : copy[i]&storage._max; + return new TypeConAry(false,(byte)0,storage,copy).intern(); + } + public static TypeConAry make(byte[] bytes) { + long[] values=new long[bytes.length]; + for( int i=0; i<bytes.length; i++ ) values[i]=bytes[i]&255; + return new TypeConAry(false,(byte)0,TypeInteger.U8,values).intern(); + } + public static TypeConAry make(String s) { return make(s.getBytes()); } + + // Keep the existing byte-array tag and encoding. An impossible Java array + // length escapes to a typed payload, without renumbering later type tags. + private static final int TYPED = -1; + private static final TypeInteger[] STORAGE={TypeInteger.BOOL,TypeInteger.I8,TypeInteger.U8, + TypeInteger.I16,TypeInteger.U16,TypeInteger.I32,TypeInteger.U32,TypeInteger.BOT}; // Reserve tags for u8 array @Override int TAGOFF() { return 1; } @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { - assert log_size()==0 && !_any; baos.write(TAGOFFS[TCONARY]+0); + if( storageType()!=TypeInteger.U8 || _any || _widen!=0 ) { + baos.packed4(TYPED); + int kind=0; + while( kind<STORAGE.length && STORAGE[kind]!=storageType() ) kind++; + assert kind<STORAGE.length; + baos.packed1(kind); + baos.packed1((_any ? 4 : 0)|_widen); + } baos.packed4(len()); - baos.write((byte[])_ary); + write(baos); } static TypeConAry packed( int tag, BAOS bais ) { - return TypeConAryB.make(bais.read(new byte[bais.packed4()])); + int len=bais.packed4(); + if( len!=TYPED ) return make(bais.read(new byte[len])); + TypeInteger storage=STORAGE[bais.packed1()]; + int flags=bais.packed1(); + long[] values=new long[bais.packed4()]; + int size=1<<storage.log_size(); + for( int i=0; i<values.length; i++ ) { + long value=0; + for( int b=0; b<size; b++ ) value|=(long)bais.read() << (8*b); + if( storage._min<0 && size<8 ) value=(value << (64-size*8)) >> (64-size*8); + values[i]=value; + } + TypeConAry ary=make(storage,values); + return flags==0 ? ary : ary._make((flags&4)!=0,(byte)(flags&3)).intern(); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java deleted file mode 100644 index 84be5fb2..00000000 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ /dev/null @@ -1,20 +0,0 @@ -package com.seaofnodes.simple.type; - -import com.seaofnodes.simple.util.BAOS; -import java.util.Arrays; - -public class TypeConAryB extends TypeConAry<byte[]> { - private TypeConAryB(boolean any, byte widen, byte[] bs) { super(any,widen,bs); } - @Override TypeConAryB _make( boolean any, byte widen ) { return new TypeConAryB(any,widen,_ary); } - public static TypeConAryB make( byte[] bs ) { return new TypeConAryB(false,(byte)0,bs).intern(); } - public static TypeConAryB make( String s ) { return make(s.getBytes()); } - static final TypeConAryB ABC = make("abc"); - static final TypeConAryB ABCD = make("abcd"); - @Override public long at8(int idx) { return _ary[idx]&255; } - @Override public int len() { return _ary.length; } - @Override public int log_size() { return 0; } - @Override public String str() { return "[\""+new String(_ary)+"\"]"; } - @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); } - @Override int hash() { return Arrays.hashCode(_ary); } - @Override public void write( BAOS baos ) { baos.write(_ary); } -} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java deleted file mode 100644 index b1b061de..00000000 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAryI.java +++ /dev/null @@ -1,16 +0,0 @@ -package com.seaofnodes.simple.type; - -import java.util.Arrays; - -public class TypeConAryI extends TypeConAry<int[]> { - private TypeConAryI(boolean any, byte widen, int[] bs) { super(any,widen,bs); } - public static TypeConAryI make( int[] bs ) { return new TypeConAryI(false,(byte)0,bs).intern(); } - @Override TypeConAryI _make( boolean any, byte widen ) { return new TypeConAryI(any,widen,_ary); } - static final TypeConAryI I123 = make(new int[]{1,2,3}); - @Override public long at8(int idx) { return _ary[idx]; } - @Override public int len() { return _ary.length; } - @Override public int log_size() { return 2; } - @Override public String str() { return "[i32]"; } - @Override boolean eq(Type t) { return t instanceof TypeConAryI ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); } - @Override int hash() { return Arrays.hashCode(_ary); } -} diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index d410e9cf..8d04fcbf 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -107,7 +107,7 @@ public class TypeFloat extends TypeScalar { else { assert isConstant(); baos.write(TAGOFFS[_type] + 2); - baos.packed8(Double.doubleToLongBits(_con)); + baos.packed8(Double.doubleToRawLongBits(_con)); } } @@ -121,12 +121,12 @@ public class TypeFloat extends TypeScalar { } @Override - int hash() { return (int)(Double.hashCode(_con) ^ _sz ^ (1<<17)); } + int hash() { return Long.hashCode(Double.doubleToRawLongBits(_con)) ^ _sz ^ (1<<17); } @Override public boolean eq( Type t ) { TypeFloat i = (TypeFloat)t; // Contract - // Allow NaN to check for equality - return _sz==i._sz && Double.doubleToLongBits(_con)==Double.doubleToLongBits(i._con); + // Representation conversions observe NaN signs/payloads and signed zero. + return _sz==i._sz && Double.doubleToRawLongBits(_con)==Double.doubleToRawLongBits(i._con); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 5faa7107..1c83ddd7 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -211,14 +211,19 @@ public class TypeMem extends Type { + (!_one ? 0 : (_clz ? 4 : 8))); if( _alias!=1 ) { // generic alias - assert _alias <= 255; - baos.packed1( _alias ); + // Zero is reserved for alias-set flags, never a memory slice. + // Use it as an escape for large libraries, retaining the existing + // single-byte encoding (including 255) for older objects. + assert _alias>1; + baos.packed1(_alias<=255 ? _alias : 0); + if( _alias>255 ) baos.packed4(_alias); } XInt.packed(baos,_escFs); XInt.packed(baos,_escAs); } static TypeMem packed( int tag, BAOS bais ) { int alias = (tag&1)==0 ? 1 : bais.packed1(); + if( alias==0 ) alias=bais.packed4(); boolean xfinal= (tag&2)==2; boolean one = (tag&12)!=0; boolean clz = (tag&4)==4; diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 7c9758bd..11ba3cc4 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -146,8 +146,7 @@ public class TypeStruct extends Type { Type len = TypeInteger.constant(con.len()); return make(name,false, Field.make("#" ,len , lenAlias,true), - Field.make("[]" ,con.elem(),bodyAlias,true), - Field.make("[con]",con ,bodyAlias,true)); + Field.make("[]" ,con ,bodyAlias,true)); } public TypeStruct makeInit() { @@ -190,6 +189,9 @@ public class TypeStruct extends Type { } @Override TypeStruct _close( String name, HashMap<String, Type> TYPES ) { assert (name==null) != (TYPES==null); // One or the other + // Primitive constant contents are already closed. Looking up their + // shared array name would discard the length and payload on import. + if( isConAry() ) return this; String namePlusFinal = isAry() ? (_name+(_fields[1]._final ? "~" : "!")).intern() : _name; TypeStruct ts = (TypeStruct)VISIT.get(namePlusFinal); if( ts!=null ) return ts; @@ -251,7 +253,7 @@ public class TypeStruct extends Type { public static final TypeStruct TEST= make("test",false,Field.TEST); private static final TypeStruct ARY = makeAry("[]i64",TypeInteger.U32,-1,TypeInteger.BOT,-2,false); private static final TypeStruct STR = makeAry("[]u8" ,TypeInteger.U32,-1,TypeInteger.U8 ,-4,false); - private static final TypeStruct ABC = makeAry("[]u8",-1,-4,TypeConAryB.ABC); + private static final TypeStruct ABC = makeAry("[]u8",-1,-4,TypeConAry.ABC); // Representative unresolved forms for the exhaustive lattice tests: // bare forward ref, forward ref constrained by a field use, and definition. private static final TypeStruct FREF0 = forward("%FREF"); @@ -462,6 +464,7 @@ public class TypeStruct extends Type { @Override public int log_size() { throw Utils.TODO("Should not reach here: structs have no scalar log size"); } @Override public int size() { return offset(_fields.length); } @Override public int alignment() { + if( isAry() ) return Math.max(2,aryScale()); // The length is always u32. int align = 0; for( Field f : _fields ) if( !f._extern ) align = Math.max(align, f._t.alignment()); @@ -607,7 +610,7 @@ public class TypeStruct extends Type { int align = _fields[1]._t.alignment(); _offs[1] = (4 + ((1<<align)-1)) & -(1<<align); if( _fields[1]._t instanceof TypeConAry ary ) // Array length is well-defined for constants, not defined for runtime arrays - _offs[2] = _offs[1]+ary.len(); + _offs[2] = _offs[1]+(ary.len()<<ary.log_size()); } else { int[] cnts = new int[5]; // Count of fields at log field size |