Forum: PC-Programmierung Comileroptimierung - was kann er und was nicht?


von Christian J. (Gast)


Lesenswert?

Hallo,

ich arbeite derzeit mit dem sdcc und nicht dem gcc aber ich frage mich, 
was man einem Compiler zumuten kann. Der sdcc ist ein 1 Pass Compiler.

Der Ausdruck

 len = strlen(keybuf);
 if ((len < 5) || (len > 21))
   return 0;

ist gleich

 len = strlen(keybuf);
 if ((len < strlen(keybuf)) || (strlen(keybuf) > 21))
   return 0;


Der sdcc erzeugt daraus zweimal einen Aufruf nach strlen, samt der 
Beladung der Register für den Aufruf. Vesion 1 ist einiges kürzer als 
Nr. 2

Wie wäre denn nun ein guter Coding Style? Schauen was man zusammenfassen 
kann oder das dem Compiler überlassen, dass der clever genug ist zu 
erkennen, dass ein Ausdruck mehrfach verwendet wird?



Grüße,
Christian

von Peter II (Gast)


Lesenswert?

Christian J. schrieb:
> Der sdcc erzeugt daraus zweimal einen Aufruf nach strlen, samt der
> Beladung der Register für den Aufruf. Vesion 1 ist einiges kürzer als
> Nr. 2

woher soll denn der Compiler wissen, das strlen reentrant ist?

strlen könnte ja auch den string manipulieren und jeweils 1 Zeichen dran 
hängen.

Wenn man 2 Funktionsaufrufe hinschreibt, wird die Funktion auch 2 mal 
aufgerufen.

von Christian J. (Gast)


Lesenswert?

Numn ja,

wenn ich zweimal

y = x*z;

benutze, dann ist der CCS Compiler schon so clever zu merken, dass der 
Ausdruck zwischengespeichert werden muss. Der CCS ist allerdings für 
PIC.

Beim sdcc für Z80 merke ich jedenfalls, dass es etrem was bringt, wenn 
man mehrfach vorkommende Ausdrücke vorher berechnet. Mehr Variablen = 
weniger Code. Den ultimativen Boost für die Codesize bringt es alle 
Variablen auf static zu setzen, so dass der Stack frei bleibt.

von Peter II (Gast)


Lesenswert?

Christian J. schrieb:
> wenn ich zweimal
>
> y = x*z;
>
> benutze, dann ist der CCS Compiler schon so clever zu merken, dass der
> Ausdruck zwischengespeichert werden muss.

das ist etwas anders. Hier geht es nur um variablen und da darf er alles 
machen so lange am ende das richtige rauskommt.
1
y = strlen(x);
2
y = strlen(x);
3
y = strlen(x);
4
y = strlen(x);

sollte auch nicht optimiert werden, eventuell bei C++ weil der Parameter 
dort const ist.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Peter II schrieb:
> woher soll denn der Compiler wissen, das strlen reentrant ist?

Was hat das mit „reentrant“ zu tun?

Ein Compiler im hosted environment darf jedoch in der Tat davon
ausgehen, dass die Funktion strlen() genau das tut, was im Standard
steht. Lediglich im freestanding environment ist sie wie eine
unbekannte Funktion zu behandeln.

Vermutlich beherrscht der SDCC allerdings diese Unterscheidung und
die daraus möglichen Optimierungen sowieso nicht.  In diesem Falle
kann man dem Compiler natürlich schon mal aushelfen und die erste
Variante wählen.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Peter II schrieb:
> eventuell bei C++ weil der Parameter dort const ist.

Auch bei C ist er seit C89 const.  Das sagt allerdings noch nichts
darüber aus, dass das Ergebnis dieser Funktion nur vom übergebenen
Argument abhängt (es könnte noch von globalen Variablen oder einem
von vorherigen Aufrufen gespeicherten Zustand abhängen).

