Kann ein Compiler kürzen und optimiert er dann?

Folgender Code:

[cpp]
int x;
cin < x;
x = (x * 2)/4
[cpp]

Frage, erkennt er, daß er in der 3. Zeile kürzen kann und dann nur noch einen rechtsshift braucht, anstatt einen langsamen div Befehl?

Wie gut optimieren hier die Compiler?
Wann und wo sind deren Grenzen der automatisierten Optimierung erreicht und ab wann ist es besser, wenn der Mensch selber Hand anlegt und Assemblercode für den kurzen Codeabschnitt schreibt?

Mist, falsches Forum. Eigentlich wollte ich das in "Rund um die Programmierung" posten.
Könnte das ein Mod verschieben?

C++ Forumbot

Dieser Thread wurde von Moderator/in nman aus dem Forum Themen rund um den PC in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

SG1

Multiplikationen/Divisionen in Shifts umwandeln ist trivial und macht eigentlich jeder Compiler. In Deinem Fall braucht er aber nicht nur ein Shift, sondern 2 Shifts (oder 1 Shift+Maske) - die Multiplikation könnte überlaufen.

Bashar

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~

dot

this.optimize schrieb:

Wie gut optimieren hier die Compiler?

Probiers doch aus

Christoph

SG1 schrieb:

In Deinem Fall braucht er aber nicht nur ein Shift, sondern 2 Shifts (oder 1 Shift+Maske) - die Multiplikation könnte überlaufen.

Muss er das wirklich? Überlauf bei signed int ist in C++ undefiniert, insofern müsste der Compiler die Maske auch ignorieren dürfen, oder?

edit: Bashar war schneller.

hustbaer

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.

Visual Studio 2008 Standardeinstellungen

int main()
{
00FE13B0  push        ebp  
00FE13B1  mov         ebp,esp 
00FE13B3  sub         esp,0CCh 
00FE13B9  push        ebx  
00FE13BA  push        esi  
00FE13BB  push        edi  
00FE13BC  lea         edi,[ebp-0CCh] 
00FE13C2  mov         ecx,33h 
00FE13C7  mov         eax,0CCCCCCCCh 
00FE13CC  rep stos    dword ptr es:[edi] 

int x; 
cin >> x; 
00FE13CE  mov         esi,esp 
00FE13D0  lea         eax,[x] 
00FE13D3  push        eax  
00FE13D4  mov         ecx,dword ptr [__imp_std::cin (0FE8298h)] 
00FE13DA  call        dword ptr [__imp_std::basic_istream<char,std::char_traits<char> >::operator>> (0FE8290h)] 
00FE13E0  cmp         esi,esp 
00FE13E2  call        @ILT+320(__RTC_CheckEsp) (0FE1145h) 

x = (x * 2)/4; 
00FE13E7  mov         eax,dword ptr [x] 
00FE13EA  shl         eax,1 
00FE13EC  cdq              
00FE13ED  and         edx,3 
00FE13F0  add         eax,edx 
00FE13F2  sar         eax,2 
00FE13F5  mov         dword ptr [x],eax 

cout << x;
00FE13F8  mov         esi,esp 
00FE13FA  mov         eax,dword ptr [x] 
00FE13FD  push        eax  
00FE13FE  mov         ecx,dword ptr [__imp_std::cout (0FE8294h)] 
00FE1404  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (0FE829Ch)] 
00FE140A  cmp         esi,esp 
00FE140C  call        @ILT+320(__RTC_CheckEsp) (0FE1145h) 

return 1;
00FE1411  mov         eax,1 
}

Bashar

MisterX schrieb:

Visual Studio 2008 Standardeinstellungen

00FE13C2  mov         ecx,33h 
00FE13C7  mov         eax,0CCCCCCCCh 
00FE13CC  rep stos    dword ptr es:[edi] 
[...]
00FE140C  call        @ILT+320(__RTC_CheckEsp) (0FE1145h)

Ich will ja nix sagen, aber bist du dir sicher, dass das keine Debugversion ist?

Bashar schrieb:

MisterX schrieb:
Visual Studio 2008 Standardeinstellungen
00FE13C2  mov         ecx,33h 
00FE13C7  mov         eax,0CCCCCCCCh 
00FE13CC  rep stos    dword ptr es:[edi] 
[...]
00FE140C  call        @ILT+320(__RTC_CheckEsp) (0FE1145h)
Ich will ja nix sagen, aber bist du dir sicher, dass das keine Debugversion ist?

Ups... hab tatsächlich auf debug übersetzt.
Bei Release Version kommt dieses:

int main()
{
012D1000  push        ecx  

int x; 
cin >> x; 
012D1001  mov         ecx,dword ptr [__imp_std::cin (12D203Ch)] 
012D1007  lea         eax,[esp] 
012D100A  push        eax  
012D100B  call        dword ptr [__imp_std::basic_istream<char,std::char_traits<char> >::operator>> (12D2038h)]

x = (x * 2)/4; 
012D1011  mov         eax,dword ptr [esp] 

cout << x;
012D1014  mov         ecx,dword ptr [__imp_std::cout (12D2044h)] 
012D101A  add         eax,eax 
012D101C  cdq              
012D101D  and         edx,3 
012D1020  add         eax,edx 
012D1022  sar         eax,2 
012D1025  push        eax  
012D1026  mov         dword ptr [esp+4],eax 
012D102A  call        dword ptr [__imp_std::basic_ostream<char,std::char_traits<char> >::operator<< (12D2040h)] 

return 1;
012D1030  mov         eax,1 
}

camper

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.

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.