Этапы компиляции
В этой главе мы приводим обобщённое представление о процессе компиляции. Обобщённая диаграмма работы компилятора выглядит следующим образом:
В этом процессе оптимизации производятся дважды:
- Машиннонезависимые производятся над внутренним представлением, полученным от front-end.
- Машинно-зависимые оптимизации производятся над предварительным ассемблерным кодом, полученным от генератора кода.
Хотелось бы отметить, что, несмотря на своё название, машиннонезависимые оптимизации нельзя считать полностью оторванными от конкретной архитектуры. Многие из них разрабатывались с учётом общих представлений о свойствах некоторого класса машин (как правило - это машина с большим количеством регистров, фон-неймановской архитектуры, с относительно большой по размерам и медленной памятью). В современных компиляторах они, как правило, нацелены на достижение предельных скоростных характеристик программы, в то время как для встраиваемых систем к критическим параметрам также относится и размер получаемого кода. Некоторые оптимизирующие преобразования (такие, например, как раскрутка циклов) могут ухудшить программу ввиду резкого разрастания размеров и утери информации, полезной для последующих стадий оптимизации.
Ещё одна особенность компилятора для встраиваемой системы вытекает из свойства большинства таких систем: ограниченность памяти и отсутствие динамических библиотек. Программа компилируется единожды целиком и в последствии не может изменяться по частям. Это порождает следующие преимущества при создании компилятора:
- Исходные программы достаточно компактны, следовательно, время необходимое на их компиляцию меньше. Поэтому можно использовать более тяжеловесные алгоритмы и эвристики, чем те, что применяются в компиляторах общего назначения.
- Есть возможность получить информацию обо всей программе целиком, не ограничиваясь только рамками собираемого модуля или библиотеки. Это свойство создаёт предпосылки для применения межпроцедурного анализа и глобальных оптимизаций.
Практически каждый компилятор производит определённый набор машинно-независимых оптимизаций.
Вот примеры таких оптимизаций:
Исключение общих подвыражений: если внутреннее представление генерируется последовательно для каждого подвыражения, оно обычно содержит большое количество избыточных вычислений. Вычисление избыточно в данной точке программы, если оно уже было выполнено ранее. Такие избыточности могут быть исключены путём сохранения вычисленного значения на регистре и последующего использования этого значения вместо повторного вычисления.
Удаление мёртвого кода: любое вычисление, производящее результат, который в дальнейшем более не будет использован, может быть удалено без последствий для семантики программы.
Вынесение инвариантов циклов: вычисления в цикле, результаты которых не зависят от других вычислений цикла, могут быть вынесены за пределы цикла как инварианты с целью увеличения скорости.
Вычисление константных подвыражений: вычисления, которые гарантированно дают константу могут быть произведены уже в процессе компиляции.
Несмотря на то, что эти преобразования называются машинно-независимыми, иногда их стоит использовать с осторожностью. Вычисление общих подвыражений, к примеру, сокращая количество вычисляемых выражений, увеличивает потребность в регистрах. Для процессора с большим количеством функциональных устройств и небольшим количеством регистров повторение вычисления может оказаться более эффективным. Аналогичным образом, вычисление константных подвыражений может отразиться на семантике программы, когда типы машин производящих компиляцию и выполняющих программу различны.
Все описанные ниже алгоритмы, за исключением межпроцедурного анализа, работают на этапе машинно-зависимых оптимизаций. Здесь следует особо отметить, что их эффективность зачастую напрямую зависит от наличия той или иной дополнительной информации об исходной программе, а именно:
- «Программная конвейеризация» и сворачивание в «аппаратные циклы» напрямую зависят от информации о циклах исходной программы и их свойствах (цикл for, цикл while, фиксированное или нет число шагов, ветвление внутри цикла, степень вложенности).
Таким образом, необходимо, во-первых, исключить машиннонезависимые преобразования, разрушающие структуру цикла, и, во-вторых, обеспечить передачу информации об этих циклах через кодогенератор. - Алгоритмы «SOA» и «GOA» (см. ниже) используют информацию о локальных переменных программы. Требуется информация, что данное обращение к памяти суть обращение к переменной и эта переменная локальная.
- Алгоритмы раскладки локальных переменных по банкам памяти требуют информации об обращениях к локальным переменным, плюс важно знать используется ли где-либо адрес каждой из локальных переменных (т.е. возможно ли обращение по указателю)
- Алгоритм «Array Index Allocation» и «частичное дублирование данных» должен иметь на входе информацию о массивах и обращениях к ним.
Таким образом, нельзя полностью абстрагироваться от начальных стадий работы компилятора, рассматривая их как производящий ассемблерный код «чёрный ящик». Предварительные стадии компиляции должны учитывать особенности класса целевой машины, чтобы создавать предпосылки к максимальной эффективности алгоритмов машинно-зависимых оптимизаций.
