mikrocontroller.net

Forum: Compiler & IDEs Bitshift schlecht implementiert?


Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

ich bin gerade dabei, ein Programm für einen ATmega644 mit dem GCC zu 
erstellen. Das geht auch nicht schlecht, der GCC produziert in den 
meisten Fällen ganz ordentlichen Code. Aber eben nur in den meisten 
Fällen. Was mir aufgefallen ist, ist, dass die Bitschieberei scheinbar 
nicht so toll implementiert ist...
Am extremsten ist das bei diesem Code:
void rf_send(const uint32_t address) {
  RDD_MOSI |= _BV(PIN_MOSI);
  rf_dir(RF_DEFCHANNEL, 0);
  _delay_us(5);
  rf_sendspi((uint8_t)(address >> 20));
  rf_sendspi((uint8_t)(address >> 12));
  rf_sendspi((uint8_t)(address >> 4));
  rf_sendspi((uint8_t)(address << 4) | (uint8_t)((RF_MyAddress >> 24) & 0x0F));
  rf_sendspi((uint8_t)(RF_MyAddress >> 16));
  rf_sendspi((uint8_t)(RF_MyAddress >> 8));
  rf_sendspi((uint8_t)RF_MyAddress);
  uint8_t i;
  for (i = 0; i < RF_LEN_DATA / 8; i++) {
    rf_sendspi(RF_Data_TX[i]);
  }
  RPO_TRWCE &= ~_BV(PIN_TRWCE);
  _delay_ms(1);
  RPO_TRWCE |= _BV(PIN_TRWCE);
  rf_dir(RF_DEFCHANNEL, 1);
}
RF_MyAddress ist ebenfalls ein uint32_t. Zugegeben, diese Schieberei ist 
nicht ganz ideal, da ich ein Offset von 4 Bit ausgleichen muss (address 
und RF_MyAddress beinhalten jeweils 28 Bit Daten). Aber was der GCC da 
produziert (Optimierung -Os) ist doch etwas krass:
@00000259: rf_send
92:       void rf_send(const uint32_t address) {
+00000259:   92EF        PUSH    R14              Push register on stack
+0000025A:   92FF        PUSH    R15              Push register on stack
+0000025B:   930F        PUSH    R16              Push register on stack
+0000025C:   931F        PUSH    R17              Push register on stack
+0000025D:   93CF        PUSH    R28              Push register on stack
+0000025E:   93DF        PUSH    R29              Push register on stack
+0000025F:   017B        MOVW    R14,R22          Copy register pair
+00000260:   018C        MOVW    R16,R24          Copy register pair
93:         RDD_MOSI |= _BV(PIN_MOSI);
+00000261:   9A25        SBI     0x04,5           Set bit in I/O register
94:         rf_dir(RF_DEFCHANNEL, 0);
+00000262:   E060        LDI     R22,0x00         Load immediate
+00000263:   E186        LDI     R24,0x16         Load immediate
+00000264:   940E01F9    CALL    0x000001F9       Call subroutine
+00000266:   E08D        LDI     R24,0x0D         Load immediate
+00000267:   958A        DEC     R24              Decrement
+00000268:   F7F1        BRNE    PC-0x01          Branch if not equal
96:         rf_sendspi((uint8_t)(address >> 20));
+00000269:   01D8        MOVW    R26,R16          Copy register pair
+0000026A:   01C7        MOVW    R24,R14          Copy register pair
+0000026B:   E124        LDI     R18,0x14         Load immediate
+0000026C:   95B6        LSR     R27              Logical shift right
+0000026D:   95A7        ROR     R26              Rotate right through carry
+0000026E:   9597        ROR     R25              Rotate right through carry
+0000026F:   9587        ROR     R24              Rotate right through carry
+00000270:   952A        DEC     R18              Decrement
+00000271:   F7D1        BRNE    PC-0x05          Branch if not equal
+00000272:   940E01EE    CALL    0x000001EE       Call subroutine
97:         rf_sendspi((uint8_t)(address >> 12));
+00000274:   01D8        MOVW    R26,R16          Copy register pair
+00000275:   01C7        MOVW    R24,R14          Copy register pair
+00000276:   E0FC        LDI     R31,0x0C         Load immediate
+00000277:   95B6        LSR     R27              Logical shift right
+00000278:   95A7        ROR     R26              Rotate right through carry
+00000279:   9597        ROR     R25              Rotate right through carry
+0000027A:   9587        ROR     R24              Rotate right through carry
+0000027B:   95FA        DEC     R31              Decrement
+0000027C:   F7D1        BRNE    PC-0x05          Branch if not equal
+0000027D:   940E01EE    CALL    0x000001EE       Call subroutine
98:         rf_sendspi((uint8_t)(address >> 4));
+0000027F:   01D8        MOVW    R26,R16          Copy register pair
+00000280:   01C7        MOVW    R24,R14          Copy register pair
+00000281:   E0E4        LDI     R30,0x04         Load immediate
+00000282:   95B6        LSR     R27              Logical shift right
+00000283:   95A7        ROR     R26              Rotate right through carry
+00000284:   9597        ROR     R25              Rotate right through carry
+00000285:   9587        ROR     R24              Rotate right through carry
+00000286:   95EA        DEC     R30              Decrement
+00000287:   F7D1        BRNE    PC-0x05          Branch if not equal
+00000288:   940E01EE    CALL    0x000001EE       Call subroutine
99:         rf_sendspi((uint8_t)(address << 4) | (uint8_t)((RF_MyAddress >> 24) & 0x0F));
+0000028A:   0CEE        LSL     R14              Logical Shift Left
+0000028B:   0CEE        LSL     R14              Logical Shift Left
+0000028C:   0CEE        LSL     R14              Logical Shift Left
+0000028D:   0CEE        LSL     R14              Logical Shift Left
+0000028E:   9180037E    LDS     R24,0x037E       Load direct from data space
+00000290:   9190037F    LDS     R25,0x037F       Load direct from data space
+00000292:   91A00380    LDS     R26,0x0380       Load direct from data space
+00000294:   91B00381    LDS     R27,0x0381       Load direct from data space
+00000296:   2F8B        MOV     R24,R27          Copy register
+00000297:   2799        CLR     R25              Clear Register
+00000298:   27AA        CLR     R26              Clear Register
+00000299:   27BB        CLR     R27              Clear Register
+0000029A:   708F        ANDI    R24,0x0F         Logical AND with immediate
+0000029B:   298E        OR      R24,R14          Logical OR
+0000029C:   940E01EE    CALL    0x000001EE       Call subroutine
100:        rf_sendspi((uint8_t)(RF_MyAddress >> 16));
+0000029E:   91800380    LDS     R24,0x0380       Load direct from data space
+000002A0:   940E01EE    CALL    0x000001EE       Call subroutine
101:        rf_sendspi((uint8_t)(RF_MyAddress >> 8));
+000002A2:   9180037E    LDS     R24,0x037E       Load direct from data space
+000002A4:   9190037F    LDS     R25,0x037F       Load direct from data space
+000002A6:   91A00380    LDS     R26,0x0380       Load direct from data space
+000002A8:   91B00381    LDS     R27,0x0381       Load direct from data space
+000002AA:   2F89        MOV     R24,R25          Copy register
+000002AB:   2F9A        MOV     R25,R26          Copy register
+000002AC:   2FAB        MOV     R26,R27          Copy register
+000002AD:   27BB        CLR     R27              Clear Register
+000002AE:   940E01EE    CALL    0x000001EE       Call subroutine
102:        rf_sendspi((uint8_t)RF_MyAddress);
+000002B0:   9180037E    LDS     R24,0x037E       Load direct from data space
+000002B2:   940E01EE    CALL    0x000001EE       Call subroutine
+000002B4:   E6C8        LDI     R28,0x68         Load immediate
+000002B5:   E0D3        LDI     R29,0x03         Load immediate
105:          rf_sendspi(RF_Data_TX[i]);
+000002B6:   9189        LD      R24,Y+           Load indirect and postincrement
+000002B7:   940E01EE    CALL    0x000001EE       Call subroutine
104:        for (i = 0; i < RF_LEN_DATA / 8; i++) {
+000002B9:   E083        LDI     R24,0x03         Load immediate
+000002BA:   37CE        CPI     R28,0x7E         Compare with immediate
+000002BB:   07D8        CPC     R29,R24          Compare with carry
+000002BC:   F7C9        BRNE    PC-0x06          Branch if not equal
107:        RPO_TRWCE &= ~_BV(PIN_TRWCE);
+000002BD:   9843        CBI     0x08,3           Clear bit in I/O register
---- c:\programme\WinAVR\avr\include\util\delay_basic.h -------------------------------------------
105:        __asm__ volatile (
+000002BE:   ED80        LDI     R24,0xD0         Load immediate
+000002BF:   E097        LDI     R25,0x07         Load immediate
+000002C0:   9701        SBIW    R24,0x01         Subtract immediate from word
+000002C1:   F7F1        BRNE    PC-0x01          Branch if not equal
---- src\rf.c -------------------------------------------------------------------------------------
109:        RPO_TRWCE |= _BV(PIN_TRWCE);
+000002C2:   9A43        SBI     0x08,3           Set bit in I/O register
110:        rf_dir(RF_DEFCHANNEL, 1);
+000002C3:   E061        LDI     R22,0x01         Load immediate
+000002C4:   E186        LDI     R24,0x16         Load immediate
+000002C5:   940E01F9    CALL    0x000001F9       Call subroutine
+000002C7:   91DF        POP     R29              Pop register from stack
+000002C8:   91CF        POP     R28              Pop register from stack
+000002C9:   911F        POP     R17              Pop register from stack
+000002CA:   910F        POP     R16              Pop register from stack
+000002CB:   90FF        POP     R15              Pop register from stack
+000002CC:   90EF        POP     R14              Pop register from stack
+000002CD:   9508        RET                      Subroutine return

Ganz toll finde ich da besonders die Schleife bei der Verschiebung um 20 
Bit, die durch den folgenden Cast ja ohne Weiteres entfallen könnte, 
sowie solche Spielereien:
+0000028E:   9180037E    LDS     R24,0x037E       Load direct from data space
+00000290:   9190037F    LDS     R25,0x037F       Load direct from data space
+00000292:   91A00380    LDS     R26,0x0380       Load direct from data space
+00000294:   91B00381    LDS     R27,0x0381       Load direct from data space
+00000296:   2F8B        MOV     R24,R27          Copy register
+00000297:   2799        CLR     R25              Clear Register
+00000298:   27AA        CLR     R26              Clear Register
+00000299:   27BB        CLR     R27              Clear Register

Ahja. Man lade vier Register um sie dann auch gleich wieder zu 
überschreiben. Ganz toll.

Ich will ja nicht sagen, dass der GCC schlecht optimiert, noch verlange 
ich, dass jeder Code bis in's letzte Detail ausgefeilt ist. Doch bei -Os 
dürfte man doch eigentlich schon erwarten, dass wenigstens solche 
offensichtlichen Ehrenrunden vermieden werden. Die schlagen sich ja dann 
sowohl auf der Codegrösse, als auch auf der Ausführungszeit nieder...

Also, zum Schluss auch noch meine Frage:
Wie könnte ich den Code umschreiben, dass er besser optimiert wird? Oder 
gibt es nur die Möglichkeit, das ganze Zeug direkt in Assembler zu 
schreiben? Letzteres möchte ich eigentlich vermeiden, nicht weil ich ASM 
nicht mag, sondern weil das schlussendlich wohl mehr Probleme produziert 
als löst...


Danke schonmal für alle (konstruktiven) Antworten und freundliche 
Grüsse,
Philipp

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
GCC lebt davon, dass er von Leuten verbessert wird. Mach es! Du hast 
keinen Anspruch darauf, dass andere es tun.

Ausserdem kannst du der Optimierung auch im Quellecode nachhelfen. Statt
  rf_sendspi((uint8_t)(address >> 20));
  rf_sendspi((uint8_t)(address >> 12));
schreibst du einfach
  rf_sendspi((uint16_t)(address >> 16) >> 4);
  rf_sendspi((uint16_t)(address >> 8) >> 4);

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas Kaiser wrote:
> GCC lebt davon, dass er von Leuten verbessert wird. Mach es! Du hast
> keinen Anspruch darauf, dass andere es tun.

Ich wusste doch, dass das kommt ;)
Würde ich gerne tun, leider habe ich vom Compilerbau wenig bis keine 
Ahnung. Wenn es so trivial wäre, wäre es auch bestimmt schon gemacht.

> Ausserdem kannst du der Optimierung auch im Quellecode nachhelfen. Statt
>
>   rf_sendspi((uint8_t)(address >> 20));
>   rf_sendspi((uint8_t)(address >> 12));
> 
> schreibst du einfach
>
>   rf_sendspi((uint16_t)(address >> 16) >> 4);
>   rf_sendspi((uint16_t)(address >> 8) >> 4);
> 

Ja, genau sowas habe ich gesucht. Danke! Mal sehn, was er draus macht.

Autor: Benedikt K. (benedikt) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Probier mal -O1 oder - O2. Die erzeugen nach meiner Erfahrung einen 
kleineren und schnelleren Code.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Probier mal -O1 oder - O2. Die erzeugen nach meiner Erfahrung einen
> kleineren und schnelleren Code.

Bringt hier nichts. Der Compiler müsste mehr Lösungensansätze für 32bit 
Shifts implementieren als er tut. Also beispielsweise Shifts in 2 Stufen 
realisieren, die erste mit n*8 durch Byteversatz, dann den Rest. Bei 
16bit macht er das, bei 32bit offenbar nicht.

Sowas ist entweder drin und wirkt immer, oder es ist nicht drin. 
Optimierung hat darauf meist wenig Einfluss.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Wenn es so trivial wäre, wäre es auch bestimmt schon gemacht.

So schwierig dürfte es tatsächlich nicht sein. Jedenfalls nicht die 
reine Shiftoptimierung, die ich grad skizziert habe. Dazu muss man nur 
entsprechenden Code für die betreffenden Shiftoperationen einbauen.

Erheblich schwieriger ist es, Erkenntnisse, die von der Reihenfolge der 
Operationen her später gewonnen werden, in vorherige Operationen 
zurückwachsen zu lassen. Also zu erkennen, dass nur 8 Bits vom Ergebnis 
gebraucht werden, und dies nicht erst danach, sondern bereits in der 
Shiftoperation selbst zu berücksichtigen.

Autor: Stefan Salewski (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>void rf_send(const uint32_t address) {

Könnte einer der C-Gurus vielleicht mal kurz erklären was hier das 
Attribut "const" bewirkt bzw. warum es notwendig ist? Ich kenne "const" 
eher in Verbindung mit Zeigern. Auf den ersten Blick würde ich denken, 
address ist ein konstanter 32-bit-Wert, d.h. dass nur Aufrufe wie 
rf_send(1), rf_send(2) usw. erlaubt sein sollen. Ist das gemeint?

Gruß

Stefan Salewski

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Andreas:

Die Änderung hat schon einiges bewirkt, vielen Dank!
96:         rf_sendspi((uint16_t)(address >> 16) >> 4);
+00000269:   01C8        MOVW    R24,R16          Copy register pair
+0000026A:   27AA        CLR     R26              Clear Register
+0000026B:   27BB        CLR     R27              Clear Register
+0000026C:   E0B4        LDI     R27,0x04         Load immediate
+0000026D:   9596        LSR     R25              Logical shift right
+0000026E:   9587        ROR     R24              Rotate right through carry
+0000026F:   95BA        DEC     R27              Decrement
+00000270:   F7E1        BRNE    PC-0x03          Branch if not equal
+00000271:   940E01EE    CALL    0x000001EE       Call subroutine
97:         rf_sendspi((uint16_t)(address >> 8) >> 4);
+00000273:   27BB        CLR     R27              Clear Register
+00000274:   2FA1        MOV     R26,R17          Copy register
+00000275:   2F90        MOV     R25,R16          Copy register
+00000276:   2D8F        MOV     R24,R15          Copy register
+00000277:   E0F4        LDI     R31,0x04         Load immediate
+00000278:   9596        LSR     R25              Logical shift right
+00000279:   9587        ROR     R24              Rotate right through carry
+0000027A:   95FA        DEC     R31              Decrement
+0000027B:   F7E1        BRNE    PC-0x03          Branch if not equal
+0000027C:   940E01EE    CALL    0x000001EE       Call subroutine
98:         rf_sendspi((uint8_t)(address >> 4));
+0000027E:   01D8        MOVW    R26,R16          Copy register pair
+0000027F:   01C7        MOVW    R24,R14          Copy register pair
+00000280:   E0E4        LDI     R30,0x04         Load immediate
+00000281:   95B6        LSR     R27              Logical shift right
+00000282:   95A7        ROR     R26              Rotate right through carry
+00000283:   9597        ROR     R25              Rotate right through carry
+00000284:   9587        ROR     R24              Rotate right through carry
+00000285:   95EA        DEC     R30              Decrement
+00000286:   F7D1        BRNE    PC-0x05          Branch if not equal
+00000287:   940E01EE    CALL    0x000001EE       Call subroutine

Ist noch nicht ideal, aber schon ein grosses Stück besser als mit den 20 
Schleifendurchläufen :)


EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit 
liessen sich die Verschiebungen um 4 Bit wesentlich effizienter 
gestalten.

EDIT2: O1 und O2 machen unwesentlich grösseren Code, optimiert wird aber 
leider nicht besser.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wer sich dran versuchen will: In gcc\config\avr\avr.c sind dafür die 
Funktionen a/lshrqi3_out (8bit), -shrhi3_out (16bit) und -shrsi3_out 
(32bit) zuständig. Bei 8- und 16bit sind die meisten Shiftcounts 
handoptimiert, bei 32bit nur 8,16,24,31.

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Stefan:

"const" bewirkt hier, dass der Parameter in der Funktion nicht verändert 
werden kann. Das kann u.U. dem Compiler etwas bei der Optimierung 
helfen. Und es schliesst Fehlerquellen aus.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit
> liessen sich die Verschiebungen um 4 Bit wesentlich effizienter
> gestalten.

Doch er kennt ihn. An genau dieser Stelle greift nun doch die vom 
Benedikt skizzierte Optimierungseinstellung, weil die Swap-Variante 
deutlich länger ist:
  mov r25,r17
  mov r24,r16
  clr r26
  clr r27
  swap r25
  swap r24
  andi r24,0x0f
  eor r24,r25
  andi r25,0x0f
  eor r24,r25

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zugriffe auf 32Bit
typedef union {
  uint16_t word;
  struct {
    uint8_t a,b;
  };
} uint16_t_u;

typedef union {
  uint32_t dword;
  struct {
    uint8_t a,b,c,d;
  };
} uint32_t_u;

typedef union {
  uint32_t dword;
  struct {
    uint16_t a,b;
  };
} uint32_t_s;

#define L8(v)    (((uint16_t_u)v).a)
#define H8(v)    (((uint16_t_u)v).b)

#define L16(v)   (((uint32_t_s)v).a)
#define H16(v)   (((uint32_t_s)v).b)

#define LL8(v)   (((uint32_t_u)v).a)
#define LH8(v)   (((uint32_t_u)v).b)
#define HL8(v)   (((uint32_t_u)v).c)
#define HH8(v)   (((uint32_t_u)v).d)

also dann so
  rf_sendspi(HL8(RF_MyAddress));
  rf_sendspi(LH8(RF_MyAddress));
  rf_sendspi(LL8(RF_MyAddress));

das produziert den besten code unter gcc.

Dann Linksshift auf einem ATMega mit einem Shift größer als 1 immer als 
Multplikation machen, das ist im Durchschnitt schneller und kompakter.

Statt
  X = Y << i;

// also
  
  X = Y * PowerOf2[i]; 

Gruß Hagen

Autor: Stefan Salewski (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Philipp Burch schrieb:

>"const" bewirkt hier, dass der Parameter in der Funktion nicht verändert
>werden kann. Das kann u.U. dem Compiler etwas bei der Optimierung
>helfen. Und es schliesst Fehlerquellen aus.

Ah ja, danke. Hatte ich wohl auch irgendwann mal gelesen aber wieder 
vergessen!

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Dann Linksshift auf einem ATMega mit einem Shift größer als 1 immer als
> Multplikation machen, das ist im Durchschnitt schneller und kompakter.

Bei 32bit Operationen und nicht konstantem Faktor? Na wenn du meinst...

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
probiers einfach aus, fertig.

Eine MUL benötigt 2 Takte, ein Links Shift des gleichen Bytes um I Bits 
benötigt 2 * i Takte minimal, ohne den Branch zu berücksichtigen.

Gilt logischerweise nur für Megas die eine HW-MUL unterstützen.
Normalerweise setzt man solche Optimierungen im Compiler voraus, sie 
sind Standard. Klar das dies für GCC nicht gelten kann, lebt dieser von 
der Eigenintiative ambtionierter Programmierer.

Ich denke das keiner hier GCC oder deren Entwickler angreifen möchte, 
esw geht einfach nur darum zu lernen was der GCC wann macht und was man 
als klein Hausmittelt so in seiner Apotheke hat um Kleinigkeiten besser 
machen zu können. Es ist wohl auch klar das man mit solchen Tricks die 
Kompatibilität des C Source aufhebt, auch dies ist logisch. (Nur um den 
vielen gutgemeinten Ratschlägen die auf solche Threads folgen 
vorzubeugen)

Gruß Hagen

Autor: Benedikt K. (benedikt) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Andreas Kaiser wrote:
>> EDIT: btw, kann es sein, dass der GCC den swap-Befehl nicht kennt? Damit
>> liessen sich die Verschiebungen um 4 Bit wesentlich effizienter
>> gestalten.
>
> Doch er kennt ihn. An genau dieser Stelle greift nun doch die vom
> Benedikt skizzierte Optimierungseinstellung, weil die Swap-Variante
> deutlich länger ist:

Genau aus diesem Grund verwende ich immer O1 oder O2 und nie Os. Denn 
der Compiler versucht bei Os zwanghaft den kleinsten Code zu erzeugen. 
Das sind oftmals dumme Schleifen (wie auch hier), oder bei y=x/128 wird 
kein Shift verwendet, sondern die Divisionsroutine, da der Aufruf kürzer 
ist (vorausgesetzt die Routine wird wo anderst sowiso benötigt). Die 
Geschwindigkeitssteigerung liegt je nach Code bei bis zu >100%.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, stimmt auch bei 32bit, ist aber abhängig von der Shiftcount. Bei 
kleiner Shiftcount ist der Shift schneller als die Laufzeitfunktion zur 
Multiplikation.

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Hagen:

WTF, das ist wohl die ultimative Optimierung (Bitfelder und 
Multiplikation) :)
96:         rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);
+0000026A:   E06F        LDI     R22,0x0F         Load immediate
+0000026B:   2ED6        MOV     R13,R22          Copy register
+0000026C:   9ED1        MUL     R13,R17          Multiply unsigned
+0000026D:   2D80        MOV     R24,R0           Copy register
+0000026E:   2411        CLR     R1               Clear Register
+0000026F:   2F90        MOV     R25,R16          Copy register
+00000270:   9592        SWAP    R25              Swap nibbles
+00000271:   709F        ANDI    R25,0x0F         Logical AND with immediate
+00000272:   2B89        OR      R24,R25          Logical OR
+00000273:   940E01EE    CALL    0x000001EE       Call subroutine
97:         rf_sendspi(HL8(address) * 0x0f | LH8(address) >> 4);
+00000275:   9ED0        MUL     R13,R16          Multiply unsigned
+00000276:   2D80        MOV     R24,R0           Copy register
+00000277:   2411        CLR     R1               Clear Register
+00000278:   2D9F        MOV     R25,R15          Copy register
+00000279:   9592        SWAP    R25              Swap nibbles
+0000027A:   709F        ANDI    R25,0x0F         Logical AND with immediate
+0000027B:   2B89        OR      R24,R25          Logical OR
+0000027C:   940E01EE    CALL    0x000001EE       Call subroutine
98:         rf_sendspi(LH8(address) * 0x0f | LL8(address) >> 4);
+0000027E:   9CDF        MUL     R13,R15          Multiply unsigned
+0000027F:   2D80        MOV     R24,R0           Copy register
+00000280:   2411        CLR     R1               Clear Register
+00000281:   2D9E        MOV     R25,R14          Copy register
+00000282:   9592        SWAP    R25              Swap nibbles
+00000283:   709F        ANDI    R25,0x0F         Logical AND with immediate
+00000284:   2B89        OR      R24,R25          Logical OR
+00000285:   940E01EE    CALL    0x000001EE       Call subroutine
99:         rf_sendspi((LL8(address) * 0x0f) | (HH8(RF_MyAddress) & 0x0f));
+00000287:   9CDE        MUL     R13,R14          Multiply unsigned
+00000288:   2D20        MOV     R18,R0           Copy register
+00000289:   2411        CLR     R1               Clear Register
+0000028A:   9180037E    LDS     R24,0x037E       Load direct from data space
+0000028C:   9190037F    LDS     R25,0x037F       Load direct from data space
+0000028E:   91A00380    LDS     R26,0x0380       Load direct from data space
+00000290:   91B00381    LDS     R27,0x0381       Load direct from data space
+00000292:   2F8B        MOV     R24,R27          Copy register
+00000293:   708F        ANDI    R24,0x0F         Logical AND with immediate
+00000294:   2B82        OR      R24,R18          Logical OR
+00000295:   940E01EE    CALL    0x000001EE       Call subroutine
100:        rf_sendspi(HL8(RF_MyAddress));
+00000297:   91800380    LDS     R24,0x0380       Load direct from data space
+00000299:   940E01EE    CALL    0x000001EE       Call subroutine
101:        rf_sendspi(LH8(RF_MyAddress));
+0000029B:   9180037F    LDS     R24,0x037F       Load direct from data space
+0000029D:   940E01EE    CALL    0x000001EE       Call subroutine
102:        rf_sendspi(LL8(RF_MyAddress));
+0000029F:   9180037E    LDS     R24,0x037E       Load direct from data space
+000002A1:   940E01EE    CALL    0x000001EE       Call subroutine
+000002A3:   E6C8        LDI     R28,0x68         Load immediate
+000002A4:   E0D3        LDI     R29,0x03         Load immediate

Der Code wird zwar absolut hässlich, aber das soll's mir an der Stelle 
wert sein. Hab' vielen Dank!

@Benedikt:

Leider bringt O2 auch an der Stelle nicht die gewünschte Verbesserung, 
da bereits keine Schleifen mehr existieren, die noch wegoptimiert werden 
könnten...


Und keine Sorge, ich habe nicht vor, den Code mit einem anderen Compiler 
zu kompilieren, daher kann ich schon solche "Hacks" machen.


EDIT:
Und hier noch die Variante mit einem "normalen" Shift:
96:         rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);
+0000026A:   2F81        MOV     R24,R17          Copy register
+0000026B:   9582        SWAP    R24              Swap nibbles
+0000026C:   7F80        ANDI    R24,0xF0         Logical AND with immediate
+0000026D:   2F90        MOV     R25,R16          Copy register
+0000026E:   9592        SWAP    R25              Swap nibbles
+0000026F:   709F        ANDI    R25,0x0F         Logical AND with immediate
+00000270:   2B89        OR      R24,R25          Logical OR
+00000271:   940E01EE    CALL    0x000001EE       Call subroutine

Hat jemand Lust, die Zyklen zusammenzuzählen? ;D

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);

