summaryrefslogtreecommitdiff
path: root/chapter24/README.md
diff options
context:
space:
mode:
Diffstat (limited to 'chapter24/README.md')
-rw-r--r--chapter24/README.md239
1 files changed, 126 insertions, 113 deletions
diff --git a/chapter24/README.md b/chapter24/README.md
index ceb7e03e..e647bec3 100644
--- a/chapter24/README.md
+++ b/chapter24/README.md
@@ -10,125 +10,16 @@ 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).
+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.
-## 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
@@ -167,7 +58,7 @@ 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.
+The following is SSA pseudocode:
```text
int x0 = 1; // x0 = 1
@@ -289,6 +180,128 @@ 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