cranelift_codegen/
remove_constant_phis.rs

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