ist aber nicht identisch zu

rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);

du multiplizierst mit 0x0F = 15 statt mit 0x10 = 16 = 2^4.

In diesem Falle ist 2. Lösung aber effizienter !

Gruß Hagen

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ok, stimmt auch bei 32bit, ist aber abhängig von der Shiftcount. Bei
>kleiner Shiftcount ist der Shift schneller als die Laufzeitfunktion zur
>Multiplikation.

Laufzeitfunktion ? Einfache Miltiplikationen, zb. ein Byte * Byte werden 
auf einem Mega der eine HW-MUL hat direkt umgesetzt. Da wird keine 
Laufzeitbiliothek benötigt. Bei der Division ist das was anderes.

Das Beispiel aus diesem Thread arbeitet nicht mit 32Bit Zahlen sondern 
nur mit Bytes.

Normale Shifts die nicht 8,16,24 sind werden als simple Schleifen 
gebaut. Ein Byte kann maximal um +7 Bits geschoben werden. Da der GCC 
den Shiftwert nicht optimiert wird bei einem Variablen Shift im 
Durchschnitt der Wert 3 vorkommen, ergo 3*2 = 6 Takte. Im Gegensatz zu 2 
Takten ohne Branches bei der MUL.

Auch bei den Shift mit 8,16,24 arbeitet der GCC ineffizient. In diesem 
Falle fügt er unnötige CLR und MOV der selben Register ein.
Das ist aber nicht nur GCC spezifisch auch der Keil hat solche Sachen 
drauf.

