From 84a70fd744f83e2d701e15fc3d17109eb59ac707 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Nov 2024 11:01:47 -0800 Subject: Chapter 18: Functions and Calls MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter18/README.md | 363 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 363 insertions(+) create mode 100644 docs/chapter18/README.md (limited to 'docs/chapter18/README.md') diff --git a/docs/chapter18/README.md b/docs/chapter18/README.md new file mode 100644 index 00000000..1306efb5 --- /dev/null +++ b/docs/chapter18/README.md @@ -0,0 +1,363 @@ +# Chapter 18: Functions and Calls + +English | [日本語](README.ja.md) + +[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. + +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. + +Here is the [complete language grammar](18-grammar.md) for this chapter. + +## 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. + +## Writing functions + +A function expression lists typed parameters, followed by `->` and a body: + +```simple +val sq = { int x -> x*x; }; +return sq(arg); +``` + +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. + +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 +``` + +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. + +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. + +### Returns and scope + +The body has the same statements as the surrounding language. Here an early +return finds the first matching array element: + +```simple +val find = { int[] es, int e -> + for( int i=0; i x+offset; }; +return addOffset(arg); +``` + +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. + +### Recursion + +A function can refer to its own binding: + +```simple +val fact = { int n -> + n <= 1 ? 1 : n*fact(n-1); +}; +return fact(arg); +``` + +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 +``` + +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. + +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. + +## Function types and call targets + +[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. + +For example, both arms below have type `{int -> int}`, but different function +indices: + +```simple +val f = arg ? { int x -> x+x; } : { int x -> x*x; }; +return f(3); // 6 when arg is nonzero, otherwise 9 +``` + +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. + +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; +``` + +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. + +### Linking known targets + +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. + +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. + +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. + +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. + +## Inlining + +Consider a function whose value is used by exactly one call: + +```simple +val inc = { int x -> x+1; }; +return inc(arg); +``` + +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 | +|---|---| +| ![The call supplies arg to inc's parameter and receives its sum.](inline-before.svg) | ![The same Add uses arg directly and supplies main's return.](inline-after.svg) | + +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(); +``` + +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. -- cgit v1.2.3