rucc_opt/pass.rs
1//! What a pass is, and the list of the ones this compiler has.
2
3use rucc_ir::Func;
4
5use crate::{Analyses, Fuel, Preserved, Stats};
6
7/// One transformation over one function.
8///
9/// A pass is a value rather than a function so that its name and its description travel with
10/// it. The name is what `-fno-<name>`, `-fpass-fuel=<name>=<n>` and `-fdump-ir=after-<name>` all
11/// spell, and there is one of it, which is why a pass cannot be added to a pipeline without
12/// being reachable from the command line.
13///
14/// A pass sees one function at a time. Whole-module work is not this trait, and inlining will
15/// need something else when it arrives.
16pub trait Pass: Sync {
17 /// What it is called, in lower case with hyphens between words.
18 fn name(&self) -> &'static str;
19
20 /// One line, for `--print-pipeline`.
21 ///
22 /// It says what the pass does to the code rather than how, because the reader of a pipeline
23 /// listing is asking why their program came out the way it did.
24 fn describe(&self) -> &'static str;
25
26 /// Which analyses still answer the same questions about the function this pass has finished
27 /// with as they did about the one it was handed.
28 ///
29 /// There is no default, on purpose. A pass that has not thought about this is a pass whose
30 /// author has not thought about it, and the safe answer, which is [`Preserved::NONE`], costs
31 /// a recomputation rather than a wrong answer, so it has to be cheap to write and not free
32 /// to leave out. Section 4.3 of `spec/optimizer/04-pass-manager.md` asks for the declaration
33 /// and section 4.4 has the table of what breaks what.
34 ///
35 /// It is a property of the pass rather than of the run. A pass that sometimes moves an edge
36 /// says it preserves nothing, and the manager gets the cheap case back another way: an
37 /// analysis is only thrown out after a pass that says in its [`Stats`] that it changed
38 /// something.
39 fn preserves(&self) -> Preserved;
40
41 /// Transforms the function, asking `fuel` before each transformation.
42 ///
43 /// Returns what it did, as named counts. There is no separate answer to whether anything
44 /// changed: [`Stats::changed`] is that answer, so recording a rewrite and performing one are
45 /// the same act rather than two things a pass has to remember. Section 42.2 of
46 /// `spec/optimizer/42-measurement.md` asks for exactly this, and gives the reason: a counter
47 /// a pass calls is a counter a pass forgets to call, and GCC's hundred instrumented events
48 /// across three hundred passes is what that looks like ten years later.
49 ///
50 /// A pass that says it changed nothing and did is a pass whose dumps lie and whose output the
51 /// verifier never sees. One that says it changed something and did not costs a verifier run.
52 /// Record the misses too, because the question at a slow loop is what the compiler nearly
53 /// did.
54 ///
55 /// `an` is where an analysis comes from. Building one by hand instead is not wrong so much
56 /// as wasteful, and it is how two passes end up disagreeing about the same function, so a
57 /// pass that wants a dominator tree asks for one here.
58 fn run(&self, func: &mut Func, an: &mut Analyses, fuel: &mut Fuel) -> Stats;
59
60 /// Whether `-fno-<name>` is refused, because the pass is not one the compile can do without.
61 ///
62 /// Almost nothing is. A pass that optimizes can always be left out, and a person turning one
63 /// off to see what it was doing is what the flag is for, so the default is that the flag is
64 /// obeyed. A pass that takes an opcode out of the IR that nothing below the optimizer lowers is
65 /// a different thing: leaving it out is not a slower program, it is a compile that stops with a
66 /// message about a construct nobody wrote, so the flag is ignored rather than obeyed.
67 fn required(&self) -> bool {
68 false
69 }
70}
71
72/// Every pass this compiler has, in no particular order.
73///
74/// The pipelines in [`crate::pipeline`] name passes out of this list, and `-f<name>` reaches any
75/// of them whether or not the level asked for it. A pass that is written and not in here is a
76/// pass nobody can turn on, so the list is the registry rather than a convenience.
77pub static PASSES: &[&dyn Pass] = &[
78 &crate::expect::Expect,
79 &crate::fold::Fold,
80 &crate::simplify::Simplify,
81 &crate::narrow::Narrow,
82 &crate::dce::Dce,
83 &crate::hoist::Hoist,
84 &crate::discharge::DISCHARGE,
85 &crate::discharge::OBJECTS,
86 &crate::discharge::DOMINANCE,
87 &crate::discharge::SUMMARIES,
88 &crate::discharge::NARROW,
89 &crate::discharge::EVERY,
90 &crate::simplify_cfg::SimplifyCfg,
91 &crate::thread::Thread,
92 &crate::phiopt::PhiOpt,
93 &crate::prune::Prune,
94 &crate::short_circuit::ShortCircuit,
95 &crate::switch_conv::SwitchConv,
96 &crate::canon::Canon,
97 &crate::header_copy::SPEED,
98 &crate::header_copy::SIZE,
99 &crate::licm::LICM,
100 &crate::number::Number,
101 &crate::load::LoadForward,
102 &crate::unroll::Unroll,
103 &crate::split::Split,
104 &crate::nests::Nests,
105 &crate::ivopts::Ivopts,
106 &crate::coalesce::Coalesce,
107 &crate::dead_plane::DeadPlane,
108];
109
110/// The pass with this name, if there is one.
111#[must_use]
112pub fn find(name: &str) -> Option<&'static dyn Pass> {
113 PASSES.iter().copied().find(|pass| pass.name() == name)
114}
115
116#[cfg(test)]
117mod tests {
118 use super::PASSES;
119
120 #[test]
121 fn every_pass_has_a_name_a_flag_could_carry() {
122 for pass in PASSES {
123 let name = pass.name();
124 assert!(!name.is_empty(), "a pass with no name cannot be turned off");
125 assert!(
126 name.bytes().all(|b| b.is_ascii_lowercase() || b == b'-'),
127 "`{name}` is not spelled the way a -f flag is"
128 );
129 assert!(!pass.describe().is_empty(), "`{name}` says nothing about itself");
130 }
131 }
132
133 #[test]
134 fn no_two_passes_share_a_name() {
135 for (index, pass) in PASSES.iter().enumerate() {
136 for other in &PASSES[index + 1..] {
137 assert_ne!(pass.name(), other.name(), "two passes answer to one name");
138 }
139 }
140 }
141
142 #[test]
143 fn a_pass_is_found_by_its_name_and_nothing_else_is() {
144 for pass in PASSES {
145 assert_eq!(super::find(pass.name()).map(super::Pass::name), Some(pass.name()));
146 }
147 assert!(super::find("no-such-pass").is_none());
148 }
149}