porttour2

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

.SH
Pass Two
.PP
Code generation is far less well understood than
parsing or lexical analysis, and for this reason
the second pass is far harder to discuss in a file by file manner.
A great deal of the difficulty is in understanding the issues
and the strategies employed to meet them.
Any particular function is likely to be reasonably straightforward.
.PP
Thus, this part of the paper will concentrate a good deal on the broader
aspects of strategy in the code generator,
and will not get too intimate with the details.
.SH
Overview.
.PP
It is difficult to organize a code generator to be flexible enough to
generate code for a large number of machines,
and still be efficient for any one of them.
Flexibility is also important when it comes time to tune
the code generator to improve the output code quality.
On the other hand, too much flexibility can lead to semantically
incorrect code, and potentially a combinatorial explosion in the
number of cases to be considered in the compiler.
.PP
One goal of the code generator is to have a high degree of correctness.
It is very desirable to have the compiler detect its own inability to
generate correct code, rather than to produce incorrect code.
This goal is achieved by having a simple model of the job
to be done (e.g., an expression tree)
and a simple model of the machine state
(e.g., which registers are free).
The act of generating an instruction performs a transformation
on the tree and the machine state;
hopefully, the tree eventually gets
reduced to a single node.
If each of these instruction/transformation pairs is correct,
and if the machine state model really represents the actual machine,
and if the transformations reduce the input tree to the desired single node, then the
output code will be correct.
.PP
For most real machines, there is no definitive theory of code generation that
encompasses all the C operators.
Thus the selection of which instruction/transformations to generate, and in what
order, will have a heuristic flavor.
If, for some expression tree, no transformation applies, or, more
seriously, if the heuristics select a sequence of instruction/transformations
that do not in fact reduce the tree, the compiler
will report its inability to generate code, and abort.
.PP
A major part of the code generator is concerned with the model and the transformations,
\(em most of this is machine independent, or depends only on simple tables.
The flexibility comes from the heuristics that guide the transformations
of the trees, the selection of subgoals, and the ordering of the computation.
.SH
The Machine Model
.PP
The machine is assumed to have a number of registers, of at most two different
types:
.I A
and
.I B .
Within each register class, there may be scratch (temporary) registers and dedicated registers
(e.g., register variables, the stack pointer, etc.).
Requests to allocate and free registers involve only the temporary registers.
.PP
Each of the registers in the machine is given a name and a number
in the
.I mac2defs
file; the numbers are used as indices into various tables
that describe the registers, so they should be kept small.
One such table is the
.I rstatus
table on file
.I local2.c .
This table is indexed by register number, and
contains expressions made up from manifest constants describing the register types:
SAREG for dedicated AREG's, SAREG\(orSTAREG for scratch AREGS's,
and SBREG and SBREG\(orSTBREG similarly for BREG's.
There are macros that access this information:
.I isbreg(r)
returns true if register number
.I r
is a BREG, and
.I istreg(r)
returns true if register number
.I r
is a temporary AREG or BREG.
Another table,
.I rnames ,
contains the register names; this is used when
putting out assembler code and diagnostics.
.PP
The usage of registers is kept track of by an array called
.I busy .
.I Busy[r]
is the number of uses of register
.I r
in the current tree being processed.
The allocation and freeing of registers will be discussed later as part of the code generation
algorithm.
.SH
General Organization
.PP
As mentioned above, the second pass reads lines from
the intermediate file, copying through to the output unchanged
any lines that begin with a `)', and making note of the
information about stack usage and register allocation contained on
lines beginning with `]' and `['.
The expression trees, whose beginning is indicated by a line beginning with `.',
are read and rebuilt into trees.
If the compiler is loaded as one pass, the expression trees are
immediately available to the code generator.
.PP
The actual code generation is done by a hierarchy of routines.
The routine
.I delay
is first given the tree; it attempts to delay some postfix
++ and \-\- computations that might reasonably be done after the
smoke clears.
It also attempts to handle comma (,) operators by computing the
left side expression first, and then rewriting the tree
to eliminate the operator.
.I Delay
calls
.I codgen
to control the actual code generation process.
.I Codgen
takes as arguments a pointer to the expression tree,
and a second argument that, for socio-historical reasons, is called a
.I cookie .
The cookie describes a set of goals that would be acceptable
for the code generation: these are assigned to individual bits,
so they may be logically or'ed together to form a large number of possible goals.
Among the possible goals are FOREFF (compute for side effects only;
don't worry about the value), INTEMP (compute and store value into a temporary location
in memory), INAREG (compute into an A register), INTAREG (compute into a scratch
A register), INBREG and INTBREG similarly, FORCC (compute for condition codes),
and FORARG (compute it as a function argument; e.g., stack it if appropriate).
.PP
.I Codgen
first canonicalizes the tree by calling
.I canon .
This routine looks for certain transformations that might now be
applicable to the tree.
One, which is very common and very powerful, is to
fold together an indirection operator (UNARY MUL)
and a register (REG); in most machines, this combination is
addressable directly, and so is similar to a NAME in its
behavior.
The UNARY MUL and REG are folded together to make
another node type called OREG.
In fact, in many machines it is possible to directly address not just the
cell pointed to by a register, but also cells differing by a constant
offset from the cell pointed to by the register.
.I Canon
also looks for such cases, calling the
machine dependent routine 
.I notoff
to decide if the offset is acceptable (for example, in the IBM 370 the offset
must be between 0 and 4095 bytes).
Another optimization is to replace bit field operations
by shifts and masks if the operation involves extracting the field.
Finally, a machine dependent routine,
.I sucomp ,
is called that computes the Sethi-Ullman numbers
for the tree (see below).
.PP
After the tree is canonicalized,
.I codgen
calls the routine
.I store
whose job is to select a subtree of the tree to be computed
and (usually) stored before beginning the
computation of the full tree.
.I Store
must return a tree that can be computed without need
for any temporary storage locations.
In effect, the only store operations generated while processing the subtree must be as a response
to explicit assignment operators in the tree.
This division of the job marks one of the more significant, and successful,
departures from most other compilers.
It means that the code generator can operate
under the assumption that there are enough
registers to do its job, without worrying about
temporary storage.
If a store into a temporary appears in the output, it is always
as a direct result of logic in the
.I store
routine; this makes debugging easier.
.PP
One consequence of this organization is that
code is not generated by a treewalk.
There are theoretical results that support this decision.
.[
Aho Johnson Optimal Code Trees jacm
.]
It may be desirable to compute several subtrees and store
them before tackling the whole tree;
if a subtree is to be stored, this is known before the code
generation for the subtree is begun, and the subtree is computed
when all scratch registers are available.
.PP
The
.I store
routine decides what subtrees, if any, should be
stored by making use of numbers,
called
.I "Sethi-Ullman numbers" ,
that give, for each subtree of an expression tree,
the minimum number of scratch registers required to
compile the subtree, without any stores into temporaries.
.[
Sethi Ullman jacm 1970
.]
These numbers are computed by the machine-dependent
routine
.I sucomp ,
called by
.I canon .
The basic notion is that, knowing the Sethi-Ullman numbers for
the descendants of a node, and knowing the operator of the
node and some information about the machine, the
Sethi-Ullman number of the node itself can be computed.
If the Sethi-Ullman number for a tree exceeds the number of scratch
registers available, some subtree must be stored.
Unfortunately, the theory behind the Sethi-Ullman numbers
applies only to uselessly simple machines and operators.
For the rich set of C operators, and for machines with
asymmetric registers, register pairs, different kinds of registers,
and exceptional forms of addressing,
the theory cannot be applied directly.
The basic idea of estimation is a good one, however,
and well worth applying; the application, especially
when the compiler comes to be tuned for high code
quality, goes beyond the park of theory into the
swamp of heuristics.
This topic will be taken up again later, when more of the compiler
structure has been described.
.PP
After examining the Sethi-Ullman numbers,
.I store
selects a subtree, if any, to be stored, and returns the subtree and the associated cookie in
the external variables
.I stotree
and
.I stocook .
If a subtree has been selected, or if
the whole tree is ready to be processed, the
routine
.I order
is called, with a tree and cookie.
.I Order
generates code for trees that
do not require temporary locations.
.I Order
may make recursive calls on itself, and,
in some cases, on
.I codgen ;
for example, when processing the operators &&, \(or\(or, and comma (`,'), that have
a left to right evaluation, it is
incorrect for
.I store
examine the right operand for subtrees to be stored.
In these cases,
.I order
will call
.I codgen
recursively when it is permissible to work on the right operand.
A similar issue arises with the ? : operator.
.PP
The
.I order
routine works by matching the current tree with
a set of code templates.
If a template is discovered that will
match the current tree and cookie, the associated assembly language
statement or statements are generated.
The tree is then rewritten,
as specified by the template, to represent the effect of the output instruction(s).
If no template match is found, first an attempt is made to find a match with a
different cookie; for example, in order to compute
an expression with cookie INTEMP (store into a temporary storage location),
it is usually necessary to compute the expression into a scratch register
first.
If all attempts to match the tree fail, the heuristic part of
the algorithm becomes dominant.
Control is typically given to one of a number of machine-dependent routines
that may in turn recursively call
.I order
to achieve a subgoal of the computation (for example, one of the
arguments may be computed into a temporary register).
After this subgoal has been achieved, the process begins again with the
modified tree.
If the machine-dependent heuristics are unable to reduce the tree further,
a number of default rewriting rules may be considered appropriate.
For example, if the left operand of a + is a scratch
register, the + can be replaced by a += operator;
the tree may then match a template.
.PP
To close this introduction, we will discuss the steps in compiling
code for the expression
.DS
\fIa\fR += \fIb\fR
.DE
where
.I a
and
.I b
are static variables.
.PP
To begin with, the whole expression tree is examined with cookie FOREFF, and
no match is found.  Search with other cookies is equally fruitless, so an
attempt at rewriting is made.