diff --git a/cc/cc.go b/cc/cc.go
index 8a0bf71..b8cbf26 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -39,7 +39,7 @@
 		ctx.BottomUp("vndk", vndkMutator).Parallel()
 		ctx.BottomUp("ndk_api", ndkApiMutator).Parallel()
 		ctx.BottomUp("test_per_src", testPerSrcMutator).Parallel()
-		ctx.BottomUp("version", versionMutator).Parallel()
+		ctx.BottomUp("version", VersionMutator).Parallel()
 		ctx.BottomUp("begin", BeginMutator).Parallel()
 	})
 
@@ -248,6 +248,7 @@
 	getVndkExtendsModuleName() string
 	isPgoCompile() bool
 	useClangLld(actx ModuleContext) bool
+	isApex() bool
 }
 
 type ModuleContext interface {
@@ -308,6 +309,8 @@
 	library bool
 
 	reexportFlags bool
+
+	explicitlyVersioned bool
 }
 
 var (
@@ -511,6 +514,20 @@
 	return c.ModuleBase.InstallInRecovery()
 }
 
+func (c *Module) IsStubs() bool {
+	if library, ok := c.linker.(*libraryDecorator); ok {
+		return library.buildStubs()
+	}
+	return false
+}
+
+func (c *Module) HasStubsVariants() bool {
+	if library, ok := c.linker.(*libraryDecorator); ok {
+		return len(library.Properties.Stubs.Versions) > 0
+	}
+	return false
+}
+
 type baseModuleContext struct {
 	android.BaseContext
 	moduleContextImpl
@@ -649,6 +666,11 @@
 	return ctx.mod.getVndkExtendsModuleName()
 }
 
+// Tests if this module is built for APEX
+func (ctx *moduleContextImpl) isApex() bool {
+	return ctx.mod.ApexName() != ""
+}
+
 func newBaseModule(hod android.HostOrDeviceSupported, multilib android.Multilib) *Module {
 	return &Module{
 		hod:      hod,
@@ -1081,6 +1103,30 @@
 		{Mutator: "link", Variation: "static"},
 	}, lateStaticDepTag, deps.LateStaticLibs...)
 
+	addSharedLibDependencies := func(depTag dependencyTag, name string, version string) {
+		var variations []blueprint.Variation
+		variations = append(variations, blueprint.Variation{Mutator: "link", Variation: "shared"})
+		versionVariantAvail := ctx.Os() == android.Android && !ctx.useVndk() && !c.inRecovery()
+		if version != "" && versionVariantAvail {
+			// Version is explicitly specified. i.e. libFoo#30
+			variations = append(variations, blueprint.Variation{Mutator: "version", Variation: version})
+			depTag.explicitlyVersioned = true
+		}
+		actx.AddVariationDependencies(variations, depTag, name)
+
+		// If the version is not specified, add dependency to the latest stubs library.
+		// The stubs library will be used when the depending module is built for APEX and
+		// the dependent module is not in the same APEX.
+		latestVersion := latestStubsVersionFor(actx.Config(), name)
+		if version == "" && latestVersion != "" && versionVariantAvail {
+			actx.AddVariationDependencies([]blueprint.Variation{
+				{Mutator: "link", Variation: "shared"},
+				{Mutator: "version", Variation: latestVersion},
+			}, depTag, name)
+			// Note that depTag.explicitlyVersioned is false in this case.
+		}
+	}
+
 	// shared lib names without the #version suffix
 	var sharedLibNames []string
 
@@ -1091,29 +1137,17 @@
 		if inList(lib, deps.ReexportSharedLibHeaders) {
 			depTag = sharedExportDepTag
 		}
