Метод высокоуровневой оптимизации циклов(Диссертация)

ЗАО “МЦСТ” УДК 004.4’416 На правах рукописи

Серебряный Константин Сергеевич МЕТОДЫ ВЫСОКОУРОВНЕВОЙ ОПТИМИЗАЦИИ ЦИКЛОВ 05.13.11 - “Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей”

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель к.т.н. с.н.с Волконский Владимир Юрьевич

Москва - 2004

Содержание Содержание

1

Введение

3

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-

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

Список примеров

89

Список иллюстраций

91

Список таблиц

91

-2-

Введение Актуальность темы. С момента появления вычислительной техники и по сегодняшний день скорость выполнения программ была и остается важной темой исследований. Один из наиболее эффективных методов увеличения скорости работы программ — использование оптимизирующих компиляторов. Увеличение мощности современных компьютеров приводит не только к ускорению выполнения программ, но и к появлению новых возможностей, в том числе и для оптимизирующих компиляторов. Кроме того, изменение архитектуры процессоров приводит к необходимости создания новых и переработки уже имеющихся методов автоматической оптимизации. На форуме Intel для разработчиков (Intel Developer Forum, IDF), прошедшем 2-го октября 2002-го года в Москве, были названы девять основных факторов повышения производительности при использовании компиляторов Intel [11]. Среди них: 1. программная конвейеризация (software pipelining) для архитектуры Itanium, 2. автопараллелизация (autoparallelization) и 3. оптимизация по профилированию (profile guided optimization, PGO). Программная конвейеризация — это такая трансформация циклов, которая позволяет наиболее эффективно использовать параллелизм уровня команд в большинстве современных микропроцессоров, в том числе, например, в Sun ULTRASparcTM IIICu или Intel ItaniumTM . Автопараллелизация — это семейство оптимизирующих трансформаций, позволяющих запускать последовательные независимые участки программы параллельно в нескольких потоках управления (threads). Наиболее распространенное применение автопараллелизации — автоматическая параллелизация циклов. Автопараллелизация позволяет эффективно использовать преимущества мультипроцессорных архитектур, в том числе и псевдо-мультипроцессорных (например, системы HyperThreading фирмы Intel). -3-

Оптимизация по профилированию — это многофазная схема оптимизации программ, состоящая из инструментирования программы, пробного прогона на характерном наборе данных и последующего использования полученной статистики при финальной компиляции. Оптимизация по профилированию позволяет правильно предсказывать переходы, находить критические пути исполнения, оценивать число итераций циклов и выявлять те участки программы, к которым следует применять наиболее агрессивные оптимизации. Наиболее важные виды оптимизации не случайно связаны именно с оптимизацией циклов. Как отмечается во многих работах по оптимизирующим компиляторам, основное время исполнения большинства программ приходится именно на циклы ([20], [13, §10.2]), и поэтому оптимизации циклов уделяется наибольшее внимание при разработке компиляторов. Основы оптимизирующего компилятора фирмы Sun для платформы SPARC закладывались в начале восьмидесятых годов прошлого века с использованием самых современных (на тот момент) технологий, а один из создателей этого компилятора, Steven Muchnick, позднее написал книгу [41], которая по праву считается одной из фундаментальных работ по компиляторам. Практически с самого начала существования данного компилятора в нем были реализованы многие классические трансформации циклов, такие, например, как вынос инвариантов цикла и снижение стоимости индуктивных выражений. С момента своего создания и по сегодняшний день компилятор фирмы Sun активно развивается — за последние годы в нем появились такие важные трансформации, как программная конвейеризация и автоматическая параллелизация, а также многие другие. Однако, с развитием компилятора становилось очевидно, что алгоритмы, заложенные при его создании, уже перестали удовлетворять все возрастающие потребности. Среди прочего, возникла необходимость в разработке нового алгоритма снижения стоимости индуктивных выражений (далее для краткости: снижение стоимости). Вряд ли можно найти оптимизацию, изученную подробнее, чем снижение стоимости: она описана во многих книгах по компиляторам ([13, §10.2], [41, §14.1.2],

-4-

[17, §6.2.3]) и, без сомнения, так или иначе реализована во всех промышленных оптимизирующих компиляторах. Тем не менее, новый алгоритм снижения стоимости, разработанный в рамках данной диссертационной работы, интересен как минимум по двум причинам. Во-первых, этот алгоритм разработан не только как теоретическое построение, но и внедрен в работающий компилятор с его заданной структурой представления программы, при этом за то же время выполняет существенно большее число трансформаций, чем предыдущий алгоритм, реализованный в компиляторе Sun. Во-вторых, в основу данного алгоритма снижения стоимости положен такой механизм символьного анализа индуктивных переменных и индуктивных выражений, который применим для очень широкого класса оптимизаций и точного аналога которому автор не нашел в известной ему литературе. После успешного внедрения в компилятор механизма символьного анализа индуктивных выражений было решено применить данный механизм для реализации еще одной оптимизирующей трансформации — подстановки индуктивных переменных. Данная оптимизация, необходимая в первую очередь для параллелизации циклов, достаточно изучена, однако ее прежняя реализация не позволяла охватить ряд важных случаев. Применение символьного анализа к индуктивным переменным позволило существенно расширить множество обрабатываемых случаев, сохранив прежнее время компиляции. В процессе работы над алгоритмами трансформации индуктивных переменных и в ходе исследования результатов их работы было обнаружено большое количество таких циклов, которые нельзя было трансформировать из-за неправильной структуры управляющей переменной цикла. Зачастую неправильная структура управляющей переменной цикла являлась следствием применения некоторых конструкций языка Си (и Си++), например, использования глобальной переменной в качестве верхней границы цикла или оператора неравенства для проверки условия выхода из цикла. Вероятно, подобные проблемы хорошо известны многим разработчикам компиляторов, однако они очень мало освещены в литературе и не были практиче-

-5-

ски решены в компиляторе Sun. В диссертационной работе предлагается метод нормализации структуры цикла с использованием специализации кода, то есть при помощи дублирования цикла и вставки в код динамической проверки определенных условий. Реализация данного метода широко использует механизм символьного анализа индуктивных переменных, упомянутый выше. Еще одно применение специализации кода основано на использовании так называемого профиля значений, т. е. статистической информации, полученной в результате пробного запуска программы и позволяющей предсказать наиболее вероятные значения тех или иных переменных и выражений. Так, имея подробную информацию о возможных значениях некоторого инварианта цикла, можно произвести специализацию кода и подставить значение данного инварианта в одну из копий цикла. Во многих промышленных компиляторах реализованы методы использования различной профильной информации (самыми распространенными типами такой информации следует назвать профиль переходов и профиль вызовов виртуальных функций). Однако профили значений выражений не нашли пока применения в большинстве компиляторов в силу крайне низкой скорости сбора статистики о значениях выражений. В большинстве работ по профилированию выражений упоминается замедление работы профилируемых программ на два порядка и более. В рамках диссертационой работы был разработан и реализован метод профилирования значений, замедляющий профилируемые программы всего лишь на несколько процентов, вместо десятков раз. Данный “быстрый” метод позволяет собирать статистику несколько иного рода, чем ранее известные “медленные” методы. Это дает возможность не только собрать б´ольшую часть информации о значениях выражений, доступной при использовании других методов, но также получить информацию о взаимозависимости значений различных выражений. Актуальность диссертационой работы обусловлена тем, что все исследованные методы оптимизации позволяют существенно повысить скорость выполнения программ.

-6-

Целью диссертационной работы является разработка новых и модификация имеющихся методов и алгоритмов оптимизации программ, связанных с программной конвейеризацией и автопараллелизацией, а также использующих профилирование. Исходя из поставленной цели, в диссертационной работе решаются следующие задачи: • разработка нового алгоритма снижения стоимости для индуктивных переменных, позволяющего в ряде случаев улучшить возможности последующей программной конвейеризации; • разработка нового алгоритма подстановки индуктивных переменных, увеличивающего возможности автопараллелизации; • анализ и частичное решение проблем, связанных с “нестандартными” управляющими переменными циклов в языках С и C++; • создание методов профилирования значений для последующей специализации кода. Предмет исследования составляют различные аспекты разработки и реализации алгоритмов оптимизации программ: • разработка эффективных алгоритмов идентификации, анализа и трансформации индуктивных переменных; • разработка эффективных методов профилирования значений и выбора участков кода для специализации; • оценка конечной производительности оптимизированного кода. Методы исследования заимствованы из областей системного программирования, технологии компиляции, символьной алгебры и теории графов. Эффективность разработанных алгоритмов и конечная производительность программ оценивались путем замера времени исполнения ряда тестовых программ, в первую очередь SPEC CPU2000, на двухпроцессорной рабочей станции SunBladeTM 1000. -7-

Тестовый набор SPEC CPU2000 ([56]) — это международно признанный пакет тестов для оценки производительности вычислительных систем, состоящий из двух частей: набор программ, использующих преимущественно целочисленную арифметику (SPECint2000) и набор программ, использующих в основном арифметику с плавающей запятой (SPECfp2000). Пакет содержит в общей сложности 26 программ (12 в SPECint2000 и 14 в SPECfp2000), представляющих различные сферы применения языков программирования Си, Си++, Фортран 77 и Фортран 90, таких как: архивация данных, компьютерная графика и распознавание образов, компиляция и интерпретация языков программирования, теория чисел, базы данных, искусственный интеллект (игра в шахматы), физика, химия, метеорология и др. Для каждой программы из тестового пакета имеется три набора входных данных: test — малый набор данных, используемый для проверки работоспособности теста, train — набор данных среднего размера, используемый для пробного запуска при многофазной схеме компиляции и ref — большой набор данных, используемый для измерения времени работы программы. Кроме пакета SPEC CPU2000, в процессе анализа и тестирования разработанных алгоритмов использовались тесты SPEC CPU95, bench++ и другие. Основной целью при анализе тестов SPECint2000 и SPECfp2000 являлось изучение не конкретных программ и циклов, а свойств, характерных для этих классов задач в целом. В этой связи в диссертации не приводятся имена конкретных программ, на которых был получен выигрыш в производительности. Научная новизна работы заключается в создании новых методов анализа и автоматической оптимизации программ, а именно: • в разработке методов идентификации и символьного анализа индуктивных переменных; • в описании и анализе различных разновидностей “нестандартных” управляющих переменных цикла и возможностей их трансформации; • в разработке быстрого метода профилирования значений с целью последую-

-8-

щей оптимизации кода. Практическая ценность работы. Разработанные алгоритмы были реализованы в рамках промышленного оптимизирующего компилятора фирмы Sun для платформы SPARC (поддерживает языки Си, Си++, Фортран 77, Фортран 90) и показали прирост производительности на ряде реальных программ. Б´ольшая часть разработанных алгоритмов имеет платформо- и языко-независимый характер, что позволяет распространить их использование на максимально широкий класс процессорных архитектур и языков программирования.

Основные научные и практические результаты, выносимые на защиту В диссертационной работе представлены следующие результаты: 1. Новые алгоритмы анализа и трансформации индуктивных переменных: • символьный анализ индуктивных переменных; • снижение стоимости индуктивных переменных и выражений; • подстановка индуктивных переменных. 2. Исследование проблемы “нестандартных” управляющих переменных и методы ее решения: применение специализации кода и интервального анализа для нормализации управляющих переменных. 3. Новые алгоритмы специализации кода, основанные на профилировании значений: • анализ возможных точек профилирования; • метод быстрого профилирования конкретных значений сразу нескольких переменных или выражений; • специализация кода по полученной статистике значений переменных и выражений. -9-

Все разработанные алгоритмы реализованы автором в оптимизирующем компиляторе фирмы 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 ([6]).

-10-

Апробация Результаты работы докладывались на научных конференциях: 1. Всероссийская научно-техническая конференция “Новые материалы и технологии”, Москва 2002; 2. Научная конференция МФТИ, Москва–Долгопрудный 2002; 3. XXIX и XXX Международная молодежная научная конференция “Гагаринские чтения” (Москва 2003 и 2004); а также на научных и технических семинарах ЗАО “МЦСТ” и ИМВС РАН и в электронном форуме по методам реализации компиляторов фирмы Sun.

Краткое содержание работы В главе 1 описывается ряд характерных трансформаций циклов, содержащих индуктивные переменные, и предлагаются новые алгоритмы анализа индуктивных переменных. На основе предложенных алгоритмов анализа индуктивных переменных описываются два метода трансформации циклов: а) снижение стоимости индуктивных выражений и б) подстановка индуктивных переменных. В главе 2 описаны несколько характерных для языков Си и Си++ проблем, связанных со структурой управляющих переменных: а) использование беззнакового целого типа для управляющей переменной, б) применение операторов неравенства и постинкремента в условии выхода из цикла и в) случаи использования глобальных переменных в качестве верхней границы цикла. Предложены способы решения этих проблем при помощи специализации кода. В главе 3 рассматривается применение специализации кода к циклам, содержащим инварианты, значения которых можно предсказать при помощи профилирования значений. Описывается новый быстрый метод профилирования значений. В заключении суммируются полученные практические и теоретические результаты.

-11-

В приложении дается краткое описание внутренней структуры компилятора фирмы Sun и показывается расположение реализованных оптимизаций в этом компиляторе.

-12-

1

Трансформации индуктивных переменных Индуктивные переменные (т. е. переменные, изменяющиеся на фиксированную

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

с управляющей переменной

SPECint2000 SPECfp2000 Всего

3500 10200 13700

Количество циклов с другими индук- без индуктивных тивными перемен- переменных ными 4400 3100 1150 400 5550 3500

Автором работы предлагается метод символьного анализа индуктивных переменных и выражений, в том числе и управляющих переменных, позволяющий получить полную информацию о структуре индуктивных выражений и произвести над ними различные трансформации. Две таких трансформации — снижение стоимости индуктивных выражений и подстановка индуктивных переменных, разработанные автором в рамках диссертационной работы — также описываются в данной главе. Реализации этих трансформаций были внедрены в компилятор Sun, заняв место предыдущих реализаций этих же трансформаций, что позволило улучшить качество создаваемого кода. Описание и сравнительный анализ прежних алгоритмов приводятся в разделе 1.6, а в разделе 1.7 представлены практические результаты применения новых алгоритмов по сравнению со старыми. Кроме алгоритмов 1

Точные определения будут даны ниже.

-13-

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

1.1

Трансформации циклов

В современных оптимизирующих компиляторах реализованы десятки или даже сотни различных трансформаций циклов. В этом разделе будет дано краткое описание лишь нескольких трансформаций, которые, по мнению автора, являются наиболее характерными трансформациями циклов с индуктивными переменными и вместе с тем важны для понимания целей анализа индуктивных переменных. Данные примеры нам понадобятся также в главе 2, где обсуждаются проблемы с “неправильными” управляющими переменными. Эти и множество других трансформаций циклов подробно описаны в обзорной статье [17]. 1.1.1

Автоматическая параллелизация

Если все итерации цикла могут выполняться независимо или могут быть разделены на независимые подмножества, компилятор может создать распараллеленную версию цикла, т. е. несколько независимых частей цикла будут выполняться одновременно в различных потоках (threads). Пример 1. Автоматическая параллелизация double a [10000] , b [10000]; f o r (i = 0; i < 10000; i ++)

a[ i ] = sin (b[ i ]);

Здесь итерации можно разбить на два или более независимых множества и запустить полученные циклы одновременно в нескольких потоках: // поток 1 f o r (i = 0;

i < 5000; i ++)

