Czy ta optymalizacja zmiennoprzecinkowa jest dozwolona?

90

Próbowałem sprawdzić, gdzie floattraci zdolność do dokładnego reprezentowania dużych liczb całkowitych. Więc napisałem ten mały fragment:

int main() {
    for (int i=0; ; i++) {
        if ((float)i!=i) {
            return i;
        }
    }
}

Ten kod wydaje się działać ze wszystkimi kompilatorami, z wyjątkiem clang. Clang generuje prostą nieskończoną pętlę. Godbolt .

Czy to jest dozwolone? Jeśli tak, czy jest to kwestia QoI?

geza
źródło
@geza Chciałbym usłyszeć wynikową liczbę!
nada
5
gccwykonuje tę samą optymalizację nieskończonych pętli, jeśli -Ofastzamiast tego kompilujesz , więc jest to optymalizacja gccuznawana za niebezpieczną, ale może to zrobić.
12345ieee
3
g ++ również generuje nieskończoną pętlę, ale nie optymalizuje pracy od wewnątrz. Widać, że ucomiss xmm0,xmm0porównuje się (float)ize sobą. To była twoja pierwsza wskazówka, że ​​twoje źródło C ++ nie oznacza tego, co myślisz, że robi. Czy twierdzisz, że masz tę pętlę do wydrukowania / zwrotu 16777216? Z jakim kompilatorem / wersją / opcjami to było? Ponieważ byłby to błąd kompilatora. gcc poprawnie optymalizuje twój kod jnpjako gałąź pętli ( godbolt.org/z/XJYWeu ): kontynuuj pętlę tak długo, jak długo operandy != nie były NaN.
Peter Cordes,
4
W szczególności jest to -ffast-mathopcja, która jest domyślnie włączona przez, -Ofastktóra pozwala GCC na stosowanie niebezpiecznych optymalizacji zmiennoprzecinkowych, a tym samym generowanie tego samego kodu co Clang. MSVC zachowuje się dokładnie w ten sam sposób: bez /fp:fastniego generuje zbiór kodu, który skutkuje nieskończoną pętlą; z /fp:fast, wysyła pojedynczą jmpinstrukcję. Zakładam, że bez jawnego włączenia niebezpiecznych optymalizacji FP te kompilatory rozłączają się z wymaganiami IEEE 754 dotyczącymi wartości NaN. Raczej interesujące, że Clang nie. Jego analizator statyczny jest lepszy. @ 12345ieee
Cody Gray
1
@geza: Jeśli kod zrobił to, co zamierzałeś, sprawdzając, kiedy wartość matematyczna (float) iróżni się od wartości matematycznej i, to wynik (wartość zwrócona w returninstrukcji) będzie wynosił 16 777 217, a nie 16 777 216.
Eric Postpischil

Odpowiedzi:

49

Jak zauważył @Angew , !=operator potrzebuje tego samego typu po obu stronach. (float)i != iskutkuje również promocją RHS do float, więc mamy (float)i != (float)i.


g ++ również generuje nieskończoną pętlę, ale nie optymalizuje pracy od wewnątrz. Możesz zobaczyć, że konwertuje int-> float zi cvtsi2ssrobi, ucomiss xmm0,xmm0aby porównać (float)ize sobą. (To była twoja pierwsza wskazówka, że ​​twoje źródło C ++ nie oznacza tego, co myślisz, że podobało się odpowiedź @ Angew.)

x != xjest prawdziwy tylko wtedy, gdy jest „nieuporządkowany”, ponieważ xbył NaN. ( INFINITYporównuje równe sobie w matematyce IEEE, ale NaN nie. NAN == NANjest fałszem, NAN != NANjest prawdą).

