Понятие компилятора. Оптимизация кода. Основные источники оптимизации.
В идеале компилятор должен давать столь же хороший целевой код, как и написанный вручную. Реальность же такова, что это достигается только в ограниченном количестве случаев, к тому же с огромным трудом. Однако зачастую код, который дает простой алгоритм компиляции, может быть сделан более быстрым или более компактным (или и то, и другое одновременно). Такое улучшение достигается преобразованием программы, традиционно именуемым оптимизацией, хотя употребление этого термина и является некорректным, поскольку крайне редко можно гарантировать, что полученный в результате преобразования код— наилучший возможный. Компилятор, применяющий улучшающие код преобразования, называется оптимизирующим.
Машинно-независимая оптимизация - преобразование программы, которое улучшает целевой код без учета конкретных свойств целевой машины. Машинно-зависимая оптимизация, такая как распределение регистров и применение специальных последовательностей машинных инструкций (машинных идиом).
Максимальное вознаграждение за минимальные усилия можно получить, если определить часто выполняемые части программы и сделать их по возможности максимально эффективными. На практике хорошими кандидатами для улучшения являются внутренние циклы. В языке с управляющими конструкциями типа for или while циклы ясно выделяются в структуре программы. В общем случае циклы идентифицируются процессом анализа потока управления по графу потока программы.
Попросту говоря, наилучшие преобразования программы — те, которые приводят к максимальному результату при минимальных усилиях. Преобразования, выполняемые оптимизирующим компилятором, должны обладать рядом свойств.
Во-первых, преобразование должно сохранять смысл программы, т.е. оптимизация не должна изменять выход программы для данного входа или приводить к ошибке (типа деления на нуль), если она не присутствовала в исходной версии программы. Это требование распространяется на всю данную главу; всякий раз, когда встает вопрос о "безопасности" преобразования, предпочтительнее не применять его вовсе, чем рисковать внесением изменений в работу программы.
Во-вторых, преобразование в среднем должно ускорять работу программы. Иногда мы заинтересованы в уменьшении размера скомпилированного кода, хотя сейчас размер кода менее важен, чем когда-то. Конечно, не всякое преобразование способно улучшить любую программу, и иногда "оптимизация" способна вызвать замедление работы программы — притом, что в среднем она повышает производительность.
В-третьих, преобразования должны стоить затрачиваемых усилий. Разработчику компилятора не имеет смысла затрачивать интеллектуальные усилия на реализацию улучшающего код преобразования и увеличивать время компиляции исходной программы, если эти усилия не окупятся при работе скомпилированной программы. Некоторые преобразования могут применяться только после кропотливого, зачастую весьма длительного анализа исходной программы, так что их применение в программах, которые будут выполняться только несколько раз, просто необоснованно.
Существенное повышение производительности программы— такое, как снижение времени работы с нескольких часов до нескольких секунд— обычно получается при совершенствовании программы на всех уровнях, от исходного текста до целевой программы. На каждом уровне возможные варианты действий простираются от поиска лучшего алгоритма до реализации данного алгоритма с помощью меньшего количества выполняемых операций.
Основные источники оптимизации
Преобразование программы называется локальным, если оно может быть выполнено только с инструкциями в пределах базового блока;
в противном случае оно именуется глобальным. Многие преобразования могут выполняться как на локальном, так и на глобальном уровне. Первыми обычно выполняются локальные преобразования.
Преобразования, сохраняющие функции
Существует ряд способов, которыми компилятор может улучшить программу без изменения вычисляемой функции. Устранение общих подвыражений, размножение копий, удаление недоступного кода и дублирование констант— вот основные примеры таких преобразований, сохраняющих функции. Зачастую программа включает несколько вычислений одного и того же значения, например смещения в массиве.
Общие подвыражения
Выражение Е называется общим подвыражением, если £ было ранее вычислено и значения переменных в £ с того времени не изменились. Повторного вычисления можно избежать, если мы сможем использовать ранее вычисленное значение.
Распространение копий
Блок В5 из рисунка может быть улучшен удалением х путем применения двух новых преобразований, касающихся присвоения вида f : = g, именуемого инструкцией копирования или, для краткости, просто копированием. Идея преобразования распространения копий заключается в использовании после присвоения f : = g переменной g вместо f везде, где только это возможно.
Такое преобразование может показаться никаким не улучшением кода, но, как мы увидим позже, оно дает нам возможность удалить присвоение х.
Удаление бесполезного кода
Переменная в некоторой точке программы считается "живой", или активной, если ее значение будет использовано в программе в последующем; в противном случае она считается "мертвой". Очередная идея оптимизации касается мертвого, или бесполезного кода, т.е. кода, вычисляющего значения, которые никогда не будут использованы.
Оптимизации циклов
Время работы программы может быть улучшено путем уменьшения количества инструкций во внутреннем цикле, даже если при этом увеличится код вне цикла. Для оптимизации циклов особенно важны три технологии:
перемещение кода (code motion), которая переносит код из цикла вовне;
устранение индуктивной переменной (induction-variable elimination), которую мы применим для удаления переменной
снижение стоимости (reduction in strength), которая замещает дорогие операции более дешевыми— например, умножение сложением.
Перемещение кода
Важным изменением, уменьшающим количество кода в цикле, является перемещение кода. Это преобразование берет из цикла выражение, приводящее к одному и тому же результату независимо от того, сколько раз выполняется цикл (вычисление, инвариантное относительно цикла (loop-invariant computation)), и размещает его перед циклом. Заметим, что понятие "перед циклом" предполагает существование входа в цикл.
Переменные индукции и снижение стоимости
Хотя перемещение кода и не применимо к рассматриваемому нами примеру быстрой сортировки, вполне возможно использование двух других технологий оптимизации. Обычно циклы обрабатываются от самого глубоко вложенного к циклам меньшей степени вложенности.
