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