Kompilátory jsou příliš chytré

21.6.2010 11:00 | Přečteno: 3338× | Programování |

Optimalizace, které umí dnešní kompilátory, jsou občas k neuvěření. Stále častěji se setkávám s případy, kdy mi právě optimalizace pořádně lezou na nervy. Pak o tom zpravidla napíšu vzteklý blogpost. Následující triviální příklad mi připadá celkem zajímavý. Někdo se mi vysměje, že se tak samozřejmé záležitosti divím. Pro někoho to naopak bude přínosné varování.

Dejme tomu, že vytvořím následující prasečí kód. Připusťme dále, že jsem naivní trouba, který si myslí, že takový kód vypíše 255 z.

#include <stdio.h>

int main() {
        char c = 0;
        while (++c) putchar('z');
}

Tak jo, první pokus...

$ gcc -O3 -march=native -S -o overflow1.s overflow.c

Nuže, podívejme se na while cyklus:

.L2:
        movq    stdout(%rip), %rsi
        movl    $122, %edi
        call    _IO_putc
        jmp     .L2

Není těch z nějak moc??? Manuálová stránka GCC otázky kolem overflow vysvětluje velmi jasně — nezbude, než se z ní poučit a zkusit to jinak:

$ gcc -O3 -fno-strict-overflow -march=native -S -o overflow2.s overflow.c

.L2:
        movq    stdout(%rip), %rsi
        movl    $122, %edi
        call    _IO_putc
        decb    %bl
        jne     .L2

Teprve teď to bude fungovat tak, jak bylo původně zamýšleno.

Přetečení v této podobě je bezesporu prasárna, jakou by nikdo neměl zkoušet. Faktem ale zůstává, že ve spoustě algoritmů z oblasti algebry se s přetečením počítá a v takovém případě optimalizace dovede světa neznalému programátorovi pořádně vypálit rybník.

       

Komentáře

[mektige]

Překladače umí překvapit... Tady je pěkná prezentace s příklady jejich chytristik: http://dl.fefe.de/optimizer-isec.pdf

[trekker.dk]

gcc pro AVR umí taky pěkný věci. Onehdá jsem jenom nevěřícně koukal na kód, kterej vypadal nějak takhle:

add r18, r18
add r18, r18
mov r19, r18
add r18, r18
add r19, r18
add r19, r18
; ... zde instrukce, které výsledek přičtou k indexovacímu registru

Kdyby někoho zajímalo, co to je, tak tenhle kód provádí násobení 20 (za předpokladu, že výsledek nebude větší než 255). Tedy něco, co se efektivněji udělá kódem:

ldi r19, 20
mul r18, r19 ; 2 tiky
; ... zde instrukce, které výsledek přičtou k indexovacímu registru
eor r1, r1

Samotné násobení tedy překladač vyrobí o polovinu delší, než by stačilo. A viděl jsem i "zajímavější" věci, které dokázal překladač vymyslet...

[Actuator]

A není to první řešení náhodou rychlejší?

[Actuator]

Ééé jsem slepej, 2 tiky, už vidím ...

[Vskutečnosti Saýc]

A urcite netrva mul dele? Na AVR na kterem jsme pracovali ve skole trval snad 18 taktu, ale byla to nejaka divna varianta.

[stativ]

Tak tak, většině procesorů násobení trvá docela dlouho, extrém je x86, kde to trvá klidně 80 taktů. Co jsem ve škole pracovali s nějakým Hitachi tak tam to trvalo asi 20 taktů. Rozhodně by se ale to násobení dalo napsat efektivněji pomocí bitových posunů (např. jeden registr posunout o 4 bity doleva, jeden o 1 bit a sečíst.).

[trekker.dk]

Rozhodně by se ale to násobení dalo napsat efektivněji pomocí bitových posunů (např. jeden registr posunout o 4 bity doleva, jeden o 1 bit a sečíst.)

Pokud dobře počítám, tak tohle by násobilo 18. A bitový posun trvá stejně dlouho jako add, takže výsledek by byl stejný s tím, co vyrobí překladač.

[stativ]

Pokud dobře počítám, tak tohle by násobilo 18.

Máš pravdu, nějak jsem se nedopočítal.

A bitový posun trvá stejně dlouho jako add, takže výsledek by byl stejný s tím, co vyrobí překladač.

Určitě? Tohle jsou 3 instrukce + mov, kdežto v tom ukázkovém kódu jich vidím 5 + mov.

[trekker.dk]

Určitě? Tohle jsou 3 instrukce + mov

AVR umí posun jenom o jednu pozici.

