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