rapx/analysis/core/alias_analysis/default/
mop.rs1use super::{graph::*, *};
2use rustc_data_structures::fx::FxHashSet;
3use rustc_hir::def_id::DefId;
4use rustc_middle::{
5 mir::{
6 Operand::{Constant, Copy, Move},
7 TerminatorKind,
8 },
9 ty::TypingEnv,
10};
11use std::{
12 collections::{HashMap, HashSet},
13 env,
14};
15
16impl<'tcx> MopGraph<'tcx> {
17 pub fn split_check(
18 &mut self,
19 bb_index: usize,
20 fn_map: &mut FxHashMap<DefId, AAResult>,
21 recursion_set: &mut HashSet<DefId>,
22 ) {
23 let backup_values = self.values.clone(); let backup_constant = self.constant.clone();
26 let backup_alias_set = self.alias_set.clone();
27 self.check(bb_index, fn_map, recursion_set);
28 self.alias_set = backup_alias_set;
30 self.values = backup_values;
31 self.constant = backup_constant;
32 }
33 pub fn split_check_with_cond(
34 &mut self,
35 bb_index: usize,
36 path_discr_id: usize,
37 path_discr_val: usize,
38 fn_map: &mut FxHashMap<DefId, AAResult>,
39 recursion_set: &mut HashSet<DefId>,
40 ) {
41 let backup_values = self.values.clone(); let backup_constant = self.constant.clone();
44 let backup_alias_set = self.alias_set.clone();
45 self.constant.insert(path_discr_id, path_discr_val);
47 self.check(bb_index, fn_map, recursion_set);
48 self.alias_set = backup_alias_set;
50 self.values = backup_values;
51 self.constant = backup_constant;
52 }
53
54 pub fn check(
56 &mut self,
57 bb_index: usize,
58 fn_map: &mut FxHashMap<DefId, AAResult>,
59 recursion_set: &mut HashSet<DefId>,
60 ) {
61 self.visit_times += 1;
62 if self.visit_times > VISIT_LIMIT {
63 return;
64 }
65 let cur_block = self.blocks[self.scc_indices[bb_index]].clone();
66 self.alias_bb(self.scc_indices[bb_index]);
67 self.alias_bbcall(self.scc_indices[bb_index], fn_map, recursion_set);
68
69 if self.child_scc.get(&self.scc_indices[bb_index]).is_some() {
70 let init_index = self.scc_indices[bb_index];
71 let (init_block, cur_targets, scc_block_set) =
72 self.child_scc.get(&init_index).unwrap().clone();
73
74 for enum_index in cur_targets.all_targets() {
75 let backup_values = self.values.clone();
76 let backup_constant = self.constant.clone();
77
78 let mut block_node = if bb_index == init_index {
79 init_block.clone()
80 } else {
81 self.blocks[bb_index].clone()
82 };
83
84 if !block_node.switch_stmts.is_empty() {
85 let TerminatorKind::SwitchInt { discr: _, targets } =
86 block_node.switch_stmts[0].kind.clone()
87 else {
88 unreachable!();
89 };
90 if cur_targets == targets {
91 block_node.next = FxHashSet::default();
92 block_node.next.insert(enum_index.index());
93 }
94 }
95
96 let mut work_list = Vec::new();
97 let mut work_set = FxHashSet::<usize>::default();
98 work_list.push(bb_index);
99 work_set.insert(bb_index);
100 while !work_list.is_empty() {
101 let current_node = work_list.pop().unwrap();
102 block_node.scc_sub_blocks.push(current_node);
103 let real_node = if current_node != init_index {
104 self.blocks[current_node].clone()
105 } else {
106 init_block.clone()
107 };
108
109 if real_node.switch_stmts.is_empty() {
110 for next in &real_node.next {
111 block_node.next.insert(*next);
112 }
113 } else {
114 let TerminatorKind::SwitchInt {
115 discr: _,
116 ref targets,
117 } = real_node.switch_stmts[0].kind
118 else {
119 unreachable!();
120 };
121
122 if cur_targets == *targets {
123 block_node.next.insert(enum_index.index());
124 } else {
125 for next in &real_node.next {
126 block_node.next.insert(*next);
127 }
128 }
129 }
130
131 if real_node.switch_stmts.is_empty() {
132 for next in &real_node.next {
133 if scc_block_set.contains(next) && !work_set.contains(next) {
134 work_set.insert(*next);
135 work_list.push(*next);
136 }
137 }
138 } else {
139 let TerminatorKind::SwitchInt {
140 discr: _,
141 ref targets,
142 } = real_node.switch_stmts[0].kind
143 else {
144 unreachable!();
145 };
146
147 if cur_targets == *targets {
148 let next_index = enum_index.index();
149 if scc_block_set.contains(&next_index)
150 && !work_set.contains(&next_index)
151 {
152 work_set.insert(next_index);
153 work_list.push(next_index);
154 }
155 } else {
156 for next in &real_node.next {
157 if scc_block_set.contains(next) && !work_set.contains(next) {
158 work_set.insert(*next);
159 work_list.push(*next);
160 }
161 }
162 }
163 }
164 }
165
166 let mut to_remove = Vec::new();
168 for i in block_node.next.iter() {
169 if self.scc_indices[*i] == init_index {
170 to_remove.push(*i);
171 }
172 }
173 for i in to_remove {
174 block_node.next.remove(&i);
175 }
176
177 for i in block_node.scc_sub_blocks.clone() {
178 self.alias_bb(i);
179 self.alias_bbcall(i, fn_map, recursion_set);
180 }
181 match block_node.next.len() {
183 0 => {}
184 _ => {
185 for next in block_node.next {
190 self.check(next, fn_map, recursion_set);
191 }
192 }
193 }
194
195 self.values = backup_values;
196 self.constant = backup_constant;
197 }
198
199 return;
200 }
201
202 let mut order = vec![];
203 order.push(vec![]);
204
205 if !cur_block.scc_sub_blocks.is_empty() {
207 match env::var_os("MOP") {
208 Some(val) if val == "0" => {
209 order.push(cur_block.scc_sub_blocks.clone());
210 }
211 _ => {
212 self.calculate_scc_order(
213 &mut cur_block.scc_sub_blocks.clone(),
214 &mut vec![],
215 &mut order,
216 &mut HashMap::new(),
217 bb_index,
218 bb_index,
219 &mut HashSet::new(),
220 );
221 }
222 }
223 }
224
225 let backup_values = self.values.clone(); let backup_constant = self.constant.clone();
227 let backup_alias_set = self.alias_set.clone();
228 let backup_fn_map = fn_map.clone();
229 let backup_recursion_set = recursion_set.clone();
230 for scc_each in order {
231 self.alias_set = backup_alias_set.clone();
232 self.values = backup_values.clone();
233 self.constant = backup_constant.clone();
234 *fn_map = backup_fn_map.clone();
235 *recursion_set = backup_recursion_set.clone();
236
237 if !scc_each.is_empty() {
238 for idx in scc_each {
239 self.alias_bb(idx);
240 self.alias_bbcall(idx, fn_map, recursion_set);
241 }
242 }
243
244 let cur_block = cur_block.clone();
245 match cur_block.next.len() {
247 0 => {
248 let results_nodes = self.values.clone();
249 self.merge_results(results_nodes);
250 return;
251 }
252 1 => {
253 for next in cur_block.next {
258 self.check(next, fn_map, recursion_set);
259 }
260 return;
261 }
262 _ => { }
264 }
265
266 let mut single_target = false;
268 let mut sw_val = 0;
269 let mut sw_target = 0; let mut path_discr_id = 0; let mut sw_targets = None; if !cur_block.switch_stmts.is_empty() && cur_block.scc_sub_blocks.is_empty() {
273 if let TerminatorKind::SwitchInt {
274 ref discr,
275 ref targets,
276 } = cur_block.switch_stmts[0].clone().kind
277 {
278 match discr {
279 Copy(p) | Move(p) => {
280 let place = self.projection(false, *p);
281 if let Some(father) = self.disc_map.get(&self.values[place].local) {
282 if let Some(constant) = self.constant.get(father) {
283 if *constant != usize::MAX {
284 single_target = true;
285 sw_val = *constant;
286 }
287 }
288 if self.values[place].local == place {
289 path_discr_id = *father;
290 sw_targets = Some(targets.clone());
291 }
292 }
293 }
294 Constant(c) => {
295 single_target = true;
296 let ty_env = TypingEnv::post_analysis(self.tcx, self.def_id);
297 if let Some(val) = c.const_.try_eval_target_usize(self.tcx, ty_env) {
298 sw_val = val as usize;
299 }
300 }
301 }
302 if single_target {
303 for iter in targets.iter() {
308 if iter.0 as usize == sw_val {
309 sw_target = iter.1.as_usize();
310 break;
311 }
312 }
313 if sw_target == 0 {
318 let all_target = targets.all_targets();
319 sw_target = all_target[all_target.len() - 1].as_usize();
320 }
321 }
322 }
323 }
324 if single_target {
327 self.check(sw_target, fn_map, recursion_set);
328 } else {
329 if let Some(targets) = sw_targets {
331 for iter in targets.iter() {
332 if self.visit_times > VISIT_LIMIT {
333 continue;
334 }
335 let next_index = iter.1.as_usize();
336 let path_discr_val = iter.0 as usize;
337 self.split_check_with_cond(
338 next_index,
339 path_discr_id,
340 path_discr_val,
341 fn_map,
342 recursion_set,
343 );
344 }
345 let all_targets = targets.all_targets();
346 let next_index = all_targets[all_targets.len() - 1].as_usize();
347 let path_discr_val = usize::MAX; self.split_check_with_cond(
349 next_index,
350 path_discr_id,
351 path_discr_val,
352 fn_map,
353 recursion_set,
354 );
355 } else {
356 for i in cur_block.next {
357 if self.visit_times > VISIT_LIMIT {
358 continue;
359 }
360 let next_index = i;
361 self.split_check(next_index, fn_map, recursion_set);
362 }
363 }
364 }
365 }
366 }
367
368 pub fn calculate_scc_order(
369 &mut self,
370 scc: &Vec<usize>,
371 path: &mut Vec<usize>,
372 ans: &mut Vec<Vec<usize>>,
373 disc_map: &mut HashMap<usize, usize>,
374 idx: usize,
375 root: usize,
376 visit: &mut HashSet<usize>,
377 ) {
378 if idx == root && !path.is_empty() {
379 ans.push(path.clone());
380 return;
381 }
382 visit.insert(idx);
383 let term = &self.terms[idx].clone();
384
385 match term {
386 TerminatorKind::SwitchInt {
387 ref discr,
388 ref targets,
389 } => match discr {
390 Copy(p) | Move(p) => {
391 let place = self.projection(false, *p);
392 if let Some(father) = self.disc_map.get(&self.values[place].local) {
393 let father = *father;
394 if let Some(constant) = disc_map.get(&father) {
395 let constant = *constant;
396 for t in targets.iter() {
397 if t.0 as usize == constant {
398 let target = t.1.as_usize();
399 if path.contains(&target) {
400 continue;
401 }
402 path.push(target);
403 self.calculate_scc_order(
404 scc, path, ans, disc_map, target, root, visit,
405 );
406 path.pop();
407 }
408 }
409 } else {
410 for t in targets.iter() {
411 let constant = t.0 as usize;
412 let target = t.1.as_usize();
413 if path.contains(&target) {
414 continue;
415 }
416 path.push(target);
417 disc_map.insert(father, constant);
418 self.calculate_scc_order(
419 scc, path, ans, disc_map, target, root, visit,
420 );
421 disc_map.remove(&father);
422 path.pop();
423 }
424 }
425 } else {
426 if let Some(constant) = disc_map.get(&place) {
427 let constant = *constant;
428 for t in targets.iter() {
429 if t.0 as usize == constant {
430 let target = t.1.as_usize();
431 if path.contains(&target) {
432 continue;
433 }
434 path.push(target);
435 self.calculate_scc_order(
436 scc, path, ans, disc_map, target, root, visit,
437 );
438 path.pop();
439 }
440 }
441 } else {
442 for t in targets.iter() {
443 let constant = t.0 as usize;
444 let target = t.1.as_usize();
445 if path.contains(&target) {
446 continue;
447 }
448 path.push(target);
449 disc_map.insert(place, constant);
450 self.calculate_scc_order(
451 scc, path, ans, disc_map, target, root, visit,
452 );
453 disc_map.remove(&place);
454 path.pop();
455 }
456
457 let constant = targets.iter().len();
458 let target = targets.otherwise().as_usize();
459 if !path.contains(&target) {
460 path.push(target);
461 disc_map.insert(place, constant);
462 self.calculate_scc_order(
463 scc, path, ans, disc_map, target, root, visit,
464 );
465 disc_map.remove(&place);
466 path.pop();
467 }
468 }
469 }
470 }
471 _ => {}
472 },
473 _ => {
474 for bidx in self.blocks[idx].next.clone() {
475 if !scc.contains(&bidx) && bidx != root {
476 continue;
477 }
478 if bidx != root {
479 path.push(bidx);
480 self.calculate_scc_order(scc, path, ans, disc_map, bidx, root, visit);
481 path.pop();
482 } else {
483 self.calculate_scc_order(scc, path, ans, disc_map, bidx, root, visit);
484 }
485 }
486 }
487 }
488
489 visit.remove(&idx);
490 }
491}