A Constant Propagation Algorithm for Explicitly Parallel Programs

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

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)563-589
Number of pages27
JournalInternational Journal of Parallel Programming
Volume26
Issue number5
DOIs
StatePublished - Jan 1 1998

Keywords

  • Compiler optimization
  • Constant propagation, Control flow graph: Explicit parallelism
  • Intermediate representation
  • Static single assignment form

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Fingerprint Dive into the research topics of 'A Constant Propagation Algorithm for Explicitly Parallel Programs'. Together they form a unique fingerprint.

Cite this