diff --git a/cc/afdo.go b/cc/afdo.go
index be4f50a..49f6987 100644
--- a/cc/afdo.go
+++ b/cc/afdo.go
@@ -34,7 +34,7 @@
 
 var afdoProfileProjectsConfigKey = android.NewOnceKey("AfdoProfileProjects")
 
-const afdoCFlagsFormat = "-funique-internal-linkage-names -fprofile-sample-accurate -fprofile-sample-use=%s"
+const afdoCFlagsFormat = "-fprofile-sample-accurate -fprofile-sample-use=%s"
 
 func recordMissingAfdoProfileFile(ctx android.BaseModuleContext, missing string) {
 	getNamedMapForConfig(ctx.Config(), modulesMissingProfileFileKey).Store(missing, true)
@@ -66,10 +66,24 @@
 // afdoEnabled returns true for binaries and shared libraries
 // that set afdo prop to True and there is a profile available
 func (afdo *afdo) afdoEnabled() bool {
-	return afdo != nil && afdo.Properties.Afdo && afdo.Properties.FdoProfilePath != nil
+	return afdo != nil && afdo.Properties.Afdo
 }
 
 func (afdo *afdo) flags(ctx ModuleContext, flags Flags) Flags {
+	if afdo.Properties.Afdo {
+		// We use `-funique-internal-linkage-names` to associate profiles to the right internal
+		// functions. This option should be used before generating a profile. Because a profile
+		// generated for a binary without unique names doesn't work well building a binary with
+		// unique names (they have different internal function names).
+		// To avoid a chicken-and-egg problem, we enable `-funique-internal-linkage-names` when
+		// `afdo=true`, whether a profile exists or not.
+		// The profile can take effect in three steps:
+		// 1. Add `afdo: true` in Android.bp, and build the binary.
+		// 2. Collect an AutoFDO profile for the binary.
+		// 3. Make the profile searchable by the build system. So it's used the next time the binary
+		//	  is built.
+		flags.Local.CFlags = append([]string{"-funique-internal-linkage-names"}, flags.Local.CFlags...)
+	}
 	if path := afdo.Properties.FdoProfilePath; path != nil {
 		// The flags are prepended to allow overriding.
 		profileUseFlag := fmt.Sprintf(afdoCFlagsFormat, *path)
@@ -129,42 +143,41 @@
 // Propagate afdo requirements down from binaries and shared libraries
 func afdoDepsMutator(mctx android.TopDownMutatorContext) {
 	if m, ok := mctx.Module().(*Module); ok && m.afdo.afdoEnabled() {
-		if path := m.afdo.Properties.FdoProfilePath; path != nil {
-			mctx.WalkDeps(func(dep android.Module, parent android.Module) bool {
-				tag := mctx.OtherModuleDependencyTag(dep)
-				libTag, isLibTag := tag.(libraryDependencyTag)
+		path := m.afdo.Properties.FdoProfilePath
+		mctx.WalkDeps(func(dep android.Module, parent android.Module) bool {
+			tag := mctx.OtherModuleDependencyTag(dep)
+			libTag, isLibTag := tag.(libraryDependencyTag)
 
-				// Do not recurse down non-static dependencies
-				if isLibTag {
-					if !libTag.static() {
-						return false
-					}
-				} else {
-					if tag != objDepTag && tag != reuseObjTag {
-						return false
-					}
+			// Do not recurse down non-static dependencies
+			if isLibTag {
+				if !libTag.static() {
+					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,
-						},
-					)
+			} else {
+				if tag != objDepTag && tag != reuseObjTag {
+					return false
 				}
+			}
 
-				return true
-			})
-		}
+			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 && m.afdo.Properties.FdoProfilePath != nil {
+		if !m.static() && m.afdo.Properties.Afdo {
 			mctx.SetDependencyVariation(encodeTarget(m.Name()))
 			return
 		}
@@ -182,7 +195,7 @@
 			//                   \                      ^
 			//                    ----------------------|
 			// We only need to create one variant per unique rdep
-			if variantNameToProfilePath[variantName] == nil {
+			if _, exists := variantNameToProfilePath[variantName]; !exists {
 				variationNames = append(variationNames, variantName)
 				variantNameToProfilePath[variantName] = afdoRDep.ProfilePath
 			}
@@ -197,6 +210,7 @@
 				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 1c20bfc..b250ad1 100644
--- a/cc/afdo_test.go
+++ b/cc/afdo_test.go
@@ -379,3 +379,85 @@
 		t.Errorf("libFoo missing dependency on non-afdo variant of libBar")
 	}
 }
+
+func TestAfdoDepsWithoutProfile(t *testing.T) {
+	t.Parallel()
+	bp := `
+	cc_library_shared {
+		name: "libTest",
+		srcs: ["test.c"],
+		static_libs: ["libFoo"],
+		afdo: true,
+	}
+
+	cc_library_static {
+		name: "libFoo",
+		srcs: ["foo.c"],
+		static_libs: ["libBar"],
+	}
+
+	cc_library_static {
+		name: "libBar",
+		srcs: ["bar.c"],
+	}
+	`
+
+	result := android.GroupFixturePreparers(
+		PrepareForTestWithFdoProfile,
+		prepareForCcTest,
+	).RunTestWithBp(t, bp)
+
+	// Even without a profile path, the afdo enabled libraries should be built with
+	// -funique-internal-linkage-names.
+	expectedCFlag := "-funique-internal-linkage-names"
+
+	libTest := result.ModuleForTests("libTest", "android_arm64_armv8-a_shared")
+	libFooAfdoVariant := result.ModuleForTests("libFoo", "android_arm64_armv8-a_static_afdo-libTest")
+	libBarAfdoVariant := result.ModuleForTests("libBar", "android_arm64_armv8-a_static_afdo-libTest")
+
+	// Check cFlags of afdo-enabled module and the afdo-variant of its static deps
+	cFlags := libTest.Rule("cc").Args["cFlags"]
+	if !strings.Contains(cFlags, expectedCFlag) {
+		t.Errorf("Expected 'libTest' to enable afdo, but did not find %q in cflags %q", expectedCFlag, cFlags)
+	}
+
+	cFlags = libFooAfdoVariant.Rule("cc").Args["cFlags"]
+	if !strings.Contains(cFlags, expectedCFlag) {
+		t.Errorf("Expected 'libFooAfdoVariant' to enable afdo, but did not find %q in cflags %q", expectedCFlag, cFlags)
+	}
+
+	cFlags = libBarAfdoVariant.Rule("cc").Args["cFlags"]
+	if !strings.Contains(cFlags, expectedCFlag) {
+		t.Errorf("Expected 'libBarAfdoVariant' to enable afdo, but did not find %q in cflags %q", expectedCFlag, cFlags)
+	}
+	// Check dependency edge from afdo-enabled module to static deps
+	if !hasDirectDep(result, libTest.Module(), libFooAfdoVariant.Module()) {
+		t.Errorf("libTest missing dependency on afdo variant of libFoo")
+	}
+
+	if !hasDirectDep(result, libFooAfdoVariant.Module(), libBarAfdoVariant.Module()) {
+		t.Errorf("libTest missing dependency on afdo variant of libBar")
+	}
+
+	// Verify non-afdo variant exists and doesn't contain afdo
+	libFoo := result.ModuleForTests("libFoo", "android_arm64_armv8-a_static")
+	libBar := result.ModuleForTests("libBar", "android_arm64_armv8-a_static")
+
+	cFlags = libFoo.Rule("cc").Args["cFlags"]
+	if strings.Contains(cFlags, expectedCFlag) {
+		t.Errorf("Expected 'libFoo' to not enable afdo, but found %q in cflags %q", expectedCFlag, cFlags)
+	}
+	cFlags = libBar.Rule("cc").Args["cFlags"]
+	if strings.Contains(cFlags, expectedCFlag) {
+		t.Errorf("Expected 'libBar' to not enable afdo, but found %q in cflags %q", expectedCFlag, cFlags)
+	}
+
+	// Check dependency edges of static deps
+	if hasDirectDep(result, libTest.Module(), libFoo.Module()) {
+		t.Errorf("libTest should not depend on non-afdo variant of libFoo")
+	}
+
+	if !hasDirectDep(result, libFoo.Module(), libBar.Module()) {
+		t.Errorf("libFoo missing dependency on non-afdo variant of libBar")
+	}
+}