One register of the object program is reserved to address 'PERM'. This is a small collection of assembly code routines provided to carry out basic services for the object program, e.g. dynamic array declaration. A checked program requires some 25 routines (3660 bytes)—an optimised program only six routines (1560 bytes). The main constituent of PERM is a large table of multiples of 4096 which are required to overcome the addressing limitation of System 360/System 4 architecture. This addressing limitation also requires that a routine's stack frame may have to be divided into two parts. The first part, restricted to 4096 bytes in length, contains scalar variables and pointers to elements in the second part. The second part contains strings, records and arrays. If any arrays have dynamic bounds, the size of the second part of the frame will not be known until run time. Frequently the size of the first part is substantially less than 4096 bytes, in which case strings, records and any arrays with constant bounds are transferred from part 2 to part 1 to utilise the balance of the space and obviate the inefficiencies caused by the use of pointers. The pre-declared routines are divided into two groups. The 'intrinsic' routines are sufficiently trivial for in-line code to be generated. The remainder are provided by external routines and functions written in IMP. When a pre-declared name is first referenced, the compiler generates the appropriate linkage data to enable the routine to be included at program load time. A systematic change of name is required to avoid confusion between pre-declared routines and user written external routines. This arrangement has the considerable advantage of enabling much of the language support software to be written in IMP and thus to be available to all the IMP compilers. It also avoids including unwanted material with system programs. Compiler structure The internal structure of the compiler is a field of very limited interest. Some features of more general interest are described below. The compiler is a normal IMP program obtaining its input via the read symbol routine and outputting a program listing and error messages via the print symbol routine. The compiler hands its binary in small chunks to a routine provided at compiler load time. This routine constructs the output file. By varying the binary output routine, the output can be an EMAS file, binary cards or a file for some other operating regime. In particular, an output routine exists which puts the code directly into core and executes it—giving a 'student crunching' system using the standard shared compiler. This arrangement is not the most efficient imaginable, but it does have the attraction that the compiler can be operated in any (sufficiently large) machine possessing an IMP system and opens the door to a variety of bootstrapping techniques. The compiling technique is one-pass, multiphase: Phase 1 Input of the source program and construction of the listing. Phase 2 Syntactical Analysis using a table-driven variation of the method of recursive descent. The syntax tables are generated automatically. This phase also includes all the dictionary building. Phase 3 Compilation proper—the following subphases are applied as necessary: 3a Generation of an internal representation of all assignments, expressions and jumps. 3b Examination of the internal form for machine-independent optimisations. 3c Examination of the internal form for shortcuts in the object code (Object machine dependent). 3d Allocation of registers (Object machine dependent). PROGRAM 1 2 3 Source file (statements) 3839 261 261 Object code (bytes) 34944 4616 11008 Total cpu time (seconds) 80-15 8-777 8-101 Total no. of page turns* 2205 607 634 Break down per Phases Phase 1 percentages of total cpu 17-38 15-11 16-37 " " p turns 33-06 58-12 55-68 Phase 2 " cpu 31-03 21-02 20-37 " " p turns 11-93 2-80 2-68 Phase 3 " cpu 50-80 61-54 62-33 " " p turns 48-66 22-90 10-78 Phase 4 " cpu 0-79 2-34 9-13 " " p turns 6-35 16-14 28-86 Program 1 is the principal component of the current EMAS supervisor (optimised compilation) Program 2 is a matrix program—predominantly performing real arithmetic on two dimensional arrays (optimised compilation) Program 3 is program 2—checked compilation. *The EMAS supervisor charges for a page turn whenever it brings a page into core on behalf of a process. Currently the charge is equivalent to 0-003 seconds of cpu time. 3e Generation of the binary (Object machine dependent). Phase 4 Synthesis of the object program from small pieces of binary. Phase 1 is applied to the source program, a line at a time; the other phases, a statement at a time. Table 1 gives the CPU times spent in each phase for two sample programs. Every effort has been made to isolate those parts of the compiler which are dependent on the characteristics of the target machine. It is distressing how large phase 3c has to be to utilise fully the 360 order code, in particular the store-to-store and store-immediate instructions. The compiler makes no attempt to improve the paging characteristics of the object program in spite of work done at Edinburgh showing how effective rearrangement can be (Pavelin, 1970). However, unnecessary branching is avoided, and in-line code preferred to subroutines except for the following operations: Initialisation (execution of the first begin) Termination Execution of a fault statement Dynamic array declarations (actually two subroutines) String Resolution In-line code is produced for exponentiation, string concatenation and fix/float operations. Optimisation techniques In optimising a source program, the 'window' technique is used: Phases 1 and 2 are allowed to run ahead of Phase 3 and a cyclic buffer is used to store up to 15 analysed statements. When elementary examination discovers a group of statements that must be executed in sequence, Phase 3 is applied to the group of statements. This technique is adequate to permit optimisation of most loops as can be seen from Appendix 2. When designing the optimisation, the (highly dubious?) assumption was made that experienced system programmers would code to a high standard. The compiler makes no attempt