Ok ich gebe zu das sind jetzt schon Tricks die ziemlich am Rande der 
sauberen Programmierung stehen und bei denen man sich die Frage stellen 
muß ob sie wirkich notwendig sind. Aber es zu wissen, das man noch was 
rausholen kann und den Compiler besser vesteht, hat auch seinen Wert.

Gruß Hagen

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Laufzeitfunktion ?

Ich sprach ausdrücklich von 32bit Operationen. Da steckt zwar auch der 
MUL-Befehl dahinter, aber halt ein paar mehr davon.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, aber auch dann wäre die MUL schneller. Zb. ein 16 Bit um 2^5 
shifted. Als normale Schleife sind das 3 * 5 Takte, 3 Takte weil ja 2 
Bytes shift + 1 Takt Schleife. Per MUL würden 3 MULs ausreichen, also 6 
Takte statt 15.

Je größer der Datentypen je höher der Aufwand für die Schleife wie auch 
MUL, aber das Ratio veräöndert sich immer mehr zu Gunsten der MUL.

Gruß Hagen

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagen Re wrote:
> rf_sendspi(HH8(address) * 0x0f | HL8(address) >> 4);
>
> ist aber nicht identisch zu
>
> rf_sendspi(HH8(address) << 4 | HL8(address) >> 4);
>
> du multiplizierst mit 0x0F = 15 statt mit 0x10 = 16 = 2^4.

