porttour2

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

.SH
The Sethi-Ullman Computation
.PP
The heart of the heuristics is the computation of the Sethi-Ullman numbers.
This computation is closely linked with the rewriting rules and the
templates.
As mentioned before, the Sethi-Ullman numbers are expected to
estimate the number of scratch registers needed to compute
the subtrees without using any stores.
However, the original theory does not apply to real machines.
For one thing, the theory assumes that all registers
are interchangeable.
Real machines have general purpose, floating point, and index registers,
register pairs, etc.
The theory also does not account for side effects;
this rules out various forms of pathology that arise
from assignment and assignment ops.
Condition codes are also undreamed of.
Finally, the influence of types, conversions, and the
various addressability restrictions and extensions of real
machines are also ignored.
.PP
Nevertheless, for a ``useless'' theory,
the basic insight of Sethi and Ullman is amazingly
useful in a real compiler.
The notion that one should attempt to estimate the
resource needs of trees before starting the
code generation provides a natural means of splitting the
code generation problem, and provides a bit of redundancy
and self checking in the compiler.
Moreover, if writing the
Sethi-Ullman routines is hard, describing, writing, and debugging the
alternative (routines that attempt to free up registers by stores into
temporaries ``on the fly'') is even worse.
Nevertheless, it should be clearly understood that these routines exist in a realm
where there is no ``right'' way to write them;
it is an art, the realm of heuristics, and, consequently, a major
source of bugs in the compiler.
Often, the early, crude versions of these routines give little trouble;
only after
the compiler is actually working
and the
code quality is being improved do serious problem have to be faced.
Having a simple, regular machine architecture is worth quite
a lot at this time.
.PP
The major problems arise from asymmetries in the registers: register pairs,
having different kinds of registers, and the related problem of
needing more than one register (frequently a pair) to store certain
data
types (such as longs or doubles).
There appears to be no general way of treating this problem;
solutions have to be fudged for each machine where the problem arises.
On the Honeywell 66, for example, there are only two general purpose registers,
so a need for a pair is the same as the need for two registers.
On the IBM 370, the register pair (0,1) is used to do multiplications and divisions;
registers 0 and 1 are not generally considered part of the scratch registers, and so
do not require allocation explicitly.
On the Interdata 8/32, after much consideration, the
decision was made not to try to deal with the register pair issue;
operations such as multiplication and division that required pairs
were simply assumed to take all of the scratch registers.
Several weeks of effort had failed to produce
an algorithm that seemed to have much chance of running successfully
without inordinate debugging effort.
The difficulty of this issue should not be minimized; it represents one of the
main intellectual efforts in porting the compiler.
Nevertheless, this problem has been fudged with a degree of
success on nearly a dozen machines, so the compiler writer should
not abandon hope.
.PP
The Sethi-Ullman computations interact with the
rest of the compiler in a number of rather subtle ways.
As already discussed, the
.I store
routine uses the Sethi-Ullman numbers to decide which subtrees are too difficult
to compute in registers, and must be stored.
There are also subtle interactions between the
rewriting routines and the Sethi-Ullman numbers.
Suppose we have a tree such as
.DS
.I "A \- B"
.DE
where
.I A
and
.I B
are expressions; suppose further that
.I B
takes two registers, and
.I A
one.
It is possible to compute the full expression in two registers by
first computing
.I B ,
and then, using the scratch register
used by
.I B ,
but not containing the answer, compute
.I A .
The subtraction can then be done, computing the expression.
(Note that this assumes a number of things, not the least of which
are register-to-register subtraction operators and symmetric
registers.)
If the machine dependent routine
.I setbin ,
however, is not prepared to recognize this case
and compute the more difficult side of the expression
first, the
Sethi-Ullman number must be set to three.
Thus, the
Sethi-Ullman number for a tree should represent the code that
the machine dependent routines are actually willing to generate.
.PP
The interaction can go the other way.
If we take an expression such as
.DS
.I "* ( p + i )"
.DE
where
.I p
is a pointer and
.I i
an integer,
this can probably be done in one register on most machines.
Thus, its Sethi-Ullman number would probably be set to one.
If double indexing is possible in the machine, a possible way
of computing the expression is to load both
.I p
and
.I i
into registers, and then use double indexing.
This would use two scratch registers; in such a case,
it is possible that the scratch registers might be unobtainable,
or might make some other part of the computation run out of
registers.
The usual solution is to cause
.I offstar
to ignore opportunities for double indexing that would tie up more scratch
registers than the Sethi-Ullman number had reserved.
.PP
In summary, the Sethi-Ullman computation represents much of the craftsmanship and artistry in any application
of the portable compiler.
It is also a frequent source of bugs.
Algorithms are available that will produce nearly optimal code
for specialized machines, but unfortunately most existing machines
are far removed from these ideals.
The best way of proceeding in practice is to start with a compiler
for a similar machine to the target, and proceed very
carefully.
.SH
Register Allocation
.PP
After the Sethi-Ullman numbers are computed,
.I order
calls a routine,
.I rallo ,
that does register allocation, if appropriate.
This routine does relatively little, in general;
this is especially true if the target machine
is fairly regular.
There are a few cases where it is assumed that
the result of a computation takes place in a particular register;
switch and function return are the two major places.
The expression tree has a field,
.I rall ,
that may be filled with a register number; this is taken
to be a preferred register, and the first temporary
register allocated by a template match will be this preferred one, if
it is free.
If not, no particular action is taken; this is just a heuristic.
If no register preference is present, the field contains NOPREF.
In some cases, the result must be placed in
a given register, no matter what.
The register number is placed in
.I rall ,
and the mask MUSTDO is logically or'ed in with it.
In this case, if the subtree is requested in a register, and comes
back in a register other than the demanded one, it is moved
by calling the routine
.I rmove .
If the target register for this move is busy, it is a compiler
error.
.PP
Note that this mechanism is the only one that will ever cause a register-to-register
move between scratch registers (unless such a move is buried in the depths of
some template).
This simplifies debugging.
In some cases, there is a rather strange interaction between
the register allocation and the Sethi-Ullman number;
if there is an operator or situation requiring a
particular register, the allocator and the Sethi-Ullman
computation must conspire to ensure that the target
register is not being used by some intermediate result of some far-removed computation.
This is most easily done by making the special operation take
all of the free registers, preventing any other partially-computed
results from cluttering up the works.
.SH
Compiler Bugs
.PP
The portable compiler has an excellent record of generating correct code.
The requirement for reasonable cooperation between the register allocation,
Sethi-Ullman computation, rewriting rules, and templates builds quite a bit
of redundancy into the compiling process.
The effect of this is that, in a surprisingly short time, the compiler will
start generating correct code for those
programs that it can compile.
The hard part of the job then becomes finding and
eliminating those situations where the compiler refuses to
compile a program because it knows it cannot do it right.
For example, a template may simply be missing; this may either
give a compiler error of the form ``no match for op ...'' , or cause
the compiler to go into an infinite loop applying various rewriting rules.
The compiler has a variable,
.I nrecur ,
that is set to 0 at the beginning of an expressions, and
incremented at key spots in the
compilation process; if this parameter gets too large, the
compiler decides that it is in a loop, and aborts.
Loops are also characteristic of botches in the machine-dependent rewriting rules.
Bad Sethi-Ullman computations usually cause the scratch registers
to run out; this often means
that the Sethi-Ullman number was underestimated, so
.I store
did not store something it should have; alternatively,
it can mean that the rewriting rules were not smart enough to
find the sequence that
.I sucomp
assumed would be used.
.PP
The best approach when a compiler error is detected involves several stages.
First, try to get a small example program that steps on the bug.
Second, turn on various debugging flags in the code generator, and follow the
tree through the process of being matched and rewritten.
Some flags of interest are
\-e, which prints the expression tree,
\-r, which gives information about the allocation of registers,
\-a, which gives information about the performance of
.I rallo ,
and \-o, which gives information about the behavior of
.I order .
This technique should allow most bugs to be found relatively quickly.
.PP
Unfortunately, finding the bug is usually not enough; it must also
be fixed!
The difficulty arises because a fix to the particular bug of interest tends
to break other code that already works.
Regression tests, tests that compare the performance of
a new compiler against the performance of an older one, are very
valuable in preventing major catastrophes.
.SH
Summary and Conclusion
.PP
The portable compiler has been a useful tool for providing C
capability on a large number of diverse machines,
and for testing a number of theoretical
constructs in a practical setting.
It has many blemishes, both in style and functionality.
It has been applied to many more machines than first
anticipated, of a much wider range than originally dreamed of.
Its use has also spread much faster than expected, leaving parts of
the compiler still somewhat raw in shape.
.PP
On the theoretical side, there is some hope that the
skeleton of the
.I sucomp
routine could be generated for many machines directly from the
templates; this would give a considerable boost
to the portability and correctness of the compiler,
but might affect tunability and code quality.
There is also room for more optimization, both within
.I optim
and in the form of a portable ``peephole'' optimizer.
.PP
On the practical, development side,
the compiler could probably be sped up and made smaller
without doing too much violence to its basic structure.
Parts of the compiler deserve to be rewritten;
the initialization code, register allocation, and
parser are prime candidates.
It might be that doing some or all of the parsing
with a recursive descent parser might
save enough space and time to be worthwhile;
it would certainly ease the problem of moving the
compiler to an environment where
.I Yacc
is not already present.
.PP
Finally, I would like to thank the many people who have
sympathetically, and even enthusiastically, helped me grapple
with what has been a frustrating program to write, test, and install.
D. M. Ritchie and E. N. Pinson provided needed early
encouragement and philosophical guidance;
M. E. Lesk,
R. Muha, T. G. Peterson,
G. Riddle, L. Rosler,
R. W. Mitze,
B. R. Rowland,
S. I. Feldman,
and
T. B. London
have all contributed ideas, gripes, and all, at one time or another,
climbed ``into the pits'' with me to help debug.
Without their help this effort would have not been possible;
with it, it was often kind of fun.
.sp 100
.LP
.[
$LIST$
.]
.LP
.sp 100
.LP