GitLab will be upgraded on 31 Jan 2023 from 2.00 pm (AEDT) to 3.00 pm (AEDT). During the update, GitLab and Mattermost services will not be available. If you have any concerns with this, please talk to us at N110 (b) CSIT building.

mod.rs 17.9 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3
4
5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9
10
11
12
13
14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

qinsoon's avatar
qinsoon committed
15
16
17
18
19
20
21
//! This module is for validating register allocation
//! However it is disabled for now due to bugs. It is uncertain
//! how important this is to Zebu. More description and discussion
//! can be found as Issue #19.

#![allow(dead_code)]

22
23
24
25
26
use utils::LinkedHashMap;
use ast::ir::*;
use ast::ptr::*;
use compiler::machine_code::CompiledFunction;
use compiler::backend::get_color_for_precolored as alias;
27
use compiler::PROLOGUE_BLOCK_NAME;
28
29
30
31
32
33
34

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

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

qinsoon's avatar
qinsoon committed
35
const VERIFY_SPILLING: bool = false;
36

37
#[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
38
#[allow(unreachable_code)]
qinsoon's avatar
qinsoon committed
39
40
41
pub fn validate_regalloc(
    cf: &CompiledFunction,
    reg_assigned: LinkedHashMap<MuID, MuID>,
42
    spill_scratch_regs: LinkedHashMap<MuID, MuID>
qinsoon's avatar
qinsoon committed
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
    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()));
    }

69
    debug!("---alive entries in the beginning---");
70
71
72
73
    debug!("{}", alive);

    let mc = cf.mc();

qinsoon's avatar
qinsoon committed
74
75
    let mut work_queue: LinkedHashMap<MuName, AliveEntries> = LinkedHashMap::new();
    let mut visited: LinkedHashMap<MuName, AliveEntries> = LinkedHashMap::new();
76
    // push entry block
77
    work_queue.insert(Arc::new(PROLOGUE_BLOCK_NAME.to_string()), alive.clone());
78

79
80
81
    while !work_queue.is_empty() {
        // fetch next block
        let (block, mut alive) = work_queue.pop_front().unwrap();
82

83
84
85
86
87
88
        debug!("---working on block {}---", block);
        debug!("{}", alive);

        // check inst sequentially
        let range = match mc.get_block_range(&block) {
            Some(range) => range,
89
            None => panic!("cannot find range for block {}", block)
90
        };
91
        let last_inst = mc.get_last_inst(range.end - 1).unwrap();
92
93
94
95
        for i in range {
            mc.trace_inst(i);

            // validate spill
96
97
98
99
100
101
102
103
            if VERIFY_SPILLING {
                panic!("the code doesnt work");

                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];
qinsoon's avatar
qinsoon committed
104
105
                    let source_temp =
                        get_source_temp_for_scratch(scratch_temp, &spill_scratch_regs);
106

qinsoon's avatar
qinsoon committed
107
108
                    // we check if source_temp are alive, and if it is alive in the
                    // designated location
109
110
111
112
113
114
115
116
117
118
119
120
121
                    validate_spill_load(scratch_temp, source_temp, spill_loc, &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)
                            }
qinsoon's avatar
qinsoon committed
122
                        }
123
124
125
126

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

                        use_temps[0]
127
                    };
qinsoon's avatar
qinsoon committed
128
129
                    let source_temp =
                        get_source_temp_for_scratch(scratch_temp, &spill_scratch_regs);
130

131
132
133
                    // we add both scratch_temp, and source_temp as alive
                    add_spill_store(scratch_temp, source_temp, spill_loc, &mut alive);
                }
134
            }
qinsoon's avatar
qinsoon committed
135

136
137
138
139
            // 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
140

141
142
143
            // remove registers that die at this instruction from alive entries
            if let Some(kills) = liveness.get_kills(i) {
                for reg in kills.iter() {
144
                    debug!("Temp/Reg{} is killed", reg);
qinsoon's avatar
qinsoon committed
145
                    kill_reg(*reg, &mut alive);
146
147
148
149
150
151
152
153
154
155
156
157
158
159
                }
            }

            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)
