Является ли это ошибкой оптимизатора clang или поведения undefined в C?

Этот код дает разные результаты для -O1 и -O2:

/*
    Example of a clang optimization bug.
    Mark Adler, August 8, 2015.

    Using -O0 or -O1 takes a little while and gives the correct result:

        47 bits set (4294967296 loops)

    Using -O2 or -O3 optimizes out the loop, returning immediately with:

        0 bits set (4294967296 loops)

    Of course, there weren't really that many loops.  The number of loops was
    calculated, correctly, by the compiler when optimizing.  But it got the
    number of bits set wrong.

    This is with:

        Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
        Target: x86_64-apple-darwin14.4.0

 */

#include <stdio.h>
#include <inttypes.h>

/* bit vector of 1<<32 bits, initialized to all zeros */
static uint64_t vec[1 << 26] = {0};

int main(void)
{
    /* set 47 of the bits. */
    vec[31415927] = UINT64_C(0xb9fe2f2fedf7ebbd);

    /* count the set bits */
    uint64_t count = 0;
    uint64_t loops = 0;
    uint32_t x = 0;
    do {
        if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))
            count++;
        x++;
        loops++;
    } while (x);
    printf("%" PRIu64 " bits set (%" PRIu64 " loops)\n", count, loops);
    return 0;
}

Так это ошибка? Или существует какое-то поведение undefined, что компилятор в пределах своих прав дает разные результаты для?

Насколько я могу судить по стандарту C99, цикл do для прохождения всех значений uint32_t действителен, так как приращение наибольшего значения без знака равнозначно, чтобы привести к нулю.

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

Ответы

Ответ 1

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

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

ОБНОВЛЕНИЕ: Марк Адлер, оригинальный плакат, сообщил об этом и подтвердил, что это ошибка в pre-3.6.0 clang, исправленная в более поздних версиях. Я бесстыдно украду эту ссылку на отчет об ошибке из своего ответа.

Правильный вывод:

47 bits set (4294967296 loops)

Чтобы рассмотреть некоторые из вещей, которые были указаны (или что я заметил сам):

static uint64_t vec[1 << 26] = {0};

Это большой объект (2 29 байты или половина гигабайта, предполагая CHAR_BIT==8), но он, по-видимому, не превышает емкость реализации. Если бы это было так, это было бы отклонено. Я не на 100% уверен, что стандарт требует этого, но поскольку программа работает корректно на более низких уровнях оптимизации, мы можем предположить, что объект не слишком велик.

vec[31415927] = 0xb9fe2f2fedf7ebbd

Постоянная 0xb9fe2f2fedf7ebbd не является проблемой. Его значение находится между 2 63 и 2 64 поэтому оно находится в диапазоне uint64_t. Тип шестнадцатеричной целочисленной константы достаточно широка, чтобы удерживать ее значение (если оно не превышает ULLONG_MAX, но это не так).

if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))

Я кратко подумал, что сдвиг влево может быть проблемой, но это не так. Левый операнд имеет тип uint64_t, а правый операнд находится в диапазоне 0.. 63. Левый сдвиг в 64 бита будет иметь поведение undefined, но это не так.

printf("%llu bits set (%llu loops)\n", count, loops);

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

%llu требуется аргумент типа unsigned long long; count и loops имеют тип uint64_t. Здесь, в зависимости от реализации, мы могли бы иметь поведение undefined (в моей системе uint64_t есть typedef для unsigned long, и я получаю предупреждение). Но это вряд ли вызовет какие-либо реальные проблемы (unsigned long long и uint64_t обычно имеют одинаковое представление, даже если они не одного типа), и когда я добавляю отливки, чтобы избежать UB:

printf("%llu bits set (%llu loops)\n",
       (unsigned long long)count,
       (unsigned long long)loops);

Я получаю такое же поведение. Следующие результаты для программы с добавлениями, добавленными к вызову printf. Забастовкa >

Используя gcc 5.2.0 на моей 64-битной системе, я получаю правильный вывод с -O0, -O1, -O2 и -O3 с или без -m32. Время указывает, что gcc не устраняет цикл на любом уровне оптимизации.

Используя clang 3.4 в той же системе, я получаю правильный вывод с -O0 или -O1, но неверный вывод (0 bits set) в -O2 или -O3. Сроки показывают, что цикл исключается при -O2 и -O3. Когда я компилирую с clang -m32, вывод корректен (и цикл не устраняется) на всех уровнях оптимизации.

Когда я изменяю объявление loops на

volatile uint64_t loops = 0;

Я получаю правильный вывод на всех уровнях оптимизации (и цикл не устраняется).

Дальнейшая настройка программы (не показана здесь) показывает, что vec[31415927] действительно установлен на 0xb9fe2f2fedf7ebbd, даже если оптимизация вызывает неправильное количество бит.

Ответ 2

Это ошибка в pre-3.6.0 clang. (Версия 3.6.0svn предшествует 3.6.0.) Поскольку она уже была исправлена ​​в версии 3.6.0 по состоянию на пять месяцев назад, я сообщил об ошибке Apple - это все еще их самый последний дистрибутив компилятора инструменты.

Ответ 3

Это похоже на ошибку в clang. Я могу воспроизвести это в моей 64-битной системе, запущенной clang3.4-1ubuntu3; как упоминается в другом ответе, я всегда получаю правильный вывод с помощью gcc (который никогда не оптимизирует цикл), но clang, похоже, оптимизирует цикл, если мы используем -O2 и -O3.

Этот ответ не добавляет много важного и выдающегося ответа Кейту, но для будущей ссылки я хочу показать возможное обходное решение (кроме volatile).

В самом деле, если любой из x, count или loops volatile будет исправлять его, но после некоторых экспериментов я решил, что ошибка проявляется только в циклах do { ... } while;.

Если вы измените код на использование цикла while или for (и внесите соответствующие изменения для поддержания поведения программы), clang всегда будет выдавать правильный вывод, и цикл не будет оптимизирован (но это все еще работает быстрее с помощью -O3).

Вот пример:

#include <stdio.h>
#include <inttypes.h>

/* bit vector of 1<<32 bits, initialized to all zeros */
static uint64_t vec[1 << 26] = {0};

int main(void)
{
    /* set 47 of the bits. */
    vec[31415927] = UINT64_C(0xb9fe2f2fedf7ebbd);

    /* count the set bits */
    uint64_t count = vec[0] & (uint64_t)1;
    uint64_t loops = 1;
    uint32_t x = 1;

    while (x) {
        if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))
            count++;
        x++;
        loops++;
    }

    printf("%" PRIu64 " bits set (%" PRIu64 " loops)\n", count, loops);
    return 0;
}