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

Межпроцедурный анализ и оптимизация (I)

Одной из самых интересных и важных компонент современного оптимизирующего компилятора является межпроцедурный анализ и оптимизации. Хороший стиль программирования и необходимость разделения работы между разработчиками диктует необходимость разбиения большого проекта на отдельные модули, в которых основные утилиты реализованы как «черные ящики» для всех основных пользователей. Детали реализации, в лучшем случае, известны паре-тройке конкретных разработчиков, ну а иногда, за давностью лет, и вообще никому неизвестны. (А что поделаешь – специализация, глобализация). Ваш код, зачастую, содержит вызовы внешних функций, тела которых определены во внешних файлах или библиотеках и ваши знания о этих функциях минимальны. Ну и помимо этого при разработке больших проектов плодятся всякие глобальные переменные, с помощью которых компоненты большого проекта обмениваются ценной информацией, и для того, чтобы разобраться в работе вашей части кода в случае каких-то проблем, бывает необходимо перелопатить массу кода. Очевидно, что все это сильно осложняет и работу оптимизирующего компилятора. Какие негативные эффекты порождает модульность и есть ли в компиляторе специальные средства для их преодоления – тема для большого разговора. Сейчас я попытаюсь начать такой разговор. Я расскажу о некоторых интересных особенностях работы оптимизирующего компилятора на примере работы компилятора Intel. Ориентироваться буду на OS Windows, поэтому опции компилятора привожу характерные для этой платформы. Ну и чтобы облегчить себе жизнь, я иногда буду использовать аббревиатуры IPA для межпроцедурного анализа и IPO для межпроцедурных оптимизаций. А начну я с рассказа о моделях межпроцедурного анализа и графе вызовов.

Влияние модульности на производительность

Чтобы понять, в чем могут заключаться проблемы порождаемые модульностью, нужно посмотреть, какие существуют варианты работы компилятора, как компилятор пытается решать те или иные проблемы, какие есть ограничения на используемые компилятором методы анализа. Компилятор должен работать консервативно, т.е. с полным недоверием к программисту и программе и делать ту или иную оптимизацию только если полностью доказана ее корректность.

Самый простой вариант работы компилятора – это однопроходная компиляция. При таком варианте работы компилятор обрабатывает поочередно все функции из исходного файла плюс «держит в голове» все предшествующие декларации. Т.е. компилятор последовательно разбирает символы из исходного файла, заполняет таблицы с различными определениями функций, заводит описания определяемых типов и последовательно разбирает тела всех функций в обрабатываемом исходном файле. Сначала компилятор решает задачу проверки программы на соответствие требованиям стандарта языка, затем он может выполнять различные оптимизации – цикловые, скалярные, оптимизации графа потока управления и т.д. По окончании обработки результат сохраняется в объектный файл. При такой работе успешно (и как правило относительно быстро) решается задача – получить работающее приложение, но до оптимальной его работы очень далеко. Причиной этого является то, что компилятор имеет недостаточно информации о нелокальных для обрабатываемой функции объектах. Также компилятор имеет очень мало информации о вызываемых функциях. Влияет ли такое положение вещей на производительность приложения и какие существуют проблемы, связанные с использованием вызовов функций? За примерами далеко ходить не надо. Перечислю некоторые, наиболее, на мой взгляд, важные:

1. Проблемы с разрешением неоднозначности при работе с памятью. Например, в предыдущих моих постах я обсуждал проблему распознавания циклов и сопутствующую ей проблему разрешения неоднозначности при работе с памятью (alias analysis). Т.е. если в программе есть аргументы указатели и/или используются глобальные переменные, то существует возможность того, что идет работа с одной и той же памятью через несколько различных объектов. Такая неопределенность мешает компилятору распознавать циклы, создает предполагаемые зависимости, мешающие выполнению цикловых оптимизаций, затрудняет анализ потока данных и т.д. Компилятор, зачастую, пытается решить такие проблемы, создавая многоверсионный код, т.е. вставляет в код проверки времени выполнения. Но это «утяжеляет» код и хорошо только для простых случаев, когда предполагаемых зависимостей мало, а что делать если неразрешенных вопросов много?

2. При передаче в функцию теряются многие свойства актуальных аргументов, которые могли бы оказать влияние на качество оптимизации. Например, информация о расположении объектов в памяти влияет на выигрыш от векторизации. Если актуальный аргумент константа, то ее протяжка внутрь функции также может вызвать упрощение выполняемых расчетов. Ну и т.д.

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

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

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

6. При статической линковке программа будет содержать избыточный код – неиспользуемые функции из исходников и библиотек.

Наверное, этот список можно продолжать.

Возникает желание собрать различные свойства функций и затем использовать их при оптимизации и обработке каждой конкретной функции. Собственно, это и является основной идеей межпроцедурного анализа. Для проведения такого анализа необходимо учитывать взаимоотношения всех участвующих в расчетах функций друг с другом. Понятно, что для того, чтобы установить свойства некой функции, необходимо проанализировать все функции, которые она вызывает и т.д. Например, в некоторых языках есть «чистые» функции (pure function) и вы завели, используете и вычисляете подобный аттрибут для всех функций. Pure функция не изменяет своих аргументов и каких-либо глобальных переменных и не выводит никакой информации. Понятно, что этот аттрибут для функции можно установить только если все вызываемые внутри этой функции функции являются pure.

Для отражения этих взаимовлияний и взаимоотношений используется граф вызовов (call graph). Его вершинами являются существующие функции, а гранями являются вызовы. Если функция foo вызывает bar, то соответствующие этим функциям вершины соединяются ребром. Поскольку вызовов может быть несколько, то и количество ребер может быть разным, то есть граф вызовов является мультиграфом.

IPA анализ работает со статическим графом, т.е. графом отражающим все возможные пути, которые могут быть пройдены при выполнении программы. Иногда при анализе производительности необходимо анализировать динамический граф вызовов, т.е. реальный путь, по которому управление передавалось при выполнении программы с каким-то конкретным набором данных.

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

Можно нарисовать примерно такую схему для двухпроходной и однопроходной схемы компиляции.

В случае когда программист задает опцию для включения межпроцедурных оптимизаций, компилятор делает лексический и синтаксический анализ каждого файла с исходными текстами и, если файл соответствует стандарту языка, то компилятор создает внутреннее представление и упаковывает его в объектный файл. Когда все необходимые файлы с внутренним представлением созданы, компилятор повторно их все изучает, собирает информацию о каждой функции, находит все вызовы внутри функций и строит граф вызовов. Анализируя граф вызовов, компилятор «протягивает» по нему различные свойства функций, анализирует свойства различных объектов и т.п. После этого производятся межпроцедурные оптимизации, которые изменяют граф вызовов или свойства объектов. (Я надеюсь, что спустя какое-то время соберусь и расскажу о самых интересных на мой взгляд оптимизациях подробнее.) Многие оптимизации применимы только в случае, если компилятору удается доказать, что выполняется генерация исполняемого файла, и граф вызовов содержит все функции программы. Такие оптимизации называются оптимизациями всей программы (whole program optimization). Примерами таких оптимизаций является удаление из графа вызовов отдельных функций или частей графа вызовов, в которые нельзя попасть из main (dead code elimination). Другим известным примером является изменение структур данных. Большинство межпроцедурных оптимизаций могут выполняться как для полного, так и неполного графа вызовов. Самой известной межпроцедурной оптимизацией является подстановка тела функции (inlining), подставляющей тело функции вместо ее вызова.

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

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

Итак, если использовать компилятор для создания объектного файла, например с опцией –с, то в зависимости от наличия или отсутствия опции –Qipo будут создаваться разные сущности. С -Qipo объектный файл — это упакованное внутреннее представление, а не обычный объектный файл. Такие файлы не поймут линковщик link и утилита для созания библиотек lib. Для работы с такими объектными файлами нужно использовать их расширенные Intel аналоги xilink и xilib. Библиотека, созданная из объектных файлов с внутренним представлением будет содержать секции с внутренним представлением и это значит, что те утилиты, которые она содержит, смогут принять участие в межпрпоцедурном анализе в тот момент, когда такая библиотека будет прилинковываться к приложению.(Естественно только с использованием интеловского компилятора и опции -Qipo.) Отсюда следует, что для того, чтобы получить максимальную выгоду от использования компилятора Intel и межпроцедурного анализа, необходимо использовать библиотеки, созданные с помощью компилятора Intel с использованием –Qipo. Чтобы межпроцедурный анализ мог работать с системными функциями, в компиляторе есть информация об этих функциях.

Кстати говоря, если по какой-то причине вы смешаете мух и котлеты, т.е. обычные объектные файлы и файлы собранные с –Qipo и вызовете для их обработки интеловский компилятор (icl), то ничего страшного не произойдет. Компилятор заметит, что вы передаете ему внутреннее представление и включит межпроцедурный анализ/оптимизации автоматом. IPA и IPO будут выполняться для неполного графа вызовов (т.е. графа вызовов, в котором есть неизвестные функции), в который войдут все функции, для которых есть внутреннее представление. Компилятор создаст объектные файлы и затем вызовет линковщик, чтобы прилинковать к ним обычные объектные файлы. Но в общем случае, попавший в сборку программы с –Qipo «обычный» объектный файл может отключить целый пласт оптимизаций, оптимизации целой программы (whole program optimizations).

Граф вызовов

Понятно, что межпроцедурные оптимизации не даются даром. Работа с графом вызовов может быть достаточно сложной и ресурсоемкой и многое определяется размерами графа. Ради интереса я посмотрел на известный тест на производительность из сьюта для измерения производительности CPU2006 447.dealII (это c++ приложение) и вывел информацию о количестве вершин графа вызовов перед началом межпроцедурного анализа. Получилось, что перед межпроцедурным анализом существовало примерно 320 000 различных функций и примерно 380 000 различных дуг, их связывающих. Большие проекты могут испытывать проблемы с использованием двухпроходной компиляции и межпроцедурным анализом.

В компиляторе Intel реализованы две различные модели межпроцедурного анализа, а именно однофайловая и многофайловая модель. Однофайловая включается по умолчанию, если не задан режим многофайловой межпроцедурной оптимизации. В описании опций это выглядит как-то так: