diff options
22 files changed, 2464 insertions, 837 deletions
diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs index 8a9f662bf83..0350824ee35 100644 --- a/src/libcore/intrinsics.rs +++ b/src/libcore/intrinsics.rs @@ -168,6 +168,16 @@ extern "rust-intrinsic" { pub fn atomic_singlethreadfence_rel(); pub fn atomic_singlethreadfence_acqrel(); + /// Magic intrinsic that derives its meaning from attributes + /// attached to the function. + /// + /// For example, dataflow uses this to inject static assertions so + /// that `rustc_peek(potentially_uninitialized)` would actually + /// double-check that dataflow did indeed compute that it is + /// uninitialized at that point in the control flow. + #[cfg(not(stage0))] + pub fn rustc_peek<T>(_: T) -> T; + /// Aborts the execution of the process. pub fn abort() -> !; diff --git a/src/librustc/middle/dataflow.rs b/src/librustc/middle/dataflow.rs index 41b27a48b29..4d01b59001c 100644 --- a/src/librustc/middle/dataflow.rs +++ b/src/librustc/middle/dataflow.rs @@ -660,8 +660,8 @@ fn set_bit(words: &mut [usize], bit: usize) -> bool { } fn bit_str(bit: usize) -> String { - let byte = bit >> 8; - let lobits = 1 << (bit & 0xFF); + let byte = bit >> 3; + let lobits = 1 << (bit & 0b111); format!("[{}:{}-{:02x}]", bit, byte, lobits) } diff --git a/src/librustc/mir/repr.rs b/src/librustc/mir/repr.rs index 458cb28144a..f9a671435ff 100644 --- a/src/librustc/mir/repr.rs +++ b/src/librustc/mir/repr.rs @@ -226,7 +226,8 @@ pub struct UpvarDecl { /// list of the `Mir`. /// /// (We use a `u32` internally just to save memory.) -#[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)] +#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, + RustcEncodable, RustcDecodable)] pub struct BasicBlock(u32); impl BasicBlock { diff --git a/src/librustc/mir/transform.rs b/src/librustc/mir/transform.rs index 79c44b2b851..828a48532a2 100644 --- a/src/librustc/mir/transform.rs +++ b/src/librustc/mir/transform.rs @@ -18,7 +18,7 @@ use ty::TyCtxt; use syntax::ast::NodeId; /// Where a specific Mir comes from. -#[derive(Copy, Clone)] +#[derive(Debug, Copy, Clone)] pub enum MirSource { /// Functions and methods. Fn(NodeId), diff --git a/src/librustc_borrowck/bitslice.rs b/src/librustc_borrowck/bitslice.rs index a4aa7ae1574..80fa86a007e 100644 --- a/src/librustc_borrowck/bitslice.rs +++ b/src/librustc_borrowck/bitslice.rs @@ -8,9 +8,14 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +// FIXME: move this to `rustc_data_structures` and potentially merge +// with `bitvec` there. + use std::mem; -/// `BitSlice` provides helper methods for treating a `[usize]` +pub type Word = usize; + +/// `BitSlice` provides helper methods for treating a `[Word]` /// as a bitvector. pub trait BitSlice { fn clear_bit(&mut self, idx: usize) -> bool; @@ -18,12 +23,12 @@ pub trait BitSlice { fn get_bit(&self, idx: usize) -> bool; } -impl BitSlice for [usize] { +impl BitSlice for [Word] { /// Clears bit at `idx` to 0; returns true iff this changed `self.` fn clear_bit(&mut self, idx: usize) -> bool { let words = self; debug!("clear_bit: words={} idx={}", - bits_to_string(words, words.len() * mem::size_of::<usize>()), bit_str(idx)); + bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx)); let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx); debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask); let oldv = words[word]; @@ -36,7 +41,7 @@ impl BitSlice for [usize] { fn set_bit(&mut self, idx: usize) -> bool { let words = self; debug!("set_bit: words={} idx={}", - bits_to_string(words, words.len() * mem::size_of::<usize>()), bit_str(idx)); + bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx)); let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx); debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask); let oldv = words[word]; @@ -54,52 +59,85 @@ impl BitSlice for [usize] { } struct BitLookup { - /// An index of the word holding the bit in original `[usize]` of query. + /// An index of the word holding the bit in original `[Word]` of query. word: usize, /// Index of the particular bit within the word holding the bit. bit_in_word: usize, /// Word with single 1-bit set corresponding to where the bit is located. - bit_mask: usize, + bit_mask: Word, } #[inline] fn bit_lookup(bit: usize) -> BitLookup { - let usize_bits = mem::size_of::<usize>() * 8; - let word = bit / usize_bits; - let bit_in_word = bit % usize_bits; + let word_bits = mem::size_of::<Word>() * 8; + let word = bit / word_bits; + let bit_in_word = bit % word_bits; let bit_mask = 1 << bit_in_word; BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask } } -fn bit_str(bit: usize) -> String { - let byte = bit >> 8; - let lobits = 1 << (bit & 0xFF); +fn bit_str(bit: Word) -> String { + let byte = bit >> 3; + let lobits = 1 << (bit & 0b111); format!("[{}:{}-{:02x}]", bit, byte, lobits) } -pub fn bits_to_string(words: &[usize], bytes: usize) -> String { +pub fn bits_to_string(words: &[Word], bits: usize) -> String { let mut result = String::new(); let mut sep = '['; // Note: this is a little endian printout of bytes. + // i tracks how many bits we have printed so far. let mut i = 0; for &word in words.iter() { let mut v = word; - for _ in 0..mem::size_of::<usize>() { - let byte = v & 0xFF; - if i >= bytes { - assert!(byte == 0); - } else { - result.push(sep); - result.push_str(&format!("{:02x}", byte)); - } + loop { // for each byte in `v`: + let remain = bits - i; + // If less than a byte remains, then mask just that many bits. + let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF }; + assert!(mask <= 0xFF); + let byte = v & mask; + + result.push(sep); + result.push_str(&format!("{:02x}", byte)); + + if remain <= 8 { break; } v >>= 8; - i += 1; + i += 8; sep = '-'; } } result.push(']'); return result } + +#[inline] +pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize], + in_vec: &[usize], + op: &Op) -> bool { + assert_eq!(out_vec.len(), in_vec.len()); + let mut changed = false; + for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) { + let old_val = *out_elt; + let new_val = op.join(old_val, *in_elt); + *out_elt = new_val; + changed |= old_val != new_val; + } + changed +} + +pub trait BitwiseOperator { + /// Applies some bit-operation pointwise to each of the bits in the two inputs. + fn join(&self, pred1: usize, pred2: usize) -> usize; +} + +pub struct Union; +impl BitwiseOperator for Union { + fn join(&self, a: usize, b: usize) -> usize { a | b } +} +pub struct Subtract; +impl BitwiseOperator for Subtract { + fn join(&self, a: usize, b: usize) -> usize { a & !b } +} diff --git a/src/librustc_borrowck/borrowck/mir/dataflow.rs b/src/librustc_borrowck/borrowck/mir/dataflow.rs deleted file mode 100644 index d6dd176e3ba..00000000000 --- a/src/librustc_borrowck/borrowck/mir/dataflow.rs +++ /dev/null @@ -1,504 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use syntax::attr::AttrMetaMethods; - -use rustc::ty::TyCtxt; -use rustc::mir::repr::{self, Mir}; - -use std::io; -use std::mem; -use std::usize; - -use super::MirBorrowckCtxt; -use super::gather_moves::{Location, MoveData, MovePathData, MovePathIndex, MoveOutIndex, PathMap}; -use super::graphviz; -use bitslice::BitSlice; // adds set_bit/get_bit to &[usize] bitvector rep. - -pub trait Dataflow { - fn dataflow(&mut self); -} - -impl<'b, 'a: 'b, 'tcx: 'a> Dataflow for MirBorrowckCtxt<'b, 'a, 'tcx> { - fn dataflow(&mut self) { - self.build_gen_and_kill_sets(); - self.pre_dataflow_instrumentation().unwrap(); - self.propagate(); - self.post_dataflow_instrumentation().unwrap(); - } -} - -struct PropagationContext<'c, 'b: 'c, 'a: 'b, 'tcx: 'a, OnReturn> - where OnReturn: Fn(&MoveData, &mut [usize], &repr::Lvalue) -{ - mbcx: &'c mut MirBorrowckCtxt<'b, 'a, 'tcx>, - changed: bool, - on_return: OnReturn -} - -impl<'b, 'a: 'b, 'tcx: 'a> MirBorrowckCtxt<'b, 'a, 'tcx> { - fn propagate(&mut self) { - let mut temp = vec![0; self.flow_state.sets.words_per_block]; - let mut propcx = PropagationContext { - mbcx: &mut *self, - changed: true, - on_return: |move_data, in_out, dest_lval| { - let move_path_index = move_data.rev_lookup.find(dest_lval); - on_all_children_bits(in_out, - &move_data.path_map, - &move_data.move_paths, - move_path_index, - &|in_out, mpi| { - in_out.clear_bit(mpi.idx()); - }); - }, - }; - while propcx.changed { - propcx.changed = false; - propcx.reset(&mut temp); - propcx.walk_cfg(&mut temp); - } - } - - fn build_gen_and_kill_sets(&mut self) { - // First we need to build the gen- and kill-sets. The - // gather_moves information provides a high-level mapping from - // mir-locations to the MoveOuts (and those correspond - // directly to gen-sets here). But we still need to figure out - // the kill-sets. - - let move_data = &self.flow_state.operator; - let move_paths = &move_data.move_paths; - let loc_map = &move_data.loc_map; - let path_map = &move_data.path_map; - let rev_lookup = &move_data.rev_lookup; - - for bb in self.mir.all_basic_blocks() { - let &repr::BasicBlockData { ref statements, - ref terminator, - is_cleanup: _ } = - self.mir.basic_block_data(bb); - - let mut sets = self.flow_state.sets.for_block(bb.index()); - for (j, stmt) in statements.iter().enumerate() { - let loc = Location { block: bb, index: j }; - debug!("stmt {:?} at loc {:?} moves out of move_indexes {:?}", - stmt, loc, &loc_map[loc]); - for move_index in &loc_map[loc] { - // Every path deinitialized by a *particular move* - // has corresponding bit, "gen'ed" (i.e. set) - // here, in dataflow vector - zero_to_one(&mut sets.gen_set, *move_index); - } - match stmt.kind { - repr::StatementKind::Assign(ref lvalue, _) => { - // assigning into this `lvalue` kills all - // MoveOuts from it, and *also* all MoveOuts - // for children and associated fragment sets. - let move_path_index = rev_lookup.find(lvalue); - - on_all_children_bits(sets.kill_set, - path_map, - move_paths, - move_path_index, - &|kill_set, mpi| { - kill_set.set_bit(mpi.idx()); - }); - } - } - } - - let loc = Location { block: bb, index: statements.len() }; - debug!("terminator {:?} at loc {:?} moves out of move_indexes {:?}", - terminator, loc, &loc_map[loc]); - for move_index in &loc_map[loc] { - zero_to_one(&mut sets.gen_set, *move_index); - } - } - - fn zero_to_one(gen_set: &mut [usize], move_index: MoveOutIndex) { - let retval = gen_set.set_bit(move_index.idx()); - assert!(retval); - } - } -} - -fn on_all_children_bits<Each>(set: &mut [usize], - path_map: &PathMap, - move_paths: &MovePathData, - move_path_index: MovePathIndex, - each_child: &Each) - where Each: Fn(&mut [usize], MoveOutIndex) -{ - // 1. invoke `each_child` callback for all moves that directly - // influence path for `move_path_index` - for move_index in &path_map[move_path_index] { - each_child(set, *move_index); - } - - // 2. for each child of the path (that is named in this - // function), recur. - // - // (Unnamed children are irrelevant to dataflow; by - // definition they have no associated moves.) - let mut next_child_index = move_paths[move_path_index].first_child; - while let Some(child_index) = next_child_index { - on_all_children_bits(set, path_map, move_paths, child_index, each_child); - next_child_index = move_paths[child_index].next_sibling; - } -} - -impl<'c, 'b: 'c, 'a: 'b, 'tcx: 'a, OnReturn> PropagationContext<'c, 'b, 'a, 'tcx, OnReturn> - where OnReturn: Fn(&MoveData, &mut [usize], &repr::Lvalue) -{ - fn reset(&mut self, bits: &mut [usize]) { - let e = if self.mbcx.flow_state.operator.initial_value() {usize::MAX} else {0}; - for b in bits { - *b = e; - } - } - - fn walk_cfg(&mut self, in_out: &mut [usize]) { - let &mut MirBorrowckCtxt { ref mir, ref mut flow_state, .. } = self.mbcx; - for (idx, bb) in mir.basic_blocks.iter().enumerate() { - { - let sets = flow_state.sets.for_block(idx); - debug_assert!(in_out.len() == sets.on_entry.len()); - in_out.clone_from_slice(sets.on_entry); - bitwise(in_out, sets.gen_set, &Union); - bitwise(in_out, sets.kill_set, &Subtract); - } - flow_state.propagate_bits_into_graph_successors_of(in_out, - &mut self.changed, - bb, - &self.on_return); - } - } -} - -impl<'b, 'a: 'b, 'tcx: 'a> MirBorrowckCtxt<'b, 'a, 'tcx> { - fn pre_dataflow_instrumentation(&self) -> io::Result<()> { - self.if_attr_meta_name_found( - "borrowck_graphviz_preflow", - |this, path: &str| { - graphviz::print_borrowck_graph_to(this, "preflow", path) - }) - } - - fn post_dataflow_instrumentation(&self) -> io::Result<()> { - self.if_attr_meta_name_found( - "borrowck_graphviz_postflow", - |this, path: &str| { - graphviz::print_borrowck_graph_to(this, "postflow", path) - }) - } - - fn if_attr_meta_name_found<F>(&self, - name: &str, - callback: F) -> io::Result<()> - where F: for <'aa, 'bb> FnOnce(&'aa Self, &'bb str) -> io::Result<()> - { - for attr in self.attributes { - if attr.check_name("rustc_mir") { - let items = attr.meta_item_list(); - for item in items.iter().flat_map(|l| l.iter()) { - if item.check_name(name) { - if let Some(s) = item.value_str() { - return callback(self, &s); - } else { - self.bcx.tcx.sess.span_err( - item.span, - &format!("{} attribute requires a path", item.name())); - } - } - } - } - } - - Ok(()) - } -} - -/// Maps each block to a set of bits -#[derive(Clone, Debug)] -struct Bits { - bits: Vec<usize>, -} - -impl Bits { - fn new(init_word: usize, num_words: usize) -> Self { - Bits { bits: vec![init_word; num_words] } - } -} - -pub struct DataflowState<O: BitDenotation> -{ - /// All the sets for the analysis. (Factored into its - /// own structure so that we can borrow it mutably - /// on its own separate from other fields.) - pub sets: AllSets, - - /// operator used to initialize, combine, and interpret bits. - operator: O, -} - -pub struct AllSets { - /// Analysis bitwidth for each block. - bits_per_block: usize, - - /// Number of words associated with each block entry - /// equal to bits_per_block / usize::BITS, rounded up. - words_per_block: usize, - - /// For each block, bits generated by executing the statements in - /// the block. (For comparison, the Terminator for each block is - /// handled in a flow-specific manner during propagation.) - gen_sets: Bits, - - /// For each block, bits killed by executing the statements in the - /// block. (For comparison, the Terminator for each block is - /// handled in a flow-specific manner during propagation.) - kill_sets: Bits, - - /// For each block, bits valid on entry to the block. - on_entry_sets: Bits, -} - -pub struct BlockSets<'a> { - on_entry: &'a mut [usize], - gen_set: &'a mut [usize], - kill_set: &'a mut [usize], -} - -impl AllSets { - pub fn bits_per_block(&self) -> usize { self.bits_per_block } - pub fn bytes_per_block(&self) -> usize { (self.bits_per_block + 7) / 8 } - pub fn for_block(&mut self, block_idx: usize) -> BlockSets { - let offset = self.words_per_block * block_idx; - let range = offset..(offset + self.words_per_block); - BlockSets { - on_entry: &mut self.on_entry_sets.bits[range.clone()], - gen_set: &mut self.gen_sets.bits[range.clone()], - kill_set: &mut self.kill_sets.bits[range], - } - } - - fn lookup_set_for<'a>(&self, sets: &'a Bits, block_idx: usize) -> &'a [usize] { - let offset = self.words_per_block * block_idx; - &sets.bits[offset..(offset + self.words_per_block)] - } - pub fn gen_set_for(&self, block_idx: usize) -> &[usize] { - self.lookup_set_for(&self.gen_sets, block_idx) - } - pub fn kill_set_for(&self, block_idx: usize) -> &[usize] { - self.lookup_set_for(&self.kill_sets, block_idx) - } - pub fn on_entry_set_for(&self, block_idx: usize) -> &[usize] { - self.lookup_set_for(&self.on_entry_sets, block_idx) - } -} - -impl<O: BitDenotation> DataflowState<O> { - fn each_bit<F>(&self, words: &[usize], mut f: F) - where F: FnMut(usize) { - //! Helper for iterating over the bits in a bitvector. - - for (word_index, &word) in words.iter().enumerate() { - if word != 0 { - let usize_bits: usize = mem::size_of::<usize>(); - let base_index = word_index * usize_bits; - for offset in 0..usize_bits { - let bit = 1 << offset; - if (word & bit) != 0 { - // NB: we round up the total number of bits - // that we store in any given bit set so that - // it is an even multiple of usize::BITS. This - // means that there may be some stray bits at - // the end that do not correspond to any - // actual value; that's why we first check - // that we are in range of bits_per_block. - let bit_index = base_index + offset as usize; - if bit_index >= self.sets.bits_per_block() { - return; - } else { - f(bit_index); - } - } - } - } - } - } - - pub fn interpret_set(&self, words: &[usize]) -> Vec<&O::Bit> { - let mut v = Vec::new(); - self.each_bit(words, |i| { - v.push(self.operator.interpret(i)); - }); - v - } -} - -pub trait BitwiseOperator { - /// Joins two predecessor bits together, typically either `|` or `&` - fn join(&self, pred1: usize, pred2: usize) -> usize; -} - -/// Parameterization for the precise form of data flow that is used. -pub trait DataflowOperator : BitwiseOperator { - /// Specifies the initial value for each bit in the `on_entry` set - fn initial_value(&self) -> bool; -} - -pub trait BitDenotation: DataflowOperator { - /// Specifies what is represented by each bit in the dataflow bitvector. - type Bit; - /// Size of each bivector allocated for each block in the analysis. - fn bits_per_block(&self) -> usize; - /// Provides the meaning of each entry in the dataflow bitvector. - /// (Mostly intended for use for better debug instrumentation.) - fn interpret(&self, idx: usize) -> &Self::Bit; -} - -impl<D: BitDenotation> DataflowState<D> { - pub fn new(mir: &Mir, denotation: D) -> Self { - let bits_per_block = denotation.bits_per_block(); - let usize_bits = mem::size_of::<usize>() * 8; - let words_per_block = (bits_per_block + usize_bits - 1) / usize_bits; - let num_blocks = mir.basic_blocks.len(); - let num_words = num_blocks * words_per_block; - - let entry = if denotation.initial_value() { usize::MAX } else {0}; - - let zeroes = Bits::new(0, num_words); - let on_entry = Bits::new(entry, num_words); - - DataflowState { - sets: AllSets { - bits_per_block: bits_per_block, - words_per_block: words_per_block, - gen_sets: zeroes.clone(), - kill_sets: zeroes, - on_entry_sets: on_entry, - }, - operator: denotation, - } - } -} - -impl<D: BitDenotation> DataflowState<D> { - /// Propagates the bits of `in_out` into all the successors of `bb`, - /// using bitwise operator denoted by `self.operator`. - /// - /// For most blocks, this is entirely uniform. However, for blocks - /// that end with a call terminator, the effect of the call on the - /// dataflow state may depend on whether the call returned - /// successfully or unwound. To reflect this, the `on_return` - /// callback mutates `in_out` when propagating `in_out` via a call - /// terminator; such mutation is performed *last*, to ensure its - /// side-effects do not leak elsewhere (e.g. into unwind target). - fn propagate_bits_into_graph_successors_of<OnReturn>( - &mut self, - in_out: &mut [usize], - changed: &mut bool, - bb: &repr::BasicBlockData, - on_return: OnReturn) where OnReturn: Fn(&D, &mut [usize], &repr::Lvalue) - { - match bb.terminator().kind { - repr::TerminatorKind::Return | - repr::TerminatorKind::Resume => {} - repr::TerminatorKind::Goto { ref target } | - repr::TerminatorKind::Drop { ref target, value: _, unwind: None } => { - self.propagate_bits_into_entry_set_for(in_out, changed, target); - } - repr::TerminatorKind::Drop { ref target, value: _, unwind: Some(ref unwind) } => { - self.propagate_bits_into_entry_set_for(in_out, changed, target); - self.propagate_bits_into_entry_set_for(in_out, changed, unwind); - } - repr::TerminatorKind::If { ref targets, .. } => { - self.propagate_bits_into_entry_set_for(in_out, changed, &targets.0); - self.propagate_bits_into_entry_set_for(in_out, changed, &targets.1); - } - repr::TerminatorKind::Switch { ref targets, .. } | - repr::TerminatorKind::SwitchInt { ref targets, .. } => { - for target in targets { - self.propagate_bits_into_entry_set_for(in_out, changed, target); - } - } - repr::TerminatorKind::Call { ref cleanup, ref destination, func: _, args: _ } => { - if let Some(ref unwind) = *cleanup { - self.propagate_bits_into_entry_set_for(in_out, changed, unwind); - } - if let Some((ref dest_lval, ref dest_bb)) = *destination { - // N.B.: This must be done *last*, after all other - // propagation, as documented in comment above. - on_return(&self.operator, in_out, dest_lval); - self.propagate_bits_into_entry_set_for(in_out, changed, dest_bb); - } - } - } - } - - fn propagate_bits_into_entry_set_for(&mut self, - in_out: &[usize], - changed: &mut bool, - bb: &repr::BasicBlock) { - let entry_set = self.sets.for_block(bb.index()).on_entry; - let set_changed = bitwise(entry_set, in_out, &self.operator); - if set_changed { - *changed = true; - } - } -} - - -impl<'a, 'tcx> DataflowState<MoveData<'tcx>> { - pub fn new_move_analysis(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Self { - let move_data = MoveData::gather_moves(mir, tcx); - DataflowState::new(mir, move_data) - } -} - -impl<'tcx> BitwiseOperator for MoveData<'tcx> { - #[inline] - fn join(&self, pred1: usize, pred2: usize) -> usize { - pred1 | pred2 // moves from both preds are in scope - } -} - -impl<'tcx> DataflowOperator for MoveData<'tcx> { - #[inline] - fn initial_value(&self) -> bool { - false // no loans in scope by default - } -} - -#[inline] -fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize], - in_vec: &[usize], - op: &Op) -> bool { - assert_eq!(out_vec.len(), in_vec.len()); - let mut changed = false; - for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec) { - let old_val = *out_elt; - let new_val = op.join(old_val, *in_elt); - *out_elt = new_val; - changed |= old_val != new_val; - } - changed -} - -struct Union; -impl BitwiseOperator for Union { - fn join(&self, a: usize, b: usize) -> usize { a | b } -} -struct Subtract; -impl BitwiseOperator for Subtract { - fn join(&self, a: usize, b: usize) -> usize { a & !b } -} diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/graphviz.rs b/src/librustc_borrowck/borrowck/mir/dataflow/graphviz.rs new file mode 100644 index 00000000000..63c11fb3545 --- /dev/null +++ b/src/librustc_borrowck/borrowck/mir/dataflow/graphviz.rs @@ -0,0 +1,340 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Hook into libgraphviz for rendering dataflow graphs for MIR. + +use syntax::ast::NodeId; +use rustc::mir::repr::{BasicBlock, Mir}; + +use dot; +use dot::IntoCow; + +use std::fmt::Debug; +use std::fs::File; +use std::io; +use std::io::prelude::*; +use std::marker::PhantomData; +use std::mem; +use std::path::Path; + +use super::super::MoveDataParamEnv; +use super::super::MirBorrowckCtxtPreDataflow; +use bitslice::bits_to_string; +use indexed_set::{Idx, IdxSet}; +use super::{BitDenotation, DataflowState}; + +impl<O: BitDenotation> DataflowState<O> { + fn each_bit<F>(&self, ctxt: &O::Ctxt, words: &IdxSet<O::Idx>, mut f: F) + where F: FnMut(O::Idx) { + //! Helper for iterating over the bits in a bitvector. + + let bits_per_block = self.operator.bits_per_block(ctxt); + let usize_bits: usize = mem::size_of::<usize>() * 8; + + for (word_index, &word) in words.words().iter().enumerate() { + if word != 0 { + let base_index = word_index * usize_bits; + for offset in 0..usize_bits { + let bit = 1 << offset; + if (word & bit) != 0 { + // NB: we round up the total number of bits + // that we store in any given bit set so that + // it is an even multiple of usize::BITS. This + // means that there may be some stray bits at + // the end that do not correspond to any + // actual value; that's why we first check + // that we are in range of bits_per_block. + let bit_index = base_index + offset as usize; + if bit_index >= bits_per_block { + return; + } else { + f(O::Idx::new(bit_index)); + } + } + } + } + } + } + + pub fn interpret_set<'c, P>(&self, + ctxt: &'c O::Ctxt, + words: &IdxSet<O::Idx>, + render_idx: &P) + -> Vec<&'c Debug> + where P: for <'b> Fn(&'b O::Ctxt, O::Idx) -> &'b Debug + { + let mut v = Vec::new(); + self.each_bit(ctxt, words, |i| { + v.push(render_idx(ctxt, i)); + }); + v + } +} + +pub trait MirWithFlowState<'tcx> { + type BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>>; + fn node_id(&self) -> NodeId; + fn mir(&self) -> &Mir<'tcx>; + fn analysis_ctxt(&self) -> &<Self::BD as BitDenotation>::Ctxt; + fn flow_state(&self) -> &DataflowState<Self::BD>; +} + +impl<'a, 'tcx: 'a, BD> MirWithFlowState<'tcx> for MirBorrowckCtxtPreDataflow<'a, 'tcx, BD> + where 'a, 'tcx: 'a, BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>> +{ + type BD = BD; + fn node_id(&self) -> NodeId { self.node_id } + fn mir(&self) -> &Mir<'tcx> { self.flow_state.mir() } + fn analysis_ctxt(&self) -> &BD::Ctxt { &self.flow_state.ctxt } + fn flow_state(&self) -> &DataflowState<Self::BD> { &self.flow_state.flow_state } +} + +struct Graph<'a, 'tcx, MWF:'a, P> where + MWF: MirWithFlowState<'tcx> +{ + mbcx: &'a MWF, + phantom: PhantomData<&'tcx ()>, + render_idx: P, +} + +pub fn print_borrowck_graph_to<'a, 'tcx, BD, P>( + mbcx: &MirBorrowckCtxtPreDataflow<'a, 'tcx, BD>, + path: &Path, + render_idx: P) + -> io::Result<()> + where BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>>, + P: for <'b> Fn(&'b BD::Ctxt, BD::Idx) -> &'b Debug +{ + let g = Graph { mbcx: mbcx, phantom: PhantomData, render_idx: render_idx }; + let mut v = Vec::new(); + dot::render(&g, &mut v)?; + debug!("print_borrowck_graph_to path: {} node_id: {}", + path.display(), mbcx.node_id); + File::create(path).and_then(|mut f| f.write_all(&v)) +} + +pub type Node = BasicBlock; + +#[derive(Copy, Clone, PartialEq, Eq, Debug)] +pub struct Edge { source: BasicBlock, index: usize } + +fn outgoing(mir: &Mir, bb: BasicBlock) -> Vec<Edge> { + let succ_len = mir.basic_block_data(bb).terminator().successors().len(); + (0..succ_len).map(|index| Edge { source: bb, index: index}).collect() +} + +impl<'a, 'tcx, MWF, P> dot::Labeller<'a> for Graph<'a, 'tcx, MWF, P> + where MWF: MirWithFlowState<'tcx>, + P: for <'b> Fn(&'b <MWF::BD as BitDenotation>::Ctxt, + <MWF::BD as BitDenotation>::Idx) + -> &'b Debug, +{ + type Node = Node; + type Edge = Edge; + fn graph_id(&self) -> dot::Id { + dot::Id::new(format!("graph_for_node_{}", + self.mbcx.node_id())) + .unwrap() + } + + fn node_id(&self, n: &Node) -> dot::Id { + dot::Id::new(format!("bb_{}", n.index())) + .unwrap() + } + + fn node_label(&self, n: &Node) -> dot::LabelText { + // A standard MIR label, as generated by write_node_label, is + // presented in a single column in a table. + // + // The code below does a bunch of formatting work to format a + // node (i.e. MIR basic-block) label with extra + // dataflow-enriched information. In particular, the goal is + // to add extra columns that present the three dataflow + // bitvectors, and the data those bitvectors represent. + // + // It presents it in the following format (where I am + // presenting the table rendering via ASCII art, one line per + // row of the table, and a chunk size of 3 rather than 5): + // + // ------ ----------------------- ------------ -------------------- + // [e1, e3, e4] + // [e8, e9] "= ENTRY:" <ENTRY-BITS> + // ------ ----------------------- ------------ -------------------- + // Left + // Most + // Column + // Is + // Just + // Normal + // Series + // Of + // MIR + // Stmts + // ------ ----------------------- ------------ -------------------- + // [g1, g4, g5] "= GEN:" <GEN-BITS> + // ------ ----------------------- ------------ -------------------- + // "KILL:" <KILL-BITS> "=" [k1, k3, k8] + // [k9] + // ------ ----------------------- ------------ -------------------- + // + // (In addition, the added dataflow is rendered with a colored + // background just so it will stand out compared to the + // statements.) + let mut v = Vec::new(); + let i = n.index(); + let chunk_size = 5; + const BG_FLOWCONTENT: &'static str = r#"bgcolor="pink""#; + const ALIGN_RIGHT: &'static str = r#"align="right""#; + const FACE_MONOSPACE: &'static str = r#"FACE="Courier""#; + fn chunked_present_left<W:io::Write>(w: &mut W, + interpreted: &[&Debug], + chunk_size: usize) + -> io::Result<()> + { + // This function may emit a sequence of <tr>'s, but it + // always finishes with an (unfinished) + // <tr><td></td><td> + // + // Thus, after being called, one should finish both the + // pending <td> as well as the <tr> itself. + let mut seen_one = false; + for c in interpreted.chunks(chunk_size) { + if seen_one { + // if not the first row, finish off the previous row + write!(w, "</td><td></td><td></td></tr>")?; + } + write!(w, "<tr><td></td><td {bg} {align}>{objs:?}", + bg = BG_FLOWCONTENT, + align = ALIGN_RIGHT, + objs = c)?; + seen_one = true; + } + if !seen_one { + write!(w, "<tr><td></td><td {bg} {align}>[]", + bg = BG_FLOWCONTENT, + align = ALIGN_RIGHT)?; + } + Ok(()) + } + ::rustc_mir::graphviz::write_node_label( + *n, self.mbcx.mir(), &mut v, 4, + |w| { + let ctxt = self.mbcx.analysis_ctxt(); + let flow = self.mbcx.flow_state(); + let entry_interp = flow.interpret_set(ctxt, + flow.sets.on_entry_set_for(i), + &self.render_idx); + chunked_present_left(w, &entry_interp[..], chunk_size)?; + let bits_per_block = flow.sets.bits_per_block(); + let entry = flow.sets.on_entry_set_for(i); + debug!("entry set for i={i} bits_per_block: {bpb} entry: {e:?} interp: {ei:?}", + i=i, e=entry, bpb=bits_per_block, ei=entry_interp); + write!(w, "= ENTRY:</td><td {bg}><FONT {face}>{entrybits:?}</FONT></td>\ + <td></td></tr>", + bg = BG_FLOWCONTENT, + face = FACE_MONOSPACE, + entrybits=bits_to_string(entry.words(), bits_per_block)) + }, + |w| { + let ctxt = self.mbcx.analysis_ctxt(); + let flow = self.mbcx.flow_state(); + let gen_interp = + flow.interpret_set(ctxt, flow.sets.gen_set_for(i), &self.render_idx); + let kill_interp = + flow.interpret_set(ctxt, flow.sets.kill_set_for(i), &self.render_idx); + chunked_present_left(w, &gen_interp[..], chunk_size)?; + let bits_per_block = flow.sets.bits_per_block(); + { + let gen = flow.sets.gen_set_for(i); + debug!("gen set for i={i} bits_per_block: {bpb} gen: {g:?} interp: {gi:?}", + i=i, g=gen, bpb=bits_per_block, gi=gen_interp); + write!(w, " = GEN:</td><td {bg}><FONT {face}>{genbits:?}</FONT></td>\ + <td></td></tr>", + bg = BG_FLOWCONTENT, + face = FACE_MONOSPACE, + genbits=bits_to_string(gen.words(), bits_per_block))?; + } + + { + let kill = flow.sets.kill_set_for(i); + debug!("kill set for i={i} bits_per_block: {bpb} kill: {k:?} interp: {ki:?}", + i=i, k=kill, bpb=bits_per_block, ki=kill_interp); + write!(w, "<tr><td></td><td {bg} {align}>KILL:</td>\ + <td {bg}><FONT {face}>{killbits:?}</FONT></td>", + bg = BG_FLOWCONTENT, + align = ALIGN_RIGHT, + face = FACE_MONOSPACE, + killbits=bits_to_string(kill.words(), bits_per_block))?; + } + + // (chunked_present_right) + let mut seen_one = false; + for k in kill_interp.chunks(chunk_size) { + if !seen_one { + // continuation of row; this is fourth <td> + write!(w, "<td {bg}>= {kill:?}</td></tr>", + bg = BG_FLOWCONTENT, + kill=k)?; + } else { + // new row, with indent of three <td>'s + write!(w, "<tr><td></td><td></td><td></td><td {bg}>{kill:?}</td></tr>", + bg = BG_FLOWCONTENT, + kill=k)?; + } + seen_one = true; + } + if !seen_one { + write!(w, "<td {bg}>= []</td></tr>", + bg = BG_FLOWCONTENT)?; + } + + Ok(()) + }) + .unwrap(); + dot::LabelText::html(String::from_utf8(v).unwrap()) + } + + fn node_shape(&self, _n: &Node) -> Option<dot::LabelText> { + Some(dot::LabelText::label("none")) + } +} + +impl<'a, 'tcx, MWF, P> dot::GraphWalk<'a> for Graph<'a, 'tcx, MWF, P> + where MWF: MirWithFlowState<'tcx> +{ + type Node = Node; + type Edge = Edge; + fn nodes(&self) -> dot::Nodes<Node> { + self.mbcx.mir().all_basic_blocks().into_cow() + } + + fn edges(&self) -> dot::Edges<Edge> { + let mir = self.mbcx.mir(); + let blocks = mir.all_basic_blocks(); + // base initial capacity on assumption every block has at + // least one outgoing edge (Which should be true for all + // blocks but one, the exit-block). + let mut edges = Vec::with_capacity(blocks.len()); + for bb in blocks { + let outgoing = outgoing(mir, bb); + edges.extend(outgoing.into_iter()); + } + edges.into_cow() + } + + fn source(&self, edge: &Edge) -> Node { + edge.source + } + + fn target(&self, edge: &Edge) -> Node { + let mir = self.mbcx.mir(); + mir.basic_block_data(edge.source).terminator().successors()[edge.index] + } +} diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs b/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs new file mode 100644 index 00000000000..e3435ed9905 --- /dev/null +++ b/src/librustc_borrowck/borrowck/mir/dataflow/impls.rs @@ -0,0 +1,571 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::ty::TyCtxt; +use rustc::mir::repr::{self, Mir}; + +use super::super::gather_moves::{Location}; +use super::super::gather_moves::{MoveOutIndex, MovePathIndex}; +use super::super::MoveDataParamEnv; +use super::super::DropFlagState; +use super::super::drop_flag_effects_for_function_entry; +use super::super::drop_flag_effects_for_location; +use super::super::on_all_children_bits; + +use super::{BitDenotation, BlockSets, DataflowOperator}; + +use bitslice::BitSlice; // adds set_bit/get_bit to &[usize] bitvector rep. +use bitslice::{BitwiseOperator}; +use indexed_set::{Idx, IdxSet}; + +// Dataflow analyses are built upon some interpretation of the +// bitvectors attached to each basic block, represented via a +// zero-sized structure. + +/// `MaybeInitializedLvals` tracks all l-values that might be +/// initialized upon reaching a particular point in the control flow +/// for a function. +/// +/// For example, in code like the following, we have corresponding +/// dataflow information shown in the right-hand comments. +/// +/// ```rust +/// struct S; +/// fn foo(pred: bool) { // maybe-init: +/// // {} +/// let a = S; let b = S; let c; let d; // {a, b} +/// +/// if pred { +/// drop(a); // { b} +/// b = S; // { b} +/// +/// } else { +/// drop(b); // {a} +/// d = S; // {a, d} +/// +/// } // {a, b, d} +/// +/// c = S; // {a, b, c, d} +/// } +/// ``` +/// +/// To determine whether an l-value *must* be initialized at a +/// particular control-flow point, one can take the set-difference +/// between this data and the data from `MaybeUninitializedLvals` at the +/// corresponding control-flow point. +/// +/// Similarly, at a given `drop` statement, the set-intersection +/// between this data and `MaybeUninitializedLvals` yields the set of +/// l-values that would require a dynamic drop-flag at that statement. +pub struct MaybeInitializedLvals<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &'a Mir<'tcx>, +} + +impl<'a, 'tcx: 'a> MaybeInitializedLvals<'a, 'tcx> { + pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self { + MaybeInitializedLvals { tcx: tcx, mir: mir } + } +} + +/// `MaybeUninitializedLvals` tracks all l-values that might be +/// uninitialized upon reaching a particular point in the control flow +/// for a function. +/// +/// For example, in code like the following, we have corresponding +/// dataflow information shown in the right-hand comments. +/// +/// ```rust +/// struct S; +/// fn foo(pred: bool) { // maybe-uninit: +/// // {a, b, c, d} +/// let a = S; let b = S; let c; let d; // { c, d} +/// +/// if pred { +/// drop(a); // {a, c, d} +/// b = S; // {a, c, d} +/// +/// } else { +/// drop(b); // { b, c, d} +/// d = S; // { b, c } +/// +/// } // {a, b, c, d} +/// +/// c = S; // {a, b, d} +/// } +/// ``` +/// +/// To determine whether an l-value *must* be uninitialized at a +/// particular control-flow point, one can take the set-difference +/// between this data and the data from `MaybeInitializedLvals` at the +/// corresponding control-flow point. +/// +/// Similarly, at a given `drop` statement, the set-intersection +/// between this data and `MaybeInitializedLvals` yields the set of +/// l-values that would require a dynamic drop-flag at that statement. +pub struct MaybeUninitializedLvals<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &'a Mir<'tcx>, +} + +impl<'a, 'tcx: 'a> MaybeUninitializedLvals<'a, 'tcx> { + pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self { + MaybeUninitializedLvals { tcx: tcx, mir: mir } + } +} + +/// `DefinitelyInitializedLvals` tracks all l-values that are definitely +/// initialized upon reaching a particular point in the control flow +/// for a function. +/// +/// FIXME: Note that once flow-analysis is complete, this should be +/// the set-complement of MaybeUninitializedLvals; thus we can get rid +/// of one or the other of these two. I'm inclined to get rid of +/// MaybeUninitializedLvals, simply because the sets will tend to be +/// smaller in this analysis and thus easier for humans to process +/// when debugging. +/// +/// For example, in code like the following, we have corresponding +/// dataflow information shown in the right-hand comments. +/// +/// ```rust +/// struct S; +/// fn foo(pred: bool) { // definite-init: +/// // { } +/// let a = S; let b = S; let c; let d; // {a, b } +/// +/// if pred { +/// drop(a); // { b, } +/// b = S; // { b, } +/// +/// } else { +/// drop(b); // {a, } +/// d = S; // {a, d} +/// +/// } // { } +/// +/// c = S; // { c } +/// } +/// ``` +/// +/// To determine whether an l-value *may* be uninitialized at a +/// particular control-flow point, one can take the set-complement +/// of this data. +/// +/// Similarly, at a given `drop` statement, the set-difference between +/// this data and `MaybeInitializedLvals` yields the set of l-values +/// that would require a dynamic drop-flag at that statement. +pub struct DefinitelyInitializedLvals<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &'a Mir<'tcx>, +} + +impl<'a, 'tcx: 'a> DefinitelyInitializedLvals<'a, 'tcx> { + pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self { + DefinitelyInitializedLvals { tcx: tcx, mir: mir } + } +} + +/// `MovingOutStatements` tracks the statements that perform moves out +/// of particular l-values. More precisely, it tracks whether the +/// *effect* of such moves (namely, the uninitialization of the +/// l-value in question) can reach some point in the control-flow of +/// the function, or if that effect is "killed" by some intervening +/// operation reinitializing that l-value. +/// +/// The resulting dataflow is a more enriched version of +/// `MaybeUninitializedLvals`. Both structures on their own only tell +/// you if an l-value *might* be uninitialized at a given point in the +/// control flow. But `MovingOutStatements` also includes the added +/// data of *which* particular statement causing the deinitialization +/// that the borrow checker's error meessage may need to report. +#[allow(dead_code)] +pub struct MovingOutStatements<'a, 'tcx: 'a> { + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &'a Mir<'tcx>, +} + +impl<'a, 'tcx> MaybeInitializedLvals<'a, 'tcx> { + fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, + state: DropFlagState) + { + match state { + DropFlagState::Absent => sets.kill(&path), + DropFlagState::Present => sets.gen(&path), + } + } +} + +impl<'a, 'tcx> MaybeUninitializedLvals<'a, 'tcx> { + fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, + state: DropFlagState) + { + match state { + DropFlagState::Absent => sets.gen(&path), + DropFlagState::Present => sets.kill(&path), + } + } +} + +impl<'a, 'tcx> DefinitelyInitializedLvals<'a, 'tcx> { + fn update_bits(sets: &mut BlockSets<MovePathIndex>, path: MovePathIndex, + state: DropFlagState) + { + match state { + DropFlagState::Absent => sets.kill(&path), + DropFlagState::Present => sets.gen(&path), + } + } +} + +impl<'a, 'tcx> BitDenotation for MaybeInitializedLvals<'a, 'tcx> { + type Idx = MovePathIndex; + type Ctxt = MoveDataParamEnv<'tcx>; + fn name() -> &'static str { "maybe_init" } + fn bits_per_block(&self, ctxt: &Self::Ctxt) -> usize { + ctxt.move_data.move_paths.len() + } + + fn start_block_effect(&self, ctxt: &Self::Ctxt, sets: &mut BlockSets<MovePathIndex>) + { + drop_flag_effects_for_function_entry( + self.tcx, self.mir, ctxt, + |path, s| { + assert!(s == DropFlagState::Present); + sets.on_entry.add(&path); + }); + } + + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + idx: usize) + { + drop_flag_effects_for_location( + self.tcx, self.mir, ctxt, + Location { block: bb, index: idx }, + |path, s| Self::update_bits(sets, path, s) + ) + } + + fn terminator_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + drop_flag_effects_for_location( + self.tcx, self.mir, ctxt, + Location { block: bb, index: statements_len }, + |path, s| Self::update_bits(sets, path, s) + ) + } + + fn propagate_call_return(&self, + ctxt: &Self::Ctxt, + in_out: &mut IdxSet<MovePathIndex>, + _call_bb: repr::BasicBlock, + _dest_bb: repr::BasicBlock, + dest_lval: &repr::Lvalue) { + // when a call returns successfully, that means we need to set + // the bits for that dest_lval to 1 (initialized). + let move_path_index = ctxt.move_data.rev_lookup.find(dest_lval); + on_all_children_bits(self.tcx, self.mir, &ctxt.move_data, + move_path_index, + |mpi| { in_out.add(&mpi); }); + } +} + +impl<'a, 'tcx> BitDenotation for MaybeUninitializedLvals<'a, 'tcx> { + type Idx = MovePathIndex; + type Ctxt = MoveDataParamEnv<'tcx>; + fn name() -> &'static str { "maybe_uninit" } + fn bits_per_block(&self, ctxt: &Self::Ctxt) -> usize { + ctxt.move_data.move_paths.len() + } + + // sets on_entry bits for Arg lvalues + fn start_block_effect(&self, ctxt: &Self::Ctxt, sets: &mut BlockSets<MovePathIndex>) { + // set all bits to 1 (uninit) before gathering counterevidence + for e in sets.on_entry.words_mut() { *e = !0; } + + drop_flag_effects_for_function_entry( + self.tcx, self.mir, ctxt, + |path, s| { + assert!(s == DropFlagState::Present); + sets.on_entry.remove(&path); + }); + } + + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + idx: usize) + { + drop_flag_effects_for_location( + self.tcx, self.mir, ctxt, + Location { block: bb, index: idx }, + |path, s| Self::update_bits(sets, path, s) + ) + } + + fn terminator_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + drop_flag_effects_for_location( + self.tcx, self.mir, ctxt, + Location { block: bb, index: statements_len }, + |path, s| Self::update_bits(sets, path, s) + ) + } + + fn propagate_call_return(&self, + ctxt: &Self::Ctxt, + in_out: &mut IdxSet<MovePathIndex>, + _call_bb: repr::BasicBlock, + _dest_bb: repr::BasicBlock, + dest_lval: &repr::Lvalue) { + // when a call returns successfully, that means we need to set + // the bits for that dest_lval to 1 (initialized). + let move_path_index = ctxt.move_data.rev_lookup.find(dest_lval); + on_all_children_bits(self.tcx, self.mir, &ctxt.move_data, + move_path_index, + |mpi| { in_out.remove(&mpi); }); + } +} + +impl<'a, 'tcx> BitDenotation for DefinitelyInitializedLvals<'a, 'tcx> { + type Idx = MovePathIndex; + type Ctxt = MoveDataParamEnv<'tcx>; + fn name() -> &'static str { "definite_init" } + fn bits_per_block(&self, ctxt: &Self::Ctxt) -> usize { + ctxt.move_data.move_paths.len() + } + + // sets on_entry bits for Arg lvalues + fn start_block_effect(&self, ctxt: &Self::Ctxt, sets: &mut BlockSets<MovePathIndex>) { + for e in sets.on_entry.words_mut() { *e = 0; } + + drop_flag_effects_for_function_entry( + self.tcx, self.mir, ctxt, + |path, s| { + assert!(s == DropFlagState::Present); + sets.on_entry.add(&path); + }); + } + + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + idx: usize) + { + drop_flag_effects_for_location( + self.tcx, self.mir, ctxt, + Location { block: bb, index: idx }, + |path, s| Self::update_bits(sets, path, s) + ) + } + + fn terminator_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MovePathIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + drop_flag_effects_for_location( + self.tcx, self.mir, ctxt, + Location { block: bb, index: statements_len }, + |path, s| Self::update_bits(sets, path, s) + ) + } + + fn propagate_call_return(&self, + ctxt: &Self::Ctxt, + in_out: &mut IdxSet<MovePathIndex>, + _call_bb: repr::BasicBlock, + _dest_bb: repr::BasicBlock, + dest_lval: &repr::Lvalue) { + // when a call returns successfully, that means we need to set + // the bits for that dest_lval to 1 (initialized). + let move_path_index = ctxt.move_data.rev_lookup.find(dest_lval); + on_all_children_bits(self.tcx, self.mir, &ctxt.move_data, + move_path_index, + |mpi| { in_out.add(&mpi); }); + } +} + +impl<'a, 'tcx> BitDenotation for MovingOutStatements<'a, 'tcx> { + type Idx = MoveOutIndex; + type Ctxt = MoveDataParamEnv<'tcx>; + fn name() -> &'static str { "moving_out" } + fn bits_per_block(&self, ctxt: &Self::Ctxt) -> usize { + ctxt.move_data.moves.len() + } + + fn start_block_effect(&self,_move_data: &Self::Ctxt, _sets: &mut BlockSets<MoveOutIndex>) { + // no move-statements have been executed prior to function + // execution, so this method has no effect on `_sets`. + } + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MoveOutIndex>, + bb: repr::BasicBlock, + idx: usize) { + let (tcx, mir, move_data) = (self.tcx, self.mir, &ctxt.move_data); + let stmt = &mir.basic_block_data(bb).statements[idx]; + let loc_map = &move_data.loc_map; + let path_map = &move_data.path_map; + let rev_lookup = &move_data.rev_lookup; + + let loc = Location { block: bb, index: idx }; + debug!("stmt {:?} at loc {:?} moves out of move_indexes {:?}", + stmt, loc, &loc_map[loc]); + for move_index in &loc_map[loc] { + // Every path deinitialized by a *particular move* + // has corresponding bit, "gen'ed" (i.e. set) + // here, in dataflow vector + zero_to_one(sets.gen_set.words_mut(), *move_index); + } + let bits_per_block = self.bits_per_block(ctxt); + match stmt.kind { + repr::StatementKind::Assign(ref lvalue, _) => { + // assigning into this `lvalue` kills all + // MoveOuts from it, and *also* all MoveOuts + // for children and associated fragment sets. + let move_path_index = rev_lookup.find(lvalue); + on_all_children_bits(tcx, + mir, + move_data, + move_path_index, + |mpi| for moi in &path_map[mpi] { + assert!(moi.idx() < bits_per_block); + sets.kill_set.add(&moi); + }); + } + } + } + + fn terminator_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<MoveOutIndex>, + bb: repr::BasicBlock, + statements_len: usize) + { + let (mir, move_data) = (self.mir, &ctxt.move_data); + let term = mir.basic_block_data(bb).terminator.as_ref().unwrap(); + let loc_map = &move_data.loc_map; + let loc = Location { block: bb, index: statements_len }; + debug!("terminator {:?} at loc {:?} moves out of move_indexes {:?}", + term, loc, &loc_map[loc]); + let bits_per_block = self.bits_per_block(ctxt); + for move_index in &loc_map[loc] { + assert!(move_index.idx() < bits_per_block); + zero_to_one(sets.gen_set.words_mut(), *move_index); + } + } + + fn propagate_call_return(&self, + ctxt: &Self::Ctxt, + in_out: &mut IdxSet<MoveOutIndex>, + _call_bb: repr::BasicBlock, + _dest_bb: repr::BasicBlock, + dest_lval: &repr::Lvalue) { + let move_data = &ctxt.move_data; + let move_path_index = move_data.rev_lookup.find(dest_lval); + let bits_per_block = self.bits_per_block(ctxt); + + let path_map = &move_data.path_map; + on_all_children_bits(self.tcx, + self.mir, + move_data, + move_path_index, + |mpi| for moi in &path_map[mpi] { + assert!(moi.idx() < bits_per_block); + in_out.remove(&moi); + }); + } +} + +fn zero_to_one(bitvec: &mut [usize], move_index: MoveOutIndex) { + let retval = bitvec.set_bit(move_index.idx()); + assert!(retval); +} + +impl<'a, 'tcx> BitwiseOperator for MovingOutStatements<'a, 'tcx> { + #[inline] + fn join(&self, pred1: usize, pred2: usize) -> usize { + pred1 | pred2 // moves from both preds are in scope + } +} + +impl<'a, 'tcx> BitwiseOperator for MaybeInitializedLvals<'a, 'tcx> { + #[inline] + fn join(&self, pred1: usize, pred2: usize) -> usize { + pred1 | pred2 // "maybe" means we union effects of both preds + } +} + +impl<'a, 'tcx> BitwiseOperator for MaybeUninitializedLvals<'a, 'tcx> { + #[inline] + fn join(&self, pred1: usize, pred2: usize) -> usize { + pred1 | pred2 // "maybe" means we union effects of both preds + } +} + +impl<'a, 'tcx> BitwiseOperator for DefinitelyInitializedLvals<'a, 'tcx> { + #[inline] + fn join(&self, pred1: usize, pred2: usize) -> usize { + pred1 & pred2 // "definitely" means we intersect effects of both preds + } +} + +// The way that dataflow fixed point iteration works, you want to +// start at bottom and work your way to a fixed point. Control-flow +// merges will apply the `join` operator to each block entry's current +// state (which starts at that bottom value). +// +// This means, for propagation across the graph, that you either want +// to start at all-zeroes and then use Union as your merge when +// propagating, or you start at all-ones and then use Intersect as +// your merge when propagating. + +impl<'a, 'tcx> DataflowOperator for MovingOutStatements<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + false // bottom = no loans in scope by default + } +} + +impl<'a, 'tcx> DataflowOperator for MaybeInitializedLvals<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + false // bottom = uninitialized + } +} + +impl<'a, 'tcx> DataflowOperator for MaybeUninitializedLvals<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + false // bottom = initialized (start_block_effect counters this at outset) + } +} + +impl<'a, 'tcx> DataflowOperator for DefinitelyInitializedLvals<'a, 'tcx> { + #[inline] + fn bottom_value() -> bool { + true // bottom = initialized (start_block_effect counters this at outset) + } +} diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs new file mode 100644 index 00000000000..b46b6c368a0 --- /dev/null +++ b/src/librustc_borrowck/borrowck/mir/dataflow/mod.rs @@ -0,0 +1,491 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::ty::TyCtxt; +use rustc::mir::repr::{self, Mir}; + +use std::fmt::Debug; +use std::io; +use std::mem; +use std::path::PathBuf; +use std::usize; + +use super::MirBorrowckCtxtPreDataflow; +use super::MoveDataParamEnv; + +use bitslice::{bitwise, BitwiseOperator}; +use indexed_set::{Idx, IdxSet, IdxSetBuf}; + +pub use self::sanity_check::sanity_check_via_rustc_peek; +pub use self::impls::{MaybeInitializedLvals, MaybeUninitializedLvals}; +pub use self::impls::{DefinitelyInitializedLvals, MovingOutStatements}; + +mod graphviz; +mod sanity_check; +mod impls; + +pub trait Dataflow<BD: BitDenotation> { + fn dataflow<P>(&mut self, p: P) where P: Fn(&BD::Ctxt, BD::Idx) -> &Debug; +} + +impl<'a, 'tcx: 'a, BD> Dataflow<BD> for MirBorrowckCtxtPreDataflow<'a, 'tcx, BD> + where BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>> + DataflowOperator +{ + fn dataflow<P>(&mut self, p: P) where P: Fn(&BD::Ctxt, BD::Idx) -> &Debug { + self.flow_state.build_sets(); + self.pre_dataflow_instrumentation(|c,i| p(c,i)).unwrap(); + self.flow_state.propagate(); + self.post_dataflow_instrumentation(|c,i| p(c,i)).unwrap(); + } +} + +struct PropagationContext<'b, 'a: 'b, 'tcx: 'a, O> + where O: 'b + BitDenotation, O::Ctxt: 'a +{ + builder: &'b mut DataflowAnalysis<'a, 'tcx, O>, + changed: bool, +} + +impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> + where BD: BitDenotation + DataflowOperator +{ + fn propagate(&mut self) { + let mut temp = IdxSetBuf::new_empty(self.flow_state.sets.bits_per_block); + let mut propcx = PropagationContext { + builder: self, + changed: true, + }; + while propcx.changed { + propcx.changed = false; + propcx.reset(&mut temp); + propcx.walk_cfg(&mut temp); + } + } + + fn build_sets(&mut self) { + // First we need to build the entry-, gen- and kill-sets. The + // gather_moves information provides a high-level mapping from + // mir-locations to the MoveOuts (and those correspond + // directly to gen-sets here). But we still need to figure out + // the kill-sets. + + { + let sets = &mut self.flow_state.sets.for_block(repr::START_BLOCK.index()); + self.flow_state.operator.start_block_effect(&self.ctxt, sets); + } + + for bb in self.mir.all_basic_blocks() { + let &repr::BasicBlockData { ref statements, + ref terminator, + is_cleanup: _ } = + self.mir.basic_block_data(bb); + + let sets = &mut self.flow_state.sets.for_block(bb.index()); + for j_stmt in 0..statements.len() { + self.flow_state.operator.statement_effect(&self.ctxt, sets, bb, j_stmt); + } + + if terminator.is_some() { + let stmts_len = statements.len(); + self.flow_state.operator.terminator_effect(&self.ctxt, sets, bb, stmts_len); + } + } + } +} + +impl<'b, 'a: 'b, 'tcx: 'a, BD> PropagationContext<'b, 'a, 'tcx, BD> + where BD: BitDenotation + DataflowOperator +{ + fn reset(&mut self, bits: &mut IdxSet<BD::Idx>) { + let e = if BD::bottom_value() {!0} else {0}; + for b in bits.words_mut() { + *b = e; + } + } + + fn walk_cfg(&mut self, in_out: &mut IdxSet<BD::Idx>) { + let mir = self.builder.mir; + for (bb_idx, bb_data) in mir.basic_blocks.iter().enumerate() { + let builder = &mut self.builder; + { + let sets = builder.flow_state.sets.for_block(bb_idx); + debug_assert!(in_out.words().len() == sets.on_entry.words().len()); + in_out.clone_from(sets.on_entry); + in_out.union(sets.gen_set); + in_out.subtract(sets.kill_set); + } + builder.propagate_bits_into_graph_successors_of( + in_out, &mut self.changed, (repr::BasicBlock::new(bb_idx), bb_data)); + } + } +} + +fn dataflow_path(context: &str, prepost: &str, path: &str) -> PathBuf { + format!("{}_{}", context, prepost); + let mut path = PathBuf::from(path); + let new_file_name = { + let orig_file_name = path.file_name().unwrap().to_str().unwrap(); + format!("{}_{}", context, orig_file_name) + }; + path.set_file_name(new_file_name); + path +} + +impl<'a, 'tcx: 'a, BD> MirBorrowckCtxtPreDataflow<'a, 'tcx, BD> + where BD: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>> +{ + fn pre_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()> + where P: Fn(&BD::Ctxt, BD::Idx) -> &Debug + { + if let Some(ref path_str) = self.print_preflow_to { + let path = dataflow_path(BD::name(), "preflow", path_str); + graphviz::print_borrowck_graph_to(self, &path, p) + } else { + Ok(()) + } + } + + fn post_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()> + where P: Fn(&BD::Ctxt, BD::Idx) -> &Debug + { + if let Some(ref path_str) = self.print_postflow_to { + let path = dataflow_path(BD::name(), "postflow", path_str); + graphviz::print_borrowck_graph_to(self, &path, p) + } else{ + Ok(()) + } + } +} + +/// Maps each block to a set of bits +#[derive(Debug)] +struct Bits<E:Idx> { + bits: IdxSetBuf<E>, +} + +impl<E:Idx> Clone for Bits<E> { + fn clone(&self) -> Self { Bits { bits: self.bits.clone() } } +} + +impl<E:Idx> Bits<E> { + fn new(bits: IdxSetBuf<E>) -> Self { + Bits { bits: bits } + } +} + +pub struct DataflowAnalysis<'a, 'tcx: 'a, O> + where O: BitDenotation, O::Ctxt: 'a +{ + flow_state: DataflowState<O>, + mir: &'a Mir<'tcx>, + ctxt: &'a O::Ctxt, +} + +impl<'a, 'tcx: 'a, O> DataflowAnalysis<'a, 'tcx, O> + where O: BitDenotation +{ + pub fn results(self) -> DataflowResults<O> { + DataflowResults(self.flow_state) + } + + pub fn mir(&self) -> &'a Mir<'tcx> { self.mir } +} + +pub struct DataflowResults<O>(DataflowState<O>) where O: BitDenotation; + +// FIXME: This type shouldn't be public, but the graphviz::MirWithFlowState trait +// references it in a method signature. Look into using `pub(crate)` to address this. +pub struct DataflowState<O: BitDenotation> +{ + /// All the sets for the analysis. (Factored into its + /// own structure so that we can borrow it mutably + /// on its own separate from other fields.) + pub sets: AllSets<O::Idx>, + + /// operator used to initialize, combine, and interpret bits. + operator: O, +} + +#[derive(Debug)] +pub struct AllSets<E: Idx> { + /// Analysis bitwidth for each block. + bits_per_block: usize, + + /// Number of words associated with each block entry + /// equal to bits_per_block / usize::BITS, rounded up. + words_per_block: usize, + + /// For each block, bits generated by executing the statements in + /// the block. (For comparison, the Terminator for each block is + /// handled in a flow-specific manner during propagation.) + gen_sets: Bits<E>, + + /// For each block, bits killed by executing the statements in the + /// block. (For comparison, the Terminator for each block is + /// handled in a flow-specific manner during propagation.) + kill_sets: Bits<E>, + + /// For each block, bits valid on entry to the block. + on_entry_sets: Bits<E>, +} + +pub struct BlockSets<'a, E: Idx> { + on_entry: &'a mut IdxSet<E>, + gen_set: &'a mut IdxSet<E>, + kill_set: &'a mut IdxSet<E>, +} + +impl<'a, E:Idx> BlockSets<'a, E> { + fn gen(&mut self, e: &E) { + self.gen_set.add(e); + self.kill_set.remove(e); + } + fn kill(&mut self, e: &E) { + self.gen_set.remove(e); + self.kill_set.add(e); + } +} + +impl<E:Idx> AllSets<E> { + pub fn bits_per_block(&self) -> usize { self.bits_per_block } + pub fn for_block(&mut self, block_idx: usize) -> BlockSets<E> { + let offset = self.words_per_block * block_idx; + let range = E::new(offset)..E::new(offset + self.words_per_block); + BlockSets { + on_entry: self.on_entry_sets.bits.range_mut(&range), + gen_set: self.gen_sets.bits.range_mut(&range), + kill_set: self.kill_sets.bits.range_mut(&range), + } + } + + fn lookup_set_for<'a>(&self, sets: &'a Bits<E>, block_idx: usize) -> &'a IdxSet<E> { + let offset = self.words_per_block * block_idx; + let range = E::new(offset)..E::new(offset + self.words_per_block); + sets.bits.range(&range) + } + pub fn gen_set_for(&self, block_idx: usize) -> &IdxSet<E> { + self.lookup_set_for(&self.gen_sets, block_idx) + } + pub fn kill_set_for(&self, block_idx: usize) -> &IdxSet<E> { + self.lookup_set_for(&self.kill_sets, block_idx) + } + pub fn on_entry_set_for(&self, block_idx: usize) -> &IdxSet<E> { + self.lookup_set_for(&self.on_entry_sets, block_idx) + } +} + +/// Parameterization for the precise form of data flow that is used. +pub trait DataflowOperator: BitwiseOperator { + /// Specifies the initial value for each bit in the `on_entry` set + fn bottom_value() -> bool; +} + +pub trait BitDenotation { + /// Specifies what index type is used to access the bitvector. + type Idx: Idx; + + /// Specifies what, if any, separate context needs to be supplied for methods below. + type Ctxt; + + /// A name describing the dataflow analysis that this + /// BitDenotation is supporting. The name should be something + /// suitable for plugging in as part of a filename e.g. avoid + /// space-characters or other things that tend to look bad on a + /// file system, like slashes or periods. It is also better for + /// the name to be reasonably short, again because it will be + /// plugged into a filename. + fn name() -> &'static str; + + /// Size of each bitvector allocated for each block in the analysis. + fn bits_per_block(&self, &Self::Ctxt) -> usize; + + /// Mutates the block-sets (the flow sets for the given + /// basic block) according to the effects that have been + /// established *prior* to entering the start block. + /// + /// (For example, establishing the call arguments.) + /// + /// (Typically this should only modify `sets.on_entry`, since the + /// gen and kill sets should reflect the effects of *executing* + /// the start block itself.) + fn start_block_effect(&self, ctxt: &Self::Ctxt, sets: &mut BlockSets<Self::Idx>); + + /// Mutates the block-sets (the flow sets for the given + /// basic block) according to the effects of evaluating statement. + /// + /// This is used, in particular, for building up the + /// "transfer-function" represnting the overall-effect of the + /// block, represented via GEN and KILL sets. + /// + /// The statement is identified as `bb_data[idx_stmt]`, where + /// `bb_data` is the sequence of statements identifed by `bb` in + /// the MIR. + fn statement_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<Self::Idx>, + bb: repr::BasicBlock, + idx_stmt: usize); + + /// Mutates the block-sets (the flow sets for the given + /// basic block) according to the effects of evaluating + /// the terminator. + /// + /// This is used, in particular, for building up the + /// "transfer-function" represnting the overall-effect of the + /// block, represented via GEN and KILL sets. + /// + /// The effects applied here cannot depend on which branch the + /// terminator took. + fn terminator_effect(&self, + ctxt: &Self::Ctxt, + sets: &mut BlockSets<Self::Idx>, + bb: repr::BasicBlock, + idx_term: usize); + + /// Mutates the block-sets according to the (flow-dependent) + /// effect of a successful return from a Call terminator. + /// + /// If basic-block BB_x ends with a call-instruction that, upon + /// successful return, flows to BB_y, then this method will be + /// called on the exit flow-state of BB_x in order to set up the + /// entry flow-state of BB_y. + /// + /// This is used, in particular, as a special case during the + /// "propagate" loop where all of the basic blocks are repeatedly + /// visited. Since the effects of a Call terminator are + /// flow-dependent, the current MIR cannot encode them via just + /// GEN and KILL sets attached to the block, and so instead we add + /// this extra machinery to represent the flow-dependent effect. + /// + /// FIXME: Right now this is a bit of a wart in the API. It might + /// be better to represent this as an additional gen- and + /// kill-sets associated with each edge coming out of the basic + /// block. + fn propagate_call_return(&self, + ctxt: &Self::Ctxt, + in_out: &mut IdxSet<Self::Idx>, + call_bb: repr::BasicBlock, + dest_bb: repr::BasicBlock, + dest_lval: &repr::Lvalue); +} + +impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> + where D: BitDenotation + DataflowOperator +{ + pub fn new(_tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &'a Mir<'tcx>, + ctxt: &'a D::Ctxt, + denotation: D) -> Self { + let bits_per_block = denotation.bits_per_block(&ctxt); + let usize_bits = mem::size_of::<usize>() * 8; + let words_per_block = (bits_per_block + usize_bits - 1) / usize_bits; + + // (now rounded up to multiple of word size) + let bits_per_block = words_per_block * usize_bits; + + let num_blocks = mir.basic_blocks.len(); + let num_overall = num_blocks * bits_per_block; + + let zeroes = Bits::new(IdxSetBuf::new_empty(num_overall)); + let on_entry = Bits::new(if D::bottom_value() { + IdxSetBuf::new_filled(num_overall) + } else { + IdxSetBuf::new_empty(num_overall) + }); + + DataflowAnalysis { + ctxt: ctxt, + mir: mir, + flow_state: DataflowState { + sets: AllSets { + bits_per_block: bits_per_block, + words_per_block: words_per_block, + gen_sets: zeroes.clone(), + kill_sets: zeroes, + on_entry_sets: on_entry, + }, + operator: denotation, + }, + } + + } +} + +impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> + where D: BitDenotation + DataflowOperator +{ + /// Propagates the bits of `in_out` into all the successors of `bb`, + /// using bitwise operator denoted by `self.operator`. + /// + /// For most blocks, this is entirely uniform. However, for blocks + /// that end with a call terminator, the effect of the call on the + /// dataflow state may depend on whether the call returned + /// successfully or unwound. + /// + /// To reflect this, the `propagate_call_return` method of the + /// `BitDenotation` mutates `in_out` when propagating `in_out` via + /// a call terminator; such mutation is performed *last*, to + /// ensure its side-effects do not leak elsewhere (e.g. into + /// unwind target). + fn propagate_bits_into_graph_successors_of( + &mut self, + in_out: &mut IdxSet<D::Idx>, + changed: &mut bool, + (bb, bb_data): (repr::BasicBlock, &repr::BasicBlockData)) + { + match bb_data.terminator().kind { + repr::TerminatorKind::Return | + repr::TerminatorKind::Resume => {} + repr::TerminatorKind::Goto { ref target } | + repr::TerminatorKind::Drop { ref target, value: _, unwind: None } => { + self.propagate_bits_into_entry_set_for(in_out, changed, target); + } + repr::TerminatorKind::Drop { ref target, value: _, unwind: Some(ref unwind) } => { + self.propagate_bits_into_entry_set_for(in_out, changed, target); + self.propagate_bits_into_entry_set_for(in_out, changed, unwind); + } + repr::TerminatorKind::If { ref targets, .. } => { + self.propagate_bits_into_entry_set_for(in_out, changed, &targets.0); + self.propagate_bits_into_entry_set_for(in_out, changed, &targets.1); + } + repr::TerminatorKind::Switch { ref targets, .. } | + repr::TerminatorKind::SwitchInt { ref targets, .. } => { + for target in targets { + self.propagate_bits_into_entry_set_for(in_out, changed, target); + } + } + repr::TerminatorKind::Call { ref cleanup, ref destination, func: _, args: _ } => { + if let Some(ref unwind) = *cleanup { + self.propagate_bits_into_entry_set_for(in_out, changed, unwind); + } + if let Some((ref dest_lval, ref dest_bb)) = *destination { + // N.B.: This must be done *last*, after all other + // propagation, as documented in comment above. + self.flow_state.operator.propagate_call_return( + &self.ctxt, in_out, bb, *dest_bb, dest_lval); + self.propagate_bits_into_entry_set_for(in_out, changed, dest_bb); + } + } + } + } + + fn propagate_bits_into_entry_set_for(&mut self, + in_out: &IdxSet<D::Idx>, + changed: &mut bool, + bb: &repr::BasicBlock) { + let entry_set = self.flow_state.sets.for_block(bb.index()).on_entry; + let set_changed = bitwise(entry_set.words_mut(), + in_out.words(), + &self.flow_state.operator); + if set_changed { + *changed = true; + } + } +} diff --git a/src/librustc_borrowck/borrowck/mir/dataflow/sanity_check.rs b/src/librustc_borrowck/borrowck/mir/dataflow/sanity_check.rs new file mode 100644 index 00000000000..74dc921b0bb --- /dev/null +++ b/src/librustc_borrowck/borrowck/mir/dataflow/sanity_check.rs @@ -0,0 +1,172 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use syntax::abi::{Abi}; +use syntax::ast; +use syntax::codemap::Span; + +use rustc::ty::{self, TyCtxt}; +use rustc::mir::repr::{self, Mir}; + +use super::super::gather_moves::{MovePathIndex}; +use super::super::MoveDataParamEnv; +use super::BitDenotation; +use super::DataflowResults; + +/// This function scans `mir` for all calls to the intrinsic +/// `rustc_peek` that have the expression form `rustc_peek(&expr)`. +/// +/// For each such call, determines what the dataflow bit-state is for +/// the L-value corresponding to `expr`; if the bit-state is a 1, then +/// that call to `rustc_peek` is ignored by the sanity check. If the +/// bit-state is a 0, then this pass emits a error message saying +/// "rustc_peek: bit not set". +/// +/// The intention is that one can write unit tests for dataflow by +/// putting code into a compile-fail test and using `rustc_peek` to +/// make observations about the results of dataflow static analyses. +/// +/// (If there are any calls to `rustc_peek` that do not match the +/// expression form above, then that emits an error as well, but those +/// errors are not intended to be used for unit tests.) +pub fn sanity_check_via_rustc_peek<'a, 'tcx, O>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + id: ast::NodeId, + _attributes: &[ast::Attribute], + flow_ctxt: &O::Ctxt, + results: &DataflowResults<O>) + where O: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>, Idx=MovePathIndex> +{ + debug!("sanity_check_via_rustc_peek id: {:?}", id); + // FIXME: this is not DRY. Figure out way to abstract this and + // `dataflow::build_sets`. (But note it is doing non-standard + // stuff, so such generalization may not be realistic.) + + let blocks = mir.all_basic_blocks(); + 'next_block: for bb in blocks { + each_block(tcx, mir, flow_ctxt, results, bb); + } +} + +fn each_block<'a, 'tcx, O>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + ctxt: &O::Ctxt, + results: &DataflowResults<O>, + bb: repr::BasicBlock) where + O: BitDenotation<Ctxt=MoveDataParamEnv<'tcx>, Idx=MovePathIndex> +{ + let move_data = &ctxt.move_data; + let bb_data = mir.basic_block_data(bb); + let &repr::BasicBlockData { ref statements, + ref terminator, + is_cleanup: _ } = bb_data; + + let (args, span) = match is_rustc_peek(tcx, terminator) { + Some(args_and_span) => args_and_span, + None => return, + }; + assert!(args.len() == 1); + let peek_arg_lval = match args[0] { + repr::Operand::Consume(ref lval @ repr::Lvalue::Temp(_)) => { + lval + } + repr::Operand::Consume(_) | + repr::Operand::Constant(_) => { + tcx.sess.diagnostic().span_err( + span, "dataflow::sanity_check cannot feed a non-temp to rustc_peek."); + return; + } + }; + + let mut entry = results.0.sets.on_entry_set_for(bb.index()).to_owned(); + let mut gen = results.0.sets.gen_set_for(bb.index()).to_owned(); + let mut kill = results.0.sets.kill_set_for(bb.index()).to_owned(); + + // Emulate effect of all statements in the block up to (but not + // including) the borrow within `peek_arg_lval`. Do *not* include + // call to `peek_arg_lval` itself (since we are peeking the state + // of the argument at time immediate preceding Call to + // `rustc_peek`). + + let mut sets = super::BlockSets { on_entry: &mut entry, + gen_set: &mut gen, + kill_set: &mut kill }; + + for (j, stmt) in statements.iter().enumerate() { + debug!("rustc_peek: ({:?},{}) {:?}", bb, j, stmt); + let (lvalue, rvalue) = match stmt.kind { + repr::StatementKind::Assign(ref lvalue, ref rvalue) => { + (lvalue, rvalue) + } + }; + + if lvalue == peek_arg_lval { + if let repr::Rvalue::Ref(_, + repr::BorrowKind::Shared, + ref peeking_at_lval) = *rvalue { + // Okay, our search is over. + let peek_mpi = move_data.rev_lookup.find(peeking_at_lval); + let bit_state = sets.on_entry.contains(&peek_mpi); + debug!("rustc_peek({:?} = &{:?}) bit_state: {}", + lvalue, peeking_at_lval, bit_state); + if !bit_state { + tcx.sess.span_err(span, &format!("rustc_peek: bit not set")); + } + return; + } else { + // Our search should have been over, but the input + // does not match expectations of `rustc_peek` for + // this sanity_check. + let msg = &format!("rustc_peek: argument expression \ + must be immediate borrow of form `&expr`"); + tcx.sess.span_err(span, msg); + } + } + + let lhs_mpi = move_data.rev_lookup.find(lvalue); + + debug!("rustc_peek: computing effect on lvalue: {:?} ({:?}) in stmt: {:?}", + lvalue, lhs_mpi, stmt); + // reset GEN and KILL sets before emulating their effect. + for e in sets.gen_set.words_mut() { *e = 0; } + for e in sets.kill_set.words_mut() { *e = 0; } + results.0.operator.statement_effect(ctxt, &mut sets, bb, j); + sets.on_entry.union(sets.gen_set); + sets.on_entry.subtract(sets.kill_set); + } + + tcx.sess.span_err(span, &format!("rustc_peek: MIR did not match \ + anticipated pattern; note that \ + rustc_peek expects input of \ + form `&expr`")); +} + +fn is_rustc_peek<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + terminator: &'a Option<repr::Terminator<'tcx>>) + -> Option<(&'a [repr::Operand<'tcx>], Span)> { + if let Some(repr::Terminator { ref kind, span, .. }) = *terminator { + if let repr::TerminatorKind::Call { func: ref oper, ref args, .. } = *kind + { + if let repr::Operand::Constant(ref func) = *oper + { + if let ty::TyFnDef(def_id, _, &ty::BareFnTy { abi, .. }) = func.ty.sty + { + let name = tcx.item_name(def_id); + if abi == Abi::RustIntrinsic || abi == Abi::PlatformIntrinsic { + if name.as_str() == "rustc_peek" { + return Some((args, span)); + } + } + } + } + } + } + return None; +} diff --git a/src/librustc_borrowck/borrowck/mir/gather_moves.rs b/src/librustc_borrowck/borrowck/mir/gather_moves.rs index bf3d671bdb5..48511cd5ebc 100644 --- a/src/librustc_borrowck/borrowck/mir/gather_moves.rs +++ b/src/librustc_borrowck/borrowck/mir/gather_moves.rs @@ -9,7 +9,7 @@ // except according to those terms. -use rustc::ty::TyCtxt; +use rustc::ty::{FnOutput, TyCtxt}; use rustc::mir::repr::*; use rustc::util::nodemap::FnvHashMap; @@ -19,8 +19,8 @@ use std::fmt; use std::iter; use std::ops::Index; -use super::dataflow::BitDenotation; use super::abs_domain::{AbstractElem, Lift}; +use indexed_set::{Idx}; // This submodule holds some newtype'd Index wrappers that are using // NonZero to ensure that Option<Index> occupies only a single word. @@ -29,17 +29,21 @@ use super::abs_domain::{AbstractElem, Lift}; // (which is likely to yield a subtle off-by-one error). mod indexes { use core::nonzero::NonZero; + use indexed_set::Idx; macro_rules! new_index { ($Index:ident) => { - #[derive(Copy, Clone, PartialEq, Eq, Debug)] + #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)] pub struct $Index(NonZero<usize>); impl $Index { - pub fn new(idx: usize) -> Self { + } + + impl Idx for $Index { + fn new(idx: usize) -> Self { unsafe { $Index(NonZero::new(idx + 1)) } } - pub fn idx(&self) -> usize { + fn idx(&self) -> usize { *self.0 - 1 } } @@ -56,6 +60,12 @@ mod indexes { pub use self::indexes::MovePathIndex; pub use self::indexes::MoveOutIndex; +impl self::indexes::MoveOutIndex { + pub fn move_path_index(&self, move_data: &MoveData) -> MovePathIndex { + move_data.moves[self.idx()].path + } +} + /// `MovePath` is a canonicalized representation of a path that is /// moved or assigned to. /// @@ -125,6 +135,7 @@ impl<'tcx> fmt::Debug for MovePath<'tcx> { } } +#[derive(Debug)] pub struct MoveData<'tcx> { pub move_paths: MovePathData<'tcx>, pub moves: Vec<MoveOut>, @@ -133,6 +144,7 @@ pub struct MoveData<'tcx> { pub rev_lookup: MovePathLookup<'tcx>, } +#[derive(Debug)] pub struct LocMap { /// Location-indexed (BasicBlock for outer index, index within BB /// for inner index) map to list of MoveOutIndex's. @@ -153,6 +165,7 @@ impl Index<Location> for LocMap { } } +#[derive(Debug)] pub struct PathMap { /// Path-indexed map to list of MoveOutIndex's. /// @@ -187,7 +200,7 @@ impl fmt::Debug for MoveOut { } } -#[derive(Copy, Clone)] +#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)] pub struct Location { /// block where action is located pub block: BasicBlock, @@ -202,10 +215,15 @@ impl fmt::Debug for Location { } } +#[derive(Debug)] pub struct MovePathData<'tcx> { move_paths: Vec<MovePath<'tcx>>, } +impl<'tcx> MovePathData<'tcx> { + pub fn len(&self) -> usize { self.move_paths.len() } +} + impl<'tcx> Index<MovePathIndex> for MovePathData<'tcx> { type Output = MovePath<'tcx>; fn index(&self, i: MovePathIndex) -> &MovePath<'tcx> { @@ -224,6 +242,7 @@ struct MovePathDataBuilder<'a, 'tcx: 'a> { } /// Tables mapping from an l-value to its MovePathIndex. +#[derive(Debug)] pub struct MovePathLookup<'tcx> { vars: MovePathInverseMap, temps: MovePathInverseMap, @@ -272,6 +291,7 @@ impl<T:Clone> FillTo for Vec<T> { #[derive(Clone, Debug)] enum LookupKind { Generate, Reuse } +#[derive(Clone, Debug)] struct Lookup<T>(LookupKind, T); impl Lookup<MovePathIndex> { @@ -419,7 +439,14 @@ impl<'a, 'tcx> MovePathDataBuilder<'a, 'tcx> { self.rev_lookup.lookup_proj(proj, base_index) } + fn create_move_path(&mut self, lval: &Lvalue<'tcx>) { + // Create MovePath for `lval`, discarding returned index. + self.move_path_for(lval); + } + fn move_path_for(&mut self, lval: &Lvalue<'tcx>) -> MovePathIndex { + debug!("move_path_for({:?})", lval); + let lookup: Lookup<MovePathIndex> = self.lookup(lval); // `lookup` is either the previously assigned index or a @@ -491,7 +518,7 @@ impl<'a, 'tcx> MoveData<'tcx> { #[derive(Debug)] enum StmtKind { Use, Repeat, Cast, BinaryOp, UnaryOp, Box, - Aggregate, Drop, CallFn, CallArg, Return, + Aggregate, Drop, CallFn, CallArg, Return, If, } fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveData<'tcx> { @@ -511,6 +538,27 @@ fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveD rev_lookup: MovePathLookup::new(), }; + // Before we analyze the program text, we create the MovePath's + // for all of the vars, args, and temps. (This enforces a basic + // property that even if the MIR body doesn't contain any + // references to a var/arg/temp, it will still be a valid + // operation to lookup the MovePath associated with it.) + assert!(mir.var_decls.len() <= ::std::u32::MAX as usize); + assert!(mir.arg_decls.len() <= ::std::u32::MAX as usize); + assert!(mir.temp_decls.len() <= ::std::u32::MAX as usize); + for var_idx in 0..mir.var_decls.len() { + let path_idx = builder.move_path_for(&Lvalue::Var(var_idx as u32)); + path_map.fill_to(path_idx.idx()); + } + for arg_idx in 0..mir.arg_decls.len() { + let path_idx = builder.move_path_for(&Lvalue::Arg(arg_idx as u32)); + path_map.fill_to(path_idx.idx()); + } + for temp_idx in 0..mir.temp_decls.len() { + let path_idx = builder.move_path_for(&Lvalue::Temp(temp_idx as u32)); + path_map.fill_to(path_idx.idx()); + } + for bb in bbs { let loc_map_bb = &mut loc_map[bb.index()]; let bb_data = mir.basic_block_data(bb); @@ -521,7 +569,7 @@ fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveD debug_assert!(loc_map_bb.len() == len + 1); let mut bb_ctxt = BlockContext { - tcx: tcx, + _tcx: tcx, moves: &mut moves, builder: builder, path_map: &mut path_map, @@ -532,8 +580,12 @@ fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveD let source = Location { block: bb, index: i }; match stmt.kind { StatementKind::Assign(ref lval, ref rval) => { - // ensure MovePath created for `lval`. - bb_ctxt.builder.move_path_for(lval); + bb_ctxt.builder.create_move_path(lval); + + // Ensure that the path_map contains entries even + // if the lvalue is assigned and never read. + let assigned_path = bb_ctxt.builder.move_path_for(lval); + bb_ctxt.path_map.fill_to(assigned_path.idx()); match *rval { Rvalue::Use(ref operand) => { @@ -569,27 +621,45 @@ fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveD Rvalue::InlineAsm { .. } => {} Rvalue::Slice {..} => { - bug!("cannot move out of slice"); + // A slice pattern `x..` binds `x` to a + // reference; thus no move occurs. + // + // FIXME: I recall arielb1 questioning + // whether this is even a legal thing to + // have as an R-value. The particular + // example where I am seeing this arise is + // `TargetDataLayout::parse(&Session)` in + // `rustc::ty::layout`. + // + // this should be removed soon. + debug!("encountered Rvalue::Slice as RHS of Assign, source: {:?}", + source); } } } } } + debug!("gather_moves({:?})", bb_data.terminator()); match bb_data.terminator().kind { TerminatorKind::Goto { target: _ } | TerminatorKind::Resume => { } TerminatorKind::Return => { let source = Location { block: bb, index: bb_data.statements.len() }; - let lval = &Lvalue::ReturnPointer.deref(); - bb_ctxt.on_move_out_lval(SK::Return, lval, source); + if let FnOutput::FnConverging(_) = bb_ctxt.builder.mir.return_ty { + debug!("gather_moves Return on_move_out_lval return {:?}", source); + bb_ctxt.on_move_out_lval(SK::Return, &Lvalue::ReturnPointer, source); + } else { + debug!("gather_moves Return on_move_out_lval \ + assuming unreachable return {:?}", source); + } } TerminatorKind::If { ref cond, targets: _ } => { - // The `cond` is always of (copyable) type `bool`, - // so there will never be anything to move. - let _ = cond; + let source = Location { block: bb, + index: bb_data.statements.len() }; + bb_ctxt.on_operand(SK::If, cond, source); } TerminatorKind::SwitchInt { switch_ty: _, values: _, targets: _, ref discr } | @@ -606,18 +676,23 @@ fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveD index: bb_data.statements.len() }; bb_ctxt.on_move_out_lval(SK::Drop, lval, source); } - TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => { let source = Location { block: bb, index: bb_data.statements.len() }; bb_ctxt.on_operand(SK::CallFn, func, source); for arg in args { + debug!("gather_moves Call on_operand {:?} {:?}", arg, source); bb_ctxt.on_operand(SK::CallArg, arg, source); } if let Some((ref destination, _bb)) = *destination { - // Create MovePath for `destination`, then - // discard returned index. - bb_ctxt.builder.move_path_for(destination); + debug!("gather_moves Call create_move_path {:?} {:?}", destination, source); + + // Ensure that the path_map contains entries even + // if the lvalue is assigned and never read. + let assigned_path = bb_ctxt.builder.move_path_for(destination); + bb_ctxt.path_map.fill_to(assigned_path.idx()); + + bb_ctxt.builder.create_move_path(destination); } } } @@ -635,7 +710,6 @@ fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveD // // well you know, lets actually try just asserting that the path map *is* complete. assert_eq!(path_map.len(), builder.pre_move_paths.len()); - path_map.fill_to(builder.pre_move_paths.len() - 1); let pre_move_paths = builder.pre_move_paths; let move_paths: Vec<_> = pre_move_paths.into_iter() @@ -667,7 +741,7 @@ fn gather_moves<'a, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> MoveD } struct BlockContext<'b, 'a: 'b, 'tcx: 'a> { - tcx: TyCtxt<'b, 'tcx, 'tcx>, + _tcx: TyCtxt<'b, 'tcx, 'tcx>, moves: &'b mut Vec<MoveOut>, builder: MovePathDataBuilder<'a, 'tcx>, path_map: &'b mut Vec<Vec<MoveOutIndex>>, @@ -679,25 +753,6 @@ impl<'b, 'a: 'b, 'tcx: 'a> BlockContext<'b, 'a, 'tcx> { stmt_kind: StmtKind, lval: &Lvalue<'tcx>, source: Location) { - let tcx = self.tcx; - let lval_ty = self.builder.mir.lvalue_ty(tcx, lval); - - // FIXME: does lvalue_ty ever return TyError, or is it - // guaranteed to always return non-Infer/non-Error values? - - // This code is just trying to avoid creating a MoveOut - // entry for values that do not need move semantics. - // - // type_contents is imprecise (may claim needs drop for - // types that in fact have no destructor). But that is - // still usable for our purposes here. - let consumed = lval_ty.to_ty(tcx).type_contents(tcx).needs_drop(tcx); - - if !consumed { - debug!("ctxt: {:?} no consume of lval: {:?} of type {:?}", - stmt_kind, lval, lval_ty); - return; - } let i = source.index; let index = MoveOutIndex::new(self.moves.len()); @@ -732,13 +787,3 @@ impl<'b, 'a: 'b, 'tcx: 'a> BlockContext<'b, 'a, 'tcx> { } } } - -impl<'tcx> BitDenotation for MoveData<'tcx>{ - type Bit = MoveOut; - fn bits_per_block(&self) -> usize { - self.moves.len() - } - fn interpret(&self, idx: usize) -> &Self::Bit { - &self.moves[idx] - } -} diff --git a/src/librustc_borrowck/borrowck/mir/graphviz.rs b/src/librustc_borrowck/borrowck/mir/graphviz.rs deleted file mode 100644 index 460c71dee3d..00000000000 --- a/src/librustc_borrowck/borrowck/mir/graphviz.rs +++ /dev/null @@ -1,232 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! Hook into libgraphviz for rendering dataflow graphs for MIR. - -use rustc::mir::repr::{BasicBlock, Mir}; - -use dot; -use dot::IntoCow; - -use std::fs::File; -use std::io; -use std::io::prelude::*; - -use super::MirBorrowckCtxt; -use bitslice::bits_to_string; -use super::gather_moves::MoveOut; - -struct Graph<'c, 'b:'c, 'a:'b, 'tcx:'a> { mbcx: &'c MirBorrowckCtxt<'b, 'a, 'tcx>, - context: &'b str } - -pub fn print_borrowck_graph_to(mbcx: &MirBorrowckCtxt, - context: &str, - path: &str) -> io::Result<()> { - let g = Graph { mbcx: mbcx, context: context }; - let mut v = Vec::new(); - dot::render(&g, &mut v)?; - println!("print_borrowck_graph_to path: {} context: {} node_id: {}", - path, context, mbcx.node_id); - File::create(path).and_then(|mut f| f.write_all(&v)) -} - -pub type Node = BasicBlock; - -#[derive(Copy, Clone, PartialEq, Eq, Debug)] -pub struct Edge { source: BasicBlock, index: usize } - -fn outgoing(mir: &Mir, bb: BasicBlock) -> Vec<Edge> { - let succ_len = mir.basic_block_data(bb).terminator().successors().len(); - (0..succ_len).map(|index| Edge { source: bb, index: index}).collect() -} - -impl<'c, 'b:'c, 'a:'b, 'tcx:'a> dot::Labeller<'c> for Graph<'c,'b,'a,'tcx> { - type Node = Node; - type Edge = Edge; - fn graph_id(&self) -> dot::Id { - dot::Id::new(format!("graph_for_node_{}_{}", - self.mbcx.node_id, - self.context)) - .unwrap() - } - - fn node_id(&self, n: &Node) -> dot::Id { - dot::Id::new(format!("bb_{}", n.index())) - .unwrap() - } - - fn node_label(&self, n: &Node) -> dot::LabelText { - // A standard MIR label, as generated by write_node_label, is - // presented in a single column in a table. - // - // The code below does a bunch of formatting work to format a - // node (i.e. MIR basic-block) label with extra - // dataflow-enriched information. In particular, the goal is - // to add extra columns that present the three dataflow - // bitvectors, and the data those bitvectors represent. - // - // It presents it in the following format (where I am - // presenting the table rendering via ASCII art, one line per - // row of the table, and a chunk size of 3 rather than 5): - // - // ------ ----------------------- ------------ -------------------- - // [e1, e3, e4] - // [e8, e9] "= ENTRY:" <ENTRY-BITS> - // ------ ----------------------- ------------ -------------------- - // Left - // Most - // Column - // Is - // Just - // Normal - // Series - // Of - // MIR - // Stmts - // ------ ----------------------- ------------ -------------------- - // [g1, g4, g5] "= GEN:" <GEN-BITS> - // ------ ----------------------- ------------ -------------------- - // "KILL:" <KILL-BITS> "=" [k1, k3, k8] - // [k9] - // ------ ----------------------- ------------ -------------------- - // - // (In addition, the added dataflow is rendered with a colored - // background just so it will stand out compared to the - // statements.) - let mut v = Vec::new(); - let i = n.index(); - let chunk_size = 5; - const BG_FLOWCONTENT: &'static str = r#"bgcolor="pink""#; - const ALIGN_RIGHT: &'static str = r#"align="right""#; - const FACE_MONOSPACE: &'static str = r#"FACE="Courier""#; - fn chunked_present_left<W:io::Write>(w: &mut W, - interpreted: &[&MoveOut], - chunk_size: usize) - -> io::Result<()> - { - // This function may emit a sequence of <tr>'s, but it - // always finishes with an (unfinished) - // <tr><td></td><td> - // - // Thus, after being called, one should finish both the - // pending <td> as well as the <tr> itself. - let mut seen_one = false; - for c in interpreted.chunks(chunk_size) { - if seen_one { - // if not the first row, finish off the previous row - write!(w, "</td><td></td><td></td></tr>")?; - } - write!(w, "<tr><td></td><td {bg} {align}>{objs:?}", - bg = BG_FLOWCONTENT, - align = ALIGN_RIGHT, - objs = c)?; - seen_one = true; - } - if !seen_one { - write!(w, "<tr><td></td><td {bg} {align}>[]", - bg = BG_FLOWCONTENT, - align = ALIGN_RIGHT)?; - } - Ok(()) - } - ::rustc_mir::graphviz::write_node_label( - *n, self.mbcx.mir, &mut v, 4, - |w| { - let flow = &self.mbcx.flow_state; - let entry = flow.interpret_set(flow.sets.on_entry_set_for(i)); - chunked_present_left(w, &entry[..], chunk_size)?; - write!(w, "= ENTRY:</td><td {bg}><FONT {face}>{entrybits:?}</FONT></td>\ - <td></td></tr>", - bg = BG_FLOWCONTENT, - face = FACE_MONOSPACE, - entrybits=bits_to_string(flow.sets.on_entry_set_for(i), - flow.sets.bytes_per_block())) - }, - |w| { - let flow = &self.mbcx.flow_state; - let gen = flow.interpret_set( flow.sets.gen_set_for(i)); - let kill = flow.interpret_set(flow.sets.kill_set_for(i)); - chunked_present_left(w, &gen[..], chunk_size)?; - write!(w, " = GEN:</td><td {bg}><FONT {face}>{genbits:?}</FONT></td>\ - <td></td></tr>", - bg = BG_FLOWCONTENT, - face = FACE_MONOSPACE, - genbits=bits_to_string( flow.sets.gen_set_for(i), - flow.sets.bytes_per_block()))?; - write!(w, "<tr><td></td><td {bg} {align}>KILL:</td>\ - <td {bg}><FONT {face}>{killbits:?}</FONT></td>", - bg = BG_FLOWCONTENT, - align = ALIGN_RIGHT, - face = FACE_MONOSPACE, - killbits=bits_to_string(flow.sets.kill_set_for(i), - flow.sets.bytes_per_block()))?; - - // (chunked_present_right) - let mut seen_one = false; - for k in kill.chunks(chunk_size) { - if !seen_one { - // continuation of row; this is fourth <td> - write!(w, "<td {bg}>= {kill:?}</td></tr>", - bg = BG_FLOWCONTENT, - kill=k)?; - } else { - // new row, with indent of three <td>'s - write!(w, "<tr><td></td><td></td><td></td><td {bg}>{kill:?}</td></tr>", - bg = BG_FLOWCONTENT, - kill=k)?; - } - seen_one = true; - } - if !seen_one { - write!(w, "<td {bg}>= []</td></tr>", - bg = BG_FLOWCONTENT)?; - } - - Ok(()) - }) - .unwrap(); - dot::LabelText::html(String::from_utf8(v).unwrap()) - } - - fn node_shape(&self, _n: &Node) -> Option<dot::LabelText> { - Some(dot::LabelText::label("none")) - } -} - -impl<'c, 'b:'c, 'a:'b, 'tcx:'a> dot::GraphWalk<'c> for Graph<'c,'b,'a,'tcx> { - type Node = Node; - type Edge = Edge; - fn nodes(&self) -> dot::Nodes<Node> { - self.mbcx.mir.all_basic_blocks().into_cow() - } - - fn edges(&self) -> dot::Edges<Edge> { - let mir = self.mbcx.mir; - let blocks = self.mbcx.mir.all_basic_blocks(); - // base initial capacity on assumption every block has at - // least one outgoing edge (Which should be true for all - // blocks but one, the exit-block). - let mut edges = Vec::with_capacity(blocks.len()); - for bb in blocks { - let outgoing = outgoing(mir, bb); - edges.extend(outgoing.into_iter()); - } - edges.into_cow() - } - - fn source(&self, edge: &Edge) -> Node { - edge.source - } - - fn target(&self, edge: &Edge) -> Node { - let mir = self.mbcx.mir; - mir.basic_block_data(edge.source).terminator().successors()[edge.index] - } -} diff --git a/src/librustc_borrowck/borrowck/mir/mod.rs b/src/librustc_borrowck/borrowck/mir/mod.rs index bec5ae03d3d..1b9d08bade7 100644 --- a/src/librustc_borrowck/borrowck/mir/mod.rs +++ b/src/librustc_borrowck/borrowck/mir/mod.rs @@ -10,24 +10,53 @@ use borrowck::BorrowckCtxt; -use syntax::ast; -use syntax::codemap::Span; +use syntax::ast::{self, MetaItem}; +use syntax::attr::AttrMetaMethods; +use syntax::codemap::{Span, DUMMY_SP}; +use syntax::ptr::P; use rustc::hir; use rustc::hir::intravisit::{FnKind}; +use rustc::mir::repr; use rustc::mir::repr::{BasicBlock, BasicBlockData, Mir, Statement, Terminator}; +use rustc::session::Session; +use rustc::ty::{self, TyCtxt}; mod abs_domain; mod dataflow; mod gather_moves; -mod graphviz; +// mod graphviz; -use self::dataflow::{Dataflow, DataflowState}; -use self::gather_moves::{MoveData}; +use self::dataflow::{BitDenotation}; +use self::dataflow::{DataflowOperator}; +use self::dataflow::{Dataflow, DataflowAnalysis, DataflowResults}; +use self::dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals}; +use self::dataflow::{DefinitelyInitializedLvals}; +use self::gather_moves::{MoveData, MovePathIndex, Location}; +use self::gather_moves::{MovePathContent}; -pub fn borrowck_mir<'b, 'a: 'b, 'tcx: 'a>( - bcx: &'b mut BorrowckCtxt<'a, 'tcx>, +fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<P<MetaItem>> { + for attr in attrs { + if attr.check_name("rustc_mir") { + let items = attr.meta_item_list(); + for item in items.iter().flat_map(|l| l.iter()) { + if item.check_name(name) { + return Some(item.clone()) + } + } + } + } + return None; +} + +pub struct MoveDataParamEnv<'tcx> { + move_data: MoveData<'tcx>, + param_env: ty::ParameterEnvironment<'tcx>, +} + +pub fn borrowck_mir<'a, 'tcx: 'a>( + bcx: &mut BorrowckCtxt<'a, 'tcx>, fk: FnKind, _decl: &hir::FnDecl, mir: &'a Mir<'tcx>, @@ -45,29 +74,106 @@ pub fn borrowck_mir<'b, 'a: 'b, 'tcx: 'a>( } } + let tcx = bcx.tcx; + + let move_data = MoveData::gather_moves(mir, tcx); + let param_env = ty::ParameterEnvironment::for_item(tcx, id); + let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env }; + let flow_inits = + do_dataflow(tcx, mir, id, attributes, &mdpe, MaybeInitializedLvals::new(tcx, mir)); + let flow_uninits = + do_dataflow(tcx, mir, id, attributes, &mdpe, MaybeUninitializedLvals::new(tcx, mir)); + let flow_def_inits = + do_dataflow(tcx, mir, id, attributes, &mdpe, DefinitelyInitializedLvals::new(tcx, mir)); + + if has_rustc_mir_with(attributes, "rustc_peek_maybe_init").is_some() { + dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &mdpe, &flow_inits); + } + if has_rustc_mir_with(attributes, "rustc_peek_maybe_uninit").is_some() { + dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &mdpe, &flow_uninits); + } + if has_rustc_mir_with(attributes, "rustc_peek_definite_init").is_some() { + dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &mdpe, &flow_def_inits); + } + + if has_rustc_mir_with(attributes, "stop_after_dataflow").is_some() { + bcx.tcx.sess.fatal("stop_after_dataflow ended compilation"); + } + let mut mbcx = MirBorrowckCtxt { - flow_state: DataflowState::new_move_analysis(mir, bcx.tcx), bcx: bcx, mir: mir, node_id: id, - attributes: attributes, + move_data: mdpe.move_data, + flow_inits: flow_inits, + flow_uninits: flow_uninits, }; for bb in mir.all_basic_blocks() { mbcx.process_basic_block(bb); } - mbcx.dataflow(); - debug!("borrowck_mir done"); } +fn do_dataflow<'a, 'tcx, BD>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + node_id: ast::NodeId, + attributes: &[ast::Attribute], + ctxt: &BD::Ctxt, + bd: BD) -> DataflowResults<BD> + where BD: BitDenotation<Idx=MovePathIndex, Ctxt=MoveDataParamEnv<'tcx>> + DataflowOperator +{ + use syntax::attr::AttrMetaMethods; + + let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> { + if let Some(item) = has_rustc_mir_with(attrs, name) { + if let Some(s) = item.value_str() { + return Some(s.to_string()) + } else { + sess.span_err( + item.span, + &format!("{} attribute requires a path", item.name())); + return None; + } + } + return None; + }; + + let print_preflow_to = + name_found(tcx.sess, attributes, "borrowck_graphviz_preflow"); + let print_postflow_to = + name_found(tcx.sess, attributes, "borrowck_graphviz_postflow"); + + let mut mbcx = MirBorrowckCtxtPreDataflow { + node_id: node_id, + print_preflow_to: print_preflow_to, + print_postflow_to: print_postflow_to, + flow_state: DataflowAnalysis::new(tcx, mir, ctxt, bd), + }; + + mbcx.dataflow(|ctxt, i| &ctxt.move_data.move_paths[i]); + mbcx.flow_state.results() +} + + +pub struct MirBorrowckCtxtPreDataflow<'a, 'tcx: 'a, BD> + where BD: BitDenotation, BD::Ctxt: 'a +{ + node_id: ast::NodeId, + flow_state: DataflowAnalysis<'a, 'tcx, BD>, + print_preflow_to: Option<String>, + print_postflow_to: Option<String>, +} + +#[allow(dead_code)] pub struct MirBorrowckCtxt<'b, 'a: 'b, 'tcx: 'a> { bcx: &'b mut BorrowckCtxt<'a, 'tcx>, mir: &'b Mir<'tcx>, node_id: ast::NodeId, - attributes: &'b [ast::Attribute], - flow_state: DataflowState<MoveData<'tcx>>, + move_data: MoveData<'tcx>, + flow_inits: DataflowResults<MaybeInitializedLvals<'a, 'tcx>>, + flow_uninits: DataflowResults<MaybeUninitializedLvals<'a, 'tcx>> } impl<'b, 'a: 'b, 'tcx: 'a> MirBorrowckCtxt<'b, 'a, 'tcx> { @@ -89,3 +195,129 @@ impl<'b, 'a: 'b, 'tcx: 'a> MirBorrowckCtxt<'b, 'a, 'tcx> { debug!("MirBorrowckCtxt::process_terminator({:?}, {:?})", bb, term); } } + +#[derive(Debug, PartialEq, Eq, Copy, Clone)] +enum DropFlagState { + Present, // i.e. initialized + Absent, // i.e. deinitialized or "moved" +} + +fn on_all_children_bits<'a, 'tcx, F>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + move_data: &MoveData<'tcx>, + move_path_index: MovePathIndex, + mut each_child: F) + where F: FnMut(MovePathIndex) +{ + fn is_terminal_path<'a, 'tcx>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + move_data: &MoveData<'tcx>, + path: MovePathIndex) -> bool + { + match move_data.move_paths[path].content { + MovePathContent::Lvalue(ref lvalue) => { + match mir.lvalue_ty(tcx, lvalue).to_ty(tcx).sty { + // don't trace paths past arrays, slices, and + // pointers. They can only be accessed while + // their parents are initialized. + // + // FIXME: we have to do something for moving + // slice patterns. + ty::TyArray(..) | ty::TySlice(..) | + ty::TyRef(..) | ty::TyRawPtr(..) => true, + _ => false + } + } + _ => true + } + } + + fn on_all_children_bits<'a, 'tcx, F>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + move_data: &MoveData<'tcx>, + move_path_index: MovePathIndex, + each_child: &mut F) + where F: FnMut(MovePathIndex) + { + each_child(move_path_index); + + if is_terminal_path(tcx, mir, move_data, move_path_index) { + return + } + + let mut next_child_index = move_data.move_paths[move_path_index].first_child; + while let Some(child_index) = next_child_index { + on_all_children_bits(tcx, mir, move_data, child_index, each_child); + next_child_index = move_data.move_paths[child_index].next_sibling; + } + } + on_all_children_bits(tcx, mir, move_data, move_path_index, &mut each_child); +} + +fn drop_flag_effects_for_function_entry<'a, 'tcx, F>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + ctxt: &MoveDataParamEnv<'tcx>, + mut callback: F) + where F: FnMut(MovePathIndex, DropFlagState) +{ + let move_data = &ctxt.move_data; + for i in 0..(mir.arg_decls.len() as u32) { + let lvalue = repr::Lvalue::Arg(i); + let move_path_index = move_data.rev_lookup.find(&lvalue); + on_all_children_bits(tcx, mir, move_data, + move_path_index, + |moi| callback(moi, DropFlagState::Present)); + } +} + +fn drop_flag_effects_for_location<'a, 'tcx, F>( + tcx: TyCtxt<'a, 'tcx, 'tcx>, + mir: &Mir<'tcx>, + ctxt: &MoveDataParamEnv<'tcx>, + loc: Location, + mut callback: F) + where F: FnMut(MovePathIndex, DropFlagState) +{ + let move_data = &ctxt.move_data; + let param_env = &ctxt.param_env; + debug!("drop_flag_effects_for_location({:?})", loc); + + // first, move out of the RHS + for mi in &move_data.loc_map[loc] { + let path = mi.move_path_index(move_data); + debug!("moving out of path {:?}", move_data.move_paths[path]); + + // don't move out of non-Copy things + if let MovePathContent::Lvalue(ref lvalue) = move_data.move_paths[path].content { + let ty = mir.lvalue_ty(tcx, lvalue).to_ty(tcx); + if !ty.moves_by_default(tcx, param_env, DUMMY_SP) { + continue; + } + } + + on_all_children_bits(tcx, mir, move_data, + path, + |moi| callback(moi, DropFlagState::Absent)) + } + + let bb = mir.basic_block_data(loc.block); + match bb.statements.get(loc.index) { + Some(stmt) => match stmt.kind { + repr::StatementKind::Assign(ref lvalue, _) => { + debug!("drop_flag_effects: assignment {:?}", stmt); + on_all_children_bits(tcx, mir, move_data, + move_data.rev_lookup.find(lvalue), + |moi| callback(moi, DropFlagState::Present)) + } + }, + None => { + // terminator - no move-ins except for function return edge + let term = bb.terminator(); + debug!("drop_flag_effects: terminator {:?}", term); + } + } +} diff --git a/src/librustc_borrowck/indexed_set.rs b/src/librustc_borrowck/indexed_set.rs new file mode 100644 index 00000000000..3fee1dbc056 --- /dev/null +++ b/src/librustc_borrowck/indexed_set.rs @@ -0,0 +1,165 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// FIXME: move this to `rustc_data_structures` + +use std::fmt; +use std::marker::PhantomData; +use std::mem; +use std::ops::{Deref, DerefMut, Range}; +use bitslice::{BitSlice, Word}; +use bitslice::{bitwise, Union, Subtract}; + +/// Represents some newtyped `usize` wrapper. +/// +/// (purpose: avoid mixing indexes for different bitvector domains.) +pub trait Idx: 'static { + fn new(usize) -> Self; + fn idx(&self) -> usize; +} + +/// Represents a set (or packed family of sets), of some element type +/// E, where each E is identified by some unique index type `T`. +/// +/// In other words, `T` is the type used to index into the bitvector +/// this type uses to represent the set of object it holds. +pub struct IdxSetBuf<T: Idx> { + _pd: PhantomData<fn(&T)>, + bits: Vec<Word>, +} + +impl<T: Idx> Clone for IdxSetBuf<T> { + fn clone(&self) -> Self { + IdxSetBuf { _pd: PhantomData, bits: self.bits.clone() } + } +} + +// pnkfelix wants to have this be `IdxSet<T>([Word]) and then pass +// around `&mut IdxSet<T>` or `&IdxSet<T>`. +// +// WARNING: Mapping a `&IdxSetBuf<T>` to `&IdxSet<T>` (at least today) +// requires a transmute relying on representation guarantees that may +// not hold in the future. + +/// Represents a set (or packed family of sets), of some element type +/// E, where each E is identified by some unique index type `T`. +/// +/// In other words, `T` is the type used to index into the bitslice +/// this type uses to represent the set of object it holds. +pub struct IdxSet<T: Idx> { + _pd: PhantomData<fn(&T)>, + bits: [Word], +} + +impl<T: Idx> fmt::Debug for IdxSetBuf<T> { + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) } +} + +impl<T: Idx> fmt::Debug for IdxSet<T> { + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) } +} + +impl<T: Idx> IdxSetBuf<T> { + fn new(init: Word, universe_size: usize) -> Self { + let bits_per_word = mem::size_of::<Word>() * 8; + let num_words = (universe_size + (bits_per_word - 1)) / bits_per_word; + IdxSetBuf { + _pd: Default::default(), + bits: vec![init; num_words], + } + } + + /// Creates set holding every element whose index falls in range 0..universe_size. + pub fn new_filled(universe_size: usize) -> Self { + Self::new(!0, universe_size) + } + + /// Creates set holding no elements. + pub fn new_empty(universe_size: usize) -> Self { + Self::new(0, universe_size) + } +} + +impl<T: Idx> IdxSet<T> { + unsafe fn from_slice(s: &[Word]) -> &Self { + mem::transmute(s) // (see above WARNING) + } + + unsafe fn from_slice_mut(s: &mut [Word]) -> &mut Self { + mem::transmute(s) // (see above WARNING) + } +} + +impl<T: Idx> Deref for IdxSetBuf<T> { + type Target = IdxSet<T>; + fn deref(&self) -> &IdxSet<T> { + unsafe { IdxSet::from_slice(&self.bits[..]) } + } +} + +impl<T: Idx> DerefMut for IdxSetBuf<T> { + fn deref_mut(&mut self) -> &mut IdxSet<T> { + unsafe { IdxSet::from_slice_mut(&mut self.bits[..]) } + } +} + +impl<T: Idx> IdxSet<T> { + pub fn to_owned(&self) -> IdxSetBuf<T> { + IdxSetBuf { + _pd: Default::default(), + bits: self.bits.to_owned(), + } + } + + /// Removes `elem` from the set `self`; returns true iff this changed `self`. + pub fn remove(&mut self, elem: &T) -> bool { + self.bits.clear_bit(elem.idx()) + } + + /// Adds `elem` to the set `self`; returns true iff this changed `self`. + pub fn add(&mut self, elem: &T) -> bool { + self.bits.set_bit(elem.idx()) + } + + pub fn range(&self, elems: &Range<T>) -> &Self { + let elems = elems.start.idx()..elems.end.idx(); + unsafe { Self::from_slice(&self.bits[elems]) } + } + + pub fn range_mut(&mut self, elems: &Range<T>) -> &mut Self { + let elems = elems.start.idx()..elems.end.idx(); + unsafe { Self::from_slice_mut(&mut self.bits[elems]) } + } + + /// Returns true iff set `self` contains `elem`. + pub fn contains(&self, elem: &T) -> bool { + self.bits.get_bit(elem.idx()) + } + + pub fn words(&self) -> &[Word] { + &self.bits[..] + } + + pub fn words_mut(&mut self) -> &mut [Word] { + &mut self.bits[..] + } + + pub fn clone_from(&mut self, other: &IdxSet<T>) { + self.words_mut().clone_from_slice(other.words()); + } + + pub fn union(&mut self, other: &IdxSet<T>) -> bool { + bitwise(self.words_mut(), other.words(), &Union) + } + + pub fn subtract(&mut self, other: &IdxSet<T>) -> bool { + bitwise(self.words_mut(), other.words(), &Subtract) + } +} diff --git a/src/librustc_borrowck/lib.rs b/src/librustc_borrowck/lib.rs index e38677de662..9d7e05ed9fa 100644 --- a/src/librustc_borrowck/lib.rs +++ b/src/librustc_borrowck/lib.rs @@ -47,6 +47,7 @@ pub mod diagnostics; mod borrowck; mod bitslice; +mod indexed_set; pub mod graphviz; diff --git a/src/librustc_mir/pretty.rs b/src/librustc_mir/pretty.rs index fb29cbd5fa8..a6bbd55ffa7 100644 --- a/src/librustc_mir/pretty.rs +++ b/src/librustc_mir/pretty.rs @@ -106,12 +106,9 @@ enum Annotation { ExitScope(ScopeId), } -pub fn write_mir_fn<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, - src: MirSource, - mir: &Mir<'tcx>, - w: &mut Write, - auxiliary: Option<&ScopeAuxiliaryVec>) - -> io::Result<()> { +fn scope_entry_exit_annotations(auxiliary: Option<&ScopeAuxiliaryVec>) + -> FnvHashMap<Location, Vec<Annotation>> +{ // compute scope/entry exit annotations let mut annotations = FnvHashMap(); if let Some(auxiliary) = auxiliary { @@ -129,7 +126,16 @@ pub fn write_mir_fn<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, } } } + return annotations; +} +pub fn write_mir_fn<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, + src: MirSource, + mir: &Mir<'tcx>, + w: &mut Write, + auxiliary: Option<&ScopeAuxiliaryVec>) + -> io::Result<()> { + let annotations = scope_entry_exit_annotations(auxiliary); write_mir_intro(tcx, src, mir, w)?; for block in mir.all_basic_blocks() { write_basic_block(tcx, block, mir, w, &annotations)?; @@ -270,6 +276,14 @@ fn write_mir_intro<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir: &Mir, w: &mut Write) -> io::Result<()> { + write_mir_sig(tcx, src, mir, w)?; + writeln!(w, " {{")?; + write_mir_decls(tcx, mir, w) +} + +fn write_mir_sig(tcx: TyCtxt, src: MirSource, mir: &Mir, w: &mut Write) + -> io::Result<()> +{ match src { MirSource::Fn(_) => write!(w, "fn")?, MirSource::Const(_) => write!(w, "const")?, @@ -295,16 +309,18 @@ fn write_mir_intro<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, // fn return type. match mir.return_ty { - ty::FnOutput::FnConverging(ty) => write!(w, "{}", ty)?, - ty::FnOutput::FnDiverging => write!(w, "!")?, + ty::FnOutput::FnConverging(ty) => write!(w, "{}", ty), + ty::FnOutput::FnDiverging => write!(w, "!"), } } else { assert!(mir.arg_decls.is_empty()); - write!(w, ": {} =", mir.return_ty.unwrap())?; + write!(w, ": {} =", mir.return_ty.unwrap()) } +} - writeln!(w, " {{")?; - +fn write_mir_decls(tcx: TyCtxt, mir: &Mir, w: &mut Write) + -> io::Result<()> +{ // User variable types (including the user's name in a comment). for (i, var) in mir.var_decls.iter().enumerate() { let mut_str = if var.mutability == Mutability::Mut { diff --git a/src/librustc_typeck/check/intrinsic.rs b/src/librustc_typeck/check/intrinsic.rs index c02139140ae..f120e38630b 100644 --- a/src/librustc_typeck/check/intrinsic.rs +++ b/src/librustc_typeck/check/intrinsic.rs @@ -117,6 +117,7 @@ pub fn check_intrinsic_type(ccx: &CrateCtxt, it: &hir::ForeignItem) { param(ccx, 0)) ], ccx.tcx.types.usize) } + "rustc_peek" => (1, vec![param(ccx, 0)], param(ccx, 0)), "init" | "init_dropped" => (1, Vec::new(), param(ccx, 0)), "uninit" => (1, Vec::new(), param(ccx, 0)), "forget" => (1, vec!( param(ccx, 0) ), tcx.mk_nil()), diff --git a/src/test/compile-fail/mir-dataflow/README.md b/src/test/compile-fail/mir-dataflow/README.md new file mode 100644 index 00000000000..a3ab14b23c7 --- /dev/null +++ b/src/test/compile-fail/mir-dataflow/README.md @@ -0,0 +1,53 @@ +This directory contains unit tests for the MIR-based dataflow +analysis. + +These unit tests check the dataflow analysis by embedding calls to a +special `rustc_peek` intrinsic within the code, in tandem with an +attribute `#[rustc_mir(rustc_peek_maybe_init)]` (\*). With that +attribute in place, `rustc_peek` calls are a signal to the compiler to +lookup the computed dataflow state for the Lvalue corresponding to the +argument expression being fed to `rustc_peek`. If the dataflow state +for that Lvalue is a 1-bit at that point in the control flow, then no +error is emitted by the compiler at that point; if it is a 0-bit, then +that invocation of `rustc_peek` will emit an error with the message +"rustc_peek: bit not set". + +(\*): Or `#[rustc_mir(rustc_peek_maybe_uninit)]`, and perhaps other +variants in the future. + +The end effect is that one can write unit tests for MIR dataflow that +perform simple-queries of the computed dataflow state, and the tests +should be able to be robust in the face of changes to how MIR is +represented or constructed. + +---- + +Sometimes understanding the dataflow results is difficult without +looking at the actual MIR control-flow graph being processed with the +corresponding GEN and KILL sets. + +For a graphviz-rendering with dataflow annotations, add the attribute +`#[rustc_mir(borrowck_graphviz_postflow="/path/to/suffix.dot")]` to +the function in question. (You can change the content of +`"suffix.dot"` to control the filenames used for the output). This +will generate a separate file for each dataflow analysis, adding a +prefix (corresponding to the name of the analysis) to the filename in +each generated output path. + + * For example, the above attribute will currently cause two files to + be generated: `/path/to/maybe_init_suffix.dot` and + `/path/to/maybe_uninit_suffix.dot`. + + * The generated `.dot` file shows both the computed dataflow results + on *entry* to each block, as well as the gen- and kill-sets that + were so-called "transfer functions" summarizing the effect of each + basic block. + + * (In addition to the `borrowck_graphviz_postflow` attribute-key + noted above, there is also `borrowck_graphviz_preflow`; it has the + same interface and generates the same set of files, but it renders + the dataflow state after building the gen- and kill-sets but + *before* running the dataflow analysis itself, so each entry-set is + just the initial default state for that dataflow analysis. This is + less useful for understanding the error message output in these + tests.) diff --git a/src/test/compile-fail/mir-dataflow/def-inits-1.rs b/src/test/compile-fail/mir-dataflow/def-inits-1.rs new file mode 100644 index 00000000000..a133ddc15f1 --- /dev/null +++ b/src/test/compile-fail/mir-dataflow/def-inits-1.rs @@ -0,0 +1,63 @@ +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// General test of maybe_uninits state computed by MIR dataflow. + +#![feature(rustc_attrs)] +#![feature(stmt_expr_attributes)] + +use std::intrinsics::rustc_peek; +use std::mem::{drop, replace}; + +struct S(i32); + +#[rustc_mir_borrowck] +#[rustc_mir(rustc_peek_definite_init,stop_after_dataflow)] +fn foo(test: bool, x: &mut S, y: S, mut z: S) -> S { + let ret; + // `ret` starts off uninitialized + unsafe { rustc_peek(&ret); } //~ ERROR rustc_peek: bit not set + + // All function formal parameters start off initialized. + + unsafe { rustc_peek(&x) }; + unsafe { rustc_peek(&y) }; + unsafe { rustc_peek(&z) }; + + ret = if test { + ::std::mem::replace(x, y) + } else { + z = y; + z + }; + + // `z` may be uninitialized here. + unsafe { rustc_peek(&z); } //~ ERROR rustc_peek: bit not set + + // `y` is definitely uninitialized here. + unsafe { rustc_peek(&y); } //~ ERROR rustc_peek: bit not set + + // `x` is still (definitely) initialized (replace above is a reborrow). + unsafe { rustc_peek(&x); } + + ::std::mem::drop(x); + + // `x` is *definitely* uninitialized here + unsafe { rustc_peek(&x); } //~ ERROR rustc_peek: bit not set + + // `ret` is now definitely initialized (via `if` above). + unsafe { rustc_peek(&ret); } + + ret +} +fn main() { + foo(true, &mut S(13), S(14), S(15)); + foo(false, &mut S(13), S(14), S(15)); +} diff --git a/src/test/compile-fail/mir-dataflow/inits-1.rs b/src/test/compile-fail/mir-dataflow/inits-1.rs new file mode 100644 index 00000000000..949688098f6 --- /dev/null +++ b/src/test/compile-fail/mir-dataflow/inits-1.rs @@ -0,0 +1,65 @@ +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// General test of maybe_inits state computed by MIR dataflow. + +#![feature(rustc_attrs)] +#![feature(stmt_expr_attributes)] + +use std::intrinsics::rustc_peek; +use std::mem::{drop, replace}; + +struct S(i32); + +#[rustc_mir_borrowck] +#[rustc_mir(rustc_peek_maybe_init,stop_after_dataflow)] +fn foo(test: bool, x: &mut S, y: S, mut z: S) -> S { + let ret; + // `ret` starts off uninitialized, so we get an error report here. + unsafe { rustc_peek(&ret); } //~ ERROR rustc_peek: bit not set + + // All function formal parameters start off initialized. + + unsafe { rustc_peek(&x) }; + unsafe { rustc_peek(&y) }; + unsafe { rustc_peek(&z) }; + + ret = if test { + ::std::mem::replace(x, y) + } else { + z = y; + z + }; + + + // `z` may be initialized here. + unsafe { rustc_peek(&z); } + + // `y` is definitely uninitialized here. + unsafe { rustc_peek(&y); } //~ ERROR rustc_peek: bit not set + + // `x` is still (definitely) initialized (replace above is a reborrow). + unsafe { rustc_peek(&x); } + + ::std::mem::drop(x); + + // `x` is *definitely* uninitialized here + unsafe { rustc_peek(&x); } //~ ERROR rustc_peek: bit not set + + // `ret` is now definitely initialized (via `if` above). + unsafe { rustc_peek(&ret); } + + ret +} + +fn main() { + foo(true, &mut S(13), S(14), S(15)); + foo(false, &mut S(13), S(14), S(15)); +} diff --git a/src/test/compile-fail/mir-dataflow/uninits-1.rs b/src/test/compile-fail/mir-dataflow/uninits-1.rs new file mode 100644 index 00000000000..c13daae24f3 --- /dev/null +++ b/src/test/compile-fail/mir-dataflow/uninits-1.rs @@ -0,0 +1,63 @@ +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// General test of maybe_uninits state computed by MIR dataflow. + +#![feature(rustc_attrs)] +#![feature(stmt_expr_attributes)] + +use std::intrinsics::rustc_peek; +use std::mem::{drop, replace}; + +struct S(i32); + +#[rustc_mir_borrowck] +#[rustc_mir(rustc_peek_maybe_uninit,stop_after_dataflow)] +fn foo(test: bool, x: &mut S, y: S, mut z: S) -> S { + let ret; + // `ret` starts off uninitialized + unsafe { rustc_peek(&ret); } + + // All function formal parameters start off initialized. + + unsafe { rustc_peek(&x) }; //~ ERROR rustc_peek: bit not set + unsafe { rustc_peek(&y) }; //~ ERROR rustc_peek: bit not set + unsafe { rustc_peek(&z) }; //~ ERROR rustc_peek: bit not set + + ret = if test { + ::std::mem::replace(x, y) + } else { + z = y; + z + }; + + // `z` may be uninitialized here. + unsafe { rustc_peek(&z); } + + // `y` is definitely uninitialized here. + unsafe { rustc_peek(&y); } + + // `x` is still (definitely) initialized (replace above is a reborrow). + unsafe { rustc_peek(&x); } //~ ERROR rustc_peek: bit not set + + ::std::mem::drop(x); + + // `x` is *definitely* uninitialized here + unsafe { rustc_peek(&x); } + + // `ret` is now definitely initialized (via `if` above). + unsafe { rustc_peek(&ret); } //~ ERROR rustc_peek: bit not set + + ret +} +fn main() { + foo(true, &mut S(13), S(14), S(15)); + foo(false, &mut S(13), S(14), S(15)); +} diff --git a/src/test/compile-fail/mir-dataflow/uninits-2.rs b/src/test/compile-fail/mir-dataflow/uninits-2.rs new file mode 100644 index 00000000000..e0bf4253449 --- /dev/null +++ b/src/test/compile-fail/mir-dataflow/uninits-2.rs @@ -0,0 +1,36 @@ +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// General test of maybe_uninits state computed by MIR dataflow. + +#![feature(rustc_attrs)] +#![feature(stmt_expr_attributes)] + +use std::intrinsics::rustc_peek; +use std::mem::{drop, replace}; + +struct S(i32); + +#[rustc_mir_borrowck] +#[rustc_mir(rustc_peek_maybe_uninit,stop_after_dataflow)] +fn foo(x: &mut S) { + // `x` is initialized here, so maybe-uninit bit is 0. + + unsafe { *rustc_peek(&x) }; //~ ERROR rustc_peek: bit not set + + ::std::mem::drop(x); + + // `x` definitely uninitialized here, so maybe-uninit bit is 1. + unsafe { rustc_peek(&x) }; +} +fn main() { + foo(&mut S(13)); + foo(&mut S(13)); +} |