--- a/Makefile.in
+++ b/Makefile.in
@@ -27,19 +27,19 @@ include $(topsrcdir)/config/config.mk
 GARBAGE_DIRS += dist _javagen _profile staticlib
 DIST_GARBAGE = config.cache config.log config.status* config-defs.h \
    config/autoconf.mk \
    mozilla-config.h \
    netwerk/necko-config.h xpcom/xpcom-config.h xpcom/xpcom-private.h \
    .mozconfig.mk
 
 ifndef MOZ_PROFILE_USE
-# We need to explicitly put backend.RecursiveMakeBackend.built here
+# We need to explicitly put backend.RecursiveMakeBackend here
 # otherwise the rule in rules.mk doesn't run early enough.
-libs binaries export tools:: CLOBBER $(topsrcdir)/configure config.status backend.RecursiveMakeBackend.built
+libs binaries export tools:: CLOBBER $(topsrcdir)/configure config.status backend.RecursiveMakeBackend
 ifndef LIBXUL_SDK
 libs binaries export tools:: js-config-status
 endif
 endif
 
 CLOBBER: $(topsrcdir)/CLOBBER
 	@echo "STOP!  The CLOBBER file has changed."
 	@echo "Please run the build through a sanctioned build wrapper, such as"
@@ -58,25 +58,25 @@ config.status: $(topsrcdir)/configure
 	@echo "Please rerun configure."
 	@echo "To ignore this message, touch 'config.status' in the build directory,"
 	@echo "but your build might not succeed."
 	@exit 1
 
 ifndef LIBXUL_SDK
 .PHONY: js-config-status
 js-config-status:
-	$(call SUBMAKE,backend.RecursiveMakeBackend.built,js/src,1)
+	$(call SUBMAKE,backend.RecursiveMakeBackend,js/src,1)
 endif
 
 install_manifests := bin idl include public private sdk
 install_manifest_depends = \
   CLOBBER \
   $(topsrcdir)/configure \
   config.status \
-  backend.RecursiveMakeBackend.built \
+  backend.RecursiveMakeBackend \
   $(NULL)
 
 ifndef LIBXUL_SDK
 install_manifest_depends += js-config-status
 endif
 
 .PHONY: install-manifests
 install-manifests: $(addprefix install-dist-,$(install_manifests))

--- a/config/rules.mk
+++ b/config/rules.mk
@@ -597,27 +597,27 @@ ifndef MOZBUILD_BACKEND_CHECKED
 
 # Since Makefile is listed as a global dependency, this has the
 # unfortunate side-effect of invalidating all targets if it is executed.
 # So e.g. if you are in /dom/bindings and /foo/moz.build changes,
 # /dom/bindings will get invalidated. The upside is if the current
 # Makefile/backend.mk is updated as a result of backend regeneration, we
 # actually pick up the changes. This should reduce the amount of
 # required clobbers and is thus the lesser evil.
-Makefile: $(DEPTH)/backend.RecursiveMakeBackend.built
+Makefile: $(DEPTH)/backend.RecursiveMakeBackend
 	@$(TOUCH) $@
 
-$(DEPTH)/backend.RecursiveMakeBackend.built:
+$(DEPTH)/backend.RecursiveMakeBackend:
 	@echo "Build configuration changed. Regenerating backend."
 	@cd $(DEPTH) && $(PYTHON) ./config.status
 	@$(TOUCH) $@
 
-include $(DEPTH)/backend.RecursiveMakeBackend.built.pp
+include $(DEPTH)/backend.RecursiveMakeBackend.pp
 
-default:: $(DEPTH)/backend.RecursiveMakeBackend.built
+default:: $(DEPTH)/backend.RecursiveMakeBackend
 
 export MOZBUILD_BACKEND_CHECKED=1
 endif
 
 # The root makefile doesn't want to do a plain export/libs, because
 # of the tiers and because of libxul. Suppress the default rules in favor
 # of something else. Makefiles which use this var *must* provide a sensible
 # default rule before including rules.mk

