duskphantom_middle/transform/
redundance_elim.rs

1// Copyright 2024 Duskphantom Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// SPDX-License-Identifier: Apache-2.0
16
17use std::collections::HashMap;
18
19use anyhow::Result;
20
21use crate::{
22    analysis::{
23        dominator_tree::DominatorTree,
24        effect_analysis::EffectAnalysis,
25        memory_ssa::MemorySSA,
26        simple_gvn::{Expr, SimpleGVN},
27    },
28    ir::{InstPtr, Operand, ValueType},
29    Program,
30};
31
32use super::Transform;
33
34pub fn optimize_program(program: &mut Program) -> Result<bool> {
35    let effect_analysis = EffectAnalysis::new(program);
36    let memory_ssa = MemorySSA::new(program, &effect_analysis);
37    let mut gvn = SimpleGVN::new(&memory_ssa);
38    RedundanceElim::new(program, &mut gvn).run_and_log()
39}
40
41pub struct RedundanceElim<'a> {
42    program: &'a mut Program,
43    gvn: &'a mut SimpleGVN<'a>,
44}
45
46impl<'a> Transform for RedundanceElim<'a> {
47    fn get_program_mut(&mut self) -> &mut Program {
48        self.program
49    }
50
51    fn name() -> String {
52        "redundance_elim".to_string()
53    }
54
55    fn run(&mut self) -> Result<bool> {
56        // Get instruction leader from GVN
57        let mut changed = false;
58        for func in self.program.module.functions.clone() {
59            if func.is_lib() {
60                continue;
61            }
62            let mut dom_tree = DominatorTree::new(func);
63
64            // Implementation of Expr::Hash does not use it's mutable content,
65            // so it's false positive according to:
66            // https://rust-lang.github.io/rust-clippy/master/index.html#/mutable_key_type
67            #[allow(clippy::mutable_key_type)]
68            let mut expr_leader: HashMap<Expr, InstPtr> = HashMap::new();
69
70            // Iterate all instructions
71            for bb in func.rpo_iter() {
72                for inst in bb.iter() {
73                    // Refuse to replace instruction that returns void
74                    if inst.get_value_type() == ValueType::Void {
75                        continue;
76                    }
77                    let expr = self.gvn.get_expr(Operand::Instruction(inst));
78                    match expr_leader.get(&expr) {
79                        // Expression appeared before, move leader and inst to lowest common ancestor
80                        Some(&leader) => {
81                            let inst_bb = inst.get_parent_bb().unwrap();
82                            let leader_bb = leader.get_parent_bb().unwrap();
83                            let lca = dom_tree.get_lca(inst_bb, leader_bb);
84                            if lca != leader_bb {
85                                // Remove partial redundancy and hoist at the same time
86                                lca.get_last_inst().insert_before(leader);
87                            }
88                            inst.clone().replace_self(&leader.into());
89                            changed = true;
90                        }
91                        // Expression not appeared before, set as leader
92                        None => {
93                            expr_leader.insert(expr, inst);
94                        }
95                    }
96                }
97            }
98        }
99        Ok(changed)
100    }
101}
102
103impl<'a> RedundanceElim<'a> {
104    pub fn new(program: &'a mut Program, gvn: &'a mut SimpleGVN<'a>) -> Self {
105        Self { program, gvn }
106    }
107}
duskphantom_middle/transform/redundance_elim.rs

duskphantom_middle/transform/
redundance_elim.rs