Argh, Schande über mein Haupt. Du hast natürlich recht.

> In diesem Falle ist 2. Lösung aber effizienter !
>
> Gruß Hagen



Erstmal ein grosses Dankeschön für eure Vorschläge, so ist es jetzt kein 
Problem mehr. Ob eine Operation nun drei Takte länger dauert oder nicht 
ist mir ja eigentlich auch egal, aber wenn halt eine Schiebeoperation 
dermassen ineffizient erzeugt wird, dann bin ich schon froh um solche 
Optimierungen.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hagen Re wrote:

> Ok, aber auch dann wäre die MUL schneller.

Nochmal: 32 Bits. Zweiunddreissig. Nicht 8 Bits, nicht 16 Bit. Der 
Multiplikationsbefehl multipliziert aber nur 8x8=>16.

Die Libfcn enthält folglich 10 MULs und noch ein paar mehr ADD/ADCs, 
insgesamt ~48 Takte plus Overhead weil Funktionsaufruf statt 
Inline-Code. Die Schleife braucht 7 Takte/Iter, d.h. ab ungefähr n=8 
dürfte die Multiplikation im Vorteil sein.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hm, lass uns mal streiten ;)

eine 32Bit  8Bit MUL benötigt 4 8x8Bit MUL + 1 ADD + 2 ADC, nicht mehr 
und nicht weniger.

