Как GCC может развернуть цикл, если его количество итераций неизвестно во время компиляции?

Я читал опции оптимизации для GCC, когда нашел опцию -funroll-all-loops.

Его описание гласит:

Разверните все циклы, даже если их количество итераций не определено, когда цикл вводится. Обычно это делает программы медленнее. '-funroll-all-loops' подразумевает те же опции, что и '-funroll-loops'

Как может компилятор развернуть цикл, если его количество итераций неизвестно во время компиляции? Разве компилятор не нуждается в этой информации, чтобы развернуть его? Какой соответствующий код C он генерирует, и в каких контекстах это может быть полезно, если оно обычно делает программы медленнее?

Ответ 1

в каких контекстах это может быть полезно, если оно обычно заставляет программы работать медленнее?

Ну, они предполагают, что если вы выберете этот вариант, вы знаете, что вы делаете, если вы этого не сделаете, вы не должны использовать эту опцию.

что gcc собирается делать, я использовал эту примерную программу:

#include <stdio.h>

void f(int j )
{
  for( int k = 0; k < j; ++k )
  {
    printf( "%d\n", k ) ;
  }
}

и протестировал его с помощью godbolt, и он генерирует таблицу перехода, основанную на количестве оставшихся итераций (видеть это в прямом эфире):

cmpl    $1, %ebp
movl    $1, %ebx
je  .L1
testl   %r12d, %r12d
je  .L27
cmpl    $1, %r12d
je  .L28
cmpl    $2, %r12d
je  .L29
cmpl    $3, %r12d
je  .L30
cmpl    $4, %r12d
je  .L31
cmpl    $5, %r12d
je  .L32
cmpl    $6, %r12d
je  .L33

Ответ 2

Он может сделать что-то вроде:

while(n >= 8){
  foo(); foo(); foo(); foo(); foo(); foo(); foo(); foo(); 
  n -= 8;
}
while(n > 0){
  foo();
  n--;
}

Конечно, Duff Device сохранит необходимость записи второго цикла.

Зачем? Это до пользователя. Если foo() проводит более нескольких циклов или если исходный цикл занимает меньше 5% от общего времени настенных часов или если n обычно мал, это, вероятно, не стоит проблем.

Ответ 3

Здесь приведен код C, показывающий, как это сделать:

int iterations = 100;
int unrollValue = 8;

while (iterations%unrollvalue)
{
   // insert loop code here
   iterations--;
}

while (iterations)
{
   // insert unrollValue copies of loop code here
   iterations-= unrollValue;
}

Компилятор заменит первый цикл на относительный скачок, но это непросто представить в C. Обратите внимание, что разворачивание по мощности 2 позволяет компилятору использовать маску вместо операции (дорогого) деления.

Ответ 4

Вы не можете предположить, что существует такая вещь, как соответствующий код C для промежуточного представления компилятора. Но в этом случае я ожидаю, что ближайший эквивалент будет выглядеть как Duff Device, который представляет собой последовательность (обычно в цикле), которая может вводится в вычисленном месте.