Optimierung von Bit-Transfer-Operationen

Wilhelm M. OP #5204617 
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 Langsamer Modus Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Melden Danke
(prx) A. K. #5204854 
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 Melden Danke
Wilhelm M. OP #5204860 
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 Melden Danke
Wilhelm M. OP #5204866 
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 Melden Danke
Peter D. #5205106 
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 Melden Danke
Johann L. Persönliche Seite #5205191 
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 Melden Danke
Wilhelm M. OP #5205258 
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 Melden Danke
Peter D. #5205358 
A. K. schrieb:
> Geht natürlich alles auch anders. Nur langsamer oder platzraubender.

Man sollte eher sagen, minimal langsamer und größer.
Bei völligem Durcheinander (8 * bst/bld) braucht das klassische SBRC+ORI 
gerademal initial ein CLR bzw. ANDI mehr, also 18 statt 17 
Zyklen/Befehle.
Die Einsparung ist also winzige 5%.
Antwort Zitieren Bearbeiten Löschen Melden Danke
Thread beobachten

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 8 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Dein Name und deine E-Mail-Adresse

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.