Ausdruck optimieren auf Laufzeit

Kommt drauf an, welcher Prozessor und ggf. Compiler.

Der Shift ist auf heutigen PCs am schnellsten (Sprich 386 aufwärts). 
Aber jeder gute Compiler setzt die anderen Anweisungen in den Shift um.

Klaus schrieb:
> Es ist vollkommen egal, welchen Ausdruck du verwendest. Jeder halbwegs
> vernünftige Optimizer verwendet automatisch die schnellste Variante.

Interessant sind allerdings Fälle, wo die entsprechende Optimierung dem 
Compiler verboten ist.

Beispiel: Multiplikation mit 7

1

x = (x<<3)-x;

Da in diesem Fall das Ergebnis für einen Teil des möglichen 
Wertebereichs anders ausfällt als bei einer echten Multiplikation mit 7 
(nämlich dann, wenn x*8 nicht mehr passt, x*7 aber schon), kann der 
Compiler die Optimierung selbst nicht durchführen. Der Programmierer 
kann dies aber tun, wenn er weiß, dass Werte aus dem fraglichen Bereich 
nicht auftreten können.

In anderen Sprachen (Ada z.B.) ist es wiederum möglich, bei Variablen 
den exakten Wertebereich zu definieren, hier kann der Compiler dann 
wieder selbst optimieren.

Andreas

Andreas Ferber schrieb:

> Compiler die Optimierung selbst nicht durchführen.

Bei welchen Werten treten denn verschiedene Ergebnisse auf? Immerhin 
führt GCC genau diese Optimierung durch, in beiden Vorzeichenvarianten 
(x86 und avr). Weder Shift noch Subtraktion fliegen beim Überlauf aus 
dem Fenster, sondern haben normales Modulo-Verhalten, weshalb das 
Ergebnis wieder stimmt.

Ein besseres Beispiel ist
  x = x / 8;
was bei Typen mit Vorzeichen aufgrund anderer Rundung bei negativen 
Werten nicht direkt durch Shift ersetzbar ist.

Umgekehrt wird ein Schuh draus: Der Compiler, der die Eigenschaften 
seiner Zielmaschine exakt kennt, darf die Ausdrücke
  x = x * 7;
  x = (x << 3) - x;
ggf. als exakt äquivalent ansehen. Der Programmierer jedoch, der nur den 
C Standard als Basis hat, der darf dies nur bei vorzeichenloser 
Rechnung.

A. K. schrieb:
>> Compiler die Optimierung selbst nicht durchführen.
> Bei welchen Werten treten denn verschiedene Ergebnisse auf?

Zum Beispiel auf AVR mit int8_t x = -17 oder x=-18. Bei x*7 ist in 
beiden Fällen alles im grünen Bereich, es kommt -119 bzw. -126 heraus. 
Bei (x<<3)-x hat man dagegen undefined behaviour, und auch real kommt 
hier dann -127 (nach dem Shiften, vom GCC implementiert durch 
wiederholtes addieren, ist binär 01110000 im Register, dazu 00010001 
(17) addiert ergibt 10000001) bzw. +122 heraus.

> Immerhin
> führt GCC genau diese Optimierung durch, in beiden Vorzeichenvarianten
> (x86 und avr).

Prinzipiell schon, aber er erweitert dazu den Wert auf 16 Bit (x ist 
jeweils int8_t, kompiliert mit avr-gcc -O6 für einen AVR ohne 
Hardware-Multiplikation, GCC Version 4.3.4):

1

        x = x*7;

2

   0:   20 91 00 00     lds     r18, 0x0000

3

   4:   33 27           eor     r19, r19

4

   6:   27 fd           sbrc    r18, 7

5

   8:   30 95           com     r19

6

   a:   c9 01           movw    r24, r18

7

   c:   88 0f           add     r24, r24

8

   e:   99 1f           adc     r25, r25

9

  10:   88 0f           add     r24, r24

10

  12:   99 1f           adc     r25, r25

11

  14:   88 0f           add     r24, r24

12

  16:   99 1f           adc     r25, r25

13

  18:   82 1b           sub     r24, r18

14

  1a:   93 0b           sbc     r25, r19

15

  1c:   80 93 00 00     sts     0x0000, r24

vs.

1

        x = (x<<3)-x;

2

   0:   90 91 00 00     lds     r25, 0x0000

3

   4:   89 2f           mov     r24, r25

4

   6:   88 0f           add     r24, r24

5

   8:   88 0f           add     r24, r24

