[AVR] Optimierung von 32bit shifts

[André A. (nummer5)]

Hallo,
ich arbeite gerade an einem Code wo ich aus ein paar bits eines uint32_t 
einen Arrayindex berechnen muss:

uint8_t test(uint32_t var)
{
    uint8_t index =  ((var >> 18) & 0x30) | ((var >> 4) & 0x0F);
    return index;
}

Der Index besteht immer aus einem 2-Bit Bereich und einen 4-Bit Bereich:

0 0 B2 B1 A4 A3 A2 A1

Wenn ich das ganze durch GCC (4.7.2) laufen lassen, generiert der 
Compiler leider zwei Schiebeschleifen:

00000080 <test>:
  80:  0f 93         push  r16
  82:  1f 93         push  r17
  84:  8b 01         movw  r16, r22
  86:  9c 01         movw  r18, r24
  88:  44 e0         ldi  r20, 0x04  ; 4
  8a:  36 95         lsr  r19
  8c:  27 95         ror  r18
  8e:  17 95         ror  r17
  90:  07 95         ror  r16
  92:  4a 95         dec  r20
  94:  d1 f7         brne  .-12       ; 0x8a <test+0xa>
  96:  0f 70         andi  r16, 0x0F  ; 15
  98:  11 27         eor  r17, r17
  9a:  22 27         eor  r18, r18
  9c:  33 27         eor  r19, r19
  9e:  ab 01         movw  r20, r22
  a0:  bc 01         movw  r22, r24
  a2:  e2 e1         ldi  r30, 0x12  ; 18
  a4:  76 95         lsr  r23
  a6:  67 95         ror  r22
  a8:  57 95         ror  r21
  aa:  47 95         ror  r20
  ac:  ea 95         dec  r30
  ae:  d1 f7         brne  .-12       ; 0xa4 <test+0x24>
  b0:  40 73         andi  r20, 0x30  ; 48
  b2:  55 27         eor  r21, r21
  b4:  66 27         eor  r22, r22
  b6:  77 27         eor  r23, r23
  b8:  80 2f         mov  r24, r16
  ba:  84 2b         or  r24, r20
  bc:  1f 91         pop  r17
  be:  0f 91         pop  r16
  c0:  08 95         ret

Mit den obigen Zahlenwerten würde es meiner Meinung nach reichen nur 
Byte0 bzw. Byte2 zu schieben, da alle anderen Bits nicht von Bedeutung 
sind.
Hat jemand eine Idee wie ich GCC dazu überreden könnte? Mir wäre es 
wichtig, dass die Lesbarkeit erhalten bleibt, da ich mehrer Indizes aus 
unterschiedlichen Bits (andere Anzahl an Verschiebungen) benötige.

[Läubi .. (laeubi)]

Eventuell kannst du den GCC motivieren indem du erst die relevanten Bits 
ausmaskierst und dann schiebst?

André Althaus schrieb:
> würde es meiner Meinung nach reichen

Vermutung oder hast du das nachgeprüft?

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

Nicht schön, aber gut:

unsigned char test(unsigned long var)
{
    unsigned char var1 = var;
    unsigned char var2 = var >> 16;
    unsigned char index = ((var2 >> 2) & 0x30) | ((var1 >> 4) & 0x0F);
    return index;
}

        lsr r24
        lsr r24
        andi r24,lo8(48)
        swap r22
        andi r22,lo8(15)
        or r24,r22
        ret

[André A. (nummer5)]

Läubi .. schrieb:
> Eventuell kannst du den GCC motivieren indem du erst die relevanten Bits
> ausmaskierst und dann schiebst?

Das ändert leider nichts.

> Vermutung oder hast du das nachgeprüft?

Ich brauche im Ergebnis nur Bit 18,19 (die stehen in Byte 2) und Bit 4-7 
(die stehen in Byte 0)

A. K. schrieb:
> Nicht schön, aber gut

Ja das klappt, aber dann müsste ich alle Rechnungen per Hand machen, da 
je nach benötigten Bits, andere Bytes benötigt werden. (Ich wollte es 
eigentlich als Makro nutzen)

uint8_t test4(uint32_t var)
{
    uint8_t index;
    uint8_t var1 = ((var >> 18) & 0x30);
    uint8_t var2 = ((var >> 4) & 0x0F);
    index = var1 | var2;
    return index;
}

Mir ist nicht klar, warum der GCC bei diesem Code nicht sieht, dass für 
var1 nur Byte 2 und für var2 nur Byte 0 relevant sind. Er schiebt immer 
alle 32 Bit.

