diff --git a/cc/binary.go b/cc/binary.go
index 9d0cf60..65e8eb5 100644
--- a/cc/binary.go
+++ b/cc/binary.go
@@ -363,8 +363,10 @@
 	var sharedLibs android.Paths
 	// Ignore shared libs for static executables.
 	if !binary.static() {
-		sharedLibs = deps.SharedLibs
+		sharedLibs = deps.EarlySharedLibs
+		sharedLibs = append(sharedLibs, deps.SharedLibs...)
 		sharedLibs = append(sharedLibs, deps.LateSharedLibs...)
+		linkerDeps = append(linkerDeps, deps.EarlySharedLibsDeps...)
 		linkerDeps = append(linkerDeps, deps.SharedLibsDeps...)
 		linkerDeps = append(linkerDeps, deps.LateSharedLibsDeps...)
 	}
diff --git a/cc/cc.go b/cc/cc.go
index ee6cd4e..baee70a 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -96,9 +96,9 @@
 
 type PathDeps struct {
 	// Paths to .so files
-	SharedLibs, LateSharedLibs android.Paths
+	SharedLibs, EarlySharedLibs, LateSharedLibs android.Paths
 	// Paths to the dependencies to use for .so files (.so.toc files)
-	SharedLibsDeps, LateSharedLibsDeps android.Paths
+	SharedLibsDeps, EarlySharedLibsDeps, LateSharedLibsDeps android.Paths
 	// Paths to .a files
 	StaticLibs, LateStaticLibs, WholeStaticLibs android.Paths
 
@@ -328,6 +328,7 @@
 var (
 	sharedDepTag          = dependencyTag{name: "shared", library: true}
 	sharedExportDepTag    = dependencyTag{name: "shared", library: true, reexportFlags: true}
+	earlySharedDepTag     = dependencyTag{name: "early_shared", library: true}
 	lateSharedDepTag      = dependencyTag{name: "late shared", library: true}
 	staticDepTag          = dependencyTag{name: "static", library: true}
 	staticExportDepTag    = dependencyTag{name: "static", library: true, reexportFlags: true}
@@ -1570,6 +1571,11 @@
 			depPtr = &depPaths.SharedLibsDeps
 			depFile = ccDep.linker.(libraryInterface).toc()
 			directSharedDeps = append(directSharedDeps, ccDep)
+		case earlySharedDepTag:
+			ptr = &depPaths.EarlySharedLibs
+			depPtr = &depPaths.EarlySharedLibsDeps
+			depFile = ccDep.linker.(libraryInterface).toc()
+			directSharedDeps = append(directSharedDeps, ccDep)
 		case lateSharedDepTag, ndkLateStubDepTag:
 			ptr = &depPaths.LateSharedLibs
 			depPtr = &depPaths.LateSharedLibsDeps
@@ -1663,7 +1669,7 @@
 
 		// Export the shared libs to Make.
 		switch depTag {
-		case sharedDepTag, sharedExportDepTag, lateSharedDepTag:
+		case sharedDepTag, sharedExportDepTag, lateSharedDepTag, earlySharedDepTag:
 			if dependentLibrary, ok := ccDep.linker.(*libraryDecorator); ok {
 				if dependentLibrary.buildStubs() && android.InAnyApex(depName) {
 					// Add the dependency to the APEX(es) providing the library so that
diff --git a/cc/library.go b/cc/library.go
index 4adb081..09e5b50 100644
--- a/cc/library.go
+++ b/cc/library.go
@@ -696,9 +696,11 @@
 		}
 	}
 
-	sharedLibs := deps.SharedLibs
+	sharedLibs := deps.EarlySharedLibs
+	sharedLibs = append(sharedLibs, deps.SharedLibs...)
 	sharedLibs = append(sharedLibs, deps.LateSharedLibs...)
 
+	linkerDeps = append(linkerDeps, deps.EarlySharedLibsDeps...)
 	linkerDeps = append(linkerDeps, deps.SharedLibsDeps...)
 	linkerDeps = append(linkerDeps, deps.LateSharedLibsDeps...)
 	linkerDeps = append(linkerDeps, objs.tidyFiles...)
diff --git a/cc/sanitize.go b/cc/sanitize.go
index 0951efe..90656da 100644
--- a/cc/sanitize.go
+++ b/cc/sanitize.go
@@ -809,7 +809,7 @@
 				mctx.AddFarVariationDependencies([]blueprint.Variation{
 					{Mutator: "link", Variation: "shared"},
 					{Mutator: "arch", Variation: mctx.Target().String()},
-				}, sharedDepTag, runtimeLibrary)
+				}, earlySharedDepTag, runtimeLibrary)
 			}
 			// static lib does not have dependency to the runtime library. The
 			// dependency will be added to the executables or shared libs using