diff --git a/android/Android.bp b/android/Android.bp
index 7bd1450..8f89a59 100644
--- a/android/Android.bp
+++ b/android/Android.bp
@@ -21,6 +21,7 @@
         "defaults.go",
         "defs.go",
         "depset.go",
+        "deptag.go",
         "expand.go",
         "filegroup.go",
         "hooks.go",
@@ -68,6 +69,7 @@
         "config_test.go",
         "csuite_config_test.go",
         "depset_test.go",
+        "deptag_test.go",
         "expand_test.go",
         "module_test.go",
         "mutator_test.go",
diff --git a/android/arch.go b/android/arch.go
index 98ff07a..16211f8 100644
--- a/android/arch.go
+++ b/android/arch.go
@@ -598,6 +598,10 @@
 	// has dependencies on all the OS variants.
 	CommonOS = NewOsType("common_os", Generic, false)
 
+	// CommonArch is the Arch for all modules that are os-specific but not arch specific,
+	// for example most Java modules.
+	CommonArch = Arch{ArchType: Common}
+
 	osArchTypeMap = map[OsType][]ArchType{
 		Linux:       []ArchType{X86, X86_64},
 		LinuxBionic: []ArchType{Arm64, X86_64},
@@ -661,7 +665,7 @@
 	if _, found := commonTargetMap[name]; found {
 		panic(fmt.Errorf("Found Os type duplicate during OsType registration: %q", name))
 	} else {
-		commonTargetMap[name] = Target{Os: os, Arch: Arch{ArchType: Common}}
+		commonTargetMap[name] = Target{Os: os, Arch: CommonArch}
 	}
 
 	return os
@@ -819,9 +823,6 @@
 // Identifies the dependency from CommonOS variant to the os specific variants.
 var commonOsToOsSpecificVariantTag = archDepTag{name: "common os to os specific"}
 
-// Identifies the dependency from arch variant to the common variant for a "common_first" multilib.
-var firstArchToCommonArchDepTag = archDepTag{name: "first arch to common arch"}
-
 // Get the OsType specific variants for the current CommonOS variant.
 //
 // The returned list will only contain enabled OsType specific variants of the
@@ -960,12 +961,6 @@
 		addTargetProperties(m, targets[i], multiTargets, i == 0)
 		m.base().setArchProperties(mctx)
 	}
