--- a/python/mozbuild/mozbuild/backend/recursivemake.py
+++ b/python/mozbuild/mozbuild/backend/recursivemake.py
@@ -258,42 +258,45 @@ class RecursiveMakeTraversal(object):
     SubDirectoryCategories = ['dirs', 'tests']
     SubDirectoriesTuple = namedtuple('SubDirectories', SubDirectoryCategories)
     class SubDirectories(SubDirectoriesTuple):
         def __new__(self):
             return RecursiveMakeTraversal.SubDirectoriesTuple.__new__(self, [], [])
 
     def __init__(self):
         self._traversal = {}
+        self._attached = set()
 
     def add(self, dir, dirs=[], tests=[]):
         """
         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 (('dirs', dirs), ('tests', tests)):
             assert(key in self.SubDirectoryCategories)
+            # Callers give us generators
+            value = list(value)
             getattr(subdirs, key).extend(value)
+            self._attached |= set(value)
 
     @staticmethod
     def default_filter(current, subdirs):
         """
         Default filter for use with compute_dependencies and traverse.
         """
         return current, [], subdirs.dirs + subdirs.tests
 
     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()))
+        return filter(current, self.get_subdirs(current))
 
     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)
@@ -352,17 +355,26 @@ class RecursiveMakeTraversal(object):
         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())
+        result = self._traversal.get(dir, self.SubDirectories())
+        if dir == '':
+            unattached = set(self._traversal) - self._attached - set([''])
+            if unattached:
+                new_result = self.SubDirectories()
+                new_result.dirs.extend(result.dirs)
+                new_result.dirs.extend(sorted(unattached))
+                new_result.tests.extend(result.tests)
+                result = new_result
+        return result
 
 
 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.
 

--- a/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
+++ b/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
@@ -153,16 +153,48 @@ class TestRecursiveMakeTraversal(unittes
             'D': ('A',),
             'E': ('D',),
             'F': ('E',),
             'G': ('C',),
             'H': ('G',),
             'I': ('H',),
         })
 
+    def test_traversal_parallel(self):
+        traversal = RecursiveMakeTraversal()
+        traversal.add('', dirs=['A', 'B', 'C'])
+        traversal.add('A')
+        traversal.add('B', dirs=['D', 'E', 'F'])
+        traversal.add('C', dirs=['G', 'H', 'I'])
+        traversal.add('D')
+        traversal.add('E')
+        traversal.add('F')
+        traversal.add('G')
+        traversal.add('H')
+        traversal.add('I')
+        traversal.add('J')
+
+        def filter(current, subdirs):
+            return current, subdirs.dirs, []
+
+        start, deps = traversal.compute_dependencies(filter)
+        self.assertEqual(start, ('A', 'D', 'E', 'F', 'G', 'H', 'I', 'J'))
+        self.assertEqual(deps, {
+            'A': ('',),
+            'B': ('',),
+            'C': ('',),
+            'D': ('B',),
+            'E': ('B',),
+            'F': ('B',),
+            'G': ('C',),
+            'H': ('C',),
+            'I': ('C',),
+            'J': ('',),
+        })
+
 class TestRecursiveMakeBackend(BackendTester):
     def test_basic(self):
         """Ensure the RecursiveMakeBackend works without error."""
         env = self._consume('stub0', RecursiveMakeBackend)
         self.assertTrue(os.path.exists(mozpath.join(env.topobjdir,
             'backend.RecursiveMakeBackend')))
         self.assertTrue(os.path.exists(mozpath.join(env.topobjdir,
             'backend.RecursiveMakeBackend.in')))