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

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

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

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

    let mc = cf.mc();

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

52
        if mc.is_jmp(i).is_some() {
qinsoon's avatar
qinsoon committed
53
            // we need to do flow-sensitive analysis
54
55
56
            unimplemented!();
        }

qinsoon's avatar
qinsoon committed
57
58
59
        // validate spill
        if let Some(spill_loc) = mc.is_spill_load(i) {
            // spill load is a move from spill location (mem) to temp
60

qinsoon's avatar
qinsoon committed
61
62
63
64
            // 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);

65
66
            // we check if source_temp are alive, and if it is alive in the designated location
            validate_spill_load(scratch_temp, source_temp, spill_loc, &reg_spilled, &mut alive);
qinsoon's avatar
qinsoon committed
67
68
        } else if let Some(spill_loc) = mc.is_spill_store(i) {
            // spill store is a move from scratch temp to mem
69

qinsoon's avatar
qinsoon committed
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
            // 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);

87
88
            // we add both scratch_temp, and source_temp as alive
            add_spill_store(scratch_temp, source_temp, spill_loc, &reg_spilled, &mut alive);
qinsoon's avatar
qinsoon committed
89
90
91
        }

        // validate uses of registers
92
93
94
95
        for reg_use in mc.get_inst_reg_uses(i) {
            validate_use(reg_use, &reg_assigned, &alive);
        }

qinsoon's avatar
qinsoon committed
96
        // remove registers that die at this instruction from alive entries
97
98
        if let Some(kills) = liveness.get_kills(i) {
            for reg in kills.iter() {
99
                kill_reg(*reg, &reg_assigned, &mut alive);
100
101
102
103
            }
        }

        for reg_def in mc.get_inst_reg_defines(i) {
104
105
106
107
            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) {
108
109
110
                // add a define
                // modify existing alive entries (e.g. kill existing registers)
                add_def(reg_def, &reg_assigned, mc.is_move(i), &mut alive);
111
            } else {
112
113
                // we need to kill the reg, so that other temps cannot use it
                // (its value has been defined)
114
115
                kill_reg(reg_def, &reg_assigned, &mut alive);
            }
116
117
118
119
120
121
122
        }

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

qinsoon's avatar
qinsoon committed
123
124
125
126
127
128
129
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
    }
}

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

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

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

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

        alive.remove_temp(temp);
    }
}

182
fn add_def(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, is_mov: bool, alive: &mut AliveEntries) {
qinsoon's avatar
qinsoon committed
183
184
185
    let machine_reg = get_machine_reg(reg, reg_assigned);
    let temp = reg;

186
    if reg < MACHINE_ID_END {
187
188
189
190
        // 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
191
        if !alive.has_entries_for_reg(reg) {
192
193
            // add new machine register
            alive.new_alive_reg(reg);
qinsoon's avatar
qinsoon committed
194
195
        } else if !alive.find_entries_for_reg(reg).iter().any(|entry| entry.has_temp()) {
            // overwrite the value that is not used
196
        } else {
197
            for entry in alive.find_entries_for_reg(reg).iter() {
qinsoon's avatar
qinsoon committed
198
199
                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);
200
            }
201
202

            panic!("validation failed: define a register that is already alive (value overwritten)");
203
204
        }
    } else {
qinsoon's avatar
qinsoon committed
205
        if !alive.has_entries_for_reg(machine_reg) {
206
207
208
209
210
            // 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
211
212
213
214
                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);
215
                    } else {
qinsoon's avatar
qinsoon committed
216
217
                        // if the register is holding a temporary, it needs to be coalesced with new temp
                        let old_temp: MuID = entry.get_temp().unwrap();
218

219
220
                        if old_temp == temp {
                            // overwrite value, safe
qinsoon's avatar
qinsoon committed
221
                        } else {
222
223
224
225
226
227
228
229
                            if is_mov {
                                warn!("Temp{} and Temp{} is using the same Register{}, possibly coalesced", temp, old_temp, machine_reg);
                            } else {
                                // trying to overwrite another value, error
                                error!("Temp{} and Temp{} try use the same Register{}", temp, old_temp, machine_reg);

                                panic!("validation failed: define a register that is already alive");
                            }
qinsoon's avatar
qinsoon committed
230
                        }
231
232
233
234
235
236
237
                    }
                }
            }

            // they are coalesced, it is valid
            alive.add_temp_in_reg(temp, machine_reg);
        }
238
    }
qinsoon's avatar
qinsoon committed
239
240
241
242
243
244
245
246
247
248
249
250
}

fn add_spill_store(scratch_temp: MuID, source_temp: MuID, spill_loc: P<Value>,
                   reg_spilled: &LinkedHashMap<MuID, P<Value>>,
                   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());
}

251
252
253
fn validate_spill_load(scratch_temp: MuID, source_temp: MuID, spill_loc: P<Value>,
                       reg_spilled: &LinkedHashMap<MuID, P<Value>>,
                       alive: &mut AliveEntries) {
qinsoon's avatar
qinsoon committed
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
    // 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")
    }
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
}

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