Principal Compiler design
Due to the technical work on the site downloading books (as well as file conversion and sending books to email/kindle) may be unstable from May, 27 to May, 28 Also, for users who have an active donation now, we will extend the donation period.

Compiler design

Addison-Wesley Publishing Co
ISBN 10:
ISBN 13:
International Computer Science Series
DJVU, 15.92 MB
Descarga (djvu, 15.92 MB)
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.

Иллюзии зрения

DJVU, 12.47 MB
COMPILER DESIGN Reinbard Wilhelm * Dieter Maurer ■fa \noiso\

INTERNATIONAL COMPUTER SCIENCE SERIES Consulting Editor A D McGettrick University of Strathclyde SELECTED TITLES IN THE SERIES Software Development with Z J B Wordsworth Program Verification N Francez Performance Modelling of Communication Networks P G Harrison and NMPatel Concurrent Systems: An Integrated Approach to Operating Systems, Database, and Distributed Systems J Bacon Introduction to Parallel Processing B Codenotti and M Leoncini Concurrent Programming A Burns and G Davies Comparative Programming Languages (2nd Edn) L B Wilson and R G Clark Functional Programming and Parallel Graph Rewriting R Plasmeijer and M van Eekelen Object-Oriented Database Systems: Concepts and Architectures E Bertino and L D Martino Prograinming in Ada (4th Edn) JGP Barnes Software Design D Budgen Ada from the Beginning (2nd Edn) JSkansholm Programming Language Essentials H E Bal and D Grune Human-Computer Interaction J Preece et al. Distributed Systems: Concepts and Design (2nd Edn) G Coulouris, J Dollimore andTKindberg Fortran 90 Programming TMR Ellis, IR Philips and TMLahey Parallel Processing: The Transputer and its Applications MEC Hull, D Crookes and P J Sweeney Foundations of Computing: System Development with Set Theory and Logic TScheurer Principles of Object Oriented Engineering A Eliens tT>3.q W?l COMPILER Reinhard Wilhelm University of the Saarland, Saarbrucken Dieter Maurer Saarbrucken Zeitung . Translated by Stephen S. Wilson ADDISON-WESLEY PUBLISHING COMPANY Harlow, England 'Reading, Massachusetts 'Menlo Park, California «New York Don Mills, Ontario 'Amsterdam »Bonn 'Sydney 'Singapore Tokyo 'Madrid «San Juan 'Milan 'Mexico City 'Seoul 'Taipei

Preface Compilers for high-level programming languages are large, complex software systems. However, they have a number of special characteristics which distinguish them from most other software systems. Their functionality is (almost) well defined. Ideally, there exist formal, or at least precis; e descriptions of the source language and the target language. Frequently, there also exist descriptions of the interfaces to the operating system, to the programming environment, to other compilers and to program libraries. The decomposition of the compilation tasks into subtasks with well-defined interfaces is well understood. This results in a natural modular structure, which, incidentally, is also reflected in the usual structure of books on compiler design. Some of the various subtasks of compilation have been very extensively studied. The corresponding theories were developed specifically or taken over from the theory of formal languages and automata. They provide a good basis for the implementation of modules for compiler subtasks. For some of the subtasks, there even exist mechanisms for their formal description and generation procedures that generate parts of compilers automatically from such formal descriptions. Many such generators are available and in use. This book is not a cook book. You will not find recipes of the form 'to construct a compiler from source language X into machine language Y, take...'. The presentation reflects the special characteristics of compiler design listed above, including, in particular, the existence of the theory and the automatic generation methods. This book is intended for advanced undergraduate and graduate students specializing in computer science. A knowledge of imperative programming languages is a prerequisite. While the chapters on the compilation of functional, logic and object-oriented programming languages each contain a long introduction to the concepts of these language classes, it is advisable to learn a modern functional language, Prolog and Smalltalk, Eiffel or C++, for a better understanding of the corresponding chapters. In addition, the reader will profit from a good grounding in the theory of formal languages and automata, although the theory needed is always presented in full. Structure of the book Chapters 2 to 5 describe what a compiler does, in other words, the correspondence that it generates between a source program and an object program. For this, we

viii Preface introduce an appropriate abstract machine for an imperative, a functional and a logic programming language and give a precise description of the compilation of programs in each source language into the language of the associated abstract machine. Object- oriented languages developed from imperative languages by extending them by a number of new concepts which essentially relate to the type system. Thus, only the compilation of these extensions is described in Chapter 5. In each case, the starting point is an analysed source program, which we shall later refer to as associated decorated abstract syntax. In Chapters 6 to 12 we describe the how of compilation, namely how the compilation process is divided into individual phases, the tasks performed by these phases, the techniques used in them, how what they do can be formally described and how a compiler module can be generated (even automatically) from such a description. Material for a two- or three-term lecture course can be selected from this book, depending on the time available. Chapter 2 and material from Chapters 6-9,11 and 12 would suffice for a conventional one-term lecture course on the compilation of imperative programming languages. A two-term lecture course would cover die compilation of functional, logic and object-oriented programming languages together with areas of current research such as abstract interpretation and code generation for parallel target architectures. Acknowledgements The book developed from a number of lecture courses given by both authors at the University of the Saarland in Saarbriicken, Germany. The (then) three-term course was first given in 1987/1988. The number of those who have actively cooperated in this work and/or provided constructive criticism of it is so large that we are unable to thank them all personally here. We are particularly grateful to Martin Alt, Ingrid Biehl, Christian Fecht, Christian Ferdinand, Reinhold Heckmann, Andreas Hense, Stefan Kahrs, Peter Lipps, Gudula Riinger, Georg Sander and Helmut Seidl. The TeXnicians Christine Wentz and Patrik Zeimetz have patiently processed several revisions. Reinhard Wilhelm, Dieter Maurer April 1992 Preface ix Preface to the English edition The major change from the German edition is that a chapter on the compilation of object-oriented languages has been added, in which we discuss the implementation of simple and multiple inheritance. Since the German edition is apparently extensively used, we have received numerous suggestions for improvements, for which we are especially grateful to Reinhold Heckmann, Helmut Seidl and, in particular, Helmut Partsch. Material related to this book, for example, a specification of an accompanying compiler laboratory project, can be obtained by anonymous ftp from ftp, in/pub/compiler. Reinhard Wilhelm, Dieter Maurer Saarbriicken, St. Ingbert, April 1995 For reasons of simplicity, the pronoun 'he' is used to relate to bom male and female throughout the book.

Contents Preface vii 1 Introduction 1 1.1 High-level programming languages 2 1.2 The implementation of programming languages 3 2 Compilation of imperative programming languages 7 2.1 Language constructs and their compilation 8 2.2 The architecture of the P machine 9 2.3 Assignments and expressions 10 2.4 Conditional and iterative statements, sequences of statements 13 2.5 Memory allocation for variables of simple type 18 2.6 Memory allocation for arrays 19 2.7 Memory allocation for records 27 2.8 Pointers and dynamic memory allocation 28 2.9 Procedures 32 2.10 Mainprogram 56 2.11 Exercises 57 2.12 Literature 61 3 Compilation of functional programming languages 63 3.1 Language type and introductory example 64 3.2 LaMa, a simple functional programming language 72 3.3 Introduction to the compilation of LaMa 77 3.4 Environments and bindings 81 3.5 The MaMa architecture 83

3.6 Stack management and addressing 3.7 Instruction set and compilation 3.8 Implementation of lists 3.9 Exercises 3.10 Literature CompUation of logic programming languages 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 Logic programming languages Logical foundations Unification Execution of logic programs Prolog Abstract Prolog machine Compilation of Prolog Efficiency improvements Exercises Literature Compilation of object-oriented languages 5.1 Concepts of object-oriented languages 5.2 The compilation of methods 5.3 Schemes for compilation of inheritance 5.4 Genericity 5.5 Exercises 5.6 Literature The structure of compilers 6.1 Compiler subtasks 6.2 Lexical analysis 6.3 Screening 6.4 Syntax analysis 6.5 Semantic analysis Contents xiii 6.6 Machine-independent optimization • 6.7 Address assignment 6.8 Generation of the target program 6.9 Machine-dependent code improvement 6.10 Real compiler structures 6.11 Formal specification and generation of compiler modules 6.12 Literature Lexical analysis 7.1 The task of lexical analysis 7.2 Theoretical foundations 7.3 A language for specifying the lexical analysis 7.4 The generation of a scanner 7.5 Thescreener 7.6 Flex, a scanner generator under UNIX 7.7 Exercises 7.8 Literature Syntax analysis 8.1 The task of syntax analysis 8.2 Theoretical foundations 8.3 Top-down syntax analysis 8.4 Bottom-up syntax analysis 8.5 Bison, an LALR(l)-parser generator 8.6 Exercises 8.7 Literature Semantic analysis 9.1 Task of the semantic analysis 9.2 Attribute grammars 9.3 Examples of attribute grammars 9.4 The generation of attribute evaluators 228 229 230 231 231 232 233 235 236 236 248 251 256 259 261 263 265 266 269 300 339 375 377 382 385 386 405 410 417

9.5 9.6 Exercises Literature Abstract interpretation 10.1 10.2 10.3 10.4 10.5 Trees: 11.1 11.2 11.3 11.4 11.5 11.6 11.7 11.8 11.9 11.10 11.11 Introduction Abstract interpretation based on denotational semantics Abstract interpretation based on operational semantics Exercises Literature pattern matching and parsing Program transformations Code selection The pattern-matching problem The tree-parsing problem Finite tree automata Generation of pattern matchers Generation of tree parsers Tree automata with costs Implementation Exercises Literature Code generation 12.1 12.2 12.3 12.4 12.5 12.6 12.7 12.8 Abstract and real machines Classification of architectures Program representations Code generation, integrated methods Register allocation by graph colouring Instruction scheduling Exercises Literature 453 456 457 458 462 484 506 510 513 514 519 523 526 529 531 535 537 542 544 545 547 548 554 558 561 568 570 588 590 Contents xv Bibliography 591 Index 599

Trademark notice Miranda™ is a trademark of Research Software Limited Smalltalk-80™ is a trademark of Xerox Corporation Flavors™ is a trademark of Symbolics Inc. Windows™ is a trademark of Microsoft Corporation MC 680x0™ is a trademark of Motorola Corporation VAX™ is a trademark of Digital Equipment Corporation 80x86™ is a trademark of Intel Corporation 32xxx™ is a trademark of National Semiconductor Corporation 360/91™ is a trademark of International Business Machines Corporation 6600™ is a trademark of Control Data Corporation 1 Introduction • High-level programming languages • The implementation of programming languages

