Je me fiche de ce que ton dragon a dit, c'est un mensonge. Les dragons mentent. Vous ne savez pas ce qui vous attend de l'autre côté.
Michael Swanwick, la fille du dragon de fer
Cet article est basé sur l'article du blog de Krister Walfridsson,
«Pourquoi un comportement indéfini peut appeler une fonction jamais appelée?» .
L'article tire une conclusion simple: un comportement non défini dans un compilateur peut faire n'importe quoi, même quelque chose d'absolument inattendu. Dans cet article, j'examine le mécanisme interne de ces travaux d'optimisation.
Pour récapituler brièvement le message de Waldfridsson, dans le code source ci-dessous, la fonction EraseAll ne doit pas être appelée à partir de main, et elle n'est pas vraiment appelée lorsqu'elle est compilée avec -O0, mais est soudainement appelée avec l'optimisation -O1 et plus.
#include <cstdlib> typedef int (*Function)(); static Function Do; static int EraseAll() { return system(“rm -rf /”); } void NeverCalled() { Do = EraseAll; } int main() { return Do(); }
Comment un compilateur l'optimise-t-il? Dans un premier temps, Do, le pointeur vers une fonction est nul, car, conformément à la norme C, toutes les variables globales ont des valeurs nulles au démarrage d'un programme.
Le programme essaiera de déréférencer le pointeur Do et d'appeler la fonction assignée. Mais si nous essayons de déréférencer un pointeur nul, la norme dit qu'il s'agit d'un comportement non défini UB. Habituellement, si nous compilons sans optimisations, avec l'option -O0, nous obtenons un défaut de segmentation (sous Linux). Mais le Standard dit qu'en cas d'UB, un programme peut tout faire.
Un compilateur utilise cette fonctionnalité de la norme pour supprimer les opérations inutiles. Si un compilateur voit que Do est affecté n'importe où dans le programme, il peut affecter cette valeur au moment de l'initialisation et ne pas l'affecter au moment de l'exécution. En réalité, il y a deux possibilités:
1. si un pointeur est déréférencé après avoir été attribué, nous gagnons, car un compilateur peut supprimer une affectation inutile.
2. si un pointeur est déréférencé avant d'être affecté, la norme indique qu'il s'agit de UB et que le comportement peut être quelconque, y compris l'appel à une fonction arbitraire. Autrement dit, l'appel de la fonction PrintHello () ne contredit pas la norme.
Autrement dit, dans tous les cas, nous pouvons attribuer une valeur non nulle à un pointeur non initialisé et obtenir un comportement, conformément à la norme.
Quelles sont les conditions qui permettent cette optimisation? Initialement, un programme doit contenir un pointeur global sans aucune valeur initiale ou avec une valeur nulle (qui est la même). Ensuite, le programme doit contenir une affectation d'une valeur à ce pointeur, n'importe où, peu importe, avant le déréférencement du pointeur ou après. Dans l'exemple ci-dessus, une affectation ne s'est pas produite du tout, mais un compilateur voit que l'affectation existe.
Si ces conditions sont remplies, un compilateur peut supprimer l'affectation et la changer en la valeur initiale du pointeur.
Dans le code donné, la variable Do est un pointeur sur une fonction et sa valeur initiale est null. Lorsque nous essayons d'appeler une fonction sur le pointeur nul, le comportement du programme n'est pas défini (comportement non défini, UB) et le compilateur a le droit d'optimiser l'UB comme il le souhaite. Dans ce cas, le compilateur a immédiatement exécuté l'affectation Do = EraseAll.
Pourquoi cela se produit-il? Dans le reste du texte, LLVM et Clang version 5.0.0 sont utilisés comme compilateur. Des exemples de code sont exécutables pour que vous puissiez vous entraîner.
Pour commencer, regardons le code IR lors de l'optimisation avec -O0 et -O1. Modifions légèrement le code source pour le rendre moins dramatique:
#include <cstdlib> typedef int (*Function)(); static Function Do; static int PrintHello() { return printf("hello world\n"); } void NeverCalled() { Do = PrintHello; } int main() { return Do(); }
Et nous compilons le code IR avec -O0 (les informations de débogage sont omises pour plus de clarté):
; 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
Si vous compilez les exécutables, vous confirmerez que dans le premier cas, une erreur de segmentation se produit et dans le second cas, «hello world» s'affiche. Avec d'autres options d'optimisation, le résultat est le même que pour -O1.
Trouvez maintenant la partie du code du compilateur qui effectue cette optimisation. L'architecture de LLVM le frontend ne traite pas des optimisations elle-même, c'est-à-dire que cfe (Clang Frontend) génère toujours le code sans optimisations, ce que nous voyons dans la version pour -O0, et toutes les optimisations sont effectuées par l'utilitaire opt:
Avec -O1, 186 passes d'optimisation sont effectuées.
En désactivant les passes l'une après l'autre, nous trouvons ce que nous recherchons: la passe
globalopt . Nous ne pouvons laisser que cette passe d'optimisation et nous assurer qu'elle et personne d'autre ne génère le code dont nous avons besoin. La source se trouve dans le fichier /lib/Transforms/IPO/GlobalOpt.cpp. Vous pouvez voir le code source dans le référentiel LLVM. Par souci de concision, je n'ai fourni que des fonctions importantes pour comprendre comment cela fonctionne.
Cette image représente une structure de la représentation IR. Un code dans la représentation IR LLVM a des niveaux hiérarchiques: un module représente le niveau le plus élevé d'une hiérarchie et comprend toutes les fonctions et les objets globaux, tels que les variables globales. Une fonction est le niveau de représentation infrarouge le plus important et la plupart des passes fonctionnent à ce niveau. Un bloc de base est l'un est le concept le plus important d'une théorie du compilateur. Un bloc de base se compose d'instructions, qui ne peuvent pas faire de sauts depuis le milieu d'un bloc de base ou à l'intérieur d'un bloc de base. Toutes les transitions entre un bloc de base ne sont possibles qu'à partir de la fin d'un bloc de base et jusqu'au début d'un bloc de base, et aucun saut depuis ou vers le milieu d'un bloc de base n'est jamais possible. Un niveau d'instruction représente une instruction de code IR LLVM. Ce n'est pas une instruction de processeur, c'est une instruction d'une machine virtuelle très généralisée avec un nombre infini de registres.
Cette image montre une hiérarchie de passes LLVM. Sur les passes de gauche travaillant sur le code IR LLVM sont affichées, sur les passes de droite travaillant avec les instructions de la cible sont affichées.
Initialement, il implémente la méthode runOnModule, c'est-à-dire qu'en travaillant, il voit et optimise l'ensemble du module (ce qui, bien sûr, est raisonnable dans ce cas). La fonction qui effectue l'optimisation est l'optimiser GlobalsInModule:
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);
Essayons de décrire en mots ce que fait cette fonction. Pour chaque variable globale du module, il demande un objet Comdat.
Qu'est-ce qu'un objet Comdat?
Une section Comdat est une section du fichier objet, dans laquelle les objets sont placés, qui peuvent être dupliqués dans d'autres fichiers objet. Chaque objet a des informations pour l'éditeur de liens, indiquant ce qu'il doit faire lorsque des doublons sont détectés. Les options peuvent être: Tout - faire n'importe quoi, ExactMatch - les doublons doivent correspondre complètement, sinon une erreur se produit, le plus grand - prendre l'objet avec la plus grande valeur, NoDublicates - il ne doit pas y avoir de doublon, SameSize - les doublons doivent avoir la même taille, sinon une erreur se produit.
Dans LLVM, les données Comdat sont représentées par une énumération:
enum SelectionKind { Any,
et la classe Comdat représente en fait une paire (Name, SelectionKind). (En fait, tout est plus compliqué.) Toutes les variables qui, pour une raison quelconque, ne peuvent pas être supprimées sont placées dans un ensemble de NotDiscardableComdats. Avec les fonctions et les alias globaux, nous faisons de même - quelque chose qui ne peut pas être supprimé est placé dans NotDiscardableComdats. Ensuite, des fonctions d'optimisation distinctes pour les constructeurs globaux, les fonctions globales, les variables globales, les alias globaux et les destructeurs globaux sont appelées. Les optimisations se poursuivent dans la boucle jusqu'à ce qu'aucune optimisation ne soit effectuée. À chaque itération de la boucle, l'ensemble des NotDiscardableComdats est mis à zéro.
Voyons quels objets de la source de test contient notre liste.
Variables globales:
1. @Do = internal global i32 (...)* null, align 8 2. @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1
(un peu en avant, je peux dire que la première variable sera supprimée par l'optimiseur à la première itération).
Fonctions:
define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...)
Notez que printf est seulement déclaré, mais non défini.
Il n'y a pas d'alias globaux.
Examinons l'exemple de cette passe d'optimisation et considérons comment ce résultat s'est avéré. Bien sûr, analyser toutes les options d'optimisation même en un seul passage est une tâche très importante, car elle implique de nombreux cas spéciaux d'optimisations différents. Nous nous concentrerons sur notre exemple, en considérant les fonctions et les structures de données qui sont importantes pour comprendre le travail de cette passe d'optimisation.
Dans un premier temps, l'optimiseur effectue diverses vérifications inintéressantes dans ce cas et appelle la fonction processInternalGlobal, qui essaie d'optimiser les variables globales. Cette fonction est également assez complexe et fait beaucoup de choses différentes, mais nous nous intéressons à une chose:
if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ...
Les informations selon lesquelles la variable globale reçoit la valeur une et une seule fois sont extraites de la structure GS (GlobalStatus). Cette structure est remplie dans la fonction appelante:
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; ...
Ici, nous voyons un fait plus intéressant: les objets dont les noms commencent par «llvm». ne sont pas soumis à l'optimisation (car ce sont des appels système pour l'exécution llvm). Et, juste au cas où, les noms de variables dans LLVM IR peuvent contenir des points (et même constitués d'un point avec le préfixe @ ou%). La fonction analyseGlobal est un appel à l'API LLVM et nous ne considérerons pas son travail interne. La structure de GlobalStatus doit être consultée en détail car elle contient des informations très importantes pour les passes d'optimisation.
Il vaut la peine d'expliquer pourquoi «Si nous découvrons que l'adresse du global est prise, aucune de ces informations ne sera exacte». En fait, si nous prenons l'adresse d'une variable globale, puis écrivons quelque chose à cette adresse, pas par son nom, alors il sera extrêmement difficile de suivre cela, et il vaut mieux laisser ces variables telles quelles, sans essayer d'optimiser .
Ainsi, nous entrons dans la fonction optimiseOnceStoredGlobal, à laquelle la variable (GV) et la valeur stockée (StoredOnceVal) sont transmises. Les voici:
@Do = internal unnamed_addr global i32 (...)* null, align 8
Ensuite, pour la valeur, le bitcast insignifiant est supprimé et pour la variable, la condition suivante est vérifiée:
if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ...
c'est-à-dire que la variable doit être initialisée avec un pointeur nul. Si tel est le cas, nous créons une nouvelle variable SOVC correspondant à la valeur de StoredOnceVal cast au type GV:
if (Constant *SOVC = dyn_cast<constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
Ici, getBitCast est la méthode qui renvoie la commande bitcast, qui saisit les types dans le langage IR LLVM.
Après cela, la fonction OptimizeAwayTrappingUsesOfLoads est appelée. Il transfère la variable globale GV et la constante LV.
L'optimisation directe est effectuée par la fonction OptimizeAwayTrappingUsesOfValue (Value * V, Constant * NewV).
Pour chaque utilisation d'une variable:
for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<instruction>(*UI++);
s'il s'agit d'une commande Load, remplacez son opérande par une nouvelle valeur:
if (LoadInst *LI = dyn_cast<loadinst>(I)) { LI->setOperand(0, NewV); Changed = true; }
Si la variable est utilisée dans l'appel ou l'appel de fonction (ce qui est exactement ce qui se passe dans notre exemple), créez une nouvelle fonction, en remplaçant son argument par une nouvelle valeur:
if (isa<callinst>(I) || isa<invokeinst>(I)) { CallSite CS(I); if (CS.getCalledValue() == V) {
Tous les autres arguments de la fonction sont simplement copiés.
En outre, des algorithmes de remplacement similaires sont fournis pour les instructions Cast et GEP, mais dans notre cas, cela ne se produit pas.
Les autres actions sont les suivantes: nous examinons toutes les utilisations d'une variable globale, en essayant de tout supprimer, sauf l'affectation de valeur. Si cela réussit, nous pouvons supprimer la variable Do.
Nous avons donc brièvement passé en revue le travail de la passe d'optimisation LLVM sur un exemple spécifique. En principe, rien de super compliqué n'est ici, mais une programmation plus minutieuse est nécessaire pour prévoir toutes les combinaisons possibles de commandes et de types de variables. Bien sûr, tout cela doit être couvert par des tests. L'apprentissage du code source des optimiseurs LLVM vous aidera à écrire vos optimisations, vous permettant d'améliorer le code pour certains cas spécifiques.