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 suelen clasificarse por sensibilidad al flujo y sensibilidad al contexto. Pueden determinar información de alias posibles o de alias obligatorios. El término análisis de alias suele usarse indistintamente con el análisis de puntos a los que apuntar , un caso específico.

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

Descripción general

En general, el análisis de alias determina si las referencias de memoria independientes 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 apuntan a la misma ubicación de memoria).
No se puede determinar de manera concluyente en tiempo de compilación si p y q son alias o no.

Si p y q no pueden crear alias, entonces i = p.foo + 3;se pueden cambiar a i = 4. Si p y q deben crear alias, entonces i = p.foo + 3;se pueden cambiar a i = 5porque p.foo + 3= q.foo + 3. En ambos casos, podemos realizar optimizaciones a partir del conocimiento del alias (asumiendo que ningún otro hilo que actualice las mismas ubicaciones puede intercalarse con el hilo actual, o que el modelo de memoria del lenguaje permite 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 crean 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 may-alias si se desconoce su alias.

Realizar 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 crear alias entre sí. Para el análisis que se presenta aquí, se supone que las optimizaciones realizadas aquí ocurren en una representación intermedia de bajo nivel del programa. Es decir, 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 de tipo seguro , 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 diferentes clases de alias:

Dos variables de diferentes tipos no pueden estar en la misma clase de alias, ya que es una propiedad de los lenguajes fuertemente tipados y libres de referencias de memoria (es decir, las referencias a ubicaciones de memoria no se pueden cambiar directamente) que dos variables de diferentes tipos no pueden compartir la misma ubicación de memoria simultáneamente.
Las asignaciones locales del marco de pila actual no pueden pertenecer a la misma clase de alias que cualquier 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 asignaciones de memoria.
En general, cada campo de registro de cada tipo de registro tiene su propia clase de alias, ya que la disciplina de tipificación normalmente solo permite crear alias para registros del mismo tipo. Como todos los registros de un tipo se almacenarán en un formato idéntico en la memoria, un campo solo puede crear alias para sí mismo.
De manera similar, cada matriz de un tipo determinado tiene su propia clase de alias.

Al realizar un análisis de alias para el código, cada carga y almacenamiento en la memoria debe etiquetarse con su clase. Entonces tenemos la propiedad útil, dadas las ubicaciones de memoria y con clases de alias, de que if then may-alias , y if then las ubicaciones de memoria no tendrán alias. $A_{i}$ $B_{j}$ $i,j$ $i=j$ $A_{i}$ $B_{j}$ $i\neq j$

Análisis de alias basado en flujo

El análisis basado en flujo se puede aplicar a programas en un lenguaje con referencias o conversión de tipos. El análisis basado en flujo se puede utilizar en lugar del análisis basado en tipos o como complemento de este. 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 estar en 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 única clase de alias.

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). Implementación de compiladores modernos en aprendizaje automático . 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.