Im Falle von strlen() jedoch ist der Fall auch in C eindeutig
optimierbar, solange (siehe voriges Posting) ein hosted environment
vorliegt.

von Peter II (Gast)


Lesenswert?

Jörg Wunsch schrieb:
> Ein Compiler im hosted environment darf jedoch in der Tat davon
> ausgehen, dass die Funktion strlen() genau das tut, was im Standard
> steht. Lediglich im freestanding environment ist sie wie eine
> unbekannte Funktion zu behandeln.

ich dachte das hosted environment nur dinge sind wofür man auch kein 
include braucht z.b. sizeof. strlen wird doch in der libc implementiert 
und kann dinge tun von dem der Compiler nicht weiß.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Peter II schrieb:
> strlen wird doch in der libc implementiert und kann dinge tun von dem
> der Compiler nicht weiß.

Was glaubst du wohl, warum es einen C-Standard gibt und warum dies
eben die Standardbibliothek ist?
1
#include <string.h>
2
3
int
4
main(void)
5
{
6
  return strlen("Hello, world");
7
}

cc -O -S hw.c =>
1
        .file   "hw.c"
2
        .text
3
        .globl  main
4
        .type   main, @function
5
main:
6
.LFB24:
7
        .cfi_startproc
8
        movl    $12, %eax
9
        ret
10
        .cfi_endproc
11
.LFE24:
12
        .size   main, .-main
13
        .ident  "GCC: (Ubuntu 4.8.2-19ubuntu1) 4.8.2"
14
        .section        .note.GNU-stack,"",@progbits

von Linksammler (Gast)


Lesenswert?

Peter II schrieb:
> strlen wird doch in der libc implementiert
> und kann dinge tun von dem der Compiler nicht weiß.

der GCC kennt dafür "attributes", die man der Funktion mitgeben kann.
in dem Fall "pure" für strlen:
1
Many functions have no effects except the return value and their return 
2
value depends only on the parameters and/or global variables. Such a 
3
function can be subject to common subexpression elimination and loop 
4
optimization just as an arithmetic operator would be. These functions 
5
should be declared with the attribute pure. For example,
6
7
8
          int square (int) __attribute__ ((pure));
9
10
says that the hypothetical function square is safe to call fewer times 
11
than the program says.
12
13
Some of common examples of pure functions are strlen or memcmp. 
14
Interesting non-pure functions are functions with infinite loops or those 
15
depending on volatile memory or other system resource, that may change 
16
between two consecutive calls (such as feof in a multithreading 
17
environment).
18
19
The attribute pure is not implemented in GCC versions earlier than 2.96.

von Peter II (Gast)


Lesenswert?

Jörg Wunsch schrieb:
> Was glaubst du wohl, warum es einen C-Standard gibt und warum dies
> eben die Standardbibliothek ist?

dann müsste müsst die libc aber immer fest mit dem Compiler verbunden 
sein.


die Erklärung von Linksammler finde ich logischer, das es ein extra 
Attribut gibt. Damit könnte man das auch bei eigenen Funktionen 
einsetzen.

von Linksammler (Gast)


Lesenswert?

Peter II schrieb:
> die Erklärung von Linksammler finde ich logischer, das es ein extra
> Attribut gibt. Damit könnte man das auch bei eigenen Funktionen
> einsetzen.

Die erklärt aber nicht, wie der compiler aus einem "strlen"-Aufruf mit 
Konstantem Parameter gleich eine Konstante (Zahl) macht.

von (prx) A. K. (prx)


Lesenswert?

GCC kennt die Eigenschaften der eingebauten Funktion __builtin_strlen(), 
auf die irgendwo in den Includes die Funktion strlen() umgesetzt wird. 
Damit ist volle Optimierung möglich. Das kann ein Compiler machen, er 
muss es nicht.

Wenn man andererseits auf
  #include <string.h>
verzichtet und
  extern int strlen(const char *);