-
-	if multilib == "common_first" && len(modules) >= 2 {
-		for i := range modules[1:] {
-			mctx.AddInterVariantDependency(firstArchToCommonArchDepTag, modules[i+1], modules[0])
-		}
-	}
 }
 
 func addTargetProperties(m Module, target Target, multiTargets []Target, primaryTarget bool) {
diff --git a/android/deptag.go b/android/deptag.go
new file mode 100644
index 0000000..be5c35c
--- /dev/null
+++ b/android/deptag.go
@@ -0,0 +1,45 @@
+// Copyright 2020 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package android
+
+import "github.com/google/blueprint"
+
+// Dependency tags can implement this interface and return true from InstallDepNeeded to annotate
+// that the installed files of the parent should depend on the installed files of the child.
+type InstallNeededDependencyTag interface {
+	// If InstallDepNeeded returns true then the installed files of the parent will depend on the
+	// installed files of the child.
+	InstallDepNeeded() bool
+}
+
+// Dependency tags can embed this struct to annotate that the installed files of the parent should
+// depend on the installed files of the child.
+type InstallAlwaysNeededDependencyTag struct{}
+
+func (i InstallAlwaysNeededDependencyTag) InstallDepNeeded() bool {
+	return true
+}
+
+var _ InstallNeededDependencyTag = InstallAlwaysNeededDependencyTag{}
+
+// IsInstallDepNeeded returns true if the dependency tag implements the InstallNeededDependencyTag
+// interface and the InstallDepNeeded returns true, meaning that the installed files of the parent
+// should depend on the installed files of the child.
+func IsInstallDepNeeded(tag blueprint.DependencyTag) bool {
+	if i, ok := tag.(InstallNeededDependencyTag); ok {
+		return i.InstallDepNeeded()
+	}
+	return false
+}
diff --git a/android/deptag_test.go b/android/deptag_test.go
new file mode 100644
index 0000000..bdd449e
--- /dev/null
+++ b/android/deptag_test.go
@@ -0,0 +1,135 @@
+// Copyright 2020 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package android
+
+import (
+	"testing"
+
+	"github.com/google/blueprint"
+)
+
+type testInstallDependencyTagModule struct {
+	ModuleBase
+	Properties struct {
+		Install_deps []string
+		Deps         []string
+	}
+}
+
+func (t *testInstallDependencyTagModule) GenerateAndroidBuildActions(ctx ModuleContext) {
+	outputFile := PathForModuleOut(ctx, "out")
+	ctx.Build(pctx, BuildParams{
+		Rule:   Touch,
+		Output: outputFile,
+	})
+	ctx.InstallFile(PathForModuleInstall(ctx), ctx.ModuleName(), outputFile)
+}
+
+var testInstallDependencyTagAlwaysDepTag = struct {
+	blueprint.DependencyTag
+	InstallAlwaysNeededDependencyTag
+}{}
+
+var testInstallDependencyTagNeverDepTag = struct {
+	blueprint.DependencyTag
+}{}
+
+func (t *testInstallDependencyTagModule) DepsMutator(ctx BottomUpMutatorContext) {
+	ctx.AddVariationDependencies(nil, testInstallDependencyTagAlwaysDepTag, t.Properties.Install_deps...)
+	ctx.AddVariationDependencies(nil, testInstallDependencyTagNeverDepTag, t.Properties.Deps...)
+}
+
+func testInstallDependencyTagModuleFactory() Module {
+	module := &testInstallDependencyTagModule{}
+	InitAndroidArchModule(module, HostAndDeviceDefault, MultilibCommon)
+	module.AddProperties(&module.Properties)
+	return module
+}
+
+func TestInstallDependencyTag(t *testing.T) {
+	bp := `
+		test_module {
+			name: "foo",
+			deps: ["dep"],
+			install_deps: ["install_dep"],
+		}
+
+		test_module {
+			name: "install_dep",
+			install_deps: ["transitive"],
+		}
+
+		test_module {
+			name: "transitive",
+		}
+
+		test_module {
+			name: "dep",
+		}
+	`
+
+	config := TestArchConfig(buildDir, nil, bp, nil)
+	ctx := NewTestArchContext(config)
+
+	ctx.RegisterModuleType("test_module", testInstallDependencyTagModuleFactory)
+
+	ctx.Register()
+	_, errs := ctx.ParseFileList(".", []string{"Android.bp"})
+	FailIfErrored(t, errs)
+	_, errs = ctx.PrepareBuildActions(config)
+	FailIfErrored(t, errs)
+
+	hostFoo := ctx.ModuleForTests("foo", config.BuildOSCommonTarget.String()).Description("install")
+	hostInstallDep := ctx.ModuleForTests("install_dep", config.BuildOSCommonTarget.String()).Description("install")
+	hostTransitive := ctx.ModuleForTests("transitive", config.BuildOSCommonTarget.String()).Description("install")
+	hostDep := ctx.ModuleForTests("dep", config.BuildOSCommonTarget.String()).Description("install")
+
+	if g, w := hostFoo.Implicits.Strings(), hostInstallDep.Output.String(); !InList(w, g) {
+		t.Errorf("expected host dependency %q, got %q", w, g)
+	}
+
+	if g, w := hostFoo.Implicits.Strings(), hostTransitive.Output.String(); !InList(w, g) {
+		t.Errorf("expected host dependency %q, got %q", w, g)
+	}
+
+	if g, w := hostInstallDep.Implicits.Strings(), hostTransitive.Output.String(); !InList(w, g) {
+		t.Errorf("expected host dependency %q, got %q", w, g)
+	}
+
+	if g, w := hostFoo.Implicits.Strings(), hostDep.Output.String(); InList(w, g) {
+		t.Errorf("expected no host dependency %q, got %q", w, g)
+	}
+
+	deviceFoo := ctx.ModuleForTests("foo", "android_common").Description("install")
+	deviceInstallDep := ctx.ModuleForTests("install_dep", "android_common").Description("install")
+	deviceTransitive := ctx.ModuleForTests("transitive", "android_common").Description("install")
+	deviceDep := ctx.ModuleForTests("dep", "android_common").Description("install")
+
+	if g, w := deviceFoo.OrderOnly.Strings(), deviceInstallDep.Output.String(); !InList(w, g) {
+		t.Errorf("expected device dependency %q, got %q", w, g)
+	}
+
+	if g, w := deviceFoo.OrderOnly.Strings(), deviceTransitive.Output.String(); !InList(w, g) {
+		t.Errorf("expected device dependency %q, got %q", w, g)
+	}
+
+	if g, w := deviceInstallDep.OrderOnly.Strings(), deviceTransitive.Output.String(); !InList(w, g) {
+		t.Errorf("expected device dependency %q, got %q", w, g)
+	}
+
+	if g, w := deviceFoo.OrderOnly.Strings(), deviceDep.Output.String(); InList(w, g) {
+		t.Errorf("expected no device dependency %q, got %q", w, g)
+	}
+}
diff --git a/android/module.go b/android/module.go
index d677406..ef1b0bd 100644
--- a/android/module.go
+++ b/android/module.go
@@ -1242,14 +1242,18 @@
 	return m.commonProperties.NamespaceExportedToMake
 }
 
+// computeInstallDeps finds the installed paths of all dependencies that have a dependency
+// tag that is annotated as needing installation via the IsInstallDepNeeded method.
 func (m *ModuleBase) computeInstallDeps(ctx blueprint.ModuleContext) InstallPaths {
-
 	var result InstallPaths
-	// TODO(ccross): we need to use WalkDeps and have some way to know which dependencies require installation
-	ctx.VisitDepsDepthFirst(func(m blueprint.Module) {
-		if a, ok := m.(Module); ok {
-			result = append(result, a.FilesToInstall()...)
+	ctx.WalkDeps(func(child, parent blueprint.Module) bool {
+		if a, ok := child.(Module); ok {
+			if IsInstallDepNeeded(ctx.OtherModuleDependencyTag(child)) {
+				result = append(result, a.FilesToInstall()...)
+				return true
+			}
 		}
+		return false
 	})
 
 	return result