diff --git a/apex/apex.go b/apex/apex.go
index a40a753..a87187a 100644
--- a/apex/apex.go
+++ b/apex/apex.go
@@ -868,13 +868,23 @@
 	mctx.VisitDirectDeps(func(child android.Module) {
 		depName := mctx.OtherModuleName(child)
 		if am, ok := child.(android.ApexModule); ok && am.CanHaveApexVariants() &&
-			cur.DepIsInSameApex(mctx, child) {
+			(cur.DepIsInSameApex(mctx, child) || inAnySdk(child)) {
 			android.UpdateApexDependency(apexBundles, depName, directDep)
 			am.BuildForApexes(apexBundles)
 		}
 	})
 }
 
+// If a module in an APEX depends on a module from an SDK then it needs an APEX
+// specific variant created for it. Refer to sdk.sdkDepsReplaceMutator.
+func inAnySdk(module android.Module) bool {
+	if sa, ok := module.(android.SdkAware); ok {
+		return sa.IsInAnySdk()
+	}
+
+	return false
+}
+
 // Create apex variations if a module is included in APEX(s).
 func apexMutator(mctx android.BottomUpMutatorContext) {
 	if am, ok := mctx.Module().(android.ApexModule); ok && am.CanHaveApexVariants() {
@@ -1849,6 +1859,14 @@
 		apexName := ctx.ModuleName()
 		fromName := ctx.OtherModuleName(from)
 		toName := ctx.OtherModuleName(to)
+
+		// If `to` is not actually in the same APEX as `from` then it does not need apex_available and neither
+		// do any of its dependencies.
+		if am, ok := from.(android.DepIsInSameApex); ok && !am.DepIsInSameApex(ctx, to) {
+			// As soon as the dependency graph crosses the APEX boundary, don't go further.
+			return false
+		}
+
 		if to.AvailableFor(apexName) || whitelistedApexAvailable(apexName, toName) {
 			return true
 		}
diff --git a/apex/apex_test.go b/apex/apex_test.go
index a76f50d..716e263 100644
--- a/apex/apex_test.go
+++ b/apex/apex_test.go
@@ -3518,16 +3518,10 @@
 	testApexError(t, `requires "libbaz" that is not available for the APEX. Dependency path:
 .*via tag apex\.dependencyTag.*"sharedLib".*
 .*-> libfoo.*link:shared.*
-.*via tag cc\.DependencyTag.*"reuse objects".*
-.*-> libfoo.*link:static.*
-.*via tag cc\.DependencyTag.*"shared from static".*
+.*via tag cc\.DependencyTag.*"shared".*
 .*-> libbar.*link:shared.*
-.*via tag cc\.DependencyTag.*"reuse objects".*
-.*-> libbar.*link:static.*
-.*via tag cc\.DependencyTag.*"shared from static".*
-.*-> libbaz.*link:shared.*
-.*via tag cc\.DependencyTag.*"reuse objects".*
-.*-> libbaz.*link:static.*`, `
+.*via tag cc\.DependencyTag.*"shared".*
+.*-> libbaz.*link:shared.*`, `
 	apex {
 		name: "myapex",
 		key: "myapex.key",