rapx/analysis/core/alias_analysis/default/
alias.rs1use crate::{
2 analysis::{
3 core::alias_analysis::{default::graph::*, AAFact, AAResult},
4 utils::intrinsic_id::*,
5 },
6 rap_debug,
7};
8use rustc_data_structures::fx::FxHashMap;
9use rustc_hir::def_id::DefId;
10use rustc_middle::{
11 mir::{Operand, Place, ProjectionElem, TerminatorKind},
12 ty,
13};
14use std::collections::HashSet;
15
16impl<'tcx> MopGraph<'tcx> {
17 pub fn alias_bb(&mut self, bb_index: usize) {
19 for stmt in self.blocks[bb_index].const_value.clone() {
20 self.constant.insert(stmt.0, stmt.1);
21 }
22 let cur_block = self.blocks[bb_index].clone();
23 for assign in cur_block.assignments {
24 let mut lv_aliaset_idx = self.projection(false, assign.lv);
25 let rv_aliaset_idx = self.projection(true, assign.rv);
26 rap_debug!("{:?} = {:?}", lv_aliaset_idx, rv_aliaset_idx);
27 match assign.atype {
28 AssignType::Variant => {
29 self.alias_set[lv_aliaset_idx] = rv_aliaset_idx;
30 continue;
31 }
32 AssignType::InitBox => {
33 lv_aliaset_idx = *self.values[lv_aliaset_idx].fields.get(&0).unwrap();
34 }
35 _ => {} }
37 if self.values[lv_aliaset_idx].local != self.values[rv_aliaset_idx].local {
38 self.merge_alias(lv_aliaset_idx, rv_aliaset_idx, 0);
39 }
40 }
41 }
42
43 pub fn alias_bbcall(
45 &mut self,
46 bb_index: usize,
47 fn_map: &mut FxHashMap<DefId, AAResult>,
48 recursion_set: &mut HashSet<DefId>,
49 ) {
50 let cur_block = self.blocks[bb_index].clone();
51 for call in cur_block.calls {
52 if let TerminatorKind::Call {
53 func: Operand::Constant(ref constant),
54 ref args,
55 ref destination,
56 target: _,
57 unwind: _,
58 call_source: _,
59 fn_span: _,
60 } = call.kind
61 {
62 let lv = self.projection(false, *destination);
63 let mut merge_vec = Vec::new();
64 merge_vec.push(lv);
65 for arg in args {
66 match arg.node {
67 Operand::Copy(ref p) => {
68 let rv = self.projection(true, *p);
69 merge_vec.push(rv);
70 }
71 Operand::Move(ref p) => {
72 let rv = self.projection(true, *p);
73 merge_vec.push(rv);
74 }
75 Operand::Constant(_) => {
76 merge_vec.push(0);
77 }
78 }
79 }
80 if let ty::FnDef(ref target_id, _) = constant.const_.ty().kind() {
81 if self.tcx.is_mir_available(*target_id) {
82 rap_debug!("target_id {:?}", target_id);
83 if fn_map.contains_key(target_id) {
84 let assignments = fn_map.get(target_id).unwrap();
85 for assign in assignments.aliases().iter() {
86 self.merge(assign, &merge_vec);
87 }
88 } else {
89 if recursion_set.contains(target_id) {
91 continue;
92 }
93 recursion_set.insert(*target_id);
94 let mut mop_graph = MopGraph::new(self.tcx, *target_id);
95 mop_graph.solve_scc();
96 mop_graph.check(0, fn_map, recursion_set);
97 let ret_alias = mop_graph.ret_alias.clone();
98 for assign in ret_alias.aliases().iter() {
99 self.merge(assign, &merge_vec);
100 }
101 fn_map.insert(*target_id, ret_alias);
102 recursion_set.remove(target_id);
103 }
104 } else {
105 if target_id.index.as_usize() == CALL_MUT {
106 continue;
107 }
108
109 let mut right_set = Vec::new();
110 for rv in &merge_vec {
111 if lv != *rv {
112 right_set.push(*rv);
113 }
114 }
115 if right_set.len() == 1 {
116 self.merge_alias(lv, right_set[0], 0);
117 }
118 }
119 }
120 }
121 }
122 }
123
124 pub fn projection(&mut self, is_right: bool, place: Place<'tcx>) -> usize {
131 let mut local = place.local.as_usize();
132 let mut proj_id: usize = local;
133 for proj in place.projection {
134 let new_id = self.values.len();
135 match proj {
136 ProjectionElem::Deref => {
137 proj_id = self.values[proj_id].index;
138 }
139 ProjectionElem::Field(field, _ty) => {
143 if is_right && self.values[proj_id].index != proj_id {
144 proj_id = self.values[proj_id].index;
145 local = self.values[proj_id].local;
146 }
147 let field_idx = field.as_usize();
148 if let std::collections::hash_map::Entry::Vacant(e) =
149 self.values[proj_id].fields.entry(field_idx)
150 {
151 let mut node = ValueNode::new(new_id, local);
152 node.field_id = field_idx;
153 e.insert(node.index);
154 self.alias_set.push(self.values.len());
155 self.values.push(node);
156 }
157 proj_id = *self.values[proj_id].fields.get(&field_idx).unwrap();
158 }
159 _ => {}
160 }
161 }
162 proj_id
163 }
164
165 pub fn merge_alias(&mut self, lv: usize, rv: usize, depth: usize) {
167 rap_debug!("Alias set now: {:?}", self.alias_set);
168 self.union_merge(lv, rv);
170 rap_debug!(
172 "Update the alias set for lv:{} rv:{} set:{:?}",
173 lv,
174 rv,
175 self.alias_set
176 );
177
178 let max_field_depth = match std::env::var_os("ALIAS") {
179 Some(val) if val == "0" => 10,
180 Some(val) if val == "1" => 20,
181 Some(val) if val == "2" => 30,
182 Some(val) if val == "3" => 50,
183 _ => 15,
184 };
185
186 if depth > max_field_depth {
187 return;
188 }
189
190 for field in self.values[rv].fields.clone().into_iter() {
191 if !self.values[lv].fields.contains_key(&field.0) {
192 let mut node = ValueNode::new(self.values.len(), self.values[lv].local);
193 node.field_id = field.0;
194 self.values[lv].fields.insert(field.0, node.index);
195 self.alias_set.push(self.values.len());
196 self.values.push(node);
197 }
198 let lv_field = *(self.values[lv].fields.get(&field.0).unwrap());
199 self.merge_alias(lv_field, field.1, depth + 1);
200 }
201 }
202
203 pub fn merge(&mut self, ret_alias: &AAFact, arg_vec: &[usize]) {
205 rap_debug!("{:?}", ret_alias);
206 if ret_alias.lhs_no() >= arg_vec.len() || ret_alias.rhs_no() >= arg_vec.len() {
207 rap_debug!("Vector error!");
208 return;
209 }
210 let left_init = arg_vec[ret_alias.lhs_no()];
211 let mut right_init = arg_vec[ret_alias.rhs_no()];
212 let mut lv = left_init;
213 let mut rv = right_init;
214 for index in ret_alias.lhs_fields().iter() {
215 if !self.values[lv].fields.contains_key(index) {
216 let mut node = ValueNode::new(self.values.len(), left_init);
217 node.field_id = *index;
218 self.values[lv].fields.insert(*index, node.index);
219 self.alias_set.push(self.values.len());
220 self.values.push(node);
221 }
222 lv = *self.values[lv].fields.get(index).unwrap();
223 }
224 for index in ret_alias.rhs_fields().iter() {
225 if self.union_is_same(rv, self.alias_set[rv]) {
226 right_init = self.values[rv].local;
227 }
228 if !self.values[rv].fields.contains_key(index) {
229 let mut node = ValueNode::new(self.values.len(), right_init);
230 node.field_id = *index;
231 self.values[rv].fields.insert(*index, node.index);
232 self.alias_set.push(self.values.len());
233 self.values.push(node);
234 }
235 rv = *self.values[rv].fields.get(index).unwrap();
236 }
237 self.merge_alias(lv, rv, 0);
238 }
239
240 pub fn merge_results(&mut self, results_nodes: Vec<ValueNode>) {
242 for node in results_nodes.iter() {
243 if node.local <= self.arg_size
244 && (self.union_is_same(node.index, self.alias_set[node.index])
245 || self.alias_set[node.index] != node.index)
246 {
247 if self.values.len() == 1 {
248 return;
249 }
250 let f_node: Vec<usize> = results_nodes.iter().map(|v| v.father).collect();
251
252 for idx in 1..self.values.len() {
253 if !self.union_is_same(idx, node.index) {
254 continue;
255 }
256
257 let mut replace = None;
258 if results_nodes[idx].local > self.arg_size {
259 for (i, &fidx) in f_node.iter().enumerate() {
260 if i != idx && i != node.index && fidx == f_node[idx] {
261 for (j, v) in results_nodes.iter().enumerate() {
262 if j != idx
263 && j != node.index
264 && self.union_is_same(j, fidx)
265 && v.local <= self.arg_size
266 {
267 replace = Some(&results_nodes[j]);
268 }
269 }
270 }
271 }
272 }
273
274 if (results_nodes[idx].local <= self.arg_size || replace.is_some())
275 && idx != node.index
276 && node.local != results_nodes[idx].local
277 {
278 let left_node;
279 let right_node;
280 match results_nodes[idx].local {
281 0 => {
282 left_node = match replace {
283 Some(replace_node) => replace_node,
284 None => &results_nodes[idx],
285 };
286 right_node = node;
287 }
288 _ => {
289 left_node = node;
290 right_node = match replace {
291 Some(replace_node) => replace_node,
292 None => &results_nodes[idx],
293 };
294 }
295 }
296 let mut new_alias = AAFact::new(left_node.local, right_node.local);
297 new_alias.lhs_fields = self.get_field_seq(left_node);
298 new_alias.rhs_fields = self.get_field_seq(right_node);
299 if new_alias.lhs_no() == 0 && new_alias.rhs_no() == 0 {
300 return;
301 }
302 self.ret_alias.add_alias(new_alias);
303 }
304 }
305 }
306 }
307 }
308
309 pub fn get_field_seq(&self, value: &ValueNode) -> Vec<usize> {
310 let mut field_id_seq = vec![];
311 let mut node_ref = value;
312 while node_ref.field_id != usize::MAX {
313 field_id_seq.push(node_ref.field_id);
314 node_ref = &self.values[value.father];
315 }
316 field_id_seq
317 }
318
319 #[inline]
320 pub fn union_find(&mut self, e: usize) -> usize {
321 let mut r = e;
322 while self.alias_set[r] != r {
323 r = self.alias_set[r];
324 }
325 r
326 }
327
328 #[inline]
329 pub fn union_merge(&mut self, e1: usize, e2: usize) {
330 let f1 = self.union_find(e1);
331 let f2 = self.union_find(e2);
332
333 if f1 < f2 {
334 self.alias_set[f2] = f1;
335 }
336 if f1 > f2 {
337 self.alias_set[f1] = f2;
338 }
339
340 for member in 0..self.alias_set.len() {
341 self.alias_set[member] = self.union_find(self.alias_set[member]);
342 }
343 }
344
345 #[inline]
346 pub fn union_is_same(&mut self, e1: usize, e2: usize) -> bool {
347 let f1 = self.union_find(e1);
348 let f2 = self.union_find(e2);
349 f1 == f2
350 }
351}