Переполнение со знаком в C ++ и неопределенное поведение (UB)

Мне интересно об использовании кода, как следующий

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Если цикл повторяется с течением nвремени, то factorон умножается на 10точное nвремя. Тем не менее, factorиспользуется только после умножения на 10общее количество n-1раз. Если мы предполагаем, что factorникогда не переполняется, за исключением последней итерации цикла, но может переполниться на последней итерации цикла, то должен ли такой код быть приемлемым? В этом случае значение factorнаверняка никогда не будет использовано после переполнения.

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

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

Компиляторы предполагают, что действительная программа на C ++ не содержит UB. Рассмотрим для примера:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Если x == nullptrзатем разыменование его и присвоение значения UB. Следовательно, единственный способ, которым это может закончиться в допустимой программе, - это когда x == nullptrникогда не будет возвращаться значение true, и компилятор может предположить, что согласно правилу «как будто» вышеприведенное эквивалентно

*x = 5;

Теперь в вашем коде

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

Последнее умножение factorне может произойти в допустимой программе (переполнение со знаком не определено). Следовательно, назначение resultне может произойти. Поскольку до последней итерации нет возможности ветвиться, предыдущей итерации быть не может. В конце концов, часть кода, которая является правильной (т. Е. Никогда не происходит неопределенное поведение):

// nothing :(

Поведение intпереполнения не определено.

Неважно, если вы читаете factorвне тела цикла; если он переполнен к тому времени, то поведение вашего кода до, после и несколько парадоксально до того, как переполнение не определено.

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

Разве вы не можете использовать unsignedтип для factorхотя тогда вам нужно беспокоиться о нежелательной конверсии intв unsignedв выражениях , содержащих как?

Может быть полезно рассмотреть реальные оптимизаторы. Разматывание петли - известная техника. Основная идея развертывания в том, что

for (int i = 0; i != 3; ++i)
    foo()

может быть лучше реализовано за кулисами, как

 foo()
 foo()
 foo()

Это простой случай с фиксированной границей. Но современные компиляторы также могут сделать это для переменных границ:

for (int i = 0; i != N; ++i)
   foo();

становится

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Очевидно, это работает, только если компилятор знает, что N <= 3. И вот где мы вернемся к первоначальному вопросу. Поскольку компилятор знает, что переполнение со знаком не происходит , он знает, что цикл может выполняться максимум 9 раз на 32-разрядных архитектурах. 10^10 > 2^32, Следовательно, он может развернуть цикл из 9 итераций. Но предполагаемый максимум был 10 итераций! ,

Может случиться так, что вы получите относительный переход к инструкции сборки (9-N) с N = 10, поэтому смещение равно -1, что является самой инструкцией перехода. К сожалению. Это вполне допустимая оптимизация цикла для четко определенного C ++, но приведенный пример превращается в жесткий бесконечный цикл.

Любое целочисленное переполнение со знаком приводит к неопределенному поведению, независимо от того, было ли переполненное значение считано или нет.

Возможно, в вашем случае вы можете вывести первую итерацию из цикла, повернув это

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

в это

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

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

Это UB; в терминах ISO C ++ все поведение всей программы совершенно не определено для выполнения, которое в конечном итоге достигает UB. Классический пример, насколько заботится стандарт C ++, может заставить демонов вылететь из вашего носа. (Я рекомендую против использования реализации, где носовые демоны являются реальной возможностью). Смотрите другие ответы для более подробной информации.

Компиляторы могут «вызывать проблемы» во время компиляции для путей выполнения, которые они могут видеть, приводя к UB, видимому во время компиляции, например, предполагая, что эти базовые блоки никогда не достигаются.

Смотрите также, что должен знать каждый программист на C о неопределенном поведении (блог LLVM). Как объяснялось там, UB со знаком переполнения позволяет компиляторам доказывать, что for(... i <= n ...)циклы не являются бесконечными циклами даже для неизвестных n. Это также позволяет им "продвигать" счетчики цикла int на ширину указателя вместо повторения расширения знака. (Таким образом, последствием UB в этом случае может быть доступ к элементам массива с низкими 64 КБ или 4 ГБ, если вы ожидали завертывания со знаком iв его диапазон значений.)

В некоторых случаях компиляторы будут выдавать недопустимую инструкцию, такую ​​как x86, ud2для блока, который вызывает UB, если он когда-либо будет выполнен. (Обратите внимание , что функция может не всегда можно назвать, поэтому составители не могут вообще сходить с ума и нарушать другие функции, или даже возможные пути через функции , которые не попали UB. То есть машинный код он компилирует должно работать для все входы, которые не ведут к UB.)

Вероятно, наиболее эффективным решением является очистка вручную последней итерации, чтобы factor*=10избежать ненужного .

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Или, если тело цикла большое, попробуйте просто использовать беззнаковый тип для factor. Затем вы можете позволить многократному переполнению без знака, и он просто выполнит четко определенное перенос до некоторой степени 2 (число битов значения в типе без знака).

Это хорошо, даже если вы используете его со знаковыми типами, особенно если ваше unsigned-> подписанное преобразование никогда не переполняется.

