Bug 907365 - Pseudo-derecursify the build (opt-in). r=gps
authorMike Hommey <mh+mozilla@glandium.org>
Fri, 20 Sep 2013 10:44:11 +0900
changeset 161926 a3d79a54d83e967bec4c7e40e536b7b0a3dd2756
parent 161859 e1998769de9e78033786a8212efda4b21825a839
child 161927 0d19104a7002076c73555a1b860d2c1ba4bcca73
push id1
push usersledru@mozilla.com
push dateThu, 04 Dec 2014 17:57:20 +0000
reviewersgps
bugs907365, 912856
milestone27.0a1
Bug 907365 - Pseudo-derecursify the build (opt-in). r=gps Also remove the compile tier added in bug 912856 when pseudo-derecursify is disabled.
Makefile.in
build/autoconf/config.status.m4
config/recurse.mk
config/rules.mk
js/src/Makefile.in
js/src/build/autoconf/config.status.m4
js/src/config/recurse.mk
js/src/config/rules.mk
python/mozbuild/mozbuild/backend/recursivemake.py
python/mozbuild/mozbuild/test/backend/test_recursivemake.py
--- a/Makefile.in
+++ b/Makefile.in
@@ -99,17 +99,17 @@ endif
 export:: install-dist-sdk
 
 ifdef ENABLE_TESTS
 # Additional makefile targets to call automated test suites
 include $(topsrcdir)/testing/testsuite-targets.mk
 endif
 
 default all::
-	$(call BUILDSTATUS,TIERS export compile libs tools)
+	$(call BUILDSTATUS,TIERS export $(if $(MOZ_PSEUDO_DERECURSE),compile )libs tools)
 
 include $(topsrcdir)/config/rules.mk
 
 distclean::
 	$(RM) $(DIST_GARBAGE)
 
 ifeq ($(OS_ARCH),WINNT)
 # we want to copy PDB files on Windows
@@ -174,17 +174,20 @@ ifdef MOZ_CRASHREPORTER
           zip -r9D "../$(PKG_PATH)$(SYMBOL_ARCHIVE_BASENAME).zip" . -i "*.sym" -i "*.txt"  -x "*test*" -x "*Test*"
 endif # MOZ_CRASHREPORTER
 
 uploadsymbols:
 ifdef MOZ_CRASHREPORTER
 	$(SHELL) $(topsrcdir)/toolkit/crashreporter/tools/upload_symbols.sh $(SYMBOL_INDEX_NAME) "$(DIST)/$(PKG_PATH)$(SYMBOL_FULL_ARCHIVE_BASENAME).zip"
 endif
 
-# defined in package-name.mk
+# MOZ_SOURCE_STAMP is defined in package-name.mk with a deferred assignment.
+# exporting it makes make run its $(shell) command for each invoked submake,
+# so transform it to an immediate assignment.
+MOZ_SOURCE_STAMP := $(MOZ_SOURCE_STAMP)
 export MOZ_SOURCE_STAMP
 
 #XXX: this is a hack, since we don't want to clobber for MSVC
 # PGO support, but we can't do this test in client.mk
 ifneq ($(OS_ARCH)_$(GNU_CC), WINNT_)
 # No point in clobbering if PGO has been explicitly disabled.
 ifndef NO_PROFILE_GUIDED_OPTIMIZE
 maybe_clobber_profiledbuild: clean
--- a/build/autoconf/config.status.m4
+++ b/build/autoconf/config.status.m4
@@ -176,8 +176,10 @@ changequote([, ])
 chmod +x $CONFIG_STATUS
 rm -fr confdefs* $ac_clean_files
 dnl Execute config.status, unless --no-create was passed to configure.
 if test "$no_create" != yes && ! ${PYTHON} $CONFIG_STATUS; then
     trap '' EXIT
     exit 1
 fi
 ])
+
+AC_SUBST([MOZ_PSEUDO_DERECURSE])
--- a/config/recurse.mk
+++ b/config/recurse.mk
@@ -1,25 +1,116 @@
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this file,
 # You can obtain one at http://mozilla.org/MPL/2.0/.
 
 ifndef INCLUDED_RULES_MK
 include $(topsrcdir)/config/rules.mk
 endif
 
