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