# SCCP Within a Function 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. The [chapter split](../docs/chapter-split.md) uses names while the chapter boundaries settle. This is an independent compiler snapshot, extracted from Chapter 24. The numbered snapshot remains a comparison baseline. ## 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); } ``` ## Convergence and calls Integer ranges can grow one value per loop trip. A loop Phi widens its range after a bounded number of such steps. Constants stay precise; above-center ranges must remain narrow so they can fall to constants monotonically. During SCCP, each function retains its unknown-caller Start input. Call edges are disconnected, and call results keep the summaries already established by pessimistic analysis. Those summaries can be sharper than the written signature, so discarding them would lose valid facts. Calls still carry whole-memory effects. The solve discovers no new call edges. After the solve, ordinary peepholes relink calls and apply inlining as before. FinalizeIR removes uncalled bodies and detaches calls for scheduling. This separates local optimistic analysis from the existing pessimistic call machinery. `SccpTest` checks a loop fixed point and a function called with 1 and 2: its parameter remains general here, while the following chapter infers [1,2]. A recursive function whose return type needs optimistic propagation through calls can still report "No defined return type" here. The next chapter adds that inference and the widening needed to make it converge; its `Chapter24Test.testRecursiveWidening` exercises both recursive data cycles. ## Building and checking Run `make lib` once for Java test dependencies, then `make tests` in this directory. From the repository root, use `make tests CHAPTERS=chapter-sccp`. The inherited tests retain their historical class names. The [grammar](docs/24-grammar.md) includes chained comparisons inherited from the extraction baseline. Their planned teaching home is with short-circuit expressions. Allocator tuning is covered separately by the planned appendix.