(A + B + C) ≠ (A + C + B) i zmiana kolejności kompilatora

Dodanie dwóch 32-bitowych liczb całkowitych może spowodować przepełnienie liczb całkowitych:

uint64_t u64_z = u32_x + u32_y;

Tego przepełnienia można uniknąć, jeśli jedna z 32-bitowych liczb całkowitych jest najpierw rzutowana lub dodawana do 64-bitowej liczby całkowitej.

uint64_t u64_z = u32_x + u64_a + u32_y;

Jeśli jednak kompilator zdecyduje się zmienić kolejność dodawania:

uint64_t u64_z = u32_x + u32_y + u64_a;

nadal może wystąpić przepełnienie całkowitoliczbowe.

Czy kompilatorom wolno dokonywać takiej zmiany kolejności, czy też możemy im ufać, że zauważą niespójność wyników i zachowają kolejność wyrażeń bez zmian?

Jeśli optymalizator dokona takiej zmiany kolejności, nadal jest on powiązany ze specyfikacją C, więc taka zmiana kolejności będzie wyglądać następująco:

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

Racjonalne uzasadnienie:

Zaczynamy od

uint64_t u64_z = u32_x + u64_a + u32_y;

Dodawanie odbywa się od lewej do prawej.

Reguły promocji liczb całkowitych określają, że w pierwszym dodatku w oryginalnym wyrażeniu u32_xzostanie podwyższony poziom uint64_t. W drugim dodatku u32_yzostanie również awansowany na uint64_t.

Tak więc, aby uzyskać zgodność ze specyfikacją C, każdy Optimiser musi wspierać u32_xi u32_yna 64-bitowe wartości znaku. Jest to równoważne z dodaniem obsady. (Właściwa optymalizacja nie jest wykonywana na poziomie C, ale używam notacji C, ponieważ jest to notacja, którą rozumiemy).

Kompilator może zmienić kolejność tylko w ramach reguły as if . Oznacza to, że jeśli zmiana kolejności zawsze da ten sam wynik, co określone uporządkowanie, to jest to dozwolone. W przeciwnym razie (jak w twoim przykładzie) nie.

Na przykład, biorąc pod uwagę następujące wyrażenie

i32big1 - i32big2 + i32small

który został starannie skonstruowany, aby odjąć dwie wartości, o których wiadomo, że są duże, ale podobne, a dopiero potem dodać drugą małą wartość (unikając w ten sposób przepełnienia), kompilator może zmienić kolejność na:

(i32small - i32big2) + i32big1

i polegać na fakcie, że platforma docelowa używa arytmetyki z dwoma uzupełnieniami z zawijaniem, aby zapobiec problemom. (Taka zmiana kolejności może być sensowna, jeśli kompilator jest wciśnięty dla rejestrów, a zdarza się, że i32smallma już rejestr).

Istnieje zasada „jak gdyby” w C, C ++ i Objective-C: kompilator może robić, co tylko zechce, o ile żaden zgodny program nie może stwierdzić różnicy.

W tych językach a + b + c oznacza to samo, co (a + b) + c. Jeśli potrafisz odróżnić to od na przykład a + (b + c), wówczas kompilator nie może zmienić kolejności. Jeśli nie możesz odróżnić, kompilator może zmienić kolejność, ale to w porządku, ponieważ nie możesz odróżnić różnicy.

W twoim przykładzie, gdy b = 64 bity, a i c 32 bity, kompilator będzie mógł obliczyć (b + a) + c lub nawet (b + c) + a, ponieważ nie możesz odróżnić różnicy, ale nie (a + c) + b, ponieważ możesz dostrzec różnicę.

Innymi słowy, kompilator nie może zrobić niczego, co spowodowałoby, że kod zachowywałby się inaczej niż powinien. Nie jest wymagane, aby produkować kod, który uważasz, że to produkować, albo że uważasz powinien produkować, ale kod będzie Ci dokładnie te wyniki należy.

Cytując ze standardów :

[Uwaga: Operatory mogą być przegrupowane zgodnie ze zwykłymi regułami matematycznymi tylko wtedy, gdy są one rzeczywiście asocjatywne lub przemienne.7 Na przykład w poniższym fragmencie int a, b;

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

wyrażenie wyrażenie zachowuje się dokładnie tak samo jak

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

ze względu na asocjatywność i pierwszeństwo tych operatorów. W ten sposób wynik sumy (a + 32760) jest następnie dodawany do b, a wynik ten jest następnie dodawany do 5, co daje w wyniku wartość przypisaną do a. Na maszynie, w której przepełnienia powodują wyjątek i w którym zakres wartości reprezentowanych przez int to [-32768, + 32767], implementacja nie może przepisać tego wyrażenia jako

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

ponieważ jeśli wartości a i b wynosiłyby odpowiednio -32754 i -15, suma a + b spowodowałaby wyjątek, podczas gdy pierwotne wyrażenie nie; nie można też przepisać wyrażenia jako

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

lub

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

ponieważ wartości a i b mogły wynosić odpowiednio 4 i -8 lub -17 i 12. Jednak na maszynie, w której przepełnienia nie powodują wyjątku i na której wyniki przepełnienia są odwracalne, powyższa instrukcja wyrażenia może zostać przepisany przez implementację w dowolny z powyższych sposobów, ponieważ wystąpi ten sam wynik. - notatka końcowa]

Czy kompilatorom wolno dokonywać takiej zmiany kolejności, czy też możemy im ufać, że zauważą niespójność wyników i zachowają kolejność wyrażeń bez zmian?

Kompilator może zmienić kolejność tylko wtedy, gdy daje ten sam wynik - tutaj, jak zauważyłeś, nie.

Możliwe jest napisanie szablonu funkcji, jeśli chcesz taki, który promuje wszystkie argumenty std::common_typeprzed dodaniem - byłoby to bezpieczne i nie polegałoby na kolejności argumentów ani ręcznym rzutowaniu, ale jest dość niezgrabne.

To zależy od szerokości bitowej unsigned/int.

Poniższe 2 nie są takie same (gdy unsigned <= 32bity). u32_x + u32_ystaje się 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.

Są takie same (jeśli są unsigned >= 34bitami). Promocje całkowite powodowały u32_x + u32_ydodawanie do 64-bitowej matematyki. Porządek nie ma znaczenia.

To jest UB (gdy unsigned == 33bity). Promocje w postaci liczb całkowitych powodowały dodawanie do 33-bitowej matematyki ze znakiem, a przepełnienie ze znakiem to UB.

Czy kompilatorom wolno dokonywać takiej zmiany kolejności ...?

(32-bitowa matematyka): Ponowna kolejność tak, ale muszą wystąpić te same wyniki, więc nie jest to propozycja ponownego zamówienia OP. Poniżej są takie same

// 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);

... czy możemy im ufać, że zauważą niespójność wyniku i zachowają kolejność wyrażeń bez zmian?

Zaufaj tak, ale cel kodowania OP nie jest krystalicznie jasny. Czy u32_x + u32_ycarry powinno się przyczyniać? Jeśli OP chce tego wkładu, kod powinien być

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);

Ale nie

uint64_t u64_z = u32_x + u32_y + u64_a;