diff --git a/meta/classes-global/base.bbclass b/meta/classes-global/base.bbclass
index dbbf6cef8c8..3d623c80a91 100644
--- a/meta/classes-global/base.bbclass
+++ b/meta/classes-global/base.bbclass
@@ -542,6 +542,24 @@ python () {
         d.setVarFlag('do_devshell', 'fakeroot', '1')
         d.appendVarFlag('do_devshell', 'depends', ' virtual/fakeroot-native:do_populate_sysroot')
 
+    # Horrible duplication with allarch as we need to set this before expanding DEPENDS below.
+    if d.getVar("PACKAGE_ARCH") == "all":
+        d.setVar("INHIBIT_DEFAULT_DEPS", "1")
+
+    # Handle recipe level PREFERRED_PROVIDERs
+    depends = (d.getVar("DEPENDS") or "").split()
+    virtprovs = (d.getVar("RECIPE_VIRTUAL_PROVIDERS") or "").split()
+    newdeps = []
+    for dep in depends:
+        if dep in virtprovs:
+            newdep = d.getVar("PREFERRED_PROVIDER_" + dep)
+            if not newdep:
+                 bb.fatal("Error, recipe virtual provider PREFERRED_PROVIDER_%s not set" % dep)
+            newdeps.append(newdep)
+        else:
+            newdeps.append(dep)
+    d.setVar("DEPENDS", " ".join(newdeps))
+
     need_machine = d.getVar('COMPATIBLE_MACHINE')
     if need_machine and not bb.utils.to_boolean(d.getVar('PARSE_ALL_RECIPES', False)):
         import re
diff --git a/meta/classes-global/staging.bbclass b/meta/classes-global/staging.bbclass
index c58ac63c57d..55581e129b6 100644
--- a/meta/classes-global/staging.bbclass
+++ b/meta/classes-global/staging.bbclass
@@ -128,8 +128,8 @@ do_populate_sysroot[vardeps] += "${SYSROOT_PREPROCESS_FUNCS}"
 do_populate_sysroot[vardepsexclude] += "BB_MULTI_PROVIDER_ALLOWED"
 
 POPULATESYSROOTDEPS = ""
-POPULATESYSROOTDEPS:class-target = "virtual/cross-binutils:do_populate_sysroot"
-POPULATESYSROOTDEPS:class-nativesdk = "virtual/sdk-binutils:do_populate_sysroot"
+POPULATESYSROOTDEPS:class-target = "${PREFERRED_PROVIDER_virtual/cross-binutils}:do_populate_sysroot"
+POPULATESYSROOTDEPS:class-nativesdk = "${PREFERRED_PROVIDER_virtual/cross-binutils}:do_populate_sysroot"
 do_populate_sysroot[depends] += "${POPULATESYSROOTDEPS}"
 
 SSTATETASKS += "do_populate_sysroot"
diff --git a/meta/classes-recipe/kernel-yocto.bbclass b/meta/classes-recipe/kernel-yocto.bbclass
index dea9eba1c2b..b8ace98787e 100644
--- a/meta/classes-recipe/kernel-yocto.bbclass
+++ b/meta/classes-recipe/kernel-yocto.bbclass
@@ -454,8 +454,8 @@ do_qa_unpack() {
     return
 }
 
-do_kernel_configme[depends] += "virtual/cross-binutils:do_populate_sysroot"
-do_kernel_configme[depends] += "virtual/cross-cc:do_populate_sysroot"
+do_kernel_configme[depends] += "${PREFERRED_PROVIDER_virtual/cross-binutils}:do_populate_sysroot"
+do_kernel_configme[depends] += "${PREFERRED_PROVIDER_virtual/cross-cc}:do_populate_sysroot"
 do_kernel_configme[depends] += "bc-native:do_populate_sysroot bison-native:do_populate_sysroot"
 do_kernel_configme[depends] += "kern-tools-native:do_populate_sysroot"
 do_kernel_configme[dirs] += "${S} ${B}"
diff --git a/meta/classes/multilib_global.bbclass b/meta/classes/multilib_global.bbclass
index c95c3a586d3..fcdda265ac7 100644
--- a/meta/classes/multilib_global.bbclass
+++ b/meta/classes/multilib_global.bbclass
@@ -155,6 +155,12 @@ def preferred_ml_updates(d):
             extramp.append(translate_provide(pref, p))
     d.setVar("BB_MULTI_PROVIDER_ALLOWED", " ".join(mp + extramp))
 
+    virtprovs = d.getVar("RECIPE_VIRTUAL_PROVIDERS").split()
+    for p in virtprovs.copy():
+        for pref in prefixes:
+            virtprovs.append(translate_provide(pref, p))
+    d.setVar("RECIPE_VIRTUAL_PROVIDERS", " ".join(virtprovs))
+
     abisafe = (d.getVar("SIGGEN_EXCLUDERECIPES_ABISAFE") or "").split()
     extras = []
     for p in prefixes:
diff --git a/meta/conf/distro/include/default-providers.inc b/meta/conf/distro/include/default-providers.inc
index 506d77811fa..881cc64a007 100644
--- a/meta/conf/distro/include/default-providers.inc
+++ b/meta/conf/distro/include/default-providers.inc
@@ -1,6 +1,7 @@
 #
 # Default virtual providers
 #
+RECIPE_VIRTUAL_PROVIDERS = "virtual/cross-cc virtual/cross-c++ virtual/cross-binutils virtual/cross-sdk-cc virtual/cross-sdk-c++ virtual/cross-sdk-binutils"
 PREFERRED_PROVIDER_virtual/xserver ?= "xserver-xorg"
 PREFERRED_PROVIDER_virtual/xserver-xf86 ?= "xserver-xorg"
 PREFERRED_PROVIDER_virtual/egl ?= "mesa"
diff --git a/meta/recipes-devtools/binutils/binutils-cross.inc b/meta/recipes-devtools/binutils/binutils-cross.inc
index b908393c1f8..9c371e7e137 100644
--- a/meta/recipes-devtools/binutils/binutils-cross.inc
+++ b/meta/recipes-devtools/binutils/binutils-cross.inc
@@ -1,5 +1,4 @@
 inherit cross
-PROVIDES = "virtual/cross-binutils"
 
 PN = "binutils-cross-${TARGET_ARCH}"
 BPN = "binutils"
diff --git a/meta/recipes-devtools/binutils/binutils-crosssdk_2.43.1.bb b/meta/recipes-devtools/binutils/binutils-crosssdk_2.43.1.bb
index afc91a9b3bd..6752659304e 100644
--- a/meta/recipes-devtools/binutils/binutils-crosssdk_2.43.1.bb
+++ b/meta/recipes-devtools/binutils/binutils-crosssdk_2.43.1.bb
@@ -1,7 +1,5 @@
 require binutils-cross_${PV}.bb
 
-PROVIDES = "virtual/cross-sdk-binutils"
-
 inherit crosssdk
 
 PN = "binutils-crosssdk-${SDK_SYS}"
diff --git a/meta/recipes-devtools/gcc/gcc-cross.inc b/meta/recipes-devtools/gcc/gcc-cross.inc
index 4549f92c2f7..7afdf585779 100644
--- a/meta/recipes-devtools/gcc/gcc-cross.inc
+++ b/meta/recipes-devtools/gcc/gcc-cross.inc
@@ -3,7 +3,6 @@ inherit cross
 INHIBIT_DEFAULT_DEPS = "1"
 EXTRADEPENDS = ""
 DEPENDS = "virtual/cross-binutils ${EXTRADEPENDS} ${NATIVEDEPS}"
-PROVIDES = "virtual/cross-cc virtual/c++"
 python () {
     if d.getVar("TARGET_OS").startswith("linux"):
         d.setVar("EXTRADEPENDS", "linux-libc-headers")