Граф вызовов

Граф вызовов (англ. Call graph) в теории построения компиляторов — ориентированный граф, который изображает вызовы между подпрограммами в компьютерной программе. В частности, каждый узел представляет собой некоторую процедуру, а каждая дуга (f, g) показывает, что процедура f вызывает процедуру g.

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

Граф вызовов может быть динамическим или статическим. Динамический граф вызовов представляет собой запись выполнения программы. Статический граф вызовов предназначен для представления всех возможных вариантов выполнения программы.

Определение

Граф вызовов программы представляет собой множество узлов и рёбер, в том смысле, что

1. каждой процедуре программы соответствует один узел,
2. каждой точке вызова, то есть месту в программе, где осуществляется вызов процедуры, соответствует один узел графа,
3. если точка вызова с может вызывать процедуру р, в графе имеется ребро от узла с к узлу р.

Многие программы, написанные на таких языках программирования, как Си и Фортран, осуществляют вызовы процедур непосредственно, так что целевой код каждого вызова может быть определён статически. В этом случае каждая точка вызова в графе имеет единственное ребро ровно к одной процедуре. Косвенные вызовы весьма распространены в объектно-ориентированных языках программирования.

Пример

Программа на языке программирования Си, в которой объявлен глобальный указатель pf на функцию, которая получает в качестве параметра и возвращает целое число. Имеются две функции данного типа — fun1 и fun2 — и функция main, тип которой не соответствует указателю pf. Три точки вызова обозначены как c1, с2 и сЗ — эти метки не являются частью программы.

int (*pf)(int);

int fun1(int x) {
    if (x < 10)
c1:     return (*pf)(x+l);
    else 
        return x;
}

int fun2(int y) {
    pf = &fun1; 
c2: return (*pf)(y);
}

void main() {
    pf = &fun2;
c3: (*pf)(5);
}

Простейший анализ того, на что может указывать pf, состоит в исследовании типов функций. Функции fun1 и fun2 имеют тот же тип, что и указатель pf, в то время как функция main имеет другой тип. При более аккуратном анализе программы обнаруживается, что указатель pf в функции main становится равным fun2, а затем в функции fun2 ему присваивается значение fun1. Никаких иных присваиваний указателю pf в программе нет, так что, в частности, указатель pf не может указывать на функцию main.

Литература

на русском

• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструменты = Compilers: Principles, Techniques, and Tools. — Издательский дом "Вильямс", 2008. — ISBN 0-321-48681-1.

на английском

• Ryder, B.G., «Constructing the Call Graph of a Program», Software Engineering, IEEE Transactions on, vol. SE-5, no.3pp. 216—226, May 1979 [1]
• Grove, D., DeFouw, G., Dean, J., and Chambers, C. 1997. «Call graph construction in object-oriented languages», SIGPLAN Not. 32, 10 (Oct. 1997), 108—124. [2]
• Callahan, D.; Carle, A.; Hall, M.W.; Kennedy, K., «Constructing the procedure call multigraph», Software Engineering, IEEE Transactions on, vol.16, no.4pp.483-487, Apr 1990 [3]