swap in C Vs. Asm

asm("blubb bla, lall");

(inline) asm ist hier gar nicht notwendig:

entweder

1

unsigned char __builtin_avr_swap (unsigned char)

oder

1

unsigned char __builtin_avr_insert_bits (unsigned long map, unsigned char bits, unsigned char val)

konkret:

1

__builtin_avr_insert_bits(0x32107654, Blah, 0)

Quelle: 
http://gcc.gnu.org/onlinedocs/gcc/AVR-Built_002din-Functions.html

(ich liebe die zweite Variante!)

Hast Du denn schon mal probiert, was bei dem C-Code ganz oben rauskommt? 
Normalerweise ist der Compiler so schlau, dass er den SWAP-Befehl nutzt, 
wenn es möglich ist.

Bastelboy schrieb:
> Swap niblles würde ich in C so schreiben:

Dann machs doch.

Erst wenn Du diesen Code zich tausende male / s brauchst, lohnt sich 
über Optimieren vielleicht nachzudenken.

Bastelboy schrieb:
> Swap niblles würde ich in C so schreiben:
> Bla = ((Bla >> 4) and 0x0F) | (Bla << 4) and 0xF0);
> Wie kann ich den (Attiny) GCC dazu bringen den ASM-Befehl SWAP zu

Indem du die beiden "and" durch "&" ersetzt und dafür sorgst, dass der 
GCC mindestens die Version 4.4 hat.

c-hater schrieb:
> Aber nein, er
> fordert vom Programmierer, daß DER weiß, daß er noch ein "inline" vor
> die Funktion zu schreiben hat, wenn die Sache nicht effizienzmäßig im
> Desaster enden soll.

Dein Hass in Ehren, aber wärs nicht besser du bliebest bei der Wahrheit? 
Inlining macht GCC sehr wohl selbtstätig, und nicht zu knapp.

c-hater schrieb:
> klausr schrieb:
>
>> Gar nicht so dumm, der gcc ;-)
>
> Findest du?
>
> ;implizit mindestens ein "rcall"    ;3
>>   swap r24                        ;1
>>   ret                             ;4
>                                     ;-
>                                     ;8
>
> ->unnützer Overhead mindestens 700% (!!). Und dabei ist noch nichtmal
> der Overhead eingerechnet, den der Compiler betreibt, um seine
> Funktionsparameter immer wieder nach r24 (und folgende) zu bringen bzw.
> diese zu nullen.
>
> Garnicht so dumm wäre er, wenn er selber rausbekommen hätte, daß der
> Callframe hier so nützlich ist wie ein Loch im Kopf. Aber nein, er
> fordert vom Programmierer, daß DER weiß, daß er noch ein "inline" vor
> die Funktion zu schreiben hat, wenn die Sache nicht effizienzmäßig im
> Desaster enden soll.

c-hater, ich fürchte du hast das alles nicht wirklich verstanden...

Du könntest ja mal versuchen, die Funktion tatsächlich zu verwenden, 
auch ohne 'inline' davor. Und du würdest erkennen dass der gcc das alles 
so macht wie du es gerne hättest.

c-hater schrieb:
> wenn die Sache nicht effizienzmäßig im
> Desaster enden soll.

C ist schon sehr effizient, wenn man die Entwicklungszeit einer 
Applikation als Maßstab nimmt, was ja selbstverständlich sein sollte.

Ineffizient ist dagegen, wenn man an Sachen unnütz rumoptimiert, die 
vielleicht 0,01% der gesamten CPU-Zeit benötigen. Das ist pure 
Zeitverschwendung, also Bestehlen des Auftraggebers.

Deine 700% kannst Du also getrost in der Pfeife rauchen.

Wer's nicht glaubt:

1

#include <avr/io.h>

2

#include <stdint.h>

3

4

static uint8_t swap(uint8_t byte)

5

{

6

  return byte>>4 & 0x0F | byte<<4 & 0xF0;

7

}

8

9

int main(void) {

10

11

  DDRD = 0xff;

12

  for(;;)

13

    PORTD = swap(PORTC);

14

  return 0;

15

}

wird vom GCC in folgenden Assembler-Code übersetzt:

1

main:

2

  ldi r24,lo8(-1)

3

  out 0x11,r24

4

.L2:

5

  in r24,0x15

6

  swap r24

7

  out 0x12,r24

8

  rjmp .L2

C-hater, wenn du das in Hand-Assembler auch nur 1 Taktzyklus pro 
Schleifendurchlauf besser hinbekommst, melde dich bitte noch einmal.

Wenn nicht, halte dich mit deinen Kommentaren einfach mal etwas zurück 
und lerne erst einmal, mit C und GCC umzugehen.

