Wie optimiert der C++ - Compiler die Stapelzuordnung?

Question

Ich finde this post und schreiben einige Tests wie folgt aus:

Ich erwarte Compiler macht eine TCO auf foo3, die sp erste und ruft func mit einem einfachen Sprung zerstört, die nicht Stapelrahmen schaffen würde. Aber es passiert nicht. Das Programm läuft in func bei (Assembly Code) Zeile 47 mit einem call und sauber sp Objekt danach. Die Optimierung wird nicht passieren, auch wenn ich ~Simple() lösche.

Also, wie kann ich TCO in diesem Fall auslösen?

Answer 1

Beachten Sie zuerst, dass das Beispiel einen doppelt freien Bug hat. Wenn der move-constructor aufgerufen wird, ist sp.buffer nicht auf nullptr gesetzt, so wie es sein muss, so dass jetzt zwei Zeiger auf den Puffer existieren, um später gelöscht zu werden. Eine einfachere Version, die den Zeiger verwaltet korrekt ist:

struct Simple { 
    std::unique_ptr<int[]> buffer {new int[1000]}; 
}; 

Mit dieser Lösung, lassen Sie sich fast alles inline und sieht, was foo3 wirklich tut in seiner ganzen Pracht:

using func_t = std::function<int(Sample&&)>&&; 
int foo3(func_t func) { 
    int* buffer1 = new int[1000]; // the unused local 
    int* buffer2 = new int[1000]; // the call argument 
    if (!func) { 
    delete[] buffer2; 
    delete[] buffer1; 
    throw bad_function_call; 
    } 
    try { 
    int retval = func(buffer2); // <-- the call 
    } catch (...) { 
    delete[] buffer2; 
    delete[] buffer1; 
    throw; 
    } 
    delete[] buffer2; 
    delete[] buffer1; 
    return retval;    // <-- the return 
} 

Der Fall buffer1 einfach ist. Es ist ein unbenutztes lokales und die einzigen Nebenwirkungen sind Zuteilung und Freigabe, die Compiler überspringen dürfen. Ein intelligent genug Compiler könnte das unbenutzte lokale vollständig entfernen. clang ++ 5.0 scheint dies zu erreichen, aber g ++ 7.2 nicht.

Interessanter ist buffer2. func nimmt eine nicht konstante rvalue-Referenz an. Es kann das Argument ändern. Zum Beispiel kann es sich davon bewegen. Aber vielleicht nicht. Das temporäre kann noch einen Puffer besitzen, der nach dem Anruf gelöscht werden muss und foo3 muss dies tun. Der Anruf ist nicht ein Tail Call.

Wie beobachtet, kommen wir zu einem Endrekursion näher, indem Sie einfach den Puffer undicht:

struct Simple { 
    int* buffer = new int[1000]; 
}; 

, die ein bisschen betrügt, weil ein großer Teil der Frage über Call-Optimierung in das Gesicht des nicht-triviale Destruktoren Schwanz ist. Aber lass uns das unterhalten. Wie beobachtet, führt dies allein nicht zu einem Tail-Call.

Zunächst einmal ist zu beachten, dass die Übergabe per Referenz eine elegante Form der Zeigerübergabe darstellt. Das Objekt muss immer noch irgendwo vorhanden sein, und das ist auf dem Stapel im Aufrufer. Wenn der Stack des Callers während des Aufrufs aktiv und nicht leer gehalten werden soll, wird die Optimierung des Endanrufs ausgeschlossen.

Um einen Tail Call zu ermöglichen, wollen wir func 's Argumente in Registern übergeben, so dass es nicht im foo3 Stack leben muss. Dies lässt darauf schließen wir nach Wert übergeben sollte: in einem Register übergeben

int foo2(Simple); // etc. 

Das SysV ABI schreibt vor, dass zu können, muss es sein trivialer kopierbar, beweglich und zerstörbar. Als Struktur, die einen int* einwickelt, haben wir das abgedeckt. Fun fact: Wir können hier keine std::unique_ptr mit einem No-Op-Deleter verwenden, weil das nicht trivial zerstörbar ist.

Trotzdem sehen wir immer noch kein Tail Call.Ich sehe keinen Grund dafür, aber ich bin kein Experte. Das Ersetzen des std::function durch einen Funktionszeiger führt zu einem Tail-Aufruf. Die std::function hat ein zusätzliches Argument im Aufruf und hat einen bedingten Wurf. Ist es möglich, dass es schwierig genug ist, sie zu optimieren?

Anyways, mit einem Funktionszeiger, g ++ 7.2 und Klirren ++ 5.0 tun, um die Endrekursion:

struct Simple { 
    int* buffer = new int[1000]; 
}; 

int foo2(Simple sp) { 
    return sp.buffer[std::rand()]; 
} 

using func_t = int (*)(Simple); 
int foo3(func_t func) { 
    return func(Simple()); 
} 

Aber das ist undicht. Können wir es besser machen? Diesem Typ ist ein Besitz zugeordnet, und wir möchten ihn von foo3 an func übergeben. Aber Typen mit nichttrivialen Destruktoren können nicht in Argumenten übergeben werden. Das bedeutet, dass ein RAII-Typ wie std::unique_ptr uns nicht dorthin bringt. Mit einem Konzept aus der GSL, wir können das Eigentum mindestens ausdrücken:

template<class T> using owner = T; 
struct Simple { 
    owner<int*> buffer = new int[1000]; 
}; 

Dann können wir hoffen, dass die statischen Analyse-Tools jetzt oder in der Zukunft erkennen können, dass foo2 Eigentum akzeptiert, aber nie buffer löschen.