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.7% of users enabled 2FA.

mod.rs 4.46 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3
4
5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9
10
11
12
13
14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15
16
extern crate petgraph;

17
18
19
mod liveness;
mod coloring;

qinsoon's avatar
qinsoon committed
20
21
use compiler::backend::reg_alloc::graph_coloring::liveness::build_interference_graph_chaitin_briggs as build_inteference_graph;
use compiler::backend::reg_alloc::graph_coloring::coloring::GraphColoring;
qinsoon's avatar
qinsoon committed
22
23
24
25

use ast::ir::*;
use vm::VM;
use compiler::CompilerPass;
qinsoon's avatar
qinsoon committed
26
use compiler::backend::is_callee_saved;
qinsoon's avatar
qinsoon committed
27
use compiler::backend::init_machine_regs_for_func;
28
use compiler::backend::reg_alloc::validate;
qinsoon's avatar
qinsoon committed
29
30
31
use std::any::Any;

pub struct RegisterAllocation {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
32
    name: &'static str,
qinsoon's avatar
qinsoon committed
33
34
}

qinsoon's avatar
qinsoon committed
35
36
37
38
39
40
41
42
43
44
45
46
47
48
impl CompilerPass for RegisterAllocation {
    fn name(&self) -> &'static str {
        self.name
    }

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

    fn visit_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
        self.coloring(vm, func);
    }
}

qinsoon's avatar
qinsoon committed
49
50
51
impl RegisterAllocation {
    pub fn new() -> RegisterAllocation {
        RegisterAllocation {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
52
            name: "Register Allocation",
qinsoon's avatar
qinsoon committed
53
54
55
        }
    }

56
    fn coloring(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
qinsoon's avatar
qinsoon committed
57
        // get compiled function
qinsoon's avatar
qinsoon committed
58
59
60
        let compiled_funcs = vm.compiled_funcs().read().unwrap();
        let mut cf = compiled_funcs.get(&func.id()).unwrap().write().unwrap();

qinsoon's avatar
qinsoon committed
61
        // initialize machine registers for the function context (we are gonna use them)
qinsoon's avatar
qinsoon committed
62
63
        init_machine_regs_for_func(&mut func.context);

qinsoon's avatar
qinsoon committed
64
        // do graph coloring
65
        let coloring = GraphColoring::start(func, &mut cf, vm);
qinsoon's avatar
qinsoon committed
66

qinsoon's avatar
qinsoon committed
67
        // if we need to validate the results
qinsoon's avatar
qinsoon committed
68
        if !vm.vm_options.flag_disable_regalloc_validate {
qinsoon's avatar
qinsoon committed
69
            // a map of register assignment (from temp to machine register)
70
            let reg_assignment = coloring.get_assignments();
qinsoon's avatar
qinsoon committed
71
72
            // a map of spilled temporaries (from spilled temp to scratch temp)
            // we use this to validate spilling correctness
qinsoon's avatar
qinsoon committed
73
            let spill_scratch_temps = coloring.get_spill_scratch_temps();
qinsoon's avatar
qinsoon committed
74

qinsoon's avatar
qinsoon committed
75
            validate::validate_regalloc(&coloring.cf, reg_assignment, spill_scratch_temps);
qinsoon's avatar
qinsoon committed
76
77
        }

qinsoon's avatar
qinsoon committed
78
        // use the result to replace temporaries with assigned regs
qinsoon's avatar
qinsoon committed
79
        trace!("Replacing Registers...");
80
81
82
83
        for (temp, machine_reg) in coloring.get_assignments() {
            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
84
85
        }

qinsoon's avatar
qinsoon committed
86
87
88
89
90
        // find out what callee saved registers are used, so we can delete unnecessary savings.
        // Currently I am only deleting those unnecessary push/pops of callee saved regs, but
        // I am not deleting the frame slots for them (so the frame size is still larger than
        // it needs to be).
        // FIXME: should fix offsets of frame slots, and patch the code. See Issue #47
qinsoon's avatar
qinsoon committed
91
        {
qinsoon's avatar
qinsoon committed
92
93
94
            // all the used callee saved registers
            let used_callee_saved: Vec<MuID> = {
                use std::collections::HashSet;
95
96
97
98
99
100
101
                let used_callee_saved: HashSet<MuID> = coloring
                    .cf
                    .temps
                    .values()
                    .map(|x| *x)
                    .filter(|x| is_callee_saved(*x))
                    .collect();
qinsoon's avatar
qinsoon committed
102
103
104
105
                used_callee_saved.into_iter().collect()
            };

            // remove unused callee saved registers
106
107
108
109
            let removed_callee_saved = coloring
                .cf
                .mc_mut()
                .remove_unnecessary_callee_saved(used_callee_saved);
qinsoon's avatar
qinsoon committed
110
111
112
            for reg in removed_callee_saved {
                coloring.cf.frame.remove_record_for_callee_saved_reg(reg);
            }
qinsoon's avatar
qinsoon committed
113
114

            // patch frame size
115
            let frame_size = coloring.cf.frame.cur_size();
116
117
118
119
            trace!(
                "patching the code to grow/shrink size of {} bytes",
                frame_size
            );
120
            coloring.cf.mc_mut().patch_frame_size(frame_size);
qinsoon's avatar
qinsoon committed
121
122
        }

qinsoon's avatar
qinsoon committed
123
124
125
        coloring.cf.mc().trace_mc();
    }
}