GCC optimiert 32bit Bitoperationen schlecht/gar nicht?

[Michael R. (Firma: Brainit GmbH) (fisa)]

Hallo allerseits,

in letzter zeit ist mir mehrfach aufgefallen, dass mein avr-gcc 4.8.1 
bei eigentlich einfachen Statements eigenartigen Code erzeugt.

Beispiel 1:

uint32_t f2 (const uint8_t x) {
    return (uint32_t)x << 12;
}

wird zu

f2:
/* prologue: function */
/* frame size = 0 */
/* stack size = 0 */
.L__stack_usage = 0
  mov r22,r24   ;  D.1884, x
  ldi r23,0   ;  D.1884
  ldi r24,0   ;  D.1884
  ldi r25,0   ;  D.1884
  ldi r18,12   ; ,
  1:
  lsl r22   ;  D.1884
  rol r23   ;  D.1884
  rol r24   ;  D.1884
  rol r25   ;  D.1884
  dec r18   ; 
  brne 1b
  ret
  .size  f2, .-f2

Ich weiss schon dass der AVR keinen Barrel Shifter hat, aber dass er 
deswegen gleich eine Schleife mit 4 Shifts erzeugt... idealerweise 
sollte er zum einen gleich die Register in anderer Reihenfolge laden 
(damit wäre schon mal ein << 8 erledigt) und die verbleibenden 4 bit 
über ein SWAP und ANDI erledigt.

irgendwie kommt mir vor, macht er das bei 16 bit operationen auch brav.

Kann es sein dass er da im 32bit-Bereich einfach Schwächen hat?

Kann man ihm da helfen, ohne gleich Assembler programmieren zu müssen?


Beispiel zwei ist für mich noch verwirrender, leider hab ich es bisher 
nciht geschafft das so zu "isolieren" dass in einem einfachen Beispiel 
der falsche Code erzeugt wird. Deshalb hier nur eine zeile:

uint8_t state = (enc_state << 2) & 0x0f;

wird zu

  lds r24,enc_state   ;  enc_state.0, enc_state
  ldi r18,lo8(4)   ; ,
  mul r24,r18   ;  enc_state.0,
  movw r24,r0   ;  D.2339
  clr __zero_reg__
  andi r24,lo8(15)   ;  state,

wenn ich ihm so auf die Sprünge helfe:

    uint8_t state = __builtin_avr_insert_bits(0xffff10ff, enc_state, 0);

wird daraus sinnvoller code:

  lds r24,enc_state   ;  state, enc_state
  lsl r24   ;  state
  lsl r24   ;  state
  andi r24,lo8(12)   ;  state,

(dass das ANDI eimal mit 12 und einmal mit 15 dasteht macht keinen 
Unterschied)

Wie kommt der im ersten Fall auf die idee, für ein simples shift eine 
Multiplikation zu verwenden?

[Falk B. (falk)]

@ Michael Reinelt (fisa)

>bei eigentlich einfachen Statements eigenartigen Code erzeugt.

Wieso eigenartig? Das Ergebnis stimmt doch.


>Ich weiss schon dass der AVR keinen Barrel Shifter hat, aber dass er
>deswegen gleich eine Schleife mit 4 Shifts erzeugt... idealerweise
>sollte er zum einen gleich die Register in anderer Reihenfolge laden
>(damit wäre schon mal ein << 8 erledigt) und die verbleibenden 4 bit
>über ein SWAP und ANDI erledigt.

Das wäre optimal.

>irgendwie kommt mir vor, macht er das bei 16 bit operationen auch brav.

>Kann es sein dass er da im 32bit-Bereich einfach Schwächen hat?

Das ist bekannt.

>Kann man ihm da helfen, ohne gleich Assembler programmieren zu müssen?

Afaik nein. Bzw. sollte man eher mit Arrays und 8 Bit arbeiten, wenn man 
in dieser Richtung unterwegs ist.

>Wie kommt der im ersten Fall auf die idee, für ein simples shift eine
>Multiplikation zu verwenden?

Ist doch logisch gesehen OK. Das Ergebnis stimmt, viele Wege führen nach 
Rom. Klar kann man direkt in Assembler in einigen Situationen bessere 
Ergebnisse erreichen als der avr gcc. Aber in den allermeisten Fällen 
lohnt sich das nicht. Bestenfalls in extremen Kernroutinen, welche 
extrem viele Daten verarbeiten bzw. sehr oft aufgerufen werden, wie z.B. 
eine ISR bei Soft-PWM o.ä.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Falk Brunner schrieb:
>>Kann es sein dass er da im 32bit-Bereich einfach Schwächen hat?
>
> Das ist bekannt.

Aha, ich wusste das nicht. Hast du irgendwelche Quellen?

[Falk B. (falk)]

@ Michael Reinelt (fisa)

>Aha, ich wusste das nicht. Hast du irgendwelche Quellen?

Nur das Forum, das wurde vor längerer Zeit schon mal diskutiert. Das 
Ergebnis war, "ja ist so, wenn es jemanden nicht passt muss er halt am 
avr gcc mitarbeiten und das verbessern, 32 und 64 Bit ist nun mal nicht 
das tägliche Brot eines 8 Bitters". Das war aber schon vor 3-4 Jahren 
;-)
Seit dem scheint niemand ein dringendes Bedürfnis gehabt zu haben, das 
zu verbessern.

[Falk B. (falk)]

Schon etwas älter.

Beitrag "Re: Frage zur C Syntax"

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

Michael Reinelt schrieb:
> (damit wäre schon mal ein << 8 erledigt) und die verbleibenden 4 bit
> über ein SWAP und ANDI erledigt.

Schöner wärs, wenns der Compiler selber macht, aber wenn der Prophet 
nicht zu Berg kommt, dann...

int32_t f2 (const uint8_t x) {
    return (uint32_t)((uint16_t)(x) << 4) << 8;
}

Auf Speed optimieren, um die SWAPs zu kriegen.

[Michael R. (Firma: Brainit GmbH) (fisa)]

A. K. schrieb:
> aber wenn der Prophet
> nicht zu Berg kommt, dann...

Danke! Werd ich also Berge bewegen :-)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Falk Brunner schrieb:
> Seit dem scheint niemand ein dringendes Bedürfnis gehabt zu haben, das
> zu verbessern.

Abgesehen davon dass mein Zeitbudget recht begrenzt ist (im nächsten 
leben werd ich Gärtner oder Lehrer) und die Einstiegshürde um am GCC 
etwas sinnvolles beizutragen recht hoch sein dürfte (mit großem Respekt 
lese ich da immer Johanns Beiträge) täte ich mich fast opfern...

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Falk Brunner schrieb:
>>>Kann es sein dass er da im 32bit-Bereich einfach Schwächen hat?
>>
>> Das ist bekannt.
>
> Aha, ich wusste das nicht. Hast du irgendwelche Quellen?

Na wo die GCC-Quellen sind weißt du ja :-)

> Kann man ihm da helfen, ohne gleich Assembler programmieren zu müssen?

Ja, das geht in C++ (GCC steht in C++) und etwas machine description.

Vom middle-end kommt ein zero-extend und ein Shift, in etwa sowas:

     (set (reg:SI 101)
          (zero_extend:SI (reg:QI 100)))  ;; zero_extendqisi2

     (set (reg:SI 102)
          (ashift:SI (reg:SI 101)
                     (const_int 12)))     ;; ashlsi3

Im .s kannst die entsprechenden Insns per -dP anzeigen lassen.

Für die beiden Insns erzeugt avr-gcc jeweils die kürzesten 
Codesequenzen. Um einen kürzeren Code zu bekommen, könnte man als 
suboptimale Lösung neue Combine-Pattern für avr.md schreiben.  Die 
Pattern, die Combine durchprobiert, können per -da gespeichert werden 
(in .combine).  Da ist dann vermutlich so ein Pattern dabei:

     (set (reg:SI 102)
          (ashift:SI (zero_extend:SI (reg:QI 100))
                     (const_int 12)))

Für das Pattern schreibst eine neue Insn:

(define_insn "*ashift-zeroextend.michael"
  [(set (match_operand:SI 0 "register_operand"                            "=r")
        (ashift:SI (zero_extend:SI (match_operand:QI 1 "register_operand"  "r"))
                   (match_operand:QI 2 "const_int_operand"                 "n")))]
  "INTVAL (operands[2]) >= 8"
  {
    gib_shift_aus();
    return "";
    // oder
    return "asm-code mit %0, %1, %2 wie inline asm";
  })

Dann überlegst du dir den optimalen Code für die mindestens 96 
auftretenden Fälle, also (Shiftoffset #2 von 8..31) * {8-Bit bzw. 16-Bit 
Operand #1) * (optimiert für Speed bzw. Size) und schreibst 
Testprogramme für die Testsuite dafür.  Falls sich Ein- und 
Ausgaberegister überlappen ist evtl. extra Fallunterscheidung notwendig, 
daher die "mindestens 96 Fälle".

[Falk B. (falk)]

Johann L. (gjlayde) schrieb

chinesisch . . . .

Dong tschau!

;-)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Na wo die GCC-Quellen sind weißt du ja :-)

Jein :-(

ich schau mir das ernsthaft an, bin aber unsicher wo ich aufsetzen soll. 
5.0? 4.8.4?

Gibts irgendwo einen (deinen?) branch der AVR-spezifische Patches 
enthält, welche es (noch) nicht nach trunk geschafft haben?

SVN wird sinnvoll sein, oder?

Wenn ich da wirklich was mache, wärst du bereit (und hättest überhaupt 
die Zeit) mich dann etwas als Mentor zu unterstützen?

Falk Brunner schrieb:
> chinesisch
Nö, zu meiner eigenen Überraschung glaube ich zu verstehen wovon er 
spricht :-)

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

Johann L. schrieb:
> Ja, das geht in C++ (GCC steht in C++) und etwas machine description.

Steckt die Codeerzeugung der Shifterei bei AVRs nicht sowieso schon in 
einer separaten Routine drin?

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

Falk Brunner schrieb:
> Dong tschau!

Um Zwischencode in den Assemblercode der Zielmaschine umzusetzen, 
verwendet GCC eine an LISP erinnernde Beschreibungssprache in Form von 
*.md Files.

[Falk B. (falk)]

@ A. K. (prx)

>Um Zwischencode in den Assemblercode der Zielmaschine umzusetzen,
>verwendet GCC eine an LISP erinnernde Beschreibungssprache in Form von
>*.md Files.

So grob hab ich das schon verstanden, was aber noch lange nicht 
bedeutet, dass ich auch nur ansatzweise Ahnung vom Compilerbau habe. Das 
ist eines der 6254527456 Dinge, die ich in diesem Leben nicht mehr 
angehen werde. Bestenfalls würde ich im Extremfall ein kleine 
Kernroutine in ASM schreiben und in mein C Projekt einbinden. Das ist 
für mich das höchste der Gefühle zu dem Thema. Ich kann nicht mal C++ 
8-0

[Michael R. (Firma: Brainit GmbH) (fisa)]

Falk Brunner schrieb:
> Das ist eines der 6254527456 Dinge, die ich in diesem Leben
> nicht mehr angehen werde.

Eigentlich gehts mir da wie dir.

Nur - ab und zu stößt du auf Ding 6254527456 + 1

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> ich schau mir das ernsthaft an, bin aber unsicher wo ich aufsetzen soll.
> 5.0? 4.8.4?

Wenn es für dich privat ist, dann die Version, die dir am besten 
gefällt.

Wenn's upstream gehen soll, dann GCC 6.  GCC 5 ist momentan in Stage 
III, d.h. nur Bugfixes und Tippfehler in der Doku werden akzeptiert; 
ditto für GCC 4.8 und 4.9.

> Gibts irgendwo einen (deinen?) branch der AVR-spezifische Patches
> enthält, welche es (noch) nicht nach trunk geschafft haben?

Nö, ich hab alles upstream, d.h. in trunk und für Bugfixes die Backports 
zu 4.9 und evtl. 4.8.  Meine Änderungen sind einfach genug so daß ich 
auf head arbeite; branches erstell ich keine.

> SVN wird sinnvoll sein, oder?

Geschmackssache. Ich arbeite mit svn.  Da ich Schreibrechte hab ist das 
einfacher; git-svn hatte andere Probleme.  Wenn dir git besser gefällt, 
dann nimm den git-Mirror.  Kann aber sein, daß neurer Tags fehlen, z.B. 
der zur baldigen GCC 5.1 Release.

Links zum svn-Repo bzw. zum git-Mirror sind auf gcc.gnu.org.  Da du 
vermutllich keine Schreibrechte auf GCC hast, gehen Änderungen nur per 
Patch, und Reviews werden eh auf Patch-Ebene durchgeführt.

> Wenn ich da wirklich was mache, wärst du bereit
> mich dann etwas als Mentor zu unterstützen?

Prinzipiell ja.

Wobei es für eine erste, triviale Änderung recht viel zu beachten bzw. 
zu machen und zu befolgen gibt.

Ganz so, wie µC-Einsteiger erst mal ihr Blinky schreiben.  Und das macht 
dann im Vergleich zur einfachen Aufgabenstellung unerwartet viel 
Aufwand.  Insbesondere Formalien wie ChangeLogs, Coding-Rules, 
Review-Prozess, Kommunikation via Mailing-Listen, Tests fahren, 
GPL-Zeugs etc. haben ja nix mit den eigentlichen technischen Änderungen 
zu tun, sind aber dennoch immer einzuhalten.


Falk Brunner schrieb:
> ansatzweise Ahnung vom Compilerbau
Der Compiler ist ja schon gebaut.  Es geht nur darum, hier und da den 
Lack zu polieren ;-)


A. K. schrieb:
> Steckt die Codeerzeugung der Shifterei bei AVRs nicht sowieso schon
> in einer separaten Routine drin?

