illumium.org

Под оптимизацией компилируемых программ можно понимать два аспекта. Первый важный аспект - это труд самого разработчика над совершенствованием реализаций алгоритмов в программе. Второй не менее важный - возможности инструментария разработки генерировать более оптимальный исполняемый код. В этом посте речь пойдёт о втором аспекте, поскольку он не требует особых усилий от разработчика и позволяет получать хороший результат прямо здесь и сейчас.

Краткое введение

Преимущественно мы будем говорить об оптимизации программ на языке C для встраиваемых систем на микроконтроллерах, также по умолчанию нашей стратегией будет уменьшение размера программы. Однако применение описанных возможностей этим не ограничивается и будет полезно всем разработчикам, использующим набор инструментов GCC.

Существуют две основных стратегии оптимизации машинного кода:

1. Оптимизация размера программы
2. Оптимизация скорости выполнения

На практике реальные компиляторы не ограничиваются только этими двумя. Например, GCC позволяет задать следующие стратегии или уровни оптимизации:

• 0 - отсутствие оптимизации и самая быстрая компиляция (по умолчанию)
• 1 - умеренная оптимизация и достаточно быстрая компиляция
• 2 - полная оптимизация по скорости и долгая компиляция
• 3 - более продвинутая полная оптимизация
• s - оптимизация размера кода и данных (не увеличивающая размер оптимизация)
• fast - оптимизация скорости в ущерб строгому следованию стандартам
• g - оптимизация не препятствующая отладке

Мы в праве выбрать любую в зависимости от ограничений и возможностей среды выполнения. С точки зрения компилятора каждая стратегия представлена набором задействованных возможностей кодогенератора, таким образом достаточно изощрённый разработчик может сам скомбинировать нужные ему опции (-fxyz) вместо указания уровня оптимизации (-Ox).

Оптимизация компилятором

Компилятор (cc) превращает файл исходного кода в объектный файл, содержащий секции с машинным кодом функций и данными. Далее мы будем называть каждый такой файл модулем компиляции. Таким образом компилятор осуществляет оптимизацию в пределах модуля.

Существует множество техник улучшения скорости выполнения кода и/или уменьшения его размера при компиляции. Основные из них следующие:

1. Исключение недостижимого кода
2. Свёртка, объединение и распространение констант
3. Выделение общих частей в выражениях
4. Полная или частичная развёртка циклов
5. Внедрение тела функций в места вызова
6. Оптимизация хвостовой рекурсии

Первая техника самая простая: компилятор определяет участки программы, которые в принципе никогда не выполняются, и исключает их из модуля.

Вторая техника посложнее: компилятору придётся проанализировать AST программы, чтобы определить, какие выражения могут быть вычислены ещё на этапе компиляции. Это могут быть не обязательно простые выражения, они могут включать вызов чистых функций (результат которых зависит только от переданных аргументов), объявленных в пределах модуля компиляции, а также встроенных функций компилятора (builtins). Свёртка констант представляет собой замену выражений на константы, а распространение идёт дальше: заменяет заведомо константные переменные в других выражениях вычисленными значениями. Объединение констант это не просто замена одинаковых значений, к примеру, строк, на одно. Компилятор достаточно умён, и если он увидит, что одна строка является частью конца другой строки, он также объединит её с первой. Эти техники оптимизируют как скорость так и размер программы.

Третья техника позволяет уменьшить количество вычислений, путём выделения общих частей выражений в отдельные переменные, вычисляемые только один раз.

Разворачивание циклов ускоряет выполнение, ценой увеличения размера программы. Ускорение осуществляется снижением числа условных и безусловных переходов, которые могут существенно замедлить программу, особенно когда в теле функции достаточно простая операция. Проще всего развернуть константные циклы, то есть те, что выполняются заведомо известное количество раз. Сложнее обстоит дело с произвольными: здесь в игру вступает так называемая векторизация. Например, когда в цикле происходит итерация по i от 0 до N, компилятор делает предположение, что N может быть больше, скажем, 8 и помещает перед циклом такой же цикл только развёрнутый в 8 раз с итерацией по i через 8. Так компилятор может развернуть цикл несколько раз, например, сначала по 16 шагов, потом по 8, и по 4. В отсутствии информации о реальном выполнении программы эти предположения делаются вслепую.

Техника встраивания позволяет исключить достаточно дорогую операцию вызова функций, внедрением тела функции в места её вызова. Эту оптимизацию наиболее разумно применять в двух случаях:

1. Функция статическая (используется только в пределах модуля компиляции)
2. Тело функции меньше или сравнимо с операцией её вызова

И наконец, последняя из основных техник позволяет предотвратить вызов функцией самой себя в конце путём безусловного перехода в её начало. Таким образом, хвостовая рекурсия превращается по сути в цикл, к которому может быть применена оптимизация развёртки/векторизации.

Оптимизация линковщиком

Линковщик (ld) объединяет множество модулей компиляции в единый исполняемый файл, путём связывания символов функций и данных разных модулей между собой. Изначально оптимизация не была уделом линковщика, но те времена давно прошли.

Практика разработки показала, что из оптимизированных модулей далеко не всегда получается оптимизированная программа, остаётся ещё множество возможностей дальнейшей оптимизации. Например, функции не могут быть встроены между модулями, или исключены неиспользуемые функции и данные.

