Commit | Line | Data |
---|---|---|
1b5c1e54 DR |
1 | .SH |
2 | Code Generation | |
3 | .PP | |
4 | The grand plan for code-generation is | |
5 | independent of any particular machine; | |
6 | it depends largely on a set of tables. | |
7 | But this fact does not necessarily make it very easy | |
8 | to modify the compiler to produce code for other machines, | |
9 | both because there is a good deal of machine-dependent structure | |
10 | in the tables, and because in any event such tables are non-trivial to | |
11 | prepare. | |
12 | .PP | |
13 | The arguments to the basic code generation routine | |
14 | .II rcexpr | |
15 | are a pointer to a tree representing an expression, | |
16 | the name of a code-generation table, | |
17 | and the number of a register in which the value of the | |
18 | expression should be placed. | |
19 | .II Rcexpr | |
20 | returns the number of the register in which the value actually | |
21 | ended up; | |
22 | its caller | |
23 | may need to produce a | |
24 | .II mov | |
25 | instruction if the value really needs to be in the given register. | |
26 | There are four code generation tables. | |
27 | .PP | |
28 | .II Regtab | |
29 | is the basic one, which actually does the job described | |
30 | above: namely, | |
31 | compile code which places the value represented by the expression | |
32 | tree in a register. | |
33 | .PP | |
34 | .II Cctab | |
35 | is used when the value of the expression is not actually needed, | |
36 | but instead the value of the condition codes resulting from | |
37 | evaluation of the expression. | |
38 | This table is used, for example, to evaluate the expression after | |
39 | .II if. | |
40 | It is clearly silly to | |
41 | calculate the value (0 or 1) of the expression | |
42 | `a==b' in the context `if (a==b) ... ' | |
43 | .PP | |
44 | The | |
45 | .II sptab | |
46 | table is used when the value of an expression is to be pushed on the stack, | |
47 | for example when it is an actual argument. | |
48 | For example in the function call `f(a)' it is a bad idea to | |
49 | load | |
50 | .II a | |
51 | into a register which is then pushed on the stack, | |
52 | when there is a single instruction which does the job. | |
53 | .PP | |
54 | The | |
55 | .II efftab | |
56 | table is used when an expression is to be evaluated for its side effects, | |
57 | not its value. | |
58 | This occurs mostly for expressions which are statements, which have no | |
59 | value. | |
60 | Thus the code for the statement | |
61 | `a = b' | |
62 | need produce only the approoriate | |
63 | .II mov | |
64 | instruction, and need not leave the value of | |
65 | .II b | |
66 | in a register, | |
67 | while in the expression `a + (b = c)' | |
68 | the value of `b = c' will appear in a register. | |
69 | .PP | |
70 | All of the tables besides | |
71 | .II regtab | |
72 | are rather small, and handle only a relatively few special cases. | |
73 | If one of these subsidiary tables does not contain | |
74 | an entry applicable to the given expression tree, | |
75 | .II rcexpr | |
76 | uses | |
77 | .II regtab | |
78 | to put the value of the expression into a register | |
79 | and then fixes things up; | |
80 | nothing need be done when the table | |
81 | was | |
82 | .II efftab, | |
83 | but a | |
84 | .II tst | |
85 | instruction is produced when the table called for was | |
86 | .II cctab, | |
87 | and a | |
88 | .II mov | |
89 | instruction, | |
90 | pushing the register on the stack, | |
91 | when the table was | |
92 | .II sptab. | |
93 | .PP | |
94 | The | |
95 | .II rcexpr | |
96 | routine itself picks off some special | |
97 | cases, then calls | |
98 | .II cexpr | |
99 | to do the real work. | |
100 | .II Cexpr | |
101 | tries to find an entry applicable | |
102 | to the given tree in the given table, and returns \-1 if | |
103 | no such entry is found, letting | |
104 | .II rcexpr | |
105 | try again with a different table. | |
106 | A successful match yields a string | |
107 | containing both literal characters | |
108 | which are written out and pseudo-operations, or macros, which are expanded. | |
109 | Before studying the contents | |
110 | of these strings we will consider how table entries are matched | |
111 | against trees. | |
112 | .PP | |
113 | Recall that most non-leaf nodes in an expression tree | |
114 | contain the name of the operator, | |
115 | the type of the value represented, and pointers to the subtrees (operands). | |
116 | They also contain an estimate of the number of registers required to evaluate | |
117 | the expression, placed there by the expression-optimizer routines. | |
118 | The register counts are used to guide the code generation process, | |
119 | which is based on the Sethi-Ullman algorithm. | |
120 | .PP | |
121 | The main code generation | |
122 | tables consist of entries | |
123 | each containing an operator number and a pointer | |
124 | to a subtable for the corresponding operator. | |
125 | A subtable consists of a sequence | |
126 | of entries, each with a key describing certain properties of the | |
127 | operands of the operator involved; associated with the key is a code string. | |
128 | Once the subtable corresponding to the operator is found, the subtable | |
129 | is searched linearly until a key is found such that the properties demanded | |
130 | by the key are compatible with the operands of the tree node. | |
131 | A successful match returns the code string; | |
132 | an unsuccessful search, either for the operator in the main table | |
133 | or a compatble key in the subtable, | |
134 | returns a failure indication. | |
135 | .PP | |
136 | The tables are all contained in a file | |
137 | which must be processed to obtain an assembly language program. | |
138 | Thus they are written in a special-purpose language. | |
139 | To provided definiteness to the following discussion, here is an | |
140 | example of a subtable entry. | |
141 | .DS | |
142 | %n,aw | |
143 | F | |
144 | add A2,R | |
145 | .DE | |
146 | The `%' indicates the key; | |
147 | the information following (up to a blank line) specifies the code string. | |
148 | Very briefly, this entry is in the subtable | |
149 | for `+' of | |
150 | .II regtab; | |
151 | the key specifies that the left operand is any integer, character, or pointer | |
152 | expression, | |
153 | and the right operand is any word quantity which is directly addressible | |
154 | (e.g. a variable or constant). | |
155 | The code string calls for the generation of the code | |
156 | to compile the left (first) operand into the | |
157 | current register (`F') | |
158 | and then to produce an `add' instruction which adds the | |
159 | second operand (`A2') to the register (`R'). | |
160 | All of the notation will be explained below. | |
161 | .PP | |
162 | Only three features of the operands are used in deciding | |
163 | whether a match has occurred. | |
164 | They are: | |
165 | .IP 1. | |
166 | Is the type of the operand compatible with that demanded? | |
167 | .RT | |
168 | .IP 2. | |
169 | Is the `degree of difficulty' (in a sense described below) compatible? | |
170 | .RT | |
171 | .IP 3. | |
172 | The table may demand that the operand have a `*' | |
173 | (indirection operator) as its highest operator. | |
174 | .PP | |
175 | As suggested above, the key for a subtable entry | |
176 | is indicated by a `%,' and a comma-separated pair | |
177 | of specifications for the operands. | |
178 | (The second specification is ignored for unary operators). | |
179 | A specification indicates | |
180 | a type requirement by including one of the following letters. | |
181 | If no type letter is present, any integer, character, | |
182 | or pointer operand will satisfy the requirement (not float, double, or long). | |
183 | .IP b | |
184 | A byte (character) operand is required. | |
185 | .RT | |
186 | .IP w | |
187 | A word (integer or pointer) operand is required. | |
188 | .RT | |
189 | .IP f | |
190 | A float or double operand is required. | |
191 | .RT | |
192 | .IP d | |
193 | A double operand is required. | |
194 | .RT | |
195 | .IP l | |
196 | A long (32-bit integer) operand is required. | |
197 | .PP | |
198 | Before discussing the `degree of difficulty' specification, | |
199 | the algorithm has to be explained more completely. | |
200 | .II Rcexpr | |
201 | (and | |
202 | .II cexpr) | |
203 | are called with a register number in which to place their result. | |
204 | Registers 0, 1, ... are used during evaluation of expressions; | |
205 | the maximum register which can be used in this way depends on the | |
206 | number of register variables, but in any event only registers | |
207 | 0 through 4 are available since r5 is used as a stack frame | |
208 | header and r6 (sp) and r7 (pc) have special | |
209 | hardware properties. | |
210 | The code generation routines assume that when called with register | |
211 | .II n | |
212 | as argument, they may use | |
213 | .II n+1, | |
214 | \&... | |
215 | (up to the first register variable) | |
216 | as temporaries. | |
217 | Consider the expression `X+Y', where both | |
218 | X and Y are expressions. | |
219 | As a first approximation, there are three ways of compiling | |
220 | code to put this expression in register | |
221 | .II n. | |
222 | .IP 1. | |
223 | If Y is an addressible cell, | |
224 | (recursively) put X into register | |
225 | .II n | |
226 | and add Y to it. | |
227 | .RT | |
228 | .IP 2. | |
229 | If Y is an expression that can be calculated in | |
230 | .II k | |
231 | registers, where | |
232 | .II k | |
233 | smaller than the number of registers available, | |
234 | compile X into register | |
235 | .II n, | |
236 | Y into register | |
237 | .II n+1, | |
238 | and add register | |
239 | .II n+1 | |
240 | to | |
241 | .II n. | |
242 | .RT | |
243 | .IP 3. | |
244 | Otherwise, compile Y into register | |
245 | .II n, | |
246 | save the result in a temporary (actually, on the stack) | |
247 | compile X into register | |
248 | .II n, | |
249 | then add in the temporary. | |
250 | .PP | |
251 | The distinction between cases 2 and 3 therefore depends | |
252 | on whether the right operand can be compiled in fewer than | |
253 | .II k | |
254 | registers, where | |
255 | .II k | |
256 | is the number of free registers left after registers 0 through | |
257 | .II n | |
258 | are taken: | |
259 | 0 through | |
260 | .II n\-1 | |
261 | are presumed to contain already computed temporary results; | |
262 | .II n | |
263 | will, in case 2, | |
264 | contain the value of the left operand while the right | |
265 | is being evaluated. | |
266 | .PP | |
267 | These considerations should make clear | |
268 | the specification codes for the degree of difficulty, | |
269 | bearing in mind that a number of special cases are also present: | |
270 | .IP z | |
271 | is satisfied when the operand is zero, so that special code | |
272 | can be produced for expressions like `x = 0'. | |
273 | .RT | |
274 | .IP 1 | |
275 | is satisfied when the operand is the constant 1, to optimize | |
276 | cases like left and right shift by 1, which can be done | |
277 | efficiently on the PDP-11. | |
278 | .RT | |
279 | .IP c | |
280 | is satisfied when the operand is a positive (16-bit) | |
281 | constant; this takes care of some special cases in long arithmetic. | |
282 | .RT | |
283 | .IP a | |
284 | is satisfied when the operand is addressible; | |
285 | this occurs not only for variables and constants, but also for | |
286 | some more complicated constructions, such as indirection through | |
287 | a simple variable, `*p++' where | |
288 | .II p | |
289 | is a register variable (because of the PDP-11's auto-increment address | |
290 | mode), and `*(p+c)' where | |
291 | .II p | |
292 | is a register and | |
293 | .II c | |
294 | is a constant. | |
295 | Precisely, the requirement is that the operand refers to a cell | |
296 | whose address can be written as a source or destination of a PDP-11 | |
297 | instruction. | |
298 | .RT | |
299 | .IP e | |
300 | is satisfied by an operand whose value can be generated in a register | |
301 | using no more than | |
302 | .II k | |
303 | registers, where | |
304 | .II k | |
305 | is the number of registers left (not counting the current register). | |
306 | The `e' stands for `easy.' | |
307 | .RT | |
308 | .IP n | |
309 | is satisfied by any operand. | |
310 | The `n' stands for `anything.' | |
311 | .PP | |
312 | These degrees of difficulty are considered to lie in a linear ordering | |
313 | and any operand which satisfies an earlier-mentioned requirement | |
314 | will satisfy a later one. | |
315 | Since the subtables are searched linearly, | |
316 | if a `1' specification is included, almost certainly | |
317 | a `z' must be written first to prevent | |
318 | expressions containing the constant 0 to be compiled | |
319 | as if the 0 were 1. | |
320 | .PP | |
321 | Finally, | |
322 | a key specification may contain a `*' which | |
323 | requires the operand to have an indirection as its leading operator. | |
324 | Examples below should clarify the utility of this specification. | |
325 | .PP | |
326 | Now let us consider the contents of the code string | |
327 | associated with each subtable entry. | |
328 | Conventionally, lower-case letters in this string | |
329 | represent literal information which is copied directly | |
330 | to the output. | |
331 | Upper-case letters generally introduce specific | |
332 | macro-operations, some of which may be followed | |
333 | by modifying information. | |
334 | The code strings in the tables are written with tabs and | |
335 | new-lines used freely to suggest instructions which will be generated; | |
336 | the table-compiling program compresses tabs (using the 0200 bit of the | |
337 | next character) and throws away some of the new-lines. | |
338 | For example the macro `F' is ordinarily written on a line by itself; | |
339 | but since its expansion will end with a new-line, the new-line | |
340 | after `F' itself is dispensable. | |
341 | This is all to reduce the size of the stored tables. | |
342 | .PP | |
343 | The first set of macro-operations is concerned with | |
344 | compiling subtrees. | |
345 | Recall that this is done by the | |
346 | .II cexpr | |
347 | routine. | |
348 | In the following discussion the `current register' | |
349 | is generally the argument register to | |
350 | .II cexpr; | |
351 | that is, the place where the result is desired. | |
352 | The `next register' is numbered one | |
353 | higher | |
354 | than the current register. | |
355 | (This explanation isn't fully true | |
356 | because of complications, described below, involving | |
357 | operations which require even-odd register pairs.) | |
358 | .IP F | |
359 | causes a recursive call to | |
360 | the | |
361 | .II rcexpr | |
362 | routine to compile code which places the value of the first (left) | |
363 | operand of the operator in the current register. | |
364 | .RT | |
365 | .IP F1 | |
366 | generates code which places the value of the first operand in the | |
367 | next register. | |
368 | It is incorrectly used if there might be no next register; | |
369 | that is, if the degree of difficulty of the first operand is not `easy;' | |
370 | if not, another register might not be available. | |
371 | .RT | |
372 | .IP FS | |
373 | generates code which pushes the value of the first operand on the stack, | |
374 | by calling | |
375 | .II rcexpr | |
376 | specifying | |
377 | .II sptab | |
378 | as the table. | |
379 | .LP | |
380 | Analogously, | |
381 | .IP "S, S1, SS" | |
382 | compile the second (right) operand | |
383 | into the current register, the next register, or onto the stack. | |
384 | .LP | |
385 | To deal with registers, there are | |
386 | .IP R | |
387 | which expands into the name of the current register. | |
388 | .RT | |
389 | .IP R1 | |
390 | which expands into the name of the next register. | |
391 | .RT | |
392 | .IP R+ | |
393 | which expands into the the name of the current register plus 1. | |
394 | It was suggested above that this is the same as the next register, | |
395 | except for complications; here is one of them. | |
396 | Long integer variables have | |
397 | 32 bits and require 2 registers; in such cases the next register | |
398 | is the current register plus 2. | |
399 | The code would like to talk about both halves of the | |
400 | long quantity, so R refers to the register with the high-order part | |
401 | and R+ to the low-order part. | |
402 | .RT | |
403 | .IP R\- | |
404 | This is another complication, involving division and mod. | |
405 | These operations involve a pair of registers of which the odd-numbered | |
406 | contains the left operand. | |
407 | .II Cexpr | |
408 | arranges that the current register is odd; | |
409 | the R\- notation allows the code to refer to the next lower, | |
410 | even-numbered register. | |
411 | .LP | |
412 | To refer to addressible quantities, there are the notations: | |
413 | .IP A1 | |
414 | causes generation of the address specified by the first operand. | |
415 | For this to be legal, the operand must be addressible; its | |
416 | key must contain an `a' | |
417 | or a more restrictive specification. | |
418 | .RT | |
419 | .IP A2 | |
420 | correspondingly generates the address of the second operand | |
421 | providing it has one. | |
422 | .PP | |
423 | We now have enough mechanism to show a complete, if suboptimal, | |
424 | table for the + operator on word or byte operands. | |
425 | .DS | |
426 | %n,z | |
427 | F | |
428 | .sp 1 | |
429 | %n,1 | |
430 | F | |
431 | inc R | |
432 | .sp 1 | |
433 | %n,aw | |
434 | F | |
435 | add A2,R | |
436 | .sp 1 | |
437 | %n,e | |
438 | F | |
439 | S1 | |
440 | add R1,R | |
441 | .sp 1 | |
442 | %n,n | |
443 | SS | |
444 | F | |
445 | add (sp)+,R | |
446 | .DE | |
447 | The first two sequences handle some special cases. | |
448 | Actually it turns out that handling a right operand of 0 | |
449 | is unnecessary since the expression-optimizer | |
450 | throws out adds of 0. | |
451 | Adding 1 by using the `increment' instruction is done next, | |
452 | and then the case where the right operand is addressible. | |
453 | It must be a word quantity, since the PDP-11 lacks an `add byte' instruction. | |
454 | Finally the cases where the right operand either can, or cannot, | |
455 | be done in the available registers are treated. | |
456 | .PP | |
457 | The next macro-instructions are conveniently | |
458 | introduced by noticing that the above table is suitable | |
459 | for subtraction as well as addition, since no use is made of the | |
460 | commutativity of addition. | |
461 | All that is needed is substitution of `sub' for `add' | |
462 | and `dec' for 'inc.' | |
463 | Considerable saving of space is achieved by factoring out | |
464 | several similar operations. | |
465 | .IP I | |
466 | is replaced by a string from another table indexed by the operator | |
467 | in the node being expanded. | |
468 | This secondary table actually contains two strings per operator. | |
469 | .RT | |
470 | .IP I\(fm | |
471 | is replaced by the second string in the side table | |
472 | entry for the current operator. | |
473 | .PP | |
474 | Thus, given that the entries for `+' and `\-' in the side table | |
475 | (which is called | |
476 | .II instab) | |
477 | are `add' and `inc,' `sub' and `dec' | |
478 | respectively, | |
479 | the middle of of the above addition table can be written | |
480 | .DS | |
481 | %n,1 | |
482 | F | |
483 | I' R | |
484 | ||
485 | %n,aw | |
486 | F | |
487 | I A2,R | |
488 | .DE | |
489 | and it will be suitable for subtraction, | |
490 | and several other operators, as well. | |
491 | .PP | |
492 | Next, there is the question of character and floating-point operations. | |
493 | .IP B1 | |
494 | generates the letter `b' if the first operand is a character, | |
495 | `f' if it is float or double, and nothing otherwise. | |
496 | It is used in a context like `movB1' | |
497 | which generates a `mov', `movb', or `movf' | |
498 | instruction according to the type of the operand. | |
499 | .RT | |
500 | .IP B2 | |
501 | is just like B1 but applies to the second operand. | |
502 | .RT | |
503 | .IP BE | |
504 | generates `b' if either operand is a character | |
505 | and null otherwise. | |
506 | .RT | |
507 | .IP BF | |
508 | generates `f' if the type of the operator node itself is float or double, | |
509 | otherwise null. | |
510 | .PP | |
511 | For example, there is an entry in | |
512 | .II efftab | |
513 | for the `=' operator | |
514 | .DS | |
515 | %a,aw | |
516 | %ab,a | |
517 | IBE A2,A1 | |
518 | .DE | |
519 | Note first that two key specifications | |
520 | can be applied to the same code string. | |
521 | Next, observe that when a word is assigned to a byte or to a word, | |
522 | or a word is assigned to a byte, | |
523 | a single instruction, | |
524 | a | |
525 | .II mov | |
526 | or | |
527 | .II movb | |
528 | as appropriate, does the job. | |
529 | However, when a byte is assigned to a word, | |
530 | it must pass through a register to implement the sign-extension rules: | |
531 | .DS | |
532 | %a,n | |
533 | S | |
534 | IB1 R,A1 | |
535 | .DE | |
536 | .PP | |
537 | Next, there is the question of handling indirection properly. | |
538 | Consider the expression `X + *Y', where X and Y are expressions, | |
539 | Assuming that Y is more complicated than just a variable, | |
540 | but on the other hand qualifies as `easy' in the context, | |
541 | the expression would be compiled by placing the value of X in a register, | |
542 | that of *Y in the next register, and adding the registers. | |
543 | It is easy to see that a better job can be done | |
544 | by compiling X, then Y (into the next register), | |
545 | and producing the | |
546 | instruction symbolized by `add (R1),R'. | |
547 | This scheme avoids generating | |
548 | the instruction `mov (R1),R1' | |
549 | required actually to place the value of *Y in a register. | |
550 | A related situation occurs | |
551 | with the expression `X + *(p+6)', which | |
552 | exemplifies a construction | |
553 | frequent in structure and array references. | |
554 | The addition table shown above would produce | |
555 | .DS | |
556 | [put X in register R] | |
557 | mov p,R1 | |
558 | add $6,R1 | |
559 | mov (R1),R1 | |
560 | add R1,R | |
561 | .DE | |
562 | when the best code is | |
563 | .DS | |
564 | [put X in R] | |
565 | mov p,R1 | |
566 | add 6(R1),R | |
567 | .DE | |
568 | As we said above, a key specification for a code table entry | |
569 | may require an operand to have an indirection as its highest operator. | |
570 | To make use of the requirement, | |
571 | the following macros are provided. | |
572 | .IP F* | |
573 | the first operand must have the form *X. | |
574 | If in particular it has the form *(Y + c), for some constant | |
575 | .II c, | |
576 | then code is produced which places the value of Y in | |
577 | the current register. | |
578 | Otherwise, code is produced which loads X into the current register. | |
579 | .RT | |
580 | .IP F1* | |
581 | resembles F* except that the next register is loaded. | |
582 | .RT | |
583 | .IP S* | |
584 | resembles F* except that the second operand is loaded. | |
585 | .RT | |
586 | .IP S1* | |
587 | resembles S* except that the next register is loaded. | |
588 | .RT | |
589 | .IP FS* | |
590 | The first operand must have the form `*X'. | |
591 | Push the value of X on the stack. | |
592 | .RT | |
593 | .IP SS* | |
594 | resembles FS* except that it applies to the second operand. | |
595 | .LP | |
596 | To capture the constant that may have been skipped over | |
597 | in the above macros, there are | |
598 | .IP #1 | |
599 | The first operand must have the form *X; | |
600 | if in particular it has the form *(Y + c) for | |
601 | .II c | |
602 | a constant, then the constant is written out, | |
603 | otherwise a null string. | |
604 | .RT | |
605 | .IP #2 | |
606 | is the same as #1 except that the second operand is used. | |
607 | .LP | |
608 | Now we can improve the addition table above. | |
609 | Just before the `%n,e' entry, put | |
610 | .DS | |
611 | %n,ew* | |
612 | F | |
613 | S1* | |
614 | add #2(R1),R | |
615 | .DE | |
616 | and just before the `%n,n' put | |
617 | .DS | |
618 | %n,nw* | |
619 | SS* | |
620 | F | |
621 | add *(sp)+,R | |
622 | .DE | |
623 | When using the stacking macros there is no place to use | |
624 | the constant | |
625 | as an index word, so that particular special case doesn't occur. | |
626 | .PP | |
627 | The constant mentioned above can actually be more | |
628 | general than a number. | |
629 | Any quantity acceptable to the assembler as an expression will do, | |
630 | in particular the address of a static cell, perhaps with a numeric offset. | |
631 | If | |
632 | .II x | |
633 | is an external character array, | |
634 | the expression `x[i+5] = 0' will generate | |
635 | the code | |
636 | .DS | |
637 | mov i,r0 | |
638 | clrb x+5(r0) | |
639 | .DE | |
640 | via the table entry (in the `=' part of | |
641 | .II efftab) | |
642 | .DS | |
643 | %e*,z | |
644 | F | |
645 | I'B1 #1(R) | |
646 | .DE | |
647 | Some machine operations place restrictions on the registers | |
648 | used. | |
649 | The divide instruction, used to implement the divide and mod | |
650 | operations, requires the dividend to be placed in the odd member | |
651 | of an even-odd pair; | |
652 | other peculiarities | |
653 | of multiplication make it simplest to put the multiplicand | |
654 | in an odd-numbered register. | |
655 | There is no theory which optimally accounts for | |
656 | this kind of requirement. | |
657 | .II Cexpr | |
658 | handles it by checking for a multiply, divide, or mod operation; | |
659 | in these cases, its argument register number is incremented by | |
660 | one or two so that it is odd, and if the operation was divide or mod, | |
661 | so that it is a member of a free even-odd pair. | |
662 | The routine which determines the number of registers required | |
663 | estimates, conservatively, that | |
664 | at least two registers are required for a multiplication | |
665 | and three for the other peculiar operators. | |
666 | After the expression is compiled, | |
667 | the register where the result actually ended up is returned. | |
668 | (Divide and mod are actually the same operation except for the | |
669 | location of the result). | |
670 | .PP | |
671 | These operations are the ones which cause results to end up in | |
672 | unexpected places, | |
673 | and this possibility adds a further level of complexity. | |
674 | The simplest way of handling the problem is always to move the | |
675 | result to the place where the caller expected it, | |
676 | but this will produce unnecessary register moves in many | |
677 | simple cases; `a = b*c' would generate | |
678 | .DS | |
679 | mov b,r1 | |
680 | mul c,r1 | |
681 | mov r1,r0 | |
682 | mov r0,a | |
683 | .DE | |
684 | The next thought is used the passed-back | |
685 | information as to where the result landed to change the notion of the current | |
686 | register. | |
687 | While compiling the `=' operation above, which comes from a | |
688 | table | |
689 | entry | |
690 | like | |
691 | .DS | |
692 | %a,e | |
693 | S | |
694 | mov R,A1 | |
695 | .DE | |
696 | it is sufficient to redefine the meaning of `R' | |
697 | after processing the `S' which does the multiply. | |
698 | This technique is in fact used; the tables are written in such a way | |
699 | that correct code is produced. | |
700 | The trouble is that the technique cannot be used in general, | |
701 | because it invalidates the count of the number of registers | |
702 | required for an expression. | |
703 | Consider just `a*b + X' where X is some expression. | |
704 | The algorithm assumes that the value of a*b, | |
705 | once computed, requires just one register. | |
706 | If there are three registers available, and X requires two registers to | |
707 | compute, then this expression will match a key specifying | |
708 | `%n,e'. | |
709 | If a*b is computed and left in register 1, then there are, contrary | |
710 | to expectations, no longer two registers available to compute X, | |
711 | but only one, and bad code will be produced. | |
712 | To guard against this possibility, | |
713 | .II cexpr | |
714 | checks the result returned by recursive calls which implement | |
715 | F, S and their relatives. | |
716 | If the result is not in the expected register, then the number of | |
717 | registers required by the other operand is checked; | |
718 | if it can be done using those registers which remain even | |
719 | after making unavailable the unexpectedly-occupied | |
720 | register, then | |
721 | the notions of the `next register' and possibly the `current | |
722 | register' are redefined. | |
723 | Otherwise a register-copy instruction is produced. | |
724 | A register-copy is also always produced | |
725 | when the current operator is one of those which have odd-even requirements. | |
726 | .PP | |
727 | Finally, there are a few loose-end macro operations | |
728 | and facts about the tables. | |
729 | The operators: | |
730 | .IP V | |
731 | is used for long operations. | |
732 | It is written with an address like a machine instruction; | |
733 | it expands into `adc' (add carry) if the operation | |
734 | is an additive operator, | |
735 | `sbc' (subtract carry) if the operation is a subtractive | |
736 | operator, and disappears, along with the rest of the line, otherwise. | |
737 | Its purpose is to allow common treatment of logical | |
738 | operations, which have no carries, and additive and subtractive | |
739 | operations, which generate carries. | |
740 | .RT | |
741 | .IP T | |
742 | generates a `tst' instruction if the first operand | |
743 | of the tree does not set the condition codes correctly. | |
744 | It is used with divide and mod operations, | |
745 | which require a sign-extended 32-bit operand. | |
746 | The code table for the operations contains an `sxt' | |
747 | (sign-extend) instruction to generate the high-order part of the | |
748 | dividend. | |
749 | .RT | |
750 | .IP H | |
751 | is analogous to the `F' and `S' macros, | |
752 | except that it calls for the generation of code for | |
753 | the current tree | |
754 | (not one of its operands) | |
755 | using | |
756 | .II regtab. | |
757 | It is used in | |
758 | .II cctab | |
759 | for all the operators which, when executed normally, | |
760 | set the condition codes properly according to the result. | |
761 | It prevents a `tst' instruction from being generated for | |
762 | constructions like `if (a+b) ...' | |
763 | since after calculation of the value of | |
764 | `a+b' a conditional branch can be written immediately. | |
765 | .PP | |
766 | All of the discussion above is in terms of operators with operands. | |
767 | Leaves of the expression tree (variables and constants), however, | |
768 | are peculiar in that they have no operands. | |
769 | In order to regularize the matching process, | |
770 | .II cexpr | |
771 | examines its operand to determine if it is a leaf; | |
772 | if so, it creates a special `load' operator whose operand | |
773 | is the leaf, and substitutes it for the argument tree; | |
774 | this allows the table entry for the created operator | |
775 | to use the `A1' notation to load the leaf into a register. | |
776 | .PP | |
777 | Purely to save space in the tables, | |
778 | pieces of subtables can be labelled and referred to later. | |
779 | It turns out, for example, | |
780 | that rather large portions of the | |
781 | the | |
782 | .II efftab | |
783 | table for the `=' and `=+' operators are identical. | |
784 | Thus `=' has an entry | |
785 | .DS | |
786 | %[move3:] | |
787 | %a,aw | |
788 | %ab,a | |
789 | IBE A2,A1 | |
790 | .DE | |
791 | while part of the `=+' table is | |
792 | .DS | |
793 | %aw,aw | |
794 | % [move3] | |
795 | .DE | |
796 | Labels are written as `%[ ... : ]', | |
797 | before the key specifications; | |
798 | references | |
799 | are written | |
800 | with `% [ ... ]' | |
801 | after the key. | |
802 | Peculiarities in the implementation | |
803 | make it necessary that labels appear before references to them. | |
804 | .PP | |
805 | The example illustrates the utility | |
806 | of allowing separate keys | |
807 | to point to the same code string. | |
808 | The assignment code | |
809 | works properly if either the right operand is a word, or the left operand | |
810 | is a byte; | |
811 | but since there is no `add byte' instruction the addition code | |
812 | has to be restricted to word operands. |