1.1 High-level programming languages Nowadays, programs are mainly written in so-called problem-oriented, high- level programming languages. These programming languages are removed (to a varying degree) from the structure and the details of the computers on which the programs written in them are executed. The four most important classes of universal programming languages are: • The class of imperative languages such as Algol 60, Algol 68, Fortran, COBOL, Pascal, Ada, Modula 2 and C. These are closely oriented towards the structure of so-called von Neumann computers which include almost all commercially available computers. These machines consist of an (active) central processing unit (CPU), a (passive) memory and a bus for the traffic between the CPU and the memory. • The class of functional languages such as LISP, HOPE, Miranda, Haskell and FP. This class is characterized by the following properties: - There is no distinction between statements and expressions. Names are only used to identify expressions and functions; they are not used to identify memory locations. Functions may occur as the arguments and the results of functions. The execution principle for functional languages is reduction; in other words, a functional program is evaluated by successively replacing expressions (subexpressions) by equivalent simpler expressions (subexpressions) until the normal form is obtained, when the process ends. • The class of logic programming languages such as Prolog and its various dialects. These languages are based on an operational view of predicate calculus. The execution mechanism is resolution, a procedure that was developed for proving implications in first-order predicate calculus. • Object-oriented programming languages are essentially imperative, have type systems that support data abstraction and permit an 'evolutionary' form of software development. This form of software development, the refinement and adaptation of existing software components, is usually supported by an appropriate development environment. In addition to these four classes, there are many other languages, for particular applications, which have a number of things in common with programming languages: • Hardware description languages. These are used to specify computers and computer components. Such specifications may describe the functional behaviour, hierarchical structure and geometrical arrangement of components. 1.2 The implementation of programming languages 3 • Operating system command languages. These include primitive constructs, for example for activating system functions and user programs, together with facilities that provide for the coordinated interworking of a number of such programs and system functions, the creation and termination of processes and the detection and handling of abnormal situations. • Text and graphics specification languages. These may be used to describe text or graphics objects. In the case of graphics, the object is usually complete, in other words, specified by the entry of geometrical coordinates, or the like. For text objects, which are usually called documents, only page layout restrictions for a text formatter are normally specified. 1.2 The implementation of programming languages In order that programs in a certain programming language L may be executed on a computer, that language must be made available, or implemented, on the particular type of computer. This may be achieved in various ways. Implementations are divided into interpreters and compilers. 1.2.1 Interpreters Let us consider a programming language L. The input to an interpreter h consists of a program pi in L and an input sequence e, from which It computes an output sequence a. The interpretation of pl may lead to an error. Thus, IL has the functionality IL:LxD* -* D*U {error} when the input and output data belong to the same domain D. The execution of the program pi with input sequence e and result sequence a is then described by the equation h(PL,e) = a What are the characteristics of an interpreter? It processes program pl and input e simultaneously. Each construct is new to it, even in the case of repeated execution. It does not use any information independent from the input data, which it could obtain by inspecting the program text (for example, the number of declared variables in a block, a function or a clause). It could use this information to allocate the memory for efficient access to the variable values. 1.2.2 Compilers The aim is to avoid the inefficiency associated with interpretation. This involves the use of a principle commonly applied in computer science, which is usually referred to as precomputation or sometimes partial evaluation or mixed computation.

Whereas the interpreter / receives and processes both its arguments, the program pl and the input sequence e, at the same time, the program and the input sequence are now processed at two different times. First, the program pi is 'preprocessed'; in other words, it is analysed independently of all input data and converted into another form which provides for the efficient execution of the program with arbitrary input sequences. The additional cost of preprocessing the program is assumed to be offset by executing it with one or more input sequences. What does preprocessing programs involve? Usually, it comprises the translation (compilation) of the program pl , written in the language L, now called the source language, into the machine or assembly language M of a specific or abstract computer. The time at which this translation takes place is called compile time and the resulting program pu, corresponding to pi, is called the object program. In particular, compiling source programs into object programs avoids the two sources of inefficiency associated with interpretation. Each program is analysed once at compile time; the analysis of the corresponding object program (let us suppose that this is a program in the machine code of a real computer) only involves the decoding of the instruction code by the computer's command unit. Efficient, and sometimes direct, access to variable values and locations is provided for by a memory management scheme which assigns fixed (relative) addresses to all the program variables. These addresses are then used in the corresponding object program. The corresponding object progam pu is executed with the input sequence e at some time after compile time, known as run time. Naturally, one requirement on compilation is that when object program pM is executed with input e it should produce the result sequence a, where Il(pl, e) = a. The following is a minimum requirement on compilation. Suppose that pi is a program which is syntactically correct and satisfies the context conditions of L; in other words, suppose that pi is correctly typed. Suppose that the compiler generates the object program pm corresponding to pl. If II does not encounter any errors when pl is executed with e and produces the output a, then no errors should occur when pu is executed with input sequence e and both the interpretation of pi and the execution of pM with e should provide the same result. Let us suppose that machine M is an interpreter Im for its machine language, then the following must hold for such combinations (pi, e): If h(PL, e) — a then Im(pm, e) = a, where pm is the object program corresponding to pi. There are also a number of error situations. For example, pi may contain syntax errors or violations of the context conditions in parts of the program that do not affect the interpreter in the case of execution with e. Thus, interpretation could be successful, although the compiler, which analyses the whole program, would fail to produce the object program, as a result of detecting errors. On the other hand, although pL is syntactically correct and satisfies the context conditions, IL may encounter a (runtime) error when executing with input e. Since //, is considered to be the definition of the semantics of L, the corresponding object program pu must also encounter errors when executed with e. 1.2 The implementation of programming languages 5 1.2.3 Real and abstract machines Usually, the programmer will have a so-called real computer at his or her disposition. A large variety of real computers is available on the market, with different hardware, that is, the motherboards with their various processors, memory chips and whatever else is required. In this case, the compiler's target language is defined by the type of processor used. As we shall see, real computers are largely oriented towards imperative programming languages; in other words, the operations and structures of real computers, such as pointers, branches, linear storage, indexed access, and so on, are to some extent mirrored in the concepts of imperative programming languages, while the other concepts of imperative languages are relatively easy to translate into the structures and instruction sequences of real computers. There is no similar correspondence between functional or logic programming languages and present-day computers. This is one reason for the introduction of so- called abstract machines which are better adapted to these language types. These computers support the concepts of these languages better than real machines and thus simplify their implementation. They also facilitate the porting of a compiler from one machine to another, because they are realized in software rather than hardware. Furthermore, an abstract machine may also be designed and used for teaching purposes. For those wishing to consider the principles of programming language compilation, suitably designed abstract machines enable the fundamental problems to be isolated from those facing the compiler designer as a result of the latest advances in computer architectures.

Compilation of imperative programming languages • Language constructs and their compilation • The architecture of the P machine • Assignments and expressions • Conditional and iterative statements, sequences of statements • Memory allocation for variables of simple type • Memory allocation for arrays • Memory allocation for records • Pointers and dynamic memory allocation • Procedures • Main program • Exercises • Literature

