diff --git a/android/apex.go b/android/apex.go
index 47f07ca..a7570dc 100644
--- a/android/apex.go
+++ b/android/apex.go
@@ -65,9 +65,9 @@
 
 	apexModuleBase() *ApexModuleBase
 
-	// Marks that this module should be built for the specified APEXes.
+	// Marks that this module should be built for the specified APEX.
 	// Call this before apex.apexMutator is run.
-	BuildForApexes(apexes []ApexInfo)
+	BuildForApex(apex ApexInfo)
 
 	// Returns the APEXes that this module will be built for
 	ApexVariations() []ApexInfo
@@ -96,7 +96,7 @@
 	IsInstallableToApex() bool
 
 	// Mutate this module into one or more variants each of which is built
-	// for an APEX marked via BuildForApexes().
+	// for an APEX marked via BuildForApex().
 	CreateApexVariations(mctx BottomUpMutatorContext) []Module
 
 	// Tests if this module is available for the specified APEX or ":platform"
@@ -178,18 +178,15 @@
 	return nil
 }
 
-func (m *ApexModuleBase) BuildForApexes(apexes []ApexInfo) {
+func (m *ApexModuleBase) BuildForApex(apex ApexInfo) {
 	m.apexVariationsLock.Lock()
 	defer m.apexVariationsLock.Unlock()
-nextApex:
-	for _, apex := range apexes {
-		for _, v := range m.apexVariations {
-			if v.ApexName == apex.ApexName {
-				continue nextApex
-			}
+	for _, v := range m.apexVariations {
+		if v.ApexName == apex.ApexName {
+			return
 		}
-		m.apexVariations = append(m.apexVariations, apex)
 	}
+	m.apexVariations = append(m.apexVariations, apex)
 }
 
 func (m *ApexModuleBase) ApexVariations() []ApexInfo {
@@ -327,17 +324,15 @@
 // depended on by the specified APEXes. Directly depending means that a module
 // is explicitly listed in the build definition of the APEX via properties like
 // native_shared_libs, java_libs, etc.
-func UpdateApexDependency(apexes []ApexInfo, moduleName string, directDep bool) {
+func UpdateApexDependency(apex ApexInfo, moduleName string, directDep bool) {
 	apexNamesMapMutex.Lock()
 	defer apexNamesMapMutex.Unlock()
-	for _, apex := range apexes {
-		apexesForModule, ok := apexNamesMap()[moduleName]
-		if !ok {
-			apexesForModule = make(map[string]bool)
-			apexNamesMap()[moduleName] = apexesForModule
-		}
-		apexesForModule[apex.ApexName] = apexesForModule[apex.ApexName] || directDep
+	apexesForModule, ok := apexNamesMap()[moduleName]
+	if !ok {
+		apexesForModule = make(map[string]bool)
+		apexNamesMap()[moduleName] = apexesForModule
 	}
+	apexesForModule[apex.ApexName] = apexesForModule[apex.ApexName] || directDep
 }
 
 // TODO(b/146393795): remove this when b/146393795 is fixed
diff --git a/apex/apex.go b/apex/apex.go
index d0c4e6e..de9b344 100644
--- a/apex/apex.go
+++ b/apex/apex.go
@@ -669,7 +669,7 @@
 }
 
 func RegisterPostDepsMutators(ctx android.RegisterMutatorsContext) {
-	ctx.TopDown("apex_deps", apexDepsMutator)
+	ctx.TopDown("apex_deps", apexDepsMutator).Parallel()
 	ctx.BottomUp("apex", apexMutator).Parallel()
 	ctx.BottomUp("apex_flattened", apexFlattenedMutator).Parallel()
 	ctx.BottomUp("apex_uses", apexUsesMutator).Parallel()
@@ -682,33 +682,30 @@
 	if !mctx.Module().Enabled() {
 		return
 	}
-	var apexBundles []android.ApexInfo
-	var directDep bool
-	if a, ok := mctx.Module().(*apexBundle); ok && !a.vndkApex {
-		apexBundles = []android.ApexInfo{{
-			ApexName:      mctx.ModuleName(),
-			MinSdkVersion: a.minSdkVersion(mctx),
-			Updatable:     a.Updatable(),
-		}}
-		directDep = true
-	} else if am, ok := mctx.Module().(android.ApexModule); ok {
-		apexBundles = am.ApexVariations()
-		directDep = false
-	}
-
-	if len(apexBundles) == 0 {
+	a, ok := mctx.Module().(*apexBundle)
+	if !ok || a.vndkApex {
 		return
 	}
-
-	cur := mctx.Module().(android.DepIsInSameApex)
-
-	mctx.VisitDirectDeps(func(child android.Module) {
-		depName := mctx.OtherModuleName(child)
-		if am, ok := child.(android.ApexModule); ok && am.CanHaveApexVariants() &&
-			(cur.DepIsInSameApex(mctx, child) || inAnySdk(child)) {
-			android.UpdateApexDependency(apexBundles, depName, directDep)
-			am.BuildForApexes(apexBundles)
+	apexInfo := android.ApexInfo{
+		ApexName:      mctx.ModuleName(),
+		MinSdkVersion: a.minSdkVersion(mctx),
+		Updatable:     a.Updatable(),
+	}
+	mctx.WalkDeps(func(child, parent android.Module) bool {
+		am, ok := child.(android.ApexModule)
+		if !ok || !am.CanHaveApexVariants() {
+			return false
 		}
+		if !parent.(android.DepIsInSameApex).DepIsInSameApex(mctx, child) && !inAnySdk(child) {
+			return false
+		}
+
+		depName := mctx.OtherModuleName(child)
+		// If the parent is apexBundle, this child is directly depended.
+		_, directDep := parent.(*apexBundle)
+		android.UpdateApexDependency(apexInfo, depName, directDep)
+		am.BuildForApex(apexInfo)
+		return true
 	})
 }