6

   a:   88 0f           add     r24, r24

7

   c:   89 1b           sub     r24, r25

8

   e:   80 93 00 00     sts     0x0000, r24

Durch die Erweiterung wird die Overflow-Problematik umgangen.

> Der Programmierer jedoch, der nur den
> C Standard als Basis hat, der darf dies nur bei vorzeichenloser
> Rechnung.

Oder wenn er weiß, dass (im Beispiel mit int8_t) die Werte -17 und -18 
niemals vorkommen können. Der Compiler kann das nicht wissen (zumindest 
nicht bei C).

Andreas

Andreas Ferber schrieb:
> Zum Beispiel auf AVR mit int8_t x = -17 oder x=-18. Bei x*7 ist in
> beiden Fällen alles im grünen Bereich, es kommt -119 bzw. -126 heraus.
> Bei (x<<3)-x hat man dagegen undefined behaviour, und auch real kommt
> hier dann -127 (nach dem Shiften, vom GCC implementiert durch
> wiederholtes addieren, ist binär 01110000 im Register, dazu 00010001
> (17) addiert ergibt 10000001) bzw. +122 heraus.

Argh, um 1 Bit vertan. OK, passt real doch alles (für C bleibt es aber 
undefined). Trotzdem bleibt (warum auch immer):

>> Immerhin
>> führt GCC genau diese Optimierung durch, in beiden Vorzeichenvarianten
>> (x86 und avr).
> Prinzipiell schon, aber er erweitert dazu den Wert auf 16 Bit (x ist
> jeweils int8_t, kompiliert mit avr-gcc -O6 für einen AVR ohne
> Hardware-Multiplikation, GCC Version 4.3.4):
[...]

Andreas

Andreas Ferber schrieb:

> Durch die Erweiterung wird die Overflow-Problematik umgangen.

Auch bei

int f(int x)
{
   return x * 7;
}

erzeugt GCC die (x<<3)-x Variante.

Andreas Ferber schrieb:

>> Bei (x<<3)-x hat man dagegen undefined behaviour

Nur wenn der Programmierer das so hinschreibt. Dem Compiler ist das 
Verhalten der Maschine bei Überlauf hingegen bekannt, daher darf er das 
im Zwischencode sehr wohl verwenden wenn er weiss dass das gleiche 
rauskommt.

A. K. schrieb:
> int f(int x)
> {
>    return x * 7;
> }
> erzeugt GCC die (x<<3)-x Variante.

Interessanterweise bekommt er es in diesem Fall auch mit int8_t hin:

1

int8_t f(int8_t x)

2

{

3

   0:   98 2f           mov     r25, r24

4

   2:   99 0f           add     r25, r25

5

   4:   99 0f           add     r25, r25

6

   6:   99 0f           add     r25, r25

7

        return x*7;

8

}

9

   8:   98 1b           sub     r25, r24

10

   a:   89 2f           mov     r24, r25

11

   c:   08 95           ret

Umso schleierhafter, warum er bei "x = x*7;" mit int8_t x auf der 
Erweiterung zu 16 Bit besteht.

Andreas

Andreas Ferber schrieb:

...
>
> Umso schleierhafter, warum er bei "x = x*7;" mit int8_t x auf der
> Erweiterung zu 16 Bit besteht.

Weil "7" den Datentyp integer hat.
Und das ist beim AVR-GCC 16 Bit breit.
Es muss vor einer Multiplikation der kürzere Typ erweitert werden (sagt 
der C Standard).

Werner B. schrieb:

> Weil "7" den Datentyp integer hat.
> Also muss vor einer Multiplikation der kürzere Typ erweitert werden.

Nein, er muss nicht. Wenn im Ergebnis das Gleiche rauskommt darf der 
Compiler auch ohne Erweiterung rechnen. Tut er auch ziemlich oft. Er 
muss nur so handeln als ob eine Erweiterung stattfinden würde.

Ausserdem ist es völlig schnuppe, ob du
  x * 7
oder
  x * (int8_t)7
schreibst, denn jeder Ausdruck < "int" ist automatisch ein Ausdruck mit 
Rechnung und Ergebnis in "int". Dem Prinzip nach.

Andreas Ferber schrieb:
> Umso schleierhafter, warum er bei "x = x*7;" mit int8_t x auf der
> Erweiterung zu 16 Bit besteht.

Der GCC 4.4.3 macht auch in diesem Fall die Shifts und die Subtraktion
in 8 Bit.