(A + B + C) ≠ (A + C + B) и переупорядочение компилятора

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

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

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

i32big1 - i32big2 + i32small

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

(i32small - i32big2) + i32big1

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

Answer 3

Существует правило "как будто" в C, C++ и Objective-C: компилятор может делать все, что ему нравится, до тех пор, пока никакая соответствующая программа не сможет определить разницу.

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

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

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

Answer 4

Цитирование из стандартов:

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

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

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

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

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

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

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

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

или же

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

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

Answer 5

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

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

---

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

Answer 6

Это зависит от ширины бита 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-битная математика): Переупорядочить да, но должны быть получены те же результаты, так что переупорядочение 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;