a[ i ] = sin (b[ i ]);

// поток 2 f o r (i = 5000; i < 10000; i ++)

a[ i ] = sin (b[ i ]);

-14-

В данном примере для проведения автоматической параллелизации необходимо проанализировать структуру управляющей переменной i и индуктивных выражений a[i] и b[i]. Для данного примера, как и для некоторых других, анализ зависимости данных (data dependence analysis) является не менее важной частью анализа трансформации, однако он выходит за рамки данной работы. Вопросы, связанные с анализом зависимости данных, подробно изложены, например, в книге [20]. 1.1.2

Распознавание циклов-идиом

Некоторые циклы могут быть заменены на вызовы библиотечных процедур (это особенно важно, если код компилируется для семейства различных процессоров с общей системой команд, и имеется библиотека функций, оптимизированных для каждого типа процессора) или реализованы с помощью машинных идиом (для векторных компьютеров). Пример 2. Замена цикла на вызов memcpy() f o r (i = 0; i < n ; i ++) a[ i ] = b[i ];

можно заменить на memcpy (a ,b , n* s i z e o f (a [0]));

1.1.3

Перестановка циклов

Достаточно часто несколько циклов вложены один в другой таким образом, что единственным оператором внешнего цикла является внутренний цикл. Такие наборы циклов называют идеальными гнездами (perfect nests). Пример 3. Идеальное гнездо циклов f o r (i = 0; i < n ; i ++) f o r (j = 0; j < m ; j ++) a [j *n+ i ] += i + j ;

В некоторых случаях перестановка местами двух циклов (при условии сохранения смысла программы) может увеличить скорость выполнения программы за счет уве-15-

личения локальности памяти. В приведенном примере элементы массива a используются в следующем порядке: 0, n, 2*n, ... (m-1)*n, 1, 1+n, ..., 1+(m-1)*n, ... m*n-1 Если переставить местами эти два цикла (что в данном случае не изменит смысла программы) , то элементы массива a будут использоваться последовательно2 . Пример 4. Гнездо циклов после перестановки f o r (j = 0; j < m ; j ++) f o r (i = 0; i < n ; i ++) a [j *n+ i ] += i + j ;

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

Снижение стоимости индуктивных выражений

Снижение стоимости (strength reduction) — это трансформация, заменяющая дорогие операции на аналогичные, но более дешевые. Так, например, в случае с индуктивными выражениями есть возможность заменить операцию умножения на операцию сложения3 . Пример 5. Замена умножения на сложение f o r (i = 1; i < n ; i ++) {... i* k ...}

эквивалентно f o r (i = 1 , ik = k ; i < n ; i ++ , ik += k ) {... ik ...} 2

Данная трансформация ускорит программу только в том случае, если массив а не помещается целиком в кэш процессора, т. е. число m*n*sizeof(a[0]) больше размера доступного кэша. 3 На многих архитектурах (в том числе, ULTRASparcTM IIICu и Intel PentiumTM 4) целочисленное умножение дороже сложения.

-16-

Даже в тех случаях, когда умножение ст´оит не дороже сложения (например, умножение на степень двойки, которое можно реализовать через сдвиг влево), эта трансформация приносит пользу, так как дает возможность лучше отработать другим трансформациям, например, планировщику (scheduler). Пример 6. Замена сдвига на сложение char * a; /∗ 1 ∗/ f o r (i = 0; i < n ; i ++) *( a +( i < <3)) = 0; /∗ 2 ∗/ f o r (i = 0 , ai =a ; i < n ; i ++ , ai +=8) *( ai ) = 0;

Циклы 1 и 2 эквивалентны, но итерация второго цикла не имеет зависимых операций (в первом цикле запись можно выполнять только после операции i<<3), что увеличивает возможности планировки (scheduling) тела цикла. 1.1.5

Развертка циклов

Развертка циклов (loop unrolling) заключается в создании нескольких копий итерации цикла (число копий n называется фактором развертки) и в увеличении шага цикла в это же число раз. После развернутого цикла (или перед ним) необходимо произвести оставшиеся итерации (не более n-1). Пример 7. Развертка цикла f o r (i = 0; i < n ; i ++) a[ i ] = b[i ] + c [i ];

После развертки (с фактором 2): f o r (i = 0; i < n - 1; i +=2){ a[ i ] = b[i ] + c [i ]; a[ i +1] = b [i +1] + c[i +1]; } f o r (; i < n ; i ++) a [i ] = b[ i ] + c [i ];

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

Многие другие трансформации циклов или используют развертку, или построены по схожему принципу (например, программная конвейеризация [17, §6.2.7]).

1.2

Индуктивные переменные и выражения

Во всех приведенных выше трансформациях (часть 1.1), как и во многих других, индуктивные переменные играют важную роль. Для некоторых трансформаций (например, для перестановки циклов, раздел 1.1.3) необходимо проанализировать индуктивные переменные вложенных циклов, после чего принимать решение о трансформации. А в других трансформациях индуктивные переменные сами являются главным объектом трансформации (например, при снижении стоимости, раздел 1.1.4). Автором был разработан и реализован в оптимизирующем компиляторе набор алгоритмов идентификации, символьного анализа и трансформации индуктивных переменных. Далее приводятся основные из этих алгоритмов и даются необходимые определения. Принципиальные отличия новых алгоритмов от ранее существовавших обсуждаются в разделе 1.6. Определение 1 Инвариантом цикла называется выражение, значение которого не изменяется внутри цикла. Таким образом, инвариантом цикла является а) любая константа, б) переменная, значение которой не изменяется внутри цикла, или в) арифметическое выражение, составленное из других инвариантов цикла. Дадим точное определение индуктивной переменной, которое понадобится нам в дальнейшем. Определение 2 Базовой индуктивной переменной или просто индуктивной переменной (БИП, ИП) будем называть переменную целого типа, все присваивания4 которой внутри цикла имеют вид 4

Подразумевается, что переменная изменяется только через операторы присваивания. Переменные, имеющие внутри цикла неявные использования или изменения, не могут считаться индуктивными. Для нахождения переменных, имеющих неявные использования или изменения, используется информация о потоке данных ([13, §10.5]), однако для изложения алгоритмов в данной работе это не существенно.

-18-

переменная = переменная + инвариант Если БИП имеет ровно одно присваивание внутри цикла, то инвариант будем называть ее шагом5 . Кроме простых индуктивных переменных, в цикле, как правило, встречаются выражения, составленные из индуктивных переменных и инвариантов цикла. Определение 3 Индуктивными выражением (ИВ) будем называть индуктивные переменные, инварианты, а также выражения следующих видов: -ИВ1, ИВ1+ИВ2, ИВ1*ИВ2, ИВ1/константа и (целый_тип)ИВ1. Кроме того, если в цикле имеется присваивание вида переменная=ИВ, то такую переменную будем называть обобщенной индуктивной переменной (ОИП), а все использования этой переменной, имеющие ровно одно достижимое присваивание6 вида переменная=ИВ (и не имеющие других достижимых присваиваний), будем считать индуктивными выражениями. Часто базовая индуктивная переменная используется для управления циклом, т. е. для вычисления условия выхода из цикла. Определение 4 Если • цикл имеет единственное условие выхода, • это условие имеет вид БИП <операция сравнения> инвариант (где операция сравнения — это <, ≤, > или ≥), • индуктивная переменная БИП имеет ровно одно присваивание внутри цикла, • это присваивание находится на главном пути цикла, то такая индуктивная переменная называется управляющей, а инвариант называется верхней границей. 5

Здесь и далее для коммутативных операций (сложение, умножение) будет приводиться только одна форма. Операция вычитания будет считаться частным случаем сложения: например, a-b эквивалентно a+(-b). 6 Здесь подразумевается, что единственное достижимое присваивание доминирует над использованием, что всегда верно, если программа корректна.

-19-

Пример 8. Индуктивные выражения i n t i , j , k , n ; char * a; f o r (i = 0; i < n ; i ++){ j = i; i f (*( a+ i *4) == 0) k += n; }

В этом примере 0, 4, n — инварианты цикла, i, k — (базовые) индуктивные переменные, i — управляющая переменная, j — обобщенная индуктивная переменная, i*4, a+i*4 — индуктивные выражения. Пример 9. Обобщенная индуктивная переменная f o r (i = 0; i < n ; i ++){ i f (...) { j = 2* i ;} else

{j = 2* i +1;}

a[ j ] = 0; }

В этом примере переменная j не будет индуктивным выражением в выражении a[j], так как в этой точке достижимо более чем одно определение j. Алгоритм поиска индуктивных переменных и выражений достаточно прост и выполняется в соответствии с определениями 2 и 3. Алгоритм 1 нахождение индуктивных выражений в цикле 1 Пометить все переменные и выражения как неизвестные. 2 Все переменные, удовлетворяющие определению 2, пометить как базовые индуктивные переменные. 3 Все выражения, удовлетворяющие определению 3, пометить как индуктивные выражения. 4 Если найдены новые индуктивные выражения, перейти к п. 3. -20-

1.2.1

Преобразование типов индуктивных переменных

Одним из видов индуктивных выражений, перечисленных в определении 3, является оператор преобразования типа, примененный к индуктивному выражению. Такие индуктивные выражения явным образом встречаются во многих программах, однако при компиляции для 64-х битных архитектур — это наиболее характерныq случай: Пример 10. Преобразование типа индуктивного выражения assert ( s i z e o f ( i n t *) == 8); assert ( s i z e o f ( long long ) == 8); assert ( s i z e o f ( i n t ) == 4); i n t i , n , * a ; ... f o r (i = 0; i < n ; i ++) a[ i ] = 0;

В примере 10 присутствует неявное преобразование типа: выражение a[i] эквивалентно выражению a[(long long)i]. Для снижения стоимости индуктивных выражений, равно как и для ряда других трансформаций, необходимо знать, что если индуктивная переменная i имеет начальное значение i0 и шаг step, то выражение (long long)i будет иметь начальное значение (long long)i0 и шаг (long long)step. Это неверно, если тип переменной i — беззнаковый (проблемы с беззнаковыми индуктивными переменными анализируются в главе 2). В определениях 3 (стр. 19) и 6 (стр. 24) подразумевается, что индуктивное выражение, стоящее в операторе преобразования типа, имеет знаковый тип. 1.2.2

Деление индуктивного выражения на константу

Еще один тип индуктивного выражения, описанный в определении 3, — это результат деления индуктивного выражения на константу. Предположим, что значения некоторого индуктивного выражения образуют арифметическую прогрессию с шагом s1. Если все элементы последовательности имеют один знак или последовательность содержит число 0, а число c нацело делит s1, то, поделив последова-21-

тельность на число c, мы получим другую арифметическую прогрессию с шагом s2 = s1/c. Пример 11. Деление индуктивных выражений на константу i n t i; f o r (i = 0; i <= 8; i += 4){ .. ( i +1) / 2 .. .. ( i -4) / 2 .. .. ( i -5) / 2 .. }

В примере 11 выражения принимают следующие значения: i+1:

1, 5, 9

(i+1)/2:

0, 2, 4

i-4:

−4, 0, 4

(i-4)/2:

−2, 0, 2

i-5:

−5, −1, 3

(i-5)/2:

−2, 0, 1

Выражение (i-5)/2 не является индуктивным (это видно из таблицы) из-за того, что не выполнено ни одно из следующих условий: • все значения делимого выражения имеют один знак или • одно из значений делимого выражения — 0. В определениях 3 и 6 подразумевается, что для индуктивного выражения, стоящего в операторе деления на константу, выполнено одно из этих условий, однако проверка таких условий выходит за рамки данной работы (см. стр 42).

1.3 1.3.1

Символьное представление индуктивных выражений С-функция

В самых простых случаях можно считать, что значение индуктивной переменной — это линейная функция от номера итерации цикла (так, например, определяется индуктивная переменная в [17, §6.2.3]). Однако нам понадобится более детальное описание значения индуктивной переменной. Рассмотрим следующий пример. -22-

Пример 12. Индуктивная переменная с двумя определениями i n t i = i0 ; j = j0 , k = k0 ; while ( i < n ){ j ++; /∗ТМ1∗/ k ++; /∗ТМ2∗/ i f ( какое - либо условие ) k +=2; /∗ТМ3∗/ f(i ,j ,k ); i ++; /∗ТМ4∗/ }

Значения переменных i и j в данном примере действительно определяются только номером итерации, но определяются по-разному. Так, при вычислении f(i,j,k) значение переменной i будет равно "номер итерации - 1 + i0", а значение переменной j — "номер итерации + j0" (номер итерации отсчитывается от единицы). Для вычисления значения переменной k будет уже недостаточно номера итерации. Таким образом, нам понадобится следующее определение. Определение 5 Выражения вида переменная = переменная + инвариант будем называть точкой модификации (ТМ) базовой индуктивной переменной. Под числовым значением точки модификации будем подразумевать количество выполнений данного выражения с начала выполнения цикла7 . В примере 12 помечены четыре ТМ. Используя числовые значения ТМ, мы можем записать значения переменных i, j, k таким образом: i = i0 + TM4 j = j0 + TM1 k = k0 + TM2 + 2*TM3 7

Операторы языка Си вида переменная++ и переменная+=инвариант также подпадают под это определение.

-23-

Определение 6 С-функцией (символьной функцией) будем называть выражение, составленное из инвариантов цикла, числовых значений ТМ и арифметических операций. С-функцией индуктивного выражения будет функция, значения которой совпадают со значениями данного индуктивного выражения. Таким образом, для любой БИП, имеющей точки модификации ТМ_1: БИП = БИП + ИНВАРИАНТ_1 ... ТМ_К: БИП = БИП + ИНВАРИАНТ_К С-функция будет вычисляться как ТМ_1*ИНВАРИАНТ_1+...+ТМ_К*ИНВАРИАНТ_К +<начальное значение БИП>. Если индуктивные выражения ИВ1 и ИВ2 имеют С-функции СФ1 и СФ2 соответственно, то для выражения, составленного из ИВ1 и ИВ2, С-функция будет вычисляться по следующим правилам: если ИВ3=ИВ1+ИВ2,

то

СФ3=СФ1+СФ2

если ИВ3=ИВ1*ИВ2,

то

СФ3=СФ1*СФ2

если ИВ3=ИВ1/ИВ2,

то

СФ3=СФ1/СФ2

если ИВ3=-ИВ1,

то

СФ3=-СФ1

если ИВ3=(целый_тип)ИВ1,

то

СФ3=СФ1

