diff --git a/cc/builder.go b/cc/builder.go
index 3d5bb77..a1d7f2c 100644
--- a/cc/builder.go
+++ b/cc/builder.go
@@ -45,6 +45,7 @@
 			Depfile:     "${out}.d",
 			Deps:        blueprint.DepsGCC,
 			Command:     "$relPwd $ccCmd -c $cFlags -MD -MF ${out}.d -o $out $in",
+			CommandDeps: []string{"$ccCmd"},
 			Description: "cc $out",
 		},
 		"ccCmd", "cFlags")
@@ -53,6 +54,7 @@
 		blueprint.RuleParams{
 			Command: "$ldCmd ${ldDirFlags} ${crtBegin} @${out}.rsp " +
 				"${libFlags} ${crtEnd} -o ${out} ${ldFlags}",
+			CommandDeps:    []string{"$ldCmd"},
 			Description:    "ld $out",
 			Rspfile:        "${out}.rsp",
 			RspfileContent: "${in}",
@@ -62,6 +64,7 @@
 	partialLd = pctx.StaticRule("partialLd",
 		blueprint.RuleParams{
 			Command:     "$ldCmd -r ${in} -o ${out}",
+			CommandDeps: []string{"$ldCmd"},
 			Description: "partialLd $out",
 		},
 		"ldCmd")
@@ -69,6 +72,7 @@
 	ar = pctx.StaticRule("ar",
 		blueprint.RuleParams{
 			Command:        "rm -f ${out} && $arCmd $arFlags $out @${out}.rsp",
+			CommandDeps:    []string{"$arCmd"},
 			Description:    "ar $out",
 			Rspfile:        "${out}.rsp",
 			RspfileContent: "${in}",
@@ -78,6 +82,7 @@
 	darwinAr = pctx.StaticRule("darwinAr",
 		blueprint.RuleParams{
 			Command:     "rm -f ${out} && $arCmd $arFlags $out $in",
+			CommandDeps: []string{"$arCmd"},
 			Description: "ar $out",
 		},
 		"arCmd", "arFlags")
@@ -85,6 +90,7 @@
 	darwinAppendAr = pctx.StaticRule("darwinAppendAr",
 		blueprint.RuleParams{
 			Command:     "cp -f ${inAr} ${out}.tmp && $arCmd $arFlags ${out}.tmp $in && mv ${out}.tmp ${out}",
+			CommandDeps: []string{"$arCmd"},
 			Description: "ar $out",
 		},
 		"arCmd", "arFlags", "inAr")
@@ -92,6 +98,7 @@
 	prefixSymbols = pctx.StaticRule("prefixSymbols",
 		blueprint.RuleParams{
 			Command:     "$objcopyCmd --prefix-symbols=${prefix} ${in} ${out}",
+			CommandDeps: []string{"$objcopyCmd"},
 			Description: "prefixSymbols $out",
 		},
 		"objcopyCmd", "prefix")
@@ -103,6 +110,7 @@
 			Depfile:     "${out}.d",
 			Deps:        blueprint.DepsGCC,
 			Command:     "$copyGccLibPath $out $ccCmd $cFlags -print-file-name=${libName}",
+			CommandDeps: []string{"$copyGccLibPath", "$ccCmd"},
 			Description: "copy gcc $out",
 		},
 		"ccCmd", "cFlags", "libName")
@@ -202,13 +210,11 @@
 			ccCmd = gccCmd(flags.toolchain, ccCmd)
 		}
 
