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

Code-Ausgabe

Die eigentliche Code-Ausgabe erfolgt bei mir nicht direkt im Burg, auch nicht in der zwischengeschalteten Bibliothek "nodeops", in der die ganzen node_ Funktionen und die Registerverwaltung untergebracht sind.

Nein, daf�r habe ich eine eigene Bibliothek, die funklib. Und darin gibt es einerseits die Check-Verwaltung (wurde f�r ein gegebenes Register bereits eine Typ�berpr�fung durchgef�hrt?) und andererseits zahlreiche print_ Funktionen f�r eben die Codeausgabe.

Ich stelle hier exemplarisch print_add() und print_add_const() vor, welche via node_add() aufgerufen werden.

384�print_add(int�rs1,�int�rs2,�int�rd)�{
385�
386���������check_int_2(rs1,�rs2);
387�
388���������trace("#�print_add(%d,�%d,�%d)\n",
389�����������������rs1,�rs2,�rd);
390�
391���������printf("\taddq�$%d,�$%d,�$%d\n",
392�����������������rs1,�rs2,�rd);
393�
394���������force_valid_int(rd);
395�}
396�
397�
398�print_add_const(int�rs1,�int�const1,�int�rd)�{
399�
400���������if(const1==0)�{
401�
402�����������������if(rs1!=rd)�{
403�
404�������������������������check_int(rs1);
405�
406�������������������������trace("#�print_add_const(%d,�%d,�%d)\n",
407���������������������������������rs1,�const1,�rd);
408�
409�������������������������//�no�(un)tagging�here�--�we�only
410�������������������������//�copy�rs1
411�
412�������������������������printf("\tmov�$%d,�$%d\n",
413���������������������������������rs1,�rd);
414�
415�������������������������force_valid_int(rd);
416�����������������}
417�
418���������}�else
419���������if((const1>0)�&&�(const1<128))�{
420�
421�����������������check_int(rs1);
422�
423�����������������trace("#�print_add_const(%d,�%d,�%d)\n",
424�������������������������rs1,�const1,�rd);
425�
426�����������������printf("\taddq�$%d,�%d,�$%d\n",
427�������������������������rs1,�const1<<1,�rd);
428�
429�����������������force_valid_int(rd);
430�
431���������}�else
432���������if((const1>-127)�&&�(const1<0))�{
433�
434�����������������check_int(rs1);
435�
436�����������������trace("#�print_add_const(%d,�%d,�%d)\n",
437�������������������������rs1,�const1,�rd);
438�
439�����������������printf("\tsubq�$%d,�%d,�$%d\n",
440�������������������������rs1,�(-const1)<<1,�rd);
441�
442�����������������force_valid_int(rd);
443�
444���������}�else�{
445�
446�����������������untag_int(rs1);
447�
448�����������������trace("#�print_add_const(%d,�%d,�%d)\n",
449�������������������������rs1,�const1,�rd);
450�
451�����������������if(const1<0)�{
452�
453�������������������������printf("\tsubq�$%d,�%d,�$%d\n",
454���������������������������������rs1,�(-const1)<<1,�rd);
455�
456�����������������}�else�{
457�
458�������������������������printf("\taddq�$%d,�%d,�$%d\n",
459���������������������������������rs1,�const1,�rd);
460�����������������}
461�
462�����������������tag_int_2(rs1,�rd);
463���������}
464�}

Das ebenfalls noch vorhandene print_add_const_const() ist ein �berbleibsel und wird inzwischen vollst�ndig von node_add() �bernommen.

Zwei Register addieren

Zwei Register zu addieren (384 - 395) kann kein Thema sein. Zwei Besonderheiten: check-int() (386) pr�ft den Typ nur "on demand". Au�erdem: force_valid_int() sagt: das kann nur ein g�ltiger int sein. Und bei einer Ausgabe von add trifft das offensichtlich zu.

Wieso brauchen wir das ganze nicht untaggen bzw. taggen? �berlegen wir uns das ganze Mathematisch. Ein typisierter int hat den Wert 2n. Klar, oder?

Zwei typisierte Werte addieren sich nun zu 2a + 2b = 2n. Somit brauchen wir uns hier mit tagging und untagging nicht besch�ftigen. Gilt genauso f�r and, bei mul ben�tigen wir ein abschlie�endes sra.

Register und Konstante addieren

Hier wirds interessant. Sollten wir die Konstante 0 erhalten (400), k�nnen wir ein einfaches Move machen. Genaugenommen w�re, wie mir gerade auff�llt, nichtmal das notwendig: Wir k�nnten in node_add im Falle der Konstante 0 einfach den Register ans Ergebnis durchreichen. Das n�chste Mal vielleicht :-)

419-444 ziehen Konstanten ab (bei negativen Werten) bzw. addieren diese zu einem Register. Geht allerdings nur +/- 128, das Tagging kostet uns ein Bit.

444-463 geht sich's wegen dem Bit nicht aus, schlagen wir hier zu. Daf�r ben�tigen wir dann (leider) tagging/untagging. H�here Konstanten verkraftet unser Compiler nicht, die Angabe schlie�t sie allerdings aus.
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