1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
//! Read only data a function pass has come to need, on its way to the module.
//!
//! A [`crate::Pass`] is handed one function and nothing else, which is what lets it be reasoned
//! about alone and is why it cannot add a global: the globals are the module's, and the module is
//! the thing the pass is not given. Switch conversion to a lookup table is the one pass that needs
//! one anyway. Section 24.4 of `spec/optimizer/24-switch-lowering.md` puts it in the middle end so
//! that what it writes is an ordinary load every pass after it can read, and a load has to load
//! from somewhere.
//!
//! So the pass asks this for a name, writes its load against that name, and leaves the table here.
//! The pipeline adds every table to the module as soon as the pass has finished with the function,
//! before the verifier looks at it, so no function is ever seen naming a table the module does not
//! have. The same shape as `crate::libcall`, which is handed the module whole because it needs
//! one, but narrower: a pass that goes through this can add a constant array and do nothing else
//! to the module, which is what keeps it a function pass.
use std::collections::HashSet;
use rucc_base::{Interner, Symbol};
use rucc_ir::Type;
/// One array a pass has asked for.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Table {
/// The name its load was written against.
pub name: Symbol,
/// The type of every cell, which is an integer of a whole number of bytes.
pub ty: Type,
/// The cells in order, each read with its own sign and held at the type's width when written.
pub cells: Vec<i128>,
/// What each cell also holds the distance to, in the same order, or nothing at all when every
/// cell is only a number. A cell with a name here is that name's address less the address of
/// the cell's own table, plus its number, which the linker works out.
pub to: Vec<Option<Symbol>>,
}
/// Where a pass puts the tables it asks for, until the pipeline takes them.
#[derive(Debug)]
pub struct ReadOnly<'a> {
names: &'a mut Interner,
taken: &'a HashSet<Symbol>,
pointer_bits: u32,
measures: bool,
next: u32,
tables: Vec<Table>,
}
impl<'a> ReadOnly<'a> {
/// A place for tables in a module where `taken` are the names already in use.
///
/// `next` is the number the next name is made from. The pipeline makes one of these for every
/// function a pass runs over, so the count is handed in and read back out with
/// [`ReadOnly::next`], and two functions never get the same name.
#[must_use]
pub fn new(
names: &'a mut Interner,
taken: &'a HashSet<Symbol>,
pointer_bits: u32,
next: u32,
) -> Self {
Self { names, taken, pointer_bits, measures: false, next, tables: Vec::new() }
}
/// The same place, able to hold a table of distances when `measures` is true.
#[must_use]
pub const fn measuring(mut self, measures: bool) -> Self {
self.measures = measures;
self
}
/// Whether a cell may be how far a name is from its table, which [`ReadOnly::distances`]
/// makes.
///
/// That needs a four byte relocation measured from where it is written. x86-64 ELF has one,
/// and it is the only target the pipeline says yes for.
#[must_use]
pub const fn measures(&self) -> bool {
self.measures
}
/// The width of an address on the target, which is how wide an index into a table is made.
#[must_use]
pub const fn pointer_bits(&self) -> u32 {
self.pointer_bits
}
/// Asks for a table and gets back the name to load from it by.
///
/// The name is gcc's, `CSWTCH.` and a number, which nothing written in C can spell because of
/// the dot and which reads the same in a disassembly of either compiler. A name the module
/// already has is stepped over rather than trusted not to be there, since an `asm` label can
/// spell anything.
pub fn table(&mut self, ty: Type, cells: Vec<i128>) -> Symbol {
let name = self.name();
self.tables.push(Table { name, ty, cells, to: Vec::new() });
name
}
/// Asks for a table of how far names are from it and gets back the name to load from it by.
///
/// Cell `k` is four bytes holding the address of the name in `to[k]` plus the bytes beside it,
/// less the address of the table, and zero where `to[k]` is `None`, which is a hole nothing
/// reads. Only asked for where [`ReadOnly::measures`] says it may be, and named the way
/// [`ReadOnly::table`] names one.
pub fn distances(&mut self, to: &[Option<(Symbol, i128)>]) -> Symbol {
let name = self.name();
let cells = to.iter().map(|cell| cell.map_or(0, |(_, bytes)| bytes)).collect();
let to = to.iter().map(|cell| cell.map(|(name, _)| name)).collect();
self.tables.push(Table { name, ty: Type::int(32), cells, to });
name
}
/// A name for the next table, which is one the module does not have.
fn name(&mut self) -> Symbol {
loop {
let name = self.names.intern(&format!("CSWTCH.{}", self.next));
self.next += 1;
if !self.taken.contains(&name) {
return name;
}
}
}
/// The number the next name will be made from.
#[must_use]
pub const fn next(&self) -> u32 {
self.next
}
/// Every table asked for so far, in the order they were asked for.
#[must_use]
pub fn into_tables(self) -> Vec<Table> {
self.tables
}
}
#[cfg(test)]
mod tests {
use std::collections::HashSet;
use rucc_base::Interner;
use rucc_ir::Type;
use super::ReadOnly;
#[test]
fn two_tables_get_two_names_and_a_taken_name_is_stepped_over() {
let mut names = Interner::new();
let taken: HashSet<_> = [names.intern("CSWTCH.1")].into_iter().collect();
let mut data = ReadOnly::new(&mut names, &taken, 64, 0);
let first = data.table(Type::int(8), vec![1, 2]);
let second = data.table(Type::int(8), vec![3]);
assert_eq!(data.next(), 3);
let tables = data.into_tables();
assert_eq!(tables.len(), 2);
assert_eq!(names.resolve(first), "CSWTCH.0");
assert_eq!(names.resolve(second), "CSWTCH.2");
}
#[test]
fn a_table_of_distances_is_four_byte_cells_named_like_any_other() {
let mut names = Interner::new();
let taken = HashSet::new();
let to = [names.intern("a"), names.intern("b")].map(Some);
let mut data = ReadOnly::new(&mut names, &taken, 64, 0).measuring(true);
assert!(data.measures());
let name = data.distances(&[to[0].map(|it| (it, 0)), None, to[1].map(|it| (it, 8))]);
let tables = data.into_tables();
assert_eq!(names.resolve(name), "CSWTCH.0");
assert_eq!(tables[0].ty, Type::int(32));
assert_eq!(tables[0].cells, [0, 0, 8]);
assert_eq!(tables[0].to, [to[0], None, to[1]]);
}
}