Почему компилятор C++ может дублировать базовый блок выхода из функции?

Рассмотрим следующий фрагмент кода:

int* find_ptr(int* mem, int sz, int val) {
    for (int i = 0; i < sz; i++) {
        if (mem[i] == val) { 
            return &mem[i];
        }
    }
    return nullptr;
}

GCC -O3 компилирует это так:

find_ptr(int*, int, int):
        mov     rax, rdi
        test    esi, esi
        jle     .L4                  # why not .L8?
        lea     ecx, [rsi-1]
        lea     rcx, [rdi+4+rcx*4]
        jmp     .L3
.L9:
        add     rax, 4
        cmp     rax, rcx
        je      .L8
.L3:
        cmp     DWORD PTR [rax], edx
        jne     .L9
        ret
.L8:
        xor     eax, eax
        ret
.L4:
        xor     eax, eax
        ret

В этой сборке блоки с метками .L4 и .L8 идентичны. Не лучше ли переписать переходы с .L4 на .L8 и сбросить .L4? Я думал, что это может быть ошибкой, но clang также дублирует последовательность xor - ret. Тем не менее, ICC и MSVC используют совершенно разные подходы.

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

Ответы

Ответ 1

Это всегда пропущенные оптимизации. Если оба пути возврата-0 используют один и тот же базовый блок, это будет чистой победой для всех микроархитектур, которые заботятся о современных компиляторах.

Но, к сожалению, эта пропущенная оптимизация не редкость для gcc. Часто это отдельная голая ret которой gcc условно веткится, вместо того, чтобы переходить к ret в другом существующем пути. (x86 не имеет условного ret, поэтому простым функциям, которые не нуждаются в очистке стека, часто просто нужно перейти к ret. Часто такие маленькие функции вставляются в полную программу, поэтому, возможно, это не повредит много в реале?)

Современные процессоры имеют стек предикторов обратных адресов, который легко предсказывает цель перехода для команд ret, поэтому не будет эффекта, когда одна команда ret чаще возвращается к одному вызывающему, а другая ret чаще возвращается к другому вызывающему. не помогите прогнозировать ветвь, чтобы разделить их и позволить им использовать разные записи. (Возможно, это поможет с -mtune=pentium3 или другими древними процессорами без предиктора RAS, но даже в этом случае вы не потратите дополнительный размер кода только на это.)

IDK о Pentium 4 и о том, следуют ли следы в его кеше трассировки call/ret. Но, к счастью, это уже не актуально. Кэш с декодированным Uop в семействе SnB и Ryzen не является кешем трассировки; строка/способ кэша UOP содержит Uops для непрерывного блока машинного кода x86, а безусловные переходы завершают строку кэша UOP. (https://agner.org/optimize/) Так что, если что-нибудь, это может быть хуже для семейства SnB, потому что для каждого пути возврата требуется отдельная строка кэша UOP, хотя каждый из них всего 2 UOP (xor-zero) и ret - это инструкции для одного мопа).

Сообщить об этом MCVE в gcc bugzilla с пропущенной ключевой оптимизацией: https://gcc.gnu.org/bugzilla/enter_bug.cgi?product=gcc

(обновление: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90178)

Причина:

Вы можете отчасти видеть, как это может прибыть на 2 выхода блоков: компиляторы, как правило преобразования for петель в if(sz>0) { do{}while(); }, if(sz>0) { do{}while(); } if(sz>0) { do{}while(); } если есть возможность его запуска 0 раз, как это делал gcc здесь. Так что есть одна ветвь, которая покидает функцию, вообще не входя в цикл. Но другой выход из провала из циклы. Возможно, прежде чем оптимизировать некоторые вещи, была некоторая дополнительная очистка. Или просто эти пути были разделены, когда была создана первая ветвь.

Я не знаю, почему gcc не замечает и объединяет два одинаковых базовых блока, которые заканчиваются на ret.

Возможно, он искал это только в каком-то проходе GIMPLE или RTL, где они фактически не были идентичны, а стали идентичными только во время финального кода x86. Может быть, после оптимизации сохранения/восстановления реестра для хранения некоторого временного файла, который в итоге оказался ненужным?

Вы можете копать глубже, если вы посмотрите на GCC GIMPLE или RTL с -fdump-tree-... после определенных проходов оптимизации: для этого у Godbolt есть пользовательский интерфейс + выпадающем меню + dropdown → tree/RTL. https://godbolt.org/z/l9mVlE. Но если вы не являетесь экспертом gcc-internals и не планируете работать над патчем или идеей, чтобы помочь gcc найти эту оптимизацию, это, вероятно, не стоит вашего времени.

Интересное открытие, что это происходит только с -mavx (включается -march=skylake или напрямую). GCC и clang не знают, как автоматически векторизовать циклы, в которых число отключений неизвестно до первой итерации. например, такие циклы поиска, как memchr или strlen. Итак, IDK, почему AVX вообще имеет значение.

(Обратите внимание, что абстрактная машина C никогда не читает mem[i] за пределами точки поиска, и эти элементы могут фактически не существовать. Например, UB не будет, если вы передадите этой функции указатель на последний int перед не отображенной страницей, и sz=1000 До тех пор, пока *mem == val. Таким образом, для автоматической векторизации без гарантированного размера объекта int mem[static sz] компилятору придется выравнивать указатель... Не то, чтобы C11 int mem[static sz] даже помогло бы; даже статический массив с постоянным размером времени компиляции, превышающим максимально возможное число отключений, не получит gcc для автоматической векторизации.)