1 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use rustc::ty::TyCtxt;
12 use rustc::mir::{self, Mir, Location};
13 use rustc_data_structures::bitslice::BitSlice; // adds set_bit/get_bit to &[usize] bitvector rep.
14 use rustc_data_structures::bitslice::{BitwiseOperator};
15 use rustc_data_structures::indexed_set::{IdxSet};
16 use rustc_data_structures::indexed_vec::Idx;
17 use rustc_mir::util::elaborate_drops::DropFlagState;
19 use super::super::gather_moves::{HasMoveData, MoveData, MoveOutIndex, MovePathIndex};
20 use super::super::MoveDataParamEnv;
21 use super::super::drop_flag_effects_for_function_entry;
22 use super::super::drop_flag_effects_for_location;
23 use super::super::on_lookup_result_bits;
25 use super::{BitDenotation, BlockSets, DataflowOperator};
27 // Dataflow analyses are built upon some interpretation of the
28 // bitvectors attached to each basic block, represented via a
29 // zero-sized structure.
31 /// `MaybeInitializedLvals` tracks all l-values 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 an l-value *must* be initialized at a
59 /// particular control-flow point, one can take the set-difference
60 /// between this data and the data from `MaybeUninitializedLvals` at the
61 /// corresponding control-flow point.
63 /// Similarly, at a given `drop` statement, the set-intersection
64 /// between this data and `MaybeUninitializedLvals` yields the set of
65 /// l-values that would require a dynamic drop-flag at that statement.
66 pub struct MaybeInitializedLvals<'a, 'tcx: 'a> {
67 tcx: TyCtxt<'a, 'tcx, 'tcx>,
69 mdpe: &'a MoveDataParamEnv<'tcx>,
72 impl<'a, 'tcx: 'a> MaybeInitializedLvals<'a, 'tcx> {
73 pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
75 mdpe: &'a MoveDataParamEnv<'tcx>)
78 MaybeInitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
82 impl<'a, 'tcx: 'a> HasMoveData<'tcx> for MaybeInitializedLvals<'a, 'tcx> {
83 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
86 /// `MaybeUninitializedLvals` tracks all l-values that might be
87 /// uninitialized upon reaching a particular point in the control flow
90 /// For example, in code like the following, we have corresponding
91 /// dataflow information shown in the right-hand comments.
95 /// fn foo(pred: bool) { // maybe-uninit:
97 /// let a = S; let b = S; let c; let d; // { c, d}
100 /// drop(a); // {a, c, d}
101 /// b = S; // {a, c, d}
104 /// drop(b); // { b, c, d}
105 /// d = S; // { b, c }
107 /// } // {a, b, c, d}
109 /// c = S; // {a, b, d}
113 /// To determine whether an l-value *must* be uninitialized at a
114 /// particular control-flow point, one can take the set-difference
115 /// between this data and the data from `MaybeInitializedLvals` at the
116 /// corresponding control-flow point.
118 /// Similarly, at a given `drop` statement, the set-intersection
119 /// between this data and `MaybeInitializedLvals` yields the set of
120 /// l-values that would require a dynamic drop-flag at that statement.
121 pub struct MaybeUninitializedLvals<'a, 'tcx: 'a> {
122 tcx: TyCtxt<'a, 'tcx, 'tcx>,
124 mdpe: &'a MoveDataParamEnv<'tcx>,
127 impl<'a, 'tcx: 'a> MaybeUninitializedLvals<'a, 'tcx> {
128 pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
130 mdpe: &'a MoveDataParamEnv<'tcx>)
133 MaybeUninitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
137 impl<'a, 'tcx: 'a> HasMoveData<'tcx> for MaybeUninitializedLvals<'a, 'tcx> {
138 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
141 /// `DefinitelyInitializedLvals` tracks all l-values that are definitely
142 /// initialized upon reaching a particular point in the control flow
145 /// FIXME: Note that once flow-analysis is complete, this should be
146 /// the set-complement of MaybeUninitializedLvals; thus we can get rid
147 /// of one or the other of these two. I'm inclined to get rid of
148 /// MaybeUninitializedLvals, simply because the sets will tend to be
149 /// smaller in this analysis and thus easier for humans to process
152 /// For example, in code like the following, we have corresponding
153 /// dataflow information shown in the right-hand comments.
157 /// fn foo(pred: bool) { // definite-init:
159 /// let a = S; let b = S; let c; let d; // {a, b }
162 /// drop(a); // { b, }
166 /// drop(b); // {a, }
175 /// To determine whether an l-value *may* be uninitialized at a
176 /// particular control-flow point, one can take the set-complement
179 /// Similarly, at a given `drop` statement, the set-difference between
180 /// this data and `MaybeInitializedLvals` yields the set of l-values
181 /// that would require a dynamic drop-flag at that statement.
182 pub struct DefinitelyInitializedLvals<'a, 'tcx: 'a> {
183 tcx: TyCtxt<'a, 'tcx, 'tcx>,
185 mdpe: &'a MoveDataParamEnv<'tcx>,
188 impl<'a, 'tcx: 'a> DefinitelyInitializedLvals<'a, 'tcx> {
189 pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
191 mdpe: &'a MoveDataParamEnv<'tcx>)
194 DefinitelyInitializedLvals { tcx: tcx, mir: mir, mdpe: mdpe }
198 impl<'a, 'tcx: 'a> HasMoveData<'tcx> for DefinitelyInitializedLvals<'a, 'tcx> {
199 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
202 /// `MovingOutStatements` tracks the statements that perform moves out
203 /// of particular l-values. More precisely, it tracks whether the
204 /// *effect* of such moves (namely, the uninitialization of the
205 /// l-value in question) can reach some point in the control-flow of
206 /// the function, or if that effect is "killed" by some intervening
207 /// operation reinitializing that l-value.
209 /// The resulting dataflow is a more enriched version of
210 /// `MaybeUninitializedLvals`. Both structures on their own only tell
211 /// you if an l-value *might* be uninitialized at a given point in the
212 /// control flow. But `MovingOutStatements` also includes the added
213 /// data of *which* particular statement causing the deinitialization
214 /// that the borrow checker's error meessage may need to report.
216 pub struct MovingOutStatements<'a, 'tcx: 'a> {
217 tcx: TyCtxt<'a, 'tcx, 'tcx>,
219 mdpe: &'a MoveDataParamEnv<'tcx>,
222 impl<'a, 'tcx> HasMoveData<'tcx> for MovingOutStatements<'a, 'tcx> {
223 fn move_data(&self) -> &MoveData<'tcx> { &self.mdpe.move_data }
226 impl<'a, 'tcx> MaybeInitializedLvals<'a, 'tcx> {
227 fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
228 state: DropFlagState)
231 DropFlagState::Absent => sets.kill(&path),
232 DropFlagState::Present => sets.gen(&path),
237 impl<'a, 'tcx> MaybeUninitializedLvals<'a, 'tcx> {
238 fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
239 state: DropFlagState)
242 DropFlagState::Absent => sets.gen(&path),
243 DropFlagState::Present => sets.kill(&path),
248 impl<'a, 'tcx> DefinitelyInitializedLvals<'a, 'tcx> {
249 fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex,
250 state: DropFlagState)
253 DropFlagState::Absent => sets.kill(&path),
254 DropFlagState::Present => sets.gen(&path),
259 impl<'a, 'tcx> BitDenotation for MaybeInitializedLvals<'a, 'tcx> {
260 type Idx = MovePathIndex;
261 fn name() -> &'static str { "maybe_init" }
262 fn bits_per_block(&self) -> usize {
263 self.move_data().move_paths.len()
266 fn start_block_effect(&self, sets: &mut BlockSets<MovePathIndex>)
268 drop_flag_effects_for_function_entry(
269 self.tcx, self.mir, self.mdpe,
271 assert!(s == DropFlagState::Present);
272 sets.on_entry.add(&path);
276 fn statement_effect(&self,
277 sets: &mut BlockSets<MovePathIndex>,
281 drop_flag_effects_for_location(
282 self.tcx, self.mir, self.mdpe,
283 Location { block: bb, statement_index: idx },
284 |path, s| Self::update_bits(sets, path, s)
288 fn terminator_effect(&self,
289 sets: &mut BlockSets<MovePathIndex>,
291 statements_len: usize)
293 drop_flag_effects_for_location(
294 self.tcx, self.mir, self.mdpe,
295 Location { block: bb, statement_index: statements_len },
296 |path, s| Self::update_bits(sets, path, s)
300 fn propagate_call_return(&self,
301 in_out: &mut IdxSet<MovePathIndex>,
302 _call_bb: mir::BasicBlock,
303 _dest_bb: mir::BasicBlock,
304 dest_lval: &mir::Lvalue) {
305 // when a call returns successfully, that means we need to set
306 // the bits for that dest_lval to 1 (initialized).
307 on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
308 self.move_data().rev_lookup.find(dest_lval),
309 |mpi| { in_out.add(&mpi); });
313 impl<'a, 'tcx> BitDenotation for MaybeUninitializedLvals<'a, 'tcx> {
314 type Idx = MovePathIndex;
315 fn name() -> &'static str { "maybe_uninit" }
316 fn bits_per_block(&self) -> usize {
317 self.move_data().move_paths.len()
320 // sets on_entry bits for Arg lvalues
321 fn start_block_effect(&self, sets: &mut BlockSets<MovePathIndex>) {
322 // set all bits to 1 (uninit) before gathering counterevidence
323 for e in sets.on_entry.words_mut() { *e = !0; }
325 drop_flag_effects_for_function_entry(
326 self.tcx, self.mir, self.mdpe,
328 assert!(s == DropFlagState::Present);
329 sets.on_entry.remove(&path);
333 fn statement_effect(&self,
334 sets: &mut BlockSets<MovePathIndex>,
338 drop_flag_effects_for_location(
339 self.tcx, self.mir, self.mdpe,
340 Location { block: bb, statement_index: idx },
341 |path, s| Self::update_bits(sets, path, s)
345 fn terminator_effect(&self,
346 sets: &mut BlockSets<MovePathIndex>,
348 statements_len: usize)
350 drop_flag_effects_for_location(
351 self.tcx, self.mir, self.mdpe,
352 Location { block: bb, statement_index: statements_len },
353 |path, s| Self::update_bits(sets, path, s)
357 fn propagate_call_return(&self,
358 in_out: &mut IdxSet<MovePathIndex>,
359 _call_bb: mir::BasicBlock,
360 _dest_bb: mir::BasicBlock,
361 dest_lval: &mir::Lvalue) {
362 // when a call returns successfully, that means we need to set
363 // the bits for that dest_lval to 0 (initialized).
364 on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
365 self.move_data().rev_lookup.find(dest_lval),
366 |mpi| { in_out.remove(&mpi); });
370 impl<'a, 'tcx> BitDenotation for DefinitelyInitializedLvals<'a, 'tcx> {
371 type Idx = MovePathIndex;
372 fn name() -> &'static str { "definite_init" }
373 fn bits_per_block(&self) -> usize {
374 self.move_data().move_paths.len()
377 // sets on_entry bits for Arg lvalues
378 fn start_block_effect(&self, sets: &mut BlockSets<MovePathIndex>) {
379 for e in sets.on_entry.words_mut() { *e = 0; }
381 drop_flag_effects_for_function_entry(
382 self.tcx, self.mir, self.mdpe,
384 assert!(s == DropFlagState::Present);
385 sets.on_entry.add(&path);
389 fn statement_effect(&self,
390 sets: &mut BlockSets<MovePathIndex>,
394 drop_flag_effects_for_location(
395 self.tcx, self.mir, self.mdpe,
396 Location { block: bb, statement_index: idx },
397 |path, s| Self::update_bits(sets, path, s)
401 fn terminator_effect(&self,
402 sets: &mut BlockSets<MovePathIndex>,
404 statements_len: usize)
406 drop_flag_effects_for_location(
407 self.tcx, self.mir, self.mdpe,
408 Location { block: bb, statement_index: statements_len },
409 |path, s| Self::update_bits(sets, path, s)
413 fn propagate_call_return(&self,
414 in_out: &mut IdxSet<MovePathIndex>,
415 _call_bb: mir::BasicBlock,
416 _dest_bb: mir::BasicBlock,
417 dest_lval: &mir::Lvalue) {
418 // when a call returns successfully, that means we need to set
419 // the bits for that dest_lval to 1 (initialized).
420 on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
421 self.move_data().rev_lookup.find(dest_lval),
422 |mpi| { in_out.add(&mpi); });
426 impl<'a, 'tcx> BitDenotation for MovingOutStatements<'a, 'tcx> {
427 type Idx = MoveOutIndex;
428 fn name() -> &'static str { "moving_out" }
429 fn bits_per_block(&self) -> usize {
430 self.move_data().moves.len()
433 fn start_block_effect(&self, _sets: &mut BlockSets<MoveOutIndex>) {
434 // no move-statements have been executed prior to function
435 // execution, so this method has no effect on `_sets`.
437 fn statement_effect(&self,
438 sets: &mut BlockSets<MoveOutIndex>,
441 let (tcx, mir, move_data) = (self.tcx, self.mir, self.move_data());
442 let stmt = &mir[bb].statements[idx];
443 let loc_map = &move_data.loc_map;
444 let path_map = &move_data.path_map;
445 let rev_lookup = &move_data.rev_lookup;
447 let loc = Location { block: bb, statement_index: idx };
448 debug!("stmt {:?} at loc {:?} moves out of move_indexes {:?}",
449 stmt, loc, &loc_map[loc]);
450 for move_index in &loc_map[loc] {
451 // Every path deinitialized by a *particular move*
452 // has corresponding bit, "gen'ed" (i.e. set)
453 // here, in dataflow vector
454 zero_to_one(sets.gen_set.words_mut(), *move_index);
456 let bits_per_block = self.bits_per_block();
458 mir::StatementKind::SetDiscriminant { .. } => {
459 span_bug!(stmt.source_info.span, "SetDiscriminant should not exist in borrowck");
461 mir::StatementKind::Assign(ref lvalue, _) => {
462 // assigning into this `lvalue` kills all
463 // MoveOuts from it, and *also* all MoveOuts
464 // for children and associated fragment sets.
465 on_lookup_result_bits(tcx,
468 rev_lookup.find(lvalue),
469 |mpi| for moi in &path_map[mpi] {
470 assert!(moi.index() < bits_per_block);
471 sets.kill_set.add(&moi);
474 mir::StatementKind::StorageLive(_) |
475 mir::StatementKind::StorageDead(_) |
476 mir::StatementKind::InlineAsm { .. } |
477 mir::StatementKind::Nop => {}
481 fn terminator_effect(&self,
482 sets: &mut BlockSets<MoveOutIndex>,
484 statements_len: usize)
486 let (mir, move_data) = (self.mir, self.move_data());
487 let term = mir[bb].terminator();
488 let loc_map = &move_data.loc_map;
489 let loc = Location { block: bb, statement_index: statements_len };
490 debug!("terminator {:?} at loc {:?} moves out of move_indexes {:?}",
491 term, loc, &loc_map[loc]);
492 let bits_per_block = self.bits_per_block();
493 for move_index in &loc_map[loc] {
494 assert!(move_index.index() < bits_per_block);
495 zero_to_one(sets.gen_set.words_mut(), *move_index);
499 fn propagate_call_return(&self,
500 in_out: &mut IdxSet<MoveOutIndex>,
501 _call_bb: mir::BasicBlock,
502 _dest_bb: mir::BasicBlock,
503 dest_lval: &mir::Lvalue) {
504 let move_data = self.move_data();
505 let bits_per_block = self.bits_per_block();
507 let path_map = &move_data.path_map;
508 on_lookup_result_bits(self.tcx,
511 move_data.rev_lookup.find(dest_lval),
512 |mpi| for moi in &path_map[mpi] {
513 assert!(moi.index() < bits_per_block);
519 fn zero_to_one(bitvec: &mut [usize], move_index: MoveOutIndex) {
520 let retval = bitvec.set_bit(move_index.index());
524 impl<'a, 'tcx> BitwiseOperator for MovingOutStatements<'a, 'tcx> {
526 fn join(&self, pred1: usize, pred2: usize) -> usize {
527 pred1 | pred2 // moves from both preds are in scope
531 impl<'a, 'tcx> BitwiseOperator for MaybeInitializedLvals<'a, 'tcx> {
533 fn join(&self, pred1: usize, pred2: usize) -> usize {
534 pred1 | pred2 // "maybe" means we union effects of both preds
538 impl<'a, 'tcx> BitwiseOperator for MaybeUninitializedLvals<'a, 'tcx> {
540 fn join(&self, pred1: usize, pred2: usize) -> usize {
541 pred1 | pred2 // "maybe" means we union effects of both preds
545 impl<'a, 'tcx> BitwiseOperator for DefinitelyInitializedLvals<'a, 'tcx> {
547 fn join(&self, pred1: usize, pred2: usize) -> usize {
548 pred1 & pred2 // "definitely" means we intersect effects of both preds
552 // The way that dataflow fixed point iteration works, you want to
553 // start at bottom and work your way to a fixed point. Control-flow
554 // merges will apply the `join` operator to each block entry's current
555 // state (which starts at that bottom value).
557 // This means, for propagation across the graph, that you either want
558 // to start at all-zeroes and then use Union as your merge when
559 // propagating, or you start at all-ones and then use Intersect as
560 // your merge when propagating.
562 impl<'a, 'tcx> DataflowOperator for MovingOutStatements<'a, 'tcx> {
564 fn bottom_value() -> bool {
565 false // bottom = no loans in scope by default
569 impl<'a, 'tcx> DataflowOperator for MaybeInitializedLvals<'a, 'tcx> {
571 fn bottom_value() -> bool {
572 false // bottom = uninitialized
576 impl<'a, 'tcx> DataflowOperator for MaybeUninitializedLvals<'a, 'tcx> {
578 fn bottom_value() -> bool {
579 false // bottom = initialized (start_block_effect counters this at outset)
583 impl<'a, 'tcx> DataflowOperator for DefinitelyInitializedLvals<'a, 'tcx> {
585 fn bottom_value() -> bool {
586 true // bottom = initialized (start_block_effect counters this at outset)