Compiler-Based Multiple Instruction Retry

Chung Chi Jim Li, Shyh Kwei Chen, W. Kent Fuchs, Wen-Mei W Hwu

Research output: Contribution to journalArticle

Abstract

This paper describes a compiler-based approach to providing multiple instruction rollback capability for general purpose processor registers. The objective is achieved by having the compiler remove all forms of A -instruction antidependencies. Pseudoregister antidependencies are removed by loop protection, node splitting, and loop expansion techniques; machine register antidependencies are prevented by introducing antidependency constraints in the interference graph used by the register allocator. To support separate compilation, inter-procedural antidependency constraints are added to the code generator to guarantee the termination of machine register antidependencies across procedure boundaries. The algorithms have been implemented in the IMPACT C compiler. Experiments illustrating the effectiveness of this approach are described.

Original languageEnglish (US)
Pages (from-to)35-46
Number of pages12
JournalIEEE Transactions on Computers
Volume44
Issue number1
DOIs
StatePublished - Jan 1995

Fingerprint

Compiler
Experiments
Compilation
Termination
Interference
Generator
Graph in graph theory
Vertex of a graph
Experiment
Form

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

Compiler-Based Multiple Instruction Retry. / Li, Chung Chi Jim; Chen, Shyh Kwei; Fuchs, W. Kent; Hwu, Wen-Mei W.

In: IEEE Transactions on Computers, Vol. 44, No. 1, 01.1995, p. 35-46.

Research output: Contribution to journalArticle

Li, Chung Chi Jim ; Chen, Shyh Kwei ; Fuchs, W. Kent ; Hwu, Wen-Mei W. / Compiler-Based Multiple Instruction Retry. In: IEEE Transactions on Computers. 1995 ; Vol. 44, No. 1. pp. 35-46.
@article{3fa744b5039f4c5e8e6f7c1b0ca03308,
title = "Compiler-Based Multiple Instruction Retry",
abstract = "This paper describes a compiler-based approach to providing multiple instruction rollback capability for general purpose processor registers. The objective is achieved by having the compiler remove all forms of A -instruction antidependencies. Pseudoregister antidependencies are removed by loop protection, node splitting, and loop expansion techniques; machine register antidependencies are prevented by introducing antidependency constraints in the interference graph used by the register allocator. To support separate compilation, inter-procedural antidependency constraints are added to the code generator to guarantee the termination of machine register antidependencies across procedure boundaries. The algorithms have been implemented in the IMPACT C compiler. Experiments illustrating the effectiveness of this approach are described.",
author = "Li, {Chung Chi Jim} and Chen, {Shyh Kwei} and Fuchs, {W. Kent} and Hwu, {Wen-Mei W}",
year = "1995",
month = "1",
doi = "10.1109/12.368011",
language = "English (US)",
volume = "44",
pages = "35--46",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "1",

}

TY - JOUR

T1 - Compiler-Based Multiple Instruction Retry

AU - Li, Chung Chi Jim

AU - Chen, Shyh Kwei

AU - Fuchs, W. Kent

AU - Hwu, Wen-Mei W

PY - 1995/1

Y1 - 1995/1

N2 - This paper describes a compiler-based approach to providing multiple instruction rollback capability for general purpose processor registers. The objective is achieved by having the compiler remove all forms of A -instruction antidependencies. Pseudoregister antidependencies are removed by loop protection, node splitting, and loop expansion techniques; machine register antidependencies are prevented by introducing antidependency constraints in the interference graph used by the register allocator. To support separate compilation, inter-procedural antidependency constraints are added to the code generator to guarantee the termination of machine register antidependencies across procedure boundaries. The algorithms have been implemented in the IMPACT C compiler. Experiments illustrating the effectiveness of this approach are described.

AB - This paper describes a compiler-based approach to providing multiple instruction rollback capability for general purpose processor registers. The objective is achieved by having the compiler remove all forms of A -instruction antidependencies. Pseudoregister antidependencies are removed by loop protection, node splitting, and loop expansion techniques; machine register antidependencies are prevented by introducing antidependency constraints in the interference graph used by the register allocator. To support separate compilation, inter-procedural antidependency constraints are added to the code generator to guarantee the termination of machine register antidependencies across procedure boundaries. The algorithms have been implemented in the IMPACT C compiler. Experiments illustrating the effectiveness of this approach are described.

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

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

U2 - 10.1109/12.368011

DO - 10.1109/12.368011

M3 - Article

AN - SCOPUS:0029208695

VL - 44

SP - 35

EP - 46

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 1

ER -