cdoc3

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

.SH
Code Generation
.PP
The grand plan for code-generation is
independent of any particular machine;
it depends largely on a set of tables.
But this fact does not necessarily make it very easy
to modify the compiler to produce code for other machines,
both because there is a good deal of machine-dependent structure
in the tables, and because in any event such tables are non-trivial to
prepare.
.PP
The arguments to the basic code generation routine
.II rcexpr
are a pointer to a tree representing an expression,
the name of a code-generation table,
and the number of a register in which the value of the
expression should be placed.
.II Rcexpr
returns the number of the register in which the value actually
ended up;
its caller
may need to produce a
.II mov
instruction if the value really needs to be in the given register.
There are four code generation tables.
.PP
.II Regtab
is the basic one, which actually does the job described
above: namely,
compile code which places the value represented by the expression
tree in a register.
.PP
.II Cctab
is used when the value of the expression is not actually needed,
but instead the value of the condition codes resulting from
evaluation of the expression.
This table is used, for example, to evaluate the expression after
.II if.
It is clearly silly to
calculate the value (0 or 1) of the expression
`a==b' in the context `if (a==b) ... '
.PP
The
.II sptab
table is used when the value of an expression is to be pushed on the stack,
for example when it is an actual argument.
For example in the function call `f(a)' it is a bad idea to
load
.II a
into a register which is then pushed on the stack,
when there is a single instruction which does the job.
.PP
The
.II efftab
table is used when an expression is to be evaluated for its side effects,
not its value.
This occurs mostly for expressions which are statements, which have no
value.
Thus the code for the statement
`a = b'
need produce only the approoriate
.II mov
instruction, and need not leave the value of
.II b
in a register,
while in the expression `a + (b = c)'
the value of `b = c' will appear in a register.
.PP
All of the tables besides
.II regtab
are rather small, and handle only a relatively few special cases.
If one of these subsidiary tables does not contain
an entry applicable to the given expression tree,
.II rcexpr
uses
.II regtab
to put the value of the expression into a register
and then fixes things up;
nothing need be done when the table
was
.II efftab,
but a
.II tst
instruction is produced when the table called for was
.II cctab,
and a 
.II mov
instruction,
pushing the register on the stack,
when the table was
.II sptab.
.PP
The
.II rcexpr
routine itself picks off some special
cases, then calls
.II cexpr
to do the real work.
.II Cexpr
tries to find an entry applicable
to the given tree in the given table, and returns \-1 if
no such entry is found, letting
.II rcexpr
try again with a different table.
A successful match yields a string
containing both literal characters
which are written out and pseudo-operations, or macros, which are expanded.
Before studying the contents
of these strings we will consider how table entries are matched
against trees.
.PP
Recall that most non-leaf nodes in an expression tree
contain the name of the operator,
the type of the value represented, and pointers to the subtrees (operands).
They also contain an estimate of the number of registers required to evaluate
the expression, placed there by the expression-optimizer routines.
The register counts are used to guide the code generation process,
which is based on the Sethi-Ullman algorithm.
.PP
The main code generation
tables consist of entries
each containing an operator number and a pointer
to a subtable for the corresponding operator.
A subtable consists of a sequence
of entries, each with a key describing certain properties of the
operands of the operator involved; associated with the key is a code string.
Once the subtable corresponding to the operator is found, the subtable
is searched linearly until a key is found such that the properties demanded
by the key are compatible with the operands of the tree node.
A successful match returns the code string;
an unsuccessful search, either for the operator in the main table
or a compatble key in the subtable,
returns a failure indication.
.PP
The tables are all contained in a file
which must be processed to obtain an assembly language program.
Thus they are written in a special-purpose language.
To provided definiteness to the following discussion, here is an
example of a subtable entry.
.DS
%n,aw
	F
	add	A2,R
