Содержание к диссертации
Введение
1 Трансформации индуктивных переменных 13
1.1 Трансформации циклов 14
1.1.1 Автоматическая параллелизация 14
1.1.2 Распознавание циклов-идиом 15
1.1.3 Перестановка циклов 15
1.1.4 Снижение стоимости индуктивных выражений 16
1.1.5 Развертка циклов 17
1.2 Индуктивные переменные и выражения 18
1.2.1 Преобразование типов индуктивных переменных 21
1.2.2 Деление индуктивного выражения на константу 21
1.3 Символьное представление индуктивных выражений 22
1.3.1 С-функция 22
1.3.2 Каноническая форма С-функции 25
1.3.3 Линейные С-функции 27
1.4 Подстановка индуктивных переменных 27
1.4.1 Подстановка точек модификации 27
1.4.2 Вычисление количества итераций цикла 28
1.4.3 Подстановка индуктивных переменных 30
1.5 Снижение стоимости 30
1.6 Другие реализации алгоритмов . 33
1.6.1 Идентификация индуктивных переменных 34
1.6.2 Снижение стоимости индуктивных выражений 34
1.6.3 Подстановка индуктивных переменных 35
1.7 Результаты 36
1.8 Выводы 38
2 Нормализация структуры управляющей переменной цикла 40
2.1 Использование беззнакового типа 44
2.2 Использование оператора != в условии цикла 46
2.3 Использование оператора постинкремента '.. 49
2.4 Использование глобальной переменной в качестве верхней границы . 52
2.5 Порядок нормализации циклов 55
2.6 Ограничения применения специализации кода 57
2.7 Результаты 58
2.8 Выводы 61
3 Профилирование значений выралсений для специализации кода 63
3.1 Специализация кода по конкретным значениям инвариантов 65
3.2 Профилирование значений выражений 68
3.2.1 Инструментирование программы 68
3.2.2 Использование результатов инструментирования 72
3.3 Результаты 73
3.4 Выводы 76
Заключение 78
Приложение. Внутренняя структура компилятора фирмы Sun 80
Список литературы 83
- Снижение стоимости индуктивных выражений
- Подстановка индуктивных переменных
- Использование глобальной переменной в качестве верхней границы .
- Использование результатов инструментирования
Введение к работе
Актуальность темы. С момента появления вычислительной техники и по сегодняшний день скорость выполнения программ была и остается важной темой исследований. Один из наиболее эффективных методов увеличения скорости работы программ — использование оптимизирующих компиляторов. Увеличение мощности современных компьютеров приводит не только к ускорению выполнения программ, но и к появлению новых возможностей, в том числе и для оптимизирующих компиляторов. Кроме того, изменение архитектуры процессоров приводит к необходимости создания новых и переработки уже имеющихся методов автоматической оптимизации.
На форуме Intel для разработчиков (Intel Developer Forum, IDF), прошедшем 2-го октября 2002-го года в Москве, были названы девять основных факторов повышения производительности при использовании компиляторов Intel [11]. Среди них:
1. программная конвейеризация (software pipelining) для архитектуры Itanium,
2. автопараллелизация (autoparallelization) и
3. оптимизация по профилированию (profile guided optimization, PGO).
Программная конвейеризация — это такая трансформация циклов, которая позволяет наиболее эффективно использовать параллелизм уровня команд в большинстве современных микропроцессоров, в том числе, например, в Sun ULTRASparc™ IIICu или Intel Itanium™.
Автопараллелизация — это семейство оптимизирующих трансформаций, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управления (threads). Наиболее распространенное применение автопараллелизации — автоматическая параллелизация циклов. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур, в том числе и псевдо-мультипроцессорных (например, системы HyperThreading фирмы Intel).
Оптимизация по профилированию — это многофазная схема оптимизации программ, состоящая из инструментирования программы, пробного прогона на характерном наборе данных и последующего использования полученной статистики при финальной компиляции. Оптимизация по профилированию позволяет правильно предсказывать переходы, находить критические пути исполнения, оценивать число итераций циклов и выявлять те участки программы, к которым следует применять наиболее агрессивные оптимизации.
Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по оптимизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы ([20], [13, §10.2]), и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов.
Основы оптимизирующего компилятора фирмы Sun для платформы SPARC закладывались в начале восьмидесятых годов прошлого века с использованием самых современных (на тот момент) технологий, а один из создателей этого компилятора, Steven Muchnick, позднее написал книгу [41], которая по праву считается одной из фундаментальных работ по компиляторам. Практически с самого начала существования данного компилятора в нем были реализованы многие классические трансформации циклов, такие, например, как вынос инвариантов цикла и снижение стоимости индуктивных выражений. С момента своего создания и по сегодняшний день компилятор фирмы Sun активно развивается — за последние годы в нем появились такие важные трансформации, как программная конвейеризация и автоматическая параллелизация, а также многие другие.
Однако, с развитием компилятора становилось очевидно, что алгоритмы, заложенные при его создании, уже перестали удовлетворять все возрастающие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимизацию, изученную подробнее, чем снижение стоимости: она описана во многих книгах по компиляторам ([13, §10.2], [41, §14.1.2],
[17, §6.2.3]) и, без сомнения, так или иначе реализована во всех промышленных оптимизирующих компиляторах.
Тем не менее, новый алгоритм снижения стоимости, разработанный в рамках данной диссертационной работы, интересен как минимум по двум причинам.
Во-первых, этот алгоритм разработан не только как теоретическое построение, но и внедрен в работающий компилятор с его заданной структурой представления программы, при этом за то же время выполняет существенно большее число трансформаций, чем предыдущий алгоритм, реализованный в компиляторе Sun.
Во-вторых, в основу данного алгоритма снижения стоимости положен такой механизм символьного анализа индуктивных переменных и индуктивных вьфажений, который применим для очень широкого класса оптимизаций и точного аналога которому автор не нашел в известной ему литературе.
После успешного внедрения в компилятор механизма символьного анализа индуктивных вьфажений было решено применить данный механизм для реализации еще одной оптимизирующей трансформации — подстановки индуктивных переменных. Данная оптимизация, необходимая в первую очередь для параллелизации циклов, достаточно изучена, однако ее прежняя реализация не позволяла охватить ряд важных случаев. Применение символьного анализа к индуктивным переменным позволило существенно расширить множество обрабатываемых случаев, сохранив прежнее время компиляции.
В процессе работы над алгоритмами трансформации индуктивных переменных и в ходе исследования результатов их работы было обнаружено большое количество таких циклов, которые нельзя было трансформировать из-за неправильной структуры управляющей переменной цикла. Зачастую неправильная структура управляющей переменной цикла являлась следствием применения некоторых конструкций языка Си (и Си++), например, использования глобальной переменной в качестве верхней границы цикла или оператора неравенства для проверки условия выхода из цикла. Вероятно, подобные проблемы хорошо известны многим разработчикам компиляторов, однако они очень мало освещены в литературе и не были практиче ски решены в компиляторе Sun.
В диссертационной работе предлагается метод нормализации структуры цикла с использованием специализации кода, то есть при помощи дублирования цикла и вставки в код динамической проверки определенных условий. Реализация данного метода широко использует механизм символьного анализа индуктивных переменных, упомянутый выше.
Еще одно применение специализации кода основано на использовании так называемого профиля значений, т. е. статистической информации, полученной в результате пробного запуска программы и позволяющей предсказать наиболее вероятные значения тех или иных переменных и выражений. Так, имея подробную информацию о возможных значениях некоторого инварианта цикла, можно произвести специализацию кода и подставить значение данного инварианта в одну из копий цикла. Во многих промышленных компиляторах реализованы методы использования различной профильной информации (самыми расіїространенньїми типами такой информации следует назвать профиль переходов и профиль вызовов виртуальных функций). Однако профили значений выражений не нашли пока применения в большинстве компиляторов в силу крайне низкой скорости сбора статистики о значениях вьфажений. В большинстве работ по профилированию выражений упоминается замедление работы профилируемых программ на два порядка и более. В рамках диссертационой работы был разработан и реализован метод профилирования значений, замедляющий профилируемые программы всего лишь на несколько процентов, вместо десятков раз. Данный "быстрый" метод позволяет собирать статистику несколько иного рода, чем ранее известные "медленные" методы. Это дает возможность не только собрать бблыпую часть информации о значениях выражений, доступной при использовании других методов, но также получить информацию о взаимозависимости значений различных выражений.
Актуальность диссертационой работы обусловлена тем, что все исследованные методы оптимизации позволяют существенно повысить скорость выполнения программ.
Целью диссертационной работы является разработка новых и модификация имеющихся методов и алгоритмов оптимизации программ, связанных с программной конвейеризацией и автопараллелизацией, а также использующих профилирование. Исходя из поставленной цели, в диссертационной работе решаются следующие задачи:
• разработка нового алгоритма снижения стоимости для индуктивных переменных, позволяющего в ряде случаев улучшить возможности последующей программной конвейеризации;
• разработка нового алгоритма подстановки индуктивных переменных, увеличивающего возможности автопараллелизации;
• анализ и частичное решение проблем, связанных с "нестандартными" управляющими переменными циклов в языках С и C++;
• создание методов профилирования значений для последующей специализации кода.
Предмет исследования составляют различные аспекты разработки и реализации алгоритмов оптимизации программ:
• разработка эффективных алгоритмов идентификации, анализа и трансформации индуктивных переменных;
• разработка эффективных методов профилирования значений и выбора участков кода для специализации;
• оценка конечной производительности оптимизированного кода.
Методы исследования заимствованы из областей системного программирования, технологии компиляции, символьной алгебры и теории графов. Эффективность разработанных алгоритмов и конечная производительность программ оценивались путем замера времени исполнения ряда тестовых программ, в первую очередь SPEC CPU2000, на двухпроцессорной рабочей станции SunBlade™ 1000.
Тестовый набор SPEC CPU2000 ([56]) — это международно признанный пакет тестов для оценки производительности вычислительных систем, состоящий из двух частей: набор программ, использующих преимущественно целочисленную арифметику (SPECint2000) и набор программ, использующих в основном арифметику с плавающей запятой (SPECfp2000). Пакет содержит в общей сложности 26 программ (12 в SPECint2000 и 14 в SPECfp2000), представляющих различные сферы применения языков программирования Си, Си++, Фортран 77 и Фортран 90, таких как: архивация данных, компьютерная графика и распознавание образов, компиляция и интерпретация языков программирования, теория чисел, базы данных, искусственный интеллект (игра в шахматы), физика, химия, метеорология и др. Для каждой программы из тестового пакета имеется три набора входных данных: test — малый набор данных, используемый для проверки работоспособности теста, train — набор данных среднего размера, используемый для пробного запуска при многофазной схеме компиляции и ref — большой набор данных, используемый для измерения времени работы программы. Кроме пакета SPEC CPU2000, в процессе анализа и тестирования разработанных алгоритмов использовались тесты SPEC CPU95, bench++ и другие.
Основной целью при анализе тестов SPECint2000 и SPECfp2000 являлось изучение не конкретных программ и циклов, а свойств, характерных для этих классов задач в целом. В этой связи в диссертации не приводятся имена конкретных программ, на которых был получен выигрыш в производительности.
Научная новизна работы заключается в создании новых методов анализа и автоматической оптимизации программ, а именно:
• в разработке методов идентификации и символьного анализа индуктивных переменных;
• в описании и анализе различных разновидностей "нестандартных" управляющих переменных цикла и возможностей их трансформации;
в разработке быстрого метода профилирования значений с целью последую щей оптимизации кода.
Практическая ценность работы. Разработанные алгоритмы были реализованы в рамках промышленного оптимизирующего компилятора фирмы Sun для платформы SPARC (поддерживает языки Си, Си++, Фортран 77, Фортран 90) и показали прирост производительности на ряде реальных программ. Ббльшая часть разработанных алгоритмов имеет платформо- и язьпсо-независимый характер, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.
Основные научные и практические результаты, выносимые на защиту
В диссертационной работе представлены следующие результаты:
• 1. Новые алгоритмы анализа и трансформации индуктивных переменных: символьный анализ индуктивных переменных;
• снижение стоимости индуктивных переменных и выражений;
• подстановка индуктивных переменных.
2. Исследование проблемы "нестандартных" управляющих переменных и методы ее решения: применение специализации кода и интервального анализа для нормализации управляющих переменных.
3. Новые алгоритмы специализации кода, основанные на профилировании значений:
• анализ возможных точек профилирования;
• метод быстрого профилирования конкретных значений сразу нескольких переменных или выражений;
• специализация кода по полученной статистике значений переменных и выражений.
Все разработанные алгоритмьГреализованы автором в оптимизирующем компиляторе фирмы Sun и успешно прошли этап опытной эксплуатации в фирме Sun и в ЗАО "МЦСТ", дав хорошие результаты и продемонстрировав высокую надежность методов. Часть алгоритмов включена в версию компилятора, поставляемого с мая 2003 года, другую часть планируется включить в коммерческую версию компилятора, готовящуюся к выпуску в середине 2005 года.
Публикации
По теме диссертации опубликовано шесть работ:
1. И. Л. Дьячков, К. С. Серебряный. Профилирование значений выражений для оптимизации программ // XXIX Гагаринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, 2003. С. 20-21 ([1]).
2. К. С. Серебряный. Методы оптимизации программ, использующие дублирование кода // Новые материалы и технологии. Тезисы докладов Всероссийской научно-технической конференции, Т. 3, 2002. С. 40-41 ([2]).
3. К. С. Серебряный. Трансформации циклов, производимые оптимизирующими компиляторами // Современные проблемы фундаментальных и прикладных наук. Научная конференция МФТИ. Часть I: Радиотехника и кибернетика. Москва-Долгопрудный, 2002. С. 42-43 ([3]).
4. К. С. Серебряный. Способ оптимизации программ с использованием раскрутки циклов // Информационные технологии 2003, N 1. С. 12-15 ([4]).
5. К. С. Серебряный. Трансформации циклов, содержащих индуктивные переменные // Информационные технологии 2003, N 9. С. 22-29 ([5]).
6. К. С. Серебряный. Нормализация структуры циклов // XXX Гагаринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, 2004. С. 56 ([б]).
Апробация ""
Результаты работы докладывались на научных конференциях:
1. Всероссийская научно-техническая конференция "Новые материалы и технологии", Москва 2002;
2. Научная конференция МФТИ, Москва-Долгопрудный 2002;
3. XXIX и XXX Международная молодежная научная конференция Тагарин-ские чтения" (Москва 2003 и 2004); а также на научных и технических семинарах ЗАО "МЦСТ" и ИМВС РАН и в электронном форуме по методам реализации компиляторов фирмы Sun.
Краткое содержание работы
В главе 1 описывается ряд характерных трансформаций циклов, содержащих индуктивные переменные, и предлагаются новые алгоритмы анализа индуктивных переменных. На основе предложенных алгоритмов анализа индуктивных переменных описываются два метода трансформации циклов: а) снижение стоимости индуктивных выражений и б) подстановка индуктивных переменных.
В главе 2 описаны несколько характерных для языков Си и Си++ проблем, связанных со структурой управляющих переменных: а) использование беззнакового целого типа для управляющей переменной, б) применение операторов неравенства и постинкремента в условии выхода из цикла и в) случаи использования глобальных переменных в качестве верхней границы цикла. Предложены способы решения этих проблем при помощи специализации кода.
В главе 3 рассматривается применение специализации кода к циклам, содержащим инварианты, значения которых можно предсказать при помощи профилирования значений. Описывается новый быстрый метод профилирования значений.
В заключении суммируются полученные практические и теоретические результаты.
-1 В приложении дается краткое описание внутренней структуры компилятора фирмы Sun и показывается расположение реализованных оптимизаций в этом компиляторе.
Снижение стоимости индуктивных выражений
Индуктивные переменные (т. е. переменные, изменяющиеся на фиксированную величину за каждую итерацию цикла)1 играют ключевую роль во многих трансформациях циклов. В большинстве случаев цикл содержит т. н. управляющую переменную — индуктивную переменную, определяющую количество итераций цикла. В таблице 1 приведено приблизительное количество циклов в программах пакета SPEC CPU2000, а) содержащих управляющую переменную, б) не содержащих управляющую переменную, но имеющих другие индуктивные переменные, и в) циклов, не имеющих индуктивных переменных.
Автором работы предлагается метод символьного анализа индуктивных переменных и выражений, в том числе и управляющих переменных, позволяющий получить полную информацию о структуре индуктивных выражений и произвести над ними различные трансформации. Две таких трансформации — снижение стоимости индуктивных выражений и подстановка индуктивных переменных, разработанные автором в рамках диссертационной работы — также описываются в данной главе. Реализации этих трансформаций были внедрены в компилятор Sun, заняв место предыдущих реализаций этих же трансформаций, что позволило улучшить качество создаваемого кода. Описание и сравнительный анализ прежних алгоритмов приводятся в разделе 1.6, а в разделе 1.7 представлены практические результаты применения новых алгоритмов по сравнению со старыми. Кроме алгоритмов снижения стоимости и подстановки индуктивных переменных, приведенные методы символьного анализа использованы в алгоритмах нормализации управляющей переменной (глава 2) и других фазах компилятора.
В современных оптимизирующих компиляторах реализованы десятки или даже сотни различных трансформаций циклов. В этом разделе будет дано краткое описание лишь нескольких трансформаций, которые, по мнению автора, являются наиболее характерными трансформациями циклов с индуктивными переменными и вместе с тем важны для понимания целей анализа индуктивных переменных. Данные примеры нам понадобятся также в главе 2, где обсуждаются проблемы с "неправильными" управляющими переменными. Эти и множество других трансформаций циклов подробно описаны в обзорной статье [17].
Если все итерации цикла могут выполняться независимо или могут быть разделены на независимые подмножества, компилятор может создать распараллеленную версию цикла, т. е. несколько независимых частей цикла будут выполняться одновременно в различных потоках (threads).
В данном примере для проведения автоматической параллелизации необходимо проанализировать структуру управляющей переменной і и индуктивных выражений а [і] и b [і]. Для данного примера, как и для некоторых других, анализ зависимости данных (data dependence analysis) является не менее важной частью анализа трансформации, однако он выходит за рамки данной работы. Вопросы, связанные с анализом зависимости данных, подробно изложены, например, в книге [20].
Некоторые циклы могут быть заменены на вызовы библиотечных процедур (это особенно важно, если код компилируется для семейства различных процессоров с общей системой команд, и имеется библиотека функций, оптимизированных для каждого типа процессора) или реализованы с помощью машинных идиом (для векторных компьютеров).
Достаточно часто несколько циклов вложены один в другой таким образом, что единственным оператором внешнего цикла является внутренний цикл. Такие наборы циклов называют идеальными гнездами (perfect nests).
В некоторых случаях перестановка местами двух циклов (при условии сохранения смысла программы) может увеличить скорость вьшолнения программы за счет увеличения локальности памяти. приведенном примере элементы массива а используются в следующем порядке:
Если переставить местами эти два цикла (что в данном случае не изменит смысла программы) , то элементы массива а будут использоваться последовательно2.
Кроме уменьшения шага, с которым считываются элементы массива, перестановка циклов может улучшить программу за счет: а) выноса большего количества инвариантов из внутреннего цикла, или б) переноса наиболее длинного цикла внутрь (например, для векторизации), или в) выноса наружу цикла с независимыми итерациями (например, для последующей параллелизации). Однако необходимо иметь в виду, что, улучшив один из параметров цикла, мы можем ухудшить другой.
Снижение стоимости (strength reduction) — это трансформация, заменяющая дорогие операции на аналогичные, но более дешевые. Так, например, в случае с индуктивными выражениями есть возможность заменить операцию умножения на операцию сложения3.
Даже в тех случаях, когда умножение стбит не дороже сложения (например, умножение на степень двойки, которое можно реализовать через сдвиг влево), эта трансформация приносит пользу, так как дает возможность лучше отработать другим трансформациям, например, планировщику (scheduler).
Циклы 1 и 2 эквивалентны, но итерация второго цикла не имеет зависимых операций (в первом цикле запись можно выполнять только после операции i«3), что увеличивает возможности планировки (scheduling) тела цикла.
Развертка циклов (loop unrolling) заключается в создании нескольких копий итерации цикла (число копий п называется фактором развертки) и в увеличении шага цикла в это же число раз. После развернутого цикла (или перед ним) необходимо произвести оставшиеся итерации (не более п-1).
Основная польза развертки цикла заключается в увеличении числа команд, которые можно вьшолнить одновременно; кроме этого, уменьшаются затраты на управление циклом и появляется больше возможностей для других оптимизаций.
Подстановка индуктивных переменных
Дано: две точки модификации тмі и тм2, находящиеся на главном пути. Необходимо: заменить тм2 на тмі во всех С-функциях. 1 Для всех индуктивных выражений, С-функции которых содержат тм2 1.1 Если данное выражение находится до или после8 обеих точек модификации, заменить тм2 на тмі в С-функции данного выражения. 1.2 Если выражение.находится после тм2 и до тмі — заменить тм2 на тм1+1. 1.3 Если выражение находится после тмі и до тм2 — заменить тм2 на тм1-1. При подстановке индуктивных переменных необходимо не только выразить все (какие возможно) индуктивные переменные через управляющую переменную, но и исключить из цикла все точки модификации подставленных индуктивных переменных. Для этого нам понадобится следующий алгоритм: Алгоритм 5 вычисление числа итераций цикла Дано: цикл типа while (или for), имеющий управляющую переменную (см. определение 4) с константным шагом шаг, начальным значением нг и верхней границей вг. Необходимо: непосредственно перед началом цикла вычислить количество итераций N. Количество итераций будет вычисляться по следующей таблице: Обработка некоторых видов индуктивных выражений не реализована на данный момент, но может быть добавлена к существующим алгоритмам при минимальных затратах. Среди неподдерживаемых индуктивных выражений — циклические, полиномиальные, геометрические ИП (см. [33]), а также операции деления (общий случай) и взятия остатка от деления, примененные к ИП (см. [48])9.
Алгоритмы анализа и трансформаций индуктивных переменных давно и активно исследуются ([17, 6.2.3]), и поэтому достаточно трудно разработать что-либо принципиально новое. С теоретической точки зрения, алгоритмы анализа индуктивных выражений, приведенные в этой главе, имеют большое сходство с другими алгоритмами (например, [29, 36]). Наиболее важное отличие нового метода — привязка значения индуктивного выражения к точкам модификации индуктивных переменных, а не к номеру итерации цикла, как в других методах. Подобный подход позволяет существенно облегчить анализ взаимосвязи индуктивных переменных. Кроме того, следует заметить, что в известных автору работах не исследуются следующие моменты: случай нескольких присваиваний индуктивной переменной; взаимосвязь между различными индуктивными переменными (при снижении стоимости); преобразование типов индуктивных выражений.
Автору представляется немаловажным тот факт, что разработанные им алгоритмы удалось внедрить в сложную структуру работающего компилятора, тем самым добавив в этот компилятор ряд новых качеств. Ниже будут описаны основные отличия новых алгоритмов, от алгоритмов, реализованных ранее в компиляторе Sun. Алгоритм идентификации индуктивных переменных, использовавшийся в прежнем алгоритме снижения стоимости (равно как и в прежнем алгоритме подстановки индуктивных переменных), очень похож на алгоритм 1, однако большим недостатком прежней реализации являлось то, что не использовалась информация о потоке данных, а обрабатывались только локальные переменные, адреса которых не брались. Таким образом, старый алгоритм поиска индуктивных переменных сужал множество обрабатываемых переменных, не рассматривая случаи, когда индуктивная переменная является глобальной, когда ее адрес берется вне цикла или когда переменная является полем в структуре. Кроме того, рассматривались только индуктивные переменные с одним присваиванием 10. Старый алгоритм снижения стоимости работал по итеративному принципу, т. е. последовательно выполнял преобразования индуктивных выражений. Вот его грубое описание. Алгоритм 8 старый алгоритм снижения стоимости (для одного цикла) 1 Найти индуктивные переменные. 2 Для всех индуктивных переменных і, имеющих начальное значение І0 и шаг s: 2.1 Для всех выражений вида (i+A) M, где М и А — инварианты цикла, создать новую индуктивную переменную с начальным значением (іО+А) М и шагом s M. Для всех выражений (i+A) M с одинаковым М создавать только одну новую беременную. Заменить данное выражение на новую переменную и внести ее в список индуктивных переменных. 3 Если на шаге 2.1 были созданы новые индуктивные переменные, вернуться к шагу 2.
Данный алгоритм имеет следующие недостатки, устраненные в новом алгоритме: в процессе работы алгоритма часто создаются временные переменные, которые затем не используются; никак не учитывается взаимосвязь между различными индуктивными переменными; никак не обрабатываются операторы деления индуктивного выражения на константу; Кроме того, итеративная природа алгоритма привела к различным проблемам в его реализации: алгоритму не всегда удается создать минимальное количество новых индуктивных переменных, то есть создается две или более индуктивных переменных для выражений, которые на самом деле отличаются на аддитивную константу; осложнена и в результате практически не реализована обработка операторов преобразования типа, примененных к индуктивным выражениям, что особенно важно при компиляции для 64-битной платформы;
Использование глобальной переменной в качестве верхней границы .
Для данного примера компилятор далеко не всегда сможет определить, что запись по указателю а не может изменить значения переменной N. Таким образом, переменная N не может считаться инвариантом и переменная і не удовлетворяет определению управляющей переменной 4. В данном случае в условии выхода из цикла используется результат считывания из памяти, что также не позволяет называть переменную і управляющей, поскольку значение выражения c- N может быть изменено через указатель а. Практика показывает, что в большинстве случаев, подобных примерам 21 и 22, верхняя граница на самом деле остается неизменной15. И в некоторых случаях этот факт можно проверить во время исполнения программы. Так, в примере 22 достаточно проверить, что адрес &(c- N) не входит в промежуток [a, a+c- N]. В примере 21 достаточно произвести аналогичную проверку для адреса переменной 15 N и интервала адресов [a, a+N].
В качестве верхней границы цикла может выступать арифметическое выражение, содержащее глобальную переменную или считывание из памяти, например, whiled = N+1) или while(i = c- N/2). Для удобства изложения дадим следующие определения: Определение 9 Полуинвариантой переменной цикла назовем переменную, не изменяемую в цикле явно, но, возможно, изменяемую неявно (см. пример 21). Определение 10 Полуинвариантным считыванием назовем считывание из инвариантного адреса А, такого, что цикл не содержит явной записи по этому адресу, но содержит другие операторы, имеющие возможностъ произвести запись по адресу А (см. пример 22). Определение 11 Полуинвариантом цикла назовем арифметическое выражение, составленное из инвариантов (определение 1), полуинвариантных переменных (определение 9) и полуинвариантных считываний (определение 10). Примеры 22 и 21 молено обобщить следующим образом. Цикл L содержит полуинвариант U. Если определить, что U является инвариантом, то цикл L будет иметь управляющую переменную (удовлетворяющую определению 4), a U будет верхней границей. Все операторы, которые могут изменить значение U, имеют вид (линейное индуктивное выражение)=..., т. е. являются операторами записи в память, адрес которой является выражением, линейным по управляющей переменной. Таким образом, для всех этих операторов можно вычислить интервал адресов, по которым производиться запись. Затем для каждой полуинвариантной переменной N, входящей в U, проверить, что адрес &N не входит ни в один из вычисленных интервалов.
Аналогичную проверку произвести для полуинвариантных считываний, содержащихся в U. Оптимизация, подобная примеру 23, является частным случаем динамического разрешения конфликтов по доступу в память (dynamic memory disambiguation, DMD, run time memory disambiguation). Как будет показано в разделе 2.7, замена полуинвариантной верхней границы на инвариант дает возможность выполнить другие виды динамического разрешения конфликтов по доступу в память, что и является основной причиной получения заметного вьшгрьппа в производительности. Динамическое разрешение конфликтов по доступу в память (DMD) Некоторые методы DMD используют специфическую аппаратную поддержку, недоступную в процессорах SPARC (см., например, [32], [39]). Наиболее распространенный и простой вид DMD, не требующий специальной аппаратной поддержки, — это проверка непересечения двух (или более) интервалов памяти перед началом цикла ([46]). Предположим, что в данном примере компилятору неизвестно, пересекаются или нет интервалы [а, а + 4п), [6,6 + 4л) и [с, с -+- 4). Если проводить оптимизацию на уровне исходного кода на языке Си (точнее, на языке Си99, [15], который имеет ключевое слово restrict, означающее, что два помеченных этим словом указателя ссылаются на непересекающиеся интервалы памяти), то получится такая программа: Для такого цикла, в отличие от исходного, становится возможным целый ряд оптимизирующих преобразований (в том числе, автопараллелизация). Данная оптимизация возможна только в том случае, если цикл имеет управляющую переменную, а все операторы записи изменяют содержимое памяти, адрес которой является выражением, линейным по управляющей переменной (то же самое условие необходимо для замены полуинвариантной верхней границы на инвариантную). Нередко встречаются циклы имеющие одновременно несколько свойств, неудобных для оптимизации. Например, Применение специализации кода для каждого "неудобного" свойства в отдельности может привести к появлению большого количества специализрованных копий цикла, что, конечно, существенно ухудшит код. Более выгодным представляется создание только одной специализированной копии цикла и одной динамической проверки. Для приведенного примера можно было бы сделать следующую специализацию:
Использование результатов инструментирования
Случай, рассмотренный в данной главе (инвариант цикла, часто принимающий одно и то же значение) оказался наиболее характерен для пяти программ из тесто вого набора SPEC CPU2000 (все из SPECfp200017). В таблице 11 приведено количество точек профилирования, созданных компилятором на этих пяти программах (в процессе инструментирования), и количество произведенных специализаций кода (по результатам полученного профиля). Каждая точка профилирования собирает статистику по одному или нескольким выражениям одновременно.
Каждая специализации также производится по значениям одного или нескольких выражений. Количество выражений также отражено в таблице. Для оценки полезности трансформации кода помимо уравнения (4) использовалась "запрещающая" эвристика Проведенные эксперименты показали, что при использовании профилирования значений время исполнения инструментированной программы увеличивается менее чем на 10% (см таблицу 12). В той же таблице приведена статистика по увеличению времени компиляции и размеру кода, а в таблице 13 — полученное ускорение (см. также рис. 2). Уменьшение скорости работы одного из тестов объясняется (как и в предыдущей главе, см. 2.7) различием между профилями для входных данных train и ref. Для входных данных train специализация кода на основе профиля, полученного на этих же данных, позволяет получить около 2% ускорения. В данной главе представлен лишь один частный случай применения профилирования конкретных значений выражений — специализация циклов по значениям инвариантов. В дальнейшем возможно существенно расширить область применения профилирования значений. Перечислим несколько возможных вариантов применения профилирования значений: Профилирование значений операндов "дорогих" операций (таких, как деление), не обязательно являющихся инвариантами охватывающего цикла, — позволит производить снижение стоимости "дорогих" операций. Профилирование предикатов, связанных с разрешением конфликтов по доступу в память (стр. 2.4), — позволит производить специализацию кода только в тех случаях, когда это действительно необходимо.
Профилирование предикатов, связанных с запоминанием результатов вызо Предложен метод профилирования значений, не составляющий полного профиля выражения, а только собирающий статистику для некоторых конкретных возможных значений выражения. Такой подход позволяет создавать очень быстрый инструментирующий код. Простота профилирования конкретных значений позволяет дополнительно собирать информацию о взаимосвязи значений нескольких выражений, что дает возможность проводить специализацию кода сразу для нескольких переменных (или выражений). Основным практическим результатом данной главы является реализация описанных методов профилирования значений для специализации циклов.
Эти методы позволили получить большое увеличение производительности реальных программ (до 10% на тестах пакета SPEC CPU2000). Специализация кода по профилю значений может стать причиной снижения производительности, если данные для пробного запуска программы подобраны неверно или если компилятор использует неверные эвристики для оценки полезности специализации. Эксперименты, проведенные в рамках данной работы, показали, что подобранные эвристики дают хорошие результаты при использовании адекватных данных для пробного запуска.