Преобразование между unsigned и дополнением 2 со знаком является бесплатным (один и тот же битовый шаблон для всех значений); Обтекание по модулю для int -> unsigned, определяемое стандартом C ++, упрощает использование только одного и того же битового шаблона, в отличие от дополнения или знака / величины.

И unsigned-> Sign также тривиален, хотя он определяется реализацией для значений, превышающих INT_MAX. Если вы не используете огромный неподписанный результат последней итерации, вам не о чем беспокоиться. Но если да, см. Не определено ли преобразование из неподписанного в подписанное? , Случай «значение не подходит» определяется реализацией , что означает, что реализация должна выбрать какое-то поведение; здравомыслящие просто усекают (если необходимо) битовый шаблон без знака и используют его как подписанный, потому что это работает для значений в диапазоне так же, без дополнительной работы. И это определенно не UB. Таким образом, большие значения без знака могут стать отрицательными знаковыми целыми числами. например, после int x = u; gcc и clang не оптимизироватьx>=0как всегда, правда, даже без -fwrapv, потому что они определили поведение.

Если вы можете допустить несколько дополнительных инструкций по сборке в цикле, вместо

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

ты можешь написать:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

чтобы избежать последнего умножения. !factorне введет ветку:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Этот код

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

также приводит к сборке без ответвлений после оптимизации:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Составлено с GCC 8.3.0 -O3)

Вы не показали, что в скобках forутверждения, но я собираюсь предположить, что это что-то вроде этого:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Вы можете просто переместить инкремент счетчика и проверку завершения цикла в тело:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

Количество инструкций по сборке в цикле останется прежним.

Вдохновленный презентацией Андрея Александреску "Скорость в умах людей".

Рассмотрим функцию:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

Согласно опубликованному Обоснованию, авторы Стандарта ожидали бы, что если бы эта функция была вызвана на (например) обычном 32-битном компьютере с аргументами 0xC000 и 0xC000, продвижение операндов *to signed intприведет к тому, что вычисления приведут к -0x10000000 , который при преобразовании в unsignedдаст 0x90000000u- тот же ответ, как если бы они сделали unsigned shortповышение unsigned. Тем не менее, gcc иногда оптимизирует эту функцию таким образом, чтобы в случае переполнения он вел себя бессмысленно. Любой код, в котором некоторая комбинация входных данных может вызвать переполнение, должен обрабатываться с -fwrapvпараметром, если только было бы неприемлемо позволить создателям намеренно искаженного ввода выполнять произвольный код по своему выбору.

Почему бы не это:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

Есть много разных лиц Неопределенного Поведения, и то, что приемлемо, зависит от использования.

узкая внутренняя петля, которая потребляет большую часть общего процессорного времени в графическом приложении реального времени

Само по себе это немного необычно, но как бы то ни было ... если это действительно так, то UB, скорее всего, находится в пределах "допустимого, приемлемого" . Графическое программирование печально известно из-за хаков и безобразных вещей. Пока он «работает» и на его создание не уходит больше 16,6 мс, обычно это никого не волнует. Но все же, имейте в виду, что значит вызывать UB.

Во-первых, это стандарт. С этой точки зрения, нечего обсуждать, и нет способа оправдать, ваш код просто недействителен. Там нет ни «если», ни «когда», просто это не правильный код. С вашей точки зрения, вы могли бы также сказать, что это средний палец вверх, и в любом случае в 95-99% случаев вам будет хорошо.

Далее есть аппаратная сторона. Есть некоторые необычные, странные архитектуры, где это проблема. Я говорю «необычно, странно», потому что на одной архитектуре, которая составляет 80% всех компьютеров (или на двух архитектурах, которые вместе составляют 95% всех компьютеров), переполнение - это «да, все равно, все равно» вещь на аппаратном уровне. Вы уверены, что получите мусор (хотя все еще предсказуемый) результат, но ничего плохого не происходит.
Это нев случае с любой архитектурой вы вполне можете получить ловушку переполнения (хотя, если посмотреть на то, как вы говорите о графическом приложении, шансы оказаться на такой странной архитектуре довольно малы). Является ли переносимость проблемой? Если это так, вы можете воздержаться.

Наконец, есть сторона компилятора / оптимизатора. Одна из причин, по которой переполнение не определено, заключается в том, что просто оставить его таким, как когда-то, было легче всего справиться с оборудованием. Но другая причина заключается в том , что , например , x+1будет гарантированно всегда быть больше x, и компилятор / оптимизатор может использовать эти знания. Теперь, для ранее упомянутого случая, как известно, компиляторы действительно действуют таким образом и просто удаляют полные блоки (несколько лет назад существовал эксплойт Linux, который был основан на том, что компилятор удалил некоторый код проверки именно из-за этого).
В вашем случае я бы серьезно усомнился в том, что компилятор делает какие-то особые, странные оптимизации. Тем не менее, что вы знаете, что я знаю. Если есть сомнения, попробуйте, Если это работает, вам хорошо идти.

(И, наконец, есть, конечно, аудит кода, вам, возможно, придется потратить время на обсуждение этого вопроса с аудитором, если вам не повезло.)