porttour2

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

it is essential that the allocator keep track of those registers that
are free and busy, in order to detect such conditions.
.PP
Allocation of registers takes place as the result of a template
match; the routine
.I allo
is called with a word describing the number of A registers,
B registers, and temporary locations needed.
The allocation of temporary locations on the stack is relatively
straightforward, and will not be further covered; the
bookkeeping is a bit tricky, but conceptually trivial, and requests
for temporary space on the stack will never fail.
.PP
Register allocation is less straightforward.
The two major complications are
.I pairing
and
.I sharing .
In many machines, some operations (such as multiplication
and division), and/or some types (such as longs or double precision)
require even/odd pairs of registers.
Operations of the first type are exceptionally difficult to
deal with in the compiler; in fact, their theoretical
properties are rather bad as well.
.[
Aho Johnson Ullman Multiregister
.]
The second issue is dealt with rather more successfully;
a machine dependent function called
.I szty(t)
is called that returns 1 or 2, depending on the
number of A registers required to hold an object of type
.I t .
If
.I szty
returns 2, an even/odd pair of A registers is allocated
for each request.
.PP
The other issue, sharing, is more subtle, but
important for good code quality.
When registers are allocated, it
is possible to reuse registers that hold address
information, and use them to contain the values
computed or accessed.
For example, on the IBM 360, if register 2 has
a pointer to an integer in it, we may load the
integer into register 2 itself by saying:
.DS
L	2,0(2)
.DE
If register 2 had a byte pointer, however, the sequence for
loading a character involves clearing the target
register first, and then inserting the desired character:
.DS
SR	3,3
IC	3,0(2)
.DE
In the first case, if register 3 were used as the target,
it would lead to a larger number of registers
used for the expression than were required; the compiler would
generate inefficient code.
On the other hand, if register 2 were used as the target in the second
case, the code would simply be wrong.
In the first case, register 2 can be 
.I shared
while in the second, it cannot.
.PP
In the specification of the register needs in the templates,
it is possible to indicate whether required scratch registers
may be shared with possible registers on the left or the right of the input tree.
In order that a register be shared, it must be scratch, and it must
be used only once, on the appropriate side of the tree being compiled.
.PP
The
.I allo
routine thus has a bit more to do than meets the eye;
it calls
.I freereg
to obtain a free register for each A and B register request.
.I Freereg
makes multiple calls on the routine
.I usable
to decide if a given register can be used to satisfy
a given need.
.I Usable
calls
.I shareit
if the register is busy, but might be shared.
Finally,
.I shareit
calls
.I ushare
to decide if the desired register is actually in the appropriate
subtree, and can be shared.
.PP
Just to add additional complexity, on some machines (such as the IBM 370) it
is possible to have ``double indexing'' forms of
addressing; these are represented by OREGS's
with the base and index registers encoded into the register field.
While the register allocation and deallocation
.I "per se"
is not made more difficult by this phenomenon, the code itself
is somewhat more complex.
.PP
Having allocated the registers and expanded the assembly language,
it is time to reclaim the resources; the routine
.I reclaim
does this.
Many operations produce more than one result.
For example, many arithmetic operations may produce
a value in a register, and also set the condition
codes.
Assignment operations may leave results both in a register and in memory.
.I Reclaim
is passed three parameters; the tree and cookie
that were matched, and the rewriting field of the template.
The rewriting field allows the specification of possible results;
the tree is rewritten to reflect the results of the operation.
If the tree was computed for side effects only (FOREFF),
the tree is freed, and all resources in it reclaimed.
If the tree was computed for condition codes, the resources
are also freed, and the tree replaced by a special
node type, FORCC.
Otherwise, the value may be found in the left
argument of the root, the right argument of the root,
or one of the temporary resources allocated.
In these cases, first the resources of the tree,
and the newly allocated resources,
are
freed; then the resources needed by the result
are made busy again.
The final result must always match the shape of the input cookie;
otherwise, the compiler error
``cannot reclaim''
is generated.
There are some machine dependent ways of
preferring results in registers or memory when
there are multiple results matching multiple goals in the cookie.
.SH
The Machine Dependent Interface
.PP
The files
.I order.c ,
.I local2.c ,
and
.I table.c ,
as well as the header file
.I mac2defs ,
represent the machine dependent portion of the second pass.
The machine dependent portion can be roughly divided into
two: the easy portion and the hard portion.
The easy portion
tells the compiler the names of the registers, and arranges that
the compiler generate the proper assembler formats, opcode names, location counters, etc.
The hard portion involves the Sethi\-Ullman computation, the
rewriting rules, and, to some extent, the templates.
It is hard because there are no real algorithms that apply;
most of this portion is based on heuristics.
This section discusses the easy portion; the next several
sections will discuss the hard portion.
.PP
If the compiler is adapted from a compiler for a machine
of similar architecture, the easy part is indeed easy.
In
.I mac2defs ,
the register numbers are defined, as well as various parameters for
the stack frame, and various macros that describe the machine architecture.
If double indexing is to be permitted, for example, the symbol
R2REGS is defined.
Also, a number of macros that are involved in function call processing,
especially for unusual function call mechanisms, are defined here.
.PP
In
.I local2.c ,
a large number of simple functions are defined.
These do things such as write out opcodes, register names,
and address forms for the assembler.
Part of the function call code is defined here; that is nontrivial
to design, but typically rather straightforward to implement.
Among the easy routines in
.I order.c
are routines for generating a created label,
defining a label, and generating the arguments
of a function call.
.PP
These routines tend to have a local effect, and depend on a fairly straightforward way
on the target assembler and the design decisions already made about
the compiler.
Thus they will not be further treated here.
.SH
The Rewriting Rules
.PP
When a tree fails to match any template, it becomes
a candidate for rewriting.
Before the tree is rewritten,
the machine dependent routine
.I nextcook
is called with the tree and the cookie; it suggests
another cookie that might be a better candidate for the
matching of the tree.
If all else fails, the templates are searched with the cookie
FORREW, to look for a rewriting rule.
The rewriting rules are of two kinds;
for most of the common operators, there are
machine dependent rewriting rules that may be applied;
these are handled by machine dependent functions
that are called and given the tree to be computed.
These routines may recursively call
.I order
or
.I codgen
to cause certain subgoals to be achieved;
if they actually call for some alteration of the tree,
they return 1, and the
code generation algorithm recanonicalizes and tries again.
If these routines choose not to deal with the tree, the
default rewriting rules are applied.
.PP
The assignment ops, when rewritten, call the routine
.I setasg .
This is assumed to rewrite the tree at least to the point where there are
no side effects in the left hand side.
If there is still no template match,
a default rewriting is done that causes
an expression such as
.DS
.I "a += b"
.DE
to be rewritten as
.DS
.I "a = a + b"
.DE
This is a useful default for certain mixtures of strange types
(for example, when
.I a
is a bit field and
.I b
an character) that
otherwise might need separate table entries.
.PP
Simple assignment, structure assignment, and all forms of calls
are handled completely by the machine dependent routines.
For historical reasons, the routines generating the calls return
1 on failure, 0 on success, unlike the other routines.
.PP
The machine dependent routine
.I setbin
handles binary operators; it too must do most of the job.
In particular, when it returns 0, it must do so with
the left hand side in a temporary register.
The default rewriting rule in this case is to convert the
binary operator into the associated assignment operator;
since the left hand side is assumed to be a temporary register,
this preserves the semantics and often allows a considerable
saving in the template table.
.PP
The increment and decrement operators may be dealt with with
the machine dependent routine
.I setincr .
If this routine chooses not to deal with the tree, the rewriting rule replaces
.DS
.I "x ++"
.DE
by
.DS
.I "( (x += 1) \- 1)"
.DE
which preserves the semantics.
Once again, this is not too attractive for the most common
cases, but can generate close to optimal code when the
type of x is unusual.
.PP
Finally, the indirection (UNARY MUL) operator is also handled
in a special way.
The machine dependent routine
.I offstar
is extremely important for the efficient generation of code.
.I Offstar
is called with a tree that is the direct descendant of a UNARY MUL node;
its job is to transform this tree so that the combination of
UNARY MUL with the transformed tree becomes addressable.
On most machines,
.I offstar
can simply compute the tree into an A or B register,
depending on the architecture, and then
.I canon
will make the resulting tree into an OREG.
On many machines,
.I offstar
can profitably choose to do less work than computing
its entire argument into a register.
For example, if the target machine supports OREGS
with a constant offset from a register, and
.I offstar
is called
with a tree of the form
.DS
.I "expr + const"
.DE
where
.I const
is a constant, then
.I offstar
need only compute
.I expr
into the appropriate form of register.
On machines that support double indexing,
.I offstar
may have even more choice as to how to proceed.
The proper tuning of
.I offstar ,
which is not typically too difficult, should be one of the
first tries at optimization attempted by the
compiler writer.