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};
14use 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 pub vars: VarNodes<'tcx, T>, pub oprs: GenOprs<'tcx, T>, pub defmap: DefMap<'tcx>, pub usemap: UseMap<'tcx>, pub symbmap: SymbMap<'tcx>, pub values_branchmap: ValuesBranchMap<'tcx, T>, constant_vector: Vec<T>, 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, 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 defmap: DefMap::new(),
71 usemap: UseMap::new(),
72 symbmap: SymbMap::new(),
73 values_branchmap: ValuesBranchMap::new(),
74 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 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 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 for statement in block_data.statements.iter() {
227 self.build_operations(statement, block);
228 }
229 }
230
231 }
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 }
249 _ => {
250 }
255 }
256 }
257 }
258 }
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 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 = 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 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 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 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 }
497 pub fn build_use_map(
498 &mut self,
499 component: &HashSet<&'tcx Place<'tcx>>,
500 ) -> HashMap<&'tcx Place<'tcx>, HashSet<usize>> {
501 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 }
560 if def_id == self.ssa {
561 self.add_ssa_op(sink, inst, operends);
562 }
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 self.oprs.push(BasicOpKind::Phi(phiop));
605
606 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 let bop_index = self.oprs.len();
633
634 self.oprs.push(BasicOpKind::Use(useop));
635 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 } 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 let sink_node = self.add_varnode(sink);
672 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 self.oprs.push(BasicOpKind::Essa(essaop));
709 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 let essaop = EssaOp::new(BI, sink, inst, source1.unwrap(), 0, true);
738 rap_trace!(
740 "addvar_in_essa_op {:?} from {:?}\n",
741 essaop,
742 source1.unwrap()
743 );
744
745 self.oprs.push(BasicOpKind::Essa(essaop));
746 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 let bop_index = self.oprs.len();
778
779 self.oprs.push(BasicOpKind::Unary(unaryop));
780 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 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 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 }
860 fn fix_intersects(&mut self, component: &HashSet<&'tcx Place<'tcx>>) {
861 for &place in component.iter() {
862 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 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 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 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 } else if old_lower.clone() <= new_lower.clone() {
944 final_lower = new_lower.clone();
945
946 };
949 if old_upper.clone() == T::max_value() && new_upper.clone() < T::max_value() {
950 final_upper = new_upper.clone();
951 } else if old_upper.clone() >= new_upper.clone() {
954 final_upper = new_upper.clone();
955 }
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 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 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 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 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 let comp_use_map = self.build_use_map(&component);
1124 let mut entry_points = HashSet::new();
1126 self.generate_entry_points(&component, &mut entry_points);
1129 rap_trace!("entry_points {:?} \n", entry_points);
1130 self.pre_update(&comp_use_map, &entry_points);
1132 self.fix_intersects(&component);
1133
1134 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 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 }
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 }
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 };
1309
1310 if single {
1311 } 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 }
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 }
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}