Optimierung von Bit-Transfer-Operationen

Wilhelm M. #5204617
Lesenswert?
• ▲
▼ 
In dem Beitrag

Beitrag "Frage Bitoperation"

geht es darum, ein einzelnes Bit von a nach b zu kopieren.

Zwei mögliche Lösungen sind etwa:

1
#include <stdint.h>

2


3
constexpr uint8_t BitValue = 1 << 0; // produces bst/bld instruction for avr

4
// constexpr uint8_t BitValue = 1 << 1; // produces and/and/or sequence

5


6
typedef uint8_t value_type;

7
value_type a, b;

8


9
void merge1(value_type& dst, const value_type& src) {

10
    dst = (src & value_type{BitValue}) | (dst & ~value_type{BitValue});    

11
}

12


13
void merge2(value_type& dst, const value_type& src) {

14
    dst ^= (dst ^ src) & value_type{BitValue};

15
}

16


17
int main() {

18
    merge1(a, b);

19
    merge2(a, b);

20
}


Mit '-Os' produziert der avr-g++ (sowohl 7.2 also auch 8.0) brav die 
optimale Variante:

1
merge1(unsigned char&, unsigned char const&):

2
        movw r30,r24     ;  dst, dst

3
        movw r26,r22     ; , src

4
        ld r24,X         ;  *src_10(D), *src_10(D)

5
        ld r25,Z         ;  *dst_11(D), *dst_11(D)

6
        bst r24,0        ;  *src_10(D)

7
        bld r25,0        ;  tmp56

8
        st Z,r25         ;  *dst_11(D), tmp56

9
        ret

10
merge2(unsigned char&, unsigned char const&):

11
        movw r30,r24     ;  dst, dst

12
        ld r25,Z         ;  _1, *dst_10(D)

13
        movw r26,r22     ; , src

14
        ld r24,X         ;  *src_11(D), *src_11(D)

15
        bst r24,0        ;  *src_11(D)

16
        bld r25,0        ;  tmp55

17
        st Z,r25         ;  *dst_10(D), tmp55

18
        ret


bestehend aus bst/bld.

Ändert man allerdings das zu kopierende Bit (s.a. comment oben), so 
erkennt der gcc diese Optimierungsmöglichkeit nicht mehr und es 
entsteht:

1
merge1(unsigned char&, unsigned char const&):

2
        movw r30,r24     ;  dst, dst

3
        movw r26,r22     ; , src

4
        ld r25,X         ;  *src_10(D), *src_10(D)

5
        andi r25,lo8(2)  ;  tmp52,

6
        ld r18,Z         ;  *dst_11(D), *dst_11(D)

7
        andi r18,lo8(-3)         ;  tmp54,

8
        or r25,r18       ;  tmp56, tmp54

9
        st Z,r25         ;  *dst_11(D), tmp56

10
        ret

11
merge2(unsigned char&, unsigned char const&):

12
        movw r30,r24     ;  dst, dst

13
        ld r24,Z         ;  _1, *dst_10(D)

14
        movw r26,r22     ; , src

15
        ld r25,X         ;  *src_11(D), *src_11(D)

16
        eor r25,r24      ;  tmp52, _1

17
        andi r25,lo8(2)  ;  tmp54,

18
        eor r25,r24      ;  tmp55, _1

19
        st Z,r25         ;  *dst_10(D), tmp55

20
        ret


Rein aus Interesse: wenn der Optimierer im gcc diese Möglichkeit für 
Bit0 erkennt, sollte er das m.E. ja auch für Bit 1...7 erkennen können? 
Ist das einfach ein Bug im Optimizer (korrekt ist der Code ja) oder gibt 
es andere Gründe, die dagegen sprechen.

Dasselbe gilt übrigens auch wenn der DT nicht uint8_t ist. Dann wird 
diese optimale Variante bst/bld gar nicht generiert (auch nicht für 
Bit0).

Vielleicht kann jemand der Mitglieder, die auch im gcc-Projekt aktiv 
sind, mich ein wenig "erhellen" ... Danke!
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
(prx) A. K. #5204854
Lesenswert?
• ▲
▼ 
Wilhelm M. schrieb:
> doch geht es mehr darum zu verstehen, warum
> das so wie oben beschrieben ist.

GCC ist Open Source, mit reichlich Optionen für die Darstellung der 
Zwischenstufen bei der Optimierung. Und wenn jener Forenteilnehmer mit 
recht viel Einblick in BLD/BST Optimierungen derzeit nicht mitliest, 
müsstest du dir eben die Mühe machen, selber reinzuschauen.

