Análisis de flujo de datos con excepciones

8

El análisis de flujo de datos funciona sobre un gráfico de flujo de control. Cuando un idioma considerado admite excepciones, el gráfico de flujo de control puede explotar.

¿Cuáles son las técnicas estándar para lidiar con esta explosión? ¿Podemos ignorar los bordes inducidos por la excepción? Los análisis de flujo de datos de todos modos calculan sobre-aproximaciones, por lo que terminaríamos con una solución menos precisa pero sólida. ¿Es esto cierto?

Actualización : Aquí hay algunos enlaces útiles que pude desenterrar al final:

Bellpeace
fuente
¿Qué quieres decir con "explotar"? ¿Sabemos estáticamente qué excepciones se pueden lanzar a dónde? ¿Qué tipo de aumento de tamaño estaría dispuesto a aceptar?
Raphael
1
Por explotar quiero decir que el número de bloques básicos aumenta y el número de bordes que los conectan, lo que resulta en tiempos de ejecución de análisis potencialmente más altos. Mi suposición, tal vez errónea, fue que esto podría ser un problema en los compiladores y tal vez haya alguna forma de tratarlo. Estoy interesado en entender el tema.
bellpeace

Respuestas:

10

Ignorar las excepciones es poco sólido. Ejemplo:

let g = {
     raise E;
}
let f = {
     x := interesting_stuff();
     g();
     x := 0;
}

Al analizar f, debe tener en cuenta el hecho de que ggenera una excepción, de lo contrario, concluiría incorrectamente que xsiempre es 0 al regresar de f.

No sé si existe una técnica "estándar" para hacer frente a las excepciones. Hay algo de literatura sobre el tema, no tengo más idea de qué documentos son relevantes de lo que puedo encontrar en una búsqueda en Google.

Formalmente, las excepciones pueden convertirse en declaraciones condicionales que se propagan por la cadena de llamadas, lo que, por supuesto, explota el gráfico de flujo de control. En muchos casos concretos, el caso de excepción es el caso menos interesante, donde se matan muchos datos, por lo que debe manejarse perezosamente en un enfoque directo (no es necesario analizar la vida en la ruta de excepción si el controlador mata los datos) .

Gilles 'SO- deja de ser malvado'
fuente
Una pregunta de seguimiento, si no le importa. Esencialmente, si me faltan algunos bordes, puedo obtener un resultado poco sólido. ¿Qué sucede si tengo un flujo de control de codificación de bordes que de hecho no se exhibe durante la ejecución del programa? ¿Tendría un resultado sólido, pero potencialmente menos preciso?
bellpeace
1
@bellpeace Si un borde corresponde a una ruta que nunca se toma durante la ejecución, es un código muerto, por lo que puede eliminarse sin afectar la solidez. El resultado sería más preciso: tiene una mejor aproximación del programa, por lo que puede obtener una mejor aproximación de su comportamiento.
Gilles 'SO- deja de ser malvado'
Entonces, esencialmente, ¿agregar bordes adicionales no afectará la solidez sino solo la precisión?
bellpeace
1
@bellpeace Sí: si agrega rutas potenciales, puede introducir nuevos flujos potenciales que en realidad no pueden suceder, pero no borrará ningún flujo que suceda.
Gilles 'SO- deja de ser malvado'
Espera, en este ejemplo, x siempre es cero al regresar de f. Si g plantea una excepción, f no regresa. Ahora, si f captó la excepción (y quizás la volvió a lanzar), eso sería un asunto diferente, pero eso sería una ventaja explícita en el diagrama de flujo.
Seudónimo