path: root/chapter24/README.md

# 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. Memory follows Chapter 11's lazy partitioning: BulkMemPhi represents
whole memory, MemPhi merges precise aliases, and allocations consume and produce
partial memory for their instance fields. During SCCP, memory Phis ignore
unreachable inputs and allocation results stay high until control reaches them.
Chapter 25 retains the larger incomplete-types SSA redesign, private constructor
memory, and separate compilation; see the [backport review queue](../docs/chapter-backports.md).


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.

## 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);
```



## 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; `phi` denotes a merge, not Simple syntax.

```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, and 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.


## 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.

Chapter 21's adjacent-copy forwarding also carries forward: after coloring,
a sole use in the next instruction can read the source register when its
operand mask permits it and no two-address tie is broken. The table below
includes this cleanup and the lazy memory forward port. Cohort 22 now also includes the two zero-move C return
ABI checks added since the earlier audit (26 entries instead of 24).

Run `make spill-stats`. All rows use **Chapter 24's compiler**, optimizer seed
123, and the same source/target combinations as the earlier cohort tables.
These Windows results combine x86 SystemV/Win64 and RISC-V/ARM SystemV,
remeasured after the lazy memory forward port.

| Program cohort | Compilations | Retained moves | Loop-weighted moves |
|---|---:|---:|---:|
| Chapter 20 | 39 | 320 | 439 |
| Chapter 21 | 52 | 420 | 952 |
| Chapter 22 | 26 | 67 | 67 |
| Chapter 23 | 30 | 78 | 225 |
| Chapter 24 | 67 | 422 | 1,325 |
| **Total** | **214** | **1,307** | **3,008** |

`_spills` counts retained SplitNodes, including register moves. `_spillScaled`
weights those moves by `8^loopDepth`; it is a cost estimate, not measured memory
traffic. Diagnostic machine graphs contribute no allocations to this table.
The reporter checks allocation legality and native/emulated results even when
spill expectations differ, and exits unsuccessfully for either kind of failure.

In the original 2026-09-20 allocator audit, before subsequent compiler fixes,
the table totaled 1,332 / 2,956. With only the cold-first rule disabled, that
compiler and the same programs produced
**1,338 moves / 2,962 weighted moves**. The rule saves six of each. A RISC-V
MergeSort case adds one move, offset by improvements in other MergeSort cases,
Sieve, and an ARM loop case. Aggregate measurements justify accepting that
local regression; the improvement here is modest, not universal.

On cohorts 20-23 alone in that audit, Chapter 23 produced 933 / 1,745; Chapter 24 produced
900 / 1,614. Only six of each reduction comes from this allocator change. The
rest comes from other compiler changes, including SCCP; comparing chapters
alone would overstate the heuristic's benefit.

The older cohorts retain the 64-bit Person, guarded String, and smaller emulator
argument list. Revised Jig, BubbleSort, Newton, and stack-argument inputs belong
to cohort 24 alongside this chapter's existing tests. The frozen String workload
also exposed a missing null check in the inlining dominator walk; that correctness
fix is included on both sides of the heuristic comparison. Area/cost spill
ranking remains for Chapter 25.

The current function-pointer rule keeps unknown callers whenever an address is
used as a value rather than only as a direct call target. This preserves callable
bodies without escape analysis, but Phi-selected functions retain general
parameter types. The no-return String case now drops its unused hash bodies and
needs no splits. Source/target membership remains unchanged; these graph changes
are separate from the cold-first allocator comparison above.