To protect your data, the CISO officer has suggested users to enable GitLab 2FA as soon as possible.

mod.rs 11.9 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>,
qinsoon's avatar
qinsoon committed
17
18
                         reg_spilled: LinkedHashMap<MuID, P<Value>>,
                         spill_scratch_regs: LinkedHashMap<MuID, MuID>)
19
20
21
{
    debug!("---Validating register allocation results---");

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

27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
    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()));
    }
qinsoon's avatar
qinsoon committed
49
50
51
52
    // we do not consider mem loc for arguments - we do consider mem loc for spilling
//    for (_, stack) in frame.argument_by_stack.iter() {
//        alive.new_alive_mem(stack.clone());
//    }
53
54
55
56
57
58
59
60
61

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

    let mc = cf.mc();

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

62
        if mc.is_jmp(i).is_some() {
qinsoon's avatar
qinsoon committed
63
            // we need to do flow-sensitive analysis
64
65
66
            unimplemented!();
        }

qinsoon's avatar
qinsoon committed
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
        // validate spill
        if let Some(spill_loc) = mc.is_spill_load(i) {
            // spill load is a move from spill location (mem) to temp
            // its define is the scratch temp
            let scratch_temp = mc.get_inst_reg_defines(i)[0];
            let source_temp  = get_source_temp_for_scratch(scratch_temp, &spill_scratch_regs);

            add_spill_load(scratch_temp, source_temp, spill_loc, &reg_spilled, &mut alive);
        } else if let Some(spill_loc) = mc.is_spill_store(i) {
            // spill store is a move from scratch temp to mem
            // it uses scratch temp as well as stack pointer (to refer to mem)
            // we try to find the scratch temp
            let scratch_temp = {
                let uses = mc.get_inst_reg_uses(i);
                let mut use_temps = vec![];
                for reg in uses {
                    if reg >= MACHINE_ID_END {
                        use_temps.push(reg)
                    }
                };

                assert!(use_temps.len() == 1);

                use_temps[0]
            };
            let source_temp = get_source_temp_for_scratch(scratch_temp, &spill_scratch_regs);

            add_spill_store(scratch_temp, source_temp, spill_loc, &reg_spilled, &reg_coalesced, &mut alive);
        }

        // validate uses of registers
98
99
100
101
        for reg_use in mc.get_inst_reg_uses(i) {
            validate_use(reg_use, &reg_assigned, &alive);
        }

qinsoon's avatar
qinsoon committed
102
        // remove registers that die at this instruction from alive entries
103
104
        if let Some(kills) = liveness.get_kills(i) {
            for reg in kills.iter() {
105
                kill_reg(*reg, &reg_assigned, &mut alive);
106
107
108
109
110
            }
        }

        // add defines to alive entries
        for reg_def in mc.get_inst_reg_defines(i) {
111
112
113
114
115
116
117
118
            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);
            }
119
120
121
122
123
124
125
        }

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

qinsoon's avatar
qinsoon committed
126
127
128
129
130
131
132
fn get_source_temp_for_scratch(scratch: MuID, spill_scratch_temps: &LinkedHashMap<MuID, MuID>) -> MuID {
    match spill_scratch_temps.get(&scratch) {
        Some(src) => get_source_temp_for_scratch(*src, spill_scratch_temps),
        None => scratch
    }
}

133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
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
qinsoon's avatar
qinsoon committed
156
157
158
159
160
        if alive.has_entries_for_temp(temp) {
            alive.find_entries_for_temp(temp).iter().inspect(|entry| {
                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);
161

qinsoon's avatar
qinsoon committed
162
163
164
                    panic!("validation failed: temp-reg pair doesnt match")
                }
            });
165
166
167
168
169
170
171
172
        } else {
            error!("Temp{} is not alive at this point. ", temp);

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

173
fn kill_reg(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, alive: &mut AliveEntries) {
174
    if reg < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
175
        if alive.has_entries_for_reg(reg) {
176
177
178
179
180
181
182
183
184
            alive.remove_reg(reg);
        }
    } else {
        let temp = reg;

        alive.remove_temp(temp);
    }
}

qinsoon's avatar
qinsoon committed
185
186
187
188
189
190
191
192
193
194
195
fn is_coalesced(reg1: MuID, reg2: MuID, reg_coalesced: &LinkedHashMap<MuID, MuID>) -> bool {
    if reg1 == reg2 {
        true
    } else if (reg_coalesced.contains_key(&reg1) && *reg_coalesced.get(&reg2).unwrap() == reg1)
        || (reg_coalesced.contains_key(&reg2) && *reg_coalesced.get(&reg1).unwrap() == reg2) {
        true
    } else {
        false
    }
}

