mod.rs 3.48 KB
Newer Older
1 2
#![allow(dead_code)]

qinsoon's avatar
qinsoon committed
3 4 5
use ast::ir::*;
use ast::ptr::*;
use vm::VM;
6
use compiler;
7
use compiler::CompilerPass;
qinsoon's avatar
qinsoon committed
8
use compiler::machine_code::CompiledFunction;
9
use compiler::PassExecutionResult;
10
use compiler::backend::init_machine_regs_for_func;
11
use compiler::backend;
12

qinsoon's avatar
qinsoon committed
13 14
use std::collections::HashMap;

15
mod graph_coloring;
16

17
pub enum RegAllocFailure {
18 19 20
    FailedForSpilling,
}

21
pub struct RegisterAllocation {
22
    name: &'static str,
23 24 25
}

impl RegisterAllocation {
26
    pub fn new() -> RegisterAllocation {
27
        RegisterAllocation {
28
            name: "Register Allcoation",
29 30 31 32
        }
    }
    
    #[allow(unused_variables)]
33
    // returns true if we spill registers (which requires another instruction selection)
34
    fn coloring(&mut self, vm: &VM, func: &mut MuFunctionVersion) -> Result<(), RegAllocFailure> {
qinsoon's avatar
qinsoon committed
35
        let compiled_funcs = vm.compiled_funcs().read().unwrap();
qinsoon's avatar
qinsoon committed
36
        let mut cf = compiled_funcs.get(&func.id()).unwrap().write().unwrap();
37
        
qinsoon's avatar
qinsoon committed
38
        cf.mc().trace_mc();
39
        
40 41 42
        // initialize machine registers for the function context
        init_machine_regs_for_func(&mut func.context);
        
43
        let liveness = graph_coloring::build_inteference_graph(&mut cf, func);
44
        liveness.print();
45 46 47 48 49 50 51 52

        let coloring = match graph_coloring::GraphColoring::start(liveness) {
            Ok(coloring) => coloring,
            Err(err) => {
                return Err(err);
            }
        };

53
        let spills = coloring.spills();
54 55
        
        if !spills.is_empty() {
qinsoon's avatar
qinsoon committed
56 57 58 59 60 61 62 63 64
            let mut spilled_mem = HashMap::new();

            // allocating frame slots for every spilled temp
            for reg_id in spills.iter() {
                let ssa_entry = match func.context.get_value(*reg_id) {
                    Some(entry) => entry,
                    None => panic!("The spilled register {} is not in func context", reg_id)
                };
                let mem = cf.frame.alloc_slot_for_spilling(ssa_entry.value().clone(), vm);
65

qinsoon's avatar
qinsoon committed
66 67 68
                spilled_mem.insert(*reg_id, mem);
            }

69
            backend::spill_rewrite(&spilled_mem, func, &mut cf, vm);
qinsoon's avatar
qinsoon committed
70 71

            return Err(RegAllocFailure::FailedForSpilling);
72 73 74 75 76 77 78 79
        }
        
        // replace regs
        trace!("Replacing Registers...");
        for node in coloring.ig.nodes() {
            let temp = coloring.ig.get_temp_of(node);
            
            // skip machine registers
qinsoon's avatar
qinsoon committed
80
            if temp < MACHINE_ID_END {
81 82 83 84 85 86
                continue;
            } else {
                let alias = coloring.get_alias(node);
                let machine_reg = coloring.ig.get_color_of(alias).unwrap();
                
                trace!("replacing {} with {}", temp, machine_reg);
qinsoon's avatar
qinsoon committed
87
                cf.mc_mut().replace_reg(temp, machine_reg);
88 89
                
                cf.temps.insert(temp, machine_reg);
90 91 92
            }
        }
        
qinsoon's avatar
qinsoon committed
93
        cf.mc().trace_mc();
94
        
95
        Ok(())
qinsoon's avatar
qinsoon committed
96
    }
97 98 99 100 101 102 103
}

impl CompilerPass for RegisterAllocation {
    fn name(&self) -> &'static str {
        self.name
    }
    
qinsoon's avatar
qinsoon committed
104
    fn execute(&mut self, vm: &VM, func: &mut MuFunctionVersion) -> PassExecutionResult {
qinsoon's avatar
qinsoon committed
105
        debug!("---CompilerPass {} for {}---", self.name(), func);
106 107 108 109 110 111
        
        match self.coloring(vm, func) {
            // skip slow path
            Ok(_) => PassExecutionResult::ProceedTo(compiler::PASS_PEEPHOLE),

            // go back to instruction selection for spilled operands
112
            Err(RegAllocFailure::FailedForSpilling) => PassExecutionResult::GoBackTo(compiler::PASS_INST_SEL),
113
        }
114
    }
115
}