Chapter 25: Modules, Separate Compilation, and SSA Constructionlinear

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

1 files changed, 0 insertions, 338 deletions

diff --git a/#README.md# b/#README.md#
deleted file mode 100644
index 9b973a09..00000000
--- a/#README.md#
+++ /dev/null
@@ -1,338 +0,0 @@
-# Chapter 24: Chaining Relationals and Sparse Conditional Constant Propagation
-
-English | [日本語](README.ja.md)
-
-[Previous: Chapter 23](../chapter23/README.md) |
-[Next: Chapter 25](../chapter25/README.md)
-
-In this Chapter we allow *chaining* conditionals, e.g. `(60 <= score < 90)`
-where `score` in the middle does not have to be repeated.
-
-The main compiler change is Interprocedural Sparse Conditional Constant
-Propagation (SCCP): an optimistic type solve which also discovers call-graph
-edges.  SCCP is otherwise the traditional one taught in many classes, except
-the lattice it operates on is very rich.
-
-A new syntax feature is chaining conditions, ala `lo <= x < min` is legal syntax.
-
-You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter24) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter23...linear-chapter24) it to the previous chapter.
-
-
-Here is the [complete language grammar](docs/24-grammar.md) for this chapter.
-
-
-## Sparse Conditional Constant Propagation
-
-[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation)
-is the top-down version of the same peephole/constant-folding work we have
-been doing all along.  The rules for the algorithm are well known from the
-literature and commonly taught at the college level;
-[example slides](https://www.cse.psu.edu/~gxt29/teaching/cse522s23/slides/08monotoneFramework.pdf).
-
-- We have a lattice already
-- We have SSA form already (hence the algorithm is *sparse*)
-- We have a mapping from Nodes to Types (`Node._type`)
-- We have transfer functions (`Node.compute`) already.
-
-We initialize all `_type` fields to ⊤ (as opposed to ⊥), and place all Nodes on
-a worklist.  We pull a Node from the worklist, run the transfer function
-`node.compute()`, and if the result changes from `node._type` we update
-`node._type` and put its output neighbors on the worklist.  A simplified
-version with all asserts and debug helpers removed:
-
-```java
-while( (n = code._iter._work.pop()) != null ) {
-    Type nval = n.compute();
-    if( n._type != nval ) {
-        assert n._type.isa(nval);     // Types start high and always fall
-        n._type = nval;               // Update type in Node
-        code._iter.addAll(n._outputs);// Neighbors might change, need to inspect
-    }
-}
-```
-
-This algorithm always terminates (and generally fairly quickly) and always
-reaches a *fixed point*, as "best answer" subject to the limits of our lattice
-and transfer functions.  The resulting types are monotonically better than
-those found by the peephole rules; we can then run the peephole rules on nodes
-with improved types, to see if unrelated peepholes can fire - such as newly
-discovered constants replacing computations with ConstantNodes.
-
-The following is SSA pseudocode:
-
-```text
-int x0 = 1;          // x0 = 1
-while( rand ) {
-    x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT)
-    x2 = 2 - x1;     // x2 = BOT = 2 - BOT
-}
-return x1
-```
-
-Without SCCP, this small program cannot fold the computation of `x`.
-A glance at the program tells us `x` must always be a `1` but
-the bottom-up (pessimistic) approach decides that since x1 is BOT, x2 must be
-BOT so x1 must be BOT.  We need the optimistic approach to break the
-stalemate, and just *assume* x1 is `1`, and then we can discover that x2 is
-also a `1`. Folding the value does not prove the loop terminates or make
-its condition and side effects removable.
-
-
-The algorithm progresses from left to right and stops when no more changes
-happen:
-
-|Var|init|x0=1|x1=phi(1,T)|x2=2-x1|x1=phi(1,1)|
-|---|----|----|-----------|-------|-----------|
-|x0 | T  | 1  | 1         | 1     | 1         |
-|x1 | T  | T  | 1         | 1     | 1         |
-|x2 | T  | T  | T         | 1     | 1         |
-
-
-
-### Conditional
-
-Since our control flow is in the same graph as our data flow (that's the major
-point of Sea-of-Nodes!), we need not do anything special and our algorithm is
-*conditional* already.  Again an example is interesting:
-
-Again using SSA pseudocode:
-
-```text
-int x0 = 1;          // x0 = 1
-while( rand ) {
-    x1 = phi(x0,x4); // x1 = BOT = phi(1,BOT)
-    if( x1 == 1 )    // Since x1 is BOT, both true and false arms are taken
-        x2 = 2 - x1; // x2 = BOT = 2 - BOT
-    else x3 = 99;    // x3 = 99
-    x4 = phi(x2,x3); // x4 = BOT = phi(BOT,99)
-}
-return x1
-```
-
-Again the algorithm progresses from left to right, although this time not all
-paths are reachable.  The `if` result is a pair of Control values, shown as
-either `C` if the path is alive or `X` if not.  This is used when we compute
-`x4 = phi(x2,x3)`; the `PhiNode` ALSO checks the corresponding control input
-from the `if` and only merges alive paths.
-
-
-|Var|init |x0=1|x1=phi(1,T)| 1 == 1? | x2=2-x1 | x3=99   |x4=phi(C/1,X/99)|x1=phi(1,1)|
-|---|-----|----|-----------|---------|---------|---------|----------------|-----------|
-|x0 | T   | 1  | 1         | 1       | 1       | 1       | 1              | 1         |
-|x1 | T   | T  | 1         | 1       | 1       | 1       | 1              | 1         |
-|if | T   | T  | T         | [C,X]   | [C,X]   | [C,X]   | [C,X]          | [C,X]     |
-|x2 | T   | T  | T         | T       | 1       | 1       | 1              | 1         |
-|x3 | T   | T  | T         | T       | T       | 99      | 99             | 99        |
-|x4 | T   | T  | T         | T       | T       | T       | 1              | 1         |
-
-This kind of conditional constant propagation really helps if a condition can
-be proven true or false, as this removes a test and branch from the optimized
-program.  A common way this happens is with null tests; here is the same
-program above, but using null pointers instead of integers:
-
-```java
-List head = notNullList();
-while( rand ) {
-    if( head ) head = new List(head,payload);
-    else { head = null; default_action(); }
-}
-```
-
-Here since `head` starts not-null, it can never be null and the
-`default_action` can never happen, and the loop can
-simplify:
-
-```java
-List head = notNullList();
-while( rand ) {
-    head = new List(head,payload);
-}
-```
-
-### Interprocedural
-
-In **Simple**, we let our SCCP run interprocedurally, again by (nearly) doing nothing:
-`CallNodes` call `FunNodes`, `ReturnNodes` return to `CallEndNodes` and they
-pass their type information along in exactly the normal way... except for one issue:
-there are no edges between `Calls` and `Funs` (nor `Returns` and `CallEnds`).
-Such edges make up a [Call Graph](https://en.wikipedia.org/wiki/Call_graph).
-
-We extend the normal SCCP algorithm to observe when a `Call`s function pointer
-input changes - when it picks up new function targets.  There are only a finite
-number so we represent them exactly with *function indices* as described in an
-earlier chapter.  (Separate compilation adds a special index for the infinite
-unknown functions that are called outside this compilation unit).
-
-Once we observe a new *fidx* at a `Call`, we *link* the `Call` with the `Fun`,
-and the `Return` with the `CallEnd`.  Such linkage acts exactly as-if we added
-a CFG edge from the `Call` to the `Fun`, and the `Call`s arguments to the
-`Fun`s `ParmNodes`.  `FunNodes` extend `RegionNodes` (and `ParmNodes` extend
-`PhiNodes`), so this linkage uses the same semantics.  `Fun`s become reachable
-when called; `Parm`s merge (*meet*) all calling arguments, and so on.
-Similarly, `CallEnd`s merge results from all called functions, computing the
-*meet* over all the `Return`s.
-
-This *link* step adds a few checks to our algorithm's inner loop, and also
-builds a precise Call Graph which allows our SCCP to run interprocedurally.
-Other than discovering a few new edges as the algorithm proceeds, the core
-algorithm is unchanged.  We are guaranteed to terminate with a fixed point
-solution, and may discover e.g. certain call parameters are constants (or
-e.g. not-null) on all calling paths.
-
-
-
-## Chaining Relational Tests
-
-Chaining relational tests offer a cleaner, more readable way to write chained
-comparisons without repeating the same variable.
-
-```java
-if (min <= x && x < max)
-```
-
-becomes
-
-```java
-if (min <= x < max)
-```
-
-This syntax saves space and makes the condition more intuitive, similar to how
-range checks are written in mathematics.  E.g.
-
-```java
-int score = 75;
-if (60 <= score < 90) {
-    sys.io.p("Pass");
-}
-```
-This checks if score is between 60 (inclusive) and 90 (exclusive), without repeating `score`.
-
-Expressions that mix opposite directions of comparison, like using both
-`<=` and `>=`, are not allowed by Simple's direction rule.
-
-```java
-if (a <= b >= c)
-```
-
-
-### Operator direction rules
-Stacked comparisons are *only* valid if all the comparison operators
-"point" the same way:
-- `<` with `<`
-- `<` with `<=`
-- `>` with `>`
-- `>` with `>=`
-
-Equality operators (`==` and `!=`) have their normal, lower precedence; they
-are not links in a relational chain.
-
-It is not allowed to mix directions in a single chain:
-```java
-if (a <= b >= c) // Invalid
-```
-
-Comparisons can be forced into numeric context using booleans.
-This is valid but unusual:
-```java
-return (0 < arg) > 1;
-```
-Depending on the result of (0 < arg) this will turn into either
-```java
-return 0 > 1;
-```
-OR
-```java
-return 1 > 1;
-```
-The equality operator is valid in this form, but since it has lower precedence than comparisons,
-```java
-a < b == c
-```
-is parsed as:
-```java
-(a < b) == c
-```
-This might not be the intended chained comparison.
-A more explicit alternative is:
-```java
-a < b && b == c
-```
-Comparisons can be chained together in any length, and different comparison operators may be
-mixed freely as long as they point in the same direction.
-Each intermediate operand is evaluated once. Later operands are evaluated only
-if earlier comparisons succeed, so calls and updates in a chain short-circuit.
-
-E.g:
-```
-return 0 < arg < arg+1 < 4;
-```
-
-### Tricky edge cases
-```java
-return 0 != arg != 1;
-```
-
-This is parsed by standard precedence rules as:
-```java
-return ((0 != arg) != 1);
-```
-not as chained inequality.
-
-```java
-return a == b == c;
-```
-Similarly, this is parsed as:
-```java
-return ((a == b) == c);
-```
-
-
-### Optimization phases
-
-SCCP introduces a real `Opto` phase between two uses of the peephole worklist:
-
-```text
-Parse -> Iter -> Opto -> IterPostOpto -> FinalizeIR -> TypeCheck
-```
-
-`Iter` first reaches the pessimistic fixed point. `Opto` resets types to TOP,
-solves SCCP and the call graph, and queues nodes whose types changed.
-    `IterPostOpto` applies rewrites and inlining enabled by that solution.
-`FinalizeIR` settles layouts and detaches the analyzed call graph while keeping
-surviving functions available to the backend.
-
-
-## RegAlloc improvements: try cold loop splits first
-
-A loop Phi and its backedge can belong to one live range even though their
-values must coexist at some instruction.  This self-conflict requires splitting
-the range.  Chapter 23 split the Phi's definition and incoming values right away.
-This chapter first leaves the hot definition/backedge alone and tries the
-outside-loop copies.  If coloring succeeds, it avoids moves on every iteration.
-Other conflicts, including two-address operations, keep their existing handling.
-
-The allocator remembers which Phis have had this chance.  If the same Phi
-self-conflicts again, the next attempt uses the ordinary aggressive splitting.
-The record uses Phi identity because live ranges are rebuilt each round.  It
-also covers a backedge-only conflict where the first attempt inserts no copy:
-that attempt must still consume the one permitted delay.  A regression checks
-both the cheaper first attempt and the mandatory fallback.
-
-Rows are fixed test cohorts; columns are compiler chapters. Each cell gives
-**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for
-allocator copies/rematerializations, and x86's loop-weighted split-move estimate.
-**Cases D / X** counts measured dynamic program/target cases and x86 compilations;
-membership and inputs stay fixed across columns. Native-library work is excluded.
-Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each
-metric; see the [measurement details](../docs/regalloc-spills.md) for coverage.
-
-<!-- spill-matrix:start -->
-| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X |
-|---|---:|---:|---:|---:|---:|---:|
-| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 |
-| Ch 21 | 20 / 18 |  | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 |
-| Ch 22 | 14 / 8 |  |  | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 |
-| Ch 23 | 14 / 8 |  |  |  | 630 / 160 / 36 | 630 / 160 / 36 |
-| Ch 24 | 36 / 20 |  |  |  |  | 4,923 / 1,341 / 790 |
-<!-- spill-matrix:end -->
-