Этот пост снова посвящается цикловым оптимизациям. Почему вообще речь зашла о цикловых перестановочных оптимизациях? Дело в том, что это одна из самых эффективных частей оптимизирующего компилятора. В число цикловых перестановочных оптимизаций входит как автовекторизация так и автопараллелизация. У этих оптимизаций существует своя специфика, но в целом у всех цикловых оптимизаций общие проблемы и общие методы их решения.
Часто приходится слышать мнение, что компилятор во многих случаях «тупит». Мне хочется здесь побыть адвокатом компилятора, чтобы показать, что жизнь компилятора не так уж легка, возможно вызвать легкую долю сочувствия к его нелегкой доле и показать, какие существуют объективные трудности при обработке программы и почему во многих случаях компилятор совершенно обоснованно не может сделать ту или иную оптимизацию, которая кажется очевидной программисту. Ну и заодно я хочу продемонстрировать некоторые возможности помочь компилятору в его работе. Понятно, что иногда существуют и субъективные факторы, в лице разработчиков, которые по како-либо причине не реализовали ту или иную функциональность внутри компилятора.
Я буду использовать компилятор Intel для Windows, но думаю схожие проблемы вызывают головную боль у пользователей и разработчиков всех оптимизирующих компиляторов с цикловыми оптимизациями, поэтому надеюсь этот пост будет полезен для всех программистов. Я предполагаю, что у читателя есть какие-то базовые представления о межпроцедурном анализе, поэтому я буду ссылаться на возможности этого анализа без детального объяснения, что это такое и как работает.
В предыдущем посте я предложил посмотреть на изменение производительности синтетического теста, вызванной применением высокоуравневой цикловой оптимизации разбиения цикла (loop distribution). Одной из основных целей примера было показать, как перестановка порядка операций может повлиять на работу подсистемы памяти и сколько различных факторов производительности могут быть изменены при этом. Т.е. оценка выгодности оптимизации довольно сложная работа, которая часто затрудняется отсутствием точной информации о структуре обрабатываемых данных.
И это еще не все трудности, которые стоят перед компилятором. Перед тем как оценивать возможные выгоды от той или иной трансформации нужно потратить определенные усилия, чтобы распознать сами циклы и доказать саму возможность применения перестановочной оптимизации. В основном этот пост посвящен проблеме распознавания циклов и разрешения неоднозначности при работе с памятью.
Распознавание циклов
Для выполнения цикловых перестановочных оптимизаций компилятор должен сначала распознать и классифицировать циклы. Основные цикловые оптимизации применимы только к циклам с определенным количеством итераций, имеющих последовательно изменяющиеся итерационные переменные (и как следствие не имеющие переходов за пределы цикла и вызовов неизвестных функций). Рассмотрим, например, набор простых циклов, раcположеных в некой функции foo:
extern int unknown();
int gn,gi;
typedef struct vector {
float *array;
int lbound;
int ubound;
} vec;
int foo(int n, float *a, vec *v) {
int i,j;
int b[100];
// 1 loop
for(i=0;i<gn;i++)
a[i] = 0;
// 2 loop
for(gi=0;gi<n;gi++)
a[gi]=0;
// 3 loop
for(i=0;i<n;i=i*3)
b[i]=0;
// 4 loop
for(i=0;i<n;i++) {
j=unknown();
b[i]=j;
}
// 5 loop
for(i=0;i<n;i++) {
if(b[i] !=0)
break;
b[i] = 1;
}
// 6 loop
for(i=0;i<n&&i<gn;i++)
b[i] = i;
// 7 loop
for(i=0;i<n;i++) {
if(gn)
break;
else
b[i] = 0;
}
// 8 loop
for(i=0;i<n;i++) {
if(i>n)
goto exit;
b[i] = 100;
}
// 9 loop
for(i=v->lbound;i<v->ubound;i++) {
v->array[i]=i;
}
exit:
return b[10];
}
Распознал ли компилятор эти циклы и существует ли способ понять это? Явного способа я не знаю, (кроме использования внутренних дампов для разработчиков), но есть интересный косвенный способ, связанный с выдачей рапорта о работе автовекторизатора с помощью ключа /Qvec-report2. Ключ /Qvec_report используется так:
/Qvec-report[n]
control amount of vectorizer diagnostic information
n=0 no diagnostic information
n=1 indicate vectorized loops (DEFAULT when enabled)
n=2 indicate vectorized/non-vectorized loops
n=3 indicate vectorized/non-vectorized loops and prohibiting
data dependence information
…
Если скомпилировать приведенный файл с опциями по умолчанию и ключом /Qvec_report2, то компилятор выдаст следующую информацию:
icl -Qvec_report2 test_loops.c
..\test_loops.c(34): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(41): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(45): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(53): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(16): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(20): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(24): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(28): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
..\test_loops.c(60): (col. 1) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
Фраза nonstandard loop и означает, что цикл имеет неподходящую структуру для выполнения цикловых оптимизаций. В чем причина того, что компилятор не смог распознать и классифицировать циклы?
1 цикл: В условии выхода из цикла используется глобальная переменная «gn». На каждой итерации происходит модификация памяти, через указатель «a». Теоретически этот указатель может ссылаться на «gn» и условие выхода из цикла может изменяться на каждой итерации.
2 цикл: Та же ситуация связана с использованием глобальной переменной «gi» в качестве итерационной переменной цикла. Итерационная переменная может быть изменена на какой-либо итерации через указатель «a».
3 цикл: Итерационная переменная изменяется нелинейно.
4 цикл: Вызов внутри цикла неизвестной функции. Такой вызов может содержать, например, выход из программы.
5 цикл: Существует несколько условий при которых выполнение цикла может быть прервано. Т.е. количество итераций такого цикла не может быть определено во время компиляции.
6 цикл: Компилятор не смог разобрать сложное условие выхода из цикла. Использование глобала «gn» не является здесь препятствием, поскольку в цикле идет работа с локальным массивом «b» и эта переменная не может быть изменена в процессе работы.
7 цикл: Условный переход внутри цикла мешает определить количество итераций. Переход не зависит от итерационной переменной, и здесь компилятор мог бы вынести условный переход из цикла. Но видимо для этого нужно сначала распознать цикл.
8 цикл: Использование goto с переходом во вне цикла делает неопределенным количество итераций такого цикла. Хотя такой переход не может случится, но эта проблема тоже должна была быть решена ДО фазы распознавания циклов.
9 цикл: Очень типичный случай. Поле array теоретически может ссылаться на поля lbound или ubound. Это одна из причин, почему существуют проблемы с обработкой различных контейнеров из STL библиотеки, таких как vector.
Большинство вышеперечисленных затруднений при классификации циклов связаны с проблемой разрешения неоднозначности при работе с памятью (memory disambiguation). Для разрешения этой проблемы компилятор использует как положения стандартов языков программирования так и результаты межпроцедурного анализа. Поскольку в моем примере межпроцедурный анализ не используется в полной мере (по умолчанию в Intel компиляторе используется –Qip, т.е. анализ только функций из компилируемого исходного файла), то компилятору приходится, в основном, использовать только правила стандартов языка С и С++, которые предоставляют программистам широкие возможности для организации различных объектов, ссылающихся на одну и ту же память.
Можно сформулировать следующие пожелания программистам, желающих добиться лучшего результата при оптимизации своих программ:
1.) Не используйте глобальных переменных и указателей в конструкциях, определяющих поведение цикла. Если необходимо, заведите локальные переменные.
2.) Упрощайте, где это возможно, условие выхода из цикла. Например, в цикле 6 можно было предварительно вычислить наименьшее значение для «n» и «gn» и использовать его в дальнейшем в условии выхода.
3.) Избегайте условных переходов за пределы цикла.
4.) Используйте опцию –Qansi_alias, если в своих программах вы не нарушаете правил ANSI aliasing. Эти правила устанавливают, что указатели несовместимых типов никогда не могут ссылаться на одну и ту же память. Т.е. поставив эту опцию при компиляции вы даете компилятору возможность использовать информацию о типах для разрешения неоднозначности при работе с памятью. В этом случае вы даете знать компилятору, что в вашей программе указатели ссылаются только на объекты своего или совместимого типов.
5.) Достаточно часто проблемой являются аргументы указатели, передаваемые внутрь функции. Стандарт C99 ввел новый квалификатор типа restrict для указателей. restrict-квалификация указателей означает, что данные, на которые указывают такие указатели не указывают на пересекающиеся объекты. В приведенном примере описание функции foo с использованием этого классификатора имело бы вид: int foo(int n, float * restrict a, vec * restrict v). Для использования этой функциональности нужно добавить при компиляции опцию –Qstd=c99.
6.) При организации вашего проекта располагайте совместно используемые функции в одном исходном файле и пользуйтесь аттрибутом static, чтобы ограничить область видимости объектов и функций этим исходным файлом. Это улучшает возможности эффективного межпроцедурного анализа с опцией –Qip. Забегая вперед хочется заметить, что полный межпроцедурный анализ -Qipo очень полезен, но значительно увеличивает необходимые для компиляции ресурсы и время компиляции. Поэтому при грамотной организации проекта опция –Qip может быть очень полезной альтернативой, обеспечивая при этом сравнимую с -Qipo производительность.
7.) Используйте опцию для включения межпроцедурного анализа и оптимизаций (-Qipo ). Эта опция позволяет, например, определить, брался ли адрес у переменной. Если удается установить, что адрес переменной никогда не брался, то это значительно упрощает устранение неоднозначности. Помимо этого межпроцедурный анализ включает сбор информации об объектах, на которые ссылаются указатели (local and global points-to analysis ) и о свойствах функций. Подстановка тела функции (inlining) может привести к тому, что цикл с вызовом функции становиться «хорошим» и может быть оптимизированным. Все это отчасти верно и для –Qip.
Ну и чтобы не обидеть поклонников C++ небольшой синтетический тест на C++.
#include <stdlib.h>
class Array {
public:
Array(int n);
~Array() { free(Objects);};
void initArray(int x);
int nobjects;
int *Objects;
};
Array::Array(int n) {
nobjects = n;
Objects = (int*) malloc(nobjects*sizeof(int));
}
void Array::initArray(int x) {
for(int i=0;i<nobjects;i++)
Objects[i] = x;
}
Меня интересует вопрос, распознается ли цикл внутри initArray.
Без опции –Qansi_alias здесь вообще все плохо, поскольку появляется скрытый аргумент указатель this, который с точки зрения наученного горькой жизнью компилятора, может указывать на все что угодно. –Qansi_alias решает эту проблему и с этой опцией члены класса уже не могут алиаситься с this. Но даже наличие опции –Qansi_alias не помогает компилятору распознать цикл.
icl -Qvec_report2 -Qansi_alias test_loops.cpp -c
test_loops.cpp(18): (col. 2) remark: loop was not vectorized: nonstandard loop is not a vectorization candidate.
Компилятор опасается здесь, что при записи в Objects может быть изменена переменная nobjects. В результате цикл не распознается. Опция –Qansi_alias не помогает, поскольку указатель Objects и nobjects имеют один и тот-же тип. В случае, если бы этот файл был частью проекта и мы собирали бы проект с опцией –Qipo компилятор бы распознал и векторизовал данный цикл, если бы доказал, что эти объекты не могут пересекаться по памяти.
Здесь следует заострить внимание на том факте, что если вы используете в условии выхода из цикла члена класса типа nobjects, то компилятор видит this->nobjects. Замена этого объекта на локальную переменную перед циклом позволит упростить распознавание цикла.
void Array::initArray(int x) {
int n=nobjects;
for(int i=0;i<n;i++)
Objects[i] = x;
}
Интересно, что если объявить nobjects приватной переменной класса, то и в этом случае цикл векторизуется. Это заслуга межпроцедурного анализа (-Qip) выполненого для одного файла.
Таким образом можно сформировать рекомендацию:
6a) Используйте аттрибут private для членов класса, если это возможно, чтобы ограничить их область видимости. Т.е. это хорошая рекомендация с точки зрения написания модульного кода, но и для оптимизаций этот принцип так-же приносит определенную пользу.
Хочется еще заметить, что в случае гнезда циклов, нераспознанный внутренний цикл автоматически ведет к отбраковке всех внешних к нему циклов. Цикловых операций над гнездом циклов немного, например перестановка циклов (loop interchange). Тем не менее выявление гнезда циклов может быть очень полезно для производительности.
Критерий допустимости перестановочных оптимизаций
Итак, основная идея цикловых оптимизаций состоит в изменении порядка выполняемой работы. После того как циклы были распознали и классифицированы и начинается настоящая работа. Необходимо определить условия, при которых можно делать цикловые перестановочные оптимизации и при этом получать «эквивалентную программу» или эквивалентные вычисления. С точки зрения непредвзятого пользователя, программы будут эквивалентными, если при одинаковых входных данных они будут получать одинаковые результаты и результаты будут выводится в одинаковом порядке. Если задуматься о том, в каком случае при изменении порядка вычислений итоговый результат будет оставаться неизменным, то легко воспроизвести критерий эквивалентности вычислений. Результаты будут одинаковыми, если зависимые друг от друга утверждения будут выполняться в одинаковом порядке в первоначальном и модифицированном вычислениях. Т.е. независимые друг от друга инструкции можно переставлять как угодно, а вот порядок зависимых вычислений необходимо сохранить. И здесь появляется такое ключевое для оптимизирующего компилятора понятие, как зависимость.
Бывают зависимости по данным и по графу управления.
Если хочется применить некую цикловую оптимизацию, то для доказательства ее корректности необходимо будет убедиться, что порядок зависимостей в начальном и производном цикле будет одинаковым. Существует достаточно сложная методология для обнаружения зависимостей при использовании в цикле (или гнезде циклов) массива A, индексированного счетчиками итераций (итерационными переменными цикла). Компилятор пытается определить, существует ли обращение и запись в одну и ту же память на разных итерациях. Наилучшим вариантом для многих цикловых оптимизаций является отсутствие в цикле зависимостей. (Есть перестановочные оптимизации, которые используют зависимости при своей работе.) Для определения зависимостей компилятор использует довольно сложные методы, но вся эта сложная функциональность не будет нужна, если предварительно не будет решена проблема неоднозначности при работе с памятью. В этом случае появляются совершенно неожиданные зависимости, которые могут помешать выгодным оптимизациям.
Опять возьмем маленький пример и посмотрим как зависимости мешают векторизации, а так-же другим оптимизациям. В данном случае приняты все меры, чтобы не было возможности использования одной памяти различными объектами.
void foo(float * restrict a, float * restrict b, int n, int offset) {
int i,j;
for(i=0;i<n;i++) {
a[i] = a[i+offset];
b[i] = b[i+offset];
}
return;
}
icl -Qstd=c99 -Qvec_report3 test_loops.c -c
est_loops.c(4): (col. 1) remark: loop was not vectorized: existence of vector dependence.
..\test_loops.c(6): (col. 4) remark: vector dependence: assumed ANTI dependence between b line 6 and b line 6.
..\test_loops.c(6): (col. 4) remark: vector dependence: assumed FLOW dependence between b line 6 and b line 6.
..\test_loops.c(6): (col. 4) remark: vector dependence: assumed FLOW dependence between b line 6 and b line 6.
..\test_loops.c(6): (col. 4) remark: vector dependence: assumed ANTI dependence between b line 6 and b line 6.
..\test_loops.c(5): (col. 4) remark: vector dependence: assumed ANTI dependence between a line 5 and a line 5.
..\test_loops.c(5): (col. 4) remark: vector dependence: assumed FLOW dependence between a line 5 and a line 5.
..\test_loops.c(5): (col. 4) remark: vector dependence: assumed FLOW dependence between a line 5 and a line 5.
..\test_loops.c(5): (col. 4) remark: vector dependence: assumed ANTI dependence between a line 5 and a line 5.
Проблема здесь в том, что осуществляя сдвиг вектора компилятор не знает как соотносятся переменные «n» и «offset». Для того, чтобы помочь компилятору оптимизировать эти циклы можно использовать прагмы:
8) Используйте #pragma ivdep перед циклом если в соответствии с вашими знаниями о цикле в нем не может быть зависимости. Использование прагмы так-же может помочь в распознавании цикла.
Еще одним широко известным случаем, с которым у компилятора нет шансов разобраться с зависимостями является случай использования векторной индексации, например такой:
void foo(int n, float * restrict a, float * restrict b, int * restrict ind) {
int i;
for(i=0;i<n;i++)
a[ind[i]] += b[i];
}
icl -Qstd=c99 -Qvec_report2 test_loops.c -c
..\test_loops.c(4): (col. 1) remark: loop was not vectorized: existence of vector dependence.
..\test_loops.c(5): (col. 3) remark: vector dependence: assumed ANTI dependence between a line 5 and a line 5.
..\test_loops.c(5): (col. 3) remark: vector dependence: assumed FLOW dependence between a line 5 and a line 5.
..\test_loops.c(5): (col. 3) remark: vector dependence: assumed FLOW dependence between a line 5 and a line 5.
..\test_loops.c(5): (col. 3) remark: vector dependence: assumed ANTI dependence between a line 5 and a line 5.
Массив ind может содержать дублирующиеся значения и тогда действительно будут существовать цикловые зависимости, препятствующие различным оптимизациям. В данном случае #pragma ivdep так-же помогает компилятору.
Вообщем, различных подобных случаев можно придумать много, но надеюсь, что в целом моя мысль понятна.
Заключение:
Этот текст был написан для того, чтобы показать, что работа оптимизирующего компилятора во многих случаях определяется необходимостью обеспечивать консервативный характер применения оптимизаций. Т.е. оптимизация может быть применена только тогда, когда есть возможность доказать ее корректность.
Консервативный характер анализа должен подразумевать презумпцию виновности программиста в желании запутать и обмануть компилятор. Можно идти навстречу компилятору и отказываться от некоторых сильно общих возможностей языков программирования. Также языками предусмотрены различные программные инструменты для предоставления компилятору дополнительной информации.
Буду рад, если кто-нибудь поделится опытом по данной теме.
