Auto merge of #79945 - jackh726:existential_trait_ref, r=nikomatsakis

Move binder for dyn to each list item

This essentially changes `ty::Binder<&'tcx List<ExistentialTraitRef>>` to `&'tcx List<ty::Binder<ExistentialTraitRef>>`.

This is a first step in moving the `dyn Trait` representation closer to Chalk, which we've talked about in `@rust-lang/wg-traits.`

r? `@nikomatsakis`

24 files changed, 310 insertions, 263 deletions

diff --git a/compiler/rustc_codegen_cranelift/src/value_and_place.rs b/compiler/rustc_codegen_cranelift/src/value_and_place.rs
index cb40d4ed9a6..5bcb11fd515 100644
--- a/compiler/rustc_codegen_cranelift/src/value_and_place.rs
+++ b/compiler/rustc_codegen_cranelift/src/value_and_place.rs
@@ -480,17 +480,19 @@ impl<'tcx> CPlace<'tcx> {
                     // fn(&T) -> for<'l> fn(&'l T) is allowed
                 }
                 (&ty::Dynamic(from_traits, _), &ty::Dynamic(to_traits, _)) => {
-                    let from_traits = fx
-                        .tcx
-                        .normalize_erasing_late_bound_regions(ParamEnv::reveal_all(), from_traits);
-                    let to_traits = fx
-                        .tcx
-                        .normalize_erasing_late_bound_regions(ParamEnv::reveal_all(), to_traits);
-                    assert_eq!(
-                        from_traits, to_traits,
-                        "Can't write trait object of incompatible traits {:?} to place with traits {:?}\n\n{:#?}",
-                        from_traits, to_traits, fx,
-                    );
+                    for (from, to) in from_traits.iter().zip(to_traits) {
+                        let from = fx
+                            .tcx
+                            .normalize_erasing_late_bound_regions(ParamEnv::reveal_all(), from);
+                        let to = fx
+                            .tcx
+                            .normalize_erasing_late_bound_regions(ParamEnv::reveal_all(), to);
+                        assert_eq!(
+                            from, to,
+                            "Can't write trait object of incompatible traits {:?} to place with traits {:?}\n\n{:#?}",
+                            from_traits, to_traits, fx,
+                        );
+                    }
                     // dyn for<'r> Trait<'r> -> dyn Trait<'_> is allowed
                 }
                 _ => {
diff --git a/compiler/rustc_infer/src/infer/error_reporting/mod.rs b/compiler/rustc_infer/src/infer/error_reporting/mod.rs
index 183fb314a00..fdec3c9fb73 100644
--- a/compiler/rustc_infer/src/infer/error_reporting/mod.rs
+++ b/compiler/rustc_infer/src/infer/error_reporting/mod.rs
@@ -496,7 +496,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
 
             fn print_dyn_existential(
                 self,
-                _predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+                _predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
             ) -> Result<Self::DynExistential, Self::Error> {
                 Err(NonTrivialPath)
             }
diff --git a/compiler/rustc_lint/src/context.rs b/compiler/rustc_lint/src/context.rs
index 16563d21ff1..bfeef490489 100644
--- a/compiler/rustc_lint/src/context.rs
+++ b/compiler/rustc_lint/src/context.rs
@@ -786,7 +786,7 @@ impl<'tcx> LateContext<'tcx> {
 
             fn print_dyn_existential(
                 self,
-                _predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+                _predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
             ) -> Result<Self::DynExistential, Self::Error> {
                 Ok(())
             }
diff --git a/compiler/rustc_lint/src/unused.rs b/compiler/rustc_lint/src/unused.rs
index 2a5ad5e6c98..5e1f94c071c 100644
--- a/compiler/rustc_lint/src/unused.rs
+++ b/compiler/rustc_lint/src/unused.rs
@@ -218,8 +218,10 @@ impl<'tcx> LateLintPass<'tcx> for UnusedResults {
                 }
                 ty::Dynamic(binder, _) => {
                     let mut has_emitted = false;
-                    for predicate in binder.skip_binder().iter() {
-                        if let ty::ExistentialPredicate::Trait(ref trait_ref) = predicate {
+                    for predicate in binder.iter() {
+                        if let ty::ExistentialPredicate::Trait(ref trait_ref) =
+                            predicate.skip_binder()
+                        {
                             let def_id = trait_ref.def_id;
                             let descr_post =
                                 &format!(" trait object{}{}", plural_suffix, descr_post,);
diff --git a/compiler/rustc_middle/src/ty/codec.rs b/compiler/rustc_middle/src/ty/codec.rs
index 1983af17dd0..df594690215 100644
--- a/compiler/rustc_middle/src/ty/codec.rs
+++ b/compiler/rustc_middle/src/ty/codec.rs
@@ -320,10 +320,14 @@ impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::List<Ty<'tcx>> {
     }
 }
 
-impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for ty::List<ty::ExistentialPredicate<'tcx>> {
+impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D>
+    for ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>
+{
     fn decode(decoder: &mut D) -> Result<&'tcx Self, D::Error> {
         let len = decoder.read_usize()?;
-        Ok(decoder.tcx().mk_existential_predicates((0..len).map(|_| Decodable::decode(decoder)))?)
+        Ok(decoder
+            .tcx()
+            .mk_poly_existential_predicates((0..len).map(|_| Decodable::decode(decoder)))?)
     }
 }
 
@@ -372,7 +376,7 @@ impl<'tcx, D: TyDecoder<'tcx>> RefDecodable<'tcx, D> for [mir::abstract_const::N
 impl_decodable_via_ref! {
     &'tcx ty::TypeckResults<'tcx>,
     &'tcx ty::List<Ty<'tcx>>,
-    &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+    &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     &'tcx Allocation,
     &'tcx mir::Body<'tcx>,
     &'tcx mir::UnsafetyCheckResult,
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index a8d007c0be2..adf02412b96 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -87,7 +87,7 @@ pub struct CtxtInterners<'tcx> {
     substs: InternedSet<'tcx, InternalSubsts<'tcx>>,
     canonical_var_infos: InternedSet<'tcx, List<CanonicalVarInfo<'tcx>>>,
     region: InternedSet<'tcx, RegionKind>,
-    existential_predicates: InternedSet<'tcx, List<ExistentialPredicate<'tcx>>>,
+    poly_existential_predicates: InternedSet<'tcx, List<ty::Binder<ExistentialPredicate<'tcx>>>>,
     predicate: InternedSet<'tcx, PredicateInner<'tcx>>,
     predicates: InternedSet<'tcx, List<Predicate<'tcx>>>,
     projs: InternedSet<'tcx, List<ProjectionKind>>,
@@ -103,7 +103,7 @@ impl<'tcx> CtxtInterners<'tcx> {
             type_list: Default::default(),
             substs: Default::default(),
             region: Default::default(),
-            existential_predicates: Default::default(),
+            poly_existential_predicates: Default::default(),
             canonical_var_infos: Default::default(),
             predicate: Default::default(),
             predicates: Default::default(),
@@ -1623,7 +1623,7 @@ nop_lift! {const_; &'a Const<'a> => &'tcx Const<'tcx>}
 nop_lift! {predicate; &'a PredicateInner<'a> => &'tcx PredicateInner<'tcx>}
 
 nop_list_lift! {type_list; Ty<'a> => Ty<'tcx>}
-nop_list_lift! {existential_predicates; ExistentialPredicate<'a> => ExistentialPredicate<'tcx>}
+nop_list_lift! {poly_existential_predicates; ty::Binder<ExistentialPredicate<'a>> => ty::Binder<ExistentialPredicate<'tcx>>}
 nop_list_lift! {predicates; Predicate<'a> => Predicate<'tcx>}
 nop_list_lift! {canonical_var_infos; CanonicalVarInfo<'a> => CanonicalVarInfo<'tcx>}
 nop_list_lift! {projs; ProjectionKind => ProjectionKind}
@@ -2064,7 +2064,8 @@ slice_interners!(
     type_list: _intern_type_list(Ty<'tcx>),
     substs: _intern_substs(GenericArg<'tcx>),
     canonical_var_infos: _intern_canonical_var_infos(CanonicalVarInfo<'tcx>),
-    existential_predicates: _intern_existential_predicates(ExistentialPredicate<'tcx>),
+    poly_existential_predicates:
+        _intern_poly_existential_predicates(ty::Binder<ExistentialPredicate<'tcx>>),
     predicates: _intern_predicates(Predicate<'tcx>),
     projs: _intern_projs(ProjectionKind),
     place_elems: _intern_place_elems(PlaceElem<'tcx>),
@@ -2295,7 +2296,7 @@ impl<'tcx> TyCtxt<'tcx> {
     #[inline]
     pub fn mk_dynamic(
         self,
-        obj: ty::Binder<&'tcx List<ExistentialPredicate<'tcx>>>,
+        obj: &'tcx List<ty::Binder<ExistentialPredicate<'tcx>>>,
         reg: ty::Region<'tcx>,
     ) -> Ty<'tcx> {
         self.mk_ty(Dynamic(obj, reg))
@@ -2425,13 +2426,17 @@ impl<'tcx> TyCtxt<'tcx> {
         Place { local: place.local, projection: self.intern_place_elems(&projection) }
     }
 
-    pub fn intern_existential_predicates(
+    pub fn intern_poly_existential_predicates(
         self,
-        eps: &[ExistentialPredicate<'tcx>],
-    ) -> &'tcx List<ExistentialPredicate<'tcx>> {
+        eps: &[ty::Binder<ExistentialPredicate<'tcx>>],
+    ) -> &'tcx List<ty::Binder<ExistentialPredicate<'tcx>>> {
         assert!(!eps.is_empty());
-        assert!(eps.array_windows().all(|[a, b]| a.stable_cmp(self, b) != Ordering::Greater));
-        self._intern_existential_predicates(eps)
+        assert!(
+            eps.array_windows()
+                .all(|[a, b]| a.skip_binder().stable_cmp(self, &b.skip_binder())
+                    != Ordering::Greater)
+        );
+        self._intern_poly_existential_predicates(eps)
     }
 
     pub fn intern_predicates(self, preds: &[Predicate<'tcx>]) -> &'tcx List<Predicate<'tcx>> {
@@ -2488,13 +2493,16 @@ impl<'tcx> TyCtxt<'tcx> {
         })
     }
 
-    pub fn mk_existential_predicates<
-        I: InternAs<[ExistentialPredicate<'tcx>], &'tcx List<ExistentialPredicate<'tcx>>>,
+    pub fn mk_poly_existential_predicates<
+        I: InternAs<
+            [ty::Binder<ExistentialPredicate<'tcx>>],
+            &'tcx List<ty::Binder<ExistentialPredicate<'tcx>>>,
+        >,
     >(
         self,
         iter: I,
     ) -> I::Output {
-        iter.intern_with(|xs| self.intern_existential_predicates(xs))
+        iter.intern_with(|xs| self.intern_poly_existential_predicates(xs))
     }
 
     pub fn mk_predicates<I: InternAs<[Predicate<'tcx>], &'tcx List<Predicate<'tcx>>>>(
diff --git a/compiler/rustc_middle/src/ty/error.rs b/compiler/rustc_middle/src/ty/error.rs
index 5ec0ec0c56a..97af927dfcb 100644
--- a/compiler/rustc_middle/src/ty/error.rs
+++ b/compiler/rustc_middle/src/ty/error.rs
@@ -58,7 +58,7 @@ pub enum TypeError<'tcx> {
     CyclicTy(Ty<'tcx>),
     CyclicConst(&'tcx ty::Const<'tcx>),
     ProjectionMismatched(ExpectedFound<DefId>),
-    ExistentialMismatch(ExpectedFound<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>),
+    ExistentialMismatch(ExpectedFound<&'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>>),
     ObjectUnsafeCoercion(DefId),
     ConstMismatch(ExpectedFound<&'tcx ty::Const<'tcx>>),
 
diff --git a/compiler/rustc_middle/src/ty/flags.rs b/compiler/rustc_middle/src/ty/flags.rs
index 8b97a87f214..4de3d159248 100644
--- a/compiler/rustc_middle/src/ty/flags.rs
+++ b/compiler/rustc_middle/src/ty/flags.rs
@@ -160,19 +160,15 @@ impl FlagComputation {
             }
 
             &ty::Dynamic(obj, r) => {
-                self.bound_computation(obj, |computation, obj| {
-                    for predicate in obj.iter() {
-                        match predicate {
-                            ty::ExistentialPredicate::Trait(tr) => {
-                                computation.add_substs(tr.substs)
-                            }
-                            ty::ExistentialPredicate::Projection(p) => {
-                                computation.add_existential_projection(&p);
-                            }
-                            ty::ExistentialPredicate::AutoTrait(_) => {}
+                for predicate in obj.iter() {
+                    self.bound_computation(predicate, |computation, predicate| match predicate {
+                        ty::ExistentialPredicate::Trait(tr) => computation.add_substs(tr.substs),
+                        ty::ExistentialPredicate::Projection(p) => {
+                            computation.add_existential_projection(&p);
                         }
-                    }
-                });
+                        ty::ExistentialPredicate::AutoTrait(_) => {}
+                    });
+                }
 
                 self.add_region(r);
             }
diff --git a/compiler/rustc_middle/src/ty/print/mod.rs b/compiler/rustc_middle/src/ty/print/mod.rs
index 2e00be2395b..c79e06b7fdd 100644
--- a/compiler/rustc_middle/src/ty/print/mod.rs
+++ b/compiler/rustc_middle/src/ty/print/mod.rs
@@ -63,7 +63,7 @@ pub trait Printer<'tcx>: Sized {
 
     fn print_dyn_existential(
         self,
-        predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+        predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     ) -> Result<Self::DynExistential, Self::Error>;
 
     fn print_const(self, ct: &'tcx ty::Const<'tcx>) -> Result<Self::Const, Self::Error>;
@@ -343,7 +343,9 @@ impl<'tcx, P: Printer<'tcx>> Print<'tcx, P> for Ty<'tcx> {
     }
 }
 
-impl<'tcx, P: Printer<'tcx>> Print<'tcx, P> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
+impl<'tcx, P: Printer<'tcx>> Print<'tcx, P>
+    for &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>
+{
     type Output = P::DynExistential;
     type Error = P::Error;
     fn print(&self, cx: P) -> Result<Self::Output, Self::Error> {
diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs
index 38f8e779f6a..09ef69e9690 100644
--- a/compiler/rustc_middle/src/ty/print/pretty.rs
+++ b/compiler/rustc_middle/src/ty/print/pretty.rs
@@ -209,6 +209,17 @@ pub trait PrettyPrinter<'tcx>:
         value.as_ref().skip_binder().print(self)
     }
 
+    fn wrap_binder<T, F: Fn(&T, Self) -> Result<Self, fmt::Error>>(
+        self,
+        value: &ty::Binder<T>,
+        f: F,
+    ) -> Result<Self, Self::Error>
+    where
+        T: Print<'tcx, Self, Output = Self, Error = Self::Error> + TypeFoldable<'tcx>,
+    {
+        f(value.as_ref().skip_binder(), self)
+    }
+
     /// Prints comma-separated elements.
     fn comma_sep<T>(mut self, mut elems: impl Iterator<Item = T>) -> Result<Self, Self::Error>
     where
@@ -753,72 +764,77 @@ pub trait PrettyPrinter<'tcx>:
 
     fn pretty_print_dyn_existential(
         mut self,
-        predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+        predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     ) -> Result<Self::DynExistential, Self::Error> {
-        define_scoped_cx!(self);
-
         // Generate the main trait ref, including associated types.
         let mut first = true;
 
         if let Some(principal) = predicates.principal() {
-            p!(print_def_path(principal.def_id, &[]));
-
-            let mut resugared = false;
-
-            // Special-case `Fn(...) -> ...` and resugar it.
-            let fn_trait_kind = self.tcx().fn_trait_kind_from_lang_item(principal.def_id);
-            if !self.tcx().sess.verbose() && fn_trait_kind.is_some() {
-                if let ty::Tuple(ref args) = principal.substs.type_at(0).kind() {
-                    let mut projections = predicates.projection_bounds();
-                    if let (Some(proj), None) = (projections.next(), projections.next()) {
-                        let tys: Vec<_> = args.iter().map(|k| k.expect_ty()).collect();
-                        p!(pretty_fn_sig(&tys, false, proj.ty));
-                        resugared = true;
+            self = self.wrap_binder(&principal, |principal, mut cx| {
+                define_scoped_cx!(cx);
+                p!(print_def_path(principal.def_id, &[]));
+
+                let mut resugared = false;
+
+                // Special-case `Fn(...) -> ...` and resugar it.
+                let fn_trait_kind = cx.tcx().fn_trait_kind_from_lang_item(principal.def_id);
+                if !cx.tcx().sess.verbose() && fn_trait_kind.is_some() {
+                    if let ty::Tuple(ref args) = principal.substs.type_at(0).kind() {
+                        let mut projections = predicates.projection_bounds();
+                        if let (Some(proj), None) = (projections.next(), projections.next()) {
+                            let tys: Vec<_> = args.iter().map(|k| k.expect_ty()).collect();
+                            p!(pretty_fn_sig(&tys, false, proj.skip_binder().ty));
+                            resugared = true;
+                        }
                     }
                 }
-            }
 
-            // HACK(eddyb) this duplicates `FmtPrinter`'s `path_generic_args`,
-            // in order to place the projections inside the `<...>`.
-            if !resugared {
-                // Use a type that can't appear in defaults of type parameters.
-                let dummy_self = self.tcx().mk_ty_infer(ty::FreshTy(0));
-                let principal = principal.with_self_ty(self.tcx(), dummy_self);
+                // HACK(eddyb) this duplicates `FmtPrinter`'s `path_generic_args`,
+                // in order to place the projections inside the `<...>`.
+                if !resugared {
+                    // Use a type that can't appear in defaults of type parameters.
+                    let dummy_cx = cx.tcx().mk_ty_infer(ty::FreshTy(0));
+                    let principal = principal.with_self_ty(cx.tcx(), dummy_cx);
+
+                    let args = cx.generic_args_to_print(
+                        cx.tcx().generics_of(principal.def_id),
+                        principal.substs,
+                    );
+
+                    // Don't print `'_` if there's no unerased regions.
+                    let print_regions = args.iter().any(|arg| match arg.unpack() {
+                        GenericArgKind::Lifetime(r) => *r != ty::ReErased,
+                        _ => false,
+                    });
+                    let mut args = args.iter().cloned().filter(|arg| match arg.unpack() {
+                        GenericArgKind::Lifetime(_) => print_regions,
+                        _ => true,
+                    });
+                    let mut projections = predicates.projection_bounds();
 
-                let args = self.generic_args_to_print(
-                    self.tcx().generics_of(principal.def_id),
-                    principal.substs,
-                );
+                    let arg0 = args.next();
+                    let projection0 = projections.next();
+                    if arg0.is_some() || projection0.is_some() {
+                        let args = arg0.into_iter().chain(args);
+                        let projections = projection0.into_iter().chain(projections);
 
-                // Don't print `'_` if there's no unerased regions.
-                let print_regions = args.iter().any(|arg| match arg.unpack() {
-                    GenericArgKind::Lifetime(r) => *r != ty::ReErased,
-                    _ => false,
-                });
-                let mut args = args.iter().cloned().filter(|arg| match arg.unpack() {
-                    GenericArgKind::Lifetime(_) => print_regions,
-                    _ => true,
-                });
-                let mut projections = predicates.projection_bounds();
-
-                let arg0 = args.next();
-                let projection0 = projections.next();
-                if arg0.is_some() || projection0.is_some() {
-                    let args = arg0.into_iter().chain(args);
-                    let projections = projection0.into_iter().chain(projections);
-
-                    p!(generic_delimiters(|mut cx| {
-                        cx = cx.comma_sep(args)?;
-                        if arg0.is_some() && projection0.is_some() {
-                            write!(cx, ", ")?;
-                        }
-                        cx.comma_sep(projections)
-                    }));
+                        p!(generic_delimiters(|mut cx| {
+                            cx = cx.comma_sep(args)?;
+                            if arg0.is_some() && projection0.is_some() {
+                                write!(cx, ", ")?;
+                            }
+                            cx.comma_sep(projections)
+                        }));
+                    }
                 }
-            }
+                Ok(cx)
+            })?;
+
             first = false;
         }
 
+        define_scoped_cx!(self);
+
         // Builtin bounds.
         // FIXME(eddyb) avoid printing twice (needed to ensure
         // that the auto traits are sorted *and* printed via cx).
@@ -1391,7 +1407,7 @@ impl<F: fmt::Write> Printer<'tcx> for FmtPrinter<'_, 'tcx, F> {
 
     fn print_dyn_existential(
         self,
-        predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+        predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     ) -> Result<Self::DynExistential, Self::Error> {
         self.pretty_print_dyn_existential(predicates)
     }
@@ -1537,6 +1553,17 @@ impl<F: fmt::Write> PrettyPrinter<'tcx> for FmtPrinter<'_, 'tcx, F> {
         self.pretty_in_binder(value)
     }
 
+    fn wrap_binder<T, C: Fn(&T, Self) -> Result<Self, Self::Error>>(
+        self,
+        value: &ty::Binder<T>,
+        f: C,
+    ) -> Result<Self, Self::Error>
+    where
+        T: Print<'tcx, Self, Output = Self, Error = Self::Error> + TypeFoldable<'tcx>,
+    {
+        self.pretty_wrap_binder(value, f)
+    }
+
     fn typed_value(
         mut self,
         f: impl FnOnce(Self) -> Result<Self, Self::Error>,
@@ -1790,6 +1817,22 @@ impl<F: fmt::Write> FmtPrinter<'_, 'tcx, F> {
         Ok(inner)
     }
 
+    pub fn pretty_wrap_binder<T, C: Fn(&T, Self) -> Result<Self, fmt::Error>>(
+        self,
+        value: &ty::Binder<T>,
+        f: C,
+    ) -> Result<Self, fmt::Error>
+    where
+        T: Print<'tcx, Self, Output = Self, Error = fmt::Error> + TypeFoldable<'tcx>,
+    {
+        let old_region_index = self.region_index;
+        let (new, new_value) = self.name_all_regions(value)?;
+        let mut inner = f(&new_value.0, new)?;
+        inner.region_index = old_region_index;
+        inner.binder_depth -= 1;
+        Ok(inner)
+    }
+
     fn prepare_late_bound_region_info<T>(&mut self, value: &ty::Binder<T>)
     where
         T: TypeFoldable<'tcx>,
@@ -1906,12 +1949,12 @@ impl ty::Binder<ty::TraitRef<'tcx>> {
 
 forward_display_to_print! {
     Ty<'tcx>,
-    &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+    &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     &'tcx ty::Const<'tcx>,
 
     // HACK(eddyb) these are exhaustive instead of generic,
     // because `for<'tcx>` isn't possible yet.
-    ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>,
+    ty::Binder<ty::ExistentialPredicate<'tcx>>,
     ty::Binder<ty::TraitRef<'tcx>>,
     ty::Binder<TraitRefPrintOnlyTraitPath<'tcx>>,
     ty::Binder<ty::FnSig<'tcx>>,
diff --git a/compiler/rustc_middle/src/ty/relate.rs b/compiler/rustc_middle/src/ty/relate.rs
index ef5034e218d..af7fc429719 100644
--- a/compiler/rustc_middle/src/ty/relate.rs
+++ b/compiler/rustc_middle/src/ty/relate.rs
@@ -603,7 +603,7 @@ pub fn super_relate_consts<R: TypeRelation<'tcx>>(
     new_const_val.map(|val| tcx.mk_const(ty::Const { val, ty: a.ty }))
 }
 
-impl<'tcx> Relate<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
+impl<'tcx> Relate<'tcx> for &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>> {
     fn relate<R: TypeRelation<'tcx>>(
         relation: &mut R,
         a: Self,
@@ -616,9 +616,10 @@ impl<'tcx> Relate<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
         // in `a`.
         let mut a_v: Vec<_> = a.into_iter().collect();
         let mut b_v: Vec<_> = b.into_iter().collect();
-        a_v.sort_by(|a, b| a.stable_cmp(tcx, b));
+        // `skip_binder` here is okay because `stable_cmp` doesn't look at binders
+        a_v.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder()));
         a_v.dedup();
-        b_v.sort_by(|a, b| a.stable_cmp(tcx, b));
+        b_v.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder()));
         b_v.dedup();
         if a_v.len() != b_v.len() {
             return Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)));
@@ -626,14 +627,18 @@ impl<'tcx> Relate<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
 
         let v = a_v.into_iter().zip(b_v.into_iter()).map(|(ep_a, ep_b)| {
             use crate::ty::ExistentialPredicate::*;
-            match (ep_a, ep_b) {
-                (Trait(a), Trait(b)) => Ok(Trait(relation.relate(a, b)?)),
-                (Projection(a), Projection(b)) => Ok(Projection(relation.relate(a, b)?)),
-                (AutoTrait(a), AutoTrait(b)) if a == b => Ok(AutoTrait(a)),
+            match (ep_a.skip_binder(), ep_b.skip_binder()) {
+                (Trait(a), Trait(b)) => Ok(ty::Binder::bind(Trait(
+                    relation.relate(ep_a.rebind(a), ep_b.rebind(b))?.skip_binder(),
+                ))),
+                (Projection(a), Projection(b)) => Ok(ty::Binder::bind(Projection(
+                    relation.relate(ep_a.rebind(a), ep_b.rebind(b))?.skip_binder(),
+                ))),
+                (AutoTrait(a), AutoTrait(b)) if a == b => Ok(ep_a.rebind(AutoTrait(a))),
                 _ => Err(TypeError::ExistentialMismatch(expected_found(relation, a, b))),
             }
         });
-        Ok(tcx.mk_existential_predicates(v)?)
+        Ok(tcx.mk_poly_existential_predicates(v)?)
     }
 }
 
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index 94e69a93a6b..8af5792b3fb 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -843,9 +843,9 @@ impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::Binder<T> {
     }
 }
 
-impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
+impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>> {
     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
-        ty::util::fold_list(self, folder, |tcx, v| tcx.intern_existential_predicates(v))
+        ty::util::fold_list(self, folder, |tcx, v| tcx.intern_poly_existential_predicates(v))
     }
 
     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index fc9dcdf1775..62d1dda37d6 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -152,7 +152,7 @@ pub enum TyKind<'tcx> {
     FnPtr(PolyFnSig<'tcx>),
 
     /// A trait, defined with `trait`.
-    Dynamic(Binder<&'tcx List<ExistentialPredicate<'tcx>>>, ty::Region<'tcx>),
+    Dynamic(&'tcx List<Binder<ExistentialPredicate<'tcx>>>, ty::Region<'tcx>),
 
     /// The anonymous type of a closure. Used to represent the type of
     /// `|a| a`.
@@ -762,7 +762,7 @@ impl<'tcx> Binder<ExistentialPredicate<'tcx>> {
     }
 }
 
-impl<'tcx> List<ExistentialPredicate<'tcx>> {
+impl<'tcx> List<ty::Binder<ExistentialPredicate<'tcx>>> {
     /// Returns the "principal `DefId`" of this set of existential predicates.
     ///
     /// A Rust trait object type consists (in addition to a lifetime bound)
@@ -788,64 +788,42 @@ impl<'tcx> List<ExistentialPredicate<'tcx>> {
     /// is `{Send, Sync}`, while there is no principal. These trait objects
     /// have a "trivial" vtable consisting of just the size, alignment,
     /// and destructor.
-    pub fn principal(&self) -> Option<ExistentialTraitRef<'tcx>> {
-        match self[0] {
-            ExistentialPredicate::Trait(tr) => Some(tr),
-            _ => None,
-        }
+    pub fn principal(&self) -> Option<ty::Binder<ExistentialTraitRef<'tcx>>> {
+        self[0]
+            .map_bound(|this| match this {
+                ExistentialPredicate::Trait(tr) => Some(tr),
+                _ => None,
+            })
+            .transpose()
     }
 
     pub fn principal_def_id(&self) -> Option<DefId> {
-        self.principal().map(|trait_ref| trait_ref.def_id)
+        self.principal().map(|trait_ref| trait_ref.skip_binder().def_id)
     }
 
     #[inline]
     pub fn projection_bounds<'a>(
         &'a self,
-    ) -> impl Iterator<Item = ExistentialProjection<'tcx>> + 'a {
-        self.iter().filter_map(|predicate| match predicate {
-            ExistentialPredicate::Projection(projection) => Some(projection),
-            _ => None,
+    ) -> impl Iterator<Item = ty::Binder<ExistentialProjection<'tcx>>> + 'a {
+        self.iter().filter_map(|predicate| {
+            predicate
+                .map_bound(|pred| match pred {
+                    ExistentialPredicate::Projection(projection) => Some(projection),
+                    _ => None,
+                })
+                .transpose()
         })
     }
 
     #[inline]
     pub fn auto_traits<'a>(&'a self) -> impl Iterator<Item = DefId> + 'a {
-        self.iter().filter_map(|predicate| match predicate {
+        self.iter().filter_map(|predicate| match predicate.skip_binder() {
             ExistentialPredicate::AutoTrait(did) => Some(did),
             _ => None,
         })
     }
 }
 
-impl<'tcx> Binder<&'tcx List<ExistentialPredicate<'tcx>>> {
-    pub fn principal(&self) -> Option<ty::Binder<ExistentialTraitRef<'tcx>>> {
-        self.map_bound(|b| b.principal()).transpose()
-    }
-
-    pub fn principal_def_id(&self) -> Option<DefId> {
-        self.skip_binder().principal_def_id()
-    }
-
-    #[inline]
-    pub fn projection_bounds<'a>(
-        &'a self,
-    ) -> impl Iterator<Item = PolyExistentialProjection<'tcx>> + 'a {
-        self.skip_binder().projection_bounds().map(Binder::bind)
-    }
-
-    #[inline]
-    pub fn auto_traits<'a>(&'a self) -> impl Iterator<Item = DefId> + 'a {
-        self.skip_binder().auto_traits()
-    }
-
-    pub fn iter<'a>(
-        &'a self,
-    ) -> impl DoubleEndedIterator<Item = Binder<ExistentialPredicate<'tcx>>> + 'tcx {
-        self.skip_binder().iter().map(Binder::bind)
-    }
-}
-
 /// A complete reference to a trait. These take numerous guises in syntax,
 /// but perhaps the most recognizable form is in a where-clause:
 ///
diff --git a/compiler/rustc_mir/src/interpret/intrinsics/type_name.rs b/compiler/rustc_mir/src/interpret/intrinsics/type_name.rs
index 554ada1ab25..e1ec4cc5e97 100644
--- a/compiler/rustc_mir/src/interpret/intrinsics/type_name.rs
+++ b/compiler/rustc_mir/src/interpret/intrinsics/type_name.rs
@@ -74,7 +74,7 @@ impl<'tcx> Printer<'tcx> for AbsolutePathPrinter<'tcx> {
 
     fn print_dyn_existential(
         mut self,
-        predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+        predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     ) -> Result<Self::DynExistential, Self::Error> {
         let mut first = true;
         for p in predicates {
diff --git a/compiler/rustc_privacy/src/lib.rs b/compiler/rustc_privacy/src/lib.rs
index 4414bf57c6b..3b4249a93e1 100644
--- a/compiler/rustc_privacy/src/lib.rs
+++ b/compiler/rustc_privacy/src/lib.rs
@@ -184,8 +184,8 @@ where
             ty::Dynamic(predicates, ..) => {
                 // All traits in the list are considered the "primary" part of the type
                 // and are visited by shallow visitors.
-                for predicate in predicates.skip_binder() {
-                    let trait_ref = match predicate {
+                for predicate in predicates {
+                    let trait_ref = match predicate.skip_binder() {
                         ty::ExistentialPredicate::Trait(trait_ref) => trait_ref,
                         ty::ExistentialPredicate::Projection(proj) => proj.trait_ref(tcx),
                         ty::ExistentialPredicate::AutoTrait(def_id) => {
diff --git a/compiler/rustc_symbol_mangling/src/legacy.rs b/compiler/rustc_symbol_mangling/src/legacy.rs
index eba8e1a0613..6356a7e7832 100644
--- a/compiler/rustc_symbol_mangling/src/legacy.rs
+++ b/compiler/rustc_symbol_mangling/src/legacy.rs
@@ -222,7 +222,7 @@ impl Printer<'tcx> for SymbolPrinter<'tcx> {
 
     fn print_dyn_existential(
         mut self,
-        predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+        predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     ) -> Result<Self::DynExistential, Self::Error> {
         let mut first = true;
         for p in predicates {
diff --git a/compiler/rustc_symbol_mangling/src/v0.rs b/compiler/rustc_symbol_mangling/src/v0.rs
index c28c2fecfbb..0294fb23c56 100644
--- a/compiler/rustc_symbol_mangling/src/v0.rs
+++ b/compiler/rustc_symbol_mangling/src/v0.rs
@@ -465,9 +465,7 @@ impl Printer<'tcx> for SymbolMangler<'tcx> {
 
             ty::Dynamic(predicates, r) => {
                 self.push("D");
-                self = self.in_binder(&predicates, |cx, predicates| {
-                    cx.print_dyn_existential(predicates)
-                })?;
+                self = self.print_dyn_existential(predicates)?;
                 self = r.print(self)?;
             }
 
@@ -486,26 +484,29 @@ impl Printer<'tcx> for SymbolMangler<'tcx> {
 
     fn print_dyn_existential(
         mut self,
-        predicates: &'tcx ty::List<ty::ExistentialPredicate<'tcx>>,
+        predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     ) -> Result<Self::DynExistential, Self::Error> {
         for predicate in predicates {
-            match predicate {
-                ty::ExistentialPredicate::Trait(trait_ref) => {
-                    // Use a type that can't appear in defaults of type parameters.
-                    let dummy_self = self.tcx.mk_ty_infer(ty::FreshTy(0));
-                    let trait_ref = trait_ref.with_self_ty(self.tcx, dummy_self);
-                    self = self.print_def_path(trait_ref.def_id, trait_ref.substs)?;
-                }
-                ty::ExistentialPredicate::Projection(projection) => {
-                    let name = self.tcx.associated_item(projection.item_def_id).ident;
-                    self.push("p");
-                    self.push_ident(&name.as_str());
-                    self = projection.ty.print(self)?;
-                }
-                ty::ExistentialPredicate::AutoTrait(def_id) => {
-                    self = self.print_def_path(def_id, &[])?;
+            self = self.in_binder(&predicate, |mut cx, predicate| {
+                match predicate {
+                    ty::ExistentialPredicate::Trait(trait_ref) => {
+                        // Use a type that can't appear in defaults of type parameters.
+                        let dummy_self = cx.tcx.mk_ty_infer(ty::FreshTy(0));
+                        let trait_ref = trait_ref.with_self_ty(cx.tcx, dummy_self);
+                        cx = cx.print_def_path(trait_ref.def_id, trait_ref.substs)?;
+                    }
+                    ty::ExistentialPredicate::Projection(projection) => {
+                        let name = cx.tcx.associated_item(projection.item_def_id).ident;
+                        cx.push("p");
+                        cx.push_ident(&name.as_str());
+                        cx = projection.ty.print(cx)?;
+                    }
+                    ty::ExistentialPredicate::AutoTrait(def_id) => {
+                        cx = cx.print_def_path(*def_id, &[])?;
+                    }
                 }
-            }
+                Ok(cx)
+            })?;
         }
         self.push("E");
         Ok(self)
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
index 1b5375938af..69f66f6e6b1 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
@@ -219,8 +219,8 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
             }
         }
         if let ty::Dynamic(traits, _) = self_ty.kind() {
-            for t in traits.skip_binder() {
-                if let ty::ExistentialPredicate::Trait(trait_ref) = t {
+            for t in traits.iter() {
+                if let ty::ExistentialPredicate::Trait(trait_ref) = t.skip_binder() {
                     flags.push((sym::_Self, Some(self.tcx.def_path_str(trait_ref.def_id))))
                 }
             }
diff --git a/compiler/rustc_trait_selection/src/traits/object_safety.rs b/compiler/rustc_trait_selection/src/traits/object_safety.rs
index d912a00d6b7..8b275db89f1 100644
--- a/compiler/rustc_trait_selection/src/traits/object_safety.rs
+++ b/compiler/rustc_trait_selection/src/traits/object_safety.rs
@@ -551,8 +551,9 @@ fn object_ty_for_trait<'tcx>(
 
     let trait_ref = ty::TraitRef::identity(tcx, trait_def_id);
 
-    let trait_predicate =
-        ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref));
+    let trait_predicate = ty::Binder::dummy(ty::ExistentialPredicate::Trait(
+        ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref),
+    ));
 
     let mut associated_types = traits::supertraits(tcx, ty::Binder::dummy(trait_ref))
         .flat_map(|super_trait_ref| {
@@ -569,24 +570,19 @@ fn object_ty_for_trait<'tcx>(
     let projection_predicates = associated_types.into_iter().map(|(super_trait_ref, item)| {
         // We *can* get bound lifetimes here in cases like
         // `trait MyTrait: for<'s> OtherTrait<&'s T, Output=bool>`.
-        //
-        // binder moved to (*)...
-        let super_trait_ref = super_trait_ref.skip_binder();
-        ty::ExistentialPredicate::Projection(ty::ExistentialProjection {
-            ty: tcx.mk_projection(item.def_id, super_trait_ref.substs),
-            item_def_id: item.def_id,
-            substs: super_trait_ref.substs,
+        super_trait_ref.map_bound(|super_trait_ref| {
+            ty::ExistentialPredicate::Projection(ty::ExistentialProjection {
+                ty: tcx.mk_projection(item.def_id, super_trait_ref.substs),
+                item_def_id: item.def_id,
+                substs: super_trait_ref.substs,
+            })
         })
     });
 
-    let existential_predicates =
-        tcx.mk_existential_predicates(iter::once(trait_predicate).chain(projection_predicates));
+    let existential_predicates = tcx
+        .mk_poly_existential_predicates(iter::once(trait_predicate).chain(projection_predicates));
 
-    let object_ty = tcx.mk_dynamic(
-        // (*) ... binder re-introduced here
-        ty::Binder::bind(existential_predicates),
-        lifetime,
-    );
+    let object_ty = tcx.mk_dynamic(existential_predicates, lifetime);
 
     debug!("object_ty_for_trait: object_ty=`{}`", object_ty);
 
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index ed22d5849e2..ab09fcfd8cc 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -375,24 +375,22 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let self_ty = self.infcx.shallow_resolve(trait_predicate.self_ty());
         let obligation_trait_ref = ty::Binder::dummy(trait_predicate.trait_ref);
         let data = match *self_ty.kind() {
-            ty::Dynamic(data, ..) => {
-                self.infcx
-                    .replace_bound_vars_with_fresh_vars(
-                        obligation.cause.span,
-                        HigherRankedType,
-                        data,
-                    )
-                    .0
-            }
+            ty::Dynamic(data, ..) => data,
             _ => span_bug!(obligation.cause.span, "object candidate with non-object"),
         };
 
-        let object_trait_ref = data
-            .principal()
-            .unwrap_or_else(|| {
-                span_bug!(obligation.cause.span, "object candidate with no principal")
-            })
-            .with_self_ty(self.tcx(), self_ty);
+        let object_trait_ref = data.principal().unwrap_or_else(|| {
+            span_bug!(obligation.cause.span, "object candidate with no principal")
+        });
+        let object_trait_ref = self
+            .infcx
+            .replace_bound_vars_with_fresh_vars(
+                obligation.cause.span,
+                HigherRankedType,
+                object_trait_ref,
+            )
+            .0;
+        let object_trait_ref = object_trait_ref.with_self_ty(self.tcx(), self_ty);
 
         let mut nested = vec![];
 
@@ -711,15 +709,22 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             // Trait+Kx+'a -> Trait+Ky+'b (upcasts).
             (&ty::Dynamic(ref data_a, r_a), &ty::Dynamic(ref data_b, r_b)) => {
                 // See `assemble_candidates_for_unsizing` for more info.
-                let existential_predicates = data_a.map_bound(|data_a| {
-                    let iter = data_a
-                        .principal()
-                        .map(ty::ExistentialPredicate::Trait)
-                        .into_iter()
-                        .chain(data_a.projection_bounds().map(ty::ExistentialPredicate::Projection))
-                        .chain(data_b.auto_traits().map(ty::ExistentialPredicate::AutoTrait));
-                    tcx.mk_existential_predicates(iter)
-                });
+                let iter = data_a
+                    .principal()
+                    .map(|b| b.map_bound(ty::ExistentialPredicate::Trait))
+                    .into_iter()
+                    .chain(
+                        data_a
+                            .projection_bounds()
+                            .map(|b| b.map_bound(ty::ExistentialPredicate::Projection)),
+                    )
+                    .chain(
+                        data_b
+                            .auto_traits()
+                            .map(ty::ExistentialPredicate::AutoTrait)
+                            .map(ty::Binder::dummy),
+                    );
+                let existential_predicates = tcx.mk_poly_existential_predicates(iter);
                 let source_trait = tcx.mk_dynamic(existential_predicates, r_b);
 
                 // Require that the traits involved in this upcast are **equal**;
diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs
index 5bcb16d21e0..3f58fd72f40 100644
--- a/compiler/rustc_trait_selection/src/traits/wf.rs
+++ b/compiler/rustc_trait_selection/src/traits/wf.rs
@@ -706,7 +706,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
     fn from_object_ty(
         &mut self,
         ty: Ty<'tcx>,
-        data: ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>,
+        data: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
         region: ty::Region<'tcx>,
     ) {
         // Imagine a type like this:
@@ -769,7 +769,7 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> {
 /// `infer::required_region_bounds`, see that for more information.
 pub fn object_region_bounds<'tcx>(
     tcx: TyCtxt<'tcx>,
-    existential_predicates: ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>,
+    existential_predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
 ) -> Vec<ty::Region<'tcx>> {
     // Since we don't actually *know* the self type for an object,
     // this "open(err)" serves as a kind of dummy standin -- basically
diff --git a/compiler/rustc_traits/src/chalk/lowering.rs b/compiler/rustc_traits/src/chalk/lowering.rs
index 9afb980f84d..3a747b09cd4 100644
--- a/compiler/rustc_traits/src/chalk/lowering.rs
+++ b/compiler/rustc_traits/src/chalk/lowering.rs
@@ -615,7 +615,7 @@ impl<'tcx> LowerInto<'tcx, Option<chalk_ir::QuantifiedWhereClause<RustInterner<'
 }
 
 impl<'tcx> LowerInto<'tcx, chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<RustInterner<'tcx>>>>
-    for Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>
+    for &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>
 {
     fn lower_into(
         self,
@@ -627,48 +627,53 @@ impl<'tcx> LowerInto<'tcx, chalk_ir::Binders<chalk_ir::QuantifiedWhereClauses<Ru
         // Binders<&[Binders<WhereClause<I>>]>
         // This means that any variables that are escaping `self` need to be
         // shifted in by one so that they are still escaping.
-        let shifted_predicates = ty::fold::shift_vars(interner.tcx, self, 1);
+        let predicates = ty::fold::shift_vars(interner.tcx, self, 1);
 
-        let (predicates, binders, _named_regions) =
-            collect_bound_vars(interner, interner.tcx, shifted_predicates);
         let self_ty = interner.tcx.mk_ty(ty::Bound(
             // This is going to be wrapped in a binder
             ty::DebruijnIndex::from_usize(1),
             ty::BoundTy { var: ty::BoundVar::from_usize(0), kind: ty::BoundTyKind::Anon },
         ));
-        let where_clauses = predicates.into_iter().map(|predicate| match predicate {
-            ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef { def_id, substs }) => {
-                chalk_ir::Binders::new(
+        let where_clauses = predicates.into_iter().map(|predicate| {
+            let (predicate, binders, _named_regions) =
+                collect_bound_vars(interner, interner.tcx, predicate);
+            match predicate {
+                ty::ExistentialPredicate::Trait(ty::ExistentialTraitRef { def_id, substs }) => {
+                    chalk_ir::Binders::new(
+                        binders.clone(),
+                        chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef {
+                            trait_id: chalk_ir::TraitId(def_id),
+                            substitution: interner
+                                .tcx
+                                .mk_substs_trait(self_ty, substs)
+                                .lower_into(interner),
+                        }),
+                    )
+                }
+                ty::ExistentialPredicate::Projection(predicate) => chalk_ir::Binders::new(
+                    binders.clone(),
+                    chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq {
+                        alias: chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy {
+                            associated_ty_id: chalk_ir::AssocTypeId(predicate.item_def_id),
+                            substitution: interner
+                                .tcx
+                                .mk_substs_trait(self_ty, predicate.substs)
+                                .lower_into(interner),
+                        }),
+                        ty: predicate.ty.lower_into(interner),
+                    }),
+                ),
+                ty::ExistentialPredicate::AutoTrait(def_id) => chalk_ir::Binders::new(
                     binders.clone(),
                     chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef {
                         trait_id: chalk_ir::TraitId(def_id),
                         substitution: interner
                             .tcx
-                            .mk_substs_trait(self_ty, substs)
+                            .mk_substs_trait(self_ty, &[])
                             .lower_into(interner),
                     }),
-                )
+                ),
             }
-            ty::ExistentialPredicate::Projection(predicate) => chalk_ir::Binders::new(
-                binders.clone(),
-                chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq {
-                    alias: chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy {
-                        associated_ty_id: chalk_ir::AssocTypeId(predicate.item_def_id),
-                        substitution: interner
-                            .tcx
-                            .mk_substs_trait(self_ty, predicate.substs)
-                            .lower_into(interner),
-                    }),
-                    ty: predicate.ty.lower_into(interner),
-                }),
-            ),
-            ty::ExistentialPredicate::AutoTrait(def_id) => chalk_ir::Binders::new(
-                binders.clone(),
-                chalk_ir::WhereClause::Implemented(chalk_ir::TraitRef {
-                    trait_id: chalk_ir::TraitId(def_id),
-                    substitution: interner.tcx.mk_substs_trait(self_ty, &[]).lower_into(interner),
-                }),
-            ),
         });
 
         // Binder for the bound variable representing the concrete underlying type.
diff --git a/compiler/rustc_typeck/src/astconv/mod.rs b/compiler/rustc_typeck/src/astconv/mod.rs
index 7888cb1b9f5..693cd236299 100644
--- a/compiler/rustc_typeck/src/astconv/mod.rs
+++ b/compiler/rustc_typeck/src/astconv/mod.rs
@@ -1254,22 +1254,22 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             })
         });
 
-        // Calling `skip_binder` is okay because the predicates are re-bound.
-        let regular_trait_predicates = existential_trait_refs
-            .map(|trait_ref| ty::ExistentialPredicate::Trait(trait_ref.skip_binder()));
-        let auto_trait_predicates = auto_traits
-            .into_iter()
-            .map(|trait_ref| ty::ExistentialPredicate::AutoTrait(trait_ref.trait_ref().def_id()));
+        let regular_trait_predicates = existential_trait_refs.map(|trait_ref| {
+            trait_ref.map_bound(|trait_ref| ty::ExistentialPredicate::Trait(trait_ref))
+        });
+        let auto_trait_predicates = auto_traits.into_iter().map(|trait_ref| {
+            ty::Binder::dummy(ty::ExistentialPredicate::AutoTrait(trait_ref.trait_ref().def_id()))
+        });
         let mut v = regular_trait_predicates
             .chain(auto_trait_predicates)
             .chain(
                 existential_projections
-                    .map(|x| ty::ExistentialPredicate::Projection(x.skip_binder())),
+                    .map(|x| x.map_bound(|x| ty::ExistentialPredicate::Projection(x))),
             )
             .collect::<SmallVec<[_; 8]>>();
-        v.sort_by(|a, b| a.stable_cmp(tcx, b));
+        v.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder()));
         v.dedup();
-        let existential_predicates = ty::Binder::bind(tcx.mk_existential_predicates(v.into_iter()));
+        let existential_predicates = tcx.mk_poly_existential_predicates(v.into_iter());
 
         // Use explicitly-specified region bound.
         let region_bound = if !lifetime.is_elided() {
@@ -2331,7 +2331,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     fn compute_object_lifetime_bound(
         &self,
         span: Span,
-        existential_predicates: ty::Binder<&'tcx ty::List<ty::ExistentialPredicate<'tcx>>>,
+        existential_predicates: &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>>,
     ) -> Option<ty::Region<'tcx>> // if None, use the default
     {
         let tcx = self.tcx();
diff --git a/compiler/rustc_typeck/src/check/method/suggest.rs b/compiler/rustc_typeck/src/check/method/suggest.rs
index 0f6253493cf..3bf41981ef6 100644
--- a/compiler/rustc_typeck/src/check/method/suggest.rs
+++ b/compiler/rustc_typeck/src/check/method/suggest.rs
@@ -620,8 +620,8 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                             ty::Adt(def, _) => bound_spans.push((def_span(def.did), msg)),
                             // Point at the trait object that couldn't satisfy the bound.
                             ty::Dynamic(preds, _) => {
-                                for pred in preds.skip_binder() {
-                                    match pred {
+                                for pred in preds.iter() {
+                                    match pred.skip_binder() {
                                         ty::ExistentialPredicate::Trait(tr) => {
                                             bound_spans.push((def_span(tr.def_id), msg.clone()))
                                         }
@@ -674,9 +674,9 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                         .iter()
                         .filter_map(|(pred, parent_pred)| {
                             format_pred(*pred).map(|(p, self_ty)| match parent_pred {
-                                None => format!("`{}`", p),
+                                None => format!("`{}`", &p),
                                 Some(parent_pred) => match format_pred(*parent_pred) {
-                                    None => format!("`{}`", p),
+                                    None => format!("`{}`", &p),
                                     Some((parent_p, _)) => {
                                         collect_type_param_suggestions(self_ty, parent_pred, &p);
                                         format!("`{}`\nwhich is required by `{}`", p, parent_p)