8 Compilation of imperative programming languages In this chapter, we shall give an intuitive description of what a compiler of imperative programming languages does; we shall only consider how it does this later. For this, we give a precise but intuitive definition of the correspondence between programs in an imperative source language and programs on a target computer obtained by compilation. For the source language, we choose a slightly thinned down version of Pascal. For the target computer, we choose an abstract machine, the P machine, whose architecture was designed to make compiling Pascal into its machine language as simple as possible. The correspondence is defined using compilation functions, which are given one by one for the individual Pascal constructs. 2.1 Language constructs and their compilation Imperative programming languages possess the following constructs and concepts which must be mapped onto the constructs, concepts and instruction sequences of abstract or real computers: • Variables are containers for data objects whose contents (values) may be changed during the execution of the program. The values are changed by the execution of statements such as assignments. A number of variables may be combined into aggregates, arrays and records. The current values of the variables at any given time form part of the state of the program at that time. Variables in programs are identified by names. Since constants, procedures and so on are also identified by names, we speak of variable identifiers, constant identifiers, and so on, when we wish to distinguish between these special types of names. Variable identifiers must be assigned machine memory locations containing the current values. If the programming language contains recursive procedures with local names, the calling of a procedure gives rise to new incarnations of the local variable identifiers, to which new storage space must be assigned. When the procedure is exited the memory locations for these incarnations are released. Thus, these languages are implemented using a stack-like memory management. • Expressions are terms formed from constants, names and operators which are evaluated during execution. Their value is generally state dependent, since on each evaluation the current values of the variables in the expression are used. • Explicit specification of the control flow. The branch instruction goto, which exists in most imperative programming languages, can be directly compiled into the unconditional branch instruction of the target machine. Higher-level control constructs such as conditional (if) or iterative (while, repeat, for) statements are compiled using conditional branches. A 2.2 The architecture of the P machine 9 conditional branch follows an instruction sequence to evaluate a condition. For some source languages, the distinction of case conditions can be efficiently implemented on some target machines using indexed branches, in which the branch address in the instruction is modified by a previously computed value. Procedures provide a means of activating a sequence of statements from a point in a program to which control is returned after their execution. For this, the machine must have a branch instruction that does not forget its origin. The body of the procedure can be supplied with actual parameters whenever it is called. This, together with the creation of incarnations of local names, requires a complex memory organization, which is often supported by special machine instructions. 2.2 The architecture of the P machine The (abstract) P machine was developed to make the Zurich implementation of Pascal portable. Anyone wishing to implement Pascal on a real computer had only to write an interpreter for the instructions of this abstract machine. The Pascal compiler, written in Pascal and compiled into P-code, could then be run on the real computer. The architecture and the instructions of the P machine will be introduced gradually as they are needed to compile the individual concepts in the source code. For now, we shall introduce only the memory, some registers and the main machine cycle of the P machine. The P machine has a data memo^ STOR& of length maxstr+1 and a program memory CODE of length codemax+1. At the lower end of the data memory (from address 0) is a variable stack. A register SP (stack pointer) points to the highest occupied location. Note that later, for clarity in figures in which stacks are represented vertically, the 'highest' stack location is always at the bottom, while the lower addresses of memory locations are shown at the top of the diagram. Some instructions store the contents of explicitly addressed locations on top of the stack and thus extend the stack; conversely, other instructions store the contents of the highest stack location in an explicitly addressed location and thus shorten the stack, see Table 2.2. The instructions are partially parameterized according to type: N stands for numerical type (integer), T stands for arbitrary simple types (numerical, STORE . CODE Stack J | | 0 ' f maxstr 0 t codemax SP PC Figure 2.1 The memory of the P machine and some registers.

Compilation of imperative programming languages logical, character and enumeration type) and for addresses, i is for integer, r is for real, b is for Boolean and a is for addresses. The arithmetic operations on addresses are the same as those on integer operands, but the value ranges are generally different. Operators indexed by a type denote the corresponding operations on the underlying value ranges, for example <,• denotes the comparison of two integers to determine the smaller. Other instructions use the contents of SP implicitly, in that they operate on the contents of one or more of the highest occupied stack locations; they may also alter the contents of SP and store the result of the operation in the (new) highest stack location, see Table 2.1. Of course, the P machine also has a program counter, the PC register, which contains the address of the next instruction to be executed. All instructions in the P machine occupy a single location in the program memory, so that, except in the case of branches, the PC register is incremented in steps of 1. Thus, the main cycle of the P machine has the following form: do PC:=PC+1; execute the instruction in location CODE\PC-l] od Initially, the PC register is initialized with the program start, in other words, it is set to 0, since the program begins at CODE[0]. 2.3 Assignments and expressions Tables 2.1 and 2.2 list all the instructions we need to compile assignments and expressions into P machine code. The instruction sequences that are generated for an assignment or an expression are specified using code functions. The argument of a code function is an assignment or a bracketed expression. The code function decomposes this argument recursively and assembles the instruction sequences generated for each component into the overall instruction sequence. When compiling assignments, we note that a variable identifier on the left of an assignment is compiled differently from a variable identifier on the right. For the variable identifier on the left, the address of the location assigned to it is required so that its contents may be overwritten; the value of the variable identifier on the right is needed to compute the value of the expression. Therefore, we talk about the left values (L values) and right values (R values) of variables, when we wish to indicate that we are interested in the address of the variable or its current value, respectively. Thus, we index the code functions with L or R, where codeL generates instructions to compute the L value and codes generates instructions to compute the R value. The function code (without a subscript) is used to compile statements for which we expect neither addresses nor values. 2.3 Assignments and expressions 11 Table 2.1 P-instructions for expressions. The 'Condition' column gives the necessary condition at the top of the stack, the 'Result' column gives the resulting situation. Here, (N, N) in the condition column means that there must be two numerical values of the same type at the top of the stack. All occurrences of N or T in the description of an instruction always refer to the same type. If the 'Condition' column contains more type characters than the 'Result' column, this means that the stack is shortened when this instruction is executed. Instr. add AT sub N imAN divN negiV and or not equT geqT leqT lesT grtr neqT Meaning STORElSP-1] := STORE[SP-l] +N STOREISP); SP:=SP-1 STORE[SP-l] := STORE[SP-i] -N STORE[SP]; SP:=SP-1 STORE[SP-l] := STORE[SP-l] *N STORE[SP]; SP:=SP-l STORE[SP-l] := STORE[SP-\] /N STORE[SP]; SP:=SP-1 STORE[SP] := -N STOREISP] STORE[SP-l] := STORE[SP-l] and STORE[SP]; SP:=SP-\ STORE[SP-l) := STORE[SP-l] orSTORE[SP]; SP:=SP-l STOREISP] := not STOREISP] STORE[SP-U := STORE[SP-l] =r STORE[SP]; SP:=SP-l STORElSP-1] := STORE[SP-l] >T STOREISP]; SP:=SP-\ STORE[SP-l] :a STORE[SP-l] <T STORE[SP]; SP:=SP-l STORElSP-l] := STORE[SP-\] <T STORE[SP]; SP':=SP-l STORElSP-l] :=STORE[SP-l] >T STORE[SP]; SP:=SP-l STORElSP-1] :=STORE[SP-l] ^T STOREISP]; SP:=SP-l Cond. (N,N) (JV) (b,b) (b,b) (b) (T,T) (T,T) (T,T) (T,T) (T. J) (T,T) Result (N) (N) (N) (ft) (N) (b) (b) (b) (b) (b) (b) (b) (b) (b)

