6500.doc 42 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893
  1. . \" $Id$"
  2. .RP
  3. .ND Dec 1984
  4. .TL
  5. .B
  6. A backend table for the 6500 microprocessor
  7. .R
  8. .AU
  9. Jan van Dalen
  10. .AB
  11. The backend table is part of the Amsterdam Compiler Kit (ACK).
  12. It translates the intermediate language family EM to a machine
  13. code for the MCS6500 microprocessor family.
  14. .AE
  15. .bp
  16. .DS C
  17. .B
  18. THE MCS6500 MICROPROCESSOR.
  19. .R
  20. .DE
  21. .NH 0
  22. Introduction
  23. .PP
  24. Why a back end table for the MCS6500 microprocessor family.
  25. Although the MCS6500 microprocessor family has an simple
  26. instruction set and internal structure, it is used in a
  27. variety of microcomputers and homecomputers.
  28. This is because of is low cost.
  29. As an example the Apple II, a well known and width spread
  30. microprocessor, uses the MCS6502 CPU.
  31. Also the BBC homecomputer, whose popularity is growing day
  32. by day uses the MCS6502 CPU.
  33. The BBC homecomputer is based on the MCS6502 CPU although
  34. better and stronger microprocessors are available.
  35. The designers of Acorn computer Industries have probably
  36. choosen for the MCS6502 because of the amount of software
  37. available for this CPU.
  38. Since its width spreaded use, a variaty of software
  39. will be needed for it.
  40. One can think of games!!, administration programs,
  41. teaching programs, basic interpreters and other application
  42. programs.
  43. Even do it will not be possible to run the total compiler kit
  44. on a MCS6500 based computer, it is possible to write application
  45. programs in a high level language, such as Pascal or C on a
  46. minicomputer.
  47. These application programs can be tested and compiled on that
  48. minicomputer and put in a ROM (Read Only Memory), for example,
  49. cso that it an be executed by a MCS6500 CPU.
  50. The strategy of writing testprograms on a minicomputer,
  51. compile it and then execute it on a MCS6500 based
  52. microprocessor is used by the development of the back end.
  53. The minicomputer used is M68000 based one, manufactured by
  54. Bleasdale Computer Systems Ltd..
  55. The micro- or homecomputer used is a BBC microcomputer,
  56. manufactured by Acorn Computer Ltd..
  57. .NH
  58. The MOS Technology MCS6500
  59. .PP
  60. The MCS6500 is as a family of CPU devices developed by MOS
  61. Technology [1].
  62. The members of the MCS6500 family are the same chips in a
  63. different housing.
  64. The MCS6502, the big brother in the family, can handle 64k
  65. bytes of memory, while for example the MCS6504 can only handle
  66. 8k bytes of memory.
  67. This difference is due to the fact that the MCS6502 is in a
  68. 40 pins house and the MCS6504 has a 28 pins house, so less
  69. address lines are available.
  70. .bp
  71. .NH
  72. The MCS6500 CPU programmable registers
  73. .PP
  74. The MCS6500 series is based on the same chip so all have the
  75. same programmable registers.
  76. .sp 9
  77. .NH 2
  78. The accumulator A.
  79. .PP
  80. The accumulator A is the only register on which the arithmetic
  81. and logical instructions can be used.
  82. For example, the instruction ADC (add with carry) adds the
  83. contents of the accumulator A and a byte from memory or data.
  84. .NH 2
  85. The index register X.
  86. .PP
  87. As the name suggests this register can be used for some
  88. indirect addressing modes.
  89. The modes are explaned below.
  90. .NH 2
  91. The index register Y.
  92. .PP
  93. This register is, just as the index register X, used for
  94. certain indirect addressing modes.
  95. These addressing modes are different from the modes which
  96. use index register X.
  97. .NH 2
  98. The program counter PC
  99. .PP
  100. This is the only 16-bit register available.
  101. It is used to point to the next instruction to be
  102. carried out.
  103. .NH 2
  104. The stack pointer SP
  105. .PP
  106. The stack pointer is an 8-bit register, so the stack can contain
  107. at most 256 bytes.
  108. The CPU always appends 00000001 as highbyte of any stack address,
  109. which means that memory locations
  110. .B
  111. 0100
  112. .R
  113. through
  114. .B
  115. 01FF
  116. .R
  117. are permanently assigned to the stack.
  118. .sp 12
  119. .NH 2
  120. The status register
  121. .PP
  122. The status register maintains six status flags and a master
  123. interrupt control bit.
  124. .br
  125. These are the six status flags:
  126. Carry (c)
  127. Zero (z)
  128. Overflow (o)
  129. Sign (n)
  130. Decimal mode (d)
  131. Break (b)
  132. The bit (i) is the master interrupt control bit.
  133. .NH
  134. The MCS6500 memory layout.
  135. .PP
  136. In the MCS6500 memory space three area's have special meaning.
  137. These area's are:
  138. .IP 1)
  139. Top page.
  140. .IP 2)
  141. Zero page.
  142. .IP 3)
  143. The stack.
  144. .PP
  145. MCS6500 memory is divided up into pages.
  146. These pages consist 256 bytes.
  147. So in a memory address the highbyte denotes the page number
  148. and the lowbyte the offset within the page.
  149. .NH 2
  150. Top page.
  151. .PP
  152. When a MCS6500 is restared it jumps indirect via memory address
  153. .B
  154. FFFC.
  155. .R
  156. At
  157. .B
  158. FFFC
  159. .R
  160. (lowbyte) and
  161. .B
  162. FFFD
  163. .R
  164. (highbyte) there must be the address of the bootstrap subroutine.
  165. When a break instruction (BRK) occurs or an interrupt takes place,
  166. the MCS6500 jumps indirect through memory address
  167. .B
  168. FFFE.
  169. .R
  170. .B
  171. FFFE
  172. .R
  173. and
  174. .B
  175. FFFF
  176. .R
  177. thus, must contain the address of the interrupt routine.
  178. The former only goes for maskeble interrupt.
  179. There also exist a nonmaskeble interrupt.
  180. This cause the MCS6500 to jump indirect through memory address
  181. .B
  182. FFFA.
  183. .R
  184. So the top six bytes of memory are used by the operating system
  185. and therefore not available for the back end.
  186. .NH 2
  187. Zero page.
  188. .PP
  189. This page has a special meaning in the sence that addressing
  190. this page uses special opcodes.
  191. Since a page consists of 256 bytes, only one byte is needed
  192. for addressing zero page.
  193. So an instruction which uses zero page occupies two bytes.
  194. It also uses less clock cycle's while carrying out the instruction.
  195. Zero page is also needed when indirect addressing is used.
  196. This means that when indirect addressing is used, the address must
  197. reside in zero page (two consecutive bytes).
  198. In this case (the back end), zero page is used, for example
  199. to hold the local base, the second local base, the stack pointer
  200. etc.
  201. .NH 2
  202. The stack.
  203. .PP
  204. The stack is described in paragraph 3.5 about the MCS6500
  205. programmable registers.
  206. .NH
  207. The memory adressing modes
  208. .PP
  209. MCS6500 memory reference instructions use direct addressing,
  210. indexed addressing, and indirect addressing.
  211. .NH 2
  212. direct addressing.
  213. .PP
  214. Three-byte instructions use the second and third bytes of the
  215. object code to provide a direct 16-bit address:
  216. therefore, 65.536 bytes of memory can be addressed directly.
  217. The commonly used memory reference instructions also have a two-byte
  218. object code variation, where the second byte directly addresses
  219. one of the first 256 bytes.
  220. .NH 2
  221. Base page, indexed addressing.
  222. .PP
  223. In this case, the instruction has two bytes of object code.
  224. The contents of either the X or Y index registers are added to the
  225. second object code byte in order to compute a memory address.
  226. This may be illustrated as follows:
  227. .sp 15
  228. Base page, indexed addressing, as illustrated above, is
  229. wraparound - which means that there is no carry.
  230. If the sum of the index register and second object code byte contents
  231. is more than
  232. .B
  233. FF
  234. .R
  235. , the carry bit will be dicarded.
  236. This may be illustrated as follows:
  237. .sp 9
  238. .NH 2
  239. Absolute indexed addressing.
  240. .PP
  241. In this case, the contents of either the X or Y register are added
  242. to a 16-bit direct address provided by the second and third bytes
  243. of an instruction's object code.
  244. This may be illustrated as follows:
  245. .sp 10
  246. .NH 2
  247. Indirect addressing.
  248. .PP
  249. Instructions that use simple indirect addressing have three bytes of
  250. object code.
  251. The second and third object code bytes provide a 16-bit address;
  252. therefore, the indirect address can be located anywhere in
  253. memory.
  254. This is straightforward indirect addressing.
  255. .NH 3
  256. Pre-indexed indirect addressing.
  257. .PP
  258. In this case, the object code consists of two bytes and the
  259. second object code byte provides an 8-bit address.
  260. Instructions that use pre-indexed indirect addressing add the contents
  261. of the X index register and the second object code byte to access
  262. a memory location in the first 256 bytes of memory, where the
  263. indirect address will be found:
  264. .sp 18
  265. When using pre-indexed indirect addressing, once again wraparound
  266. addition is used, which means that when the X index register contents
  267. are added to the second object code byte, any carry will be discarded.
  268. Note that only the X index register can be used with pre-indexed
  269. addressing.
  270. .NH 3
  271. Post-indexed indirect addressing.
  272. .PP
  273. In this case, the object code consists of two bytes and the
  274. second object code byte provides an 8-bit address.
  275. Now the second object code byte indentifies a location
  276. in the first 256 bytes of memory where an indirect address
  277. will be found.
  278. The contents of the Y index register are added to this indirect
  279. address.
  280. This may be illustrated as follows:
  281. .sp 18
  282. Note that only the Y index register can be used with post-indexed
  283. indirect addressing.
  284. .bp
  285. .NH
  286. What the CPU has and doesn't has.
  287. .PP
  288. Although the designers of the MCS6500 CPUs family state that
  289. there is nothing very significant about the short stack (only
  290. 256 bytes) this stack caused problems for the back end.
  291. The designers say that a 256-byte stack usually is sufficient
  292. for any typical microcomputer, this is only true if the stack
  293. is used only for return addresses of the JSR (jump to
  294. subroutine) instruction.
  295. But since the EM machine is suppost to be a stack machine and
  296. high level languages need the ability of parameters and
  297. locals in there procedures and function, this short stack
  298. is unsufficiant.
  299. So an software stack is implemented in this back end, requiring two
  300. additional subroutines for stack handling.
  301. These two stack handling subroutines slow down the processing time
  302. of a program since the stack is used heavely.
  303. .PP
  304. Since parameters and locals of EM procedures are offseted
  305. from the localbase of that procedure, indirect addressing
  306. is havily used.
  307. Offsets are positive (for parameters) and negative (for
  308. local variables).
  309. As explaned before the addressing modes the MCS6500 have a
  310. post indexed indirect addressing mode.
  311. This addressing mode can only handle positive offsets.
  312. This raises a problem for accessing the local variables
  313. I have chosen for the next solution.
  314. A second local base is introduced.
  315. This second local base is the real local base subtracted by
  316. a constant BASE.
  317. In the present situation of the back end the value of BASE
  318. is 240.
  319. This means that there are 240 bytes reseved for local
  320. variables to be indirect addressed and 14 bytes for
  321. the parameters.
  322. .DS C
  323. .B
  324. THE CODE GENERATOR.
  325. .R
  326. .DE
  327. .NH 0
  328. Description of the machine table.
  329. .PP
  330. The machine description table consists of the following sections:
  331. .IP 1.
  332. The macro definitions.
  333. .IP 2.
  334. Constant definitions.
  335. .IP 3.
  336. Register definitions.
  337. .IP 4.
  338. Token definitions.
  339. .IP 5.
  340. Token expressions.
  341. .IP 6.
  342. Code rules.
  343. .IP 7.
  344. Move definitions.
  345. .IP 8.
  346. Test definitions.
  347. .IP 9.
  348. Stack definitions.
  349. .NH 2
  350. Macro definitions.
  351. .PP
  352. The macro definitions at the top of the table are expanded
  353. by the preprocessor on occurence in the rest of the table.
  354. .NH 2
  355. Constant definitions.
  356. .PP
  357. There are three constants which must be defined at first.
  358. The are:
  359. .IP EM_WSIZE: 11
  360. Number of bytes in a machine word.
  361. This is the number of bytes a simple
  362. .B
  363. loc
  364. .R
  365. instruction will put on the stack.
  366. .IP EM_PSIZE:
  367. Number of bytes in a pointer.
  368. This is the number of bytes a
  369. .B
  370. lal
  371. .R
  372. instruction will put on the stack.
  373. .IP EM_BSIZE:
  374. Number of bytes in the hole between AB and LB.
  375. The calling sequence only saves LB on the stack so this
  376. constant is equal to the pointer size.
  377. .NH 1
  378. Register definitions.
  379. .PP
  380. The only important register definition is the definition of
  381. the registerpair AX.
  382. Since the rest of the machine's registers Y, PC, ST serve
  383. special purposes, the code generator cannot use them.
  384. .NH 2
  385. Token definitions
  386. .PP
  387. There is a fake token.
  388. This token is put in the table, since the code generator generator
  389. complains if it cannot find one.
  390. .NH 2
  391. Token expression definitions.
  392. .PP
  393. The token expression is also a fake one.
  394. This token expression is put in the table, since the code generator
  395. generator complains if it cannot find one.
  396. .NH 2
  397. Code rules.
  398. .PP
  399. The code rule section is the largest section in the table.
  400. They specify EM patterns, stack patterns, code to be generated,
  401. etc.
  402. The syntax is:
  403. .IP code rule:
  404. EM pattern '|' stack pattern '|' code '|'
  405. stack replacement '|' EM replacement '|'
  406. .PP
  407. All patterns are optional, however there must be at least one
  408. pattern present.
  409. If the EM pattern is missing the rule becomes a rewriting
  410. rule or a
  411. .B
  412. coercion
  413. .R
  414. to be used when code generation cannot continue because of an
  415. invalid stack pattern.
  416. The code rules are preceeded by the word CODE:.
  417. .NH 3
  418. The EM pattern.
  419. .PP
  420. The EM pattern consists of a list of EM mnemonics followed by
  421. a boolean expression. Examples:
  422. .sp 1
  423. .br
  424. .B
  425. loe
  426. .R
  427. .sp 1
  428. will match a single
  429. .B
  430. loe
  431. .R
  432. instruction,
  433. .sp 1
  434. .br
  435. .B
  436. loc loc cif
  437. .R
  438. $1==2 && $2==8
  439. .sp 1
  440. is a pattern that will match
  441. .sp 1
  442. .br
  443. .B
  444. loc
  445. .R
  446. 2
  447. .br
  448. .B
  449. loc
  450. .R
  451. 8
  452. .br
  453. .B
  454. cif
  455. .R
  456. .sp 1
  457. and
  458. .sp 1
  459. .br
  460. .B
  461. lol
  462. inc
  463. stl
  464. .R
  465. $1==$3
  466. .sp 1
  467. will match for example
  468. .sp 1
  469. .br
  470. .B
  471. lol
  472. .R
  473. 6
  474. .br
  475. .B
  476. inc
  477. .R
  478. .br
  479. .B
  480. stl
  481. .R
  482. 6
  483. .sp 1
  484. A missing boolean expession evaluates to TRUE.
  485. .PP
  486. The code generator will match the longest EM pattern on every occasion,
  487. if two patterns of the same length match the first in the table
  488. will be chosen, while all patterns of length greater than or equal
  489. to three are considered to be of the same length.
  490. .NH 3
  491. The stack pattern.
  492. .PP
  493. The only stack pattern that can occur is R16, which means that the
  494. registerpair AX contains the word on top of the stack.
  495. If this is not the case a coersion occurs.
  496. This coersion generates a "jsr Pop", which means that the top
  497. of the stack is popped and stored in the registerpair AX.
  498. .NH 3
  499. The code part.
  500. .PP
  501. The code part consists of three parts, stack cleanup, register
  502. allocation, and code to be generated.
  503. All of these may be omitted.
  504. .NH 4
  505. Stack cleanup.
  506. .PP
  507. When generating something like a branch instruction it might be
  508. needed to empty the fake stack, that is, remove the AX registerpair.
  509. This is done by the instruction remove(ALL)
  510. .NH 4
  511. Register allocation.
  512. .PP
  513. If the machine code to be generated uses the registerpair AX,
  514. this is signaled to the code generator by the allocate(R16)
  515. instruction.
  516. If the registerpair AX resides on the fake stack, this will result
  517. in a "jsr Push", which means that the registerpair AX is pushed on
  518. the stack and will be free for further use.
  519. If registerpair AX is not on the fake stack nothing happens.
  520. .NH 4
  521. Code to be generated.
  522. .PP
  523. Code to be generated is specified as a list of items of the following
  524. kind:
  525. .IP 1)
  526. A string in double quotes("This is a string").
  527. This is copied to the codefile and a newline ('\n') is appended.
  528. Inside the string all normal C string conventions are allowed,
  529. and substitutions can be made of the following sorts.
  530. .RS
  531. .IP a)
  532. $1, $2 etc. These are the operand of the corresponding EM
  533. instructions and are printed according to there type.
  534. To put a real '$' inside the string it must be doubled ('$$').
  535. .IP b)
  536. %[1], %[2.reg], %[b.1] etc. these have there obvious meaning.
  537. If they describe a complete token (%[1]) the printformat for
  538. the token is used.
  539. If they stand fo a basic term in an expression they will be
  540. printed according to their type.
  541. To put a real '%' inside the string it must be doubled ('%%').
  542. .IP c)
  543. %( arbitrary expression %). This allows inclusion of arbitrary
  544. expressions inside strings.
  545. Usually not needed very often, so that the akward notation
  546. is not too bad.
  547. Note that %(%[1]%) is equivalent to %[1].
  548. .RE
  549. .NH 3
  550. stack replacement.
  551. .PP
  552. The stack replacement is a possibly empty list of items to be
  553. pushed on the fake stack.
  554. Three things can occur:
  555. .IP 1)
  556. %[1] is used if the registerpair AX was on the fake stack and is
  557. to be pushed back onto it.
  558. .IP 2)
  559. %[a] is used if the registerpair AX is allocated with allocate(R16)
  560. and is to be pushed onto the fake stack.
  561. .IP 3)
  562. It can also be empty.
  563. .NH 3
  564. EM replacement.
  565. .PP
  566. In exeptional cases it might be useful to leave part of the an EM
  567. pattern undone.
  568. For example, a
  569. .B
  570. sdl
  571. .R
  572. instruction might be split into two
  573. .B
  574. stl
  575. .R
  576. instructions when there is no 4-byte quantity on the stack.
  577. The EM replacement part allows one to express this.
  578. Example:
  579. .sp 1
  580. .br
  581. .B
  582. stl
  583. .R
  584. $1
  585. .B
  586. stl
  587. .R
  588. $1+2
  589. .sp 1
  590. The instructions are inserted in the stream so they can match
  591. the first part of a pattern in the next step.
  592. Note that since the code generator traverses the EM instructions
  593. in a strict linear fashion, it is impossible to let the EM
  594. replacement match later parts of a pattern.
  595. So if there is a pattern
  596. .sp 1
  597. .br
  598. .B
  599. loc
  600. stl
  601. .R
  602. $1==0
  603. .sp1
  604. and the input is
  605. .sp 1
  606. .br
  607. .B
  608. loc
  609. .R
  610. 0
  611. .B
  612. sdl
  613. .R
  614. 4
  615. .sp 1
  616. the
  617. .B
  618. loc
  619. .R
  620. 0
  621. will be processed first, then the
  622. .B
  623. sdl
  624. .R
  625. might be split into two
  626. .B
  627. stl
  628. .R
  629. 's but the pattern cannot match now.
  630. .NH 3
  631. Move definitions.
  632. .PP
  633. This definition is a fake. This definition is put in the
  634. table, since the code generator generator complains if it
  635. cannot find one.
  636. .NH 3
  637. Test definitions.
  638. .PP
  639. Test definitions aren't used by the table.
  640. .NH 3
  641. Stack definitions.
  642. .PP
  643. When the generator has to push the registerpair AX, it must
  644. know how to do so.
  645. The machine code to be generated is defined here.
  646. .NH 1
  647. Some remarks.
  648. .PP
  649. The above description of the machine table is
  650. a description of the table for the MCS6500.
  651. It uses only a part of the possibilities which the code generator
  652. generator offers.
  653. For a more precise and detailed description see [2].
  654. .DS C
  655. .B
  656. THE BACK END TABLE.
  657. .R
  658. .DE
  659. .NH 0
  660. Introduction.
  661. .PP
  662. The code rules are divided in 15 groups.
  663. These groups are:
  664. .IP 1.
  665. Load instructions.
  666. .IP 2.
  667. Store instructions.
  668. .IP 3.
  669. Integer arithmetic instructions.
  670. .IP 4.
  671. Unsigned arithmetic instructions.
  672. .IP 5.
  673. Floating point arithmetic instructions.
  674. .IP 6.
  675. Pointer arithmetic instructions.
  676. .IP 7.
  677. Increment, decrement and zero instructions.
  678. .IP 8.
  679. Convert instructions.
  680. .IP 9.
  681. Logical instructions.
  682. .IP 10.
  683. Set manipulation instructions.
  684. .IP 11.
  685. Array instructions.
  686. .IP 12.
  687. Compare instructions.
  688. .IP 13.
  689. Branch instructions.
  690. .IP 14.
  691. Procedure call instructions.
  692. .IP 15.
  693. Miscellaneous instructions.
  694. .PP
  695. From all of these groups one or two typical EM pattern will be explained
  696. in the next paragraphs.
  697. Comment is placed between /* and */ (/* This is a comment */).
  698. .NH
  699. The instructions.
  700. .NH 2
  701. The load instructions.
  702. .PP
  703. In this group a typical instruction is
  704. .B
  705. lol
  706. .R
  707. .
  708. A
  709. .B
  710. lol
  711. .R
  712. instruction pushes the word at local base + offset, where offset
  713. is the instructions argument, onto the stack.
  714. Since the MCS6500 can only offset by 256 bytes, as explaned at the
  715. memory addressing modes, there is a need for two code rules in the
  716. table.
  717. One which can offset directly and one that must explicit
  718. calculate the address of the local.
  719. .NH 3
  720. The lol instruction with indirect offsetting.
  721. .PP
  722. In this case an indirect offsetted load from the second local base
  723. is possible.
  724. The table content is:
  725. .sp 1
  726. .br
  727. .B
  728. lol
  729. .R
  730. IN($1) | |
  731. .br
  732. allocate(R16) /* allocate registerpair AX */
  733. .br
  734. "ldy #BASE+$1" /* load Y with the offset from the second
  735. .br
  736. local base */
  737. .br
  738. "lda (LBl),y" /* load indirect the lowbyte of the word */
  739. .br
  740. "tax" /* move register A to register X */
  741. .br
  742. "iny" /* increment register Y (offset) */
  743. .br
  744. "lda (LBl),y" /* load indirect the highbyte of the word */
  745. .br
  746. | %[a] | | /* push the word onto the fake stack */
  747. .NH 3
  748. The lol instruction whose offset is to big.
  749. .PP
  750. In this case, the library subroutine "Lol" is used.
  751. This subroutine expects the offset in registerpair AX, then
  752. calculates the address of the local or parameter, and loads
  753. it into registerpair AX.
  754. The table content is:
  755. .sp 1
  756. .br
  757. .B
  758. lol
  759. .R
  760. | |
  761. .br
  762. allocate(R16) /* allocate registerpair AX */
  763. .br
  764. "lda #[$1].h" /* load highbyte of offset into register A */
  765. .br
  766. "ldx #[$1].l" /* load lowbyte of offset into register X */
  767. .br
  768. "jsr Lol" /* perform the subroutine */
  769. .br
  770. | %[a] | | /* push word onto the fake stack */
  771. .NH 2
  772. The store instructions.
  773. .PP
  774. In this group a typical instruction is
  775. .B
  776. stl.
  777. .R
  778. A
  779. .B
  780. stl
  781. .R
  782. instruction poppes a word from the stack and stores it in the word
  783. at local base + offset, where offset is the instructions argument.
  784. Here also is the need for two code rules in the table as a result
  785. of the offset limits.
  786. .NH 3
  787. The stl instruction with indirect offsetting.
  788. .PP
  789. In this case it an indirect offsetted store from the second local
  790. base is possible.
  791. The table content is:
  792. .sp 1
  793. .br
  794. .B
  795. stl
  796. .R
  797. IN($1) | R16 | /* expect registerpair AX on top of the
  798. .br
  799. fake stack */
  800. .br
  801. "ldy #BASE+1+$1" /* load Y with the offset from the
  802. .br
  803. second local base */
  804. .br
  805. "sta (LBl),y" /* store the highbyte of the word from A */
  806. .br
  807. "txa" /* move register X to register A */
  808. .br
  809. "dey" /* decrement offset */
  810. .br
  811. "sta (LBl),y" /* store the lowbyte of the word from A */
  812. .br
  813. | | |
  814. .NH 3
  815. The stl instruction whose offset is to big.
  816. .PP
  817. In this case the library subroutine 'Stl' is used.
  818. This subroutine expects the offset in registerpair AX, then
  819. calculates the address, poppes the word stores it at its place.
  820. The table content is:
  821. .sp 1
  822. .br
  823. .B
  824. stl
  825. .R
  826. | |
  827. .br
  828. allocate(R16) /* allocate registerpair AX */
  829. .br
  830. "lda #[$1].h" /* load highbyte of offset in register A */
  831. .br
  832. "ldx #[$1].l" /* load lowbyte of offset in register X */
  833. .br
  834. "jsr Stl" /* perform the subroutine */
  835. .br
  836. | | |
  837. .NH 2
  838. Integer arithmetic instructions.
  839. .PP
  840. In this group typical instructions are
  841. .B
  842. adi
  843. .R
  844. and
  845. .B
  846. mli.
  847. .R
  848. These instructions, in this table, are implemented for 2-byte
  849. and 4-byte integers.
  850. The only arithmetic instructions available on the MCS6500 are
  851. the ADC (add with carry), and SBC (subtract with not(carry)).
  852. Not(carry) here means that in a subtraction, the one's complement
  853. of the carry is taken.
  854. The absence of multiply and division instructions forces the
  855. use of subroutines to handle these cases.
  856. Because there are no registers left to perform on the multiply
  857. and division, zero page is used here.
  858. The 4-byte integer arithmetic is implemented, because in C there
  859. exists the integer type long.
  860. A user is freely to use the type long, but will pay in performance.
  861. .NH 3
  862. The adi instruction.
  863. .PP
  864. In case of the
  865. .B
  866. adi
  867. .R
  868. 2 (and
  869. .B
  870. sbi
  871. .R
  872. 2) instruction there are many EM
  873. patterns, so that the instruction can be performed in line in
  874. most cases.
  875. For the worst case there exists a subroutine in the library
  876. which deals with the EM instruction.
  877. In case of a
  878. .B
  879. adi
  880. .R
  881. 4 (or
  882. .B
  883. sbi
  884. .R
  885. 4) there only is a subroutine to deal with it.
  886. A table content is:
  887. .sp 1
  888. .br
  889. .B
  890. lol lol adi
  891. .R
  892. (IN($1) && IN($2) && $3==2) | | /* is it in range */
  893. .br
  894. allocate(R16) /* allocate registerpair AX */
  895. .br
  896. "ldy #BASE+$1+1" /* load Y with offset for first operand */
  897. .br
  898. "lda (LBl),y" /* load indirect highbyte first operand */
  899. .br
  900. "pha" /* save highbyte first operand on hard_stack */
  901. .br
  902. "dey" /* decrement offset first operand */
  903. .br
  904. "lda (LBl),y" /* load indirect lowbyte first operand */
  905. .br
  906. "ldy #BASE+$2" /* load Y with offset for second operand */
  907. .br
  908. "clc" /* clear carry for addition */
  909. .br
  910. "adc (LBl),y" /* add the lowbytes of the operands */
  911. .br
  912. "tax" /* store lowbyte of result in place */
  913. .br
  914. "iny" /* increment offset second operand */
  915. .br
  916. "pla" /* get highbyte first operand */
  917. .br
  918. "adc (LBl),y" /* add the highbytes of the operands */
  919. .br
  920. | %[a] | | /* push the result onto the fake stack */
  921. .NH 3
  922. The mli instruction.
  923. .PP
  924. The
  925. .B
  926. mli
  927. .R
  928. 2 instruction uses most the subroutine 'Mlinp'.
  929. This subroutine expects the multiplicand in zero page
  930. at locations ARTH, ARTH+1, while the multiplier is in zero
  931. page locations ARTH+2, ARTH+3.
  932. For a description of the algorithms used for multiplication and
  933. division, see [3].
  934. A table content is:
  935. .sp 1
  936. .br
  937. .B
  938. lol lol mli
  939. .R
  940. (IN($1) && IN($2) && $3==2) | |
  941. .br
  942. allocate(R16) /* allocate registerpair AX */
  943. .br
  944. "ldy #BASE+$1" /* load Y with offset of multiplicand */
  945. .br
  946. "lda (LBl),y" /* load indirect lowbyte of multiplicand */
  947. .br
  948. "sta ARTH" /* store lowbyte in zero page */
  949. .br
  950. "iny" /* increment offset of multiplicand */
  951. .br
  952. "lda (LBl),y" /* load indirect highbyte of multiplicand */
  953. .br
  954. "sta ARTH+1" /* store highbyte in zero page */
  955. .br
  956. "ldy #BASE+$2" /* load Y with offset of multiplier */
  957. .br
  958. "lda (LBl),y" /* load indirect lowbyte of multiplier */
  959. .br
  960. "sta ARTH+2" /* store lowbyte in zero page */
  961. .br
  962. "iny" /* increment offset of multiplier */
  963. .br
  964. "lda (LBl),y" /* load indirect highbyte of multiplier */
  965. .br
  966. "sta ARTH+3" /* store highbyte in zero page */
  967. .br
  968. "jsr Mlinp" /* perform the multiply */
  969. .br
  970. | %[a] | | /* push result onto fake stack */
  971. .NH 2
  972. The unsgned arithmetic instructions.
  973. .PP
  974. Since unsigned addition an subtraction is performed in the same way
  975. as signed addition and subtraction, these cases are dealt with by
  976. an EM replacement.
  977. For mutiplication and division there are special subroutines.
  978. .NH 3
  979. Unsigned addition.
  980. .PP
  981. This is an example of the EM replacement strategy.
  982. .sp 1
  983. .br
  984. .B
  985. lol lol adu
  986. .R
  987. | | | |
  988. .B
  989. lol
  990. .R
  991. $1
  992. .B
  993. lol
  994. .R
  995. $2
  996. .B
  997. adi
  998. .R
  999. $3 |
  1000. .NH 2
  1001. Floating point arithmetic.
  1002. .PP
  1003. Floating point arithmetic isn't implemented in this table.
  1004. .NH 2
  1005. Pointer arithmetic instructions.
  1006. .PP
  1007. A typical pointer arithmetic instruction is
  1008. .B
  1009. adp
  1010. .R
  1011. 2.
  1012. This instruction adds an offset and a pointer.
  1013. A table content is:
  1014. .sp 1
  1015. .br
  1016. .B
  1017. adp
  1018. .R
  1019. | | | |
  1020. .B
  1021. loc
  1022. .R
  1023. $1
  1024. .B
  1025. adi
  1026. .R
  1027. 2 |
  1028. .NH 2
  1029. Increment, decrement and zero instructions.
  1030. .PP
  1031. In this group a typical instruction is
  1032. .B
  1033. inl
  1034. .R
  1035. , which increments a local or parameter.
  1036. The MCS6500 doesn't have an instruction to increment the
  1037. accumulator A, so the 'ADC' instruction must be used.
  1038. A table content is:
  1039. .sp 1
  1040. .br
  1041. .B
  1042. inl
  1043. .R
  1044. IN($1) | |
  1045. .br
  1046. allocate(R16) /* allocate registerpair AX */
  1047. .br
  1048. "ldy #BASE+$1" /* load Y with offset of the local */
  1049. .br
  1050. "clc" /* clear carry for addition */
  1051. .br
  1052. "lda (LBl),y" /* load indirect lowbyte of local */
  1053. .br
  1054. "adc #1" /* increment lowbyte */
  1055. .br
  1056. "sta (LBl),y" /* restore indirect the incremented lowbyte */
  1057. .br
  1058. "bcc 1f" /* if carry is clear then ready */
  1059. .br
  1060. "iny" /* increment offset of local */
  1061. .br
  1062. "lda (LBl),y" /* load indirect highbyte of local */
  1063. .br
  1064. "adc #0" /* add carry to highbyte */
  1065. .br
  1066. "sta (LBl),y\\n1:" /* restore indirect the highbyte */
  1067. .PP
  1068. If the offset of the local or parameter is to big, first the
  1069. local or parameter is fetched, than incremented, and then
  1070. restored.
  1071. .NH 2
  1072. Convert instructions.
  1073. .PP
  1074. In this case there are two convert instructions
  1075. which really do something.
  1076. One of them is in line code, and deals with the extension of
  1077. a character (1-byte) to an integer.
  1078. The other one is a subroutine which handles the conversion
  1079. between 2-byte integers and 4-byte integers.
  1080. .NH 3
  1081. The in line conversion.
  1082. .PP
  1083. The table content is:
  1084. .sp 1
  1085. .br
  1086. .B
  1087. loc loc cii
  1088. .R
  1089. $1==1 && $2==2 | R16 |
  1090. .br
  1091. "txa" /* see if sign extension is needed */
  1092. .br
  1093. "bpl 1f" /* there is no need for sign extension */
  1094. .br
  1095. "lda #0FFh" /* sign extension here */
  1096. .br
  1097. "bne 2f" /* conversion ready */
  1098. .br
  1099. "1: lda #0\\n2:" /* no sign extension here */
  1100. .NH 2
  1101. Logical instructions.
  1102. .PP
  1103. A typical instruction in this group is the logical
  1104. .B
  1105. and
  1106. .R
  1107. on two 2-byte words.
  1108. The logical
  1109. .B
  1110. and
  1111. .R
  1112. on groups of more than two bytes (max 254)
  1113. is also possible and uses a library subroutine.
  1114. .NH 3
  1115. The logical and on 2-byte groups.
  1116. .PP
  1117. The table content is:
  1118. .sp 1
  1119. .br
  1120. .B
  1121. and
  1122. .R
  1123. $1==2 | R16 | /* one group must be on the fake stack */
  1124. .br
  1125. "sta ARTH+1" /* temporary save of first group highbyte */
  1126. .br
  1127. "stx ARTH" /* temporary save of first group lowbyte */
  1128. .br
  1129. "jsr Pop" /* pop second group from the stack */
  1130. .br
  1131. "and ARTH+1" /* logical and on highbytes */
  1132. .br
  1133. "pha" /* temporary save the result's highbyte */
  1134. .br
  1135. "txa" /* logical and can only be done in A */
  1136. .br
  1137. "and ARTH" /* logical and on lowbytes */
  1138. .br
  1139. "tax" /* restore results lowbyte */
  1140. .br
  1141. "pla" /* restore results highbyte */
  1142. .br
  1143. | %[1] | | /* push result onto fake stack */
  1144. .NH 2
  1145. Set manipulation instructions.
  1146. .PP
  1147. A typical EM pattern in this group is
  1148. .B
  1149. loc inn zeq
  1150. .R
  1151. $1>0 && $1<16 && $2==2.
  1152. This EM pattern works on sets of 16 bits.
  1153. Sets can be bigger (max 256 bytes = 2048 bits), but than a
  1154. library routine is used instead of in line code.
  1155. The table content of the above EM pattern is:
  1156. .sp 1
  1157. .br
  1158. .B
  1159. loc inn zeq
  1160. .R
  1161. $1>0 && $1<16 && $2==2 | R16 |
  1162. .br
  1163. "ldy #$1+1" /* load Y with bit number */
  1164. .br
  1165. "stx ARTH" /* cannot rotate X, so use zero page */
  1166. .br
  1167. "1: lsr a" /* right shift A */
  1168. .br
  1169. "ror ARTH" /* right rotate zero page location */
  1170. .br
  1171. "dey" /* decrement Y */
  1172. .br
  1173. "bne 1b" /* shift $1 times */
  1174. .br
  1175. "bcc $1" /* no carry, so bit is zero */
  1176. .NH 2
  1177. Array instructions.
  1178. .PP
  1179. In this group a typical EM pattern is
  1180. .B
  1181. lae lar
  1182. .R
  1183. defined(rom(1,3)) | | | |
  1184. .B
  1185. lae
  1186. .R
  1187. $1
  1188. .B
  1189. aar
  1190. .R
  1191. $2
  1192. .B
  1193. loi
  1194. .R
  1195. rom(1,3).
  1196. This pattern uses the
  1197. .B
  1198. aar
  1199. .R
  1200. instruction, which is part of a typical EM pattern:
  1201. .sp 1
  1202. .br
  1203. .B
  1204. lae aar
  1205. .R
  1206. $2==2 && rom(1,3)==2 && rom(1,1)==0 | R16 | /* registerpair AX contains
  1207. the index in the array */
  1208. .br
  1209. "pha" /* save highbyte of index */
  1210. .br
  1211. "txa" /* move lowbyte of index to A */
  1212. .br
  1213. "asl a" /* shift left lowbyte == 2 times lowbyte */
  1214. .br
  1215. "tax" /* restore lowbyte */
  1216. .br
  1217. "pla" /* restore highbyte */
  1218. .br
  1219. "rol a" /* rotate left highbyte == 2 times highbyte */
  1220. .br
  1221. | %[1] | adi 2 | /* push new index, add to lowerbound array */
  1222. .NH 2
  1223. Compare instructions.
  1224. .PP
  1225. In this group all EM patterns are performed by calling
  1226. a subroutine.
  1227. Subroutines are used here because comparison is only
  1228. possible byte by byte.
  1229. This means a lot of code, and since compare are used frequently
  1230. a lot of in line code would be generated, and thus reducing
  1231. the space left for the software stack.
  1232. These subroutines can be found in the library.
  1233. .NH 2
  1234. Branch instructions.
  1235. .PP
  1236. A typical branch instruction is
  1237. .B
  1238. beq.
  1239. .R
  1240. The table content for it is:
  1241. .sp 1
  1242. .br
  1243. .B
  1244. beq
  1245. .R
  1246. | R16 |
  1247. .br
  1248. "sta BRANCH+1" /* save highbyte second operand in zero page */
  1249. .br
  1250. "stx BRANCH" /* save lowbyte second operand in zero page */
  1251. .br
  1252. "jsr Pop" /* pop the first operand */
  1253. .br
  1254. "cmp BRANCH+1" /* compare the highbytes */
  1255. .br
  1256. "bne 1f" /* there not equal so go on */
  1257. .br
  1258. "cpx BRANCH" /* compare the lowbytes */
  1259. .br
  1260. "beq $1\\n1:" /* lowbytes are also equal, so branch */
  1261. .PP
  1262. Another typical instruction in this group is
  1263. .B
  1264. zeq.
  1265. .R
  1266. The table content is:
  1267. .sp 1
  1268. .br
  1269. .B
  1270. zeq
  1271. .R
  1272. | R16 |
  1273. .br
  1274. "tay" /* move A to Y for setting testbits */
  1275. .br
  1276. "bmi $1" /* highbyte s minus so branch */
  1277. .br
  1278. "txa" /* move X to A for setting testbits */
  1279. .br
  1280. "beq $1\\n1:" /* lowbyte also zero, thus branch */
  1281. .NH 2
  1282. Procedure call instructions.
  1283. .PP
  1284. In this group one code generation might seem a little
  1285. akward.
  1286. It is the EM instruction
  1287. .B
  1288. cai
  1289. .R
  1290. which generates a 'jsr Indir'.
  1291. This is because there is no indirect jump_subroutine in the
  1292. MCS6500.
  1293. The only solution is to store the address in zero page, and then
  1294. do a 'jsr' to a known label.
  1295. At this label there must be an indirect jump instruction, which
  1296. perform a jump to the address stored in zero page.
  1297. In this case the label is Indir, and the address is stored in
  1298. zero page at the addresses ADDR, ADDR+1.
  1299. The tabel content is:
  1300. .sp 1
  1301. .br
  1302. .B
  1303. cai
  1304. .R
  1305. | R16 |
  1306. .br
  1307. "stx ADDR" /* store lowbyte of address in zero page */
  1308. .br
  1309. "sta ADDR+1" /* store highbyte of address in zero page */
  1310. .br
  1311. "jsr Indir" /* use the indirect jump */
  1312. .br
  1313. | | |
  1314. .NH 2
  1315. Miscellaneous instructions.
  1316. .PP
  1317. In this group, as the name suggests, there is no
  1318. typical EM instruction or EM pattern.
  1319. Most of the MCS6500 code to be generated uses a library subroutine
  1320. or is straightforward.
  1321. .DS C
  1322. .B
  1323. PERFORMANCE.
  1324. .R
  1325. .DE
  1326. .NH 0
  1327. Introduction.
  1328. .PP
  1329. To measure the performance of the back end table some timing
  1330. tests are done.
  1331. What to time?
  1332. In this case, the execution time of several Pascal statements
  1333. are timed.
  1334. Statements in C, which have a Pascal equivalence are timed also.
  1335. The statements are timed as follows.
  1336. A test program is been written, which executes two
  1337. nested for_loops from 1 to 1.000.
  1338. Within these for_loops the statement, which is to be tested, is placed,
  1339. so the statement will be executed 1.000.000 times.
  1340. Then the same program is executed without the test statement.
  1341. The time difference between the two executions is the time
  1342. neccesairy to execute the test statement 1.000.000 times.
  1343. The total time to execute the test statement requires thus the
  1344. time difference divided by 1.000.000.
  1345. .NH 0
  1346. Testing Pascal statements.
  1347. .PP
  1348. The next statements are tested.
  1349. .IP 1)
  1350. int1 := 0;
  1351. .IP 2)
  1352. int1 := int2 - 1;
  1353. .IP 3)
  1354. int1 := int1 + 1;
  1355. .IP 4)
  1356. int1 := icon1 - icon2;
  1357. .IP 5)
  1358. int1 := icon2 div icon1;
  1359. .IP 6)
  1360. int1 := int2 * int3;
  1361. .IP 7)
  1362. bool := (int1 < 0);
  1363. .IP 8)
  1364. bool := (int1 < 3);
  1365. .IP 9)
  1366. bool := ((int1 > 3) or (int1 < 3))
  1367. .IP 10)
  1368. case int1 of 1: bool := false; 2: bool := true end;
  1369. .IP 11)
  1370. if int1 = 0 then int2 := 3;
  1371. .IP 12)
  1372. while int1 > 0 do int1 := int1 - 1;
  1373. .IP 13)
  1374. m := a[k];
  1375. .IP 14)
  1376. let2 := ['a'..'c'];
  1377. .IP 15)
  1378. P3(x);
  1379. .IP 16)
  1380. dum := F3(x);
  1381. .IP 17)
  1382. s.overhead := 5400;
  1383. .IP 18)
  1384. with s do overhead := 5400;
  1385. .PP
  1386. These statement were tested in a procedure test.
  1387. .sp 1
  1388. .br
  1389. procedure test;
  1390. .br
  1391. var i, j, ... : integer;
  1392. .br
  1393. bool : boolean;
  1394. .br
  1395. let2 : set of char;
  1396. .br
  1397. begin
  1398. .br
  1399. for i := 1 to 1000
  1400. .br
  1401. for j := 1 to 1000
  1402. .br
  1403. STATEMENT
  1404. .br
  1405. end;
  1406. .sp 1
  1407. .PP
  1408. STATEMENT is one of the statements as shown above, or it is
  1409. the empty statement.
  1410. The assignment of used variables, if neccesairy, is done before
  1411. the first for_loop.
  1412. In case of the statement which uses the procedure call, statement
  1413. 15, a dummy procedure is declared whose body is empty.
  1414. In case of the statement which uses the function, statement 16,
  1415. this function returns its argument.
  1416. for the timing of C statements a similar test program was
  1417. written.
  1418. .sp 1
  1419. .br
  1420. main()
  1421. .br
  1422. {
  1423. .br
  1424. int i, j, ...;
  1425. .br
  1426. for (i = 1; i <= 1000; i++)
  1427. .br
  1428. for (j = 1; j <= 1000; j++)
  1429. .br
  1430. STATEMENT
  1431. .br
  1432. }
  1433. .sp 1
  1434. .NH
  1435. The results.
  1436. .PP
  1437. Here are tables with the results of the time measurments.
  1438. Times are in microseconds (10^-6).
  1439. Some statements appear twice in the tables.
  1440. In the second case an array of 200 integers was declerated
  1441. before the variable to be tested, so this variable cannot
  1442. be accessed by indirect addressing from the second local base.
  1443. This results in a larger execution time of the statement to be
  1444. tested.
  1445. The column 68000 contains the times measured on a Bleasdale,
  1446. M68000 based, computer.
  1447. The times in column pdp are measured on a DEC pdp11/44, where
  1448. the times from column 6500 come from a BBC microcomputer.
  1449. .bp
  1450. .TS
  1451. expand;
  1452. c s s s
  1453. c c c c
  1454. lw35 nw7 nw7 nw7.
  1455. Pascal timing results
  1456. statement 68000 pdp 6500
  1457. _
  1458. T{
  1459. int1 := 0;
  1460. T} 4.0 5.8 16.7
  1461. 4.0 4.2 97.8
  1462. _
  1463. T{
  1464. int1 := int2 - 1;
  1465. T} 7.2 7.1 27.2
  1466. 6.9 7.1 206.5
  1467. _
  1468. T{
  1469. int1 := int1 + 1;
  1470. T} 6.9 6.8 27.2
  1471. 6.4 6.7 106.5
  1472. _
  1473. T{
  1474. int1 := icon1 + icon2;
  1475. T} 6.2 6.2 25.6
  1476. 6.2 6.0 106.6
  1477. _
  1478. T{
  1479. int1 := icon2 div icon1;
  1480. T} 14.9 14.3 372.6
  1481. 14.9 14.7 453.7
  1482. _
  1483. T{
  1484. int1 := int2 * int3;
  1485. T} 11.5 12.0 558.1
  1486. 11.3 11.6 728.6
  1487. _
  1488. T{
  1489. bool := (int1 < 0);
  1490. T} 7.2 6.9 122.8
  1491. 7.8 8.1 453.2
  1492. _
  1493. T{
  1494. bool := (int1 < 3);
  1495. T} 7.3 7.6 126.0
  1496. 7.2 8.1 232.2
  1497. _
  1498. T{
  1499. bool := ((int1 > 3) or (int1 < 3))
  1500. T} 10.1 12.0 307.8
  1501. 10.2 11.9 440.1
  1502. _
  1503. T{
  1504. case int1 of 1: bool := false; 2: bool := true end;
  1505. T} 18.3 17.9 165.7
  1506. _
  1507. T{
  1508. if int1 = 0 then int2 := 3;
  1509. T} 9.5 8.5 133.8
  1510. _
  1511. T{
  1512. while int1 > 0 do int1 := int1 - 1;
  1513. T} 6.9 6.9 126.0
  1514. _
  1515. T{
  1516. m := a[k];
  1517. T} 7.2 6.8 134.3
  1518. _
  1519. T{
  1520. let2 := ['a'..'c'];
  1521. T} 38.4 38.8 447.4
  1522. _
  1523. T{
  1524. P3(x);
  1525. T} 18.9 18.8 180.3
  1526. _
  1527. T{
  1528. dum := F3(x);
  1529. T} 26.8 27.1 343.3
  1530. _
  1531. T{
  1532. s.overhead := 5400;
  1533. T} 4.6 4.1 16.7
  1534. _
  1535. T{
  1536. with s do overhead := 5400;
  1537. T} 4.2 4.3 16.7
  1538. .TE
  1539. .TS
  1540. expand;
  1541. c s s s
  1542. c c c c
  1543. lw35 nw7 nw7 nw7.
  1544. C timing results
  1545. statement 68000time pdptime 6500time
  1546. _
  1547. T{
  1548. int1 = 0;
  1549. T} 4.1 3.6 17.2
  1550. 4.1 4.1 97.7
  1551. _
  1552. T{
  1553. int1 = int2 - 1;
  1554. T} 6.6 6.9 27.2
  1555. 6.1 6.5 206.4
  1556. _
  1557. T{
  1558. int1 = int1 + 1;
  1559. T} 6.4 7.3 27.2
  1560. 6.3 6.2 206.4
  1561. _
  1562. T{
  1563. int1 = int2 * int3;
  1564. T} 11.4 12.3 522.6
  1565. 9.6 10.1 721.2
  1566. _
  1567. T{
  1568. int1 = (int2 < 0);
  1569. T} 7.2 7.6 126.4
  1570. 7.4 7.7 232.5
  1571. _
  1572. T{
  1573. int1 = (int2 < 3);
  1574. T} 7.0 7.5 126.0
  1575. 7.8 7.8 232.6
  1576. _
  1577. T{
  1578. int1 = ((int2 > 3) || (int2 < 3));
  1579. T} 11.8 12.2 193.4
  1580. 11.5 13.2 245.6
  1581. _
  1582. T{
  1583. switch (int1) { case 1: int1 = 0; break; case 2: int1 = 1; break; }
  1584. T} 28.3 29.2 164.1
  1585. _
  1586. T{
  1587. if (int1 == 0) int2 = 3;
  1588. T} 4.8 4.8 19.4
  1589. _
  1590. T{
  1591. while (int2 > 0) int2 = int2 - 1;
  1592. T} 5.8 6.0 125.9
  1593. _
  1594. T{
  1595. int2 = a[int2];
  1596. T} 4.8 5.1 192.8
  1597. _
  1598. T{
  1599. P3(int2);
  1600. T} 18.8 18.4 180.3
  1601. _
  1602. T{
  1603. int2 = F3(int2);
  1604. T} 27.0 27.2 309.4
  1605. _
  1606. T{
  1607. s.overhead = 5400;
  1608. T} 5.0 4.1 16.7
  1609. .TE
  1610. .NH
  1611. Pascal statements which don't have a C equivalent.
  1612. .PP
  1613. At first, the two statements who perform an operation on constants
  1614. are left out.
  1615. These are left out while the C front end does constant folding,
  1616. while the Pascal front end doesn't.
  1617. So in C the statements int1 = icon1 + icon2; and int1 = icon1 / icont2;
  1618. will use the same amount of time since the expression is evaluated
  1619. by the front end.
  1620. The two other statements (let2 := ['a'..'c']; and
  1621. .B
  1622. with
  1623. .R
  1624. s
  1625. .B
  1626. do
  1627. .R
  1628. overhead := 5400;), aren't included in the C statement timing table,
  1629. because there constructs do not exist in C.
  1630. Although in C there can be direct bit manipulation, and thus can
  1631. be used to implement sets I have not used it here.
  1632. The
  1633. .B
  1634. with
  1635. .R
  1636. statement does not exists in C and there is nothing with the slightest
  1637. resemblance to it.
  1638. .PP
  1639. At first sight in the table , it looked if there is no much difference
  1640. in the times for the M68000 and the pdp11/44, in comparison with the
  1641. times needed by the MCS6500.
  1642. To verify this impression, I calculated the correlation coefficient
  1643. between the times of the M68000 and pdp11/44.
  1644. It turned out to be 0.997 for both the Pascal time tests and the C
  1645. time tests.
  1646. Since the correlation coefficient is near to one and the difference
  1647. between the times is small, they can be considered to be the same
  1648. as seen from the times of the MCS6500.
  1649. Then I have tried to make a grafic of the times from the M68000 and
  1650. the MCS6500.
  1651. Well, there was't any correlation to been seen, taken all the times.
  1652. The only correlation one could see, with some effort, was in the
  1653. times for the first three Pascal statements.
  1654. The two first C statements show also a correlation, which two points
  1655. always do.
  1656. .PP
  1657. Also the three Pascal statements
  1658. .B
  1659. case
  1660. .R
  1661. ,
  1662. .B
  1663. if
  1664. .R
  1665. ,
  1666. and
  1667. .B
  1668. while
  1669. .R
  1670. have a correlation coefficient of 0.999.
  1671. This is probably because the
  1672. .B
  1673. case
  1674. .R
  1675. statement uses a subroutine in both cases and the other two
  1676. statements
  1677. .B
  1678. if
  1679. .R
  1680. and,
  1681. .B
  1682. while
  1683. .R
  1684. generate in line code.
  1685. The last two Pascal statements use the same time, since the front
  1686. end wil generate the same EM code for both.
  1687. .PP
  1688. The independence between the rest of the test times is because
  1689. in these cases the object code for the MCS6500 uses library
  1690. subroutines, while the other processors can handle the EM code
  1691. with in line code.
  1692. .PP
  1693. It is clear that the MCS6500 is a slower device, it needs longer
  1694. execution times, the need of more library subroutines, but
  1695. there is no constant factor between it execution times and those
  1696. of other processors.
  1697. .PP
  1698. The slowing down of the MCS6500 as result of the need of a
  1699. library subroutine is illustrated by the muliplication
  1700. statement.
  1701. The MCS6500 needs a library subroutine, while the other
  1702. two processors have a machine instruction to perform the
  1703. multiply.
  1704. This results in a factor of 48.5, when the operands can be accessed
  1705. indirect by the MCS6500.
  1706. When the MCS6500 cannot access the operands indirectly the situation
  1707. is even worse.
  1708. The slight differences between the MCS6500 execution times for
  1709. Pascal statements and C statements is probably the result of the
  1710. front end, and thus beyond the scope of this discussion.
  1711. .PP
  1712. Another timing test is done in C on the statement k = i + j + 1983.
  1713. This statement is tested on many UNIX*
  1714. .FS
  1715. * UNIX is a Trademark of Bell Laboratories.
  1716. .FE
  1717. systems.
  1718. For a complete list see appendix A.
  1719. The slowest one is the IBM XT, which runs on a 8088 microprocessor.
  1720. The fasted one is the Amdahl computer.
  1721. Here is short table to illustrate the performance of the
  1722. MCS6500.
  1723. .TS
  1724. c c c
  1725. c n n.
  1726. machine short int
  1727. IBM XT 53.4 53.4
  1728. Amdahl 0.5 0.3
  1729. MCS6500 150.2 150.2
  1730. .TE
  1731. The MCS6500 is three times slower than the IBM XT, but threehundred
  1732. times slower than the Amdahl.
  1733. The reason why the times on the IBM XT and the MCS6500 are the
  1734. same for short's and int's, is that most C compilers make the types
  1735. short and integer the same size on 16-bit machines.
  1736. In this project the MCS6500 is regarded as a 16-bit machine.
  1737. .NH
  1738. Length tests.
  1739. .PP
  1740. I have also compiled several programs written in Pascal and C to
  1741. see if there is a resemblance between the number of bytes generated
  1742. in the machine's language.
  1743. In the tables:
  1744. .IP length: 9
  1745. The number of bytes of the source program.
  1746. .IP 68000:
  1747. The number of bytes of the a.out file for a M68000.
  1748. .IP pdp:
  1749. The number of bytes of the a.out file for a pdp11/44.
  1750. .IP 6500:
  1751. The number of bytes of the a.out file for a MCS6500.
  1752. .LP
  1753. These are the results:
  1754. .TS
  1755. c s s s
  1756. c c c c
  1757. n n n n.
  1758. Pascal programs
  1759. length 68000 pdp 6500
  1760. _
  1761. 19946 14383 16090 26710
  1762. 19484 20169 20190 35416
  1763. 10849 10469 11464 18949
  1764. 273 4221 5106 7944
  1765. 1854 5807 6610 10301
  1766. .TE
  1767. .TS
  1768. c s s s
  1769. c c c c
  1770. n n n n.
  1771. C progams
  1772. length 68000 pdp 6500
  1773. _
  1774. 9444 6927 8234 11559
  1775. 7655 14353 18240 26251
  1776. 4775 11309 15934 19910
  1777. 639 6337 9660 12494
  1778. .TE
  1779. .PP
  1780. In contrast to the execution times of the test statements, the
  1781. object code files sizes show a constant factor between them.
  1782. After calculating the correlation coefficient, I have calculated
  1783. the line fitted between sizes.
  1784. .FS
  1785. * x is the number of bytes
  1786. .FE
  1787. .TS
  1788. c s s
  1789. c c c
  1790. l c c.
  1791. Pascal programs
  1792. processor corr. coef. fitted line
  1793. _
  1794. 68000-pdp 0.996
  1795. 68000-6500 0.999 1.76x + 502*
  1796. pdp-6500 0.999 1.80x - 1577
  1797. .TE
  1798. .TS
  1799. c s s
  1800. c c c
  1801. l c c.
  1802. C programs
  1803. processor corr. coef. fitted line
  1804. _
  1805. 68000-pdp 0.974
  1806. 68000-6500 0.992 1.80x + 502*
  1807. pdp-6500 0.980 1.40x - 1577
  1808. .TE
  1809. .PP
  1810. As seen from the tables above the correlation coefficient for
  1811. Pascal programs is better than the ones for C programs.
  1812. Thus the line fits best for Pascal programs.
  1813. With the formula of the best fitted line one can now estimate
  1814. the size of the object code, which a program needs, for a MCS6500
  1815. without having the compiler at hand.
  1816. One also can see from these formula that the object code
  1817. generated for a MCS6500 is about 1.8 times more than for the other
  1818. processors.
  1819. Since the number of bytes in the source file havily depends on the
  1820. programmer, how many spaces he or she uses, the size of the indenting
  1821. in structured programs, etc., there is no correlation between the
  1822. size of the source file and the size of the object file.
  1823. Also the use of comments has its influence on the size.
  1824. .bp
  1825. .DS C
  1826. .B
  1827. SUMMARY.
  1828. .R
  1829. .DE
  1830. .NH 0
  1831. Summary
  1832. .PP
  1833. In this chapter some final conclusions are made.
  1834. .PP
  1835. In spite of its simplicity, the MCS6500 is strong enough to
  1836. implement a EM machine.
  1837. A serious deficy of the MCS6500 is the missing of 16-bit
  1838. general purpose registers, and especially the missing of a
  1839. 16-bit stackpointer.
  1840. As pointed out before, one 16-bit register can be simulated
  1841. by a pair of 8-bit registers, in fact, the accumulator A to
  1842. hold the highbyte, and the index register X to hold the lowbyte
  1843. of the word.
  1844. By lack of a 16-bit stackpointer, zero page must be used to hold
  1845. a stackpointer and there are also two subroutines needed for
  1846. manipulating the stack (Push and Pop).
  1847. .PP
  1848. As seen at the time tests, the simple instruction set of the
  1849. MCS6500 forces the use of library subroutines.
  1850. These library subroutines increas the execution time of the
  1851. programs.
  1852. .PP
  1853. The sizes of the object code files show a strong correlation
  1854. in contrast to the execution times.
  1855. With this correlatiuon one canestimate the size of a program
  1856. if it is to be used on a MCS6500.
  1857. .bp
  1858. .NH 0
  1859. .B
  1860. REFERENCES.
  1861. .R
  1862. .IP 1.
  1863. Osborn, A., Jacobson, S., and Kane, J. The Mos Technology MCS6500.
  1864. .B
  1865. An Introduction to Microcomputers ,
  1866. .R
  1867. Volume II, Some Real Products (june 1977) chap. 9.
  1868. .RS
  1869. .PP
  1870. A hardware description of some real existing CPU's, such as
  1871. the Intel Z80, MCS6500, etc. is given in this book.
  1872. .RE
  1873. .IP 2.
  1874. van Staveren, H.
  1875. The table driven code generator from the Amsterdam Compiler Kit.
  1876. Vrije Universiteit, Amsterdam, (July 11, 1983).
  1877. .RS
  1878. .PP
  1879. The defining document for writing a back end table.
  1880. .RE
  1881. .IP 3.
  1882. Tanenbaum, A.S. Structured Computer Organization.
  1883. Prentice Hall. (1976).
  1884. .RS
  1885. .PP
  1886. In this book computers are described as a hierarchy of levels,
  1887. with each one performing some well-defined function.
  1888. .RE