rapx/analysis/core/range_analysis/domain/
ConstraintGraph.rs

1#![allow(unused_imports)]
2#![allow(unused_variables)]
3#![allow(dead_code)]
4#![allow(unused_assignments)]
5#![allow(unused_parens)]
6#![allow(non_snake_case)]
7
8use super::{domain::*, range::RangeType, range::*};
9use crate::rap_debug;
10use crate::rap_info;
11use crate::rap_trace;
12use num_traits::Bounded;
13use once_cell::sync::{Lazy, OnceCell};
14// use rand::Rng;
15use rustc_abi::FieldIdx;
16use rustc_hir::{def, def_id::DefId};
17use rustc_index::IndexVec;
18use rustc_middle::{
19    mir::*,
20    ty::{self, print, ScalarInt, TyCtxt},
21};
22use rustc_span::sym::var;
23
24use std::{
25    collections::{HashMap, HashSet, VecDeque},
26    default,
27    fmt::Debug,
28};
29pub struct ConstraintGraph<'tcx, T: IntervalArithmetic + Debug> {
30    // Protected fields
31    pub vars: VarNodes<'tcx, T>, // The variables of the source program
32    pub oprs: GenOprs<'tcx, T>,  // The operations of the source program
33
34    // func: Option<Function>,             // Save the last Function analyzed
35    pub defmap: DefMap<'tcx>, // Map from variables to the operations that define them
36    pub usemap: UseMap<'tcx>, // Map from variables to operations where variables are used
37    pub symbmap: SymbMap<'tcx>, // Map from variables to operations where they appear as bounds
38    pub values_branchmap: ValuesBranchMap<'tcx, T>, // Store intervals, basic blocks, and branches
39    // values_switchmap: ValuesSwitchMap<'tcx, T>, // Store intervals for switch branches
40    constant_vector: Vec<T>, // Vector for constants from an SCC
41
42    pub inst_rand_place_set: Vec<Place<'tcx>>,
43    pub essa: DefId,
44    pub ssa: DefId,
45
46    pub index: i32,
47    pub dfs: HashMap<&'tcx Place<'tcx>, i32>,
48    pub root: HashMap<&'tcx Place<'tcx>, &'tcx Place<'tcx>>,
49    pub in_component: HashSet<&'tcx Place<'tcx>>,
50    pub components: HashMap<&'tcx Place<'tcx>, HashSet<&'tcx Place<'tcx>>>,
51    pub worklist: VecDeque<&'tcx Place<'tcx>>,
52    pub numAloneSCCs: usize,
53    pub numSCCs: usize, // Add a stub for pre_update to resolve the missing method error.
54    pub final_vars: VarNodes<'tcx, T>,
55}
56
57impl<'tcx, T> ConstraintGraph<'tcx, T>
58where
59    T: IntervalArithmetic + ConstConvert + Debug,
60{
61    pub fn convert_const(c: &Const) -> Option<T> {
62        T::from_const(c)
63    }
64
65    pub fn new(essa: DefId, ssa: DefId) -> Self {
66        Self {
67            vars: VarNodes::new(),
68            oprs: GenOprs::new(),
69            // func: None,
70            defmap: DefMap::new(),
71            usemap: UseMap::new(),
72            symbmap: SymbMap::new(),
73            values_branchmap: ValuesBranchMap::new(),
74            // values_switchmap: ValuesSwitchMap::new(),
75            constant_vector: Vec::new(),
76            inst_rand_place_set: Vec::new(),
77            essa,
78            ssa,
79            index: 0,
80            dfs: HashMap::new(),
81            root: HashMap::new(),
82            in_component: HashSet::new(),
83            components: HashMap::new(),
84            worklist: VecDeque::new(),
85            numAloneSCCs: 0,
86            numSCCs: 0,
87            final_vars: VarNodes::new(),
88        }
89    }
90    pub fn build_final_vars(
91        &mut self,
92        locals_map: &HashMap<Local, HashSet<Local>>,
93    ) -> (VarNodes<'tcx, T>, Vec<Local>) {
94        let mut final_vars: VarNodes<'tcx, T> = HashMap::new();
95        let mut not_found: Vec<Local> = Vec::new();
96
97        for (_key_local, local_set) in locals_map {
98            for &local in local_set {
99                let found = self.vars.iter().find(|(place, _)| place.local == local);
100
101                if let Some((&place, var_node)) = found {
102                    final_vars.insert(place, var_node.clone());
103                } else {
104                    not_found.push(local);
105                }
106            }
107        }
108        self.final_vars = final_vars.clone();
109        (final_vars, not_found)
110    }
111    pub fn rap_print_final_vars(&self) {
112        for (&key, value) in &self.final_vars {
113            rap_info!("var: {:?}. {} ", key, value.get_range());
114        }
115    }
116    pub fn rap_print_vars(&self) {
117        for (&key, value) in &self.vars {
118            rap_debug!("var: {:?}. {} ", key, value.get_range());
119        }
120    }
121    pub fn print_vars(&self) {
122        for (&key, value) in &self.vars {
123            rap_trace!("var: {:?}. {} ", key, value.get_range());
124        }
125    }
126    pub fn print_conponent_vars(&self) {
127        rap_trace!("====print_conponent_vars====");
128        for (key, value) in &self.components {
129            if value.len() > 1 {
130                rap_trace!("component: {:?} ", key);
131                for v in value {
132                    if let Some(var_node) = self.vars.get(v) {
133                        rap_trace!("var: {:?}. {} ", v, var_node.get_range());
134                    } else {
135                        rap_trace!("var: {:?} not found", v);
136                    }
137                }
138            }
139        }
140    }
141    fn print_values_branchmap(&self) {
142        for (&key, value) in &self.values_branchmap {
143            rap_trace!("vbm place: {:?}. {:?}\n ", key, value);
144        }
145    }
146    fn print_symbmap(&self) {
147        for (&key, value) in &self.symbmap {
148            for op in value.iter() {
149                if let Some(op) = self.oprs.get(*op) {
150                    rap_trace!("symbmap op: {:?}. {:?}\n ", key, op);
151                } else {
152                    rap_trace!("symbmap op: {:?} not found\n ", op);
153                }
154            }
155        }
156    }
157    fn print_defmap(&self) {
158        for (key, value) in self.defmap.clone() {
159            rap_trace!(
160                "place: {:?} def in stmt:{:?} {:?}",
161                key,
162                self.oprs[value].get_type_name(),
163                self.oprs[value].get_instruction()
164            );
165        }
166    }
167    fn print_compusemap(
168        &self,
169        component: &HashSet<&'tcx Place<'tcx>>,
170        comp_use_map: &HashMap<&'tcx Place<'tcx>, HashSet<usize>>,
171    ) {
172        for (key, value) in comp_use_map.clone() {
173            if component.contains(key) {
174                for v in value {
175                    rap_trace!(
176                        "compusemap place: {:?} use in stmt:{:?} {:?}",
177                        key,
178                        self.oprs[v].get_type_name(),
179                        self.oprs[v].get_instruction()
180                    );
181                }
182            }
183        }
184    }
185    fn print_usemap(&self) {
186        for (key, value) in self.usemap.clone() {
187            for v in value {
188                rap_trace!(
189                    "place: {:?} use in stmt:{:?} {:?}",
190                    key,
191                    self.oprs[v].get_type_name(),
192                    self.oprs[v].get_instruction()
193                );
194            }
195        }
196    }
197    // pub fn create_random_place(&mut self) -> Place<'tcx> {
198    //     let mut rng = rand::rng();
199    //     let random_local = Local::from_usize(rng.random_range(10000..100000));
200    //     let place = Place {
201    //         local: random_local,
202    //         projection: ty::List::empty(),
203    //     };
204    //     self.inst_rand_place_set.push(place);
205    //     place
206    // }
207    pub fn add_varnode(&mut self, v: &'tcx Place<'tcx>) -> &mut VarNode<'tcx, T> {
208        let node = VarNode::new(v);
209        let node_ref: &mut VarNode<'tcx, T> = self.vars.entry(v).or_insert(node);
210        self.usemap.entry(v).or_insert(HashSet::new());
211
212        node_ref
213    }
214
215    pub fn build_graph(&mut self, body: &'tcx Body<'tcx>) {
216        rap_trace!("====Building graph====\n");
217        self.build_value_maps(body);
218        // rap_trace!("varnodes{:?}\n", self.vars);
219        self.print_values_branchmap();
220        rap_trace!("====build_operations====\n");
221
222        for block in body.basic_blocks.indices() {
223            let block_data = &body[block];
224            // Traverse statements
225
226            for statement in block_data.statements.iter() {
227                self.build_operations(statement, block);
228            }
229        }
230
231        // self.print_vars();
232        // self.print_defmap();
233        // self.print_usemap();
234        // rap_trace!("end\n");
235    }
236
237    pub fn build_value_maps(&mut self, body: &'tcx Body<'tcx>) {
238        for bb in body.basic_blocks.indices() {
239            let block_data = &body[bb];
240            if let Some(terminator) = &block_data.terminator {
241                match &terminator.kind {
242                    TerminatorKind::SwitchInt { discr, targets } => {
243                        rap_trace!("SwitchIntblock{:?}\n", bb);
244                        self.build_value_branch_map(body, discr, targets, block_data);
245                    }
246                    TerminatorKind::Goto { target } => {
247                        // self.build_value_goto_map(block_index, *target);
248                    }
249                    _ => {
250                        // rap_trace!(
251                        //     "BasicBlock {:?} has an unsupported terminator: {:?}",
252                        //     block_index, terminator.kind
253                        // );
254                    }
255                }
256            }
257        }
258        // rap_trace!("value_branchmap{:?}\n", self.values_branchmap);
259        // rap_trace!("varnodes{:?}\n,", self.vars);
260    }
261
262    pub fn build_value_branch_map(
263        &mut self,
264        body: &Body<'tcx>,
265        discr: &'tcx Operand<'tcx>,
266        targets: &'tcx SwitchTargets,
267        block: &'tcx BasicBlockData<'tcx>,
268    ) {
269        // let place1: &Place<'tcx>;
270
271        if let Operand::Copy(place) | Operand::Move(place) = discr {
272            if let Some((op1, op2, cmp_op)) = self.extract_condition(place, block) {
273                let const_op1 = op1.constant();
274                let const_op2 = op2.constant();
275
276                match (const_op1, const_op2) {
277                    (Some(c1), Some(c2)) => {}
278                    (Some(c), None) | (None, Some(c)) => {
279                        let const_in_left: bool;
280                        let variable;
281                        if const_op1.is_some() {
282                            const_in_left = true;
283                            variable = match op2 {
284                                Operand::Copy(p) | Operand::Move(p) => p,
285                                _ => panic!("Expected a place"),
286                            };
287                        } else {
288                            const_in_left = false;
289                            variable = match op1 {
290                                Operand::Copy(p) | Operand::Move(p) => p,
291                                _ => panic!("Expected a place"),
292                            };
293                        }
294                        self.add_varnode(variable);
295                        rap_trace!("add_vbm_varnode{:?}\n", variable.clone());
296
297                        // let value = c.const_.try_to_scalar_int().unwrap();
298                        let value = Self::convert_const(&c.const_).unwrap();
299                        let const_range =
300                            Range::new(value.clone(), value.clone(), RangeType::Unknown);
301                        rap_trace!("cmp_op{:?}\n", cmp_op);
302                        rap_trace!("const_in_left{:?}\n", const_in_left);
303                        let mut true_range =
304                            self.apply_comparison(value.clone(), cmp_op, true, const_in_left);
305                        let mut false_range =
306                            self.apply_comparison(value.clone(), cmp_op, false, const_in_left);
307                        true_range.set_regular();
308                        false_range.set_regular();
309                        // rap_trace!("true_range{:?}\n", true_range);
310                        // rap_trace!("false_range{:?}\n", false_range);
311                        let target_vec = targets.all_targets();
312
313                        let vbm = ValueBranchMap::new(
314                            variable,
315                            &target_vec[0],
316                            &target_vec[1],
317                            IntervalType::Basic(BasicInterval::new(false_range)),
318                            IntervalType::Basic(BasicInterval::new(true_range)),
319                        );
320                        self.values_branchmap.insert(variable, vbm);
321                    }
322                    (None, None) => {
323                        let CR = Range::new(T::min_value(), T::max_value(), RangeType::Unknown);
324
325                        let p1 = match op1 {
326                            Operand::Copy(p) | Operand::Move(p) => p,
327                            _ => panic!("Expected a place"),
328                        };
329                        let p2 = match op2 {
330                            Operand::Copy(p) | Operand::Move(p) => p,
331                            _ => panic!("Expected a place"),
332                        };
333                        let target_vec = targets.all_targets();
334                        self.add_varnode(&p1);
335                        rap_trace!("add_vbm_varnode{:?}\n", p1.clone());
336
337                        self.add_varnode(&p2);
338                        rap_trace!("add_vbm_varnode{:?}\n", p2.clone());
339                        let flipped_binop = Self::flipped_binop(cmp_op).unwrap();
340                        let STOp1 = IntervalType::Symb(SymbInterval::new(CR.clone(), p2, cmp_op));
341                        let SFOp1 = IntervalType::Symb(SymbInterval::new(CR.clone(), p2, cmp_op));
342                        let STOp2 =
343                            IntervalType::Symb(SymbInterval::new(CR.clone(), p1, flipped_binop));
344                        let SFOp2 =
345                            IntervalType::Symb(SymbInterval::new(CR.clone(), p1, flipped_binop));
346                        //    let STOp1 = IntervalType::Symb(SymbInterval::new(CR.clone(), p2, flipped_binop));
347                        //     let SFOp1 = IntervalType::Symb(SymbInterval::new(CR.clone(), p2, cmp_op));
348                        //     let STOp2 = IntervalType::Symb(SymbInterval::new(CR.clone(), p1, flipped_binop));
349                        //     let SFOp2 = IntervalType::Symb(SymbInterval::new(CR.clone(), p1, cmp_op));
350                        let vbm_1 =
351                            ValueBranchMap::new(p1, &target_vec[0], &target_vec[1], STOp1, SFOp1);
352                        let vbm_2 =
353                            ValueBranchMap::new(p2, &target_vec[0], &target_vec[1], STOp2, SFOp2);
354                        self.values_branchmap.insert(&p1, vbm_1);
355                        self.values_branchmap.insert(&p2, vbm_2);
356                    }
357                }
358            };
359        }
360    }
361    pub fn flipped_binop(op: BinOp) -> Option<BinOp> {
362        use BinOp::*;
363        Some(match op {
364            Eq => Eq,
365            Ne => Ne,
366            Lt => Gt,
367            Le => Ge,
368            Gt => Lt,
369            Ge => Le,
370            Add => Add,
371            Mul => Mul,
372            BitXor => BitXor,
373            BitAnd => BitAnd,
374            BitOr => BitOr,
375            _ => {
376                return None;
377            }
378        })
379    }
380    fn extract_condition(
381        &mut self,
382        place: &'tcx Place<'tcx>,
383        switch_block: &'tcx BasicBlockData<'tcx>,
384    ) -> Option<(&'tcx Operand<'tcx>, &'tcx Operand<'tcx>, BinOp)> {
385        for stmt in &switch_block.statements {
386            if let StatementKind::Assign(box (lhs, Rvalue::BinaryOp(bin_op, box (op1, op2)))) =
387                &stmt.kind
388            {
389                if lhs == place {
390                    let mut return_op1: &Operand<'tcx> = &op1;
391                    let mut return_op2: &Operand<'tcx> = &op2;
392                    for stmt_original in &switch_block.statements {
393                        if let StatementKind::Assign(box (lhs, Rvalue::Use(OP1))) =
394                            &stmt_original.kind
395                        {
396                            if lhs.clone() == op1.place().unwrap() {
397                                return_op1 = OP1;
398                            }
399                        }
400                    }
401                    if op2.constant().is_none() {
402                        for stmt_original in &switch_block.statements {
403                            if let StatementKind::Assign(box (lhs, Rvalue::Use(OP2))) =
404                                &stmt_original.kind
405                            {
406                                if lhs.clone() == op2.place().unwrap() {
407                                    return_op2 = OP2;
408                                }
409                            }
410                        }
411                    }
412                    return Some((return_op1, return_op2, *bin_op));
413                }
414            }
415        }
416        None
417    }
418
419    fn apply_comparison<U: IntervalArithmetic>(
420        &self,
421        constant: U,
422        cmp_op: BinOp,
423        is_true_branch: bool,
424        const_in_left: bool,
425    ) -> Range<U> {
426        match cmp_op {
427            BinOp::Lt => {
428                if is_true_branch ^ const_in_left {
429                    Range::new(U::min_value(), constant.sub(U::one()), RangeType::Unknown)
430                } else {
431                    Range::new(constant, U::max_value(), RangeType::Unknown)
432                }
433            }
434
435            BinOp::Le => {
436                if is_true_branch ^ const_in_left {
437                    Range::new(U::min_value(), constant, RangeType::Unknown)
438                } else {
439                    Range::new(constant.add(U::one()), U::max_value(), RangeType::Unknown)
440                }
441            }
442
443            BinOp::Gt => {
444                if is_true_branch ^ const_in_left {
445                    Range::new(U::min_value(), constant, RangeType::Unknown)
446                } else {
447                    Range::new(constant.add(U::one()), U::max_value(), RangeType::Unknown)
448                }
449            }
450
451            BinOp::Ge => {
452                if is_true_branch ^ const_in_left {
453                    Range::new(U::min_value(), constant, RangeType::Unknown)
454                } else {
455                    Range::new(constant, U::max_value().sub(U::one()), RangeType::Unknown)
456                }
457            }
458
459            BinOp::Eq => {
460                if is_true_branch ^ const_in_left {
461                    Range::new(U::min_value(), constant, RangeType::Unknown)
462                } else {
463                    Range::new(constant, U::max_value(), RangeType::Unknown)
464                }
465            }
466
467            _ => Range::new(constant.clone(), constant.clone(), RangeType::Empty),
468        }
469    }
470
471    fn build_value_goto_map(&self, block_index: BasicBlock, target: BasicBlock) {
472        rap_trace!(
473            "Building value map for Goto in block {:?} targeting block {:?}",
474            block_index,
475            target
476        );
477    }
478    pub fn build_varnodes(&mut self) {
479        // Builds VarNodes
480        for (name, node) in self.vars.iter_mut() {
481            let is_undefined = !self.defmap.contains_key(name);
482            node.init(is_undefined);
483        }
484    }
485    pub fn build_symbolic_intersect_map(&mut self) {
486        for i in 0..self.oprs.len() {
487            if let BasicOpKind::Essa(essaop) = &self.oprs[i] {
488                if let IntervalType::Symb(symbi) = essaop.get_intersect() {
489                    let v = symbi.get_bound();
490                    self.symbmap.entry(v).or_insert_with(HashSet::new).insert(i);
491                    rap_trace!("symbmap insert {:?} {:?}\n", v, essaop);
492                }
493            }
494        }
495        // rap_trace!("symbmap: {:?}", self.symbmap);
496    }
497    pub fn build_use_map(
498        &mut self,
499        component: &HashSet<&'tcx Place<'tcx>>,
500    ) -> HashMap<&'tcx Place<'tcx>, HashSet<usize>> {
501        // Builds use map
502        let mut comp_use_map = HashMap::new();
503        for &place in component {
504            if let Some(uses) = self.usemap.get(place) {
505                for op in uses.iter() {
506                    let sink = self.oprs[*op].get_sink();
507                    if component.contains(&sink) {
508                        comp_use_map
509                            .entry(place)
510                            .or_insert_with(HashSet::new)
511                            .insert(*op);
512                    }
513                }
514            }
515        }
516
517        self.print_compusemap(component, &comp_use_map);
518        comp_use_map
519    }
520    pub fn build_operations(&mut self, inst: &'tcx Statement<'tcx>, block: BasicBlock) {
521        if let StatementKind::Assign(box (sink, rvalue)) = &inst.kind {
522            match rvalue {
523                Rvalue::BinaryOp(op, box (op1, op2)) => match op {
524                    BinOp::Add
525                    | BinOp::Sub
526                    | BinOp::Mul
527                    | BinOp::Div
528                    | BinOp::Rem
529                    | BinOp::AddUnchecked => {
530                        self.add_binary_op(sink, inst, op1, op2);
531                    }
532                    BinOp::AddWithOverflow => {
533                        self.add_binary_op(sink, inst, op1, op2);
534                    }
535                    BinOp::SubUnchecked => {
536                        self.add_binary_op(sink, inst, op1, op2);
537                    }
538                    BinOp::SubWithOverflow => {
539                        self.add_binary_op(sink, inst, op1, op2);
540                    }
541                    BinOp::MulUnchecked => {
542                        self.add_binary_op(sink, inst, op1, op2);
543                    }
544                    BinOp::MulWithOverflow => {
545                        self.add_binary_op(sink, inst, op1, op2);
546                    }
547
548                    _ => {}
549                },
550                Rvalue::UnaryOp(UnOp, op) => {
551                    self.add_unary_op(sink, inst, op);
552                }
553                Rvalue::Aggregate(kind, operends) => {
554                    match **kind {
555                        AggregateKind::Adt(def_id, _, _, _, _) => {
556                            if def_id == self.essa {
557                                self.add_essa_op(sink, inst, operends, block);
558                                // rap_trace!("Adt{:?}\n", operends);
559                            }
560                            if def_id == self.ssa {
561                                self.add_ssa_op(sink, inst, operends);
562                                // rap_trace!("Adt{:?}\n", operends);
563                            }
564                        }
565                        _ => {}
566                    }
567                }
568                Rvalue::Use(operend) => {
569                    self.add_use_op(sink, inst, operend);
570                }
571                _ => {}
572            }
573        }
574    }
575    fn add_ssa_op(
576        &mut self,
577        sink: &'tcx Place<'tcx>,
578
579        inst: &'tcx Statement<'tcx>,
580        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
581    ) {
582        rap_trace!("ssa_op{:?}\n", inst);
583
584        let sink_node = self.add_varnode(sink);
585        rap_trace!("addsink_in_ssa_op{:?}\n", sink_node);
586
587        let BI: BasicInterval<T> = BasicInterval::new(Range::default(T::min_value()));
588        let mut phiop = PhiOp::new(IntervalType::Basic(BI), sink, inst, 0);
589        let bop_index = self.oprs.len();
590        for i in 0..operands.len() {
591            let source = match &operands[FieldIdx::from_usize(i)] {
592                Operand::Copy(place) | Operand::Move(place) => Some(place),
593                _ => None,
594            };
595            if let Some(source) = source {
596                self.add_varnode(source);
597                phiop.add_source(source);
598                rap_trace!("addvar_in_ssa_op{:?}\n", source);
599                self.usemap.entry(source).or_default().insert(bop_index);
600            }
601        }
602        // Insert the operation in the graph.
603
604        self.oprs.push(BasicOpKind::Phi(phiop));
605
606        // Insert this definition in defmap
607
608        self.defmap.insert(sink, bop_index);
609    }
610    fn add_use_op(
611        &mut self,
612        sink: &'tcx Place<'tcx>,
613        inst: &'tcx Statement<'tcx>,
614        op: &'tcx Operand<'tcx>,
615    ) {
616        rap_trace!("use_op{:?}\n", inst);
617
618        let sink_node = self.add_varnode(sink);
619        rap_trace!("addsink_in_use_op{:?}\n", sink_node);
620
621        let BI: BasicInterval<T> = BasicInterval::new(Range::default(T::min_value()));
622        let mut source: Option<&'tcx Place<'tcx>> = None;
623
624        match op {
625            Operand::Copy(place) | Operand::Move(place) => {
626                source = Some(place);
627                if let Some(source) = source {
628                    rap_trace!("addvar_in_use_op{:?}\n", source);
629
630                    let useop = UseOp::new(IntervalType::Basic(BI), sink, inst, source, 0);
631                    // Insert the operation in the graph.
632                    let bop_index = self.oprs.len();
633
634                    self.oprs.push(BasicOpKind::Use(useop));
635                    // Insert this definition in defmap
636                    self.usemap.entry(source).or_default().insert(bop_index);
637
638                    self.defmap.insert(sink, bop_index);
639                }
640            }
641            Operand::Constant(constant) => {
642                rap_trace!("add_constant_op{:?}\n", inst);
643                let Some(c) = op.constant() else {
644                    rap_trace!("add_constant_op: constant is None\n");
645                    return;
646                };
647
648                if let Some(value) = Self::convert_const(&c.const_) {
649                    sink_node.set_range(Range::new(
650                        value.clone(),
651                        value.clone(),
652                        RangeType::Regular,
653                    ));
654                    rap_trace!("set_const {:?} value: {:?}\n", sink_node, value);
655                    // rap_trace!("sinknoderange: {:?}\n", sink_node.get_range());
656                } else {
657                    sink_node.set_range(Range::default(T::min_value()));
658                };
659            }
660        }
661    }
662    fn add_essa_op(
663        &mut self,
664        sink: &'tcx Place<'tcx>,
665
666        inst: &'tcx Statement<'tcx>,
667        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
668        block: BasicBlock,
669    ) {
670        // rap_trace!("essa_op{:?}\n", inst);
671        let sink_node = self.add_varnode(sink);
672        // rap_trace!("addsink_in_essa_op {:?}\n", sink_node);
673
674        // let BI: BasicInterval<T> = BasicInterval::new(Range::default(T::min_value()));
675        let loc_1: usize = 0;
676        let loc_2: usize = 1;
677        let source1 = match &operands[FieldIdx::from_usize(loc_1)] {
678            Operand::Copy(place) | Operand::Move(place) => Some(place),
679            _ => None,
680        };
681        let op = &operands[FieldIdx::from_usize(loc_2)];
682        let bop_index = self.oprs.len();
683
684        let BI: IntervalType<'_, T>;
685        if let Operand::Constant(c) = op {
686            let vbm = self.values_branchmap.get(source1.unwrap()).unwrap();
687            if block == *vbm.get_bb_true() {
688                rap_trace!("essa_op true branch{:?}\n", block);
689                BI = vbm.get_itv_t();
690            } else {
691                rap_trace!("essa_op false branch{:?}\n", block);
692                BI = vbm.get_itv_f();
693            }
694            self.usemap
695                .entry(source1.unwrap())
696                .or_default()
697                .insert(bop_index);
698
699            let essaop = EssaOp::new(BI, sink, inst, source1.unwrap(), 0, false);
700            rap_trace!(
701                "addvar_in_essa_op {:?} from const {:?}\n",
702                essaop,
703                source1.unwrap()
704            );
705
706            // Insert the operation in the graph.
707
708            self.oprs.push(BasicOpKind::Essa(essaop));
709            // Insert this definition in defmap
710            // self.usemap
711            //     .entry(source1.unwrap())
712            //     .or_default()
713            //     .insert(bop_index);
714
715            self.defmap.insert(sink, bop_index);
716        } else {
717            let vbm = self.values_branchmap.get(source1.unwrap()).unwrap();
718            if block == *vbm.get_bb_true() {
719                rap_trace!("essa_op true branch{:?}\n", block);
720                BI = vbm.get_itv_t();
721            } else {
722                rap_trace!("essa_op false branch{:?}\n", block);
723                BI = vbm.get_itv_f();
724            }
725            let source2 = match op {
726                Operand::Copy(place) | Operand::Move(place) => Some(place),
727                _ => None,
728            };
729            self.usemap
730                .entry(source1.unwrap())
731                .or_default()
732                .insert(bop_index);
733            // self.usemap
734            // .entry(source2.unwrap())
735            // .or_default()
736            // .insert(bop_index);
737            let essaop = EssaOp::new(BI, sink, inst, source1.unwrap(), 0, true);
738            // Insert the operation in the graph.
739            rap_trace!(
740                "addvar_in_essa_op {:?} from {:?}\n",
741                essaop,
742                source1.unwrap()
743            );
744
745            self.oprs.push(BasicOpKind::Essa(essaop));
746            // Insert this definition in defmap
747            // self.usemap
748            //     .entry(source1.unwrap())
749            //     .or_default()
750            //     .insert(bop_index);
751
752            self.defmap.insert(sink, bop_index);
753        }
754    }
755    fn add_unary_op(
756        &mut self,
757        sink: &'tcx Place<'tcx>,
758        inst: &'tcx Statement<'tcx>,
759        op: &'tcx Operand<'tcx>,
760    ) {
761        rap_trace!("unary_op{:?}\n", inst);
762
763        let sink_node = self.add_varnode(sink);
764        rap_trace!("addsink_in_unary_op{:?}\n", sink_node);
765
766        let BI: BasicInterval<T> = BasicInterval::new(Range::default(T::min_value()));
767        let loc_1: usize = 0;
768        let source = match op {
769            Operand::Copy(place) | Operand::Move(place) => Some(place),
770            _ => None,
771        };
772        rap_trace!("addvar_in_unary_op{:?}\n", source.unwrap());
773        self.add_varnode(source.unwrap());
774
775        let unaryop = UnaryOp::new(IntervalType::Basic(BI), sink, inst, source.unwrap(), 0);
776        // Insert the operation in the graph.
777        let bop_index = self.oprs.len();
778
779        self.oprs.push(BasicOpKind::Unary(unaryop));
780        // Insert this definition in defmap
781
782        self.defmap.insert(sink, bop_index);
783    }
784
785    fn add_binary_op(
786        &mut self,
787        sink: &'tcx Place<'tcx>,
788        inst: &'tcx Statement<'tcx>,
789        op1: &'tcx Operand<'tcx>,
790        op2: &'tcx Operand<'tcx>,
791    ) {
792        rap_trace!("binary_op{:?}\n", inst);
793        let sink_node = self.add_varnode(sink);
794        rap_trace!("addsink_in_binary_op{:?}\n", sink_node);
795        let bop_index = self.oprs.len();
796        let BI: BasicInterval<T> = BasicInterval::new(Range::default(T::min_value()));
797
798        let source1_place = match op1 {
799            Operand::Copy(place) | Operand::Move(place) => {
800                self.add_varnode(place);
801                rap_trace!("addvar_in_binary_op{:?}\n", place);
802
803                Some(place)
804            }
805            Operand::Constant(_) => None,
806        };
807
808        match op2 {
809            Operand::Copy(place) | Operand::Move(place) => {
810                self.add_varnode(place);
811                rap_trace!("addvar_in_binary_op{:?}\n", place);
812
813                let source2_place = Some(place);
814                let BOP = BinaryOp::new(
815                    IntervalType::Basic(BI),
816                    sink,
817                    inst,
818                    source1_place,
819                    source2_place,
820                    0,
821                    None,
822                );
823                self.oprs.push(BasicOpKind::Binary(BOP));
824                // let bop_ref = unsafe { &*(self.oprs.last().unwrap() as *const BasicOp<'tcx, T>) };
825                self.defmap.insert(sink, bop_index);
826                if let Some(place) = source1_place {
827                    self.usemap.entry(place).or_default().insert(bop_index);
828                }
829
830                if let Some(place) = source2_place {
831                    self.usemap.entry(place).or_default().insert(bop_index);
832                }
833            }
834            Operand::Constant(c) => {
835                let const_value = Self::convert_const(&c.const_).unwrap();
836                let BOP = BinaryOp::new(
837                    IntervalType::Basic(BI),
838                    sink,
839                    inst,
840                    source1_place,
841                    None,
842                    0,
843                    Some(const_value),
844                );
845                self.oprs.push(BasicOpKind::Binary(BOP));
846                // let bop_ref = unsafe { &*(self.oprs.last().unwrap() as *const BasicOp<'tcx, T>) };
847                self.defmap.insert(sink, bop_index);
848                if let Some(place) = source1_place {
849                    self.usemap.entry(place).or_default().insert(bop_index);
850                }
851            }
852        };
853
854        // rap_trace!("varnodes{:?}\n", self.vars);
855        // rap_trace!("defmap{:?}\n", self.defmap);
856        // rap_trace!("usemap{:?}\n", self.usemap);
857        // rap_trace!("{:?}add_binary_op{:?}\n", inst,sink);
858        // ...
859    }
860    fn fix_intersects(&mut self, component: &HashSet<&'tcx Place<'tcx>>) {
861        for &place in component.iter() {
862            // node.fix_intersects();
863            if let Some(sit) = self.symbmap.get_mut(place) {
864                let node = self.vars.get(place).unwrap();
865
866                for &op in sit.iter() {
867                    let op = &mut self.oprs[op];
868                    let sinknode = self.vars.get(op.get_sink()).unwrap();
869
870                    op.op_fix_intersects(node, sinknode);
871                }
872            }
873        }
874    }
875    pub fn widen(&mut self, op: usize) -> bool {
876        // use crate::range_util::{get_first_less_from_vector, get_first_greater_from_vector};
877        // assert!(!constant_vector.is_empty(), "Invalid constant vector");
878        let op = &mut self.oprs[op];
879        let sink = op.get_sink();
880        let old_interval = self.vars.get(sink).unwrap().get_range().clone();
881        let estimated_interval = op.eval(&self.vars);
882        let old_lower = old_interval.get_lower();
883        let old_upper = old_interval.get_upper();
884        let new_lower = estimated_interval.get_lower();
885        let new_upper = estimated_interval.get_upper();
886        // op.set_intersect(estimated_interval.clone());
887
888        // let nlconstant = get_first_less_from_vector(constant_vector, new_lower);
889        // let nuconstant = get_first_greater_from_vector(constant_vector, new_upper);
890        // let nlconstant = constant_vector
891        //     .iter()
892        //     .find(|&&c| c <= new_lower)
893        //     .cloned()
894        //     .unwrap_or(T::min_value());
895        // let nuconstant = constant_vector
896        //     .iter()
897        //     .find(|&&c| c >= new_upper)
898        //     .cloned()
899        //     .unwrap_or(T::max_value());
900
901        let updated = if old_interval.is_unknown() {
902            estimated_interval.clone()
903        } else if new_lower < old_lower && new_upper > old_upper {
904            Range::new(T::min_value(), T::max_value(), RangeType::Regular)
905        } else if new_lower < old_lower {
906            Range::new(T::min_value(), old_upper.clone(), RangeType::Regular)
907        } else if new_upper > old_upper {
908            Range::new(old_lower.clone(), T::max_value(), RangeType::Regular)
909        } else {
910            old_interval.clone()
911        };
912
913        self.vars.get_mut(sink).unwrap().set_range(updated.clone());
914        rap_trace!(
915            "WIDEN in {} set {:?}: E {} U {} {} -> {}",
916            op,
917            sink,
918            estimated_interval,
919            updated,
920            old_interval,
921            updated
922        );
923
924        old_interval != updated
925    }
926    pub fn narrow(&mut self, op: usize) -> bool {
927        let op = &mut self.oprs[op];
928        let sink = op.get_sink();
929        let old_interval = self.vars.get(sink).unwrap().get_range().clone();
930        let estimated_interval = op.eval(&self.vars);
931        let old_lower = old_interval.get_lower();
932        let old_upper = old_interval.get_upper();
933        let new_lower = estimated_interval.get_lower();
934        let new_upper = estimated_interval.get_upper();
935        // op.set_intersect(estimated_interval.clone());
936        // let mut hasChanged = false;
937        let mut final_lower = old_lower.clone();
938        let mut final_upper = old_upper.clone();
939        if old_lower.clone() == T::min_value() && new_lower.clone() > T::min_value() {
940            final_lower = new_lower.clone();
941            // tightened = Range::new(new_lower.clone(), old_upper.clone(), RangeType::Regular);
942            // hasChanged = true;
943        } else if old_lower.clone() <= new_lower.clone() {
944            final_lower = new_lower.clone();
945
946            // tightened = Range::new(new_lower.clone(), old_upper.clone(), RangeType::Regular);
947            // hasChanged = true;
948        };
949        if old_upper.clone() == T::max_value() && new_upper.clone() < T::max_value() {
950            final_upper = new_upper.clone();
951            // tightened = Range::new(old_lower.clone(), new_upper.clone(), RangeType::Regular);
952            // hasChanged = true;
953        } else if old_upper.clone() >= new_upper.clone() {
954            final_upper = new_upper.clone();
955            // tightened = Range::new(old_lower.clone(), new_upper.clone(), RangeType::Regular);
956            // hasChanged = true;
957        }
958        let tightened = Range::new(final_lower, final_upper, RangeType::Regular);
959
960        self.vars
961            .get_mut(sink)
962            .unwrap()
963            .set_range(tightened.clone());
964        rap_trace!(
965            "NARROW in {} set {:?}: E {} U {} {} -> {}",
966            op,
967            sink,
968            estimated_interval,
969            tightened,
970            old_interval,
971            tightened
972        );
973        let hasChanged = old_interval != tightened;
974
975        hasChanged
976    }
977
978    fn pre_update(
979        &mut self,
980        comp_use_map: &HashMap<&'tcx Place<'tcx>, HashSet<usize>>,
981        entry_points: &HashSet<&'tcx Place<'tcx>>,
982    ) {
983        let mut worklist: Vec<&'tcx Place<'tcx>> = entry_points.iter().cloned().collect();
984
985        while let Some(place) = worklist.pop() {
986            if let Some(op_set) = comp_use_map.get(place) {
987                for &op in op_set {
988                    if self.widen(op) {
989                        let sink = self.oprs[op].get_sink();
990                        rap_trace!("W {:?}\n", sink);
991                        // let sink_node = self.vars.get_mut(sink).unwrap();
992                        worklist.push(sink);
993                    }
994                }
995            }
996        }
997    }
998
999    fn pos_update(
1000        &mut self,
1001        comp_use_map: &HashMap<&'tcx Place<'tcx>, HashSet<usize>>,
1002        entry_points: &HashSet<&'tcx Place<'tcx>>,
1003    ) {
1004        let mut worklist: Vec<&'tcx Place<'tcx>> = entry_points.iter().cloned().collect();
1005        let mut iteration = 0;
1006        while let Some(place) = worklist.pop() {
1007            iteration += 1;
1008            if (iteration > 1000) {
1009                rap_trace!("Iteration limit reached, breaking out of pos_update\n");
1010                break;
1011            }
1012
1013            if let Some(op_set) = comp_use_map.get(place) {
1014                for &op in op_set {
1015                    if self.narrow(op) {
1016                        let sink = self.oprs[op].get_sink();
1017                        rap_trace!("N {:?}\n", sink);
1018
1019                        // let sink_node = self.vars.get_mut(sink).unwrap();
1020                        worklist.push(sink);
1021                    }
1022                }
1023            }
1024        }
1025        rap_trace!("pos_update finished after {} iterations\n", iteration);
1026    }
1027    fn generate_active_vars(
1028        &mut self,
1029        component: &HashSet<&'tcx Place<'tcx>>,
1030        active_vars: &mut HashSet<&'tcx Place<'tcx>>,
1031    ) {
1032        for place in component {
1033            let node = self.vars.get(place).unwrap();
1034        }
1035    }
1036    fn generate_entry_points(
1037        &mut self,
1038        component: &HashSet<&'tcx Place<'tcx>>,
1039        entry_points: &mut HashSet<&'tcx Place<'tcx>>,
1040    ) {
1041        for &place in component {
1042            let op = self.defmap.get(place).unwrap();
1043            if let BasicOpKind::Essa(essaop) = &mut self.oprs[*op] {
1044                if essaop.is_unresolved() {
1045                    let source = essaop.get_source();
1046                    let new_range = essaop.eval(&self.vars);
1047                    let sink_node = self.vars.get_mut(source).unwrap();
1048                    sink_node.set_range(new_range);
1049                }
1050                essaop.mark_resolved();
1051            }
1052            if (!self.vars[place].get_range().is_unknown()) {
1053                entry_points.insert(place);
1054            }
1055        }
1056    }
1057    fn propagate_to_next_scc(&mut self, component: &HashSet<&'tcx Place<'tcx>>) {
1058        for &place in component.iter() {
1059            let node = self.vars.get_mut(place).unwrap();
1060            for &op in self.usemap.get(place).unwrap().iter() {
1061                let op = &mut self.oprs[op];
1062                let sink = op.get_sink();
1063                if !component.contains(sink) {
1064                    let new_range = op.eval(&self.vars);
1065                    let sink_node = self.vars.get_mut(sink).unwrap();
1066                    rap_trace!(
1067                        "prop component {:?} set {} to {:?} through {:?}\n",
1068                        component,
1069                        new_range,
1070                        sink,
1071                        op.get_instruction()
1072                    );
1073                    sink_node.set_range(new_range);
1074                    // if self.symbmap.contains_key(sink) {
1075                    //     let symb_set = self.symbmap.get_mut(sink).unwrap();
1076                    //     symb_set.insert(op.get_index());
1077                    // }
1078                    if let BasicOpKind::Essa(essaop) = op {
1079                        if essaop.get_intersect().get_range().is_unknown() {
1080                            essaop.mark_unresolved();
1081                        }
1082                    }
1083                }
1084            }
1085        }
1086    }
1087    pub fn find_intervals(&mut self) {
1088        // let scc_list = Nuutila::new(&self.vars, &self.usemap, &self.symbmap,false,&self.oprs);
1089        // self.print_vars();
1090        self.numSCCs = self.worklist.len();
1091        let mut seen = HashSet::new();
1092        let mut components = Vec::new();
1093
1094        for &place in self.worklist.iter().rev() {
1095            if seen.contains(place) {
1096                continue;
1097            }
1098
1099            if let Some(component) = self.components.get(place) {
1100                for &p in component {
1101                    seen.insert(p);
1102                }
1103
1104                components.push(component.clone());
1105            }
1106        }
1107        rap_trace!("TOLO:{:?}\n", components);
1108
1109        for component in components {
1110            rap_trace!("===start component {:?}===\n", component);
1111            if component.len() == 1 {
1112                self.numAloneSCCs += 1;
1113
1114                self.fix_intersects(&component);
1115
1116                let variable: &Place<'tcx> = *component.iter().next().unwrap();
1117                let varnode = self.vars.get_mut(variable).unwrap();
1118                if varnode.get_range().is_unknown() {
1119                    varnode.set_default();
1120                }
1121            } else {
1122                // self.pre_update(&comp_use_map, &entry_points);
1123                let comp_use_map = self.build_use_map(&component);
1124                // build_constant_vec(&component, &self.oprs, &mut self.constant_vec);
1125                let mut entry_points = HashSet::new();
1126                // self.print_vars();
1127
1128                self.generate_entry_points(&component, &mut entry_points);
1129                rap_trace!("entry_points {:?}  \n", entry_points);
1130                // rap_trace!("comp_use_map {:?}  \n ", comp_use_map);
1131                self.pre_update(&comp_use_map, &entry_points);
1132                self.fix_intersects(&component);
1133
1134                // for &variable in &component {
1135                //     let varnode = self.vars.get_mut(variable).unwrap();
1136                //     if varnode.get_range().is_unknown() {
1137                //         varnode.set_default();
1138                //     }
1139                // }
1140
1141                let mut active_vars = HashSet::new();
1142                self.generate_active_vars(&component, &mut active_vars);
1143                self.pos_update(&comp_use_map, &entry_points);
1144            }
1145            self.propagate_to_next_scc(&component);
1146        }
1147    }
1148    pub fn add_control_dependence_edges(&mut self) {
1149        rap_trace!("====Add control dependence edges====\n");
1150        self.print_symbmap();
1151        for (&place, opset) in self.symbmap.iter() {
1152            for &op in opset.iter() {
1153                let bop_index = self.oprs.len();
1154                let opkind = &self.oprs[op];
1155                let control_edge = ControlDep::new(
1156                    IntervalType::Basic(BasicInterval::default()),
1157                    opkind.get_sink(),
1158                    opkind.get_instruction(),
1159                    place,
1160                );
1161                rap_trace!(
1162                    "add control_edge {:?} {:?}\n",
1163                    control_edge,
1164                    opkind.get_source()
1165                );
1166                self.oprs.push(BasicOpKind::ControlDep(control_edge));
1167                self.usemap.entry(place).or_default().insert(bop_index);
1168            }
1169        }
1170    }
1171    pub fn del_control_dependence_edges(&mut self) {
1172        rap_trace!("====Delete control dependence edges====\n");
1173
1174        // 从后往前找到第一个不是 ControlDep 的位置
1175        let mut remove_from = self.oprs.len();
1176        while remove_from > 0 {
1177            match &self.oprs[remove_from - 1] {
1178                BasicOpKind::ControlDep(dep) => {
1179                    let place = dep.source;
1180                    rap_trace!(
1181                        "removing control_edge at idx {}: {:?}\n",
1182                        remove_from - 1,
1183                        dep
1184                    );
1185                    if let Some(set) = self.usemap.get_mut(&place) {
1186                        set.remove(&(remove_from - 1));
1187                        if set.is_empty() {
1188                            self.usemap.remove(&place);
1189                        }
1190                    }
1191                    remove_from -= 1;
1192                }
1193                _ => break,
1194            }
1195        }
1196
1197        self.oprs.truncate(remove_from);
1198    }
1199
1200    pub fn build_nuutila(&mut self, single: bool) {
1201        rap_trace!("====Building graph====\n");
1202        self.print_usemap();
1203        self.build_symbolic_intersect_map();
1204
1205        if single {
1206        } else {
1207            for place in self.vars.keys().copied() {
1208                self.dfs.insert(place, -1);
1209            }
1210
1211            self.add_control_dependence_edges();
1212
1213            let places: Vec<_> = self.vars.keys().copied().collect();
1214            rap_trace!("places{:?}\n", places);
1215            for place in places {
1216                if self.dfs[&place] < 0 {
1217                    rap_trace!("start place{:?}\n", place);
1218                    let mut stack = Vec::new();
1219                    self.visit(place, &mut stack);
1220                }
1221            }
1222
1223            self.del_control_dependence_edges();
1224        }
1225        rap_trace!("components{:?}\n", self.components);
1226        rap_trace!("worklist{:?}\n", self.worklist);
1227        rap_trace!("dfs{:?}\n", self.dfs);
1228    }
1229    pub fn visit(&mut self, place: &'tcx Place<'tcx>, stack: &mut Vec<&'tcx Place<'tcx>>) {
1230        self.dfs.entry(place).and_modify(|v| *v = self.index);
1231        self.index += 1;
1232        self.root.insert(place, place);
1233        let uses = self.usemap.get(place).unwrap().clone();
1234        for op in uses {
1235            let name = self.oprs[op].get_sink();
1236            rap_trace!("place {:?} get name{:?}\n", place, name);
1237            if self.dfs.get(name).copied().unwrap_or(-1) < 0 {
1238                self.visit(name, stack);
1239            }
1240
1241            if (!self.in_component.contains(name)
1242                && self.dfs[self.root[place]] >= self.dfs[self.root[name]])
1243            {
1244                *self.root.get_mut(place).unwrap() = self.root.get(name).copied().unwrap();
1245
1246                // let weq = self.root.get(place)
1247            }
1248        }
1249
1250        if self.root.get(place).copied().unwrap() == place {
1251            self.worklist.push_back(place);
1252
1253            let mut scc = HashSet::new();
1254            scc.insert(place);
1255
1256            self.in_component.insert(place);
1257
1258            while let Some(top) = stack.last() {
1259                if self.dfs.get(top).copied().unwrap_or(-1) > self.dfs.get(place).copied().unwrap()
1260                {
1261                    let node = stack.pop().unwrap();
1262                    self.in_component.insert(node);
1263
1264                    scc.insert(node);
1265                } else {
1266                    break;
1267                }
1268            }
1269
1270            self.components.insert(place, scc);
1271        } else {
1272            stack.push(place);
1273        }
1274    }
1275}
1276#[derive(Debug)]
1277pub struct Nuutila<'tcx, T: IntervalArithmetic + Debug> {
1278    pub variables: &'tcx VarNodes<'tcx, T>,
1279    pub index: i32,
1280    pub dfs: HashMap<&'tcx Place<'tcx>, i32>,
1281    pub root: HashMap<&'tcx Place<'tcx>, &'tcx Place<'tcx>>,
1282    pub in_component: HashSet<&'tcx Place<'tcx>>,
1283    pub components: HashMap<&'tcx Place<'tcx>, HashSet<&'tcx Place<'tcx>>>,
1284    pub worklist: VecDeque<&'tcx Place<'tcx>>,
1285    // pub oprs: &Vec<BasicOpKind<'tcx, T>>,
1286}
1287
1288impl<'tcx, T> Nuutila<'tcx, T>
1289where
1290    T: IntervalArithmetic + ConstConvert + Debug,
1291{
1292    pub fn new(
1293        varNodes: &'tcx VarNodes<'tcx, T>,
1294        use_map: &'tcx UseMap<'tcx>,
1295        symb_map: &'tcx SymbMap<'tcx>,
1296        single: bool,
1297        oprs: &'tcx Vec<BasicOpKind<'tcx, T>>,
1298    ) -> Self {
1299        let mut n: Nuutila<'_, T> = Nuutila {
1300            variables: varNodes,
1301            index: 0,
1302            dfs: HashMap::new(),
1303            root: HashMap::new(),
1304            in_component: HashSet::new(),
1305            components: HashMap::new(),
1306            worklist: std::collections::VecDeque::new(),
1307            // oprs:oprs
1308        };
1309
1310        if single {
1311            // let mut scc = HashSet::new();
1312            // for var_node in variables.values() {
1313            //     scc.insert(var_node.clone());
1314            // }
1315
1316            // for (place, _) in variables.iter() {
1317            //     n.components.insert(place.clone(), scc.clone());
1318            // }
1319
1320            // if let Some((first_place, _)) = variables.iter().next() {
1321            //     n.worklist.push_back(first_place.clone());
1322            // }
1323        } else {
1324            for place in n.variables.keys().copied() {
1325                n.dfs.insert(place, -1);
1326            }
1327
1328            n.add_control_dependence_edges(symb_map, use_map, varNodes);
1329
1330            for place in n.variables.keys() {
1331                if n.dfs[place] < 0 {
1332                    let mut stack = Vec::new();
1333                    n.visit(place, &mut stack, use_map, oprs);
1334                }
1335            }
1336
1337            // n.del_control_dependence_edges(use_map);
1338        }
1339
1340        n
1341    }
1342
1343    pub fn visit(
1344        &mut self,
1345        place: &'tcx Place<'tcx>,
1346        stack: &mut Vec<&'tcx Place<'tcx>>,
1347        use_map: &'tcx UseMap<'tcx>,
1348        oprs: &'tcx Vec<BasicOpKind<'tcx, T>>,
1349    ) {
1350        self.dfs.entry(place).and_modify(|v| *v = self.index);
1351        self.index += 1;
1352        self.root.insert(place, place);
1353
1354        if let Some(uses) = use_map.get(place) {
1355            for op in uses {
1356                let name = oprs[*op].get_sink();
1357
1358                if self.dfs.get(name).copied().unwrap_or(-1) < 0 {
1359                    self.visit(name, stack, use_map, oprs);
1360                }
1361
1362                if (!self.in_component.contains(name)
1363                    && self.dfs[self.root[place]] >= self.dfs[self.root[name]])
1364                {
1365                    *self.root.get_mut(place).unwrap() = self.root.get(name).copied().unwrap();
1366
1367                    // let weq = self.root.get(place)
1368                }
1369            }
1370        }
1371
1372        if self.root.get(place).copied().unwrap() == place {
1373            self.worklist.push_back(place);
1374
1375            let mut scc = HashSet::new();
1376            scc.insert(place);
1377
1378            self.in_component.insert(place);
1379
1380            while let Some(&top) = stack.last() {
1381                if self.dfs.get(top).copied().unwrap_or(-1) > self.dfs.get(place).copied().unwrap()
1382                {
1383                    let node = stack.pop().unwrap();
1384                    self.in_component.insert(node);
1385
1386                    scc.insert(node);
1387                } else {
1388                    break;
1389                }
1390            }
1391
1392            self.components.insert(place, scc);
1393        } else {
1394            stack.push(place);
1395        }
1396    }
1397
1398    pub fn add_control_dependence_edges(
1399        &mut self,
1400        _symb_map: &'tcx SymbMap<'tcx>,
1401        _use_map: &'tcx UseMap<'tcx>,
1402        _vars: &'tcx VarNodes<'tcx, T>,
1403    ) {
1404        todo!()
1405    }
1406
1407    pub fn del_control_dependence_edges(&mut self, _use_map: &'tcx mut UseMap<'tcx>) {
1408        todo!()
1409    }
1410}
rapx/analysis/core/range_analysis/domain/ConstraintGraph.rs

rapx/analysis/core/range_analysis/domain/
ConstraintGraph.rs
