nopt.doc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591
  1. .\" $Id$
  2. .TL
  3. A Tour of the New Peephole Optimizer
  4. .AU
  5. B. J. McKenzie
  6. .NH
  7. Introduction
  8. .LP
  9. The peephole optimizer consists of four major parts:
  10. .IP a)
  11. the table describing the optimization to be performed
  12. .IP b)
  13. a program to parse these tables and build input and output routines to
  14. interface to the library and a dfa based routine to recognize patterns and
  15. make the requested replacements.
  16. .IP c)
  17. common routines for the library that are independent of the table of a)
  18. .IP d)
  19. a stand alone version of the optimizer.
  20. .LP
  21. The library conforms to the
  22. .I EM_CODE(3)
  23. module interface but with routine names of the form
  24. .BI C_ xxx
  25. replaced by names like
  26. .BI O_ xxx.
  27. Furthermore there is also no routine
  28. .I O_getid
  29. and no variable
  30. .I O_tmpdir
  31. in the module.
  32. The library module results in calls to the usual
  33. .I EM_CODE(3)
  34. module. It is possible to write a front end so that it can call either the
  35. normal
  36. .I EM_CODE(3)
  37. module or this new module by adding
  38. .B
  39. #define PEEPHOLE
  40. .R
  41. before the line
  42. .B
  43. #include <em.h>
  44. .R
  45. This will map all calls to the routine
  46. .BI C_ xxx
  47. into a call to the routine
  48. .BI O_ xxx.
  49. .LP
  50. We shall now describe each of these major parts in some detail.
  51. .NH
  52. The optimization table
  53. .LP
  54. The file
  55. .I patterns
  56. contains the patterns of EM instructions to be recognized by the optimizer
  57. and the EM instructions to replace them. Each pattern may have an
  58. optional restriction that must be satisfied before the replacement is made.
  59. The syntax of the table will be described using extended BNF notation
  60. used by
  61. .I LLGen
  62. where:
  63. .DS
  64. .I
  65. [...] - are used to group items
  66. | - is used to separate alternatives
  67. ; - terminates a rule
  68. ? - indicates item is optional
  69. * - indicates item is repeated zero or more times
  70. + - indicates item is repeated one or more times
  71. .R
  72. .DE
  73. The format of each rule in the table is:
  74. .DS
  75. .I
  76. rule : pattern global_restriction? ':' replacement
  77. ;
  78. .R
  79. .DE
  80. Each rule must be on a single line except that it may be broken after the
  81. colon if the next line begins with a tab character.
  82. The pattern has the syntax:
  83. .DS
  84. .I
  85. pattern : [ EM_mnem [ local_restriction ]? ]+
  86. ;
  87. EM-mnem : "An EM instruction mnemonic"
  88. | 'lab'
  89. ;
  90. .R
  91. .DE
  92. and consists of a sequence of one or more EM instructions or
  93. .I lab
  94. which stands for a defined instruction label. Each EM-mnem may optionally be
  95. followed by a local restriction on the argument of the mnemonic and take
  96. one of the following forms depending on the type of the EM instruction it
  97. follows:
  98. .DS
  99. .I
  100. local_restriction : normal_restriction
  101. | opt_arg_restriction
  102. | ext_arg_restriction
  103. ;
  104. .R
  105. .DE
  106. A normal restriction is used after all types of EM instruction except for
  107. those that allow an optional argument, (such as
  108. .I adi
  109. ) or those involving external names, (such as
  110. .I lae
  111. )
  112. and takes the form:
  113. .DS
  114. .I
  115. normal_restriction : [ rel_op ]? expression
  116. ;
  117. rel_op : '=='
  118. | '!='
  119. | '<='
  120. | '<'
  121. | '>='
  122. | '>'
  123. ;
  124. .R
  125. .DE
  126. If the rel_op is missing, the equality
  127. .I ==
  128. operator is assumed. The general form of expression is defined later but
  129. basically it involves simple constants, references to EM_mnem arguments
  130. that appear earlier in the pattern and expressions similar to those used
  131. in C expressions.
  132. The form of the restriction after those EM instructions like
  133. .I adi
  134. whose arguments are optional takes the form:
  135. .DS
  136. .I
  137. opt_arg_restriction : normal_restriction
  138. | 'defined'
  139. | 'undefined'
  140. ;
  141. .R
  142. .DE
  143. The
  144. .I defined
  145. and
  146. .I undefined
  147. indicate that the argument is present
  148. or absent respectively. The normal restriction form implies that the
  149. argument is present and satisfies the restriction.
  150. The form of the restriction after those EM instructions like
  151. .I lae
  152. whose arguments refer to external object take the form:
  153. .DS
  154. .I
  155. ext_arg_restriction : patarg offset_part?
  156. ;
  157. offset_part : [ '+' | '-' ] expression
  158. ;
  159. .R
  160. .DE
  161. Such an argument has one of three forms: a offset with no name, an
  162. offset form a name or an offset from a label. With no offset part
  163. the restriction requires the argument to be identical to a previous
  164. external argument. With an offset part it requires an identical name
  165. part, (either empty, same name or same label) and supplies a relationship
  166. among the offset parts. It is possible to refer to test for the same
  167. external argument, the same name or to obtain the offset part of an external
  168. argument using the
  169. .I sameext
  170. ,
  171. .I samenam
  172. and
  173. .I offset
  174. functions given below.
  175. .LP
  176. The general form of an expression is:
  177. .DS
  178. .I
  179. expression : expression binop expression
  180. | unaryop expression
  181. | '(' expression ')'
  182. | bin_function '(' expression ',' expression ')'
  183. | ext_function '(' patarg ',' patarg ')'
  184. | 'offset' '(' patarg ')'
  185. | patarg
  186. | 'p'
  187. | 'w2'
  188. | 'w'
  189. | INTEGER
  190. ;
  191. .R
  192. .DE
  193. .DS
  194. .I
  195. bin_function : 'sfit'
  196. | 'ufit'
  197. | 'samesign'
  198. | 'rotate'
  199. ;
  200. .R
  201. .DE
  202. .DS
  203. .I
  204. ext_function : 'samenam'
  205. | 'sameext'
  206. ;
  207. patarg : '$' INTEGER
  208. ;
  209. binop : "As for C language"
  210. unaryop : "As for C language"
  211. .R
  212. .DE
  213. The INTEGER in the
  214. .I patarg
  215. refers to the first, second, etc. argument in the pattern and it is
  216. required to refer to a pattern that appears earlier in the pattern
  217. The
  218. .I w
  219. and
  220. .I p
  221. refer to the word size and pointer size (in bytes) respectively.
  222. The
  223. .I w2
  224. refers to twice the word size.
  225. The
  226. various function test for:
  227. .IP sfit 10
  228. the first argument fits as a signed value of
  229. the number of bit specified by the second argument.
  230. .IP ufit 10
  231. as for sfit but for unsigned values.
  232. .IP samesign 10
  233. the first argument has the same sign as the second.
  234. .IP rotate 10
  235. the value of the first argument rotated by the number of bit specified
  236. by the second argument.
  237. .IP samenam 10
  238. both arguments refer to externals and have either no name, the same name
  239. or same label.
  240. .IP sameext 10
  241. both arguments refer to the same external.
  242. .IP offset 10
  243. the argument is an external and this yields it offset part.
  244. .LP
  245. The global restriction takes the form:
  246. .DS
  247. .I
  248. global_restriction : '?' expression
  249. ;
  250. .R
  251. .DE
  252. and is used to express restrictions that cannot be expressed as simple
  253. restrictions on a single argument or are can be expressed in a more
  254. readable fashion as a global restriction. An example of such a rule is:
  255. .DS
  256. .I
  257. dup w ldl stf ? p==2*w : ldl $2 stf $3 ldl $2 lof $3
  258. .R
  259. .DE
  260. which says that this rule only applies if the pointer size is twice the
  261. word size.
  262. .NH
  263. Incompatibilities with Previous Optimizer
  264. .LP
  265. The current table format is not compatible with previous versions of the
  266. peephole optimizer tables. In particular the previous table had no provision
  267. for local restrictions and only the equivalent of the global restriction.
  268. This meant that our
  269. .I '?'
  270. character that announces the presence of the optional global restriction was
  271. not required. The previous optimizer performed a number of other tasks that
  272. were unrelated to optimization that were possible because the old optimizer
  273. read the EM code for a complete procedure at a time. This included tasks such
  274. as register variable reference counting and moving the information regarding
  275. the number of bytes of local storage required by a procedure from it
  276. .I end
  277. pseudo instruction to it's
  278. .I pro
  279. pseudo instruction. These tasks are no longer done by this module but have
  280. been moved to other modules or programs in the pipeline. The register variable
  281. reference counting is now performed by the front end. The reordering of
  282. code, such as the moving of mes instructions and the local storage
  283. requirements from the end to beginning of procedures, is now performed using
  284. the insertpart mechanism in the
  285. .I EM_CODE
  286. (or
  287. .I EM_OPT
  288. ) module.
  289. The removal of dead code is performed by the global optimizer.
  290. Various
  291. .I ext_functions
  292. available in the old tables are no longer available as they rely on
  293. information that is not available to the current program.
  294. These are the
  295. .I notreg
  296. and the
  297. .I rom
  298. functions.
  299. The previous optimizer allowed the use of
  300. .I LLP,
  301. .I LEP,
  302. .I SLP
  303. and
  304. .I SEP
  305. in patterns. For example
  306. .I LLP
  307. stood for either
  308. .I lol
  309. if the pointer size was the same as the word size, or for
  310. .I ldl
  311. if the pointer size was twice the word size.
  312. In the current optimizer it is necessary to include two patterns for each
  313. such single pattern in the old table. For example for a pattern containing
  314. .I LLP
  315. there would be one pattern with
  316. .I lol
  317. and with a global restriction of the form
  318. .I p=w
  319. and another pattern with ldl and a global restriction of the form
  320. .I p=2*w.
  321. .NH
  322. The Parser
  323. .LP
  324. The program to parse the tables and build the pattern table dependent dfa
  325. routines is built from the files:
  326. .IP parser.h 15
  327. header file
  328. .IP parser.g 15
  329. LLGen source file defining syntax of table
  330. .IP syntax.l 15
  331. Lex sources file defining form of tokens in table.
  332. .IP initlex.c 15
  333. Uses the data in the library
  334. .I em_data.a
  335. to initialize the lexical analyzer to recognize EM instruction mnemonics.
  336. .IP outputdfa.c 15
  337. Routines to output the dfa when it has been constructed. It outputs the files
  338. .I dfa.c
  339. and
  340. .I trans.c
  341. .IP outcalls.c 15
  342. Routines to output the file
  343. .I incalls.r
  344. defined in the next section.
  345. .IP findworst.c 15
  346. Routines to analyze patterns to find how to continue matching after a
  347. successful replacement or failed match.
  348. .LP
  349. The parser checks that the tables conform to the syntax outlined in the
  350. previous section and also makes a number of semantic checks on their
  351. validity. Further versions could make further checks such as looking for
  352. cycles in the rules or checking that each replacement leaves the same
  353. number of bytes on the stack as the pattern it replaces. The parser
  354. builds an internal dfa representation of the rules by combining rules with
  355. common prefixes. All local and global restrictions are combined into a single
  356. test to be performed are a complete pattern has been detected in the input.
  357. The idea is to build a structure so that each of the patterns can be matched
  358. and then the corresponding tests made and the first that succeeds is replaced.
  359. If two rules have the same pattern and both their tests also succeed the one
  360. that appears first in the tables file will be done. Somewhat less obvious
  361. is that if one pattern is a proper prefix of a longer pattern and its test
  362. succeeds then the second pattern will not be checked for.
  363. A major task of the parser if to decide on the action to take when a rule has
  364. been partially matched or when a pattern has been completely matched but its
  365. test does not succeed. This requires a search of all patterns to see if any
  366. part of the part matched could be part of some other pattern. for example
  367. given the two patterns:
  368. .DS
  369. .I
  370. loc adi w loc adi w : loc $1+$3 adi w
  371. loc adi w loc sbi w : loc $1-$3 adi w
  372. .R
  373. .DE
  374. If the first pattern fails after seeing the input:
  375. .DS
  376. .I
  377. loc adi loc
  378. .R
  379. .DE
  380. the parser will still need to check whether the second pattern matches.
  381. This requires a decision on how to fix up any internal data structures in
  382. the dfa matcher, such as moving some instructions from the pattern to the
  383. output queue and moving the pattern along and then deciding what state
  384. it should continue from. Similar decisions are requires after a pattern
  385. has been replaced. For example if the replacement is empty it is necessary
  386. to backup
  387. .I n-1
  388. instructions where
  389. .I n
  390. is the length of the longest pattern in the tables.
  391. .NH
  392. Structure of the Resulting Library
  393. .LP
  394. The major data structures maintained by the library consist of three queues;
  395. an
  396. .I output
  397. queue of instructions awaiting output, a
  398. .I pattern
  399. queue containing instructions that match the current prefix, and a
  400. .I backup
  401. queue of instructions that have been backed up over and need to be reparsed
  402. for further pattern matches.
  403. These three queues are maintained in a single fixed size buffer as explained
  404. in more detail in the next section.
  405. Also, after a successful match, a replacement queue is constructed.
  406. .LP
  407. If no errors are detected by the parser in the tables it output the following
  408. files if they have changed from the existing version of the file:
  409. .IP dfa.c 10
  410. this contains the dfa encoded into a number of arrays using the technique
  411. of row displacement for compacted sparse matricies. Given an opcode and
  412. the current state, the value of
  413. .I OO_base[OO_state]
  414. is consulted to obtain a pointer into the array
  415. .I OO_checknext.
  416. If this pointer in zero or the
  417. .I check
  418. field of the addressed structure does
  419. not correspond to the curerent state then it is known there is no entry for
  420. this opcode/state pair and the
  421. .I OO_default
  422. array is consulted instead.
  423. If the check field does match then the
  424. .I next
  425. field contains the new state.
  426. After each transition the array
  427. .I OO_ftrans
  428. is consulted to see if this state corresponds to a final state
  429. (i.e. a complete pattern) and if so the corresponding function is called.
  430. .IP trans.c 10
  431. this contains external declarations of transition routines with names like
  432. .B OO_xxxdotrans
  433. (where
  434. .I xxx
  435. is a small integer).
  436. These are called when there a transition to state
  437. .I xxx
  438. that corresponds to a
  439. complete pattern. Any tests are performed if necessary to confirm that the
  440. pattern matches and then the replacement instructions are placed on the
  441. output queue and the routine
  442. .I OO_mkrepl
  443. is called to make the replacement and if backup the amount required.
  444. If there are a number of patterns with the same instructions but different
  445. tests, these will all appear in the same routine and the tests performed in
  446. the order they appear in the original
  447. .I patterns
  448. file.
  449. .IP incalls.r 10
  450. this contains an entry for every EM instruction (plus
  451. .I lab
  452. ) giving information on how to build a routine with the name
  453. .BI O_ xxx
  454. for the library version of the module.
  455. If the EM instruction does not appear in the tables
  456. patterns at all then the dfa routine is called to flush any current queued
  457. output and the the output
  458. .BI C_ xxx
  459. routine is called. If the EM instruction does appear in a pattern then the
  460. instruction data structure fields are
  461. initialized and it is added onto the end of the pattern queue.
  462. The dfa routines are then called to attempted to make a transition.
  463. This file is input to the
  464. .I awk
  465. program
  466. .I makefuns.awk.
  467. .LP
  468. The following files contain code that is independent of the pattern tables:
  469. .IP main.c 10
  470. this is used only in the stand alone version of the optimizer and consists
  471. of code to open the input file, read the input using the
  472. .I READ_EM(3)
  473. module and call the dfa routines. This version does not require the routines
  474. constructed from the incalls.r file described above.
  475. .IP nopt.c 10
  476. general routines to initialize, and maintain the data structures. The file
  477. handling routines
  478. .I O_open
  479. etc are defined here. Also defined are routines for flushing the output queue
  480. by calling the
  481. .I EM_mkcalls
  482. routine from the
  483. .I READ_EM(3)
  484. module and moving instructions from the output to the backup queue.
  485. Routines to free the strings stored in instructions
  486. with types of
  487. .I sof_ptyp,
  488. .I pro_ptyp,
  489. .I str_ptyp,
  490. .I ico_ptyp,
  491. .I uco_ptyp,
  492. and
  493. .I fco_ptyp are also defined. These strings are copied to a large array that
  494. is extended by
  495. .I Realloc
  496. if it overflows. The strings can be thrown away on any flush that occurs when
  497. the backup queue is empty.
  498. .IP mkstrct.c 10
  499. contains routines to build the data structure from the input
  500. .BI C_ xxx
  501. routines and place the structure on the pattern queue. These routines are also
  502. used to build the data structures when a replacement is constructed.
  503. .IP aux.c 10
  504. routines to implement the external functions used in the pattern table.
  505. .LP
  506. The following files are also used in building the module library:
  507. .IP makefuns.awk 10
  508. this
  509. .I awk
  510. program is used to produce individual C files with names like
  511. .BI O_ xxx.c
  512. each containing a single function definition and then call the
  513. .I cc
  514. compiler to produce a single output file.
  515. This enables the loader to only load those routines that are actually
  516. needed when the library is loaded.
  517. .IP pseudo.r 10
  518. this file is like the
  519. .I incalls.r
  520. file produced by the parser but is built by hand and handles the pseudo
  521. EM instructions. It is also processed by
  522. .I makefuns.awk.
  523. .NH
  524. Miscellaneous Issues
  525. .LP
  526. The output, pattern and backup queues are maintained in fixed length array,
  527. .I OO_buffer
  528. allocated of size
  529. .I MAXBUFFER
  530. (a constant declared in nopt.h) at run time.
  531. It consists of an array of the
  532. .I e_instr
  533. data structure used by the
  534. .I READ_EM(3)
  535. module.
  536. At any time the pointers
  537. .I OO_patternqueue
  538. and
  539. .I OO_nxtpatt
  540. point to the beginning and end of the current pattern prefix that corresponds
  541. to the current state. Any instructions on the backup queue are between
  542. .I OO_nxtpatt
  543. and
  544. .I OO_endbackup.
  545. If there are no instructions on the backup queue then
  546. .I OO_endbackup
  547. will be 0 (zero).
  548. The size of the replacement queue is set to the length of the maximum
  549. replacement length by the tables output by the parser.
  550. .LP
  551. The fixed size of the buffer causes no difficulty in
  552. practice and can only result in some potential optimizations being missed.
  553. When space for a new instruction is required and the buffer is full the
  554. routine
  555. .I OO_halfflush
  556. is called to flush half the buffer and move all the data structures left.
  557. It should be noted that it is not possible to statically determine the
  558. maximum possible size for these queues as they need to be unbounded in
  559. the worst case.
  560. A study of the rule
  561. .DS
  562. .I
  563. inc dec :
  564. .R
  565. .DE
  566. with the input consisting of
  567. .I N
  568. .I inc
  569. and then
  570. .I N
  571. .I dec
  572. instructions requires an output queue length of
  573. .I N-1
  574. to find all possible replacements.