![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to interface.tex CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / lcc / doc|
Return to interface.tex CVS log | Up to [Research Unix] / researchv10no / cmd / lcc / doc |
1.1 root 1: \documentstyle{article}
2:
3: \begin{document}
4: \begin{titlepage}
5: \normalsize
6: \vspace*{.7in}
7: \begin{center}
8: \begin{tabular}{c}
9: \bf\Large A Code Generation Interface for ANSI C \\[.5in]
10:
11: Christopher W. Fraser \\
12: \em AT\&T Bell Laboratories, 600 Mountain Avenue, \\
13: \em Murray Hill, NJ 07974 \\[1ex]
14: and \\[1ex]
15: David R. Hanson \\
16: \em Department of Computer Science, Princeton University, \\
17: \em Princeton, NJ 08544 \\[.7in]
18:
19: Research Report CS-TR-270-90 \\[1ex]
20: July 1990 \\
21: Last Revised September 1992 \\[.5in]
22:
23: \end{tabular}
24: \end{center}
25:
26: \begin{abstract}
27: \normalsize
28: \verb|lcc| is a retargetable, production compiler for ANSI~C;
29: it has been ported to the VAX, Motorola 68020, SPARC, and MIPS R3000,
30: and some versions have been in use for over two years.
31: It is smaller and faster than generally available alternatives,
32: and its local code is comparable.
33: This report describes the interface between the target-independent front end
34: and the target-dependent back ends.
35: The interface consists of shared data structures, a few functions,
36: and a dag language. While this approach couples the front
37: and back ends tightly, it results in efficient, compact compilers.
38: The interface is illustrated by detailing a complete code generator
39: that emits naive VAX code.
40: \end{abstract}
41:
42: \end{titlepage}
43:
44: %\setcounter{secnumdepth}{0}
45: %\bibliographystyle{abbrv}
46:
47: \section{Introduction}
48:
49: \verb|lcc| is a retargetable compiler for ANSI~C~\cite{ansi:Cstandard}.
50: It has been ported to the VAX, Motorola 68020, SPARC, and MIPS R3000.
51: It emits code that is comparable with that from other generally
52: available C compilers, but it runs up to twice as fast and is about
53: half the size~\cite{fraser:hanson:91b}.
54: \verb|lcc| is in production use at Princeton University
55: and AT\&T Bell Laboratories.
56:
57: This paper describes the interface between the target-independent
58: front end and the target-dependent back ends.\footnote{References~\cite{fraser:hanson:91a}
59: and~\cite{fraser:hanson:92} were drawn from earlier versions of this report.
60: This report is slightly more detailed and corresponds to the latest
61: release of \verb|lcc|.}
62: Good code-generation interfaces are hard to design.
63: An inadequate interface may force each back end
64: to do work that could otherwise be done once in the front end.
65: Annotating frequently referenced variables for assignment
66: to registers is an example.
67: If the interface is too small, it
68: may not encode enough information to exploit new
69: machines thoroughly. If the interface is too large, the back ends
70: may be needlessly complicated.
71: These competing demands
72: require careful engineering, and re-engineering as new targets expose
73: flaws. This paper reports the results of such experience.
74:
75: The interface is illustrated with a {\em sample} code generator
76: for the VAX. This code generator emits naive code; i.e., it uses only
77: the `RISC subset' of the VAX instruction set. It is nevertheless
78: complete: when used with a conforming preprocessor and library, the
79: compiler with this code generator passes the conformance section of
80: Version 2.00 of the Plum-Hall Validation Suite for ANSI~C, except that
81: it does not detect overflow in floating constants.
82: The production versions of \verb|lcc| use the interface described here,
83: but use back ends in which instruction selection and optimization are
84: generated automatically from a compact specification~\cite{fraser:sigplan89}.%
85: \footnote{The {\tt lcc} front end and a sample code generator are available
86: for anonymous {\tt ftp} from {\tt princeton.edu}.
87: The file {\tt README} in the directory {\tt pub/lcc} gives details.}
88:
89: Unlike other interfaces, \verb|lcc|'s interface is not a monolithic
90: intermediate language~\cite{tanenbaum:toplas:82}. Such interfaces
91: promote decoupling between the front and back ends, but sacrifice
92: compiler performance~\cite{tanenbaum:sigplan:89}. With \verb|lcc|'s
93: interface, the front and back ends are tightly coupled; this approach
94: yields efficient, compact compilers, but can complicate maintenance
95: because changes to the front end may affect the back ends. This
96: complication is less important for standardized languages like ANSI~C
97: because there will be few changes to the language.
98:
99: The interface consists of a few shared data structures, 19 functions,
100: most of which are very simple, and a 36-operator dag language, which
101: encodes the executable code from a source program. The dag language
102: corresponds to the `intermediate language' used in other compilers, but
103: it is smaller than typical intermediate languages.
104: The functions, which can be implemented as true functions or as macros,
105: are listed in Appendix~\ref{appendix:interface} and are
106: described in the sections below.
107:
108: The front and back ends are clients of each other. The front end calls
109: on the back end to generate and emit code. The back end calls on the
110: front end to perform output, allocate storage, interrogate types, and
111: manage nodes, symbols, and strings. These front-end services are
112: performed by functions that are summarized in Appendix~\ref{appendix:functions}.
113:
114:
115: \section{Configuration}
116:
117: \label{configuration}
118: Target-specific configuration parameters specify the widths and
119: alignments of the basic datatypes and optionally define conditional
120: compilation flags. They are defined in a `header' file, \verb|config.h|,
121: which is included when a target-specific \verb|lcc| is compiled.
122:
123: The sample type metrics
124: and conditional compilation flags are defined as follows.
125: Target-specific components of the shared data structures
126: are defined in Sections~\ref{symbols} and \ref{dags}.
127: \begin{verbatim}
128: typedef int Xinterface;
129: \end{verbatim}
130:
131: Type metrics are triples that give the size and alignment of the type
132: in bytes, along with a flag indicating whether or not constants of that
133: type can appear in instructions. A \verb|1| indicates that the
134: constants {\em cannot} appear in instructions; the front end generates
135: variables to hold them. The size of a type must be a multiple of its alignment.
136:
137: Both the size and alignment for characters must be \verb|1|.
138: Unsigned and long integers are assumed to have metrics
139: identical to integer, and long doubles are assumed to have metrics
140: identical to double. The front end correctly treats all of these types
141: as separate, however.
142: \verb|POINTER_METRICS| apply to all pointer types, and pointers
143: must fit in unsigned integers.
144: The alignment of a structure is the maximum of the alignments
145: of its fields and \verb|STRUCT_ALIGN|.
146:
147: If \verb|JUMP_ON_RETURN| is non-zero, the front end generates a jump to
148: a generated label for each \verb|return| statement and defines this
149: label at the end of each function. Similar action is taken if the
150: compiler is asked to generate data for a debugger, because some
151: debuggers assume a common exit point. Since the VAX does returns with
152: one instruction, \verb|JUMP_ON_RETURN| is defined as \verb|0|.
153:
154: By default, the front end generates code that evaluates function
155: arguments from right to left;
156: defining \verb|LEFT_TO_RIGHT| yields the opposite order.
157: A sequence of bit fields is laid out from left to right
158: in one or more unsigned values; defining \verb|LITTLE_ENDIAN|
159: yields a right-to-left layout.
160: Defining \verb|LITTLE_ENDIAN| for the sample
161: makes the code compatible with existing VAX C compilers.
162: The standard permits either argument evaluation
163: or bit-field layout order, however.
164:
165: The front end contains a few target-specific operations.
166: These are protected by conditional compilation on \verb|VAX|,
167: \verb|MIPS|, \verb|MC|, \verb|SPARC|, etc. Thus, \verb|VAX| is defined above.
168:
169: \subsection{{\tt progbeg} and \tt progend}
170:
171: \label{progbeg}\label{progend}
172: During initialization, the front end calls
173: \begin{verbatim}
174: void progbeg(int argc, char *argv[])
175: \end{verbatim}
176: \verb|argv[0..argc-1]| point
177: to those program arguments that are not recognized by the front end,
178: e.g., target-specific options.
179: Typical implementations of \verb|progbeg| process such
180: options and initialize themselves.
181: At the end of compilation, \verb|progend(void)| is called to give
182: the back end an opportunity to finalize its output.
183:
184: The sample \verb|progbeg| initializes a register usage mask
185: \begin{verbatim}
186: void progbeg(int argc, char *argv[]) {
187: rmask = ((~0)<<12)|1;
188: }
189: \end{verbatim}
190: which is described in Section~\ref{dags:registers}.
191: Finalization is unnecessary in the sample,
192: so \verb|progend| is an empty function:
193: \begin{verbatim}
194: static void progend(void) {
195: }
196: \end{verbatim}
197: All back-end functions except \verb|address| and \verb|gen| return nothing.
198:
199:
200: \section{Symbols}
201:
202: \label{symbols}
203: The front and back ends share two major data structures: symbol table
204: entries and dag nodes. Dag nodes are described in Section~\ref{dags}.
205: Symbol table entries are used for variables, constants, and labels.
206: They are represented by pointers to the following structure.
207: \begin{verbatim}
208: typedef struct symbol *Symbol;
209: struct symbol { /* symbol table entries: */
210: Xsymbol x; /* type extension for code generator */
211: char *name; /* name */
212: unsigned char scope; /* scope level */
213: unsigned char sclass; /* storage class */
214: unsigned defined:1; /* 1 if defined */
215: unsigned temporary:1; /* 1 if a temporary */
216: unsigned generated:1; /* 1 if a generated identifier */
217: unsigned addressed:1; /* 1 if its address is taken */
218: unsigned structarg:1; /* 1 if parameter is a struct */
219: Type type; /* data type */
220: union {
221: struct { /* labels: */
222: int label; /* label number */
223: } l;
224: struct { /* constants: */
225: Value v; /* value */
226: Symbol loc; /* out-of-line location */
227: } c;
228: int seg; /* globals, statics: definition segment */
229: } u;
230: };
231: \end{verbatim}
232: The \verb|scope|, \verb|sclass|, and \verb|type| fields give the symbol's
233: scope level, its storage class, and its type, respectively.
234: Most of the bit fields flag self-explanatory attributes for each symbol;
235: fields relevant only to the front end are elided above.
236:
237: Scope values classify symbols as constants, labels, or variables.
238: For labels, constants, and some variables,
239: a field of the union \verb|u| supplies additional data.
240:
241: Labels have a \verb|scope| equal to the enumeration constant \verb|LABELS|.
242: The \verb|u.l.label| field is the numeric value of the label,
243: and \verb|name| is the string representation of that value.
244: Labels have no \verb|type| or \verb|sclass|.
245:
246: Constants have a scope equal to \verb|CONSTANTS|, a \verb|sclass| equal
247: to \verb|STATIC|, and a \verb|name|
248: equal to the string representation of the constant.
249: The actual value of the constant is stored in the \verb|u.c.v| field,
250: which is defined by
251: \begin{verbatim}
252: typedef union value { /* constant values: */
253: char sc; /* signed */
254: short ss; /* signed */
255: int i; /* signed */
256: unsigned char uc;
257: unsigned short us;
258: unsigned int u;
259: float f;
260: double d;
261: char *p; /* pointer to anything */
262: } Value;
263: \end{verbatim}
264: If a variable is generated to hold the constant,
265: \verb|u.c.loc| points to the symbol-table entry for that variable.
266:
267: Variables have a \verb|scope| equal to \verb|GLOBAL|, \verb|PARAM|,
268: or \verb|LOCAL|$+k$ for nesting level $k$.
269: \verb|sclass| is \verb|STATIC|, \verb|AUTO|, \verb|EXTERN|, or \verb|REGISTER|.
270: The \verb|name| of most variables is the name used in the source code.
271: For temporaries and other generated variables, \verb|name| is a digit sequence.
272: \verb|temporary| and \verb|generated| are set for temporaries,
273: and \verb|generated| is set for labels and other generated variables, e.g., those
274: that hold constants.
275: \verb|structarg| is described in Section~\ref{emit}.
276: For global and static variables,
277: \verb|u.seg| gives the logical segment in which the variable is defined
278: (see Section~\ref{segment}).
279:
280: The \verb|type| field for constants and variables points to
281: a structure that describes types. The \verb|size| and \verb|align|
282: fields of this structure give, respectively, the size and alignment constraints
283: of the type in bytes.
284:
285: The \verb|x| field is an `extension' in which the back end stores
286: target-specific data for the symbol.
287: The sample has only two fields:
288: \begin{verbatim}
289: typedef struct {
290: char *name; /* name for back end */
291: int offset; /* frame offset */
292: } Xsymbol;
293: \end{verbatim}
294: This definition appears in the configuration file.
295: \verb|p->name| identifies the symbol to the front end, but the back end
296: may need to emit a different `name'. For example,
297: the `name' for locals is usually an offset from a frame pointer.
298: \verb|p->x.name| is the back end's name for the symbol.
299: For parameters and locals, \verb|p->x.offset| is the
300: offset from the frame pointer (see Sections~\ref{function} and~\ref{local}).
301:
302: \subsection{\tt defsymbol}
303:
304: \label{defsymbol}
305: Whenever the front end defines a new symbol with
306: \verb|scope| \verb|CONSTANTS|, \verb|LABELS|, or \verb|GLOBAL|
307: or a static variable, it calls
308: \verb|defsymbol(Symbol p)| to give the back end an opportunity to initialize
309: its \verb|Xsymbol| fields. The sample's \verb|defsymbol| is
310: \begin{verbatim}
311: static void defsymbol(Symbol p) {
312: if (p->scope == CONSTANTS)
313: p->x.name = p->name;
314: else if (p->scope >= LOCAL && p->sclass == STATIC)
315: p->x.name = stringf("L%d", genlabel(1));
316: else if (p->generated)
317: p->x.name = stringf("L%s", p->name);
318: else
319: p->x.name = stringf("_%s", p->name);
320: }
321: \end{verbatim}
322: The back end's name for a constant is just the constant itself.
323: For generated symbols including labels, \verb|x.name| is the front end's name,
324: which is a digit string, prefixed with an \verb|L|,
325: and an underscore prefixes the names of other symbols.
326: \verb|stringf| returns a pointer to a string formatted as specified
327: by its \verb|printf|-style arguments.
328:
329: For \verb|scope| \verb|PARAM| and \verb|LOCAL|$+k$,
330: the \verb|Xsymbol| fields are initialized
331: by \verb|function| (see Section~\ref{function})
332: and \verb|local| (see Section~\ref{local}), respectively,
333: and symbols that represent address computations
334: are initialized by \verb|address| (see Section~\ref{address}).
335:
336: \subsection{{\tt import} and \tt export}
337:
338: \label{import}\label{export}
339: A symbol can be exported or imported.
340: Non-static variables and functions are exported
341: in order to be available to other,
342: separately compiled modules. Likewise, variables and functions used
343: in one module, but defined in another one, are imported
344: in the former module.
345: The front end identifies an exported or imported symbol
346: by calling \verb|export(Symbol p)| or \verb|import(Symbol p)|. \verb|export|
347: is always called {\em before} the symbol is defined;
348: \verb|import|, however, may be called any time, before or after the symbol
349: is used.
350:
351: The sample back end emits an assembler directive for \verb|export|,
352: but no output is required for \verb|import|:
353: \begin{verbatim}
354: static void export(Symbol p) {
355: print(".globl %s\n", p->x.name);
356: }
357:
358: static void import(Symbol p) {
359: }
360: \end{verbatim}
361: \verb|print| is a front-end function similar to the standard \verb|printf|.
362:
363: \subsection{\tt segment}
364:
365: \label{segment}
366: The front end manages four logical segments:
367: \verb|CODE|, \verb|BSS|, \verb|DATA|, and \verb|LIT|.
368: Executable code is emitted into the \verb|CODE| segment,
369: uninitialized variables are defined in the \verb|BSS| segment,
370: initialized variables are defined and initialized in the \verb|DATA| segment,
371: and constants appear in the \verb|LIT| segment.
372:
373: The front end announces a segment change by calling
374: \verb|segment(int s)| where \verb|s| is one of the segments listed above.
375: \verb|segment| maps the logical segments onto the segments
376: provided by the target machine. The \verb|CODE| and \verb|LIT| segments
377: can be mapped to read-only segments; the others must be mapped to read/write segments.
378: The sample mapping is
379: \begin{verbatim}
380: static void segment(int s) {
381: switch (s) {
382: case CODE: print(".text\n"); break;
383: case LIT: print(".text 1\n"); break;
384: case DATA:
385: case BSS: print(".data\n"); break;
386: }
387: }
388: \end{verbatim}
389:
390: \subsection{\tt global}
391:
392: \label{global}
393: \verb|global(Symbol p)| emits code to define a global variable.
394: The front end will have already directed the definition
395: to the appropriate logical segment by calling \verb|segment| and
396: set \verb|p->u.seg| to that segment,
397: and it will follow the call to \verb|global|
398: with any appropriate calls to the data initialization functions.
399: \verb|global| handles the necessary alignment adjustments and
400: the actual definition.
401:
402: The sample definition for global \verb|y| is simply
403: \verb|y|'s \verb|x.name| field preceded by an alignment directive, if necessary:
404: \begin{verbatim}
405: static void global(Symbol p) {
406: switch (p->type->align) {
407: case 2: print(".align 1; "); break;
408: case 4: print(".align 2; "); break;
409: case 8: print(".align 3; "); break;
410: }
411: print("%s:", p->x.name);
412: }
413: \end{verbatim}
414:
415: \subsection{\tt defconst}
416:
417: \label{defconst}
418:
419: \verb|defconst(int ty, Value v)| emits the scalar \verb|v|.
420: \verb|ty| indicates which field of
421: \verb|v| is to be emitted according the following table.
422:
423: \begin{center}
424: \begin{tabular}{lll}
425: \tt ty & \tt v \it field & \it type \\ \hline
426: \tt C & \tt v.uc & character \\
427: \tt S & \tt v.us & short \\
428: \tt I & \tt v.i & int \\
429: \tt U & \tt v.u & unsigned \\
430: \tt P & \tt v.p & any pointer type \\
431: \tt F & \tt v.f & float \\
432: \tt D & \tt v.d & double \\
433: \end{tabular}
434: \end{center}
435: The codes \verb|S|, \verb|I|, \ldots\ are identical to the type suffixes
436: used for the dag operators, which are described in Section~\ref{dags}.
437: The signed fields \verb|v.sc| and \verb|v.ss| can be used instead
438: of \verb|v.uc| and \verb|v.us|, but \verb|defconst|
439: must initialize only the specified number of bits.
440:
441: The sample \verb|defconst| is
442: \begin{verbatim}
443: static void defconst(int ty, Value v) {
444: switch (ty) {
445: case C: print(".byte %d\n", v.uc); break;
446: case S: print(".word %d\n", v.us); break;
447: case I: print(".long %d\n", v.i ); break;
448: case U: print(".long 0x%x\n", v.u ); break;
449: case P: print(".long 0x%x\n", v.p ); break;
450: case F:
451: print(".long 0x%x\n", ((unsigned *) &v.f)[0]);
452: break;
453: case D:
454: print(".long 0x%x,0x%x\n", ((unsigned *) &v.d)[0],
455: ((unsigned *) &v.d)[1]);
456: break;
457: }
458: }
459: \end{verbatim}
460: In the production compilers, \verb|defconst| accommodates cross-compilation,
461: so it corrects for different representations and byte orders.
462:
463: If \verb|ty| is \verb|P|, \verb|v.p| holds a numeric constant of some pointer type.
464: These originate from declarations like \verb|char *p=(char *)0xF0|.
465: \verb|defaddress| emits addresses relative to a symbol.
466:
467: Few ANSI~C compilers can leave the encoding of floating-point constants
468: to the assembler, because few assemblers can cope with the effect of
469: casts on these constants. For example, the correct initialization for
470: \begin{verbatim}
471: double x = (float)0.3;
472: \end{verbatim}
473: is \verb|.long 0x999a3f99,0x0|.
474: The directive \verb|.double 0.3| would erroneously initialize \verb|x|
475: to the equivalent of
476: \begin{verbatim}
477: .long 0x99993f99,0x0999a9999
478: \end{verbatim}
479: because it cannot represent the effect of the cast.
480:
481:
482: \subsection{{\tt defstring}, {\tt defaddress}, and \tt space}
483:
484: \label{defstring}
485: \label{defaddress}
486: \label{space}
487:
488: \verb|defstring(int len, char *s)| emits code to initialize
489: a string of length \verb|len| to the characters in \verb|s|.
490: The front end converts escape sequences, like \verb|\n|, into
491: the corresponding ASCII characters.
492:
493: \verb|defaddress(Symbol p)| emits the address denoted by \verb|p|.
494: \verb|space(int n)| emits code to allocate \verb|n| zero bytes.
495:
496: The sample \verb|defstring|, \verb|defaddress|, and \verb|space| are
497: \begin{verbatim}
498: static void defstring(int len, char *s) {
499: while (len-- > 0)
500: print(".byte %d\n", *s++);
501: }
502:
503: static void defaddress(Symbol p) {
504: print(".long %s\n", p->x.name);
505: }
506:
507: static void space(int n) {
508: print(".space %d\n", n);
509: }
510: \end{verbatim}
511:
512:
513: \section{Functions}
514:
515: The front end completely consumes each function before passing any part
516: of the function to the back end. This organization permits certain
517: optimizations. For example, only by processing complete functions can
518: the front end identify the locals and parameters whose address is not taken; only
519: these variables may be assigned to registers.
520:
521: \subsection{\tt function}
522:
523: \label{function}
524:
525: The front end accumulates functions into private data structures. At
526: the end of each function, it calls \verb|function| to generate and emit
527: code. The typical form of \verb|function| is
528: \begin{flushleft}\tt
529: \verb|void function(Symbol f, Symbol caller[], Symbol callee[], int ncalls) {| \\
530: \ \ \ \ldots {\rm initialize} \\
531: \ \ \ gencode(caller, callee); \\
532: \ \ \ \ldots {\rm emit prologue} \\
533: \ \ \ emitcode(); \\
534: \ \ \ \ldots {\rm emit epilogue} \\
535: \verb|}|
536: \end{flushleft}
537: \verb|gencode| is a front-end routine that traverses the front end's
538: private structures and passes each dag to the back end's \verb|gen|
539: (see Section~\ref{gen}), which selects code, annotates the dag to
540: record its selection, and returns a dag pointer. \verb|emitcode| is a
541: front-end routine that traverses the private structures again and
542: passes each of the pointers from \verb|gen| to \verb|emit| (see
543: Section~\ref{emit}), which emits the code.
544:
545: This organization offers the back end flexibility in
546: generating function prologue and epilogue code.
547: Before calling \verb|gencode|, \verb|function| initializes
548: the \verb|Xsymbol| fields of the function's parameters, as described
549: below, and does other per-function initializations, if necessary.
550: After calling \verb|gencode|, the size of the activation record,
551: or {\em frame}, the number of registers used, etc.\ are known;
552: this information is usually needed to emit the prologue.
553: After calling \verb|emitcode| to emit the code for the body of the function,
554: \verb|function| emits the epilogue.
555:
556: The argument \verb|f| to \verb|function| is the pointer
557: to the symbol-table entry for the current function,
558: and \verb|ncalls| is the number of calls to other functions
559: made by the current function. \verb|ncalls| is useful
560: on targets like the SPARC where `leaf' functions get special treatment.
561:
562: \verb|caller| and \verb|callee| are arrays of pointers to symbol
563: table entries; each is terminated with a zero pointer.
564: The symbols in \verb|caller| are the function parameters
565: as passed by a caller; those in \verb|callee| are the parameters
566: as seen within the function. For most functions,
567: the symbols in each array are the same, but they
568: can differ in both \verb|sclass| and \verb|type|.
569: For example, in
570: \begin{verbatim}
571: foo(x) float x; { ... }
572: \end{verbatim}
573: a call to \verb|foo| passes the actual argument as a double.
574: Within \verb|foo|, \verb|x| is a float.
575: Thus, \verb|caller[0]->type| refers to `double' and \verb|callee[0]->type|
576: refers to `float.' And in
577: \begin{verbatim}
578: int strlen(register char *s) { ... }
579: \end{verbatim}
580: \verb|caller[0]->sclass| is \verb|AUTO| and \verb|callee[0]->sclass| is \verb|REGISTER|.
581: Even without register declarations, the front end assigns
582: frequently referenced parameters to the \verb|REGISTER| class,
583: and \verb|callee|'s \verb|sclass| is set accordingly.
584: This assignment is made only when there are no explicit register {\em locals}
585: to avoid interfering with the programmer's intentions (see Section~\ref{local}).
586:
587: \verb|caller| and \verb|callee| are passed to \verb|gencode|.
588: If \verb|caller[i]->type| is not equal to \verb|callee[i]->type|
589: or if \verb|caller[i]->sclass| is not equal to \verb|callee[i]->sclass|,
590: \verb|gencode| generates an assignment of \verb|caller[i]|
591: to \verb|callee[i]|. If the types are not equal, this assignment
592: may include a conversion; for example, the assignment to \verb|x| in
593: \verb|foo| includes a truncation of a double to a float.
594: For parameters that include register declarations, \verb|function|
595: must assign a register and initialize the \verb|x| field accordingly,
596: or change the \verb|callee|'s \verb|sclass| to \verb|AUTO|.
597:
598: \verb|function| could also change \verb|callee[i]->sclass| from \verb|AUTO|
599: to \verb|REGISTER| if it wished to assign a register to that parameter.
600: On the MIPS, for example, some of the parameters are passed in registers,
601: so \verb|function| assigns those registers to the corresponding
602: \verb|callee|s in leaf functions. If, however, \verb|callee[i]->addressed| is set,
603: the address of the parameter is taken in the function body,
604: and it must be stored in memory on most machines.
605:
606: Initialization of the \verb|Xsymbol| fields of the symbols
607: in \verb|caller| and \verb|callee| depends on the frame layout,
608: which is target specific. Figure~\ref{fig:frame} shows the layout
609: of the VAX frame. The stack grows towards
610: lower addresses and towards the top of the page.
611:
612: \begin{figure}
613: \begin{center}
614: \setlength{\unitlength}{12pt}
615: \begin{picture}(10,16)
616: \thinlines
617:
618: \put( 0,14){\makebox(10, 2){argument build area}}
619: \put( 0,14){\line( 1, 0){10}}
620: \put(13,15.5){\vector(-1,0){3}}\put(13,15){\makebox(1.5,1){\tt sp}}
621: \put( 0,10){\makebox(10, 4){locals}}
622: \put( 0,10){\line( 1, 0){10}}
623: \put( 0, 9){\makebox(10, 1){\tt 0}}
624: \put( 0, 9){\line( 1, 0){10}}
625: \put(13, 9.5){\vector(-1,0){3}}\put(13, 9){\makebox(1.5,1){\tt fp}}
626: \put( 0, 8){\makebox(10, 1){\sc psw}}
627: \put( 0, 8){\line( 1, 0){10}}
628: \put( 0, 7){\makebox(10, 1){previous \tt ap}}
629: \put( 0, 7){\line( 1, 0){10}}
630: \put( 0, 6){\makebox(10, 1){previous \tt fp}}
631: \put( 0, 6){\line( 1, 0){10}}
632: \put( 0, 5){\makebox(10, 1){previous \tt pc}}
633: \put( 0, 5){\line( 1, 0){10}}
634: \put( 0, 3){\makebox(10, 2){saved registers}}
635: \put( 0, 3){\line( 1, 0){10}}
636: \put( 0, 2){\makebox(10, 1){argument count}}
637: \put( 0, 2){\line( 1, 0){10}}
638: \put(13, 2.5){\vector(-1,0){3}}\put(13, 2){\makebox(1.5,1){\tt ap}}
639: \put( 0, 0){\makebox(10, 2){actual arguments}}
640:
641: \thicklines
642: \put( 0, 0){\line( 1, 0){10}}
643: \put( 0, 0){\line( 0, 1){16}}
644: \put(10,16){\line( 0,-1){16}}
645: \put(10,16){\line(-1, 0){10}}
646:
647: \end{picture}
648: \end{center}
649: \caption{VAX Frame Layout.\label{fig:frame}}
650: \end{figure}
651:
652: Arguments are referenced by displacement-mode addressing
653: with positive offsets from register \verb|ap|, so
654: the first argument is at address \verb|4(ap)|. Locals are referenced
655: via negative offsets from \verb|fp|, e.g., the first local is at \verb|-4(fp)|.
656: The `argument build area' is used to store arguments to functions that are
657: called by the current function. The front end `un-nests' calls so that
658: the back end does not need to deal with nested calls. The argument build area
659: can thus be used for all calls and must be large enough to hold the largest
660: argument list. When a function is called, the caller's argument build area
661: becomes the callee's `actual arguments'.
662:
663: Typical VAX calling sequences can handle nested calls,
664: so using an argument build area is not strictly necessary.
665: But other targets, such as the MIPS, require this approach,
666: so it's used here to illustrate the technique. This approach also
667: has the advantage that stack overflow can occur only at function
668: entry, which is useful on targets that require explicit
669: prologue code to detect stack overflow.
670:
671: The sample version of \verb|function| is
672: \begin{verbatim}
673: static int framesize; /* size of activation record */
674: static int offset; /* current frame offset */
675: static int argbuildsize; /* size of argument build area */
676:
677: \end{verbatim}
678: \begin{verbatim}
679: static void function(Symbol f, Symbol caller[],
680: Symbol callee[], int ncalls) {
681: int i;
682:
683: offset = 4;
684: for (i = 0; caller[i] && callee[i]; i++) {
685: offset = roundup(offset, caller[i]->type->align);
686: callee[i]->x.offset = caller[i]->x.offset = offset;
687: callee[i]->x.name = caller[i]->x.name = stringf("%d(ap)", offset);
688: offset += caller[i]->type->size;
689: callee[i]->sclass = AUTO;
690: }
691: usedmask = argbuildsize = framesize = offset = 0;
692: gencode(caller, callee);
693: print("%s:.word 0x%x\n", f->x.name, usedmask&~0x3f);
694: framesize += 4*nregs + argbuildsize;
695: print("subl2 $%d,sp\n", framesize);
696: if (isstruct(freturn(f->type)))
697: print("movl r1,-4(fp)\n");
698: emitcode();
699: if (glevel > 1)
700: print("ret\n");
701: }
702: \end{verbatim}
703: The VAX \verb|calls| instruction saves the general registers specified
704: by the entry mask, \verb|ap|, \verb|fp|,
705: and the return address, \verb|pc|, as shown in the frame figure above.
706: \verb|function| computes the size of the locals and argument build area,
707: given by \verb|framesize| and \verb|argbuildsize|, respectively.
708:
709: The first part of \verb|function| initializes the \verb|x.offset| and \verb|x.name| fields
710: of each \verb|caller| and \verb|callee| symbol to the appropriate offset and name, respectively.
711: The running \verb|offset| is rounded up to the alignment for each argument.
712: \verb|roundup(n,m)| is a front-end macro that returns \verb|n| rounded up to the
713: next multiple of \verb|m|. Depending on the type metrics, the size of an
714: argument may not be a multiple of longwords (e.g., 3-byte structures),
715: but the front end ensures that the minimum alignment for each \verb|caller[i]|
716: is that for integers, which keeps the VAX stack longword-aligned.
717: \verb|stringd(n)| is a front-end function that returns the string
718: representation of the integer \verb|n|.
719:
720: This version of \verb|function| does not support register
721: declarations, so each \verb|callee|'s storage \verb|sclass| is
722: set to \verb|AUTO|.
723:
724: During code generation, \verb|argbuildsize| is increased when
725: code for calls is generated (see Section~\ref{gen}), \verb|offset| is adjusted in response
726: to the definition of locals and block boundaries,
727: and \verb|framesize| records \verb|offset|'s maximum
728: (see Sections~\ref{local} and \ref{blockbeg}).
729: Before calling \verb|gencode|, \verb|function| clears
730: \verb|usedmask|, which records the registers used in the function body,
731: and clears \verb|argbuildsize|, \verb|framesize|, and \verb|offset|.
732:
733: After \verb|gencode| returns, \verb|usedmask| and \verb|framesize|
734: hold the information needed to generate the prologue.
735: \verb|framesize| is adjusted to include the argument build area
736: and space for saving all of the registers.
737: This space, which is in addition to that specified by the register save mask,
738: is used to save registers across those instructions that
739: destroy fixed registers, e.g., \verb|movc3|.
740: The \verb|subl2| instruction allocates the remainder of the frame.
741:
742: The last instruction of the prologue is emitted only for
743: functions that return structures. For a function type \verb|ty|,
744: \verb|freturn(ty)| gives the type of the value returned by the function,
745: and \verb|isstruct(ty)| is true if \verb|ty| is a structure or union type.
746: Section~\ref{dags:calls} gives details on returning structures.
747:
748: If \verb|JUMP_ON_RETURN| had been defined as \verb|1| in the configuration,
749: returns would have been followed by a jump to the label
750: that follows the code emitted by \verb|emitcode|. If the front
751: end is passed the \verb|-g|$n$ option, it sets the global
752: variable \verb|glevel| to $n$
753: and behaves as if \verb|JUMP_ON_RETURN| is \verb|1|, so the code
754: above emits the necessary \verb|ret| instruction at the end
755: of each function.
756:
757: \subsection{\tt local}
758:
759: \label{local}
760:
761: During the execution of \verb|gencode|, the front end announces local
762: variables by calling \verb|local(Symbol p)|, where \verb|p| points the
763: relevant symbol-table entry. It announces temporaries likewise; these
764: have \verb|p->temporary| set. \verb|local| must initialize \verb|p|'s
765: \verb|Xsymbol| fields. That is, it must set \verb|p->x.offset| and \verb|p->x.name|
766: so that they identify a
767: stack offset or register number, depending on the availability of
768: registers and on the value of \verb|p->sclass|, which is \verb|AUTO| or
769: \verb|REGISTER|.
770:
771: For each block, the front end first announces locals with explicit
772: register declarations, in order of declaration, to permit programmer
773: control of register assignment. Then it announces the rest, starting
774: with those that appear to be most frequently referenced. It assigns
775: \verb|REGISTER| class to even these locals {\em if} their address
776: is never taken and if their estimated frequency of use exceeds two.
777: This announcement order and \verb|sclass| override collaborate to put the most
778: promising locals in registers even if no registers were declared. As
779: with parameters, \verb|local| could assign a register to \verb|p| and
780: change \verb|p->sclass| from \verb|AUTO| to \verb|REGISTER|, but it
781: should do so only if \verb|p->addressed| is not set.
782:
783: If \verb|p->sclass| is \verb|REGISTER|, \verb|local|
784: can decline to allocate a register by setting \verb|p->sclass| to \verb|AUTO|
785: and initializing \verb|p->x.offset| and \verb|p->x.name| to the appropriate frame offset
786: and address string, respectively.
787: This choice is illustrated by the sample version:
788: \begin{verbatim}
789: static void local(Symbol p) {
790: offset = roundup(offset + p->type->size, p->type->align);
791: offset = roundup(offset, 4);
792: p->x.offset = -offset;
793: p->x.name = stringf("%d(fp)", -offset);
794: p->sclass = AUTO;
795: }
796: \end{verbatim}
797: The second \verb|roundup| keeps \verb|offset| and hence the stack
798: aligned on longwords, as described above.
799:
800: \subsection{\tt address}
801:
802: \label{address}
803: The front end calls \verb|address(Symbol q, Symbol p, int n)| to
804: initialize \verb|q->x| to a symbol that represents an address of the form $x+{\tt n}$,
805: where $x$ is the address represented by \verb|p| and \verb|n| is positive or negative.
806: Like \verb|defsymbol|, \verb|address| initializes \verb|q->x|, but
807: does so based on the values of \verb|p->x| and \verb|n|.
808: The sample \verb|address| is
809: \begin{verbatim}
810: static void address(Symbol q, Symbol p, int n) {
811: if (p->scope == GLOBAL || p->sclass == STATIC || p->sclass == EXTERN)
812: q->x.name = stringf("%s%s%d", p->x.name, n >= 0 ? "+" : "", n);
813: else {
814: q->x.offset = p->x.offset + n;
815: q->x.name = stringf("%d(%s)", q->x.offset,
816: p->scope == PARAM ? "ap" : "fp");
817: }
818: }
819: \end{verbatim}
820: which computes \verb|q->x.offset| and \verb|q->x.name| for locals and parameters,
821: or sets \verb|q->x.name| to \verb|p->x.name| concatenated with \verb|+n| or \verb|-n|
822: for other variables.
823:
824: For example, in
825: \begin{verbatim}
826: struct node { struct node *link; int count; } a;
827: f() { int b[10]; b[4] = a.count; ... }
828: \end{verbatim}
829: suppose \verb|a| and \verb|b| point to the symbol-table entries
830: for \verb|a| and \verb|b|, respectively.
831: \verb|a->x.name| is set to \verb|"_a"| by \verb|defsymbol|, and
832: \verb|b->x.offset| and \verb|b->x.name| are set to, respectively,
833: \verb|-40| \verb|"-40(fp)"| by \verb|local|.
834: \verb|address(q1,a,4)| is called with \verb|q1| representing the address
835: of \verb|a.count|, and \verb|q1->x.name| is set to \verb|"_a+4"|.
836: Likewise, \verb|address(q2,b,16)| sets \verb|q2->x.offset|
837: and \verb|q2->x.name| to, respectively, \verb|-24| and \verb|"-24(fp)"|,
838: which together denote the address of \verb|b[4]|.
839:
840: \verb|address| accepts globals, parameters, and locals,
841: and is called only after these symbols have been initialized
842: by {\tt defsymbol}, {\tt function}, or {\tt local}.
843:
844: \subsection{{\tt blockbeg} and \tt blockend}
845:
846: \label{blockbeg}\label{blockend}
847: Source-language blocks bracket the lifetime of locals.
848: \verb|gencode| announces the beginning and end of a block
849: by calling \verb|blockbeg(Env *e)| and \verb|blockend(Env *e)|, respectively.
850: \verb|Env| is target specific and typically includes
851: the data necessary to reuse that portion of the local frame
852: space associated with the block
853: and to release any registers assigned to locals within the block.
854: The sample \verb|Env| is
855: \begin{verbatim}
856: typedef struct {
857: unsigned rmask;
858: int offset;
859: } Env;
860: \end{verbatim}
861: The fields save the values of \verb|rmask| and \verb|offset| at the beginning
862: of a block so that they can be restored on the end of the block.
863: The sample \verb|blockbeg| and \verb|blockend| are thus
864:
865: \noindent
866: \begin{minipage}[t]{.5\textwidth}
867: \vspace{\parskip}
868: \begin{verbatim}
869: static void blockbeg(Env *e) {
870: e->rmask = rmask;
871: e->offset = offset;
872: }
873: \end{verbatim}
874: \vspace{\parskip}
875: \end{minipage}
876: \begin{minipage}[t]{.5\textwidth}
877: \vspace{\parskip}
878: \begin{verbatim}
879: static void blockend(Env *e) {
880: if (offset > framesize)
881: framesize = offset;
882: offset = e->offset;
883: rmask = e->rmask;
884: }
885: \end{verbatim}
886: \vspace{\parskip}
887: \end{minipage}
888:
889: \noindent
890: \verb|blockend| also updates \verb|framesize| if the locals for the current
891: block require more space than previous blocks.
892: The sample could do without the \verb|rmask| field, but
893: if its \verb|local| assigned registers to locals, it would need
894: the field to release those registers.
895:
896: Temporaries --- locals with \verb|temporary| set --- to which
897: \verb|local| assigned registers live only for the expressions in which
898: they are used. They are announced by \verb|local| as usual, but are
899: used only in the dags passed to next call on \verb|gen|
900: (see~\ref{gen}). \verb|gen| can thus release all registers assigned to
901: temporaries.
902:
903:
904: \section{Dags}
905:
906: \label{dags}
907: Executable code is specified by dags. A function body is a sequence of
908: forests of dags, each of which is passed the back end via \verb|gen|,
909: as described below. Dag nodes, or simply nodes, are defined by
910: \begin{verbatim}
911: typedef struct node *Node;
912: struct node { /* dag nodes: */
913: Opcode op; /* operator */
914: short count; /* reference count */
915: Symbol syms[MAXSYMS]; /* symbols */
916: Node kids[MAXKIDS]; /* operands */
917: Node link; /* next dag in the forest */
918: Xnode x; /* back-end's type extension */
919: };
920: \end{verbatim}
921:
922: The \verb|kids| point to the operand nodes. Some operators also
923: take symbol table pointers as operands; these appear in the \verb|syms|
924: array. The default and minimum allowable value for both \verb|MAXKIDS|
925: and \verb|MAXSYMS| is \verb|2|; larger values can be defined for the
926: back end's convenience in the configuration file. \verb|count|
927: holds the number of references to this node from \verb|kids| in other
928: nodes. \verb|link| points to the root of the next dag in the forest.
929:
930: The \verb|x| field is the back end's `extension' to nodes. The
931: configuration defines the type \verb|Xnode| to hold the per-node data
932: that the back end needs to generate code. The sample \verb|Xnode| is
933: \begin{verbatim}
934: typedef struct {
935: int state;
936: unsigned visited:1; /* 1 if dag has been linearized */
937: int reg; /* register number */
938: unsigned rmask; /* unshifted register mask */
939: unsigned busy; /* busy regs */
940: int argoffset; /* ARG: argument offset */
941: Node next; /* next node on emit list */
942: } Xnode;
943: \end{verbatim}
944: Section~\ref{gen} describes the fields.
945:
946: The \verb|op| field holds an operator. The last character of each is a
947: {\em type suffix} from Table~\ref{dags:suffix-table}.
948: For example, the generic operator \verb|ADD| has the variants
949: \verb|ADDI|, \verb|ADDU|, \verb|ADDP|, \verb|ADDF|, and \verb|ADDD|.
950:
951: \begin{table}
952: \begin{center}
953: \begin{tabular}{lll}
954: \em type suffix & \em type \\ \hline
955: \tt C & char \\
956: \tt S & short \\
957: \tt I & int \\
958: \tt U & unsigned \\
959: \tt P & any pointer type \\
960: \tt F & float \\
961: \tt D & double \\
962: \tt B & structure or block \\
963: \tt V & void \\
964: \end{tabular}
965: \end{center}
966: \caption{Type Suffixes.\label{dags:suffix-table}}
967: \end{table}
968:
969: Table~\ref{dags:op-table} lists each generic operator, its valid type
970: suffixes, and the number of \verb|kids| and \verb|syms| that it uses;
971: multiple values for \verb|kids| indicate type-specific variations,
972: which are detailed below. For most operators, the type suffix denotes
973: the type of operation to perform and the type of the result.
974: Exceptions are \verb|ADDP|, in which an integer operand
975: is added to a pointer operand, and \verb|SUBP|, which
976: subtracts the second integer operand from the first pointer operand.
977: The operators for assignment, comparison, arguments, and some calls return
978: no results; their type suffixes denote the type of operation to perform.
979:
980: \begin{table}
981: \begin{center}
982: \begin{tabular}{lllll}
983: \tt syms & \tt kids & \it operator & \it type suffixes & \it operation \\ \hline
984: 1 & 0 & \tt ADDRF & \verb| P | & address of a parameter \\
985: 1 & 0 & \tt ADDRG & \verb| P | & address of a global \\
986: 1 & 0 & \tt ADDRL & \verb| P | & address of a local\\
987: 1 & 0 & \tt CNST & \verb|CSIUPFD | & constant \\[1.5ex]
988:
989: & 1 & \tt BCOM & \verb| U | & bitwise complement \\
990: & 1 & \tt CVC & \verb| IU | & convert from \tt char \\
991: & 1 & \tt CVD & \verb| I F | & convert from \tt double \\
992: & 1 & \tt CVF & \verb| D | & convert from \tt float \\
993: & 1 & \tt CVI & \verb|CS U D | & convert from \tt int \\
994: & 1 & \tt CVP & \verb| U | & convert from pointer \\
995: & 1 & \tt CVS & \verb| IU | & convert from \tt short \\
996: & 1 & \tt CVU & \verb|CSI P | & convert from \tt unsigned \\
997: & 1 & \tt INDIR & \verb|CSI PFDB | & fetch \\
998: & 1 & \tt NEG & \verb| I FD | & negation \\[1.5ex]
999:
1000: & 2 & \tt ADD & \verb| IUPFD | & addition \\
1001: & 2 & \tt BAND & \verb| U | & bitwise \sc AND \\
1002: & 2 & \tt BOR & \verb| U | & bitwise inclusive \sc OR \\
1003: & 2 & \tt BXOR & \verb| U | & bitwise exclusive \sc OR \\
1004: & 2 & \tt DIV & \verb| IU FD | & division \\
1005: & 2 & \tt LSH & \verb| IU | & left shift \\
1006: & 2 & \tt MOD & \verb| IU | & modulus \\
1007: & 2 & \tt MUL & \verb| IU FD | & multiplication \\
1008: & 2 & \tt RSH & \verb| IU | & right shift \\
1009: & 2 & \tt SUB & \verb| IUPFD | & subtraction \\[1.5ex]
1010:
1011: 2 & 2 & \tt ASGN & \verb|CSI PFDB | & assignment \\
1012: 1 & 2 & \tt EQ & \verb| I FD | & jump if equal \\
1013: 1 & 2 & \tt GE & \verb| IU FD | & jump if greater than or equal \\
1014: 1 & 2 & \tt GT & \verb| IU FD | & jump if greater than \\
1015: 1 & 2 & \tt LE & \verb| IU FD | & jump if less than or equal \\
1016: 1 & 2 & \tt LT & \verb| IU FD | & jump if less than \\
1017: 1 & 2 & \tt NE & \verb| I FD | & jump if not equal \\[1.5ex]
1018:
1019: 2 & 1 & \tt ARG & \verb| I PFDB | & argument \\
1020: 1 & 1 2 & \tt CALL & \verb| I FDBV| & function call \\
1021: & 0 1 & \tt RET & \verb| I FD V| & return from function \\[1.5ex]
1022:
1023: & 1 & \tt JUMP & \verb| V| & unconditional jump \\
1024: 1 & 0 & \tt LABEL & \verb| V| & label definition \\
1025: \end{tabular}
1026: \end{center}
1027: \caption{Node Operators.\label{dags:op-table}}
1028: \end{table}
1029:
1030: The leaf operators yield the address of a variable or the value of a
1031: constant. \verb|syms[0]| identifies the variable or constant.
1032:
1033: The unary operators accept and yield a number, except for \verb|INDIR|,
1034: which accepts an address and yields the value at that address.
1035: There is no \verb|BCOMI|; signed integers are complemented using
1036: \verb|BCOMU|. The binary operators accept two numbers and yield one.
1037:
1038: The type suffix for a conversion operator denotes the type of the
1039: result. For example, \verb|CVUI| converts an unsigned (\verb|U|) to an
1040: signed integer (\verb|I|). Conversions between unsigned and short and
1041: between unsigned and character are unsigned conversions; those between
1042: integer and short and between integer and character are signed
1043: conversions. For example, \verb|CVSU| converts an unsigned short to an
1044: unsigned while \verb|CVSI| converts an signed short to a signed
1045: integer.
1046:
1047: The front end composes conversions to form those not in the table.
1048: For example, it converts a short to a float by first
1049: converting it to an int and then a double. The 16
1050: conversion operators are represented by arrows in Figure~\ref{fig:conversions}.
1051: Composed conversions follow the path from the source
1052: type to the destination type.
1053:
1054: \begin{figure}
1055: \begin{center}
1056: \setlength{\unitlength}{7pt}
1057: \begin{picture}(20,12)
1058: \multiput(1,2)(6,0){3}{\begin{picture}(0,3)
1059: \put(0,0){\vector(0,1){3}}\put(0,0){\vector(0,-1){0}}\end{picture}}
1060: \multiput(7,7)(6,0){2}{\begin{picture}(0,3)
1061: \put(0,0){\vector(0,1){3}}\put(0,0){\vector(0,-1){0}}\end{picture}}
1062: \multiput(2,6)(6,0){3}{\begin{picture}(4,0)
1063: \put(0,0){\vector(1,0){4}}\put(0,0){\vector(-1,0){0}}\end{picture}}
1064: \put( 1, 1){\makebox(0,0){\tt F}}
1065: \put( 7, 1){\makebox(0,0){\tt S}}
1066: \put(13, 1){\makebox(0,0){\tt S}}
1067:
1068: \put( 1, 6){\makebox(0,0){\tt D}}
1069: \put( 7, 6){\makebox(0,0){\tt I}}
1070: \put(13, 6){\makebox(0,0){\tt U}}
1071: \put(19, 6){\makebox(0,0){\tt P}}
1072:
1073: \put( 7,11){\makebox(0,0){\tt C}}
1074: \put(13,11){\makebox(0,0){\tt C}}
1075: \end{picture}
1076: \end{center}
1077: \vspace{-1.5pc}\small\em
1078: \caption{Conversions~\label{fig:conversions}}
1079: \end{figure}
1080:
1081: There is no \verb|CVUD|; conversion of an unsigned \verb|u| to a double
1082: is done by the equivalent of the expression
1083: \begin{verbatim}
1084: (int)u >= 0 ? (double)(int)u : (double)(int)u + UINT_MAX + 1
1085: \end{verbatim}
1086: where \verb|UINT_MAX| is the ANSI-specified maximum value for an unsigned.
1087: Likewise, there is no \verb|CVDU|; conversion of a double \verb|d| to an unsigned
1088: is done by the equivalent of the expression
1089: \begin{verbatim}
1090: d >= INT_MAX + 1 ? (unsigned)(int)(d-(INT_MAX+1)) + INT_MAX + 1
1091: : (unsigned)(int)d
1092: \end{verbatim}
1093: where \verb|INT_MAX| is the ANSI-specified maximum value for a signed integer.
1094:
1095: \verb|ASGN| stores the value of \verb|kids[1]| in the cell addressed by
1096: \verb|kids[0]|. \verb|syms[0]| and \verb|syms[1]| point to symbol table
1097: entries for integer constants that give the size of the value and
1098: its alignment, respectively. These are most useful for \verb|ASGNB|,
1099: which implements structure assignment and other
1100: `block moves' (e.g., initialization of automatic arrays).
1101:
1102: For the comparisons, \verb|syms[0]| points to a symbol-table entry for
1103: the label to jump to if the comparison is true. \verb|JUMPV| is an
1104: unconditional jump to the address computed by \verb|kids[0]|. \verb|LABEL|
1105: defines the label given by \verb|syms[0]| and is otherwise a no-op.
1106: As on most computers, signed comparisons are used for unsigned equals and not equals.
1107:
1108: Function calls have a \verb|CALL| node preceded by zero or more
1109: \verb|ARG| nodes. The front end `un-nests'
1110: function calls, so \verb|ARG| nodes are always associated with the next
1111: \verb|CALL| node in the forest. The order of the \verb|ARG| nodes is
1112: right-to-left unless the configuration parameter \verb|LEFT_TO_RIGHT|
1113: is defined, which it is for the sample.
1114: A \verb|CALL| node's \verb|syms[0]| points to a symbol
1115: whose only non-null field is \verb|type|,
1116: which is the function type of the callee.
1117:
1118: \verb|ARG| nodes establish the value computed by \verb|kids[0]| as the
1119: next argument. \verb|syms[0]| and \verb|syms[1]| point to symbol table
1120: entries for integer constants that give the size of the argument and
1121: its alignment, respectively.
1122:
1123: \label{dags:calls}
1124:
1125: In \verb|CALL| nodes, \verb|kids[0]| computes the address of the callee.
1126: \verb|CALLB| calls functions that return structures;
1127: \verb|kids[1]| computes the address of a
1128: temporary local variable to hold the returned value. There is no
1129: \verb|RETB|; the front end uses a \verb|RETV| preceded by an
1130: \verb|ASGNB| to the structure addressed by the first local. The
1131: \verb|CALLB| code and the function prologue must collaborate to store the
1132: \verb|CALLB|'s \verb|kids[1]| into the callee's first local.
1133: \verb|function| (Section~\ref{function}), \verb|local| (Section~\ref{local})
1134: and the code emitted below for \verb|CALLB| (Section~\ref{emit})
1135: illustrate such collaboration.
1136: \verb|CALLB| nodes have a \verb|count| of \verb|0| because the front end references
1137: the temporary wherever the returned value is referenced.
1138:
1139: In \verb|RET| nodes, \verb|kids[0]| computes the value returned, except
1140: for \verb|RETV| nodes, which are childless.
1141:
1142: Character and short integer arguments are always promoted to the
1143: corresponding integer type even in the presence of a prototype.
1144: The promoted values are converted back to the intended
1145: type upon entry to the function. The front end accomplishes
1146: this conversion by specifying the intended types for the callee
1147: as described in Section~\ref{function}.
1148: For example, the body for
1149: \begin{verbatim}
1150: f(char c) { f(c); }
1151: \end{verbatim}
1152: becomes two forests, which are linearized below;
1153: the \verb|syms| columns list the \verb|x.name| fields.
1154: \begin{verbatim}
1155: # op count kids syms
1156: 1. ADDRFP 1 4(ap)
1157: 2. ADDRFP 1 4(ap)
1158: 3. INDIRI 1 2
1159: 4. CVIC 1 3
1160: 5. ASGNC 0 1 4
1161:
1162: 1. ADDRFP 1 4(ap)
1163: 2. INDIRC 1 1
1164: 3. CVCI 1 2
1165: 4. ARGI 0 3 4 4
1166: 5. ADDRGP 1 _f
1167: 6. CALLI 0 5 4
1168: \end{verbatim}
1169: The first forest holds one dag, which converts the actual argument to the
1170: intended type. The second forest holds two dags.
1171: The first (nodes 1--4) promotes \verb|c| to pass it as an integer,
1172: and the second (nodes 5 \& 6) calls \verb|f|.
1173:
1174: Unsigned variants of \verb|ASGN|, \verb|INDIR|, \verb|ARG|,
1175: \verb|CALL|, and \verb|RET| were omitted as unnecessary. Signed and
1176: unsigned integers have the same size, so the corresponding signed
1177: operator is used instead. Likewise, there is no \verb|CALLP| or
1178: \verb|RETP|. A pointer is returned by using \verb|CVPU| and
1179: \verb|RETI|. A pointer-valued function is called by using \verb|CALLI|
1180: and \verb|CVUP|.
1181:
1182: In Table~\ref{dags:op-table}, the operators listed at and following \verb|ASGN|
1183: are used for their side-effects. They always appear as roots in the
1184: forest of dags, and they appear in the order in which they must be executed.
1185: Except for \verb|CALLD|, \verb|CALLF| and \verb|CALLI|, their reference
1186: counts are always zero. Even these \verb|CALL| nodes have zero
1187: reference counts when their values are unused.
1188:
1189: \subsection{\tt gen}
1190:
1191: \label{gen}
1192: \label{dags:registers}
1193: The front end calls \verb|gen| to select code. It passes \verb|gen| a
1194: forest of dags. For example,
1195: \begin{verbatim}
1196: int i, *p; f() { i = *p++; }
1197: \end{verbatim}
1198: yields the forest linearized below.
1199: \begin{verbatim}
1200: # op count kids syms
1201: 1. ADDRGP 2 _p
1202: 2. INDIRP 2 1
1203: 3. CNSTI 1 4
1204: 4. ADDP 1 2 3
1205: 5. ASGNP 0 1 4
1206: 6. ADDRGP 1 _i
1207: 7. INDIRI 1 2
1208: 8. ASGNI 0 6 7
1209: \end{verbatim}
1210: This forest consists of three dags, rooted at nodes 2, 5, and 8 above.
1211: The \verb|INDIRP| node, which fetches the value of \verb|p|, comes
1212: before node 5, which changes \verb|p|, so the original value of
1213: \verb|p| is available for subsequent use by node 7, which fetches the
1214: integer pointed to by that value.
1215:
1216: \verb|gen| traverses the forest and selects code, but it
1217: emits nothing because it may be necessary to determine, for example,
1218: the registers needed before the function prologue
1219: can be emitted (see Section~\ref{function}).
1220: So \verb|gen| merely annotates the nodes to identify the code selected,
1221: and it returns a pointer that is ultimately passed to the back end's
1222: \verb|emit| to actually output the code. Once the front end calls
1223: \verb|gen|, it does not inspect the contents of the nodes again, so
1224: \verb|gen| may modify them freely.
1225:
1226: The sample code generator emits naive code, so \verb|gen| concerns
1227: itself mainly with register allocation.
1228: The sample \verb|gen|
1229: \begin{verbatim}
1230: static Node gen(Node p) {
1231: Node head, *last;
1232:
1233: for (last = &head; p; p = p->link)
1234: last = linearize(p, last, 0);
1235: for (p = head; p; p = p->x.next) {
1236: ralloc(p);
1237: if (p->count == 0 && sets(p))
1238: putreg(p);
1239: }
1240: return head;
1241: }
1242: \end{verbatim}
1243: linearizes each dag in the forest, in execution order, and then
1244: allocates registers for each node. If the node sets a register, but no
1245: subsequent node references it, which is indicated by a reference
1246: \verb|count| of \verb|0|, \verb|gen| releases the register. Finally,
1247: it returns the linearized node list for traversal by \verb|emit|.
1248:
1249: \verb|gen| linearizes the dags before allocating registers to simplify
1250: the insertion of spills and reloads. The function
1251: \begin{verbatim}
1252: static Node *linearize(Node p, Node *last, Node next) {
1253: if (p && !p->x.visited) {
1254: last = linearize(p->kids[0], last, 0);
1255: last = linearize(p->kids[1], last, 0);
1256: p->x.visited = 1;
1257: *last = p;
1258: last = &p->x.next;
1259: }
1260: *last = next;
1261: return last;
1262: }
1263: \end{verbatim}
1264: linearizes the dag at \verb|p| and inserts it into the growing list of
1265: nodes between \verb|*last| and \verb|next|.
1266:
1267: \verb|ralloc| handles register allocation for a single node.
1268: \begin{verbatim}
1269: static void ralloc(Node p) {
1270: int i;
1271:
1272: switch (generic(p->op)) {
1273: case ARG:
1274: argoffset = roundup(argoffset, p->syms[1]->u.c.v.i);
1275: p->x.argoffset = argoffset;
1276: argoffset += p->syms[0]->u.c.v.i;
1277: if (argoffset > argbuildsize)
1278: argbuildsize = roundup(argoffset, 4);
1279: break;
1280: case CALL:
1281: argoffset = 0;
1282: break;
1283: }
1284: for (i = 0; i < MAXKIDS; i++)
1285: putreg(p->kids[i]);
1286: p->x.busy = rmask;
1287: if (needsreg(p))
1288: getreg(p);
1289: }
1290: \end{verbatim}
1291: \verb|generic| strips the type suffix from an operator and
1292: thus simplifies the switch. \verb|ralloc| calls \verb|putreg| to
1293: release the registers allocated for the node's children and then it
1294: calls \verb|getreg| to allocate a register for the node itself if it needs one. It sets
1295: the node's \verb|x.busy| to record the busy registers; \verb|emit|
1296: needs this information for a few operators. The register state is
1297: encoded in \verb|rmask|; \verb|rmask&(1<<r)| is \verb|1| if register
1298: \verb|r| is busy, for \verb|r| from \verb|0| to \verb|11|.
1299:
1300: \verb|CALL| and \verb|ARG| nodes require extra steps. \verb|ARG| nodes
1301: produce no result; instead, they store the value computed by
1302: \verb|kids[0]| into the next location in the argument build area.
1303: \verb|syms[0]| and \verb|syms[1]| point to constant symbols that give
1304: the size and alignment of the argument. \verb|argoffset| is the
1305: running offset into the argument build area.
1306: \verb|argoffset| is rounded up to the appropriate alignment boundary, saved
1307: in the node's \verb|x.argoffset| for use in \verb|emit|, and incremented
1308: by the size of the argument. \verb|argbuildsize| tracks the maximum
1309: \verb|argoffset| needed by the current function. The case for \verb|CALL| nodes
1310: clears \verb|argoffset| for the next set of \verb|ARG| nodes.
1311:
1312: \verb|getreg|
1313: accepts a node and allocates a register for it:
1314: \begin{verbatim}
1315: static void getreg(Node p) {
1316: int r, m = optype(p->op) == D ? 3 : 1;
1317:
1318: for (r = 0; r < nregs; r++)
1319: if ((rmask&(m<<r)) == 0) {
1320: p->x.rmask = m;
1321: p->x.reg = r;
1322: rmask |= sets(p);
1323: usedmask |= sets(p);
1324: return;
1325: }
1326: r = spillee(p, m);
1327: spill(r, m, p);
1328: getreg(p);
1329: }
1330: \end{verbatim}
1331: \verb|optype(op)| returns the type suffix of operator \verb|op|.
1332: \verb|m| is set to the mask \verb|1| if
1333: the result of \verb|p->op| needs an ordinary register and \verb|3| if it
1334: needs a double register.
1335: \verb|getreg| loops over the registers. If it finds one that's free,
1336: it sets the node's \verb|x.reg| field to the register allocated and the
1337: \verb|x.rmask| field to the mask. It also
1338: updates \verb|usedmask|, which is used to generate the prologue
1339: described in Section~\ref{function}; \verb|sets(p)| returns
1340: \verb|p->x.rmask<<p->x.reg|. If no registers are free, \verb|getreg|
1341: spills a register and calls itself recursively to try again.
1342: Section~\ref{spills} describes spills.
1343:
1344: \verb|putreg| releases registers:
1345: \begin{verbatim}
1346: static void putreg(Node p) {
1347: if (p && --p->count <= 0)
1348: rmask &= ~sets(p);
1349: }
1350: \end{verbatim}
1351: Dags can use result registers multiple times, so \verb|putreg|
1352: decrements the reference count and frees the register only when the
1353: last reference is removed by clearing the appropriate bits in
1354: \verb|rmask|.
1355:
1356: \subsection{\tt emit}
1357:
1358: \label{emit}
1359: \verb|emit| emits the linearized forest. The sample walks down the list,
1360: switches on the opcode to identify the code to emit:
1361: \begin{verbatim}
1362: void emit(Node p) {
1363: for (; p; p = p->x.next) {
1364: Node a = p->kids[0], b = p->kids[1];
1365: int r = p->x.reg;
1366: switch (p->op) {
1367: case CNSTC: case CNSTI: case CNSTP:
1368: case CNSTS: case CNSTU:
1369: print("movl $%s,r%d\n", p->syms[0]->x.name, r);
1370: break;
1371: case ADDRGP: case ADDRFP: case ADDRLP:
1372: print("moval %s,r%d\n", p->syms[0]->x.name, r);
1373: break;
1374: ...
1375: }
1376: }
1377: }
1378: \end{verbatim}
1379: The individual cases emit naive code for a single operator.
1380: The \verb|CNST| cases above emit a VAX instruction that loads a constant
1381: into a register. \verb|defsymbol| stored the constant string in
1382: \verb|p->syms[0]->x.name|, and \verb|ralloc| stored the result register
1383: name \verb|p->x.reg|. The \verb|ADDR| cases above emit a VAX
1384: instruction that moves the address of a variable into the result
1385: register.
1386:
1387: Most of the unary operators share a common pattern, which the sample
1388: abstracts into a macro:
1389: \begin{verbatim}
1390: #define suffix(p) ".fdbwllll."[optype((p)->op)]
1391: #define unary(inst) print("%s%c r%d,r%d\n", inst, suffix(p), a->x.reg, r)
1392: case BCOMU: unary("mcom" ); break;
1393: case NEGD: case NEGF: case NEGI: unary("mneg" ); break;
1394: case CVCI: unary("cvtb" ); break;
1395: case CVCU: unary("movzb"); break;
1396: case CVSI: unary("cvtw" ); break;
1397: case CVSU: unary("movzw"); break;
1398: case CVDF: case CVDI: unary("cvtd" ); break;
1399: case CVFD: unary("cvtf" ); break;
1400: case CVUC: case CVUS: unary("cvtl" ); break;
1401: case CVIC: case CVIS: case CVID: unary("cvtl" ); break;
1402: case CVIU: case CVUI: unary("mov" ); break;
1403: case CVPU: case CVUP: unary("mov" ); break;
1404: \end{verbatim}
1405: \verb|unary| emits the VAX operator, the VAX type suffix --- which is
1406: computed by indexing a string of such suffixes --- and the source and
1407: destination registers. Most of the binary operators
1408: \begin{verbatim}
1409: #define binary(inst) print("%s%c3 r%d,r%d,r%d\n", inst, suffix(p), \
1410: b->x.reg, a->x.reg, r)
1411: case BANDU: binary("bic"); break;
1412: case BORU: binary("bis"); break;
1413: case BXORU: binary("xor"); break;
1414: case ADDD: case ADDF: binary("add"); break;
1415: case ADDI: case ADDP: case ADDU: binary("add"); break;
1416: case SUBD: case SUBF: binary("sub"); break;
1417: case SUBI: case SUBP: case SUBU: binary("sub"); break;
1418: case MULD: case MULF: binary("mul"); break;
1419: case MULI: case MULU: binary("mul"); break;
1420: case DIVD: case DIVF: case DIVI: binary("div"); break;
1421: \end{verbatim}
1422: and all of the comparisons
1423: \begin{verbatim}
1424: #define compare(cp) print("cmp%c r%d,r%d; j%s %s\n", suffix(p), \
1425: a->x.reg, b->x.reg, cp, p->syms[0]->x.name)
1426: case EQD: case EQF: case EQI: compare("eql" ); break;
1427: case GED: case GEF: case GEI: compare("geq" ); break;
1428: case GEU: compare("gequ"); break;
1429: case GTD: case GTF: case GTI: compare("gtr" ); break;
1430: case GTU: compare("gtru"); break;
1431: case LED: case LEF: case LEI: compare("leq" ); break;
1432: case LEU: compare("lequ"); break;
1433: case LTD: case LTF: case LTI: compare("lss" ); break;
1434: case LTU: compare("lssu"); break;
1435: case NED: case NEF: case NEI: compare("neq" ); break;
1436: \end{verbatim}
1437: are handled similarly.
1438:
1439: The cases
1440: \begin{verbatim}
1441: case INDIRC: case INDIRD: case INDIRF: case INDIRI:
1442: case INDIRP: case INDIRS:
1443: print("mov%c (r%d),r%d\n", suffix(p), a->x.reg, r);
1444: break;
1445: case ASGNC: case ASGND: case ASGNF: case ASGNI: case ASGNP: case ASGNS:
1446: print("mov%c r%d,(r%d)\n", suffix(p), b->x.reg, a->x.reg);
1447: break;
1448: case JUMPV:
1449: print("jmp (r%d)\n", a->x.reg);
1450: break;
1451: case LABELV:
1452: print("%s:", p->syms[0]->x.name);
1453: break;
1454: \end{verbatim}
1455: emit code to indirectly load and store memory cells, to jump indirectly,
1456: and to emit a label definition.
1457:
1458: The cases
1459: \begin{verbatim}
1460: case ARGD: case ARGF: case ARGI: case ARGP:
1461: print("mov%c r%d,%d(sp)\n", suffix(p),
1462: a->x.reg, p->x.argoffset);
1463: break;
1464: case CALLD: case CALLF: case CALLI: case CALLV:
1465: save(p->x.busy&0x3e);
1466: print("calls $0,(r%d)\n", a->x.reg);
1467: if (p->op != CALLV)
1468: print("mov%c r0,r%d\n", suffix(p), r);
1469: restore(p->x.busy&0x3e);
1470: break;
1471: case RETD: case RETF: case RETI:
1472: print("mov%c r%d,r0; ret\n", suffix(p), a->x.reg);
1473: break;
1474: case RETV:
1475: print("ret\n");
1476: break;
1477: \end{verbatim}
1478: emit code to move an argument onto the stack, to call a procedure, and
1479: to return a value. The \verb|ARG| cases use \verb|x.argoffset|,
1480: into which \verb|ralloc| stored the stack offset for the argument.
1481: Procedures may destroy registers 1--5, so the \verb|CALL| cases use
1482: \begin{verbatim}
1483: static void save(unsigned mask) {
1484: int i;
1485:
1486: for (i = 1; i < nregs; i++)
1487: if (mask&(1<<i))
1488: print("movl r%d,%d(fp)\n", i,
1489: 4*i - framesize + argbuildsize);
1490: }
1491: \end{verbatim}
1492: to emit code to save any of those registers that are busy;
1493: \verb|restore| is similar.
1494: The \verb|RET| cases merely copy any return value into register 0 and return.
1495:
1496: Several binary operators require special handling. The shift
1497: instructions use a syntax that differs slightly from the other binary instructions:
1498: \begin{verbatim}
1499: case RSHI: case LSHI: case LSHU:
1500: print("ashl r%d,r%d,r%d\n", b->x.reg, a->x.reg, r);
1501: break;
1502: \end{verbatim}
1503: \verb|RSHI| and \verb|LSHI| generate the same code because the front
1504: end negates the shift count for \verb|RSHI| if the configuration
1505: parameter \verb|VAX| is defined. No instructions directly
1506: implement unsigned right shift, division, or modulus, so \verb|emit|
1507: uses a field-extraction instruction for the first and library calls for the others:
1508: \begin{verbatim}
1509: case RSHU:
1510: print("subl3 r%d,$32,r0; extzv r%d,r0,r%d,r%d\n",
1511: b->x.reg, b->x.reg, a->x.reg, r);
1512: break;
1513: case DIVU:
1514: save(p->x.busy&0x3e);
1515: print("pushl r%d; pushl r%d; calls $2,udiv; movl r0,r%d\n",
1516: b->x.reg, a->x.reg, r);
1517: restore(p->x.busy&0x3e);
1518: break;
1519: case MODU:
1520: save(p->x.busy&0x3e);
1521: print("pushl r%d; pushl r%d; calls $2,urem; movl r0,r%d\n",
1522: b->x.reg, a->x.reg, r);
1523: restore(p->x.busy&0x3e);
1524: break;
1525: \end{verbatim}
1526: Finally, ANSI C requires that \verb|a%b| equal \verb|a-(a/b)*b|,
1527: so \verb|MODI| computes it just this way:
1528: \begin{verbatim}
1529: case MODI:
1530: print("divl3 r%d,r%d,r0; mull2 r%d,r0; subl3 r0,r%d,r%d\n",
1531: b->x.reg, a->x.reg, b->x.reg, a->x.reg, r);
1532: break;
1533: \end{verbatim}
1534:
1535: Only the structure instructions remain:
1536: \begin{verbatim}
1537: case INDIRB:
1538: print("moval (r%d),r%d\n", a->x.reg, r);
1539: break;
1540: case ASGNB:
1541: save(p->x.busy&0x3f);
1542: print("movc3 $%s,(r%d),(r%d)\n", p->syms[0]->x.name,
1543: b->x.reg, a->x.reg);
1544: restore(p->x.busy&0x3f);
1545: break;
1546: case ARGB:
1547: save(p->x.busy&0x3f);
1548: print("movc3 $%s,(r%d),%d(sp)\n", p->syms[0]->x.name,
1549: a->x.reg, p->x.argoffset);
1550: restore(p->x.busy&0x3f);
1551: break;
1552: \end{verbatim}
1553: The scalar \verb|INDIR|s and \verb|ASGN|s load and store values
1554: directly, but structures won't fit in registers, so their instructions
1555: manipulate {\em addresses} instead. \verb|ASGNB| uses a
1556: block move instruction, which needs the size from
1557: \verb|p->syms[0]->x.name|; it also destroys registers 0--5, so
1558: \verb|emit| arranges to save and restore their values. \verb|ARGB|
1559: operates similarly, but copies the structure into the stack instead.
1560: Finally,
1561: \begin{verbatim}
1562: case CALLB:
1563: save(p->x.busy&0x3e);
1564: if (a->x.reg == 1) {
1565: print("movl r1,r0\n");
1566: a->x.reg = 0;
1567: }
1568: if (b->x.reg != 1)
1569: print("movl r%d,r1\n", b->x.reg);
1570: print("calls $0,(r%d)\n", a->x.reg);
1571: restore(p->x.busy&0x3e);
1572: break;
1573: \end{verbatim}
1574: is like an ordinary call, but it also passes the address at which to
1575: store the return value in register 1; if the address of the {\em function}
1576: is already in register 1, it is first moved out of the way into
1577: register 0, which is not otherwise allocated.
1578:
1579: If \verb|NOARGB| is defined (e.g., in the configuration file),
1580: the front end uses Sun's convention for passing structures by value.
1581: It builds dags that copy structure arguments to temporaries,
1582: passes pointers to these temporaries, adds an extra indirection
1583: to references to these parameters in the callee, and changes
1584: the types of the callee's formals to reflect this convention.
1585: It also sets \verb|structarg| for these parameters to distinquish
1586: them from bona fide structure pointer parameters.
1587:
1588: \section{Spills}
1589:
1590: \label{spills}
1591: When \verb|getreg| finds that all registers are busy,
1592: one or more must be {\em spilled} now and {\em reloaded}
1593: when the values are needed again.
1594: Handling spills correctly is difficult and a common
1595: source of compiler bugs. Test cases that expose
1596: bugs in the spill code are necessarily complex.
1597: As such, and for completeness,
1598: the implementation described in this section is adapted
1599: from that used in the production versions of \verb|lcc|.
1600: Reference~\cite{fraser:hanson:92} describes the important
1601: differences and explains the rationale behind this spiller.
1602:
1603: The dag constructed by the front end minimizes the reevaluation of
1604: common subexpressions. Spills are, in a sense,
1605: a result of the front end's eagerness to avoid
1606: reevaluation, and handling spills amounts to
1607: `breaking the dags' generated by the front end.
1608: A node representing a common subexpression is changed
1609: so that it stores the value in a temporary, and
1610: subsequent references to that node are edited
1611: to load the value from the temporary.
1612:
1613: Spilling involves three major steps:
1614: Identifying the registers to spill,
1615: generating the code for the spills at the correct
1616: location the output stream, and
1617: generating the code for the reloads, again at the correct locations.
1618: These steps are performed at the end of \verb|getreg|:
1619: \begin{verbatim}
1620: static void getreg(Node p) {
1621: int r, m = optype(p->op) == D ? 3 : 1;
1622: ...
1623: r = spillee(p, m);
1624: spill(r, m, p);
1625: getreg(p);
1626: }
1627: \end{verbatim}
1628: \verb|spillee| identifies the register (\verb|m==1|) or register pair (\verb|m==3|)
1629: to be spilled on behalf of \verb|p|,
1630: and \verb|spill| generates the spill and reload code.
1631: Once \verb|r| has been spilled,
1632: it is available,
1633: and the call to \verb|getreg| is guaranteed to succeed.
1634:
1635: \verb|ralloc| frees registers as soon as possible.
1636: If the available registers are exhausted,
1637: it is because there are multiple references
1638: to the nodes holding the registers, which arise
1639: from common subexpressions and from multiple assignment, augmented
1640: assignment, and the operators \verb|++| and \verb|--|.
1641: Consider the following program.
1642: \begin{verbatim}
1643: double a[10],b[10];
1644: int i;
1645: f(){ i = (a[i]+b[i])*(a[i]-b[i]); }
1646: \end{verbatim}
1647: The initial linearized forest is shown to the left of
1648: the vertical line in the display below.
1649: \begin{flushleft}\tt
1650: \begin{tabular}{rlllc|cll}
1651: \#\ & op & kids & syms & count &count & uses & sets \\
1652: 1. & ADDRGP & & \_i & 2 & 1 & & r1 \\
1653: 2. & INDIRI & 1 & & 1 & 0 & r1 & r2 \\
1654: 3. & CNSTI & & 3 & 1 & 0 & & r3 \\
1655: 4. & LSHI & 2 3 & & 2 & 0 & r2 r3 & r2 \\
1656: 5. & ADDRGP & & \_a & 1 & 0 & & r3 \\
1657: 6. & ADDP & 4 5 & & 1 & 0 & r2 r3 & r3 \\
1658: 7. & INDIRD & 6 & & 2 & 2 & r3 & r3 r4 \\
1659: 8. & ADDRGP & & \_b & 1 & 0 & & r5 \\
1660: 9. & ADDP & 4 8 & & 1 & 0 & r2 r5 & r2 \\
1661: 10. & INDIRD & 9 & & 2 & 2 & r2 \\
1662: 11. & ADDD & 7 10 & & 1 & 1 & r3 r4 \\
1663: 12. & SUBD & 7 10 & & 1 & 1 & r3 r4 \\
1664: 13. & MULD & 11 12 & & 1 & 1 \\
1665: 14. & CVDI & 13 & & 1 & 1 \\
1666: 15. & ASGNI & 1 14 & & 0 & 0 & r1 \\
1667: \end{tabular}
1668: \end{flushleft}
1669: Nodes with \verb|count| fields greater than 1 represent
1670: four common subexpressions: the lvalue of \verb|i| (node 1),
1671: the addressing expression \verb|i<<3| (node 4), and
1672: the rvalues of \verb|a[i]| (node 7) and \verb|b[i]| (node 10).
1673: If only registers 1--5 are available, \verb|ralloc| runs
1674: out of registers at node 10.
1675: The linearized forest at that point is shown to the right of
1676: the vertical line in the display above.
1677: As indicated by the non-zero \verb|count|s and the \verb|sets| column,
1678: node 1 is using \verb|r1| and
1679: node 7 is using \verb|r3| and \verb|r4|.
1680: Node 10 needs a register pair,
1681: but only registers \verb|r2| and \verb|r5| are available.
1682: Note that the \verb|count| of node 4, which is \verb|i<<3|,
1683: has dropped to 0 because \verb|ralloc| has
1684: processed both uses (nodes 6 and 9).
1685:
1686: \verb|getreg| calls \verb|spillee| to identify a register pair
1687: to be spilled so that it can be used for node 10.
1688: \verb|spillee| chooses the register whose next use
1689: is the most distant in the linearized forest.
1690: This choice is analogous to the optimal demand paging strategy that
1691: replaces pages whose next use is most distant
1692: in the execution stream~\cite{freiburghouse}.
1693:
1694: For each register,
1695: \verb|spillee| simply searches down the linearized forest
1696: for register uses and records the most distant.
1697: \begin{verbatim}
1698: static int spillee(Node dot, unsigned m) {
1699: int bestdist = -1, bestreg = 0, dist, r;
1700: Node q;
1701:
1702: for (r = 1; r < nregs - (m>>1); r++) {
1703: dist = 0;
1704: for (q = dot->x.next; q && !(uses(q)&(m<<r)); q = q->x.next)
1705: dist++;
1706: if (dist > bestdist) {
1707: bestdist = dist;
1708: bestreg = r;
1709: }
1710: }
1711: return bestreg;
1712: }
1713: \end{verbatim}
1714: \verb|spillee| is called with \verb|dot| equal to the node at which
1715: the spill is required, which is node 10 in the example above.
1716: \verb|uses(p)| returns a bit mask giving the registers used by node \verb|p|,
1717: i.e., the registers set by \verb|p|'s kids:
1718: \begin{verbatim}
1719: static unsigned uses(Node p) {
1720: int i;
1721: unsigned m = 0;
1722:
1723: for (i = 0; i < MAXKIDS; i++)
1724: if (p->kids[i])
1725: m |= sets(p->kids[i]);
1726: return m;
1727: }
1728: \end{verbatim}
1729:
1730: In this example, \verb|spillee| finds \verb|r1| used
1731: in node 15, which is at `distance' 4, and
1732: \verb|r3| and \verb|r4| used in node 11 at distance 0.
1733: Consequently, \verb|spillee| returns \verb|r1|, which denotes
1734: both \verb|r1| and \verb|r2| because \verb|m| is 3.
1735:
1736: The implementations of \verb|spillee| above and \verb|spill| below
1737: assume that the instruction
1738: emitted for each node reads the registers it uses before setting
1739: the register allocated to it. This assumption
1740: permits \verb|ralloc| to reassign registers used by a node to that node.
1741: It also permits \verb|spillee| to start its scan {\em after} the
1742: current instruction.
1743: This assumption is invalid on machines with two-address instructions.
1744:
1745: Actually spilling the register chosen by \verb|spillee| and inserting
1746: the reloads is done by \verb|spill| and its associates, \verb|genspill|
1747: and \verb|genreloads|.
1748: In the example, these functions collaborate to `break the dag'
1749: at node 1, which sets register \verb|r1| (\verb|r2| is already free).
1750: \verb|genspill| generates a temporary and the nodes necessary
1751: to store the value computed by node 1 into the temporary.
1752: These new nodes are stitched into the linearized forest immediately
1753: after node 1. \verb|genreloads| changes future {\em uses} of the
1754: value computed by node 1 to reload the value from
1755: the temporary instead of referencing node 1 directly.
1756: The effect is to remove the common subexpression
1757: by assigning it to a temporary.
1758:
1759: \verb|spill| identifies the locations at which
1760: to insert the spills by searching the linearized forest beyond \verb|dot|
1761: for nodes that use the registers that are to be spilled, e.g.,
1762: \verb|r1| in the example.
1763: \begin{verbatim}
1764: static void spill(int r, unsigned m, Node dot) {
1765: int i;
1766: Node p = dot;
1767:
1768: while (p = p->x.next)
1769: for (i = 0; i < MAXKIDS; i++)
1770: if (p->kids[i] && sets(p->kids[i])&(m<<r)) {
1771: Symbol temp = genspill(p->kids[i]);
1772: rmask &= ~sets(p->kids[i]);
1773: genreloads(dot, p->kids[i], temp);
1774: }
1775: }
1776: \end{verbatim}
1777: \verb|genspill| allocates the temporary,
1778: generates the spill code, and inserts it into the linearized forest
1779: right after the node that set the spillee.
1780: It returns the symbol-table entry for the temporary
1781: so that it can be used by \verb|genreloads| to generate the reloads.
1782: \begin{verbatim}
1783: static Symbol genspill(Node p) {
1784: Symbol temp = newtemp(AUTO, typecode(p));
1785: Node q = p->x.next;
1786:
1787: linearize(newnode(ASGN + typecode(p),
1788: newnode(ADDRLP, 0, 0, temp), p, 0),
1789: &p->x.next, p->x.next);
1790: rmask &= ~1;
1791: for (p = p->x.next; p != q; p = p->x.next)
1792: ralloc(p);
1793: rmask |= 1;
1794: return temp;
1795: }
1796: \end{verbatim}
1797: \verb|typecode| is like \verb|optype|, but maps \verb|U| to \verb|I|
1798: because the front-end uses \verb|ASGNI| and \verb|INDIRI|
1799: to store and load unsigned values. It also maps \verb|B| to
1800: \verb|P| because registers always point structures.
1801: The front-end's \verb|newtemp(sclass, type)|
1802: allocates a new temporary or reuses an existing one if
1803: its storage \verb|sclass| and \verb|type| code match those requested,
1804: and it announces a new temporary by calling \verb|local| as usual.
1805:
1806: The spill code is an \verb|ADDRLP| node to compute the
1807: address of the temporary and an \verb|ASGN| node to store the value
1808: into that address. The right operand of the \verb|ASGN| is simply
1809: \verb|p|, the node that set the registers to spill, e.g.,
1810: node 1 above.
1811: A node is allocated and initialized by the front-end function
1812: \verb|newnode(op,l,r,sym)|, where
1813: \verb|op| is the operator, \verb|l| and \verb|r|
1814: are \verb|kids[0]| and \verb|kids[1]|, and \verb|sym| is the symbol
1815: table pointer for leaf nodes. \verb|newnode| also increments
1816: the reference counts of \verb|l| and \verb|r|.
1817:
1818: Finally, \verb|genspill| linearizes the spill code and
1819: inserts it right after \verb|p|, which sets the spilled register.
1820: The manipulation of \verb|rmask| ensures that \verb|ralloc|
1821: assigns register \verb|r0| --- which is not otherwise allocated ---
1822: to the \verb|ADDRLP| node to compute the address.
1823: The linearized forest after \verb|genspill| returns is
1824: \begin{verbatim}
1825: # op kids syms count uses sets
1826: 1. ADDRGP _i 1 r1
1827: 16. ADDRLP -4(fp) 0 r0
1828: 17. ASGNP 16 1 0 r0 r1
1829: 2. INDIRI 1 0 r1 r2
1830: ...
1831: \end{verbatim}
1832: Nodes 16 and 17 are the spill code. This code references
1833: node 1, so its \verb|count| goes to 2 momentarily
1834: until \verb|ralloc| processes the reference from the spill code.
1835: The remaining reference is from node 15.
1836: Node 16's symbol \verb|-4(fp)| is the temporary location.
1837:
1838: After \verb|genspill| returns the temporary,
1839: \verb|spill| frees the registers set by the node and calls \verb|genreloads|.
1840: \verb|genreloads| searches the linearized forest
1841: after \verb|dot| for uses of \verb|p|.
1842: \begin{verbatim}
1843: static void genreloads(Node dot, Node p, Symbol temp) {
1844: int i;
1845: Node last;
1846:
1847: for (last = dot; dot = dot->x.next; last = dot)
1848: for (i = 0; i < MAXKIDS; i++)
1849: if (dot->kids[i] == p) {
1850: dot->kids[i] = newnode(INDIR + typecode(p),
1851: newnode(ADDRL+P, 0, 0, temp), 0, 0);
1852: dot->kids[i]->count = 1;
1853: p->count--;
1854: linearize(dot->kids[i], &last->x.next, last->x.next);
1855: last = dot->kids[i];
1856: }
1857: }
1858: \end{verbatim}
1859: Each use of \verb|p| is changed
1860: to a reload of the temporary \verb|temp|.
1861: The reload code is an \verb|ADDRLP| node to compute the
1862: address of the temporary and an \verb|INDIR| node to load the value
1863: from that address. There is only one reference to each reload, so the
1864: \verb|INDIR|'s \verb|count| is set accordingly,
1865: and \verb|p->count| is decremented to reflect the change.
1866: The reload code is linearized and inserted into the linearized node
1867: list immediately {\em before} its use.
1868: For the example above, a reload is placed before node 15.
1869: Since the reload is beyond the point that \verb|gen| has reached,
1870: registers are allocated for these nodes by subsequent calls to \verb|ralloc|.
1871:
1872: The linearized forest after \verb|spill| returns is
1873: \begin{verbatim}
1874: # op kids syms count uses sets
1875: 1. ADDRGP _i 0 r1
1876: 16. ADDRLP -4(fp) 0 r0
1877: 17. ASGNP 16 1 0 r0 r1
1878: 2. INDIRI 1 0 r1 r2
1879: ...
1880: 14. CVDI 13 1
1881: 18. ADDRLP -4(fp) 1
1882: 19. INDIRP 18 1
1883: 15. ASGNI 19 14 0
1884: \end{verbatim}
1885: Nodes 18 and 19 are the reload.
1886: Note that node 1's \verb|count| has become 0;
1887: after inserting the reload, there are no unprocessed references.
1888:
1889: Another spill occurs at node 11, which computes \verb|a[i]+b[i]|.
1890: Registers \verb|r1| and \verb|r2|, which are set by node 10, are spilled,
1891: and node 12 is edited to refer to the second temporary, which is reloaded
1892: by nodes 22 and 23 inserted before node 12.
1893: The last spill occurs at node 23, which is the reload
1894: created for the second spill. \verb|r1| and \verb|r2|, which are
1895: set by node 11, are spilled again, and node 13 is edited
1896: to refer to the third temporary.
1897: The final linearized forest and corresponding VAX code follows;
1898: \verb|count| fields are omitted because they're all 0,
1899: and each instruction shows which registers are used and set by each node.
1900: \begin{verbatim}
1901: VAX instruction # op kids syms
1902: moval _i,r1 1. ADDRGP _i
1903: moval -4(fp),r0 16. ADDRLP -4(fp)
1904: movl r1,(r0) 17. ASGNP 16 1
1905: movl (r1),r2 2. INDIRI 1
1906: movl $3,r3 3. CNSTI 3
1907: ashl r3,r2,r2 4. LSHI 2 3
1908: moval _a,r3 5. ADDRGP _a
1909: addl3 r3,r2,r3 6. ADDP 4 5
1910: movd (r3),r3 7. INDIRD 6
1911: moval _b,r5 8. ADDRGP _b
1912: addl3 r5,r2,r2 9. ADDP 4 8
1913: movd (r2),r1 10. INDIRD 9
1914: moval -12(fp),r0 20. ADDRLP -12(fp)
1915: movd r1,(r0) 21. ASGND 20 10
1916: addd3 r1,r3,r1 11. ADDD 7 10
1917: moval -20(fp),r0 24. ADDRLP -20(fp)
1918: movd r1,(r0) 25. ASGND 24 11
1919: moval -12(fp),r5 22. ADDRLP -12(fp)
1920: movd (r5),r1 23. INDIRD 22
1921: subd3 r1,r3,r1 12. SUBD 7 23
1922: moval -20(fp),r3 26. ADDRLP -20(fp)
1923: movd (r3),r3 27. INDIRD 26
1924: muld3 r1,r3,r1 13. MULD 27 12
1925: cvtdl r1,r1 14. CVDI 13
1926: moval -4(fp),r2 18. ADDRLP -4(fp)
1927: movl (r2),r2 19. INDIRP 18
1928: movl r1,(r2) 15. ASGNI 19 14
1929: \end{verbatim}
1930: Spills have added nodes 16--27.
1931:
1932:
1933: \section{Discussion}
1934:
1935: \verb|lcc|'s code generation interface is smaller than most
1936: because it omits the inessential and makes simplifying assumptions.
1937: These omissions and assumptions do, however,
1938: limit the interface's applicability to other languages and machines.
1939:
1940: The datatype assumptions detailed in Section~\ref{configuration},
1941: e.g., that unsigneds, integers, and long integers all have the same size,
1942: make it possible to have only 9 type suffixes and 109 type-specific operators.
1943: Relaxing these assumptions would increase this vocabulary;
1944: e.g., adding a suffix for long doubles would also add at least
1945: 19 more operators.
1946:
1947: The interface assumes that all pointer types have the same representation,
1948: which precludes its use for word-addressed machines.
1949: Differentiating between character and word pointers
1950: would add another suffix and at least 13 more operators.
1951:
1952: The operator repertoire omits some operators whose effect
1953: can be synthesized from simpler ones.
1954: For example, bit fields are accessed with shifting
1955: and masking instead of specific bit-field operators, so
1956: code quality may suffer on machines with bit-field instructions.
1957: The front end special-cases one-bit fields
1958: and generates efficient masking dags,
1959: which often yields better code than code
1960: that uses bit-field instructions.
1961:
1962: The front end implements switch statements completely.
1963: It generates a binary search of dense branch tables;
1964: inline comparisons replace small tables~\cite{bernstein85}.
1965: It fabricates the tables and indirect jumps
1966: using the functions \verb|global| and \verb|defaddress|
1967: and the \verb|JUMPV| operator.
1968: This decision prevents back ends from using larger `case' instructions,
1969: which usually combine a bounds check and an indirect branch through a table,
1970: but these instructions are increasingly rare, and some don't suit C anyway.
1971: For example, the branch table for the VAX's \verb|casel| instruction is limited
1972: to 16-bit offsets.
1973:
1974: The interface has no direct support for building
1975: a flow graph and other structures that facilitate
1976: global optimization. More elaborate versions of
1977: \verb|function| and \verb|gen| could collaborate
1978: to build the relevant structures, perform optimizations,
1979: and invoke the simpler \verb|gen|.
1980: The front end's \verb|gencode| and \verb|emitcode| traverse
1981: an approximation of a flow graph; future work may focus on
1982: a machine-independent optimizer that edits
1983: this graph while preserving the current interface.
1984:
1985: To date, the interface has been used only for ANSI~C.
1986: But it has little that is specific to C, and it could be used for
1987: similar languages and perhaps for languages with features like nested
1988: procedures, objects, and exception handling.
1989: Existing compilers for some object-oriented languages with these features,
1990: such as C\verb|++|, Modula-3, and Eiffel, generate C, so, in principle,
1991: the interface could be used for these languages.
1992:
1993: %\bibliography{refs,lib}
1994: \begin{thebibliography}{1}
1995:
1996: \bibitem{ansi:Cstandard}
1997: American National Standard Institute, Inc., New York.
1998: \newblock {\em American National Standards for Information Systems, Programming
1999: Language C {ANSI} X3.159--1989}, 1990.
2000:
2001: \bibitem{bernstein85}
2002: R.~L. Bernstein.
2003: \newblock Producing good code for the case statement.
2004: \newblock {\em Software---Practice \& Experience}, 15(10):1021--1024, Oct.
2005: 1985.
2006:
2007: \bibitem{fraser:sigplan89}
2008: C.~W. Fraser.
2009: \newblock A language for writing code generators.
2010: \newblock {\em Proceedings of the SIGPLAN'89 Conference on Programming Language
2011: Design and Implementation, SIGPLAN Notices}, 24(7):238--245, July 1989.
2012:
2013: \bibitem{fraser:hanson:91a}
2014: C.~W. Fraser and D.~R. Hanson.
2015: \newblock A code generation interface for {ANSI C}.
2016: \newblock {\em Software---Practice \& Experience}, 21(9):963--988, Sept. 1991.
2017:
2018: \bibitem{fraser:hanson:91b}
2019: C.~W. Fraser and D.~R. Hanson.
2020: \newblock A retargetable compiler for {ANSI C}.
2021: \newblock {\em SIGPLAN Notices}, 26(10):29--43, Oct. 1991.
2022:
2023: \bibitem{fraser:hanson:92}
2024: C.~W. Fraser and D.~R. Hanson.
2025: \newblock Simple register spilling in a retargetable compiler.
2026: \newblock {\em Software---Practice \& Experience}, 22(1):85--99, Jan. 1992.
2027:
2028: \bibitem{freiburghouse}
2029: R.~A. Freiburghouse.
2030: \newblock Register allocation via usage counts.
2031: \newblock {\em Communications of the ACM}, 17(11):638--642, Nov. 1974.
2032:
2033: \bibitem{tanenbaum:sigplan:89}
2034: A.~S. Tanenbaum, M.~F. Kaashoek, K.~G. Langendoen, and C.~J.~H. Jacobs.
2035: \newblock The design of very fast portable compilers.
2036: \newblock {\em SIGPLAN Notices}, 24(11):125--131, Nov. 1989.
2037:
2038: \bibitem{tanenbaum:toplas:82}
2039: A.~S. Tanenbaum, H.~van Staveren, and J.~W. Stevenson.
2040: \newblock Using peephole optimization on intermediate code.
2041: \newblock {\em ACM Transactions on Programming Languages and Systems},
2042: 4(1):21--36, Jan. 1982.
2043:
2044: \end{thebibliography}
2045:
2046: \appendix
2047:
2048: \section{Interface Functions}
2049: \label{appendix:interface}
2050:
2051: \begin{center}
2052: \begin{tabular}{cl}
2053: \em Section & \em Interface Function \\ \hline
2054: \ref{address} & \tt void address(Symbol, Symbol, int) \\
2055: \ref{blockbeg} & \tt void blockbeg(Env *e) \\
2056: \ref{blockend} & \tt void blockend(Env *e) \\
2057: \ref{defaddress}& \tt void defaddress(Symbol) \\
2058: \ref{defconst} & \tt void defconst(int, Value) \\
2059: \ref{defstring} & \tt void defstring(int, char *) \\
2060: \ref{defsymbol} & \tt void defsymbol(Symbol) \\
2061: \ref{emit} & \tt void emit(Node) \\
2062: \ref{export} & \tt void export(Symbol) \\
2063: \ref{function} & \tt void function(Symbol, Symbol [], Symbol [], int) \\
2064: \ref{gen} & \tt Node gen(Node) \\
2065: \ref{global} & \tt void global(Symbol) \\
2066: \ref{import} & \tt void import(Symbol) \\
2067: \ref{local} & \tt void local(Symbol) \\
2068: \ref{progbeg} & \tt void progbeg(int, char *[]) \\
2069: \ref{progend} & \tt void progend(void) \\
2070: \ref{segment} & \tt void segment(int) \\
2071: \ref{space} & \tt void space(int) \\
2072: \end{tabular}
2073: \end{center}
2074:
2075:
2076: \section{Front-End Functions}
2077:
2078: \label{appendix:functions}
2079:
2080: \begin{description}
2081:
2082: \item[{\tt void *alloc(int n)}] permanently allocates \verb|n| bytes and returns
2083: a pointer to the first byte. No alignment is guaranteed.
2084:
2085: \item[{\tt void fprint(int fd, char *fmt, \ldots)}] prints up to 5 arguments on
2086: the file descriptor \verb|fd|. See \verb|print| for formatting details.
2087: If \verb|fd| is not \verb|1| (standard output),
2088: \verb|fprint| flushes the output buffer for \verb|fd| via \verb|outflush|.
2089:
2090: \item[{\tt Type freturn(Type t)}] is the type of the return value for
2091: function type \verb|t|.
2092:
2093: \item[{\tt int generic(int op)}] is the generic version
2094: of the type-specific operator \verb|op|.
2095:
2096: \item[{\tt int genlabel(int n)}] increments the generated identifier
2097: counter by \verb|n| and returns its previous value.
2098:
2099: \item[{\tt int is\it type\/\tt(Type t)}] are a set of type predicates that
2100: return non-zero if type \verb|t| is the type in the following table.
2101:
2102: \begin{center}
2103: \begin{tabular}{lllll}
2104: \it predicate & \it type && \it predicate & \it type \\ \hline
2105: \tt isarith & arithmetic && \tt isint & integral \\
2106: \tt isarray & array && \tt isptr & pointer \\
2107: \tt ischar & character && \tt isscalar & scalar \\
2108: \tt isdouble & double && \tt isstruct & structure or union \\
2109: \tt isenum & enumeration && \tt isunion & union \\
2110: \tt isfloat & floating && \tt isunsigned & unsigned \\
2111: \tt isfunc & function && \\
2112: \end{tabular}
2113: \end{center}
2114:
2115: \item[{\tt Node newnode(int op, Node l, Node r, Symbol sym)}] allocates a node
2116: and initializes the \verb|op| field to \verb|op|, \verb|kids[0]| and \verb|kids[1]|
2117: to \verb|l| and \verb|r|, and \verb|syms[0]| to \verb|sym| and returns
2118: a pointer to the new node. If \verb|l| and \verb|r| are non-null,
2119: their \verb|count| fields are incremented.
2120:
2121: \item[{\tt Symbol newconst(Value v, int t)}] installs an constant with value \verb|v|
2122: and type suffix \verb|t| into the symbol table, if necessary,
2123: and returns a pointer to the symbol-table entry.
2124:
2125: \item[{\tt Symbol newtemp(int sclass, int t)}] creates a temporary
2126: with storage class \verb|sclass| and a type synonymous with type suffix \verb|t|
2127: and returns a pointer the symbol-table entry.
2128: If an existing temporary with the appropriate class and type is available,
2129: it is used; otherwise, the new temporary is announced by calling \verb|local|.
2130:
2131: \item[{\tt void outflush(void)}] writes the current output buffer
2132: to the standard output, if it's not empty.
2133:
2134: \item[{\tt void outs(char *s)}] appends string \verb|s| to the output buffer
2135: for standard output and calls \verb|outflush|
2136: if the resulting buffer pointer is within 80 characters
2137: of the end of the buffer.
2138:
2139: \item[{\tt int optype(op)}] is the type suffix of the type-specific operator \verb|op|.
2140:
2141: \item[{\tt void print(char *fmt, \ldots)}] prints up to 5 arguments on standard output
2142: similar to \verb|printf|. The supported formats are
2143: \verb|%c|, \verb|%d|, \verb|%o|, \verb|%x|, and \verb|%s|,
2144: and precision and field width specifications are not supported.
2145: \verb|print| calls \verb|outflush| if it prints a newline character from
2146: \verb|fmt| within 80 characters of the end of the output buffer,
2147: and each format except \verb|%c| does the actual output
2148: with \verb|outs|, which may also flush the buffer.
2149:
2150: \item[{\tt int roundup(int n, int m)}] is \verb|n| rounded up to the
2151: next multiple of \verb|m| where \verb|m| is a power of 2.
2152:
2153: \item[{\tt char *string(char *s)}] installs \verb|s| in the string space,
2154: if necessary, and returns a pointer to the installed copy.
2155:
2156: \item[{\tt char *stringd(int n)}] returns the string representation of \verb|n|;
2157: the returned string is installed in the string space by \verb|string|.
2158:
2159: \item[{\tt char *stringf(char *fmt, \ldots)}] formats up to 5 arguments
2160: into a string in the string space and returns a pointer to that string.
2161: See \verb|print| for formatting details.
2162:
2163: \item[{\tt void *talloc(int n)}] temporarily allocates \verb|n| bytes and returns
2164: a pointer to the first byte. The storage is released at the end of
2165: the current function. No alignment is guaranteed.
2166:
2167: \item[{\tt int ttob(Type t)}] is the type suffix synonymous with type \verb|t|.
2168:
2169: \item[{\tt int variadic(Type t)}] is true if type \verb|t| denotes a variadic function.
2170:
2171: \end{description}
2172:
2173: \end{document}
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.