Makefile: Run the subdirectory recursion in parallel

Makefile: Run the subdirectory recursion in parallel

The top-level makefile was marked .NOTPARALLEL and ran the
per-subdirectory sub-makes strictly one at a time in the topological
order computed by scripts/gen-sorted.awk.  Only the compilations inside
a single subdirectory could run in parallel, so on wide machines every
subdirectory's compile tail and link steps left most cores idle, once
per subdirectory per pass.

Drop .NOTPARALLEL and encode the ordering the serial recursion relied
on as explicit dependencies between the per-subdirectory targets:

  * The subdirectories that generate shared files in $(common-objpfx)
    consumed by the rest of the build without explicit dependencies run
    serially, in their sorted order, before the rest fan out: csu
    provides the tree-wide gen-as-const headers, and on Hurd the mach
    and hurd directories generate the MiG RPC headers (every other
    subdirectory otherwise runs a nested make in hurd/ to create them,
    racing under parallel recursion; see sysdeps/mach/hurd/Makefile).
    The first of them also materializes the other shared generated files
    (abi-versions.h, sysd-syscalls, before-compile headers).

  * The edges requested by the Depend files (now emitted by
    gen-sorted.awk as subdir-deps-*) are preserved.  Edges pointing to
    elf are dropped, as the sorted list already overrides them by
    forcing elf last.

  * The tests and xtests classes only run the per-directory test
    programs, which are mutually independent once the others pass has
    built the tree.  They therefore carry only the others pass barrier
    below and none of the csu-first or Depend edges (+ordered_parallel_-
    subdir_targets excludes them); otherwise "make subdir/tests" would
    also run the tests of every subdirectory reachable through those
    edges, rather than just the requested one.

  * elf stays last: its rtld link consumes $(common-objpfx)libc_pic.a,
    which aggregates every other subdirectory's objects, and its
    rtld-Rules recursion compiles into the other subdirectories' object
    directories.

  * Pass barriers replace the implicit pass ordering: others after lib
    (a subdirectory others sub-make would otherwise race to link
    libc.so itself), tests/xtests after others, and the testroot
    install behind others.

  * The threading (nptl, or htl on Hurd) and realtime (rt) tests are
    timing-sensitive and were previously shielded from system load by
    the global .NOTPARALLEL.  With the recursion now parallel, a full
    test run ('make check'/'tests', run-built-tests=yes) orders them
    after the rest of the test run and one group at a time -- the
    threading subdirectory, then rt -- and each serializes its own run
    via a .NOTPARALLEL in its Makefile.  A targeted 'make subdir/tests'
    is not ordered.

    The serialization (the per-subdirectory .NOTPARALLEL and the ordering
    above) constrains only the test run, not the build of the test
    programs; but building and running a subdirectory's tests are fused
    in its sub-make, so under run-built-tests=yes the serialized
    subdirectories would also build their test programs serially.  To
    avoid that, the top-level 'make check' (in Makerules) now runs two
    passes: it builds every test program with run-built-tests=no, where
    the recursion is fully parallel and none of the serialization
    applies, and then runs the tests with run-built-tests=yes.  'make
    tests' and a subdirectory's own 'check' stay single pass.

  * The subdirectory-built files that the top-level libc.so and
    linkobj/libc_pic.a rules list as prerequisites (elf/ld.so,
    interp.os, sofini.os, sunrpc/librpc_compat_pic.a, and on Hurd
    mach/libmachuser_pic.a and hurd/libhurduser_pic.a, from which the
    lib*user-link.so inputs of libc.so are built) get order-only edges
    on the corresponding sub-make with an explicit empty recipe.  A
    prerequisite-only rule would trigger an implicit rule search and
    this level would compile them itself in the wrong context.

  * The install, clean, abi, and stubs target classes keep the
    previous total order via a serial dependency chain.

  * The elf DSO sorting test recipes, run when make remakes the
    included generated makefiles at parse time, create the elf object
    directory before writing into it; the serial recursion no longer
    guarantees another rule created it first.

  * catgets builds locale-specific message catalogs (and tst-catgets
    reads one) by running gencat under de_DE.ISO-8859-1, hr_HR.ISO-8859-2
    and ja_JP.SJIS, but never declared those locales as prerequisites: it
    relied on localedata running before it in the serial order.  Under
    the parallel recursion gencat could run before localedata generated
    the locale, fall back to C, and fail.  catgets/Makefile now pulls the
    locales in via gen-locales.mk, like the other subdirectories that use
    locales in their tests.

Results on a x86_64 machine [1] with default configuration [3]: a
from-scratch build improves from 78.728s to 61s, and check with
run-built-tests=no from 374s to 190s.

On a 80-core aarch64 machine [2] with default configuration [3]: a
from-scratch build improves from 105.251s to 56.703s, and check with
run-built-tests=no from 886.183s to 298.726s.

Build results are unchanged: all 8919 built objects, archives, and
shared objects are bit-identical to the serial build across 7 clean
parallel builds, the installed tree layout is identical, and the
tests.sum failure sets are identical.  i686-gnu was verified with
repeated from-scratch builds.

[1] Ryzen 5900x, 12c/24t, gcc 16.1.1, binutils 2.26, and GNU make 4.3
[2] N1, 80c, gcc 15.1.1, binutils 2.25, GNU make 4.3
[3] --enable-stack-protector=all --enable-bind-now=yes --enable-profile=yes
    --enable-fortify-source=2 --enable-hardcoded-path-in-tests

Reviewed-by: Sam James <sam@gentoo.org>