Browse Prior Art Database

APPLICATION OF THE USE-DEFINITION CHAINING TO ATTRIBUTE-FLOW ANALYSIS

IP.com Disclosure Number: IPCOM000128175D
Original Publication Date: 1980-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 33 page(s) / 76K

Publishing Venue

Software Patent Institute

Related People

Micha Shari_: AUTHOR [+3]

Abstract

1 2. Terminology and Notation

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

Page 1 of 33

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

APPLICATION OF THE USE-DEFINITION CHAINING TO ATTRIBUTE- FLOW ANALYSIS

" by Micha Shari_

, January 1980

REPORT NO. 0.17 ~3 * This work is based upon work supported partly by the National Science Foundation under Grant Nos. MCS-7818922 and MCS 76-00116. 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 National Science Foundation.

This work is also based upon work supported in part by the U.S. Department of Energy Contract EY-76-C-02-3077.

Table of Contents Page

Abstract iv

1. Introduction 1 2. Terminology and Notation

3. Equivalence of the Flow Graph and 13 the ud Propagation Methods

4. Various Properties of the~ud Map 23 5. Issues .in Interprocedural ud Propagation 25 References 53 iii

ABSTRACT

Use-definition chaining is a well known pragmatic technique for solving various classes of data flow analysis problems. In this paper. we compare this method with the standard flow graph method for solving such problems and show that when applied to the class of attribute flow analysis problems (which includes constant propagation, type analysis, etc.) both methods yield tile same solution, but that the u.se definition method is generally much more efficient than the flow graph method. We also describe and analyze a possible adaptation of the use-definition technique to inter-procedural attribute flow analysis.

Use-definition chaining is a well known pragmatic technique for solving various classes of data flow analysis problems. In this paper. we compare this method with the standard flow graph method for solving such problems and show that when applied to the class of attribute flow analysis problems (which includes constant propagation, type analysis, etc.) both methods yield tile same solution, but that the u.se definition method is generally much more efficient than the flow graph method. We also describe and analyze a possible adaptation of the use-definition technique to inter-procedural attribute flow analysis. iv

1. Introduction

New York University Page 1 Dec 31, 1980

Page 2 of 33

APPLICATION OF THE USE-DEFINITION CHAINING TO ATTRIBUTE-FLOW ANALYSIS

Data floes analysis of computer programs has become a key tool for program analysis and optimization. However, a significant portion of the extensive literature on this subject concerns itself with abstract theory and methods, and the issue of practical implementation of these abstract methods does not always receive adequate treatment. As the role of code optimization tends to become more central in compiler design and implementation (especially in the development of progressively higher level programming languages), more thought will need to be given to the efficiency of existing data flow algorithms and methods. This paper aims to narrow the gap between theory and practice by providing a theoretical study of th...