Die Abbildung von RTL auf Assembler: ja.
Die Abbildung von tree-SSA auf RTL: nein.

tree-SSA -> RTL hängt ab von den rtx-Kosten (avr_rtx_costs), ob es eine 
Standard-Insn für den Shift gibt; hier ashl<mode>3 mit mode = SImode 
(32-Bit Integer) sowie weiteren Eigenschaften des Backends.

Im vorliegenden Fall geht es aber nicht um einen Shift, sondern um eine 
etwas komplexere Operation, für die es keine Standard-Insn gibt.

RTL -> asm wird i.W. durch eine Routine in avr.c erledigt, die nicht 
immer den besten Code ausgibt.  D.h. man kann die Codeerzeugung 
verbessern, indem man in dieser C-Routine bessere Codesequenzen 
(Assembler) ausgibt.  Das beschränkt sich dann auf lokale Änderungen in 
dieser Routine; mehr als C und AVR-Assembler braucht man dafür nicht zu 
beherrschen.

http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/config/avr/avr.c?revision=221316&view=markup#l6076

Z.B. gibt "unsigned long >> 27" eine Schleife aus.  Bei Optimierung auf 
Speed ist das echt übel.  Und selbst für Size find ich das schlecht, 
denn Shifts haben in Programmen oft eine so zentrale Rolle, daß man 
nicht um jedes Byte fuchsen sollte wenn das die Laufzeit x-fach 
aufbläst.  Wenn der µC groß genug ist, sollten m.E. selbst bei 
Optimierung auf Codegröße solche Schleifen mit vielen Durchläufen 
vermieden werden.

[Frank K. (fchk)]

Michael Reinelt schrieb:
> Falk Brunner schrieb:
>> Seit dem scheint niemand ein dringendes Bedürfnis gehabt zu haben, das
>> zu verbessern.
>
> Abgesehen davon dass mein Zeitbudget recht begrenzt ist (im nächsten
> leben werd ich Gärtner oder Lehrer) und die Einstiegshürde um am GCC
> etwas sinnvolles beizutragen recht hoch sein dürfte (mit großem Respekt
> lese ich da immer Johanns Beiträge) täte ich mich fast opfern...

Warum nimmst Du nicht gleich ein kleines Ärmchen? Von den Teilekosten 
ist es inzwischen egal. Oder ist Dir die Einarbeitung zu viel?

fchk

[Michael R. (Firma: Brainit GmbH) (fisa)]

Es geht los...

sourcen sind (per svn) da, drei Prerequisites (die 
Multi-Precision-Dinger) im Nu installiert (Debian sei Dank!), 
avr-gcc-5.0.0 problemlos kompiliert (heidenei, ich glaub es ist mehr als 
15 Jahre her, dass ich einen gcc selbst gebaut habe!)

Allerdings:

/usr/local/avr/lib/gcc/avr/5.0.0/include/stdint.h:9:26: fatal error: stdint.h: No such file or directory

Frage: muss ich binutils und avr-libc (die natürlich in einer alten 
Version installiert sind) auch lokal in einer brandaktuellen Version 
bauen?

Danke, Michi

PS: die avr.c sieht durchaus beherrschbar für mich aus!

[Michael R. (Firma: Brainit GmbH) (fisa)]

Michael Reinelt schrieb:
> avr-gcc-5.0.0 problemlos kompiliert

Johann L. schrieb:
> Wenn's upstream gehen soll, dann GCC 6.

Jetzt seh ichs gerade: ich hab svn://gcc.gnu.org/svn/gcc/trunk genommen, 
sollte das nicht gcc-6 sein?

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Es geht los...
>
> sourcen sind (per svn) da, drei Prerequisites (die
> Multi-Precision-Dinger) im Nu installiert (Debian sei Dank!),

Geht auch direct: von srcroot aus

$ ./contrib/download_prerequisites

ausführen.

> Allerdings:
>

/usr/local/avr/lib/gcc/avr/5.0.0/include/stdint.h:9:26: fatal error: 
> stdint.h: No such file or directory

>
> Frage: muss ich binutils und avr-libc (die natürlich in einer alten
> Version installiert sind) auch lokal in einer brandaktuellen Version
> bauen?

Zunächst würd ich alle Tools nur ohne root installieren, z.B in deinem 
home per passendem --prefix= beim configure, sowohl für binutils als 
auch für gcc und avr-libc.

Ohne libc wirst du nicht weit kommen, abwohl du den compiler auch ohne 
erzeugen kannst.  In dem build-Ordner (der nie innerhalb der gcc-Quellen 
sein darf, d.h. nie configure in srcroot ausführen) kannst du auch 
einfach nur cc1 per "make cc1" neu erzeugen und per xgcc verwenden:

$ <pfad>/xgcc -B<pfad> <optionen>

Michael Reinelt schrieb:
> Jetzt seh ichs gerade: ich hab svn://gcc.gnu.org/svn/gcc/trunk genommen,
> sollte das nicht gcc-6 sein?

Momentan ist's noch 5; das steht in ./gcc/BASE-VER und auch auf 
gcc.gnu.org: "Development:  GCC 5.0 ... (regression fixes and docs 
only)"

Bis gcc 6 abgezweigt wird dauert's noch ein paar Wochen; wann weiß man 
vorher nie so genau.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Ich bin wieder ein paar Schritte weiter: ich habe jetzt in einem 
speziellen lokalen bereich die komplette Toolchain, also binutils-avr, 
gcc und avr-libc installiert, konfiguriert und kompiliert.

Ein erstes kleines Testprogramm (mit eben genau einem << 12) kompiliert 
auch erfolgreich. jetzt könnte ich mich also langsam und behutsam an 
Änderungen am avr.c machen.

Ein kleines problemchen hab ich noch: Mein "originales" avr-size kennt 
die Optionen "--format=avr" und "--mcu=atmega328p", das frisch 
installierte leider nicht. Vermutlich hat Debian da ein paar 
Atmel-Patches mit aufgenommen...

Gibts da eine "offizielle" Version im Source? ich hab 
http://ftp.gnu.org/gnu/binutils/binutils-2.25.tar.gz genommen... es Gäbe 
auch eine git-source, wäre es da drinnen?

ist aber nicht weiter tragisch, meine GCC-Optimierungen kann ich auch 
mit diesem avr-size machen....

Nächste für mich wichtige Frage, speziell an Johann: wenn ich da jetzt 
meine ersten kleinen Änderungen am avr.c mache, wäre es vermutlich 
gescheit, gelcih jede menge tests (Regressions, test cases etc) zu 
machen. Kannst du mir da etwas auf die Sprünge helfen, wie hier das 
"offizielle" und praktikable Verfahren ist?

Wie macht man überhaupt regression tests mit einem Cross-Compiler?



Danke, Michi

[Michael R. (Firma: Brainit GmbH) (fisa)]

H I L F E ! ;-)

Ich versuche grad die avr.c zu verstehen, speziell den Shift-Teil. Ich 
hab schon gesehen dass beim 8- und 16-bit Shift schon alles sehr 
"carefully hand-optimized" ist, da gibts null Handlungsbedarf. Ich 
staune wie man dort um jedes Word ringt :-)

Dafür werden im 32bit-Teil nur die "geraden" shifts (<<8, <<16, <<24) 
optimiert, da gibts also viel Betätigungsfeld für mich.

Also hab ich mir mal ein paar Test-Funktiönchen geschrieben, so in der 
Form

uint32_t f3 (const uint32_t x) {
    return x << 3;
}

und mal den Assembler-Output verglichen, im wesentlichen finde ich mich 
damit also in der avr.c zurecht.

ABER: bei kleinen Shifts (3..7) und mit -O9 macht der ganz komische 
Sachen:

f3:
        /* x << 3 */
  movw r26,r24   ;  tmp47, x
  movw r24,r22   ;  tmp47, x
  lsl r24   ;  tmp47
  rol r25   ;  tmp47
  rol r26   ;  tmp47
  rol r27   ;  tmp47
  lsl r24   ;  tmp47
  rol r25   ;  tmp47
  rol r26   ;  tmp47
  rol r27   ;  tmp47
  movw r22,r24   ;  D.1874, tmp47
  movw r24,r26   ;  D.1874, tmp47
  lsl r22   ;  D.1874
  rol r23   ;  D.1874
  rol r24   ;  D.1874
  rol r25   ;  D.1874
  ret

Warum schiebt der da so komisch zwischen den Regs hin und her?

Soweit ich sehen kann, kommt das nicht vom avr.c, sondern da sind schon 
ein paar zusätzlichen insns involviert:

f3:
/* prologue: function */
/* frame size = 0 */
/* stack size = 0 */
.L__stack_usage = 0
 ; (insn 18 6 23 (set (reg:SI 24 r24 [47])
 ;         (reg/v:SI 22 r22 [orig:44 x ] [44])) shift.c:26 95 {*movsi}
 ;      (expr_list:REG_DEAD (reg:QI 23 r23)
 ;         (expr_list:REG_DEAD (reg:QI 22 r22)
 ;             (nil))))
  movw r26,r24   ;  tmp47, x   ;  18  *movsi/1  [length = 2]
  movw r24,r22   ;  tmp47, x
 ; (insn 23 18 19 (parallel [
 ;             (set (reg:SI 24 r24 [47])
 ;                 (ashift:SI (reg:SI 24 r24 [47])
 ;                     (const_int 2 [0x2])))
 ;             (clobber (reg:QI 18 r18))
 ;         ]) shift.c:26 310 {*ashlsi3_const}
 ;      (expr_list:REG_UNUSED (reg:QI 18 r18)
 ;         (nil)))
  lsl r24   ;  tmp47   ;  23  *ashlsi3_const/4  [length = 8]
  rol r25   ;  tmp47
  rol r26   ;  tmp47
  rol r27   ;  tmp47
  lsl r24   ;  tmp47
  rol r25   ;  tmp47
  rol r26   ;  tmp47
  rol r27   ;  tmp47
 ; (insn 19 23 24 (set (reg:SI 22 r22 [orig:48 D.1874 ] [48])
 ;         (reg:SI 24 r24 [47])) shift.c:26 95 {*movsi}
 ;      (expr_list:REG_DEAD (reg:QI 27 r27)
 ;         (expr_list:REG_DEAD (reg:QI 26 r26)
 ;             (nil))))
  movw r22,r24   ;  D.1874, tmp47   ;  19  *movsi/1  [length = 2]
  movw r24,r26   ;  D.1874, tmp47
 ; (insn 24 19 14 (parallel [
 ;             (set (reg:SI 22 r22 [orig:48 D.1874 ] [48])
 ;                 (ashift:SI (reg:SI 22 r22 [orig:48 D.1874 ] [48])
 ;                     (const_int 1 [0x1])))
 ;             (clobber (reg:QI 19 r19))
 ;         ]) shift.c:26 310 {*ashlsi3_const}
 ;      (expr_list:REG_UNUSED (reg:QI 19 r19)
 ;         (nil)))
  lsl r22   ;  D.1874   ;  24  *ashlsi3_const/2  [length = 4]
  rol r23   ;  D.1874
  rol r24   ;  D.1874
  rol r25   ;  D.1874
 ; (jump_insn 22 14 21 (return) shift.c:27 453 {return}
 ;      (nil)
 ;  -> return)
  ret   ;  22  return  [length = 1]

Johann? Hilfe!

[Markus F. (mfro)]

Hmmm, mit AVR-Assembler habe ich normalerweise nix am Hut, aber für mich 
sieht das logisch aus.

LSL ist (wie ROL) eine 8-Bit Operation. Was dabei oben "rausfällt" 
wandert ins Carry-Flag und wenn das Bit (bei einer 32-Bit-Operation) 
nicht verloren gehen soll, muß es mit ROL ein Byte "drüber" wieder 
"reingeholt" werden.

Wie würdest Du das sonst machen?

[Michael R. (Firma: Brainit GmbH) (fisa)]

Markus F. schrieb:
> Wie würdest Du das sonst machen?

Die beiden MOVs versteh ich nciht, und das verwenden zweier zusätzlicher 
Register.

Eigentlich sollte das so aussehen:

  lsl r22 ; nummer 1
  rol r23
  rol r24
  rol r25
  lsl r22 ; Nummer 2
  rol r23
  rol r24
  rol r25
  lsl r22 ; Nummer 3
  rol r23
  rol r24
  rol r25

ich hab noch etwas weiter geforscht, und mir die ganzen Zwischenfiles 
mit -da ausgeben lassen. Irgendwo kommt er auf die Idee, das <<3 durch 3 
mal <<1 zu ersetzen (ist legitim), etwas später kommt er auf die idee 
zwei von den <<1 zu einem <<2 zusammenzufassen (ist auch legitim). 
Übrigbleiben tun dann zwei getrennte Shift-Insns (einmal << 1 und einmal 
<< 2) plus die unnötigen Register

[Markus F. (mfro)]

Verstehe.

Please ignore my ignorance, aber ich hab' das für Endianess-Rumgemache 
gehalten, sehe aber ein, daß das nicht so ist.

P.S.: Du hast ja schon herausgefunden, was los ist.

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Mein "originales" avr-size kennt die Optionen "--format=avr"
> und "--mcu=atmega328p", das frisch installierte leider nicht.

Keine Ahnung wo es das gibt; hab ich nie verwendet oder gebraucht.
Jörg weiß bestimmt mehr.

> wenn ich da jetzt meine ersten kleinen Änderungen am avr.c
> mache, wäre es vermutlich gescheit, gelcih jede menge tests
> (Regressions, test cases etc) zu machen.

Tests sind zwar unerlässlich, Qualität lässt sich aber nicht in Software 
"reintesten" ;-)  Für den Anfang würd ich einfach übersetzen und den 
erzeugten Code und evtl. rtl-Dumps und rtx-Kosten beurteilen.