[stativ]

Aha, to jsem nevěděl.

[trekker.dk]

18 taktů? Jsi si jistý, že to bylo AVR (ne AVR32)? Nejdelší instrukce, které má AVR, trvají 4 tiky (volání a návrat z podprogramů, návrat z přerušení); mul má určitě 2.

[Josef Kufner]

A nemohlo to být třeba kvůli tomu, že těsně předtím tam bylo ještě jiné násobení a pipeline by musela čekat než se uvolní násobička?

[trekker.dk]

AVR

[Josef Kufner]

Neíkej, že by tak krásný procesor neměl pipeline...

[trekker.dk]

Nemá, v tomhle smyslu dělá akorát to, že při zpracovávání jedné instrukce přednačítá další z programové paměti.

[Josef Kufner]

Aha, tak to pak jo.

[trekker.dk]

Tak jenom pro úplnost (koukl jsem se do poznámek): ten kód nahoře se ve skutečnosti počítá v 16 bitech, takže těch instrukcí pro sčítání je 12 , kdežto kód s násobičkou se v podstatě nemění

Další pěkné případy dělají tohle

C kód:

unsigned char *j;
unsigned char a;

j = sdev->out_hlavicka; /* out_hlavicka je char[3] */
for (a = 3; a; a--) 
    *(j++) = b;

Očekával bych kód

adiw r26, 0x15 ; indexovací registr ukazující na začátek struct sdev
               ; se posune na prvek out_hlavicka
st X+, r18     ; hodnota v r18 se zkopíruje do tří po sobě 
st X+, r18     ; jdoucích pozic
st X+, r18

Ve skutečnosti ovšem překladač vyplodí toto:

adiw r26, 0x15 ; posun indexovacího registru
st X, r18
sbiw r26, 0x15 ; návrat na začátek struktury
adiw r26, 0x16 ; abychom se hned vrátili zpátky o byte dál
st X, r18
sbiw r26, 0x16
adiw r26, 0x17
st X, r18

adiw i sbiw jsou dvoutikové, takže osm tiků zbytečně navíc

No a nejhezčí na konec - kód, který kopíruje jeden buffer v paměti jinam:

movw r30, r10 ; r10:r11 obsahuje adresu bufferu, ze kterého se kopíruje,
              ; nahraje se do r30:r31
ld r24, Z+    ; Z je r30:r31, inkrementuje se
movw r10, r30 ; nové Z se uloží zpět do r10:r11
movw r30, r12 ; totéž pro cílovou adresu uloženou v r12:r13
st Z+, r24    ; kam se hodnota v r24 uloží
movw r12, r30 ; a nový ukazatel se vrátí do r12:r13
subi r16, 0x01 ; dekrementace počítadla a skok, pokud
sbci r17, 0x00 ; není nulové
brne .-22

Správný postup je tohle:

   mov ZL, r10 ; jeden ukazatel do Z
   mov XL, r12 ; druhý ukazatel do X
1: ld r24, Z+
   st X+, r24
   subi r16, 0x01
   sbci r17, 0x00
   brne 1b

movw je taky dvoutiková, takže překladač každý průchod cyklem prodlužuje o osm tiků a zdvojnásobuje tak dobu, za jakou se cyklus vykoná.

Zkrátka a dobře překladači se tady nedá věřit, přičemž o verzi 4 gcc to platí víc než o verzi 3.

[Sinuhet]

Nepocita se v tech alogritmech z algebry s pretecenim bezznamenkovych cisel?

[Let_Me_Be]

Presne tak, znamenkove preteceni neni garantovane (preteceni vede k nedefinovanemu stavu), neznamenkove ano.

Holt to chce proste znat standard.

[Grunt]

Nechápu. Na tom by mělo být něco divného?

[Let_Me_Be]

Ono je ted strasne moderni delat ze sebe blbce pres blog. Ja kdyz jsem narazil na podobnou vec, kterou jsem neznal tak jsem se s tim maximalne pobavil se zkusenejsim kamaradem, ktery mi rekl ze jsem kreten a ze si mam precist standard.

[Grunt]

Nač standard? Bohatě stačí i manuálová stránka.

-fstrict-overflow

Allow the compiler to assume strict signed overflow rules, depending on the language being compiled. For C (and C++) this means that overflow when doing arithmetic with signed numbers is undefined, which means that the compiler may assume that it will not happen. This permits various optimizations. For example, the compiler will assume that an expression like "i + 10 > i" will always be true for signed "i". This assumption is only valid if signed overflow is undefined, as the expression is false if "i + 10" overflows when using twos complement arithmetic. When this option is in effect any attempt to determine whether an operation on signed numbers will overflow must be written carefully to not actually involve overflow.

