diff --git a/cc/afdo.go b/cc/afdo.go
index 6155084..79fbae1 100644
--- a/cc/afdo.go
+++ b/cc/afdo.go
@@ -27,12 +27,23 @@
 // This flag needs to be in both CFlags and LdFlags to ensure correct symbol ordering
 const afdoFlagsFormat = "-fprofile-sample-use=%s -fprofile-sample-accurate"
 
+func recordMissingAfdoProfileFile(ctx android.BaseModuleContext, missing string) {
+	getNamedMapForConfig(ctx.Config(), modulesMissingProfileFileKey).Store(missing, true)
+}
+
+type afdoRdep struct {
+	VariationName *string
+	ProfilePath   *string
+}
+
 type AfdoProperties struct {
 	// Afdo allows developers self-service enroll for
 	// automatic feedback-directed optimization using profile data.
 	Afdo bool
 
 	FdoProfilePath *string `blueprint:"mutated"`
+
+	AfdoRDeps []afdoRdep `blueprint:"mutated"`
 }
 
 type afdo struct {
@@ -91,6 +102,29 @@
 	return flags
 }
 
+func (afdo *afdo) addDep(ctx BaseModuleContext, actx android.BottomUpMutatorContext) {
+	if ctx.Host() {
+		return
+	}
+
+	if ctx.static() && !ctx.staticBinary() {
+		return
+	}
+
+	if c, ok := ctx.Module().(*Module); ok && c.Enabled() {
+		if fdoProfileName, err := actx.DeviceConfig().AfdoProfile(actx.ModuleName()); fdoProfileName != nil && err == nil {
+			actx.AddFarVariationDependencies(
+				[]blueprint.Variation{
+					{Mutator: "arch", Variation: actx.Target().ArchVariation()},
+					{Mutator: "os", Variation: "android"},
+				},
+				FdoProfileTag,
+				[]string{*fdoProfileName}...,
+			)
+		}
+	}
+}
+
 // FdoProfileMutator reads the FdoProfileProvider from a direct dep with FdoProfileTag
 // assigns FdoProfileInfo.Path to the FdoProfilePath mutated property
 func (c *Module) fdoProfileMutator(ctx android.BottomUpMutatorContext) {
@@ -102,96 +136,87 @@
 		return
 	}
 
-	if c.Host() {
-		return
-	}
-
-	if c.static() && !c.staticBinary() {
-		return
-	}
-
-	if c, ok := ctx.Module().(*Module); ok && c.Enabled() {
-		if fdoProfileName, err := ctx.DeviceConfig().AfdoProfile(ctx.ModuleName()); fdoProfileName != "" && err == nil {
-			deps := ctx.AddFarVariationDependencies(
-				[]blueprint.Variation{
-					{Mutator: "arch", Variation: ctx.Target().ArchVariation()},
-					{Mutator: "os", Variation: "android"},
-				},
-				FdoProfileTag,
-				fdoProfileName)
-			if len(deps) > 0 && deps[0] != nil {
-				if info, ok := android.OtherModuleProvider(ctx, deps[0], FdoProfileProvider); ok {
-					c.afdo.Properties.FdoProfilePath = proptools.StringPtr(info.Path.String())
-				}
-			}
+	ctx.VisitDirectDepsWithTag(FdoProfileTag, func(m android.Module) {
+		if info, ok := android.OtherModuleProvider(ctx, m, FdoProfileProvider); ok {
+			c.afdo.Properties.FdoProfilePath = proptools.StringPtr(info.Path.String())
 		}
-	}
+	})
 }
 
 var _ FdoProfileMutatorInterface = (*Module)(nil)
 
