diff --git a/android/bazel_handler.go b/android/bazel_handler.go
index 33b67ab..8cd2363 100644
--- a/android/bazel_handler.go
+++ b/android/bazel_handler.go
@@ -21,6 +21,7 @@
 	"io/ioutil"
 	"os"
 	"os/exec"
+	"path"
 	"path/filepath"
 	"runtime"
 	"strings"
@@ -870,53 +871,14 @@
 		})
 	}
 
-	// Register bazel-owned build statements (obtained from the aquery invocation).
+	executionRoot := path.Join(ctx.Config().BazelContext.OutputBase(), "execroot", "__main__")
+	bazelOutDir := path.Join(executionRoot, "bazel-out")
 	for index, buildStatement := range ctx.Config().BazelContext.BuildStatementsToRegister() {
 		if len(buildStatement.Command) < 1 {
 			panic(fmt.Sprintf("unhandled build statement: %v", buildStatement))
 		}
 		rule := NewRuleBuilder(pctx, ctx)
-		cmd := rule.Command()
-
-		// cd into Bazel's execution root, which is the action cwd.
-		cmd.Text(fmt.Sprintf("cd %s/execroot/__main__ &&", ctx.Config().BazelContext.OutputBase()))
-
-		// Remove old outputs, as some actions might not rerun if the outputs are detected.
-		if len(buildStatement.OutputPaths) > 0 {
-			cmd.Text("rm -f")
-			for _, outputPath := range buildStatement.OutputPaths {
-				cmd.Text(outputPath)
-			}
-			cmd.Text("&&")
-		}
-
-		for _, pair := range buildStatement.Env {
-			// Set per-action env variables, if any.
-			cmd.Flag(pair.Key + "=" + pair.Value)
-		}
-
-		// The actual Bazel action.
-		cmd.Text(buildStatement.Command)
-
-		for _, outputPath := range buildStatement.OutputPaths {
-			cmd.ImplicitOutput(PathForBazelOut(ctx, outputPath))
-		}
-		for _, inputPath := range buildStatement.InputPaths {
-			cmd.Implicit(PathForBazelOut(ctx, inputPath))
-		}
-		for _, inputDepsetHash := range buildStatement.InputDepsetHashes {
-			otherDepsetName := bazelDepsetName(inputDepsetHash)
-			cmd.Implicit(PathForPhony(ctx, otherDepsetName))
-		}
-
-		if depfile := buildStatement.Depfile; depfile != nil {
-			cmd.ImplicitDepFile(PathForBazelOut(ctx, *depfile))
-		}
-
-		for _, symlinkPath := range buildStatement.SymlinkPaths {
-			cmd.ImplicitSymlinkOutput(PathForBazelOut(ctx, symlinkPath))
-		}
-
+		createCommand(rule.Command(), buildStatement, executionRoot, bazelOutDir, ctx)
 		// This is required to silence warnings pertaining to unexpected timestamps. Particularly,
 		// some Bazel builtins (such as files in the bazel_tools directory) have far-future
 		// timestamps. Without restat, Ninja would emit warnings that the input files of a
@@ -928,6 +890,58 @@
 	}
 }
 
