Künstliche Intelligenz soll den GCC beschleunigen

Hmm, halte ich für ein Hirngespinst. Keine KI kann auch nur annähernd 
einem versierten Entwickler das Wasser reichen. Und ein "one size fits 
all" Konzept ala Java verschleudert Resourcen ohne Ende, erst recht ohne 
zielspezifische Handoptimierung.

MFG
Falk

UBoot-Stocki wrote:
> Künstliche Intelligenz soll den GCC beschleunigen

Na hoffentlich nicht.

Der AVR-GCC geht mir ja jetzt schon zu weit mit seiner nutzlosen 
Code-Umsortierung (z.B. zusätzliche RJMPs in Schleifen).

Dafür läßt er viele leichte Optimierungsmöglichkeiten aus (z.B. 
Registeroptimierung).


Peter

hmmm, ein bissl finde ich die Neuigkeiten wie bei heise...misleading.

Soweit ich das verstehe wird am GCC selbst nichts geändert.

Vielmehr geht es darum, anhand der Characteristika eines Programmes die 
besten Optimierungsoptionen zu finden und gcc damit zu füttern.

Die in gcc intergrierten Optimierungsalgorithmen sind davon nicht 
betroffen, bzw. nur insoweit, wie sie verschaltert sind oder mit --param 
feinjustierbar sind.

Die "Änderungen" beziehen sich also aufs Tuning der Optionen. Bei den 
neueren gcc-Versionen zählt man allein 140 maschinen/sprachunanhängige 
Optimierungsschalter (gehören zu -f), die zum Teil noch parametrisierbar 
sind (zB das Verhalten von Inlining, insn Scheduling, etc). Hinzu kommen 
die maschinenabhäng Optimierungsschalter (gehören zu -m). Also einige 
Arbeit, Schalter zu finden, die das meiste (bzw das wenigste im Hinblick 
auf Resourcenverbrauch) aus gcc ausholen.

Peter Dannegger wrote:
> UBoot-Stocki wrote:
>> Künstliche Intelligenz soll den GCC beschleunigen
>
> Na hoffentlich nicht.
>
> Der AVR-GCC geht mir ja jetzt schon zu weit mit seiner nutzlosen
> Code-Umsortierung (z.B. zusätzliche RJMPs in Schleifen).
>
> Dafür läßt er viele leichte Optimierungsmöglichkeiten aus (z.B.
> Registeroptimierung).
>
> Peter

Optimierungen an der Registervergabe als "leicht" zu bezeichnen, finde 
ich gewagt. Registerallokierung ist eine der komplexesten Aufgaben eines 
Compilers; zumindest wenn er Werte möglichst in GPRs halten soll. Wenn 
man mal unter gccs Haube schaut, was etwa in den reload Passes abgeht, 
stopft man direkt wieder alle Kabel und Strippen rein und macht die 
Haube gaaanz schnell wieder zu ;-)

Wenn man das o.g. Tool für avr-gcc anwirft, wird man irgendwann 
vielleicht feststellen, dass Optionen wie

  -freorder-blocks
  -freorder-blocks-and-partition
  -freorder-functions

auf einem AVR nicht so sinnig sind, zumindest solange ihm kein 
Instruction-Cache spendiert wird. Und testet mal an und hofft und staunt 
-- oder ist enttäuscht davon --, was

  -fno-reorder-blocks
  -fno-reorder-blocks-and-partition
  -fno-reorder-functions

gcc hervorzaubern lassen.

Hoffend, dass AVR nie einen Instruction Cache bekommen wird,

Johann

Johann L. wrote:

> Optimierungen an der Registervergabe als "leicht" zu bezeichnen, finde
> ich gewagt.

Naja, es gibt öfters mal unnütze MOVs, z.B. hier:

1

  OCR1C = bauddiv-1;

2

 118:   82 2f           mov     r24, r18

3

 11a:   81 50           subi    r24, 0x01       ; 1

4

 11c:   8d bd           out     0x2d, r24       ; 45

Die zu entfernen ist aus menschlicher Sicht leicht.
Der AVR-GCC scheint ja gut zu erkennen, wann eine Variable nicht mehr 
benötigt wird.

Schwieriger stelle ich mir schon Registeroptimierungen über ne ganze 
Funktion vor, z.b. wenn 3 Pointer benötigt werden, diese in X,Y,Z zu 
halten.


>   -fno-reorder-blocks
>   -fno-reorder-blocks-and-partition
>   -fno-reorder-functions

Danke, muß ich gleich mal ausprobieren.


Peter

Die Schalter haben leider nichts gebracht.
Das Reordering in if-Anweisungen und Schleifen wird dadurch nicht 
verhindert.


Peter

Man muß immer beachten was KI eigentlich bedeutet. Das Wort umschreibt 
in der Informatik was ganz anderes als das was sich normale Menschen 
darunter vorstellen.

Man kann zb. mit genetischen Algoerithmen einfach stupid alle möglichen 
Parameter durchprobieren. Auf normelem Wege ist die Komplexität einfach 
zu hoch um jemals zeitlich ein brauchbares Ergebnis erzielen zu können. 
Der GA beschleunigt nur dieses Verfahren der stupiden Suche innerhab 
aller möglichen Kombinationen. Nun, normele Menschen würden sowas nicht 
als KI bezeichnen, Informatiker aber schon ;)