Первое время проблема отсутствия оптимизации связывания разработчиками решалась так: в релизе все модули включались в единый исходный файл директивами #include и компилировался уже этот файл. Однако, данный подход применим далеко не во всех случаях, к тому же он не позволяет работать со статическими библиотеками.

В настоящее время линковщики стали намного интеллектуальнее и при некоторой поддержке со стороны компилятора могут производить достаточно изощрённые оптимизации. Но начнём рассмотрение мы с самого простого, а именно, с возможности исключения неиспользуемых функций и констант. Эта возможность связана со способностью линковщика исключать неиспользуемые секции. Так, если заставить компилятор помещать каждую функцию и кусок данных в отдельные секции (с помощью опций -ffunction-sections и -fdata-sections), то линковщик (с опцией --gc-sections) сможет исключить те из них, которые не доступны из программы.

Оптимизация времени связывания

Возможность, носящая название LTO, в GCC реализуется отдельным плагином. Стоит заметить, что нужна соответствующая поддержка со стороны компилятора (включается опцией -flto). Это именно тот тип оптимизаций, который плотно завязан на LTCG. В общих словах это означает, что те оптимизации, которые раньше были доступны только компилятору, теперь могут осуществляться линковщиком, в который загружен соответствующий плагин.

Собирая свой код с -flto, я заметил следующее:

1. Компиляция заметно ускорилась вне зависимости от используемых опций оптимизации.
2. Линковщик теперь знает о типах переменных и функциях и выдаёт предупреждения, если в разных модулях для общих символов они не совпадают.

Вторая особенность весьма удобна и позволяет избежать неверного использования в некоторых общих случаях.

Но как и с любой достаточно молодой и прогрессивной технологией c LTO не всё так просто, как могло бы быть. С её использованием связаны некоторые проблемы с линковкой, в частности, когда некоторые модули или библиотеки собраны без LTO, могут быть проблемы с нахождением некоторых символов из них.

Мною были опробованы несколько версий GCC для сборки прошивки для устройства на STM32, и получены довольно любопытные результаты:

Компиляция производилась с -Os и опциями -ffunction-sections -fdata-sections для компилятора, а также --gc-sections для линковщика. Но в первом случае без опции -flto, а во втором с ней. В данном конкретном случае GCC 5.4 сгенерировал наиболее оптимальный по размеру код как с LTO так и без.

В результате исследования полученного исполняемого файла утилитой objdump, я сделал следующие выводы:

1. Короткие функции были встроены в места вызова, не смотря на расположение в разных модулях и библиотеках
2. Функции, вызываемые один раз, также были внедрены в место вызова
3. Отладочная информация была окончательно испорчена и польза от неё сведена на нет весьма существенно пострадала

Как было сказано выше, необходимо наличие специального плагина LTO. В GCC предусмотрены специальные обёртки для запуска программ типа nm, ar обеспечивающие загрузку соответствующего плагина. Достаточно просто использовать gcc-nm, gcc-ar вместо них.

Оптимизация, управляемая профилированием

И наконец наиболее продвинутые техники оптимизации PGO. Выше мы сделали оговорку, что во многих случаях компилятор делает выбор в оптимизации исполняемого кода исходя из некоторых общих предположений, которые на практике не всегда могут быть оправданы. Скорректировать эти предположения можно только собрав информацию о реальном выполнении программы. В GCC есть специальные опции -fprofile-generate для компилирования программы с профилированием и -fprofile-use для использования созданного в процессе выполнения профиля на следующем этапе компиляции. Следует учитывать, что скомпилированную для профилирования программу лучше всего запускать с учетом наиболее частого варианта использования, чтобы получить на выходе наиболее оптимальный профиль.

При разработке встраиваемого ПО эта технология оптимизации имеет смысл, если применяются вычислительно-ёмкие алгоритмы типа сжатия, шифрования или кодирования. Но применить её здесь не так тривиально. Во-первых необходимо реализовать кое-какие stub функции для libc, чтобы профилировщик мог записать файл профиля. Во-вторых, дополнительный код профилирования увеличит размер программы и потребление оперативной памяти. Это может стать серьёзным препятствием для запуска её на реальном прототипе устройства, поэтому программу придётся собирать для работы в эмуляторе либо использовать контроллеры с существенно большим объёмом Flash памяти и RAM.

По таблице ниже можно примерно оценить вносимые профилированием накладные расходы:

Как видим, они довольно таки велики. Чтобы получить эти данные, мне пришлось выбрать High-density микроконтроллер при сборке, поскольку программа никак не хотела вписываться в имеющуюся оперативную память (20KB).

Выводы

В статье рассмотрены возможности оптимизации, предлагаемые современными версиями GCC. Кроме собственно оптимизаций компилятора, особое внимание уделено оптимизациям линковщика, также затронута тема оптимизации профилированием. На основании полученных данных можно сделать вывод, что оптимизации линковщика весьма полезны в разработке под микроконтроллеры. Профилирование тоже может помочь в генерации наиболее оптимального кода, особенно когда дело касается оптимизации на скорость выполнения. Другая сторона использования продвинутых техник оптимизации: существенное ухудшение возможностей отладки, поэтому можно рекомендовать их применение только для финальной сборки, особенно когда есть соблазн сэкономить на целевом микроконтроллере.