1 //! Top level module for all analysis activities.
2
3 use log::{debug, info};
4
5 use crate::analysis_control_flow::{CFGInfo, InstIxToBlockIxMap};
6 use crate::analysis_data_flow::{
7 calc_def_and_use, calc_livein_and_liveout, collect_move_info, compute_reg_to_ranges_maps,
8 get_range_frags, get_sanitized_reg_uses_for_func, merge_range_frags,
9 };
10 use crate::analysis_reftypes::do_reftypes_analysis;
11 use crate::data_structures::{
12 BlockIx, MoveInfo, RangeFrag, RangeFragIx, RangeFragMetrics, RealRange, RealRangeIx, RealReg,
13 RealRegUniverse, RegClass, RegToRangesMaps, RegVecsAndBounds, TypedIxVec, VirtualRange,
14 VirtualRangeIx, VirtualReg,
15 };
16 use crate::sparse_set::SparseSet;
17 use crate::AlgorithmWithDefaults;
18 use crate::{Function, Reg};
19
20 //=============================================================================
21 // Overall analysis return results, for both control- and data-flow analyses.
22 // All of these failures refer to various problems with the code that the
23 // client (caller) supplied to us.
24
25 #[derive(Clone, Debug)]
26 pub enum AnalysisError {
27 /// A critical edge from "from" to "to" has been found, and should have been
28 /// removed by the caller in the first place.
29 CriticalEdge { from: BlockIx, to: BlockIx },
30
31 /// Some values in the entry block are live in to the function, but are not
32 /// declared as such.
33 EntryLiveinValues(Vec<Reg>),
34
35 /// The incoming code has an explicit or implicit mention (use, def or mod)
36 /// of a real register, which either (1) isn't listed in the universe at
37 /// all, or (2) is one of the `suggested_scratch` registers in the universe.
38 /// (1) isn't allowed because the client must mention *all* real registers
39 /// in the universe. (2) isn't allowed because the client promises to us
40 /// that the `suggested_scratch` registers really are completely unused in
41 /// the incoming code, so that the allocator can use them at literally any
42 /// point it wants.
43 IllegalRealReg(RealReg),
44
45 /// At least one block is dead.
46 UnreachableBlocks,
47
48 /// Implementation limits exceeded. The incoming function is too big. It
49 /// may contain at most 1 million basic blocks and 16 million instructions.
50 ImplementationLimitsExceeded,
51
52 /// Currently LSRA can't generate stackmaps, but the client has requested LSRA *and*
53 /// stackmaps.
54 LSRACantDoStackmaps,
55 }
56
57 impl ToString for AnalysisError {
to_string(&self) -> String58 fn to_string(&self) -> String {
59 match self {
60 AnalysisError::CriticalEdge { from, to } => {
61 format!("critical edge detected, from {:?} to {:?}", from, to)
62 }
63 AnalysisError::EntryLiveinValues(regs) => {
64 let regs_string = regs.iter().map(|reg| format!("{:?}", reg)).collect::<Vec<_>>().join(", ");
65 format!("entry block has love-in value not present in function liveins: {}", regs_string)
66 }
67 AnalysisError::IllegalRealReg(reg) => {
68 format!("instructions mention real register {:?}, which either isn't defined in the register universe, or is a 'suggested_scratch' register", reg)
69 }
70 AnalysisError::UnreachableBlocks => {
71 "at least one block is unreachable".to_string()
72 }
73 AnalysisError::ImplementationLimitsExceeded => {
74 "implementation limits exceeded (more than 1 million blocks or 16 million insns)".to_string()
75 }
76 AnalysisError::LSRACantDoStackmaps => {
77 "LSRA *and* stackmap creation requested; but this combination is not yet supported".to_string()
78 }
79 }
80 }
81 }
82
83 //=============================================================================
84 // Top level for all analysis activities.
85
86 pub struct AnalysisInfo {
87 /// The sanitized per-insn reg-use info
88 pub(crate) reg_vecs_and_bounds: RegVecsAndBounds,
89 /// The real-reg live ranges
90 pub(crate) real_ranges: TypedIxVec<RealRangeIx, RealRange>,
91 /// The virtual-reg live ranges
92 pub(crate) virtual_ranges: TypedIxVec<VirtualRangeIx, VirtualRange>,
93 /// The fragment table
94 pub(crate) range_frags: TypedIxVec<RangeFragIx, RangeFrag>,
95 /// The fragment metrics table
96 pub(crate) range_metrics: TypedIxVec<RangeFragIx, RangeFragMetrics>,
97 /// Estimated execution frequency per block
98 pub(crate) estimated_frequencies: TypedIxVec<BlockIx, u32>,
99 /// Maps InstIxs to BlockIxs
100 pub(crate) inst_to_block_map: InstIxToBlockIxMap,
101 /// Maps from RealRegs to sets of RealRanges and VirtualRegs to sets of VirtualRanges
102 /// (all operating on indices, not the actual objects). This is only generated in
103 /// situations where we need it, hence the `Option`.
104 pub(crate) reg_to_ranges_maps: Option<RegToRangesMaps>,
105 /// Information about registers connected by moves. This is only generated in situations
106 /// where we need it, hence the `Option`.
107 pub(crate) move_info: Option<MoveInfo>,
108 }
109
110 #[inline(never)]
run_analysis<F: Function>( func: &F, reg_universe: &RealRegUniverse, algorithm: AlgorithmWithDefaults, client_wants_stackmaps: bool, reftype_class: RegClass, reftyped_vregs: &Vec<VirtualReg>, ) -> Result<AnalysisInfo, AnalysisError>111 pub fn run_analysis<F: Function>(
112 func: &F,
113 reg_universe: &RealRegUniverse,
114 algorithm: AlgorithmWithDefaults,
115 client_wants_stackmaps: bool,
116 reftype_class: RegClass,
117 reftyped_vregs: &Vec<VirtualReg>, // as supplied by the client
118 ) -> Result<AnalysisInfo, AnalysisError> {
119 info!("run_analysis: begin");
120 info!(
121 " run_analysis: {} blocks, {} insns",
122 func.blocks().len(),
123 func.insns().len()
124 );
125
126 // LSRA can't do reftypes yet. That should have been checked at the top level already.
127 if client_wants_stackmaps {
128 assert!(algorithm != AlgorithmWithDefaults::LinearScan);
129 }
130
131 info!(" run_analysis: begin control flow analysis");
132
133 // First do control flow analysis. This is (relatively) simple. Note that
134 // this can fail, for various reasons; we propagate the failure if so.
135 let cfg_info = CFGInfo::create(func)?;
136
137 // Create the InstIx-to-BlockIx map. This isn't really control-flow
138 // analysis, but needs to be done at some point.
139 let inst_to_block_map = InstIxToBlockIxMap::new(func);
140
141 // Annotate each Block with its estimated execution frequency
142 let mut estimated_frequencies = TypedIxVec::new();
143 for bix in func.blocks() {
144 let mut estimated_frequency = 1;
145 let depth = u32::min(cfg_info.depth_map[bix], 3);
146 for _ in 0..depth {
147 estimated_frequency *= 10;
148 }
149 assert!(bix == BlockIx::new(estimated_frequencies.len()));
150 estimated_frequencies.push(estimated_frequency);
151 }
152
153 info!(" run_analysis: end control flow analysis");
154
155 // Now perform dataflow analysis. This is somewhat more complex.
156 info!(" run_analysis: begin data flow analysis");
157
158 // See `get_sanitized_reg_uses_for_func` for the meaning of "sanitized".
159 let reg_vecs_and_bounds = get_sanitized_reg_uses_for_func(func, reg_universe)
160 .map_err(|reg| AnalysisError::IllegalRealReg(reg))?;
161 assert!(reg_vecs_and_bounds.is_sanitized());
162
163 // Calculate block-local def/use sets.
164 let (def_sets_per_block, use_sets_per_block) =
165 calc_def_and_use(func, ®_vecs_and_bounds, ®_universe);
166 debug_assert!(def_sets_per_block.len() == func.blocks().len() as u32);
167 debug_assert!(use_sets_per_block.len() == func.blocks().len() as u32);
168
169 // Calculate live-in and live-out sets per block, using the traditional
170 // iterate-to-a-fixed-point scheme.
171
172 // `liveout_sets_per_block` is amended below for return blocks, hence `mut`.
173 let (livein_sets_per_block, mut liveout_sets_per_block) = calc_livein_and_liveout(
174 func,
175 &def_sets_per_block,
176 &use_sets_per_block,
177 &cfg_info,
178 ®_universe,
179 );
180 debug_assert!(livein_sets_per_block.len() == func.blocks().len() as u32);
181 debug_assert!(liveout_sets_per_block.len() == func.blocks().len() as u32);
182
183 // Verify livein set of entry block against liveins specified by function
184 // (e.g., ABI params).
185 let func_liveins = SparseSet::from_vec(
186 func.func_liveins()
187 .to_vec()
188 .into_iter()
189 .map(|rreg| rreg.to_reg())
190 .collect(),
191 );
192 if !livein_sets_per_block[func.entry_block()].is_subset_of(&func_liveins) {
193 let mut regs = livein_sets_per_block[func.entry_block()].clone();
194 regs.remove(&func_liveins);
195 return Err(AnalysisError::EntryLiveinValues(regs.to_vec()));
196 }
197
198 // Add function liveouts to every block ending in a return.
199 let func_liveouts = SparseSet::from_vec(
200 func.func_liveouts()
201 .to_vec()
202 .into_iter()
203 .map(|rreg| rreg.to_reg())
204 .collect(),
205 );
206 for block in func.blocks() {
207 let last_iix = func.block_insns(block).last();
208 if func.is_ret(last_iix) {
209 liveout_sets_per_block[block].union(&func_liveouts);
210 }
211 }
212
213 info!(" run_analysis: end data flow analysis");
214
215 // Dataflow analysis is now complete. Now compute the virtual and real live
216 // ranges, in two steps: (1) compute RangeFrags, and (2) merge them
217 // together, guided by flow and liveness info, so as to create the final
218 // VirtualRanges and RealRanges.
219 info!(" run_analysis: begin liveness analysis");
220
221 let (frag_ixs_per_reg, frag_env, frag_metrics_env, vreg_classes) = get_range_frags(
222 func,
223 ®_vecs_and_bounds,
224 ®_universe,
225 &livein_sets_per_block,
226 &liveout_sets_per_block,
227 );
228
229 // These have to be mut because they may get changed below by the call to
230 // `to_reftypes_analysis`.
231 let (mut rlr_env, mut vlr_env) = merge_range_frags(
232 &frag_ixs_per_reg,
233 &frag_env,
234 &frag_metrics_env,
235 &estimated_frequencies,
236 &cfg_info,
237 ®_universe,
238 &vreg_classes,
239 );
240
241 debug_assert!(liveout_sets_per_block.len() == estimated_frequencies.len());
242
243 debug!("");
244 let mut n = 0;
245 for rlr in rlr_env.iter() {
246 debug!(
247 "{:<4?} {}",
248 RealRangeIx::new(n),
249 rlr.show_with_rru(®_universe)
250 );
251 n += 1;
252 }
253
254 debug!("");
255 n = 0;
256 for vlr in vlr_env.iter() {
257 debug!("{:<4?} {:?}", VirtualRangeIx::new(n), vlr);
258 n += 1;
259 }
260
261 // Now a bit of auxiliary info collection, which isn't really either control- or data-flow
262 // analysis.
263
264 // For BT and/or reftypes, we'll also need the reg-to-ranges maps.
265 let reg_to_ranges_maps =
266 if client_wants_stackmaps || algorithm == AlgorithmWithDefaults::Backtracking {
267 Some(compute_reg_to_ranges_maps(
268 func,
269 ®_universe,
270 &rlr_env,
271 &vlr_env,
272 ))
273 } else {
274 None
275 };
276
277 // For BT and/or reftypes, we'll also need information about moves.
278 let move_info = if client_wants_stackmaps || algorithm == AlgorithmWithDefaults::Backtracking {
279 Some(collect_move_info(
280 func,
281 ®_vecs_and_bounds,
282 &estimated_frequencies,
283 ))
284 } else {
285 None
286 };
287
288 info!(" run_analysis: end liveness analysis");
289
290 if client_wants_stackmaps {
291 info!(" run_analysis: begin reftypes analysis");
292 do_reftypes_analysis(
293 &mut rlr_env,
294 &mut vlr_env,
295 &frag_env,
296 reg_to_ranges_maps.as_ref().unwrap(), /* safe because of logic just above */
297 &move_info.as_ref().unwrap(), /* ditto */
298 reftype_class,
299 reftyped_vregs,
300 );
301 info!(" run_analysis: end reftypes analysis");
302 }
303
304 info!("run_analysis: end");
305
306 Ok(AnalysisInfo {
307 reg_vecs_and_bounds,
308 real_ranges: rlr_env,
309 virtual_ranges: vlr_env,
310 range_frags: frag_env,
311 range_metrics: frag_metrics_env,
312 estimated_frequencies,
313 inst_to_block_map,
314 reg_to_ranges_maps,
315 move_info,
316 })
317 }
318