-		objDeps := append([]string{ccCmd}, deps...)
-
 		ctx.Build(pctx, blueprint.BuildParams{
 			Rule:      cc,
 			Outputs:   []string{objFile},
 			Inputs:    []string{srcFile},
-			Implicits: objDeps,
+			Implicits: deps,
 			Args: map[string]string{
 				"cFlags": moduleCflags,
 				"ccCmd":  ccCmd,
@@ -227,10 +233,9 @@
 	arFlags := "crsPD"
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      ar,
-		Outputs:   []string{outputFile},
-		Inputs:    objFiles,
-		Implicits: []string{arCmd},
+		Rule:    ar,
+		Outputs: []string{outputFile},
+		Inputs:  objFiles,
 		Args: map[string]string{
 			"arFlags": arFlags,
 			"arCmd":   arCmd,
@@ -337,7 +342,6 @@
 		ldDirs = append(ldDirs, dir)
 	}
 
-	deps = append(deps, ldCmd)
 	deps = append(deps, sharedLibs...)
 	deps = append(deps, staticLibs...)
 	deps = append(deps, lateStaticLibs...)
@@ -368,13 +372,10 @@
 
 	ldCmd := gccCmd(flags.toolchain, "ld")
 
-	deps := []string{ldCmd}
-
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      partialLd,
-		Outputs:   []string{outputFile},
-		Inputs:    objFiles,
-		Implicits: deps,
+		Rule:    partialLd,
+		Outputs: []string{outputFile},
+		Inputs:  objFiles,
 		Args: map[string]string{
 			"ldCmd": ldCmd,
 		},
@@ -388,10 +389,9 @@
 	objcopyCmd := gccCmd(flags.toolchain, "objcopy")
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      prefixSymbols,
-		Outputs:   []string{outputFile},
-		Inputs:    []string{inputFile},
-		Implicits: []string{objcopyCmd},
+		Rule:    prefixSymbols,
+		Outputs: []string{outputFile},
+		Inputs:  []string{inputFile},
 		Args: map[string]string{
 			"objcopyCmd": objcopyCmd,
 			"prefix":     prefix,
@@ -405,10 +405,6 @@
 	ctx.Build(pctx, blueprint.BuildParams{
 		Rule:    copyGccLib,
 		Outputs: []string{outputFile},
-		Implicits: []string{
-			"$copyGccLibPath",
-			gccCmd(flags.toolchain, "gcc"),
-		},
 		Args: map[string]string{
 			"ccCmd":   gccCmd(flags.toolchain, "gcc"),
 			"cFlags":  flags.globalFlags,
diff --git a/cc/gen.go b/cc/gen.go
index 3bfe679..be50d75 100644
--- a/cc/gen.go
+++ b/cc/gen.go
@@ -38,6 +38,7 @@
 		blueprint.RuleParams{
 			Command: "BISON_PKGDATADIR=$yaccDataDir $yaccCmd -d $yaccFlags -o $cppFile $in && " +
 				"cp -f $hppFile $hFile",
+			CommandDeps: []string{"$yaccCmd"},
 			Description: "yacc $out",
 		},
 		"yaccFlags", "cppFile", "hppFile", "hFile")
@@ -45,6 +46,7 @@
 	lex = pctx.StaticRule("lex",
 		blueprint.RuleParams{
 			Command:     "$lexCmd -o$out $in",
+			CommandDeps: []string{"$lexCmd"},
 			Description: "lex $out",
 		})
 )
@@ -57,10 +59,9 @@
 	headerFile = pathtools.ReplaceExtension(cppFile, "h")
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      yacc,
-		Outputs:   []string{cppFile, headerFile},
-		Inputs:    []string{yaccFile},
-		Implicits: []string{"$yaccCmd"},
+		Rule:    yacc,
+		Outputs: []string{cppFile, headerFile},
+		Inputs:  []string{yaccFile},
 		Args: map[string]string{
 			"yaccFlags": yaccFlags,
 			"cppFile":   cppFile,
@@ -78,10 +79,9 @@
 	cppFile = pathtools.ReplaceExtension(cppFile, "cpp")
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      lex,
-		Outputs:   []string{cppFile},
-		Inputs:    []string{lexFile},
-		Implicits: []string{"$lexCmd"},
+		Rule:    lex,
+		Outputs: []string{cppFile},
+		Inputs:  []string{lexFile},
 	})
 
 	return cppFile
diff --git a/common/defs.go b/common/defs.go
index 0001ce1..67fcb1f 100644
--- a/common/defs.go
+++ b/common/defs.go
@@ -33,6 +33,7 @@
 	androidbp    = pctx.StaticRule("androidbp",
 		blueprint.RuleParams{
 			Command:     androidbpCmd + " ${srcDir}/Android.bp $in $out",
+			CommandDeps: []string{androidbpCmd},
 			Description: "androidbp $out",
 		})
 
diff --git a/common/glob.go b/common/glob.go
index 152be94..3de18ee 100644
--- a/common/glob.go
+++ b/common/glob.go
@@ -46,6 +46,7 @@
 	globRule = pctx.StaticRule("globRule",
 		blueprint.RuleParams{
 			Command:     fmt.Sprintf(`%s -o $out $excludes "$glob"`, globCmd),
+			CommandDeps: []string{globCmd},
 			Description: "glob $glob",
 
 			Restat:  true,
@@ -95,9 +96,8 @@
 	// Create a rule to rebuild fileListFile if a directory in depFile changes.  fileListFile
 	// will only be rewritten if it has changed, preventing unnecesary build.ninja regenerations.
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      globRule,
-		Outputs:   []string{fileListFile},
-		Implicits: []string{globCmd},
+		Rule:    globRule,
+		Outputs: []string{fileListFile},
 		Args: map[string]string{
 			"glob":     globPattern,
 			"excludes": JoinWithPrefixAndQuote(excludes, "-e "),
diff --git a/common/module.go b/common/module.go
index cb38513..33a801f 100644
--- a/common/module.go
+++ b/common/module.go
@@ -570,11 +570,10 @@
 
 		transMk := filepath.Join("androidmk", "Android_"+strings.Replace(filepath.Dir(origBp), "/", "_", -1)+".mk")
 		ctx.Build(pctx, blueprint.BuildParams{
-			Rule:      androidbp,
-			Outputs:   []string{transMk},
-			Inputs:    []string{bpFile},
-			Implicits: []string{androidbpCmd},
-			Optional:  true,
+			Rule:     androidbp,
+			Outputs:  []string{transMk},
+			Inputs:   []string{bpFile},
+			Optional: true,
 		})
 
 		androidMks = append(androidMks, transMk)
diff --git a/java/app_builder.go b/java/app_builder.go
index 8e907d2..4b3d315 100644
--- a/java/app_builder.go
+++ b/java/app_builder.go
@@ -34,6 +34,7 @@
 				`$aaptCmd package -m $aaptFlags -P $publicResourcesFile -G $proguardOptionsFile ` +
 				`-J $javaDir || ( rm -rf "$javaDir/*"; exit 41 ) && ` +
 				`find $javaDir -name "*.java" > $javaFileList`,
+			CommandDeps: []string{"$aaptCmd"},
 			Description: "aapt create R.java $out",
 		},
 		"aaptFlags", "publicResourcesFile", "proguardOptionsFile", "javaDir", "javaFileList")
@@ -41,6 +42,7 @@
 	aaptCreateAssetsPackage = pctx.StaticRule("aaptCreateAssetsPackage",
 		blueprint.RuleParams{
 			Command:     `rm -f $out && $aaptCmd package $aaptFlags -F $out`,
+			CommandDeps: []string{"$aaptCmd"},
 			Description: "aapt export package $out",
 		},
 		"aaptFlags", "publicResourcesFile", "proguardOptionsFile", "javaDir", "javaFileList")
@@ -49,6 +51,7 @@
 		blueprint.RuleParams{
 			// TODO: add-jni-shared-libs-to-package
 			Command:     `cp -f $in $out.tmp && $aaptCmd package -u $aaptFlags -F $out.tmp && mv $out.tmp $out`,
+			CommandDeps: []string{"$aaptCmd"},
 			Description: "aapt package $out",
 		},
 		"aaptFlags")
@@ -56,6 +59,7 @@
 	zipalign = pctx.StaticRule("zipalign",
 		blueprint.RuleParams{
 			Command:     `$zipalignCmd -f $zipalignFlags 4 $in $out`,
+			CommandDeps: []string{"$zipalignCmd"},
 			Description: "zipalign $out",
 		},
 		"zipalignFlags")
@@ -63,6 +67,7 @@
 	signapk = pctx.StaticRule("signapk",
 		blueprint.RuleParams{
 			Command:     `java -jar $signapkCmd $certificates $in $out`,
+			CommandDeps: []string{"$signapkCmd"},
 			Description: "signapk $out",
 		},
 		"certificates")
@@ -71,6 +76,7 @@
 		blueprint.RuleParams{
 			Command: "java -classpath $androidManifestMergerCmd com.android.manifmerger.Main merge " +
 				"--main $in --libs $libsManifests --out $out",
+			CommandDeps: []string{"$androidManifestMergerCmd"},
 			Description: "merge manifest files $out",
 		},
 		"libsManifests")
@@ -96,8 +102,6 @@
 	publicResourcesFile := filepath.Join(common.ModuleOutDir(ctx), "public_resources.xml")
 	proguardOptionsFile := filepath.Join(common.ModuleOutDir(ctx), "proguard.options")
 
-	deps = append([]string{"$aaptCmd"}, deps...)
-
 	ctx.Build(pctx, blueprint.BuildParams{
 		Rule:      aaptCreateResourceJavaFile,
 		Outputs:   []string{publicResourcesFile, proguardOptionsFile, javaFileList},
@@ -117,8 +121,6 @@
 func CreateExportPackage(ctx common.AndroidModuleContext, flags []string, deps []string) string {
 	outputFile := filepath.Join(common.ModuleOutDir(ctx), "package-export.apk")
 
-	deps = append([]string{"$aaptCmd"}, deps...)
-
 	ctx.Build(pctx, blueprint.BuildParams{
 		Rule:      aaptCreateAssetsPackage,
 		Outputs:   []string{outputFile},
@@ -137,10 +139,9 @@
 	resourceApk := filepath.Join(common.ModuleOutDir(ctx), "resources.apk")
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      aaptAddResources,
-		Outputs:   []string{resourceApk},
-		Inputs:    []string{jarFile},
-		Implicits: []string{"$aaptCmd"},
+		Rule:    aaptAddResources,
+		Outputs: []string{resourceApk},
+		Inputs:  []string{jarFile},
 		Args: map[string]string{
 			"aaptFlags": strings.Join(flags, " "),
 		},
@@ -154,10 +155,9 @@
 	}
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      signapk,
-		Outputs:   []string{signedApk},
-		Inputs:    []string{resourceApk},
-		Implicits: []string{"$signapkCmd"},
+		Rule:    signapk,
+		Outputs: []string{signedApk},
+		Inputs:  []string{resourceApk},
 		Args: map[string]string{
 			"certificates": strings.Join(certificateArgs, " "),
 		},
@@ -166,10 +166,9 @@
 	outputFile := filepath.Join(common.ModuleOutDir(ctx), "package.apk")
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      zipalign,
-		Outputs:   []string{outputFile},
-		Inputs:    []string{signedApk},
-		Implicits: []string{"$zipalignCmd"},
+		Rule:    zipalign,
+		Outputs: []string{outputFile},
+		Inputs:  []string{signedApk},
 		Args: map[string]string{
 			"zipalignFlags": "",
 		},
diff --git a/java/builder.go b/java/builder.go
index 4eda6adf..36506ae 100644
--- a/java/builder.go
+++ b/java/builder.go
@@ -52,6 +52,7 @@
 	jar = pctx.StaticRule("jar",
 		blueprint.RuleParams{
 			Command:     `$jarCmd -o $out $jarArgs`,
+			CommandDeps: []string{"$jarCmd"},
 			Description: "jar $out",
 		},
 		"jarCmd", "jarArgs")
@@ -61,6 +62,7 @@
 			Command: `rm -rf "$outDir" && mkdir -p "$outDir" && ` +
 				`$dxCmd --dex --output=$outDir $dxFlags $in || ( rm -rf "$outDir"; exit 41 ) && ` +
 				`find "$outDir" -name "classes*.dex" > $out`,
+			CommandDeps: []string{"$dxCmd"},
 			Description: "dex $out",
 		},
 		"outDir", "dxFlags")
@@ -68,6 +70,7 @@
 	jarjar = pctx.StaticRule("jarjar",
 		blueprint.RuleParams{
 			Command:     "java -jar $jarjarCmd process $rulesFile $in $out",
+			CommandDeps: []string{"$jarjarCmd", "$rulesFile"},
 			Description: "jarjar $out",
 		},
 		"rulesFile")
@@ -156,8 +159,6 @@
 		jarArgs = append(jarArgs, "-m "+manifest)
 	}
 
-	deps = append(deps, "$jarCmd")
-
 	ctx.Build(pctx, blueprint.BuildParams{
 		Rule:      jar,
 		Outputs:   []string{outputFile},
@@ -177,10 +178,9 @@
 	outputFile := filepath.Join(common.ModuleOutDir(ctx), "dex.filelist")
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      dx,
-		Outputs:   []string{outputFile},
-		Inputs:    []string{classesJar},
-		Implicits: []string{"$dxCmd"},
+		Rule:    dx,
+		Outputs: []string{outputFile},
+		Inputs:  []string{classesJar},
 		Args: map[string]string{
 			"dxFlags": flags.dxFlags,
 			"outDir":  outDir,
@@ -205,8 +205,6 @@
 	deps = append(deps, dexJarSpec.fileList)
 	jarArgs = append(jarArgs, dexJarSpec.soongJarArgs())
 
-	deps = append(deps, "$jarCmd")
-
 	ctx.Build(pctx, blueprint.BuildParams{
 		Rule:      jar,
 		Outputs:   []string{outputFile},
@@ -222,10 +220,9 @@
 func TransformJarJar(ctx common.AndroidModuleContext, classesJar string, rulesFile string) string {
 	outputFile := filepath.Join(common.ModuleOutDir(ctx), "classes-jarjar.jar")
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      jarjar,
-		Outputs:   []string{outputFile},
-		Inputs:    []string{classesJar},
-		Implicits: []string{"$jarjarCmd"},
+		Rule:    jarjar,
+		Outputs: []string{outputFile},
+		Inputs:  []string{classesJar},
 		Args: map[string]string{
 			"rulesFile": rulesFile,
 		},
diff --git a/java/gen.go b/java/gen.go
index 6e8313a..f989875 100644
--- a/java/gen.go
+++ b/java/gen.go
@@ -44,6 +44,7 @@
 	aidl = pctx.StaticRule("aidl",
 		blueprint.RuleParams{
 			Command:     "$aidlCmd -d$depFile $aidlFlags $in $out",
+			CommandDeps: []string{"$aidlCmd"},
 			Description: "aidl $out",
 		},
 		"depFile", "aidlFlags")
@@ -51,12 +52,14 @@
 	logtags = pctx.StaticRule("logtags",
 		blueprint.RuleParams{
 			Command:     "$logtagsCmd -o $out $in $allLogtagsFile",
+			CommandDeps: []string{"$logtagsCmd"},
 			Description: "logtags $out",
 		})
 
 	mergeLogtags = pctx.StaticRule("mergeLogtags",
 		blueprint.RuleParams{
 			Command:     "$mergeLogtagsCmd -o $out $in",
+			CommandDeps: []string{"$mergeLogtagsCmd"},
 			Description: "merge logtags $out",
 		})
 )
@@ -68,10 +71,9 @@
 	depFile := javaFile + ".d"
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      aidl,
-		Outputs:   []string{javaFile},
-		Inputs:    []string{aidlFile},
-		Implicits: []string{"$aidlCmd"},
+		Rule:    aidl,
+		Outputs: []string{javaFile},
+		Inputs:  []string{aidlFile},
 		Args: map[string]string{
 			"depFile":   depFile,
 			"aidlFlags": aidlFlags,
@@ -87,10 +89,9 @@
 	javaFile = pathtools.ReplaceExtension(javaFile, "java")
 
 	ctx.Build(pctx, blueprint.BuildParams{
-		Rule:      logtags,
-		Outputs:   []string{javaFile},
-		Inputs:    []string{logtagsFile},
-		Implicits: []string{"$logtagsCmd"},
+		Rule:    logtags,
+		Outputs: []string{javaFile},
+		Inputs:  []string{logtagsFile},
 	})
 
 	return javaFile