Yalu X. schrieb:
> C-hater, wenn du das in Hand-Assembler auch nur 1 Taktzyklus pro
> Schleifendurchlauf besser hinbekommst, melde dich bitte noch einmal.

Kein Problem:

  in r24,0x15
  swap r24
  out 0x12,r24
  in r24,0x15
  swap r24
  out 0x12,r24
  in r24,0x15
  swap r24
  out 0x12,r24
  in r24,0x15
  swap r24
  out 0x12,r24
  in r24,0x15
  swap r24
  out 0x12,r24
  in r24,0x15
  swap r24
  out 0x12,r24
  ...

Könnte mir aber denken, dass GCC mit -O2 oder -O3 statt -Os ansatzweise 
auf ähnliche Gedanken verfällt.

A. K. schrieb:
> Könnte mir aber denken, dass GCC mit -O2 oder -O3 statt -Os ansatzweise
> auf ähnliche Gedanken verfällt.

Nein, für eine Endlosschleife nicht, denn irgendwann wird ja doch
ein „teurer“ Rücksprung gebraucht.

Eine abgezählte Schleife würde er aber in der Tat bei -O3 entrollen.

Wobei mir ein echtes Swap noch nie in einem Programm vorgekommen ist.
Nur sowas hier:

1

static void lcd_byte( uint8_t d )

2

{

3

  lcd_nibble( d );

4

  lcd_nibble( d<<4 );

5

  _delay_us( 45 );      // 45us

6

}

Moby schrieb:
> Bastelboy schrieb:
>> Wie kann ich den (Attiny) GCC dazu bringen den ASM-Befehl SWAP zu
>> nehmen?
>
> Solche Fragen stellen sich nicht wenn man gleich Assembler nimmt.
> Ist unter dem Strich auch einfacher mit viel weniger Schreibaufwand.

Wir haben das Jahr 2013.

c-hater schrieb:
> klausr schrieb:
>
>> Gar nicht so dumm, der gcc ;-)
>
> Findest du?
>
> ;implizit mindestens ein "rcall"    ;3
>>   swap r24                        ;1
>>   ret                             ;4
>                                     ;-
>                                     ;8
>
> ->unnützer Overhead mindestens 700% (!!). Und dabei ist noch nichtmal
> der Overhead eingerechnet, den der Compiler betreibt, um seine
> Funktionsparameter immer wieder nach r24 (und folgende) zu bringen bzw.
> diese zu nullen.

Wo, aus Projektsicht gesehen, entsteht eigentlich genau dieser Overhead?

A) Wird die Entwicklungszeit länger weil C statt ASM genutzt wird?
B) Wird eine Anwendung, die bei MCUs meist zu 90% aus sleep mode 
besteht, dadurch langsamer?
C) Wird das Programm so viel größer, das ein anderer Mikrocontroller 
genutzt werden muss?

Oder

D) Die Entwicklungszeit verkürzt sich gegenüber ASM
E) Der Code wird portierbar
F) Der Code wird wartbar

A-C) NEIN
D-F) JA

6:0 für C in kommerziellen oder sonstigen Projekten, bei denen 
Entwicklungseffizienz eine Rolle spielt.

Jörg Wunsch schrieb:
> A. K. schrieb:
>> Könnte mir aber denken, dass GCC mit -O2 oder -O3 statt -Os ansatzweise
>> auf ähnliche Gedanken verfällt.
>
> Nein, für eine Endlosschleife nicht, denn irgendwann wird ja doch
> ein „teurer“ Rücksprung gebraucht.

Wenn man die Schleife wirklich teilweise unrollen will, kann ja im 
C-Quellcode die Zeile

1

    PORTD = swap(PORTC);

mehrmals hintereinander schreiben. Entsprechendes müsste der C-Hater 
auch in Assembler machen, um mehrere Swaps pro Schleifendurchlauf
auszuführen.

Kindergärtner schrieb:
> Tim .  schrieb:
>> Wir haben das Jahr 2013.
> Und trotzdem benutzen noch Leute AVR...

Welche Kriterien sprechen genau dagegen?

Yalu X. schrieb:
> PORTD = swap(PORTC);

Dieser Code geht noch kürzer:

1

  PORTD = 0;

2

  for(;;);

Du meintest warscheinlich:

1

  for(;;)

2

    PORTD = swap(PINC);

Peter Dannegger schrieb:
> Du meintest warscheinlich:
>   for(;;)
>     PORTD = swap(PINC);

Mist, natürlich. Danke für den Hinweis.

Kindergärtner schrieb:
> Tim .  schrieb:
>> Welche Kriterien sprechen genau dagegen?
> Na wenn man nicht gerade auf Massenproduktion geht und jeder Cent zählt,
> kann man zB auch kleine ARM's (wie die STM32) nehmen und sich daran
> erfreuen dass man viel leichter viel mehr Rechen&Peripherie-Leistung
> bekommt... Die viel schnellere Interrupt-Behandlung, die effizientere
> Datenverarbeitung macht die besonders schön für zeitkritische Sachen.

Ja, ich finde die kleine ARMS auch toll. Wenn Du auf den Hobbybereich 
kommst, spricht allerdings noch einiges dagegen:

- Fast keine DIP Bausteine verfügbar.
- ISP Hardware teurer/schwerer zu bekommen.
- Kostenlose Entwicklungsumgebungen sind nicht so gut wie bei AVR.
- Die Peripherie der ARM Prozessoren ist deutlich komplexer als bei AVR.
- Für die meisten Controllanwendungen benötigt man weder 32bit, noch 30 
MIPS.

Jungs, es ging um den Swap hier … Threads, ob nun Controllerarchitektur
A oder B besser oder schlechter ist, haben wir wirklich schon zur
Genüge, und die Argumente bleiben auch jedesmal die gleichen.

Peter Zz schrieb:
> Mir ging es halt darum, wie man da ein bischen Assembler in den C-Code
> moggeln kann

OK, ein paar Links dafür hast du ja auch bekommen. ;-)

Generell: der GCC-Inline-Assembler ist reichlich komplex.  Er ist
ziemlich weit unten im Compiler angebunden.  Dadurch ist er zwar
sehr mächtig, weil man insbesondere noch dem Compiler die volle
Freiheit überlassen kann, wie er die Daten zu den möglichen Orten
(Register, Stack) zusortieren kann, aber andererseits ist das dafür
notwendige constraining nicht gerade auf den ersten Blick mental
erfassbar (um es mal vorsichtig zu formulieren ;-).

Peter Zz schrieb:
> Mir ging es halt darum, wie man da ein bischen Assembler in den C-Code
> moggeln kann, und wie man da den Assembler-Befehlen Werte übergeben und
> zurückbekommen kann.

Hier sind noch zusätzlich zu den bereits genannten Links zwei etwas 
ausführlichere Dokumente zu dem Thema:

Allgemein:

  http://gcc.gnu.org/onlinedocs/gcc-4.8.1/gcc/Extended-Asm.html

Speziell für AVRs:

  http://www.nongnu.org/avr-libc/user-manual/inline_asm.html

Kindergärtner schrieb:
> Und hier ein paar Feinheiten für ARM's, das ist wohl sonst kaum bis gar
> nicht dokumentiert:

Das wäre es doch eigentlich mal Wert, hier irgendwo im Wiki erwähnt
zu werden, oder?

Peter Zz schrieb:
> Und es geht doch:

leider falsch...

Klaus-Dieter schrieb:
> und der Compiler meckert nicht!

Das ist bei asm Statements kein Argument. ARM hatte lange Zeit einen 
ähnlichen Fehler im GCC Teil von CMSIS drin, der in bestimmten Fällen zu 
falschem Code führte.

Die Spezifikationen in diesem Statement gehen davon aus, dass der darin 
enthaltene Assembler-Code einen Input- und einen davon unabhängigen 
Output-Operand hat. Also sowas wie swap %0,%1.

1

unsigned char test_x, test_y;

2

unsigned char f(unsigned char x, unsigned char y)

3

{

4

  test_x = x;

5

  test_y = y;

6

  asm volatile(

7

  " swap %0    \n\t"

8

  : "=d" (y)

9

  : "r" (y)

10

  );

11

  return y;

12

}

führt zu

1

  sts test_x,r24

2

  sts test_y,r22

3

         swap r24

Hier wird also nicht y geswapped, sondern x.

Probiers mal so:

1

asm volatile("swap %0" : "+r"(my_byte));

PS: Das volatile im asm kann man hier auch weglassen.

W.S. schrieb:
> Leute, kommt mal wieder runter.

Verfolg mal c-haters Vorgeschichte. Er ist kein unbeschriebenes Blatt.

> Wenn die Compilerprogrammierer so einige Sachen wie Multiplikation mit
> 2er potenzen usw. per Schift erledigen oder sehr spezielle Dinge
> dediziert entdecken (wie die Verwendung von Swap), dann ist das schon
> recht viel.

?
Das sind einfache Übungen im Compilerbau.


> Assembler programmieren kann. Das erreicht man mit C oder Pascal oder
> compiliertem Basic udgl. nie und nimmer. Aber im Stile der heutigen Zeit
> wird dann eher gesagt "nimm einen dickeren Controller".

Wie PeDa weiter oben schon gesagt hat:
Es bringt nichts, ein Codestück um 100% zu optimieren, wenn dieses 
Codestück für nicht mehr als ein paar Prozent der kompletten Laufzeit 
verantwortlich ist.

Hab ich ein Programm, dass 1 Stunde Laufzeit für 1 Durchgang benötigt 
und habe ich ein Codestück, welches für 1 Sekunde davon verantwortlich 
ist, dann ist das die falsche Stelle um mit einer Optimierung 
anzusetzen. Selbst wenn ich die Laufzeit dieses Stücks von 1 Sekunde auf 
0.1 Sekunden senken könnte (was viel ist), verringert sich die komplette 
Laufzeit damit lediglich von 60 Minuten auf 59 Minuten und 59.1 
Sekunden. Also praktisch nicht merkbar und völlig irrelevant.
Die meisten dieser 'cleveren' Hacks fallen in den meisten Programmen 
(bis auf ein paar Sonderfälle abgesehen) genau in diese Kategorie.

W.S. schrieb:
>> Das sind einfache Übungen im Compilerbau.
>
> Nana, SOOOO einfach ist der Compilerbau denn doch nicht.

Der von oben dir beschriebene Kram schon. Sowas konnten C Compiler schon 
zu einer Zeit, als die Storage Class "register" noch reale Bedeutung 
hatte. Ersetzung bestimmter Rechenausdrücke durch einfachere ist eine 
sehr einfache Optimierung, weil rein lokal auf den Ausdruck begrenzt. 
Freilich hat man nicht alles getan, was man gekonnt hätte, denn wenn der 
Compiler in 64K passen musste war für exotische Fälle kein Platz.

A. K. schrieb:

> Ersetzung bestimmter Rechenausdrücke durch einfachere ist eine
> sehr einfache Optimierung, weil rein lokal auf den Ausdruck begrenzt.

Genau. Das ist schon mal die 2-er Potenz Sache.
Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer 
machen.

Jeder Student der das 1. Semster "Compilerbau" hinter sich hat, kann 
diese Dinge problemlos realisieren. Zum Teil sind derartige 
Optimierungen (und noch viele mehr) Teil der zugehörigen Übungen.

Karl Heinz Buchegger schrieb:
> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer
> machen.

Eher nicht. Zwar hätte man Swap wohl nicht für lohnend erachtet, weil zu 
exotisch, aber einen Baum aus ein paar OR/AND/SHIFT Ops mit bestimmten 
Operanden zu identifizieren ist leichter, als den Kram hinterher im Code 
zu erkennen. Zumal wenn Suboperandenausdrücke die Befehle trennen.

Peephole-Optimizer waren eher dort relevant, wo eben nicht innerhalb von 
Ausdrücken optimiert wird, sondern übergreifend. So beispielsweise wenn 
ein Load-Befehl genau das wieder läd, was der andere Ausdruck direkt 
davor gespeichert hat, oder ein Sprungbefehl genau dahinter wieder 
aufschlägt.

W.S. schrieb:
> Er hat auch schon mal sowas gesagt wie "wie gut, daß mein ATtiny davon
> nix weiß.." als es um die maximal erfaßbare Zählrate an einem
> Controllerpin ging und er partout nicht begreifen wollte, daß da maximal
> Fsystem/2 drin ist

Nö, ging es nicht.
Du mußt andere Leute nicht für dumm halten, ich kann Datenblätter lesen.

Karl Heinz Buchegger schrieb:
> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer
> machen.

PS: Der Abschnitt "replacement rules" der Wikipedia(en) zur Peephole 
Optimization ist schlichtweg Unsinn.

Karl Heinz Buchegger schrieb:
> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer
> machen.
>
> Jeder Student der das 1. Semster "Compilerbau" hinter sich hat, kann
> diese Dinge problemlos realisieren.

Wie schon oben geschrieben, musste der AVR-GCC immerhin die Version 4.4
erreichen, um den Ausdruck im Eröffnungsbeitrag als Swap zu erkennen.

Aber seither kann er es, weswegen mich mich die vielen Vorschläge,
Inline-Assembler zu verwenden, etwas wundern.

Yalu X. schrieb:
> Aber seither kann er es, weswegen mich mich die vielen Vorschläge,
> Inline-Assembler zu verwenden, etwas wundern.

Was will man machen. Dieses dauernde Ersetzen von Divisionen durch 
Shifts, weil man ebenfalls meint klüger zu sein als der Compiler ist ja 
auch nicht tot zu bekommen. Und diese Optimierung ist schon wesentlich 
länger in dem AVR-GCC enthalten.

Yalu X. schrieb:
> Wie schon oben geschrieben, musste der AVR-GCC immerhin die Version 4.4
> erreichen, um den Ausdruck im Eröffnungsbeitrag als Swap zu erkennen.

Es gibt 2 Wege, wie so etwas in einem Compiler wie GCC landen kann.

(1) Im maschinenunabhängigen Teil werden Rotationen erkannt und im 
maschinenabhängigen Teil wird eine Byte-Rotation um 4 durch Swap 
ersetzt.

(2) Der Kram landet ziemlich originalgetreu im maschinenabhängigen Teil 
und muss dort identifiziert werden.

Wie das hier abgeht weiss ich nicht. Methode (2) ist ziemlich speziell 
und gehört eher nicht zu den vorrangigen Optimierungen. Methode (1) 
lohnt eher, zumal davon alle profitieren.

Simon K. schrieb:
> Was will man machen. Dieses dauernde Ersetzen von Divisionen durch
> Shifts, weil man ebenfalls meint klüger zu sein als der Compiler ist ja
> auch nicht tot zu bekommen.

Wobei man dabei aber aufpassen muss, dass einem die integer promotion 
keinen Strich durch die Rechnung macht. Wenn der Compiler negative Werte 
nicht aussschliessen kann wirds hässlicher.

A. K. schrieb:
> Karl Heinz Buchegger schrieb:
>> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer
>> machen.
>
> PS: Der Abschnitt "replacement rules" der Wikipedia(en) zur Peephole
> Optimization ist schlichtweg Unsinn.

Sorry.
Nö, ist er nicht.
All diese Dinge KANN man mit Peephole Optimizern machen. Man muss nicht. 
Aber man kann. Das der gcc manche Dinge anders erledigt, ist dabei kein 
Argument.
Letzten Endes geht es beim Peephole Optimizing nur darum, ein bestimmtes 
Muster im erzeugten 'Code' (das kann durchaus auch eine interne 
Repräsentierung des Codes sein, die noch nicht auf den endgültigen 
Opcodes basiert) zu finden und durch ein anderes funktional 
gleichwertiges Muster zu ersetzen. Auch das Abklappern eines Baumes auf 
bestimmte Knoten-Teibaum-konstellationen ist nichts anderes als eine 
Form des Peephole-Optimizings.

Dein Denkfehler besteht darin, anzunehmen dass Peephole-Optimizer nur 
auf Maschinencode-Ebene arbeiten. Das ist aber nicht der Fall. Der 
entscheidende Punkt beim Peephole-Optimizing besteht darin, dass der 
Optimizer ohne Ansehen der Sprachregeln einfach nur nach Mustern 'in den 
Datenstrukturen' sucht und diese Muster durch andere ersetzt. Die 
Sprachregeln sind, wenn überhaupt notwendig, implizit in den Mustern 
enthalten. Der Optimizer muss sich nicht mehr darum kümmern.

Rolf Magnus schrieb:
> Andererseits kennen viele CPU-Architekturen auch einen arithmetischen
> Rechts-Shift, der auch mit negativen Werten umgehen kann.

Sicher, aber hast du mal die Resultate von
  i / 2
und
  i >> 1
bei ungeraden negativen Werten verglichen?

Ein arithmetischer Shift kann also nicht direkt eine Division mit 
Vorzeichen ersetzen, sondern es wird eine Anpassung für negative Werte 
erforderlich.

A. K. schrieb:
> Simon K. schrieb:
>> Was will man machen. Dieses dauernde Ersetzen von Divisionen durch
>> Shifts, weil man ebenfalls meint klüger zu sein als der Compiler ist ja
>> auch nicht tot zu bekommen.
>
> Wobei man dabei aber aufpassen muss, dass einem die integer promotion
> keinen Strich durch die Rechnung macht. Wenn der Compiler negative Werte
> nicht aussschliessen kann wirds hässlicher.

Die Frage ist dann aber eher:
Hat der 'clevere' Programmierer das überhaupt bedacht, dass das Ergebnis 
eines Rechtsshifts bei negativen Zahlen im 2-er Komplement eben nicht 
identisch ist mit einer Division.
Wenn ich dividieren will, weil das die richtige Operation an dieser 
Stelle ist, dann ist man gut beraten, da auch eine Division 
hinzuschreiben. Ist es möglich diese Division durch einen Shift zu 
ersetzen (weil der Datentyp des beteiligten Operanden es erlaubt), dann 
macht der Optimizer das (auch wenn ich, wie Rolf korrekterweise anmerkt, 
mich nicht 100% darauf verlassen kann, dass der Compiler die Fähigkeit 
dazu hat). Ist die Ersetzung nicht möglich, dann hat das auch einen 
Grund. Meistens hat dann der Programmierer geschlafen und die falschen 
Datentypen benutzt. Man kann aber einem Compiler nicht die mangelhafte 
Ausbildung der Programmierer anlasten.

