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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

//! A simple GVN pass.

use crate::cursor::{Cursor, FuncCursor};
use crate::dominator_tree::DominatorTree;
use crate::ir::{Function, Inst, InstructionData, Opcode, Type};
use crate::scoped_hash_map::ScopedHashMap;
use crate::timing;
use alloc::vec::Vec;
use core::cell::{Ref, RefCell};
use core::hash::{Hash, Hasher};

/// Test whether the given opcode is unsafe to even consider for GVN.
fn trivially_unsafe_for_gvn(opcode: Opcode) -> bool {
    opcode.is_call()
        || opcode.is_branch()
        || opcode.is_terminator()
        || opcode.is_return()
        || opcode.can_store()
        || (opcode.can_trap() && !opcode.side_effects_idempotent())
        || (opcode.other_side_effects() && !opcode.side_effects_idempotent())
}

/// Test that, if the specified instruction is a load, it doesn't have the `readonly` memflag.
fn is_load_and_not_readonly(inst_data: &InstructionData) -> bool {
    match *inst_data {
        InstructionData::Load { flags, .. } => !flags.readonly(),
        _ => inst_data.opcode().can_load(),
    }
}

/// Wrapper around `InstructionData` which implements `Eq` and `Hash`
#[derive(Clone)]
struct HashKey<'a, 'f: 'a> {
    inst: InstructionData,
    ty: Type,
    pos: &'a RefCell<FuncCursor<'f>>,
}
impl<'a, 'f: 'a> Hash for HashKey<'a, 'f> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let pool = &self.pos.borrow().func.dfg.value_lists;
        self.inst.hash(state, pool, |value| value);
        self.ty.hash(state);
    }
}
impl<'a, 'f: 'a> PartialEq for HashKey<'a, 'f> {
    fn eq(&self, other: &Self) -> bool {
        let pool = &self.pos.borrow().func.dfg.value_lists;
        self.inst.eq(&other.inst, pool, |value| value) && self.ty == other.ty
    }
}
impl<'a, 'f: 'a> Eq for HashKey<'a, 'f> {}

/// Perform simple GVN on `func`.
///
pub fn do_simple_gvn(func: &mut Function, domtree: &mut DominatorTree) {
    let _tt = timing::gvn();
    debug_assert!(domtree.is_valid());

    // Visit blocks in a reverse post-order.
    //
    // The RefCell here is a bit ugly since the HashKeys in the ScopedHashMap
    // need a reference to the function.
    let pos = RefCell::new(FuncCursor::new(func));

    let mut visible_values: ScopedHashMap<HashKey, Inst> = ScopedHashMap::new();
    let mut scope_stack: Vec<Inst> = Vec::new();

    for &block in domtree.cfg_postorder().iter().rev() {
        {
            // Pop any scopes that we just exited.
            let layout = &pos.borrow().func.layout;
            loop {
                if let Some(current) = scope_stack.last() {
                    if domtree.dominates(*current, block, layout) {
                        break;
                    }
                } else {
                    break;
                }
                scope_stack.pop();
                visible_values.decrement_depth();
            }

            // Push a scope for the current block.
            scope_stack.push(layout.first_inst(block).unwrap());
            visible_values.increment_depth();
        }

        pos.borrow_mut().goto_top(block);
        while let Some(inst) = {
            let mut pos = pos.borrow_mut();
            pos.next_inst()
        } {
            // Resolve aliases, particularly aliases we created earlier.
            pos.borrow_mut().func.dfg.resolve_aliases_in_arguments(inst);

            let func = Ref::map(pos.borrow(), |pos| &pos.func);

            let opcode = func.dfg.insts[inst].opcode();

            if opcode.is_branch() && !opcode.is_terminator() {
                scope_stack.push(func.layout.next_inst(inst).unwrap());
                visible_values.increment_depth();
            }

            if trivially_unsafe_for_gvn(opcode) {
                continue;
            }

            // These are split up to separate concerns.
            if is_load_and_not_readonly(&func.dfg.insts[inst]) {
                continue;
            }

            let ctrl_typevar = func.dfg.ctrl_typevar(inst);
            let key = HashKey {
                inst: func.dfg.insts[inst],
                ty: ctrl_typevar,
                pos: &pos,
            };
            use crate::scoped_hash_map::Entry::*;
            match visible_values.entry(key) {
                Occupied(entry) => {
                    #[allow(clippy::debug_assert_with_mut_call)]
                    {
                        // Clippy incorrectly believes `&func.layout` should not be used here:
                        // https://github.com/rust-lang/rust-clippy/issues/4737
                        debug_assert!(domtree.dominates(*entry.get(), inst, &func.layout));
                    }

                    // If the redundant instruction is representing the current
                    // scope, pick a new representative.
                    let old = scope_stack.last_mut().unwrap();
                    if *old == inst {
                        *old = func.layout.next_inst(inst).unwrap();
                    }
                    // Replace the redundant instruction and remove it.
                    drop(func);
                    let mut pos = pos.borrow_mut();
                    pos.func.dfg.replace_with_aliases(inst, *entry.get());
                    pos.remove_inst_and_step_back();
                }
                Vacant(entry) => {
                    entry.insert(inst);
                }
            }
        }
    }
}