diff --git a/java/aar.go b/java/aar.go
index 5c19a9c..0f5e30d 100644
--- a/java/aar.go
+++ b/java/aar.go
@@ -390,7 +390,7 @@
 			// (including the java_sdk_library) itself then append any implicit sdk library
 			// names to the list of sdk libraries to be added to the manifest.
 			if component, ok := module.(SdkLibraryComponentDependency); ok {
-				sdkLibraries.AddLibraryPath(ctx, component.OptionalImplicitSdkLibrary(),
+				sdkLibraries.MaybeAddLibraryPath(ctx, component.OptionalImplicitSdkLibrary(),
 					component.DexJarBuildPath(), component.DexJarInstallPath())
 			}
 
diff --git a/java/app.go b/java/app.go
index 5e3a9d9..34f96dd 100755
--- a/java/app.go
+++ b/java/app.go
@@ -586,7 +586,7 @@
 	return android.PathForModuleInstall(ctx, installDir, a.installApkName+".apk")
 }
 
-func (a *AndroidApp) dexBuildActions(ctx android.ModuleContext) android.Path {
+func (a *AndroidApp) dexBuildActions(ctx android.ModuleContext, sdkLibs dexpreopt.LibraryPaths) 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.
@@ -597,6 +597,7 @@
 	a.dexpreopter.usesLibs = a.usesLibrary.usesLibraryProperties.Uses_libs
 	a.dexpreopter.optionalUsesLibs = a.usesLibrary.presentOptionalUsesLibs(ctx)
 	a.dexpreopter.libraryPaths = a.usesLibrary.usesLibraryPaths(ctx)
+	a.dexpreopter.libraryPaths.AddLibraryPaths(sdkLibs)
 	a.dexpreopter.manifestFile = a.mergedManifestFile
 	a.exportedSdkLibs = make(dexpreopt.LibraryPaths)
 
@@ -767,6 +768,15 @@
 	// Process all building blocks, from AAPT to certificates.
 	a.aaptBuildActions(ctx)
 
+	// The decision to enforce <uses-library> checks is made before adding implicit SDK libraries.
+	a.usesLibrary.freezeEnforceUsesLibraries()
+
+	// Add implicit SDK libraries to <uses-library> list.
+	for _, usesLib := range android.SortedStringKeys(a.aapt.sdkLibraries) {
+		a.usesLibrary.addLib(usesLib, inList(usesLib, optionalUsesLibs))
+	}
+
+	// Check that the <uses-library> list is coherent with the manifest.
 	if a.usesLibrary.enforceUsesLibraries() {
 		manifestCheckFile := a.usesLibrary.verifyUsesLibrariesManifest(ctx, a.mergedManifestFile)
 		apkDeps = append(apkDeps, manifestCheckFile)
@@ -779,7 +789,7 @@
 	a.linter.resources = a.aapt.resourceFiles
 	a.linter.buildModuleReportZip = ctx.Config().UnbundledBuildApps()
 
-	dexJarFile := a.dexBuildActions(ctx)
+	dexJarFile := a.dexBuildActions(ctx, a.aapt.sdkLibraries)
 
 	jniLibs, certificateDeps := collectAppDeps(ctx, a, a.shouldEmbedJnis(ctx), !Bool(a.appProperties.Jni_uses_platform_apis))
 	jniJarFile := a.jniBuildActions(jniLibs, ctx)
@@ -1888,6 +1898,16 @@
 	usesLibraryProperties UsesLibraryProperties
 }
 
+func (u *usesLibrary) addLib(lib string, optional bool) {
+	if !android.InList(lib, u.usesLibraryProperties.Uses_libs) && !android.InList(lib, u.usesLibraryProperties.Optional_uses_libs) {
+		if optional {
+			u.usesLibraryProperties.Optional_uses_libs = append(u.usesLibraryProperties.Optional_uses_libs, lib)
+		} else {
+			u.usesLibraryProperties.Uses_libs = append(u.usesLibraryProperties.Uses_libs, lib)
+		}
+	}
+}
+
 func (u *usesLibrary) deps(ctx android.BottomUpMutatorContext, hasFrameworkLibs bool) {
 	if !ctx.Config().UnbundledBuild() {
 		ctx.AddVariationDependencies(nil, usesLibTag, u.usesLibraryProperties.Uses_libs...)
@@ -1960,6 +1980,12 @@
 	return BoolDefault(u.usesLibraryProperties.Enforce_uses_libs, defaultEnforceUsesLibs)
 }
 
+// Freeze the value of `enforce_uses_libs` based on the current values of `uses_libs` and `optional_uses_libs`.
+func (u *usesLibrary) freezeEnforceUsesLibraries() {
+	enforce := u.enforceUsesLibraries()
+	u.usesLibraryProperties.Enforce_uses_libs = &enforce
+}
+
 // verifyUsesLibrariesManifest checks the <uses-library> tags in an AndroidManifest.xml against the ones specified
 // in the uses_libs and optional_uses_libs properties.  It returns the path to a copy of the manifest.
 func (u *usesLibrary) verifyUsesLibrariesManifest(ctx android.ModuleContext, manifest android.Path) android.Path {
diff --git a/java/app_test.go b/java/app_test.go
index 6b27124..7e7ae41 100644
--- a/java/app_test.go
+++ b/java/app_test.go
@@ -2542,6 +2542,19 @@
 		android_app {
 			name: "app",
 			srcs: ["a.java"],
+			libs: ["qux", "quuz"],
+			static_libs: ["static-runtime-helper"],
+			uses_libs: ["foo"],
+			sdk_version: "current",
+			optional_uses_libs: [
+				"bar",
+				"baz",
+			],
+		}
+
+		android_app {
+			name: "app_with_stub_deps",
+			srcs: ["a.java"],
 			libs: ["qux", "quuz.stubs"],
 			static_libs: ["static-runtime-helper"],
 			uses_libs: ["foo"],
@@ -2572,6 +2585,7 @@
 	run(t, ctx, config)
 
 	app := ctx.ModuleForTests("app", "android_common")
+	appWithStubDeps := ctx.ModuleForTests("app_with_stub_deps", "android_common")
 	prebuilt := ctx.ModuleForTests("prebuilt", "android_common")
 
 	// Test that implicit dependencies on java_sdk_library instances are passed to the manifest.
@@ -2602,15 +2616,24 @@
 		t.Errorf("wanted %q in %q", w, cmd)
 	}
 
-	// Test that only present libraries are preopted
+	// Test that all present libraries are preopted, including implicit SDK dependencies
 	cmd = app.Rule("dexpreopt").RuleParams.Command
-
-	if w := `--target-classpath-for-sdk any /system/framework/foo.jar:/system/framework/bar.jar`; !strings.Contains(cmd, w) {
+	w := `--target-classpath-for-sdk any` +
+		` /system/framework/foo.jar` +
+		`:/system/framework/quuz.jar` +
+		`:/system/framework/qux.jar` +
+		`:/system/framework/runtime-library.jar` +
+		`:/system/framework/bar.jar`
+	if !strings.Contains(cmd, w) {
 		t.Errorf("wanted %q in %q", w, cmd)
 	}
 
-	cmd = prebuilt.Rule("dexpreopt").RuleParams.Command
+	// TODO(skvadrik) fix dexpreopt for stub libraries for which the implementation is present
+	if appWithStubDeps.MaybeRule("dexpreopt").RuleParams.Command != "" {
+		t.Errorf("dexpreopt should be disabled for apps with dependencies on stub libraries")
+	}
 
+	cmd = prebuilt.Rule("dexpreopt").RuleParams.Command
 	if w := `--target-classpath-for-sdk any /system/framework/foo.jar:/system/framework/bar.jar`; !strings.Contains(cmd, w) {
 		t.Errorf("wanted %q in %q", w, cmd)
 	}
diff --git a/java/java.go b/java/java.go
index 4d7d568..27e425d 100644
--- a/java/java.go
+++ b/java/java.go
@@ -991,7 +991,7 @@
 			case libTag:
 				deps.classpath = append(deps.classpath, dep.SdkHeaderJars(ctx, j.sdkVersion())...)
 				// names of sdk libs that are directly depended are exported
-				j.exportedSdkLibs.AddLibraryPath(ctx, dep.OptionalImplicitSdkLibrary(), dep.DexJarBuildPath(), dep.DexJarInstallPath())
+				j.exportedSdkLibs.MaybeAddLibraryPath(ctx, dep.OptionalImplicitSdkLibrary(), dep.DexJarBuildPath(), dep.DexJarInstallPath())
 			case staticLibTag:
 				ctx.ModuleErrorf("dependency on java_sdk_library %q can only be in libs", otherName)
 			}
@@ -1970,7 +1970,7 @@
 	// add the name of that java_sdk_library to the exported sdk libs to make sure
 	// that, if necessary, a <uses-library> element for that java_sdk_library is
 	// added to the Android manifest.
-	j.exportedSdkLibs.AddLibraryPath(ctx, j.OptionalImplicitSdkLibrary(), j.DexJarBuildPath(), j.DexJarInstallPath())
+	j.exportedSdkLibs.MaybeAddLibraryPath(ctx, j.OptionalImplicitSdkLibrary(), j.DexJarBuildPath(), j.DexJarInstallPath())
 
 	j.distFiles = j.GenerateTaggedDistFiles(ctx)
 }
@@ -2608,7 +2608,7 @@
 			switch tag {
 			case libTag:
 				// names of sdk libs that are directly depended are exported
-				j.exportedSdkLibs.AddLibraryPath(ctx, &otherName, dep.DexJarBuildPath(), dep.DexJarInstallPath())
+				j.exportedSdkLibs.AddLibraryPath(ctx, otherName, dep.DexJarBuildPath(), dep.DexJarInstallPath())
 			}
 		}
 	})
@@ -2623,7 +2623,7 @@
 	// add the name of that java_sdk_library to the exported sdk libs to make sure
 	// that, if necessary, a <uses-library> element for that java_sdk_library is
 	// added to the Android manifest.
-	j.exportedSdkLibs.AddLibraryPath(ctx, j.OptionalImplicitSdkLibrary(), outputFile, installFile)
+	j.exportedSdkLibs.MaybeAddLibraryPath(ctx, j.OptionalImplicitSdkLibrary(), outputFile, installFile)
 
 	j.exportAidlIncludeDirs = android.PathsForModuleSrc(ctx, j.properties.Aidl.Export_include_dirs)
 }