rapx/analysis/range/domain/constraint_graph/
graph.rs

1
2use crate::analysis::range::domain::domain::*;
3use crate::analysis::range::{Range, RangeType};
4
5use crate::analysis::range::domain::symbolic_expr::*;
6use crate::compat::Spanned;
7use rustc_abi::FieldIdx;
8use rustc_hir::def_id::LOCAL_CRATE;
9use rustc_hir::def_id::DefId;
10use rustc_index::IndexVec;
11use rustc_middle::{
12    mir::*,
13    ty::{self},
14};
15
16use std::{
17    collections::{HashMap, HashSet},
18    fmt::Debug,
19};
20
21use super::ConstraintGraph;
22
23impl<'tcx, T> ConstraintGraph<'tcx, T>
24where
25    T: IntervalArithmetic + ConstConvert + Debug,
26{
27    fn register_op(&mut self, op: BasicOpKind<'tcx, T>, sink: &'tcx Place<'tcx>) -> usize {
28        let idx = self.oprs.len();
29        self.oprs.push(op);
30        self.defmap.insert(sink, idx);
31        idx
32    }
33
34    pub fn add_varnode(&mut self, v: &'tcx Place<'tcx>) -> &mut VarNode<'tcx, T> {
35        let local_decls = &self.body.local_decls;
36
37        let node = VarNode::new(v);
38        let node_ref: &mut VarNode<'tcx, T> = self
39            .vars
40            .entry(v)
41            .or_insert(node);
42        self.usemap.entry(v).or_insert(HashSet::new());
43
44        let ty = local_decls[v.local].ty;
45        let place_ty = v.ty(local_decls, self.tcx);
46
47        if v.projection.is_empty() || self.defmap.contains_key(v) {
48            return node_ref;
49        }
50
51        if !v.projection.is_empty() {
52            let matches: Vec<(_, _)> = self
53                .defmap
54                .iter()
55                .filter(|(p, _)| p.local == v.local && p.projection.is_empty())
56                .map(|(p, def_op)| (*p, *def_op))
57                .collect();
58
59            for (base_place, def_op) in matches {
60                let mut v_op = self.oprs[def_op].clone();
61                v_op.set_sink(v);
62
63                for source in v_op.get_sources() {
64                    self.usemap
65                        .entry(source)
66                        .or_insert(HashSet::new())
67                        .insert(self.oprs.len());
68                }
69
70                self.oprs.push(v_op);
71                self.defmap.insert(v, self.oprs.len() - 1);
72            }
73        }
74
75        node_ref
76    }
77
78    pub fn use_add_varnode_sym(
79        &mut self,
80        v: &'tcx Place<'tcx>,
81        rvalue: &'tcx Rvalue<'tcx>,
82    ) -> &mut VarNode<'tcx, T> {
83        if !self.vars.contains_key(v) {
84            let place_ctx: Vec<&Place<'tcx>> = self.vars.keys().map(|p| *p).collect();
85            let node = VarNode::new_symb(v, SymbExpr::from_rvalue(rvalue, place_ctx.clone()));
86            rap_debug!("use node:{:?}", node);
87
88            self.vars.insert(v, node);
89            self.usemap.entry(v).or_insert(HashSet::new());
90
91            if !(v.projection.is_empty() || self.defmap.contains_key(v)) {
92                let matches: Vec<_> = self
93                    .defmap
94                    .iter()
95                    .filter(|(p, _)| p.local == v.local && p.projection.is_empty())
96                    .map(|(p, &def_op)| (*p, def_op))
97                    .collect();
98
99                for (base_place, def_op) in matches {
100                    let mut v_op = self.oprs[def_op].clone();
101                    v_op.set_sink(v);
102
103                    for source in v_op.get_sources() {
104                        self.usemap
105                            .entry(source)
106                            .or_insert(HashSet::new())
107                            .insert(self.oprs.len());
108                    }
109
110                    self.oprs.push(v_op);
111                    self.defmap.insert(v, self.oprs.len() - 1);
112                }
113            }
114        }
115
116        self.vars.get_mut(v).unwrap()
117    }
118
119    pub fn def_add_varnode_sym(
120        &mut self,
121        v: &'tcx Place<'tcx>,
122        rvalue: &'tcx Rvalue<'tcx>,
123    ) -> &mut VarNode<'tcx, T> {
124        let place_ctx: Vec<&Place<'tcx>> = self.vars.keys().map(|p| *p).collect();
125
126        let local_decls = &self.body.local_decls;
127        let node = VarNode::new_symb(v, SymbExpr::from_rvalue(rvalue, place_ctx.clone()));
128        rap_debug!("def node:{:?}", node);
129        let node_ref: &mut VarNode<'tcx, T> = self
130            .vars
131            .entry(v)
132            .and_modify(|old| *old = node.clone())
133            .or_insert(node);
134        self.usemap.entry(v).or_insert(HashSet::new());
135
136        let ty = local_decls[v.local].ty;
137        let place_ty = v.ty(local_decls, self.tcx);
138
139        if v.projection.is_empty() || self.defmap.contains_key(v) {
140            return node_ref;
141        }
142
143        if !v.projection.is_empty() {
144            let matches: Vec<(_, _)> = self
145                .defmap
146                .iter()
147                .filter(|(p, _)| p.local == v.local && p.projection.is_empty())
148                .map(|(p, &def_op)| (*p, def_op))
149                .collect();
150
151            for (base_place, def_op) in matches {
152                let mut v_op = self.oprs[def_op].clone();
153                v_op.set_sink(v);
154
155                for source in v_op.get_sources() {
156                    self.usemap
157                        .entry(source)
158                        .or_insert(HashSet::new())
159                        .insert(self.oprs.len());
160                }
161
162                self.oprs.push(v_op);
163                self.defmap.insert(v, self.oprs.len() - 1);
164            }
165        }
166        node_ref
167    }
168
169    pub fn resolve_all_symexpr(&mut self) {
170        let lookup_context = self.vars.clone();
171        let mut nodes: Vec<&mut VarNode<'tcx, T>> = self.vars.values_mut().collect();
172        nodes.sort_by(|a, b| a.v.local.as_usize().cmp(&b.v.local.as_usize()));
173        for node in nodes {
174            if let IntervalType::Basic(basic) = &mut node.interval {
175                rap_debug!("======{}=====", node.v.local.as_usize());
176                rap_debug!("Before resolve: lower_expr: {}\n", basic.lower);
177                basic.lower.resolve_lower_bound(&lookup_context);
178                basic.lower.simplify();
179                rap_debug!("After resolve: lower_expr: {}\n", basic.lower);
180                rap_debug!("Before resolve: upper_expr: {}\n", basic.upper);
181                basic.upper.resolve_upper_bound(&lookup_context);
182                basic.upper.simplify();
183
184                rap_debug!("After resolve: upper_expr: {}\n", basic.upper);
185            }
186        }
187    }
188
189    pub fn postprocess_defmap(&mut self) {
190        for place in self.vars.keys() {
191            if !place.projection.is_empty() {
192                if let Some((&base_place, &base_value)) = self
193                    .defmap
194                    .iter()
195                    .find(|(p, _)| p.local == place.local && p.projection.is_empty())
196                {
197                    self.defmap.insert(place, base_value);
198                } else {
199                    rap_trace!("postprocess_defmap: No base place found for {:?}", place);
200                }
201            }
202        }
203    }
204
205    pub fn build_graph(&mut self, body: &'tcx Body<'tcx>) {
206        self.build_value_maps(body);
207        for block in body.basic_blocks.indices() {
208            let block_data: &BasicBlockData<'tcx> = &body[block];
209            for statement in block_data.statements.iter() {
210                self.build_operations(statement, block, body);
211            }
212            self.build_terminator(block, block_data.terminator.as_ref().unwrap());
213        }
214        self.resolve_all_symexpr();
215        self.print_vars();
216        self.print_defmap();
217        self.print_usemap();
218        self.print_symbexpr();
219    }
220
221    pub fn build_value_maps(&mut self, body: &'tcx Body<'tcx>) {
222        for bb in body.basic_blocks.indices() {
223            let block_data = &body[bb];
224            if let Some(terminator) = &block_data.terminator {
225                match &terminator.kind {
226                    TerminatorKind::SwitchInt { discr, targets } => {
227                        if targets.iter().count() == 1 {
228                            self.build_value_branch_map(body, discr, targets, bb, block_data);
229                        }
230                    }
231                    _ => {}
232                }
233            }
234        }
235    }
236
237    fn trace_operand_origin(
238        &self,
239        body: &'tcx Body<'tcx>,
240        mut current_block: BasicBlock,
241        target_place: Place<'tcx>,
242        original: &'tcx Operand<'tcx>,
243    ) -> &'tcx Operand<'tcx> {
244        let mut visited = HashSet::new();
245        let target_local = target_place.local;
246        while visited.insert(current_block) {
247            let data = &body.basic_blocks[current_block];
248            for stmt in data.statements.iter().rev() {
249                if let StatementKind::Assign(assign) = &stmt.kind {
250                    let (lhs, rvalue) = &**assign;
251                    if lhs.local == target_local {
252                        return match rvalue {
253                            Rvalue::Use(op, ..) => op,
254                            _ => original,
255                        };
256                    }
257                }
258            }
259            let preds = &body.basic_blocks.predecessors()[current_block];
260            if preds.len() == 1 {
261                current_block = preds[0];
262            } else {
263                break;
264            }
265        }
266        original
267    }
268
269    pub fn build_value_branch_map(
270        &mut self,
271        body: &'tcx Body<'tcx>,
272        discr: &'tcx Operand<'tcx>,
273        targets: &'tcx SwitchTargets,
274        switch_block: BasicBlock,
275        block_data: &'tcx BasicBlockData<'tcx>,
276    ) {
277        if let Operand::Copy(place) | Operand::Move(place) = discr {
278            if let Some((op1, op2, cmp_op)) = self.extract_condition(place, block_data) {
279                rap_debug!(
280                    "extract_condition op1:{:?} op2:{:?} cmp_op:{:?}\n",
281                    op1,
282                    op2,
283                    cmp_op
284                );
285                let op1 = if let Some(p1) = op1.place() {
286                    self.trace_operand_origin(body, switch_block, p1, op1)
287                } else {
288                    op1
289                };
290
291                let op2 = if let Some(p2) = op2.place() {
292                    self.trace_operand_origin(body, switch_block, p2, op2)
293                } else {
294                    op2
295                };
296                rap_debug!(
297                    "build_value_branch_map op1:{:?} op2:{:?} cmp_op:{:?}\n",
298                    op1,
299                    op2,
300                    cmp_op
301                );
302                let const_op1 = op1.constant();
303                let const_op2 = op2.constant();
304                match (const_op1, const_op2) {
305                    (Some(_), Some(_)) => {}
306                    (Some(c), None) | (None, Some(c)) => {
307                        let const_in_left: bool;
308                        let variable;
309                        if const_op1.is_some() {
310                            const_in_left = true;
311                            variable = match op2 {
312                                Operand::Copy(p) | Operand::Move(p) => p,
313                                _ => panic!("Expected a place"),
314                            };
315                        } else {
316                            const_in_left = false;
317                            variable = match op1 {
318                                Operand::Copy(p) | Operand::Move(p) => p,
319                                _ => panic!("Expected a place"),
320                            };
321                        }
322                        self.add_varnode(variable);
323                        rap_trace!("add_vbm_varnode{:?}\n", variable.clone());
324
325                        let Some(value) = T::from_const(&c.const_) else {
326                            rap_trace!("from_const returned None for const {:?}, skipping VBM", c);
327                            return;
328                        };
329                        let const_range =
330                            Range::new(value.clone(), value.clone(), RangeType::Unknown);
331                        rap_trace!("cmp_op {:?}\n", cmp_op);
332                        rap_trace!("const_in_left {:?}\n", const_in_left);
333                        let mut true_range =
334                            self.apply_comparison(value.clone(), cmp_op, true, const_in_left);
335                        let mut false_range =
336                            self.apply_comparison(value.clone(), cmp_op, false, const_in_left);
337                        true_range.set_regular();
338                        false_range.set_regular();
339                        let target_vec = targets.all_targets();
340
341                        let vbm = ValueBranchMap::new(
342                            variable,
343                            &target_vec[0],
344                            &target_vec[1],
345                            IntervalType::Basic(BasicInterval::new(false_range)),
346                            IntervalType::Basic(BasicInterval::new(true_range)),
347                        );
348                        self.values_branchmap.insert(variable, vbm);
349                    }
350                    (None, None) => {
351                        let CR = Range::new(T::min_value(), T::max_value(), RangeType::Unknown);
352
353                        let p1 = match op1 {
354                            Operand::Copy(p) | Operand::Move(p) => p,
355                            _ => panic!("Expected a place"),
356                        };
357                        let p2 = match op2 {
358                            Operand::Copy(p) | Operand::Move(p) => p,
359                            _ => panic!("Expected a place"),
360                        };
361                        let target_vec = targets.all_targets();
362                        self.add_varnode(&p1);
363                        rap_trace!("add_vbm_varnode{:?}\n", p1.clone());
364
365                        self.add_varnode(&p2);
366                        rap_trace!("add_vbm_varnode{:?}\n", p2.clone());
367                        let flipped_cmp_op = match Self::flipped_binop(cmp_op) {
368                            Some(op) => op,
369                            None => {
370                                rap_debug!(
371                                    "build_value_branch_map: unsupported binop {:?}, skipping\n",
372                                    cmp_op
373                                );
374                                return;
375                            }
376                        };
377                        let reversed_cmp_op = match Self::reverse_binop(cmp_op) {
378                            Some(op) => op,
379                            None => {
380                                rap_debug!(
381                                    "build_value_branch_map: unsupported binop {:?}, skipping\n",
382                                    cmp_op
383                                );
384                                return;
385                            }
386                        };
387                        let reversed_flippedd_cmp_op = match Self::flipped_binop(reversed_cmp_op) {
388                            Some(op) => op,
389                            None => {
390                                rap_debug!(
391                                    "build_value_branch_map: unsupported binop {:?}, skipping\n",
392                                    reversed_cmp_op
393                                );
394                                return;
395                            }
396                        };
397                        let STOp1 = IntervalType::Symb(SymbInterval::new(CR.clone(), p2, cmp_op));
398                        let SFOp1 =
399                            IntervalType::Symb(SymbInterval::new(CR.clone(), p2, flipped_cmp_op));
400                        let STOp2 =
401                            IntervalType::Symb(SymbInterval::new(CR.clone(), p1, reversed_cmp_op));
402                        let SFOp2 = IntervalType::Symb(SymbInterval::new(
403                            CR.clone(),
404                            p1,
405                            reversed_flippedd_cmp_op,
406                        ));
407                        rap_trace!("SFOp1{:?}\n", SFOp1);
408                        rap_trace!("SFOp2{:?}\n", SFOp2);
409                        rap_trace!("STOp1{:?}\n", STOp1);
410                        rap_trace!("STOp2{:?}\n", STOp2);
411                        let vbm_1 =
412                            ValueBranchMap::new(p1, &target_vec[0], &target_vec[1], SFOp1, STOp1);
413                        let vbm_2 =
414                            ValueBranchMap::new(p2, &target_vec[0], &target_vec[1], SFOp2, STOp2);
415                        self.values_branchmap.insert(&p1, vbm_1);
416                        self.values_branchmap.insert(&p2, vbm_2);
417                        self.switchbbs.insert(switch_block, (*p1, *p2));
418                    }
419                }
420            };
421        }
422    }
423
424    pub fn flipped_binop(op: BinOp) -> Option<BinOp> {
425        use BinOp::*;
426        Some(match op {
427            Eq => Eq,
428            Ne => Ne,
429            Lt => Ge,
430            Le => Gt,
431            Gt => Le,
432            Ge => Lt,
433            Add => Add,
434            Mul => Mul,
435            BitXor => BitXor,
436            BitAnd => BitAnd,
437            BitOr => BitOr,
438            _ => {
439                return None;
440            }
441        })
442    }
443
444    fn reverse_binop(op: BinOp) -> Option<BinOp> {
445        use BinOp::*;
446        Some(match op {
447            Eq => Eq,
448            Ne => Ne,
449            Lt => Gt,
450            Le => Ge,
451            Gt => Lt,
452            Ge => Le,
453            Add => Add,
454            Mul => Mul,
455            BitXor => BitXor,
456            BitAnd => BitAnd,
457            BitOr => BitOr,
458            _ => {
459                return None;
460            }
461        })
462    }
463
464    fn extract_condition(
465        &mut self,
466        place: &'tcx Place<'tcx>,
467        switch_block: &'tcx BasicBlockData<'tcx>,
468    ) -> Option<(&'tcx Operand<'tcx>, &'tcx Operand<'tcx>, BinOp)> {
469        for stmt in &switch_block.statements {
470            if let StatementKind::Assign(assign) = &stmt.kind {
471                let (lhs, rvalue) = &**assign;
472                if let Rvalue::BinaryOp(bin_op, pair) = rvalue {
473                    let (op1, op2) = &**pair;
474                    if lhs == place {
475                        let return_op1: &Operand<'tcx> = &op1;
476                        let return_op2: &Operand<'tcx> = &op2;
477
478                        return Some((return_op1, return_op2, *bin_op));
479                    }
480                }
481            }
482        }
483        None
484    }
485
486    fn apply_comparison<U: IntervalArithmetic>(
487        &self,
488        constant: U,
489        cmp_op: BinOp,
490        is_true_branch: bool,
491        const_in_left: bool,
492    ) -> Range<U> {
493        match cmp_op {
494            BinOp::Lt => {
495                if is_true_branch ^ const_in_left {
496                    Range::new(U::min_value(), constant.sub(U::one()), RangeType::Unknown)
497                } else {
498                    Range::new(constant, U::max_value(), RangeType::Unknown)
499                }
500            }
501
502            BinOp::Le => {
503                if is_true_branch ^ const_in_left {
504                    Range::new(U::min_value(), constant, RangeType::Unknown)
505                } else {
506                    Range::new(constant.add(U::one()), U::max_value(), RangeType::Unknown)
507                }
508            }
509
510            BinOp::Gt => {
511                if is_true_branch ^ const_in_left {
512                    Range::new(U::min_value(), constant, RangeType::Unknown)
513                } else {
514                    Range::new(constant.add(U::one()), U::max_value(), RangeType::Unknown)
515                }
516            }
517
518            BinOp::Ge => {
519                if is_true_branch ^ const_in_left {
520                    Range::new(U::min_value(), constant, RangeType::Unknown)
521                } else {
522                    Range::new(constant, U::max_value().sub(U::one()), RangeType::Unknown)
523                }
524            }
525
526            BinOp::Eq => {
527                if is_true_branch ^ const_in_left {
528                    Range::new(U::min_value(), constant, RangeType::Unknown)
529                } else {
530                    Range::new(constant, U::max_value(), RangeType::Unknown)
531                }
532            }
533
534            _ => Range::new(constant.clone(), constant.clone(), RangeType::Empty),
535        }
536    }
537
538    pub fn build_symbolic_intersect_map(&mut self) {
539        for i in 0..self.oprs.len() {
540            if let BasicOpKind::Essa(essaop) = &self.oprs[i] {
541                if let IntervalType::Symb(symbi) = essaop.get_intersect() {
542                    let v = symbi.get_bound();
543                    self.symbmap.entry(v).or_insert_with(HashSet::new).insert(i);
544                    rap_trace!("symbmap insert {:?} {:?}\n", v, essaop);
545                }
546            }
547        }
548    }
549
550    pub fn build_use_map(
551        &mut self,
552        component: &HashSet<&'tcx Place<'tcx>>,
553    ) -> HashMap<&'tcx Place<'tcx>, HashSet<usize>> {
554        // Builds use map
555        let mut comp_use_map = HashMap::new();
556        for &place in component {
557            if let Some(uses) = self.usemap.get(place) {
558                for op in uses.iter() {
559                    let sink = self.oprs[*op].get_sink();
560                    if component.contains(&sink) {
561                        comp_use_map
562                            .entry(place)
563                            .or_insert_with(HashSet::new)
564                            .insert(*op);
565                    }
566                }
567            }
568        }
569
570        self.print_compusemap(component, &comp_use_map);
571        comp_use_map
572    }
573
574    pub fn build_terminator(&mut self, block: BasicBlock, terminator: &'tcx Terminator<'tcx>) {
575        match &terminator.kind {
576            TerminatorKind::Call {
577                func,
578                args,
579                destination,
580                target: _,
581                unwind: _,
582                fn_span: _,
583                call_source,
584            } => {
585                rap_trace!(
586                    "TerminatorKind::Call in block {:?} with function {:?} destination {:?} args {:?}\n",
587                    block,
588                    func,
589                    destination,
590                    args
591                );
592                // Handle the call operation
593                self.add_call_op(destination, args, terminator, func, block);
594            }
595            TerminatorKind::Return => {}
596            TerminatorKind::Goto { target } => {
597                rap_trace!(
598                    "TerminatorKind::Goto in block {:?} targeting block {:?}\n",
599                    block,
600                    target
601                );
602            }
603            TerminatorKind::SwitchInt { discr, targets } => {
604                rap_trace!(
605                    "TerminatorKind::SwitchInt in block {:?} with discr {:?} and targets {:?}\n",
606                    block,
607                    discr,
608                    targets
609                );
610            }
611            _ => {
612                rap_trace!(
613                    "Unsupported terminator kind in block {:?}: {:?}",
614                    block,
615                    terminator.kind
616                );
617            }
618        }
619    }
620
621    pub fn build_operations(
622        &mut self,
623        inst: &'tcx Statement<'tcx>,
624        block: BasicBlock,
625        body: &'tcx Body<'tcx>,
626    ) {
627        match &inst.kind {
628            StatementKind::Assign(assign) => {
629                let (sink, rvalue) = &**assign;
630                match rvalue {
631                    Rvalue::BinaryOp(op, pair) => {
632                        let (op1, op2) = &**pair;
633                        match op {
634                            BinOp::Add
635                            | BinOp::Sub
636                            | BinOp::Mul
637                            | BinOp::Div
638                            | BinOp::Rem
639                            | BinOp::AddUnchecked => {
640                                self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
641                            }
642                            BinOp::AddWithOverflow => {
643                                self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
644                            }
645                            BinOp::SubUnchecked => {
646                                self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
647                            }
648                            BinOp::SubWithOverflow => {
649                                self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
650                            }
651                            BinOp::MulUnchecked => {
652                                self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
653                            }
654                            BinOp::MulWithOverflow => {
655                                self.add_binary_op(sink, inst, rvalue, op1, op2, *op);
656                            }
657
658                            _ => {}
659                        }
660                    }
661                    Rvalue::UnaryOp(unop, operand) => {
662                        self.add_unary_op(sink, inst, rvalue, operand, *unop);
663                    }
664                    Rvalue::Aggregate(kind, operends) => match **kind {
665                        AggregateKind::Adt(def_id, _, _, _, _) => match def_id {
666                            _ if def_id == self.essa => {
667                                self.add_essa_op(sink, inst, rvalue, operends, block)
668                            }
669                            _ if def_id == self.ssa => {
670                                self.add_ssa_op(sink, inst, rvalue, operends)
671                            }
672                            _ => match self.unique_adt_handler(def_id) {
673                                1 => {
674                                    self.add_aggregate_op(sink, inst, rvalue, operends, 1);
675                                }
676                                _ => {
677                                    rap_trace!(
678                                        "AggregateKind::Adt with def_id {:?} in statement {:?} is not handled specially.\n",
679                                        def_id,
680                                        inst
681                                    );
682                                }
683                            },
684                        },
685                        _ => {}
686                    },
687                    Rvalue::Use(operend, ..) => {
688                        self.add_use_op(sink, inst, rvalue, operend);
689                    }
690                    Rvalue::Ref(_, borrowkind, place) => {
691                        self.add_ref_op(sink, inst, rvalue, place, *borrowkind);
692                    }
693                    _ => {}
694                }
695            }
696            _ => {}
697        }
698    }
699
700    fn unique_adt_handler(&mut self, def_id: DefId) -> usize {
701        let adt_path = self.tcx.def_path_str(def_id);
702        rap_trace!("adt_path: {:?}\n", adt_path);
703        if self.unique_adt_path.contains_key(&adt_path) {
704            rap_trace!(
705                "unique_adt_handler for def_id: {:?} -> {}\n",
706                def_id,
707                adt_path
708            );
709            return *self.unique_adt_path.get(&adt_path).unwrap();
710        }
711        0
712    }
713    /// Adds a function call operation to the graph.
714
715    fn add_call_op(
716        &mut self,
717        sink: &'tcx Place<'tcx>,
718        args: &'tcx Box<[Spanned<Operand<'tcx>>]>,
719        terminator: &'tcx Terminator<'tcx>,
720        func: &'tcx Operand<'tcx>,
721        block: BasicBlock,
722    ) {
723        rap_trace!("add_call_op for sink: {:?} {:?}\n", sink, terminator);
724        let sink_node = self.add_varnode(&sink);
725
726        // Convert Operand arguments to Place arguments.
727        // An Operand can be a Constant or a moved/copied Place.
728        // We only care about Places for our analysis.
729        let mut path = String::new();
730        let mut func_def_id = None;
731        if let Operand::Constant(c_box) = func {
732            let const_operand = &**c_box;
733            let fn_ty = const_operand.ty();
734            if let ty::TyKind::FnDef(def_id, _substs) = fn_ty.kind() {
735                // Found the DefId for a direct function call!
736                rap_debug!("fn_ty: {:?}\n", fn_ty);
737                if def_id.krate != LOCAL_CRATE {
738                    path = self.tcx.def_path_str(*def_id);
739
740                    rap_debug!("called external/no-MIR fn: {:?} -> {}", def_id, path);
741                }
742                func_def_id = Some(def_id);
743            }
744        }
745
746        if let Some(def_id) = func_def_id {
747            rap_trace!(
748                "TerminatorKind::Call in block {:?} with DefId {:?}\n",
749                block,
750                def_id
751            );
752            // You can now use the def_id
753        } else {
754            rap_trace!(
755                "TerminatorKind::Call in block {:?} is an indirect call (e.g., function pointer)\n",
756                block
757            );
758            // This handles cases where the call is not a direct one,
759            // such as calling a function pointer stored in a variable.
760        }
761        let mut constant_count = 0 as usize;
762        let arg_count = args.len();
763        let mut arg_operands: Vec<Operand<'tcx>> = Vec::new();
764        let mut places = Vec::new();
765        for op in args.iter() {
766            match &op.node {
767                Operand::Copy(place) | Operand::Move(place) => {
768                    arg_operands.push(op.node.clone());
769                    places.push(place);
770                    self.add_varnode(place);
771                    self.usemap
772                        .entry(place)
773                        .or_default()
774                        .insert(self.oprs.len());
775                }
776
777                Operand::Constant(_) => {
778                    // If it's not a Place, we can still add it as an operand.
779                    // This is useful for constants or other non-place operands.
780                    arg_operands.push(op.node.clone());
781                    constant_count += 1;
782                }
783                #[cfg(rapx_ge_99)]
784                Operand::RuntimeChecks(_) => {}
785            }
786        }
787        {
788            let bi = BasicInterval::default();
789
790            let Some(def_id) = func_def_id else {
791                rap_debug!("Call to function without DefId, skipping\n");
792                return;
793            };
794            let call_op = CallOp::new(
795                IntervalType::Basic(bi),
796                &sink,
797                terminator,
798                arg_operands,
799                *def_id,
800                path,
801                places,
802            );
803            rap_debug!("call_op: {:?}\n", call_op);
804            let bop_index = self.oprs.len();
805
806            // Insert the operation into the graph.
807            self.oprs.push(BasicOpKind::Call(call_op));
808
809            // Insert this definition in defmap
810            self.defmap.insert(&sink, bop_index);
811            if constant_count == arg_count {
812                rap_trace!("all args are constants\n");
813                self.const_func_place.insert(&sink, bop_index);
814            }
815        }
816    }
817
818    fn add_ssa_op(
819        &mut self,
820        sink: &'tcx Place<'tcx>,
821        inst: &'tcx Statement<'tcx>,
822        rvalue: &'tcx Rvalue<'tcx>,
823
824        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
825    ) {
826        rap_trace!("ssa_op{:?}\n", inst);
827
828        let sink_node: &mut VarNode<'_, T> = self.def_add_varnode_sym(sink, rvalue);
829        rap_trace!("addsink_in_ssa_op{:?}\n", sink_node);
830
831        let BI: BasicInterval<T> = BasicInterval::default();
832        let mut phiop = PhiOp::new(IntervalType::Basic(BI), sink, inst);
833        let bop_index = self.oprs.len();
834        for i in 0..operands.len() {
835            let source = match &operands[FieldIdx::from_usize(i)] {
836                Operand::Copy(place) | Operand::Move(place) => {
837                    self.use_add_varnode_sym(place, rvalue);
838                    Some(place)
839                }
840                _ => None,
841            };
842            if let Some(source) = source {
843                self.use_add_varnode_sym(source, rvalue);
844                phiop.add_source(source);
845                rap_trace!("addvar_in_ssa_op{:?}\n", source);
846                self.usemap.entry(source).or_default().insert(bop_index);
847            }
848        }
849        // Insert the operation in the graph.
850
851        self.oprs.push(BasicOpKind::Phi(phiop));
852
853        // Insert this definition in defmap
854
855        self.defmap.insert(sink, bop_index);
856    }
857
858    fn add_use_op(
859        &mut self,
860        sink: &'tcx Place<'tcx>,
861        inst: &'tcx Statement<'tcx>,
862        rvalue: &'tcx Rvalue<'tcx>,
863        op: &'tcx Operand<'tcx>,
864    ) {
865        rap_trace!("use_op{:?}\n", inst);
866
867        let BI: BasicInterval<T> = BasicInterval::default();
868        let source: Option<&'tcx Place<'tcx>> = None;
869
870        match op {
871            Operand::Copy(place) | Operand::Move(place) => {
872                if sink.local == RETURN_PLACE && sink.projection.is_empty() {
873                    self.rerurn_places.insert(place);
874
875                    let sink_node = self.def_add_varnode_sym(sink, rvalue);
876
877                    rap_debug!("add_return_place{:?}\n", place);
878                } else {
879                    self.use_add_varnode_sym(place, rvalue);
880                    rap_trace!("addvar_in_use_op{:?}\n", place);
881                    let sink_node = self.def_add_varnode_sym(sink, rvalue);
882                    let useop = UseOp::new(IntervalType::Basic(BI), sink, inst, Some(place), None);
883                    // Insert the operation in the graph.
884                    let bop_index = self.oprs.len();
885
886                    self.oprs.push(BasicOpKind::Use(useop));
887                    // Insert this definition in defmap
888                    self.usemap.entry(place).or_default().insert(bop_index);
889
890                    self.defmap.insert(sink, bop_index);
891                }
892            }
893            Operand::Constant(constant) => {
894                rap_trace!("add_constant_op{:?}\n", inst);
895                let Some(c) = op.constant() else {
896                    rap_trace!("add_constant_op: constant is None\n");
897                    return;
898                };
899                let useop = UseOp::new(IntervalType::Basic(BI), sink, inst, None, Some(c.const_));
900                // Insert the operation in the graph.
901                let bop_index = self.oprs.len();
902
903                self.oprs.push(BasicOpKind::Use(useop));
904                // Insert this definition in defmap
905
906                self.defmap.insert(sink, bop_index);
907                let sink_node = self.def_add_varnode_sym(sink, rvalue);
908
909                if let Some(value) = T::from_const(&c.const_) {
910                    sink_node.set_range(Range::new(
911                        value.clone(),
912                        value.clone(),
913                        RangeType::Regular,
914                    ));
915                    rap_trace!("set_const {:?} value: {:?}\n", sink_node, value);
916                } else {
917                    sink_node.set_range(Range::bottom());
918                };
919            }
920            #[cfg(rapx_ge_99)]
921            Operand::RuntimeChecks(_) => {}
922        }
923    }
924
925    fn add_essa_op(
926        &mut self,
927        sink: &'tcx Place<'tcx>,
928        inst: &'tcx Statement<'tcx>,
929        rvalue: &'tcx Rvalue<'tcx>,
930        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
931        block: BasicBlock,
932    ) {
933        let sink_node = self.def_add_varnode_sym(sink, rvalue);
934
935
936        let loc_1: usize = 0;
937        let loc_2: usize = 1;
938        let source1 = match &operands[FieldIdx::from_usize(loc_1)] {
939            Operand::Copy(place) | Operand::Move(place) => {
940                self.use_add_varnode_sym(place, rvalue);
941                Some(place)
942            }
943            _ => None,
944        };
945        let op = &operands[FieldIdx::from_usize(loc_2)];
946        let bop_index = self.oprs.len();
947        let BI: IntervalType<'_, T>;
948        rap_trace!("essa_op operand1 {:?}\n", source1.unwrap());
949        if let Operand::Constant(c) = op {
950            let vbm = self.values_branchmap.get(source1.unwrap()).unwrap();
951            if block == *vbm.get_bb_true() {
952                rap_trace!("essa_op true branch{:?}\n", block);
953                BI = vbm.get_itv_t();
954            } else {
955                rap_trace!("essa_op false branch{:?}\n", block);
956                BI = vbm.get_itv_f();
957            }
958            self.usemap
959                .entry(source1.unwrap())
960                .or_default()
961                .insert(bop_index);
962
963            let essaop = EssaOp::new(BI, sink, inst, source1.unwrap(), false);
964            rap_trace!(
965                "addvar_in_essa_op {:?} from const {:?}\n",
966                essaop,
967                source1.unwrap()
968            );
969
970            // Insert the operation in the graph.
971
972            self.oprs.push(BasicOpKind::Essa(essaop));
973            // Insert this definition in defmap
974
975            self.defmap.insert(sink, bop_index);
976        } else {
977            let vbm = self.values_branchmap.get(source1.unwrap()).unwrap();
978            if block == *vbm.get_bb_true() {
979                rap_trace!("essa_op true branch{:?}\n", block);
980                BI = vbm.get_itv_t();
981            } else {
982                rap_trace!("essa_op false branch{:?}\n", block);
983                BI = vbm.get_itv_f();
984            }
985            let source2 = match op {
986                Operand::Copy(place) | Operand::Move(place) => {
987                    self.use_add_varnode_sym(place, rvalue);
988                    Some(place)
989                }
990                _ => None,
991            };
992            self.usemap
993                .entry(source1.unwrap())
994                .or_default()
995                .insert(bop_index);
996            let essaop = EssaOp::new(BI, sink, inst, source1.unwrap(), true);
997            // Insert the operation in the graph.
998            rap_trace!(
999                "addvar_in_essa_op {:?} from {:?}\n",
1000                essaop,
1001                source1.unwrap()
1002            );
1003
1004            self.oprs.push(BasicOpKind::Essa(essaop));
1005
1006            self.defmap.insert(sink, bop_index);
1007        }
1008    }
1009
1010    pub fn add_aggregate_op(
1011        &mut self,
1012        sink: &'tcx Place<'tcx>,
1013        inst: &'tcx Statement<'tcx>,
1014        rvalue: &'tcx Rvalue<'tcx>,
1015        operands: &'tcx IndexVec<FieldIdx, Operand<'tcx>>,
1016        unique_adt: usize,
1017    ) {
1018        rap_trace!("aggregate_op {:?}\n", inst);
1019
1020        let BI: BasicInterval<T> = BasicInterval::default();
1021        let mut agg_operands: Vec<AggregateOperand<'tcx>> = Vec::with_capacity(operands.len());
1022
1023        for operand in operands {
1024            match operand {
1025                Operand::Copy(place) | Operand::Move(place) => {
1026                    if sink.local == RETURN_PLACE && sink.projection.is_empty() {
1027                        self.rerurn_places.insert(place);
1028                        self.def_add_varnode_sym(sink, rvalue);
1029                        rap_debug!("add_return_place {:?}\n", place);
1030                    } else {
1031                        self.use_add_varnode_sym(place, rvalue);
1032                        rap_trace!("addvar_in_aggregate_op {:?}\n", place);
1033                        agg_operands.push(AggregateOperand::Place(place));
1034                    }
1035                }
1036                Operand::Constant(c) => {
1037                    rap_trace!("add_constant_aggregate_op {:?}\n", c);
1038                    agg_operands.push(AggregateOperand::Const(c.const_));
1039
1040                    let sink_node = self.def_add_varnode_sym(sink, rvalue);
1041                    if let Some(value) = T::from_const(&c.const_) {
1042                        sink_node.set_range(Range::new(
1043                            value.clone(),
1044                            value.clone(),
1045                            RangeType::Regular,
1046                        ));
1047                        rap_trace!("set_const {:?} value: {:?}\n", sink_node, value);
1048                    } else {
1049                        sink_node.set_range(Range::bottom());
1050                    }
1051                }
1052                #[cfg(rapx_ge_99)]
1053                Operand::RuntimeChecks(_) => {}
1054            }
1055        }
1056
1057        if agg_operands.is_empty() {
1058            rap_trace!("aggregate_op has no operands, skipping\n");
1059            return;
1060        }
1061
1062        let agg_op = AggregateOp::new(
1063            IntervalType::Basic(BI),
1064            sink,
1065            inst,
1066            agg_operands,
1067            unique_adt,
1068        );
1069        let bop_index = self.oprs.len();
1070        self.oprs.push(BasicOpKind::Aggregate(agg_op));
1071
1072        for operand in operands {
1073            if let Operand::Copy(place) | Operand::Move(place) = operand {
1074                self.usemap.entry(place).or_default().insert(bop_index);
1075            }
1076        }
1077
1078        self.defmap.insert(sink, bop_index);
1079
1080        self.def_add_varnode_sym(sink, rvalue);
1081    }
1082
1083    fn add_unary_op(
1084        &mut self,
1085        sink: &'tcx Place<'tcx>,
1086        inst: &'tcx Statement<'tcx>,
1087        rvalue: &'tcx Rvalue<'tcx>,
1088        operand: &'tcx Operand<'tcx>,
1089        op: UnOp,
1090    ) {
1091        rap_trace!("unary_op{:?}\n", inst);
1092
1093        let sink_node = self.def_add_varnode_sym(sink, rvalue);
1094        rap_trace!("addsink_in_unary_op{:?}\n", sink_node);
1095
1096        let BI: BasicInterval<T> = BasicInterval::default();
1097        let loc_1: usize = 0;
1098
1099        let source = match operand {
1100            Operand::Copy(place) | Operand::Move(place) => {
1101                self.add_varnode(place);
1102                Some(place)
1103            }
1104            _ => None,
1105        };
1106
1107        rap_trace!("addvar_in_unary_op{:?}\n", source.unwrap());
1108        self.use_add_varnode_sym(&source.unwrap(), rvalue);
1109
1110        let unaryop = UnaryOp::new(IntervalType::Basic(BI), sink, inst, source.unwrap(), op);
1111        // Insert the operation in the graph.
1112        let bop_index = self.oprs.len();
1113
1114        self.oprs.push(BasicOpKind::Unary(unaryop));
1115        // Insert this definition in defmap
1116
1117        self.defmap.insert(sink, bop_index);
1118    }
1119
1120    fn add_binary_op(
1121        &mut self,
1122        sink: &'tcx Place<'tcx>,
1123        inst: &'tcx Statement<'tcx>,
1124        rvalue: &'tcx Rvalue<'tcx>,
1125        op1: &'tcx Operand<'tcx>,
1126        op2: &'tcx Operand<'tcx>,
1127        bin_op: BinOp,
1128    ) {
1129        rap_trace!("binary_op{:?}\n", inst);
1130
1131        // Define the sink node (Def)
1132        let sink_node = self.def_add_varnode_sym(sink, rvalue);
1133        rap_trace!("addsink_in_binary_op{:?}\n", sink_node);
1134
1135        let bop_index = self.oprs.len();
1136        let bi: BasicInterval<T> = BasicInterval::default();
1137
1138        // Match both operands simultaneously to handle all combinations.
1139        // Goal: Ensure source1 is always a Place if at least one Place exists.
1140        let (source1_place, source2_place, const_val) = match (op1, op2) {
1141            // Case 1: Place + Place
1142            (Operand::Copy(p1) | Operand::Move(p1), Operand::Copy(p2) | Operand::Move(p2)) => {
1143                self.use_add_varnode_sym(p1, rvalue);
1144                self.use_add_varnode_sym(p2, rvalue);
1145                rap_trace!("addvar_in_binary_op p1:{:?}, p2:{:?}\n", p1, p2);
1146
1147                (Some(p1), Some(p2), None)
1148            }
1149
1150            // Case 2: Place + Constant
1151            (Operand::Copy(p1) | Operand::Move(p1), Operand::Constant(c2)) => {
1152                self.use_add_varnode_sym(p1, rvalue);
1153                rap_trace!("addvar_in_binary_op p1:{:?}\n", p1);
1154
1155                (Some(p1), None, Some(c2.const_))
1156            }
1157
1158            // Case 3: Constant + Place
1159            // Here we normalize: Treat the Place (op2) as source1, and the Constant (op1) as the const value.
1160            // NOTE: Be careful with non-commutative operations (Sub, Div) in your interval logic later,
1161            // as the physical order is swapped here.
1162            (Operand::Constant(c1), Operand::Copy(p2) | Operand::Move(p2)) => {
1163                self.use_add_varnode_sym(p2, rvalue);
1164                rap_trace!("addvar_in_binary_op p2(as source1):{:?}\n", p2);
1165
1166                // Assign p2 to the first return position to make it source1
1167                (Some(p2), None, Some(c1.const_))
1168            }
1169
1170            // Case 4: Constant + Constant
1171            (Operand::Constant(c1), Operand::Constant(_)) => {
1172                // Logic depends on how you want to handle two constants.
1173                // Usually keeping one is sufficient for the struct signature.
1174                (None, None, Some(c1.const_))
1175            }
1176            #[cfg(rapx_ge_99)]
1177            _ => (None, None, None),
1178        };
1179
1180        // Construct the BinaryOp
1181        let bop = BinaryOp::new(
1182            IntervalType::Basic(bi),
1183            sink,
1184            inst,
1185            source1_place, // This is guaranteed to be the Place (if one exists)
1186            source2_place,
1187            const_val,
1188            bin_op.clone(),
1189        );
1190
1191        self.oprs.push(BasicOpKind::Binary(bop));
1192
1193        // Update DefMap
1194        self.defmap.insert(sink, bop_index);
1195
1196        // Update UseMap
1197        if let Some(place) = source1_place {
1198            self.usemap.entry(place).or_default().insert(bop_index);
1199        }
1200
1201        if let Some(place) = source2_place {
1202            self.usemap.entry(place).or_default().insert(bop_index);
1203        }
1204    }
1205
1206    fn add_ref_op(
1207        &mut self,
1208        sink: &'tcx Place<'tcx>,
1209        inst: &'tcx Statement<'tcx>,
1210        rvalue: &'tcx Rvalue<'tcx>,
1211        place: &'tcx Place<'tcx>,
1212        borrowkind: BorrowKind,
1213    ) {
1214        rap_trace!("ref_op {:?}\n", inst);
1215
1216        let BI: BasicInterval<T> = BasicInterval::default();
1217
1218        let source_node = self.use_add_varnode_sym(place, rvalue);
1219
1220        let sink_node = self.def_add_varnode_sym(sink, rvalue);
1221
1222        let refop = RefOp::new(IntervalType::Basic(BI), sink, inst, place, borrowkind);
1223        let bop_index = self.oprs.len();
1224        self.oprs.push(BasicOpKind::Ref(refop));
1225
1226        self.usemap.entry(place).or_default().insert(bop_index);
1227
1228        self.defmap.insert(sink, bop_index);
1229
1230        rap_trace!(
1231            "add_ref_op: created RefOp from {:?} to {:?} at {:?}\n",
1232            place,
1233            sink,
1234            inst
1235        );
1236    }
1237}
rapx/analysis/range/domain/constraint_graph/graph.rs

rapx/analysis/range/domain/constraint_graph/
graph.rs
