--- a/python/mozbuild/mozbuild/controller/building.py
+++ b/python/mozbuild/mozbuild/controller/building.py
@@ -988,16 +988,29 @@ class BuildDriver(MozbuildObject):
                         if e.errno == errno.ENOENT:
                             return True
                         raise
                     if dep_mtime > mtime:
                         return True
                 return False
 
             def backend_out_of_date(backend_file):
+                if not os.path.isfile(backend_file):
+                    return True
+
+                # Check if any of our output files have been removed since
+                # we last built the backend, re-generate the backend if
+                # so.
+                outputs = []
+                with open(backend_file, 'r') as fh:
+                    outputs = fh.read().splitlines()
+                for output in outputs:
+                    if not os.path.isfile(mozpath.join(self.topobjdir, output)):
+                        return True
+
                 dep_file = '%s.in' % backend_file
                 return build_out_of_date(backend_file, dep_file)
 
             def maybe_invoke_backend(active_backend):
                 # Attempt to bypass the make-oriented logic below. Note this
                 # will only succeed in case we're building with a non-make
                 # backend (Tup), and otherwise be harmless.
                 if active_backend: