Der Titel fragt's - warum kann ein Compiler besseren Code für RISC erzeugen? -oder ist das nur ein Gerücht? Was ist überhaupt besserer Code?
Das ist ein Gerücht. Umgekehrt wird ein Schuh daraus. Früher baute man CISC Cpus. Also CPUs mit einem mächtigen Instruktionsvorrat. Bis sich dann jemand mal die Arbeit machte und nachsah, welche Instruktionen dieses mächtigen Befehlssatzes von einem Compiler überhaupt benutzt werden. Die Überraschung war groß, als man herausfand, dass diese mächtigen Befehle (eine VAX hatte zb stringverarbeitende Befehle auf CPU-Ebene) überhaupt nicht benutzt wurden. Es war im Compiler einfach zu kompliziert die Situationen zu identifizieren, in denen sie eingesetzt werden konnten. Und so wurde die Idee des RISC geboren. Eine CPU mit wenigen Befehlen, die dafür aber orthogonal angeordnet sind und schneller abgearbeitet werden können. Dem Compilerbauern wars mehr oder weniger egal. Im Compiler selbst hat sich nicht viel geändert. Lediglich ein paar Sonderfälle wurden in der Codegenerierung durch den orthogonalen Befehlssatz eliminiert. Aber die CPUs wurden schneller.
Hallo woha, Die Qualität des vom Compiler generierten Codes dürfte sich wohl danach bemessen, wie optimal die Ressourcen der Zielarchitektur genutzt werden. Damit dürfte Code optimal übersetzt sein, wenn keine schnellere Ausführung und keine geringere Speicher-/Registerbelegung möglich ist. Das RISC Befehle im Gegensatz zu CISC Befehlen wesentlich atomarer sind, dürfte es für den Compiler "leichter" sein, Abhängigkeiten aufzulösen und Befehle hinsichtlich der Ausführungsreihenfolge zu optimieren. In wie weit aber ein "echt besserer" Code im Sinne von effizient generiert wird, kann ich nicht sagen. Grüße Andreas
Besserer Code ist je nach Optimierungsziel kürzer und/oder schneller. Bei manchen CISCs gibt (gab) es Adressierungsarten, die - ein Register R1 verwenden, - dazu eine Konstante addieren, - dort eine Adresse aus dem Speicher laden, - zu dieser Adresse eine weitere Konstante addieren, - ein Register R2 mit einer dritten Konstante multiplizieren, - dieses Register auf der vorher ermittelten Adresse addieren, - und dann erst die fertige Adresse berechnet haben. Einerseits ist das eine ausgewachsene Scheusslichkeit bei der Implementierung in Hardware, spätestens ab der dritten Hardwaregeneration nach der Definition des Befehlssatzes. Insbesondere hat ein Compiler aber reichlich Arbeit dabei, den Zwischencode so zu sortieren und zu verarbeiten, dass er darin eine solche Rechenstruktur überhaupt erkennt oder gar gezielt darauf hinarbeiten kann, sie zu verwenden. Nicht selten läuft es darauf hinaus, dass ein Compiler die extremeren Formen davon (solche wie oben) überhaupt nicht oder nur selten verwendet und sich auf einfachere Formen beschränkt. Die Vorteile solcher Adressierungstürme sind etwas kürzerer Code und weniger für Zwischergebnisse ver(sch)wendete Register. Schneller als eine Aufdröselung dieser Rechnerei in Teiloperationen ist es jedoch nicht - nicht selten sogar langsamer. Selbst wenn man diesen Zirkus weglässt: Etliche CISCs haben eher wenig allgemein verwendbare Register (alle Akku-Architekturen, und beispielsweise auch Renesas R8C/M16C/M32C). Nun sind Register aber der schnellste Speicher. Register durch Speicher zu ersetzen verlangsamt den Code. Besser sieht es aus, wenn man vorher dran denkt. MSP430 ist CISC mit genug Registern und einfacher Adressierung und stellt für einen Compiler kein Problem dar. Es muss also nicht schlechter sein. Zwar lässt sich eine Architektur mit fester Befehlslänge leichter auf hohes Tempo bringen als eine variable, aber im Kontext von Controllern wie MSP430 ist das ja kein Thema.
Karl heinz Buchegger schrieb: > Und so wurde die Idee des RISC geboren. Eine CPU mit wenigen Befehlen, > die dafür aber orthogonal angeordnet sind und schneller abgearbeitet > werden können. > Dem Compilerbauern wars mehr oder weniger egal. Naja, nicht ganz. Die Compilertechnologie hatte sich mittlerweile deutlich weiter entwickelt. Als man auf die Idee mit RISC kam, war man im Compilerbau so weit, dass man praktisch x-beliebige schräge Szenarien in einem Compiler durchziehen konnte, was ihn schon recht stark von den Compilern der 1970er Jahre unterscheidet. So kann man eben im Compiler gut mit Dingen umgehen wie: "Die CPU braucht nach dem Dekodieren des Sprungbefehls noch einen Takt, in dem sie das Sprungziel berechnet. In diesem Takt kann sie aber noch eine einfache Registeroperation parallel abarbeiten, die dann effektiv noch vor dem Sprung abgearbeitet wird, obwohl sie im Befehlsspeicher erst danach steht." (delay slot) Die Idee hinter RISC ist also, dass man eine relativ dumme aber schnelle CPU bauen kann (die übrigens vergleichsweise stromsparend ist, weil sie nicht so viele Gatter hat) und dass man die Intelligenz in den Compiler verlagert.
RISC mag ja für die erste Version eines Compilers einfacher sein. Dafür wird aber der Codebus der Flaschenhals, da ja mehr Code geladen werden muß, um eine CISC Instruktion nachzubilden. Ein Compiler, der effektiv CISC Instruktionen einsetzen kann, erzeugt schlankeren und damit schnelleren Code. Um diesen Flaschenhals etwas zu entschärfen, arbeiten z.B. ARM-MC intern mit einem 128Bit-Bus, um 4 32Bit-Befehle gleichzeitig laden zu können. Sprünge und Calls werden dann natürlich teuer (bis zu 3 Waitstates). Peter
Peter Dannegger schrieb: > RISC mag ja für die erste Version eines Compilers einfacher sein. > Dafür wird aber der Codebus der Flaschenhals, da ja mehr Code geladen > werden muß, um eine CISC Instruktion nachzubilden. Korrekt, jedenfalls in der ursprünglichen Form mit fester 32-Bit Befehlsbreite. Daher ist es auch kein Zufall, dass sich RISCs ungefähr zu dem Zeitpunkt verbreiteten, zu dem integrierte Caches machbar wurden. > Um diesen Flaschenhals etwas zu entschärfen, arbeiten z.B. ARM-MC intern > mit einem 128Bit-Bus, Manche jedenfalls. Analog Devices kommt beim ADuC7000 in dieser Stelle (Flash) lustigerweise mit 16 Bits aus. Der in 16 Bits codierte Instruction Stream von Thumb2 (Cortex-M3) oder MIPS16 (PIC32) ist auch vom Platzverbrauch her recht effizient - deswegen sind diese Codierungen ja überhaupt erst entstanden. Wobei man dran denken sollte, dass 32-Bit Adressierung unabhängig von RISC oder CISC in Form breiter Adresskonstanten aufgrund der grosszügigen Adressverteilung deutlich mehr Platz braucht, als der 8-Bit I/O-Adressraum eines 8051. > Sprünge und Calls werden dann natürlich teuer (bis zu 3 Waitstates). Die Anzahl Waitstates hat nichts mit der Breite zu tun und viel mit den MHz. Die LPC1700 brauchen bis zu 5 davon, aber nicht wegen der 128 Bits, sondern wegen der 100MHz - und weil NXPs Flash offenbar langsamer ist als das von ST.
A. K. schrieb: > Bei manchen CISCs gibt (gab) es Adressierungsarten, die > - ein Register R1 verwenden, > - dazu eine Konstante addieren, > - dort eine Adresse aus dem Speicher laden, > - zu dieser Adresse eine weitere Konstante addieren, > - ein Register R2 mit einer dritten Konstante multiplizieren, > - dieses Register auf der vorher ermittelten Adresse addieren, > - und dann erst die fertige Adresse berechnet haben. Die Prozessorbauer in der CISC-Ära haben versucht, Hochsprachenkonstruk- te (insbesondere von C, das ebenfalls in dieser Zeit populär wurde) möglichts 1:1 auf dem Prozessor abzubilden in der Hoffnung, dass damit auch der Code von schwach optimierenden Compilern schnell ausgeführt werden kann. Das obige Beispiel ist die direkte Umsetzung des C-Ausdrucks
1 | a->b[i] |
R1 ist der Stackpointer oder ein Zeiger auf den Speicherbereich für statische Variablen (je nachdem, ob a automatisch oder statisch ist), die erste Konstante ist der Offset von a, die zweite Konstante ist der Offset von b innerhalb der Strukur *a, R2 ist der Array-Index i, und die dritte Konstante ist die Größe eines Arrayelements. Ein anderes Beispiel: Auf dem MC68000 konnte die berühmte String-Copy- Anweisung aus dem K&R
1 | while(*pdst++=*psrc++); |
ebenfalls fast 1:1 umgesetzt werden:
1 | loop: move.b (a0)+,(a1)+ |
2 | bnz loop |
Auch die LINK- und UNLK-Befehle des MC68000 zum Anlegen und Entfernen von Variablenblöcken auf dem Stack waren speziell für Hochsprachen wie C vorgesehen. Man ging also davon aus, dass nun ein C-Programm trotz mäßiger Optimie- rung durch den Compiler fast genauso schnell laufen sollte wie ein Assembler-Programm. Die Praxis sah leider etwas anders aus: Da die Compiler so schlecht op- timierten, konnten sie diese leistungsfähigen Befehle nur dann erzeugen, wenn sie im C-Quellcode bestimmte Muster vorfanden. Als C-Programmierer versuchte man deswegen, durch Probieren herausfinden, wie diese Muster aussahen und hat anschließend die Anweisungen und Ausdrücke entsprechend hingebogen. Nur dann konnte man die Vorteile der CISC-Prozessoren wirk- lich ausschöpfen. Inzwischen sind die Optimierungsfähigkeiten der Compiler so weit fortge- schritten, dass dies kaum noch ein Problem ist. Weil aber die Optimie- rung so gut funktioniert, ist es oft vorteilhafter, wenn der Compiler den Code aus vielen kleinen und schnellen Befehlen zusammenstückeln kann, als wenn er langsame, fette CISC-Befehle verwenden muss, von dessen Features er vielleicht nur die Hälfte brauchen kann. Das hängt aber stark vom Aufbau des CISC-Befehlssatzes ab. Ist er mit viel Über- legung entworfen, so dass seine Features gewinnbringend genutzt werden können, wird dies ein guter Compiler auch tun und ebenfalls effizienten Code generieren.
yalu schrieb: > A. K. schrieb: >> Bei manchen CISCs gibt (gab) es Adressierungsarten, die >> - ein Register R1 verwenden, >> - dazu eine Konstante addieren, >> - dort eine Adresse aus dem Speicher laden, >> - zu dieser Adresse eine weitere Konstante addieren, >> - ein Register R2 mit einer dritten Konstante multiplizieren, >> - dieses Register auf der vorher ermittelten Adresse addieren, >> - und dann erst die fertige Adresse berechnet haben. > > Die Prozessorbauer in der CISC-Ära haben versucht, Hochsprachenkonstruk- > te (insbesondere von C, das ebenfalls in dieser Zeit populär wurde) > möglichts 1:1 auf dem Prozessor abzubilden in der Hoffnung, dass damit > auch der Code von schwach optimierenden Compilern schnell ausgeführt > werden kann. Dummerweise haben sie dazu aber nicht mit den Compilerbauern geredet. Die nämlich an der entsprechden Stelle der Codegenrierung nicht mehr a->b[i] gesehen haben, sondern beispielsweise sowas wie load add add load variable a offset b multiply load variable i constant 4 oder so ähnlich.
A. K. schrieb: > Dummerweise haben sie dazu aber nicht mit den Compilerbauern geredet. :-) > Die nämlich an der entsprechden Stelle der Codegenrierung nicht mehr > a->b[i] > gesehen haben, sondern beispielsweise sowas wie > load > add > add > load > variable a > offset b > multiply > load > variable i > constant 4 > oder so ähnlich. Die Hoffnung war damals, in die Peephole-Optimizer ziemlich einfach die entsprechenden Muster einbringen zu können. Zur Erinnerung: Ein Peephole-Optimizer im Compiler weiß eigentlich nichts von der Sprache an sich. Er durchsucht den Assembler-Code (oder eine Entsprechung in einem Zwischencode) nach bestimmten Mustern und ersetzt dieses Muster durch ein anderes, schnellereres, kürzereres Muster So generieren Compiler in der Behandlung von if-then-else Sequenzen schon mal gerne so etwas ... jmp label // ende vom then Zweig // else Zweig gibt es keinen label: ... Klar kann man das jetzt bei der Generierung des Zwischencodes entfernen und behandeln, aber einfacher ist es, es dem Peephole Optimizer zu üblassen, diesen jmp rauszuwerfen.
Karl heinz Buchegger schrieb: > Die Hoffnung war damals, in die Peephole-Optimizer ziemlich einfach die > entsprechenden Muster einbringen zu können. Nö, im Peephole Optimizer ist dieses Kind definitiv schon im Brunnen. Sowas wie hier muss vorher gelöst werden. Die Hauptaufgabe eines Peephole-Optimizers liegt wie du richtig beschreibst darin, Code zusammenzubauen, den der Codegenerator getrennt erzeugt hat. Wenn also der Code vom Statement 1 in einem Befehl endete, der zusammen mit den Code am Anfang vom Statement 2 optimierbar war. Was Compiler früher nicht gesehen haben, weil Statements unabhängig voneinander generiert wurden. Im hier betrachteten Fall geht es eher darum, im Rahmen der normalen Codegenerierung solche reich geschmückten Christbäume als adressierbar zu identifizieren. Das geht durchaus. Aber solche Patternmatcher reagieren empfindlich auf kleinste Abweichungen. Ausserdem liegt im Beispiel oben ja die Variable "i" vielleicht grad nicht in einem Register. So dass der Codegenerator zunächst das Pattern nicht als adressierbar erkennen kann. Statt aber nun einen beliebigen passenden Unterbaum getrennt zu rechnen müsste er trotzdem ein bestimmtes komplexes Pattern als auf Adressierungart optimierbar erkennen und daraus den Schluss ziehen, gezielt nur die Variable "i" ins Register zu holen, damit der Code adressierbar wird. Kann man machen. Hat man aber vielleicht nicht. Und wenn du das mühselig zustande gebracht hast, dann kommt der Hersteller mit der nächsten Generation seiner Prozessoren und sagt "lass den Mist sein, die komplexen Adressierungen sind jetzt viel langsamer als wenn du den Kram einzeln rechnest, die sind nur noch drin, damit alter Code überhaupt läuft" (Motorola 680xx). Spätestens dann wirst du zum Konvertit ;-). > Zur Erinnerung: Ein Peephole-Optimizer im Compiler weiß eigentlich > nichts von der Sprache an sich. Der Codegenerator auch nicht mehr. Nach dem Parser ist das Thema "Sprache" durch. Ich habe sowas schon geschrieben.
A. K. schrieb: > Karl heinz Buchegger schrieb: > >> Die Hoffnung war damals, in die Peephole-Optimizer ziemlich einfach die >> entsprechenden Muster einbringen zu können. > > Nö, im Peephole Optimizer ist dieses Kind definitiv schon im Brunnen. > Sowas wie hier muss vorher gelöst werden. Drum sagte ich ja: Die Hoffnung war ... Aber die Hoffnung war trügerisch :-)
A. K. schrieb: > Dummerweise haben sie dazu aber nicht mit den Compilerbauern geredet. Diesen Eindruck konnte man durchaus bekommen. > Die nämlich an der entsprechden Stelle der Codegenrierung nicht mehr > a->b[i] > gesehen haben, sondern beispielsweise sowas wie > load > add > add > load > variable a > offset b > multiply > load > variable i > constant 4 > oder so ähnlich. Wenn man nicht gerade einen Universalcompiler wie den GCC mit austauschbaren Backends zum Ziel hat, erscheint es aber auch nicht besonders sinnvoll, einen Zwischencodebefefehlssatz zu verwenden, der deutlich lower-level als der Target-Befehlssatz ist. Vielleicht hätten also nicht nur die Prozessorbauer mit den auch die Compilerbauern reden, sondern auch diese etwas von ihren Gewohnheiten abrücken und Neues dazulernen müssen :)
yalu schrieb: > Wenn man nicht gerade einen Universalcompiler wie den GCC mit > austauschbaren Backends zum Ziel hat, erscheint es aber auch nicht > besonders sinnvoll, einen Zwischencodebefefehlssatz zu verwenden, der > deutlich lower-level als der Target-Befehlssatz ist. Dieses Beispiel entspricht in groben Zügen dem, was beim Portable C Compiler von Steve Johnson aus dem ersten Pass rauskam - siehe http://de.wikipedia.org/wiki/Portable_C_Compiler, ihm hat die Welt auch Lint zu verdanken. Ausserdem möchte ich zu gerne mal einen Parser sehen, der direkt als Zwischencode die Befehlsstruktur einer VAX wiederspiegelt. Der hätte wahrscheinlich nicht in den Speicher gepasst ;-). Nö, ein Parser, der nicht hunderte von Spezialfällen als Quelltextpattern erkennt, der zerlegt erst eine Sprache in Grundelemente und setzt sie später teilweise wieder zusammen. Das ist der natürliche Vorgang. > Vielleicht hätten also nicht nur die Prozessorbauer mit den auch die > Compilerbauern reden, sondern auch diese etwas von ihren Gewohnheiten > abrücken und Neues dazulernen müssen :) Haben sie. Dies war das Ergebnis ;-). Die vorherigen Compiler liessen sich weitaus schlechter anpassen als PCC.
<off> Beim GCC wäre es generell sinnvoll, wenn das Backend sich irgendwann mal mit dem Frontend verständigen würde :-> Spaß bei Seite, viele halten den Wust im GCC für veraltet und kaum noch wartbar -- ich kanns nicht beurteilen. Nur so weit, als dass es schon mehrmals Ungereimtheiten beim Erstellen von AVR-Code gab, die man aber offenbar aufgrund der Architektur des GCC kaum beheben könne (wenn ich mich recht entsinne etwa der Epilog hinter main(), wird nie erreicht). </off>
Sven P. schrieb: > Spaß bei Seite, viele halten den Wust im GCC für veraltet und kaum noch > wartbar -- ich kanns nicht beurteilen. Zumindest kleinräumig im Backend habe ich auch diesen Eindruck. Der Code für Proglog/Epilog im ARM-Backend ist eine Katastrophe, an die sich deshalb wohl auch niemand mehr rantraut (beispielsweise um den alten Bug mit defektem Prolog/Epilog bei Interrupt-Funktionen zu beheben). Wirkt wie ein typisches Ergebnis von unkoordinierter kooperativer Vorgehensweise, wenn jeder seinen Kram separat hinzudichtet ohne den ähnlichen Kram seines Vorgängers anfassen zu wollen.
A. K. schrieb: > zerlegt erst eine Sprache in Grundelemente und setzt sie später > teilweise wieder zusammen. Das ist der natürliche Vorgang. Yep. Ich hab da ein schönes Buch von Digital Press "Engeneering a compiler" das von der Portierung eines PL/I Compilers von (ich glaube) CDC zur VAX handelt. Und dort hatte der Peephole Optimizer unter anderem auch die Aufgabe einige der Pattern in VAX-spezifische Opcodes umzusetzen. (Das war wohl zeitweise einer der langsamtes Compiler aller Zeiten :-) War ein Multipass Compiler, und die Entwickler haben Pass für Pass zur VAX portiert. Auf der CDC liefen die ersten Passes, die ihr Ergebnis auf ein Band gedumpt haben. Das Band wurde quer durch die USA geschickt, wo es dann die bereits portierten Passes eingelesen haben und die Compilierung vervollständigt wurde :-) Erinnert mich irgendwie an den RFC zum Netzwerkaufbau mittels Brieftauben.
Karl heinz Buchegger schrieb: > das von der Portierung eines PL/I Compilers von (ich glaube) CDC zur VAX > handelt. Au weh, das ist allerdings wirklich Hardcore. Von einer ziemlich einfachen RISC-artigen Maschine mit extrem einfacher aber dennoch etwas bizarrer Adressierung (es gibt bei den Hauptregistern weder Lade- noch Speicherbefehle) auf ausgerechnet eine VAX. Und dann auch noch ausgerechnet PL/I.
A. K. schrieb: > Speicherbefehle) auf ausgerechnet eine VAX. LOL. Nichts gegen die VAX. Von der und dem VMS träume ich heute noch zeitweise :-) > Und dann auch noch ausgerechnet PL/I. Meine erste Sprache auf der Uni :-)
Karl heinz Buchegger schrieb:
> Meine erste Sprache auf der Uni :-)
Mein Beileid. Das ist glaube ich jene Sprache, in der Schönheiten wie
if if = then then then = else else else = end;
möglich sind. Oder so ähnlich, vielleicht fehlt ein ";".
Ideal geignet für Controller-Programmierung - oder wo gibt es sonst
schon variable Bitstrings? Ok, dass die linksbündig arbeiten...
A. K. schrieb: >> Meine erste Sprache auf der Uni :-) > > Mein Beileid. Das ist glaube ich jene Sprache, in der Schönheiten wie > if if = then then then = else else else = end; > möglich sind. Oder so ähnlich, vielleicht fehlt ein ";". Entsprechendes (Schlüsselwörter als Variablennamen zu verwenden) ging auch in Fortran. Damals hat man eben noch gespart ;-)
A. K. schrieb: > Mein Beileid. Das ist glaube ich jene Sprache, in der Schönheiten wie > if if = then then then = else else else = end; > möglich sind. Oder so ähnlich, vielleicht fehlt ein ";". Ich würde sagen, da fehlt ein end. Peter
A. K. schrieb: > Karl heinz Buchegger schrieb: > >> Meine erste Sprache auf der Uni :-) > > Das ist glaube ich jene Sprache, in der Schönheiten wie > if if = then then then = else else else = end; > möglich sind. Oder so ähnlich, vielleicht fehlt ein ";". Lang, lang ists her. Aber ich denke das stimmt schon. > Mein Beileid. Wenn ich dir jetzt noch sage, dass wir auf einem IBM-360-Clone unsere Übungen gemacht haben ... im Batch-Betrieb ... mit einem Compilerlauf täglich (eigentlich nächtlich. Job im RZ abgeben und am nächsten Tag in der Früh lag der gedruckte Output in deinem Fach. Jede Woche gab es 3 neue Übungen, die 14 Tage später abzugeben waren. Da hat man auf jeden fehlenden ; geachtet). Wundert es dich dann noch, dass ich das Glück hatte zum ersten Jahrgang zu gehören, der nicht mehr mit Lochkarten hantieren musste (was wir aber zu unserer eigenen Freude trotzdem gemacht haben :-) > > Ideal geignet für Controller-Programmierung - oder wo gibt es sonst > schon variable Bitstrings? Oder Regional-1, Regional-2, ISAM Dateien direkt in der Sprache ... (alles längst vergessen, frag mich blos nicht was es damit genau auf sich hatte)
Peter Dannegger schrieb: > Um diesen Flaschenhals etwas zu entschärfen, arbeiten z.B. ARM-MC intern > mit einem 128Bit-Bus, um 4 32Bit-Befehle gleichzeitig laden zu können. > Sprünge und Calls werden dann natürlich teuer (bis zu 3 Waitstates). Das betrifft aber lediglich das interne Flash interface einiger µC. Es gibt derzeit keinen ARM Kern, der ein 128bit System Interface hat. Gruß Marcus http://www.doulos.com/arm/
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.