rucc_opt/
fuel.rs

1//! How many transformations a pass is allowed before it stops transforming.
2//!
3//! Section 9.10 of `spec/09-optimizer.md` requires this of every pass, and the reason is
4//! bisection. When a program compiles wrongly at `-O2` and correctly at `-O0`, the question is
5//! which of the thousands of rewrites the optimizer performed is the wrong one. With fuel it is
6//! a binary search: give the suspect pass n transformations, run the program, and halve. The
7//! answer arrives in about twenty compilations of a file rather than by reading a diff of two
8//! assembly listings.
9//!
10//! The counter is per pass and per compilation rather than per function, because the site being
11//! searched for is one site in one file and numbering it per function would need the function to
12//! be identified first, which is the thing not yet known.
13
14use std::fmt;
15
16/// What a pass has left.
17///
18/// A pass asks [`Fuel::take`] immediately before each transformation and does nothing when the
19/// answer is no. A pass that asks after transforming, or that transforms without asking, is
20/// what the fuel test in [`crate::pipeline`] exists to catch.
21#[derive(Debug, Clone, Copy, PartialEq, Eq)]
22pub struct Fuel {
23    /// How many transformations are still allowed, or `None` for as many as are wanted.
24    left: Option<u32>,
25    /// How many have been performed.
26    spent: u32,
27}
28
29impl Fuel {
30    /// Fuel that never runs out, which is what every pass gets unless `-fpass-fuel` says
31    /// otherwise.
32    #[must_use]
33    pub const fn unlimited() -> Self {
34        Self { left: None, spent: 0 }
35    }
36
37    /// Fuel for exactly this many transformations.
38    #[must_use]
39    pub const fn of(count: u32) -> Self {
40        Self { left: Some(count), spent: 0 }
41    }
42
43    /// Whether one more transformation is allowed, counting it when it is.
44    ///
45    /// The counting happens here rather than at the transformation because a pass that has to
46    /// remember to do two things does one of them.
47    pub fn take(&mut self) -> bool {
48        match &mut self.left {
49            Some(0) => false,
50            Some(left) => {
51                *left -= 1;
52                self.spent += 1;
53                true
54            }
55            None => {
56                self.spent += 1;
57                true
58            }
59        }
60    }
61
62    /// How many transformations have been taken.
63    #[must_use]
64    pub const fn spent(self) -> u32 {
65        self.spent
66    }
67
68    /// Whether the pass has run out, which is only ever true when a limit was set.
69    #[must_use]
70    pub const fn is_empty(self) -> bool {
71        matches!(self.left, Some(0))
72    }
73}
74
75impl Default for Fuel {
76    fn default() -> Self {
77        Self::unlimited()
78    }
79}
80
81impl fmt::Display for Fuel {
82    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
83        match self.left {
84            None => write!(f, "{} of unlimited", self.spent),
85            Some(left) => write!(f, "{} of {}", self.spent, self.spent + left),
86        }
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::Fuel;
93
94    #[test]
95    fn unlimited_fuel_is_never_refused_and_still_counts() {
96        let mut fuel = Fuel::unlimited();
97        for _ in 0..1000 {
98            assert!(fuel.take());
99        }
100        assert_eq!(fuel.spent(), 1000);
101        assert!(!fuel.is_empty());
102    }
103
104    #[test]
105    fn a_limit_of_three_allows_three_and_then_stops_allowing_any() {
106        let mut fuel = Fuel::of(3);
107        assert!(fuel.take());
108        assert!(fuel.take());
109        assert!(fuel.take());
110        assert!(!fuel.take());
111        assert!(!fuel.take());
112        assert_eq!(fuel.spent(), 3);
113        assert!(fuel.is_empty());
114    }
115
116    #[test]
117    fn a_limit_of_zero_allows_nothing_at_all() {
118        let mut fuel = Fuel::of(0);
119        assert!(!fuel.take());
120        assert_eq!(fuel.spent(), 0);
121        assert!(fuel.is_empty());
122    }
123
124    #[test]
125    fn the_display_says_how_much_of_how_much() {
126        let mut fuel = Fuel::of(4);
127        assert!(fuel.take());
128        assert_eq!(fuel.to_string(), "1 of 4");
129        let mut open = Fuel::unlimited();
130        assert!(open.take());
131        assert_eq!(open.to_string(), "1 of unlimited");
132    }
133}
rucc_opt/fuel.rs

rucc_opt/
fuel.rs
