duskphantom_middle/analysis/
effect_analysis.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 crate::ir::instruction::downcast_ref;
18use crate::{
19    ir::{
20        instruction::{misc_inst::Call, InstType},
21        FunPtr, InstPtr, Operand,
22    },
23    Program,
24};
25use std::collections::{HashMap, HashSet};
26
27use super::{alias_analysis::EffectRange, call_graph::CallGraph};
28
29pub struct Effect {
30    pub def_range: EffectRange,
31    pub use_range: EffectRange,
32}
33
34impl Default for Effect {
35    fn default() -> Self {
36        Self::new()
37    }
38}
39
40impl Effect {
41    pub fn new() -> Self {
42        Self {
43            def_range: EffectRange::new(),
44            use_range: EffectRange::new(),
45        }
46    }
47
48    pub fn dump(&self) -> String {
49        format!(
50            "(def: {}, use: {})",
51            self.def_range.dump(),
52            self.use_range.dump()
53        )
54    }
55}
56
57pub struct EffectAnalysis {
58    pub inst_effect: HashMap<InstPtr, Effect>,
59    pub has_io_input: HashSet<FunPtr>,
60    pub has_io_output: HashSet<FunPtr>,
61    pub has_mem_input: HashSet<FunPtr>,
62    pub has_mem_output: HashSet<FunPtr>,
63    functions: Vec<FunPtr>,
64}
65
66impl EffectAnalysis {
67    /// Run effect analysis on program.
68    pub fn new(program: &Program) -> Self {
69        let mut worklist: HashSet<FunPtr> = HashSet::new();
70        let mut effect = Self {
71            inst_effect: HashMap::new(),
72            has_io_input: HashSet::new(),
73            has_io_output: HashSet::new(),
74            has_mem_input: HashSet::new(),
75            has_mem_output: HashSet::new(),
76            functions: program.module.functions.clone(),
77        };
78
79        // Set all library functions as has_io
80        for func in program.module.functions.iter() {
81            if func.is_lib() {
82                if func.name.contains("get") {
83                    effect.has_io_input.insert(*func);
84                }
85                if func.name.contains("put")
86                    || func.name.contains("starttime")
87                    || func.name.contains("stoptime")
88                {
89                    effect.has_io_output.insert(*func);
90                }
91                if func.name.contains("thrd") {
92                    effect.has_io_input.insert(*func);
93                    effect.has_io_output.insert(*func);
94                }
95                if func.name.contains("memset")
96                    || func.name == "getarray"
97                    || func.name == "getfarray"
98                {
99                    effect.has_mem_output.insert(*func);
100                }
101                if func.name == "putarray" || func.name == "putfarray" {
102                    effect.has_mem_input.insert(*func);
103                }
104            } else {
105                worklist.insert(*func);
106            }
107        }
108
109        // Iterate all functions until unchanged
110        let call_graph = CallGraph::new(program);
111        loop {
112            let mut changed = false;
113            for func in program.module.functions.iter() {
114                if func.is_lib() || !worklist.contains(func) {
115                    continue;
116                }
117                worklist.remove(func);
118                if effect.process_func(*func) {
119                    changed = true;
120                    worklist.extend(
121                        call_graph
122                            .get_called_by(*func)
123                            .iter()
124                            .map(|edge| edge.caller),
125                    );
126                }
127            }
128            if !changed {
129                break effect;
130            }
131        }
132    }
133
134    /// Get if instruction has IO.
135    pub fn has_io(&self, inst: InstPtr) -> bool {
136        if inst.get_type() == InstType::Call {
137            let call = downcast_ref::<Call>(inst.as_ref().as_ref());
138            self.has_io_input.contains(&call.func) || self.has_io_output.contains(&call.func)
139        } else {
140            false
141        }
142    }
143
144    /// Get if function has side effect.
145    pub fn has_effect(&self, inst: InstPtr) -> bool {
146        if inst.get_type() == InstType::Call {
147            let call = downcast_ref::<Call>(inst.as_ref().as_ref());
148            self.has_mem_input.contains(&call.func)
149                || self.has_mem_output.contains(&call.func)
150                || self.has_io_input.contains(&call.func)
151                || self.has_io_output.contains(&call.func)
152        } else {
153            false
154        }
155    }
156
157    /// Dump effect analysis result on instruction to string.
158    pub fn dump_inst(&self) -> String {
159        let mut res = String::new();
160        for func in self.functions.iter() {
161            if func.is_lib() {
162                continue;
163            }
164            for bb in func.dfs_iter() {
165                for inst in bb.iter() {
166                    let Some(effect) = self.inst_effect.get(&inst) else {
167                        continue;
168                    };
169                    res += &format!("{}:\n", inst.gen_llvm_ir());
170                    res += &format!("    def: {}\n", effect.def_range.dump());
171                    res += &format!("    use: {}\n\n", effect.use_range.dump());
172                }
173            }
174        }
175        res
176    }
177
178    /// Process function, return changed or not
179    fn process_func(&mut self, func: FunPtr) -> bool {
180        let mut changed = false;
181        for bb in func.dfs_iter() {
182            for inst in bb.iter() {
183                match inst.get_type() {
184                    InstType::Call => {
185                        // Merge function effect
186                        let call = downcast_ref::<Call>(inst.as_ref().as_ref());
187                        changed |= self.add_batch_to_func(func, call.func);
188
189                        // Add instruction effect
190                        if call.func.name.contains("memset") {
191                            // Treat memset as a store
192                            let ptr = get_base_pointer(inst.get_operand()[0].clone());
193                            self.inst_effect.insert(
194                                inst,
195                                Effect {
196                                    def_range: ptr.into(),
197                                    use_range: EffectRange::new(),
198                                },
199                            );
200                        } else if call.func.name == "putarray" || call.func.name == "putfarray" {
201                            let ptr = get_base_pointer(inst.get_operand()[1].clone());
202                            self.inst_effect.insert(
203                                inst,
204                                Effect {
205                                    def_range: EffectRange::new(),
206                                    use_range: ptr.into(),
207                                },
208                            );
209                        } else if call.func.name == "getarray" || call.func.name == "getfarray" {
210                            let ptr = get_base_pointer(inst.get_operand()[0].clone());
211                            self.inst_effect.insert(
212                                inst,
213                                Effect {
214                                    def_range: ptr.into(),
215                                    use_range: EffectRange::new(),
216                                },
217                            );
218                        } else if !call.func.is_lib() {
219                            // Treat other non-library function as impure
220                            self.inst_effect.insert(
221                                inst,
222                                Effect {
223                                    def_range: EffectRange::All,
224                                    use_range: EffectRange::new(),
225                                },
226                            );
227                        }
228                    }
229                    InstType::Store => {
230                        let target = inst.get_operand()[1].clone();
231                        if check_effect(&target) {
232                            changed |= self.has_mem_output.insert(func);
233                        }
234
235                        // Add store as an effective inst
236                        self.inst_effect.insert(
237                            inst,
238                            Effect {
239                                def_range: target.into(),
240                                use_range: EffectRange::new(),
241                            },
242                        );
243                    }
244                    InstType::Load => {
245                        let target = inst.get_operand()[0].clone();
246                        if check_effect(&target) {
247                            changed |= self.has_mem_input.insert(func);
248                        }
249
250                        // Add load as an effective inst
251                        self.inst_effect.insert(
252                            inst,
253                            Effect {
254                                def_range: EffectRange::new(),
255                                use_range: target.into(),
256                            },
257                        );
258                    }
259                    _ => {}
260                }
261            }
262        }
263        changed
264    }
265
266    /// Merge effect of two functions, return changed or not.
267    /// This attempts to change effect target from local variable to parameter.
268    fn add_batch_to_func(&mut self, dst: FunPtr, src: FunPtr) -> bool {
269        let mut changed = false;
270        if self.has_io_input.contains(&src) {
271            changed |= self.has_io_input.insert(dst);
272        }
273        if self.has_io_output.contains(&src) {
274            changed |= self.has_io_output.insert(dst);
275        }
276        if self.has_mem_input.contains(&src) {
277            changed |= self.has_mem_input.insert(dst);
278        }
279        if self.has_mem_output.contains(&src) {
280            changed |= self.has_mem_output.insert(dst);
281        }
282        changed
283    }
284}
285
286/// Check if operand as store / load position causes outside effect.
287fn check_effect(operand: &Operand) -> bool {
288    match operand {
289        Operand::Instruction(inst) => {
290            if inst.get_type() == InstType::GetElementPtr {
291                check_effect(inst.get_operand().first().unwrap())
292            } else {
293                false
294            }
295        }
296        Operand::Global(_) => true,
297        Operand::Parameter(_) => true,
298        Operand::Constant(_) => false,
299    }
300}
301
302/// Get base pointer of operand (because pointer in function argument can GEP a lot)
303fn get_base_pointer(operand: Operand) -> Operand {
304    match operand {
305        Operand::Instruction(inst) => {
306            if inst.get_type() == InstType::GetElementPtr {
307                get_base_pointer(inst.get_operand().first().unwrap().clone())
308            } else {
309                operand
310            }
311        }
312        _ => operand,
313    }
314}
duskphantom_middle/analysis/effect_analysis.rs

duskphantom_middle/analysis/
effect_analysis.rs
