cg.doc 56 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864
  1. .\" $Id$
  2. .RP
  3. .ND Nov 1984
  4. .TL
  5. The table driven code generator from
  6. .br
  7. the Amsterdam Compiler Kit
  8. .AU
  9. Hans van Staveren
  10. .AI
  11. Dept. of Mathematics and Computer Science
  12. Vrije Universiteit
  13. Amsterdam, The Netherlands
  14. .AB
  15. It is possible to automate the process of compiler building
  16. to a great extent using collections of tools.
  17. The Amsterdam Compiler Kit is such a collection of tools.
  18. This document provides a description of the internal workings
  19. of the table driven code generator in the Amsterdam Compiler Kit,
  20. and a description of syntax and semantics of the driving table.
  21. .PP
  22. >>> NOTE <<<
  23. .br
  24. This document pertains to the \fBold\fP code generator. Refer to the
  25. "Second Revised Edition" for the new code generator.
  26. .AE
  27. .NH 1
  28. Introduction
  29. .PP
  30. Part of the Amsterdam Compiler Kit is a code generator system consisting
  31. of a code generator generator (\fIcgg\fP for short) and some machine
  32. independent C code.
  33. .I Cgg
  34. reads a machine description table and creates two files,
  35. tables.h and tables.c.
  36. These are then used together with other C code to produce
  37. a code generator for the machine at hand.
  38. .PP
  39. This in turn reads compact EM code and produces
  40. assembly code.
  41. The remainder of this document will first broadly describe
  42. the working of the code generator,
  43. then a description of the machine table follows after which
  44. the internal workings of the code generator will be explained.
  45. .PP
  46. The reader is assumed to have at least a vague notion about the
  47. semantics of the intermediary EM code.
  48. Someone wishing to write a table for a new machine
  49. should be thoroughly acquainted with EM code
  50. and the assembly code of the machine at hand.
  51. .NH 1
  52. Global overview of the workings of the code generator.
  53. .PP
  54. The code generator or
  55. .I cg
  56. tries to generate good code by simulating the runtime stack
  57. of the program compiled and delaying emission of code as long
  58. as possible.
  59. It also keeps track of register contents, which enables it to
  60. eliminate redundant moves, and tries to eliminate redundant tests
  61. by keeping information about condition code status,
  62. if applicable for the machine.
  63. .PP
  64. .I Cg
  65. maintains a `fakestack' containing `tokens' that are built
  66. by executing the pseudo code contained in the code rules given
  67. by the table writer.
  68. One can think of the fakestack as a logical extension of the real
  69. stack the program compiled will have when run.
  70. During code generation tokens will be kept on the fakestack as long
  71. as possible but when they are moved to the real stack,
  72. by generating code for the push,
  73. all tokens above\u*\d
  74. .FS
  75. * in the rest of this document the stack is assumed to grow downwards,
  76. although the top of the stack will mean the first element that will
  77. be popped.
  78. .FE
  79. the tokens pushed will be pushed also,
  80. so that the fakestack will not contain holes.
  81. .PP
  82. The main loop of
  83. .I cg
  84. is this:
  85. .IP 1)
  86. find a pattern of EM instructions starting at the current one to
  87. generate code for.
  88. This pattern will usually be of length one but longer patterns can be used.
  89. .IP 2)
  90. Select one of the possibly many stack patterns that go with this
  91. EM pattern on the basis of heuristics and/or lookahead.
  92. .IP 3)
  93. Force the current fakestack contents to match the pattern.
  94. This may involve
  95. copying tokens to registers, making dummy transformations, e.g. to
  96. transform a "local" into an "register offsetted" or might even
  97. cause to have the complete fakestack contents put to the real stack
  98. and then back into registers if no suitable transformations
  99. were provided by the table writer.
  100. .IP 4)
  101. Execute the pseudocode associated with the code rule just selected,
  102. this may cause registers to be allocated,
  103. code to be emitted etc..
  104. .IP 5)
  105. Put tokens onto the fakestack to reflect the result of the operation.
  106. .IP 6)
  107. Insert some EM instructions into the stream,
  108. this is possible but not common.
  109. .IP 7)
  110. Account for the cost.
  111. The cost is kept in a (space, time) vector and lookahead decisions
  112. are based on a linear combination of these.
  113. .PP
  114. The table that drives
  115. .I cg
  116. is not read in every time,
  117. but instead is used at compiletime
  118. of
  119. .I cg
  120. to set parameters and to load pseudocode tables.
  121. A program called
  122. .I cgg
  123. reads the table and produces large lists of numbers that are
  124. compiled together with machine independent code to produce
  125. a code generator for the machine at hand.
  126. .NH 1
  127. Description of the machine table
  128. .PP
  129. The machine description table consists of the following sections:
  130. .IP 1)
  131. Constant definitions
  132. .IP 2)
  133. Register definitions
  134. .IP 3)
  135. Token definitions
  136. .IP 4)
  137. Token expression definitions
  138. .IP 5)
  139. Code rules
  140. .IP 6)
  141. Move definitions
  142. .IP 7)
  143. Test definitions
  144. .IP 8)
  145. Stacking definitions
  146. .PP
  147. Input is in free format, white space and newlines may be used
  148. at will to improve legibility.
  149. Identifiers used in the table have the same syntax as C identifiers,
  150. upper and lower case considered different, all characters significant.
  151. There is however one exception:
  152. identifiers must be more than one character long for parsing reasons.
  153. C style comments are accepted
  154. .DS
  155. /* this is a comment */
  156. .DE
  157. and #define macros may be used if the need arises.
  158. .NH 2
  159. Some constants
  160. .PP
  161. Before anything else three constants must be defined,
  162. all with the syntax NAME=value, value being an integer.
  163. These constants are:
  164. .IP EM_WSIZE 10
  165. Number of bytes in a machine word.
  166. This is the number of bytes
  167. a simple \fBloc\fP instruction will put on the stack.
  168. .IP EM_PSIZE
  169. Number of bytes in a pointer.
  170. This is the number of bytes
  171. a \fBlal\fP instruction will put on the stack.
  172. .IP EM_BSIZE
  173. Number of bytes in the hole between AB and LB.
  174. If the calling sequence just saves PC and LB this
  175. size will be twice the pointersize.
  176. .PP
  177. EM_WSIZE and EM_PSIZE are checked when a program is compiled
  178. with the resulting code generator.
  179. EM_BSIZE is used by
  180. .I cg
  181. to add to the offset of instructions dealing with locals
  182. having positive offsets,
  183. i.e. parameters.
  184. .PP
  185. Optionally one can give here the factors with which the size and time
  186. parts of the cost function have to be multiplied to ensure they have the
  187. same order of magnitude.
  188. This can be done as
  189. .DS
  190. TIMEFACTOR = C\d1\u/C\d2\u
  191. SIZEFACTOR = C\d3\u/C\d4\u
  192. .DE
  193. Above numbers must be read as rational numbers.
  194. Defaults are 1/1 for both of them.
  195. These constants set the default size/time tradeoff in the code generator,
  196. so if TIMEFACTOR and SIZEFACTOR are both 1 the code generator will choose
  197. at random between two codesequences where one has
  198. cost (10,4) and the other has cost (8,6).
  199. See also the description of the cost field below.
  200. .PP
  201. Also optional is the definition of a printformat for integers in the codefile.
  202. This is given as
  203. .DS
  204. FORMAT = string
  205. .DE
  206. The default for string is "%ld".
  207. For example on the PDP 11 one can use
  208. .DS
  209. FORMAT= "0%lo"
  210. .DE
  211. to satisfy the old UNIX assembler that reads octal unless followed by
  212. a period, and the ACK assembler that follows C conventions.
  213. .NH 2
  214. Register definition
  215. .PP
  216. The next part of the tables describes the various registers of the
  217. machine and defines identifiers
  218. to be used in later parts of the tables.
  219. Example for the PDP-11:
  220. .DS L
  221. REGISTERS:
  222. R0 = ( "r0",2), REG.
  223. R1 = ( "r1",2), REG, ODDREG.
  224. R2 = ( "r2",2), REG.
  225. R3 = ( "r3",2), REG, ODDREG.
  226. R4 = ( "r4",2), REG.
  227. LB = ( "r5",2), LOCALBASE.
  228. R01= ( "r0",4,R0,R1), REGPAIR.
  229. R23= ( "r2",4,R2,R3), REGPAIR.
  230. FR0= ( "r0",4), FREG.
  231. FR1= ( "r1",4), FREG.
  232. FR2= ( "r2",4), FREG.
  233. FR3= ( "r3",4), FREG.
  234. DR0= ( "r0",8,FR0), DREG.
  235. DR1= ( "r1",8,FR1), DREG.
  236. DR2= ( "r2",8,FR2), DREG.
  237. DR3= ( "r3",8,FR3), DREG.
  238. .DE
  239. .PP
  240. The identifier before the '=' sign is the name of the register
  241. as used further on in the table.
  242. The string is the name of the register as far as the assembler is concerned.
  243. The number is the size of the register in bytes.
  244. Identifiers following the number but within the parentheses are previously
  245. defined registernames that are contained in the register being defined.
  246. The identifiers following the closing parenthesis are properties
  247. of the register.
  248. So for example R23 is a register with assembler name r2, 4 bytes long,
  249. contains the registers R2 and R3 and has the property REGPAIR.
  250. .PP
  251. It might seem wise to list each and every property of a register,
  252. so one might give R0 the extra property MFPTREG named after the not
  253. too well known MFPT instruction on newer PDP-11 types,
  254. but this is not a good idea.
  255. Every extra property means the registerset is more unorthogonal
  256. and
  257. .I cg
  258. execution time is influenced by that,
  259. because it has to take into account a larger set of registers
  260. that are not equivalent.
  261. .PP
  262. There is a predefined property SCRATCH that is dynamic,
  263. i.e. a register can have the property SCRATCH one time,
  264. and loose it the next.
  265. A register has the property SCRATCH when it has a reference count of one.
  266. One needs to be able to discriminate between SCRATCH registers
  267. and others,
  268. because it is only allowed to do arithmetic on
  269. SCRATCH registers.
  270. .NH 2
  271. Stack token definition
  272. .PP
  273. The next part describes all possible tokens that can reside on
  274. the fakestack during code generation.
  275. Attributes of a token are described in the form of a C struct declaration,
  276. this is followed by the size in bytes of the token,
  277. optionally followed by the cost of the token when used as an addressing mode
  278. and the format
  279. to be used on output.
  280. .PP
  281. Tokens should usually be declared for every addressing mode
  282. of the machine at hand and for every size directly usable in
  283. a machine instruction.
  284. Example for the PDP-11 (incomplete):
  285. .DS L
  286. TOKENS:
  287. IREG2 = { REGISTER reg; } 2 "*%[reg]" /* indirect register */
  288. REGCONST = { REGISTER reg; STRING off; } 2 /* not really addressable */
  289. REGOFF2 = { REGISTER reg; STRING off; } 2 "%[off](%[reg])"
  290. IREGOFF2 = { REGISTER reg; STRING off; } 2 "*%[off](%[reg])"
  291. CONST = { INT off; } 2 cost=(2,850) "$%[off]."
  292. EXTERN2 = { STRING off; } 2 "%[off]"
  293. IEXTERN2 = { STRING off; } 2 "*%[off]"
  294. PAIRSIGNED = { REGISTER regeven,regodd; } 2 "%[regeven]"
  295. .DE
  296. .PP
  297. Types allowed in the struct are REGISTER, INT and STRING.
  298. Tokens without a printformat should never be output.
  299. .PP
  300. Notice that tokens need not correspond to addressing modes,
  301. the REGCONST token listed above,
  302. meaning the sum of the contents of the register and the constant,
  303. has no corresponding addressing mode on the PDP-11,
  304. but is included so that a sequence of add constant, load indirect,
  305. can be handled efficiently.
  306. This REGCONST token is needed as part of the path
  307. .DS
  308. REGISTER -> REGCONST -> REGOFF
  309. .DE
  310. of which the first and the last "exist" and the middle is needed
  311. only as an intermediate step.
  312. .NH 2
  313. Token expressions
  314. .PP
  315. Usually machines have certain collections of addressing modes that
  316. can be used with certain instructions.
  317. The stack patterns in the table are lists of these collections
  318. and since it is cumbersome to write out these long lists
  319. every time, there is a section here to give names to these
  320. collections.
  321. Please note that it is not forbidden to write out a token expression
  322. in the remainder of the table,
  323. but for clarity it is usually better not to.
  324. Example for the PDP-11 (incomplete):
  325. .DS L
  326. TOKENEXPRESSIONS:
  327. SOURCE2 = REG + IREG2 + REGOFF2 + IREGOFF2 + CONST + EXTERN2 +
  328. IEXTERN2
  329. SREG = REG * SCRATCH
  330. .DE
  331. Permissible in the expressions are all PASCAL set operators, i.e.
  332. .IP +
  333. set union
  334. .IP -
  335. set difference
  336. .IP *
  337. set intersection
  338. .PP
  339. Every tokenidentifier is also a token expression identifier
  340. denoting the singleton collection of tokens containing
  341. just itself.
  342. Every register property as defined above is also a token expression
  343. matching all registers with that property when on the fakestack.
  344. The standard token expression identifier ALL denotes the collection of
  345. all tokens.
  346. .NH 2
  347. Expressions
  348. .PP
  349. Throughout the rest of the table expressions can be used in some
  350. places.
  351. This section will give the syntax and semantics of expressions.
  352. There are four types of expressions: integer, string, register and undefined.
  353. Type checking is performed by
  354. .I cgg .
  355. An operator with at least one undefined operand returns undefined except
  356. for the defined() function mentioned below.
  357. An undefined expression is interpreted as FALSE when it is needed
  358. as a truth value.
  359. Basic terms in an expression are
  360. .IP number 16
  361. A number is a constant of type integer.
  362. .IP "string"
  363. A string within double quotes is a constant of type string.
  364. All the normal C style escapes may be used within the string.
  365. .IP REGIDENT
  366. The name of a register is a constant of type register.
  367. .IP $\fIi\fP
  368. A dollarsign followed by a number is the representation of the argument
  369. of EM instruction \fI\fP.
  370. The type of the operand is dependent on the instruction,
  371. sometimes it is integer,
  372. sometimes it is string.
  373. It is undefined when the instruction has no operand.
  374. .br
  375. Although an exhaustive list could be given describing all the types
  376. the following rule of thumb will suffice.
  377. If it is unimaginable for the operand of the instruction ever to be
  378. something different from a plain integer, the type is integer,
  379. otherwise it is string.
  380. .br
  381. .I Cg
  382. makes all necessary conversions,
  383. like adding EM_BSIZE to positive arguments of instructions
  384. dealing with locals,
  385. prepending underlines to global names,
  386. converting codelabels into a unique representation etc.
  387. Details about this can be found in the section about
  388. machine dependent C code.
  389. .IP %[1]
  390. This in general means the token mentioned first in the
  391. stack pattern.
  392. When used inside an expression the token must be a simple register.
  393. Type of this is register.
  394. .IP %[1.off]
  395. This means field "off" of the first stack pattern token.
  396. Type is the same as that of field "off".
  397. To use this expression implies a check that all tokens
  398. in the token expression used have the same attributes.
  399. .IP %[1.1]
  400. This is the first subregister of the first token.
  401. Previous comments apply.
  402. .IP %[b]
  403. The second allocated register.
  404. .IP %[a.2]
  405. The second subregister of the first allocated register.
  406. .PP
  407. All normal C operators apply to integers,
  408. the + operator serves for string concatenation
  409. and register expressions can only be compared to each other.
  410. Furthermore there are some special "functions":
  411. .IP tostring(e) 16
  412. Converts an integer expression e to a string.
  413. .IP defined(e)
  414. Returns 1 if expression e is defined, 0 otherwise.
  415. .IP samesign(e1,e2)
  416. Returns 1 if integer expression e1 and e2 have the same sign.
  417. .IP sfit(e1,e2)
  418. Returns 1 if integer expression e1 fits as a signed integer
  419. into a field of e2 bits, 0 otherwise.
  420. .IP ufit(e1,e2)
  421. Same as above but now for unsigned e1.
  422. .IP rom(a,n)
  423. Integer expression giving the n'th argument from the \fBrom\fP descriptor
  424. pointed at by the a'th EM instruction.
  425. Undefined if that descriptor does not exist.
  426. .IP loww(a)
  427. Returns the lower half of the argument of the a'th EM instruction.
  428. This is used to split the arguments of a \fBldc\fP instruction.
  429. .IP highw(a)
  430. Same for upper half.
  431. .NH 2
  432. Code rules
  433. .PP
  434. The largest section of the tables consists of the code generation rules.
  435. They specify EM patterns, stack patterns, code to be generated etc.
  436. Syntax is
  437. .DS L
  438. code rule : EM pattern '|' stack pattern '|' code '|'
  439. stack replacement '|' EM replacement '|' cost ;
  440. .DE
  441. All parts are optional, however there must be at least one pattern present.
  442. If the empattern is missing the rule becomes a rewriting rule or
  443. .I coercion
  444. to be used when code generation cannot continue
  445. because of an invalid stack pattern.
  446. The code rules are preceded by the word
  447. .DS
  448. CODE:
  449. .DE
  450. The next paragraphs describe the various parts in detail.
  451. .NH 3
  452. The EM pattern
  453. .PP
  454. The EM pattern consists of a list of EM mnemonics followed
  455. by a boolean expression.
  456. Examples:
  457. .DS
  458. \fBloe\fP
  459. .DE
  460. will match a single \fBloe\fP instruction,
  461. .DS
  462. \fBloc\fP \fBloc\fP \fBcif\fP $1==2 && $2==8
  463. .DE
  464. is a pattern that will match
  465. .DS
  466. \fBloc\fP 2
  467. \fBloc\fP 8
  468. \fBcif\fP
  469. .DE
  470. and
  471. .DS
  472. \fBlol\fP \fBinc\fP \fBstl\fP $1==$3
  473. .DE
  474. will match for example
  475. .DS
  476. .ta 10m 20m 30m 40m 50m 60m
  477. \fBlol\fP 6 \fBlol\fP -2 \fBlol\fP 4
  478. \fBinc\fP \fBinc\fP but \fInot\fP \fBinc\fP
  479. \fBstl\fP 6 \fBstl\fP -2 \fBstl\fP -4
  480. .DE
  481. A missing boolean expression evaluates to TRUE.
  482. .PP
  483. When the EM pattern is the same as in the previous code rule the pattern
  484. should be given as `...'.
  485. The code generator will match the longest EM pattern on every occasion,
  486. if two patterns of the same length match the first in the table will be chosen,
  487. while all patterns of length greater than or equal to three are considered
  488. to be of the same length.
  489. .NH 3
  490. The stack pattern
  491. .PP
  492. The stack pattern is a list of token expressions,
  493. usually token expression identifiers for clarity.
  494. No boolean expression is allowed here.
  495. The first expression is the one that matches the top of the stack.
  496. .PP
  497. The pattern can be followed by the word STACK
  498. in which case the pattern only matches if there is nothing
  499. else on the fakestack.
  500. The code generator will stack everything not matched at the start
  501. of the rule.
  502. .PP
  503. The pattern can be preceded with the word
  504. .DS
  505. nocoercions:
  506. .DE
  507. which tells the code generator not to try to coerce to the pattern
  508. but only to use it when it is already there.
  509. There are two reasons for this construction,
  510. correctness and speed.
  511. It is needed for correctness when the pattern contains a register
  512. that is not transparent when data is moved through it.
  513. .PP
  514. Example: on the PDP-11 the shortest code for
  515. .DS
  516. \fBlae\fP a
  517. \fBloi\fP 8
  518. \fBlae\fP b
  519. \fBsti\fP 8
  520. .DE
  521. is
  522. .DS
  523. movf _a,fr0
  524. movf fr0,_b
  525. .DE
  526. assuming that the floating point processor is in double
  527. precision mode and fr0 is free.
  528. Unfortunately this is not correct since a trap can occur on certain
  529. kinds of data.
  530. This could happen if there was a pattern for \fBsti\fP\ 8 that allowed
  531. one to move a floating point register not preceded by nocoercions: .
  532. The code generator would then find that moving the 8-byte global _a
  533. to a floating point register and then storing it to _b was the cheapest,
  534. assuming that the space/time knob was turned far enough to space.
  535. It is unfortunate that the type information is no longer present,
  536. since if _a really is a floating point number the move could be
  537. made without error.
  538. .PP
  539. The second reason for the nocoercions: construct is speed.
  540. When the code generator has a long list of possible stack patterns
  541. for one EM pattern it can waste a lot of time trying to find coercions
  542. to all of them, while the mere presence of such a long list
  543. indicates that the table writer has given a lot of special cases.
  544. In this case prepending all the special cases by nocoercions:
  545. will stop the code generator from trying to find things there aren't.
  546. .NH 3
  547. The code part
  548. .PP
  549. The code part consists of three parts, stack cleanup, register allocation
  550. and code to generate.
  551. All of these may be omitted.
  552. .NH 4
  553. Stack cleanup
  554. .PP
  555. The stack cleanup part describes certain stacktokens that should neither remain on
  556. the fakestack, nor remembered as contents of registers.
  557. This is usually only required with store operations.
  558. The entire fakestack, except for the part matched in the stack pattern,
  559. is searched for tokens matching the expression and they are copied
  560. to the real stack.
  561. Every register that contains the stacktoken is marked as empty.
  562. .PP
  563. Syntax is
  564. .DS
  565. remove(token expression) \fIor\fP
  566. remove(token expression, boolean expression)
  567. .DE
  568. Example:
  569. .DS
  570. remove(REGOFF2,%[reg] != LB || %[off] == $1)
  571. .DE
  572. is part of a remove() call for use in the \fBstl\fP code rule.
  573. It removes all register offsetted tokens where the register is not the
  574. localbase plus the local wherein the store is done.
  575. The necessity for this can be seen from the following example:
  576. .DS
  577. \fBlol\fP 4
  578. \fBinl\fP 4
  579. \fBstl\fP 6
  580. .DE
  581. Without a proper remove() call in the rule for \fBinl\fP code would
  582. be generated as here
  583. .DS
  584. inc 4(r5)
  585. mov 4(r5),6(r5)
  586. .DE
  587. so local 6 would be given the new value of local 4 instead of the old
  588. as the EM code prescribed.
  589. .PP
  590. When generating something like a branch instruction it
  591. might be needed to empty the fakestack completely.
  592. This can of course be done with
  593. .DS
  594. remove(ALL)
  595. .DE
  596. .NH 4
  597. Register allocation
  598. .PP
  599. The register allocation part describes the kind of registers needed.
  600. Syntax for allocate() is
  601. .DS
  602. allocate(itemlist)
  603. .DE
  604. where itemlist is a list of three kinds of things:
  605. .IP 1)
  606. a tokendescription, for example %[1].
  607. .br
  608. This will instruct the code generator to temporarily decrement the reference count
  609. of all registers contained in the token,
  610. so that they are available for allocation in this allocate() call
  611. if they were only used in that token.
  612. See example below.
  613. .IP 2)
  614. a register property.
  615. .br
  616. This will allocate a register with that property.
  617. The register will be marked as empty at this point.
  618. Lookahead will be performed if necessary.
  619. .IP 3)
  620. a register property with initialization.
  621. .br
  622. This will allocate the register as in 2) but will also
  623. initialize it.
  624. This eases the task of the code generator because it can
  625. find a register already filled with the right value
  626. if it exists.
  627. .PP
  628. Examples:
  629. .DS
  630. allocate(OREG)
  631. .DE
  632. will allocate an odd register, while
  633. .DS
  634. allocate(REG={REGOFF2,LB,$1})
  635. .DE
  636. will allocate a register while simultaneously filling it with
  637. the asked value.
  638. .br
  639. Inside the coercion from SOURCE2 to REGISTER in the PDP-11 table
  640. the following allocate() can be found.
  641. .DS
  642. allocate(%[1],REG=%[1])
  643. .DE
  644. This tells the code generator that registers contained in %[1] can be used
  645. again and asks to fill the register allocated with %[1].
  646. So if %[1]={REGOFF2,R3,"4"} and R3 has a reference count of 1
  647. the following code might be generated.
  648. .DS
  649. mov 4(r3),r3
  650. .DE
  651. In the rest of the line the registers allocated can be named by
  652. %[a] and %[b.1],%[b.2], i.e. with lower case letters
  653. in order of allocation.
  654. .PP
  655. Warning:
  656. .DS
  657. allocate(R3)
  658. .DE
  659. is \fRnot\fP the way to allocate R3.
  660. R3 is not a register property, so it will be seen as a token description
  661. and the effect is that R3 will have its reference count decremented.
  662. .NH 4
  663. Code
  664. .PP
  665. Code to be generated is specified as a list of items of the following kind:
  666. .IP 1)
  667. a string in double quotes ("This is a string").
  668. .br
  669. This is copied to the codefile and a newline ( \en ) is appended.
  670. Inside the string all normal C string conventions are allowed,
  671. and substitutions can be made of the following sorts.
  672. .RS
  673. .IP a)
  674. $1, $2 etc.
  675. These are the operands of the corresponding EM instructions
  676. and are printed according to their type.
  677. To put a real '$' inside the string it must be doubled ('$$').
  678. .IP b)
  679. %[1], %[2.reg], %[b.1] etc.
  680. These have their obvious meaning.
  681. If they describe a complete token ( %[1] )
  682. the printformat for the token is used.
  683. If they stand for a basic term in an expression
  684. they will be printed according to their type.
  685. To put a real '%' inside the string it must be doubled ('%%').
  686. .IP c)
  687. %( arbitrary expression %).
  688. This allows inclusion of arbitrary expressions inside strings.
  689. Usually not needed very often,
  690. so that the awkward notation is not too bad.
  691. Note that %(%[1]%) is equivalent to %[1].
  692. .RE
  693. .IP 2)
  694. a move() call.
  695. This has the following syntax:
  696. .DS
  697. move(token description, token description)
  698. .DE
  699. Moves are handled specially since that enables the code generator
  700. to keep track of register contents.
  701. Example:
  702. .DS
  703. move(R3,{REGOFF2,LB,$1})
  704. .DE
  705. will generate code to move R3 to $1(r5) except when
  706. R3 already was a copy of $1(r5).
  707. Then the code will be omitted.
  708. The rules describing how to move things to each other
  709. can be found in the MOVES section described below.
  710. .IP 3)
  711. an erase() call.
  712. This has the following syntax:
  713. .DS
  714. erase(register expression)
  715. .DE
  716. This tells the code generator that the register mentioned no longer has any
  717. useful value.
  718. This is
  719. .I necessary
  720. after code in the table has changed the contents of registers.
  721. For example, after an add to a register the register must be erased,
  722. because the contents do no longer match any token.
  723. .IP 4)
  724. For machines that have condition codes,
  725. alas most of them do,
  726. there are provisions to remember condition code setting
  727. and prevent needless testing.
  728. To set the condition code to a token put in the code the following call:
  729. .DS
  730. test(token)
  731. .DE
  732. where token can be all of the standard forms that can also be used in move().
  733. This will generate a test if the condition codes
  734. were not already set to that token.
  735. It is also possible to tell
  736. .I cg
  737. that a certain operation, like a preceding add
  738. has set the condition codes to some token with the call
  739. .DS
  740. setcc(token)
  741. .DE
  742. So a sequence of a setcc and a test on the same token will generate
  743. no code.
  744. Another allowed call within the code is
  745. .DS
  746. samecc
  747. .DE
  748. which tells the code generator that condition codes were unaffected
  749. in this rule.
  750. If no setcc or samecc has been given the default is
  751. .DS
  752. nocc
  753. .DE
  754. when a piece of code contained strings,
  755. which tells the code generator that the condition codes
  756. have no useful value any more.
  757. .NH 3
  758. Stack replacement
  759. .PP
  760. The stack replacement is a possibly empty list of items to be pushed onto
  761. the fakestack. Three kinds of items are possible:
  762. .IP 1)
  763. An item of the form %[1]. This will push the stacktoken mentioned back
  764. onto the stack unchanged.
  765. .IP 2)
  766. A register expression. This will push the register mentioned
  767. onto the fakestack.
  768. .IP 3)
  769. An item of the form { REGOFF2,%[1.reg],$1 }.
  770. This generates a token with tokenidentifier REGOFF2 and attributes
  771. in order of declaration.
  772. .PP
  773. All tokens matched by the stack pattern at the beginning of the code rule
  774. are first removed and their registers deallocated.
  775. Items are pushed in the order of appearance.
  776. This means that the last item will be on the top of the
  777. stack after the push.
  778. So if the stack pattern contained two token expressions
  779. and they must be pushed back unchanged,
  780. they have to be specified as stack replacement
  781. .DS
  782. %[2] %[1]
  783. .DE
  784. and not the other way around.
  785. .NH 3
  786. EM replacement
  787. .PP
  788. In exceptional cases it might be useful to leave part of an empattern
  789. undone.
  790. For example, a \fBsdl\fP instruction might be split into two \fBstl\fP instructions
  791. when there is no 4-byte quantity on the stack. The emreplacement part allows
  792. one to express this.
  793. Example:
  794. .DS
  795. \fBstl\fP $1 \fBstl\fP $1+2
  796. .DE
  797. The instructions are inserted in the stream so that they can match
  798. the first part of a pattern in the next step.
  799. Note that since the code generator traverses the EM instructions in a strict
  800. linear fashion,
  801. it is impossible to let the EM replacement match later parts of a pattern.
  802. So if there is a pattern
  803. .DS
  804. \fBloc\fP \fBstl\fP $1==0
  805. .DE
  806. and the input is
  807. .DS
  808. \fBloc\fP 0 \fBsdl\fP 4
  809. .DE
  810. the \fBloc\fP\ 0 will be processed first,
  811. then the \fBsdl\fP might be split into two \fBstl\fP's but the pattern
  812. cannot match now.
  813. .NH 3
  814. Cost
  815. .PP
  816. The cost field can be specified when there is more than one
  817. code rule with the same empattern.
  818. If the code generator has a choice between two possibilities
  819. to generate code it will choose the cheapest according to
  820. the cost field.
  821. The cost for a code generation is the sum of the costs
  822. of all the coercions needed, plus the cost for freeing
  823. registers plus the cost of the code rule itself.
  824. .PP
  825. The format of the costfield is
  826. .DS
  827. ( nbytes, time ) or
  828. ( nbytes, time ) + %[\fIi\fP]
  829. .DE
  830. with time in the metric desired, like nanoseconds or states.
  831. See constants section above.
  832. The %[\fIi\fP] in the second example is used for adding the cost of a certain
  833. address mode used in the code generated.
  834. This can of course be repeated if desired.
  835. The cost of the address mode must then be specified in the token definition
  836. section.
  837. .NH 3
  838. Examples
  839. .PP
  840. A list of examples for the PDP-11 is given here.
  841. Far from being complete it gives examples of most kinds
  842. of instructions.
  843. .DS L
  844. \fBadi\fP $1==2 | SREG,SOURCE2 |
  845. "add %[2],%[1]" erase(%[1]) setcc(%[1])
  846. | %[1] | | (2,450) + %[2]
  847. \&... | SOURCE2,SREG |
  848. "add %[1],%[2]" erase(%[2]) setcc(%[2])
  849. | %[2] | | (2,450) + %[1]
  850. .DE
  851. is an example of the use of the `...' construct
  852. and shows how to place erase() and setcc() calls.
  853. .DS L
  854. \fBdvi\fP $1==2 | SOURCE2,SPAIRSIGNED |
  855. "div %[1],%[2]" erase(%[2])
  856. | %[2.regeven] | |
  857. \fBcmi\fP \fBtgt\fP $1==2 | SOURCE2,SOURCE2 | allocate(REG={CONST,0})
  858. "cmp %[2],%[1];ble 1f;inc %[a];1:" erase(%[a])
  859. | %[a] | |
  860. \fBcal\fP | STACK |
  861. "jsr pc,$1"
  862. | | |
  863. \fBlol\fP | | | { REGOFF2, LB, $1 } | |
  864. \fBstl\fP | SOURCE2 |
  865. remove(REGOFF2,%[off]==$1)
  866. move(%[1],{REGOFF2,LB,$1})
  867. | | |
  868. | SOURCE2 |
  869. allocate(%[1],REGPAIR)
  870. move(%[1],%[a.2])
  871. test(%[a.2])
  872. "sxt %[a.even]" | { PAIRSIGNED, %[a.1], %[a.2] }| |
  873. .DE
  874. This coercion shows how to use the move and test calls.
  875. At first one might think that the testcall is unnecessary,
  876. since the move will have set the condition codes,
  877. but the move may never have been executed
  878. if the register already contained the value,
  879. in which case it is necessary to do the test.
  880. If the move was executed the test will be omitted.
  881. .DS L
  882. | SOURCE2 | allocate(%[1],REG=%[1]) | %[a] | |
  883. \fBsdl\fP | SOURCE2 | | %[1] | \fBstl\fP $1 \fBstl\fP $1+2 |
  884. \fBexg\fP $1==2 | SOURCE2 SOURCE2 | | %[1] %[2] | |
  885. .DE
  886. This last example again shows the difference in the order
  887. of the stack pattern and the stack replacement.
  888. .NH 2
  889. Move code rules
  890. .PP
  891. When issuing a move() call as described above or a register allocation
  892. with initialization, the code generator has to know which
  893. instruction to use for the move.
  894. The code will of course only be generated if it cannot be omitted.
  895. This is listed in the move section of the tables by giving a list
  896. of tuples:
  897. .DS
  898. ( source, destination, codepart [ , costfield ] )
  899. .DE
  900. where the square brackets mean the costfield is optional.
  901. Example for the PDP-11
  902. .DS
  903. MOVES:
  904. ( CONST %[off]==0 , SOURCE2, "clr %[2]" )
  905. ( SOURCE2, SOURCE2, "mov %[1],%[2]" )
  906. .DE
  907. The moves are scanned from top to bottom,
  908. so the first one that matches will be chosen.
  909. .NH 2
  910. Test code rules
  911. .PP
  912. When issuing a test() call as described above,
  913. the code generator has to know which instruction
  914. to use for the test.
  915. The code will only be generated if the condition codes
  916. were not already set to the token.
  917. This is listed in the test section of the tables by giving
  918. a list of tuples:
  919. .DS
  920. ( source, codepart [ , costfield ] )
  921. .DE
  922. Example for the PDP-11
  923. .DS
  924. TESTS:
  925. ( SOURCE2, "tst %[1]")
  926. ( DREG, "tstf %[1]\encfcc")
  927. .DE
  928. The tests are scanned from top to bottom,
  929. so the first one that matches will be chosen.
  930. .NH 2
  931. Stacking code rules.
  932. .PP
  933. When the code generator has to stack a token it must know
  934. which code to use.
  935. Since it must at all times be possible to empty the fakestack
  936. even when no registers are free,
  937. it is mandatory that all
  938. tokens used must have a rule attached for stacking them
  939. without using a scratch register.
  940. Since however this might be clumsy and
  941. a register might in practice be available
  942. it is also possible to give rules
  943. which use a register.
  944. On the Intel 8086 for example,
  945. there is no instruction to push a constant without using a register,
  946. and the code needed to do it without, must use global data
  947. and as such is very complicated and wasteful of memory and time.
  948. It can therefore be left to be used in extreme cases,
  949. while in general the constant is pushed through a register.
  950. The stacking rules are listed in the stack section of the table as a list
  951. of tuples:
  952. .DS
  953. (source, [ register property ] , codepart [ , costfield ] )
  954. .DE
  955. Example for the Intel 8086:
  956. .DS
  957. STACKS:
  958. (CONST, REG, move(%[1],%[a]) "push %[a]")
  959. (REG ,, "push %[1]")
  960. .DE
  961. .NH 1
  962. The files mach.h and mach.c
  963. .PP
  964. The table writer must also supply two files containing
  965. machine dependent declarations and C code.
  966. These files are mach.h and mach.c.
  967. .NH 2
  968. Types in the code generator
  969. .PP
  970. Three different types of integer coexist in the code generator
  971. and their range depends on the machine at hand.
  972. The type 'int' is used for things like labelcounters that won't require
  973. more than 16 bits precision.
  974. The type 'word' is used among others to assemble datawords and
  975. is of type 'long'.
  976. The type 'full' is used for addresses and is of type 'long' if
  977. EM_WSIZE>2 or EM_PSIZE>2.
  978. .PP
  979. In macro and function definitions in later paragraphs implicit typing
  980. will be used for parameters, that is parameters starting with an 's'
  981. will be of type string, and the letters 'i','w','f' will stand for
  982. int, word and full respectively.
  983. .NH 2
  984. Global variables to work with
  985. .PP
  986. Some global variables are present in the code generator
  987. that can be manipulated by the routines in mach.h and mach.c.
  988. .LP
  989. The declarations are:
  990. .DS L
  991. .ta 20
  992. FILE *codefile; /* code is emitted on this stream */
  993. word part_word; /* words to be output are put together here */
  994. int part_size; /* number of bytes already put in part_word */
  995. char str[]; /* Last string read in */
  996. long argval; /* Last int read and kept */
  997. .DE
  998. .NH 2
  999. Macros in mach.h
  1000. .PP
  1001. In the file mach.h a collection of macros is defined that have
  1002. to do with formatting of assembly code for the machine at hand.
  1003. Some of these macros can of course be left undefined in which case the
  1004. macro calls are left in the source and will be treated as
  1005. function calls.
  1006. These functions can then be defined in \fImach.c\fR.
  1007. .PP
  1008. The macros to be defined are:
  1009. .IP ex_ap(s) 16
  1010. Must print the magic incantations that will mark the symbol \fI\fR
  1011. to be exported to other modules.
  1012. This is the translation of the EM \fBexa\fP and \fBexp\fP instructions.
  1013. .IP in_ap(s)
  1014. Same to import the symbol.
  1015. Translation of \fBina\fP and \fBinp\fP.
  1016. .IP newplb(s)
  1017. Must print the definition of procedure label \fIs\fR.
  1018. If left undefined the newilb() macro is used instead.
  1019. .IP newilb(s)
  1020. Must print the definition of instruction label \fIs\fR.
  1021. .IP newdlb(s)
  1022. Must print the definition of data label \fIs\fR.
  1023. .IP dlbdlb(s1,s2)
  1024. Must define data label
  1025. .I s1
  1026. to be equal to
  1027. .I s2 .
  1028. .IP newlbss(s,f)
  1029. Must declare a piece of memory initialized to BSS_INIT(see below)
  1030. of length
  1031. .I f
  1032. and with label
  1033. .I s .
  1034. .IP cst_fmt
  1035. Format to be used when converting constant arguments of
  1036. EM instructions to string.
  1037. Argument to be formatted will be 'full'.
  1038. .IP off_fmt
  1039. Format to be used for integer part of label+constant,
  1040. argument will be 'full'.
  1041. .IP fmt_ilb(ip,il,s)
  1042. Must use the numbers
  1043. .I ip
  1044. and
  1045. .I il
  1046. which are a procedure number
  1047. and a label number respectively and copy a string to
  1048. .I s
  1049. that must be unique for that combination.
  1050. This procedure is optional, if it is not given ilb_fmt
  1051. must be defined as below.
  1052. .IP ilb_fmt
  1053. Format to be used for creation of unique instruction labels.
  1054. Arguments will be a unique procedure number (int) and the label
  1055. number (int).
  1056. .IP dlb_fmt
  1057. Format to be used for printing numeric data labels.
  1058. Argument will be 'int'.
  1059. .IP hol_fmt
  1060. Format to be used for generation of labels for
  1061. space generated by a
  1062. .B hol
  1063. pseudo.
  1064. Argument will be 'int'.
  1065. .IP hol_off
  1066. Format to be used for printing of the address of an element in
  1067. .B hol
  1068. space.
  1069. Arguments will be the offset in the
  1070. .B hol
  1071. block (word) and the number of the
  1072. .B hol
  1073. (int).
  1074. .IP con_cst(w)
  1075. Must generate output that will assemble into one machineword.
  1076. .IP con_ilb(s)
  1077. Must generate output that will put the address of the instruction label
  1078. into the datastream.
  1079. .IP con_dlb(s)
  1080. Must generate output that will put the address of the data label
  1081. into the datastream.
  1082. .IP fmt_id(sf,st)
  1083. Must take the string in
  1084. .I sf
  1085. which is a nonnumeric global label, and transform it into a copy made to
  1086. .I st
  1087. which will not collide with reserved assembler words and system labels.
  1088. This procedure is optional, if it is not given the id_first macro is used
  1089. as defined below.
  1090. .IP id_first
  1091. Must be a character.
  1092. This is prepended to all nonnumeric global labels if their length
  1093. is shorter than the maximum allowed(currently 8) or if they already
  1094. start with that character.
  1095. This is to avoid conflicts of user labels with system labels.
  1096. .IP BSS_INIT
  1097. Must be a constant.
  1098. This is the value filled in all the words not initialized explicitly.
  1099. This is loader and system dependent.
  1100. If omitted no initialization is assumed.
  1101. .NH 3
  1102. Example mach.h for the PDP-11
  1103. .DS L
  1104. .ta 8 16 24 32 40 48 56
  1105. #define ex_ap(y) fprintf(codefile,"\et.globl %s\en",y)
  1106. #define in_ap(y) /* nothing */
  1107. #define newplb(x) fprintf(codefile,"%s:\en",x)
  1108. #define newilb(x) fprintf(codefile,"%s:\en",x)
  1109. #define newdlb(x) fprintf(codefile,"%s:\en",x)
  1110. #define dlbdlb(x,y) fprintf(codefile,"%s=%s\en",x,y)
  1111. #define newlbss(l,x) fprintf(codefile,"%s:.=.+%d.\en",l,x);
  1112. #define cst_fmt "$%d."
  1113. #define off_fmt "%d."
  1114. #define ilb_fmt "I%x_%x"
  1115. #define dlb_fmt "_%d"
  1116. #define hol_fmt "hol%d"
  1117. #define hol_off "%ld.+hol%d"
  1118. #define con_cst(x) fprintf(codefile,"%ld.\en",x)
  1119. #define con_ilb(x) fprintf(codefile,"%s\en",x)
  1120. #define con_dlb(x) fprintf(codefile,"%s\en",x)
  1121. #define id_first '_'
  1122. #define BSS_INIT 0
  1123. .DE
  1124. .NH 2
  1125. Functions in mach.c
  1126. .PP
  1127. In mach.c some functions must be supplied,
  1128. mostly manipulating data resulting from pseudoinstructions.
  1129. The specifications are given here,
  1130. implicit typing of parameters as above.
  1131. .IP con_part(isz,word) 20
  1132. This function must manipulate the globals
  1133. part_word and part_size to append the isz bytes
  1134. contained in word to the output stream.
  1135. If part_word is full, i.e. part_size==EM_WSIZE
  1136. the function part_flush() may be called to empty the buffer.
  1137. This is the function that must go through the trouble of
  1138. doing byte order in words correct.
  1139. .IP con_mult(w_size)
  1140. This function must take the string str[] and create an integer
  1141. from the string of size w_size and generate code to assemble global
  1142. data for that integer.
  1143. Only the sizes for which arithmetic is implemented need be
  1144. handled,
  1145. so if 200-byte integer division is not implemented,
  1146. 200-byte integer global data do not have to be implemented.
  1147. Here one must take care of word order in long integers.
  1148. .IP con_float()
  1149. This function must generate code to assemble a floating
  1150. point number of which the size is contained in argval
  1151. and the ASCII representation in str[].
  1152. .IP prolog(f_nlocals)
  1153. This function is called at the start of every procedure.
  1154. Function prolog code must be generated,
  1155. and room made for local variables for a total of f_nlocals bytes.
  1156. .IP mes(w_mesno)
  1157. This function is called when a
  1158. .B mes
  1159. pseudo is seen that is not handled by the machine independent part.
  1160. The example below probably shows all the table writer ever has to know
  1161. about that.
  1162. .IP segname[]
  1163. This is not a function,
  1164. but an array of four strings.
  1165. These strings are put out whenever the code generator
  1166. switches segments.
  1167. Segments are SEGTXT, SEGCON, SEGROM and SEGBSS in that order.
  1168. .NH 3
  1169. Example mach.c for the PDP-11
  1170. .PP
  1171. As an example of the sort of code expected,
  1172. the mach.c for the PDP-11 is presented here.
  1173. .DS L
  1174. .ta 8 16 24 32 40 48 56 64
  1175. /*
  1176. * machine dependent back end routines for the PDP-11
  1177. */
  1178. con_part(sz,w) register sz; word w; {
  1179. while (part_size % sz)
  1180. part_size++;
  1181. if (part_size == EM_WSIZE)
  1182. part_flush();
  1183. if (sz == 1) {
  1184. w &= 0xFF;
  1185. if (part_size)
  1186. w <<= 8;
  1187. part_word |= w;
  1188. } else {
  1189. assert(sz == 2);
  1190. part_word = w;
  1191. }
  1192. part_size += sz;
  1193. }
  1194. con_mult(sz) word sz; {
  1195. long l;
  1196. if (sz != 4)
  1197. fatal("bad icon/ucon size");
  1198. l = atol(str);
  1199. fprintf(codefile,"\et%o;%o\en",(int)(l>>16),(int)l);
  1200. }
  1201. con_float() {
  1202. double f;
  1203. register short *p,i;
  1204. /*
  1205. * This code is correct only when the code generator is
  1206. * run on a PDP-11 or VAX-11 since it assumes native
  1207. * floating point format is PDP-11 format.
  1208. */
  1209. if (argval != 4 && argval != 8)
  1210. fatal("bad fcon size");
  1211. f = atof(str);
  1212. p = (short *) &f;
  1213. i = *p++;
  1214. if (argval == 8) {
  1215. fprintf(codefile,"\et%o;%o;",i,*p++);
  1216. i = *p++;
  1217. }
  1218. fprintf(codefile,"\et%o;%o\en",i,*p++);
  1219. }
  1220. prolog(nlocals) full nlocals; {
  1221. fprintf(codefile,"mov r5,-(sp)\enmov sp,r5\en");
  1222. if (nlocals == 0)
  1223. return;
  1224. if (nlocals == 2)
  1225. fprintf(codefile,"tst -(sp)\en");
  1226. else
  1227. fprintf(codefile,"sub $%d.,sp\en",nlocals);
  1228. }
  1229. mes(type) word type; {
  1230. int argt ;
  1231. switch ( (int)type ) {
  1232. case ms_ext :
  1233. for (;;) {
  1234. switch ( argt=getarg(
  1235. ptyp(sp_cend)|ptyp(sp_pnam)|sym_ptyp) ) {
  1236. case sp_cend :
  1237. return ;
  1238. default:
  1239. strarg(argt) ;
  1240. fprintf(codefile,".globl %s\en",argstr) ;
  1241. break ;
  1242. }
  1243. }
  1244. default :
  1245. while ( getarg(any_ptyp) != sp_cend ) ;
  1246. break ;
  1247. }
  1248. }
  1249. char *segname[] = {
  1250. ".text", /* SEGTXT */
  1251. ".data", /* SEGCON */
  1252. ".data", /* SEGROM */
  1253. ".bss" /* SEGBSS */
  1254. };
  1255. .DE
  1256. .NH 1
  1257. Coercions
  1258. .PP
  1259. A central part in code generation is taken by the
  1260. .I coercions .
  1261. It is the responsibility of the table writer to provide
  1262. all necessary coercions so that code generation can continue.
  1263. The very minimal set of coercions are
  1264. the coercions to unstack every token expression,
  1265. in combination with the rules to stack every token.
  1266. .PP
  1267. If these are present the code generator can always make the necessary
  1268. transformations by stacking and unstacking.
  1269. Of course for codequality it is usually best to provide extra coercions
  1270. to prevent this stacking to take place.
  1271. .I Cg
  1272. discriminates three types of coercions:
  1273. .IP 1)
  1274. Unstacking coercions.
  1275. This category can use the allocate() call in its code.
  1276. .IP 2)
  1277. Splitting coercions, these are the coercions that split
  1278. larger tokens into smaller ones.
  1279. .IP 3)
  1280. Transforming coercions, these are the coercions that transform
  1281. a token into another one of the same size.
  1282. This category can use the allocate() call in its code.
  1283. .PP
  1284. When a stack configuration does not match the stack pattern
  1285. .I coercions
  1286. are searched for in the following order:
  1287. .IP 1)
  1288. First tokens are split if necessary to get their sizes right.
  1289. .IP 2)
  1290. Then transforming coercions are found that will make the pattern match.
  1291. .IP 3)
  1292. Finally if the stack pattern is longer than the fakestack contents
  1293. unstacking coercions will be used to fill up the pattern.
  1294. .PP
  1295. At any point, when coercions are missing so code generation could not
  1296. continue, the offending tokens are stacked.
  1297. .NH 1
  1298. Internal workings of the code generator.
  1299. .NH 2
  1300. Description of tables.c and tables.h contents
  1301. .PP
  1302. In this section the intermediate files will be described
  1303. that are produced by
  1304. .I cgg
  1305. and compiled with machine independent code to produce a code generator.
  1306. .NH 3
  1307. Tables.c
  1308. .PP
  1309. Tables.c contains a large number of initialized array's of all sorts.
  1310. Description of each follows:
  1311. .br
  1312. .in 1i
  1313. .ti -0.5i
  1314. byte code rules[]
  1315. .br
  1316. Pseudo code interpreted by the code generator.
  1317. Always starts with some opcode followed by operands depending
  1318. on the opcode.
  1319. Integers in this table are between 0 and 32767 and have a one byte
  1320. encoding if between 0 and 127.
  1321. .ti -0.5i
  1322. char stregclass[]
  1323. .br
  1324. Number of computed static register class per register.
  1325. Two registers are in the same class if they have the same properties
  1326. and don't share a common subregister.
  1327. .ti -0.5i
  1328. struct reginfo machregs[]
  1329. .br
  1330. Info per register.
  1331. Initialized with representation string, size,
  1332. members of the register and set of registers affected when this
  1333. one is changed.
  1334. Also contains room for runtime information,
  1335. like contents and reference count.
  1336. .ti -0.5i
  1337. tkdef_t tokens[]
  1338. .br
  1339. Information per tokentype.
  1340. Initialized with size, cost, type of operands and formatstring.
  1341. .ti -0.5i
  1342. node_t enodes[]
  1343. .br
  1344. List of triples representing expressions for the code generator.
  1345. .ti -0.5i
  1346. string code strings[]
  1347. .br
  1348. List of strings.
  1349. All strings are put in a list and checked for duplication,
  1350. so only one copy per string will reside here.
  1351. .ti -0.5i
  1352. set_t machsets[]
  1353. .br
  1354. List of token expression sets.
  1355. Bit 0 of the set is used for the SCRATCH property of registers,
  1356. bit 1 upto NREG are for the corresponding registers
  1357. and bit NREG+1 upto the end are for corresponding tokens.
  1358. .ti -0.5i
  1359. inst_t tokeninstances[]
  1360. .br
  1361. List of descriptions for building tokens.
  1362. Contains type of rule for building one,
  1363. plus operands depending on the type.
  1364. .ti -0.5i
  1365. move_t moves[]
  1366. .br
  1367. List of move rules.
  1368. Contains token expressions for source and destination
  1369. plus cost and index for code rule.
  1370. .ti -0.5i
  1371. byte pattern[]
  1372. .br
  1373. EM patterns.
  1374. This is structured internally as chains of patterns,
  1375. each chain pointed at by pathash[].
  1376. After each pattern the list of possible code rules is given.
  1377. .ti -0.5i
  1378. int pathash[256]
  1379. .br
  1380. Indices into pattern[] for all patterns with a certain low order
  1381. byte of the hashing function.
  1382. .ti -0.5i
  1383. c1_t c1coercs[]
  1384. .br
  1385. List of rules to stack tokens.
  1386. Contains token expressions,
  1387. register needed,
  1388. cost
  1389. and code rule.
  1390. .ti -0.5i
  1391. c2_t c2coercs[]
  1392. .br
  1393. List of splitting coercions.
  1394. Token expressions,
  1395. split factor,
  1396. replacements
  1397. and code rule.
  1398. .ti -0.5i
  1399. c3_t c3coercs[]
  1400. .br
  1401. List of one to one coercions.
  1402. Token expressions,
  1403. register needed,
  1404. replacement
  1405. and code rule.
  1406. .ti -0.5i
  1407. struct reginfo **reglist[]
  1408. .br
  1409. List of lists of pointers to register information.
  1410. For every property the list is here
  1411. to find the registers corresponding to it.
  1412. .in 0
  1413. .NH 3
  1414. tables.h
  1415. .PP
  1416. In tables.h various derived constants for the tables are
  1417. given.
  1418. They are then used to determine array sizes in the actual code generator,
  1419. plus loop termination in some cases.
  1420. .NH 2
  1421. Other important data structures
  1422. .PP
  1423. During code generation some other data structures are used
  1424. and here is a short description of some of the important ones.
  1425. .PP
  1426. Tokens are kept in the code generator as a struct consisting of
  1427. one integer
  1428. .I t_token
  1429. which is -1 if the token is a register,
  1430. and the number of the token otherwise,
  1431. plus an array of
  1432. .I TOKENSIZE
  1433. unions
  1434. .I t_att
  1435. of which the first is the register number in case of a register.
  1436. .PP
  1437. The fakestack is an array of these tokens,
  1438. there is a global variable
  1439. .I stackheight .
  1440. .PP
  1441. The results of expressions are kept in a struct
  1442. .I result
  1443. with elements
  1444. .I e_typ ,
  1445. giving the type of the expression:
  1446. .I EV_INT ,
  1447. .I EV_REG
  1448. or
  1449. .I EV_STR ,
  1450. and a union
  1451. .I e_v
  1452. which contains the real result.
  1453. .NH 2
  1454. A tour through the sources
  1455. .NH 3
  1456. codegen.c
  1457. .PP
  1458. The file codegen.c contains one large function consisting
  1459. of one giant switch statement.
  1460. It is the interpreter for the code generator pseudo code
  1461. as contained in code rules[].
  1462. This function can call itself recursively when doing lookahead.
  1463. Arguments are:
  1464. .IP codep 10
  1465. Pointer into code rules, pseudo program counter.
  1466. .IP ply
  1467. Number of EM pattern lookahead allowed.
  1468. .IP toplevel
  1469. Boolean telling whether this is the toplevel codegen() or
  1470. a deeper incarnation.
  1471. .IP costlimit
  1472. A cutoff value to limit searches.
  1473. If the cost crosses costlimit the incarnation can terminate.
  1474. .IP forced
  1475. A register number if nonzero.
  1476. This is used inside coercions to force the allocate() call to allocate
  1477. a register determined by earlier lookahead.
  1478. .PP
  1479. The instructions inplemented in the switch:
  1480. .NH 4
  1481. DO_NEXTEM
  1482. .PP
  1483. Matches the next EM pattern and does lookahead if necessary to find the best
  1484. code rule associated with this pattern.
  1485. Heuristics are used to determine best code rule when possible.
  1486. This is done by calling the distance() function.
  1487. .NH 4
  1488. DO_COERC
  1489. .PP
  1490. This sets the code generator in the state to do a from stack coercion.
  1491. .NH 4
  1492. DO_XMATCH
  1493. .PP
  1494. This is done when a match no longer has to be checked.
  1495. Used when the nocoercions: trick is used in the table.
  1496. .NH 4
  1497. DO_MATCH
  1498. .PP
  1499. This is the big one inside this function.
  1500. It has the task to transform the contents of the current
  1501. fakestack to match the pattern given after it.
  1502. .PP
  1503. Since the code generator does not know combining coercions,
  1504. i.e. there is no way to make a big token out of two smaller ones,
  1505. the first thing done is to stack every token that is too small.
  1506. After that all tokens too big are split if possible to the right size.
  1507. .PP
  1508. Next the coercions are sought that would transform tokens in place to
  1509. the right one, plus the coercions that would pop tokens of the stack.
  1510. Each of those might need a register, so a list of registers is generated
  1511. and at the end of looking for coercions the function
  1512. .I tuples()
  1513. is called to generate the list of all possible \fIn\fP-tuples,
  1514. where
  1515. .I n
  1516. equals the number of registers needed.
  1517. .PP
  1518. Lookahead is now performed if the number of tuples is greater than one.
  1519. If no possibility is found within the costlimit,
  1520. the fakestack is made smaller by pushing the bottom token,
  1521. and this process is repeated until either a way is found or
  1522. the fakestack is completely empty and there is still no way
  1523. to make the match.
  1524. .PP
  1525. If there is a way the corresponding coercions are executed
  1526. and the code is finished.
  1527. .NH 4
  1528. DO_REMOVE
  1529. .PP
  1530. Here the remove() call is executed, all tokens matched by the
  1531. token expression plus boolean expression are pushed.
  1532. In the current implementation there is no attempt to move those
  1533. tokens to registers, but that is a possible future extension.
  1534. .NH 4
  1535. DO_DEALLOCATE
  1536. .PP
  1537. This one temporarily decrements by one the reference count of all registers
  1538. contained in the token given as argument.
  1539. .NH 4
  1540. DO_REALLOCATE
  1541. .PP
  1542. Here all temporary deallocates are made undone.
  1543. .NH 4
  1544. DO_ALLOCATE
  1545. .PP
  1546. This is the part that allocates a register and decides which one to use.
  1547. If the
  1548. .I forced
  1549. argument was given its task is simple,
  1550. otherwise some work must be done.
  1551. First the list of possible registers is scanned,
  1552. all free registers noted and it is noted whether any of those
  1553. registers is already
  1554. containing the initialization.
  1555. If no registers are available some fakestack token is stacked and the
  1556. process is repeated.
  1557. .PP
  1558. After that if an exact match was found,
  1559. the list of registers is reduced to one register matching exactly
  1560. out of every register class.
  1561. Now lookahead is performed if necessary and the register chosen.
  1562. If an initialization was given the corresponding move is performed,
  1563. otherwise the register is marked empty.
  1564. .NH 4
  1565. DO_LOUTPUT
  1566. .PP
  1567. This prints a string and an expression.
  1568. Only done on toplevel.
  1569. .NH 4
  1570. DO_ROUTPUT
  1571. .PP
  1572. Prints a string and a new line.
  1573. Only on toplevel.
  1574. .NH 4
  1575. DO_MOVE
  1576. .PP
  1577. Calls the move() function in the code generator to implement the move()
  1578. function in the table.
  1579. .NH 4
  1580. DO_ERASE
  1581. .PP
  1582. Marks the register that is its argument as empty.
  1583. .NH 4
  1584. DO_TOKREPLACE
  1585. .PP
  1586. This is the token replacement part.
  1587. It is also called if there is no token replacement because it has
  1588. some other functions as well.
  1589. .PP
  1590. First the tokens that will be pushed on the fakestack are computed
  1591. and stored in a temporary array.
  1592. Then the tokens that were matched in this rule are popped
  1593. and their embedded registers have their reference count
  1594. decremented.
  1595. After that the replacement tokens are pushed.
  1596. .PP
  1597. Finally all registers allocated in this rule have their reference count
  1598. decremented.
  1599. If they were not pushed on the fakestack they will be available again
  1600. in the next code rule.
  1601. .NH 4
  1602. DO_EMREPLACE
  1603. .PP
  1604. Places replacement EM instructions back into the instruction stream.
  1605. .NH 4
  1606. DO_COST
  1607. .PP
  1608. Accounts for cost as given in the code rule.
  1609. .NH 4
  1610. DO_RETURN
  1611. .PP
  1612. Returns from this level of codegen().
  1613. Is used at the end of coercions,
  1614. move rules etc..
  1615. .NH 3
  1616. compute.c
  1617. .PP
  1618. This module computes the various expressions as given
  1619. in the enodes[] array.
  1620. Nothing very special happens here,
  1621. it is just a recursive function computing leaves
  1622. of expressions and applying the operator.
  1623. .NH 3
  1624. equiv.c
  1625. .PP
  1626. In this module the tuples() function is implemented.
  1627. It is given the number of registers needed and
  1628. a list of register lists and it constructs a list of tuples
  1629. where the \fIn\fP'th register comes from the \fIn\fP'th list.
  1630. Before the list is constructed however
  1631. the dynamic register classes are computed.
  1632. Two registers are in the same dynamic class if they are in the
  1633. same static class and their contents is the same.
  1634. .PP
  1635. After that the permute() recursive function is called to
  1636. generate the list of tuples.
  1637. After construction a generated tuple is added to the list
  1638. if it is not already pairwise in the same class
  1639. or if the register relations are not the same,
  1640. i.e. if the first and second register share a common
  1641. subregister in one tuple and not in the other they are considered different.
  1642. .NH 3
  1643. fillem.c
  1644. .PP
  1645. This is the routine that does the reading of EM instructions
  1646. and the handling of pseudos.
  1647. The mach.c module provided by the table writer is included
  1648. at the end of this module.
  1649. The routine fillemlines() is called by nextem() at toplevel
  1650. to make sure there are enough instruction to match.
  1651. It fills the EM instruction buffer up to 5 places from the end to
  1652. keep room for EM replacement instructions,
  1653. or up to a pseudo.
  1654. .PP
  1655. The dopseudo() function performs the function of the pseudo last
  1656. encountered.
  1657. If the pseudo is a
  1658. .B rom
  1659. the corresponding label is saved with the contents of the
  1660. .B rom
  1661. to be available to the code generator later.
  1662. The rest of the routines are small service routines for either
  1663. input or data output.
  1664. .NH 3
  1665. gencode.c
  1666. .PP
  1667. This module contains routines called by codegen() to generate the real
  1668. code to the codefile.
  1669. The function gencode() gets a string as argument and copies it to codefile
  1670. while processing certain embedded control characters implementing
  1671. the $2 and [1.reg] escapes.
  1672. The function genexpr() prints the expression given as argument.
  1673. It is used to implement the %(\ expr\ %) escape.
  1674. The prtoken() function interprets the tokenformat as given in
  1675. the tokens[] array.
  1676. .NH 3
  1677. glosym.c
  1678. .PP
  1679. This module maintains a list of global symbols that have a
  1680. .B rom
  1681. pseudo associated.
  1682. There are functions to enter a symbol and to find a symbol.
  1683. .NH 3
  1684. main.c
  1685. .PP
  1686. Main routine of the code generator.
  1687. Processes arguments and flags.
  1688. Flags available are:
  1689. .IP -d
  1690. Sets debug mode if the code generator was not compiled with
  1691. the NDEBUG macro defined.
  1692. Debug mode gives very long output on stderr indicating
  1693. all steps of the code generation process including nesting
  1694. of the codegen() function.
  1695. .IP -p\fIn\fP
  1696. Sets the lookahead depth to
  1697. .I n ,
  1698. the
  1699. .I p
  1700. stands for ply,
  1701. a well known word in chess playing programs.
  1702. .IP -w\fIn\fP
  1703. Sets the weight percentage for size in the cost function to
  1704. .I n
  1705. percent.
  1706. Uses Euclides algorithm to simplify rationals.
  1707. .NH 3
  1708. move.c
  1709. .PP
  1710. Function to implement the move() pseudo function in the tables,
  1711. register initialization and the setcc and test pseudo functions.
  1712. First tests are made to try to prevent the move from really happening.
  1713. The condition code register is treated special here.
  1714. After that, if there is an after that,
  1715. the move rule is found and the code executed.
  1716. .NH 3
  1717. nextem.c
  1718. .PP
  1719. The entry point of this module is nextem().
  1720. It hashes the next three EM instructions,
  1721. and uses the low order byte of the hash
  1722. as an index into the array pathash[],
  1723. to find a chain of patterns in the array
  1724. pattern[],
  1725. that are all tried for a match.
  1726. .PP
  1727. The function trypat() does most of the work
  1728. checking patterns.
  1729. When a pattern is found to match all instructions
  1730. the operands of the instruction are placed into the dollar[] array.
  1731. Then the boolean expression is tried.
  1732. If it matches the function can return,
  1733. leaving the operands still in the dollar[] array,
  1734. so later in the code rule they can still be used.
  1735. .NH 3
  1736. reg.c
  1737. .PP
  1738. Collection of routines to handle registers.
  1739. Reference count routines are here,
  1740. chrefcount() and getrefcount(),
  1741. plus routines to erase a single register or all of them,
  1742. erasereg() and cleanregs().
  1743. .PP
  1744. If NDEBUG hasn't been defined, here is also the routine that checks
  1745. if the reference count kept with the register information is in
  1746. agreement with the number of times it occurs on the fakestack.
  1747. .NH 3
  1748. salloc.c
  1749. .PP
  1750. Module for string allocation and garbage collection.
  1751. Contains entry points myalloc(),
  1752. a routine calling malloc() and checking whether room is left,
  1753. myfree(), just free(),
  1754. popstr() a function called from state.c to free all strings
  1755. made since the last saved status.
  1756. Furthermore there is salloc() which has the size of the string as parameter
  1757. and returns a pointer to the allocated space,
  1758. while keeping a copy of the pointer for garbage allocation purposes.
  1759. .PP
  1760. The function garbage_collect is called from codegen() at toplevel
  1761. every now and then,
  1762. and checks all places where strings may reside to mark strings
  1763. as being in use.
  1764. Strings not in use are returned to the pool of free space.
  1765. .NH 3
  1766. state.c
  1767. .PP
  1768. Set of routines called to save current status,
  1769. restore a previous saved state and to free the room
  1770. occupied by a saved state.
  1771. A list of structs is kept here to save the state.
  1772. If this is not done,
  1773. small allocates will take space
  1774. from the holes big enough for state saves,
  1775. and as a result every new state save will need a new struct.
  1776. The code generator runs out of room very rapidly under these conditions.
  1777. .NH 3
  1778. subr.c
  1779. .PP
  1780. Random set of leftover routines.
  1781. .NH 4
  1782. match
  1783. .PP
  1784. Computes whether a certain token matches a certain token expression.
  1785. Just computes a bitnumber according to the algorithm explained with
  1786. machsets[],
  1787. and tests the bit and the boolean expression if it is there.
  1788. .NH 4
  1789. instance,cinstance
  1790. .PP
  1791. These two functions compute a token from a description.
  1792. They differ very slight, cinstance() is used to compute
  1793. the result of a coercion in a certain context
  1794. and therefore has more arguments, which it uses instead of
  1795. the global information instance() works on.
  1796. .NH 4
  1797. eqtoken
  1798. .PP
  1799. eqtoken computes whether two tokens can be considered identical.
  1800. Used to check register contents during moves mainly.
  1801. .NH 4
  1802. distance
  1803. .PP
  1804. This is the heuristic function that computes a distance from
  1805. the current fakestack contents to the token pattern in the table.
  1806. It likes exact matches most, then matches where at least the sizes are correct
  1807. and if the sizes are not correct it likes too large sizes more than too
  1808. small, since splitting a token is easier than combining one.
  1809. .NH 4
  1810. split
  1811. .PP
  1812. This function tries to find a splitting coercion
  1813. and executes it immediately when found.
  1814. The fakestack is shuffled thoroughly when this happens,
  1815. so pieces below the token that must be split are saved first.
  1816. .NH 4
  1817. docoerc
  1818. .PP
  1819. This function executes a coercion that was found.
  1820. The same shuffling is done, so the top of the stack is again saved.
  1821. .NH 4
  1822. stackupto
  1823. .PP
  1824. This function gets a pointer into the fakestack and must stack
  1825. every token including the one pointed at up to the bottom of the fakestack.
  1826. The first stacking rule possible is used,
  1827. so rules using registers must come first.
  1828. .NH 4
  1829. findcoerc
  1830. .PP
  1831. Looks for a one to one coercion, if found it returns a pointer
  1832. to it and leaves a list of possible registers to use in the global
  1833. variable curreglist.
  1834. This is used by codegen().
  1835. .NH 3
  1836. var.c
  1837. .PP
  1838. Global variables used by more than one module.
  1839. External definitions are in extern.h.