Rolf Magnus schrieb:

> Nicht jeder hat Lust, bei allen Operationen, die man in C nur indirekt
> ausdrücken kann, erstmal nachzuschauen, ob der Compiler auch erkennt,
> was eigentlich gemeint war und schlau genug ist, das in die passende
> Assembler-Instruktion umzuformen.

Ich verstehe dein Dilemma.

Trotzdem musst du dich auf einige Dinge verlassen können. Das ein 
Compiler die neusten Optimierungstricks nicht unbedingt beherrscht, 
davon muss man nicht ausgehen und sollte besser nachsehen, wenn man 
darauf angewiesen ist. Es gibt allerdings auch einen Haufen 
Optimierungen, die sind seit Jahrzehnten Standard. Wenn ein Compiler die 
nicht beherrscht, dann ist das meistens deshalb weil es ganz einfach 
noch keinem aufgefallen ist, dass hier eine mögliche Optimierung fehlt 
oder weil der Leidensdruck nicht groß genug war (sprich die Operation 
kommt nicht oft genug vor, als dass sich jemand ran gesetzt hätte und 
sie schneller gemacht hat)
Das der gcc nicht unbedingt auf Spitzen-Leistungen im Bereich 8 Bit 
Prozessoren getrimmt ist, wissen wir alle. Aber er schlägt sich nicht 
schlecht. Als Faustregel würde ich für mich nehmen: Jede Optimierung auf 
Anweisungsebene, auf die ein Neuling mit vielleicht 1 Jahr Erfahrung 
auch kommt (oder die er irgendwo gesehen hat), kann ein ernstzunehmender 
handelsüblicher Compiler genausogut auch in Eigenregie erledigen. Das 
ist nichts, was einem groß Kopfzerbrechen machen müsste.

Trotzdem bleibt natürlich der von dir angesprochene schale 
Nachgeschmack. Wenn mich der stört, dann bleibt mir aber in letzter 
Konsequenz nicht viel anders übrig, als auf Hochsprachen zu verzichten 
und auf direkten Assembler zu gehen. Und das will dann eigentlich keiner 
wirklich.

Karl Heinz Buchegger schrieb:
> Auch das Abklappern eines Baumes auf
> bestimmte Knoten-Teibaum-konstellationen ist nichts anderes als eine
> Form des Peephole-Optimizings.

Sorry, aber da bin ich anderer Ansicht. Dass ein Peephole-Optimizer 
nicht nur auf dem Maschinecode aufsetzen muss ist richtig. Wobei er im 
üblichen Verständnis aber nach einer Art von Codegenerierung greift, 
was auch Zwischencode sein darf.

Wenn du aber bereits den vom Parser ausgeworfenen Baum als solchen 
Zwischencode definierst, dann machst du den Parser zu einem 
Codegenerator erster Stufe und alle lokalen Optimierungen in diesem Baum 
werden zu Peephole-Optimierungen. Das wäre ziemlich quer zum üblichen 
Verständnis von Abläufen in einem Compiler.

Die Wikipedia-Anmerkung zeigt auch, dass ich nicht der Einzige bin, der 
mit der dortigen Definition nicht recht glücklich ist.

Dass man Optimierungen auch umständlich hinten durchführen kann, die man 
einfacher vorne gemacht hätte, ist freilich richtig.

> Dieses dauernde Ersetzen von Divisionen durch Shifts, weil
> man ebenfalls meint klüger zu sein als der Compiler ist ja
> auch nicht tot zu bekommen.

Selbiges mit modulo und Verunden.
Ja, bei 2-er Potenzen und unsigned Typen stimmt diese Beziehung. Aber 
auch nur dann.
Und? Das ist für einen Compiler nicht schwer rauszukriegen, ob diese 
Voraussetzungen gegeben sind oder nicht und den Ersatz zu machen.
Es ist aber für einen (Nachfolge-)Programmierer nicht so einfach 
rauszukriegen, warum in einem größeren System

1

#define QUEUE_SIZE  8

2

3

uint8_t queue[QUEUE_SIZE];

4

uint8_t count;

5

6

void add( uint8_t value )

7

{

8

  queue[count++] = value;

9

  if( count & (QUEUE_SIZE - 1) )

10

    count = 0;

11

}