> Wie macht man überhaupt regression tests mit einem Cross-Compiler?

Ich verwende avrtest

http://sourceforge.net/p/winavr/code/HEAD/tree/trunk/avrtest/

Der ist plattformunabhähgig, GPL und dürfte mit Abstabnd der schnellste 
Simulator sein.  Ein Core-Simulator ist ja ausreichend.

Tests im dg-framework haben magische Kommentare, die Meta-Infos zu 
jeweiligen Testfall enthalten.

Für den Testfall selbst: Die Quelle sollte natürlich entsprechende 
Pattern erzeugen.  In deinem Fall geht es aber nicht nur um Korrektheit, 
sondern auch um Effizienz, und die kann man mit der gcc Testuite nur 
ansatzweise testen, etwa Abtesten ob bestimmte insns oder Instruktionen 
erzeugt werden.  Dann ist auch wichtig, daß die Tests nicht durch andere 
Optimierungen trivialisieren:

long sh12 (long x)
{
  return x << 12;
}

int main (void)
{
  if (sh12 (1) != 1l << 12)
    abort();

  exit (0);
}

Wird mit Optimierung nie auf abort laufen, egal wie kaputt der Code in 
sh12 auch sein mag :-)


Michael Reinelt schrieb:

> Also hab ich mir mal ein paar Test-Funktiönchen geschrieben,
> so in der Form
>

uint32_t f3 (const uint32_t x) { return x << 3; }

> und mal den Assembler-Output verglichen,

Das wird i.W. expandiert zu

  a = x + x;
  b = a + a;
  c = b + b;
  return c;

Die rtx-Kosten sind für den Fall, naja, nicht sonderlich exakt... Das 
führt dann dazu, daß <<-Schleifen vermieden werden.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Für den Anfang würd ich einfach übersetzen und den
> erzeugten Code und evtl. rtl-Dumps und rtx-Kosten beurteilen.

Ok, überzeugt. Frage dazu: Wo sehe ich die rtx-costs, und was muss ich 
dafür "aufdrehen"? (derzeit fahre ich mit -Dp -da -dA). in deinem avr.c 
sehe ich zwar teilweise die (Debug-)Ausgaben, weiss aber nicht wie ich 
die aktiviere

Johann L. schrieb:
> Ich verwende avrtest

Guter Hinweis, Danke!

Johann L. schrieb:
> Für den Testfall selbst

Hättest du ein Beispiel für einen (einigermaßen passenden) Testfall, das 
ich dann anpassen kann?

Johann L. schrieb:
> Die rtx-Kosten sind für den Fall, naja, nicht sonderlich exakt...

Ah! Ich glaube ich beginne zu verstehen: im avr.c (ist das das 
"Backend"?) erzeugst du nicht nur konkreten asm-code für die insns, 
sondern berechnest auch (in einer anderen Funktion) die entsprechenden 
Kosten? Das heißt aber auch: Wenn ich an einer Stelle stark optimiere, 
müsste ich an einer anderen Stelle auch die Kosten korrigieren, sonst 
wird meine Super-Duper-Optimierung aufgrund falscher (zu hoher) Kosten 
erst gar nicht verwendet?

Letzte Frage für heute: Wie sind denn die Regeln für 
"size-speed-tradeoff"? Wenn -Os muss dann bedingungslos auf size 
optimiert werden, oder dürfen auch mal zwei Words mehr verwendet werden, 
wenn der Code um Faktor 20 schneller wird? Wo liegt die Grenze? Wer 
definiert die? Woran soll ich mich orientieren?

lg Michi

[Michael R. (Firma: Brainit GmbH) (fisa)]

Eine Frage beantwortet, zwei weitere tun sich auf :-)

die rtx_costs seh ich jetzt, -mlog=rtx-costs ist was ich gesucht habe

Ich hab dann mal zaghaft meine erste "Änderung" in avr.c durchgeführt 
(ich gestehe: ein fprintf(stderr, "Hallo Michi\n") ) und das hat sogar 
funktioniert!

Aber: dabei habe ich ein zwar logisches, aber lästiges Verhalten 
bemerkt: Wenn ich am avr.c schraube, und danach den Compiler neu baue, 
baut er mir zwar brav den neuen Compiler (was vergleichsweise schnell 
geht) aber danach für alle AVR-Architekturen die libgcc auch neu, und 
das dauert dann schon mal ein paar Minuten :-(

Das kann man aber sicher ganz einfach abdrehen, und für solche Szenarien 
auf eine (meine) Architektur einschränken, oder?

Zweite Frage: im GCC und rundherum werden immer "modes" verwendet, das 
ganze HI und QI usw. Wenn man mal eine zeitlang damit gearbeitet hat, 
kennt man die sicher im Schlaf, für mich wäre aber eine einfache 
Übersicht ganz praktisch... die gibts sicher irgendwo, nur wo? Als 
Suchbegriffe für google eignen sich die nämlich nur bedingt.... und grep 
versagt an der Stelle auch eher kläglich :-)

Edit: noch eine Frage: In welcher Einheit werden die rtx_costs 
angegeben? Irgendwie kommt mir vor, das wären Vierteltakte, kann das 
sein? (Hintergrund: ein einfaches shl (1 Word / 1 Cycle) hat 
rtx_costs=4)

Danke, Michi

[Jörg W. (dl8dtl) (Moderator)]

Johann L. schrieb:
>> Mein "originales" avr-size kennt die Optionen "--format=avr"
>> und "--mcu=atmega328p", das frisch installierte leider nicht.
>
> Keine Ahnung wo es das gibt; hab ich nie verwendet oder gebraucht.
> Jörg weiß bestimmt mehr.

Das --format=avr war ein reichlich schräger Hack, den sich Eric
Weddington seinerzeit nicht ausreden lassen wollte, und den er in
seine WinAVR-Version der Binutils reingehackt hatte.  Eine Zeitlang
hatte ich ihn auch mal in meinen FreeBSD-Ports drin, und Atmel hackt
seine AVR-Toolchain auch immer noch damit.

Ihm war von vornherein klar, dass ein derartiger Hack wohl keine
Akzeptanz bei den Binutils finden würde, daher hat er das auch nie
probiert.  Nicht, dass das Feature unsinnig wäre, aber wenn schon,
dann hätte man es deutlich generischer aufsetzen müssen, damit auch
andere Controllerfamilien als AVR davon profitieren können.

[Fritz G. (fritzg)]

Darüber bin ich auch gestolpert als ich heute avr-gcc auf macports 
umgestellt habe. Ich finde den Hack gut, habe mir die alte Version (aus 
CrossPack) aus dem Backup geholt.

[Johann L. (gjlayde)]

Jörg Wunsch schrieb:
> Das --format=avr war ein reichlich schräger Hack,

Ich dachte das wär inzwischen über notes gelöst?

[Jörg W. (dl8dtl) (Moderator)]

Johann L. schrieb:
> Ich dachte das wär inzwischen über notes gelöst?

Bin ich mir nicht so ganz sicher.

Selbst dann sollte man es wohl --format=mcu oder so benennen, damit
es allgemeingültig wird und beispielsweise auch von einem ARM
genutzt werden kann.

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> aber danach für alle AVR-Architekturen die libgcc auch neu,

Möglich ist make [inst]all-host.  Oder wie oben beschrieben xgcc oder 
cc1 direkt verwenden und per (in ./gcc) make cc1 generieren.

In ./gcc gelten andere Regeln:  Wird der Compiler von BUILD aus 
generiert, wird er mit -O2 erzeugt, von BUILD/gcc aus jedoch ohne -O, 
was hilfreich ist wenn du cc1 debuggen willst.  Für eine flotte 
Generierung geht z.B.

make -j 10 cc1 CXXFLAGS='-O0 -g0 -pipe'

> Zweite Frage: im GCC und rundherum werden immer "modes" verwendet,
> das ganze HI und QI usw.

Solche Sachen werden üblicherweise in .def Dateien definiert und i.d.R 
auch besser kommentiert als in den Internals dokumentiert.  In dem Fall 
gcc/machmode.def.  Eine Auflösung ist auch da:

http://gcc.gnu.org/wiki/avr-gcc#Exceptions_to_the_Calling_Convention

> Edit: noch eine Frage: In welcher Einheit werden die rtx_costs
> angegeben? Irgendwie kommt mir vor, das wären Vierteltakte, kann das
> sein? (Hintergrund: ein einfaches shl (1 Word / 1 Cycle) hat
> rtx_costs=4)

Mit 1/4 ist eine bessere Granulierung möglich.  Die Einheit ist 
eigentlich COSTS_N_INSNS.

Michael Reinelt schrieb:
> ist das das "Backend"?

Ursprünglich bestanden BEs aus .md und bissl .c und passendem .h. 
Inzwischen ist GCC komplexer; das avr BE besteht aus ca. 40 Dateien.  Im 
weiteren Sinne gehören dazu:

./gcc/config/avr/
./gcc/common/config/avr/
./libgcc/config/avr/
./gcc/testsuite/gcc.target/avr/

und Teile der Build-Umgebung wie Teile von config.gcc, configure.ac, 
etc.

> sondern berechnest auch die entsprechenden Kosten?

Die kommen von TARGET_RTX_COSTS.

> müsste ich an einer anderen Stelle auch die Kosten korrigieren,
> sonst wird meine Super-Duper-Optimierung aufgrund falscher
> (zu hoher) Kosten erst gar nicht verwendet?

Ja.

> Wenn -Os muss dann bedingungslos auf size optimiert werden,
> oder dürfen auch mal zwei Words mehr verwendet werden,

Früher wurde mit -Os strikt die kürzesze Lösung verwendet, und für 
kleine Devices sollte das wohl auch so bleiben.  Für größere µCs ist das 
m.E. nicht mehr sinnvoll, insbesondere für Shifts, die ja in vielen 
Programmen eine zentrale Rolle spielen.  Allerdings hat gcc keine Info 
über die Speichergröße, diese kann nur grob durch andere Features wie 
AVR_HAVE_JMP_CALL nach unten abgeschätzt werden.

> Hättest du ein Beispiel für einen (einigermaßen passenden) Testfall,
> das ich dann anpassen kann?

Um eine halbwegs vollständige Abdeckung der Offsets zu erreichen 
braucht's ja einiges an Code.  Entweder man scheibt alle Fälle händisch 
und überprüft das Ergebnis durch andere Operationen oder eine Tabelle. 
Oder man lässt die zu testende Funktion das Ergebnis selbst bestimmen 
wie in diesem Beispiel für Offsets 8 und 9:

/* { dg-do run } */
/* { dg-options "-fwrapv" } */

#define _ni static __attribute__((__noinline__,__noclone__))
#define _ai static __inline__ __attribute__((__always_inline__))

typedef __INT32_TYPE__ s32;
typedef __UINT32_TYPE__ u32;

_ni u32 fu (int x, u32 a)
{
  (void) x;
  return a;
}

_ni s32 fs (int x, s32 a)
{
  (void) x;
  return a;
}

#define MK_TEST0(N)                                                     \
  _ai u32 ai_lsl_##N (u32 a) { return a << N; }                         \
  _ai u32 ai_lsr_##N (u32 a) { return a >> N; }                         \
  _ai s32 ai_asr_##N (s32 a) { return a >> N; }                         \
                                                                        \
  _ni u32 ni_lsl_##N (u32 a) { return ai_lsl_##N (a); }                 \
  _ni u32 ni_lsr_##N (u32 a) { return ai_lsr_##N (a); }                 \
  _ni s32 ni_asr_##N (s32 a) { return ai_asr_##N (a); }                 \
                                                                        \
  _ni u32 ni_flsl_##N (u32 a) { return fu (0, ai_lsl_##N (a)); }        \
  _ni u32 ni_flsr_##N (u32 a) { return fu (0, ai_lsr_##N (a)); }        \
  _ni s32 ni_fasr_##N (s32 a) { return fs (0, ai_asr_##N (a)); }        \
                                                                        \
  _ni u32 ni_0lsl_##N (int x, u32 a) { (void) x; return ai_lsl_##N (a); } \
  _ni u32 ni_0lsr_##N (int x, u32 a) { (void) x; return ai_lsr_##N (a); } \
  _ni s32 ni_0asr_##N (int x, s32 a) { (void) x; return ai_asr_##N (a); }