4*2 + 3 Takte also  macht 11 Takte, vorrausgesetzt wir vernachlässigen 
mal das Laden der Register, da dies bei beiden Methoden mit festen 
Overhead einhergeht.

Ein Shift über 4 Bytes benötigt 4 Takte + 1 Takt Spungbefehlt, macht 5 
Takte um 1 Bit zu schieben.

1 Bit = 5 Takte
2 Bit = 10 Takte
31 Bit = 155 Takte

5+10+...155 / 31 = 80 Takte im Durchschnitt. Also wenn man vorraussetzt 
das gleichverteilt im Bereich von 1 bis 31 Bits ein 32 Bit Wert links 
geschoben wird so belaufen sich die Kosten auf

Shiftloop = 80 Takte im Durchschnitt
MUL Methode = konstante 11 Takte

Na das nenn ich mal ein ordentliches Ratio, oder ?

Klar, wenn man C Source voraussetz und die auf Univeralität 
programmierte MUL Methode der Standardlib die nicht nur 32x8 Bit sondern 
auch 32x16 und 32x32 rechnen kann, dann sind das 48 Takte. Aber auch das 
ist besser als die 80 Takte mit Loops.

Wo ist jetzt mein Rechenfehler ?

Gruß Hagen

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Wo ist jetzt mein Rechenfehler ?

