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

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

26 голосов
/ 18 апреля 2019

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

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 on -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 Ответ

8 голосов
/ 19 апреля 2019

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

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

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

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

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

(обновление: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90178, о котором сообщилOP, и исправлена ​​через несколько дней.)

Причина:

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

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

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

Вы можете копать глубже, если вы посмотрите на GIMPLE или RTL в GCC с опциями -fdump-tree-... после определенных проходов оптимизации: Godboltдля этого есть пользовательский интерфейс в выпадающем списке + -> 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 для автоматической векторизации.)

...