Оптимизация разворота цикла, как это работает

Рассмотрим этот C-код:

int sum=0; for(int i=0;i<5;i++) sum+=i; 

Это можно было бы перевести в (псевдо) сборку таким образом (без развертки цикла):

 % pseudo-code assembly ADDI $R10, #0 % sum ADDI $R11, #0 % i LOOP: ADD $R10, $R11 ADDI $R11, #1 BNE $R11, #5 LOOP 

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

1)

 ADDI $R10, #0 ADDI $R10, #0 ADDI $R10, #1 ADDI $R10, #2 ADDI $R10, #3 ADDI $R10, #4 

2)

  ADD $R10, #10 

Может ли компилятор оптимизировать код и напрямую знать, что он должен добавить 10, не выполняя все суммы?

Кроме того, есть ли возможность заблокировать конвейер с помощью инструкции перехода? Должен ли я писать так:

 % pseudo-code assembly ADDI $R10, #0 % sum ADDI $R11, #0 % i LOOP: ADD $R10, $R11 ADDI $R11, #1 NOP % is this necessary to avoid the pipeline blocking? NOP NOP NOP BNE $R11, #5 LOOP 

Чтобы избежать того, что обратный цикл fetch-decode-exe-mem-write прерывается ветвью?

Это больше для демонстрации того, что способен компилятор, а не того, что сделает каждый компилятор. Источник:

 #include  int main(void) { int i, sum = 0; for(i=0; i<5; i++) { sum+=i; } printf("%d\n", sum); return 0; } 

Заметьте, что printf я добавил. Если переменная не используется, компилятор оптимизирует весь цикл.

Компиляция с -O0 (без оптимизации)

gcc -Wall -O0 -S -c lala.c :

 .L3: movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) .L2: cmpl $4, -8(%rbp) jle .L3 

Цикл происходит «глупым» способом, причем -8(%rbp) является переменной i .

Компиляция с -O1 (уровень оптимизации 1)

gcc -Wall -O1 -S -c lala.c :

 movl $10, %edx 

Цикл был полностью удален и заменен эквивалентным значением.


При разворачивании компилятор смотрит, сколько итераций произойдет, и попытается развернуть, выполняя меньше итераций. Например, тело цикла может дублироваться дважды, что приведет к уменьшению количества ветвей. Такой случай в C:

 int i = 0, sum = 0; sum += i; i++; for(; i<5;i++) { sum+=i; i++; sum+=i; } 

Обратите внимание, что одна итерация должна быть извлечена из цикла. Это связано с тем, что 5 - нечетное число, и поэтому работу нельзя просто сократить вдвое, дублируя содержимое. В этом случае цикл будет введен только дважды. Код сборки, созданный -O0 :

  movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) jmp .L2 .L3: movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) .L2: cmpl $4, -8(%rbp) 

Полностью разворачивается в C:

 for(i=0; i<5;i++) { sum+=i; i++; sum+=i; i++; sum+=i; i++; sum+=i; i++; sum+=i; } 

На этот раз цикл фактически вводится только один раз. Сборка, произведенная с -O0 :

 .L3: movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) movl -8(%rbp), %eax addl %eax, -4(%rbp) addl $1, -8(%rbp) .L2: cmpl $4, -8(%rbp) jle .L3 

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

Такая оптимизация обычно выполняется на уровне АСТ вместо уровня выходного кода (например, сборки). Развертка цикла может быть выполнена, когда число итераций фиксировано и известно во время компиляции. Так, например, у меня есть этот АСТ:

 Program | +--For | +--Var | | | +--Variable i | +--Start | | | +--Constant 1 | +--End | | | +--Constant 3 | +--Statements | + Print i 

Компилятор знал бы, что For’s Start и End являются константами и поэтому могут легко копировать Statement, заменяя все вхождения Var его значением для каждого вызова. Для выше АСТ это будет переведено на:

 Program | +--Print 1 | +--Print 2 | +--Print 3 

Может ли компилятор оптимизировать код и напрямую знать, что он должен добавить 10, не выполняя все суммы?

Да, если это реализовано, чтобы иметь такую ​​функцию. На самом деле это улучшение по сравнению с вышеприведенным случаем. В примере вашего примера, после выполнения разворачивания, компилятор мог видеть, что все значения l остаются неизменными, а значение r – константами. Поэтому он мог бы выполнять оптимизацию глазок в сочетании с постоянной складкой, чтобы получить однократное добавление. Если оптимизация глазок также учитывает декларацию, тогда она может быть даже оптимизирована более в одной команде перемещения.

На базовом уровне концепция разворачивания цикла просто просто копирует тело цикла несколько раз по мере необходимости. Компилятор также может выполнять другие оптимизации (например, вставлять фиксированные значения из расчета), но не будет рассматриваться как разворачивание цикла, но потенциально заменяя его все вместе. Но это в конечном счете будет зависеть от используемого компилятора и флагов.

Код C (только развернутый) будет выглядеть примерно так:

 int sum = 0; int i = 0; for ( ; i < (5 & ~(4-1)); i += 4) /* unrolling 4 iterations */ { sum+=(i+0); sum+=(i+1); sum+=(i+2); sum+=(i+3); } for ( ; i < 5; i++) { sum+=i; } 

Хотя у компилятора есть много возможностей сделать еще больше оптимизаций, это всего лишь один шаг.

Для этого нет общего ответа, разные компиляторы, разные версии из них, разные флаги компилятора будут различаться. Используйте соответствующий вариант своего компилятора, чтобы посмотреть на результат ассемблера. С gcc и родственниками это опция -S .