diff --git a/cc/cc.go b/cc/cc.go
index b7183d7..592f373 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -52,7 +52,7 @@
 		ctx.TopDown("tsan_deps", sanitizerDepsMutator(tsan))
 		ctx.BottomUp("tsan", sanitizerMutator(tsan)).Parallel()
 
-		ctx.TopDown("sanitize_runtime_deps", sanitizerRuntimeDepsMutator())
+		ctx.TopDown("sanitize_runtime_deps", sanitizerRuntimeDepsMutator)
 
 		ctx.BottomUp("coverage", coverageLinkingMutator).Parallel()
 		ctx.TopDown("vndk_deps", sabiDepsMutator)
diff --git a/cc/sanitize.go b/cc/sanitize.go
index 38f4fc2..080ac09 100644
--- a/cc/sanitize.go
+++ b/cc/sanitize.go
@@ -21,6 +21,8 @@
 	"strings"
 	"sync"
 
+	"github.com/google/blueprint"
+
 	"android/soong/android"
 	"android/soong/cc/config"
 )
@@ -610,43 +612,54 @@
 	return sanitizerVal != nil && *sanitizerVal == true
 }
 
+func isSanitizableDependencyTag(tag blueprint.DependencyTag) bool {
+	t, ok := tag.(dependencyTag)
+	return ok && t.library || t == reuseObjTag
+}
+
 // Propagate asan requirements down from binaries
 func sanitizerDepsMutator(t sanitizerType) func(android.TopDownMutatorContext) {
 	return func(mctx android.TopDownMutatorContext) {
 		if c, ok := mctx.Module().(*Module); ok && c.sanitize.isSanitizerEnabled(t) {
-			mctx.VisitDepsDepthFirst(func(module android.Module) {
-				if d, ok := module.(*Module); ok && d.sanitize != nil &&
+			mctx.WalkDeps(func(child, parent android.Module) bool {
+				if !isSanitizableDependencyTag(mctx.OtherModuleDependencyTag(child)) {
+					return false
+				}
+				if d, ok := child.(*Module); ok && d.sanitize != nil &&
 					!Bool(d.sanitize.Properties.Sanitize.Never) &&
 					!d.sanitize.isSanitizerExplicitlyDisabled(t) {
 					if (t == cfi && d.static()) || t != cfi {
 						d.sanitize.Properties.SanitizeDep = true
 					}
 				}
+				return true
 			})
 		}
 	}
 }
 
 // Propagate the ubsan minimal runtime dependency when there are integer overflow sanitized static dependencies.
-func sanitizerRuntimeDepsMutator() func(android.TopDownMutatorContext) {
-	return func(mctx android.TopDownMutatorContext) {
-		if c, ok := mctx.Module().(*Module); ok && c.sanitize != nil {
-			mctx.VisitDepsDepthFirst(func(module android.Module) {
-				if d, ok := module.(*Module); ok && d.static() && d.sanitize != nil {
+func sanitizerRuntimeDepsMutator(mctx android.TopDownMutatorContext) {
+	if c, ok := mctx.Module().(*Module); ok && c.sanitize != nil {
+		mctx.WalkDeps(func(child, parent android.Module) bool {
+			if !isSanitizableDependencyTag(mctx.OtherModuleDependencyTag(child)) {
+				return false
+			}
+			if d, ok := child.(*Module); ok && d.static() && d.sanitize != nil {
 
-					if enableMinimalRuntime(d.sanitize) {
-						// If a static dependency is built with the minimal runtime,
-						// make sure we include the ubsan minimal runtime.
-						c.sanitize.Properties.MinimalRuntimeDep = true
-					} else if Bool(d.sanitize.Properties.Sanitize.Diag.Integer_overflow) ||
-						len(d.sanitize.Properties.Sanitize.Diag.Misc_undefined) > 0 {
-						// If a static dependency runs with full ubsan diagnostics,
-						// make sure we include the ubsan runtime.
-						c.sanitize.Properties.UbsanRuntimeDep = true
-					}
+				if enableMinimalRuntime(d.sanitize) {
+					// If a static dependency is built with the minimal runtime,
+					// make sure we include the ubsan minimal runtime.
+					c.sanitize.Properties.MinimalRuntimeDep = true
+				} else if Bool(d.sanitize.Properties.Sanitize.Diag.Integer_overflow) ||
+					len(d.sanitize.Properties.Sanitize.Diag.Misc_undefined) > 0 {
+					// If a static dependency runs with full ubsan diagnostics,
+					// make sure we include the ubsan runtime.
+					c.sanitize.Properties.UbsanRuntimeDep = true
 				}
-			})
-		}
+			}
+			return true
+		})
 	}
 }