regalloc2/ion/
redundant_moves.rs

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

regalloc2/ion/
redundant_moves.rs
