| Description |
In order to perform global code optimizations, the compiler needs to gather information about a program. It may want to know whether a value computed will be used later during the execution of the program (Live Variables Analysis) or whether during the execution, the result of an expression computation can be reused at several places (Available Expressions Analysis). Data flow analysis is an abstraction of these and several other similar analyses. This information can be gathered by computing the Meet Over all Paths (MOP) solution for Data Flow Analysis. However, if the underlying semilattice is infinite, computing the MOP solution is undecidable. So as a safe approximation, we settle with the Maximum Fixed Point (MFP) solution which is polynomial time computable for semilattices of finite height.
In this talk, we consider Data Flow Analysis over monotone data flow frameworks with a finite bounded meet-semilattice. We show that the problem of computing the MFP solution is P-complete. This shows that the problem can not have efficient parallel algorithms unless P = NC. We will also show that the problem of computing the MOP solution is NL-complete (and hence efficiently parallelizable) when the semilattice is finite. These results appear in contrast with the fact that computing the MOP solution is significantly harder than the MFP solution in general.
|