12 Compilation of imperative programming languages Table 2.2 Store and load instructions. Ido loads from a location given by an absolute address, ldc loads a constant given in the instruction, ind loads indirectly using the highest stack location, sro stores in a location given by an absolute address, and sto stores in a location addressed by the second-highest location on the stack. Instr. \AoTq IdcTq indT sroTq stoT Meaning SP:=SP+V, STORE[SP]-STORE[q] SP:=SP+l; STORE[SP]:=q STORE[SP] := STORE{STORE[SP]] STORE[q]:=STORE[SPY, SP:=SP-l STORE[STORE[SP-l]] := STORE[SP]; SP:=SP-2 Cond. q € [0,maxstr] Type(«) = r (a) (7) q 6 [Ojnaxstr] (a, 7) Result (7) (7) (7) Thus, the compilation of an assignment x := y for integer variables x and y is given by the following instruction sequence Compute L value of x Compute R value of y stoi Here, we are not concerned with the problem of how a Pascal program is analysed syntactically, but how its syntactic structure is determined. This is discussed in Chapter 8 on syntax analysis. Similarly, we also assume that the input program has already been checked for 'type correctness'. Chapter 9 on semantic analysis explains how this is done. The conditions in code definitions are only used to determine the correct type of the parameters for the instructions to be generated. As a second parameter, the code functions use a function p which assigns an address in STORE to all declared variables. As we shall see later, this address is a relative address; that is, it is a constant difference between two absolute addresses in STORE, namely the actual address of the location of this variable and the start address of the memory area for all the variables and parameters of the procedure in which the variable is declared. For the moment, we may suppose that p(x) is the address of x relative to the start of STORE. Remark Of course, we could compile the occurrence of a variable identifier x in an expression with a single instruction, namely Ido T p(x). We have refrained from doing this in order to achieve consistency with the subsequently extended code scheme for variables. 2.4 Conditional and iterative statements, sequences of statements 13 Table 2.3 The compilation of assignments. Function codeg(e\ — ex) p = codeR e\ p; codeR e2 p\ equ 7" codeR(ei^e2) p = codeR e\ p\ codeR e2 p; neq T code/t(ei + e2) p = codeR e\ p\ codeR ez p; add N codeR{e\ — e2) p = codeR e\ p; codeR e% p; subN codeRifi\ * e2) p = codeR e\ p; codeR e2 p; mul N codeR{e\let) p = codeR e\ p; codeR e2 p; divN codeR (—e)p = codeR e p; neg N codeR x p = codei x p; ind T codeR cp = ldc Tc codeix := e) p = codei x p; codeR e p; sto T codet x p = ldc a p(x) Condition Type(ei) = Type(e2) = 7' Type(ei) = Type(e2) = r Type(ei) = Type(e2) = // Type(ei) = Type(e2)=Ar Type(ei) = Type(e2) = W Type(ei) = Type(e2)=JV Type(e) = JV x variable identifier of typeT c constant of type T x variable identifier x variable identifier Example 2.1 Suppose we are given a program with three integer variables, a, b, c. The memory allocation function p maps a, b, c onto the addresses 5,6 and 7. Then the assignment a := (b + (b * c)) is compiled as follows: code(a := (b+(b* c))) p = codeL a p; codeR(b + (b* c)) p; sto i = ldc a 5; codeR(b + (b* c)) p; sto i = ldc a 5; codeR(b) p; codeR(b * c) p; add i; sto i = ldc a 5; ldc a 6; ind i; codeR(b * c) p; add i; sto i = ldc a 5; ldc a 6; ind i; codeR(b) p; codeR(c) p; mul i; add i; sto i = ldc a S; ldc a 6; ind i; ldc a 6; ind i; codeRic) p; mul i; add i; sto i = ldc a S; ldc a 6; ind i; ldc a 6; ind i; ldc a 7; ind i; mul i; add i; sto i □ 2.4 Conditional and iterative statements, sequences of statements We now turn to the compilation of conditional and iterative statements. We give compilation schemes for the bidirectional and unidirectional if statements, if e then sti else st2 ft" and if e then st fi, and for the while and repeat loops, while e do st od and repeat st until e.

14 Compilation of imperative programming languages Table 2.4 Conditional and unconditional branch. Instr. ujp? Qp? Meaning PC:=q HSTORE[SP]=fabe then PC :=g fl SP:=SP-l Comments Unconditional branch Conditional branch Cond. q € [0,codemax] (b) q 6 [0,codemax] Result The syntax is slightly modified from Pascal to achieve unambiguous parsing of the if statement and to eliminate the begin-end bracketing. We use a new tool in the compilation scheme for the code function defined here. We label instructions and the end of the scheme with names which we use in branch instructions. This insertion of a label as the object of a branch instruction may be explained as follows: we insert the address that the instruction with this label receives or has received. Of course, a code scheme can be applied several times or even recursively when compiling a Pascal program. However, it is clear how the definition of a label and its use in a branch instruction correspond on each occasion. So that the control flow described in the statements discussed here can be implemented on the P machine, the latter has conditional and unconditional branches. These are described in Table 2.4. We can now describe the code function for conditional statements and loops. codeQS e then st\ else st2 fl) p = codeR e p; fjp h; code sti p; ujp h; h: code stz p; h- After evaluation of the condition e, the code for sti is executed if the value is true; otherwise, a branch to the code for sf2 takes place, skipping the code for st \ and the unconditional branch. The unidirectional conditional statement is compiled as follows: code(if e then stS) p = codeR e p; fjp /; code st p;l: . The instruction sequences for both types of conditional statement may be illustrated graphically as shown in Figure 2.2. The two iterative statements are compiled as follows: code (while e do st od) p = l\\ codeR e p; fjp h; code st p; ujp h; h: code (repeat st until e) p = l: code st p; codeR e p; fjp I The generation schemes for these two types of loop are illustrated in Figure 2.3. 2.4 Conditional and iterative statements, sequences of statements 15 codeR{e) fjp —] code{st{) UJP code(st2) codeR(e) «P code(sf) (a) (b) Figure 2.2 Instruction sequences for conditional statements, (a) Bidirectional, (b) unidirectional. code(e) «P code(st) «JP code(st) code(e) Qp (a) (b) Figure 2.3 Code generation for loops, (a) while e do st do and (b) repeat st until e. Example 2.2 Suppose once again that p[a) = 5, p(b) = 6 and p{c) = 7. Compile the statement if a > b then c := a else c := b fi as in Figure 2.4(a) and the loop while a > b do c := c + 1; a := a — bod as in Figure 2.4(b). □ The compilation scheme for a sequence of consecutive statements is very simple: code {st\\st2) p - code st\ p; code sti p

16 Compilation of imperative programming languages ldc ind ldc ind grt fJP ldc ldc ind ldc add sto ldc ldc ind ldc ind sub sto UJP a5 <-i i a6 i i 1 a7 a7 i il i i a5 a5 i a6 i i i ldc ind ldc ind grt a5 i a6 i i «P ldc ldc ind sto a7 a5 i i UJP ldc ldc ind sto a7 a6 «j i 1 i (a) (b) Figure 2.4 Compilation of (a) a bidirectional conditional statement and (b) a while loop. Let us consider a case statement which is simplified in comparison with Pascal. Only selectors between 0 and a constant k which is obvious from the program are allowed. Components for all selectors 0, 1 k are present and these are arranged in increasing order. Thus, case statements have the following form: case e of 0: st0; 1: sh ; k: stk ; end One method of compiling case statements uses an indexed branch, in other words, a branch in which the given target address is increased by a value defined immediately beforehand. The ixj instruction in the P machine (see Table 2.5) adds the value in the highest stack location to the target address. 2.4 Conditional and iterative statements, sequences of statements 17 Table 2.5 Indexed branch. Instr. ixj? Meaning PC:=STORE[SP]+q; SP:=SP-l Cond. (0 Result codes eP nega code sto P ujp code st\ p ujp code stk P ujp ujp ujp ujp leaves the value of the selector on the top of the stack indexed branch to the end of the branching table branch to the end of the statement branching table Figure 2.5 Code generation for a case statement. Figure 2.5 illustrates the instruction sequences generated for case statements. Note that in this scheme the value of the selector expression is negated. In the ixj instruction this negative value is added to the address q of the last unconditional branch in the branch table. Thus, the branches in the branch table are arranged in the reverse order to the components. The last branch leads to the address of the instruction sequence for sto, the first to that for stk. This permits a recursive specification of the compilation (see Exercise 5).

18 Compilation of imperative programming languages 2.5 Memory allocation for variables of simple type In this section we introduce a number of very important concepts in compiler design, namely the concepts of compile time and run time, and static and dynamic information. At compile time a given Pascal program is compiled into a P program. At run time this P program is executed with input data. All information about a Pascal program that is available from this program alone or can be computed or generated from available information at compile time is said to be static. All information that only becomes available at run time when the corresponding P program is executed with input data is said to be dynamic. We have already met a number of examples of static and dynamic information about Pascal programs. For example, the target addresses of conditional and unconditional branches are static because they are ultimately computed from the source program using the code function. This is true as a whole for a P program generated from a Pascal program; thus, the latter is also static. Dynamic information includes the values of variables and of expressions in which variables occur. These variables generally depend on program input values, which are only available at run time. Because the values of the conditions in statements are dynamic, the nature of control flow after the evaluation of the condition is also dynamic. Before we can assign variables declared in the source program to memory locations, we need to make a number of assumptions about the number of memory locations and our generosity with memory. To each variable of the simple types integer, real, character and bool and of the enumeration or set type and to each pointer variable we shall assign one memory location to hold its value. Thus, unlike in real compilers, we make no attempt to pack more than one 'small value' (for example, Boolean values or characters) into a single word. We also temporarily ignore the fact that mathematicians, physicists and engineers often wish to carry out highly accurate calculations with real numbers with long mantissas. Thus, for the time being, we can only compile programs in which the accuracy is limited by the word length of the P machine. However, this word length is not specified. As a minimum, the word length should be such that a single word may contain Boolean values, characters from a sufficiently large alphabet and, above all, a single instruction. We then have a very simple memory allocation scheme. The variables in the declaration part of the program (we are currently still considering programs without blocks or procedures) are assigned consecutive addresses from the start of the stack memory, according to the order in which they occur. For reasons which will become clear later, the first address assigned is not 0 but 5. For reasons which will also become clear when we consider procedures and blocks, we shall call the addresses assigned relative addresses. The (actual) absolute address 5 is therefore defined to be the address 5 relative to the base 0. The function that records the assignment of variables to relative addresses is p : Var -*■ INo- Let us consider the variable declaration part of a Pascal program, where the types that occur are all simple; that is, 2.6 Memory allocation for arrays 19 varni :*i;...;nk :tk; The memory allocation strategy outlined above would then define the function p as follows: pint) = i'+4 fori <i <k It is easy to see that the relative addresses assigned are static quantities, since they are derived (in a very simple way) from the source program, namely from the positions of the variables in the variable declaration part. Of course, these addresses lie within the range of the memory we have reserved for the P machine stack. When procedures and functions are involved, it becomes clear that we are talking about two nested stacks, namely a 'large' stack consisting of the data areas of all currently active procedures, which grows when a procedure is entered and shrinks when a procedure is exited, and a 'small' stack for every active procedure which holds interim results determined during the processing of statements in the body. Up to now, we have only met the latter, for example in the processing of assignments. The assignment of memory locations and/or addresses to declared variables defines the structure of the data area. 2.6 Memory allocation for arrays First, we consider the case of static arrays, as in the original Pascal; we shall then consider dynamic arrays as in Algol 60 and ISO Pascal. 2.6.1 Static arrays ^ How many memory locations will an arrajjuTbccupy if it is declared as follows? var a: array[—5..5.1..9] of integer According to our previous assumptions, every component of the array occupies one location. Clearly, there are 99 components a[-5,l],fl[-5,2],...,a[-5,9], a[-4,l],a[-4,2] a[-4,9], ar5,l],a[5,2],...,a[5,9], which we shall store consecutively in the memory in this order. This allocation scheme is known as row-major ordering. It is intuitively described by the principle that 'the order of the array components in the memory is such that the last index varies most quickly'. Here is a precise definition. Suppose that a ^-dimensional array is defined by the declaration:

20 Compilation of imperative programming languages \arb: array[«i..oi,..., «*..£>*] of integer («;, o-, integer constants) Then the array components b[h ij,Oj+u.... Oi] and b[ix ij+l, uj+i uk] are immediately adjacent in memory if Uj < ij <Oj. In the above declaration of the array b, the array components occupy nLi(°i ~~ "i + !) locations in the order b[ui,...,uk], fc[«i,...,iii_i,«t + l]. ...fc[«i,,..,«i_i,ojfc], b[u\ k*_i + 1,«t], b[ui,....Uk-i + 1,ut + 1],...b[u\ Uk-i + 1,o*], Moi.---.ot_i.Ui], b[oi,...,Ok-i,Uk + l], ...b[oi,...,Ok-i,ok] We again record the first memory location occupied by the array using the function p. Of course, we now have a somewhat more complicated allocation strategy. We introduce a function size : Type -> IN, which specifies the size of an object of the given type, in other words, the number of memory locations occupied by the variables of this type. According to the above, we have size(t) = 1 for types integer, real, char, bool pointer, and enumeration and set types. size(t) = nf=i (Pi - «,■ + 1) for the type of the array b declared above. Then, for a variable declaration part varni :ti;n2 : h; ...;nmtm; the function p is given by i-l p(m) = 5 + "Y^sizeitj) for 1 < i < m ;=i At this point, it should be clear to the reader that in the previous case of static arrays discussed above, the quantities k,u\,u2,.,.,Uk,01,02,...,Ok, and therefore also the functions size and p which depend on these, are known at compile time; in other words, they are read or computed from a given Pascal program. Correspondingly, in order to store, for example, the value 0 in the first location of the above array a we could generate the instruction sequence ldc a p(a)\ ldc i 0; sto i; where p(a) is an address which is known at compile time. 2.6 Memory, allocation for arrays 21 However, it becomes interesting when, for example, we have to compile the assignment a[i, j] := 0 in which i and j are integer variables that only acquire their values at the time the compiled program is executed. In this case we have to generate instructions that load the current values i and j off and /' using the addresses p(i) and p(j) and then compute the following expression: (7-(-5))*(9-l + l)+7-l = (7 + 5)*9 + 7-l When added to the initial address p(a), this value gives the address of the location a[7, J]. Thus, in this process we encounter the compile-time quantities —5,1 and 9, the bounds of the array a, and its start address, p{a), together with the execution- time quantities i and 7, the values of i and j at the time the instruction sequence for the Pascal statement a[i, j] := 0 is executed. Let us consider our general array declaration var b: array [111...01, «2-"2. • • •, «t-ot] of integer Let d; = oi — u; + 1 for 1 < i < k denote the ranges of the array b in the individual dimensions. How do we determine the relative address of die component of b denoted by b[i\, i%,..., <t] relative to the start address of i? We again let 77,..., ik denote the current values of ii,..., i* at execution time for the corresponding statement. According to our arrangement of the array components in memory, the value of Oi — «i) * «'ze(array[M2"02, • • •, «t-ot] of integer) brings us to the start of the (k — l)-dimensional subarray in which the addressed component lies. Adding ('2 - "2) * «'ze(array[M3..03 Uk-Ok] of integer) leads us to the start of the correct (k — 2)-dimensional subarray, and so on. Thus, the expression r — {i\_ — u\) * «ze(array[«2-02. • • •. "k-oki of integer) + (12 — U2) * size(array[u3..03,..., Uk..Ok] of integer) + (ik-i — Uk-\) * size(array[uk..Ok] of integer) + (ik ~ uk) computes the desired address relative to the start of the array. If we substitute the values of the size expressions (known at compile time), we obtain: r = (ii—u\)*d2*di*...*dk + (i2 — U2)*d-}*d4*...*dk + ... + (77C7 - t<t-i) *dk + (h- uk)

22 Compilation of imperative programming languages Table 2.6 Computation of indexed address. STORE[SP-l] contains a 'start address'. STORE[SP] contains the index of the selected subarray and q contains the size of the subarray. Instr. ixaq Meaning STORE[SP -1] := STORE[SP -1] + STORE[SP] *q SP:=SP-l Cond. (a,i) Results (a) Multiplying this out and splitting it into ij and «,- expressions, we have r = (ii * da * ds... * d* + i% * dz * d\ * ... * dk . + --- + k^i*dk + h) —(«i * di * d-i * ... * dk + u% * d} * d\ * ... * dk +... + «fc_l * <4 + u*) (2.1) We see that the second part of this expression contains only quantities that are known at compile time. Thus, the compiler can evaluate this expression to a constant d. We can also simplify the first part of the expression. Because the ranges are known in the case of static arrays, we can evaluate all the products of ranges at compile time. This only leaves a sum of the form h = Y%=\ i] • dy), where tey+1 We now generalize the address computation one last time before giving the compilation scheme for addressing the components of arrays. Our declaration for the array b specified the component type as integer. Thus, the storage requirement was one memory location per component. Let us now consider arbitrary component types (including non-simple components) t with a known storage requirement of size(t) locations; in this case, the array c with the declaration var c: array [«i..oi, U2..02, ■■•, «t-ojt] off requires di**g storage locations where g stands for size(f). The relative address of the array component c[h,..., i*], again relative to the start of the array, is then h*g — d*g where, in our case of static arrays, the term d * g can again be computed by the compiler. Table 2.6 gives a P machine instruction which can be used to move gradually through increasingly lower-dimensioned subarrays. Here, the parameter q can be used for the factors g ■ d^. 2.6 Memory allocation for arrays 23 Table 2.7 Incrementing and decrementing are defined in Pascal for all types that have a succ function. Instr. incTtf decTtf Meaning STORE[SP] := STORE[SP] +q STORE[SP] := STORE[SP] -q Cond. (7) and type (q) = i (7) and type (q) = i Result (7) (7) In addition, we require other instructions for arithmetic on addresses. These include increment and decrement instructions (see Table 2.7). To compile the index sequence, we use a function coder, whose second parameter is the component size. The compilation scheme for computing the address of the array component c[»i. • • ■. «*] with component size g and start address p(c) is codeL c[i\,... it] p = Idc a p{c); codej [ii,..., i*] g p codei [«i,..., ik] g p = codeR h p; ixa g ■ dm; codeR 12 p; ixa g • d<2); codeRkp; ix&g-d(k); dec a g • d; However, this compilation scheme has the same disadvantage as the scheme described earlier for the case statement; namely, there is no check to verify that the values of the index expressions ij,..., ik lie within the allowed bounds. We shall now change this. The chk instruction given in Table 2.8 checks whether the computed index value lies within the bounds. The improved compilation scheme is then code/ [i\,...,ik\arr p = codeR t'i p; chk u\ oy, ixa g -d(1); codeR i-2 p; chk 112 02; ixa g • d(2); codeR it p; chk «* o*; ixa g ■ </(t); dec a g ■ d\ wherearr = (g; uuolt ...,«„,o„). Table 2.8 Check whether the highest stack value lies between p and q, inclusive. Halt with error message if not. Instr.' chk pq Meaning if (STOREISP] < p) or (STOREtfP] > q) then emvOvalue out of range') Cond. (i) Result (i)

