Kann ein Compiler kürzen und optimiert er dann?

camper schrieb:

hustbaer schrieb:

Jeder vernünftige Compiler definiert das Verhalten bei Überlauf.
Ob das vom Standard vorgeschrieben (implementation-defined vs. undefined) ist müsste ich nachsehen, aber darauf kommts nicht an. Zu behaupten ein Compiler könnte daraus evtl. nur einen einzigen Shift machen ist daher entweder falsch oder zumindest weltfremd.

gcc ist unvernünftig und weltfremd?
Natürlich kann kein einfaches shift herauskommen, sondern nur ein solches, dass das Vorzeichen bewahrt.

Untersucht doch mal, was bei dem hier rauskommt:
int x, y;
cin >> x;
x = x * x;
y = ( x * 2 ) / 4;
x kann nicht negativ werden (ohne Überlauf). Hier wird ein schlauer Compiler also ein einfaches shift draus machen.

Als Release kommt:

int main()
{
00091000  push        ecx  

int x, y; 
cin >> x; 
00091001  mov         ecx,dword ptr [__imp_std::cin (9203Ch)] 
00091007  lea         eax,[esp] 
0009100A  push        eax  
0009100B  call        dword ptr [__imp_std::basic_istream<char,std::char_traits<char> >::operator>> (92038h)] 

x = x * x; 
00091011  mov         eax,dword ptr [esp] 

y = ( x * 2 ) / 4;

cout << x;
00091014  mov         ecx,dword ptr [__imp_std::cout (92044h)] 
0009101A  imul        eax,eax 
0009101D  push        eax  
0009101E  mov         dword ptr [esp+4],eax 
00091022  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (92040h)] 

return 1;
00091028  mov         eax,1 
}

Ahhh Schei.. es sollte bestimmt y ausgegeben werden ^^

int main()
{
00E21000  push        ecx  

int x, y; 
cin >> x; 
00E21001  mov         ecx,dword ptr [__imp_std::cin (0E2203Ch)] 
00E21007  lea         eax,[esp] 
00E2100A  push        eax  
00E2100B  call        dword ptr [__imp_std::basic_istream<char,std::char_traits<char> >::operator>> (0E22038h)] 
x = x * x; 
00E21011  mov         eax,dword ptr [esp] 
y = ( x * 2 ) / 4;

cout << y;
00E21014  mov         ecx,dword ptr [__imp_std::cout (0E22044h)] 
00E2101A  imul        eax,eax 
00E2101D  mov         dword ptr [esp],eax 
00E21020  add         eax,eax 
00E21022  cdq              
00E21023  and         edx,3 
00E21026  add         eax,edx 
00E21028  sar         eax,2 
00E2102B  push        eax  
00E2102C  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (0E22040h)] 

return 1;
00E21032  mov         eax,1 
}

camper

Das wäre dann ja noch was, das am gcc verbessert werden könnte...

Christoph

hustbaer schrieb:

Jeder vernünftige Compiler definiert das Verhalten bei Überlauf.
Ob das vom Standard vorgeschrieben (implementation-defined vs. undefined) ist müsste ich nachsehen, aber darauf kommts nicht an. Zu behaupten ein Compiler könnte daraus evtl. nur einen einzigen Shift machen ist daher entweder falsch oder zumindest weltfremd.

LLVM und clang, an denen gerade gut entwickelt wird, scheinen bei undefiniertem Verhalten deutlich agressiver vorzugehen als bisherige Compiler:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

For example, knowing that INT_MAX+1 is undefined allows optimizing "X+1 > X" to "true". Knowing the multiplication "cannot" overflow (because doing so would be undefined) allows optimizing "X*2/2" to "X".

edit: Es gibt auch eine Fortsetzung des ersten Blogposts, wo noch ein paar Punkte erwähnt werden: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html

Bashar

Der Artikel (und der von dort verlinkte Artikel) ist unbedingt lesenswert.

SG1

Bashar schrieb:

Beim Überlauf ist der Verhalten undefiniert, darum muss er sich also nicht kümmern.

Gnar, ich vergaß. Asche auf mein Haupt.

hustbaer

Hm.
Wie man sich irren kann.

Chris Lattner schrieb:

Why undefined behavior is often a scary and terrible thing for C programmers

Dem kann ich mich nur anschliessen.

ps

regehr schrieb:

Basically: be very careful, use good tools, and hope for the best.

hope for the best

Bashar schrieb:

Er muss einmal links und einmal rechts schieben, das zusammenzufassen sollte nicht das große Problem sein. Beim Überlauf ist das Verhalten undefiniert, darum muss er sich also nicht kümmern.

~edit: deutsche sprache schwere sprache~

Aber wozu soll er nach links schieben?
Wenn er kürzt, dann fliegt die Multiplikaion raus, übrig bleibt eine Division durch 2 die mit einem einzigen rechtsshift lösbar ist.

Bashar

this.optimize schrieb:

Bashar schrieb:

Er muss einmal links und einmal rechts schieben, das zusammenzufassen sollte nicht das große Problem sein.

Aber wozu soll er nach links schieben?

Das würde er tun, wenn er den Ausdruck direkt übersetzt und für die Multiplikation alleine ein optimales (naja, relativ) Codemuster wählt.

Wenn er kürzt, dann fliegt die Multiplikaion raus, übrig bleibt eine Division durch 2 die mit einem einzigen rechtsshift lösbar ist.

Geht auch. Mein hypothetischer Compiler kürzt halt keine Brüche, sondern fasst nur Shifts zusammen.

@Bashar
Du arbeitest im Bereich Compiler, oder?
Falls ja, darf man mehr erfahren? Das Thema ist spannend aber die Arbeitsstellen natürlich sehr rar.