Browse Prior Art Database

Early Days of FORTRAN: Register Allocation in FORTRAN I

IP.com Disclosure Number: IPCOM000129429D
Original Publication Date: 1984-Jan-01
Included in the Prior Art Database: 2005-Oct-06
Document File: 3 page(s) / 19K

Publishing Venue

Software Patent Institute

Related People

RICHARD GOLDBERG: AUTHOR [+2]

Abstract

David Sayre and I became intimately acquainted with Phase 5 of the FORTRAN I compiler, the section that handled register allocation, in the late summer and early fall of 1956. Sheldon Best, the designer and implementer of Phase 5, was on loan from the Digital Computer Laboratory at MIT but returned to Cambridge that summer, leaving a debugging gap in the compiler group that we undertook to fill.

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

Page 1 of 3

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1984 by the American Federation of Information Processing Societies, Inc. Used with permission.

Early Days of FORTRAN: Register Allocation in FORTRAN I

RICHARD GOLDBERG

(Image Omitted: Author's Address: R. Goldberg, T. J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598.)

David Sayre and I became intimately acquainted with Phase 5 of the FORTRAN I compiler, the section that handled register allocation, in the late summer and early fall of 1956. Sheldon Best, the designer and implementer of Phase 5, was on loan from the Digital Computer Laboratory at MIT but returned to Cambridge that summer, leaving a debugging gap in the compiler group that we undertook to fill.

When Sayre and I took over, the initial implementation of Phase 5 and the four sections of the compiler that preceded it was essentially complete. The project was entering a period of intensive interphase debugging made possible by the fact that realistic input, beginning with the FORTRAN source program itself, was available for all phases. In this setting, Sayre and I became the official exterminators for Phase 5.

We were familiar with the general design of the phase -- the group was closely knit and everything was in the air. I do not recall any extensive discussion of the implementation with Best before he left; at that time most of such a discussion would have been lost on us, anyway. We had, or had easy access to, complete information about the input to the phase; I had programmed Phase 3 whose principal output was an intermediate-language version of the source program. Lois Mitchell Haibt, the proprietor of Phase 4, was on hand to tell us about the other input -- a graph constructed in Phase 4 that defined the "basic blocks" of the intermediate- language program and described their predecessor-successor relationship. Finally, we had a collection of manila folders, our legacy from Best (in addition to the code itself) that contained his documentation of Phase 5 and its various parts -- comments, flowcharts, table formats, etc.

With this equipment, Sayre and I descended into Phase 5. To accommodate the irregular working hours of the group, some hotel rooms in the vicinity of our office (and the machine on which the debugging was done) were rented. We closeted ourselves in one of these rooms and began to explore the contents of the manila folders and the code listings. Our method consisted of redocumenting the phase, bit by bit, as we went along. We developed our own table descriptions and constructed flowcharts that grew, scotch-tapewise, as each new piece of the terrain was brought under control.

After a while we started to use the machine. Gradually, aided by storage dumps, we reached the point of understanding the relationship of input to table entries -- and table entries to new code generated by the phase. A little later we knew enough to be able to localize and identify ...