Межпроцеду́рный ана́лиз програ́мм, анализ программ, который в ходе работы рассматривает совместно несколько процедур программы и учитывает связи между ними, т. е. при обработке вызывающей процедуры и – внутри неё – вызова другой процедуры оценивает влияние этого вызова на состояние анализа. Обычно предполагается, что не все вызовы анализируемых процедур известны (т. н. открытый мир). Например, выполняется анализ библиотеки, или анализируется отдельный файл программы в языках с раздельной компиляцией, или в ходе выполнения программы возможна загрузка дополнительного кода. Реже анализируется вся программа целиком и предполагается, что никакие новые процедуры в неё добавлены быть не могут («закрытый мир»). В языках с раздельной компиляцией и компоновкой межпроцедурная оптимизация всей программы обычно выполняется в ходе компоновки окончательной программы, поэтому термин «оптимизация на этапе компоновки» часто используется как синоним термина «межпроцедурная оптимизация всей программы».

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

Методы межпроцедурного анализа:

• Построение графа потока управления для всей программы. Сначала объединяются графы потока управления отдельных процедур, а затем проводятся дополнительные дуги: непосредственно перед вызовом процедуры проводится дуга к точке её входа (блоку ENTRY графа потока управления), от точки возврата из процедуры (блока EXIT графа) к точке после вызова процедуры.

  Объединение графов потока управления процедур в единый граф.Объединение графов потока управления процедур в единый граф.Чтобы представить поток данных, на первых дугах дополнительно вставляются присваивания фактических параметров конкретного вызова формальным, на вторых – присваивания результата работы процедуры выходным переменным в точке вызова. Такой метод не только плохо работает для больших программ, но и неточен – в объединённом графе потока управления программы возникают нереализуемые пути, которые заходят в процедуру из одной точки вызова, а возвращаются в другую.

• Оптимизация встраивания (англ. inlining) тела процедур в точки вызова. Метод применим в случае, когда программа не содержит рекурсивных вызовов. Метод также неприменим к большим программам из-за высокой вычислительной сложности, однако он более точен, т. к. в каждом месте вызова процедуры её тело (её внутреннее представление для внутрипроцедурного анализа) анализируется отдельно с учётом фактических параметров. Такие методы межпроцедурного анализа, учитывающие контекст вызова процедуры – стек предыдущих вызовов и их фактические параметры, называются контекстно-чувствительными. При разработке алгоритмов анализа необходимо искать компромисс между уровнем контекстной чувствительности и сложностью анализа. Так, часто анализируют процедуру не для каждого контекста вызова по отдельности, а для каждой группы контекстов. Группы выделяются, например, по последним нескольким вызовам в стеке вызовов, по собранной информации о потоке данных, по типу объектов, через которые происходит виртуальный вызов и т. д.

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

Часто сведения в резюме параметризуют, записывая через формальные параметры процедуры, и создают одно резюме, пригодное для обработки всех вызовов процедуры. При обработке вызова процедуры контекстная чувствительность достигается за счёт подстановки фактических параметров на место формальных. Граф вызовов программы при этом обходится в обратном топологическом порядке, чтобы посетить вызываемые процедуры до вызывающих; при наличии рекурсии (циклов в графе вызовов) они разрываются, обходятся заданное число раз или, по аналогии с алгоритмами анализа потока данных, до достижения фиксированной точки. Также обходы графа вызовов снизу вверх комбинируют с обходами сверху вниз (от точек входа в программу к листьям).

Обход графа вызовов от листьев к корню.Обход графа вызовов от листьев к корню.Для графа вызовов на картинке сначала будут проанализированы функции f, g и h. Как только функции f и g проанализированы, можно анализировать функцию foo; как только готовы функции g и h, можно анализировать функцию bar. Функция main анализируется последней.

Это позволяет получить более точную информацию, в особенности для анализа распространения чувствительных данных.