24 Compilation of imperative programming languages Example 2.3 Suppose we have the declarations var i, j: integer; a: array[-5..5,1..9] of integer then p(i) = 5, p(J) = 6 and p(a) = 7 and for the array a, we have the ranges d\ = 11, d2 = 9, the component size g = 1 and d = -44. The compilation of a[i + 1, j] := 0 is then given by: code(a[i + l,j]:=0)p = idc a 7 ldc a 6 ldc a 5 ind i ind i chk 1 9 ldc i 1 ixa 1 add i dec a - 44 chk - 5 5 ldc i 0 ixa 9 sto i a In this section, we have shown how static arrays may be implemented. Here is a summary of the features. The bounds, the ranges, the component sizes and the relative address of each array are known at compile time. All expressions (for example, in indexing) that consist of these alone can be evaluated by the compiler. The results become operands of the instructions generated. Each array is stored together with the other declared variables. The relative address assigned to an array is the relative address of its first location. 2.6.2 Dynamic arrays The ISO standard for Pascal eliminates some of the design faults in the original language, in that it allows arrays as formal parameters which adjust their size to that of the actual parameter. For a given procedure declaration procedure p (value a: array[«i..Oi,..., «*..»*] of type) the bounds for a are only determined when the procedure p is called. A similar thing holds for a declaration var a: array[Hi..oi,...,K*..o*] of type, when not all the «, and o, are constant, but are global variables or formal parameters of the procedure. In both cases, a is a dynamic array; its bounds, the ranges in the individual dimensions, and thus its size, are dynamic. Only the dimension itself remains static. Thus, neither the previous allocation scheme nor the component addressing can be used. We shall therefore treat these aspects afresh for the case of dynamic arrays. The storage of dynamic arrays in memory causes problems, because as soon as there are two such arrays a static assignment of start addresses is no longer possible. Because the storage space required by an array is only known when the procedure is entered, memory reservation can only take place at that time. As we shall see later in our discussion of procedures, dynamic arrays are stored in the dynamic part of the procedure space, after the static part. 2.6 Memory allocation for arrays 25 How can we generate instruction sequences for component addressing or at least to determine the start address? Even if we do not know the start address, we can still determine statically where it will be stored at run time. For this we use an array descriptor to which we assign a static start address and a size. Its size depends only on the dimensions of the array. Its first location is used for the start address of the array, which is stored there when the array is created, in other words, when the procedure is entered and the array declaration is processed. The remaining structure will become apparent. Let us again turn to the problem of generating instruction sequences to address the array component b[i\,...,it], but now in a dynamic array b: array[u\..o\,...,uic..oic] of integer. The variables u\,...,Uk,o\,...,Ok only acquire their values at run time. Let us again consider the formula for computing the relative address of b[i\,..., i*] in Equation (2.1) on page 22. Except for k, the dimension of the array, all the quantities in (2.1) are now dynamic. Thus, we have to compute their values at run time and statically provide space for them. However, there is a difference between i'i, ..., i* and u\,...,ut,di,...,dt. The values of i\,...,ik depend on the particular indexing of the array, while the values of u i,..., u/c and d%,..., dk are defined once for the whole lifetime of the array. In the case of a formal dynamic array parameter the values of u\ Uk, di,..., dk are retrieved from the actual parameter when the parameters are passed. In the case of a declared dynamic array, the values of the bounds and of d%,..., dk are computed once when the array is created. The whole of the second part of Equation (2.1), namely («i * d% * dj * ... * dk + ...), gives the same value d however the array is indexed, and this is therefore passed with the parameters or computed once when the array is created. For each form of indexing, to save ourselves from having to subtract d ■ g every time, we subtract d ■ g immediately from the start address of the array and store the result, the adjusted start address, in the array descriptor instead of the actual start address. Now, in order to address the component b[i\,..., it], we need only add the value ofh-g, where h = i\*d2*di*.. .*dk+i2*d3*d4*.. .*dk+.. .+ik-i*dt+Tk, to this adjusted start address. To save multiplications we compute this expression using a Horner scheme h = (... ((h * d2 + h) * d3 +13") * d4 +...) * dk + 4 For the evaluation, we must be able to access the values of dt. Thus, we provide room for these in the array descriptor, which now has the structure shown in Figure 2.6. The second and third locations are needed for copying arrays. The contents of the third location are used to compute the adjusted start address of the copy. The values of the upper and lower bounds are required for the test to ensure that the range bounds are not violated. For indexing in dynamic arrays we use two new code functions codeu and codeu. Here, codeu only generates an ldc instruction which loads the address of the array descriptor at the top of the stack. The code generated by codeu duplicates this address, uses the upper duplicate to load the adjusted start address (with an

26 Compilation of imperative programming languages Address 0 1 2 3 4 2ifc + l 2k + 2 2fc + 3 3fc+l Adjusted start address: a Array size: i Subtract for adjusted start address: i ova «*a Ok A d2'.i dkX Figure 2.6 Array descriptor for the fc-dimensional array b. The address in the left column is given relative to the start. indirection) and accesses the remainder of the array descriptor indirectly using the lower duplicate. The lower duplicate is no longer required once the address has been computed and is therefore removed from the stack and replaced by the resulting address. We could still address the individual locations of the array descriptor of an array b statically using p(b) + j; however, later, we would have to give another coding scheme for when this is no longer the case. codeLdb[ii,...,ik]p=: ldc a p(b); codeu[ii ik]g P code,d[iu...,ik]g p = dpi a; inda; ldc i 0; code/t ii p; add i; ldd Ik + 3; mul i; codeR 12 P\ add i; ldd Ik + 4; mul i; codeg ik-\ p; add i; ldd 3Jfc -4-1; mul i; codeR ik p\ add i; ixag slia descriptor address (static) component size g duplicate highest stack entry adjusted start address 2.7 Memory allocation for records 27 Table 2.9 Instructions for dynamic arrays. Instr. dpir ldd q slir2 Meaning SP:=SP+l; STORE[SP):- STORE[SP-l] SP:=SP+1; STOREISP) := STORElSTOREiiSP -3] +q] STORE[SP -1] := STORE[SP]; SP:=SP-l Cond. (7) (a,r!,r2) m,r2j Result (T,T) (a,ri,r2,i) (72) The new instructions dpi, ldd and sli are defined in Table 2.9. dpi copies the highest stack entry, ldd accesses descriptor arrays indirectly and sli moves the highest stack entry to the second highest position. The general case of dynamic arrays of an arbitrary (including dynamic) type will be handled in an exercise, as will the necessary introduction of the range check. 2.7 Memory allocation for records We shall now discuss the problem of memory allocation and addressing for records. Our records are simplified in comparison with Pascal records, in that we do not allow variants and also require that the names of record components should not be multiply declared, for instance outside the record type. This means that we can also use our function p for names of records and their components. Suppose, for example, that the record variable v is declared as var v. record a: integer; b : booi end Then we assign the address of the first free memory location to the variable v according to the previous strategy and relative addresses within the record (0 and 1, here) to the component names (for reasons which will become clear in the next section). Thus, if the above declaration follows the declarations var i, j: integer, we have p(i) = 5, p(J) = 6, p(v) = 7, p(a) = 0 and p(b) = 1. The computation of the relative addresses of record components uses the size function in a similar way to the computation of relative addresses in declaration parts. In general, for a record declaration var v: record c\ : ti\ ci: tt\...; c* : tk end, we have

