diff --git a/java/java.go b/java/java.go
index b6e2a54..5bf3d79 100644
--- a/java/java.go
+++ b/java/java.go
@@ -248,13 +248,15 @@
 
 type usesLibraryDependencyTag struct {
 	dependencyTag
-	sdkVersion int // SDK version in which the library appared as a standalone library.
+	sdkVersion int  // SDK version in which the library appared as a standalone library.
+	optional   bool // If the dependency is optional or required.
 }
 
-func makeUsesLibraryDependencyTag(sdkVersion int) usesLibraryDependencyTag {
+func makeUsesLibraryDependencyTag(sdkVersion int, optional bool) usesLibraryDependencyTag {
 	return usesLibraryDependencyTag{
 		dependencyTag: dependencyTag{name: fmt.Sprintf("uses-library-%d", sdkVersion)},
 		sdkVersion:    sdkVersion,
+		optional:      optional,
 	}
 }
 
@@ -283,10 +285,11 @@
 	syspropPublicStubDepTag = dependencyTag{name: "sysprop public stub"}
 	jniInstallTag           = installDependencyTag{name: "jni install"}
 	binaryInstallTag        = installDependencyTag{name: "binary install"}
-	usesLibTag              = makeUsesLibraryDependencyTag(dexpreopt.AnySdkVersion)
-	usesLibCompat28Tag      = makeUsesLibraryDependencyTag(28)
-	usesLibCompat29Tag      = makeUsesLibraryDependencyTag(29)
-	usesLibCompat30Tag      = makeUsesLibraryDependencyTag(30)
+	usesLibReqTag           = makeUsesLibraryDependencyTag(dexpreopt.AnySdkVersion, false)
+	usesLibOptTag           = makeUsesLibraryDependencyTag(dexpreopt.AnySdkVersion, true)
+	usesLibCompat28OptTag   = makeUsesLibraryDependencyTag(28, true)
+	usesLibCompat29ReqTag   = makeUsesLibraryDependencyTag(29, false)
+	usesLibCompat30OptTag   = makeUsesLibraryDependencyTag(30, true)
 )
 
 func IsLibDepTag(depTag blueprint.DependencyTag) bool {
@@ -1807,8 +1810,10 @@
 	}
 
 	depTag := ctx.OtherModuleDependencyTag(depModule)
-	if depTag == libTag || depTag == usesLibTag {
+	if depTag == libTag {
 		// Ok, propagate <uses-library> through non-static library dependencies.
+	} else if tag, ok := depTag.(usesLibraryDependencyTag); ok && tag.sdkVersion == dexpreopt.AnySdkVersion {
+		// Ok, propagate <uses-library> through non-compatibility <uses-library> dependencies.
 	} else if depTag == staticLibTag {
 		// Propagate <uses-library> through static library dependencies, unless it is a component
 		// library (such as stubs). Component libraries have a dependency on their SDK library,
@@ -1826,7 +1831,7 @@
 	// <uses_library> and should not be added to CLC, but the transitive <uses-library> dependencies
 	// from its CLC should be added to the current CLC.
 	if sdkLib != nil {
-		clcMap.AddContext(ctx, dexpreopt.AnySdkVersion, *sdkLib,
+		clcMap.AddContext(ctx, dexpreopt.AnySdkVersion, *sdkLib, false,
 			dep.DexJarBuildPath(), dep.DexJarInstallPath(), dep.ClassLoaderContexts())
 	} else {
 		clcMap.AddContextMap(dep.ClassLoaderContexts(), depName)