Tata Institute of Fundamental Research
On the Computational Complexity of Data Flow Analysis Over Finite Bounded Meet-semilattices
MSc Project Seminar
Speaker:
Gaurav Sood
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 24 Jun 2014, 15:30 to 17:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: 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.
| Speaker: | Gaurav Sood |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 24 Jun 2014, 15:30 to 17:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: 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.
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.