To protect your data, the CISO officer has suggested users to enable GitLab 2FA as soon as possible.

exact_liveness.rs 3.39 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
17
18
19
20
use utils::LinkedHashMap;
use utils::LinkedHashSet;
use ast::ir::*;
use compiler::machine_code::CompiledFunction;

pub struct ExactLiveness {
21
    livein: LinkedHashMap<usize, LinkedHashSet<MuID>>,
22
    liveout: LinkedHashMap<usize, LinkedHashSet<MuID>>,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
23
    kill: LinkedHashMap<usize, LinkedHashSet<MuID>>,
24
25
26
27
28
29
30
}

impl ExactLiveness {
    pub fn new(cf: &CompiledFunction) -> ExactLiveness {
        let mut ret = ExactLiveness {
            livein: LinkedHashMap::new(),
            liveout: LinkedHashMap::new(),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
31
            kill: LinkedHashMap::new(),
32
33
34
35
36
37
38
39
40
41
42
43
44
        };

        ret.liveness_analysis(cf);

        ret
    }

    fn liveness_analysis(&mut self, cf: &CompiledFunction) {
        let mc = cf.mc();

        for block in mc.get_all_blocks().iter() {
            let range = mc.get_block_range(block).unwrap();

45
46
            let mut liveout: LinkedHashSet<MuID> =
                LinkedHashSet::from_vec(mc.get_ir_block_liveout(block).unwrap().clone());
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

            for i in range.rev() {
                // set liveout
                self.liveout.insert(i, liveout.clone());

                // compute livein: in[n] <- use[n] + (out[n] - def[n])
                for reg_def in mc.get_inst_reg_defines(i) {
                    liveout.remove(&reg_def);
                }
                for reg_use in mc.get_inst_reg_uses(i) {
                    liveout.insert(reg_use);
                }
                // liveout is livein now
                self.livein.insert(i, liveout.clone());

                // liveout for prev inst is livein for current inst
            }
        }

        // liveness analysis done
        // compute 'kill': if a reg is in livein of an inst, but not liveout, it kills in the inst
        for i in self.livein.keys() {
69
            let mut kill: LinkedHashSet<MuID> = LinkedHashSet::new();
70
71
72
73
74
75
76
77
78
79
80
81
82

            let livein = self.livein.get(i).unwrap();
            let liveout = self.liveout.get(i).unwrap();

            for reg in livein.iter() {
                if !liveout.contains(reg) {
                    kill.insert(*reg);
                }
            }

            self.kill.insert(*i, kill);
        }
    }
83
84
85
86

    pub fn get_liveout(&self, index: usize) -> Option<LinkedHashSet<MuID>> {
        match self.liveout.get(&index) {
            Some(s) => Some(s.clone()),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
87
            None => None,
88
89
        }
    }
90

91
92
93
    pub fn get_kills(&self, index: usize) -> Option<LinkedHashSet<MuID>> {
        match self.kill.get(&index) {
            Some(s) => Some(s.clone()),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
94
            None => None,
95
96
97
98
99
100
101
102
103
104
        }
    }

    pub fn trace(&self, index: usize) {
        if self.livein.contains_key(&index) {
            trace!("in  : {:?}", self.livein.get(&index).unwrap());
            trace!("out : {:?}", self.liveout.get(&index).unwrap());
            trace!("kill: {:?}", self.kill.get(&index).unwrap());
        }
    }
105
}