Commit | Line | Data |
---|---|---|
95f51977 C |
1 | .\" @(#)porttour1.ms 6.3 (Berkeley) 5/30/86 |
2 | .\" | |
3 | .ds f \fIf77\fP | |
4 | .ds U \s-2UNIX\s0 | |
5 | .ds V \s-2VAX\s0 | |
6 | .de Bl | |
7 | .na | |
8 | .fi | |
9 | .ll 3i | |
10 | .. | |
11 | .de Sp | |
12 | .sp 0.25v | |
13 | .. | |
c9528a00 C |
14 | .TL |
15 | A Tour Through the Portable C Compiler | |
16 | .AU | |
17 | S. C. Johnson | |
18 | .AI | |
95f51977 C |
19 | AT&T Bell Laboratories |
20 | .sp | |
21 | .AU | |
22 | Donn Seeley | |
23 | .AI | |
24 | Department of Computer Science | |
25 | University of Utah | |
26 | .AB | |
27 | .OH 'A Tour Through the Portable C Compiler''SMM:19-%' | |
28 | .EH 'SMM:19-%''A Tour Through the Portable C Compiler' | |
29 | .PP | |
30 | Since its introduction, | |
31 | the Portable C Compiler has become the standard | |
32 | \*U C compiler for many machines. | |
33 | Three quarters or more of the code | |
34 | in the compiler is machine independent | |
35 | and much of the rest can be generated easily | |
36 | using knowledge of the target architecture. | |
37 | This paper describes the structure | |
38 | and organization of the compiler | |
39 | and tries to further simplify the job | |
40 | of the compiler porter. | |
41 | .PP | |
42 | This document originally appeared with the Seventh Edition of \*U, | |
43 | and has been revised and extended for publication | |
44 | with the Fourth Berkeley Software Distribution. | |
45 | The new material covers changes which | |
46 | have been made in the compiler since the Seventh Edition, | |
47 | and includes some discussion of secondary topics | |
48 | which were thought to be of interest | |
49 | in future ports of the compiler. | |
50 | .sp | |
51 | .LP | |
52 | Revised April, 1986 | |
53 | .AE | |
c9528a00 C |
54 | .SH |
55 | Introduction | |
56 | .PP | |
57 | A C compiler has been implemented that has proved to be quite portable, | |
58 | serving as the basis for C compilers on roughly a dozen machines, including | |
95f51977 | 59 | the DEC \*V, Honeywell 6000, IBM 370, and Interdata 8/32. |
c9528a00 C |
60 | The compiler is highly compatible with the C language standard. |
61 | .[ | |
62 | Kernighan Ritchie Prentice 1978 | |
63 | .] | |
64 | .PP | |
65 | Among the goals of this compiler are portability, high reliability, | |
66 | and the use of state-of-the-art techniques and tools wherever practical. | |
67 | Although the efficiency of the compiling process is not | |
68 | a primary goal, the compiler is efficient enough, and produces | |
69 | good enough code, to serve as a production compiler. | |
70 | .PP | |
71 | The language implemented is highly compatible with the current PDP-11 version of C. | |
72 | Moreover, roughly 75% of the compiler, including | |
73 | nearly all the syntactic and semantic routines, is machine independent. | |
74 | The compiler also serves as the major portion of the program | |
75 | .I lint , | |
76 | described elsewhere. | |
77 | .[ | |
78 | Johnson Lint Program Checker | |
79 | .] | |
80 | .PP | |
81 | A number of earlier attempts to make portable compilers are worth noting. | |
82 | While on CO-OP assignment to Bell Labs in 1973, Alan Snyder wrote a portable C | |
83 | compiler which was the basis of his Master's Thesis at M.I.T. | |
84 | .[ | |
85 | Snyder Portable C Compiler | |
86 | .] | |
87 | This compiler was very slow and complicated, and contained a number of rather | |
88 | serious implementation difficulties; | |
89 | nevertheless, a number of Snyder's ideas appear in this work. | |
90 | .PP | |
91 | Most earlier portable compilers, including Snyder's, have proceeded by | |
92 | defining an intermediate language, perhaps based | |
93 | on three-address code or code for a stack machine, | |
94 | and writing a machine independent program to | |
95 | translate from the source code to this | |
96 | intermediate code. | |
97 | The intermediate code is then read by a second pass, and interpreted or compiled. | |
98 | This approach is elegant, and has a number of advantages, especially if the | |
99 | target machine is far removed from the host. | |
100 | It suffers from some disadvantages as well. | |
101 | Some constructions, like initialization and subroutine prologs, | |
102 | are difficult or expensive to express in a | |
103 | machine independent way that still allows them | |
104 | to be easily adapted to the target assemblers. | |
105 | Most of these approaches require a symbol table to be constructed | |
106 | in the second (machine dependent) pass, and/or | |
107 | require powerful target assemblers. | |
108 | Also, many conversion operators may be generated | |
109 | that have no effect on a given machine, | |
110 | but may be needed on others (for example, pointer to pointer | |
111 | conversions usually do nothing in C, but must be generated because | |
112 | there are some machines where they are significant). | |
113 | .PP | |
114 | For these reasons, the first pass of the portable compiler | |
115 | is not entirely machine independent. | |
116 | It contains some machine dependent features, such as initialization, subroutine | |
117 | prolog and epilog, certain storage allocation functions, | |
118 | code for the | |
119 | .I switch | |
120 | statement, and code to throw out unneeded conversion operators. | |
121 | .PP | |
122 | As a crude measure of the degree of | |
123 | portability actually achieved, | |
124 | the Interdata 8/32 C compiler has | |
125 | roughly 600 machine dependent lines of source out of 4600 in Pass 1, and 1000 | |
126 | out of 3400 in Pass 2. | |
127 | In total, 1600 out of 8000, or 20%, | |
128 | of the total source is machine dependent | |
129 | (12% in Pass 1, 30% in Pass 2). | |
130 | These percentages can be expected to rise slightly as the | |
131 | compiler is tuned. | |
132 | The percentage of machine-dependent code for the IBM is 22%, for | |
133 | the Honeywell 25%. | |
134 | If the assembler format and structure were the same for all | |
135 | these machines, perhaps another 5-10% of the code | |
136 | would become machine independent. | |
137 | .PP | |
138 | These figures are sufficiently misleading as to be almost | |
139 | meaningless. | |
140 | A large fraction of the machine dependent code can be converted | |
141 | in a straightforward, almost mechanical way. | |
95f51977 | 142 | On the other hand, a certain amount of the code requires hard |
c9528a00 C |
143 | intellectual effort to convert, since the algorithms |
144 | embodied in this part of the code are typically complicated | |
145 | and machine dependent. | |
146 | .PP | |
147 | To summarize, however, if you need a C compiler written for a machine with | |
148 | a reasonable architecture, the compiler is already three quarters finished! | |
149 | .SH | |
150 | Overview | |
151 | .PP | |
152 | This paper discusses the structure and organization of the portable compiler. | |
153 | The intent is to give the big picture, rather than discussing the details of a particular machine | |
154 | implementation. | |
155 | After a brief overview and a discussion of the source file structure, | |
156 | the paper describes the major data structures, and then delves more | |
157 | closely into the two passes. | |
158 | Some of the theoretical work on which the compiler is based, and | |
159 | its application to the compiler, is discussed elsewhere. | |
160 | .[ | |
161 | johnson portable theory practice | |
162 | .] | |
163 | One of the major design issues in any C compiler, the design of | |
164 | the calling sequence and stack frame, is the subject of a separate | |
165 | memorandum. | |
166 | .[ | |
167 | johnson lesk ritchie calling sequence | |
168 | .] | |
169 | .PP | |
170 | The compiler consists of two passes, | |
171 | .I pass1 | |
172 | and | |
173 | .I pass2 , | |
174 | that together turn C source code into assembler code for the target | |
175 | machine. | |
176 | The two passes are preceded by a preprocessor, that | |
177 | handles the | |
178 | .B "#define" | |
179 | and | |
180 | .B "#include" | |
181 | statements, and related features (e.g., | |
182 | .B #ifdef , | |
183 | etc.). | |
95f51977 C |
184 | The two passes may optionally be followed by |
185 | a machine dependent code improver. | |
c9528a00 C |
186 | .PP |
187 | The output of the preprocessor is a text file that is read as the standard | |
188 | input of the first pass. | |
189 | This | |
190 | produces as standard output another text file that becomes the standard | |
191 | input of the second pass. | |
192 | The second pass produces, as standard output, the desired assembler language source code. | |
95f51977 C |
193 | The code improver, if used, converts the assembler code |
194 | to more effective code, | |
195 | and the result is passed to the assembler. | |
c9528a00 C |
196 | The preprocessor and the two passes |
197 | all write error messages on the standard error file. | |
198 | Thus the compiler itself makes few demands on the I/O | |
199 | library support, aiding in the bootstrapping process. | |
200 | .PP | |
95f51977 C |
201 | The division of the compiler into two passes is somewhat artificial. |
202 | The compiler can optionally be loaded | |
c9528a00 C |
203 | so that both passes operate in the same program. |
204 | This ``one pass'' operation eliminates the overhead of | |
205 | reading and writing the intermediate file, so the compiler | |
206 | operates about 30% faster in this mode. | |
207 | It also occupies about 30% more space than the larger | |
208 | of the two component passes. | |
95f51977 C |
209 | This ``one pass'' compiler is the standard version |
210 | on machines with large address spaces, such as the \*V. | |
c9528a00 C |
211 | .PP |
212 | Because the compiler is fundamentally structured as two | |
213 | passes, even when loaded as one, this document primarily | |
214 | describes the two pass version. | |
215 | .PP | |
216 | The first pass does the lexical analysis, parsing, and | |
217 | symbol table maintenance. | |
218 | It also constructs parse trees for expressions, | |
219 | and keeps track of the types of the nodes in these trees. | |
220 | Additional code is devoted to initialization. | |
221 | Machine dependent portions of the first pass serve to | |
222 | generate subroutine prologs and epilogs, | |
223 | code for switches, and code for branches, label definitions, | |
224 | alignment operations, | |
225 | changes of location counter, etc. | |
226 | .PP | |
227 | The intermediate file is a text file organized into lines. | |
228 | Lines beginning with a right parenthesis are copied by the second | |
229 | pass directly to its output file, with the | |
230 | parenthesis stripped off. | |
231 | Thus, when the first pass produces assembly code, such as subroutine prologs, | |
232 | etc., each line is prefaced with a right parenthesis; | |
233 | the second pass passes these lines to through to the assembler. | |
234 | .PP | |
235 | The major job done by the second pass is generation of code | |
236 | for expressions. | |
237 | The expression parse trees produced in the first pass are | |
238 | written onto the | |
239 | intermediate file in Polish Prefix form: | |
240 | first, there is a line beginning with a period, followed by the source | |
241 | file line number and name on which the expression appeared (for debugging purposes). | |
242 | The successive lines represent the nodes of the parse tree, | |
243 | one node per line. | |
244 | Each line contains the node number, type, and | |
245 | any values (e.g., values of constants) | |
246 | that may appear in the node. | |
247 | Lines representing nodes with descendants are immediately | |
248 | followed by the left subtree of descendants, then the | |
249 | right. | |
250 | Since the number of descendants of any node is completely | |
251 | determined by the node number, there is no need to mark the end | |
252 | of the tree. | |
253 | .PP | |
254 | There are only two other line types in the intermediate file. | |
255 | Lines beginning with a left square bracket (`[') represent the beginning of | |
256 | blocks (delimited by { ... } in the C source); | |
257 | lines beginning with right square brackets (`]') represent the end of blocks. | |
258 | The remainder of these lines tell how much | |
259 | stack space, and how many register variables, | |
260 | are currently in use. | |
261 | .PP | |
262 | Thus, the second pass reads the intermediate files, copies the `)' lines, | |
263 | makes note of the information in the `[' and `]' lines, | |
264 | and devotes most of its effort to the | |
265 | `.' lines and their associated expression trees, turning them | |
266 | turns into assembly code to evaluate the expressions. | |
267 | .PP | |
268 | In the one pass version of the compiler, the expression | |
95f51977 | 269 | trees contain information useful to both logical passes. |
c9528a00 C |
270 | Instead of writing the trees onto an intermediate file, |
271 | each tree is transformed in place into an acceptable | |
272 | form for the code generator. | |
273 | The code generator then writes the result of compiling | |
274 | this tree onto the standard output. | |
275 | Instead of `[' and `]' lines in the intermediate file, the information is passed | |
276 | directly to the second pass routines. | |
277 | Assembly code produced by the first pass is simply written out, | |
95f51977 | 278 | without the need for `)' at the head of each line. |
c9528a00 C |
279 | .SH |
280 | The Source Files | |
281 | .PP | |
95f51977 C |
282 | The compiler source consists of 25 source files. |
283 | Several header files contain information | |
284 | which is needed across various source modules. | |
285 | .I Manifest.h | |
286 | has declarations for node types, type manipulation | |
287 | macros and other macros, and some global data definitions. | |
288 | .I Macdefs.h | |
c9528a00 C |
289 | has machine-dependent definitions, such as the size and alignment of the |
290 | various data representations. | |
95f51977 C |
291 | .I Config.h |
292 | defines symbols which control the configuration of the compiler, | |
293 | including such things as the sizes of various tables | |
294 | and whether the compiler is ``one pass''. | |
295 | The compiler conditionally includes another file, | |
296 | .I onepass.h , | |
297 | which contains definitions which are particular to | |
298 | a ``one pass'' compiler. | |
299 | .I Ndu.h | |
300 | defines the basic tree building structure | |
301 | which is used throughout the compiler | |
302 | to construct expression trees. | |
303 | .I Manifest.h | |
304 | includes a file of opcode and type definitions named | |
305 | .I pcclocal.h ; | |
306 | this file is automatically generated from | |
307 | a header file specific to the C compiler named | |
308 | .I localdefs.h | |
309 | and a public header file | |
310 | .I /usr/include/pcc.h . | |
311 | Another file, | |
312 | .I pcctokens , | |
313 | is generated in a similar way | |
314 | and contains token definitions for the compiler's Yacc | |
315 | .[ | |
316 | Johnson Yacc Compiler cstr | |
317 | .] | |
318 | grammar. | |
c9528a00 | 319 | Two machine independent header files, |
95f51977 | 320 | .I pass1.h |
c9528a00 | 321 | and |
95f51977 | 322 | .I pass2.h , |
c9528a00 C |
323 | contain the data structure and manifest definitions |
324 | for the first and second passes, respectively. | |
325 | In the second pass, a machine dependent header file, | |
95f51977 | 326 | .I mac2defs.h , |
c9528a00 C |
327 | contains declarations of register names, etc. |
328 | .PP | |
95f51977 C |
329 | .I Common.c |
330 | contains machine independent routines used in both passes. | |
c9528a00 C |
331 | These include routines for allocating and freeing trees, walking over trees, |
332 | printing debugging information, and printing error messages. | |
95f51977 C |
333 | This file can be compiled in two flavors, |
334 | one for pass 1 and one for pass 2, | |
335 | depending on what conditional compilation symbol is used. | |
c9528a00 C |
336 | .PP |
337 | Entire sections of this document are devoted to the detailed structure of the | |
338 | passes. | |
339 | For the moment, we just give a brief description of the files. | |
340 | The first pass | |
341 | is obtained by compiling and loading | |
95f51977 | 342 | .I cgram.y , |
c9528a00 | 343 | .I code.c , |
95f51977 C |
344 | .I common.c , |
345 | .I local.c , | |
346 | .I optim.c , | |
347 | .I pftn.c , | |
348 | .I scan.c , | |
349 | .I stab.c , | |
350 | .I trees.c | |
c9528a00 | 351 | and |
95f51977 | 352 | .I xdefs.c . |
c9528a00 | 353 | .I Scan.c |
95f51977 C |
354 | is the lexical analyzer, which provides tokens to the |
355 | bottom-up parser which is defined by the Yacc grammar | |
c9528a00 C |
356 | .I cgram.y . |
357 | .I Xdefs.c | |
358 | is a short file of external definitions. | |
359 | .I Pftn.c | |
360 | maintains the symbol table, and does initialization. | |
361 | .I Trees.c | |
362 | builds the expression trees, and computes the node types. | |
363 | .I Optim.c | |
364 | does some machine independent optimizations on the expression trees. | |
95f51977 C |
365 | .I Common.c |
366 | contains service routines common to the two passes of the compiler. | |
c9528a00 C |
367 | All the above files are machine independent. |
368 | The files | |
369 | .I local.c | |
370 | and | |
371 | .I code.c | |
372 | contain machine dependent code for generating subroutine | |
373 | prologs, switch code, and the like. | |
95f51977 C |
374 | .I Stab.c |
375 | contains machine dependent code for | |
376 | producing external symbol table information | |
377 | which can drive a symbolic debugger. | |
c9528a00 C |
378 | .PP |
379 | The second pass | |
380 | is produced by compiling and loading | |
c9528a00 | 381 | .I allo.c , |
95f51977 C |
382 | .I common.c , |
383 | .I local2.c , | |
c9528a00 | 384 | .I match.c , |
c9528a00 | 385 | .I order.c , |
95f51977 | 386 | .I reader.c |
c9528a00 C |
387 | and |
388 | .I table.c . | |
389 | .I Reader.c | |
390 | reads the intermediate file, and controls the major logic of the | |
391 | code generation. | |
392 | .I Allo.c | |
393 | keeps track of busy and free registers. | |
394 | .I Match.c | |
395 | controls the matching | |
396 | of code templates to subtrees of the expression tree to be compiled. | |
95f51977 C |
397 | .I Common.c |
398 | defines certain service routines, | |
c9528a00 C |
399 | as in the first pass. |
400 | The above files are machine independent. | |
401 | .I Order.c | |
402 | controls the machine dependent details of the code generation strategy. | |
403 | .I Local2.c | |
404 | has many small machine dependent routines, | |
405 | and tables of opcodes, register types, etc. | |
406 | .I Table.c | |
407 | has the code template tables, | |
408 | which are also clearly machine dependent. | |
409 | .SH | |
95f51977 | 410 | Data Structure Considerations |
c9528a00 C |
411 | .PP |
412 | This section discusses the node numbers, type words, and expression trees, used | |
413 | throughout both passes of the compiler. | |
414 | .PP | |
415 | The file | |
95f51977 | 416 | .I manifest.h |
c9528a00 C |
417 | defines those symbols used throughout both passes. |
418 | The intent is to use the same symbol name (e.g., MINUS) | |
419 | for the given operator throughout the lexical analysis, parsing, tree building, | |
95f51977 C |
420 | and code generation phases. |
421 | .I Manifest.h | |
422 | obtains some of its definitions from | |
423 | two other header files, | |
424 | .I localdefs.h | |
425 | and | |
426 | .I pcc.h . | |
427 | .I Localdefs.h | |
428 | contains definitions for operator symbols | |
429 | which are specific to the C compiler. | |
430 | .I Pcc.h | |
431 | contains definitions for operators and types | |
432 | which may be used by other compilers | |
433 | to communicate with a portable code generator | |
434 | based on pass 2; | |
435 | this code generator will be described later. | |
c9528a00 C |
436 | .PP |
437 | A token | |
438 | like MINUS may be seen in the lexical analyzer before it is known | |
439 | whether it is a unary or binary operator; | |
440 | clearly, it is necessary to know this by the time the parse tree | |
441 | is constructed. | |
442 | Thus, an operator (really a macro) called | |
443 | UNARY is provided, so that MINUS | |
444 | and UNARY MINUS are both distinct node numbers. | |
445 | Similarly, many binary operators exist in an assignment form (for example, \-=), | |
446 | and the operator ASG may be applied to such node names to generate new ones, e.g. ASG MINUS. | |
447 | .PP | |
448 | It is frequently desirable to know if a node represents a leaf (no descendants), a unary operator (one | |
449 | descendant) or a binary operator (two descendants). | |
450 | The macro | |
451 | .I optype(o) | |
452 | returns one of the manifest constants LTYPE, UTYPE, or BITYPE, respectively, depending | |
453 | on the node number | |
454 | .I o . | |
455 | Similarly, | |
456 | .I asgop(o) | |
457 | returns true if | |
458 | .I o | |
459 | is an assignment operator number (=, +=, etc. ), and | |
460 | .I logop(o) | |
461 | returns true if | |
462 | .I o | |
463 | is a relational or logical (&&, \(or\(or, or !) operator. | |
464 | .PP | |
465 | C has a rich typing structure, with a potentially infinite number of types. | |
466 | To begin with, there are the basic types: CHAR, SHORT, INT, LONG, the unsigned versions | |
467 | known as | |
468 | UCHAR, USHORT, UNSIGNED, ULONG, and FLOAT, DOUBLE, | |
469 | and finally | |
470 | STRTY (a structure), UNIONTY, and ENUMTY. | |
471 | Then, there are three operators that can be applied to types to make others: | |
472 | if | |
473 | .I t | |
474 | is a type, we may potentially have types | |
475 | .I "pointer to t" , | |
476 | .I "function returning t" , | |
477 | and | |
478 | .I "array of t's" | |
479 | generated from | |
480 | .I t . | |
481 | Thus, an arbitrary type in C consists of a basic type, and zero or more of these operators. | |
482 | .PP | |
483 | In the compiler, a type is represented by an unsigned integer; the rightmost four bits hold the basic | |
484 | type, and the remaining bits are divided into two-bit fields, containing | |
485 | 0 (no operator), or one of the three operators | |
486 | described above. | |
487 | The modifiers are read right to left in the word, starting with the two-bit | |
488 | field adjacent to the basic type, until a field with 0 in it is reached. | |
489 | The macros PTR, FTN, and ARY represent the | |
490 | .I "pointer to" , | |
491 | .I "function returning" , | |
492 | and | |
493 | .I "array of" | |
494 | operators. | |
495 | The macro values are shifted so that they align with the first two-bit | |
496 | field; thus PTR+INT | |
497 | represents the type for an integer pointer, and | |
498 | .DS | |
499 | ARY + (PTR<<2) + (FTN<<4) + DOUBLE | |
500 | .DE | |
95f51977 | 501 | represents the type of an array of pointers to functions returning \fBdouble\fPs. |
c9528a00 C |
502 | .PP |
503 | The type words are ordinarily manipulated by macros. | |
504 | If | |
505 | .I t | |
506 | is a type word, | |
507 | .I BTYPE(t) | |
508 | gives the basic type. | |
509 | .I ISPTR(t) , | |
510 | .I ISARY(t) , | |
511 | and | |
512 | .I ISFTN(t) | |
513 | ask if an object of this type is a pointer, array, or a function, | |
514 | respectively. | |
515 | .I MODTYPE(t,b) | |
516 | sets the basic type of | |
517 | .I t | |
518 | to | |
519 | .I b . | |
520 | .I DECREF(t) | |
521 | gives the type resulting from removing the first operator from | |
522 | .I t . | |
523 | Thus, if | |
524 | .I t | |
525 | is a pointer to | |
95f51977 | 526 | .I t\(fm , |
c9528a00 | 527 | a function returning |
95f51977 | 528 | .I t\(fm , |
c9528a00 | 529 | or an array of |
95f51977 | 530 | .I t\(fm , |
c9528a00 C |
531 | then |
532 | .I DECREF(t) | |
533 | would equal | |
95f51977 | 534 | .I t\(fm . |
c9528a00 C |
535 | .I INCREF(t) |
536 | gives the type representing a pointer to | |
537 | .I t . | |
538 | Finally, there are operators for dealing with the unsigned types. | |
539 | .I ISUNSIGNED(t) | |
540 | returns true if | |
541 | .I t | |
542 | is one of the four basic unsigned types; | |
543 | in this case, | |
544 | .I DEUNSIGN(t) | |
545 | gives the associated `signed' type. | |
546 | Similarly, | |
547 | .I UNSIGNABLE(t) | |
548 | returns true if | |
549 | .I t | |
550 | is one of the four basic types that could become unsigned, and | |
551 | .I ENUNSIGN(t) | |
552 | returns the unsigned analogue of | |
553 | .I t | |
554 | in this case. | |
555 | .PP | |
556 | The other important global data structure is that of expression trees. | |
557 | The actual shapes of the nodes are given in | |
95f51977 C |
558 | .I ndu.h . |
559 | The information stored for each pass is not quite the same; | |
560 | in the first pass, nodes contain | |
561 | dimension and size information, while in the second pass | |
c9528a00 C |
562 | nodes contain register allocation information. |
563 | Nevertheless, all nodes contain fields called | |
564 | .I op , | |
565 | containing the node number, | |
566 | and | |
567 | .I type , | |
568 | containing the type word. | |
569 | A function called | |
570 | .I talloc() | |
571 | returns a pointer to a new tree node. | |
572 | To free a node, its | |
573 | .I op | |
574 | field need merely be set to FREE. | |
575 | The other fields in the node will remain intact at least until the next allocation. | |
576 | .PP | |
577 | Nodes representing binary operators contain fields, | |
578 | .I left | |
579 | and | |
580 | .I right , | |
581 | that contain pointers to the left and right descendants. | |
582 | Unary operator nodes have the | |
583 | .I left | |
584 | field, and a value field called | |
585 | .I rval . | |
586 | Leaf nodes, with no descendants, have two value fields: | |
587 | .I lval | |
588 | and | |
589 | .I rval . | |
590 | .PP | |
591 | At appropriate times, the function | |
592 | .I tcheck() | |
593 | can be called, to check that there are no busy nodes remaining. | |
594 | This is used as a compiler consistency check. | |
595 | The function | |
596 | .I tcopy(p) | |
597 | takes a pointer | |
598 | .I p | |
599 | that points to an expression tree, and returns a pointer | |
600 | to a disjoint copy of the tree. | |
601 | The function | |
602 | .I walkf(p,f) | |
603 | performs a postorder walk of the tree pointed to by | |
604 | .I p , | |
605 | and applies the function | |
606 | .I f | |
607 | to each node. | |
608 | The function | |
609 | .I fwalk(p,f,d) | |
610 | does a preorder walk of the tree pointed to by | |
611 | .I p . | |
612 | At each node, it calls a function | |
613 | .I f , | |
614 | passing to it the node pointer, a value passed down | |
615 | from its ancestor, and two pointers to values to be passed | |
616 | down to the left and right descendants (if any). | |
617 | The value | |
618 | .I d | |
619 | is the value passed down to the root. | |
c9528a00 C |
620 | .I Fwalk |
621 | is used for a number of tree labeling and debugging activities. | |
622 | .PP | |
623 | The other major data structure, the symbol table, exists only in pass one, | |
624 | and will be discussed later. | |
625 | .SH | |
626 | Pass One | |
627 | .PP | |
628 | The first pass does lexical analysis, parsing, symbol table maintenance, | |
629 | tree building, optimization, and a number of machine dependent things. | |
630 | This pass is largely machine independent, and the machine independent | |
631 | sections can be pretty successfully ignored. | |
632 | Thus, they will be only sketched here. | |
633 | .SH | |
634 | Lexical Analysis | |
635 | .PP | |
636 | The lexical analyzer is a conceptually simple routine that reads the input | |
637 | and returns the tokens of the C language as it encounters them: | |
638 | names, constants, operators, and keywords. | |
639 | The conceptual simplicity of this job is confounded a bit by several | |
640 | other simple jobs that unfortunately must go on simultaneously. | |
641 | These include | |
642 | .IP \(bu | |
643 | Keeping track of the current filename and line number, and occasionally | |
644 | setting this information as the result of preprocessor control lines. | |
645 | .IP \(bu | |
646 | Skipping comments. | |
647 | .IP \(bu | |
648 | Properly dealing with octal, decimal, hex, floating | |
649 | point, and character constants, as well as character strings. | |
650 | .PP | |
651 | To achieve speed, the program maintains several tables | |
652 | that are indexed into by character value, to tell | |
653 | the lexical analyzer what to do next. | |
654 | To achieve portability, these tables must be initialized | |
655 | each time the compiler is run, in order that the | |
656 | table entries reflect the local character set values. | |
657 | .SH | |
658 | Parsing | |
659 | .PP | |
95f51977 | 660 | As mentioned above, the parser is generated by Yacc from the grammar |
c9528a00 C |
661 | .I cgram.y. |
662 | The grammar is relatively readable, but contains some unusual features | |
663 | that are worth comment. | |
664 | .PP | |
665 | Perhaps the strangest feature of the grammar is the treatment of | |
666 | declarations. | |
667 | The problem is to keep track of the basic type | |
668 | and the storage class while interpreting the various | |
669 | stars, brackets, and parentheses that may surround a given name. | |
670 | The entire declaration mechanism must be recursive, | |
671 | since declarations may appear within declarations of | |
672 | structures and unions, or even within a | |
673 | .B sizeof | |
674 | construction | |
675 | inside a dimension in another declaration! | |
676 | .PP | |
677 | There are some difficulties in using a bottom-up parser, | |
678 | such as produced by Yacc, to handle constructions where a lot | |
679 | of left context information must be kept around. | |
680 | The problem is that the original PDP-11 compiler is top-down in | |
681 | implementation, and some of the semantics of C reflect this. | |
682 | In a top-down parser, the input rules are restricted | |
683 | somewhat, but one can naturally associate temporary | |
684 | storage with a rule at a very early stage in the recognition | |
685 | of that rule. | |
686 | In a bottom-up parser, there is more freedom in the | |
687 | specification of rules, but it is more difficult to know what | |
688 | rule is being matched until the entire rule is seen. | |
689 | The parser described by | |
95f51977 | 690 | .I cgram.y |
c9528a00 C |
691 | makes effective use of |
692 | the bottom-up parsing mechanism in some places (notably the treatment | |
693 | of expressions), but struggles against the | |
694 | restrictions in others. | |
695 | The usual result is that it is necessary to run a stack of values | |
696 | ``on the side'', independent of the Yacc value stack, | |
697 | in order to be able to store and access information | |
698 | deep within inner constructions, where the relationship of the | |
699 | rules being recognized to the total picture is not yet clear. | |
700 | .PP | |
701 | In the case of declarations, the attribute information | |
702 | (type, etc.) for a declaration is carefully | |
703 | kept immediately to the left of the declarator | |
704 | (that part of the declaration involving the name). | |
705 | In this way, when it is time to declare the name, the | |
706 | name and the type information can be quickly brought together. | |
707 | The ``$0'' mechanism of Yacc is used to accomplish this. | |
708 | The result is not pretty, but it works. | |
709 | The storage class information changes more slowly, | |
710 | so it is kept in an external variable, and stacked if | |
711 | necessary. | |
712 | Some of the grammar could be considerably cleaned up by using | |
713 | some more recent features of Yacc, notably actions within | |
714 | rules and the ability to return multiple values for actions. | |
715 | .PP | |
716 | A stack is also used to keep track of the current location | |
717 | to be branched to when a | |
718 | .B break | |
719 | or | |
720 | .B continue | |
721 | statement is processed. | |
722 | .PP | |
723 | This use of external stacks dates from the time when Yacc did not permit | |
724 | values to be structures. | |
725 | Some, or most, of this use of external stacks | |
726 | could be eliminated by redoing the grammar to use the mechanisms now provided. | |
727 | There are some areas, however, particularly the processing of structure, union, | |
95f51977 | 728 | and enumeration declarations, function |
c9528a00 C |
729 | prologs, and switch statement processing, when having |
730 | all the affected data together in an array speeds later | |
731 | processing; in this case, use of external storage seems essential. | |
732 | .PP | |
733 | The | |
734 | .I cgram.y | |
735 | file also contains some small functions used as | |
736 | utility functions in the parser. | |
737 | These include routines for saving case values and labels in processing switches, | |
738 | and stacking and popping | |
739 | values on the external stack described above. | |
740 | .SH | |
741 | Storage Classes | |
742 | .PP | |
743 | C has a finite, but fairly extensive, number of storage classes | |
744 | available. | |
745 | One of the compiler design decisions was to | |
746 | process the storage class information totally in the first pass; | |
747 | by the second pass, this information must have | |
748 | been totally dealt with. | |
749 | This means that all of the storage allocation must take place in the first | |
750 | pass, so that references to automatics and | |
751 | parameters can be turned into references to cells lying a certain | |
752 | number of bytes offset from certain machine registers. | |
753 | Much of this transformation is machine dependent, and strongly | |
754 | depends on the storage class. | |
755 | .PP | |
756 | The classes include EXTERN (for externally declared, but not defined variables), | |
757 | EXTDEF (for external definitions), and similar distinctions for | |
758 | USTATIC and STATIC, UFORTRAN and FORTRAN (for fortran functions) and | |
759 | ULABEL and LABEL. | |
760 | The storage classes REGISTER and AUTO are obvious, as | |
761 | are STNAME, UNAME, and ENAME (for structure, union, and enumeration | |
762 | tags), and the associated MOS, MOU, and MOE (for the members). | |
763 | TYPEDEF is treated as a storage class as well. | |
764 | There are two special storage classes: PARAM and SNULL. | |
765 | SNULL is used to distinguish the case where no explicit | |
766 | storage class has been given; before an entry is made | |
767 | in the symbol table the true storage class is discovered. | |
768 | Similarly, PARAM is used for the temporary entry in the symbol | |
769 | table made before the declaration of function parameters is completed. | |
770 | .PP | |
771 | The most complexity in the storage class process comes from | |
772 | bit fields. | |
773 | A separate storage class is kept for each width bit field; | |
774 | a | |
775 | .I k | |
776 | bit bit field has storage class | |
777 | .I k | |
778 | plus FIELD. | |
779 | This enables the size to be quickly recovered from the storage class. | |
780 | .SH | |
95f51977 | 781 | Symbol Table Maintenance |
c9528a00 C |
782 | .PP |
783 | The symbol table routines do far more than simply enter | |
784 | names into the symbol table; | |
785 | considerable semantic processing and checking is done as well. | |
786 | For example, if a new declaration comes in, it must be checked | |
787 | to see if there is a previous declaration of the same symbol. | |
788 | If there is, there are many cases. | |
789 | The declarations may agree and be compatible (for example, | |
95f51977 | 790 | an \fBextern\fP declaration can appear twice) in which case the |
c9528a00 C |
791 | new declaration is ignored. |
792 | The new declaration may add information (such as an explicit array | |
793 | dimension) to an already present declaration. | |
794 | The new declaration may be different, but still correct (for example, | |
95f51977 | 795 | an \fBextern\fP declaration of something may be entered, |
c9528a00 C |
796 | and then later the definition may be seen). |
797 | The new declaration may be incompatible, but appear in an inner block; | |
798 | in this case, the old declaration is carefully hidden away, and | |
799 | the new one comes into force until the block is left. | |
800 | Finally, the declarations may be incompatible, and an error | |
801 | message must be produced. | |
802 | .PP | |
803 | A number of other factors make for additional complexity. | |
804 | The type declared by the user is not always the type | |
95f51977 | 805 | entered into the symbol table (for example, if a formal parameter to a function |
c9528a00 C |
806 | is declared to be an array, C requires that this be changed into |
807 | a pointer before entry in the symbol table). | |
808 | Moreover, there are various kinds of illegal types that | |
809 | may be declared which are difficult to | |
810 | check for syntactically (for example, | |
811 | a function returning an array). | |
812 | Finally, there is a strange feature in C that requires | |
813 | structure tag names and member names for structures and unions | |
814 | to be taken from a different logical symbol table than ordinary identifiers. | |
815 | Keeping track of which kind of name is involved is a bit of struggle | |
816 | (consider typedef names used within structure declarations, for example). | |
817 | .PP | |
818 | The symbol table handling routines have been rewritten a number of times to | |
819 | extend features, improve performance, and fix bugs. | |
820 | They address the above problems with reasonable effectiveness | |
821 | but a singular lack of grace. | |
822 | .PP | |
823 | When a name is read in the input, it is hashed, and the | |
824 | routine | |
825 | .I lookup | |
826 | is called, together with a flag which tells which symbol table | |
827 | should be searched (actually, both symbol tables are stored in one, and a flag | |
828 | is used to distinguish individual entries). | |
829 | If the name is found, | |
830 | .I lookup | |
831 | returns the index to the entry found; otherwise, it makes | |
832 | a new entry, marks it UNDEF (undefined), and returns the | |
833 | index of the new entry. | |
834 | This index is stored in the | |
835 | .I rval | |
836 | field of a NAME node. | |
837 | .PP | |
838 | When a declaration is being parsed, this NAME node is | |
95f51977 | 839 | made part of a tree with UNARY MUL nodes for each \fB*\fP, |
c9528a00 C |
840 | LB nodes for each array descriptor (the right descendant |
841 | has the dimension), and UNARY CALL nodes for each function | |
842 | descriptor. | |
843 | This tree is passed to the routine | |
844 | .I tymerge , | |
845 | along with the attribute type of the whole declaration; | |
846 | this routine collapses the tree to a single node, by calling | |
847 | .I tyreduce , | |
848 | and then modifies the type to reflect the overall | |
849 | type of the declaration. | |
850 | .PP | |
851 | Dimension and size information is stored in a table called | |
852 | .I dimtab . | |
853 | To properly describe a type in C, one needs not just the | |
854 | type information but also size information (for structures and | |
95f51977 | 855 | enumerations) and dimension information (for arrays). |
c9528a00 C |
856 | Sizes and offsets are dealt with in the compiler by |
857 | giving the associated indices into | |
858 | .I dimtab . | |
859 | .I Tymerge | |
860 | and | |
861 | .I tyreduce | |
862 | call | |
863 | .I dstash | |
864 | to put the discovered dimensions away into the | |
865 | .I dimtab | |
866 | array. | |
867 | .I Tymerge | |
868 | returns a pointer to a single node that contains | |
869 | the symbol table index in its | |
870 | .I rval | |
871 | field, and the size and dimension indices in | |
872 | fields | |
873 | .I csiz | |
874 | and | |
875 | .I cdim , | |
876 | respectively. | |
877 | This information is properly considered part of the type in the first pass, | |
878 | and is carried around at all times. | |
879 | .PP | |
880 | To enter an element into the symbol table, the routine | |
881 | .I defid | |
882 | is called; it is handed a storage class, and a pointer | |
883 | to the node produced by | |
884 | .I tymerge . | |
885 | .I Defid | |
886 | calls | |
887 | .I fixtype , | |
888 | which adjusts and checks the given type depending on the storage | |
889 | class, and converts null types appropriately. | |
890 | It then calls | |
891 | .I fixclass , | |
892 | which does a similar job for the storage class; | |
893 | it is here, for example, that | |
95f51977 C |
894 | \fBregister\fP declarations are either allowed or changed |
895 | to \fBauto\fP. | |
c9528a00 C |
896 | .PP |
897 | The new declaration is now compared against an older one, | |
898 | if present, and several pages of validity checks performed. | |
899 | If the definitions are compatible, with possibly some added information, | |
900 | the processing is straightforward. | |
901 | If the definitions differ, the block levels of the | |
902 | current and the old declaration are compared. | |
903 | The current block level is kept in | |
904 | .I blevel , | |
905 | an external variable; the old declaration level is kept in the symbol table. | |
906 | Block level 0 is for external declarations, 1 is for arguments to functions, | |
907 | and 2 and above are blocks within a function. | |
908 | If the current block level is the same as the old declaration, an error | |
909 | results. | |
910 | If the current block level is higher, the new declaration overrides the old. | |
911 | This is done by marking the old symbol table entry ``hidden'', and making | |
912 | a new entry, marked ``hiding''. | |
913 | .I Lookup | |
914 | will skip over hidden entries. | |
915 | When a block is left, the symbol table is searched, | |
916 | and any entries defined in that block are destroyed; if | |
917 | they hid other entries, the old entries are ``unhidden''. | |
918 | .PP | |
919 | This nice block structure is warped a bit because labels | |
920 | do not follow the block structure rules (one can do a | |
921 | .B goto | |
922 | into | |
923 | a block, for example); | |
924 | default definitions of functions in inner blocks also persist clear out to the outermost scope. | |
925 | This implies that cleaning up the symbol table after block exit is more | |
926 | subtle than it might first seem. | |
927 | .PP | |
928 | For successful new definitions, | |
929 | .I defid | |
930 | also initializes a ``general purpose'' field, | |
931 | .I offset , | |
932 | in the symbol table. | |
933 | It contains the stack offset for automatics and parameters, the register number | |
934 | for register variables, the bit offset into the structure for | |
935 | structure members, and | |
936 | the internal label number for static variables and labels. | |
937 | The offset field is set by | |
938 | .I falloc | |
939 | for bit fields, and | |
940 | .I dclstruct | |
941 | for structures and unions. | |
942 | .PP | |
943 | The symbol table entry itself thus contains | |
944 | the name, type word, size and dimension offsets, | |
945 | offset value, and declaration block level. | |
946 | It also has a field of flags, describing what symbol table the | |
947 | name is in, and whether the entry is hidden, or hides another. | |
948 | Finally, a field gives the line number of the last use, | |
949 | or of the definition, of the name. | |
950 | This is used mainly for diagnostics, but is useful to | |
951 | .I lint | |
952 | as well. | |
953 | .PP | |
954 | In some special cases, there is more than the above amount of information kept | |
955 | for the use of the compiler. | |
956 | This is especially true with structures; for use in initialization, | |
957 | structure declarations must have access to a list of the members of the | |
958 | structure. | |
959 | This list is also kept in | |
960 | .I dimtab . | |
961 | Because a structure can be mentioned long before the | |
962 | members are known, it is necessary to have another | |
963 | level of indirection in the table. | |
964 | The two words following the | |
965 | .I csiz | |
966 | entry in | |
967 | .I dimtab | |
968 | are used to hold the alignment of the structure, and | |
969 | the index in dimtab of the list of members. | |
970 | This list contains the symbol table indices for the structure members, terminated by a | |
971 | \-1. | |
972 | .SH | |
973 | Tree Building | |
974 | .PP | |
975 | The portable compiler transforms expressions | |
976 | into expression trees. | |
977 | As the parser recognizes each rule making up an | |
978 | expression, | |
979 | it calls | |
980 | .I buildtree | |
981 | which is given an operator number, and pointers to the | |
982 | left and right descendants. | |
983 | .I Buildtree | |
984 | first examines the left and right descendants, | |
985 | and, if they are both constants, and the operator | |
986 | is appropriate, simply does the constant | |
987 | computation at compile time, and returns | |
988 | the result as a constant. | |
989 | Otherwise, | |
990 | .I buildtree | |
991 | allocates a node for the head of the tree, | |
992 | attaches the descendants to it, and ensures that | |
993 | conversion operators are generated if needed, and that | |
994 | the type of the new node is consistent with the types | |
995 | of the operands. | |
996 | There is also a considerable amount of semantic complexity here; | |
997 | many combinations of types are illegal, and the portable | |
998 | compiler makes a strong effort to check | |
999 | the legality of expression types completely. | |
1000 | This is done both for | |
1001 | .I lint | |
1002 | purposes, and to prevent such semantic errors | |
1003 | from being passed through to the code generator. | |
1004 | .PP | |
1005 | The heart of | |
1006 | .I buildtree | |
1007 | is a large table, accessed by the routine | |
1008 | .I opact . | |
1009 | This routine maps the types of the left and right | |
1010 | operands into a rather smaller set of descriptors, and then | |
1011 | accesses a table (actually encoded in a switch statement) which | |
1012 | for each operator and pair of types causes | |
1013 | an action to be returned. | |
1014 | The actions are logical or's of a number of | |
1015 | separate actions, which may be | |
1016 | carried out by | |
1017 | .I buildtree . | |
1018 | These component actions may include | |
1019 | checking the left side to ensure that it | |
1020 | is an lvalue (can be stored into), | |
1021 | applying a type conversion to the left or right operand, | |
1022 | setting the type of the new node to | |
1023 | the type of the left or right operand, calling various | |
1024 | routines to balance the types of the left and right operands, | |
1025 | and suppressing the ordinary conversion | |
1026 | of arrays and function operands to pointers. | |
1027 | An important operation is OTHER, which causes | |
1028 | some special code to be invoked | |
1029 | in | |
1030 | .I buildtree , | |
1031 | to handle issues which are unique to a particular operator. | |
1032 | Examples of this are | |
1033 | structure and union reference | |
1034 | (actually handled by | |
1035 | the routine | |
1036 | .I stref ), | |
1037 | the building of NAME, ICON, STRING and FCON (floating point constant) nodes, | |
95f51977 C |
1038 | unary \fB*\fP and \fB&\fP, structure assignment, and calls. |
1039 | In the case of unary \fB*\fP and \fB&\fP, | |
c9528a00 | 1040 | .I buildtree |
95f51977 C |
1041 | will cancel a \fB*\fP applied to a tree, the top node of which |
1042 | is \fB&\fP, and conversely. | |
c9528a00 C |
1043 | .PP |
1044 | Another special operation is | |
1045 | PUN; this | |
1046 | causes the compiler to check for type mismatches, | |
1047 | such as intermixing pointers and integers. | |
1048 | .PP | |
95f51977 | 1049 | The treatment of conversion operators is a rather |
c9528a00 | 1050 | strange area of the compiler (and of C!). |
95f51977 | 1051 | The introduction of type casts only confounded this |
c9528a00 C |
1052 | situation. |
1053 | Most of the conversion operators are generated by | |
1054 | calls to | |
1055 | .I tymatch | |
1056 | and | |
1057 | .I ptmatch , | |
1058 | both of which are given a tree, and asked to make the | |
1059 | operands agree in type. | |
1060 | .I Ptmatch | |
1061 | treats the case where one of the operands is a pointer; | |
1062 | .I tymatch | |
1063 | treats all other cases. | |
1064 | Where these routines have decided on the | |
1065 | proper type for an operand, they call | |
1066 | .I makety , | |
1067 | which is handed a tree, and a type word, dimension offset, and size offset. | |
1068 | If necessary, it inserts a conversion operation to make the | |
1069 | types correct. | |
1070 | Conversion operations are never inserted on the left side of | |
1071 | assignment operators, however. | |
1072 | There are two conversion operators used; | |
1073 | PCONV, if the conversion is to a non-basic type (usually a pointer), | |
1074 | and | |
1075 | SCONV, if the conversion is to a basic type (scalar). | |
1076 | .PP | |
1077 | To allow for maximum flexibility, every node produced by | |
1078 | .I buildtree | |
1079 | is given to a machine dependent routine, | |
1080 | .I clocal , | |
1081 | immediately after it is produced. | |
1082 | This is to allow more or less immediate rewriting of those | |
1083 | nodes which must be adapted for the local machine. | |
1084 | The conversion operations are given to | |
1085 | .I clocal | |
1086 | as well; on most machines, many of these | |
1087 | conversions do nothing, and should be thrown away | |
1088 | (being careful to retain the type). | |
1089 | If this operation is done too early, | |
1090 | however, | |
1091 | later calls to | |
1092 | .I buildtree | |
1093 | may get confused about correct type of the | |
1094 | subtrees; | |
1095 | thus | |
1096 | .I clocal | |
95f51977 | 1097 | is given the conversion operations only after the entire tree is built. |
c9528a00 C |
1098 | This topic will be dealt with in more detail later. |
1099 | .SH | |
1100 | Initialization | |
1101 | .PP | |
1102 | Initialization is one of the messier areas in the portable compiler. | |
1103 | The only consolation is that most of the mess takes place | |
1104 | in the machine independent part, where it | |
1105 | is may be safely ignored by the implementor of the | |
1106 | compiler for a particular machine. | |
1107 | .PP | |
1108 | The basic problem is that the semantics of initialization | |
1109 | really calls for a co-routine structure; one collection | |
1110 | of programs reading constants from the input stream, while another, | |
1111 | independent set of programs places these constants into the | |
1112 | appropriate spots in memory. | |
1113 | The dramatic differences in the local assemblers also | |
1114 | come to the fore here. | |
1115 | The parsing problems are dealt with by keeping a rather | |
1116 | extensive stack containing the current | |
1117 | state of the initialization; the assembler | |
1118 | problems are dealt with by having a fair number of machine dependent routines. | |
1119 | .PP | |
1120 | The stack contains the symbol table number, | |
1121 | type, dimension index, and size index for the current identifier | |
1122 | being initialized. | |
1123 | Another entry has the offset, in bits, of the beginning | |
1124 | of the current identifier. | |
1125 | Another entry keeps track of how many elements have been seen, | |
1126 | if the current identifier is an array. | |
1127 | Still another entry keeps track of the current | |
1128 | member of a structure being initialized. | |
1129 | Finally, there is an entry containing flags | |
1130 | which keep track of the current state of the initialization process | |
95f51977 | 1131 | (e.g., tell if a `}' has been seen for the current identifier). |
c9528a00 C |
1132 | .PP |
1133 | When an initialization begins, the routine | |
1134 | .I beginit | |
1135 | is called; it handles the alignment restrictions, if | |
1136 | any, and calls | |
1137 | .I instk | |
1138 | to create the stack entry. | |
1139 | This is done by first making an entry on the top of the stack for the item | |
1140 | being initialized. | |
1141 | If the top entry is an array, another entry is made on the stack | |
1142 | for the first element. | |
1143 | If the top entry is a structure, another entry is made on the | |
1144 | stack for the first member of the structure. | |
1145 | This continues until the top element of the stack is a scalar. | |
1146 | .I Instk | |
1147 | then returns, and the parser begins collecting initializers. | |
1148 | .PP | |
1149 | When a constant is obtained, the routine | |
1150 | .I doinit | |
1151 | is called; it examines the stack, and does whatever | |
1152 | is necessary to assign the current constant to the | |
1153 | scalar on the top of the stack. | |
1154 | .I gotscal | |
1155 | is then called, which rearranges the stack so that the | |
1156 | next scalar to be initialized gets placed on top of the stack. | |
1157 | This process continues until the end of the initializers; | |
1158 | .I endinit | |
1159 | cleans up. | |
95f51977 | 1160 | If a `{' or `}' is encountered in the |
c9528a00 C |
1161 | string of initializers, it is handled by calling |
1162 | .I ilbrace | |
1163 | or | |
1164 | .I irbrace , | |
1165 | respectively. | |
1166 | .PP | |
1167 | A central issue is the treatment of the ``holes'' that | |
1168 | arise as a result of alignment restrictions or explicit | |
1169 | requests for holes in bit fields. | |
1170 | There is a global variable, | |
1171 | .I inoff , | |
1172 | which contains the current offset in the initialization | |
1173 | (all offsets in the first pass of the compiler are in bits). | |
1174 | .I Doinit | |
1175 | figures out from the top entry on the stack the expected | |
1176 | bit offset of the next identifier; it calls the | |
1177 | machine dependent | |
1178 | routine | |
1179 | .I inforce | |
1180 | which, in a machine dependent way, forces | |
1181 | the assembler to | |
1182 | set aside space if need be so that the | |
1183 | next scalar seen will go into the appropriate | |
1184 | bit offset position. | |
1185 | The scalar itself is passed to one of the machine dependent | |
1186 | routines | |
1187 | .I fincode | |
1188 | (for floating point initialization), | |
1189 | .I incode | |
1190 | (for fields, and other initializations less than an int in | |
1191 | size), | |
1192 | and | |
1193 | .I cinit | |
1194 | (for all other initializations). | |
1195 | The size is passed to all these routines, and it is up to | |
1196 | the machine dependent routines to ensure that the | |
1197 | initializer occupies exactly the right size. | |
1198 | .PP | |
1199 | Character strings represent a bit of an exception. | |
1200 | If a character string is seen as the initializer for | |
1201 | a pointer, the characters making up the string must | |
1202 | be put out under a different location counter. | |
1203 | When the lexical analyzer sees the quote at the head | |
1204 | of a character string, it returns the token STRING, | |
1205 | but does not do anything with the contents. | |
1206 | The parser calls | |
1207 | .I getstr , | |
1208 | which sets up the appropriate location counters | |
1209 | and flags, and calls | |
1210 | .I lxstr | |
1211 | to read and process the contents of the string. | |
1212 | .PP | |
1213 | If the string is being used to initialize a character array, | |
1214 | .I lxstr | |
1215 | calls | |
1216 | .I putbyte , | |
1217 | which in effect simulates | |
1218 | .I doinit | |
1219 | for each character read. | |
1220 | If the string is used to initialize a character pointer, | |
1221 | .I lxstr | |
1222 | calls a machine dependent routine, | |
1223 | .I bycode , | |
1224 | which stashes away each character. | |
1225 | The pointer to this string is then returned, | |
1226 | and processed normally by | |
1227 | .I doinit . | |
1228 | .PP | |
1229 | The null at the end of the string is treated as if it | |
1230 | were read explicitly by | |
1231 | .I lxstr . | |
1232 | .SH | |
1233 | Statements | |
1234 | .PP | |
1235 | The first pass addresses four main areas; declarations, expressions, initialization, and statements. | |
1236 | The statement processing is relatively simple; most of it is carried out in the | |
1237 | parser directly. | |
1238 | Most of the logic is concerned with allocating | |
1239 | label numbers, defining the labels, and branching appropriately. | |
1240 | An external symbol, | |
1241 | .I reached , | |
1242 | is 1 if a statement can be reached, 0 otherwise; this is | |
1243 | used to do a bit of simple flow analysis as the program is being parsed, | |
1244 | and also to avoid generating the subroutine return sequence if the subroutine | |
1245 | cannot ``fall through'' the last statement. | |
1246 | .PP | |
1247 | Conditional branches are handled by generating an expression | |
1248 | node, CBRANCH, | |
1249 | whose left descendant is the conditional expression and the | |
1250 | right descendant is an ICON node containing the internal label | |
1251 | number to be branched to. | |
1252 | For efficiency, the semantics are that | |
1253 | the label is gone to if the condition is | |
1254 | .I false . | |
1255 | .PP | |
1256 | The switch statement is | |
1257 | compiled by collecting the case entries, and an indication as to whether | |
1258 | there is a default case; | |
1259 | an internal label number is generated for each of these, | |
1260 | and remembered in a big array. | |
1261 | The expression comprising the value to be switched on is | |
1262 | compiled when the switch keyword is encountered, | |
1263 | but the expression tree is headed by | |
1264 | a special node, FORCE, which tells the code generator to | |
1265 | put the expression value into a special distinguished | |
1266 | register (this same mechanism is used for processing the | |
1267 | return statement). | |
1268 | When the end of the switch block is reached, the array | |
1269 | containing the case values is sorted, and checked for | |
1270 | duplicate entries (an error); if all is | |
1271 | correct, the machine dependent routine | |
1272 | .I genswitch | |
1273 | is called, with this array of labels and values in increasing order. | |
1274 | .I Genswitch | |
1275 | can assume that the value to be tested is already in the | |
1276 | register which is the usual integer return value register. | |
1277 | .SH | |
1278 | Optimization | |
1279 | .PP | |
1280 | There is a machine independent file, | |
1281 | .I optim.c , | |
1282 | which contains a relatively short optimization routine, | |
1283 | .I optim . | |
1284 | Actually the word optimization is something of a misnomer; | |
1285 | the results are not optimum, only improved, and the | |
1286 | routine is in fact not optional; it must | |
1287 | be called for proper operation of the compiler. | |
1288 | .PP | |
1289 | .I Optim | |
1290 | is called after an expression tree is built, but | |
1291 | before the code generator is called. | |
1292 | The essential part of its job is to call | |
1293 | .I clocal | |
1294 | on the conversion operators. | |
1295 | On most machines, the treatment of | |
95f51977 | 1296 | \fB&\fP is also essential: |
c9528a00 | 1297 | by this time in the processing, the only node which |
95f51977 C |
1298 | is a legal descendant of \fB&\fP is NAME. |
1299 | (Possible descendants of \fB*\fP have been eliminated by | |
1300 | .I buildtree .) | |
c9528a00 C |
1301 | The address of a static name is, almost by definition, a |
1302 | constant, and can be represented by an ICON node on most machines | |
1303 | (provided that the loader has enough power). | |
1304 | Unfortunately, this is not universally true; on some machine, such as the IBM 370, | |
1305 | the issue of addressability rears its ugly head; | |
1306 | thus, before turning a NAME node into an ICON node, | |
1307 | the machine dependent function | |
1308 | .I andable | |
1309 | is called. | |
1310 | .PP | |
1311 | The optimization attempts of | |
1312 | .I optim | |
95f51977 | 1313 | are quite limited. |
c9528a00 C |
1314 | It is primarily concerned with improving the behavior of |
1315 | the compiler with operations one of whose arguments is a constant. | |
1316 | In the simplest case, the constant is placed on the right if the | |
1317 | operation is commutative. | |
1318 | The compiler also makes a limited search for expressions | |
1319 | such as | |
1320 | .DS | |
95f51977 | 1321 | ( \fIx\fP + \fIa\fP ) + \fIb\fP |
c9528a00 C |
1322 | .DE |
1323 | where | |
1324 | .I a | |
1325 | and | |
1326 | .I b | |
1327 | are constants, and attempts to combine | |
1328 | .I a | |
1329 | and | |
1330 | .I b | |
1331 | at compile time. | |
1332 | A number of special cases are also examined; | |
1333 | additions of 0 and multiplications by 1 are removed, | |
1334 | although the correct processing of these cases to get | |
1335 | the type of the resulting tree correct is | |
1336 | decidedly nontrivial. | |
1337 | In some cases, the addition or multiplication must be replaced by | |
95f51977 | 1338 | a conversion operator to keep the types from becoming |
c9528a00 | 1339 | fouled up. |
95f51977 C |
1340 | In cases where a relational operation is being done |
1341 | and one operand is a constant, the operands are permuted and the operator altered, if necessary, | |
c9528a00 C |
1342 | to put the constant on the right. |
1343 | Finally, multiplications by a power of 2 are changed to shifts. | |
c9528a00 C |
1344 | .SH |
1345 | Machine Dependent Stuff | |
1346 | .PP | |
1347 | A number of the first pass machine dependent routines have been discussed above. | |
1348 | In general, the routines are short, and easy to adapt from | |
1349 | machine to machine. | |
1350 | The two exceptions to this general rule are | |
1351 | .I clocal | |
1352 | and | |
1353 | the function prolog and epilog generation routines, | |
1354 | .I bfcode | |
1355 | and | |
1356 | .I efcode . | |
1357 | .PP | |
1358 | .I Clocal | |
1359 | has the job of rewriting, if appropriate and desirable, | |
1360 | the nodes constructed by | |
1361 | .I buildtree . | |
1362 | There are two major areas where this | |
95f51977 | 1363 | is important: |
c9528a00 C |
1364 | NAME nodes and conversion operations. |
1365 | In the case of NAME nodes, | |
1366 | .I clocal | |
1367 | must rewrite the NAME node to reflect the | |
1368 | actual physical location of the name in the machine. | |
1369 | In effect, the NAME node must be examined, the symbol table | |
1370 | entry found (through the | |
1371 | .I rval | |
1372 | field of the node), | |
1373 | and, based on the storage class of the node, | |
1374 | the tree must be rewritten. | |
1375 | Automatic variables and parameters are typically | |
1376 | rewritten by treating the reference to the variable as | |
1377 | a structure reference, off the register which | |
1378 | holds the stack or argument pointer; | |
1379 | the | |
1380 | .I stref | |
1381 | routine is set up to be called in this way, and to | |
1382 | build the appropriate tree. | |
1383 | In the most general case, the tree consists | |
95f51977 C |
1384 | of a unary \fB*\fP node, whose descendant is |
1385 | a \fB+\fP node, with the stack or argument register as left operand, | |
c9528a00 C |
1386 | and a constant offset as right operand. |
1387 | In the case of LABEL and internal static nodes, the | |
1388 | .I rval | |
1389 | field is rewritten to be the negative of the internal | |
1390 | label number; a negative | |
1391 | .I rval | |
1392 | field is taken to be an internal label number. | |
1393 | Finally, a name of class REGISTER must be converted into a REG node, | |
1394 | and the | |
1395 | .I rval | |
1396 | field replaced by the register number. | |
1397 | In fact, this part of the | |
1398 | .I clocal | |
1399 | routine is nearly machine independent; only for machines | |
1400 | with addressability problems (IBM 370 again!) does it | |
95f51977 | 1401 | have to be noticeably different. |
c9528a00 C |
1402 | .PP |
1403 | The conversion operator treatment is rather tricky. | |
1404 | It is necessary to handle the application of conversion operators | |
1405 | to constants in | |
1406 | .I clocal , | |
1407 | in order that all constant expressions can have their values known | |
1408 | at compile time. | |
1409 | In extreme cases, this may mean that some simulation of the | |
1410 | arithmetic of the target machine might have to be done in a | |
1411 | cross-compiler. | |
1412 | In the most common case, | |
1413 | conversions from pointer to pointer do nothing. | |
1414 | For some machines, however, conversion from byte pointer to short or long | |
1415 | pointer might require a shift or rotate operation, which would | |
1416 | have to be generated here. | |
1417 | .PP | |
1418 | The extension of the portable compiler to machines where the size of a pointer | |
1419 | depends on its type would be straightforward, but has not yet been done. | |
1420 | .PP | |
95f51977 C |
1421 | Another machine dependent issue in the first pass |
1422 | is the generation of external ``symbol table'' information. | |
1423 | This sort of symbol table is used by programs such as symbolic debuggers | |
1424 | to relate object code back to source code. | |
1425 | Symbol table routines are provided in | |
1426 | the file \fIstab.c\fP, | |
1427 | which is included in the machine dependent sources | |
1428 | for the first pass. | |
1429 | The symbol table routines insert assembly code | |
1430 | containing assembly pseudo-ops directly into | |
1431 | the instruction stream generated by the compiler. | |
1432 | .PP | |
1433 | There are two basic kinds of symbol table operations. | |
1434 | The simplest operation is the generation of a source line number; | |
1435 | this serves to map an address in an executable image | |
1436 | into a line in a source file so that a debugger | |
1437 | can find the source code | |
1438 | corresponding to the instructions being executed. | |
1439 | The routine \fIpsline\fP is called by the scanner | |
1440 | to emit source line numbers when | |
1441 | a nonempty source line is seen. | |
1442 | The other variety of symbol table operation | |
1443 | is the generation of type and address information | |
1444 | about C symbols. | |
1445 | This is done through the \fIoutstab\fP routine, | |
1446 | which is normally called using the FIXDEF macro | |
1447 | in the monster \fIdefid\fP routine in \fIpftn.c\fP | |
1448 | that enters symbols into the compiler's internal symbol table. | |
1449 | .PP | |
1450 | Yet another major machine dependent issue involves function prolog and epilog | |
c9528a00 C |
1451 | generation. |
1452 | The hard part here is the design of the stack frame | |
1453 | and calling sequence; this design issue is discussed elsewhere. | |
1454 | .[ | |
1455 | Johnson Lesk Ritchie calling sequence | |
1456 | .] | |
1457 | The routine | |
1458 | .I bfcode | |
1459 | is called with the number of arguments | |
1460 | the function is defined with, and | |
1461 | an array containing the symbol table indices of the | |
1462 | declared parameters. | |
1463 | .I Bfcode | |
1464 | must generate the code to establish the new stack frame, | |
1465 | save the return address and previous stack pointer | |
1466 | value on the stack, and save whatever | |
1467 | registers are to be used for register variables. | |
1468 | The stack size and the number of register variables is not | |
1469 | known when | |
1470 | .I bfcode | |
1471 | is called, so these numbers must be | |
1472 | referred to by assembler constants, which are | |
1473 | defined when they are known (usually in the second pass, | |
1474 | after all register variables, automatics, and temporaries have been seen). | |
1475 | The final job is to find those parameters which may have been declared | |
1476 | register, and generate the code to initialize | |
1477 | the register with the value passed on the stack. | |
1478 | Once again, for most machines, the general logic of | |
1479 | .I bfcode | |
1480 | remains the same, but the contents of the | |
1481 | .I printf | |
1482 | calls in it will change from machine to machine. | |
1483 | .I efcode | |
1484 | is rather simpler, having just to generate the default | |
1485 | return at the end of a function. | |
1486 | This may be nontrivial in the case of a function returning a structure or union, however. | |
1487 | .PP | |
1488 | There seems to be no really good place to discuss structures and unions, but | |
1489 | this is as good a place as any. | |
1490 | The C language now supports structure assignment, | |
1491 | and the passing of structures as arguments to functions, | |
1492 | and the receiving of structures back from functions. | |
1493 | This was added rather late to C, and thus to the portable compiler. | |
1494 | Consequently, it fits in less well than the older features. | |
1495 | Moreover, most of the burden of making these features work is | |
1496 | placed on the machine dependent code. | |
1497 | .PP | |
1498 | There are both conceptual and practical problems. | |
1499 | Conceptually, the compiler is structured around | |
1500 | the idea that to compute something, you put it into | |
1501 | a register and work on it. | |
1502 | This notion causes a bit of trouble on some machines (e.g., machines with 3-address opcodes), but | |
1503 | matches many machines quite well. | |
1504 | Unfortunately, this notion breaks down with structures. | |
1505 | The closest that one can come is to keep the addresses of the | |
1506 | structures in registers. | |
1507 | The actual code sequences used to move structures vary from the | |
1508 | trivial (a multiple byte move) to the horrible (a | |
1509 | function call), and are very machine dependent. | |
1510 | .PP | |
1511 | The practical problem is more painful. | |
1512 | When a function returning a structure is called, this function | |
1513 | has to have some place to put the structure value. | |
1514 | If it places it on the stack, it has difficulty popping its stack frame. | |
1515 | If it places the value in a static temporary, the routine fails to be | |
1516 | reentrant. | |
1517 | The most logically consistent way of implementing this is for the | |
1518 | caller to pass in a pointer to a spot where the called function | |
1519 | should put the value before returning. | |
1520 | This is relatively straightforward, although a bit tedious, to implement, | |
1521 | but means that the caller must have properly declared | |
1522 | the function type, even if the value is never used. | |
1523 | On some machines, such as the Interdata 8/32, the return value | |
1524 | simply overlays the argument region (which on the 8/32 is part | |
1525 | of the caller's stack frame). | |
1526 | The caller takes care of leaving enough room if the returned value is larger | |
1527 | than the arguments. | |
95f51977 | 1528 | This also assumes that the caller declares the |
c9528a00 C |
1529 | function properly. |
1530 | .PP | |
95f51977 | 1531 | The PDP-11 and the \*V have stack hardware which is used in function calls and returns; |
c9528a00 C |
1532 | this makes it very inconvenient to |
1533 | use either of the above mechanisms. | |
95f51977 C |
1534 | In these machines, a static area within the called function |
1535 | is allocated, and | |
c9528a00 C |
1536 | the function return value is copied into it on return; the function |
1537 | returns the address of that region. | |
1538 | This is simple to implement, but is non-reentrant. | |
1539 | However, the function can now be called as a subroutine | |
1540 | without being properly declared, without the disaster which would otherwise ensue. | |
1541 | No matter what choice is taken, the convention is that the function | |
1542 | actually returns the address of the return structure value. | |
1543 | .PP | |
1544 | In building expression trees, the portable compiler takes a bit for granted about | |
1545 | structures. | |
1546 | It assumes that functions returning structures | |
1547 | actually return a pointer to the structure, and it assumes that | |
1548 | a reference to a structure is actually a reference to its address. | |
1549 | The structure assignment operator is rebuilt so that the left | |
1550 | operand is the structure being assigned to, but the | |
1551 | right operand is the address of the structure being assigned; | |
1552 | this makes it easier to deal with | |
1553 | .DS | |
1554 | .I "a = b = c" | |
1555 | .DE | |
1556 | and similar constructions. | |
1557 | .PP | |
1558 | There are four special tree nodes associated with these | |
1559 | operations: | |
1560 | STASG (structure assignment), STARG (structure argument | |
1561 | to a function call), and STCALL and UNARY STCALL | |
1562 | (calls of a function with nonzero and zero arguments, respectively). | |
1563 | These four nodes are unique in that the size and alignment information, which can be determined by | |
1564 | the type for all other objects in C, | |
1565 | must be known to carry out these operations; special | |
1566 | fields are set aside in these nodes to contain | |
1567 | this information, and special | |
1568 | intermediate code is used to transmit this information. | |
1569 | .SH | |
1570 | First Pass Summary | |
1571 | .PP | |
1572 | There are may other issues which have been ignored here, | |
1573 | partly to justify the title ``tour'', and partially | |
1574 | because they have seemed to cause little trouble. | |
1575 | There are some debugging flags | |
1576 | which may be turned on, by giving the compiler's first pass | |
1577 | the argument | |
1578 | .DS | |
95f51977 | 1579 | .B \-X [flags] |
c9528a00 C |
1580 | .DE |
1581 | Some of the more interesting flags are | |
95f51977 C |
1582 | \fB\-Xd\fP for the defining and freeing of symbols, |
1583 | \fB\-Xi\fP for initialization comments, and | |
1584 | \fB\-Xb\fP for various comments about the building of trees. | |
c9528a00 C |
1585 | In many cases, repeating the flag more than once gives more information; |
1586 | thus, | |
95f51977 | 1587 | \fB\-Xddd\fP gives more information than \fB\-Xd\fP. |
c9528a00 C |
1588 | In the two pass version of the compiler, the |
1589 | flags should not be set when the output is sent to the second | |
1590 | pass, since the debugging output and the intermediate code both go onto the standard | |
1591 | output. | |
1592 | .PP | |
1593 | We turn now to consideration of the second pass. |