diff options
Diffstat (limited to 'chapter-sccp')
8 files changed, 75 insertions, 346 deletions
diff --git a/chapter-sccp/#README.md# b/chapter-sccp/#README.md# deleted file mode 100644 index 9b973a09..00000000 --- a/chapter-sccp/#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 --> - diff --git a/chapter-sccp/.#README.md b/chapter-sccp/.#README.md deleted file mode 100644 index c657b199..00000000 --- a/chapter-sccp/.#README.md +++ /dev/null @@ -1 +0,0 @@ -cliffc@DESKTOP-DAD.21980:1790387027
\ No newline at end of file diff --git a/chapter-sccp/README.md b/chapter-sccp/README.md index c27b76e1..3b7599da 100644 --- a/chapter-sccp/README.md +++ b/chapter-sccp/README.md @@ -5,10 +5,9 @@ English | [日本語](README.ja.md) [Previous: Methods and Types](../chapter23/README.md) | [Next: SCCP Across Functions](../chapter-interprocedural-sccp/README.md) -This chapter introduces optimistic type analysis within each function. It -starts with the existing pessimistic peepholes, resets flow types to TOP, -then propagates reachable control and values to a fixed point. Calls keep -their conservative interfaces; discovering calls is the next chapter's topic. +This chapter introduces [SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation) +within each function. Next chapter, we'll go interprocedural with SCCP. + The [chapter split](../docs/chapter-split.md) uses names while the chapter boundaries settle. This is an independent compiler snapshot, extracted from diff --git a/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 71b9e495..7a24ca30 100644 --- a/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -189,6 +189,12 @@ public class CodeGen { // the return is not part of the match). final Ary<FunNode> _linker = new Ary<>(FunNode.class); + // Native symbols belong to function identities, not to one ExternNode. + // Selection and spill copies can turn that node into an ordinary constant. + private final HashMap<TypeFunPtr,String> _externs = new HashMap<>(); + public void externFunc(TypeFunPtr tfp, String name) { _externs.put(tfp.makeFrom(Type.BOTTOM),name); } + public String externFunc(TypeFunPtr tfp) { return _externs.get(tfp.makeFrom(Type.BOTTOM)); } + // Parser object public final Parser P; diff --git a/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java index b5a8e148..019e3892 100644 --- a/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java +++ b/chapter-sccp/src/main/java/com/seaofnodes/simple/codegen/Encoding.java @@ -138,6 +138,10 @@ public class Encoding implements com.seaofnodes.isa.CodeSink { } public Encoding relo( ConstantNode con ) { TypeFunPtr tfp = (TypeFunPtr)con._con; + // A native address has no local FunNode. Keep its symbol even after + // selection or a spill copy has replaced the original ExternNode. + String name = _code.externFunc(tfp); + if( name!=null ) return external(con,name); _internals.put(con,_code.link(tfp)); return this; } diff --git a/chapter-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/chapter-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java index ccbcfc66..7a26e2e9 100644 --- a/chapter-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java +++ b/chapter-sccp/src/main/java/com/seaofnodes/simple/node/ExternNode.java @@ -13,7 +13,11 @@ import java.util.BitSet; public class ExternNode extends ConstantNode { public final String _extern; - public ExternNode(Type t, String ex) { super(t); _extern = ex; } + public ExternNode(Type t, String ex) { + super(t); + _extern = ex; + if( t instanceof TypeFunPtr tfp ) CodeGen.CODE.externFunc(tfp,ex); + } @Override public String label() { return "#"+_con+":"+_extern; } diff --git a/chapter-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java b/chapter-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java index 98a56089..2c41dc57 100644 --- a/chapter-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java +++ b/chapter-sccp/src/main/java/com/seaofnodes/simple/node/cpus/arm/TFPARM.java @@ -39,8 +39,9 @@ public class TFPARM extends ConstantNode implements MachNode, RIPRelSize { int base = opStart & ~0xFFF; delta = target-base; int adrp_delta = delta >> 12; - // patch upper 20 bits via adrp - enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, adrp_delta >> 2, rpc)); + // ADRP splits a signed page offset into two unsigned bit fields. + // Mask the high field too, including for an address below this PC. + enc.patch4(opStart, Arm64.adrp(1, adrp_delta & 0b11, 0b10000, (adrp_delta >> 2) & 0x7FFFF, rpc)); // low 12 bits via add enc.patch4(opStart+4, Arm64.imm_inst_l(Arm64.OPI_ADD, delta & 0xfff, rpc)); } else { diff --git a/chapter-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java b/chapter-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java new file mode 100644 index 00000000..6d21ca5f --- /dev/null +++ b/chapter-sccp/src/test/java/com/seaofnodes/simple/NativeAddressTest.java @@ -0,0 +1,54 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.isa.eval.EvalArm64; +import com.seaofnodes.isa.eval.EvalRisc5; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Test; +import static org.junit.Assert.*; + +public class NativeAddressTest { + @Test public void testReturnedNativeAddress() throws IOException { + Path dir = Path.of("build/objs"); + Files.createDirectories(dir); + Files.writeString(dir.resolve("nativeAddress.smp"), """ + val getAbs = { -> + { i32 -> i32 } abs = "C"; + return abs; + }; + """); + Files.writeString(dir.resolve("nativeAddress.c"), """ + typedef int (*func)(int); + extern func getAbs(void); + int main(void) { + func f = getAbs(); + return f(-7) != 7 || f(9) != 9; + } + """); + TestC.run("build/objs", "nativeAddress", "", -1); + } + + @Test public void testEmulatedNativeAddress() throws IOException { + // No native call: return the address itself, patched to the emulator's + // known write entry. Both ports share Encoding's symbol lookup. + String src = "{ int -> int } write = \"C\"; return write;"; + for( String cpu : new String[]{"arm","riscv"} ) { + CodeGen code = new CodeGen(src).driver(cpu,"SystemV",null); + byte[] bits = code._encoding.bits(); + byte[] image = new byte[1<<20]; + System.arraycopy(bits,0,image,0,bits.length); + if( cpu.equals("arm") ) { + EvalArm64 eval = new EvalArm64(image,1<<16); + assertEquals(0,eval.step(100)); + assertEquals(Encoding.SENTINEL_WRITE,eval.regs[0]); + } else { + EvalRisc5 eval = new EvalRisc5(image,1<<16); + assertEquals(0,eval.step(100)); + assertEquals(Encoding.SENTINEL_WRITE,eval.regs[10]); + } + } + } +} |