diff --git a/dexpreopt/dexpreopt.go b/dexpreopt/dexpreopt.go
index 2074339..4d8ccb5 100644
--- a/dexpreopt/dexpreopt.go
+++ b/dexpreopt/dexpreopt.go
@@ -41,12 +41,21 @@
 
 	"android/soong/android"
 
+	"github.com/google/blueprint"
 	"github.com/google/blueprint/pathtools"
 )
 
 const SystemPartition = "/system/"
 const SystemOtherPartition = "/system_other/"
 
+type dependencyTag struct {
+	blueprint.BaseDependencyTag
+	name string
+}
+
+var SystemServerDepTag = dependencyTag{name: "system-server-dep"}
+var SystemServerForcedDepTag = dependencyTag{name: "system-server-forced-dep"}
+
 // GenerateDexpreoptRule generates a set of commands that will preopt a module based on a GlobalConfig and a
 // ModuleConfig.  The produced files and their install locations will be available through rule.Installs().
 func GenerateDexpreoptRule(ctx android.PathContext,
@@ -78,7 +87,7 @@
 		bootProfileCommand(ctx, global, module, rule)
 	}
 
-	if !dexpreoptDisabled(global, module) {
+	if !dexpreoptDisabled(ctx, global, module) {
 		// Don't preopt individual boot jars, they will be preopted together.
 		if !contains(global.BootJars, module.Name) {
 			appImage := (generateProfile || module.ForceCreateAppImage || global.DefaultAppImages) &&
@@ -95,7 +104,7 @@
 	return rule, nil
 }
 
-func dexpreoptDisabled(global GlobalConfig, module ModuleConfig) bool {
+func dexpreoptDisabled(ctx android.PathContext, global GlobalConfig, module ModuleConfig) bool {
 	if contains(global.DisablePreoptModules, module.Name) {
 		return true
 	}
@@ -107,6 +116,13 @@
 		}
 	}
 
+	// Don't preopt system server jars that are not Soong modules.
+	if android.InList(module.Name, NonUpdatableSystemServerJars(ctx, global)) {
+		if _, ok := ctx.(android.ModuleContext); !ok {
+			return true
+		}
+	}
+
 	// If OnlyPreoptBootImageAndSystemServer=true and module is not in boot class path skip
 	// Also preopt system server jars since selinux prevents system server from loading anything from
 	// /data. If we don't do this they will need to be extracted which is not favorable for RAM usage
@@ -236,7 +252,8 @@
 	var conditionalClassLoaderContextHost29 android.Paths
 	var conditionalClassLoaderContextTarget29 []string
 
-	var classLoaderContextHostString string
+	var classLoaderContextHostString, classLoaderContextDeviceString string
+	var classLoaderDeps android.Paths
 
 	if module.EnforceUsesLibraries {
 		usesLibs := append(copyOf(module.UsesLibraries), module.PresentOptionalUsesLibraries...)
@@ -282,6 +299,30 @@
 			filepath.Join("/system/framework", hidlBase+".jar"))
 
 		classLoaderContextHostString = strings.Join(classLoaderContextHost.Strings(), ":")
+	} else if android.InList(module.Name, NonUpdatableSystemServerJars(ctx, global)) {
+		// We expect that all dexpreopted system server jars are Soong modules.
+		mctx, isModule := ctx.(android.ModuleContext)
+		if !isModule {
+			panic("Cannot dexpreopt system server jar that is not a soong module.")
+		}
+
+		// System server jars should be dexpreopted together: class loader context of each jar
+		// should include preceding jars (which can be found as dependencies of the current jar
+		// with a special tag).
+		var jarsOnHost android.Paths
+		var jarsOnDevice []string
+		mctx.VisitDirectDepsWithTag(SystemServerDepTag, func(dep android.Module) {
+			depName := mctx.OtherModuleName(dep)
+			if jar, ok := dep.(interface{ DexJar() android.Path }); ok {
+				jarsOnHost = append(jarsOnHost, jar.DexJar())
+				jarsOnDevice = append(jarsOnDevice, "/system/framework/"+depName+".jar")
+			} else {
+				mctx.ModuleErrorf("module \"%s\" is not a jar", depName)
+			}
+		})
+		classLoaderContextHostString = strings.Join(jarsOnHost.Strings(), ":")
+		classLoaderContextDeviceString = strings.Join(jarsOnDevice, ":")
+		classLoaderDeps = jarsOnHost
 	} else {
 		// Pass special class loader context to skip the classpath and collision check.
 		// This will get removed once LOCAL_USES_LIBRARIES is enforced.
@@ -293,8 +334,13 @@
 	rule.Command().FlagWithArg("mkdir -p ", filepath.Dir(odexPath.String()))
 	rule.Command().FlagWithOutput("rm -f ", odexPath)
 	// Set values in the environment of the rule.  These may be modified by construct_context.sh.
-	rule.Command().FlagWithArg("class_loader_context_arg=--class-loader-context=", classLoaderContextHostString)
-	rule.Command().Text(`stored_class_loader_context_arg=""`)
+	if classLoaderContextHostString == `\&` {
+		rule.Command().Text(`class_loader_context_arg=--class-loader-context=\&`)
+		rule.Command().Text(`stored_class_loader_context_arg=""`)
+	} else {
+		rule.Command().Text("class_loader_context_arg=--class-loader-context=PCL[" + classLoaderContextHostString + "]")
+		rule.Command().Text("stored_class_loader_context_arg=--stored-class-loader-context=PCL[" + classLoaderContextDeviceString + "]")
+	}
 
 	if module.EnforceUsesLibraries {
 		if module.ManifestPath != nil {
@@ -348,7 +394,7 @@
 		Flag("--runtime-arg").FlagWithInputList("-Xbootclasspath:", module.PreoptBootClassPathDexFiles, ":").
 		Flag("--runtime-arg").FlagWithList("-Xbootclasspath-locations:", module.PreoptBootClassPathDexLocations, ":").
 		Flag("${class_loader_context_arg}").
-		Flag("${stored_class_loader_context_arg}").
+		Flag("${stored_class_loader_context_arg}").Implicits(classLoaderDeps).
 		FlagWithArg("--boot-image=", strings.Join(module.DexPreoptImageLocations, ":")).Implicits(module.DexPreoptImagesDeps[archIdx].Paths()).
 		FlagWithInput("--dex-file=", module.DexPath).
 		FlagWithArg("--dex-location=", dexLocationArg).
@@ -542,6 +588,26 @@
 	return filepath.Join("/apex", apex, "javalib", jar+".jar")
 }
 
+func GetJarsFromApexJarPairs(apexJarPairs []string) []string {
+	modules := make([]string, len(apexJarPairs))
+	for i, p := range apexJarPairs {
+		_, jar := android.SplitApexJarPair(p)
+		modules[i] = jar
+	}
+	return modules
+}
+
+var nonUpdatableSystemServerJarsKey = android.NewOnceKey("nonUpdatableSystemServerJars")
+
+// TODO: eliminate the superficial global config parameter by moving global config definition
+// from java subpackage to dexpreopt.
+func NonUpdatableSystemServerJars(ctx android.PathContext, global GlobalConfig) []string {
+	return ctx.Config().Once(nonUpdatableSystemServerJarsKey, func() interface{} {
+		return android.RemoveListFromList(global.SystemServerJars,
+			GetJarsFromApexJarPairs(global.UpdatableSystemServerJars))
+	}).([]string)
+}
+
 func contains(l []string, s string) bool {
 	for _, e := range l {
 		if e == s {
diff --git a/java/dexpreopt_config.go b/java/dexpreopt_config.go
index 57b6125..7d0bd8f 100644
--- a/java/dexpreopt_config.go
+++ b/java/dexpreopt_config.go
@@ -70,12 +70,11 @@
 // systemServerClasspath returns the on-device locations of the modules in the system server classpath.  It is computed
 // once the first time it is called for any ctx.Config(), and returns the same slice for all future calls with the same
 // ctx.Config().
-func systemServerClasspath(ctx android.PathContext) []string {
+func systemServerClasspath(ctx android.MakeVarsContext) []string {
 	return ctx.Config().OnceStringSlice(systemServerClasspathKey, func() []string {
 		global := dexpreoptGlobalConfig(ctx)
-
 		var systemServerClasspathLocations []string
-		for _, m := range global.SystemServerJars {
+		for _, m := range *DexpreoptedSystemServerJars(ctx.Config()) {
 			systemServerClasspathLocations = append(systemServerClasspathLocations,
 				filepath.Join("/system/framework", m+".jar"))
 		}
@@ -112,15 +111,6 @@
 	return moduleName
 }
 
-func getJarsFromApexJarPairs(apexJarPairs []string) []string {
-	modules := make([]string, len(apexJarPairs))
-	for i, p := range apexJarPairs {
-		_, jar := android.SplitApexJarPair(p)
-		modules[i] = jar
-	}
-	return modules
-}
-
 var (
 	bootImageConfigKey     = android.NewOnceKey("bootImageConfig")
 	artBootImageName       = "art"
@@ -141,7 +131,7 @@
 			artModules = append(artModules, "jacocoagent")
 		}
 		frameworkModules := android.RemoveListFromList(global.BootJars,
-			concat(artModules, getJarsFromApexJarPairs(global.UpdatableBootJars)))
+			concat(artModules, dexpreopt.GetJarsFromApexJarPairs(global.UpdatableBootJars)))
 
 		artSubdir := "apex/com.android.art/javalib"
 		frameworkSubdir := "system/framework"
diff --git a/java/java.go b/java/java.go
index 279d674..d84d162 100644
--- a/java/java.go
+++ b/java/java.go
@@ -23,12 +23,14 @@
 	"path/filepath"
 	"strconv"
 	"strings"
+	"sync"
 
 	"github.com/google/blueprint"
 	"github.com/google/blueprint/pathtools"
 	"github.com/google/blueprint/proptools"
 
 	"android/soong/android"
+	"android/soong/dexpreopt"
 	"android/soong/java/config"
 	"android/soong/tradefed"
 )
@@ -52,6 +54,8 @@
 			PropertyName: "java_tests",
 		},
 	})
+
+	android.PostDepsMutators(RegisterPostDepsMutators)
 }
 
 func RegisterJavaBuildComponents(ctx android.RegistrationContext) {
@@ -76,6 +80,44 @@
 	ctx.RegisterSingletonType("kythe_java_extract", kytheExtractJavaFactory)
 }
 
+func RegisterPostDepsMutators(ctx android.RegisterMutatorsContext) {
+	ctx.BottomUp("ordered_system_server_jars", systemServerJarsDepsMutator)
+}
+
+var (
+	dexpreoptedSystemServerJarsKey  = android.NewOnceKey("dexpreoptedSystemServerJars")
+	dexpreoptedSystemServerJarsLock sync.Mutex
+)
+
+func DexpreoptedSystemServerJars(config android.Config) *[]string {
+	return config.Once(dexpreoptedSystemServerJarsKey, func() interface{} {
+		return &[]string{}
+	}).(*[]string)
+}
+
+// A PostDepsMutator pass that enforces total order on non-updatable system server jars. A total
+// order is neededed because such jars must be dexpreopted together (each jar on the list must have
+// all preceding jars in its class loader context). The total order must be compatible with the
+// partial order imposed by genuine dependencies between system server jars (which is not always
+// respected by the PRODUCT_SYSTEM_SERVER_JARS variable).
+//
+// An earlier mutator pass creates genuine dependencies, and this pass traverses the jars in that
+// order (which is partial and non-deterministic). This pass adds additional dependencies between
+// jars, making the order total and deterministic. It also constructs a global ordered list.
+func systemServerJarsDepsMutator(ctx android.BottomUpMutatorContext) {
+	jars := dexpreopt.NonUpdatableSystemServerJars(ctx, dexpreoptGlobalConfig(ctx))
+	name := ctx.ModuleName()
+	if android.InList(name, jars) {
+		dexpreoptedSystemServerJarsLock.Lock()
+		defer dexpreoptedSystemServerJarsLock.Unlock()
+		jars := DexpreoptedSystemServerJars(ctx.Config())
+		for _, dep := range *jars {
+			ctx.AddDependency(ctx.Module(), dexpreopt.SystemServerDepTag, dep)
+		}
+		*jars = append(*jars, name)
+	}
+}
+
 func (j *Module) checkSdkVersion(ctx android.ModuleContext) {
 	if j.SocSpecific() || j.DeviceSpecific() ||
 		(j.ProductSpecific() && ctx.Config().EnforceProductPartitionInterface()) {
@@ -659,6 +701,11 @@
 	} else if j.shouldInstrumentStatic(ctx) {
 		ctx.AddVariationDependencies(nil, staticLibTag, "jacocoagent")
 	}
+
+	// services depend on com.android.location.provider, but dependency in not registered in a Blueprint file
+	if ctx.ModuleName() == "services" {
+		ctx.AddDependency(ctx.Module(), dexpreopt.SystemServerForcedDepTag, "com.android.location.provider")
+	}
 }
 
 func hasSrcExt(srcs []string, ext string) bool {