GitLab will continue to be upgraded from 11.4.5-ce.0 on November 25th 2019 at 4.00pm (AEDT) to 5.00pm (AEDT) due to Critical Security Patch Availability. During the update, GitLab and Mattermost services will not be available.

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
}