Ceckarsky kviz III

Neděle Červen 7 12:36:30 CEST 2009

>Byl by az takovy problem sem hodit i vysledek prekladu? (ASM listing)
>To by mohlo dost osvetlit:)

Trocha som ten zdrojak poupravil, aby to bolo procesorovo nezavisle - ide len o nahradu zmeny pinu portu prostym zapisom do volatile bytu (co kompilator nesmie vyoptimalizovat podobne ako to menenie hodnoty portu):

volatile unsigned char p;

int main(void) {
  int i = 0;

  while (1) {
    if (i & 0x8000) {
      p = 0;
    } else {
      p = 1;
    }
    i++;
  }
}

Preklad s prepinacom -O0, t.j. bez optimalizacie (moje komentare v []):

  11               	main:
  12 0000 DF93      		push r29
  13 0002 CF93      		push r28              [tymto sa v stacku ulozi hodnota pointra Y (*)]
  14 0004 00D0      		rcall .               [finta: tymto sa v stacku urobi miesto 2 byte pre lokalnu premennu i]
  15 0006 CDB7      		in r28,__SP_L__
  16 0008 DEB7      		in r29,__SP_H__       [a tymto sa nastavi Y, aby ukazoval na miesto v stacku vymedzene pre lokalne premenne]
  19 000a 1A82      		std Y+2,__zero_reg__
  20 000c 1982      		std Y+1,__zero_reg__  [takto sa vynuluje i]
  21               	.L4:                          [toto je while(1)]
  22 000e 8981      		ldd r24,Y+1
  23 0010 9A81      		ldd r25,Y+2           [poctivo sa nacita i do registrov]
  24 0012 9923      		tst r25               
  25 0014 04F4      		brge .L2              [toto je test na najvyssi bit r25]
  26 0016 1092 0000 		sts p,__zero_reg__
  27 001a 00C0      		rjmp .L3
  28               	.L2:
  29 001c 81E0      		ldi r24,lo8(1)
  30 001e 8093 0000 		sts p,r24
  31               	.L3:
  32 0022 8981      		ldd r24,Y+1           [znova sa poctivo nacita i -- nezabudnite, je to brutalne neoptimalizovany kod]
  33 0024 9A81      		ldd r25,Y+2
  34 0026 0196      		adiw r24,1            [pricita sa 1 k celemu registrovemu paru]
  35 0028 9A83      		std Y+2,r25
  36 002a 8983      		std Y+1,r24           [i sa ulozi spat]
  37 002c 00C0      		rjmp .L4              [no a toto je koniec while(1)]

(*) Dohoda (tzv. ABI) v avr-gcc je, ze vsetky funkcie su povinne uchovat stav niektorych registrov, a registrova dvojica r28:r29, ktora tvori pointer Y, je medzi nimi. main() sa poklada za funkciu ako akakolvek ina; toto spravanie sa da ciastocne potlacit vhodnymi prepinacmi, ale nechce sa mi ich teraz skumat.

Preklad s prepinacom -O1, t.j. s miernou optimalizaciou:
  11               	main:
  14 0000 80E0      		ldi r24,lo8(0)        [uz sa nerobi miesto v stacku, i sa drzi cely cas v registroch]
  15 0002 90E0      		ldi r25,hi8(0)
  16 0004 21E0      		ldi r18,lo8(1)        [toto je zaujimava optimalizacia, konstanta pre ulozenie do p sa nastavi do registra pred cyklom]
  17               	.L4:                          [while(1)]
  18 0006 9923      		tst r25
  19 0008 04F4      		brge .L2              [robi sa v podstate ten isty test na najvysii bit ako v predoslom]
  20 000a 1092 0000 		sts p,__zero_reg__
  21 000e 00C0      		rjmp .L3
  22               	.L2:
  23 0010 2093 0000 		sts p,r18
  24               	.L3:
  25 0014 0196      		adiw r24,1            [a takisto sa pricita 1, akurat sa uz necita/nezapisuje do RAM]
  26 0016 00C0      		rjmp .L4              [koniec while(1)]

