use std::io::prelude::*;
use std::rc::Rc;
+mod rwu_table;
+
rustc_index::newtype_index! {
pub struct Variable {
DEBUG_FORMAT = "v({})",
// swap in a new set of IR maps for this body
let mut maps = IrMaps::new(self.tcx);
let hir_id = maps.tcx.hir().body_owner(body.id());
- let def_id = maps.tcx.hir().local_def_id(hir_id);
+ let local_def_id = maps.tcx.hir().local_def_id(hir_id);
+ let def_id = local_def_id.to_def_id();
// Don't run unused pass for #[derive()]
- if let Some(parent) = self.tcx.parent(def_id.to_def_id()) {
+ if let Some(parent) = self.tcx.parent(def_id) {
if let DefKind::Impl = self.tcx.def_kind(parent.expect_local()) {
if self.tcx.has_attr(parent, sym::automatically_derived) {
return;
}
}
- if let Some(upvars) = maps.tcx.upvars_mentioned(def_id) {
- for (&var_hir_id, _upvar) in upvars {
+ if let Some(captures) = maps.tcx.typeck(local_def_id).closure_captures.get(&def_id) {
+ for &var_hir_id in captures.keys() {
let var_name = maps.tcx.hir().name(var_hir_id);
maps.add_variable(Upvar(var_hir_id, var_name));
}
intravisit::walk_body(&mut maps, body);
// compute liveness
- let mut lsets = Liveness::new(&mut maps, def_id);
+ let mut lsets = Liveness::new(&mut maps, local_def_id);
let entry_ln = lsets.compute(&body, hir_id);
lsets.log_liveness(entry_ln, body.id().hir_id);
fn visit_arm(&mut self, arm: &'tcx hir::Arm<'tcx>) {
self.add_from_pat(&arm.pat);
+ if let Some(hir::Guard::IfLet(ref pat, _)) = arm.guard {
+ self.add_from_pat(pat);
+ }
intravisit::walk_arm(self, arm);
}
// construction site.
let mut call_caps = Vec::new();
let closure_def_id = self.tcx.hir().local_def_id(expr.hir_id);
- if let Some(upvars) = self.tcx.upvars_mentioned(closure_def_id) {
- call_caps.extend(upvars.iter().map(|(&var_id, upvar)| {
+ if let Some(captures) = self
+ .tcx
+ .typeck(closure_def_id)
+ .closure_captures
+ .get(&closure_def_id.to_def_id())
+ {
+ // If closure captures is Some, upvars_mentioned must also be Some
+ let upvars = self.tcx.upvars_mentioned(closure_def_id).unwrap();
+ call_caps.extend(captures.keys().map(|var_id| {
+ let upvar = upvars[var_id];
let upvar_ln = self.add_live_node(UpvarNode(upvar.span));
- CaptureInfo { ln: upvar_ln, var_hid: var_id }
+ CaptureInfo { ln: upvar_ln, var_hid: *var_id }
}));
}
self.set_captures(expr.hir_id, call_caps);
// Actually we compute just a bit more than just liveness, but we use
// the same basic propagation framework in all cases.
-#[derive(Clone, Copy)]
-struct RWU {
- reader: Option<LiveNode>,
- writer: Option<LiveNode>,
- used: bool,
-}
-
-/// Conceptually, this is like a `Vec<RWU>`. But the number of `RWU`s can get
-/// very large, so it uses a more compact representation that takes advantage
-/// of the fact that when the number of `RWU`s is large, most of them have an
-/// invalid reader and an invalid writer.
-struct RWUTable {
- /// Each entry in `packed_rwus` is either INV_INV_FALSE, INV_INV_TRUE, or
- /// an index into `unpacked_rwus`. In the common cases, this compacts the
- /// 65 bits of data into 32; in the uncommon cases, it expands the 65 bits
- /// in 96.
- ///
- /// More compact representations are possible -- e.g., use only 2 bits per
- /// packed `RWU` and make the secondary table a HashMap that maps from
- /// indices to `RWU`s -- but this one strikes a good balance between size
- /// and speed.
- packed_rwus: Vec<u32>,
- unpacked_rwus: Vec<RWU>,
-}
-
-// A constant representing `RWU { reader: None; writer: None; used: false }`.
-const INV_INV_FALSE: u32 = u32::MAX;
-
-// A constant representing `RWU { reader: None; writer: None; used: true }`.
-const INV_INV_TRUE: u32 = u32::MAX - 1;
-
-impl RWUTable {
- fn new(num_rwus: usize) -> RWUTable {
- Self { packed_rwus: vec![INV_INV_FALSE; num_rwus], unpacked_rwus: vec![] }
- }
-
- fn get(&self, idx: usize) -> RWU {
- let packed_rwu = self.packed_rwus[idx];
- match packed_rwu {
- INV_INV_FALSE => RWU { reader: None, writer: None, used: false },
- INV_INV_TRUE => RWU { reader: None, writer: None, used: true },
- _ => self.unpacked_rwus[packed_rwu as usize],
- }
- }
-
- fn get_reader(&self, idx: usize) -> Option<LiveNode> {
- let packed_rwu = self.packed_rwus[idx];
- match packed_rwu {
- INV_INV_FALSE | INV_INV_TRUE => None,
- _ => self.unpacked_rwus[packed_rwu as usize].reader,
- }
- }
-
- fn get_writer(&self, idx: usize) -> Option<LiveNode> {
- let packed_rwu = self.packed_rwus[idx];
- match packed_rwu {
- INV_INV_FALSE | INV_INV_TRUE => None,
- _ => self.unpacked_rwus[packed_rwu as usize].writer,
- }
- }
-
- fn get_used(&self, idx: usize) -> bool {
- let packed_rwu = self.packed_rwus[idx];
- match packed_rwu {
- INV_INV_FALSE => false,
- INV_INV_TRUE => true,
- _ => self.unpacked_rwus[packed_rwu as usize].used,
- }
- }
-
- #[inline]
- fn copy_packed(&mut self, dst_idx: usize, src_idx: usize) {
- self.packed_rwus[dst_idx] = self.packed_rwus[src_idx];
- }
-
- fn assign_unpacked(&mut self, idx: usize, rwu: RWU) {
- if rwu.reader == None && rwu.writer == None {
- // When we overwrite an indexing entry in `self.packed_rwus` with
- // `INV_INV_{TRUE,FALSE}` we don't remove the corresponding entry
- // from `self.unpacked_rwus`; it's not worth the effort, and we
- // can't have entries shifting around anyway.
- self.packed_rwus[idx] = if rwu.used { INV_INV_TRUE } else { INV_INV_FALSE }
- } else {
- // Add a new RWU to `unpacked_rwus` and make `packed_rwus[idx]`
- // point to it.
- self.packed_rwus[idx] = self.unpacked_rwus.len() as u32;
- self.unpacked_rwus.push(rwu);
- }
- }
-
- fn assign_inv_inv(&mut self, idx: usize) {
- self.packed_rwus[idx] = if self.get_used(idx) { INV_INV_TRUE } else { INV_INV_FALSE };
- }
-}
-
const ACC_READ: u32 = 1;
const ACC_WRITE: u32 = 2;
const ACC_USE: u32 = 4;
typeck_results: &'a ty::TypeckResults<'tcx>,
param_env: ty::ParamEnv<'tcx>,
upvars: Option<&'tcx FxIndexMap<hir::HirId, hir::Upvar>>,
+ closure_captures: Option<&'tcx FxIndexMap<hir::HirId, ty::UpvarId>>,
successors: IndexVec<LiveNode, Option<LiveNode>>,
- rwu_table: RWUTable,
+ rwu_table: rwu_table::RWUTable,
/// A live node representing a point of execution before closure entry &
/// after closure exit. Used to calculate liveness of captured variables
let typeck_results = ir.tcx.typeck(body_owner);
let param_env = ir.tcx.param_env(body_owner);
let upvars = ir.tcx.upvars_mentioned(body_owner);
+ let closure_captures = typeck_results.closure_captures.get(&body_owner.to_def_id());
let closure_ln = ir.add_live_node(ClosureNode);
let exit_ln = ir.add_live_node(ExitNode);
typeck_results,
param_env,
upvars,
+ closure_captures,
successors: IndexVec::from_elem_n(None, num_live_nodes),
- rwu_table: RWUTable::new(num_live_nodes * num_vars),
+ rwu_table: rwu_table::RWUTable::new(num_live_nodes, num_vars),
closure_ln,
exit_ln,
break_ln: Default::default(),
succ
}
- fn idx(&self, ln: LiveNode, var: Variable) -> usize {
- ln.index() * self.ir.var_kinds.len() + var.index()
- }
-
- fn live_on_entry(&self, ln: LiveNode, var: Variable) -> Option<LiveNodeKind> {
- if let Some(reader) = self.rwu_table.get_reader(self.idx(ln, var)) {
- Some(self.ir.lnks[reader])
- } else {
- None
- }
+ fn live_on_entry(&self, ln: LiveNode, var: Variable) -> bool {
+ self.rwu_table.get_reader(ln, var)
}
// Is this variable live on entry to any of its successor nodes?
- fn live_on_exit(&self, ln: LiveNode, var: Variable) -> Option<LiveNodeKind> {
+ fn live_on_exit(&self, ln: LiveNode, var: Variable) -> bool {
let successor = self.successors[ln].unwrap();
self.live_on_entry(successor, var)
}
fn used_on_entry(&self, ln: LiveNode, var: Variable) -> bool {
- self.rwu_table.get_used(self.idx(ln, var))
+ self.rwu_table.get_used(ln, var)
}
- fn assigned_on_entry(&self, ln: LiveNode, var: Variable) -> Option<LiveNodeKind> {
- if let Some(writer) = self.rwu_table.get_writer(self.idx(ln, var)) {
- Some(self.ir.lnks[writer])
- } else {
- None
- }
+ fn assigned_on_entry(&self, ln: LiveNode, var: Variable) -> bool {
+ self.rwu_table.get_writer(ln, var)
}
- fn assigned_on_exit(&self, ln: LiveNode, var: Variable) -> Option<LiveNodeKind> {
+ fn assigned_on_exit(&self, ln: LiveNode, var: Variable) -> bool {
let successor = self.successors[ln].unwrap();
self.assigned_on_entry(successor, var)
}
- fn indices2<F>(&mut self, ln: LiveNode, succ_ln: LiveNode, mut op: F)
- where
- F: FnMut(&mut Liveness<'a, 'tcx>, usize, usize),
- {
- let node_base_idx = self.idx(ln, Variable::from(0u32));
- let succ_base_idx = self.idx(succ_ln, Variable::from(0u32));
- for var_idx in 0..self.ir.var_kinds.len() {
- op(self, node_base_idx + var_idx, succ_base_idx + var_idx);
- }
- }
-
- fn write_vars<F>(&self, wr: &mut dyn Write, ln: LiveNode, mut test: F) -> io::Result<()>
+ fn write_vars<F>(&self, wr: &mut dyn Write, mut test: F) -> io::Result<()>
where
- F: FnMut(usize) -> bool,
+ F: FnMut(Variable) -> bool,
{
- let node_base_idx = self.idx(ln, Variable::from(0u32));
for var_idx in 0..self.ir.var_kinds.len() {
- let idx = node_base_idx + var_idx;
- if test(idx) {
- write!(wr, " {:?}", Variable::from(var_idx))?;
+ let var = Variable::from(var_idx);
+ if test(var) {
+ write!(wr, " {:?}", var)?;
}
}
Ok(())
{
let wr = &mut wr as &mut dyn Write;
write!(wr, "[{:?} of kind {:?} reads", ln, self.ir.lnks[ln]);
- self.write_vars(wr, ln, |idx| self.rwu_table.get_reader(idx).is_some());
+ self.write_vars(wr, |var| self.rwu_table.get_reader(ln, var));
write!(wr, " writes");
- self.write_vars(wr, ln, |idx| self.rwu_table.get_writer(idx).is_some());
+ self.write_vars(wr, |var| self.rwu_table.get_writer(ln, var));
write!(wr, " uses");
- self.write_vars(wr, ln, |idx| self.rwu_table.get_used(idx));
+ self.write_vars(wr, |var| self.rwu_table.get_used(ln, var));
write!(wr, " precedes {:?}]", self.successors[ln]);
}
self.successors[ln] = Some(succ_ln);
// It is not necessary to initialize the RWUs here because they are all
- // set to INV_INV_FALSE when they are created, and the sets only grow
- // during iterations.
+ // empty when created, and the sets only grow during iterations.
}
fn init_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) {
// more efficient version of init_empty() / merge_from_succ()
self.successors[ln] = Some(succ_ln);
-
- self.indices2(ln, succ_ln, |this, idx, succ_idx| {
- this.rwu_table.copy_packed(idx, succ_idx);
- });
+ self.rwu_table.copy(ln, succ_ln);
debug!("init_from_succ(ln={}, succ={})", self.ln_str(ln), self.ln_str(succ_ln));
}
- fn merge_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode, first_merge: bool) -> bool {
+ fn merge_from_succ(&mut self, ln: LiveNode, succ_ln: LiveNode) -> bool {
if ln == succ_ln {
return false;
}
- let mut any_changed = false;
- self.indices2(ln, succ_ln, |this, idx, succ_idx| {
- // This is a special case, pulled out from the code below, where we
- // don't have to do anything. It occurs about 60-70% of the time.
- if this.rwu_table.packed_rwus[succ_idx] == INV_INV_FALSE {
- return;
- }
-
- let mut changed = false;
- let mut rwu = this.rwu_table.get(idx);
- let succ_rwu = this.rwu_table.get(succ_idx);
- if succ_rwu.reader.is_some() && rwu.reader.is_none() {
- rwu.reader = succ_rwu.reader;
- changed = true
- }
-
- if succ_rwu.writer.is_some() && rwu.writer.is_none() {
- rwu.writer = succ_rwu.writer;
- changed = true
- }
-
- if succ_rwu.used && !rwu.used {
- rwu.used = true;
- changed = true;
- }
-
- if changed {
- this.rwu_table.assign_unpacked(idx, rwu);
- any_changed = true;
- }
- });
-
- debug!(
- "merge_from_succ(ln={:?}, succ={}, first_merge={}, changed={})",
- ln,
- self.ln_str(succ_ln),
- first_merge,
- any_changed
- );
- any_changed
+ let changed = self.rwu_table.union(ln, succ_ln);
+ debug!("merge_from_succ(ln={:?}, succ={}, changed={})", ln, self.ln_str(succ_ln), changed);
+ changed
}
// Indicates that a local variable was *defined*; we know that no
// uses of the variable can precede the definition (resolve checks
// this) so we just clear out all the data.
fn define(&mut self, writer: LiveNode, var: Variable) {
- let idx = self.idx(writer, var);
- self.rwu_table.assign_inv_inv(idx);
-
- debug!("{:?} defines {:?} (idx={}): {}", writer, var, idx, self.ln_str(writer));
+ let used = self.rwu_table.get_used(writer, var);
+ self.rwu_table.set(writer, var, rwu_table::RWU { reader: false, writer: false, used });
+ debug!("{:?} defines {:?}: {}", writer, var, self.ln_str(writer));
}
// Either read, write, or both depending on the acc bitset
fn acc(&mut self, ln: LiveNode, var: Variable, acc: u32) {
debug!("{:?} accesses[{:x}] {:?}: {}", ln, acc, var, self.ln_str(ln));
- let idx = self.idx(ln, var);
- let mut rwu = self.rwu_table.get(idx);
+ let mut rwu = self.rwu_table.get(ln, var);
if (acc & ACC_WRITE) != 0 {
- rwu.reader = None;
- rwu.writer = Some(ln);
+ rwu.reader = false;
+ rwu.writer = true;
}
// Important: if we both read/write, must do read second
// or else the write will override.
if (acc & ACC_READ) != 0 {
- rwu.reader = Some(ln);
+ rwu.reader = true;
}
if (acc & ACC_USE) != 0 {
rwu.used = true;
}
- self.rwu_table.assign_unpacked(idx, rwu);
+ self.rwu_table.set(ln, var, rwu);
}
fn compute(&mut self, body: &hir::Body<'_>, hir_id: HirId) -> LiveNode {
// if they are live on the entry to the closure, since only the closure
// itself can access them on subsequent calls.
- if let Some(upvars) = self.upvars {
+ if let Some(closure_captures) = self.closure_captures {
// Mark upvars captured by reference as used after closure exits.
- for (&var_hir_id, upvar) in upvars.iter().rev() {
- let upvar_id = ty::UpvarId {
- var_path: ty::UpvarPath { hir_id: var_hir_id },
- closure_expr_id: self.body_owner,
- };
- match self.typeck_results.upvar_capture(upvar_id) {
+ // Since closure_captures is Some, upvars must exists too.
+ let upvars = self.upvars.unwrap();
+ for (&var_hir_id, upvar_id) in closure_captures {
+ let upvar = upvars[&var_hir_id];
+ match self.typeck_results.upvar_capture(*upvar_id) {
ty::UpvarCapture::ByRef(_) => {
let var = self.variable(var_hir_id, upvar.span);
self.acc(self.exit_ln, var, ACC_READ | ACC_USE);
let succ = self.propagate_through_expr(&body.value, self.exit_ln);
- if self.upvars.is_none() {
+ if self.closure_captures.is_none() {
// Either not a closure, or closure without any captured variables.
// No need to determine liveness of captured variables, since there
// are none.
};
// Propagate through calls to the closure.
- let mut first_merge = true;
loop {
self.init_from_succ(self.closure_ln, succ);
for param in body.params {
})
}
- if !self.merge_from_succ(self.exit_ln, self.closure_ln, first_merge) {
+ if !self.merge_from_succ(self.exit_ln, self.closure_ln) {
break;
}
- first_merge = false;
assert_eq!(succ, self.propagate_through_expr(&body.value, self.exit_ln));
}
//
let ln = self.live_node(expr.hir_id, expr.span);
self.init_empty(ln, succ);
- let mut first_merge = true;
for arm in arms {
let body_succ = self.propagate_through_expr(&arm.body, succ);
- let guard_succ = self.propagate_through_opt_expr(
- arm.guard.as_ref().map(|hir::Guard::If(e)| *e),
- body_succ,
- );
+ let guard_succ = arm.guard.as_ref().map_or(body_succ, |g| match g {
+ hir::Guard::If(e) => self.propagate_through_expr(e, body_succ),
+ hir::Guard::IfLet(pat, e) => {
+ let let_bind = self.define_bindings_in_pat(pat, body_succ);
+ self.propagate_through_expr(e, let_bind)
+ }
+ });
let arm_succ = self.define_bindings_in_pat(&arm.pat, guard_succ);
- self.merge_from_succ(ln, arm_succ, first_merge);
- first_merge = false;
+ self.merge_from_succ(ln, arm_succ);
}
self.propagate_through_expr(&e, ln)
}
let ln = self.live_node(expr.hir_id, expr.span);
self.init_from_succ(ln, succ);
- self.merge_from_succ(ln, r_succ, false);
+ self.merge_from_succ(ln, r_succ);
self.propagate_through_expr(&l, ln)
}
};
// Do a first pass for writing outputs only
- for op in asm.operands.iter().rev() {
+ for (op, _op_sp) in asm.operands.iter().rev() {
match op {
hir::InlineAsmOperand::In { .. }
| hir::InlineAsmOperand::Const { .. }
// Then do a second pass for inputs
let mut succ = succ;
- for op in asm.operands.iter().rev() {
+ for (op, _op_sp) in asm.operands.iter().rev() {
match op {
hir::InlineAsmOperand::In { expr, .. }
| hir::InlineAsmOperand::Const { expr, .. }
acc: u32,
) -> LiveNode {
match path.res {
- Res::Local(hid) => self.access_var(hir_id, hid, succ, acc, path.span),
+ Res::Local(hid) => {
+ let in_upvars = self.upvars.map_or(false, |u| u.contains_key(&hid));
+ let in_captures = self.closure_captures.map_or(false, |c| c.contains_key(&hid));
+
+ match (in_upvars, in_captures) {
+ (false, _) | (true, true) => self.access_var(hir_id, hid, succ, acc, path.span),
+ (true, false) => {
+ // This case is possible when with RFC-2229, a wild pattern
+ // is used within a closure.
+ // eg: `let _ = x`. The closure doesn't capture x here,
+ // even though it's mentioned in the closure.
+ succ
+ }
+ }
+ }
_ => succ,
}
}
*/
// first iteration:
- let mut first_merge = true;
let ln = self.live_node(expr.hir_id, expr.span);
self.init_empty(ln, succ);
debug!("propagate_through_loop: using id for loop body {} {:?}", expr.hir_id, body);
let body_ln = self.propagate_through_block(body, ln);
// repeat until fixed point is reached:
- while self.merge_from_succ(ln, body_ln, first_merge) {
- first_merge = false;
+ while self.merge_from_succ(ln, body_ln) {
assert_eq!(body_ln, self.propagate_through_block(body, ln));
}
}
hir::ExprKind::InlineAsm(ref asm) => {
- for op in asm.operands {
+ for (op, _op_sp) in asm.operands {
match op {
hir::InlineAsmOperand::Out { expr, .. } => {
if let Some(expr) = expr {
}
fn warn_about_unused_upvars(&self, entry_ln: LiveNode) {
- let upvars = match self.upvars {
+ let closure_captures = match self.closure_captures {
None => return,
- Some(upvars) => upvars,
+ Some(closure_captures) => closure_captures,
};
- for (&var_hir_id, upvar) in upvars.iter() {
+
+ // If closure_captures is Some(), upvars must be Some() too.
+ let upvars = self.upvars.unwrap();
+ for &var_hir_id in closure_captures.keys() {
+ let upvar = upvars[&var_hir_id];
let var = self.variable(var_hir_id, upvar.span);
let upvar_id = ty::UpvarId {
var_path: ty::UpvarPath { hir_id: var_hir_id },
ty::UpvarCapture::ByRef(..) => continue,
};
if self.used_on_entry(entry_ln, var) {
- if self.live_on_entry(entry_ln, var).is_none() {
+ if !self.live_on_entry(entry_ln, var) {
if let Some(name) = self.should_warn(var) {
self.ir.tcx.struct_span_lint_hir(
lint::builtin::UNUSED_ASSIGNMENTS,
fn warn_about_unused_args(&self, body: &hir::Body<'_>, entry_ln: LiveNode) {
for p in body.params {
self.check_unused_vars_in_pat(&p.pat, Some(entry_ln), |spans, hir_id, ln, var| {
- if self.live_on_entry(ln, var).is_none() {
+ if !self.live_on_entry(ln, var) {
self.report_unsed_assign(hir_id, spans, var, |name| {
format!("value passed to `{}` is never read", name)
});
// {ret}`, there is only one node, so asking about
// assigned_on_exit() is not meaningful.
let is_assigned =
- if ln == self.exit_ln { false } else { self.assigned_on_exit(ln, var).is_some() };
+ if ln == self.exit_ln { false } else { self.assigned_on_exit(ln, var) };
if is_assigned {
self.ir.tcx.struct_span_lint_hir(
}
fn warn_about_dead_assign(&self, spans: Vec<Span>, hir_id: HirId, ln: LiveNode, var: Variable) {
- if self.live_on_exit(ln, var).is_none() {
+ if !self.live_on_exit(ln, var) {
self.report_unsed_assign(hir_id, spans, var, |name| {
format!("value assigned to `{}` is never read", name)
});