График зависимостей, как и следовало ожидать, основан на предварительных условиях, перечисленных для каждой цели Makefile. make построит график, в котором цели и предпосылки являются вершинами, а от предварительных требований до их целей есть направленное ребро. Таким образом, количество входящих ребер говорит вам, сколько предварительных требований у цели. Если у него нет входящих ребер, у него нет предпосылок.
Например,
Вершины для файлов .c и .h не будут иметь входящих ребер. Эти файлы являются вашими исходными файлами и не нуждаются в сборке.
Затем выполняется топологическая сортировка на графике для определения порядка выполнения. Из Википедии:
Каноническое применение топологической сортировки (топологический порядок) заключается в планировании последовательности заданий или заданий; Алгоритмы топологической сортировки впервые были изучены в начале 1960-х годов в контексте технологии PERT для планирования в управлении проектами (Jarnagin 1960). Задания представлены вершинами, и существует грань от x до y, если задание x должно быть завершено до того, как задание y может быть запущено (например, при стирке белья стиральная машина должна завершить работу до того, как мы сохнем). Затем топологическая сортировка дает порядок выполнения заданий.
Суть топологической сортировки состоит в том, чтобы найти вершины без входящих ребер (без зависимостей) и поставить их на первое место. Затем удалите их из графика. Теперь у вас будет новый набор вершин без входящих ребер (без зависимостей). Это следующие. И так до тех пор, пока не закончите. (Если вы когда-либо достигнете точки, когда таких вершин не существует, то граф зависимостей содержит цикл, который является ошибочным условием.)
В типичном Makefile это означает, что вы сначала создадите исходные файлы (ничего не нужно делать). Затем объектные файлы, которые зависят от этих исходных файлов. Затем библиотеки и исполняемые файлы, созданные из этих объектных файлов.
При обычной непараллельной работе make будет просто выбирать одну цель на каждой итерации и строить ее. Когда он параллельный, он будет захватывать столько целей без зависимостей, сколько может, и строить их параллельно, до количества разрешенных одновременных заданий.
Таким образом, когда make дойдет, скажем, до шага объектного файла, у него будет большое количество вершин в графе, которые не имеют входных ребер. Он знает, что может создавать объектные файлы параллельно, и поэтому он создает n копий gcc для создания объектных файлов.