diff --git a/core/main.mk b/core/main.mk
index 85f9117..cbac2a8 100644
--- a/core/main.mk
+++ b/core/main.mk
@@ -106,11 +106,6 @@
 include build/core/ninja.mk
 else # KATI
 
-# With these files findleaves.py won't be unnecessarily slower even if
-# there is a user creates a copy of $(OUT_DIR).
-$(shell echo '# This file prevents findleaves.py from traversing this directory further' > $(OUT_DIR)/Android.mk)
-$(shell echo '# This file prevents findleaves.py from traversing this directory further' > $(OUT_DIR)/CleanSpec.mk)
-
 # Write the build number to a file so it can be read back in
 # without changing the command line every time.  Avoids rebuilds
 # when using ninja.
diff --git a/core/ninja.mk b/core/ninja.mk
index 3013a5f..f5d9c89 100644
--- a/core/ninja.mk
+++ b/core/ninja.mk
@@ -142,11 +142,18 @@
 	@echo Starting build with ninja
 	+$(hide) export NINJA_STATUS="$(NINJA_STATUS)" && source $(KATI_ENV_SH) && $(NINJA_MAKEPARALLEL) $(NINJA) -d keepdepfile $(NINJA_GOALS) -C $(TOP) -f $(COMBINED_BUILD_NINJA) $(NINJA_ARGS)
 
+# Dummy Android.mk and CleanSpec.mk files so that kati won't recurse into the
+# out directory
+DUMMY_OUT_MKS := $(OUT_DIR)/Android.mk $(OUT_DIR)/CleanSpec.mk
+$(DUMMY_OUT_MKS):
+	@mkdir -p $(dir $@)
+	$(hide) echo '# This file prevents findleaves.py from traversing this directory further' >$@
+
 KATI_FIND_EMULATOR := --use_find_emulator
 ifeq ($(KATI_EMULATE_FIND),false)
   KATI_FIND_EMULATOR :=
 endif
-$(KATI_BUILD_NINJA): $(CKATI) $(MAKEPARALLEL) run_soong FORCE
+$(KATI_BUILD_NINJA): $(CKATI) $(MAKEPARALLEL) $(DUMMY_OUT_MKS) run_soong FORCE
 	@echo Running kati to generate build$(KATI_NINJA_SUFFIX).ninja...
 	+$(hide) $(KATI_MAKEPARALLEL) $(CKATI) --ninja --ninja_dir=$(OUT_DIR) --ninja_suffix=$(KATI_NINJA_SUFFIX) --regen --ignore_dirty=$(OUT_DIR)/% --no_ignore_dirty=$(SOONG_ANDROID_MK) --ignore_optional_include=$(OUT_DIR)/%.P --detect_android_echo $(KATI_FIND_EMULATOR) -f build/core/main.mk $(KATI_GOALS) --gen_all_targets BUILDING_WITH_NINJA=true SOONG_ANDROID_MK=$(SOONG_ANDROID_MK)
 
diff --git a/core/soong.mk b/core/soong.mk
index 4893add..659a1ab 100644
--- a/core/soong.mk
+++ b/core/soong.mk
@@ -1,23 +1,9 @@
 SOONG_OUT_DIR := $(OUT_DIR)/soong
-
-# This needs to exist before the realpath checks below
-$(shell mkdir -p $(SOONG_OUT_DIR))
-
-ifeq (,$(filter /%,$(SOONG_OUT_DIR)))
-SOONG_TOP_RELPATH := $(shell python -c "import os; print os.path.relpath('$(TOP)', '$(SOONG_OUT_DIR)')")
-# Protect against out being a symlink and relative paths not working
-ifneq ($(realpath $(SOONG_OUT_DIR)/$(SOONG_TOP_RELPATH)),$(realpath $(TOP)))
-SOONG_OUT_DIR := $(abspath $(SOONG_OUT_DIR))
-SOONG_TOP_RELPATH := $(abspath $(TOP))
-endif
-else
-SOONG_TOP_RELPATH := $(abspath $(TOP))
-endif
-
 SOONG := $(SOONG_OUT_DIR)/soong
+SOONG_BOOTSTRAP := $(SOONG_OUT_DIR)/.soong.bootstrap
 SOONG_BUILD_NINJA := $(SOONG_OUT_DIR)/build.ninja
-SOONG_VARIABLES := $(SOONG_OUT_DIR)/soong.variables
 SOONG_IN_MAKE := $(SOONG_OUT_DIR)/.soong.in_make
+SOONG_VARIABLES := $(SOONG_OUT_DIR)/soong.variables
 
 # Only include the Soong-generated Android.mk if we're merging the
 # Soong-defined binaries with Kati-defined binaries.
@@ -25,10 +11,24 @@
 SOONG_ANDROID_MK := $(SOONG_OUT_DIR)/Android.mk
 endif
 
-# Bootstrap soong.  Run only the first time for clean builds
-$(SOONG):
+# We need to rebootstrap soong if SOONG_OUT_DIR or the reverse path from
+# SOONG_OUT_DIR to TOP changes
+SOONG_NEEDS_REBOOTSTRAP :=
+ifneq ($(wildcard $(SOONG_BOOTSTRAP)),)
+  ifneq ($(SOONG_OUT_DIR),$(strip $(shell source $(SOONG_BOOTSTRAP); echo $$BUILDDIR)))
+    SOONG_NEEDS_REBOOTSTRAP := FORCE
+    $(warning soong_out_dir changed)
+  endif
+  ifneq ($(strip $(shell build/soong/reverse_path.py $(SOONG_OUT_DIR))),$(strip $(shell source $(SOONG_BOOTSTRAP); echo $$SRCDIR_FROM_BUILDDIR)))
+    SOONG_NEEDS_REBOOTSTRAP := FORCE
+    $(warning reverse path changed)
+  endif
+endif
+
+# Bootstrap soong.
+$(SOONG_BOOTSTRAP): bootstrap.bash $(SOONG_NEEDS_REBOOTSTRAP)
 	$(hide) mkdir -p $(dir $@)
-	$(hide) cd $(dir $@) && $(SOONG_TOP_RELPATH)/bootstrap.bash
+	$(hide) BUILDDIR=$(SOONG_OUT_DIR) ./bootstrap.bash
 
 # Create soong.variables with copies of makefile settings.  Runs every build,
 # but only updates soong.variables if it changes
@@ -76,5 +76,5 @@
 # Run Soong, this implicitly create an Android.mk listing all soong outputs as
 # prebuilts.
 .PHONY: run_soong
-run_soong: $(SOONG) $(SOONG_VARIABLES) $(SOONG_IN_MAKE) FORCE
+run_soong: $(SOONG_BOOTSTRAP) $(SOONG_VARIABLES) $(SOONG_IN_MAKE) FORCE
 	$(hide) $(SOONG) $(SOONG_BUILD_NINJA) $(NINJA_ARGS)