+// Register bazel-owned build statements (obtained from the aquery invocation).
+func createCommand(cmd *RuleBuilderCommand, buildStatement bazel.BuildStatement, executionRoot string, bazelOutDir string, ctx PathContext) {
+	// executionRoot is the action cwd.
+	cmd.Text(fmt.Sprintf("cd '%s' &&", executionRoot))
+
+	// Remove old outputs, as some actions might not rerun if the outputs are detected.
+	if len(buildStatement.OutputPaths) > 0 {
+		cmd.Text("rm -f")
+		for _, outputPath := range buildStatement.OutputPaths {
+			cmd.Text(outputPath)
+		}
+		cmd.Text("&&")
+	}
+
+	for _, pair := range buildStatement.Env {
+		// Set per-action env variables, if any.
+		cmd.Flag(pair.Key + "=" + pair.Value)
+	}
+
+	// The actual Bazel action.
+	cmd.Text(buildStatement.Command)
+
+	for _, outputPath := range buildStatement.OutputPaths {
+		cmd.ImplicitOutput(PathForBazelOut(ctx, outputPath))
+	}
+	for _, inputPath := range buildStatement.InputPaths {
+		cmd.Implicit(PathForBazelOut(ctx, inputPath))
+	}
+	for _, inputDepsetHash := range buildStatement.InputDepsetHashes {
+		otherDepsetName := bazelDepsetName(inputDepsetHash)
+		cmd.Implicit(PathForPhony(ctx, otherDepsetName))
+	}
+
+	if depfile := buildStatement.Depfile; depfile != nil {
+		// The paths in depfile are relative to `executionRoot`.
+		// Hence, they need to be corrected by replacing "bazel-out"
+		// with the full `bazelOutDir`.
+		// Otherwise, implicit outputs and implicit inputs under "bazel-out/"
+		// would be deemed missing.
+		// (Note: The regexp uses a capture group because the version of sed
+		//  does not support a look-behind pattern.)
+		replacement := fmt.Sprintf(`&& sed -i'' -E 's@(^|\s|")bazel-out/@\1%s/@g' '%s'`,
+			bazelOutDir, *depfile)
+		cmd.Text(replacement)
+		cmd.ImplicitDepFile(PathForBazelOut(ctx, *depfile))
+	}
+
+	for _, symlinkPath := range buildStatement.SymlinkPaths {
+		cmd.ImplicitSymlinkOutput(PathForBazelOut(ctx, symlinkPath))
+	}
+}
+
 func getCqueryId(key cqueryKey) string {
 	return key.label + "|" + getConfigString(key)
 }
diff --git a/android/bazel_handler_test.go b/android/bazel_handler_test.go
index dd9a7ed..935ce4e 100644
--- a/android/bazel_handler_test.go
+++ b/android/bazel_handler_test.go
@@ -57,8 +57,13 @@
 }
 
 func TestInvokeBazelPopulatesBuildStatements(t *testing.T) {
-	bazelContext, _ := testBazelContext(t, map[bazelCommand]string{
-		bazelCommand{command: "aquery", expression: "deps(@soong_injection//mixed_builds:buildroot)"}: `
+	type testCase struct {
+		input   string
+		command string
+	}
+
+	var testCases = []testCase{
+		{`
 {
   "artifacts": [{
     "id": 1,
@@ -88,15 +93,60 @@
     "label": "two"
   }]
 }`,
-	})
-	err := bazelContext.InvokeBazel(testConfig)
-	if err != nil {
-		t.Fatalf("Did not expect error invoking Bazel, but got %s", err)
+			"cd 'er' && rm -f one && touch foo",
+		}, {`
+{
+  "artifacts": [{
+    "id": 1,
+    "pathFragmentId": 10
+  }, {
+    "id": 2,
+    "pathFragmentId": 20
+  }],
+  "actions": [{
+    "targetId": 100,
+    "actionKey": "x",
+    "mnemonic": "x",
+    "arguments": ["bogus", "command"],
+    "outputIds": [1, 2],
+    "primaryOutputId": 1
+  }],
+  "pathFragments": [{
+    "id": 10,
+    "label": "one",
+    "parentId": 30
+  }, {
+    "id": 20,
+    "label": "one.d",
+    "parentId": 30
+  }, {
+    "id": 30,
+    "label": "parent"
+  }]
+}`,
+			`cd 'er' && rm -f parent/one && bogus command && sed -i'' -E 's@(^|\s|")bazel-out/@\1bo/@g' 'parent/one.d'`,
+		},
 	}
 
-	got := bazelContext.BuildStatementsToRegister()
-	if want := 1; len(got) != want {
-		t.Errorf("Expected %d registered build statements, got %#v", want, got)
+	for _, testCase := range testCases {
+		bazelContext, _ := testBazelContext(t, map[bazelCommand]string{
+			bazelCommand{command: "aquery", expression: "deps(@soong_injection//mixed_builds:buildroot)"}: testCase.input})
+
+		err := bazelContext.InvokeBazel(testConfig)
+		if err != nil {
+			t.Fatalf("Did not expect error invoking Bazel, but got %s", err)
+		}
+
+		got := bazelContext.BuildStatementsToRegister()
+		if want := 1; len(got) != want {
+			t.Errorf("expected %d registered build statements, but got %#v", want, got)
+		}
+
+		cmd := RuleBuilderCommand{}
+		createCommand(&cmd, got[0], "er", "bo", PathContextForTesting(TestConfig("out", nil, "", nil)))
+		if actual := cmd.buf.String(); testCase.command != actual {
+			t.Errorf("expected: [%s], actual: [%s]", testCase.command, actual)
+		}
 	}
 }