No me importa lo que haya dicho tu dragón, es mentira. Los dragones mienten. No sabes lo que te espera del otro lado.
Michael Swanwick, la hija del dragón de hierro
Este artículo se basa en la publicación en el blog de Krister Walfridsson,
"¿Por qué el comportamiento indefinido puede llamar a una función que nunca se llama?" .
El artículo saca una conclusión simple: el comportamiento indefinido en un compilador puede hacer cualquier cosa, incluso algo absolutamente inesperado. En este artículo, examino el mecanismo interno de este trabajo de optimización.
Para resumir brevemente la publicación de Waldfridsson, en el código fuente a continuación, la función EraseAll no debe llamarse desde main, y realmente no se llama cuando se compila con -O0, pero de repente se llama con optimización -O1 y superior.
#include <cstdlib> typedef int (*Function)(); static Function Do; static int EraseAll() { return system(“rm -rf /”); } void NeverCalled() { Do = EraseAll; } int main() { return Do(); }
¿Cómo lo optimiza un compilador? Al principio, Do, el puntero a una función es nulo, porque, de acuerdo con el estándar C, todas las variables globales tienen valores cero cuando se inicia un programa.
El programa intentará desreferenciar el puntero Do y llamar a la función asignada. Pero si tratamos de desreferenciar un puntero nulo, el estándar dice que es UB, comportamiento indefinido. Por lo general, si compilamos sin optimizaciones, con la opción -O0, obtenemos una falla de segmentación (en Linux). Pero el Estándar dice que en el caso de UB, un programa puede hacer cualquier cosa.
Un compilador utiliza esta característica del estándar para eliminar operaciones innecesarias. Si un compilador ve que Do está asignado en cualquier parte del programa, puede asignar este valor en el tiempo de inicialización y no asignarlo en tiempo de ejecución. En realidad, hay dos posibilidades:
1. si un puntero se desreferencia después de que se debe asignar, ganamos, porque un compilador puede eliminar una asignación innecesaria.
2. si un puntero se desreferencia antes de que deba asignarse, el estándar dice que es UB, y el comportamiento puede ser cualquiera, incluida la llamada a una función arbitraria. Es decir, llamar a la función PrintHello () no contradice el estándar.
Es decir, en cualquier caso, podemos asignar algún valor no nulo a un puntero no inicializado y obtener un comportamiento, de acuerdo con el estándar.
¿Cuáles son las condiciones que hacen posible esta optimización? Inicialmente, un programa debe contener un puntero global sin ningún valor inicial o con un valor nulo (que es lo mismo). A continuación, el programa debe contener una asignación de un valor para este puntero, en cualquier lugar, sin importar, antes de que el puntero se desreferencia o después. En el ejemplo anterior, no se ha producido una asignación, pero un compilador ve que la asignación existe.
Si se cumplen estas condiciones, un compilador puede eliminar la asignación y cambiarla al valor inicial del puntero.
En el código dado, la variable Do es un puntero a una función y tiene el valor inicial nulo. Cuando intentamos llamar a una función en el puntero nulo, el comportamiento del programa es indefinido (comportamiento indefinido, UB) y el compilador tiene derecho a optimizar el UB como lo desee. En este caso, el compilador ejecutó inmediatamente la asignación Do = EraseAll.
¿Por qué sucede esto? En el resto del texto, LLVM y Clang versión 5.0.0 se utilizan como compilador. Los ejemplos de código son ejecutables para que pueda practicar usted mismo.
Para empezar, echemos un vistazo al código IR al optimizar con -O0 y -O1. Cambiemos ligeramente el código fuente para hacerlo menos dramático:
#include <cstdlib> typedef int (*Function)(); static Function Do; static int PrintHello() { return printf("hello world\n"); } void NeverCalled() { Do = PrintHello; } int main() { return Do(); }
Y compilamos el código IR con -O0 (la información de depuración se omite para mayor claridad):
; 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 compila los ejecutables, confirmará que en el primer caso, se produce un error de segmentación, y en el segundo caso, se muestra "hello world". Con otras opciones de optimización, el resultado es el mismo que para -O1.
Ahora encuentre la parte del código del compilador que realiza esta optimización. La arquitectura de LLVM el frontend no se ocupa de las optimizaciones en sí misma, es decir, cfe (Clang Frontend) siempre genera el código sin optimizaciones, que vemos en la versión para -O0, y todas las optimizaciones son realizadas por la utilidad opt:
Con -O1, se realizan 186 pases de optimización.
Desactivando los pases uno tras otro, encontramos lo que estamos buscando: el pase
globalopt . Solo podemos dejar este pase de optimización y asegurarnos de que, y nadie más, genere el código que necesitamos. La fuente está en el archivo /lib/Transforms/IPO/GlobalOpt.cpp. Puede ver el código fuente en el repositorio LLVM. Por brevedad, solo he proporcionado funciones importantes para comprender cómo funciona.
Esta imagen representa una estructura de la representación IR. Un código en la representación LLVM IR tiene niveles jerárquicos: un módulo representa el nivel más alto de una jerarquía e incluye todas las funciones y objetos globales, como las variables globales. Una función es el nivel más importante de representación IR y la mayoría de los pases funcionan en este nivel. Un bloque básico es uno de los conceptos más importantes de una teoría de compilación. Un bloque básico consta de instrucciones, que no pueden realizar saltos desde la mitad de un bloque básico o dentro de un bloque básico. Todas las transiciones entre el bloque básico son posibles solo desde el final de un bloque básico y hasta el comienzo de un bloque básico, y nunca es posible ningún salto desde o hacia la mitad de un bloque básico. Un nivel de instrucción representa una instrucción de código IR LLVM. No es una instrucción de procesador, es una instrucción de una máquina virtual muy generalizada con un número infinito de registros.
Esta imagen muestra una jerarquía de pases LLVM. A la izquierda se muestran los pases que funcionan con el código LLVM IR, en el lado derecho se muestran pases que funcionan con las instrucciones del objetivo.
Inicialmente, implementa el método runOnModule, es decir, cuando trabaja, ve y optimiza todo el módulo (que, por supuesto, es razonable en este caso). La función que realiza la optimización es optimizarGlobalsInModule:
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);
Tratemos de describir con palabras lo que hace esta función. Para cada variable global en el módulo, solicita un objeto Comdat.
¿Qué es un objeto Comdat?
Una sección de Comdat es una sección en el archivo de objetos, en la que se colocan los objetos, que se pueden duplicar en otros archivos de objetos. Cada objeto tiene información para el enlazador, que indica lo que debe hacer cuando se detectan duplicados. Las opciones pueden ser: Cualquiera - hacer cualquier cosa, ExactMatch - los duplicados deben coincidir completamente, de lo contrario se produce un error, Mayor - tomar el objeto con el valor más grande, NoDublicates - no debe haber un duplicado, SameSize - los duplicados deben tener el mismo tamaño, de lo contrario se produce un error.
En LLVM, los datos de Comdat se representan mediante una enumeración:
enum SelectionKind { Any,
y la clase Comdat en realidad representa un par (Name, SelectionKind). (De hecho, todo es más complicado). Todas las variables que por alguna razón no se pueden eliminar se colocan en un conjunto de NotDiscardableComdats. Con funciones y alias globales, hacemos lo mismo: algo que no se puede eliminar se coloca en NotDiscardableComdats. Luego, se llaman funciones de optimización separadas para constructores globales, funciones globales, variables globales, alias globales y destructores globales. Las optimizaciones continúan en el ciclo hasta que no se realiza ninguna optimización. En cada iteración del bucle, el conjunto de NotDiscardableComdats se establece en cero.
Veamos qué objetos de la lista contiene nuestra fuente de prueba.
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 poco mirando hacia el futuro, puedo decir que la primera variable será eliminada por el optimizador en la primera iteración).
Funciones:
define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...)
Tenga en cuenta que printf solo se declara, pero no se define.
No hay alias globales.
Veamos el ejemplo de este pase de optimización y consideremos cómo resultó este resultado. Por supuesto, analizar todas las opciones de optimización, incluso en una sola pasada, es una tarea muy grande, porque involucra muchos casos especiales diferentes de optimizaciones. Nos concentraremos en nuestro ejemplo, considerando aquellas funciones y estructuras de datos que son importantes para comprender el trabajo de este pase de optimización.
Inicialmente, el optimizador realiza varias comprobaciones poco interesantes en este caso y llama a la función processInternalGlobal, que intenta optimizar las variables globales. Esta función también es bastante compleja y hace muchas cosas diferentes, pero nos interesa una cosa:
if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ...
La información de que a la variable global se le asigna el valor uno y solo una vez se extrae de la estructura GS (GlobalStatus). Esta estructura se completa en la función de llamada:
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; ...
Aquí vemos un hecho más interesante: los objetos cuyos nombres comienzan con "llvm". no están sujetos a optimización (ya que son llamadas del sistema para llvm runtime). Y, por si acaso, los nombres de las variables en LLVM IR pueden contener puntos (e incluso constar de un punto con el prefijo @ o%). La función analyGlobal es una llamada a la API LLVM y no consideraremos su trabajo interno. La estructura de GlobalStatus debe verse en detalle ya que contiene información muy importante para los pases de optimización.
Vale la pena explicar por qué "Si descubrimos que se toma la dirección de lo global, nada de esta información será precisa". De hecho, si tomamos la dirección de una variable global, y luego escribimos algo en esta dirección, no por nombre, será extremadamente difícil rastrear esto, y es mejor dejar las variables como están, sin tratar de optimizar .
Entonces, ingresamos a la función optimiceOnceStoredGlobal, a la cual se pasan la variable (GV) y el valor almacenado (StoredOnceVal). Aquí están:
@Do = internal unnamed_addr global i32 (...)* null, align 8
A continuación, para el valor, se elimina el bitcast insignificante y para la variable se verifica la siguiente condición:
if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ...
es decir, la variable debe inicializarse con un puntero nulo. Si este es el caso, creamos una nueva variable SOVC correspondiente al valor de StoredOnceVal emitido al tipo GV:
if (Constant *SOVC = dyn_cast<constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
Aquí, getBitCast es el método que devuelve el comando bitcast, que escribe los tipos en el lenguaje LLVM IR.
Después de eso, se llama a la función OptimizeAwayTrappingUsesOfLoads. Transfiere la variable global GV y la constante LV.
La optimización directa se realiza mediante la función OptimizeAwayTrappingUsesOfValue (Value * V, Constant * NewV).
Para cada uso de una variable:
for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<instruction>(*UI++);
Si se trata de un comando Cargar, reemplace su operando con un nuevo valor:
if (LoadInst *LI = dyn_cast<loadinst>(I)) { LI->setOperand(0, NewV); Changed = true; }
Si la variable se usa en la función invocar o invocar (que es exactamente lo que sucede en nuestro ejemplo), cree una nueva función, reemplazando su argumento con un nuevo valor:
if (isa<callinst>(I) || isa<invokeinst>(I)) { CallSite CS(I); if (CS.getCalledValue() == V) {
Todos los demás argumentos de la función simplemente se copian.
Además, se proporcionan algoritmos de reemplazo similares para las instrucciones Cast y GEP, pero en nuestro caso esto no sucede.
Las acciones adicionales son las siguientes: examinamos todos los usos de una variable global, tratando de eliminar todo, excepto la asignación de valor. Si esto es exitoso, entonces podemos eliminar la variable Do.
Entonces, revisamos brevemente el trabajo del paso de optimización LLVM en un ejemplo específico. En principio, aquí no hay nada súper complicado, pero se requiere una programación más cuidadosa para proporcionar todas las combinaciones posibles de comandos y tipos de variables. Por supuesto, todo esto debe ser cubierto por pruebas. Aprender el código fuente de los optimizadores LLVM lo ayudará a escribir sus optimizaciones, permitiéndole mejorar el código para algunos casos específicos.