En informática , el algoritmo de Steensgaard es un algoritmo escalable e insensible al flujo para el análisis de punteros . Se utiliza a menudo en compiladores debido a su velocidad (por ejemplo, hay una implementación disponible en el marco del compilador LLVM ). [1] En su formulación original, este algoritmo no era sensible a campos, contextos ni matrices.
El algoritmo de Steensgaard se basa en restricciones de igualdad , [2] a diferencia del algoritmo de Andersen, que se basa en restricciones de subconjunto . Esto permite rastrear la información de puntos a través de una estructura de datos de unión-búsqueda . Esta elección le da al algoritmo su velocidad característica; cuando se implementa utilizando una estructura de datos de unión-búsqueda, es lineal en el espacio y casi lineal en el tiempo en el tamaño del programa de entrada.
La formulación del algoritmo de Bjarne Steensgaard se basó en la inferencia y verificación de tipos . Steensgaard propuso el análisis de puntos a un lenguaje de punteros imperativo pequeño pero genérico que captura las propiedades esenciales de otros lenguajes comunes con punteros, como C. La semántica del lenguaje y las reglas de tipado constituyen el análisis.