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::image::Image,
81 &crate::simplify::Simplify,
82 &crate::narrow::Narrow,
83 &crate::dce::Dce,
84 &crate::hoist::Hoist,
85 &crate::discharge::DISCHARGE,
86 &crate::discharge::OBJECTS,
87 &crate::discharge::DOMINANCE,
88 &crate::discharge::SUMMARIES,
89 &crate::discharge::NARROW,
90 &crate::discharge::EVERY,
91 &crate::simplify_cfg::SimplifyCfg,
92 &crate::thread::Thread,
93 &crate::phiopt::PhiOpt,
94 &crate::prune::Prune,
95 &crate::short_circuit::ANY,
96 &crate::short_circuit::FREE,
97 &crate::switch_conv::SwitchConv,
98 &crate::canon::Canon,
99 &crate::header_copy::SPEED,
100 &crate::header_copy::SIZE,
101 &crate::licm::LICM,
102 &crate::number::Number,
103 &crate::load::LoadForward,
104 &crate::reload::RedundantLoad,
105 &crate::unroll::Unroll,
106 &crate::split::Split,
107 &crate::nests::Nests,
108 &crate::ivopts::Ivopts,
109 &crate::coalesce::Coalesce,
110 &crate::dead_plane::DeadPlane,
111];
112
113/// The pass with this name, if there is one.
114#[must_use]
115pub fn find(name: &str) -> Option<&'static dyn Pass> {
116 PASSES.iter().copied().find(|pass| pass.name() == name)
117}
118
119#[cfg(test)]
120mod tests {
121 use super::PASSES;
122
123 #[test]
124 fn every_pass_has_a_name_a_flag_could_carry() {
125 for pass in PASSES {
126 let name = pass.name();
127 assert!(!name.is_empty(), "a pass with no name cannot be turned off");
128 assert!(
129 name.bytes().all(|b| b.is_ascii_lowercase() || b == b'-'),
130 "`{name}` is not spelled the way a -f flag is"
131 );
132 assert!(!pass.describe().is_empty(), "`{name}` says nothing about itself");
133 }
134 }
135
136 #[test]
137 fn no_two_passes_share_a_name() {
138 for (index, pass) in PASSES.iter().enumerate() {
139 for other in &PASSES[index + 1..] {
140 assert_ne!(pass.name(), other.name(), "two passes answer to one name");
141 }
142 }
143 }
144
145 #[test]
146 fn a_pass_is_found_by_its_name_and_nothing_else_is() {
147 for pass in PASSES {
148 assert_eq!(super::find(pass.name()).map(super::Pass::name), Some(pass.name()));
149 }
150 assert!(super::find("no-such-pass").is_none());
151 }
152}