diff --git a/dexpreopt/class_loader_context.go b/dexpreopt/class_loader_context.go
index 2b6ec79..77d6ee9 100644
--- a/dexpreopt/class_loader_context.go
+++ b/dexpreopt/class_loader_context.go
@@ -171,7 +171,23 @@
 }
 
 // Merge the other class loader context map into this one, do not override existing entries.
-func (clcMap ClassLoaderContextMap) AddContextMap(otherClcMap ClassLoaderContextMap) {
+// The implicitRootLib parameter is the name of the library for which the other class loader
+// context map was constructed. If the implicitRootLib is itself a <uses-library>, it should be
+// already present in the class loader context (with the other context as its subcontext) -- in
+// that case do not re-add the other context. Otherwise add the other context at the top-level.
+func (clcMap ClassLoaderContextMap) AddContextMap(otherClcMap ClassLoaderContextMap, implicitRootLib string) {
+	if otherClcMap == nil {
+		return
+	}
+
+	// If the implicit root of the merged map is already present as one of top-level subtrees, do
+	// not merge it second time.
+	for _, clc := range clcMap[AnySdkVersion] {
+		if clc.Name == implicitRootLib {
+			return
+		}
+	}
+
 	for sdkVer, otherClcs := range otherClcMap {
 		for _, otherClc := range otherClcs {
 			alreadyHave := false
diff --git a/dexpreopt/class_loader_context_test.go b/dexpreopt/class_loader_context_test.go
index aed3543..e0a75bf 100644
--- a/dexpreopt/class_loader_context_test.go
+++ b/dexpreopt/class_loader_context_test.go
@@ -80,7 +80,12 @@
 	// from conditional context.
 	m.AddContextForSdk(ctx, 42, "f", buildPath(ctx, "f"), installPath(ctx, "f"), nil)
 	m.AddContextForSdk(ctx, AnySdkVersion, "f", buildPath(ctx, "f"), installPath(ctx, "f"), nil)
-	m.AddContextMap(m3)
+
+	// Merge map with implicit root library that is among toplevel contexts => does nothing.
+	m.AddContextMap(m1, "c")
+	// Merge map with implicit root library that is not among toplevel contexts => all subcontexts
+	// of the other map are added as toplevel contexts.
+	m.AddContextMap(m3, "m_g")
 
 	// Compatibility libraries with unknown install paths get default paths.
 	m.AddContextForSdk(ctx, 29, AndroidHidlManager, buildPath(ctx, AndroidHidlManager), nil, nil)
diff --git a/java/aar.go b/java/aar.go
index c8faed0..7c3840b 100644
--- a/java/aar.go
+++ b/java/aar.go
@@ -109,7 +109,6 @@
 	useEmbeddedNativeLibs   bool
 	useEmbeddedDex          bool
 	usesNonSdkApis          bool
-	sdkLibraries            dexpreopt.ClassLoaderContextMap
 	hasNoCode               bool
 	LoggingParent           string
 	resourceFiles           android.Paths
@@ -259,12 +258,11 @@
 		CommandDeps: []string{"${config.Zip2ZipCmd}"},
 	})
 
-func (a *aapt) buildActions(ctx android.ModuleContext, sdkContext sdkContext, extraLinkFlags ...string) {
+func (a *aapt) buildActions(ctx android.ModuleContext, sdkContext sdkContext,
+	sdkLibraries dexpreopt.ClassLoaderContextMap, extraLinkFlags ...string) {
 
-	transitiveStaticLibs, transitiveStaticLibManifests, staticRRODirs, assetPackages, libDeps, libFlags, sdkLibraries :=
-		aaptLibs(ctx, sdkContext)
-
-	a.sdkLibraries = sdkLibraries
+	transitiveStaticLibs, transitiveStaticLibManifests, staticRRODirs, assetPackages, libDeps, libFlags :=
+		aaptLibs(ctx, sdkContext, sdkLibraries)
 
 	// App manifest file
 	manifestFile := proptools.StringDefault(a.aaptProperties.Manifest, "AndroidManifest.xml")
@@ -391,29 +389,31 @@
 }
 
 // aaptLibs collects libraries from dependencies and sdk_version and converts them into paths
-func aaptLibs(ctx android.ModuleContext, sdkContext sdkContext) (transitiveStaticLibs, transitiveStaticLibManifests android.Paths,
-	staticRRODirs []rroDir, assets, deps android.Paths, flags []string, sdkLibraries dexpreopt.ClassLoaderContextMap) {
+func aaptLibs(ctx android.ModuleContext, sdkContext sdkContext, sdkLibraries dexpreopt.ClassLoaderContextMap) (
+	transitiveStaticLibs, transitiveStaticLibManifests android.Paths, staticRRODirs []rroDir, assets, deps android.Paths, flags []string) {
 
 	var sharedLibs android.Paths
 
+	if sdkLibraries == nil {
+		// Not all callers need to compute class loader context, those who don't just pass nil.
+		// Create a temporary class loader context here (it will be computed, but not used).
+		sdkLibraries = make(dexpreopt.ClassLoaderContextMap)
+	}
+
 	sdkDep := decodeSdkDep(ctx, sdkContext)
 	if sdkDep.useFiles {
 		sharedLibs = append(sharedLibs, sdkDep.jars...)
 	}
 
-	sdkLibraries = make(dexpreopt.ClassLoaderContextMap)
-
 	ctx.VisitDirectDeps(func(module android.Module) {
+		depName := ctx.OtherModuleName(module)
+
 		var exportPackage android.Path
 		aarDep, _ := module.(AndroidLibraryDependency)
 		if aarDep != nil {
 			exportPackage = aarDep.ExportPackage()
 		}
 
-		if dep, ok := module.(Dependency); ok {
-			sdkLibraries.AddContextMap(dep.ExportedSdkLibs())
-		}
-
 		switch ctx.OtherModuleDependencyTag(module) {
 		case instrumentationForTag:
 			// Nothing, instrumentationForTag is treated as libTag for javac but not for aapt2.
@@ -439,7 +439,7 @@
 				transitiveStaticLibs = append(transitiveStaticLibs, aarDep.ExportedStaticPackages()...)
 				transitiveStaticLibs = append(transitiveStaticLibs, exportPackage)
 				transitiveStaticLibManifests = append(transitiveStaticLibManifests, aarDep.ExportedManifests()...)
-				sdkLibraries.AddContextMap(aarDep.ExportedSdkLibs())
+				sdkLibraries.AddContextMap(aarDep.ExportedSdkLibs(), depName)
 				if aarDep.ExportedAssets().Valid() {
 					assets = append(assets, aarDep.ExportedAssets().Path())
 				}
@@ -457,6 +457,12 @@
 				}
 			}
 		}
+
+		// Add nested dependencies after processing the direct dependency: if it is a <uses-library>,
+		// nested context is added as its subcontext, and should not be re-added at the top-level.
+		if dep, ok := module.(Dependency); ok {
+			sdkLibraries.AddContextMap(dep.ExportedSdkLibs(), depName)
+		}
 	})
 
 	deps = append(deps, sharedLibs...)
@@ -473,7 +479,7 @@
 	transitiveStaticLibs = android.FirstUniquePaths(transitiveStaticLibs)
 	transitiveStaticLibManifests = android.FirstUniquePaths(transitiveStaticLibManifests)
 
-	return transitiveStaticLibs, transitiveStaticLibManifests, staticRRODirs, assets, deps, flags, sdkLibraries
+	return transitiveStaticLibs, transitiveStaticLibManifests, staticRRODirs, assets, deps, flags
 }
 
 type AndroidLibrary struct {
@@ -508,8 +514,8 @@
 
 func (a *AndroidLibrary) GenerateAndroidBuildActions(ctx android.ModuleContext) {
 	a.aapt.isLibrary = true
-	a.aapt.buildActions(ctx, sdkContext(a))
-	a.exportedSdkLibs = a.aapt.sdkLibraries
+	a.exportedSdkLibs = make(dexpreopt.ClassLoaderContextMap)
+	a.aapt.buildActions(ctx, sdkContext(a), a.exportedSdkLibs)
 
 	a.hideApexVariantFromMake = !ctx.Provider(android.ApexInfoProvider).(android.ApexInfo).IsForPlatform()
 
@@ -781,12 +787,11 @@
 	linkFlags = append(linkFlags, "--manifest "+a.manifest.String())
 	linkDeps = append(linkDeps, a.manifest)
 
-	transitiveStaticLibs, staticLibManifests, staticRRODirs, transitiveAssets, libDeps, libFlags, sdkLibraries :=
-		aaptLibs(ctx, sdkContext(a))
+	transitiveStaticLibs, staticLibManifests, staticRRODirs, transitiveAssets, libDeps, libFlags :=
+		aaptLibs(ctx, sdkContext(a), nil)
 
 	_ = staticLibManifests
 	_ = staticRRODirs
-	_ = sdkLibraries
 
 	linkDeps = append(linkDeps, libDeps...)
 	linkFlags = append(linkFlags, libFlags...)
diff --git a/java/app.go b/java/app.go
index 4848fae..9ff413c 100755
--- a/java/app.go
+++ b/java/app.go
@@ -565,9 +565,8 @@
 	aaptLinkFlags = append(aaptLinkFlags, a.additionalAaptFlags...)
 
 	a.aapt.splitNames = a.appProperties.Package_splits
-	a.aapt.sdkLibraries = a.exportedSdkLibs
 	a.aapt.LoggingParent = String(a.overridableAppProperties.Logging_parent)
-	a.aapt.buildActions(ctx, sdkContext(a), aaptLinkFlags...)
+	a.aapt.buildActions(ctx, sdkContext(a), a.exportedSdkLibs, aaptLinkFlags...)
 
 	// apps manifests are handled by aapt, don't let Module see them
 	a.properties.Manifest = nil
@@ -601,7 +600,7 @@
 	return android.PathForModuleInstall(ctx, installDir, a.installApkName+".apk")
 }
 
-func (a *AndroidApp) dexBuildActions(ctx android.ModuleContext, sdkLibs dexpreopt.ClassLoaderContextMap) android.Path {
+func (a *AndroidApp) dexBuildActions(ctx android.ModuleContext) android.Path {
 	a.dexpreopter.installPath = a.installPath(ctx)
 	if a.dexProperties.Uncompress_dex == nil {
 		// If the value was not force-set by the user, use reasonable default based on the module.
@@ -609,10 +608,8 @@
 	}
 	a.dexpreopter.uncompressedDex = *a.dexProperties.Uncompress_dex
 	a.dexpreopter.enforceUsesLibs = a.usesLibrary.enforceUsesLibraries()
-	a.dexpreopter.classLoaderContexts = a.usesLibrary.classLoaderContextForUsesLibDeps(ctx)
-	a.dexpreopter.classLoaderContexts.AddContextMap(sdkLibs)
+	a.dexpreopter.classLoaderContexts = a.exportedSdkLibs
 	a.dexpreopter.manifestFile = a.mergedManifestFile
-	a.exportedSdkLibs = make(dexpreopt.ClassLoaderContextMap)
 
 	if ctx.ModuleName() != "framework-res" {
 		a.Module.compile(ctx, a.aaptSrcJar)
@@ -782,6 +779,8 @@
 		a.aapt.noticeFile = a.noticeOutputs.HtmlGzOutput
 	}
 
+	a.exportedSdkLibs = a.usesLibrary.classLoaderContextForUsesLibDeps(ctx)
+
 	// Process all building blocks, from AAPT to certificates.
 	a.aaptBuildActions(ctx)
 
@@ -789,7 +788,7 @@
 	a.usesLibrary.freezeEnforceUsesLibraries()
 
 	// Add implicit SDK libraries to <uses-library> list.
-	for _, usesLib := range a.aapt.sdkLibraries.UsesLibs() {
+	for _, usesLib := range a.exportedSdkLibs.UsesLibs() {
 		a.usesLibrary.addLib(usesLib, inList(usesLib, dexpreopt.OptionalCompatUsesLibs))
 	}
 
@@ -806,7 +805,7 @@
 	a.linter.resources = a.aapt.resourceFiles
 	a.linter.buildModuleReportZip = ctx.Config().UnbundledBuildApps()
 
-	dexJarFile := a.dexBuildActions(ctx, a.aapt.sdkLibraries)
+	dexJarFile := a.dexBuildActions(ctx)
 
 	jniLibs, certificateDeps := collectAppDeps(ctx, a, a.shouldEmbedJnis(ctx), !Bool(a.appProperties.Jni_uses_platform_apis))
 	jniJarFile := a.jniBuildActions(jniLibs, ctx)
@@ -1848,7 +1847,7 @@
 		aaptLinkFlags = append(aaptLinkFlags,
 			"--rename-overlay-target-package "+*r.overridableProperties.Target_package_name)
 	}
-	r.aapt.buildActions(ctx, r, aaptLinkFlags...)
+	r.aapt.buildActions(ctx, r, nil, aaptLinkFlags...)
 
 	// Sign the built package
 	_, certificates := collectAppDeps(ctx, r, false, false)
diff --git a/java/java.go b/java/java.go
index 31466b0..d6dc148 100644
--- a/java/java.go
+++ b/java/java.go
@@ -1039,7 +1039,7 @@
 			case libTag, instrumentationForTag:
 				deps.classpath = append(deps.classpath, dep.HeaderJars()...)
 				// sdk lib names from dependencies are re-exported
-				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs())
+				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs(), otherName)
 				deps.aidlIncludeDirs = append(deps.aidlIncludeDirs, dep.AidlIncludeDirs()...)
 				pluginJars, pluginClasses := dep.ExportedPlugins()
 				addPlugins(&deps, pluginJars, pluginClasses...)
@@ -1051,7 +1051,7 @@
 				deps.staticHeaderJars = append(deps.staticHeaderJars, dep.HeaderJars()...)
 				deps.staticResourceJars = append(deps.staticResourceJars, dep.ResourceJars()...)
 				// sdk lib names from dependencies are re-exported
-				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs())
+				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs(), otherName)
 				deps.aidlIncludeDirs = append(deps.aidlIncludeDirs, dep.AidlIncludeDirs()...)
 				pluginJars, pluginClasses := dep.ExportedPlugins()
 				addPlugins(&deps, pluginJars, pluginClasses...)
@@ -2735,7 +2735,7 @@
 			case libTag, staticLibTag:
 				flags.classpath = append(flags.classpath, dep.HeaderJars()...)
 				// sdk lib names from dependencies are re-exported
-				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs())
+				j.exportedSdkLibs.AddContextMap(dep.ExportedSdkLibs(), otherName)
 			case bootClasspathTag:
 				flags.bootClasspath = append(flags.bootClasspath, dep.HeaderJars()...)
 			}