Browse Prior Art Database

A SURVEY OF ALGORITHMS FOR REGISTER ALLOCATION IN STRAIGHT-LINE PROGRAMS

IP.com Disclosure Number: IPCOM000128475D
Original Publication Date: 1984-Feb-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 13 page(s) / 57K

Publishing Venue

Software Patent Institute

Related People

Rajlich, Vaclav: AUTHOR [+4]

Abstract

Two models of register allocation for straight-line programs are investigated in the literature: the permutation model, and the temporary- spilling model. The problem of register allocation in the permutation model is NP-complete, while in the temporary-spilling model it is polynomial. However, in practice, the polynomial solution is intractable because the degree of the polynomial is too large for practical consideration. The paper surveys the results related to the temporary-spilling model. Heuristic algorithms are also surveyed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A SURVEY OF ALGORITHMS FOR REGISTER ALLOCATION IN STRAIGHT-LINE PROGRAMS

Vaclav Rajlich and M. Dear Moshier

CRL-TR-14-84

THE UNIVERSITY OF MICHIGAN

COMPUTING RESEARCH LABORATORY1

FEBRUARY 1984

Room 1079, East Engineering Building

Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

A Survey of Algorithms for Register Allocation in Straight-Line Programs2 Vaclav Rajlich
M. Drew Moshier

Department of Computer and Communication Sciences

University of Michigan
Ann Arbor, MI 48109

Abstract

Two models of register allocation for straight-line programs are investigated in the literature: the permutation model, and the temporary- spilling model. The problem of register allocation in the permutation model is NP-complete, while in the temporary-spilling model it is polynomial. However, in practice, the polynomial solution is intractable because the degree of the polynomial is too large for practical consideration. The paper surveys the results related to the temporary-spilling model. Heuristic algorithms are also surveyed.

[ Chapter ] 1. Introduction

Register oriented architectures are the most commonly used computer architectures. Registers are special memory locations, which play a different role than the rest of the memory: access time to the registers is much shorter than to the other memory locations, hence registers improve the efficiency of programs; registers may also perform specific tasks which cannot be performed by the ordinary memory locations, like to hold the index value for index addressing, etc.

To improve the efficiency of a program, it is advantageous to assign certain information to the registers. If an operation produces a temporary result which will be reused, then both the time of

1 Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

2 This survey was partially supported by a grant from IBM Corporation.

University of Michigan Computing Research Laboratory Page 1 Feb 01, 1984

Page 2 of 13

A SURVEY OF ALGORITHMS FOR REGISTER ALLOCATION IN STRAIGHT-LINE PROGRAMS

storing and retrieving can be shortened by storing the temporary result in a register. However registers are a scarce resource; typically there are many more temporary results than available re1patera. Register allocation algorithms then select those candidates for which the over-all contribution to the efficiency of the program is the greatest.

In the literature, several algorithms are given which provide allocation of registers. The algorithms are Dually presented in the context of an idealized computer architecture and a set of constraints, under which the algorithms work. These constraints may involve whether or not we allow permutation of the instructions, whether or not we allow storing the contents of a register even if that value will be wed sometime in the future, whet...