Wilhelm M. schrieb:
>> Warum? Willst du die Innereien des Compilers verstehen?
>
> Ja, genau (s.o.)

Verstehen - oder verstehen lassen, mit detaillierter Erklärung? ;-)
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wilhelm M. #5204860
Lesenswert?
• ▲
▼ 
A. K. schrieb:
> Wilhelm M. schrieb:
>> doch geht es mehr darum zu verstehen, warum
>> das so wie oben beschrieben ist.
>
> GCC ist Open Source, mit reichlich Optionen für die Darstellung der
> Zwischenstufen bei der Optimierung. Und wenn jener Forenteilnehmer mit
> recht viel Einblick in BLD/BST Optimierungen derzeit nicht mitliest,
> müsstest du dir eben die Mühe machen, selber reinzuschauen.

Werde ich tun.

Es hätte aber auch sein können, dass der geballte Sachverstand in diesem 
Forum sagt, dass das, was ich da oben vermute, ist Quatsch, weil ...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wilhelm M. #5204866
Lesenswert?
• ▲
▼ 
A. K. schrieb:
> Wilhelm M. schrieb:
>> doch geht es mehr darum zu verstehen, warum
>> das so wie oben beschrieben ist.
>
> GCC ist Open Source, mit reichlich Optionen für die Darstellung der
> Zwischenstufen bei der Optimierung. Und wenn jener Forenteilnehmer mit
> recht viel Einblick in BLD/BST Optimierungen derzeit nicht mitliest,
> müsstest du dir eben die Mühe machen, selber reinzuschauen.
>
> Wilhelm M. schrieb:
>>> Warum? Willst du die Innereien des Compilers verstehen?
>>
>> Ja, genau (s.o.)
>
> Verstehen - oder verstehen lassen, mit detaillierter Erklärung? ;-)

Ich weiß nicht, was das jetzt wieder soll: dieses Forum ist doch nicht 
nur dazu da, Fragen zu stellen, sondern auch Antworten zu bekommen, 
oder? Und wer die Frage dumm findet oder einfach keine Antwort geben 
will, der braucht auch keinen Beitrag zu schreiben.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Peter D. #5205106
Lesenswert?
• ▲
▼ 
Ich finde die Frage nicht dumm, aber ich verstehe, daß da keiner große 
Lust dazu hat. Ob nun 10 oder 11 Zyklen ist nicht so der riesen 
Unterschied.
Davon abgesehen ist mir in der Praxis bisher keine auch nur ähnliche 
Aufgabe begegnet. Ich mag viel lieber Aufgaben, die auch einen 
praktischen Bezug haben.

Selbst zu Assemblerzeiten kann ich mich nicht erinnern, bst/bld je 
benötigt zu haben.
Ich habe T nur als Userflag benutzt, z.B. um zu unterscheiden, ob die 
Division den Quotienten oder den Rest berechnen soll.
Beim 8051 waren die Bitbefehle erheblich leistungsfähiger, da konnte man 
sogar Bits aus Portpins einlesen oder ausgeben (MOV C, P1.2 oder MOV 
P2.3, C).
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Johann L. Persönliche Seite #5205191
Lesenswert?
• ▲
▼ 
Wilhelm M. schrieb:
> doch geht es mehr darum zu verstehen, warum
> das so wie oben beschrieben ist.

-fdump-tree-all -fdump-rtl-all -fdump-ipa-all

und: lesen :o)

> void merge1(value_type& dst, const value_type& src)

Wohl ein C++er-Reflex das &src.  Wenn das Zeug nicht geinlint wird 
erzwingt das einen 16-Bit Zeiger (AVR) und indirekten Zugriff. Wenn es 
dir um "optimal" geht, dann solltest du das beheben bevor du über 
Feinheiten der GCC-Optimizer sinnierst.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Wilhelm M. #5205258
Lesenswert?
• ▲
▼ 
Johann L. schrieb:

> Wohl ein C++er-Reflex das &src.  Wenn das Zeug nicht geinlint wird
> erzwingt das einen 16-Bit Zeiger (AVR) und indirekten Zugriff.

Das stimmt nicht ganz, da es ein const T& ist, und dort normalerweise 
die ipa sra Optimierung gemacht wird (bei einem template, woher der Code 
auch stammt).

> Wenn es
> dir um "optimal" geht, dann solltest du das beheben bevor du über
> Feinheiten der GCC-Optimizer sinnierst.

Das spielt für die angesprochene Binnenoptimierung aber keine Rolle.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren