From 3568f3deed586327f885ac98b73d07ae3ade6e57 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 20 Aug 2026 10:56:30 -0700 Subject: Squashed commit of the following: commit c05d7df4f9c90984d2c04126772be3fee1d81fd1 Author: Cliff Click Date: Thu Aug 20 10:52:58 2026 -0700 Fix local frefs, deferred inlining, and sys FileIO support - Defer non-trivial inlining out of CallEnd idealization and run it from IterPeeps after normal peepholes reach a fixed point. - Keep forward refs local to their lexical scope, promote them outward on scope pop, and track created FRefNodes directly for dependency discovery. - Preserve loop scope shape when frefs are first seen inside loop bodies. - Treat frefs as final constants from creation and force lazy self lookups before implicit calls. - Reset imported pointer/struct types conservatively for post-parse Iter. - Pin Start-owned global machine value chains and clone global constants per function during GCM. - Improve late ASM printing before encoding and namespace constant-pool symbols. - Add optional regalloc function-local edge verifier and improve empty-mask splitting for multi-def/fixed-register LRGs. - Add sys array compare, safer array copy bounds, libc open/creat/close/unlink bindings, aryu8.str0, and higher-level sys.io file operations. - Add docs/examples/FileIO.smp and a Chapter25 FileIO test. - Update spill/code-size goldens after the allocator and scheduling changes. commit ef5316979732ac118612d310b75923c8f59ecdc1 Author: Cliff Click Date: Fri Aug 14 16:29:56 2026 -0700 Dijkstra uses bitset. TestC.exec for repeated test runs with different stdins. Support &= and |= op-update forms. commit 728a527587f19bb49860f02ae5ac5968ab01ae33 Author: Cliff Click Date: Fri Aug 14 12:13:28 2026 -0700 Fix live demo commit e4c069b9ef2cbfafe28d8edfcbff55396cde085e Author: Cliff Click Date: Fri Aug 14 09:52:24 2026 -0700 Update Dijkstra.smp commit b8015739b4056e3f7a715a030e846a441021a9f1 Author: Cliff Click Date: Fri Aug 14 09:41:17 2026 -0700 Better looking Dijkstra commit 7cce587804c6169b24829e0b5bdc10be94357a31 Author: Cliff Click Date: Fri Aug 14 09:33:33 2026 -0700 Fix CmpMemX86 encoding Use sys.aryu8 for number printing commit 310b5d8c9978a3b09622a4b89dac97f0e5e6f3fb Author: Cliff Click Date: Fri Aug 14 09:04:58 2026 -0700 Progress dijlstra Fix NotX86 encoding. Allow Not-sinking through Phis; the Nots both take Scalar and might take different types (ptr vs int). Better guard installing during && || opers. Drop the csv parse flavor in sys lib. commit 5917d5322521dd5e762c4698d34e5d7ac9b3a37f Author: Cliff Click Date: Thu Aug 13 14:44:12 2026 -0700 missed commit da35ad4d8a330559a21c04ae6326536e0fd62c48 Author: Cliff Click Date: Thu Aug 13 14:43:42 2026 -0700 Major cleanup of allocation All the graph-gen is moved to the declaration and not at the alloc site. commit c4223216099ccbc526d282bb263972532d48c5b2 Author: Cliff Click Date: Thu Aug 13 13:26:01 2026 -0700 Some work from Dykstra (more coming) commit a03bc567f61dc7e4355e453ee4be16ac2528d1ab Author: Cliff Click Date: Thu Aug 13 09:32:55 2026 -0700 Spill correctness and improvements Had the callee-save pick-risky backwards vs cloneables. commit 2d306e4430225f916cb7fb999f4926e52f6fb70a Author: Cliff Click Date: Wed Aug 12 19:40:04 2026 -0700 Tighter parser handling of missing fields Bug fix add libc.errno, read can return -1, sys.ary exists commit b7eeefda4cafa1e86153170dca6f13d45ef63f69 Author: Cliff Click Date: Wed Aug 12 16:22:48 2026 -0700 Printer improvements commit 8b9112226f1d2d1c843b080eecefe0d5ddc1f8cf Author: Cliff Click Date: Wed Aug 12 15:30:46 2026 -0700 Remove GLB commit ae566f5c610b9c30831906d3f024901d8930a227 Author: Cliff Click Date: Wed Aug 12 14:38:51 2026 -0700 Add Capitalize example Rename Ary to ary. Fix bug || carrying state along. Fix bug load-array removing control. Add sys.char tolower/upper --- chapter25/Makefile | 10 +- chapter25/docs/examples/BubbleSort.smp | 16 +- chapter25/docs/examples/Capitalize.smp | 23 ++ chapter25/docs/examples/Dijkstra.smp | 73 ++++++ chapter25/docs/examples/FileIO.smp | 51 ++++ .../main/java/com/seaofnodes/simple/IterPeeps.java | 44 +++- .../main/java/com/seaofnodes/simple/Parser.java | 260 ++++++++++++++------- .../com/seaofnodes/simple/codegen/CodeGen.java | 65 +++++- .../com/seaofnodes/simple/codegen/ElfWriter.java | 3 +- .../simple/codegen/GlobalCodeMotion.java | 85 ++++--- .../java/com/seaofnodes/simple/codegen/IFG.java | 84 ++++--- .../java/com/seaofnodes/simple/codegen/Opto.java | 4 + .../com/seaofnodes/simple/codegen/ParseAll.java | 29 ++- .../com/seaofnodes/simple/codegen/RegAlloc.java | 134 ++++++++++- .../com/seaofnodes/simple/codegen/Serialize.java | 9 +- .../com/seaofnodes/simple/node/CallEndNode.java | 203 ++++++++-------- .../java/com/seaofnodes/simple/node/CallNode.java | 14 +- .../com/seaofnodes/simple/node/EscapeNode.java | 2 +- .../java/com/seaofnodes/simple/node/FRefNode.java | 7 +- .../java/com/seaofnodes/simple/node/FunNode.java | 73 ++++-- .../java/com/seaofnodes/simple/node/LoadNode.java | 3 +- .../com/seaofnodes/simple/node/MemMergeNode.java | 3 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 8 +- .../java/com/seaofnodes/simple/node/ParmNode.java | 4 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 9 +- .../com/seaofnodes/simple/node/ReturnNode.java | 3 + .../java/com/seaofnodes/simple/node/ScopeNode.java | 104 +++++++-- .../java/com/seaofnodes/simple/node/StoreNode.java | 10 +- .../simple/node/cpus/riscv/StoreRISC.java | 4 +- .../simple/node/cpus/x86_64_v2/CmpMemX86.java | 2 +- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 2 +- .../simple/node/cpus/x86_64_v2/NotX86.java | 17 +- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 5 +- .../com/seaofnodes/simple/print/ASMPrinter.java | 43 ++-- .../com/seaofnodes/simple/print/IRPrinter.java | 157 +++++++++++-- .../java/com/seaofnodes/simple/type/Field.java | 2 - .../main/java/com/seaofnodes/simple/type/Type.java | 25 +- .../com/seaofnodes/simple/type/TypeConAry.java | 3 +- .../java/com/seaofnodes/simple/type/TypeFloat.java | 8 +- .../com/seaofnodes/simple/type/TypeFunPtr.java | 7 +- .../com/seaofnodes/simple/type/TypeInteger.java | 6 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 11 +- .../com/seaofnodes/simple/type/TypeMemPtr.java | 6 +- .../java/com/seaofnodes/simple/type/TypeNil.java | 1 - .../java/com/seaofnodes/simple/type/TypePtr.java | 4 +- .../java/com/seaofnodes/simple/type/TypeRPC.java | 2 +- .../com/seaofnodes/simple/type/TypeScalar.java | 3 +- .../com/seaofnodes/simple/type/TypeStruct.java | 21 +- chapter25/src/main/smp/sys.smp | 13 +- chapter25/src/main/smp/sys/Ary.smp | 10 - chapter25/src/main/smp/sys/Scan.smp | 42 ---- chapter25/src/main/smp/sys/adt.smp | 4 + chapter25/src/main/smp/sys/adt/bitset.smp | 58 +++++ chapter25/src/main/smp/sys/ary.smp | 25 ++ chapter25/src/main/smp/sys/aryi64.smp | 26 ++- chapter25/src/main/smp/sys/aryu8.smp | 38 ++- chapter25/src/main/smp/sys/char.smp | 9 + chapter25/src/main/smp/sys/io.smp | 65 ++++-- chapter25/src/main/smp/sys/libc.smp | 28 ++- chapter25/src/main/smp/sys/scan.smp | 40 ++++ .../java/com/seaofnodes/simple/BrainFuckTest.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter13Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter17Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter18Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 41 +++- .../java/com/seaofnodes/simple/Chapter21Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 30 ++- .../java/com/seaofnodes/simple/Chapter24Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter25Test.java | 147 ++++++------ .../test/java/com/seaofnodes/simple/Simple.java | 2 +- .../src/test/java/com/seaofnodes/simple/TestC.java | 36 ++- .../test/java/com/seaofnodes/simple/TypeTest.java | 30 +-- .../seaofnodes/simple/test_smp/forward_ctor/m.smp | 2 + .../simple/test_smp/forward_ctor/m/a.smp | 1 + .../simple/test_smp/forward_ctor/m/b.smp | 4 + .../simple/test_smp/seed_repro/sys/Ary.smp | 6 - .../simple/test_smp/seed_repro/sys/ary.smp | 6 + .../simple/test_smp/seed_repro/sys/aryu8.smp | 10 +- 82 files changed, 1681 insertions(+), 729 deletions(-) create mode 100644 chapter25/docs/examples/Capitalize.smp create mode 100644 chapter25/docs/examples/Dijkstra.smp create mode 100644 chapter25/docs/examples/FileIO.smp delete mode 100644 chapter25/src/main/smp/sys/Ary.smp delete mode 100644 chapter25/src/main/smp/sys/Scan.smp create mode 100644 chapter25/src/main/smp/sys/adt.smp create mode 100644 chapter25/src/main/smp/sys/adt/bitset.smp create mode 100644 chapter25/src/main/smp/sys/ary.smp create mode 100644 chapter25/src/main/smp/sys/char.smp create mode 100644 chapter25/src/main/smp/sys/scan.smp create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m.smp create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/a.smp create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/b.smp delete mode 100644 chapter25/src/test/java/com/seaofnodes/simple/test_smp/seed_repro/sys/Ary.smp create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/test_smp/seed_repro/sys/ary.smp diff --git a/chapter25/Makefile b/chapter25/Makefile index 98b6e368..2bae14fb 100644 --- a/chapter25/Makefile +++ b/chapter25/Makefile @@ -63,6 +63,7 @@ TST := src/test/java CLZDIR:= build/classes main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java $(SRC)/$(SIMPLE)/node/cpus/*/*java) test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) +simple_driver := $(TST)/$(SIMPLE)/Simple.java main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) # These tests do not rely on the stdlib @@ -139,16 +140,17 @@ $(CLZDIR)/test/.ttag: $(test_javas) $(CLZDIR)/main/.mtag # dumped. The default sys search needs to NOT include all the dumped test # files; move it down into lib/ OBJS:= build/objs -SYS_SMPS:= $(wildcard src/main/smp/*.smp src/main/smp/*/*.smp) +SYS_SMPS:= $(wildcard src/main/smp/*.smp src/main/smp/*/*.smp src/main/smp/*/*/*.smp) CPU_PORT:= x86_64_v2 CALL_CONV:= win64 CPU_ABI:= $(CPU_PORT)_$(CALL_CONV) RELEASE:= build/release +TEST_SYS:= $(OBJS)/lib_$(CPU_ABI)/sys.o RELEASE_SYS:= $(RELEASE)/$(CPU_ABI)/sys.o RELEASE_CRT:= $(RELEASE)/$(CPU_ABI)/simple_crt.o C_CALL_CONV:= $(if $(filter win64,$(CALL_CONV)),ms_abi,sysv_abi) -$(OBJS)/lib_$(CPU_ABI)/sys.o: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(SYS_SMPS) +$(TEST_SYS): $(CLZDIR)/main/.mtag $(simple_driver) $(SYS_SMPS) | $(CLZDIR)/test/.ttag @echo "simping " $@ @$(JVM) com.seaofnodes.simple.Simple --cpu $(CPU_PORT) --abi $(CALL_CONV) --norun -o $@ src/main/smp/sys.smp @@ -184,7 +186,7 @@ tests_alone: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(RELEASE_CRT) @$(JVM) org.junit.runner.JUnitCore $(test_alone) # Tests that DO need sys.smp -tests_sys: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(RELEASE_SYS) $(RELEASE_CRT) +tests_sys: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(TEST_SYS) $(RELEASE_CRT) @echo "testing " $(test_sys) @[ -d $(OBJS) ] || mkdir -p $(OBJS) @$(JVM) org.junit.runner.JUnitCore $(test_sys) @@ -193,7 +195,7 @@ fuzzer: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag @echo "fuzzing " @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap -tests: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(RELEASE_SYS) tests_raw0 tests_raw1 tests_alone tests_sys +tests: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag tests_raw0 tests_raw1 tests_alone tests_sys @echo "All tests" @[ -d $(OBJS) ] || mkdir -p $(OBJS) @$(JVM) org.junit.runner.JUnitCore $(test_cp) diff --git a/chapter25/docs/examples/BubbleSort.smp b/chapter25/docs/examples/BubbleSort.smp index 1a4359ae..7327e461 100644 --- a/chapter25/docs/examples/BubbleSort.smp +++ b/chapter25/docs/examples/BubbleSort.smp @@ -6,14 +6,12 @@ // Bubble sort, with reading (parsing) and writing (formatting) the data. val sort = { sys.aryi64 nums -> - var done = false; - while( !done ) { - done = true; + var more = nums; + while( more ) { + more = null; for( var i = 0; i < nums.len-1; i++ ) - if( nums.buf[i] > nums.buf[i+1] ) { - nums.swap(i,i+1); - done = false; - } + if( nums.buf[i] > nums.buf[i+1] ) + more = nums.swap(i,i+1); } }; @@ -33,7 +31,7 @@ val main = { u8[~][] args -> // Bubble sort array of integers sort(nums); - // Print the comma-separated result without the input brackets. - nums.csv().write(1); + // Print the same bracketed array-list format accepted as input. + nums.str().add('\n').write(1); return 0; }; diff --git a/chapter25/docs/examples/Capitalize.smp b/chapter25/docs/examples/Capitalize.smp new file mode 100644 index 00000000..72b5df70 --- /dev/null +++ b/chapter25/docs/examples/Capitalize.smp @@ -0,0 +1,23 @@ +// -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/capitalize/ + +val main = { u8[~][] args -> + if( args# > 2 ) { + sys.io.p("Use quotes around multiple strings.\n"); + return 0; + } + if( args# != 2 || args[1]# == 0 ) { + sys.io.p("Usage: please provide a string\n"); + return 0; + } + + u8[~] input = args[1]; + var output = new u8[input# + 1]; + sys.ary.copy(output,0,input,0,input#); + output[0] = sys.char.toupper(input[0]); + output[input#] = '\n'; + sys.io.p(output); + return 0; +}; diff --git a/chapter25/docs/examples/Dijkstra.smp b/chapter25/docs/examples/Dijkstra.smp new file mode 100644 index 00000000..57e1fad4 --- /dev/null +++ b/chapter25/docs/examples/Dijkstra.smp @@ -0,0 +1,73 @@ +// -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/dijkstra/ + +val shortestPath = { sys.aryi64 matrix, int nodes, int src, int dst -> + i64 infinity = (1 << 63)-1; + var dist = new i64[nodes]; + var visited = new sys.adt.bitset(); + // All nodes are infinitely far from each other + for( int i=0; i 0 && !visited.get(node) && best+weight < dist[node] ) + dist[node] = best+weight; + } + } + count++; + } + return result; +}; + +val usage = { -> + sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n"); + return 0; +}; + +val main = { u8[~][] args -> + // Exactly 3 args + if( args# != 4 ) return usage(); + // First is a serialized square matrix of positive numbers + var matrix = sys.aryi64.parseAryI64(args[1]); + if( !matrix ) return usage(); + if( !matrix.len ) return usage(); + // All numbers are positive + for( int i=0; i= nodes || dst < 0 || dst >= nodes ) + return usage(); // Source and destination land within the graph + + i64 cost = shortestPath(matrix,nodes,src,dst); + if( cost >= 0 ) { + new sys.aryu8().num(cost).add('\n').write(1); + return 0; + } + return usage(); +}; diff --git a/chapter25/docs/examples/FileIO.smp b/chapter25/docs/examples/FileIO.smp new file mode 100644 index 00000000..29f037bd --- /dev/null +++ b/chapter25/docs/examples/FileIO.smp @@ -0,0 +1,51 @@ +// -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/file-input-output/ + +val FILE = "output.txt"; + +val main = { u8[~][] args -> + var str = new sys.aryu8(); + str.addAry("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.\n"); + str.addAry("Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.\n"); + str.addAry("Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.\n"); + str.addAry("Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.\n"); + + // Create + i32 fd = sys.io.create(FILE); + if( fd == -1 ) return _error(); + // Write + int wrote = sys.io.writeOff(fd,str.buf,0,str.len); + if( wrote == -1 ) return _error(); + if( wrote != str.len ) return _error2(-2); + // Close + if( sys.io.close(fd) != 0 ) return _error(); + + // Open + i32 fd2 = sys.io.open(FILE); + if( fd2 == -1 ) return _error(); + // Read + var got = sys.io.read(fd2); + if( got# != str.len ) return _error2(-3); + // Close + if( sys.io.close(fd2) != 0 ) return _error(); + + // Check contents are equal + if( sys.ary.cmp(got,0,str.buf,0,str.len) ) + return _error2(-4); + + // Remove + if( sys.io.remove(FILE) != 0 ) return _error(); + + sys.io.p("File I/O succeeded\n"); + return 0; +}; + +val _error2 = { i32 errno -> + sys.io.remove(FILE); + new sys.aryu8().addAry("Failed with error code ").num(errno).add('\n').write(sys.libc.STDERR); + sys.libc._exit(errno); +}; + +val _error = { -> _error2(sys.libc.errno); }; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index 9fac7a99..532f5c70 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -50,18 +50,58 @@ import java.util.Random; public class IterPeeps { public final WorkList _work; + final WorkList _workInline; - public IterPeeps( long seed ) { _work = new WorkList<>(seed); } + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } @SuppressWarnings("unchecked") public N add( N n ) { return (N)_work.push(n); } public void addAll( Ary ary ) { _work.addAll(ary); } + public void deferInline( CodeGen code, CallEndNode cend ) { + if( !code._midAssert ) + _workInline.push(cend); + } + /** - * Iterate peepholes to a fixed point + * Iterate peepholes and inlining to a fixed point */ public void iterate( CodeGen code ) { + CallEndNode cend = null; + boolean didInline = false; + Ary defer = new Ary<>(Node.class); + while( true ) { + // Clean up everything that does not grow the code + iteratePeeps(code); + + // Pick an inline candidate, no real heuristic, first come, first served + while( (cend=_workInline.pop()) != null) { + if( cend.isDead() ) continue; + if( cend.inline() == -1 ) defer.add(cend); + if( cend.inline() > 0 ) break; + } + // Found an inline candidate, so inline + if( cend != null ) { + // Inline, run peeps until clean again + cend.doInline(); + didInline = true; + continue; + } + // No more candidates, check the defer list + if( !didInline ) break; // No more progress, so all the "maybe inline after cleanup" do not progress + // Some inlining happened, retry all the "try again after cleanup" calls + didInline = false; + code.addAll(defer); + defer.clear(); + } + } + + // Run all the code-reduction and type-lifting peeps as possible + private void iteratePeeps( CodeGen code ) { assert progressOnList(code, _work, true); int cnt=0; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index e964fa5b..98093a77 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -100,6 +100,7 @@ public class Parser { ScopeNode _breakScope; // Merge all the while-breaks here ScopeNode _continueScope; // Merge all the while-continues here ScopeNode _returnScope; // Merge all the function exits here + Ary _frefs; // Forward refs created during this parse TypeStruct _ctorOpenStruct; // Open struct being initialized by an allocation constructor block. // Mapping from a type name to a Type. The string name matches @@ -164,7 +165,9 @@ public class Parser { public Ary parse( CompUnit ref ) { assert _scope == null && _breakScope == null && _continueScope == null && _returnScope == null; + assert _frefs == null; _lexer = new Lexer(ref._src); + _frefs = new Ary<>(FRefNode.class); // Starting Scope has control, memory, initial arguments _scope = new ScopeNode(); _scope.define(ScopeNode.CTRL, Type.CONTROL , false, null, _lexer); @@ -183,12 +186,12 @@ public class Parser { if( !_lexer.isEOF() ) throw _errorSyntax("unexpected"); - // At the top scope and every new var should be a FRef, and these + // All still-unresolved forward refs // should immediately resolve to a file-based name which is a Simple // class type. Ary frefs = new Ary<>(FRefNode.class); - for( int i=2; i<_scope._vars._len; i++ ) { - FRefNode fref = (FRefNode)_scope._inputs.at(i); + for( FRefNode fref : _frefs ) { + if( fref.nIns() != 1 && fref._con == FRefNode.FREF_TYPE ) continue; CompUnit cu = ParseAll.findCompUnitOrThrow(_code,_ref,fref._name); fref._con = TypeMemPtr.make((byte)2,TypeStruct.make(addClzPrefix(cu._cname),true),true); frefs.push(fref); @@ -201,6 +204,7 @@ public class Parser { _xScopes.pop(); _scope.kill(); _scope = null; + _frefs = null; return frefs; } @@ -475,7 +479,7 @@ public class Parser { Field[] fs = new Field[self._fields.length]; for( int i=0; i (doRHS=match(fside)) ? parseStatement() : con(lhs._type.makeZero()); case ":" -> (doRHS=match(fside)) ? parseAsgn() : con(lhs._type.makeZero()); - case "&&" -> rhs = pred; - case "||" -> rhs = parseLogical(); + case "&&" -> con(lhs._type.makeZero()); // pred && expr_is_ignored + case "||" -> parseLogical(); // pred || expr default -> throw TODO(); }; rhs.keep(); _scope.removeGuards(ifF); - if( doRHS ) + // The RHS of `||` is parsed on the false side, so retain its updated + // control, memory and locals just as an explicit else arm does. + if( doRHS || fside.equals("||") ) fScope = _scope; pred.unkeep(); @@ -889,7 +897,7 @@ public class Parser { _returnScope = _scope.dup(); while( lexN+1 < _returnScope.depth() ) _returnScope._pop(); // Pop a nested block scope until we hit the function scope - _returnScope.define("$expr", expr._type.glb(false), true, expr, null); + _returnScope.define("$expr", inferredReturnType(expr._type), true, expr, null); } else { // For and - ALL FIELDS IN LAST SCOPE are live @@ -998,6 +1006,34 @@ public class Parser { return peep(new ConvertNode(t,expr)); } + // Inferred `var` declarations describe writable slots, not the exact + // value used to initialize them. Explicitly typed locals retain the + // user's nullability and numeric-width guarantees; `val` retains the + // initializer's precise type. + private static Type mutableInferredType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + case TypeMemPtr tmp -> tmp.makeVar(); + case TypeFunPtr tfp -> tfp; + case TypeConAry a -> a; + case TypePtr ptr -> TypePtr.PTR; + case TypeScalar ts -> TypeScalar.BOT; + default -> t; + }; + } + + // Seed an inferred return merge with the declared numeric family instead + // of a transient constant/range. Pointer nullability remains part of the + // inferred function result and is combined by the later Phi. + private static Type inferredReturnType(Type t) { + return switch( t ) { + case TypeInteger ti -> TypeInteger.BOT; + case TypeFloat tf -> TypeFloat.F64; + default -> t; + }; + } + private Node widenInt( Node expr, Type t ) { return (expr._type instanceof TypeInteger || expr._type==Type.NIL) && t instanceof TypeFloat ? peep(new ToFloatNode(expr)) : expr; @@ -1064,7 +1100,7 @@ public class Parser { if( expr._type==Type.NIL ) throw error("a not-null/non-zero expression"); t = expr._type; - if( !xfinal ) t = t.glb(false); // Widen if not final + if( !xfinal ) t = mutableInferredType(t); } // Final is deep on ptrs @@ -1074,7 +1110,8 @@ public class Parser { } // expr is a constant function - if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + if( t instanceof TypeFunPtr decl && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { + t = decl.makeFrom(tfp.fidx()); FunNode fun = _code.link(tfp); if( fun != null ) fun.setName(name); // Assign debug name to Simple function @@ -1158,6 +1195,8 @@ public class Parser { ts = ctorFld==null ? TypeStruct.make(clzName,false,fld) : TypeStruct.make(clzName,false,fld,ctorFld); + TypeFunPtr alloc = makeAllocator((TypeStruct)TYPES.get(fullName),ret,ctorFld); + ts = ts.add(Field.make("",alloc,_code.alias(_ref._cname),true)); TYPES.put(clzName,ts); // Insert a field in the containing class with the nested class type. @@ -1169,6 +1208,78 @@ public class Parser { return require(_code.ZERO,";"); } + // Build the declaration-side allocation helper. Allocation sites only + // call this function; all layout, initialization and publication choices + // are made here, where the complete struct and constructor are known. + private TypeFunPtr makeAllocator(TypeStruct ts, ReturnNode initRet, Field ctorFld) { + TypeFunPtr ctor = ctorFld==null ? null : (TypeFunPtr)ctorFld._t; + int nargs = ctor==null ? 0 : ctor.nargs()-2; // Hide self and selfMem + Type[] atypes = new Type[nargs]; + for( int i=0; i").intern(); + + int oldUID = _code.UID(); + FunNode fun = (FunNode)new FunNode(loc(),sig,name,_ref,null,_ref._start).peephole(); + _code.link(fun); + Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,ConstantNode.seed(TypeRPC.BOT).peephole()).peephole(); + Node pub = new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun, + new ProjNode(_ref._start,1,ScopeNode.MEM0).peephole()).peephole(); + Node[] parms = new Node[nargs]; + for( int i=0; i code @@ -1816,7 +1927,8 @@ public class Parser { t = TypeMemPtr.make((byte)2,clz,true); } // Define the FRef - var = _scope.defineFRef(id,t,cu!=null,loc()); + var = _scope.defineFRef(id,t,true,loc()); + _frefs.push((FRefNode)_scope.in(var)); } // Load local value @@ -1867,7 +1979,7 @@ public class Parser { int selfx = _scope.kindFcn(var)._lexSize; // Might be a method call from inside a method, so no explicit "self". // Pass the in-scope "self" - return parsePostfixMethod(rvalue,_scope.in(selfx)); + return parsePostfixMethod(rvalue,_scope.in(_scope.update(_scope.var(selfx),null))); } // Assign-update direct into Scope Node op = opAssign(ch,rvalue, var.type() ); @@ -1897,11 +2009,13 @@ public class Parser { case '-' -> new SubNode(lhs,rhs); case '*' -> new MulNode(lhs,rhs); case '/' -> new DivNode(lhs,rhs); + case '|' -> new OrNode(null,lhs,rhs); + case '&' -> new AndNode(null,lhs,rhs); default -> throw TODO(); }; // Convert to float ops, or narrow int types; error if not declared type. // Also, if postfix LHS is still keep() - return convertExpr(peep(op),t.glb(false)); + return convertExpr(peep(op),t); } @@ -1931,59 +2045,38 @@ public class Parser { } private Node allocStruct(TypeStruct ts) { - Ary ctorArgs = constructorArgs(); // CNC TODO- BAD THREADING SELF-MEM - Node size = off(ts, " len"); - - // Build a NewNode; takes in ctrl and size. - // Produces a ptr and a private mem. - NewNode nnn = new NewNode(ts, ctrl(), size ).init(); - ProjNode self = new ProjNode(nnn,0,ts.str()).init().keep(); - ProjNode smem = new ProjNode(nnn,1,"#selfMem").init(); - - // Find a "class:XXX" struct, with field "XXX" function ptr as the - TypeStruct clz = (TypeStruct)TYPES.get(addClzPrefix(ts._name)); + Ary ctorArgs = constructorArgs(); + // A field declaration can leave a short forward type name in TYPES. + // Allocation happens in lexical context, so resolve that short name + // to the completed nested type before selecting its class helper. + String typeName = ts._name.indexOf('.') == -1 ? fullTypeName(ts._name) : ts._name; + Type resolved = TYPES.get(typeName); + if( resolved instanceof TypeStruct rts ) ts = rts; + TypeStruct clz = (TypeStruct)TYPES.get(addClzPrefix(typeName)); if( clz==null ) throw error("Unknown struct type '" + ts._name + "'"); - TypeFunPtr init = (TypeFunPtr)clz.field(initFieldName(ts._name))._t; - - // Call construct ($ctrl,$mem,NewNode.self,NewNode.#selfMem) and - // encourage inlining - Node initSelf = self._type.isa(init.arg(0)) ? self : peep(new CheckCastNode(init.arg(0),ctrl(),self)); - Ary args = new Ary<>(Node.class){{add(ctrl()); add(mem()); add(initSelf); add(smem); add(ConstantNode.seed(init)); }}; - Node selfMem = functionCall( args ); - // The returned value is a merge of private *Memory* and NOT some Scalar - - // Optional user constructor; same as the default constructor; private - // memory going in and out. - Field ctor = clz.field(""); - if( ctor != null ) - selfMem = constructorCall((TypeFunPtr)ctor._t,self,selfMem,ctorArgs); - else if( !ctorArgs.isEmpty() ) - throw error("Constructor arguments for '" + ts._name + "' but no constructor is defined"); - if( match("{") ) - throw error("Inline constructor blocks are no longer supported; define a constructor in '" + ts._name + "'"); - - // Might be TOP if parsing in dead/unreachable code - if( selfMem._type == Type.TOP ) { - _code.add(selfMem); - return self.unkeep(); - } - - // Escape all new aliases. EscapeNode inputs are the self pointer, the - // merged private memory, then all the named public aliases. The - // output is all the newly merged public aliases - but not actually - // bulk memory. - selfMem.keep(); - for( Field fld : ts._fields ) { - Field fld2 = fld._final ? fld : (Field)fld.glb(true); - Node prior = mem(); - Node esc = peep(new EscapeNode(fld2,self,selfMem,prior)); - mem(mergeAlias(prior,fld._alias,esc)); - } - - if( selfMem.unkeep().isUnused() ) selfMem.kill(); - else _code.add(selfMem); - return self.unkeep(); + Field afld = clz.field(""); + Node alloc; + if( afld != null ) { + TypeFunPtr tfp = (TypeFunPtr)afld._t; + FunNode fun = _code.link(tfp); + alloc = fun==null + ? new FRefNode((addClzPrefix(typeName)+".").intern(),loc()) + : new FunPtrNode(tfp,_code._start,fun.ret()).peephole(); + } else { + if( !ts._fref ) + throw error("Constructor arguments for '" + ts._name + "' but no constructor is defined"); + Type[] sig = new Type[ctorArgs._len]; + for( int i=0; i").intern(),loc(), + TypeFunPtr.make(false,sig,TypeMemPtr.make(ts))); + } + Ary args = new Ary<>(Node.class); + args.add(ctrl()); args.add(mem()); + for( Node arg : ctorArgs ) args.add(arg.unkeep()); + args.add(alloc); + return functionCall(args); } private Ary constructorArgs() { @@ -2000,29 +2093,6 @@ public class Parser { return args; } - // Constructors are called with two extra arguments: self and selfMem. - private Node constructorCall(TypeFunPtr ctor, Node self, Node selfMem, Ary ctorArgs) { - Ary args = new Ary<>(Node.class); - Node ctorSelf = self._type.isa(ctor.arg(0)) - ? self - : peep(new CheckCastNode(ctor.arg(0),ctrl(),self)); - args.add(ctrl()); - args.add(mem()); - args.add(ctorSelf); - args.add(selfMem); - for( Node arg : ctorArgs ) - args.add(arg.unkeep()); - args.add(ConstantNode.seed(ctor)); - - CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole(); - CallEndNode cend = (CallEndNode)new CallEndNode(call,TypeRPC.constant(_code.rpc(_ref._cname))).peephole(); - call.peephole(); - cend = (CallEndNode)cend.keep().peephole(); - ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); - mem (new ProjNode(cend,1,ScopeNode.MEM0).peephole()); - return new ProjNode(cend.unkeep(),2,"#selfMem").peephole(); - } - private Node allocArray(TypeStruct ts, Node len) { Field lenFld = ts.field("#" ); Field bodyFld = ts.field("[]"); @@ -2104,7 +2174,8 @@ public class Parser { } private Node defaultSelf() { - return _scope.in(_scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize); + int selfx = _scope._kinds.at(_scope.enclosingFuncOrDecl())._lexSize; + return _scope.in(_scope.update(_scope.var(selfx),null)); } /** @@ -2147,8 +2218,18 @@ public class Parser { } Field fld = ts==null ? null : ts.field(name); + if( fld==null && ts!=null && !startsClzPrefix(ts._name) ) { + Type clz0 = TYPES.get(addClzPrefix(ts._name)); + if( clz0 instanceof TypeStruct clz && (fld = latestStruct(clz).field(name)) != null ) { + expr.unkeep(); + ts = latestStruct(clz); + expr = con(TypeMemPtr.make((byte)2,ts,true)).keep(); + } + } if( fld==null && ts!=null ) fld = fieldOrOpen(ts,name,false); + if( fld==null && ts!=null && !latestStruct(ts)._open ) + throw error("Accessing unknown field '"+name+"' from '*"+ts._name+"'"); // With no field, we will update the bulk memory int alias = fld==null ? 1 : fld._alias; Type decl = fld==null ? Type.BOTTOM : fld._t; @@ -2195,7 +2276,7 @@ public class Parser { throw error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor" ); Node op = opAssign(ch,load, decl ); mem.keep(); - Node st = new StoreNode(loc(), name, alias, decl.glb(true), ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); + Node st = new StoreNode(loc(), name, alias, decl, ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); storeMem(st,alias,mem); st.unkeep(); mem.unkeep(); @@ -2416,6 +2497,7 @@ public class Parser { private char escapedChar(String kind) { char esc = _lexer.nextChar(); return switch( esc ) { + case '0' -> '\u0000'; case 'n' -> '\n'; case 't' -> '\t'; case 'r' -> '\r'; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 85d8143b..50f5c33b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -77,6 +77,7 @@ public class CodeGen { // True when fidx is published through a public field of a public class. // TypeStruct.fidxs() already excludes private (underscore) fields. public boolean publicFIDX(int fidx) { + if( fidx < GlobalBits.RESERVED ) return false; // A public class initializer is itself an external root; unlike // constructors and methods, it is not reached through a class field. FunNode fun = _linker.atX(fidx); @@ -128,7 +129,7 @@ public class CodeGen { void freezePublicInterface() { assert _publicFIDXs==null && _publicAliases==null; int[] fidxs = XInt.EMPTY; - for( int fidx=1; fidx<_linker._len; fidx++ ) + for( int fidx=GlobalBits.RESERVED; fidx<_linker._len; fidx++ ) if( publicFIDX(fidx) ) fidxs = XInt.make(fidxs,fidx); int[] aliases = XInt.EMPTY; @@ -268,7 +269,9 @@ public class CodeGen { if( (dump & (1<<30)) != 0 ) System.err.println("After "+_phase+":"); - System.err.println(IRPrinter.prettyPrint(this)); + System.err.println(_phase.ordinal() >= Phase.LocalSched.ordinal() + ? asm(new SB()).toString() + : IRPrinter.prettyPrint(this)); return p2; } @@ -444,11 +447,13 @@ public class CodeGen { // The phase shift closes all parser-in-progress states and freezes // unknown external inputs. Imported nodes carry post-Opto escape - // precision, but Iter is a fresh pessimistic solve: non-singleton - // memory must restart at FULL so newly discovered private escapes can - // only be removed, never added. Seed the complete graph once. + // precision, but Iter is a fresh pessimistic solve: memory escape + // summaries must restart at FULL so newly discovered private escapes + // can only be removed, never added. Seed the complete graph once. + boolean hasImports = _externPaths != null; _start.walk(n -> { - n._type = iterEscapeReset(n._type); + if( !(n instanceof ConstantNode) ) + n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); add(n); return null; }); @@ -473,6 +478,26 @@ public class CodeGen { return t; } + private static Type iterImportReset(Type t) { + if( t.isHigh() ) + return t.dual(); + if( t instanceof TypeMem mem ) + return TypeMem.make(mem._alias,iterImportReset(mem._t),mem._one,mem._clz,mem._final,XInt.FULL,XInt.FULL); + if( t instanceof TypeMemPtr ) + return t.makeStorage(); + if( t instanceof TypeStruct ) + return t.makeStorage(); + if( t instanceof TypeTuple tt ) { + TypeTuple rez = tt; + for( int i=0; i Phase.Schedule.ordinal() ) - return IRPrinter.prettyPrint( this ); if( _stop == null ) return "No StopNode"; - return _stop.p(4999); + return IRPrinter.prettyPrint(this); } // Debugging helper diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index 274be838..7af7e5f1 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -317,10 +317,11 @@ public class ElfWriter { } // Write relocations for the constant pool + String cpoolPrefix = _code.entryClinitName().replaceAll("[^A-Za-z0-9_$]", "_") + "$CPOOL$"; for( Encoding.Relo relo : enc._bigCons.values() ) { boolean ro = !(relo._t instanceof TypeStruct ts) || ts.isConstant(); DataSection data = ro ? rodata : rwdata; - int symidx = symbols.symbol("CPOOL$"+symbols.gidx(), data._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC, relo._target, relo._t.size()); + int symidx = symbols.symbol(cpoolPrefix+symbols.gidx(), data._index, SYM_BIND_GLOBAL, SYM_TYPE_FUNC, relo._target, relo._t.size()); relocations.writeReloOffPlus(relo._opStart+relo._off, symidx, relo._elf ); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index fa187000..f13e8ae3 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -24,7 +24,7 @@ public abstract class GlobalCodeMotion { schedEarly(code); // Break up shared global constants by functions - breakUpGlobalConstants(code._start ); + breakUpGlobalConstants(code._start); code._visit.clear(); schedLate(code); @@ -44,32 +44,31 @@ public abstract class GlobalCodeMotion { } // Break up shared global constants by functions - private static void breakUpGlobalConstants( Node start ) { + private static void breakUpGlobalConstants( StartNode start ) { - // For all global constants + // For all explicitly Start-pinned global values. Instruction + // selection keeps each zero-code/global chain member hooked to Start, + // so no later pass has to infer hidden global chains from data inputs. for( int i=0; i< start.nOuts(); i++ ) { Node con = start.out(i); - // Instruction selection can expand one shared TypeNode constant - // into a constant-valued machine expression. Split either form - // before scheduling, since separate functions have no CFG LCA. - if( !(con instanceof CFGNode) && - ((con._type.isHighOrConst() && con.isConst()) || - con instanceof MachNode mach && mach.isClone() && con._type.isConstant()) ) { - breakUpGlobalConstantSingle( con ); - i--; // Removed a global constant, re-run same index + if( isStartPinnedGlobalValue(con) ) { + breakUpGlobalConstantSingle(con); + if( con.nIns()==0 || con.in(0) != start ) + i--; // Removed a global constant, re-run same index } } } private static void breakUpGlobalConstantSingle( Node con ) { - // If an immediate global-value user still spans functions, it cannot - // yet be assigned to one clone. Keeping the constant at Start is a - // valid schedule; a downstream value with concrete ownership can be - // split independently. + // Split dependent global values first; cloning a later chain member + // will recursively clone its Start-pinned inputs on demand. for( Node use : con.outs() ) - if( use != null && useFun(use)==null ) - return; + if( use != null && useFun(use)==null ) { + if( !isStartPinnedGlobalValue(use) ) + return; + breakUpGlobalConstantSingle(use); + } // While constant has users in different functions while( true ) { // Find a function user, and another function @@ -82,22 +81,16 @@ public abstract class GlobalCodeMotion { if( fun==null || fun==fun2 ) fun=fun2; else { done=false; break; } } + // No direct function users: keep this global value at Start. + if( fun==null ) + return; // Single function user, so this constant is not shared if( done ) { con.setDef(0,fun); return; } // Move function users to a private constant - Node con2 = con.copy(); // Private constant clone - // Node copies made through Node(Node) carry unregistered inputs, - // while some machine copies construct fresh registered edges. - // Detach correctly in either case before pinning to the function. - Node old = con2.in(0); - if( old != null && old._outputs.find(con2) != -1 ) - con2.setDef(0,null); - else - con2._inputs.set(0,null); - con2.setDef(0,fun); + Node con2 = cloneGlobalForFun(con,fun,new IdentityHashMap<>()); // Move function users to this private constant for( int j=0; j memo) { + Node memoized = memo.get(con); + if( memoized != null ) return memoized; + Node con2 = con.copy(); // Private constant clone + // Node copies made through Node(Node) carry unregistered inputs, while + // some machine copies construct fresh registered edges. The default + // Node.copy path gives an input-less clone. Normalize all of them to + // the original data inputs, pinned to the owning function. + memo.put(con,con2); + if( con2.nIns()==0 ) { + con2.addDef(fun); + for( int i=1; i memo) { + return isStartPinnedGlobalValue(def) + ? cloneGlobalForFun(def,fun,memo) + : def; + } + + private static boolean isStartPinnedGlobalValue(Node n) { + return n != null && n._type != null && !(n instanceof CFGNode) && + n.nIns() > 0 && n.in(0) instanceof StartNode && + (n.isConst() || n instanceof MachNode mach && mach.outregmap()!=null); + } + private static FunNode useFun(Node use) { return useFun(use,new BitSet()); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 1d88597c..2b559a38 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -207,18 +207,11 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - // Disallow clone-ables from killing registers. Just fail - // them and re-clone closer to target... so no kill. - // Special case for Intel XOR used to zero. - Node n = (Node)m; - CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0(); - if( m.isClone() && // Must be clonable - (n.nOuts()>1 || // Has many users OR - // Only 1 user but effective use is remote block - effUseBlk != n.cfg0() )) - // Then fail the clonable; it should split or move - alloc.fail(alloc.lrg((Node)m)); - // Else clonable cannot move + Node live = TMP.get(tlrg); + // Disallow clone-ables from living across killed registers. + // Fail them and let splitting re-clone closer to the target use. + if( live instanceof MachNode mach && mach.isClone() ) + alloc.fail(tlrg); else if( !tlrg.sub(killMask) ) alloc.fail(tlrg); } @@ -328,7 +321,7 @@ abstract public class IFG { // Pull all lrgs from IFG, in trivial order if possible while( sptr < color_stack.length ) { // Swap best color up front - pickColor(color_stack,sptr,swork); + pickColor(color_stack,sptr,swork,alloc); // Pick a trivial lrg, and (temporarily) remove from the IFG. LRG lrg = color_stack[sptr++]; @@ -384,10 +377,10 @@ abstract public class IFG { } // Pick LRG from color stack - private static void pickColor(LRG[] color_stack, int sptr, int swork) { + private static void pickColor(LRG[] color_stack, int sptr, int swork, RegAlloc alloc) { // Out of trivial colorable, pick an at-risk to pull if( sptr==swork ) - swap(color_stack,sptr,pickRisky(color_stack,sptr)); + swap(color_stack,sptr,pickRisky(color_stack,sptr,alloc)); // When coloring, we'd like to give more choices; so when coloring we'd // like to see the single-def first (since no choices anyway), then // non-split related (so more live ranges get colored), then @@ -422,12 +415,12 @@ abstract public class IFG { // Pick a live range that hasn't already spilled, or has a single-def- // single-use that are not adjacent. - private static int pickRisky( LRG[] color_stack, int sptr ) { + private static int pickRisky( LRG[] color_stack, int sptr, RegAlloc alloc ) { int best=sptr; - int bestScore = pickRiskyScore(color_stack[best]); + int bestScore = pickRiskyScore(color_stack[best],alloc); for( int i=sptr+1; i bestScore ) { best = i; bestScore = iScore; } } @@ -442,32 +435,55 @@ abstract public class IFG { // // Picking a live range that is very close to coloring might allow it to // color despite being risky. - private static int pickRiskyScore( LRG lrg ) { + private static int pickRiskyScore( LRG lrg, RegAlloc alloc ) { + // Callee-save live ranges cover the whole function and are cheap to + // split. Rank scheduled area recovered against the loop-scaled cost + // of the def- and use-side moves. + if( lrg._machDef instanceof CalleeSaveNode ) + return areaScore(functionArea(lrg._fun,alloc), + splitCost((Node)lrg._machDef,(Node)lrg._machUse)); + if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && + lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) + return areaScore(functionArea(lrg._fun,alloc), + splitCost(lrg._splitDef,lrg._splitUse)); + // Pick single-def clonables that are not right next to their single-use. - // Failing to color these will clone them closer to their uses. + // Rank by the area recovered by cloning closer to the use. if( !lrg._multiDef && lrg._machDef.isClone() && lrg._machUse != null ) { Node def = ((Node)lrg._machDef); Node use = ((Node)lrg._machUse); CFGNode cfg = def.cfg0(); - if( cfg != use.cfg0() || // Different blocks OR - // Same block, but not close - cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) - return 1000000; + int area = cfg != use.cfg0() + ? functionArea(lrg._fun,alloc) + : cfg._outputs.find(use)-cfg._outputs.find(def)-1; + if( area > 0 ) + return areaScore(area,loopCost(use)); } - // Always pick callee-save registers as being very large area recovered - // and very cheap to spill. - if( lrg._machDef instanceof CalleeSaveNode ) - return 1000000-2-lrg._mask.firstReg(); - if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && - lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) - return 1000000-1; - - // TODO: cost/benefit model. Perhaps counting loop-depth (freq) of def/use for cost - // and "area" for benefit + // Default for ranges without a specific area/cost estimate. return 1000 + (lrg._multiUse ? -100 : 0); } + private static int functionArea(FunNode fun, RegAlloc alloc) { + int area=0; + for( CFGNode bb : alloc._code._cfg ) + if( bb.fun()==fun ) + area += bb.nOuts(); + return area; + } + + private static int areaScore(int area, int cost) { + return 1000 + (area<<10)/cost; + } + + private static int splitCost(Node def, Node use) { + return loopCost(def) + (use==null ? 0 : loopCost(use)); + } + + private static int loopCost(Node n) { + return 1 << (n.cfg0().loopDepth()*3); + } + private static short biasColor( RegAlloc alloc, LRG lrg, short reg, RegMask mask ) { if( mask.size1() ) return reg; // Check chain of splits up the def-chain. Take first allocated diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java index b88067c4..5d4c151d 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -127,6 +127,10 @@ abstract public class Opto { private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { if( tfp.nargs() != call.nargs() ) return; // Error calls hit this int[] fidxs = tfp.fidxs(); + // An unresolved forward call can still carry the infinite, inferred + // function set into Opto. There is no finite call graph to link yet; + // type checking will report the unresolved reference afterwards. + if( XInt.isHigh(fidxs) ) return; for( int fidx = XInt.next(fidxs,0); fidx >=0; fidx = XInt.next(fidxs,fidx) ) { // unlinkStart deliberately leaves uncalled functions in a // temporarily dead limbo. A newly discovered call revives them; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 191016be..90309328 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -114,15 +114,32 @@ public abstract class ParseAll { code._stop.walk( (Node n) -> { n.upgradeType(Parser.TYPES); if( n instanceof FRefNode fref ) { - TypeStruct clz = (TypeStruct)Parser.TYPES.get(fref._name); + boolean alloc = fref._name.endsWith("."); + String clzName = alloc + ? fref._name.substring(0,fref._name.length()-".".length()).intern() + : fref._name; + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); if( clz == null ) return null; - // Class pointer: - TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); - // Class pointer constant: - ConstantNode clzCon = code.con(clzptr); + Node con; + if( alloc ) { + Field ctor = clz.field(""); + if( ctor == null || !(ctor._t instanceof TypeFunPtr tfp) ) { + String name = clzName.startsWith(Parser.CLZ) + ? clzName.substring(Parser.CLZ.length()) : clzName; + int dot = name.lastIndexOf('.'); + throw Parser.error("Unknown struct type '"+(dot==-1 ? name : name.substring(dot+1))+"'",fref._loc); + } + FunNode fun = code.link(tfp); + if( fun == null ) return null; + con = new FunPtrNode(tfp,code._start,fun.ret()).peephole(); + } else { + // Class pointer constant: + TypeMemPtr clzptr = TypeMemPtr.make((byte)2,clz,true); + con = code.con(clzptr); + } // Replace and optimize - fref.addDef(clzCon); + fref.addDef(con); code.add(fref); } // Adds sort by NIDs, which just got shuffled diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 4c00391c..0d5b9e7b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -61,6 +61,9 @@ public class RegAlloc { // ----------------------- // Live ranges with self-conflicts or no allowed registers private final IdentityHashMap _failed = new IdentityHashMap<>(); + // Loop Phis get one chance to color after only cold self-conflict splits. + // If the same Phi self-conflicts again, split its hot def/backedge also. + private final IdentityHashMap _deferredLoopSelf = new IdentityHashMap<>(); void fail( LRG lrg ) { assert lrg.leader(); _failed.put(lrg,""); @@ -171,6 +174,8 @@ public class RegAlloc { for( Node n : bb._outputs ) if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } + // Expensive assert: useful when chasing cross-function allocator edges. + //assert verifyFunctionLocalEdges(); // Top driver: repeated rounds of coloring and splitting. byte round=0; @@ -184,6 +189,63 @@ public class RegAlloc { _done = true; } + private boolean verifyFunctionLocalEdges() { + for( CFGNode bb : _code._cfg ) + for( Node use : bb._outputs ) { + FunNode useFun = funOf(use); + for( int i=1; i ") + .append(use.uniqueName()).append("(").append(useFun.label()).append(") input ").append(idx) + .append(" def=").append(def).append(" use=").append(use).append("\n all uses:"); + for( Node out : def.outs() ) { + FunNode outFun = funOf(out); + sb.append("\n ").append(out.uniqueName()).append("(") + .append(outFun==null ? "?" : outFun.label()).append(")"); + } + return sb.toString(); + } + + private static boolean allowedCrossFunctionEdge(Node use, int idx, Node def) { + // Function metadata/control edges are not value live ranges. + if( use instanceof FunNode || use instanceof StopNode || use instanceof StopCUNode ) + return true; + // Return-linked function pointers carry function identity/lifetime, not + // an allocator value flowing from the callee body into this function. + if( use instanceof FunPtrNode && def instanceof ReturnNode ) + return true; + // Parm defaults and call-linked argument edges are the entry protocol; + // BuildLRG also skips Parm input 1. + if( use instanceof ParmNode ) + return true; + // Linked CallEnd -> Return edges should be gone before RegAlloc, but + // diagnose allocator value edges rather than call graph metadata here. + if( use instanceof CallEndNode && def instanceof ReturnNode ) + return true; + return false; + } + + private static FunNode funOf(Node n) { + if( n instanceof ParmNode parm ) return parm.fun(); + if( n instanceof ReturnNode ret ) return ret.fun(); + if( n instanceof FunNode fun ) return fun; + if( n instanceof CFGNode cfg ) return cfg.fun(); + CFGNode cfg = n.cfg0(); + return cfg==null ? null : cfg.fun(); + } + private boolean graphColor(byte round) { _failed.clear(); _lrgs.clear(); @@ -227,7 +289,7 @@ public class RegAlloc { // Register mask when empty; split around defs and uses with limited // register masks. - if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { + if( lrg._mask.isEmpty() ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) @@ -238,6 +300,10 @@ public class RegAlloc { if( splitEmptyMaskByUse(round,lrg) ) return true; } + if( lrg._mask.isEmpty() && lrg._multiDef && lrg._1regUseCnt > 1 && lrg._1regDefCnt <= 1 ) { + if( splitEmptyMaskSingleUses(round,lrg) ) + return true; + } // Generic split-by-loop depth. return splitByLoop(round,lrg); @@ -322,6 +388,26 @@ public class RegAlloc { return true; } + // Empty-mask live range with several direct single-register uses, often + // through a Phi with multiple defs. Split those uses directly instead of + // doing a loop-depth split, which might keep isolating the wrong edge. + boolean splitEmptyMaskSingleUses( byte round, LRG lrg ) { + findAllLRG(lrg); + if( _ns._len <= 5 ) + return false; + boolean progress = false; + for( Node n : _ns ) { + if( !(n instanceof MachNode mach) ) continue; + for( int i=1; i x._nid - y._nid ); + // First encounter with a loop Phi: try only cold splits this round. + // Remember the Phi across rounds so a persistent self-conflict forces + // the hot def/backedge splits on the next encounter. + IdentityHashMap deferred = new IdentityHashMap<>(); + for( Node def : conflicts ) { + if( def instanceof PhiNode phi && phi.region() instanceof LoopNode ) + deferLoopSelf(phi,deferred); + for( Node use : def._outputs ) + if( use instanceof PhiNode phi && phi.region() instanceof LoopNode && + phi._inputs.find(def)==2 ) + deferLoopSelf(phi,deferred); + } + // For all conflicts for( Node def : conflicts ) { assert lrg(def)==lrg; // Might be conflict use-side @@ -354,6 +453,7 @@ public class RegAlloc { for( int i=0; i loop.idepth() ) ) || (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) ) insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg ); @@ -362,10 +462,12 @@ public class RegAlloc { // Phi slot 1 (and not all inputs), because Phis extend the live range. // TODO: split before all inputs (except the last; at least 1 split here must be extra) if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) { - SplitNode split = makeSplit("def/self",round,lrg); - insertAfterAndReplace(split,def,false); - if( split.nOuts()==0 ) - split.killOrdered(); + if( !deferred.containsKey(phi) ) { + SplitNode split = makeSplit("def/self",round,lrg); + insertAfterAndReplace(split,def,false); + if( split.nOuts()==0 ) + split.killOrdered(); + } insertBefore(phi,1,"use/self/phi",round,lrg); } // Split before two-address ops which extend the live range @@ -375,6 +477,13 @@ public class RegAlloc { return true; } + private void deferLoopSelf(PhiNode phi, IdentityHashMap deferred) { + if( !_deferredLoopSelf.containsKey(phi) ) { + _deferredLoopSelf.put(phi,""); + deferred.put(phi,""); + } + } + // Generic: split around the outermost loop with non-split def/uses. This // covers both self-conflicts (once we split deep enough) and register @@ -401,9 +510,11 @@ public class RegAlloc { int min = (int)ld; int max = (int)(ld>>32); - - // If the minLoopDepth is less than the maxLoopDepth: for-all defs and - // uses, if at minLoopDepth or lower, split after def and before use. + boolean emptyMulti = lrg._mask.isEmpty() && lrg._multiDef && lrg._1regDefCnt <= 1 && + (lrg._1regUseCnt > 1 || _ns._len > 5); + // Multi-def empty-mask conflicts need the hot/deep side isolated from + // fixed register uses. Ordinary pressure splits keep the old shallow + // boundary behavior. for( Node n : _ns ) { if( n instanceof SplitNode && min!=max ) continue; // Ignoring splits; since spilling need to split in a deeper loop if( n.isDead() ) continue; // Some Cloneable went dead by other spill changes @@ -414,7 +525,7 @@ public class RegAlloc { if( lrg(n)==lrg && // This is a LRG def // At loop boundary, or splitting in inner loop - (min==max || n.cfg0().loopDepth() <= min) ) { + (min==max || (emptyMulti ? n.cfg0().loopDepth() >= max : n.cfg0().loopDepth() <= min)) ) { // Cloneable constants will be cloned at uses, not after def if( !(n instanceof MachNode mach && mach.isClone()) && // Single user is already a split adjacent @@ -429,7 +540,7 @@ public class RegAlloc { // No split in front of a split if( !(n.in(i) instanceof SplitNode) && // splitting in inner loop or at loop border - (min==max || phi.region().cfg(i).loopDepth() <= min) && + (min==max || (emptyMulti ? phi.region().cfg(i).loopDepth() >= max : phi.region().cfg(i).loopDepth() <= min)) && // and not around the backedge of a loop (bad place to force a split, hard to remove) !(phi.region() instanceof LoopNode && i==2 && (phi.in(i) instanceof PhiNode pp && pp.region()==phi.region())) ) // Split before phi-use in prior block @@ -441,7 +552,8 @@ public class RegAlloc { // This is a LRG use // splitting in inner loop or at loop border if( lrgSame( n.in( i ), lrg ) && - (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || n.cfg0().loopDepth() <= min) ) + (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || + (emptyMulti ? n.cfg0().loopDepth() >= max : n.cfg0().loopDepth() <= min)) ) // Split before in this block insertBefore( n, i, "use/loop/use", round,lrg, false ); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index 8014bb2c..7c230f9c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -177,7 +177,6 @@ abstract public class Serialize { IdentityHashMap anodes = new IdentityHashMap<>(); for( Node n : nodes ) anodes.put(n,anodes.size()+1); // +1 bias, reserve 0 for null - // First cut: 1 byte opcode, optional per-node info, includes variable nIns for( Node n : nodes ) { baos.packed1(n.serialTag().ordinal()); @@ -367,9 +366,11 @@ abstract public class Serialize { // MemMerge precise aliases are encoded by their input slot. // Remap populated file-local slots into this compilation's // local alias numbering; null holes carry no identity. - int local = n instanceof MemMergeNode && i >= GlobalBits.RESERVED && def != null - ? aliases.map(fileAliases,i) - : i; + int local = i; + if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { + if( def == null ) continue; + local = aliases.map(fileAliases,i); + } n.setDefX(local,def); // Call's output[0] is always the CallEnd if( n instanceof CallEndNode cend && i==0 ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 8e7f47f3..061232c7 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -16,6 +16,12 @@ public class CallEndNode extends CFGNode implements MultiNode { // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; + // +2 must clone, so await all cleanup but OK + // +1 trivial now, + // 0: take a look, + // -1: somethings wrong, but might improve + // -2: never and stop asking, + private byte _inline; public final TypeRPC _rpc; public CallEndNode(CallNode call, TypeRPC rpc) { @@ -51,6 +57,7 @@ public class CallEndNode extends CFGNode implements MultiNode { public CallNode call() { return (CallNode)in(0); } boolean folding() { return _folding; } + public byte inline() { return _inline; } @Override public CFGNode idom(Node dep) { // Folding the idom is the one inlining Return @@ -101,14 +108,10 @@ public class CallEndNode extends CFGNode implements MultiNode { // appear later - meanwhile, we use a conservative approx of memory // effects. if( (nIns()-1)+externs < tfp.nfcns() ) { - // If before SCCP, we might call extras or also the unknown target. - StartNode start = CodeGen.CODE._start; - addDep(start); - Type tmem = start._type instanceof TypeTuple tt ? tt._types[1] : (start._type.isHigh() ? TypeMem.TOP : TypeMem.BOT); - Type ret = tfp.ret(); // If during Opto, assume call won't be called and thus won't return anything. - if( CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal() ) - ret = Type.TOP; + boolean opto = CodeGen.CODE._phase.ordinal() >= CodeGen.Phase.Opto.ordinal(); + Type tmem = opto ? TypeMem.TOP : TypeMem.BOT; + Type ret = opto ? Type.TOP : tfp.ret(); return TypeTuple.make(Type.CONTROL,tmem,ret); } @@ -118,6 +121,12 @@ public class CallEndNode extends CFGNode implements MultiNode { : TypeTuple.STATE.dual(); for( int i=1; i= CodeGen.Phase.Opto.ordinal() ) + return TypeTuple.make(Type.CONTROL,TypeMem.TOP,Type.TOP); // At least as good as the TFP return state.makeFrom(2,state.ret().join(tfp.ret())); } @@ -125,125 +134,112 @@ public class CallEndNode extends CFGNode implements MultiNode { @Override public Node idealize() { - // Worklist-based inlining. Cannot inline if folding, or calling - // multiple targets or no CallNode (malformed because dying). - if( !_folding && nIns()==2 && in(0) instanceof CallNode call ) { - Node fptr = call.fptr(); - if( fptr.isConst() && // We have an immediate call - // Function is being called, and its not-null - fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && !tfp.isHigh() && - // Arguments are correct - call.nargs()==tfp.nargs() && goodArgs(call,tfp) ) { - ReturnNode ret = (ReturnNode)in(1); - FunNode fun = ret.fun(); - int isTrivial = trivialInlining( fptr, fun ); - - // Encouraged inlining because small size and constructor. - int maxSize = fun._name!=null && fun.isInit() && !fun.isClz() ? 200 : 100; - if( isTrivial==1 && fun._approxUIDs < maxSize ) { - assert fun.sig().isa(tfp); - assert !CodeGen.CODE._midAssert; // Triggered inlining - CodeGen.CODE.add(fun); - // Remove the existing function linkage - call.unlink_all(); - // Clone the function body - FunNode fun2 = fun.copyBody(); - // Call uses the unique new function - Node fptr2 = new FunPtrNode(fun2.sig(),CodeGen.CODE._start,fun2.ret()).peephole(); - call.setDef(call.nIns()-1,fptr2); - // Link to the new function - call.link(fun2); - fun = fun2; - assert trivialInlining( fptr2, fun2 )==0; - isTrivial = 0; - } - - // Trivial inlining: call site calls a single function; single function - // is only called by this call site. - if( isTrivial==0 ) - return doTrivialInlining(fun); - - } else { // Function not (yet) a constant function pointer - addDep(fptr); - } + _inline = inlineCandidate(); + if( _inline == 1 ) { + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + doTrivialInlining(fun); + return this; } + // Delay for cleanup, before cloning + if( _inline >= 2 ) + CodeGen.CODE._iter.deferInline(CodeGen.CODE,this); return null; } - boolean goodArgs( CallNode call, TypeFunPtr tfp ) { - for( int i=0; i= maxSize ) + return -2; // Try later (if shrinking helps) + if( fun.body().cardinality() >= maxSize ) + return -1; // Try later (if cleanup makes the real body small enough) + + // Can be cloned but not trivial + if( fun.nIns() > 2 ) { addDep(fun); return 2; } + + // A candidate right now + return 1; + } - // If the *inlined* function is mid-collapse, also do not inline (yet) - idom = fun.ret(); - while( idom != fun ) { - if( idom==null ) return -1; // Forced off, half-folded call - if( idom instanceof FunNode fun2 ) - { addDep(fun2); return -1; } - if( idom instanceof CallEndNode cend && cend._folding ) - { addDep(cend); return -1; } - idom = idom.idom(); + public void doInline() { + assert _inline > 0; // Only called when possible to inline + + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + CallNode call = call(); + assert fun.sig().isa(call.fptr()._type); + + // Clone first + if( _inline==2 ) { + assert !CodeGen.CODE._midAssert; // Triggered inlining + // Remove the existing function linkage + call.unlink_all(); + // Clone the function body + FunNode fun2 = fun.copyBody(); + // Call uses the unique new function + Node fptr2 = new FunPtrNode(fun2.sig(),CodeGen.CODE._start,fun2.ret()).peephole(); + call.setDef(call.nIns()-1,fptr2); + // Link to the new function + call.link(fun2); + fun = fun2; } - // Only fun user is this call - if( fun.nIns() > 2 ) { addDep(fun); return 1; } // Trivial inlining: call site calls a single function; single function // is only called by this call site. - assert fun.in(1)==call(); + doTrivialInlining(fun); + } - return 0; + boolean goodArgs( CallNode call, TypeFunPtr tfp ) { + for( int i=0; i TYPES) { TypeFunPtr sig = (TypeFunPtr)_sig.upgradeType(TYPES); if( sig == _sig ) return false; @@ -323,12 +337,20 @@ public class FunNode extends RegionNode { ReturnNode ret2 = (ReturnNode)map.get(_ret); fun2._ret = ret2; ret2._fun = fun2; + BitSet body2 = new BitSet(); + for( Node n : map.values() ) + body2.set(n._nid); + + // Remove non-body callers. Body-local call edges were cloned along + // with their CallEnds and must stay linked so their cloned types remain + // monotonic during the post-Opto Iter. + for( int i=1; i 1 ) - if( fun2.in(1) instanceof CallNode call && body.get(call._nid) ) - call.unlink(fun2,1); // Recursive calls unlink - else fun2.removeDeadPath(1); // Start and external calls can just be removed + for( Node old : map.keySet() ) + if( old instanceof CallNode oldCall ) + relinkClonedCall(oldCall,(CallNode)map.get(oldCall),map); // Flip to a new FIDX to avoid confusion with the old one. // This is a non-monotonic (sideways) type move, only applicable @@ -338,6 +360,23 @@ public class FunNode extends RegionNode { return fun2; } + private static void relinkClonedCall( CallNode oldCall, CallNode call, IdentityHashMap map ) { + CallEndNode oldCend = oldCall.cend(); + if( oldCend==null || oldCend._folding ) + return; + for( int i=1; i 1 ) + cend._type = cend.compute(); + } + // Clone small function private void bodyCopy( BitSet visit, BitSet body, IdentityHashMap map, Node n ) { if( n==null ) return; @@ -357,18 +396,20 @@ public class FunNode extends RegionNode { if( visit.get(n._nid) ) return; // Been there, done that visit.set(n._nid); Node m = map.get(n); - // The cloned Call should not clone any linked edges. - if( n instanceof CallEndNode cend && !cend._folding ) { - m.addDef( map.get(cend.call()) ); - } else { - for( Node e : n._inputs ) { - Node x = e; - if( e != null ) { - x = map.get(e); - if( x == null ) x = e; + for( Node e : n._inputs ) { + Node x = e; + if( e != null ) { + if( n instanceof CallEndNode cend && e != cend.call() && + (!(e instanceof ReturnNode ret) || map.get(ret.fun()) == null) ) + continue; + x = map.get(e); + if( x == null ) { + if( n instanceof CallEndNode cend && e != cend.call() ) + continue; + x = e; } - m.addDef(x); } + m.addDef(x); } for( Node x : n._outputs ) bodyEdge(visit,body,map,x); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java index f67f2b97..4ff2bd82 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -102,8 +102,7 @@ public class LoadNode extends MemOpNode { // baked into the type system. Loads into arrays DO need the ctrl // edge, at least until proper range-checking is in place. if( in(0)!=null && ptr()._type instanceof TypeMemPtr tmp && - // Never can be an array - (!tmp._obj._open || (tmp._obj._fields.length > 1 && tmp._obj._fields[0]._fname != "#")) ) { + !tmp._obj.isAry() ) { setDef(0,null); return this; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index a88748b5..e4e7d607 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -113,7 +113,8 @@ public class MemMergeNode extends Node { if( XInt.bit(mem._escAs,i) ) { Node n = in(i); if( n != null && !n._type.isHigh() ) { - TypeMem mem2 = (TypeMem)mem.meet(n._type); + TypeMem nmem2 = ((TypeMem)n._type).makeFrom(mem._escFs, mem._escAs); + TypeMem mem2 = (TypeMem)mem.meet(nmem2); // More escape aliases if( mem2 != mem ) { mem = mem2; progress = true; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index d824bc3a..59f7c304 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -43,15 +43,15 @@ public abstract class MemOpNode extends TypeNode { // Source location for late reported errors public final Parser.Lexer _loc; - public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type glb, Node ctrl, Node mem, Node ptr, Node off) { - super(glb, ctrl, mem, ptr, off); + public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off) { + super(decl, ctrl, mem, ptr, off); _name = name; _alias = alias; _loc = loc; _isLoad = isLoad; } - public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type glb, Node ctrl, Node mem, Node ptr, Node off, Node value) { - this(loc, name, alias, isLoad, glb, ctrl, mem, ptr, off); + public MemOpNode(Parser.Lexer loc, String name, int alias, boolean isLoad, Type decl, Node ctrl, Node mem, Node ptr, Node off, Node value) { + this(loc, name, alias, isLoad, decl, ctrl, mem, ptr, off); addDef(value); } public MemOpNode( Node ideal, MemOpNode mop ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 6488b827..51ea28b0 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -73,7 +73,9 @@ public class ParmNode extends PhiNode { @Override public Node idealize() { if( !(region() instanceof FunNode) ) - return in(1); // Input has collapse to e.g. starting control. + // A dead function can lose every caller before the Parm itself is + // removed; there is no replacement input in that transient form. + return nIns()==1 ? null : in(1); // Input has collapse to e.g. starting control. // If function is folding, do all possible peeps if( fun()._folding ) return super.idealize(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 2c57eb8b..2ae3c752 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -76,7 +76,7 @@ public class PhiNode extends Node { if( !(region() instanceof RegionNode r) ) return region()._type==Type.XCONTROL || region()._type==Type.TOP ? (_type instanceof TypeMem ? TypeMem.TOP : Type.TOP) : _type; // During parsing Phis have to be computed type pessimistically. - if( r.inProgress() ) + if( r.inProgress() || in(nIns()-1)==null ) return declaredType(); // Set type to local top of the starting type Type t = Type.TOP; @@ -219,7 +219,7 @@ public class PhiNode extends Node { if( in(i).in(j) != x ) { needsPhi=true; break; } if( needsPhi ) { - x = make(_label,op.in(j)._type.glb(false)); + x = make(_label,op.in(j)._type); x.addDef(region()); for( int i=1; i doubles as the public no-arg // constructor. Required fields remain TOP in its private memory: a // typed parser poison which deliberately emitted no Store or code. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 58508a1c..dd5fa541 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -240,20 +240,16 @@ public class ScopeNode extends MemMergeNode { return true; } - // Normal lookup was tried and failed. Insert a forward ref outside any - // enclosing Kind.Func scope, skipping any nested Blocks or Allocs and - // return the Var. May insert at the outermost scope, which means this - // must be defined externally, or it's an error. + // Normal lookup was tried and failed. Append a forward ref in the current + // lexical scope. Scope pops promote it outwards "as if" the final constant + // had been declared before the using scope. public Var defineFRef( String id, Type t, boolean xfinal, Parser.Lexer loc ) { - // Kind/Lexical scope index - int kidx = enclosingFunction(); - int idx = _kinds.at(kidx)._lexSize; - Var var = new Var(idx,id,t,xfinal,loc,true); + Var var = new Var(nIns(),id,t,xfinal,loc,true); FRefNode fref = new FRefNode(id,loc).init(); fref._type = fref._con = t; - // Insert in the lex scope just prior to kidx - insert(var,fref,kidx); + _vars.add(var); + addDef(fref); return var; } @@ -406,6 +402,18 @@ public class ScopeNode extends MemMergeNode { } } + public void balanceLoopFRefs( ScopeNode scope ) { + for( int i = nIns(); i < scope.nIns(); i++ ) { + Var n = scope.var(i); + if( n.isFRef() ) { // Loop body has forward refs + Var v = new Var(nIns(),n._name,n.type(),n._final,n._loc,true); + v._uninit = n._uninit; + _vars.add(v); + addDef(scope.in(i)); + } + } + } + // ------------------------------------------------ // peephole the backedge scope into this loop head scope @@ -426,8 +434,10 @@ public class ScopeNode extends MemMergeNode { for( int i=1; i= 4 + ? riscv.MEM_MASK // Word/dword value in GPR or FPR + : riscv.RMASK; // Byte/short stores require a GPR return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java index 24812fea..9d131fc6 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java @@ -38,7 +38,7 @@ public class CmpMemX86 extends MemOpX86 { case 0: enc.add1(_imm); break; case 1: enc.add2(_imm); break; case 2: enc.add4(_imm); break; - case 3: enc.add8(_imm); break; + case 3: enc.add4(_imm); break; } } else { encVal(enc, _con, ptr, idx, src, _off, _scale, _swap); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 6069c07b..bfaf7a91 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -67,7 +67,7 @@ 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 >= 2 + 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 return null; // Anti-dependence diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java index d9056be9..7db80299 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/NotX86.java @@ -17,23 +17,20 @@ public class NotX86 extends MachConcreteNode implements MachNode { short dst = enc.reg(this ); short src = enc.reg(in(1)); - // Pre-zero using XOR dst,dst; since zero'd will not have a - // byte-dependency from the setz. Can skip REX is dst is low 8, makes - // this a 32b xor, which will also zero the high bits. - if( dst >= 8 ) enc.add1(x86_64_v2.rex(dst, dst, 0)); - enc.add1(0x33); // opcode - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); - // test rdi,rdi enc.add1(x86_64_v2.rex(src, src, 0)); enc.add1(0x85); enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, src, src)); - // setz (sete dil) - enc.add1(x86_64_v2.rex(dst, 0, 0)); + // setz dstb; then zero-extend the low byte into the full register. + if( dst >= 4 ) enc.add1(x86_64_v2.rex(0, dst, 0, false)); enc.add1(0x0F); enc.add1(0x94); - enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, 0)); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, 0, dst)); + if( dst >= 4 ) enc.add1(x86_64_v2.rex(dst, dst, 0, false)); + enc.add1(0x0F); + enc.add1(0xB6); + enc.add1(x86_64_v2.modrm(x86_64_v2.MOD.DIRECT, dst, dst)); } @Override public void asm(CodeGen code, SB sb) { sb.p(code.reg(this)); } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index a1ad17dc..4cabefca 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -511,7 +511,8 @@ public class x86_64_v2 extends Machine { // Operands swap in the encoding directly, no need for Set/Jmp to swap `bop` if( rhs instanceof LoadNode ld && ld.nOuts() == 1 && lhs._type.isa(ld.declaredType()) && - (val!=null || bool.op()=="==" || bool.op()=="!=") ) + (!(lhs instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm32(ti.value())) || + bool.op()=="==" || bool.op()=="!=") ) return new CmpMemX86(bool, address(ld), ld.ptr(), idx, off, scale, imm(lhs), val, true ); // Vs immediate @@ -667,7 +668,7 @@ public class x86_64_v2 extends Machine { private int imm( Node xval ) { assert val == null && imm == 0; - if( xval instanceof ConstantNode con && con._con instanceof TypeInteger ti) { + if( xval instanceof ConstantNode con && con._con instanceof TypeInteger ti && ti.isConstant() && imm32(ti.value()) ) { val = null; imm = (int) ti.value(); assert imm == ti.value(); // In 32-bit range diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 206983a0..e15d7dbe 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -14,23 +14,26 @@ public abstract class ASMPrinter { public static SB print(SB sb, CodeGen code ) { Encoding enc = code._encoding; - if( enc == null ) return sb.p("No encoding for ").p(code._srcName); + Ary cfg = enc == null ? code._cfg : enc._cfg; + if( cfg == null || cfg._len == 0 ) return sb.p("No scheduled code for ").p(code._srcName); // instruction address int iadr = 0; // Print all functions in order - for( int i=0; i0 ) - iadr = printConstantPool(iadr, sb, enc._cpool,enc._bigCons,true ,"Constant Pool"); + if( enc != null ) { + iadr = (iadr+15)&-16; // pad to 16 + if( enc._cpool.size()>0 ) + iadr = printConstantPool(iadr, sb, enc._cpool,enc._bigCons,true ,"Constant Pool"); - iadr = (iadr+15)&-16; // pad to 16 - if( enc._sdata.size()>0 ) - iadr = printConstantPool(iadr, sb,enc._sdata,enc._bigCons,false, "Static Data" ); + iadr = (iadr+15)&-16; // pad to 16 + if( enc._sdata.size()>0 ) + iadr = printConstantPool(iadr, sb,enc._sdata,enc._bigCons,false, "Static Data" ); + } return sb; } @@ -90,7 +93,7 @@ public abstract class ASMPrinter { } - private static int print(int iadr, SB sb, CodeGen code, Encoding enc, FunNode fun, int cfgidx) { + private static int print(int iadr, SB sb, CodeGen code, Encoding enc, Ary cfg, FunNode fun, int cfgidx) { // Function header sb.nl().p("---"); if( fun._name != null ) sb.p(fun._name).p(" "); @@ -100,8 +103,8 @@ public abstract class ASMPrinter { if( fun._frameAdjust != 0 ) iadr = doInst(iadr,sb,code,enc, cfgidx,fun,true,enc!=null); - while( !(enc._cfg.at(cfgidx) instanceof ReturnNode) ) - iadr = doBlock(iadr,sb,code,enc,fun,cfgidx++); + while( !(cfg.at(cfgidx) instanceof ReturnNode) ) + iadr = doBlock(iadr,sb,code,enc,cfg,fun,cfgidx++); // Function separator sb.p("---"); @@ -112,9 +115,9 @@ public abstract class ASMPrinter { static private final int opWidth = 5; static private final int argWidth = 30; - static int doBlock(int iadr, SB sb, CodeGen code, Encoding enc, FunNode fun, int cfgidx) { + static int doBlock(int iadr, SB sb, CodeGen code, Encoding enc, Ary cfg, FunNode fun, int cfgidx) { final int encWidth = code._mach==null ? 2 : code._mach.defaultOpSize()*2; - CFGNode bb = enc._cfg.at(cfgidx); + CFGNode bb = cfg.at(cfgidx); if( bb != fun && !(bb instanceof IfNode) && !(bb instanceof CallEndNode) && !(bb instanceof CallNode) && !(bb instanceof CProjNode && bb.in(0) instanceof CallEndNode )) sb.p(label(bb)).p(":").nl(); if( bb instanceof CallNode ) return iadr; @@ -167,8 +170,9 @@ public abstract class ASMPrinter { // need to assume a jump. There's no real hardware op here, yet. if( n instanceof RegionNode cfg && !(n instanceof FunNode) ) { if( postEncode ) return iadr; // All jumps inserted already - while( cfgidx < enc._cfg._len-1 ) { - CFGNode next = enc._cfg.at(++cfgidx); + Ary blocks = enc == null ? code._cfg : enc._cfg; + while( cfgidx < blocks._len-1 ) { + CFGNode next = blocks.at(++cfgidx); if( next == n ) return iadr; // Fall-through, no branch if( next.nOuts()>1 ) break; // Has code in the block, need to jump around @@ -243,7 +247,7 @@ public abstract class ASMPrinter { sb.nl(); // Printing more op bits than fit - if( isMultiOp != null ) { + if( isMultiOp != null && enc != null ) { // Multiple ops, template style, no RA, no scheduling. Print out // one-line-per-newline, with encoding bits up front. int size = enc != null ? enc.opLen(n) : 0; @@ -267,6 +271,9 @@ public abstract class ASMPrinter { } + } else if( isMultiOp != null ) { + sb.p(isMultiOp).nl(); + } else if( fatEncoding > 0 ) { // Extra bytes past the default encoding width, all put on a line by // themselves. X86 special for super long encodings diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index 7c0f84f3..8b1c1e2f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/IRPrinter.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.print; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.codegen.Serialize; +import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.SB; @@ -37,30 +37,133 @@ public abstract class IRPrinter { // Bulk whole program pretty print public static String prettyPrint( CodeGen code ) { - // Loop-tree for nodeOrder - CFGNode.LoopTree old = code._start._ltree; - if( old==null ) - code._start.buildLoopTree( code._linker, code._stop); - Ary nodes = Serialize.nodeOrder(code); - if( old == null ) - code._start._ltree = null; SB sb = new SB(); - Node prior=null; - for( Node n : nodes ) { - if( n instanceof FunNode fun ) { - sb.nl().p("--- "); - fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" ")); - sb.p("----------------------\n"); - } - if( n instanceof MultiNode || n instanceof RegionNode || n instanceof CallNode || + printLine(code._start,sb); + + // Constants are shared program-wide. Print only actual Start children + // here; derived values belong to the functions which use them. + ArrayList globals = new ArrayList<>(); + for( Node n : code._start._outputs ) + if( n instanceof ConstantNode ) globals.add(n); + globals.sort(Comparator.comparingInt(n -> n._nid)); + for( Node n : globals ) printLine(n,sb); + + ArrayList cus = new ArrayList<>(code._compunits.values()); + cus.sort(Comparator.comparing(cu -> cu._cname==null ? "" : cu._cname)); + for( CompUnit cu : cus ) { + if( cu._start==null || cu._start._inputs==null ) continue; + sb.nl().p("=== ").p(cu._cname==null ? "" : cu._cname).p(" ===\n"); + printLine(cu._start,sb); + ArrayList projs = projections(cu._start); + for( Node proj : projs ) printLine(proj,sb); + + ArrayList funs = new ArrayList<>(); + for( FunNode fun : code._linker ) + if( fun!=null && fun._inputs!=null && fun._compunit==cu ) + funs.add(fun); + funs.sort(Comparator.comparingInt(n -> n._nid)); + for( FunNode fun : funs ) printFunction(fun,sb); + + printLine(cu._stop,sb); + } + printLine(code._stop,sb); + return sb.toString(); + } + + /** Print one function without ever traversing a call-graph linkage. */ + private static void printFunction(FunNode fun, SB sb) { + sb.nl().p("--- "); + fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" ")); + sb.p("----------------------\n"); + + ArrayList post = new ArrayList<>(); + IdentityHashMap visit = new IdentityHashMap<>(); + functionPost(fun,fun,visit,post); + Collections.reverse(post); + + Node prior = null; + IdentityHashMap emitted = new IdentityHashMap<>(); + for( Node n : post ) { + if( emitted.containsKey(n) ) continue; + if( n instanceof RegionNode || n instanceof MultiNode || n instanceof CallNode || (isMultiChild(prior) && !isMultiChild(n)) ) sb.nl(); + // A Region/Loop and its Phis are one block header. In particular, + // do not pull loop-carried Phi inputs up between the header and + // the Phi; those values belong down in the loop body/backedge. + if( !isMultiChild(n) ) + emitLocalDefs(n,visit,emitted,sb); printLine(n,sb); - if( n instanceof ReturnNode ret ) - sb.p("--- ").p(ret._fun._name==null ? "" : ret._fun._name).p(" ----------------------\n"); + emitted.put(n,Boolean.TRUE); prior = n; } - return sb.toString(); + sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" ----------------------\n"); + } + + private static void emitLocalDefs(Node n, + IdentityHashMap owned, + IdentityHashMap emitted, + SB sb) { + if( n._inputs==null ) return; + for( Node def : n._inputs ) { + if( def==null || def instanceof CFGNode || def instanceof ConstantNode || + def instanceof PhiNode || isMultiChild(def) || + !owned.containsKey(def) || emitted.containsKey(def) ) + continue; + emitLocalDefs(def,owned,emitted,sb); + printLine(def,sb); + emitted.put(def,Boolean.TRUE); + } + } + + // Printer-private RPO. This deliberately uses raw edge arrays and local + // identity state: no Node visit bits, cached idoms, or loop-tree metadata. + private static void functionPost(Node n, FunNode owner, + IdentityHashMap visit, + ArrayList post) { + if( n==null || n._inputs==null || visit.put(n,Boolean.TRUE)!=null ) return; + if( n instanceof FunNode fun && fun!=owner ) return; // Linked callee + if( n instanceof ParmNode && + input0(n)!=owner ) return; // Callee parameter + if( n instanceof StopCUNode || n instanceof StopNode || n instanceof StartCUNode ) return; + if( n instanceof CallEndNode && input0(n) instanceof CallNode call && + !visit.containsKey(call) ) return; // Foreign caller + + ArrayList uses = new ArrayList<>(); + // A Return is terminal inside its function. All of its graph users + // are ownership/linkage hooks (StopCU, CallEnds, FunPtrs), never CFG + // continuation in the function being printed. + if( !(n instanceof ReturnNode) ) for( Node use : n._outputs ) { + if( use==null || use._inputs==null ) continue; + if( n instanceof CallNode && use instanceof FunNode ) continue; + if( use instanceof FunNode fun && fun!=owner ) continue; + if( use instanceof ParmNode && + input0(use)!=owner ) continue; + uses.add(use); + } + // CFG first produces an RPO-like block order. Stable nid ordering + // keeps malformed/multiply-connected graphs deterministic. + uses.sort(Comparator + .comparingInt((Node use) -> use instanceof CFGNode ? 0 : 1) + .thenComparingInt(use -> use._nid)); + for( Node use : uses ) functionPost(use,owner,visit,post); + + // Keep a multi-head and its projections contiguous. + if( isMultiChild(n) ) return; + if( isMultiHead(n) ) { + ArrayList ps = projections(n); + for( Node p : ps ) visit.put(p,Boolean.TRUE); + for( int i=ps.size()-1; i>=0; i-- ) post.add(ps.get(i)); + } + post.add(n); + } + + private static ArrayList projections(Node multi) { + ArrayList ps = new ArrayList<>(); + for( Node use : multi._outputs ) + if( use!=null && use._inputs!=null && isMultiChild(use) ) ps.add(use); + ps.sort(Comparator.comparingInt(IRPrinter::sortOrder)); + return ps; } private static boolean isMultiHead(Node n) { @@ -68,7 +171,19 @@ public abstract class IRPrinter { } private static boolean isMultiChild(Node n) { - return n!=null && n.nIns() > 0 && n.in(0) != null && isMultiHead(n.in(0)); + Node head = input0(n); + // Regions group their Phis, and tuple-producing MultiNodes group their + // projections. Merely being controlled by a Region/Loop does not + // make an ordinary CFG node a grouped child. + return (n instanceof PhiNode && head instanceof RegionNode) || + (n instanceof Proj && head instanceof MultiNode); + } + + // Raw, bounds-safe graph inspection for the debugger. In particular do + // not call an accessor which might assert, sharpen, cache, or lazily kill. + private static Node input0(Node n) { + return n==null || n._inputs==null || n._inputs.isEmpty() + ? null : n._inputs.at(0); } @@ -163,7 +278,7 @@ public abstract class IRPrinter { } static int sortOrder( Node n ) { - if( n instanceof ProjNode proj ) return proj._idx; + if( n instanceof Proj proj ) return proj.idx(); if( n instanceof PhiNode phi ) return phi._nid; if( n == null ) return 0; return n._nid+1000000; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java index b6ea5843..ed505b19 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/Field.java @@ -98,8 +98,6 @@ public class Field extends Type { @Override boolean _isConstant() { return _t._isConstant(); } @Override boolean _isFinal() { return _final && _t._isFinal(); } @Override Field _makeRO() { return _final ? this : make(_fname, _t._makeRO(),_alias,true); } - @Override boolean _isGLB(boolean mem) { return _t._isGLB(true); } - @Override public Type _glb(boolean mem) { return make(_fname,_t._glb(true),_alias,true); } @Override Field _close( String name, HashMap TYPES ) { return makeFrom( _t._close(name, TYPES )); } @Override Type _upgradeType(HashMap TYPES) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java index fd3a7c59..509326bb 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/Type.java @@ -480,28 +480,11 @@ public class Type /*implements Cloneable*/ { } Type _makeRO() { return this; } - // Compute greatest lower bound in the lattice. If values are in memory, - // ints and floats cannot widen. - public final boolean isGLB(boolean mem) { return recurClose(recurOpen()._isGLB(mem)); }; - boolean _isGLB(boolean mem) { - return switch(_type) { - case TBOT -> false; - case TSCALAR -> this==TypeScalar.BOT; - case TNIL -> false; - case TCTRL -> true; - case TXCTRL -> false; - case TXNIL -> false; - case TTOP -> false; - default -> throw Utils.TODO(); - }; - } - public final Type glb(boolean mem) { - if( isGLB(mem) ) return this; - Type glb = recurOpen()._glb(mem).recurClose(); - assert this.isa(glb); - return glb; + /** Declared shape used when a value is published into mutable memory. */ + public final Type makeStorage() { + return recurOpen()._makeStorage().recurClose(); } - Type _glb(boolean mem) { assert is_simple(); return Type.BOTTOM; } + Type _makeStorage() { assert is_simple(); return BOTTOM; } // Bulk close-over all recursive types public static TypeStruct[] closeOver(TypeStruct[] ts, HashMap TYPES) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index 26fa4a67..2a0a817e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -48,8 +48,7 @@ public abstract class TypeConAry extends TypeScalar { @Override public boolean isHigh() { return this==TOP; } @Override boolean _isConstant() { return true; } - @Override Type _glb(boolean mem) { return this; } - @Override boolean _isGLB(boolean mem) { return true; } + @Override Type _makeStorage() { return this; } // Meet-over-elements type public Type elem() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index f4968f28..1325b707 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -90,15 +90,13 @@ public class TypeFloat extends TypeScalar { return _isConstant() ? this : new TypeFloat((byte)-_sz,0); // Constants are a self-dual } - @Override boolean _isGLB(boolean mem) { return _glb(mem)==this; } - @Override Type _glb(boolean mem) { - if( !mem ) return F64; + @Override boolean _isConstant() { return _sz==0; } + + @Override Type _makeStorage() { if( _isConstant() ) return isF32() ? F32 : F64; return isHigh() ? dual() : this; } - @Override boolean _isConstant() { return _sz==0; } - @Override public Type makeZero() { return FZERO; } // Reserve tags for F64,F32,constant diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index e2ec6263..d18ebd9c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -68,7 +68,7 @@ public class TypeFunPtr extends TypeNil { @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } - public TypeFunPtr makeFrom( int fidx ) { return make1((byte)2,_open,_sig,_ret,fidx); } + public TypeFunPtr makeFrom( int fidx ) { return make1(_nil,_open,_sig,_ret,fidx); } public TypeFunPtr makeFrom( Type arg, int idx ) { // Alter named arg Type[] sig = _sig.clone(); @@ -159,8 +159,7 @@ public class TypeFunPtr extends TypeNil { @Override boolean _isConstant() { return (_nil==2 && XInt.isConstant(_fidxs)) || (_nil==3 && _fidxs== XInt.EMPTY); } @Override boolean _isFinal() { return true; } - @Override boolean _isGLB(boolean mem) { return true; } - @Override TypeFunPtr _glb(boolean mem) { return this; } + @Override TypeFunPtr _makeStorage() { return this; } @Override TypeFunPtr _close( String name, HashMap TYPES ) { Type[] sig = new Type[_sig.length]; @@ -213,7 +212,7 @@ public class TypeFunPtr extends TypeNil { @Override int TAGOFF() { return 8; } @Override public void packed( BAOS baos, HashMap strs ) { assert _open; // Open: Passing extra args is fine, and extras ignored. - if( _nil==2 && nargs()<6 && nfcns() == 1 ) { + if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx() < 64 ) { baos.write(TAGOFFS[_type] + nargs()); baos.packed2(fidx()); } else { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 25c3fa6f..c981f3d3 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -170,14 +170,10 @@ public class TypeInteger extends TypeScalar { } @Override public Type makeZero() { return ZERO; } @Override boolean _isConstant() { return _min == _max; } - @Override boolean _isGLB(boolean mem) { return _glb(mem)==this; } - @Override Type _glb(boolean mem) { - if( !mem ) return BOT; - // GLB is not well-defined in memory; depends on the size of the memory field + @Override Type _makeStorage() { if( _isConstant() ) return BOT; return isHigh() ? dual() : this; } - // Reserve tags for I64,I32,U32,0,constant,generic @Override int TAGOFF() { return 7; } @Override public void packed( BAOS baos, HashMap strs ) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 3bbdf1df..7658e3fd 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -123,10 +123,10 @@ public class TypeMem extends Type { int[] fidxs = XInt.meet( _escFs, that._escFs ); int[] aliases= XInt.meet( _escAs, that._escAs ); // Singleton & class facts are kept only when both sides agree. - + // Final is kept if either side is final, merging a final & non-final // memory can be argued either way here: - + // - Keep it: merging a final & non-final memory means a later Store // update will be flagged as an error. // - Lose it: merging a final & non-final memory means a later Load @@ -152,8 +152,7 @@ public class TypeMem extends Type { @Override boolean _isConstant() { return _one && _clz && _alias!= 1 && _t._isConstant(); } @Override public int log_size() { throw Utils.TODO(); } @Override boolean _isFinal() { return _t._isFinal(); } - @Override boolean _isGLB(boolean mem) { return _t._isGLB(true); } - @Override public Type _glb(boolean mem) { return make(_alias,_t._glb(true),_one,_clz,_final,_escFs,_escAs); } + @Override TypeMem _makeStorage() { return make(_alias,_t._makeStorage(),_one,_clz,_final,_escFs,_escAs); } @Override TypeMem _close( String name, HashMap TYPES ) { return malloc(_alias,_t._close(name, TYPES ),_one,_clz,_final,_escFs,_escAs); } @@ -230,7 +229,7 @@ public class TypeMem extends Type { private static int[] escapeFIDX( int[] xs, Type t ) { return switch(t) { case TypeMemPtr tmp -> escapeFIDX(xs,tmp._obj); - case TypeStruct ts -> ts._open + case TypeStruct ts -> ts._open && !ts.isAry() ? XInt.FULL // Open structs can have any fields : XInt.meet(xs,ts.fidxs()); case TypeFunPtr tfp -> XInt.meet(xs,tfp.fidxs()); @@ -242,7 +241,7 @@ public class TypeMem extends Type { private static int[] escapeAlias( int[] xs, Type t ) { return switch(t) { case TypeMemPtr tmp -> escapeAlias(xs,tmp._obj); - case TypeStruct ts -> ts._open + case TypeStruct ts -> ts._open && !ts.isAry() ? XInt.FULL // Open structs can have any fields : XInt.meet(xs,ts.aliases()); case TypeMem mem -> XInt.meet(xs,mem._escAs); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 67d80591..5a2693c9 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -68,6 +68,10 @@ public class TypeMemPtr extends TypeNil { public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(_nil, obj, _one, _pub); } public TypeMemPtr makeNullable() { return makeFrom((byte)3); } + /** Inferred mutable local: nullable, public and non-singleton. */ + public TypeMemPtr makeVar() { return (TypeMemPtr)makeStorage(); } + /** Public-memory shape: nullable and non-singleton, preserving the referent. */ + @Override TypeMemPtr _makeStorage() { return make((byte)3,_obj._makeStorage(),false,true); } @Override TypeMemPtr makeFrom(byte nil) { return nil==_nil ? this : make(nil, _obj, _one, _pub); } public TypeMemPtr makeHigh(byte nil) { return make(nil,_obj.makeHigh(),false); } @Override public Type nonZero() { return makeFrom((byte)(_nil <= 1 ? 1 : 2)); } @@ -109,8 +113,6 @@ public class TypeMemPtr extends TypeNil { @Override boolean _isConstant() { return _one; } @Override boolean _isFinal() { return _obj._isFinal(); } @Override TypeMemPtr _makeRO() { return makeFrom(_obj._makeRO()); } - @Override boolean _isGLB(boolean mem) { return _obj._isGLB(true); } - @Override TypeMemPtr _glb(boolean mem) { return make((byte)3,_obj.glb2()); } @Override TypeMemPtr _close( String name, HashMap TYPES ) { return malloc(_nil,_obj._close(name, TYPES ),_one,_pub); } @Override Type _upgradeType(HashMap TYPES) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java index 32505aa2..2c1c1d76 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeNil.java @@ -51,7 +51,6 @@ public abstract class TypeNil extends TypeScalar { public boolean nullable() { return _nil==3; } @Override boolean _isConstant() { return false; } - @Override Type _glb(boolean mem) { return Type.NIL; } final String q() { return _nil == 1 || _nil == 2 ? "" : "?"; } final String x() { return isHigh() ? "~" : ""; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java index 3ff9765b..7b27ff2b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypePtr.java @@ -50,8 +50,8 @@ public class TypePtr extends TypeNil { // 0->xscalar, 1->nscalar, 2->nscalar, 3->scalar @Override Type meetX() { return _nil==0 ? XNIL : (_nil==3 ? PTR : NPTR); } - boolean _isGLB(boolean mem) { return this==PTR; } - @Override TypePtr _glb(boolean mem) { return PTR; } + @Override TypePtr _makeStorage() { return PTR; } + // Reserve 2 tags, PTR and NPTR @Override int TAGOFF() { return 2; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java index a39ebc04..8a12f50a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -73,7 +73,7 @@ public class TypeRPC extends Type { } @Override boolean _isConstant() { return XInt.isConstant(_rpcs); } - @Override boolean _isGLB(boolean mem) { return true; } + @Override TypeRPC _makeStorage() { return this; } // Reserve tags for ALL, singleton, generic @Override int TAGOFF() { return 3; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java index 7b5d6317..eaba0a1c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeScalar.java @@ -38,8 +38,7 @@ public class TypeScalar extends Type { @Override TypeScalar xdual() { return new TypeScalar(); } @Override public boolean isHigh() { return this == TOP; } - @Override boolean _isGLB(boolean mem) { return this == BOT; } - @Override Type _glb(boolean mem) { return BOT; } + @Override Type _makeStorage() { return BOT; } // Reserve tags for both lattice endpoints. Unlike most concrete scalar // families, generic scalar TOP can survive into a serialized graph. diff --git a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index f51ab859..2949b015 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -463,18 +463,8 @@ public class TypeStruct extends Type { return recurTransform(_name,_name,_open,_fref,true,Type::_makeRO); } - // Keeps the same struct, but lower-bounds all fields. - public TypeStruct glb2() { - return recurTransform(_uid,_name,_open,false,false,t -> t._glb(true)); - } - - @Override boolean _isGLB(boolean mem) { - if( VISIT.containsKey(_uid) ) return true; // Cycles assume GLB - VISIT.put(_uid,this); - for( Field f : _fields ) - if( !f._t._isGLB(mem) ) - return false; - return true; + @Override TypeStruct _makeStorage() { + return recurTransform(_uid,_name,_open,false,false,Type::_makeStorage); } // log_size for a struct is not defined, unless its exactly some power of @@ -569,7 +559,12 @@ public class TypeStruct extends Type { if( isAry() && field("[]")._t instanceof TypeConAry con ) return sb.p(con.str()); sb.p(_name); - if( html || isAry() ) + if( isAry() ) + // Array names deliberately canonicalize mutable and immutable + // element variants. The verbose debugger print must retain the + // otherwise invisible lattice coordinate. + return sb.p(_fields[1]._final ? "[final]" : "[mutable]"); + if( html ) return sb; sb.p(" {"); for( Field f : _fields ) diff --git a/chapter25/src/main/smp/sys.smp b/chapter25/src/main/smp/sys.smp index 815212ab..8aef5b68 100644 --- a/chapter25/src/main/smp/sys.smp +++ b/chapter25/src/main/smp/sys.smp @@ -2,8 +2,11 @@ // top-level default standard library import -var libc = libc; -var io = io; -var aryu8 = aryu8; -var Scan = Scan; -var aryi64 = aryi64; +val adt = adt; // Abstract Data Types +val ary = ary; // Array utilities +val aryi64 = aryi64; // Variable sized array of i64 +val aryu8 = aryu8; // Variable sized array of u8 +val char = char; // Character utilities +val io = io; // IO library +val libc = libc; // libc FFI bindings +val scan = scan; // A simple string parser diff --git a/chapter25/src/main/smp/sys/Ary.smp b/chapter25/src/main/smp/sys/Ary.smp deleted file mode 100644 index 0f667695..00000000 --- a/chapter25/src/main/smp/sys/Ary.smp +++ /dev/null @@ -1,10 +0,0 @@ -// -*- mode: java; -*- - -// Array utilities - -// Copy byte array contents -val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> - for( int i=0; i - buf = b; - }; - - // Skip whitespace - val skip = { -> - while( x < buf# && buf[x] <= ' ' ) - x++; - return self; - }; - - // True if find required character, and skip it; else False. - val match = { u8 c -> - skip(); - if( x >= buf# ) return false; - if( buf[x] != c ) return false; - x++; - return true; - }; - - // Parse a simple number - val number = { -> - skip(); - bool neg = match('-'); - if( x >= buf# || buf[x] < '0' || '9' < buf[x] ) { - bad = true; - return 0; - } - i64 n = 0; - while( x < buf# && '0' <= buf[x] & buf[x] <= '9' ) - n = n*10 + (buf[x++] - '0'); - return neg ? -n : n; - }; -}; diff --git a/chapter25/src/main/smp/sys/adt.smp b/chapter25/src/main/smp/sys/adt.smp new file mode 100644 index 00000000..efdad395 --- /dev/null +++ b/chapter25/src/main/smp/sys/adt.smp @@ -0,0 +1,4 @@ +// -*- mode: java; -*- + +// Abstract data types. +val bitset = bitset; diff --git a/chapter25/src/main/smp/sys/adt/bitset.smp b/chapter25/src/main/smp/sys/adt/bitset.smp new file mode 100644 index 00000000..f56f1cce --- /dev/null +++ b/chapter25/src/main/smp/sys/adt/bitset.smp @@ -0,0 +1,58 @@ +// -*- mode: java; -*- + +// A set of non-negative integers, represented one bit per value. +struct bitset { + i64[] !_bits; + + new bitset = { -> + _bits = new i64[1]; + }; + + // Return 0 for missing, non-zero for true + val get = { int bit -> + if( (bit >> 6) >= _bits# ) return false; + i64 mask = 1 << (bit & 63); + return (_bits[bit >> 6] & mask); + }; + + val _grow = { int bit -> + int x = bit >> 6; + int len = _bits#; + if( x < len ) return self; + while( x >= len ) len *= 2; + var bits = new i64[len]; + for( int i=0; i<_bits#; i++ ) + bits[i] = _bits[i]; + _bits = bits; + return self; + }; + + // Set + val set = { int bit -> + i64 mask = 1 << (bit & 63); + _grow(bit)._bits[bit >> 6] |= mask; + return self; + }; + + // Test and set + val tset = { int bit -> + int idx = bit >> 6; + i64 mask = 1 << (bit & 63); + if( _grow(bit)._bits[idx] & mask ) + return true; // Already set + _bits[idx] |= mask; + return false; // Was false (and now set) + }; + + val clr = { int bit -> + if( (bit >> 6) >= _bits# ) return self; + i64 mask = 1 << (bit & 63); + _bits[bit >> 6] &= (mask ^ -1); + return self; + }; + + val clear = { -> + for( int i=0; i<_bits#; i++ ) _bits[i] = 0; + return self; + }; +}; diff --git a/chapter25/src/main/smp/sys/ary.smp b/chapter25/src/main/smp/sys/ary.smp new file mode 100644 index 00000000..feade0f5 --- /dev/null +++ b/chapter25/src/main/smp/sys/ary.smp @@ -0,0 +1,25 @@ +// -*- mode: java; -*- + +// Array utilities + +// Copy byte array contents. Copies the shorter of the buffers and len +val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> + if( len > dst# - doff ) len = dst# - doff; + if( len > src# - soff ) len = src# - soff; + for( int i=0; i0 for first non-matching byte. Returns <0 or >0 for +// the larger array after that, or 0 if both arrays are fully equal. +val cmp = { u8[~] src1, u32 off1, u8[~] src2, u32 off2, u32 len -> + u32 len1 = len > src1# - off1 ? src1# - off1 : len; + u32 len2 = len > src2# - off2 ? src2# - off2 : len; + u32 max = len1 > len2 ? len2 : len1; + for( int i=0; i return buf[index]; }; + + // Write the bracketed array-list form to aryu8. val str = { -> // TODO: clunky default constructor syntax - var str = new aryu8(new u8[1]).add('['); - for( int i=0; i - var str = new aryu8(new u8[1]); + var str = new aryu8().add('['); for( int i=0; i @@ -53,12 +48,13 @@ struct aryi64 { }; + // Parse a comma-separated list of numbers, wrapped with square brackets, // with optional whitespace e.g. "[ -17, 0,99,12456789 ] ". // parseAryI64 & aryi64.str are bijections modulo whitespace. // Returns null if the parse failed, without giving a clue as to why. val parseAryI64 = { u8[~] str -> - Scan !s = new Scan(str); + scan !s = new scan(str); if( !s.match('[') ) return null; // Array of parsed results var nums = new aryi64(new i64[1]); @@ -79,3 +75,9 @@ val parseAryI64 = { u8[~] str -> s.skip(); return s.x == s.buf# ? nums : null; }; + +val copy = { i64[] dst, int doff, i64[~] src, int soff, int len -> + for( int i=0; i - buf = b; - }; + new aryu8 = { -> buf = new u8[1]; }; // Grow as needed val _grow = { int len2 -> @@ -15,7 +13,7 @@ struct aryu8 { int newlen = buf# * 2; while( len+len2 >= newlen ) newlen *= 2; u8[] !buf2 = new u8[newlen]; - Ary.copy(buf2,0,buf,0,buf#); + ary.copy(buf2,0,buf,0,buf#); buf = buf2; self; }; @@ -29,10 +27,10 @@ struct aryu8 { }; // Add all of a plain array to the aryu8 - val addAry = { u8[~] ary -> - _grow(ary#); - Ary.copy(buf,len,ary,0,ary#); - len += ary#; + val addAry = { u8[~] xs -> + _grow(xs#); + ary.copy(buf,len,xs,0,xs#); + len += xs#; self; }; @@ -64,3 +62,27 @@ struct aryu8 { libc.write(fd,ptr,len); }; }; + + +// Parse one integer, ignore trailing data; returns 0 with an empty string. +// If you want a more robust parsing, use the `scan` class +val atoi = { u8[~] str -> + int x = 0; + while( x < str# && str[x] <= ' ' ) x++; + if( x == str# ) return 0; + bool neg = false; + if( str[x]=='-' ) { neg=true; x++; } + i64 n = 0; + while( x < str# && '0' <= str[x] <= '9' ) + n = n*10 + str[x++]-'0'; + return neg ? -n : n; +}; + +// Zero-terminate string for libc strings. No error checking, just copies and +// appends a zero. +{ u8[~] -> u8[] } str0 = { u8[~] str -> + u8[] !strz = new u8[str#+1]; + ary.copy(strz,0,str,0,str#); + strz[str#] = '\0'; + strz; +}; diff --git a/chapter25/src/main/smp/sys/char.smp b/chapter25/src/main/smp/sys/char.smp new file mode 100644 index 00000000..de37968e --- /dev/null +++ b/chapter25/src/main/smp/sys/char.smp @@ -0,0 +1,9 @@ +// -*- mode: java; -*- + +val toupper = { u8 c -> + return c >= 'a' && c <= 'z' ? c - ('a' - 'A') : c; +}; + +val tolower = { u8 c -> + return c >= 'A' && c <= 'Z' ? c + ('a' - 'A') : c; +}; diff --git a/chapter25/src/main/smp/sys/io.smp b/chapter25/src/main/smp/sys/io.smp index b94e89fa..3d6be512 100644 --- a/chapter25/src/main/smp/sys/io.smp +++ b/chapter25/src/main/smp/sys/io.smp @@ -3,30 +3,63 @@ // Simple I/O Library // Write byte array to stdout -val p = { u8[~] str -> - i64 ptr = str; // cast array base to i64 - return libc.write(1,ptr,str#); -}; - -val p_noInline = { u8[~] str -> - i64 ptr = str; // cast array base to i64 - return libc.write(1,ptr,str#); -}; +val p = { u8[~] str -> write(1,str); }; +val p_noInline = { u8[~] str -> write(1,str); }; -// Return stdin as a u8[]. -val stdin = { -> +// Return fd contents as a u8[]. +val read = { i32 fd -> var buf = new u8[8*1024]; i64 ptr = buf; int len = 0; while( true ) { - int rez = libc.read(0,ptr,buf#); - if( rez < 0 ) libc._exit(libc.errno); + i32 rez = libc.read(fd,ptr,buf#); + if( rez > buf# ) libc._exit(libc.errno); len += rez; if( rez < buf# ) break; libc._exit(-2); // Need to implement for more than 8K input } - // Compress - var dst = new u8[len]; - return Ary.copy(dst,0,buf,0,len); + var out = new u8[len]; + ary.copy(out,0,buf,0,len); +}; + +// Write all of str to fd. +val write = { i32 fd, u8[~] str -> + i64 ptr = str; // Convert array pointer to a i64 for the native call + libc.write(fd,ptr,str#); +}; + +// Write all of str to fd. +val writeOff = { i32 fd, u8[~] str, u32 off, u32 len -> + i64 ptr = str; // Convert array pointer to a i64 for the native call + ptr += off; // Skip offset + // Cap at available length + if( len > str# - off ) len = str# - off; + // Do the write + libc.write(fd,ptr,len); +}; + +// Return stdin as a u8[]. +val stdin = { -> read(0); }; + +// Create file for writing. Return fd, or -1 and errno has the error code +val create = { u8[~] str -> + i64 ptr = sys.aryu8.str0(str); + i32 perms = 6*64 + 6*8 + 6; // 0666 + return libc.creat(ptr, perms); +}; + +// Open file for reading. Return fd, or -1 and errno has the error code +val open = { u8[~] str -> + i64 ptr = sys.aryu8.str0(str); + return libc.open(ptr, sys.libc.O_RDONLY, 0); +}; + +// Close an open fd. Return 0, or -1 and errno has the error code +val close = { i32 fd -> return libc.close(fd); }; + +// Remove a file. Return 0, or -1 and errno has the error code +val remove = { u8[~] str -> + i64 ptr = sys.aryu8.str0(str); + return libc.unlink(ptr); }; diff --git a/chapter25/src/main/smp/sys/libc.smp b/chapter25/src/main/smp/sys/libc.smp index 42fc7313..6d750f7b 100644 --- a/chapter25/src/main/smp/sys/libc.smp +++ b/chapter25/src/main/smp/sys/libc.smp @@ -3,12 +3,36 @@ // libc bindings: // https://www.man7.org/linux/man-pages/man2/.2.html +// The buffers are int-versions of zero-terminated strings. +// int buf = aryu8.str0("some_file"); +// buf mode perm-> fd +{ i64 i32 i32 -> i32 } open = "C"; +// buf perm -> fd +{ i64 i32 -> i32 } creat = "C"; + // fd buf len -> len -{ i32 i64 u32 -> u32 } write = "C"; +{ i32 i64 u32 -> i32 } write = "C"; // fd buf len -> len -{ i32 i64 u32 -> u32 } read = "C"; +{ i32 i64 u32 -> i32 } read = "C"; +// fd -> err +{ i32 -> i32 } close = "C"; +// path -> err +{ i64 -> i32 } unlink = "C"; + +i32 O_RDONLY = 0; +i32 O_WRONLY = 1; +i32 O_RDWR = 2; +i32 O_CREAT = 512; // 02000 on x86_64-pc-cygwin +i32 O_TRUNC = 1024; // 04000 on x86_64-pc-cygwin + +i32 STDIN = 0; +i32 STDOUT = 1; +i32 STDERR = 2; + // status { i32 -> i32 } _exit = "C"; +// Error return from many native calls +i32 errno = "C"; // addr len prot flags fd off -> void* { i64 i64 i32 i32 i32 i32 -> i64 } mmap = "C"; // mmap flags diff --git a/chapter25/src/main/smp/sys/scan.smp b/chapter25/src/main/smp/sys/scan.smp new file mode 100644 index 00000000..ba91003e --- /dev/null +++ b/chapter25/src/main/smp/sys/scan.smp @@ -0,0 +1,40 @@ +// -*- mode: java; -*- + +// Scanner; a simple string parser. +struct scan { + int !x; // Cursor + bool !bad; // True after a malformed token + u8[~] buf; // Buffer to parse + + new scan = { u8[~] b -> buf = b; }; + + // Skip whitespace + val skip = { -> + while( x < buf# && buf[x] <= ' ' ) + x++; + return self; + }; + + // True if find required character, and skip it; else False. + val match = { u8 c -> + skip(); + if( x >= buf# ) return false; + if( buf[x] != c ) return false; + x++; + return true; + }; + + // Parse a simple number + val number = { -> + skip(); + bool neg = match('-'); + if( x >= buf# || buf[x] < '0' || '9' < buf[x] ) { + bad = true; + return 0; + } + i64 n = 0; + while( x < buf# && '0' <= buf[x] & buf[x] <= '9' ) + n = n*10 + (buf[x++] - '0'); + return neg ? -n : n; + }; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter25/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 0ebee2c4..a42ebc24 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -61,7 +61,7 @@ val brain_fuck = { -> """; TestC.runC(src,"brain_fuck", brain_fuck, 40); - EvalRisc5 R5 = TestRisc5.build( src, "brain_fuck", 0, 28, false); + EvalRisc5 R5 = TestRisc5.build( src, "brain_fuck", 0, 25, false); int trap = R5.step(100000); assertEquals(0,trap); int ptr = (int)R5.regs[com.seaofnodes.simple.node.cpus.riscv.riscv.A0]; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6b237b18..0d40d871 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -65,7 +65,7 @@ else return v; """); code.parse().opto(); - assertEquals("Stop[ return Test.Vector2D; return MEM[ 2:.x=0; 3:.y=0;]; ]", code.print()); + assertEquals("Stop[ return Test.Vector2D; return MEM[ 2:.x=0; 3:.y=0;]; return Test.Vector2D; ]", code.print()); } @Test @@ -103,7 +103,7 @@ while (arg) { return bar.a; """); code.parse().opto(); - assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MEM[ 2:.a=0;]; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi_a+2)); return MEM[ 2:.a=0;]; return Test.Bar; ]", code.print()); } @Test @@ -225,7 +225,7 @@ while( i.x < i.len ) { return sum; """); code.parse().opto(); - assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MEM[ 2:.x=0; 3:.len=0;]; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum)); return MEM[ 2:.x=0; 3:.len=0;]; return Test.Iter; ]", code.print()); } @@ -244,7 +244,7 @@ while(arg) { return ret; """); code.parse().opto(); - assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MEM[ 2:.v0=0;]; ]", code.print()); + assertEquals("Stop[ return Phi(Loop,Test.s0,Phi(Region,Test.s0,Phi_ret)); return MEM[ 2:.v0=0;]; return Test.s0; ]", code.print()); } @Test @@ -297,7 +297,7 @@ s0 b = new s0(); return a.x * 100 + b.x * 10 + cnt; """); code.parse().iter().opto(); - assertEquals("Stop[ return 112; return MEM[ 2:___ 3:.x=1;]; ]", code.print()); + assertEquals("Stop[ return 112; return MEM[ 2:___ 3:.x=1;]; return Test.s0; ]", code.print()); } @@ -340,7 +340,7 @@ else return new s0; if(new s0.f0) return 0; """); code.parse().iter().opto().typeCheck(); - assertEquals("Stop[ return Test.s0; return MEM[ 2:.f0=0;]; ]", code.print()); + assertEquals("Stop[ return Test.s0; return MEM[ 2:.f0=0;]; return Test.s0; ]", code.print()); } @Test @@ -368,7 +368,7 @@ s0 v1 = v0; return v1; """); code.parse().opto(); - assertEquals("Stop[ return (const)Test.s0; return MEM[ 2:.f0=0;]; ]", code.print()); + assertEquals("Stop[ return (const)Test.s0; return MEM[ 2:.f0=0;]; return Test.s0; ]", code.print()); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 8bbcf21c..fedd59ce 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -99,7 +99,7 @@ N n = new N(new M); return n.next; """); code.parse().opto(); - assertEquals("Stop[ return (const)Test.M; return MEM[ 2:.m=0;]; return MEM[ 2:___ 3:___ 4:___ 5:.next=Parm_m(Test.N.N,*Test.M {i64 !m; }); 6:.i=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:.i=0;]; ]", code.print()); + assertEquals("Stop[ return (const)Test.M; return MEM[ 2:.m=0;]; return Test.M; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:.next=Parm_m(Test.N.N,*Test.M {i64 !m; }); 7:.i=0;]; return MEM[ 2:___ 3:___ 4:___ 5:___ 6:___ 7:.i=0;]; return Test.N; ]", code.print()); } @Test @@ -173,7 +173,7 @@ struct _S2 { int x; }; return (new _S1).s=new _S2; """); code.parse().opto(); - assertEquals("return _S2;", code.print()); + assertEquals("return Test._S2;", code.print()); } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java index d4790b3b..4d273aff 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -175,7 +175,7 @@ return root; """); code.parse().opto().typeCheck(); assertEquals("return Test._Tree;", code.print()); - assertEquals("Test._Tree{_kids=*Test._Tree {*[]*Test._Tree?? !_kids; }?[ Test._Tree{_kids=null},null]}", Eval2.eval(code, 0)); + assertEquals("Test._Tree{_kids=*Test._Tree {*[]*Test._Tree?[mutable]? !_kids; }?[ Test._Tree{_kids=null},null]}", Eval2.eval(code, 0)); } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java index 24daa164..faba6451 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -334,6 +334,18 @@ return arg ? 0 : arg; assertEquals("0", Eval2.eval(code, 0)); } + @Test + public void testShortCircuitGuard() { + CodeGen code = new CodeGen(""" +struct S { int !x; }; +val get = { S s -> s.x; }; +S? !s = arg ? new S; +if( !s || !arg ) return 0; +return get(s); +"""); + code.parse().opto().typeCheck(); + } + @Test public void testTrinary2() { CodeGen code = new CodeGen(""" @@ -395,7 +407,7 @@ struct S{}; return arg ? 7 : new S; """); try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("No common type amongst 7 and *Test.S {}",e.getMessage()); } + catch( Exception e ) { assertEquals("Cannot return generic scalar",e.getMessage()); } } // --------------------------------------------------------------- diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java index b65e101b..dc29dafa 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -146,7 +146,8 @@ return fcn(3); CodeGen code = new CodeGen("val _fact = { int x -> x <= 1 ? 1 : x*_fact(x-1); }; return _fact(arg);"); code.parse().opto().typeCheck(); String ir = code.print(); - assertTrue(ir.equals("Stop[ return Phi(Region,1,(arg*#2)); return Phi(Region,1,(Parm_x(_fact,(arg-1),(x-1))*#2)); ]") || + assertTrue(ir.equals("Stop[ return #2; return Phi(Region,1,(Parm_x(_fact,arg,(x-1))*#2)); ]") || + ir.equals("Stop[ return Phi(Region,1,(arg*#2)); return Phi(Region,1,(Parm_x(_fact,(arg-1),(x-1))*#2)); ]") || ir.equals("Stop[ return Phi(Region,1,(arg*Phi(Region,1,((arg-1)*#2)))); return Phi(Region,1,(Parm_x(_fact,(Sub-1),(x-1))*#2)); ]")); assertEquals( "1", Eval2.eval(code, 0)); assertEquals( "1", Eval2.eval(code, 1)); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java index eaf76041..10c4690e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -58,7 +58,7 @@ val hashCode = { String self -> hashCode(new String("Hello, World!")); """; CodeGen code = new CodeGen(src).driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MEM[ 2:___ 3:___ 4:.cs=Parm_s(Test.String.String,*[]u8); 5:._hashCode=0;]; return MEM[ 2:___ 3:___ 4:___ 5:._hashCode=0;]; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(((Phi_hash<<5)-Phi_hash)+.[])))); ]", code.print()); + assertEquals("Stop[ return Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash)))); return MEM[ 2:___ 3:___ 4:.cs=Parm_s(Test.String.String,*[]u8[final]); 5:._hashCode=0;]; return MEM[ 2:___ 3:___ 4:___ 5:._hashCode=0;]; return Test.String; return Phi(Region,0,1,0,1); return Phi(Region,(!=0)._hashCode,Phi(Region,123456789,(!=0)Phi(Loop,0,(.[]+((Phi_hash<<5)-Phi_hash))))); ]", code.print()); assertEquals("4029215624828139541", Eval2.eval(code, 2)); } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 17b0fd0a..e8a3a875 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -80,9 +80,34 @@ val _test_sqrt_noInline = { flt x -> }; flt farg = arg; return _test_sqrt_noInline(farg) + _test_sqrt_noInline(farg+2.0); """; - testCPU(src,"x86_64_v2", "SystemV",65,null); - testCPU(src,"riscv" , "SystemV",35,null); - testCPU(src,"arm" , "SystemV",35,null); + testCPU(src,"x86_64_v2", "SystemV",48,null); + testCPU(src,"riscv" , "SystemV",17,null); + testCPU(src,"arm" , "SystemV",18,null); + } + + @Test + public void testIterPrettyPrintIsLocalAndReadOnly() { + CodeGen code = new CodeGen(""" + val f_noInline = { flt x -> while(1) { if(x) return x; } }; + flt y=arg; + return f_noInline(y)+f_noInline(y+2.0); + """).driver(CodeGen.Phase.Iter); + assertNull(code._start._ltree); + int pre = code._start._pre; + + String p0 = code.toString(); + String p1 = code.toString(); + assertEquals(p0,p1); + assertNull(code._start._ltree); + assertEquals(pre,code._start._pre); + + int main0 = p0.indexOf("--- class:Test."); + int main1 = p0.indexOf("--- class:Test. ----------------------",main0); + int fun0 = p0.indexOf("--- f_noInline ",main1); + int fun1 = p0.indexOf("--- f_noInline ----------------------",fun0); + assertTrue(main0 < main1 && main1 < fun0 && fun0 < fun1); + assertTrue(p0.indexOf("ToFloat",main0) < p0.indexOf("Call",main0)); + assertTrue(p0.indexOf("CallEnd",fun0) == -1 || p0.indexOf("CallEnd",fun0) > fun1); } @Test @@ -108,7 +133,7 @@ for( int i=0; i }; """; testCPU(src,"x86_64_v2", "SystemV",18,null); - testCPU(src,"riscv" , "SystemV", 5,null); - testCPU(src,"arm" , "SystemV", 4,null); + testCPU(src,"riscv" , "SystemV", 7,null); + testCPU(src,"arm" , "SystemV", 8,null); } @Test public void testCast() { String src = "struct Bar { int x; }; var b = arg ? new Bar; return b ? b.x++ + b.x++ : -1;"; testCPU(src,"x86_64_v2", "SystemV",3,null); - testCPU(src,"riscv" , "SystemV",3,null); - testCPU(src,"arm" , "SystemV",3,null); + testCPU(src,"riscv" , "SystemV",6,null); + testCPU(src,"arm" , "SystemV",6,null); } @Test diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index e4d49e7f..6eb9a698 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -74,7 +74,7 @@ for( int i=0; i }; """; testCPU(src,"x86_64_v2", "SystemV",18,null); - testCPU(src,"riscv" , "SystemV", 5,null); - testCPU(src,"arm" , "SystemV", 4,null); + testCPU(src,"riscv" , "SystemV", 7,null); + testCPU(src,"arm" , "SystemV", 8,null); } @Test public void testStringExport() throws IOException { @@ -359,7 +359,7 @@ val fib = { int n -> int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; - EvalRisc5 R5 = TestRisc5.build( src, "fcn", ps, 0, false); + EvalRisc5 R5 = TestRisc5.build( src, "fcn", ps, 2, false); R5.regs[riscv.A1] = 1; // Index 1 R5.st8(ps,3); // Length R5.st8(ps+1*8,p0); @@ -375,7 +375,7 @@ val fib = { int n -> assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); - EvalArm64 A5 = TestArm64.build("fcn", src, ps, 0, false); + EvalArm64 A5 = TestArm64.build("fcn", src, ps, 2, false); A5.regs[arm.X1] = 1; // Index 1 A5.st8(ps, 3); A5.st8(ps+1*8,p0); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java index 91b8310d..68f94f12 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -60,7 +60,7 @@ _Person !p = new _Person; p.age = (arg<<17)>>17; return 0; """; - assertEquals(83, testCPUSize(src, "x86_64_v2","win64", 3 )); + assertEquals(82, testCPUSize(src, "x86_64_v2","win64", 3 )); assertEquals(96, testCPUSize(src, "riscv", "SystemV", 4 )); assertEquals(96, testCPUSize(src, "arm" , "SystemV", 4 )); @@ -88,11 +88,11 @@ return 0; int trap = R5.step(100); assertEquals(0,trap); - EvalArm64 A5 = TestArm64.build("sext_str_not_fold_away_2", src, 0, 4, false); + EvalArm64 A5 = TestArm64.build("sext_str_not_fold_away_2", src, 0, 3, false); int trap_arm = A5.step(100); assertEquals(0,trap_arm); - assertEquals(83, testCPUSize(src, "x86_64_v2","win64",3 )); + assertEquals(82, testCPUSize(src, "x86_64_v2","win64",3 )); assertEquals(96, testCPUSize(src, "riscv", "SystemV",4 )); assertEquals(96, testCPUSize(src, "arm", "SystemV",4 )); @@ -116,9 +116,9 @@ return 0; int trap_arm = A5.step(100); assertEquals(0,trap_arm); - assertEquals(71, testCPUSize(src, "x86_64_v2","win64",3 )); + assertEquals(72, testCPUSize(src, "x86_64_v2","win64",3 )); assertEquals(92, testCPUSize(src, "riscv", "SystemV",5 )); - assertEquals(92, testCPUSize(src, "arm", "SystemV",5 )); + assertEquals(92, testCPUSize(src, "arm", "SystemV",5)); // do assertEquals here } @@ -148,7 +148,7 @@ val fcn = { Person?[] ps, int x -> // exports a field with a constant fcn ptr; e int p1 = ps+4*8+1*8; // P2 = { age } // sizeof=8 int p2 = ps+4*8+2*8; - EvalRisc5 R5 = TestRisc5.build( src, "fcn", ps, 0, false); + EvalRisc5 R5 = TestRisc5.build( src, "fcn", ps, 2, false); R5.regs[riscv.A1] = 1; // Index 1 R5.st8(ps,3); // Length R5.st8(ps+1*8,p0); @@ -164,7 +164,7 @@ val fcn = { Person?[] ps, int x -> // exports a field with a constant fcn ptr; e assertEquals(17+1,R5.ld8(p1)); assertEquals(60+0,R5.ld8(p2)); - EvalArm64 A5 = TestArm64.build("fcn", src, ps, 0, false); + EvalArm64 A5 = TestArm64.build("fcn", src, ps, 2, false); A5.regs[arm.X1] = 1; // Index 1 A5.st8(ps, 3); A5.st8(ps+1*8,p0); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 08acfd32..3346aa51 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -85,6 +85,26 @@ return a && b ? 0 : 1; // Expected answer 0 assertEquals(0,arm.regs[0]); } + @Test + public void testLogicalValueSemantics() { + assertEquals("42", Eval2.eval(new CodeGen("return 7 && 42;").parse().opto(), 0)); + assertEquals("0", Eval2.eval(new CodeGen("return 0 && 42;").parse().opto(), 0)); + assertEquals("7", Eval2.eval(new CodeGen("return 7 || 42;").parse().opto(), 0)); + assertEquals("42", Eval2.eval(new CodeGen("return 0 || 42;").parse().opto(), 0)); + } + + @Test + public void testMixedScalarNotPhiPredicate() { + CodeGen code = new CodeGen(""" +struct S {}; +S? s = arg ? new S; +return !(!s || !arg) ? 1 : 0; +"""); + code.parse().opto().typeCheck(); + assertEquals("0", Eval2.eval(code, 0)); + assertEquals("1", Eval2.eval(code, 1)); + } + @Test public void testAndPtr() throws IOException { // Todo: have one src here @@ -97,7 +117,7 @@ return ptr && ptr.fld ? "true" : "false"; assertEquals("true", Eval2.eval(code, 0)); // Evaluate on RISC5 emulator - EvalRisc5 R5 = TestRisc5.build( src, "class:Test.", 1, 8, false); + EvalRisc5 R5 = TestRisc5.build( src, "class:Test.", 1, 12, false); int trap = R5.step(100); assertEquals(0,trap); int adr = (int)R5.regs[riscv.A0]; // Returns a Simple *u8[~] string @@ -105,7 +125,7 @@ return ptr && ptr.fld ? "true" : "false"; assertEquals(0x65757274,R5.ld4s(adr+4)); // "true" // Evaluate on ARM emulator - EvalArm64 arm = TestArm64.build("class:Test.", src, 1, 8, false); + EvalArm64 arm = TestArm64.build("class:Test.", src, 1, 12, false); trap = arm.step(100); assertEquals(0,trap); int adr2 = (int)arm.regs[0]; // Returns a Simple *u8[~] string @@ -185,13 +205,13 @@ return (a && sq_noInline(0)) TestC.runSF( src, "and3", "", 2); // Evaluate on RISC5 emulator - EvalRisc5 R5 = TestRisc5.build( src, "and3", 0, 5, false); + EvalRisc5 R5 = TestRisc5.build( src, "and3", 0, 2, false); int trap = R5.step(100); assertEquals(0,trap); assertEquals(0,R5.regs[riscv.A0]); // Evaluate on ARM emulator - EvalArm64 arm = TestArm64.build("and3", src, 0, 5, false); + EvalArm64 arm = TestArm64.build("and3", src, 0, 2, false); trap = arm.step(100); assertEquals(0,trap); assertEquals(0,arm.regs[0]); @@ -251,7 +271,7 @@ return s.skip().x; try { new CodeGen(src).parse().opto().typeCheck(); fail(); } catch( Exception e ) { // Bad error message, but basically requires a mutable 'x' field. - assertEquals("Argument #0 isa *Test._Scan {i64 x; *[]u8 buf; { *Test._Scan -> *Test._Scan {i64 !x; *[]u8 buf; {[ 5]} skip; } #[ 5]} skip; }, but must be a *Test._Scan {i64 !x; *[]u8 buf; { *Test._Scan -> *Test._Scan #[ 5]} skip; }",e.getMessage()); + assertEquals("Argument #0 isa *Test._Scan {i64 x; *[]u8[final] buf; { *Test._Scan -> *Test._Scan {i64 !x; *[]u8 buf; {[ 5]} skip; } #[ 5]} skip; }, but must be a *Test._Scan {i64 !x; *[]u8[final] buf; { *Test._Scan -> *Test._Scan #[ 5]} skip; }",e.getMessage()); } }; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java index fe8aaf2e..eb89dbb3 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -62,16 +62,16 @@ return (sq_noInline(2) <= score < sq_noInline(3)) ? 0 // Expected : 1; // Error """; - TestC.runSF( src, "stacked_r_3", "", 4); + TestC.runSF( src, "stacked_r_3", "", 2); // Evaluate on RISC5 emulator - EvalRisc5 R5 = TestRisc5.build( src, "stacked_r_3", 0, 5, false); + EvalRisc5 R5 = TestRisc5.build( src, "stacked_r_3", 0, 2, false); int trap = R5.step(100); assertEquals(0,trap); assertEquals(0,R5.regs[riscv.A0]); // Evaluate on ARM emulator - EvalArm64 arm = TestArm64.build("stacked_r_3", src, 0, 5, false); + EvalArm64 arm = TestArm64.build("stacked_r_3", src, 0, 3, false); int trap_1 = arm.step(100); assertEquals(0,trap_1); assertEquals(0,arm.regs[0]); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java index 8f1c7285..b21734b4 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -18,9 +18,17 @@ import static org.junit.Assert.*; public class Chapter25Test { - private static final String SYS_MODDIR = "src/main/smp"; private static final String SYS_BLDDIR = "build/objs/lib_"+TestC.CPU_ABI; - private static final String RELEASE_SYS_BLDDIR = TestC.RELEASE_SYS_DIR; + private static final File SYS_FILE = new File(SYS_BLDDIR+"/sys.o"); + + @Test + public void testForwardConstructor() { + CodeGen code = new CodeGen("src/test/java/com/seaofnodes/simple/test_smp/forward_ctor", + "build/objs/forward_ctor_parse",null, + "m",null,123L,TypeInteger.BOT); + code.driver(CodeGen.Phase.TypeCheck); + } + @Test public void testPostfixFieldUpdate() { @@ -163,56 +171,34 @@ public class Chapter25Test { } - private File buildTestSys(boolean clean) { - if( clean ) - delELFiles(new File(SYS_BLDDIR)); - File sys_file = new File(SYS_BLDDIR+"/sys.o" ); - if( sys_file.exists() ) - return sys_file; - - // Compile SYS_MODDIR/sys.smp into SYS_BLDDIR/sys.o. Chapter25 - // compiler tests intentionally depend on this freshly built sys.o. - CodeGen code1 = new CodeGen(SYS_MODDIR, SYS_BLDDIR,null, - "sys",null,123L,TypeInteger.BOT); - code1.driver(CodeGen.Phase.Export,TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false,0); - assertTrue( sys_file.exists() ); - return sys_file; - } - @Test public void testSys() { - delELFiles(new File(SYS_BLDDIR)); - - CodeGen code1 = new CodeGen(SYS_MODDIR, SYS_BLDDIR,null, - "sys",null,123L,TypeInteger.BOT); - code1.driver(CodeGen.Phase.Export,TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false,0); - - // Verify produces sys.o, sys/io.o - File sys_file = new File(SYS_BLDDIR+"/sys.o" ); - assertTrue( sys_file.exists() ); + assertTrue("Missing "+SYS_FILE+"; run make tests_sys", SYS_FILE.exists()); // Can read the ELF files - ElfReader sys_elf = ElfReader.load( sys_file, null); - sys_elf.loadSimple(code1); + CodeGen code1 = new CodeGen("return 0;"); + ElfReader sys_elf = ElfReader.load(SYS_FILE, null); + sys_elf.loadPublicTypes(code1); // Elf files are sane - // Sys depends on io, libc, aryi64, aryu8 - assertEquals(6,sys_elf._deps.length); + // Sys depends on io, libc, char, collections, and array utilities. + assertEquals(10,sys_elf._deps.length); assertSame("sys/aryu8" ,sys_elf._deps[0]); - assertSame("sys/io" ,sys_elf._deps[1]); - assertSame("sys/aryi64",sys_elf._deps[2]); - assertSame("sys/Ary" ,sys_elf._deps[3]); - assertSame("sys/Scan" ,sys_elf._deps[4]); - assertSame("sys/libc" ,sys_elf._deps[5]); + assertSame("sys/char" ,sys_elf._deps[1]); + assertSame("sys/io" ,sys_elf._deps[2]); + assertSame("sys/ary" ,sys_elf._deps[3]); + assertSame("sys/aryi64",sys_elf._deps[4]); + assertSame("sys/adt/bitset",sys_elf._deps[5]); + assertSame("sys", sys_elf._deps[6]); + assertSame("sys/scan" ,sys_elf._deps[7]); + assertSame("sys/adt" ,sys_elf._deps[8]); + assertSame("sys/libc" ,sys_elf._deps[9]); assertSame("class:sys" ,sys_elf._clz._name); } @Test public void testHelloWorld() throws IOException { - File sys_file = buildTestSys(false); - assertTrue("Missing "+sys_file+"; testHelloWorld depends on testSys building it", sys_file.exists()); - String expected = "Hello, World!\n"; String prog = "return sys.io.p(\""+expected+"\") - "+expected.length()+";"; TestC.run(prog,"helloWorld",new Ary<>(new String[]{SYS_BLDDIR}), @@ -221,23 +207,16 @@ public class Chapter25Test { @Test public void testHelloWorldDriver() throws Exception { - File sys_file = new File(RELEASE_SYS_BLDDIR+"/sys.o"); - assertTrue("Missing "+sys_file+"; run make release or make tests_sys first", sys_file.exists()); - Simple.main(new String[]{"-L",RELEASE_SYS_BLDDIR,"--norun","docs/examples/A_helloWorld.smp"}); + Simple.main(new String[]{"-L",SYS_BLDDIR,"--norun","docs/examples/A_helloWorld.smp"}); } @Test public void testHelloWorldDriverLibFile() throws Exception { - File sys_file = new File(RELEASE_SYS_BLDDIR+"/sys.o"); - assertTrue("Missing "+sys_file+"; run make release or make tests_sys first", sys_file.exists()); - Simple.main(new String[]{"-L",sys_file.toString(),"docs/examples/A_helloWorld.smp"}); + Simple.main(new String[]{"-L",SYS_FILE.toString(),"docs/examples/A_helloWorld.smp"}); } @Test public void testHelloWorldNoInline() throws Exception { - File sys_file = buildTestSys(false); - assertTrue("Missing "+sys_file+"; testHelloWorldNoInline depends on testSys building it", sys_file.exists()); - String base = "helloWorldNoInline"; String expected = "Hello, World!\n"; String prog = "return sys.io.p_noInline(\""+expected+"\") - "+expected.length()+";"; @@ -250,7 +229,7 @@ public class Chapter25Test { String syms = run(new String[]{"nm",obj}); assertTrue(syms, syms.contains(" U sys.io.p_noInline")); - String out = run(new String[]{"gcc",obj,sys_file.toString(),TestC.runtimeObject(),"-lm","-g","-o",exe}); + String out = run(new String[]{"gcc",obj,SYS_FILE.toString(),TestC.runtimeObject(),"-lm","-g","-o",exe}); assertEquals("",out); String rez = run(new String[]{exe}); assertEquals(expected,rez); @@ -267,8 +246,6 @@ public class Chapter25Test { @Test public void testRedirectedRead() throws IOException { - File sys_file = buildTestSys(false); - assertTrue("Missing "+sys_file+"; testRedirectedRead depends on testSys building it", sys_file.exists()); String src = """ u8[] buf = new u8[10]; i64 ptr = buf; @@ -282,28 +259,58 @@ return rez < buf# ? 0 : sys.libc._exit(-2); @Test public void testBubbles() throws IOException { - File sys_file = buildTestSys(false); - assertTrue("Missing "+sys_file+"; testBubbles depends on testSys building it", sys_file.exists()); String src = Files.readString( Path.of("docs/examples/BubbleSort.smp")); - TestC.runArgs(src,"BubbleSort",new Ary<>(new String[]{SYS_BLDDIR}), - TestC.CALL_CONVENTION,"-17, 2, 3, 999\n",-1, - "[3, 2,-17, 999 ]"); - - String obj = "build/objs/BubbleSort.o"; - String exe = "build/objs/BubbleSort"+(TestC.OS.startsWith("Windows") ? ".exe" : ""); - Ary libs = new Ary<>(new String[]{sys_file.toString()}); - assertEquals("1, 2, 3, 4, 4, 5\n", - TestC.gcc(obj,null,null,null,libs,exe,"[4, 5, 3, 1, 4, 2]")); - assertEquals("1, 2, 3, 4, 5\n", - TestC.gcc(obj,null,null,null,libs,exe,"[1, 2, 3, 4, 5]")); - assertEquals("1, 2, 3, 4, 5, 6, 7, 8, 9\n", - TestC.gcc(obj,null,null,null,libs,exe,"[9, 8, 7, 6, 5, 4, 3, 2, 1]")); + String exe = TestC.compile(src,"BubbleSort",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("[-17, 2, 3, 999]\n", + TestC.exec(exe,"[3, 2,-17, 999 ]")); + assertEquals("[1, 2, 3, 4, 4, 5]\n", + TestC.exec(exe,"[4, 5, 3, 1, 4, 2]")); + assertEquals("[1, 2, 3, 4, 5]\n", + TestC.exec(exe,"[1, 2, 3, 4, 5]")); + assertEquals("[1, 2, 3, 4, 5, 6, 7, 8, 9]\n", + TestC.exec(exe,"[9, 8, 7, 6, 5, 4, 3, 2, 1]")); String usage = "Usage: please provide a list of at least two integers to sort in the format \"[1, 2, 3, 4, 5]\"\n"; - assertEquals(usage,TestC.gcc(obj,null,null,null,libs,exe)); - assertEquals(usage,TestC.gcc(obj,null,null,null,libs,exe,"")); - assertEquals(usage,TestC.gcc(obj,null,null,null,libs,exe,"[1]")); - assertEquals(usage,TestC.gcc(obj,null,null,null,libs,exe,"[4 5 3]")); + assertEquals(usage,TestC.exec(exe)); + assertEquals(usage,TestC.exec(exe,"")); + assertEquals(usage,TestC.exec(exe,"[1]")); + assertEquals(usage,TestC.exec(exe,"[4 5 3]")); } + @Test + public void testCapitalize() throws IOException { + String src = Files.readString(Path.of("docs/examples/Capitalize.smp")); + String exe = TestC.compile(src,"Capitalize",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("Hello world\n",TestC.exec(exe,"hello world")); + assertEquals("Hello World\n",TestC.exec(exe,"Hello World")); + assertEquals("123 apples\n",TestC.exec(exe,"123 apples")); + assertEquals("Usage: please provide a string\n",TestC.exec(exe)); + assertEquals("Usage: please provide a string\n",TestC.exec(exe,"")); + assertEquals("Use quotes around multiple strings.\n",TestC.exec(exe,"hello","world")); + } + + @Test + public void testDijkstra() throws IOException { + String src = Files.readString(Path.of("docs/examples/Dijkstra.smp")); + String matrix = "[0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0]"; + String exe = TestC.compile(src,"Dijkstra",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("2\n",TestC.exec(exe,matrix,"0","1")); + String usage = "Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n"; + assertEquals("7\n",TestC.exec(exe,matrix,"0","4")); + assertEquals(usage,TestC.exec(exe)); + assertEquals(usage,TestC.exec(exe,"","","")); + assertEquals(usage,TestC.exec(exe,"[1, 0, 3, 0, 5, 1]","1","2")); + assertEquals(usage,TestC.exec(exe,"[0, 0, 0, 0]","0","1")); + } + + @Test + public void testFileIO() throws IOException { + String src = Files.readString(Path.of("docs/examples/FileIO.smp")); + String exe = TestC.compile(src,"FileIO",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("File I/O succeeded\n",TestC.exec(exe)); + } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Simple.java b/chapter25/src/test/java/com/seaofnodes/simple/Simple.java index 35b9b922..a5d104e7 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Simple.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Simple.java @@ -247,7 +247,7 @@ Options: if ( !TestC.CPU_PORT.equals( cpu ) || !TestC.CALL_CONVENTION.equals( abi ) ) throw bad("cannot run code on not native target"); String exe = TestC.OS.startsWith("Windows") ? outBase+".exe" : outBase; - String result = TestC.gcc(outBase+".o", null, null, true, exe); + String result = TestC.gcc(outBase+".o", null, null, "", TestC.linkObjs(externPaths), exe); System.out.print(result); } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java index 2f737579..bd8a52cc 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TestC.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TestC.java @@ -98,6 +98,17 @@ public abstract class TestC { private static void run0( String src, String base, Ary externPaths, String simple_conv, String c_conv, String cfile, String stdin, String expected, int spills, String[] programArgs ) throws IOException { + String exe = compile(src,base,externPaths,simple_conv,c_conv,cfile,spills); + + String[] execArgs = new String[programArgs.length+1]; + execArgs[0] = exe; + System.arraycopy(programArgs,0,execArgs,1,programArgs.length); + String result = execStdin(stdin, execArgs ); + assertEquals(expected,result); + } + + public static String compile( String src, String base, Ary externPaths, String simple_conv, String c_conv, + String cfile, int spills ) throws IOException { // Simple file base-name example: // foo.smp -> // build/objs/foo.o - object file @@ -110,17 +121,14 @@ public abstract class TestC { CodeGen code = new CodeGen(null,"build/objs",externPaths,base,src,126L,TypeInteger.BOT); code.driver( CPU_PORT, simple_conv, false, cfile==null ); - String[] execArgs = new String[programArgs.length+1]; - execArgs[0] = exe; - System.arraycopy(programArgs,0,execArgs,1,programArgs.length); - String result = gcc(obj, c_conv, cfile, stdin, linkObjs(externPaths), execArgs ); - assertEquals(expected,result); + linkExe(obj, c_conv, cfile, linkObjs(externPaths), exe); // Allocation quality not degraded int delta = spills>>3; if( delta==0 ) delta = 1; if( spills != -1 && !CodeGen.iterSeedOverridden() ) assertEquals("Expect spills:",spills,code._regAlloc._spillScaled,delta); + return exe; } // Link with gcc, and execute the resulting binary, returning stdout as a @@ -146,7 +154,11 @@ public abstract class TestC { } public static String gcc( String obj, String c_conv, String cfile, String stdin, Ary linkObjs, String... args ) throws IOException { + linkExe(obj,c_conv,cfile,linkObjs,args[0]); + return execStdin(stdin,args); + } + public static void linkExe( String obj, String c_conv, String cfile, Ary linkObjs, String exe ) throws IOException { // Compile the C program. Compiling code and constants in the low // 2Gig. Pointers are 64b BUT since always in the low 2G all the // high bits are zero - and Simple code can be emitted treating @@ -165,7 +177,7 @@ public abstract class TestC { "-lm", // Picks up 'sqrt' for newtonFloat tests to compare "-g", "-o", - args[0], + exe, }); // Calling convention for C calls, if any if( cfile!=null ) { @@ -190,6 +202,13 @@ public abstract class TestC { assertEquals( 0, exit ); //assertTrue(result.isEmpty()); // No data in error stream + } + + public static String exec( String... args ) throws IOException { + return execStdin(null,args); + } + + private static String execStdin( String stdin, String... args ) throws IOException { // Execute results ProcessBuilder smp = new ProcessBuilder(args); File stdinFile = null; @@ -204,8 +223,9 @@ public abstract class TestC { Process p = smp.start(); if( stdin==null ) p.getOutputStream().close(); + int exit; try { exit = (byte)p.waitFor(); } catch( InterruptedException e ) { throw new IOException("interrupted"); } - result = Files.readString(stdoutFile.toPath()); + String result = Files.readString(stdoutFile.toPath()); if( stdinFile != null ) stdinFile.delete(); stdoutFile.delete(); @@ -214,7 +234,7 @@ public abstract class TestC { return result; } - private static Ary linkObjs(Ary externPaths) { + static Ary linkObjs(Ary externPaths) { if( externPaths == null ) return null; Ary objs = new Ary<>(String.class); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java index e881a2bf..65635afe 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -7,7 +7,7 @@ import static org.junit.Assert.assertSame; public class TypeTest { - // Test basic properties and GLB + // Test basic type properties @Test public void testTypeAdHoc() { Assert.assertEquals( TypeScalar.BOT, TypeInteger.TRUE.meet(TypeNil.NIL) ); @@ -19,13 +19,8 @@ public class TypeTest { TypeStruct s2 = TypeStruct.make("s2",false, Field.make("a", TypeInteger.BOT,-3, false), Field.make("b", TypeInteger.BOT,-4, false) ); - TypeStruct x1ro = (TypeStruct)s1.makeRO(); TypeMemPtr p1 = TypeMemPtr.make(s1); - // GLB no longer forces RO - //Assert.assertEquals(x1ro, ((TypeMemPtr)p1.glb(false))._obj); Assert.assertNotEquals(s1, s1.dual()); - TypeStruct s1dglb = ((TypeMemPtr)p1.dual().glb(false))._obj; - Assert.assertTrue(x1ro.isa(s1dglb)); TypeMem m1 = TypeMem.make(2,TypeNil.NIL); TypeMem m2 = TypeMem.make(3,TypeInteger.U16); @@ -42,9 +37,7 @@ public class TypeTest { Assert.assertEquals(TypeMem.make(1,TypeScalar.BOT), m1.meet(m3)); Assert.assertEquals(scalarMemBot, ((TypeMem)m3.meet(m4)).makeFrom( XInt.FULL, XInt.FULL)); - Assert.assertEquals(TypeMem.make(2,Type.BOTTOM), m1.glb(false)); Assert.assertEquals(TypeMem.make(2,Type.XNIL,true,true,true, XInt.FULL, XInt.FULL), m1.dual()); - Assert.assertEquals(m4.dual(), m4.glb(false).dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); @@ -59,18 +52,8 @@ public class TypeTest { Assert.assertEquals(s2, ptr2nil._obj); Assert.assertNotEquals(ptr1, ptr2); - Type p1glb = ptr1.glb(false); - // GLB no longer forces RO - //Assert.assertNotEquals(ptr1, p1glb ); - Type p1nro = ptr1nil.makeRO(); - // GLB no longer forces RO - //Assert.assertEquals(p1nro, p1glb); - Assert.assertEquals(ptr1, ptr1.dual().dual()); - Assert.assertTrue(p1glb.makeRO().isa( ptr1.dual().glb(false))); Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT), ptr1.meet(ptr2nil)); - // GLB no longer forces RO - //Assert.assertEquals(p1glb, ptr1.meet(TypeNil.NIL).makeRO()); TypeMemPtr TOP = TypeMemPtr.TOP; TypeMemPtr BOT = TypeMemPtr.makeNullable(TypeStruct.BOT); @@ -96,9 +79,6 @@ public class TypeTest { Assert.assertTrue(s1ro.isFinal()); Assert.assertFalse(S1.isConstant()); - Type s1glb = S1.field("s2")._t.glb(false); - Type s1glb2 = S1.field("s2")._t.glb(false); - Assert.assertSame(s1glb,s1glb2); } // Test theoretical properties. @@ -177,14 +157,6 @@ public class TypeTest { assertSame(TypeStruct.SFLT1,d1); } - @Test - public void testGLB() { - Type[] ts = Type.gather(); - for( Type t0 : ts ) - if( !(t0 instanceof Field || t0 instanceof TypeStruct || t0 instanceof TypeTuple || t0 instanceof TypeConAry ) ) - Assert.assertTrue(t0.isa(t0.glb(false))); - } - @Test public void testList() { TypeStruct list = TypeStruct.open("List"); diff --git a/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m.smp b/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m.smp new file mode 100644 index 00000000..569f38be --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m.smp @@ -0,0 +1,2 @@ +val a = a; +val b = b; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/a.smp b/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/a.smp new file mode 100644 index 00000000..97113b71 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/a.smp @@ -0,0 +1 @@ +val f = { -> new b(1); }; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/b.smp b/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/b.smp new file mode 100644 index 00000000..43770b60 --- /dev/null +++ b/chapter25/src/test/java/com/seaofnodes/simple/test_smp/forward_ctor/m/b.smp @@ -0,0 +1,4 @@ +struct b { + int x; + new b = { int y -> x = y; }; +}; diff --git a/chapter25/src/test/java/com/seaofnodes/simple/test_smp/seed_repro/sys/Ary.smp b/chapter25/src/test/java/com/seaofnodes/simple/test_smp/seed_repro/sys/Ary.smp deleted file mode 100644 index e3dd6140..00000000 --- a/chapter25/src/test/java/com/seaofnodes/simple/test_smp/seed_repro/sys/Ary.smp +++ /dev/null @@ -1,6 +0,0 @@ -// Array utilities, discovered indirectly from aryu8. -val copy = { u8[] dst, int doff, u8[~] src, int soff, int len -> - for( int i=0; i + for( int i=0; i= newlen ) newlen *= 2; u8[] !buf2 = new u8[newlen]; - Ary.copy(buf2,0,buf,0,buf#); + ary.copy(buf2,0,buf,0,buf#); buf = buf2; self; }; @@ -21,10 +21,10 @@ struct aryu8 { self; }; - val addAry = { u8[~] ary -> - _grow(ary#); - Ary.copy(buf,len,ary,0,ary#); - len += ary#; + val addAry = { u8[~] xs -> + _grow(xs#); + ary.copy(buf,len,xs,0,xs#); + len += xs#; self; }; -- cgit v1.2.3