skip to main content

kiesler.at
You are NOT logged in. ( login | New Account Signup | Forgot Your Password? ) Why log in?

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.
RSSAll Articles
2008, 2007, 2006, 2005, 2004