Содержание к диссертации
Введение
Глава первая: Основные понятия 9
1.1 Современные архитектуры и оптимизирующая компиляция 9
1.2 Основные структуры данных 13
1.2.1 Промежуточное представление 14
1.2.2 Управляющий граф 16
1.2.3 Дерево доминаторов / постдоминаторов 18
1.2.4 Дерево циклов 19
1.2.5 Форма со статически единственным присваиванием 21
1.2.6 Граф потока данных 22
1.3 Распределение регистров 24
1.4 Распределение регистров, основанное на раскраске графа несовместимости 26
1.4.1 Общее описание : 27
1.4.2 Поиск сетей 28
1.4.3 Построение графа несовместимости 32
1.4.4 Раскраска графа несовместимости 34
1.4.5 Замена виртуальных регистров на соответствующие им физические регистры 36
1.5 Выводы 37
Глава вторая: Влияние современных архитектурных механизмов на распределение регистров 38
2.1 Широкое командное слово 39
2.1.1 Влияние широкого командного слова па распределение регистров 40
2.1.2 Взаимодействие распределителя регистров и планировщика 43
2.2 Предикатность 46
2.2.1 Точное определение окончания времени жизни регистров и сетей 49
2.2.1.1 Анализ работы [gillies 1996] 50
2.2.1.2 Предварительное маркирование первых определений 52
2.2.2 Удаление "ложных несовместимостей" 60
2.2.2.1 Граф разделения предикатов 61
2.2.2.2 Новый подход к удалению "ложных несовместимостей" 62
2.2.2.3 Оптимальное объединение битовых векторов с информацией о "живых" сетях выходных дуг гиперблоков. 64
2.3 Распределение регистров разных типов 66
2.3.1 Порядок распределения регистров разных типов 68
2.3.2 Точный учет влияния различных форматов регистров 70
2.4 Выводы 72
Глава третья: Взаимодействие распределителя регистров с другими фазами оптимизирующего компилятора 76
3.1 Взаимодействие распределителя регистров с оптимизациями 76
3.2 Взаимодействие общецелевого и циклового распределителей регистров 80
3.3 Распределитель регистров, не зависящий от целевой машины 86
3.4 Выводы 92
Заключение 94
Список литературы
- Промежуточное представление
- Распределение регистров, основанное на раскраске графа несовместимости
- Взаимодействие распределителя регистров и планировщика
- Взаимодействие общецелевого и циклового распределителей регистров
Введение к работе
Сегодня вычислительная техника играет огромную роль в, без исключения, всех областях современной жизни: промышленности, торговле, обороне, науке и образовании. От надежности и быстродействия вычислительных систем зависит благополучие каждого из нас и всего общества в целом.
Сразу после своего появления в середине двадцатого века, информатика стала развиваться бурными темпами, всегда преследуя в своем развитии три цели: увеличение быстродействия, надежности и доступности вычислений. Сложно сказать, какая из этих трех целей является более важной, но, без сомнения, необходимость увеличения быстродействия вычислений невозможно оспорить.
Большую часть второй половины двадцатого века увеличение скорости достигалось, в основном, достижениями в области производства микросхем. Начиная с шестидесятых годов плотность размещения транзисторов, а значит и быстродействие микросхем, удваивается каждые несколько месяцев.
Однако же, одним лишь удвоением плотности размещения транзисторов возможности роста производительности вычислений не исчерпываются. В настоящий момент основные возможности для такого роста кроются в новаторских решениях в области архитектуры микропроцессоров и программных средств.
Последние десятилетия двадцатого века и начало века двадцать первого стали свидетелями значительных достижений в этих областях. Усилия большинства исследователей были направлены на развитие идеи параллельности вычислений, когда отдельные, независимые друг от друга части одной программы выполняются одновременно. Первоначально в микропроцессорных вычислительных системах весь анализ возможности распараллеливания проводился динамически и только на аппаратном уровне (суперскалярные архитектуры); затем распространение получили идеи статического анализа параллельности, проводимого в момент компиляции программы; при таком подходе в процессоре должны быть заложены хмеханизмы, при помощи которых компилятор мог бы сообщить процессору об обнаруженной параллельности (архитектуры с широким командным словом).
Одновременно с появлением первых вычислительных систем появились и первые оптимизирующие компиляторы, не только переводящие программу из языка программирования в язык машинных кодов, но и обеспечивающие при этом ее оптимизацию. Развитие аппаратных средств и появление специализированных аппаратных механизмов только лишь увеличило важность оптимизирующей компиляции, так как эффективное использование новых возможностей аппаратуры невозможно без поддержки со стороны компилятора.
Критически важной компонентой любого компилятора, в том числе оптимизирующего, является распределитель регистров. Без решения задачи эффективного распределения регистров оптимизации не имеют смысла. Действительно, практически все оптимизации так или иначе увеличивают число пользовательских переменных и удлиняют время их жизни, что накладывает жесткие требования к качеству распределителя регистров. При недостаточно эффективном распределении регистров оптимизирующие преобразования зачастую приводят не к улучшению, а к ухудшению скорости работы пользовательской программы.
В настоящий момент наиболее удачным подходом к распределению регистров является подход, основанный на раскраске графа несовместимости. Первые идеи о возможности использования раскраски графа при распределении регистров появились еще в 60-ых годах; окончательно они были оформлены к концу 70-ых, и с тех пор не претерпели значительных изменений.
К сожалению, достижения в области аппаратных средств привели к тому, что распределение регистров на основе раскраски графа несовместимости в своем первоначальном виде, не учитывающем новых реалий, оказалось неадекватным для современных нужд. В настоящий же момент вопросы влияния новых аппаратных механизмов и оптимизаций на распределение регистров являются все еще малоисследованными. В то же время, решение возникающих в этих условиях проблем становится крайне актуальным.
Цель диссертационной работы
Целью диссертационной работы является исследование проблем и подходов к распределению регистров, основанному на раскраске графа несовместимости, для современных вычислительных систем.
Для проведения этих исследований необходимо спроектировать и реализовать распределитель регистров, учитывающий новые аппаратные возможности современных вычислительных систем, и взаимодействующий в своей работе с другими компонентами оптимизирующего компилятора.
Для достижения поставленной цели в работе выполняются следующие этапы:
• Исследование влияния аппаратных механизмов вычислительных систем и других компонент оптимизирующего компилятора на задачу распределения регистров;
• Разработка подходов, методов и алгоритмов, наиболее эффективным образом учитывающих это влияние при распределении регистров;
• Оптимизация алгоритмической сложности разработанных алгоритмов;
• Реализация разработанных алгоритмов в составе распределителя регистров оптимизирующего компилятора архитектуры Эльбрус ЗМ.
Предмет исследования составляют алгоритмические аспекты распределения регистров в оптимизирующем компиляторе для высокопроизводительной вычислительной системы:
• конкретные архитектурные механизмы, их влияние на распределение регистров
• подходы и методы к распределению регистров для оптимизирующего компилятора, взаимодействие с другими компонентами такого компилятора
• алгоритмы решения различных задач, возникающих при распределении регистров, их эффективность и сложность
• конечная производительность и эффективность результирующего кода
Методы исследования заимствованы из областей системного программирования, технологии компиляции, теории графов. Эффективность конечной исполняемой программы оценивалась путем замера времени ее работы (в тактах) на потактной модели микропроцессора Эльбрус-ЗМ. Полученные данные для разных вариантов распределителя регистров сравнивались между собой.
Научная новизна
Решение поставленных в диссертационной работе задач определяет научную новизну исследования, которую, в основном, составляют:
• Исследование влияния новых аппаратных механизмов (широкого командного слова, предикатности, отдельных регистровых файлов для данных разных типов) на распределение регистров
• Исследование влияние разных компонент оптимизирующего компилятора (оптимизаций, увеличивающих время жизни переменных, компонент, обеспечивающих совмещение итераций циклов, планировщика) на работу распределителя регистров
• Разработанные алгоритмы, позволяющие эффективным образом учитывать наличие новых аппаратные механизмов (таких как широкое командное слово и предикатность) при распределение регистров
• Разработанные алгоритмы, позволяющие осуществить эффективное взаимодействие распределителя регистров с прочими компонентами оптимизирующего компилятора
• Разработанный алгоритм анализа предикатных определений переменных с точки зрения прекращения времени жизни этих переменных
Практическая ценность результатов работы состоит в том, что в результате проведенных исследований были выработаны и реализованы на практике методы эффективного учета при распределении регистров новых аппаратных механизмов вычислительных систем. Изучение особенностей взаимодействия распределителя регистров и других компонент оптимизирующего компилятора позволило добиться их максимально эффективного взаимодействия, что резко улучшило как качество работы компилятора, так и, соответственно, производительность систем, являющихся целевыми для данного компилятора.
Кроме того, были выявлены недостатки в алгоритмах некоторых компонент компилятора, и ситуации, в которых действия, проводимые оптимизациями, могут негативно повлиять на качество работы распределителя регистров, а значит, и на весь результат работы оптимизирующего компилятора в целом. Предложены подходы к устранению этих недостатков.
В процессе выполнения диссертационной работы получены следующие практические результаты:
1.) Все разработанные алгоритмы были реализованы в составе распределителя регистров оптимизирующего компилятора с языков высокого уровня С, C++ и Фортран-77, позволяющего получить высокоэффективный оптимизированный код для микропроцессора с архитектурой Эльбрус-ЗМ.
2.) Оптимизирующий компилятор как конечный продукт вошел в состав программного комплекса вычислительной системы Эльбрус-ЗМ.
3.) Результаты исследований были учтены при проектировании и реализации текущего и будущих версий оптимизирующего компилятора, разрабатываемого в рамках проекта Эльбрус-ЗМ.
Апробация
Результаты работы докладывались па международной молодежной научной конференции «XXX Гагаринские чтения» (Москва, в 2004 и 2005 гг.) и международной конференции "Региональная информатика 2004" (С-Петербург, 2004 г.); кроме того, был сделан доклад и проведено обсуждение на семинарах и научно-технических совещаниях ЗАО "МЦСТ" и Института Микропроцессорных Вычислительных Систем РАН.
Публикации
По теме диссертации опубликовано шесть печатных работ:
• Дроздов А. Ю., Корнев Р. М, Боханко А. С. Индексный анализ зависимостей по данным // Информационные технологии и вычислительные системы, № 3, 2004. С. 27-37.
• Боханко А. С, Дроздов А. Ю., Корнев Р. М. Анализ зависимостей по данным в цикловых регионах программы // Компьютеры в учебном процессе, № 8, 2004. С. 57-68.
• Дроздов А. Ю., Боханко А. С. Дерево значений: новая структура данных, объединяющая информацию о потоке управления и доминировании // Информационные технологии, № 12, 2004. С. 32-37.
• Боханко А. С, Новиков С. В., Шлыков С. Л. Некоторые вопросы распределения регистров в архитектурах с широким командным словом // Компьютеры в учебном процессе, № 8, 2005. С. 73-80.
• Боханко А. С, Дроздов А. Ю., Новиков С. В., Шлыков С. Л. Распределение регистров методом раскраски графа несовместимости для VLIW-архитектур / Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Вып. 8. М, 2005. С. 71-77.
• Дроздов А. Ю., Новиков С. В., Боханко А. С, Галазин А. Б. Глобальный граф потока данных и его роль в проведении оптимизирующих преобразований программ / Высокопроизводительные вычислительные системы и микропроцессоры: сборник трудов ИМВС РАН, Вып. 8. М, 2005. С. 78-87.
Краткое содержание работы
В Первой главе рассматриваются основные понятия, необходимые для понимания последующих глав диссертационной работы.
В первом разделе первой главы дан обзор подходов к организации параллельных вычислений и показана предпочтительность архитектур с параллелизмом на уровне отдельных операций. Во втором разделе дано краткое определение понятия оптимизирующего компилятора
Раздел 1.2 посвящен описанию основных структур данных, на которых основаны все последующие алгоритмы и подходы к распределению регистров. В частности, дано краткое описание промежуточного представления, управляющего графа, дерева доминаторов / иостдоминаторов, дерева циклов, формы со статически единственным присваиванием, графа потока данных.
В разделе 1.3 представлена задача распределения регистров; показана ее важность и сложность. В разделе 1.4 дано краткое описание подхода к распределению регистров, основанному на раскраске графа несовместимости. Приведены алгоритмы выполнения основных шагов данного подхода.
Основным результатом первой главы следует считать определение структур данных и алгоритмов, необходимых для базового алгоритма распределения регистров методом раскраски графа несовместимости.
Вторая глава посвящена исследованию влияния аппаратных механизмов на процесс распределения регистров.
В разделе 2.1 подробно изучены последствия наличия широкого командного слова для распределителя регистров. Представлены модификации алгоритма пропагации времени жизни, позволяющие корректно и эффективно работать в архитектурах с широким командным словом. Проведено исследование взаимодействия распределителя регистров и планировщика; проведены замеры влияния на эффективность работы порядка запуска этих фаз. Замеры проводились на пакете тестов SPEC2000; результаты замеров представлены в таблице.
Раздел 2.2 посвящен другому архитектурному механизму - предикатности. Дано определение и краткое описание этого механизма; показаны проблемы, встающие перед распределителем регистров при работе на предикатном коде. Дана классификация этих проблем. Последующие подразделы посвящены исследованию упомянутых проблем. В частности, в разделе 2.2.1 исследуется вопрос точного определения окончания времени жизни регистров и сетей. Проведен анализ опубликованных ранее работ, показаны их недостатки. Предложен новаторский метод решения поставленной проблемы, представлен алгоритм его реализации - причем в двух вариантах, с разными свойствами и разной алгоритмической сложностью. Приведено доказательство корректности представленного алгоритма. В разделе 2.2.2 представлен алгоритм решения второй проблемы, возникающей на предикатном коде - удаления "ложных несовместимостей". Для этого алгоритма доказана алгоритмическая сложность и корректность.
В разделе 2.3 исследуются теоретические и практические аспекты распределения регистров разных типов и разного формата. Приведены алгоритмы, решающие некоторые встающие при этом задачи.
Важнейшими результатами второй главы является создание, доказательство и практическое испытание алгоритмов, решающих целый ряд проблем, встающих перед распределителем регистров при работе на современных вычислительных системах. В частности, это работа в архитектурах с поддержкой широкого командного слова, предикатности, регистров разных типов и форматов.
В Третьей главе исследуются различные аспекты взаимодействия распределителя регистров и других фаз оптимизирующего компилятора.
В первом разделе этой главы представлен общих подход оценки влияния на распределитель регистров целой группы оптимизаций, продлевающих времена жизни переменных. К числу таких оптимизаций относятся Глобальное распространение копий, вынос инвариантов, сбор общих подвыражений. На основе предложенного подхода возможна реализаций конкретных
эвристических оценок для каждой конкретной оптимизации, управляющих ее работой.
В разделе 3.2 изучены вопросы взаимодействия глобального распределителя регистров с цикловым (работающим в циклах с наложением итераций). Предложены методы, позволяющие организовать такое взаимодействие оптимальным образом. Представлены модификации алгоритмов пропагации времени жизни регистров и сетей и оценки стоимости откачки сетей, позволяющая эффективным образом учитывать факт наличия циклов с наложением итераций.
Раздел 5.6 посвящен исследованию вопроса написания распределителя регистров, не зависящего от целевой машины. Тщательно изучены два подхода к построению платформонезависимых компиляторов, дано их сравнение и выработаны рекомендации по использованию. Представлен список свойств, достаточный для настройки платформонезависимого распределителя регистров на целевую архитектуру. Приведены примеры конкретного определения этих свойств для двух современных архитектур: Эльбрус-ЗМ и Intel Itanium.
Основной результат третьей главы заключается в исследовании распределителя регистров как части большой системы, и вопросов, возникающих при взаимодействии с другими частями этой системы. Также важное значение имеет подробное изучение вопросов платформонезависимого распределения регистров.
В Заключении перечисляются основные результаты диссертационной работы. Проводится их обобщение и оценка.
Промежуточное представление
Один из важнейших видов анализа программ - анализ потока управления, позволяющий выявить и представить в удобной форме порядок выполнения отдельных операций программы.
Цепочки операций, безусловно выполняющихся последовательно друг за другом, можно факторизовать в виде отдельных линейных участков3. Внутри линейного участка поток управления линеен. Допускается наличие операций вызова других процедур, которые в данном случае рассматриваются как не нарушающие линейный поток управления.
Весь более сложный, нелинейный поток управления оказывается, таким образом, вынесенным за пределы линейных участков.
Граф потока управления, или управляющий граф, это потоковый граф, узлами которого являются линейные участки; дуги управляющего графа выражают поток управления между линейными участками.
Напомним, что потоковым графом называется ориентированный граф G = V, Е , где V — множество узлов, а Е — множество дуг, у которого есть уникальный входной узел, не имеющий предшественников, и один или несколько выходных узлов, не имеющих преемников [Ryder 1986].
В управляющем графе узел, не имеющий предшественников, называется стартовым; узел, не имеющий преемников - стоповым. Как правило, для удобства оставляют только один стоповый узел; если в программе несколько выходов, то все их соединяют с единственным стоповым узлом.
Стартовый и стоповый узлы обычно делают (опять-таки, для удобства) пустыми.
Управляющий граф может быть построен как для отдельной процедуры, так и для всей программы. В настоящей диссертационной работе предполагается, что, как и все прочие аналитические структуры данных, граф потока управления построен для процедуры, хотя это, в общем, не имеет особенного значения.
Между операциями промежуточного представления и управляющим графом существует определенная связь.
А именно, во-первых, к промежуточному представлению добавляются операции ENTER4 (начало линейного участка), END (конец линейного участка), START (начало стартового линейного участка) и STOP (конец стопового линейного участка).
Во-вторых, в структурах данных, представляющих линейные участки, запоминаются ссылки на соответствующие им операции ENTER, END, START и STOP, а в самих этих операциях - ссылки на соответствующие линейные участки.
И, в-третьих, в структурах данных, представляющих дуги управляющего графа, запоминаются ссылки на соответствующие им операции передачи управления, а в операциях передачи управления, соответственно, ссылки на дуги.
Операциями передачи управления являются: операция перехода (в IRE2K имеет мнемонику BRANCH), операция выхода из процедуры (RETURN), операция, завершающая нестоповый линейный участок (END), или разновидности этих операций.
В случае операции END передача управления - это "провал" на следующий линейный участок.
Например, управляющий граф такой программы: if ( foo == 3 ) bar = foo; baz = bar; состоит из трех линейных участков, в первый из которых входит две операции передачи управления: BRANCH, переходящая ко второй строке программы (в случае, если значение переменной foo равняется 3), и END, "проваливающаяся" сразу же к третьей строке (в противном случае).
Впрочем, роль операций BRANCH и END в данном примере может быть совершенно противоположной — все зависит от того, как был построен управляющий граф.
Из линейного участка может выходить только одна или две дуги; в противном случае мы не можем утверждать, что операции внутри такого участка выполняются последовательно одна за другой. Однако же, данное условие ограничивает размеры линейных участков, что, в свою очередь, уменьшает область применения некоторых фаз оптимизирующего компилятора. Важнейшей из таких фаз является планировщик.
Для решения данной проблемы используются гиперблоки {hyperblocks). Гиперблок, в отличие от линейного участка, может иметь более двух выходов, но также как и линейный участок, лишь один вход.
Большую часть работы компилятора в управляющем графе присутствуют только линейные участки; гиперблоки появляются после преобразования слияние условий (if-conversion). Как правило, распределитель регистров работает уже после того, как слияние условий было проведено (если в компиляторе вообще есть такая фаза).
Для гиперблоков особенно важна связь дуг управляющего графа с операциями перехода, так как только она позволяет понять, в каком порядке выполняются переходы, и какие операции им предшествуют.
Одним из важных отношений между линейными участками5 является отношение доминирования.
Считается, что узел управляющего графа nl доминирует над узлом п2, если любой путь от стартового узла до узла п2 проходит через nl. Узел nl называется доминатором узла п2.
И обратно, если любой путь от пі до стопового узла проходит через п2, то п2 постдоминирует над узлом nl. Узел п2 называется постдоминатором узла nl.
Все, что будет сказано далее о доминировании и доминаторах, справедливо и для постдоминирования и постдоминаторов.
Считается, что любой узел доминирует над самим собой. Однако, есть отношение строгого доминирования, в котором как раз совпадение узлов исключено.
То есть узел управляющего графа nl строго доминирует над узлом п2, если nl доминирует над п2 и не совпадает с ним.
Очевидно, что отношение доминирования транзитивно. То есть если узел nl доминирует над узлом п2, а узел п2 при этом доминирует над узлом пЗ, то и узел nl также доминирует над узлом пЗ.
Тот из строго доминирующих узлов, что встречается на пути от стартового узла к доминируемому узлу последним, называется непосредственным доминатором. Любой узел, кроме стартового, имеет одного и только одного непосредственного доминатора. У стартового узла непосредственного доминатора нет.
Распределение регистров, основанное на раскраске графа несовместимости
В процессе работы оптимизирующего компилятора программа представлена в виде промежуточного представления, оперирующего с пользовательскими переменными, часто носящими название виртуальных регистров8.
Такое представление программы удобно для проведения на нем анализа и оптимизаций; однако же не только используемые регистры, но и само представление можно назвать виртуальным, так как оно не учитывает ресурсных ограничений целевой машины.
Одно из важнейших ограничений — номенклатура, число и правила использования физических регистров, на которые необходимо распределить регистры виртуальные. Распределение виртуальных регистров на физические и есть та задача, которую решает распределитель регистров. Или, как написано в работе [Aho 1986], "в процессе распределения регистров мы выбираем множество переменных, которые будут находится в регистрах в некоторой точке программы".
Известно, что операции, использующие регистры, обычно короче и гораздо быстрее выполняются, чем операции, работающие с операндами, расположенными в памяти. Тем более это справедливо для современных архитектур, в большинстве которых значение, расположенное в памяти, не может быть непосредственным операндом операции, и должно быть предварительно загружено специальной операцией чтения значения из памяти. Кроме того, разрыв между скоростью работы процессора и скоростью передачи данных между процессором и памятью постоянно возрастает, поэтому "стоимость" загрузки данных из памяти также все время увеличивается.
Возникает вопрос: а что, если в некоторой точке программы число доступных физических регистров будет недостаточным для распределения на них всех необходимых в этот момент виртуальных регистров? В этом .случае единственный возможный выход - временное сохранение значений одного или нескольких виртуальных регистров в памяти, с последующей загрузкой этих значений в тех местах, где они потребуются. Таким образом можно облегчить нагрузку на физические регистры (фактически, "перенеся" данные из регистров в память), но цена такого облегчения будет невероятно высокой - мы вынуждены будем создать операции чтения из памяти, о нежелательности которых было сказано выше.
Приведем пример. Допустим, нам дана программа, в промежуточном представлении выглядящая так: а = х / у b - а 3 b=b + x + y + 5 Допустим, что в целевой машине имеется всего три регистра, нумерующиеся с нуля: RO, R1 и R2.
При наивном подходе к распределению регистров, когда каждой новой переменной выделяется новый физический регистр, после проведенного распределения программа могла бы выглядеть так: R2 = RO / R1 STORE [stackl], RO RO = R2 З LOAD [stackl], R2 RO = RO + R2 f Rl + 5 При более эффективном распределении программа выглядит по другому: R2 = RO / R1 R2 = R2 3 R2 = R2 + RO + Rl + 5 Как видим, разница в две операции, причем ни каких-нибудь, а операции записи и чтения из памяти.
В контексте работы распределителя регистров такое сохранение / восстановление значений в памяти называется "откачкой" (сохранение) и "подкачкой" (восстановление). В англоязычной литературе используются термины spilling / filling. Эти термины происходят от английских глаголов Чо spill" (выливать) и "to fill" (наполнять). То есть значения в буквальном смысле слова "выливаются" в память и "наполняются" обратно из памяти в регистры.
Как было показано, эффективное распределение регистров критически важно для результата работы всего оптимизирующего компилятора. Более того, это одна из немногих компонент, без присутствия которой (в том или ином виде) немыслим ни один компилятор, оптимизирующий или нет.
Кроме того, что эта задача крайне важна, она еще и невероятно сложна. Известно, что с точки зрения математики, распределение регистров является NP-полной задачей, то есть такой задачей, оптимального решения которой не существует.
В свое время было предложено множество алгоритмов распределения регистров ([Aho 1986], [Muchnick 1997]); все они обладали существенными недостатками. Основным недостатком, "родовым пятном" большинства подходов к распределению являлась их локальность - как правило, они сосредотачивались на небольших участках программы (например, отдельных линейных участках или циклах). В результате получалось, что в заданном регионе регистры распределялись хорошо, но вообще в программе - плохо. Слабости локальных подходов особенно заметно проявляются при использовании для современных архитектур, для которых характерно как раз укрупнение обрабатываемых регионов.
Требовался глобальный подход, учитывающий всю процедуру целиком. И на рубеже 70-80-ых годов такой подход был создан.
Впервые идея использования графа несовместимости при распределении регистров была предложена в работе [Ершов 1977], но на западе она стала известной и популярной только после появления работы [Chaitin 1981] и [Chaitin 1982].
Основная идея проста: свести задачу распределения регистров к задаче раскраски графа несовместимости. Число узлов в графе - число виртуальных регистров, которые необходимо распределить на физические, дуги графа выражают несовместимость между виртуальными регистрами (два несовместимых виртуальных регистра не могут быть распределены на один физический), а число цветов, которыми необходимо раскрасить граф - это число доступных физических регистров.
Что делать, если заданный граф несовместимости не удалось раскрасить в заданное число цветов? В этом случае, как и во всех других алгоритмах распределения регистров, не обойтись без откачки виртуальных регистров. Откачка сокращает время жизни регистров, а значит, приводит к уменьшению числа дуг в графе несовместимости, и увеличивает наши шансы раскрасить его в заданное число цветов.
Взаимодействие распределителя регистров и планировщика
В архитектурах с широким командным словом важная роль принадлежит планировщику. Его задачей является максимальное задействование всех устройств микропроцессора, то есть наибольшее заполнение широкой команды. Для VLIW-архитектур наиболее удачным считается алгоритм планирования, предложенный в работе [Fisher 1981].
Естественно, что всякое агрессивное планирование приводит к возрастанию числа одновременно живущих переменных, что усложняет задачу распределения регистров и может привести к появлению дополнительных операций откачки/подкачки. Более того, чем больше регион работы планировщика, тем вероятнее возрастание времени жизни переменных.
Распределитель регистров, в свою очередь, приводит к появлению новых зависимостей, так как два ранее независимых виртуальных регистра могут быть распределены на один физический регистр, и сделать, таким образом, соответствующие операции зависимыми друг с другом. Чем больше зависимостей, тем менее оптимальны результаты работы планировщика.
Возникает некоторый "заколдованный круг", когда от порядка запуска фаз зависят результаты их работы, а идеального порядка нет и быть не может.
Были проведены исследования того, какой порядок работы планировщика и распределителя регистров наиболее эффективен. Результаты этих исследований собраны в таблице 2.1. Для замеров использовался общепринятый в индустрии и исследовательском сообществе пакет тестов SPEC2000, в котором собраны наиболее типичные пользовательские программы. В него включены как целочисленные, так и вещественные задачи.
Под "эффективностью работы планировщика" понималось число широких команд, в которые ему удалось спланировать процедуру. Под "эффективностью работы распределителя регистров" понималось число откачки/подкачки, которые ему потребовалось создать для того, чтобы распределить все виртуальные регистры процедуры. Планировщик и распределитель были настроены на архитектуру Эльбрус ЗМ (максимальная ширина команды 14 (существуют некоторые ограничения по типам планируемых операций), число регистров общего назначения 192, число предикатных регистров 32).
Как видно из таблицы, возросшее после планирования давление на регистры практически не сказалось на эффективности работы распределителя регистров. В то же время, результаты работы планировщика при его запуске после распределения оказались всегда хуже, чем при запуске до распределения. Статическое ухудшение (увеличение числа широких команд) в большинстве случаев не очень велико, однако же исследования показывают, что динамическое ухудшение (увеличение числа тактов, необходимых для выполнения задачи) гораздо более существенно. Дело в том, что при измерении статических показателей большую погрешность вносят "обязательные" широкие команды, не зависящие от порядка запуска фаз. Это пролог, эпилог, команды, содержащие вызовы процедур, переходы, не входящие в циклы, и им подобные широкие команды.
Некоторые исследователи (например, в работе [Norris 1995J) пропагандируют одновременное планирование и распределение регистров. Но это и другие исследования, проводившиеся в тот же период ([Norris 1993], [Pinter 1993]), основаны на компиляторах, рассчитанных на последовательные архитектуры, для которых важность планирования далеко не гак велика, как для архитектур с широким командным словом. Насколько известно автору, для VLIW архитектур до сей поры подобных исследований не проводилось.
Как показывает опыт, приобретенный при разработке оптимизирующего компилятора для вычислительной системы Эльбрус ЗМ, в современных условиях подход, основанный на одновременном планировании и распределении регистров, нежизнеспособен. Дело в том, что для сегодняшних пользовательских программ характерны большой размер и высокая сложность. Больше того, оптимизирующие преобразования, как правило, приводят к увеличению этой сложности и еще большему запутыванию структуры управления. В то же время, как уже было отмечено, размеры регистровых файлов в современных архитектурах очень велики, а правила использования регистров могут быть достаточно ограничительными. Поэтому для максимально эффективного задействования имеющихся регистровых ресурсов в программах со сложной структурой управления необходим глобальный (в рамках всей процедуры) анализ, который при планировании, работающем в рамках отдельных линейных участков, провести невозможно.
Как правило, при одновременном планировании и распределении регистров используется битовый вектор, в котором отмечаются уже занятые физические регистры. Для нового виртуального регистра выделяется первый свободный в этом векторе физический регистр. Если свободных физических регистров нет, то откачивается один из виртуальных регистров, занимающих физический. Таким образом, в первую очередь распределяются всегда те виртуальные регистры, которые встречаются в линейном участке раньше, что начисто отрицает возможность оптимального распределения регистров во всей программе.
Кроме того, так как планировщик работает локально в рамках одного линейного участка, то на входе этого участка невозможно сказать, какие регистры уже заняты. Поэтому накладывается дополнительное ограничение на локальность (в рамках линейного участка) всех регистров, как виртуальных, так и физических.
В последнее время значительный интерес вызывают методы глобального планирования ([Nicolau 1993]), которые, казалось бы, позволяют одновременно проводить распределение регистров, основываясь на результатах глобального анализа. Однако же, эта тема остается малоизученной, сложность самих алгоритмов глобального планирования крайне высока, а тот анализ, что необходим для эффективного планирования, значительно отличается от анализа, необходимого для распределения регистров. Не стоит забывать, что задачи распределения ограниченного числа ресурсов (к которым относятся и планирование, и распределение регистров) являются NP-полными, и очень сложны для решения. Как бы там ни было, но хорошего практического алгоритма распределения регистров одновременно с глобальным планированием автору неизвестно; и в число задач настоящей диссертационной работы не входил поиск такого алгоритма.
Взаимодействие общецелевого и циклового распределителей регистров
В некоторых архитектурах, например в архитектуре Itanium, пространства вращающихся и общецелевых регистров пересекаются; в других, таких как Эльбрус-ЗМ, эти пространства разделены, однако ничто не мешает использовать вращающиеся регистры вне циклов с совмещением итераций, для распределения па них обычных виртуальных регистров.
Таким образом, ресурсы, используемые двумя упомянутыми распределителями регистров, пересекаются. Необходимо некоторое взаимодействие, призванное обеспечить корректное разделение ресурсов.
Один из вариантов такого взаимодействия — самостоятельное отслеживание тех физических регистров, что уже заняты в наложенных циклах, общецелевым распределителем регистров. Однако же, такое отслеживание крайне тяжело и в некоторых случаях даже невозможно. Дело в том, что благодаря вращению, даже одна операция, определяющая один вращающийся регистр (например, RRO), может перезаписать значения сразу нескольких физических регистров (конкретнее, их число совпадает с размером вращающейся области).
Предпочтительней представляется следующая схема взаимодействия: цикловой распределитель (который всегда работает раньше) запоминает для каждого цикла число занятых регистров каждого типа. Эта информация может быть сохранена, например, в структуре, привязанной к узлу дерева циклов.
Регистры, занятые цикловых распределителем в цикле 1, считаются недоступными для всех сетей, время жизни которых пересекает 1. Однако же, для этих сетей остаются доступными вращающиеся регистры, незанятые в 1.
При этом границы "запретной зоны" несколько превышают границы собственно цикла 1. Дело в том, что ряд вращающихся регистров может инициализироваться в предцикле і; также в постцикле 1 могут быть пересылки значений с вращающихся регистров на обычные. Таким образом, границами наложенного цикла с точки зрения общецелевого распределителя регистров следует считать те операции установки базы вращающихся регистров, что входят в предцикл и постцикл. Если в аппаратуре таких операций не требуется, то в промежуточном представлении следует завести соответствующие псевдооперации, не приводящие к появлению какого-либо кода на этапе кодогенерации, и не занимающие ресурсов при планировании.
При пропагации времени жизни операции установки базы, входящие в постциклы наложенных циклов, следует считать чтением физических регистров, занятых в соответствующем наложенном цикле, а операции установки базы, входящие в предциклы, определениями этих регистров. Аргументы операций, собственно работающие с вращающимися регистрами, при этом надо игнорировать.
У данного решения есть один существенный недостаток: оно полностью полагается на информацию, переданную от циклового распределителя регистров к общецелевому распределителю. Это означает что, во-первых, все фазы, способные оперировать с вращающимися регистрами, должны корректировать данную информацию. В настоящий момент, однако же, автору неизвестно о существовании таких фаз (за исключением, собственно, циклового распределителя регистров), что, однако, не означает невозможность появления подобного рода фаз в будущем.
Во-вторых и главных, полностью запрещается создание до запуска фаз оптимизирующего компилятора операций, работающих с вращающимися регистрами. То есть фактически запрещается наличие ассемблерных вставок, оперирующих подобного рода регистрами. Действительно, такие ассемблерные вставки практически не поддаются анализу (с точки зрения используемых ими регистров), и для их успешной оптимизации не обойтись без дополнительной вспомогательной информации. Содержание и способы передачи этой вспомогательной информации выходят за рамки настоящей диссертационной работы.
Для тех архитектур, в которых пространства обычных и вращающихся регистров пересекаются, может возникнуть ситуация, когда в результате слишком большого числа регистров, занятым цикловым распределителем под свои нужны, промежуточное представление окажется "нераспределяемым" - то есть в нем будут участки, число одновременно живущих сетей в которых превышает число оставшихся после циклового распределителя физических регистров, и при этом операции откачки / подкачки будут неспособны исправить положение.
Например, если после циклового распределителя осталось только восемь целочисленных регистров, и в предцикле наложенного цикла есть широкая команда, читающая девять разных виртуальных регистров, то очевидно, что распределить эти девять регистров невозможно - какие бы операции откачки / подкачки не были при этом созданы.
Существует два способа решения данной проблемы, каждый из которых обладает своими недостатками. Первый способ заключается в превращении промежуточного представления из "нераспределяемого" в "распределяемое" за счет разрыва широких команд. Например, если в упомянутом примере разорвать широкую команду с девятью разными виртуальными регистрами на две команды с меньшим числом регистров в каждой, то распределить регистры снова станет возможно (правда, за счет создания операций откачки / подкачки). Но реализация такого разрыва широких команд крайне сложна и возможна не во всех ситуациях.
Второй способ заключается в ограничении максимального числа регистров, доступных для циклового распределителя так, чтобы остающиеся регистры гарантировали "распределяемость" промежуточного представления. Максимальное число регистров, которые нужно оставить для общецелевого распределителя, равно максимальному числу разных виртуальных регистров, которое может быть прочитано или определено в одной широкой команде целевой архитектуры. Недостатком этого способа является, во-первых, то, что понижается эффективность или становится вовсе невозможной совмещение итераций для некоторых циклов с большим требованиям к ширине области вращающихся регистров, а во-вторых, этот способ малоприменим к архитектурам с динамической шириной широкой команды (то есть к EPIC-архитектурам).
