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}