diff options
Diffstat (limited to 'chapter32')
34 files changed, 927 insertions, 545 deletions
diff --git a/chapter32/Makefile b/chapter32/Makefile index af6da154..d91f59e0 100644 --- a/chapter32/Makefile +++ b/chapter32/Makefile @@ -30,13 +30,23 @@ test_cp := $(filter-out $(test_sys) ,$(test_cp4)) test_group0 := com.seaofnodes.simple.DrawTest test_group1 := com.seaofnodes.simple.GraphicsTest test_group2 := $(addprefix com.seaofnodes.simple.,TimeTest MemoryEncodingTest ChainedComparisonTest ParserTest Chapter28bTest) -test_group3 := $(addprefix com.seaofnodes.simple.,StringFormatTest FinalConstructionTest PartialReadTest EscapeFlowTest CallEndTest BulkMemPhiTest) -test_group4 := $(addprefix com.seaofnodes.simple.,BreakoutTest ArithNodeTest PhaseTest MethodAccessTest Int32Test MinusNodeTest ConstructorCompletionTest) -test_group5 := $(addprefix com.seaofnodes.simple.,TerminalInputTest ParserDiagnosticTest StaticDataTest ArrayInitTest MethodFieldsTest ConstantArrayTest BoundaryTest IntegerLiteralTest ConstructionRequirementsTest) -test_group6 := $(addprefix com.seaofnodes.simple.,AssemblyDumpTest AudioTest MathTest TicTacToeTest SelectiveLoadingTest FloatComparisonNativeTest SchedulingTest SeparateCompilationTest ConstructionGroupTest CompoundAssignmentTest) +test_group3 := $(addprefix com.seaofnodes.simple.,StringFormatTest StaticDataTest PhaseTest FinalConstructionTest PartialReadTest EscapeFlowTest CallEndTest BulkMemPhiTest) +test_group4 := $(addprefix com.seaofnodes.simple.,BreakoutTest ConvertNodeTest ArithNodeTest MethodAccessTest Int32Test MinusNodeTest ConstructorCompletionTest) +test_group5 := $(addprefix com.seaofnodes.simple.,TerminalInputTest ParserDiagnosticTest ArrayInitTest MethodFieldsTest ConstantArrayTest BoundaryTest IntegerLiteralTest ConstructionRequirementsTest) +test_group6 := $(addprefix com.seaofnodes.simple.,AssemblyDumpTest AudioTest MathTest TicTacToeTest ModTest SelectiveLoadingTest FloatComparisonNativeTest SchedulingTest SeparateCompilationTest ConstructionGroupTest CompoundAssignmentTest) test_group7 := $(filter-out $(test_group0) $(test_group1) $(test_group2) $(test_group3) $(test_group4) $(test_group5) $(test_group6),$(test_cp)) test_groups := $(addprefix tests_group,0 1 2 3 4 5 6 7) +# Fast compiler checks retain the full lattice, chapter/backend regressions, +# fuzzer regression seeds, and focused compiler tests. Library/application and +# CLI integration remains in `tests`. New compiler tests join sanity group 2. +sanity_omit := $(addprefix com.seaofnodes.simple.,DrawTest GraphicsTest TimeTest StringFormatTest BreakoutTest TerminalInputTest AudioTest MathTest TicTacToeTest StreamIOTest RuntimeArgsTest NativeExecutionTest ParserDiagnosticTest) +sanity_cp := $(filter-out $(sanity_omit),$(test_cp)) +sanity_group0 := $(addprefix com.seaofnodes.simple.,ClassInitDependenciesTest ConvertNodeTest ArithNodeTest MemoryEncodingTest ModTest IntrinsicTest AssemblyDumpTest) +sanity_group1 := $(addprefix com.seaofnodes.simple.,StaticDataTest FloatComparisonNativeTest ArrayInitTest ConstantArrayTest BoundaryTest Int32Test ReceiverTest GlobalAssignmentTest IncrementalBuildTest SeparateCompilationTest) +sanity_group2 := $(filter-out $(sanity_group0) $(sanity_group1),$(sanity_cp)) +sanity_groups := $(addprefix sanity_group,0 1 2) + # Size each test JVM for a share of the machine, instead of giving every JVM # JIT and GC pools sized for all cores. Absolute paths also serve child JVMs # launched from a group's private working directory (native Java on Windows). @@ -158,6 +168,15 @@ $(test_groups): tests_group%: $(test_classes) $(TEST_SYS) $(RELEASE_SYS) $(RELEA @echo "testing $@: $(test_group$*)" @cd build/tests/$@ && $(TEST_JVM) org.junit.runner.JUnitCore $(test_group$*) +.PHONY: sanity $(sanity_groups) +$(sanity_groups): sanity_group%: $(test_classes) $(TEST_SYS) $(RELEASE_SYS) $(RELEASE_CRT) + @$(TEST_JVM) com.seaofnodes.simple.TestWorkspace $@ $(CPU_ABI) + @echo "testing $@: $(sanity_group$*)" + @cd build/tests/$@ && $(TEST_JVM) org.junit.runner.JUnitCore $(sanity_group$*) + +sanity: $(sanity_groups) tests_raw0 tests_raw1 fuzzer tests_lattice0 tests_lattice1 tests_lattice2 tests_lattice3 + @echo "All sanity checks passed" + # One test method (or the whole class when METHOD is omitted). CLASS ?= Chapter25Test METHOD ?= @@ -165,7 +184,9 @@ METHOD ?= test: $(main_classes) $(test_classes) $(RELEASE_SYS) $(RELEASE_CRT) @$(TEST_JVM) com.seaofnodes.simple.TestRunner "$(CLASS)" "$(METHOD)" -tests: $(test_groups) tests_sys fuzzer tests_alone tests_raw1 tests_raw0 +# At -j8, start the remaining chapter cohorts before the short lattice parts +# so their native links overlap the earlier groups instead of forming a tail. +tests: $(test_groups) tests_sys fuzzer tests_raw1 tests_raw0 tests_alone @echo "All tests passed" diff --git a/chapter32/README.ja.md b/chapter32/README.ja.md index ac57b417..30d3c26c 100644 --- a/chapter32/README.ja.md +++ b/chapter32/README.ja.md @@ -15,6 +15,12 @@ - 高価な検証の既定値を log 8 から log 10 に変更し、インライン化の各途中段階で繰り返していたスケジュール検証を削減します。 - 外部状態を読む依存関係を不透明な引数に限定し、定数引数の削除による無関係な利用側への通知を減らします。 呼び出しの切り離しで変更したパラメータは明示的に再処理します。 +- IFG の live-out マップと作業領域を関数ごとに持ち、スピルによる再試行の間だけ再利用します。 + 過去のコンパイルの基本ブロックを保持し続けることがなくなります。 + スピル候補の評価に使う関数の大きさも、彩色の試行ごとに一度だけ計算します。 +- ロードを命令に組み込めるか調べる走査では、訪問済みノードを ID の BitSet で管理します。 + パック値のヒストグラムはコメントアウトし、通常のコンパイルでは収集しません。 + ELF の `.simple` セクションのサイズと内訳も測定し、今後の形式改善の基準にします。 測定ではワークリストからの peephole 呼び出しが約446万回から370万回へ、17.2%減少しました。 詳細な測定条件、実装の説明、残る調査対象は[英語版](README.md)を参照してください。 diff --git a/chapter32/README.md b/chapter32/README.md index d7ca40db..467b1792 100644 --- a/chapter32/README.md +++ b/chapter32/README.md @@ -4,304 +4,209 @@ English | [日本語](README.ja.md) [Previous: Chapter 31 — Software Drawing, Time, and Graphical Games](../chapter31/README.md) -Chapter 31 completes the graphics, games, and library work. This chapter keeps -that language and those programs, then investigates the cost of compiling and -testing them. Larger programs have made repeated graph walks, unnecessary -worklist visits, and uneven test parallelism visible in the test runtime. - -The starting changes address four costs: test JVM scheduling, scratch-state -cleanup in type queries, expensive verification, and overly broad optimizer -notifications. Each change keeps the existing native and evaluator coverage. - -## Measure the work before changing it - -A test suite includes Java startup, JIT compilation, assertions, compiler -passes, native compiler/linker subprocesses, and execution of generated code. -Timing the suite alone does not identify which part is growing. Likewise, -adding the timings of parallel JVMs does not give elapsed time. - -The investigation used JFR and temporary counters around compiler phases, -`_iter.iterate()`, expensive checks, and native subprocesses. Counters separate -worklist peepholes from the extra peepholes performed by verification. A -separate sample records the first accepted enqueue and follows it until the -node is popped, relating a null result to the code that scheduled the visit. -Duplicate pushes while a node is already queued are coalesced by the worklist. - -Use identity maps for bookkeeping keyed by Nodes. `Node.hashCode()` participates -in GVN locking; an ordinary HashMap used by a profiler can change compiler state. -The investigation helpers stay outside the production compiler. - -## Give independent tests independent JVMs - -The older Makefile ran chapter cohorts in parallel, but put the remaining tests -into one JVM. That last process became the long tail of `make -j 8 tests`. -The [Makefile](Makefile) divides those tests into eight measured groups, keeping -each class and its fixtures together. New test classes join the last group -automatically, so the grouping cannot silently omit them. - -Each JVM defaults to `-XX:ActiveProcessorCount=2`. This sizes its JIT and GC -thread pools for a share of the machine instead of letting every concurrent -JVM size itself for all cores. The limit does not pin the process to CPUs. - -Native tests create objects and executables with common filenames. -[TestWorkspace](src/test/java/com/seaofnodes/simple/TestWorkspace.java) gives -each group a working directory under `build/tests`, refreshing its fixtures -and native libraries before the run. Classes and JARs are shared through an -absolute classpath. The groups can then run without overwriting each other's -generated programs. - -The exhaustive [lattice test](src/test/java/com/seaofnodes/simple/TypeTest.java) -partitions its outer type loop across four JVMs. Together they check every -pair and triple. Separate processes also isolate the mutable type interning -and traversal state. A direct JUnit or IDE invocation still runs the complete -lattice test in one JVM; part zero of the Make run also runs the other type tests. - -## Shallow type queries need no recursive scratch state - -[Type.isConstant and Type.isFinal](src/main/java/com/seaofnodes/simple/type/Type.java) -used to wrap their queries in `recurOpen`/`recurClose`. That made sense when -constant detection could follow pointers into cyclic structures. The current -rules stop at the pointer: constantness tests its identity, and finality tests -its access qualifier. Struct queries inspect their fields without following -pointer referents. - -These queries therefore do not need to clear the shared traversal map, mark -visited structs, or treat a repeated visit as success. Removing that bookkeeping -keeps the existing answers and avoids repeated scratch-state cleanup. Recursive -operations that actually traverse or construct cyclic types retain their own -recursion machinery. Type tests cover repeated fields, cyclic singleton -pointers, and finality qualifiers. - -## Sample expensive verification - -The optimizer checks a strong invariant: a live node is either on the worklist -or cannot make progress. Testing it walks the entire graph and tries peepholes -again. `schedulableUses` also walks the graph to check that inputs and uses admit -a legal schedule. Running such checks too often can dominate the transformation -being checked. - -[CodeGen](src/main/java/com/seaofnodes/simple/codegen/CodeGen.java) now defaults -`simple.assert.expensive` to log 10 rather than 8, sampling one eligible step in -1,024. [IterPeeps](src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java) -checks scheduling at the end of the completed fixed point instead of after -every intermediate inlining batch. Entry, periodic, and phase checks remain. -Ordinary assertions remain enabled in the test harness. - -The verification-only change left the measured worklist visits identical at -4,463,457. Assertion-only peepholes fell from 5,295,983 to 1,910,132, and measured -checking time inside `iterate()` fell from 12.36 to 4.08 seconds. - -## Wake nodes for changes they actually read - -`listener.addDep(source)` puts the listener on the source's dependency list. -Later, `source.moveDepsToWorklist()` schedules those listeners. Notifications -can follow type changes, edge edits, or use-count changes. An unnecessary -subscription can therefore cause many visits even if the source's type never -changes. - -### Outside state is needed only for opaque arguments - -[SummaryNode](src/main/java/com/seaofnodes/simple/node/SummaryNode.java) and -[CallNode](src/main/java/com/seaofnodes/simple/node/CallNode.java) requested -`Start.outside` unconditionally while computing exposed escapes. That request -registers a dependency on Start. Deleting constants changes Start's users and -can wake every registered summary. - -But `TypeMem.escapesFrom(argument, outside)` consults `outside` only for an -opaque argument. The callers now use that same condition before requesting -outside state. Dependencies on argument types remain: if an argument later -refines to an opaque type, it wakes the reader, which installs the needed Start -dependency. The return-state dependencies of external CallEnds remain intact. - -### Removing a constant argument should not wake unrelated callers - -[RegionNode.removeDeadPath](src/main/java/com/seaofnodes/simple/node/RegionNode.java) -used to schedule every user of each removed Phi input. During inlining, common -constants can be shared by parameters throughout the program. Removing one -argument caused a broadcast to many unrelated functions. - -For a constant input, the code now schedules the changed Phi. Nonconstant -inputs retain the broader notification, and the Phi's outputs still receive -their notification. - -Stronger verification exposed a dependency on the old broadcast: -`CallNode.unlink` removed parameter inputs without scheduling the edited Parms. -Those nodes need another visit even when their types stay unchanged, because -editing their inputs removes them from GVN. Unlink now queues the parameters it -actually edits. A focused regression checks this independently of later cloning. - -### Results and remaining work - -With verification held at the new setting, the two filters produced: - -| Worklist peepholes | Before | After | -|---|---:|---:| -| SummaryNode | 455,186 | 50,623 | -| ParmNode | 700,827 | 373,604 | -| All nodes | 4,463,457 | 3,695,609 | -| Null returns | 4,140,886 | 3,371,682 | -| Null percentage | 92.8% | 91.2% | - -That is 17.2% fewer live worklist visits. Measured `iterate()` wall time fell -from 14.24 to 11.97 seconds; the serial profiled suite fell from 98.53 to 93.37 -seconds. These are individual Windows/JDK 21 runs with JFR and enqueue sampling, -not portable performance guarantees. The baseline had 792 test methods; the -final run included two additional regressions. The parallel uninstrumented -Make run took 28.8 seconds and passed 797 executions, including the additional -lattice partitions. The full suite also passed at log 8, with focused tests -at log 1. These measurements were taken before creating the chapter snapshot. - -A null return does not always mean wasted work: `peepholeOpt` can reinsert an -unlocked node into GVN and still return null. Some null-returning nodes are then -killed as unused. Already-dead pops are counted separately from this table. - -Dependency notifications accounted for only 28% of sampled baseline null-return -visits. Most came from direct scheduling. The largest remaining candidates are -MemPhi input requeues during Lower and IfNode dominator dependencies. The latter -also wake on use-count changes. Any narrower filter must preserve the topology -and use-count changes that actually enable a rewrite; deleting subscriptions -just because a sample showed no progress is not enough. - -### MemPhi and IfNode follow-up - -The next trace records the notifying node as well as the enqueue stack. -BulkMemPhi splitting and MemMerge cleanup repeatedly queue precise memory Phis -as inputs of successful peepholes. Removing memory Phis also changes a Region's -users, waking IfNodes which subscribed while walking the dominator chain. -Unlinking callers produces similar notifications from CallNodes. - -Two small filters are retained. A type-only update of a user no longer queues -an already-used, stable MemPhi input. New or edited inputs and first-use Phis -remain eligible; replacement and edge-edit notifications retain their existing -behavior. `IfNode.idealize` searches dominators only when both branches remain -possible. Known branches already fold through CProj and need no new distant -subscriptions. - -On the same 794-method profiling sweep, MemPhi visits fell from 474,510 to -469,866, IfNode visits from 254,787 to 249,609, and total visits from 3,695,609 -to 3,661,560. The total reduction is 0.9%; whole-suite elapsed times of 91.88 -and 91.64 seconds do not establish a meaningful timing improvement. Existing -spill expectations still pass. One graph expectation loses a redundant integer -narrowing; both branches also have execution checks. - -A broader experiment separated dependency use-count notifications from type -and input-edge notifications, and filtered more MemPhi use-count revisits. -That version changed optimizer ordering enough to increase the Sieve spill -score from 216 to 343 and the forward-field example from 23 to 31. It is not -enabled: reducing compiler work is not a reason to silently raise code-quality -expectations. The broader filter also requires notifying a node's dependents -when `delDef` changes its inputs, rather than redundantly notifying the old -input's use-count listeners. - -In the 302-method non-chapter group, that isolated experiment reduced MemPhi -visits from 367,387 to 205,245 and IfNode visits from 144,652 to 59,185. Total -visits fell 9.7%, but elapsed time was essentially unchanged at 57.48 versus -57.75 seconds. Fewer visits alone do not demonstrate a runtime improvement. - -These measurements precede the verifier fixes below. - -### Every-step verifier fixes - -Checking every progress step exposed two bugs, both reproducible before the -MemPhi/IfNode filters: - -- `Chapter05Test.testMerge4` fails at iteration 38: replacing `Phi#44` with - `arg` changes `If#52`'s predicate and enables `Phi#75`'s guard-merge rewrite. - `matchingGuardMerge` had no dependency on that predicate comparison. It now - subscribes to the If for direct input edits and to its predicate for replacement - through `subsume`. Tests cover both notification paths. -- `Chapter15Test.testArrayLoadDominatingControl` fails at iteration 30, when a - bulk memory Phi splits into a MemMerge. The verifier treated the consuming - load's earlier range-check control as its execution block. A memory operation's - control is only a lower bound: its data inputs can force it later. The check - now includes those inputs, matching early scheduling. Regression tests accept - this legal placement and still reject a load used before its memory is ready. - -After these fixes, all 802 suite executions pass at log 8; 444 chapter tests and -34 focused worklist, scheduling, and memory tests pass at log 1. Existing spill -expectations are unchanged. - -### Dense MemMerge inputs - -`MemMergeNode` now keeps precise alias slices in a dense input list, with an -`IntHashMap` from alias to input index and a reverse array for iteration. -Alias order is preserved. Missing aliases use input 1, the bulk default. -Deletion compacts the list and rebuilds the small map; graph copies own their -maps. Bulk-Phi splitting and object loading use alias lookup rather than -assuming an alias is an input index. The existing sparse object encoding remains -compatible with the baseline compiler. - -This is deliberately a storage experiment. `_aliasLimit` retains the previous -sparse extent for encoding and fold eligibility. The old `allDefault` test -counts null holes as non-defaults; simply folding whenever the dense list is -empty introduces additional optimizations. That separate trial altered code -quality: graphical Tic-tac-toe's weighted spill score rose from 1085 to 1240 -with its rebuilt library. The retained version preserves the old folding -behavior and matches baseline peephole counts, code sizes, and spill counts on -all measured workloads. - -Against commit `8b80d94c`, the final interleaved comparison measured: - -| Workload | Compile time change | Compiler-thread allocation change | -| --- | ---: | ---: | -| sys library | -5.8% | -3.7% | -| Clock | -2.1% | -10.8% | -| Breakout | -2.9% | -6.4% | -| Graphical tic-tac-toe | -0.5% | -5.3% | -| HelloWorld | -0.6% | -4.5% | - -The timing improvement is modest; sub-percent differences are within noise. -The structural reduction is much larger. After Lower, sys's live MemMerge input -slots fall from 54,388 to 2,462, Clock's from 54,255 to 2,237, and Breakout's from -61,286 to 2,592. These are input-slot counts, not total heap measurements; the -maps and reverse arrays have their own cost. - -Measurements use Java 21, assertions at log10, two active processors, and a -256 MiB initial / 2 GiB maximum heap. The compiler runs through object export, -without gcc, linking, or execution. Isolated compiler class loaders alternate -in one JVM; six measured rounds follow three warmups for each workload. Games -read the same baseline sys objects. Time changes are medians of paired ratios; -allocation uses ThreadMXBean. Earlier separate-process runs drifted enough that -the interleaved comparison is the basis for the table. - -The full suite passes at log8; 444 chapter tests and 18 memory/import tests pass -with every-step verification. Raw measurements, saved compiler classes, and -reproduction commands are in `build/memmerge-dense/`; verification logs are in -`build/test-profile/dense-final-*.log`. - -## Build and test - -From `chapter32`, using the existing offline dependency caches: +The games and libraries from chapter 31 made both compiling and testing slow +enough to interrupt development. This chapter makes room for future work: +faster feedback for Simple's developers, and faster compilation for its users. + +| What improved | Result | +| --- | --- | +| Repeated compilation | 29–79% less compile time for the large workloads below | +| Development testing | Roughly 30 seconds for a full run → 8.8 seconds for sanity checks; the full suite now takes 22.8 seconds | +| IR stored in ELF files | 21.9% smaller across 26 objects | + +The compiler figures isolate the allocator-scratch fix in repeated compiles. +The testing gain includes a deliberate coverage tradeoff. The sections below +explain what changed and what each measurement covers. + +## Faster development of Simple + +### Measure the work and the wait + +A test run starts JVMs, compiles Java methods, runs the compiler, checks +assertions, links native programs, and executes them. In one serial profiling +run, compiler phases took 29.7 seconds and 153 GCC calls took another 29.8, +mostly linking. Compiler optimization could address only part of the cost. + +Parallel testing has the "tallest pole" problem: we wait for the last worker. +The [Makefile](Makefile) now splits the former catch-all JVM into balanced +groups, with private native outputs. Each JVM sizes its JIT and GC pools for +two processors. Eight Make jobs beat both four and sixteen on this host. + +| Command | Coverage | Warm elapsed time | +| --- | --- | ---: | +| `make -j8 sanity` | Full lattice, chapter/backend tests, saved fuzzer regressions, focused compiler tests | 8.8 s | +| `make -j8 tests` | All of the above, plus remaining library, application, and CLI integration | 22.8 s | + +These runs use Windows, Java 21, and a 10-core/20-thread i9-10900K, with builds +already up to date. They execute 680 and 819 tests respectively, including the +lattice partitions. Assertions stay enabled. Use the full suite before finishing +a change, especially when working on libraries or interfaces omitted by `sanity`. + +Routine savings came from cheaper fixtures: loop over the division/remainder +matrix instead of generating 200 conditional checks; share native programs +between formatting cases; compile two small modules for an assembly-dump test +instead of all of `sys`. The full suite's GCC calls fell from 153 to 141. + +### Keep the full lattice, with fewer repetitions + +The [lattice test](src/test/java/com/seaofnodes/simple/TypeTest.java) stays in +the sanity run. Compiler transformations depend on its laws, so we reduced +repetition rather than sampling fewer types. + +First, format assertion messages only on failure. Doing that inside the cubic +loop reduced the standalone run from 10.6 to 4.5 seconds. Next, cache pairwise +meets and joins, computing both operand orders before checking commutativity. + +Associativity formerly visited all `n^3` ordered triples. Now it visits +`i <= j <= k`, including repeated operands: `n(n+1)(n+2)/6` iterations. Each +visit compares all six results: -```sh -make -j 8 release -make -j 8 tests_nographics -make test CLASS=TypeTest ``` +(a & b) & c c & (a & b) +(a & c) & b b & (a & c) +(b & c) & a a & (b & c) +``` + +Once the original pairs commute, the six original associativity equalities +connect these results in a cycle. Comparing them to one common result checks +the same property. We must retain both operand orders involving intermediate +types: `a & b` may be outside the gathered set, so its commutativity has not +yet been established. -On a fresh checkout, run `make libs` once while online to populate the caches. -The ordinary builds and tests do not download dependencies or open windows. +All comparable-pair monotonicity checks remain. The complete unpartitioned +TypeTest now takes about 0.7 seconds. Make still partitions it across four +JVMs, each with private type-interning state. -Override JVM sizing with `TEST_JAVA_OPTS`. For example: +## Faster compilation for Simple users + +### Wake nodes when something relevant changes + +`listener.addDep(source)` asks to wake a node when the source changes. +Registering extra dependencies is easy; paying for them happens later. + +Tracing enqueues exposed two broad notifications. Calls and summaries read +`Start.outside` even when their arguments did not need it, subscribing them to +unrelated changes. They now read it only for opaque arguments. Removing a +constant Phi input also woke every user of that constant throughout the +program. It now queues the changed Phi. + +These filters cut worklist visits from 4.46 million to 3.70 million, or 17.2%. +Time inside `iterate()` fell from 14.24 to 11.97 seconds. Further MemPhi and +IfNode filters reduced visits slightly without a measurable timing gain. +Fewer visits alone are not proof of a faster compiler. + +Broad notifications can hide missing dependencies. Stronger verification found +nodes that had relied on accidental wakeups, including a Phi whose guard-merge +rewrite became possible after an If predicate changed. Checking every progress +step isolated the peephole that exposed the missing dependency. + +Normal runs sample expensive checks every 1,024 eligible steps, retaining entry +and completed-phase checks. Use `-Dsimple.assert.expensive=1` to check every +progress step while diagnosing a failure. Ordinary assertions remain enabled. + +### Give scratch data the lifetime of the work + +[RegAlloc](src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java) already +allocated one function at a time, but its interference-graph helper retained +basic-block keys from every previous allocation. Each `sys` compile added +another 2,558 keys to clear on later runs. + +Each function now owns its [IFG](src/main/java/com/seaofnodes/simple/codegen/IFG.java) +scratch maps. They survive spill retries, then become unreachable when allocation +finishes. Spill scoring also computes the function's area once per coloring +attempt instead of walking the blocks for each candidate. + +| Program | Before | After | +| --- | ---: | ---: | +| `sys` library | 1,290 ms | 913 ms | +| Clock | 537 ms | 279 ms | +| Breakout | 1,007 ms | 609 ms | +| Graphical tic-tac-toe | 1,362 ms | 292 ms | + +These medians isolate that change: six measured compiles after three warmups, +alternating baseline and changed compilers, with the same library and assertions +enabled. They include object export but exclude linking. The old compiler +accumulated keys during warmup too; this measures repeated compilation, not +fresh command-line startup. Machine-code bytes matched in all 26 objects checked. + +### Remove empty space and unnecessary allocation + +[MemMergeNode](src/main/java/com/seaofnodes/simple/node/MemMergeNode.java) +used alias numbers as input indices, leaving mostly null slots supplied by +the default memory value. A dense list plus an alias-to-input map cut `sys`'s +live MemMerge input slots from 54,388 to 2,462. That change alone reduced its +compile time by 5.8%, while preserving folding behavior and generated code. + +Other savings were straightforward: remove recursive scratch-state setup from +the shallow `isConstant` and `isFinal` queries; use node-ID BitSets for load-fold +visits; stop collecting a packed-value histogram left over from profiling. +The latter two changes reduced `sys` compiler-thread allocation from 119.6 to +69.4 MiB and median compile time from 1,017 to 942 ms. These are separate +comparisons, not cumulative chapter-wide timings. + +### Make saved compiler state smaller + +ELF's `.simple` section stores reloadable IR, declarations, and import metadata. +It occupied 79% of the measured `sys` objects. Three encoding changes removed +avoidable overhead: gradual growth for packed integers, explicit MemMerge +alias/input pairs instead of default holes, and a wider compact encoding for +singleton function IDs. Strings retain raw UTF-8 bytes. + +| `.simple` payload | Before | After | Reduction | +| --- | ---: | ---: | ---: | +| `sys`, all 22 modules | 469,881 bytes | 368,694 bytes | 21.5% | +| Clock | 43,854 bytes | 31,906 bytes | 27.2% | +| Breakout | 80,950 bytes | 62,139 bytes | 23.2% | +| Graphical tic-tac-toe | 44,353 bytes | 35,961 bytes | 18.9% | +| HelloWorld | 14,635 bytes | 11,523 bytes | 21.3% | + +Across these 26 objects, the payload shrank by 143,450 bytes, or 21.9%, with +identical machine code. Compile timings showed no consistent improvement; +the demonstrated gain is smaller saved compiler state. + +## Keep the generated code good + +Changing worklist order can change rewrites and register allocation. Some +broader notification filters increased register copies, so we did not keep +them. Judge a compiler speedup by compile time, memory use, and generated code +together. + +Correctness fixes uncovered here belong in their teaching chapters: +[Phi factoring after strength reduction in chapter 5](../chapter05/README.md#factoring-after-strength-reduction), +and shared class receivers in [chapter 28a](../chapter28a/README.md#globals-use-the-same-receiver-as-fields) +and [chapter 28b](../chapter28b/README.md). + +## Build and use this chapter + +From `chapter32`, populate the dependency cache once with `make libs` if needed. +Ordinary builds use that cache and do not download dependencies. ```sh -make -j 4 tests_nographics TEST_JAVA_OPTS=-XX:ActiveProcessorCount=4 -make test CLASS=EscapeFlowTest "TEST_JAVA_OPTS=-XX:ActiveProcessorCount=2 -Dsimple.assert.expensive=1" +make -j8 release +make -j8 sanity +make -j8 tests ``` -Log 1 checks every progress step; log 8 restores the preceding sampling rate; -log 0 disables these expensive checks while retaining ordinary assertions. +For a fully headless full run, use `make -j8 tests_nographics`. It disables the +optional MiniFB and miniaudio backends. The packed IR header changes from `C0DE` +to `C0D2`; the reader rejects the older format. Run `make clean` before +`make -j8 release` to rebuild old objects, and rebuild any separately maintained +Simple libraries too. -## Language, libraries, and examples - -The [grammar and parser map](docs/32-grammar.md) describes this snapshot. -Language and library additions are taught in [Chapter 31](../chapter31/README.md). -Their implementations and runnable examples are also present here: +Run one class, or enable every-step verification for a focused investigation: -- [Examples and launch commands](docs/examples/README.md), including Clock, - Breakout, and graphical tic-tac-toe. -- [Drawing](src/main/smp/sys/draw/README.md), [window/input](src/main/smp/sys/gfx.md), - [audio](src/main/smp/sys/audio.md), and [time](src/main/smp/sys/time/README.md). -- [Math and intrinsics](../chapter31/README.md#math-support-and-intrinsics). +```sh +make test CLASS=TypeTest +make test CLASS=WorklistTest "TEST_JAVA_OPTS=-XX:ActiveProcessorCount=2 -Dsimple.assert.expensive=1" +``` -Future compiler and language proposals remain in the [roadmap](../docs/roadmap.md). +The [grammar and parser map](docs/32-grammar.md) describes this snapshot. +[Chapter 31](../chapter31/README.md) teaches its language and library additions; +the [examples](docs/examples/README.md) include launch commands for the games. +Library references live with [drawing](src/main/smp/sys/draw/README.md), +[window/input](src/main/smp/sys/gfx.md), [audio](src/main/smp/sys/audio.md), and +[time](src/main/smp/sys/time/README.md). Further projects belong in the +[roadmap](../docs/roadmap.md). + +Use the fast checks while editing. Run the full suite before finishing, and +turn up verification when a failure needs a closer look. diff --git a/chapter32/docs/32-grammar.md b/chapter32/docs/32-grammar.md index 2628f566..4a794341 100644 --- a/chapter32/docs/32-grammar.md +++ b/chapter32/docs/32-grammar.md @@ -69,6 +69,7 @@ constructorParameter : type '^'? bindingModifier? IDENTIFIER ; // A method is an ordinary fixed function binding in a struct definition. // The compiler supplies self; it is not written in parameterList. // Function types and expressions both receive their implicit receiver here. +// Global functions use their owning class singleton as self. methodDeclaration : 'val' bindingModifier? memberName '=' functionExpression ';' ; memberName : IDENTIFIER | primitiveType ; @@ -254,10 +255,11 @@ one-pass IR builder: - A statement beginning with `{` might be a block or a function-type binding. `Declarations` and `Types` use speculative parsing and cursor restore; qualified type lookup also stops before a suffix that belongs to an expression. -- Bare assignment, field assignment, and compound updates share the grammar's - precedence but use different IR paths. `References` decides between an SSA - local, a constructor field's local value, and an actual memory access. A - function-valued field may also supply an implicit receiver to a call. +- `References` resolves bare fields through their receiver, so assignments, + reads, and updates share the field-access path. Locals use SSA; class + initializer declarations retain their Scope values until initializer exit. + Global functions receive their owning class singleton as `self`, including + when invoked through a callback. Instance methods receive their object. - `for` updates are scanned first and parsed after the body, where their effects belong. Explicit constructor bodies are scanned first and parsed after field discovery, so later fields have local slots. Both use `Lexer.skipTo`, which diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java index 6ad7c0ad..a027263f 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -8,18 +8,20 @@ import java.util.BitSet; import java.util.IdentityHashMap; // Interference Graph -abstract public class IFG { +public class IFG { // Interference Graph Support + // Scratch for one function, reused across its spill retries. // Map from a Basic Block to Live-Out: {a map from a Live Range to a Def} - private static final IdentityHashMap<CFGNode,IdentityHashMap<LRG,Node>> BBOUTS = new IdentityHashMap<>(); - static void resetBBLiveOut() { - for( IdentityHashMap<LRG,Node> bbout : BBOUTS.values() ) + private final IdentityHashMap<CFGNode,IdentityHashMap<LRG,Node>> _bbouts = new IdentityHashMap<>(); + private void resetBBLiveOut() { + for( IdentityHashMap<LRG,Node> bbout : _bbouts.values() ) bbout.clear(); } - static final IdentityHashMap<LRG,Node> TMP = new IdentityHashMap<>(); + private final IdentityHashMap<LRG,Node> _tmp = new IdentityHashMap<>(); - // Inteference Graph: Array of Bitsets + // Interference Graph: Array of Bitsets. Reuse capacity across functions; + // these contain only live-range numbers, not references to the graph. static final Ary<BitSet> IFG = new Ary<>(BitSet.class); static void resetIFG() { for( BitSet bs : IFG ) @@ -42,10 +44,10 @@ abstract public class IFG { } - private static final Ary<CFGNode> WORK = new Ary<>(CFGNode.class); - static void pushWork(CFGNode bb) { - if( WORK.find(bb) == -1 ) - WORK.push(bb); + private final Ary<CFGNode> _work = new Ary<>(CFGNode.class); + private void pushWork(CFGNode bb) { + if( _work.find(bb) == -1 ) + _work.push(bb); } // ------------------------------------------------------------------------ @@ -65,20 +67,20 @@ abstract public class IFG { // - At block head, "push" the new live-out to prior blocks. // - - If they pick up new live-outs, put them on the worklist. - public static boolean build( int round, RegAlloc alloc ) { + public boolean build( int round, RegAlloc alloc ) { // Reset all to empty resetBBLiveOut(); resetIFG(); - WORK.clear(); + _work.clear(); // Last block has nothing live out for( CFGNode bb : alloc._cfg ) if( bb.blockHead()) - WORK.push( bb ); + _work.push( bb ); // Process blocks until no more changes - while( !WORK.isEmpty() ) - do_block(round,alloc,WORK.pop()); + while( !_work.isEmpty() ) + do_block(round,alloc,_work.pop()); if( alloc.success() ) convert2DAdjacency(alloc); @@ -86,12 +88,12 @@ abstract public class IFG { } // Walk one block backwards, compute live-in from live-out, and build IFG - static void do_block( int round, RegAlloc alloc, CFGNode bb ) { + private void do_block( int round, RegAlloc alloc, CFGNode bb ) { assert bb.blockHead(); - IdentityHashMap<LRG,Node> live_out = BBOUTS.get(bb); - TMP.clear(); + IdentityHashMap<LRG,Node> live_out = _bbouts.get(bb); + _tmp.clear(); if( live_out != null ) - TMP.putAll(live_out); // Copy bits to temp + _tmp.putAll(live_out); // Copy bits to temp // A backwards walk over instructions in the basic block for( int inum = bb.nOuts()-1; inum >= 0; inum-- ) { @@ -118,14 +120,14 @@ abstract public class IFG { mergeLiveOut(alloc,bb,0); } - private static void do_node(RegAlloc alloc, Node n) { + private void do_node(RegAlloc alloc, Node n) { // Defining means killing live LRG LRG lrg = alloc.lrg(n); if( lrg != null ) { // Check for def-side self-conflict live ranges. These must split, // and only happens during the first round a particular LRG splits. selfConflict(alloc,n,lrg); - TMP.remove(lrg); // Kill def + _tmp.remove(lrg); // Kill def } // Phis use and define the same live range, i.e. these LRGs already @@ -141,7 +143,7 @@ abstract public class IFG { // Interfere n with all live if( lrg!=null ) { // Interfere n with all live - for( LRG tlrg : TMP.keySet() ) { + for( LRG tlrg : _tmp.keySet() ) { assert tlrg.leader(); // Skip self if( lrg != tlrg && @@ -177,7 +179,7 @@ abstract public class IFG { selfConflict(alloc,def,lrg1); // All operands are live together, regardless of their input order. - TMP.put(lrg1,def); + _tmp.put(lrg1,def); } // Check fixed-register uses after gathering every operand. An indirect @@ -191,9 +193,9 @@ abstract public class IFG { RegMask ni_mask = m.regmap(i); if( ni_mask!=null && ni_mask.size1() ) { // Must-use single register // Search all current live - for( LRG tlrg : TMP.keySet() ) { + for( LRG tlrg : _tmp.keySet() ) { assert tlrg.leader(); - Node live = TMP.get(tlrg); + Node live = _tmp.get(tlrg); if( live != def && live instanceof MachNode lmach && lmach.outregmap().overlap(ni_mask) ) { // Deny the register, since it absolutely must be used here if( !tlrg.clr(ni_mask.firstReg()) ) @@ -210,15 +212,15 @@ abstract public class IFG { // Single-register defines *must* have their register; other live ranges // *must* avoid this register, so instead of interfering we remove the // single register from the other rmask. - private static void kills( RegAlloc alloc, MachNode m ) { + private void kills( RegAlloc alloc, MachNode m ) { RegMask killMask = m.killmap(); if( killMask==null ) return; // Kill registers with all live - for( LRG tlrg : TMP.keySet() ) { + for( LRG tlrg : _tmp.keySet() ) { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - Node live = TMP.get(tlrg); + 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() ) @@ -231,8 +233,8 @@ abstract public class IFG { // Check for self-conflict live ranges. These must split, and only happens // during the first round a particular LRG splits. - private static void selfConflict(RegAlloc alloc, Node n, LRG lrg) { - selfConflict(alloc,n,lrg,TMP.get(lrg)); + private void selfConflict(RegAlloc alloc, Node n, LRG lrg) { + selfConflict(alloc,n,lrg,_tmp.get(lrg)); } private static void selfConflict(RegAlloc alloc, Node n, LRG lrg, Node prior) { if( prior!=null && prior != n ) { @@ -242,17 +244,17 @@ abstract public class IFG { } } - // Merge TMP into bb's live-out set; if changes put bb on WORK - private static void mergeLiveOut( RegAlloc alloc, CFGNode priorbb, int i ) { + // Merge _tmp into bb's live-out set; if changes put bb on _work + private void mergeLiveOut( RegAlloc alloc, CFGNode priorbb, int i ) { CFGNode bb = priorbb.cfg(i); if( bb == null ) return; // Start has no prior while( !bb.blockHead() ) bb = bb.cfg0(); // Lazy get live-out set for bb - IdentityHashMap<LRG, Node> lrgs = BBOUTS.computeIfAbsent( bb, k -> new IdentityHashMap<>() ); + IdentityHashMap<LRG, Node> lrgs = _bbouts.computeIfAbsent( bb, k -> new IdentityHashMap<>() ); - for( LRG lrg : TMP.keySet() ) { - Node def = TMP.get(lrg); + for( LRG lrg : _tmp.keySet() ) { + Node def = _tmp.get(lrg); // Effective def comes from phi input from prior block if( def instanceof PhiNode phi && phi.cfg0()==priorbb ) { assert i!=0; @@ -306,6 +308,9 @@ abstract public class IFG { // If there's no spare color we'll have to spill this at-risk live range. public static boolean color(int round, RegAlloc alloc) { + // Coalescing is finished; splitting may change this area next round. + FunNode fun = alloc._cfg.at(0).fun(); + int functionArea = functionArea(fun,alloc); int maxlrg = alloc._LRGS.length, nlrgs=0; for( int i=1; i<maxlrg; i++ ) if( alloc._LRGS[i] != null ) @@ -325,6 +330,7 @@ abstract public class IFG { for( int i=0, j=0; i<maxlrg; i++ ) { LRG lrg = alloc._LRGS[i]; if( lrg==null ) continue; // Unified lrgs are null here + assert lrg._fun==fun; color_stack[j++] = lrg; if( lrg.lowDegree() ) swap(color_stack, swork++, j-1); } @@ -332,7 +338,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,alloc); + pickColor(color_stack,sptr,swork,functionArea); // Pick a trivial lrg, and (temporarily) remove from the IFG. LRG lrg = color_stack[sptr++]; @@ -388,10 +394,10 @@ abstract public class IFG { } // Pick LRG from color stack - private static void pickColor(LRG[] color_stack, int sptr, int swork, RegAlloc alloc) { + private static void pickColor(LRG[] color_stack, int sptr, int swork, int functionArea) { // Out of trivial colorable, pick an at-risk to pull if( sptr==swork ) - swap(color_stack,sptr,pickRisky(color_stack,sptr,alloc)); + swap(color_stack,sptr,pickRisky(color_stack,sptr,functionArea)); // 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 @@ -426,12 +432,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, RegAlloc alloc ) { + private static int pickRisky( LRG[] color_stack, int sptr, int functionArea ) { int best=sptr; - int bestScore = pickRiskyScore(color_stack[best],alloc); + int bestScore = pickRiskyScore(color_stack[best],functionArea); for( int i=sptr+1; i<color_stack.length; i++ ) { if( bestScore == 1000000 ) return best; // Already max score - int iScore = pickRiskyScore(color_stack[i],alloc); + int iScore = pickRiskyScore(color_stack[i],functionArea); if( iScore > bestScore ) { best = i; bestScore = iScore; } } @@ -446,16 +452,16 @@ 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, RegAlloc alloc ) { + private static int pickRiskyScore( LRG lrg, int functionArea ) { // 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), + return areaScore(functionArea, 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), + return areaScore(functionArea, splitCost(lrg._splitDef,lrg._splitUse)); // Pick single-def clonables that are not right next to their single-use. @@ -465,7 +471,7 @@ abstract public class IFG { Node use = ((Node)lrg._machUse); CFGNode cfg = def.cfg0(); int area = cfg != use.cfg0() - ? functionArea(lrg._fun,alloc) + ? functionArea : cfg._outputs.find(use)-cfg._outputs.find(def)-1; // A single-use function address can move next to its use without // adding an instruction. Prefer that to saving a callee-save diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 303fd355..c3be4b71 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -213,8 +213,9 @@ public class RegAlloc { } private void allocateFunction() { + IFG ifg = new IFG(); _deferredLoopSelf.clear(); - for( byte round=0; !graphColor(round); round++ ) { + for( byte round=0; !graphColor(round,ifg); round++ ) { split(round); if( round >= 10 ) { FunNode fun = _cfg.at(0).fun(); @@ -281,7 +282,7 @@ public class RegAlloc { return cfg==null ? null : cfg.fun(); } - private boolean graphColor(byte round) { + private boolean graphColor(byte round, IFG ifg) { _failed.clear(); _lrgs.clear(); _lrg_num = 1; @@ -291,7 +292,7 @@ public class RegAlloc { // Build Live Ranges BuildLRG.run(round,this) && // if no hard register conflicts // Build Interference Graph - IFG.build(round,this) && // If no self conflicts or uncolorable + ifg.build(round,this) && // If no self conflicts or uncolorable // Conservative coalesce copies Coalesce.coalesce(round,this) && // Color attempt diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index e1aee9aa..9c43e029 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -103,8 +103,10 @@ public class Serialize { Type startType = TypeTuple.make(Type.CONTROL,stopType.mem(),((StartNode)nodes.at(0)).arg()); BAOS baos = new BAOS(); - // A - Print the C0DE header. The format is not versioned yet. - baos.write('C').write('0').write('D').write('E'); + // A - Print the C0DE header; last byte is the version number. + // Format 2: gradual packed ints, UTF-8 strings, sparse MemMerge edges, + // and wider singleton function IDs. Reject old cached objects clearly. + baos.write('C').write('0').write('D').write('2'); // Count unique Types var types = new HashMap<Type,Integer>(); @@ -265,10 +267,12 @@ public class Serialize { } // Write out the input indices packed. for( Node n : nodes ) { - int count = n instanceof MemMergeNode mem ? mem.packedSize() : n.nIns(); + int count = n.nIns(); for( int j=0; j<count; j++ ) { if( !writeInput(n,j,anodes) ) continue; - Node def = n instanceof MemMergeNode mem ? mem.packedInput(j) : n.in(j); + if( n instanceof MemMergeNode mem && j>=2 ) + baos.packed2(mem.aliasAt(j)); + Node def = n.in(j); Integer idx = def==null ? Integer.valueOf(0) : anodes.get(def); // Imported function constants retain their symbol, not a body. if( idx==null && n instanceof FunPtrNode && j==1 ) idx=0; @@ -331,7 +335,7 @@ public class Serialize { Type.TAGOFFS(); // A - Read a header - if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='E' ) + if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='2' ) throw new IllegalArgumentException("Unsupported serialized IR format; rebuild the object file"); // B - Packed read of #strings, then strings @@ -364,7 +368,7 @@ public class Serialize { String[] strs = elf._strs; if( strs == null ) { // A - Read a header - if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != 'E' ) + if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != '2' ) throw new IllegalArgumentException( "Unsupported serialized IR format; rebuild the object file" ); // B - Packed read of #strings, then strings @@ -503,14 +507,13 @@ public class Serialize { for( Node n : nodes ) { int len = n instanceof MemMergeNode mem ? mem.readSize() : n.nIns(); for( int i = 0; i<len; i++ ) { + int fileAlias = n instanceof MemMergeNode && i>=2 ? bais.packed2() : 0; int idx = bais.packed2(); Node def = idx==0 ? null : nodes.at(idx-1); - // 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. + // Remap only explicit slices; omitted aliases use the default. if( n instanceof MemMergeNode mem && i>=2 ) { if( def==null ) continue; - int alias = i>=GlobalBits.RESERVED ? aliases.map(fileAliases,i) : i; + int alias = aliases.map(fileAliases,fileAlias); mem.alias(alias,def); } else n.setDefX(i,def); // Call's output[0] is always the CallEnd diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/CallNode.java index 3b2dc75b..5506621b 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -7,6 +7,7 @@ import com.seaofnodes.simple.parser.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Iter; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypePtr; import com.seaofnodes.simple.type.TypeMemPtr; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeMem; @@ -95,13 +96,15 @@ public class CallNode extends CFGNode { // A broad scalar target can refine to a function pointer during Iter. // It cannot yet promise that the call exposes nothing. if( _type!=Type.CONTROL ) return TypeMem.BOT; - if( !(fptr()._type instanceof TypeFunPtr) ) + if( !(fptr()._type instanceof TypeFunPtr tfp) ) return fptr()._type.isHigh() ? TypeMem.START : TypeMem.BOT; if( Intrinsic.pure(this) ) return TypeMem.START; if( !external() ) return TypeMem.START; Type input = dep.addDepForwards(mem())._type; TypeMem escaped = input instanceof TypeMem m ? m : input.isHigh() ? TypeMem.TOP : TypeMem.BOT; - for( int i = 2; i<nIns()-1; i++ ) { + // The class-receiver slot is absent from the ABI. The callee supplies + // its own singleton, so passing a callback does not expose our class. + for( int i = tfp.nargs()>0 && tfp.arg(0)==TypePtr.PTR ? 3 : 2; i<nIns()-1; i++ ) { Type arg = dep.addDepForwards(arg(i))._type; TypeMem outside = TypeMem.opaque(arg) ? CodeGen.CODE._start.outside(dep) : TypeMem.BOT; escaped = escaped.escapesFrom(arg,outside); @@ -182,7 +185,13 @@ public class CallNode extends CFGNode { CodeGen.CODE.add(fun).addDef(this); for( Node use : fun._outputs ) if( use instanceof ParmNode parm ) { - Node def = parm._idx==0 ? ConstantNode.seed(cend()._rpc).peephole() : arg(parm._idx); + // A class function's receiver belongs to the callee, even + // when a different class or an instance forwards its callback. + // Match its declared view: before SCCP, forward fields can + // still differ from the completed class layout. + Node def = parm._idx==0 ? ConstantNode.seed(cend()._rpc).peephole() + : parm._idx==2 && fun.sig().arg(0)==TypePtr.PTR + ? ConstantNode.seed(parm._declaredType).peephole() : arg(parm._idx); CodeGen.CODE.add(parm).addDef(def); // Linking can happen during post-SCCP inlining. Keep an RPC // Parm's cached finite set synchronized with its newly added diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index d5eaa743..a077e14b 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -24,7 +24,7 @@ public class MemMergeNode extends Node { private AryInt _aliases; private IntHashMap _aliasToInput; private int _readSize; - // Retain the old sparse extent for encoding and fold eligibility, without its holes. + // Retain the old sparse extent for fold eligibility, without its holes. private int _aliasLimit=2; public MemMergeNode(MemMergeNode mem) { super(mem); copyAliases(mem); _aliasLimit=mem._aliasLimit; } @@ -50,10 +50,8 @@ public class MemMergeNode extends Node { return input==0 ? null : in(input); } - // Preserve the existing sparse object encoding; input indices on disk are aliases. - public int packedSize() { return _aliasLimit; } + // The reader has not wired the dense inputs yet. public int readSize() { return _readSize; } - public Node packedInput(int alias) { return alias<2 ? in(alias) : explicitAlias(alias); } private void reindex() { _aliasToInput.clear(); @@ -68,18 +66,17 @@ public class MemMergeNode extends Node { } @Override public Tag serialTag() { return Tag.MemMerge; } public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { - // A memory merge always has inputs. Zero escapes a wide alias table, - // preserving every existing nonzero single-byte count. - assert nIns()>0; - baos.packed1(packedSize()<=255 ? packedSize() : 0); - if( packedSize()>255 ) baos.packed4(packedSize()); + // Keep the extent even if its last precise slice was removed. Edges + // are dense: control/default followed by explicit (alias,input) pairs. + baos.packed4(_aliasLimit); + baos.packed2(nIns()); } static Node make( BAOS bais ) { - int count=bais.packed1(); - if( count==0 ) count=bais.packed4(); + int limit=bais.packed4(), count=bais.packed2(); + assert 2<=count && count<=limit; MemMergeNode mem=new MemMergeNode(null,null); mem._readSize=count; - mem._aliasLimit=count; + mem._aliasLimit=limit; return mem; } diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 7544962f..94376086 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -122,7 +122,8 @@ public class PhiNode extends Node { // Generic "pull down op" Node progress; - if( same_op() && (progress = drop_same_op()) != null ) + Node op = factoringOp(); + if( same_op(op) && (progress = drop_same_op(op)) != null ) return progress; // If merging Phi(ZERO, guardNZ(N)) at the matching `if(N)` join, the @@ -161,10 +162,28 @@ public class PhiNode extends Node { return tested!=null && (early==null || early.dominates(r,this)) ? n : null; } + // View x<<1 as x+x when factoring mixed Add/Shl arms. Do not expand the + // graph: Add would immediately strength-reduce it again. If all arms are + // shifts, keep the ordinary shift factoring (including arbitrary counts). + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i<nIns(); i++ ) + if( in(i) instanceof AddNode add && add._mode==1 ) return add; + return op; + } + + private boolean doubled(Node n) { + return n instanceof ShlNode && addDep(n.in(2))._type==TypeInteger.TRUE; + } + + private static Node factoringInput(Node op, Node n, int j) { + return n instanceof ShlNode && op instanceof AddNode ? n.in(1) : n.in(j); + } + // Same op on all Phi paths; all ops have only the Phi as a use. // None have a control input. - private boolean same_op() { - Node op = in(1); + private boolean same_op(Node op) { if( op instanceof EscapeNode || op instanceof CFGNode || op instanceof ConstantNode || op instanceof PhiNode || op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; // A bulk Phi must split its aliases before factoring precise Stores. @@ -181,8 +200,10 @@ public class PhiNode extends Node { Node busy = null; for( int i=1; i<nIns(); i++ ) { Node n = in(i); + boolean same = op.getClass()==n.getClass() && op.eq(n); + if( !same && op instanceof AddNode add && add._mode==1 ) same = doubled(n); if( addDep(region().in(i))._type==Type.XCONTROL || - op.getClass()!=n.getClass() || n.nIns()!=op.nIns() || n.in(0)!=null || !op.eq(n) ) return false; + !same || n.nIns()!=op.nIns() || n.in(0)!=null ) return false; if( n instanceof MemOpNode mem && !mem.canDrop((MemOpNode)op,this) ) return false; // Moving a Store must remove the old effect, not duplicate it. // Allow one shared arm: the other arms disappear into the single @@ -200,21 +221,21 @@ public class PhiNode extends Node { return true; } - private Node drop_same_op() { - Node op = in(1), cp = op.copyEmpty(); + private Node drop_same_op(Node op) { + Node cp = op.copyEmpty(); cp._type = null; cp._inputs.add(null); for( int j=1; j<op.nIns(); j++ ) { - Node x = op.in(j); + Node x = factoringInput(op,in(1),j); boolean different = false; for( int i=2; i<nIns(); i++ ) - if( in(i).in(j)!=x ) different=true; + if( factoringInput(op,in(i),j)!=x ) different=true; if( different ) { Node[] ins = new Node[nIns()]; ins[0] = region(); Type t = Type.TOP; for( int i=1; i<nIns(); i++ ) { - ins[i] = in(i).in(j); + ins[i] = factoringInput(op,in(i),j); t = t.meet(ins[i]._type); } // Do not introduce an operand Phi mixing incompatible type families. diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/RegionNode.java index ca358b5a..17126f27 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -68,8 +68,9 @@ public class RegionNode extends CFGNode { for( Node use : _outputs ) { if( use instanceof PhiNode phi ) { PhiNode phi2 = phi.in(i) instanceof PhiNode phi2x && phi2x.region()==region ? phi2x : null; + // New users can require a bulk-memory input to split. for( int j=1; j<region.nIns(); j++ ) - phi.addDef(phi2==null ? phi.in(i) : phi2.in(j)); + phi.addDef(CodeGen.CODE.add(phi2==null ? phi.in(i) : phi2.in(j))); CodeGen.CODE.add(phi); } } diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/SummaryNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/SummaryNode.java index f73ba611..5b945457 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/SummaryNode.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/SummaryNode.java @@ -26,7 +26,7 @@ public class SummaryNode extends CFGNode implements MultiNode { // A library summary does not forget escapes already present in the caller. TypeMem mem = in(1)._type instanceof TypeMem m ? m : in(1)._type.isHigh() ? TypeMem.TOP : TypeMem.BOT; mem = (TypeMem)mem.meet(_state.mem()); - for( int i = 2; i<nIns(); i++ ) { + for( int i = firstArgument(); i<nIns(); i++ ) { Type arg = in(i)._type; // Only opaque arguments can hide identities supplied by outside code. TypeMem outside = TypeMem.opaque(arg) ? CodeGen.CODE._start.outside(this) : TypeMem.BOT; @@ -39,13 +39,20 @@ public class SummaryNode extends CFGNode implements MultiNode { dep.addDepForwards(this); if( dep.addDepForwards(in(0))._type.isHigh() ) return TypeMem.START; TypeMem mem = (TypeMem)_state.mem(); - for( int i = 2; i<nIns(); i++ ) { + for( int i = firstArgument(); i<nIns(); i++ ) { Type arg = dep.addDepForwards(in(i))._type; TypeMem outside = TypeMem.opaque(arg) ? CodeGen.CODE._start.outside(dep) : TypeMem.BOT; mem = mem.escapesFrom(arg,outside); } return TypeMem.make(1,Type.BOTTOM,false,false,false,mem._escFs,mem._escAs); } + // A class receiver is supplied by the callee, not exposed by its caller. + // Actual uses which publish self are already represented in _state. + private int firstArgument() { + if( !(in(0) instanceof FunNode fun) ) return 2; + TypeFunPtr sig = fun.sig(); + return sig.nargs()>0 && sig.arg(0)==TypePtr.PTR ? 3 : 2; + } @Override boolean _upgradeType(HashMap<String,Type> types) { TypeTuple state = (TypeTuple)_state.upgradeType(types); if( state==_state ) return false; diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter32/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index d4714953..9e0d864a 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -5,7 +5,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; import com.seaofnodes.simple.util.Ary; -import java.util.IdentityHashMap; +import java.util.BitSet; public class x86_64_v2 extends Machine { public x86_64_v2( CodeGen code ) {} @@ -461,12 +461,13 @@ public class x86_64_v2 extends Machine { if( load.nOuts()!=1 ) return false; Ary<Node> writers=load.antiDeps(new Ary<>(Node.class)); if( writers.isEmpty() ) return true; - var seen=new IdentityHashMap<Node,Boolean>(); + var seen=new BitSet(); Ary<Node> work=new Ary<>(Node.class); work.push(value); while( !work.isEmpty() ) { Node n=work.pop(); - if( seen.put(n,Boolean.TRUE)!=null ) continue; + if( seen.get(n._nid) ) continue; + seen.set(n._nid); if( writers.find(n)!=-1 ) return false; for( Node def : n._inputs ) if( def!=null ) work.push(def); } diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Expressions.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Expressions.java index ffc96f57..f791a34c 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/parser/Expressions.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Expressions.java @@ -36,6 +36,9 @@ final class Expressions { { P.pos(old); return parseExpression(); } P.references.checkAssignment(def,site); + // All fields use the same receiver-based lvalue path. + if( P.references.fieldSelf(def)!=null ) + { P.pos(old); return parseExpression(); } return P.references.assign(def,parseAssignment()); } diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/Functions.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/Functions.java index 84bd509e..a7726521 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/parser/Functions.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/Functions.java @@ -36,7 +36,7 @@ final class Functions { Type self = P.types.implicitSelfType(); if( P.structs.inStructDeclaration() ) self = self.makeRO(); ts.push(self); - ids.push(self == TypePtr.PTR ? "#self" : "self"); + ids.push("self"); // Parse other arguments P._lexer.skipWhiteSpace(); @@ -130,6 +130,10 @@ final class Functions { P._lexer.skipWhiteSpace(); Lexer nameLoc=P.loc(); String id = P.requireId(); + // Older free functions may explicitly name a source argument + // "self". It shadows the implicit class receiver, not its ABI slot. + if( id=="self" && ts.at(0)==TypePtr.PTR && ids.at(0)=="self" ) + ids.set(0,"#self"); if( ids.find(id)!=-1 ) throw Parser.error("Duplicate parameter '"+id+"'",nameLoc); ts .push(t ); // Push type/arg pairs ids.push(id); @@ -359,6 +363,14 @@ final class Functions { if( i == 0 && ids[0].equals("self") && !FunNode.isInit(funName) && !(sig.ret() instanceof TypeMem) && t instanceof TypeMemPtr ptr ) t = ptr.withAccess(false); + // The body sees its owning class receiver. PTR remains in the + // signature as the ABI marker for a receiver with no machine slot. + if( i==0 && t==TypePtr.PTR ) { + TypeStruct clz = ((TypeMemPtr)fun.defaultArg(i))._obj; + // A file can add globals after its struct declaration closes. + // Keep this view open until SCCP installs the completed class. + t = TypeMemPtr.make((byte)2,TypeStruct.make(clz._name,true,clz._fields),true); + } // Args take a default input if called from Start/external-world Type seed = i == 0 && t instanceof TypeMemPtr ? t : fun.defaultArg(i); Node parm = new ParmNode(ids[i],i+2,t,fun,ConstantNode.seed(seed).peephole()).peephole(); diff --git a/chapter32/src/main/java/com/seaofnodes/simple/parser/References.java b/chapter32/src/main/java/com/seaofnodes/simple/parser/References.java index 7724103e..91cf6859 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/parser/References.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/parser/References.java @@ -93,23 +93,9 @@ final class References { // Check for a function-escaping variable; these require true // closures. Final constants are OK; final vars require a hidden var // argument; not-final fields can just use an explicit struct arg. - if( kx < fx && !P.structs.inExplicitConstructor() && // Out of scope - !(var._final && rvalue._type.isConstant()) ) { // Not a final constant - if( kx > 0 ) // Global scope is OK, only ever one of these (not one per function invoke) - throw Parser.error("Variable '"+var._name+"' is out of function scope and must be a final constant",site); - - // var.idx==2 is self argument, 3 is args, 4 or more are now static globals - if( var._idx >= 4 ) { - // Read from global scope. - // Surely a nicer way to get the top-level scope compile name? - Var clzptr = P._scope.var( 2 ); - // Get the most recent sharpen global - TypeStruct clz = (TypeStruct) Parser.TYPES.get( ((TypeMemPtr) clzptr.type())._obj._name ); - TypeMemPtr clztmp = TypeMemPtr.make( (byte) 2, clz, true ); - return parseField( P.con( clztmp ), id,pre ); - //return parseField(_scope.in(2),id); - } - } + if( kx>0 && kx<fx && !P.structs.inExplicitConstructor() && + !(var._final && rvalue._type.isConstant()) ) + throw Parser.error("Variable '"+var._name+"' is out of function scope and must be a final constant",site); // Check for assign-update, x += e0; char ch = pre==0 ? P._lexer.matchOperAssign() : (char)pre; @@ -144,19 +130,6 @@ final class References { } Node assign(Var def, Node expr) { - Node self = fieldSelf(def); - if( self!=null ) { - TypeStruct ts = P.types.latestStruct(((TypeMemPtr)self._type)._obj); - Field fld = ts.field(def._name); - Node val = expr.keep(); - Node lift = P.conversions.convertExpr(val,def.type()); - Node mem = P.construction.storeMemory(self).keep(); - Node st = new StoreNode(P.loc(),fld._fname,fld._alias,fld._t,P.ctrl(),mem,self, - ConFldOffNode.make(ts,fld._fname),lift,P.construction.own(self)).peephole(); - P.construction.store(self,fld._alias,st,mem); - mem.unkeep(); - return val.unkeep(); - } String name = def._name; // Lift expression, based on type Type decl = def.type(); // Declared type @@ -305,19 +278,27 @@ final class References { return P._scope.in(P._scope.update(P._scope.var(selfx),null)); } - // Fields are lvalues in memory, including inside their initializer and - // explicit constructor. Scope slots retain declaration metadata only. - private Node fieldSelf(Var var) { + // Find the receiver for a field lvalue. Instance initializers use memory; + // class declarations retain their Scope values until initializer exit. + Node fieldSelf(Var var) { int kx = P._scope.kindx(var); ScopeNode.Kind kind = P._scope._kinds.at(kx); - if( !(kind instanceof Kind.Func inst) || !FunNode.isInstance(inst._name) || var._idx<inst._lexSize+2 ) return null; + if( !(kind instanceof Kind.Func owner) || !FunNode.isInit(owner._name) || var._idx<owner._lexSize+2 ) return null; + // Class declarations still accumulate their initial values in Scope. + // This also preserves declaration-time struct default expressions. + if( FunNode.isClz(owner._name) && P._scope.enclosingFunction()==kx ) return null; // Nested functions have their own receiver parameter. Resolve fields // through it even across intervening function and block scopes. Node self = defaultSelf(); - Type owner = P._scope.var(inst._lexSize).type(); - if( self._type instanceof TypeMemPtr ptr && owner instanceof TypeMemPtr declared && + Var receiver = P._scope.var(owner._lexSize); + if( self._type instanceof TypeMemPtr ptr && receiver.type() instanceof TypeMemPtr declared && ptr._obj._name.equals(declared._obj._name) ) return self; - return null; + // An instance method can also name fields of its enclosing class. + // Use that declaration's receiver; normal folding handles its identity. + if( !FunNode.isClz(owner._name) ) return null; + // The enclosing declaration may have discovered more fields since + // creating its receiver. View that same receiver with its current type. + return P.peep(new ConvertNode(receiver.type().upgradeType(Parser.TYPES),P._scope.in(receiver))); } private void checkSharedFunction(Var v) { diff --git a/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 19ec5019..c6f53022 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -248,7 +248,7 @@ public class TypeFunPtr extends TypeNil { @Override int TAGOFF() { return 8; } @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { assert _open; // Open: Passing extra args is fine, and extras ignored. - if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx() < 64 ) { + if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx()<=65535 ) { baos.write(TAGOFFS[_type] + nargs()); baos.packed2(fidx()); } else { @@ -259,8 +259,7 @@ public class TypeFunPtr extends TypeNil { } static TypeFunPtr packed( int tag, BAOS bais ) { if( tag < 6 ) { - int fidx = bais.read(); - assert fidx < 64; // Need a larger fidx space + int fidx = bais.packed2(); return malloc((byte)2,true,new Type[tag],null, XInt.make(fidx)); } byte nil = (byte)(tag==6 ? 2 : 3); diff --git a/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java b/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java index 61ce7387..c47d386c 100644 --- a/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java +++ b/chapter32/src/main/java/com/seaofnodes/simple/util/BAOS.java @@ -1,7 +1,8 @@ package com.seaofnodes.simple.util; -import java.util.HashMap; +//import java.util.HashMap; import java.util.Arrays; +import java.nio.charset.StandardCharsets; // "ByteArrayOutputStream", and Input Stream and not synchronized and has // matching pack/unpack strategies. @@ -96,12 +97,12 @@ public class BAOS { } // ----------------------------------------------------------------------- - // Write a packed integer to the BAOS. Track a histogram to make more - // intelligent choices in the future. - private static final HashMap<Long,Integer> PACKED_HISTOGRAM = new HashMap<>(); + // Optional profiling for choosing smaller packed representations. Leave + // disabled during normal compilation; re-enable when studying .simple size. + //private static final HashMap<Long,Integer> PACKED_HISTOGRAM = new HashMap<>(); private BAOS histo(long x) { - Integer cnt = PACKED_HISTOGRAM.get(x); - PACKED_HISTOGRAM.put(x,cnt==null ? 1 : cnt+1); + //Integer cnt = PACKED_HISTOGRAM.get(x); + //PACKED_HISTOGRAM.put(x,cnt==null ? 1 : cnt+1); return this; } @@ -125,15 +126,29 @@ public class BAOS { return x==0xFF ? read2() : x; } - // Write a packed i32 + // Signed zigzag varint: -64..63 use one byte, -8192..8191 two, + // and the full int range needs at most five. Seven payload bits per byte. public void packed4(int x) { - ((-127 <= x && x <= 127 ) ? write(x) : write(-128).write4(x)).histo(x); + histo(x); + int bits = (x<<1) ^ (x>>31); + while( (bits & ~127)!=0 ) { + write((bits & 127) | 128); + bits >>>= 7; + } + write(bits); } // Read a packed i32 public int packed4() { - int x = _buf[_len++]; // Signed byte read - return x== -128 ? read4() : x; + int bits=0; + for( int shift=0; shift<32; shift+=7 ) { + int b = read(); + if( shift==28 && (b & 0xF0)!=0 ) + throw new IllegalArgumentException("Packed int overflow"); + bits |= (b & 127)<<shift; + if( (b & 128)==0 ) return (bits>>>1) ^ -(bits & 1); + } + throw new IllegalArgumentException("Unterminated packed int"); } // Write a packed i64 @@ -148,14 +163,16 @@ public class BAOS { } public void packedS(String s) { - packed4(s.length()); - for( int i=0; i<s.length(); i++ ) - packed4(s.charAt(i)); + // Strings are bytes, not signed packed integers. Keep ASCII at one + // byte per character and agree on the representation of non-ASCII. + byte[] utf8 = s.getBytes(StandardCharsets.UTF_8); + packed4(utf8.length); + write(utf8); } public String packedS() { int len = packed4(); - String s = new String(_buf,_len,len).intern(); + String s = new String(_buf,_len,len,StandardCharsets.UTF_8).intern(); _len += len; return s; } diff --git a/chapter32/src/test/java/com/seaofnodes/simple/AssemblyDumpTest.java b/chapter32/src/test/java/com/seaofnodes/simple/AssemblyDumpTest.java index 0e4c230a..5399aecf 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/AssemblyDumpTest.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/AssemblyDumpTest.java @@ -13,25 +13,39 @@ public class AssemblyDumpTest { @Test public void libraryUnitsAndGlyphs() throws Exception { Path root=Path.of("build/objs/assembly-dump"); Files.createDirectories(root); - Path build=Files.createTempDirectory(root,"sys-"); - CodeGen code=new CodeGen("src/main/smp",build.toString(),null,"sys",null,123,true,TypeInteger.BOT) + Path fixture=Files.createTempDirectory(root,"font-"); + Path source=Files.createDirectories(fixture.resolve("src")); + Path build=Files.createDirectories(fixture.resolve("obj")); + Files.createDirectories(source.resolve("Atlas")); + // Use the real font, but only two tiny modules: drawing integration is + // covered by DrawTest. This test needs multiple units and constant data. + String canvasSource=Files.readString(Path.of("src/main/smp/sys/draw/Canvas.smp")); + int fontStart=canvasSource.indexOf("val _glyphs ="); + assertTrue("Font declaration",fontStart>=0); + int fontEnd=canvasSource.indexOf("};",fontStart); + assertTrue("Font initializer",fontEnd>=0); + Files.writeString(source.resolve("Atlas/Font.smp"),canvasSource.substring(fontStart,fontEnd+2)+ + "\nval glyph={int i -> _glyphs[i];};\n"); + Files.writeString(source.resolve("Atlas.smp"),"val glyph={int i -> Font.glyph(i);};\n"); + CodeGen code=new CodeGen(source.toString(),build.toString(),null,"Atlas",null,123,true,TypeInteger.BOT) .driver(CodeGen.Phase.Serialize,TestC.CPU_PORT,TestC.CALL_CONVENTION) .driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION); var entry=code._encoding; String before=code.asm(); assertSame("Dumping another unit must not change the active encoding",entry,code._encoding); + assertEquals(2,code._compunits.size()); for( var unit : code._compunits.values() ) if( unit._src!=null ) { String heading="=== Compilation unit: "+unit._cname+" ==="; assertEquals("Exactly one heading for "+unit._cname,2,before.split(heading,-1).length); } - int start=before.indexOf("=== Compilation unit: sys.draw.Canvas ==="); + int start=before.indexOf("=== Compilation unit: Atlas.Font ==="); assertTrue(start>=0); int end=before.indexOf("=== Compilation unit:",start+1); String canvas=before.substring(start,end<0 ? before.length() : end); assertTrue(canvas.contains("Constant Pool")); - assertTrue(canvas.contains("sys.draw.Canvas._glyphs: []u16")); - TypeMemPtr ptr=(TypeMemPtr)code._compunits.get("sys/draw/Canvas")._clz.field("_glyphs")._t; + assertTrue(canvas.contains("Atlas.Font._glyphs: []u16")); + TypeMemPtr ptr=(TypeMemPtr)code._compunits.get("Atlas/Font")._clz.field("_glyphs")._t; TypeConAry glyphs=(TypeConAry)ptr._obj.field("[]")._t; assertEquals(96,glyphs.len()); BAOS bytes=new BAOS(); @@ -40,10 +54,10 @@ public class AssemblyDumpTest { canvas.contains("60000000"+HexFormat.of().formatHex(bytes.toByteArray()))); code.exportELF(false,false); com.seaofnodes.simple.codegen.PrintRegTestSupport.checkDataAliases( - build.resolve("sys/draw/Canvas.o"),196,"sys.draw.Canvas._glyphs"); + build.resolve("Atlas/Font.o"),196,"Atlas.Font._glyphs"); assertSame(entry,code._encoding); assertEquals("Export must not truncate the dump to its entry unit",before,code.asm()); - Files.writeString(build.resolve("sys.asm"),before); + Files.writeString(build.resolve("Atlas.asm"),before); } @Test public void combinedEncodingAndEarlierPhase() { diff --git a/chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java b/chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java new file mode 100644 index 00000000..03e53b6d --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/BAOSTest.java @@ -0,0 +1,58 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.type.PackedTypeTestSupport; +import com.seaofnodes.simple.util.BAOS; +import java.util.Random; +import org.junit.Test; +import static org.junit.Assert.*; + +public class BAOSTest { + @Test public void packedIntBoundaries() { + int[] values={Integer.MIN_VALUE,-134217729,-134217728,-1048577,-1048576, + -8193,-8192,-65,-64,-1,0,1,63,64,8191,8192,1048575,1048576, + 134217727,134217728,Integer.MAX_VALUE}; + int[] widths={5,5,4,4,3,3,2,2,1,1,1,1,1,2,2,3,3,4,4,5,5}; + BAOS out=new BAOS(); + for( int i=0; i<values.length; i++ ) { + int before=out.size(); + out.packed4(values[i]); + assertEquals("width of "+values[i],widths[i],out.size()-before); + } + BAOS in=new BAOS(out.toByteArray()); + for( int value : values ) assertEquals(value,in.packed4()); + assertEquals(out.size(),in.size()); + out.clear(); + out.packed4(-65); out.packed4(64); + assertArrayEquals(new byte[]{(byte)0x81,1,(byte)0x80,1},out.toByteArray()); + } + + @Test public void packedIntsAndStrings() { + Random random=new Random(123); + int[] values=new int[10000]; + BAOS out=new BAOS(); + for( int i=0; i<values.length; i++ ) out.packed4(values[i]=random.nextInt()); + String[] strings={"","ASCII stays compact", "\u0000", "caf\u00e9 \u65e5\u672c\u8a9e \uD83D\uDE00", "x".repeat(8192)}; + for( String s : strings ) out.packedS(s); + out.packed8(Long.MIN_VALUE); + BAOS in=new BAOS(out.toByteArray()); + for( int value : values ) assertEquals(value,in.packed4()); + for( String s : strings ) assertEquals(s,in.packedS()); + assertEquals(Long.MIN_VALUE,in.packed8()); + assertEquals(out.size(),in.size()); + } + + @Test public void rejectPackedIntOverflow() { + for( byte last : new byte[]{0x10,(byte)0x80} ) { + BAOS in=new BAOS(new byte[]{(byte)0x80,(byte)0x80,(byte)0x80,(byte)0x80,last}); + try { in.packed4(); fail("overflow accepted"); } + catch( IllegalArgumentException expected ) { assertTrue(expected.getMessage().contains("overflow")); } + } + } + + @Test public void wideSingletonFunctionIds() { + new CodeGen(""); + for( int id : new int[]{2,63,64,254,255,256,1024,65535} ) + PackedTypeTestSupport.singleton(id); + } +} diff --git a/chapter32/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter32/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 43057c00..9f733da5 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -201,4 +202,38 @@ return a; catch( RuntimeException e ) { assertEquals("Undefined name 'ififif'",e.getMessage()); } } + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean shift : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = new CProjNode(code._start,0,"Ctrl").init(); + RegionNode region = new RegionNode(null,null,ctrl,ctrl).init(); + Node p = code.con(TypeInteger.BOT), i = code.con(TypeInteger.I32); + Node twice = shift ? new ShlNode(null,p,code.con(1)).init() + : new AddNode(p,p,(byte)1).init(); + Node sum = new AddNode(i,p,(byte)1).init(); + PhiNode phi = new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum).init(); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } + + @Test public void testOtherShiftIsNotDoubling() { + CodeGen code = new CodeGen(""); + Node ctrl = new CProjNode(code._start,0,"Ctrl").init(); + RegionNode region = new RegionNode(null,null,ctrl,ctrl).init(); + Node p = code.con(TypeInteger.BOT), i = code.con(TypeInteger.I32); + Node shift = new ShlNode(null,p,code.con(2)).init(); + Node sum = new AddNode(i,p,(byte)1).init(); + PhiNode phi = new PhiNode("sum",region,shift,sum).init(); + phi.keep(); + assertNull(phi.idealize()); + phi.unkeep(); + } } diff --git a/chapter32/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter32/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 273d76ba..226425ca 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -262,8 +262,8 @@ val hashCode = { !String self -> """; // Return the public hashCode wrapper; keep its helper private. testCPU(src,"x86_64_v2", "SystemV",28,null); - testCPU(src,"riscv" , "SystemV",8,null); - testCPU(src,"arm" , "SystemV",6,null); + testCPU(src,"riscv" , "SystemV",11,null); + testCPU(src,"arm" , "SystemV",11,null); } @Test diff --git a/chapter32/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter32/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 14a091ac..7a59adb0 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -386,8 +386,8 @@ val hashCode = { !String self -> """; // Return the public hashCode wrapper; keep its helper private. testCPU(src,"x86_64_v2", "SystemV",28,null); - testCPU(src,"riscv" , "SystemV",8,null); - testCPU(src,"arm" , "SystemV",6,null); + testCPU(src,"riscv" , "SystemV",11,null); + testCPU(src,"arm" , "SystemV",11,null); } @Test public void testStringExport() throws IOException { @@ -472,7 +472,8 @@ val test_sqrt = { flt x -> } }; """; - TestC.runC(src, "newtonFloat", result, TestC.CALL_CONVENTION.equals("win64") ? 42 : 34); + // With the zero-input guard, both SystemV and win64 score 42. + TestC.runC(src, "newtonFloat", result, 42); EvalRisc5 R5 = TestRisc5.build( src, "test_sqrt", 0, 10, false); R5.fregs[riscv.FA0 - riscv.F_OFFSET] = 3.0; @@ -532,8 +533,8 @@ val sieve = { int N -> String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - // Load/Phi hoisting now requires the pointer before the loop entry. - TestC.runC(src, "sieve", sprimes,216); + // Phi factoring also recognizes p<<1 after p+p strength reduction. + TestC.runC(src, "sieve", sprimes,215); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. diff --git a/chapter32/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter32/src/test/java/com/seaofnodes/simple/Chapter22Test.java index c9791de4..f9146ae6 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -302,17 +302,17 @@ val p = { u8[~] str -> p("Hello, World!"); return 0; """; - TestC.runSF(src,"helloWorld", "Hello, World!",2); + TestC.runSF(src,"helloWorld", "Hello, World!",4); // Evaluate on RISC5 emulator - EvalRisc5 R5 = TestRisc5.build( src, "helloWorld", 0, 5, false); + EvalRisc5 R5 = TestRisc5.build( src, "helloWorld", 0, 8, false); int trap = R5.step(100); assertEquals(0,trap); assertEquals(0,R5.regs[riscv.A0]); assertEquals("Hello, World!",R5._stdout.toString()); // Evaluate on ARM emulator - EvalArm64 arm = TestArm64.build("helloWorld", src,0, 5, false); + EvalArm64 arm = TestArm64.build("helloWorld", src,0, 8, false); trap = arm.step(100); assertEquals(0,trap); assertEquals(0,arm.regs[0]); diff --git a/chapter32/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java b/chapter32/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java new file mode 100644 index 00000000..51ed10c6 --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/GlobalAssignmentTest.java @@ -0,0 +1,71 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.parser.Parser; +import org.junit.Test; +import static org.junit.Assert.*; + +public class GlobalAssignmentTest { + private static final String SOURCE = """ + int value=1; + int writes=0; + u8 small=0; + val set={int n -> value=n; return value;}; + val set_noInline={int n -> + if( n<0 ) value=3; + else value=n; + return value; + }; + val rhs_noInline={ -> writes=writes+1; return value+1;}; + val shadow={int value -> value=42; return value;}; + struct Writer { + int seen; + new Writer={int n -> value=n; seen=value;}; + }; + struct InitWriter { int seen=(value=17); }; + val main={ -> + if( set(5)!=5 || value!=5 ) return 1; + if( set_noInline(-1)!=3 || value!=3 ) return 2; + if( set_noInline(8)!=8 || value!=8 ) return 3; + int result=(value=rhs_noInline()); + if( result!=9 || value!=9 || writes!=1 ) return 4; + value=writes=11; + if( value!=11 || writes!=11 ) return 5; + if( shadow(0)!=42 || value!=11 ) return 6; + int wide=(small=257); + if( wide!=257 || small!=1 ) return 7; + val constructed=new Writer(13); + if( value!=13 || constructed.seen!=13 ) return 8; + val initialized=new InitWriter; + // Default expressions run at declaration time, not per instance. + if( value!=13 || initialized.seen!=17 ) return 9; + return 0; + }; + return main(); + """; + + @Test public void storesGlobalMemory() throws Exception { + assertEquals("0",Eval2.eval(new CodeGen(SOURCE).driver(CodeGen.Phase.TypeCheck),0)); + TestC.runSF(SOURCE,"global_assignment","",-1); + } + + @Test public void rejectsFinalGlobal() { + try { + new CodeGen("val value=1; val set={ -> value=2; }; return set();") + .driver(CodeGen.Phase.TypeCheck); + fail("Assigned a final global"); + } catch( Parser.ParseException e ) { + assertEquals("Cannot reassign final 'value'",e.getMessage()); + } + } + + @Test public void rejectsIncompatibleGlobalValue() { + try { + new CodeGen("struct S { int x; }; int value=1; val set={ -> value=new S; }; set(); return value;") + .driver(CodeGen.Phase.TypeCheck); + fail("Stored an object in an integer global"); + } catch( Parser.ParseException expected ) { + assertTrue(expected.getMessage(),expected.getMessage().contains("not of declared type")); + } + } +} diff --git a/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java index cb17982e..253bce0b 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/MemMergeTest.java @@ -20,9 +20,8 @@ public class MemMergeTest { assertEquals(10000,mem.aliasAt(4)); assertSame(value,mem.alias(10000)); assertSame(defaults,mem.alias(512)); - assertEquals(10001,mem.packedSize()); - assertNull(mem.packedInput(9999)); - assertSame(value,mem.packedInput(10000)); + assertNull(mem.explicitAlias(9999)); + assertSame(value,mem.explicitAlias(10000)); mem.alias(513,null); assertEquals(4,mem.nIns()); assertEquals(10000,mem.aliasAt(3)); diff --git a/chapter32/src/test/java/com/seaofnodes/simple/ModTest.java b/chapter32/src/test/java/com/seaofnodes/simple/ModTest.java index 7f79599d..c06e99f1 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/ModTest.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/ModTest.java @@ -166,20 +166,31 @@ public class ModTest { return integerEdges(new long[]{Long.MIN_VALUE,Long.MIN_VALUE+1,-17,-5,-1,0,1,5,17,Long.MAX_VALUE}); } private static String integerEdges(long[] values) { + // Keep the full value matrix in data, rather than compiling a long + // chain of constant calls and conditional returns for every pair. StringBuilder source=new StringBuilder(""" val rem_noInline={ i64 x,i64 y -> x%y; }; val div_noInline={ i64 x,i64 y -> x/y; }; val main={ -> + val values=new i64[~]{ """); - int failure=1; - for( long x : values ) - for( long y : values ) { - source.append("if(rem_noInline(").append(literal(x)).append(',').append(literal(y)) - .append(")!=").append(literal(y==0 ? 0 : x%y)).append(") return ").append(failure++).append(';'); - source.append("if(div_noInline(").append(literal(x)).append(',').append(literal(y)) - .append(")!=").append(literal(y==0 ? 0 : x/y)).append(") return ").append(failure++).append(';'); + for(int i=0;i<values.length;i++) source.append(i==0 ? "" : ",").append(literal(values[i])); + source.append("}; val expectedRem=new i64[~]{"); + int n=0; + for(long x:values) for(long y:values) source.append(n++==0 ? "" : ",").append(literal(y==0 ? 0 : x%y)); + source.append("}; val expectedDiv=new i64[~]{"); + n=0; + for(long x:values) for(long y:values) source.append(n++==0 ? "" : ",").append(literal(y==0 ? 0 : x/y)); + return source.append(""" + }; + int index=0; + for(int i=0;i<values#;i++) for(int j=0;j<values#;j++) { + if(rem_noInline(values[i],values[j])!=expectedRem[index]) return index*2+1; + if(div_noInline(values[i],values[j])!=expectedDiv[index]) return index*2+2; + index++; } - return source.append("return 0; };").toString(); + return 0; }; + """).toString(); } @Test public void nativeFloatingEdges() throws Exception { double[][] cases={{Double.MAX_VALUE,0.1},{-Double.MAX_VALUE,0.1}, diff --git a/chapter32/src/test/java/com/seaofnodes/simple/ReceiverTest.java b/chapter32/src/test/java/com/seaofnodes/simple/ReceiverTest.java new file mode 100644 index 00000000..83bf6768 --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/ReceiverTest.java @@ -0,0 +1,93 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ReceiverTest { + @Test public void classAndInstanceFields() throws Exception { + String source=""" + int total=1; + val forward={ -> late(); }; + val early={ -> total; }; + val late={ -> early(); }; + val add_noInline={int n -> self.total=self.total+n; return total;}; + val read_noInline={ -> self.total; }; + val nested={ -> + val inc={ -> self.total++; }; + inc(); + return total; + }; + struct Counter { + int total=100; + val read=read_noInline; + }; + struct Writer { + int count=2; + val step={ -> self.count++; total=count; return total; }; + }; + val table=new u16[~2]{7,9}; + val lookup={u8 c -> c<2 ? table[c] : 0;}; + val main={ -> + total=1; + if( forward()!=1 ) return 4; + if( lookup(1)!=9 || lookup(2)!=0 ) return 5; + if( add_noInline(5)!=6 || nested()!=7 ) return 1; + val counter=new Counter; + if( counter.read()!=7 || counter.total!=100 ) return 2; + val a=new Writer, b=new Writer; + if( a.step()!=3 || total!=3 || a.count!=3 || b.count!=2 ) return 3; + return 0; + }; + return main(); + """; + assertEquals("0",Eval2.eval(new CodeGen(source).driver(CodeGen.Phase.TypeCheck),0)); + TestC.runSF(source,"class_instance_receivers","",-1); + } + + @Test public void importedCallbackKeepsItsClass() throws Exception { + Path build=Path.of("build/objs/receivers"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"classes-"); + new CodeGen(null,lib.toString(),null,"Owner", + "int value=7; val get_noInline={ -> self.value; };",123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + new CodeGen(null,lib.toString(),null,"Forwarder", + "int value=99; val apply_noInline={ {int} action -> action()+self.value; };",123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + var paths=new Ary<>(new String[]{lib.toString()}); + String source="return Forwarder.apply_noInline(Owner.get_noInline)==106 ? 0 : 1;"; + CodeGen code=new CodeGen(null,null,paths,"ReceiverClient",source,123,true,TypeInteger.BOT) + .driver(CodeGen.Phase.TypeCheck); + assertEquals("0",Eval2.eval(code,0)); + TestC.run(source,"imported_receivers",paths,TestC.CALL_CONVENTION,null,null,"",-1); + } + + @Test public void classReceiverHasNoNativeArgument() throws Exception { + String source=""" + int base=10; + val calc={int a,int b,int c,int d,int e,int f,int g -> + self.base+a+2*b+3*c+4*d+5*e+6*f+7*g; + }; + val callback_noInline={int n -> self.base+n;}; + { {int -> i64} int -> i64 } invoke="C"; + val viaC={int n -> invoke(callback_noInline,n);}; + """; + Path build=Path.of("build/objs/receivers"); + Files.createDirectories(build); + Path driver=build.resolve("native_receiver.c"); + Files.writeString(driver,""" + typedef long long (__attribute__((CALL_CONV)) *action_t)(int); + __attribute__((CALL_CONV)) long long invoke(action_t action, int n) { return action(n); } + __attribute__((CALL_CONV)) extern long long calc(int,int,int,int,int,int,int); + __attribute__((CALL_CONV)) extern long long viaC(int); + int main(void) { return calc(1,2,3,4,5,6,7)!=150 || viaC(5)!=15; } + """); + TestC.run(source,"native_receiver",null,TestC.CALL_CONVENTION, + TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi",driver.toString(),"",-1); + } +} diff --git a/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java b/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java index 1c278791..cc4e552f 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java @@ -10,6 +10,42 @@ import org.junit.Test; import static org.junit.Assert.*; public class SeparateCompilationTest { + @Test public void testSparseWideMemoryImport() throws Exception { + Path build=Path.of("build/objs/separate"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"wide-memory-"); + StringBuilder source=new StringBuilder("int f0=7;\n"); + for( int i=1; i<300; i++ ) source.append("int f").append(i).append("=0;\n"); + source.append("val touch={int n -> f299=n; return f0+f299;};"); + new CodeGen(null,lib.toString(),null,"Wide",source.toString(),123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + var paths=new Ary<>(new String[]{lib.toString()}); + CodeGen code=new CodeGen(null,null,paths,"WideEval","return Wide.touch((arg<<32)>>32);",123,true,TypeInteger.BOT) + .driver(CodeGen.Phase.TypeCheck); + assertEquals("12",Eval2.eval(code,5)); + TestC.run("return Wide.touch(5)==12 ? 0 : 1;","wide_memory_client",paths, + TestC.CALL_CONVENTION,null,null,"",-1); + } + + @Test public void testOldObjectFormatRequestsRebuild() throws Exception { + Path build=Path.of("build/objs/separate"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"old-format-"); + new CodeGen(null,lib.toString(),null,"Old","val value=7;",123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + Path file=lib.resolve("Old.o"); + ElfReader elf=ElfReader.load(file.toFile(),null); + byte[] bytes=Files.readAllBytes(file); + bytes[elf._bais.size()+3]='E'; // Previous C0DE header, before format 2. + Files.write(file,bytes); + try { + ElfReader.load(file.toFile(),null).loadPublicTypes(new CodeGen("")); + fail("old format accepted"); + } catch( IllegalArgumentException expected ) { + assertTrue(expected.getMessage().contains("rebuild the object file")); + } + } + @Test public void testImportedReadOnlyPrimitiveArray() throws Exception { Path build=Path.of("build/objs/separate"); Files.createDirectories(build); diff --git a/chapter32/src/test/java/com/seaofnodes/simple/StringFormatTest.java b/chapter32/src/test/java/com/seaofnodes/simple/StringFormatTest.java index 59b62709..d6783380 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/StringFormatTest.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/StringFormatTest.java @@ -11,28 +11,88 @@ import org.junit.Test; import static org.junit.Assert.*; public class StringFormatTest extends TestC { - private static void prints(String body, String expected) throws Exception { - runSYS("val main={ -> "+body+" return 0; };", "stringFormat",expected,-1); + // Share a few native programs, retaining a separately reported assertion + // for each case. Blocks isolate locals; the delimiter preserves embedded + // NULs and newlines in the expected output. + private enum Format { + DefaultsAndNestedStrings("sys.io.p(\"CPU plays %(2+3). %(\"nested %(7)\") %(true) %(1.5)\\n\");", + "CPU plays 5. nested 7 1 1.5\n"), + Formats("sys.io.p(\"%+06d(17)|%#08x(42)|%-5.3s(\"abcdef\")|%.2f(1.25)|%c(65)|%b(false)\\n\");", + "+00017|0x00002a|abc |1.25|A|false\n"), + RemainderInInterpolation("int mod=17; sys.io.p(\"%(mod%5)|%02d(mod%5)|%%|\\%|%(mod %= 5)|%(mod)\");", + "2|02|%|%|2|2"), + IntegerLimits("i64 lo=-9223372036854775807-1; sys.io.p(\"%(lo)|%(9223372036854775807)|%u(-1)|%X(-1)\");", + "-9223372036854775808|9223372036854775807|18446744073709551615|FFFFFFFFFFFFFFFF"), + IntegerPaddingRules("sys.io.p(\"%#.0o(0)|%#.3o(1)|%#x(0)|%-08d(17)|%08.4d(-17)|%+d(0)|% d(0)\");", + "0|001|0|17 | -0017|+0| 0"), + BuilderNumberUsesFormatter("val b=new sys.aryu8(); b.num(-9223372036854775807-1).add('|').num(9223372036854775807); sys.io.p(sys.text.end(b));", + "-9223372036854775808|9223372036854775807"), + EvaluationOrder("int x=0; val s=\"%(x++)%(x++)%(x++)\"; sys.io.p(\"%(s):%(s#):%(x)|%%|\\%\");", + "012:3:3|%|%"), + EvaluationMutatesBytes("val a=new u8[1]; a[0]='A'; sys.io.p(\"%(a)%(a[0]='B')%(a)\");", "A66B"), + Converters("sys.io.p(sys.text.int(17)); sys.io.p(sys.text.char(65)); sys.io.p(sys.text.bool(true)); sys.io.p(sys.text.flt(1.5));", + "17Atrue1.5"), + FieldNamedInt("struct S { int int=7; }; sys.io.p(\"%((new S).int)\");", "7"), + FloatAndAlternateFormats("f32 x=1.25f; sys.io.p(\"%(x)|%f(x)|%.2e(x)|%.2G(x)|%#o(9)|% d(7)|%.0d(0)|%a(1.5)\");", + "1.25|1.250000|1.25e+00|1.2|011| 7||0x1.8p+0"), + BufferGrowth("sys.io.p(\"%0100d(17)|%.100f(1.0)\");", "0".repeat(98)+"17|1."+"0".repeat(100)), + BytesAndEmptyStrings("val empty=\"%(\"\")\"; val bytes=\"a\\0b\"; sys.io.p(\"%(empty#):%s(bytes):%.2s(bytes):%c(0)\");", + "0:a\0b:a\0:\0"), + Utf8String("val s=\"π\"; sys.io.p(\"%(s):%(s#):%(s[0]):π\");", "π:2:207:π"), + DeferredParsing(""" + struct S { u8[~] s; new S={ -> s="%("}) %(3)")"; }; }; + val s=new S; + sys.io.p(s.s); + for(int i=0; i<2; sys.io.p("%(i++) %("(")")) { } + """, "}) 30 (1 ("); + + final String body, expected; + Format(String body, String expected) { this.body=body; this.expected=expected; } + } + private static final String END="\n--end-format-case--\n"; + private static final int BATCH_SIZE=5; + private static final String[] OUTPUTS=new String[Format.values().length]; + + @org.junit.BeforeClass public static void resetNativeBatches() { + java.util.Arrays.fill(OUTPUTS,null); + } + + private static void prints(Format test) throws Exception { + int index=test.ordinal(); + if( OUTPUTS[index]==null ) { + Format[] cases=Format.values(); + int first=index/BATCH_SIZE*BATCH_SIZE, limit=Math.min(first+BATCH_SIZE,cases.length); + StringBuilder source=new StringBuilder("val main={ -> "); + for( int i=first; i<limit; i++ ) { + assertFalse("Reserved batch delimiter",cases[i].expected.contains(END)); + source.append('{').append(cases[i].body).append('}'); + source.append("sys.io.p(\"\\n--end-format-case--\\n\");"); + } + source.append("return 0; };"); + String exe=compile(source.toString(),"stringFormat"+first, + new Ary<>(new String[]{RELEASE_SYS_DIR}),CALL_CONVENTION,null,null,-1); + String[] outputs=exec(TEST_TIMEOUT_SECONDS,exe).split(java.util.regex.Pattern.quote(END),-1); + assertEquals("Each format case must complete",limit-first+1,outputs.length); + assertEquals("No output after final case", "",outputs[outputs.length-1]); + for( int i=first; i<limit; i++ ) OUTPUTS[i]=outputs[i-first]; + } + assertEquals(test.name(),test.expected,OUTPUTS[index]); } @Test public void testDefaultsAndNestedStrings() throws Exception { - prints("sys.io.p(\"CPU plays %(2+3). %(\"nested %(7)\") %(true) %(1.5)\\n\");", - "CPU plays 5. nested 7 1 1.5\n"); + prints(Format.DefaultsAndNestedStrings); } @Test public void testFormats() throws Exception { - prints("sys.io.p(\"%+06d(17)|%#08x(42)|%-5.3s(\"abcdef\")|%.2f(1.25)|%c(65)|%b(false)\\n\");", - "+00017|0x00002a|abc |1.25|A|false\n"); + prints(Format.Formats); } @Test public void testRemainderInInterpolation() throws Exception { - prints("int mod=17; sys.io.p(\"%(mod%5)|%02d(mod%5)|%%|\\%|%(mod %= 5)|%(mod)\");", - "2|02|%|%|2|2"); + prints(Format.RemainderInInterpolation); } @Test public void testIntegerLimits() throws Exception { - prints("i64 lo=-9223372036854775807-1; sys.io.p(\"%(lo)|%(9223372036854775807)|%u(-1)|%X(-1)\");", - "-9223372036854775808|9223372036854775807|18446744073709551615|FFFFFFFFFFFFFFFF"); + prints(Format.IntegerLimits); } @Test public void testSignedAndUnsignedRadices() throws Exception { @@ -49,13 +109,11 @@ public class StringFormatTest extends TestC { } @Test public void testIntegerPaddingRules() throws Exception { - prints("sys.io.p(\"%#.0o(0)|%#.3o(1)|%#x(0)|%-08d(17)|%08.4d(-17)|%+d(0)|% d(0)\");", - "0|001|0|17 | -0017|+0| 0"); + prints(Format.IntegerPaddingRules); } @Test public void testBuilderNumberUsesFormatter() throws Exception { - prints("val b=new sys.aryu8(); b.num(-9223372036854775807-1).add('|').num(9223372036854775807); sys.io.p(sys.text.end(b));", - "-9223372036854775808|9223372036854775807"); + prints(Format.BuilderNumberUsesFormatter); } @Test public void testFormattingInEvaluatorFromSource() { @@ -74,15 +132,13 @@ public class StringFormatTest extends TestC { } @Test public void testEvaluationOrderAndLength() throws Exception { - prints("int x=0; val s=\"%(x++)%(x++)%(x++)\"; sys.io.p(\"%(s):%(s#):%(x)|%%|\\%\");", - "012:3:3|%|%"); - prints("val a=new u8[1]; a[0]='A'; sys.io.p(\"%(a)%(a[0]='B')%(a)\");", "A66B"); + prints(Format.EvaluationOrder); + prints(Format.EvaluationMutatesBytes); } @Test public void testConverters() throws Exception { - prints("sys.io.p(sys.text.int(17)); sys.io.p(sys.text.char(65)); sys.io.p(sys.text.bool(true)); sys.io.p(sys.text.flt(1.5));", - "17Atrue1.5"); - prints("struct S { int int=7; }; sys.io.p(\"%((new S).int)\");", "7"); + prints(Format.Converters); + prints(Format.FieldNamedInt); } @Test public void testForwardReturnTypes() throws Exception { @@ -91,14 +147,13 @@ public class StringFormatTest extends TestC { } @Test public void testFloatAndAlternateFormats() throws Exception { - prints("f32 x=1.25f; sys.io.p(\"%(x)|%f(x)|%.2e(x)|%.2G(x)|%#o(9)|% d(7)|%.0d(0)|%a(1.5)\");", - "1.25|1.250000|1.25e+00|1.2|011| 7||0x1.8p+0"); + prints(Format.FloatAndAlternateFormats); runSYS("val format_noInline={ f32 x -> \"%(x)|%f(x)\"; }; val main={ -> sys.io.p(format_noInline(1.25f)); return 0; };", "stringFormatFloat","1.25|1.250000",-1); } @Test public void testBufferGrowth() throws Exception { - prints("sys.io.p(\"%0100d(17)|%.100f(1.0)\");", "0".repeat(98)+"17|1."+"0".repeat(100)); + prints(Format.BufferGrowth); } @Test public void testLiteralRemainsConstant() { @@ -107,18 +162,12 @@ public class StringFormatTest extends TestC { } @Test public void testBytesAndEmptyStrings() throws Exception { - prints("val empty=\"%(\"\")\"; val bytes=\"a\\0b\"; sys.io.p(\"%(empty#):%s(bytes):%.2s(bytes):%c(0)\");", - "0:a\0b:a\0:\0"); - prints("val s=\"π\"; sys.io.p(\"%(s):%(s#):%(s[0]):π\");", "π:2:207:π"); + prints(Format.BytesAndEmptyStrings); + prints(Format.Utf8String); } @Test public void testDeferredParsing() throws Exception { - prints(""" - struct S { u8[~] s; new S={ -> s="%("}) %(3)")"; }; }; - val s=new S; - sys.io.p(s.s); - for(int i=0; i<2; sys.io.p("%(i++) %("(")")) { } - """, "}) 30 (1 ("); + prints(Format.DeferredParsing); } @Test public void testImportedFormatter() throws Exception { diff --git a/chapter32/src/test/java/com/seaofnodes/simple/TestWorkspace.java b/chapter32/src/test/java/com/seaofnodes/simple/TestWorkspace.java index 30cff89f..d875c47a 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/TestWorkspace.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/TestWorkspace.java @@ -7,7 +7,7 @@ import java.nio.file.attribute.BasicFileAttributes; /** Prepare a Make test group's working directory without sharing native outputs. */ public class TestWorkspace { public static void main(String[] args) throws IOException { - if( args.length!=2 || !args[0].matches("tests_group[0-7]") || !args[1].matches("[A-Za-z0-9_]+") ) + if( args.length!=2 || !args[0].matches("tests_group[0-7]|sanity_group[0-2]") || !args[1].matches("[A-Za-z0-9_]+") ) throw new IllegalArgumentException("Expected test group and CPU_ABI"); Path root = Path.of("").toAbsolutePath().normalize(); Path work = root.resolve("build/tests").resolve(args[0]).normalize(); diff --git a/chapter32/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter32/src/test/java/com/seaofnodes/simple/TypeTest.java index 8f212bda..adcc1b3a 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -276,74 +276,77 @@ public class TypeTest { public void testLatticeTheory() { Type[] ts = Type.gather(); // Make partitions the outer loop between independent JVMs. A direct - // JUnit/IDE invocation retains the full Cartesian-product coverage. + // JUnit/IDE invocation retains the full coverage. int parts = Integer.parseInt(System.getProperty("simple.lattice.parts","1")); int part = Integer.parseInt(System.getProperty("simple.lattice.part" ,"0")); Assert.assertTrue("Invalid lattice partition",parts > 0 && parts <= ts.length && part >= 0 && part < parts); - // Confirm commutative & complete - for( int i=part; i<ts.length; i+=parts ) { - Type t0 = ts[i]; - for( Type t1 : ts ) { - check_commute (t0,t1); - check_symmetric(t0,t1); + // Every triple reuses these pairs. Compute both operand orders rather + // than assuming commutativity in the table we are about to check. + Type[][] meets = new Type[ts.length][ts.length]; + Type[][] joins = new Type[ts.length][ts.length]; + for( int i=0; i<ts.length; i++ ) + for( int j=0; j<ts.length; j++ ) { + meets[i][j] = ts[i].meet(ts[j]); + joins[i][j] = ts[i].join(ts[j]); } - } - // Confirm associative + // Confirm commutative & complete, once per unordered pair. for( int i=part; i<ts.length; i+=parts ) { - Type t0 = ts[i]; - for( Type t1 : ts ) - for( Type t2 : ts ) - assoc(t0,t1,t2); + assertSame(ts[i],meets[i][i]); + for( int j=i; j<ts.length; j++ ) { + assertSame(meets[i][j],meets[j][i]); + check_symmetric(ts[i],ts[j],meets[i][j]); + } } + // Each unordered triple represents all six permutations. Check every + // intermediate result in both operand orders; a pair's meet need not + // itself be in ts, so its commutativity must not be assumed. + for( int i=part; i<ts.length; i+=parts ) + for( int j=i; j<ts.length; j++ ) + for( int k=j; k<ts.length; k++ ) + assoc(ts[i],ts[j],ts[k],meets[i][j],meets[i][k],meets[j][k]); + // Confirm symmetry. If A isa B, then A.join(C) isa B.join(C) for( int i=part; i<ts.length; i+=parts ) { Type t0 = ts[i]; - for( Type t1 : ts ) - if( t0.isa(t1) ) - for( Type t2 : ts ) { - Type t02 = t0.join(t2); - Type t12 = t1.join(t2); + for( int j=0; j<ts.length; j++ ) + if( meets[i][j]==ts[j] ) + for( int k=0; k<ts.length; k++ ) { + Type t02 = joins[i][k]; + Type t12 = joins[j][k]; Type mt = t02.meet(t12); - assertSame(t0+" isa "+t1+" joined "+t2, mt,t12); + if( mt!=t12 ) assertSame(t0+" isa "+ts[j]+" joined "+ts[k], mt,t12); } } } - // By design in meet, args are already flipped to order _type, which forces - // symmetry for things with badly ordered _type fields. The question is - // still interesting for other orders. - private static void check_commute( Type t0, Type t1 ) { - if( t0==t1 ) return; - if( t0.is_simple() && !t1.is_simple() ) return; // By design, flipped the only allowed order - Type mta = t0.meet(t1); - Type mtb = t1.meet(t0); // Reverse args and try again - assertSame(mta,mtb); - } - // A & B = MT // Expect: ~A & ~MT == ~A // Expect: ~B & ~MT == ~B private static void check_symmetric( Type t0, Type t1 ) { + check_symmetric(t0,t1,t0.meet(t1)); + } + + private static void check_symmetric( Type t0, Type t1, Type mt ) { if( t1==t0 ) return; - Type mt = t0.meet(t1); Type dm = mt.dual(); Type d0 = t0.dual(); Type d1 = t1.dual(); Type ta = dm.meet(d1); Type tb = dm.meet(d0); - assertSame(t0+" & "+t1+" mt="+mt, ta,d1); - assertSame(t0+" & "+t1+" mt="+mt, tb,d0); + if( ta!=d1 ) assertSame(t0+" & "+t1+" mt="+mt, ta,d1); + if( tb!=d0 ) assertSame(t0+" & "+t1+" mt="+mt, tb,d0); } - private static void assoc( Type t0, Type t1, Type t2 ) { - Type t01 = t0 .meet(t1 ); - Type t12 = t1 .meet(t2 ); - Type t01_2 = t01.meet(t2 ); - Type t0_12 = t0 .meet(t12); - assertSame(t0+" & "+t1+" & "+t2, t01_2,t0_12); + private static void assoc( Type a, Type b, Type c, Type ab, Type ac, Type bc ) { + // The six original associativity equalities connect these six values + // in a cycle. Equality to one common result checks the same property. + Type result = ab.meet(c); + if( result!=c.meet(ab) || result!=ac.meet(b) || result!=b.meet(ac) || + result!=bc.meet(a) || result!=a.meet(bc) ) + Assert.fail("Associativity: "+a+" & "+b+" & "+c); } // Test cyclic types and meets diff --git a/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index edb2519c..ae935da0 100644 --- a/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter32/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -85,7 +85,7 @@ public class RegAllocTestSupport { new Op(null,A,null,false,code._start,def); RegAlloc alloc = new RegAlloc(code); assertTrue(BuildLRG.run(0,alloc)); - assertFalse("A live value cannot survive a register kill",IFG.build(0,alloc)); + assertFalse("A live value cannot survive a register kill",new IFG().build(0,alloc)); } public static void nullUseMask() { @@ -95,7 +95,7 @@ public class RegAllocTestSupport { new Op(null,null,null,false,code._start,def); // Scheduling dependency only. RegAlloc alloc = new RegAlloc(code); assertTrue(BuildLRG.run(0,alloc)); - assertTrue(IFG.build(0,alloc)); + assertTrue(new IFG().build(0,alloc)); } public static void independentFunctions() { @@ -262,7 +262,7 @@ public class RegAllocTestSupport { assertTrue(BuildLRG.run(0,alloc)); assertNull(alloc.lrg(top)); assertSame(alloc.lrg(def),alloc.lrg(phi)); - assertTrue(IFG.build(0,alloc)); + assertTrue(new IFG().build(0,alloc)); alloc.insertBefore(phi,slot,"test",(byte)0,alloc.lrg(phi)); assertSame(top,phi.in(slot)); } diff --git a/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java b/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java new file mode 100644 index 00000000..c218e98b --- /dev/null +++ b/chapter32/src/test/java/com/seaofnodes/simple/type/PackedTypeTestSupport.java @@ -0,0 +1,20 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.util.BAOS; +import java.util.HashMap; +import static org.junit.Assert.*; + +public class PackedTypeTestSupport { + public static void singleton(int id) { + Type.TAGOFFS(); + TypeFunPtr fun=TypeFunPtr.make((byte)2,true,new Type[0],TypeInteger.BOT,XInt.make(id)); + BAOS out=new BAOS(); + fun.packed(out,new HashMap<>()); + assertEquals(id<=254 ? 2 : 4,out.size()); + BAOS in=new BAOS(out.toByteArray()); + TypeFunPtr copy=(TypeFunPtr)Type.packed(in,new String[]{""}); + assertEquals(id,copy.fidx()); + assertEquals(0,copy.nargs()); + assertEquals(out.size(),in.size()); + } +} |
