Почему / как gcc компилирует неопределенное поведение в этом тесте с переполнением со знаком, чтобы он работал на x86, но не на ARM64?
Я самостоятельно изучал CSAPP и получил странный результат, когда натолкнулся на странную проблему во время выполнения теста утверждений.
Я не уверен, с чего начать этот вопрос, поэтому позвольте мне сначала получить код (имя файла видно в комментариях):
// File: 2.30.c
// Author: iBug
int tadd_ok(int x, int y) {
if ((x ^ y) >> 31)
return 1; // A positive number and a negative integer always add without problem
if (x < 0)
return (x + y) < y;
if (x > 0)
return (x + y) > y;
// x == 0
return 1;
}
// File: 2.30-test.c
// Author: iBug
#include <assert.h>
int tadd_ok(int x, int y);
int main() {
assert(sizeof(int) == 4);
assert(tadd_ok(0x7FFFFFFF, 0x80000000) == 1);
assert(tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0);
assert(tadd_ok(0x80000000, 0x80000000) == 0);
return 0;
}
И команды:
gcc -o test -O0 -g3 -Wall -std=c11 2.30.c 2.30-test.c
./test
(Примечание: не было -O опция присутствует в командной строке, но по умолчанию она равна 0, добавляя явно -O0 не должно сильно меняться.)
Вышеуказанные две команды работали очень хорошо на моей виртуальной машине Ubuntu (amd64, GCC 7.3.0), но на моем телефоне Android не удалось выполнить одно из утверждений (AArch64 или armv8-a, GCC 8.2.0).
2.30-test.c:13: main: assertion "tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0" failed
Обратите внимание, что первое утверждение прошло, поэтому int гарантированно будет 4 байта на платформах.
Так что я загорелся gdb на моем телефоне пытаюсь понять:
(gdb) l 2.30.c:1
1 // File: 2.30.c
2 // Author: iBug
3
4 int tadd_ok(int x, int y) {
5 if ((x ^ y) >> 31)
6 return 1; // A positive number and a negative integer always add without problem
7 if (x < 0)
8 return (x + y) < y;
9 if (x > 0)
10 return (x + y) > y;
(gdb) b 2.30.c:10
Breakpoint 1 at 0x728: file 2.30.c, line 10.
(gdb) r
Starting program: /data/data/com.termux/files/home/CSAPP-2019/ch2/test
warning: Unable to determine the number of hardware watchpoints available.
warning: Unable to determine the number of hardware breakpoints available.
Breakpoint 1, tadd_ok (x=2147483647, y=2147483647)
at 2.30.c:10
10 return (x + y) > y;
(gdb) p x
$1 = 2147483647
(gdb) p y
$2 = 2147483647
(gdb) p (x + y) > y
$3 = 0
(gdb) c
Continuing.
2.30-test.c:13: main: assertion "tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) == 0" failed
Program received signal SIGABRT, Aborted.
0x0000007fb7ca5928 in abort ()
from /system/lib64/libc.so
(gdb) d 1
(gdb) p tadd_ok(0x7FFFFFFF, 0x7FFFFFFF)
$4 = 1
(gdb)
Как вы видите в выводе GDB, результат очень противоречив, так как return заявление о 2.30.c:10 было достигнуто, и возвращаемое значение должно было быть 0, но функция по-прежнему возвращает 1, что делает утверждение неудачным.
Просьба представить идею, что я здесь не так.
Пожалуйста, уважайте то, что я представил. Просто сказать, что это UB без связи с платформами, особенно с выводом GDB, не будет никакой пользы.
6 ответов
Переполнение со знаком является неопределенным поведением в ISO C. Вы не можете надежно вызвать это, а затем проверить, произошло ли это.
В выражении (x + y) > y; , компилятор может предполагать, что x+y не переполняется (потому что это будет UB). Таким образом, он оптимизирует до проверки x > 0 , (Да, действительно, GCC делает это даже в -O0).
Эта оптимизация является новой в gcc8. То же самое на x86 и AArch64; вы должны были использовать разные версии GCC на AArch64 и x86. (Даже в -O3, gcc7.x и ранее (намеренно?) пропускают эту оптимизацию. clang7.0 тоже этого не делает. Они на самом деле делают 32-битное сложение и сравнение. Они также скучают по оптимизации tadd_ok в return 1 или add и проверка флага переполнения (V на ARM, OF на х86). Оптимизированный Asm Clang представляет собой интересную смесь >>31, ИЛИ и одна операция XOR, но -fwrapv фактически изменяет этот asm, поэтому он, вероятно, не выполняет полную проверку переполнения.)
Можно сказать, что gcc8 "ломает" ваш код, но на самом деле он уже был взломан, поскольку легальный / переносимый ISO C. gcc8 только что выявил этот факт.
Чтобы увидеть это более четко, давайте выделим только это выражение в одну функцию. gcc -O0 в любом случае каждый оператор компилируется отдельно, поэтому информация о том, x<0 не влияет на -O0 код для этого утверждения в вашем tadd_ok функция.
// compiles to add and checking the carry flag, or equivalent
int unsigned_overflow_test(unsigned x, unsigned y) {
return (x+y) >= y; // unsigned overflow is well-defined as wrapping.
}
// doesn't work because of UB.
int signed_overflow_expression(int x, int y) {
return (x+y) > y;
}
На проводнике компилятора Godbolt с AArch64 GCC8.2 -O0 -fverbose-asm:
signed_overflow_expression:
sub sp, sp, #16 //,, // make a stack fram
str w0, [sp, 12] // x, x // spill the args
str w1, [sp, 8] // y, y
// end of prologue
// instructions that implement return (x+y) > y; as return x > 0
ldr w0, [sp, 12] // tmp94, x
cmp w0, 0 // tmp94,
cset w0, gt // tmp95, // w0 = (x>0) ? 1 : 0
and w0, w0, 255 // _1, tmp93 // redundant
// epilogue
add sp, sp, 16 //,,
ret
НКУ -ftree-dump-original или же -optimized даже превратит свой GIMPLE обратно в C-подобный код с этой оптимизацией (по ссылке Godbolt):
;; Function signed_overflow_expression (null)
;; enabled by -tree-original
{
return x > 0;
}
К сожалению даже с -Wall -Wextra -Wpedantic Предупреждения о сравнении нет. Это не тривиально, правда; это все еще зависит от x,
Оптимизированный asm неудивительно cmp w0, 0 / cset w0, gt / ret, И с 0xff избыточно cset псевдоним csinc используя нулевой регистр в качестве обоих источников. Таким образом, он будет производить 0 / 1. С другими регистрами, общий случай csinc условный выбор и приращение любых двух регистров.
Тем не мение, cset является эквивалентом AArch64 для x86 setcc для превращения состояния флага в bool в реестре.
Если вы хотите, чтобы ваш код работал как написано, вам нужно скомпилировать с -fwrapv чтобы сделать это четко определенное поведение в варианте C, который -fwrapv заставляет GCC внедрять. По умолчанию -fstrict-overflow, как стандарт ISO C.
Если вы хотите проверить переполнение со знаком в современном C, вам нужно написать проверки, которые обнаруживают переполнение, фактически не вызывая его. Это сложнее, раздражает и вызывает споры между авторами компиляторов и (некоторыми) разработчиками. Они утверждают, что языковые правила вокруг неопределенного поведения не предназначались для использования в качестве предлога для "бесполезного разрыва" кода при компиляции для целевых машин, где это имело бы смысл в asm. Но современные компиляторы в основном реализуют только ISO C (с некоторыми расширениями и дополнительным определенным поведением), даже при компиляции для целевых архитектур, таких как x86 и ARM, где целые числа со знаком не имеют дополнения (и, таким образом, просто переносятся) и не перехватывают переполнение.
Таким образом, вы могли бы сказать "выстрелы" в этой войне, с изменением в gcc8.x на фактическое "взлом" небезопасного кода, подобного этому.:П
См. Обнаружение переполнения со знаком в C/C++ и Как проверить целочисленное переполнение со знаком в C без неопределенного поведения?
Поскольку сложение со знаком и без знака - это одна и та же двоичная операция в дополнении 2, вы можете просто привести к unsigned для добавления и отбросить для подписанного сравнения. Это сделало бы версию вашей функции безопасной для "нормальных" реализаций: дополнение 2 и приведение между unsigned а также int это просто переосмысление одних и тех же битов.
У этого не может быть UB, просто он не даст правильного ответа относительно реализации дополнения или знака / величины C.
return (int)((unsigned)x + (unsigned)y) > y;
Это компилирует (с gcc8.2 -O3 для AArch64) в
add w0, w0, w1 // x+y
cmp w0, w1 // x+y cmp y
cset w0, gt
ret
Если бы вы написали int sum = x+y как отдельное утверждение C от return sum < y этот UB не будет виден gcc с отключенной оптимизацией. Но как часть того же выражения, даже gcc по умолчанию -O0 могу видеть это.
UB, видимый во время компиляции, - это все виды плохого. В этом случае только определенные диапазоны входов будут генерировать UB, поэтому компилятор предполагает, что этого не происходит. Если безусловный UB виден на пути выполнения, оптимизирующий компилятор может предположить, что путь никогда не произойдет. (В функции без ветвления можно предположить, что эта функция никогда не вызывается, и скомпилировать ее в одну недопустимую инструкцию.) См. Допускает ли стандарт C++ неинициализированный bool для сбоя программы? для получения дополнительной информации о UB, видимом во время компиляции.
(-O0 не означает "нет оптимизации", это означает, что нет никакой дополнительной оптимизации, кроме того, что уже необходимо преобразовать посредством внутренних представлений gcc на пути к asm для любой целевой платформы. @Basile Starynkevitch объясняет в " Отключить все параметры оптимизации в GCC)
Некоторые другие компиляторы могут "отключить свой мозг" еще больше с отключенной оптимизацией и сделать что-то ближе к транслитерации C в asm, но gcc не такой. Например, gcc по-прежнему использует мультипликативный обратный для целочисленного деления на константу в -O0, ( Почему GCC использует умножение на странное число при реализации целочисленного деления?) Все 3 других основных компилятора x86 (clang/ICC/MSVC) используют div,
Переполнение целых чисел со знаком вызывает неопределенное поведение. Вы не можете проверить состояние переполнения, добавив два числа и проверив, не обернут ли они каким-либо образом. Хотя это может сойти с рук в системе x86/x64, нет гарантии, что другие будут вести себя так же.
Что вы можете сделать, однако, это некоторая арифметика вместе с INT_MAX или же INT_MIN сделать проверку.
int tadd_ok(int x, int y) {
if ((x ^ y) >> 31)
return 1; // A positive number and a negative integer always add without problem
if (x < 0)
return INT_MIN - x < y;
if (x > 0)
return INT_MAX - x > y;
// x == 0
return 1;
}
Выражение INT_MAX - x > y арифметически эквивалентно INT_MAX > x + y но предотвращает переполнение. Так же, INT_MIN - x < y арифметически эквивалентно INT_MIN < x + y но предотвращает переполнение.
РЕДАКТИРОВАТЬ:
Если вы хотите принудительно определить целочисленное переполнение со знаком, вы можете использовать -fwrapv вариант для gcc. Однако лучше избегать переполнения.
Я хотел бы добавить, что в GCC есть простой способ справиться с подписанным дополнением с помощью переполнения и определить его. Вы можете использовать встроенные функции, задокументированные на https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html для выполнения подписанных операций (add, sub, mul), которые определены для переноса, и он сообщит вам переполнена ли операция.
bool __builtin_add_overflow(type1 a, type2 b, type3 *res)
Например, вы можете переписать вашу функцию следующим образом:
int tadd_ok(int x, int y) {
int result;
return !__builtin_add_overflow(x, y, &result);
// result now contains (int)((unsigned int)x + (unsigned int)y)
}
Я знаю, что вы просили что-то другое, кроме UB, но я боюсь, что это является причиной проблемы в вашем случае, даже если вы используете -O0, Давайте посмотрим на сгенерированную сборку.
Я упростил вашу функцию для этого, чтобы изолировать UB:
int tadd_ok(int x, int y) {
if (x > 0)
return (x + y) > y;
return 1;
}
Выходные данные, сгенерированные для AArch64 (-O0 -x c -march=armv8-a):
tadd_ok:
sub sp, sp, #16
str w0, [sp, 12]
str w1, [sp, 8]
ldr w0, [sp, 12]
cmp w0, 0
ble .L2 ; if (x <= 0) goto return stmt
ldr w0, [sp, 12] ; here we are runnig (x + y) > y branch
cmp w0, 0 ; x is compared to zero
cset w0, gt ; return value is set to (x > 0)
and w0, w0, 255
b .L3
.L2:
mov w0, 1
.L3:
add sp, sp, 16
ret
Помните, что, поскольку целые числа со знаком не могут переполняться, выражение (x + y) всегда больше чем y если x <= 0, GCC знает об этом до запуска оптимизатора, поэтому он заменяет (x + y) > y с x > 0,
Даже при том, что он только что сделал ту же самую проверку, это, кажется, забывает об этом - побочный эффект отсутствия включенных оптимизаций.
Вы можете заменить код C выше с этим:
int tadd_ok(int x, int y) {
if (x > 0)
return x > 0;
return 1;
}
И вывод не меняется:
tadd_ok:
sub sp, sp, #16
str w0, [sp, 12]
str w1, [sp, 8]
ldr w0, [sp, 12]
cmp w0, 0
ble .L2
ldr w0, [sp, 12]
cmp w0, 0
cset w0, gt
and w0, w0, 255
b .L3
.L2:
mov w0, 1
.L3:
add sp, sp, 16
ret
С приведенным выше кодом ясно, что оптимизатор сделает с ним:
tadd_ok:
mov w0, 1
ret
Другие опции, которые вы используете, ничего не меняют, платформа не имеет значения, так как не генерируются инструкции по добавлению.
Что касается GDB: он выполняет сложные выражения, выполняя их в процессе отладки, используя тот же код, который был сгенерирован компилятором, поэтому выходные данные не будут отличаться. Отсюда и оценка tadd_ok(0x7FFFFFFF, 0x7FFFFFFF) запускает тот же код.
Как вам уже сказали, вы вызываете неопределенное поведение. Переполнение не определено для целых чисел со знаком в C. Компилятор понимает, что второе и третье, если операторы не определены в терминах целых чисел со знаком, следовательно, компилятор решает, что какая бы ветвление не было принято, не может произойти в хорошо определенной программе. Таким образом, вся функция tadd_ok рушится в единый return 1,
Неважно, если вы отключите оптимизацию: эти операторы, вызывающие неопределенное поведение, определяются задолго до того, как оптимизатор начинает работать.
И также не имеет значения, что вы включаете генерацию отладочной информации, потому что это не меняет способ генерации кода (он просто добавляет аннотации для инструментов, которые интерпретируют двоичные дампы и состояние процесса).
Последнее, но не менее важное, когда вы заставляете GDB печатать результат оператора (x+y)>y это делается вне рамок компиляции Си, но с точки зрения инструкций "работа на металле". После C не единственный язык, который скомпилирован в бинарный. И хотя недопустимое целочисленное значение со знаком не определено в C, оно может быть совершенно точно определено на другом языке; и вы можете захотеть использовать GDB в таких программах. При сравнении выхода p (x+y)>y с заявлением C (x+y)>y с x а также y являющийся signed intсравниваешь апельсины с яблоками; это очень разные вещи.
Целочисленное переполнение со знаком является неопределенным поведением в соответствии со стандартом C, в отличие от переполнения без знака, которое гарантированно будет изменено.
Попробуйте поместить свой код на Godbolt с последними версиями GCC x86-64 и -O3. Он оптимизирован для:
mov eax, 1
ret
Что приемлемо. Я предполагаю, что для ARM64 генерируется эквивалентная последовательность команд, но я не знаю эту архитектуру и не могу быть уверен, просто посмотрев.