1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

//! Redundant-move elimination.

use crate::{Allocation, VReg};
use fxhash::FxHashMap;
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.iter() {
                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);
            }
            existing_copies.clear();
        }
        self.allocs.remove(&alloc);
    }
}