160
161
162
163
                    if !mc.is_move(i) {
                        debug!("Temp/Reg{} is not liveout, will be killed", reg_def);
                        kill_reg(reg_def, &mut alive);
                    }
164
165
                }
            }
qinsoon's avatar
qinsoon committed
166

167
            debug!("{}", alive);
qinsoon's avatar
qinsoon committed
168
            debug!("---");
169
170
        }

qinsoon's avatar
qinsoon committed
171
172
173
        // find liveout of the block, and only preserve what is in the liveout
        let liveout = match mc.get_ir_block_liveout(&block) {
            Some(liveout) => liveout,
174
            None => panic!("cannot find liveout for block {}", block)
qinsoon's avatar
qinsoon committed
175
176
177
178
179
180
        };
        alive.preserve_list(liveout);
        debug!("liveout is {:?}", liveout);
        debug!("preserve only entries in liveout, we get:");
        debug!("{}", alive);

181
        // find succeeding blocks
qinsoon's avatar
qinsoon committed
182
183
184
185
        let succeeding_blocks: Vec<MuName> = mc.get_succs(last_inst)
            .iter()
            .map(|x| match mc.is_label(*x - 1) {
                Some(label) => label,
186
                None => panic!("cannot find label for inst {}", *x - 1)
qinsoon's avatar
qinsoon committed
187
188
            })
            .collect();
189
190
191
192
193
194
195
196
197
198
199
200

        // 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 {
qinsoon's avatar
qinsoon committed
201
202
203
204
                debug!(
                    "we have visted this block before, but intersection made changes. \
                     we need to push its sucessors again. "
                );
205
                should_push_successors = true;
206
            }
207
208
209
210
        } else {
            debug!("first time we visited this block, push its successors");
            visited.insert(block.clone(), alive.clone());
            should_push_successors = true;
211
212
        }

213
214
215
216
217
218
219
220
        // 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
qinsoon's avatar
qinsoon committed
221

222
223
                // it is possible that a variable is alive at the end of a BB, and used
                // only in one of its successors
qinsoon's avatar
qinsoon committed
224
225
226
227
228
229

                // 1st branch
                {
                    let block1 = succeeding_blocks[0].clone();
                    let block1_livein = match mc.get_ir_block_livein(&block1) {
                        Some(livein) => livein,
230
                        None => panic!("cannot find livein for block {}", block1)
qinsoon's avatar
qinsoon committed
231
232
233
234
235
236
237
238
239
240
241
242
243
                    };
                    let mut block1_alive = alive.clone();
                    block1_alive.preserve_list(block1_livein);

                    work_queue.insert(block1, block1_alive);
                    debug!("push block {} to work list", succeeding_blocks[0]);
                }

                // 2nd branch
                {
                    let block2 = succeeding_blocks[1].clone();
                    let block2_livein = match mc.get_ir_block_livein(&block2) {
                        Some(livein) => livein,
244
                        None => panic!("cannot find livein for block {}", block2)
qinsoon's avatar
qinsoon committed
245
246
247
248
249
250
251
                    };
                    let mut block2_alive = alive.clone();
                    block2_alive.preserve_list(block2_livein);

                    work_queue.insert(block2, block2_alive);
                    debug!("push block {} to work list", succeeding_blocks[1]);
                }
252
            }
253
254
        }

255
        //
256
257
258
    }
}

qinsoon's avatar
qinsoon committed
259
260
fn get_source_temp_for_scratch(
    scratch: MuID,
261
    spill_scratch_temps: &LinkedHashMap<MuID, MuID>
qinsoon's avatar
qinsoon committed
262
) -> MuID {
qinsoon's avatar
qinsoon committed
263
264
    match spill_scratch_temps.get(&scratch) {
        Some(src) => get_source_temp_for_scratch(*src, spill_scratch_temps),
265
        None => scratch
qinsoon's avatar
qinsoon committed
266
267
268
    }
}

