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
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
//! We denote as "SSA" the set of locals that verify the following properties:
//! 1/ They are only assigned-to once, either as a function parameter, or in an assign statement;
//! 2/ This single assignment dominates all uses;
//!
//! As a consequence of rule 2, we consider that borrowed locals are not SSA, even if they are
//! `Freeze`, as we do not track that the assignment dominates all uses of the borrow.

use either::Either;
use rustc_data_structures::graph::dominators::Dominators;
use rustc_index::bit_set::BitSet;
use rustc_index::{IndexSlice, IndexVec};
use rustc_middle::middle::resolve_bound_vars::Set1;
use rustc_middle::mir::visit::*;
use rustc_middle::mir::*;

pub struct SsaLocals {
    /// Assignments to each local. This defines whether the local is SSA.
    assignments: IndexVec<Local, Set1<LocationExtended>>,
    /// We visit the body in reverse postorder, to ensure each local is assigned before it is used.
    /// We remember the order in which we saw the assignments to compute the SSA values in a single
    /// pass.
    assignment_order: Vec<Local>,
    /// Copy equivalence classes between locals. See `copy_classes` for documentation.
    copy_classes: IndexVec<Local, Local>,
    /// Number of "direct" uses of each local, ie. uses that are not dereferences.
    /// We ignore non-uses (Storage statements, debuginfo).
    direct_uses: IndexVec<Local, u32>,
}

/// We often encounter MIR bodies with 1 or 2 basic blocks. In those cases, it's unnecessary to
/// actually compute dominators, we can just compare block indices because bb0 is always the first
/// block, and in any body all other blocks are always dominated by bb0.
struct SmallDominators<'a> {
    inner: Option<&'a Dominators<BasicBlock>>,
}

impl SmallDominators<'_> {
    fn dominates(&self, first: Location, second: Location) -> bool {
        if first.block == second.block {
            first.statement_index <= second.statement_index
        } else if let Some(inner) = &self.inner {
            inner.dominates(first.block, second.block)
        } else {
            first.block < second.block
        }
    }

    fn check_dominates(&mut self, set: &mut Set1<LocationExtended>, loc: Location) {
        let assign_dominates = match *set {
            Set1::Empty | Set1::Many => false,
            Set1::One(LocationExtended::Arg) => true,
            Set1::One(LocationExtended::Plain(assign)) => {
                self.dominates(assign.successor_within_block(), loc)
            }
        };
        // We are visiting a use that is not dominated by an assignment.
        // Either there is a cycle involved, or we are reading for uninitialized local.
        // Bail out.
        if !assign_dominates {
            *set = Set1::Many;
        }
    }
}

