rapx/analysis/core/range_analysis/
default.rs

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

rapx/analysis/core/range_analysis/
default.rs
