porttour1

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

initializer occupies exactly the right size.
.PP
Character strings represent a bit of an exception.
If a character string is seen as the initializer for
a pointer, the characters making up the string must
be put out under a different location counter.
When the lexical analyzer sees the quote at the head
of a character string, it returns the token STRING,
but does not do anything with the contents.
The parser calls
.I getstr ,
which sets up the appropriate location counters
and flags, and calls
.I lxstr
to read and process the contents of the string.
.PP
If the string is being used to initialize a character array,
.I lxstr
calls
.I putbyte ,
which in effect simulates
.I doinit
for each character read.
If the string is used to initialize a character pointer,
.I lxstr
calls a machine dependent routine,
.I bycode ,
which stashes away each character.
The pointer to this string is then returned,
and processed normally by
.I doinit .
.PP
The null at the end of the string is treated as if it
were read explicitly by
.I lxstr .
.SH
Statements
.PP
The first pass addresses four main areas; declarations, expressions, initialization, and statements.
The statement processing is relatively simple; most of it is carried out in the
parser directly.
Most of the logic is concerned with allocating
label numbers, defining the labels, and branching appropriately.
An external symbol,
.I reached ,
is 1 if a statement can be reached, 0 otherwise; this is
used to do a bit of simple flow analysis as the program is being parsed,
and also to avoid generating the subroutine return sequence if the subroutine
cannot ``fall through'' the last statement.
.PP
Conditional branches are handled by generating an expression
node, CBRANCH,
whose left descendant is the conditional expression and the
right descendant is an ICON node containing the internal label
number to be branched to.
For efficiency, the semantics are that
the label is gone to if the condition is
.I false .
.PP
The switch statement is 
compiled by collecting the case entries, and an indication as to whether
there is a default case;
an internal label number is generated for each of these,
and remembered in a big array.
The expression comprising the value to be switched on is
compiled when the switch keyword is encountered,
but the expression tree is headed by
a special node, FORCE, which tells the code generator to
put the expression value into a special distinguished
register (this same mechanism is used for processing the
return statement).
When the end of the switch block is reached, the array
containing the case values is sorted, and checked for
duplicate entries (an error); if all is
correct, the machine dependent routine
.I genswitch
is called, with this array of labels and values in increasing order.
.I Genswitch
can assume that the value to be tested is already in the
register which is the usual integer return value register.
.SH
Optimization
.PP
There is a machine independent file,
.I optim.c ,
which contains a relatively short optimization routine,
.I optim .
Actually the word optimization is something of a misnomer;
the results are not optimum, only improved, and the
routine is in fact not optional; it must
be called for proper operation of the compiler.
.PP
.I Optim
is called after an expression tree is built, but
before the code generator is called.
The essential part of its job is to call
.I clocal
on the conversion operators.
On most machines, the treatment of
& is also essential:
by this time in the processing, the only node which
is a legal descendant of & is NAME.
(Possible descendants of * have been eliminated by
.I buildtree.)
The address of a static name is, almost by definition, a
constant, and can be represented by an ICON node on most machines
(provided that the loader has enough power).
Unfortunately, this is not universally true; on some machine, such as the IBM 370,
the issue of addressability rears its ugly head;
thus, before turning a NAME node into an ICON node,
the machine dependent function
.I andable
is called.
.PP
The optimization attempts of
.I optim
are currently quite limited.
It is primarily concerned with improving the behavior of
the compiler with operations one of whose arguments is a constant.
In the simplest case, the constant is placed on the right if the
operation is commutative.
The compiler also makes a limited search for expressions
such as
.DS
.I "( x + a ) + b"
.DE
where
.I a
and
.I b
are constants, and attempts to combine
.I a
and
.I b
at compile time.
A number of special cases are also examined;
additions of 0 and multiplications by 1 are removed,
although the correct processing of these cases to get
the type of the resulting tree correct is
decidedly nontrivial.
In some cases, the addition or multiplication must be replaced by
a conversion op to keep the types from becoming
fouled up.
Finally, in cases where a relational operation is being done,
and one operand is a constant, the operands are permuted, and the operator altered, if necessary,
to put the constant on the right.
Finally, multiplications by a power of 2 are changed to shifts.
.PP
There are dozens of similar optimizations that can be, and should be,
done.
It seems likely that this routine will be expanded in the relatively near future.
.SH
Machine Dependent Stuff
.PP
A number of the first pass machine dependent routines have been discussed above.
In general, the routines are short, and easy to adapt from
machine to machine.
The two exceptions to this general rule are
.I clocal
and
the function prolog and epilog generation routines,
.I bfcode
and
.I efcode .
.PP
.I Clocal
has the job of rewriting, if appropriate and desirable,
the nodes constructed by
.I buildtree .
There are two major areas where this
is important;
NAME nodes and conversion operations.
In the case of NAME nodes,
.I clocal
must rewrite the NAME node to reflect the
actual physical location of the name in the machine.
In effect, the NAME node must be examined, the symbol table
entry found (through the
.I rval
field of the node),
and, based on the storage class of the node,
the tree must be rewritten.
Automatic variables and parameters are typically
rewritten by treating the reference to the variable as
a structure reference, off the register which
holds the stack or argument pointer;
the
.I stref
routine is set up to be called in this way, and to
build the appropriate tree.
In the most general case, the tree consists
of a unary * node, whose descendant is
a + node, with the stack or argument register as left operand,
and a constant offset as right operand.
In the case of LABEL and internal static nodes, the
.I rval
field is rewritten to be the negative of the internal
label number; a negative
.I rval 
field is taken to be an internal label number.
Finally, a name of class REGISTER must be converted into a REG node,
and the
.I rval
field replaced by the register number.
In fact, this part of the
.I clocal
routine is nearly machine independent; only for machines
with addressability problems (IBM 370 again!) does it
have to be noticeably different,
.a
.PP
The conversion operator treatment is rather tricky.
It is necessary to handle the application of conversion operators
to constants in
.I clocal ,
in order that all constant expressions can have their values known
at compile time.
In extreme cases, this may mean that some simulation of the
arithmetic of the target machine might have to be done in a
cross-compiler.
In the most common case,
conversions from pointer to pointer do nothing.
For some machines, however, conversion from byte pointer to short or long
pointer might require a shift or rotate operation, which would
have to be generated here.
.PP
The extension of the portable compiler to machines where the size of a pointer
depends on its type would be straightforward, but has not yet been done.
.PP
The other major machine dependent issue involves the subroutine prolog and epilog
generation.
The hard part here is the design of the stack frame
and calling sequence; this design issue is discussed elsewhere.
.[
Johnson Lesk Ritchie calling sequence
.]
The routine
.I bfcode
is called with the number of arguments
the function is defined with, and
an array containing the symbol table indices of the
declared parameters.
.I Bfcode
must generate the code to establish the new stack frame,
save the return address and previous stack pointer
value on the stack, and save whatever
registers are to be used for register variables.
The stack size and the number of register variables is not
known when
.I bfcode
is called, so these numbers must be
referred to by assembler constants, which are
defined when they are known (usually in the second pass,
after all register variables, automatics, and temporaries have been seen).
The final job is to find those parameters which may have been declared
register, and generate the code to initialize
the register with the value passed on the stack.
Once again, for most machines, the general logic of
.I bfcode
remains the same, but the contents of the
.I printf
calls in it will change from machine to machine.
.I efcode
is rather simpler, having just to generate the default
return at the end of a function.
This may be nontrivial in the case of a function returning a structure or union, however.
.PP
There seems to be no really good place to discuss structures and unions, but
this is as good a place as any.
The C language now supports structure assignment,
and the passing of structures as arguments to functions,
and the receiving of structures back from functions.
This was added rather late to C, and thus to the portable compiler.
Consequently, it fits in less well than the older features.
Moreover, most of the burden of making these features work is
placed on the machine dependent code.
.PP
There are both conceptual and practical problems.
Conceptually, the compiler is structured around
the idea that to compute something, you put it into
a register and work on it.
This notion causes a bit of trouble on some machines (e.g., machines with 3-address opcodes), but
matches many machines quite well.
Unfortunately, this notion breaks down with structures.
The closest that one can come is to keep the addresses of the
structures in registers.
The actual code sequences used to move structures vary from the
trivial (a multiple byte move) to the horrible (a
function call), and are very machine dependent.
.PP
The practical problem is more painful.
When a function returning a structure is called, this function
has to have some place to put the structure value.
If it places it on the stack, it has difficulty popping its stack frame.
If it places the value in a static temporary, the routine fails to be
reentrant.
The most logically consistent way of implementing this is for the
caller to pass in a pointer to a spot where the called function
should put the value before returning.
This is relatively straightforward, although a bit tedious, to implement,
but means that the caller must have properly declared
the function type, even if the value is never used.
On some machines, such as the Interdata 8/32, the return value
simply overlays the argument region (which on the 8/32 is part
of the caller's stack frame).
The caller takes care of leaving enough room if the returned value is larger
than the arguments.
This also assumes that the caller know and declares the
function properly.
.PP
The PDP-11 and the VAX have stack hardware which is used in function calls and returns;
this makes it very inconvenient to
use either of the above mechanisms.
In these machines, a static area within the called functionis allocated, and
the function return value is copied into it on return; the function
returns the address of that region.
This is simple to implement, but is non-reentrant.
However, the function can now be called as a subroutine
without being properly declared, without the disaster which would otherwise ensue.
No matter what choice is taken, the convention is that the function
actually returns the address of the return structure value.
.PP
In building expression trees, the portable compiler takes a bit for granted about
structures.
It assumes that functions returning structures
actually return a pointer to the structure, and it assumes that
a reference to a structure is actually a reference to its address.
The structure assignment operator is rebuilt so that the left
operand is the structure being assigned to, but the
right operand is the address of the structure being assigned;
this makes it easier to deal with
.DS
.I "a = b = c"
.DE
and similar constructions.
.PP
There are four special tree nodes associated with these
operations:
STASG (structure assignment), STARG (structure argument
to a function call), and STCALL and UNARY STCALL
(calls of a function with nonzero and zero arguments, respectively).
These four nodes are unique in that the size and alignment information, which can be determined by
the type for all other objects in C, 
must be known to carry out these operations; special
fields are set aside in these nodes to contain
this information, and special
intermediate code is used to transmit this information.
.SH
First Pass Summary
.PP
There are may other issues which have been ignored here,
partly to justify the title ``tour'', and partially
because they have seemed to cause little trouble.
There are some debugging flags
which may be turned on, by giving the compiler's first pass
the argument
.DS
\-X[flags]
.DE
Some of the more interesting flags are
\-Xd for the defining and freeing of symbols,
\-Xi for initialization comments, and
\-Xb for various comments about the building of trees.
In many cases, repeating the flag more than once gives more information;
thus,
\-Xddd gives more information than \-Xd.
In the two pass version of the compiler, the
flags should not be set when the output is sent to the second
pass, since the debugging output and the intermediate code both go onto the standard
output.
.PP
We turn now to consideration of the second pass.