This option also allows the compiler to assume strict pointer semantics: given a pointer to an object, if adding an offset to that pointer does not produce a pointer to the same object, the addition is undefined. This permits the compiler to conclude that "p + u > p" is always true for a pointer "p" and unsigned integer "u". This assumption is only valid because pointer wraparound is undefined, as the expression is false if "p + u" overflows using twos complement arithmetic.

See also the -fwrapv option. Using -fwrapv means that integer signed overflow is fully defined: it wraps. When -fwrapv is used, there is no difference between -fstrict-overflow and -fno-strict-overflow for integers. With -fwrapv certain types of overflow are permitted. For example, if the compiler gets an overflow when doing arithmetic on constants, the overflowed value can still be used with -fwrapv, but not otherwise.

The -fstrict-overflow option is enabled at levels -O2, -O3, -Os.

Jestli je to i ve standardu, tak jen o to víc.

[Andrej]

A právě o manuálové stránce jsem se v zápisu zmínil. Je na tom něco špatně?

[deda.jabko]

Ono je ted strasne moderni delat ze sebe blbce pres blog.

takze ten kdo nezna specifikaci do detailu je blbec. jinak clanek jako upozorneni na (neobvyklou) chybu, kterou muze udelat kazdy, je imho dobry napad.

Ja kdyz jsem narazil na podobnou vec, kterou jsem neznal tak jsem se s tim maximalne pobavil se zkusenejsim kamaradem, ktery mi rekl ze jsem kreten a ze si mam precist standard.

mas zvlastni kamarady.

[Sinuhet]

Kdyby kolega napsal, ze to byla jeho chyba zpusobena neznalosti standardu, tak je to v poradku. Bohuzel on ten incident podava tak, ze za to muzou kompilatory a jejich optimalizace.

[Marek Bernát]

Ťažko to mohol napísať, ak o tom nevedel. Za druhé, treba si z blogu zobrať podstatu a nebazírovať na názoroch autora, tie nie sú až tak dôležité a môžu sa deň odo dňa zmeniť (v princípe). Navyše tu vznikla celkom zaujímavá diskusia o nejakom procesore, ktorý som dodnes nepoznal. Takže blog má u mňa palec hore.

[Sinuhet]

V tomto vlakne se bavime o tom, dela-li ze sebe kolega Andrej blbce, takze je nutne "bazirovat" na nazorech autora. Kdyby blog upozornoval na to, ze znamenkove preteceni je nedefinovane chovani, tak by to bylo v poradku. Jenze on ten text vyzniva tak, ze je to sice trochu prasarnicka, ale jinak je kod v poradku a chyba je v optimalizujicich kompilatorech.

[Marek Bernát]

Ešte raz: ak o tom nevedel, ťažko to mohol písať tak, ako to chcete. Písal to tak, ako si myslel, že to je. Súhlasím, že si mal o tom niečo viac zistiť, kým napísal blog. Ale určite by som ho kvôli tomu neoznačoval za blbca.

[Let_Me_Be]

Osobne si myslim ze mezi vyrazy "XY ze sebe dela blbce" a "XY je blbec" je vyrazny semanticky rozdil. Navic tohle je tak desne proflaknuta vec (google rad poradi).

[Marek Bernát]

Mno neviem, pre mňa sú tie výrazy skoro ekvivalentné. Ničmenej, ak ti dobre rozumiem, tak pre teba výraz "dělat ze sebe blbce" je práve to, čo spravil Andrej (tj. drobná chyba z neznalosti). To potom ok, s tým nemám problém.

Že je to prefláknuté je irelevantné. Buď o tom vieš, alebo nie

[Andrej]

Abych řekl pravdu, křiklouny typu „přečti si standard a nepruď“ jsem více méně čekal. Přesto si dovolím doplnit několik poznámek:

