porttour2

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

Suppose we are dealing with the Interdata 8/32 for the moment.
It is recognized that the left hand and right hand sides of the += operator
are addressable, and in particular the left hand side has no
side effects, so it is permissible to rewrite this as
.DS
\fIa\fR = \fIa\fR + \fIb\fR
.DE
and this is done.
No match is found on this tree either, so a machine dependent rewrite is done; it is recognized
that the left hand side of the assignment is addressable, but the right hand side is not
in a register, so
.I order
is called recursively, being asked to put the right
hand side of the assignment into a register.
This invocation of
.I order
searches the tree for a match, and fails.
The machine dependent rule for +
notices that the right hand operand is addressable;
it decides to put the left operand into a scratch register.
Another recursive call to
.I order
is made, with the tree
consisting solely of the leaf
.I a ,
and the cookie asking that the value be placed into a scratch register.
This now matches a template, and a load instruction is emitted.
The node consisting of
.I a
is rewritten in place to represent the register into which
.I a
is loaded,
and this third call to
.I order
returns.
The second call to
.I order
now finds that it has the tree
.DS
\fBreg\fR + \fIb\fR
.DE
to consider.
Once again, there is no match, but the default rewriting rule rewrites
the + as a += operator, since the left operand is a scratch register.
When this is done, there is a match: in fact,
.DS
\fBreg\fR += \fIb\fR
.DE
simply describes the effect of the add instruction
on a typical machine.
After the add is emitted, the tree is rewritten
to consist merely of the register node, since the result of the add
is now in the register.
This agrees with the cookie passed to the second invocation of
.I order ,
so this invocation
terminates, returning to the first level.
The original tree has now
become
.DS
\fIa\fR = \fBreg\fR
.DE
which matches a template for the store instruction.
The store is output, and the tree rewritten to become
just a single register node.
At this point, since the top level call to
.I order
was
interested only in side effects, the call to
.I order
returns, and the code generation is completed;
we have generated a load, add, and store, as might have been expected.
.PP
The effect of machine architecture on this is considerable.
For example, on the Honeywell 6000, the machine dependent heuristics recognize that there is an ``add to storage''
instruction, so the strategy is quite different;
.I b
is loaded in to
a register, and then an add to storage instruction generated
to add this register in to
.I a .
The transformations, involving as they do the semantics of C,
are largely machine independent.
The decisions as to when to use them, however, are
almost totally machine dependent.
.PP
Having given a broad outline of
the code generation process, we shall next consider the
heart of it: the templates.
This leads naturally into discussions of template matching and register allocation,
and finally a discussion of the machine dependent interfaces and strategies.
.SH
The Templates
.PP
The templates describe the effect of the target machine instructions
on the model of computation around which the compiler is organized.
In effect, each template has five logical sections, and represents an assertion
of the form:
.IP
.B If
we have a subtree of a given shape (1), and we have a goal (cookie) or goals to
achieve (2), and we have sufficient free resources (3),
.B then
we may emit an instruction or instructions (4), and
rewrite the subtree in a particular manner (5),
and the rewritten tree will achieve the desired goals.
.PP
These five sections will be discussed in more
detail later.  First, we give an example of a
template:
.DS
.ta 1i 2i 3i 4i 5i
ASG PLUS,	INAREG,
	SAREG,	TINT,
	SNAME,	TINT,
		0,	RLEFT,
		"	add	AL,AR\en",
