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, ReadOnly, 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 /// Transforms the function the way [`Pass::run`] does, with somewhere to put a read only
61 /// table the transformation needs.
62 ///
63 /// This is what the pipeline calls. Almost every pass writes code and nothing else, so the
64 /// default is `run` with the place for tables left empty. `crate::switch_conv` is the pass that
65 /// is not like that, and `crate::readonly` says why a table is asked for this way rather than
66 /// by handing the pass the module.
67 fn run_emitting(
68 &self,
69 func: &mut Func,
70 an: &mut Analyses,
71 fuel: &mut Fuel,
72 data: &mut ReadOnly<'_>,
73 ) -> Stats {
74 let _ = data;
75 self.run(func, an, fuel)
76 }
77
78 /// Whether `-fno-<name>` is refused, because the pass is not one the compile can do without.
79 ///
80 /// Almost nothing is. A pass that optimizes can always be left out, and a person turning one
81 /// off to see what it was doing is what the flag is for, so the default is that the flag is
82 /// obeyed. A pass that takes an opcode out of the IR that nothing below the optimizer lowers is
83 /// a different thing: leaving it out is not a slower program, it is a compile that stops with a
84 /// message about a construct nobody wrote, so the flag is ignored rather than obeyed.
85 fn required(&self) -> bool {
86 false
87 }
88}
89
90/// Every pass this compiler has, in no particular order.
91///
92/// The pipelines in [`crate::pipeline`] name passes out of this list, and `-f<name>` reaches any
93/// of them whether or not the level asked for it. A pass that is written and not in here is a
94/// pass nobody can turn on, so the list is the registry rather than a convenience.
95pub static PASSES: &[&dyn Pass] = &[
96 &crate::expect::Expect,
97 &crate::constant_p::ConstantP,
98 &crate::fold::Fold,
99 &crate::image::Image,
100 &crate::simplify::Simplify,
101 &crate::narrow::Narrow,
102 &crate::dce::Dce,
103 &crate::hoist::Hoist,
104 &crate::discharge::DISCHARGE,
105 &crate::discharge::OBJECTS,
106 &crate::discharge::DOMINANCE,
107 &crate::discharge::SUMMARIES,
108 &crate::discharge::NARROW,
109 &crate::discharge::EVERY,
110 &crate::simplify_cfg::SimplifyCfg,
111 &crate::thread::Thread,
112 &crate::phiopt::PhiOpt,
113 &crate::prune::Prune,
114 &crate::short_circuit::ANY,
115 &crate::short_circuit::FREE,
116 &crate::switch_conv::SwitchConv,
117 &crate::canon::Canon,
118 &crate::header_copy::SPEED,
119 &crate::header_copy::SIZE,
120 &crate::licm::LICM,
121 &crate::number::Number,
122 &crate::load::LoadForward,
123 &crate::reload::RedundantLoad,
124 &crate::unroll::Unroll,
125 &crate::loop_delete::LoopDelete,
126 &crate::split::Split,
127 &crate::nests::Nests,
128 &crate::ivopts::Ivopts,
129 &crate::coalesce::Coalesce,
130 &crate::sink::Sink,
131 &crate::dead_plane::DeadPlane,
132];
133
134/// The pass with this name, if there is one.
135#[must_use]
136pub fn find(name: &str) -> Option<&'static dyn Pass> {
137 PASSES.iter().copied().find(|pass| pass.name() == name)
138}
139
140#[cfg(test)]
141mod tests {
142 use super::PASSES;
143
144 #[test]
145 fn every_pass_has_a_name_a_flag_could_carry() {
146 for pass in PASSES {
147 let name = pass.name();
148 assert!(!name.is_empty(), "a pass with no name cannot be turned off");
149 assert!(
150 name.bytes().all(|b| b.is_ascii_lowercase() || b == b'-'),
151 "`{name}` is not spelled the way a -f flag is"
152 );
153 assert!(!pass.describe().is_empty(), "`{name}` says nothing about itself");
154 }
155 }
156
157 #[test]
158 fn no_two_passes_share_a_name() {
159 for (index, pass) in PASSES.iter().enumerate() {
160 for other in &PASSES[index + 1..] {
161 assert_ne!(pass.name(), other.name(), "two passes answer to one name");
162 }
163 }
164 }
165
166 #[test]
167 fn a_pass_is_found_by_its_name_and_nothing_else_is() {
168 for pass in PASSES {
169 assert_eq!(super::find(pass.name()).map(super::Pass::name), Some(pass.name()));
170 }
171 assert!(super::find("no-such-pass").is_none());
172 }
173}