diff --git a/android/apex.go b/android/apex.go
index f625baf..78511f9 100644
--- a/android/apex.go
+++ b/android/apex.go
@@ -77,6 +77,9 @@
 
 	// Returns the value of `apex_available_name`
 	ApexAvailableName string
+
+	// Returns the apex names that this module is available for
+	ApexAvailableFor []string
 }
 
 // AllApexInfo holds the ApexInfo of all apexes that include this module.
@@ -213,6 +216,12 @@
 	// apex_available property of the module.
 	AvailableFor(what string) bool
 
+	// Returns the apexes that are available for this module, valid values include
+	// "//apex_available:platform", "//apex_available:anyapex" and specific apexes.
+	// There are some differences between this one and the ApexAvailable on
+	// ApexModuleBase for cc, java library and sdkLibraryXml.
+	ApexAvailableFor() []string
+
 	// AlwaysRequiresPlatformApexVariant allows the implementing module to determine whether an
 	// APEX mutator should always be created for it.
 	//
@@ -320,6 +329,10 @@
 	return CopyOf(availableToPlatformList)
 }
 
+func (m *ApexModuleBase) ApexAvailableFor() []string {
+	return m.ApexAvailable()
+}
+
 // Implements ApexModule
 func (m *ApexModuleBase) BuildForApex(apex ApexInfo) {
 	m.apexInfosLock.Lock()
@@ -420,7 +433,7 @@
 
 // Implements ApexModule
 func (m *ApexModuleBase) AvailableFor(what string) bool {
-	return CheckAvailableForApex(what, m.ApexProperties.Apex_available)
+	return CheckAvailableForApex(what, m.ApexAvailableFor())
 }
 
 // Implements ApexModule
@@ -614,6 +627,7 @@
 		} else {
 			panic(fmt.Errorf("failed to find apexInfo for incoming variation %q", variation))
 		}
+		thisApexInfo.ApexAvailableFor = module.ApexAvailableFor()
 
 		SetProvider(ctx, ApexInfoProvider, thisApexInfo)
 	}
diff --git a/android/module_proxy.go b/android/module_proxy.go
index 30459b9..8cc8fa1 100644
--- a/android/module_proxy.go
+++ b/android/module_proxy.go
@@ -189,7 +189,7 @@
 }
 
 func (m ModuleProxy) String() string {
-	return m.module.Name()
+	return m.module.String()
 }
 
 func (m ModuleProxy) qualifiedModuleId(ctx BaseModuleContext) qualifiedModuleName {
diff --git a/apex/apex.go b/apex/apex.go
index e22cf9e..912780d 100644
--- a/apex/apex.go
+++ b/apex/apex.go
@@ -2694,7 +2694,7 @@
 		return
 	}
 
