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 core::cmp::Ordering;
6 use core::iter::Iterator;
7 use core::ops::Bound::*;
8 use core::ops::Deref;
9 use std::collections::BTreeMap;
10 use std::vec::Vec;
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.
22     pub start: u32,
23     /// The end of the range.
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     let values_labels = build_value_labels_index::<T>(func);
95 
96     let mut ebbs = func.layout.ebbs().collect::<Vec<_>>();
97     ebbs.sort_by_key(|ebb| func.offsets[*ebb]); // Ensure inst offsets always increase
98     let encinfo = isa.encoding_info();
99     let values_locations = &func.locations;
100     let liveness_ranges = regalloc.liveness().ranges();
101 
102     let mut ranges = HashMap::new();
103     let mut add_range = |label, range: (u32, u32), loc: ValueLoc| {
104         if range.0 >= range.1 || !loc.is_assigned() {
105             return;
106         }
107         if !ranges.contains_key(&label) {
108             ranges.insert(label, Vec::new());
109         }
110         ranges.get_mut(&label).unwrap().push(ValueLocRange {
111             loc,
112             start: range.0,
113             end: range.1,
114         });
115     };
116 
117     let mut end_offset = 0;
118     let mut tracked_values: Vec<(Value, ValueLabel, u32, ValueLoc)> = Vec::new();
119     let mut divert = RegDiversions::new();
120     for ebb in ebbs {
121         divert.at_ebb(&func.entry_diversions, ebb);
122         let mut last_srcloc: Option<T> = None;
123         for (offset, inst, size) in func.inst_offsets(ebb, &encinfo) {
124             divert.apply(&func.dfg[inst]);
125             end_offset = offset + size;
126             // Remove killed values.
127             tracked_values.retain(|(x, label, start_offset, last_loc)| {
128                 let range = liveness_ranges.get(*x);
129                 if range.expect("value").killed_at(inst, ebb, &func.layout) {
130                     add_range(*label, (*start_offset, end_offset), *last_loc);
131                     return false;
132                 }
133                 return true;
134             });
135 
136             let srcloc = func.srclocs[inst];
137             if srcloc.is_default() {
138                 // Don't process instructions without srcloc.
139                 continue;
140             }
141             let srcloc = T::from(srcloc);
142 
143             // Record and restart ranges if Value location was changed.
144             for (val, label, start_offset, last_loc) in &mut tracked_values {
145                 let new_loc = divert.get(*val, values_locations);
146                 if new_loc == *last_loc {
147                     continue;
148                 }
149                 add_range(*label, (*start_offset, end_offset), *last_loc);
150                 *start_offset = end_offset;
151                 *last_loc = new_loc;
152             }
153 
154             // New source locations range started: abandon all tracked values.
155             if last_srcloc.is_some() && last_srcloc.as_ref().unwrap() > &srcloc {
156                 for (_, label, start_offset, last_loc) in &tracked_values {
157                     add_range(*label, (*start_offset, end_offset), *last_loc);
158                 }
159                 tracked_values.clear();
160                 last_srcloc = None;
161             }
162 
163             // Get non-processed Values based on srcloc
164             let range = (
165                 match last_srcloc {
166                     Some(a) => Excluded(a),
167                     None => Unbounded,
168                 },
169                 Included(srcloc),
170             );
171             let active_values = values_labels.range(range);
172             let active_values = active_values.filter(|(_, (v, _))| {
173                 // Ignore dead/inactive Values.
174                 let range = liveness_ranges.get(*v);
175                 match range {
176                     Some(r) => r.reaches_use(inst, ebb, &func.layout),
177                     None => false,
178                 }
179             });
180             // Append new Values to the tracked_values.
181             for (_, (val, label)) in active_values {
182                 let loc = divert.get(*val, values_locations);
183                 tracked_values.push((*val, *label, end_offset, loc));
184             }
185 
186             last_srcloc = Some(srcloc);
187         }
188         // Finish all started ranges.
189         for (_, label, start_offset, last_loc) in &tracked_values {
190             add_range(*label, (*start_offset, end_offset), *last_loc);
191         }
192     }
193 
194     // Optimize ranges in-place
195     for (_, label_ranges) in ranges.iter_mut() {
196         assert!(label_ranges.len() > 0);
197         label_ranges.sort_by(|a, b| a.start.cmp(&b.start).then_with(|| a.end.cmp(&b.end)));
198 
199         // Merge ranges
200         let mut i = 1;
201         let mut j = 0;
202         while i < label_ranges.len() {
203             assert!(label_ranges[j].start <= label_ranges[i].end);
204             if label_ranges[j].loc != label_ranges[i].loc {
205                 // Different location
206                 if label_ranges[j].end >= label_ranges[i].end {
207                     // Consumed by previous range, skipping
208                     i += 1;
209                     continue;
210                 }
211                 j += 1;
212                 label_ranges[j] = label_ranges[i];
213                 i += 1;
214                 continue;
215             }
216             if label_ranges[j].end < label_ranges[i].start {
217                 // Gap in the range location
218                 j += 1;
219                 label_ranges[j] = label_ranges[i];
220                 i += 1;
221                 continue;
222             }
223             // Merge i-th and j-th ranges
224             if label_ranges[j].end < label_ranges[i].end {
225                 label_ranges[j].end = label_ranges[i].end;
226             }
227             i += 1;
228         }
229         label_ranges.truncate(j + 1);
230 
231         // Cut/move start position of next range, if two neighbor ranges intersect.
232         for i in 0..j {
233             if label_ranges[i].end > label_ranges[i + 1].start {
234                 label_ranges[i + 1].start = label_ranges[i].end;
235                 assert!(label_ranges[i + 1].start < label_ranges[i + 1].end);
236             }
237             assert!(label_ranges[i].end <= label_ranges[i + 1].start);
238         }
239     }
240     ranges
241 }
242 
243 #[derive(Eq, Clone, Copy)]
244 pub struct ComparableSourceLoc(SourceLoc);
245 
246 impl From<SourceLoc> for ComparableSourceLoc {
247     fn from(s: SourceLoc) -> Self {
248         ComparableSourceLoc(s)
249     }
250 }
251 
252 impl Deref for ComparableSourceLoc {
253     type Target = SourceLoc;
254     fn deref(&self) -> &SourceLoc {
255         &self.0
256     }
257 }
258 
259 impl PartialOrd for ComparableSourceLoc {
260     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
261         Some(self.cmp(other))
262     }
263 }
264 
265 impl Ord for ComparableSourceLoc {
266     fn cmp(&self, other: &Self) -> Ordering {
267         self.0.bits().cmp(&other.0.bits())
268     }
269 }
270 
271 impl PartialEq for ComparableSourceLoc {
272     fn eq(&self, other: &Self) -> bool {
273         self.0 == other.0
274     }
275 }
276