clippy_utils/mir/
mod.rs

1use std::{iter, mem};
2
3use rustc_data_structures::either::Either;
4use rustc_hir::{Expr, HirId};
5use rustc_index::IndexVec;
6use rustc_index::bit_set::DenseBitSet;
7use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
8use rustc_middle::mir::{
9    BasicBlock, BasicBlockData, Body, InlineAsmOperand, Local, Location, Place, START_BLOCK, StatementKind,
10    TerminatorKind,
11};
12use rustc_middle::ty::TyCtxt;
13
14mod possible_borrower;
15pub use possible_borrower::PossibleBorrowerMap;
16
17mod possible_origin;
18
19mod transitive_relation;
20
21#[derive(Clone, Debug, Default)]
22pub struct LocalUsage {
23    /// The locations where the local is used, if any.
24    pub local_use_locs: Vec<Location>,
25    /// The locations where the local is consumed or mutated, if any.
26    pub local_consume_or_mutate_locs: Vec<Location>,
27}
28
29/// Collects usage locations (reads, consumes or mutations) for the set of the locals across blocks where their storage
30/// remains live relative to the `location` specified.
31///
32/// Returns:
33/// - `Some([LocalUsage; N])` containing usage metadata for each local in `locals`.
34/// - `None` if the analysis fails or `location` is unreachable.
35pub fn visit_local_usage<const N: usize>(
36    locals: [Local; N],
37    mir: &Body<'_>,
38    location: Location,
39) -> Option<[LocalUsage; N]> {
40    let live_on_entry = reachable_while_storage_live(&locals, mir, location)?;
41
42    let mut v = V {
43        locals: &locals,
44        location,
45        results: [const {
46            LocalUsage {
47                local_use_locs: Vec::new(),
48                local_consume_or_mutate_locs: Vec::new(),
49            }
50        }; N],
51    };
52
53    for &tbb in mir.basic_blocks.reverse_postorder() {
54        if live_on_entry[tbb] != 0 {
55            v.visit_basic_block_data(tbb, &mir.basic_blocks[tbb]);
56        }
57    }
58
59    Some(v.results)
60}
61
62/// Starting from the specified location, determines which blocks may be entered while any of the
63/// `locals` are still live.
64///
65/// Returns:
66/// - `None` if `location.block` may be re-entered while any of the locals are live.
67/// - `Some` with (for each [`BasicBlock`]) a bitset representing which of the locals are potentially live at the start
68///   of the block. Bit `i` stands for `locals[i]`. The exception is `location.block`, which is entered at `location`
69///   and therefore has every bit set.
70fn reachable_while_storage_live<const N: usize>(
71    locals: &[Local; N],
72    mir: &Body<'_>,
73    location: Location,
74) -> Option<IndexVec<BasicBlock, u8>> {
75    fn join(base: &mut u8, other: u8) -> bool {
76        let new = *base | other;
77        mem::replace(base, new) != new
78    }
79    fn enqueue(state: &mut u8) -> bool {
80        let new = *state | ENQUEUED_FLAG;
81        mem::replace(state, new) != new
82    }
83    fn dequeue(state: &mut u8) {
84        *state &= !ENQUEUED_FLAG;
85    }
86
87    const ENQUEUED_FLAG: u8 = 0b1000_0000;
88    const {
89        assert!(
90            N <= ENQUEUED_FLAG.trailing_zeros() as usize,
91            "implementation isn't well suited for handling a larger number locals nor do we have any reason to pass a larger number"
92        );
93    }
94
95    // Kills every local which is `StorageDead`-ed by a statement of `bb_data` at or after `start`.
96    let apply_deaths = |bb_data: &BasicBlockData<'_>, start: usize, mut live: u8| {
97        // `start` is past the end when `location` points at the terminator.
98        for stmt in bb_data.statements.get(start..).unwrap_or_default() {
99            if let StatementKind::StorageDead(killed) = stmt.kind
100                && let Some(slot) = locals.iter().position(|&local| local == killed)
101            {
102                live &= !(1 << slot);
103            }
104        }
105        live
106    };
107
108    // Walk forward over the successors of `location`.
109    // Each block's state packs the locals which are live on entry into the low `N` bits, plus a flag
110    // marking the block as queued.
111
112    let mut states = IndexVec::from_raw(vec![0; mir.basic_blocks.len()]);
113    let mut queue = Vec::new();
114    // Assumed to have all locals live, so fully filled
115    let init = u8::MAX >> (u8::BITS as usize - N);
116    states[location.block] = init;
117
118    // `location.block` is the only block entered part-way through, so it is walked separately.
119    // Reaching it again in the loop below means a cycle closed around `location`.
120    let bb_data = &mir.basic_blocks[location.block];
121    let result = apply_deaths(bb_data, location.statement_index + 1, init);
122    // A path is not followed past the point where every local is dead, as no statement there can
123    // refer to the values being tracked.
124    // A local declared inside a loop is therefore treated as distinct on each iteration.
125    if result != 0 {
126        for succ in bb_data.terminator().successors() {
127            if succ == location.block {
128                return None;
129            }
130            if join(&mut states[succ], result) && enqueue(&mut states[succ]) {
131                queue.push(succ);
132            }
133        }
134    }
135
136    while let Some(bb) = queue.pop() {
137        dequeue(&mut states[bb]);
138        let bb_data = &mir.basic_blocks[bb];
139        let result = apply_deaths(bb_data, 0, states[bb]);
140        if result != 0 {
141            for succ in bb_data.terminator().successors() {
142                if succ == location.block {
143                    return None;
144                }
145                if join(&mut states[succ], result) && enqueue(&mut states[succ]) {
146                    queue.push(succ);
147                }
148            }
149        }
150    }
151
152    Some(states)
153}
154
155struct V<'a, const N: usize> {
156    locals: &'a [Local; N],
157    location: Location,
158    results: [LocalUsage; N],
159}
160
161impl<'tcx, const N: usize> Visitor<'tcx> for V<'_, N> {
162    fn visit_place(&mut self, place: &Place<'tcx>, ctx: PlaceContext, loc: Location) {
163        if loc.block == self.location.block && loc.statement_index <= self.location.statement_index {
164            return;
165        }
166
167        let local = place.local;
168
169        for (self_local, result) in iter::zip(self.locals, &mut self.results) {
170            if local == *self_local {
171                if !matches!(
172                    ctx,
173                    PlaceContext::MutatingUse(MutatingUseContext::Drop) | PlaceContext::NonUse(_)
174                ) {
175                    result.local_use_locs.push(loc);
176                }
177                if matches!(
178                    ctx,
179                    PlaceContext::NonMutatingUse(NonMutatingUseContext::Move | NonMutatingUseContext::Inspect)
180                        | PlaceContext::MutatingUse(MutatingUseContext::Borrow)
181                ) {
182                    result.local_consume_or_mutate_locs.push(loc);
183                }
184            }
185        }
186    }
187}
188
189/// Checks if the block is part of a cycle
190pub fn block_in_cycle(body: &Body<'_>, block: BasicBlock) -> bool {
191    let mut seen = DenseBitSet::new_empty(body.basic_blocks.len());
192    let mut to_visit = Vec::with_capacity(body.basic_blocks.len() / 2);
193
194    seen.insert(block);
195    let mut next = block;
196    loop {
197        for succ in body.basic_blocks[next].terminator().successors() {
198            if seen.insert(succ) {
199                to_visit.push(succ);
200            } else if succ == block {
201                return true;
202            }
203        }
204
205        if let Some(x) = to_visit.pop() {
206            next = x;
207        } else {
208            return false;
209        }
210    }
211}
212
213/// Convenience wrapper around `visit_local_usage`.
214pub fn used_exactly_once(mir: &Body<'_>, local: Local) -> Option<bool> {
215    visit_local_usage(
216        [local],
217        mir,
218        Location {
219            block: START_BLOCK,
220            statement_index: 0,
221        },
222    )
223    .map(|[local_usage]| {
224        let mut locations = local_usage
225            .local_use_locs
226            .into_iter()
227            .filter(|&location| !is_local_assignment(mir, local, location));
228        if let Some(location) = locations.next() {
229            locations.next().is_none() && !block_in_cycle(mir, location.block)
230        } else {
231            false
232        }
233    })
234}
235
236/// Returns the `mir::Body` containing the node associated with `hir_id`.
237#[expect(clippy::module_name_repetitions)]
238pub fn enclosing_mir(tcx: TyCtxt<'_>, hir_id: HirId) -> Option<&Body<'_>> {
239    let body_owner_local_def_id = tcx.hir_enclosing_body_owner(hir_id);
240    if tcx.hir_body_owner_kind(body_owner_local_def_id).is_fn_or_closure() {
241        Some(tcx.optimized_mir(body_owner_local_def_id.to_def_id()))
242    } else {
243        None
244    }
245}
246
247/// Tries to determine the `Local` corresponding to `expr`, if any.
248/// This function is expensive and should be used sparingly.
249pub fn expr_local(tcx: TyCtxt<'_>, expr: &Expr<'_>) -> Option<Local> {
250    enclosing_mir(tcx, expr.hir_id).and_then(|mir| {
251        mir.local_decls.iter_enumerated().find_map(|(local, local_decl)| {
252            if local_decl.source_info.span == expr.span {
253                Some(local)
254            } else {
255                None
256            }
257        })
258    })
259}
260
261/// Returns a vector of `mir::Location` where `local` is assigned.
262pub fn local_assignments(mir: &Body<'_>, local: Local) -> Vec<Location> {
263    let mut locations = Vec::new();
264    for (block, data) in mir.basic_blocks.iter_enumerated() {
265        for statement_index in 0..=data.statements.len() {
266            let location = Location { block, statement_index };
267            if is_local_assignment(mir, local, location) {
268                locations.push(location);
269            }
270        }
271    }
272    locations
273}
274
275// `is_local_assignment` is based on `is_place_assignment`:
276// https://github.com/rust-lang/rust/blob/b7413511dc85ec01ef4b91785f86614589ac6103/compiler/rustc_middle/src/mir/visit.rs#L1350
277fn is_local_assignment(mir: &Body<'_>, local: Local, location: Location) -> bool {
278    match mir.stmt_at(location) {
279        Either::Left(statement) => {
280            if let StatementKind::Assign((place, _)) = statement.kind {
281                place.as_local() == Some(local)
282            } else {
283                false
284            }
285        },
286        Either::Right(terminator) => match &terminator.kind {
287            TerminatorKind::Call { destination, .. } => destination.as_local() == Some(local),
288            TerminatorKind::InlineAsm { operands, .. } => operands.iter().any(|operand| {
289                if let InlineAsmOperand::Out { place: Some(place), .. } = operand {
290                    place.as_local() == Some(local)
291                } else {
292                    false
293                }
294            }),
295            _ => false,
296        },
297    }
298}
299
300/// Returns the basic block that is terminated with this function call.
301pub fn function_call_basic_block(body: &Body<'_>, fun: &Expr<'_>) -> Option<BasicBlock> {
302    body.basic_blocks.iter_enumerated().find_map(|(block, data)| {
303        if let Some(terminator) = data.terminator.as_ref()
304            && let TerminatorKind::Call { fn_span, .. } = terminator.kind
305            && fn_span.lo() == fun.span.lo()
306        {
307            Some(block)
308        } else {
309            None
310        }
311    })
312}
clippy_utils/mir/mod.rs

clippy_utils/mir/
mod.rs