#define DO_TEST0(N, OP, X)                                              \
  do {                                                                  \
    if (ai_##OP##_##N (X) != ni_##OP##_##N (X)) __builtin_abort();      \
    if (ai_##OP##_##N (X) != ni_f##OP##_##N (X)) __builtin_abort();     \
    if (ai_##OP##_##N (X) != ni_0##OP##_##N (0, X)) __builtin_abort();  \
  } while (0)

#define DO_TEST1(N, X)                          \
  DO_TEST0 (N, lsl, X);                         \
  DO_TEST0 (N, lsr, X);                         \
  DO_TEST0 (N, asr, (s32) X)

#define DO_TEST2(N)                             \
  DO_TEST1 (N, 0xcafebabe);                     \
  DO_TEST1 (N, 0x12345678)


MK_TEST0 (8)
MK_TEST0 (9)


int main (void)
{
  DO_TEST2 (8);
  DO_TEST2 (9);

  __builtin_exit (0);
  return 0;
}

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Möglich ist make [inst]all-host.

Danke, klingt gut!

Johann L. schrieb:
> Oder wie oben beschrieben xgcc

Das hab ich zwar grelesen, aber mangels Verständnis verdrängt. ich werd 
mich da reinkämpfen...

Johann L. schrieb:
> Oder man lässt die zu testende Funktion das Ergebnis selbst bestimmen
> wie in diesem Beispiel für Offsets 8 und 9:

Uuups... das sieht ja heftig aus... muss ich auch erstmal verstehen. ich 
vermute man stellt den vom Compiler berechneten Wert einem Wert 
gegenüber, von dem man verhindert dass ihn der COmpiler berechnet? 
_noclone_ ist das zauberwort?

ich hab mir nämlich heute schon auf 4 Studnen Autofahrt den Kopf darüber 
zerbrochen, wie man sowas hinkriegen könnte :-)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Guten Morgen allerseits,

Johann L. schrieb:
> Früher wurde mit -Os strikt die kürzesze Lösung verwendet, und für
> kleine Devices sollte das wohl auch so bleiben.  Für größere µCs ist das
> m.E. nicht mehr sinnvoll, insbesondere für Shifts, die ja in vielen
> Programmen eine zentrale Rolle spielen.  Allerdings hat gcc keine Info
> über die Speichergröße, diese kann nur grob durch andere Features wie
> AVR_HAVE_JMP_CALL nach unten abgeschätzt werden.

Hmmm... Die Entscheidung sollte IMHO beim (erfahrenen) Benutzer liegen, 
wobei Kompatibilität gewahrt werden sollte. Wäre es sinnvoll, eine 
(AVR-Spezifisch) Option "-relax-size" oder ähnlich einzuführen? Ohne 
Option wird wie bisher konsequent die kürzeste Variante gewählt, 
andernfalls können diese shifts (und eventuell auch andere wichtige 
Operationen) mal etwas größer ausfallen, wenn sich dadurch ein 
signifikanter Geschwindigkeitsvorteil ergibt.

Abgesehen davon versuche ich gerade die Zusammenhänge zwischen 
tatsächlicher Ausgabe des Asm-Codes und der Kostenberechnung zu 
verstehen. Die müssen ja aus meiner Sicht möglichst exakt 
zusammenpassen, sonst wir eine eigentlich optimale Variante verworfen, 
weil sie zu hohe (aber falsche) Kosten hat.

Und - sie stimmen schon jetzt nicht zusammen:
z.B. (char)x << 5)
erzeugter Code:

swap %0
lsl %0
andi %0,0xe0

tatsächliche Kosten wären 3*COSTS_N_INSNS (unter der Voraussetzung dass 
%0 ein Register ist, auf das ein andi angewendet werden kann)

berechnet werden aber 5:

avr_rtx_costs_1()
case ASHIFT:
[...]
case QImode:
[...]
val = INTVAL (XEXP (x, 1));
[...]
else if (val >= 0 && val <= 7)
*total = COSTS_N_INSNS (val);

Hier fangen aber die Probleme an: TARGET_RTX_COSTS wird in einem anderen 
Kontext (und viel früher) aufgerufen als die Erzeugung des Codes, und 
wichtige Infos stehen nicht zur Verfügung (hier speziell das 
Zielregister, weil es schlicht noch keine (endgültige) 
Register-Zuordnung gibt.

Wie geht man in so einem Fall vor? pessimistisch (5), optimistisch (3), 
oder irgendwo dazwischen?

pessimistisch ist schlecht, weil der (eigentlich optimale) Code dann 
möglicherweise verliert. optimistisch wäre besser, aus meiner Sicht ist 
es sehr wahrscheinlich dass das Zielregister für immediate geeignet ist 
(gibt ja schon ein Stück weit das ABI vor). Schlimmstenfall werden es 
halt zwei words (und cycles) mehr, der Asm-Code ist aber ohnehin noch 
immer optimal.

Eure Meinung?

@Johann: wären meine Fragen per PN (email) besser aufgehoben? Wenn ja, 
lässt du mir eine email-adresse zukommen?

bye, Michi

[Martin (Gast)]

Michael Reinelt schrieb:
> wären meine Fragen per PN (email) besser aufgehoben?

Ich lese gerne mit, daher wäre es schade, wenn auf Email
geschwenkt werden würde...
Ich habe derzeit keinen Anwendungsfall, an dieser Stelle
etwas zu machen, bin auch eher in Zielrichtung ARM Cortex-Mx unterwegs
(ich weiß nicht, ob es dort überhaupt ähnlich ist),
finde es aber trotzdem interessant, etwas über die Internas
des gcc zu erfahren. Vielleicht kann man es später ja mal brauchen...

[Konrad S. (maybee)]

Martin schrieb:
> Ich lese gerne mit, daher wäre es schade, wenn auf Email
> geschwenkt werden würde...

Wir sind viele! ;-)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Konrad S. schrieb:
> Martin schrieb:
>> Ich lese gerne mit, daher wäre es schade, wenn auf Email
>> geschwenkt werden würde...
>
> Wir sind viele! ;-)

Ja, aber was ist wenn das unsere Pascal-Freunde (und/oder C-Hasser) 
lesen? ;-)

[Olaf B. (Firma: OBUP) (obrecht)]

Michael Reinelt schrieb:
> Ja, aber was ist wenn das unsere Pascal-Freunde (und/oder C-Hasser)
> lesen? ;-)

Lasst Sie doch.
Ich bin es durch Arbeit gewöhnt Mitarbeiter/... zu ignorieren, die mich 
stören - wenn ich dann manchmal auch böse werde.

Das Thema ist interessant, komme aber auch aus ARM/PSoC-Ecke.
Einfach weitermachen & ... ausblenden!

mfg

Olaf

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

Michael Reinelt schrieb:
> Ja, aber was ist wenn das unsere Pascal-Freunde (und/oder C-Hasser)
> lesen? ;-)

Das Backend ist sprachunabhängig. Man muss also schon so ziemlich alle 
Compilersprachen hassen.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Feut mich wenn das auf Interesse stößt. Zeitweise hatte ich das Gefühl 
ich führe Selbstgespräche, hab mich wohl getäuscht.

Dann bleiben wir natürlich gerne hier!

[Konrad S. (maybee)]

Michael Reinelt schrieb:
> Ja, aber was ist wenn

Es ist dein Thread. Wenn ein Beitrag den Thread stört, dann verwende 
"Beitrag melden".

[Yalu X. (yalu) (Moderator)]

Michael Reinelt schrieb:
> Ja, aber was ist wenn das unsere Pascal-Freunde (und/oder C-Hasser)
> lesen? ;-)

Falls die hier tatsächlich hereinplatzen und Radau machen sollten, dann
schlage ihnen einfach vor, ihre Zeit besser zu nutzen und endlich einmal
das AVR-Backend des Free-Pascal-Compiler fertigzustellen ;-)

  http://wiki.freepascal.org/AVR

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

Yalu X. schrieb:
> Falls die hier tatsächlich hereinplatzen und Radau machen sollten, dann
> schlage ihnen einfach vor, ihre Zeit besser zu nutzen und endlich einmal
> das AVR-Backend des Free-Pascal-Compiler fertigzustellen ;-)

Oder sich dem lange vernachlässigten Pascal-Frontend des GCC widmen. ;-)

Beider Schicksal suggeriert indes ein gepflegtes Desinteresse.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Konrad S. schrieb:
> Michael Reinelt schrieb:
>> Ja, aber was ist wenn
>
> Es ist dein Thread. Wenn ein Beitrag den Thread stört, dann verwende
> "Beitrag melden".

Jetzt lassts mal gut sein, das war ein  S C H E R Z !

[Michael R. (Firma: Brainit GmbH) (fisa)]

Neue Erkenntnisse, neue Fragen...

Es gibt eine dritte Stelle, welche für die Inmplementierung (zumindest 
des left shifts) relevant ist: Die Länge (in Words) der Operation. GCC 
braucht diese, um darüberliegende (relative) Sprünge zu berechnen (die 
Berechnung selbst macht zwar der Assembler, aber der GCC muss im Vorfeld 
schon abschätzen, ob das Sprungziel innerhalb von 63 Byte liegt, 
andernfalls eine andere Sprungtechnik anwenden)

Damit müssen drei Aufgaben betrachtet werden:

1. Die Abschätzung der Kosten einer konkreten Implementierung: Diese 
wird sehr oft aufgerufen, da diverse Optimierungen verschiedene 
Alternativen auswerfen, aus denen dann anhand der Kosten die beste 
ausgewählt wird.
(@Johann: kann es sein dass der GCC intern manchmal zwischen 
Optimierungsstufen hin- und herspringt, um auch hier mehrere Varianten 
zu prüfen?)

2. Die Berechnung der Länge einer Instruktion (siehe oben)

3. das Erzeugen der Instruktion selbst

2 und 3 sind bereits intern zusammengefasst, ein und derselbe Code 
berechnet entweder die Länge oder gibt Asm aus (hat mich ein paar 
Gehirnzellen gekostet, das rauszulesen)

1 steht leider recht alleine da, und hängt auch im Code nicht mit 2 und 
3 zusammen. Daher ist das Risiko, dass falsche Kosten ermittelt werden, 
recht hoch (siehe Beitrag "Re: GCC optimiert 32bit Bitoperationen schlecht/gar nicht?") 
Es ist aber leider nicht ganz einfach, das "richtig" zu machen, da zu 
dem Zeitpunkt einfach noch zu wenig über das "Umfeld" bekannt ist (z.B. 
ob das Zielregister ein "hohes" Register r16..r31 ist, sprich: für 
Immediate-Operationen geeignet ist, was den erzeugten Assembler-Code 
wesentlich verkürzen kann)

Oder vielleicht doch? Hier hänge ich gerade...

Wo ich momentan ganz verwirrt bin: geht der GCC von einer Zwei- oder 
Drei-Adress-Maschine aus?

(zur Erklärung: reg1 = reg1 op reg2 versus reg1 = reg2 op reg3)

Einiges spricht für die Drei-Adress-Maschine: ashlqi3_out kriegt drei 
operanden, op[0] ist das Zielregister, op[1] und op[2] sind die 
Operanden. Allerdings sind (soweit ich sehen konnte) op[0] und op[1] 
immer identisch, ein Unterschied wird auch bei der Code-Erzeugung 
(zumindest im QI-Zweig) nicht berücksichtigt. Das deutet wieder darauf 
hin, dass man implizit doch von einer Zwei-Adress-Maschine ausgeht (also 
reg1 = reg2)

Allerdings wird im 32-bit Zweig dann doch wieder unterschieden: hier 
wird abhängig von der tatsächlichen Registernummer von op[0] und op[1] 
die Reihenfolge der Operationen umgestellt. Das blick ich jetzt grad gar 
nicht....

Diese Information wäre enorm wichtig für die Kostenberechnung: Hier habe 
ich (soweit ich erkennen konnte) kein Ziel, sondern nur die beiden 
Operanden (ich krieg also nicht reg1 = reg2 op reg3, sondern nur reg2 op 
reg3). Wenn ich stillschweigend davon ausgehen kann dass reg1==reg2 
macht das eine "stimmige" Kostenberechnung einfacher...

Leider sind damit noch nicht alle Schwierigkeiten aus der Welt: Eine 
weitere wichtige Information wäre, ob ein Scratch-Register zur Verfügung 
steht. Diese Info wird bei der Kostenberechnung mit ziemlicher 
Sicherheit nicht zur Verfügung stehen. Aber irgendeinen Tod muss man 
sterben... Hier wäre noch gut zu wissen, ob man bei der Kostenberechnung 
eher optimistisch oder pessimistisch vorgehen sollte (siehe mein Beitrag 
von gestern), wobei ich gefühlsmäßig zu 'optimistisch' tendiere...

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Johann L. schrieb:
>> Früher wurde mit -Os strikt die kürzesze Lösung verwendet, und für
>> kleine Devices sollte das wohl auch so bleiben.  Für größere µCs ist das
>> m.E. nicht mehr sinnvoll, insbesondere für Shifts, die ja in vielen
>> Programmen eine zentrale Rolle spielen.  Allerdings hat gcc keine Info
>> über die Speichergröße, diese kann nur grob durch andere Features wie
>> AVR_HAVE_JMP_CALL nach unten abgeschätzt werden.
>
> [...] Wäre es sinnvoll, eine Option "-relax-size" oder ähnlich
> einzuführen?

Nein.  Erste Direktive sollte sein, dass der Compiler ohne solche 
Optionen guten Code erzeugt.  Zudem wäre die Option keine 
Multilib-Option — nicht einmal -O2 oder -Os sind Multilib-Optionen. 
D.h. die Option wirkt nicht auf Code in Standardbibliotheken.  In der 
Entwicklungsphase kann so eine Option ganz sinnvoll sein, z.B. um 
Codeerzeugung oder Benchmarks zu vergleichen.

avr-gcc bietet genug Optimierungspotential und -möglichkeiten: Als 
Bitgefummel, als Schleife, als transparenter Libcall oder ABI-Call, 
Expansion zu (Kombination von) anderen Pattern, entweder händisch oder 
implizit über die Kosten, mit oder ohne Vorlauf von Byte-Shifts, 
Implementierung komplexerer Pattern (inc. Move, Extend, Maskierung, 
etc.).  So bietet es sich für Offsets >= 8 an, anstatt "0" als 2. 
Constraint "r" zu nehmen, so dass ein 32-Bit Move mit dem Shift 
verwurstet wird.  Das ist momentan nur für Offsets von 8·n der Fall.

Momentan geht die Flashgröße nur an wenigen Stellen in die Algorithmen 
ein, z.B. bei 64-Bit Division — was dann dazu führen kann, dass bei 
gleichen Werten eine 64-Bit Division schneller ist als eine 32-Bit 
Division

http://gcc.gnu.org/viewcvs/gcc/trunk/libgcc/config/avr/lib1funcs.S?revision=220000&view=markup#l1740

Natürlich ist so etwas auch direkt im Compiler möglich.

> Abgesehen davon versuche ich gerade die Zusammenhänge zwischen
> tatsächlicher Ausgabe des Asm-Codes und der Kostenberechnung zu
> verstehen.

