regalloc2/ion/
redundant_moves.rs

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

regalloc2/ion/
redundant_moves.rs
