unison-runtime-0.0.0
Safe HaskellNone
LanguageHaskell2010

Unison.Runtime.MCode.Explode

Description

Loop state exploded into parameters: call-pattern specialisation.

A function of a batch that some saturated call in the batch passes a product or constructor built for the call (a let of a constructor application or a record literal, (acc, i) in go (acc, i), Left x in go (Left x), or a record update of such a value) gets a specialisation for that call pattern: a worker, a combinator of the group at an index of its own (specIndex), whose parameters are the pattern's fields and whose body is the lambda's with each match on the argument replaced by the arm for the pattern's constructor and each update of it by a literal of the fields. Call sites that build the pattern call the worker with the field variables, which are in scope where the value was built, and the let that built it is dropped when nothing else uses it (dropDead); so a loop whose state is a tuple or a record allocates nothing per round, and a loop whose state is a sum runs as one worker per constructor, mutually recursive through the sites, with no tag anywhere. The lambda's own index keeps the original body, for callers the batch cannot see (a later batch, a function value, a partial application) and for sites that pass a value they did not build. Fields that are products built for the call explode in turn, which is what a tuple's nesting needs. This is GHC's SpecConstr (Peyton Jones, "Call-pattern specialisation for Haskell programs", 2007), done for the call sites the loader can see (explosions, over each batch cacheAdd loads) and without any change to how values are represented: a worker's parameters are ordinary slots, so nothing here depends on the wide convention (Unison.Runtime.Wide). A continuation captured in rewritten code is written out as the unoptimized code's frames, which is what Sources and Prepared are for (FrameLayout, design.md "Continuations across processes").

A pattern is taken apart only as far as the body consumes it: an argument the body passes on, stores or returns on some path stays a plain parameter (usable), so nothing is ever rebuilt. The patterns of a function are a closure: the ones its callers' bodies build, then the ones each worker's own body builds, up to a cap per function (maxSpecs). A sum built in the branches of a match and passed at once, go (if p then Left x else Right y), is first rewritten so that each branch makes the call (sinkCalls), which is what gives each branch its worker.

The return side is the same idea for results (returns): a function whose every return builds a product, through its own tail calls, gets a product-return worker, a combinator of its group at retIndex whose tails yield the product's leaves as several values instead of packing them (returnWorker), while the entry keeps the original body. A caller in the batch that takes the result apart at once calls the worker with a let of the leaves (useReturns), so a loop and its step function exchange a tuple with nothing allocated in either direction; a result that escapes keeps the entry, and one that is only passed on to an exploded position of another worker is rebuilt in the caller and dropped like any other product built for such a call. A function whose own recursion embeds its result, a tree insert rebuilding the path, gets no worker (selfResultEscapes): the worker's recursion would yield the leaves and pack them again at every level.

Everything here is a rewrite of the ANF, and the result says what it means: a call of a worker is TApp (FWorker r i) args, the combinator at index i of the group of r with exactly the arguments it takes, and a tail that returns several values is TApp FYield vs. The emitter (Unison.Runtime.MCode) turns each into one instruction and checks the counts (resultCount); it decides nothing. The two forms exist only in a batch's code after it is loaded, never in what the cache stores or a continuation names, so the serializers refuse them.

