(А + В + С) ≠ (А + С + В) и компилятор переназначения

Question

Добавление двух 32-битных чисел может привести целое переполнение:

uint64_t u64_z = u32_x + u32_y; 

Это переполнение можно избежать, если один из 32-разрядные целые числа сначала добавляются или добавляются в 64-разрядное целое число.

uint64_t u64_z = u32_x + u64_a + u32_y; 

Однако, если компилятор решает изменить порядок добавления:

uint64_t u64_z = u32_x + u32_y + u64_a; 

целое переполнение еще может произойти.

Могут ли компиляторы разрешить такое переупорядочение или мы можем доверять им, чтобы заметить несоответствие результата и сохранить порядок выражения как есть?

Answer 1

Если Оптимизатор делает такое переназначение он все еще привязан к спецификации C, поэтому такое изменение порядка стало бы:

uint64_t u64_z = (uint64_t)u32_x + (uint64_t)u32_y + u64_a; 

Обоснование:

Мы начинаем с

uint64_t u64_z = u32_x + u64_a + u32_y; 

Дополнение выполняется слева направо.

Целочисленные правила продвижения гласят, что в первом добавлении в исходном выражении u32_x будет переведен в uint64_t. Во втором добавлении, u32_y будет также переведено в uint64_t.

Итак, для того, чтобы быть совместимым со спецификацией C, любой оптимизатор должен продвигать u32_x и u32_y до 64-битных значений без знака. Это эквивалентно добавлению приведения. (Фактическая оптимизация не выполняется на уровне C, но я использую запись C, потому что это обозначение, которое мы понимаем.)

Answer 2

В C, C++ и Objective-C есть правило «как будто»: компилятор может делать все, что угодно, если никакая соответствующая программа не может отличить эту информацию.

В этих языках a + b + c определяется так же, как (a + b) + c. Если вы можете определить разницу между этим и, например, a + (b + c), то компилятор не может изменить порядок. Если вы не можете сказать разницу, то компилятор может свободно изменять порядок, но это нормально, потому что вы не можете отличить эту разницу.

В вашем примере с b = 64 бит, а и c 32 бит компилятору будет разрешено оценивать (b + a) + c или даже (b + c) + a, потому что вы не могли сказать разница, но не (a + c) + b, потому что вы можете сказать разницу.

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

Answer 3

Компилятор допускается только при заказе под кодом , как если бы правил. То есть, если переупорядочение всегда будет давать тот же результат, что и указанный порядок, тогда это разрешено. В противном случае (как в вашем примере), нет.

Например, учитывая следующее выражение

i32big1 - i32big2 + i32small 

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

(i32small - i32big2) + i32big1 

и полагаться на то, что целевая платформа использует два-комплемент арифметику с оберточным раундом, чтобы избежать проблем. (Такое переупорядочение может быть разумным, если компилятор нажат для регистров, и, как оказалось, в регистре уже есть i32small).

Answer 4

Могут ли компиляторы разрешить такое переупорядочение или мы можем доверять им, чтобы заметить несоответствие результата и сохранить порядок выражения как есть?

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

---

Можно написать шаблон функции, если вы хотите один, который продвигает все аргументы std::common_type перед добавлением - это было бы безопасно, а не полагаться на любом порядке аргументов или ручного литья, но это довольно неуклюжим.

Answer 5

Это зависит от ширины бита unsigned/int.

Нижеследующие 2 не то же самое (когда unsigned <= 32 бит). u32_x + u32_y становится 0.

u64_a = 0; u32_x = 1; u32_y = 0xFFFFFFFF; 
uint64_t u64_z = u32_x + u64_a + u32_y; 
uint64_t u64_z = u32_x + u32_y + u64_a; // u32_x + u32_y carry does not add to sum. 

Они же (когда unsigned >= 34 бит). Целочисленные акции вызвали u32_x + u32_y, что произошло в 64-битной математике. Заказ не имеет значения.

Это UB (когда unsigned == 33 бит). Целочисленные акции вызвали добавление к подписанной 33-битной математике, а подписанное переполнение - UB.

Могут ли компиляторы разрешать такое переупорядочение ...?

(32 бита математика): Re заказа да, но такое же результаты должны происходить, так что не что повторный заказ OP предлагает. Ниже одни и те же

// Same 
u32_x + u64_a + u32_y; 
u64_a + u32_x + u32_y; 
u32_x + (uint64_t) u32_y + u64_a; 
... 

// Same as each other below, but not the same as the 3 above. 
uint64_t u64_z = u32_x + u32_y + u64_a; 
uint64_t u64_z = u64_a + (u32_x + u32_y); 

... мы можем доверять им, чтобы заметить результат несогласованности и сохранить порядок экспрессии, как это?

Доверьтесь да, но цель кодирования OP не кристально чиста. Должен ли u32_x + u32_y нести вклад?Если ОП хочет тот вклад, код должен быть

uint64_t u64_z = u64_a + u32_x + u32_y; 
uint64_t u64_z = u32_x + u64_a + u32_y; 
uint64_t u64_z = u32_x + (u32_y + u64_a); 

Но не

uint64_t u64_z = u32_x + u32_y + u64_a; 

Answer 6

Цитирование из standards:

[Примечание: Операторы могут быть перегруппированы в соответствии с обычными математическим правилам только там, где операторы действительно являются ассоциативными или коммутативными.7 Например, в следующем фрагменте int a, b;

/∗ ... ∗/ 
a = a + 32760 + b + 5; 

выражение оператор ведет себя точно так же, как и

a = (((a + 32760) + b) + 5); 

благодаря ассоциативности и приоритете этих операторов. Таким образом, результат суммы (a + 32760) затем добавляется к b, и этот результат равен , а затем добавляется к 5, что приводит к значению, присвоенному a. На машине , в котором переливается произвести исключение, и в котором диапазон значений, изображаемых с помощью Int является [-32768 + 32767], реализация не может переписать это выражение, как

a = ((a + b) + 32765); 

, так как, если значения для a и b были соответственно -32754 и -15, сумма a + b создавала исключение, тогда как исходное выражение не было бы; не может выражение быть переписано либо как

a = ((a + 32765) + b); 

или

a = (a + (b + 32765)); 

, так как значения для а и б, возможно, были, соответственно, 4 и -8 или -17 и 12. Тем не менее на машина, в которой переполнения не производят исключение и в котором результаты переполнения обратимы, выражение выражения выражения выражения может быть переписано реализацией в любым из указанных способов, поскольку тот же результат будет иметь место. - end note]