> Given that the target-structure of a Makefile contains all the data on 
> what can/should be done an in parallel, and what to wait for before 
> proceeding to the next target, I wonder if that can't be used.

I haven't looked in the source, but it seems it would be harder to write
a make that got that wrong than to write one that gets it right, as it's
really just an obvious extension of the topological ordering any make has
to do anyway (except for the old MS make :).  Therefore I'd be surprised if
make isn't doing that right, or, given a clear demonstration that it isn't,
I'd be surprised if it proved extremely difficult to fix.

On the other hand, "the target-structure of a Makefile contains all the data"
might be an optimistic statement of the way most Makefiles seem to get
written.  I'd hazard they often contain any subset of the complete dependency
data that allows building successfully in the author's environment and
doesn't get too many complaints from outside.  :/  Parallel building is
probably a more demanding test case than what's often used.

-Chap