impl SsaLocals {
    pub fn new<'tcx>(body: &Body<'tcx>) -> SsaLocals {
        let assignment_order = Vec::with_capacity(body.local_decls.len());

        let assignments = IndexVec::from_elem(Set1::Empty, &body.local_decls);
        let dominators =
            if body.basic_blocks.len() > 2 { Some(body.basic_blocks.dominators()) } else { None };
        let dominators = SmallDominators { inner: dominators };

        let direct_uses = IndexVec::from_elem(0, &body.local_decls);
        let mut visitor = SsaVisitor { assignments, assignment_order, dominators, direct_uses };

        for local in body.args_iter() {
            visitor.assignments[local] = Set1::One(LocationExtended::Arg);
        }

        // For SSA assignments, a RPO visit will see the assignment before it sees any use.
        // We only visit reachable nodes: computing `dominates` on an unreachable node ICEs.
        for (bb, data) in traversal::reverse_postorder(body) {
            visitor.visit_basic_block_data(bb, data);
        }

        for var_debug_info in &body.var_debug_info {
            visitor.visit_var_debug_info(var_debug_info);
        }

        debug!(?visitor.assignments);
        debug!(?visitor.direct_uses);

        visitor
            .assignment_order
            .retain(|&local| matches!(visitor.assignments[local], Set1::One(_)));
        debug!(?visitor.assignment_order);

        let mut ssa = SsaLocals {
            assignments: visitor.assignments,
            assignment_order: visitor.assignment_order,
            direct_uses: visitor.direct_uses,
            // This is filled by `compute_copy_classes`.
            copy_classes: IndexVec::default(),
        };
        compute_copy_classes(&mut ssa, body);
        ssa
    }

    pub fn num_locals(&self) -> usize {
        self.assignments.len()
    }

    pub fn locals(&self) -> impl Iterator<Item = Local> {
        self.assignments.indices()
    }

    pub fn is_ssa(&self, local: Local) -> bool {
        matches!(self.assignments[local], Set1::One(_))
    }

    /// Return the number of uses if a local that are not "Deref".
    pub fn num_direct_uses(&self, local: Local) -> u32 {
        self.direct_uses[local]
    }

    pub fn assignment_dominates(
        &self,
        dominators: &Dominators<BasicBlock>,
        local: Local,
        location: Location,
    ) -> bool {
        match self.assignments[local] {
            Set1::One(LocationExtended::Arg) => true,
            Set1::One(LocationExtended::Plain(ass)) => {
                if ass.block == location.block {
                    ass.statement_index < location.statement_index
                } else {
                    dominators.dominates(ass.block, location.block)
                }
            }
            _ => false,
        }
    }

    pub fn assignments<'a, 'tcx>(
        &'a self,
        body: &'a Body<'tcx>,
    ) -> impl Iterator<Item = (Local, &'a Rvalue<'tcx>, Location)> + 'a {
        self.assignment_order.iter().filter_map(|&local| {
            if let Set1::One(LocationExtended::Plain(loc)) = self.assignments[local] {
                // `loc` must point to a direct assignment to `local`.
                let Either::Left(stmt) = body.stmt_at(loc) else { bug!() };
                let Some((target, rvalue)) = stmt.kind.as_assign() else { bug!() };
                assert_eq!(target.as_local(), Some(local));
                Some((local, rvalue, loc))
            } else {
                None
            }
        })
    }

    pub fn for_each_assignment_mut<'tcx>(
        &self,
        basic_blocks: &mut BasicBlocks<'tcx>,
        mut f: impl FnMut(Local, &mut Rvalue<'tcx>, Location),
    ) {
        for &local in &self.assignment_order {
            if let Set1::One(LocationExtended::Plain(loc)) = self.assignments[local] {
                // `loc` must point to a direct assignment to `local`.
                let bbs = basic_blocks.as_mut_preserves_cfg();
                let bb = &mut bbs[loc.block];
                let stmt = &mut bb.statements[loc.statement_index];
                let StatementKind::Assign(box (target, ref mut rvalue)) = stmt.kind else { bug!() };
                assert_eq!(target.as_local(), Some(local));
                f(local, rvalue, loc)
            }
        }
    }

    /// Compute the equivalence classes for locals, based on copy statements.
    ///
    /// The returned vector maps each local to the one it copies. In the following case:
    ///   _a = &mut _0
    ///   _b = move? _a
    ///   _c = move? _a
    ///   _d = move? _c
    /// We return the mapping
    ///   _a => _a // not a copy so, represented by itself
    ///   _b => _a
    ///   _c => _a
    ///   _d => _a // transitively through _c
    ///
    /// Exception: we do not see through the return place, as it cannot be substituted.
    pub fn copy_classes(&self) -> &IndexSlice<Local, Local> {
        &self.copy_classes
    }

    /// Make a property uniform on a copy equivalence class by removing elements.
    pub fn meet_copy_equivalence(&self, property: &mut BitSet<Local>) {
        // Consolidate to have a local iff all its copies are.
        //
        // `copy_classes` defines equivalence classes between locals. The `local`s that recursively
        // move/copy the same local all have the same `head`.
        for (local, &head) in self.copy_classes.iter_enumerated() {
            // If any copy does not have `property`, then the head is not.
            if !property.contains(local) {
                property.remove(head);
            }
        }
        for (local, &head) in self.copy_classes.iter_enumerated() {
            // If any copy does not have `property`, then the head doesn't either,
            // then no copy has `property`.
            if !property.contains(head) {
                property.remove(local);
            }
        }

        // Verify that we correctly computed equivalence classes.
        #[cfg(debug_assertions)]
        for (local, &head) in self.copy_classes.iter_enumerated() {
            assert_eq!(property.contains(local), property.contains(head));
        }
    }
}

#[derive(Copy, Clone, Debug, PartialEq, Eq)]
enum LocationExtended {
    Plain(Location),
    Arg,
}

struct SsaVisitor<'a> {
    dominators: SmallDominators<'a>,
    assignments: IndexVec<Local, Set1<LocationExtended>>,
    assignment_order: Vec<Local>,
    direct_uses: IndexVec<Local, u32>,
}

