peep.doc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521
  1. .\" $Id$
  2. .TL
  3. Internal documentation on the peephole optimizer
  4. .br
  5. from the Amsterdam Compiler Kit
  6. .NH 1
  7. Introduction
  8. .PP
  9. Part of the Amsterdam Compiler Kit is a program to do
  10. peephole optimization on an EM program.
  11. The optimizer scans the program to match patterns from a table
  12. and if found makes the optimization from the table,
  13. and with the result of the optimization
  14. it tries to find yet another optimization
  15. continuing until no more optimizations are found.
  16. .PP
  17. Furthermore it does some optimizations that can not be called
  18. peephole optimizations for historical reasons,
  19. like branch chaining and the deletion of unreachable code.
  20. .PP
  21. The peephole optimizer consists of three parts
  22. .IP 1)
  23. A driving table
  24. .IP 2)
  25. A program translating the table to internal format
  26. .IP 3)
  27. C code compiled with the table to make the optimizer proper
  28. .PP
  29. In this document the table format, internal format and
  30. data structures in the optimizer will be explained,
  31. plus a hint on what the code does where it might not be obvious.
  32. It is a simple program mostly.
  33. .NH 1
  34. Table format
  35. .PP
  36. The driving table consists of pattern/replacement pairs,
  37. in principle one per line,
  38. although a line starting with white space is considered
  39. a continuation line for the previous.
  40. The general format is:
  41. .DS
  42. optimization : pattern ':' replacement '\en'
  43. .sp
  44. pattern : EMlist optional_boolean_expression
  45. .sp
  46. replacement : EM_plus_operand_list
  47. .DE
  48. Example of a simple one
  49. .DS
  50. loc stl $1==0 : zrl $2
  51. .DE
  52. There is no real limit for the length of the pattern or the replacement,
  53. the replacement might even be longer than the pattern,
  54. and expressions can be made arbitrarily complicated.
  55. .PP
  56. The expressions in the table are made of the following pieces:
  57. .IP -
  58. Integer constants
  59. .IP -
  60. $\fIn\fP, standing for the operand of the \fIn\fP'th EM
  61. instruction in the pattern,
  62. undefined if that instruction has no operand.
  63. .IP -
  64. w, standing for the wordsize of the code optimized.
  65. .IP -
  66. p, for the pointersize.
  67. .IP -
  68. defined(expr), true if expression is defined
  69. .IP -
  70. samesign(expr,expr), true if expressions have the same sign.
  71. .IP -
  72. sfit(expr,expr), ufit(expr,expr),
  73. true if the first expression fits signed or unsigned in the number
  74. of bits given in the second expression.
  75. .IP -
  76. rotate(expr,expr),
  77. first expression rotated left the number of bits given by the second expression.
  78. .IP -
  79. notreg(expr),
  80. true if the local with the expression as number is not a candidate to put
  81. in a register.
  82. .IP -
  83. rom(\fIn\fP,expr), contents of the rom descriptor at index expr that
  84. is associated with the global label that should be the argument of
  85. the \fIn\fP'th EM instruction.
  86. Undefined if such a thing does not exist.
  87. .PP
  88. The usual arithmetic operators may be used on integer values,
  89. if any operand is undefined the expression is undefined,
  90. except for the defined() function above.
  91. An undefined expression used for its truth value is false.
  92. All arithmetic on local label operands is forbidden,
  93. only things allowed are tests for equality.
  94. Arithmetic on global labels makes sense,
  95. i.e. one can add a global label and a constant,
  96. but not two global labels.
  97. .PP
  98. In the table one can use five additional EM instructions in patterns.
  99. These are:
  100. .IP lab
  101. Stands for a local label
  102. .IP LLP
  103. Load Local Pointer, translates into a
  104. .B lol
  105. or into a
  106. .B ldl
  107. depending on the relationship between wordsize and pointersize.
  108. .IP LEP
  109. Load External Pointer, translates into a
  110. .B loe
  111. or into a
  112. .B lde .
  113. .IP SLP
  114. Store Local Pointer,
  115. .B stl
  116. or
  117. .B sdl .
  118. .IP SEP
  119. Store External Pointer,
  120. .B ste
  121. or
  122. .B sde .
  123. .PP
  124. There is only one peephole optimizer,
  125. so the substitutions to be made for the last four instructions
  126. are made at run time before the first optimizations are made.
  127. .NH 1
  128. Internal format
  129. .PP
  130. The translating program,
  131. .I mktab
  132. converts the table into an array of bytes where all
  133. patterns follow unaligned.
  134. Format of a pattern is:
  135. .IP 1)
  136. One byte for high byte of hash value,
  137. will be explained later on.
  138. .IP 2)
  139. Two bytes for the index of the next pattern in a chain.
  140. .IP 3)
  141. An integer\u*\d,
  142. .FS
  143. * An integer is encoded as a byte when less than 255,
  144. otherwise as a byte containing 255 followed by two
  145. bytes with the real value.
  146. .FE
  147. pattern length.
  148. .IP 4)
  149. The list of pattern opcodes, one per byte.
  150. .IP 5)
  151. An integer expression index, 0 if not used.
  152. .IP 6)
  153. An integer, replacement length.
  154. .IP 7)
  155. A list of pairs consisting of a one byte opcode and an integer
  156. expression index.
  157. .PP
  158. The expressions are kept in an array of triples,
  159. implementing a binary tree.
  160. The
  161. .I mktab
  162. program tries to minimize the number of triples by reusing
  163. duplicates and even reverses the operands of commutative operators
  164. when doing so would spare a triple.
  165. .NH 1
  166. A tour through the sources
  167. .PP
  168. Now we will walk through the sources and note things of interest.
  169. .NH 2
  170. The header files
  171. .PP
  172. The header files are the place where data structures and options reside.
  173. .NH 3
  174. alloc.h
  175. .PP
  176. In the header file alloc.h several defines can be used to select various
  177. kinds of core allocation schemes.
  178. This is important on small machines like the PDP-11 since a complete
  179. procedure must be in core at the same space,
  180. and the peephole optimizer should not be the limiting factor in
  181. determining the maximum size of procedures if possible.
  182. Options are:
  183. .IP -
  184. USEMALLOC, standard malloc() and free() are used instead of the own
  185. core allocation package.
  186. Not recommended unless the own package does not work on some bizarre
  187. machine.
  188. .IP -
  189. COREDEBUG, prints large amounts of information about core management.
  190. Not recommended unless the code is changed and it stops working.
  191. .IP -
  192. SEPID, defining this will add an extra procedure that will
  193. go through a lot of work to scrape the last bytes together if the
  194. system won't provide more.
  195. This is not a good idea if memory is scarce and code and data reside
  196. in the same spaces, since the room used by the procedure might well
  197. be more than the room saved.
  198. .IP -
  199. STACKROOM, number of shorts used in stack space.
  200. This is used if memory is scarce and stack space and data space are
  201. different.
  202. On the PDP-11 a UNIX process starts with an 8K stack segment which
  203. cannot be transferred to the data segment.
  204. Under these conditions one can use a lot of the stack space for storage.
  205. .NH 3
  206. assert.h
  207. .PP
  208. Just defines the assert macro.
  209. When compiled with -DNDEBUG all asserts will be off.
  210. .NH 3
  211. ext.h
  212. .PP
  213. Gives external definitions of variables used by more than one module.
  214. .NH 3
  215. line.h
  216. .PP
  217. Defines the structures used to keep instructions,
  218. one structure per line of EM code,
  219. and the structure to keep arguments of pseudos,
  220. one structure per argument.
  221. Both structures essentially contain a pointer to the next,
  222. a type,
  223. and a union containing information depending on the type.
  224. Core is allocated only for the part of the union used.
  225. .PP
  226. The
  227. .I
  228. struct line
  229. .R
  230. has a very compact encoding for small integers,
  231. they are encoded in the type field.
  232. On the PDP-11 this gives a line structure of only 4 bytes for most
  233. instructions.
  234. .NH 3
  235. lookup.h
  236. .PP
  237. Contains definition of the struct used for symbol table management,
  238. global labels and procedure names are kept in one table.
  239. .NH 3
  240. optim.h
  241. .PP
  242. If one defines the DIAGOPT option in this header file,
  243. for every optimization performed a number is written on stderr.
  244. The number gives the number of the pattern in the table
  245. or one of the four special numbers in this header file.
  246. .NH 3
  247. param.h
  248. .PP
  249. Contains one settable option,
  250. LONGOFF.
  251. If this is not defined the optimizer can only optimize programs
  252. with wordsize 2 and pointersize 2.
  253. Set this only if it must be run on a Z80 or something pathetic like that.
  254. .PP
  255. Other defines here should not be touched.
  256. .NH 3
  257. pattern.h
  258. .PP
  259. Contains defines of indices in a pattern,
  260. definition of the expression triples,
  261. definitions of the various expression operators
  262. and definition of the result struct where expression results are put.
  263. .PP
  264. This header file is the main one that is also included by
  265. .I mktab .
  266. .NH 3
  267. proinf.h
  268. .PP
  269. This one contains definitions
  270. for the local label table structs
  271. and for the struct where all information for one procedure is kept.
  272. This is in one struct so it can be saved easily when recursive
  273. procedures have to be resolved.
  274. .NH 3
  275. tes.h
  276. .PP
  277. Contains the data structure used by the top element size computation.
  278. .NH 3
  279. types.h
  280. .PP
  281. Collection of typedefs to be used by almost all modules.
  282. .NH 2
  283. The C code itself.
  284. .PP
  285. The C code will now be the center of our attention.
  286. We will make a walk through the sources and we will try
  287. to follow the sources in a logical order.
  288. So we will start at
  289. .NH 3
  290. main.c
  291. .PP
  292. The main.c module contains the main() function.
  293. Here nothing spectacular happens,
  294. only thing of interest is the handling of flags:
  295. .IP -L
  296. This is an instruction to the peephole optimizer to perform
  297. one of its auxiliary functions, the generation of a library module.
  298. This makes the peephole optimizer write its output on a temporary file,
  299. and at the end making the real output by first generating a list
  300. of exported symbols and then copying the temporary file behind it.
  301. .IP -n
  302. Disables all optimization.
  303. Only thing the optimizer does now is filling in the blank after the
  304. .I END
  305. pseudo and resolving recursive procedures.
  306. .PP
  307. The place where main() is left is the call to getlines() which brings
  308. us to
  309. .NH 3
  310. getline.c
  311. .PP
  312. This module reads the EM code and constructs a list of
  313. .I
  314. struct line
  315. .R
  316. records,
  317. linked together backwards,
  318. i.e. the first instruction read is the last in the list.
  319. Pseudos are handled here also,
  320. for most pseudos this just means that a chain of argument records
  321. is linked into the linked line list but some pseudos get special attention:
  322. .IP exc
  323. This pseudo is acted upon right away.
  324. Lines read are shuffled around according to instruction.
  325. .IP mes
  326. Some messages are acted upon.
  327. These are:
  328. .RS
  329. .IP ms_err 8
  330. The input is drained, just in case it is a pipe.
  331. After that the optimizer exits.
  332. .IP ms_opt
  333. The do not optimize flag is set.
  334. Acts just like -n on the command line.
  335. .IP ms_emx
  336. The word- and pointersize are read,
  337. complain if we are not able to handle this.
  338. .IP ms_reg
  339. We take notice of the offset of this local.
  340. See also comments in the description of peephole.c
  341. .RE
  342. .IP pro
  343. A new procedure starts, if we are already in one save the status,
  344. else process collected input.
  345. Collect information about this procedure and if already in a procedure
  346. call getlines() recursively.
  347. .IP end
  348. Process collected input.
  349. .PP
  350. The phrase "process collected input" is used twice,
  351. which brings us to
  352. .NH 3
  353. process.c
  354. .PP
  355. This module contains the entry point process() which is called at any
  356. time the collected input must be processed.
  357. It calls a variety of other routines to get the real work done.
  358. Routines in this module are in chronological order:
  359. .IP symknown 12
  360. Marks all symbols seen until now as known,
  361. i.e. it is now known whether their scope is local or global.
  362. This information is used again during output.
  363. .IP symvalue
  364. Runs through the chain of pseudos to give values to data labels.
  365. This needs an extra pass.
  366. It cannot be done during the getlines pass, since an
  367. .B exc
  368. pseudo could destroy things.
  369. Nor can it be done during the backward pass since it is impossible
  370. to do good fragment numbering backward.
  371. .IP checklocs
  372. Checks whether all local labels referenced are defined.
  373. It needs to be sure about this since otherwise the
  374. semi global optimizations made cannot work.
  375. .IP relabel
  376. This routine finds the final destination for each label in the procedure.
  377. Labels followed by unconditional branches or other labels are marked during
  378. the peephole fase and this leeds to chains of identical labels.
  379. These chains are followed here, and in the local label table each label
  380. has associated with it its replacement label, after this procedure is run.
  381. Care is taken in this routine to prevent a loop in the program to
  382. cause the optimizer to loop.
  383. .IP cleanlocals
  384. This routine empties the local label table after everything
  385. is processed.
  386. .PP
  387. But before this can all be done,
  388. the backward linked list of instructions first has to be reversed,
  389. so here comes
  390. .NH 3
  391. backward.c
  392. .PP
  393. The routine backward has a number of functions:
  394. .IP -
  395. It reverses the backward linked list, making two forward linked lists,
  396. one for the instructions and one for the pseudos.
  397. .IP -
  398. It notes the last occurrence of data labels in the backward linked list
  399. and puts it in the global symbol table.
  400. This is of course the first occurence in the procedure.
  401. This information is needed to decide whether the symbols are global
  402. or local to this module.
  403. .IP -
  404. It decides about the fragment boundaries of data blocks.
  405. Fragments are numbered backwards starting at 3.
  406. This is done to be able to make the type of an expression
  407. containing a symbol equal to its fragment.
  408. This type can then not clash with the types integer and local label.
  409. .IP -
  410. It allocates a rom buffer to every data label with a rom behind
  411. it, if that rom contains only plain integers at the start.
  412. .PP
  413. The first thing done after process() has called backward() and some
  414. of its own little routines is a call to the real routine,
  415. the one that does the work the program was written for
  416. .NH 3
  417. peephole.c
  418. .PP
  419. The first routines in peephole.c
  420. implement a linked list for the offsets of local variables
  421. that are candidates for a register implementation.
  422. Several patterns use the notreg() function,
  423. since it is forbidden to combine a load of that variable
  424. with the load of another and
  425. it is not allowed to take the address of that variable.
  426. .PP
  427. The routine peephole hashes the patterns the first time it is called
  428. after which it doesn't do much more than calling optimize.
  429. But first hashpatterns().
  430. .PP
  431. The patterns are hashed at run time of the optimizer because of
  432. the
  433. .B LLP ,
  434. .B LEP ,
  435. .B SLP
  436. and
  437. .B SEP
  438. instructions added to the instruction set in this optimizer.
  439. These are first replaced everywhere in the table by the correct
  440. replacement after which the first three instructions of the
  441. pattern are hashed and the pattern is linked into one of the
  442. 256 linked lists.
  443. There is a define CHK_HASH in this module that
  444. can be set if the randomness of the hashing
  445. function is not trusted.
  446. .PP
  447. The attention now shifts to optimize().
  448. This routine calls basicblock() for every piece of code between two labels.
  449. It also notes which labels have another label or a branch behind them
  450. so the relabel() routine from process.c can do something with that.
  451. .PP
  452. Basicblock() keeps making passes over its basic block
  453. until no more optimizations are found.
  454. This might be inefficient if there is a long basicblock with some
  455. deep recursive optimization in one part of it.
  456. The entire basic block is then scanned a lot of times just for
  457. that one piece.
  458. The alternative is backing up after making an optimization and running
  459. through the same code again, but that is difficult
  460. in a single linked list.
  461. .PP
  462. It hashes instructions and calls trypat() for every pattern that has
  463. a full hash value match,
  464. i.e. lower byte and upper byte equal.
  465. Longest pattern is tried first.
  466. .PP
  467. Trypat() checks length and opcodes of the pattern.
  468. If correct it fills the iargs[] array with argument values
  469. and calculates the expression.
  470. If that is also correct the work shifts to tryrepl().
  471. .PP
  472. Tryrepl() generates the list of replacement instructions,
  473. links it into the list and returns true.
  474. Why then the name tryrepl() if it always succeeds?
  475. Well, there is a mechanism in the optimizer,
  476. unused until today that makes it possible to do optimizations that cannot
  477. be described by the table.
  478. It is possible to give a number as a replacement which will cause the
  479. optimizer to call a routine special() to do some work.
  480. This routine might decide not to do an optimization and return false.
  481. .PP
  482. The last routine that is called from process() is putline()
  483. to write the optimized code, bringing us to
  484. .NH 3
  485. tes.c
  486. .PP
  487. Contains the routines used by the top element size computation phase,
  488. which is run after the peephole-optimisation.
  489. The main routine of tes.c is tes_instr(). This looks at an instruction and
  490. decides the size of the element on top of the stack after the instruction
  491. is executed. When a label is defined or used, the size of the top element
  492. is remembered for later use. When the information in consistent throuhout
  493. the procedure, it is passed to the code generator by means of an ms_tes
  494. message.
  495. .NH 3
  496. putline.c
  497. .PP
  498. The major part of putline.c is the standard set of routines
  499. that makes EM compact code.
  500. The extra functions performed are:
  501. .IP -
  502. For every occurence of a global symbol it might be necessary to
  503. output a
  504. .B exa ,
  505. .B exp ,
  506. .B ina
  507. or
  508. .B inp
  509. pseudo instruction.
  510. That task is performed.
  511. .IP -
  512. The
  513. .B lin
  514. instructions are optimized here,
  515. .B lni
  516. instructions added for
  517. .B lin
  518. instructions and superfluous
  519. .B lin
  520. instructions deleted.