Preklad s prepinacom -O2, -O3 a -Os (to posledne je optimalizacia na rychlost) dopadne rovnako:
  11               	main:
  14 0000 81E0      		ldi r24,lo8(1)        [toto je ta optimalizacia, ze sa konstanta nastavi do registra pred cyklom]
  15               	.L2:                          [while(1)]
  16 0002 8093 0000 		sts p,r24             [p je volatile, takze sa do neho musi vzdy zapisovat]
  17 0006 00C0      		rjmp .L2              [konice while(1)]

Podotykam, ze takto sa sprava len novsia verzia avr-gcc (pouzil som v4.3.2, distribuovanu s WinAVR20090313). Starsia v4.2.2 tuto optimalizaciu neurobi, aj s -Os je vysledok podobny tomu, co je v novsej verzii s -O1.

Pred vysvetlenim vsak najprv mala odbocka:
> Lepe receno, asi mam moc velkou fantazii, ale predstavuji si ty optimalizace takto:
> a) orezani konstanty 0x8000 podle datoveho typu, vysledek bude 0. (Tady by to asi melo hlasit nejakou chybu).

No, praveze toto sa nikdy nestane. Dovod spociva ciastocne v tom, co bolo diskutovane v "Ceckarskom kvize II" (http://list.hw.cz/pipermail/hw-list/2009-March/138851.html): norma (v kap. 6.3) pomerne rozsiahlo popisuje implicitne konverzie, ktore sa robia, ked sa stretnu vo vyraze premenne rozneho typu. 
Nespecifikuje sa sice explicitne, aky typ ma byt 0x8000, ale v norme je pomerne rozsiahlo rozvedene, ako sa urci typ celociselnej konstanty (kap. 6.4.4.1) - 
ide sa po tabulke, a najmensi typ, do ktoreho konstanta vojde, sa pouzije - pre konstantu zapisanu ako hexadecimalne cislo bez suffixu (U, L) je to najprv 
int, to je tu int16_t, to nestaci; dalsi je unsigned int, to je uint16_t, to staci, tak to sa pouzije - t.j. konstanta 0x8000 je typu uint16_t. Dalej norma 
predpisuje, ze ak sa stretne int a uint, tak uint sa konvertuje na int len ak sa tym zachovaju vsetky mozne hodnoty (co u uint16_t -> int16_t zjavne 
neplati); inak sa konvertuje na uint. Inaksie povedane, vo vyraze z povodneho programu (i & 0x8000) sa neoreze 0x8000, ale naopak, i sa konvertuje na 
neznamienkove (pod tou konverziou si treba predstavit to, ze sa v skutocnosti nic neurobi, takze zo znamienkoveho 0x8000=-32768 vznikne neznamienkove 
0x8000=32768). Mozete si to vyskusat napriklad tak, ze si nastavite i na nejake zaporne cislo - potom ta podmienka bude mat vysledok TRUE (!=0) aj v 
optimalizovanej verzii (kdezto keby sa konstanta orezala, podmienka by VZDY dopadla FALSE (==0), a to aj v neoptimalizovanej verzii).

Problem teda nie je v tom, zeby sa konstanta 0x8000 orezala.

Problem je v tom, ze ak int i=0x7FFF a urobi sa i++, vysledok je pretecenim v danom type. A podla normy, nasledok pretecenia je NEDEFINOVANY. Inaksie 
povedane, pri preteceni moze i zostat 0x7FFF, moze byt 0x8000, moze byt 0, a moze sa dokonca aj vyvolat runtime error (exception), aj ked to je u C nezvykle.

Vysledok prekladu je teda spravny v obidvoch pripadoch: prekladac ma uplnu volnost v interpretacii toho pretecenia.

Pri -O0 a -O1 prekladac predpoklada, ze pri preteceni moze byt vysledok 0x8000, t.j. 32767 + 1 = -32768.
No a pri -Os prekladac predpoklada, ze pri preteceni moze byt vysledok akykolvek kladny, napr. 32767 + 1 = 32767. To umozni odstranit test v cykle - i predsa 
zostane trvalo kladne - a tym aj celu premennu i (jedine miesto kde i bolo *pouzite* je v tom teste); a do portu zapisovat stale tu istu hodnotu (vsimnite si 
vsak, ze kedze p je volatile, prekladac nemoze odstranit cyklus a nahradit ho jedinym zapisom - povodny cyklus zapisuje do p donekonecna, a to s p musi robit 
aj optimalizovany program).

Vsimnite si, ze ta hodnota po pricitani moze byt naozaj akakolvek. Prestavte si, pre priklad, ze by prekladac predpokladal 32767 + 1 = -10000. Znie to sice 
ako uplna hlupost, ale pointa je, ze to prekladac MOZE urobit. MOZE totiz urobit COKOLVEK, kedze vysledok je NEDEFINOVANY. Takyto program by potom LEDkou 
sice blikal, ale akosi divne.

Dalej si vsimnite, ze ta optimalizacia ktora odstrani premennu i aj test v cykle je mozna len za predpokladu, ze i je na zaciatku kladne. Ak namiesto "int i 
= 0"; v definicii premennej i napisem len "int i;", prekladac to aj s -Os prelozi rovnako ako s -O1 - inkrement i aj ten test tam musi ostat, a inkrement i 
je najjednoduchsie implementovat takto "prirodzene", cokolvek ine by bolo menej optimalne. Takze tam ta LEDka blikat bude. Naopak, ak namiesto "int i = 0" 
dam "int i = -1" a namiesto "i++" dam "i--", prekladac znova urobi tu super-optimalizaciu.

Pan kolega Kral: v podstate ste v http://list.hw.cz/pipermail/hw-list/2009-June/144111.html dospeli k obom vysvetleniam; ale pointa je, ze obe su vlastne 
spravne, a chybu tu robi programator. To, ze drviva vacsina prekladacov C implementuje i++ ako prirodzeny inkrement s prirodzenym "wraparoundom" bez 
akychkolvek testov a chybovych osetreni, neznamena, ze to tak bude u vsetkych prekladacov a, ako vidite, aj v tom istom prekladaci pri roznych podmienkach (a 
to nemusi byt dane len prepinacom, moze sa to spravanie zmenit napr. preto, ze v nejakej zlozitejsej funkcii prekladac dospeje k nejakej inej optimalizacii 
kvoli napr. obmedzenemu priestoru v registroch). Nie je podstatne to, co robi nejaka konkretna implementacia jazyka; podstatne je to, co hovori norma.

> To je celé opravdu jen akademická debata. V praxi pouiju pro
> pøetékající èítaè vždy typ unsigned a nebudu øešit, jestli int pøi
> pøeteèení zmìní znamínko nebo zaène od nuly.

Toto je vlastne taky isty problem: ani pri preteceni neznamienkovej premennej nie je zaruce spravanie. Je sice velmi pravdepodobne, ze drviva vacsina 
prekladacov to bude implementovat ako prirodzeny wraparound a nenastavaju tu problemy s pretecenim do znamienka; ale to neznamena, ze to tak bude vzdy. 
Takymto konstrukciam je jednoducho lepsie sa vyhnut; alebo, ak su pre nieco naozaj nevyhnutne (nutna optimalizacia do poslednej bodky), napisat ich v 
asembleri - portabilita je predsa uz aj tak s tym pretecenim pochybna.

Z tohoto pohladu je teda plne odovodnene riesenie, ktore uviedol pan kolega Gregor. Da sa sice namietnut, ze to nie je optimalne co sa tyka velkosti programu 
- ale ak uz raz clovek zacal pouzivat vyssi jazyk, tak by to mal robit s urcitym nadhladom, a nehnat sa za kazdym byte a kazdou mikrosekundou aj za cenu 
"divokeho", a v podstate nespravneho, riesenia.

wek