269
270
271
272
273
274
275
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,
276
            None => panic!("Temp {} is not assigned to any machine register", reg)
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
        }
    }
}

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
292
        if alive.has_entries_for_temp(temp) {
293
            for entry in alive.find_entries_for_temp(temp).iter() {
qinsoon's avatar
qinsoon committed
294
                if !entry.match_reg(machine_reg) {
qinsoon's avatar
qinsoon committed
295
296
297
298
299
                    error!(
                        "Temp{}/MachineReg{} does not match at this point. ",
                        temp,
                        machine_reg
                    );
qinsoon's avatar
qinsoon committed
300
                    error!("Temp{} is assigned as {}", temp, entry);
301

qinsoon's avatar
qinsoon committed
302
303
                    panic!("validation failed: temp-reg pair doesnt match")
                }
304
            }
305
306
307
308
309
310
311
312
        } else {
            error!("Temp{} is not alive at this point. ", temp);

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

qinsoon's avatar
qinsoon committed
313
fn kill_reg(reg: MuID, alive: &mut AliveEntries) {
314
    if reg < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
315
        if alive.has_entries_for_reg(reg) {
316
317
318
319
320
321
322
323
324
            alive.remove_reg(reg);
        }
    } else {
        let temp = reg;

        alive.remove_temp(temp);
    }
}

qinsoon's avatar
qinsoon committed
325
326
327
328
fn add_def(
    reg: MuID,
    reg_assigned: &LinkedHashMap<MuID, MuID>,
    is_mov: bool,
329
    alive: &mut AliveEntries
qinsoon's avatar
qinsoon committed
330
) {
qinsoon's avatar
qinsoon committed
331
332
333
    let machine_reg = get_machine_reg(reg, reg_assigned);
    let temp = reg;

334
    if reg < MACHINE_ID_END {
335
336
337
338
        // 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
339
        if !alive.has_entries_for_reg(reg) {
340
341
            // add new machine register
            alive.new_alive_reg(reg);
qinsoon's avatar
qinsoon committed
342
343
344
345
346
        } else if !alive
                   .find_entries_for_reg(reg)
                   .iter()
                   .any(|entry| entry.has_temp())
        {
qinsoon's avatar
qinsoon committed
347
            // overwrite the value that is not used
348
        } else {
349
            for entry in alive.find_entries_for_reg(reg).iter() {
qinsoon's avatar
qinsoon committed
350
                let old_temp = entry.get_temp().unwrap();
qinsoon's avatar
qinsoon committed
351
352
353
354
355
356
357
                error!(
                    "Register{}/Temp{} is alive at this point, \
                     defining a new value to Register{} is incorrect",
                    reg,
                    old_temp,
                    reg
                );
358
            }
359

qinsoon's avatar
qinsoon committed
360
361
362
            panic!(
                "validation failed: define a register that is already alive (value overwritten)"
            );
363
364
        }
    } else {
qinsoon's avatar
qinsoon committed
365
        if !alive.has_entries_for_reg(machine_reg) {
366
367
368
369
370
            // 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
371
372
373
374
                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);
375
                    } else {
qinsoon's avatar
qinsoon committed
376
377
                        // if the register is holding a temporary,
                        // it needs to be coalesced with new temp
qinsoon's avatar
qinsoon committed
378
                        let old_temp: MuID = entry.get_temp().unwrap();
379

380
381
                        if old_temp == temp {
                            // overwrite value, safe
qinsoon's avatar
qinsoon committed
382
                        } else {
383
                            if is_mov {
qinsoon's avatar
qinsoon committed
384
385
386
387
388
389
390
                                debug!(
                                    "Temp{} and Temp{} is using the same Register{}, \
                                     possibly coalesced",
                                    temp,
                                    old_temp,
                                    machine_reg
                                );
391
392
                            } else {
                                // trying to overwrite another value, error
qinsoon's avatar
qinsoon committed
393
394
395
396
397
398
399
400
401
402
                                error!(
                                    "Temp{} and Temp{} try use the same Register{}",
                                    temp,
                                    old_temp,
                                    machine_reg
                                );

                                panic!(
                                    "validation failed: define a register that is already alive"
                                );
403
                            }
qinsoon's avatar
qinsoon committed
404
                        }
405
406
407
408
409
410
411
                    }
                }
            }

            // they are coalesced, it is valid
            alive.add_temp_in_reg(temp, machine_reg);
        }