28 Compilation of imperative programming languages i-l j=i The size of the record variable v is determined inductively from the sizes of the components k size(v) = ]pM'ze(f;) ;=i Note that these sizes are static in Pascal; that is, they are known at compile time. Thus, using what we learnt in the last section, we can now handle an array of records and generate instruction sequences to compute the start address of a component in such an array. Conversely, let us suppose that a record component is a dynamic array. Here too, we wish to keep the static addressing of all record components. We again achieve this by storing only the array descriptor in the record, rather than the array itself. The addressing of record components involves the following steps: • loading the start address of the record; • increasing the address by the relative address of the component. Thus, we obtain the address, which is a usable L value. If we require the value of the (simple) component, we must load it (indirectly) using the address. If the component addressed is itself a record or an array, another record component or array component can be selected based on the computed address. To increase an address by a relative address we use the inc instruction given in Table 2.7. The following P instruction sequence is generated to address the component c,- in the record v. ldc a p(v); inc a p(c,) 2.8 Pointers and dynamic memory allocation Pointers and the dynamic memory occupancy of anonymous objects are two closely related concepts in imperative programming languages. So far, we have only considered memory allocation for objects introduced by a declaration. A name for the object is given in the declaration and a static (relative) address is assigned to this name. If a programming language includes pointers, these may be used to access nameless objects; pointers may be used to implement dynamically growing and shrinking chained structures, where the individual objects are not defined by a declaration but created by executing a suitable statement, such as the Pascal new statement. The semantics of both Pascal and C are not very precise as far as the lifetime of dynamically created objects is concerned. Of course, the implementation of a programming language may release the memory occupied by such an object 2.8 Pointers and dynamic memory allocation 29 before the end of its lifetime without violating the semantics, provided it is certain that the running program can no longer access the object. The process of releasing memory occupied by unreachable objects is called garbage collection. As previously mentioned, when a procedure is entered, a data area for all its local storage requirements (and for organizational purposes) is created in the lower part of the data memory; this area is released when the procedure is exited. This stack-like memory allocation and release is not matched to the lifetime of dynamically created objects; garbage collection will generally not release memory in a stack-like manner or synchronously with exits from procedures. Thus, dynamically created objects are allocated space in a storage area called a heap at the higher end of the memory. The heap grows downwards towards the stack as objects are dynamically created. A new register in the P machine, NP (new pointer), points to the lowest occupied location in the heap. Thus, the memory of the P machine has the following form: Stack T SP Heap NP maxstr A new object is created in the heap using the P instruction new (see Table 2.10 and Figure 2.7). This expects the size of the object to be created to be at the top of the stack, with the address of the pointer to the future object below it. The start address of the new object is stored indirectly in the pointer using this address. When the new lower end of the heap is computed, a check is made to determine whether the stack and the heap would collide. This uses the EP (extreme stack pointer) register. As we shall see in the next section, this register points to Table 2.10 The new instruction. Instr. new Meaning if NP - STORE[SP] < EP then erroK'store overflow') else NP := NP - STORE[SP}; STORE[STORE[SP - 1]] := NP; SP :=SP-2 fi; Cond. (a4) Result

30 Compilation of imperative programming languages STORE STORE SP SP NP NP- < after before Figure 2.7 The effect of the new instruction in the P machine. the highest stack location to which SP can point when evaluating expressions in the statement part. As Exercise 3 is intended to show, the maximum number of stack locations needed to evaluate any given expression can be precomputed at compile time. Thus, EP can be increased by this static quantity whenever a procedure is entered, after the necessary dynamic arrays have been created. The check to determine whether the stack extension would collide with the heap should only take place on entry to a procedure; otherwise, this test would have to be repeated whenever SP was increased. Using the EP register in this way is clearly more efficient. We can now describe the compilation of a Pascal new statement into P machine code, essentially into a P new instruction. code(newO)) = ldc a p(x); Idc i «ze(t); new if x is a variable of type f t The ind instruction is again used for dereferencing, in other words, to 2.8 Pointers and dynamic memory allocation 31 address an object via a pointer to it. To conclude the last three sections, we consider the problem of address computation for variable denotations with an arbitrarily complicated structure; in other words, variable denotations containing an arbitrary number of indexes, selections and dereferences in an arbitrary order. Thus, this involves the compilation of words such as x f [i + 1, j].a f [i] f and y.a.b.c f [»', j + l]-d. For this, we introduce a number of new cases of the recursive code function, which compile address modifications, in other words, indexes, selections and dereferences. We note that the function codeu has two arguments; in addition to the list of index expressions it also includes the (static) array-component size. The compilation scheme given below decomposes composite variable denotations from left to right; it picks the variable name first, followed by any subsequent selections, dereferences and indexes. codeiXxr) p = ldc a p(x); for name x codeM(r) p codeM(-xr) p = inc a p(x); for name x codeM(r) p codenii^ r) p = ind a; codeM(r) p codeiu(U]r) p = codeu [«'] g P\ where g is the component size codeu (r) P of the indexed array codeu (e) — £ The following assertion holds for this code function. Let us assume that the prefix « of a composite term u v is compiled into an instruction sequence b; codei (uv)p = h; codetfvp. The execution of b then computes: • the address of an array descriptor into the highest stack location, if v begins with an index, or • the start address of the variables denoted by u into the highest stack location, otherwise. Example 2.4 Suppose we have the following declaration. type t = record a: array[-5.. + 5,1 ..9] of integer b: f t end; var i,j : integer; pt : f r, Assuming that p(i) = 5, p(j) = 6 and p(pi) = 7, the variable denotation pt f .b f .a[i + 1, j] is compiled as follows:

ion of imperative programming languages ldc a 7; Load address of pt ind a; Load start address of record inc a 99; Compute start address of record component b ind a; Dereference pointer inc a 0; Start address of component a codeuli + 1, j] 1 p; As in Example 2.3 D This completes our discussion of memory allocation for records and the addressing of record components. Note that the compilation scheme given here only yields correct instruction sequences for correctly composed variable denotations. It does not include the verification of context conditions, for example that x in x f is also a pointer variable, that x in x[i\,..., i*] is a fc-dimensional array, or that x in x.a is a record variable with a component with name a. 2.9 Procedures In preparation for the compilation of procedures, we shall now briefly discuss the associated concepts, terms and problems. A procedure declaration consists of • a name under which it may be called, • the specification of the formal parameters which form the input/output interface, • a sequence of (local) declarations, and • a statement part, the body. If it is a function procedure, the result type must also be given. Procedures are called (that is to say, activated) when an occurrence of their name in the statement part of the main program or a procedure is processed. A called procedure can in turn call another procedure or even itself. When the statement part of a procedure has been processed in full, the procedure is exited and its caller (in other words, the procedure that activated it) continues the execution following the call. The chains of procedure calls that arise during the execution of a program form an ordered tree, the calling tree for the program execution. The root of the calling tree is labelled with the name of the main program. Every internal node of the calling tree is labelled with a procedure name p (more precisely, with one of possibly several defining occurrences of p), its immediate predecessor is labelled with the name of the procedure that executed this call to p, and its immediate successors form a list of procedures ordered in the sequence in which they are called by p. The 2.9 Procedures 33 program h; var i: integer; procp procr if i > 0 theni := i — \\p elser r fi T:= 2; p; P end. Figure 2.8 A program and its calling tree. The brackets mark the declaration part and the statement part of the procedure. label p may occur several times in the calling tree; more precisely, it occurs exactly as often as p is called during the processing of the program. Every occurrence of p is called an incarnation of p. It is characterized by the path from the root of the tree (which corresponds to the main program) to the particular node. This path is called the incarnation path for this incarnation of p. Let us consider the state of the program execution when a particular incarnation of p is active. According to the above, all ancestors of this incarnation, in other words, all nodes on the incarnation path, have already been called but not yet exited, or, in the case of the main program, started but not yet ended. All these incarnations are said to be live at this point in time. Example 2.5 Figure 2.8 shows a program and its calling tree. The arrow points to an incarnation of r, which is reached after the first three recursive calls to p. At this time, the main program h, three incarnations of p and one incarnation of r are live. It should be stressed here that: • a program may have more than one calling tree • there may be infinitely many calling trees. □

34 Compilation of imperative programming languages Let us now consider the names that occur in procedures. The names introduced as formal parameters or by local declarations are called local names (in the section on functional languages, they are referred to as bound names). When a procedure is called, new incarnations are created for all local names. At the same time, according to the specification or declaration, space for simple variables, arrays and records is reserved and, in the case of parameters, allocated in accordance with the actual parameters. The lifetime of the incarnations created in this way is equal to the lifetime of the procedure incarnation; in other words, the space they occupy can be released when the procedure is exited (in this introduction, we ignore local variables that, because of an additional specification (own in Algol 60, STATIC in PL/I and in C), outlive their procedure incarnations). It is easy to see that this can be implemented using a stack-like memory management. When a procedure is entered, memory for the formal parameters, the locally declared variables and possible intermediate results (see Figure 2.10) is reserved; this memory is released when the procedure is exited. We shall discuss the details later. The treatment of applied occurrences of non-local names (these are referred to as free occurrences of names in functional programs) is not quite so straightforward. Names that are global to the procedure in question are called global names. The visibility and/or scoping rules of a programming language specify how to find the defining occurrence of a name corresponding to an applied occurrence of that name. The converse, but equivalent, approach begins with a defining occurrence of a name and specifies the program segment in which all occurrences of the name relate to this defining occurrence. The following scoping rule is familiar from Algol-like languages. A defining occurrence of a name is valid throughout the program unit whose declaration or specification part includes the definition, except in any program units properly contained in this program unit that contain a new definition of the name. Here, a 'program unit' means a procedure and/or a block. Based on this scoping rule, we shall discuss these two approaches in further detail. If we search for the defining occurrence corresponding to an applied occurrence, we clearly find it if we begin our search in the declaration part of the program unit in which the applied occurrence occurs. A declaration or specification there is the object of our search. If there is no such declaration or specification, we continue our search in the immediately surrounding program unit, and so on. If there is no defining occurrence in all the surrounding program units, including the main program, there is a programming error. The alternative approach, beginning with a defining occurrence, sweeps over the containing program unit and associates this defining occurrence with all applied occurrences of the name found. The sweeping process is blocked on the boundaries of all program units containing a new definition of the same name. These concepts are considered in more detail in Chapter 9 on semantic analysis. Example 2.6 Figure 2.9 shows a program with several nested procedures together with the relationship between applied and defining occurrences of variables. □ 2.9 Procedures 35 proc p(a) var b; var c proc q vara vara procr varfc a — b - 9 - proc s vara a L_ q a — _T] Figure 2.9 The arrows point from applied occurrences to the associated defining occurrences. This scoping rule is used to derive the so-called static binding, in which global names in a procedure are associated with defining occurrences in the surrounding (textual) procedures. This association is static, since it relates only to the program text and not to a (dynamic) execution of the program. Whenever the global name is used, an incarnation of the statically associated defining occurrence is accessed at execution time. This contrasts with dynamic binding (static binding is principally used in Algol-like languages; some LISP dialects have a static binding, others a dynamic binding) in which an access to a global name accesses the most recently created incarnation of this name, irrespective of the procedure in which its defining occurrence occurred.

