rapx/analysis/rcanary/ranalyzer/
order.rs

1use rustc_middle::{mir::TerminatorKind, ty::InstanceKind::Item};
2
3use std::collections::BinaryHeap;
4//use stopwatch::Stopwatch;
5
6use super::super::ranalyzer::{FlowAnalysis, NodeOrder};
7use super::super::RcxMut;
8
9impl<'tcx, 'a> FlowAnalysis<'tcx, 'a> {
10    pub fn order(&mut self) {
11        // Get the Global TyCtxt from rustc
12        // Grasp all mir Keys defined in current crate
13
14        //let mut sw = Stopwatch::start_new();
15
16        let tcx = self.tcx();
17        let mir_keys = tcx.mir_keys(());
18
19        for each_mir in mir_keys {
20            // Get the defid of current crate and get mir Body through this id
21            let def_id = each_mir.to_def_id();
22            let body = tcx.instance_mir(Item(def_id));
23
24            let mut path = NodeOrder::new(body);
25            let mut lev: Vec<usize> = vec![0; body.basic_blocks.len()];
26
27            path.collect_edges(&mut lev);
28            path.topo_order(&mut lev);
29            self.rcx_mut()
30                .mir_graph_mut()
31                .insert(def_id, path.graph_mut().clone());
32        }
33    }
34}
35
36impl<'tcx> NodeOrder<'tcx> {
37    /// !Note: this function does not collect the edges that belongs to unwind paths.
38    pub(crate) fn collect_edges(&mut self, lev: &mut Vec<usize>) {
39        let bbs = &self.body().basic_blocks;
40        for (block, data) in bbs.iter().enumerate() {
41            let mut result: Vec<usize> = vec![];
42            match &data.terminator().kind {
43                TerminatorKind::Goto { target } => result.push(target.as_usize()),
44                TerminatorKind::SwitchInt { targets, .. } => {
45                    for bb in targets.all_targets() {
46                        result.push(bb.as_usize());
47                    }
48                }
49                TerminatorKind::Return => (),
50                TerminatorKind::Unreachable => (),
51                TerminatorKind::Drop { target, .. } => result.push(target.as_usize()),
52                TerminatorKind::Assert { target, .. } => result.push(target.as_usize()),
53                TerminatorKind::Yield { .. } => (),
54                TerminatorKind::FalseEdge { .. } => (),
55                TerminatorKind::FalseUnwind { .. } => (),
56                TerminatorKind::InlineAsm { .. } => (),
57                TerminatorKind::UnwindResume => (),
58                TerminatorKind::UnwindTerminate(..) => (),
59                TerminatorKind::CoroutineDrop => (),
60                TerminatorKind::Call { target, .. } => {
61                    // We check the destination due to following case.
62                    // Terminator { source_info: SourceInfo { span: src/main.rs:100:9: 100:35 (#7), scope: scope[0] },
63                    // kind: core::panicking::panic(const "assertion failed: index <= self.len") -> bb24 },
64                    // destination -> None, cleanup -> Some(bb24)
65                    match target {
66                        Some(t) => result.push(t.as_usize()),
67                        None => (),
68                    }
69                }
70                TerminatorKind::TailCall { .. } => todo!(),
71            }
72            // Update the lev for generating topo order.
73            for index in result.iter() {
74                lev[*index] = lev[*index] + 1;
75                self.graph_mut().get_pre_mut()[*index].push(block);
76            }
77            self.graph_mut().get_edges_mut()[block] = result;
78        }
79    }
80
81    pub(crate) fn topo_order(&mut self, lev: &mut Vec<usize>) {
82        let mut q: BinaryHeap<usize> = BinaryHeap::new();
83        q.push(0);
84        while !q.is_empty() {
85            let top = q.pop().unwrap();
86            self.graph_mut().get_topo_mut().push(top);
87            for cnt in 0..self.graph().e[top].len() {
88                let next = self.graph().e[top][cnt];
89                lev[next] = lev[next] - 1;
90                if lev[next] == 0 {
91                    q.push(next);
92                }
93            }
94        }
95    }
96}
rapx/analysis/rcanary/ranalyzer/order.rs

rapx/analysis/rcanary/ranalyzer/
order.rs