+# The traditional model of directory traversal with make is as follows:
+#   make -C foo
+#     Entering foo
+#     make -C bar
+#       Entering foo/bar
+#     make -C baz
+#       Entering foo/baz
+#   make -C qux
+#     Entering qux
+#
+# Pseudo derecurse transforms the above into:
+#   make -C foo
+#   make -C foo/bar
+#   make -C foo/baz
+#   make -C qux
+
+ifeq (1_.,$(MOZ_PSEUDO_DERECURSE)_$(DEPTH))
+
+include root.mk
+
+# Disable build status for mach in top directories without TIERS.
+# In practice this disables it when recursing under js/src, which confuses mach.
+ifndef TIERS
+BUILDSTATUS =
+endif
+
+# Main rules (export, compile, libs and tools) call recurse_* rules.
+# This wrapping is only really useful for build status.
+compile libs export tools::
+	$(call BUILDSTATUS,TIER_START $@ $($@_subtiers))
+	+$(MAKE) recurse_$@
+	$(call BUILDSTATUS,TIER_FINISH $@)
+
+# Carefully avoid $(eval) type of rule generation, which makes pymake slower
+# than necessary.
+# Get current tier and corresponding subtiers from the data in root.mk.
+CURRENT_TIER := $(filter $(foreach tier,compile libs export tools,recurse_$(tier)),$(MAKECMDGOALS))
+ifneq (,$(filter-out 0 1,$(words $(CURRENT_TIER))))
+$(error $(CURRENT_TIER) not supported on the same make command line)
+endif
+CURRENT_TIER := $(subst recurse_,,$(CURRENT_TIER))
+CURRENT_SUBTIERS := $($(CURRENT_TIER)_subtiers)
+
+# The rules here are doing directory traversal, so we don't want further
+# recursion to happen when running make -C subdir $tier. But some make files
+# further call make -C something else, and sometimes expect recursion to
+# happen in that case (see browser/metro/locales/Makefile.in for example).
+# Conveniently, every invocation of make increases MAKELEVEL, so only stop
+# recursion from happening at current MAKELEVEL + 1.
+ifdef CURRENT_TIER
+ifeq (0,$(MAKELEVEL))
+export NO_RECURSE_MAKELEVEL=1
+else
+export NO_RECURSE_MAKELEVEL=$(word $(MAKELEVEL),2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
+endif
+endif
+
+# Get all directories traversed for all subtiers in the current tier, or use
+# directly the $(*_dirs) variables available in root.mk when there is no
+# TIERS (like for js/src).
+CURRENT_DIRS := $(or $($(CURRENT_TIER)_dirs),$(foreach subtier,$(CURRENT_SUBTIERS),$($(CURRENT_TIER)_subtier_$(subtier))))
+
+# Subtier delimiter rules
+$(addprefix subtiers/,$(addsuffix _start/$(CURRENT_TIER),$(CURRENT_SUBTIERS))): subtiers/%_start/$(CURRENT_TIER):
+	$(call BUILDSTATUS,SUBTIER_START $(CURRENT_TIER) $* $(if $(BUG_915535_FIXED),$($(CURRENT_TIER)_subtier_$*)))
+
+$(addprefix subtiers/,$(addsuffix _finish/$(CURRENT_TIER),$(CURRENT_SUBTIERS))): subtiers/%_finish/$(CURRENT_TIER):
+	$(call BUILDSTATUS,SUBTIER_FINISH $(CURRENT_TIER) $*)
+
+# Recursion rule for all directories traversed for all subtiers in the
+# current tier.
+# root.mk defines subtier_of_* variables, that map a normalized subdir path to
+# a subtier name (e.g. subtier_of_memory_jemalloc = base)
+$(addsuffix /$(CURRENT_TIER),$(CURRENT_DIRS)): %/$(CURRENT_TIER):
+ifdef BUG_915535_FIXED
+	$(call BUILDSTATUS,TIERDIR_START $(CURRENT_TIER) $(subtier_of_$(subst /,_,$*)) $*)
+endif
+	+@$(MAKE) -C $* $(if $(filter $*,$(tier_$(subtier_of_$(subst /,_,$*))_staticdirs)),,$(CURRENT_TIER))
+ifdef BUG_915535_FIXED
+	$(call BUILDSTATUS,TIERDIR_FINISH $(CURRENT_TIER) $(subtier_of_$(subst /,_,$*)) $*)
+endif
+
+else
+
+# Don't recurse if MAKELEVEL is NO_RECURSE_MAKELEVEL as defined above, but
+# still recurse for externally managed make files (gyp-generated ones).
+ifeq ($(EXTERNALLY_MANAGED_MAKE_FILE)_$(NO_RECURSE_MAKELEVEL),_$(MAKELEVEL))
+
+compile libs export tools::
+
+else
 #########################
 # Tier traversal handling
 #########################
 
 ifdef TIERS
 
-compile libs export tools::
+libs export tools::
 	$(call BUILDSTATUS,TIER_START $@ $(filter-out $(if $(filter export,$@),,precompile),$(TIERS)))
-	$(foreach tier,$(TIERS), $(if $(filter-out compile_precompile libs_precompile tools_precompile,$@_$(tier)), \
+	$(foreach tier,$(TIERS), $(if $(filter-out libs_precompile tools_precompile,$@_$(tier)), \
 		$(call BUILDSTATUS,SUBTIER_START $@ $(tier) $(if $(filter libs,$@),$(tier_$(tier)_staticdirs)) $(tier_$(tier)_dirs)) \
 		$(if $(filter libs,$@),$(foreach dir, $(tier_$(tier)_staticdirs), $(call TIER_DIR_SUBMAKE,$@,$(tier),$(dir),,1))) \
 		$(foreach dir, $(tier_$(tier)_dirs), $(call TIER_DIR_SUBMAKE,$@,$(tier),$(dir),$@)) \
 		$(call BUILDSTATUS,SUBTIER_FINISH $@ $(tier))))
 	$(call BUILDSTATUS,TIER_FINISH $@)
 
 else
 
@@ -36,14 +127,18 @@ endif
 $(1):: $$(SUBMAKEFILES)
 ifdef PARALLEL_DIRS
 	+@$(MAKE) $$(PARALLEL_DIRS_$(1))
 endif
 	$$(LOOP_OVER_DIRS)
 
 endef
 
-$(foreach subtier,export compile libs tools,$(eval $(call CREATE_SUBTIER_TRAVERSAL_RULE,$(subtier))))
+$(foreach subtier,export libs tools,$(eval $(call CREATE_SUBTIER_TRAVERSAL_RULE,$(subtier))))
 
-compile export tools:: $(SUBMAKEFILES)
+tools export:: $(SUBMAKEFILES)
 	$(LOOP_OVER_TOOL_DIRS)
 
-endif
+endif # ifdef TIERS
+
+endif # ifeq ($(EXTERNALLY_MANAGED_MAKE_FILE)_$(NO_RECURSE_MAKELEVEL),_$(MAKELEVEL))
+
+endif # ifeq (1_.,$(MOZ_PSEUDO_DERECURSE)_$(DEPTH))
--- a/config/rules.mk
+++ b/config/rules.mk
@@ -690,17 +690,19 @@ SUBMAKEFILES += $(addsuffix /Makefile, $
 
 # 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
 ifndef SUPPRESS_DEFAULT_RULES
 default all::
 	$(MAKE) export
+ifdef MOZ_PSEUDO_DERECURSE
 	$(MAKE) compile
+endif
 	$(MAKE) libs
 	$(MAKE) tools
 endif # SUPPRESS_DEFAULT_RULES
 
 ifeq ($(findstring s,$(filter-out --%, $(MAKEFLAGS))),)
 ECHO := echo
 QUIET :=
 else
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -201,17 +201,17 @@ endif
 
 INSTALL_TARGETS += jsconfig
 jsconfig_FILES = $(export_files)
 jsconfig_DEST = $(DIST)/include
 jsconfig_TARGET := export
 
 .PHONY: buildffi buildicu
 buildffi buildicu:
-compile:: buildffi buildicu
+$(if $(MOZ_PSEUDO_DERECURSE),compile,export):: buildffi buildicu
 
 include $(topsrcdir)/config/rules.mk
 
 ifdef JS_HAS_CTYPES
 ifndef MOZ_NATIVE_FFI
 buildffi:
 		$(call SUBMAKE,,ctypes/libffi)
 
--- a/js/src/build/autoconf/config.status.m4
+++ b/js/src/build/autoconf/config.status.m4
@@ -176,8 +176,10 @@ changequote([, ])
 chmod +x $CONFIG_STATUS
 rm -fr confdefs* $ac_clean_files
 dnl Execute config.status, unless --no-create was passed to configure.
 if test "$no_create" != yes && ! ${PYTHON} $CONFIG_STATUS; then
     trap '' EXIT
     exit 1
 fi
 ])
+
+AC_SUBST([MOZ_PSEUDO_DERECURSE])
--- a/js/src/config/recurse.mk
+++ b/js/src/config/recurse.mk
@@ -1,25 +1,116 @@
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this file,
 # You can obtain one at http://mozilla.org/MPL/2.0/.
 
 ifndef INCLUDED_RULES_MK
 include $(topsrcdir)/config/rules.mk
 endif
 
+# The traditional model of directory traversal with make is as follows:
+#   make -C foo
+#     Entering foo
+#     make -C bar
+#       Entering foo/bar
+#     make -C baz
+#       Entering foo/baz
+#   make -C qux
+#     Entering qux
+#
+# Pseudo derecurse transforms the above into:
+#   make -C foo
+#   make -C foo/bar
+#   make -C foo/baz
+#   make -C qux
+
+ifeq (1_.,$(MOZ_PSEUDO_DERECURSE)_$(DEPTH))
+
+include root.mk
+
+# Disable build status for mach in top directories without TIERS.
+# In practice this disables it when recursing under js/src, which confuses mach.
+ifndef TIERS
+BUILDSTATUS =
+endif
+
+# Main rules (export, compile, libs and tools) call recurse_* rules.
+# This wrapping is only really useful for build status.
+compile libs export tools::
+	$(call BUILDSTATUS,TIER_START $@ $($@_subtiers))
+	+$(MAKE) recurse_$@
+	$(call BUILDSTATUS,TIER_FINISH $@)
+
+# Carefully avoid $(eval) type of rule generation, which makes pymake slower
+# than necessary.
+# Get current tier and corresponding subtiers from the data in root.mk.
+CURRENT_TIER := $(filter $(foreach tier,compile libs export tools,recurse_$(tier)),$(MAKECMDGOALS))
+ifneq (,$(filter-out 0 1,$(words $(CURRENT_TIER))))
+$(error $(CURRENT_TIER) not supported on the same make command line)
+endif
+CURRENT_TIER := $(subst recurse_,,$(CURRENT_TIER))
+CURRENT_SUBTIERS := $($(CURRENT_TIER)_subtiers)
+
+# The rules here are doing directory traversal, so we don't want further
+# recursion to happen when running make -C subdir $tier. But some make files
+# further call make -C something else, and sometimes expect recursion to
+# happen in that case (see browser/metro/locales/Makefile.in for example).
+# Conveniently, every invocation of make increases MAKELEVEL, so only stop
+# recursion from happening at current MAKELEVEL + 1.
+ifdef CURRENT_TIER
+ifeq (0,$(MAKELEVEL))
+export NO_RECURSE_MAKELEVEL=1
+else
+export NO_RECURSE_MAKELEVEL=$(word $(MAKELEVEL),2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
+endif
+endif
+
+# Get all directories traversed for all subtiers in the current tier, or use
+# directly the $(*_dirs) variables available in root.mk when there is no
+# TIERS (like for js/src).
+CURRENT_DIRS := $(or $($(CURRENT_TIER)_dirs),$(foreach subtier,$(CURRENT_SUBTIERS),$($(CURRENT_TIER)_subtier_$(subtier))))
+
+# Subtier delimiter rules
+$(addprefix subtiers/,$(addsuffix _start/$(CURRENT_TIER),$(CURRENT_SUBTIERS))): subtiers/%_start/$(CURRENT_TIER):
+	$(call BUILDSTATUS,SUBTIER_START $(CURRENT_TIER) $* $(if $(BUG_915535_FIXED),$($(CURRENT_TIER)_subtier_$*)))
+
+$(addprefix subtiers/,$(addsuffix _finish/$(CURRENT_TIER),$(CURRENT_SUBTIERS))): subtiers/%_finish/$(CURRENT_TIER):
+	$(call BUILDSTATUS,SUBTIER_FINISH $(CURRENT_TIER) $*)
+
+# Recursion rule for all directories traversed for all subtiers in the
+# current tier.
+# root.mk defines subtier_of_* variables, that map a normalized subdir path to
+# a subtier name (e.g. subtier_of_memory_jemalloc = base)
+$(addsuffix /$(CURRENT_TIER),$(CURRENT_DIRS)): %/$(CURRENT_TIER):
+ifdef BUG_915535_FIXED
+	$(call BUILDSTATUS,TIERDIR_START $(CURRENT_TIER) $(subtier_of_$(subst /,_,$*)) $*)
+endif
+	+@$(MAKE) -C $* $(if $(filter $*,$(tier_$(subtier_of_$(subst /,_,$*))_staticdirs)),,$(CURRENT_TIER))
+ifdef BUG_915535_FIXED
+	$(call BUILDSTATUS,TIERDIR_FINISH $(CURRENT_TIER) $(subtier_of_$(subst /,_,$*)) $*)
+endif
+
+else
+
+# Don't recurse if MAKELEVEL is NO_RECURSE_MAKELEVEL as defined above, but
+# still recurse for externally managed make files (gyp-generated ones).
+ifeq ($(EXTERNALLY_MANAGED_MAKE_FILE)_$(NO_RECURSE_MAKELEVEL),_$(MAKELEVEL))
+
+compile libs export tools::
+
+else
 #########################
 # Tier traversal handling
 #########################
 
 ifdef TIERS
 
-compile libs export tools::
+libs export tools::
 	$(call BUILDSTATUS,TIER_START $@ $(filter-out $(if $(filter export,$@),,precompile),$(TIERS)))
-	$(foreach tier,$(TIERS), $(if $(filter-out compile_precompile libs_precompile tools_precompile,$@_$(tier)), \
+	$(foreach tier,$(TIERS), $(if $(filter-out libs_precompile tools_precompile,$@_$(tier)), \
 		$(call BUILDSTATUS,SUBTIER_START $@ $(tier) $(if $(filter libs,$@),$(tier_$(tier)_staticdirs)) $(tier_$(tier)_dirs)) \
 		$(if $(filter libs,$@),$(foreach dir, $(tier_$(tier)_staticdirs), $(call TIER_DIR_SUBMAKE,$@,$(tier),$(dir),,1))) \
 		$(foreach dir, $(tier_$(tier)_dirs), $(call TIER_DIR_SUBMAKE,$@,$(tier),$(dir),$@)) \
 		$(call BUILDSTATUS,SUBTIER_FINISH $@ $(tier))))
 	$(call BUILDSTATUS,TIER_FINISH $@)
 
 else
 
@@ -36,14 +127,18 @@ endif
 $(1):: $$(SUBMAKEFILES)
 ifdef PARALLEL_DIRS
 	+@$(MAKE) $$(PARALLEL_DIRS_$(1))
 endif
 	$$(LOOP_OVER_DIRS)
 
 endef
 
-$(foreach subtier,export compile libs tools,$(eval $(call CREATE_SUBTIER_TRAVERSAL_RULE,$(subtier))))
+$(foreach subtier,export libs tools,$(eval $(call CREATE_SUBTIER_TRAVERSAL_RULE,$(subtier))))
 
-compile export tools:: $(SUBMAKEFILES)
+tools export:: $(SUBMAKEFILES)
 	$(LOOP_OVER_TOOL_DIRS)
 
-endif
+endif # ifdef TIERS
+
+endif # ifeq ($(EXTERNALLY_MANAGED_MAKE_FILE)_$(NO_RECURSE_MAKELEVEL),_$(MAKELEVEL))
+
+endif # ifeq (1_.,$(MOZ_PSEUDO_DERECURSE)_$(DEPTH))
--- a/js/src/config/rules.mk
+++ b/js/src/config/rules.mk
@@ -690,17 +690,19 @@ SUBMAKEFILES += $(addsuffix /Makefile, $
 
 # 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
 ifndef SUPPRESS_DEFAULT_RULES
 default all::
 	$(MAKE) export
+ifdef MOZ_PSEUDO_DERECURSE
 	$(MAKE) compile
+endif
 	$(MAKE) libs
 	$(MAKE) tools
 endif # SUPPRESS_DEFAULT_RULES
 
 ifeq ($(findstring s,$(filter-out --%, $(MAKEFLAGS))),)
 ECHO := echo
 QUIET :=
 else
--- a/python/mozbuild/mozbuild/backend/recursivemake.py
+++ b/python/mozbuild/mozbuild/backend/recursivemake.py
@@ -4,16 +4,18 @@
 
 from __future__ import unicode_literals
 
 import errno
 import logging
 import os
 import types
 
+from collections import namedtuple
+
 from mozpack.copier import FilePurger
 from mozpack.manifests import (
     InstallManifest,
 )
 import mozpack.path as mozpath
 
 from .common import CommonBackend
 from ..frontend.data import (
@@ -30,16 +32,17 @@ from ..frontend.data import (
     SandboxDerived,
     TestWebIDLFile,
     VariablePassthru,
     XPIDLFile,
     XpcshellManifests,
     WebIDLFile,
 )
 from ..util import FileAvoidWrite
+from ..makeutil import Makefile
 
 
 class BackendMakeFile(object):
     """Represents a generated backend.mk file.
 
     This is both a wrapper around a file handle as well as a container that
     holds accumulated state.
 
@@ -61,16 +64,17 @@ class BackendMakeFile(object):
 
     The solution is to not update the mtimes of backend.mk files unless they
     actually change. We use FileAvoidWrite to accomplish this.
     """
 
     def __init__(self, srcdir, objdir, environment):
         self.srcdir = srcdir
         self.objdir = objdir
+        self.relobjdir = objdir[len(environment.topobjdir) + 1:]
         self.environment = environment
         self.path = os.path.join(objdir, 'backend.mk')
 
         # XPIDLFiles attached to this file.
         self.idls = []
         self.xpt_name = None
 
         self.fh = FileAvoidWrite(self.path)
@@ -102,16 +106,145 @@ class BackendMakeFile(object):
             self.fh.write('NONRECURSIVE_TARGETS_export_xpidl_DIRECTORY = '
                 '$(DEPTH)/config/makefiles/precompile\n')
             self.fh.write('NONRECURSIVE_TARGETS_export_xpidl_TARGETS += '
                 'xpidl\n')
 
         return self.fh.close()
 
 
+class RecursiveMakeTraversal(object):
+    """
+    Helper class to keep track of how the "traditional" recursive make backend
+    recurses subdirectories. This is useful until all adhoc rules are removed
+    from Makefiles.
+
+    Each directory may have one or more types of subdirectories:
+        - parallel
+        - static
+        - (normal) dirs
+        - tests
+        - tools
+
+    The "traditional" recursive make backend recurses through those by first
+    building the current directory, followed by parallel directories (in
+    parallel), then static directories, dirs, tests and tools (all
+    sequentially).
+    """
+    SubDirectoryCategories = ['parallel', 'static', 'dirs', 'tests', 'tools']
+    SubDirectoriesTuple = namedtuple('SubDirectories', SubDirectoryCategories)
+    class SubDirectories(SubDirectoriesTuple):
+        def __new__(self):
+            return RecursiveMakeTraversal.SubDirectoriesTuple.__new__(self, [], [], [], [], [])
+
+    def __init__(self):
+        self._traversal = {}
+
+    def add(self, dir, **kargs):
+        """
+        Function signature is, in fact:
+            def add(self, dir, parallel=[], static=[], dirs=[],
+                               tests=[], tools=[])
+        but it's done with **kargs to avoid repetitive code.
+
+        Adds a directory to traversal, registering its subdirectories,
+        sorted by categories. If the directory was already added to
+        traversal, adds the new subdirectories to the already known lists.
+        """
+        subdirs = self._traversal.setdefault(dir, self.SubDirectories())
+        for key, value in kargs.items():
+            assert(key in self.SubDirectoryCategories)
+            getattr(subdirs, key).extend(value)
+
+    @staticmethod
+    def default_filter(current, subdirs):
+        """
+        Default filter for use with compute_dependencies and traverse.
+        """
+        return current, subdirs.parallel, \
+               subdirs.static + subdirs.dirs + subdirs.tests + subdirs.tools
+
+    def call_filter(self, current, filter):
+        """
+        Helper function to call a filter from compute_dependencies and
+        traverse.
+        """
+        return filter(current, self._traversal.get(current,
+            self.SubDirectories()))
+
+    def compute_dependencies(self, filter=None):
+        """
+        Compute make dependencies corresponding to the registered directory
+        traversal.
+
+        filter is a function with the following signature:
+            def filter(current, subdirs)
+        where current is the directory being traversed, and subdirs the
+        SubDirectories instance corresponding to it.
+        The filter function returns a tuple (filtered_current, filtered_parallel,
+        filtered_dirs) where filtered_current is either current or None if
+        the current directory is to be skipped, and filtered_parallel and
+        filtered_dirs are lists of parallel directories and sequential
+        directories, which can be rearranged from whatever is given in the
+        SubDirectories members.
+
+        The default filter corresponds to a default recursive traversal.
+        """
+        filter = filter or self.default_filter
+
+        deps = {}
+
+        def recurse(start_node, prev_nodes=None):
+            current, parallel, sequential = self.call_filter(start_node, filter)
+            if current is not None:
+                if start_node != '':
+                    deps[start_node] = prev_nodes
+                prev_nodes = (start_node,)
+            if not start_node in self._traversal:
+                return prev_nodes
+            parallel_nodes = []
+            for node in parallel:
+                nodes = recurse(node, prev_nodes)
+                if nodes != ('',):
+                    parallel_nodes.extend(nodes)
+            if parallel_nodes:
+                prev_nodes = tuple(parallel_nodes)
+            for dir in sequential:
+                prev_nodes = recurse(dir, prev_nodes)
+            return prev_nodes
+
+        return recurse(''), deps
+
+    def traverse(self, start, filter=None):
+        """
+        Iterate over the filtered subdirectories, following the traditional
+        make traversal order.
+        """
+        if filter is None:
+            filter = self.default_filter
+
+        current, parallel, sequential = self.call_filter(start, filter)
+        if current is not None:
+            yield start
+        if not start in self._traversal:
+            return
+        for node in parallel:
+            for n in self.traverse(node, filter):
+                yield n
+        for dir in sequential:
+            for d in self.traverse(dir, filter):
+                yield d
+
+    def get_subdirs(self, dir):
+        """
+        Returns all direct subdirectories under the given directory.
+        """
+        return self._traversal.get(dir, self.SubDirectories())
+
+
 class RecursiveMakeBackend(CommonBackend):
     """Backend that integrates with the existing recursive make build system.
 
     This backend facilitates the transition from Makefile.in to moz.build
     files.
 
     This backend performs Makefile.in -> Makefile conversion. It also writes
     out .mk files containing content derived from moz.build files. Both are
@@ -154,16 +287,18 @@ class RecursiveMakeBackend(CommonBackend
                 'dist_include',
                 'dist_public',
                 'dist_private',
                 'dist_sdk',
                 'tests',
                 'xpidl',
             ]}
 
+        self._traversal = RecursiveMakeTraversal()
+
     def _update_from_avoid_write(self, result):
         existed, updated = result
 
         if not existed:
             self.summary.created_count += 1
         elif updated:
             self.summary.updated_count += 1
         else:
@@ -244,19 +379,118 @@ class RecursiveMakeBackend(CommonBackend
         elif isinstance(obj, XpcshellManifests):
             self._process_xpcshell_manifests(obj, backend_file)
 
         elif isinstance(obj, LocalInclude):
             self._process_local_include(obj.path, backend_file)
 
         self._backend_files[obj.srcdir] = backend_file
 
+    def _fill_root_mk(self):
+        """
+        Create two files, root.mk and root-deps.mk, the first containing
+        convenience variables, and the other dependency definitions for a
+        hopefully proper directory traversal.
+        """
+        # Skip static dirs during export traversal
+        def export_filter(current, subdirs):
+            return current, subdirs.parallel, \
+                subdirs.dirs + subdirs.tests + subdirs.tools
+
+        # compile and tools tiers use the same traversal as export, but skip
+        # precompile.
+        def other_filter(current, subdirs):
+            if current == 'subtiers/precompile':
+                return None, [], []
+            return export_filter(current, subdirs)
+
+        # Skip tools dirs during libs traversal
+        def libs_filter(current, subdirs):
+            if current == 'subtiers/precompile':
+                return None, [], []
+            return current, subdirs.parallel, \
+                subdirs.static + subdirs.dirs + subdirs.tests
+
+        # compile and tools tiers use the same traversal as export
+        filters = {
+            'export': export_filter,
+            'compile': other_filter,
+            'libs': libs_filter,
+            'tools': other_filter,
+        }
+
+        root_deps_mk = Makefile()
+
+        # Fill the dependencies for traversal of each tier.
+        for tier, filter in filters.items():
+            main, all_deps = \
+                self._traversal.compute_dependencies(filter)
+            for dir, deps in all_deps.items():
+                rule = root_deps_mk.create_rule(['%s/%s' % (dir, tier)])
+                if deps is not None:
+                    rule.add_dependencies('%s/%s' % (d, tier) for d in deps if d)
+            root_deps_mk.create_rule(['recurse_%s' % tier]) \
+                        .add_dependencies('%s/%s' % (d, tier) for d in main)
+
+        root_mk = Makefile()
+
+        # Fill root.mk with the convenience variables.
+        for tier, filter in filters.items() + [('all', self._traversal.default_filter)]:
+            # Gather filtered subtiers for the given tier
+            all_direct_subdirs = reduce(lambda x, y: x + y,
+                                        self._traversal.get_subdirs(''), [])
+            direct_subdirs = [d for d in all_direct_subdirs
+                              if filter(d, self._traversal.get_subdirs(d))[0]]
+            subtiers = [d.replace('subtiers/', '') for d in direct_subdirs
+                        if d.startswith('subtiers/')]
+
+            if tier != 'all':
+                # Gather filtered directories for the given tier
+                dirs = [d for d in direct_subdirs if not d.startswith('subtiers/')]
+                if dirs:
+                    # For build systems without tiers (js/src), output a list
+                    # of directories for each tier.
+                    root_mk.add_statement('%s_dirs := %s' % (tier, ' '.join(dirs)))
+                    continue
+                if subtiers:
+                    # Output the list of filtered subtiers for the given tier.
+                    root_mk.add_statement('%s_subtiers := %s' % (tier, ' '.join(subtiers)))
+
+            for subtier in subtiers:
+                # subtier_dirs[0] is 'subtiers/%s_start' % subtier, skip it
+                subtier_dirs = list(self._traversal.traverse('subtiers/%s_start' % subtier, filter))[1:]
+                if tier == 'all':
+                    for dir in subtier_dirs:
+                        # Output convenience variables to be able to map directories
+                        # to subtier names from Makefiles.
+                        stamped = dir.replace('/', '_')
+                        root_mk.add_statement('subtier_of_%s := %s' % (stamped, subtier))
+
+                else:
+                    # Output the list of filtered directories for each tier/subtier
+                    # pair.
+                    root_mk.add_statement('%s_subtier_%s := %s' % (tier, subtier, ' '.join(subtier_dirs)))
+
+        root_mk.add_statement('$(call include_deps,root-deps.mk)')
+
+        root = FileAvoidWrite(
+            os.path.join(self.environment.topobjdir, 'root.mk'))
+        root_deps = FileAvoidWrite(
+            os.path.join(self.environment.topobjdir, 'root-deps.mk'))
+        root_mk.dump(root, removal_guard=False)
+        root_deps_mk.dump(root_deps, removal_guard=False)
+        self._update_from_avoid_write(root.close())
+        self._update_from_avoid_write(root_deps.close())
+
+
     def consume_finished(self):
         CommonBackend.consume_finished(self)
 
+        self._fill_root_mk()
+
         for srcdir in sorted(self._backend_files.keys()):
             bf = self._backend_files[srcdir]
 
             if not os.path.exists(bf.objdir):
                 try:
                     os.makedirs(bf.objdir)
                 except OSError as error:
                     if error.errno != errno.EEXIST:
@@ -360,51 +594,92 @@ class RecursiveMakeBackend(CommonBackend
             self.summary.managed_count += 1
 
         self._write_manifests('install', self._install_manifests)
 
     def _process_directory_traversal(self, obj, backend_file):
         """Process a data.DirectoryTraversal instance."""
         fh = backend_file.fh
 
+        def relativize(dirs):
+            return [mozpath.normpath(mozpath.join(backend_file.relobjdir, d))
+                for d in dirs]
+
         for tier, dirs in obj.tier_dirs.iteritems():
             fh.write('TIERS += %s\n' % tier)
+            # For pseudo derecursification, subtiers are treated as pseudo
+            # directories, with a special hierarchy:
+            # - subtier1 - subtier1_start - dirA - dirAA
+            # |          |                |      + dirAB
+            # |          |                ...
+            # |          |                + dirB
+            # |          + subtier1_finish
+            # + subtier2 - subtier2_start ...
+            # ...        + subtier2_finish
+            self._traversal.add('subtiers/%s' % tier,
+                                dirs=['subtiers/%s_start' % tier,
+                                      'subtiers/%s_finish' % tier])
 
             if dirs:
                 fh.write('tier_%s_dirs += %s\n' % (tier, ' '.join(dirs)))
                 fh.write('DIRS += $(tier_%s_dirs)\n' % tier)
+                self._traversal.add('subtiers/%s_start' % tier,
+                                    dirs=relativize(dirs))
 
             # tier_static_dirs should have the same keys as tier_dirs.
             if obj.tier_static_dirs[tier]:
                 fh.write('tier_%s_staticdirs += %s\n' % (
                     tier, ' '.join(obj.tier_static_dirs[tier])))
+                self._traversal.add('subtiers/%s_start' % tier,
+                                    static=relativize(obj.tier_static_dirs[tier]))
+
+            self._traversal.add('subtiers/%s_start' % tier)
+            self._traversal.add('subtiers/%s_finish' % tier)
+            self._traversal.add('', dirs=['subtiers/%s' % tier])
 
         if obj.dirs:
             fh.write('DIRS := %s\n' % ' '.join(obj.dirs))
+            self._traversal.add(backend_file.relobjdir, dirs=relativize(obj.dirs))
 
         if obj.parallel_dirs:
             fh.write('PARALLEL_DIRS := %s\n' % ' '.join(obj.parallel_dirs))
+            self._traversal.add(backend_file.relobjdir,
+                                parallel=relativize(obj.parallel_dirs))
 
         if obj.tool_dirs:
             fh.write('TOOL_DIRS := %s\n' % ' '.join(obj.tool_dirs))
+            self._traversal.add(backend_file.relobjdir,
+                                tools=relativize(obj.tool_dirs))
 
         if obj.test_dirs:
             fh.write('TEST_DIRS := %s\n' % ' '.join(obj.test_dirs))
+            self._traversal.add(backend_file.relobjdir,
+                                tests=relativize(obj.test_dirs))
 
         if obj.test_tool_dirs and \
             self.environment.substs.get('ENABLE_TESTS', False):
 
             fh.write('TOOL_DIRS += %s\n' % ' '.join(obj.test_tool_dirs))
+            self._traversal.add(backend_file.relobjdir,
+                                tools=relativize(obj.test_tool_dirs))
 
         if len(obj.external_make_dirs):
             fh.write('DIRS += %s\n' % ' '.join(obj.external_make_dirs))
+            self._traversal.add(backend_file.relobjdir,
+                                dirs=relativize(obj.external_make_dirs))
 
         if len(obj.parallel_external_make_dirs):
             fh.write('PARALLEL_DIRS += %s\n' %
                 ' '.join(obj.parallel_external_make_dirs))
+            self._traversal.add(backend_file.relobjdir,
+                                parallel=relativize(obj.parallel_external_make_dirs))
+
+        # The directory needs to be registered whether subdirectories have been
+        # registered or not.
+        self._traversal.add(backend_file.relobjdir)
 
         if obj.is_tool_dir:
             fh.write('IS_TOOL_DIR := 1\n')
 
     def _process_exports(self, obj, exports, backend_file, namespace=""):
         # This may not be needed, but is present for backwards compatibility
         # with the old make rules, just in case.
         if not obj.dist_install:
--- a/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
+++ b/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
@@ -1,28 +1,157 @@
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 from __future__ import unicode_literals
 
 import os
+import unittest
 
 from mozpack.manifests import (
     InstallManifest,
 )
 from mozunit import main
 
-from mozbuild.backend.recursivemake import RecursiveMakeBackend
+from mozbuild.backend.recursivemake import (
+    RecursiveMakeBackend,
+    RecursiveMakeTraversal,
+)
 from mozbuild.frontend.emitter import TreeMetadataEmitter
 from mozbuild.frontend.reader import BuildReader
 
 from mozbuild.test.backend.common import BackendTester
 
 
+class TestRecursiveMakeTraversal(unittest.TestCase):
+    def test_traversal(self):
+        traversal = RecursiveMakeTraversal()
+        traversal.add('', dirs=['A', 'B', 'C'])
+        traversal.add('', dirs=['D'])
+        traversal.add('A')
+        traversal.add('B', dirs=['E', 'F'])
+        traversal.add('C', parallel=['G', 'H'])
+        traversal.add('D', parallel=['I'], dirs=['K'])
+        traversal.add('D', parallel=['J'], dirs=['L'])
+        traversal.add('E')
+        traversal.add('F')
+        traversal.add('G')
+        traversal.add('H')
+        traversal.add('I', dirs=['M', 'N'])
+        traversal.add('J', parallel=['O', 'P'])
+        traversal.add('K', parallel=['Q', 'R'])
+        traversal.add('L', dirs=['S'])
+        traversal.add('M')
+        traversal.add('N', dirs=['T'])
+        traversal.add('O')
+        traversal.add('P', parallel=['U'])
+        traversal.add('Q')
+        traversal.add('R', dirs=['V'])
+        traversal.add('S', dirs=['W'])
+        traversal.add('T')
+        traversal.add('U')
+        traversal.add('V')
+        traversal.add('W', dirs=['X'])
+        traversal.add('X')
+
+        start, deps = traversal.compute_dependencies()
+        self.assertEqual(start, ('X',))
+        self.assertEqual(deps, {
+            'A': ('',),
+            'B': ('A',),
+            'C': ('F',),
+            'D': ('G', 'H'),
+            'E': ('B',),
+            'F': ('E',),
+            'G': ('C',),
+            'H': ('C',),
+            'I': ('D',),
+            'J': ('D',),
+            'K': ('T', 'O', 'U'),
+            'L': ('Q', 'V'),
+            'M': ('I',),
+            'N': ('M',),
+            'O': ('J',),
+            'P': ('J',),
+            'Q': ('K',),
+            'R': ('K',),
+            'S': ('L',),
+            'T': ('N',),
+            'U': ('P',),
+            'V': ('R',),
+            'W': ('S',),
+            'X': ('W',),
+        })
+
+        self.assertEqual(list(traversal.traverse('')),
+                         ['', 'A', 'B', 'E', 'F', 'C', 'G', 'H', 'D', 'I',
+                         'M', 'N', 'T', 'J', 'O', 'P', 'U', 'K', 'Q', 'R',
+                         'V', 'L', 'S', 'W', 'X'])
+
+        self.assertEqual(list(traversal.traverse('C')),
+                         ['C', 'G', 'H'])
+
+    def test_traversal_2(self):
+        traversal = RecursiveMakeTraversal()
+        traversal.add('', dirs=['A', 'B', 'C'])
+        traversal.add('A')
+        traversal.add('B', static=['D'], dirs=['E', 'F'])
+        traversal.add('C', parallel=['G', 'H'], dirs=['I'])
+        # Don't register D
+        traversal.add('E')
+        traversal.add('F')
+        traversal.add('G')
+        traversal.add('H')
+        traversal.add('I')
+
+        start, deps = traversal.compute_dependencies()
+        self.assertEqual(start, ('I',))
+        self.assertEqual(deps, {
+            'A': ('',),
+            'B': ('A',),
+            'C': ('F',),
+            'D': ('B',),
+            'E': ('D',),
+            'F': ('E',),
+            'G': ('C',),
+            'H': ('C',),
+            'I': ('G', 'H'),
+        })
+
+    def test_traversal_filter(self):
+        traversal = RecursiveMakeTraversal()
+        traversal.add('', dirs=['A', 'B', 'C'])
+        traversal.add('A')
+        traversal.add('B', static=['D'], dirs=['E', 'F'])
+        traversal.add('C', parallel=['G', 'H'], dirs=['I'])
+        traversal.add('D')
+        traversal.add('E')
+        traversal.add('F')
+        traversal.add('G')
+        traversal.add('H')
+        traversal.add('I')
+
+        def filter(current, subdirs):
+            if current == 'B':
+                current = None
+            return current, subdirs.parallel, subdirs.dirs
+
+        start, deps = traversal.compute_dependencies(filter)
+        self.assertEqual(start, ('I',))
+        self.assertEqual(deps, {
+            'A': ('',),
+            'C': ('F',),
+            'E': ('A',),
+            'F': ('E',),
+            'G': ('C',),
+            'H': ('C',),
+            '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')))
         self.assertTrue(os.path.exists(os.path.join(env.topobjdir,
             'backend.RecursiveMakeBackend.built.pp')))