doc.t 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434
  1. .TL
  2. A Tour of the Peephole Optimizer Library
  3. .AU
  4. B. J. McKenzie
  5. .NH
  6. Introduction
  7. .LP
  8. The peephole optimizer consists of three major parts:
  9. .IP a)
  10. the table describing the optimization to be performed
  11. .IP b)
  12. a program to parse these tables and build input and output routines to
  13. interface to the library and a dfa based routine to recognize patterns and
  14. make the requested replacements.
  15. .IP c)
  16. common routines for the library that are independent of the table of a)
  17. .LP
  18. The library conforms to the
  19. .I EM_CODE(3)
  20. module interface with entry points with names like
  21. .I C_xxx.
  22. The library module results in calls to a module with an identical interface
  23. but with calls to routines with names of the form
  24. .I O_xxx.
  25. .LP
  26. We shall now describe each of these in turn in some detail.
  27. .NH
  28. The optimization table
  29. .LP
  30. The file
  31. .I patterns
  32. contains the patterns of EM instructions to be recognized by the optimizer
  33. and the EM instructions to replace them. Each pattern may have an
  34. optional restriction that must be satisfied before the replacement is made.
  35. The syntax of the table will be described using extended BNF notation
  36. used by
  37. .I LLGen
  38. where:
  39. .DS
  40. .I
  41. [...] - are used to group items
  42. | - is used to separate alternatives
  43. ; - terminates a rule
  44. ? - indicates item is optional
  45. * - indicates item is repeated zero or more times
  46. + - indicates item is repeated one or more times
  47. .R
  48. .DE
  49. The format of each rule in the table is:
  50. .DS
  51. .I
  52. rule : pattern global_restriction? ':' replacement
  53. ;
  54. .R
  55. .DE
  56. Each rule must be on a single line except that it may be broken after the
  57. colon if the next line begins with a tab character.
  58. The pattern has the syntax:
  59. .DS
  60. .I
  61. pattern : [ EM_mnem [ local_restriction ]? ]+
  62. ;
  63. EM-mnem : "An EM instruction mnemonic"
  64. | 'lab'
  65. ;
  66. .R
  67. .DE
  68. and consists of a sequence of one or more EM instructions or
  69. .I lab
  70. which stands for a defined instruction label. Each EM-mnem may optionally be
  71. followed by a local restriction on the argument of the mnemonic and take
  72. one of the following forms depending on the type of the EM instruction it
  73. follows:
  74. .DS
  75. .I
  76. local_restriction : normal_restriction
  77. | opt_arg_restriction
  78. | ext_arg_restriction
  79. ;
  80. .R
  81. .DE
  82. A normal restriction is used after all types of EM instruction except for
  83. those that allow an optional argument, (such as
  84. .I adi
  85. ) or those involving external names, (such as
  86. .I lae
  87. )
  88. and takes the form:
  89. .DS
  90. .I
  91. normal_restriction : [ rel_op ]? expression
  92. ;
  93. rel_op : '=='
  94. | '!='
  95. | '<='
  96. | '<'
  97. | '>='
  98. | '>'
  99. ;
  100. .R
  101. .DE
  102. If the rel_op is missing, the equality
  103. .I ==
  104. operator is assumed. The general form of expression is defined later but
  105. basically it involves simple constants, references to EM_mnem arguments
  106. that appear earlier in the pattern and expressions similar to those used
  107. in C expressions.
  108. The form of the restriction after those EM instructions like
  109. .I adi
  110. whose arguments are optional takes the form:
  111. .DS
  112. .I
  113. opt_arg_restriction : normal_restriction
  114. | 'defined'
  115. | 'undefined'
  116. ;
  117. .R
  118. .DE
  119. The
  120. .I defined
  121. and
  122. .I undefined
  123. indicate that the argument is present
  124. or absent respectively. The normal restriction form implies that the
  125. argument is present and satisfies the restriction.
  126. The form of the restriction after those EM instructions like
  127. .I lae
  128. whose arguments refer to external object take the form:
  129. .DS
  130. .I
  131. ext_arg_restriction : patarg offset_part?
  132. ;
  133. offset_part : [ '+' | '-' ] expression
  134. ;
  135. .R
  136. .DE
  137. Such an argument has one of three forms: a offset with no name, an
  138. offset form a name or an offset from a label. With no offset part
  139. the restriction requires the argument to be identical to a previous
  140. external argument. With an offset part it requires an identical name
  141. part, (either empty, same name or same label) and supplies a relationship
  142. among the offset parts. It is possible to refer to test for the same
  143. external argument, the same name or to obtain the offset part of an external
  144. argument using the
  145. .I sameext
  146. ,
  147. .I samenam
  148. and
  149. .I offset
  150. functions given below.
  151. .LP
  152. The general form of an expression is:
  153. .DS
  154. .I
  155. expression : expression binop expression
  156. | unaryop expression
  157. | '(' expression ')'
  158. | bin_function '(' expression ',' expression ')'
  159. | ext_function '(' patarg ',' patarg ')'
  160. | 'offset' '(' patarg ')'
  161. | patarg
  162. | 'p'
  163. | 'w'
  164. | INTEGER
  165. ;
  166. .R
  167. .DE
  168. .DS
  169. .I
  170. bin_function : 'sfit'
  171. | 'ufit'
  172. | 'samesign'
  173. | 'rotate'
  174. ;
  175. .R
  176. .DE
  177. .DS
  178. .I
  179. ext_function : 'samenam'
  180. | 'sameext'
  181. ;
  182. patarg : '$' INTEGER
  183. ;
  184. binop : "As for C language"
  185. unaryop : "As for C language"
  186. .R
  187. .DE
  188. The INTEGER in the
  189. .I patarg
  190. refers to the first, second, etc. argument in the pattern and it is
  191. required to refer to a pattern that appears earlier in the pattern
  192. The
  193. .I w
  194. and
  195. .I p
  196. refer to the word size and pointer size (in bytes) respectively. The
  197. various function test for:
  198. .IP sfit 10
  199. the first argument fits as a signed value of
  200. the number of bit specified by the second argument.
  201. .IP ufit 10
  202. as for sfit but for unsigned values.
  203. .IP samesign 10
  204. the first argument has the same sign as the second.
  205. .IP rotate 10
  206. the value of the first argument rotated by the number of bit specified
  207. by the second argument.
  208. .IP samenam 10
  209. both arguments refer to externals and have either no name, the same name
  210. or same label.
  211. .IP sameext 10
  212. both arguments refer to the same external.
  213. .IP offset 10
  214. the argument is an external and this yields it offset part.
  215. .LP
  216. The global restriction takes the form:
  217. .DS
  218. .I
  219. global_restriction : '?' expression
  220. ;
  221. .R
  222. .DE
  223. and is used to express restrictions that cannot be expressed as simple
  224. restrictions on a single argument or are can be expressed in a more
  225. readable fashion as a global restriction. An example of such a rule is:
  226. .DS
  227. .I
  228. dup w ldl stf ? p==2*w : ldl $2 stf $3 ldl $2 lof $3
  229. .R
  230. .DE
  231. which says that this rule only applies if the pointer size is twice the
  232. word size.
  233. .NH
  234. Incompatibilities with Previous Optimizer
  235. .LP
  236. The current table format is not compatible with previous versions of the
  237. peephole optimizer tables. In particular the previous table had no provision
  238. for local restrictions and only the equivalent of the global restriction.
  239. This meant that our
  240. .I '?'
  241. character that announces the presence of the optional global restriction was
  242. not required. The previous optimizer performed a number of other tasks that
  243. were unrelated to optimization that were possible because the old optimizer
  244. read the EM code for a complete procedure at a time. This included task such
  245. as register variable reference counting and moving the information regarding
  246. the number of bytes of local storage required by a procedure from it
  247. .I end
  248. pseudo instruction to it's
  249. .I pro
  250. pseudo instruction. These tasks are no longer done. If there are required
  251. then the must be performed by some other program in the pipeline.
  252. .NH
  253. The Parser
  254. .LP
  255. The program to parse the tables and build the pattern table dependent dfa
  256. routines is built from the files:
  257. .IP parser.h 15
  258. header file
  259. .IP parser.g 15
  260. LLGen source file defining syntax of table
  261. .IP syntax.l 15
  262. Lex sources file defining form of tokens in table.
  263. .IP initlex.c 15
  264. Uses the data in the library
  265. .I em_data.a
  266. to initialize the lexical analyser to recognize EM instruction mnemonics.
  267. .IP outputdfa.c 15
  268. Routines to output dfa when it has been constructed.
  269. .IP outcalls.c 15
  270. Routines to output the file
  271. .I incalls.c
  272. defined in section 4.
  273. .IP findworst.c 15
  274. Routines to analyze patterns to find how to continue matching after a
  275. successful replacement or failed match.
  276. .LP
  277. The parser checks that the tables conform to the syntax outlined in the
  278. previous section and also mades a number of semantic checks on their
  279. validity. Further versions could make further checks such as looking for
  280. cycles in the rules or checking that each replacement leaves the same
  281. number of bytes on the stack as the pattern it replaces. The parser
  282. builds an internal dfa representation of the rules by combining rules with
  283. common prefixes. All local and global restrictions are combined into a single
  284. test to be performed are a complete pattern has been detected in the input.
  285. The idea is to build a structure so that each of the patterns can be matched
  286. and then the corresponding tests made and the first that succeeds is replaced.
  287. If two rules have the same pattern and both their tests also succeed the one
  288. that appears first in the tables file will be done. Somewhat less obvious
  289. is that id one pattern is a proper prefix of a longer pattern and its test
  290. succeeds then the second pattern will not be checked for.
  291. A major task of the parser if to decide on the action to take when a rule has
  292. been partially matched or when a pattern has been completely matched but its
  293. test does not succeed. This requires a search of all patterns to see if any
  294. part of the part matched could be part of some other pattern. for example
  295. given the two patterns:
  296. .DS
  297. .I
  298. loc adi w loc adi w : loc $1+$3 adi w
  299. loc adi w loc sbi w : loc $1-$3 adi w
  300. .R
  301. .DE
  302. If the first pattern fails after seeing the input:
  303. .DS
  304. .I
  305. loc adi loc
  306. .R
  307. .DE
  308. the parser will still need to check whether the second pattern matches.
  309. This requires a decision on how to fix up any internal data structures in
  310. the dfa matcher, such as moving some instructions from the pattern to the
  311. output queue and moving the pattern along and then deciding what state
  312. it should continue from. Similar decisions are requires after a pattern
  313. has been replaced. For example if the replacement is empty it is necessary
  314. to backup
  315. .I n-1
  316. instructions where
  317. .I n
  318. is the length of the longest pattern in the tables.
  319. .NH
  320. Structure of the Resulting Library
  321. .LP
  322. The major data structures maintained by the library consist of three queues;
  323. an
  324. .I output
  325. queue of instructions awaiting output, a
  326. .I pattern
  327. queue containing instructions that match the current prefix, and a
  328. .I backup
  329. queue of instructions that have been backed up over and need to be reparsed
  330. for further pattern matches.
  331. .LP
  332. If no errors are detected by the parser in the tables it output the following
  333. files:
  334. .IP dfa.c 10
  335. this consists of a large switch statement that maintains the current state of
  336. the dfa and makes a transition to the next state if the next input instruction
  337. matches.
  338. .IP incalls.r 10
  339. this contains an entry for every EM instruction (plus
  340. .I lab
  341. ) giving information on how to build a routine with the name
  342. .I C_xxx
  343. that conforms to the
  344. .I EM_CODE(3)
  345. modules interface. If the EM instruction does not appear in the tables
  346. patterns at all then the dfa routine is called to flush any current queued
  347. output and the the output
  348. .I O_xxx
  349. routine is called. If the EM instruction does appear in a pattern then the instruction is added onto the end of the pattern queue and the dfa routines called
  350. to attempted to make a transition. This file is input to the
  351. .I awk
  352. program
  353. .I makefuns.awk
  354. to produce individual C files with names like
  355. .I C_xxx.c
  356. each containing a single function definition. This enables the loader to
  357. only load those routines that are actually needed when the library is loaded.
  358. .IP trans.c 10
  359. this contains a routine that is called after each transition to a state that
  360. contains restrictions and replacements. The restrictions a converted to
  361. C expressions and the replacements coded as calls to output instructions
  362. into the output queue.
  363. .LP
  364. The following files contain code that is independent of the pattern tables:
  365. .IP nopt.c 10
  366. general routines to initialize, and maintain the data structures.
  367. .IP aux.c 10
  368. routines to implement the functions used in the rules.
  369. .IP mkcalls.c 10
  370. code to convert the internal data structures to calls on the output
  371. .I O_xxx
  372. routines when the output queue is flushed.
  373. .NH
  374. Miscellaneous Issues
  375. .LP
  376. The size of the output and backup queues are fixed in size according to the
  377. values of
  378. .I MAXOUTPUT
  379. and
  380. .I MAXBACKUP
  381. defined in the file
  382. .I nopt.h.
  383. The size of the pattern queue is set to the length of the maximum pattern
  384. length by the tables output by the parser. The queues are implemented as
  385. arrays of pointers to structures containing the instruction and its arguments.
  386. The space for the structures are initially obtained by calls to
  387. .I Malloc
  388. (from the
  389. .I alloc(3)
  390. module),
  391. and freed when the output queue or patterns queue is cleared. These freed
  392. structures are collected on a free list and reused to avoid the overheads
  393. of repeated calls to
  394. .I malloc
  395. and
  396. .I free.
  397. .LP
  398. The fixed size of the output and pattern queues causes no difficulty in
  399. practice and can only result in some potential optimizations being missed.
  400. When the output queue fills it is simply prematurely flushed and backups
  401. when the backup queue is fill are simply ignored. A possible improvement
  402. would be to flush only part of the output queue when it fills. It should
  403. be noted that it is not possible to statically determine the maximum possible
  404. size for these queues as they need to be unbounded in the worst case. A
  405. study of the rule
  406. .DS
  407. .I
  408. inc dec :
  409. .R
  410. .DE
  411. with the input consisting of
  412. .I N
  413. .I inc
  414. and then
  415. .I N
  416. .I dec
  417. instructions requires an output queue length of
  418. .I N-1
  419. to find all possible replacements.