Несколько сложнее определяется С-функция для обобщенной индуктивной переменной. Пример 13. Различные обобщенные индуктивные переменные while (...){ i ++;

g= i *2;

f1 (g ); /∗ 1 ∗/

g= j *3;

f2 (g );

j ++;

g= k *4;

k ++;

f3 (g ); /∗ 3 ∗/

/∗ 2 ∗/

}

-24-

Алгоритм 2 Вычисление С-функции использования ОИП 1 Найти выражение ОИП=ИВ, соответствующее данному использованию. (если данное использование не удовлетворяет определению 3, то С-функция для этого использования ОИП не определена). 2 Присвоить С-функции данного использования ОИП значение С-функции ИВ. 3 Для каждой точки модификации ТМ, которая входит в С-функцию ИВ и находится между выражением ОИП=ИВ и данным использованием, заменить ТМ на ТМ-1 в С-функции данного использования ОИП. Так, в случаях 1 и 2 (пример 13) C-функция переменной g будет совпадать с функциями выражений i*2 и j*3 соответственно. Для вычисления C-функции в случае 3 необходимо заменить точку модификации переменной k (ТМ_К) на ТМ_К-1. Пример 14. С-функции ОИП while (...){ i ++; /∗ТМ_I∗/

g =2*( i0 + TM_I );

g =3*( j0 + TM_J );

f2 (3*( j0 + TM_J )); j ++; /∗TM_J∗/

g =4*( k0 + TM_K );

k ++; /∗TM_K∗/

f1 (2*( i0 + TM_I ));

f3 (4*( k0 +( TM_K -1)));

}

Определение 7 С-функцией использования обобщенной индуктивной переменной будем называть С-функцию, вычисленную по алгоритму 2. 1.3.2

Каноническая форма С-функции

Большинство систем, оперирующих с символьными выражениями, приводят выражения к какому-либо стандартному виду. Например, в документации к системе компьютерной алгебры Mathematica описана каноническая форма, к которой приводятся математические выражения перед выполнением большинства операций ([50, §2.5.2]). Основная причина для приведения выражений к стандартному виду — необходимость сравнивать выражения между собой. Например, программе -25-

может быть не очевидно, что выражения b*2+a и b+a+b эквивалентны. Если же оба выражения привести к какому-либо стандартному виду, например a+2*b, то операция сравнения сильно упростится. Важной частью приведения к каноническому виду является задание полного порядка на множестве возможных выражений, так как операнды коммутативных операций (сложение, умножение) должны находиться в определенном порядке. Не имеет большого значения, как именно задавать полный порядок; важно лишь задать его таким образом, чтобы упростить дальнейшие операции. В нашем случае удобно, чтобы константы всегда находились в левой части выражения, а точки модификации — в правой. Алгоритм приведения символьного выражения к каноническому виду, примененный автором при реализации символьного анализа индуктивных переменных, не имеет принципиальных отличий от алгоритмов, традиционно используемых в системах компьютерной алгебры; см., например, [34, §5.3]). Приведем сжатое описание этого алгоритма: Алгоритм 3 приведение символьного выражения к каноническому виду

1 Упорядочивание операндов коммутативных операций. 2 Замена операций вычитания и унарного минуса на сложение и умножение: заменить (-a) на (-1 * a), (a-b) на (a + (-1 * b)). 3 Линеаризация коммутативных операций (умножения и сложения): выражения вида a+(b+(c+d)) заменяются на выражения вида a+b+c+d (т. е. используется многооперандное сложение или умножение). 4 Раскрытие скобок: выражения вида a*(b+c) заменяются на a*b+a*c. 5 Упрощение выражений, содержащих константы. 6 Если выражение было изменено, вернуться к шагу 1.

-26-

1.3.3

Линейные С-функции

Большинство алгоритмов, оперирующих с индуктивными выражениями, рассматривают только линейные ИВ, т. е. те ИВ, С-функции которых являются линейными по одной или нескольким точкам модификации. Такую линейную функцию можно записать в виде коэфф_0 + коэфф_1*тм_1 + ... + коэфф_к*тм_к где тм_1, . . . , тм_к — различные точки модификации, а коэфф0, . . . , коэфф_к — выражения, составленные из инвариантов. Описанная выше (раздел 1.3.2) каноническая форма позволяет идентифицировать линейные С-функции при помощи простой группировки слагаемых. Каноническая форма:

1 + 4*a + -1*a*тм_1 + 4*тм_1 + тм_2

Линейная форма:

коэфф0=1+4*a; коэфф1=4+-1*a; коэфф2=1;

1.4

Подстановка индуктивных переменных

Подстановка ИП заключается в замене одной БИП на линейную функцию другой БИП (см. пример 15). Как правило, все БИП заменяются на функцию управляющей переменной (когда это возможно). Сама по себе эта трансформация бесполезна и является (до некоторой степени) обратной по отношению к снижению стоимости. Однако, подстановка ИП применяется на начальном этапе оптимизации программы, чтобы облегчить алгоритмы анализа зависимости данных и автоматической параллелизации (см., например, [29]). Для реализации подстановки ИП был использован механизм символьного представления индуктивных выражений, описанный в частях 1.2 и 1.3. 1.4.1

Подстановка точек модификации

Приведем пример цикла с более чем одной индуктивной переменной, находящейся на главном пути (см. пример 15). В этом примере переменную j можно выразить через переменную i. Точно так же здесь можно выразить одну точку модификации через другую: f(i,j) эквивалент-27-

Пример 15. Подстановка ТМ i = i0 , j = while (...){ j ++; /∗ f(i ,j ); i ++; /∗ }

j0 ; тм2 ∗/ /∗ j ==( j 0+i −i 0 +1) ∗/ тм1 ∗/

но f(i0+тм1, j0+тм2) и эквивалентно f(i0+тм1, j0+тм1+1). Алгоритм 4 подстановка ТМ Дано: две точки модификации тм1 и тм2, находящиеся на главном пути. Необходимо: заменить тм2 на тм1 во всех С-функциях. 1 Для всех индуктивных выражений, С-функции которых содержат тм2 1.1 Если данное выражение находится до или после8 обеих точек модификации, заменить тм2 на тм1 в С-функции данного выражения. 1.2 Если выражение находится после тм2 и до тм1 — заменить тм2 на тм1+1. 1.3 Если выражение находится после тм1 и до тм2 — заменить тм2 на тм1-1. 1.4.2

Вычисление количества итераций цикла

При подстановке индуктивных переменных необходимо не только выразить все (какие возможно) индуктивные переменные через управляющую переменную, но и исключить из цикла все точки модификации подставленных индуктивных переменных. Для этого нам понадобится следующий алгоритм: Алгоритм 5 вычисление числа итераций цикла Дано: цикл типа while (или for), имеющий управляющую переменную (см. определение 4) с константным шагом шаг, начальным значением нг и верхней границей вг. Необходимо: непосредственно перед началом цикла вычислить количество итераций N. Количество итераций будет вычисляться по следующей таблице: 8

Так как обе точки модификации находятся на основном пути цикла, то условия “до” и “после” определяются через условие доминирования.

-28-

операция сравнения

шаг

количество итераций

<

шаг > 0

N=(вг-нг-1)/шаг+1

≤

шаг > 0

N=(вг-нг)/шаг+1

>

шаг < 0 N=(нг-вг-1)/(-шаг)+1

≥

шаг < 0

N=(нг-вг)/(-шаг)+1

Здесь следует уточнить, что означает “непосредственно перед началом цикла”. Циклы типа while(условие){тело;} представляются в компиляторе в следующем виде: 1

i f ( условие ){ // начало цикла

2

3

метка :

4

тело ;

5

i f ( условие ) goto метка ;

6

}

Для таких циклов вычисление числа итераций N следует производить перед оператором метка:. Если же цикл имеет тип do{тело;}while(условие);, т. е. представляется как метка : тело ; i f ( условие ) goto метка ;

то алгоритм 5 может дать неверный результат. Пример 16. Цикл do...while i n t i = 0; do{ ...; i ++; } while (i < n );

Для цикла в примере 16 число итераций N будет вычислено как (n-0-1)/1+1, однако, если n < 0, этот результат будет неверен. Для циклов типа do..while можно использовать следующую формулу: число итераций=min(N,1). -29-

1.4.3

Подстановка индуктивных переменных

Теперь опишем алгоритм подстановки индуктивных переменных. Алгоритм 6 подстановка ИП для одного цикла 1 Найти все БИП (алгоритм 1). 2 Найти управляющую переменную (определение 4). 3 Вычислить С-функции всех ИП (определения 6, 7) и привести их к каноническому виду (часть 1.3.2). 4 В С-функциях всех индуктивных переменных, находящихся на главном пути, (кроме управляющей) подставить точку модификации управляющей переменной (алгоритм 4). 5 Выбрать БИП из п. 4, С-функции которых содержат теперь только точку модификации управляющей переменной, т. е. имеют вид коэфф0+коэфф1*тм, где тм — точка модификации управляющей переменной. 6 Для каждой БИП из п. 5: 6.1 Все вхождения БИП заменить на выражения, вычисленные по новой Сфункции. 6.2 Удалить из цикла все точки модификации БИП. 6.3 Если значение БИП используется после цикла, установить значение БИП равным <начальное значение БИП> + коэфф1*число_итераций (алгоритм 5).

1.5

Снижение стоимости

Описанная в разделе 1.1.4 трансформация снижения стоимости реализована при помощи разработанных и приведенных выше алгоритмов следующим образом: -30-

Алгоритм 7 снижение стоимости (для одного цикла) 1 Найти индуктивные выражения (алгоритм 1). 2 Вычислить С-функции всех ИВ (определения 6, 7) и привести их к каноническому виду (часть 1.3.2). 3 Если в цикле есть несколько БИП, имеющих одно присваивание и ТМ которых находятся на основном пути, выразить эти БИП через одну из них (используя подстановку ТМ, алгоритм 4). 4 Выделить линейные С-функции индуктивных выражений (часть 1.3.3). 5 Выбрать такие выражения, имеющие линейную С-функцию, которые не входят в другое выражение, имеющее линейную С-функцию. 6 Разбить выражения из п. 5 на группы с линейными частями, совпадающими полностью, кроме нулевых коэффициентов (коэфф0). 6* Можно потребовать дополнительное условие: нулевые коэффициенты должны различаться между собой только на константу. 7 Для каждой группы из п. 6 создать новую индуктивную переменную, входящую в данную группу, выбрав в качестве коэфф0 соответствующий коэффициент любого члена группы (если в группе есть БИП — взять ее). Для каждого члена группы вычислить разницу между ним и новой индуктивной переменной (это будет разница нулевых коэффициентов). 8 Все выражения из п. 5 (которым сопоставлена новая индуктивная переменная БИП и разница нулевых коэффициентов разн_коэфф) заменить на выражения БИП+разн_коэфф.

Пример 17. Снижение стоимости //До снижения стоимости : i n t * a , * b ; double * c;

-31-

i n t i = 0; j = j0 ; while (...){ j ++; a[ i ] ... a [i +1] ... a [j ]

... b [i ] ... c [i ]

i ++; } // После снижения стоимости : i n t * a , * b ; double * c; void * p1 =0 , * p2 =( void *) c; i n t i = 0; j = j0 ; while (...){ j ++; *( p1 + a ) ... *( p1 +a +4)... *( p1 +a+ j0 +4) ... *( p1 + b ) ... *( p2 ) p1 += 4; p2 += 8; i ++; } // После снижения стоимости при выполнении пункта 6 ∗ : i n t * a , * b ; double * c; void * p1_1 =( void *) a , * p1_2 =( void *)( a+ j0 +4) , * p1_3 =( void *)b , * p2 =( void *) c; i n t i = 0; j = j0 ; while (...){ j ++; * p1_1 ... *( p1_1 +4) ... * p1_2 ... * p1_3 ... * p2 ; p1_1 +=4; p1_2 +=4; p1_3 +=4; p2 +=8; i ++;

-32-

}

Обработка некоторых видов индуктивных выражений не реализована на данный момент, но может быть добавлена к существующим алгоритмам при минимальных затратах. Среди неподдерживаемых индуктивных выражений — циклические, полиномиальные, геометрические ИП (см. [33]), а также операции деления (общий случай) и взятия остатка от деления, примененные к ИП (см. [48])9 .

1.6

Другие реализации алгоритмов

Алгоритмы анализа и трансформаций индуктивных переменных давно и активно исследуются ([17, §6.2.3]), и поэтому достаточно трудно разработать что-либо принципиально новое. С теоретической точки зрения, алгоритмы анализа индуктивных выражений, приведенные в этой главе, имеют большое сходство с другими алгоритмами (например, [29, 36]). Наиболее важное отличие нового метода — привязка значения индуктивного выражения к точкам модификации индуктивных переменных, а не к номеру итерации цикла, как в других методах. Подобный подход позволяет существенно облегчить анализ взаимосвязи индуктивных переменных. Кроме того, следует заметить, что в известных автору работах не исследуются следующие моменты: • случай нескольких присваиваний индуктивной переменной; • взаимосвязь между различными индуктивными переменными (при снижении стоимости); • преобразование типов индуктивных выражений. Автору представляется немаловажным тот факт, что разработанные им алгоритмы удалось внедрить в сложную структуру работающего компилятора, тем самым добавив в этот компилятор ряд новых качеств. Ниже будут описаны основные 9

Применение оптимизаций перечисленных ИП “вручную” к программам из тестовых наборов SPEC CPU95 и SPEC CPU2000 не принесло существенных результатов.

-33-

отличия новых алгоритмов, от алгоритмов, реализованных ранее в компиляторе Sun. 1.6.1

Идентификация индуктивных переменных

Алгоритм идентификации индуктивных переменных, использовавшийся в прежнем алгоритме снижения стоимости (равно как и в прежнем алгоритме подстановки индуктивных переменных), очень похож на алгоритм 1, однако большим недостатком прежней реализации являлось то, что не использовалась информация о потоке данных, а обрабатывались только локальные переменные, адреса которых не брались. Таким образом, старый алгоритм поиска индуктивных переменных сужал множество обрабатываемых переменных, не рассматривая случаи, когда индуктивная переменная является глобальной, когда ее адрес берется вне цикла или когда переменная является полем в структуре. Кроме того, рассматривались только индуктивные переменные с одним присваиванием 1.6.2

10

.

Снижение стоимости индуктивных выражений

Старый алгоритм снижения стоимости работал по итеративному принципу, т. е. последовательно выполнял преобразования индуктивных выражений. Вот его грубое описание. Алгоритм 8 старый алгоритм снижения стоимости (для одного цикла) 1 Найти индуктивные переменные. 2 Для всех индуктивных переменных i, имеющих начальное значение i0 и шаг s: 2.1 Для всех выражений вида (i+A)*M, где M и A — инварианты цикла, создать новую индуктивную переменную с начальным значением (i0+A)*M и шагом s*M. Для всех выражений (i+A)*M с одинаковым M создавать 10

Стоит, однако, отметить, что индуктивные переменные с несколькими присваиваниями встречаются относительно редко.

-34-

