1 use crate::ir::{Function, SourceLoc, Value, ValueLabel, ValueLabelAssignments, ValueLoc};
2 use crate::isa::TargetIsa;
3 use crate::machinst::MachCompileResult;
4 use crate::regalloc::{Context, RegDiversions};
5 use crate::HashMap;
6 use alloc::collections::BTreeMap;
7 use alloc::vec::Vec;
8 use core::cmp::Ordering;
9 use core::convert::From;
10 use core::iter::Iterator;
11 use core::ops::Bound::*;
12 use core::ops::Deref;
13 use regalloc::Reg;
14
15 #[cfg(feature = "enable-serde")]
16 use serde::{Deserialize, Serialize};
17
18 /// Value location range.
19 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
20 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
21 pub struct ValueLocRange {
22 /// The ValueLoc containing a ValueLabel during this range.
23 pub loc: LabelValueLoc,
24 /// The start of the range. It is an offset in the generated code.
25 pub start: u32,
26 /// The end of the range. It is an offset in the generated code.
27 pub end: u32,
28 }
29
30 /// The particular location for a value.
31 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
32 #[cfg_attr(feature = "enable-serde", derive(Serialize, Deserialize))]
33 pub enum LabelValueLoc {
34 /// Old-backend location: RegUnit, StackSlot, or Unassigned.
35 ValueLoc(ValueLoc),
36 /// New-backend Reg.
37 Reg(Reg),
38 /// New-backend offset from stack pointer.
39 SPOffset(i64),
40 }
41
42 impl From<ValueLoc> for LabelValueLoc {
from(v: ValueLoc) -> Self43 fn from(v: ValueLoc) -> Self {
44 LabelValueLoc::ValueLoc(v)
45 }
46 }
47
48 /// Resulting map of Value labels and their ranges/locations.
49 pub type ValueLabelsRanges = HashMap<ValueLabel, Vec<ValueLocRange>>;
50
build_value_labels_index<T>(func: &Function) -> BTreeMap<T, (Value, ValueLabel)> where T: From<SourceLoc> + Deref<Target = SourceLoc> + Ord + Copy,51 fn build_value_labels_index<T>(func: &Function) -> BTreeMap<T, (Value, ValueLabel)>
52 where
53 T: From<SourceLoc> + Deref<Target = SourceLoc> + Ord + Copy,
54 {
55 if func.dfg.values_labels.is_none() {
56 return BTreeMap::new();
57 }
58 let values_labels = func.dfg.values_labels.as_ref().unwrap();
59
60 // Index values_labels by srcloc/from
61 let mut sorted = BTreeMap::new();
62 for (val, assigns) in values_labels {
63 match assigns {
64 ValueLabelAssignments::Starts(labels) => {
65 for label in labels {
66 if label.from.is_default() {
67 continue;
68 }
69 let srcloc = T::from(label.from);
70 let label = label.label;
71 sorted.insert(srcloc, (*val, label));
72 }
73 }
74 ValueLabelAssignments::Alias { from, value } => {
75 if from.is_default() {
76 continue;
77 }
78 let mut aliased_value = *value;
79 while let Some(ValueLabelAssignments::Alias { value, .. }) =
80 values_labels.get(&aliased_value)
81 {
82 // TODO check/limit recursion?
83 aliased_value = *value;
84 }
85 let from = T::from(*from);
86 if let Some(ValueLabelAssignments::Starts(labels)) =
87 values_labels.get(&aliased_value)
88 {
89 for label in labels {
90 let srcloc = if label.from.is_default() {
91 from
92 } else {
93 from.max(T::from(label.from))
94 };
95 let label = label.label;
96 sorted.insert(srcloc, (*val, label));
97 }
98 }
99 }
100 }
101 }
102 sorted
103 }
104
105 /// Builds ranges and location for specified value labels.
106 /// The labels specified at DataFlowGraph's values_labels collection.
build_value_labels_ranges<T>( func: &Function, regalloc: &Context, mach_compile_result: Option<&MachCompileResult>, isa: &dyn TargetIsa, ) -> ValueLabelsRanges where T: From<SourceLoc> + Deref<Target = SourceLoc> + Ord + Copy,107 pub fn build_value_labels_ranges<T>(
108 func: &Function,
109 regalloc: &Context,
110 mach_compile_result: Option<&MachCompileResult>,
111 isa: &dyn TargetIsa,
112 ) -> ValueLabelsRanges
113 where
114 T: From<SourceLoc> + Deref<Target = SourceLoc> + Ord + Copy,
115 {
116 if let Some(mach_compile_result) = mach_compile_result {
117 return mach_compile_result.value_labels_ranges.clone();
118 }
119
120 let values_labels = build_value_labels_index::<T>(func);
121
122 let mut blocks = func.layout.blocks().collect::<Vec<_>>();
123 blocks.sort_by_key(|block| func.offsets[*block]); // Ensure inst offsets always increase
124 let encinfo = isa.encoding_info();
125 let values_locations = &func.locations;
126 let liveness_ranges = regalloc.liveness().ranges();
127
128 let mut ranges = HashMap::new();
129 let mut add_range = |label, range: (u32, u32), loc: ValueLoc| {
130 if range.0 >= range.1 || !loc.is_assigned() {
131 return;
132 }
133 ranges
134 .entry(label)
135 .or_insert_with(Vec::new)
136 .push(ValueLocRange {
137 loc: loc.into(),
138 start: range.0,
139 end: range.1,
140 });
141 };
142
143 let mut end_offset = 0;
144 let mut tracked_values: Vec<(Value, ValueLabel, u32, ValueLoc)> = Vec::new();
145 let mut divert = RegDiversions::new();
146 for block in blocks {
147 divert.at_block(&func.entry_diversions, block);
148 let mut last_srcloc: Option<T> = None;
149 for (offset, inst, size) in func.inst_offsets(block, &encinfo) {
150 divert.apply(&func.dfg[inst]);
151 end_offset = offset + size;
152 // Remove killed values.
153 tracked_values.retain(|(x, label, start_offset, last_loc)| {
154 let range = liveness_ranges.get(*x);
155 if range.expect("value").killed_at(inst, block, &func.layout) {
156 add_range(*label, (*start_offset, end_offset), *last_loc);
157 return false;
158 }
159 true
160 });
161
162 let srcloc = func.srclocs[inst];
163 if srcloc.is_default() {
164 // Don't process instructions without srcloc.
165 continue;
166 }
167 let srcloc = T::from(srcloc);
168
169 // Record and restart ranges if Value location was changed.
170 for (val, label, start_offset, last_loc) in &mut tracked_values {
171 let new_loc = divert.get(*val, values_locations);
172 if new_loc == *last_loc {
173 continue;
174 }
175 add_range(*label, (*start_offset, end_offset), *last_loc);
176 *start_offset = end_offset;
177 *last_loc = new_loc;
178 }
179
180 // New source locations range started: abandon all tracked values.
181 if last_srcloc.is_some() && last_srcloc.unwrap() > srcloc {
182 for (_, label, start_offset, last_loc) in &tracked_values {
183 add_range(*label, (*start_offset, end_offset), *last_loc);
184 }
185 tracked_values.clear();
186 last_srcloc = None;
187 }
188
189 // Get non-processed Values based on srcloc
190 let range = (
191 match last_srcloc {
192 Some(a) => Excluded(a),
193 None => Unbounded,
194 },
195 Included(srcloc),
196 );
197 let active_values = values_labels.range(range);
198 let active_values = active_values.filter(|(_, (v, _))| {
199 // Ignore dead/inactive Values.
200 let range = liveness_ranges.get(*v);
201 match range {
202 Some(r) => r.reaches_use(inst, block, &func.layout),
203 None => false,
204 }
205 });
206 // Append new Values to the tracked_values.
207 for (_, (val, label)) in active_values {
208 let loc = divert.get(*val, values_locations);
209 tracked_values.push((*val, *label, end_offset, loc));
210 }
211
212 last_srcloc = Some(srcloc);
213 }
214 // Finish all started ranges.
215 for (_, label, start_offset, last_loc) in &tracked_values {
216 add_range(*label, (*start_offset, end_offset), *last_loc);
217 }
218 }
219
220 // Optimize ranges in-place
221 for (_, label_ranges) in ranges.iter_mut() {
222 assert!(!label_ranges.is_empty());
223 label_ranges.sort_by(|a, b| a.start.cmp(&b.start).then_with(|| a.end.cmp(&b.end)));
224
225 // Merge ranges
226 let mut i = 1;
227 let mut j = 0;
228 while i < label_ranges.len() {
229 assert!(label_ranges[j].start <= label_ranges[i].end);
230 if label_ranges[j].loc != label_ranges[i].loc {
231 // Different location
232 if label_ranges[j].end >= label_ranges[i].end {
233 // Consumed by previous range, skipping
234 i += 1;
235 continue;
236 }
237 j += 1;
238 label_ranges[j] = label_ranges[i];
239 i += 1;
240 continue;
241 }
242 if label_ranges[j].end < label_ranges[i].start {
243 // Gap in the range location
244 j += 1;
245 label_ranges[j] = label_ranges[i];
246 i += 1;
247 continue;
248 }
249 // Merge i-th and j-th ranges
250 if label_ranges[j].end < label_ranges[i].end {
251 label_ranges[j].end = label_ranges[i].end;
252 }
253 i += 1;
254 }
255 label_ranges.truncate(j + 1);
256
257 // Cut/move start position of next range, if two neighbor ranges intersect.
258 for i in 0..j {
259 if label_ranges[i].end > label_ranges[i + 1].start {
260 label_ranges[i + 1].start = label_ranges[i].end;
261 assert!(label_ranges[i + 1].start < label_ranges[i + 1].end);
262 }
263 assert!(label_ranges[i].end <= label_ranges[i + 1].start);
264 }
265 }
266 ranges
267 }
268
269 #[derive(Eq, Clone, Copy)]
270 pub struct ComparableSourceLoc(SourceLoc);
271
272 impl From<SourceLoc> for ComparableSourceLoc {
from(s: SourceLoc) -> Self273 fn from(s: SourceLoc) -> Self {
274 Self(s)
275 }
276 }
277
278 impl Deref for ComparableSourceLoc {
279 type Target = SourceLoc;
deref(&self) -> &SourceLoc280 fn deref(&self) -> &SourceLoc {
281 &self.0
282 }
283 }
284
285 impl PartialOrd for ComparableSourceLoc {
partial_cmp(&self, other: &Self) -> Option<Ordering>286 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
287 Some(self.cmp(other))
288 }
289 }
290
291 impl Ord for ComparableSourceLoc {
cmp(&self, other: &Self) -> Ordering292 fn cmp(&self, other: &Self) -> Ordering {
293 self.0.bits().cmp(&other.0.bits())
294 }
295 }
296
297 impl PartialEq for ComparableSourceLoc {
eq(&self, other: &Self) -> bool298 fn eq(&self, other: &Self) -> bool {
299 self.0 == other.0
300 }
301 }
302