//! 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;

use crate::ir::instructions::BranchInfo;

use crate::ir::Function;

use crate::ir::{Block, Inst, Value};

use crate::timing;

use arrayvec::ArrayVec;

use bumpalo::Bump;

use cranelift_entity::SecondaryMap;

use smallvec::SmallVec;

// 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 {

        matches!(self, AbstractValue::One(_))

    }

}

#[derive(Clone, Copy, Debug)]

struct OutEdge<'a> {

    /// An instruction that transfers control.

    inst: Inst,

    /// The block that control is transferred to.

    block: Block,

    /// The arguments to that block.

    ///

    /// These values can be from both groups A and B.

    args: &'a [Value],

}

impl<'a> OutEdge<'a> {

    /// Construct a new `OutEdge` for the given instruction.

    ///

    /// Returns `None` if this is an edge without any block arguments, which

    /// means we can ignore it for this analysis's purposes.

    #[inline]

    fn new(bump: &'a Bump, dfg: &ir::DataFlowGraph, inst: Inst, block: Block) -> Option<Self> {

        let inst_var_args = dfg.inst_variable_args(inst);

        // Skip edges without params.

        if inst_var_args.is_empty() {

            return None;

        }

        Some(OutEdge {

            inst,

            block,

            args: bump.alloc_slice_fill_iter(

                inst_var_args

                    .iter()

                    .map(|value| dfg.resolve_aliases(*value)),

            ),

        })

    }

}

/// 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(Clone, Debug, Default)]

struct BlockSummary<'a> {

    /// Formal parameters for this `Block`.

    ///

    /// These values are from group A.

    formals: &'a [Value],

    /// Each outgoing edge from this block.

    ///

    /// We don't bother to include transfers that pass zero parameters

    /// since that makes more work for the solver for no purpose.

    ///

    /// Note that, because blocks used with `br_table`s cannot have block

    /// arguments, there are at most two outgoing edges from these blocks.

    dests: ArrayVec<OutEdge<'a>, 2>,

}

impl<'a> BlockSummary<'a> {

    /// Construct a new `BlockSummary`, using `values` as its backing storage.

    #[inline]

    fn new(bump: &'a Bump, formals: &[Value]) -> Self {

        Self {

            formals: bump.alloc_slice_copy(formals),

            dests: Default::default(),

        }

    }

}

/// 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 {

        *self

            .absvals

            .get(&actual)

            .unwrap_or_else(|| 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());

    // 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

    );

}