1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
use super::ControlFlowGraph;
use super::super::bitvec::BitVector;
use super::iterate::reverse_post_order;
use super::super::indexed_vec::{IndexVec, Idx};
#[cfg(test)]
mod test;
pub fn reachable<G: ControlFlowGraph>(graph: &G) -> Reachability<G::Node> {
let reverse_post_order = reverse_post_order(graph, graph.start_node());
reachable_given_rpo(graph, &reverse_post_order)
}
pub fn reachable_given_rpo<G: ControlFlowGraph>(graph: &G,
reverse_post_order: &[G::Node])
-> Reachability<G::Node> {
let mut reachability = Reachability::new(graph);
let mut changed = true;
while changed {
changed = false;
for &node in reverse_post_order.iter().rev() {
changed |= reachability.bits[node].insert(node.index());
for pred in graph.predecessors(node) {
let nodes_bits = reachability.bits[node].clone();
changed |= reachability.bits[pred].insert_all(&nodes_bits);
}
}
}
reachability
}
pub struct Reachability<Node: Idx> {
bits: IndexVec<Node, BitVector>,
}
impl<Node: Idx> Reachability<Node> {
fn new<G: ControlFlowGraph>(graph: &G) -> Self {
let num_nodes = graph.num_nodes();
Reachability { bits: IndexVec::from_elem_n(BitVector::new(num_nodes), num_nodes) }
}
pub fn can_reach(&self, source: Node, target: Node) -> bool {
let bit: usize = target.index();
self.bits[source].contains(bit)
}
}