8
$\begingroup$

Data flow analysis work over a control flow graph. When a language under consideration supports exceptions, control flow graph can explode.

What are the standard techniques for dealing with this blow-up? Can we soundly disregard edges induced by exception? Data flow analyses anyhow compute over-approximations, so we would end up with a less precise but sound solution. Is this true?

Update: Here are few useful links that I was able to dig out at the end:

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "explode"? Do we statically know which exceptions can be thrown where? Which kind of size increase would you be willing to accept? $\endgroup$
    – Raphael
    Commented Jun 20, 2016 at 18:54
  • 1
    $\begingroup$ By explode I mean that the number of basic blocks is increased and the number of edges connecting them, resulting in potentially higher analysis execution times. My assumption, perhaps wrong, was that this might be a problem in compilers and there are maybe some way of dealing with it. I am interested in understanding the subject. $\endgroup$
    – zpavlinovic
    Commented Jun 20, 2016 at 19:02

1 Answer 1

Reset to default
10
$\begingroup$

Ignoring exceptions is unsound. Example:

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

When analyzing f, you need to take into account the fact that g raises an exception, otherwise you would incorrectly conclude that x is always 0 on return from f.

I don't know that there is a “standard” technique for dealing with exceptions. There's some literature on the topic, I don't have any more idea of what papers are relevant than I can find by a Google search.

Formally, exceptions can be turned into conditional statements that propagate up the call chain, which of course blows up the control flow graph. In many concrete cases, the exception case is the less interesting case, where a lot of data gets killed, so it should be handled lazily in a forward approach (no need to analyze the liveness on the exception path if the handler kills the data).

Improve this answer
$\endgroup$
6
  • $\begingroup$ A follow up question, if you don't mind. Essentially, if I am missing some edges, I can get an unsound result. What if I have edges encoding control flow that is in fact not exhibited during program execution? Would I have a sound result, but potentially less precise one? $\endgroup$
    – zpavlinovic
    Commented Jun 20, 2016 at 20:13
  • 1
    $\begingroup$ @bellpeace If an edge corresponds to a path that is never taken during execution, it's dead code, so it can be removed without affecting soundness. The result would be more precise: you have a better approximation of the program, so you can get a better approximation of its behavior. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jun 20, 2016 at 20:51
  • $\begingroup$ So, essentially, adding additional edges will not affect soundness but only precision? $\endgroup$
    – zpavlinovic
    Commented Jun 20, 2016 at 21:01
  • 1
    $\begingroup$ @bellpeace Yes: if you add potential paths, you might introduce new potential flows that can't actually happen, but you won't erase any flows that do happen. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jun 20, 2016 at 21:20
  • $\begingroup$ Hang on, in this example, x is always zero on return from f. If g raises an exception, f doesn't return. Now if f caught the exception (and perhaps rethrew), that would be a different matter, but that would be an explicit edge in the flow graph. $\endgroup$
    – Pseudonym ♦
    Commented Jun 22, 2016 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.