Du hast für die Bitschieberei zuwenig Takte veranschlagt ;-)
Ein branch-Befehl braucht zwei Takte, wenn er springt. Macht also 6 
Takte pro geschobenem Bit, nicht 5. Beim letzten Durchlauf wird zwar 
nicht gesprungen, was einen Takt spart, aber den braucht man dafür dann 
zum Initialisieren des Schleifenzählers.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bis auf den Sprung nirgends. Jetzt sind wir beisammen. Ich schrieb, auf 
Basis der Libfunktion, dass kleine Shiftcounts drunter liegen. Du, dass 
die optimale aber nirgend realisierte Multiplikation ebenso wie die 
mittlere angenommene Shiftcount drüber liegen. Kein Widerspruch, stimmt 
beides.

Wenn wir weiter streiten wollen, dann allenfalls über die angenommene 
Gleichverteilung bei den Shiftcounts ;-).

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
;)

Ok, das mit dem Branch stimmt. Und bei der MUL Methode müssen wir auf 
Grund der Eigenheiten das der AVR immer über Register r1:r0 geht wohl 
auch noch par Takte hinzurechnen, für die MOVW Opcodes, falls wir mehr 
als 8 Bit schieben wollen.

Auf alle Fälle benutze ich den MUL Trick immer dann wenn ich zb. in 
meinen Grafik Libraries oä. per Inline Assembler arbeite. Dieser Schritt 
ist eh kontraproduktiv aus Sicht der Portierbarkeit, also kann man auch 
solche Tricks da anwenden. Gerade bei Ausgabe von Bitmapfonts oder 
kodierten Bitmaps benötigt man oft Shifts. Als erstes baue ich die 
Datenformate immer so das ich mit Links Shifts auskomme statt mit Rechts 
Shifts. Dann kann ich später für die ATMega's das per MULs optimieren. 
Das macht dann schon einen großen Unterschied in der Performance aus, 
wenn zb. ein Fontzeichen 14x12 Pixel hat und pro Pixel shifted werden 
muß.

