Chaining Conditionals and SCCP (#230)

* merge fixup

* More x86,risc,arm call convention fixes

Collect callee and caller save masks (inverts of each other, except for spills).
Reorg layout to be closer to each other; remove dead mask definitions; add final keyword

* lui fix up with 32 bit immediates

* Callee-save registers

Callee-save registers and masks and inserting LRGs for same and spilling and picking good spills.  Insert CalleeSaveNodes and edges to RetXXXs and RegMasks for those edges.
Iterators for regmask.
Better printing post-allocation

* RegMask supports 128 bits

All regs available arm, risc.
MergeSort compiles & runs

* added flags splitting

* Fix risc5 compares

No flags on risc5.
Branch takes 2 inputs (one can be imm12).
Float compare only sets a GPR to 0/1.
Bool has a isFloat
Common risc5 imm-form handling

* extend test cases

* imm encoding, flags fixed

* grep for Todo: relocs

* float riscv fixed

* flags for set

* lui fix for small bits [0, 12]

* arm init

* arm last touches

* fmov still needs fix

* minor fixes

* minor fixes(2)

* got rid of unnecessary stuff

* create ch21

* remove encodings from chapter20 dir

* 1/2 pass cleaning up ARM encoding API

* ARM encoding compiles

* Risc R_TYPE and I_TYPE

* Progress RISC encodings

Missing lots of stuff still

* progress risc encoding

* risc encodings compile

* Update README.md

* Fold up redundant OP/OP-FP risc5 encoding

* x86 mem opcodes first cut

break out MemOp encodings into parts; change x86 indirectAdr to use Encoding class, remove redundant asserts & code

* x86 mem op encodings

* x86 reg+imm forms

* most reg-reg forms

* More x86 encodings

* Last few encodings

* switch to binary literals over decimals for opcodes

* logical immediates fixed, bitwise ops imm forms

* tfp and setArm fixed

* PC relative float for riscv

* readme init

* Merged pr/169

* Fixed the array1 test encodings

Clean up branch invert logic during BB layout
Cleanup branch target printing for RISC,ARM
ImmRISC ops mask imm12 to 12 bits
Fix NewRISC; hardcode RPC as part of call
Fix RISC inverting branchs >,>=

* floatarm encoding

* tfparm and intarm

* uncontional jump encoding for arm and riscv

* smarter IntARM, Intx86 does not always include rex.

* REX after PREFIX

* fixup load and store indirect

* updated rex prefix, if its 0x40 then its not needed

* Rex fix for floats, got rid of unnecessary stuff.

* rename to camel case, better param name

* add test export

* merged

* store opt

* store and load optimised forms handled

* tfp patch

* Store/load float arm/riscv/x64

* got rid of debug print

* splits for x86, riscv and arm

* readme fixups

* fix global symbol numbering for constants

* fix TFP pathc on arm and riscv, keep symbols in good order.

* fix opcode for store and loads, memOpRisc for Store and splitting

* replace hard coded opcodes with major opcodes

* replace hard coded opcodes with major opcodes

* add asserts and fix reg numbering

* add asserts and fix reg numbering

* minor updates

* revert changes

* remove constant pool from encoder TODO: add flag for JIT

* extend test cases

* minor fixes

* minor fixes

* update float test case

* stringHash fix on x64

* remove conditional ConstantPool write

* brainfuck minor fixes

* minor arm fixes

* split fix

* brainfuck and fib

* brain fuck

* arg_count, person

* add ignore

* typo

* riscv test sieve attempt

* minor changes

* riscv5 emulator additions

* arm eval setup

* Update riscv.java

* arm eval basics

* delta fixes

* arm fixes

* testfib arm

* arg_count

* small update for test newton

* small update for test newton

* testNewton runs on x64, riscv and arm

* arm additions

* arm pc eval fix

* arm workings

* debugging

* Progress sieve on ARM

Most ops need WMASK as the output, to exclude RSP.
calloc sentinal changes to multiple of 4
NewArm needs to set arg X0 to #1; arg X1 is length.
Fix EvalARM calling calloc & not advancing PC.
Fix EvalARM using ints vs longs.
Fix EvalARM missing AndI encoding.

* Fix some arm encoding

Fix some OBOB in R5 calloc encoding.
Sort EvalArm by major opcodes.
Add ASL.  Remove leading switch.  Fix OBOB in calloc.
Fix shift in ld/st with reg+offset

* arm sieve test

* test person push

* brainFuck arm

* "and" "or" syntactic sugar

* update encoding

* ch23 `and` `or`

* hack parse trinary for and, or

* close

* fixed or issue

* Update CallEndNode.java

* fix type issue

* fixed

* Adjust parseTrinary precedence vs && ||

* Fix arm simulation return

* Formatting

* Formatting

* simplify rn to be always 0.

* ch24 init

* stacked rel

* stack init

* stack rel

* remove parenthesis

* got rid of old test case

* update

* upgrade eval

* arm encoding bugs

encodeing cset had a shift wrong
eval missed using 0 for r31

* remove debug prints

* force main to encode first

* fix for missing main

* got rid of debug prints

* backwards with ch23

* simple new test cases

* update test cases

* enable old test

* got rid of own test case

* fix test11

* inline Api

* inline x86_64

* inline test cases

* fix stacked_r_5

* got rid of redundant rdid -1 set

* Several new fuzzer addDeps/keep bugs.

Fix risc/arm spill code values for passing 20 args.

* Update README

Move ch23_ch24 branch into ROADMAP

* Create TypeAnalysis.md

* Update TypeAnalysis.md

* Update TypeAnalysis.md

* More lattices for main

* Update TypeAnalysis.md

* Update TypeAnalysis.md

* TypeAnalysis continued

* fix typos

* pointers

* typo fix in reader

* Update TypeAnalysis.md

* sccp first attempt

* test

* init

* still debug

* Update TypeAnalysis.md

* more examples

* More docs

* Update TypeAnalysis.md

* widen phi nodes in loops

* extra debug stuff for opto

* Work in progress opto pass

* Progress on opto

* opto missing deps

ConFldOff needs String.equals in `eq`
Fix monotonic xfer functions in
- CallENd, CProj, Load, Arith
Mostly if either TOP or BOT inputs, the output is the matching TOP or BOT

* push mid-progress

* progress sccp

* Make all the default parser integer types pre-widen

Function sigs to calls allow wide ints

* progress sccp

* Update TypeInteger.java

* progress SCCP

* Progress SCCP

* Progress SCCP

A series of minor fixes, generally making transfer functions monotonic, or p[reserving sanity for error test cases.

* Progress on opto

Most tests pass, a few failures remain.
Split Opto code into a seperate file.
Improve `compute` precision in several places showing up during opto.
bugfix: "split-thru-phis" on Parms changes calling conventions.  Not ready for that yet.

* most tests pass

Handle non-default main.
Simplify trivial inlining cutout test.
ParmNode excludes most Phi opts
Region idom excludes dead paths
RPC now interns

* Fix arm NOT encoding

* all tests pass

Float math handles high types monotonically
Minus node does not reset int widen.
Phi widen handles non-int mintype
Dead returns do not error complain.
Better handling default vs dead main

* If NewNode is high, produce high results

* BrainFuck uses a string

* README

* Update README.md

* Typos from copilot review

* monotonic fix MinusF

* Update TypeAnalysis.md

* Update TypeInteger.java

---------

Co-authored-by: Hadházy Tamás <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>

1 files changed, 197 insertions, 13 deletions

diff --git a/chapter24/README.md b/chapter24/README.md
index 268fbfcc..cd5693d4 100644
--- a/chapter24/README.md
+++ b/chapter24/README.md
@@ -1,11 +1,18 @@
-# Chapter 24: Chaining relationals and Sparse Conditional Constant Propagation
+# Chapter 24: Chaining Relationals and Sparse Conditional Constant Propagation
+
+In this Chapter we allow *chaining* conditionals, e.g. `(60 <= score < 90)`
+where `score` in the middle does not have to be repeated.
+
+We also present an Interprocedural Sparse Conditional Constant Propagation
+algorithm.
+
 
 You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter23) 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-chapter22...linear-chapter23) it to the previous chapter.
 
 