только одну новую переменную. Заменить данное выражение на новую переменную и внести ее в список индуктивных переменных. 3 Если на шаге 2.1 были созданы новые индуктивные переменные, вернуться к шагу 2. Данный алгоритм имеет следующие недостатки, устраненные в новом алгоритме: • в процессе работы алгоритма часто создаются временные переменные, которые затем не используются; • никак не учитывается взаимосвязь между различными индуктивными переменными; • никак не обрабатываются операторы деления индуктивного выражения на константу; Кроме того, итеративная природа алгоритма привела к различным проблемам в его реализации: • алгоритму не всегда удается создать минимальное количество новых индуктивных переменных, то есть создается две или более индуктивных переменных для выражений, которые на самом деле отличаются на аддитивную константу; • осложнена и в результате практически не реализована обработка операторов преобразования типа, примененных к индуктивным выражениям, что особенно важно при компиляции для 64-битной платформы; 1.6.3

Подстановка индуктивных переменных

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

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

1.7

Результаты

Основным практическим результатом внедрения алгоритмов снижения стоимости индуктивных выражений и подстановки индуктивных переменных является увеличение скорости работы скомпилированных программ11 — до 12% ускорения на тестах SPEC CPU2000 (см. таблицы 2 и 3, а также рисунок 2). Из таблиц видно, что выигрыш был получен в основном на тестах из набора SPECfp2000. Этот факт хорошо согласуется с таблицей 1, из которой следует, что циклы с индуктивными переменными (в том числе, с управляющей переменной) более характерны для набора SPECfp2000, чем для набора SPECint2000. Таблица 2. Результат применения нового алгоритма снижения стоимости индуктивных выражений Тест SPECint2000 1 SPECfp2000 1 2 3 4 5 6 7 11

Ускорение 1% 4% 3% 3% 3% 2% 2% 1%

Здесь и далее имена тестов не указываются.

-36-

Таблица 3. Результат применения нового алгоритма подстановки индуктивных переменных Тест SPECfp2000 1 2

Ускорение 12% 2%

Необходимо также рассмотреть причины такого ускорения. При помощи нового алгоритма идентификации линейных индуктивных выражений (см. раздел 1.3.3) удалось найти на 10% выражений больше, чем при помощи старого алгоритма: см. таблицу 4. Новый алгоритм подстановки индуктивных переменных позволил произвести подстановок в три раза больше прежнего, что, в свою очередь, привело к увеличению числа распараллеленных циклов на 7% (таблицы 5 и 6). Таблица 4. Количество найденных линейных индуктивных выражений Тесты SPECint2000 SPECfp2000 Всего

Старый алгоритм 29000 69000 98000

Новый алгоритм 31000 78000 109000

Таблица 5. Количество произведенных подстановок индуктивных переменных Тесты SPECint2000 SPECfp2000 Всего

Старый алгоритм 244 110 354

-37-

Новый алгоритм 613 566 1179

Таблица 6. Количество распараллеленных циклов Тесты SPECint2000 SPECfp2000 Всего

Старый алгоритм 114 977 1091

Новый алгоритм 129 1023 1172

Несмотря на то что новые алгоритмы, описанные в данной главе, выполняют существенно больше действий, чем применявшиеся ранее, проведенные эксперименты показали, что время компиляции изменяется не существенно (суммарное время компиляции тестов SPEC CPU2000 возросло менее, чем на один процент).

1.8

Выводы

• Разработаны новые алгоритмы идентификации и символьного анализа индуктивных переменных и выражений, а также управляющей переменной. Новые алгоритмы анализа позволяют: – обрабатывать индуктивные переменные с несколькими присваиваниями; – учитывать взаимосвязь между различными индуктивными переменными; – анализировать и оптимизировать операторы преобразования типов, примененные к индуктивным переменным и выражениям; – трансформировать операторы деления индуктивного выражения на константу. • На основе данных алгоритмов анализа разработаны алгоритмы оптимизации: подстановка индуктивных переменных и снижение стоимости индуктивных выражений. Новые алгоритмы снижения стоимости и подстановки индуктивных переменных реализованы в промышленном оптимизирующем компиляторе Sun, заменив собой предыдущие реализации этих же трансформаций.

-38-

Ранее используемые алгоритмы (см. 1.6) имели ряд существенных недостатков теоретического характера, равно как и проблемы в реализации. • Основным практическим результатом данной главы является увеличение производительности программ (до 12% на программах пакета SPEC CPU2000), полученное в результате применения новых алгоритмов снижения стоимости индуктивных выражений и подстановки индуктивных переменных. • В результате перехода на новые алгоритмы время компиляции не возросло, несмотря на то, что cущественно увеличилось количество производимых трансформаций.

-39-

2

Нормализация структуры управляющей переменной цикла Оптимизация циклов, имеющих управляющую переменную (см. определение 4),

по праву считается одним из наиболее важных классов автоматических оптимизаций. В подавляющем большинстве работ, посвященных данной теме, рассматриваются только циклы, имеющие стандартную структуру DO цикла на языке Фортран (см., например, [20, §4.2]). do i= lower , upper [ , step ] < тело цикла > enddo

Использование языка Фортран для описания примеров циклов не случайно. По стандарту языка ([14, §8.1.4.4]) поведение циклов с управляющей переменной определено следующим образом: сначала вычисляется количество итераций цикла

count = max(0,

upper − lower + step ), step

а затем производится вычисленное количество итераций. При этом значение переменной i вычисляется как lower+n*step, где n — номер итерации, отсчитываемый от нуля. Такое определение, конечно же, не обязывает компилятор создавать столь сложный код в простых случаях, а только строго определяет семантику выполнения циклов. В языках Си ([37]) и Си++ ([12]) вообще нет понятия управляющей переменной: вместо этого определяется конструкция for цикла, которая в простом случае может быть эквивалентна DO циклу в языке Фортран. В простейшем (и наиболее распространенном) случае цикл for выглядит следующим образом: f o r (i = lower ; i <= upper ; i += step ){ < тело цикла > }

-40-

На первый взгляд может показаться, что приведенные выше структуры циклов на языках Фортран и Си эквивалентны. Однако это не всегда так. Приведем лишь несколько примеров, когда данные две структуры циклов не эквивалентны. • Выражения upper и/или step не являются инвариантами цикла и/или переменная i может быть неявно изменена в теле цикла. В таком случае переменная i в цикле на языке Си не будет управляющей

12

.

• Переменная i имеет беззнаковый (unsigned) целый тип (см. раздел 2.1). Кроме приведенных примеров, проблемы с идентификацией управляющей переменной в языке Си могут возникнуть, например, из-за использования оператора неравенства (!=) вместо оператора сравнения (<=) или использования глобальной переменной в качестве верхней границы. Дадим определение структуры цикла на языке Си (Си++), аналогичное DOциклу в языке Фортран. Определение 8 DO-циклом в языке Си будем называть цикл, который можно записать в одном из следующих видов: f o r (i = l ; i <

u ; i += step ) ...

f o r (i = l ; i <= u ; i += step ) ... f o r (i = l ; i >

u ; i -= step ) ...

f o r (i = l ; i >= u ; i -= step ) ...

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

Точнее, она не будет удовлетворять определению управляющей переменной 4. Однако, в некоторых случаях в этой главе мы будем называть такие переменные управляющими. 13 В данной главе будет рассмотрен только случай положительного константного значения выражения step.

-41-

Интервальный анализ Интервальный анализ (interval analysis, value range analysis) — это такой вид анализа значений переменных и выражений, который позволяет статически (т. е. во время компиляции) определить множество возможных значений той или иной переменной, а также проверить выполнение некоторых условий, связывающих несколько переменных. Пример 18. Применения интервального анализа 1

i n t a , b , c ; ...

2

i f (...) a = 10; e l s e a = 20;

3

i f ( b < a && c < b ){

4

... b ... c ...

5

}

В строчке 3 (пример 18) переменная a может принимать значения 10 и 20. Таким образом, можно утверждать, что в строке 4 выполнены неравенства b <= 19 и c <= 18. Подробное описание алгоритмов интервального анализа дано в работах [45], [22], [23] и [38]. Специализация кода Специализация кода — очень простая трансформация. Предположим, у нас имеется участок кода C и условное выражение α. Если фрагмент C может быть упрощен в случае, когда выполнено условие α, тогда мы можем заменить фрагмент C следующим кодом: if(α) then Cα else C где Cα — это версия фрагмента C, упрощенная благодаря тому факту, что условие α выполнено. Для корректности такой трансформации достаточно, чтобы условие α не имело побочных эффектов, а фрагмент кода C имел ровно один вход.

-42-

Рис. 1. Специализация кода Специализация кода может быть применена практически к любому фрагменту C и любому условию α, но в большинстве случаев это замедлит программу. Таким образом, главным вопросом будет: в каких случаях производить специализацию кода, т. е. • Какой фрагмент C выбрать? • Какое условие α выбрать? Если мы хотим увеличить скорость работы программы, трансформированный код должен работать быстрее, чем первоначальный, т. е. мы должны убедиться, что специализация кода принесет положительный результат. Таким образом, мы приходим к простому уравнению:

(1)

Benefit(α) = Cost(C) − (1 − Freq(α))Cost(C) − Freq(α)Cost(Cα ) − Cost(α)

где Cost(x) представляет стоимость выполнения фрагмента x, а Freq(y) — относительную частоту выполнения условия y. Уравнение (1) можно переписать в следующем виде: Benefit(α) = Freq(α)(Cost(C) − Cost(Cα )) − Cost(α) -43-

(2)

Если фрагмент C является просто одной машинной инструкцией (например, инструкцией деления или умножения), то уравнение (1) не достаточно верно описывает возможный выигрыш: специализация таких маленьких фрагментов кода может помешать другим важным трансформациям, напрмер программной конвейеризации. Применение специализации кода к дорогим машинным инструкциям является безусловно интересной темой исследования, но в данной работе мы рассмотрим только фрагменты кода большего размера, а именно циклы. Специализация кода и ее применения рассматриваются, например, в [43].

2.1

Использование беззнакового типа

В языках Си и Си++, в противоположность языку Фортран, имеется различие между знаковыми и беззнаковыми целыми типами. Одним из важных отличий знаковых и беззнаковых типов является результат операций сравнения. Другое, не менее важное отличие следует из различного определения результата целочисленных операций, вызывающих переполнение (overflow). Для беззнаковых целых типов результат определен как вычисление по модулю 2k , где k — разрядность типа, в то время как для знаковых типов результат переполнения не определен вовсе ([37, §7.2.2]). Такое ограничение, вводимое для беззнаковых типов, не позволяет проводить целый ряд трансформаций, если управляющая переменная имеет беззнаковый тип. Приведем пример: Пример 19. Цикл с беззнаковой управляющей переменной f o r ( unsigned i = 0; i <= n ; i ++) a[ i ] = 0;

В этом простейшем цикле нельзя произвести трансформацию снижения стоимости (1.5), если размер типа unsigned меньше размера указателя (типичная ситуация при компиляции для 64-х битной платформы). В этом же примере невозможно точно вычислить число итераций, так как переменная n может иметь значение UINT_MAX, и в этом случае цикл будет выполняться вечно.

-44-

В подавляющем большинстве реальных программ беззнаковый тип для управляющей переменной или верхней границы выбран не потому, что он позволяет хранить положительные числа с б´ольшими значениями, чем в знаковом типе, а по ряду других причин или вообще случайно. Как правило, замена типа управляющей переменной и/или типа верхней границы на знаковый тип того же размера не изменяет смысла программы. Однако, компилятор должен строго соблюдать семантику языка, поэтому во многих случаях для замены типа управляющей переменной необходимо производить специализацию кода (стр. 42). В некоторых простых случаях интервальный анализ (см. стр. 42) или просто анализ константных выражений позволяет избежать специализации кода. Для замены типа управляющей переменной или верхней границы достаточно выполнения следующего условия: начальное и конечное значения управляющей переменной находятся в интервале [0,INTTYPE_MAX], где INTTYPE_MAX — максимальное значение данного знакового типа. В некоторых случаях проверку этого условия можно осуществить статически, в других случаях необходимо производить специализацию кода. Иногда условие можно ослабить или проверить часть условия статически. Приведем примеры. unsigned u , l ;... f o r ( unsigned i = l ; i < u ; i ++) ...

Здесь конечным значением управляющей переменной будет u, и условие замены типа будет l ≤ INT _MAX ∧ u ≤ INT _MAX. f o r ( unsigned i = 0; i < 100; i ++)

Поскольку проверку можно произвести статически, для замены типа специализации кода не требуется. unsigned u; f o r ( unsigned i = 0; i <= u ; i ++)

Здесь конечным значением будет u+1, и условие замены следует записать как u < INT _MAX.

-45-

unsigned u; f o r ( unsigned i = 0; i <= u ; i +=2)

Возможных конечных значений два: u+1 и u+2. Достаточным условием для замены типа будет u ≤ INT _MAX − 2.

2.2

Использование оператора != в условии цикла

Языки Си и Си++ позволяют программисту использовать оператор неравенства в условии завершения цикла. Например, достаточно распространенным является такое описание цикла: while (-- i ) ...

Здесь неявно используется оператор неравенства для сравнения управляющей переменной с нулем. Как правило, такой цикл можно переписать в виде while (-- i > 0) ...

Но, если начальное значение переменной i было меньше нуля, смысл цикла изменится. Встречается также полная конструкция цикла for: f o r (i = l ; i != u ; i ++) ...

Опыт автора показывает, что в программах, написанных на Си, такая конструкция появляется по причине “неопрятности” программиста и его непонимания проблем оптимизации программ. Однако использование конструкции for с оператором неравенства часто бывает оправдано в программах, написанных на языке Си++, что в первую очередь связано с использованием стандартной библиотеки шаблонов STL [55] и других подобных библиотек. В библиотеке STL имеется множество различных классов-контейнеров, которым соответствуют типы итераторов. Для всех типов итераторов, имеющихся в STL, определен оператор неравенства, тогда как оператор меньше определен далеко не для всех типов итераторов. Такая ситуация приучает программиста везде использовать оператор неравенства, даже если точно известно, что данный тип итератора (например, vector::iterator) име-46-

ет оператор меньше. Использование оператора неравенства является единственно возможным вариантом при написании кода функций-шаблонов, когда неизвестно, какого именно типа данный класс-контейнер. В ряде случаев использование оператора неравенства в цикле for может привести к логическим ошибкам в программе (см., например, [7, §66.1]). Но не менее важной проблемой таких циклов является снижение производительности. Приведем пример. i n t foo ( unsigned l , unsigned u , i n t & sum ) { f o r ( unsigned i = l ; i != u ; i ++) sum ++; }

