| //! A Constant-Phi-Node removal pass. |
| |
| use crate::dominator_tree::DominatorTree; |
| use crate::entity::EntityList; |
| use crate::fx::FxHashMap; |
| use crate::fx::FxHashSet; |
| use crate::ir::instructions::BranchInfo; |
| use crate::ir::Function; |
| use crate::ir::{Block, Inst, Value}; |
| use crate::timing; |
| |
| use smallvec::{smallvec, SmallVec}; |
| use std::vec::Vec; |
| |
| // A note on notation. For the sake of clarity, this file uses the phrase |
| // "formal parameters" to mean the `Value`s listed in the block head, and |
| // "actual parameters" to mean the `Value`s passed in a branch or a jump: |
| // |
| // block4(v16: i32, v18: i32): <-- formal parameters |
| // ... |
| // brnz v27, block7(v22, v24) <-- actual parameters |
| // jump block6 |
| |
| // This transformation pass (conceptually) partitions all values in the |
| // function into two groups: |
| // |
| // * Group A: values defined by block formal parameters, except for the entry block. |
| // |
| // * Group B: All other values: that is, values defined by instructions, |
| // and the formals of the entry block. |
| // |
| // For each value in Group A, it attempts to establish whether it will have |
| // the value of exactly one member of Group B. If so, the formal parameter is |
| // deleted, all corresponding actual parameters (in jumps/branches to the |
| // defining block) are deleted, and a rename is inserted. |
| // |
| // The entry block is special-cased because (1) we don't know what values flow |
| // to its formals and (2) in any case we can't change its formals. |
| // |
| // Work proceeds in three phases. |
| // |
| // * Phase 1: examine all instructions. For each block, make up a useful |
| // grab-bag of information, `BlockSummary`, that summarises the block's |
| // formals and jump/branch instruction. This is used by Phases 2 and 3. |
| // |
| // * Phase 2: for each value in Group A, try to find a single Group B value |
| // that flows to it. This is done using a classical iterative forward |
| // dataflow analysis over a simple constant-propagation style lattice. It |
| // converges quickly in practice -- I have seen at most 4 iterations. This |
| // is relatively cheap because the iteration is done over the |
| // `BlockSummary`s, and does not visit each instruction. The resulting |
| // fixed point is stored in a `SolverState`. |
| // |
| // * Phase 3: using the `SolverState` and `BlockSummary`, edit the function to |
| // remove redundant formals and actuals, and to insert suitable renames. |
| // |
| // Note that the effectiveness of the analysis depends on on the fact that |
| // there are no copy instructions in Cranelift's IR. If there were, the |
| // computation of `actual_absval` in Phase 2 would have to be extended to |
| // chase through such copies. |
| // |
| // For large functions, the analysis cost using the new AArch64 backend is about |
| // 0.6% of the non-optimising compile time, as measured by instruction counts. |
| // This transformation usually pays for itself several times over, though, by |
| // reducing the isel/regalloc cost downstream. Gains of up to 7% have been |
| // seen for large functions. |
| |
| // The `Value`s (Group B) that can flow to a formal parameter (Group A). |
| #[derive(Clone, Copy, Debug, PartialEq)] |
| enum AbstractValue { |
| // Two or more values flow to this formal. |
| Many, |
| // Exactly one value, as stated, flows to this formal. The `Value`s that |
| // can appear here are exactly: `Value`s defined by `Inst`s, plus the |
| // `Value`s defined by the formals of the entry block. Note that this is |
| // exactly the set of `Value`s that are *not* tracked in the solver below |
| // (see `SolverState`). |
| One(Value /*Group B*/), |
| // No value flows to this formal. |
| None, |
| } |
| |
| impl AbstractValue { |
| fn join(self, other: AbstractValue) -> AbstractValue { |
| match (self, other) { |
| // Joining with `None` has no effect |
| (AbstractValue::None, p2) => p2, |
| (p1, AbstractValue::None) => p1, |
| // Joining with `Many` produces `Many` |
| (AbstractValue::Many, _p2) => AbstractValue::Many, |
| (_p1, AbstractValue::Many) => AbstractValue::Many, |
| // The only interesting case |
| (AbstractValue::One(v1), AbstractValue::One(v2)) => { |
| if v1 == v2 { |
| AbstractValue::One(v1) |
| } else { |
| AbstractValue::Many |
| } |
| } |
| } |
| } |
| fn is_one(self) -> bool { |
| if let AbstractValue::One(_) = self { |
| true |
| } else { |
| false |
| } |
| } |
| } |
| |
| // For some block, a useful bundle of info. The `Block` itself is not stored |
| // here since it will be the key in the associated `FxHashMap` -- see |
| // `summaries` below. For the `SmallVec` tuning params: most blocks have |
| // few parameters, hence `4`. And almost all blocks have either one or two |
| // successors, hence `2`. |
| #[derive(Debug)] |
| struct BlockSummary { |
| // Formal parameters for this `Block` |
| formals: SmallVec<[Value; 4] /*Group A*/>, |
| // For each `Inst` in this block that transfers to another block: the |
| // `Inst` itself, the destination `Block`, and the actual parameters |
| // passed. We don't bother to include transfers that pass zero parameters |
| // since that makes more work for the solver for no purpose. |
| dests: SmallVec<[(Inst, Block, SmallVec<[Value; 4] /*both Groups A and B*/>); 2]>, |
| } |
| impl BlockSummary { |
| fn new(formals: SmallVec<[Value; 4]>) -> Self { |
| Self { |
| formals, |
| dests: smallvec![], |
| } |
| } |
| } |
| |
| // Solver state. This holds a AbstractValue for each formal parameter, except |
| // for those from the entry block. |
| struct SolverState { |
| absvals: FxHashMap<Value /*Group A*/, AbstractValue>, |
| } |
| impl SolverState { |
| fn new() -> Self { |
| Self { |
| absvals: FxHashMap::default(), |
| } |
| } |
| fn get(&self, actual: Value) -> AbstractValue { |
| match self.absvals.get(&actual) { |
| Some(lp) => *lp, |
| None => panic!("SolverState::get: formal param {:?} is untracked?!", actual), |
| } |
| } |
| fn maybe_get(&self, actual: Value) -> Option<&AbstractValue> { |
| self.absvals.get(&actual) |
| } |
| fn set(&mut self, actual: Value, lp: AbstractValue) { |
| match self.absvals.insert(actual, lp) { |
| Some(_old_lp) => {} |
| None => panic!("SolverState::set: formal param {:?} is untracked?!", actual), |
| } |
| } |
| } |
| |
| /// Detect phis in `func` that will only ever produce one value, using a |
| /// classic forward dataflow analysis. Then remove them. |
| #[inline(never)] |
| pub fn do_remove_constant_phis(func: &mut Function, domtree: &mut DominatorTree) { |
| let _tt = timing::remove_constant_phis(); |
| debug_assert!(domtree.is_valid()); |
| |
| // Get the blocks, in reverse postorder |
| let mut blocks_reverse_postorder = Vec::<Block>::new(); |
| for block in domtree.cfg_postorder() { |
| blocks_reverse_postorder.push(*block); |
| } |
| blocks_reverse_postorder.reverse(); |
| |
| // Phase 1 of 3: for each block, make a summary containing all relevant |
| // info. The solver will iterate over the summaries, rather than having |
| // to inspect each instruction in each block. |
| let mut summaries = FxHashMap::<Block, BlockSummary>::default(); |
| |
| for b in &blocks_reverse_postorder { |
| let formals = func.dfg.block_params(*b); |
| let mut summary = BlockSummary::new(SmallVec::from(formals)); |
| |
| for inst in func.layout.block_insts(*b) { |
| let idetails = &func.dfg[inst]; |
| // Note that multi-dest transfers (i.e., branch tables) don't |
| // carry parameters in our IR, so we only have to care about |
| // `SingleDest` here. |
| if let BranchInfo::SingleDest(dest, _) = idetails.analyze_branch(&func.dfg.value_lists) |
| { |
| let inst_var_args = func.dfg.inst_variable_args(inst); |
| // Skip branches/jumps that carry no params. |
| if inst_var_args.len() > 0 { |
| let mut actuals = SmallVec::<[Value; 4]>::new(); |
| for arg in inst_var_args { |
| let arg = func.dfg.resolve_aliases(*arg); |
| actuals.push(arg); |
| } |
| summary.dests.push((inst, dest, actuals)); |
| } |
| } |
| } |
| |
| // Ensure the invariant that all blocks (except for the entry) appear |
| // in the summary, *unless* they have neither formals nor any |
| // param-carrying branches/jumps. |
| if formals.len() > 0 || summary.dests.len() > 0 { |
| summaries.insert(*b, summary); |
| } |
| } |
| |
| // Phase 2 of 3: iterate over the summaries in reverse postorder, |
| // computing new `AbstractValue`s for each tracked `Value`. The set of |
| // tracked `Value`s is exactly Group A as described above. |
| |
| let entry_block = func |
| .layout |
| .entry_block() |
| .expect("remove_constant_phis: entry block unknown"); |
| |
| // Set up initial solver state |
| let mut state = SolverState::new(); |
| |
| for b in &blocks_reverse_postorder { |
| // For each block, get the formals |
| if *b == entry_block { |
| continue; |
| } |
| let formals: &[Value] = func.dfg.block_params(*b); |
| for formal in formals { |
| let mb_old_absval = state.absvals.insert(*formal, AbstractValue::None); |
| assert!(mb_old_absval.is_none()); |
| } |
| } |
| |
| // Solve: repeatedly traverse the blocks in reverse postorder, until there |
| // are no changes. |
| let mut iter_no = 0; |
| loop { |
| iter_no += 1; |
| let mut changed = false; |
| |
| for src in &blocks_reverse_postorder { |
| let mb_src_summary = summaries.get(src); |
| // The src block might have no summary. This means it has no |
| // branches/jumps that carry parameters *and* it doesn't take any |
| // parameters itself. Phase 1 ensures this. So we can ignore it. |
| if mb_src_summary.is_none() { |
| continue; |
| } |
| let src_summary = mb_src_summary.unwrap(); |
| for (_inst, dst, src_actuals) in &src_summary.dests { |
| assert!(*dst != entry_block); |
| // By contrast, the dst block must have a summary. Phase 1 |
| // will have only included an entry in `src_summary.dests` if |
| // that branch/jump carried at least one parameter. So the |
| // dst block does take parameters, so it must have a summary. |
| let dst_summary = summaries |
| .get(dst) |
| .expect("remove_constant_phis: dst block has no summary"); |
| let dst_formals = &dst_summary.formals; |
| assert!(src_actuals.len() == dst_formals.len()); |
| for (formal, actual) in dst_formals.iter().zip(src_actuals.iter()) { |
| // Find the abstract value for `actual`. If it is a block |
| // formal parameter then the most recent abstract value is |
| // to be found in the solver state. If not, then it's a |
| // real value defining point (not a phi), in which case |
| // return it itself. |
| let actual_absval = match state.maybe_get(*actual) { |
| Some(pt) => *pt, |
| None => AbstractValue::One(*actual), |
| }; |
| |
| // And `join` the new value with the old. |
| let formal_absval_old = state.get(*formal); |
| let formal_absval_new = formal_absval_old.join(actual_absval); |
| if formal_absval_new != formal_absval_old { |
| changed = true; |
| state.set(*formal, formal_absval_new); |
| } |
| } |
| } |
| } |
| |
| if !changed { |
| break; |
| } |
| } |
| let mut n_consts = 0; |
| for absval in state.absvals.values() { |
| if absval.is_one() { |
| n_consts += 1; |
| } |
| } |
| |
| // Phase 3 of 3: edit the function to remove constant formals, using the |
| // summaries and the final solver state as a guide. |
| |
| // Make up a set of blocks that need editing. |
| let mut need_editing = FxHashSet::<Block>::default(); |
| for (block, summary) in &summaries { |
| if *block == entry_block { |
| continue; |
| } |
| for formal in &summary.formals { |
| let formal_absval = state.get(*formal); |
| if formal_absval.is_one() { |
| need_editing.insert(*block); |
| break; |
| } |
| } |
| } |
| |
| // Firstly, deal with the formals. For each formal which is redundant, |
| // remove it, and also add a reroute from it to the constant value which |
| // it we know it to be. |
| for b in &need_editing { |
| let mut del_these = SmallVec::<[(Value, Value); 32]>::new(); |
| let formals: &[Value] = func.dfg.block_params(*b); |
| for formal in formals { |
| // The state must give an absval for `formal`. |
| if let AbstractValue::One(replacement_val) = state.get(*formal) { |
| del_these.push((*formal, replacement_val)); |
| } |
| } |
| // We can delete the formals in any order. However, |
| // `remove_block_param` works by sliding backwards all arguments to |
| // the right of the it is asked to delete. Hence when removing more |
| // than one formal, it is significantly more efficient to ask it to |
| // remove the rightmost formal first, and hence this `reverse`. |
| del_these.reverse(); |
| for (redundant_formal, replacement_val) in del_these { |
| func.dfg.remove_block_param(redundant_formal); |
| func.dfg.change_to_alias(redundant_formal, replacement_val); |
| } |
| } |
| |
| // Secondly, visit all branch insns. If the destination has had its |
| // formals changed, change the actuals accordingly. Don't scan all insns, |
| // rather just visit those as listed in the summaries we prepared earlier. |
| for (_src_block, summary) in &summaries { |
| for (inst, dst_block, _src_actuals) in &summary.dests { |
| if !need_editing.contains(dst_block) { |
| continue; |
| } |
| |
| let old_actuals = func.dfg[*inst].take_value_list().unwrap(); |
| let num_old_actuals = old_actuals.len(&func.dfg.value_lists); |
| let num_fixed_actuals = func.dfg[*inst] |
| .opcode() |
| .constraints() |
| .num_fixed_value_arguments(); |
| let dst_summary = summaries.get(&dst_block).unwrap(); |
| |
| // Check that the numbers of arguments make sense. |
| assert!(num_fixed_actuals <= num_old_actuals); |
| assert!(num_fixed_actuals + dst_summary.formals.len() == num_old_actuals); |
| |
| // Create a new value list. |
| let mut new_actuals = EntityList::<Value>::new(); |
| // Copy the fixed args to the new list |
| for i in 0..num_fixed_actuals { |
| let val = old_actuals.get(i, &func.dfg.value_lists).unwrap(); |
| new_actuals.push(val, &mut func.dfg.value_lists); |
| } |
| |
| // Copy the variable args (the actual block params) to the new |
| // list, filtering out redundant ones. |
| for i in 0..dst_summary.formals.len() { |
| let actual_i = old_actuals |
| .get(num_fixed_actuals + i, &func.dfg.value_lists) |
| .unwrap(); |
| let formal_i = dst_summary.formals[i]; |
| let is_redundant = state.get(formal_i).is_one(); |
| if !is_redundant { |
| new_actuals.push(actual_i, &mut func.dfg.value_lists); |
| } |
| } |
| func.dfg[*inst].put_value_list(new_actuals); |
| } |
| } |
| |
| log::debug!( |
| "do_remove_constant_phis: done, {} iters. {} formals, of which {} const.", |
| iter_no, |
| state.absvals.len(), |
| n_consts |
| ); |
| } |
