Почему clang выдает неправильные результаты для моего кода c, скомпилированного с -O1, но не с -O0?

Для ввода 0xffffffff следующий код c работает нормально без оптимизации, но дает неверные результаты при компиляции с параметром -O1. Другие параметры компиляции: -g -m32 -Wall. Код протестирован с clang-900.0.39.2 в macOS 10.13.2.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    if (argc < 2) return 1;

    char *endp;
    int x = (int)strtoll(argv[1], &endp, 0);

    int mask1 = 0x55555555;
    int mask2 = 0x33333333;
    int count = (x & mask1) + ((x >> 1) & mask1);

    int v1 = count >> 2;
    printf("v1 = %#010x\n", v1);

    int v2 = v1 & mask2;
    printf("v2 = %#010x\n", v2);

    return 0;
}

Ввод: 0xffffffff

Выходы с -O0: (ожидается)

v1 = 0xeaaaaaaa

v2 = 0x22222222

Выходы с -O1: (неправильно)

v1 = 0x2ааааааа

v2 = 0x02222222

Ниже приведены дизассемблированные инструкции для строки "int v1 = count >> 2;" с -O0 и -O1.

С -O0:

сарл $0x2, %esi

С -О1:

шрл $0x2, %esi

Ниже приведены дизассемблированные инструкции для строки "int v2 = v1 & mask2;" с -O0 и -O1.

С -O0:

andl -0x24(%ebp), %esi //-0x24(%ebp) сохраняет 0x33333333

С -О1:

andl $0x13333333, %esi //почему оптимизация меняет 0x33333333 на 0x13333333?

Кроме того, если для x локально установлено значение 0xffffffff вместо получения его значения из аргументов, код будет работать должным образом даже с -O1.

P.S. Код представляет собой экспериментальную часть, основанную на моем решении Data Lab из курса CS:APP @ CMU. Лабораторная работа просит студента реализовать функцию, которая подсчитывает число 1 бит переменной int без использования какого-либо другого типа, кроме int.


