diff --git a/android/base_module_context.go b/android/base_module_context.go
index 1f89dea..06819d6 100644
--- a/android/base_module_context.go
+++ b/android/base_module_context.go
@@ -288,7 +288,7 @@
 	return b.bp.OtherModuleReverseDependencyVariantExists(name)
 }
 func (b *baseModuleContext) OtherModuleType(m blueprint.Module) string {
-	return b.bp.OtherModuleType(m)
+	return b.bp.OtherModuleType(getWrappedModule(m))
 }
 
 func (b *baseModuleContext) otherModuleProvider(m blueprint.Module, provider blueprint.AnyProviderKey) (any, bool) {
diff --git a/android/module.go b/android/module.go
index d703c19..a9f6b94 100644
--- a/android/module.go
+++ b/android/module.go
@@ -1870,6 +1870,7 @@
 	CompileTarget           Target
 	SkipAndroidMkProcessing bool
 	BaseModuleName          string
+	CanHaveApexVariants     bool
 }
 
 var CommonModuleInfoKey = blueprint.NewProvider[CommonModuleInfo]()
@@ -2145,6 +2146,8 @@
 	} else {
 		commonData.Enabled = m.commonProperties.Enabled.GetOrDefault(m.ConfigurableEvaluator(ctx), !m.Os().DefaultDisabled)
 	}
+	am, ok := m.module.(ApexModule)
+	commonData.CanHaveApexVariants = ok && am.CanHaveApexVariants()
 	SetProvider(ctx, CommonModuleInfoKey, commonData)
 	if p, ok := m.module.(PrebuiltInterface); ok && p.Prebuilt() != nil {
 		SetProvider(ctx, PrebuiltModuleProviderKey, PrebuiltModuleProviderData{})
diff --git a/apex/apex.go b/apex/apex.go
index f934134..5f700ee 100644
--- a/apex/apex.go
+++ b/apex/apex.go
@@ -1683,6 +1683,32 @@
 	})
 }
 
+func (a *apexBundle) WalkPayloadDepsProxy(ctx android.BaseModuleContext,
+	do func(ctx android.BaseModuleContext, from, to android.ModuleProxy, externalDep bool) bool) {
+	ctx.WalkDepsProxy(func(child, parent android.ModuleProxy) bool {
+		if !android.OtherModuleProviderOrDefault(ctx, child, android.CommonModuleInfoKey).CanHaveApexVariants {
+			return false
+		}
+		// Filter-out unwanted depedendencies
+		depTag := ctx.OtherModuleDependencyTag(child)
+		if _, ok := depTag.(android.ExcludeFromApexContentsTag); ok {
+			return false
+		}
+		if dt, ok := depTag.(*dependencyTag); ok && !dt.payload {
+			return false
+		}
+		if depTag == android.RequiredDepTag {
+			return false
+		}
+
+		ai, _ := android.OtherModuleProvider(ctx, child, android.ApexInfoProvider)
+		externalDep := !android.InList(ctx.ModuleName(), ai.InApexVariants)
+
+		// Visit actually
+		return do(ctx, parent, child, externalDep)
+	})
+}
+
 // filesystem type of the apex_payload.img inside the APEX. Currently, ext4 and f2fs are supported.
 type fsType int
 
@@ -2576,21 +2602,19 @@
 		librariesDirectlyInApex[ctx.OtherModuleName(dep)] = true
 	})
 
-	a.WalkPayloadDeps(ctx, func(ctx android.BaseModuleContext, from blueprint.Module, to android.ApexModule, externalDep bool) bool {
-		if ccm, ok := to.(*cc.Module); ok {
-			apexName := ctx.ModuleName()
-			fromName := ctx.OtherModuleName(from)
-			toName := ctx.OtherModuleName(to)
-
+	a.WalkPayloadDepsProxy(ctx, func(ctx android.BaseModuleContext, from, to android.ModuleProxy, externalDep bool) bool {
+		if ccInfo, ok := android.OtherModuleProvider(ctx, to, cc.CcInfoProvider); ok {
 			// 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) {
+			if externalDep {
 				// As soon as the dependency graph crosses the APEX boundary, don't go further.
 				return false
 			}
 
+			apexName := ctx.ModuleName()
+			fromName := ctx.OtherModuleName(from)
+			toName := ctx.OtherModuleName(to)
+
 			// The dynamic linker and crash_dump tool in the runtime APEX is the only
 			// exception to this rule. It can't make the static dependencies dynamic
 			// because it can't do the dynamic linking for itself.
@@ -2600,12 +2624,11 @@
 				return false
 			}
 
-			isStubLibraryFromOtherApex := ccm.HasStubsVariants() && !librariesDirectlyInApex[toName]
+			isStubLibraryFromOtherApex := ccInfo.HasStubsVariants && !librariesDirectlyInApex[toName]
 			if isStubLibraryFromOtherApex && !externalDep {
 				ctx.ModuleErrorf("%q required by %q is a native library providing stub. "+
 					"It shouldn't be included in this APEX via static linking. Dependency path: %s", to.String(), fromName, ctx.GetPathString(false))
 			}
-
 		}
 		return true
 	})
diff --git a/cc/cc.go b/cc/cc.go
index 03f738f..4838a5f 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -53,6 +53,13 @@
 
 var CcObjectInfoProvider = blueprint.NewProvider[CcObjectInfo]()
 
+// Common info about the cc module.
+type CcInfo struct {
+	HasStubsVariants bool
+}
+
+var CcInfoProvider = blueprint.NewProvider[CcInfo]()
+
 type LinkableInfo struct {
 	// StaticExecutable returns true if this is a binary module with "static_executable: true".
 	StaticExecutable bool
@@ -2124,6 +2131,10 @@
 		StaticExecutable: c.StaticExecutable(),
 	})
 
+	android.SetProvider(ctx, CcInfoProvider, CcInfo{
+		HasStubsVariants: c.HasStubsVariants(),
+	})
+
 	c.setOutputFiles(ctx)
 
 	if c.makeVarsInfo != nil {