Почему компилятор не может (или не может) оптимизировать предсказуемый цикл сложения в умножение?

Этот вопрос пришел в голову при чтении блестящего ответа Mysticial на вопрос: почему обрабатывать отсортированный массив быстрее, чем несортированный ?

Контекст для задействованных типов:

const unsigned arraySize = 32768;
int data[arraySize];
long long sum = 0;

В своем ответе он объясняет, что компилятор Intel (ICC) оптимизирует это:

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            sum += data[c];

... во что-то эквивалентное этому:

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

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

Но почему он этого не делает?

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

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

Компилятор не может преобразовать

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

в

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

потому что последнее может привести к переполнению целых чисел со знаком, тогда как первое - нет. Даже с гарантированным поведением переноса для переполнения подписанных двух целых дополнений, это изменит результат (если data[c]это 30000, продукт станет -1294967296для типичных 32-битных ints с переносом, а 100000 раз, добавив 30000 к, sumбудет, если это не переполняется, увеличивается sumна 3000000000). Обратите внимание, что то же самое верно и для беззнаковых величин с разными числами, переполнение 100000 * data[c]обычно приводит к уменьшению по модулю, 2^32которое не должно появляться в конечном результате.

Он мог бы превратить его в

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

хотя, если, как обычно, long longдостаточно больше, чем int.

Почему он этого не делает, я не могу сказать, я предполагаю, что это то, что сказал Mysticial: «по-видимому, он не запускает проход с разрушением цикла после обмена циклом».

Обратите внимание, что сам обмен циклами обычно недопустим (для целых чисел со знаком), поскольку

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

может привести к переполнению, где

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

не будет. Здесь кошерно, так как условие гарантирует, data[c]что все, что добавлено, имеют один и тот же знак, поэтому, если одно переполняется, то оба.

Я бы не был слишком уверен, что компилятор учел это (@Mysticial, не могли бы вы попробовать с таким условием, data[c] & 0x80которое может быть истинным для положительных и отрицательных значений?). У меня были компиляторы, которые выполняли недопустимую оптимизацию (например, пару лет назад у меня было ICC (11.0, iirc), использующее преобразование signed-32-bit-int-to-double, 1.0/nгде nбыло an unsigned int. Было примерно в два раза быстрее, чем у gcc вывод. Но не так, многие значения были больше 2^31, упс.).

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

Из-за конечной точности повторное сложение с плавающей запятой не эквивалентно умножению . Рассматривать:

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);

демонстрация

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

Оптимизация, которая была сделана, была движением кода с инвариантным циклом. Это можно сделать с помощью набора приемов.

Что ж, я предполагаю, что некоторые компиляторы могут выполнять такую ​​оптимизацию, предполагая, что мы говорим о целочисленной арифметике.

В то же время некоторые компиляторы могут отказаться делать это, потому что замена повторяющегося сложения умножением может изменить поведение кода при переполнении. Для беззнаковых целочисленных типов это не должно иметь значения, поскольку их поведение при переполнении полностью определяется языком. Но для подписанных это может (возможно, не на платформе дополнения 2). Верно, что подписанное переполнение на самом деле приводит к неопределенному поведению в C, а это означает, что должно быть совершенно нормально игнорировать эту семантику переполнения в целом, но не все компиляторы достаточно храбры, чтобы сделать это. Он часто вызывает много критики со стороны толпы «C - это просто язык ассемблера более высокого уровня». (Помните, что произошло, когда GCC ввел оптимизацию на основе семантики строгого псевдонима?)

Исторически GCC зарекомендовал себя как компилятор, у которого есть все, что нужно для таких решительных шагов, но другие компиляторы могут предпочесть придерживаться воспринимаемого «пользовательского» поведения, даже если оно не определено языком.

Теперь это так - по крайней мере, clang :

long long add_100k_signed(int *data, int arraySize)
{
    long long sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

компилируется с -O1 в

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        movsxd  rdx, dword ptr [rdi + 4*rsi]
        imul    rcx, rdx, 100000
        cmp     rdx, 127
        cmovle  rcx, r8
        add     rax, rcx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

Целочисленное переполнение тут ни при чем; если есть целочисленное переполнение, вызывающее неопределенное поведение, это может произойти в любом случае. Вот такая же функция, использующая intвместоlong :

int add_100k_signed(int *data, int arraySize)
{
    int sum = 0;

    for (int c = 0; c < arraySize; ++c)
        if (data[c] >= 128)
            for (int i = 0; i < 100000; ++i)
                sum += data[c];
    return sum;
}

компилируется с -O1 в

add_100k_signed:                        # @add_100k_signed
        test    esi, esi
        jle     .LBB0_1
        mov     r9d, esi
        xor     r8d, r8d
        xor     esi, esi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        mov     edx, dword ptr [rdi + 4*rsi]
        imul    ecx, edx, 100000
        cmp     edx, 127
        cmovle  ecx, r8d
        add     eax, ecx
        add     rsi, 1
        cmp     r9, rsi
        jne     .LBB0_4
        ret
.LBB0_1:
        xor     eax, eax
        ret

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

Люди, которые разрабатывают и обслуживают компиляторы, имеют ограниченное количество времени и энергии, которые они могут тратить на свою работу, поэтому они обычно хотят сосредоточиться на том, что больше всего волнует их пользователей: превращении хорошо написанного кода в быстрый код. Они не хотят тратить свое время, пытаясь найти способы превратить глупый код в быстрый код - для этого и нужна проверка кода. В языке высокого уровня может быть «глупый» код, который выражает важную идею, поэтому разработчикам стоит потратить время на то, чтобы сделать это быстро - например, сокращенная вырубка леса и слияние потоков позволяют программам Haskell структурироваться вокруг определенных типов ленивых создаваемые структуры данных для компиляции в жесткие циклы, не выделяющие память. Но такой стимул просто не применим к превращению зацикленного сложения в умножение. Если вы хотите, чтобы это было быстро,