.DE
The `%' indicates the key;
the information following (up to a blank line) specifies the code string.
Very briefly, this entry is in the subtable
for `+' of
.II regtab;
the key specifies that the left operand is any integer, character, or pointer
expression,
and the right operand is any word quantity which is directly addressible
(e.g. a variable or constant).
The code string calls for the generation of the code
to compile the left (first) operand into the
current register (`F')
and then to produce an `add' instruction which adds the
second operand (`A2') to the register (`R').
All of the notation will be explained below.
.PP
Only three features of the operands are used in deciding
whether a match has occurred.
They are:
.IP 1.
Is the type of the operand compatible with that demanded?
.RT
.IP 2.
Is the `degree of difficulty' (in a sense described below) compatible?
.RT
.IP 3.
The table may demand that the operand have a `*'
(indirection operator) as its highest operator.
.PP
As suggested above, the key for a subtable entry
is indicated by a `%,' and a comma-separated pair
of specifications for the operands.
(The second specification is ignored for unary operators).
A specification indicates
a type requirement by including one of the following letters.
If no type letter is present, any integer, character,
or pointer operand will satisfy the requirement (not float, double, or long).
.IP b
A byte (character) operand is required.
.RT
.IP w
A word (integer or pointer) operand is required.
.RT
.IP f
A float or double operand is required.
.RT
.IP d
A double operand is required.
.RT
.IP l
A long (32-bit integer) operand is required.
.PP
Before discussing the `degree of difficulty' specification,
the algorithm has to be explained more completely.
.II Rcexpr
(and
.II cexpr)
are called with a register number in which to place their result.
Registers 0, 1, ... are used during evaluation of expressions;
the maximum register which can be used in this way depends on the
number of register variables, but in any event only registers
0 through 4 are available since r5 is used as a stack frame
header and r6 (sp) and r7 (pc) have special
hardware properties.
The code generation routines assume that when called with register
.II n
as argument, they may use
.II n+1,
\&...
(up to the first register variable)
as temporaries.
Consider the expression `X+Y', where both
X and Y are expressions.
As a first approximation, there are three ways of compiling
code to put this expression in register
.II n.
.IP 1.
If Y is an addressible cell,
(recursively) put X into register
.II n
and add Y to it.
.RT
.IP 2.
If Y is an expression that can be calculated in
.II k
registers, where
.II k
smaller than the number of registers available,
compile X into register
.II n,
Y into register
.II n+1,
and add register
.II n+1
to
.II n.
.RT
.IP 3.
Otherwise, compile Y into register
.II n,
save the result in a temporary (actually, on the stack)
compile X into register
.II n,
then add in the temporary.
.PP
The distinction between cases 2 and 3 therefore depends
on whether the right operand can be compiled in fewer than
.II k
registers, where
.II k
is the number of free registers left after registers 0 through
.II n
are taken:
0 through
.II n\-1
are presumed to contain already computed temporary results;
.II n
will, in case 2,
contain the value of the left operand while the right
is being evaluated.
.PP
These considerations should make clear
the specification codes for the degree of difficulty,
bearing in mind that a number of special cases are also present:
.IP z
is satisfied when the operand is zero, so that special code
can be produced for expressions like `x = 0'.
.RT
.IP 1
is satisfied when the operand is the constant 1, to optimize
cases like left and right shift by 1, which can be done
efficiently on the PDP-11.
.RT
.IP c
is satisfied when the operand is a positive (16-bit)
constant; this takes care of some special cases in long arithmetic.
.RT
.IP a
is satisfied when the operand is addressible;
this occurs not only for variables and constants, but also for
some more complicated constructions, such as indirection through
a simple variable, `*p++' where
.II p
is a register variable (because of the PDP-11's auto-increment address
mode), and `*(p+c)' where
.II p
is a register and
.II c
is a constant.
Precisely, the requirement is that the operand refers to a cell
whose address can be written as a source or destination of a PDP-11
instruction.
.RT
.IP e
is satisfied by an operand whose value can be generated in a register
using no more than
.II k
registers, where
.II k
is the number of registers left (not counting the current register).
The `e' stands for `easy.'
.RT
.IP n
is satisfied by any operand.
The `n' stands for `anything.'
.PP
These degrees of difficulty are considered to lie in a linear ordering
and any operand which satisfies an earlier-mentioned requirement
will satisfy a later one.
Since the subtables are searched linearly,
if a `1' specification is included, almost certainly
a `z' must be written first to prevent
expressions containing the constant 0 to be compiled
as if the 0 were 1.
.PP
Finally,
a key specification may contain a `*' which
requires the operand to have an indirection as its leading operator.
Examples below should clarify the utility of this specification.
.PP
Now let us consider the contents of the code string
associated with each subtable entry.
Conventionally, lower-case letters in this string
represent literal information which is copied directly
to the output.
Upper-case letters generally introduce specific
macro-operations, some of which may be followed
by modifying information.
The code strings in the tables are written with tabs and
new-lines used freely to suggest instructions which will be generated;
the table-compiling program compresses tabs (using the 0200 bit of the
next character) and throws away some of the new-lines.
For example the macro `F' is ordinarily written on a line by itself;
but since its expansion will end with a new-line, the new-line
after `F' itself is dispensable.
This is all to reduce the size of the stored tables.
.PP
The first set of macro-operations is concerned with
compiling subtrees.
Recall that this is done by the
.II cexpr
routine.
In the following discussion the `current register'
is generally the argument register to
.II cexpr;
that is, the place where the result is desired.
The `next register' is numbered one
higher
than the current register.
(This explanation isn't fully true
because of complications, described below, involving
operations which require even-odd register pairs.)
.IP F
causes a recursive call to
the
.II rcexpr
routine to compile code which places the value of the first (left)
operand of the operator in the current register.
.RT
.IP F1
generates code which places the value of the first operand in the
next register.
It is incorrectly used if there might be no next register;
that is, if the degree of difficulty of the first operand is not `easy;'
if not, another register might not be available.
.RT
.IP FS
generates code which pushes the value of the first operand on the stack,
by calling
.II rcexpr
specifying
.II sptab
as the table.
.LP
Analogously,
.IP "S, S1, SS"
compile the second (right) operand
into the current register, the next register, or onto the stack.
.LP
To deal with registers, there are
.IP R
which expands into the name of the current register.
.RT
.IP R1
which expands into the name of the next register.
.RT
.IP R+
which expands into the the name of the current register plus 1.
It was suggested above that this is the same as the next register,
except for complications; here is one of them.
Long integer variables have
32 bits and require 2 registers; in such cases the next register
is the current register plus 2.
The code would like to talk about both halves of the
long quantity, so R refers to the register with the high-order part
and R+ to the low-order part.
.RT
.IP R\-
This is another complication, involving division and mod.
These operations involve a pair of registers of which the odd-numbered
contains the left operand.
.II Cexpr