Если вызов функции foo будет выглядеть как foo(10,20,sum), то цикл выполнит десять итераций. Если вызвать foo(20,10,sum), то будет выполнено существенно больше итераций, так как переменная i пройдет все значения от 20 до UINT_MAX, далее произойдет переполнение и выполнится еще 10 итераций. В случае, когда переменная i имеет знаковый тип и l > u, поведение цикла точно не определено, но наверняка выполнится INT_MAX-20 итераций, прежде чем произойдет целочисленное переполнение. В связи с неопределенностью поведения циклов, использующих оператор неравенства, компилятор не может проводить над такими циклами большинство оптимизаций. Таким образом, мы пришли к необходимости привести цикл к более привычному виду f o r (i = l ; i < u ; i ++) sum ++;

Рассмотрим два подхода. • Проверить, что нижняя граница цикла l не превосходит верхней границы u. Такую проверку можно проводить как статически (т. е. во время компиляции), так и динамически (т. е. во время исполнения программы). • Убедиться, что в случае, если нижняя граница цикла превосходит верхнюю, -47-

то цикл выполнит недопустимую операцию и программа будет завершена. Здесь используется подход “мусор на входе — мусор на выходе” (“garbage in — garbage out”), т. е. некорректная программа может быть некорректно трансформирована. Такой подход, однако, не годится для языка Java ([52]), в котором строго определен порядок появления исключительных ситуаций. Приведем примеры. 1

unsigned u;

2

i n t U;

3

char * p1 , * p2 ;

4

...

5

f o r ( unsigned i = 0; i != u ; i ++) ...

6

f o r ( i n t i = 10; i != 20; i ++) ...

7

f o r ( i n t i = 0; i != U ; i ++) ...

8

f o r ( char * p = p1 ; p != p2 ; p ++) * p = 0;

В первых двух циклах (строки 5 и 6) можно заменить оператор неравенства оператором меньше, так как во время компиляции известно, что верхняя граница не меньше нижней. Для цикла на строке 7 неизвестно отношение верхней и нижней границ цикла и остается только производить специализацию кода, вставляя динамическую проверку. i f ( U >= 0) f o r ( i n t i = 0; i < U ; i ++) ... else f o r ( i n t i = 0; i != U ; i ++) ...

Последний цикл (на строке 8) выполнит недопустимую операцию чтения из несуществующего адреса в том случае, если p1 > p2. Поэтому здесь можно заменить оператор неравенства на оператор меньше, не используя динамическую проверку. Ситуация осложняется, если шаг управляющей переменной не равен единице. f o r ( i n t i = l ; i != u ; i += 2)

В таком случае к условию l <= u добавляется условие ((u-l)%2)==0. -48-

Рассуждения, приведенные в данном разделе для положительных константных значений шага управляющей переменной, легко переносятся на случай отрицательного константного шага. Если же шаг управляющей переменной вовсе не является константой (что, однако, встречается относительно редко), то дополнительно надо проверить знак шага. Например, для нормализации цикла f o r ( i n t i = l ; i != u ; i += s ) ...

необходимо произвести следующую специализацию: i f ( s > 0 && l <= u && (( u -l )% s ) == 0) f o r ( i n t i = l ; i < u ; i += s ) ... e l s e i f (s < 0 && l >= u && (( l -u )% s ) == 0) f o r ( i n t i = l ; i > u ; i += s ) ... else < оригинальный цикл >

2.3

Использование оператора постинкремента

