diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index a886c44..c5712cc 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -1562,11 +1562,7 @@
         ShallowResolver { infcx }
     }
 
-    // We have this force-inlined variant of `shallow_resolve` for the one
-    // callsite that is extremely hot. All other callsites use the normal
-    // variant.
-    #[inline(always)]
-    pub fn inlined_shallow_resolve(&mut self, typ: Ty<'tcx>) -> Ty<'tcx> {
+    pub fn shallow_resolve(&mut self, typ: Ty<'tcx>) -> Ty<'tcx> {
         match typ.sty {
             ty::Infer(ty::TyVar(v)) => {
                 // Not entirely obvious: if `typ` is a type variable,
@@ -1601,6 +1597,42 @@
             _ => typ,
         }
     }
+
+    // `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.
+    #[inline(always)]
+    pub fn shallow_resolve_changed(&mut self, typ: Ty<'tcx>) -> bool {
+        match typ.sty {
+            ty::Infer(ty::TyVar(v)) => {
+                use self::type_variable::TypeVariableValue;
+
+                // See the comment in `shallow_resolve()`.
+                match self.infcx.type_variables.borrow_mut().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) {
+                    Some(v) => v.to_type(self.infcx.tcx) != typ,
+                    None => false,
+                }
+            }
+
+            ty::Infer(ty::FloatVar(v)) => {
+                match self.infcx.float_unification_table.borrow_mut().probe_value(v) {
+                    Some(v) => v.to_type(self.infcx.tcx) != typ,
+                    None => false,
+                }
+            }
+
+            _ => false,
+        }
+    }
+
 }
 
 impl<'a, 'tcx> TypeFolder<'tcx> for ShallowResolver<'a, 'tcx> {
@@ -1609,7 +1641,7 @@
     }
 
     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
-        self.inlined_shallow_resolve(ty)
+        self.shallow_resolve(ty)
     }
 
     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index 4494c03..805727b 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -256,15 +256,20 @@
         &mut self,
         pending_obligation: &mut Self::Obligation,
     ) -> ProcessResult<Self::Obligation, Self::Error> {
-        // if we were stalled on some unresolved variables, first check
+        // 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() {
-            if pending_obligation.stalled_on.iter().all(|&ty| {
-                // Use the force-inlined variant of shallow_resolve() because this code is hot.
-                let resolved = ShallowResolver::new(self.selcx.infcx()).inlined_shallow_resolve(ty);
-                resolved == ty // nothing changed here
-            }) {
+            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 !changed {
                 debug!("process_predicate: pending obligation {:?} still stalled on {:?}",
                        self.selcx.infcx()
                            .resolve_vars_if_possible(&pending_obligation.obligation),
diff --git a/src/librustc_data_structures/obligation_forest/graphviz.rs b/src/librustc_data_structures/obligation_forest/graphviz.rs
index b2120b1..ddf89d9 100644
--- a/src/librustc_data_structures/obligation_forest/graphviz.rs
+++ b/src/librustc_data_structures/obligation_forest/graphviz.rs
@@ -74,9 +74,7 @@
             .flat_map(|i| {
                 let node = &self.nodes[i];
 
-                node.parent.iter()
-                    .chain(node.dependents.iter())
-                    .map(move |p| (p.index(), i))
+                node.dependents.iter().map(move |&d| (d, i))
             })
             .collect()
     }
diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index 189506b..98ae1a5 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -73,8 +73,6 @@
 //! aren't needed anymore.
 
 use crate::fx::{FxHashMap, FxHashSet};
-use crate::indexed_vec::Idx;
-use crate::newtype_index;
 
 use std::cell::{Cell, RefCell};
 use std::collections::hash_map::Entry;
@@ -87,10 +85,6 @@
 #[cfg(test)]
 mod tests;
 
-newtype_index! {
-    pub struct NodeIndex { .. }
-}
-
 pub trait ForestObligation : Clone + Debug {
     type Predicate : Clone + hash::Hash + Eq + Debug;
 
@@ -143,9 +137,10 @@
     /// At the end of processing, those nodes will be removed by a
     /// call to `compress`.
     ///
-    /// Ideally, this would be an `IndexVec<NodeIndex, Node<O>>`. But that is
-    /// slower, because this vector is accessed so often that the
-    /// `u32`-to-`usize` conversions required for accesses are significant.
+    /// `usize` indices are used here and throughout this module, rather than
+    /// `newtype_index!` indices, because this code is hot enough that the
+    /// `u32`-to-`usize` conversions that would be required are significant,
+    /// and space considerations are not important.
     nodes: Vec<Node<O>>,
 
     /// A cache of predicates that have been successfully completed.
@@ -154,7 +149,7 @@
     /// 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, NodeIndex>,
+    waiting_cache: FxHashMap<O::Predicate, usize>,
 
     /// A scratch vector reused in various operations, to avoid allocating new
     /// vectors.
@@ -177,20 +172,16 @@
     obligation: O,
     state: Cell<NodeState>,
 
-    /// The parent of a node - the original obligation of which it is a
-    /// subobligation. Except for error reporting, it is just like any member
-    /// of `dependents`.
-    ///
-    /// Unlike `ObligationForest::nodes`, this uses `NodeIndex` rather than
-    /// `usize` for the index, because keeping the size down is more important
-    /// than the cost of converting to a `usize` for indexing.
-    parent: Option<NodeIndex>,
-
     /// Obligations that depend on this obligation for their completion. They
     /// must all be in a non-pending state.
-    ///
-    /// This uses `NodeIndex` for the same reason as `parent`.
-    dependents: Vec<NodeIndex>,
+    dependents: Vec<usize>,
+
+    /// If true, dependents[0] points to a "parent" node, which requires
+    /// special treatment upon error but is otherwise treated the same.
+    /// (It would be more idiomatic to store the parent node in a separate
+    /// `Option<usize>` field, but that slows down the common case of
+    /// iterating over the parent and other descendants together.)
+    has_parent: bool,
 
     /// Identifier of the obligation tree to which this node belongs.
     obligation_tree_id: ObligationTreeId,
@@ -198,15 +189,20 @@
 
 impl<O> Node<O> {
     fn new(
-        parent: Option<NodeIndex>,
+        parent: Option<usize>,
         obligation: O,
         obligation_tree_id: ObligationTreeId
     ) -> Node<O> {
         Node {
             obligation,
             state: Cell::new(NodeState::Pending),
-            parent,
-            dependents: vec![],
+            dependents:
+                if let Some(parent_index) = parent {
+                    vec![parent_index]
+                } else {
+                    vec![]
+                },
+            has_parent: parent.is_some(),
             obligation_tree_id,
         }
     }
@@ -302,9 +298,7 @@
     }
 
     // Returns Err(()) if we already know this obligation failed.
-    fn register_obligation_at(&mut self, obligation: O, parent: Option<NodeIndex>)
-                              -> Result<(), ()>
-    {
+    fn register_obligation_at(&mut self, obligation: O, parent: Option<usize>) -> Result<(), ()> {
         if self.done_cache.contains(obligation.as_predicate()) {
             return Ok(());
         }
@@ -313,15 +307,13 @@
             Entry::Occupied(o) => {
                 debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!",
                        obligation, parent, o.get());
-                let node = &mut self.nodes[o.get().index()];
+                let node = &mut self.nodes[*o.get()];
                 if let Some(parent_index) = parent {
-                    // If the node is already in `waiting_cache`, it's already
-                    // been marked with a parent. (It's possible that parent
-                    // has been cleared by `apply_rewrites`, though.) So just
-                    // dump `parent` into `node.dependents`... unless it's
-                    // already in `node.dependents` or `node.parent`.
-                    if !node.dependents.contains(&parent_index) &&
-                       Some(parent_index) != node.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
+                    // dependents as a non-parent.
+                    if !node.dependents.contains(&parent_index) {
                         node.dependents.push(parent_index);
                     }
                 }
@@ -336,10 +328,8 @@
                        obligation, parent, self.nodes.len());
 
                 let obligation_tree_id = match parent {
-                    Some(parent_index) => {
-                        self.nodes[parent_index.index()].obligation_tree_id
-                    }
-                    None => self.obligation_tree_id_generator.next().unwrap()
+                    Some(parent_index) => self.nodes[parent_index].obligation_tree_id,
+                    None => self.obligation_tree_id_generator.next().unwrap(),
                 };
 
                 let already_failed =
@@ -352,7 +342,7 @@
                 if already_failed {
                     Err(())
                 } else {
-                    v.insert(NodeIndex::new(self.nodes.len()));
+                    v.insert(self.nodes.len());
                     self.nodes.push(Node::new(parent, obligation, obligation_tree_id));
                     Ok(())
                 }
@@ -363,9 +353,9 @@
     /// Converts all remaining obligations to the given error.
     pub fn to_errors<E: Clone>(&mut self, error: E) -> Vec<Error<O, E>> {
         let mut errors = vec![];
-        for (i, node) in self.nodes.iter().enumerate() {
+        for (index, node) in self.nodes.iter().enumerate() {
             if let NodeState::Pending = node.state.get() {
-                let backtrace = self.error_at(i);
+                let backtrace = self.error_at(index);
                 errors.push(Error {
                     error: error.clone(),
                     backtrace,
@@ -409,10 +399,10 @@
         let mut errors = vec![];
         let mut stalled = true;
 
-        for i in 0..self.nodes.len() {
-            let node = &mut self.nodes[i];
+        for index in 0..self.nodes.len() {
+            let node = &mut self.nodes[index];
 
-            debug!("process_obligations: node {} == {:?}", i, node);
+            debug!("process_obligations: node {} == {:?}", index, node);
 
             // `processor.process_obligation` can modify the predicate within
             // `node.obligation`, and that predicate is the key used for
@@ -424,7 +414,7 @@
                 _ => continue
             };
 
-            debug!("process_obligations: node {} got result {:?}", i, result);
+            debug!("process_obligations: node {} got result {:?}", index, result);
 
             match result {
                 ProcessResult::Unchanged => {
@@ -438,18 +428,18 @@
                     for child in children {
                         let st = self.register_obligation_at(
                             child,
-                            Some(NodeIndex::new(i))
+                            Some(index)
                         );
                         if let Err(()) = st {
                             // Error already reported - propagate it
                             // to our node.
-                            self.error_at(i);
+                            self.error_at(index);
                         }
                     }
                 }
                 ProcessResult::Error(err) => {
                     stalled = false;
-                    let backtrace = self.error_at(i);
+                    let backtrace = self.error_at(index);
                     errors.push(Error {
                         error: err,
                         backtrace,
@@ -493,14 +483,14 @@
 
         debug!("process_cycles()");
 
-        for (i, node) in self.nodes.iter().enumerate() {
+        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.
             match node.state.get() {
                 NodeState::Waiting | NodeState::Pending | NodeState::Done | NodeState::Error => {},
-                _ => self.find_cycles_from_node(&mut stack, processor, i),
+                _ => self.find_cycles_from_node(&mut stack, processor, index),
             }
         }
 
@@ -510,21 +500,21 @@
         self.scratch.replace(stack);
     }
 
-    fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, processor: &mut P, i: usize)
+    fn find_cycles_from_node<P>(&self, stack: &mut Vec<usize>, processor: &mut P, index: usize)
         where P: ObligationProcessor<Obligation=O>
     {
-        let node = &self.nodes[i];
+        let node = &self.nodes[index];
         match node.state.get() {
             NodeState::OnDfsStack => {
-                let i = stack.iter().rposition(|n| *n == i).unwrap();
-                processor.process_backedge(stack[i..].iter().map(GetObligation(&self.nodes)),
+                let index = stack.iter().rposition(|&n| n == index).unwrap();
+                processor.process_backedge(stack[index..].iter().map(GetObligation(&self.nodes)),
                                            PhantomData);
             }
             NodeState::Success => {
                 node.state.set(NodeState::OnDfsStack);
-                stack.push(i);
-                for index in node.parent.iter().chain(node.dependents.iter()) {
-                    self.find_cycles_from_node(stack, processor, index.index());
+                stack.push(index);
+                for &index in node.dependents.iter() {
+                    self.find_cycles_from_node(stack, processor, index);
                 }
                 stack.pop();
                 node.state.set(NodeState::Done);
@@ -541,33 +531,34 @@
 
     /// Returns a vector of obligations for `p` and all of its
     /// ancestors, putting them into the error state in the process.
-    fn error_at(&self, mut i: usize) -> Vec<O> {
+    fn error_at(&self, mut index: usize) -> Vec<O> {
         let mut error_stack = self.scratch.replace(vec![]);
         let mut trace = vec![];
 
         loop {
-            let node = &self.nodes[i];
+            let node = &self.nodes[index];
             node.state.set(NodeState::Error);
             trace.push(node.obligation.clone());
-            error_stack.extend(node.dependents.iter().map(|index| index.index()));
-
-            // Loop to the parent.
-            match node.parent {
-                Some(parent_index) => i = parent_index.index(),
-                None => break
+            if node.has_parent {
+                // The first dependent is the parent, which is treated
+                // specially.
+                error_stack.extend(node.dependents.iter().skip(1));
+                index = node.dependents[0];
+            } else {
+                // No parent; treat all dependents non-specially.
+                error_stack.extend(node.dependents.iter());
+                break;
             }
         }
 
-        while let Some(i) = error_stack.pop() {
-            let node = &self.nodes[i];
+        while let Some(index) = error_stack.pop() {
+            let node = &self.nodes[index];
             match node.state.get() {
                 NodeState::Error => continue,
                 _ => node.state.set(NodeState::Error),
             }
 
-            error_stack.extend(
-                node.parent.iter().chain(node.dependents.iter()).map(|index| index.index())
-            );
+            error_stack.extend(node.dependents.iter());
         }
 
         self.scratch.replace(error_stack);
@@ -577,8 +568,8 @@
     // This always-inlined function is for the hot call site.
     #[inline(always)]
     fn inlined_mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
-        for dependent in node.parent.iter().chain(node.dependents.iter()) {
-            self.mark_as_waiting_from(&self.nodes[dependent.index()]);
+        for &index in node.dependents.iter() {
+            self.mark_as_waiting_from(&self.nodes[index]);
         }
     }
 
@@ -631,16 +622,16 @@
         // Now move all popped nodes to the end. Try to keep the order.
         //
         // LOOP INVARIANT:
-        //     self.nodes[0..i - dead_nodes] are the first remaining nodes
-        //     self.nodes[i - dead_nodes..i] are all dead
-        //     self.nodes[i..] are unchanged
-        for i in 0..self.nodes.len() {
-            let node = &self.nodes[i];
+        //     self.nodes[0..index - dead_nodes] are the first remaining nodes
+        //     self.nodes[index - dead_nodes..index] are all dead
+        //     self.nodes[index..] are unchanged
+        for index in 0..self.nodes.len() {
+            let node = &self.nodes[index];
             match node.state.get() {
                 NodeState::Pending | NodeState::Waiting => {
                     if dead_nodes > 0 {
-                        self.nodes.swap(i, i - dead_nodes);
-                        node_rewrites[i] -= dead_nodes;
+                        self.nodes.swap(index, index - dead_nodes);
+                        node_rewrites[index] -= dead_nodes;
                     }
                 }
                 NodeState::Done => {
@@ -655,7 +646,7 @@
                     } else {
                         self.done_cache.insert(node.obligation.as_predicate().clone());
                     }
-                    node_rewrites[i] = nodes_len;
+                    node_rewrites[index] = nodes_len;
                     dead_nodes += 1;
                 }
                 NodeState::Error => {
@@ -663,9 +654,9 @@
                     // tests must come up with a different type on every type error they
                     // check against.
                     self.waiting_cache.remove(node.obligation.as_predicate());
-                    node_rewrites[i] = nodes_len;
+                    node_rewrites[index] = nodes_len;
                     dead_nodes += 1;
-                    self.insert_into_error_cache(i);
+                    self.insert_into_error_cache(index);
                 }
                 NodeState::OnDfsStack | NodeState::Success => unreachable!()
             }
@@ -706,23 +697,18 @@
         let nodes_len = node_rewrites.len();
 
         for node in &mut self.nodes {
-            if let Some(index) = node.parent {
-                let new_i = node_rewrites[index.index()];
-                if new_i >= nodes_len {
-                    node.parent = None;
+            let mut index = 0;
+            while index < node.dependents.len() {
+                let new_index = node_rewrites[node.dependents[index]];
+                if new_index >= nodes_len {
+                    node.dependents.swap_remove(index);
+                    if index == 0 && node.has_parent {
+                        // We just removed the parent.
+                        node.has_parent = false;
+                    }
                 } else {
-                    node.parent = Some(NodeIndex::new(new_i));
-                }
-            }
-
-            let mut i = 0;
-            while i < node.dependents.len() {
-                let new_i = node_rewrites[node.dependents[i].index()];
-                if new_i >= nodes_len {
-                    node.dependents.swap_remove(i);
-                } else {
-                    node.dependents[i] = NodeIndex::new(new_i);
-                    i += 1;
+                    node.dependents[index] = new_index;
+                    index += 1;
                 }
             }
         }
@@ -730,11 +716,11 @@
         // This updating of `self.waiting_cache` is necessary because the
         // removal of nodes within `compress` can fail. See above.
         self.waiting_cache.retain(|_predicate, index| {
-            let new_i = node_rewrites[index.index()];
-            if new_i >= nodes_len {
+            let new_index = node_rewrites[*index];
+            if new_index >= nodes_len {
                 false
             } else {
-                *index = NodeIndex::new(new_i);
+                *index = new_index;
                 true
             }
         });