Die Kosten beziehen sich auf RTXe, das sagt ja schon der Name des Hooks. 
Dementsprechend sollte man eher auf RTX-Ebene als auf asm-Ebene denken.

> Die müssen ja aus meiner Sicht möglichst exakt zusammenpassen,
> sonst wir eine eigentlich optimale Variante verworfen,
> weil sie zu hohe (aber falsche) Kosten hat.

Kosten sind so eine Sache.  Spät im Compilevorgang nutzen Kosten nicht 
viel; spätestens mit strict RTL, also nach der Registerallokation, ist 
der Code wegen die durch die Registerallokierung eingeführten 
Abhängigkeiten zwischen Insns so verbacken, dass nicht mehr viel am Code 
gedreht werden kann.  Andererseits müssen halbwegs brauchbare Kosten 
bereits in frühen Passes verfügbar sein, z.B. um Entscheidungen über 
Inlining zu treffen.

Die meisten Möglichkeiten, maschinenspezifische Aspekte in Codeerzeugung 
und -transformation einzugringen ist in non-strict RTL, also in den 
Passes von tree-ssa -> RTl Lowering bis Registerallokation, und darauf 
passen RTX-Kosten schon einigermaßem gut.

> sie stimmen schon jetzt nicht zusammen: z.B. (char)x << 5)
> erzeugter Code:

> swap %0
> lsl %0
> andi %0,0xe0

Das ist kein Code, das ist Text ;-) insbesondere ist das kein $0 << 5,
sondern:

$0 <<<= 4
$0 <<= 1
$0 &= 0xe0

 
d.h. es sind 3 Insns, welche zusammen ein $0 << 5 ergeben.

> tatsächliche Kosten wären 3*COSTS_N_INSNS berechnet werden aber 5:

"Besser als erwartet" würde Volker Pispers sagen :-)

> TARGET_RTX_COSTS wird in einem anderen Kontext (und viel früher)
> aufgerufen als die Erzeugung des Codes,

Es wird i.W. schon mit der Codeerzeugung verwendet, d.h. der Erzeugung 
von RTL aus tree-SSA.  Der Compiler arbeitet ja nicht auf 
Assembler-Ebene.  Natürlich versucht man, zum "1 Insn pro 
Assembler-Instruktion" zu gelangen, aber das ist zum einen nur 
angenähert möglich und zum anderen kann die Abbildung auf asm recht 
aufwändig und kaum als Kosten modellierbar sein.  So braucht allein die 
Ausgabe von "a += b" durch avr_out_plus_1 et. al über 600 Zeilen Code.

> Wie geht man in so einem Fall vor? pessimistisch (5),
> optimistisch (3), oder irgendwo dazwischen?

RTX-Kosten sind eher als Erwartungswerte für die Kosten des erzeugten 
asm anzusehen.

Was auch zu berücksichtigen ist sind die Verhältnisse unterschiedlicher 
Kosten untereinander.  Shift wird z.B. einen Zusammenhang haben mit 
Multiplikation und Addition da sowohl + als auch * einen Shift 
darstellen können (und teilweise auch umgekehrt).  Die Kosten von MUL 
wiederum sind u.U. billiger gemacht damit erweiternde Multiplikation wie 
16x16=32 oder 32x32=64 verwendet wird, d.h. teilweise hat man paradoxe 
Kosten etwa wenn für die Kosten zweier Operationen gilt cost(A + B) < 
cost(A) + cost(B) oder sogar cost(A + B) < cost(A).

Michael Reinelt schrieb:
> Die Länge (in Words) der Operation.

Ja, die ist erforderlich weil Binutils Sprünge nicht relaxen können, 
zumindestnicht in die richtige Richtung.  Daher muss die Mindestgröße 
der asm-Sequenz bestimmt werden.  Optimal ist natürlich die exakte 
Größe.

> Es ist aber leider nicht ganz einfach, das "richtig" zu machen, da zu
> dem Zeitpunkt einfach noch zu wenig über das "Umfeld" bekannt ist

Ja, so ist das... Es hängt z.B. ab von

- der Constraint-Alternative
- ob ein Scratch-Register verfügbar ist wie in einigen RTL-Peepholes
- ob cc0 (Condition Code) so gesetzt wird, daß er einen evtl.
  folgenden Vergleich überflüssig machen kann

> geht der GCC von einer Zwei- oder Drei-Adress-Maschine aus?

Weder noch.  In non-strict RTL werden die Operanden durch Prädikate 
beschrieben wie dem "register_operand" oder "const_int_operand" von 
oben.  In strict RTL bestimmen die Constraints über die Operanden. Den 
Übergang bewerkstelligt der Registerallokator.

> reg1 = reg1 op reg2 versus reg1 = reg2 op reg3

Als Constraints ausgedrückt wäre das "=r,0,r" bzw. "=r,r,r" wobei die 
Alternativen im md nicht in einer Zeile stehen sondern in einer Spalte, 
d.h.

(set (match_operand:MM 0 "register_operand"        "=r,r")
     (op:MM (match_operand:QI 1 "register_operand"  "0,r")
            (match_operand:QI 2 "register_operand"  "r,r")))

hat 2 Constraintalternativen.

Dazu ist es hilfreich, Komponenten einer Insn und deren Funktion zu 
kennen:

1) Name
2) Pattern bestehend aus RTXen, Prädikaten und Constraints
3) Condition
4) Template
5) Attribute
6) Evtl. Code- und / oder Mode-Iteratoren

Ditto define_expand, define_split, define_insn_and_split, 
define_peephole2 und define_peephole.

> Diese Information wäre enorm wichtig für die Kostenberechnung:

Ist dort aber nicht verfügbar.  GCC enthält keine Algorithmen, die 
komplexer sind als lineraristisch, und es gibt keine spekulative 
Codeerzeugung.

Kein Anwender würde akzeptieren, wenn der Compiler 1/2 Stunde über einem 
kleinen Programm brüten würde so wie ein Großmeister über den besten 
Schachzug (und ihn dann doch nicht findet ;-))

> ob ein Scratch-Register zur Verfügung steht. Diese Info wird bei
> der Kostenberechnung mit ziemlicher Sicherheit nicht zur Verfügung
> stehen.

Jepp.  Es gibt auch mehrere Wege sich ein Scratch-Register zu besorgen. 
Im avr BE wird nicht selten ein Scratch nicht explizit angefordert oder 
generiert, sondern ein rtl-Peephole angewandt falls ein Scratch der 
benötigten Klasse verfügbar ist. Beispiel:

http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/config/avr/avr.md?revision=220000&view=markup#l4102
http://gcc.gnu.org/viewcvs/gcc/trunk/gcc/config/avr/avr.md?revision=220000&view=markup#l4017

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Michael Reinelt schrieb:
>> [...] Wäre es sinnvoll, eine Option "-relax-size" oder ähnlich
>> einzuführen?
>
> Nein.  Erste Direktive sollte sein, dass der Compiler ohne solche
> Optionen guten Code erzeugt.  Zudem wäre die Option keine
> Multilib-Option — nicht einmal -O2 oder -Os sind Multilib-Optionen.
> D.h. die Option wirkt nicht auf Code in Standardbibliotheken.

Guter Punkt, ok, kein relax-size

> avr-gcc bietet genug Optimierungspotential und -möglichkeiten: Als
> Bitgefummel, als Schleife, als transparenter Libcall oder ABI-Call,
> Expansion zu (Kombination von) anderen Pattern, entweder händisch oder
> implizit über die Kosten, mit oder ohne Vorlauf von Byte-Shifts,
> Implementierung komplexerer Pattern (inc. Move, Extend, Maskierung,
> etc.).  So bietet es sich für Offsets >= 8 an, anstatt "0" als 2.
> Constraint "r" zu nehmen, so dass ein 32-Bit Move mit dem Shift
> verwurstet wird.  Das ist momentan nur für Offsets von 8·n der Fall.
Ui, da hab ich noch viel zu lernen :-)

> Momentan geht die Flashgröße nur an wenigen Stellen in die Algorithmen
> ein,

Ha, klingt gut! AVR_HAVE_SPH bietet sich heir wirklich an...

> Die Kosten beziehen sich auf RTXe, das sagt ja schon der Name des Hooks.
> Dementsprechend sollte man eher auf RTX-Ebene als auf asm-Ebene denken.

Jein. ein <<12 sieht auf RTX-Ebene ja erstmal "billig" aus, ist es aber 
im Endeffekt nicht.

>> (char)x << 5)
>> erzeugter Code:

> swap %0
>> lsl %0
>> andi %0,0xe0

>
> Das ist kein Code, das ist Text ;-) insbesondere ist das kein $0 << 5,
> sondern:

$0 <<<= 4
> $0 <<= 1
> $0 &= 0xe0

>  
> d.h. es sind 3 Insns, welche zusammen ein $0 << 5 ergeben.

Grummel du hast recht. Hier wird "doppelt gemoppelt": im avr.c wird 
für ein <<5 genau diese Optimierung durchgeführt; die kommt aber im 
Endeffekt nie zur Anwendung, weil im md schon obige Ersetzung 
stattfindet.

>> Wie geht man in so einem Fall vor? pessimistisch (5),
>> optimistisch (3), oder irgendwo dazwischen?
>
> RTX-Kosten sind eher als Erwartungswerte für die Kosten des erzeugten
> asm anzusehen.

Verstanden. Trotzdem wüsste ich jetzt nicht wie ich die Kosten für 
obiges Beispiel ansetzen sollte (nehmen wir mal an <<5 würde nicht im md 
zerlegt). Aber wenn du sagst "Erwartungswert", so würde ich es als sehr 
wahrscheinlich ansehen, dass final immediate-taugliche Register zur 
Verfügung stehen, und damit "erwarte" ist Kosten von 3. Richtig?

Nebenfrage: wie geht der GCC vor, wenn er zwei Alternativen hat, mit 
gleichen Kosten und gleicher Länge?

>> geht der GCC von einer Zwei- oder Drei-Adress-Maschine aus?
>
> Weder noch.  In non-strict RTL werden die Operanden durch Prädikate
> beschrieben wie dem "register_operand" oder "const_int_operand" von
> oben.  In strict RTL bestimmen die Constraints über die Operanden. Den
> Übergang bewerkstelligt der Registerallokator.

Ah ja, verstanden!

Das heisst aber auch, dass ich im Endeffekt doch auch das md-File 
zumindest lesen können muss :-(

ich hab da zwar einen kleinen Startvorteil, da ich vor gefühlten 100 
jahren Lisp im AutoCAD-Umfeld programmiert habe, und auch bei emacs da 
und dort damit in Berührung gekommen bin, aber "per Du" bin ich mit dem 
zeug noch weit nicht....

> Als Constraints ausgedrückt wäre das "=r,0,r" bzw. "=r,r,r" wobei die
> Alternativen im md nicht in einer Zeile stehen sondern in einer Spalte,

Hmmm... ich habe mal versucht ein (einfaches?) Beispiel zu verstehen, eh 
gleich mein ashlqi3 (Apropos: Welche bedeutung hat das "3"? ashl ist 
klar, qi ist klar)

(define_insn "*ashl<mode>3"
  [(set (match_operand:ALL1 0 "register_operand"              "=r,r,r,r,!d,r,r")
        (ashift:ALL1 (match_operand:ALL1 1 "register_operand"  "0,0,0,0,0 ,0,0")
                     (match_operand:QI 2 "nop_general_operand" "r,L,P,K,n ,n,Qm")))]
  ""
  {
    return ashlqi3_out (insn, operands, NULL);
  }
  [(set_attr "length" "5,0,1,2,4,6,9")
   (set_attr "adjust_len" "ashlqi")
   (set_attr "cc" "clobber,none,set_czn,set_czn,set_czn,set_czn,clobber")])

Die teile glaube ich zu verstehen (korrigiere mich bitte wenn ich falsch 
liege)

ALL1 sind alle 8-bit-modi (QI, QQ, UQQ; letztere für fract)

das "=" steht fürs Ergebnis, die anderen beiden für die operanden

Alternativen sind die Spalten

"0" steht für "Operand-Register = Ergebnis-Register" (also meine obige 
"2-adress-maschine")

"r" meint "irgendein" Register

"d" ist ein immediate-Register, !d also ein dafür nicht taugliches?

die dritte zeile versteh ich nicht wirklich, vereinzelt finde ich die im 
constraints.md; Qn aber nicht....

Vermutlich hängt das aber mit den Attributen "length" und "cc" zusammen

length wir hier also schon berechnet, trotzdem gibt es noch das 
"adjust_length" im avr.c?

"cc"?

Der Teil alleine für ashlqi im md ist ja schon recht lang.... z.T. habe 
ich eine Vorstellung was passiert (alternativen/zerlegungen für 
verschiedene Optimierungen) bei vielen fehlt aber noch der Durchblick...

Gibts vielleicht irgendwo ein kommentiertes Beispiel (muss nicht << 
sein, eine einfache Operation halt)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Ich glaub ich brauche etwas Hilfe beim Verstehen des avr.md

ich hab mal versucht die relevanten teile für den 8-bit-shift-left 
zusammenzusuchen, werde daraus aber nicht schlau:

(define_expand "ashl<mode>3"
  [(set (match_operand:ALL1 0 "register_operand" "")
        (ashift:ALL1 (match_operand:ALL1 1 "register_operand" "")
                     (match_operand:QI 2 "nop_general_operand" "")))])

Das sieht zwar gut aus, aber irgendwie fehlt mir da was? Wohin wird 
denn expandiert, was ist das Ergebnis? Die Beispiele und die Doku zu 
define_expand sind immer irgendwie länger...

(define_insn "*ashl<mode>3"
  [(set (match_operand:ALL1 0 "register_operand"              "=r,r,r,r,!d,r,r")
        (ashift:ALL1 (match_operand:ALL1 1 "register_operand"  "0,0,0,0,0 ,0,0")
                     (match_operand:QI 2 "nop_general_operand" "r,L,P,K,n ,n,Qm")))]
  ""
  {
    return ashlqi3_out (insn, operands, NULL);
  }
  [(set_attr "length" "5,0,1,2,4,6,9")
   (set_attr "adjust_len" "ashlqi")
   (set_attr "cc" "clobber,none,set_czn,set_czn,set_czn,set_czn,clobber")])

Hier dachte ich zuerst, das wäre die zentrale Definition von ashlqi3, 
allerdings sagt mir die Doku dass Namen die mit einem Stern beginnen 
(was hier ja der Fall ist) nur zu Debugging-Zwecken da sind, und sonst 
eigentlich keine Funktion haben???

Der rest sind dann nur diverse Spezialfälle (meist mit const_int), aber 
irgendwie find ich die Basis nicht? Suche ich falsch? Wo ist mein 
Denkfehler?

Und dann habe ich noch folgendes entdeckt, was ich auch nciht verstehe:

;; Optimize if a scratch register from LD_REGS happens to be available.

(define_peephole2 ; ashlqi3_l_const4
  [(set (match_operand:ALL1 0 "l_register_operand" "")
        (ashift:ALL1 (match_dup 0)
                     (const_int 4)))
   (match_scratch:QI 1 "d")]
  ""
  [(set (match_dup 2) (rotate:QI (match_dup 2) (const_int 4)))
   (set (match_dup 1) (const_int -16))
   (set (match_dup 2) (and:QI (match_dup 2) (match_dup 1)))]
  {
    operands[2] = avr_to_int_mode (operands[0]);
  })

"scratch register" hat mich zuerst in die Irre geführt, ein paar der 
optimalen Shifts brauchen zwar ein Scratch register, <<4 aber nicht. 
Dafür hätte die Operation gerne ein High-Register, um ein andi 
(AND-Immediate) einzusetzen. Ich vermute genau das soll hier passieren: 
Versuchen ein High-Register zu kriegen. Allerdings verstehe ich 
überhaupt nicht was wie wo warum...

und was macht schlußendlich das "operands[2] = avr_to_int_mode 
(operands[0]);"?

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Johann L. schrieb:

> Ein <<12 sieht auf RTX-Ebene ja erstmal "billig" aus, ist es aber
> im Endeffekt nicht.

Es sieht so billig aus, wie es die RTX-Kosten sagen.  Wenn die nicht 
stimmen müssen sie eben angepasst werden.

>>> (char)x << 5)
>> d.h. es sind 3 Insns, welche zusammen ein $0 << 5 ergeben.
>
> Grummel du hast recht. Hier wird "doppelt gemoppelt": im avr.c wird
> für ein <<5 genau diese Optimierung durchgeführt; die kommt aber im
> Endeffekt nie zur Anwendung, weil im md schon obige Ersetzung
> stattfindet.

