1 //! A Constant-Phi-Node removal pass.
2
3 use crate::dominator_tree::DominatorTree;
4 use crate::entity::EntityList;
5 use crate::fx::FxHashMap;
6 use crate::fx::FxHashSet;
7 use crate::ir::instructions::BranchInfo;
8 use crate::ir::Function;
9 use crate::ir::{Block, Inst, Value};
10 use crate::timing;
11
12 use smallvec::{smallvec, SmallVec};
13 use std::vec::Vec;
14
15 // A note on notation. For the sake of clarity, this file uses the phrase
16 // "formal parameters" to mean the `Value`s listed in the block head, and
17 // "actual parameters" to mean the `Value`s passed in a branch or a jump:
18 //
19 // block4(v16: i32, v18: i32): <-- formal parameters
20 // ...
21 // brnz v27, block7(v22, v24) <-- actual parameters
22 // jump block6
23
24 // This transformation pass (conceptually) partitions all values in the
25 // function into two groups:
26 //
27 // * Group A: values defined by block formal parameters, except for the entry block.
28 //
29 // * Group B: All other values: that is, values defined by instructions,
30 // and the formals of the entry block.
31 //
32 // For each value in Group A, it attempts to establish whether it will have
33 // the value of exactly one member of Group B. If so, the formal parameter is
34 // deleted, all corresponding actual parameters (in jumps/branches to the
35 // defining block) are deleted, and a rename is inserted.
36 //
37 // The entry block is special-cased because (1) we don't know what values flow
38 // to its formals and (2) in any case we can't change its formals.
39 //
40 // Work proceeds in three phases.
41 //
42 // * Phase 1: examine all instructions. For each block, make up a useful
43 // grab-bag of information, `BlockSummary`, that summarises the block's
44 // formals and jump/branch instruction. This is used by Phases 2 and 3.
45 //
46 // * Phase 2: for each value in Group A, try to find a single Group B value
47 // that flows to it. This is done using a classical iterative forward
48 // dataflow analysis over a simple constant-propagation style lattice. It
49 // converges quickly in practice -- I have seen at most 4 iterations. This
50 // is relatively cheap because the iteration is done over the
51 // `BlockSummary`s, and does not visit each instruction. The resulting
52 // fixed point is stored in a `SolverState`.
53 //
54 // * Phase 3: using the `SolverState` and `BlockSummary`, edit the function to
55 // remove redundant formals and actuals, and to insert suitable renames.
56 //
57 // Note that the effectiveness of the analysis depends on on the fact that
58 // there are no copy instructions in Cranelift's IR. If there were, the
59 // computation of `actual_absval` in Phase 2 would have to be extended to
60 // chase through such copies.
61 //
62 // For large functions, the analysis cost using the new AArch64 backend is about
63 // 0.6% of the non-optimising compile time, as measured by instruction counts.
64 // This transformation usually pays for itself several times over, though, by
65 // reducing the isel/regalloc cost downstream. Gains of up to 7% have been
66 // seen for large functions.
67
68 // The `Value`s (Group B) that can flow to a formal parameter (Group A).
69 #[derive(Clone, Copy, Debug, PartialEq)]
70 enum AbstractValue {
71 // Two or more values flow to this formal.
72 Many,
73 // Exactly one value, as stated, flows to this formal. The `Value`s that
74 // can appear here are exactly: `Value`s defined by `Inst`s, plus the
75 // `Value`s defined by the formals of the entry block. Note that this is
76 // exactly the set of `Value`s that are *not* tracked in the solver below
77 // (see `SolverState`).
78 One(Value /*Group B*/),
79 // No value flows to this formal.
80 None,
81 }
82
83 impl AbstractValue {
join(self, other: AbstractValue) -> AbstractValue84 fn join(self, other: AbstractValue) -> AbstractValue {
85 match (self, other) {
86 // Joining with `None` has no effect
87 (AbstractValue::None, p2) => p2,
88 (p1, AbstractValue::None) => p1,
89 // Joining with `Many` produces `Many`
90 (AbstractValue::Many, _p2) => AbstractValue::Many,
91 (_p1, AbstractValue::Many) => AbstractValue::Many,
92 // The only interesting case
93 (AbstractValue::One(v1), AbstractValue::One(v2)) => {
94 if v1 == v2 {
95 AbstractValue::One(v1)
96 } else {
97 AbstractValue::Many
98 }
99 }
100 }
101 }
is_one(self) -> bool102 fn is_one(self) -> bool {
103 if let AbstractValue::One(_) = self {
104 true
105 } else {
106 false
107 }
108 }
109 }
110
111 // For some block, a useful bundle of info. The `Block` itself is not stored
112 // here since it will be the key in the associated `FxHashMap` -- see
113 // `summaries` below. For the `SmallVec` tuning params: most blocks have
114 // few parameters, hence `4`. And almost all blocks have either one or two
115 // successors, hence `2`.
116 #[derive(Debug)]
117 struct BlockSummary {
118 // Formal parameters for this `Block`
119 formals: SmallVec<[Value; 4] /*Group A*/>,
120 // For each `Inst` in this block that transfers to another block: the
121 // `Inst` itself, the destination `Block`, and the actual parameters
122 // passed. We don't bother to include transfers that pass zero parameters
123 // since that makes more work for the solver for no purpose.
124 dests: SmallVec<[(Inst, Block, SmallVec<[Value; 4] /*both Groups A and B*/>); 2]>,
125 }
126 impl BlockSummary {
new(formals: SmallVec<[Value; 4]>) -> Self127 fn new(formals: SmallVec<[Value; 4]>) -> Self {
128 Self {
129 formals,
130 dests: smallvec![],
131 }
132 }
133 }
134
135 // Solver state. This holds a AbstractValue for each formal parameter, except
136 // for those from the entry block.
137 struct SolverState {
138 absvals: FxHashMap<Value /*Group A*/, AbstractValue>,
139 }
140 impl SolverState {
new() -> Self141 fn new() -> Self {
142 Self {
143 absvals: FxHashMap::default(),
144 }
145 }
get(&self, actual: Value) -> AbstractValue146 fn get(&self, actual: Value) -> AbstractValue {
147 match self.absvals.get(&actual) {
148 Some(lp) => *lp,
149 None => panic!("SolverState::get: formal param {:?} is untracked?!", actual),
150 }
151 }
maybe_get(&self, actual: Value) -> Option<&AbstractValue>152 fn maybe_get(&self, actual: Value) -> Option<&AbstractValue> {
153 self.absvals.get(&actual)
154 }
set(&mut self, actual: Value, lp: AbstractValue)155 fn set(&mut self, actual: Value, lp: AbstractValue) {
156 match self.absvals.insert(actual, lp) {
157 Some(_old_lp) => {}
158 None => panic!("SolverState::set: formal param {:?} is untracked?!", actual),
159 }
160 }
161 }
162
163 /// Detect phis in `func` that will only ever produce one value, using a
164 /// classic forward dataflow analysis. Then remove them.
165 #[inline(never)]
do_remove_constant_phis(func: &mut Function, domtree: &mut DominatorTree)166 pub fn do_remove_constant_phis(func: &mut Function, domtree: &mut DominatorTree) {
167 let _tt = timing::remove_constant_phis();
168 debug_assert!(domtree.is_valid());
169
170 // Get the blocks, in reverse postorder
171 let mut blocks_reverse_postorder = Vec::<Block>::new();
172 for block in domtree.cfg_postorder() {
173 blocks_reverse_postorder.push(*block);
174 }
175 blocks_reverse_postorder.reverse();
176
177 // Phase 1 of 3: for each block, make a summary containing all relevant
178 // info. The solver will iterate over the summaries, rather than having
179 // to inspect each instruction in each block.
180 let mut summaries = FxHashMap::<Block, BlockSummary>::default();
181
182 for b in &blocks_reverse_postorder {
183 let formals = func.dfg.block_params(*b);
184 let mut summary = BlockSummary::new(SmallVec::from(formals));
185
186 for inst in func.layout.block_insts(*b) {
187 let idetails = &func.dfg[inst];
188 // Note that multi-dest transfers (i.e., branch tables) don't
189 // carry parameters in our IR, so we only have to care about
190 // `SingleDest` here.
191 if let BranchInfo::SingleDest(dest, _) = idetails.analyze_branch(&func.dfg.value_lists)
192 {
193 let inst_var_args = func.dfg.inst_variable_args(inst);
194 // Skip branches/jumps that carry no params.
195 if inst_var_args.len() > 0 {
196 let mut actuals = SmallVec::<[Value; 4]>::new();
197 for arg in inst_var_args {
198 let arg = func.dfg.resolve_aliases(*arg);
199 actuals.push(arg);
200 }
201 summary.dests.push((inst, dest, actuals));
202 }
203 }
204 }
205
206 // Ensure the invariant that all blocks (except for the entry) appear
207 // in the summary, *unless* they have neither formals nor any
208 // param-carrying branches/jumps.
209 if formals.len() > 0 || summary.dests.len() > 0 {
210 summaries.insert(*b, summary);
211 }
212 }
213
214 // Phase 2 of 3: iterate over the summaries in reverse postorder,
215 // computing new `AbstractValue`s for each tracked `Value`. The set of
216 // tracked `Value`s is exactly Group A as described above.
217
218 let entry_block = func
219 .layout
220 .entry_block()
221 .expect("remove_constant_phis: entry block unknown");
222
223 // Set up initial solver state
224 let mut state = SolverState::new();
225
226 for b in &blocks_reverse_postorder {
227 // For each block, get the formals
228 if *b == entry_block {
229 continue;
230 }
231 let formals: &[Value] = func.dfg.block_params(*b);
232 for formal in formals {
233 let mb_old_absval = state.absvals.insert(*formal, AbstractValue::None);
234 assert!(mb_old_absval.is_none());
235 }
236 }
237
238 // Solve: repeatedly traverse the blocks in reverse postorder, until there
239 // are no changes.
240 let mut iter_no = 0;
241 loop {
242 iter_no += 1;
243 let mut changed = false;
244
245 for src in &blocks_reverse_postorder {
246 let mb_src_summary = summaries.get(src);
247 // The src block might have no summary. This means it has no
248 // branches/jumps that carry parameters *and* it doesn't take any
249 // parameters itself. Phase 1 ensures this. So we can ignore it.
250 if mb_src_summary.is_none() {
251 continue;
252 }
253 let src_summary = mb_src_summary.unwrap();
254 for (_inst, dst, src_actuals) in &src_summary.dests {
255 assert!(*dst != entry_block);
256 // By contrast, the dst block must have a summary. Phase 1
257 // will have only included an entry in `src_summary.dests` if
258 // that branch/jump carried at least one parameter. So the
259 // dst block does take parameters, so it must have a summary.
260 let dst_summary = summaries
261 .get(dst)
262 .expect("remove_constant_phis: dst block has no summary");
263 let dst_formals = &dst_summary.formals;
264 assert!(src_actuals.len() == dst_formals.len());
265 for (formal, actual) in dst_formals.iter().zip(src_actuals.iter()) {
266 // Find the abstract value for `actual`. If it is a block
267 // formal parameter then the most recent abstract value is
268 // to be found in the solver state. If not, then it's a
269 // real value defining point (not a phi), in which case
270 // return it itself.
271 let actual_absval = match state.maybe_get(*actual) {
272 Some(pt) => *pt,
273 None => AbstractValue::One(*actual),
274 };
275
276 // And `join` the new value with the old.
277 let formal_absval_old = state.get(*formal);
278 let formal_absval_new = formal_absval_old.join(actual_absval);
279 if formal_absval_new != formal_absval_old {
280 changed = true;
281 state.set(*formal, formal_absval_new);
282 }
283 }
284 }
285 }
286
287 if !changed {
288 break;
289 }
290 }
291 let mut n_consts = 0;
292 for absval in state.absvals.values() {
293 if absval.is_one() {
294 n_consts += 1;
295 }
296 }
297
298 // Phase 3 of 3: edit the function to remove constant formals, using the
299 // summaries and the final solver state as a guide.
300
301 // Make up a set of blocks that need editing.
302 let mut need_editing = FxHashSet::<Block>::default();
303 for (block, summary) in &summaries {
304 if *block == entry_block {
305 continue;
306 }
307 for formal in &summary.formals {
308 let formal_absval = state.get(*formal);
309 if formal_absval.is_one() {
310 need_editing.insert(*block);
311 break;
312 }
313 }
314 }
315
316 // Firstly, deal with the formals. For each formal which is redundant,
317 // remove it, and also add a reroute from it to the constant value which
318 // it we know it to be.
319 for b in &need_editing {
320 let mut del_these = SmallVec::<[(Value, Value); 32]>::new();
321 let formals: &[Value] = func.dfg.block_params(*b);
322 for formal in formals {
323 // The state must give an absval for `formal`.
324 if let AbstractValue::One(replacement_val) = state.get(*formal) {
325 del_these.push((*formal, replacement_val));
326 }
327 }
328 // We can delete the formals in any order. However,
329 // `remove_block_param` works by sliding backwards all arguments to
330 // the right of the it is asked to delete. Hence when removing more
331 // than one formal, it is significantly more efficient to ask it to
332 // remove the rightmost formal first, and hence this `reverse`.
333 del_these.reverse();
334 for (redundant_formal, replacement_val) in del_these {
335 func.dfg.remove_block_param(redundant_formal);
336 func.dfg.change_to_alias(redundant_formal, replacement_val);
337 }
338 }
339
340 // Secondly, visit all branch insns. If the destination has had its
341 // formals changed, change the actuals accordingly. Don't scan all insns,
342 // rather just visit those as listed in the summaries we prepared earlier.
343 for (_src_block, summary) in &summaries {
344 for (inst, dst_block, _src_actuals) in &summary.dests {
345 if !need_editing.contains(dst_block) {
346 continue;
347 }
348
349 let old_actuals = func.dfg[*inst].take_value_list().unwrap();
350 let num_old_actuals = old_actuals.len(&func.dfg.value_lists);
351 let num_fixed_actuals = func.dfg[*inst]
352 .opcode()
353 .constraints()
354 .num_fixed_value_arguments();
355 let dst_summary = summaries.get(&dst_block).unwrap();
356
357 // Check that the numbers of arguments make sense.
358 assert!(num_fixed_actuals <= num_old_actuals);
359 assert!(num_fixed_actuals + dst_summary.formals.len() == num_old_actuals);
360
361 // Create a new value list.
362 let mut new_actuals = EntityList::<Value>::new();
363 // Copy the fixed args to the new list
364 for i in 0..num_fixed_actuals {
365 let val = old_actuals.get(i, &func.dfg.value_lists).unwrap();
366 new_actuals.push(val, &mut func.dfg.value_lists);
367 }
368
369 // Copy the variable args (the actual block params) to the new
370 // list, filtering out redundant ones.
371 for i in 0..dst_summary.formals.len() {
372 let actual_i = old_actuals
373 .get(num_fixed_actuals + i, &func.dfg.value_lists)
374 .unwrap();
375 let formal_i = dst_summary.formals[i];
376 let is_redundant = state.get(formal_i).is_one();
377 if !is_redundant {
378 new_actuals.push(actual_i, &mut func.dfg.value_lists);
379 }
380 }
381 func.dfg[*inst].put_value_list(new_actuals);
382 }
383 }
384
385 log::debug!(
386 "do_remove_constant_phis: done, {} iters. {} formals, of which {} const.",
387 iter_no,
388 state.absvals.len(),
389 n_consts
390 );
391 }
392