Граф вызовов




Главная
Новости
Статьи
Строительство
Ремонт
Дизайн и интерьер
Строительная теплофизика
Прочность сплавов
Основания и фундаменты
Осадочные породы
Прочность дорог
Минералогия глин
Краны башенные
Справочник токаря
Цементный бетон




15.01.2021


15.01.2021


15.01.2021


06.01.2021


05.01.2021


02.01.2021


29.12.2020





Яндекс.Метрика
         » » Граф вызовов

Граф вызовов

05.01.2021


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

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

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

Определение

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

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

    Пример

    Программа на языке программирования Си, в которой объявлен глобальный указатель 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.