A New Method of MHP Analysis for Languages with Dynamic Barriers

May-happen-in-parallel analysis is a very important analysis which enables several optimizations in parallel programs. Most of the work on MHP analysis has used forward flow analysis to compute "parallel(n)" | set of nodes which may execute in parallel to a given node "n" | including those approaches that addressed the issue for dynamic barrier languages. We propose a new approach to MHP analysis called "Phase Interval Analysis" (PIA) which computes phase intervals, corresponding to dynamic barriers, in which a statement may execute. PIA enables us to infer an order between two statements whenever it can establish that they can not execute in parallel. Because the ordering relation is transitive, we may also be able to infer indirect synchronization happening between two statements, even when they do not share a barrier. To the best of our knowledge, the issue of indirect synchronization has not been addressed prior to this work. We also compute condition functions under which different instances of the same statement may not execute in parallel, when the statements are nested within loops.