| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
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
- explodeArgsOn :: Bool
- explodeReturnsOn :: Bool
- knownConstructorOn :: Bool
- rewritesOn :: Bool
- specIndex :: Int -> Word64
- retIndex :: Word64
- joinIndex :: Word64 -> Int -> Word64
- isJoinIndex :: Word64 -> Bool
- data Shape
- type Pattern = [Shape]
- shapeLeaves :: Shape -> Int
- data Batch = Batch {}
- type Explosions = Map Reference [Pattern]
- explosions :: Var v => Returns -> Map Reference (SuperGroup Reference v) -> Explosions
- type Returns = Map Reference Shape
- returns :: Var v => Map Reference (SuperGroup Reference v) -> Returns
- prepare :: Var v => Batch -> Maybe (JoinSetting v) -> SuperNormal Reference v -> Prepared v
- specialise :: Var v => Batch -> Maybe (JoinSetting v) -> Pattern -> SuperNormal Reference v -> Prepared v
- returnWorker :: Var v => Batch -> Shape -> SuperNormal Reference v -> Prepared v
- data Prepared v = Prepared {
- preparedLambda :: SuperNormal Reference v
- preparedSources :: Sources v
- preparedLets :: Map [v] [v]
- preparedDead :: Set v
- preparedJoins :: [Join v]
- data Join v = Join {
- joinLambda :: SuperNormal Reference v
- joinCut :: Maybe [v]
- joinSources :: Sources v
- data JoinSetting v = JoinSetting {}
- type Sources v = Map v (Either v (Built v))
- data Built v
- = BuiltCon Reference CTag [v]
- | BuiltRec RecordSchema [v]
- builtFields :: Built v -> [v]
- conLets :: Var v => ANormal Reference v -> ConLets v
- uniqueBody :: Var v => ANormal Reference v -> ANormal Reference v
- universe :: ANormal Reference v -> [ANormal Reference v]
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).
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.
isJoinIndex :: Word64 -> Bool 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.
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.
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.
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.
Constructors
| Prepared | |
Fields
| |
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 | |
Fields
| |
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.
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.
A product a let built: which one, and its field variables, in the shape's field order.
Constructors
| BuiltCon Reference CTag [v] | |
| BuiltRec RecordSchema [v] |
builtFields :: Built v -> [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).