rapx/analysis/range_analysis/
default.rs

1#![allow(unused_imports)]
2
3use crate::{
4    analysis::{
5        Analysis,
6        callgraph::{default::CallGraph, visitor::CallGraphVisitor},
7        path_analysis::default::PathAnalyzer,
8        range_analysis::{
9            Range, RangeAnalysis,
10            domain::{
11                ConstraintGraph::ConstraintGraph,
12                domain::{ConstConvert, IntervalArithmetic, VarNodes},
13            },
14        },
15        // SSA / ESSA transformation passes
16        ssa_transform::*,
17    },
18    graphs::scc::Scc,
19    rap_debug, rap_info,
20};
21
22use crate::compat::FxHashMap;
23use rustc_hir::{def::DefKind, def_id::DefId};
24use rustc_middle::{
25    mir::{Body, Place},
26    ty::TyCtxt,
27};
28use std::{
29    cell::RefCell,
30    collections::{HashMap, HashSet},
31    fmt::Debug,
32    fs::{self, File},
33    io::Write,
34    path::PathBuf,
35    rc::Rc,
36};
37
38use super::{PathConstraint, PathConstraintMap, RAResult, RAResultMap, RAVecResultMap};
39
40/// RangeAnalyzer performs MIR-based interprocedural range analysis.
41/// It builds SSA/ESSA, constraint graphs, propagates intervals,
42/// and optionally extracts path constraints.
43pub struct RangeAnalyzer<'tcx, T: IntervalArithmetic + ConstConvert + Debug> {
44    pub tcx: TyCtxt<'tcx>, // Compiler type context
45    pub debug: bool,       // Enable debug output
46
47    pub ssa_def_id: Option<DefId>,  // SSA marker function DefId
48    pub essa_def_id: Option<DefId>, // ESSA marker function DefId
49
50    pub final_vars: RAResultMap<'tcx, T>, // Final merged interval results
51
52    // Mapping from original places to SSA-renamed places
53    pub ssa_places_mapping: FxHashMap<DefId, HashMap<Place<'tcx>, HashSet<Place<'tcx>>>>,
54
55    pub fn_constraintgraph_mapping: FxHashMap<DefId, ConstraintGraph<'tcx, T>>,
56    pub callgraph: CallGraph<'tcx>,
57    pub body_map: FxHashMap<DefId, Body<'tcx>>,
58    pub cg_map: FxHashMap<DefId, Rc<RefCell<ConstraintGraph<'tcx, T>>>>,
59
60    // Variable nodes collected per function (per call context)
61    pub vars_map: FxHashMap<DefId, Vec<RefCell<VarNodes<'tcx, T>>>>,
62
63    pub final_vars_vec: RAVecResultMap<'tcx, T>, // Interval results per call
64
65    pub path_constraints: PathConstraintMap<'tcx>, // Path-sensitive constraints
66}
67
68impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> Analysis for RangeAnalyzer<'tcx, T>
69where
70    T: IntervalArithmetic + ConstConvert + Debug,
71{
72    fn name(&self) -> &'static str {
73        "Range Analysis"
74    }
75
76    /// Entry point of the analysis
77    fn run(&mut self) {
78        // self.start();
79        self.only_caller_range_analysis();
80        self.start_path_constraints_analysis();
81    }
82
83    fn reset(&mut self) {
84        self.final_vars.clear();
85        self.ssa_places_mapping.clear();
86    }
87}
88
89impl<'tcx, T: IntervalArithmetic + ConstConvert + Debug> RangeAnalysis<'tcx, T>
90    for RangeAnalyzer<'tcx, T>
91where
92    T: IntervalArithmetic + ConstConvert + Debug,
93{
94    fn get_fn_range(&self, def_id: DefId) -> Option<RAResult<'tcx, T>> {
95        self.final_vars.get(&def_id).cloned()
96    }
97
98    fn get_fn_ranges_percall(&self, def_id: DefId) -> Option<Vec<RAResult<'tcx, T>>> {
99        self.final_vars_vec.get(&def_id).cloned()
100    }
101
102    fn get_all_fn_ranges(&self) -> RAResultMap<'tcx, T> {
103        // Return a cloned map of all final ranges
104        self.final_vars.clone()
105    }
106
107    fn get_all_fn_ranges_percall(&self) -> RAVecResultMap<'tcx, T> {
108        self.final_vars_vec.clone()
109    }
110
111    /// Query the range of a specific local variable
112    fn get_fn_local_range(&self, def_id: DefId, place: Place<'tcx>) -> Option<Range<T>> {
113        self.final_vars
114            .get(&def_id)
115            .and_then(|vars| vars.get(&place).cloned())
116    }
117
118    fn get_fn_path_constraints(&self, def_id: DefId) -> Option<PathConstraint<'tcx>> {
119        self.path_constraints.get(&def_id).cloned()
120    }
121
122    fn get_all_path_constraints(&self) -> PathConstraintMap<'tcx> {
123        self.path_constraints.clone()
124    }
125}
126
127impl<'tcx, T> RangeAnalyzer<'tcx, T>
128where
129    T: IntervalArithmetic + ConstConvert + Debug,
130{
131    pub fn new(tcx: TyCtxt<'tcx>, debug: bool) -> Self {
132        let mut ssa_id = None;
133        let mut essa_id = None;
134
135        if let Some(ssa_def_id) = tcx.hir_crate_items(()).free_items().find(|id| {
136            let hir_id = id.hir_id();
137            if let Some(ident_name) = tcx.hir_opt_name(hir_id) {
138                ident_name.to_string() == "SSAstmt"
139            } else {
140                false
141            }
142        }) {
143            ssa_id = Some(ssa_def_id.owner_id.to_def_id());
144            if let Some(essa_def_id) = tcx.hir_crate_items(()).free_items().find(|id| {
145                let hir_id = id.hir_id();
146                if let Some(ident_name) = tcx.hir_opt_name(hir_id) {
147                    ident_name.to_string() == "ESSAstmt"
148                } else {
149                    false
150                }
151            }) {
152                essa_id = Some(essa_def_id.owner_id.to_def_id());
153            }
154        }
155        Self {
156            tcx: tcx,
157            debug,
158            ssa_def_id: ssa_id,
159            essa_def_id: essa_id,
160            final_vars: FxHashMap::default(),
161            ssa_places_mapping: FxHashMap::default(),
162            fn_constraintgraph_mapping: FxHashMap::default(),
163            callgraph: CallGraph::new(tcx),
164            body_map: FxHashMap::default(),
165            cg_map: FxHashMap::default(),
166            vars_map: FxHashMap::default(),
167            final_vars_vec: FxHashMap::default(),
168            path_constraints: FxHashMap::default(),
169        }
170    }
171
172    fn build_constraintgraph(&mut self, body_mut_ref: &'tcx Body<'tcx>, def_id: DefId) {
173        rap_debug!(
174            "Building ConstraintGraph for function: {}",
175            self.tcx.def_path_str(def_id)
176        );
177        let ssa_def_id = self.ssa_def_id.expect("SSA definition ID is not set");
178        let essa_def_id = self.essa_def_id.expect("ESSA definition ID is not set");
179        let mut cg: ConstraintGraph<'tcx, T> =
180            ConstraintGraph::new(body_mut_ref, self.tcx, def_id, essa_def_id, ssa_def_id);
181        cg.build_graph(body_mut_ref);
182        cg.build_nuutila(false);
183        // cg.rap_print_vars();
184        // cg.rap_print_final_vars();
185        let dot_output = cg.to_dot();
186        let vars_map = cg.get_vars().clone();
187
188        self.cg_map.insert(def_id, Rc::new(RefCell::new(cg)));
189        let mut vec = Vec::new();
190        vec.push(RefCell::new(vars_map));
191        self.vars_map.insert(def_id, vec);
192        let function_name = self.tcx.def_path_str(def_id);
193
194        let dir_path = PathBuf::from("cg_dot");
195        fs::create_dir_all(dir_path.clone()).unwrap();
196        let safe_filename = format!("{}_cg.dot", function_name);
197        let output_path = dir_path.join(format!("{}", safe_filename));
198
199        let mut file = File::create(&output_path).expect("cannot create file");
200        file.write_all(dot_output.as_bytes())
201            .expect("Could not write to file");
202
203        rap_trace!("Successfully generated graph.dot");
204    }
205
206    fn only_caller_range_analysis(&mut self) {
207        let ssa_def_id = self.ssa_def_id.expect("SSA definition ID is not set");
208        let essa_def_id = self.essa_def_id.expect("ESSA definition ID is not set");
209        // ====================================================================
210        // PHASE 1: Build all ConstraintGraphs and the complete CallGraph first.
211        // ====================================================================
212        rap_debug!("PHASE 1: Building all ConstraintGraphs and the CallGraph...");
213        for local_def_id in self.tcx.iter_local_def_id() {
214            if matches!(self.tcx.def_kind(local_def_id), DefKind::Fn) {
215                let def_id = local_def_id.to_def_id();
216
217                if self.tcx.is_mir_available(def_id) {
218                    rap_info!("Processing function: {}", self.tcx.def_path_str(def_id));
219                    let mut body = self.tcx.optimized_mir(def_id).clone();
220                    let body_mut_ref = unsafe { &mut *(&mut body as *mut Body<'tcx>) };
221                    // Run SSA/ESSA passes
222                    let mut passrunner = PassRunner::new(self.tcx);
223                    passrunner.run_pass(body_mut_ref, ssa_def_id, essa_def_id);
224                    self.body_map.insert(def_id, body);
225                    // Print the MIR after SSA/ESSA passes
226                    if self.debug {
227                        print_diff(self.tcx, body_mut_ref, def_id.into());
228                        print_mir_graph(self.tcx, body_mut_ref, def_id.into());
229                    }
230
231                    self.ssa_places_mapping
232                        .insert(def_id, passrunner.places_map.clone());
233                    // rap_debug!("ssa_places_mapping: {:?}", self.ssa_places_mapping);
234                    // Build and store the constraint graph
235                    self.build_constraintgraph(body_mut_ref, def_id);
236                    // Visit for call graph construction
237                    let mut call_graph_visitor =
238                        CallGraphVisitor::new(self.tcx, def_id, body_mut_ref, &mut self.callgraph);
239                    call_graph_visitor.visit();
240                }
241            }
242        }
243        rap_debug!("PHASE 1 Complete. ConstraintGraphs & CallGraphs built.");
244        // self.callgraph.print_call_graph(); // Optional: for debugging
245
246        // ====================================================================
247        // PHASE 2: Analyze only the call chain start functions.
248        // ====================================================================
249        rap_debug!("PHASE 2: Finding and analyzing call chain start functions...");
250
251        let mut call_chain_starts: Vec<DefId> = Vec::new();
252
253        let callers_by_callee_id = self.callgraph.get_callers_map();
254
255        for &def_id in &self.callgraph.functions {
256            if !callers_by_callee_id.contains_key(&def_id) && self.cg_map.contains_key(&def_id) {
257                call_chain_starts.push(def_id);
258            }
259        }
260
261        call_chain_starts.sort_by_key(|d| self.tcx.def_path_str(*d));
262
263        rap_debug!(
264            "Found call chain starts ({} functions): {:?}",
265            call_chain_starts.len(),
266            call_chain_starts
267                .iter()
268                .map(|d| self.tcx.def_path_str(*d))
269                .collect::<Vec<_>>()
270        );
271
272        for def_id in call_chain_starts {
273            rap_debug!(
274                "Analyzing function (call chain start): {}",
275                self.tcx.def_path_str(def_id)
276            );
277            if let Some(cg_cell) = self.cg_map.get(&def_id) {
278                let mut cg = cg_cell.borrow_mut();
279                cg.find_intervals(&self.cg_map, &mut self.vars_map);
280            } else {
281                rap_debug!(
282                    "Warning: No ConstraintGraph found for DefId {:?} during analysis of call chain starts.",
283                    def_id
284                );
285            }
286        }
287
288        let analysis_order = self.callgraph.get_reverse_post_order();
289        for def_id in analysis_order {
290            if let Some(cg_cell) = self.cg_map.get(&def_id) {
291                let mut cg = cg_cell.borrow_mut();
292                let (final_vars_for_fn, _) = cg.build_final_vars(&self.ssa_places_mapping[&def_id]);
293                let mut ranges_for_fn = HashMap::new();
294                for (&place, varnode) in final_vars_for_fn {
295                    ranges_for_fn.insert(place, varnode.get_range().clone());
296                }
297                let Some(varnodes_vec) = self.vars_map.get_mut(&def_id) else {
298                    rap_debug!(
299                        "Warning: No VarNodes found for DefId {:?} during analysis of call chain starts.",
300                        def_id
301                    );
302                    continue;
303                };
304                for varnodes in varnodes_vec.iter_mut() {
305                    let ranges_for_fn_recursive = ConstraintGraph::filter_final_vars(
306                        &varnodes.borrow(),
307                        &self.ssa_places_mapping[&def_id],
308                    );
309                    self.final_vars_vec
310                        .entry(def_id)
311                        .or_default()
312                        .push(ranges_for_fn_recursive);
313                }
314
315                self.final_vars.insert(def_id, ranges_for_fn);
316            }
317        }
318
319        rap_debug!("PHASE 2 Complete. Interval analysis finished for call chain start functions.");
320    }
321
322    pub fn start_path_constraints_analysis_for_defid(
323        &mut self,
324        def_id: DefId,
325    ) -> Option<PathConstraint<'tcx>> {
326        if self.tcx.is_mir_available(def_id) {
327            let mut body = self.tcx.optimized_mir(def_id).clone();
328            let body_mut_ref = unsafe { &mut *(&mut body as *mut Body<'tcx>) };
329            let mut path_analyzer = PathAnalyzer::new(self.tcx, self.debug);
330            let paths = path_analyzer.analyze(def_id)?;
331
332            let mut cg: ConstraintGraph<'tcx, T> =
333                ConstraintGraph::new_without_ssa(body_mut_ref, self.tcx, def_id);
334            let result = cg.start_analyze_path_constraints(body_mut_ref, &paths);
335            rap_debug!(
336                "Paths for function {}: {:?}",
337                self.tcx.def_path_str(def_id),
338                paths
339            );
340            let switchbbs = cg.switchbbs.clone();
341            rap_debug!(
342                "Switch basicblocks for function {}: {:?}",
343                self.tcx.def_path_str(def_id),
344                switchbbs
345            );
346            rap_debug!(
347                "Path Constraints Analysis Result for function {}: {:?}",
348                self.tcx.def_path_str(def_id),
349                result
350            );
351            self.path_constraints.insert(def_id, result.clone());
352            Some(result)
353        } else {
354            None
355        }
356    }
357    pub fn start_path_constraints_analysis(&mut self) {
358        let mut path_analyzer = PathAnalyzer::new(self.tcx, self.debug);
359        for local_def_id in self.tcx.iter_local_def_id() {
360            if matches!(self.tcx.def_kind(local_def_id), DefKind::Fn) {
361                let def_id = local_def_id.to_def_id();
362
363                if self.tcx.is_mir_available(def_id) {
364                    let mut body = self.tcx.optimized_mir(def_id).clone();
365                    let body_mut_ref = unsafe { &mut *(&mut body as *mut Body<'tcx>) };
366
367                    let mut cg: ConstraintGraph<'tcx, T> =
368                        ConstraintGraph::new_without_ssa(body_mut_ref, self.tcx, def_id);
369                    let Some(paths) = path_analyzer.analyze(def_id) else {
370                        continue;
371                    };
372                    let result = cg.start_analyze_path_constraints(body_mut_ref, &paths);
373                    rap_debug!(
374                        "Paths for function {}: {:?}",
375                        self.tcx.def_path_str(def_id),
376                        paths
377                    );
378                    let switchbbs = cg.switchbbs.clone();
379                    rap_debug!(
380                        "Switch basicblocks for function {}: {:?}",
381                        self.tcx.def_path_str(def_id),
382                        switchbbs
383                    );
384                    rap_debug!(
385                        "Path Constraints Analysis Result for function {}: {:?}",
386                        self.tcx.def_path_str(def_id),
387                        result
388                    );
389                    self.path_constraints.insert(def_id, result);
390                }
391            }
392        }
393    }
394}
rapx/analysis/range_analysis/default.rs

rapx/analysis/range_analysis/
default.rs
