diff options
Diffstat (limited to 'chapter18/#README.md#')
| -rw-r--r-- | chapter18/#README.md# | 274 |
1 files changed, 0 insertions, 274 deletions
diff --git a/chapter18/#README.md# b/chapter18/#README.md# deleted file mode 100644 index 6d570d21..00000000 --- a/chapter18/#README.md# +++ /dev/null @@ -1,274 +0,0 @@ -# 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 `fidx` in the code. Function indices are -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` (there is no `void` in Simple), 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. - - -## 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); // BODY -} -``` - -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` (*link*) 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 *link* 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); ]` - - -### 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), shows up in [Chapter24](../chapter19/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. - -Like `Start`, `CallEnd`s are followed by projections for Control, Memory and the return value. - - - -## 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). - - -## Graph Visualizer - -Run `make view`, type your program in the text box, and click **Compile** -(or press **Ctrl+Enter**). Use the Left/Right arrow keys to step through graph -construction and optimization. See the [shared viewer guide](../graph/README.md). - -Nodes use colors and shapes for their graph roles: control, data, memory, Phis, -and scopes. This palette is distinct from the type-lattice diagrams. The viewer -also displays `ScopeNode`s, -which only exist for the Parser but are actual Nodes and have `use->def` edges -into the IR. - -## Memory across functions - -Each function has one `$mem` parameter and the parser keeps one memory binding. -Branches, loops, and multiple returns merge whole memory with BulkMemPhi. Field -uses discover precise MemPhis, while MemMerge packages a default memory state -and its alias overrides. MemMerge is an ordinary graph node; it no longer doubles -as a mutable parser alias table. - -| Boundary | Memory convention | -|---|---| -| Function entry | Parm 1 carries whole memory; heap contents are unknown | -| Call inputs | `{ctrl, $mem, arguments..., function pointer}` | -| CallEnd outputs | `{ctrl, $mem, value}` | -| Return inputs | `{ctrl, $mem, value, rpc}` | -| New inputs | `{ctrl, $mem, size, field values...}` | -| New outputs | `{ptr, $mem}`, covering only the allocated struct's aliases | - -A function may receive an existing object, so its entry memory cannot be treated -as an empty heap. Calls conservatively affect every alias. The returned memory -becomes the caller's new whole-memory state; there is no per-function alias -summary. Trivial inlining removes this boundary and lets the ordinary memory -rewrites see through the function body. - -Scheduling follows the relevant alias through MemMerge when looking for writes -or calls that must follow a Load. Calls end their basic block, so moving the Load -before that terminator supplies the required order without appending scheduling -edges to the argument list. Phi factoring keeps the simple one-step Load guard; -a direct Call user blocks that rewrite. |