hinschreibt, dann hat man den Aufruf 4x drin.

Teilt man GCC mit, dass die Funktion nur von ihren Parametern abhängt 
und keine Seiteneffekte hat, dann hat man genau einen Aufruf:
  extern int strlen(const char *) __attribute__((pure));

: Bearbeitet durch User
von Peter II (Gast)


Lesenswert?

A. K. schrieb:
> GCC kennt die Eigenschaften der eingebauten Funktion __builtin_strlen(),
> auf die irgendwo in den Includes die Funktion strlen() umgesetzt wird.
> Damit ist volle Optimierung möglich. Das kann ein Compiler machen, er
> muss es nicht.

danke, das erklärt es nun.

Damit kennt der Compiler also nicht wirklich strlen sondern nur 
__builtin_strlen und in den includes wird darauf gemappt.

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Peter II schrieb:
> dann müsste müsst die libc aber immer fest mit dem Compiler verbunden
> sein.

Nein.  Eine C-Standard-Bibliothek muss sich halt immer nur so
verhalten, dass sie die im Standard beschriebenen Funktionen auch
exakt so implementiert, wie es der Standard vorsieht.

Ein typisches Beispiel ist ja die avr-libc: sie wird als Projekt
unabhängig vom GCC implementiert, aber für all die Funktionen, die
sie implementiert(*), hält sie sich an den Standard.  Der Compiler
wiederum geht im hosted Mode (-fhosted, Default beim GCC) genau
davon aus, und darf (das gestattet ihm der Standard) daher auch
internes Wissen darum haben und ausnutzen, wie sich eine
standardkonforme Funktion verhält.

(*) und die im Standard vorgesehen sind – Erweiterungen sind natürlich
etwas anderes

: Bearbeitet durch Moderator
von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

Peter II schrieb:
> Damit kennt der Compiler also nicht wirklich strlen sondern nur
> __builtin_strlen und in den includes wird darauf gemappt.

Nein.  Nochmal das gleiche Spiel mit dem AVR-GCC, einfach nur durch
den Präprozessor geschickt:
1
$ avr-gcc -E hw.c | fgrep strlen
2
extern size_t strlen(const char *) __attribute__((__pure__));
3
  return strlen("Hello world!");

Also kein __builtin_strlen, dennoch wird der Aufruf durch eine
Konstante ersetzt:
1
        .file   "hw.c"
2
__SP_H__ = 0x3e
3
__SP_L__ = 0x3d
4
__SREG__ = 0x3f
5
__tmp_reg__ = 0
6
__zero_reg__ = 1
7
        .text
8
.global main
9
        .type   main, @function
10
main:
11
/* prologue: function */
12
/* frame size = 0 */
13
/* stack size = 0 */
14
.L__stack_usage = 0
15
        ldi r24,lo8(12)
16
        ldi r25,0
17
        ret
18
        .size   main, .-main
19
        .ident  "GCC: (GNU) 4.7.2"

Optimierung mehrfacher Aufrufe wäre noch mit dem "pure"-Attribut zu
erklären, das Ersetzen durch eine Konstante jedoch nicht.

Zum Gegenvergleich, nochmal mit -ffreestanding:
1
        .file   "hw.c"
2
__SP_H__ = 0x3e
3
__SP_L__ = 0x3d
4
__SREG__ = 0x3f
5
__tmp_reg__ = 0
6
__zero_reg__ = 1
7
        .section        .rodata.str1.1,"aMS",@progbits,1
8
.LC0:
9
        .string "Hello world!"
10
        .text
11
.global main
12
        .type   main, @function
13
main:
14
/* prologue: function */
15
/* frame size = 0 */
16
/* stack size = 0 */
17
.L__stack_usage = 0
18
        ldi r24,lo8(.LC0)
19
        ldi r25,hi8(.LC0)
20
        rcall strlen
21
        ret
22
        .size   main, .-main