Предметом рассмотрения в данном разделе является использование оператора постинкремента с управляющей переменной цикла for (или while). Как и в предыдущих разделах 2.1 и 2.2, здесь исследуется вопрос приведения циклов к нормальной форме DO циклов. Язык Си и языки, унаследовавшие богатый синтаксис Си (такие как Си++, Objective С ([53]), Java, С# ([54]) и многие другие), имеют крайне удобный для программиста унарный оператор постинкремента (a++), означающий прибавление единицы к операнду. Однако в некоторых случаях использование оператора постинкремента может создать определенные “неудобства” для оптимизирующего компилятора. Дело в том, что результатом вычисления выражения a++ является значение переменной a до прибавления единицы, то есть запись b=a++; эквивалентна записи tmp=a; a=a+1; b=tmp;. Игнорирование многими программистами семантики оператора постинкремента приводит к тому, что в некоторых случаях существенно усложняется анализ цикла для компилятора. Вот достаточно распространенный пример: -49-

Пример 20. Оператор постинкремента в цикле while i = 0; while ( i ++ <= n ) a [i ] = 0;

Приведенный цикл семантически эквивалентен следующему: tmp = 0; i = 1; while ( tmp <= n ){ a[ i ] = 0; tmp = i ; i = i + 1; }

То есть в цикле, среди прочего, производятся следующие вычисления: tmp = i ; i = i + 1; tmp <= n;

Таким образом, получается, что у цикла нет управляющей переменной (по крайней мере, удовлетворяющей определению 4 на стр. 19) и большинство трансформаций цикла становятся невыполнимыми. Задачей данного раздела является перечисление условий, при которых можно заменить цикл, использующий оператор постинкремента, на обычный DO цикл. Если рассматривать проблему с точки зрения математики, то последовательность tmp=i; i=i+1; tmp<=n; эквивалентна последовательности tmp=i; i=i+1; i<=n+1. Однако возможность целочисленного переполнения не позволяет в общем случае произвести такую замену. Мы пришли к следующему утверждению: Условие завершения цикла, имеющее вид i++<=n, можно заменить на условие ++i<=(n+1)14 , если при вычислении n+1 и ++i заведомо не произойдет переполнения. Условие непереполнения n+1 означает то, что верхняя граница не должна превратиться из очень большого числа в очень маленькое (или наоборот). Необходи14

Оператор предекремента i=i+1;i<=(n+1);

использован

для

-50-

простоты.

Можно

было

бы

написать

мость непереполнения ++i может показаться чуть менее очевидной, поэтому рассмотрим пример: unsigned l = UINT_MAX -1 , u = UINT_MAX -1; while ( l ++ <= u ) printf ("% u\ n" , l );

данный фрагмент программы выведет одну строку, тогда как программа unsigned l = UINT_MAX -1 , u = UINT_MAX -1; while (++ l <= ( u +1)) printf ( "%u \n" , l );

должна зациклиться. Нечто подобное может произойти также и в случае, когда тип управляющей переменной будет знаковый. Несмотря на то что результат переполнения знаковой переменной не определен, а в исходной программе происходит переполнение, поведение программы строго определено, так как результат переполнения в ней не используется. Нетрудно проверить, что для цикла for (или while) оба условия выполняются, если верхняя граница n не превосходит числа M-2, где M — максимальное возможное число данного целого типа. Для цикла вида do..while(..) это, к сожалению, не верно (необходимо дополнительно проверить, что перед началом цикла выполнено условие l<=u). Для циклов с условием i++
a [i ] = 0;

-51-

2.4

Использование глобальной переменной в качестве верхней границы

Рассмотрим следующие два примера: Пример 21. Глобальная переменная в качестве верхней границы extern i n t N; void foo ( i n t *a , i n t * b ){ f o r ( i n t i = 0; i <= N ; i ++) a [i ] = b[ i ]; }

Для данного примера компилятор далеко не всегда сможет определить, что запись по указателю a не может изменить значения переменной N. Таким образом, переменная N не может считаться инвариантом и переменная i не удовлетворяет определению управляющей переменной 4. Пример 22. Результат считывания из памяти в качестве верхней границы s t r u c t bar {... i n t N ; ...}; void foo ( i n t *a , i n t *b , s t r u c t bar * c ){ f o r ( i n t i = 0; i <= c -> N ; i ++) a [i ] = b[ i ]; }

В данном случае в условии выхода из цикла используется результат считывания из памяти, что также не позволяет называть переменную i управляющей, поскольку значение выражения c->N может быть изменено через указатель a. Практика показывает, что в большинстве случаев, подобных примерам 21 и 22, верхняя граница на самом деле остается неизменной15 . И в некоторых случаях этот факт можно проверить во время исполнения программы. Так, в примере 22 достаточно проверить, что адрес &(c->N) не входит в промежуток [a, a+c->N]. В примере 21 достаточно произвести аналогичную проверку для адреса переменной 15

Автор ни разу не сталкивался с реальной программой, в которой это было бы не так.

-52-

N и интервала адресов [a, a+N]. Пример 23. Проверка инвариантности верхней границы i f (& N < a || & N > ( a+N )){ i n t tmp = N; f o r ( i n t i = 0; i <= tmp ; i ++) a [i ] = b[ i ]; } else { < исходный цикл > }

Проверку

(&N < a || &N > (a+N))

можно

записать

в

виде

(unsigned)(&N-a) > (unsigned)N. В качестве верхней границы цикла может выступать арифметическое выражение, содержащее глобальную переменную или считывание из памяти, например, while(i <= N+1) или while(i <= c->N/2). Для удобства изложения дадим следующие определения: Определение 9 Полуинвариантой переменной цикла назовем переменную, не изменяемую в цикле явно, но, возможно, изменяемую неявно (см. пример 21). Определение 10 Полуинвариантным считыванием назовем считывание из инвариантного адреса A, такого, что цикл не содержит явной записи по этому адресу, но содержит другие операторы, имеющие возможность произвести запись по адресу A (см. пример 22). Определение 11 Полуинвариантом цикла назовем арифметическое выражение, составленное из инвариантов (определение 1), полуинвариантных переменных (определение 9) и полуинвариантных считываний (определение 10). Примеры 22 и 21 можно обобщить следующим образом. Цикл L содержит полуинвариант U. Если определить, что U является инвариантом, то цикл L будет иметь управляющую переменную (удовлетворяющую определению 4), а U будет -53-

верхней границей. Все операторы, которые могут изменить значение U, имеют вид *(линейное индуктивное выражение)=..., т. е. являются операторами записи в память, адрес которой является выражением, линейным по управляющей переменной. Таким образом, для всех этих операторов можно вычислить интервал адресов, по которым производиться запись. Затем для каждой полуинвариантной переменной N, входящей в U, проверить, что адрес &N не входит ни в один из вычисленных интервалов. Аналогичную проверку произвести для полуинвариантных считываний, содержащихся в U. Оптимизация, подобная примеру 23, является частным случаем динамического разрешения конфликтов по доступу в память (dynamic memory disambiguation, DMD, run time memory disambiguation). Как будет показано в разделе 2.7, замена полуинвариантной верхней границы на инвариант дает возможность выполнить другие виды динамического разрешения конфликтов по доступу в память, что и является основной причиной получения заметного выигрыша в производительности. Динамическое разрешение конфликтов по доступу в память (DMD) Некоторые методы DMD используют специфическую аппаратную поддержку, недоступную в процессорах SPARC (см., например, [32], [39]). Наиболее распространенный и простой вид DMD, не требующий специальной аппаратной поддержки, — это проверка непересечения двух (или более) интервалов памяти перед началом цикла ([46]). Пример 24. Цикл с конфликтами по доступу в память int32 * a , * b , * c , n , i ; f o r (i = 0; i < n ; i ++) a[ i ] = b[i ] * (* c );

Предположим, что в данном примере компилятору неизвестно, пересекаются или нет интервалы [a, a + 4n), [b, b + 4n) и [c, c + 4). Если проводить оптимизацию на уровне исходного кода на языке Си (точнее, на языке Си99, [15], который имеет -54-

ключевое слово restrict, означающее, что два помеченных этим словом указателя ссылаются на непересекающиеся интервалы памяти), то получится такая программа: Пример 25. Цикл с разрешенными конфликтами по доступу в память int32 * a , * b , * c , n , i ; i f (( a+n <= b || b+n <= a ) && ( c +1 <= a || a+n <= c )){ i n t * restrict A = a , * restrict B = b; int C = *c; f o r (i = 0; i < n ; i ++) A [i ] = B[ i ] * C; } else < оригинальный цикл >

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

2.5

Порядок нормализации циклов

Нередко встречаются циклы имеющие одновременно несколько свойств, неудобных для оптимизации. Например, unsigned l , u , i ; ... i = l; while ( i ++ != u ) ...

Применение специализации кода для каждого “неудобного” свойства в отдельности может привести к появлению большого количества специализрованных копий цикла, что, конечно, существенно ухудшит код. Более выгодным представляется -55-

создание только одной специализированной копии цикла и одной динамической проверки. Для приведенного примера можно было бы сделать следующую специализацию: i n t I = ( i n t )l ; i f ( l < u && u < INT_MAX ) while (++ I <= ( i n t ) u ) ... else < оригинальный цикл >

Как видно из примера, проверки, необходимые для замены оператора неравенства, для замены оператора постинкремента и для замены беззнакового типа частично пересекаются. Таким образом, мы пришли к следующему алгоритму: Алгоритм 9 приведение цикла к виду DO-цикла 1 Если условие выхода из цикла использует оператор неравенства, запомнить условия, необходимые для замены оператора неравенства на один из операторов сравнения: <, ≤, >, ≥. См. раздел 2.2. 2 Если верхняя граница цикла является полуинвариантом, запомнить условия, при которых верхняя граница будет инвариантом. См. раздел 2.4 3 Если в условии выхода из цикла участвует оператор постинкремента (постдекремента), запомнить условия, необходимые для замены этого оператора на оператор преинкремента (предекремента). См. раздел 2.3. 4 Если управляющая переменная имеет беззнаковый тип, запомнить условия, при которых можно заменить тип управляющей переменной и верхней границы на знаковый. См. раздел 2.1. 5 Если в пп. 1-4 были запомнены некоторые условия (таким образом, цикл не является DO-циклом по определению 8), при выполнении которых цикл можно записать в виде DO-цикла, то

-56-

5.1 Если все запомненные условия выполнены во время компиляции (т. е. в этом можно убедиться, например, при помощи анализа интервалов значений), записать цикл в виде DO-цикла без применения специализации кода. Например, если цикл с беззнаковой управляющей переменной имеет константные границы 0 и 100: for(unsigned i=0;i<100;i++)... 5.2 Если некоторые из запомненных условий выполнены во время компиляции, исключить их. Например, цикл с беззнаковой верхней границей имеет константную нижнюю границу 0: for(int i=0;i<=unigned_n;i++)... 5.3 Исключить

дублируемые

for(unsigned i=l;i!=u;i++)

условия. уcловиями

Например, будут:

l

<

для

цикла

INT _MAX,

u < INT _MAX, l < u. Эти три условия частично дублируют друг друга, и можно оставить только два из них: u < INT _MAX, l < u. 5.4 Произвести специализацию кода по оставшимся условиям и записать специализированный цикл в виде DO-цикла.

2.6

Ограничения применения специализации кода

Если есть возможность произвести нормализацию цикла без применения специализации кода (то есть без дублирования кода и вставки динамической проверки условий), то это необходимо делать в любом случае. Применение специализации кода требует особой аккуратности, поскольку во многих случаях специализация может замедлить программу. Так, например: • Не следует проводить специализацию для циклов, содержащих сложное управление (например, вложенные циклы), вызовы функций (кроме простых, таких, как abs) или операторы throw, try, catch. Для таких циклов эффект от нормализации будет минимален, а затраты — велики. • При наличии профиля пробного забега следует избегать специализации циклов с малым (например, менее 5) средним числом итераций.

-57-

• Как правило, следует проводить специализацию, если после этого цикл будет пригоден для автоматической параллелизации, программной конвейеризации (software pipelining), динамического разрешения конфликтов по памяти, замены операций с памятью на скаляры (scalar replacement, [17, §6.3.8]) или других трансформаций, в особенности, если известно, что цикл исполняется достаточно часто (например, занимает не менее 0.001 от общего времени исполнения программы), а среднее количество итераций велико (например, не менее 5). Перечисленные условия (эвристики) не претендуют на полноту и точность, однако их использование позволяет добиться хороших результатов.

2.7

Результаты

Описываемые в данной главе проблемы управляющей переменной характерны для пяти тестов из набора SPEC CPU2000 (четырех из SPECint2000 и одного из SPECfp2000). Все пять тестов написаны на языке Си и представляют различные области программирования. Общее для этих тестов — частое использование проблемных конструкций, описанных в разделах 2.1, 2.2, 2.3 и 2.4. В остальных 11-ти тестах, написанных на Си и Си++, данные проблемы встречаются крайне редко (или не встречаются вовсе) и не влияют на производительность и время компиляции. В таблице 7 приведено количество циклов из программ пакета SPEC CPU2000, имеющих 1. беззнаковую управляющую переменную (un), 2. оператор неравенства в условии завершения цикла (ne), 3. оператор постинкремента в условии цикла (pi), 4. полуинвариантную верхнюю границу (up).

-58-

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

ne,pi

1 2 3 4

2 5 4 1

2 25 0 0

1

1

0

Проблемы структуры цикла ne,pi,un ne,un un up SPECint2000 2 7 6 0 2 0 7 1 0 0 0 16 0 0 0 8 SPECfp2000 0 1 280 1

up,un 0 0 0 0 8

В результате проведения специализации циклов увеличился размер промежуточного представления программ и, как следствие, время компиляции; размер результирующего кода также увеличился (см. таблицу 8). Благодаря нормализации структуры управляющей переменной удалось получить заметный прирост производительности: см. таблицу 9 и рис. 2. Только один из видов нормализации (а именно, вынос из цикла полуинвариантной верхней границы) может принести выгоду сам по себе, поскольку из цикла выносится оператор считывания из памяти. Основной же причиной получения заметного выигрыша является тот факт, что увеличиваются возможности для следующих трансформаций: • программная конвейеризация, • динамическое разрешение конфликтов по памяти, • автоматическая параллелизация. В таблице 10 приведено количество циклов, дальнейшая оптимизация которых стала возможна благодаря нормализации структуры управляющей переменной. -59-

Таблица 8. Увеличение времени компиляции и размера кода в результате нормализации циклов Тесты SPECint2000 1 2 3 4 SPECfp2000 1

Увеличение времени компиляции

Увеличение кода

2% 1% 3% 1%

4% 2% 6% <1%

25%

20%

размера

Таблица 9. Результат нормализации структуры управляющей переменной Тесты SPECint2000 1 2 3 4 SPECfp2000 1

Прирост производительности 3% 2% 1% 1% -1%

Отрицательный результат, полученный на одном из тестов, объясняется следующим образом. Ряд “горячих” циклов теста имеет беззнаковую управляющую переменную; после нормализации этих циклов становится возможным динамическое разрешение конфликтов по памяти, что приводит к большому количеству динамических проверок и увеличению кода. Профиль управления, полученный на данных train, показывает, что среднее количество итераций этих циклов — более 100. Однако при запуске с данными ref, все эти циклы имеют в среднем 2 итерации, т. е. удельный вес динамических проверок велик, а выигрыш от нормализации — мал. Стоит заметить, что на данных train нормализация циклов приводит к ускорению теста на 3%. Любая специализация кода безусловно относится к разряду “агрессивных” оптимизаций, т. е. оптимизаций, которые могут ухудшить производительность. В случае -60-

Таблица 10. Число трансформаций, ставших возможными в результате нормализации структуры управляющей переменной Тесты

SPECint2000 1 2 3 4 SPECfp2000 1

Динамическое разрешение конфликтов по памяти

Программная конвейеризация

Автопараллелизация

1 19 16 3

12 37 18 9

3 17 3 9

75

60

53

нормализации структуры управляющей переменной можно обойтись и без специализации кода — если программист сам исправит исходный код. Для удобства поиска циклов с ненормализованной структурой в компиляторе была реализована опция, по которой выводятся сообщения обо всех таких циклах. Изменение исходных кодов программ пакета SPEC CPU2000 “вручную” принесли приблизительно такой-же результат, что и автоматическая нормализация, за тем исключением, что ни один тест не замедлился.

2.8

Выводы

• Проанализированы следующие проблемы, связанные со структурой управляющей переменной цикла: – использование управляющей переменной, имеющей беззнаковый целый тип; – использование оператора != вместо оператора < в условии завершения цикла; – использование оператора постинкремента в условии завершения цикла; – использование глобальной переменной (или оператора считывания из памяти) в качестве верхней границы цикла. -61-

Все перечисленные проблемы характерны для программ на языках Си и Си++ (а также Java и C#). В программах на языке Фортран такие проблемы отсутствуют. • Исследованы методы нормализации структуры управляющей переменной с применением специализации кода, способные нормализовать циклы, содержащие несколько описанных проблем одновременно. • Основным практическим результатом главы является реализация разработанных алгоритмов в компиляторе Sun, позволившая повысить производительность реальных программ (до 3% на тестах пакета SPEC CPU2000). • Основная причина повышения производительности при нормализации структуры управляющей переменной — возможность проведения дальнейших трансформаций, в том числе автопараллелизации и программной конвейеризации. • Проведенные эксперименты показывают, что в некоторых случаях нормализация циклов может привести к небольшому замедлению программ, особенно в том случае, если не используется профиль управления или он неадекватен. Однако, использование адекватных тренировочных данных обеспечивает отсутствие такого эффекта.

-62-

3

Профилирование значений выражений для специализации кода В тех случаях, когда возможно вычислить значение переменной или выражения

во время компиляции, компилятор может заменить данную переменную или выражение на соответствующее значение. Такую оптимизацию называют, как правило, распространением константных значений (constant propagation, [41]). Практически все оптимизирующие компиляторы реализуют данный вид оптимизации. В реальных программах нередко случается так, что некоторое выражение принимает всего несколько различных значений или даже ровно одно значение, но узнать это во время компиляции невозможно. Другая ситуация, возникающая достаточно часто, заключается в том, что некоторое выражение принимает много различных значений, но одно из этих значений — принимает “большую часть времени”. Зная статистическое распределение значений выражений в “горячих” участках программы, мы могли бы увеличить скорость выполнения программы, оптимизируя ее “вручную” или при помощи оптимизирующего компилятора. Такого рода статистическую информацию часто называют профилями значений (value profiles). В первой работе [26], посвященной профилям значений, ее авторы (Calder, Feller и Eustace) представляют метод профилирования значений, названный ими таблицей N верхних значений (Top N Value table, TNV); этот метод позволяет ответить на вопрос: какие N значений принимаются данным выражением чаще всего? Для каждого профилируемого выражения (или переменной) создается таблица фиксированной длины N (например, N = 10). Каждый элемент таблицы содержит значение (того же типа, который имеет профилируемое выражение) и счетчик. В начале программы таблица очищается. Профилирование осуществляется специальной функцией, которая добавлена к исходной программе и вызывается в точках профилирования. Эта функция сравнивает значение профилируемого выражения со всеми значениями, хранящимися в таблице. Если текущее значение найдено в таблице, соответствующий счетчик увеличивается; в противном случае, если таблица

-63-

еще не полна, текущее значение добавляется к таблице, а счетчик устанавливается равным 1. Если таблица заполнена, данное значение игнорируется. Через некоторые промежутки времени несколько элементов таблицы, имеющих наименьшие счетчики, удаляются. Метод TNV не дает точных профилей значений, т. е. в некоторых случаях собранные профили могут отличаться от реальных. Однако Calder и др. показывают, что различие между собранными и реальными профилями невелико и что правильные верхние значения определяются в 98% случаях. Еще одним важным фактом, полученным Calder и др., является то, что значение ноль оказывается наиболее частым верхним значением TNV таблиц. В той же статье представлены профили значений выражений, полученные для программ тестового набора SPEC CPU95; эти профили показывают, что значения в большой степени предсказуемы вне зависимости от набора входных данных. В следующей работе тех же авторов [25] показано, что, используя профилирование значений для автоматической (при помощи компилятора) специализации кода, можно добиться 15-ти процентного увеличения скорости для некоторых программ из набора SPEC CPU95. Основная проблема метода TNV заключается в том, что инструментированная программа получается очень большой и медленной. Calder и др. предлагают использовать конвергентное профилирование (convergent profiling): через некоторое время после начала работы инструментированной программы TNV таблица достигает устойчивого состояния и профилирующий код может быть выключен. В статье [49] Watterson и Debray описывают целевое (goal-directed) профилирование значений: основанный на TNV метод профилирования значений, который не профилирует те выражения, которые оптимизировать бессмысленно. Но даже такой подход замедляет инструментированную программу в 1.5-4.5 раз по сравнению с неинструментированной. В данной главе описывается другой метод профилирования значений, который создает быстрые инструментированные программы и в то же время позволяет получить ответ на вопрос: как связаны между собой наиболее частые значения раз-

-64-

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

3.1

Специализация кода по конкретным значениям инвариантов

В главе 2 мы исследовали применение специализации кода для нормализации структуры управляющей переменной. В предыдущей главе (стр. 42) был приведен анализ применения специализации кода к участку кода C и условию α. Здесь, как и в предыдущей главе, участок C будет циклом. Условием α будет условие равенства одного или нескольких инвариантов цикла некоторым конкретным значениям. Пример 26. Специализация кода: простой пример цикла f o r (i = 0; i < n ; i ++){ a[ i ] = c[i ] * A ; b[ i ] = d[i ] * B ; c[ i ] *= C; }

В примере 26 мы видим три инварианта: A, B и C. Для нас не имеет особого значения, какого типа данные переменные: целого или плавающего. Если во время компиляции известно, что A принимает значение 0 “достаточно часто”, то компилятор может произвести следующую специализацию:

-65-

Пример 27. Специализация по значению одной переменной i f ( A == 0){ f o r (i = 0; i < n ; i ++){ a [i ] = 0; b [i ] = d[ i ] * B; c [i ] *= C ; } } else { // з д е с ь расположен исходный цикл }

Если компилятору известно, что условия A==0 и B==1 “достаточно часто” выполняются одновременно, то он может произвести еще более агрессивную трансформацию: Пример 28. Специализация по значениям двух переменных i f ( A == 0 && B == 1){ f o r (i = 0; i < n ; i ++){ a [i ] = 0; b [i ] = d[ i ]; c [i ] *= C ; } } else { // з д е с ь расположен исходный цикл }

В данной главе мы рассмотрим только случаи, похожие на пример 26, т. е. случаи, для которых условие α имеет следующий вид:

α : v1 = c1 ∧ v2 = c2 ∧ . . . ∧ vn = cn

(3)

где vi , i = 1..n — различные инварианты цикла, а ci , i = 1..n — некоторые константы. Следующие эвристики можно использовать для выбора инвариантов v и -66-

констант c : • v — один из операндов операции умножения и c = 0, или • v — один из операндов операции умножения и c = 1, или • v — левый операнд операции деления и c = 0, или • v — правый операнд операции деления и c = 1 • и другие. Для цикла L, имеющего в среднем Iter(L) итераций и тела цикла B, уравнение (2) (стр. 43) можно записать в следующем виде:

Benefit(α) = Freq(α)Iter(L)(Cost(B) − Cost(Bα )) − Cost(α)

(4)

Модифицированное тело цикла Bα получается путем простой подстановки значений ci вместо vi и последующим проведением алгебраических упрощений. Задача вычисления стоимости выполнения произвольного фрагмента кода, такого, например, как тело цикла B, крайне сложна, в особенности, если B имеет сложный поток управления. Выражение Cost(B) − Cost(Bα ) намного проще и поэтому может быть вычислено компилятором с достаточной точностью16 . Поскольку выражение (3) имеет предельно простую форму, компилятор имеет возможность вычислить Cost(α) практически точно. Среднее число итераций цикла Iter(L) может быть получено из профиля управления (basic block profile). Таким образом, единственным неизвестным членом уравнения (4) является Freq(α). Один из способов определения значения Freq(α) — использование метода TNV таблицы ([26]). В следующем разделе будет предложен еще один способ оценки Freq(α), также использующий профилирование. 16

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

-67-

3.2

Профилирование значений выражений

Как правило, профилированием называется трехфазный процесс сбора и анализа статистической информации. Процесс включает в себя следующие фазы: 1. Инструментирование Программа компилируется в режиме профилирования, включая профилирование управления (см., например, [19]) и профилирование конкретных значений (см. раздел 3.2.1). В ходе этой фазы компилятор выбирает переменные v и константы c, используя приведенные выше эвристики (стр. 67) и добавляет код, отвечающий за профилирование значений. 2. Пробный запуск Программа выполняется с некоторыми тренировочными данными. Чем более характерные данные будут использованы на этой фазе, тем выше будет скорость программы, полученной на следующем шаге. 3. Использование профиля Программа компилируется с использованием профиля управления и профиля значений, полученных в ходе тренировочного запуска программы. На этой стадии компилятор имеет полную информацию для вычисления Freq(α) (см. раздел 3.2.2) и может решить, где и как производить специализацию кода. Использовать профиль можно также “вручную”, т. е. без применения компилятора. 3.2.1

Инструментирование программы

Сначала покажем, как может быть использовано профилирование значений на простом примере 26 (стр. 65). Предположим, что A — единственная переменная, которую мы хотим профилировать, а 0 — единственное значение переменной A, которое нас интересует. Каждый раз, когда начинается выполнение цикла, существует ровно две взаимо исключающие возможности: переменная A либо равна 0, либо нет. -68-

Следующий фрагмент кода демонстрирует простой способ собрать информацию о переменной A. Пример 29. Простое профилирование значения 1

s t a t i c int64_t Acounters [2] = {0 ,0};

2

Acounters [A ==0]++;

3

// Содержимое A c o u n t e r s [ ] записывается

4

// на диск по окончании программы .

5

f o r (i = 0; i < n ; i ++) ...

В приведенной программе создается статический масив Acounters, содержащий два элемента. Когда программа первый раз доходит до строки 1, оба элемента массива устанавливаются равными нулю. Затем, каждый раз, когда программа доходит до строки 2, в зависимости от значения A==0 один из элементов массива увеличивается на единицу. Непосредственно перед завершением программы содержимое массива Acounters при помощи некоторого внешнего кода сохраняется на диске. Значение Acounters[1] будет представлять то число, сколько раз переменная A принимала значение 0, а Acounters[0] — сколько раз переменная A не была равна 0. Автором был реализован описываемый метод профилирования значений в оптимизаторе высокого уровня компилятора Sun (см. Приложение). Но для простоты изложения в данном разделе будет описано, как профилирование значений могло бы быть реализовано в виде трансформаций исходного кода на языке C++. Далее нам понадобится класс PVP (Particular Value Profilier), приведенный в примере 30. С использованием класса PVP простой пример профилирования (пример 29) можно переписать следующим образом: Пример 31. Использование класса PVP { s t a t i c PVP vp ( some_unique_id , 2); vp (A ==0); } f o r (i = 0; i < n ; i ++) ...

-69-

Пример 30. Класс PVP c l a s s PVP { int64_t * counters ; i n t ID , N; public: // Конструктор . Инициализировать c o u n t e r s , N , ID PVP ( i n t id , i n t n ): ID ( id ) , N (n ){ counters = new int64_t [N ]; memset ( counters , 0 , N* s i z e o f ( int64_t )); } // Деструктор . Записать содержимое // массива ’ c o u n t e r s ’ , а так же // ’N ’ и ’ ID ’ в некоторый файл на диске . ~ PVP (); // увеличить один элемент ’ c o u n t e r s ’ на 1 // в с о о т в е т с т в и и со значением ’ e x p r ’ . // Значение ’ e x p r ’ должно быть // в интервале [ 0 , N−1] void operator ()( i n t expr ){ counters [ expr ]++; } };

Здесь создается статический объект vp типа PVP, которому сопоставляется некоторый уникальный номер some_unique_id. Объект vp содержит два счетчика, инициализированных нулем. Каждый вызов PVP::operator() увеличивает один из этих счетчиков на единицу. По завершении программы объект vp разрушается (is destructed) и значения счетчиков записываются на диск. Если нам необходимо профилировать три значения переменной A: 0, -1 и 1, то код будет выглядеть следующим образом. Пример 32. Профилирование трех значений s t a t i c PVP vp ( some_unique_id , 4); vp (( A ==0)+2*( A ==1)+3*( A == -1));...

В общем случае, если необходимо профилировать k булевых предиката, попарно исключающих друг друга, индексное выражение (выражение, передаваемое в PVP::operator()) будет иметь такой вид:

Index =

k X

iPi ,

i=0

-70-

Index ∈ [0, k]

(5)

где Pi ∈ {0, 1}, i = 1..k — заданные предикаты, P0 =

Vk

i=1 (Pi

= 0),

Pk

i=0 Pi

= 1.

При профилировании значений двух различных переменных A и B соответствующие предикаты не будут исключать друг друга, т. е. A==0 и B==1 может быть выполнено одновременно. В общем случае, для профилирования l различных предикатов P j ∈ {0, 1}, j = 1..l, которые не исключают друг друга (т. е.

Pl

j=1 P

j

∈ [0, l])

необходимо следующее индексное выражение:

Index =

l X

2j−1 P j ,

Index ∈ [0, 2k )

(6)

j=1

Таким образом, индексным выражением для для предикатов A==0, B==1 и C==0 будет (A==0)+2*(B==1)+4*(C==0). Теперь мы можем объединить выражения (5) и (6). Если у нас имеется l наборов предикатов, каждый из которых содержит kl булевых предикатов, попарно исключающих друг друга, то индексное выражение будет таким:

Index =

k1 X

iPi1

+ K1

i=0

k2 X

iPi2

+ ...+

i=0

l−1 Y

Kj

j=1

Kj = kj + 1, j = 1..l,

Index ∈ [0,

kl X

iPil

(7)

i=0 l Y

Kj )

j=1

где верхний индекс предиката обозначает номер набора, а нижний — номер элемента в наборе. Как и в уравнении (5),

P0j =

kj ^

(Pij = 0), j = 1..l

i=1

Если нам необходимо профилировать значения 0 и 1 для трех переменных A, B и C, то, исходя из уравнения (7), нам понадобится следующий код: Пример 33. Профилирование трех переменных // 2 7 = 3 ∗ 3 ∗ 3 s t a t i c PVP vp ( uniq_id , 27); vp ( (( A ==0)+2*( A ==1)) +

-71-

3*(( B ==0)+2*( B ==1)) + 9*(( C ==0)+2*( C ==1)));...

3.2.2

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

Во время пробного запуска инструментированная программа записывает собранную статистику в файл. Далее, во время фазы использования профиля, компилятор считывает данную статистику из файла. Для инструментированной программы, приведенной в примере 33, файл со статистикой будет содержать 27 значений счетчиков, собранных для значений 0 и 1 переменных A, B и C. При считывании файла, компилятор поместит счетчики в некоторый массив, например counters. Сумма всех счетчиков будет равна общему числу исполнений цикла (назовем это число Total). Первый счетчик, counters[0], будет соответствовать числу раз, когда ни одна из переменных A, B и C не принимала значения 0 или 1. А, например, counters[7] (counters[1+3*2+9*0]) будет соответствовать числу раз, когда условия A==0, B==1 и C!=0 && C!=1 выполнялись одновременно. Для принятия решения о специализации кода и для выбора условного выражения α, компилятору необходимо вычислить Benefit(α) для всех возможных условий α и затем найти максимальный выигрыш. Если максимальный выигрыш “достаточно велик” (и, по крайней мере, положителен), компилятор произведет специализацию кода. В соответствии с уравнением (4) для вычисления Benefit(α) необходимо знать только Freq(α). Используя собранные профили значений, компилятор может вычислить Freq(α) для всех α. Предположим, что профилировались переменные vj , j = 1..l и их соответствующие значения cji , j = 1..l, i = 1..kj , kj = 1, 2, ... В примере 33 имеем: n = 3, v1 = A, v2 = B, v3 = C, k1 = k2 = k3 = 2, c11 = c21 = c31 = 0, c12 = c22 = c32 = 1. Все условные выражения α будут иметь вид vj1 = cji11 ∧ vj2 = cji22 ∧ . . . ∧ vjn = cjinn

-72-

(8)

где 1 ≤ n ≤ l и 1 ≤ j1 < j2 . . . < jn ≤ l. Вот несколько возможных условных выражения для нашего примера: A==0, (A==1)&&(C==0), (A==0)&&(B==0)&&(C==1). В общем случае (см. уравнение (7)) условие α будет иметь вид Pij11 ∧ Pij2n ∧ . . . ∧ Pijnn Мы можем вычислить Freq(α) для всех α, используя рекуррентные соотношения (9) и (10). Если n = l, т. е. уравнение (7) содержит l переменных, то Freq(α) равно одному соответствующему счетчику, деленному на сумму всех счетчиков:

Freq(Pi11 ∧ Pi22 ∧ . . . ∧ Pill ) =

counters[i1 + K1 i2 + . . . + K1 K2 . . . Kl−1 il ] Total

(9)

Если уже вычислены Freq(α) для всех α, содержащих n переменных, мы можем вычислить частоты для условных выражений, содержащих n − 1 переменную. Freq(Pij11

∧...∧

jn−1 ) Pin−1

=

kj X

j

n−1 ∧ Pij ) Freq(Pij11 ∧ . . . ∧ Pin−1

(10)

i=0

где j — любой номер набора предикатов, не входящий во множество j1 . . . jn−1 . Проведенные в рамках данной работы эксперименты показали, что в большинстве случаев есть всего несколько (как правило, один или два) элементов массива counters, которые существенно превосходят все остальные элементы, т. е. только небольшое количество условных выражений α выполняются “достаточно часто”. В таких случаях можно пользоваться непосредственно уравнением (9) для выбора нескольких условий с максимальными частотами, вместо вычисления частот всех условий.

3.3

Результаты

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

-73-

вого набора SPEC CPU2000 (все из SPECfp200017 ). В таблице 11 приведено количество точек профилирования, созданных компилятором на этих пяти программах (в процессе инструментирования), и количество произведенных специализаций кода (по результатам полученного профиля). Каждая точка профилирования собирает статистику по одному или нескольким выражениям одновременно. Каждая специализации также производится по значениям одного или нескольких выражений. Количество выражений также отражено в таблице. Для оценки полезности трансформации кода помимо уравнения (4) использовалась “запрещающая” эвристика

(11)

Freq(α) ≥ 50%

Таблица 11. Количество точек профилирования и специализаций кода Тесты 1 2 3 4 5

Точек профилирования: 1 выр. 2-3 выр. 4-8 выр. 9 760 269 1 11 0 4 142 51 29 669 81 6 180 20

Специализаций: 1 выр. 2-3 выр. 4-8 выр. 4 5 0 1 0 0 2 15 4 1 0 0 4 0 0

Проведенные эксперименты показали, что при использовании профилирования значений время исполнения инструментированной программы увеличивается менее чем на 10% (см таблицу 12). В той же таблице приведена статистика по увеличению времени компиляции и размеру кода, а в таблице 13 — полученное ускорение (см. также рис. 2). Уменьшение скорости работы одного из тестов объясняется (как и в предыдущей главе, см. 2.7) различием между профилями для входных данных train и ref. Для входных данных train специализация кода на основе профиля, полученного на этих же данных, позволяет получить около 2% ускорения. 17 Из этого не стоит делать вывод, что подобные ситуации не встречаются в целочисленных программах: см. [25].

-74-

Таблица 12. Замедление инструментированной программы, увеличение времени компиляции и размера кода в результате специализации по профилю значений Тесты

1 2 3 4 5

Замедление инструментированной программы <1% 7% 5% 6% 8%

Увеличение времени компиляции

Увеличение размера кода

2% 3% 4% <1% 8%

0.5% 0.4% 0.6% <0.1% 0.2%

Таблица 13. Результат применения специализации по профилю значений Тесты 1 2 3 4 5

Прирост производительности 10% 5% 1% 0% -1%

В данной главе представлен лишь один частный случай применения профилирования конкретных значений выражений — специализация циклов по значениям инвариантов. В дальнейшем возможно существенно расширить область применения профилирования значений. Перечислим несколько возможных вариантов применения профилирования значений: • Профилирование значений операндов “дорогих” операций (таких, как деление), не обязательно являющихся инвариантами охватывающего цикла, — позволит производить снижение стоимости “дорогих” операций. • Профилирование предикатов, связанных с разрешением конфликтов по доступу в память (стр. 2.4), — позволит производить специализацию кода только в тех случаях, когда это действительно необходимо. • Профилирование предикатов, связанных с запоминанием результатов вызо-75-

Рис. 2. Прирост производительности вов функций (function memoization, [17, §6.6.8]) или с запоминанием других вычислений.

3.4

Выводы

• Предложен метод профилирования значений, не составляющий полного профиля выражения, а только собирающий статистику для некоторых конкретных возможных значений выражения. Такой подход позволяет создавать очень быстрый инструментирующий код. • Простота профилирования конкретных значений позволяет дополнительно собирать информацию о взаимосвязи значений нескольких выражений, что дает возможность проводить специализацию кода сразу для нескольких пере-76-

менных (или выражений). • Основным практическим результатом данной главы является реализация описанных методов профилирования значений для специализации циклов. Эти методы позволили получить большое увеличение производительности реальных программ (до 10% на тестах пакета SPEC CPU2000). • Специализация кода по профилю значений может стать причиной снижения производительности, если данные для пробного запуска программы подобраны неверно или если компилятор использует неверные эвристики для оценки полезности специализации. Эксперименты, проведенные в рамках данной работы, показали, что подобранные эвристики дают хорошие результаты при использовании адекватных данных для пробного запуска.

-77-

Заключение 1. Разработаны новые алгоритмы идентификации и символьного анализа индуктивных переменных и выражений, а также управляющей переменной. На основе данных алгоритмов разработаны алгоритмы оптимизации: подстановка индуктивных переменных и снижение стоимости индуктивных выражений. Новые алгоритмы позволяют: • обрабатывать индуктивные переменные с несколькими присваиваниями; • учитывать взаимосвязь между различными индуктивными переменными; • анализировать и оптимизировать операторы преобразования типов, примененные к индуктивным переменным и выражениям; • трансформировать операторы деления индуктивного выражения на константу. 2. Проведен детальный анализ проблем, возникающих в программах на языках Си и Си++, и связанных с нестандартными способами описания управляющей переменной. Предложен механизм решения этих проблем с применением специализации кода. Рассмотрены следующие случаи и их комбинации: • использование управляющей переменной, имеющей беззнаковый целый тип; • использование оператора != вместо оператора < в условии завершения цикла; • использование оператора постинкремента в условии завершения цикла; • использование глобальной переменной (или оператора считывания из памяти) в качестве верхней границы цикла. 3. Разработан метод быстрого профилирования конкретных значений выражений, учитывающий взаимозависимость значений нескольких различных вы-78-

ражений. На основе этого метода разработан механизм специализации кода по профилю значений. 4. Показано, что исследованные методы оптимизации, использующие специализацию циклов, являются “агрессивными”, т. е. в некоторых случаях могут ухудшить производительность. Однако, проведенные эксперименты доказали, что использование адекватных тренировочных данных при многофазной схеме компиляции обеспечивает отсутствие отрицательного результата. 5. Все исследованные методы анализа и оптимизации циклов реализованы в оптимизирующем компиляторе для платформы SPARC, что является важным практическим результатом работы. 6. Все предложенные методы оптимизации являются универсальными, т. е. не привязаны к конкретной архитектуре, конкретному компилятору или набору тестовых задач. 7. Реализованные оптимизации позволяют существенно повысить производительность реальных программ. На программах тестового набора SPEC CPU2000 был получен прирост производительности до 12%. Разработка и исследование в области высокоуровневых оптимизаций циклов осуществлялась (и продолжает осуществляться) в рамках проекта оптимизатора промежуточного представления iropt (см. приложение), проводимого совместно фирмами ЗАО “МЦСТ” и Sun Microsystems с 1992 года. Автором были разработаны и реализованы все оптимизации, предложенные в главах 1, 2 и 3. В заключение автору хотелось бы поблагодарить всех специалистов, принимавших (и принимающих) участие в проекте iropt, в том числе: С. Гурьева, Е. Черниса, В. Яковлева, В. Броля (Россия) и X. Kong, Б. Синдеева (США). Я выражаю глубокую признательность руководителю проекта iropt г-ну J.-Z. Wang за проявленное понимание и предоставленную возможность работать над диссертацией. Особо хочу поблагодарить моего научного руководителя к.т.н. В.Ю. Волконского и проф. В.В. Шилова, без которых данная работа не могла бы осуществиться. -79-

Приложение. Внутренняя структура компилятора фирмы Sun В данном разделе дано описание структуры компилятора фирмы Sun для платформы SPARC (далее: компилятор) и основных режимы компиляции. Более подробно с компилятором можно ознакомиться в [41, §21.1.2] и на сайте производителя [51]. Некоторые важные ключи компиляции: -xO1, -xO2 Производить ограниченное количество локальных оптимизаций. -xO3 Производить трансформации выражений, содержащих глобальные переменные, и операции чтения и записи в память; производить программную конвейеризацию. -xO4, -xO5 Производить межпроцедурный анализ и оптимизацию. -xparallel, -xreduction Производить автоматическое распараллеливание кода. -xprofile Создать

инструментированный

исполняемый

файл

(-xprfile=collect). Использовать профиль, полученный в результате пробного прогона программы (-xprilfe=use). -xarch=v9 Включить 64-битный режим компиляции (для архитектуры SPARC-v9). -fast Включить режим -xO5 и ряд других дополнительных режимов. -xipo=2 Включить режим межфайлового межпроцедурного анализа и оптимизаций. Для большинства экспериментов, проведенных в рамках данной работы, была использована следующая комбинация флагов: -fast -xparallel -xreduction -xarch=v9 -xprofile Компилятор состоит из следующих основных частей (см. также рис. 3): -80-

frontends Компиляторы переднего плана (front end) для языков C, C++, Fortran90. Данные модули отвечают за лексический и синтаксический разбор входного языка, проверку семантики и генерацию промежуточного представления программы. Промежуточное представление называется Sun IR (Intermediate representation). iropt Глобальный

оптимизатор

высокого

уровня,

называемый

iropt

(IR

OPTimizer). Iropt принимает на входе Sun IR, созданный компилятором переднего плана, производит различные трансформации и на выходе выдает модифицированный Sun IR. cg Оптимизирующий генератор кода (Sparc Code Generator, cg). Cg получает на входе Sun IR, преобразует его в другое внутреннее представление asm+ (ассемблер с дополнительной информацией), производит ряд оптимизирующих трансформаций (в том числе, программную конвейеризацию) и создает на выходе объектный файл (или программу на ассемблере). yabe Быстрый генератор кода yabe (Yet Another Back End). Работает после компилятора переднего плана в том случае, если не задано никакого уровня оптимизации. Создает объектный файл (или программу на ассемблере). Глобальный оптимизатором iropt производит следующие трансформации в данном порядке (перечислены лишь некоторые основные фазы и фазы, описанные в данной работе). • Инструментирование программы (при -xprofile=collect) и сбор полученного профиля (при -xprofile=use). Включает в себя профилирование значений выражений (раздел 3.2.1). • Межпроцедурный анализ и трансформации: встраивание (inlining), клонирование функций (procedure cloning), и т. п. • Нормализация структуры управляющих переменных (глава 2).

-81-

• Трансформации циклов, включая автоматическую параллелизацию, перестановку циклов, и многие другие. На данном этапе применяется подстановка индуктивных переменных (раздел 1.4). • Специализация кода по профилям значений выражений (раздел 3.2.2). • Скалярные трансформации: алгебраические трансформации, реассоциация, оптимизация условных переходов и т. д. • Снижение стоимости индуктивных выражений (раздел 1.5). • Глобальный сбор общих подвыражений (common subexpression elimination, cse), вынос инвариантов цикла и т. д.

Рис. 3. Структура оптимизирующего компилятора Sun

-82-

Список литературы [1] И. Л. Дьячков, К. С. Серебряный. Профилирование значений выражений для оптимизации программ // XXIX Гагаринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, 2003. С. 20–21. [2] К. С. Серебряный. Методы оптимизации программ, использующие дублирование кода // Новые материалы и технологии. Тезисы докладов Всероссийской научно-технической конференции, Т. 3, 2002. С. 40–41. [3] К. С. Серебряный. Трансформации циклов, производимые оптимизирующими компиляторами // Современные проблемы фундаментальных и прикладных наук. Научная конференция МФТИ. Часть I: Радиотехника и кибернетика. Москва–Долгопрудный, 2002. С. 42–43. [4] К. С. Серебряный. Способ оптимизации программ с использованием раскрутки циклов // Информационные технологии 2003, N 1. С. 12–15. [5] К. С. Серебряный. Трансформации циклов, содержащих индуктивные переменные // Информационные технологии 2003, N 9. С. 22–29. [6] К. С. Серебряный. Нормализация структуры циклов // XXX Гагаринские чтения. Международная молодежная научная конференция. Тезисы докладов Т. 5, 2004. С. 56. [7] А. И. Голуб. С и С++. Правила программирования // М.: Восточная Книжная Компания, 1996. [8] В. Н. Касьянов, В. А. Евстигнеев. Графы в программировании: обработка, визуализация и применение // СПб.: БХВ-Петербург, 2003. [9] Д. Э. Кнут. Искусство программирования, 3-е изд. // М.: Вильямс, 2000. [10] Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ // М.: МЦНМО, 1999.

-83-

[11] Д. Прохоров, А. Исаев. Использование компиляторов Intel и программных средств набора Intel Threading Toolkit для создания, оптимизации и отладки одно- и многопотоковых приложений // Материалы форума Intel для разработчиков, октябрь 2002 (CD-ROM). [12] Б. Страуструп. Язык программирования С++. 3-е изд. // М.: БИНОМ, 1999. [13] Д. Д Ульман, А. В. Ахо, Р. Сети. Компиляторы: принципы, технологии и инcтрументы // М.: Вильямс, 2001. [14] Фортран 90. Международный стандарт // М.: Финансы и статистика, 1998. [15] С. П. Харбисон, Г. Л. Стил. Язык программирования С //М.: Бином–Пресс, 2004. [16] G. Aigner, U. H¨olzle. Eliminating virtual function calls in C++ programs // Lecture Notes in Computer Science, 1098, 1996. [17] D. F. Bacon, S. L. Graham, O. J. Sharp. Compiler transformations for highperformance computing // ACM Computing Surveys, 26(4), pp. 345–420, 1994. [18] T. Ball, J. R. Larus. Optimally profiling and tracing programs // ACM Transactions on Programming Languages and Systems, 16(4), pp. 1319–1360, July 1994. [19] T. Ball, J. R. Larus. Efficient path profiling // In International Symposium on Microarchitecture, pp. 46–57, 1996. [20] U. Banerjee. Dependence Analysis. Loop Transformations for Restructuring Compilers // Kluwer Academic Publishers, Boston, MA., 1997. [21] D. Bernstein, D. Cohen, D. E. Maydan. Dynamic memory disambiguation for array references // Proceedings of the 27th annual international symposium on Microarchitecture, pp. 105-111, 1994. [22] W. Blume, R. Eigenmann. Symbolic range propagation // In Proceedings of the 9th International Parallel Processing Symposium, pp. 357–363, Santa Barbara, CA, April 1995. -84-

[23] W. Blume. Symbolic Analysis Techniques for Effective Automatic Parallelization // PhD thesis, Dept. of Computer Science, University of Illinois at UrbanaChampaign, June 1995. [24] M. Burrows, U. Erlingson, S.-T. Leung, M. T. Vandevoorde, C. A. Waldspurger, K. Walker, W. E. Weihl. Efficient and flexible value sampling // In Architectural Support for Programming Languages and Operating Systems, pp. 160–167, 2000. [25] B. Calder, P. Feller, A. Eustace. Value profiling and optimization // Journal of Instruction Level Parallelism, 1999. [26] B. Calder, P. Feller, A. Eustace. Value profiling // In International Symposium on Microarchitecture, pp. 259–269, 1997. [27] B. Calder, D. Grunwald. Reducing indirect function call overhead in C++ programs // In Conference Record of POPL ’94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 397–408, Portland, Oregon, 1994. [28] J. W. Davidson, S. Jinturkar. Improving instruction-level parallelism by loop unrolling and dynamic memory disambiguation // Proceedings of the 28th annual international symposium on Microarchitecture, pp. 125-132, 1995. [29] R. van Engelen. Symbolic evaluation of chains of recurrences for loop optimization // Technical report, TR-000102, Computer Science Deptartment, Florida State University, 2000. [30] P. Feller. Value profiling for instructions and memory locations // Technical repor CS98581, Department of Computer Science and Engineering, University of California, San Diego, Apr. 1998. [31] F. Gabbay, A. Mendelson. Can program profiling support value prediction? // In International Symposium on Microarchitecture, pp. 270–280, 1997. [32] D. M. Gallagher, W. Y. Chen, S. A. Mahlke, J. C. Gyllenhaal, W. W. Hwu. Dynamic memory disambiguation using the memory conflict buffer // Proceedings of the -85-

sixth international conference on Architectural support for programm ing languages and operating systems, pp. 183-193, 1994. [33] M. P. Gerlek, E. Stoltz, M. Wolfe. Beyond induction variables: Detecting and classifying sequences using a demand-driven SSA form // ACM Transactions on Programming Languages and Systems, 17(1), pp. 85–122, January 1995. [34] D. Ginsburg, B. Groose, J. Taylor, B. Vernescu. The History of the Calculus and the Development of Computer Algebra Systems // http://www.math.wpi.edu/IQP/BVCalcHist [35] M. R. Haghighat, C. D. Polychronopoulos. Symbolic Program Analysis and Optimization for Parallelizing Compilers // In Conference Record of the 5th Workshop on Languages and Compilers for Parallel Computing, Yale University, Department of Computer Science, 1992. [36] M. R. Haghighat, C. D. Polychronopoulos. Symbolic analysis for parallelizing compilers // ACM Transactions on Programming Languages and Systems, 18(4), pp. 477–518, July 1996. [37] S. P. Harbison, G. L. Steel, Jr. C, a reference manual // 1990. Third edition. Prentice-Hall, 1991. [38] W. Harrison. Compiler Analysis of the Value Ranges for Variables // IEEE Trans. on Software Engineering, vol. SE-3, no. 3, pp. 243-250, May 1977. [39] A. S. Huang, G. Slavenburg, J. P. Shen. Speculative disambiguation: a compilation technique for dynamic memory disambiguation // Proceedings of the 21ST annual international symposium on Computer architecture, pp. 200-210, 1994. [40] C.-K. Luk. Memory disambiguation for general-purpose applications // Proceedings of the 1995 conference of the Centre for Advanced Studies on Collaborative research, p 43, 1995.

-86-

[41] S. S. Muchnick. Advanced compiler design and implementation // Morgan Kaufmann Publishers Inc., 1997. [42] R. Muth. Alto: A platform for object code modification // PhD thesis, Department of Computer Science, University of Arizona, 1999. [43] R. Muth, S. A. Watterson, S. K. Debray. Code specialization based on value profiles // In Static Analysis Symposium, pp. 340–359, 2000. [44] D. A. Padua, M. J. Wolfe. Advanced compiler optimizations for supercomputers // Commun. ACM, vol. 29, no. 12, pp. 1184-1201, 1986. [45] J.R.C. Patterson. Accurate static branch prediction by value range propagation // In Proceedings of the ACM SIGPLAN ’95 Conference on Programming Language Design and Implementation, pp. 67–78, 1995. [46] E. Salami, J. Corbal, C. Alvarez, M. Valero. Cost effective memory disambiguation for multimedia codes // Proceedings of the international conference on Compilers, architecture, and synthesis f or embedded systems, pp. 117-126, 2002. [47] Y. Sazeides, J. E. Smith. The predictability of data values // In International Symposium on Microarchitecture, pp. 248–258, 1997. [48] J. Sheldon, W. Lee, B. Greenwald, S. Amarasinghe. Strength reduction of integer division and modulo operations // citeseer.nj.nec.com/503048.html [49] S. Watterson, S. Debray. Goal-directed value profiling // Lecture Notes in Computer Science, 2027, 2001. [50] S. Wolfram. The Mathematica Book, 4th ed. // Wolfram Media/Cambridge University Press, 1999. [51] http://docs.sun.com [52] http://java.sun.com [53] http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC -87-

[54] http://msdn.microsoft.com/library/en-us/csspec/html/vclrfcsharpspec_1.asp [55] http://www.stlport.org/doc [56] http://www.spec.org/cpu2000

-88-

Список примеров 1

Автоматическая параллелизация . . . . . . . . . . . . . . . . . . . . . 14

2

Замена цикла на вызов memcpy() . . . . . . . . . . . . . . . . . . . . . 15

3

Идеальное гнездо циклов . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4

Гнездо циклов после перестановки

5

Замена умножения на сложение . . . . . . . . . . . . . . . . . . . . . . 16

6

Замена сдвига на сложение . . . . . . . . . . . . . . . . . . . . . . . . . 17

7

Развертка цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

8

Индуктивные выражения . . . . . . . . . . . . . . . . . . . . . . . . . . 20

9

Обобщенная индуктивная переменная

10

Преобразование типа индуктивного выражения . . . . . . . . . . . . . 21

11

Деление индуктивных выражений на константу . . . . . . . . . . . . . 22

12

Индуктивная переменная с двумя определениями . . . . . . . . . . . . 23

13

Различные обобщенные индуктивные переменные . . . . . . . . . . . . 24

14

С-функции ОИП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

15

Подстановка ТМ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

16

Цикл do...while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

17

Снижение стоимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

18

Применения интервального анализа . . . . . . . . . . . . . . . . . . . . 42

19

Цикл с беззнаковой управляющей переменной . . . . . . . . . . . . . . 44

20

Оператор постинкремента в цикле while . . . . . . . . . . . . . . . . . 50

21

Глобальная переменная в качестве верхней границы . . . . . . . . . . 52

22

Результат считывания из памяти в качестве верхней границы . . . . . 52

23

Проверка инвариантности верхней границы . . . . . . . . . . . . . . . 53

24

Цикл с конфликтами по доступу в память . . . . . . . . . . . . . . . . 54

25

Цикл с разрешенными конфликтами по доступу в память . . . . . . . 55

26

Специализация кода: простой пример цикла . . . . . . . . . . . . . . . 65

27

Специализация по значению одной переменной . . . . . . . . . . . . . 66

28

Специализация по значениям двух переменных . . . . . . . . . . . . . 66 -89-

. . . . . . . . . . . . . . . . . . . . 16

. . . . . . . . . . . . . . . . . . 20

29

Простое профилирование значения . . . . . . . . . . . . . . . . . . . . 69

31

Использование класса PVP . . . . . . . . . . . . . . . . . . . . . . . . . 69

30

Класс PVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

32

Профилирование трех значений . . . . . . . . . . . . . . . . . . . . . . 70

33

Профилирование трех переменных . . . . . . . . . . . . . . . . . . . . 71

-90-

Список иллюстраций 1

Специализация кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2

Прирост производительности . . . . . . . . . . . . . . . . . . . . . . . . 76

3

Структура оптимизирующего компилятора Sun . . . . . . . . . . . . . 82

Список таблиц 1

Типы циклов в пакете SPEC CPU2000. . . . . . . . . . . . . . . . . . . 13

2

Результат применения нового алгоритма снижения стоимости . . . . . 36

3

Результат применения нового алгоритма подстановки ИП . . . . . . . 37

4

Количество найденных линейных индуктивных выражений . . . . . . 37

5

Количество произведенных подстановок индуктивных переменных . . 37

6

Количество распараллеленных циклов . . . . . . . . . . . . . . . . . . 38

7

Количество нормализованных циклов . . . . . . . . . . . . . . . . . . . 59

8

Увеличение времени компиляции в результате нормализации циклов

9

Результат нормализации структуры управляющей переменной . . . . 60

10

Число трансформаций нормализованных циклов . . . . . . . . . . . . 61

11

Количество точек профилирования и специализаций кода . . . . . . . 74

12

Замедление инструментированной программы . . . . . . . . . . . . . . 75

13

Результат применения специализации по профилю значений . . . . . 75

-91-

60