Ja, dieser split für d-Regs geschieht immer.  Idee ist, das entstehende 
ANDI evtl. gegen eine folgende Maskierung zu optimieren.

>> RTX-Kosten sind eher als Erwartungswerte für die Kosten des
>> erzeugten asm anzusehen.
>
> Trotzdem wüsste ich jetzt nicht wie ich die Kosten für obiges
> Beispiel ansetzen sollte (nehmen wir mal an <<5 würde nicht im md
> zerlegt).

Der Split geschieht immer, wie gesagt.  Um Kosten richtig einzuschätzen 
braucht's schon etwas Erfahrung, und was der Compiler so alles treiben 
kann bekommt man mit einfachen Testfällen eben auch nicht raus; da muß 
man schon eine Vorstellung von haben.  Bei hoher Registerlast sieht der 
Code dann anders aus, hier ein Testfall, bzw. auch mit "long r24":

void g5 (void)
{
    register long long r16 asm ("16");
    register long long r24 asm ("24");
    register unsigned char r9 asm ("9");

    asm volatile ("; " : "=r" (r9), "=r" (r16), "=r" (r24));
    r9 <<= 5;
    asm volatile ("; " : "+r" (r9), "+r" (r16), "+r" (r24));
}

> Aber wenn du sagst "Erwartungswert", so würde ich es als sehr
> wahrscheinlich ansehen, dass final immediate-taugliche Register
> zur Verfügung stehen, und damit "erwarte" ist Kosten von 3.

Davon kann man ausgehen, ja.  Wobei in komplexeren Programmen die Kosten 
effektiv größer sein können.

> Nebenfrage: wie geht der GCC vor, wenn er zwei Alternativen hat, mit
> gleichen Kosten und gleicher Länge?

Die Länge wird nur für Sprungoffsets gebraucht und ist erst recht spät 
(korrfekt) verfügbar, in manchen Fällen sogar garnicht (z.B. peephole). 
Manchaml wird die Länge auch für die Codeerzeugung verwendet, z.B. in 
avr_out_plus oder avr_prologue_setup_frame.  Die unterschiedlichen 
Varianten sind jeweils so kompliziert, daß a priori nicht zu sagen ist, 
was besser ist.  Die Varianten werden generiert und die billigste 
verwendet.

Was expand mit gleichen Kosten umgeht weiß ich nicht.  combine verwendet 
bei gleichen Kosten das komplexere Pattern.

> Das heisst aber auch, dass ich im Endeffekt doch auch das md-File
> zumindest lesen können muss :-(

Ja, auf jeden Fall!  Wenn du besseren Code ausgibt musst du ja sicher 
sein, daß z.B. cc0 (SREG) noch passt, sonst kann sowas passieren wie 
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39633#c10

Wenn man die 32-Bit Shifts einer Rosskur unterzieht dann ist wohl auch 
die libgcc anzupassen :-)

> Welche bedeutung hat das "3"?

Anzahl der Operanden.

> (define_insn "*ashl<mode>3"
>   [(set (match_operand:ALL1 0 "register_operand" 
> "=r,r,r,r,!d,r,r")
>         (ashift:ALL1 (match_operand:ALL1 1 "register_operand" 
> "0,0,0,0,0 ,0,0")
>                      (match_operand:QI 2 "nop_general_operand" 
> "r,L,P,K,n ,n,Qm")))]
>   ""
>   {
>     return ashlqi3_out (insn, operands, NULL);
>   }
>   [(set_attr "length" "5,0,1,2,4,6,9")
>    (set_attr "adjust_len" "ashlqi")
>    (set_attr "cc" 
> "clobber,none,set_czn,set_czn,set_czn,set_czn,clobber")])

> das "=" steht fürs Ergebnis, die anderen beiden für die operanden

Das Ergebnis zählt auch als Operand. (set a b) hat Seiteneffakt auf a, 
das ist der einzige Unterschied zu ashift — neben der Semantik 
natürlich.

> "d" ist ein immediate-Register, !d also ein dafür nicht taugliches?

Nein, ! gehört zu den Constraint-Kosten:

http://gcc.gnu.org/onlinedocs/gccint/Multi-Alternative.html#Multi-Alternative
http://gcc.gnu.org/onlinedocs/gccint/Modifiers.html#Modifiers

> Qn

"Qm" ist die Vereinigung von "Q" und "m".

> "cc"?

Eine der 3 Möglichkeiten im GCC Condition Codes zu modellieren, hier 
cc0, siege z.B. RTL für nen Branch. cc0 ist eine i.W. implizite 
Modellierung des SREG, siehe z.B. avr_notice_update_cc.

> Der Teil alleine für ashlqi im md ist ja schon recht lang.... z.T. habe
> ich eine Vorstellung was passiert (alternativen/zerlegungen für
> verschiedene Optimierungen) bei vielen fehlt aber noch der Durchblick...

Mit Optimierungen hat das eigentlich nix zu tun, es ist lediglich ein 
Teil der Beschreibung von 8-Bit Shifts.

Michael Reinelt schrieb:

> (define_expand "ashl<mode>3"
>   [(set (match_operand:ALL1 0 "register_operand" "")
>         (ashift:ALL1 (match_operand:ALL1 1 "register_operand" "")
>                      (match_operand:QI 2 "nop_general_operand" "")))])
>

>
> Das sieht zwar gut aus, aber irgendwie fehlt mir da was? Wohin wird
> denn expandiert, was ist das Ergebnis? Die Beispiele und die Doku zu
> define_expand sind immer irgendwie länger...

hmmm, in dem Fall dient der Expander genauso aus wie "*ashlqi3", d.h. 
man hätte den Expander auch weglassen können und bei der Insn das "*" 
weg.  Dann wäre "ashlqi3" ein Standard-Insn und ihr Pattern würde zur 
Expansion verwendet.

Das "Ergebnis" ist RTL, das aus tree erzeugt wird.  Die erste Dump ist 
.expand.

Expander werden zum Expandieren verwendet, Insns zum Expandieren und zum 
Matching.

Wenn z.B. combine eine komplexes Pattern zusammenbastelt und es gibt 
eine passende Insn, dann wird diese Insn anstatt der alten Insns (aus 
denen das Pattern gebastelt wurde) verwendet.  Und Insns beschreiben 
auch die Relaods für den Register-Allokator und können beliebig viele 
Attribute (define_attr) haben, z.B. für Länge, Scheduler, enabled, oder 
was auch immer.

Wenn eine Insn einen gültigen C-Identifier als Name hat, dann erzeugen 
die gentools des Compilers eine entsprechende Funktion in insn-emit.c; 
hier gen_ashlqi3.  Schau einfach mal nach insn-emit.c, macht es 
vielleicht etwas klarer. Andere wichtige, aus .md erzeugte Quellen sind 
*.c im gleichen Verzeichnis.

Mit Expandern kann komplexerer Code ausgegeben werden, siehe 
"push<mode>1".

> Hier dachte ich zuerst, das wäre die zentrale Definition von ashlqi3,
> allerdings sagt mir die Doku dass Namen die mit einem Stern beginnen
> (was hier ja der Fall ist) nur zu Debugging-Zwecken da sind, und sonst
> eigentlich keine Funktion haben???

Der Name hat sonst keine Funktion, d.h. es gibt keine gen_foo() für 
die Insn.  Der Name (falls vorhanden, er kann auch einfach "" sein) 
erscheint z.B. im asm bei -dp oder höher und auch in vielen RTL-Dumps.

> Der rest sind dann nur diverse Spezialfälle (meist mit const_int), aber
> irgendwie find ich die Basis nicht?

Schau mal nach addqi3, oder pushqi1, die sind schön einfach.  Im .md 
wird sogar gen_pushqi1() verwendet.

> Und dann habe ich noch folgendes entdeckt, was ich auch nicht verstehe:

> ;; Optimize if a scratch register from LD_REGS happens to be available.
> 
> (define_peephole2 ; ashlqi3_l_const4
>   [(set (match_operand:ALL1 0 "l_register_operand" "")
>         (ashift:ALL1 (match_dup 0)
>                      (const_int 4)))
>    (match_scratch:QI 1 "d")]
>   ""
>   [(set (match_dup 2) (rotate:QI (match_dup 2) (const_int 4)))
>    (set (match_dup 1) (const_int -16))
>    (set (match_dup 2) (and:QI (match_dup 2) (match_dup 1)))]
>   {
>     operands[2] = avr_to_int_mode (operands[0]);
>   })

> "scratch register" hat mich zuerst in die Irre geführt, ein paar der
> optimalen Shifts brauchen zwar ein Scratch register, <<4 aber nicht.

Aber es gibt besseren Code. Ohne d-Scratch ist der Code 4 x LSL, mit 
d-Scratch nur SWAP + LDI + AND.

> Dafür hätte die Operation gerne ein High-Register, um ein andi
> (AND-Immediate) einzusetzen. Ich vermute genau das soll hier passieren:

Nein, dieses peep2 passt nur dann, wenn es ein d-Reg übrig hat und $0 in 
einem l-Reg gelandet ist.  Wie ein Sratch explizit angefordert wird 
siehst du z.B. in der 3. Alternative von addsi3.  Das erhöht dann aber 
die Registerlast, was das obige peep2 nicht tut.

> operands[2] = avr_to_int_mode (operands[0]);

Meine Faulheit.  Das "patcht" QQmodes zu QImode, damit werden dann für 
QQ die entsprechenden QI insn verwendet.  War einfacher als alle 
möglichen insn für den Zoo von sat und accum und fixed modes zu 
schreiben, und das .md ist auch einfacher zu lesen als (fast) alle Insns 
mit Mode-Iteratoren zu versehen.  Der erzeugte Code ist ja eh gleich.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Guten Morgen Johann,

erstmal Danke für deine wie immer ausführliche Antwort!

> Ja, dieser split für d-Regs geschieht immer.  Idee ist, das entstehende
> ANDI evtl. gegen eine folgende Maskierung zu optimieren.

Ha! Kapiert, ausprobiert, und für genial befunden!

>> Aber wenn du sagst "Erwartungswert", so würde ich es als sehr
>> wahrscheinlich ansehen, dass final immediate-taugliche Register
>> zur Verfügung stehen, und damit "erwarte" ist Kosten von 3.
>
> Davon kann man ausgehen, ja.  Wobei in komplexeren Programmen die Kosten
> effektiv größer sein können.
Ja, auch verstanden.

> Wenn man die 32-Bit Shifts einer Rosskur unterzieht dann ist wohl auch
> die libgcc anzupassen :-)

>> "d" ist ein immediate-Register, !d also ein dafür nicht taugliches?
> Nein, ! gehört zu den Constraint-Kosten:
Ok, hab mich von "! = not" in die Irre führen lassen.

>> "scratch register" hat mich zuerst in die Irre geführt, ein paar der
>> optimalen Shifts brauchen zwar ein Scratch register, <<4 aber nicht.
>
> Aber es gibt besseren Code. Ohne d-Scratch ist der Code 4 x LSL, mit
> d-Scratch nur SWAP + LDI + AND.

