Region-based compilation: Introduction, motivation, and initial experience

Richard E. Hank, Wen-Mei W Hwu, B. Ramakrishna Rau

Research output: Contribution to journalArticle

Abstract

The most important task of a compiler designed to exploit instruction-level parallelism (ILP) is instruction scheduling. If higher levels of ILP are to be achieved. the compiler must use, as the unit of scheduling, regions consisting of multiple basic blocks - preferably those that frequently execute consecutively, and which capture cycles in the program's execution. Traditionally, compilers have been built using the function as the unit of compilation. In this framework, function boundaries often act as barriers to the formation of the most suitable scheduling regions. Function inlining may be used to circumvent this problem by assembling strongly coupled functions into the same compilation unit, but at the cost of very large function bodies. Consequently, global optimizations whose compile time and space requirements are superlinear in the size of the compilation unit, may be rendered prohibitively expensive. This paper introduces a new approach, called region-based compilation, wherein the compiler, after inlining, repartitions the program into more desirable compilation units, termed regions. Region-based compilation allows the compiler to control problem size and complexity while exposing inter-procedural scheduling, optimization and code motion opportunities.

Original languageEnglish (US)
Pages (from-to)113-146
Number of pages34
JournalInternational Journal of Parallel Programming
Volume25
Issue number2
DOIs
StatePublished - Jan 1 1997

Fingerprint

Compilation
Compiler
Scheduling
Unit
Instruction Level Parallelism
Instruction Scheduling
Global optimization
Global Optimization
Experience
Control Problem
Cycle
Motion
Optimization
Requirements

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Information Systems

Cite this

Region-based compilation : Introduction, motivation, and initial experience. / Hank, Richard E.; Hwu, Wen-Mei W; Rau, B. Ramakrishna.

In: International Journal of Parallel Programming, Vol. 25, No. 2, 01.01.1997, p. 113-146.

Research output: Contribution to journalArticle

@article{ab384f81786a4339a6adc97c59071a5c,
title = "Region-based compilation: Introduction, motivation, and initial experience",
abstract = "The most important task of a compiler designed to exploit instruction-level parallelism (ILP) is instruction scheduling. If higher levels of ILP are to be achieved. the compiler must use, as the unit of scheduling, regions consisting of multiple basic blocks - preferably those that frequently execute consecutively, and which capture cycles in the program's execution. Traditionally, compilers have been built using the function as the unit of compilation. In this framework, function boundaries often act as barriers to the formation of the most suitable scheduling regions. Function inlining may be used to circumvent this problem by assembling strongly coupled functions into the same compilation unit, but at the cost of very large function bodies. Consequently, global optimizations whose compile time and space requirements are superlinear in the size of the compilation unit, may be rendered prohibitively expensive. This paper introduces a new approach, called region-based compilation, wherein the compiler, after inlining, repartitions the program into more desirable compilation units, termed regions. Region-based compilation allows the compiler to control problem size and complexity while exposing inter-procedural scheduling, optimization and code motion opportunities.",
author = "Hank, {Richard E.} and Hwu, {Wen-Mei W} and Rau, {B. Ramakrishna}",
year = "1997",
month = "1",
day = "1",
doi = "10.1007/BF02700049",
language = "English (US)",
volume = "25",
pages = "113--146",
journal = "International Journal of Parallel Programming",
issn = "0885-7458",
publisher = "Springer New York",
number = "2",

}

TY - JOUR

T1 - Region-based compilation

T2 - Introduction, motivation, and initial experience

AU - Hank, Richard E.

AU - Hwu, Wen-Mei W

AU - Rau, B. Ramakrishna

PY - 1997/1/1

Y1 - 1997/1/1

N2 - The most important task of a compiler designed to exploit instruction-level parallelism (ILP) is instruction scheduling. If higher levels of ILP are to be achieved. the compiler must use, as the unit of scheduling, regions consisting of multiple basic blocks - preferably those that frequently execute consecutively, and which capture cycles in the program's execution. Traditionally, compilers have been built using the function as the unit of compilation. In this framework, function boundaries often act as barriers to the formation of the most suitable scheduling regions. Function inlining may be used to circumvent this problem by assembling strongly coupled functions into the same compilation unit, but at the cost of very large function bodies. Consequently, global optimizations whose compile time and space requirements are superlinear in the size of the compilation unit, may be rendered prohibitively expensive. This paper introduces a new approach, called region-based compilation, wherein the compiler, after inlining, repartitions the program into more desirable compilation units, termed regions. Region-based compilation allows the compiler to control problem size and complexity while exposing inter-procedural scheduling, optimization and code motion opportunities.

AB - The most important task of a compiler designed to exploit instruction-level parallelism (ILP) is instruction scheduling. If higher levels of ILP are to be achieved. the compiler must use, as the unit of scheduling, regions consisting of multiple basic blocks - preferably those that frequently execute consecutively, and which capture cycles in the program's execution. Traditionally, compilers have been built using the function as the unit of compilation. In this framework, function boundaries often act as barriers to the formation of the most suitable scheduling regions. Function inlining may be used to circumvent this problem by assembling strongly coupled functions into the same compilation unit, but at the cost of very large function bodies. Consequently, global optimizations whose compile time and space requirements are superlinear in the size of the compilation unit, may be rendered prohibitively expensive. This paper introduces a new approach, called region-based compilation, wherein the compiler, after inlining, repartitions the program into more desirable compilation units, termed regions. Region-based compilation allows the compiler to control problem size and complexity while exposing inter-procedural scheduling, optimization and code motion opportunities.

UR - http://www.scopus.com/inward/record.url?scp=0031121734&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031121734&partnerID=8YFLogxK

U2 - 10.1007/BF02700049

DO - 10.1007/BF02700049

M3 - Article

AN - SCOPUS:0031121734

VL - 25

SP - 113

EP - 146

JO - International Journal of Parallel Programming

JF - International Journal of Parallel Programming

SN - 0885-7458

IS - 2

ER -