frontend 0.4.1

//! Global value numbering.
//!
//! MIR may contain repeated and/or redundant computations. The objective of this pass is to detect
//! such redundancies and re-use the already-computed result when possible.
//!
//! From those assignments, we construct a mapping `VnIndex -> Vec<(Local, Location)>` of available
//! values, the locals in which they are stored, and the assignment location.
//!
//! We traverse all assignments `x = rvalue` and operands.
//!
//! For each SSA one, we compute a symbolic representation of values that are assigned to SSA
//! locals. This symbolic representation is defined by the `Value` enum. Each produced instance of
//! `Value` is interned as a `VnIndex`, which allows us to cheaply compute identical values.
//!
//! For each non-SSA
//! one, we compute the `VnIndex` of the rvalue. If this `VnIndex` is associated to a constant, we
//! replace the rvalue/operand by that constant. Otherwise, if there is an SSA local `y`
//! associated to this `VnIndex`, and if its definition location strictly dominates the assignment
//! to `x`, we replace the assignment by `x = y`.
//!
//! By opportunity, this pass simplifies some `Rvalue`s based on the accumulated knowledge.
//!
//! # Operational semantic
//!
//! Operationally, this pass attempts to prove bitwise equality between locals. Given this MIR:
//! ```ignore (MIR)
//! _a = some value // has VnIndex i
//! // some MIR
//! _b = some other value // also has VnIndex i
//! ```
//!
//! We consider it to be replaceable by:
//! ```ignore (MIR)
//! _a = some value // has VnIndex i
//! // some MIR
//! _c = some other value // also has VnIndex i
//! assume(_a bitwise equal to _c) // follows from having the same VnIndex
//! _b = _a // follows from the `assume`
//! ```
//!
//! Which is simplifiable to:
//! ```ignore (MIR)
//! _a = some value // has VnIndex i
//! // some MIR
//! _b = _a
//! ```
//!
//! # Handling of references
//!
//! We handle references by assigning a different "provenance" index to each Ref/RawPtr rvalue.
//! This ensure that we do not spuriously merge borrows that should not be merged. For instance:
//! ```ignore (MIR)
//! _x = &_a;
//! _a = 0;
//! _y = &_a; // cannot be turned into `_y = _x`!
//! ```
//!
//! On top of that, we consider all the derefs of an immutable reference to a freeze type to give
//! the same value:
//! ```ignore (MIR)
//! _a = *_b // _b is &Freeze
//! _c = *_b // replaced by _c = _a
//! ```
//!
//! # Determinism of constant propagation
//!
//! When registering a new `Value`, we attempt to opportunistically evaluate it as a constant.
//! The evaluated form is inserted in `evaluated` as an `OpTy` or `None` if evaluation failed.
//!
//! The difficulty is non-deterministic evaluation of MIR constants. Some `Const` can have
//! different runtime values each time they are evaluated. This happens with valtrees that
//! generate a new allocation each time they are used. This is checked by `is_deterministic`.
//!
//! Meanwhile, we want to be able to read indirect constants. For instance:
//! ```
//! static A: &'static &'static u8 = &&63;
//! fn foo() -> u8 {
//!     **A // We want to replace by 63.
//! }
//! fn bar() -> u8 {
//!     b"abc"[1] // We want to replace by 'b'.
//! }
//! ```
//!
//! The `Value::Constant` variant stores a possibly unevaluated constant. Evaluating that constant
//! may be non-deterministic. When that happens, we assign a disambiguator to ensure that we do not
//! merge the constants. See `duplicate_slice` test in `gvn.rs`.
//!
//! Conversely, some constants cannot cross function boundaries, which could happen because of
//! inlining. For instance, constants that contain a fn pointer (`AllocId` pointing to a
//! `GlobalAlloc::Function`) point to a different symbol in each codegen unit. To avoid this,
//! when writing constants in MIR, we do not write `Const`s that contain `AllocId`s. This is
//! checked by `may_have_provenance`. See <https://github.com/rust-lang/rust/issues/128775> for
//! more information.

// `#![no_std]`: these arrive with the standard prelude and name no path, so a `std::`
// search cannot see them - and a `#[derive]` can use them without the name appearing
// in this file at all, which is why they are not trimmed by inspection.
use alloc::borrow::ToOwned;
// `discard_err`/`report_err` and friends: an extension trait now that `InterpResult` is a `Result`.
use crate::rustc_middle::mir::interpret::InterpResultExt as _;
use alloc::boxed::Box;
use alloc::format;
use alloc::string::{String, ToString};
use alloc::vec;
use alloc::vec::Vec;

use alloc::borrow::Cow;
use core::hash::{Hash, Hasher};

use either::Either;
use itertools::Itertools as _;
use crate::rustc_abi::{self as abi, BackendRepr, FIRST_VARIANT, FieldIdx, Primitive, Size, VariantIdx};
use crate::rustc_arena::DroplessArena;
use crate::rustc_const_eval::const_eval::DummyMachine;
use crate::rustc_const_eval::interpret::{
    ImmTy, Immediate, InterpCx, MemPlaceMeta, MemoryKind, OpTy, Projectable, Scalar,
    intern_const_alloc_for_constprop,
};
use crate::rustc_data_structures::fx::FxHasher;
use crate::rustc_data_structures::graph::dominators::Dominators;
use crate::rustc_data_structures::hash_table::{Entry, HashTable};
use crate::rustc_hir::def::DefKind;
use crate::rustc_index::bit_set::DenseBitSet;
use crate::rustc_index::{IndexVec, newtype_index};
use crate::bug;
use crate::rustc_middle::mir::interpret::{AllocRange, GlobalAlloc};
use crate::rustc_middle::mir::visit::*;
use crate::rustc_middle::mir::*;
use crate::rustc_middle::ty::layout::HasTypingEnv;
use crate::rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt, Unnormalized};
use crate::rustc_mir_dataflow::{Analysis, ResultsCursor};
use crate::rustc_span::DUMMY_SP;
use smallvec::SmallVec;
use tracing::{debug, instrument, trace};

use crate::rustc_mir_transform::PassPolicy;
use crate::rustc_mir_transform::ssa::{MaybeUninitializedLocals, SsaLocals};

pub(super) struct GVN;

impl<'tcx> crate::rustc_mir_transform::MirPass<'tcx> for GVN {
    fn policy(&self, sess: &crate::rustc_session::Session) -> PassPolicy {
        PassPolicy::optimization(sess.mir_opt_level() >= 2)
    }

    #[instrument(level = "trace", skip(self, tcx, body))]
    fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
        debug!(def_id = ?body.source.def_id());

        let typing_env = body.typing_env(tcx);
        let ssa = SsaLocals::new(tcx, body, typing_env);
        // Clone dominators because we need them while mutating the body.
        let dominators = body.basic_blocks.dominators().clone();

        let arena = DroplessArena::default();
        let mut state =
            VnState::new(tcx, body, typing_env, &ssa, dominators, &body.local_decls, &arena);

        for local in body.args_iter().filter(|&local| ssa.is_ssa(local)) {
            let opaque = state.new_argument(body.local_decls[local].ty);
            state.assign(local, opaque);
        }

        let reverse_postorder = body.basic_blocks.reverse_postorder().to_vec();
        for bb in reverse_postorder {
            let data = &mut body.basic_blocks.as_mut_preserves_cfg()[bb];
            state.visit_basic_block_data(bb, data);
        }

        // When emitting storage statements, we want to retain the reused locals' storage statements,
        // as this enables better optimizations. For each local use location, we mark it for storage removal
        // only if it might be uninitialized at that point.
        let storage_to_remove = if tcx.sess.emit_lifetime_markers() {
            let maybe_uninit = MaybeUninitializedLocals
                .iterate_to_fixpoint(tcx, body, Some("mir_opt::gvn"))
                .into_results_cursor(body);

            let mut storage_checker = StorageChecker {
                reused_locals: &state.reused_locals,
                storage_to_remove: DenseBitSet::new_empty(body.local_decls.len()),
                maybe_uninit,
            };

            for (bb, data) in traversal::reachable(body) {
                storage_checker.visit_basic_block_data(bb, data);
            }

            Some(storage_checker.storage_to_remove)
        } else {
            None
        };

        // If None, remove the storage statements of all the reused locals.
        let storage_to_remove = storage_to_remove.as_ref().unwrap_or(&state.reused_locals);
        debug!(?storage_to_remove);

        StorageRemover { tcx, reused_locals: &state.reused_locals, storage_to_remove }
            .visit_body_preserves_cfg(body);
    }
}

newtype_index! {
    /// This represents a `Value` in the symbolic execution.
    #[debug_format = "_v{}"]
    struct VnIndex {}
}

