diff --git a/cc/cc.go b/cc/cc.go
index 9722cf0..1e313c0 100644
--- a/cc/cc.go
+++ b/cc/cc.go
@@ -40,6 +40,7 @@
 		ctx.BottomUp("ndk_api", ndkApiMutator).Parallel()
 		ctx.BottomUp("test_per_src", testPerSrcMutator).Parallel()
 		ctx.BottomUp("begin", beginMutator).Parallel()
+		ctx.BottomUp("coverage", coverageLinkingMutator).Parallel()
 	})
 
 	android.PostDepsMutators(func(ctx android.RegisterMutatorsContext) {
@@ -54,7 +55,6 @@
 
 		ctx.TopDown("sanitize_runtime_deps", sanitizerRuntimeDepsMutator())
 
-		ctx.BottomUp("coverage", coverageLinkingMutator).Parallel()
 		ctx.TopDown("vndk_deps", sabiDepsMutator)
 
 		ctx.TopDown("lto_deps", ltoDepsMutator)
@@ -809,12 +809,15 @@
 	if c.compiler != nil {
 		deps = c.compiler.compilerDeps(ctx, deps)
 	}
-	// Add the PGO dependency (the clang_rt.profile runtime library), which
-	// sometimes depends on symbols from libgcc, before libgcc gets added
-	// in linkerDeps().
+	// clang_rt.profile runtime libraries necessary for PGO and coverage
+	// depend on symbols from libgcc.  Add the runtime library dependency
+	// before libgcc gets added in linkerDeps().
 	if c.pgo != nil {
 		deps = c.pgo.deps(ctx, deps)
 	}
+	if c.coverage != nil {
+		deps = c.coverage.deps(ctx, deps)
+	}
 	if c.linker != nil {
 		deps = c.linker.linkerDeps(ctx, deps)
 	}
@@ -824,9 +827,6 @@
 	if c.sanitize != nil {
 		deps = c.sanitize.deps(ctx, deps)
 	}
-	if c.coverage != nil {
-		deps = c.coverage.deps(ctx, deps)
-	}
 	if c.sabi != nil {
 		deps = c.sabi.deps(ctx, deps)
 	}
diff --git a/cc/config/toolchain.go b/cc/config/toolchain.go
index ca863a7..19d2828 100644
--- a/cc/config/toolchain.go
+++ b/cc/config/toolchain.go
@@ -85,6 +85,8 @@
 	AvailableLibraries() []string
 
 	Bionic() bool
+
+	profileRuntimeLibrary() string
 }
 
 type toolchainBase struct {
@@ -169,6 +171,10 @@
 	return true
 }
 
+func (t toolchainBase) profileRuntimeLibrary() string {
+	return ""
+}
+
 func (t toolchainBase) ToolPath() string {
 	return ""
 }
@@ -240,6 +246,12 @@
 }
 
 func ProfileRuntimeLibrary(t Toolchain) string {
+	lib := t.profileRuntimeLibrary()
+	if lib != "" {
+		// Return the directly exported profile library
+		return lib
+	}
+	// Return the Android-specific library
 	return SanitizerRuntimeLibrary(t, "profile")
 }
 
diff --git a/cc/config/x86_linux_bionic_host.go b/cc/config/x86_linux_bionic_host.go
index a9fb1f6..290793e 100644
--- a/cc/config/x86_linux_bionic_host.go
+++ b/cc/config/x86_linux_bionic_host.go
@@ -151,6 +151,10 @@
 	return true
 }
 
+func (t *toolchainLinuxBionic) profileRuntimeLibrary() string {
+	return "libclang_rt.profile-x86_64"
+}
+
 var toolchainLinuxBionicSingleton Toolchain = &toolchainLinuxBionic{}
 
 func linuxBionicToolchainFactory(arch android.Arch) Toolchain {
diff --git a/cc/config/x86_linux_host.go b/cc/config/x86_linux_host.go
index 354500e..653f819 100644
--- a/cc/config/x86_linux_host.go
+++ b/cc/config/x86_linux_host.go
@@ -270,6 +270,14 @@
 	return "${config.LinuxX8664YasmFlags}"
 }
 
+func (t *toolchainLinuxX86) profileRuntimeLibrary() string {
+	return "libclang_rt.profile-i386"
+}
+
+func (t *toolchainLinuxX8664) profileRuntimeLibrary() string {
+	return "libclang_rt.profile-x86_64"
+}
+
 func (t *toolchainLinux) AvailableLibraries() []string {
 	return linuxAvailableLibraries
 }
diff --git a/cc/coverage.go b/cc/coverage.go
index 391b118..671353c 100644
--- a/cc/coverage.go
+++ b/cc/coverage.go
@@ -16,6 +16,7 @@
 
 import (
 	"android/soong/android"
+	"android/soong/cc/config"
 )
 
 type CoverageProperties struct {
@@ -38,6 +39,10 @@
 func (cov *coverage) begin(ctx BaseModuleContext) {}
 
 func (cov *coverage) deps(ctx BaseModuleContext, deps Deps) Deps {
+	if cov.Properties.CoverageEnabled {
+		runtimeLibrary := config.ProfileRuntimeLibrary(ctx.toolchain())
+		deps.LateStaticLibs = append(deps.LateStaticLibs, runtimeLibrary)
+	}
 	return deps
 }
 
@@ -99,9 +104,8 @@
 
 		if !mctx.DeviceConfig().NativeCoverageEnabled() {
 			// Coverage is disabled globally
-		} else if mctx.Host() {
-			// TODO(dwillemsen): because of -nodefaultlibs, we must depend on libclang_rt.profile-*.a
-			// Just turn off for now.
+		} else if mctx.Darwin() || mctx.Windows() {
+			// Coverage not supported for Darwin and Windows
 		} else if c.coverage.Properties.Native_coverage != nil {
 			enabled = *c.coverage.Properties.Native_coverage
 		} else {