Gleiches gilt für Neuronale Netzwerke, alles künstlich aber intelligent 
würde ich nur das Verfahren bezeichnen nicht das was am Ende rauskommt 
als Ergebnis.

KI würde ich also eher als Komplexe Informatik übersetzen wollen ;)

Gruß Hagen

Peter Dannegger wrote:
> Johann L. wrote:
>
>> Optimierungen an der Registervergabe als "leicht" zu bezeichnen, finde
>> ich gewagt.
>
> Naja, es gibt öfters mal unnütze MOVs, z.B. hier:
>

1

> 

2

>   OCR1C = bauddiv-1;

3

>  118:   82 2f           mov     r24, r18

4

>  11a:   81 50           subi    r24, 0x01       ; 1

5

>  11c:   8d bd           out     0x2d, r24       ; 45

6

> 

7

>

> Die zu entfernen ist aus menschlicher Sicht leicht.
> Der AVR-GCC scheint ja gut zu erkennen, wann eine Variable nicht mehr
> benötigt wird.

Ich vermute mal, das ist erzeugt mit avr-gcc 4.x, Der ist meiner 
Erfahrung nach (noch) nicht so gut wie avr-gcc 3.4.6.

Beim Blick an die as-Ausgabe kann man kaum erkennen, was der Compiler so 
treibt. Eher aufschlussreich ist ein Blick in die Compiler-Ausgabe, zB 
mit -save-temps -fverbose-asm -dp (und -g nervt dann auch)

Mit dem so erhaltenen foo.s kann man eher Aussagen treffen, wo man die 
C-Quelle wie tunen könnte. Man findet zB flott unnötige extends wie 
zero_extendqihi2 etc.

Die Reihenfolge der Register bei der Allokierung ist hart in avr-gcc 
eincompiliert und kann mit -morder1 oder -morder2 verändert werden. Mit 
-morder1 ist der Code manchmal etwas besser, manchmal etwas schlechter 
als ohne -morder. Aber das für jedes Modul auszutesten, lohnt die Mühe 
m.E. nicht.

Wenn es wirklich auf jedes Byte ankommt, könnte man zwei .o erzeugen und 
target-size beurteilen lassen, welches Modul gelinkt wird. Fingerübung 
in sh und sed.

> Schwieriger stelle ich mir schon Registeroptimierungen über ne ganze
> Funktion vor, z.b. wenn 3 Pointer benötigt werden, diese in X,Y,Z zu
> halten.

Die Allokierung der GPRs erfolgt i.W. in zwei Schritten:

lreg (local register alloc) erledigt die Aufgabe für basic blocks (BB, 
d.h. Block enthält weder Verzweigungen noch Sprungmarken), d.h. 
allokiert für Pseudo-Regs, die nur in einem BB leben.

greg (global register alloc) erledigt den Rest für alle noch nicht 
abgebildeten Pseudo-Regs.

Manches kann avr-gcc leider noch nicht oder schiesst übers Ziel hinaus, 
z.B. wenn man hinschreibt

1

struct_t * p = & foo;

2

p->bar  = 0;

3

p->bazz = 0;

4

p->blah = 0;

Wird er die indirekten Zugriffe weg"optimiern" und stattdessen direkte 
Zugriff erzeugen. Das ist bei einem einzigen Zugriff auch besser, weil 
es weniger GPRs braucht -- vor allem kein wertvolles P-Reg und der Code 
schneller ist. Bei mehreren Zugriffen auf die Struktur wäre für dichten 
Code indirekter Zugriff aber besser, weil der nur 2 Byte belegt anstatt 
4 Byte. Bei mehrern Kompositen bzw. anderen indirekten Zugriffen müsste 
das P-Register aber wieder freigeschaufelt werden, und der Pointer würde 
beispielsweise nicht in Z leben, sonder in R15:R14, was wieder 
schlechter wäre...

Erschwerend kommt hinzu, dass Y eigentlich den Frame-Pointer hält und 
vor greg nicht bekannt ist, ob er gebraucht wird oder wegfallen darf.

Die Kosten eines Registers/einer Instruktion sind also a-priori nicht 
zielgenau oder garnich bestimmbar, und werden bei den 
mschinenunabhängigen Optimierungen schon garnicht beachtet.

Ein Ausweg wäre spekulative Compilerung, d.h. mehrer Varianten 
ausprobieren und die beste wählen. Das könnte auf verschiedenen Ebenen 
geschehen, würde aber die Compilezeit deutlich erhöhen und weit mehr 
Kenntnis über die Laufzeit-Umgebung erfordern wie Cache und 
Speicherzugriffs-Kosten, die -- wenn überhaupt -- nicht vor dem 
Lokatieren bekannt sind. AFAIK gibt's in der Richtung aber keine Ansätze 
in der GCC-Entwicklung, und GCC hat auch garnicht die Infrastruktur 
dafür.

Milepost versucht ja, per Heuristik a-priori Aussagen für die besten 
Optionen zu treffen. Ohne a-posteriori Beurteilung von dem, was man 
getan hat, ist das aber alles sehr wackelig was den Erfolg angeht. GCC 
macht auch kein a-posteriore Bewertung, aber ich finde so ein Ansatz 
könnte nochmal deutlich die Leistung erhöhen ohne an den vorhandenen 
Optimierungsalgorithmen zu drehen.