Der hat mich jetzt Nerven gekostet... Ich musste lange darüber brüten, 
plötzlich hat es "Pling!" gemacht. Ja, verstanden, ebenfalls genial!

Allerdings bin ich auch ein Stück weit ernüchtert: Anfangs bin ich davon 
ausgegangen, mich auf das avr.c zu konzentrieren, und das md links 
liegen zu lassen. Das wird so nicht funktionieren :-( Optimierungen im 
md haben wesentlich mehr Potential...

Wo ich noch unsicher bin: im C-Teil werden viele Code-Varianten 
berücksichtigt, die so eigentlich nie vorkommen (sollten): z.B. ein 
(char)x << 4, das dürfte es nie ins .c schaffen, weils im md schon zu 
einem rotate(4)+and umgewandelt wird. Jetzt kann mans stillschweigend 
trotzdem ausprogrammieren (der nächste braucht so wie ich wieder 
ewig+2tage ums zu verstehen), zumindest mit einem Kommentar versehen, 
überhaupt weglassen, oder eine Exception werfen, weil wenns trotzdem 
verwendet wird stimmt u.U. im md was nicht...

Ein paar andere Fragen haben sich noch aufgetan:

Zum einen habe ich mir mein Beispiel von vor ein paar tagen nochmal 
angeschaut:

uint32_t f3 (const uint32_t x) {
    return x << 3;
}

Da wird ja "eigenartiger" Code erzeugt, du meintest schon die Kosten 
wären da nicht ganz exakt...

im .s mit -mlog=rtx_costs -dP -da -dA sieht das ausschnittsweise so aus:

 ; (insn 18 6 23 (set (reg:SI 24 r24 [47])
 ;         (reg/v:SI 22 r22 [orig:44 x ] [44])) shift.c:8 95 {*movsi}
 ;      (expr_list:REG_DEAD (reg:QI 23 r23)
 ;         (expr_list:REG_DEAD (reg:QI 22 r22)
 ;             (nil))))
/* DEBUG: cost = 0.  */
        movw r26,r24     ;  tmp47, x     ;  18  *movsi/1        [length = 2]
        movw r24,r22     ;  tmp47, x

Die beiden movw scheinen also nix zu kosten, was vermutlich so nicht 
stimmt. ich habe nun versucht nachzuvollziehen, wie es a) überhaupt dazu 
kommt, und b) woher die Kosten = 0 kommen.

I failed :-(


Zweitens: Beim eigentlichen Ausgangspunkt, dem "Jucken am Hintern" (Eric 
S. Raymond):

uint32_t f2 (const uint8_t x) {
    return (uint32_t)x << 12;
}

macht er ja zuerst ein zero extend bevor er shiftet. Dieses zero extend 
ist (z.T) nicht notwendig; zumindest nicht wenn man das <<12 in ein <<8 
und ein <<4 zerlegt. "Wegmachen" tut man das auch wieder in der md, mit 
einer peephole-Optimierung, die das Muster erkennt? Kennst du da aus dem 
Stegreif ein Beispiel, welches ich studieren könnte?


Werden solche Zerlegungen/Umwandlungen (peephole) eigentlich mehrfach 
aufgerufen? z.B. hab ich eine Zerlegung von x<<12 in (x<<8)<<4 , wenn 
ich nun eine Zerlegung x<<20 => (x<<8)<<12 mache, kann ich davon 
ausgehen dass der <<12-teil von der ersten Zerlegung wieder gefunden 
wird? (eine Art "Rekursion"?)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Und weitere Fragen:

Constraints: "=r" mit "0" beim ersten Operanden heisst ja, Resultat und 
Operand1 sind im selben register. "=" heisst Register wird geschrieben. 
Streng genommen müsste das doch "+" sein (Operand wird gelesen und 
geschrieben), das "wird gelesen" ergibt sich aber implizit aus dem "0"?

Alternativen: ich hab mir mal eine Tabelle zu ashlqi3 gemacht:

#|Constraint |len| cc      | remark
-|-----------|---|---------|-----------------------------------------
1|= r, 0, r  | 5 | clobber | any register
2|= r, 0, L  | 0 | none    | << 0
3|= r, 0, P  | 1 | set_czn | << 1
4|= r, 0, K  | 2 | set_czn | << 2
5|=!d, 0, n  | 4 | set_czn | LD_REGS
6|= r, 0, n  | 6 | set_czn | n = immediate integer
7|= r, 0, Qm | 9 | clobber | Q = Y or Z pointer; m = memory operand

Zeile 3, 4 und 6 unterscheiden sich nur in "length", diese wird aber 
ohnehin per "adjust_length" neu berechnet. Die Alternativen wären also 
nach meinem Wissensstand nicht nötig. Ich hab aber sicher wieder was 
übersehen, oder?

Zeile 5 ist mir auch unklar: "d" = LD_REGS ist ja eigentlich gut, weil 
mit LD_REG kann man praktischerweise das andi sofort anwenden. Das ! 
heisst aber "nimm eher nicht" (Zitat "Disparage severely the 
alternative")

Zeile 2: das wäre ein x<<0. Kommt das überhaupt soweit durch, wird das 
nicht bereits viel viel früher vom Middle-dings schon als "sinnlos" 
wegoptimiert?

Zu Zeile 7 habe ich beschlossen, dass ich das jetzt noch nicht verstehen 
muss :-)

Spalte cc: Hier wird eingetragen, inwiefern eine Operation das SREG 
(möglicherweise) ändert. ich vermute mal:
none = SREG wird nicht angetastet
clobber = SREG wird u.U. komplett durch den Fleischwolf gedreht, es ist 
nicht mal sicher ob es anschließend überhaupt noch ein SREG gibt
set_czn = Carry, Zero- und Negative-Flag wird möglicherweise verändert?


Ich beginne langsam zu erahnen welche Komplexität da dahintersteckt. Mal 
sehr hypotetisch angenommen, ich würde für <<3 einen ultimativen, bisher 
unbekannten Assembler-befehl finden, der in 1/4 CPU-Zyklus um 3 shiftet 
(die haben nur den Barrel-Shifter gut versteckt, wegen NSA und so...). 
ich müsste:

- im .md dafür sorgen dass diese Option auch wahrgenommen wird
- im .c (oder im .md) den bis dato unbekannten OpCode irgendwie ausgeben
- im .md die Länge der neuen Operation hinterlegen
- im .c an der richtigen Stelle adjust_length anpassen
- im .c die richtigen TARGET_RTX_COSTS hinterlegen
- im .md nach sehr genauem nachdenekn eintragen, wie sich das SREG 
ändern könnte

und ich hab sicher noch 7 Stellen vergessen...

Phew...

[Michael R. (Firma: Brainit GmbH) (fisa)]

ich finde da echte Perlen, auf die ich niemals nicht selber gekommen 
wäre...

Frage: Wie krieg ich z.B. 32 in r1 geladen, ohne ein anderes Reg zu 
benutzen? (Hint: auf r0..16 geht kein load immediate)

Antwort:

set
bld r1,5

Aber das nur nebenbei... mich beschäftigt grad was anderes: ich bin ja 
nach wie vor restlos begeistert von dem Trick, das <<4 durch ein ROT + 
AND zu ersetzen, und zwar schon direkt in den insns, weil das AND u.U. 
mit einem weiteren AND "verschmolzen" wird.

Nun gibt es ähnliche Konstrukte in den "breiteren" Varianten HI und SI, 
und ich frage mich ob man da ähnlich trickreich vorgehen könnte. Dazu 
müssten wie Register/Werte/Operanden in Lo- und Hi-Byte zerlegt (und 
vielleicht auch wieder zusammengebaut) werden. Geht sowas überhaupt, und 
wäre das sinnvoll?

[Michael R. (Firma: Brainit GmbH) (fisa)]

Ich hätte da noch was gefunden...

es gibt eine Optimierung "subregs", die eigentlich einen Teil von dem 
erledigt, was ich zu optimieren versuche: Diese zerlegt Operationen mit 
Multi-Register-Operanden (ein 16-bit-Wert steht im AVR ja in zwei 
Registern, 32bit=>4 usw) in kleinere Operationen auf einzelnen 
Registern.

Im speziellen beim Shift wird geprüft, ob es sich um eine konstantes 
shift um mehr als 8 handelt.

(vereinfachtes) Beispiel: ein 16-Bit-shift-left um 9 wird zerlegt in:
MSB = LSB << 1
LSB = 0

Das scheint auch wunderbar zu funktionieren (übrigens ist das nichts 
AVR-spezifisches, das macht der gcc offensichtlich immer)

ABER: diese Optimierung greift (generell) nur bei BITS_PRO_REGISTER => 
2*BITS_PRO_REGISTER

Anders gesagt: am AVR werden nur Verschiebungen im HImode um 8..15 
geprüft.

Damit fallen die ganzen (ineffizienten) 24- und 32-Bit-Shifts durch den 
Rost.

Was kann man dagegen tun?

lower-subreg.c trau ich mich ehrlich gesagt nicht anzufassen...

[Johann L. (gjlayde)]

Es ist auch möglich auf Teilregistern zu operieren wie im folgenden 
Beispiel:
 

Index: avr.md
===================================================================
--- avr.md  (revision 222054)
+++ avr.md  (working copy)
@@ -3644,6 +3644,55 @@ (define_peephole2
   })
 
 
+(define_insn_and_split "*split.ashlsi.extend";
+  [(set (match_operand:SI 0 "register_operand"                 "=r")
+        (ashift:SI (match_operand:SI 1 "reg_or_extend_operand"  "r")
+                   (match_operand:QI 2 "const_int_operand"      "n")))]
+  "!reload_completed
+   && 16 < INTVAL (operands[2])
+   && 0 != INTVAL (operands[2]) % 8"
+  { gcc_unreachable(); }
+  "&& 1"
+  [;; "*movhi"
+   ;; "extendqihi2"
+   ;; "zero_extendqihi2"
+   (set (match_dup 6)
+        (match_dup 5))
+   ;; "*ashlhi3_const"
+   (set (match_dup 6)
+        (ashift:HI (match_dup 6)
+                   (match_dup 2)))
+   ;; "*movhi"
+   (set (match_dup 4)
+        (match_dup 6))
+   ;; "*movhi"
+   (set (match_dup 3)
+        (const_int 0))
+   ;; "*movsi"
+   (set (match_dup 0)
+        (match_dup 7))]
+  {
+    operands[7] = gen_reg_rtx (SImode);
+    operands[6] = gen_reg_rtx (HImode);
+    operands[2] = plus_constant (QImode, operands[2], -16);
+    operands[3] = simplify_gen_subreg (HImode, operands[7], SImode, 0);
+    operands[4] = simplify_gen_subreg (HImode, operands[7], SImode, 2);
+    if (UNARY_P (operands[1]))
+      {
+        operands[5] = QImode == GET_MODE (XEXP (operands[1], 0))
+          // (*_extend:SI reg:QI) -->  (*_extend:HI reg:QI)
+          // FIXME: $1 must be a pseudo, cf. combine_pseudo_register_operand.
+          ? gen_rtx_fmt_e (GET_CODE (operands[1]), HImode, XEXP (operands[1], 0))
+          // (*_extend:SI reg:HI) -->  reg:HI
+          : XEXP (operands[1], 0);
+      }
+    else
+      {
+        operands[5] = simplify_gen_subreg (HImode, operands[1], SImode, 0);
+      }
+  })
+
+
 ;; "ashlsi3"
 ;; "ashlsq3"  "ashlusq3"
 ;; "ashlsa3"  "ashlusa3"
Index: predicates.md
===================================================================
--- predicates.md  (revision 222054)
+++ predicates.md  (working copy)
@@ -277,3 +277,9 @@ (define_predicate "const_or_immediate_op
   (ior (match_code "const_fixed")
        (match_code "const_double")
        (match_operand 0 "immediate_operand")))