impl<'tcx> Visitor<'tcx> for SsaVisitor<'_> {
    fn visit_local(&mut self, local: Local, ctxt: PlaceContext, loc: Location) {
        match ctxt {
            PlaceContext::MutatingUse(MutatingUseContext::Projection)
            | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => bug!(),
            // Anything can happen with raw pointers, so remove them.
            // We do not verify that all uses of the borrow dominate the assignment to `local`,
            // so we have to remove them too.
            PlaceContext::NonMutatingUse(
                NonMutatingUseContext::SharedBorrow
                | NonMutatingUseContext::ShallowBorrow
                | NonMutatingUseContext::AddressOf,
            )
            | PlaceContext::MutatingUse(_) => {
                self.assignments[local] = Set1::Many;
            }
            PlaceContext::NonMutatingUse(_) => {
                self.dominators.check_dominates(&mut self.assignments[local], loc);
                self.direct_uses[local] += 1;
            }
            PlaceContext::NonUse(_) => {}
        }
    }

    fn visit_place(&mut self, place: &Place<'tcx>, ctxt: PlaceContext, loc: Location) {
        if place.projection.first() == Some(&PlaceElem::Deref) {
            // Do not do anything for storage statements and debuginfo.
            if ctxt.is_use() {
                // Only change the context if it is a real use, not a "use" in debuginfo.
                let new_ctxt = PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy);

                self.visit_projection(place.as_ref(), new_ctxt, loc);
                self.dominators.check_dominates(&mut self.assignments[place.local], loc);
            }
            return;
        } else {
            self.visit_projection(place.as_ref(), ctxt, loc);
            self.visit_local(place.local, ctxt, loc);
        }
    }

    fn visit_assign(&mut self, place: &Place<'tcx>, rvalue: &Rvalue<'tcx>, loc: Location) {
        if let Some(local) = place.as_local() {
            self.assignments[local].insert(LocationExtended::Plain(loc));
            if let Set1::One(_) = self.assignments[local] {
                // Only record if SSA-like, to avoid growing the vector needlessly.
                self.assignment_order.push(local);
            }
        } else {
            self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), loc);
        }
        self.visit_rvalue(rvalue, loc);
    }
}

#[instrument(level = "trace", skip(ssa, body))]
fn compute_copy_classes(ssa: &mut SsaLocals, body: &Body<'_>) {
    let mut direct_uses = std::mem::take(&mut ssa.direct_uses);
    let mut copies = IndexVec::from_fn_n(|l| l, body.local_decls.len());

    for (local, rvalue, _) in ssa.assignments(body) {
        let (Rvalue::Use(Operand::Copy(place) | Operand::Move(place))
        | Rvalue::CopyForDeref(place)) = rvalue
        else {
            continue;
        };

        let Some(rhs) = place.as_local() else { continue };
        let local_ty = body.local_decls()[local].ty;
        let rhs_ty = body.local_decls()[rhs].ty;
        if local_ty != rhs_ty {
            // FIXME(#112651): This can be removed afterwards.
            trace!("skipped `{local:?} = {rhs:?}` due to subtyping: {local_ty} != {rhs_ty}");
            continue;
        }

        if !ssa.is_ssa(rhs) {
            continue;
        }

        // We visit in `assignment_order`, ie. reverse post-order, so `rhs` has been
        // visited before `local`, and we just have to copy the representing local.
        let head = copies[rhs];

        if local == RETURN_PLACE {
            // `_0` is special, we cannot rename it. Instead, rename the class of `rhs` to
            // `RETURN_PLACE`. This is only possible if the class head is a temporary, not an
            // argument.
            if body.local_kind(head) != LocalKind::Temp {
                continue;
            }
            for h in copies.iter_mut() {
                if *h == head {
                    *h = RETURN_PLACE;
                }
            }
        } else {
            copies[local] = head;
        }
        direct_uses[rhs] -= 1;
    }

    debug!(?copies);
    debug!(?direct_uses);

    // Invariant: `copies` must point to the head of an equivalence class.
    #[cfg(debug_assertions)]
    for &head in copies.iter() {
        assert_eq!(copies[head], head);
    }
    debug_assert_eq!(copies[RETURN_PLACE], RETURN_PLACE);

    ssa.direct_uses = direct_uses;
    ssa.copy_classes = copies;
}

#[derive(Debug)]
pub(crate) struct StorageLiveLocals {
    /// Set of "StorageLive" statements for each local.
    storage_live: IndexVec<Local, Set1<LocationExtended>>,
}

impl StorageLiveLocals {
    pub(crate) fn new(
        body: &Body<'_>,
        always_storage_live_locals: &BitSet<Local>,
    ) -> StorageLiveLocals {
        let mut storage_live = IndexVec::from_elem(Set1::Empty, &body.local_decls);
        for local in always_storage_live_locals.iter() {
            storage_live[local] = Set1::One(LocationExtended::Arg);
        }
        for (block, bbdata) in body.basic_blocks.iter_enumerated() {
            for (statement_index, statement) in bbdata.statements.iter().enumerate() {
                if let StatementKind::StorageLive(local) = statement.kind {
                    storage_live[local]
                        .insert(LocationExtended::Plain(Location { block, statement_index }));
                }
            }
        }
        debug!(?storage_live);
        StorageLiveLocals { storage_live }
    }

    #[inline]
    pub(crate) fn has_single_storage(&self, local: Local) -> bool {
        matches!(self.storage_live[local], Set1::One(_))
    }
}