gcc7.4 i starsze poprawnie optymalizują twój kod jnpjako gałąź pętli ( https://godbolt.org/z/fyOhW1 ): zachowaj pętlę tak długo, jak długo operandy x != x nie były NaN. (gcc8 i późniejsze również sprawdzają je, czy nie doszło do wyrwania się z pętli, nie optymalizując na podstawie faktu, że zawsze będzie to prawda dla każdego wejścia innego niż NaN). x86 FP porównuje ustawione PF na nieuporządkowanym.


A tak przy okazji, oznacza to, że optymalizacja clang jest również bezpieczna : po prostu musi CSE (float)i != (implicit conversion to float)ibyć taka sama i udowodnić, że i -> floatnigdy nie jest NaN dla możliwego zakresu int.

(Chociaż biorąc pod uwagę, że ta pętla uderzy w UB przepełnienia ze znakiem, może wyemitować dosłownie każdy asm, którego chce, w tym ud2niedozwoloną instrukcję lub pustą nieskończoną pętlę, niezależnie od tego, czym faktycznie była treść pętli.) Ale ignorowanie UB przepełnienia ze znakiem , ta optymalizacja jest nadal w 100% legalna.


GCC nie udaje się zoptymalizować treści pętli, nawet jeśli -fwrapvprzepełnienie liczb całkowitych ze znakiem jest dobrze zdefiniowane (jako zawijanie dopełniacza 2). https://godbolt.org/z/t9A8t_

Nawet włączenie -fno-trapping-mathnie pomaga. (Domyślnym ustawieniem GCC jest niestety włączenie,
-ftrapping-mathmimo że jego implementacja w GCC jest zepsuta / błędna). Konwersja int-> float może spowodować niedokładny wyjątek FP (dla liczb zbyt dużych, aby były dokładnie reprezentowane), więc w przypadku wyjątków, które mogą zostać zdemaskowane, rozsądne jest nie zoptymalizować korpus pętli. (Ponieważ konwersja 16777217do typu float może mieć obserwowalny efekt uboczny, jeśli niedokładny wyjątek zostanie zdemaskowany).

Ale w przypadku -O3 -fwrapv -fno-trapping-math100% pominiętej optymalizacji nie kompilowanie tego do pustej nieskończonej pętli. Bez #pragma STDC FENV_ACCESS ONstanu lepkich flag, które rejestrują zamaskowane wyjątki FP, nie można zaobserwować efektu ubocznego kodu. Nie int-> floatkonwersja może skutkować NaN, więc x != xnie może być prawdą.


Wszystkie te kompilatory optymalizują pod kątem implementacji C ++, które używają pojedynczej precyzji IEEE 754 (binary32) floati 32-bitowej int.

Bugfixed(int)(float)i != i pętla musiałaby UB na implementacje C ++ z wąskiej 16-bitowej inti / lub szerszy float, ponieważ chcesz trafić podpisał liczbą całkowitą przepełnienie przed UB osiągnięciu pierwszego liczbę całkowitą, która nie była dokładnie przedstawianego jako float.

Ale UB w ramach innego zestawu wyborów zdefiniowanych w ramach implementacji nie ma żadnych negatywnych konsekwencji podczas kompilacji dla implementacji takiej jak gcc lub clang z x86-64 System V ABI.


Przy okazji, możesz statycznie obliczyć wynik tej pętli z FLT_RADIXi FLT_MANT_DIG, zdefiniowane w <climits>. A przynajmniej możesz w teorii, jeśli floatfaktycznie pasuje do modelu IEEE float, a nie innego rodzaju reprezentacji liczb rzeczywistych, takich jak Posit / unum.

Nie jestem pewien, jak bardzo standard ISO C ++ wpływa na floatzachowanie i czy format, który nie był oparty na wykładniku o stałej szerokości i polach istotności, byłby zgodny ze standardami.


W komentarzach:

@geza Chciałbym usłyszeć wynikową liczbę!

@nada: to 16777216

Czy twierdzisz, że masz tę pętlę do wydrukowania / zwrotu 16777216?

Aktualizacja: ponieważ ten komentarz został usunięty, myślę, że nie. Prawdopodobnie OP po prostu cytuje floatprzed pierwszą liczbą całkowitą, której nie można dokładnie przedstawić jako 32-bitowej float. https://en.wikipedia.org/wiki/Single-precision_floating-point_format#Precision_limits_on_integer_values, czyli to, co chcieli zweryfikować za pomocą tego błędnego kodu.

Wersja z naprawionymi błędami oczywiście wypisuje 16777217pierwszą liczbę całkowitą, której nie można dokładnie przedstawić, zamiast wartości poprzedzającej.

(Wszystkie wyższe wartości zmiennoprzecinkowe są dokładnymi liczbami całkowitymi, ale są to wielokrotności 2, następnie 4, następnie 8 itd. Dla wartości wykładników wyższych niż szerokość istotności. Można przedstawić wiele wyższych wartości całkowitych, ale 1 jednostka na ostatnim miejscu (znaczenia) jest większe niż 1, więc nie są one ciągłymi liczbami całkowitymi. Największa liczba skończona floatma nieco mniej niż 2 ^ 128, co jest zbyt duże, aby było parzyste int64_t).

Gdyby jakiś kompilator zakończył oryginalną pętlę i wydrukował to, byłby to błąd kompilatora.

Peter Cordes
źródło
3
@SombreroChicken: nie, najpierw nauczyłem się elektroniki (z niektórych podręczników, które mój tata leżał; był profesorem fizyki), potem logiki cyfrowej, a potem zająłem się procesorami / oprogramowaniem. : P Tak więc prawie zawsze lubiłem rozumieć rzeczy od podstaw, lub jeśli zaczynam od wyższego poziomu, to lubię dowiedzieć się przynajmniej czegoś o niższym poziomie, który wpływa na to, jak / dlaczego wszystko działa na poziomie, na którym myśląc o. (np. jak działa asm i jak go zoptymalizować zależy od ograniczeń projektowych procesora / elementów architektury procesora. Co z kolei pochodzi z fizyki + matematyki).
Peter Cordes
1
GCC może nie być w stanie zoptymalizować nawet z frapw, ale jestem pewien, że GCC 10 -ffinite-loopszostało zaprojektowane do takich sytuacji.
MCCCS
64

Zwróć uwagę, że operator wbudowany !=wymaga , aby jego operandy były tego samego typu i w razie potrzeby osiągnie to za pomocą promocji i konwersji. Innymi słowy, twój stan jest równoważny z:

(float)i != (float)i

To nigdy nie powinno zawieść, więc kod w końcu się przepełni i, powodując niezdefiniowane zachowanie programu. Dlatego możliwe jest każde zachowanie.

Aby poprawnie sprawdzić, co chcesz sprawdzić, prześlij wynik z powrotem do int:

if ((int)(float)i != i)
Angew nie jest już dumny z SO
źródło
8
@ Džuris To UB. Nie ma nikt określony wynik. Kompilator może zdać sobie sprawę, że może zakończyć się tylko na UB i zdecydować o całkowitym usunięciu pętli.
Załóż pozew Moniki,
4
@opa masz na myśli static_cast<int>(static_cast<float>(i))? reinterpret_castjest tam oczywiste UB
Caleth
6
@NicHartley: Mówisz, że (int)(float)i != ito UB? Jak to podsumowujesz? Tak, zależy to od właściwości zdefiniowanych w implementacji (ponieważ floatnie jest wymagane, aby być IEEE754 binary32), ale w każdej implementacji jest dobrze zdefiniowane, chyba że floatmoże dokładnie reprezentować wszystkie pozytywneint wartości , więc otrzymujemy przepełnienie UB ze całkowitym. ( en.cppreference.com/w/cpp/types/climits definiuje FLT_RADIXi FLT_MANT_DIGokreśla to). Ogólnie rzecz biorąc, rzeczy zdefiniowane w druku, jak std::cout << sizeof(int)nie jest UB ...
Peter Cordes,
2
@Caleth: reinterpret_cast<int>(float)nie jest dokładnie UB, to tylko błąd składni / źle sformułowany. Byłoby miło, gdyby ta składnia pozwalała na przebijanie typu float intjako alternatywa dla memcpy(co jest dobrze zdefiniowane), ale reinterpret_cast<>myślę, że działa tylko na typach wskaźników.
Peter Cordes,
2
@Peter Tylko dla NaN, x != xjest prawdą. Zobacz na żywo na coliru . W C też.
Deduplicator