/// Marker type to forbid hashing and comparing opaque values.
/// This struct should only be constructed by `ValueSet::insert_unique` to ensure we use that
/// method to create non-unifiable values. It will ICE if used in `ValueSet::insert`.
#[derive(Copy, Clone, Debug, Eq)]
struct VnOpaque;
impl PartialEq for VnOpaque {
    fn eq(&self, _: &VnOpaque) -> bool {
        // ICE if we try to compare unique values
        unreachable!()
    }
}
impl Hash for VnOpaque {
    fn hash<T: Hasher>(&self, _: &mut T) {
        // ICE if we try to hash unique values
        unreachable!()
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
enum AddressKind {
    Ref(BorrowKind),
    Address(RawPtrKind),
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
enum AddressBase {
    /// This address is based on this local.
    Local(Local),
    /// This address is based on the deref of this pointer.
    Deref(VnIndex),
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
enum Value<'a, 'tcx> {
    // Root values.
    /// Used to represent values we know nothing about.
    Opaque(VnOpaque),
    /// The value is a argument.
    Argument(VnOpaque),
    /// Evaluated or unevaluated constant value.
    Constant {
        value: Const<'tcx>,
        /// Some constants do not have a deterministic value. To avoid merging two instances of the
        /// same `Const`, we assign them an additional integer index.
        // `disambiguator` is `None` iff the constant is deterministic.
        disambiguator: Option<VnOpaque>,
    },

    // Aggregates.
    /// An aggregate value, either tuple/closure/struct/enum.
    /// This does not contain unions, as we cannot reason with the value.
    Aggregate(VariantIdx, &'a [VnIndex]),
    /// A union aggregate value.
    Union(FieldIdx, VnIndex),
    /// A raw pointer aggregate built from a thin pointer and metadata.
    RawPtr {
        /// Thin pointer component. This is field 0 in MIR.
        pointer: VnIndex,
        /// Metadata component. This is field 1 in MIR.
        metadata: VnIndex,
    },
    /// This corresponds to a `[value; count]` expression.
    Repeat(VnIndex, ty::Const<'tcx>),
    /// The address of a place.
    Address {
        base: AddressBase,
        // We do not use a plain `Place` as we want to be able to reason about indices.
        // This does not contain any `Deref` projection.
        projection: &'a [ProjectionElem<VnIndex, Ty<'tcx>>],
        kind: AddressKind,
        /// Give each borrow and pointer a different provenance, so we don't merge them.
        provenance: VnOpaque,
    },

    // Extractions.
    /// This is the *value* obtained by projecting another value.
    Projection(VnIndex, ProjectionElem<VnIndex, ()>),
    /// Discriminant of the given value.
    Discriminant(VnIndex),

    // Operations.
    RuntimeChecks(RuntimeChecks),
    UnaryOp(UnOp, VnIndex),
    BinaryOp(BinOp, VnIndex, VnIndex),
    Cast {
        kind: CastKind,
        value: VnIndex,
    },
}

/// Stores and deduplicates pairs of `(Value, Ty)` into in `VnIndex` numbered values.
///
/// This data structure is mostly a partial reimplementation of `FxIndexMap<VnIndex, (Value, Ty)>`.
/// We do not use a regular `FxIndexMap` to skip hashing values that are unique by construction,
/// like opaque values, address with provenance and non-deterministic constants.
struct ValueSet<'a, 'tcx> {
    indices: HashTable<VnIndex>,
    hashes: IndexVec<VnIndex, u64>,
    values: IndexVec<VnIndex, Value<'a, 'tcx>>,
    types: IndexVec<VnIndex, Ty<'tcx>>,
}

impl<'a, 'tcx> ValueSet<'a, 'tcx> {
    fn new(num_values: usize) -> ValueSet<'a, 'tcx> {
        ValueSet {
            indices: HashTable::with_capacity(num_values),
            hashes: IndexVec::with_capacity(num_values),
            values: IndexVec::with_capacity(num_values),
            types: IndexVec::with_capacity(num_values),
        }
    }

    /// Insert a `(Value, Ty)` pair without hashing or deduplication.
    /// This always creates a new `VnIndex`.
    #[inline]
    fn insert_unique(
        &mut self,
        ty: Ty<'tcx>,
        value: impl FnOnce(VnOpaque) -> Value<'a, 'tcx>,
    ) -> VnIndex {
        let value = value(VnOpaque);

        debug_assert!(match value {
            Value::Opaque(_) | Value::Argument(_) | Value::Address { .. } => true,
            Value::Constant { disambiguator, .. } => disambiguator.is_some(),
            _ => false,
        });

        let index = self.hashes.push(0);
        let _index = self.types.push(ty);
        debug_assert_eq!(index, _index);
        let _index = self.values.push(value);
        debug_assert_eq!(index, _index);
        index
    }

    /// Insert a `(Value, Ty)` pair to be deduplicated.
    /// Returns `true` as second tuple field if this value did not exist previously.
    fn insert(&mut self, ty: Ty<'tcx>, value: Value<'a, 'tcx>) -> (VnIndex, bool) {
        debug_assert!(match value {
            Value::Opaque(_) | Value::Address { .. } => false,
            Value::Constant { disambiguator, .. } => disambiguator.is_none(),
            _ => true,
        });

        let hash: u64 = {
            let mut h = FxHasher::default();
            value.hash(&mut h);
            ty.hash(&mut h);
            h.finish()
        };

        let eq = |index: &VnIndex| self.values[*index] == value && self.types[*index] == ty;
        let hasher = |index: &VnIndex| self.hashes[*index];
        match self.indices.entry(hash, eq, hasher) {
            Entry::Occupied(entry) => {
                let index = *entry.get();
                (index, false)
            }
            Entry::Vacant(entry) => {
                let index = self.hashes.push(hash);
                entry.insert(index);
                let _index = self.values.push(value);
                debug_assert_eq!(index, _index);
                let _index = self.types.push(ty);
                debug_assert_eq!(index, _index);
                (index, true)
            }
        }
    }

    /// Return the `Value` associated with the given `VnIndex`.
    #[inline]
    fn value(&self, index: VnIndex) -> Value<'a, 'tcx> {
        self.values[index]
    }

    /// Return the type associated with the given `VnIndex`.
    #[inline]
    fn ty(&self, index: VnIndex) -> Ty<'tcx> {
        self.types[index]
    }
}

struct VnState<'body, 'a, 'tcx> {
    tcx: TyCtxt<'tcx>,
    ecx: InterpCx<'tcx, DummyMachine>,
    local_decls: &'body LocalDecls<'tcx>,
    is_coroutine: bool,
    /// Value stored in each local.
    locals: IndexVec<Local, Option<VnIndex>>,
    /// Locals that are assigned that value.
    // This vector does not hold all the values of `VnIndex` that we create.
    rev_locals: IndexVec<VnIndex, SmallVec<[Local; 1]>>,
    values: ValueSet<'a, 'tcx>,
    /// Values evaluated as constants if possible.
    /// - `None` are values not computed yet;
    /// - `Some(None)` are values for which computation has failed;
    /// - `Some(Some(op))` are successful computations.
    evaluated: IndexVec<VnIndex, Option<Option<&'a OpTy<'tcx>>>>,
    ssa: &'body SsaLocals,
    dominators: Dominators<BasicBlock>,
    reused_locals: DenseBitSet<Local>,
    arena: &'a DroplessArena,
}

impl<'body, 'a, 'tcx> VnState<'body, 'a, 'tcx> {
    fn new(
        tcx: TyCtxt<'tcx>,
        body: &Body<'tcx>,
        typing_env: ty::TypingEnv<'tcx>,
        ssa: &'body SsaLocals,
        dominators: Dominators<BasicBlock>,
        local_decls: &'body LocalDecls<'tcx>,
        arena: &'a DroplessArena,
    ) -> Self {
        // Compute a rough estimate of the number of values in the body from the number of
        // statements. This is meant to reduce the number of allocations, but it's all right if
        // we miss the exact amount. We estimate based on 2 values per statement (one in LHS and
        // one in RHS) and 4 values per terminator (for call operands).
        let num_values =
            2 * body.basic_blocks.iter().map(|bbdata| bbdata.statements.len()).sum::<usize>()
                + 4 * body.basic_blocks.len();
        VnState {
            tcx,
            ecx: InterpCx::new(tcx, DUMMY_SP, typing_env, DummyMachine),
            local_decls,
            is_coroutine: body.coroutine.is_some(),
            locals: IndexVec::from_elem(None, local_decls),
            rev_locals: IndexVec::with_capacity(num_values),
            values: ValueSet::new(num_values),
            evaluated: IndexVec::with_capacity(num_values),
            ssa,
            dominators,
            reused_locals: DenseBitSet::new_empty(local_decls.len()),
            arena,
        }
    }

    fn typing_env(&self) -> ty::TypingEnv<'tcx> {
        self.ecx.typing_env()
    }

    fn insert_unique(
        &mut self,
        ty: Ty<'tcx>,
        value: impl FnOnce(VnOpaque) -> Value<'a, 'tcx>,
    ) -> VnIndex {
        let index = self.values.insert_unique(ty, value);
        let _index = self.evaluated.push(None);
        debug_assert_eq!(index, _index);
        let _index = self.rev_locals.push(SmallVec::new());
        debug_assert_eq!(index, _index);
        index
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn insert(&mut self, ty: Ty<'tcx>, value: Value<'a, 'tcx>) -> VnIndex {
        let (index, new) = self.values.insert(ty, value);
        if new {
            // Grow `evaluated` and `rev_locals` here to amortize the allocations.
            let _index = self.evaluated.push(None);
            debug_assert_eq!(index, _index);
            let _index = self.rev_locals.push(SmallVec::new());
            debug_assert_eq!(index, _index);
        }
        index
    }

    /// Create a new `Value` for which we have no information at all, except that it is distinct
    /// from all the others.
    #[instrument(level = "trace", skip(self), ret)]
    fn new_opaque(&mut self, ty: Ty<'tcx>) -> VnIndex {
        let index = self.insert_unique(ty, Value::Opaque);
        self.evaluated[index] = Some(None);
        index
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn new_argument(&mut self, ty: Ty<'tcx>) -> VnIndex {
        let index = self.insert_unique(ty, Value::Argument);
        self.evaluated[index] = Some(None);
        index
    }

    /// Create a new `Value::Address` distinct from all the others.
    #[instrument(level = "trace", skip(self), ret)]
    fn new_pointer(&mut self, place: Place<'tcx>, kind: AddressKind) -> Option<VnIndex> {
        let pty = place.ty(self.local_decls, self.tcx).ty;
        let ty = match kind {
            AddressKind::Ref(bk) => {
                Ty::new_ref(self.tcx, self.tcx.lifetimes.re_erased, pty, bk.to_mutbl_lossy())
            }
            AddressKind::Address(mutbl) => Ty::new_ptr(self.tcx, pty, mutbl.to_mutbl_lossy()),
        };

        let mut projection = place.projection.iter();
        let base = if place.is_indirect_first_projection() {
            let base = self.locals[place.local]?;
            // Skip the initial `Deref`.
            projection.next();
            AddressBase::Deref(base)
        } else if self.ssa.is_ssa(place.local) {
            // Only propagate the pointer of the SSA local.
            AddressBase::Local(place.local)
        } else {
            return None;
        };
        // Do not try evaluating inside `Index`, this has been done by `simplify_place_projection`.
        let projection =
            projection.map(|proj| proj.try_map(|index| self.locals[index], |ty| ty).ok_or(()));
        let projection = self.arena.try_alloc_from_iter(projection).ok()?;

        let index = self.insert_unique(ty, |provenance| Value::Address {
            base,
            projection,
            kind,
            provenance,
        });
        Some(index)
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn insert_constant(&mut self, value: Const<'tcx>) -> VnIndex {
        if is_deterministic(value) {
            // The constant is deterministic, no need to disambiguate.
            let constant = Value::Constant { value, disambiguator: None };
            self.insert(value.ty(), constant)
        } else {
            // Multiple mentions of this constant will yield different values,
            // so assign a different `disambiguator` to ensure they do not get the same `VnIndex`.
            self.insert_unique(value.ty(), |disambiguator| Value::Constant {
                value,
                disambiguator: Some(disambiguator),
            })
        }
    }

    #[inline]
    fn get(&self, index: VnIndex) -> Value<'a, 'tcx> {
        self.values.value(index)
    }

    #[inline]
    fn ty(&self, index: VnIndex) -> Ty<'tcx> {
        self.values.ty(index)
    }

    /// Record that `local` is assigned `value`. `local` must be SSA.
    #[instrument(level = "trace", skip(self))]
    fn assign(&mut self, local: Local, value: VnIndex) {
        debug_assert!(self.ssa.is_ssa(local));
        self.locals[local] = Some(value);
        self.rev_locals[value].push(local);
    }

    fn insert_bool(&mut self, flag: bool) -> VnIndex {
        // Booleans are deterministic.
        let value = Const::from_bool(self.tcx, flag);
        debug_assert!(is_deterministic(value));
        self.insert(self.tcx.types.bool, Value::Constant { value, disambiguator: None })
    }

    fn insert_scalar(&mut self, ty: Ty<'tcx>, scalar: Scalar) -> VnIndex {
        // Scalars are deterministic.
        let value = Const::from_scalar(self.tcx, scalar, ty);
        debug_assert!(is_deterministic(value));
        self.insert(ty, Value::Constant { value, disambiguator: None })
    }

    fn insert_tuple(&mut self, ty: Ty<'tcx>, values: &[VnIndex]) -> VnIndex {
        self.insert(ty, Value::Aggregate(VariantIdx::ZERO, self.arena.alloc_slice(values)))
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn eval_to_const_inner(&mut self, value: VnIndex) -> Option<OpTy<'tcx>> {
        use Value::*;
        let ty = self.ty(value);
        // Avoid computing layouts inside a coroutine, as that can cause cycles.
        let ty = if !self.is_coroutine || ty.is_scalar() {
            self.ecx.layout_of(ty).ok()?
        } else {
            return None;
        };
        let op = match self.get(value) {
            _ if ty.is_zst() => ImmTy::uninit(ty).into(),

            Opaque(_) | Argument(_) => return None,
            // Keep runtime check constants as symbolic.
            RuntimeChecks(..) => return None,

            // In general, evaluating repeat expressions just consumes a lot of memory.
            // But in the special case that the element is just Immediate::Uninit, we can evaluate
            // it without extra memory! If we don't propagate uninit values like this, LLVM can get
            // very confused: https://github.com/rust-lang/rust/issues/139355
            Repeat(value, _count) => {
                let value = self.eval_to_const(value)?;
                if value.is_immediate_uninit() {
                    ImmTy::uninit(ty).into()
                } else {
                    return None;
                }
            }
            Constant { ref value, disambiguator: _ } => {
                self.ecx.eval_mir_constant(value, DUMMY_SP, None).discard_err()?
            }
            Aggregate(variant, ref fields) => {
                let fields =
                    fields.iter().map(|&f| self.eval_to_const(f)).collect::<Option<Vec<_>>>()?;
                let variant = if ty.ty.is_enum() { Some(variant) } else { None };
                let (BackendRepr::Scalar(..) | BackendRepr::ScalarPair { .. }) = ty.backend_repr
                else {
                    return None;
                };
                let dest = self.ecx.allocate(ty, MemoryKind::Stack).discard_err()?;
                let variant_dest = if let Some(variant) = variant {
                    self.ecx.project_downcast(&dest, variant).discard_err()?
                } else {
                    dest.clone()
                };
                for (field_index, op) in fields.into_iter().enumerate() {
                    let field_dest = self
                        .ecx
                        .project_field(&variant_dest, FieldIdx::from_usize(field_index))
                        .discard_err()?;
                    self.ecx.copy_op(op, &field_dest).discard_err()?;
                }
                self.ecx
                    .write_discriminant(variant.unwrap_or(FIRST_VARIANT), &dest)
                    .discard_err()?;
                self.ecx
                    .alloc_mark_immutable(dest.ptr().provenance.unwrap().alloc_id())
                    .discard_err()?;
                dest.into()
            }
            Union(active_field, field) => {
                let field = self.eval_to_const(field)?;
                if field.layout.layout.is_zst() {
                    ImmTy::from_immediate(Immediate::Uninit, ty).into()
                } else if matches!(
                    ty.backend_repr,
                    BackendRepr::Scalar(..) | BackendRepr::ScalarPair { .. }
                ) {
                    let dest = self.ecx.allocate(ty, MemoryKind::Stack).discard_err()?;
                    let field_dest = self.ecx.project_field(&dest, active_field).discard_err()?;
                    self.ecx.copy_op(field, &field_dest).discard_err()?;
                    self.ecx
                        .alloc_mark_immutable(dest.ptr().provenance.unwrap().alloc_id())
                        .discard_err()?;
                    dest.into()
                } else {
                    return None;
                }
            }
            RawPtr { pointer, metadata } => {
                let pointer = self.eval_to_const(pointer)?;
                let metadata = self.eval_to_const(metadata)?;

                // Pointers don't have fields, so don't `project_field` them.
                let data = self.ecx.read_pointer(pointer).discard_err()?;
                let meta = if metadata.layout.is_zst() {
                    MemPlaceMeta::None
                } else {
                    MemPlaceMeta::Meta(self.ecx.read_scalar(metadata).discard_err()?)
                };
                let ptr_imm = Immediate::new_pointer_with_meta(data, meta, &self.ecx);
                ImmTy::from_immediate(ptr_imm, ty).into()
            }

            Projection(base, elem) => {
                let base = self.eval_to_const(base)?;
                // `Index` by constants should have been replaced by `ConstantIndex` by
                // `simplify_place_projection`.
                let elem = elem.try_map(|_| None, |()| ty.ty)?;
                self.ecx.project(base, elem).discard_err()?
            }
            Address { base, projection, .. } => {
                debug_assert!(!projection.contains(&ProjectionElem::Deref));
                let pointer = match base {
                    AddressBase::Deref(pointer) => self.eval_to_const(pointer)?,
                    // We have no stack to point to.
                    AddressBase::Local(_) => return None,
                };
                let mut mplace = self.ecx.deref_pointer(pointer).discard_err()?;
                for elem in projection {
                    // `Index` by constants should have been replaced by `ConstantIndex` by
                    // `simplify_place_projection`.
                    let elem = elem.try_map(|_| None, |ty| ty)?;
                    mplace = self.ecx.project(&mplace, elem).discard_err()?;
                }
                let pointer = mplace.to_ref(&self.ecx);
                ImmTy::from_immediate(pointer, ty).into()
            }

            Discriminant(base) => {
                let base = self.eval_to_const(base)?;
                let variant = self.ecx.read_discriminant(base).discard_err()?;
                let discr_value =
                    self.ecx.discriminant_for_variant(base.layout.ty, variant).discard_err()?;
                discr_value.into()
            }
            UnaryOp(un_op, operand) => {
                let operand = self.eval_to_const(operand)?;
                let operand = self.ecx.read_immediate(operand).discard_err()?;
                let val = self.ecx.unary_op(un_op, &operand).discard_err()?;
                val.into()
            }
            BinaryOp(bin_op, lhs, rhs) => {
                let lhs = self.eval_to_const(lhs)?;
                let rhs = self.eval_to_const(rhs)?;
                let lhs = self.ecx.read_immediate(lhs).discard_err()?;
                let rhs = self.ecx.read_immediate(rhs).discard_err()?;
                let val = self.ecx.binary_op(bin_op, &lhs, &rhs).discard_err()?;
                val.into()
            }
            Cast { kind, value } => match kind {
                CastKind::IntToInt | CastKind::IntToFloat => {
                    let value = self.eval_to_const(value)?;
                    let value = self.ecx.read_immediate(value).discard_err()?;
                    let res = self.ecx.int_to_int_or_float(&value, ty).discard_err()?;
                    res.into()
                }
                CastKind::FloatToFloat | CastKind::FloatToInt => {
                    let value = self.eval_to_const(value)?;
                    let value = self.ecx.read_immediate(value).discard_err()?;
                    let res = self.ecx.float_to_float_or_int(&value, ty).discard_err()?;
                    res.into()
                }
                CastKind::Transmute | CastKind::Subtype => {
                    let value = self.eval_to_const(value)?;
                    // `offset` for immediates generally only supports projections that match the
                    // type of the immediate. However, as a HACK, we exploit that it can also do
                    // limited transmutes: it only works between types with the same layout, and
                    // cannot transmute pointers to integers.
                    if value.as_mplace_or_imm().is_right() {
                        let can_transmute = match (value.layout.backend_repr, ty.backend_repr) {
                            (BackendRepr::Scalar(s1), BackendRepr::Scalar(s2)) => {
                                s1.size(&self.ecx) == s2.size(&self.ecx)
                                    && !matches!(s1.primitive(), Primitive::Pointer(..))
                            }
                            (
                                BackendRepr::ScalarPair { a: a1, b: b1, b_offset: b1_offset },
                                BackendRepr::ScalarPair { a: a2, b: b2, b_offset: b2_offset },
                            ) => {
                                a1.size(&self.ecx) == a2.size(&self.ecx)
                                    && b1.size(&self.ecx) == b2.size(&self.ecx)
                                    // The first component is always at offset zero, but the offset to the second
                                    // component needs to match as well for us to be able to transmute.
                                    && b1_offset == b2_offset
                                    // None of the inputs may be a pointer.
                                    && !matches!(a1.primitive(), Primitive::Pointer(..))
                                    && !matches!(b1.primitive(), Primitive::Pointer(..))
                            }
                            _ => false,
                        };
                        if !can_transmute {
                            return None;
                        }
                    }
                    value.offset(Size::ZERO, ty, &self.ecx).discard_err()?
                }
                CastKind::PointerCoercion(ty::adjustment::PointerCoercion::Unsize, _) => {
                    let src = self.eval_to_const(value)?;
                    let dest = self.ecx.allocate(ty, MemoryKind::Stack).discard_err()?;
                    self.ecx.unsize_into(src, ty, &dest).discard_err()?;
                    self.ecx
                        .alloc_mark_immutable(dest.ptr().provenance.unwrap().alloc_id())
                        .discard_err()?;
                    dest.into()
                }
                CastKind::FnPtrToPtr | CastKind::PtrToPtr => {
                    let src = self.eval_to_const(value)?;
                    let src = self.ecx.read_immediate(src).discard_err()?;
                    let ret = self.ecx.ptr_to_ptr(&src, ty).discard_err()?;
                    ret.into()
                }
                CastKind::PointerCoercion(ty::adjustment::PointerCoercion::UnsafeFnPointer, _) => {
                    let src = self.eval_to_const(value)?;
                    let src = self.ecx.read_immediate(src).discard_err()?;
                    ImmTy::from_immediate(*src, ty).into()
                }
                _ => return None,
            },
        };
        Some(op)
    }

    fn eval_to_const(&mut self, index: VnIndex) -> Option<&'a OpTy<'tcx>> {
        if let Some(op) = self.evaluated[index] {
            return op;
        }
        let op = self.eval_to_const_inner(index);
        self.evaluated[index] = Some(self.arena.alloc(op).as_ref());
        self.evaluated[index].unwrap()
    }

    /// Represent the *value* we obtain by dereferencing an `Address` value.
    #[instrument(level = "trace", skip(self), ret)]
    fn dereference_address(
        &mut self,
        base: AddressBase,
        projection: &[ProjectionElem<VnIndex, Ty<'tcx>>],
    ) -> Option<VnIndex> {
        let (mut place_ty, mut value) = match base {
            // The base is a local, so we take the local's value and project from it.
            AddressBase::Local(local) => {
                let local = self.locals[local]?;
                let place_ty = PlaceTy::from_ty(self.ty(local));
                (place_ty, local)
            }
            // The base is a pointer's deref, so we introduce the implicit deref.
            AddressBase::Deref(reborrow) => {
                let place_ty = PlaceTy::from_ty(self.ty(reborrow));
                self.project(place_ty, reborrow, ProjectionElem::Deref)?
            }
        };
        for &proj in projection {
            (place_ty, value) = self.project(place_ty, value, proj)?;
        }
        Some(value)
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn project(
        &mut self,
        place_ty: PlaceTy<'tcx>,
        value: VnIndex,
        proj: ProjectionElem<VnIndex, Ty<'tcx>>,
    ) -> Option<(PlaceTy<'tcx>, VnIndex)> {
        let projection_ty = place_ty.projection_ty(self.tcx, proj);
        let proj = match proj {
            ProjectionElem::Deref => {
                if let Some(Mutability::Not) = place_ty.ty.ref_mutability()
                    && projection_ty.ty.is_freeze(self.tcx, self.typing_env())
                {
                    if let Value::Address { base, projection, .. } = self.get(value)
                        && let Some(value) = self.dereference_address(base, projection)
                    {
                        return Some((projection_ty, value));
                    }
                    // We cannot unify two references produced by dereferencing the same nested reference,
                    // because they may have different lifetimes.
                    // ```
                    // let b: &T = *a;
                    // ... `a` is allowed to be modified. `c` and `b` have different borrowing lifetime.
                    // Unifying them will extend the lifetime of `b`.
                    // let c: &T = *a;
                    // ```
                    // Furthermore, unifying them can also violate Stacked Borrows or Tree Borrows.
                    // We can only unify all `*b` and `*c` separately
                    // because nested shared references are not read-only.
                    // For more, see <https://github.com/rust-lang/rust/issues/155884> and
                    // <https://github.com/rust-lang/rust/issues/130853>.
                    if self.ty_may_have_ref(projection_ty.ty) {
                        return None;
                    }

                    // An immutable borrow `_x` always points to the same value for the
                    // lifetime of the borrow, so we can merge all instances of `*_x`.
                    let deref = self
                        .insert(projection_ty.ty, Value::Projection(value, ProjectionElem::Deref));
                    return Some((projection_ty, deref));
                } else {
                    return None;
                }
            }
            ProjectionElem::PhantomDeref => bug!("PhantomDeref in GVN"),
            ProjectionElem::Downcast(name, index) => ProjectionElem::Downcast(name, index),
            ProjectionElem::Field(f, _) => match self.get(value) {
                Value::Aggregate(_, fields) => return Some((projection_ty, fields[f.as_usize()])),
                Value::Union(active, field) if active == f => return Some((projection_ty, field)),
                Value::Projection(outer_value, ProjectionElem::Downcast(_, read_variant))
                    if let Value::Aggregate(written_variant, fields) = self.get(outer_value)
                    // This pass is not aware of control-flow, so we do not know whether the
                    // replacement we are doing is actually reachable. We could be in any arm of
                    // ```
                    // match Some(x) {
                    //     Some(y) => /* stuff */,
                    //     None => /* other */,
                    // }
                    // ```
                    //
                    // In surface rust, the current statement would be unreachable.
                    //
                    // However, from the reference chapter on enums and RFC 2195,
                    // accessing the wrong variant is not UB if the enum has repr.
                    // So it's not impossible for a series of MIR opts to generate
                    // a downcast to an inactive variant.
                    && written_variant == read_variant =>
                {
                    return Some((projection_ty, fields[f.as_usize()]));
                }
                _ => ProjectionElem::Field(f, ()),
            },
            ProjectionElem::Index(idx) => {
                if let Value::Repeat(inner, _) = self.get(value) {
                    return Some((projection_ty, inner));
                }
                ProjectionElem::Index(idx)
            }
            ProjectionElem::ConstantIndex { offset, min_length, from_end } => {
                match self.get(value) {
                    Value::Repeat(inner, _) => {
                        return Some((projection_ty, inner));
                    }
                    Value::Aggregate(_, operands) => {
                        let offset = if from_end {
                            operands.len() - offset as usize
                        } else {
                            offset as usize
                        };
                        let value = operands.get(offset).copied()?;
                        return Some((projection_ty, value));
                    }
                    _ => {}
                };
                ProjectionElem::ConstantIndex { offset, min_length, from_end }
            }
            ProjectionElem::Subslice { from, to, from_end } => {
                ProjectionElem::Subslice { from, to, from_end }
            }
            ProjectionElem::OpaqueCast(_) => ProjectionElem::OpaqueCast(()),
            ProjectionElem::UnwrapUnsafeBinder(_) => ProjectionElem::UnwrapUnsafeBinder(()),
        };

        let value = self.insert(projection_ty.ty, Value::Projection(value, proj));
        Some((projection_ty, value))
    }

    /// Simplify the projection chain if we know better.
    #[instrument(level = "trace", skip(self))]
    fn simplify_place_projection(&mut self, place: &mut Place<'tcx>, location: Location) {
        // If the projection is indirect, we treat the local as a value, so can replace it with
        // another local.
        if place.is_indirect_first_projection()
            && let Some(base) = self.locals[place.local]
            && let Some(new_local) = self.try_as_local(base, location)
            && place.local != new_local
        {
            place.local = new_local;
            self.reused_locals.insert(new_local);
        }

        let mut projection = Cow::Borrowed(&place.projection[..]);

        for i in 0..projection.len() {
            let elem = projection[i];
            if let ProjectionElem::Index(idx_local) = elem
                && let Some(idx) = self.locals[idx_local]
            {
                if let Some(offset) = self.eval_to_const(idx)
                    && let Some(offset) = self.ecx.read_target_usize(offset).discard_err()
                    && let Some(min_length) = offset.checked_add(1)
                {
                    projection.to_mut()[i] =
                        ProjectionElem::ConstantIndex { offset, min_length, from_end: false };
                } else if let Some(new_idx_local) = self.try_as_local(idx, location)
                    && idx_local != new_idx_local
                {
                    projection.to_mut()[i] = ProjectionElem::Index(new_idx_local);
                    self.reused_locals.insert(new_idx_local);
                }
            }
        }

        // A match rather than `Cow::is_owned`, which is the unstable `cow_is_borrowed`.
        if matches!(projection, Cow::Owned(_)) {
            place.projection = self.tcx.mk_place_elems(&projection);
        }

        trace!(?place);
    }

    /// Represent the *value* which would be read from `place`. If we succeed, return it.
    /// If we fail, return a `PlaceRef` that contains the same value.
    #[instrument(level = "trace", skip(self), ret)]
    fn compute_place_value(
        &mut self,
        place: Place<'tcx>,
        location: Location,
    ) -> Result<VnIndex, PlaceRef<'tcx>> {
        // Invariant: `place` and `place_ref` point to the same value, even if they point to
        // different memory locations.
        let mut place_ref = place.as_ref();

        // Invariant: `value` holds the value up-to the `index`th projection excluded.
        let Some(mut value) = self.locals[place.local] else { return Err(place_ref) };
        // Invariant: `value` has type `place_ty`, with optional downcast variant if needed.
        let mut place_ty = PlaceTy::from_ty(self.local_decls[place.local].ty);
        for (index, proj) in place.projection.iter().enumerate() {
            if let Some(local) = self.try_as_local(value, location) {
                // Both `local` and `Place { local: place.local, projection: projection[..index] }`
                // hold the same value. Therefore, following place holds the value in the original
                // `place`.
                place_ref = PlaceRef { local, projection: &place.projection[index..] };
            }

            let Some(proj) = proj.try_map(|value| self.locals[value], |ty| ty) else {
                return Err(place_ref);
            };
            let Some(ty_and_value) = self.project(place_ty, value, proj) else {
                return Err(place_ref);
            };
            (place_ty, value) = ty_and_value;
        }

        Ok(value)
    }

    /// Represent the *value* which would be read from `place`, and point `place` to a preexisting
    /// place with the same value (if that already exists).
    #[instrument(level = "trace", skip(self), ret)]
    fn simplify_place_value(
        &mut self,
        place: &mut Place<'tcx>,
        location: Location,
    ) -> Option<VnIndex> {
        self.simplify_place_projection(place, location);

        match self.compute_place_value(*place, location) {
            Ok(value) => {
                if let Some(new_place) = self.try_as_place(value, location, true)
                    && (new_place.local != place.local
                        || new_place.projection.len() < place.projection.len())
                {
                    *place = new_place;
                    self.reused_locals.insert(new_place.local);
                }
                Some(value)
            }
            Err(place_ref) => {
                if place_ref.local != place.local
                    || place_ref.projection.len() < place.projection.len()
                {
                    // By the invariant on `place_ref`.
                    *place = place_ref.project_deeper(&[], self.tcx);
                    self.reused_locals.insert(place_ref.local);
                }
                None
            }
        }
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn simplify_operand(
        &mut self,
        operand: &mut Operand<'tcx>,
        location: Location,
    ) -> Option<VnIndex> {
        let value = match *operand {
            Operand::RuntimeChecks(c) => self.insert(self.tcx.types.bool, Value::RuntimeChecks(c)),
            Operand::Constant(ref constant) => self.insert_constant(constant.const_),
            Operand::Copy(ref mut place) | Operand::Move(ref mut place) => {
                self.simplify_place_value(place, location)?
            }
        };
        if let Some(const_) = self.try_as_constant(value) {
            *operand = Operand::Constant(Box::new(const_));
        } else if let Value::RuntimeChecks(c) = self.get(value) {
            *operand = Operand::RuntimeChecks(c);
        }
        Some(value)
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn simplify_rvalue(
        &mut self,
        lhs: &Place<'tcx>,
        rvalue: &mut Rvalue<'tcx>,
        location: Location,
    ) -> Option<VnIndex> {
        let value = match *rvalue {
            // Forward values.
            Rvalue::Use(ref mut operand, _) => return self.simplify_operand(operand, location),

            // Roots.
            Rvalue::Repeat(ref mut op, amount) => {
                let op = self.simplify_operand(op, location)?;
                Value::Repeat(op, amount)
            }
            Rvalue::Aggregate(..) => return self.simplify_aggregate(rvalue, location),
            Rvalue::Ref(_, borrow_kind, ref mut place) => {
                self.simplify_place_projection(place, location);
                return self.new_pointer(*place, AddressKind::Ref(borrow_kind));
            }
            Rvalue::Reborrow(_, mutbl, place) => {
                if mutbl == Mutability::Mut {
                    // Note: this is adapted from simplify_aggregate.
                    let mut operand = Operand::Copy(place);
                    let val = self.simplify_operand(&mut operand, location);
                    // FIXME(reborrow): Is it correct to make these retagging assignments?
                    *rvalue = Rvalue::Use(Operand::Copy(place), WithRetag::Yes);
                    return val;
                } else {
                    // FIXME(reborrow): CoerceShared should perform effectively a copy followed by a
                    // transmute, or possibly something more complicated in the future. For now we
                    // leave this unoptimised.
                    return None;
                }
            }
            Rvalue::RawPtr(mutbl, ref mut place) => {
                self.simplify_place_projection(place, location);
                return self.new_pointer(*place, AddressKind::Address(mutbl));
            }
            Rvalue::WrapUnsafeBinder(ref mut op, _) => {
                let value = self.simplify_operand(op, location)?;
                Value::Cast { kind: CastKind::Transmute, value }
            }

            // Operations.
            Rvalue::Cast(ref mut kind, ref mut value, to) => {
                return self.simplify_cast(kind, value, to, location);
            }
            Rvalue::BinaryOp(op, ref mut operands) => {
                let (lhs, rhs) = &mut **operands;
                return self.simplify_binary(op, lhs, rhs, location);
            }
            Rvalue::UnaryOp(op, ref mut arg_op) => {
                return self.simplify_unary(op, arg_op, location);
            }
            Rvalue::Discriminant(ref mut place) => {
                let place = self.simplify_place_value(place, location)?;
                if let Some(discr) = self.simplify_discriminant(place) {
                    return Some(discr);
                }
                Value::Discriminant(place)
            }

            // Unsupported values.
            Rvalue::ThreadLocalRef(..) => return None,
            Rvalue::CopyForDeref(_) => {
                bug!("forbidden in runtime MIR: {rvalue:?}")
            }
        };
        let ty = rvalue.ty(self.local_decls, self.tcx);
        Some(self.insert(ty, value))
    }

    fn simplify_discriminant(&mut self, place: VnIndex) -> Option<VnIndex> {
        let enum_ty = self.ty(place);
        if enum_ty.is_enum()
            && let Value::Aggregate(variant, _) = self.get(place)
        {
            let discr = self.ecx.discriminant_for_variant(enum_ty, variant).discard_err()?;
            return Some(self.insert_scalar(discr.layout.ty, discr.to_scalar()));
        }

        None
    }

    fn try_as_place_elem(
        &mut self,
        ty: Ty<'tcx>,
        proj: ProjectionElem<VnIndex, ()>,
        loc: Location,
    ) -> Option<PlaceElem<'tcx>> {
        proj.try_map(
            |value| {
                let local = self.try_as_local(value, loc)?;
                self.reused_locals.insert(local);
                Some(local)
            },
            |()| ty,
        )
    }

    fn simplify_aggregate_to_copy(
        &mut self,
        ty: Ty<'tcx>,
        variant_index: VariantIdx,
        fields: &[VnIndex],
    ) -> Option<VnIndex> {
        let Some(&first_field) = fields.first() else { return None };
        let Value::Projection(copy_from_value, _) = self.get(first_field) else { return None };

        // All fields must correspond one-to-one and come from the same aggregate value.
        if fields.iter().enumerate().any(|(index, &v)| {
            if let Value::Projection(pointer, ProjectionElem::Field(from_index, _)) = self.get(v)
                && copy_from_value == pointer
                && from_index.index() == index
            {
                return false;
            }
            true
        }) {
            return None;
        }

        let mut copy_from_local_value = copy_from_value;
        if let Value::Projection(pointer, proj) = self.get(copy_from_value)
            && let ProjectionElem::Downcast(_, read_variant) = proj
        {
            if variant_index == read_variant {
                // When copying a variant, there is no need to downcast.
                copy_from_local_value = pointer;
            } else {
                // The copied variant must be identical.
                return None;
            }
        }

        // Both must be variants of the same type.
        if self.ty(copy_from_local_value) == ty { Some(copy_from_local_value) } else { None }
    }

    fn simplify_aggregate(
        &mut self,
        rvalue: &mut Rvalue<'tcx>,
        location: Location,
    ) -> Option<VnIndex> {
        let tcx = self.tcx;
        let ty = rvalue.ty(self.local_decls, tcx);

        let Rvalue::Aggregate(ref kind, ref mut field_ops) = *rvalue else { bug!() };

        if field_ops.is_empty() {
            let is_zst = match **kind {
                AggregateKind::Array(..)
                | AggregateKind::Tuple
                | AggregateKind::Closure(..)
                | AggregateKind::CoroutineClosure(..) => true,
                // Only enums can be non-ZST.
                AggregateKind::Adt(did, ..) => tcx.def_kind(did) != DefKind::Enum,
                // Coroutines are never ZST, as they at least contain the implicit states.
                AggregateKind::Coroutine(..) => false,
                AggregateKind::RawPtr(..) => bug!("MIR for RawPtr aggregate must have 2 fields"),
            };

            if is_zst {
                return Some(self.insert_constant(Const::zero_sized(ty)));
            }
        }

        let fields = self.arena.alloc_from_iter(field_ops.iter_mut().map(|op| {
            self.simplify_operand(op, location)
                .unwrap_or_else(|| self.new_opaque(op.ty(self.local_decls, self.tcx)))
        }));

        let variant_index = match **kind {
            AggregateKind::Array(..) | AggregateKind::Tuple => {
                assert!(!field_ops.is_empty());
                FIRST_VARIANT
            }
            AggregateKind::Closure(..)
            | AggregateKind::CoroutineClosure(..)
            | AggregateKind::Coroutine(..) => FIRST_VARIANT,
            AggregateKind::Adt(_, variant_index, _, _, None) => variant_index,
            // Do not track unions.
            AggregateKind::Adt(_, _, _, _, Some(active_field)) => {
                let field = *fields.first()?;
                return Some(self.insert(ty, Value::Union(active_field, field)));
            }
            AggregateKind::RawPtr(..) => {
                assert_eq!(field_ops.len(), 2);
                let [mut pointer, metadata] = fields.try_into().unwrap();

                // Any thin pointer of matching mutability is fine as the data pointer.
                let mut was_updated = false;
                while let Value::Cast { kind: CastKind::PtrToPtr, value: cast_value } =
                    self.get(pointer)
                    && let ty::RawPtr(from_pointee_ty, from_mtbl) = self.ty(cast_value).kind()
                    && let ty::RawPtr(_, output_mtbl) = ty.kind()
                    && from_mtbl == output_mtbl
                    && from_pointee_ty.is_sized(self.tcx, self.typing_env())
                {
                    pointer = cast_value;
                    was_updated = true;
                }

                if was_updated && let Some(op) = self.try_as_operand(pointer, location) {
                    field_ops[FieldIdx::ZERO] = op;
                }

                return Some(self.insert(ty, Value::RawPtr { pointer, metadata }));
            }
        };

        if ty.is_array()
            && fields.len() > 4
            && let Ok(&first) = fields.iter().all_equal_value()
        {
            let len = ty::Const::from_target_usize(self.tcx, fields.len().try_into().unwrap());
            if let Some(op) = self.try_as_operand(first, location) {
                *rvalue = Rvalue::Repeat(op, len);
            }
            return Some(self.insert(ty, Value::Repeat(first, len)));
        }

        if let Some(value) = self.simplify_aggregate_to_copy(ty, variant_index, &fields) {
            if let Some(place) = self.try_as_place(value, location, true) {
                self.reused_locals.insert(place.local);
                // FIXME: Is it correct to make these retagging assignments?
                *rvalue = Rvalue::Use(Operand::Copy(place), WithRetag::Yes);
            }
            return Some(value);
        }

        Some(self.insert(ty, Value::Aggregate(variant_index, fields)))
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn simplify_unary(
        &mut self,
        op: UnOp,
        arg_op: &mut Operand<'tcx>,
        location: Location,
    ) -> Option<VnIndex> {
        let mut arg_index = self.simplify_operand(arg_op, location)?;
        let arg_ty = self.ty(arg_index);
        let ret_ty = op.ty(self.tcx, arg_ty);

        // PtrMetadata doesn't care about *const vs *mut vs & vs &mut,
        // so start by removing those distinctions so we can update the `Operand`
        if op == UnOp::PtrMetadata {
            let mut was_updated = false;
            loop {
                arg_index = match self.get(arg_index) {
                    // Pointer casts that preserve metadata, such as
                    // `*const [i32]` <-> `*mut [i32]` <-> `*mut [f32]`.
                    // It's critical that this not eliminate cases like
                    // `*const [T]` -> `*const T` which remove metadata.
                    // We run on potentially-generic MIR, though, so unlike codegen
                    // we can't always know exactly what the metadata are.
                    // To allow things like `*mut (?A, ?T)` <-> `*mut (?B, ?T)`,
                    // it's fine to get a projection as the type.
                    Value::Cast { kind: CastKind::PtrToPtr, value: inner }
                        if self.pointers_have_same_metadata(self.ty(inner), arg_ty) =>
                    {
                        inner
                    }

                    // We have an unsizing cast, which assigns the length to wide pointer metadata.
                    Value::Cast {
                        kind: CastKind::PointerCoercion(ty::adjustment::PointerCoercion::Unsize, _),
                        value: from,
                    } if let Some(from) = self.ty(from).builtin_deref(true)
                        && let ty::Array(_, len) = from.kind()
                        && let Some(to) = self.ty(arg_index).builtin_deref(true)
                        && let ty::Slice(..) = to.kind() =>
                    {
                        return Some(self.insert_constant(Const::Ty(self.tcx.types.usize, *len)));
                    }

                    // `&mut *p`, `&raw *p`, etc don't change metadata.
                    Value::Address { base: AddressBase::Deref(reborrowed), projection, .. }
                        if projection.is_empty() =>
                    {
                        reborrowed
                    }

                    _ => break,
                };
                was_updated = true;
            }

            if was_updated && let Some(op) = self.try_as_operand(arg_index, location) {
                *arg_op = op;
            }
        }

        let value = match (op, self.get(arg_index)) {
            (UnOp::Not, Value::UnaryOp(UnOp::Not, inner)) => return Some(inner),
            (UnOp::Neg, Value::UnaryOp(UnOp::Neg, inner)) => return Some(inner),
            (UnOp::Not, Value::BinaryOp(BinOp::Eq, lhs, rhs)) => {
                Value::BinaryOp(BinOp::Ne, lhs, rhs)
            }
            (UnOp::Not, Value::BinaryOp(BinOp::Ne, lhs, rhs)) => {
                Value::BinaryOp(BinOp::Eq, lhs, rhs)
            }
            (UnOp::PtrMetadata, Value::RawPtr { metadata, .. }) => return Some(metadata),
            // We have an unsizing cast, which assigns the length to wide pointer metadata.
            (
                UnOp::PtrMetadata,
                Value::Cast {
                    kind: CastKind::PointerCoercion(ty::adjustment::PointerCoercion::Unsize, _),
                    value: inner,
                },
            ) if let ty::Slice(..) = arg_ty.builtin_deref(true).unwrap().kind()
                && let ty::Array(_, len) = self.ty(inner).builtin_deref(true).unwrap().kind() =>
            {
                return Some(self.insert_constant(Const::Ty(self.tcx.types.usize, *len)));
            }
            _ => Value::UnaryOp(op, arg_index),
        };
        Some(self.insert(ret_ty, value))
    }

    #[instrument(level = "trace", skip(self), ret)]
    fn simplify_binary(
        &mut self,
        op: BinOp,
        lhs_operand: &mut Operand<'tcx>,
        rhs_operand: &mut Operand<'tcx>,
        location: Location,
    ) -> Option<VnIndex> {
        let lhs = self.simplify_operand(lhs_operand, location);
        let rhs = self.simplify_operand(rhs_operand, location);

        // Only short-circuit options after we called `simplify_operand`
        // on both operands for side effect.
        let mut lhs = lhs?;
        let mut rhs = rhs?;

        let lhs_ty = self.ty(lhs);

        // If we're comparing pointers, remove `PtrToPtr` casts if the from
        // types of both casts and the metadata all match.
        if let BinOp::Eq | BinOp::Ne | BinOp::Lt | BinOp::Le | BinOp::Gt | BinOp::Ge = op
            && lhs_ty.is_any_ptr()
            && let Value::Cast { kind: CastKind::PtrToPtr, value: lhs_value } = self.get(lhs)
            && let Value::Cast { kind: CastKind::PtrToPtr, value: rhs_value } = self.get(rhs)
            && let lhs_from = self.ty(lhs_value)
            && lhs_from == self.ty(rhs_value)
            && self.pointers_have_same_metadata(lhs_from, lhs_ty)
        {
            lhs = lhs_value;
            rhs = rhs_value;
            if let Some(lhs_op) = self.try_as_operand(lhs, location)
                && let Some(rhs_op) = self.try_as_operand(rhs, location)
            {
                *lhs_operand = lhs_op;
                *rhs_operand = rhs_op;
            }
        }

        if let Some(value) = self.simplify_binary_inner(op, lhs_ty, lhs, rhs) {
            return Some(value);
        }
        let ty = op.ty(self.tcx, lhs_ty, self.ty(rhs));
        let value = Value::BinaryOp(op, lhs, rhs);
        Some(self.insert(ty, value))
    }

    fn simplify_binary_inner(
        &mut self,
        op: BinOp,
        lhs_ty: Ty<'tcx>,
        lhs: VnIndex,
        rhs: VnIndex,
    ) -> Option<VnIndex> {
        // Floats are weird enough that none of the logic below applies.
        let reasonable_ty =
            lhs_ty.is_integral() || lhs_ty.is_bool() || lhs_ty.is_char() || lhs_ty.is_any_ptr();
        if !reasonable_ty {
            return None;
        }

        let layout = self.ecx.layout_of(lhs_ty).ok()?;

        let mut as_bits = |value: VnIndex| {
            let constant = self.eval_to_const(value)?;
            if layout.backend_repr.is_scalar() {
                let scalar = self.ecx.read_scalar(constant).discard_err()?;
                scalar.to_bits(constant.layout.size).discard_err()
            } else {
                // `constant` is a wide pointer. Do not evaluate to bits.
                None
            }
        };

        // Represent the values as `Left(bits)` or `Right(VnIndex)`.
        use Either::{Left, Right};
        let a = as_bits(lhs).map_or(Right(lhs), Left);
        let b = as_bits(rhs).map_or(Right(rhs), Left);

        let result = match (op, a, b) {
            // Neutral elements.
            (
                BinOp::Add
                | BinOp::AddWithOverflow
                | BinOp::AddUnchecked
                | BinOp::BitOr
                | BinOp::BitXor,
                Left(0),
                Right(p),
            )
            | (
                BinOp::Add
                | BinOp::AddWithOverflow
                | BinOp::AddUnchecked
                | BinOp::BitOr
                | BinOp::BitXor
                | BinOp::Sub
                | BinOp::SubWithOverflow
                | BinOp::SubUnchecked
                | BinOp::Offset
                | BinOp::Shl
                | BinOp::Shr,
                Right(p),
                Left(0),
            )
            | (BinOp::Mul | BinOp::MulWithOverflow | BinOp::MulUnchecked, Left(1), Right(p))
            | (
                BinOp::Mul | BinOp::MulWithOverflow | BinOp::MulUnchecked | BinOp::Div,
                Right(p),
                Left(1),
            ) => p,
            // Attempt to simplify `x & ALL_ONES` to `x`, with `ALL_ONES` depending on type size.
            (BinOp::BitAnd, Right(p), Left(ones)) | (BinOp::BitAnd, Left(ones), Right(p))
                if ones == layout.size.truncate(u128::MAX)
                    || (layout.ty.is_bool() && ones == 1) =>
            {
                p
            }
            // Absorbing elements.
            (
                BinOp::Mul | BinOp::MulWithOverflow | BinOp::MulUnchecked | BinOp::BitAnd,
                _,
                Left(0),
            )
            | (BinOp::Rem, _, Left(1))
            | (
                BinOp::Mul
                | BinOp::MulWithOverflow
                | BinOp::MulUnchecked
                | BinOp::Div
                | BinOp::Rem
                | BinOp::BitAnd
                | BinOp::Shl
                | BinOp::Shr,
                Left(0),
                _,
            ) => self.insert_scalar(lhs_ty, Scalar::from_uint(0u128, layout.size)),
            // Attempt to simplify `x | ALL_ONES` to `ALL_ONES`.
            (BinOp::BitOr, _, Left(ones)) | (BinOp::BitOr, Left(ones), _)
                if ones == layout.size.truncate(u128::MAX)
                    || (layout.ty.is_bool() && ones == 1) =>
            {
                self.insert_scalar(lhs_ty, Scalar::from_uint(ones, layout.size))
            }
            // Sub/Xor with itself.
            (BinOp::Sub | BinOp::SubWithOverflow | BinOp::SubUnchecked | BinOp::BitXor, a, b)
                if a == b =>
            {
                self.insert_scalar(lhs_ty, Scalar::from_uint(0u128, layout.size))
            }
            // Comparison:
            // - if both operands can be computed as bits, just compare the bits;
            // - if we proved that both operands have the same value, we can insert true/false;
            // - otherwise, do nothing, as we do not try to prove inequality.
            (BinOp::Eq, Left(a), Left(b)) => self.insert_bool(a == b),
            (BinOp::Eq, a, b) if a == b => self.insert_bool(true),
            (BinOp::Ne, Left(a), Left(b)) => self.insert_bool(a != b),
            (BinOp::Ne, a, b) if a == b => self.insert_bool(false),
            _ => return None,
        };

        if op.is_overflowing() {
            let ty = Ty::new_tup(self.tcx, &[self.ty(result), self.tcx.types.bool]);
            let false_val = self.insert_bool(false);
            Some(self.insert_tuple(ty, &[result, false_val]))
        } else {
            Some(result)
        }
    }

    fn simplify_cast(
        &mut self,
        initial_kind: &mut CastKind,
        initial_operand: &mut Operand<'tcx>,
        to: Ty<'tcx>,
        location: Location,
    ) -> Option<VnIndex> {
        use CastKind::*;
        use crate::rustc_middle::ty::adjustment::PointerCoercion::*;

        let mut kind = *initial_kind;
        let mut value = self.simplify_operand(initial_operand, location)?;
        let mut from = self.ty(value);
        if from == to {
            return Some(value);
        }

        if let CastKind::PointerCoercion(ReifyFnPointer(_) | ClosureFnPointer(_), _) = kind {
            // Each reification of a generic fn may get a different pointer.
            // Do not try to merge them.
            return Some(self.new_opaque(to));
        }

        let mut was_ever_updated = false;
        loop {
            let mut was_updated_this_iteration = false;

            // Transmuting between raw pointers is just a pointer cast so long as
            // they have the same metadata type (like `*const i32` <=> `*mut u64`
            // or `*mut [i32]` <=> `*const [u64]`), including the common special
            // case of `*const T` <=> `*mut T`.
            if let Transmute = kind
                && from.is_raw_ptr()
                && to.is_raw_ptr()
                && self.pointers_have_same_metadata(from, to)
            {
                kind = PtrToPtr;
                was_updated_this_iteration = true;
            }

            // If a cast just casts away the metadata again, then we can get it by
            // casting the original thin pointer passed to `from_raw_parts`
            if let PtrToPtr = kind
                && let Value::RawPtr { pointer, .. } = self.get(value)
                && let ty::RawPtr(to_pointee, _) = to.kind()
                && to_pointee.is_sized(self.tcx, self.typing_env())
            {
                from = self.ty(pointer);
                value = pointer;
                was_updated_this_iteration = true;
                if from == to {
                    return Some(pointer);
                }
            }

            // Aggregate-then-Transmute can just transmute the original field value,
            // so long as the bytes of a value from only from a single field.
            if let Transmute = kind
                && let Value::Aggregate(variant_idx, field_values) = self.get(value)
                && let Some((field_idx, field_ty)) =
                    self.value_is_all_in_one_field(from, variant_idx)
            {
                from = field_ty;
                value = field_values[field_idx.as_usize()];
                was_updated_this_iteration = true;
                if field_ty == to {
                    return Some(value);
                }
            }

            // Various cast-then-cast cases can be simplified.
            if let Value::Cast { kind: inner_kind, value: inner_value } = self.get(value) {
                let inner_from = self.ty(inner_value);
                let new_kind = match (inner_kind, kind) {
                    // Even if there's a narrowing cast in here that's fine, because
                    // things like `*mut [i32] -> *mut i32 -> *const i32` and
                    // `*mut [i32] -> *const [i32] -> *const i32` can skip the middle in MIR.
                    (PtrToPtr, PtrToPtr) => Some(PtrToPtr),
                    // PtrToPtr-then-Transmute is fine so long as the pointer cast is identity:
                    // `*const T -> *mut T -> NonNull<T>` is fine, but we need to check for narrowing
                    // to skip things like `*const [i32] -> *const i32 -> NonNull<T>`.
                    (PtrToPtr, Transmute) if self.pointers_have_same_metadata(inner_from, from) => {
                        Some(Transmute)
                    }
                    // Similarly, for Transmute-then-PtrToPtr. Note that we need to check different
                    // variables for their metadata, and thus this can't merge with the previous arm.
                    (Transmute, PtrToPtr) if self.pointers_have_same_metadata(from, to) => {
                        Some(Transmute)
                    }
                    // It would be legal to always do this, but we don't want to hide information
                    // from the backend that it'd otherwise be able to use for optimizations.
                    (Transmute, Transmute)
                        if !self.transmute_may_have_niche_of_interest_to_backend(
                            inner_from, from, to,
                        ) =>
                    {
                        Some(Transmute)
                    }
                    _ => None,
                };
                if let Some(new_kind) = new_kind {
                    kind = new_kind;
                    from = inner_from;
                    value = inner_value;
                    was_updated_this_iteration = true;
                    if inner_from == to {
                        return Some(inner_value);
                    }
                }
            }

            if was_updated_this_iteration {
                was_ever_updated = true;
            } else {
                break;
            }
        }

        if was_ever_updated && let Some(op) = self.try_as_operand(value, location) {
            *initial_operand = op;
            *initial_kind = kind;
        }

        Some(self.insert(to, Value::Cast { kind, value }))
    }

    fn pointers_have_same_metadata(&self, left_ptr_ty: Ty<'tcx>, right_ptr_ty: Ty<'tcx>) -> bool {
        let left_meta_ty = left_ptr_ty.pointee_metadata_ty_or_projection(self.tcx);
        let right_meta_ty = right_ptr_ty.pointee_metadata_ty_or_projection(self.tcx);
        if left_meta_ty == right_meta_ty {
            true
        } else if let Ok(left) = self
            .tcx
            .try_normalize_erasing_regions(self.typing_env(), Unnormalized::new_wip(left_meta_ty))
            && let Ok(right) = self.tcx.try_normalize_erasing_regions(
                self.typing_env(),
                Unnormalized::new_wip(right_meta_ty),
            )
        {
            left == right
        } else {
            false
        }
    }

    fn ty_may_have_ref(&self, ty: Ty<'tcx>) -> bool {
        fn ty_may_have_ref_inner<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, depth: usize) -> bool {
            if !tcx.recursion_limit().value_within_limit(depth) {
                return true;
            }
            let depth = depth + 1;
            match ty.kind() {
                ty::Int(_)
                | ty::Uint(_)
                | ty::Float(_)
                | ty::Bool
                | ty::Char
                | ty::Str
                | ty::Never
                | ty::FnDef(..)
                | ty::Error(_)
                | ty::FnPtr(..) => false,
                ty::Tuple(fields) => {
                    fields.iter().any(|field| ty_may_have_ref_inner(tcx, field, depth))
                }
                ty::Pat(ty, _) | ty::Slice(ty) | ty::Array(ty, _) => {
                    ty_may_have_ref_inner(tcx, *ty, depth)
                }
                ty::Adt(adt_def, args) => {
                    adt_def.has_param()
                        || adt_def.has_aliases()
                        || adt_def.all_fields().any(|field| {
                            ty_may_have_ref_inner(
                                tcx,
                                field.ty(tcx, args).skip_normalization(),
                                depth,
                            )
                        })
                }
                ty::Ref(..)
                | ty::RawPtr(_, _)
                | ty::Bound(..)
                | ty::Closure(..)
                | ty::CoroutineClosure(..)
                | ty::Dynamic(..)
                | ty::Foreign(_)
                | ty::Coroutine(..)
                | ty::CoroutineWitness(..)
                | ty::UnsafeBinder(_)
                | ty::Infer(_)
                | ty::Alias(..)
                | ty::Param(_)
                | ty::Placeholder(_) => true,
            }
        }
        ty_may_have_ref_inner(self.tcx, ty, 0)
    }

    /// Returns `false` if we're confident that the middle type doesn't have an
    /// interesting niche so we can skip that step when transmuting.
    ///
    /// The backend will emit `assume`s when transmuting between types with niches,
    /// so we want to preserve `i32 -> char -> u32` so that that data is around,
    /// but it's fine to skip whole-range-is-value steps like `A -> u32 -> B`.
    fn transmute_may_have_niche_of_interest_to_backend(
        &self,
        from_ty: Ty<'tcx>,
        middle_ty: Ty<'tcx>,
        to_ty: Ty<'tcx>,
    ) -> bool {
        let Ok(middle_layout) = self.ecx.layout_of(middle_ty) else {
            // If it's too generic or something, then assume it might be interesting later.
            return true;
        };

        if middle_layout.uninhabited {
            return true;
        }

        match middle_layout.backend_repr {
            BackendRepr::Scalar(mid) => {
                if mid.is_always_valid(&self.ecx) {
                    // With no niche it's never interesting, so don't bother
                    // looking at the layout of the other two types.
                    false
                } else if let Ok(from_layout) = self.ecx.layout_of(from_ty)
                    && !from_layout.uninhabited
                    && from_layout.size == middle_layout.size
                    && let BackendRepr::Scalar(from_a) = from_layout.backend_repr
                    && let mid_range = mid.valid_range(&self.ecx)
                    && let from_range = from_a.valid_range(&self.ecx)
                    && mid_range.contains_range(from_range, middle_layout.size)
                {
                    // The `from_range` is a (non-strict) subset of `mid_range`
                    // such as if we're doing `bool` -> `ascii::Char` -> `_`,
                    // where `from_range: 0..=1` and `mid_range: 0..=127`,
                    // and thus the middle doesn't tell us anything we don't
                    // already know from the initial type.
                    false
                } else if let Ok(to_layout) = self.ecx.layout_of(to_ty)
                    && !to_layout.uninhabited
                    && to_layout.size == middle_layout.size
                    && let BackendRepr::Scalar(to_a) = to_layout.backend_repr
                    && let mid_range = mid.valid_range(&self.ecx)
                    && let to_range = to_a.valid_range(&self.ecx)
                    && mid_range.contains_range(to_range, middle_layout.size)
                {
                    // The `to_range` is a (non-strict) subset of `mid_range`
                    // such as if we're doing `_` -> `ascii::Char` -> `bool`,
                    // where `mid_range: 0..=127` and `to_range: 0..=1`,
                    // and thus the middle doesn't tell us anything we don't
                    // already know from the final type.
                    false
                } else {
                    true
                }
            }
            BackendRepr::ScalarPair { a, b, b_offset: _ } => {
                // The offset is irrelevant to niches since it can only cause padding,
                // which can never have a niche since it's uninitialized.
                !a.is_always_valid(&self.ecx) || !b.is_always_valid(&self.ecx)
            }
            BackendRepr::SimdVector { .. }
            | BackendRepr::SimdScalableVector { .. }
            | BackendRepr::Memory { .. } => false,
        }
    }

    fn value_is_all_in_one_field(
        &self,
        ty: Ty<'tcx>,
        variant: VariantIdx,
    ) -> Option<(FieldIdx, Ty<'tcx>)> {
        if let Ok(layout) = self.ecx.layout_of(ty)
            && let abi::Variants::Single { index } = layout.variants
            && index == variant
            && let Some((field_idx, field_layout)) = layout.non_1zst_field(&self.ecx)
            && layout.size == field_layout.size
        {
            // We needed to check the variant to avoid trying to read the tag
            // field from an enum where no fields have variants, since that tag
            // field isn't in the `Aggregate` from which we're getting values.
            Some((field_idx, field_layout.ty))
        } else if let ty::Adt(adt, args) = ty.kind()
            && adt.is_struct()
            && adt.repr().transparent()
            && let [single_field] = adt.non_enum_variant().fields.raw.as_slice()
        {
            Some((FieldIdx::ZERO, single_field.ty(self.tcx, args).skip_norm_wip()))
        } else {
            None
        }
    }
}

/// Return true if any evaluation of this constant in the same MIR body
/// always returns the same value, taking into account even pointer identity tests.
///
/// In other words, this answers: is "cloning" the `Const` ok?
///
/// This returns `false` for constants that synthesize new `AllocId` when they are instantiated.
/// It is `true` for anything else, since a given `AllocId` *does* have a unique runtime value
/// within the scope of a single MIR body.
fn is_deterministic(c: Const<'_>) -> bool {
    // Primitive types cannot contain provenance and always have the same value.
    if c.ty().is_primitive() {
        return true;
    }

    match c {
        // Some constants may generate fresh allocations for pointers they contain,
        // so using the same constant twice can yield two different results.
        // Notably, valtrees purposefully generate new allocations.
        Const::Ty(..) => false,
        // We do not know the contents, so don't attempt to do anything clever.
        Const::Unevaluated(..) => false,
        // When an evaluated constant contains provenance, it is encoded as an `AllocId`.
        // Cloning the constant will reuse the same `AllocId`. If this is in the same MIR
        // body, this same `AllocId` will result in the same pointer in codegen.
        Const::Val(..) => true,
    }
}

/// Check if a constant may contain provenance information.
/// Can return `true` even if there is no provenance.
fn may_have_provenance(tcx: TyCtxt<'_>, value: ConstValue, size: Size) -> bool {
    match value {
        ConstValue::ZeroSized | ConstValue::Scalar(Scalar::Int(_)) => return false,
        ConstValue::Scalar(Scalar::Ptr(..)) | ConstValue::Slice { .. } => return true,
        ConstValue::Indirect { alloc_id, offset } => !tcx
            .global_alloc(alloc_id)
            .unwrap_memory()
            .inner()
            .provenance()
            .range_empty(AllocRange::from(offset..offset + size), &tcx),
    }
}

fn op_to_prop_const<'tcx>(
    ecx: &mut InterpCx<'tcx, DummyMachine>,
    op: &OpTy<'tcx>,
) -> Option<ConstValue> {
    // Do not attempt to propagate unsized locals.
    if op.layout.is_unsized() {
        return None;
    }

    // This constant is a ZST, just return an empty value.
    if op.layout.is_zst() {
        return Some(ConstValue::ZeroSized);
    }

    // Do not synthetize too large constants. Codegen will just memcpy them, which we'd like to
    // avoid.
    // But we *do* want to synthesize any size constant if it is entirely uninit because that
    // benefits codegen, which has special handling for them.
    if !op.is_immediate_uninit()
        && !matches!(
            op.layout.backend_repr,
            BackendRepr::Scalar(..) | BackendRepr::ScalarPair { .. }
        )
    {
        return None;
    }

    // If this constant has scalar ABI, return it as a `ConstValue::Scalar`.
    if let BackendRepr::Scalar(abi::Scalar::Initialized { .. }) = op.layout.backend_repr
        && let Some(scalar) = ecx.read_scalar(op).discard_err()
    {
        if !scalar.try_to_scalar_int().is_ok() {
            // Check that we do not leak a pointer.
            // Those pointers may lose part of their identity in codegen.
            // FIXME: remove this hack once https://github.com/rust-lang/rust/issues/128775 is fixed.
            return None;
        }
        return Some(ConstValue::Scalar(scalar));
    }

    // If this constant is already represented as an `Allocation`,
    // try putting it into global memory to return it.
    if let Either::Left(mplace) = op.as_mplace_or_imm() {
        let (size, _align) = ecx.size_and_align_of_val(&mplace).discard_err()??;

        // Do not try interning a value that contains provenance.
        // Due to https://github.com/rust-lang/rust/issues/128775, doing so could lead to bugs.
        // FIXME: remove this hack once that issue is fixed.
        let alloc_ref = ecx.get_ptr_alloc(mplace.ptr(), size).discard_err()??;
        if alloc_ref.has_provenance() {
            return None;
        }

        let pointer = mplace.ptr().into_pointer_or_addr().ok()?;
        let (prov, offset) = pointer.prov_and_relative_offset();
        let alloc_id = prov.alloc_id();
        intern_const_alloc_for_constprop(ecx, alloc_id).discard_err()?;

        // `alloc_id` may point to a static. Codegen will choke on an `Indirect` with anything
        // by `GlobalAlloc::Memory`, so do fall through to copying if needed.
        // FIXME: find a way to treat this more uniformly (probably by fixing codegen)
        if let GlobalAlloc::Memory(alloc) = ecx.tcx.global_alloc(alloc_id)
            // Transmuting a constant is just an offset in the allocation. If the alignment of the
            // allocation is not enough, fallback to copying into a properly aligned value.
            && alloc.inner().align >= op.layout.align.abi
        {
            return Some(ConstValue::Indirect { alloc_id, offset });
        }
    }

    // Everything failed: create a new allocation to hold the data.
    let alloc_id =
        ecx.intern_with_temp_alloc(op.layout, |ecx, dest| ecx.copy_op(op, dest)).discard_err()?;
    Some(ConstValue::Indirect { alloc_id, offset: Size::ZERO })
}

impl<'tcx> VnState<'_, '_, 'tcx> {
    /// If either [`Self::try_as_constant`] as [`Self::try_as_place`] succeeds,
    /// returns that result as an [`Operand`].
    fn try_as_operand(&mut self, index: VnIndex, location: Location) -> Option<Operand<'tcx>> {
        if let Some(const_) = self.try_as_constant(index) {
            Some(Operand::Constant(Box::new(const_)))
        } else if let Value::RuntimeChecks(c) = self.get(index) {
            Some(Operand::RuntimeChecks(c))
        } else if let Some(place) = self.try_as_place(index, location, false) {
            self.reused_locals.insert(place.local);
            Some(Operand::Copy(place))
        } else {
            None
        }
    }

    /// If `index` is a `Value::Constant`, return the `Constant` to be put in the MIR.
    fn try_as_constant(&mut self, index: VnIndex) -> Option<ConstOperand<'tcx>> {
        let value = self.get(index);

        // This was already an *evaluated* constant in MIR, do not change it.
        if let Value::Constant { value, disambiguator: None } = value
            && let Const::Val(..) = value
        {
            return Some(ConstOperand { span: DUMMY_SP, user_ty: None, const_: value });
        }

        if let Some(value) = self.try_as_evaluated_constant(index) {
            return Some(ConstOperand { span: DUMMY_SP, user_ty: None, const_: value });
        }

        // We failed to provide an evaluated form, fallback to using the unevaluated constant.
        if let Value::Constant { value, disambiguator: None } = value {
            return Some(ConstOperand { span: DUMMY_SP, user_ty: None, const_: value });
        }

        None
    }

    fn try_as_evaluated_constant(&mut self, index: VnIndex) -> Option<Const<'tcx>> {
        let op = self.eval_to_const(index)?;
        if op.layout.is_unsized() {
            // Do not attempt to propagate unsized locals.
            return None;
        }

        let value = op_to_prop_const(&mut self.ecx, op)?;

        // Check that we do not leak a pointer.
        // Those pointers may lose part of their identity in codegen.
        // FIXME: remove this hack once https://github.com/rust-lang/rust/issues/128775 is fixed.
        if may_have_provenance(self.tcx, value, op.layout.size) {
            return None;
        }

        Some(Const::Val(value, op.layout.ty))
    }

    /// Construct a place which holds the same value as `index` and for which all locals strictly
    /// dominate `loc`. If you used this place, add its base local to `reused_locals` to remove
    /// storage statements.
    #[instrument(level = "trace", skip(self), ret)]
    fn try_as_place(
        &mut self,
        mut index: VnIndex,
        loc: Location,
        allow_complex_projection: bool,
    ) -> Option<Place<'tcx>> {
        let mut projection = SmallVec::<[PlaceElem<'tcx>; 1]>::new();
        loop {
            if let Some(local) = self.try_as_local(index, loc) {
                projection.reverse();
                let place =
                    Place { local, projection: self.tcx.mk_place_elems(projection.as_slice()) };
                return Some(place);
            } else if projection.last() == Some(&PlaceElem::Deref) {
                // `Deref` can only be the first projection in a place.
                // If we are here, we failed to find a local, and we already have a `Deref`.
                // Trying to add projections will only result in an ill-formed place.
                return None;
            } else if let Value::Projection(pointer, proj) = self.get(index)
                && (allow_complex_projection || proj.is_stable_offset())
                && let Some(proj) = self.try_as_place_elem(self.ty(index), proj, loc)
            {
                if proj == PlaceElem::Deref {
                    // We can introduce a new dereference if the source value cannot be changed in the body.
                    // Dereferencing an immutable argument always gives the same value in the body.
                    match self.get(pointer) {
                        Value::Argument(_)
                            if let Some(Mutability::Not) = self.ty(pointer).ref_mutability() => {}
                        _ => {
                            return None;
                        }
                    }
                }
                projection.push(proj);
                index = pointer;
            } else {
                return None;
            }
        }
    }

    /// If there is a local which is assigned `index`, and its assignment strictly dominates `loc`,
    /// return it. If you used this local, add it to `reused_locals` to remove storage statements.
    fn try_as_local(&mut self, index: VnIndex, loc: Location) -> Option<Local> {
        let other = self.rev_locals.get(index)?;
        other
            .iter()
            .find(|&&other| self.ssa.assignment_dominates(&self.dominators, other, loc))
            .copied()
    }
}

impl<'tcx> MutVisitor<'tcx> for VnState<'_, '_, 'tcx> {
    fn tcx(&self) -> TyCtxt<'tcx> {
        self.tcx
    }

