6500.doc 51 KB

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