Refining the parallel hybrid algorithm for data flow analysis

Data flow analysis is a compile-time analysis technique that gathers information about definitions and uses of variables in a program. That information is regarded as essential in optimizing and parallel compilers, and various other software understanding tools. Gathering data flow information can be performed at different levels of precision, with the most precise levels being very computationally expensive. The result is that modern tools do not perform analysis or perform it in a very approximate way. During the past few years, massively parallel machines have become the supercomputer successors, and multiprocessor boxes are getting ever more common and inexpensive, even as single-user workstations. Aggressive program understanding tools and optimizations will be made practical as soon as parallel data flow analysis algorithms become available and start being used to gather more precise data flow information than it has been profitable to obtain before. Yong-fong Lee has already worked extensively on the topic, and he implemented and profiled the performance of a parallel algorithm for data flow analysis. The algorithm was shown to be applicable for many, but not all of the program instances with which it was tested. As a continuing effort, this thesis concentrates on the development of the necessary changes to the former algorithm in order to make it effective for all tested problem instances. The result is a new algorithm that exploits the strengths of the former algorithm and corrects its weaknesses. As this thesis shows, the modifications lead to the development of two main algorithms that modify both the partitioning and the solution phases of the abovementioned algorithm. In order to validate the previous ideas, all the components in the new design have been implemented and extensively tested on a CM-5 machine to prove their applicability and effectiveness. The necessary steps to make implementations efficient are also covered, including some alternatives whose applicability may be platform dependent thus requiring some empirical experimentation.Technical report lcsr-tr-26