Can We Make It Faster? Efficient May-Happen-in-Parallel Analysis Revisited

May-Happen-in-Parallel (MHP) analysis is a very important and fundamental mechanism to facilitate concurrent program analysis, optimization and even concurrency bug detection. However, the inefficiency in its design and implementation keeps MHP analysis away from being practical and effective. In this paper, we investigate the state-of-art of iterative data flow based (IDFB) MHP analysis and propose a new design and corresponding systematic implementation. Specifically, we address the most severe efficiency problems in node process order of the work-list in the original approach, and resolve them in our design and implementation by using the concept of parallel level to avoid redundant node visits. Our intensive experimental study shows that the proposed design and implementation have a relative speed up of 29.02x compared with the original implementation, moreover, it achieves a relative speed up of 10.00x comparing to the state-of-art of non-IDFB approach which is claimed to be more efficient than the original IDFB approach. Our design and implementation are capable of achieving an order of magnitude efficiency improvement comparing to both IDFB and non-IDFB approaches.