23
        .ident  "GCC: (GNU) 4.7.2"
24
.global __do_copy_data

: Bearbeitet durch Moderator
von (prx) A. K. (prx)


Lesenswert?

Es gibt Compiler-Techniken, mit denen ein Compiler selbst herausfinden 
kann, ob eine Funktion Nebeneffekte hat, auch wenn eine Funktion in 
einem anderen Quellfile implementiert ist. Letztlich wird dabei in den 
einzelnen Compilerläufen der Code nur vorübersetzt, die Codegenerierung 
und Optimierung findet erst im Linker statt.

Im GCC dürfte das unter LTO = "link time optimization" zu finden sein, 
bei Microsoft wohl unter "Whole Program Optimization".

von Jörg W. (dl8dtl) (Moderator) Benutzerseite


Lesenswert?

A. K. schrieb:
> Im GCC dürfte das unter LTO = "link time optimization" zu finden sein

Ja, aber selbst die schlägt in meinem Beispiel ja nicht zu, da gar
nicht gelinkt worden ist.  Ist das reine Compilat, wie es sich nach
einem Aufruf mit -S ergibt.

von (prx) A. K. (prx)


Lesenswert?

Jörg Wunsch schrieb:
> Ja, aber selbst die schlägt in meinem Beispiel ja nicht zu, da gar
> nicht gelinkt worden ist.

Betrifft auch eher eigene Funktionen. Hatte nur als Ergänzung zum Thema 
aufgeführt, nicht als Erklärung von strlen().

von Rolf Magnus (Gast)


Lesenswert?

Peter II schrieb:
> Jörg Wunsch schrieb:
>> Ein Compiler im hosted environment darf jedoch in der Tat davon
>> ausgehen, dass die Funktion strlen() genau das tut, was im Standard
>> steht. Lediglich im freestanding environment ist sie wie eine
>> unbekannte Funktion zu behandeln.
>
> ich dachte das hosted environment nur dinge sind wofür man auch kein
> include braucht z.b. sizeof.

Nein, das gibt es immer, egal ob hosted oder nicht.
Der Hauptunterschied zwischen einem hosted und eiem freestanding 
environment ist, daß ersteres das Vorhandensein der Standardbibliothek 
voraussetzt, letzteres nicht. sizeof ist kein Teil der 
Standardbibliothek.

> strlen wird doch in der libc implementiert und kann dinge tun von dem
> der Compiler nicht weiß.

Was strlen macht, ist bei einem hosted environment genau festgelegt. 
Wenn die libc was anderes macht, ist sie nicht konform. Der Compiler 
kann also auch wenn er nicht mit der libc "verheiratet" ist, gewisse 
Annahmen über das Verhalten treffen, unter anderem auch, daß sie bei 
mehrmaligem Aufruf mit dem selben String auch das selbe Ergebnis 
zurückliefert. Dazu sind an sich auch keine speziellen Attribute 
notwendig, sondern es reicht, daß es sich um ein hosted environment 
handelt und die Funktion strlen() heißt.

Peter II schrieb:
> dann müsste müsst die libc aber immer fest mit dem Compiler verbunden
> sein.

Für die Optimierung hilft es, wenn sie sich gegenseitig kennen. Tun sie 
meist auch. Beim gcc geht das dann noch einen Schritt weiter, indem er 
gleich selber einige Funktionen der libc implementiert. So kann er daher 
auch bei Strings, die er zur Compilezeit kennt, den Aufruf der Funktion 
strlen() komplett wegoptimieren und das Ergebnis gleich als Konstante in 
den code schreiben. gcc macht sowas heute für große Teile der libc.
Siehe folgende Liste:
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

> die Erklärung von Linksammler finde ich logischer, das es ein extra
> Attribut gibt. Damit könnte man das auch bei eigenen Funktionen
> einsetzen.

Kann man auch. Trotzdem gibt es für den Compiler noch einige weitere 
Freiheiten bei der Implementation der Standardbibliotheken.