Vielleicht hat ja noch jemand einen Geistesblitz?

[Falk B. (falk)]

@  André Althaus (nummer5)

>Mir ist nicht klar, warum der GCC bei diesem Code nicht sieht, dass für
>var1 nur Byte 2 und für var2 nur Byte 0 relevant sind. Er schiebt immer
>alle 32 Bit.

>Vielleicht hat ja noch jemand einen Geistesblitz?

Man kann mit einem Union auf die einzelnen Bytes des 32 Bit Werts 
zugreifen, das geht direkt und schnell. Ist zwar nicht 100% portabel, 
geht aber.

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

Falk Brunner schrieb:
> Man kann mit einem Union auf die einzelnen Bytes des 32 Bit Werts
> zugreifen, das geht direkt und schnell. Ist zwar nicht 100% portabel,
> geht aber.

Sicher, aber den Trick kennt GCC auch, nur eleganter. Er erkennt, dass 
man Bytes aus Shifts um 8*n auch ohne Aufwand raus bekommt. Das ist ja 
die Basis meiner Lösung.

Ihm hilft das vermutlich nichts, weil solche Lösungen nicht generisch 
sind und dort scheitern, wo das Feld über einer Byte/Wortgrenze liegt.

Ansatz daher: Wenn die Shiftcounts und Masken konstant sind, kann man 
eine Fallunterscheidung drum herum zimmern und dann wenns passt mit 
>>8*n direkt auf die Bytes gehen wie in meiner Lösung. Die 
Fallunterscheidung kostet nichts, weil sie komplett vom Compiler 
eingedampft wird.

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

André Althaus schrieb:
> Ja das klappt, aber dann müsste ich alle Rechnungen per Hand machen, da
> je nach benötigten Bits, andere Bytes benötigt werden. (Ich wollte es
> eigentlich als Makro nutzen)

Du solltest vielleicht die Rahmenbedingungen etwas präzisieren. Am Ende 
kommst du dann noch mit der Forderung, dass es mit jeder Maske und jeder 
Shiftcount hocheffizient funktionieren soll, und zwar auch dann wenn 
nichts davon konstant ist. In dem Fall empfehle ich einen ARM an Stelle 
eines AVR - das können die nämlich sehr gut.

Andrers ausgedrückt: Je stärker sich die Bedingungen eingrenzen lassen, 
desto besser die Chancen.

[Jim M. (turboj)]

> Vielleicht hat ja noch jemand einen Geistesblitz?

Welche Optimierungsstufe ist eingeschaltet?

[André A. (nummer5)]

Jim Meba schrieb:
> Welche Optimierungsstufe ist eingeschaltet?

Ich hab Os und O3 getestet, macht keinen Unterschied.

A. K. schrieb:
> Du solltest vielleicht die Rahmenbedingungen etwas präzisieren.

Es sind alles Konstanten bis auf die Eingabevariable.


Es ist kein Problem das ganze per Hand zu schreiben (sind 5 
Berechnungen), ich war nur erstaunt, dass der Compiler das nicht selber 
macht obwohl die Optimierung sonst ganz gut funktioniert.
Ich dachte es gäbe irgendeinen mir unbekannten Grund dafür, aber so wie 
es aussieht liegts wohl am Zusammenspiel zwischen GCC und AVR.

Kann vielleicht jemand mein Beispiel mit einem anderen Compiler 
compilieren (z.B. IAR)? Mich würde interessieren, was dabei herauskommt.

[Rolf Magnus (Gast)]

André Althaus schrieb:
> Es sind alles Konstanten bis auf die Eingabevariable.

Aber Konstanten, die sich ändern?

André Althaus schrieb:
> Ja das klappt, aber dann müsste ich alle Rechnungen per Hand machen, da
> je nach benötigten Bits, andere Bytes benötigt werden.

[Johann L. (gjlayde)]

Momentan sehe ich nicht, wie man das Problem einfach in GCC lösen kann.

Auf C-Ebene geht folgender, hässliche Code:
 

static __inline__ __attribute__((always_inline))
uint8_t extract (const uint32_t val, const uint8_t pos, const uint8_t mask)
{
    uint8_t b;

    if (!__builtin_constant_p (pos))
    {
        return (val >> pos) & mask;
    }
    
    if ((mask << (pos & 7)) > UINT8_MAX)
    {
        uint16_t a = val >> (pos & ~7);
        b = a >> (pos & 7);
    }
    else
    {
        uint8_t a = val >> (pos & ~7);
        b = a >> (pos & 7);
    }
    
    return b & mask;
}

