Каков наиболее эффективный метод получения топологически упорядоченного списка функций?

Question

Предположим, что у нас есть модуль, содержащий некоторые функции без рекурсивных вызовов (так что граф-вызов является DAG). Каков наиболее эффективный метод получения вектора функции * из модуля, упорядоченного топологическим порядком в терминах порядка вызова? По топологическому порядку я имею в виду, что если foo() вызывает bar(), то foo появится перед строкой в ​​отсортированном списке. Есть ли какой-либо проход анализа, который может дать мне эту информацию, или мне нужно написать свою собственную процедуру сортировки?

Answer 1

Хотя я не знаком с существующим пропуском, который делает точно, что вы хотите, код в LLVM очень близко, и я уверен, что вы можете использовать его для быстрого решения своей проблемы. Он находится в библиотеке IPA (Inter-процедурный анализ), в lib/Analysis/IPA. В частности, посмотрите на lib/Analysis/IPA/CallGraph.cpp - он строит график вызовов в модуле. Сортировка такого графика топологически должна быть довольно простой.