    fn visit_place(&mut self, place: &mut Place<'tcx>, context: PlaceContext, location: Location) {
        self.simplify_place_projection(place, location);
        self.super_place(place, context, location);
    }

    fn visit_operand(&mut self, operand: &mut Operand<'tcx>, location: Location) {
        self.simplify_operand(operand, location);
        self.super_operand(operand, location);
    }

    fn visit_assign(
        &mut self,
        lhs: &mut Place<'tcx>,
        rvalue: &mut Rvalue<'tcx>,
        location: Location,
    ) {
        self.simplify_place_projection(lhs, location);

        let value = self.simplify_rvalue(lhs, rvalue, location);
        if let Some(value) = value {
            // FIXME: Is it correct to make these retagging assignments?
            if let Some(const_) = self.try_as_constant(value) {
                *rvalue = Rvalue::Use(Operand::Constant(Box::new(const_)), WithRetag::Yes);
            } else if let Some(place) = self.try_as_place(value, location, false)
                && !matches!(rvalue, Rvalue::Use(Operand::Move(p) | Operand::Copy(p), _) if p == &place)
            {
                *rvalue = Rvalue::Use(Operand::Copy(place), WithRetag::Yes);
                self.reused_locals.insert(place.local);
            }
        }

        if let Some(local) = lhs.as_local()
            && self.ssa.is_ssa(local)
            && let rvalue_ty = rvalue.ty(self.local_decls, self.tcx)
            // FIXME(#112651) `rvalue` may have a subtype to `local`. We can only mark
            // `local` as reusable if we have an exact type match.
            && self.local_decls[local].ty == rvalue_ty
        {
            let value = value.unwrap_or_else(|| self.new_opaque(rvalue_ty));
            self.assign(local, value);
        }
    }

