Two in One: A case for Combined Points-to and MHP Analysis

With parallel programs becoming a mainstay, analyzing them has become an important requirement. Points-to analysis and May-Happen-in-Parallel (MHP) analysis are two of the most foundational analyses for parallel programs written in OO languages like Java. It is well known that precise MHP analysis needs points-to analysis results and precise flow-sensitive points-to analysis needs MHP analysis results. In this paper, we explore the interdependence between these analyses and propose new schemes to perform them efficiently. We start by proving that there is a phase-ordering relation between MHP analysis and flow-sensitive points-to analysis; that is, they are interdependent such that no particular order of performing the analyses can yield the precise result. Next, we propose a novel combined MHP and points-to analysis scheme (called ComPoMHP ) based on inclusion constraints, for real world parallel Java applications; this generates flow-sensitive, context-insensitive results; it even computes the required call graph information on the fly. We have implemented ComPoMHP in the Soot compiler framework and tested our analysis on thirteen benchmarks drawn from multiple sources. We show that the combined analysis leads to significant improvements in terms of precision of both MHP and points-to results, across seven different clients. We find that ComPoMHP leads to an excellent time-precision trade-off for points-to results, compared to the popular Doop based analyses. We also show that composing the points-to results of ComPoMHP with the results from existing Doop based flow-insensitive, context-sensitive analysis leads to highly precise results at affordable costs. We believe that our work paves the way for more precise and practical analysis of parallel Java programs.