Chapter 6
Passes
A pass transforms a function of a verified module into a function that does the same: for every state and arguments, running the result gives the same results, calls the same operations with the same arguments in the same order and ends the same way as running the original. Passes rely only on the meaning of statements and expressions and on the declarations of operations (their state, features and laws), never on how a target implements an operation.
Passes in the Pipeline
The functions that a backend prints from the Exec stage are converted from the Flow stage a table at a time: the
functions of a table into one module (see Lowering From the Flow Stage). Each such module then goes
through the passes of the one compiler pipeline that run at the Exec stage, in their declared order; a pass on one
function takes each function of the module in turn. A pass has a name that no pass of Core IR or of the Flow stage has, and that
is also the name of the optimization that turns it off; a pass that is off, or that does not apply to the build, does
not run. A pass returns the module after it, in which it keeps each function
that lowering made, at the same place and with the same name, and in it the locals that lowering declared for the
variables of the function of the Flow stage, because the backend prints the body of that function with those locals;
it may change the bodies, add locals and add the declarations that its changes need. A module that lost a function or
one of those locals is an error of the passes. The
module MUST satisfy the invariants where the pipeline leaves the stage: verification runs right after
the lowering and again where the pipeline leaves the stage, and also after every pass when asked, and a violation names
the pass after which it was found. Lowering has verified the module, so a run in which no pass runs does not verify it
again. The first pass of the stage is canonicalize (below); specialization and the dead stores are used by the compositions
and the printers.
Specialization
Specializing a function for a set of features, which are features of the module, makes a copy of it in which each
Feature expression is the constant true when its feature is in the set and false otherwise; the copy is then
canonicalized (below). The copy's features are the set, so that it may call the operations of those features and no
others. A specialization does what the function does in a build that has each feature of the set and no other.
Every printed composition is a specialization (see Compositions). A function written for several builds tests a feature where its builds differ; after specialization, the code of the features that are off is gone, and with it the calls of their operations.
Canonicalization
One pass, canonicalize, applies named local patterns to a function until none applies, trying them in a fixed
order, so that the result is the same on every run. It runs at the Exec stage and, with the patterns that keep the
invariants of that stage, at the Flow stage. Each pattern is an optimization
with its own name, which turns it off, and each application of a pattern is counted on its own when passes are
bisected. A specialization applies every pattern, whatever optimizations a build turns off. The patterns of the Exec
stage fold constant expressions and remove code that cannot run, in place, in this order:
fold-constants: an operator or a conversion whose operands are constants becomes its value, computed as running it computes it, except a division or a remainder by zero, which stays;!of a constant becomes its value, and&&and||with a constant operand that decides them become that constant, or their other operand when the constant does not decide them; an operand that is dropped never holds a call;fold-branches: anIfwhose condition is a constant becomes its Init and the branch that the condition selects, as its statements, or as a block when the branch declares a local; aLoopwhose condition is the constant false becomes its Init, and the constant true condition of aLoopis removed;drop-after-exit: the statements after anExit,Break,ContinueorReturnin the same block are removed;drop-unused-labels: the label of a block that noExitnames is removed;splice-blocks: a block without a label that declares no local is spliced into the block that holds it, and an emptyElseis removed.
Backends also print an operator on constants as its value, because target languages evaluate constant expressions in arithmetic of their own: a constant expression of Code IR that wraps would not be accepted, or would not wrap, there.
Dead Stores
Finding the dead stores of a function, among the candidate locals that a backend names, tells the backend which locals nothing reads, so that it does not declare them, and which assignments it may leave out.
- Reachability follows the printers: after an
Exit, aBreak, aContinueor aReturn, the point is unreachable up to the end of the enclosing block; the point after a block is reachable when its end is or when a reachable jump leaves it; the point after anIfis reachable when the point before it is; and the point after a loop always is. Only reachable statements read locals, except the Init, condition and Post of a loop, which read whatever their reachability. - An assignment, a
Setthat is a statement of a block with one value for each place, is left out when every value is pure and every place is a dead local. A value is pure when evaluating it has no effect and cannot fail. Whether a call of an operation is pure is derived from its declaration: it writes no component or register, cannot end the parse, and, in a build with the featurebudget, has a cost of zero. A law of the operation never makes a call pure. Leaving an assignment out may leave the locals that its values read unread, so the removal repeats until no more locals become dead. The reads of a pure assignment of its own places, such as an increment, do not keep them. - A local assigned in the Init of an
Ifor of a loop, which is never left out, stays; so does a local assigned opposite a null handle in an assignment of several values. - An assignment that is not left out keeps its values, and the backend prints its dead places as discarded.