Re: Abstract Interpretation vs DFA in Clang and GCC

Jack Smith <ilikequoting@katamail.com> writes:


> since someone says that nowadays it's better abstract interpretation
> than DFA can anyone tell me what's the difference among them?


Abstract interpretation (AI) has a strong tie to the semantics of the
language: Each value in AI corresponds to a set of values in the
semantics, which makes it relatively easy to prove the correctness of
an anlysis. Values in data-flow analysis (DFA) do not have such a
clear relation to the semantics, so they are more difficult to prove
correct. On the other hand, DFA can do analyses that are difficult to
express as AI, such as liveness. To do liveness analysis with AI you
need a continuation-passing semantics.


A more precise relation between the two can be found in the following
papers:


Schmidt, D.A. Data-flow analysis is model checking of abstract
interpretations. Proc. 25th ACM Symp. Principles of Programming
Languages, San Diego, 1998.
http://people.cis.ksu.edu/~schmidt/papers/dfa.ps.gz


Schmidt, D.A. and Steffen, B. Data-flow analysis as model checking of
abstract interpretations. Proc. 5th Static Analysis Symposium,
G. Levi. ed., Pisa, September, 1998. Springer LNCS 1503.
http://people.cis.ksu.edu/~schmidt/papers/paperneu9.ps.gz


Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.