To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.7% of users enabled 2FA.

mod.rs 7.43 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
use utils::LinkedHashMap;
use ast::ir::*;
use ast::ptr::*;
use compiler::machine_code::CompiledFunction;
use compiler::backend::get_color_for_precolored as alias;

mod alive_entry;
use compiler::backend::reg_alloc::validate::alive_entry::*;

mod exact_liveness;
use compiler::backend::reg_alloc::validate::exact_liveness::*;

pub fn validate_regalloc(cf: &CompiledFunction,
                         func: &MuFunctionVersion,
                         reg_assigned: LinkedHashMap<MuID, MuID>,
16
                         reg_coalesced:LinkedHashMap<MuID, MuID>,
17
18
19
20
                         reg_spilled: LinkedHashMap<MuID, P<Value>>)
{
    debug!("---Validating register allocation results---");

21
22
23
24
25
    debug!("coalesced registers: ");
    for (a, b) in reg_coalesced.iter() {
        debug!("{} -> {}", a, b);
    }

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
    debug!("liveness analysis...");
    let liveness = ExactLiveness::new(cf);
    for i in 0..cf.mc().number_of_insts() {
        cf.mc().trace_inst(i);

        liveness.trace(i);
    }

    let mut alive = AliveEntries::new();

    debug!("initializing alive entries for arguments...");

    // set up initial states

    // machine specific regs, such as program counter, stack pointer, etc
    add_machine_specific_regs_at_func_start(&mut alive);

    // arguments with real locations
    let ref frame = cf.frame;
    for (_, reg) in frame.argument_by_reg.iter() {
        alive.new_alive_reg(alias(reg.id()));
    }
    for (_, stack) in frame.argument_by_stack.iter() {
        alive.new_alive_mem(stack.clone());
    }

    debug!("alive entries in the beginning");
    debug!("{}", alive);

    let mc = cf.mc();

    for i in 0..mc.number_of_insts() {
        mc.trace_inst(i);

60
        if mc.is_jmp(i).is_some() {
61
62
63
64
65
66
67
68
69
70
71
            // we need to flow-sensitive analysis
            unimplemented!();
        }

        for reg_use in mc.get_inst_reg_uses(i) {
            validate_use(reg_use, &reg_assigned, &alive);
        }

        // remove kills in the inst from alive entries
        if let Some(kills) = liveness.get_kills(i) {
            for reg in kills.iter() {
72
                kill_reg(*reg, &reg_assigned, &mut alive);
73
74
75
76
77
            }
        }

        // add defines to alive entries
        for reg_def in mc.get_inst_reg_defines(i) {
78
79
80
81
82
83
84
85
            let liveout = liveness.get_liveout(i).unwrap();

            // if reg is in the liveout set, we add a define to it
            if liveout.contains(&reg_def) {
                add_def(reg_def, &reg_assigned, &reg_coalesced, &mut alive);
            } else {
                kill_reg(reg_def, &reg_assigned, &mut alive);
            }
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
        }

        debug!("{}", alive);
        trace!("---");
    }
}

fn get_machine_reg(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>) -> MuID {
    // find machine regs
    if reg < MACHINE_ID_END {
        reg
    } else {
        match reg_assigned.get(&reg) {
            Some(reg) => *reg,
            None => panic!("Temp {} is not assigned to any machine register", reg)
        }
    }
}

fn validate_use(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, alive: &AliveEntries) {
    if reg < MACHINE_ID_END {
        // machine register

        // instruction selector choose to use machine registers
        // it is not about the correctness of register allocation, we do not verify it here
    } else {
        let machine_reg = get_machine_reg(reg, reg_assigned);
        let temp = reg;

        // ensure temp is assigned to the same machine reg in alive entries
        if let Some(entry) = alive.find_entry_for_temp(temp) {
            if !entry.match_reg(machine_reg) {
                error!("Temp{}/MachineReg{} does not match at this point. ", temp, machine_reg);
                error!("Temp{} is assigned as {}", temp, entry);

                panic!("validation failed: temp-reg pair doesnt match")
            }
        } else {
            error!("Temp{} is not alive at this point. ", temp);

            panic!("validation failed: use a temp that is not alive");
        }
    }
}