-## Chaining relationals
+## Chaining Relational Tests
 
-Chainged relationals offer a cleaner, more readable way to write chained
+Chaining relational tests offer a cleaner, more readable way to write chained
 comparisons without repeating the same variable.
 
 ```java 
@@ -29,22 +36,24 @@ if (60 <= score < 90) {
 ```
 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, because they create ambiguous logic.
+Expressions that mix opposite directions of comparison, like using both 
+`<=` and `=>`, are not allowed, because they create ambiguous logic.
 
 ```java
 if (a <= b >= c)
 ```
 
 
-## Operator direction rules
-Stacked comparisons are *only valid* if all the comparison operators
+### Operator direction rules
+Stacked comparisons are *only* valid if all the comparison operators
 "point" the same way:
 - `<` with `<`
 - `<` with `<=`
 - `>` with `>`
 - `>` with `>=`
 
+All operators above can be combined with `==` and `!=`.
+
 It is not allowed to mix directions in a single chain:
 ```java 
 if (a <= b >= c) // Invalid
@@ -76,14 +85,189 @@ 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.
+Equality(`==`) and inequality(`!=`) operators may be combined with any other comparisons at any point in the chain.
 
-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.
-Equality(`==`) and inequality(`!=`) operators may be combined with any other
-comparisons at any point in the chain. E.g:
-
+E.g:
 ```
 return 0 < arg < arg+1 < 4;
 ```
 
-## SCCP(top-down)
\ No newline at end of file
+### 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.
+
+Example:
+
+```java
+int x0 = 1;          // x0 = 1
+while( rand ) {
+    x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT)
+    x2 = 2 - x1;     // x2 = BOT = 2 - BOT
+}
+return x2
+```
+
+Without SCCP, this small program cannot remove the computation of `x` and hence
+the loop either.  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
+statemate, and just *assume* x1 is `1`, and then we can discover than x2 is
+also a `1`.
+
+
+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:
+
+Example:
+
+```java
+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 x4
+```
+
+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
+early 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.