diff options
Diffstat (limited to 'compiler/rustc_passes/src/liveness.rs')
| -rw-r--r-- | compiler/rustc_passes/src/liveness.rs | 254 |
1 files changed, 44 insertions, 210 deletions
diff --git a/compiler/rustc_passes/src/liveness.rs b/compiler/rustc_passes/src/liveness.rs index debb873beb9..a161ad16b8c 100644 --- a/compiler/rustc_passes/src/liveness.rs +++ b/compiler/rustc_passes/src/liveness.rs @@ -105,6 +105,8 @@ use std::io; use std::io::prelude::*; use std::rc::Rc; +mod rwu_table; + rustc_index::newtype_index! { pub struct Variable { DEBUG_FORMAT = "v({})", @@ -468,101 +470,6 @@ impl<'tcx> Visitor<'tcx> for IrMaps<'tcx> { // 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; @@ -575,7 +482,7 @@ struct Liveness<'a, '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 @@ -613,7 +520,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { 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(), @@ -652,61 +559,37 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { 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(()) @@ -718,11 +601,11 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { { 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]); } @@ -747,100 +630,57 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { 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 { @@ -906,7 +746,6 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { }; // 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 { @@ -916,10 +755,9 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { }) } - 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)); } @@ -1025,7 +863,6 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { // 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); @@ -1034,8 +871,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { body_succ, ); 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) } @@ -1146,7 +982,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { 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) } @@ -1174,7 +1010,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { }; // 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 { .. } @@ -1197,7 +1033,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { // 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, .. } @@ -1390,7 +1226,6 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { */ // 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); @@ -1402,8 +1237,7 @@ impl<'a, 'tcx> Liveness<'a, 'tcx> { 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)); } @@ -1454,7 +1288,7 @@ fn check_expr<'tcx>(this: &mut Liveness<'_, 'tcx>, expr: &'tcx Expr<'tcx>) { } 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 { @@ -1575,7 +1409,7 @@ impl<'tcx> Liveness<'_, 'tcx> { 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, @@ -1609,7 +1443,7 @@ impl<'tcx> Liveness<'_, 'tcx> { 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) }); @@ -1658,7 +1492,7 @@ impl<'tcx> Liveness<'_, 'tcx> { // {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( @@ -1725,7 +1559,7 @@ impl<'tcx> Liveness<'_, 'tcx> { } 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) }); |