diff options
| -rw-r--r-- | chapter18/#README.md# | 274 | ||||
| -rw-r--r-- | chapter18/README.md | 558 | ||||
| -rw-r--r-- | chapter18/docs/Makefile | 13 | ||||
| -rw-r--r-- | chapter18/docs/inline-after.json | 101 | ||||
| -rw-r--r-- | chapter18/docs/inline-after.svg | 81 | ||||
| -rw-r--r-- | chapter18/docs/inline-before.json | 276 | ||||
| -rw-r--r-- | chapter18/docs/inline-before.svg | 117 |
7 files changed, 884 insertions, 536 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. diff --git a/chapter18/README.md b/chapter18/README.md index d0ee46c6..2daff473 100644 --- a/chapter18/README.md +++ b/chapter18/README.md @@ -1,301 +1,359 @@ -# Chapter 18: Functions +# Chapter 18: Functions and Calls [Previous: Chapter 17b](../chapter17b/README.md) | [Next: Chapter 19](../chapter19/README.md) +Through Chapter 17b, a program has one body, with an input `arg` and a result. +We can branch, loop, allocate objects, and update memory, but cannot yet break +up the program into functions. This chapter adds function values and calls, +including recursive calls. -# Table of Contents +The graph representation builds on familiar pieces. A function entry is a +Region, its parameters are Phis, and its exits merge into one Return. Calls +connect these pieces across function boundaries. When a function has just one +caller, removing that boundary lets ordinary peepholes simplify the combined +graph: this is our first form of inlining. -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) +## Table of Contents + +1. [Writing functions](#writing-functions) +2. [Functions in the graph](#functions-in-the-graph) +3. [Memory across calls](#memory-across-calls) +4. [Function types and call targets](#function-types-and-call-targets) +5. [Inlining](#inlining) +6. [Scheduling and execution](#scheduling-and-execution) 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. +## Writing functions -Highlights of the changes: +A function expression lists typed parameters, followed by `->` and a body: -- 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. +```simple +val sq = { int x -> x*x; }; +return sq(arg); +``` -Functions are *not* closures in this chapter; that brings about far more -changes and subtle complexities than sensible for such a large chapter. +The initializer creates a function value; the declaration binds it to `sq`. +The call `sq(arg)` evaluates its argument, executes the body with that value +bound to `x`, and yields the result. The final expression supplies the result +when execution reaches the end of the body. An explicit `return` can exit +earlier. -Functions can only refer to out of scope variables if they are some final -constant. This generally includes e.g. recursive function pointers. +A function type lists the parameter types and result type, without parameter +names. The same square function can be declared with an explicit type: +```simple +{int -> int} sq = { int x -> x*x; }; +return sq(4); // 16 +``` -## Function and RPC Types +Functions are anonymous values. Assigning one to a variable can give it a name +for diagnostics, but the binding follows the same rules as other variables. +`val` infers a fixed binding; `var` infers a reassignable one. Functions can +be passed as arguments, returned as results, and selected by expressions. -``` -{ argtype, argtype, ... -> rettype } -``` +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. Parameter types are required; +`var` and `val` apply to the variable holding a function, not its parameters. -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. +### Returns and scope -Function variables are normal variables and assigned the same way: +The body has the same statements as the surrounding language. Here an early +return finds the first matching array element: -`functiontype fcn = function-typed-expr;` +```simple +val find = { int[] es, int e -> + for( int i=0; i<es#; i++ ) + if( es[i] == e ) + return i; + return -1; +}; +val es = new int[3]; +es[0] = 7; +es[1] = 9; +return find(es,9); // 1 +``` -and function typed variables can be inferred, so `val` and `var` on the left -hand side is fine: +All reachable results of one function must have a common type. This is checked +after optimization, so an unreachable return does not cause a type error. +There is no `void` type although a function can return `null` with no syntax, +and callers can ignore a result by using the call as a statement. -`val sq = { int x -> x*x; };` +Functions do not capture an enclosing function's local variables. An outer +binding is accessible only when it is fixed and its value is a compile-time +constant. For example: -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. +```simple +val offset = 2; +val addOffset = { int x -> x+offset; }; +return addOffset(arg); +``` -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. +Changing `val offset` to `int offset` makes the binding mutable and the function +definition is rejected. Likewise, `val offset = arg` is fixed but not constant, +so it cannot be used from the nested function. Fixed function constants satisfy +this rule, allowing one function to refer to another without capturing a frame. -Function types can be `null` just like references. +### Recursion -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. +A function can refer to its own binding: +```simple +val fact = { int n -> + n <= 1 ? 1 : n*fact(n-1); +}; +return fact(arg); +``` -### Return Program Counters +The parser registers the function entry before parsing its body. A forward +reference to `fact` is resolved when the declaration receives its function +value. Recursive calls can then find the same entry as calls from outside. +Return-type inference is still pessimistic in this chapter; mutually recursive +definitions can require the stronger analysis introduced with SCCP in +[Chapter 24](../chapter24/README.md). + +## Functions in the graph + +Until now, `Start` supplied the input to one program body. We now parse that +body as an implicit `main` with an integer parameter `arg`. The evaluator +enters `main` from `Start` and delivers its result to the outside world. +Existing programs therefore keep their source syntax while acquiring the same +function representation as explicitly declared functions. + +### Entries, parameters, and exits + +[FunNode](src/main/java/com/seaofnodes/simple/node/FunNode.java) extends +`RegionNode`. Where a Region merges control from different branches, a Fun +merges control from different callers. A linked call supplies one incoming +control edge. + +[ParmNode](src/main/java/com/seaofnodes/simple/node/ParmNode.java) extends +`PhiNode`. Each parameter selects the argument belonging to the incoming call, +just as a Phi selects the value belonging to an incoming branch. The parameter +index identifies what the caller supplies: + +| Parameter index | Value | +|---|---| +| 0 | Return point: where execution resumes in the caller | +| 1 | Whole memory | +| 2 onward | Source-language arguments | + +Each function also has an implicit unknown caller, represented by `Start`. +It supplies the declared parameter types and unknown memory. This keeps the +entry conservative while calls are still being discovered. + +Every source-level `return` contributes to one exit Region. A value Phi merges +the results, and a BulkMemPhi merges their memory states. The resulting +[ReturnNode](src/main/java/com/seaofnodes/simple/node/ReturnNode.java) has inputs +`{control, memory, value, return point}`. A single exit often folds away the +Region and Phis. `Stop` retains the functions' Returns, including `main`'s. + +This gives each function a single entry and a single merged exit even when its +body contains branches, loops, and several return statements. + +### Calls and return points + +[CallNode](src/main/java/com/seaofnodes/simple/node/CallNode.java) takes inputs +`{control, memory, arguments..., function pointer}`. The final input determines +the target; it can be a constant function or the result of a function-valued +expression. Argument expressions are evaluated before the Call takes its +control and memory inputs. + +Each Call has a [CallEndNode](src/main/java/com/seaofnodes/simple/node/CallEndNode.java), +the point where its caller continues. CallEnd takes the Call and the Returns +of linked targets as inputs. Its projections provide control, memory, and the +result, in slots 0, 1, and 2 respectively. + +The callee needs to know which CallEnd to return to. Its hidden parameter 0 +carries that return point through the body to the Return. `TypeRPC`, short for +*return program counter*, describes sets of possible return points, much as +function-pointer types describe sets of possible entries. These are internal +values; a source program does not declare RPC variables. + +Call-graph edges describe which functions a call may reach. They are distinct +from the control flow within one function: walking the graph typically requires +taking care around calls and functions, as most walks are only valid from within +a single function. + +## Memory across calls + +Earlier chapters split memory lazily by field alias. That still happens within +a function, but a function's entry memory is unknown: an argument may refer to +an object allocated and modified by its caller. We can no longer assume that +the incoming heap is empty. + +A Call receives the complete memory state, including any slices packaged in a +MemMerge. Its CallEnd produces a new whole-memory value. This chapter treats +every call as potentially modifying every alias; knowing which function is +called does not yet provide a summary of which fields it writes. + +```simple +struct Counter { int n; }; +val bump = { !Counter p -> p.n++; return null; }; +val p = new Counter; +int before = p.n; +bump(p); +bump(p); +return before*10+p.n; // 2 +``` -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. +The first read of `p.n` observes its initialized value. The final read must use +memory after both calls; it cannot reuse the first read. The two calls also +remain ordered by their memory inputs and outputs. The writable parameter +permission allows the updates, while the memory edges record when they occur. -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. +Inside a function, MemMerge, MemPhi, and BulkMemPhi continue to expose precise +slices and merge branch or loop states. At the boundary, memory Parm 1 and the +CallEnd memory result stay opaque. Global code motion respects a call as a +possible writer when placing Loads. Calls end their blocks, so a Load that +must precede a Call is scheduled before that terminator. +Inlining removes the call boundary and exposes its actual Loads and Stores +to the existing alias optimizations. More precise effects for calls that remain +in the graph require later escape analysis. -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. +## Function types and call targets -## Functions +[TypeFunPtr](src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java) records +an argument tuple, a result type, nullability, and a set of function indices +(`fidxs`). Within an argument signature, each function gets a small integer +index. A bit set can then describe one known function or several possible +functions with that signature. `CodeGen` maps a concrete function identity to +its FunNode; no machine code address is needed to execute this chapter's IR. -Functions themselves use the same syntax as function types, but filled in: +For example, both arms below have type `{int -> int}`, but different function +indices: -``` -{ flt x, flt y -> // Signature - sqrt(x*x+y*y); // Body -} +```simple +val f = arg ? { int x -> x+x; } : { int x -> x*x; }; +return f(3); // 6 when arg is nonzero, otherwise 9 ``` -Used in a declaration statement: -``` -// TYPE VAR = EXPR -{flt,flt->flt} dist = { flt x, flt y -> - sqrt(x*x+y*y); -} -``` +The Phi for `f` combines the two function-pointer types. Its set of targets +contains both functions; choosing a function does not execute its body. -With `var`: -``` -var dist = { flt x, flt y -> sqrt(x*x+y*y); } +Function pointers can also be nullable, using the familiar `?` suffix: + +```simple +{int -> int}? f = arg ? { int x -> x*x; } : null; +if( f ) return f(3); +return 0; ``` -Functions are called in the usual way: -`dist( 1.2, 2.3 ) // yields 2.59422435` +The guard proves the pointer non-null at the call. A call also checks its +argument count, types, and access permissions. Struct pointers and function +pointers share the distinguished `null` value, represented by `Type.NIL`; +`TypeNil` supplies their common nullability machinery. -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 -`{}`. +### Linking known targets -`just5 = { -> 5 } // With arrow` +Here *linking* means adding IR edges between a call and a function. It is not +object-file linking. For each known target, the compiler adds the Call as an +input to the Fun, adds arguments to its Parms, and adds its Return as an input +to the CallEnd. Corresponding input positions preserve the relationship +between a caller and its arguments. -`just5 = { 5 } // Without arrow` +This chapter already links finite sets of known targets, including both +functions in the conditional example above. The infinite set that still +includes unknown functions cannot be enumerated. We avoid representing that +uncertainty with edges from every call to every function, which would grow +quadratically. -Called: -`just5() // Returns 5` +Instead, a Fun retains its *unknown-caller* input. Its parameters must accept +their declared types even when the calls found so far pass constants. Finding +one caller is not proof that no other callers exist! Similarly, CallEnd obtains +its result type from the function-pointer type and keeps its memory result +unknown. Linked Return edges alone do not remove these conservative assumptions. -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: +Inlining relies on a local proof that a function has only one caller. The later +SCCP chapter develops stronger analysis of which functions and calls are +reachable, allowing more information to flow across boundaries that remain. -`val fcn = arg ? { int x -> x+x; } : { int x -> x*x; };` +## Inlining -`fcn(3) // Prints either 6 or 9, depending on arg` +Consider a function whose value is used by exactly one call: -Functions can be recursive: -``` -val fact = { int n -> - n <=1 ? n : n*fact(n-1); -}; -return fact(4); // Returns 4! or 24 +```simple +val inc = { int x -> x+1; }; +return inc(arg); ``` -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; +Once this call links to `inc`, CallEnd can prove that it has one target and +that the target has no other uses of its function pointer. With valid +arguments and no self-recursive call, the function body can become part of +the caller. + +| Before inlining | After inlining | +|---|---| +|  |  | + +These are schematic slices of the graph, with stable node IDs across the +rewrite. They show the argument, result, and linking edges; the surrounding +control flow, memory, and RPC plumbing are omitted. The `int` input to `Parm_x` +represents the unknown caller's argument before inlining. + +The rewrite removes the unknown-caller path and connects the function entry to +the call's incoming control. Ordinary Region and Phi simplifications then +replace the parameter with the actual argument. CallEnd's projections become +the callee's returned control, memory, and value. The Call, function boundary, +and return-point machinery disappear as their uses disappear. + +The Add remains, but now consumes `arg` directly. If the argument had instead +been `3`, the same constant-folding rules used since Chapter 2 would produce +`4`. Loads and Stores exposed by inlining can similarly simplify using the +existing memory rules. + +This form of inlining moves a body with one caller into that caller; it does +not clone the body for several call sites. A recursive function such as +`fact` retains its calls and is handled by the evaluator. + +## Scheduling and execution + +New in this chapter is +[CodeGen](src/main/java/com/seaofnodes/simple/CodeGen.java) which owns the +compilation process and its function lookup table. It enforces the phase order: + +| Phase | Purpose | +|---|---| +| Parse | Build the functions and calls directly in the IR. | +| Opto | Iterate peepholes, including call linking and trivial inlining. | +| TypeCheck | Check the surviving graph after types and dead control have settled. | +| Schedule | Use global code motion to place operations in basic blocks. | +| LocalSched | Order operations within each block for execution. | + +For example: + +```java +CodeGen code = new CodeGen("val sq = { int x -> x*x; }; return sq(arg);"); +code.parse().opto().typeCheck().GCM().localSched(); ``` -`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). +Global code motion extends the work of [Chapter 13](../chapter13/README.md) to +multiple functions. It keeps their bodies separate, gives shared constant +expressions a local copy in each function that uses them, and respects memory +effects across calls. + +[ListScheduler](src/main/java/com/seaofnodes/simple/ListScheduler.java) then +orders each block. It counts unscheduled local dependencies, chooses a ready +operation, and makes its users ready as their dependencies are satisfied. Phis +belong at entry and control transfers at exit. There is room for all sorts of +improvements - there is no machine timing model here, but this is out of scope +for this chapter. The goal remains a legal execution order. + +[Eval2](src/test/java/com/seaofnodes/simple/Eval2.java) executes that schedule, +treating IR operations as instructions with an unlimited supply of value +slots. Each invocation has its own frame, so recursive invocations of the same +nodes keep distinct values. At a call it saves the caller's frame and return +point, creates a callee frame, and transfers to the selected function. At a +return it restores the caller and delivers the value to its CallEnd. At a +Region, it reads all selected Phi inputs before assigning any results, so +parallel assignments remain correct. + +We now have an executable program made of scheduled functions, still expressed +in machine-independent operations. [Chapter 19](../chapter19/README.md) inserts +instruction selection before scheduling: those ideal operations become +instructions for a chosen CPU, with its register constraints and calling +convention. diff --git a/chapter18/docs/Makefile b/chapter18/docs/Makefile index 12659b8f..6fa0f057 100644 --- a/chapter18/docs/Makefile +++ b/chapter18/docs/Makefile @@ -1,12 +1 @@ -GV := $(wildcard *.gv) -SVG := $(patsubst %.gv,%.svg,$(GV)) - -.PHONY: all -all: $(SVG) - -%.svg: %.gv - dot -Tsvg $< > $@ - -.PHONY: clean -clean: - @rm -f $(SVG) +include ../../graph/docs.mk diff --git a/chapter18/docs/inline-after.json b/chapter18/docs/inline-after.json new file mode 100644 index 00000000..64e36e97 --- /dev/null +++ b/chapter18/docs/inline-after.json @@ -0,0 +1,101 @@ +{ + "ver": 1, + "comp": "inline", + "step": 2, + "roots": [ + 12 + ], + "scope": 0, + "nodes": [ + { + "id": 1, + "label": "Parm_arg", + "type": "int", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 2, + "label": "Con", + "type": "1", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 8, + "label": "Add", + "type": "int", + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 1, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 2, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 12, + "label": "Return main", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 8, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + } + ], + "groups": [] +} diff --git a/chapter18/docs/inline-after.svg b/chapter18/docs/inline-after.svg new file mode 100644 index 00000000..f376ce7f --- /dev/null +++ b/chapter18/docs/inline-after.svg @@ -0,0 +1,81 @@ +<svg aria-label="Compiler graph" width="332" height="312" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 332 312" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e8i1" d="M96,80 L96,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #1 · DATA</title></path><path class="edge DATA" id="e8i2" d="M248,80 L248,85 Q248,90 243,90 L134,90 Q126,90 126,98 L126,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #2 · DATA</title></path><path class="edge DATA" id="e12i2" d="M96,184 L96,232" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#12[2] → #8 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(36,30)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Parm_arg</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60">int</text><title>#1 Parm_arg +int + +[0] → — ASSOC +[1] → — DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text></g><g class="node" id="n2" data-id="2" transform="translate(188,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Con</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60">1</text><title>#2 Con +1 + +</title></g><g class="node" id="n8" data-id="8" transform="translate(36,134)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Add</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60">int</text><title>#8 Add +int + +[0] → — CTRL +[1] → #1 DATA +[2] → #2 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n12" data-id="12" transform="translate(24,238)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return main</tspan><tspan class="node-id"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 Return main +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #8 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="white"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/chapter18/docs/inline-before.json b/chapter18/docs/inline-before.json new file mode 100644 index 00000000..243aff79 --- /dev/null +++ b/chapter18/docs/inline-before.json @@ -0,0 +1,276 @@ +{ + "ver": 1, + "comp": "inline", + "step": 1, + "roots": [ + 12 + ], + "scope": 0, + "nodes": [ + { + "id": 1, + "label": "Parm_arg", + "type": "int", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 2, + "label": "Con", + "type": "1", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 3, + "label": "Con inc", + "type": "{int -> int}", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 4, + "label": "Call", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 1, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 3, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 5, + "label": "inc", + "type": null, + "kind": "FUN", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 2, + "def": 4, + "role": "CTRL", + "label": null + } + ], + "proj": null + }, + { + "id": 6, + "label": "Con", + "type": "int", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 7, + "label": "Parm_x", + "type": "int", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 5, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 6, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 1, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 8, + "label": "Add", + "type": "int", + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 7, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 2, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 9, + "label": "Return inc", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 8, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 10, + "label": "CallEnd", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 4, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 9, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 11, + "label": "result", + "type": "int", + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 10, + "role": "DATA", + "label": null + } + ], + "proj": { + "par": 10, + "idx": 2 + } + }, + { + "id": 12, + "label": "Return main", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 11, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + } + ], + "groups": [] +} diff --git a/chapter18/docs/inline-before.svg b/chapter18/docs/inline-before.svg new file mode 100644 index 00000000..8e15f6ea --- /dev/null +++ b/chapter18/docs/inline-before.svg @@ -0,0 +1,117 @@ +<svg aria-label="Compiler graph" width="543" height="772" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 543 772" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e4i2" d="M96,80 L96,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#4[2] → #1 · DATA</title></path><path class="edge DATA" id="e4i3" d="M248,80 L248,85 Q248,90 243,90 L128,90 Q120,90 120,98 L120,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#4[3] → #3 · DATA</title></path><path class="edge CTRL" id="e5i2" d="M84,184 L84,189 Q84,194 89,194 L177,194 Q185,194 185,202 L185,232" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#5[2] → #4 · CTRL</title></path><path class="edge DATA" id="e7i1" d="M257,184 L257,189 Q257,194 262,194 L279,194 Q287,194 287,202 L287,232" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[1] → #6 · DATA</title></path><path class="edge DATA" id="e7i2" d="M96,80 L96,92 Q96,100 104,100 L319,100 Q327,100 327,108 L327,232" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#7[2] → #1 · DATA</title></path><path class="edge DATA" id="e8i1" d="M307,288 L307,336" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[1] → #7 · DATA</title></path><path class="edge DATA" id="e8i2" d="M459,288 L459,293 Q459,298 454,298 L345,298 Q337,298 337,306 L337,336" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#8[2] → #2 · DATA</title></path><path class="edge DATA" id="e9i2" d="M307,392 L307,440" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#9[2] → #8 · DATA</title></path><path class="edge CTRL" id="e10i0" d="M84,184 L84,544" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#10[0] → #4 · CTRL</title></path><path class="edge DATA" id="e10i1" d="M295,496 L295,501 Q295,506 290,506 L132,506 Q124,506 124,514 L124,544" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#10[1] → #9 · DATA</title></path><path class="edge DATA" id="e12i2" d="M104,644 L104,692" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#12[2] → #11 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(36,30)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Parm_arg</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60">int</text><title>#1 Parm_arg +int + +[0] → — ASSOC +[1] → — DATA</title><circle class="port" cx="0" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="white"/><text class="slot" x="0" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text></g><g class="node" id="n2" data-id="2" transform="translate(399,238)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Con</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60">1</text><title>#2 Con +1 + +</title></g><g class="node" id="n3" data-id="3" transform="translate(188,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Con inc</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60">{int -> int}</text><title>#3 Con inc +{int -> int} + +</title></g><g class="node" id="n4" data-id="4" transform="translate(24,134)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Call</tspan><tspan class="node-id"> #4</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#4 Call +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #1 DATA +[3] → #3 DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="white"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="#536477"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n5" data-id="5" transform="translate(95,238)" style="opacity: 1;"><path class="box" d="M10,0H110L120,10V34L110,44H10L0,34V10Z" fill="#ffe0ab"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>inc</tspan><tspan class="node-id"> #5</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#5 inc +Type not computed + +[0] → — ASSOC +[1] → — CTRL +[2] → #4 CTRL</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="white"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n6" data-id="6" transform="translate(197,134)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Con</tspan><tspan class="node-id"> #6</tspan></text><text class="type" text-anchor="middle" y="35" x="60">int</text><title>#6 Con +int + +</title></g><g class="node" id="n7" data-id="7" transform="translate(247,238)" style="opacity: 1;"><path class="box" d="M12,0H108L120,22L108,44H12L0,22Z" fill="#f5e4fa"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Parm_x</tspan><tspan class="node-id"> #7</tspan></text><text class="type" text-anchor="middle" y="35" x="60">int</text><title>#7 Parm_x +int + +[0] → #5 ASSOC +[1] → #6 DATA +[2] → #1 DATA</title><circle class="port" cx="-3" cy="22" r="3" fill="#536477"/><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><path class="reg" fill="none" stroke="#b63838" d="M-3,22H-18m4,-3l-4,3l4,3"><title>[0] → #5</title></path><text class="slot" x="-10" y="15" text-anchor="middle">0</text><text class="slot" x="40" y="-10" text-anchor="middle">1</text><text class="slot" x="80" y="-10" text-anchor="middle">2</text></g><g class="node" id="n8" data-id="8" transform="translate(247,342)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Add</tspan><tspan class="node-id"> #8</tspan></text><text class="type" text-anchor="middle" y="35" x="60">int</text><title>#8 Add +int + +[0] → — CTRL +[1] → #7 DATA +[2] → #2 DATA</title><circle class="port" cx="30" cy="-3" r="3" fill="white"/><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><circle class="port" cx="90" cy="-3" r="3" fill="#536477"/><text class="slot" x="30" y="-10" text-anchor="middle">0</text><text class="slot" x="60" y="-10" text-anchor="middle">1</text><text class="slot" x="90" y="-10" text-anchor="middle">2</text></g><g class="node" id="n9" data-id="9" transform="translate(235,446)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return inc</tspan><tspan class="node-id"> #9</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#9 Return inc +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #8 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="white"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g><g class="node" id="n10" data-id="10" transform="translate(44,550)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>CallEnd</tspan><tspan class="node-id"> #10</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#10 CallEnd +Type not computed + +[0] → #4 CTRL +[1] → #9 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g><g class="node" id="n11" data-id="11" transform="translate(44,594)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>result</tspan><tspan class="node-id"> #11/2</tspan></text><text class="type" text-anchor="middle" y="35" x="60">int</text><title>#11 result +Projection 2 of #10 +int + +[0] → #10 DATA</title></g><g class="node" id="n12" data-id="12" transform="translate(32,698)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return main</tspan><tspan class="node-id"> #12</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#12 Return main +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #11 DATA +[3] → — DATA</title><circle class="port" cx="24" cy="-3" r="3" fill="white"/><circle class="port" cx="48" cy="-3" r="3" fill="white"/><circle class="port" cx="72" cy="-3" r="3" fill="#536477"/><circle class="port" cx="96" cy="-3" r="3" fill="white"/><text class="slot" x="24" y="-10" text-anchor="middle">0</text><text class="slot" x="48" y="-10" text-anchor="middle">1</text><text class="slot" x="72" y="-10" text-anchor="middle">2</text><text class="slot" x="96" y="-10" text-anchor="middle">3</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> |
