duskphantom_middle/analysis/
alias_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::ir::{
19    instruction::{memory_op_inst::GetElementPtr, InstType},
20    Constant, Operand, ValueType,
21};
22use std::collections::{HashMap, HashSet};
23
24#[derive(Clone)]
25pub enum EffectRange {
26    All,
27    Some(HashSet<Operand>),
28}
29
30/// Check if two effect range must be the same.
31impl PartialEq for EffectRange {
32    fn eq(&self, another: &Self) -> bool {
33        match (self, another) {
34            (EffectRange::Some(a), EffectRange::Some(b)) => {
35                if a.len() != 1 || b.len() != 1 {
36                    return false;
37                }
38                // TODO judge equal with GVN
39                a.iter().next().unwrap() == b.iter().next().unwrap()
40            }
41            _ => false,
42        }
43    }
44}
45
46impl Default for EffectRange {
47    fn default() -> Self {
48        Self::new()
49    }
50}
51
52impl EffectRange {
53    /// Create an empty effect range.
54    pub fn new() -> Self {
55        EffectRange::Some(HashSet::new())
56    }
57
58    /// Check if two effect ranges conflict when parallelized.
59    /// TODO-TLE: use a more efficient way to check conflict, separate in parallel_analysis
60    pub fn can_conflict(&self, another: &EffectRange, indvar: &Operand) -> bool {
61        match (self, another) {
62            (EffectRange::All, EffectRange::All) => true,
63            (EffectRange::All, EffectRange::Some(_)) => true,
64            (EffectRange::Some(_), EffectRange::All) => true,
65            (EffectRange::Some(a), EffectRange::Some(b)) => a
66                .iter()
67                .any(|a_op| b.iter().any(|b_op| can_op_conflict(a_op, b_op, indvar))),
68        }
69    }
70
71    /// Check if two effect ranges can alias.
72    pub fn can_alias(&self, another: &EffectRange) -> bool {
73        match (self, another) {
74            (EffectRange::All, EffectRange::All) => true,
75            (EffectRange::All, EffectRange::Some(_)) => true,
76            (EffectRange::Some(_), EffectRange::All) => true,
77            (EffectRange::Some(a), EffectRange::Some(b)) => a
78                .iter()
79                .any(|a_op| b.iter().any(|b_op| can_op_alias(a_op, b_op))),
80        }
81    }
82
83    /// Merge two effect ranges.
84    pub fn merge(&mut self, another: &EffectRange) {
85        if let EffectRange::All = another {
86            *self = EffectRange::All;
87        } else if let (EffectRange::Some(a), EffectRange::Some(b)) = (self, another) {
88            a.extend(b.iter().cloned());
89        }
90    }
91
92    /// Check if the effect range is empty.
93    pub fn is_empty(&self) -> bool {
94        match self {
95            EffectRange::All => false,
96            EffectRange::Some(set) => set.is_empty(),
97        }
98    }
99
100    /// Get the only operand if the effect range contains only one operand.
101    pub fn get_single(&self) -> Option<&Operand> {
102        match self {
103            EffectRange::All => None,
104            EffectRange::Some(set) => {
105                if set.len() == 1 {
106                    set.iter().next()
107                } else {
108                    None
109                }
110            }
111        }
112    }
113
114    /// Dump effect range to string.
115    pub fn dump(&self) -> String {
116        match self {
117            EffectRange::All => "all".to_string(),
118            EffectRange::Some(set) => {
119                let mut set: Vec<_> = set.iter().map(Operand::to_string).collect();
120                set.sort();
121                set.join(", ")
122            }
123        }
124    }
125}
126
127impl From<Operand> for EffectRange {
128    fn from(op: Operand) -> Self {
129        EffectRange::Some([op].into_iter().collect())
130    }
131}
132
133impl From<HashSet<Operand>> for EffectRange {
134    fn from(set: HashSet<Operand>) -> Self {
135        EffectRange::Some(set)
136    }
137}
138
139/// Check if two operands (maybe with GEP) can alias.
140fn can_op_alias(a: &Operand, b: &Operand) -> bool {
141    if a == b {
142        return true;
143    }
144    let (ptr_a, offset_a) = split_gep(a);
145    let (ptr_b, offset_b) = split_gep(b);
146    can_ptr_alias(&ptr_a, &ptr_b) && can_offset_overlap(offset_a, offset_b)
147}
148
149/// Check if two operands cans conflict when parallelized.
150fn can_op_conflict(a: &Operand, b: &Operand, indvar: &Operand) -> bool {
151    if a == b && is_affine(a, indvar) {
152        return false;
153    }
154    can_op_alias(a, b)
155}
156
157/// Check if an operand address is affine over the induction variable.
158fn is_affine(op: &Operand, indvar: &Operand) -> bool {
159    let (_, offset) = split_gep(op);
160    for (_, op) in offset.iter() {
161        if let Operand::Instruction(inst) = op {
162            if let InstType::Add | InstType::Sub = inst.get_type() {
163                if &inst.get_operand()[0] == indvar {
164                    if let Operand::Constant(_) = inst.get_operand()[1] {
165                        return true;
166                    }
167                }
168            }
169        }
170        if op == indvar {
171            return true;
172        }
173    }
174    false
175}
176
177/// Check if two operands (without GEP) can alias.
178fn can_ptr_alias(a: &Operand, b: &Operand) -> bool {
179    // If any of them is param, they can alias
180    if let Operand::Parameter(_) = a {
181        return true;
182    }
183    if let Operand::Parameter(_) = b {
184        return true;
185    }
186
187    // Global variable alias only when they're the same
188    if let Operand::Global(a) = a {
189        if let Operand::Global(b) = b {
190            return a == b;
191        }
192    }
193
194    // Alloc instruction alias only when they're the same
195    if let Operand::Instruction(a) = a {
196        if let Operand::Instruction(b) = b {
197            return a == b;
198        }
199    }
200
201    // Operand of different type will not alias
202    false
203}
204
205/// Check if two sets of GEP offsets can overlap.
206fn can_offset_overlap(a: HashMap<ValueType, Operand>, b: HashMap<ValueType, Operand>) -> bool {
207    for (key, a_op) in a.iter() {
208        if let Some(b_op) = b.get(key) {
209            if !can_equal(a_op.clone(), b_op.clone()) {
210                return false;
211            }
212        }
213    }
214    true
215}
216
217/// Split GEP instruction into base pointer and offset.
218fn split_gep(op: &Operand) -> (Operand, HashMap<ValueType, Operand>) {
219    let mut base = op.clone();
220    let mut offset = HashMap::new();
221    while let Operand::Instruction(inst) = base {
222        if inst.get_type() != InstType::GetElementPtr {
223            break;
224        }
225
226        // Update base
227        base = inst.get_operand().first().unwrap().clone();
228
229        // Update offset
230        let gep = downcast_ref::<GetElementPtr>(inst.as_ref().as_ref());
231        let mut element_type = gep.element_type.clone();
232        for op in inst.get_operand().iter().skip(1) {
233            if let Some(old_offset) = offset.get_mut(&element_type) {
234                // Handle only +0 or 0+ in this case, UB otherwise
235                if let Operand::Constant(Constant::Int(0)) = old_offset {
236                    *old_offset = op.clone();
237                } else if let Operand::Constant(Constant::Int(0)) = op {
238                    // Do nothing
239                } else {
240                    unimplemented!("Unsupported GEP offset: {} + {}", old_offset, op);
241                }
242            } else {
243                offset.insert(element_type.clone(), op.clone());
244            }
245            if let Some(subtype) = element_type.get_sub_type() {
246                element_type = subtype.clone();
247            }
248        }
249    }
250    (base, offset)
251}
252
253/// Check if two indexing operands can equal.
254fn can_equal(a: Operand, b: Operand) -> bool {
255    match (a, b) {
256        // Constants only equal when they're the same
257        (Operand::Constant(a), Operand::Constant(b)) => a == b,
258
259        // Other operands can always equal (give up predicate analysis)
260        _ => true,
261    }
262}
duskphantom_middle/analysis/alias_analysis.rs

duskphantom_middle/analysis/
alias_analysis.rs
