/src/regalloc2/src/ion/redundant_moves.rs

Source
//! Redundant-move elimination.

use crate::{Allocation, FxHashMap, VReg};
use smallvec::{smallvec, SmallVec};

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum RedundantMoveState {
    Copy(Allocation, Option<VReg>),
    Orig(VReg),
    None,
}
#[derive(Clone, Debug, Default)]
pub struct RedundantMoveEliminator {
    allocs: FxHashMap<Allocation, RedundantMoveState>,
    reverse_allocs: FxHashMap<Allocation, SmallVec<[Allocation; 4]>>,
}
#[derive(Copy, Clone, Debug)]
pub struct RedundantMoveAction {
    pub elide: bool,
}

impl RedundantMoveEliminator {
    pub fn process_move(
        &mut self,
        from: Allocation,
        to: Allocation,
        to_vreg: Option<VReg>,
    ) -> RedundantMoveAction {
        // Look up the src and dest.
        let from_state = self
            .allocs
            .get(&from)
            .map(|&p| p)
            .unwrap_or(RedundantMoveState::None);
        let to_state = self
            .allocs
            .get(&to)
            .map(|&p| p)
            .unwrap_or(RedundantMoveState::None);

        trace!(
            "     -> redundant move tracker: from {} to {} to_vreg {:?}",
            from,
            to,
            to_vreg
        );
        trace!(
            "       -> from_state {:?} to_state {:?}",
            from_state,
            to_state
        );

        if from == to && to_vreg.is_some() {
            self.clear_alloc(to);
            self.allocs
                .insert(to, RedundantMoveState::Orig(to_vreg.unwrap()));
            return RedundantMoveAction { elide: true };
        }

        let src_vreg = match from_state {
            RedundantMoveState::Copy(_, opt_r) => opt_r,
            RedundantMoveState::Orig(r) => Some(r),
            _ => None,
        };
        trace!("      -> src_vreg {:?}", src_vreg);
        let dst_vreg = to_vreg.or(src_vreg);
        trace!("      -> dst_vreg {:?}", dst_vreg);
        let existing_dst_vreg = match to_state {
            RedundantMoveState::Copy(_, opt_r) => opt_r,
            RedundantMoveState::Orig(r) => Some(r),
            _ => None,
        };
        trace!("      -> existing_dst_vreg {:?}", existing_dst_vreg);

        let elide = match (from_state, to_state) {
            (_, RedundantMoveState::Copy(orig_alloc, _)) if orig_alloc == from => true,
            (RedundantMoveState::Copy(new_alloc, _), _) if new_alloc == to => true,
            _ => false,
        };
        trace!("      -> elide {}", elide);

        // Invalidate all existing copies of `to` if `to` actually changed value.
        if !elide {
            self.clear_alloc(to);
        }

        // Set up forward and reverse mapping. Don't track stack-to-stack copies.
        if from.is_reg() || to.is_reg() {
            self.allocs
                .insert(to, RedundantMoveState::Copy(from, dst_vreg));
            trace!(
                "     -> create mapping {} -> {:?}",
                to,
                RedundantMoveState::Copy(from, dst_vreg)
            );
            self.reverse_allocs
                .entry(from)
                .or_insert_with(|| smallvec![])
                .push(to);
        }

        RedundantMoveAction { elide }
    }

    pub fn clear(&mut self) {
        trace!("   redundant move eliminator cleared");
        self.allocs.clear();
        self.reverse_allocs.clear();
    }

    pub fn clear_alloc(&mut self, alloc: Allocation) {
        trace!("   redundant move eliminator: clear {:?}", alloc);
        if let Some(ref mut existing_copies) = self.reverse_allocs.get_mut(&alloc) {
            for to_inval in existing_copies.drain(..) {
                trace!("     -> clear existing copy: {:?}", to_inval);
                if let Some(val) = self.allocs.get_mut(&to_inval) {
                    match val {
                        RedundantMoveState::Copy(_, Some(vreg)) => {
                            *val = RedundantMoveState::Orig(*vreg);
                        }
                        _ => *val = RedundantMoveState::None,
                    }
                }
                self.allocs.remove(&to_inval);
            }
        }
        self.allocs.remove(&alloc);
    }
}

