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

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

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
17
18
                         reg_spilled: LinkedHashMap<MuID, P<Value>>,
                         spill_scratch_regs: LinkedHashMap<MuID, MuID>)
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
{
    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()));
    }

45
    debug!("---alive entries in the beginning---");
46
47
48
49
    debug!("{}", alive);

    let mc = cf.mc();

50
51
52
53
    let mut work_queue : LinkedHashMap<MuName, AliveEntries> = LinkedHashMap::new();
    let mut visited    : LinkedHashMap<MuName, AliveEntries> = LinkedHashMap::new();
    // push entry block
    work_queue.insert(PROLOGUE_BLOCK_NAME.to_string(), alive.clone());
54

55
56
57
    while !work_queue.is_empty() {
        // fetch next block
        let (block, mut alive) = work_queue.pop_front().unwrap();
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
        debug!("---working on block {}---", block);
        debug!("{}", alive);

        // check inst sequentially
        let range = match mc.get_block_range(&block) {
            Some(range) => range,
            None => panic!("cannot find range for block {}", block)
        };
        let last_inst = range.end - 1;
        for i in range {
            mc.trace_inst(i);

            // 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);

                // 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);
            } 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]
qinsoon's avatar
qinsoon committed
98
                };
99
                let source_temp = get_source_temp_for_scratch(scratch_temp, &spill_scratch_regs);
qinsoon's avatar
qinsoon committed
100

101
102
103
                // 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
104

105
106
107
108
            // validate uses of registers
            for reg_use in mc.get_inst_reg_uses(i) {
                validate_use(reg_use, &reg_assigned, &alive);
            }
qinsoon's avatar
qinsoon committed
109

110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
            // remove registers that die at this instruction from alive entries
            if let Some(kills) = liveness.get_kills(i) {
                for reg in kills.iter() {
                    kill_reg(*reg, &reg_assigned, &mut alive);
                }
            }

            for reg_def in mc.get_inst_reg_defines(i) {
                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 a define
                    // modify existing alive entries (e.g. kill existing registers)
                    add_def(reg_def, &reg_assigned, mc.is_move(i), &mut alive);
                } else {
                    // we need to kill the reg, so that other temps cannot use it
                    // (its value has been defined)
                    kill_reg(reg_def, &reg_assigned, &mut alive);
                }
            }
qinsoon's avatar
qinsoon committed
131

132
133
            debug!("{}", alive);
            trace!("---");
134
135
        }

136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
        // find succeeding blocks
        let succeeding_blocks : Vec<MuName> = mc.get_succs(last_inst).iter()
                                              .map(|x| match mc.is_label(*x - 1) {
                                                  Some(label) => label,
                                                  None => panic!("cannot find label for inst {}", *x - 1)
                                              }).collect();

        // 1) if we have visited this block before, we need to merge (intersect alive entries)
        // alive entries is changed, we need to push successors
        // 2) if this is our first time visit the block, we push successors
        let mut should_push_successors = false;

        if visited.contains_key(&block) {
            // if current block exists in visited, intersect with current
            let mut old = visited.get_mut(&block).unwrap();
            let changed = old.intersect(&alive);

            if changed {
                debug!("we have visted this block before, but intersection made changes. we need to push its sucessors again. ");
                should_push_successors = true;
156
            }
157
158
159
160
        } else {
            debug!("first time we visited this block, push its successors");
            visited.insert(block.clone(), alive.clone());
            should_push_successors = true;
161
162
        }

163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
        // push successors to work list
        if should_push_successors {
            if succeeding_blocks.len() == 1 {
                // nothing special, just push next block to work list
                work_queue.insert(succeeding_blocks[0].clone(), alive.clone());
                debug!("push block {} to work list", succeeding_blocks[0]);
            } else if succeeding_blocks.len() == 2 {
                // conditional branch
                // FIXME: need to prune alive entries based on live in
                // it is possible that a variable is alive at the end of a BB, and used
                // only in one of its successors
                work_queue.insert(succeeding_blocks[0].clone(), alive.clone());
                work_queue.insert(succeeding_blocks[1].clone(), alive.clone());
                debug!("push block {} to work list", succeeding_blocks[0]);
                debug!("push block {} to work list", succeeding_blocks[1]);
178
            }
179
180
        }

181
        //
182
183
184
    }
}

qinsoon's avatar
qinsoon committed
185
186
187
188
189
190
191
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
    }
}

192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
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
215
        if alive.has_entries_for_temp(temp) {
216
            for entry in alive.find_entries_for_temp(temp).iter() {
qinsoon's avatar
qinsoon committed
217
218
219
                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);
220

qinsoon's avatar
qinsoon committed
221
222
                    panic!("validation failed: temp-reg pair doesnt match")
                }
223
            }
224
225
226
227
228
229
230
231
        } else {
            error!("Temp{} is not alive at this point. ", temp);

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

232
fn kill_reg(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, alive: &mut AliveEntries) {
233
    if reg < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
234
        if alive.has_entries_for_reg(reg) {
235
236
237
238
239
240
241
242
243
            alive.remove_reg(reg);
        }
    } else {
        let temp = reg;

        alive.remove_temp(temp);
    }
}

244
fn add_def(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, is_mov: bool, alive: &mut AliveEntries) {
qinsoon's avatar
qinsoon committed
245
246
247
    let machine_reg = get_machine_reg(reg, reg_assigned);
    let temp = reg;

248
    if reg < MACHINE_ID_END {
249
250
251
252
        // 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
253
        if !alive.has_entries_for_reg(reg) {
254
255
            // add new machine register
            alive.new_alive_reg(reg);
qinsoon's avatar
qinsoon committed
256
257
        } else if !alive.find_entries_for_reg(reg).iter().any(|entry| entry.has_temp()) {
            // overwrite the value that is not used
258
        } else {
259
            for entry in alive.find_entries_for_reg(reg).iter() {
qinsoon's avatar
qinsoon committed
260
261
                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);
262
            }
263
264

            panic!("validation failed: define a register that is already alive (value overwritten)");
265
266
        }
    } else {
qinsoon's avatar
qinsoon committed
267
        if !alive.has_entries_for_reg(machine_reg) {
268
269
270
271
272
            // 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
273
274
275
276
                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);
277
                    } else {
qinsoon's avatar
qinsoon committed
278
279
                        // if the register is holding a temporary, it needs to be coalesced with new temp
                        let old_temp: MuID = entry.get_temp().unwrap();
280

281
282
                        if old_temp == temp {
                            // overwrite value, safe
qinsoon's avatar
qinsoon committed
283
                        } else {
284
285
286
287
288
289
290
291
                            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
292
                        }
293
294
295
296
297
298
299
                    }
                }
            }

            // they are coalesced, it is valid
            alive.add_temp_in_reg(temp, machine_reg);
        }
300
    }
qinsoon's avatar
qinsoon committed
301
302
303
304
305
306
307
308
309
310
311
312
}

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

313
314
315
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
316
317
    // verify its correct: the source temp should be alive with the mem location
    if alive.has_entries_for_temp(source_temp) {
318
        for entry in alive.find_entries_for_temp(source_temp).iter() {
qinsoon's avatar
qinsoon committed
319
320
321
322
323
324
325
326
            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");
            }
327
        }
qinsoon's avatar
qinsoon committed
328
329
330
331
332
    } 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")
    }
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
}

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