Simplifying Control Flow in Compiler-Generated Parallel Code

John Mellor-Crummey, Vikram Adve

Research output: Contribution to journalArticlepeer-review

Abstract

Optimizing compilers for data-parallel languages such as High Performance Fortran perform a complex sequence of transformations. However, the effects of many transformations are not independent, which makes it challenging to generate high quality code. In particular, some transformations introduce conditional control flow, while others make some conditionals unnecessary by refining program context. Eliminating unnecessary conditional control flow during compilation can reduce code size and remove a source of overhead in the generated code. This paper describes algorithms to compute symbolic constraints on the values of expressions used in control predicates and to use these constraints to identify and remove unnecessary conditional control flow. These algorithms have been implemented in the Rice dHPF compiler and we show that these algorithms are effective in reducing the number of conditionals and the overall size of generated code. Finally, we describe a synergy between control flow simplification and data-parallel code generation based on loop splitting which achieves the effects of more narrow data-parallel compiler optimizations such as vector message pipelining and the use of overlap areas.

Original languageEnglish (US)
Pages (from-to)613-638
Number of pages26
JournalInternational Journal of Parallel Programming
Volume26
Issue number5
DOIs
StatePublished - 1998
Externally publishedYes

Keywords

  • Constraint propagation
  • Expression range analysis

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Fingerprint

Dive into the research topics of 'Simplifying Control Flow in Compiler-Generated Parallel Code'. Together they form a unique fingerprint.

Cite this