.DE
The top line specifies the operator (+=) and the cookie (compute the
value of the subtree into an AREG).
The second and third lines specify the left and right descendants,
respectively,
of the += operator.
The left descendant must be a REG node, representing an
A register, and have integer type, while the right side must be a NAME node,
and also have integer type.
The fourth line contains the resource requirements (no scratch registers
or temporaries needed), and the rewriting rule (replace the subtree by the left descendant).
Finally, the quoted string on the last line represents the output to the assembler:
lower case letters, tabs, spaces, etc. are copied
.I verbatim .
to the output; upper case letters trigger various macro-like expansions.
Thus,
.B AL
would expand into the \fBA\fRddress form of the \fBL\fReft operand \(em
presumably the register number.
Similarly,
.B AR
would expand into the name of the right operand.
The
.I add
instruction of the last section might well be
emitted by this template.
.PP
In principle, it would be possible to make separate templates
for all legal combinations of operators, cookies, types, and shapes.
In practice, the number of combinations is very large.
Thus, a considerable amount of mechanism is present to
permit a large number of subtrees to be matched
by a single template.
Most of the shape and type specifiers are individual bits, and can
be logically
or'ed
together.
There are a number of special descriptors for matching classes of
operators.
The cookies can also be combined.
As an example of the kind of template
that really arises in practice, the
actual template for the Interdata 8/32
that subsumes the above example is:
.DS
.ta 1i 2i 3i 4i 5i
ASG OPSIMP,	INAREG\(orFORCC,
	SAREG,	TINT\(orTUNSIGNED\(orTPOINT,
	SAREG\(orSNAME\(orSOREG\(orSCON,	TINT\(orTUNSIGNED\(orTPOINT,
		0,	RLEFT\(orRESCC,
		"	OI	AL,AR\en",
.DE
Here, OPSIMP represents the operators
+, \-, \(or, &, and ^.
The
.B OI
macro in the output string expands into the
appropriate \fBI\fRnteger \fBO\fRpcode for the operator.
The left and right sides can be integers, unsigned, or pointer types.
The right side can be, in addition to a name, a register,
a memory location whose address is given by a register and displacement (OREG),
or a constant.
Finally, these instructions set the condition codes,
and so can be used in condition contexts:
the cookie and rewriting rules reflect this.
.SH
The Template Matching Algorithm.
.PP
The heart of the second pass is the template matching
algorithm, in the routine
.I match .
.I Match
is called with a tree and a cookie; it attempts to match
the given tree against some template that will transform it
according to one of the goals given in the cookie.
If a match is successful, the transformation is
applied;
.I expand
is called to generate the assembly code, and then
.I reclaim
rewrites the tree, and reclaims the resources, such
as registers, that might have become free as a result
of the generated code.
.PP
This part of the compiler is among the most time critical.
There is a spectrum of implementation techniques available
for doing this matching.
The most naive algorithm simply looks at the templates one by one.
This can be considerably improved upon by restricting the search
for an acceptable template.
It would be possible to do better than this if the templates were given
to a separate program that ate them and generated a template
matching subroutine.
This would make maintenance of the compiler much more
complicated, however, so this has not been done.
.PP
The matching algorithm is actually carried out by restricting
the range in the table that must be searched for each opcode.
This introduces a number of complications, however, and needs a
bit of sympathetic help by the person constructing the
compiler in order to obtain best results.
The exact tuning of this algorithm continues; it
is best to consult the code and comments in
.I match
for the latest version.
.PP
In order to match a template to a tree,
it is necessary to match not only the cookie and the
op of the root, but also the types and shapes of the
left and right descendants (if any) of the tree.
A convention is established here that is carried out throughout
the second pass of the compiler.
If a node represents a unary operator, the single descendant
is always the ``left'' descendant.
If a node represents a unary operator or a leaf node (no descendants)
the ``right'' descendant is taken by convention to be the node itself.
This enables templates to easily match leaves and conversion operators, for example,
without any additional mechanism in the matching program.
.PP
The type matching is straightforward; it is possible to specify any combination
of basic types, general pointers, and pointers to one or more of
the basic types.
The shape matching is somewhat more complicated, but still pretty simple.
Templates have a collection of possible operand shapes
on which the opcode might match.
In the simplest case, an
.I add
operation might be able to add to either a register variable
or a scratch register, and might be able (with appropriate
help from the assembler) to add an integer constant (ICON), a static
memory cell (NAME), or a stack location (OREG).
.PP
It is usually attractive to specify a number of such shapes,
and distinguish between them when the assembler output is produced.
It is possible to describe the union of many elementary
shapes such as ICON, NAME, OREG,
AREG or BREG
(both scratch and register forms), etc.
To handle at least the simple forms of indirection, one can also
match some more complicated forms of trees; STARNM and STARREG
can match more complicated trees headed by an indirection operator,
and SFLD can match certain trees headed by a FLD operator: these
patterns call machine dependent routines that match the
patterns of interest on a given machine.
The shape SWADD may be used to recognize NAME or OREG
nodes that lie on word boundaries: this may be of some importance
on word\-addressed machines.
Finally, there are some special shapes: these may not
be used in conjunction with the other shapes, but may be
defined and extended in machine dependent ways.
The special shapes SZERO, SONE, and SMONE are predefined and match
constants 0, 1, and \-1, respectively; others are easy to add
and match by using the machine dependent routine
.I special .
.PP
When a template has been found that matches the root of the tree,
the cookie, and the shapes and types of the descendants,
there is still one bar to a total match: the template may
call for some resources (for example, a scratch register).
The routine
.I allo
is called, and it attempts to allocate the resources.
If it cannot, the match fails; no resources are
allocated.
If successful, the allocated resources are given numbers
1, 2, etc. for later reference when the assembly code is
generated.
The routines
.I expand
and
.I reclaim
are then called.
The
.I match
routine then returns a special value, MDONE.
If no match was found, the value MNOPE is returned;
this is a signal to the caller to try more cookie
values, or attempt a rewriting rule.
.I Match
is also used to select rewriting rules, although
the way of doing this is pretty straightforward.
A special cookie, FORREW, is used to ask
.I match
to search for a rewriting rule.
The rewriting rules are keyed to various opcodes; most
are carried out in
.I order .
Since the question of when to rewrite is one of the key issues in
code generation, it will be taken up again later.
.SH
Register Allocation.
.PP
The register allocation routines, and the allocation strategy,
play a central role in the correctness of the code generation algorithm.
If there are bugs in the Sethi-Ullman computation that cause the
number of needed registers to be underestimated,
the compiler may run out of scratch registers;