cdoc3

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

arranges that the current register is odd;
the R\- notation allows the code to refer to the next lower,
even-numbered register.
.LP
To refer to addressible quantities, there are the notations:
.IP A1
causes generation of the address specified by the first operand.
For this to be legal, the operand must be addressible; its 
key must contain an `a'
or a more restrictive specification.
.RT
.IP A2
correspondingly generates the address of the second operand
providing it has one.
.PP
We now have enough mechanism to show a complete, if suboptimal,
table for the + operator on word or byte operands.
.DS
%n,z
	F
.sp 1
%n,1
	F
	inc	R
.sp 1
%n,aw
	F
	add	A2,R
.sp 1
%n,e
	F
	S1
	add	R1,R
.sp 1
%n,n
	SS
	F
	add	(sp)+,R
.DE
The first two sequences handle some special cases.
Actually it turns out that handling a right operand of 0
is unnecessary since the expression-optimizer
throws out adds of 0.
Adding 1 by using the `increment' instruction is done next,
and then the case where the right operand is addressible.
It must be a word quantity, since the PDP-11 lacks an `add byte' instruction.
Finally the cases where the right operand either can, or cannot,
be done in the available registers are treated.
.PP
The next macro-instructions are conveniently
introduced by noticing that the above table is suitable
for subtraction as well as addition, since no use is made of the
commutativity of addition.
All that is needed is substitution of `sub' for `add'
and `dec' for 'inc.'
Considerable saving of space is achieved by factoring out
several similar operations.
.IP I
is replaced by a string from another table indexed by the operator
in the node being expanded.
This secondary table actually contains two strings per operator.
.RT
.IP I\(fm
is replaced by the second string in the side table
entry for the current operator.
.PP
Thus, given that the entries for `+' and `\-' in the side table
(which is called
.II instab)
are `add' and `inc,' `sub' and `dec'
respectively,
the middle of of the above addition table can be written
.DS
%n,1
	F
	I'	R

%n,aw
	F
	I	A2,R
.DE
and it will be suitable for subtraction,
and several other operators, as well.
.PP
Next, there is the question of character and floating-point operations.
.IP B1
generates the letter `b' if the first operand is a character,
`f' if it is float or double, and nothing otherwise.
It is used in a context like `movB1'
which generates a `mov', `movb', or `movf'
instruction according to the type of the operand.
.RT
.IP B2
is just like B1 but applies to the second operand.
.RT
.IP BE
generates `b' if either operand is a character
and null otherwise.
.RT
.IP BF
generates `f' if the type of the operator node itself is float or double,
otherwise null.
.PP
For example, there is an entry in
.II efftab
for the `=' operator
.DS
%a,aw
%ab,a
	IBE	A2,A1
.DE
Note first that two key specifications
can be applied to the same code string.
Next, observe that when a word is assigned to a byte or to a word,
or a word is assigned to a byte,
a single instruction,
a
.II mov
or
.II movb
as appropriate, does the job.
However, when a byte is assigned to a word,
it must pass through a register to implement the sign-extension rules:
.DS
%a,n
	S
	IB1	R,A1
.DE
.PP
Next, there is the question of handling indirection properly.
Consider the expression `X + *Y', where X and Y are expressions,
Assuming that Y is more complicated than just a variable,
but on the other hand qualifies as `easy' in the context,
the expression would be compiled by placing the value of X in a register,
that of *Y in the next register, and adding the registers.
It is easy to see that a better job can be done
by compiling X, then Y (into the next register),
and producing the
instruction symbolized by `add (R1),R'.
This scheme avoids generating
the instruction `mov (R1),R1'
required actually to place the value of *Y in a register.
A related situation occurs
with the expression `X + *(p+6)', which
exemplifies a construction
frequent in structure and array references.
The addition table shown above would produce
.DS
[put X in register R]
mov	p,R1
add	$6,R1
mov	(R1),R1
add	R1,R
.DE
when the best code is
.DS
[put X in R]
mov	p,R1
add	6(R1),R
.DE
As we said above, a key specification for a code table entry
may require an operand to have an indirection as its highest operator.
To make use of the requirement,
the following macros are provided.
.IP F*
the first operand must have the form *X.
If in particular it has the form *(Y + c), for some constant
.II c,
then code is produced which places the value of Y in
the current register.
Otherwise, code is produced which loads X into the current register.
.RT
.IP F1*
resembles F* except that the next register is loaded.
.RT
.IP S*
resembles F* except that the second operand is loaded.
.RT
.IP S1*
resembles S* except that the next register is loaded.
.RT
.IP FS*
The first operand must have the form `*X'.
Push the value of X on the stack.
.RT
.IP SS*
resembles FS* except that it applies to the second operand.
.LP
To capture the constant that may have been skipped over
in the above macros, there are
.IP #1
The first operand must have the form *X;
if in particular it has the form *(Y + c) for
.II c
a constant, then the constant is written out,
otherwise a null string.
.RT
.IP #2
is the same as #1 except that the second operand is used.
.LP
Now we can improve the addition table above.
Just before the `%n,e' entry, put
.DS
%n,ew*
	F
	S1*
	add	#2(R1),R
