El análisis de alias es una técnica en la teoría del compilador , que se utiliza para determinar si se puede acceder a una ubicación de almacenamiento de más de una forma. Se dice que dos punteros tienen un alias si apuntan a la misma ubicación.
Las técnicas de análisis de alias generalmente se clasifican por sensibilidad al flujo y sensibilidad al contexto. Pueden determinar información de may-alias o must-alias. El término análisis de alias a menudo se usa indistintamente con análisis de puntos a , un caso específico.
Los analizadores de alias intentan generar 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 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 declaració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 ;
Hay tres posibles casos de alias aquí:
- Las variables pyq no pueden alias (es decir, nunca apuntan a la misma ubicación de memoria).
- Las variables pyq 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 pyq son alias o no.
Si pyq no pueden tener un alias, entonces i = p.foo + 3;
se puede cambiar a i = 4
. Si pyq deben tener un alias, entonces i = p.foo + 3;
se puede cambiar a i = 5
porque p.foo + 3
= q.foo + 3
. En ambos casos, podemos realizar optimizaciones a partir del conocimiento de alias (suponiendo que ningún otro hilo que actualice las mismas ubicaciones pueda intercalar 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 pyq son 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.
Realización de 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 de ubicaciones disjuntos que no pueden crear alias entre sí. Para la discusión aquí, se supone que las optimizaciones realizadas aquí ocurren en una representación intermedia de bajo nivel del programa. Es decir que el programa ha sido compilado en operaciones binarias, salta, se mueve entre registros, se mueve de registros a memoria, se mueve de memoria a registros, bifurca y llamadas / retornos de funciones.
Análisis de alias basado en tipos
Si el lenguaje que se está compilando es seguro para 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 diferentes clases de alias:
- Dos variables de diferentes tipos no pueden estar en la misma clase de alias ya que es una propiedad de lenguajes fuertemente tipados, sin referencias de memoria (es decir, las referencias a ubicaciones de memoria no se pueden cambiar directamente) en los que dos variables de diferentes tipos no pueden compartir la misma ubicación de memoria simultaneamente.
- Las asignaciones locales al marco de pila actual no pueden estar en la misma clase de alias que cualquier asignación anterior de otro marco de pila. Este es el caso porque las nuevas asignaciones de memoria deben estar separadas de todas las demás asignaciones de memoria.
- Cada campo de registro de cada tipo de registro tiene su propia clase de alias, en general, porque la disciplina de mecanografía generalmente solo permite registros del mismo tipo a alias. Dado que todos los registros de un tipo se almacenarán en un formato idéntico en la memoria, un campo solo puede alias a 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. Luego tenemos la propiedad útil, dadas las ubicaciones de memoria y con clases de alias, que si luego may-alias , y si entonces las ubicaciones de memoria no tendrán alias.
Análisis de alias basado en flujo
El análisis basado en el flujo, se puede aplicar a programas en un lenguaje con referencias o tipografía. El análisis basado en flujo se puede utilizar en lugar de o para complementar el análisis basado en tipo. 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 ha 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 sola clase de alias.
Ver 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: 106-117. doi : 10.1145 / 277650.277670 . ISBN 978-0-89791-987-6.
- Appel, Andrew W. (1998). Implementación del compilador moderno en ML . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-60764-7.
enlaces externos
- Taxonomía y aplicaciones del análisis de alias - Trabajo Fin de Máster de introducción al campo.