curry.icurry.analysis.inlining module

Inlines calls of small functions, and calls of a single-case function on a known constructor.

Two rules of the optimizer rewrite a saturated call in place (see curry.interpreter.optimize.inline_calls):

• A call of a non-recursive function whose body is an expression of at most budget nodes is replaced by the body (ExpressionBody). The budget counts the nodes the body builds: calls, partial applications, constructors, choices, and literals; a variable is a reference and counts nothing. A body may bind local variables (a let or where that is not recursive) and declare free variables.

• A call g (K a b) of a non-recursive function whose body is one case on that parameter, with a branch for K, is replaced by the body of the branch (CaseBody). The fields of the constructor take the places of the pattern variables.

The sharing rule. Every substitution of an expression for a variable keeps the expression built once, as the call would have built it: an argument, a field, the whole constructor, or a local that is used more than once is bound to a fresh variable of the caller’s block (IVarDecl and IVarAssign) before the body is substituted; one that is used once is written at its use; one that is not used is dropped. Call-time choice demands it: g (0 ? 1) with g x = (x, x) yields (0, 0) and (1, 1), never (0, 1). When a body binds two variables to one parameter or to one field, their uses count together, since both name one argument. A variable, a literal, and a static string are written at every use. A free variable of the body becomes a fresh free variable of the caller’s block: one per inlined call, as one per call before. A choice in the body is one choice per call site, as one call per site.

The body that a call is replaced by is the body as the front end wrote it (after the saturation of apply chains), not the body after this pass rewrote it: the inner calls of the body are then rewritten in the context of the caller, where the arguments are known. So the dictionary chain of a class method on a constant dictionary resolves (section 4.2 (c) of the phase 3 plan): x /= y on Int becomes not (eqInt x y). The body is copied before the function is rewritten (inline_shape), and recorded under INLINE_KEY as ICurry-JSON when it is small enough, so that a module loaded from its compiled form, which has no bodies, still tells its small functions to the modules that import it.

Non-recursive means not on a cycle of saturated calls within the module: a cycle cannot cross modules, since imports are acyclic, and a body recorded by a compiled module was found non-recursive when the module was compiled. A partial application is a value, not a call: the dictionary of an instance names its methods, and a method that falls back to a class default names the dictionary, and both are inlined, which the dictionary chain needs. An apply that saturates such a partial is rewritten again to the depth MAX_DEPTH and no further. A public function records its body; a private one records it when a recorded body of its module names it (recorded_functions): the selector behind a class method is private, and the chain needs it, while a lifted case function that only its parent calls is reached through the parent’s body or not at all.

A function whose body has a case is not inlined by the first rule, and a branch whose block has a case, an exempt, or a recursive let is not inlined by the second: a case of the body would scrutinize a node that is not a successor of the redex. The plan leaves the case at a return position to the un-lifting pass (O4). A call of a user alias of apply (app f x = f x) stays, as it stays for the saturation pass: the source wrote the indirection, and a program may need it to hand a known function value to the apply of the runtime.

class curry.icurry.analysis.inlining.Branch(symbolname, arity, fields, locals, frees, result)

Bases: object

A branch of a single-case body: the pattern variables it binds (variable to field index), its locals, its free variables, and the result. size and uses include the locals of the body before the case.

fields_at(index)

The pattern variables bound to the field index.

class curry.icurry.analysis.inlining.CaseBody(body, params, locals, frees, scrutinee, branches)

Bases: object

A body that is one case on a parameter: the parameters it binds, the locals before the case, its free variables, the variable and the parameter index of the scrutinee, and the branches by the full name of their constructor. size is the largest branch.

class curry.icurry.analysis.inlining.ExpressionBody(body, params, locals, frees, result)

Bases: object

A body that returns an expression: the parameters it binds (variable to parameter index), the locals it binds, in order (variable and expression), its free variables, and the result. size counts the nodes it builds, uses the occurrences of each variable.

class curry.icurry.analysis.inlining.Inliner(modules, budget, depth=MAX_DEPTH)