    fn visit_terminator(&mut self, terminator: &mut Terminator<'tcx>, location: Location) {
        if let Terminator { kind: TerminatorKind::Call { destination, .. }, .. } = terminator {
            if let Some(local) = destination.as_local()
                && self.ssa.is_ssa(local)
            {
                let ty = self.local_decls[local].ty;
                let opaque = self.new_opaque(ty);
                self.assign(local, opaque);
            }
        }
        self.super_terminator(terminator, location);
    }
}

struct StorageRemover<'a, 'tcx> {
    tcx: TyCtxt<'tcx>,
    reused_locals: &'a DenseBitSet<Local>,
    storage_to_remove: &'a DenseBitSet<Local>,
}

impl<'a, 'tcx> MutVisitor<'tcx> for StorageRemover<'a, 'tcx> {
    fn tcx(&self) -> TyCtxt<'tcx> {
        self.tcx
    }

    fn visit_operand(&mut self, operand: &mut Operand<'tcx>, _: Location) {
        if let Operand::Move(place) = *operand
            && !place.is_indirect_first_projection()
            && self.reused_locals.contains(place.local)
        {
            *operand = Operand::Copy(place);
        }
    }

    fn visit_statement(&mut self, stmt: &mut Statement<'tcx>, loc: Location) {
        match stmt.kind {
            // When removing storage statements, we need to remove both (#107511).
            StatementKind::StorageLive(l) | StatementKind::StorageDead(l)
                if self.storage_to_remove.contains(l) =>
            {
                stmt.make_nop(true)
            }
            _ => self.super_statement(stmt, loc),
        }
    }
}

