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, get_range_frags, get_sanitized_reg_uses_for_func,
8 merge_range_frags, set_virtual_range_metrics,
9 };
10 use crate::data_structures::{
11 BlockIx, RangeFrag, RangeFragIx, RealRange, RealRangeIx, RealReg, RealRegUniverse, Reg,
12 RegVecsAndBounds, TypedIxVec, VirtualRange, VirtualRangeIx,
13 };
14 use crate::sparse_set::SparseSet;
15 use crate::Function;
16
17 //=============================================================================
18 // Overall analysis return results, for both control- and data-flow analyses.
19 // All of these failures refer to various problems with the code that the
20 // client (caller) supplied to us.
21
22 #[derive(Clone, Debug)]
23 pub enum AnalysisError {
24 /// A critical edge from "from" to "to" has been found, and should have been
25 /// removed by the caller in the first place.
26 CriticalEdge { from: BlockIx, to: BlockIx },
27
28 /// Some values in the entry block are live in to the function, but are not
29 /// declared as such.
30 EntryLiveinValues,
31
32 /// The incoming code has an explicit or implicit mention (use, def or mod)
33 /// of a real register, which either (1) isn't listed in the universe at
34 /// all, or (2) is one of the `suggested_scratch` registers in the universe.
35 /// (1) isn't allowed because the client must mention *all* real registers
36 /// in the universe. (2) isn't allowed because the client promises to us
37 /// that the `suggested_scratch` registers really are completely unused in
38 /// the incoming code, so that the allocator can use them at literally any
39 /// point it wants.
40 IllegalRealReg(RealReg),
41
42 /// At least one block is dead.
43 UnreachableBlocks,
44
45 /// Implementation limits exceeded. The incoming function is too big. It
46 /// may contain at most 1 million basic blocks and 16 million instructions.
47 ImplementationLimitsExceeded,
48 }
49
50 impl ToString for AnalysisError {
to_string(&self) -> String51 fn to_string(&self) -> String {
52 match self {
53 AnalysisError::CriticalEdge { from, to } => {
54 format!("critical edge detected, from {:?} to {:?}", from, to)
55 }
56 AnalysisError::EntryLiveinValues => {
57 "entry block has live-in value not present in function liveins".into()
58 }
59 AnalysisError::IllegalRealReg(reg) => {
60 format!("instructions mention real register {:?}, which either isn't defined in the register universe, or is a 'suggested_scratch' register", reg)
61 }
62 AnalysisError::UnreachableBlocks => {
63 "at least one block is unreachable".to_string()
64 }
65 AnalysisError::ImplementationLimitsExceeded => {
66 "implementation limits exceeded (more than 1 million blocks or 16 million insns)".to_string()
67 }
68 }
69 }
70 }
71
72 //=============================================================================
73 // Top level for all analysis activities.
74
75 #[inline(never)]
run_analysis<F: Function>( func: &F, reg_universe: &RealRegUniverse, ) -> Result< ( RegVecsAndBounds, TypedIxVec<RealRangeIx, RealRange>, TypedIxVec<VirtualRangeIx, VirtualRange>, TypedIxVec<RangeFragIx, RangeFrag>, TypedIxVec<BlockIx, SparseSet<Reg>>, TypedIxVec<BlockIx, u32>, InstIxToBlockIxMap, ), AnalysisError, >76 pub fn run_analysis<F: Function>(
77 func: &F,
78 reg_universe: &RealRegUniverse,
79 ) -> Result<
80 (
81 // The sanitized per-insn reg-use info
82 RegVecsAndBounds,
83 // The real-reg live ranges
84 TypedIxVec<RealRangeIx, RealRange>,
85 // The virtual-reg live ranges
86 TypedIxVec<VirtualRangeIx, VirtualRange>,
87 // The fragment table
88 TypedIxVec<RangeFragIx, RangeFrag>,
89 // Liveouts per block
90 TypedIxVec<BlockIx, SparseSet<Reg>>,
91 // Estimated execution frequency per block
92 TypedIxVec<BlockIx, u32>,
93 // Maps InstIxs to BlockIxs
94 InstIxToBlockIxMap,
95 ),
96 AnalysisError,
97 > {
98 info!("run_analysis: begin");
99 info!(
100 " run_analysis: {} blocks, {} insns",
101 func.blocks().len(),
102 func.insns().len()
103 );
104 info!(" run_analysis: begin control flow analysis");
105
106 // First do control flow analysis. This is (relatively) simple. Note that
107 // this can fail, for various reasons; we propagate the failure if so.
108 let cfg_info = CFGInfo::create(func)?;
109
110 // Create the InstIx-to-BlockIx map. This isn't really control-flow
111 // analysis, but needs to be done at some point.
112 let inst_to_block_map = InstIxToBlockIxMap::new(func);
113
114 // Annotate each Block with its estimated execution frequency
115 let mut estimated_frequencies = TypedIxVec::new();
116 for bix in func.blocks() {
117 let mut estimated_frequency = 1;
118 let mut depth = cfg_info.depth_map[bix];
119 if depth > 3 {
120 depth = 3;
121 }
122 for _ in 0..depth {
123 estimated_frequency *= 10;
124 }
125 assert!(bix == BlockIx::new(estimated_frequencies.len()));
126 estimated_frequencies.push(estimated_frequency);
127 }
128
129 info!(" run_analysis: end control flow analysis");
130
131 // Now perform dataflow analysis. This is somewhat more complex.
132 info!(" run_analysis: begin data flow analysis");
133
134 // See `get_sanitized_reg_uses_for_func` for the meaning of "sanitized".
135 let reg_vecs_and_bounds = get_sanitized_reg_uses_for_func(func, reg_universe)
136 .map_err(|reg| AnalysisError::IllegalRealReg(reg))?;
137 assert!(reg_vecs_and_bounds.is_sanitized());
138
139 // Calculate block-local def/use sets.
140 let (def_sets_per_block, use_sets_per_block) =
141 calc_def_and_use(func, ®_vecs_and_bounds, ®_universe);
142 debug_assert!(def_sets_per_block.len() == func.blocks().len() as u32);
143 debug_assert!(use_sets_per_block.len() == func.blocks().len() as u32);
144
145 // Calculate live-in and live-out sets per block, using the traditional
146 // iterate-to-a-fixed-point scheme.
147
148 // `liveout_sets_per_block` is amended below for return blocks, hence `mut`.
149 let (livein_sets_per_block, mut liveout_sets_per_block) = calc_livein_and_liveout(
150 func,
151 &def_sets_per_block,
152 &use_sets_per_block,
153 &cfg_info,
154 ®_universe,
155 );
156 debug_assert!(livein_sets_per_block.len() == func.blocks().len() as u32);
157 debug_assert!(liveout_sets_per_block.len() == func.blocks().len() as u32);
158
159 // Verify livein set of entry block against liveins specified by function
160 // (e.g., ABI params).
161 let func_liveins = SparseSet::from_vec(
162 func.func_liveins()
163 .to_vec()
164 .into_iter()
165 .map(|rreg| rreg.to_reg())
166 .collect(),
167 );
168 if !livein_sets_per_block[func.entry_block()].is_subset_of(&func_liveins) {
169 return Err(AnalysisError::EntryLiveinValues);
170 }
171
172 // Add function liveouts to every block ending in a return.
173 let func_liveouts = SparseSet::from_vec(
174 func.func_liveouts()
175 .to_vec()
176 .into_iter()
177 .map(|rreg| rreg.to_reg())
178 .collect(),
179 );
180 for block in func.blocks() {
181 let last_iix = func.block_insns(block).last();
182 if func.is_ret(last_iix) {
183 liveout_sets_per_block[block].union(&func_liveouts);
184 }
185 }
186
187 info!(" run_analysis: end data flow analysis");
188
189 // Dataflow analysis is now complete. Now compute the virtual and real live
190 // ranges, in two steps: (1) compute RangeFrags, and (2) merge them
191 // together, guided by flow and liveness info, so as to create the final
192 // VirtualRanges and RealRanges.
193 info!(" run_analysis: begin liveness analysis");
194
195 let (frag_ixs_per_reg, frag_env) = get_range_frags(
196 func,
197 &livein_sets_per_block,
198 &liveout_sets_per_block,
199 ®_vecs_and_bounds,
200 ®_universe,
201 );
202
203 let (rlr_env, mut vlr_env) = merge_range_frags(&frag_ixs_per_reg, &frag_env, &cfg_info);
204
205 set_virtual_range_metrics(&mut vlr_env, &frag_env, &estimated_frequencies);
206
207 debug_assert!(liveout_sets_per_block.len() == estimated_frequencies.len());
208
209 debug!("");
210 let mut n = 0;
211 for rlr in rlr_env.iter() {
212 debug!(
213 "{:<4?} {}",
214 RealRangeIx::new(n),
215 rlr.show_with_rru(®_universe)
216 );
217 n += 1;
218 }
219
220 debug!("");
221 n = 0;
222 for vlr in vlr_env.iter() {
223 debug!("{:<4?} {:?}", VirtualRangeIx::new(n), vlr);
224 n += 1;
225 }
226
227 info!(" run_analysis: end liveness analysis");
228 info!("run_analysis: end");
229
230 Ok((
231 reg_vecs_and_bounds,
232 rlr_env,
233 vlr_env,
234 frag_env,
235 liveout_sets_per_block,
236 estimated_frequencies,
237 inst_to_block_map,
238 ))
239 }
240