Oder bei sehr zeitkritischen ISRs. Dort ist es wünschenswert das die ISR 
sehr schnell arbeitet aber noch viel wichtiger das sie mit konstanten 
Taktanzahlen auskommt. Dh. die ISR soll immer die gleiche Taktanzahl 
besitzen um damit im Gesamtsystem besser berechnebar zu sein. Und die 
MUL Methode benötigt immer die gleiche Taktanzahl unabhängig wieviele 
Bits geschoben werden. Die Loop Methode logischerweise nicht.

Gruß Hagen

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da ist mir doch gleich noch eine Ungereimtheit aufgefallen:
121:          if (RPI_MISO & _BV(PIN_MISO)) *s_address |= (1UL << 24);
+000002CF:   9B1E        SBIS    0x03,6           Skip if bit in I/O register set
+000002D0:   C008        RJMP    PC+0x0009        Relative jump
+000002D1:   E040        LDI     R20,0x00         Load immediate
+000002D2:   E050        LDI     R21,0x00         Load immediate
+000002D3:   E060        LDI     R22,0x00         Load immediate
+000002D4:   E071        LDI     R23,0x01         Load immediate
+000002D5:   2AE4        OR      R14,R20          Logical OR
+000002D6:   2AF5        OR      R15,R21          Logical OR
+000002D7:   2B06        OR      R16,R22          Logical OR
+000002D8:   2B17        OR      R17,R23          Logical OR
+000002D9:   2F89        MOV     R24,R25          Copy register
+000002DA:   958A        DEC     R24              Decrement
+000002DB:   F7F1        BRNE    PC-0x01          Branch if not equal
Kann mir jemand erklären, was die Schleife dort am Ende soll? R25 
beinhaltet den Wert 2. Soll das eine etwas andere Variante darstellen um 
ein Register zu nullen? Warteschleife oder sowas hat's nicht in der 
Nähe.

EDIT: Und gleich nochwas: Was ist das Problem, wenn ich die Zeile so 
abändere?
if (RPI_MISO & _BV(PIN_MISO)) HH8(*s_address) |= 0x01;
Da haut mir der Compiler den Fehler "error: invalid lvalue in 
assignment" um die Ohren...

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oha, Kommando zurück. In der nächsten Zeile steht ja _delay_us(1) ich 
Idiot... Damit hat sich das Problem wohl erledigt. Warum aber die zweite 
Möglichkeit mit HH8() nicht funktioniert ist mir immer noch nicht ganz 
klar...

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi

und was verbirgt sich hinter HH8()?

Matthias

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Siehe den Beitrag von Hagen etwas weiter oben: 
Beitrag "Re: Bitshift schlecht implementiert?"

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Niemand eine Idee, warum das nicht geht? Sind die Elemente einer Union 
schreibgeschützt oder so? Kaum, oder?
Ausserdem motzt er ja den lvalue an und da kommt doch eigentlich nur 
HH8(*s_address) rechts vom '=', sowie 0x01 in Frage. Was soll daran 
falsch sein?

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.