.DE
and just before the `%n,n' put
.DS
%n,nw*
	SS*
	F
	add	*(sp)+,R
.DE
When using the stacking macros there is no place to use
the constant
as an index word, so that particular special case doesn't occur.
.PP
The constant mentioned above can actually be more
general than a number.
Any quantity acceptable to the assembler as an expression will do,
in particular the address of a static cell, perhaps with a numeric offset.
If
.II x
is an external character array,
the expression `x[i+5] = 0' will generate
the code
.DS
mov	i,r0
clrb	x+5(r0)
.DE
via the table entry (in the `=' part of
.II efftab)
.DS
%e*,z
	F
	I'B1	#1(R)
.DE
Some machine operations place restrictions on the registers
used.
The divide instruction, used to implement the divide and mod
operations, requires the dividend to be placed in the odd member
of an even-odd pair;
other peculiarities
of multiplication make it simplest to put the multiplicand
in an odd-numbered register.
There is no theory which optimally accounts for
this kind of requirement.
.II Cexpr
handles it by checking for a multiply, divide, or mod operation;
in these cases, its argument register number is incremented by
one or two so that it is odd, and if the operation was divide or mod,
so that it is a member of a free even-odd pair.
The routine which determines the number of registers required
estimates, conservatively, that
at least two registers are required for a multiplication
and three for the other peculiar operators.
After the expression is compiled,
the register where the result actually ended up is returned.
(Divide and mod are actually the same operation except for the
location of the result).
.PP
These operations are the ones which cause results to end up in
unexpected places,
and this possibility adds a further level of complexity.
The simplest way of handling the problem is always to move the
result to the place where the caller expected it,
but this will produce unnecessary register moves in many
simple cases; `a = b*c' would generate
.DS
mov	b,r1
mul	c,r1
mov	r1,r0
mov	r0,a
.DE
The next thought is used the passed-back
information as to where the result landed to change the notion of the current
register.
While compiling the `=' operation above, which comes from a
table
entry
like
.DS
%a,e
	S
	mov	R,A1
.DE
it is sufficient to redefine the meaning of `R'
after processing the `S' which does the multiply.
This technique is in fact used; the tables are written in such a way
that correct code is produced.
The trouble is that the technique cannot be used in general,
because it invalidates the count of the number of registers
required for an expression.
Consider just `a*b + X' where X is some expression.
The algorithm assumes that the value of a*b,
once computed, requires just one register.
If there are three registers available, and X requires two registers to
compute, then this expression will match a key specifying
`%n,e'.
If a*b is computed and left in register 1, then there are, contrary
to expectations, no longer two registers available to compute X,
but only one, and bad code will be produced.
To guard against this possibility,
.II cexpr
checks the result returned by recursive calls which implement
F, S and their relatives.
If the result is not in the expected register, then the number of
registers required by the other operand is checked;
if it can be done using those registers which remain even
after making unavailable the unexpectedly-occupied
register, then
the notions of the `next register' and possibly the `current
register' are redefined.
Otherwise a register-copy instruction is produced.
A register-copy is also always produced
when the current operator is one of those which have odd-even requirements.
.PP
Finally, there are a few loose-end macro operations
and facts about the tables.
The operators:
.IP V
is used for long operations.
It is written with an address like a machine instruction;
it expands into `adc' (add carry) if the operation
is an additive operator,
`sbc' (subtract carry) if the operation is a subtractive
operator, and disappears, along with the rest of the line, otherwise.
Its purpose is to allow common treatment of logical
operations, which have no carries, and additive and subtractive
operations, which generate carries.
.RT
.IP T
generates a `tst' instruction if the first operand
of the tree does not set the condition codes correctly.
It is used with divide and mod operations,
which require a sign-extended 32-bit operand.
The code table for the operations contains an `sxt'
(sign-extend) instruction to generate the high-order part of the
dividend.
.RT
.IP H
is analogous to the `F' and `S' macros,
except that it calls for the generation of code for
the current tree
(not one of its operands)
using
.II regtab.
It is used in
.II cctab
for all the operators which, when executed normally,
set the condition codes properly according to the result.
It prevents a `tst' instruction from being generated for
constructions like `if (a+b) ...'
since after calculation of the value of
`a+b' a conditional branch can be written immediately.
.PP
All of the discussion above is in terms of operators with operands.
Leaves of the expression tree (variables and constants), however,
are peculiar in that they have no operands.
In order to regularize the matching process,
.II cexpr
examines its operand to determine if it is a leaf;
if so, it creates a special `load' operator whose operand
is the leaf, and substitutes it for the argument tree;
this allows the table entry for the created operator
to use the `A1' notation to load the leaf into a register.
.PP
Purely to save space in the tables,
pieces of subtables can be labelled and referred to later.
It turns out, for example,
that rather large portions of the
the
.II efftab
table for the `=' and `=+' operators are identical.
Thus `=' has an entry
.DS
%[move3:]
%a,aw
%ab,a
	IBE	A2,A1
.DE
while part of the `=+' table is
.DS
%aw,aw
%	[move3]
.DE
Labels are written as `%[ ... : ]',
before the key specifications;
references
are written
with `%  [ ... ]'
after the key.
Peculiarities in the implementation
make it necessary that labels appear before references to them.
.PP
The example illustrates the utility
of allowing separate keys
to point to the same code string.
The assignment code
works properly if either the right operand is a word, or the left operand
is a byte;
but since there is no `add byte' instruction the addition code
has to be restricted to word operands.