rucc_codegen/select/x86_64.rs
1//! The x86-64 lowering table.
2//!
3//! Everything below the module comment is generated from `rules/x86-64.rules` by `rucc-rules`
4//! when this crate is built, and none of it is in the repository. The rule file is the only
5//! place the rules are written, which is what makes the table that is matched with and the
6//! table `rucc-verify` proves things about the same table.
7//!
8//! To read the rules, read the rule file. To read the automaton they compile into, build the
9//! crate and read `x86-64.rs` under the build directory, which is a file worth looking at once
10//! for the shape of it and never again.
11
12// A guard is emitted as the comparison the rule writes, so a rule saying a shift count is at
13// least zero and less than the width comes out as two comparisons rather than as a range. That
14// is deliberate: the generated line and the rule it came from should read the same, and the
15// suggestion to write it another way is advice for somebody editing code, which nobody here is.
16#![allow(clippy::manual_range_contains)]
17
18include!(concat!(env!("OUT_DIR"), "/x86-64.rs"));
19
20#[cfg(test)]
21mod tests {
22 use rucc_target::x86_64;
23
24 use super::TABLE;
25 use crate::select::Piece;
26
27 /// The prefix a rule file puts in front of a machine term, which is how it says which target
28 /// the term belongs to. It is not part of the opcode.
29 const PREFIX: &str = "x64.";
30
31 /// The two address constructors, which are not instructions. An addressing mode is an
32 /// argument to `lea` and to every memory operand after it, so it is written as a term in the
33 /// rule file and built by the selector into the instruction that takes it.
34 const AMODES: &[&str] =
35 &["amode_base_index_scale", "amode_index_scale", "amode_base", "amode_base_offset"];
36
37 /// Every head this table can write, in and under the replacements.
38 fn heads() -> Vec<&'static str> {
39 let mut found: Vec<&'static str> = TABLE
40 .rules
41 .iter()
42 .flat_map(|rule| rule.replacement.iter())
43 .filter_map(|piece| match piece {
44 Piece::App { head, .. } => Some(*head),
45 _ => None,
46 })
47 .collect();
48 found.sort_unstable();
49 found.dedup();
50 found
51 }
52
53 #[test]
54 fn every_instruction_the_table_writes_is_described() {
55 for head in heads() {
56 if AMODES.contains(&head) {
57 continue;
58 }
59 let opcode = head.strip_prefix(PREFIX).unwrap_or_else(|| {
60 panic!("{head} is neither an x86-64 term nor an addressing mode")
61 });
62 assert!(
63 x86_64::form(opcode).is_some(),
64 "{head} is selected by a rule and `rucc_target::x86_64` does not say what it \
65 does with its operands"
66 );
67 }
68 }
69
70 /// The order the operands of a store are written in, which is the IR's and not a choice this
71 /// file makes.
72 ///
73 /// A pattern is matched against an instruction's operand list by position, so a rule that
74 /// names the address where the IR holds the value is a rule that stores to the value and
75 /// writes the address into memory. Nothing in a proof would catch it, because a proof is
76 /// about the rule file agreeing with itself, and both halves would be wrong in the same way.
77 /// `rucc_ir::Builder::store` takes the value first and the machine instruction takes it last,
78 /// which is why the two halves of one of these rules read in opposite orders.
79 #[test]
80 fn a_store_is_written_with_the_value_first_because_that_is_where_the_ir_keeps_it() {
81 let mut seen = 0;
82 for rule in TABLE.rules {
83 let Some(rest) = rule.pattern.strip_prefix("(store.") else { continue };
84 let (width, operands) = rest.split_once(' ').expect("a store takes operands");
85 assert!(
86 operands.starts_with(&format!("(value.{width} ")),
87 "line {}: {} binds something other than the value it is storing first",
88 rule.line,
89 rule.pattern
90 );
91 assert!(
92 operands.contains("(value.i64 "),
93 "line {}: {} reaches no address",
94 rule.line,
95 rule.pattern
96 );
97 seen += 1;
98 }
99 assert_eq!(seen, 8, "the store rules moved and this test did not follow them");
100 }
101
102 /// The instructions the calling convention writes rather than a rule.
103 ///
104 /// Two kinds of them. Naming the register an argument arrived in, where an argument is depends
105 /// on its position in the signature and on the classification of every argument before it,
106 /// and a rule pattern sees one term and has no way to say any of that, so `crate::abi` builds
107 /// these from the convention instead. Calling a name is the same the other way round: what its
108 /// operands are is whatever the signature made them. The return is not here, because where a
109 /// return value goes depends on nothing but the value, which is exactly what a rule can say.
110 const CONVENTION: &[&str] = &["arg_val_8", "arg_val_16", "arg_val_32", "arg_val_64", "call"];
111
112 /// The instructions the block layout writes rather than a rule.
113 ///
114 /// A rule sees one branch and the layout is about the order of every block in the function, so
115 /// which arm falls through is not something any pattern could say. That answer is what decides
116 /// whether the jump goes to the arm the condition is true for or the other one, and whether
117 /// there is a second jump after it, so all four of these are written where the answer is.
118 const LAYOUT: &[&str] = &["test_rr_8", "jcc_e", "jcc_ne", "jmp"];
119
120 /// The instructions a frame writes rather than a rule.
121 ///
122 /// A prologue, an epilogue, a copy, a spill and a reload are not in the program. They are what
123 /// the allocator's answer costs, so they are written after it, by `crate::finish` reading
124 /// `x86_64::FRAME`. Six of the names that describes are already reachable from a rule, since a
125 /// prologue taking its frame is a subtraction and a spill is a store, and those are not here:
126 /// this is only the ones nothing else can reach.
127 const FRAME: &[&str] =
128 &["push_64", "pop_64", "ret", "mov_rr_64", "movaps_rr", "movaps_rm", "movaps_mr"];
129
130 #[test]
131 fn every_instruction_exempt_from_a_rule_is_one_a_frame_really_writes() {
132 // The same claim as the one about the convention, so that this list cannot grow an opcode
133 // that no frame asks for. In the order `x86_64::FRAME` names them, the moves last because
134 // there is one set of them per class the allocator may spill.
135 let frame = &x86_64::FRAME;
136 let mut written = vec![frame.push, frame.pop, frame.ret];
137 for class in frame.classes {
138 written.extend([class.mov, class.load, class.store]);
139 }
140 // What is left after the ones a rule already reaches, which are the loads and the stores
141 // of a general purpose register, since those are the same instructions a program's own
142 // reads and writes of memory are.
143 written.retain(|opcode| !heads().contains(&format!("{PREFIX}{opcode}").as_str()));
144 assert_eq!(written, FRAME);
145 }
146
147 #[test]
148 fn every_instruction_exempt_from_a_rule_is_one_the_convention_really_writes() {
149 // An exemption list that nothing checks is a hole, since an opcode dropped into it stops
150 // being covered by either direction of the pinning. These are the five `crate::abi` can
151 // name, at the four widths it has names for an argument, and no others.
152 let strip = |head: &'static str| head.strip_prefix(PREFIX).expect("an x86-64 term");
153 let written: Vec<&str> = [8, 16, 32, 64]
154 .into_iter()
155 .map(|bits| {
156 strip(
157 crate::abi::head_of(rucc_ir::Type::int(bits))
158 .expect("every width the pseudos cover"),
159 )
160 })
161 .chain([strip(crate::abi::CALL)])
162 .collect();
163 assert_eq!(written, CONVENTION);
164 }
165
166 #[test]
167 fn every_described_instruction_is_reachable_from_a_rule() {
168 let written = heads();
169 for &(opcode, _) in x86_64::INSTS {
170 if CONVENTION.contains(&opcode) || LAYOUT.contains(&opcode) || FRAME.contains(&opcode) {
171 continue;
172 }
173 let head = format!("{PREFIX}{opcode}");
174 assert!(
175 written.contains(&head.as_str()),
176 "{opcode} is described and no rule in {} selects it",
177 TABLE.source
178 );
179 }
180 }
181}