Summary Capstone , thesis & dissertations Toward an optimizing compiler for a very high level language

Toward an optimizing compiler for a very high level language Walter E. Brown Iowa State University Follow this and additional works at: Part of the Computer Sciences Commons This Dissertation is brought to you for free and open access by the Iowa State University Capstones, Theses and Dissertations at Iowa State University Digital Repository. It has been accepted for inclusion in Retrospective Theses and Dissertations by an authorized administrator of Iowa State University Digital Repository. For more information, please contact . Recommended Citation Brown, Walter E., "Toward an optimizing compiler for a very high level language " (1979). Retrospective Theses and Dissertations. 7195. INFORMATION TO USERS This was produced from a copy of a document sent to us for microfilming. While the most advanced technological means to photograph and reproduce this document have been used, the quality is heavily dependent upon the quality of the material submitted. The following explanation of techniques is provided to help you understand markings or notations which may appear on this reproduction. 1. The sign or "target" for pages apparently lacking from the document photographed is "Missing Page(s)". If it was possible to obtain the missing page(s) or section, they are spliced into the film along with adjacent pages. This may have necessitated cutting through an image and duplicating adjacent pages to assure you of complete continuity. 2. When an image on the film is obliterated with a round black mark it is an indication that the film inspector noticed either blurred copy because of movement during exposure, or duplicate copy. Unless we meant to delete copyrighted materials that should not have been filmed, you will find a good image of the page in the adjacent frame. 3. When a map, drawing or chart, etc., is part of the material being photographed the photographer has followed a definite method in "sectioning" the material. It is customary to begin filming at the upper left hand comer of a large sheet and to continue from left to ri^t in equal sections with small overlaps. If necessary, sectioning is continued again—beginning below the first row and continuing on until complete. 4. For any illustrations that cannot be reproduced satisfactorily by xerography, photographic prints can be purchased at additional cost and tipped into your xerographic copy. Requests can be made to our Dissertations Customer Services Department. 5. Some pages in any document may have indistinct print. In all cases we have filmed the best available copy. University Microfilms International 300 N. ZEEB ROAD, ANN ARBOR. Ml 43106 18 BEDFORD ROW, LONDON WCIR 4EJ. ENGLAND BROWN, WALTER E. TOWARD AN OPTIMIZING COMPILER FOR A VERY HIGH LEVEL LANGUAGEIOWA STATE UNIVERSITY, PH.D., 1979 Universi^ MiCTOTlms IrtematiOncll SOON. ZEEB ROAD, ANN ARBOR, MI 48106 © 1979 WALTER E. BROWN All Rights Reserved PLEASE NOTE: In an cases this material has been filmed in the best possible way from the available copy. Problems encountered with this document have been identified here with a check mark . 1. Glossy photographs 2. Colored illustrations 3. Photographs with dark background 4. Illustrations are poor copy 5. ®rint shows through as there is text on both sides of page 6. Indistinct, Lroken or small print on several pages throughout 7. Tightly bound copy with print lost in spine 8. Computer printout pages with indistinct print 9. Page(s) lacking when material received, and not available from school or author •'0. Page(s) seau to be missing in numbering only as text follows 11. Poor carbon copy 12. Not original copy, several pages with blurred type 13. Appendix pages are poor copy ________ 14. Original copy with light type 15. Curling and wrinkled pages 16. Other Page 6b is unavailable for microfilming. Filmed as received. UniversîV Micrâiims intemadonal 300 N. 2==3 mo.. ANN ARBOR. VII •18106 i313l 761-4700 Toward an optimizing compiler for a very high level language by Walter E. Brown A Dissertation Submitted to the Graduate Faculty in Partial Fulfillment of the Requirements for the Degree of DOCTOR OF PHILOSOPHY Major: Computer Science Approved : In Charge of Major Wor For the Major Department For ?ortlfje. tl(le GVàdqate College Iowa State University Ames, Iowa 1979 Copyright 0 Walter E. Brown, 1979. All rights reserved. Signature was redacted for privacy. Signature was redacted for privacy. Signature was redacted for privacy. ii TABLE OF CONTENTS Page DEDICATION viii INTRODUCTION I CHAPTER I. STRUCTURED PROGRAMMING 4 Introduction 4 Stepwise Refinement 4 Abstract Data Types 6 Partial Recomposition 7 CHAPTER II. THE EXPERIMENTAL ENVIRONMENT 10 Introduction and Terminology 10 The APL Compiler and its Execution Mechanism 11 Acquisition and Preparation of the Sample 15 CHAPTER III. A TYPICAL APL PROGRAM 18 Introduction 18 General Information 19 Scalar and Mixed Operations 22 Operators 22 References 29 Specification, User Function Calls, I/O, and Branching 32 Sinnmary 33 CHAPTER IV. OPPORTUNITIES FOR PARTIAL RECOMPOSITION IN APL 37 Introduction and Definitions 37 Approach and General Statistics 39 N-ary Concatenation 43 Propagation of Constants 47 iii Page Shape 54 Constant Scalar Operands 60 Branch 68 Compress 77 N-ary Output 79 Composite Scalar Operations 83 Impact of Results on Execution Time 86 Summary 88 CHAPTER V. CONCLUSION 93 Overview 93 Evaluation 94 Future Directions 95 BIBLIOGRAPHY 97 ACKNOWLEDGMENTS 101 APPENDIX A. HEIGHT 0 DATA 102 APPENDIX B. TOP 40 DISTINCT HEIGHT 1 COMPOSITES 107 APPENDIX C. TOP 40 DISTINCT HEIGHT 2 COMPOSITES 109 iv LIST OF TABLES Page Table 1. General statistics of three samples 20 Table 2. Most common APL operations 21 Table 3. Dyadic scalar operations' frequencies 23 Table 4. Monadic scalar operations* frequencies 24 Table 5. Dyadic mixed operations' frequencies 25 Table 6. Monadic mixed operations' frequencies 26 Table 7. APL operator frequencies 27 Table 8. Dyadic scalar frequencies used in reduction 28 Table 9. Dyadic scalar frequencies used in outer product. ... 29 Table 10. Dyadic scalar pair frequencies used in inner product . 30 Table 11. Reference frequencies 31 Table 12. Constant frequencies by type 31 Table 13. Input/output frequencies 33 Table 14. Summary of static use of APL operation categories. . . 34 Table 15. Composition of a typical line of an APL program. ... 36 Table 16. Most frequently occurring height one flow of control composites 41 Table 17. Distribution of concatenations in composites 44 Table 18. Execution time model for simple concatenation 45 Table 19. Naive vs. recomposed n-ary concatenation execution times 46 Table 20. Comparison of execution times for n-ary concatenation when s = 10 47 Table 21. Distribution of operations in composites of constants. 50 V Page Table 22. Major contributing operations to constant propagation 51 Table 23. Operations appearing at the root of compiletxme cowposxtes........... ......... 31 Table 24. Distribution of operations in feasible composites of constants 53 Table 25. Major composites involving shape 55 Table 26. Execution time model for shape 56 Table 27. Execution time model for ravel 56 Table 28. Naive vs. recomposed rank execution times 57 Table 29. Naive vs. reccmposed size execution times 58 Table 30. Operands of the size composite 59 Table 31. Operands of the rank composite 59 Table 32a. Constant left operands with commutative dyadic operations 61 Table 32b. Constant right operands with commutative dyadic operations 61 Table 33a. Constant left operands with noncomnutative dyadic operations 62 Table 33b. Constant right operands with noncommutative dyadic operations 63 Table 34. Naive vs. recomposed immediate execution times .... 64 Table 35. Summary of occurrences of constant operands 66 Table 36. Predominant branching targets 69 Table 37. Execution time model for branch 69 Table 38. Execution time for compression 70 Table 39. Naive vs. recomposed branch-compress execution times 70 vi Page Table 40. Execution time model for a relational operation. ... 72 Table 41. Naive vs. recomposed branch-compress-relational execution 72 Table 42. Naive vs. recomposed branch-immediate execution times 74 Table 43. Naive vs. recomposed conditional branch immediate execution times 74 Table 44. Naive vs. recomposed branch-concatenate execution times 76 Table 45. Predominant left operands of compression ....... 78 Table 46. Naive vs. reccmposed compress-r(rel) execution times 79 Table 47. Naive vs. recomposed 2-ary output execution times. . . 81 Table 48. Predominant targets of monadic format 82 Table 49. Distribution of number of operands of implicit output 82 Table 50. Distribution of operations in composites of connected scalar operations 84 Table 51. Naive vs. recomposed plus-times composite execution times on vector data 86 Table 52. Summary of benefits of recommended recompositions. . . 87 Table 53. Timing estimates for operations appearing in no composite 89 Table 54. Timing estimates for operations appearing in one or more composites 90 Table 55. Timing estimates for recomposed composite operations 91 vii LIST OF FIGURES Page Figure 1. A simple expression tree « . . . . 38 Figure 2. Some composite operations occurring in the expression tree of Figure 1 . 38 Figure 3. Examples of height 2 composite operations 38 Figure 4. Typical concatenation composite (with arbitrary operands) and its proposed 3-ary recomposition. ... 43 Figure 5. A typical height one composite having constant operands and its proposed recomposition via propagation of constants 48 Figure 6. An "immediate" recomposition 60 Figure 7. Branch-compress composite (with arbitrary operands) and its proposed recomposition 69 Figure 8. Branch-compress relational composite (with arbitrary operands) and its proposed recomposition 71 Figure 9. Conditional branch immediate composite and its proposed recomposition 75 Figure 10. Branch-concatenate composite and its proposed recomposition, for use where the left operand of the concatenation is known to be nonempty 75 Figure 11. Compress-relational composite (with arbitrary operands) and its proposed recomposition 78 Figure 12. Typical output-concatenation composite (with arbitrary operands) and its proposed 3-ary recomposition 80 Figure 13. Typical scalar operation composite (with arbitrary operands) and its proposed recomposition. ... 83 viii DEDICATION Dedicated to the Memory of my Grandmother VALERIE POPPER Rechtsanwaltswitwe 1 INTRODUCTION In recent years, the term "structured programming" has been used to refer to a highly disciplined methodology of computer programming which promotes the development of computer programs that are deemed better than programs developed via classical, less disciplined and more ad hoc, methods. It has been observed that, although structured programming leads to correct, well-written programs, it does little or nothing to promote efficiency in execution of such programs. Strawn (1) has addressed this issue in proposing an extension to the methodology, programming by "partial recomposition." His extension is designed to augment existing structured programming techniques by promoting execution efficiency in a highly disciplined manner. Recent developments in structured programming methodology have included the concept of "abstract data types" (implementation-independent mechanisms, typically axicsnatic in nature, for the formal specification of data structures [see Guttag (12)]) to be implemented via "operation clusters" (modules within a program in which all storage structures for data objects as well as all routines for manipulation of such storage structures are provided [see Liskov and Zilles (14)]). Underlying Strawn's proposal is the concept of a "composite operation" (an operation derived by composition of the primitive operations elaborated in operation clusters, intended to replace specific sequences of such primitive operations. The significance of the techniques lies in the hypothesis that direction execution of such composite operations by the 2 underlying execution mechanism is less costly than is execution of the corresponding sequence of primitives. (Storage utilization and execution time are accepted measures of efficiency in program execution; these will be employed throughout the remainder of this work.) Partial recomposition, then, is a form of "algorithm substitution" (50, p. 410), an optimization technique recognized as inapplicable in the environment provided by high level languages. Strawn intends his technique to be applied to well-structured programs represented as the application of basic operations (which are elaborated in an operation cluster) to data values of the appropriate types. Advantage can thus be taken of the specific sequence in which such basic operations are applied, and of the relative frequencies with which subsequences of the basic operations occur. Since the built-in operations of any programming language may be regarded as implementations of operation clusters on the language's built-in data types, Strawn's theory also has application in the context of programming languages. The processes of translation and subsequent execution of programs are directly affected by Strawn's proposal. The former involves a search for composite operations, while the latter involves the hypothesized gains in efficiency. This dissertation represents a verification of Strawn's proposal for a single programming language of significant size and scope. Such a verification does not, of course, establish the theory in general. It is felt, however, that the techniques used herein can be generalized and that general establishment of the theory will be forthcoming. 3a The APL programming language was chosen for this study. Since APL is a very high level language, it represents a possible worst case language for efficiency in program execution. More importantly, however, APL has a single data type (the rectangular array) with an exceptionally rich set of operations defined on it. This richness gives the language enough power to be interesting, yet the restriction to a single data type keeps the analysis manageable as a first step. The principal result of this dissertation is that partial recomposition is applicable in the environment of APL and that execution of resulting programs is significantly more efficient. This result was obtained by acquiring a large sample of APL programs and applying the partial recomposition technique to them. By comparing a detailed statistical analysis of these programs with comparable published work, it was established that the programs used here represent typical APL programs. This analysis was then extended to determine, for the language as a whole, what operation sequences are typically employed and with what relative frequencies. Specific composites were then proposed for recomposition and, within given models of an underlying execution mechanism, their execution efficiency compared with that of their underlying basic operations. In Chapter I, structured programming is surveyed, and Strawn's partial recomposition methodology is explained. Chapter II details the specific environment within which the investigation herein described took place. Chapter III presents results, corroborating earlier work by others, leading to a determination of the ingredients of a typical APL 3b program. Opportunities for improvement, via partial recomposition, of ccsnpiled APL code are investigated in Chapter IV, and recommendations are presented and modeled. Finally, Chapter V summarizes these procedures, tenders conclusions, and offers some directions for future extensions of uhe present work. 4 CHAPTER I. STRUCTURED PROGRAMMING Introduction Dijkstra, in discussing structured programming, refers to "techniques (mental, organizational or mechanical) [which] could be applied in the process of program composition . . (2, p. 222). Thus, structured programming can be defined as a discipline imposed on the programming task in order to obtain "software that is characterized by high degrees of initial correctness, readability, and maintainability ..." (3, p. 3). Put another way, "The task of organizing one's thought in a way that leads, in a reasonable time, to an understandable expression of a computing task, has ccme to be called [structured programming]" (attributed to C. A. R. Hoare [in 4, p. 656]). This chapter presents three approaches to structured programming, all of which can blend to form a more complete methodology than any approach by itself. Most attention will be focused on Strawn's contribution, since it is the motivating force behind the present work. Stepwise Refinement Wirth has noted that "Program construction consists of a sequence of refinement steps" (5, p. 226). When adhered to, this discipline "leads to programs with an inherent structure . . ." (6, p. 126). Since "the object [a programmer] has to produce must be usefully structured" (7, p. 51), stepwise refinement appears to be an appropriate methodology for the formulation of computer programs. 5 At the highest levels, according to this methodology, a programmer deals principally with abstractions: those (abstract) properites (of the data) that are required for solution of the p-^oblem, and those (sb= stract) operations (on these data) needed to achieve the desired goal. As subsequent refinements take place, decomposing the problem into constituent parts, more detail is added to the developing program and more ccHfflnitments are made. "Each refinement implies a number of design decisions based upon a set of design criteria (5, p. 227). Two principal benefits accrue from such an orderly development. First, a well-structured program invites an inductive proof of its correctness based on its structure. Thus, "the reliability of t