196
fn add_def(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, reg_coalesced: &LinkedHashMap<MuID, MuID>, alive: &mut AliveEntries) {
qinsoon's avatar
qinsoon committed
197
198
199
    let machine_reg = get_machine_reg(reg, reg_assigned);
    let temp = reg;

200
    if reg < MACHINE_ID_END {
201
202
203
204
        // 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

qinsoon's avatar
qinsoon committed
205
        if !alive.has_entries_for_reg(reg) {
206
207
            // add new machine register
            alive.new_alive_reg(reg);
qinsoon's avatar
qinsoon committed
208
209
        } else if !alive.find_entries_for_reg(reg).iter().any(|entry| entry.has_temp()) {
            // overwrite the value that is not used
210
        } else {
qinsoon's avatar
qinsoon committed
211
212
213
214
            alive.find_entries_for_reg(reg).iter().inspect(|entry| {
                let old_temp = entry.get_temp().unwrap();
                error!("Register{}/Temp{} is alive at this point, defining a new value to Register{} is incorrect", reg, old_temp, reg);
            });
215
216

            panic!("validation failed: define a register that is already alive (value overwritten)");
217
218
        }
    } else {
qinsoon's avatar
qinsoon committed
219
        if !alive.has_entries_for_reg(machine_reg) {
220
221
222
223
224
            // 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
            {
qinsoon's avatar
qinsoon committed
225
226
227
228
                for entry in alive.find_entries_for_reg_mut(machine_reg) {
                    if !entry.has_temp() {
                        debug!("adding temp {} to reg {}", temp, machine_reg);
                        entry.set_temp(temp);
229
                    } else {
qinsoon's avatar
qinsoon committed
230
231
                        // if the register is holding a temporary, it needs to be coalesced with new temp
                        let old_temp: MuID = entry.get_temp().unwrap();
232

qinsoon's avatar
qinsoon committed
233
234
235
236
237
238
239
240
                        if is_coalesced(old_temp, temp, reg_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");
                        }
241
242
243
244
245
246
247
                    }
                }
            }

            // they are coalesced, it is valid
            alive.add_temp_in_reg(temp, machine_reg);
        }
248
    }
qinsoon's avatar
qinsoon committed
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305

    // if other temp use the same register, remove the register from their entry
    for entry in alive.find_entries_for_reg_mut(machine_reg) {
        if let Some(other_temp) = entry.get_temp() {
            if is_coalesced(other_temp, temp, reg_coalesced) {
                // do nothing
            } else {
                entry.remove_real(reg);
            }
        }
    }
}

fn add_spill_store(scratch_temp: MuID, source_temp: MuID, spill_loc: P<Value>,
                   reg_spilled: &LinkedHashMap<MuID, P<Value>>,
                   reg_coalesced: &LinkedHashMap<MuID, MuID>,
                   alive: &mut AliveEntries) {
    // add source_temp with mem loc
    alive.add_temp_in_mem(source_temp, spill_loc.clone());

    // add scratch_temp
    alive.add_temp_in_mem(scratch_temp, spill_loc.clone());

    // trying to store into a spill location, it is always valid
    // but if other temp use the same mem location and it is not coalesced temp,
    // we need to delete the mem location from their entry
    for entry in alive.find_entries_for_mem_mut(spill_loc.clone()) {
        if let Some(temp) = entry.get_temp() {
            if is_coalesced(temp, source_temp, reg_coalesced) || is_coalesced(temp, scratch_temp, reg_coalesced) {
                // its okay, coalesced temps can have one spill location
            } else {
                entry.remove_stack_loc(spill_loc.clone())
            }
        }
    }
}

fn add_spill_load(scratch_temp: MuID, source_temp: MuID, spill_loc: P<Value>,
                  reg_spilled: &LinkedHashMap<MuID, P<Value>>,
                  alive: &mut AliveEntries) {
    // verify its correct: the source temp should be alive with the mem location
    if alive.has_entries_for_temp(source_temp) {
        alive.find_entries_for_temp(source_temp).iter().inspect(|entry| {
            if entry.match_stack_loc(spill_loc.clone()) {
                // valid
            } else {
                error!("SourceTemp{} is alive with the following entry, loading it from {} as ScratchTemp{} is not valid", source_temp, spill_loc, scratch_temp);
                debug!("{}", entry);

                panic!("validation failed: load a register from a spilled location that is incorrect");
            }
        });
    } else {
        error!("SourceTemp{} is not alive, loading it from {} as ScratchTemp{} is not valid", scratch_temp, spill_loc, scratch_temp);

        panic!("validation failed: load a register from a spilled location before storing into it")
    }
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
}

#[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());
}