Optimierung von Bit-Transfer-Operationen

[Wilhelm M. (wimalopaan)]

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:

#include <stdint.h>

constexpr uint8_t BitValue = 1 << 0; // produces bst/bld instruction for avr
// constexpr uint8_t BitValue = 1 << 1; // produces and/and/or sequence

typedef uint8_t value_type;
value_type a, b;

void merge1(value_type& dst, const value_type& src) {
    dst = (src & value_type{BitValue}) | (dst & ~value_type{BitValue});    
}

void merge2(value_type& dst, const value_type& src) {
    dst ^= (dst ^ src) & value_type{BitValue};
}

int main() {
    merge1(a, b);
    merge2(a, b);
}

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

merge1(unsigned char&, unsigned char const&):
        movw r30,r24     ;  dst, dst
        movw r26,r22     ; , src
        ld r24,X         ;  *src_10(D), *src_10(D)
        ld r25,Z         ;  *dst_11(D), *dst_11(D)
        bst r24,0        ;  *src_10(D)
        bld r25,0        ;  tmp56
        st Z,r25         ;  *dst_11(D), tmp56
        ret
merge2(unsigned char&, unsigned char const&):
        movw r30,r24     ;  dst, dst
        ld r25,Z         ;  _1, *dst_10(D)
        movw r26,r22     ; , src
        ld r24,X         ;  *src_11(D), *src_11(D)
        bst r24,0        ;  *src_11(D)
        bld r25,0        ;  tmp55
        st Z,r25         ;  *dst_10(D), tmp55
        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:

merge1(unsigned char&, unsigned char const&):
        movw r30,r24     ;  dst, dst
        movw r26,r22     ; , src
        ld r25,X         ;  *src_10(D), *src_10(D)
        andi r25,lo8(2)  ;  tmp52,
        ld r18,Z         ;  *dst_11(D), *dst_11(D)
        andi r18,lo8(-3)         ;  tmp54,
        or r25,r18       ;  tmp56, tmp54
        st Z,r25         ;  *dst_11(D), tmp56
        ret
merge2(unsigned char&, unsigned char const&):
        movw r30,r24     ;  dst, dst
        ld r24,Z         ;  _1, *dst_10(D)
        movw r26,r22     ; , src
        ld r25,X         ;  *src_11(D), *src_11(D)
        eor r25,r24      ;  tmp52, _1
        andi r25,lo8(2)  ;  tmp54,
        eor r25,r24      ;  tmp55, _1
        st Z,r25         ;  *dst_10(D), tmp55
        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!

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

Vielleicht hilft __builtin_avr_insert_bits aus:
https://gcc.gnu.org/onlinedocs/gcc-4.7.1/gcc/AVR-Built_002din-Functions.html

[Wilhelm M. (wimalopaan)]

A. K. schrieb:
> Vielleicht hilft __builtin_avr_insert_bits aus:
> https://gcc.gnu.org/onlinedocs/gcc-4.7.1/gcc/AVR-Built_002din-Functions.html

Das könnte eine Lösung sein, doch geht es mehr darum zu verstehen, warum 
das so wie oben beschrieben ist.

[Falk B. (falk)]

@Wilhelm M. (wimalopaan)

>Das könnte eine Lösung sein, doch geht es mehr darum zu verstehen, warum
>das so wie oben beschrieben ist.

Warum? Willst du die Innereien des Compilers verstehen?

[Wilhelm M. (wimalopaan)]

Falk B. schrieb:
> @Wilhelm M. (wimalopaan)
>
>>Das könnte eine Lösung sein, doch geht es mehr darum zu verstehen, warum
>>das so wie oben beschrieben ist.
>
> Warum? Willst du die Innereien des Compilers verstehen?

Ja, genau (s.o.)

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

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? ;-)

[Wilhelm M. (wimalopaan)]

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 ...

[Wilhelm M. (wimalopaan)]

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.

[Peter D. (peda)]

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).

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

Peter D. schrieb:
> Selbst zu Assemblerzeiten kann ich mich nicht erinnern, bst/bld je
> benötigt zu haben.

Schau dir man die Beispiele zu __builtin_avr_insert_bits an. Du wusstest 
bisher bloss noch nicht, dass du das brauchst. ;-)

Geht natürlich alles auch anders. Nur langsamer oder platzraubender.

[Johann L. (gjlayde)]

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.

[Wilhelm M. (wimalopaan)]

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.

[Peter D. (peda)]

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%.

[Johann L. (gjlayde)]

Wilhelm M. schrieb:
> Das spielt für die angesprochene Binnenoptimierung aber keine Rolle.

Dann bleibt dir ein Blick in die verwendeten Pattern nicht erspart. 
Siehe entsprechende -fdump-*-all optionen von oben.