# SCCP Across Functions

English | [日本語](README.ja.md)

[Previous: SCCP Within a Function](../chapter-sccp/README.md) |
[Next: SSA Before Types Are Known](../chapter-incomplete-types/README.md) |

The previous chapter runs SCCP with each function, and assumes very
conservative typing across calls.  This chapter lets the same worklist
discover call edges and propagate values between functions.  

## Discovering calls while solving types

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*, or *fidx*
internally, as described earlier chapters.  (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.

## Recursion is a loop in disguise

We use the notion of *widening* integer ranges at loop heads, see Chapter XXX.
This allows us to have a sharper notion of integers over `BOTTOM` without also
allowing the lattice to fall 2^32 times.  The same issue arises during
recursive calls: an argument can flow from a Parm through arithmetic into a
recursive call, then back to the same Parm.

```simple
val fact = { int x -> x ? 0 : f(x-1)+1; };
```

Here if we pass in `f(999)` , parameter `x` will have the integer range
`[999]`.  We'll then track the recursive call to `f(998)` via normal SCCP 
and realize the parameter `x` has a range `[999-998]`.  Lather, rinse, repeat 
and we're at `[999-997]`.  We need to *widen* integer parameters at `Parms`
not just loop-head `Phis`.  

The same issue arises during the recursive return: the first return will be
with `0` when `x` is zero, then we return `0+1` or the range `[0-1]` then range
`[0-2]`, etc.  `CallEnds` also need to widen.

Loop Phis, Parms, and CallEnds get widening points, and since this same issue
hits in 3 unrelated places, their comments all cross-reference each other.


## Unknown callers

A `FunPtrNode` (function address) that survives outside a direct call may be
called by code we cannot see.  We have to assume the address escapes into
unknown code, which later calls it.  We preserve its unknown-caller input,
since we cannot tell what that unknown caller will pass.  Precise escape
analysis is introduced later exactly to inmprove this.

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