Análisis de alias

El análisis de alias es una técnica de la teoría de compiladores que se utiliza para determinar si se puede acceder a una ubicación de almacenamiento de más de una manera. Se dice que dos punteros tienen alias si apuntan a la misma ubicación.

Las técnicas de análisis de alias se clasifican generalmente según su sensibilidad al flujo y al contexto. Pueden determinar si una información puede contener alias o debe contenerlos. El término análisis de alias se usa a menudo indistintamente con el análisis de referencias , un caso específico.

Los analizadores de alias tienen como objetivo generar y calcular información útil para comprender el aliasing en los programas.

Descripción general

En general, el análisis de alias determina si las referencias de memoria separadas apuntan o no a la misma área de memoria. Esto permite al compilador determinar qué variables del programa se verán afectadas por una instrucción. Por ejemplo, considere la siguiente sección de código que accede a miembros de estructuras:

p . foo = 1 ; q . foo = 2 ; i = p . foo + 3 ;

Aquí hay tres posibles casos de alias:

Las variables p y q no pueden tener alias (es decir, nunca apuntan a la misma ubicación de memoria).
Las variables p y q deben tener un alias (es decir, siempre deben apuntar a la misma ubicación de memoria).
En tiempo de compilación no se puede determinar de forma concluyente si p y q son alias o no.

Si p y q no pueden tener alias, entonces i = p.foo + 3;se puede cambiar a i = 4. Si p y q deben tener alias, entonces i = p.foo + 3;se puede cambiar a i = 5porque p.foo + 3= q.foo + 3. En ambos casos, podemos realizar optimizaciones a partir del conocimiento del alias (suponiendo que ningún otro hilo que actualice las mismas ubicaciones pueda intercalarse con el hilo actual, o que el modelo de memoria del lenguaje permita que esas actualizaciones no sean inmediatamente visibles para el hilo actual en ausencia de construcciones de sincronización explícitas ). Por otro lado, si no se sabe si p y q tienen alias o no, entonces no se pueden realizar optimizaciones y se debe ejecutar todo el código para obtener el resultado. Se dice que dos referencias de memoria tienen una relación de alias posible si se desconoce su alias.

Realizando análisis de alias

En el análisis de alias, dividimos la memoria del programa en clases de alias . Las clases de alias son conjuntos disjuntos de ubicaciones que no pueden tener alias entre sí. Para este análisis, se asume que las optimizaciones realizadas aquí se aplican a una representación intermedia de bajo nivel del programa. Esto significa que el programa se ha compilado en operaciones binarias, saltos, movimientos entre registros, movimientos de registros a memoria, movimientos de memoria a registros, bifurcaciones y llamadas/retornos de funciones.

Análisis de alias basado en tipos

Si el lenguaje que se está compilando es seguro en cuanto a tipos , el verificador de tipos del compilador es correcto y el lenguaje carece de la capacidad de crear punteros que hagan referencia a variables locales (como ML , Haskell o Java ), entonces se pueden realizar algunas optimizaciones útiles. ^{[ 1 ]} Hay muchos casos en los que sabemos que dos ubicaciones de memoria deben estar en clases de alias diferentes:

Dos variables de tipos diferentes no pueden estar en la misma clase de alias, ya que es una propiedad de los lenguajes fuertemente tipados y sin referencias a memoria (es decir, las referencias a ubicaciones de memoria no se pueden cambiar directamente) que dos variables de tipos diferentes no pueden compartir la misma ubicación de memoria simultáneamente.
Las asignaciones locales al marco de pila actual no pueden pertenecer a la misma clase de alias que ninguna asignación anterior de otro marco de pila. Esto se debe a que las nuevas asignaciones de memoria deben ser independientes de todas las demás.
En general, cada campo de registro de cada tipo de registro tiene su propia clase de alias, ya que la disciplina de tipado normalmente solo permite que los registros del mismo tipo tengan alias. Dado que todos los registros de un tipo se almacenarán en memoria en un formato idéntico, un campo solo puede tener un alias consigo mismo.
De manera similar, cada matriz de un tipo dado tiene su propia clase de alias.

Al realizar un análisis de alias para el código, cada carga y almacenamiento en memoria debe etiquetarse con su clase. Luego tenemos la propiedad útil, dadas las ubicaciones de memoria. $A_{i}$ y $B_{j}$ con $i,j$ clases alias, que si $i=j$ entonces $A_{i}$ mayo-alias $B_{j}$ y si $i\neq j$ De esta forma, las ubicaciones de memoria no se superpondrán.

Análisis de alias basado en flujo

El análisis basado en flujo se puede aplicar a programas escritos en lenguajes con referencias o conversión de tipos. Este análisis puede utilizarse en lugar del análisis basado en tipos o como complemento. En el análisis basado en flujo, se crean nuevas clases de alias para cada asignación de memoria y para cada variable global y local cuya dirección se haya utilizado. Las referencias pueden apuntar a más de un valor a lo largo del tiempo y, por lo tanto, pueden pertenecer a más de una clase de alias. Esto significa que cada ubicación de memoria tiene un conjunto de clases de alias en lugar de una sola.

Véase también

Referencias

↑ Diwan, Amer; McKinley, Kathryn S.; Moss, J. Eliot B. (1998). "Análisis de alias basado en tipos" . Actas de la conferencia ACM SIGPLAN 1998 sobre diseño e implementación de lenguajes de programación - PLDI '98 . Montreal, Quebec, Canadá: ACM Press. págs. 106–117 . doi : 10.1145/277650.277670 . ISBN 978-0-89791-987-6. S2CID 5155574 .

Appel, Andrew W. (1998). Modern Compiler Implementation in ML . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-60764-7.

Enlaces externos

Taxonomía y aplicaciones del análisis de alias : Tesis de maestría que ofrece una introducción al campo.

[1] Diwan, Amer; McKinley, Kathryn S.; Moss, J. Eliot B. (1998). "Análisis de alias basado en tipos" . Actas de la conferencia ACM SIGPLAN 1998 sobre diseño e implementación de lenguajes de programación - PLDI '98 . Montreal, Quebec, Canadá: ACM Press. págs. 106–117 . doi : 10.1145/277650.277670 . ISBN 978-0-89791-987-6. S2CID 5155574 .

[ 1 ]