top.n 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869
  1. .ND
  2. .tr ~
  3. .ds <.
  4. .ds <,
  5. .ds >. .
  6. .ds >, ,
  7. .ds [. [
  8. .ds .] ]
  9. .TL
  10. The ACK Target Optimizer
  11. .AU
  12. H.E. Bal
  13. .AI
  14. Vrije Universiteit
  15. Wiskundig Seminarium, Amsterdam
  16. .AB
  17. The Target Optimizer is one of several optimizers that are part of
  18. the Amsterdam Compiler Kit.
  19. It operates directly on assembly code,
  20. rather than on a higher level intermediate code,
  21. as the Peephole Optimizer and Global Optimizer do.
  22. Consequently, the Target Optimizer can do optimizations
  23. that are highly machine-dependent.
  24. .PP
  25. Each target machine has its own Target Optimizer.
  26. New optimizers are generated by the Target Optimizer Generator,
  27. which uses a machine-dependent table as input.
  28. This document contains full information on how to
  29. write such a table for a new machine.
  30. It also discusses the implementation of the
  31. Target Optimizer and its generator.
  32. .AE
  33. .NH 1
  34. Introduction
  35. .PP
  36. .FS
  37. This work was supported by the
  38. Stichting Technische Wetenschappen (STW)
  39. under grant VWI03.0001.
  40. .FE
  41. This document describes the target optimizer component
  42. of the Amsterdam Compiler Kit (ACK) .
  43. .[
  44. tanenbaum staveren amsterdam toolkit
  45. .]
  46. .[
  47. tanenbaum staveren cacm
  48. .]
  49. .[
  50. tanenbaum staveren toronto
  51. .]
  52. Optimization takes place in several parts of ACK compilers,
  53. most notably in the Peephole Optimizer
  54. .[
  55. staveren peephole toplas
  56. .]
  57. and
  58. the Global Optimizer,
  59. .[
  60. bal tanenbaum global optimization
  61. .]
  62. .[
  63. bal implementation global optimizer
  64. .]
  65. which are both language- and machine-independent,
  66. and in the machine-specific code generators.
  67. .[
  68. documentation amsterdam compiler kit
  69. .]
  70. The target optimizer is the finishing touch in this sequence of
  71. optimizers.
  72. It can be used to capture those optimizations that are hard
  73. to express in the other parts of ACK.
  74. These optimizations will typically be very machine-specific.
  75. .PP
  76. The target optimizer operates on the assembly code of some target machine.
  77. Hence there is one target optimizer per machine.
  78. However, just as for the ACK code generators and assemblers,
  79. a framework has been build that allows easy generation of
  80. target optimizers out of machine-independent parts and a
  81. machine-dependent description table (see figure 1.).
  82. So the major part of the code of a target optimizer is
  83. shared among all target optimizers.
  84. .DS
  85. .ft CW
  86. |-------------------------|
  87. | machine-independent |
  88. | code |
  89. | |
  90. |-----------------| |-------------------------|
  91. descrip- |target optimizer | | machine-dependent code |
  92. tion --> |generator | ----> | + tables |
  93. table | | | |
  94. |-----------------| |-------------------------|
  95. target optimizer
  96. .ft R
  97. Figure 1: Generation of a target optimizer.
  98. .DE
  99. .PP
  100. This document focusses on the description of the machine-dependent table.
  101. In chapter 2 we give an informal introduction to the optimization
  102. algorithm and to the definition of the table format.
  103. Chapters 3 and 4 discuss the implementation of the target optimizer
  104. and the target optimizer generator.
  105. Appendix A gives full information for writing a description table.
  106. .NH 1
  107. Global structure of the target optimizer
  108. .PP
  109. The target optimizer is based on the well understood model
  110. of a \fIpeephole optimizer\fR.
  111. .[
  112. aho ullman compiler
  113. .]
  114. It contains a machine-dependent table
  115. of (pattern,replacement) pairs.
  116. Each pattern describes
  117. a sequence of one or more assembler instructions
  118. that can be replaced by zero or more equivalent, yet cheaper,
  119. instructions (the 'replacement').
  120. The optimizer maintains a \fIwindow\fR that moves over the input.
  121. At any moment, the window contains some contiguous part of the input.
  122. If the instructions in the current window match some pattern
  123. in the table,
  124. they are replaced by the corresponding replacement;
  125. else, the window moves one instruction to the right.
  126. .PP
  127. In the remainder of this section we will give an informal
  128. description of the machine-dependent table.
  129. A more precise definition is given in appendix A.
  130. We will first discuss the restrictions put on the
  131. format of the assembly code.
  132. .NH 2
  133. Assumptions about the assembly code format
  134. .PP
  135. We assume that a line of assembly code begins with an
  136. instruction \fImnemonic\fR (opcode),
  137. followed by zero or more \fIoperands\fR.
  138. The mnemonic and the first operand must be separated by a special
  139. character (e.g. a space or a tab).
  140. Likewise, the operands must be separated by a special
  141. character (e.g. a comma).
  142. These separators need not be the same for all machines.
  143. .NH 2
  144. Informal description of the machine-dependent tables
  145. .PP
  146. The major part of the table consists of (pattern,replacement) pairs
  147. called \fIentries\fR.
  148. .PP
  149. A pattern is a list of instruction descriptions.
  150. Each instruction description describes the instruction mnemonic and
  151. the operands.
  152. .PP
  153. A mnemonic is described either by a string constant or by the
  154. keyword ANY.
  155. As all entities dealt with by the target optimizer are strings,
  156. string constants do not contain quotes.
  157. A string constant matches only itself.
  158. ANY matches every instruction mnemonic.
  159. .nf
  160. Examples of mnemonic descriptions:
  161. .ft CW
  162. add
  163. sub.l
  164. mulw3
  165. ANY
  166. .ft R
  167. .fi
  168. .PP
  169. An operand can also be described by a string constant.
  170. .nf
  171. Examples:
  172. .ft CW
  173. (sp)+
  174. r5
  175. -4(r6)
  176. .ft R
  177. .fi
  178. Alternatively, it can be described by means of a \fIvariable name\fR.
  179. Variables have values which are strings.
  180. They have to be declared in the table before the patterns.
  181. Each such declaration defines the name of a variable and
  182. a \fIrestriction\fR to which its value is subjected.
  183. .nf
  184. Example of variable declarations:
  185. .ft CW
  186. CONST { VAL[0] == '$' };
  187. REG { VAL[0] == 'r' && VAL[1] >= '0' && VAL[1] <= '3' &&
  188. VAL[2] == '\\0' };
  189. X { TRUE };
  190. .ft R
  191. .fi
  192. The keyword VAL denotes the value of the variable, which is
  193. a null-terminated string.
  194. An operand description given via a variable name matches an
  195. actual operand if the actual operand obeys the associated restriction.
  196. .nf
  197. .ft CW
  198. CONST matches $1, $-5, $foo etc.
  199. REG matches r0, r1, r2 and r3
  200. X matches anything
  201. .ft R
  202. .fi
  203. The restriction (between curly braces) may be any legal "C"
  204. .[
  205. kernighan ritchie c programming
  206. .]
  207. expression.
  208. It may also contain calls to user-defined procedures.
  209. These procedures must be added to the table after the patterns.
  210. .nf
  211. Example:
  212. .ft CW
  213. FERMAT_NUMBER { VAL[0] == '$' && is_fermat_number(&VAL[1]) };
  214. .ft R
  215. .fi
  216. An operand can also be described by a mixture of a string constant
  217. and a variable name.
  218. The most general form allowed is:
  219. .nf
  220. string_constant1 variable_name string_constant2
  221. Example:
  222. .ft CW
  223. (REG)+ matches (r0)+, (r1)+, (r2)+ and (r3)+
  224. .ft R
  225. .fi
  226. Any of the three components may be omitted,
  227. so the first two forms are just special cases of the general form.
  228. The name of a variable can not be used as a string constant.
  229. In the above context, it is impossible to define an operand that
  230. matches the string "REG".
  231. This limitation is of little consequence,
  232. as the table writer is free to choose the names of variables.
  233. This approach, however, avoids the need for awkward escape sequences.
  234. .PP
  235. A pattern consists of one or more instruction descriptions
  236. (separated by a colon)
  237. followed by an optional constraint.
  238. A pattern "P1 : P2 : .. : Pn C" matches the sequence of
  239. instructions "I1 I2 .. In" if:
  240. .IP (i) 7
  241. for each i, 1 <= i <= n, Pi matches Ii, as described above;
  242. .IP (ii)
  243. multiple occurrences of the same variable name or of
  244. the keyword ANY stand for the same values throughout the pattern;
  245. .IP (iii)
  246. the optional constraint C is satisfied, i.e. it evaluates to TRUE.
  247. .LP
  248. .nf
  249. The pattern:
  250. .ft CW
  251. dec REG : move.b CONST,(REG)
  252. .ft R
  253. matches:
  254. .ft CW
  255. dec r0 : move.b $4,(r0)
  256. .ft R
  257. but not:
  258. .ft CW
  259. dec r0 : move.b $4,(r1)
  260. .ft R
  261. (as the variable REG matches two different strings).
  262. .fi
  263. If a pattern containing different registers must be described,
  264. extra names for a register should be declared, all sharing
  265. the same restriction.
  266. .nf
  267. Example:
  268. .ft CW
  269. REG1,REG2 { VAL[0] == 'r' && ..... };
  270. addl3 REG1,REG1,REG2 : subl2 REG2,REG1
  271. .ft R
  272. .fi
  273. .PP
  274. The optional constraint is an auxiliary "C" expression (just like
  275. the parameter restrictions).
  276. The expression may refer to the variables and to ANY.
  277. .nf
  278. Example:
  279. .ft CW
  280. move REG1,REG2 { REG1[1] == REG2[1] + 1 }
  281. .ft R
  282. matches
  283. .ft CW
  284. move r1,r0
  285. move r2,r1
  286. move r3,r2
  287. .ft R
  288. .fi
  289. .PP
  290. The replacement part of a (pattern,replacement) table entry
  291. has the same structure as a pattern, except that:
  292. .IP (i)
  293. it may not contain an additional constraint;
  294. .IP (ii)
  295. it may be empty.
  296. .LP
  297. A replacement may also refer to the values of variables and ANY.
  298. .NH 2
  299. Examples
  300. .PP
  301. This section contains some realistic examples for
  302. optimization on PDP-11 and Vax assembly code.
  303. .NH 3
  304. Vax examples
  305. .PP
  306. Suppose the table contains the following declarations:
  307. .nf
  308. .ft CW
  309. X, LOG { TRUE };
  310. LAB { VAL[0] == 'L' }; /* e.g. L0017 */
  311. A { no_side_effects(VAL) };
  312. NUM { is_number(VAL) };
  313. .ft R
  314. .fi
  315. The procedure "no_side_effects" checks if its argument
  316. contains any side effects, i.e. auto increment or auto decrement.
  317. The procedure "is_number" checks if its argument contains only digits.
  318. These procedures must be supplied by the table-writer and must be
  319. included in the table.
  320. .PP
  321. .nf
  322. .ft CW
  323. \fIentry:\fP addl3 X,A,A -> addl2 X,A;
  324. .ft R
  325. .fi
  326. This entry changes a 3-operand instruction into a cheaper 2-operand
  327. instruction.
  328. An optimization like:
  329. .nf
  330. .ft CW
  331. addl3 r0,(r2)+,(r2)+ -> addl2 r0,(r2)+
  332. .ft R
  333. .fi
  334. is illegal, as r2 should be incremented twice.
  335. Hence the second argument is required to
  336. be side-effect free.
  337. .PP
  338. .nf
  339. .ft CW
  340. \fIentry:\fP addw2 $-NUM,X -> subw2 $NUM,X;
  341. .ft R
  342. .fi
  343. An instruction like "subw2 $5,r0" is cheaper
  344. than "addw2 $-5,r0",
  345. because constants in the range 0 to 63 are represented
  346. very efficiently on the Vax.
  347. .PP
  348. .nf
  349. .ft CW
  350. \fIentry:\fP bitw $NUM,A : jneq LAB
  351. { is_poweroftwo(NUM,LOG) } -> jbs $LOG,A,LAB;
  352. .ft R
  353. .fi
  354. A "bitw x,y" sets the condition codes to the bitwise "and" of
  355. x and y.
  356. A "jbs n,x,l" branches to l if bit n of x is set.
  357. So, for example, the following transformation is possible:
  358. .nf
  359. .ft CW
  360. bitw $32,r0 : jneq L0017 -> jbs $5,r0,L0017
  361. .ft R
  362. .fi
  363. The user-defined procedure "is_poweroftwo" checks if its first argument is
  364. a power of 2 and, if so, sets its second argument to the logarithm
  365. of the first argument. (Both arguments are strings).
  366. Note that the variable LOG is not used in the pattern itself.
  367. It is assigned a (string) value by "is_poweroftwo" and is used
  368. in the replacement.
  369. .NH 3
  370. PDP-11 examples
  371. .PP
  372. Suppose we have the following declarations:
  373. .nf
  374. .ft CW
  375. X { TRUE };
  376. A { no_side_effects(VAL) };
  377. L1, L2 { VAL[0] == 'I' };
  378. REG { VAL[0] == 'r' && VAL[1] >= '0' && VAL[1] <= '5' &&
  379. VAL[2] == '\\0' };
  380. .ft P
  381. .fi
  382. The implementation of "no_side_effects" may of course
  383. differ for the PDP-11 and the Vax.
  384. .PP
  385. .nf
  386. .ft CW
  387. \fIentry:\fP mov REG,A : ANY A,X -> mov REG,A : ANY REG,X ;
  388. .ft R
  389. .fi
  390. This entry implements register subsumption.
  391. If A and REG hold the same value (which is true after "mov REG,A")
  392. and A is used as source (first) operand, it is cheaper to use REG instead.
  393. .PP
  394. .nf
  395. .ft CW
  396. \fIentry:\fP jeq L1 : jbr L2 : labdef L1 -> jne L2 : labdef L1;
  397. .ft R
  398. .fi
  399. The "jeq L1" is a "skip over an unconditional jump". "labdef L1"
  400. denotes the definition (i.e. defining occurrence) of label L1.
  401. As the target optimizer has to know how such a definition
  402. looks like, this must be expressed in the table (see Appendix A).
  403. .PP
  404. .nf
  405. .ft CW
  406. \fIentry:\fP add $01,X { carry_dead(REST) } -> inc X;
  407. .ft R
  408. .fi
  409. On the PDP-11, an add-one is not equivalent to an increment.
  410. The latter does not set the carry-bit of the condition codes,
  411. while the former does.
  412. So a look-ahead is needed to see if the rest of the input uses
  413. the carry-bit before changing the condition codes.
  414. A look-ahead of one instruction is provided by
  415. the target optimizer.
  416. This will normally be sufficient for compiler-generated code.
  417. The keyword REST contains the mnemonic of the first instruction of
  418. the rest of the input.
  419. If this instruction uses the carry-bit (e.g. an adc, subc, bhis)
  420. the transformation is not allowed.
  421. .NH 1
  422. Implementation of the target optimizer
  423. .PP
  424. The target optimizer reads one input file of assembler instructions,
  425. processes it, and writes the optimized code
  426. to the output file.
  427. So it performs one pass over the input.
  428. .NH 2
  429. The window mechanism
  430. .PP
  431. The optimizer uses a \fIwindow\fR that moves over the input.
  432. It repeatedly tries to match the instructions in the window
  433. with the patterns in the table.
  434. If no match is possible, the window moves
  435. one instruction forwards (to the right).
  436. After a successful match the matched instructions are
  437. removed from the window and are replaced by the
  438. replacement part of the table entry.
  439. Furthermore, the window is moved a few instructions
  440. backwards,
  441. as it is possible that instructions that were rejected earlier now do match.
  442. For example, consider the following patterns:
  443. .DS
  444. .ft CW
  445. cmp $0, X -> tst X ;
  446. mov REG,X : tst X -> move REG.X ; /* redundant test */
  447. .ft R
  448. .DE
  449. If the input is:
  450. .DS
  451. .ft CW
  452. mov r0,foo : cmp $0,foo
  453. .ft R
  454. .DE
  455. then the first instruction is initially rejected.
  456. However, after the transformation
  457. .DS
  458. .ft CW
  459. cmp $0,foo -> tst foo
  460. .ft R
  461. .DE
  462. the following optimization is possible:
  463. .DS
  464. .ft CW
  465. mov r0,foo : tst foo -> mov r0,foo
  466. .ft R
  467. .DE
  468. .PP
  469. The window is implemented as a \fIqueue\fR.
  470. Matching takes place at the head of the queue.
  471. New instructions are added at the tail.
  472. If the window is moved forwards, the instruction at the head
  473. is not yet written to the output,
  474. as it may be needed later on.
  475. Instead it is added to a second queue,
  476. the \fIbackup queue\fR.
  477. After a successful match, the entire backup queue is
  478. inserted at the front of the window queue,
  479. which effectively implements the shift backwards.
  480. .PP
  481. Both queues have the length of the longest pattern in the table.
  482. If, as a result of a forward window move,
  483. the backup queue gets full,
  484. the instruction at its head is outputted and removed.
  485. Instructions are read from the input whenever the
  486. window queue contains fewer elements than the length
  487. of the longest pattern.
  488. .NH 2
  489. Pattern matching
  490. .PP
  491. Pattern matching is done in three steps:
  492. .IP (i) 7
  493. find patterns in the table whose instruction mnemonics
  494. match the mnemonics of the instructions in the
  495. current window;
  496. .IP (ii)
  497. check if the operands of the pattern match the operands of the
  498. instructions in the current window;
  499. .IP (iii)
  500. check if the optional constraint is satisfied.
  501. .LP
  502. For step (i) hashing is used.
  503. The mnemonic of the first instruction of the window
  504. is used to determine a list of possible patterns.
  505. Patterns starting with ANY are always tried.
  506. .PP
  507. Matching of operand descriptions against actual operands
  508. takes place as follows.
  509. The general form of an operand description is:
  510. .DS
  511. string_constant1 variable_name string_constant2
  512. .DE
  513. The actual operand should begin with string_constant1 and end
  514. on string_constant2.
  515. If so, these strings are stripped from it and the remaining string is
  516. matched against the variable.
  517. Matching a string against a variable is
  518. defined as follows:
  519. .IP 1.
  520. initially (before the entire pattern match)
  521. all variables are uninstantiated;
  522. .IP 2.
  523. matching a string against an uninstantiated variable
  524. succeeds if the restriction associated with the variable is
  525. satisfied.
  526. As a side effect, it causes the variable to be instantiated to
  527. the string;
  528. .IP 3.
  529. matching a string against an instantiated variable succeeds
  530. only if the variable was instantiated to the same string.
  531. .LP
  532. Matching an actual mnemonic against the keyword ANY is defined likewise.
  533. .PP
  534. The matching scheme implements the requirement that multiple occurrences
  535. of the same variable name or of the keyword ANY should
  536. stand for the same values throughout the entire pattern
  537. (see section 2.).
  538. .PP
  539. Both the parameter restriction of 2. and the constraint of step (iii)
  540. are checked by executing the "C" expression.
  541. .NH 2
  542. Data structures
  543. .PP
  544. The most important data structure is the representation
  545. of the input instructions.
  546. For every instruction we use two representations:
  547. .IP (i)
  548. the textual representation,
  549. i.e. the exact code as it appeared in the input;
  550. .IP (ii)
  551. a structural representation,
  552. containing the opcode and the operands.
  553. .LP
  554. The opcode of an instruction is determined as soon as it is read.
  555. If the line contains a label definition, the opcode is set
  556. to "labdef", so a label definition is treated like a normal
  557. instruction.
  558. .PP
  559. The operands of an instruction are not determined until
  560. they are needed, i.e. until step (i) of the pattern matching
  561. process has succeeded.
  562. For every instruction we keep track of a \fIstate\fR.
  563. After the opcode has successfully been determined,
  564. the state is OPC_ONLY.
  565. Once the operands have been recognized, the state is set to DONE.
  566. If the opcode or operands can not be determined,
  567. or if the instruction cannot be optimized for any other
  568. reason (see Appendix A), the state is set to JUNK
  569. and any attempt to match it will fail.
  570. .PP
  571. For each table entry we record the following information:
  572. .IP (i) 7
  573. the length of the pattern (i.e. the number of instruction descriptions)
  574. .IP (ii)
  575. a description of the instructions of the pattern
  576. .IP (iii)
  577. the length of the replacement
  578. .IP (iv)
  579. a description of the instructions of the replacement.
  580. .LP
  581. The description of an instruction consists of:
  582. .IP (i)
  583. the opcode
  584. .IP (ii)
  585. for each operand, a description of the operand.
  586. .LP
  587. The description of an operand of the form:
  588. .DS
  589. string_constant1 variable_name string_constant2
  590. .DE
  591. contains:
  592. .IP (i)
  593. both string constants
  594. .IP (ii)
  595. the number of the variable.
  596. .LP
  597. Each declared variable is assigned a unique number.
  598. For every variable we maintain:
  599. .IP (i)
  600. its state (instantiated or not instantiated)
  601. .IP (ii)
  602. its current value (a string).
  603. .LP
  604. The restrictions on variables and the constraints are stored
  605. in a switch-statement,
  606. indexed by variable number and entry number respectively.
  607. .NH 1
  608. Implementation of the target optimizer generator
  609. .PP
  610. The target optimizer generator (\fItopgen\fR)
  611. reads a target machine description table and produces
  612. two files:
  613. .IP gen.h: 9
  614. contains macro definitions for
  615. machine parameters that were changed
  616. in the parameter section of the table (see appendix A)
  617. and for some attributes derived from the table
  618. (longest pattern, number of patterns, number
  619. of variables).
  620. .IP gen.c:
  621. contains the entry description tables,
  622. code for checking the parameter restrictions and constraints
  623. (switch statements)
  624. and the user-defined procedures.
  625. .LP
  626. These two files are compiled together with some machine-independent
  627. files to produce a target optimizer.
  628. .PP
  629. Topgen is implemented using
  630. the LL(1) parser generator system LLgen ,
  631. .[
  632. jacobs topics parser generation
  633. .]
  634. a powerful tool of the Amsterdam Compiler Kit.
  635. This system provides a flexible way of describing the syntax of the tables.
  636. The syntactical description of the table format included
  637. in Appendix A was derived from the LLgen syntax rules.
  638. .PP
  639. The parser uses a simple, hand-written, lexical analyzer (scanner).
  640. The scanner returns a single character in most cases.
  641. The recognition of identifiers is left to the parser, as
  642. this eases the analysis of operand descriptions.
  643. Comments are removed from the input by the scanner,
  644. but white space is passed to the parser,
  645. as it is meaningful in some contexts (it separates the
  646. opcode description from the description of the first operand).
  647. .PP
  648. Topgen maintains two symbol tables, one for variable names and one
  649. for tunable parameters.
  650. The symbol tables are organized as binary trees.
  651. .bp
  652. .NH 1
  653. References
  654. .[
  655. $LIST$
  656. .]
  657. .bp
  658. .SH
  659. Appendix A
  660. .PP
  661. In this appendix we present a complete definition of the target
  662. optimizer description table format.
  663. This appendix is intended for table-writers.
  664. We use syntax rules for the description of the table format.
  665. The following notation is used:
  666. .TS
  667. center;
  668. l l.
  669. { a } zero or more of a
  670. [ a ] zero or one of a
  671. a b a followed by b
  672. a | b a or b
  673. .TE
  674. Terminals are given in quotes, as in ';'.
  675. .PP
  676. The table may contain white space and comment at all reasonable places.
  677. Comments are as in "C", so they begin with /* and end on */.
  678. Identifiers are sequences of letters, digits and the underscore ('_'),
  679. beginning with a letter.
  680. .PP
  681. .DS
  682. .ft CW
  683. table -> {parameter_line} '%%;' {variable_declaration} '%%;'
  684. {entry} '%%;' user_routines.
  685. .ft R
  686. .DE
  687. A table consists of four sections, containing machine-dependent
  688. constants, variable declarations, pattern rules and
  689. user-supplied subroutines.
  690. .PP
  691. .DS
  692. .ft CW
  693. parameter_line -> identifier value ';' .
  694. .ft R
  695. .DE
  696. A parameter line defines some attributes of the target machines
  697. assembly code.
  698. For unspecified parameters default values apply.
  699. The names of the parameters and the corresponding defaults
  700. are shown in table 1.
  701. .TS
  702. center;
  703. l l.
  704. OPC_TERMINATOR ' '
  705. OP_SEPARATOR ','
  706. LABEL_STARTER 'I'
  707. LABEL_TERMINATOR ':'
  708. MAXOP 2
  709. MAXOPLEN 25
  710. MAX_OPC_LEN 10
  711. MAXVARLEN 25
  712. MAXLINELEN 100
  713. PAREN_OPEN not defined
  714. PAREN_CLOSE not defined
  715. .TE
  716. .ce 1
  717. table 1: parameter names and defaults
  718. .DE
  719. The OPC_TERMINATOR is the character that separates the instruction
  720. mnemonic from the first operand (if any).
  721. The OP_SEPARATOR separates adjacent operands.
  722. A LABEL_STARTER is the first character of an instruction label.
  723. (Instruction labels are assumed to start with the same character).
  724. The LABEL_TERMINATOR is the last character of a label definition.
  725. It is assumed that this character is not used in an applied
  726. occurrence of the label identifier.
  727. For example, the defining occurrence may be "I0017:"
  728. and the applied occurrence may be "I0017"
  729. as in "jmp I0017".
  730. MAXOP defines the maximum number of operands an instruction can have.
  731. MAXOPLEN is the maximum length (in characters) of an operand.
  732. MAX_OPC_LEN is the maximum length of an instruction opcode.
  733. MAXVARLEN is the maximum length of a declared string variable.
  734. As variables may be set by user routines (see "bitw" example for
  735. the Vax) the table-writer must have access to this length and
  736. must be able to change it.
  737. MAXLINELEN denotes the maximum length of a line of assembly code.
  738. PAREN_OPEN and PAREN_CLOSE must be used when the operand separator can also
  739. occur within operands, between parentheses of some kind. In this case,
  740. PAREN_OPEN must be set to a string containing the opening parentheses, and
  741. PAREN_CLOSE must be set to a string containing the closing parentheses.
  742. .PP
  743. If a line of assembly code violates any of the assumptions or
  744. exceeds some limit,
  745. the line is not optimized.
  746. Optimization does, however, proceed with the rest of the input.
  747. .PP
  748. .DS
  749. .ft CW
  750. variable_declaration -> identifier {',' identifier} restriction ';' .
  751. restriction -> '{' anything '}' .
  752. .ft R
  753. .DE
  754. A variable declaration declares one or more string variables
  755. that may be used in the patterns and in the replacements.
  756. If a variable is used as part of an operand description in
  757. a pattern, the entire pattern can only match if the
  758. restriction evaluates to TRUE.
  759. If the pattern does match, the variable is assigned the matching
  760. part of the actual operand.
  761. Variables that are not used in a pattern are initialized to
  762. null-strings and may be assigned a value in the constraint-part of
  763. the pattern.
  764. .PP
  765. The restriction must be a legal "C" expression.
  766. It may not contain a closing bracket ('}').
  767. Inside the expression, the name VAL stands for the part of the actual
  768. (matching) operand.
  769. The expression may contain calls to procedures that are defined in the
  770. user-routines section.
  771. .DS
  772. .ft CW
  773. entry -> pattern '->' replacement ';' .
  774. pattern -> instruction_descr
  775. { ':' instruction_descr }
  776. constraint .
  777. replacement -> [ instruction_descr { ':' instruction_descr } ] .
  778. instruction_descr -> opcode
  779. white
  780. [ operand_descr { ',' operand_descr } ] .
  781. constraint -> '{' anything '}' .
  782. operand_descr -> [ string_constant ]
  783. [ variable_name ]
  784. [ string_constant ] .
  785. variable_name -> identifier .
  786. opcode -> anything .
  787. .ft R
  788. .DE
  789. The symbol 'white' stands for white space (space or tab).
  790. An opcode can be any string not containing the special
  791. symbols ';', '{', '}', ':', ',', '->' or white space.
  792. To be recognized, it must begin with a letter.
  793. The opcode should either be a mnemonic of a target machine
  794. instruction or it should be one of the keywords ANY and labdef.
  795. ANY matches any actual opcode. labdef matches only label definitions.
  796. .PP
  797. If an operand description contains an identifier (as defined earlier),
  798. it is checked if the identifier is the name of a declared variable.
  799. This effects the semantics of the matching rules for the operand,
  800. as described in section 2.
  801. An operand may contain at most one such variable name.
  802. .PP
  803. The constraint must be a legal "C" expression, just as the operand restriction.
  804. It may call user-defined procedures and use or change the value of
  805. declared variables.
  806. It may also use the string variable REST,
  807. which contains the mnemonic of the first instruction of the
  808. rest of the input. (REST is a null-string if this mnemonic can
  809. not be determined).
  810. .DS
  811. .ft CW
  812. user_routines -> anything .
  813. .ft R
  814. .DE
  815. The remainder of the table consists of user-defined subroutines.