Crate rucc_opt 

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.

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 fuel::Fuel;

pub use gate::Gates;

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 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.

fuel

How many transformations a pass is allowed before it stops transforming.

gate

Which functions a pass is allowed to run on.

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.

range

What values an integer can hold: a few intervals, and the bits that are known.

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.md that fills this crate in.