rucc_cost/
lib.rs

1//! What things cost on a target, and every tuning constant the optimizer has.
2//!
3//! This is document 40 of `spec/optimizer/`, made real. The crate exists because of the failure
4//! that document opens with: a compiler where each pass has its own idea of what an operation
5//! costs is a compiler where two passes undo each other, and neither of them is wrong. Putting the
6//! numbers in one place does not make them right, but it makes them one thing that can be measured
7//! and changed, instead of thirty things that have to be found first.
8//!
9//! # What is in here
10//!
11//! [`Cycles`] and [`Bytes`], which are separate types so that a cost in time is never compared
12//! against a threshold in space. [`Cost`], which is a time and a complexity compared
13//! lexicographically with an explicit infinity, from GCC's `comp_cost`. [`CostTable`], which a
14//! target fills in completely or not at all. [`TuneFlag`], which is the half of a cost model that
15//! is a boolean rather than a number. And [`heuristics`], which is the file every threshold in
16//! every pass has to come from.
17//!
18//! # Two tables, not one table and a policy
19//!
20//! Section 40.3 reads `ix86_cur_cost()` at `gcc/config/i386/i386.h:269` and takes the design
21//! from it: optimizing for size is a different cost table, not a weighting applied to the same
22//! one. `-Os` selects the second table and every pass then goes on asking the same questions in
23//! the same way. It makes `-Os` behaviour inspectable as data, and it means no pass has to
24//! remember to ask whether it is optimizing for size, which is the sort of thing a pass forgets
25//! in exactly one of its five decisions.
26//!
27//! # What is not in here
28//!
29//! Anything derived from a function. Register pressure, block frequency and branch predictability
30//! are all things section 40.6 wants computed once per function and shared, and all three need the
31//! IR, so they belong with the analyses rather than with the target description. This crate is
32//! below the IR on purpose.
33
34#![doc(html_root_url = "https://docs.rs/rucc-cost/0.5.2")]
35
36pub mod cost;
37pub mod cycles;
38pub mod heuristics;
39pub mod table;
40pub mod tune;
41pub mod x86_64;
42
43pub use cost::{Complexity, Cost};
44pub use cycles::{Bytes, Cycles};
45pub use table::{AddrMode, Builder, CostTable, Width};
46pub use tune::{TuneFlag, Tuning};
47
48use rucc_target::Arch;
49
50/// Which of a target's two tables is wanted.
51///
52/// A named type rather than a bare `bool`, because `table(true)` at a call site is a coin toss for
53/// the reader and `table(Goal::Size)` is not.
54#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
55pub enum Goal {
56    /// Make it fast. `-O1`, `-O2`, `-O3`.
57    Speed,
58    /// Make it small. `-Os` and `-Oz`.
59    Size,
60}
61
62impl Goal {
63    /// The goal for a level that has already been asked whether it optimizes for size.
64    ///
65    /// Takes the answer rather than the level, because the level lives in `rucc-session` and this
66    /// crate sits below it. That is not a workaround for the layer rule, it is the layer rule
67    /// working: what an instruction costs on a machine has nothing to do with how the driver was
68    /// invoked, and a dependency the other way would say it did. The caller writes
69    /// `Goal::for_size(level.is_size())`, which is one line and reads correctly.
70    #[must_use]
71    pub const fn for_size(size: bool) -> Self {
72        if size { Self::Size } else { Self::Speed }
73    }
74
75    /// The goal as it appears in a dump.
76    #[must_use]
77    pub const fn as_str(self) -> &'static str {
78        match self {
79            Self::Speed => "speed",
80            Self::Size => "size",
81        }
82    }
83}
84
85impl std::fmt::Display for Goal {
86    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
87        f.write_str(self.as_str())
88    }
89}
90
91/// What a pass asks a target about costs, per section 40.12.
92///
93/// Two methods, because there are two kinds of answer: a number, which comes from one of the two
94/// tables, and a boolean, which does not depend on the goal at all. Whether a microarchitecture
95/// prefers an `lea` to an `add` is not a different fact when optimizing for size.
96pub trait TargetCosts: Send + Sync {
97    /// The table for this goal.
98    fn table(&self, goal: Goal) -> &CostTable;
99
100    /// What this target answers for a tuning flag.
101    fn tune(&self, flag: TuneFlag) -> bool;
102
103    /// What the target is called in a dump.
104    fn name(&self) -> &'static str;
105
106    /// What an unpredictable branch costs at this goal, per section 40.5.
107    ///
108    /// Provided rather than left to each pass, because `BRANCH_COST` at
109    /// `gcc/config/i386/i386.h:2023` is three cases in one line and getting one of them wrong is
110    /// how a well predicted branch ends up if-converted.
111    ///
112    /// Two of the three cases read the table. Optimizing for speed, a predictable branch is free
113    /// and an unpredictable one costs whatever the target says; optimizing for size, a branch is
114    /// the same number of bytes either way, because the branch predictor does not shorten the
115    /// encoding. The one case that does not read the table is the free one, and it does not
116    /// because zero is a claim about hardware rather than about this machine.
117    fn branch_cost(&self, goal: Goal, predictable: bool) -> Cycles {
118        if goal == Goal::Speed && predictable {
119            return heuristics::BRANCH_COST_PREDICTABLE;
120        }
121        self.table(goal).branch_cost
122    }
123}
124
125/// The costs for a target, or nothing for one nobody has written a table for.
126///
127/// x86-64 is the only answer today, because it is the only back end rucc has. The function exists
128/// anyway so that the second target is a file and a match arm rather than a redesign.
129#[must_use]
130pub fn for_arch(arch: Arch) -> Option<&'static dyn TargetCosts> {
131    match arch {
132        Arch::X86_64 => Some(x86_64::COSTS),
133        _ => None,
134    }
135}
136
137#[cfg(test)]
138mod tests {
139    use super::{Goal, TuneFlag, for_arch};
140    use rucc_target::Arch;
141
142    #[test]
143    fn the_only_backend_has_costs() {
144        let costs = for_arch(Arch::X86_64).expect("x86-64 is the back end rucc has");
145        assert_eq!(costs.name(), "x86-64");
146        assert!(!costs.table(Goal::Speed).add.is_infinite());
147    }
148
149    #[test]
150    fn a_target_with_no_back_end_has_no_costs_rather_than_made_up_ones() {
151        // The alternative would be a default table, and a default table is a set of numbers
152        // nobody chose that every pass would believe.
153        assert!(for_arch(Arch::Aarch64).is_none());
154    }
155
156    #[test]
157    fn a_tuning_flag_does_not_depend_on_the_goal() {
158        // There is nothing to assert against here except the shape of the interface: `tune` takes
159        // no goal, so it cannot answer differently for `-Os`. The test is here to fail if
160        // somebody adds one.
161        let costs = for_arch(Arch::X86_64).unwrap();
162        for flag in TuneFlag::ALL {
163            let _: bool = costs.tune(flag);
164        }
165    }
166}
rucc_cost/lib.rs

rucc_cost/
lib.rs