person Zack Zhu    schedule 21.12.2017    source источник
comment
0xffffffff это › MAX_INT в вашем случае, а переполнение int является неопределенным поведением.   -  person Stargateur    schedule 22.12.2017
comment
@Stargateur Ты уверен? Разве это не должно быть -1?   -  person Sergey Kalinichenko    schedule 22.12.2017
comment
Подписанное переполнение @dasblinkenlight используется как пример неопределенного поведения, port70.net /~nsz/c/c11/n1570.html#3.4.3p3.   -  person Stargateur    schedule 22.12.2017
comment
Тем не менее, я предлагаю вам использовать unsigned int по многим причинам, битовый оператор следует использовать только с unsigned integer, printf("v1 = %#010x\n", v1); => %x ожидать unsigned int, поэтому поведение undefined для отправки int.   -  person Stargateur    schedule 22.12.2017
comment
можно воспроизвести с помощью clang .. Я получаю одинаковый (правильный) вывод с помощью gcc как для -O0, так и для -O1   -  person yano    schedule 22.12.2017
comment
но я думаю, что проблема в том, что отрицательные знаковые типы со сдвигом вправо определяются реализацией (и, по-видимому, clang и gcc обрабатывают это по-разному). Вероятно, безопаснее всего ограничить битовые операции беззнаковыми типами: целое число"> stackoverflow.com/questions/4009885/   -  person yano    schedule 22.12.2017
comment
Я удивлен, что это вообще работает из-за отсутствующих операторов #include   -  person user3629249    schedule 22.12.2017
comment
никогда не выходите за пределы argv[0] без предварительной проверки argc, чтобы убедиться, что пользователь действительно ввел ожидаемый параметр командной строки   -  person user3629249    schedule 22.12.2017
comment
этот оператор: int count = (x & mask1) + ((x >> 1) & mask1); приведет к переполнению переменной count Предложите привести выражения к ssize_t или лучше int64_t и объявить count как более длинный тип.   -  person user3629249    schedule 22.12.2017
comment
Код действительно должен проверять, действительно ли параметр был введен пользователем, иначе код будет иметь событие ошибки сегмента при вызове функции: strtol()   -  person user3629249    schedule 22.12.2017
comment
@Stargateur: преобразование слишком большого целочисленного значения в целочисленный тип со знаком не является неопределенным поведением. Это поведение, определяемое реализацией. Переполнение со знаком вызывает неопределенное поведение, когда это происходит во время оценки арифметических операторов (об этом говорит ваша ссылка). Переполнение во время преобразования в целочисленный тип со знаком определяется реализацией (port70.net/~nsz/c/c11/n1570.html#6.3.1.3p3). Только значения с плавающей запятой могут вызывать UB при преобразовании в целые типы.   -  person AnT    schedule 22.12.2017
comment
Этот код страдает от неаккуратного набора текста, а это означает, что программист не задумывался о размере или подписи, необходимых для их алгоритма, он просто набирал int повсюду. Неаккуратная типизация имеет тенденцию приводить к различным формам плохо определенных ошибок поведения и всегда приводит к полностью непереносимому коду. Профессиональные программисты используют stdint.h.   -  person Lundin    schedule 22.12.2017
comment
@user3629249 user3629249 Извините за недостающие части. Я только что добавил операторы #include и проверку argc.   -  person Zack Zhu    schedule 22.12.2017
comment
@Lundin Спасибо за совет по stdint.h. Код представляет собой экспериментальную часть, основанную на моем решении Data Lab из курса CS:APP @ CMU. Лабораторная работа просит студента реализовать функцию, которая подсчитывает количество 1 бит переменной int, не используя какой-либо другой тип, кроме int. Теперь я понимаю, что сдвиг вправо int имеет неопределенность, но я все еще не понимаю, почему оптимизация меняет маску2 (0x33333333) на 0x13333333.   -  person Zack Zhu    schedule 22.12.2017
comment
@ZackZhu Понятия не имею. gcc -O1 и -O3 не меняют эту маску при разборке.   -  person Lundin    schedule 22.12.2017


Ответы (3)


Как отметили несколько комментаторов, знаковые значения со сдвигом вправо нечетко определены.

Я изменил объявление и инициализацию x на

unsigned int x = (unsigned int)strtoll(argv[1], &endp, 0);

и получили согласованные результаты при -O0 и -O1. (Но прежде чем внести это изменение, я смог воспроизвести ваш результат под clang в MacOS.)

person Steve Summit    schedule 22.12.2017
comment
Я могу подтвердить, что изменение типа x на unsigned устранило несоответствие. Но я до сих пор не понимаю, почему оптимизация меняет маску2 на 0x13333333. - person Zack Zhu; 22.12.2017
comment
@ZackZhu Я тоже не совсем понимаю, хотя это может быть просто разница между сдвигом на 0 или сдвигом на 1 на левом краю. Но для меня это даже не интересный вопрос. Хотя здесь мы говорим о поведении, определяемом реализацией, а не о неопределенном, большая часть этот другой ответ применим. - person Steve Summit; 22.12.2017

Как вы обнаружили, вы вызываете Поведение, определяемое реализацией при попытке сохранить 0xffffffff (4294967295) в int x (где INT_MAX равно 7fffffff или 2147483647). Стандарт C11 §6.3.1.3 (проект n1570) — целые числа со знаком и без знака Всякий раз, когда вы используете strtoll (или strtoull) (подойдут обе версии с 1-l) и пытаетесь сохранить значение как int, вы должны сверить результат с INT_MAX перед выполнением присваивания с приведением. (или при использовании точных типов ширины против INT32_MAX или UINT32_MAX для беззнакового)

Кроме того, в таких обстоятельствах, когда задействованы битовые операции, вы можете устранить неопределенность и обеспечить переносимость, используя точные типы ширины, представленные в stdint.h, и соответствующие спецификаторы формата, представленные в inttypes.h. Здесь нет необходимости использовать подписанный int. Было бы разумнее обрабатывать все значения как unsigned (или uint32_t).

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

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

int main (int argc, char *argv[]) {

    uint64_t tmp = argc > 1 ? strtoul (argv[1], NULL, 0) : 0xffffffff;

    if (tmp > UINT32_MAX) {
        fprintf (stderr, "input exceeds UINT32_MAX.\n");
        return 1;
    }

    uint32_t x = (uint32_t)tmp,
        mask1 = 0x55555555,
        mask2 = 0x33333333,
        count = (x & mask1) + ((x >> 1) & mask1),
        v1 = count >> 2,
        v2 = v1 & mask2;

    printf("v1 = 0x%" PRIx32 "\n", v1);

    printf("v2 = 0x%" PRIx32 "\n", v2);

    return 0;
}

Пример использования/вывода

$ ./bin/masktst
v1 = 0x2aaaaaaa
v2 = 0x22222222

Составлено

$ gcc -Wall -Wextra -pedantic -std=gnu11 -Ofast -o bin/masktst masktst.c

Просмотрите все и дайте мне знать, если у вас есть дополнительные вопросы.

person David C. Rankin    schedule 22.12.2017
comment
Преобразование слишком большого целочисленного значения в целочисленный тип со знаком не является неопределенным поведением. Это поведение, определяемое реализацией. - person AnT; 22.12.2017
comment
Хороший вопрос, это тонкие моменты «определенного» словоблудия, которые сбили меня с толку. (Приложение J.2 или J.3) Фактическая стандартная ссылка (вне Приложения) — 6.3.1.3 Целые числа со знаком и без знака Будь то неопределенное или определенное реализацией - я стараюсь избегать этого, как чумы... - person David C. Rankin; 22.12.2017

это утверждение:

int x = (int)strtoll(argv[1], &endp, 0);

приводит к переполнению со знаком, что является неопределенным поведением.

(в моей системе результат: -1431655766

Полученные значения имеют тенденцию идти вниз:

Переменная: v1 получает: -357913942

Переменная: v2 получает: 572662306

спецификатор формата %x корректно работает только с беззнаковыми переменными

person user3629249    schedule 22.12.2017
comment
Это преобразование вне допустимого диапазона, а не переполнение. См. 6.3.1.3/3 о поведении преобразования вне диапазона (которое не является UB). - person M.M; 22.12.2017
comment
Или это было бы, если бы OP действительно включал stdlib.h - как есть, вызов strtoll является нарушением ограничения в C99 для вызова необъявленной функции (а strtoll не существовало в C89) - person M.M; 22.12.2017