Künstliche Intelligenz soll den GCC beschleunigen

Das von der EU mit knapp 1,7 Millionen Euro geförderte Milepost-Projekt
hält die Technik vor allem für eingebettete Systeme, etwa Mobilgeräte,
für sinnvoll. Ziel sei es, automatisch einen optimierenden Compiler zu
bauen, statt wie bislang für jede Plattform von Hand die nötigen
Änderungen vorzunehmen.

Quelle:
http://www.heise.de/newsticker/Kuenstliche-Intelli...

Weiterführender Link: http://gcc-ici.sourceforge.net/papers/fmtp2008.pdf

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:

  OCR1C = bauddiv-1;
 118:   82 2f           mov     r24, r18
 11a:   81 50           subi    r24, 0x01       ; 1
 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:
>

> 
>   OCR1C = bauddiv-1;
>  118:   82 2f           mov     r24, r18
>  11a:   81 50           subi    r24, 0x01       ; 1
>  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.

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

struct_t * p = & foo;
p->bar  = 0;
p->bazz = 0;
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.