TY - JOUR
T1 - A Constant Propagation Algorithm for Explicitly Parallel Programs
AU - Lee, Jaejin
AU - Midkiff, Samuel P.
AU - Padua, David A.
N1 - Funding Information:
1This work is supported in part by Army contract DABT63-95-C-0097; Army contract N66001-97-C-8532; NSF contract ASC-96-12099; and a Partnership Award from IBM. Jaejin Lee’s work is partially supported by an IBM cooperative fellowship. This work is not necessarily representative of the positions or policies of the Army, Government, or IBM Corp. This paper is an extended version of the article by Lee et al.(1). 2Department of Computer Science, University of Illinois, Urbana, Illinois 61801. E-mail: {j-lee44, padua}@cs.uiuc.edu 3IBM T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, New York 10598. E-mail: [email protected].
PY - 1998
Y1 - 1998
N2 - In this paper, we present a constant propagation algorithm for explicitly parallel programs, which we call the Concurrent Sparse Conditional Constant propagation algorithm. This algorithm is an extension of the Sparse Conditional Constant propagation algorithm. Without considering the interaction between threads, classical optimizations lead to an incorrect program transformation for parallel programs. To make analyzing parallel programs possible, a new intermediate representation is needed. We introduce the Concurrent Static Single Assignment (CSSA) form to represent explicitly parallel programs with interleaving semantics and synchronization. The only parallel construct considered in this paper is cobegin/coend. A new confluence function, the π-assignment, which summarizes the information of interleaving statements between threads, is introduced. The Concurrent Control Flow Graph, which contains information about conflicting statements, control flow, and synchronization, is used as an underlying representation for the CSSA from.
AB - In this paper, we present a constant propagation algorithm for explicitly parallel programs, which we call the Concurrent Sparse Conditional Constant propagation algorithm. This algorithm is an extension of the Sparse Conditional Constant propagation algorithm. Without considering the interaction between threads, classical optimizations lead to an incorrect program transformation for parallel programs. To make analyzing parallel programs possible, a new intermediate representation is needed. We introduce the Concurrent Static Single Assignment (CSSA) form to represent explicitly parallel programs with interleaving semantics and synchronization. The only parallel construct considered in this paper is cobegin/coend. A new confluence function, the π-assignment, which summarizes the information of interleaving statements between threads, is introduced. The Concurrent Control Flow Graph, which contains information about conflicting statements, control flow, and synchronization, is used as an underlying representation for the CSSA from.
KW - Compiler optimization
KW - Constant propagation, Control flow graph: Explicit parallelism
KW - Intermediate representation
KW - Static single assignment form
UR - http://www.scopus.com/inward/record.url?scp=0032181142&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0032181142&partnerID=8YFLogxK
U2 - 10.1023/A:1018772514882
DO - 10.1023/A:1018772514882
M3 - Article
AN - SCOPUS:0032181142
SN - 0885-7458
VL - 26
SP - 563
EP - 589
JO - International Journal of Parallel Programming
JF - International Journal of Parallel Programming
IS - 5
ER -