diff options
| -rw-r--r-- | Cargo.lock | 4 | ||||
| -rw-r--r-- | src/librustc/infer/mod.rs | 9 | ||||
| -rw-r--r-- | src/librustc/infer/type_variable.rs | 8 | ||||
| -rw-r--r-- | src/librustc/traits/fulfill.rs | 55 | ||||
| -rw-r--r-- | src/librustc_data_structures/Cargo.toml | 2 | ||||
| -rw-r--r-- | src/librustc_data_structures/obligation_forest/mod.rs | 67 |
6 files changed, 85 insertions, 60 deletions
diff --git a/Cargo.lock b/Cargo.lock index 73ebc8b4616..106792b941e 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -917,9 +917,9 @@ dependencies = [ [[package]] name = "ena" -version = "0.13.0" +version = "0.13.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "3dc01d68e08ca384955a3aeba9217102ca1aa85b6e168639bf27739f1d749d87" +checksum = "8944dc8fa28ce4a38f778bd46bf7d923fe73eed5a439398507246c8e017e6f36" dependencies = [ "log", ] diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs index c5712cc9941..5d556485c15 100644 --- a/src/librustc/infer/mod.rs +++ b/src/librustc/infer/mod.rs @@ -1600,8 +1600,8 @@ impl<'a, 'tcx> ShallowResolver<'a, 'tcx> { // `resolver.shallow_resolve_changed(ty)` is equivalent to // `resolver.shallow_resolve(ty) != ty`, but more efficient. It's always - // inlined, despite being large, because it has a single call site that is - // extremely hot. + // inlined, despite being large, because it has only two call sites that + // are extremely hot. #[inline(always)] pub fn shallow_resolve_changed(&mut self, typ: Ty<'tcx>) -> bool { match typ.sty { @@ -1609,20 +1609,21 @@ impl<'a, 'tcx> ShallowResolver<'a, 'tcx> { use self::type_variable::TypeVariableValue; // See the comment in `shallow_resolve()`. - match self.infcx.type_variables.borrow_mut().probe(v) { + match self.infcx.type_variables.borrow_mut().inlined_probe(v) { TypeVariableValue::Known { value: t } => self.fold_ty(t) != typ, TypeVariableValue::Unknown { .. } => false, } } ty::Infer(ty::IntVar(v)) => { - match self.infcx.int_unification_table.borrow_mut().probe_value(v) { + match self.infcx.int_unification_table.borrow_mut().inlined_probe_value(v) { Some(v) => v.to_type(self.infcx.tcx) != typ, None => false, } } ty::Infer(ty::FloatVar(v)) => { + // Not `inlined_probe_value(v)` because this call site is colder. match self.infcx.float_unification_table.borrow_mut().probe_value(v) { Some(v) => v.to_type(self.infcx.tcx) != typ, None => false, diff --git a/src/librustc/infer/type_variable.rs b/src/librustc/infer/type_variable.rs index e30e86998a8..dd09e9a8f58 100644 --- a/src/librustc/infer/type_variable.rs +++ b/src/librustc/infer/type_variable.rs @@ -234,7 +234,13 @@ impl<'tcx> TypeVariableTable<'tcx> { /// Retrieves the type to which `vid` has been instantiated, if /// any. pub fn probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> { - self.eq_relations.probe_value(vid) + self.inlined_probe(vid) + } + + /// An always-inlined variant of `probe`, for very hot call sites. + #[inline(always)] + pub fn inlined_probe(&mut self, vid: ty::TyVid) -> TypeVariableValue<'tcx> { + self.eq_relations.inlined_probe_value(vid) } /// If `t` is a type-inference variable, and it has been diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs index 805727b6ce0..6c421e9df68 100644 --- a/src/librustc/traits/fulfill.rs +++ b/src/librustc/traits/fulfill.rs @@ -256,29 +256,46 @@ impl<'a, 'b, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'tcx> { &mut self, pending_obligation: &mut Self::Obligation, ) -> ProcessResult<Self::Obligation, Self::Error> { - // If we were stalled on some unresolved variables, first check - // whether any of them have been resolved; if not, don't bother - // doing more work yet - if !pending_obligation.stalled_on.is_empty() { - let mut changed = false; - // This `for` loop was once a call to `all()`, but this lower-level - // form was a perf win. See #64545 for details. - for &ty in &pending_obligation.stalled_on { - if ShallowResolver::new(self.selcx.infcx()).shallow_resolve_changed(ty) { - changed = true; - break; - } + // If we were stalled on some unresolved variables, first check whether + // any of them have been resolved; if not, don't bother doing more work + // yet. + let change = match pending_obligation.stalled_on.len() { + // Match arms are in order of frequency, which matters because this + // code is so hot. 1 and 0 dominate; 2+ is fairly rare. + 1 => { + let ty = pending_obligation.stalled_on[0]; + ShallowResolver::new(self.selcx.infcx()).shallow_resolve_changed(ty) + } + 0 => { + // In this case we haven't changed, but wish to make a change. + true } - if !changed { - debug!("process_predicate: pending obligation {:?} still stalled on {:?}", - self.selcx.infcx() - .resolve_vars_if_possible(&pending_obligation.obligation), - pending_obligation.stalled_on); - return ProcessResult::Unchanged; + _ => { + // This `for` loop was once a call to `all()`, but this lower-level + // form was a perf win. See #64545 for details. + (|| { + for &ty in &pending_obligation.stalled_on { + if ShallowResolver::new(self.selcx.infcx()).shallow_resolve_changed(ty) { + return true; + } + } + false + })() } - pending_obligation.stalled_on = vec![]; + }; + + if !change { + debug!("process_predicate: pending obligation {:?} still stalled on {:?}", + self.selcx.infcx() + .resolve_vars_if_possible(&pending_obligation.obligation), + pending_obligation.stalled_on); + return ProcessResult::Unchanged; } + // This part of the code is much colder. + + pending_obligation.stalled_on.truncate(0); + let obligation = &mut pending_obligation.obligation; if obligation.predicate.has_infer_types() { diff --git a/src/librustc_data_structures/Cargo.toml b/src/librustc_data_structures/Cargo.toml index be9f79c83bb..ae3403cf0ce 100644 --- a/src/librustc_data_structures/Cargo.toml +++ b/src/librustc_data_structures/Cargo.toml @@ -10,7 +10,7 @@ path = "lib.rs" doctest = false [dependencies] -ena = "0.13" +ena = "0.13.1" indexmap = "1" log = "0.4" jobserver_crate = { version = "0.1.13", package = "jobserver" } diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs index 98ae1a58324..1c7109fe500 100644 --- a/src/librustc_data_structures/obligation_forest/mod.rs +++ b/src/librustc_data_structures/obligation_forest/mod.rs @@ -149,7 +149,7 @@ pub struct ObligationForest<O: ForestObligation> { /// A cache of the nodes in `nodes`, indexed by predicate. Unfortunately, /// its contents are not guaranteed to match those of `nodes`. See the /// comments in `process_obligation` for details. - waiting_cache: FxHashMap<O::Predicate, usize>, + active_cache: FxHashMap<O::Predicate, usize>, /// A scratch vector reused in various operations, to avoid allocating new /// vectors. @@ -278,7 +278,7 @@ impl<O: ForestObligation> ObligationForest<O> { ObligationForest { nodes: vec![], done_cache: Default::default(), - waiting_cache: Default::default(), + active_cache: Default::default(), scratch: RefCell::new(vec![]), obligation_tree_id_generator: (0..).map(ObligationTreeId), error_cache: Default::default(), @@ -303,15 +303,15 @@ impl<O: ForestObligation> ObligationForest<O> { return Ok(()); } - match self.waiting_cache.entry(obligation.as_predicate().clone()) { + match self.active_cache.entry(obligation.as_predicate().clone()) { Entry::Occupied(o) => { debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!", obligation, parent, o.get()); let node = &mut self.nodes[*o.get()]; if let Some(parent_index) = parent { - // If the node is already in `waiting_cache`, it has - // already had its chance to be marked with a parent. So if - // it's not already present, just dump `parent` into the + // If the node is already in `active_cache`, it has already + // had its chance to be marked with a parent. So if it's + // not already present, just dump `parent` into the // dependents as a non-parent. if !node.dependents.contains(&parent_index) { node.dependents.push(parent_index); @@ -355,10 +355,9 @@ impl<O: ForestObligation> ObligationForest<O> { let mut errors = vec![]; for (index, node) in self.nodes.iter().enumerate() { if let NodeState::Pending = node.state.get() { - let backtrace = self.error_at(index); errors.push(Error { error: error.clone(), - backtrace, + backtrace: self.error_at(index), }); } } @@ -406,8 +405,8 @@ impl<O: ForestObligation> ObligationForest<O> { // `processor.process_obligation` can modify the predicate within // `node.obligation`, and that predicate is the key used for - // `self.waiting_cache`. This means that `self.waiting_cache` can - // get out of sync with `nodes`. It's not very common, but it does + // `self.active_cache`. This means that `self.active_cache` can get + // out of sync with `nodes`. It's not very common, but it does // happen, and code in `compress` has to allow for it. let result = match node.state.get() { NodeState::Pending => processor.process_obligation(&mut node.obligation), @@ -439,10 +438,9 @@ impl<O: ForestObligation> ObligationForest<O> { } ProcessResult::Error(err) => { stalled = false; - let backtrace = self.error_at(index); errors.push(Error { error: err, - backtrace, + backtrace: self.error_at(index), }); } } @@ -484,13 +482,16 @@ impl<O: ForestObligation> ObligationForest<O> { debug!("process_cycles()"); for (index, node) in self.nodes.iter().enumerate() { - // For rustc-benchmarks/inflate-0.1.0 this state test is extremely - // hot and the state is almost always `Pending` or `Waiting`. It's - // a win to handle the no-op cases immediately to avoid the cost of - // the function call. + // For some benchmarks this state test is extremely + // hot. It's a win to handle the no-op cases immediately to avoid + // the cost of the function call. match node.state.get() { - NodeState::Waiting | NodeState::Pending | NodeState::Done | NodeState::Error => {}, - _ => self.find_cycles_from_node(&mut stack, processor, index), + // Match arms are in order of frequency. Pending, Success and + // Waiting dominate; the others are rare. + NodeState::Pending => {}, + NodeState::Success => self.find_cycles_from_node(&mut stack, processor, index), + NodeState::Waiting | NodeState::Done | NodeState::Error => {}, + NodeState::OnDfsStack => self.find_cycles_from_node(&mut stack, processor, index), } } @@ -506,8 +507,8 @@ impl<O: ForestObligation> ObligationForest<O> { let node = &self.nodes[index]; match node.state.get() { NodeState::OnDfsStack => { - let index = stack.iter().rposition(|&n| n == index).unwrap(); - processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)), + let rpos = stack.iter().rposition(|&n| n == index).unwrap(); + processor.process_backedge(stack[rpos..].iter().map(GetObligation(&self.nodes)), PhantomData); } NodeState::Success => { @@ -636,11 +637,11 @@ impl<O: ForestObligation> ObligationForest<O> { } NodeState::Done => { // This lookup can fail because the contents of - // `self.waiting_cache` is not guaranteed to match those of + // `self.active_cache` is not guaranteed to match those of // `self.nodes`. See the comment in `process_obligation` // for more details. - if let Some((predicate, _)) = self.waiting_cache - .remove_entry(node.obligation.as_predicate()) + if let Some((predicate, _)) = + self.active_cache.remove_entry(node.obligation.as_predicate()) { self.done_cache.insert(predicate); } else { @@ -653,7 +654,7 @@ impl<O: ForestObligation> ObligationForest<O> { // We *intentionally* remove the node from the cache at this point. Otherwise // tests must come up with a different type on every type error they // check against. - self.waiting_cache.remove(node.obligation.as_predicate()); + self.active_cache.remove(node.obligation.as_predicate()); node_rewrites[index] = nodes_len; dead_nodes += 1; self.insert_into_error_cache(index); @@ -697,25 +698,25 @@ impl<O: ForestObligation> ObligationForest<O> { let nodes_len = node_rewrites.len(); for node in &mut self.nodes { - let mut index = 0; - while index < node.dependents.len() { - let new_index = node_rewrites[node.dependents[index]]; + let mut i = 0; + while i < node.dependents.len() { + let new_index = node_rewrites[node.dependents[i]]; if new_index >= nodes_len { - node.dependents.swap_remove(index); - if index == 0 && node.has_parent { + node.dependents.swap_remove(i); + if i == 0 && node.has_parent { // We just removed the parent. node.has_parent = false; } } else { - node.dependents[index] = new_index; - index += 1; + node.dependents[i] = new_index; + i += 1; } } } - // This updating of `self.waiting_cache` is necessary because the + // This updating of `self.active_cache` is necessary because the // removal of nodes within `compress` can fail. See above. - self.waiting_cache.retain(|_predicate, index| { + self.active_cache.retain(|_predicate, index| { let new_index = node_rewrites[*index]; if new_index >= nodes_len { false |