skip to main content

kiesler.at

Codeoptimierung mit BURG
updated by rck, 2006-03-26

Im Sommersemester 2004 galt es, wie schon viele Jahre davor, im Rahmen der Übung Übersetzerbau einen codeerzeugenden Compiler zu schreiben und zu optimieren. Ich möchte hier ein paar der von mir eingesetzten naheliegenden und weniger naheliegenden Tricks vorstellen.

1 | 2 | 3 | 4 | 5 | 6 | 7

Registerbibliothek in der Anwendung

Ich habe für jeden Knoten eine eigene Behandlungsroutine geschrieben, die Folgende ist beispielsweise für die Behandlung von "add"-Befehlen zuständig. Das gezeigte Prinzip sollte aber für so ziemlich alle binären Operationen anwendbar sein.

83 /*              arithmetics
84 */
85 
86 
87 node_add(treenodep a, treenodep b, treenodep dest) {
88 
89         if((a->regnr!=-1) && (b->regnr!=-1)) {
90 
91                 if(is_work_reg(a->regnr))
92                         dest->regnr=a->regnr;
93                 else
94                 if(is_work_reg(b->regnr))
95                         dest->regnr=b->regnr;
96                 else
97                         dest->regnr=alloc_register();
98 
99                 print_add(a->regnr, b->regnr, dest->regnr);
100 
101         } else
102         if(a->regnr!=-1) {
103 
104                 if(is_work_reg(a->regnr)) {
105 
106                         dest->regnr=a->regnr;
107                         print_add_const(a->regnr, b->num, a->regnr);
108 
109                 } else {
110 
111                         dest->regnr=alloc_register();
112                         print_add_const(a->regnr, b->num, dest->regnr);
113                 }
114 
115         } else
116         if(b->regnr!=-1) {
117 
118 
119                 if(is_work_reg(b->regnr)) {
120 
121                         dest->regnr=b->regnr;
122                         print_add_const(b->regnr, a->num, b->regnr);
123 
124                 } else {
125 
126                         dest->regnr=alloc_register();
127                         print_add_const(b->regnr, a->num, dest->regnr);
128                 }
129 
130         } else {
131 
132                 /* herzlichen Dank an Peter / Informatik-Forum
133                    für diese GENIALE Idee! :-) */
134 
135                 if(((a->num+b->num)>-254) &&
136                    ((a->num+b->num)< 255)) {
137 
138                         dest->num=a->num+b->num;
139                         dest->regnr=-1;
140 
141                 } else {
142 
143                         dest->regnr=alloc_register();
144                         print_store_const(a->num, dest->regnr);
145                         print_add_const(dest->regnr, b->num, dest->regnr);
146 
147                 }
148 
149         }
150 }

Kompliziert?

Sieht im ersten Moment sehr kompliziert aus -- es ist allerdings auch schon heftig optimiert worden darin.

89 - 101 wir haben zwei Register als Operanden. Der Fall ist fast so gut, wie Nummer vier: Lauter Konstanten. Ich habe für nichtvorhandene Register -1 eingesetzt und nicht etwa 0 -- die Nummerierung der Register beginnt ja bei 0 und wir würden dadurch einen der 32 Register nicht ansprechen können.

Hier sehen wir gleich eine wichtige Optimierung: Register-Recycling. Handelt es sich bei einem der Register nämlich um einen Arbeitsregister, können wir ihn gleich als Zielregister für die Operation definieren (92 bzw. 95). Praktisch!

Wenn nicht: Auch kein Problem, einfach einen neuen aus dem Pool nehmen.

102 - 130 hier das gleiche für nur einen Register. Vermutlich kann man das alles kompakter anschreiben.

130 - 149 im Falle lauter Konstanten braucht man gar keine Operation! Einfach das Ergebnis, wenn es im Rahmen bleibt, als Konstante weitergeben. Sehr effizient, habe ich mir von Peter aka. Risewind aus dem Informatik-Forum abgeschaut. Dankeschön!

1 | 2 | 3 | 4 | 5 | 6 | 7



