![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to porttour1.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / share / doc / smm / 19.porttour|
Return to porttour1.ms CVS log | Up to [CSRG BSD Unix] / 43BSDReno / share / doc / smm / 19.porttour |
1.1 root 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: ..
14: .TL
15: A Tour Through the Portable C Compiler
16: .AU
17: S. C. Johnson
18: .AI
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
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
59: the DEC \*V, Honeywell 6000, IBM 370, and Interdata 8/32.
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.
142: On the other hand, a certain amount of the code requires hard
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.).
184: The two passes may optionally be followed by
185: a machine dependent code improver.
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.
193: The code improver, if used, converts the assembler code
194: to more effective code,
195: and the result is passed to the assembler.
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
201: The division of the compiler into two passes is somewhat artificial.
202: The compiler can optionally be loaded
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.
209: This ``one pass'' compiler is the standard version
210: on machines with large address spaces, such as the \*V.
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
269: trees contain information useful to both logical passes.
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,
278: without the need for `)' at the head of each line.
279: .SH
280: The Source Files
281: .PP
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
289: has machine-dependent definitions, such as the size and alignment of the
290: various data representations.
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.
319: Two machine independent header files,
320: .I pass1.h
321: and
322: .I pass2.h ,
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,
326: .I mac2defs.h ,
327: contains declarations of register names, etc.
328: .PP
329: .I Common.c
330: contains machine independent routines used in both passes.
331: These include routines for allocating and freeing trees, walking over trees,
332: printing debugging information, and printing error messages.
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.
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
342: .I cgram.y ,
343: .I code.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
351: and
352: .I xdefs.c .
353: .I Scan.c
354: is the lexical analyzer, which provides tokens to the
355: bottom-up parser which is defined by the Yacc grammar
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.
365: .I Common.c
366: contains service routines common to the two passes of the compiler.
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.
374: .I Stab.c
375: contains machine dependent code for
376: producing external symbol table information
377: which can drive a symbolic debugger.
378: .PP
379: The second pass
380: is produced by compiling and loading
381: .I allo.c ,
382: .I common.c ,
383: .I local2.c ,
384: .I match.c ,
385: .I order.c ,
386: .I reader.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.
397: .I Common.c
398: defines certain service routines,
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
410: Data Structure Considerations
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
416: .I manifest.h
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,
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.
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
501: represents the type of an array of pointers to functions returning \fBdouble\fPs.
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
526: .I t\(fm ,
527: a function returning
528: .I t\(fm ,
529: or an array of
530: .I t\(fm ,
531: then
532: .I DECREF(t)
533: would equal
534: .I t\(fm .
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
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
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.
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
660: As mentioned above, the parser is generated by Yacc from the grammar
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
690: .I cgram.y
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,
728: and enumeration declarations, function
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
781: Symbol Table Maintenance
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,
790: an \fBextern\fP declaration can appear twice) in which case the
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,
795: an \fBextern\fP declaration of something may be entered,
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
805: entered into the symbol table (for example, if a formal parameter to a function
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
839: made part of a tree with UNARY MUL nodes for each \fB*\fP,
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
855: enumerations) and dimension information (for arrays).
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
894: \fBregister\fP declarations are either allowed or changed
895: to \fBauto\fP.
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,
1038: unary \fB*\fP and \fB&\fP, structure assignment, and calls.
1039: In the case of unary \fB*\fP and \fB&\fP,
1040: .I buildtree
1041: will cancel a \fB*\fP applied to a tree, the top node of which
1042: is \fB&\fP, and conversely.
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
1049: The treatment of conversion operators is a rather
1050: strange area of the compiler (and of C!).
1051: The introduction of type casts only confounded this
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
1097: is given the conversion operations only after the entire tree is built.
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
1131: (e.g., tell if a `}' has been seen for the current identifier).
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.
1160: If a `{' or `}' is encountered in the
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
1296: \fB&\fP is also essential:
1297: by this time in the processing, the only node which
1298: is a legal descendant of \fB&\fP is NAME.
1299: (Possible descendants of \fB*\fP have been eliminated by
1300: .I buildtree .)
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
1313: are quite limited.
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
1321: ( \fIx\fP + \fIa\fP ) + \fIb\fP
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
1338: a conversion operator to keep the types from becoming
1339: fouled up.
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,
1342: to put the constant on the right.
1343: Finally, multiplications by a power of 2 are changed to shifts.
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
1363: is important:
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
1384: of a unary \fB*\fP node, whose descendant is
1385: a \fB+\fP node, with the stack or argument register as left operand,
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
1401: have to be noticeably different.
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
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
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.
1528: This also assumes that the caller declares the
1529: function properly.
1530: .PP
1531: The PDP-11 and the \*V have stack hardware which is used in function calls and returns;
1532: this makes it very inconvenient to
1533: use either of the above mechanisms.
1534: In these machines, a static area within the called function
1535: is allocated, and
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
1579: .B \-X [flags]
1580: .DE
1581: Some of the more interesting flags are
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.
1585: In many cases, repeating the flag more than once gives more information;
1586: thus,
1587: \fB\-Xddd\fP gives more information than \fB\-Xd\fP.
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.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.