Function cranelift_codegen::timing::remove_constant_phis

pub fn remove_constant_phis() -> TimingToken

Remove constant phi-nodes

Examples found in repository

src/remove_constant_phis.rs (line 219)

pub fn do_remove_constant_phis(func: &mut Function, domtree: &mut DominatorTree) {
    let _tt = timing::remove_constant_phis();
    debug_assert!(domtree.is_valid());

    // 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 bump =
        Bump::with_capacity(domtree.cfg_postorder().len() * 4 * std::mem::size_of::<Value>());
    let mut summaries =
        SecondaryMap::<Block, BlockSummary>::with_capacity(domtree.cfg_postorder().len());

    for b in domtree.cfg_postorder().iter().rev().copied() {
        let formals = func.dfg.block_params(b);
        let mut summary = BlockSummary::new(&bump, 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)
            {
                if let Some(edge) = OutEdge::new(&bump, &func.dfg, inst, dest) {
                    summary.dests.push(edge);
                }
            }
        }

        // 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[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 domtree.cfg_postorder().iter().rev().copied() {
        // For each block, get the formals
        if b == entry_block {
            continue;
        }
        let formals = 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 domtree.cfg_postorder().iter().rev().copied() {
            let src_summary = &summaries[src];
            for edge in &src_summary.dests {
                assert!(edge.block != 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[edge.block];
                let dst_formals = &dst_summary.formals;
                assert_eq!(edge.args.len(), dst_formals.len());
                for (formal, actual) in dst_formals.iter().zip(edge.args) {
                    // 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.iter() {
        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 value 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 `rev()`.
        for (redundant_formal, replacement_val) in del_these.into_iter().rev() {
            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 summary in summaries.values() {
        for edge in &summary.dests {
            if !need_editing.contains(&edge.block) {
                continue;
            }

            let old_actuals = func.dfg[edge.inst].take_value_list().unwrap();
            let num_old_actuals = old_actuals.len(&func.dfg.value_lists);
            let num_fixed_actuals = func.dfg[edge.inst]
                .opcode()
                .constraints()
                .num_fixed_value_arguments();
            let dst_summary = &summaries[edge.block];

            // Check that the numbers of arguments make sense.
            assert!(num_fixed_actuals <= num_old_actuals);
            assert_eq!(
                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, formal_i) in dst_summary.formals.iter().enumerate() {
                let actual_i = old_actuals
                    .get(num_fixed_actuals + i, &func.dfg.value_lists)
                    .unwrap();
                let is_redundant = state.get(*formal_i).is_one();
                if !is_redundant {
                    new_actuals.push(actual_i, &mut func.dfg.value_lists);
                }
            }
            func.dfg[edge.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
    );
}