Es ist mir egal, was dein Drache gesagt hat, es ist eine Lüge. Drachen lügen. Sie wissen nicht, was auf der anderen Seite auf Sie wartet.
Michael Swanwick, die Tochter des Eisendrachen
Dieser Artikel basiert auf dem Beitrag im Blog von Krister Walfridsson:
„Warum kann undefiniertes Verhalten eine nie aufgerufene Funktion aufrufen?“ .
Der Artikel zieht eine einfache Schlussfolgerung: Undefiniertes Verhalten in einem Compiler kann alles, auch etwas absolut Unerwartetes. In diesem Artikel untersuche ich den internen Mechanismus dieser Optimierungsarbeiten.
Um Waldfridssons Beitrag im folgenden Quellcode kurz zusammenzufassen, sollte die EraseAll-Funktion nicht von main aufgerufen werden, und sie wird beim Kompilieren mit -O0 nicht wirklich aufgerufen, sondern plötzlich mit der Optimierung -O1 und höher.
#include <cstdlib> typedef int (*Function)(); static Function Do; static int EraseAll() { return system(“rm -rf /”); } void NeverCalled() { Do = EraseAll; } int main() { return Do(); }
Wie optimiert ein Compiler es? Zunächst ist der Zeiger auf eine Funktion ungültig, da gemäß dem C-Standard alle globalen Variablen beim Starten eines Programms Nullwerte haben.
Das Programm versucht, den Do-Zeiger zu dereferenzieren und die zugewiesene Funktion aufzurufen. Wenn wir jedoch versuchen, einen Nullzeiger dereferenzieren, sagt der Standard, dass es sich um ein undefiniertes UB-Verhalten handelt. Wenn wir ohne Optimierung mit der Option -O0 kompilieren, erhalten wir normalerweise einen Segmentierungsfehler (unter Linux). Aber der Standard sagt, dass im Fall von UB ein Programm alles kann.
Ein Compiler verwendet diese Funktion des Standards, um unnötige Operationen zu entfernen. Wenn ein Compiler feststellt, dass Do an einer beliebigen Stelle im Programm zugewiesen ist, kann er diesen Wert in der Initialisierungszeit zuweisen und nicht zur Laufzeit. In Wirklichkeit gibt es zwei Möglichkeiten:
1. Wenn ein Zeiger nach seiner Zuweisung dereferenziert wird, gewinnen wir, weil ein Compiler eine unnötige Zuweisung entfernen kann.
2. Wenn ein Zeiger dereferenziert wird, bevor er zugewiesen werden soll, gibt der Standard an, dass es sich um UB handelt, und das Verhalten kann beliebig sein, einschließlich des Aufrufs einer beliebigen Funktion. Das Aufrufen der Funktion PrintHello () widerspricht also nicht dem Standard.
Das heißt, wir können in jedem Fall einem nicht initialisierten Zeiger einen Wert ungleich Null zuweisen und das Verhalten gemäß dem Standard abrufen.
Welche Bedingungen ermöglichen diese Optimierung? Zu Beginn sollte ein Programm einen globalen Zeiger ohne Anfangswert oder mit Nullwert (das ist derselbe) enthalten. Als nächstes sollte das Programm eine Zuweisung eines Werts für diesen Zeiger enthalten, unabhängig davon, ob vor oder nach der Zeiger-Dereferenzierung. Im obigen Beispiel ist eine Zuweisung überhaupt nicht aufgetreten, aber ein Compiler sieht, dass die Zuweisung vorhanden ist.
Wenn diese Bedingungen erfüllt sind, kann ein Compiler die Zuordnung entfernen und in den Anfangswert des Zeigers ändern.
Im angegebenen Code ist die Variable Do ein Zeiger auf eine Funktion und hat den Anfangswert null. Wenn wir versuchen, eine Funktion für den Nullzeiger aufzurufen, ist das Verhalten des Programms undefiniert (undefiniertes Verhalten, UB) und der Compiler hat das Recht, die UB nach Belieben zu optimieren. In diesem Fall hat der Compiler die Zuweisung Do = EraseAll sofort ausgeführt.
Warum passiert das? Im Rest des Textes werden LLVM und Clang Version 5.0.0 als Compiler verwendet. Codebeispiele können ausgeführt werden, damit Sie sich selbst üben können.
Schauen wir uns zunächst den IR-Code an, wenn wir mit -O0 und -O1 optimieren. Lassen Sie uns den Quellcode leicht ändern, um ihn weniger dramatisch zu machen:
#include <cstdlib> typedef int (*Function)(); static Function Do; static int PrintHello() { return printf("hello world\n"); } void NeverCalled() { Do = PrintHello; } int main() { return Do(); }
Und wir kompilieren den IR-Code mit -O0 (die Debugging-Informationen werden aus Gründen der Übersichtlichkeit weggelassen):
; ModuleID = 'test.c' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @Do = internal global i32 (...)* null, align 8 @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() #0 { entry: store i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*), i32 (...)** @Do, align 8 ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %0 = load i32 (...)*, i32 (...)** @Do, align 8 %call = call i32 (...) %0() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) #1 And with -O1: ; ModuleID = 'test.ll' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() local_unnamed_addr #0 { entry: ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() local_unnamed_addr #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %call = call i32 (...) bitcast (i32 ()* @PrintHello to i32 (...)*)() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() unnamed_addr #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) local_unnamed_addr #1
Wenn Sie die ausführbaren Dateien kompilieren, bestätigen Sie, dass im ersten Fall ein Segmentierungsfehler auftritt und im zweiten Fall "Hallo Welt" angezeigt wird. Bei anderen Optimierungsoptionen ist das Ergebnis dasselbe wie bei -O1.
Suchen Sie nun den Teil des Compiler-Codes, der diese Optimierung durchführt. Die Architektur von LLVM, das Frontend, behandelt keine Optimierungen selbst, d. H. Cfe (Clang Frontend) generiert immer den Code ohne Optimierungen, die wir in der Version für -O0 sehen, und alle Optimierungen werden vom Dienstprogramm opt durchgeführt:
Mit -O1 werden 186 Optimierungsdurchläufe durchgeführt.
Wenn wir die Pässe nacheinander ausschalten, finden wir, wonach wir suchen: den
globalopt- Pass. Wir können nur diesen Optimierungsdurchlauf belassen und sicherstellen, dass er und niemand anderes den Code generiert, den wir benötigen. Die Quelle befindet sich in der Datei /lib/Transforms/IPO/GlobalOpt.cpp. Sie können den Quellcode im LLVM-Repository sehen. Der Kürze halber habe ich nur Funktionen bereitgestellt, die wichtig sind, um zu verstehen, wie es funktioniert.
Dieses Bild zeigt eine Struktur der IR-Darstellung. Ein Code in der LLVM-IR-Darstellung hat Hierarchieebenen: Ein Modul repräsentiert die höchste Ebene einer Hierarchie und enthält alle Funktionen und globalen Objekte, z. B. globale Variablen. Eine Funktion ist die wichtigste Ebene der IR-Darstellung, und die meisten Durchgänge funktionieren auf dieser Ebene. Ein Grundblock ist eines der wichtigsten Konzepte einer Compilertheorie. Ein Basisblock besteht aus Anweisungen, die keine Sprünge aus der Mitte eines Basisblocks oder innerhalb eines Basisblocks ausführen können. Alle Übergänge zwischen Basisblöcken sind nur von einem Ende eines Basisblocks bis zu einem Anfang eines Basisblocks möglich, und Sprünge von oder zu einer Mitte eines Basisblocks sind niemals möglich. Eine Befehlsebene repräsentiert eine LLVM-IR-Code-Anweisung. Es ist keine Anweisung eines Prozessors, sondern eine Anweisung einer sehr verallgemeinerten virtuellen Maschine mit einer unendlichen Anzahl von Registern.
Dieses Bild zeigt eine Hierarchie von LLVM-Durchläufen. Auf der linken Seite werden Durchgänge angezeigt, die mit dem LLVM-IR-Code arbeiten, auf der rechten Seite werden Durchgänge angezeigt, die mit den Anweisungen des Ziels arbeiten.
Zunächst wird die runOnModule-Methode implementiert, dh beim Arbeiten wird das gesamte Modul angezeigt und optimiert (was in diesem Fall natürlich sinnvoll ist). Die Funktion, die die Optimierung durchführt, ist optimizeGlobalsInModule:
static bool optimizeGlobalsInModule( Module &M, const DataLayout &DL, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { SmallSet<const comdat="Comdat" 8="8"> NotDiscardableComdats; bool Changed = false; bool LocalChange = true; while (LocalChange) { LocalChange = false; NotDiscardableComdats.clear(); for (const GlobalVariable &GV : M.globals()) if (const Comdat *C = GV.getComdat()) if (!GV.isDiscardableIfUnused() || !GV.use_empty()) NotDiscardableComdats.insert(C); for (Function &F : M) if (const Comdat *C = F.getComdat()) if (!F.isDefTriviallyDead()) NotDiscardableComdats.insert(C); for (GlobalAlias &GA : M.aliases()) if (const Comdat *C = GA.getComdat()) if (!GA.isDiscardableIfUnused() || !GA.use_empty()) NotDiscardableComdats.insert(C);
Versuchen wir in Worten zu beschreiben, was diese Funktion bewirkt. Für jede globale Variable im Modul wird ein Comdat-Objekt angefordert.
Was ist ein Comdat-Objekt?
Ein Comdat-Abschnitt ist ein Abschnitt in der Objektdatei, in dem Objekte platziert werden, die in anderen Objektdateien dupliziert werden können. Jedes Objekt verfügt über Informationen für den Linker, die angeben, was zu tun ist, wenn Duplikate erkannt werden. Die Optionen können sein: Beliebig - alles tun, ExactMatch - Duplikate müssen vollständig übereinstimmen, andernfalls tritt ein Fehler auf. Größte - Nehmen Sie das Objekt mit dem größten Wert. NoDublicates - Es sollte kein Duplikat vorhanden sein. SameSize - Duplikate müssen dieselbe Größe haben. Andernfalls tritt ein Fehler auf.
In LLVM werden Comdat-Daten durch eine Aufzählung dargestellt:
enum SelectionKind { Any,
und die Klasse Comdat repräsentiert tatsächlich ein Paar (Name, SelectionKind). (Tatsächlich ist alles komplizierter.) Alle Variablen, die aus irgendeinem Grund nicht gelöscht werden können, werden in einer Reihe von NotDiscardableComdats abgelegt. Mit Funktionen und globalen Aliasen machen wir dasselbe - etwas, das nicht gelöscht werden kann, wird in NotDiscardableComdats platziert. Anschließend werden separate Optimierungsfunktionen für globale Konstruktoren, globale Funktionen, globale Variablen, globale Aliase und globale Destruktoren aufgerufen. Optimierungen werden in der Schleife fortgesetzt, bis keine Optimierung mehr durchgeführt wird. Bei jeder Iteration der Schleife wird die Menge von NotDiscardableComdats auf Null gesetzt.
Mal sehen, welche Objekte der Liste unsere Testquelle enthält.
Globale Variablen:
1. @Do = internal global i32 (...)* null, align 8 2. @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1
(Mit Blick auf die Zukunft kann ich sagen, dass die erste Variable bei der ersten Iteration vom Optimierer gelöscht wird.)
Funktionen:
define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...)
Beachten Sie, dass printf nur deklariert, aber nicht definiert ist.
Es gibt keine globalen Aliase.
Schauen wir uns das Beispiel dieses Optimierungsdurchlaufs an und betrachten wir, wie sich dieses Ergebnis herausstellte. Natürlich ist es eine sehr große Aufgabe, alle Optimierungsoptionen auch nur in einem Durchgang zu analysieren, da es sich um viele verschiedene Spezialfälle von Optimierungen handelt. Wir werden uns auf unser Beispiel konzentrieren und die Funktionen und Datenstrukturen berücksichtigen, die für das Verständnis der Arbeit dieses Optimierungsdurchlaufs wichtig sind.
Zunächst führt der Optimierer in diesem Fall verschiedene uninteressante Überprüfungen durch und ruft die Funktion processInternalGlobal auf, die versucht, globale Variablen zu optimieren. Diese Funktion ist auch ziemlich komplex und macht viele verschiedene Dinge, aber wir sind an einer Sache interessiert:
if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ...
Die Information, dass der globalen Variablen der Wert eins und nur einmal zugewiesen wird, wird aus der GS-Struktur (GlobalStatus) extrahiert. Diese Struktur wird in der aufrufenden Funktion ausgefüllt:
static bool processGlobal(GlobalValue &GV, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { if (GV.getName().startswith("llvm.")) return false; GlobalStatus GS; if (GlobalStatus::analyzeGlobal(&GV, GS)) return false; ...
Hier sehen wir eine weitere interessante Tatsache: Objekte, deren Namen mit "llvm" beginnen. unterliegen keiner Optimierung (da es sich um Systemaufrufe für die llvm-Laufzeit handelt). Und nur für den Fall, dass die Namen von Variablen in LLVM IR Punkte enthalten können (und sogar aus einem Punkt mit dem Präfix @ oder% bestehen). Die Funktion analyseGlobal ist ein Aufruf der LLVM-API, und wir werden ihre interne Arbeit nicht berücksichtigen. Die Struktur von GlobalStatus sollte im Detail betrachtet werden, da sie sehr wichtige Informationen für Optimierungsdurchläufe enthält.
Es lohnt sich zu erklären, warum "Wenn wir herausfinden, dass die Adresse des globalen verwendet wird, ist keine dieser Informationen korrekt." Wenn wir die Adresse einer globalen Variablen nehmen und dann etwas an diese Adresse schreiben, nicht namentlich, ist es äußerst schwierig, dies zu verfolgen, und es ist besser, solche Variablen unverändert zu lassen, ohne zu versuchen, sie zu optimieren .
Wir gelangen also in die Funktion optimizeOnceStoredGlobal, an die die Variable (GV) und der gespeicherte Wert (StoredOnceVal) übergeben werden. Hier sind sie:
@Do = internal unnamed_addr global i32 (...)* null, align 8
Als nächstes wird für den Wert der unbedeutende Bitcast gelöscht und für die Variable die folgende Bedingung überprüft:
if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ...
Das heißt, die Variable muss mit einem Nullzeiger initialisiert werden. Wenn dies der Fall ist, erstellen wir eine neue SOVC-Variable, die dem Wert von StoredOnceVal entspricht, der in den GV-Typ umgewandelt wurde:
if (Constant *SOVC = dyn_cast<constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
Hier ist getBitCast die Methode, die den Bitcast-Befehl zurückgibt, der die Typen in der LLVM-IR-Sprache eingibt.
Danach wird die Funktion OptimizeAwayTrappingUsesOfLoads aufgerufen. Es überträgt die globale Variable GV und die Konstante LV.
Die direkte Optimierung erfolgt über die Funktion OptimizeAwayTrappingUsesOfValue (Wert * V, Konstante * NewV).
Für jede Verwendung einer Variablen:
for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<instruction>(*UI++);
Wenn dies ein Ladebefehl ist, ersetzen Sie seinen Operanden durch einen neuen Wert:
if (LoadInst *LI = dyn_cast<loadinst>(I)) { LI->setOperand(0, NewV); Changed = true; }
Wenn die Variable im Funktionsaufruf oder im Funktionsaufruf verwendet wird (genau das passiert in unserem Beispiel), erstellen Sie eine neue Funktion und ersetzen Sie ihr Argument durch einen neuen Wert:
if (isa<callinst>(I) || isa<invokeinst>(I)) { CallSite CS(I); if (CS.getCalledValue() == V) {
Alle anderen Argumente für die Funktion werden einfach kopiert.
Ähnliche Ersetzungsalgorithmen werden auch für die Cast- und GEP-Anweisungen bereitgestellt, in unserem Fall ist dies jedoch nicht der Fall.
Die weiteren Aktionen lauten wie folgt: Wir untersuchen alle Verwendungen einer globalen Variablen und versuchen, alles außer der Wertzuweisung zu löschen. Wenn dies erfolgreich ist, können wir die Do-Variable löschen.
Daher haben wir die Arbeit des Optimierungspasses LLVM an einem bestimmten Beispiel kurz besprochen. Im Prinzip ist hier nichts sehr Kompliziertes, aber eine sorgfältigere Programmierung ist erforderlich, um alle möglichen Kombinationen von Befehlen und Variablentypen zu ermöglichen. All dies muss natürlich durch Tests abgedeckt werden. Das Erlernen des Quellcodes von LLVM-Optimierern hilft Ihnen beim Schreiben Ihrer Optimierungen, sodass Sie den Code für bestimmte Fälle verbessern können.