Browse Prior Art Database

Data Flow Analysis for Records and Pointers to Records

IP.com Disclosure Number: IPCOM000128620D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 7 page(s) / 23K

Publishing Venue

Software Patent Institute

Related People

James R. Low: AUTHOR [+3]

Abstract

Significant improvements in the performance of programs are possible when an optimizer can determine the range of values and uses of the various fields within records. Some of the optimizations include: not allocating space for unread fields of records; removal of assignments tc unread fields; allocating less space for a field if the range of possible values is small; and, in general, taking advantage of properties of the values taken on by the fields of records in traditional optimizations :such as redundant test removal and constant propagation. One cut at the problem would be to do standard ra age-anal ysis on a record class (all records with the same declaration template). basis.. a better technique involves recognizing that a record class is often an overly general concept. He would get, much stronger information if we could analyze each record which is allocated within the program. However, this is not possible, as even the number of individual records of a program may depend on ingot data and cannot ;in general) be determined from a static compile time analysis. The compromise we suggest is to construct a finite set of equivalence classes on records. , Each equivalence class represents an indefinite number of records o` the same r=cord class. 1! record class is thus represented by one or more equivalence classes. Any particular instance (runtime) Page 2 of a record will be a member of a single equivalence class. An appropriate partition into equivalence classes is to make an equivalence class of ail records allocated at as individual source statement in the original program (or original program With one or more procedures expanded in-line). This rill give us a finite number of equivalence classes.

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

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Data Flow Analysis for Records and Pointers to Records

James R. Low Computer Science Department University of Rochester

TR35

May 1979 This research was supported in part: by the National Science Foundation under Grant No. MCS76-10825. Data Flow Analysis for Records and Pointers to Records

Summary,

I. Introduction

Significant improvements in the performance of programs are possible when an optimizer can determine the range of values and uses of the various fields within records. Some of the optimizations include: not allocating space for unread fields of records; removal of assignments tc unread fields; allocating less space for a field if the range of possible values is small; and, in general, taking advantage of properties of the values taken on by the fields of records in traditional optimizations :such as redundant test removal and constant propagation.

One cut at the problem would be to do standard ra age-anal ysis on a record class (all records with the same declaration template). basis.. a better technique involves recognizing that a record class is often an overly general concept. He would get, much stronger information if we could analyze each record which is allocated within the program. However, this is not possible, as even the number of individual records of a program may depend on ingot data and cannot ;in general) be determined from a static compile time analysis. The compromise we suggest is to construct a finite set of equivalence classes on records. , Each equivalence class represents an indefinite number of records o` the same r=cord class. 1! record class is thus represented by one or more equivalence classes. Any particular instance (runtime) Page 2

of a record will be a member of a single equivalence class.

An appropriate partition into equivalence classes is to make an equivalence class of ail records allocated at as individual source statement in the original program (or original program With one or more procedures expanded in-line). This rill give us a finite number of equivalence classes.

The first stage of flow analysis is to determine the possible contents of the pointer variables (which equivalence classes they might refer to) at the various statements of the program.

II. Data Flow Equations

There are four basic assignment statements involving pointer variables. All others may be decomposed into these with (if nECessar7) the addition of taaporary variables.

(Equation Omitted)

Columbia University Page 1 Dec 31, 1979

Page 2 of 7

Data Flow Analysis for Records and Pointers to Records

The possible set of values (record equivalence cusses) for variable X on entry to node k will be denoted:

(Equation Omitted)

Page 3

The possible sets of values of variable X on exit from node k will be written: -

(Equation Omitted)

The set of possible values for any pointer variable will be a subset of

(Equation Omitted)

where the Ai correspond to nodes containing...