THE A D A- COMPILER On the design and implementation of an Ada compiler J. van Katwijk pity '£/£ The Ada— compiler On the design and implementation of an Ada language compiler Proefschrift ter verkrijging van de graad van doctor aan de Technische Universiteit Delft, op gezag van de Rector Magnificus, prof. dr. J.M. Dirken, in het openbaar te verdedigen ten overstaan van een commissie aangewezen door het College van Dekanen op dinsdag 15 september 1987 te 1400 uur door Jan van Katwijk geboren te Amsterdam, Wiskundig Ingenieur. Dit proefschrift is goedgekeurd door de promotor prof. dr. ir. W.L. van der Poel De tekst van dit proefschrift is door de auteur ingetypt met de ed editor onder het UNIX operating system. De tekst is geformatteerd met het volgende UNDC commando: pic | tbt[ eqn (diraff en is afgedrukt op een Canon Al laserprinter. t UNIX is een handelsmerk van A.T. & T. De Ada— compiler Het ontwerp en de implementatie van een Ada compiler Samenvatting In dit proefschrift worden enkele elementen uit het ontwerp en de implementatie van een compiler voor de programmeertaal Ada besproken. Daarbij wordt verwezen naar de Ada— compiler, een compiler voor bijna de gehele programmeertaal Ada. Deze implementatie is ontwikkeld aan de Technische Universiteit Delft, onder leiding van de auteur. De implementatie wordt Ada— genoemd omdat enkele details van de Ada programmeertaal (nog) niet zijn geïmplementeerd. In dit proefschrift worden de problemen bij de implementatie van een taal van de omvang en de complexiteit als de Ada taal besproken. De belangrijkste bijdragen van dit proefschrift zijn: (i) een overzicht van de literatuur over het implementeren van de Ada taal, (ii) een bespreking van algorithmes die toepasbaar zijn bij de implementatie van de Ada taal en die toegepast zijn bij de Ada— compiler. Het proefschrift begint, na een inleiding, met een kort overzicht van de Ada taal. Daarna wordt een compiler model besproken dat voor een grote taal toepasbaar is en als model heeft gediend voor de Ada— compiler. De belangrijkste elementen van de Ada— compiler worden vervolgens in een grotere mate van detaillering besproken. De discussie over het front end van de compiler spitst zich toe op praktische aspecten bij overload resolutie en het efficient implementeren van de scope en zichtbaarheidsregels. De bespreking van het back endvnn de compiler valt in verschillende delen uiteen. Allereerst wordt het run-time model voor de beschrijving van data structuren besproken. Daarna wordt een overzicht gegeven van de vertaling van enkele van de Ada taal constructies. Deze beschrijving wordt gevolgd door een beschrijving van low-level talen voor de intermediaire programma representatie. Een apart hoofdstuk is gewijd aan het ontwerp en de implementatie van een supervisor voor de ondersteuning van Ada tasking in run-time. Ook is een apart hoofdstuk opgenomen waarin het ontwerp en de implementatie van een programma bibliotheek faciliteit wordt besproken. Voor de in de diverse hoofdstukken geformuleerde problemen worden oplossingen besproken. t Ada is een geregistreerd handelsmerk van de regering der Verenigde Staten van Amerika, Ada Joint Program Office. The Ada— compiler On the design and implementation of an Ada language compiler Abstract In this thesis some elements in the design and implementation of a compiler for the Ada programming language are discussed. Reference is made to the Ada— compiler, an implementation of almost the whole Ada language. This implementation was made at Delft University of Technology under the author's supervision. It is called Ada—since a few details of the Ada language are not (yet) implemented. In this thesis the problems are discussed that are encountered in the implementation of a language as large and complex as the Ada language. The main contributions of this thesis are: (i) a survey of literature on the subject of implementing the Ada language, (ii) a discussion of algorithms that are applicable in an Ada language compiler and that are applied in the Ada— compiler. The thesis starts with an introduction and a brief survey of the Ada language. It then describes a compiler model suitable for the translation of a large language applied in the Ada— compiler. The major elements of the Ada— compiler are discussed in more detail. The discussion on the compiler front end is oriented towards practical aspects in overload resolution and the efficient implementation of the scope and visibility rules. The discussion on the compiler back end falls into several parts. First the run-time data description model is described. Then the translation of several higher-level language constructs is given. This description is followed by a brief description of low-level intermediate languages. A separate chapter is devoted to the design and implementation of an Ada tasking supervisor. Similarly, a separate chapter is devoted to the design and the implementation of a program-library manager. For the problems introduced in the various chapters solutions are discussed. CONTENTS 1. Introduction 1 1.1 A review of the research 1 1.2 A review of this thesis 2 1.3 Motivation for the present work and a project history 3 1.4 Research goals 8 2. A short overview of the Ada language 10 3. Architecture of an Ada language compiler 17 3.1 Introduction 17 3.2 The architecture of the Ada— compiler 19 3.3 The literature on Ada implementations 25 4. The Ada— compiler front end 28 4.1 Introduction 28 4.2 A brief review of front end descriptions 30 4.3 Intermediate program representations 34 4.4 Parsing and error repair 44 4.5 The handling of static semantics 53 4.6 Generic declarations and instantiations 102 5. The Ada— compiler back end 105 5.1 Introduction 105 5.2 Literature 107 5.3 Describing data: the run-time data description model 110 5.4 Exceptions and exception handling 135 5.5 The lowering of the semantics 140 5.6 Intermediate codes and code generators 152 6. The Ada— tasking supervisor 163 6.1 A survey of the literature 164 6.2 Issues in an Ada tasking supervisor 168 6.3 A tasking supervisor for the Ada— compiler 175 / 6.4 A schematic overview 184 6.5 The implementation of the Ada— tasking supervisor 186 7. The Ada— program library 196 7.1 Requirements for an Ada program library 196 7.2 A survey of the literature 197 7.3 The compilation and the elaboration order of compilation units 200 7.4 Program libraries for the Ada— Compiler 203 8. Results and conclusions 209 9. References 211 1 1. Introduction Writing a compiler is, even today, a rather complex job. Although since the early days of FORTRAN a tremendous progress has been made in the field, writing a compiler is still an art (or a craft) rather than a clerical job. Writing a compiler for a language of modest complexity, e.g. Pascal, is, using current methods and techniques, a relatively well- understood job. On the other hand, writing a compiler for a more complex language like the programming language Ada heavily relies on the inventivity of the compiler writer. Some areas of the field are well understood; in these areas established formalisms can be used to describe or even to generate parts of a compiler. This is particularly true for scanning, parsing and to some extent for code generation. For the design of other parts, other formalisms can be used, either to develop a prototype or to increase the insight in how particular subprocesses are (to be) performed. In particular this applies to the use of attributed grammars or, to a lesser extent, to the use of denotational semantics. Nevertheless, in a recent paper [Boom-86] it is stated that current formal methods are not well-suited for use in programming language descriptions. We believe that it will take some time before such formal methods are ready to be used by a compiler writer. For a large number of subtasks in the design and the implementation of a compiler, formalisms are not yet well-suited or even not applicable at all. This is by no means meant as a criticism of the use of formalisms; all that is stated here is that for the design and implementation of large-language compilers important parts have to be designed by the compiler writer himself. The design and implementation of large-language compilers has some things in common with other software engineerings disciplines; a large part of the process is related to mastering the complexity of the problem and its solution. A positive side effect of designing large-language compilers is the increasing insight in how a compiler has to be built. It is this knowledge that can be used in a later stage as the basis for a process of automating parts of the compiler writer's job. 1.1 A review of the research This paper makes reference to a project to design and implement a compiler for (a large subset of) the Ada language under the UNIX operating system. As a result of the project, a compiler for almost the whole Ada language was designed, implemented and is operational. The implementation, called the Ada— compiler, is still incomplete (hence its name: the Ada minus compiler); it is expected, however, that in due course it will become a full Ada language compiler. The most significant omission in the implemented language is the lack of fixed and floating point arithmetic types and operators. Furthermore, the language differs in a number of minor details from the language described in [LRM-83]. A detailed survey of the implemented language is given in [Biegstraaten-87]. The research started as an exercise to implement a subset of the Ada language, more or less to satisfy our curiosity. The original subset, which was called DAS (Delft Ada t UNIX is a trademark of AT & T 2 Introduction Subset), included packages and overloading. It excluded tasking, generics, derived types, numeric types, stubs and separate units. After DAS was implemented successfully, the research aspect gained importance. It was not only felt interesting to implement a subset, it seemed at least as interesting to investigate the problems that would come up in the design and implementation of a larger subset or even of the full language. In particular, interest was raised for practical aspects concerning the construction of a compiler. Currently, a number of validated Ada language compilers is available; the technology used in their construction is not widespread, however. This technology usually remains a company secret. One of the goals in this research is to make available algorithms, methods and techniques that are useful in the construction of Ada language compilers. The knowledge gained in the process of building a compiler can be used as a basis for improving the implementation itself. Furthermore it should be the basis for further research in and development of compiler technology. 1,2 A review of this thesis No attempt is made in this thesis to write a Cookbook for the Ada-compiler builder. Our implementation is currently about 55,000 lines of C code and although only a small part of the code is really interesting, this small part is still over 10,000 lines of code. Such an amount is far too large to allow a detailed discussion. Therefore, the description is restricted to a review of some particularly interesting points. As such, the choice resulted in a discussion on compiler front-end aspects, a discussion on aspects of the compiler back end, a discussion on the design and implementation of a tasking supervisor and a discussion on support for separate compilation. — Front end: The front end of an average Ada language compiler deals with various forms of analysis that are required by the language reference manual [LRM-83] and generates a high-level intermediate program representation. Points that were thought to be particularly interesting are: • practical aspects of overload resolution. Although the basic approach to overload resolution in Ada is well known, any implementor has to solve a number of practical problems. Problems that can be identified are: resolving the syntactic ambiguity in indexing, calling and slicing operations and handling of special operators such as e.g. the equality operator, which is implicitly declared for user- defined types in the Ada language. • the implementation of scope and visibility rules. The Ada language has forms of explicit scope control . Managing a compile-time symbol table is complex and time-consuming. A straightforwardly implemented set of algorithms for symbol table management consumed about 25% of the time spent in front end processing. — Back end: The back end of an Ada language compiler performs a translation of the high-level intermediate program representation obtained by the front end to target assembler code. A major effort in our work was the design and subsequently the t Explicit scope control gives the programmer control over the visibility of declarations in terms of the program text. 1.2 A review of this thesis 3 implementation of a model for the representation of the complex data structures at run time. This model, the doublet model, turns out to be simple and easy to implement while yielding fairly efficient run-time code. — Tasking: Tasking is considered to be an important as well as a complex topic. — Separate compilation: One of the contributions of the Ada language to the field of software engineering is the safe separate compilation facility. This facility requires support in the form of a program library. The organisation of this thesis is therefore as follows: • first a short chapter (chapter 2) is devoted to a discussion of some of the main characteristics of the Ada language; • in the next chapter (chapter 3), an overview is given on the architecture of a compiler for the Ada language together with a brief overview on literature on the topic. • the bulk of this thesis is formed by four technical chapters (chapters 4, 5, 6, and 7), describing some details of algorithms that are applied in the implementation of the Ada— compiler. Chapter 4 is devoted to elements of the front end; chapter 5 to elements of the compiler's back end, chapter 6 to various (implementation) aspects of tasking in the Ada language and chapter 7 to separate compilation and its implementation; • finally, a short chapter (chapter 8) is dedicated to results and conclusions. 1.3 Motivation for the present work and a project history There are, of course, several reasons for implementing a language as large and complex as the Ada language. Prior to attacking the Ada language, the author had implemented Algol 60 twice. The first implementation was in BCPL [Richards-80] on a DEC/PDP-11 computer under the RT/11 operating system. The second implementation, a redesign of the previous one, was written in C under the UNIX time-sharing system. Having implemented ALGOL 60 and having interest in systems programming and programming language implementation, it was felt that the design and implementation of a compiler for a (small) subset of the Ada language could be a real challenge. Interest for the Ada language was expressed in early 1980 when the author organized a workshop on the language. As a result, other staff members became highly interested, as did students; the interest centered on the aspects of software engineering, raised by Ada as language, by the language itself and by its implementation aspects. Some students began to design and to build a simple context-free parser for Ada. At that time discussions started among staff members on the feasibility of implementing an Ada subset as a student project. A group of four students (Henri Bal, Wim de Pauw, Hans van Someren en Jeanet Vonk) was asked to investigate the possibilities for such an t PDP, VAX and RT/11 are trademarks of Digital Equipment Corporation 4 Introduction implementation. Later, three of them (Henri Bal, Hans van Someren en Jeanet Vonk) actually began with the design and implementation of a subset which was called DAS. Henri Bal and Jeanet Vonk designed a front end [Bal-82], [Vonk-82]. The resulting front end which was written in C ran on a PDP-11/60 under the UNIX time sharing system. It consisted of two separate programs: • a lexical and syntactical analyzer comprising the first pass, [Vonk-82]; • a static-semantics analyzer comprising the second pass [Vonk-82], [Bal-82]. At the same time a tree-structured intermediate program representation based on early versions of DIANA [DIANA-83] was designed. The output of the first compiler pass was a program representation in this intermediate notation; the second pass operated on the intermediate program representation, essentially without changing its structure. One of the first steps in the design of the back end of our compiler was the development of a model for the description of data at run time. We felt that the classical dope-vector based approach as described by e.g. Gries [Gries-71] was less suited for a language like the Ada language. Dope vectors carry a pointer to the object they describe or are part of this object. Sharing descriptors between objects with a similar structure and similar constraints seems hardly possible. Furthermore, we felt that the usual dope-vector based tree-structured organization of complex data structures accompanying the dope vector approach would complicate the generating of efficient access code to components of these data structures. A new model, the doublet model, was designed by this author in cooperation with Hans van Someren [Katwijk-84a]. A start of the implementation of the computation of storage requirements based on the doublet model was made by Hans van Someren. He implemented a part of the storage allocator, a compiler phase determining for each run-time object its storage class and its addressing path [Someren-82]. Wim de Pauw made a first attempt to implement an expander phase, a compiler phase mapping the high-level intermediate program representation onto the low-level intermediate program representation of the selected code generator [Pauw-83]. An interpreter for (a part of) DAS was designed and implemented by Niels Bogstad en Albert Hartveld [Bogstad-83]. The work was carried out at the Department of Electrical Engineering under the supervision of Prof. A. van de Goor and Hans van Someren. The interpreter was based on a literal implementation of the doublet model. As could be expected, it was extremely slow. Nevertheless, at that time it was helpful to have such a tool available. A major restriction in the design and the implementation of the compiler was the 64 Kb address space of the PDP-11/60. There was no possibility to have any significant part of the intermediate program representation in main memory. As a result, the intermediate program representation was constructed piece by piece and was processed piece by piece. t DIANA, Descriptive intermediate Attributed dotation for /Ida, was intended as a standardized intermediate program representation.