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

clippy_utils/mir/
mod.rs