1. Kolik uživatelů kompilátoru C má prostudovaný standard? Kdyby ho znali všichni, nemusel bych o tomto psát, že ano.
2. K tomuto příspěvku a k některým příspěvkům níže bych asi přidal řečnickou otázku: Kde tvrdím, že ten kód je v pořádku? V mém blogpostu to nevidím.
3. I kdyby byl tentýž kód založený na bezznaménkovém přetečení, které se přeloží správně, stále bych ho neoznačil (z hlediska čitelnosti) za „v pořádku“.
4. Kód nevznikl tak, že bych něco takového sám od sebe vytvořil a pak se divil. Zkoušel jsem cca třicet různých cyklů (ne vždy v souladu se standardem) a zajímalo mě, jak si GCC poradí například
   • s alokací registrů a s paměťovými referencemi na proměnné (lokální, globální, globální static, členy struktur, volatile, ...).
   • s optimalizací přístupu k proměnným a s přeuspořádáním instrukcí přes volání funkcí (lokálních, dobře známých (putchar()) či neznámých (z dynamických knihoven)).
   Některé výsledky mě překvapily, jiné jsem očekával. Každopádně se vsadím, že mnozí z těch, kteří tu předvádějí bohatýrské řeči ve stylu „jo, hochu, kdybys tak znal standard...“, by asi taktéž ve spoustě situací neměli příliš jasno.
5. Cílem blogpostu je upozornit na jednu z rizikových situací, kdy kompilace dopadne při -O0 a -O1 jinak než při -O2 a -O3. Není to chyba kompilátoru (nestandardní kód -> nedefinovaný výsledek), ale zas tak samozřejmé mi to nepřipadá.
6. Že je celá situace popsaná v manuálové stránce, to můj blogpost říká zcela výslovně. Nevím, proč si někdo myslí, že tuto záležitost považuji za bug v kompilátoru nebo co.

A vůbec, chce to klid. Nebo rovnou -Wstrict-overflow.

[R]

-Wstrict-overflow nefunguje (GCC 4.4.4)

[Andrej]

Nefunguje? Co tím chtěl básník říci?

$ gcc -O3 -Wstrict-overflow -march=native -S -o overflow.s overflow.c
overflow.c: In function ‘main’:
overflow.c:5:8: warning: assuming signed overflow does not occur when simplifying conditional to constant

Třeba je to verzí GCC, co já vím...

$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-unknown-linux-gnu/4.5.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ../configure --prefix=/usr --enable-languages=c,c++,fortran,objc,obj-c++,ada --enable-shared --enable-threads=posix --enable-__cxa_atexit --enable-clocale=gnu --enable-gnu-unique-object --enable-lto --enable-plugin --disable-multilib --disable-libstdcxx-pch --with-system-zlib --with-ppl --with-cloog --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info
Thread model: posix
gcc version 4.5.0 20100520 (prerelease) (GCC)

[R]

$ gcc -O3 -Wstrict-overflow -march=native -S -o overflow.s overflow.c
$

$ gcc -v
Reading specs from /usr/lib/gcc/i486-slackware-linux/4.4.4/specs
Target: i486-slackware-linux
Configured with: ../gcc-4.4.4/configure --prefix=/usr --libdir=/usr/lib --enable-shared --enable-bootstrap --enable-languages=ada,c,c++,fortran,java,objc --enable-threads=posix --enable-checking=release --with-system-zlib --with-python-dir=/lib/python2.6/site-packages --disable-libunwind-exceptions --enable-__cxa_atexit --enable-libssp --with-gnu-ld --verbose --with-arch=i486 --target=i486-slackware-linux --build=i486-slackware-linux --host=i486-slackware-linux
Thread model: posix
gcc version 4.4.4 (GCC)

[Andrej]

Tak buď ve starší verzi příslušné varování chybí, nebo starší verze tu optimalizaci nepoužila a nebylo tedy před čím varovat.

[Let_Me_Be]

RTFM: "This option is only active when -fstrict-overflow is active"

[Andrej]

RTFM: "The -fstrict-overflow option is enabled at levels -O2, -O3, -Os."

[Martin Doucha]

Že je celá situace popsaná v manuálové stránce, to můj blogpost říká zcela výslovně. Nevím, proč si někdo myslí, že tuto záležitost považuji za bug v kompilátoru nebo co.

Protože tak vyznívá název článku a ten více méně definuje kontext pro celý zbytek textu, například hranici mezi sarkasmem a vážně myšleným textem.

[Marek Bernát]

+1, chcel som napísať niečo v podobnom duchu.

[hajma]

Sun Studio to zkompiluje korektne

[Let_Me_Be]

Vsechny kompilatory (i to co to nezkompiluji) to kompiluji korektne. Protoze korektne v tomto pripade = libovolne.

[JS]

Mozna se pletu, ale u -O3 je napsano, ze zapina optimalizace, ktere mohou za jistych okolnosti menit semantiku kodu. To si staci pamatovat a je to v pohode.

[Andrej]

V tomto konkrétním případě to pro -O2 dopadne stejně, takže tentokrát problém není v -O3. Problém je v tom, že ten kód není korektní (jak už se někteří místní experti nechali slyšet) a výsledek tedy není jasně definovaný.