Теперь, когда мы увидели, как клиентская часть компилятора находит ошибки пользователя в коде, а средняя часть выполняет некоторую платформо-независимую оптимизацию, давайте посмотрим, что делает внутренняя часть компилятора.
Основная цель серверной части - создание низкоуровневого кода, который может выполняться в определенной среде. Поскольку разные среды имеют разные возможности, серверная часть может выполнять дополнительную оптимизацию кода, чтобы воспользоваться преимуществами различий в оборудовании. Таких оптимизаций много, некоторые из которых обсуждаются ниже.
Оптимизация цикла
Поскольку большие объемы программных вычислений выполняются в циклах, компиляторы обычно стремятся повысить эффективность кода, выполняемого в циклах.
Для этого есть несколько методов, некоторые из которых обсуждаются ниже.
Автоматическое распараллеливание
Этот метод оптимизации работает в системах с несколькими ядрами. Цель состоит в том, чтобы разделить цикл на несколько ядер, чтобы сократить время вычислений.
Циклическая многопоточность - это первый метод распараллеливания, который разбивает цикл на разные итерации и выполняет их одновременно. Это может работать только с циклами, которые не изменяют последовательно никаких значений.
Конвейерная многопоточность - это другой метод распараллеливания, который разбивает процессы внутри цикла на отдельные фрагменты кода и запускает их на отдельных ядрах, что приводит к более быстрым итерациям, поскольку следующую итерацию можно запустить первое ядро, в то время как последующие ядра могут завершить оставшиеся вычисления на выходе первого ядра.
Слияние / Комбинирование
Путем нахождения циклов, которые повторяются одинаковое количество раз, можно сделать меньше вычислений, комбинируя циклы и выполняя их одновременно. Это может быть выполнено только в том случае, если циклы не изменяют одни и те же значения.
Разворачивание
Чтобы уменьшить накладные расходы на выполнение кода, переходящего к началу цикла каждый раз, когда он повторяется, каждая итерация цикла может быть записана. Это наиболее выгодно, когда количество итераций известно во время компиляции, что позволяет полностью развернуть цикл.
Генерация кода
Генерация кода - основная причина для компилятора. Другие этапы процесса проверяют правильность и позволяют оптимизировать, но в конечном итоге это единственный этап, который требуется компилятору для запуска кода на машине.
Я упоминал об этом в предыдущем посте, но если вы хотите больше узнать о том, как работает машинный код низкого уровня, я очень рекомендую поиграть в TIS-100. Это сделает все, что ниже, намного понятнее.
Выбор инструкции
Этот процесс принимает промежуточное представление кода и переводит его в инструкции, доступные в целевой архитектуре. Например
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1
Становится
MOV EAX, a XCHG EAX, b ADD a, EAX
Существует несколько стратегий поиска оптимального преобразования промежуточного представления в машинный код. Обычно используется рекурсивный обход дерева промежуточного представления (которое мы узнали в части 1 - это дерево). При этом обходе шаблоны ищутся в дереве, которое соответствует шаблонам, которые могут быть представлены в машинном коде. Как только эти шаблоны найдены, их можно заменить инструкциями машинного кода.
Планирование инструкций
Остановка конвейера происходит, когда выполнение следующей инструкции сразу после текущей приведет к неверному значению. Чтобы этого не произошло, следующая инструкция ненадолго приостанавливается, чтобы текущая инструкция обновила все правильно.
Рассмотрим две команды:
1: A <- B + C 2: D <- A + B
В этой ситуации выполняется команда 1, а затем рассматривается команда 2. Если бы команда 2 была запущена сразу после команды 1, A еще не был бы сохранен (поскольку вычисление требует такта часов, а затем для записи в регистр A требуется второй такт). Это означает, что команду 2 нужно отложить до тех пор, пока команда 1 не закончит запись.
Планирование инструкций - это процесс изменения порядка выполнения инструкций (которые уже были выбраны) для предотвращения остановок конвейера.
Размещение регистров
Чтобы оптимизировать скорость выполнения программы, необходимо как можно чаще использовать присвоение значений регистрам ЦП (к которым можно быстро получить доступ). Для этого компилятор оценит необходимость одновременного использования значений, а затем обеспечит их присвоение разным регистрам.
Как только будет найден оптимальный набор регистров для использования, машинный код может быть обновлен, чтобы ссылаться на регистры в командах, которые обращаются к ним.
Любые значения, которые не могут быть присвоены регистру (из-за того, что значения уже присутствуют во всех регистрах) будут присвоены ОЗУ, доступ к которому сравнительно медленнее. Процесс присвоения этих значений ОЗУ известен как разлив.
Проблема присвоения значений регистрам ЦП является NP-сложной, но есть хорошо известные алгоритмы, которые уравновешивают оптимизацию распределения регистров со временем, необходимым для достижения оптимального решения. Есть интересная статья об использовании машинного обучения для выполнения распределения регистров здесь.
Вот и все. Общий обзор того, что делает ваш компилятор за кулисами. Мы видели, что интерфейсная часть выполняет поиск ошибок в коде, средняя часть выполняет оптимизацию, не зависящую от платформы, а серверная часть выполняет оптимизацию для конкретной платформы и, наконец, преобразует код высокого уровня в машинный код низкого уровня.
Если вам понравилась эта статья, порекомендуйте ее с помощью кнопки ❤ .