36 Compilation of imperative programming languages Example 2.7 var x procp ~ proc q I- varx L p x q p (1) Call to p (from outside p). For static and dynamic binding the applied occurrence of x refers to the external declaration. (2) Call to p (in q). For static binding the applied occurrence of x refers to the external declaration of x; for dynamic binding, it refers to the declaration of x in q. It involves the most recently created incarnation of x. O The difference between static and dynamic binding can be clearly illustrated using the calling tree. Let us consider an incarnation of a procedure p which accesses a global variable x. In the case of dynamic binding, the current incarnation path is traced backwards from the active incarnation until the first incarnation of a procedure containing a declaration of x is found. In the case of static binding, we look for the most recent incarnation of a procedure containing the innermost p that contains a definition of x. Any earlier incarnations of x on the incarnation path must be skipped over. It is easy to see that while the calling tree reflects the calling relationship between procedures, it is not well suited to efficient searches for the right incarnation of a global variable. A more detailed consideration shows that, as far as access to global variables is concerned, the following unique tree, called the tree of static predecessors, may be assigned to each incarnation path. The immediate predecessor of a node (a procedure incarnation) in this tree is the last incarnation of the immediately surrounding procedure created before this. Let us consider a path from an incarnation of p to the root in this tree of static predecessors. The right incarnations of global variables for this p all lie in an incarnation on this path. Example 2.8 The incarnation path in Figure 2.8 h-p~p~p-r has the static predecessor tree: h /l\ P P P I r 2.9 Procedures 37 All accesses to global variables in all incarnations of p lead to the main program. Only accesses from r lead to the corresponding incarnation of p. D 2.9.1 Memory organization for procedures Let us again be clear that: • all incarnations of procedures (and the main program) that are live at a given time form the current incarnation path, • when a procedure is exited, a step is taken from the current incarnation to its parent in the calling tree, and • all variables reachable from the current incarnation lie in ancestors of the current incarnation in the tree of static predecessors for the current incarnation path. At any given time, the memory organization described below, the so-called runtime stack, contains a sequence of storage areas for the set of living incarnations, in the same order in which these occur on the incarnation path. So that the procedures can be exited efficiently, the dynamic predecessors are linked together. So that global variables can be accessed efficiently, the static predecessors are linked together from the inside out. Thus, the runtime stack contains both the current incarnation path and the current tree of static predecessors. As a minimum, this supports exiting from procedures and access to global variables. In addition to these two pointer locations, there are also other organizational cells. A stack frame is therefore created in the memory of the P machine for a calling procedure (or an incarnation); the structure of this stack frame is shown in Figure 2.10. The components of a stack frame and their use are described below. function value Static! link SL Dyn. link DL valu4 of EP return address RA parameters (static)l local variables (static) MP organizational cells static part data area arrays and array params. (dyn.) ■ dyn. - local stack for intermed. results (occupied) t t SP EP Figure 2.10 The highest stack frame.

38 Compilation of imperative programming languages • A location for the result, in the case of a function procedure. Here, we assume that, as in Pascal, the results of function procedures can only be of simple type. • A location, SL, for a pointer to the stack frame of the static predecessor, in other words, the immediate predecessor in the tree of static predecessors. This is the start of the chain via which we can access the right incarnations . of all global variables. In what follows we shall refer to this pointer as the static link. • A location, DL, for a pointer to the stack frame of the dynamic predecessor, namely, the program unit that activated the current program unit. This is the start of the current incarnation path on which all living incarnations lie. This pointer is now called the dynamic link. Looked at in another way, this location contains the current state of the MP register, so that the latter can be restored later. • A location to record the state of EP so that this can be restored later on return from a called procedure to the current procedure. • The return address, RA, for the calling program unit, in other words, the address of the next instruction in the code memory, at which execution will be continued when the called procedure is exited. We refer to these five locations as the organizational cells, because they ensure that the procedure entry and exit code and global accesses run correctly. These organizational cells form the start of the data area for the incarnation. This also contains: • Space for the values, addresses and descriptors of the actual parameters; • Space for the local variables of the procedure, and • Space for dynamic arrays. It is clear from what was said in Sections 2.5 to 2.7 that, in addition to dynamic arrays, all local variables and parameters of Pascal procedures have static sizes. Together with the organizational cells, they form the static part of the data area for the procedure. From Section 2.6, we also know that in the case of dynamic arrays and array parameters passed by value, a copy must be created in the data area, and the space requirement of the copy is determined dynamically. Thus, the static part of the data area is followed by a dynamic part in which dynamic arrays and array parameters passed by value are stored. Their size is determined when the procedure is entered or when the actual parameters are passed. The static area contains the descriptors of these arrays. Finally, we have • The local stack, which is the stack we met in Section 2.3 when evaluating expressions. As can be seen, its maximum length can also be determined statically (see Exercise 3). 2.9 Procedures 39 We already know something about the registers MP, SP and EP. • MP (mark pointer) points to the start of the stack frame of the current incarnation. The organizational cells, the locations for the parameters and the local variables are addressed relative to MP. • SP points to the highest occupied location in the local stack. In the case of an empty local stack, SP points to the last location of the data area. • EP points to the highest location occupied throughout the execution of the procedure as a whole. EP is used to determine possible collisions between the stack and the heap. Thus, the test for collisions between the stack and the heap does not have to be carried out every time SP is increased. Let us suppose that the stack of die P machine is occupied by such stack frames during the execution of a program and that the pointer chains are set as described above. Then the dynamic chain links the stack frames of the incarnations on the current incarnation path. The static links form the tree of static predecessors belonging to the incarnation path. Example 2.9 Let us consider the program in Figure 2.11(a) after the second (recursive) call of s. At that point the stack has the form shown in Figure 2.11(b). DL pointers are shown to the left of the stack frames and SL pointers to the right. The tree of static predecessors is shown in Figure 2.11(c). D 2.9.2 Addressing of variables In languages that, like Pascal, have nested scopes and permit the dynamic creation of new incarnations of names local to procedures, variable names can no longer be assigned static absolute storage addresses. In general, different incarnations of a name will occupy different memory locations. As described in the previous section, a stack frame is established for each procedure incarnation. All quantities stored in the static part of the stack frame are assigned a static relative address relative to the start of the stack frame. Thus, all incarnations of these quantities have the same relative addresses within the stack frames, but not necessarily the same absolute addresses in STORE. The relative addresses are assigned as described in the preceding section. Thus, access to a local variable can be implemented if there exist instructions that fetch the start address of the current stack frame from the MP register and add it to the static relative address of the variable. These are the instructions lod, Ida and str, to be introduced later. We shall now discuss the addressing of global variables. For this, we define the concept of the nesting depth (nd) of a program construct. The nesting depth of the main program is 0. The nesting depth of a defining (applied) occurrence of a name in the declaration or specification (statement) part of a program unit with nesting depth n is n + 1.

40 Compilation of imperative programming languages program h; varx procp proc# procr vary procs x + y q s 1_ p (a) 1 * X I—a. 1 =» y i—> i—* ■—> y Q 0 p r s 9 ZZ1 r s 6— «S ■e—i <—| 1 —J DL SL (b) P A r q (c) Figure 2.11 (a) A program, (b) a stack configuration and (c) the associated tree of static predecessors. Example 2.10 The nesting depths in Figure 2.11 are: Defining occurrence P 1 q 2 r 2 s 3 Applied occurrence P 1 q 4 r (in />) 2 r (in #) 3 s 3 2.9 Procedures Non-local variables are addressed from a procedure incarnation using the pointer to the static predecessor of the incarnation. We assume the following assertion holds (ISL): ISL In every frame created in the stack for the incarnation of a procedure p, the static link points to the stack frame of the correct incarnation of the program unit immediately surrounding p. In programs without formal procedures, in other words, with procedures as parameters, this is the youngest living incarnation of the program unit immediately surrounding p. This is not necessarily the case in programs with procedures. D Let us now consider two different classes of non-local names, variable names and procedure names. To access non-local variables, in other words, to calculate their address, we use the assertion (ISL); to call a procedure (including a non-local procedure), we also use (ISL) to generate the condition of assertion (ISL) for the stack frame to be created. Let us consider access to the non-local names x and y from the procedure s in Figure 2.11. Let us suppose that the defining occurrence of x in the main program is visible there. According to the above definition, its nesting depth is 1. The nesting depth of the applied occurrences of x and y in s is 4. In Figure 2.11, it is clear that the stack frame of the main program which contains x is reached by following the static links three times. The correct incarnation of y from procedure r is reached by following this pointer once; the difference between the nesting depths of the applied and defining occurrences is 1. In fact, if we can guarantee (ISL), then it follows by induction that: An access from a nesting depth n to a defining occurrence at nesting depth m, where m < n, involves following the static links (n — m) times to reach the stack frame containing the correct incarnation of the name. The (static) relative address must then be added to its start address to obtain the address of the global variable. Read and write access and address computation for global variables are implemented using new P instructions which are defined in Table 2.11. Accesses to local variables are also covered, by the special case p = 0. Let us now consider how we may guarantee the condition of the assertion (ISL) when executing a procedure call. If a procedure q is declared at nesting depth n, it can be called: (1) in the statement part of the program unit p immediately surrounding it; this would be at nesting depth n; (2) in procedures whose declarations (arbitrarily deeply nested) are surrounded by p if p is not hidden by a declaration. These calls are at a nesting depth greater than or equal to n. Figure 2.12 shows examples of these situations. In each case, p is the calling procedure and q the called procedure. Let d be the difference between the nesting

