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

peephole_opt.rs 7.36 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
qinsoon's avatar
qinsoon committed
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
qinsoon's avatar
qinsoon committed
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
qinsoon's avatar
qinsoon committed
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
use compiler::CompilerPass;
use ast::ir::*;
qinsoon's avatar
qinsoon committed
17
use vm::VM;
qinsoon's avatar
qinsoon committed
18
use compiler::machine_code::CompiledFunction;
qinsoon's avatar
qinsoon committed
19
use compiler::backend;
20

qinsoon's avatar
qinsoon committed
21
22
use std::any::Any;

23
pub struct PeepholeOptimization {
24
    name: &'static str
25
26
}

qinsoon's avatar
qinsoon committed
27
28
29
30
31
32
33
34
35
36
37
38
39
40
impl CompilerPass for PeepholeOptimization {
    fn name(&self) -> &'static str {
        self.name
    }

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

    fn visit_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
        let compiled_funcs = vm.compiled_funcs().read().unwrap();
        let mut cf = compiled_funcs.get(&func.id()).unwrap().write().unwrap();

        for i in 0..cf.mc().number_of_insts() {
qinsoon's avatar
qinsoon committed
41
42
            // if two sides of a move instruction are the same,
            // it is redundant, and can be eliminated
qinsoon's avatar
qinsoon committed
43
            self.remove_redundant_move(i, &mut cf);
44
45
46
47
48
49
50
51
52
53
54

            // if a branch jumps a label that contains another jump, such as
            // ..
            //   jmp L1
            // ..
            // L1:
            //   jmp L2
            // ..
            // we can rewrite first branch to jump to L2 directly

            // the order matters: we need to run this first, then remove_unnecessary_jump()
55
            // as this will give us more chances to remove unnecessary jumps
56
57
            self.remove_jump_to_jump(i, &mut cf);

qinsoon's avatar
qinsoon committed
58
59
60
61
62
63
64
65
66
            // if a branch targets a block that immediately follow it, it can be eliminated
            self.remove_unnecessary_jump(i, &mut cf);
        }

        trace!("after peephole optimization:");
        cf.mc().trace_mc();
    }
}

67
68
69
impl PeepholeOptimization {
    pub fn new() -> PeepholeOptimization {
        PeepholeOptimization {
70
            name: "Peephole Optimization"
71
72
        }
    }
qinsoon's avatar
qinsoon committed
73

qinsoon's avatar
qinsoon committed
74
75
    fn remove_redundant_move(&mut self, inst: usize, cf: &mut CompiledFunction) {
        // if this instruction is a move, and move from register to register (no memory operands)
qinsoon's avatar
qinsoon committed
76
77
        if cf.mc().is_move(inst) && !cf.mc().is_using_mem_op(inst) {
            cf.mc().trace_inst(inst);
qinsoon's avatar
qinsoon committed
78
79

            // get source reg/temp ID
qinsoon's avatar
qinsoon committed
80
            let src: MuID = {
qinsoon's avatar
qinsoon committed
81
                let uses = cf.mc().get_inst_reg_uses(inst);
qinsoon's avatar
qinsoon committed
82
                if uses.len() == 0 {
83
84
                    // moving immediate to register, its not redundant
                    return;
qinsoon's avatar
qinsoon committed
85
                }
86
87
                uses[0]
            };
qinsoon's avatar
qinsoon committed
88
89

            // get dest reg/temp ID
qinsoon's avatar
qinsoon committed
90
            let dst: MuID = cf.mc().get_inst_reg_defines(inst)[0];
qinsoon's avatar
qinsoon committed
91
92

            // turning temp into machine reg
qinsoon's avatar
qinsoon committed
93
            let src_machine_reg: MuID = {
94
95
                match cf.temps.get(&src) {
                    Some(reg) => *reg,
96
                    None => src
97
98
                }
            };
qinsoon's avatar
qinsoon committed
99
            let dst_machine_reg: MuID = {
100
101
                match cf.temps.get(&dst) {
                    Some(reg) => *reg,
102
                    None => dst
103
104
                }
            };
qinsoon's avatar
qinsoon committed
105
106

            // check if two registers are aliased
107
            if backend::is_aliased(src_machine_reg, dst_machine_reg) {
qinsoon's avatar
qinsoon committed
108
109
110
111
112
                info!(
                    "move between {} and {} is redundant! removed",
                    src_machine_reg,
                    dst_machine_reg
                );
113
                // redundant, remove this move
qinsoon's avatar
qinsoon committed
114
                cf.mc_mut().set_inst_nop(inst);
qinsoon's avatar
qinsoon committed
115
116
            } else {

117
118
119
            }
        }
    }
120

qinsoon's avatar
qinsoon committed
121
    fn remove_unnecessary_jump(&mut self, inst: usize, cf: &mut CompiledFunction) {
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
        let mut mc = cf.mc_mut();

        // if this is last instruction, return
        if inst == mc.number_of_insts() - 1 {
            return;
        }

        // if this inst jumps to a label that directly follows it, we can set it to nop
        let opt_dest = mc.is_jmp(inst);

        match opt_dest {
            Some(ref dest) => {
                let opt_label = mc.is_label(inst + 1);
                match opt_label {
                    Some(ref label) if dest == label => {
137
138
                        info!("inst {}'s jmp to {} is unnecessary! removed", inst, label);
                        mc.set_inst_nop(inst);
139
140
141
142
143
144
145
146
147
148
149
                    }
                    _ => {
                        // do nothing
                    }
                }
            }
            None => {
                // do nothing
            }
        }
    }
150
151
152
153

