Parallel pointer analysis for large-scale software

Abstract

Pointer analysis, a process that statically computes the possible runtime values of a pointer in a program, enables the understanding of program behaviours. It lies in the heart of software engineering and has laid foundations for extensive applications, such as compiler optimisation, software bug detection and program verification. The long existing challenge of the analysis, however, is to improve its efficiency while maintaining high precision, especially when applied to large programs. Parallel platforms, which are prevalent nowadays, provide a great opportunity to enhance the efficiency of pointer analysis. Yet, it is challenging to parallelise this analysis, which is essentially an irregular graph algorithm. In general, pointer analysis comes in two styles: whole-program and demand-driven. Whole-program analysis, which computes the points-to information of all variables in a program, is often formulated as a graph-rewriting problem that makes extensive modifications to data structures representing the graph. Demand-driven analysis, which only targets the variables requested by queries, is solved in terms of a graph traversal problem. This thesis presents the design and implementation of a parallel pointer analysis framework that enables efficient pointer analysis for large-scale software. This framework consists of three parts, each targeting one of today’s most popular parallel platforms, and is implemented with a combination of Java, C++ and CUDA. The first part is a parallel solution to pointer analysis driven by queries, on multi-core CPUs. It has achieved significant speedups over the sequential solution, since a large amount of unnecessary graph traversals have been eliminated by information sharing and query scheduling. The second part is an efficient GPU solution to whole-program pointer analysis. With effective load balancing and reduced redundant computation, it demonstrates considerable speedups over the state-of-the-art GPU implementation. The third part is a heterogeneous CPU-GPU solution to whole-program pointer analysis. It prioritises the distribution of different work-loads to CPU/GPU according to the processing unit’s ability for processing them, and therefore has achieved speedups over the corresponding CPU-only and GPU-only solutions. The effectiveness of each part of the framework is demonstrated via an evaluation with a set of open-source Java/C programs.