Skip to main content

rapx/vm/mir_rules/call/
effect.rs

1mod memory;
2mod numeric;
3mod simd;
4
5use rustc_middle::{
6    mir::{Local, Operand},
7    ty::{Ty, TyKind},
8};
9use z3::ast::{Ast, Bool, Int};
10
11use super::super::super::state::{
12    AllocId, Provenance, ValueFacts, ValueSource, VmExecutor, VmValue,
13};
14use crate::def_ids::type_ids;
15use crate::compat::Spanned;
16use crate::util::mir_utils;
17use crate::analysis::dataflow::call_summary::{
18    BoundedArithmeticOp, CallEffect, OverflowOp, SimdArithOp, SimdCmpOp,
19};
20
21impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
22    fn set_dest_as_heap_ptr(&mut self, arg_val: &VmValue<'z3, 'tcx>, dest: Local) {
23        let mut val = arg_val.clone();
24        val.ty = self.body().local_decls[dest].ty;
25        val.facts.non_null = true;
26        val.facts.init = true;
27        self.set_local(dest, val);
28    }
29
30    pub(crate) fn apply_call_effect(
31        &mut self,
32        effect: &CallEffect,
33        args: &[VmValue<'z3, 'tcx>],
34        caller_arg_locals: &[Option<Local>],
35        call_args: &[Spanned<Operand<'tcx>>],
36        dest: Local,
37        func: &Operand<'tcx>,
38    ) {
39        match effect {
40            CallEffect::ReallocateVec { arg } => {
41                if let Some(value) = args.get(*arg) {
42                    self.reallocate_vec_backing(value);
43                }
44            }
45            CallEffect::ReturnLayoutSymbolic { is_size } => {
46                let ty = mir_utils::fn_def_first_type_arg(func).expect("layout effect built from a FnDef");
47                let term = if *is_size {
48                    self.size_sym(ty)
49                } else {
50                    self.align_sym(ty)
51                };
52                let dest_ty = self.body().local_decls[dest].ty;
53                self.set_local(dest, VmValue::new(term, dest_ty));
54            }
55            CallEffect::ReturnAliasArg { arg } => {
56                if let Some(arg_val) = args.get(*arg) {
57                    self.set_dest_as_heap_ptr(arg_val, dest);
58                }
59            }
60            CallEffect::ReturnArgValue { arg } => {
61                if let Some(arg_val) = args.get(*arg) {
62                    let mut val = arg_val.clone();
63                    val.ty = self.body().local_decls[dest].ty;
64                    val.facts.init = true;
65                    self.set_local(dest, val);
66                }
67            }
68            CallEffect::ReturnOpaque => {
69                self.set_opaque_intrinsic_result(dest);
70            }
71            CallEffect::ReturnFloatToIntUnchecked => {
72                let dest_ty = self.body().local_decls[dest].ty;
73                let result = call_args.first()
74                    .and_then(|arg| crate::analysis::dataflow::call_summary::constant_float_to_int(self.tcx, &arg.node, dest_ty))
75                    .and_then(|bits| self.scalar_bits_term(dest_ty, bits));
76                if let Some(term) = result {
77                    self.set_local(dest, VmValue::new(term, dest_ty));
78                } else {
79                    self.set_opaque_intrinsic_result(dest);
80                }
81            }
82            CallEffect::ReturnSizeOfVal { arg } => {
83                let size = args.get(*arg).and_then(|value| {
84                    let pointee = mir_utils::pointee_ty(value.ty)?;
85                    match pointee.kind() {
86                        TyKind::Slice(elem) => {
87                            let len = self.slice_len_from_value(value)?;
88                            Some(Int::mul(self.z3_ctx, &[&len, &self.size_sym(*elem)]))
89                        }
90                        TyKind::Dynamic(..) => None,
91                        _ => Some(self.size_sym(pointee)),
92                    }
93                });
94                if let Some(size) = size {
95                    let ty = self.body().local_decls[dest].ty;
96                    self.set_local(dest, VmValue::new(size, ty));
97                } else {
98                    self.set_opaque_intrinsic_result(dest);
99                }
100            }
101            CallEffect::ReturnAlignOfVal { arg } => {
102                let align = args.get(*arg).and_then(|value| {
103                    let pointee = mir_utils::pointee_ty(value.ty)?;
104                    match pointee.kind() {
105                        TyKind::Slice(elem) => Some(self.align_sym(*elem)),
106                        TyKind::Str => Some(Int::from_u64(self.z3_ctx, 1)),
107                        TyKind::Dynamic(..) => None,
108                        _ => Some(self.align_sym(pointee)),
109                    }
110                });
111                if let Some(align) = align {
112                    let ty = self.body().local_decls[dest].ty;
113                    self.set_local(dest, VmValue::new(align, ty));
114                } else {
115                    self.set_opaque_intrinsic_result(dest);
116                }
117            }
118            CallEffect::ReturnCompareBytes {
119                left_arg,
120                right_arg,
121                count_arg,
122            } => {
123                let Some((left, right, count)) = args
124                    .get(*left_arg)
125                    .zip(args.get(*right_arg))
126                    .zip(args.get(*count_arg))
127                    .map(|((left, right), count)| (left, right, count))
128                else {
129                    self.record_unsupported("compare_bytes arguments");
130                    return;
131                };
132                let ty = self.body().local_decls[dest].ty;
133                let term = if count.z3_term.simplify().as_u64() == Some(0)
134                    || left.z3_term == right.z3_term
135                {
136                    Int::from_u64(self.z3_ctx, 0)
137                } else {
138                    let result = self.fresh_int("compare_bytes_result");
139                    if let Some((min, max, _, _)) = self.integer_limits(ty) {
140                        self.path_state.constraints.assertions.push(result.ge(&min));
141                        self.path_state.constraints.assertions.push(result.le(&max));
142                    }
143                    result
144                };
145                self.set_local(dest, VmValue::new(term, ty));
146            }
147            CallEffect::ReturnMaskedPointer {
148                pointer_arg,
149                mask_arg,
150            } => {
151                let unchanged = args.get(*mask_arg).is_some_and(|mask| {
152                    let value = mask.z3_term.simplify();
153                    value.as_u64() == Some(usize::MAX as u64) || value.as_i64() == Some(-1)
154                });
155                if unchanged {
156                    if let Some(pointer) = args.get(*pointer_arg) {
157                        let mut pointer = pointer.clone();
158                        pointer.ty = self.body().local_decls[dest].ty;
159                        self.set_local(dest, pointer);
160                    }
161                } else {
162                    self.set_opaque_intrinsic_result(dest);
163                }
164            }
165            effect @ (CallEffect::LoadMemory { .. }
166            | CallEffect::StoreMemory { .. }
167            | CallEffect::AtomicRmw { .. }
168            | CallEffect::CopyMemory { .. }
169            | CallEffect::SwapMemory { .. }
170            | CallEffect::FillBytes { .. }) => {
171                self.apply_memory_effect(effect, args, dest);
172            }
173            effect @ (CallEffect::SimdCompare { .. }
174            | CallEffect::SimdArithmetic { .. }
175            | CallEffect::SimdOpaque
176            | CallEffect::SimdSplat { .. }
177            | CallEffect::SimdExtract { .. }
178            | CallEffect::SimdInsert { .. }
179            | CallEffect::SimdHavocMemory { .. }
180            | CallEffect::SimdMaskedFallback { .. }
181            | CallEffect::SimdBitmask { .. }) => {
182                self.apply_simd_effect(effect, args, caller_arg_locals, dest);
183            }
184            CallEffect::ReturnRawEq {
185                left_arg,
186                right_arg,
187            } => {
188                let ty = self.body().local_decls[dest].ty;
189                let Some((left, right)) = args.get(*left_arg).zip(args.get(*right_arg)) else {
190                    self.record_unsupported_effect("ReturnRawEq arguments unavailable");
191                    return;
192                };
193                if left.z3_term == right.z3_term && left.ty == right.ty {
194                    self.set_local(dest, VmValue::new(Int::from_u64(self.z3_ctx, 1), ty));
195                } else if let Some((left_local, right_local)) = self
196                    .find_local_by_address(&left.z3_term)
197                    .zip(self.find_local_by_address(&right.z3_term))
198                    .filter(|(left_local, right_local)| {
199                        let left_ty = self.body().local_decls[*left_local].ty;
200                        left_ty == self.body().local_decls[*right_local].ty
201                            && matches!(left_ty.kind(), TyKind::Int(_) | TyKind::Uint(_))
202                    })
203                    && let Some((left_value, right_value)) = self
204                        .local_value(left_local)
205                        .zip(self.local_value(right_local))
206                {
207                    let one = Int::from_u64(self.z3_ctx, 1);
208                    let zero = Int::from_u64(self.z3_ctx, 0);
209                    let term = left_value
210                        .z3_term
211                        ._eq(&right_value.z3_term)
212                        .ite(&one, &zero);
213                    self.set_local(dest, VmValue::new(term, ty));
214                } else {
215                    let term = self.fresh_int("raw_eq_result");
216                    self.path_state.inline.opaque_intrinsic_terms.insert(term.clone());
217                    self.set_local(dest, VmValue::new(term, ty));
218                }
219            }
220            CallEffect::ReturnExactDiv { lhs_arg, rhs_arg } => {
221                let ty = self.body().local_decls[dest].ty;
222                let Some((lhs, rhs)) = args.get(*lhs_arg).zip(args.get(*rhs_arg)) else {
223                    self.record_unsupported_effect("ReturnExactDiv arguments unavailable");
224                    return;
225                };
226                if !matches!(ty.kind(), TyKind::Uint(_)) {
227                    self.record_unsupported_effect("ReturnExactDiv result type unsupported");
228                    return;
229                }
230                self.set_local(dest, VmValue::new(lhs.z3_term.div(&rhs.z3_term), ty));
231            }
232            CallEffect::SelectUnpredictable => {
233                if args.len() >= 3 {
234                    let term = self.fresh_int(&format!("selunpred_{}", dest.as_usize()));
235                    let dest_ty = self.body().local_decls[dest].ty;
236                    let eq1 = term._eq(&args[1].z3_term);
237                    let eq2 = term._eq(&args[2].z3_term);
238                    self.path_state.constraints.assertions.push(Bool::or(self.z3_ctx, &[&eq1, &eq2]));
239                    let prov = args[1]
240                        .provenance
241                        .clone()
242                        .or_else(|| args[2].provenance.clone());
243                    self.set_local(
244                        dest,
245                        VmValue {
246                            z3_term: term,
247                            ty: dest_ty,
248                            provenance: prov,
249                            facts: ValueFacts::default(),
250                            source: ValueSource::None,
251                        },
252                    );
253                }
254            }
255            CallEffect::ReturnTransparentDeref { arg, peel } => {
256                if let Some(arg_val) = args.get(*arg) {
257                    self.set_dest_as_heap_ptr(arg_val, dest);
258                    if let Some(arg_local) = caller_arg_locals.get(*arg).copied().flatten() {
259                        let keys: Vec<Vec<usize>> = self.field_paths(arg_local);
260                        for path in keys {
261                            if path.len() > *peel
262                                && path[..*peel].iter().all(|&f| f == 0)
263                                && let Some(v) = self.field_value(arg_local, &path).cloned()
264                            {
265                                self.set_field_value(dest, path[*peel..].to_vec(), v);
266                            }
267                        }
268                    }
269                }
270            }
271            CallEffect::ReturnWrappingPointerOffset {
272                base_arg,
273                offset_arg,
274            } => {
275                if let (Some(base), Some(offset)) = (args.get(*base_arg), args.get(*offset_arg)) {
276                    let stride = mir_utils::pointee_ty(base.ty).and_then(|pointee| {
277                        let (_, size) = mir_utils::type_layout(
278                            self.tcx,
279                            self.path_state.current_frame.current_def_id,
280                            pointee,
281                        )?;
282                        if size == 0 && mir_utils::ty_has_type_param(pointee) {
283                            None
284                        } else {
285                            Some(size)
286                        }
287                    });
288                    self.apply_pointer_add(dest, base, offset, stride, false);
289                }
290            }
291            CallEffect::ReturnPtrOffsetFrom { ptr_arg, base_arg } => {
292                let dest_ty = self.body().local_decls[dest].ty;
293                let ptr = args.get(*ptr_arg).cloned();
294                let base = args.get(*base_arg).cloned();
295                let count = match (ptr.as_ref(), base.as_ref()) {
296                    (Some(p), Some(b)) => self.iter_len_from_ptrs(b, p).unwrap_or_else(|| {
297                        self.fresh_int(&format!("ptr_offset_from_{}", dest.as_usize()))
298                    }),
299                    _ => self.fresh_int(&format!("ptr_offset_from_{}", dest.as_usize())),
300                };
301                self.set_local(
302                    dest,
303                    VmValue {
304                        z3_term: count,
305                        ty: dest_ty,
306                        provenance: None,
307                        facts: ValueFacts::default(),
308                        source: ValueSource::None,
309                    },
310                );
311            }
312            CallEffect::ReturnConst { value } => {
313                let dest_ty = self.body().local_decls[dest].ty;
314                let term = Int::from_u64(self.z3_ctx, *value);
315                let val = VmValue::new(term, dest_ty);
316                self.set_local(dest, val);
317            }
318            CallEffect::ReturnAlignOffset { ptr_arg, align_arg } => {
319                let dest_ty = self.body().local_decls[dest].ty;
320                let offset = self.fresh_int(&format!("align_offset_{}", dest.as_usize()));
321                if let (Some(ptr_val), Some(align_val)) = (args.get(*ptr_arg), args.get(*align_arg))
322                {
323                    let elem = mir_utils::pointee_ty(ptr_val.ty)
324                        .map(|pointee| self.size_sym(pointee))
325                        .unwrap_or_else(|| Int::from_u64(self.z3_ctx, 1));
326                    let byte_off = Int::mul(self.z3_ctx, &[&offset, &elem]);
327                    let ptr_plus_off = Int::add(self.z3_ctx, &[&ptr_val.z3_term, &byte_off]);
328                    let zero = Int::from_u64(self.z3_ctx, 0);
329                    let pointer_bits = self.tcx.data_layout.pointer_size().bits();
330                    let max_value = if pointer_bits >= 64 {
331                        u64::MAX
332                    } else {
333                        (1u64 << pointer_bits) - 1
334                    };
335                    let max = Int::from_u64(self.z3_ctx, max_value);
336                    let aligned = ptr_plus_off.rem(&align_val.z3_term)._eq(&zero);
337                    let nonnegative = offset.ge(&zero);
338                    let bounded = offset.lt(&align_val.z3_term);
339                    let success = Bool::and(self.z3_ctx, &[&aligned, &nonnegative, &bounded]);
340                    self.path_state.constraints
341                        .assertions
342                        .push(Bool::or(self.z3_ctx, &[&offset._eq(&max), &success]));
343                }
344                let val = VmValue::new(offset, dest_ty);
345                self.set_local(dest, val);
346            }
347            effect @ (CallEffect::ReturnMin { .. }
348            | CallEffect::ReturnMax { .. }
349            | CallEffect::ReturnAdd { .. }
350            | CallEffect::ReturnMul { .. }
351            | CallEffect::ReturnBoundedArithmetic { .. }
352            | CallEffect::ReturnWithOverflow { .. }
353            | CallEffect::ReturnNonZeroIff { .. }
354            | CallEffect::ReturnLeadingZeros { .. }
355            | CallEffect::ReturnTrailingZeros { .. }) => {
356                self.apply_numeric_effect(effect, args, dest);
357            }
358            CallEffect::ReturnNullableAllocation {
359                size_arg,
360                align_arg,
361                zeroed,
362            } => {
363                if let Some(size) = args.get(*size_arg) {
364                    let align = args
365                        .get(*align_arg)
366                        .map(|value| value.z3_term.clone())
367                        .unwrap_or_else(|| Int::from_u64(self.z3_ctx, 1));
368                    let (alloc_id, base) = self.allocate_external(
369                        size.z3_term.clone(),
370                        align,
371                        Some(self.tcx.types.u8),
372                    );
373                    self.alloc_mut(alloc_id).facts.owning = Some(base.clone());
374                    self.alloc_mut(alloc_id).facts.locally_allocated = true;
375                    if *zeroed {
376                        self.content_mut(alloc_id).facts.initialized = true;
377                    }
378                    let dest_ty = self.body().local_decls[dest].ty;
379                    self.set_local(
380                        dest,
381                        VmValue {
382                            z3_term: base,
383                            ty: dest_ty,
384                            provenance: Some(Provenance {
385                                alloc_id,
386                                offset: Int::from_u64(self.z3_ctx, 0),
387                                offset_kind: None,
388                            }),
389                            facts: ValueFacts::default(),
390                            source: ValueSource::None,
391                        },
392                    );
393                }
394            }
395            CallEffect::ReturnVecFromSlice => {
396                self.ensure_local_allocation(dest);
397                let dest_ty = self.body().local_decls[dest].ty;
398                let elem_ty = crate::analysis::dataflow::call_summary::effects::vec_elem_ty(dest_ty);
399                let heap_align = elem_ty
400                    .map(|ty| self.align_sym(ty))
401                    .unwrap_or_else(|| Int::from_u64(self.z3_ctx, 1));
402                let known_len = args
403                    .first()
404                    .and_then(|v| v.provenance.as_ref())
405                    .and_then(|p| {
406                        let alloc = self.alloc(p.alloc_id);
407                        if let Some(slice_len) = alloc.slice_len().cloned() {
408                            return Some(slice_len);
409                        }
410                        let source_ty = alloc.element_ty.as_ty()?;
411                        let array_ty = match source_ty.kind() {
412                            TyKind::Adt(def, args)
413                                if type_ids::is_maybe_uninit_type(def.did()) =>
414                            {
415                                args.first()?.as_type()?
416                            }
417                            _ => source_ty,
418                        };
419                        let TyKind::Array(_, count) = array_ty.kind() else {
420                            return None;
421                        };
422                        Some(self.const_len_term(count))
423                    })
424                    .or_else(|| {
425                        let TyKind::Adt(box_def, box_args) = args.first()?.ty.kind() else {
426                            return None;
427                        };
428                        if !type_ids::is_std_box(box_def.did()) {
429                            return None;
430                        }
431                        let mut source_ty = box_args.first()?.as_type()?;
432                        if let TyKind::Adt(def, args) = source_ty.kind()
433                            && type_ids::is_maybe_uninit_type(def.did())
434                        {
435                            source_ty = args.first()?.as_type()?;
436                        }
437                        let TyKind::Array(_, count) = source_ty.kind() else {
438                            return None;
439                        };
440                        Some(self.const_len_term(count))
441                    });
442                let size = if let Some(len) = &known_len {
443                    let elem_size = elem_ty
444                        .map(|ty| self.size_sym(ty))
445                        .unwrap_or_else(|| Int::from_u64(self.z3_ctx, 1));
446                    Int::mul(self.z3_ctx, &[len, &elem_size])
447                } else {
448                    Int::from_u64(self.z3_ctx, i64::MAX as u64)
449                };
450                let (alloc_id, base) = self.allocate_external(size, heap_align, elem_ty);
451                if let Some(len) = &known_len {
452                    self.alloc_mut(alloc_id).set_slice_len(len.clone());
453                }
454                if let Some(box_alloc) = args.first().and_then(|v| v.provenance_alloc_id()) {
455                    self.copy_byte_tracking(box_alloc, 0, alloc_id);
456                }
457                if let Some(ptr_field) = self.set_external_container_result(dest, alloc_id, base, elem_ty)
458                {
459                    let len_term = known_len
460                        .clone()
461                        .unwrap_or_else(|| self.fresh_int(&format!("vec_len_{}", dest.as_usize())));
462                    self.materialize_vec_fields(dest, ptr_field, len_term.clone(), len_term);
463                }
464            }
465        }
466    }
467
468    fn simd_lane_type(&self, ty: Ty<'tcx>) -> Option<(Ty<'tcx>, usize)> {
469        let TyKind::Adt(def, args) = ty.kind() else {
470            return None;
471        };
472        if !def.repr().simd() {
473            return None;
474        }
475        let field = mir_utils::field_ty(self.tcx, def.non_enum_variant().fields.raw.first()?, args);
476        let TyKind::Array(elem, len) = field.kind() else {
477            return None;
478        };
479        let len = mir_utils::eval_array_len(self.tcx, len)? as usize;
480        Some((*elem, len))
481    }
482
483    fn set_opaque_simd_result(&mut self, dest: Local) {
484        let dest_ty = self.body().local_decls[dest].ty;
485        let Some((elem_ty, len)) = self.simd_lane_type(dest_ty) else {
486            self.set_opaque_intrinsic_result(dest);
487            return;
488        };
489        let limits = self.integer_limits(elem_ty);
490        for index in 0..len {
491            let term = self.fresh_int("simd_lane");
492            if let Some((min, max, _, _)) = &limits {
493                self.path_state.constraints.assertions.push(term.ge(min));
494                self.path_state.constraints.assertions.push(term.le(max));
495            }
496            let mut value = VmValue::new(term, elem_ty);
497            value.facts.init = true;
498            self.set_field_value(dest, vec![0, index], value);
499        }
500    }
501
502    fn copy_simd_result_from_local(&mut self, dest: Local, source: Local) -> bool {
503        let dest_ty = self.body().local_decls[dest].ty;
504        let Some((_, len)) = self.simd_lane_type(dest_ty) else {
505            return false;
506        };
507        let lanes: Option<Vec<_>> = (0..len)
508            .map(|index| self.field_value(source, &[0, index]).cloned())
509            .collect();
510        let Some(lanes) = lanes else {
511            return false;
512        };
513        for (index, value) in lanes.into_iter().enumerate() {
514            self.set_field_value(dest, vec![0, index], value);
515        }
516        true
517    }
518
519    fn set_opaque_intrinsic_result(&mut self, dest: Local) {
520        let ty = self.body().local_decls[dest].ty;
521        let term = self.fresh_int("intrinsic_result");
522        self.path_state.inline.opaque_intrinsic_terms.insert(term.clone());
523        self.set_local(dest, VmValue::new(term, ty));
524    }
525
526    fn set_external_container_result(
527        &mut self,
528        dest: Local,
529        alloc_id: AllocId,
530        base: Int<'z3>,
531        elem_ty: Option<Ty<'tcx>>,
532    ) -> Option<VmValue<'z3, 'tcx>> {
533        let dest_ty = self.body().local_decls[dest].ty;
534        let dest_alloc_id = self.path_state.current_frame.local_alloc.get(&dest).copied();
535        self.alloc_mut(alloc_id).facts.owning = Some(base.clone());
536        self.content_mut(alloc_id).facts.initialized = true;
537        self.set_local(
538            dest,
539            VmValue {
540                z3_term: base.clone(),
541                ty: dest_ty,
542                provenance: dest_alloc_id.map(|stack_id| Provenance {
543                    alloc_id: stack_id,
544                    offset: Int::from_u64(self.z3_ctx, 0),
545                    offset_kind: None,
546                }),
547                facts: ValueFacts {
548                    non_null: true,
549                    init: true,
550                    in_bounds: true,
551                    ..ValueFacts::default()
552                },
553                source: ValueSource::None,
554            },
555        );
556        let TyKind::Adt(adt_def, _) = dest_ty.kind() else {
557            return None;
558        };
559        if !type_ids::is_std_vec(adt_def.did()) {
560            return None;
561        }
562        Some(VmValue {
563            z3_term: base,
564            ty: elem_ty.unwrap_or(dest_ty),
565            provenance: Some(Provenance {
566                alloc_id,
567                offset: Int::from_u64(self.z3_ctx, 0),
568                offset_kind: None,
569            }),
570            facts: ValueFacts {
571                non_null: true,
572                init: true,
573                in_bounds: true,
574                ..ValueFacts::default()
575            },
576            source: ValueSource::None,
577        })
578    }
579}