m68020.doc 43 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408
  1. .nr PS 11
  2. .nr VS 13p
  3. .EQ
  4. delim @@
  5. .EN
  6. .EQ
  7. gfont R
  8. .EN
  9. .ND
  10. .RP
  11. .TL
  12. A back end table for the Motorola MC68000, MC68010 and MC68020 microprocessors
  13. .AU
  14. Frank Doodeman
  15. .AB
  16. A back end table is part of the Amsterdam Compiler Kit (ACK). It is used
  17. to produce the actual back end, a program that translates the intermediate
  18. language family EM to assembly language for some target machine. The table
  19. discussed here can be used for two back ends, suitable for in total three
  20. machines: the MC68000 and MC68010 (the difference between these two is
  21. so small that one back end table can be used for either one), or
  22. for the MC68020.
  23. .AE
  24. .NH
  25. Introduction
  26. .PP
  27. To simplify the task of producing portable (cross) compilers and interpreters
  28. the Vrije Universiteit designed an integrated collection of programs, the
  29. Amsterdam Compiler Kit (ACK) [2]. It is based on the old UNCOL idea [1] which
  30. attempts to solve the problem of how to make a compiler for each of @ N @
  31. languages on @ M @ different machines without having to write @ N times M @
  32. programs.
  33. .PP
  34. The UNCOL approach is to write @ N @
  35. .I
  36. front ends,
  37. .R
  38. which translate the
  39. source language into a common intermediate language UNCOL (Universal Computer
  40. Oriented Language), and @ M @
  41. .I
  42. back ends,
  43. .R
  44. each of which translates programs in
  45. UNCOL into a specific machine language. Under these conditions only @ M + N @
  46. programs must be written to provide all @ N @ languages on all @ M @
  47. machines, instead of @ M times N @ programs.
  48. .PP
  49. The intermediate language for the Amsterdam Compiler Kit is the machine language
  50. for a simple stack machine called EM (Encoding Machine) [3]. So a back end for
  51. the MC68020 translates EM code into MC68020 assembly language. Writing such a
  52. table [4] suffices to get the back end.
  53. .PP
  54. The back end is a single program that is driven by a machine dependent driving
  55. table. This table, the back end table, defines the mapping of EM code to
  56. the MC68000, MC68010 or MC68020 assembly language.
  57. .NH
  58. The MC68000 and MC68020 micro processors
  59. .PP
  60. In this document the name MC68000 will be used for both the MC68000 and the
  61. MC68010 micro processors, because as far as the back end table is concerned
  62. there is no difference between them. For a complete and detailed description
  63. of the MC68020 one is referred to [5]; for the MC68000 one might also use [6].
  64. In this section some relevant parts will be handled.
  65. .NH 2
  66. Registers
  67. .PP
  68. Both the MC68000 and the MC68020 have eight 32-bit data registers (@ D sub 0 @-@ D sub 7 @) that can
  69. be used for byte (8-bit), word (16-bit) and long word (32-bit) data operations.
  70. They also have seven 32-bit address registers (@ A sub 0 @-@ A sub 6 @) that may be used as
  71. software stack pointers and base address registers; address register @ A sub 7 @ is
  72. used as the system stack pointer. Address registers may also be used for
  73. word and long word address operations.
  74. .NH 2
  75. Addressing modes
  76. .PP
  77. First the MC68000 addressing modes will be discussed. Since the MC68020's
  78. set of addressing modes is an extension of the MC68000's set, of course this
  79. section also applies to the MC68020.
  80. .PP
  81. In the description we use:
  82. .IP @ A sub n @
  83. for address register;
  84. .IP @ D sub n @
  85. for data register;
  86. .IP @ R sub n @
  87. for address or data register;
  88. .IP @ X sub n @
  89. for index register (either data or address register);
  90. .IP @ PC @
  91. for program counter;
  92. .IP @ d sub 8 @
  93. for 8 bit displacement integer;
  94. .IP @ d sub 16 @
  95. for 16 bit displacement integer;
  96. .IP @ bd @
  97. for base displacement (may be null, word or long);
  98. .IP @ od @
  99. for outer displacement (may be null, word or long).
  100. .NH 3
  101. General addressing modes
  102. .NH 4
  103. Register Direct Addressing
  104. .IP Syntax: 8
  105. @ R sub n @
  106. .PP
  107. This addressing mode (it can be used with either a data register or an address
  108. register) specifies that the operand is in one of
  109. the 16 multifunction registers.
  110. .NH 4
  111. Address Register Indirect
  112. .IP Syntax: 8
  113. @ ( A sub n ) @
  114. .PP
  115. The address of the operand is in the address register specified.
  116. .NH 4
  117. Address Register Indirect With Postincrement
  118. .IP Syntax: 8
  119. @ ( A sub n )+ @
  120. .PP
  121. The address of the operand is in the address register specified. After the
  122. operand address is used, the address register is incremented by one, two or
  123. four depending upon whether the size of the operand is byte, word or long.
  124. If the address register is the stack pointer and the operand size is byte, the
  125. address register is incremented by two rather than one to keep the stack pointer
  126. on a word boundary.
  127. .NH 4
  128. Address Register Indirect With Predecrement
  129. .IP Syntax: 8
  130. @ -( A sub n ) @
  131. .PP
  132. The address of the operand is in the address register specified. Before the
  133. operand address is used, the address register is decremented by one, two or
  134. four depending upon whether the size of the operand is byte, word or long.
  135. If the address register is the stack pointer and the operand size is byte, the
  136. address register is decremented by two rather than one to keep the stack pointer
  137. on a word boundary.
  138. .NH 4
  139. Address Register Indirect With Displacement
  140. .IP Syntax: 8
  141. @ d sub 16 ( A sub n ) @ for the MC68000, @ ( d sub 16 , A sub n ) @ for the MC68020
  142. .PP
  143. This address mode requires one word of extension. The address of the operand is
  144. the sum of the contents of the address register and the sign extended 16-bit
  145. integer in the extension word.
  146. .NH 4
  147. Address Register Indirect With Index
  148. .IP Syntax: 8
  149. @ d sub 8 ( A sub n , X sub n .size) @ for the MC68000, @ ( d sub 8 , A sub n , X sub n .size) @ for the MC68020
  150. .PP
  151. This address mode requires one word of extension according to a certain format,
  152. which specifies
  153. .IP 1.
  154. which register to use as index register;
  155. .IP 2.
  156. a flag that indicates whether the index register is a data register or an
  157. address register;
  158. .IP 3.
  159. a flag that indicates the index size; this is
  160. .I word
  161. when the low order part of the index register is to be used, and
  162. .I long
  163. when the whole long value in the register is to be used as index;
  164. .IP 4.
  165. an 8-bit displacement integer (the low order byte of the extension word).
  166. .PP
  167. The address of the operand is the sum of the contents of the address register,
  168. the possibly sign extended contents of index register and the sign
  169. extended 8-bit displacement.
  170. .NH 4
  171. Absolute Data Addressing
  172. .IP Syntax: 8
  173. @ address @ for the MC68000, @ ( address ) @ for the MC68020
  174. .PP
  175. Two different kinds of this mode are available:
  176. .IP 1.
  177. Absolute Short Address; this mode requires one word of extension. The address of
  178. the operand is the sign extended 16-bit extension word.
  179. .IP 2.
  180. Absolute Long Address; this mode requires two words of extension. The address of
  181. the operand is developed by concatenation of the two extension words; the high
  182. order part of the address is the first extension word, the low order part is
  183. the second.
  184. .NH 4
  185. Program Counter With Displacement.
  186. .IP Syntax: 8
  187. @ d sub 16 ( PC ) @ for the MC68000, @ ( d sub 16 , PC ) @ for the MC68020
  188. .PP
  189. This mode requires one word of extension. The address of the operand is the sum
  190. of the address in the program counter and the sign extended 16-bit displacement
  191. integer in the extension word. The value in the program counter is the
  192. address of the extension word.
  193. .NH 4
  194. Program Counter With Index
  195. .IP Syntax: 8
  196. @ d sub 8 ( PC , X sub n .size ) @ for the MC68000, @ ( d sub 8 , PC, X sub n .size ) @ for the MC68020
  197. .PP
  198. This mode requires one word of extension as described under
  199. .I
  200. Address Register Indirect With Index.
  201. .R
  202. The address of the operand is the sum of the value in the
  203. program counter, the possibly sign extended index register and the sign
  204. extended 8-bit displacement integer in the extension word.
  205. The value in the program counter is the address of the extension word.
  206. .NH 4
  207. Immediate Data
  208. .IP Syntax: 8
  209. @ "\#data" @
  210. .PP
  211. This addressing mode requires either one or two words of extension, depending
  212. on the size of the operation;
  213. .IP
  214. byte operation - the operand is in the low order byte of extension word;
  215. .IP
  216. word operation - the operand is in the extension word;
  217. .IP
  218. long operation - the operand is in the two extension words, the high order
  219. 16-bits are in the first extension word, the low order 16-bits in the second.
  220. .NH 3
  221. Extra MC68020 addressing modes
  222. .PP
  223. The MC68020 has three more addressing modes. These modes all use a displacement
  224. (some even two), an address register and an index register. Instead of the
  225. address register one may also use the program counter. Any of these
  226. may be omitted. If all addends are omitted the processor creates an
  227. effective address of zero. All of these three modes require at least one
  228. extension word, the
  229. .I
  230. Full Format Extension Word,
  231. .R
  232. which specifies:
  233. .IP 1.
  234. the index register number (0-7);
  235. .IP 2.
  236. the index register type (address or data register);
  237. .IP 3.
  238. the size of the index (only low order part or the whole register)
  239. .IP 4.
  240. a scale factor. This is a number from 0 to 3 which specifies how many bits
  241. the contents of the index register is to be shifted to the left before being
  242. used as an index;
  243. .IP 5.
  244. a flag that specifies whether the base (address) register is to be added or
  245. to be suppressed;
  246. .IP 6.
  247. a flag that specifies whether to add or suppress the index operand;
  248. .IP 7.
  249. two bits that specify the size of the base displacement (null, word or long);
  250. .IP 8.
  251. three bits that in combination with (6) above specify which of the three
  252. addressing modes (described below) to use and, if used, the size of the
  253. outer displacement (null, word or long).
  254. .IP N.B.
  255. All modes mentioned above for the MC68000
  256. that use an index register may have this register
  257. scaled (only when using the MC68020).
  258. .PP
  259. The three extra addressing modes are:
  260. .NH 4
  261. Address Register Indirect With Index (Base Displacement)
  262. .IP Syntax: 8
  263. @ ( bd , A sub n , X sub n .size*scale ) @ (MC68020 only)
  264. .PP
  265. The address of the operand is the sum of the contents of the address register,
  266. the scaled contents of the possibly scaled index register and the possibly
  267. sign extended base displacement. When the program counter is used instead
  268. of the address register, the value in the program counter is the address
  269. of the full format extension word. This mode requires one or two more extension
  270. words when the size of the base displacement is word or long respectively.
  271. .PP
  272. Note that without the index operand, this mode is an extension of the
  273. .I
  274. Address Register Indirect With Displacement
  275. .R
  276. mode; when using the MC68020 one is no longer limited to a 16-bit displacement.
  277. Also note that with the index operand added, this mode is an extension
  278. of the
  279. .I
  280. Address Register Indirect With Index
  281. .R
  282. mode; when using the MC68020 one is no longer limited to an 8-bit displacement.
  283. .NH 4
  284. Memory Indirect Post-Indexed
  285. .IP Syntax: 8
  286. @ ( [ bd , A sub n ] , X sub n .size*scale , od ) @ (MC68020 only)
  287. .PP
  288. This mode may use an outer displacement. First an intermediate memory
  289. address is calculated by adding the contents of the address register and
  290. the possibly sign extended base displacement. This address is used
  291. for in indirect memory access of a long word, followed by adding
  292. the index operand (scaled and possibly signed extended). Finally the
  293. outer displacement is added to yield the address of the operand.
  294. When the program counter is used, the value in the program counter is the
  295. address of the full format extension word.
  296. .NH 4
  297. Memory Indirect Pre-Indexed
  298. .IP Syntax: 8
  299. @ ( [ bd , A sub n , X sub n .size*scale ] , od ) @ (MC68020 only)
  300. .PP
  301. This mode may use an outer displacement. First an intermediate memory
  302. address is calculated by adding the contents of the address register,
  303. the scaled contents of the possibly sign extended index register and
  304. the possibly sign extended base displacement. This address is used
  305. for an indirect memory access of a long word, followed by adding
  306. the outer displacement to yield the address of the operand.
  307. When the program counter is used, the value in the program counter is the
  308. address of the full format extension word.
  309. .NH 3
  310. Addressing modes used in the table
  311. .PP
  312. Not all addressing modes mentioned above are used in code generation. It is
  313. clear that none of the modes that use the program counter PC can be used,
  314. since at code generation time nothing is known about the value in PC.
  315. Also some of the possibilities of the three MC68020 addressing modes are not
  316. used; e.g. it is possible to use a
  317. .I
  318. Data Register Indirect
  319. .R
  320. mode, which actually is the
  321. .I
  322. Address Register Indirect With Index
  323. .R
  324. mode, with the address register and the displacement left out. However
  325. such a mode would require two extra bytes for the full format extension word,
  326. and it would also be much slower than using
  327. .I
  328. Address Register Indirect.
  329. .R
  330. For this kind of reasons several possible addressing modes are not used in the
  331. generation of code.
  332. In the table address registers are only used for holding addresses, and
  333. for index registers only data registers are used.
  334. .NH
  335. The M68000 and MC68020 back end table
  336. .PP
  337. The table itself has to be run through the C preprocessor
  338. before it can be used to generate
  339. the back end (called
  340. .I
  341. code generator
  342. .R
  343. or
  344. .I cg
  345. for short). When no flags are given to
  346. the preprocessor an MC68020 code generator is produced; for the MC68000
  347. code generator one has to run the table through the preprocessor using the
  348. .I -Dm68k4
  349. flag.
  350. .PP
  351. The table is designed as described in [4]. For the overall design of a back
  352. end table one is referred to this document. This section only deals
  353. with problems encountered in writing the table and other things worth noting.
  354. .NH 2
  355. Constant Definitions
  356. .PP
  357. Wordsize and pointersize (EM_WSIZE and EM_PSIZE respectively) are defined
  358. as four (bytes). EM_BSIZE, the hole between AB (the parameter base) and
  359. LB (the local base), is eight bytes: only
  360. the return address and the localbase are saved.
  361. .NH 2
  362. Properties
  363. .PP
  364. Since Hans van Staveren in his document [4] clearly states that
  365. .I cg
  366. execution time is negatively influenced by the number of properties, only
  367. four different properties have been defined. Besides, since the registers
  368. really are multifunctional, these four are really all that are needed.
  369. .NH 2
  370. Registers
  371. .PP
  372. The table uses register variables: @ D sub 3 @ - @ D sub 7 @ are used as general register
  373. variables, and address registers @ A sub 2 @ - @ A sub 5 @ are used as pointer register
  374. variables. @ A sub 6 @ is reserved for the localbase.
  375. .NH 2
  376. Tokens
  377. .PP
  378. At first glance one might wonder about the amount of tokens, especially
  379. for the MC68020, considering the small amount of different addressing modes.
  380. However, the last three addressing modes mentioned for the MC68020 may
  381. omit any of the addends, and this leads to a large amount of different tokens.
  382. I did consider the possibility of enlarging the number of tokens and sets
  383. even further, because there might be assemblers that don't handle displacements
  384. of zero optimally (they might generate a 2 byte extension word holding zero).
  385. The small profit in bytes in the generated code
  386. however does not justify the increase
  387. in size of the token section, the set section and the patterns section,
  388. so this idea was not developed any further.
  389. .PP
  390. The timing cost of the tokens may be incorrect for some MC68000 tokens.
  391. This is because the MC68000 uses a 16-bit data bus which causes the need
  392. of two separate memory accesses for getting 32-bit operands.
  393. .NH 3
  394. Token names
  395. .PP
  396. The amount of tokens and the limited capability of the authors imagination
  397. might have caused the names of some tokens not to be very clarifying.
  398. Some information about the names may be in place here.
  399. .PP
  400. Whenever part of a token name is in capitals that part is memory indirected
  401. (i.e. in square brackets). In token names
  402. .I OFF
  403. and
  404. .I off
  405. mean an offsetted address register, so an address register with a displacement
  406. (either base displacement or outer displacement).
  407. .I
  408. IND, ind
  409. .R
  410. and
  411. .I index
  412. stand for indexed, or index register.
  413. .I ABS
  414. and
  415. .I abs
  416. stand for absolute, which actually is just a displacement (base or outer).
  417. These `rules' only apply to names of tokens that represent actual operands.
  418. There are also tokens that represent addresses of operands. These
  419. (with a few exceptions) contain
  420. .I
  421. regA, regX
  422. .R
  423. and
  424. .I con
  425. as parts of there names, which stand for address register, index register and
  426. displacement (always base displacement) respectively. If the address to which
  427. the token refers uses memory indirection, that part of the name comes first
  428. (in small letters), followed by an underscore. The memory indirection part
  429. follows the `rules' for operand token names.
  430. .PP
  431. Of course there are exceptions to these `rules' but in those cases the names
  432. are self explanatory.
  433. .PP
  434. Two special cases:
  435. .I ext_regX
  436. is the name of the token that represents the
  437. address of an absolute indexed operand, syntax @ ( bd , X sub n .size*scale ) @;
  438. .I regX
  439. does not represent any real mode, but is used with EM array instructions and
  440. pointer arithmetic.
  441. .NH 3
  442. Special tokens for the MC68000
  443. .PP
  444. The MC68000 requires two extra tokens, which are called
  445. .I t_regAcon
  446. and
  447. .I
  448. t_regAregXcon.
  449. .R
  450. They are necessary because
  451. .I regAcon
  452. can only have a 16-bit displacement on the MC68000, and
  453. .I regAregXcon
  454. uses only 8 bits for its displacement. To prevent these addressing modes to
  455. be used with displacements that are too large, the extra tokens are needed.
  456. Whenever the displacements become too large and they need
  457. to be used in the generation
  458. of assembly code, these tokens are transformed into other tokens.
  459. To prevent the table from becoming too messy I defined
  460. .I t_regAcon
  461. and
  462. .I t_regAregXcon
  463. to be identical to
  464. .I regAcon
  465. and
  466. .I regAregXcon
  467. respectively for the MC68020.
  468. .NH 2
  469. Sets
  470. .PP
  471. Most set names used in the table are self explanatory, especially to the reader
  472. who is familiar with the four addressing categories as mentioned in [5]:
  473. .I
  474. data, memory, alterable
  475. .R
  476. and
  477. .I
  478. control.
  479. .R
  480. In the sets definition part some sets are defined that are not used elsewhere in
  481. the table, but are only used to be part of the definition of
  482. some other set. This keeps the
  483. set definition part from getting too unreadable.
  484. .PP
  485. The sets called
  486. .I imm_cmp
  487. consist of all tokens that can be used to compare with a constant.
  488. .NH 2
  489. Instructions
  490. .PP
  491. Only the instructions that are used in code generation are listed here.
  492. The first few instructions are meant especially for the use with register
  493. variables. The operand LOCAL used here refers to a register variable.
  494. The reader may not conclude that these operations are also allowed on
  495. ordinary locals. The space and timing cost of these instructions have been
  496. adapted, but the use of the word LOCAL for register variables causes these cost
  497. to be inaccurate anyway.
  498. .PP
  499. The
  500. .I killreg
  501. instruction, which generates a comment in the assembly language output and
  502. which is meant to let
  503. .I cg
  504. know that the data register operand has its contents destroyed,
  505. needs some explaining but this explanation is better in place
  506. in the discussion of groups 3 and 4 of the section about patterns.
  507. .PP
  508. The timing cost of the instructions are probably not very accurate for the
  509. MC68020 because the MC68020 uses an instruction cache and prefetch. The
  510. cost used in the table are the `worst case cost' as mentioned in section 9
  511. of [5].
  512. .NH 2
  513. Moves
  514. .PP
  515. These are all pretty straightforward, except perhaps when
  516. .I t_regAcon
  517. and
  518. .I t_regAregXcon
  519. are used. In these cases the size of the displacement has to be checked
  520. before moving. This also applies to the stacking rules and the coercions.
  521. .NH 2
  522. Tests
  523. .PP
  524. These three tests (one fore each operation size) could not be more
  525. straightforward than they are now.
  526. .NH 2
  527. Stackingrules
  528. .PP
  529. The only peculiar stackingrule is the one for
  530. .I
  531. regX.
  532. .R
  533. This token is only used with EM array instructions and
  534. with pointer arithmetic. Whenever it is put
  535. on the fake stack, some EM instructions are left in the instruction stream
  536. to remove this token. Consequently it should never have to be stacked. However
  537. the
  538. .I
  539. code generator generator
  540. .R
  541. (or
  542. .I cgg
  543. for short)
  544. complained about not having a stackingrule for this token, so it had to
  545. be added nevertheless.
  546. .NH 2
  547. Coercions
  548. .PP
  549. These are all straightforward. There are no splitting coercions since
  550. the fake stack never contains any tokens that can be split.
  551. There are only two unstacking coercions.
  552. The rest are all transforming coercions. Almost all coercions transform
  553. tokens into either a data register or an address register, except in the
  554. MC68000 part of the table the
  555. .I t_regAcon
  556. and
  557. .I t_regAregXcon
  558. tokens are transformed into real
  559. .I regAcon
  560. and
  561. .I regAregXcon
  562. tokens with displacements that are properly sized.
  563. .NH 2
  564. Patterns
  565. .PP
  566. This is the largest part of the table. It is subdivided into 17 groups.
  567. We will take a closer look at the more interesting groups.
  568. .NH 3
  569. Group 0: rules for register variables
  570. .PP
  571. This group makes sure that EM instructions using register variables are
  572. handled efficiently. This group includes: local loads and
  573. stores; arithmetic, shifts and logical operations on locals and indirect locals
  574. and pointer handling, where C expressions like
  575. .I
  576. *cp++
  577. .R
  578. are handled. For such an expression there are several EM instruction
  579. sequences the front end might generate. For an integer pointer e.g.:
  580. .DS
  581. .B
  582. lol lol adp stl loi $1==$2 && $1==$4 && $3==4 && $5==4
  583. .I
  584. .DE
  585. or
  586. .DS
  587. .B
  588. lol loi lol adp stl $1==$3 && $3==$5 && $2==4 && $5==4
  589. .I
  590. .DE
  591. or perhaps even
  592. .DS
  593. .B
  594. lil lol adp stl $1==$2 && $2==$4 && $3==4
  595. .I
  596. .DE
  597. Each of these is included, since which one is generated is is up to the front
  598. end. If the front end is consistent this will mean that some of these patterns
  599. will never be used in code generation. This might seem a waist, but anyone
  600. who thinks that will certainly change his mind when his new C front end
  601. generates a different EM instruction sequence.
  602. .NH 3
  603. Groups 1 and 2: load and store instructions
  604. .PP
  605. In these groups
  606. .B lof
  607. and
  608. .B stf
  609. ,
  610. .B loi
  611. and
  612. .B sti
  613. ,
  614. .B ldf
  615. and
  616. .B sdf
  617. are the important instructions.
  618. These are the large parts in this group, especially the
  619. .B loi
  620. and
  621. .B sti
  622. instructions, because they come in three basic sizes (byte, word and long).
  623. Note that with these instructions in the MC68000 part the
  624. .I exact
  625. is omitted in front of
  626. .I regAcon
  627. and
  628. .I
  629. regAregXcon.
  630. .R
  631. This makes sure that
  632. .I t_regAcon
  633. and
  634. .I t_regAregXcon
  635. are transformed into proper tokens before they are used as addresses.
  636. .PP
  637. Also note that the
  638. .I regAregXcon
  639. token is completely left out from the
  640. \fBlof\fR, \fBstf\fR, \fBldf\fR and \fBsdf\fR
  641. instruction handling. This is because the sum of the token displacement
  642. and the offset provided in the instruction cannot be checked and is likely
  643. to exceed 8 bits. Unfortunately
  644. .I cgg
  645. does not allow the inspection of subregisters of tokens that are on the
  646. fake stack. This same problem might also occur with the
  647. .I regAcon
  648. token, but this is less likely because it
  649. uses 16-bit displacements. Besides if it would have been left out the
  650. \fBlof\fR, \fBstf\fR, \fBldf\fR and \fBsdf\fR
  651. instructions would have been handled considerably less efficient.
  652. .NH 3
  653. Groups 3 and 4: integer and unsigned arithmetic
  654. .PP
  655. EM instruction
  656. .B sbi
  657. also works with address registers, because the
  658. .B cmp
  659. instruction in group 12 is replaced by \fBsbi 4\fR.
  660. .PP
  661. For the MC68000 \fBmli\fR, \fBmlu\fR, \fBdvi\fR, \fBdvu\fR, \fBrmi\fR
  662. and \fBrmu\fR are handled
  663. by library routines. This is because the MC68000 has only 16-bit multiplications
  664. and divisions.
  665. .PP
  666. The MC68020 does have 32-bit multiplications and divisions, but for the
  667. .B rmi
  668. and
  669. .B rmu
  670. EM instructions peculiar things happen anyway: they generate the
  671. .I killreg
  672. instruction. This is necessary because the data register that
  673. first held the dividend now holds the quotient; the original contents are
  674. destroyed without
  675. .I cg
  676. knowing about it (the destruction of the two registers that make up the
  677. .I DREG_pair
  678. token couldn't be noted in the instructions part of the table).
  679. To let
  680. .I cg
  681. know that these contents are destroyed, we have to use this `pseudo instruction'
  682. from lack of a better solution.
  683. .NH 3
  684. Group 5: floating point arithmetic
  685. .PP
  686. Since floating point arithmetic is not implemented traps will be generated here.
  687. .NH 3
  688. Group 6: pointer arithmetic
  689. .PP
  690. This also is a very important group, along with groups 1 and 2. The MC68020
  691. has many different addressing modes and if possible they should be used in
  692. the generation of assembly language.
  693. .PP
  694. The
  695. .I regX
  696. token is generated here too. It is meant to make efficient use of the
  697. MC68020 possibility of scaling index registers.
  698. .PP
  699. Note that I would have liked one extra pattern to handle C-statements
  700. like
  701. .DS
  702. .I
  703. pointer += expr ? constant1 : constant2;
  704. .R
  705. .DE
  706. efficiently. This pattern would have looked like:
  707. .DS
  708. pat ads
  709. with const
  710. leaving adp %1.num
  711. .DE
  712. but when
  713. .I cg
  714. is coming to the EM replacement part, the constant has already been removed
  715. from the fake stack, causing
  716. .I %1.num
  717. to have a wrong value.
  718. .NH 3
  719. Group 9: logical instructions
  720. .PP
  721. The EM instructions \fBand\fR,
  722. .B ior
  723. and
  724. .B xor
  725. are so much alike that procedures can be used here, except for the
  726. .B
  727. xor $1==4
  728. .R
  729. instruction, because the MC68000
  730. .I eor
  731. instruction does not allow as many kinds of operands as
  732. .I and
  733. and
  734. .I
  735. or.
  736. .R
  737. .NH 3
  738. Group 11: arrays
  739. .PP
  740. This group also tries to make efficient use of the available addressing modes,
  741. but it leaves the actual work to group 6 mentioned above.
  742. .PP
  743. The
  744. .I regX
  745. token is also generated here. In this group this token is very useful for
  746. handling array instructions for arrays with one, two, four or eight byte
  747. elements; the array index goes into the index register, which can then
  748. be scaled appropriately. An offset is used when the
  749. first array element has an index other than zero.
  750. .PP
  751. I would have liked some extra patterns here too but they won't work
  752. for the same reasons as explained in the discussion of group 6.
  753. .NH 3
  754. Group 14: procedure calls instructions
  755. .PP
  756. The function return area consists of registers @ D sub 0 @ and @ D sub 1 @.
  757. .NH 3
  758. Group 15: miscellaneous instructions
  759. .PP
  760. In many cases here library routines are called. These will be discussed
  761. later.
  762. .PP
  763. Two special EM instructions are included here: \fBdch\fR, and \fBlpb\fR.
  764. I don't know when they are generated by a front end, but these
  765. instructions were also in the back end table for the PDP. In the PDP table
  766. these instructions were replaced by
  767. .B
  768. loi 4
  769. .R
  770. and
  771. .B
  772. adp 8
  773. .R
  774. respectively. I included them both, since they couldn't do any harm.
  775. .NH 3
  776. Extra group: optimalization
  777. .PP
  778. This group is handling EM patterns with more than one instruction. This group
  779. is not absolutely necessary but it makes the generation of code
  780. more efficient. Among the things that are handled here are: arithmetic and
  781. logical operations on locals, externals and indirect locals; shifting
  782. of locals, externals and indirect locals by one; some pointer arithmetic; tests
  783. in combination with logical and's and or's or with branches. Finally
  784. there are sixteen patterns about divisions that could be handled more
  785. efficiently by right shifts and which I think should be handled by the
  786. peephole optimizer (since it also handles
  787. the same patterns with multiplication).
  788. .NH
  789. The library routines
  790. .PP
  791. The table is supplied with two separate libraries: one for the MC68000 and one
  792. for the MC68020. The MC68000 uses a couple more routines than the MC68020
  793. because it doesn't have 32-bit division and multiplication.
  794. .PP
  795. The routines that need to pop their operands first store their return address.
  796. Routines that need other register besides @ D sub 0 @-@ D sub 2 @ and @ A sub 0 @-@ A sub 1 @ first store
  797. the original contents of those registers. @ D sub 0 @-@ D sub 2 @ and @ A sub 0 @-@ A sub 1 @ do not have
  798. to be saved because if they contain anything useful, their contents
  799. are pushed on the stack before the routine is called.
  800. .PP
  801. The
  802. .I .trp
  803. routine just prints a message stating the trap number and exits (except
  804. of course when that particular trap number is masked). Usually higher
  805. level languages use their own trap handling routines.
  806. .PP
  807. The
  808. .I .mon
  809. routine doesn't do anything useful at all. It just prints a message stating that
  810. the specified system call is not implemented and then exits. Front ends
  811. usually generate calls to special routines rather than the EM
  812. instruction \fBmon\fR.
  813. These routines have to be supplied in another library. They
  814. may be system dependent (e.g. the MC68000 machine this table was tested on
  815. first moves the parameters to registers, then moves the system call number
  816. to @ D sub 0 @ and then executes
  817. .I
  818. trap #0,
  819. .R
  820. whereas the MC68020 machine this table was tested on required the parameters
  821. to be on the stack rather than in registers). Therefor this library is not
  822. discussed here.
  823. .PP
  824. The
  825. .I .printf
  826. routine is included for EM diagnostic messages. It can print strings using %s,
  827. 16-bit decimal numbers using %d and 32-bit hexadecimal numbers using %x.
  828. .PP
  829. The
  830. .I .strhp
  831. routine stores a new EM heap pointer, and sometimes it needs to allocate more
  832. heap space. This is done by calling the system call routine \fI_brk\fR.
  833. Chunks of 1K bytes are allocated, but this can easily be changed into
  834. larger or smaller chunks.
  835. .PP
  836. The MC68000 library also contains a routine to handle the EM instruction \fBrck\fR.
  837. The MC68020 has an instruction
  838. .I cmp2
  839. that is specially meant for range checking so the MC68020 library can do without
  840. that routine.
  841. .PP
  842. The MC68000 library has two multiplication routines, one for unsigned and the other
  843. for signed multiplication. The one for signed multiplication
  844. first tests the sizes of the operands, to see if it can perform
  845. the 16 bit machine instruction instead of the routine. If not, it considers
  846. it's two operands being two digit numbers in a 65535-radix system. It
  847. uses the 16-bit unsigned multiply instruction
  848. .I mulu
  849. three times (it does not calculate the high order result),
  850. and adds up the intermediary results the proper way. The signed
  851. multiplication routine calculates the sign of the result, calculates
  852. the result as it it were an unsigned multiplication, and
  853. adjusts the sign of the result. Here testing
  854. the operands for there sizes would be less simple, because the operands
  855. are signeds; so that is not done here.
  856. .PP
  857. The MC68000 library also has two division routines. The routine for unsigned
  858. division uses the popular algorithm, where the divisor is shifted out and
  859. the quotient shifted in. The signed division routine calculates the sign of
  860. both the quotient and the remainder, calls the unsigned division routine
  861. and adjusts the signs for the quotient and the remainder.
  862. .PP
  863. The
  864. .I .nop
  865. routine is included for testing purposes. This routine prints the line
  866. number and the value in the stack pointer. Calls to this routine
  867. are generated by the EM instruction \fBnop\fR, which is ordinarily
  868. left out by the peephole optimizer.
  869. .NH
  870. Testing the table
  871. .PP
  872. There are special test programs available for testing back end tables.
  873. First there is the EM test set, which tests most EM instructions, making
  874. good use of the
  875. .B nop
  876. instruction. Then there are the Pascal and C test programs. The Pascal
  877. test programs report errors, which makes it relatively easy
  878. to find out what was wrong in the table. The C test programs just
  879. generate some output, which then has to be compared to the expected
  880. output. Differences are
  881. not only caused by errors but also e.g. by the use of four
  882. byte integers and unsigneds (which this table does),
  883. the use of signed characters
  884. instead of unsigned characters (the C front end I used generated signed
  885. characters) or because the back end
  886. does not support floating point.
  887. These differences have to be `filtered out' to reveal
  888. the differences caused by actual errors in the back end table.
  889. These errors then have to be found out by examining the assembly code, for
  890. no proper diagnostic messages are generated.
  891. .PP
  892. After these three basic tests there still remain a number of patterns that
  893. haven't been tested yet. Fortunately
  894. .I cgg
  895. offers the possibility of generating a special
  896. .I cg
  897. that can print a list of patterns that haven't been used in
  898. code generation yet.
  899. For these patterns the table writer has to write his own test programs.
  900. This may complicate things a bit because errors may now be caused by
  901. errors in the back end table as well as errors in the test programs.
  902. The latter happened quite often to me, because I found EM
  903. to be an uncomfortable programming language (of course it isn't meant to
  904. be a programming language, but an intermediary language).
  905. .PP
  906. There still remain a couple of patterns in this table that haven't been tested
  907. yet. However these patterns all have very similar cases that have been
  908. tested (an example of this is mentioned in the section on group 0
  909. of the patterns section of the table). Some patterns have to
  910. do with floating point numbers. These EM instructions all generate
  911. traps, so they didn't all have to be tested. The two instructions
  912. .B dch
  913. and
  914. .B lpb
  915. haven't been tested in this table, but since they only use EM replacement
  916. and they have been tested in the PDP back end table, these two should
  917. be all right.
  918. .NH
  919. Performance of the back end
  920. .PP
  921. To test the performance of the back end I gathered a couple of
  922. C programs and compiled them on the machines I used to test the back ends on.
  923. I compiled them using the C compiler that was available there and
  924. I also compiled them using the back end. I then compared the sizes
  925. of the text segments in the object files.
  926. The final results of these comparisons are in fig. 1 and fig. 2.
  927. .KF
  928. .TS
  929. center box;
  930. cfI s s s s s
  931. c s s s s s
  932. c c | c s | c s
  933. c c | c s | c s
  934. c | c | c c | c c
  935. l | n | n n | n n.
  936. Differences in text segment sizes for the MC68000
  937. parts of the back end compiled by itself
  938. _
  939. original old m68k4 new MC68000
  940. compiler (100%) back end back end
  941. _
  942. name size size perc. size perc.
  943. _
  944. codegen.c 13892 16224 116.7% 12860 92.5%
  945. compute.c 4340 4502 103.7% 4530 104.3%
  946. equiv.c 680 662 97.3% 598 87.9%
  947. fillem.c 8016 7304 91.1% 6880 85.8%
  948. gencode.c 1356 1194 88.0% 1130 83.3%
  949. glosym.c 224 202 90.1% 190 84.8%
  950. main.c 732 672 91.8% 634 86.6%
  951. move.c 1876 1526 81.3% 1410 75.1%
  952. nextem.c 1288 1594 123.7% 1192 92.5%
  953. reg.c 1076 1014 94.2% 916 85.1%
  954. regvar.c 1352 1188 87.8% 1150 85.0%
  955. salloc.c 1240 1100 88.7% 1024 82.5%
  956. state.c 628 600 95.5% 532 84.7%
  957. subr.c 6948 6382 91.8% 5680 81.7%
  958. =
  959. averages 2939 3155 95.8% 2766 86.6%
  960. .TE
  961. .DS C
  962. fig 1.
  963. .DE
  964. .KE
  965. .KF
  966. .TS
  967. center box;
  968. cfI s s s
  969. cfI s s s
  970. c s s s
  971. c s s s
  972. c c | c s
  973. c c | c s
  974. c | c | c c
  975. l | n | n n.
  976. Differences in text segment sizes
  977. for the MC68020
  978. parts of the back end
  979. compiled by itself
  980. _
  981. original MC68020
  982. compiler (100%) back end
  983. _
  984. name size size perc.
  985. _
  986. codegen.c 12608 12134 96.2%
  987. compute.c 4624 4416 95.5%
  988. equiv.c 572 504 88.1%
  989. fillem.c 7780 6976 89.6%
  990. gencode.c 1320 1086 82.2%
  991. glosym.c 228 182 79.8%
  992. main.c 736 596 80.9%
  993. move.c 1392 1280 91.9%
  994. nextem.c 1176 1066 90.6%
  995. reg.c 1052 836 79.4%
  996. regvar.c 1196 968 80.9%
  997. salloc.c 1200 932 77.6%
  998. state.c 580 528 91.0%
  999. subr.c 6136 5268 85.8%
  1000. =
  1001. averages 2900 2627 86.4%
  1002. .TE
  1003. .DS C
  1004. fig 2.
  1005. .DE
  1006. .KE
  1007. Fig. 1 also includes results of an old m68k4 back end (a back end
  1008. for the MC68000 with four byte word and pointersize). The table for
  1009. this back end was given to me as an example, but I thought it didn't make
  1010. good use of the MC68000's addressing capabilities, it hardly did any
  1011. optimalization, and it sometimes even
  1012. generated code that the assembler would not swallow.
  1013. This was sufficient reason for me to write a completely new table.
  1014. .PP
  1015. The results from the table may not be taken too seriously. The sizes measured
  1016. are the sizes of the text segments of the user programs, i.e. without the
  1017. inclusion of library routines. Of course these segments do contain calls
  1018. to these routines. Another thing is that the
  1019. .I rom
  1020. segment may be included in the text segment (this is why the
  1021. results for the MC68000 for
  1022. .I compute.c
  1023. look so bad).
  1024. .PP
  1025. Some other things must be said about these results.
  1026. The quality of EM code
  1027. generated by the C front end is certainly not optimal. The front end
  1028. uses temporary locals (extra locals that are used to evaluate expressions)
  1029. far too quickly: for a simple C expression like
  1030. .DS
  1031. .I
  1032. *(pointer) += constant
  1033. .R
  1034. .DE
  1035. where
  1036. .I pointer
  1037. is a register variable, the C front end generates (for obscure reasons)
  1038. a temporary local that holds the contents of \fIpointer\fR. This way
  1039. the pattern for
  1040. .DS
  1041. .B
  1042. loc lil adi sil $2==$4 && $3==4
  1043. .R
  1044. .DE
  1045. for register variables is not used and longer, less efficient
  1046. code is generated. But even in spite of this, the back end seems to
  1047. generate rather compact code.
  1048. .NH
  1049. Some timing results
  1050. .PP
  1051. In order to measure the performance of the code generated by the back end
  1052. some timing tests were done. The reason I chose these particular tests is
  1053. that they were also done for many other back ends; the reader can compare
  1054. the results if he so wishes (of course comparing the results only
  1055. show a global difference in speed of the various machines; it doesn't
  1056. show whether some back end generates relatively better code than another).
  1057. .PP
  1058. On the MC68000 machine the statements were executed one million times.
  1059. On the MC68020 machine the statements had to be executed four million times
  1060. because this machine was so fast that timing results would be very
  1061. unreliable if the statements were executed only one million times.
  1062. .PP
  1063. For testing I used the following C test program:
  1064. .DS
  1065. .I
  1066. main()
  1067. {
  1068. int i, j, ...
  1069. ...
  1070. for (i=0; i<1000; i++)
  1071. for (j=0; j<1000; j++)
  1072. STATEMENT;
  1073. }
  1074. .R
  1075. .DE
  1076. where
  1077. .I STATEMENT
  1078. is any of the test statements or the empty statement. For the MC68020
  1079. tests I used 2000 instead of 1000.
  1080. The results of the test with the empty statement were used to calculate
  1081. the execution times of the other test statements.
  1082. .PP
  1083. Figures 3 and 4 show many results. For each machine actually two tests were
  1084. done: one with register variables, and the other without them.
  1085. I noticed that the original C compilers on both machines did not generate
  1086. the use of register variables, unless specifically requested. The
  1087. back end uses register variables when and where they are profitable, even
  1088. if the user did not ask for them.
  1089. .KF
  1090. .TS
  1091. center box;
  1092. cfI s s s s
  1093. c s s s s
  1094. c | c s | c s
  1095. cw(1.5i) | c c | c c
  1096. c | c c | c c
  1097. lp-2fI | n n | n n.
  1098. timing results for the MC68000
  1099. times in @ mu @seconds
  1100. _
  1101. test statement without register variables with register variables
  1102. _
  1103. original new MC68000 original new MC68000
  1104. C compiler back end C compiler back end
  1105. _
  1106. int1=0; 2.8 2.7 0.5 0.5
  1107. int1=int2-1; 4.1 4.1 1.3 1.3
  1108. int1=int1+1; 4.1 4.1 1.3 1.3
  1109. int1=int2*int3; 40.0 40.5 36.2 36.8
  1110. T{
  1111. int1=(int2<0);
  1112. \/*true*/
  1113. T} 5.5 7.3 2.0 4.5
  1114. T{
  1115. int1=(int2<0);
  1116. \/*false*/
  1117. T} 4.7 8.5 2.8 5.6
  1118. T{
  1119. int1=(int2<3);
  1120. \/*true*/
  1121. T} 6.2 7.7 2.6 5.4
  1122. T{
  1123. int1=(int2<3);
  1124. \/*false*/
  1125. T} 5.4 8.9 3.6 6.5
  1126. T{
  1127. .na
  1128. int1=((int2>3)||(int2<3));
  1129. \/* true || false */
  1130. T} 6.0 7.8 3.4 5.4
  1131. T{
  1132. .na
  1133. int1=((int2>3)||(int2<3));
  1134. \/* false || true */
  1135. T} 9.1 10.2 5.7 7.1
  1136. T{
  1137. .na
  1138. switch (int1) {
  1139. case 1: int1=0; break;
  1140. case 2: int1=1; break;
  1141. }
  1142. T} 6.3 17.8 5.3 14.0
  1143. T{
  1144. .na
  1145. if (int1=0) int2=3;
  1146. \/*true*/
  1147. T} 5.1 4.7 1.3 1.3
  1148. T{
  1149. .na
  1150. if (int1=0) int2=3;
  1151. \/*false*/
  1152. T} 2.2 2.1 1.9 1.1
  1153. while (int1>0) int1=int1-1; 2.2 2.1 1.1 1.1
  1154. int1=a[int2]; 6.8 6.7 4.0 3.1
  1155. p3(int1); 14.3 11.1 13.4 10.0
  1156. int1=f(int2); 17.7 14.5 14.8 11.7
  1157. s.overhead=5400; 2.8 2.7 2.9 2.7
  1158. .TE
  1159. .DS C
  1160. Fig. 3
  1161. .DE
  1162. .KE
  1163. .KF
  1164. .TS
  1165. center box;
  1166. cfI s s s s
  1167. c s s s s
  1168. c | c s | c s
  1169. cw(1.5i) | c c | c c
  1170. c | c c | c c
  1171. lp-2fI | n n | n n.
  1172. timing results for the MC68020
  1173. times in @ mu @seconds
  1174. _
  1175. test statement without register variables with register variables
  1176. _
  1177. original new MC68020 original new MC68020
  1178. C compiler back end C compiler back end
  1179. _
  1180. int1=0; .25 .25 .15 .15
  1181. int1=int2-1; 1.3 1.3 .38 .38
  1182. int1=int1+1; 1.2 .90 .38 .15
  1183. int1=int2*int3; 4.4 4.2 3.0 3.1
  1184. T{
  1185. int1=(int2<0);
  1186. \/*true*/
  1187. T} 1.6 2.7 1.1 2.3
  1188. T{
  1189. int1=(int2<0);
  1190. \/*false*/
  1191. T} 1.9 2.9 .80 2.1
  1192. T{
  1193. int1=(int2<3);
  1194. \/*true*/
  1195. T} 1.7 2.8 1.2 2.6
  1196. T{
  1197. int1=(int2<3);
  1198. \/*false*/
  1199. T} 2.1 3.0 .85 2.3
  1200. T{
  1201. .na
  1202. int1=((int2>3)||(int2<3));
  1203. \/* true || false */
  1204. T} 2.1 3.1 1.2 2.5
  1205. T{
  1206. .na
  1207. int1=((int2>3)||(int2<3));
  1208. \/* false || true */
  1209. T} 3.4 4.2 1.8 3.2
  1210. T{
  1211. .na
  1212. switch (int1) {
  1213. case 1: int1=0; break;
  1214. case 2: int1=1; break;
  1215. }
  1216. T} 2.7 8.0 2.0 6.9
  1217. T{
  1218. .na
  1219. if (int1=0) int2=3;
  1220. \/*true*/
  1221. T} 1.2 1.3 .63 .63
  1222. T{
  1223. .na
  1224. if (int1=0) int2=3;
  1225. \/*false*/
  1226. T} 1.7 1.6 .50 .53
  1227. while (int1>0) int1=int1-1; 1.2 1.3 .55 .53
  1228. int1=a[int2]; 1.8 1.8 1.0 1.0
  1229. p3(int1); 14.8 5.5 14.1 5.0
  1230. int1=f(int2); 16.3 6.6 15.2 5.9
  1231. s.overhead=5400; .48 .48 .50 .50
  1232. .TE
  1233. .DS C
  1234. Fig. 4
  1235. .DE
  1236. .KE
  1237. .PP
  1238. The reader may have noticed that on both machines the back end seems
  1239. to generate considerably slower code for tests where a `condition' is
  1240. used in the rhs of an assignment statement. This is in fact not true: it is
  1241. the front end that generates bad code. Two examples: for the C statement
  1242. .DS
  1243. .I
  1244. int1 = (int2 < 0);
  1245. .R
  1246. .DE
  1247. the front end generates the following code for the rhs (I
  1248. used arbitrary labels):
  1249. .DS
  1250. .B
  1251. lol -16
  1252. zlt *10
  1253. loc 0
  1254. bra *11
  1255. 10
  1256. loc 1
  1257. 11
  1258. .R
  1259. .DE
  1260. while in this case (to my opinion) it should have generated
  1261. .DS
  1262. .B
  1263. lol -16
  1264. tlt
  1265. .R
  1266. .DE
  1267. which is much shorter. Another example: for the C statement
  1268. .DS
  1269. .I
  1270. int1 = (int2 < 3);
  1271. .B
  1272. .DE
  1273. the front end generates for the rhs
  1274. .DS
  1275. .B
  1276. lol -16
  1277. loc 3
  1278. blt *10
  1279. loc 0
  1280. bra *11
  1281. 10
  1282. loc 1
  1283. 11
  1284. .R
  1285. .DE
  1286. while a much better translation would be
  1287. .DS
  1288. .B
  1289. lol -16
  1290. loc 3
  1291. cmi 4
  1292. tlt
  1293. .R
  1294. .DE
  1295. .PP
  1296. Another statement that the back end seems to generate slower code for is
  1297. the C switch statement. This is true, but it is also caused by
  1298. the way these things are done in EM. EM uses the
  1299. .B csa
  1300. or
  1301. .B csb
  1302. instruction, and for these two I had to use library routines. On larger
  1303. switch statements the
  1304. .I .csa
  1305. routine will perform relatively better.
  1306. .PP
  1307. The back end generates considerably faster code for procedure and function
  1308. calls, especially in the MC68020 case, and also for the C statement
  1309. .DS
  1310. .I
  1311. int1 = int1 + 1;
  1312. .R
  1313. .DE
  1314. The original C compilers use the same method for this instruction
  1315. as for
  1316. .DS
  1317. .I
  1318. int1 = int2 - 1;
  1319. .R
  1320. .DE
  1321. they perform the addition in a scratch register, and then store the
  1322. result. For the former C statement this is not necessary, because
  1323. the MC68000 and MC68020 have an instruction that can add constants
  1324. to almost anything (in this case: to locals). The MC68000 and MC68020
  1325. back ends do use this instruction.
  1326. .NH
  1327. Some final remarks
  1328. .PP
  1329. As mentioned a few times before, the C front end compiler does not
  1330. generate optimal code and as a consequence of this the
  1331. back end does not always generate optimal code. This is especially
  1332. the case with temporary locals, which the front end generates much
  1333. too quickly, and also with conditional expressions that are
  1334. used in the rhs of an assignment statement (fortunately this is not
  1335. needed so much).
  1336. .PP
  1337. If
  1338. .I cgg
  1339. would have been able to accept operands separated by any character
  1340. instead of just by commas (in the instruction definitions part),
  1341. I wouldn't have had the need of the
  1342. .I killreg
  1343. pseudo instruction. It would also be handy to have
  1344. .I cgg
  1345. accept all normal C operators. At the moment
  1346. .I cgg
  1347. does not accept binary ands, ors and exors, even though in [4]
  1348. it is stated that
  1349. .I cgg
  1350. does accept all normal C operators. As it happens I did not need the
  1351. binary operators, but at some time in developing the table I thought
  1352. I did.
  1353. .PP
  1354. I would also like
  1355. .I cg
  1356. to do more with the condition codes information that is supplied with
  1357. each instruction in the instruction definitions section of the table.
  1358. Sometimes
  1359. .I cg
  1360. generates test instructions which actually were not necessary. This
  1361. of course causes the generated
  1362. programs to be slightly larger and slightly slower.
  1363. .PP
  1364. In spite of the few minor shortcomings mentioned above I found
  1365. .I cgg
  1366. a very comfortable tool to use.
  1367. .SH
  1368. References
  1369. .PP
  1370. .IP [1]
  1371. T. B. Steel Jr.,
  1372. .I
  1373. UNCOL: The myth and the Fact,
  1374. .R
  1375. in Ann. Rev. Auto. Prog.,
  1376. R. Goodman (ed.), Vol. 2 (1969), pp 325 - 344
  1377. .IP [2]
  1378. A. S. Tanenbaum, H. van Staveren, E. G. Keizer, J. W. Stevenson,
  1379. .I
  1380. A practical toolkit for making portable compilers,
  1381. .R
  1382. Informatica Report 74, Vrije Universiteit, Amsterdam, 1983
  1383. .IP [3]
  1384. A. S. Tanenbaum, H. van Staveren, E. G. Keizer, J. W. Stevenson,
  1385. .I
  1386. Description of an experimental machine architecture for use with
  1387. block structured languages,
  1388. .R
  1389. Informatica Report 81, Vrije Universiteit, Amsterdam, 1983
  1390. .IP [4]
  1391. H. van Staveren
  1392. .I
  1393. The table driven code generator from the Amsterdam Compiler Kit,
  1394. Second Revised Edition,
  1395. .R
  1396. Vrije Universiteit, Amsterdam
  1397. .IP [5]
  1398. .I
  1399. MC68020 32-bit Microprocessor User's Manual,
  1400. .R
  1401. Second Edition,
  1402. Motorola Inc., 1985, 1984
  1403. .IP [6]
  1404. .I
  1405. MC68000 16-bit Microprocessor User's Manual,
  1406. Preliminary,
  1407. .R
  1408. Motorola Inc., 1979