What it does not change: the groups the cache stores and hashes (the rewrite is a function of a batch's optimized code, like inlining, run again at every load), a compiled program's file (its MCode has the workers in it), and the serialized form of a continuation (a worker's frame holds plain slots; its index is a combinator of its group like any other). A continuation captured inside a worker names the worker's index, so a process that loads the same code with the rewrite off cannot resume it, as with any difference in the optimizer between two versions.

Two rewrites of a body on its own come first (knownCons, splitJoins; design.md "Known constructors and case of case"): a let binding a constructor application or a record literal has every match on it replaced by the arm, the arm's variables renamed to the fields (the argument side's rewrite), so that match (a, b) with .., which builds the tuple and takes it apart at once, allocates nothing and tests no tag; and a let whose binding is a match (or anything whose every tail builds a constructor of the matched type) and whose body is a match on it (the let's body, or the binding of the next let) has the outer match moved into those tails, where the constructor is known, an outer arm that several tails reach becoming a join point, a combinator of the group at joinIndex that the tails call with the arm's fields and the variables the arm uses, so that an arm's code is not copied into every tail (an arm that is a single expression, or that one tail reaches, is copied instead), and so does the rest of the body when the match's value was let-bound. The join points of a lambda are made last, after the other rewrites, with their parameters taken from the unoptimized arm (caseSites), so that every variable the unoptimized arm reads is in the join point's frame and a continuation captured inside it can be written out (Join).

UNISON_OPTIMIZATIONS=-explode_args and -explode_returns switch the two sides off, and -known_constructor the two rewrites above (explodeArgsOn, explodeReturnsOn, knownConstructorOn; Unison.Runtime.Optimizations), for measuring and for a process that has to agree with one that ran without them.

Synopsis

Documentation

explodeArgsOn :: Bool Source #

Whether loop state is exploded in this process (the argument side: explosions, specialise): on unless UNISON_OPTIMIZATIONS says -explode_args.

explodeReturnsOn :: Bool Source #

Whether product results are exploded (the return side: returns, returnWorker): on unless UNISON_OPTIMIZATIONS says -explode_returns.

knownConstructorOn :: Bool Source #

Whether a product or sum built and matched in the same body is matched where it is built, and a match on the value of a match moved into its tails (knownCons, splitJoins): on unless UNISON_OPTIMIZATIONS says -known_constructor.

rewritesOn :: Bool Source #

Whether any rewrite of the ANF is on: with none, every lambda is emitted as its unoptimized form and no section gets a deoptimization table (the emitter checks this).

specIndex :: Int -> Word64 Source #

The combinator index of a group's k-th specialisation (k from 1): in the high bits like a local function's, with a bit no let index reaches (the lets of a combinator are numbered from 1 in its low sixteen bits) and no local function has. The JIT treats a worker like the entry point it stands for (Compile's isEntry).

retIndex :: Word64 Source #

The combinator index of a group's product-return worker (returns): the specialisation slot no call pattern takes, since those are numbered from 1.

joinIndex :: Word64 -> Int -> Word64 Source #

The combinator index of the k-th join point (k from 1) of the lambda at an index of the group (splitJoins): the lambda's index with k in the bits above any a local function's or a specialisation's number uses, so that the low fifteen bits are the owner's and the JIT compiles it as it does a worker (Compile's isEntry), and the lets of the join point are numbered under it like any combinator's.

data Shape Source #

How an argument position is taken apart: left as one slot, or a product, a data constructor or a record (Fields, its fields in the schema's order, which is the field names' order), whose fields are taken apart in turn.

Instances

Instances details
Show Shape Source # 
Instance details

Defined in Unison.Runtime.MCode.Explode

Methods

showsPrec :: Int -> Shape -> ShowS #

show :: Shape -> String #

showList :: [Shape] -> ShowS #

Eq Shape Source # 
Instance details

Defined in Unison.Runtime.MCode.Explode

Methods

(==) :: Shape -> Shape -> Bool #

(/=) :: Shape -> Shape -> Bool #

Ord Shape Source # 
Instance details

Defined in Unison.Runtime.MCode.Explode

Methods

compare :: Shape -> Shape -> Ordering #

(<) :: Shape -> Shape -> Bool #

(<=) :: Shape -> Shape -> Bool #

(>) :: Shape -> Shape -> Bool #

(>=) :: Shape -> Shape -> Bool #

max :: Shape -> Shape -> Shape #

min :: Shape -> Shape -> Shape #

type Pattern = [Shape] Source #

A call pattern: a shape per argument.

shapeLeaves :: Shape -> Int Source #

The values a shape is taken apart into: one for a plain position, the leaves of its fields for a product.

data Batch Source #

What the rewrites know about the batch, each by a function's reference and Nothing for a function outside the batch or without one: the call patterns it has a specialisation for, in worker order (explosions), the product it returns on every path (returns), and its arity. The analyses run with the parts not yet known empty.

type Explosions = Map Reference [Pattern] Source #

The specialisations of each function of a batch, by its reference: the patterns, in the order their workers are numbered (specIndex).

explosions :: Var v => Returns -> Map Reference (SuperGroup Reference v) -> Explosions Source #

The specialisations of a batch of groups: for each group's entry point, the patterns its callers in the batch build, each narrowed to what its body consumes, and then the patterns each worker's own body builds, until there are no new ones.

type Returns = Map Reference Shape Source #

The product each function of a batch returns on every path, by its reference: the shape every tail of its body builds (a constructor application or a record literal, or a variable bound to one, its fields taken apart in turn where they are built for it), met over the tails, where the other tails are saturated calls of functions of the batch that return the same product. A closure from the shapes the tails build: a callee's shape narrows its callers' until nothing changes, and a function with a tail that returns anything else, or calls a function that does, is dropped. Products of one leaf are left to the wide convention and products of none are nothing to return; a function of no arguments is a value evaluated once when it loads, so it keeps its entry.

prepare :: Var v => Batch -> Maybe (JoinSetting v) -> SuperNormal Reference v -> Prepared v Source #

A lambda as the emitter sees it (prepareBody on its body). Applied to every lambda of a batch, so that the sites the analyses saw are the sites emitted; the analyses pass no setting and get no join points.

specialise :: Var v => Batch -> Maybe (JoinSetting v) -> Pattern -> SuperNormal Reference v -> Prepared v Source #

The worker of a lambda for a pattern: its parameters are the plain arguments and the fields of the exploded ones, each a fresh name, and its body is the lambda's with the exploded arguments rewritten to their fields, prepared again afterwards, since a record update the rewrite turned into a literal is a product built for whatever it is passed to. The join points are made by the second pass, from the sites of the unoptimized body.

returnWorker :: Var v => Batch -> Shape -> SuperNormal Reference v -> Prepared v Source #

The product-return worker of a lambda that returns a product of the shape on every path: the lambda with its tails yielding the leaves. It gets no join points: its tails are what yield the leaves.

data Prepared v Source #

A lambda as the emitter sees it, with what its rewrite changed: the sources of the unoptimized body's variables, the binders of each let the rewrite changed, mapped to the binders of the unoptimized let it stands for (a let of a result's leaves, to the let of the result), and the variables the rewrite found dead wherever a frame could hold them (the let of a site splitJoins rewrote, used only by the match that is gone), and its join points, the k-th at joinIndex k of the lambda's index.

data Join v Source #

A join point of a lambda (splitJoins): an arm of a match on the value of a match, as a combinator of the group whose parameters are the arm's variables and then the variables the arm uses; the binders of the unoptimized let whose binding the match was in, if any, which is where the unoptimized frames of a continuation captured inside the join point stop (the emitter's deoptOf); and the source of the match's variable, the constructor this arm is for over the arm's variables (none for the default arm, whose frames never read it).

Constructors

Join 

data JoinSetting v Source #

Where a lambda's join points go: the lambda's index in its group, the group's reference, and the names of the group's local functions, which a body refers to as variables but which no frame holds.

Constructors

JoinSetting 

type Sources v = Map v (Either v (Built v)) Source #

Where a variable of the unoptimized body went, for the frames of a continuation captured in the optimized code to be written out as the unoptimized code's (design.md, "Continuations across processes"; FrameLayout): renamed to another variable (a match arm's field variable to the leaf or product that stands for it, a field read's let to the parameter it reads), or replaced by a product the optimized body no longer names, given as the product with the names of its fields in the optimized body (an exploded parameter, a result the leaves replace, a product of either that a match took apart in turn). A variable with no entry has the same name in both.

data Built v Source #

A product a let built: which one, and its field variables, in the shape's field order.

Instances

Instances details
Show v => Show (Built v) Source # 
Instance details

Defined in Unison.Runtime.MCode.Explode

Methods

showsPrec :: Int -> Built v -> ShowS #

show :: Built v -> String #

showList :: [Built v] -> ShowS #

conLets :: Var v => ANormal Reference v -> ConLets v Source #

uniqueBody :: Var v => ANormal Reference v -> ANormal Reference v Source #

The body with a name of its own for every binder and an index of its own for every indirect let. Normalization reuses a name under shadowing (the blank variables), and freshen gives a name back once the binder's scope is over, while everything here maps variables by name. Only a binder already bound elsewhere in the body is renamed, so that a body whose binders are already unique comes back as it is: the unoptimized body is renamed the same way, and the names are what pairs its lets with the optimized body's (Prepared). The let indices number the sections of the emitted combinator, and the ones normalization assigned repeat once the ANF optimizer has inlined a body whose lets carry their own (uniqueLets), which is also why the renaming is applied with every rewrite off.

universe :: ANormal Reference v -> [ANormal Reference v] Source #

A term and every term inside it. | Every subterm, the term first; built with an accumulator, since the analyses walk it once per let of a body and the nested appends of a concatMap cost the body's size times its depth per walk (a doc literal of a few thousand lets took minutes, 2026-11-03).