mod.rs 2.81 KB
Newer Older
qinsoon's avatar
qinsoon committed
1 2
#![allow(dead_code)]

3
use compiler;
4
use compiler::CompilerPass;
5
use compiler::PassExecutionResult;
6
use ast::ir::*;
qinsoon's avatar
qinsoon committed
7
use vm::VM;
8

qinsoon's avatar
qinsoon committed
9 10
use compiler::backend::init_machine_regs_for_func;

11
mod graph_coloring;
12

13
pub enum RegAllocFailure {
14 15 16
    FailedForSpilling,
}

17
pub struct RegisterAllocation {
18
    name: &'static str,
19 20 21
}

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

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

49
        let spills = coloring.spills();
50 51
        
        if !spills.is_empty() {
52 53 54
            unimplemented!();

            // return Err(RegAllocFailure::FailedForSpilling);
55 56 57 58 59 60 61 62
        }
        
        // 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
63
            if temp < MACHINE_ID_END {
64 65 66 67 68 69
                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
70
                cf.mc_mut().replace_reg(temp, machine_reg);
71 72
                
                cf.temps.insert(temp, machine_reg);
73 74 75
            }
        }
        
qinsoon's avatar
qinsoon committed
76
        cf.mc().trace_mc();
77
        
78
        Ok(())
79 80 81 82 83 84 85 86
    }    
}

impl CompilerPass for RegisterAllocation {
    fn name(&self) -> &'static str {
        self.name
    }
    
qinsoon's avatar
qinsoon committed
87
    fn execute(&mut self, vm: &VM, func: &mut MuFunctionVersion) -> PassExecutionResult {
qinsoon's avatar
qinsoon committed
88
        debug!("---CompilerPass {} for {}---", self.name(), func);
89 90 91 92 93 94
        
        match self.coloring(vm, func) {
            // skip slow path
            Ok(_) => PassExecutionResult::ProceedTo(compiler::PASS_PEEPHOLE),

            // go back to instruction selection for spilled operands
95
            Err(RegAllocFailure::FailedForSpilling) => PassExecutionResult::GoBackTo(compiler::PASS_INST_SEL),
96
        }
97
    }
98
}