compiler.ms 30 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157
  1. .HTML "Plan 9 C Compilers
  2. .TL
  3. Plan 9 C Compilers
  4. .AU
  5. Ken Thompson
  6. ken@plan9.bell-labs.com
  7. .AB
  8. .FS
  9. Originally appeared, in a different form, in
  10. .I
  11. Proceedings of the Summer 1990 UKUUG Conference,
  12. .R
  13. pp. 41-51,
  14. London, 1990.
  15. .FE
  16. This paper describes the overall structure and function of the Plan 9 C compilers.
  17. A more detailed implementation document
  18. for any one of the compilers
  19. is yet to be written.
  20. .AE
  21. .NH
  22. Introduction
  23. .LP
  24. There are many compilers in the series.
  25. Six of the compilers (MIPS 3000, SPARC, Intel 386, Power PC, DEC Alpha, and Motorola 68020)
  26. are considered active and are used to compile
  27. current versions of Plan 9.
  28. Several others (Motorola 68000, Intel 960, ARM 7500, AMD 29000) have had only limited use, such as
  29. to program peripherals or experimental devices.
  30. .NH
  31. Structure
  32. .LP
  33. The compiler is a single program that produces an
  34. object file.
  35. Combined in the compiler are the traditional
  36. roles of preprocessor, lexical analyzer, parser, code generator,
  37. local optimizer,
  38. and first half of the assembler.
  39. The object files are binary forms of assembly
  40. language,
  41. similar to what might be passed between
  42. the first and second passes of an assembler.
  43. .LP
  44. Object files and libraries
  45. are combined by a loader
  46. program to produce the executable binary.
  47. The loader combines the roles of second half
  48. of the assembler, global optimizer, and loader.
  49. The names of the compliers, loaders, and assemblers
  50. are as follows:
  51. .DS
  52. .ta 1.5i
  53. .de Ta
  54. \\$1 \f(CW\\$2\fP \f(CW\\$3\fP \f(CW\\$4\fP
  55. ..
  56. .Ta SPARC kc kl ka
  57. .Ta Power\ PC qc ql qa
  58. .Ta MIPS vc vl va
  59. .Ta Motorola\ 68000 1c 1l 1a
  60. .Ta Motorola\ 68020 2c 2l 2a
  61. .Ta ARM\ 7500 5c 5l 5a
  62. .Ta Intel\ 960 6c 6l 6a
  63. .Ta DEC\ Alpha 7c 7l 7a
  64. .Ta Intel\ 386 8c 8l 8a
  65. .Ta AMD\ 29000 9c 9l 9a
  66. .DE
  67. There is a further breakdown
  68. in the source of the compilers into
  69. object-independent and
  70. object-dependent
  71. parts.
  72. All of the object-independent parts
  73. are combined into source files in the
  74. directory
  75. .CW /sys/src/cmd/cc .
  76. The object-dependent parts are collected
  77. in a separate directory for each compiler,
  78. for example
  79. .CW /sys/src/cmd/vc .
  80. All of the code,
  81. both object-independent and
  82. object-dependent,
  83. is machine-independent
  84. and may be cross-compiled and executed on any
  85. of the architectures.
  86. .NH
  87. The Language
  88. .LP
  89. The compiler implements ANSI C with some
  90. restrictions and extensions
  91. [ANSI90].
  92. Most of the restrictions are due to
  93. personal preference, while
  94. most of the extensions were to help in
  95. the implementation of Plan 9.
  96. There are other departures from the standard,
  97. particularly in the libraries,
  98. that are beyond the scope of this
  99. paper.
  100. .NH 2
  101. Register, volatile, const
  102. .LP
  103. The keyword
  104. .CW register
  105. is recognized syntactically
  106. but is semantically ignored.
  107. Thus taking the address of a
  108. .CW register
  109. variable is not diagnosed.
  110. The keyword
  111. .CW volatile
  112. disables all optimizations, in particular registerization, of the corresponding variable.
  113. The keyword
  114. .CW const
  115. generates warnings (if warnings are enabled by the compiler's
  116. .CW -w
  117. option) of non-constant use of the variable,
  118. but does not affect the generated code.
  119. .NH 2
  120. The preprocessor
  121. .LP
  122. The C preprocessor is probably the
  123. biggest departure from the ANSI standard.
  124. .LP
  125. The preprocessor built into the Plan 9 compilers does not support
  126. .CW #if ,
  127. although it does handle
  128. .CW #ifdef
  129. and
  130. .CW #include .
  131. If it is necessary to be more standard,
  132. the source text can first be run through the separate ANSI C
  133. preprocessor,
  134. .CW cpp .
  135. .NH 2
  136. Unnamed substructures
  137. .LP
  138. The most important and most heavily used of the
  139. extensions is the declaration of an
  140. unnamed substructure or subunion.
  141. For example:
  142. .DS
  143. .CW
  144. .ta .1i .6i 1.1i 1.6i
  145. typedef
  146. struct lock
  147. {
  148. int locked;
  149. } Lock;
  150. typedef
  151. struct node
  152. {
  153. int type;
  154. union
  155. {
  156. double dval;
  157. float fval;
  158. long lval;
  159. };
  160. Lock;
  161. } Node;
  162. Lock* lock;
  163. Node* node;
  164. .DE
  165. The declaration of
  166. .CW Node
  167. has an unnamed substructure of type
  168. .CW Lock
  169. and an unnamed subunion.
  170. One use of this feature allows references to elements of the
  171. subunit to be accessed as if they were in
  172. the outer structure.
  173. Thus
  174. .CW node->dval
  175. and
  176. .CW node->locked
  177. are legitimate references.
  178. .LP
  179. When an outer structure is used
  180. in a context that is only legal for
  181. an unnamed substructure,
  182. the compiler promotes the reference to the
  183. unnamed substructure.
  184. This is true for references to structures and
  185. to references to pointers to structures.
  186. This happens in assignment statements and
  187. in argument passing where prototypes have been
  188. declared.
  189. Thus, continuing with the example,
  190. .DS
  191. .CW
  192. .ta .1i .6i 1.1i 1.6i
  193. lock = node;
  194. .DE
  195. would assign a pointer to the unnamed
  196. .CW Lock
  197. in
  198. the
  199. .CW Node
  200. to the variable
  201. .CW lock .
  202. Another example,
  203. .DS
  204. .CW
  205. .ta .1i .6i 1.1i 1.6i
  206. extern void lock(Lock*);
  207. func(...)
  208. {
  209. ...
  210. lock(node);
  211. ...
  212. }
  213. .DE
  214. will pass a pointer to the
  215. .CW Lock
  216. substructure.
  217. .LP
  218. Finally, in places where context is insufficient to identify the unnamed structure,
  219. the type name (it must be a
  220. .CW typedef )
  221. of the unnamed structure can be used as an identifier.
  222. In our example,
  223. .CW &node->Lock
  224. gives the address of the anonymous
  225. .CW Lock
  226. structure.
  227. .NH 2
  228. Structure displays
  229. .LP
  230. A structure cast followed by a list of expressions in braces is
  231. an expression with the type of the structure and elements assigned from
  232. the corresponding list.
  233. Structures are now almost first-class citizens of the language.
  234. It is common to see code like this:
  235. .DS
  236. .CW
  237. .ta .1i
  238. r = (Rectangle){point1, (Point){x,y+2}};
  239. .DE
  240. .NH 2
  241. Initialization indexes
  242. .LP
  243. In initializers of arrays,
  244. one may place a constant expression
  245. in square brackets before an initializer.
  246. This causes the next initializer to assign
  247. the indicated element.
  248. For example:
  249. .DS
  250. .CW
  251. .ta .1i .6i 1.6i
  252. enum errors
  253. {
  254. Etoobig,
  255. Ealarm,
  256. Egreg
  257. };
  258. char* errstrings[] =
  259. {
  260. [Ealarm] "Alarm call",
  261. [Egreg] "Panic: out of mbufs",
  262. [Etoobig] "Arg list too long",
  263. };
  264. .DE
  265. In the same way,
  266. individual structures members may
  267. be initialized in any order by preceding the initialization with
  268. .CW .tagname .
  269. Both forms allow an optional
  270. .CW = ,
  271. to be compatible with a proposed
  272. extension to ANSI C.
  273. .NH 2
  274. External register
  275. .LP
  276. The declaration
  277. .CW extern
  278. .CW register
  279. will dedicate a register to
  280. a variable on a global basis.
  281. It can be used only under special circumstances.
  282. External register variables must be identically
  283. declared in all modules and
  284. libraries.
  285. The feature is not intended for efficiency,
  286. although it can produce efficient code;
  287. rather it represents a unique storage class that
  288. would be hard to get any other way.
  289. On a shared-memory multi-processor,
  290. an external register is
  291. one-per-processor and neither one-per-procedure (automatic)
  292. or one-per-system (external).
  293. It is used for two variables in the Plan 9 kernel,
  294. .CW u
  295. and
  296. .CW m .
  297. .CW U
  298. is a pointer to the structure representing the currently running process
  299. and
  300. .CW m
  301. is a pointer to the per-machine data structure.
  302. .NH 2
  303. Long long
  304. .LP
  305. The compilers accept
  306. .CW long
  307. .CW long
  308. as a basic type meaning 64-bit integer.
  309. On all of the machines
  310. this type is synthesized from 32-bit instructions.
  311. .NH 2
  312. Pragma
  313. .LP
  314. The compilers accept
  315. .CW #pragma
  316. .CW lib
  317. .I libname
  318. and pass the
  319. library name string uninterpreted
  320. to the loader.
  321. The loader uses the library name to
  322. find libraries to load.
  323. If the name contains
  324. .CW %O ,
  325. it is replaced with
  326. the single character object type of the compiler
  327. (e.g.,
  328. .CW v
  329. for the MIPS).
  330. If the name contains
  331. .CW %M ,
  332. it is replaced with
  333. the architecture type for the compiler
  334. (e.g.,
  335. .CW mips
  336. for the MIPS).
  337. If the name starts with
  338. .CW /
  339. it is an absolute pathname;
  340. if it starts with
  341. .CW .
  342. then it is searched for in the loader's current directory.
  343. Otherwise, the name is searched from
  344. .CW /%M/lib .
  345. Such
  346. .CW #pragma
  347. statements in header files guarantee that the correct
  348. libraries are always linked with a program without the
  349. need to specify them explicitly at link time.
  350. .LP
  351. They also accept
  352. .CW #pragma
  353. .CW hjdicks
  354. .CW on
  355. (or
  356. .CW yes
  357. or
  358. .CW 1 )
  359. to cause subsequently declared data, until
  360. .CW #pragma
  361. .CW hjdicks
  362. .CW off
  363. (or
  364. .CW no
  365. or
  366. .CW 0 ),
  367. to be laid out in memory tightly packed in successive bytes, disregarding
  368. the usual alignment rules.
  369. Accessing such data can cause faults.
  370. .LP
  371. Similarly,
  372. .CW #pragma
  373. .CW profile
  374. .CW off
  375. (or
  376. .CW no
  377. or
  378. .CW 0 )
  379. causes subsequently declared functions, until
  380. .CW #pragma
  381. .CW profile
  382. .CW on
  383. (or
  384. .CW yes
  385. or
  386. .CW 1 ),
  387. to be marked as unprofiled.
  388. Such functions will not be profiled when
  389. profiling is enabled for the rest of the program.
  390. .LP
  391. Two
  392. .CW #pragma
  393. statements allow type-checking of
  394. .CW print -like
  395. functions.
  396. The first, of the form
  397. .P1
  398. #pragma varargck argpos error 2
  399. .P2
  400. tells the compiler that the second argument to
  401. .CW error
  402. is a
  403. .CW print
  404. format string (see the manual page
  405. .I print (2))
  406. that specifies how to format
  407. .CW error 's
  408. subsequent arguments.
  409. The second, of the form
  410. .P1
  411. #pragma varargck type "s" char*
  412. .P2
  413. says that the
  414. .CW print
  415. format verb
  416. .CW s
  417. processes an argument of
  418. type
  419. .CW char* .
  420. If the compiler's
  421. .CW -F
  422. option is enabled, the compiler will use this information
  423. to report type violations in the arguments to
  424. .CW print ,
  425. .CW error ,
  426. and similar routines.
  427. .NH
  428. Object module conventions
  429. .LP
  430. The overall conventions of the runtime environment
  431. are important
  432. to runtime efficiency.
  433. In this section,
  434. several of these conventions are discussed.
  435. .NH 2
  436. Register saving
  437. .LP
  438. In the Plan 9 compilers,
  439. the caller of a procedure saves the registers.
  440. With caller-saves,
  441. the leaf procedures can use all the
  442. registers and never save them.
  443. If you spend a lot of time at the leaves,
  444. this seems preferable.
  445. With callee-saves,
  446. the saving of the registers is done
  447. in the single point of entry and return.
  448. If you are interested in space,
  449. this seems preferable.
  450. In both,
  451. there is a degree of uncertainty
  452. about what registers need to be saved.
  453. Callee-saved registers make it difficult to
  454. find variables in registers in debuggers.
  455. Callee-saved registers also complicate
  456. the implementation of
  457. .CW longjmp .
  458. The convincing argument is
  459. that with caller-saves,
  460. the decision to registerize a variable
  461. can include the cost of saving the register
  462. across calls.
  463. For a further discussion of caller- vs. callee-saves,
  464. see the paper by Davidson and Whalley [Dav91].
  465. .LP
  466. In the Plan 9 operating system,
  467. calls to the kernel look like normal procedure
  468. calls, which means
  469. the caller
  470. has saved the registers and the system
  471. entry does not have to.
  472. This makes system calls considerably faster.
  473. Since this is a potential security hole,
  474. and can lead to non-determinism,
  475. the system may eventually save the registers
  476. on entry,
  477. or more likely clear the registers on return.
  478. .NH 2
  479. Calling convention
  480. .LP
  481. Older C compilers maintain a frame pointer, which is at a known constant
  482. offset from the stack pointer within each function.
  483. For machines where the stack grows towards zero,
  484. the argument pointer is at a known constant offset
  485. from the frame pointer.
  486. Since the stack grows down in Plan 9,
  487. the Plan 9 compilers
  488. keep neither an
  489. explicit frame pointer nor
  490. an explicit argument pointer;
  491. instead they generate addresses relative to the stack pointer.
  492. .LP
  493. On some architectures, the first argument to a subroutine is passed in a register.
  494. .NH 2
  495. Functions returning structures
  496. .LP
  497. Structures longer than one word are awkward to implement
  498. since they do not fit in registers and must
  499. be passed around in memory.
  500. Functions that return structures
  501. are particularly clumsy.
  502. The Plan 9 compilers pass the return address of
  503. a structure as the first argument of a
  504. function that has a structure return value.
  505. Thus
  506. .DS
  507. .CW
  508. .ta .1i .6i 1.1i 1.6i
  509. x = f(...)
  510. .DE
  511. is rewritten as
  512. .DS
  513. .CW
  514. .ta .1i .6i 1.1i 1.6i
  515. f(&x, ...)\f1.
  516. .DE
  517. This saves a copy and makes the compilation
  518. much less clumsy.
  519. A disadvantage is that if you call this
  520. function without an assignment,
  521. a dummy location must be invented.
  522. .LP
  523. There is also a danger of calling a function
  524. that returns a structure without declaring
  525. it as such.
  526. With ANSI C function prototypes,
  527. this error need never occur.
  528. .NH
  529. Implementation
  530. .LP
  531. The compiler is divided internally into
  532. four machine-independent passes,
  533. four machine-dependent passes,
  534. and an output pass.
  535. The next nine sections describe each pass in order.
  536. .NH 2
  537. Parsing
  538. .LP
  539. The first pass is a YACC-based parser
  540. [Joh79].
  541. Declarations are interpreted immediately,
  542. building a block structured symbol table.
  543. Executable statements are put into a parse tree
  544. and collected,
  545. without interpretation.
  546. At the end of each procedure,
  547. the parse tree for the function is
  548. examined by the other passes of the compiler.
  549. .LP
  550. The input stream of the parser is
  551. a pushdown list of input activations.
  552. The preprocessor
  553. expansions of
  554. macros
  555. and
  556. .CW #include
  557. are implemented as pushdowns.
  558. Thus there is no separate
  559. pass for preprocessing.
  560. .NH 2
  561. Typing
  562. .LP
  563. The next pass distributes typing information
  564. to every node of the tree.
  565. Implicit operations on the tree are added,
  566. such as type promotions and taking the
  567. address of arrays and functions.
  568. .NH 2
  569. Machine-independent optimization
  570. .LP
  571. The next pass performs optimizations
  572. and transformations of the tree, such as converting
  573. .CW &*x
  574. and
  575. .CW *&x
  576. into
  577. .CW x .
  578. Constant expressions are converted to constants in this pass.
  579. .NH 2
  580. Arithmetic rewrites
  581. .LP
  582. This is another machine-independent optimization.
  583. Subtrees of add, subtract, and multiply of integers are
  584. rewritten for easier compilation.
  585. The major transformation is factoring:
  586. .CW 4+8*a+16*b+5
  587. is transformed into
  588. .CW 9+8*(a+2*b) .
  589. Such expressions arise from address
  590. manipulation and array indexing.
  591. .NH 2
  592. Addressability
  593. .LP
  594. This is the first of the machine-dependent passes.
  595. The addressability of a processor is defined as the set of
  596. expressions that is legal in the address field
  597. of a machine language instruction.
  598. The addressability of different processors varies widely.
  599. At one end of the spectrum are the 68020 and VAX,
  600. which allow a complex mix of incrementing,
  601. decrementing,
  602. indexing, and relative addressing.
  603. At the other end is the MIPS,
  604. which allows only registers and constant offsets from the
  605. contents of a register.
  606. The addressability can be different for different instructions
  607. within the same processor.
  608. .LP
  609. It is important to the code generator to know when a
  610. subtree represents an address of a particular type.
  611. This is done with a bottom-up walk of the tree.
  612. In this pass, the leaves are labeled with small integers.
  613. When an internal node is encountered,
  614. it is labeled by consulting a table indexed by the
  615. labels on the left and right subtrees.
  616. For example,
  617. on the 68020 processor,
  618. it is possible to address an
  619. offset from a named location.
  620. In C, this is represented by the expression
  621. .CW *(&name+constant) .
  622. This is marked addressable by the following table.
  623. In the table,
  624. a node represented by the left column is marked
  625. with a small integer from the right column.
  626. Marks of the form
  627. .CW A\s-2\di\u\s0
  628. are addressable while
  629. marks of the form
  630. .CW N\s-2\di\u\s0
  631. are not addressable.
  632. .DS
  633. .B
  634. .ta .1i 1.1i
  635. Node Marked
  636. .CW
  637. name A\s-2\d1\u\s0
  638. const A\s-2\d2\u\s0
  639. &A\s-2\d1\u\s0 A\s-2\d3\u\s0
  640. A\s-2\d3\u\s0+A\s-2\d1\u\s0 N\s-2\d1\u\s0 \fR(note that this is not addressable)\fP
  641. *N\s-2\d1\u\s0 A\s-2\d4\u\s0
  642. .DE
  643. Here there is a distinction between
  644. a node marked
  645. .CW A\s-2\d1\u\s0
  646. and a node marked
  647. .CW A\s-2\d4\u\s0
  648. because the address operator of an
  649. .CW A\s-2\d4\u\s0
  650. node is not addressable.
  651. So to extend the table:
  652. .DS
  653. .B
  654. .ta .1i 1.1i
  655. Node Marked
  656. .CW
  657. &A\s-2\d4\u\s0 N\s-2\d2\u\s0
  658. N\s-2\d2\u\s0+N\s-2\d1\u\s0 N\s-2\d1\u\s0
  659. .DE
  660. The full addressability of the 68020 is expressed
  661. in 18 rules like this,
  662. while the addressability of the MIPS is expressed
  663. in 11 rules.
  664. When one ports the compiler,
  665. this table is usually initialized
  666. so that leaves are labeled as addressable and nothing else.
  667. The code produced is poor,
  668. but porting is easy.
  669. The table can be extended later.
  670. .LP
  671. This pass also rewrites some complex operators
  672. into procedure calls.
  673. Examples include 64-bit multiply and divide.
  674. .LP
  675. In the same bottom-up pass of the tree,
  676. the nodes are labeled with a Sethi-Ullman complexity
  677. [Set70].
  678. This number is roughly the number of registers required
  679. to compile the tree on an ideal machine.
  680. An addressable node is marked 0.
  681. A function call is marked infinite.
  682. A unary operator is marked as the
  683. maximum of 1 and the mark of its subtree.
  684. A binary operator with equal marks on its subtrees is
  685. marked with a subtree mark plus 1.
  686. A binary operator with unequal marks on its subtrees is
  687. marked with the maximum mark of its subtrees.
  688. The actual values of the marks are not too important,
  689. but the relative values are.
  690. The goal is to compile the harder
  691. (larger mark)
  692. subtree first.
  693. .NH 2
  694. Code generation
  695. .LP
  696. Code is generated by recursive
  697. descent.
  698. The Sethi-Ullman complexity completely guides the
  699. order.
  700. The addressability defines the leaves.
  701. The only difficult part is compiling a tree
  702. that has two infinite (function call)
  703. subtrees.
  704. In this case,
  705. one subtree is compiled into the return register
  706. (usually the most convenient place for a function call)
  707. and then stored on the stack.
  708. The other subtree is compiled into the return register
  709. and then the operation is compiled with
  710. operands from the stack and the return register.
  711. .LP
  712. There is a separate boolean code generator that compiles
  713. conditional expressions.
  714. This is fundamentally different from compiling an arithmetic expression.
  715. The result of the boolean code generator is the
  716. position of the program counter and not an expression.
  717. The boolean code generator makes extensive use of De Morgan's rule.
  718. The boolean code generator is an expanded version of that described
  719. in chapter 8 of Aho, Sethi, and Ullman
  720. [Aho87].
  721. .LP
  722. There is a considerable amount of talk in the literature
  723. about automating this part of a compiler with a machine
  724. description.
  725. Since this code generator is so small
  726. (less than 500 lines of C)
  727. and easy,
  728. it hardly seems worth the effort.
  729. .NH 2
  730. Registerization
  731. .LP
  732. Up to now,
  733. the compiler has operated on syntax trees
  734. that are roughly equivalent to the original source language.
  735. The previous pass has produced machine language in an internal
  736. format.
  737. The next two passes operate on the internal machine language
  738. structures.
  739. The purpose of the next pass is to reintroduce
  740. registers for heavily used variables.
  741. .LP
  742. All of the variables that can be
  743. potentially registerized within a procedure are
  744. placed in a table.
  745. (Suitable variables are any automatic or external
  746. scalars that do not have their addresses extracted.
  747. Some constants that are hard to reference are also
  748. considered for registerization.)
  749. Four separate data flow equations are evaluated
  750. over the procedure on all of these variables.
  751. Two of the equations are the normal set-behind
  752. and used-ahead
  753. bits that define the life of a variable.
  754. The two new bits tell if a variable life
  755. crosses a function call ahead or behind.
  756. By examining a variable over its lifetime,
  757. it is possible to get a cost
  758. for registerizing.
  759. Loops are detected and the costs are multiplied
  760. by three for every level of loop nesting.
  761. Costs are sorted and the variables
  762. are replaced by available registers on a greedy basis.
  763. .LP
  764. The 68020 has two different
  765. types of registers.
  766. For the 68020,
  767. two different costs are calculated for
  768. each variable life and the register type that
  769. affords the better cost is used.
  770. Ties are broken by counting the number of available
  771. registers of each type.
  772. .LP
  773. Note that externals are registerized together with automatics.
  774. This is done by evaluating the semantics of a ``call'' instruction
  775. differently for externals and automatics.
  776. Since a call goes outside the local procedure,
  777. it is assumed that a call references all externals.
  778. Similarly,
  779. externals are assumed to be set before an ``entry'' instruction
  780. and assumed to be referenced after a ``return'' instruction.
  781. This makes sure that externals are in memory across calls.
  782. .LP
  783. The overall results are satisfactory.
  784. It would be nice to be able to do this processing in
  785. a machine-independent way,
  786. but it is impossible to get all of the costs and
  787. side effects of different choices by examining the parse tree.
  788. .LP
  789. Most of the code in the registerization pass is machine-independent.
  790. The major machine-dependency is in
  791. examining a machine instruction to ask if it sets or references
  792. a variable.
  793. .NH 2
  794. Machine code optimization
  795. .LP
  796. The next pass walks the machine code
  797. for opportunistic optimizations.
  798. For the most part,
  799. this is highly specific to a particular
  800. processor.
  801. One optimization that is performed
  802. on all of the processors is the
  803. removal of unnecessary ``move''
  804. instructions.
  805. Ironically,
  806. most of these instructions were inserted by
  807. the previous pass.
  808. There are two patterns that are repetitively
  809. matched and replaced until no more matches are
  810. found.
  811. The first tries to remove ``move'' instructions
  812. by relabeling variables.
  813. .LP
  814. When a ``move'' instruction is encountered,
  815. if the destination variable is set before the
  816. source variable is referenced,
  817. then all of the references to the destination
  818. variable can be renamed to the source and the ``move''
  819. can be deleted.
  820. This transformation uses the reverse data flow
  821. set up in the previous pass.
  822. .LP
  823. An example of this pattern is depicted in the following
  824. table.
  825. The pattern is in the left column and the
  826. replacement action is in the right column.
  827. .DS
  828. .CW
  829. .ta .1i .6i 1.6i 2.1i 2.6i
  830. MOVE a->b \fR(remove)\fP
  831. .R
  832. (sequence with no mention of \f(CWa\fP)
  833. .CW
  834. USE b USE a
  835. .R
  836. (sequence with no mention of \f(CWa\fP)
  837. .CW
  838. SET b SET b
  839. .DE
  840. .LP
  841. Experiments have shown that it is marginally
  842. worthwhile to rename uses of the destination variable
  843. with uses of the source variable up to
  844. the first use of the source variable.
  845. .LP
  846. The second transform will do relabeling
  847. without deleting instructions.
  848. When a ``move'' instruction is encountered,
  849. if the source variable has been set prior
  850. to the use of the destination variable
  851. then all of the references to the source
  852. variable are replaced by the destination and
  853. the ``move'' is inverted.
  854. Typically,
  855. this transformation will alter two ``move''
  856. instructions and allow the first transformation
  857. another chance to remove code.
  858. This transformation uses the forward data flow
  859. set up in the previous pass.
  860. .LP
  861. Again,
  862. the following is a depiction of the transformation where
  863. the pattern is in the left column and the
  864. rewrite is in the right column.
  865. .DS
  866. .CW
  867. .ta .1i .6i 1.6i 2.1i 2.6i
  868. SET a SET b
  869. .R
  870. (sequence with no use of \f(CWb\fP)
  871. .CW
  872. USE a USE b
  873. .R
  874. (sequence with no use of \f(CWb\fP)
  875. .CW
  876. MOVE a->b MOVE b->a
  877. .DE
  878. Iterating these transformations
  879. will usually get rid of all redundant ``move'' instructions.
  880. .LP
  881. A problem with this organization is that the costs
  882. of registerization calculated in the previous pass
  883. must depend on how well this pass can detect and remove
  884. redundant instructions.
  885. Often,
  886. a fine candidate for registerization is rejected
  887. because of the cost of instructions that are later
  888. removed.
  889. .NH 2
  890. Writing the object file
  891. .LP
  892. The last pass walks the internal assembly language
  893. and writes the object file.
  894. The object file is reduced in size by about a factor
  895. of three with simple compression
  896. techniques.
  897. The most important aspect of the object file
  898. format is that it is independent of the compiling machine.
  899. All integer and floating numbers in the object
  900. code are converted to known formats and byte
  901. orders.
  902. .NH
  903. The loader
  904. .LP
  905. The loader is a multiple pass program that
  906. reads object files and libraries and produces
  907. an executable binary.
  908. The loader also does some minimal
  909. optimizations and code rewriting.
  910. Many of the operations performed by the
  911. loader are machine-dependent.
  912. .LP
  913. The first pass of the loader reads the
  914. object modules into an internal data
  915. structure that looks like binary assembly language.
  916. As the instructions are read,
  917. code is reordered to remove
  918. unconditional branch instructions.
  919. Conditional branch instructions are inverted
  920. to prevent the insertion of unconditional branches.
  921. The loader will also make a copy of a few instructions
  922. to remove an unconditional branch.
  923. .LP
  924. The next pass allocates addresses for
  925. all external data.
  926. Typical of processors is the MIPS,
  927. which can reference ±32K bytes from a
  928. register.
  929. The loader allocates the register
  930. .CW R30
  931. as the static pointer.
  932. The value placed in
  933. .CW R30
  934. is the base of the data segment plus 32K.
  935. It is then cheap to reference all data in the
  936. first 64K of the data segment.
  937. External variables are allocated to
  938. the data segment
  939. with the smallest variables allocated first.
  940. If all of the data cannot fit into the first
  941. 64K of the data segment,
  942. then usually only a few large arrays
  943. need more expensive addressing modes.
  944. .LP
  945. For the MIPS processor,
  946. the loader makes a pass over the internal
  947. structures,
  948. exchanging instructions to try
  949. to fill ``delay slots'' with useful work.
  950. If a useful instruction cannot be found
  951. to fill a delay slot,
  952. the loader will insert
  953. ``noop''
  954. instructions.
  955. This pass is very expensive and does not
  956. do a good job.
  957. About 40% of all instructions are in
  958. delay slots.
  959. About 65% of these are useful instructions and
  960. 35% are ``noops.''
  961. The vendor-supplied assembler does this job
  962. more effectively,
  963. filling about 80%
  964. of the delay slots with useful instructions.
  965. .LP
  966. On the 68020 processor,
  967. branch instructions come in a variety of
  968. sizes depending on the relative distance
  969. of the branch.
  970. Thus the size of branch instructions
  971. can be mutually dependent.
  972. The loader uses a multiple pass algorithm
  973. to resolve the branch lengths
  974. [Szy78].
  975. Initially, all branches are assumed minimal length.
  976. On each subsequent pass,
  977. the branches are reassessed
  978. and expanded if necessary.
  979. When no more expansions occur,
  980. the locations of the instructions in
  981. the text segment are known.
  982. .LP
  983. On the MIPS processor,
  984. all instructions are one size.
  985. A single pass over the instructions will
  986. determine the locations of all addresses
  987. in the text segment.
  988. .LP
  989. The last pass of the loader produces the
  990. executable binary.
  991. A symbol table and other tables are
  992. produced to help the debugger to
  993. interpret the binary symbolically.
  994. .LP
  995. The loader places absolute source line numbers in the symbol table.
  996. The name and absolute line number of all
  997. .CW #include
  998. files is also placed in the
  999. symbol table so that the debuggers can
  1000. associate object code to source files.
  1001. .NH
  1002. Performance
  1003. .LP
  1004. The following is a table of the source size of the MIPS
  1005. compiler.
  1006. .DS
  1007. .ta .1i .6i
  1008. lines module
  1009. \0509 machine-independent headers
  1010. 1070 machine-independent YACC source
  1011. 6090 machine-independent C source
  1012. \0545 machine-dependent headers
  1013. 6532 machine-dependent C source
  1014. \0298 loader headers
  1015. 5215 loader C source
  1016. .DE
  1017. .LP
  1018. The following table shows timing
  1019. of a test program
  1020. that plays checkers, running on a MIPS R4000.
  1021. The test program is 26 files totaling 12600 lines of C.
  1022. The execution time does not significantly
  1023. depend on library implementation.
  1024. Since no other compiler runs on Plan 9,
  1025. the Plan 9 tests were done with the Plan 9 operating system;
  1026. the other tests were done on the vendor's operating system.
  1027. The hardware was identical in both cases.
  1028. The optimizer in the vendor's compiler
  1029. is reputed to be extremely good.
  1030. .DS
  1031. .ta .1i .9i
  1032. \0\04.49s Plan 9 \f(CWvc\fP \f(CW-N\fP compile time (opposite of \f(CW-O\fP)
  1033. \0\01.72s Plan 9 \f(CWvc\fP \f(CW-N\fP load time
  1034. 148.69s Plan 9 \f(CWvc\fP \f(CW-N\fP run time
  1035. \015.07s Plan 9 \f(CWvc\fP compile time (\f(CW-O\fP implicit)
  1036. \0\01.66s Plan 9 \f(CWvc\fP load time
  1037. \089.96s Plan 9 \f(CWvc\fP run time
  1038. \014.83s vendor \f(CWcc\fP compile time
  1039. \0\00.38s vendor \f(CWcc\fP load time
  1040. 104.75s vendor \f(CWcc\fP run time
  1041. \043.59s vendor \f(CWcc\fP \f(CW-O\fP compile time
  1042. \0\00.38s vendor \f(CWcc\fP \f(CW-O\fP load time
  1043. \076.19s vendor \f(CWcc\fP \f(CW-O\fP run time
  1044. \0\08.19s vendor \f(CWcc\fP \f(CW-O3\fP compile time
  1045. \035.97s vendor \f(CWcc\fP \f(CW-O3\fP load time
  1046. \071.16s vendor \f(CWcc\fP \f(CW-O3\fP run time
  1047. .DE
  1048. .LP
  1049. To compare the Intel compiler,
  1050. a program that is about 40% bit manipulation and
  1051. about 60% single precision floating point was
  1052. run on the same 33 MHz 486, once under Windows
  1053. compiled with the Watcom compiler, version 10.0,
  1054. in 16-bit mode and once under
  1055. Plan 9 in 32-bit mode.
  1056. The Plan 9 execution time was 27 sec while the Windows
  1057. execution time was 31 sec.
  1058. .NH
  1059. Conclusions
  1060. .LP
  1061. The new compilers compile
  1062. quickly,
  1063. load slowly,
  1064. and produce
  1065. medium quality
  1066. object code.
  1067. The compilers are relatively
  1068. portable,
  1069. requiring but a couple of weeks' work to
  1070. produce a compiler for a different computer.
  1071. For Plan 9,
  1072. where we needed several compilers
  1073. with specialized features and
  1074. our own object formats,
  1075. this project was indispensable.
  1076. It is also necessary for us to
  1077. be able to freely distribute our compilers
  1078. with the Plan 9 distribution.
  1079. .LP
  1080. Two problems have come up in retrospect.
  1081. The first has to do with the
  1082. division of labor between compiler and loader.
  1083. Plan 9 runs on multi-processors and as such
  1084. compilations are often done in parallel.
  1085. Unfortunately,
  1086. all compilations must be complete before loading
  1087. can begin.
  1088. The load is then single-threaded.
  1089. With this model,
  1090. any shift of work from compile to load
  1091. results in a significant increase in real time.
  1092. The same is true of libraries that are compiled
  1093. infrequently and loaded often.
  1094. In the future,
  1095. we may try to put some of the loader work
  1096. back into the compiler.
  1097. .LP
  1098. The second problem comes from
  1099. the various optimizations performed over several
  1100. passes.
  1101. Often optimizations in different passes depend
  1102. on each other.
  1103. Iterating the passes could compromise efficiency,
  1104. or even loop.
  1105. We see no real solution to this problem.
  1106. .NH
  1107. References
  1108. .LP
  1109. [Aho87] A. V. Aho, R. Sethi, and J. D. Ullman,
  1110. .I
  1111. Compilers \- Principles, Techniques, and Tools,
  1112. .R
  1113. Addison Wesley,
  1114. Reading, MA,
  1115. 1987.
  1116. .LP
  1117. [ANSI90] \f2American National Standard for Information Systems \-
  1118. Programming Language C\f1, American National Standards Institute, Inc.,
  1119. New York, 1990.
  1120. .LP
  1121. [Dav91] J. W. Davidson and D. B. Whalley,
  1122. ``Methods for Saving and Restoring Register Values across Function Calls'',
  1123. .I
  1124. Software\-Practice and Experience,
  1125. .R
  1126. Vol 21(2), pp. 149-165, February 1991.
  1127. .LP
  1128. [Joh79] S. C. Johnson,
  1129. ``YACC \- Yet Another Compiler Compiler'',
  1130. .I
  1131. UNIX Programmer's Manual, Seventh Ed., Vol. 2A,
  1132. .R
  1133. AT&T Bell Laboratories,
  1134. Murray Hill, NJ,
  1135. 1979.
  1136. .LP
  1137. [Set70] R. Sethi and J. D. Ullman,
  1138. ``The Generation of Optimal Code for Arithmetic Expressions'',
  1139. .I
  1140. Journal of the ACM,
  1141. .R
  1142. Vol 17(4), pp. 715-728, 1970.
  1143. .LP
  1144. [Szy78] T. G. Szymanski,
  1145. ``Assembling Code for Machines with Span-dependent Instructions'',
  1146. .I
  1147. Communications of the ACM,
  1148. .R
  1149. Vol 21(4), pp. 300-308, 1978.