porttour1

unix v7是最后一个广泛发布的研究型UNIX版本

.TL
A Tour Through the Portable C Compiler
.AU
S. C. Johnson
.AI
.MH
.SH
Introduction
.PP
A C compiler has been implemented that has proved to be quite portable,
serving as the basis for C compilers on roughly a dozen machines, including
the Honeywell 6000, IBM 370, and Interdata 8/32.
The compiler is highly compatible with the C language standard.
.[
Kernighan Ritchie Prentice 1978
.]
.PP
Among the goals of this compiler are portability, high reliability,
and the use of state-of-the-art techniques and tools wherever practical.
Although the efficiency of the compiling process is not
a primary goal, the compiler is efficient enough, and produces
good enough code, to serve as a production compiler.
.PP
The language implemented is highly compatible with the current PDP-11 version of C.
Moreover, roughly 75% of the compiler, including
nearly all the syntactic and semantic routines, is machine independent.
The compiler also serves as the major portion of the program
.I lint ,
described elsewhere.
.[
Johnson Lint Program Checker
.]
.PP
A number of earlier attempts to make portable compilers are worth noting.
While on CO-OP assignment to Bell Labs in 1973, Alan Snyder wrote a portable C
compiler which was the basis of his Master's Thesis at M.I.T.
.[
Snyder Portable C Compiler
.]
This compiler was very slow and complicated, and contained a number of rather
serious implementation difficulties;
nevertheless, a number of Snyder's ideas appear in this work.
.PP
Most earlier portable compilers, including Snyder's, have proceeded by
defining an intermediate language, perhaps based
on three-address code or code for a stack machine,
and writing a machine independent program to
translate from the source code to this
intermediate code.
The intermediate code is then read by a second pass, and interpreted or compiled.
This approach is elegant, and has a number of advantages, especially if the
target machine is far removed from the host.
It suffers from some disadvantages as well.
Some constructions, like initialization and subroutine prologs,
are difficult or expensive to express in a
machine independent way that still allows them
to be easily adapted to the target assemblers.
Most of these approaches require a symbol table to be constructed
in the second (machine dependent) pass, and/or
require powerful target assemblers.
Also, many conversion operators may be generated
that have no effect on a given machine,
but may be needed on others (for example, pointer to pointer
conversions usually do nothing in C, but must be generated because
there are some machines where they are significant).
.PP
For these reasons, the first pass of the portable compiler
is not entirely machine independent.
It contains some machine dependent features, such as initialization, subroutine
prolog and epilog, certain storage allocation functions,
code for the
.I switch
statement, and code to throw out unneeded conversion operators.
.PP
As a crude measure of the degree of
portability actually achieved,
the Interdata 8/32 C compiler has
roughly 600 machine dependent lines of source out of 4600 in Pass 1, and 1000
out of 3400 in Pass 2.
In total, 1600 out of 8000, or 20%,
of the total source is machine dependent
(12% in Pass 1, 30% in Pass 2).
These percentages can be expected to rise slightly as the
compiler is tuned.
The percentage of machine-dependent code for the IBM is 22%, for
the Honeywell 25%.
If the assembler format and structure were the same for all
these machines, perhaps another 5-10% of the code
would become machine independent.
.PP
These figures are sufficiently misleading as to be almost
meaningless.
A large fraction of the machine dependent code can be converted
in a straightforward, almost mechanical way.
On the other hand, a certain amount of the code requres hard
intellectual effort to convert, since the algorithms
embodied in this part of the code are typically complicated
and machine dependent.
.PP
To summarize, however, if you need a C compiler written for a machine with
a reasonable architecture, the compiler is already three quarters finished!
.SH
Overview
.PP
This paper discusses the structure and organization of the portable compiler.
The intent is to give the big picture, rather than discussing the details of a particular machine
implementation.
After a brief overview and a discussion of the source file structure,
the paper describes the major data structures, and then delves more
closely into the two passes.
Some of the theoretical work on which the compiler is based, and
its application to the compiler, is discussed elsewhere.
.[
johnson portable theory practice
.]
One of the major design issues in any C compiler, the design of
the calling sequence and stack frame, is the subject of a separate
memorandum.
.[
johnson lesk ritchie calling sequence
.]
.PP
The compiler consists of two passes,
.I pass1
and
.I pass2 ,
that together turn C source code into assembler code for the target
machine.
The two passes are preceded by a preprocessor, that
handles the
.B "#define"
and
.B "#include"
statements, and related features (e.g.,
.B #ifdef ,
etc.).
It is a nearly machine independent program, and will
not be further discussed here.
.PP
The output of the preprocessor is a text file that is read as the standard
input of the first pass.
This
produces as standard output another text file that becomes the standard
input of the second pass.
The second pass produces, as standard output, the desired assembler language source code.
The preprocessor and the two passes
all write error messages on the standard error file.
Thus the compiler itself makes few demands on the I/O
library support, aiding in the bootstrapping process.
.PP
Although the compiler is divided into two passes,
this represents historical accident more than deep necessity.
In fact, the compiler can optionally be loaded
so that both passes operate in the same program.
This ``one pass'' operation eliminates the overhead of
reading and writing the intermediate file, so the compiler
operates about 30% faster in this mode.
It also occupies about 30% more space than the larger
of the two component passes.
.PP
Because the compiler is fundamentally structured as two
passes, even when loaded as one, this document primarily
describes the two pass version.
.PP
The first pass does the lexical analysis, parsing, and
symbol table maintenance.
It also constructs parse trees for expressions,
and keeps track of the types of the nodes in these trees.
Additional code is devoted to initialization.
Machine dependent portions of the first pass serve to
generate subroutine prologs and epilogs,
code for switches, and code for branches, label definitions,
alignment operations,
changes of location counter, etc.
.PP
The intermediate file is a text file organized into lines.
Lines beginning with a right parenthesis are copied by the second
pass directly to its output file, with the
parenthesis stripped off.
Thus, when the first pass produces assembly code, such as subroutine prologs,
etc., each line is prefaced with a right parenthesis;
the second pass passes these lines to through to the assembler.
.PP
The major job done by the second pass is generation of code
for expressions.
The expression parse trees produced in the first pass are
written onto the
intermediate file in Polish Prefix form:
first, there is a line beginning with a period, followed by the source
file line number and name on which the expression appeared (for debugging purposes).
The successive lines represent the nodes of the parse tree,
one node per line.
Each line contains the node number, type, and
any values (e.g., values of constants)
that may appear in the node.
Lines representing nodes with descendants are immediately
followed by the left subtree of descendants, then the
right.
Since the number of descendants of any node is completely
determined by the node number, there is no need to mark the end
of the tree.
.PP
There are only two other line types in the intermediate file.
Lines beginning with a left square bracket (`[') represent the beginning of
blocks (delimited by { ... } in the C source);
lines beginning with right square brackets (`]') represent the end of blocks.
The remainder of these lines tell how much
stack space, and how many register variables,
are currently in use.
.PP
Thus, the second pass reads the intermediate files, copies the `)' lines,
makes note of the information in the `[' and `]' lines,
and devotes most of its effort to the
`.' lines and their associated expression trees, turning them
turns into assembly code to evaluate the expressions.
.PP
In the one pass version of the compiler, the expression
trees that are built by the first pass have
been declared to have room for the second pass
information as well.
Instead of writing the trees onto an intermediate file,
each tree is transformed in place into an acceptable
form for the code generator.
The code generator then writes the result of compiling
this tree onto the standard output.
Instead of `[' and `]' lines in the intermediate file, the information is passed
directly to the second pass routines.
Assembly code produced by the first pass is simply written out,
without the need for ')' at the head of each line.
.SH
The Source Files
.PP
The compiler source consists of 22 source files.
Two files,
.I manifest
and
.I macdefs ,
are header files included with all other files.
.I Manifest
has declarations for the node numbers, types, storage classes,
and other global data definitions.
.I Macdefs
has machine-dependent definitions, such as the size and alignment of the
various data representations.
Two machine independent header files,
.I mfile1
and
.I mfile2 ,
contain the data structure and manifest definitions
for the first and second passes, respectively.
In the second pass, a machine dependent header file,
.I mac2defs ,
contains declarations of register names, etc.
.PP
There is a file,
.I common ,
containing (machine independent) routines used in both passes.
These include routines for allocating and freeing trees, walking over trees,
printing debugging information, and printing error messages.
There are two dummy files,
.I comm1.c
and
.I comm2.c ,
that simply include
.I common
within the scope of the appropriate pass1 or pass2 header files.
When the compiler is loaded as a single pass,
.I common
only needs to be included once:
.I comm2.c
is not needed.
.PP
Entire sections of this document are devoted to the detailed structure of the
passes.
For the moment, we just give a brief description of the files.
The first pass
is obtained by compiling and loading
.I scan.c ,
.I cgram.c ,
.I xdefs.c ,
.I pftn.c ,
.I trees.c ,
.I optim.c ,
.I local.c ,
.I code.c ,
and
.I comm1.c .
.I Scan.c
is the lexical analyzer, which is used by
.I cgram.c ,
the result of applying
.I Yacc
.[
Johnson Yacc Compiler cstr
.]
to the input grammar
.I cgram.y .
.I Xdefs.c
is a short file of external definitions.
.I Pftn.c
maintains the symbol table, and does initialization.
.I Trees.c
builds the expression trees, and computes the node types.
.I Optim.c
does some machine independent optimizations on the expression trees.
.I Comm1.c
includes
.I common ,
that contains service routines common to the two passes of the compiler.
All the above files are machine independent.
The files
.I local.c
and
.I code.c
contain machine dependent code for generating subroutine
prologs, switch code, and the like.
.PP
The second pass
is produced by compiling and loading
.I reader.c ,
.I allo.c ,
.I match.c ,
.I comm1.c ,
.I order.c ,
.I local.c ,
and
.I table.c .
.I Reader.c
reads the intermediate file, and controls the major logic of the
code generation.
.I Allo.c
keeps track of busy and free registers.
.I Match.c
controls the matching
of code templates to subtrees of the expression tree to be compiled.
.I Comm2.c
includes the file
.I common ,
as in the first pass.
The above files are machine independent.
.I Order.c
controls the machine dependent details of the code generation strategy.
.I Local2.c
has many small machine dependent routines,
and tables of opcodes, register types, etc.
.I Table.c
has the code template tables,
which are also clearly machine dependent.
.SH
Data Structure Considerations.
.PP
This section discusses the node numbers, type words, and expression trees, used
throughout both passes of the compiler.
.PP
The file
.I manifest
defines those symbols used throughout both passes.
The intent is to use the same symbol name (e.g., MINUS)
for the given operator throughout the lexical analysis, parsing, tree building,
and code generation phases;
this requires some synchronization with the
.I Yacc
input file,
.I cgram.y ,
as well.
.PP
A token
like MINUS may be seen in the lexical analyzer before it is known
whether it is a unary or binary operator;
clearly, it is necessary to know this by the time the parse tree
is constructed.
Thus, an operator (really a macro) called
UNARY is provided, so that MINUS
and UNARY MINUS are both distinct node numbers.
Similarly, many binary operators exist in an assignment form (for example, \-=),
and the operator ASG may be applied to such node names to generate new ones, e.g. ASG MINUS.