von Rolf Magnus (Gast)


Lesenswert?

Peter II schrieb:
> A. K. schrieb:
>> GCC kennt die Eigenschaften der eingebauten Funktion __builtin_strlen(),
>> auf die irgendwo in den Includes die Funktion strlen() umgesetzt wird.
>> Damit ist volle Optimierung möglich. Das kann ein Compiler machen, er
>> muss es nicht.
>
> danke, das erklärt es nun.
>
> Damit kennt der Compiler also nicht wirklich strlen sondern nur
> __builtin_strlen und in den includes wird darauf gemappt.

Im Prinzip ja, wobei das eine Design-Entscheidung des 
Compiler-Herstellers ist. Der könnte sich auch dazu entscheiden, die 
gesamte Standardbibliothek im Compiler selbst zu implementieren und 
Standardheader gar nicht als Dateien auszuführen.
Ein
1
#include <stdio.h>
wäre dann nur ein spezielle Marker im Programm, der daraufhin die 
entsprechenden Bezeichner der Standardbibliothek quasi "freischaltet".

von ... (Gast)


Lesenswert?

ich kann mir gut vorstellen, dass der compiler pure-functions mit 
compiletime-konstantem parameter selbst ausführen kann. bei 
Math-functions macht er das doch auch... da wird ein ln(1) einfach durch 
0 im quellcode ersetzt... dort wundert sich aber keiner.. warum?

was für mich interessant ist wäre:

>const char* huhu[strlen(huhu)] = "huhu";

compiliert das?

von Rolf Magnus (Gast)


Lesenswert?

... schrieb:
> ich kann mir gut vorstellen, dass der compiler pure-functions mit
> compiletime-konstantem parameter selbst ausführen kann.

Wenn sie inline sind, sollte er das in vielen Fällen hinbekommen. Dazu 
müssen sie dann aber nicht mal pure sein. Das ist ja nur in dem Fall 
relevant, in dem der Compiler die Implementation nicht kennt. Da kann er 
aber die Funktion nicht selber ausführen. Er kann nur bestimmte Annahmen 
darüber treffen und z.B. mehrfaches Ausführen mit den selben 
Parameterwerten verhindern.

> bei Math-functions macht er das doch auch... da wird ein ln(1) einfach
> durch 0 im quellcode ersetzt... dort wundert sich aber keiner.. warum?

ln ist bereits im Compiler selbst implementiert.

> was für mich interessant ist wäre:
>
>>const char* huhu[strlen(huhu)] = "huhu";
>
> compiliert das?

Hier mußt du unterscheiden. Nur weil der Compiler etwas zur Compilezeit 
ausrechnen kann, heißt das nicht, daß er es im Quelltext wie eine 
Konstante behandeln darf. Die Optimierung ändert nichts an der Validität 
des Code. strlen ist eine Funktion, die aufgerufen werden muß und zur 
Laufzeit ein Ergebnis zurückgibt, also kann man sie nicht dort 
verwenden, wo eine Konstante notwendig ist. Daß das Ergebnis durch 
Optimierungen bereits zur Compilezeit berechnet werden kann, spielt 
dabei keine Rolle.

von Christian J. (Gast)


Lesenswert?

Ähm... ok. :-)

Meine Frage war aber schon beantwortet. Der sdcc kann es nicht, auch 
nicht bei fixen Strings im Quelltext. Er ruft immer brav auf und 
Optmierung ist etwas was man selbst machen muss.

von horst (Gast)


Lesenswert?

Christian J. schrieb:
> ist gleich

Wo wird im zweiten Codeschnippsel geprüft, ob der String weniger als 5 
Zeichen hat?



Und sollte der Parameter aus irgendeinem Grund volatile sein, so kann 
bei mehrmaligem Aufruf der Funktion tatsächlich ein anderes Ergebnis 
rauskommen.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.