peep.doc 16 KB

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