duskphantom_middle/transform/
ldce.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::{
18    collections::{HashSet, VecDeque},
19    pin::Pin,
20};
21
22use crate::{
23    analysis::{
24        effect_analysis::EffectAnalysis,
25        loop_tools::{LoopForest, LoopPtr},
26    },
27    ir::{
28        instruction::{downcast_ref, misc_inst::Call, InstType},
29        BBPtr, InstPtr,
30    },
31    IRBuilder,
32};
33use anyhow::{Ok, Result};
34
35use super::loop_optimization::loop_forest_post_order;
36
37type IRBuilderWraper = Pin<Box<IRBuilder>>;
38
39pub struct LDCE<'a> {
40    _ir_builder: &'a mut IRBuilderWraper,
41    check_set: HashSet<InstPtr>,
42    loop_bbs: HashSet<BBPtr>,
43    effect_analysis: &'a EffectAnalysis,
44}
45
46impl<'a> LDCE<'a> {
47    pub fn new(
48        _ir_builder: &'a mut IRBuilderWraper,
49        effect_analysis: &'a EffectAnalysis,
50    ) -> LDCE<'a> {
51        Self {
52            _ir_builder,
53            check_set: HashSet::new(),
54            loop_bbs: HashSet::new(),
55            effect_analysis,
56        }
57    }
58
59    pub fn run(&mut self, forest: &mut LoopForest) -> Result<()> {
60        loop_forest_post_order(forest, |x| self.ldce_one_loop(x))
61    }
62
63    fn ldce_one_loop(&mut self, lo: LoopPtr) -> Result<()> {
64        self.loop_bbs.clear();
65        {
66            let mut queue = VecDeque::from([lo]);
67            while let Some(lo) = queue.pop_back() {
68                self.loop_bbs.extend(lo.blocks.iter());
69                queue.extend(lo.sub_loops.iter());
70            }
71        }
72
73        lo.blocks.iter().try_for_each(|&x| self.ldce_one_bb(x))
74    }
75
76    fn ldce_one_bb(&mut self, bb: BBPtr) -> Result<()> {
77        let mut cur_set = HashSet::new();
78        for inst in bb.iter() {
79            if self.check_set.contains(&inst) {
80                continue;
81            }
82            cur_set.extend(self.ldce_inst(inst)?);
83        }
84        cur_set.into_iter().for_each(|mut x| x.remove_self());
85        Ok(())
86    }
87
88    fn ldce_inst(&mut self, inst: InstPtr) -> Result<HashSet<InstPtr>> {
89        let check_user_out_loop = |inst: InstPtr| {
90            inst.get_user()
91                .iter()
92                .any(|x| self.loop_bbs.contains(&x.get_parent_bb().unwrap()))
93        };
94        if check_user_out_loop(inst) {
95            self.check_set.insert(inst);
96            return Ok(HashSet::new());
97        }
98
99        let mut cur_set = HashSet::from([inst]);
100        let mut queue = VecDeque::from([inst]);
101        while let Some(inst) = queue.pop_back() {
102            if !self.can_delete_inst(inst) || check_user_out_loop(inst) {
103                self.check_set
104                    .extend(cur_set.iter().chain(inst.get_user().iter()));
105                return Ok(HashSet::new());
106            }
107            queue.extend(inst.get_user().iter().filter(|x| !cur_set.contains(x)));
108            cur_set.extend(inst.get_user().iter());
109        }
110
111        self.check_set.extend(cur_set.iter());
112        Ok(cur_set)
113    }
114
115    fn can_delete_inst(&self, inst: InstPtr) -> bool {
116        let call_no_effect = if inst.get_type() == InstType::Call {
117            let call = downcast_ref::<Call>(inst.as_ref().as_ref());
118            !(self.effect_analysis.has_mem_output.contains(&call.func)
119                || self.effect_analysis.has_io_input.contains(&call.func)
120                || self.effect_analysis.has_io_output.contains(&call.func))
121        } else {
122            true
123        };
124        let no_control_or_store = !matches!(
125            inst.get_type(),
126            InstType::Br | InstType::Ret | InstType::Store
127        );
128        call_no_effect && no_control_or_store
129    }
130}
duskphantom_middle/transform/ldce.rs

duskphantom_middle/transform/
ldce.rs
