Basic compiler algorithms for parallel programs

Jaejin Lee, David A. Padua, Samuel P. Midkiff

Research output: Contribution to journalArticlepeer-review


Traditional compiler techniques developed for sequential programs do not guarantee the correctness (sequential consistency) of compiler transformations when applied to parallel programs. This is because traditional compilers for sequential programs do not account for the updates to a shared variable by different threads. We present a concurrent static single assignment (CSSA) form for parallel programs containing cobegin/coend and parallel do constructs and post/wait synchronization primitives. Based on the CSSA form, we present copy propagation and dead code elimination techniques. Also, a global value numbering technique that detects equivalent variables in parallel programs is presented. By using global value numbering and the CSSA form, we extend classical common subexpression elimination, redundant load/store elimination, and loop invariant detection to parallel programs without violating sequential consistency. These optimization techniques are the most commonly used techniques for sequential programs. By extending these techniques to parallel programs, we can guarantee the correctness of the optimized program and maintain single processor performance in a multiprocessor environment.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalSIGPLAN Notices (ACM Special Interest Group on Programming Languages)
Issue number8
StatePublished - Aug 1999

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Basic compiler algorithms for parallel programs'. Together they form a unique fingerprint.

Cite this