Unterprogramme (I) (22. 10. 03)

Frames

$$Id: frame.tex,v 1.1 2003/10/21 20:46:18 joe Exp $$

Frame (Rahmen) ist Speicherbereich zur Verwaltung eines Unterprogramm-Aufrufs. Bestandteile sind:

• Platz für Parameter (Argumente)
• Platz für lokale Variablen
• (bei JVM) Operand Stack für lokale Rechnungen
• Rückkehradresse
• (bei Funktionen) (Verweis auf) Platz für Resultat

Zu jedem Zeitpunkt gibt es einen aktuellen Frame. Zum Unterprogramm-Aufruf legt der Caller einen neuen Frame an und schreibt die Werte der Parameter hinein. Wenn das fertig ist, wechselt die Kontrolle zum Callee. Wenn der fertig ist, wieder zurück zum vorigen Frame.

Unterprogramme bei x86

$$Id: intel.tex,v 1.1 2003/10/22 11:35:30 joe Exp $$

Unterprogramm-Deklaration:

int simple (int x) {
 return x + 5;
}

simple: pushl %ebp
        movl %esp,%ebp
        movl 8(%ebp),%edx
        addl $5,%edx
        movl %edx,%eax
        jmp .L5
        .p2align 4,,7
.L5:    leave
        ret

Unterprogramm-Aufruf:

    r = simple (4);

        addl $-12,%esp
        pushl $4
        call simple
        addl $16,%esp
        movl %eax,%eax
        movl %eax,-4(%ebp)

Frame-Optimierungen

$$Id: register.tex,v 1.2 2003/10/22 11:35:30 joe Exp $$

Literatur: Apppel: Modern Compiler Implementation, Chapt. 6

Die Frames decken den allgemeinsten Fall ab (rekursive Unterprogramme mit beliebig vielen Parametern).

Viel häufiger sind jedoch Spezialfälle: keine Rekursion, und nur geringe Schachtel-Tiefe; deswegen lohnt es sich, diese zu optimieren.

Register

Die Übergabe in Frames (im Hauptspeicher) ist langsam. Besser sind Register (in der CPU). Frames gibt es viele, aber Register nur einmal. Vor Überschreiben Werte retten! Wer macht das? Der Caller (vorausschauend) oder der Callee (wenn er es braucht).

Dazu gibt es evtl. Konventionen (z. B. auf MIPS sollen Register 16-23 callee-save sein)

Register-Windows

$$Id: window.tex,v 1.1 2003/10/22 11:35:30 joe Exp $$

der Registersatz ist tatsächlich ziemlich groß, damit spart man sich (für eine Weile) das Arbeiten auf dem Stack.

Man benutzt Register g0 ...g7 (global), i0 ...i7 (input), l0 ...l7 (local), o0 ...o7 (output).

Sparc hat 128 Register, eingeteilt in 8 Blöcke zu je 8 in-registern und 8 local-registern. Die out-register sind die in-register des nächsten Blocks! (D. h. dort schreibt man Argumente für Unterprogramme hin, und holt sich auch das Ergebnis.)

Erst wenn die Schachteltiefe größer als 8 Aufrufe wird, muß in den Speicher geschrieben werden.

Unterprogramme auf Sparc

$$Id: sparc.tex,v 1.1 2003/10/22 11:35:30 joe Exp $$

Unterprogramm-Deklaration:

int simple (int x) {
 return x + 5;
}

simple: !#PROLOGUE# 0
        save    %sp, -112, %sp
        !#PROLOGUE# 1
        st      %i0, [%fp+68]
        ld      [%fp+68], %o1
        add     %o1, 5, %o0
        mov     %o0, %i0
        ret
        restore

Unterprogramm-Aufruf:

    r = simple (4);

        mov     4, %o0
        call    simple, 0
        st      %o0, [%fp-20]

Aufgaben: wo liegen die beteiligten Register, was passiert genau bei save/ret/restore?

Gesamt-Analyse

$$Id: gesamt.tex,v 1.1 2003/10/22 11:35:30 joe Exp $$

Wenn der Compiler den kompletten Programmtext sieht:

Unterprogramm-Aufrufe können aufgelöst werden (inlining).

Aufgabe: ausprobieren mit gcc.

Für verbleibende Aufrufe ist interprozedurale Register-Allokation möglich. Dann müssen Werte von Argumenten nicht umkopiert werden.

Beachte: Konflikt mit modularer Programmierung (Quelltext der Module muß vorhanden sein).

Tail-Rekursionen

$$Id: tail.tex,v 1.1 2003/10/21 20:46:18 joe Exp $$

Wenn die letzte Aktion eines Unterprogramms $P$ der Aufruf eines Unterprogramms $Q$ ist (eine End-Rekursion),

dann wird nach der Rückkehr aus $Q$ der Frame von $P$ nicht mehr gebraucht.

Deswegen diesen Frame bereits vor dem Ruf von $Q$ aufgeben, d. h. den Frame zum $Q$-Aufruf in den $P$-Frame hineinschreiben!

Aufgabe: untersuche, ob gcc End-Rekursionen bei Prozeduren und Funktionen auflösen kann, und welche anderen Optimierung bei Prozedur-Aufrufen noch stattfinden. Beachte Unterschiede zwischen gcc -Ox für $x \in \{0,1,2,3\}$.

Vergleiche mit der Dokumentation gcc.gnu.org.

Seminar 24. 10.

$$Id: seminar.tex,v 1.1 2003/11/05 12:33:51 joe Exp $$

• Prozedur-Aufrufe, vergleiche gcc -S mit gcc -S -O, mit gcc -S -O3, bzw. mit Sun-Compiler cc
• Inlining, Constant Propragation, Loop Unrolling?
• Tail Recursion ($\to$ Sprung $\to$ Schleife)

Nested Functions

$$Id: nested.tex,v 1.2 2003/10/22 11:35:30 joe Exp $$

void walk 
(void action (int), 
  tree * t) {
  void help (tree * t) {
    if (NULL != t) {
      action (t -> node);
      help (t -> left);
      help (t -> right);
    }
  }
  help (t);
}

void display (tree * t) {
  void show (int n) 
    { printf ("%d ", n); }
  walk (& show, t);
}

int count (tree * t) {
  int counter = 0;
  void one (int n) 
    { counter ++; }
  walk (& one, t);
  return counter;
}

Das ist eine C-Erweiterung (implementiert in gcc).

Aufgabe: und in Java? (Helfen innere Klassen?)

Statische und Dynamische Ketten

$$Id: static.tex,v 1.2 2003/10/26 23:25:31 joe Exp $$

Implementierung von nested functions:

damit Zugriff auf lokale Variablen in umgebenden Blöcken funktioniert, brauchen wir die statische Aufrufkette (= Verweise auf textlich umgebende Frames).

(Ein Zeiger auf) eine Funktion ist damit nicht nur eine Adresse, sondern auch ein (Zeiger auf die passende) statische Kette. So ein Paar heißt closure.