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 a3d79a54d83e
parent 161859 e1998769de9e
child 161927 0d19104a7002
push id3066
push userakeybl@mozilla.com
push dateMon, 09 Dec 2013 19:58:46 +0000
treeherdermozilla-beta@a31a0dce83aa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgps
bugs907365, 912856
milestone27.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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')))