AVR-GCC: Frage zu Constant Folding / Constant propagation

[Michael R. (Firma: Brainit GmbH) (fisa)]

Hallo zusammen,

ich habe einen Ausdruck in der Form:

y = x * (a2 - a1) / (b2 - b1);

wobei a1, a2 und b1, b2 Konstanten sind.

"Theoretisch" könnte der Compiler ja (a2-a1)/(b2-b1) vorab ausrechnen 
und den Ausdruck vereinfachen zu

y = x * k;

wobei k die zur Kompilierzeit ausgerechnete Konstante ist.

Spannend wird das Ganze, wenn es nicht um float oder double geht, 
sondern um int (in meinem Fall int32_t)

Offensichtlich ist der gcc hier klug genug, zwar (a2-a1) und (b2-b1) 
vorab auszurechnen (ich nenn sie mal da und db) und den Ausdruck zu

y = (x * da) / db;

zu vereinfachen, andernfalls hätte man einen sehr erheblichen (u.U. 
totalen) Genauigkeitsverlust. Die Klammern hab ich gesetzt um die 
Reihenfolge der Berechnung zu verdeutlichen.

Frage: Kann man sich auf dieses Verhalten verlassen? Wenn ja, steht das 
irgendwo dass der gcc so vorgeht? Gibts da irgendwelche "Fallen" in die 
man tappen könnte?


Danke, michi

[(prx) A. K. (prx)]

Michael Reinelt schrieb:
> Frage: Kann man sich auf dieses Verhalten verlassen?

Der Compiler darf im Rahmen von Optimierung das Ergebnis nur dann 
ändern, wenn auch ohne Optimierung unspezifizierte oder undefinierte 
Schritte auftreten.

Sind jedoch alle Schritte von der Sprache klar definiert und 
spezifiziert, dann darf sich das Ergebnis durch die Optimierung nicht 
verändern.

[Stefan E. (sternst)]

Michael Reinelt schrieb:
> "Theoretisch" könnte der Compiler ja (a2-a1)/(b2-b1) vorab ausrechnen
> und den Ausdruck vereinfachen zu

 y = x * k;

> wobei k die zur Kompilierzeit ausgerechnete Konstante ist.

Nein, kann er nicht, denn die Operatoren sind linksassoziativ.

> Frage: Kann man sich auf dieses Verhalten verlassen?

Ja, wenn sich der Compiler an den C-Standard hält.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Stefan Ernst schrieb:
> Michael Reinelt schrieb:
>> "Theoretisch" könnte der Compiler ja (a2-a1)/(b2-b1) vorab ausrechnen
>> und den Ausdruck vereinfachen zu
>

>  y = x * k;
>

>> wobei k die zur Kompilierzeit ausgerechnete Konstante ist.
>
> Nein, kann er nicht, denn die Operatoren sind linksassoziativ.

Tja, was soll ich sagen: du hast recht!

Aber ich verstehe ehrlich gesagt nicht, warum :-(

ich hab mal folgendes kleines progrämmle geschrieben:

#include <stdio.h>
#include <stdlib.h>

typedef int int32_t;


static int func1(const int x)
{
    const int a = 750;
    const int b = 1000;

    return x * a / b;
}

static double func2(const double x)
{
    const double a = 750.0;
    const double b = 1000.0;

    return x * a / b;
}


static double func3(const double x)
{
    const double a = 750.0;
    const double b = 1000.0;

    return x * (a / b);
}

static double func4(const double x)
{
    const double a = 750.0;
    const double b = 1000.0;

    return a / b * x;
}


int main (int argc, char *argv[])
{
    int x;

    for (x = 700; x < 1000; x+=10) {
  printf ("%d: %d %.2f %.2f %.2f\n", x, func1(x), func2(x), func3(x), func4(x));
    }
    return 0;
}

Compiliert mit:

gcc -Wall -fno-inline -O9 -S -o junk.s junk.c

Erwartet hätte ich, dass func2/3/4() denselben Assembler-Code ergeben, 
weil ja auch mathematisch die Ausdrücke (a * b) / c und a * (b / c) und 
b / c * a identisch sind (hoffe ich jedenfalls, immerhin ist die 
Multiplikation ja kommutativ)

!atsächlich wird aus func2() aber eine Multiplikation + Division, 
während func3() und func4 nur zu einer Division führt!

Das find ich insofern hochinteressant, da in der Praxis natürlich 
func2() signifikant langsamer sein wird (wegen der Division)

Kann mir das jemand erklären?

[(prx) A. K. (prx)]

Bei der formalen mathematischen Multiplikation gilt das 
Assoziativgesetz, aber bei der in realen Rechner implementierten 
Multiplikation gilt es nicht.

Theoretisch:  (a * b) * c == a * (b * c)
Real möglich: (a * b) * c != a * (b * c)

Grund: Die mathematische Theorie kennt weder Überlauf noch begrenzte 
Genauigkeit.

[Stefan E. (sternst)]

Michael Reinelt schrieb:
> Aber ich verstehe ehrlich gesagt nicht, warum :-(

Weil der Standard das so vorgibt. Operator-Vorrang und -Assoziativität 
sind genau festgelegt.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Danke euch! Wieder was gelernt! ich verstehe nun die Hintergründe, aber 
das war mir so nicht klar!

Nachtrag: mit -ffast-math ist der GCC dann "aggressiv" und reduziert 
wirklich alle drei Funktionen auf denselben Code, eine Multiplikation.

[Karl H. (kbuchegg)]

Michael Reinelt schrieb:

> Kann mir das jemand erklären?

Nimm nicht so abenteuerliche Konstanten sondern zb 2 und 3. Und um das 
Problem deutlich zu sehen, setz dir selbst eine Auflösungsgrenze von zb 
nur 1 Nachkommastelle. D.h. nach JEDER Berechnung limitierst du die 
Auflösung auf genau 1 Nachkommastelle und nicht mehr.
Dann sieht man sehr schnell, das man eben nicht dieselben Ergebnisse 
bekommmt, wenn man die Reihenfolge der Berechnungen umordnet.

x sei 15, a gleich 2.0, b gleich 3.0

    return x * a / b;

  15.0 * 2.0 -> 30.0
  30.0 / 3.0 -> 10.0

    return x * (a / b);

  2.0 / 3.0     -> 0.6
  15.0 * 0.6    -> 9.0

    return a / b * x;

  2.0 / 3.0     -> 0.6
  15.0 * 0.6    -> 9.0

Offenbar kriegst du von den Berechnungen nicht identische Ergebnisse.
Und ... Compilerbauer sind auch keine Trottel.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Danke Karl Heinz, jetzt ists mir endgültig klar.

Gut zu wissen, weil bis jetzt hab ich mir nie die Mühe gemacht, 
Ausdrücke u.U. umzuordnen, ich hab mich auf "der Compiler wirds schon 
richten" verlassen. Nun, er richtet's nicht, aus gutem Grund.

Übrigens: Der Einfluss von "-ffast-math" auf die binary-größe ist 
durchaus erheblich: In einem größeren AVR-Projekt, wo floats eigentlich 
nur für die Berechnung von (unwichtigen) Zwischenergebnissen und deren 
Formatierung zur Ausgabe am Display verwendet wird, sinkt die Größe der 
main() funktion von 7548 auf 6932 Byte (immerhin fast 10% !!!)