--- a/dom/bindings/Makefile.in
+++ b/dom/bindings/Makefile.in
@@ -245,17 +245,16 @@ ParserResults.pkl: $(globalgen_dependenc
 	  .changed-dependency-list
 	@$(TOUCH) $@
 
 GARBAGE += \
   webidlyacc.py \
   parser.out \
   $(wildcard *-example.h) \
   $(wildcard *-example.cpp) \
-  $(unified_binding_cpp_files) \
   .BindingGen \
   .all-webidl-file-list \
   .generated-events-webidl-files \
   .changed-dependency-list \
   $(binding_dependency_trackers) \
   $(NULL)
 
 # Make sure all binding header files are created during the export stage, so we

--- a/ipc/ipdl/Makefile.in
+++ b/ipc/ipdl/Makefile.in
@@ -3,18 +3,16 @@
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 GARBAGE_DIRS += _ipdlheaders
 GARBAGE += ipdl_lextab.py ipdl_yacctab.py $(wildcard *.pyc $(srcdir)/ipdl/*.pyc $(srcdir)/ipdl/cxx/*.pyc)
 
 # This file is generated by the moz.build backend.
 include ipdlsrcs.mk
 
-GARBAGE += $(CPPSRCS)
-
 LOCAL_INCLUDES += -I$(DEPTH)/ipc/ipdl/_ipdlheaders
 
 
 include $(topsrcdir)/config/rules.mk
 
 
 # NB: the IPDL compiler manages .ipdl-->.h/.cpp dependencies itself,
 # which is why we don't have explicit .h/.cpp targets here

--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -364,17 +364,17 @@ ifndef HAVE_DTRACE
 endif
 endif
 
 DIST_GARBAGE = config.cache config.log config.status* \
    config/autoconf.mk config/emptyvars.mk \
    $(JS_CONFIG_NAME) js-config.h js-confdefs.h \
    backend.mk config/backend.mk devtools/backend.mk editline/backend.mk \
    gdb/backend.mk jsapi-tests/backend.mk shell/backend.mk tests/backend.mk \
-   backend.RecursiveMakeBackend.built backend.RecursiveMakeBackend.built.pp \
+   backend.RecursiveMakeBackend backend.RecursiveMakeBackend.pp \
    devtools/rootAnalysis/Makefile
 
 distclean::
 	$(RM) $(DIST_GARBAGE)
 
 DEFINES		+= -DEXPORT_JS_API
 
 INCLUDES	+= -I$(srcdir)

--- a/js/src/config/rules.mk
+++ b/js/src/config/rules.mk
@@ -597,27 +597,27 @@ ifndef MOZBUILD_BACKEND_CHECKED
 
 # Since Makefile is listed as a global dependency, this has the
 # unfortunate side-effect of invalidating all targets if it is executed.
 # So e.g. if you are in /dom/bindings and /foo/moz.build changes,
 # /dom/bindings will get invalidated. The upside is if the current
 # Makefile/backend.mk is updated as a result of backend regeneration, we
 # actually pick up the changes. This should reduce the amount of
 # required clobbers and is thus the lesser evil.
-Makefile: $(DEPTH)/backend.RecursiveMakeBackend.built
+Makefile: $(DEPTH)/backend.RecursiveMakeBackend
 	@$(TOUCH) $@
 
-$(DEPTH)/backend.RecursiveMakeBackend.built:
+$(DEPTH)/backend.RecursiveMakeBackend:
 	@echo "Build configuration changed. Regenerating backend."
 	@cd $(DEPTH) && $(PYTHON) ./config.status
 	@$(TOUCH) $@
 
-include $(DEPTH)/backend.RecursiveMakeBackend.built.pp
+include $(DEPTH)/backend.RecursiveMakeBackend.pp
 
-default:: $(DEPTH)/backend.RecursiveMakeBackend.built
+default:: $(DEPTH)/backend.RecursiveMakeBackend
 
 export MOZBUILD_BACKEND_CHECKED=1
 endif
 
 # The root makefile doesn't want to do a plain export/libs, because
 # of the tiers and because of libxul. Suppress the default rules in favor
 # of something else. Makefiles which use this var *must* provide a sensible
 # default rule before including rules.mk

--- a/python/mozbuild/mozbuild/backend/base.py
+++ b/python/mozbuild/mozbuild/backend/base.py
@@ -43,16 +43,19 @@ class BackendConsumeSummary(object):
         self.created_count = 0
 
         # The number of backend files updated.
         self.updated_count = 0
 
         # The number of unchanged backend files.
         self.unchanged_count = 0
 
+        # The number of deleted backend files.
+        self.deleted_count = 0
+
         # The total wall time this backend spent consuming objects. If
         # the iterable passed into consume() is a generator, this includes the
         # time spent to read moz.build files.
         self.wall_time = 0.0
 
         # CPU time spent by during the interval captured by wall_time.
         self.cpu_time = 0.0
 
@@ -116,16 +119,27 @@ class BuildBackend(LoggingMixin):
 
         self.environment = environment
         self.summary = BackendConsumeSummary()
 
         # Files whose modification should cause a new read and backend
         # generation.
         self.backend_input_files = set()
 
+        # Files generated by the backend.
+        self._backend_output_files = set()
+
+        # Previously generated files.
+        self._backend_output_list_file = os.path.join(environment.topobjdir,
+            'backend.%s' % self.__class__.__name__)
+        self._backend_output_list = set()
+        if os.path.exists(self._backend_output_list_file):
+            self._backend_output_list.update(open(self._backend_output_list_file) \
+                                               .read().split('\n'))
+
         # Pull in Python files for this package as dependencies so backend
         # regeneration occurs if any of the code affecting it changes.
         for name, module in sys.modules.items():
             if not module or not name.startswith('mozbuild'):
                 continue
 
             p = module.__file__
 
@@ -194,28 +208,44 @@ class BuildBackend(LoggingMixin):
 
             if isinstance(obj, SandboxDerived):
                 self.backend_input_files |= obj.sandbox_all_paths
 
             if isinstance(obj, ReaderSummary):
                 self.summary.mozbuild_count = obj.total_file_count
                 self.summary.mozbuild_execution_time = obj.total_execution_time
 
-        # Write out a file indicating when this backend was last generated.
-        age_file = os.path.join(self.environment.topobjdir,
-            'backend.%s.built' % self.__class__.__name__)
-        if self.summary.updated_count or self.summary.created_count or \
-                not os.path.exists(age_file):
-            with open(age_file, 'a'):
-                os.utime(age_file, None)
-
         finished_start = time.time()
         self.consume_finished()
         backend_time += time.time() - finished_start
 
+        # Purge backend files created in previous run, but not created anymore
+        delete_files = self._backend_output_list - self._backend_output_files
+        for path in delete_files:
+            try:
+                os.unlink(os.path.join(self.environment.topobjdir, path))
+                self.summary.deleted_count += 1
+            except OSError:
+                pass
+        # Remove now empty directories
+        for dir in set(os.path.dirname(d) for d in delete_files):
+            try:
+                os.removedirs(dir)
+            except OSError:
+                pass
+
+        # Write out the list of backend files generated, if it changed.
+        if self.summary.deleted_count or self.summary.created_count or \
+                not os.path.exists(self._backend_output_list_file):
+            with open(self._backend_output_list_file, 'w') as fh:
+                fh.write('\n'.join(sorted(self._backend_output_files)))
+        elif self.summary.updated_count:
+            with open(self._backend_output_list_file, 'a'):
+                os.utime(self._backend_output_list_file, None)
+
         self.summary.cpu_time = time.clock() - cpu_start
         self.summary.wall_time = time.time() - time_start
         self.summary.backend_execution_time = backend_time
         self.summary.other_time = self.summary.wall_time - \
             self.summary.mozbuild_execution_time - \
             self.summary.backend_execution_time
 
         return self.summary
@@ -254,15 +284,16 @@ class BuildBackend(LoggingMixin):
         try:
             os.makedirs(dirname)
         except OSError as error:
             if error.errno != errno.EEXIST:
                 raise
 
         yield fh
 
+        self._backend_output_files.add(os.path.relpath(fh.name, self.environment.topobjdir))
         existed, updated = fh.close()
         if not existed:
             self.summary.created_count += 1
         elif updated:
             self.summary.updated_count += 1
         else:
             self.summary.unchanged_count += 1

--- a/python/mozbuild/mozbuild/backend/recursivemake.py
+++ b/python/mozbuild/mozbuild/backend/recursivemake.py
@@ -263,20 +263,23 @@ class RecursiveMakeBackend(CommonBackend
         self._webidl_sources = set()
         self._generated_events_webidl_sources = set()
         self._test_webidl_sources = set()
         self._preprocessed_test_webidl_sources = set()
         self._preprocessed_webidl_sources = set()
         self._generated_webidl_sources = set()
 
         def detailed(summary):
-            return '{:d} total backend files. {:d} created; {:d} updated; {:d} unchanged'.format(
+            s = '{:d} total backend files. {:d} created; {:d} updated; {:d} unchanged'.format(
                 summary.created_count + summary.updated_count +
                 summary.unchanged_count, summary.created_count,
                 summary.updated_count, summary.unchanged_count)
+            if summary.deleted_count:
+                s+= '; {:d} deleted'.format(summary.deleted_count)
+            return s
 
         # This is a little kludgy and could be improved with a better API.
         self.summary.backend_detailed_summary = types.MethodType(detailed,
             self.summary)
 
         self._test_manifests = {}
 
         self.backend_input_files.add(os.path.join(self.environment.topobjdir,
@@ -698,26 +701,24 @@ class RecursiveMakeBackend(CommonBackend
 
         # Assume that Somebody Else has responsibility for correctly
         # specifying removal dependencies for |all_webidl_sources|.
         with self._write_file(os.path.join(bindings_dir, 'webidlsrcs.mk')) as webidls:
             mk.dump(webidls, removal_guard=False)
 
         # Write out a dependency file used to determine whether a config.status
         # re-run is needed.
-        backend_built_path = os.path.join(self.environment.topobjdir,
-            'backend.%s.built' % self.__class__.__name__).replace(os.sep, '/')
         inputs = sorted(p.replace(os.sep, '/') for p in self.backend_input_files)
 
         # We need to use $(DEPTH) so the target here matches what's in
         # rules.mk. If they are different, the dependencies don't get pulled in
         # properly.
-        with self._write_file('%s.pp' % backend_built_path) as backend_deps:
-            backend_deps.write('$(DEPTH)/backend.RecursiveMakeBackend.built: %s\n' %
-                ' '.join(inputs))
+        with self._write_file('%s.pp' % self._backend_output_list_file) as backend_deps:
+            backend_deps.write('$(DEPTH)/backend.%s: %s\n' %
+                (self.__class__.__name__, ' '.join(inputs)))
             for path in inputs:
                 backend_deps.write('%s:\n' % path)
 
         # Make the master test manifest files.
         for flavor, t in self._test_manifests.items():
             install_prefix, manifests = t
             manifest_stem = os.path.join(install_prefix, '%s.ini' % flavor)
             self._write_master_test_manifest(os.path.join(

--- a/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
+++ b/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
@@ -148,19 +148,19 @@ class TestRecursiveMakeTraversal(unittes
             'I': ('G', 'H'),
         })
 
 class TestRecursiveMakeBackend(BackendTester):
     def test_basic(self):
         """Ensure the RecursiveMakeBackend works without error."""
         env = self._consume('stub0', RecursiveMakeBackend)
         self.assertTrue(os.path.exists(os.path.join(env.topobjdir,
-            'backend.RecursiveMakeBackend.built')))
+            'backend.RecursiveMakeBackend')))
         self.assertTrue(os.path.exists(os.path.join(env.topobjdir,
-            'backend.RecursiveMakeBackend.built.pp')))
+            'backend.RecursiveMakeBackend.pp')))
 
     def test_output_files(self):
         """Ensure proper files are generated."""
         env = self._consume('stub0', RecursiveMakeBackend)
 
         expected = ['', 'dir1', 'dir2']
 
         for d in expected: