I have been learning about data-flow analysis and have come across the idea of approximations and that the data-flow analysis should be able to under and over approximate a situation. For example, when using available expressions, we under under-approximate if we aren't sure if we can do something by not doing it. I just don't really understand; surely if analysis wasn't sure if it could do something or not, the algorithm would just not report this as a possible available expression?

What does approximation and decidability (which I think is also related) mean in terms of data-flow analysis?


1 Answer 1


All of the problems we want to solve with static analysis are undecidable. We have a yes-or-no question ("will this expression be available?", "is this variable live?", etc.). Ideally we'd like an algorithm that takes as input the program, terminates in a finite amount of time, and outputs the correct answer to the question. Unfortunately, the problem is undecidable, so there is no such algorithm.

But we're not willing to give up. So, we accept algorithms that always terminate but sometimes output "I'm not sure". There are basically two kinds of such algorithm. One can will either output "Definitely yes" or "I'm not sure (might be yes, might be no)". The other kind will either output "Definitely no" or "I'm not sure (might be yes, might be no)".

Underapproximation vs overapproximation just refers to the difference between those two kinds of algorithms.

How do you pick one or the other? That depends on what you're ultimately trying to achieve. In some situations, it's more useful to know that the answer is "definitely yes". In others, it's more useful to know that the answer is "definitely no".

Of course, these two notions can be combined, so you can get an algorithm that will output either "Definitely yes", "Definitely no", or "I'm not sure (might be yes, might be no)". But you can't avoid the possibility of an "I'm not sure" answer; that's an unavoidable consequence of undecidability.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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