-func afdoPropagateViaDepTag(tag blueprint.DependencyTag) bool {
-	libTag, isLibTag := tag.(libraryDependencyTag)
-	// Do not recurse down non-static dependencies
-	if isLibTag {
-		return libTag.static()
-	} else {
-		return tag == objDepTag || tag == reuseObjTag || tag == staticVariantTag
-	}
-}
+// Propagate afdo requirements down from binaries and shared libraries
+func afdoDepsMutator(mctx android.TopDownMutatorContext) {
+	if m, ok := mctx.Module().(*Module); ok && m.afdo.afdoEnabled() {
+		path := m.afdo.Properties.FdoProfilePath
+		mctx.WalkDeps(func(dep android.Module, parent android.Module) bool {
+			tag := mctx.OtherModuleDependencyTag(dep)
+			libTag, isLibTag := tag.(libraryDependencyTag)
 
-// afdoTransitionMutator creates afdo variants of cc modules.
-type afdoTransitionMutator struct{}
-
-func (a *afdoTransitionMutator) Split(ctx android.BaseModuleContext) []string {
-	return []string{""}
-}
-
-func (a *afdoTransitionMutator) OutgoingTransition(ctx android.OutgoingTransitionContext, sourceVariation string) string {
-	if m, ok := ctx.Module().(*Module); ok && m.afdo != nil {
-		if !afdoPropagateViaDepTag(ctx.DepTag()) {
-			return ""
-		}
-
-		if sourceVariation != "" {
-			return sourceVariation
-		}
-
-		if m.afdo.afdoEnabled() && !(m.static() && !m.staticBinary()) && !m.Host() {
-			return encodeTarget(ctx.Module().Name())
-		}
-	}
-	return ""
-}
-
-func (a *afdoTransitionMutator) IncomingTransition(ctx android.IncomingTransitionContext, incomingVariation string) string {
-	if m, ok := ctx.Module().(*Module); ok && m.afdo != nil {
-		return incomingVariation
-	}
-	return ""
-}
-
-func (a *afdoTransitionMutator) Mutate(ctx android.BottomUpMutatorContext, variation string) {
-	if variation == "" {
-		return
-	}
-
-	if m, ok := ctx.Module().(*Module); ok && m.afdo != nil {
-		m.Properties.PreventInstall = true
-		m.Properties.HideFromMake = true
-		m.afdo.Properties.Afdo = true
-		if fdoProfileName, err := ctx.DeviceConfig().AfdoProfile(decodeTarget(variation)); fdoProfileName != "" && err == nil {
-			deps := ctx.AddFarVariationDependencies(
-				[]blueprint.Variation{
-					{Mutator: "arch", Variation: ctx.Target().ArchVariation()},
-					{Mutator: "os", Variation: "android"},
-				},
-				FdoProfileTag,
-				fdoProfileName)
-			if len(deps) > 0 && deps[0] != nil {
-				if info, ok := android.OtherModuleProvider(ctx, deps[0], FdoProfileProvider); ok {
-					m.afdo.Properties.FdoProfilePath = proptools.StringPtr(info.Path.String())
+			// Do not recurse down non-static dependencies
+			if isLibTag {
+				if !libTag.static() {
+					return false
 				}
+			} else {
+				if tag != objDepTag && tag != reuseObjTag {
+					return false
+				}
+			}
+
+			if dep, ok := dep.(*Module); ok {
+				dep.afdo.Properties.AfdoRDeps = append(
+					dep.afdo.Properties.AfdoRDeps,
+					afdoRdep{
+						VariationName: proptools.StringPtr(encodeTarget(m.Name())),
+						ProfilePath:   path,
+					},
+				)
+			}
+
+			return true
+		})
+	}
+}
+
+// Create afdo variants for modules that need them
+func afdoMutator(mctx android.BottomUpMutatorContext) {
+	if m, ok := mctx.Module().(*Module); ok && m.afdo != nil {
+		if !m.static() && m.afdo.Properties.Afdo {
+			mctx.SetDependencyVariation(encodeTarget(m.Name()))
+			return
+		}
+
+		variationNames := []string{""}
+
+		variantNameToProfilePath := make(map[string]*string)
+
+		for _, afdoRDep := range m.afdo.Properties.AfdoRDeps {
+			variantName := *afdoRDep.VariationName
+			// An rdep can be set twice in AfdoRDeps because there can be
+			// more than one path from an afdo-enabled module to
+			// a static dep such as
+			// afdo_enabled_foo -> static_bar ----> static_baz
+			//                   \                      ^
+			//                    ----------------------|
+			// We only need to create one variant per unique rdep
+			if _, exists := variantNameToProfilePath[variantName]; !exists {
+				variationNames = append(variationNames, variantName)
+				variantNameToProfilePath[variantName] = afdoRDep.ProfilePath
+			}
+		}
+
+		if len(variationNames) > 1 {
+			modules := mctx.CreateVariations(variationNames...)
+			for i, name := range variationNames {
+				if name == "" {
+					continue
+				}
+				variation := modules[i].(*Module)
+				variation.Properties.PreventInstall = true
+				variation.Properties.HideFromMake = true
+				variation.afdo.Properties.Afdo = true
+				variation.afdo.Properties.FdoProfilePath = variantNameToProfilePath[name]
 			}
 		}
 	}
diff --git a/cc/afdo_test.go b/cc/afdo_test.go
index 584af0d..b250ad1 100644
--- a/cc/afdo_test.go
+++ b/cc/afdo_test.go
@@ -174,11 +174,11 @@
 	libBar := result.ModuleForTests("libBar", "android_arm64_armv8-a_static").Module()
 
 	if !hasDirectDep(result, libTest, libFoo.Module()) {
-		t.Errorf("libTest missing dependency on non-afdo variant of libFoo")
+		t.Errorf("libTest missing dependency on afdo variant of libFoo")
 	}
 
 	if !hasDirectDep(result, libFoo.Module(), libBar) {
-		t.Errorf("libFoo missing dependency on non-afdo variant of libBar")
+		t.Errorf("libFoo missing dependency on afdo variant of libBar")
 	}
 
 	fooVariants := result.ModuleVariantsForTests("foo")
diff --git a/cc/cc.go b/cc/cc.go
index cac52cf..1a9c7bf 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -55,7 +55,7 @@
 		ctx.BottomUp("test_per_src", TestPerSrcMutator).Parallel()
 		ctx.BottomUp("version", versionMutator).Parallel()
 		ctx.BottomUp("begin", BeginMutator).Parallel()
-		ctx.BottomUp("fdo_profile", fdoProfileMutator).Parallel()
+		ctx.BottomUp("fdo_profile", fdoProfileMutator)
 	})
 
 	ctx.PostDepsMutators(func(ctx android.RegisterMutatorsContext) {
@@ -70,7 +70,8 @@
 
 		ctx.Transition("coverage", &coverageTransitionMutator{})
 
-		ctx.Transition("afdo", &afdoTransitionMutator{})
+		ctx.TopDown("afdo_deps", afdoDepsMutator)
+		ctx.BottomUp("afdo", afdoMutator).Parallel()
 
 		ctx.Transition("orderfile", &orderfileTransitionMutator{})
 
@@ -2338,6 +2339,10 @@
 	}
 	ctx.ctx = ctx
 
+	if !actx.Host() || !ctx.static() || ctx.staticBinary() {
+		c.afdo.addDep(ctx, actx)
+	}
+
 	c.begin(ctx)
 }