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
61/// Every pass this compiler has, in no particular order.
62///
63/// The pipelines in [`crate::pipeline`] name passes out of this list, and `-f<name>` reaches any
64/// of them whether or not the level asked for it. A pass that is written and not in here is a
65/// pass nobody can turn on, so the list is the registry rather than a convenience.
66pub static PASSES: &[&dyn Pass] = &[
67 &crate::fold::Fold,
68 &crate::simplify::Simplify,
69 &crate::narrow::Narrow,
70 &crate::dce::Dce,
71 &crate::hoist::Hoist,
72 &crate::discharge::DISCHARGE,
73 &crate::discharge::OBJECTS,
74 &crate::discharge::DOMINANCE,
75 &crate::discharge::SUMMARIES,
76 &crate::discharge::NARROW,
77 &crate::discharge::EVERY,
78 &crate::simplify_cfg::SimplifyCfg,
79 &crate::thread::Thread,
80 &crate::phiopt::PhiOpt,
81 &crate::prune::Prune,
82 &crate::short_circuit::ShortCircuit,
83 &crate::switch_conv::SwitchConv,
84 &crate::canon::Canon,
85 &crate::header_copy::SPEED,
86 &crate::header_copy::SIZE,
87 &crate::licm::LICM,
88 &crate::number::Number,
89 &crate::load::LoadForward,
90 &crate::unroll::Unroll,
91 &crate::split::Split,
92 &crate::nests::Nests,
93 &crate::ivopts::Ivopts,
94];
95
96/// The pass with this name, if there is one.
97#[must_use]
98pub fn find(name: &str) -> Option<&'static dyn Pass> {
99 PASSES.iter().copied().find(|pass| pass.name() == name)
100}
101
102#[cfg(test)]
103mod tests {
104 use super::PASSES;
105
106 #[test]
107 fn every_pass_has_a_name_a_flag_could_carry() {
108 for pass in PASSES {
109 let name = pass.name();
110 assert!(!name.is_empty(), "a pass with no name cannot be turned off");
111 assert!(
112 name.bytes().all(|b| b.is_ascii_lowercase() || b == b'-'),
113 "`{name}` is not spelled the way a -f flag is"
114 );
115 assert!(!pass.describe().is_empty(), "`{name}` says nothing about itself");
116 }
117 }
118
119 #[test]
120 fn no_two_passes_share_a_name() {
121 for (index, pass) in PASSES.iter().enumerate() {
122 for other in &PASSES[index + 1..] {
123 assert_ne!(pass.name(), other.name(), "two passes answer to one name");
124 }
125 }
126 }
127
128 #[test]
129 fn a_pass_is_found_by_its_name_and_nothing_else_is() {
130 for pass in PASSES {
131 assert_eq!(super::find(pass.name()).map(super::Pass::name), Some(pass.name()));
132 }
133 assert!(super::find("no-such-pass").is_none());
134 }
135}