die Operation so richtig in die Hose geht, wenn die QUEUE_SIZE von 8 auf 
10 erhöht wird.
Der Code ist nur beispielhaft gemeint. Es geht darum, dass man hier im 
Code eine Annahme versteckt hat, nämlich das QUEUE_SIZE eine 2-er Potenz 
ist. Das kann gut gehen, aber wir alle wissen, dass die Dinge eben des 
öfteren nicht gut gehen. Vor allen Dingen dann nicht, wenn der Code dann 
auch schon ein paar Jahre auf dem Buckel hat und niemand mehr über die 
Internals Bescheid weiß.
Zumal es hier keinen Grund für diese Annahme gibt. Solange die 
Voraussetzung "ist 2-er Potenz" erfüllt ist, ersetzt mir der Optimizer 
recht zuverlässig die Modulo-Rechnung durch ein &. Ist sie nicht 
erfüllt, dann benutzt er die Divisions-Module-routine, wie auch immer 
die aussieht. Das kostet mir zwar Laufzeit ist aber immer noch korrekt. 
Das ist mir immer noch lieber, als ein Programm, welches dann Mist baut 
und man dann erst mal (nach Jahren) suchen muss, was da schief ging.

Pastor Braune schrieb:
> a = a^b
> b = a^b
> a = a^b

Ich hacke ja schon ewige Jahre. Aber das Ding war mir neu (kann man 
manchmal sicher gut brauchen;-)

Thx 4 te hint

Grüße
Andreas

Andreas H. schrieb:
> Pastor Braune schrieb:
>> a = a^b
>> b = a^b
>> a = a^b
>
> Ich hacke ja schon ewige Jahre. Aber das Ding war mir neu (kann man
> manchmal sicher gut brauchen;-)
>
> Thx 4 te hint

Das ist aber kein 4-Bit Swap, sondern ein Austausch der Inhalte von 2 
Variablen. Und vermutlich ginge das sogar schneller, wenn man einfach 
eine neue lokale Variable erzeugen und normal kopieren würde ;-)

Ein Problem bei der Optimierung von Mul/Div zu Shift ist, dass der mit 
Shifts erzeugte Code länger sein kann als Mul/Div-Befehle oder der 
Aufruf einer Laufzeitfunktion. Und avr-gcc daher in seiner üblicherweise 
verwendeten -Os Variante zumindest früher oft den Aufruf wählte. Dem 
Compiler ist da formal kein Vorwurf zu machen, aber ob der Programmierer 
das auch so fundamentalistisch sieht?

Karl Heinz Buchegger schrieb:
> A. K. schrieb:
>
>> Ersetzung bestimmter Rechenausdrücke durch einfachere ist eine
>> sehr einfache Optimierung, weil rein lokal auf den Ausdruck begrenzt.
>
> Genau. Das ist schon mal die 2-er Potenz Sache.
> Die Swap Erkennung kann zb der nachgeschaltete Peephole-Optimizer
> machen.
>
> Jeder Student der das 1. Semster "Compilerbau" hinter sich hat, kann
> diese Dinge problemlos realisieren. Zum Teil sind derartige
> Optimierungen (und noch viele mehr) Teil der zugehörigen Übungen.

ALso ich finde siese Optimierung nicht trival.  Klar, in einem eigenen 
Mini-Compiler ist recht einfach zu hacken wenn man genau weiß wonach man 
sucht. Aber die Anzahl der Regeln wechst schnell und ist irgendwann 
nicht mehr zu überblicken -- man will ja nicht nur SWAP erkennen sondern 
auch andere Instrktionen, und beileibe nicht jeder Instruktionssatz ist 
so einfach wie bei AVRs.

Konkret für swap:

1

static inline unsigne char swap (unsigned char x)

2

{

3

    return (x << 4) | (x >> 4);

4

}

Dies bringt folgende Operationen:

2 Promotionen 8 Bit  ->  16 Bit
2 Shifts
1 Or
1 Truncation 16 Bit  ->  8 Bit

Hinzu kommt die Fähigkeit früh zu inlinen und damit früh genug die 
Kosten für eine Inline-Version vs. eine nicht-Inline Version bestimmen 
zu können, also noch lange bevor mit dem eigentlichen 
maschinenabhängigen Teil begonnen wird.  Auch das ist nichttrivial.

Die o.g. swap-Darstellung geschieht im GCC im Instruction-Combiner

http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/combine.c?content-type=text%2Fplain&view=co

bereits ein kurzes Überfliegen des Codes sollte klar werden lassen, daß 
das kein triviales Stückchen Code ist.  Der Instruction-Combiner des GCC 
untersucht maximal 3 Pseudo-Instruktionen.  Die Beschränkung auf 3 ist 
dadurch begründet, daß die Laufzeit exponentiell mit Anzahl der 
Instruktionen steigt.  Zudem sind bereits bei nur 3 Instruktionen sehr 
viele Sonderfälle zu berücksichtigen, und die Anzahl zu testenden 
Combines ist selbst für kleine Routinen sehr hoch.

