Введение 2
1 Цели и задачи 3
2 Обзор 4
2.1 Анализ Clang 5
2.2 Анализ GCC 6
2.3 Оптимизация на основе SSA-формы 7
2.4 Оптимизация на основе AST-формы 8
3 Реализация 8
3.1 Общий подход 8
3.2 Оптимизация последовательных переходов 9
3.3 Вычисление количества повторов цикла перед телом цикла 11
3.4 Использование слота задержки 12
3.5 Индуцированные переменные 14
3.6 Удаление ненужных индуктивных переменных 17
4 Измерения и оценка 19
5 Заключение 21
Список литературы 23
Приложение 1 26
Приложение 2 27
Приложение 3 27
Несмотря на то, что C является фактическим стандартом для низкоуровневого программирования и программирования встроенных систем, он имеет существенные недостатки, такие как арифметика указателей и отсутствие контроля за границами массива при доступе к элементу массива. Примечательно, что это недостатки самого языка, а не отдельных компиляторов. Эти недостатки негативно сказываются на безопасности языка C.
На кафедре системного программирования Санкт-Петербургского государственного университета разрабатывается транслятор языка RuC, представляющий собой усовершенствованную версию языка C [1]. На эту тему были сделаны научные публикации [2, 3]. На данный момент проект RuC стал промышленным, что свидетельствует об актуальности и практической значимости данного проекта.
С развитием RuC возникла необходимость в реализации оптимизаций. Без оптимизаций транслятор не сможет конкурировать с популярными компиляторами с языка C, такими, как GCC или Clang.
Генерация оптимального объектного кода является одной из основных и наиболее сложных задач в области разработки компиляторов. Данная работа посвящена оптимизации генерации кода для процессоров с архитектурой MIPS [4], что усложняет задачу. MIPS - это RISC-архитектура, допускающая огромную вариативность в генерации кода и его оптимизации.
Разработчик генератора кода сталкивается со сложными вопросами. Какие оптимизации должны быть реализованы? Какие оптимизации дадут значительный выигрыш в скорости работы программы? Какие оптимизации часто ускоряют работу программы, а какие срабатывают очень редко? Какие особенности архитектуры следует учитывать при оптимизации кода? Все это требует анализа других трансляторов, подходов к оптимизации и большой работы с машиной, в коды которой переводится программа.
Некоторые оптимизации не могут быть реализованы только в рамках генератора кода. Для сложных оптимизаций может потребоваться изменить абстрактное синтаксическое дерево или добавить дополнительную информацию в таблицы транслятора до начала кодогенерации, что требует включения в компилятор дополнительного оптимизирующего просмотра.
После реализации необходимо повторно проанализировать другие трансляторы, чтобы выяснить, где и как еще можно оптимизировать код, насколько и в каких случаях компилятор RuC проигрывает своим аналогам, а в каких случаях и на сколько он стал лучше.
Работа состоит из пяти глав. В первой главе ставится цель работы и описываются конкретные задачи для достижения цели. Во второй главе представлен обзор оптимизированного кода, сгенерированного GCC и Clang, а также обзор подходов к оптимизации. Третья глава содержит общий подход к реализации оптимизаций и детали реализации конкретных оптимизаций. В четвёртой главе представлены измерения, их оценка и повторное сравнение с GCC и Clang. В пятой главе описаны результаты работы и возможности для дальнейших исследований.
В данной работе решается задача оптимизации генерации ассемблерного кода архитектуры MIPS. Были проанализированы компиляторы GCC и Clang. На основе проведенного анализа были выбраны оптимизации для реализации: оптимизация последовательных переходов, вычисление количества повторов цикла перед телом цикла, использования слота задержки, индуцированные переменные и удаление ненужных индуктивных переменных. Эффективность оптимизаций была показана на примере умножения матриц. Таким образом, генерация кода для циклов и вырезок была оптимизирована в трансляторе RuC.
Дальнейшим направлением работ по оптимизации генерации RuC в архитектуру MIPS могут быть: оптимизация вызовов функций, арифметических операций, распределение регистров, устранение неиспользуемых переменных.
Также работа оставляет после себя несколько открытых проблем для исследований. Например, в обзоре было указано, что команда madd сильно замедляет программу. Но почему так происходит? Это хорошая тема для исследований свойств архитектуры процессора. Сам результат данной работы может стать объектом для исследования. Почему оптимизированная программа работает всё ещё медленнее аналогов в отдельных случаях? Вопрос остаётся открытым.
