mod.rs 15.2 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

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

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

14 15
const VERIFY_SPILLING : bool = false;

16
#[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
17
#[allow(unreachable_code)]
18 19
pub fn validate_regalloc(cf: &CompiledFunction,
                         reg_assigned: LinkedHashMap<MuID, MuID>,
qinsoon's avatar
qinsoon committed
20
                         spill_scratch_regs: LinkedHashMap<MuID, MuID>)
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
{
    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()));
    }

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

    let mc = cf.mc();

52 53 54 55
    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());
56

57 58 59
    while !work_queue.is_empty() {
        // fetch next block
        let (block, mut alive) = work_queue.pop_front().unwrap();
60

61 62 63 64 65 66 67 68
        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)
        };
69
        let last_inst = mc.get_last_inst(range.end - 1).unwrap();
70 71 72 73
        for i in range {
            mc.trace_inst(i);

            // validate spill
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
            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];
                    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, &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]
103
                    };
104
                    let source_temp = get_source_temp_for_scratch(scratch_temp, &spill_scratch_regs);
105

106 107 108
                    // we add both scratch_temp, and source_temp as alive
                    add_spill_store(scratch_temp, source_temp, spill_loc, &mut alive);
                }
109
            }
qinsoon's avatar
qinsoon committed
110

111 112 113 114
            // 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
115

116 117 118
            // remove registers that die at this instruction from alive entries
            if let Some(kills) = liveness.get_kills(i) {
                for reg in kills.iter() {
119
                    debug!("Temp/Reg{} is killed", reg);
qinsoon's avatar
qinsoon committed
120
                    kill_reg(*reg, &mut alive);
121 122 123 124 125 126 127 128 129 130 131 132 133 134
                }
            }

            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)
135 136 137 138
                    if !mc.is_move(i) {
                        debug!("Temp/Reg{} is not liveout, will be killed", reg_def);
                        kill_reg(reg_def, &mut alive);
                    }
139 140
                }
            }
qinsoon's avatar
qinsoon committed
141

142
            debug!("{}", alive);
143
            debug!("---");
144 145
        }

qinsoon's avatar
qinsoon committed
146 147 148 149 150 151 152 153 154 155
        // 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,
            None => panic!("cannot find liveout for block {}", block)
        };
        alive.preserve_list(liveout);
        debug!("liveout is {:?}", liveout);
        debug!("preserve only entries in liveout, we get:");
        debug!("{}", alive);

156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
        // 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;
176
            }
177 178 179 180
        } else {
            debug!("first time we visited this block, push its successors");
            visited.insert(block.clone(), alive.clone());
            should_push_successors = true;
181 182
        }

183 184 185 186 187 188 189 190
        // 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
191

192 193
                // 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
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221

                // 1st branch
                {
                    let block1 = succeeding_blocks[0].clone();
                    let block1_livein = match mc.get_ir_block_livein(&block1) {
                        Some(livein) => livein,
                        None => panic!("cannot find livein for block {}", block1)
                    };
                    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,
                        None => panic!("cannot find livein for block {}", block2)
                    };
                    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]);
                }
222
            }
223 224
        }

225
        //
226 227 228
    }
}

qinsoon's avatar
qinsoon committed
229 230 231 232 233 234 235
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
    }
}

236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
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
259
        if alive.has_entries_for_temp(temp) {
260
            for entry in alive.find_entries_for_temp(temp).iter() {
qinsoon's avatar
qinsoon committed
261 262 263
                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);
264

qinsoon's avatar
qinsoon committed
265 266
                    panic!("validation failed: temp-reg pair doesnt match")
                }
267
            }
268 269 270 271 272 273 274 275
        } 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
276
fn kill_reg(reg: MuID, alive: &mut AliveEntries) {
277
    if reg < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
278
        if alive.has_entries_for_reg(reg) {
279 280 281 282 283 284 285 286 287
            alive.remove_reg(reg);
        }
    } else {
        let temp = reg;

        alive.remove_temp(temp);
    }
}

288
fn add_def(reg: MuID, reg_assigned: &LinkedHashMap<MuID, MuID>, is_mov: bool, alive: &mut AliveEntries) {
qinsoon's avatar
qinsoon committed
289 290 291
    let machine_reg = get_machine_reg(reg, reg_assigned);
    let temp = reg;

292
    if reg < MACHINE_ID_END {
293 294 295 296
        // 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
297
        if !alive.has_entries_for_reg(reg) {
298 299
            // add new machine register
            alive.new_alive_reg(reg);
qinsoon's avatar
qinsoon committed
300 301
        } else if !alive.find_entries_for_reg(reg).iter().any(|entry| entry.has_temp()) {
            // overwrite the value that is not used
302
        } else {
303
            for entry in alive.find_entries_for_reg(reg).iter() {
qinsoon's avatar
qinsoon committed
304 305
                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);
306
            }
307 308

            panic!("validation failed: define a register that is already alive (value overwritten)");
309 310
        }
    } else {
qinsoon's avatar
qinsoon committed
311
        if !alive.has_entries_for_reg(machine_reg) {
312 313 314 315 316
            // 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
317 318 319 320
                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);
321
                    } else {
qinsoon's avatar
qinsoon committed
322 323
                        // if the register is holding a temporary, it needs to be coalesced with new temp
                        let old_temp: MuID = entry.get_temp().unwrap();
324

325 326
                        if old_temp == temp {
                            // overwrite value, safe
qinsoon's avatar
qinsoon committed
327
                        } else {
328
                            if is_mov {
329
                                debug!("Temp{} and Temp{} is using the same Register{}, possibly coalesced", temp, old_temp, machine_reg);
330 331 332 333 334 335
                            } 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
336
                        }
337 338 339 340 341 342 343
                    }
                }
            }

            // they are coalesced, it is valid
            alive.add_temp_in_reg(temp, machine_reg);
        }
344
    }
qinsoon's avatar
qinsoon committed
345 346 347 348 349 350 351 352 353 354 355
}

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

356 357
fn validate_spill_load(scratch_temp: MuID, source_temp: MuID, spill_loc: P<Value>,
                       alive: &mut AliveEntries) {
qinsoon's avatar
qinsoon committed
358 359
    // verify its correct: the source temp should be alive with the mem location
    if alive.has_entries_for_temp(source_temp) {
360
        for entry in alive.find_entries_for_temp(source_temp).iter() {
qinsoon's avatar
qinsoon committed
361 362 363 364 365 366 367 368
            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");
            }
369
        }
qinsoon's avatar
qinsoon committed
370 371 372 373 374
    } 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")
    }
375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
}

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