uint8_t test (uint32_t val)
{
    return extract (val, 18, 0x30) | extract (val, 4, 0xf);
}

 
4.7.2 erzeugt:
 

test:
  mov r18,r24   ;  32  movqi_insn/1  [length = 1]
  ldi r19,0   ;  33  movqi_insn/1  [length = 1]
  asr r19   ;  39  *ashrhi3_const/4  [length = 4]
  ror r18
  asr r19
  ror r18
  andi r18,48   ;  10  andhi3/3  [length = 2]
  clr r19
  mov r24,r22   ;  31  movqi_insn/1  [length = 1]
  swap r24   ;  34  *rotlqi3/4  [length = 1]
  andi r24,lo8(15)   ;  35  andqi3/2  [length = 1]
  or r24,r18   ;  19  iorqi3/1  [length = 1]
  ret   ;  38  return  [length = 1]

 
Für andere Bitwerte / Masken kann man extract() ebenfalls verwenden.

[Johann L. (gjlayde)]

...und falls das immer noch nicht reicht (und die Position zur 
Compilezeit bekannt ist), kann man extract von ober so schreiben:
 

static __inline__ __attribute__((always_inline))
uint8_t extract (const uint32_t val, const uint8_t pos, const uint8_t mask)
{
    uint8_t b;

    if ((mask << (pos & 7)) > UINT8_MAX)
    {
        uint16_t a = val >> (pos & ~7);
        b = a >> (pos & 7);
    }
    else
    {
        uint8_t a = val >> (pos & ~7);
        b = a >> (pos & 7);
    }
    asm ("" : "+r" (b));
    
    return b & mask;
}

 
Wird übersetzt zu:
 

test:
  lsr r24   ;  10  *lshrqi3/4  [length = 2]
  lsr r24
  swap r22   ;  37  *rotlqi3/4  [length = 1]
  andi r22,lo8(15)   ;  38  andqi3/2  [length = 1]
  andi r22,lo8(15)   ;  19  andqi3/2  [length = 1]
  andi r24,lo8(48)   ;  20  andqi3/2  [length = 1]
  or r24,r22   ;  26  iorqi3/1  [length = 1]
  ret   ;  41  return  [length = 1]

 
Bis auf das doppelte ANDI *,15 ist das optimal.

Wie man die Optimierung direkt in GCC macht ist mir aber nicht klar, 
vielleicht hat ja jemand ne Idee...

[Frank M. (ukw) (Moderator)]

André Althaus schrieb:
> Vielleicht hat ja noch jemand einen Geistesblitz?

Ich würde mir erstmal die Frage stellen, warum da mehrere numerische 
Werte in einer uint32_t-Variablen zusammengefasst wurden. Vermutlich nur 
aus Bequemlichkeit.

uint32_t ist auf einem 8-Bit-AVR absolut unhandlich und sollte möglichst 
nicht verwendet werden. Ich sehe da bis auf wenige Ausnahmen überhaupt 
keine Notwendigkeit dafür. Mein Ansatz wäre eine Aufsplittung der 
uint32_t-Variablen in die einzelnen numerischen Werte und Verwendung von 
passenden uint8_t bzw. uint16_t-Variablen.

Das Mitschleppen von mehreren Variablen ist zwar für den Programmierer 
etwas unhandlicher, aber wesentlich komfortabler für den Compiler.

[Falk B. (falk)]

@  A. K. (prx)

>Du solltest vielleicht die Rahmenbedingungen etwas präzisieren.

So langsam wird es dafür Zeit. Wer denkt schon an Netiquette, 
geschweige denn den gesunden Menschenverstand?

>Am Ende
>kommst du dann noch mit der Forderung, dass es mit jeder Maske und jeder
>Shiftcount hocheffizient funktionieren soll, und zwar auch dann wenn
>nichts davon konstant ist. In dem Fall empfehle ich einen ARM an Stelle
>eines AVR - das können die nämlich sehr gut.

Ich sehe schon wieder Kanonen und Spatzen vor meinem geistigen Auge.

Wie oft muss den diese Funktion ausgeführt werden? Welche Zeit darf sie 
maximal verbrauchen? Oder ist das eine Rechung, die nur ein paar mal 
vollkommen zeitunkritisch ausgeführt wird?

>Andrers ausgedrückt: Je stärker sich die Bedingungen eingrenzen lassen,
>desto besser die Chancen.

So in der Richtung. Man sollte immer erstmal ein paar Schritte zurück 
machen und die Frage zu stellen, was wirklich gebraucht wird und was nur 
Mittel zum Zweck ist.