current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 7 down vote favorite
3

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?

share|cite|improve this question
    
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? – Raphael♦ 11 hours ago
1  
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. – bellpeace 11 hours ago
up vote 9 down vote

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).

share|cite|improve this answer
    
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? – bellpeace 10 hours ago
1  
@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. – Gilles♦ 9 hours ago
    
So, essentially, adding additional edges will not affect soundness but only precision? – bellpeace 9 hours ago
1  
@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. – Gilles♦ 9 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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