Защо 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 = 0x2aaaaaaa

v2 = 0x02222222

По-долу са разглобени инструкции за реда "int v1 = count >> 2;" с -O0 и -O1.

С -O0:

sarl $0x2, %esi

С -O1:

shrl $0x2, %esi

По-долу са разглобени инструкции за реда "int v2 = v1 & mask2;" с -O0 и -O1.

С -O0:

andl -0x24(%ebp), %esi //-0x24(%ebp) съхранява 0x33333333

С -O1:

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 signed overflow се използва като пример за недефинирано поведение, 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, така че изпращането на 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
Кодът наистина трябва да проверява дали параметърът действително е въведен от потребителя, в противен случай кодът ще има събитие за грешка на seg, когато се извика функцията: 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 Съжалявам за липсващите части. Току-що добавих инструкциите #include и проверката на argc.   -  person Zack Zhu    schedule 22.12.2017
comment
@Lundin Благодаря за съвета относно stdint.h. Кодът е експериментална част, базирана на моето решение за Data Lab от курса CS:APP @ CMU. Лабораторията иска от студента да имплементира функция, която отчита броя на 1 бит от int променлива, без да използва друг тип освен int. Сега разбирам, че int с изместване надясно има несигурност, но все още не разбирам защо оптимизацията променя mask2 (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 премахна несъответствието. Но все още не разбирам защо оптимизацията променя mask2 на 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 Standard §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