Konkret erkennt der Combiner, daß das Konstrukt einem 8-Bit Rotate um 4 
entspricht, welches wiederum in AVR-Teil implementiert wird.

Ein Peephole würde an dieser Stelle nicht oder nur sehr schlecht 
funktionieren.

Johann L. schrieb:
> man will ja nicht nur SWAP erkennen sondern
> auch andere Instrktionen, und beileibe nicht jeder Instruktionssatz ist
> so einfach wie bei AVRs.

Eine solche Optimierung lohnt IMHO dann, wenn man eine zwar nicht 
triviale aber strikt lokale generische Erkennung von 
Rotationsoperationen durchführt. Zumal die in Crypto-Algorithmen nicht 
selten sind. Daraus pickt man dann den Spezialfall für SWAP.

A. K. schrieb:
> Johann L. schrieb:
>> man will ja nicht nur SWAP erkennen sondern
>> auch andere Instruktionen, und beileibe nicht jeder Instruktionssatz ist
>> so einfach wie bei AVRs.
>
> Eine solche Optimierung lohnt IMHO dann, wenn man eine zwar nicht
> triviale aber strikt lokale generische Erkennung von

Lokal muß es nicht sein, daß heißt im Codefluß können beliebig viele 
andere, unbeteiligte Instruktionen auftreten.  Was hier relevant ist, 
ist der Datenfluß.

Johann L. schrieb:
> Lokal muß es nicht sein, daß heißt im Codefluß können beliebig viele
> andere, unbeteiligte Instruktionen auftreten.  Was hier relevant ist,
> ist der Datenfluß.

Mit "lokal" bezog ich mich auf die Auswirkungen, nicht auf den Raum. 
Gleicher Input und Output, keine Seiteneffekte, ausser ggf. Flags.

Simon K. schrieb:
> Das ist aber kein 4-Bit Swap, sondern ein Austausch der Inhalte von 2
> Variablen.
Für Nibbleswap haben viele CPUs ja schon einen ASM Befehl. Da braucht 
man es eher nicht, denk ich.

>Und vermutlich ginge das sogar schneller, wenn man einfach
> eine neue lokale Variable erzeugen und normal kopieren würde ;-)
Unglücklicherweise arbeiten die meisten meiner Programme nicht mit 
Vermutungen.
Und schneller als drei ASM Statement (nach -O2) wirds wohl auch nicht 
oder ?

Grüße
Andreas

Andreas H. schrieb:
> Simon K. schrieb:
>> Das ist aber kein 4-Bit Swap, sondern ein Austausch der Inhalte von 2
>> Variablen.
> Für Nibbleswap haben viele CPUs ja schon einen ASM Befehl. Da braucht
> man es eher nicht, denk ich.
Äh ja? Darum geht es doch hier. Siehe Eröffnungspost.

>>Und vermutlich ginge das sogar schneller, wenn man einfach
>> eine neue lokale Variable erzeugen und normal kopieren würde ;-)
> Unglücklicherweise arbeiten die meisten meiner Programme nicht mit
> Vermutungen.
> Und schneller als drei ASM Statement (nach -O2) wirds wohl auch nicht
> oder ?
Nunja, wenn für die nachfolgenden Operationen keine bestimmten Register 
benötigt werden, wird der "Variablenswap" unter Umständen sogar in 0 
Instruktionen optimiert.

Es ist jedenfalls besser hinzuschreiben, was man meint und lässt den 
Compiler überlegen, was in der Situation besser ist, als dass man 
irgendwelche vorzeitigen Optimierungen einbaut, die unter Umständen 
jedoch nachteiligen Code erzeugen könnten.

Andreas H. schrieb:
> Und schneller als drei ASM Statement (nach -O2) wirds wohl auch nicht
> oder ?

Je nach Aufbau der CPU geht das sehr wohl.

Diese 3 XORs sind sequentiell abhängig, also nicht in weniger als 3 
Takten machbar, wenn eine ALU-Operation mindestens 1 Takt benötigt.

Im Gegensatz dazu ist die Variante mit 3 Transportbefehlen nicht 
sequentiell abhängig, jedenfalls nicht vollständig, somit 
parallelisierbar.

Überdies ist es bei Operanden in Registern prinzipiell möglich, 
Transportbefehle vollständig über Register Renaming zu implementieren, 
womit es aus der Sicht von Ausführungseinheiten und entsprechenden 
Laufzeiten auf 0 Takte schrumpft, selbst wenn die Register wirklich 
ihren Inhalt tauschen.

Das Ding mit den 3 EXORs ist vor allem interessant, wenn man 2 Register 
tauschen möchte, ohne weiteren Platz zu benötigen.
Nur dafür kenne ich es.


Gruß

Jobst