42 Compilation of imperative programming languages Table 2.11 Loading and storing for a given difference in nesting depths p and a given relative address q. lod loads values, Ida loads addresses. base(p,a) = if p = 0 then a else base(p - 1, STORE[a + 1]). Instr. lodTpq ldapg strTpq Meaning S/>:=SP+1; STOREISP] := STORE[base(p, MP) +q] SP:=SP+l; STORE[SP] := base(p, MP) +q STORE[base(p, MP) +q] := STORE[SP]; SP:-SP-1 procp procq [ MP- SP- (a) procr procp 1 procij c pre [ MP- SP- d = \ (b) procr procg procp 1 P 1 MP SP c 1 d = 2 (c) \4 Figure 2.12 Three different call and stack situations. In each case, the current call is marked by the arrow. The dotted line shows the new static link to be set. * = static link. 2.9 Procedures 43 depths of the call and the declaration of the procedure. Let us consider the situation in which procedure q is called in procedure p so that the difference in the nesting depths d is greater than or equal to 1 (in other words, we temporarily exclude case (a) of Figure 2.12). The desired static predecessor of q is of course a direct or indirect static predecessor of p and is therefore reachable via the chain of static links. How far do we have to go along this chain, beginning with the pointer in the stack frame of ql It is easy to see that we have to follow the pointers d times. In case (a) of Figure 2.12, we have d = 0. In fact, in this case, we do not need to follow the static link in p, since the static link in the stack frame of q must point to the stack frame of p. In particular, this last case ensures that the condition of the assertion (ISL) can be satisfied when procedures are called in the statement part of the main program. These calls can only involve procedures declared in the main program. For these, the static link must point to the stack frame of the main program. The MP register points to this. The difference between the nesting depths of call ^declaration is 0. Thus, there is no need to follow a static link. In fact no such pointer exists. Thus, it should be intuitively clear how access to global names, whether procedure or variable names, is implemented. Access to global variables is formally described in Section 2.9.6, and the setting of the pointer to the static predecessor on procedure entry in Section 2.9.4. 2.9.3 Computation of the address environments In Section 2.5, we described how the names defined in a declaration part can be assigned to memory locations and addresses. Since at that point we were only considering programs with one declaration part and one statement part (that is, without procedures), the problem of global variables did not arise. The address environment p computed in a declaration part assigned names to (relative) addresses. We shall now extend p and its computation in two directions: For each defining occurrence of a variable name, in addition to a relative address, p must also contain its nesting depth, for, as we saw in the previous section, the addressing of global variables requires precisely these two pieces of information. What should p bind a procedure name to? Naturally, procedure names should be bound to everything we need to compile procedure calls. As in the case of variable names, this includes the nesting depth of the procedure declaration. In addition, the compiler has to generate the branch to the start of the compilation of the procedure; therefore, p binds each procedure name to a symbolic label, whose value will be the start address of the procedure code. Thus, for address environments such as p we introduce the domain AddrJinv = Name -» Addr x ST where Addr = N and ST = N Here, variable names are bound to relative addresses in the stack frame and procedure names are bound to CODE addresses.

44 Compilation of imperative programming languages The nature of the computation of p must ensure that at every application point p has a precise knowledge o£ the names visible there. We can achieve this when processing the declaration part of a procedure by overwriting those entries in the external p that are hidden by a new declaration. However, outside the procedure, we must continue with the external p. The functions elabspecs, elab.vdecls and elabjdecls which are now defined recursively decompose specification lists of formal parameters and variable and procedure declaration parts. Thus, based on an external address environment p, they construct the local address environment for the statement part of the procedure. If they encounter a new declaration of a known name, they overwrite its entry in the address environment by the new entry. Thus, the external name is hidden. The function /': A -*■ B, which takes the value b e B at a e A and otherwise agrees with the function / : A -*■ B, is denoted by f[b/a]. elabspecs takes a list of parameter specifications, an address environment, a relative address which is the next to be assigned and a nesting depth and produces a new address environment and the relative address of the next free location after the space for the formal parameters. Thus, the functionality of elabspecs is given by: elabspecs : Spec* x AddrJEnv x Addr x 57* -*■ AddrJLnv x Addr elabspecs (var x: t; specs) pnjast- elabspecs specs p[(nui, st)/x](nM + 1) st elabspecs (value x: array[wi..oi,..., uk..Ok\ of t'; specs) p nui st = elabspecs specs p'(nja + 3k + 2) st where p' = p[(rua,st)/x][(n-a+2i + l, st)/ui]^1[(nM+2i+2,st)/oi}^1 elabspecs (value x: t; specs) ptuist = elabspecs specs p[(nM, st)/x\(nji + size(t)) st for static types t elabspecs () p rua st = (p, hm) For var parameters (reference parameters) a location is reserved in which the caller stores the pointer to the current parameter. For ^-dimensional value array parameters, a descriptor consisting of 3k+2 locations is provided. This contains the start address, the array size, the subtrahend for calculating the adjusted start address, the lower and upper limits (for range checking) and the ranges. We note how the formal bounds «i,..., uk, o\,..., ok of the formal value array parameter are bound to their corresponding positions in the descriptor. The second case of the static value parameters covers the other cases. The last case concerns exhausted specification lists. The definition of the function elab.vdecls follows. This looks after memory allocation for variable declarations. Here, we must distinguish between static and dynamic objects. The first three cases handle the declaration of static variables. The addressing of record components will be taken from Section 2.7. The functionality of elab.vdecls is given by: elab-vdecls : Vdecl* x Addr Jim x Addr x ST -+ AddrMnv x Addr 2.9 Procedures 45 elab.vdecls (var x :t; vdecls) p rua st = for non-array types t elab.vdecls vdecls p[ (n_a, st)/x ] (n_a + size(t)) st elab.vdecls (var x : array[ui..oi,..., uk..Ok\ of t; vdecls) p hm st = elab.vdecls vdecls p[(«-fl, st)/x] x (riM + 3k + 2 + f[(oi - ui + 1) • size(t)) st Space for Space for the the descnptor array components if* is a static array. elab.vdecls () p nji st = (p,riM) This is the memory allocation for local variables previously described in Section 2.9.2. Only the storage of arrays has changed. A descriptor is created for each array, because it could occur as the actual parameter of a procedure. In this case, we require the information contained in the descriptor. For static arrays, the descriptor and the array are stored consecutively. The start address of the array and the limits and ranges are entered in the descriptor using an instruction sequence. The generation of this instruction sequence is left as an exercise. In the case of dynamic arrays, only the descriptor has a static length. It is stored in the static part of the stack frame. The array name is bound to the start address of the descriptor. When the procedure is entered an instruction sequence is executed which stores the array itself in the dynamic part of the stack frame and sets up the entries in the descriptor. The function elabjpdecls processes procedure declaration parts. elabjpdecls : Pdecf x Addr^nv x ST -*■ AddrJEnv x Code elab4>decls ( proc p\ (...);...; proc pk(...);...;)pst = (p', h : code (procp^...);...) p' st + 1; lk : code (procpA(...);...) p' st + 1) where p' = p[(/i, st) /px (h,si)/pk] The function elab^decls has a functionality we have not yet encountered; it generates both an address environment and the code of the procedure declaration part. The latter may contain simultaneously recursive procedures, provided that forward declarations as in Pascal are not required; in that case the compiler encounters procedure names it does not yet know and has to generate subprogram branches to addresses that are not yet specified. We help ourselves again by introducing symbolic labels for the compilation of procedures, binding the procedure names to these

Compilation of imperative programming languages and compiling the procedures in this environment (the same 'circular-environment' technique is also used in functional languages to implement simultaneous recursion, see Chapter 3). Note that all the procedures are compiled in the same address environment. The address environments computed inside the procedures are not used outside the procedures. 2.9.4 Entering and exiting procedures Let us now consider some important actions in the implementation of procedures, namely the call and thus the entry to the procedure and the exit from the procedure after its body has been executed. Let us first consider the procedure call. Suppose that p is the currently active procedure. Its stack frame is the highest in the stack. Suppose that the pointers in the stack frame are correctly set, in other words, the static link points to the correct incarnation of the procedure immediately surrounding p, and the dynamic link points to the incarnation from which p was called. Now suppose that p calls a procedure What actions must be executed in order that the processing of q may begin? (1) The static link must be set to point to the frame of the correct incarnation of the procedure immediately surrounding q. (2) The dynamic link must be set to point to the start of the frame for p. (3) The current state of the EP register must be saved. (4) The values and addresses of the actual parameters must be determined and stored. In particular, descriptors must be stored for formal value array descriptors. The copies of the associated actual parameters are created later (we delay our discussion of the passing of parameters slightly). (5) The MP register must be increased so that it points to the start of the new stack frame. (6) The return address must be stored. (7) A branch to the first instruction in the code of q must be executed. (8) SP must point to the upper end of the area occupied by the static parameters and local variables. (9) The copies of the actual value array parameters must be created. Here, the size of each such parameter is computed using its descriptor and the SP register is increased by this quantity. (10) EP must be set to take into account the space requirement for the local stack. A check for collision of the stack and heap is made here. Actions (1) to (3) are usually executed using the mst instruction. Of course, parameter evaluation is carried out by the caller, because the actual parameters must be evaluated in the environment of the call. Actions (5) to (7) are carried out using 2.9 Procedures Table 2.12 Instructions for calling and entering procedures, mst (mark stack), cup (call user procedure), ssp (set stack pointer) and sep (set extreme stack pointer). base(p, a) = if p = 0 then a else base(p - 1, STORE[a +1]) fi. Instr. mst p cup p q ssp p sep p Meaning STORE[SP +2] := base(p,MP); STORE[SP+3]:=MP; STORE[SP+4]:=EP; SP:=SP+5 MP:= SP -(p + 4); STORE[MP+4]:=PC; PC:=q SP:=MP+p-\ EP := SP +p; if EP>NP then error('store overflow') fi Comments Static link Dynamic link Save EP The parameters can now be evaluated starting from STORE[SP+l] p is the storage requirement for the parameters Save return address Branch to procedure start address q p size of static part of data area p max. depth of local stack Check for collision of stack and heap the cup instruction, which is also executed by the caller. Then the called procedure begins its work. It executes action (8) using the ssp (set stack pointer) instruction, executes action (9) using an initialization sequence which we shall discuss later, and executes action (10) (to increase EP) using the instruction sep (set extreme stack pointer). The instructions used are listed in Table 2.12. Remark: In the original P machine, which only supported static arrays, actions (8) and (10) were executed together using the ent instruction. The copying of static value array parameters was executed later. ent/?g SP:=MP+q-l EP:=SP+p iSEP>NP then errori'store overflow') fi q data-area size p max. depth of local stack Collision of stack and heap

48 Compilation of imperative programming languages Table 2.13 Return from function procedures and proper procedures. Instr. retf retp Meaning SP:~MP; PC := STOREIMP +4]; EP := STORE[MP +3]; itEP>NP then error('store overflow') fl MP: STOREIMP +2] SP:=MP-\\ PC := STOREIMP +4]; EP:= STOREIMP +3]; if£/>>iV/> then error('store overflow') fi Atf>:=SrOi?E[M/>+2] Comments Function result in Return branch Restore fi0 Dynamic link Proper procedure Return branch Restore EP Dynamic link the local stack with no results When the body of a procedure or function has been executed in full, the corresponding stack frame must be released and