diff --git a/java/dexpreopt_bootjars.go b/java/dexpreopt_bootjars.go
index 40aad06..f2079b0 100644
--- a/java/dexpreopt_bootjars.go
+++ b/java/dexpreopt_bootjars.go
@@ -16,6 +16,7 @@
 
 import (
 	"path/filepath"
+	"sort"
 	"strings"
 
 	"android/soong/android"
@@ -312,17 +313,17 @@
 	// All the files that constitute this image variant, i.e. .art, .oat and .vdex files.
 	imagesDeps android.OutputPaths
 
-	// The path to the primary image variant's imagePathOnHost field, where primary image variant
+	// The path to the base image variant's imagePathOnHost field, where base image variant
 	// means the image variant that this extends.
 	//
 	// This is only set for a variant of an image that extends another image.
-	primaryImages android.OutputPath
+	baseImages android.OutputPaths
 
-	// The paths to the primary image variant's imagesDeps field, where primary image variant
+	// The paths to the base image variant's imagesDeps field, where base image variant
 	// means the image variant that this extends.
 	//
 	// This is only set for a variant of an image that extends another image.
-	primaryImagesDeps android.Paths
+	baseImagesDeps android.Paths
 
 	// Rules which should be used in make to install the outputs on host.
 	//
@@ -511,8 +512,13 @@
 
 	defaultImageConfig := defaultBootImageConfig(ctx)
 	d.defaultBootImage = defaultImageConfig
-	artBootImageConfig := artBootImageConfig(ctx)
-	d.otherImages = []*bootImageConfig{artBootImageConfig}
+	imageConfigs := genBootImageConfigs(ctx)
+	d.otherImages = make([]*bootImageConfig, 0, len(imageConfigs)-1)
+	for _, config := range imageConfigs {
+		if config != defaultImageConfig {
+			d.otherImages = append(d.otherImages, config)
+		}
+	}
 }
 
 // shouldBuildBootImages determines whether boot images should be built.
@@ -708,9 +714,11 @@
 	}
 
 	if image.extends != nil {
-		// It is a boot image extension, so it needs the boot image it depends on (in this case the
-		// primary ART APEX image).
-		artImage := image.primaryImages
+		// It is a boot image extension, so it needs the boot images that it depends on.
+		baseImageLocations := make([]string, 0, len(image.baseImages))
+		for _, image := range image.baseImages {
+			baseImageLocations = append(baseImageLocations, dexpreopt.PathToLocation(image, arch))
+		}
 		cmd.
 			Flag("--runtime-arg").FlagWithInputList("-Xbootclasspath:", image.dexPathsDeps.Paths(), ":").
 			Flag("--runtime-arg").FlagWithList("-Xbootclasspath-locations:", image.dexLocationsDeps, ":").
@@ -718,11 +726,11 @@
 			// dex2oat will reconstruct the path to the actual file when it needs it. As the actual path
 			// to the file cannot be passed to the command make sure to add the actual path as an Implicit
 			// dependency to ensure that it is built before the command runs.
-			FlagWithArg("--boot-image=", dexpreopt.PathToLocation(artImage, arch)).Implicit(artImage).
+			FlagWithList("--boot-image=", baseImageLocations, ":").Implicits(image.baseImages.Paths()).
 			// Similarly, the dex2oat tool will automatically find the paths to other files in the base
 			// boot image so make sure to add them as implicit dependencies to ensure that they are built
 			// before this command is run.
-			Implicits(image.primaryImagesDeps)
+			Implicits(image.baseImagesDeps)
 	} else {
 		// It is a primary image, so it needs a base address.
 		cmd.FlagWithArg("--base=", ctx.Config().LibartImgDeviceBaseAddress())
@@ -1021,6 +1029,8 @@
 			ctx.Strict("DEXPREOPT_IMAGE_LOCATIONS_ON_DEVICE"+current.name, strings.Join(imageLocationsOnDevice, ":"))
 			ctx.Strict("DEXPREOPT_IMAGE_ZIP_"+current.name, current.zip.String())
 		}
