1use rustc_middle::{
2 mir::{BinOp, Local, Operand, UnOp},
3 ty::{Ty, TyKind},
4};
5use z3::ast::{Ast, Bool, Int};
6
7use crate::util::mir_utils;
8
9use super::state::{OffsetKind, Provenance, ValueFacts, ValueSource, VmExecutor, VmValue};
10
11impl<'z3, 'tcx> VmExecutor<'z3, 'tcx> {
12 pub(crate) fn inject_layout_constraints(
14 &mut self,
15 operand: &Operand<'tcx>,
16 val: &VmValue<'z3, 'tcx>,
17 ) {
18 if let Operand::Constant(constant) = operand {
19 let text = format!("{:?}", constant.const_);
20 if mir_utils::const_int_from_debug(&text).is_none() {
21 let is_align_or_size = text.starts_with("AlignOf(") || text.starts_with("SizeOf(");
22 if is_align_or_size {
23 let one = Int::from_u64(self.z3_ctx, 1);
24 self.path_state.constraints.assertions.push(val.z3_term.ge(&one));
25 }
26 }
27 }
28 }
29
30 pub(crate) fn try_emit_gcd_divisibility(
34 &mut self,
35 operand: &Operand<'tcx>,
36 val: &VmValue<'z3, 'tcx>,
37 ) {
38 let Operand::Constant(constant) = operand else {
39 return;
40 };
41 let rustc_middle::mir::Const::Unevaluated(uneval, _) = constant.const_ else {
42 return;
43 };
44 let def_name = self.tcx.def_path_str(uneval.def);
45 if !def_name.contains("align_to_offsets::{constant")
46 || !mir_utils::ctfe_mir_available(self.tcx, uneval.def)
47 {
48 return;
49 }
50 let body = self.tcx.mir_for_ctfe(uneval.def);
51 let calls_gcd = body.basic_blocks.iter().any(|bb| {
52 if let rustc_middle::mir::TerminatorKind::Call { func, .. } = &bb.terminator().kind
53 && let Some(did) = mir_utils::dep_callee_def_id(func)
54 {
55 return crate::def_ids::other_api::is_gcd(self.tcx, did);
56 }
57 false
58 });
59 if !calls_gcd || uneval.args.len() < 2 {
60 return;
61 }
62 let a = self.size_sym(uneval.args.type_at(0));
63 let b = self.size_sym(uneval.args.type_at(1));
64 let g = &val.z3_term;
65 let zero = Int::from_u64(self.z3_ctx, 0);
66 self.path_state.constraints.assertions.push(a.rem(g)._eq(&zero));
67 self.path_state.constraints.assertions.push(b.rem(g)._eq(&zero));
68 let a_div_g = a.div(g);
71 let b_div_g = b.div(g);
72 let lhs = Int::mul(self.z3_ctx, &[&a_div_g, &b]);
73 let rhs = Int::mul(self.z3_ctx, &[&b_div_g, &a]);
74 self.path_state.constraints.assertions.push(lhs._eq(&rhs));
75 }
76
77 pub(crate) fn non_trivial_align(align: Int<'z3>) -> Option<Int<'z3>> {
80 (align.simplify().as_u64() != Some(1)).then_some(align)
81 }
82
83 pub(crate) fn alloc_align_of(&self, val: &VmValue<'z3, 'tcx>) -> Option<Int<'z3>> {
85 val.provenance
86 .as_ref()
87 .map(|p| self.alloc(p.alloc_id).align.clone())
88 .and_then(Self::non_trivial_align)
89 }
90
91 pub(crate) fn emit_div_rem_axioms(
100 &mut self,
101 op: BinOp,
102 term: &Int<'z3>,
103 lhs: &Int<'z3>,
104 rhs: &Int<'z3>,
105 ) {
106 let quot = if matches!(op, BinOp::Div) {
107 term
108 } else {
109 &lhs.div(rhs)
110 };
111 let rem = lhs.rem(rhs);
112 let mul_term = Int::mul(self.z3_ctx, &[quot, rhs]);
113 let sum_term = Int::add(self.z3_ctx, &[&mul_term, &rem]);
114 self.path_state.constraints.assertions.push(lhs._eq(&sum_term));
115 let zero = Int::from_u64(self.z3_ctx, 0);
116 self.path_state.constraints.assertions.push(rem.ge(&zero));
117 if rhs.as_u64().is_none_or(|r| r >= 1) {
118 self.path_state.constraints.assertions.push(rem.lt(rhs));
119 }
120 self.path_state.constraints.assertions.push(rem.le(lhs));
121 self.path_state.constraints.assertions.push(quot.ge(&zero));
122 self.path_state.constraints.assertions.push(mul_term.le(lhs));
124 if rhs.as_u64().is_some_and(|r| r >= 2) {
125 let one = Int::from_u64(self.z3_ctx, 1);
126 let qp1 = Int::add(self.z3_ctx, &[quot, &one]);
127 self.path_state.constraints
128 .assertions
129 .push(lhs.ge(&one).implies(&qp1.le(lhs)));
130 } else {
131 if rhs.as_u64().is_some_and(|r| r >= 1) {
132 self.path_state.constraints.assertions.push(quot.le(lhs));
133 }
134 }
135 }
136
137 fn bool_as_int(&self, cond: &Bool<'z3>) -> Int<'z3> {
138 cond.ite(
139 &Int::from_u64(self.z3_ctx, 1),
140 &Int::from_u64(self.z3_ctx, 0),
141 )
142 }
143
144 fn negate(&self, val: &Int<'z3>) -> Int<'z3> {
145 let zero = Int::from_u64(self.z3_ctx, 0);
146 Int::sub(self.z3_ctx, &[&zero, val])
147 }
148
149 pub(crate) fn eval_binary_op(&mut self, op: BinOp, lhs: &Int<'z3>, rhs: &Int<'z3>) -> Int<'z3> {
150 match op {
151 BinOp::Add | BinOp::AddWithOverflow | BinOp::AddUnchecked => {
152 Int::add(self.z3_ctx, &[lhs, rhs])
153 }
154 BinOp::Sub | BinOp::SubWithOverflow | BinOp::SubUnchecked => {
155 if lhs.as_u64() == Some(0) {
159 -rhs.clone()
160 } else {
161 Int::sub(self.z3_ctx, &[lhs, rhs])
162 }
163 }
164 BinOp::Mul | BinOp::MulWithOverflow | BinOp::MulUnchecked => {
165 if let Some((div_lhs, div_rhs)) = self.path_state.constraints.term_caches.div_roots.get(lhs)
172 && let Some(us_dividend) = self.path_state.constraints.term_caches.exact_div_roots.get(rhs)
173 && let Some(ts_dividend) =
174 self.path_state.constraints.term_caches.exact_div_roots.get(div_rhs)
175 {
176 let us_len = self.fresh_int("us_len");
177 self.path_state.constraints
178 .assertions
179 .push(us_len._eq(&Int::mul(self.z3_ctx, &[lhs, rhs])));
180 let byte_len = Int::mul(self.z3_ctx, &[&us_len, ts_dividend]);
181 let byte_bound = Int::mul(self.z3_ctx, &[div_lhs, us_dividend]);
182 self.path_state.constraints.assertions.push(byte_len.le(&byte_bound));
183 return us_len;
184 }
185 Int::mul(self.z3_ctx, &[lhs, rhs])
186 }
187 BinOp::Div => {
188 let zero = Int::from_u64(self.z3_ctx, 0);
198 let exact = self.path_state
199 .constraints
200 .assertions
201 .iter()
202 .any(|c| *c == lhs.rem(rhs)._eq(&zero));
203 if exact {
204 let q = self.fresh_int("exact_div");
205 self.path_state.constraints
206 .term_caches
207 .exact_div_roots
208 .insert(q.clone(), lhs.clone());
209 q
210 } else {
211 let q = self.fresh_int("div");
217 self.path_state.constraints
218 .term_caches
219 .div_roots
220 .insert(q.clone(), (lhs.clone(), rhs.clone()));
221 q
222 }
223 }
224 BinOp::Rem => lhs.rem(rhs),
225 BinOp::Eq => self.bool_as_int(&lhs._eq(rhs)),
226 BinOp::Ne => self.bool_as_int(&lhs._eq(rhs).not()),
227 BinOp::Lt => self.bool_as_int(&lhs.lt(rhs)),
228 BinOp::Le => self.bool_as_int(&lhs.le(rhs)),
229 BinOp::Gt => self.bool_as_int(&lhs.gt(rhs)),
230 BinOp::Ge => self.bool_as_int(&lhs.ge(rhs)),
231 BinOp::Offset => Int::add(self.z3_ctx, &[lhs, rhs]),
232 BinOp::BitAnd => {
233 let left = lhs.simplify();
234 let right = rhs.simplify();
235 let all_bits = Int::from_i64(self.z3_ctx, -1);
236 if left == all_bits {
237 return rhs.clone();
238 }
239 if right == all_bits {
240 return lhs.clone();
241 }
242 if let (Some(left), Some(right)) = (left.as_u64(), right.as_u64()) {
243 return Int::from_u64(self.z3_ctx, left & right);
244 }
245 let result = self.fresh_int("binop");
246 if let Some(mask) = rhs.simplify().as_u64() {
247 let zero = Int::from_u64(self.z3_ctx, 0);
248 if mask == 0 {
249 self.path_state.constraints.assertions.push(result._eq(&zero));
250 } else if mask.trailing_zeros() > 0 {
251 let divisor = Int::from_u64(self.z3_ctx, 1_u64 << mask.trailing_zeros());
253 self.path_state.constraints.assertions.push(result.rem(&divisor)._eq(&zero));
254 }
255 }
256 let zero = Int::from_u64(self.z3_ctx, 0);
260 self.path_state.constraints.assertions.push(
261 lhs.ge(&zero)
262 .implies(&Bool::and(self.z3_ctx, &[&result.ge(&zero), &result.le(lhs)])),
263 );
264 if rhs.simplify().as_u64().is_some() {
270 self.path_state.constraints.assertions.push(result.ge(&zero));
271 self.path_state.constraints.assertions.push(result.le(rhs));
272 }
273 if self.path_state.constraints.term_caches.not_mask_terms.contains(rhs) {
274 let zero = Int::from_u64(self.z3_ctx, 0);
279 let align = Int::sub(self.z3_ctx, &[&zero, rhs]);
280 self.path_state.constraints
281 .assertions
282 .push(result.rem(&align)._eq(&zero));
283 let one = Int::from_u64(self.z3_ctx, 1);
284 let addr = Int::add(self.z3_ctx, &[lhs, rhs, &one]);
285 self.path_state.constraints.assertions.push(result.ge(&addr));
286 }
287 result
288 }
289 BinOp::BitOr => {
290 let result = self.fresh_int("binop");
291 let zero = Int::from_u64(self.z3_ctx, 0);
292 self.path_state.constraints
298 .assertions
299 .push(lhs._eq(&zero).not().implies(&result._eq(&zero).not()));
300 self.path_state.constraints
301 .assertions
302 .push(rhs._eq(&zero).not().implies(&result._eq(&zero).not()));
303 result
304 }
305 _ => self.fresh_int("binop"),
306 }
307 }
308
309 pub(crate) fn eval_unary_op(&mut self, op: UnOp, val: &Int<'z3>, is_bool: bool) -> Int<'z3> {
310 match op {
311 UnOp::Not => {
312 if is_bool {
313 let zero = Int::from_u64(self.z3_ctx, 0);
314 let one = Int::from_u64(self.z3_ctx, 1);
315 val._eq(&zero).ite(&one, &zero)
316 } else {
317 let one = Int::from_u64(self.z3_ctx, 1);
318 let result = Int::sub(self.z3_ctx, &[&self.negate(val), &one]);
319 self.path_state.constraints
320 .term_caches
321 .not_mask_terms
322 .insert(result.clone());
323 result
324 }
325 }
326 UnOp::Neg => self.negate(val),
327 UnOp::PtrMetadata => self.fresh_int("ptr_metadata"),
328 }
329 }
330
331 pub(crate) fn integer_limits(
332 &self,
333 ty: Ty<'tcx>,
334 ) -> Option<(Int<'z3>, Int<'z3>, Int<'z3>, bool)> {
335 let signed = match ty.kind() {
336 TyKind::Int(_) => true,
337 TyKind::Uint(_) => false,
338 _ => return None,
339 };
340 let (_, bytes) = mir_utils::type_layout(self.tcx, self.path_state.current_frame.current_def_id, ty)?;
341 let bits = bytes.checked_mul(8)?;
342 if bits == 0 || bits > 128 {
343 return None;
344 }
345 let unsigned_max = if bits == 128 {
346 u128::MAX
347 } else {
348 (1u128 << bits) - 1
349 };
350 let modulus = Int::add(
351 self.z3_ctx,
352 &[
353 &Int::from_str(self.z3_ctx, &unsigned_max.to_string())?,
354 &Int::from_u64(self.z3_ctx, 1),
355 ],
356 );
357 let (min, max) = if signed {
358 let signed_max = if bits == 128 {
359 i128::MAX
360 } else {
361 (1i128 << (bits - 1)) - 1
362 };
363 let signed_min = if bits == 128 {
364 i128::MIN
365 } else {
366 -(1i128 << (bits - 1))
367 };
368 (signed_min.to_string(), signed_max.to_string())
369 } else {
370 ("0".to_string(), unsigned_max.to_string())
371 };
372 Some((
373 Int::from_str(self.z3_ctx, &min)?,
374 Int::from_str(self.z3_ctx, &max)?,
375 modulus,
376 signed,
377 ))
378 }
379
380 pub(crate) fn wrap_integer_term(&self, ty: Ty<'tcx>, raw: &Int<'z3>) -> Int<'z3> {
381 let Some((min, max, modulus, signed)) = self.integer_limits(ty) else {
382 return raw.clone();
383 };
384 if self.path_implies(&raw.ge(&min)) && self.path_implies(&raw.le(&max)) {
385 return raw.clone();
386 }
387 let wrapped = raw.modulo(&modulus);
388 if signed {
389 wrapped
390 .gt(&max)
391 .ite(&Int::sub(self.z3_ctx, &[&wrapped, &modulus]), &wrapped)
392 } else {
393 wrapped
394 }
395 }
396
397 fn compute_pointer_add_align(
403 &self,
404 base: &VmValue<'z3, 'tcx>,
405 stride_bytes: u64,
406 ) -> Option<Int<'z3>> {
407 let base_align = base.facts.align_n.as_ref()?;
408 let n = base_align.simplify().as_u64()?;
414 if stride_bytes > 0 && stride_bytes.is_multiple_of(n) {
415 return Some(base_align.clone());
416 }
417 None
418 }
419
420 fn pointer_stride_term(
423 &mut self,
424 dest: Local,
425 base: &VmValue<'z3, 'tcx>,
426 stride: Option<u64>,
427 ) -> Int<'z3> {
428 match stride {
429 Some(s) => Int::from_u64(self.z3_ctx, s),
430 None => {
431 let dest_ty = self.body().local_decls[dest].ty;
432 let dest_pointee = mir_utils::pointee_ty(dest_ty).unwrap_or(dest_ty);
433 let base_pointee = mir_utils::pointee_ty(base.ty).unwrap_or(base.ty);
434 let generic_pointer = matches!(
438 (base_pointee.kind(), dest_pointee.kind()),
439 (TyKind::Param(_), TyKind::Param(_))
440 );
441 let pointee = match base_pointee.kind() {
442 TyKind::Array(element, _) | TyKind::Slice(element) => *element,
443 TyKind::Str => return Int::from_u64(self.z3_ctx, 1),
444 _ if generic_pointer => base_pointee,
445 _ => dest_pointee,
446 };
447 self.size_sym(pointee)
448 }
449 }
450 }
451
452 pub(crate) fn apply_pointer_add(
456 &mut self,
457 dest: Local,
458 base: &VmValue<'z3, 'tcx>,
459 offset: &VmValue<'z3, 'tcx>,
460 stride: Option<u64>,
461 dereferenceable: bool,
462 ) {
463 let (offset_term, subtract) = if offset.z3_term.num_children() == 1
470 && let Some(positive) = offset.z3_term.nth_child(0).and_then(|c| c.as_int())
471 {
472 (positive, true)
473 } else {
474 (offset.z3_term.clone(), false)
475 };
476 let stride_term = self.pointer_stride_term(dest, base, stride);
477 let adjusted_offset = if stride == Some(1) {
478 offset_term.clone()
479 } else {
480 Int::mul(self.z3_ctx, &[&offset_term, &stride_term])
481 };
482 let combine = |l: &Int<'z3>, r: &Int<'z3>| {
483 if subtract {
484 Int::sub(self.z3_ctx, &[l, r])
485 } else {
486 Int::add(self.z3_ctx, &[l, r])
487 }
488 };
489 let new_term = combine(&base.z3_term, &adjusted_offset);
490 let is_field_offset = offset.is_field_offset()
491 && base
492 .provenance
493 .as_ref()
494 .is_some_and(|p| p.offset.as_u64() == Some(0));
495 let element_offset = if stride == Some(1) {
496 None
497 } else {
498 match base.provenance.as_ref().and_then(|p| match &p.offset_kind {
499 Some(OffsetKind::Element { index, stride })
500 if stride.simplify() == stride_term.simplify() =>
501 {
502 Some(index.clone())
503 }
504 _ => None,
505 }) {
506 Some(e) => Some(combine(&e, &offset_term)),
507 None if base
508 .provenance
509 .as_ref()
510 .is_some_and(|p| p.offset.as_u64() == Some(0)) =>
511 {
512 Some(if subtract {
513 -offset_term.clone()
514 } else {
515 offset_term.clone()
516 })
517 }
518 None => None,
519 }
520 };
521 let offset_kind = if is_field_offset {
522 Some(OffsetKind::Field)
523 } else if let Some(e) = element_offset {
524 Some(OffsetKind::Element {
525 index: e,
526 stride: stride_term.clone(),
527 })
528 } else {
529 Some(OffsetKind::Byte)
530 };
531 let adjusted_provenance = base.provenance.as_ref().map(|prov| Provenance {
532 alloc_id: prov.alloc_id,
533 offset: combine(&prov.offset, &adjusted_offset),
534 offset_kind,
535 });
536 let align_n = match stride {
537 Some(s) => self.compute_pointer_add_align(base, s),
538 None => base.facts.align_n.clone(),
539 };
540 let val = VmValue {
541 z3_term: new_term,
542 ty: self.body().local_decls[dest].ty,
543 provenance: adjusted_provenance,
544 facts: ValueFacts {
545 non_null: base.facts.non_null,
546 dangling: base.facts.dangling,
547 in_bounds: dereferenceable,
548 align_n,
549 init: base.facts.init,
550 ownership_transfer: base.facts.ownership_transfer,
551 },
552 source: ValueSource::None,
553 };
554 self.set_local(dest, val);
555 }
556}