WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.6% of users enabled 2FA.

mod.rs 4.02 KB
Newer Older
1 2
extern crate petgraph;

3 4 5 6
mod liveness;
mod coloring;

pub use compiler::backend::reg_alloc::graph_coloring::liveness::InterferenceGraph;
7 8
//pub use compiler::backend::reg_alloc::graph_coloring::liveness::build as build_inteference_graph;
pub use compiler::backend::reg_alloc::graph_coloring::liveness::build_chaitin_briggs as build_inteference_graph;
9
pub use compiler::backend::reg_alloc::graph_coloring::coloring::GraphColoring;
qinsoon's avatar
qinsoon committed
10 11 12 13

use ast::ir::*;
use vm::VM;
use compiler::CompilerPass;
qinsoon's avatar
qinsoon committed
14
use compiler::backend::is_callee_saved;
qinsoon's avatar
qinsoon committed
15
use compiler::backend::init_machine_regs_for_func;
qinsoon's avatar
qinsoon committed
16
use utils::POINTER_SIZE;
qinsoon's avatar
qinsoon committed
17 18 19 20 21 22 23 24 25 26 27 28 29 30
use std::any::Any;

pub struct RegisterAllocation {
    name: &'static str,
}

impl RegisterAllocation {
    pub fn new() -> RegisterAllocation {
        RegisterAllocation {
            name: "Register Allocation",
        }
    }

    #[allow(unused_variables)]
31
    fn coloring(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
32 33 34 35 36 37
        let compiled_funcs = vm.compiled_funcs().read().unwrap();
        let mut cf = compiled_funcs.get(&func.id()).unwrap().write().unwrap();

        // initialize machine registers for the function context
        init_machine_regs_for_func(&mut func.context);

38
        let coloring = GraphColoring::start(func, &mut cf, vm);
qinsoon's avatar
qinsoon committed
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

        // replace regs
        trace!("Replacing Registers...");
        for node in coloring.ig.nodes() {
            let temp = coloring.ig.get_temp_of(node);

            // skip machine registers
            if temp < MACHINE_ID_END {
                continue;
            } else {
                let alias = coloring.get_alias(node);
                let machine_reg = match coloring.ig.get_color_of(alias) {
                    Some(reg) => reg,
                    None => panic!(
                        "Reg{}/{:?} (aliased as Reg{}/{:?}) is not assigned with a color",
                        coloring.ig.get_temp_of(node), node,
                        coloring.ig.get_temp_of(alias), alias)
                };

                trace!("replacing {} with {}", temp, machine_reg);
                coloring.cf.mc_mut().replace_reg(temp, machine_reg);

                coloring.cf.temps.insert(temp, machine_reg);
            }
        }

qinsoon's avatar
qinsoon committed
65
        // find out what callee saved registers are used
qinsoon's avatar
qinsoon committed
66 67 68
        // FIXME: current not doing this
        // reason: we generated frame slots for callee saved registers, then generated slots for spills
        // if we delete some callee saved registers, the slots for spills are not correct
qinsoon's avatar
qinsoon committed
69 70 71 72 73 74 75 76 77 78
        {
            use std::collections::HashSet;

            let used_callee_saved: HashSet<MuID> =
                coloring.cf.temps.values()
                    .map(|x| *x)
                    .filter(|x| is_callee_saved(*x))
                    .collect();

            let used_callee_saved: Vec<MuID> = used_callee_saved.into_iter().collect();
qinsoon's avatar
qinsoon committed
79
            let n_used_callee_saved = used_callee_saved.len();
qinsoon's avatar
qinsoon committed
80 81 82 83 84

            let removed_callee_saved = coloring.cf.mc_mut().remove_unnecessary_callee_saved(used_callee_saved);
            for reg in removed_callee_saved {
                coloring.cf.frame.remove_record_for_callee_saved_reg(reg);
            }
qinsoon's avatar
qinsoon committed
85 86 87 88 89 90 91 92 93 94 95 96 97 98

            // patch frame size

            // size for callee saved regs
            let size_for_callee_saved_regs = n_used_callee_saved * POINTER_SIZE;
            trace!("callee saved registers used {} bytes", size_for_callee_saved_regs);

            let total_frame_size = coloring.cf.frame.cur_size();
            trace!("frame reserved for {} bytes", total_frame_size);

            let size_to_patch = total_frame_size - size_for_callee_saved_regs;

            trace!("patching the code to grow/shrink size of {} bytes", size_to_patch);
            coloring.cf.mc_mut().patch_frame_size(size_to_patch);
qinsoon's avatar
qinsoon committed
99 100
        }

qinsoon's avatar
qinsoon committed
101 102 103 104 105 106 107 108 109 110 111 112 113
        coloring.cf.mc().trace_mc();
    }
}

impl CompilerPass for RegisterAllocation {
    fn name(&self) -> &'static str {
        self.name
    }

    fn as_any(&self) -> &Any {
        self
    }

114 115
    fn visit_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
        self.coloring(vm, func);
qinsoon's avatar
qinsoon committed
116 117
    }
}