    fn remove_jump_to_jump(&mut self, inst: usize, cf: &mut CompiledFunction) {
        let mut mc = cf.mc_mut();

154
155
156
        // the instruction that we may rewrite
        let orig_inst = inst;
        // the destination we will rewrite the instruction to branch to
qinsoon's avatar
qinsoon committed
157
        let final_dest: Option<MuName> = {
158
159
            use std::collections::HashSet;

160
161
            let mut cur_inst = inst;
            let mut last_dest = None;
162
163
164

            let mut visited_labels = HashSet::new();

165
166
167
168
            loop {
                let opt_dest = mc.is_jmp(cur_inst);
                match opt_dest {
                    Some(ref dest) => {
169
170
171
172
173
174
175
176
                        // if we have already visited this instruction
                        // this means we met an infinite loop, we need to break
                        if visited_labels.contains(dest) {
                            warn!("met an infinite loop in removing jump-to-jump");
                            warn!("we are not optimizing this case");
                            return;
                        }

177
178
                        // get the block for destination
                        let first_inst = mc.get_block_range(dest).unwrap().start;
qinsoon's avatar
qinsoon committed
179
180
181
182
183
184
185
                        debug_assert!(
                            mc.is_label(first_inst).is_none(),
                            "expect start inst {} of \
                             block {} is a inst instead of label",
                            first_inst,
                            dest
                        );
186
187
188
189
190
191
192
193
194

                        trace!("examining first inst {} of block {}", first_inst, dest);

                        // if first instruction is jump
                        match mc.is_jmp(first_inst) {
                            Some(ref dest2) => {
                                // its a jump-to-jump case
                                cur_inst = first_inst;
                                last_dest = Some(dest2.clone());
195
196
                                visited_labels.insert(dest2.clone());
                                debug!("visited {}", dest2);
197
                            }
198
                            None => break
199
                        }
200
                    }
201
                    None => break
202
203
                }
            }
204
205
206
207
            last_dest
        };

        if let Some(dest) = final_dest {
208
            let first_inst = mc.get_block_range(&dest).unwrap().start;
209

qinsoon's avatar
qinsoon committed
210
211
212
213
214
215
216
            info!(
                "inst {} chain jumps to {}, rewrite as branching to {} (successor: {})",
                orig_inst,
                dest,
                dest,
                first_inst
            );
217
            mc.replace_branch_dest(inst, &dest, first_inst);
218
219
        }
    }
220
}