Data flow analysis is a most important phase of any programming language compiler. I am investigating data flow analysis with a view to whole-program optimisation (see my research page for details). However, there is lots of jargon associated with data flow analysis. I have attempted to collect together some of the most important terms, and their meanings.
alias analysis determines storage locations that may be accessed in more than one way. Alias analysis computes pairs of expressions that may be aliased (i.e. may point to the same memory location).
may-alias information indicates what may occur on some path through the flow graph
must-alias information indicates what must occur on all paths through the flow graph
flow-insensitive information is independent of the control flow encountered. The program is considered as a set of statements. Information given simply indicates that a particular fact may hold anywhere in the program because it does hold somewhere in the program. Flow-insensitive information is fast to compute, but not very precise.
flow-sensitive information depends on control flow. The program is considered as a sequence of statements. Information given indicates that a particular fact is true at a certain point in the program. Flow-sensitive analysis usually provides more precise information that flow-insensitive analysis, but it is also usually considerably more expensive in terms of computational time and space.
points-to analysis computes a store model using abstract locations
unification-based points-to analysis treats pointers as either unaliased or pointing to the same set of locations. (Steensgard's flow-insensitive points-to analysis is unification-based.)
inclusion-based points-to analysis two aliased pointers may point to overlapping but different sets of locations. This is usually more precise than unification-based analysis, although usually more expensive too. (Andersen's flow-insensitive points-to analysis is inclusion-based.)
strong/weak updates are part of points-to analysis---trying to build an abstract model of the memory layout. Update means assigning an expression to a memory location through a pointer. In strong update, the reference that has been changed must point to a new set of locations rather than the old. In weak update, the reference that has been changed points to the new set of locations in addition to the old. Strong updates are better, since they provide more information. It is always correct to perform a weak update. (It is not always correct to perform a strong update.)
context-sensitive analysis takes into account the fact that a function must return to the site of its most recent call. (So we can acquire specific information for each invocation of the function.)
context-insensitive analysis propagates information from a call site through the called function and back to all call sites.