+
+(define_predicate "reg_or_extend_operand"
+  (ior (match_operand 0 "register_operand")
+       (and (match_code "zero_extend,sign_extend")
+            (match_test "register_operand (XEXP (op, 0), QImode)
+                         || register_operand (XEXP (op, 0), HImode)"))))

 
Der 32-Bit Shift wird abgebildet auf einen 16-Bit Shift mit $6.  Subregs 
können den Nachteil haben, dass reload nicht so gut arbeitet wie auf 
vollen Regs und überflüssige Moves erzeugt.

Das Beispiel könnte auch direkt auf Subregs von $0 operieren, aber es 
wird erst ein 32-Bit Pseudo $7 allokiert, in zwei 16-Bit Subregs $3 und 
$4 aufgespalten und die Operation dann auf den Subregs des neuen Pseudos 
ausgeführt (bzw. einem 16-Bit Pseudo $6, das den low-Teil $5 des zu 
schiebenden Wertes beinhaltet).  Das Ergebnis wird dann zu einem 32-Bit 
Wert $7 zusammengesetzt und dann $0 zugewiesen.

Auf neuem  Pseudo anstsatt auf Subregs von $0 zu arbeiten hat auch den 
Vorteil, dass so earlycobber-Situationen vermieden werden, etwa wenn $0 
und $1 überlappen.

Die Insn wird erzeugt in .combine (Dump lesen!) und gesplittet in 
.split1.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Es ist auch möglich auf Teilregistern zu operieren wie im folgenden
> Beispiel:

Ja, genau, ungefähr so wollte ich das auch schreiben ;-) Ich staune 
wieder mal Bauklötze wie du sowas aus dem Ärmel schüttelst.

so ganz hab ichs noch nicht kapiert, aber das prinzip verstanden. 
Resultierender Code schaut auch schon mal um Welten besser aus.

Allerdings krieg ich in einem speziellen Fall einen Compiler Error:

uint32_t f2 (const uint8_t x) {
    return (uint32_t)x << 21;
}

und zwar später, das Ergebnis von .combine schaut nämlich noch richtig 
aus

shift.c: In function 'f2':
shift.c:15:1: error: unrecognizable insn:
 }
 ^
(insn 15 6 16 2 (set (reg:HI 49)
        (zero_extend:HI (reg:QI 24 r24 [ x ]))) shift.c:14 -1
     (nil))
shift.c:15:1: internal compiler error: in extract_insn, at recog.c:2343
0x9dadf3 _fatal_insn(char const*, rtx_def const*, char const*, int, char const*)
        ../../gcc/rtl-error.c:110

der tritt aber nur auf, wenn ein uint8 auf uint32 gecastet wird.

Wenn ich etwas mehr Zeit habe, muss ich mir das nochmal im Detail 
anschauen...

[Johann L. (gjlayde)]

Die Insn ist falsch, siehe das FIXME im Patch.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Die Insn ist falsch

Ach so, und ich dachte schon es wäre was ernstes :-)

Aber ein paar ernst gemeinte Fragen dazu:

was macht gcc_unreachable()? Das hab ich im C-Code schon öfter gesehen, 
sah mir aus wie eine art assert?

mit gen_reg_rtx() "erzeugst" du dir ein reg?

simplify_gen_subreg() "addressiert" ein Sub-Register (also z.B. das MSB 
eines SI?

was macht UNARY_P?

und wenn du dir die zeit nehmen willst, und grad nix besseres zu tun 
hast, sind hier Beitrag "Re: GCC optimiert 32bit Bitoperationen schlecht/gar nicht?" und 
im folgenden beitrag noch ein paar Fragen meinerseits.

[Johann L. (gjlayde)]

Momentan geht meine wenige "avr-Zeit" für andere Sachen drauf, z.B. 
PR65657, PR65296, ...

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Momentan geht meine wenige "avr-Zeit" für andere Sachen drauf, z.B.
> PR65657, PR65296, ...

Sowas hab ich mir schon gedacht... Ich werd mal alleine weiterkämpfen.

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Johann L. schrieb:
>> Die Insn ist falsch
>
> Ach so, und ich dachte schon es wäre was ernstes :-)

Teilweise werden die (teilweise) erweiternden Multiplikationen von 
combine erzeugt, und weil diese MULs durchweg auf transparente Libcalls 
abgebildet werden, würden Hardregs in den Operanden dazu führen, daß das 
Pattern nicht matcht, weil das entsprechende Hardreg geclobbert wird. 
Siehe z.B. mulsi3 Expander und Insn, und wie

long mul65432 (long x)
{
    return x * -65432L;
}

optimiert wird.

Furchbares Denglisch, aber du wolltest ja in einem deutschen Forum 
anstatt in einer einschlägigen Mailingliste ;-)

> was macht gcc_unreachable()?

Eine Assertion, ebenso wie gcc_assert() oder gcc_checking_assert(). 
Gibt im Ernstfall einen etwas netteren Ausstieg, z.B. mit Stacktrace. 
Außerdem muss der default von switch (enum) eh beackert werden um eine 
build-Warnung zu vermeiden.

> mit gen_reg_rtx() "erzeugst" du dir ein reg?

Ein Pseudo.  gen_reg_rtx (QImode) gibt ein QImode Pseudo.  Für ein 
Hardreg, z.B. Z mit unsigned fract wäre es gen_rtx_REG (UHQmode, REG_Z), 
wobei REG_Z nur ein define auf 30 ist -- ungünstig, ist aber nun mal so.

> simplify_gen_subreg() "addressiert" ein Sub-Register (also z.B. das MSB
> eines SI?

Nein es erstellt ein RTX, das den entsprechenden Teil des Registers 
darstellt.  Wenn man das untere Byte von Z will, ist das z.B. (avr ist 
little Endian): simplify_gen_subreg (QImode, ..., UHQmode, 0); oder 
einfach (reg:QI 30).  Für Pseudos gelten andere Regeln:  Ein Pseudo hat 
einen bestimmten MMode, der nicht geändert werden kann; daher muss es in 
ein subreg eingepackt werden, um es anders oder teilweise zuzugreifen. 
Ist in reg 9999 ein z.B. float, und will man dem reg den kleinsten, 
positiven float zuweisen, geht das z.B. per

(set (subreg:SI (reg:SF 9999) 0)
     (const_int 1))

> was macht UNARY_P?

Ist true für univariate RTXe, z.b. Negation, 2er-Komplement, 
sign-Extend.  Steht in rtl.h oder rtl.def.

> Ja, genau, ungefähr so wollte ich das auch schreiben

Wenn es zu viel auf einmal ist, spalte das Pattern einfach mal in 3 
Pattern auf; quasi als Hausaufgabe :-) Einmal für $1 zero_extend, einmal 
für sign_extend, und einmal für ein Register.  Das werden dann zwar 3 
insn-and-split die aber dafür einfacher ausfallen.

Lehrreich ist bestimmt auch, die Optimierung erst post-reload als 
peephole2 zu machen, und dann z.B. per Option zwischen den Varianten 
hin-und herschalten um zu gucken was jeweils passiert.

Oder das FIXME zu fixen, so dass der Compiler für dein Beispiel keinen 
ICE wirft :-)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Ein erster Erfolg: ich hab zwar noch nix optimiert, dafür aber ein 
eigenartiges Verhalten gefunden:

uint8_t f (const uint8_t x) {
    volatile uint8_t y = 255;
    return x << y;
}

wird zu (ausschnittsweise)

ldi r25,lo8(-1)  ;  tmp49,
std Y+1,r25      ;  y, tmp49
ldd r25,Y+1      ;  D.1769, y
rjmp 2f
1:
lsl r24  ; 
2:
dec r25  ;  D.1769
brpl 1b

Das Ergebnis eines left-shifts um 255 bit sollte auf jeden Fall immer 0 
ergeben, da ich weit über die 8 bit hinausschiebe.

Tatsächlich liefert die Funktion immer x zurück, d.h. f(42)=42 und nicht 
0

Der Fehler tritt bei allen shifts > 127 auf, Ursache ist die letzte 
Zeile im Asm-Code: brpl (branch plus): Das ist für alle Werte > 127 
immer falsch.

Ich hab grad versucht herauszufinden was der C-Standard dazu sagt, und 
offensichtlich ist das Verhalten standardkonform:

If the value of the right operand is negative or is greater than or equal
to the width of the promoted left operand, the behavior is undefined.

Aha! man lernt ja nie aus... ich lese das so, dass ein (uint8_t)x<<8 
schon undefined ist...


Back to topic: Meine "Hausübungen" werd ich machen, ich hab momentan 
leider berufsbedingt wenig Zeit. Aber ich arbeite mich in die avr.c ein 
(die überblicke ich schon recht gut), mit der md kämpfe ich noch etwas, 
parallel schraube ich an der lower-subreg herum.

Eine allgemeinere, für mich wichtige Frage hätt ich aber noch: ich habe 
verstanden dass rtx_costs eine zentrale Rolle spielen, bei falschen 
Kosten werden diverse Optimierungen schlicht verworfen (auch in 
lower_subreg). Generell habe ich die Kosten verstanden, bis auf einen 
Fall: Wie geht man mit Kosten um, die zur Compile-Zeit nicht bekannt 
sein können, weil z.B. eine Schleife? Der Bug oben ist genau aus diesen 
Experimenten heraus entstanden...

im avr.c finde ich folgende Zeile:

if (GET_CODE (XEXP (x, 1)) != CONST_INT)
    *total = COSTS_N_INSNS (!speed ? 4 : 17);

(Kostenberechnung eines ashift um einen nicht-konstanten Wert, wird in 
etwa zur Schleife oben)

Zum einen ist mir völlig rätselhaft, woher die 4 resp. 17 kommen. 
Schätz- oder Erfahrungswerte?

Zum zweiten wird das Statement billiger, wenn ich auf size optimiere??? 
Der resultierende asm-output ist ja völlig identisch...

Der eigentliche Hintergrund der Frage: so ein shift lässt sich (ohne 
Barrel-Shifter) etweder als Schleife ausführen, oder durch ein simples 
mul (Multiplizieren) ersetzen. Bei kleinen Werten wird die Schleife 
besser sein, irgendwann wird das mul gewinnen. Vorteil des mul ist ja, 
dass es immer gleich lang braucht.

Wie geht man damit um?

[Stefan E. (sternst)]

Michael Reinelt schrieb:
> ich lese das so, dass ein (uint8_t)x<<8
> schon undefined ist...

Nein, denn hier ist der "promoted left operand" 16 Bit breit.
left operand = uint8_t  =>  promoted left operand = int

[Michael R. (Firma: Brainit GmbH) (fisa)]

Stefan Ernst schrieb:
> Michael Reinelt schrieb:
>> ich lese das so, dass ein (uint8_t)x<<8
>> schon undefined ist...
>
> Nein, denn hier ist der "promoted left operand" 16 Bit breit.
> left operand = uint8_t  =>  promoted left operand = int

Auch wenn explizit auf uint8 gecasted?

ich hab mal schnell etwas gegoogelt, diese promotion scheint ja ein 
Quell unerschöpflicher Mißverständnisse zu sein ;-)

dann müsste aber ein (uint8_t)x<<16 undefined sein, richtig?

und ein (uint16_t)x << 16 auch? (weil wenn implizit promoted wird dann 
nach int) richtig?

[Stefan E. (sternst)]

Michael Reinelt schrieb:
> Auch wenn explizit auf uint8 gecasted?

Klar. Das Promoten ist integraler Bestandteil des Operators und findet 
immer statt. Der Cast ist nur ein zusätzlicher Zwischenschritt vor dem 
Promoten.

Michael Reinelt schrieb:
> dann müsste aber ein (uint8_t)x<<16 undefined sein, richtig?

Ja (bei 16-Bit ints).

Michael Reinelt schrieb:
> und ein (uint16_t)x << 16 auch? (weil wenn implizit promoted wird dann
> nach int) richtig?

Dito.

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Zum zweiten wird das Statement billiger, wenn ich auf size optimiere???

Die Länge einer Codesequenz sagt nicht über deren Dauer aus, dito 
vice-versa.

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Michael Reinelt schrieb:
>> Zum zweiten wird das Statement billiger, wenn ich auf size optimiere???
>
> Die Länge einer Codesequenz sagt nicht über deren Dauer aus, dito
> vice-versa.

Schon klar, aber: Wir reden hier über Kosten = Dauer (ich hoffe 
zumindest) Das Code-Fragment kommt aus der Implementierung von 
TARGET_RTX_COSTS.

Logisch für mich wäre:

ich optimiere auf size: möglichst kurzer Code, dafür möglicherweise 
längere Dauer

ich optimiere auf speed: möglichst schnelle Ausführung, dafür u.U. 
längerer Code

im obigen Beispiel ists aber genau umgekehrt (außer ich hab  mal wieder 
dreifache Verneinungen falsch interpretiert): Wenn ich auf Size 
optimiere, erwarte ich schnellern Code.

[Johann L. (gjlayde)]

Michael Reinelt schrieb:
> Wir reden hier über Kosten = Dauer

Wenn du auf Dauer, also Ausführungszeit optimiert, dann ja.

Wenn du auf Codegröße optimierst, dann sollten die Kosten offenbar die 
Codegröße beschreiben.

Wie sollte denn nach Codegröße optimiert werden, wenn die Kosten der 
jeweiligen Operationen überhaupt nicht beschrieben sind?

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johann L. schrieb:
> Michael Reinelt schrieb:
>> Wir reden hier über Kosten = Dauer
>
> Wenn du auf Dauer, also Ausführungszeit optimiert, dann ja.
>
> Wenn du auf Codegröße optimierst, dann sollten die Kosten offenbar die
> Codegröße beschreiben.
>
> Wie sollte denn nach Codegröße optimiert werden, wenn die Kosten der
> jeweiligen Operationen überhaupt nicht beschrieben sind?

Aaaaaaah! Jetzt ist der Groschen gefallen!

Ich bin irgendwie davon ausgegangen, GCC würde immer beides betrachten 
(Dauer und größe) und abhängig von der Optimierung eins als primäres und 
das andere als sekundäres Sortierkriterium verwenden (z.B. optimierung 
auf Size: kürzsesten Code, wenn es zwei gleich kürzeste gibt, den 
schnellern, und umgekehrt bei Optimierung auf Speed).

Da hätt ich jetzt aber echt selber draufkommen können, dass 
TARGET_RTX_COSTS das ja gar nicht hergibt :-(

Mannmannmannmann, ich werde alt :-(

[Falk B. (falk)]

Was macht das gcc Tuning?

[Michael R. (Firma: Brainit GmbH) (fisa)]

Falk Brunner schrieb:
> Was macht das gcc Tuning?

Liegt leider derzeit auf Eis, wegen dem verflixten BMP280, einem 
DDS-Modul für RM.org, die Lichtorgel ist auch noch nicht fertig, mein 
Raspberry-VDR muss gemacht werden, bei meiner Heizdatenerfassung spinnt 
ein I2C-Sensor, ich soll mit meinen Kids im neu eingerichteten 
Elektronik-Labor Löten üben, der Garten macht Arbeit. Acha ja, und so 
nebenbei, wenn etwas zeit bleibt, müsste ich auch noch die eine oder 
andere Stunde Geld verdienen :-(

Aber ich bleibe dran!

[Falk B. (falk)]

Kann es sein, dass du ein "paar" Projekte zuviel parallel laufen hast?

[Michael R. (Firma: Brainit GmbH) (fisa)]

Falk Brunner schrieb:
> Kann es sein, dass du ein "paar" Projekte zuviel parallel laufen hast?

Wie kommst du denn darauf?

Die Sache mit den Prioritäten, das muss ich noch üben...