diff --git a/cc/builder.go b/cc/builder.go
index 72c2fa5..fea65d5 100644
--- a/cc/builder.go
+++ b/cc/builder.go
@@ -549,6 +549,10 @@
 		return "$" + kind + n
 	}
 
+	// clang-tidy checks source files and does not need to link with libraries.
+	// tidyPathDeps should contain pathDeps but not libraries.
+	tidyPathDeps := skipNdkLibraryDeps(ctx, pathDeps)
+
 	for i, srcFile := range srcFiles {
 		objFile := android.ObjPathWithExt(ctx, subdir, srcFile, "o")
 
@@ -672,7 +676,7 @@
 				Output:      tidyFile,
 				Input:       srcFile,
 				Implicits:   cFlagsDeps,
-				OrderOnly:   pathDeps,
+				OrderOnly:   tidyPathDeps,
 				Args: map[string]string{
 					"ccCmd":     ccCmd,
 					"cFlags":    shareFlags("cFlags", escapeSingleQuotes(moduleToolingFlags)),
diff --git a/cc/ndk_sysroot.go b/cc/ndk_sysroot.go
index fd458d9..ee11db1 100644
--- a/cc/ndk_sysroot.go
+++ b/cc/ndk_sysroot.go
@@ -82,12 +82,33 @@
 	return android.PathForOutput(ctx, "ndk_base.timestamp")
 }
 
+// The headers timestamp file depends only on the NDK headers.
+// This is used mainly for .tidy files that do not need any stub libraries.
+func getNdkHeadersTimestampFile(ctx android.PathContext) android.WritablePath {
+	return android.PathForOutput(ctx, "ndk_headers.timestamp")
+}
+
 // The full timestamp file depends on the base timestamp *and* the static
 // libraries.
 func getNdkFullTimestampFile(ctx android.PathContext) android.WritablePath {
 	return android.PathForOutput(ctx, "ndk.timestamp")
 }
 
+// Replace ndk_base.timestamp and ndk.timestamp with ndk_headers.timestamp.
+func skipNdkLibraryDeps(ctx android.ModuleContext, paths android.Paths) android.Paths {
+	var newPaths android.Paths
+	baseTimestamp := getNdkBaseTimestampFile(ctx)
+	fullTimestamp := getNdkFullTimestampFile(ctx)
+	headersTimestamp := getNdkHeadersTimestampFile(ctx)
+	for _, path := range paths {
+		if path == baseTimestamp || path == fullTimestamp {
+			path = headersTimestamp
+		}
+		newPaths = append(newPaths, path)
+	}
+	return newPaths
+}
+
 func NdkSingleton() android.Singleton {
 	return &ndkSingleton{}
 }
@@ -96,6 +117,7 @@
 
 func (n *ndkSingleton) GenerateBuildActions(ctx android.SingletonContext) {
 	var staticLibInstallPaths android.Paths
+	var headerPaths android.Paths
 	var installPaths android.Paths
 	var licensePaths android.Paths
 	ctx.VisitAllModules(func(module android.Module) {
@@ -104,16 +126,19 @@
 		}
 
 		if m, ok := module.(*headerModule); ok {
+			headerPaths = append(headerPaths, m.installPaths...)
 			installPaths = append(installPaths, m.installPaths...)
 			licensePaths = append(licensePaths, m.licensePath)
 		}
 
 		if m, ok := module.(*versionedHeaderModule); ok {
+			headerPaths = append(headerPaths, m.installPaths...)
 			installPaths = append(installPaths, m.installPaths...)
 			licensePaths = append(licensePaths, m.licensePath)
 		}
 
 		if m, ok := module.(*preprocessedHeadersModule); ok {
+			headerPaths = append(headerPaths, m.installPaths...)
 			installPaths = append(installPaths, m.installPaths...)
 			licensePaths = append(licensePaths, m.licensePath)
 		}
@@ -153,6 +178,12 @@
 		Validation: getNdkAbiDiffTimestampFile(ctx),
 	})
 
+	ctx.Build(pctx, android.BuildParams{
+		Rule:      android.Touch,
+		Output:    getNdkHeadersTimestampFile(ctx),
+		Implicits: headerPaths,
+	})
+
 	fullDepPaths := append(staticLibInstallPaths, getNdkBaseTimestampFile(ctx))
 
 	// There's a phony "ndk" rule defined in core/main.mk that depends on this.