path: root/chapter18/README.md

# Chapter 18: Functions

[Previous: Chapter 17b](../chapter17b/README.md) |
[Next: Chapter 19](../chapter19/README.md)


# Table of Contents

1. [FunctionTypes](#function-and-rpc-types)
2. [Return Program Counters](#return-program-counters)
3. [Functions](#functions)
4. [CodeGen - The Compile Driver](#codegen---the-compile-driver)
5. [Graph Visualizer](#graph-visualizer)
6. [Memory across functions](#memory-across-functions)

You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter18) 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-chapter17b...linear-chapter18) it to the previous chapter.

I hardly know where to begin!  So many things changed here, mostly as indirect
consequences of supporting functions.

Highlights of the changes:

- Function types, and a rework of the type lattice diagrams.
- Return Program Counter types, or Return PC or RPC for short.
- A distinguished `null` which can be used for functions, RPCs and struct pointers.
- Functions themselves can be parsed and evaluated; recursive functions are supported.
- Function calls work, call sites can link, and functions can be inlined.
- The top-level is now a call to function `main`, and this changed most tests.
- A top-level compile driver, which enforces optimization steps.
- A local scheduler.
- A new evaluator which relies on code motion, both global and local.
- A graphic animated viewer for peepholes.

Functions are *not* closures in this chapter; that brings about far more
changes and subtle complexities than sensible for such a large chapter.

Functions can only refer to out of scope variables if they are some final
constant.  This generally includes e.g. recursive function pointers.


## Function and RPC Types

```
{ argtype, argtype, ... -> rettype }
```

A leading `{` character denotes the start of a function or function type, then
a list of argument types, and an arrow `->` and the return type.

Function variables are normal variables and assigned the same way:

`functiontype fcn = function-typed-expr;`

and function typed variables can be inferred, so `val` and `var` on the left
hand side is fine:

`val sq = { int x -> x*x; };`

Internally, functions have a `TypeTuple` for the arguments, a return `Type`,
and a *function index* spelled as a `fidx` in the code.  Function indices are
unique small dense integers, one per unique function.  They are mapped
1-to-1 to the final code address of the generated function code.

Function pointers can refer to more than one function with the same signature,
and the `TypeFunPtr` tracks this as a bit set with the same tuple for signature
and return.

Function types can be `null` just like references.

Functions cannot return `void`, but they can return `null` and have their
return value ignored.  A syntactic sugar for void returns may be added in the
future.


### Return Program Counters

Just like functions have a unique "function index" mapped one to one with
function start addresses, call sites generate a unique "return program
counter", one per unique call site.  These are required for the evaluator to return
from functions without itself relying on the implementing language's
(e.g. Java) stack.  This is the type for such values and `TypeRPC` is very
similar to a `TypeFunPtr` except that the signature doesn't matter.

In spirit, this is part of a `continuation` and would be required to do IR
analysis of a hypothetical `call/cc` operation.  That is outside our current
scope, so for now these are only used in the evaluator.


Parameters use the explicit declaration syntax from
[Chapter 17a](../chapter17a/README.md): `!Point p` allows writes through a fixed
parameter binding, `Point !p` allows reassignment of a read-only reference,
and `int ~limit` fixes a primitive parameter. Inferred `var`/`val` parameters
are not supported.

## Functions

Functions themselves use the same syntax as function types, but filled in:

```
{ flt x, flt y ->  // Signature
  sqrt(x*x+y*y);   // Body
}
```

Used in a declaration statement:
```
// TYPE        VAR  =   EXPR
{flt,flt->flt} dist = { flt x, flt y ->
  sqrt(x*x+y*y);
}
```

With `var`:
```
var dist = { flt x, flt y -> sqrt(x*x+y*y); }
```

Functions are called in the usual way:
`dist( 1.2, 2.3 ) // yields 2.59422435`

Functions can have zero arguments, in which case the `->` argument separator is
optional.  This allows any section of code to be "thunked" by wrapping it in
`{}`.

`just5 = { -> 5 } // With    arrow`

`just5 = {    5 } // Without arrow`

Called:
`just5() // Returns 5`

Functions are always anonymous.  When finally assigned to a variable, they will
pick up the variable name for debugging and display purposes, but this has no
semantic meaning.  Here is a function variable referring to more than one
anonymous function; the resulting function either doubles or squares:

`val fcn = arg ? { int x -> x+x; } : { int x -> x*x; };`

`fcn(3) // Prints either 6 or 9, depending on arg`

Functions can be recursive:
```
val fact = { int n ->
  n <=1 ? n : n*fact(n-1);
};
return fact(4); // Returns 4! or 24
```

You can early return as normal out of functions:
```
val find = { int[] es, int e ->
  for( int i=0; i<es#; i++ )
    if( es[i] == e )
      return i;  // Found matching element, return the index
  return -1;     // Return -1 for not-found
};
return find;
```

`FunNodes` define functions, have a pointer to the one `ReturnNode` (which
itself has a back pointer to the `Fun`), extend a `RegionNode` and are followed
by `ParmNodes` which themselves extend `PhiNodes`.  All `Calls` which reach a
`Fun` merge all their arguments into the `Parms`; there is an extra `Parm` for
memory and for the return point back to the `CallEnd`: a RPC.  So a `Fun` is
basically a fancy merge point, merging all calls that reach here.

Unlike prior chapters, all the `returns` from a single function are gathered
together into a single `ReturnNode` point, and they must all be of the same
general type.  `Returns` take in a Control, a Memory, a return value, and the
`RPC` that was handed to the function when called.

When looking at the returned IR, the `StopNode` now reports one return for each
function, including `main`:
`Stop[ return find; return Phi(Region,int,-1); ]`

### Functions and Memory

Functions start with all of memory on a `Parm` (which extends `Phi`) and having
an argument `_idx` of 1, and return all of memory on the `Return` whioh takes
as inputs `{Control, Memory, Expr, RPC}` - except for the new `RPC`, unchanged
from before.  In the middle of the function, the normal alias slicing proceeds,
sharpening memory information locally.  A later chapter will introduce the
notion of *escaped* aliases, and allow simple functions to not take in and
clobber all of memory.


## Calls

Calls have the usual syntax: `fcn(3)`.  Internally a `CallNode` takes in
Control, Memory, all the normal arguments, and a hidden last argument which is
the function pointer.  For calls to named functions this last argument will be
a `ConstantNode` of the named function type, but in general it can be the
result of any function-typed expression.

The call arguments passed to the matching `ParmNode`s in the function,
with the `Call`s constant `RPC` being passed to the matching RPC `Parm`.

After a `Call` is a `CallEndNode`, internally abbreviated as `cend`.  The
`CallEnd` will take the `Call` as an input, and also every *linked* function:
functions the call-site *knows* it will call.  This will be expanded later to
be a conservative approximation to the *Call Graph*, with each `CallEnd`
*linked* to every function it *may* call; if a function is not linked it can
not be called from here.  This requires a global analysis (fast, cheap,
incremental, and global) which shows up in [Chapter24](../chapter24/README.md),
[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation).
So for the moment we only link exact constant functions.

If a call site is linked to a single function, and that single function is only
called by this one call site (its function pointer is only used here, obvious
from GVN) then the function inlines in the IR.

[edit note: needs before/after graph of trivial inlining]

Like `Start`, `CallEnd`s are followed by projections for Control, Memory and the return value.


### Calls and Linking

When Simple starts parsing code, the target of a call is generally unknown;
likewise a function has to assume any call can reach it.  This is a very weak
knowledge about a Call Graph, and this knowledge usually gets sharper very
quick: most calls are to known fixed functions... but not always.  And for
functions, its generally harder to know that a function pointer is never called.

So taking these contrainsts together, we can imagine building a call graph by
linking all call sites to all functions.  Here *linking* means the actual call
arguments are fed into the `Parm`s for the functions; the function `Return`
feeds into the `CallEnd`, and we can imagine flowing type information across
the caller/callee border.  But this immediately requires `O(n^2)` edges - 
every call is linked to every function, and there are `O(n)` of each.  

To avoid this `O(n^2)` graph growth, Simple assumes that all calls *start*
linked to all functions, we just don't include the edges (yet).  `FunNode`
includes a `hasUnknownCallers` call just for this situation, and this
means all `Parms` on all functions assume the worst possible callers will
be calling... so their arguments all default to their known types.

Similarly, all `Calls` assume they call all functions, and take return
values from all functions... so their return type is computed from 
their function signature instead of from some actual `Return`.

If we later discover a sharp target for a call (i.e., any call to a named
function, such as `fcn(3)`), we can refine the returned value to what the
function actually returns - maybe e.g. the function ends in `return null;` and
the CallEnd can use that information!  Similar for functions, if the function
is private, and never escapes, we might discover that its called from a limited
set of places - and so its arguments might be more precisely known.

In the same SCCP mentioned above we will refine the set of function pointers
flowing around the graph, and thus **who** calls **what**.  At that point we
generally do NOT have an `O(n^2)` Call Graph, so we will make the prior assumed
call edges "all-calls-all", into concrete and precise edges, building a real
Call Graph (which we will promptly use to optimize across function/call
borders).  This all comes in [Chapter24](../chapter24/README.md).  For now,
we assume all-calls-all unless we can locally prove otherwise, and our
calling situation remains very conservative.


### Calls and Memory

Calls take in all of memory, and return all of memory - a very conservative
approach.  Inlining can sharpen the alias information (at the cost of code
growth), via the normal memory peepholes applying to a larger and less
constrained graph (no Call after inlining!).  Like the functions above, a later
chapter will explore the notion of escaping aliases, and can allow call sites
to be less conservative about memory.


## CodeGen - The Compile Driver

There is now a top-level compile driver that enforces a phase ordering, and
allows multiple compilations; the Fuzzer uses this to compare various generated
programs.  The phases (for now) are:

- *Parse* - Convert program text to Simple IR
- *Opto* - General optimizations; for now iterate peepholes.
- *TypeCheck* - Error checking after all types have propagated.  This mostly
  reports on failed null checks.
- *Schedule* - Global Code Motion scheduler.  After this phase, all nodes belong
  in some basic block, with the normal suspect CFGNodes being basic blocks.
- *LocalSched* - a local scheduler.  It's completely naive, except it enforces
  some required rules: Phis appear at block heads, branches at block exits.
  There's room in the algorithm for a much more sophisticated list scheduler.
  The `Eval2` evaluator requires this information.
- *RegAlloc* - Not implemented (yet).

Several globals moved from the Parser to CodeGen, and probably several others
ought to move here.

There is a very nice `toString()` here; hovering over the `code` variable in
the debug window will pretty-print the IR "as if" globally scheduled, and the
code becomes very readable.


## Eval2 - A new Evaluator

There is now a second evaluator that uses the scheduling information to
evaluate in a very straightforward way.  Essentially the normal IR nodes are
treated like a special "machine instruction set" with infinite registers, and a
globally correct schedule.  This evaluator supports functions and calls (and
recursive calls).