gbf_core/decompiler/structure_analysis/
linear_region_reducer.rs

1#![deny(missing_docs)]
2
3use std::backtrace::Backtrace;
4
5use super::{
6    RegionReducer, StructureAnalysis, StructureAnalysisError,
7    region::{RegionId, RegionType},
8};
9
10/// Reduces a linear region.
11pub struct LinearRegionReducer;
12
13impl LinearRegionReducer {
14    /// Merge two regions.
15    fn merge_regions(
16        &mut self,
17        analysis: &mut StructureAnalysis,
18        from_region_id: RegionId,
19        to_region_id: RegionId,
20    ) -> Result<(), StructureAnalysisError> {
21        let (from_nodes, from_jump_expr, region_type) = {
22            let from_region = analysis.regions.get_mut(from_region_id.index).ok_or(
23                StructureAnalysisError::RegionNotFound {
24                    region_id: from_region_id,
25                    backtrace: Backtrace::capture(),
26                },
27            )?;
28            (
29                from_region.get_nodes().to_vec(),
30                from_region.get_jump_expr().cloned(),
31                *from_region.region_type(),
32            )
33        };
34
35        let to_region = analysis.regions.get_mut(to_region_id.index).ok_or(
36            StructureAnalysisError::RegionNotFound {
37                region_id: to_region_id,
38                backtrace: Backtrace::capture(),
39            },
40        )?;
41
42        if region_type == RegionType::Inactive {
43            return Err(StructureAnalysisError::Other {
44                message: "Cannot merge inactive region".to_string(),
45                backtrace: Backtrace::capture(),
46            });
47        }
48
49        to_region.push_nodes(from_nodes);
50        to_region.set_jump_expr(from_jump_expr);
51        to_region.set_region_type(region_type);
52
53        Ok(())
54    }
55}
56
57impl RegionReducer for LinearRegionReducer {
58    fn reduce_region(
59        &mut self,
60        analysis: &mut StructureAnalysis,
61        region_id: RegionId,
62    ) -> Result<bool, StructureAnalysisError> {
63        let succ = analysis.get_single_successor(region_id)?.ok_or_else(|| {
64            StructureAnalysisError::Other {
65                message: "Linear region does not have exactly one successor".to_string(),
66                backtrace: Backtrace::capture(),
67            }
68        })?;
69
70        if !analysis.has_single_predecessor(succ)? {
71            return Ok(false);
72        }
73
74        // Call the before_reduce hook
75        analysis.before_reduce(region_id);
76        self.merge_regions(analysis, succ, region_id)?;
77        analysis.remove_edge(region_id, succ)?;
78
79        // For each successor of the successor region, add an edge from the region to the successor
80        for (succ_succ, edge_type) in analysis.get_successors(succ)? {
81            analysis.connect_regions(region_id, succ_succ, edge_type)?;
82            analysis.remove_edge(succ, succ_succ)?;
83        }
84
85        // Remove the successor region
86        analysis.remove_node(succ)?;
87        Ok(true)
88    }
89}
90
91#[cfg(test)]
92mod tests {
93    use crate::decompiler::{
94        ast::{new_assignment, new_id},
95        structure_analysis::ControlFlowEdgeType,
96    };
97
98    use super::*;
99
100    #[test]
101    fn test_linear_reduce() -> Result<(), StructureAnalysisError> {
102        let mut structure_analysis = StructureAnalysis::new(false, 100);
103
104        let entry_region = structure_analysis.add_region(RegionType::Linear);
105        let region_1 = structure_analysis.add_region(RegionType::Linear);
106        let region_2 = structure_analysis.add_region(RegionType::Linear);
107        let region_3 = structure_analysis.add_region(RegionType::Tail);
108
109        // push nodes to the regions
110        structure_analysis
111            .push_to_region(entry_region, new_assignment(new_id("foo"), new_id("bar")));
112        structure_analysis.push_to_region(region_1, new_assignment(new_id("foo2"), new_id("bar2")));
113        structure_analysis.push_to_region(region_1, new_assignment(new_id("foo3"), new_id("bar3")));
114        structure_analysis.push_to_region(region_2, new_assignment(new_id("foo4"), new_id("bar4")));
115        structure_analysis.push_to_region(region_2, new_assignment(new_id("foo5"), new_id("bar5")));
116        structure_analysis.push_to_region(region_3, new_assignment(new_id("foo6"), new_id("bar6")));
117        structure_analysis.connect_regions(entry_region, region_1, ControlFlowEdgeType::Branch)?;
118        structure_analysis.connect_regions(region_1, region_2, ControlFlowEdgeType::Branch)?;
119        structure_analysis.connect_regions(region_2, region_3, ControlFlowEdgeType::Branch)?;
120        structure_analysis.execute()?;
121
122        assert_eq!(structure_analysis.region_graph.node_count(), 1);
123
124        let region = structure_analysis.get_entry_region();
125        let region = structure_analysis.get_region(region)?;
126        assert_eq!(region.get_nodes().len(), 6);
127
128        // ensure that the final region is a tail region
129        assert_eq!(region.get_region_type(), RegionType::Tail);
130
131        Ok(())
132    }
133}
gbf_core/decompiler/structure_analysis/linear_region_reducer.rs

gbf_core/decompiler/structure_analysis/
linear_region_reducer.rs
