On 3/13/12 10:47 AM, deadalnix wrote:
This problem is pretty close to garbage collection. Let's use pure as
example, but it work with other qualifier too.
function are marked pure, impure, or pure given all function called are
pure (possibly pure). Then you go throw all possibly pure function and
if it call an impure function, they mark it impure. When you don't mark
any function as impure on a loop, you can mark all remaining possibly
pure functions as pure.
Certain analyses can be done using the so-called worklist approach. The
analysis can be pessimistic (initially marking all functions as not
carrying the property analyzed and gradually proving some do carry it)
or optimistic (the other way around). The algorithm ends when the
worklist is empty. This approach is well-studied and probably ought more
coverage in compiler books. I learned about it in a graduate compiler class.
However, the discussion was about availability of the body. A
worklist-based approach would need all functions that call one another
regardless of module. That makes the analysis interprocedural, i.e.
difficult on large codebases.
Andrei
