Expand description
The pass manager, the acyclic e-graph, the rewrite rules and the analyses.
Design: spec/09-optimizer.md. Layer rank 9, see spec/18-package-layout.md.
§What is here
The pass manager and five passes. pipeline holds the six pipelines, one per optimization
level, written out rather than assembled from flags, along with the fuel, the dumps and the
verification that section 9.10 asks of every pass. gate is the other half of the
bisection interface, which is -fdisable-<pass> and -fenable-<pass> over a list of
functions, so that which pass and which function are two searches rather than one. fold is the first pass through it,
simplify is the peephole the e-graph will eventually absorb, narrow takes the width
back off arithmetic that C promoted, simplify_cfg turns a branch whose condition is known
into a jump and removes the blocks that leaves stranded, and dce is what clears up after
all four of them. uses is the one thing two of them share, which is a count of who reads
what.
stats is what a pass has to return, and optinfo is that printed. A pass reports what
it did and what it gave up on, and there is no other way for it to tell the manager it changed
anything, so the instrumentation cannot be the thing nobody got round to. Section 42.2 of
spec/optimizer/42-measurement.md counted what happens otherwise.
cfg, dom, loops, scev, alias, memssa and range are the analyses
so far, and everything in spec/optimizer/07 through spec/optimizer/11 is built on them.
cfg is the shape of a function with the instructions taken out, dom answers what
every path has to go through, forwards and backwards, loops says what loops there are, how
they nest, and which cycles are not loops at all, scev says how a value changes across the
iterations of one and how many iterations there are, alias answers the one question every
memory optimization is gated on, which is whether two references can touch the same byte,
memssa puts memory on a chain so a load can walk back to the store it sees, and range
says what values an integer can hold at the place it is asked about, which is not the same
question as what it can hold where it was defined.
profile is how likely an edge is taken and how often a block runs, along with the field
that says how much either is worth believing. The types come first because section 11.5 of
spec/optimizer/11-profile-and-frequency.md says what M4 owes the profile work that arrives
after it, which is the shape rather than the data: a quality on every number, arithmetic that
degrades it, and no way to build one without saying where it came from. Retrofitting that into
thirty passes once there is real profile data is the failure mode, and it is GCC’s, whose
profile maintenance bugs are mostly in passes written before the quality field existed.
predict is where the first of those numbers comes from, which is a guess: ten predictors
from section 11.2, first match, each one a syntactic situation somebody measured in the 1990s
and a rate it turned out right at. Nothing in here is a measurement and every probability out
of it says so.
frequency turns those guesses into the number the consumers actually want, which is how
often a block runs compared with the function entry. Section 11.3’s method: solve each loop
from the inside out, take the chance of going round again, and the header runs one over one
minus that many times, which is the sum of the series. A loop nothing predicted an exit for
gets a cap rather than a division by zero, an irreducible region gets an answer that is marked
as not meaning anything, and the check section 11.5 asks for, which is that what arrives at a
block adds up to the block, is in frequency::Frequencies::problems.
live is what is live where, and pressure is that counted per register class, which is
section 40.6’s one function with four consumers. In SSA the number of values live at a point is
the number of registers the program needs there rather than an estimate of it, which is what
makes it worth computing exactly: loop invariant motion, the scheduler, the spill phase and if
conversion all ask about the same quantity, and four passes each working out their own would be
four chances for two of them to make opposite decisions off different counts of one thing. How
many registers there are is the target’s and is not here, so the answer is a count and the
caller brings the register file.
purity is the other question asked about a call, which is what it is allowed to do. Five
answers rather than a boolean, because whether a call reads memory and whether it comes back are
separate questions and GCC needs both, and the default is the one that permits everything, so a
call nobody has taught it about costs a missed optimization rather than a wrong program. The
declaration the user wrote and the answer an analysis works out are kept in separate fields and
combined where they are read, which is what makes it possible to check one against the other.
analysis is where a pass gets one from. It computes on demand, caches per function, and
throws out what a pass broke, working from what the pass said it preserved rather than from a
list kept somewhere else. A pass that claims to preserve an analysis it broke is caught under
--verify, by recomputing the analysis and comparing.
The e-graph and the rewrite rule set are still M4 work and are not here yet.
§Stability
Every crate in the workspace is published, and publishing implies a promise. This one is
tier 3: its Rust API is explicitly unstable and will change without a major version bump.
Depend on the rucc binary’s behaviour, not on this.
Re-exports§
pub use alias::Access;pub use alias::Alias;pub use alias::Answer;pub use alias::Counts;pub use alias::Escapes;pub use alias::Origin;pub use alias::Reason;pub use analysis::Analyses;pub use analysis::Analysis;pub use analysis::Preserved;pub use cfg::Cfg;pub use dom::Dominators;pub use dom::PostDominators;pub use frequency::Frequencies;pub use frontier::ControlDependence;pub use frontier::Frontiers;pub use fuel::Fuel;pub use gate::Gates;pub use live::LiveHere;pub use live::Liveness;pub use loops::Exit;pub use loops::LoopId;pub use loops::Loops;pub use memssa::Clobber;pub use memssa::Step;pub use memssa::Walk;pub use optinfo::Wants;pub use pass::PASSES;pub use pass::Pass;pub use pipeline::Dump;pub use pipeline::Dumps;pub use pipeline::Options;pub use pipeline::Remark;pub use pipeline::Report;pub use pipeline::run;pub use predict::Callees;pub use predict::Predictions;pub use predict::Predictor;pub use pressure::Pressure;pub use profile::Frequency;pub use profile::Hotness;pub use profile::Probability;pub use profile::Quality;pub use purity::Purity;pub use range::query::Ranges;pub use range::Bits;pub use range::Range;pub use scev::Assumption;pub use scev::Bound;pub use scev::Chrec;pub use scev::Count;pub use scev::Estimate;pub use scev::Evolution;pub use scev::Invariant;pub use scev::Scev;pub use stats::Stats;
Modules§
- alias
- Alias analysis: whether two memory references can touch the same byte.
- analysis
- The analysis cache, and what a pass has to say about what it left standing.
- cfg
- The control flow graph, which is the shape of a function with the instructions taken out.
- dce
- Dead code elimination: an instruction nothing uses and nothing depends on goes away.
- dom
- Dominance, which is the question of what every path has to go through.
- fold
- Constant folding: an instruction whose operands are all constants becomes a constant.
- frequency
- Block frequency: how often a block runs, relative to the function it is in.
- frontier
- Where a dominator stops dominating, forwards and backwards.
- fuel
- How many transformations a pass is allowed before it stops transforming.
- gate
- Which functions a pass is allowed to run on.
- live
- Which values are live where, which is what the pressure model counts and what a scheduler has to know before it moves anything.
- loops
- The loop forest: what loops there are, how they nest, and what is in a cycle that is not one.
- memssa
- Memory SSA: the chain, and the budgeted walk back to the store a load sees.
- narrow
- Width narrowing: arithmetic redone at the width the program actually uses.
- optinfo
-fopt-info, which is the compiler saying what it did and what it nearly did.- pass
- What a pass is, and the list of the ones this compiler has.
- pipeline
- The pipelines, one per optimization level, and the manager that runs one.
- predict
- Static branch prediction: which way a branch goes, when there is no profile that says.
- pressure
- How many registers the program needs at each point, which is the one number four passes ask for and none of them should compute for itself.
- profile
- How likely an edge is taken, how often a block runs, and how much either is worth believing.
- purity
- What a call is allowed to do, which is the question every pass asks before it moves one.
- range
- What values an integer can hold: a few intervals, and the bits that are known.
- rules
- Matching the rewrite rules against the IR.
- scev
- Scalar evolution: how a value changes across the iterations of a loop, and how many iterations there are.
- simplify
- Peephole rewrites: a small pattern of instructions becomes a smaller one.
- simplify_
cfg - Control flow simplification: a branch whose condition is already known becomes a jump, and the blocks that leaves stranded are removed.
- stats
- What a pass has to say about what it did, and about what it wanted to do and could not.
- uses
- Who reads what, counted by occurrence.
Constants§
- MILESTONE
- The milestone in
spec/17-milestones.mdthat fills this crate in.