TYPE PARTITIONED DATAFLOW ANALYSES

Type partitioned dataflow analyses perform a dataflow analysis of a program by partitioning the dataflow analysis into phases using types to help reduce costs attendant to the dataflow analysis of the entire program. Each phase models only a subset of the relevant program quantities and may be analyzed separately. Type partitioned dataflow analyses extend quantity-based partitioning to non-separable dataflow analyses by determining analysis-time dependencies connoting potential run-time interactions between relevant program quantities and scheduling the dataflow analysis of each program quantity after the dataflow analysis of all other program quantities upon which it depends. Because each phase may be analyzed separately, type partitioned dataflow analyses may enable the use of suitable efficient dataflow techniques, such as suitable sparse representation methods for example, that otherwise could not have been used for an entire non-separable program and may also enable the performance of dataflow analyses in parallel for more than one separate phase of such a non-separable program.