Line	Count	Source
1		//! Redundant-move elimination.
2
3		use crate::{Allocation, FxHashMap, VReg};
4		use smallvec::{smallvec, SmallVec};
5
6		#[derive(Copy, Clone, Debug, PartialEq, Eq)]
7		pub enum RedundantMoveState {
8		Copy(Allocation, Option<VReg>),
9		Orig(VReg),
10		None,
11		}
12		#[derive(Clone, Debug, Default)]
13		pub struct RedundantMoveEliminator {
14		allocs: FxHashMap<Allocation, RedundantMoveState>,
15		reverse_allocs: FxHashMap<Allocation, SmallVec<[Allocation; 4]>>,
16		}
17		#[derive(Copy, Clone, Debug)]
18		pub struct RedundantMoveAction {
19		pub elide: bool,
20		}
21
22		impl RedundantMoveEliminator {
23	1.03M	pub fn process_move(
24	1.03M	&mut self,
25	1.03M	from: Allocation,
26	1.03M	to: Allocation,
27	1.03M	to_vreg: Option<VReg>,
28	1.03M	) -> RedundantMoveAction {
29		// Look up the src and dest.
30	1.03M	let from_state = self
31	1.03M	.allocs
32	1.03M	.get(&from)
33	1.03M	.map(\|&p\| p)
34	1.03M	.unwrap_or(RedundantMoveState::None);
35	1.03M	let to_state = self
36	1.03M	.allocs
37	1.03M	.get(&to)
38	1.03M	.map(\|&p\| p)
39	1.03M	.unwrap_or(RedundantMoveState::None);
40
41	1.03M	trace!(
42		" -> redundant move tracker: from {} to {} to_vreg {:?}",
43		from,
44		to,
45		to_vreg
46		);
47	1.03M	trace!(
48		" -> from_state {:?} to_state {:?}",
49		from_state,
50		to_state
51		);
52
53	1.03M	if from == to && to_vreg.is_some() {
54	0	self.clear_alloc(to);
55	0	self.allocs
56	0	.insert(to, RedundantMoveState::Orig(to_vreg.unwrap()));
57	0	return RedundantMoveAction { elide: true };
58	1.03M	}
59
60	1.03M	let src_vreg = match from_state {
61	161k	RedundantMoveState::Copy(_, opt_r) => opt_r,
62	0	RedundantMoveState::Orig(r) => Some(r),
63	873k	_ => None,
64		};
65	1.03M	trace!(" -> src_vreg {:?}", src_vreg);
66	1.03M	let dst_vreg = to_vreg.or(src_vreg);
67	1.03M	trace!(" -> dst_vreg {:?}", dst_vreg);
68	1.03M	let existing_dst_vreg = match to_state {
69	189k	RedundantMoveState::Copy(_, opt_r) => opt_r,
70	0	RedundantMoveState::Orig(r) => Some(r),
71	846k	_ => None,
72		};
73	1.03M	trace!(" -> existing_dst_vreg {:?}", existing_dst_vreg);
74
75	1.03M	let elide = match (from_state, to_state) {
76	189k	(_, RedundantMoveState::Copy(orig_alloc, _)) if orig_alloc == from => true,
77	144k	(RedundantMoveState::Copy(new_alloc, _), _) if new_alloc == to => true,
78	894k	_ => false,
79		};
80	1.03M	trace!(" -> elide {}", elide);
81
82		// Invalidate all existing copies of `to` if `to` actually changed value.
83	1.03M	if !elide {
84	894k	self.clear_alloc(to);
85	894k	}
86
87		// Set up forward and reverse mapping. Don't track stack-to-stack copies.
88	1.03M	if from.is_reg() \|\| to.is_reg() {
89	1.03M	self.allocs
90	1.03M	.insert(to, RedundantMoveState::Copy(from, dst_vreg));
91	1.03M	trace!(
92		" -> create mapping {} -> {:?}",
93		to,
94	0	RedundantMoveState::Copy(from, dst_vreg)
95		);
96	1.03M	self.reverse_allocs
97	1.03M	.entry(from)
98	1.03M	.or_insert_with(\|\| smallvec![])
99	1.03M	.push(to);
100	0	}
101
102	1.03M	RedundantMoveAction { elide }
103	1.03M	}
104
105	131k	pub fn clear(&mut self) {
106	131k	trace!(" redundant move eliminator cleared");
107	131k	self.allocs.clear();
108	131k	self.reverse_allocs.clear();
109	131k	}
110
111	2.23M	pub fn clear_alloc(&mut self, alloc: Allocation) {
112	2.23M	trace!(" redundant move eliminator: clear {:?}", alloc);
113	2.23M	if let Some(ref mut existing_copies) = self.reverse_allocs.get_mut(&alloc) {
114	276k	for to_inval in existing_copies.drain(..) {
115	233k	trace!(" -> clear existing copy: {:?}", to_inval);
116	233k	if let Some(val) = self.allocs.get_mut(&to_inval) {
117	152k	match val {
118	151k	RedundantMoveState::Copy(_, Some(vreg)) => {
119	151k	val = RedundantMoveState::Orig(vreg);
120	151k	}
121	882	_ => *val = RedundantMoveState::None,
122		}
123	80.7k	}
124	233k	self.allocs.remove(&to_inval);
125		}
126	1.96M	}
127	2.23M	self.allocs.remove(&alloc);
128	2.23M	}
129		}

Coverage Report

Created: 2026-10-12 08:10