-		var variations []blueprint.Variation
-		variations = append(variations, blueprint.Variation{Mutator: "link", Variation: "shared"})
-		if version != "" && ctx.Os() == android.Android && !ctx.useVndk() && !c.inRecovery() {
-			variations = append(variations, blueprint.Variation{Mutator: "version", Variation: version})
-		}
-		actx.AddVariationDependencies(variations, depTag, name)
+		addSharedLibDependencies(depTag, name, version)
 	}
 
 	for _, lib := range deps.LateSharedLibs {
-		name, version := stubsLibNameAndVersion(lib)
-		if inList(name, sharedLibNames) {
+		if inList(lib, sharedLibNames) {
 			// This is to handle the case that some of the late shared libs (libc, libdl, libm, ...)
 			// are added also to SharedLibs with version (e.g., libc#10). If not skipped, we will be
 			// linking against both the stubs lib and the non-stubs lib at the same time.
 			continue
 		}
-		depTag := lateSharedDepTag
-		var variations []blueprint.Variation
-		variations = append(variations, blueprint.Variation{Mutator: "link", Variation: "shared"})
-		if version != "" && ctx.Os() == android.Android && !ctx.useVndk() && !c.inRecovery() {
-			variations = append(variations, blueprint.Variation{Mutator: "version", Variation: version})
-		}
-		actx.AddVariationDependencies(variations, depTag, name)
+		addSharedLibDependencies(lateSharedDepTag, lib, "")
 	}
 
 	actx.AddVariationDependencies([]blueprint.Variation{
@@ -1372,7 +1406,53 @@
 				return
 			}
 		}
+
+		// Extract explicitlyVersioned field from the depTag and reset it inside the struct.
+		// Otherwise, sharedDepTag and lateSharedDepTag with explicitlyVersioned set to true
+		// won't be matched to sharedDepTag and lateSharedDepTag.
+		explicitlyVersioned := false
+		if t, ok := depTag.(dependencyTag); ok {
+			explicitlyVersioned = t.explicitlyVersioned
+			t.explicitlyVersioned = false
+			depTag = t
+		}
+
 		if t, ok := depTag.(dependencyTag); ok && t.library {
+			if dependentLibrary, ok := ccDep.linker.(*libraryDecorator); ok {
+				depIsStubs := dependentLibrary.buildStubs()
+				depHasStubs := ccDep.HasStubsVariants()
+				depNameWithTarget := depName + "-" + ccDep.Target().String()
+				depInSameApex := android.DirectlyInApex(ctx.Config(), c.ApexName(), depNameWithTarget)
+				depInPlatform := !android.DirectlyInAnyApex(ctx.Config(), depNameWithTarget)
+
+				var useThisDep bool
+				if depIsStubs && explicitlyVersioned {
+					// Always respect dependency to the versioned stubs (i.e. libX#10)
+					useThisDep = true
+				} else if !depHasStubs {
+					// Use non-stub variant if that is the only choice
+					// (i.e. depending on a lib without stubs.version property)
+					useThisDep = true
+				} else if c.IsForPlatform() {
+					// If not building for APEX, use stubs only when it is from
+					// an APEX (and not from platform)
+					useThisDep = (depInPlatform != depIsStubs)
+					if c.inRecovery() {
+						// However, for recovery modules, since there is no APEX there,
+						// always link to non-stub variant
+						useThisDep = !depIsStubs
+					}
+				} else {
+					// If building for APEX, use stubs only when it is not from
+					// the same APEX
+					useThisDep = (depInSameApex != depIsStubs)
+				}
+
+				if !useThisDep {
+					return // stop processing this dep
+				}
+			}
+
 			if i, ok := ccDep.linker.(exportedFlagsProducer); ok {
 				flags := i.exportedFlags()
 				deps := i.exportedFlagsDeps()
diff --git a/cc/cc_test.go b/cc/cc_test.go
index 41f633a..e368fb3 100644
--- a/cc/cc_test.go
+++ b/cc/cc_test.go
@@ -66,7 +66,7 @@
 		ctx.BottomUp("image", imageMutator).Parallel()
 		ctx.BottomUp("link", LinkageMutator).Parallel()
 		ctx.BottomUp("vndk", vndkMutator).Parallel()
-		ctx.BottomUp("version", versionMutator).Parallel()
+		ctx.BottomUp("version", VersionMutator).Parallel()
 		ctx.BottomUp("begin", BeginMutator).Parallel()
 	})
 	ctx.Register()
diff --git a/cc/library.go b/cc/library.go
index 8b8fe02..822274a 100644
--- a/cc/library.go
+++ b/cc/library.go
@@ -16,6 +16,8 @@
 
 import (
 	"regexp"
+	"sort"
+	"strconv"
 	"strings"
 	"sync"
 
@@ -981,30 +983,65 @@
 	}
 }
 
+// maps a module name to the list of stubs versions available for the module
+func stubsVersionsFor(config android.Config) map[string][]string {
+	return config.Once("stubVersions", func() interface{} {
+		return make(map[string][]string)
+	}).(map[string][]string)
+}
+
+var stubsVersionsLock sync.Mutex
+
+func latestStubsVersionFor(config android.Config, name string) string {
+	versions, ok := stubsVersionsFor(config)[name]
+	if ok && len(versions) > 0 {
+		// the versions are alreay sorted in ascending order
+		return versions[len(versions)-1]
+	}
+	return ""
+}
+
 // Version mutator splits a module into the mandatory non-stubs variant
-// (which is named "impl") and zero or more stubs variants.
-func versionMutator(mctx android.BottomUpMutatorContext) {
+// (which is unnamed) and zero or more stubs variants.
+func VersionMutator(mctx android.BottomUpMutatorContext) {
 	if mctx.Os() != android.Android {
 		return
 	}
 
 	if m, ok := mctx.Module().(*Module); ok && !m.inRecovery() && m.linker != nil {
-		if library, ok := m.linker.(*libraryDecorator); ok && library.buildShared() {
-			versions := []string{""}
+		if library, ok := m.linker.(*libraryDecorator); ok && library.buildShared() &&
+			len(library.Properties.Stubs.Versions) > 0 {
+			versions := []string{}
 			for _, v := range library.Properties.Stubs.Versions {
+				if _, err := strconv.Atoi(v); err != nil {
+					mctx.PropertyErrorf("versions", "%q is not a number", v)
+				}
 				versions = append(versions, v)
 			}
+			sort.Slice(versions, func(i, j int) bool {
+				left, _ := strconv.Atoi(versions[i])
+				right, _ := strconv.Atoi(versions[j])
+				return left < right
+			})
+
+			// save the list of versions for later use
+			copiedVersions := make([]string, len(versions))
+			copy(copiedVersions, versions)
+			stubsVersionsLock.Lock()
+			defer stubsVersionsLock.Unlock()
+			stubsVersionsFor(mctx.Config())[mctx.ModuleName()] = copiedVersions
+
+			// "" is for the non-stubs variant
+			versions = append(versions, "")
+
 			modules := mctx.CreateVariations(versions...)
 			for i, m := range modules {
 				l := m.(*Module).linker.(*libraryDecorator)
-				if i == 0 {
-					l.MutatedProperties.BuildStubs = false
-					continue
+				if versions[i] != "" {
+					l.MutatedProperties.BuildStubs = true
+					l.MutatedProperties.StubsVersion = versions[i]
+					m.(*Module).Properties.HideFromMake = true
 				}
-				// Mark that this variant is for stubs.
-				l.MutatedProperties.BuildStubs = true
-				l.MutatedProperties.StubsVersion = versions[i]
-				m.(*Module).Properties.HideFromMake = true
 			}
 		} else {
 			mctx.CreateVariations("")