1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
//! Call summaries for the staged verifier: backward dependency (which call
//! arguments stay relevant) and forward effect (what facts a call adds).
pub(crate) mod effects;
pub(crate) mod dependencies;
use rustc_middle::{
mir::Operand,
ty::TyCtxt,
};
use crate::helpers::mir_utils;
use crate::verify::api_classify::is_branch;
/// Dependency summary consumed by the backward visitor.
#[derive(Clone, Debug)]
pub(crate) struct CallDependencySummary {
/// If the call destination is relevant, these call arguments are relevant.
pub return_depends_on_args: Vec<usize>,
/// Arguments definitely written on every return path (the must-write
/// intersection, from `local_must_write_args`). The backward slicer keeps
/// these relevant so the write effect is applied. A conditionally-written
/// argument is *not* listed here — that is the "may-write" set, which this
/// summary does not compute.
pub must_write_args: Vec<usize>,
}
impl CallDependencySummary {
/// Conservative fallback: keep all arguments relevant.
fn fallback(arg_count: usize) -> Self {
Self {
return_depends_on_args: (0..arg_count).collect(),
must_write_args: Vec::new(),
}
}
}
/// Effect summary consumed by the forward visitor.
pub(crate) type CallEffectSummary = Vec<CallEffect>;
/// Path-local effect produced by a retained call.
#[derive(Clone, Debug)]
pub(crate) enum CallEffect {
/// The return value aliases or is a direct value flow from an argument.
ReturnAliasArg { arg: usize },
/// `select_unpredictable(cond, x, y)` returns either `x` or `y`: the result
/// is one of the two candidate values (`args[1]`/`args[2]`), non-deterministic
/// since the boolean selector (`args[0]`) is unpredictable.
SelectUnpredictable,
/// The return value is a pointer extracted from an aggregate/reference arg.
ReturnPointerFromArg { arg: usize },
/// The return value is `base + offset * stride`.
ReturnPointerAdd {
base_arg: usize,
offset_arg: usize,
stride: Option<u64>,
/// Whether the result is a *dereferenceable* pointer (its contract
/// guarantees strict in-bounds, e.g. `SliceIndex::get_unchecked`), as
/// opposed to plain `add` arithmetic whose result may be one-past-end.
dereferenceable: bool,
},
/// The return value is `base - offset * stride`.
ReturnPointerSub {
base_arg: usize,
offset_arg: usize,
stride: Option<u64>,
},
/// The return value is known to be non-zero.
ReturnNonZero,
/// The return value is known to satisfy a concrete alignment.
ReturnAligned,
/// The return value is a concrete layout/numeric constant.
ReturnConst { value: u64 },
/// The call writes one initialized element through a pointer argument.
WriteMemory { pointer_arg: usize },
/// The return value is a pointer backed by a fresh allocation of
/// `size_arg` elements × `elem_size` bytes. The base address is taken
/// from `pointer_arg`. Used for `from_raw_parts(ptr, len)`.
ReturnFreshAllocation {
pointer_arg: usize,
size_arg: usize,
elem_size: u64,
},
/// `alloc::alloc::exchange_malloc(size, align)` — a fresh allocation of
/// `size_arg` bytes, returned as `*mut u8`.
ReturnExchangeMalloc { size_arg: usize },
/// The return value is the length of an aggregate argument.
ReturnLengthOfArg { arg: usize },
/// The return value is `min(lhs_arg, rhs_arg)`, satisfying
/// `return <= lhs_arg` and `return <= rhs_arg`.
ReturnMin { lhs_arg: usize, rhs_arg: usize },
/// The return value is `max(lhs_arg, rhs_arg)`.
ReturnMax { lhs_arg: usize, rhs_arg: usize },
/// The return value is `clamp(value_arg, min_arg, max_arg)`.
ReturnClamp {
value_arg: usize,
min_arg: usize,
max_arg: usize,
},
/// The return value is the absolute value of `arg` (`ite(arg >= 0, arg, -arg)`).
ReturnAbs { arg: usize },
/// The return value is the negation of `arg` (`-arg`).
ReturnNeg { arg: usize },
/// The return value is `lhs_arg + rhs_arg`.
ReturnAdd { lhs_arg: usize, rhs_arg: usize },
/// The return value is `lhs_arg * rhs_arg`.
ReturnMul { lhs_arg: usize, rhs_arg: usize },
/// The call returns `Option<T>` whose `Some` payload is `lhs_arg + rhs_arg`
/// (models `checked_add`; the payload is non-zero whenever `lhs_arg` is).
ReturnOptionSomeAdd { lhs_arg: usize, rhs_arg: usize },
/// The call returns `Option<T>` whose `Some` payload is `lhs_arg * rhs_arg`
/// (models `checked_mul`; the payload is non-zero whenever both args are).
ReturnOptionSomeMul { lhs_arg: usize, rhs_arg: usize },
/// The return value is non-zero *iff* `arg` is non-zero (models bit-preserving
/// operations like `rotate_left`/`swap_bytes`/`count_ones`/`isqrt`, which map
/// `0` to `0` and non-zero to non-zero).
ReturnNonZeroIff { arg: usize },
/// The call returns `Option<T>` whose `Some` payload is non-zero *iff* `arg`
/// is non-zero (models `checked_pow`).
ReturnOptionSomeNonZeroIff { arg: usize },
/// The call returns `Option<T>` whose `Some` payload is unconditionally
/// non-zero (models `checked_next_power_of_two`, where the next power of
/// two is always positive regardless of the argument).
ReturnOptionSomeNonZero,
/// A specific field of the returned tuple is known to be non-zero (e.g.
/// `overflowing_abs`/`overflowing_neg` return `(result, overflow)` where
/// `result != 0`). Used to discharge a downstream `ValidNum(result != 0)`.
ReturnTupleFieldNonZero { field: usize },
/// A specific field of the returned tuple carries the length of a given
/// argument (e.g. split_at(mid) returns (left, right) where left.len() == mid).
ReturnTupleFieldLength { field: usize, from_arg: usize },
/// The return value is a pointer backed by a fresh heap allocation of
/// `size_arg` elements × `elem_size` bytes. Unlike ReturnFreshAllocation
/// this does not require a pointer argument — used for constructors like
/// `Vec::from_elem(init, count)` that allocate fresh memory.
ReturnNewAllocation { size_arg: usize, elem_size: u64 },
/// `Box::new` / `Box::new_in` / `Box::new_uninit` / `Box::new_uninit_in`
/// (and `try_` variants): allocate a fresh heap buffer of `size_of::<T>()`
/// bytes and return a `Box` whose pointer field backs it. These have MIR
/// available but carry a `match` on the allocator's `Result`, which the
/// inline heuristic rejects as a semantic branch, so a direct effect is the
/// only way the fresh allocation's provenance reaches the `NonNull`.
ReturnBoxAllocation,
/// Like ReturnNewAllocation but the length is carried by the argument
/// itself (a Box fat pointer) rather than a separate count argument.
/// Used for `into_vec` / `box_assume_init_into_vec_unsafe`.
ReturnNewAllocationFromBox,
/// Like `ReturnNewAllocation`, but the argument is the *capacity*: the
/// returned Vec starts empty (`len == 0`) with `cap == cap_arg` (models
/// `Vec::with_capacity`).
ReturnNewAllocationFromCap { cap_arg: usize, elem_size: u64 },
/// The return value is a non-zero power of two (models `Layout::align`).
ReturnPowerOfTwo,
/// The call transfers a Vec's backing allocation into a Box (e.g.
/// `Vec::into_boxed_slice`). Looks up the current heap allocation from the
/// argument's owning pointer field via its stack provenance.
ReturnBoxFromVec { arg: usize },
/// The return value is known to own initialized memory of the type pointed
/// to by the indicated argument (e.g. `Box::from_raw(p)` owns one initialized
/// `T` element reached through `p`).
OwnsInitMemory { arg: usize },
/// The call returns `Option<usize>` whose `Some` payload is a scan index
/// into the iterator argument `self_arg` (models `Iterator::position` /
/// `Iterator::find`): `Some(i)` satisfies `0 <= i < self.len()` where
/// `self` is the Iter/IterMut struct produced by `into_iter`/`iter`.
ReturnOptionSomeScanIndex { self_arg: usize },
/// The call is `Try::branch`: `Option<T>` -> `ControlFlow<Option<!>, T>`,
/// so the result's `Continue` payload (field 0) equals the input's `Some`
/// payload (field 0). Models the `?` operator's `if let Some(..) = expr?`
/// unwrap so the payload's provenance survives the branch.
ReturnBranchPayload { arg: usize },
/// The call returns the length of a nul-terminated string (models
/// `strlen`): `0 <= len < isize::MAX`, so `len + 1` (the byte length with
/// the terminator) fits in `isize::MAX` — discharging the
/// `from_raw_parts` `ValidNum(size_of(T)*(len+1) <= isize::MAX)` bound.
ReturnScanLength,
/// `ptr.align_offset(align)` returns an offset such that
/// `(ptr + offset) % align == 0` and `0 <= offset < align` (or `usize::MAX`
/// when no such offset exists). Models `*const T::align_offset` /
/// `*mut T::align_offset` by recording the alignment path-condition so
/// downstream `ptr.add(offset)` dereferences can discharge `Align`.
ReturnAlignOffset { ptr_arg: usize, align_arg: usize },
/// A local `align_to`-style wrapper (`align_to_ext`/`align_to_mut_ext`)
/// returns `(prefix, body, suffix)` where `body` is `align_of::<U>()`-aligned.
/// Models the tuple by creating three sub-slices whose lengths/offsets obey
/// `prefix.len() = offset` and `len - suffix.len() = offset + k*size_of::<U>()`,
/// and records `(ptr + offset) % align_of::<U>() == 0` so downstream
/// `ptr.add(offset - k)` dereferences can discharge `Align`.
ReturnAlignTo { receiver_arg: usize },
/// `<ManuallyDrop<T> as Deref>::deref` / `MaybeDangling::as_ref` return a
/// reference to the inner value at the *same* address (transparent
/// wrappers). The return aliases `arg` (a `&T` pointing at `arg`'s
/// pointee) and its pointee field values are the argument's field values
/// with the leading `peel` transparent field-0 hops stripped.
ReturnTransparentDeref { arg: usize, peel: usize },
/// `slice::range(range, bounds)` returns `Range { start, end }` satisfying
/// `0 <= start <= end <= bounds.end`. Models the range normalizer whose
/// `start_bound`/`end_bound` trait dispatch cannot be inlined.
ReturnRange { bounds_arg: usize },
/// `mem::replace(dest, src)` returns `*dest` (the old value), so the return
/// is the *pointee* of the reference argument, not the reference itself.
ReturnDerefArg { arg: usize },
/// The call *frees* the heap allocation behind `pointer_arg` (a `&mut`
/// reference to a `Box`/`Vec`/`String` pointee). Models `ManuallyDrop::drop`.
DropMemory { pointer_arg: usize },
/// `<[T]>::index(range)` / `::index_mut(range)` returns a sub-slice whose
/// length is the range's extent. Modelled as a sub-allocation of the array
/// so downstream `into_iter`/`next()` see the correct element count.
ReturnSliceRangeIndex,
/// `<[T]>::get(range)` / `::get_mut(range)` returns `Option<&[T]>` whose
/// `Some` payload is a sub-slice with the range's extent.
ReturnSliceRangeGet,
/// `Iter::len()` / `Iter::is_empty()` computed from the iterator's pointer
/// fields (`ptr` + `end_or_len` sharing the same allocation).
ReturnIterLen { is_len: bool },
/// `NonNull::<T>::new(ptr) -> Option<NonNull<T>>`: the safe constructor,
/// returning `Some(ptr)` when the pointer is provably non-null and an
/// unconstrained `Option` otherwise.
ReturnNonNullNew,
/// `Iter::next()` / `IterMut::next()`: return the current element pointer
/// and advance the iterator's tracked offset by one.
ReturnIterNext,
/// `Range<A>::next` / `RangeInclusive<A>::next`: return the current
/// `start` and advance it by one, carrying the `start < end` bound so a
/// downstream `InBound(arr, i)` can be discharged.
ReturnRangeNext,
/// `size_of::<T>()` / `align_of::<T>()` for a *generic* `T` (no concrete
/// layout): the result is the shared symbolic `sizeof_T` / `align_T`, bound
/// at apply time from `func`'s type argument.
ReturnLayoutSymbolic { is_size: bool },
}
/// Return dependency information for a MIR call terminator.
pub(crate) fn dependency_summary<'tcx>(
tcx: TyCtxt<'tcx>,
func: &Operand<'tcx>,
arg_count: usize,
) -> CallDependencySummary {
let callee = mir_utils::dep_callee_def_id(func);
// MIR dataflow first: works for local and cross-crate (`#[inline]`)
// callees alike, no hand-written table needed.
if let Some(callee) = callee {
if tcx.intrinsic(callee).is_some() || mir_utils::is_drop_in_place(callee) {
return CallDependencySummary::fallback(arg_count);
}
// Writes and return-dependencies are orthogonal: a callee can both
// write an argument and return a value depending on another, so compute
// both rather than clearing `return_depends_on_args` when a write exists.
let must_write_args = dependencies::local_must_write_args(tcx, callee)
.map(|args| args.into_iter().filter(|i| *i < arg_count).collect::<Vec<_>>())
.filter(|args| !args.is_empty());
let return_deps = if is_branch(Some(callee)) {
Some(vec![0])
} else {
dependencies::local_return_dependencies(tcx, callee)
.map(|args| args.into_iter().filter(|i| *i < arg_count).collect::<Vec<_>>())
};
if must_write_args.is_some() || return_deps.is_some() {
return CallDependencySummary {
return_depends_on_args: return_deps.unwrap_or_default(),
must_write_args: must_write_args.unwrap_or_default(),
};
}
}
CallDependencySummary::fallback(arg_count)
}