duskphantom_middle/transform/
licm.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::pin::Pin;
18
19use crate::{
20    analysis::{
21        loop_tools::{LoopForest, LoopPtr},
22        memory_ssa::MemorySSA,
23    },
24    ir::{instruction::InstType, BBPtr, IRBuilder, InstPtr, Operand},
25};
26use anyhow::{Ok, Result};
27
28use super::loop_optimization::loop_forest_post_order;
29
30type IRBuilderWraper = Pin<Box<IRBuilder>>;
31
32pub struct LICM<'a, 'b> {
33    _ir_builder: &'a mut IRBuilderWraper,
34    memory_ssa: &'a mut MemorySSA<'b>,
35}
36
37impl<'a, 'b> LICM<'a, 'b> {
38    pub fn new(
39        _ir_builder: &'a mut IRBuilderWraper,
40        memory_ssa: &'a mut MemorySSA<'b>,
41    ) -> LICM<'a, 'b> {
42        Self {
43            _ir_builder,
44            memory_ssa,
45        }
46    }
47
48    pub fn run(&mut self, forest: &mut LoopForest) -> Result<()> {
49        loop_forest_post_order(forest, |x| self.licm_one_loop(x))
50    }
51
52    fn licm_one_loop(&mut self, lo: LoopPtr) -> Result<()> {
53        let preheader = lo.pre_header.unwrap();
54        lo.blocks
55            .iter()
56            .try_for_each(|&x| self.licm_one_bb(lo, x, preheader))
57    }
58
59    fn licm_one_bb(&mut self, lo: LoopPtr, bb: BBPtr, preheader: BBPtr) -> Result<()> {
60        for inst in bb.iter() {
61            self.licm_inst_trace(lo, inst, preheader)?
62        }
63        Ok(())
64    }
65
66    fn licm_inst_trace(&mut self, lo: LoopPtr, mut inst: InstPtr, preheader: BBPtr) -> Result<()> {
67        if
68        // 防止递归之后得到循环外的inst
69        lo.is_in_loop(&inst.get_parent_bb().unwrap())
70        // 以下指令暂不考虑
71        && !matches!(
72            inst.get_type(),
73            InstType::Br
74            | InstType::Alloca
75            | InstType::Store
76            | InstType::Call
77            | InstType::Ret
78            | InstType::Phi
79            )
80        // 判断是否是循环不变量，即操作数是否都在循环外 
81        && inst.get_operand().iter().all(|i| {
82            if let Operand::Instruction(i) = i {
83                !lo.is_in_loop(&i.get_parent_bb().unwrap())
84            } else {
85                true
86            }
87            })
88        // 对于 Load 指令，所使用的 MemoryDef 必须在循环外
89        && self.memory_ssa.get_inst_node(inst).map_or(true, |node| {
90            !lo.is_in_loop(&self.memory_ssa.get_node_block(node.get_use_node()).unwrap())
91        }) {
92            unsafe {
93                inst.move_self();
94            }
95            // 无需移动 MemorySSA 节点，反正 Load 不会被别的用
96            preheader.get_last_inst().insert_before(inst);
97
98            inst.get_user()
99                .iter()
100                .try_for_each(|&user| self.licm_inst_trace(lo, user, preheader))?
101        }
102        Ok(())
103    }
104}
duskphantom_middle/transform/licm.rs

duskphantom_middle/transform/
licm.rs