struct StorageChecker<'a, 'tcx> {
    reused_locals: &'a DenseBitSet<Local>,
    storage_to_remove: DenseBitSet<Local>,
    maybe_uninit: ResultsCursor<'a, 'tcx, MaybeUninitializedLocals>,
}

impl<'a, 'tcx> Visitor<'tcx> for StorageChecker<'a, 'tcx> {
    fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) {
        match context {
            // These mutating uses do not require the local to be initialized,
            // so we cannot use our maybe-uninit check on them.
            // However, GVN doesn't introduce or move mutations,
            // so this local must already have valid storage at this location.
            PlaceContext::MutatingUse(MutatingUseContext::AsmOutput)
            | PlaceContext::MutatingUse(MutatingUseContext::Call)
            | PlaceContext::MutatingUse(MutatingUseContext::Store)
            | PlaceContext::MutatingUse(MutatingUseContext::Yield)
            | PlaceContext::NonUse(_) => {
                return;
            }
            // Must check validity for other mutating usages and all non-mutating uses.
            PlaceContext::MutatingUse(_) | PlaceContext::NonMutatingUse(_) => {}
        }

        // We only need to check reused locals which we haven't already removed storage for.
        if !self.reused_locals.contains(local) || self.storage_to_remove.contains(local) {
            return;
        }

        self.maybe_uninit.seek_before_primary_effect(location);

        if self.maybe_uninit.get().contains(local) {
            debug!(
                ?location,
                ?local,
                "local is reused and is maybe uninit at this location, marking it for storage statement removal"
            );
            self.storage_to_remove.insert(local);
        }
    }
}