412
    }
qinsoon's avatar
qinsoon committed
413
414
}

qinsoon's avatar
qinsoon committed
415
416
417
418
fn add_spill_store(
    scratch_temp: MuID,
    source_temp: MuID,
    spill_loc: P<Value>,
419
    alive: &mut AliveEntries
qinsoon's avatar
qinsoon committed
420
) {
qinsoon's avatar
qinsoon committed
421
422
423
424
425
426
427
    // 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());
}

qinsoon's avatar
qinsoon committed
428
429
430
431
fn validate_spill_load(
    scratch_temp: MuID,
    source_temp: MuID,
    spill_loc: P<Value>,
432
    alive: &mut AliveEntries
qinsoon's avatar
qinsoon committed
433
) {
qinsoon's avatar
qinsoon committed
434
435
    // verify its correct: the source temp should be alive with the mem location
    if alive.has_entries_for_temp(source_temp) {
436
        for entry in alive.find_entries_for_temp(source_temp).iter() {
qinsoon's avatar
qinsoon committed
437
438
439
            if entry.match_stack_loc(spill_loc.clone()) {
                // valid
            } else {
qinsoon's avatar
qinsoon committed
440
441
442
443
444
445
446
                error!(
                    "SourceTemp{} is alive with the following entry, loading it \
                     from {} as ScratchTemp{} is not valid",
                    source_temp,
                    spill_loc,
                    scratch_temp
                );
qinsoon's avatar
qinsoon committed
447
448
                debug!("{}", entry);

qinsoon's avatar
qinsoon committed
449
450
451
                panic!(
                    "validation failed: load a register from a spilled location that is incorrect"
                );
qinsoon's avatar
qinsoon committed
452
            }
453
        }
qinsoon's avatar
qinsoon committed
454
    } else {
qinsoon's avatar
qinsoon committed
455
456
457
458
459
460
        error!(
            "SourceTemp{} is not alive, loading it from {} as ScratchTemp{} is not valid",
            scratch_temp,
            spill_loc,
            scratch_temp
        );
qinsoon's avatar
qinsoon committed
461
462
463

        panic!("validation failed: load a register from a spilled location before storing into it")
    }
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
}

#[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());
481
482
483
484
485
486
}

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

qinsoon's avatar
qinsoon committed
487
488
    // the instruction pointer, stack pointer, link register and frame pointer
    // always have valid values
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
    alive.new_alive_reg(aarch64::SP.id());
    alive.new_alive_reg(aarch64::LR.id());
    alive.new_alive_reg(aarch64::FP.id());

    // callee saved regs are alive
    alive.new_alive_reg(aarch64::X28.id());
    alive.new_alive_reg(aarch64::X27.id());
    alive.new_alive_reg(aarch64::X26.id());
    alive.new_alive_reg(aarch64::X25.id());
    alive.new_alive_reg(aarch64::X24.id());
    alive.new_alive_reg(aarch64::X23.id());
    alive.new_alive_reg(aarch64::X22.id());
    alive.new_alive_reg(aarch64::X21.id());
    alive.new_alive_reg(aarch64::X20.id());
    alive.new_alive_reg(aarch64::X19.id());

    // platform register, reserved (never use it)
    alive.new_alive_reg(aarch64::PR.id());
qinsoon's avatar
qinsoon committed
507
}