-	a.WalkPayloadDeps(ctx, func(ctx android.BaseModuleContext, from android.Module, to android.ApexModule, externalDep bool) bool {
+	a.WalkPayloadDepsProxy(ctx, func(ctx android.BaseModuleContext, from, to android.ModuleProxy, externalDep bool) bool {
 		// As soon as the dependency graph crosses the APEX boundary, don't go further.
 		if externalDep {
 			return false
@@ -2711,17 +2711,8 @@
 		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.
-		//
-		// It is ok to call DepIsInSameApex() directly from within WalkPayloadDeps().
-		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) {
+		if android.CheckAvailableForApex(apexName,
+			android.OtherModuleProviderOrDefault(ctx, to, android.ApexInfoProvider).ApexAvailableFor) {
 			return true
 		}
 
diff --git a/apex/apex_test.go b/apex/apex_test.go
index 282cd1d..12cf6a6 100644
--- a/apex/apex_test.go
+++ b/apex/apex_test.go
@@ -6353,10 +6353,16 @@
 	testApexError(t, `requires "libbaz" that doesn't list the APEX under 'apex_available'.\n\nDependency path:
 .*via tag apex\.dependencyTag\{"sharedLib"\}
 .*-> libfoo.*link:shared.*
+.*via tag cc\.dependencyTag.*
+.*-> libfoo.*link:static.*
 .*via tag cc\.libraryDependencyTag.*Kind:sharedLibraryDependency.*
 .*-> libbar.*link:shared.*
+.*via tag cc\.dependencyTag.*
+.*-> libbar.*link:static.*
 .*via tag cc\.libraryDependencyTag.*Kind:sharedLibraryDependency.*
-.*-> libbaz.*link:shared.*`, `
+.*-> libbaz.*link:shared.*
+.*via tag cc\.dependencyTag.*
+.*-> libbaz.*link:static.*`, `
 	apex {
 		name: "myapex",
 		key: "myapex.key",
diff --git a/cc/cc.go b/cc/cc.go
index 8023324..e51cfcf 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -3689,13 +3689,18 @@
 }
 
 func (c *Module) AvailableFor(what string) bool {
+	return android.CheckAvailableForApex(what, c.ApexAvailableFor())
+}
+
+func (c *Module) ApexAvailableFor() []string {
+	list := c.ApexModuleBase.ApexAvailable()
 	if linker, ok := c.linker.(interface {
-		availableFor(string) bool
+		apexAvailable() []string
 	}); ok {
-		return c.ApexModuleBase.AvailableFor(what) || linker.availableFor(what)
-	} else {
-		return c.ApexModuleBase.AvailableFor(what)
+		list = append(list, linker.apexAvailable()...)
 	}
+
+	return android.FirstUniqueStrings(list)
 }
 
 func (c *Module) EverInstallable() bool {
diff --git a/cc/library.go b/cc/library.go
index 6485ea3..ebc65ef 100644
--- a/cc/library.go
+++ b/cc/library.go
@@ -723,7 +723,7 @@
 	// Write LOCAL_ADDITIONAL_DEPENDENCIES for ABI diff
 	androidMkWriteAdditionalDependenciesForSourceAbiDiff(w io.Writer)
 
-	availableFor(string) bool
+	apexAvailable() []string
 
 	getAPIListCoverageXMLPath() android.ModuleOutPath
 
@@ -1959,17 +1959,15 @@
 	return library.MutatedProperties.IsLatestVersion
 }
 
-func (library *libraryDecorator) availableFor(what string) bool {
+func (library *libraryDecorator) apexAvailable() []string {
 	var list []string
 	if library.static() {
 		list = library.StaticProperties.Static.Apex_available
 	} else if library.shared() {
 		list = library.SharedProperties.Shared.Apex_available
 	}
-	if len(list) == 0 {
-		return false
-	}
-	return android.CheckAvailableForApex(what, list)
+
+	return list
 }
 
 func (library *libraryDecorator) installable() *bool {
diff --git a/java/base.go b/java/base.go
index f26404b..b579a5d 100644
--- a/java/base.go
+++ b/java/base.go
@@ -838,13 +838,18 @@
 }
 
 func (j *Module) AvailableFor(what string) bool {
-	if what == android.AvailableToPlatform && Bool(j.deviceProperties.Hostdex) {
+	return android.CheckAvailableForApex(what, j.ApexAvailableFor())
+}
+
+func (j *Module) ApexAvailableFor() []string {
+	list := j.ApexModuleBase.ApexAvailable()
+	if Bool(j.deviceProperties.Hostdex) {
 		// Exception: for hostdex: true libraries, the platform variant is created
 		// even if it's not marked as available to platform. In that case, the platform
 		// variant is used only for the hostdex and not installed to the device.
-		return true
+		list = append(list, android.AvailableToPlatform)
 	}
-	return j.ApexModuleBase.AvailableFor(what)
+	return android.FirstUniqueStrings(list)
 }
 
 func (j *Module) staticLibs(ctx android.BaseModuleContext) []string {
diff --git a/java/sdk_library_internal.go b/java/sdk_library_internal.go
index 768e57a..ec9c160 100644
--- a/java/sdk_library_internal.go
+++ b/java/sdk_library_internal.go
@@ -15,12 +15,13 @@
 package java
 
 import (
-	"android/soong/android"
-	"android/soong/etc"
 	"fmt"
 	"path"
 	"strings"
 
+	"android/soong/android"
+	"android/soong/etc"
+
 	"github.com/google/blueprint/proptools"
 )
 
@@ -778,7 +779,11 @@
 
 // from android.ApexModule
 func (module *sdkLibraryXml) AvailableFor(what string) bool {
-	return true
+	return android.CheckAvailableForApex(what, module.ApexAvailableFor())
+}
+
+func (module *sdkLibraryXml) ApexAvailableFor() []string {
+	return []string{android.AvailableToPlatform, android.AvailableToAnyApex}
 }
 
 func (module *sdkLibraryXml) DepsMutator(ctx android.BottomUpMutatorContext) {