Concurrent SSA for general barrier-synchronized parallel programs

摘要

Static single assignment (SSA) form has been widely studied and used for sequential programs. This form enables many compiler optimizations to be done efficiently. Work on concurrent static single assignment form (CSSA) for concurrent programs is focused on languages that have limited, implicit barriers (e.g., cobegin/coend and parallel do). Recent programming languages for high-performance computing have general features for barrier/phase synchronization - this is essentially a dual of mutual exclusion and arises mainly in constructing synchronous systems from asynchronous systems. X10 is one such language that has features for general purpose barriers. In X10, barriers are provided through features such as clocks and finish. Since barriers provide explicit synchronization, they offer an opportunity for reducing pi interferences needed for CSSA. This paper provides a means for computing improved CSSA form of a program taking advantage of the general barriers present in it. Our algorithm is based on constructing a control-flow graph of the program and flow equations. The efficiency of analysis and optimizations for parallel programs depends on the number and complexity of pi assignments in their CSSA representations. We demonstrate that our approach of computing CSSA form for languages supporting general barrier synchronization can improve the precision of intermediate representation for computing global value numbering and loop invariant detection.