131
fn kill_reg(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, alive: &mut AliveEntries) {
132
133
134
135
136
137
138
139
140
141
142
    if reg < MACHINE_ID_END {
        if alive.find_entry_for_reg(reg).is_some() {
            alive.remove_reg(reg);
        }
    } else {
        let temp = reg;

        alive.remove_temp(temp);
    }
}

143
fn add_def(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, reg_coalesced: &LinkedHashMap<MuID, MuID>, alive: &mut AliveEntries) {
144
    if reg < MACHINE_ID_END {
145
146
147
148
        // if it is a machine register
        // we require either it doesn't have an entry,
        // or its entry doesnt have a temp, so that we can safely overwrite it

149
150
151
        if alive.find_entry_for_reg(reg).is_none() {
            // add new machine register
            alive.new_alive_reg(reg);
152
153
154
155
156
157
158
159
        } else if !alive.find_entry_for_reg(reg).unwrap().has_temp() {
            // overwrite it
        } else {
            let old_temp = alive.find_entry_for_reg(reg).unwrap().get_temp().unwrap();

            error!("Register{}/Temp{} is alive at this point, defining a new value to Register{} is incorrect", reg, old_temp, reg);

            panic!("validation failed: define a register that is already alive (value overwritten)");
160
161
162
163
164
        }
    } else {
        let machine_reg = get_machine_reg(reg, reg_assigned);
        let temp = reg;

165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
        if alive.find_entry_for_reg(machine_reg).is_none() {
            // if this register is not alive, we add an entry for it
            alive.add_temp_in_reg(temp, machine_reg);
        } else {
            // otherwise, this register contains some value
            {
                let entry = alive.find_entry_for_reg_mut(machine_reg).unwrap();

                if !entry.has_temp() {
                    debug!("adding temp {} to reg {}", temp, machine_reg);
                    entry.set_temp(temp);
                } else {
                    // if the register is holding a temporary, it needs to be coalesced with new temp
                    let old_temp: MuID = entry.get_temp().unwrap();

qinsoon's avatar
qinsoon committed
180
181
182
183
                    if old_temp == temp {
                        // the register that is used at this instruction, and also defined here
                        // safe
                    } else  if (reg_coalesced.contains_key(&old_temp) && *reg_coalesced.get(&old_temp).unwrap() == temp)
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
                        || (reg_coalesced.contains_key(&temp) && *reg_coalesced.get(&temp).unwrap() == old_temp)
                    {
                        // coalesced, safe
                    } else {
                        // not coalesced, error
                        error!("Temp{} and Temp{} are not coalesced, but they use the same Register{}", temp, old_temp, machine_reg);

                        panic!("validation failed: define a register that is already alive, and their temps are not coalesced");
                    }
                }
            }

            // they are coalesced, it is valid
            alive.add_temp_in_reg(temp, machine_reg);
        }
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
    }
}

#[cfg(target_arch = "x86_64")]
fn add_machine_specific_regs_at_func_start(alive: &mut AliveEntries) {
    use compiler::backend::x86_64;

    // RIP, RSP, RBP always have valid values
    alive.new_alive_reg(x86_64::RIP.id());
    alive.new_alive_reg(x86_64::RSP.id());
    alive.new_alive_reg(x86_64::RBP.id());

    // callee saved regs are alive
    alive.new_alive_reg(x86_64::RBX.id());
    alive.new_alive_reg(x86_64::R12.id());
    alive.new_alive_reg(x86_64::R13.id());
    alive.new_alive_reg(x86_64::R14.id());
    alive.new_alive_reg(x86_64::R15.id());
}