| 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. |