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