Bases: object

Rewrites the body of one function at a time, in place: every saturated call of a known function is replaced by its body under the rules of this module, and every apply whose head is known is saturated (partials.saturate), to a fixpoint bounded by depth. budget is the largest expression body inlined, in nodes built; 0 turns both rules off. symbols collects the symbol names that the copied bodies name, so the caller can join the imports of the module.

bind(sigma, vids, expr, uses, pending, depth, rewrite=False)

Maps the variables vids of the body, which name one argument, to expr under the sharing rule: a variable, a literal, or a static string as it is; an expression used once as it is; one used more through a fresh variable of the caller’s block, so that it is built once; one not used is dropped. uses counts the occurrences of all the variables together. A local that gets a variable is rewritten first (rewrite); an argument was rewritten already.

bind_frees(sigma, frees, pending)

bind_locals(sigma, locals, uses, pending, depth)

block(block)

expr(expr, pending, depth)

Rewrites expr from the inside out. The result of a rule is rewritten again, one level deeper, until no rule applies or the depth is reached. The walk over the arguments runs on the trampoline; the rewrite of a result (rules) runs a walk of its own, at most depth deep.

fresh()

instantiate(shape, args, pending, depth)

The expression body shape on the arguments args.

instantiate_case(shape, branch, args, pending, depth)

The branch branch of the single-case body shape on the arguments args, whose scrutinee is a constructor of the branch.

rewrite(ifun)

Rewrites the body of ifun. Returns the number of calls and applies replaced. The shape of the function is taken first, so that a caller reached later sees the body as it was.

rules(expr, pending, depth)

The rewrite of the call expr, or None when no rule applies.

curry.icurry.analysis.inlining.body_shape(body, arity)

The ExpressionBody or CaseBody of the IFuncBody body of a function of arity parameters, or None when the body has another shape: no block (a built-in, an external, or a function loaded from its compiled form), a recursive let, a case whose branches all have a case or an exempt, a variable the body does not bind, or a path the inliner does not follow.

curry.icurry.analysis.inlining.inline_body_text(body)

The ICurry-JSON text of a function body, for the metadata.

curry.icurry.analysis.inlining.inline_shape(ifun)

The shape of the body that a call of ifun is replaced by, or None. The shape is built once per function, over a copy of the body as it is when first asked for (before the pass rewrites the function), or over the body the metadata records (INLINE_KEY: a module loaded from its compiled form has no bodies). A text that does not read back makes the function unknown; it does not stop the import.

curry.icurry.analysis.inlining.is_recursive(ifun, modules)

Whether ifun lies on a cycle of the call graph of its module. A function whose module is not among modules counts as recursive: the inliner leaves it alone.

curry.icurry.analysis.inlining.lookup_module(modulename, modules)

Finds the IModule named modulename among the loaded modules, as lookup_function finds a function, or None.

curry.icurry.analysis.inlining.node_count(expr)

The nodes that expr builds: a call, a partial application, a constructor, a choice, or a literal is one node plus its arguments; a variable is a reference and counts nothing.

curry.icurry.analysis.inlining.recordable(ifun, modules)

Whether the body of ifun is one that a module records for its importers: it has a shape, it is not recursive, and it is within the limit (RECORD_LIMIT for an expression body, CASE_LIMIT for the largest branch of a single-case body).

curry.icurry.analysis.inlining.recorded_functions(imodule, modules)

The full names of the functions of imodule whose bodies the module records under INLINE_KEY, as a frozenset: every public function that is recordable, and every private function that a recorded body names, in a saturated call or in a partial application, so that an importer can follow the chain (the lambda behind . sits in a partial application of the body of .). Computed once per module and cached on it.

curry.icurry.analysis.inlining.recursive_functions(imodule)

The full names of the functions of imodule that lie on a cycle of its call graph, as a frozenset: a function that calls itself, or two or more that call each other, through saturated calls (IFCall). A partial application is a value and makes no edge. Computed once per module, from the bodies as they are when first asked for, and cached on the module. A function without a body has no edges.