ncg.doc 85 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023
  1. .\" $Header$
  2. .RP
  3. .ND
  4. .TL
  5. The table driven code generator
  6. .br
  7. from the
  8. .br
  9. Amsterdam Compiler Kit
  10. .br
  11. Second Revised Edition
  12. .AU
  13. Hans van Staveren
  14. .AI
  15. Dept. of Mathematics and Computer Science
  16. Vrije Universiteit
  17. Amsterdam, The Netherlands
  18. .AB
  19. The Amsterdam Compiler Kit is a collection of tools
  20. designed to help automate the process of compiler building.
  21. Part of it is a table driven code generator,
  22. called
  23. .I cg ,
  24. and a program to check and translate machine description
  25. tables called
  26. .I cgg .
  27. This document provides a description of the internal workings of
  28. .I cg ,
  29. and a description of syntax and semantics of the driving table.
  30. This is required reading for those wishing to write a new table.
  31. .AE
  32. .NH 1
  33. Introduction
  34. .PP
  35. Part of the Amsterdam Compiler Kit is a code generator system consisting
  36. of a code generator generator (\fIcgg\fP for short) and some machine
  37. independent C code.
  38. .I Cgg
  39. reads a machine description table and creates two files,
  40. tables.h and tables.c.
  41. These are then used together with other C code to produce
  42. a code generator for the machine at hand.
  43. .PP
  44. This in turn reads compact EM code and produces
  45. assembly code.
  46. The remainder of this document will first broadly describe
  47. the working of the code generator,
  48. then the machine table will be described after which
  49. some light is shed onto
  50. the internal workings of the code generator.
  51. .PP
  52. The reader is assumed to have at least a vague notion about the
  53. semantics of the intermediary EM code.
  54. Someone wishing to write a table for a new machine
  55. should be thoroughly acquainted with EM code
  56. and the assembly code of the machine at hand.
  57. .NH 1
  58. What has changed since version 1 ?
  59. .PP
  60. This section can be skipped by anyone not familiar with the first version.
  61. It is not needed to understand the current version.
  62. .PP
  63. This paper describes the second version of the code generator system.
  64. Although the code generator itself is for the main part unchanged,
  65. the table format has been drastically redesigned and the opportunities
  66. to make faulty tables are reduced.
  67. The format is now aesthaticly more pleasing (according to \fIme\fP that is),
  68. mainly because the previous version was designed for one line code rules,
  69. which did not work out that way.
  70. .PP
  71. The `SCRATCH' property is now automatically generated by
  72. .I cgg ,
  73. .I erase
  74. and
  75. .I setcc
  76. calls and their ilk are now no longer needed
  77. (read: can no longer be forgotten)
  78. and all this because the table now
  79. .I knows
  80. what the machine instructions look like and what arguments they
  81. destroy.
  82. .PP
  83. Checks are now made for register types, so it is no longer possible
  84. to generate a `regind2' token with a floating point register as a base.
  85. In general, if the instructions of the machine are correctly defined,
  86. it is no longer possible to generate code that does not assemble,
  87. which of course does not mean that it is not possible to generate
  88. assembly code that does not do what was intended!
  89. .PP
  90. Checks are made now for missing moves, tests, coercions, etc.
  91. There is a form of procedure call now to reduce table size:
  92. it is no longer necessary to write the code for conditional
  93. instructions six times.
  94. .PP
  95. The inreg() pseudo-function returns other results!!
  96. .NH 1
  97. Global overview of the workings of the code generator.
  98. .PP
  99. The code generator or
  100. .I cg
  101. tries to generate good code by simulating the stack
  102. of the compiled program and delaying emission of code as long
  103. as possible.
  104. It also keeps track of register contents, which enables it to
  105. eliminate redundant moves, and tries to eliminate redundant tests
  106. by keeping information about condition code status,
  107. if applicable for the machine.
  108. .PP
  109. .I Cg
  110. maintains a `fake stack' containing `tokens' that are built
  111. by executing the pseudo code contained in the code rules given
  112. by the table writer.
  113. One can think of the fake stack as a logical extension of the real
  114. stack the compiled program will have when run.
  115. Alternatively one can think of the real stack as an infinite extension
  116. at the bottom of the fake stack.
  117. Both ways, the concatenation of the real stack and the fake stack
  118. will be the stack as it would have been on a real EM machine (see figure).
  119. .TS
  120. center;
  121. cw(3.5c) cw(3c) cw(3.5c)
  122. cw(3.5c) cw(3c) cw(3.5c)
  123. |cw(3.5c)| cw(3c) |cw(3.5c)| .
  124. EM machine target machine
  125. real stack
  126. stack
  127. grows
  128. EM stack \s+2\(br\s0
  129. \s+2\(br\s0
  130. \s+2\(br\s0 _
  131. \s+2\(br\s0
  132. \s+2\(da\s0
  133. fake stack
  134. _ _
  135. .T&
  136. ci s s.
  137. Relation between EM stack, real stack and fake stack.
  138. .TE
  139. During code generation tokens will be kept on the fake stack as long
  140. as possible but when they are moved to the real stack,
  141. by generating code for the push,
  142. all tokens above\v'-.25m'\(dg\v'.25m'
  143. .FS
  144. \(dg in this document the stack is assumed to grow downwards,
  145. although the top of the stack will mean the first element that will
  146. be popped.
  147. .FE
  148. the pushed tokens will be pushed also,
  149. so the fake stack will not contain holes.
  150. .PP
  151. The information about the machine that
  152. .I cg
  153. needs has to be given in a machine description table,
  154. with as a major part a list of code rules telling
  155. .I cg
  156. what to do when certain EM-instructions occur
  157. with certain tokens on the fake stack.
  158. Not all possible fake stack possibilities have to be given of course,
  159. there is a possibility for providing rewriting rules, or
  160. .I coercions
  161. as they are called in this document.
  162. .PP
  163. The main loop of
  164. .I cg
  165. is:
  166. .IP 1)
  167. find a pattern of EM instructions starting at the current one to
  168. generate code for.
  169. This pattern will usually be of length one but longer patterns can be used.
  170. Process any pseudo-instructions found.
  171. .IP 2)
  172. Select one of the possibly many stack patterns that go with this
  173. EM pattern on the basis of heuristics, look ahead or both.
  174. The cost fields provided in the token definitions and
  175. instruction definitions are used
  176. to compute costs during look ahead.
  177. .IP 3)
  178. Force the current fake stack contents to match the pattern.
  179. This may involve
  180. copying tokens to registers, making dummy transformations, e.g. to
  181. transform a `local' into an `indexed from register' or might even
  182. cause the move of the complete fake stack contents to the real stack
  183. and then back into registers if no suitable coercions
  184. were provided by the table writer.
  185. .IP 4)
  186. Execute the pseudocode associated with the code rule just selected,
  187. this may cause registers to be allocated,
  188. code to be emitted etc..
  189. .IP 5)
  190. Put tokens onto the fake stack to reflect the result of the operation.
  191. .IP 6)
  192. Insert some EM instructions into the stream;
  193. this is possible but not common.
  194. .IP 7)
  195. Account for the cost.
  196. The cost is kept in a (space, time) vector and look ahead decisions
  197. are based on a linear combination of these.
  198. The code generator calls on itself recursively during look ahead,
  199. and the recursive incarnations return the costs they made.
  200. The costs the top-level code generator makes is of course irrelevant.
  201. .PP
  202. The table that drives
  203. .I cg
  204. is not read in every time,
  205. but instead is used at compile time
  206. of
  207. .I cg
  208. to set parameters and to load pseudocode tables.
  209. A program called
  210. .I cgg
  211. reads the table and produces large lists of numbers that are
  212. compiled together with machine independent code to produce
  213. a code generator for the machine at hand.
  214. .PP
  215. Part of the information needed is not easily expressed in this table
  216. format and must be supplied in two separate files,
  217. mach.h and mach.c.
  218. Their contents are described later in this document.
  219. .NH 1
  220. Register variables
  221. .PP
  222. If the machine has more than enough registers to generate code with,
  223. it is possible to reserve some of them for use as register variables.
  224. If it has not, you can skip this section and ignore any references
  225. to register variables in the rest of this document.
  226. .PP
  227. The front ends generate messages to the back ends telling them which
  228. local variables could go into registers.
  229. The information given is the offset of the local, its size and type
  230. and a scoring number, roughly the number of times it occurs.
  231. .PP
  232. The decision which variable to put in which register is taken by the
  233. machine independent part of
  234. .I cg
  235. with the help of a scoring function provided by the table writer in mach.c.
  236. The types of variables known are
  237. .IP reg_any 12
  238. Just a variable of some integer type.
  239. Nothing special known about it.
  240. .IP reg_float
  241. A floating point variable.
  242. .IP reg_loop
  243. A loop control variable.
  244. .IP reg_pointer
  245. A pointer variable.
  246. Usually they are better candidates to put in registers.
  247. .PP
  248. If you use register variables in your table you must supply
  249. more functions in mach.c.
  250. These functions are explained later.
  251. .NH 1
  252. Description of the machine table
  253. .PP
  254. The machine description table consists of the
  255. concatenation of the following sections:
  256. .IP 1)
  257. Constant definitions
  258. .IP 2)
  259. Property definitions
  260. .IP 3)
  261. Register definitions
  262. .IP 4)
  263. Token definitions
  264. .IP 5)
  265. Set definitions
  266. .IP 6)
  267. Instruction definitions
  268. .IP 7)
  269. Move definitions
  270. .IP 8)
  271. Test definitions
  272. .IP 9)
  273. Stack definitions
  274. .IP 10)
  275. Coercions
  276. .IP 11)
  277. Code rules
  278. .PP
  279. This is the order in the table
  280. but the descriptions in this document will use a slightly different
  281. order.
  282. All sections except the first start with an uppercase header word.
  283. Examples may be given in early stages that use knowledge that is explained
  284. in a later stage.
  285. If something is not clear the first time, please read on.
  286. All will clear up in a couple of pages.
  287. .PP
  288. Input is in free format, white space and newlines may be used
  289. at will to improve legibility.
  290. Identifiers used in the table have the same syntax as C identifiers,
  291. upper and lower case considered different, all characters significant.
  292. Here is a list of reserved words; all of these are unavailable as identifiers.
  293. .TS
  294. box;
  295. l l l l l.
  296. ADDR STACKINGRULES gen proc test
  297. COERCIONS TESTS highw reg_any to
  298. INSTRUCTIONS TIMEFACTOR inreg reg_float topeltsize
  299. INT TOKENS is_rom reg_loop ufit
  300. MOVES call kills reg_pointer uses
  301. PATTERNS cost lab regvar with
  302. PROPERTIES defined labeldef return yields
  303. REGISTERS exact leaving reusing
  304. SETS example loww rom
  305. SIZEFACTOR fallthrough move samesign
  306. STACK from pat sfit
  307. .TE
  308. C style comments are accepted.
  309. .DS
  310. /* this is a comment */
  311. .DE
  312. If the standard constant facility is not enough the C-preprocessor can
  313. be used to enhance the table format.
  314. .PP
  315. Integers in the table have the normal C-style syntax.
  316. Decimal by default, octal when preceded by a 0
  317. and hexadecimal when preceded by 0x.
  318. .NH 2
  319. Constant section
  320. .PP
  321. In the first part of the table some constants can be defined,
  322. most with the syntax
  323. .DS
  324. NAME=value
  325. .DE
  326. value being an integer or string.
  327. Three constants must be defined here:
  328. .IP EM_WSIZE 14
  329. Number of bytes in a machine word.
  330. This is the number of bytes
  331. a \fBloc\fP instruction will put on the stack.
  332. .IP EM_PSIZE
  333. Number of bytes in a pointer.
  334. This is the number of bytes
  335. a \fBlal\fP instruction will put on the stack.
  336. .IP EM_BSIZE
  337. Number of bytes in the hole between AB and LB.
  338. If the calling sequence just saves PC and LB this
  339. size will be twice the pointersize.
  340. .PP
  341. EM_WSIZE and EM_PSIZE are checked when a program is compiled
  342. with the resulting code generator.
  343. EM_BSIZE is used by
  344. .I cg
  345. to add to the offset of instructions dealing with locals
  346. having positive offsets,
  347. i.e. parameters.
  348. .PP
  349. Other constants can be defined here to be used as mnemonics
  350. later in the table.
  351. .PP
  352. Optional is the definition of a printformat for integers in the code file.
  353. This is given as
  354. .DS
  355. FORMAT = string
  356. .DE
  357. The string must be a valid printf(III) format,
  358. and defaults to "%ld".
  359. For example on the PDP-11 one can use
  360. .DS
  361. FORMAT= "0%lo"
  362. .DE
  363. to satisfy the old UNIX assembler that reads octal unless followed by
  364. a period, and the ACK assembler that follows C conventions.
  365. .PP
  366. Tables under control of source code control systems like
  367. .I sccs
  368. or
  369. .I rcs
  370. can put their id-string here, for example
  371. .DS
  372. rcsid="$\&Header$"
  373. .DE
  374. These strings, like all strings in the table, will eventually
  375. end up in the binary code generator produced.
  376. .PP
  377. Optionally one can give the factors with which the size and time
  378. parts of the cost vector have to be multiplied to ensure they have the
  379. same order of magnitude.
  380. This can be done as
  381. .DS
  382. SIZEFACTOR = C\d3\u/C\d4\u
  383. .sp
  384. TIMEFACTOR = C\d1\u/C\d2\u
  385. .DE
  386. Above numbers must be read as rational numbers.
  387. Defaults are 1/1 for both of them.
  388. These constants set the default size/time tradeoff in the code generator,
  389. so if TIMEFACTOR and SIZEFACTOR are both 1 the code generator will choose
  390. at random between two code sequences where one has
  391. cost (10,4) and the other has cost (8,6).
  392. See also the description of the cost field below.
  393. .NH 2
  394. Property definition
  395. .PP
  396. This part of the table defines the list of properties that can be used
  397. to differentiate between register classes.
  398. It consists of a list of user-defined
  399. identifiers optionally followed by the size
  400. of the property in parentheses, default EM_WSIZE.
  401. Example for the PDP-11:
  402. .TS
  403. l l.
  404. PROPERTIES /* The header word for this section */
  405. GENREG /* All PDP registers */
  406. REG /* Normal registers (allocatable) */
  407. ODDREG /* All odd registers (allocatable) */
  408. REGPAIR(4) /* Register pairs for division */
  409. FLTREG(4) /* Floating point registers */
  410. DBLREG(8) /* Same, double precision */
  411. GENFREG(4) /* generic floating point */
  412. GENDREG(8) /* Same, double precision */
  413. FLTREGPAIR(8) /* register pair for modf */
  414. DBLREGPAIR(16) /* Same, double precision */
  415. LOCALBASE /* Guess what */
  416. STACKPOINTER
  417. PROGRAMCOUNTER
  418. .TE
  419. Registers are allocated by asking for a property,
  420. so if for some reason in later parts of the table
  421. one particular register must be allocated it
  422. has to have a unique property.
  423. .NH 2
  424. Register definition
  425. .PP
  426. The next part of the tables describes the various registers of the
  427. machine and defines identifiers
  428. to be used in later parts of the tables.
  429. Syntax:
  430. .DS
  431. <register definitions> : REGISTERS <list of definitions>
  432. <definition> : <registerlist> ':' <propertylist> <optional regvar> '.'
  433. <register> : ident [ '(' string ')' ] [ '=' ident [ '+' ident ] ]
  434. .DE
  435. Example for the PDP-11:
  436. .TS
  437. l l.
  438. REGISTERS
  439. r0,r2,r4 : GENREG,REG.
  440. r1,r3 : GENREG,REG,ODDREG.
  441. r01("r0")=r0+r1 : REGPAIR.
  442. fr0("r0"),fr1("r1"),fr2("r2"),fr3("r3") : GENFREG,FLTREG.
  443. dr0("r0")=fr0,dr1("r1")=fr1,
  444. dr2("r2")=fr2,dr3("r3")=fr3 : GENDREG,DBLREG.
  445. fr01("r0")=fr0+fr1,fr23("r2")=fr2+fr3 : FLTREGPAIR.
  446. dr01("r0")=dr0+dr1,dr23("r2")=dr2+dr3 : DBLREGPAIR.
  447. lb("r5") : GENREG,LOCALBASE.
  448. sp : GENREG,STACKPOINTER.
  449. pc : GENREG,PROGRAMCOUNTER.
  450. .TE
  451. .PP
  452. The names in the left hand lists are names of registers as used
  453. in the table.
  454. They can optionally be followed by a string in parentheses,
  455. their name as far as the assembler is concerned.
  456. The default assembler name is the same as the table name.
  457. A name can also be followed by
  458. .DS
  459. = othername
  460. .DE
  461. or
  462. .DS
  463. = othername + othername
  464. .DE
  465. which says that the register is composed of the parts
  466. after the '=' sign.
  467. The identifiers at the right hand side of the lists are
  468. names of properties.
  469. The end of each register definition is a period.
  470. .PP
  471. It might seem wise to list every property of a register,
  472. so one might give r0 the extra property MFPTREG named after the not
  473. too well known MFPT instruction on newer PDP-11 types,
  474. but this is not a good idea,
  475. especially since no use can be made of that instruction anyway.
  476. Every extra property means the register set is more unorthogonal
  477. and
  478. .I cg
  479. execution time is influenced by that,
  480. because it has to take into account a larger set of registers
  481. that are not equivalent.
  482. So try to keep the number of different register classes to a minimum.
  483. When faced with the choice between two possible code rules
  484. for a nonfrequent EM sequence,
  485. one being elegant but requiring an extra property,
  486. and the other less elegant,
  487. elegance should probably loose.
  488. .PP
  489. Tables that implement register variables must mark registers to be used
  490. for variable storage here by following the list of properties by one
  491. of the following:
  492. .DS
  493. regvar \fIor\fP regvar(reg_any)
  494. regvar(reg_loop)
  495. regvar(reg_pointer)
  496. regvar(reg_float)
  497. .DE
  498. meaning they are candidates for that type of variable.
  499. All register variables of one type must be of the same size,
  500. and they may have no subregisters.
  501. Such registers are not available for normal code generation.
  502. .NH 2
  503. Stack token definition
  504. .PP
  505. The next part describes all possible tokens that can reside on
  506. the fake stack during code generation.
  507. Attributes of a token are described as a C struct declaration;
  508. this is followed by the size of the token in bytes,
  509. optionally followed by the cost of the token when used as an addressing mode
  510. and the format to be used on output.
  511. .PP
  512. In general, when writing a table, it is not wise to try
  513. to think of all necessary tokens in advance.
  514. While writing the necessity or advisability for some token
  515. will be seen and it can then be added together with the
  516. stacking rules and coercions needed.
  517. .PP
  518. Tokens should usually be declared for every addressing mode
  519. of the machine at hand and for every size directly usable in
  520. a machine instruction.
  521. Example for the PDP-11 (incomplete):
  522. .TS
  523. l l.
  524. TOKENS
  525. const2 = { INT num; } 2 cost(2,300) "$" num .
  526. addr_local = { INT ind; } 2 .
  527. addr_external = { ADDR off; } 2 "$" off.
  528. regdef2 = { GENREG reg; } 2 "*" reg.
  529. regind2 = { GENREG reg; ADDR off; } 2 off "(" reg ")" .
  530. reginddef2 = { GENREG reg; ADDR off; } 2 "*" off "(" reg ")" .
  531. regconst2 = { GENREG reg; ADDR off; } 2 .
  532. relative2 = { ADDR off; } 2 off .
  533. reldef2 = { ADDR off; } 2 "*" off.
  534. .TE
  535. .PP
  536. Types allowed in the struct are ADDR, INT and all register properties.
  537. The type ADDR means a string and an integer,
  538. which is output as string+integer,
  539. and arithmetic on mixed ADDR and INT is possible.
  540. This is the right mode for anything that can be an
  541. assembler address expression.
  542. The type of the register in the token is strict.
  543. At any assignment of an expression of type register to a token attribute
  544. of type register
  545. .I cgg
  546. will check if the set of possible results from the expression is a subset
  547. of the set of permissible values for the token attribute.
  548. .PP
  549. The cost-field is made up by the word
  550. .I cost
  551. followed by two numbers in parentheses, the size and timecosts
  552. of this token when output in the code file.
  553. If omitted, zero cost is assumed.
  554. While generating code,
  555. .I cg
  556. keeps track of a linear combination of these costs together
  557. with the costs of the instructions itself which we will see later.
  558. The coefficients of this linear combination are influenced
  559. by two things:
  560. .IP 1)
  561. The SIZEFACTOR and TIMEFACTOR constants,
  562. as mentioned above.
  563. .IP 2)
  564. A run time option to
  565. .I cg
  566. that can adjust the time/space tradeoff to all positions
  567. from 100% time to 100% space.
  568. .LP
  569. By supplying different code rules in certain situations
  570. it is possible to get a code generator that can adjust its
  571. code to the need of the moment.
  572. This is probably most useful with small machines,
  573. experience has shown that on the larger micro's and mini's
  574. the difference between time-optimal and space-optimal code
  575. is often small.
  576. .PP
  577. The printformat consists of a list of strings intermixed with
  578. attributes from the token.
  579. Strings are output literally, attributes are printed according
  580. to their type and value.
  581. Tokens without a printformat should never be output,
  582. and
  583. .I cgg
  584. checks for this.
  585. .PP
  586. Notice that tokens need not correspond to addressing modes;
  587. the regconst2 token listed above,
  588. meaning the sum of the contents of the register and the constant,
  589. has no corresponding addressing mode on the PDP-11,
  590. but is included so that a sequence of add constant, load indirect,
  591. can be handled efficiently.
  592. This regconst2 token is needed as part of the path
  593. .DS
  594. REG -> regconst2 -> regind2
  595. .DE
  596. of which the first and the last "exist" and the middle is needed
  597. only as an intermediate step.
  598. .PP
  599. Tokens with name `LOCAL' or `DLOCAL' are a special case when
  600. register variables are used, this is explained further in the
  601. section on token descriptions.
  602. .NH 2
  603. Sets
  604. .PP
  605. Usually machines have certain collections of addressing modes that
  606. can be used with certain instructions.
  607. The stack patterns in the table are lists of these collections
  608. and since it is cumbersome to write out these long lists
  609. every time, there is a section here to give names to these
  610. collections.
  611. Please note that it is not forbidden to write out a set
  612. in the remainder of the table,
  613. but for clarity it is usually better not to.
  614. .LP
  615. Example for the PDP-11 (incomplete):
  616. .TS
  617. l l.
  618. SETS
  619. src2 = GENREG + regdef2 + regind2 + reginddef2 + relative2 +
  620. \h'\w'= 'u'reldef2 + addr_external + const2 + LOCAL + ILOCAL +
  621. \h'\w'= 'u'autodec + autoinc .
  622. dst2 = src2 - ( const2 + addr_external ) .
  623. xsrc2 = src2 + ftoint .
  624. src1 = regdef1 + regind1 + reginddef1 + relative1 + reldef1 .
  625. dst1 = src1 .
  626. src1or2 = src1 + src2 .
  627. src4 = relative4 + regdef4 + DLOCAL + regind4 .
  628. dst4 = src4 .
  629. .TE
  630. Permissible in the set construction are all the usual set operators, i.e.
  631. .IP +
  632. set union
  633. .IP -
  634. set difference
  635. .IP *
  636. set intersection
  637. .PP
  638. Normal operator priorities apply, and parentheses can be
  639. used.
  640. Every token identifier is also a set identifier
  641. denoting the singleton collection of tokens containing
  642. just itself.
  643. Every register property as defined above is also a set
  644. matching all registers with that property.
  645. The standard set identifier ALL denotes the collection of
  646. all tokens.
  647. .NH 2
  648. Instruction definitions
  649. .PP
  650. In the next part of the table the instructions for the machine
  651. are declared together with information about their operands.
  652. Example for the PDP-11(very incomplete):
  653. .DS
  654. .ta 8 16 24 32 40 48 56 64
  655. INSTRUCTIONS
  656. /* default cost */
  657. cost(2,600)
  658. /* Normal instructions */
  659. adc dst2:rw:cc .
  660. add src2:ro,dst2:rw:cc cost(2,450).
  661. ash src2:ro,REG:rw:cc .
  662. ashc src2:ro,REGPAIR+ODDREG:rw .
  663. asl dst2:rw:cc .
  664. asr dst2:rw:cc .
  665. bhis "bcc" label .
  666. /* floating point instructions */
  667. movf "ldf" fsrc,freg .
  668. movf "stf" freg,fdst .
  669. .DE
  670. As the examples show an instruction definition consists of the name
  671. of the instruction,
  672. optionally followed by an assembler mnemonic in
  673. quotes-default is the name itself-and then
  674. a list of operands,
  675. optionally followed by the cost and then a period.
  676. If the cost is omitted the cost just after the word
  677. INSTRUCTIONS is assumed,
  678. if that is also omitted the cost is zero.
  679. The cost must be known by
  680. .I cg
  681. of course if it has multiple
  682. code generation paths to choose from.
  683. .PP
  684. For each operand we have the set of possible token values,
  685. followed by a qualifier that can be
  686. .IP :ro
  687. signifies that this operand is read only,
  688. so it can be replaced by a register with the same contents
  689. if available.
  690. .IP :rw
  691. signifies that the operand is read-write
  692. .IP :wo
  693. signifies that the operand is write only.
  694. .IP :cc
  695. says that after the instruction is finished, the condition codes
  696. are set to this operand.
  697. If none of the operands have the :cc qualifier set,
  698. .I cg
  699. will assume that condition codes were unaffected
  700. (but see below).
  701. .PP
  702. The first three qualifiers are of course mutually exclusive.
  703. The :ro qualifier does not cause any special action in the current
  704. implementation, and the :wo and :rw qualifiers are treated equal.
  705. It must be recommended however to be precise in the specifications,
  706. since later enhancements to the code generator might use them.
  707. .PP
  708. As the last examples show it is not necessary to give one definition
  709. for an instruction.
  710. There are machines that have very unorthogonal instruction sets,
  711. in fact most of them do,
  712. and it is possible to declare each possible combination
  713. of operands.
  714. The
  715. .I cgg
  716. program will check all uses of the instruction to find out which
  717. one was meant.
  718. .PP
  719. Although not in the PDP-11 example above there is a possibility
  720. to describe instructions that have side effects to registers not
  721. in the operand list.
  722. The only thing possible is to say that the instruction is destructive
  723. to some registers or the condition codes, by following the operand list
  724. with the word
  725. .I kills
  726. and a list of the things destroyed.
  727. Example for some hypothetic accumulator machine:
  728. .DS
  729. add source2:ro kills ACCU :cc .
  730. .DE
  731. .PP
  732. The cost fields in the definitions for tokens and instructions
  733. are added together when generating code.
  734. It depends on the machine at hand whether the costs are orthogonal
  735. enough to make use of both these costs,
  736. in extreme cases every combination of instructions and operands
  737. can be given in this section,
  738. all with their own costs.
  739. .NH 2
  740. Expressions
  741. .PP
  742. Throughout the rest of the table expressions can be used in some
  743. places.
  744. This section will give the syntax and semantics of expressions.
  745. There are four types of expressions: integer, address, register and undefined.
  746. Really the type register is nonexistent as such,
  747. for each register expression
  748. .I cgg
  749. keeps a set of possible values,
  750. and this set can be seen as the real type.
  751. .PP
  752. Type checking is performed by
  753. .I cgg .
  754. An operator with at least one undefined operand returns undefined except
  755. for the defined() function mentioned below.
  756. An undefined expression is interpreted as FALSE when it is needed
  757. as a truth value.
  758. It is the responsibility of the table writer to ensure no undefined
  759. expressions are ever used as initialisers for token attributes.
  760. This is unfortunately almost impossible to check for
  761. .I cgg
  762. so be careful.
  763. .LP
  764. Basic terms in an expression are
  765. .IP number 16
  766. A number is a constant of type integer.
  767. Also usable is an identifier defined to a number in the constant
  768. definition section.
  769. .IP """string"""
  770. A string within double quotes is a constant of type address.
  771. All the normal C style escapes may be used within the string.
  772. Also usable is an identifier defined to a string in the constant
  773. definition section.
  774. .IP [0-9][bf]
  775. This must be read as a grep-pattern.
  776. It evaluates to a string that is the label name for the
  777. temporary label meant.
  778. More about this in the section on code rules.
  779. .IP REGIDENT
  780. The name of a register is a constant of type register.
  781. .IP $\fIi\fP
  782. A dollarsign followed by a number is the representation of the argument
  783. of EM instruction \fI\fP.
  784. The type of the operand is dependent on the instruction,
  785. sometimes it is integer,
  786. sometimes it is address.
  787. It is undefined when the instruction has no operand.
  788. Watch out for instructions with type-letter w.
  789. They can occur without an operand.
  790. Check for this in your code rule with the defined() pseudo function.
  791. .br
  792. If you cannot imagine the operand of the instruction ever to be
  793. something different from a plain integer, the type is integer,
  794. otherwise it is address.
  795. .br
  796. Those who want to know it exactly, the integer instruction types
  797. are the instructions marked with the
  798. type-letters c,f,l,n,o,s,r,w,z in the EM manual.
  799. .br
  800. .I Cg
  801. makes all necessary conversions for you,
  802. like adding EM_BSIZE to positive arguments of instructions
  803. dealing with locals,
  804. prepending underlines to global names,
  805. converting code labels into a unique representation etc.
  806. Details about this can be found in the section about
  807. machine dependent C code.
  808. .IP %1
  809. This in general means the token mentioned first in the
  810. stack pattern.
  811. When used inside an expression the token must be a simple register.
  812. Type of this is register.
  813. .IP %1.off
  814. This means attribute "off" of the first stack pattern token.
  815. Type is the same as that of attribute "off".
  816. To use this expression implies a check that all tokens
  817. in the set used have the same attribute in the same place.
  818. .IP %off
  819. This means attribute "off" in the `current' token.
  820. This can only be used when no confusion is possible about which token
  821. was meant, eg. in the optional boolean expressions following token sets
  822. in the move and test rules, in coercions or in the kills section inside
  823. the code rules.
  824. Same check as above.
  825. .IP %1.1
  826. This is the first subregister of the first token.
  827. Previous comments apply.
  828. .IP %b
  829. A percent sign followed by a lowercase letter
  830. stands for an allocated register.
  831. This is the second allocated register.
  832. .IP %a.2
  833. The second subregister of the first allocated register.
  834. .PP
  835. All normal C operators apply to integers,
  836. the + operator on addresses behaves as you would expect
  837. and the only operators allowed on register expressions
  838. are == and != .
  839. Furthermore there are some special `functions':
  840. .IP defined(e) 16
  841. Returns 1 if expression
  842. .I e
  843. is defined, 0 otherwise.
  844. .IP samesign(e1,e2)
  845. Returns 1 if integer expression
  846. .I e1
  847. and
  848. .I e2
  849. have the same sign.
  850. .IP sfit(e1,e2)
  851. Returns 1 if integer expression
  852. .I e1
  853. fits as a signed integer
  854. into a field of
  855. .I e2
  856. bits, 0 otherwise.
  857. .IP ufit(e1,e2)
  858. Same as above but now for unsigned
  859. .I e1 .
  860. .IP rom($a,n)
  861. Integer expression giving word
  862. .I n
  863. from the \fBrom\fP descriptor
  864. pointed at by EM instruction
  865. number
  866. .I a
  867. in the EM-pattern.
  868. Undefined if that descriptor does not exist.
  869. .IP is_rom($a)
  870. Integer expression indicating whether EM instruction number
  871. .I a
  872. in the EM-pattern refers to ROM. This may be useful for generating
  873. position-independent code with the ROM in read-only memory.
  874. .I Is_rom
  875. enables one to see the difference between ROM references and other data
  876. references.
  877. .IP loww($a)
  878. Returns the lower half of the argument of EM instruction number
  879. .I a .
  880. This is used to split the arguments of a \fBldc\fP instruction.
  881. .IP highw($a)
  882. Same for upper half.
  883. .LP
  884. The next two `functions' are only needed in a table that
  885. implements register variables.
  886. .IP inreg(e) 16
  887. Returns the status of the local variable with offset
  888. .I e
  889. from the localbase.
  890. Value is an integer,
  891. negative if the local was not allowed as a register
  892. variable,
  893. zero if it was allowed but not assigned to a register,
  894. and the type of the register if it was assigned to a register.
  895. This makes it possible to write
  896. .DS
  897. inreg($1)==reg_pointer
  898. .DE
  899. and similar things.
  900. .IP regvar(e,t)
  901. Type of this is register.
  902. It returns the register the local with offset
  903. .I e
  904. is assigned to.
  905. The table writer guarantees the register is one of type
  906. .I t ,
  907. with
  908. .I t
  909. one of reg_any, reg_loop, reg_pointer or reg_float.
  910. If
  911. .I t
  912. is omitted reg_any is assumed.
  913. Undefined if inreg(\fIe\fP)<=0 .
  914. .LP
  915. The next two `functions' are only needed in a table that
  916. uses the top element size information.
  917. .IP topeltsize($a) 16
  918. Returns the size of the element on top of the EM-stack at the label
  919. identified by $a. This can be used to put the top of the stack in a
  920. register at the moment of an unconditional jump. At an unconditional jump,
  921. the size of the top-element will always look 0.
  922. .IP fallthrough($a)
  923. Returns 1 if the label identified by $a can be reached via fallthrough, 0
  924. otherwise.
  925. .NH 2
  926. Token descriptions
  927. .PP
  928. Throughout the rest of the table tokens must be described,
  929. be it as operands of instructions or as stack-replacements.
  930. In all those cases we will speak about a token description.
  931. The possibilities for these will be described here.
  932. .PP
  933. All expressions of type register are token descriptions.
  934. The construct %1 means the token matched first in the stack pattern.
  935. All other token descriptions are those that are built on the spot.
  936. They look like this:
  937. .DS
  938. { <tokenname> , <list of token attribute initializing expressions> }
  939. .DE
  940. All expressions are type-checked by
  941. .I cgg ,
  942. and the number of initializers is also checked.
  943. .PP
  944. A special case of the last token descriptions occurs when
  945. the token name is `LOCAL' or `DLOCAL' and the table uses register
  946. variables. The first token attribute then must be of type integer and
  947. the token description is automagically replaced by the register chosen
  948. if the LOCAL (wordsize) or DLOCAL (twice the wordsize) was assigned
  949. to a register.
  950. .NH 2
  951. Code rules
  952. .PP
  953. The largest section of the tables consists of the code generation rules.
  954. They specify EM patterns, stack patterns, code to be generated etc.
  955. Broadly the syntax is
  956. .DS L
  957. code rule : EM-part code-part
  958. EM-part : EM-pattern | procedure-heading
  959. code-part : code-description | procedure-call
  960. code-description : stackpattern kills allocates generates yields leaving
  961. .DE
  962. Ignoring the "procedure"-part for now, the description for the EM-pattern
  963. and the code-description follows.
  964. Almost everything here is optional, the minimum code rule
  965. is:
  966. .DS
  967. pat nop
  968. .DE
  969. that will simply throw away
  970. .I nop
  971. instructions.
  972. .NH 3
  973. The EM pattern
  974. .PP
  975. The EM pattern consists of a list of EM mnemonics
  976. preceded by the word
  977. .I pat
  978. optionally followed by a boolean expression.
  979. Examples:
  980. .DS
  981. pat \fBloe\fP
  982. .DE
  983. will match a single \fBloe\fP instruction,
  984. .DS
  985. pat \fBloc\fP \fBloc\fP \fBcif\fP $1==2 && $2==8
  986. .DE
  987. is a pattern that will match
  988. .DS
  989. \fBloc\fP 2
  990. \fBloc\fP 8
  991. \fBcif\fP
  992. .DE
  993. and
  994. .DS
  995. pat \fBlol\fP \fBinc\fP \fBstl\fP $1==$3
  996. .DE
  997. will match for example
  998. .DS
  999. .ta 10m 20m 30m 40m 50m 60m
  1000. \fBlol\fP 6 \fBlol\fP -2 \fBlol\fP 4
  1001. \fBinc\fP \fBinc\fP but \fInot\fP \fBinc\fP
  1002. \fBstl\fP 6 \fBstl\fP -2 \fBstl\fP -4
  1003. .DE
  1004. A missing boolean expression evaluates to TRUE.
  1005. .PP
  1006. The code generator will match the longest EM pattern on every occasion,
  1007. if two patterns of the same length match the first in the table will be chosen,
  1008. while all patterns of length greater than or equal to three are considered
  1009. to be of the same length.
  1010. This rule of three is an unfortunate implementation dependent restriction,
  1011. but patterns longer than three EM instructions are luckily not needed
  1012. too often.
  1013. .PP
  1014. The EM mnemonic may also be the pseudo-instruction \fBlab\fP, which matches
  1015. a label. Its argument can be used in testing on topeltsize and
  1016. fallthrough. When this pattern is specified, the label should be defined
  1017. explicitly with a
  1018. .I labeldef
  1019. statement.
  1020. .PP
  1021. Following the EM-pattern there may be more than one code
  1022. rule,
  1023. .I cg
  1024. will choose using heuristics and the cost
  1025. information provided with the instruction and token
  1026. definitions.
  1027. Owing to parsing reasons of the table, the word
  1028. .I with
  1029. (see below)
  1030. is mandatory when there are more code rules attached to one
  1031. EM-pattern.
  1032. The stack pattern may be empty however.
  1033. .NH 3
  1034. The stack pattern
  1035. .PP
  1036. The optional stack pattern is a list of token sets preceded by the word
  1037. .I with .
  1038. The token sets are usually represented by set identifiers for clarity.
  1039. No boolean expression is allowed here.
  1040. The first expression is the one that matches the top of the stack.
  1041. .PP
  1042. If the pattern is followed by the word STACK
  1043. it only matches if there is nothing
  1044. else on the fake stack,
  1045. and the code generator will stack everything not matched at the start
  1046. of the rule.
  1047. .PP
  1048. The pattern can be preceded with the word
  1049. .I exact
  1050. following the
  1051. .I with
  1052. that tells the code generator not to try to coerce to the pattern
  1053. but only to use it when it is already present on the fake stack.
  1054. There are two reasons for this construction,
  1055. correctness and speed.
  1056. It is needed for correctness when the pattern contains a register
  1057. that is not transparent when data is moved through it.
  1058. .LP
  1059. Example: on the PDP-11 the shortest code for
  1060. .DS
  1061. \fBlae\fP a
  1062. \fBloi\fP 8
  1063. \fBlae\fP b
  1064. \fBsti\fP 8
  1065. .DE
  1066. is
  1067. .DS
  1068. movf _a,fr0
  1069. movf fr0,_b
  1070. .DE
  1071. if the floating point processor is in double
  1072. precision mode and fr0 is free.
  1073. Unfortunately this is not correct since a trap can occur on certain
  1074. kinds of data.
  1075. This could happen if there was a stack pattern for \fBsti\fP\ 8
  1076. like this:
  1077. .DS
  1078. with DBLREG
  1079. .DE
  1080. The code generator would then find that coercing the 8-byte global _a
  1081. to a floating point register and then storing it to _b was the cheapest,
  1082. if the space/time knob was turned far enough to space.
  1083. This can be prevented by changing the stack pattern to
  1084. .DS
  1085. with exact DBLREG
  1086. .DE
  1087. It is unfortunate that the type information is no longer present,
  1088. since if _a really is a floating point number the move could be
  1089. made without error.
  1090. .PP
  1091. The second reason for the
  1092. .I exact
  1093. construct is speed.
  1094. When the code generator has a long list of possible stack patterns
  1095. for one EM pattern it can waste much time trying to find coercions
  1096. to all of them, while the mere presence of such a long list
  1097. indicates that the table writer has given many special cases.
  1098. Prepending all the special cases by
  1099. .I exact
  1100. will stop the code generator from trying to find things
  1101. that either cannot be done,
  1102. or are too expensive anyway.
  1103. .PP
  1104. So in general it is wise to prepend all stack patterns that
  1105. cannot be made by coercions with
  1106. .I exact .
  1107. .PP
  1108. Using both
  1109. .I exact
  1110. and STACK in the stack pattern has the effect that the rule will
  1111. only be taken if there is nothing else on the fake stack.
  1112. .NH 3
  1113. The kills part
  1114. .PP
  1115. The optional kills part describes certain tokens
  1116. that should neither remain on
  1117. the fake stack, nor remembered as contents of registers.
  1118. This is usually only required with store operations.
  1119. The entire fake stack, except for the part matched in the stack pattern,
  1120. is searched for tokens matching the expression and they are copied
  1121. to the real stack.
  1122. Every register that contains the token is marked as empty.
  1123. .PP
  1124. Syntax is
  1125. .DS
  1126. kills <list of things to kill separated by commas>
  1127. thing to kill : token set optionally followed by boolean expression
  1128. .DE
  1129. Example:
  1130. .DS
  1131. kills regind2 %reg != lb || %off == $1
  1132. .DE
  1133. is a kills part used for example in the \fBinl\fP or \fBstl\fP code rule.
  1134. It removes all register offsetted tokens where the register is not the
  1135. localbase plus the local in which the store is done.
  1136. The necessity for this can be seen from the following example:
  1137. .DS
  1138. \fBlol\fP 4
  1139. \fBinl\fP 4
  1140. \fBstl\fP 6
  1141. .DE
  1142. Without a proper kills part in the rule for \fBinl\fP code would
  1143. be generated as here
  1144. .DS
  1145. inc 4(r5)
  1146. mov 4(r5),6(r5)
  1147. .DE
  1148. so local 6 would be given the new value of local 4 instead of the old
  1149. as the EM code prescribed.
  1150. .PP
  1151. When generating code for an EM-instruction like
  1152. .B sti
  1153. it is necessary to write a line in the table like
  1154. .DS
  1155. kills all_except_constant_or_register
  1156. .DE
  1157. where the long identifier is a set containing all tokens
  1158. that can be the destination of some random indirect store.
  1159. These indirect stores are the main reason to prevent this
  1160. .I kills
  1161. line to be deduced automatically by
  1162. .I cgg .
  1163. .PP
  1164. When generating something like a branch instruction it
  1165. might be needed to empty the fake stack completely.
  1166. This can of course be done with
  1167. .DS
  1168. kills ALL
  1169. .DE
  1170. or by ending the stack pattern with the word STACK,
  1171. if the stack pattern does not start with
  1172. .I exact .
  1173. The latter does not erase the contents of registers.
  1174. .PP
  1175. It is unfortunate that this part is still present in the table
  1176. but it is too much for now to let the
  1177. .I cgg
  1178. program discover what rules ruin what kind of tokens.
  1179. Maybe some day .....
  1180. .NH 3
  1181. The allocates part
  1182. .PP
  1183. The optional register allocation part describes the registers needed.
  1184. Syntax is
  1185. .DS
  1186. uses <list of use elements separated by commas>
  1187. .DE
  1188. where itemlist is a list of three kinds of things:
  1189. .IP 1)
  1190. .I reusing
  1191. < a token description >, for example %1.
  1192. .br
  1193. This will instruct the code generator that all registers
  1194. contained in this token can be reused if they are not used
  1195. in another token on the fakestack,
  1196. so that they are available for allocation in this
  1197. .I uses
  1198. line
  1199. if they were only used in that token.
  1200. See example below.
  1201. .IP 2)
  1202. a register property.
  1203. .br
  1204. This will allocate a register with that property,
  1205. that is marked as empty at this point.
  1206. Look ahead can be performed if there is more than one register available.
  1207. .IP 3)
  1208. a register property with initialization.
  1209. .br
  1210. This will allocate the register as in 2) but will also
  1211. initialize it.
  1212. This eases the task of the code generator because it can
  1213. find a register already filled with the right value
  1214. if it exists.
  1215. .LP
  1216. Examples:
  1217. .DS
  1218. uses ODDREG
  1219. .DE
  1220. will allocate an odd register, while
  1221. .DS
  1222. uses REG={regind2,lb,$1}
  1223. .DE
  1224. will allocate a register while simultaneously filling it with
  1225. the asked value.
  1226. .br
  1227. Inside the coercion from xsrc2 to REG in the PDP-11 table
  1228. the following line can be found.
  1229. .DS
  1230. uses reusing %1, REG=%1
  1231. .DE
  1232. This tells the code generator that registers contained in %1 can be used
  1233. again and asks to fill the register allocated with %1.
  1234. So if %1={regind2,r3,"4"} and r3 is not in use elsewhere on the fake stack
  1235. the following code might be generated.
  1236. .DS
  1237. mov 4(r3),r3
  1238. .DE
  1239. In the rest of the line the registers allocated can be named by
  1240. %a and %b.1,%b.2, i.e. with lower case letters
  1241. in order of allocation.
  1242. .NH 3
  1243. The generates part
  1244. .PP
  1245. Code to be generated, also optionally, is specified as
  1246. the word
  1247. .I gen
  1248. followed by a list of items of the following kind:
  1249. .IP 1)
  1250. An instruction name followed by a comma-separated
  1251. list of token descriptions.
  1252. .I Cgg
  1253. will search the instruction definitions for the machine to find a suitable
  1254. instruction.
  1255. At code generation time the assembler name of the
  1256. instruction will be output followed by a space,
  1257. followed by a comma separated list of tokens.
  1258. .br
  1259. In the table an instruction without operands must be
  1260. followed by a period.
  1261. The author of
  1262. .I cgg
  1263. could not get
  1264. .I yacc
  1265. to accept his syntax without it.
  1266. Sorry about this.
  1267. .IP 2)
  1268. a
  1269. .I move
  1270. call.
  1271. This has the following syntax:
  1272. .DS
  1273. move <token description>,<token description>
  1274. .DE
  1275. Moves are handled specially since that enables the code generator
  1276. to keep track of register contents.
  1277. Example:
  1278. .DS
  1279. move r3,{regind2,lb,$1}
  1280. .DE
  1281. will generate code to move r3 to $1(r5) except when
  1282. r3 already was a copy of $1(r5).
  1283. Then the code will be omitted.
  1284. The rules describing how to move things to each other
  1285. can be found in the move definitions section described below.
  1286. .IP 3)
  1287. For machines that have condition codes,
  1288. which alas most of them do,
  1289. there are provisions to remember condition code settings
  1290. and prevent needless testing.
  1291. To set the condition code to a token put in the code the following call:
  1292. .DS
  1293. test <token description>
  1294. .DE
  1295. This will generate a test if the condition codes
  1296. were not already set to that token.
  1297. The rules describing how to test things
  1298. can be found in the test definitions section described below.
  1299. See also the :cc qualifier that can be used at instruction
  1300. definition time.
  1301. .IP 4)
  1302. The
  1303. .I return
  1304. statement.
  1305. Only used when register variables are in use.
  1306. This statement causes a call to the machine dependent
  1307. C-routine
  1308. .I regreturn .
  1309. Explanation of this must wait for the description of the
  1310. file mach.c below.
  1311. .IP 5)
  1312. The
  1313. .I labeldef
  1314. statement. Its only argument should be that of the
  1315. .I lab
  1316. pseudo-instruction. This is needed to generate local labels when the
  1317. top element size information is used. It takes the form
  1318. .DS
  1319. labeldef $i
  1320. .DE
  1321. .IP 6)
  1322. A temporary label of the form <digit>: may be placed here.
  1323. Expressions of the form [0-9][bf] in this code rule
  1324. generate the same string as is used for this label.
  1325. The code generator system could probably easily be changed
  1326. to make this work for assemblers that do not support this
  1327. type of label by generating unique labels itself.
  1328. Implementation of this is not contemplated at the moment,
  1329. bad luck if your assembler cannot do it.
  1330. .NH 3
  1331. Stack replacement
  1332. .PP
  1333. The optional stack replacement is a possibly empty list
  1334. of tokens to be pushed onto the fake stack.
  1335. It start with the word
  1336. .I yields ,
  1337. and is followed by a list of token descriptions.
  1338. .PP
  1339. All tokens matched by the stack pattern at the beginning of the code rule
  1340. are first removed and their registers deallocated.
  1341. Items are pushed in the order of appearance.
  1342. This means that the last item will be on the top of the
  1343. stack after the push.
  1344. So if the stack pattern contained two sets
  1345. and you want to push them back unchanged,
  1346. you have to specify as stack replacement
  1347. .DS
  1348. yields %2 %1
  1349. .DE
  1350. and not the other way around.
  1351. This is known to cause errors in tables so watch out for
  1352. this!
  1353. .NH 3
  1354. EM replacement
  1355. .PP
  1356. In exceptional cases it might be useful to leave part of an EM-pattern
  1357. undone.
  1358. For example, a \fBsdl\fP instruction might
  1359. be split into two \fBstl\fP instructions
  1360. when there is no 4-byte quantity on the stack.
  1361. The EM replacement part allows
  1362. one to express this.
  1363. It is activated by the word
  1364. .I leaving .
  1365. .LP
  1366. Example:
  1367. .DS
  1368. leaving \fBstl\fP $1 \fBstl\fP $1+2
  1369. .DE
  1370. The instructions are inserted in the stream so that they can match
  1371. the first part of a pattern in the next step.
  1372. Note that since the code generator traverses the EM instructions in a strict
  1373. linear fashion,
  1374. it is impossible to let the EM replacement match later parts of a pattern.
  1375. So if there is a pattern
  1376. .DS
  1377. \fBloc\fP \fBstl\fP $1==0
  1378. .DE
  1379. and the input is
  1380. .DS
  1381. \fBloc\fP 0 \fBsdl\fP 4
  1382. .DE
  1383. the \fBloc\fP\ 0 will be processed first,
  1384. then the \fBsdl\fP might be split into two \fBstl\fP's but the pattern
  1385. cannot match now.
  1386. .NH 3
  1387. Examples
  1388. .PP
  1389. A list of examples for the PDP-11 is given here.
  1390. Far from being complete it gives examples of most kinds
  1391. of instructions.
  1392. .DS
  1393. .ta 7.5c
  1394. pat loc yields {const2, $1}
  1395. pat ldc yields {const2, loww($1)} {const2, highw($1)}
  1396. .DE
  1397. These simple patterns just push one or more tokens onto the fake stack.
  1398. .DS
  1399. .ta 7.5c
  1400. pat lof
  1401. with REG yields {regind2,%1,$1}
  1402. with exact regconst2 yields {regind2,%1.reg,$1+%1.off}
  1403. with exact addr_external yields {relative2,$1+%1.off}
  1404. with exact addr_local yields {LOCAL, %1.ind + $1,2}
  1405. .DE
  1406. This pattern shows the possibility to do different things
  1407. depending on the fake stack contents,
  1408. there are some rules for some specific cases plus a general rule,
  1409. not preceded by
  1410. .I exact
  1411. that can always be taken after a coercion,
  1412. if necessary.
  1413. .DS
  1414. .ta 7.5c
  1415. pat lxl $1>3
  1416. uses REG={LOCAL, SL, 2}, REG={const2,$1-1}
  1417. gen 1:
  1418. move {regind2,%a, SL},%a
  1419. sob %b,{label,1b} yields %a
  1420. .DE
  1421. This rule shows register allocation with initialisation,
  1422. and the use of a temporary label.
  1423. The constant SL used here is defined to be the offset from lb
  1424. of the static link,
  1425. that is pushed by the Pascal compiler as the last argument of
  1426. a function.
  1427. .DS
  1428. .ta 7.5c
  1429. pat stf
  1430. with regconst2 xsrc2
  1431. kills allexeptcon
  1432. gen move %2,{regind2,%1.reg,$1+%1.off}
  1433. with addr_external xsrc2
  1434. kills allexeptcon
  1435. gen move %2,{relative2,$1+%1.off}
  1436. .DE
  1437. This rule shows the use of a
  1438. .I kills
  1439. part in a store instruction.
  1440. The set allexeptcon contains all tokens that can be the destination
  1441. of an indirect store.
  1442. .DS
  1443. .ta 7.5c
  1444. pat sde
  1445. with exact FLTREG
  1446. kills posextern
  1447. gen move %1,{relative4,$1}
  1448. with exact ftolong
  1449. kills posextern
  1450. gen setl.
  1451. movfi %1.reg,{relative4,$1}
  1452. seti.
  1453. with src2 src2
  1454. kills posextern
  1455. gen move %1, {relative2, $1 }
  1456. move %2, {relative2, $1+2}
  1457. .DE
  1458. The rule for
  1459. .B sde
  1460. shows the use of the
  1461. .I exact
  1462. clause in both qualities,
  1463. the first is for correctness,
  1464. the second for efficiency.
  1465. The third rule is taken by default,
  1466. resulting in two separate stores,
  1467. nothing better exists on the PDP-11.
  1468. .DS
  1469. .ta 7.5c
  1470. pat sbi $1==2
  1471. with src2 REG
  1472. gen sub %1,%2 yields %2
  1473. with exact REG src2-REG
  1474. gen sub %2,%1
  1475. neg %1 yields %1
  1476. .DE
  1477. This rule for
  1478. .I sbi
  1479. has a normal first part,
  1480. and a hand optimized special case as its second part.
  1481. .DS
  1482. .ta 7.5c
  1483. pat mli $1==2
  1484. with ODDREG src2
  1485. gen mul %2,%1 yields %1
  1486. with src2 ODDREG
  1487. gen mul %1,%2 yields %2
  1488. .DE
  1489. This shows the general property for rules with commutative
  1490. operators,
  1491. heuristics or look ahead will have to decide which rule is the best.
  1492. .DS
  1493. .ta 7.5c
  1494. pat loc sli $1==1 && $2==2
  1495. with REG
  1496. gen asl %1 yields %1
  1497. .DE
  1498. A simple rule involving a longer EM-pattern,
  1499. to make use of a specialized instruction available.
  1500. .DS
  1501. .ta 7.5c
  1502. pat loc loc cii $1==1 && $2==2
  1503. with src1or2
  1504. uses reusing %1,REG
  1505. gen movb %1,%a yields %a
  1506. .DE
  1507. A somewhat more complicated example of the same.
  1508. Note the
  1509. .I reusing
  1510. clause.
  1511. .DS
  1512. .ta 7.5c
  1513. pat loc loc loc cii $1>=0 && $2==2 && $3==4
  1514. leaving loc $1 loc 0
  1515. .DE
  1516. Shows a trivial example of EM-replacement.
  1517. This is a rule that could be done by the
  1518. peephole optimizer,
  1519. if word order in longs was defined in EM.
  1520. On a `big-endian' machine the two replacement
  1521. instructions would be the other way around.
  1522. .DS
  1523. .ta 7.5c
  1524. pat and $1==2
  1525. with const2 REG
  1526. gen bic {const2,~%1.num},%2 yields %2
  1527. with REG const2
  1528. gen bic {const2,~%2.num},%1 yields %1
  1529. with REG REG
  1530. gen com %1
  1531. bic %1,%2 yields %2
  1532. .DE
  1533. Shows the way you have to twist the table,
  1534. if an
  1535. .I and -instruction
  1536. is not available on your machine.
  1537. .DS
  1538. .ta 7.5c
  1539. pat set $1==2
  1540. with REG
  1541. uses REG={const2,1}
  1542. gen ash %1,%a yields %a
  1543. .DE
  1544. Shows the building of a word-size set.
  1545. .DS
  1546. .ta 7.5c
  1547. pat lae aar $2==2 && rom($1,3)==1 && rom($1,1)==0
  1548. leaving adi 2
  1549. pat lae aar $2==2 && rom($1,3)==1 && rom($1,1)!=0
  1550. leaving adi 2 adp 0-rom($1,1)
  1551. .DE
  1552. Two rules showing the use of the rom pseudo function,
  1553. and some array optimalisation.
  1554. .DS
  1555. .ta 7.5c
  1556. pat bra
  1557. with STACK
  1558. gen jbr {label, $1}
  1559. .DE
  1560. A simple jump.
  1561. The stack pattern guarantees that everything will be stacked
  1562. before the jump is taken.
  1563. .DS
  1564. pat lab topeltsize($1)==2 && !fallthrough($1)
  1565. gen labeldef $1 yields r0
  1566. pat lab topeltsize($1)==2 && fallthrough($1)
  1567. with src2
  1568. gen move %1,r0
  1569. labeldef $1 yields r0
  1570. pat lab topeltsize($1)!=2
  1571. with STACK
  1572. kills all
  1573. gen labeldef $1
  1574. pat bra topeltsize($1)==2
  1575. with src2 STACK
  1576. gen move %1,d0
  1577. jbr {label, $1}
  1578. pat bra topeltsize($1)!=2
  1579. with STACK
  1580. gen jbr {label, $1}
  1581. .DE
  1582. The combination of these patterns make sure that the top of the EM-stack will
  1583. be in register r0 whenever necessary. The top element size mechanism will
  1584. also show a size of 0 whenever a conditional branch to a label
  1585. occurs. This saves a lot of patterns and hardly decreases performance.
  1586. When the same register is used to return function results, this can save
  1587. many moves to and from the stack.
  1588. .DS
  1589. .ta 7.5c
  1590. pat cal
  1591. with STACK
  1592. gen jsr pc,{label, $1}
  1593. .DE
  1594. A simple call.
  1595. Same comments as previous rule.
  1596. .DS
  1597. .ta 7.5c
  1598. pat lfr $1==2 yields r0
  1599. pat lfr $1==4 yields r1 r0
  1600. .DE
  1601. Shows the return area conventions of the PDP-11 table.
  1602. At this point a reminder:
  1603. the
  1604. .B asp
  1605. instruction, and some other instructions must leave
  1606. the function return area intact.
  1607. See the defining document for EM for exact information.
  1608. .DS
  1609. .ta 7.5c
  1610. pat ret $1==0
  1611. with STACK
  1612. gen mov lb,sp
  1613. rts pc
  1614. .DE
  1615. This shows a rule for
  1616. .B ret
  1617. in a table not using register variables.
  1618. In a table with register variables the
  1619. .I gen
  1620. part would just contain
  1621. .I return .
  1622. .DS
  1623. .ta 7.5c
  1624. pat blm
  1625. with REG REG
  1626. uses REG={const2,$1/2}
  1627. gen 1:
  1628. mov {autoinc,%2},{autoinc,%1}
  1629. sob %a,{label,1b}
  1630. .DE
  1631. This rule for
  1632. .B blm
  1633. already uses three registers of the same type.
  1634. .I Cgg
  1635. contains code to check all your rules
  1636. to see if they can be applied from an empty fakestack.
  1637. It uses the marriage thesis from Hall,
  1638. a thesis from combinatorial mathematics,
  1639. to accomplish this.
  1640. .DS
  1641. .ta 7.5c
  1642. pat exg $1==2
  1643. with src2 src2 yields %1 %2
  1644. .DE
  1645. This rule shows the exchanging of two elements on the fake stack.
  1646. .NH 2
  1647. Code rules using procedures
  1648. .PP
  1649. To start this section it must be admitted at once that the
  1650. word procedure is chosen here mainly for its advertising
  1651. value.
  1652. It more resembles a glorified goto but this of course can
  1653. not be admitted in the glossy brochures.
  1654. This document will continue to use the word
  1655. procedure.
  1656. .PP
  1657. The need for procedures was felt after the first version of
  1658. the code generator system was made,
  1659. mainly because of conditional instructions.
  1660. Often the code sequences for
  1661. .B tlt ,
  1662. .B tle ,
  1663. .B teq ,
  1664. .B tne ,
  1665. .B tge
  1666. and
  1667. .B tgt
  1668. were identical apart from one opcode in the code rule.
  1669. The code sequence had to be written out six times however.
  1670. Not only did this increase the table size and bore the
  1671. table writer, it also led to errors when changing the table
  1672. since it happened now and then that five out of six
  1673. rules were changed.
  1674. .PP
  1675. In general the procedures in this table format are used to
  1676. keep one copy instead of six of the code rules for all
  1677. sorts of conditionals and one out of two for things like
  1678. increment/decrement.
  1679. .PP
  1680. And now the syntax, first the procedure definition,
  1681. which must indeed be defined before the call because
  1682. .I cgg
  1683. is one-pass.
  1684. The procedure heading replaces the EM-pattern in a code rule
  1685. and looks like this:
  1686. .DS
  1687. proc <identifier> <optional example>
  1688. .DE
  1689. The identifier is used in later calls and the example must
  1690. be used if expressions like $1 are used in the code rule.
  1691. .DS
  1692. <optional example> : example <list of EM-instructions>
  1693. .DE
  1694. so an example looks just like an EM-pattern, but without
  1695. the optional boolean expression.
  1696. The example is needed to know the types of $1 expressions.
  1697. The current version of
  1698. .I cgg
  1699. does not check correctness of the example, so be careful.
  1700. .PP
  1701. A procedure is called with string-parameters,
  1702. that are assembler opcodes.
  1703. They can be accessed by appending the string `[<number>]'
  1704. to a table opcode, where <number> is the parameter number.
  1705. The string `*' can be used as an equivalent for `[1]'.
  1706. Just in case this is not clear, here is an example for
  1707. a procedure to increment/decrement a register.
  1708. .DS
  1709. .ta 7.5c
  1710. incop REG:rw:cc . /* in the INSTRUCTIONS part of course */
  1711. proc incdec
  1712. with REG
  1713. gen incop* %1 yields %1
  1714. .DE
  1715. The procedure is called with parameter "inc" or "dec".
  1716. .PP
  1717. The procedure call is given instead of the code-part of the
  1718. code rule and looks like this
  1719. .DS
  1720. call <identifier> '(' <comma-separated list of strings> ')'
  1721. .DE
  1722. which leads to the following large example:
  1723. .DS
  1724. .ta 7.5c
  1725. proc bxx example beq
  1726. with src2 src2 STACK
  1727. gen cmp %2,%1
  1728. jxx* {label, $1}
  1729. pat blt call bxx("jlt")
  1730. pat ble call bxx("jle")
  1731. pat beq call bxx("jeq")
  1732. pat bne call bxx("jne")
  1733. pat bgt call bxx("jgt")
  1734. pat bge call bxx("jge")
  1735. .DE
  1736. .NH 2
  1737. Move definitions
  1738. .PP
  1739. We now jump back to near the beginning of the table
  1740. where the move definitions are found.
  1741. The move definitions directly follow the instruction
  1742. definitions.
  1743. .PP
  1744. In certain cases a move is called for,
  1745. either explicitly when a
  1746. .I move
  1747. instruction is used in a code rule,
  1748. or implicitly in a register initialization.
  1749. The different code rules possible to move data from one
  1750. spot to another are described here.
  1751. Example for the PDP-11:
  1752. .DS
  1753. .ta 8 16 24 32 40 48 56 64
  1754. MOVES
  1755. from const2 %num==0 to dst2
  1756. gen clr %2
  1757. from src2 to dst2
  1758. gen mov %1,%2
  1759. from FLTREG to longf4-FLTREG
  1760. gen movfo %1,%2
  1761. from longf4-FLTREG to FLTREG
  1762. gen movof %1,%2
  1763. .DE
  1764. The example shows that the syntax is just
  1765. .DS
  1766. from <source> to <destination> gen <list of instructions>
  1767. .DE
  1768. Source and destination are a token set, optionally followed by
  1769. a boolean expression.
  1770. The code generator will take the first move that matches,
  1771. whenever a move is necessary.
  1772. .I Cgg
  1773. checks whether all moves called for in the table are present.
  1774. .NH 2
  1775. Test definitions
  1776. .PP
  1777. This part describes the instructions necessary to set the condition codes
  1778. to a certain token.
  1779. These rules are needed when the
  1780. .I test
  1781. instruction is used in code rules.
  1782. Example for the PDP-11:
  1783. .DS
  1784. .ta 8 16 24 32 40 48 56 64
  1785. TESTS
  1786. to test src2
  1787. gen tst %1
  1788. .DE
  1789. So syntax is just
  1790. .DS
  1791. to test <source> gen <instruction list>
  1792. .DE
  1793. Source is the same thing as in the move definition.
  1794. .I Cgg
  1795. checks whether all tests called for in the table are present.
  1796. .NH 2
  1797. Some explanation about the rules behind coercions
  1798. .PP
  1799. A central part in code generation is taken by the
  1800. .I coercions .
  1801. It is the responsibility of the table writer to provide
  1802. all necessary coercions so that code generation can continue.
  1803. The minimal set of coercions are
  1804. the coercions to unstack every token expression,
  1805. in combination with the rules to stack every token.
  1806. It should not be possible to smuggle a table through
  1807. .I cgg
  1808. without these basic set available.
  1809. .PP
  1810. If these are present the code generator can always make the necessary
  1811. transformations by stacking and unstacking.
  1812. Of course for code quality it is usually best to provide extra coercions
  1813. to prevent this stacking to take place.
  1814. .I Cg
  1815. discriminates three types of coercions:
  1816. .IP 1)
  1817. Unstacking coercions.
  1818. This category can use the
  1819. .I uses
  1820. clause in its code.
  1821. .IP 2)
  1822. Splitting coercions, these are the coercions that split
  1823. larger tokens into smaller ones.
  1824. .IP 3)
  1825. Transforming coercions, these are the coercions that transform
  1826. a token into another of the same size.
  1827. This category can use the
  1828. .I uses
  1829. clause in its code.
  1830. .PP
  1831. When a stack configuration does not match the stack pattern
  1832. .I coercions
  1833. are searched for in the following order:
  1834. .IP 1)
  1835. First tokens are split if necessary to get their sizes right.
  1836. .IP 2)
  1837. Then transforming coercions are found that will make the pattern match.
  1838. .IP 3)
  1839. Finally if the stack pattern is longer than the fake stack contents
  1840. unstacking coercions will be used to fill up the pattern.
  1841. .PP
  1842. At any point, when coercions are missing so code generation could not
  1843. continue, the offending tokens are stacked.
  1844. .NH 2
  1845. Stack definitions
  1846. .PP
  1847. The next part of the table defines the stacking rules for the machine.
  1848. Each token that may reside on the fake stack must have a rule attached
  1849. to put it on the real stack.
  1850. Example for the PDP-11:
  1851. .DS
  1852. .ta 8 16 24 32 40 48 56 64
  1853. STACKINGRULES
  1854. from const2 %num==0 to STACK
  1855. gen clr {autodec,sp}
  1856. from src2 to STACK
  1857. gen mov %1,{autodec,sp}
  1858. from regconst2 to STACK
  1859. gen mov %1.reg,{autodec,sp}
  1860. add {addr_external, %1.off},{regdef2,sp}
  1861. from DBLREG to STACK
  1862. gen movf %1,{autodec,sp}
  1863. from FLTREG to STACK
  1864. gen movfo %1,{autodec,sp}
  1865. from regind8 to STACK
  1866. uses REG
  1867. gen move %1.reg,%a
  1868. add {addr_external, 8+%1.off},%a
  1869. mov {autodec, %a},{autodec,sp}
  1870. mov {autodec, %a},{autodec,sp}
  1871. mov {autodec, %a},{autodec,sp}
  1872. mov {autodec, %a},{autodec,sp}
  1873. .DE
  1874. .PP
  1875. These examples should be self-explanatory, except maybe for the last one.
  1876. It is possible inside a stacking-rule to use a register.
  1877. Since however the stacking might also take place at a moment
  1878. when no registers are free, it is mandatory that for each token
  1879. there is one stackingrule that does not use a register.
  1880. The code generator uses the first rule possible.
  1881. .NH 2
  1882. Coercions
  1883. .PP
  1884. The next part of the table defines the coercions that are possible
  1885. on the defined tokens.
  1886. Example for the PDP-11:
  1887. .DS
  1888. .ta 7.5c
  1889. COERCIONS
  1890. from STACK
  1891. uses REG
  1892. gen mov {autoinc,sp},%a yields %a
  1893. from STACK
  1894. uses DBLREG
  1895. gen movf {autoinc,sp},%a yields %a
  1896. from STACK
  1897. uses REGPAIR
  1898. gen mov {autoinc,sp},%a.1
  1899. mov {autoinc,sp},%a.2 yields %a
  1900. .DE
  1901. These three coercions just deliver a certain type
  1902. of register by popping it from the real stack.
  1903. .DS
  1904. .ta 7.5c
  1905. from LOCAL yields {regind2,lb,%1.ind}
  1906. from DLOCAL yields {regind4,lb,%1.ind}
  1907. from REG yields {regconst2, %1, 0}
  1908. .DE
  1909. These three are zero-cost rewriting rules.
  1910. .DS
  1911. .ta 7.5c
  1912. from regconst2 %1.off==1
  1913. uses reusing %1,REG=%1.reg
  1914. gen inc %a yields %a
  1915. from regconst2
  1916. uses reusing %1,REG=%1.reg
  1917. gen add {addr_external, %1.off},%a yields %a
  1918. from addr_local
  1919. uses REG
  1920. gen mov lb,%a
  1921. add {const2, %1.ind},%a yields %a
  1922. .DE
  1923. The last three are three different cases of the coercion
  1924. register+constant to register.
  1925. Only in the last case is it always necessary to allocate
  1926. an extra register,
  1927. since arithmetic on the localbase is unthinkable.
  1928. .DS
  1929. .ta 7.5c
  1930. from xsrc2
  1931. uses reusing %1, REG=%1 yields %a
  1932. from longf4
  1933. uses FLTREG=%1 yields %a
  1934. from double8
  1935. uses DBLREG=%1 yields %a
  1936. from src1
  1937. uses REG={const2,0}
  1938. gen bisb %1,%a yields %a
  1939. .DE
  1940. These examples show the coercion of different
  1941. tokens to a register of the needed type.
  1942. The last one shows the trouble needed on a PDP-11 to
  1943. ensure bytes are not sign-extended.
  1944. In EM it is defined that the result of a \fBloi\fP\ 1
  1945. instruction is an integer in the range 0..255.
  1946. .DS
  1947. .ta 7.5c
  1948. from REGPAIR yields %1.2 %1.1
  1949. from regind4 yields {regind2,%1.reg,2+%1.off}
  1950. {regind2,%1.reg,%1.off}
  1951. from relative4 yields {relative2,2+%1.off}
  1952. {relative2,%1.off}
  1953. .DE
  1954. The last examples are splitting rules.
  1955. .PP
  1956. The examples show that
  1957. all coercions change one token on the fake stack into one or more others,
  1958. possibly generating code.
  1959. The STACK token is supposed to be on the fake stack when it is
  1960. really empty, and can only be changed into one other token.
  1961. .NH 1
  1962. The files mach.h and mach.c
  1963. .PP
  1964. The table writer must also supply two files containing
  1965. machine dependent declarations and C code.
  1966. These files are mach.h and mach.c.
  1967. .NH 2
  1968. Types in the code generator
  1969. .PP
  1970. Three different types of integer coexist in the code generator
  1971. and their range depends on the machine at hand.
  1972. They are defined depending on the Target EM_WSIZE, or TEM_WSIZE,
  1973. and TEM_PSIZE.
  1974. The type 'int' is used for things like counters that won't require
  1975. more than 16 bits precision.
  1976. The type 'word' is used among others to assemble datawords and
  1977. is of type 'long'.
  1978. The type 'full' is used for addresses and is of type 'long' if
  1979. TEM_WSIZE>2 or TEM_PSIZE>2.
  1980. .PP
  1981. In macro and function definitions in later paragraphs implicit typing
  1982. will be used for parameters, that is parameters starting with an 's'
  1983. will be of type string, and the letters 'i','w','f' will stand for
  1984. int, word and full respectively.
  1985. .NH 2
  1986. Global variables to work with
  1987. .PP
  1988. Some global variables are present in the code generator
  1989. that can be manipulated by the routines in mach.h and mach.c.
  1990. .LP
  1991. The declarations are:
  1992. .DS L
  1993. .ta 20
  1994. FILE *codefile; /* code is emitted on this stream */
  1995. word part_word; /* words to be output are put together here */
  1996. int part_size; /* number of bytes already put in part_word */
  1997. char str[]; /* Last string read in */
  1998. long argval; /* Last int read and kept */
  1999. .DE
  2000. .NH 2
  2001. Macros in mach.h
  2002. .PP
  2003. In the file mach.h a collection of macros is defined that have
  2004. to do with formatting of assembly code for the machine at hand.
  2005. Some of these macros can of course be left undefined in which case the
  2006. macro calls are left in the source and will be treated as
  2007. function calls.
  2008. These functions can then be defined in \fImach.c\fR.
  2009. .PP
  2010. The macros to be defined are:
  2011. .IP ex_ap(s) 16
  2012. Must print the magic incantations that will mark the symbol \fI\fR
  2013. to be exported to other modules.
  2014. This is the translation of the EM \fBexa\fP and \fBexp\fP instructions.
  2015. .IP in_ap(s)
  2016. Same to import the symbol.
  2017. Translation of \fBina\fP and \fBinp\fP.
  2018. .IP newplb(s)
  2019. Must print the definition of procedure label \fIs\fR.
  2020. If left undefined the newilb() macro is used instead.
  2021. .IP newilb(s)
  2022. Must print the definition of instruction label \fIs\fR.
  2023. .IP newdlb(s)
  2024. Must print the definition of data label \fIs\fR.
  2025. .IP dlbdlb(s1,s2)
  2026. Must define data label
  2027. .I s1
  2028. to be equal to
  2029. .I s2 .
  2030. .IP newlbss(s,f)
  2031. Must declare a piece of memory initialized to BSS_INIT(see below)
  2032. of length
  2033. .I f
  2034. and with label
  2035. .I s .
  2036. .IP cst_fmt
  2037. Format to be used when converting constant arguments of
  2038. EM instructions to string.
  2039. Argument to be formatted will be 'full'.
  2040. .IP off_fmt
  2041. Format to be used for integer part of label+constant,
  2042. argument will be 'full'.
  2043. .IP fmt_ilb(ip,il,s)
  2044. Must use the numbers
  2045. .I ip
  2046. and
  2047. .I il
  2048. that are a procedure number
  2049. and a label number respectively and copy a string to
  2050. .I s
  2051. that must be unique for that combination.
  2052. This procedure is optional, if it is not given ilb_fmt
  2053. must be defined as below.
  2054. .IP ilb_fmt
  2055. Format to be used for creation of unique instruction labels.
  2056. Arguments will be a unique procedure number (int) and the label
  2057. number (int).
  2058. .IP dlb_fmt
  2059. Format to be used for printing numeric data labels.
  2060. Argument will be 'int'.
  2061. .IP hol_fmt
  2062. Format to be used for generation of labels for
  2063. space generated by a
  2064. .B hol
  2065. pseudo.
  2066. Argument will be 'int'.
  2067. .IP hol_off
  2068. Format to be used for printing of the address of an element in
  2069. .B hol
  2070. space.
  2071. Arguments will be the offset in the
  2072. .B hol
  2073. block (word) and the number of the
  2074. .B hol
  2075. (int).
  2076. .IP con_cst(w)
  2077. Must generate output that will assemble into one machine word.
  2078. .IP con_ilb(s)
  2079. Must generate output that will put the address of the instruction label
  2080. into the datastream.
  2081. .IP con_dlb(s)
  2082. Must generate output that will put the address of the data label
  2083. into the datastream.
  2084. .IP fmt_id(sf,st)
  2085. Must take the string in
  2086. .I sf
  2087. that is a nonnumeric global label, and transform it into a copy made to
  2088. .I st
  2089. that will not collide with reserved assembler words and system labels.
  2090. This procedure is optional, if it is not given the id_first macro is used
  2091. as defined below.
  2092. .IP id_first
  2093. Must be a character.
  2094. This is prepended to all nonnumeric global labels if their length
  2095. is shorter than the maximum allowed(currently 8) or if they already
  2096. start with that character.
  2097. This is to avoid conflicts of user labels with system labels.
  2098. .IP BSS_INIT
  2099. Must be a constant.
  2100. This is the value filled in all the words not initialized explicitly.
  2101. This is loader and system dependent.
  2102. If omitted no initialization is assumed.
  2103. .NH 3
  2104. Example mach.h for the PDP-11
  2105. .DS L
  2106. .ta 4c
  2107. #define ex_ap(y) fprintf(codefile,"\et.globl %s\en",y)
  2108. #define in_ap(y) /* nothing */
  2109. #define newplb(x) fprintf(codefile,"%s:\en",x)
  2110. #define newilb(x) fprintf(codefile,"%s:\en",x)
  2111. #define newdlb(x) fprintf(codefile,"%s:\en",x)
  2112. #define dlbdlb(x,y) fprintf(codefile,"%s=%s\en",x,y)
  2113. #define newlbss(l,x) fprintf(codefile,"%s:.=.+%d.\en",l,x);
  2114. #define cst_fmt "$%d."
  2115. #define off_fmt "%d."
  2116. #define ilb_fmt "I%x_%x"
  2117. #define dlb_fmt "_%d"
  2118. #define hol_fmt "hol%d"
  2119. #define hol_off "%ld.+hol%d"
  2120. #define con_cst(x) fprintf(codefile,"%ld.\en",x)
  2121. #define con_ilb(x) fprintf(codefile,"%s\en",x)
  2122. #define con_dlb(x) fprintf(codefile,"%s\en",x)
  2123. #define id_first '_'
  2124. #define BSS_INIT 0
  2125. .DE
  2126. .NH 2
  2127. Functions in mach.c
  2128. .PP
  2129. In mach.c some functions must be supplied,
  2130. mostly manipulating data resulting from pseudoinstructions.
  2131. The specifications are given here,
  2132. implicit typing of parameters as above.
  2133. .IP -
  2134. con_part(isz,word)
  2135. .br
  2136. This function must manipulate the globals
  2137. part_word and part_size to append the isz bytes
  2138. contained in word to the output stream.
  2139. If part_word is full, i.e. part_size==TEM_WSIZE
  2140. the function part_flush() may be called to empty the buffer.
  2141. This is the function that must go through the trouble of
  2142. doing byte order in words correct.
  2143. .IP -
  2144. con_mult(w_size)
  2145. .br
  2146. This function must take the string str[] and create an integer
  2147. from the string of size w_size and generate code to assemble global
  2148. data for that integer.
  2149. Only the sizes for which arithmetic is implemented need be
  2150. handled,
  2151. so if you didn't implement 200-byte integer division
  2152. you don't have to implement 200-byte integer global data.
  2153. Here one must take care of word order in long integers.
  2154. .IP -
  2155. con_float()
  2156. .br
  2157. This function must generate code to assemble a floating
  2158. point number of which the size is contained in argval
  2159. and the ASCII representation in str[].
  2160. .IP -
  2161. prolog(f_nlocals)
  2162. .br
  2163. This function is called at the start of every procedure.
  2164. Function prolog code must be generated,
  2165. and room made for local variables for a total of f_nlocals bytes.
  2166. .IP -
  2167. mes(w_mesno)
  2168. .br
  2169. This function is called when a
  2170. .B mes
  2171. pseudo is seen that is not handled by the machine independent part.
  2172. The example below shows all you probably have to know about that.
  2173. .IP -
  2174. segname[]
  2175. .br
  2176. This is not a function,
  2177. but an array of four strings.
  2178. These strings are put out whenever the code generator
  2179. switches segments.
  2180. Segments are SEGTXT, SEGCON, SEGROM and SEGBSS in that order.
  2181. .PP
  2182. If register variables are used in a table, the program
  2183. .I cgg
  2184. will define the word REGVARS during compilation of the sources.
  2185. So the following functions described here should be bracketed
  2186. by #ifdef REGVARS and #endif.
  2187. .IP -
  2188. regscore(off,size,typ,freq,totyp) long off;
  2189. .br
  2190. This function should assign a score to a register variable,
  2191. the score should preferably be the estimated number of bytes
  2192. gained when it is put in a register.
  2193. Off and size are the offset and size of the variable,
  2194. typ is the type, that is reg_any, reg_pointer, reg_loop or reg_float.
  2195. Freq is the count of static occurrences, and totyp
  2196. is the type of the register it is planned to go into.
  2197. .br
  2198. Keep in mind that the gain should be net, that is the cost for
  2199. register save/restore sequences and the cost of initialisation
  2200. in the case of parameters should already be included.
  2201. .IP -
  2202. i_regsave()
  2203. .br
  2204. This function is called at the start of a procedure, just before
  2205. register saves are done.
  2206. It can be used to initialise some variables if needed.
  2207. .IP -
  2208. f_regsave()
  2209. .br
  2210. This function is called at end of the register save sequence.
  2211. It can be used to do the real saving if multiple register move
  2212. instructions are available.
  2213. .IP -
  2214. regsave(regstr,off,size) char *regstr; long off;
  2215. .br
  2216. Should either do the real saving or set up a table to have
  2217. it done by f_regsave.
  2218. Note that initialisation of parameters should also be done,
  2219. or planned here.
  2220. .IP -
  2221. regreturn()
  2222. .br
  2223. Should restore saved registers and return.
  2224. The function result is already in the function return area by now.
  2225. .NH 3
  2226. Example mach.c for the PDP-11
  2227. .PP
  2228. As an example of the sort of code expected,
  2229. the mach.c for the PDP-11 is presented here.
  2230. .DS L
  2231. .ta 0.5i 1i 1.5i 2i 2.5i 3i 3.5i 4i 4.5i
  2232. /*
  2233. * machine dependent back end routines for the PDP-11
  2234. */
  2235. con_part(sz,w) register sz; word w; {
  2236. while (part_size % sz)
  2237. part_size++;
  2238. if (part_size == 2)
  2239. part_flush();
  2240. if (sz == 1) {
  2241. w &= 0xFF;
  2242. if (part_size)
  2243. w <<= 8;
  2244. part_word |= w;
  2245. } else {
  2246. assert(sz == 2);
  2247. part_word = w;
  2248. }
  2249. part_size += sz;
  2250. }
  2251. con_mult(sz) word sz; {
  2252. long l;
  2253. if (sz != 4)
  2254. fatal("bad icon/ucon size");
  2255. l = atol(str);
  2256. fprintf(codefile,"\et%o;%o\en",(int)(l>>16),(int)l);
  2257. }
  2258. con_float() {
  2259. double f;
  2260. register short *p,i;
  2261. /*
  2262. * This code is correct only when the code generator is
  2263. * run on a PDP-11 or VAX-11 since it assumes native
  2264. * floating point format is PDP-11 format.
  2265. */
  2266. if (argval != 4 && argval != 8)
  2267. fatal("bad fcon size");
  2268. f = atof(str);
  2269. p = (short *) &f;
  2270. i = *p++;
  2271. if (argval == 8) {
  2272. fprintf(codefile,"\et%o;%o;",i,*p++);
  2273. i = *p++;
  2274. }
  2275. fprintf(codefile,"\et%o;%o\en",i,*p++);
  2276. }
  2277. #ifdef REGVARS
  2278. char Rstring[10];
  2279. full lbytes;
  2280. struct regadm {
  2281. char *ra_str;
  2282. long ra_off;
  2283. } regadm[2];
  2284. int n_regvars;
  2285. regscore(off,size,typ,score,totyp) long off; {
  2286. /*
  2287. * This function is full of magic constants.
  2288. * They are a result of experimentation.
  2289. */
  2290. if (size != 2)
  2291. return(-1);
  2292. score -= 1; /* allow for save/restore */
  2293. if (off>=0)
  2294. score -= 2;
  2295. if (typ==reg_pointer)
  2296. score *= 17;
  2297. else if (typ==reg_loop)
  2298. score = 10*score+50; /* Guestimate */
  2299. else
  2300. score *= 10;
  2301. return(score); /* 10 * estimated # of words of profit */
  2302. }
  2303. i_regsave() {
  2304. Rstring[0] = 0;
  2305. n_regvars=0;
  2306. }
  2307. f_regsave() {
  2308. register i;
  2309. if (n_regvars==0 || lbytes==0) {
  2310. fprintf(codefile,"mov r5,-(sp)\enmov sp,r5\en");
  2311. if (lbytes == 2)
  2312. fprintf(codefile,"tst -(sp)\en");
  2313. else if (lbytes!=0)
  2314. fprintf(codefile,"sub $0%o,sp\en",lbytes);
  2315. for (i=0;i<n_regvars;i++)
  2316. fprintf(codefile,"mov %s,-(sp)\en",regadm[i].ra_str);
  2317. } else {
  2318. if (lbytes>6) {
  2319. fprintf(codefile,"mov $0%o,r0\en",lbytes);
  2320. fprintf(codefile,"jsr r5,PR%s\en",Rstring);
  2321. } else {
  2322. fprintf(codefile,"jsr r5,PR%d%s\en",lbytes,Rstring);
  2323. }
  2324. }
  2325. for (i=0;i<n_regvars;i++)
  2326. if (regadm[i].ra_off>=0)
  2327. fprintf(codefile,"mov 0%lo(r5),%s\en",regadm[i].ra_off,
  2328. regadm[i].ra_str);
  2329. }
  2330. regsave(regstr,off,size) char *regstr; long off; {
  2331. fprintf(codefile,"/ Local %ld into %s\en",off,regstr);
  2332. strcat(Rstring,regstr);
  2333. regadm[n_regvars].ra_str = regstr;
  2334. regadm[n_regvars].ra_off = off;
  2335. n_regvars++;
  2336. }
  2337. regreturn() {
  2338. fprintf(codefile,"jmp RT%s\en",Rstring);
  2339. }
  2340. #endif
  2341. prolog(nlocals) full nlocals; {
  2342. #ifndef REGVARS
  2343. fprintf(codefile,"mov r5,-(sp)\enmov sp,r5\en");
  2344. if (nlocals == 0)
  2345. return;
  2346. if (nlocals == 2)
  2347. fprintf(codefile,"tst -(sp)\en");
  2348. else
  2349. fprintf(codefile,"sub $0%o,sp\en",nlocals);
  2350. #else
  2351. lbytes = nlocals;
  2352. #endif
  2353. }
  2354. mes(type) word type; {
  2355. int argt ;
  2356. switch ( (int)type ) {
  2357. case ms_ext :
  2358. for (;;) {
  2359. switch ( argt=getarg(
  2360. ptyp(sp_cend)|ptyp(sp_pnam)|sym_ptyp) ) {
  2361. case sp_cend :
  2362. return ;
  2363. default:
  2364. strarg(argt) ;
  2365. fprintf(codefile,".globl %s\en",argstr) ;
  2366. break ;
  2367. }
  2368. }
  2369. default :
  2370. while ( getarg(any_ptyp) != sp_cend ) ;
  2371. break ;
  2372. }
  2373. }
  2374. char *segname[] = {
  2375. ".text", /* SEGTXT */
  2376. ".data", /* SEGCON */
  2377. ".data", /* SEGROM */
  2378. ".bss" /* SEGBSS */
  2379. };
  2380. .DE
  2381. .NH 1
  2382. Internal workings of the code generator.
  2383. .NH 2
  2384. Description of tables.c and tables.h contents
  2385. .PP
  2386. In this section the intermediate files will be described
  2387. that are produced by
  2388. .I cgg
  2389. and compiled with machine independent code to produce a code generator.
  2390. .NH 3
  2391. Tables.c
  2392. .PP
  2393. Tables.c contains a large number of initialized array's of all sorts.
  2394. Description of each follows:
  2395. .br
  2396. .in 1i
  2397. .ti -0.5i
  2398. byte coderules[]
  2399. .br
  2400. Pseudo code interpreted by the code generator.
  2401. Always starts with some opcode followed by operands depending
  2402. on the opcode.
  2403. Some of the opcodes have an argument encoded in the upper three
  2404. bits of the opcode byte.
  2405. Integers in this table are between 0 and 32767 and have a one byte
  2406. encoding if between 0 and 127.
  2407. .ti -0.5i
  2408. char wrd_fmt[]
  2409. .br
  2410. The format used for output of words.
  2411. .ti -0.5i
  2412. char stregclass[]
  2413. .br
  2414. Number of computed static register class per register.
  2415. Two registers are in the same class if they have the same properties
  2416. and don't share a common subregister.
  2417. .ti -0.5i
  2418. struct reginfo machregs[]
  2419. .br
  2420. Info per register.
  2421. Initialized with representation string, size,
  2422. members of the register and set of registers affected when this
  2423. one is changed.
  2424. Also contains room for run time information,
  2425. like contents and reference count.
  2426. .ti -0.5i
  2427. tkdef_t tokens[]
  2428. .br
  2429. Information per tokentype.
  2430. Initialized with size, cost, type of operands and formatstring.
  2431. .ti -0.5i
  2432. node_t enodes[]
  2433. .br
  2434. List of triples representing expressions for the code generator.
  2435. .ti -0.5i
  2436. string codestrings[]
  2437. .br
  2438. List of strings.
  2439. All strings are put in a list and checked for duplication,
  2440. so only one copy per string will reside here.
  2441. .ti -0.5i
  2442. set_t machsets[]
  2443. .br
  2444. List of token expression sets.
  2445. Bit 0 of the set is used for the SCRATCH property of registers,
  2446. bit 1 upto NREG are for the corresponding registers
  2447. and bit NREG+1 upto the end are for corresponding tokens.
  2448. .ti -0.5i
  2449. inst_t tokeninstances[]
  2450. .br
  2451. List of descriptions for building tokens.
  2452. Contains type of rule for building one,
  2453. plus operands depending on the type.
  2454. .ti -0.5i
  2455. move_t moves[]
  2456. .br
  2457. List of move rules.
  2458. Contains token expressions for source and destination
  2459. plus index for code rule.
  2460. .ti -0.5i
  2461. test_t tests[]
  2462. .br
  2463. List of test rules.
  2464. Contains token expressions for source
  2465. plus index for code rule.
  2466. .ti -0.5i
  2467. byte pattern[]
  2468. .br
  2469. EM patterns.
  2470. This is structured internally as chains of patterns,
  2471. each chain pointed at by pathash[].
  2472. After each pattern the list of possible code rules is given.
  2473. .ti -0.5i
  2474. int pathash[256]
  2475. .br
  2476. Indices into pattern[] for all patterns with a certain low order
  2477. byte of the hashing function.
  2478. .ti -0.5i
  2479. c1_t c1coercs[]
  2480. .br
  2481. List of rules to stack tokens.
  2482. Contains token expressions,
  2483. register needed,
  2484. cost
  2485. and code rule.
  2486. .ti -0.5i
  2487. c2_t c2coercs[]
  2488. .br
  2489. List of splitting coercions.
  2490. Token expressions,
  2491. split factor,
  2492. replacements
  2493. and code rule.
  2494. .ti -0.5i
  2495. c3_t c3coercs[]
  2496. .br
  2497. List of one to one coercions.
  2498. Token expressions,
  2499. register needed,
  2500. replacement
  2501. and code rule.
  2502. .ti -0.5i
  2503. struct reginfo **reglist[]
  2504. .br
  2505. List of lists of pointers to register information.
  2506. For every property the list is here
  2507. to find the registers corresponding to it.
  2508. .in 0
  2509. .NH 3
  2510. tables.h
  2511. .PP
  2512. In tables.h various derived constants for the tables are
  2513. given.
  2514. They are then used to determine array sizes in the actual code generator,
  2515. plus loop termination in some cases.
  2516. .NH 2
  2517. Other important data structures
  2518. .PP
  2519. During code generation some other data structures are used
  2520. and here is a short description of some of the important ones.
  2521. .PP
  2522. Tokens are kept in the code generator as a struct consisting of
  2523. one integer
  2524. .I t_token
  2525. which is -1 if the token is a register,
  2526. and the number of the token otherwise,
  2527. plus an array of
  2528. .I TOKENSIZE
  2529. unions
  2530. .I t_att
  2531. of which the first is the register number in case of a register.
  2532. .PP
  2533. The fakestack is an array of these tokens,
  2534. there is a global variable
  2535. .I stackheight .
  2536. .PP
  2537. The results of expressions are kept in a struct
  2538. .I result
  2539. with elements
  2540. .I e_typ ,
  2541. giving the type of the expression:
  2542. .I EV_INT ,
  2543. .I EV_REG
  2544. or
  2545. .I EV_ADDR ,
  2546. and a union
  2547. .I e_v
  2548. which contains the real result.
  2549. .NH 2
  2550. A tour through the sources
  2551. .NH 3
  2552. codegen.c
  2553. .PP
  2554. The file codegen.c contains one large function consisting
  2555. of one giant switch statement.
  2556. It is the interpreter for the code generator pseudo code
  2557. as contained in code rules[].
  2558. This function can call itself recursively when doing look ahead.
  2559. Arguments are:
  2560. .IP codep 10
  2561. Pointer into code rules, pseudo program counter.
  2562. .IP ply
  2563. Number of EM pattern look ahead allowed.
  2564. .IP toplevel
  2565. Boolean telling whether this is the toplevel codegen() or
  2566. a deeper incarnation.
  2567. .IP costlimit
  2568. A cutoff value to limit searches.
  2569. If the cost crosses costlimit the incarnation can terminate.
  2570. .IP forced
  2571. A register number if nonzero.
  2572. This is used inside coercions to force the allocate() call to allocate
  2573. a register determined by earlier look ahead.
  2574. .PP
  2575. The instructions inplemented in the switch:
  2576. .NH 4
  2577. DO_DLINE
  2578. .PP
  2579. Prints debugging information if the code generator runs in debug mode.
  2580. This information is only generated if
  2581. .I cgg
  2582. was called with the -d flag.
  2583. .NH 4
  2584. DO_NEXTEM
  2585. .PP
  2586. Matches the next EM pattern and does look ahead if necessary to find the best
  2587. code rule associated with this pattern.
  2588. Heuristics are used to determine best code rule when possible.
  2589. This is done by calling the distance() function.
  2590. It can also handle the procedure mechanism.
  2591. .NH 4
  2592. DO_COERC
  2593. .PP
  2594. This sets the code generator in the state to do a from stack coercion.
  2595. .NH 4
  2596. DO_XMATCH
  2597. .PP
  2598. This is done when a match no longer has to be checked.
  2599. Used when the nocoercions: trick is used in the table.
  2600. .NH 4
  2601. DO_MATCH
  2602. .PP
  2603. This is the big one inside this function.
  2604. It has the task to transform the contents of the current
  2605. fake stack to match the pattern given after it.
  2606. .PP
  2607. Since the code generator does not know combining coercions,
  2608. i.e. there is no way to make a big token out of two smaller ones,
  2609. the first thing done is to stack every token that is too small.
  2610. After that all tokens too big are split if possible to the right size.
  2611. .PP
  2612. Next the coercions are sought that would transform tokens in place to
  2613. the right one, plus the coercions that would pop tokens of the stack.
  2614. Each of those might need a register, so a list of registers is generated
  2615. and at the end of looking for coercions the function
  2616. .I tuples()
  2617. is called to generate the list of all possible \fIn\fP-tuples,
  2618. where
  2619. .I n
  2620. equals the number of registers needed.
  2621. .PP
  2622. Look ahead is now performed if the number of tuples is greater than one.
  2623. If no possibility is found within the costlimit,
  2624. the fake stack is made smaller by pushing the bottom token,
  2625. and this process is repeated until either a way is found or
  2626. the fake stack is completely empty and there is still no way
  2627. to make the match.
  2628. .PP
  2629. If there is a way the corresponding coercions are executed
  2630. and the code is finished.
  2631. .NH 4
  2632. DO_REMOVE
  2633. .PP
  2634. Here the kills clause is executed, all tokens matched by the
  2635. token expression plus boolean expression are pushed.
  2636. In the current implementation there is no attempt to move those
  2637. tokens to registers, but that is a possible future extension.
  2638. .NH 4
  2639. DO_DEALLOCATE
  2640. .PP
  2641. This one temporarily decrements by one the reference count of all registers
  2642. contained in the token given as argument.
  2643. .NH 4
  2644. DO_REALLOCATE
  2645. .PP
  2646. Here all temporary deallocates are made undone.
  2647. .NH 4
  2648. DO_ALLOCATE
  2649. .PP
  2650. This is the part that allocates a register and decides which one to use.
  2651. If the
  2652. .I forced
  2653. argument was given its task is simple,
  2654. otherwise some work must be done.
  2655. First the list of possible registers is scanned,
  2656. all free registers noted and it is noted whether any of those
  2657. registers is already
  2658. containing the initialization.
  2659. If no registers are available some fakestack token is stacked and the
  2660. process is repeated.
  2661. .PP
  2662. After that if an exact match was found,
  2663. the list of registers is reduced to one register matching exactly
  2664. out of every register class.
  2665. Now look ahead is performed if necessary and the register chosen.
  2666. If an initialization was given the corresponding move is performed,
  2667. otherwise the register is marked empty.
  2668. .NH 4
  2669. DO_INSTR
  2670. .PP
  2671. This prints an instruction and its operands.
  2672. Only done on toplevel.
  2673. .NH 4
  2674. DO_MOVE
  2675. .PP
  2676. Calls the move() function in the code generator to implement the move
  2677. instruction in the table.
  2678. .NH 4
  2679. DO_TEST
  2680. .PP
  2681. Calls the test() function in the code generator to implement the test
  2682. instruction in the table.
  2683. .NH 4
  2684. DO_ERASE
  2685. .PP
  2686. Marks the register that is its argument as empty.
  2687. .NH 4
  2688. DO_TOKREPLACE
  2689. .PP
  2690. This is the token replacement part.
  2691. It is also called if there is no token replacement because it has
  2692. some other functions as well.
  2693. .PP
  2694. First the tokens that will be pushed on the fake stack are computed
  2695. and stored in a temporary array.
  2696. Then the tokens that were matched in this rule are popped
  2697. and their embedded registers have their reference count
  2698. decremented.
  2699. After that the replacement tokens are pushed.
  2700. .PP
  2701. Finally all registers allocated in this rule have their reference count
  2702. decremented.
  2703. If they were not pushed on the fake stack they will be available again
  2704. in the next code rule.
  2705. .NH 4
  2706. DO_EMREPLACE
  2707. .PP
  2708. Places replacement EM instructions back into the instruction stream.
  2709. .NH 4
  2710. DO_COST
  2711. .PP
  2712. Accounts for cost as given in the code rule.
  2713. .NH 4
  2714. DO_RETURN
  2715. .PP
  2716. Returns from this level of codegen().
  2717. Is used at the end of coercions,
  2718. move rules etc..
  2719. .NH 4
  2720. DO_LABDEF
  2721. .PP
  2722. This prints a label when the top element size mechanism is used. Only done on
  2723. toplevel.
  2724. .NH 3
  2725. compute.c
  2726. .PP
  2727. This module computes the various expressions as given
  2728. in the enodes[] array.
  2729. Nothing very special happens here,
  2730. it is just a recursive function computing leaves
  2731. of expressions and applying the operator.
  2732. .NH 3
  2733. equiv.c
  2734. .PP
  2735. In this module the tuples() function is implemented.
  2736. It is given the number of registers needed and
  2737. a list of register lists and it constructs a list of tuples
  2738. where the \fIn\fP'th register comes from the \fIn\fP'th list.
  2739. Before the list is constructed however
  2740. the dynamic register classes are computed.
  2741. Two registers are in the same dynamic class if they are in the
  2742. same static class and their contents is the same.
  2743. .PP
  2744. After that the permute() recursive function is called to
  2745. generate the list of tuples.
  2746. After construction a generated tuple is added to the list
  2747. if it is not already pairwise in the same class
  2748. or if the register relations are not the same,
  2749. i.e. if the first and second register share a common
  2750. subregister in one tuple and not in the other they are considered different.
  2751. .NH 3
  2752. fillem.c
  2753. .PP
  2754. This is the routine that does the reading of EM instructions
  2755. and the handling of pseudos.
  2756. The mach.c module provided by the table writer is included
  2757. at the end of this module.
  2758. The routine fillemlines() is called by nextem() at toplevel
  2759. to make sure there are enough instruction to match.
  2760. It fills the EM instruction buffer up to 5 places from the end to
  2761. keep room for EM replacement instructions,
  2762. or up to a pseudo.
  2763. .PP
  2764. The dopseudo() function performs the function of the pseudo last
  2765. encountered.
  2766. If the pseudo is a
  2767. .B rom
  2768. the corresponding label is saved with the contents of the
  2769. .B rom
  2770. to be available to the code generator later.
  2771. The rest of the routines are small service routines for either
  2772. input or data output.
  2773. .NH 3
  2774. gencode.c
  2775. .PP
  2776. This module contains routines called by codegen() to generate the real
  2777. code to the codefile.
  2778. The function genstr() gets a string as argument and copies it to codefile.
  2779. The prtoken() function interprets the tokenformat as given in
  2780. the tokens[] array.
  2781. .NH 3
  2782. glosym.c
  2783. .PP
  2784. This module maintains a list of global symbols that have a
  2785. .B rom
  2786. pseudo associated.
  2787. There are functions to enter a symbol and to find a symbol.
  2788. .NH 3
  2789. label.c
  2790. .PP
  2791. This module contains routines to handle the top element size messages.
  2792. .NH 3
  2793. main.c
  2794. .PP
  2795. Main routine of the code generator.
  2796. Processes arguments and flags.
  2797. Flags available are:
  2798. .IP -d
  2799. Sets debug mode if the code generator was not compiled with
  2800. the NDEBUG macro defined.
  2801. The flag can be followed by a digit specifying the amount of debugging
  2802. wanted,
  2803. and by @labelname giving the start of debugging.
  2804. Debug mode gives very long output on stderr indicating
  2805. all steps of the code generation process including nesting
  2806. of the codegen() function.
  2807. .IP -p\fIn\fP
  2808. Sets the look ahead depth to
  2809. .I n ,
  2810. the
  2811. .I p
  2812. stands for ply,
  2813. a well known word in chess playing programs.
  2814. .IP -w\fIn\fP
  2815. Sets the weight percentage for size in the cost function to
  2816. .I n
  2817. percent.
  2818. Uses Euclides algorithm to simplify rationals.
  2819. .NH 3
  2820. move.c
  2821. .PP
  2822. Function to implement the move instruction in the tables,
  2823. register initialization and the test instruction and associated bookkeeping.
  2824. First tests are made to try to prevent the move from really happening.
  2825. After that, if there is an after that,
  2826. the move rule is found and the code executed.
  2827. .NH 3
  2828. nextem.c
  2829. .PP
  2830. The entry point of this module is nextem().
  2831. It hashes the next three EM instructions,
  2832. and uses the low order byte of the hash
  2833. as an index into the array pathash[],
  2834. to find a chain of patterns in the array
  2835. pattern[],
  2836. that are all tried for a match.
  2837. .PP
  2838. The function trypat() does most of the work
  2839. checking patterns.
  2840. When a pattern is found to match all instructions
  2841. the operands of the instruction are placed into the dollar[] array.
  2842. Then the boolean expression is tried.
  2843. If it matches the function can return,
  2844. leaving the operands still in the dollar[] array,
  2845. so later in the code rule they can still be used.
  2846. .NH 3
  2847. reg.c
  2848. .PP
  2849. Collection of routines to handle registers.
  2850. Reference count routines are here,
  2851. chrefcount() and getrefcount(),
  2852. plus routines to erase a single register or all of them,
  2853. erasereg() and cleanregs().
  2854. .PP
  2855. If NDEBUG hasn't been defined, here is also the routine that checks
  2856. if the reference count kept with the register information is in
  2857. agreement with the number of times it occurs on the fake stack.
  2858. .NH 3
  2859. salloc.c
  2860. .PP
  2861. Module for string allocation and garbage collection.
  2862. Contains entry points myalloc(),
  2863. a routine calling malloc() and checking whether room is left,
  2864. myfree(), just free(),
  2865. popstr() a function called from state.c to free all strings
  2866. made since the last saved status.
  2867. Furthermore there is salloc() which has the size of the string as parameter
  2868. and returns a pointer to the allocated space,
  2869. while keeping a copy of the pointer for garbage allocation purposes.
  2870. .PP
  2871. The function garbage_collect is called from codegen() at toplevel
  2872. every now and then,
  2873. and checks all places where strings may reside to mark strings
  2874. as being in use.
  2875. Strings not in use are returned to the pool of free space.
  2876. .NH 3
  2877. state.c
  2878. .PP
  2879. Set of routines called to save current status and
  2880. restore a previous saved state.
  2881. .NH 3
  2882. subr.c
  2883. .PP
  2884. Random set of leftover routines.
  2885. .NH 4
  2886. match
  2887. .PP
  2888. Computes whether a certain token matches a certain token expression.
  2889. Just computes a bitnumber according to the algorithm explained with
  2890. machsets[],
  2891. and tests the bit and the boolean expression if it is there.
  2892. .NH 4
  2893. instance,cinstance
  2894. .PP
  2895. These two functions compute a token from a description.
  2896. They differ very slight, cinstance() is used to compute
  2897. the result of a coercion in a certain context
  2898. and therefore has more arguments, which it uses instead of
  2899. the global information instance() works on.
  2900. .NH 4
  2901. eqtoken
  2902. .PP
  2903. eqtoken computes whether two tokens can be considered identical.
  2904. Used to check register contents during moves mainly.
  2905. .NH 4
  2906. distance
  2907. .PP
  2908. This is the heuristic function that computes a distance from
  2909. the current fake stack contents to the token pattern in the table.
  2910. It likes exact matches most, then matches where at least the sizes are correct
  2911. and if the sizes are not correct it likes too large sizes more than too
  2912. small, since splitting a token is easier than combining one.
  2913. .NH 4
  2914. split
  2915. .PP
  2916. This function tries to find a splitting coercion
  2917. and executes it immediately when found.
  2918. The fake stack is shuffled thoroughly when this happens,
  2919. so pieces below the token that must be split are saved first.
  2920. .NH 4
  2921. docoerc
  2922. .PP
  2923. This function executes a coercion that was found.
  2924. The same shuffling is done, so the top of the stack is again saved.
  2925. .NH 4
  2926. stackupto
  2927. .PP
  2928. This function gets a pointer into the fake stack and must stack
  2929. every token including the one pointed at up to the bottom of the fake stack.
  2930. The first stacking rule possible is used,
  2931. so rules using registers must come first.
  2932. .NH 4
  2933. findcoerc
  2934. .PP
  2935. Looks for a one to one coercion, if found it returns a pointer
  2936. to it and leaves a list of possible registers to use in the global
  2937. variable curreglist.
  2938. This is used by codegen().
  2939. .NH 3
  2940. var.c
  2941. .PP
  2942. Global variables used by more than one module.
  2943. External definitions are in extern.h.