+		// Ensure determinism.
+		sort.Strings(imageNames)
 		ctx.Strict("DEXPREOPT_IMAGE_NAMES", strings.Join(imageNames, " "))
 	}
 }
diff --git a/java/dexpreopt_config.go b/java/dexpreopt_config.go
index 2975130..76c78cb 100644
--- a/java/dexpreopt_config.go
+++ b/java/dexpreopt_config.go
@@ -94,10 +94,7 @@
 		deviceDir := android.PathForOutput(ctx, ctx.Config().DeviceName())
 
 		configs := genBootImageConfigRaw(ctx)
-		artCfg := configs[artBootImageName]
-		frameworkCfg := configs[frameworkBootImageName]
 
-		// common to all configs
 		for _, c := range configs {
 			c.dir = deviceDir.Join(ctx, "dex_"+c.name+"jars")
 			c.symbolsDir = deviceDir.Join(ctx, "dex_"+c.name+"jars_unstripped")
@@ -133,18 +130,42 @@
 			c.zip = c.dir.Join(ctx, c.name+".zip")
 		}
 
-		// specific to the framework config
-		frameworkCfg.dexPathsDeps = append(artCfg.dexPathsDeps, frameworkCfg.dexPathsDeps...)
-		for i := range targets {
-			frameworkCfg.variants[i].primaryImages = artCfg.variants[i].imagePathOnHost
-			frameworkCfg.variants[i].primaryImagesDeps = artCfg.variants[i].imagesDeps.Paths()
-			frameworkCfg.variants[i].dexLocationsDeps = append(artCfg.variants[i].dexLocations, frameworkCfg.variants[i].dexLocationsDeps...)
+		visited := make(map[string]bool)
+		for _, c := range configs {
+			calculateDepsRecursive(c, targets, visited)
 		}
 
 		return configs
 	}).(map[string]*bootImageConfig)
 }
 
+// calculateDepsRecursive calculates the dependencies of the given boot image config and all its
+// ancestors, if they are not visited.
+// The boot images are supposed to form a tree, where the root is the primary boot image. We do not
+// expect loops (e.g., A extends B, B extends C, C extends A), and we let them crash soong with a
+// stack overflow.
+// Note that a boot image config only has a pointer to the parent, not to children. Therefore, we
+// first go up through the parent chain, and then go back down to visit every code along the path.
+// `visited` is a map where a key is a boot image name and the value indicates whether the boot
+// image config is visited. The boot image names are guaranteed to be unique because they come from
+// `genBootImageConfigRaw` above, which also returns a map and would fail in the first place if the
+// names were not unique.
+func calculateDepsRecursive(c *bootImageConfig, targets []android.Target, visited map[string]bool) {
+	if c.extends == nil || visited[c.name] {
+		return
+	}
+	if c.extends.extends != nil {
+		calculateDepsRecursive(c.extends, targets, visited)
+	}
+	visited[c.name] = true
+	c.dexPathsDeps = android.Concat(c.extends.dexPathsDeps, c.dexPathsDeps)
+	for i := range targets {
+		c.variants[i].baseImages = android.Concat(c.extends.variants[i].baseImages, android.OutputPaths{c.extends.variants[i].imagePathOnHost})
+		c.variants[i].baseImagesDeps = android.Concat(c.extends.variants[i].baseImagesDeps, c.extends.variants[i].imagesDeps.Paths())
+		c.variants[i].dexLocationsDeps = android.Concat(c.extends.variants[i].dexLocationsDeps, c.variants[i].dexLocationsDeps)
+	}
+}
+
 func artBootImageConfig(ctx android.PathContext) *bootImageConfig {
 	return genBootImageConfigs(ctx)[artBootImageName]
 }
diff --git a/java/dexpreopt_config_testing.go b/java/dexpreopt_config_testing.go
index 1c236d8..c509c1b 100644
--- a/java/dexpreopt_config_testing.go
+++ b/java/dexpreopt_config_testing.go
@@ -100,8 +100,8 @@
 	imagePathOnHost   string
 	imagePathOnDevice string
 	imagesDeps        []string