RSSComments - Make a comment
The comments are owned by the poster. We are not responsible for its content.
  • Prototypes

    Posted on 2004-06-03 11:43:21 By Anonymous

    changed On 2004-06-03 12:32:28 Edited By rck (reason: versehentlich original-Kommentar von Gergo durch meinen Ersetzt. Hier wieder sein Kommentar. Sorry!)

    Prototypes
    Gesendet am: 2004-06-03 11:43:21 von: Anonymous

    Im Jahr 1989 wurde die Programmiersprache C in den USA von ANSI standardisiert, 1990 wurde dieser Standard von ISO als internationale Norm verabschiedet. Schon in diesem C89-Standard galten Funktionsdefinitionen ohne Protype (d.h. ohne explizite Angabe von Rückgabe- und Parametertypen) als "obsolescent feature". Eine Definition wie "alloc_register() {" ist also bereits seit 15 Jahren veraltet!
    Der neue C-Standard, C99, läßt überhaupt keine Funktionsdefinition ohne Prototype mehr zu. Es empfiehlt sich daher, in allen neu geschriebenen Programmen auf Prototypes zu achten und die Funktion explizit als "int alloc_register(void)" zu deklarieren. Das ist nicht bloß eine Stilfrage, dadurch ermöglicht man dem Compiler ja erst anständiges type checking.
    Der Preis: Man muß etwas mehr tippen. Das sollte es uns aber schon wert sein ;-)

    Gergo

    [Reply ]

    • Re: Prototypes

      Posted on 2004-06-03 12:31:28 By rck[110]

      Hallo Gergo! Herzlichen Dank für Deinen Kommentar.

      die Funktion explizit als "int alloc_register(void)" zu deklarieren. Das ist nicht bloß eine Stilfrage, dadurch ermöglicht man dem Compiler ja erst anständiges type checking.

      hmm. Ich hab durchaus Prototypen geschrieben, in die .h Datei, wo sie hingehören. Ein Auszug:

      1 /*              the assembler codegenerator,
      2                 to keep the bfe file tidy.
      3 
      4                 http://www.kiesler.at/
      5 */
      6 
      7 
      8 int print_not(int rs1, int rd);
      9 int print_not_const(int const, int rd);
      10 
      11 int print_neg(int rs1, int rd);
      12 int print_neg_const(int const, int rd);
      13 
      14 int print_head(int rs1, int rd);
      15 int print_tail(int rs1, int rd);
      16 int print_islist(int rs, int rd);
      17 
      18 int print_add(int rs1, int rs2, int rd);
      19 int print_add_const(int rs1, int const, int rd);
      20 int print_add_const_const(int const1, int const2, int rd);
      21 
      22 int print_mul(int rs1, int rs2, int rd);
      23 int print_mul_const(int rs1, int const, int rd);
      24 int print_mul_const_const(int const1, int const2, int rd);
      25 
      26 int print_add(int rs1, int rs2, int rd);
      27 int print_add_const(int rs1, int const, int rd);
      28 int print_add_const_const(int const1, int const2, int rd);


      ist das lesbarer als:

      17 /*              arithmetics
      18 
      19                 our mini-compiler only supports
      20                 add, negate and multiply.
      21 
      22 */
      23 
      24 node_add(treenodep a, treenodep b, treenodep dest);
      25 node_mul(treenodep a, treenodep b, treenodep dest);
      26 node_neg(treenodep a, treenodep b, treenodep dest);


      ? Stelle ich zur Diskussion, imho nicht. "Richtig" wäre wahrscheinlich sogar, statt der ints überall ein void hinzuschreiben. Dem Compiler ist das aber Wurst.

      Gleichzeitig stelle ich mir die Frage: Ändert das was an der Wartbarkeit? Habe ich davon einen Mehrwert? Wird dadurch mein erzeugter Code schneller? Was hab ich überhaupt davon, wenn ich explizit einen Rückgabetyp hinschreiben?

      Ich persönlich habe lieber übersichtlichen, kompakten Code. Vergleiche zB mal das Mini-Tutorial zu BURG mit folgendem Snippet aus meinem Code:

      22 start:  ARETURN(regnr)          # 1 #   node_return(LEFT_CHILD(this));
      23 
      24 regnr:  AADD(regnr, regnr)      # 3 #   node_add(LEFT_CHILD(this), RIGHT_CHILD(this), this);
      25 regnr:  AAND(regnr, regnr)      # 3 #   node_and(LEFT_CHILD(this), RIGHT_CHILD(this), this);
      26 regnr:  AMUL(regnr, regnr)      # 3 #   node_mul(LEFT_CHILD(this), RIGHT_CHILD(this), this);


      ...was ist übersichtlicher?

      Bezüglich seit 15 Jahren obsolet: Ja, vielleicht. Eigentlich sollte MS-DOS auch seit ewig obsolet sein, jeder neue AMD64 Rechner hat trotzdem noch das dazu passende A20-Gate. Irgendwo eine philosophische Frage... // René!

      [Reply ]

      • Re: Prototypes

        Posted on 2004-06-03 13:20:35 By Anonymous

        changed On 2004-06-03 13:33:08 Edited By rck (reason: Code lesbarer gemacht)

        Du argumentierst leider etwas an meiner beabsichtigten Richtung vorbei: Ja, ob man jetzt explizit "int" als Rueckgabewert hinschreibt oder nicht, ist ziemlich egal.
        Der Mehrwert von Prototypes kommt aber nicht vom Rueckgabewert, sondern von den Parametern.
        Nimm zum Beispiel dieses Programm:


        1 #include <stdio.h>
        2 
        3 func_ohne_args()
        4 {
        5         puts("hallo, arglose welt!");
        6 }
        7 
        8 func_nimmt_float(f)
        9         float f;
        10 {
        11         printf("f ist: %f\n", f);
        12 }
        13 
        14 int main(void)
        15 {
        16         func_ohne_args();
        17         func_ohne_args(1);
        18         func_ohne_args(1,2);
        19 
        20         func_nimmt_float();
        21         func_nimmt_float(12345);
        22         func_nimmt_float("kernighan und ritchie");
        23         func_nimmt_float(3.14159);
        24         func_nimmt_float(3.14159, 2.7172);
        25 
        26         return 0;
        27 }

        und sag mir, ob du das so wartbar findest. (Und ob du ueber den Output ebenso erstaunt bist wie ich!) Mit anstaendigen Prototypen wuerden die falschen Aufrufe sofort vom Compiler erkannt werden, aber in C89 ist der Compiler dazu nicht verpflichtet (GCC tut's auch nicht). Ohne type checking stehst du ziemlich allein da.
        Und ja, es bringt auch einen Mehrwert, sich an Standards zu halten.

        Gergo

        [Reply ]

RSSAll Articles
2008, 2007, 2006, 2005, 2004