Хороший алгоритм генерации графов вызовов?

Question

Я пишу некоторый код для генерации графиков вызовов для определенного промежуточного представления без его выполнения путем статического сканирования кода IR .Сам код IR не слишком сложен, и я хорошо понимаю, как выглядят последовательности вызовов функций, поэтому все, что мне нужно сделать, это отследить вызовы.В настоящее время я делаю это очевидным образом:

• Следите за тем, где мы находимся
• Если мы сталкиваемся с вызовом функции, выполняем переход к этому месту, выполняем и возвращаемся
• Во время ветвления вставьте грань между вызывающим и вызываемым

Я удовлетворен тем, к чему стремлюсь, но хочу убедиться, что я не изобретаю колесо здесь, и сталкиваюсь с угловыми случаями.Мне интересно, есть ли какие-либо приемлемые хорошие алгоритмы (и / или шаблоны проектирования), которые делают это эффективно?

ОБНОВЛЕНИЕ: ИК-код представляет собой дизассемблирование байт-кода из самодельного Java-подобного языка и выглядит как спецификация Jasmine .

Answer 1

С академической точки зрения, вот некоторые соображения:

• Вы хотите быть консервативным / правильным? Например, предположим, что код, который вы анализируете, содержит вызов через указатель на функцию. Если вы просто генерируете документацию, то с этим не нужно иметь дело. Если вы выполняете оптимизацию кода, которая может пойти не так, вам нужно будет предположить, что «вызов через указатель» означает «может быть что угодно».

• Остерегайтесь исключительных путей выполнения. Ваш IR может или не может абстрагироваться от вас, но помните, что многие операции могут генерировать как исключения уровня языка, так и аппаратные прерывания. Опять же, это зависит от того, что вы хотите сделать с графом вызовов позже.

• Подумайте, как вы справитесь с циклами (например, рекурсия, взаимная рекурсия). Это может повлиять на то, как вы напишете код для обхода графиков позже (то есть им потребуется какой-то набор посещений, чтобы избежать циклов обхода навсегда).

Приветствие.

Обновление 6 марта :

На основании дополнительной информации, добавленной к исходному сообщению:

• Будьте осторожны с вызовами виртуальных методов. Имейте в виду, что в общем случае неизвестно, какой метод будет выполняться. Возможно, вам придется предположить, что вызов перейдет к любому из подклассов определенного класса. Стандартный пример выглядит примерно так: предположим, у вас есть ArrayList<A>, и у вас есть class B extends A. Основываясь на генераторе случайных чисел, вы добавите в список экземпляры A и B. Теперь вы вызываете x.foo() для всех x в списке, где foo() - это виртуальный метод в A с переопределением в B. Поэтому, просто взглянув на исходный код, невозможно узнать, вызывает ли цикл вызовы A.foo, B.foo или оба во время выполнения.

Answer 2

Я не знаю алгоритм, но pycallgraph делает достойную работу.Для этого стоит проверить источник .Это не долго и должно быть хорошо для проверки существующих шаблонов проектирования.