-	primaryImages     string
-	primaryImagesDeps []string
+	baseImages        []string
+	baseImagesDeps    []string
 
 	// Mutated fields
 	installs            []normalizedInstall
@@ -413,8 +413,8 @@
 					"out/soong/test_device/dex_bootjars/android/system/framework/arm64/boot-framework.oat",
 					"out/soong/test_device/dex_bootjars/android/system/framework/arm64/boot-framework.vdex",
 				},
-				primaryImages: "out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm64/boot.art",
-				primaryImagesDeps: []string{
+				baseImages: []string{"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm64/boot.art"},
+				baseImagesDeps: []string{
 					"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm64/boot.art",
 					"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm64/boot.oat",
 					"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm64/boot.vdex",
@@ -461,8 +461,8 @@
 					"out/soong/test_device/dex_bootjars/android/system/framework/arm/boot-framework.oat",
 					"out/soong/test_device/dex_bootjars/android/system/framework/arm/boot-framework.vdex",
 				},
-				primaryImages: "out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm/boot.art",
-				primaryImagesDeps: []string{
+				baseImages: []string{"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm/boot.art"},
+				baseImagesDeps: []string{
 					"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm/boot.art",
 					"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm/boot.oat",
 					"out/soong/test_device/dex_artjars/android/apex/art_boot_images/javalib/arm/boot.vdex",
@@ -509,8 +509,8 @@
 					"out/soong/test_device/dex_bootjars/linux_glibc/system/framework/x86_64/boot-framework.oat",
 					"out/soong/test_device/dex_bootjars/linux_glibc/system/framework/x86_64/boot-framework.vdex",
 				},
-				primaryImages: "out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86_64/boot.art",
-				primaryImagesDeps: []string{
+				baseImages: []string{"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86_64/boot.art"},
+				baseImagesDeps: []string{
 					"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86_64/boot.art",
 					"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86_64/boot.oat",
 					"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86_64/boot.vdex",
@@ -557,8 +557,8 @@
 					"out/soong/test_device/dex_bootjars/linux_glibc/system/framework/x86/boot-framework.oat",
 					"out/soong/test_device/dex_bootjars/linux_glibc/system/framework/x86/boot-framework.vdex",
 				},
-				primaryImages: "out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86/boot.art",
-				primaryImagesDeps: []string{
+				baseImages: []string{"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86/boot.art"},
+				baseImagesDeps: []string{
 					"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86/boot.art",
 					"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86/boot.oat",
 					"out/soong/test_device/dex_artjars/linux_glibc/apex/art_boot_images/javalib/x86/boot.vdex",
@@ -664,8 +664,8 @@
 			android.AssertPathRelativeToTopEquals(t, "imagePathOnHost", expectedVariant.imagePathOnHost, variant.imagePathOnHost)
 			android.AssertStringEquals(t, "imagePathOnDevice", expectedVariant.imagePathOnDevice, variant.imagePathOnDevice)
 			android.AssertPathsRelativeToTopEquals(t, "imagesDeps", expectedVariant.imagesDeps, variant.imagesDeps.Paths())
-			android.AssertPathRelativeToTopEquals(t, "primaryImages", expectedVariant.primaryImages, variant.primaryImages)
-			android.AssertPathsRelativeToTopEquals(t, "primaryImagesDeps", expectedVariant.primaryImagesDeps, variant.primaryImagesDeps)
+			android.AssertPathsRelativeToTopEquals(t, "baseImages", expectedVariant.baseImages, variant.baseImages.Paths())
+			android.AssertPathsRelativeToTopEquals(t, "baseImagesDeps", expectedVariant.baseImagesDeps, variant.baseImagesDeps)
 			assertInstallsEqual(t, "installs", expectedVariant.installs, variant.installs)
 			assertInstallsEqual(t, "vdexInstalls", expectedVariant.vdexInstalls, variant.vdexInstalls)
 			assertInstallsEqual(t, "unstrippedInstalls", expectedVariant.unstrippedInstalls, variant.unstrippedInstalls)