1 //! Dataflow analyses are built upon some interpretation of the
2 //! bitvectors attached to each basic block, represented via a
3 //! zero-sized structure.
6 use rustc
::mir
::{self, Body, Location}
;
7 use rustc_index
::bit_set
::BitSet
;
8 use rustc_index
::vec
::Idx
;
10 use super::MoveDataParamEnv
;
12 use crate::util
::elaborate_drops
::DropFlagState
;
14 use super::move_paths
::{HasMoveData, MoveData, MovePathIndex, InitIndex, InitKind}
;
15 use super::{BitDenotation, BottomValue, GenKillSet}
;
17 use super::drop_flag_effects_for_function_entry
;
18 use super::drop_flag_effects_for_location
;
19 use super::on_lookup_result_bits
;
22 mod indirect_mutation
;
25 pub use self::borrowed_locals
::*;
26 pub use self::indirect_mutation
::IndirectlyMutableLocals
;
27 pub use self::storage_liveness
::*;
29 pub(super) mod borrows
;
31 /// `MaybeInitializedPlaces` tracks all places that might be
32 /// initialized upon reaching a particular point in the control flow
35 /// For example, in code like the following, we have corresponding
36 /// dataflow information shown in the right-hand comments.
40 /// fn foo(pred: bool) { // maybe-init:
42 /// let a = S; let b = S; let c; let d; // {a, b}
54 /// c = S; // {a, b, c, d}
58 /// To determine whether a place *must* be initialized at a
59 /// particular control-flow point, one can take the set-difference
60 /// between this data and the data from `MaybeUninitializedPlaces` at the
61 /// corresponding control-flow point.
63 /// Similarly, at a given `drop` statement, the set-intersection
64 /// between this data and `MaybeUninitializedPlaces` yields the set of
65 /// places that would require a dynamic drop-flag at that statement.
66 pub struct MaybeInitializedPlaces
<'a
, 'tcx
> {
69 mdpe
: &'a MoveDataParamEnv
<'tcx
>,
72 impl<'a
, 'tcx
> MaybeInitializedPlaces
<'a
, 'tcx
> {
73 pub fn new(tcx
: TyCtxt
<'tcx
>, body
: &'a Body
<'tcx
>, mdpe
: &'a MoveDataParamEnv
<'tcx
>) -> Self {
74 MaybeInitializedPlaces { tcx, body, mdpe }
78 impl<'a
, 'tcx
> HasMoveData
<'tcx
> for MaybeInitializedPlaces
<'a
, 'tcx
> {
79 fn move_data(&self) -> &MoveData
<'tcx
> { &self.mdpe.move_data }
82 /// `MaybeUninitializedPlaces` tracks all places that might be
83 /// uninitialized upon reaching a particular point in the control flow
86 /// For example, in code like the following, we have corresponding
87 /// dataflow information shown in the right-hand comments.
91 /// fn foo(pred: bool) { // maybe-uninit:
93 /// let a = S; let b = S; let c; let d; // { c, d}
96 /// drop(a); // {a, c, d}
97 /// b = S; // {a, c, d}
100 /// drop(b); // { b, c, d}
101 /// d = S; // { b, c }
103 /// } // {a, b, c, d}
105 /// c = S; // {a, b, d}
109 /// To determine whether a place *must* be uninitialized at a
110 /// particular control-flow point, one can take the set-difference
111 /// between this data and the data from `MaybeInitializedPlaces` at the
112 /// corresponding control-flow point.
114 /// Similarly, at a given `drop` statement, the set-intersection
115 /// between this data and `MaybeInitializedPlaces` yields the set of
116 /// places that would require a dynamic drop-flag at that statement.
117 pub struct MaybeUninitializedPlaces
<'a
, 'tcx
> {
119 body
: &'a Body
<'tcx
>,
120 mdpe
: &'a MoveDataParamEnv
<'tcx
>,
123 impl<'a
, 'tcx
> MaybeUninitializedPlaces
<'a
, 'tcx
> {
124 pub fn new(tcx
: TyCtxt
<'tcx
>, body
: &'a Body
<'tcx
>, mdpe
: &'a MoveDataParamEnv
<'tcx
>) -> Self {
125 MaybeUninitializedPlaces { tcx, body, mdpe }
129 impl<'a
, 'tcx
> HasMoveData
<'tcx
> for MaybeUninitializedPlaces
<'a
, 'tcx
> {
130 fn move_data(&self) -> &MoveData
<'tcx
> { &self.mdpe.move_data }
133 /// `DefinitelyInitializedPlaces` tracks all places that are definitely
134 /// initialized upon reaching a particular point in the control flow
137 /// For example, in code like the following, we have corresponding
138 /// dataflow information shown in the right-hand comments.
142 /// fn foo(pred: bool) { // definite-init:
144 /// let a = S; let b = S; let c; let d; // {a, b }
147 /// drop(a); // { b, }
151 /// drop(b); // {a, }
160 /// To determine whether a place *may* be uninitialized at a
161 /// particular control-flow point, one can take the set-complement
164 /// Similarly, at a given `drop` statement, the set-difference between
165 /// this data and `MaybeInitializedPlaces` yields the set of places
166 /// that would require a dynamic drop-flag at that statement.
167 pub struct DefinitelyInitializedPlaces
<'a
, 'tcx
> {
169 body
: &'a Body
<'tcx
>,
170 mdpe
: &'a MoveDataParamEnv
<'tcx
>,
173 impl<'a
, 'tcx
> DefinitelyInitializedPlaces
<'a
, 'tcx
> {
174 pub fn new(tcx
: TyCtxt
<'tcx
>, body
: &'a Body
<'tcx
>, mdpe
: &'a MoveDataParamEnv
<'tcx
>) -> Self {
175 DefinitelyInitializedPlaces { tcx, body, mdpe }
179 impl<'a
, 'tcx
> HasMoveData
<'tcx
> for DefinitelyInitializedPlaces
<'a
, 'tcx
> {
180 fn move_data(&self) -> &MoveData
<'tcx
> { &self.mdpe.move_data }
183 /// `EverInitializedPlaces` tracks all places that might have ever been
184 /// initialized upon reaching a particular point in the control flow
185 /// for a function, without an intervening `Storage Dead`.
187 /// This dataflow is used to determine if an immutable local variable may
190 /// For example, in code like the following, we have corresponding
191 /// dataflow information shown in the right-hand comments.
195 /// fn foo(pred: bool) { // ever-init:
197 /// let a = S; let b = S; let c; let d; // {a, b }
200 /// drop(a); // {a, b, }
201 /// b = S; // {a, b, }
204 /// drop(b); // {a, b, }
205 /// d = S; // {a, b, d }
209 /// c = S; // {a, b, c, d }
212 pub struct EverInitializedPlaces
<'a
, 'tcx
> {
214 body
: &'a Body
<'tcx
>,
215 mdpe
: &'a MoveDataParamEnv
<'tcx
>,
218 impl<'a
, 'tcx
> EverInitializedPlaces
<'a
, 'tcx
> {
219 pub fn new(tcx
: TyCtxt
<'tcx
>, body
: &'a Body
<'tcx
>, mdpe
: &'a MoveDataParamEnv
<'tcx
>) -> Self {
220 EverInitializedPlaces { tcx, body, mdpe }
224 impl<'a
, 'tcx
> HasMoveData
<'tcx
> for EverInitializedPlaces
<'a
, 'tcx
> {
225 fn move_data(&self) -> &MoveData
<'tcx
> { &self.mdpe.move_data }
228 impl<'a
, 'tcx
> MaybeInitializedPlaces
<'a
, 'tcx
> {
229 fn update_bits(trans
: &mut GenKillSet
<MovePathIndex
>,
231 state
: DropFlagState
)
234 DropFlagState
::Absent
=> trans
.kill(path
),
235 DropFlagState
::Present
=> trans
.gen(path
),
240 impl<'a
, 'tcx
> MaybeUninitializedPlaces
<'a
, 'tcx
> {
241 fn update_bits(trans
: &mut GenKillSet
<MovePathIndex
>,
243 state
: DropFlagState
)
246 DropFlagState
::Absent
=> trans
.gen(path
),
247 DropFlagState
::Present
=> trans
.kill(path
),
252 impl<'a
, 'tcx
> DefinitelyInitializedPlaces
<'a
, 'tcx
> {
253 fn update_bits(trans
: &mut GenKillSet
<MovePathIndex
>,
255 state
: DropFlagState
)
258 DropFlagState
::Absent
=> trans
.kill(path
),
259 DropFlagState
::Present
=> trans
.gen(path
),
264 impl<'a
, 'tcx
> BitDenotation
<'tcx
> for MaybeInitializedPlaces
<'a
, 'tcx
> {
265 type Idx
= MovePathIndex
;
266 fn name() -> &'
static str { "maybe_init" }
267 fn bits_per_block(&self) -> usize {
268 self.move_data().move_paths
.len()
271 fn start_block_effect(&self, entry_set
: &mut BitSet
<MovePathIndex
>) {
272 drop_flag_effects_for_function_entry(
273 self.tcx
, self.body
, self.mdpe
,
275 assert
!(s
== DropFlagState
::Present
);
276 entry_set
.insert(path
);
280 fn statement_effect(&self,
281 trans
: &mut GenKillSet
<Self::Idx
>,
284 drop_flag_effects_for_location(
285 self.tcx
, self.body
, self.mdpe
,
287 |path
, s
| Self::update_bits(trans
, path
, s
)
291 fn terminator_effect(&self,
292 trans
: &mut GenKillSet
<Self::Idx
>,
295 drop_flag_effects_for_location(
296 self.tcx
, self.body
, self.mdpe
,
298 |path
, s
| Self::update_bits(trans
, path
, s
)
302 fn propagate_call_return(
304 in_out
: &mut BitSet
<MovePathIndex
>,
305 _call_bb
: mir
::BasicBlock
,
306 _dest_bb
: mir
::BasicBlock
,
307 dest_place
: &mir
::Place
<'tcx
>,
309 // when a call returns successfully, that means we need to set
310 // the bits for that dest_place to 1 (initialized).
311 on_lookup_result_bits(self.tcx
, self.body
, self.move_data(),
312 self.move_data().rev_lookup
.find(dest_place
.as_ref()),
313 |mpi
| { in_out.insert(mpi); }
);
317 impl<'a
, 'tcx
> BitDenotation
<'tcx
> for MaybeUninitializedPlaces
<'a
, 'tcx
> {
318 type Idx
= MovePathIndex
;
319 fn name() -> &'
static str { "maybe_uninit" }
320 fn bits_per_block(&self) -> usize {
321 self.move_data().move_paths
.len()
324 // sets on_entry bits for Arg places
325 fn start_block_effect(&self, entry_set
: &mut BitSet
<MovePathIndex
>) {
326 // set all bits to 1 (uninit) before gathering counterevidence
327 assert
!(self.bits_per_block() == entry_set
.domain_size());
328 entry_set
.insert_all();
330 drop_flag_effects_for_function_entry(
331 self.tcx
, self.body
, self.mdpe
,
333 assert
!(s
== DropFlagState
::Present
);
334 entry_set
.remove(path
);
338 fn statement_effect(&self,
339 trans
: &mut GenKillSet
<Self::Idx
>,
342 drop_flag_effects_for_location(
343 self.tcx
, self.body
, self.mdpe
,
345 |path
, s
| Self::update_bits(trans
, path
, s
)
349 fn terminator_effect(&self,
350 trans
: &mut GenKillSet
<Self::Idx
>,
353 drop_flag_effects_for_location(
354 self.tcx
, self.body
, self.mdpe
,
356 |path
, s
| Self::update_bits(trans
, path
, s
)
360 fn propagate_call_return(
362 in_out
: &mut BitSet
<MovePathIndex
>,
363 _call_bb
: mir
::BasicBlock
,
364 _dest_bb
: mir
::BasicBlock
,
365 dest_place
: &mir
::Place
<'tcx
>,
367 // when a call returns successfully, that means we need to set
368 // the bits for that dest_place to 0 (initialized).
369 on_lookup_result_bits(self.tcx
, self.body
, self.move_data(),
370 self.move_data().rev_lookup
.find(dest_place
.as_ref()),
371 |mpi
| { in_out.remove(mpi); }
);
375 impl<'a
, 'tcx
> BitDenotation
<'tcx
> for DefinitelyInitializedPlaces
<'a
, 'tcx
> {
376 type Idx
= MovePathIndex
;
377 fn name() -> &'
static str { "definite_init" }
378 fn bits_per_block(&self) -> usize {
379 self.move_data().move_paths
.len()
382 // sets on_entry bits for Arg places
383 fn start_block_effect(&self, entry_set
: &mut BitSet
<MovePathIndex
>) {
386 drop_flag_effects_for_function_entry(
387 self.tcx
, self.body
, self.mdpe
,
389 assert
!(s
== DropFlagState
::Present
);
390 entry_set
.insert(path
);
394 fn statement_effect(&self,
395 trans
: &mut GenKillSet
<Self::Idx
>,
398 drop_flag_effects_for_location(
399 self.tcx
, self.body
, self.mdpe
,
401 |path
, s
| Self::update_bits(trans
, path
, s
)
405 fn terminator_effect(&self,
406 trans
: &mut GenKillSet
<Self::Idx
>,
409 drop_flag_effects_for_location(
410 self.tcx
, self.body
, self.mdpe
,
412 |path
, s
| Self::update_bits(trans
, path
, s
)
416 fn propagate_call_return(
418 in_out
: &mut BitSet
<MovePathIndex
>,
419 _call_bb
: mir
::BasicBlock
,
420 _dest_bb
: mir
::BasicBlock
,
421 dest_place
: &mir
::Place
<'tcx
>,
423 // when a call returns successfully, that means we need to set
424 // the bits for that dest_place to 1 (initialized).
425 on_lookup_result_bits(self.tcx
, self.body
, self.move_data(),
426 self.move_data().rev_lookup
.find(dest_place
.as_ref()),
427 |mpi
| { in_out.insert(mpi); }
);
431 impl<'a
, 'tcx
> BitDenotation
<'tcx
> for EverInitializedPlaces
<'a
, 'tcx
> {
432 type Idx
= InitIndex
;
433 fn name() -> &'
static str { "ever_init" }
434 fn bits_per_block(&self) -> usize {
435 self.move_data().inits
.len()
438 fn start_block_effect(&self, entry_set
: &mut BitSet
<InitIndex
>) {
439 for arg_init
in 0..self.body
.arg_count
{
440 entry_set
.insert(InitIndex
::new(arg_init
));
444 fn statement_effect(&self,
445 trans
: &mut GenKillSet
<Self::Idx
>,
446 location
: Location
) {
447 let (_
, body
, move_data
) = (self.tcx
, self.body
, self.move_data());
448 let stmt
= &body
[location
.block
].statements
[location
.statement_index
];
449 let init_path_map
= &move_data
.init_path_map
;
450 let init_loc_map
= &move_data
.init_loc_map
;
451 let rev_lookup
= &move_data
.rev_lookup
;
453 debug
!("statement {:?} at loc {:?} initializes move_indexes {:?}",
454 stmt
, location
, &init_loc_map
[location
]);
455 trans
.gen_all(&init_loc_map
[location
]);
458 mir
::StatementKind
::StorageDead(local
) => {
459 // End inits for StorageDead, so that an immutable variable can
460 // be reinitialized on the next iteration of the loop.
461 let move_path_index
= rev_lookup
.find_local(local
);
462 debug
!("stmt {:?} at loc {:?} clears the ever initialized status of {:?}",
463 stmt
, location
, &init_path_map
[move_path_index
]);
464 trans
.kill_all(&init_path_map
[move_path_index
]);
470 fn terminator_effect(&self,
471 trans
: &mut GenKillSet
<Self::Idx
>,
474 let (body
, move_data
) = (self.body
, self.move_data());
475 let term
= body
[location
.block
].terminator();
476 let init_loc_map
= &move_data
.init_loc_map
;
477 debug
!("terminator {:?} at loc {:?} initializes move_indexes {:?}",
478 term
, location
, &init_loc_map
[location
]);
480 init_loc_map
[location
].iter().filter(|init_index
| {
481 move_data
.inits
[**init_index
].kind
!= InitKind
::NonPanicPathOnly
486 fn propagate_call_return(
488 in_out
: &mut BitSet
<InitIndex
>,
489 call_bb
: mir
::BasicBlock
,
490 _dest_bb
: mir
::BasicBlock
,
491 _dest_place
: &mir
::Place
<'tcx
>,
493 let move_data
= self.move_data();
494 let bits_per_block
= self.bits_per_block();
495 let init_loc_map
= &move_data
.init_loc_map
;
497 let call_loc
= Location
{
499 statement_index
: self.body
[call_bb
].statements
.len(),
501 for init_index
in &init_loc_map
[call_loc
] {
502 assert
!(init_index
.index() < bits_per_block
);
503 in_out
.insert(*init_index
);
508 impl<'a
, 'tcx
> BottomValue
for MaybeInitializedPlaces
<'a
, 'tcx
> {
509 /// bottom = uninitialized
510 const BOTTOM_VALUE
: bool
= false;
513 impl<'a
, 'tcx
> BottomValue
for MaybeUninitializedPlaces
<'a
, 'tcx
> {
514 /// bottom = initialized (start_block_effect counters this at outset)
515 const BOTTOM_VALUE
: bool
= false;
518 impl<'a
, 'tcx
> BottomValue
for DefinitelyInitializedPlaces
<'a
, 'tcx
> {
519 /// bottom = initialized (start_block_effect counters this at outset)
520 const BOTTOM_VALUE
: bool
= true;
523 impl<'a
, 'tcx
> BottomValue
for EverInitializedPlaces
<'a
, 'tcx
> {
524 /// bottom = no initialized variables by default
525 const BOTTOM_VALUE
: bool
= false;