falcon/analysis/
reaching_definitions.rs

1use crate::analysis::{fixed_point, LocationSet};
2use crate::il;
3use crate::Error;
4use std::collections::HashMap;
5
6/// Compute reaching definitions for the given function.
7pub fn reaching_definitions(
8    function: &il::Function,
9) -> Result<HashMap<il::ProgramLocation, LocationSet>, Error> {
10    let rda = ReachingDefinitionsAnalysis { function };
11    fixed_point::fixed_point_forward(rda, function)
12}
13
14// We require a struct to implement methods for our analysis over.
15struct ReachingDefinitionsAnalysis<'r> {
16    function: &'r il::Function,
17}
18
19impl<'r> fixed_point::FixedPointAnalysis<'r, LocationSet> for ReachingDefinitionsAnalysis<'r> {
20    fn trans(
21        &self,
22        location: il::RefProgramLocation<'r>,
23        state: Option<LocationSet>,
24    ) -> Result<LocationSet, Error> {
25        let mut state = match state {
26            Some(state) => state,
27            None => LocationSet::new(),
28        };
29
30        match *location.function_location() {
31            il::RefFunctionLocation::Instruction(_, instruction) => {
32                instruction
33                    .operation()
34                    .scalars_written()
35                    .into_iter()
36                    .for_each(|scalar_written| {
37                        let kill: Vec<il::ProgramLocation> = state
38                            .locations()
39                            .iter()
40                            .filter(|location| {
41                                location
42                                    .function_location()
43                                    .apply(self.function)
44                                    .unwrap()
45                                    .instruction()
46                                    .unwrap()
47                                    .operation()
48                                    .scalars_written()
49                                    .into_iter()
50                                    .any(|scalar| scalar == scalar_written)
51                            })
52                            .cloned()
53                            .collect();
54                        kill.iter().for_each(|location| state.remove(location));
55                        state.insert(location.clone().into());
56                    });
57            }
58            il::RefFunctionLocation::EmptyBlock(_) | il::RefFunctionLocation::Edge(_) => {}
59        }
60
61        Ok(state)
62    }
63
64    fn join(&self, mut state0: LocationSet, state1: &LocationSet) -> Result<LocationSet, Error> {
65        state1
66            .locations()
67            .iter()
68            .for_each(|location| state0.insert(location.clone()));
69        Ok(state0)
70    }
71}
72
73#[test]
74fn reaching_definitions_test() {
75    /*
76    a = in
77    b = 4
78    if a < 10 {
79        c = a
80        [0xdeadbeef] = c
81    }
82    else {
83        c = b
84    }
85    b = c
86    c = [0xdeadbeef]
87    */
88    let mut control_flow_graph = il::ControlFlowGraph::new();
89
90    let head_index = {
91        let block = control_flow_graph.new_block().unwrap();
92
93        block.assign(il::scalar("a", 32), il::expr_scalar("in", 32));
94        block.assign(il::scalar("b", 32), il::expr_const(4, 32));
95
96        block.index()
97    };
98
99    let gt_index = {
100        let block = control_flow_graph.new_block().unwrap();
101
102        block.assign(il::scalar("c", 32), il::expr_scalar("b", 32));
103
104        block.index()
105    };
106
107    let lt_index = {
108        let block = control_flow_graph.new_block().unwrap();
109
110        block.assign(il::scalar("c", 32), il::expr_scalar("a", 32));
111        block.store(il::expr_const(0xdeadbeef, 32), il::expr_scalar("c", 32));
112
113        block.index()
114    };
115
116    let tail_index = {
117        let block = control_flow_graph.new_block().unwrap();
118
119        block.assign(il::scalar("b", 32), il::expr_scalar("c", 32));
120        block.load(il::scalar("c", 32), il::expr_const(0xdeadbeef, 32));
121
122        block.index()
123    };
124
125    let condition =
126        il::Expression::cmpltu(il::expr_scalar("a", 32), il::expr_const(10, 32)).unwrap();
127
128    control_flow_graph
129        .conditional_edge(head_index, lt_index, condition.clone())
130        .unwrap();
131    control_flow_graph
132        .conditional_edge(
133            head_index,
134            gt_index,
135            il::Expression::cmpeq(condition, il::expr_const(0, 1)).unwrap(),
136        )
137        .unwrap();
138
139    control_flow_graph
140        .unconditional_edge(lt_index, tail_index)
141        .unwrap();
142    control_flow_graph
143        .unconditional_edge(gt_index, tail_index)
144        .unwrap();
145
146    control_flow_graph.set_entry(head_index).unwrap();
147
148    let function = il::Function::new(0, control_flow_graph);
149
150    let rd = reaching_definitions(&function).unwrap();
151
152    // for r in rd.iter() {
153    //     println!("{}", r.0);
154    //     for d in r.1 {
155    //         println!("  {}", d);
156    //     }
157    // }
158
159    let block = function.control_flow_graph().block(3).unwrap();
160    let instruction = block.instruction(0).unwrap();
161
162    let function_location = il::RefFunctionLocation::Instruction(block, instruction);
163    let program_location = il::RefProgramLocation::new(&function, function_location);
164
165    let r = &rd[&program_location.into()];
166
167    let block = function.control_flow_graph().block(0).unwrap();
168    assert!(r.contains(
169        &il::RefProgramLocation::new(
170            &function,
171            il::RefFunctionLocation::Instruction(block, block.instruction(0).unwrap())
172        )
173        .into()
174    ));
175
176    let block = function.control_flow_graph().block(1).unwrap();
177    assert!(r.contains(
178        &il::RefProgramLocation::new(
179            &function,
180            il::RefFunctionLocation::Instruction(block, block.instruction(0).unwrap())
181        )
182        .into()
183    ));
184
185    let block = function.control_flow_graph().block(2).unwrap();
186    assert!(r.contains(
187        &il::RefProgramLocation::new(
188            &function,
189            il::RefFunctionLocation::Instruction(block, block.instruction(0).unwrap())
190        )
191        .into()
192    ));
193
194    let block = function.control_flow_graph().block(3).unwrap();
195    assert!(r.contains(
196        &il::RefProgramLocation::new(
197            &function,
198            il::RefFunctionLocation::Instruction(block, block.instruction(0).unwrap())
199        )
200        .into()
201    ));
202
203    let block = function.control_flow_graph().block(0).unwrap();
204    assert!(!r.contains(
205        &il::RefProgramLocation::new(
206            &function,
207            il::RefFunctionLocation::Instruction(block, block.instruction(1).unwrap())
208        )
209        .into()
210    ));
211}
falcon/analysis/reaching_definitions.rs

falcon/analysis/
reaching_definitions.rs
