Как заставить компилятор C/C++ генерировать плохой код

Источник: habrahabr

m1kc

Это перевод статьи "How to trick C/C++ compilers into generating terrible code?",

автор оригинала - Aater Suleman.

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

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

Компиляторы

Компилятор берёт ваш код на языке высокого уровня и преобразует его в код машинный. Схема работы компилятора выглядит примерно так:

Выполнить синтаксический анализ кода и построить его промежуточное представление.
Оптимизировать промежуточное представление.
Сгенерировать машинный код.
Выполнить линковку (компоновку).

Оптимизация кода требует от компилятора выполнения довольно объёмного анализа. Простой пример - удаление мёртвого кода (англ. dead code elimination, DCE). При выполнении DCE компилятор исключает из программы код, исполнение которого не влияет на результат работы программы. Например, цикл в строках 3 и 4 будет исключён компилятором, потому что результат выполнения цикла не используется нигде.

1: void foo(){
2:   int x;
3:   for(int i = 0; i < N; i++)
4:     x += i;
5: }

При выполнении DCE компилятор производит обратный анализ потока данных (def-use), чтобы определить, какие из переменных не используются. Затем он удаляет строки, которые выполняют запись в эти неиспользуемые переменные. Чтобы компилятор смог выполнить DCE и другие подобные оптимизации, у него должна быть возможность узнать со 100%-ной уверенностью, будет ли выполняться доступ к переменной. Здесь и открываются возможности для запутывания компилятора. Мы можем использовать несколько хорошо известных "узких мест".

Вызовы функций

Анализ, выполняемый компилятором, - очень сложная вычислительная задача. Для справки - код самого компилятора, вероятно, является самым сложным кодом в мире. Более того, проблемы оптимизации проявляются очень быстро. Чтобы удержать время компиляции в разумных рамках, компиляторы часто ограничивают область анализа функциями и выполняют ограниченный межпроцедурный анализ (англ. inter-procedural analysis, IPA) или не выполняют его вовсе. Вдобавок к этому компилятор, воспринимающий функции как независимые сущности, может компилировать несколько файлов одновременно.

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

Давайте посмотрим на этот пример:

void foo(){
  int x;
  for(int i = 0; i < N; i++)
    x += bar(i);
}

И в другом файле:

int bar(int i){
  return i;
}

Программист может подумать, что лишние ресурсы здесь тратятся только на вызовы bar(). Однако во время компиляции foo() компилятор не может увидеть, что у bar() нет никаких побочных эффектов, например, записи в глобальную переменную или операций ввода-вывода. Поэтому он отключает DCE, и бесполезный цикл теперь тоже будет выполняться. Результатом может стать существенное падение производительности.

Указатели

Я видел много программистов, которые используют указатели без необходимости. В теории для указателей главным источником трат ресурсов считается их разыменование (если оно есть). На практике они сжигают гораздо больше ресурсов, потому что запутывают компилятор.

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

for(int i = 0; i < N; i++)
 *a++ = *b++ + *c++;

После внимательного изучения человек может понять, что код на самом деле просто делает следующее:

for(int i = 0; i < N; i++)
 a[i] = b[i] + c[i];
a += N;
b += N;
c += N;

Первый код запутывает компилятор. Даже если итерации цикла независимы, компилятор не считает их таковыми; по этой причине он не может векторизовать данный кусок кода. А вот второй - может.

Для справки: векторизованный код выполняется в 5 раз быстрее. Использование многопоточной обработки может дать прирост в 4 раза на 4 ядрах с небольшими усилиями со стороны программиста. Этот же код, автоматически векторизованный, даёт прирост скорости в 5 раз без каких-либо усилий. Я пробовал Intel C Compiler (ICC) 9.1 и GCC 4.1. Результаты приведены для ICC.

Если идей больше нет, используйте глобальные переменные

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

for(int i = 0; i < N; i++)
 a[i] = b[i] + c[i];

Когда вы объявляете переменную N глобальной, компилятор оставляет её в памяти и добавляет в цикл инструкцию для её загрузки. Если же объявить Nлокальной, компилятор загружает её в регистр. Можно ругать такое поведение компилятора (потому что N не является volatile), но приходится работать с тем, что есть.

Заключение

Важно помнить об IPA и указателях, когда вы пишете код на C/C++. Так вы сможете помочь компилятору сгенерировать код, который будет выполняться быстрее.

Кстати: я заметил, что и GCC, и ICC чувствительны к порядку линковки, т.е. сгенерированный код зависит от порядка, в котором указаны входные файлы в командной строке компоновщика. Это может оказать сильное влияние (до 10%) на производительность из-за кэширования и предсказания ветвлений. Если вы по-настоящему цените производительность, стоит попробовать поиграться и с порядком линковки.

Ссылки по теме