--- a/python/mozbuild/mozbuild/backend/recursivemake.py
+++ b/python/mozbuild/mozbuild/backend/recursivemake.py
@@ -737,17 +737,30 @@ class RecursiveMakeBackend(CommonBackend
                 if dir in self._idl_dirs and tier == 'export':
                     rule.add_dependencies(['xpcom/xpidl/%s' % tier])
             rule = root_deps_mk.create_rule(['recurse_%s' % tier])
             if main:
                 rule.add_dependencies('%s/%s' % (d, tier) for d in main)
 
         all_compile_deps = reduce(lambda x,y: x|y,
             self._compile_graph.values()) if self._compile_graph else set()
-        compile_roots = set(self._compile_graph.keys()) - all_compile_deps
+        # Include the following as dependencies of the top recursion target for
+        # compilation:
+        # - nodes that are not dependended upon by anything. Typically, this
+        #   would include programs, that need to be recursed, but that nothing
+        #   depends on.
+        # - nodes that have no dependencies of their own. Technically, this is
+        #   not necessary, because other things have dependencies on them, and
+        #   they all end up rooting to nodes from the above category. But the
+        #   way make works[1] is such that there can be benefits listing them
+        #   as direct dependencies of the top recursion target, to somehow
+        #   prioritize them.
+        #   1. See bug 1262241 comment 5.
+        compile_roots = [t for t, deps in self._compile_graph.iteritems()
+                         if not deps or t not in all_compile_deps]
 
         rule = root_deps_mk.create_rule(['recurse_compile'])
         rule.add_dependencies(compile_roots)
         for target, deps in sorted(self._compile_graph.items()):
             if deps:
                 rule = root_deps_mk.create_rule([target])
                 rule.add_dependencies(deps)
 

--- a/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
+++ b/python/mozbuild/mozbuild/test/backend/test_recursivemake.py
@@ -832,17 +832,17 @@ class TestRecursiveMakeBackend(BackendTe
             'HOST_RUST_CARGO_PROGRAMS += host',
         ]
 
         self.assertEqual(lines, expected)
 
         root_deps_path = mozpath.join(env.topobjdir, 'root-deps.mk')
         lines = [l.strip() for l in open(root_deps_path, 'rt').readlines()]
 
-        self.assertTrue(any(l == 'recurse_compile: code/host code/target' for l in lines))
+        self.assertTrue(any(l == 'recurse_compile: code/target code/host' for l in lines))
 
     def test_final_target(self):
         """Test that FINAL_TARGET is written to backend.mk correctly."""
         env = self._consume('final_target', RecursiveMakeBackend)
 
         final_target_rule = "FINAL_TARGET = $(if $(XPI_NAME),$(DIST)/xpi-stage/$(XPI_NAME),$(DIST)/bin)$(DIST_SUBDIR:%=/%)"
         expected = dict()
         expected[env.topobjdir] = []