4 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468
  1. .In
  2. .hw data-structures
  3. .nr H1 3
  4. .NH
  5. SOLUTIONS
  6. .NH 2
  7. Maintaining SPARC speed
  8. .PP
  9. In chapter 3 we wrote:
  10. .sp 0.3
  11. .nf
  12. >If we want to generate efficient code, we should at least try to reduce the number of
  13. >memory references and use registers wherever we can.
  14. .fi
  15. .sp 0.3
  16. In this chapter we will device a strategy to swiftly generate acceptable
  17. code by using push-pop optimization.
  18. Note that this is not the push-pop
  19. optimization already available in the EM-kit, since that is only present
  20. in the assembler-to-binary part which we do not use
  21. .[ [
  22. The Code Expander Generator
  23. .]].
  24. Our push-pop optimization
  25. works more like the fake-stack described in
  26. .[ [
  27. The table driven code generator
  28. .]].
  29. .NH 3
  30. Ad-hoc optimization
  31. .PP
  32. Before getting involved in any optimization let's have a look at some
  33. code generated with a straightforward EM to SPARC conversion of the
  34. C statement: \*(Sif(a[i]);\*(So Note that \*(Si%SP\*(So is an alias
  35. for a general purpose
  36. register and acts as the EM stack pointer. It has nothing to do with
  37. \*(Si%sp\*(So \(em the SPARC stack pointer.
  38. Analogous \*(Si%LB\*(So is EMs local base pointer.
  39. .br
  40. .IP
  41. .HS
  42. .TS
  43. ;
  44. l s l s l
  45. l1f6 lf6 l2f6 lf6 l.
  46. EM code SPARC code Comment
  47. lae _a set _a, %g1 ! load address of external _a
  48. dec 4, %SP
  49. st %g1, [%SP]
  50. lol -4 set -4, %g1 ! load local -4 (i)
  51. ld [%g1+%LB], %g2
  52. dec 4, %SP
  53. st %g2, [%SP]
  54. loc 2 set 2, %g1 ! load constant 2
  55. dec 4, %SP
  56. st %g1, [%SP]
  57. sli 4 ld [%SP], %g1 ! pop shift count
  58. ld [%SP+4], %g2 ! pop shiftee
  59. sll %g2, %g1, %g3
  60. inc 4, %SP
  61. st %g3, [%SP] ! push 4 * i
  62. ads 4 ld [%SP], %g1 ! add pointer and offset
  63. ld [%SP+4], %g2
  64. add %g1, %g2, %g3
  65. inc 4, %SP
  66. st %g3, [%SP] ! push address of _a + (4 * i)
  67. loi 4 ld [%SP], %g1 ! load indirect 4 bytes
  68. ld [%g1], %g2
  69. st %g2, [%SP] ! push a[i]
  70. cal _f
  71. ...
  72. .TE
  73. .HS
  74. .LP
  75. Although the code is easy understand, it clearly is far from optimal.
  76. The above code uses approximately 60 clock-cycles\(dg
  77. .FS
  78. \(dg In general each instruction only takes one cycle,
  79. except for \*(Sild\*(So and
  80. \*(Sist\*(So which may both require additional clock cycles. The exact amount
  81. of extra cycles needed depends on the SPARC implementation and memory access
  82. time. Furthermore, the
  83. \*(Siset\*(So pseudo-instruction is a bit tricky. It takes one cycle when
  84. its argument lies between -4096 and 4095, and two cycles otherwise.
  85. .FE
  86. to push an array-element on the stack,
  87. something which a 68020 can do in a single instruction. The SPARC
  88. processor may be fast, but not fast enough to justify the above code.
  89. .PP
  90. The same statement can be translated much more efficiently:
  91. .DS
  92. .TS
  93. ;
  94. l2f6 lf6 l.
  95. sll %i0, 2, %g2 ! multiply index by 4
  96. set _a, g3
  97. ld [%g2+%g3], %g1 ! get contents of a[i]
  98. dec 4, SP
  99. st %g2, [SP] ! push a[i] onto the stack
  100. .TE
  101. .DE
  102. which, instead of 60, uses only 5 clock cycles to retrieve the element
  103. from memory and 5 additional cycles when the result has to be pushed
  104. on the stack. Note that when the result is not a parameter it does not
  105. have to be pushed on the stack. By making efficient use of the SPARC
  106. registers we can fetch \*(Sia[i]\*(So in only 5 cycles!
  107. .NH 3
  108. Analyzing optimization
  109. .PP
  110. Instead of ad-hoc optimization we will need something more solid.
  111. When one tries to optimize the above code in an ad-hoc manner one will
  112. probably notice the large overhead due to stack access. Almost every EM
  113. instruction requires at least three SPARC instructions: one to carry out
  114. the EM instruction and two to pop and push the result from and onto the
  115. stack. This happens for every instruction, even though the data being pushed
  116. will probably be needed by the next instruction. To optimize this extensive
  117. pushing and popping of data we will use the appropriately named push-pop
  118. optimization.
  119. .PP
  120. The idea behind push-pop optimization is to delay the push operation until
  121. it is almost certain that the data actually has to be pushed.
  122. As is often the case, the data does not have to be pushed,
  123. but will be used as input to another EM instruction.
  124. If we can decide at compile time that this will indeed be
  125. the case we can save the time of first pushing the data and then popping it
  126. back again by temporarily storing the data (possibly only during compilation!)
  127. and using it no sooner than it is actually needed.
  128. .PP
  129. The \*(Sisli 4\*(So instruction, for instance, expects two inputs on top of the
  130. stack: on top a counter and right below that the shiftee (the number
  131. to be shifted). As a result \*(Sisli\*(So
  132. pushes 'shiftee << counter' back to the stack. Now consider the following
  133. sequence, which could be the result of the expression \*(Si4 * i\*(So
  134. .DS
  135. .TS
  136. ;
  137. l1f6 lf6 l.
  138. lol -4
  139. loc 2
  140. sli 4
  141. .TE
  142. .DE
  143. In the non-optimized situation the \*(Silol\*(So would push
  144. a local variable (whose offset is -4) on the stack.
  145. Then the \*(Siloc\*(So pushes a 2 on the stack and finally \*(Sisli\*(So
  146. retrieves both these numbers to replace then with the result.
  147. On most machines it is not necessary to
  148. push the 2 on the stack, since it can be used in the shift instruction
  149. as an immediately operand. On a SPARC, for instance, one can write
  150. .DS
  151. .TS
  152. ;
  153. l2f6 lf6 l.
  154. ld [%LB-4], %g1 ! load local variable into register g1
  155. sll %g1, 2, %g2 ! perform the shift-left-by-2
  156. .TE
  157. .DE
  158. where the output of the \*(Silol\*(So, as well as the immediate operand 2 are used
  159. in the shift instruction. As suggested before, all of this can be
  160. achieved with push-pop optimization.
  161. .NH 3
  162. A mechanism for push-pop optimization
  163. .PP
  164. To implement the above optimization we need some mechanism to
  165. temporarily store information during compilation.
  166. We need to be able to store, compare and retrieve information from the
  167. temporary storage (cache) without any
  168. loss of information. Before describing all the routines used
  169. to implement our cache we will first describe how the cache works.
  170. .PP
  171. Items in the cache are structures containing an external (\*(Sichar *\*(So),
  172. two registers (\*(Sireg_t\*(So) and a constant (\*(Siarith\*(So),
  173. any of which may be 0.
  174. The value of such a structure is the sum of (the values of)
  175. its elements. To put a register in the cache, one has to be allocated either
  176. by calling \*(Sialloc_reg\*(So which returns a free register, by
  177. \*(Siforced_alloc_reg\*(So which allocates a specific register or any
  178. of the other routines available to allocate a register. The keep things
  179. simple, we will not discuss all of the available primitives here.
  180. When the register
  181. is then put in the cache by the \*(Sipush_reg\*(So routine, the ownership will
  182. be transferred from the user to the cache. Ownership is important, because
  183. only the owner of a register may (and must!) deallocate it. Registers can be
  184. owned by either an (imaginary) register manager, the cache or the user.
  185. When the user retrieves a register from the stack with \*(Sipop_reg\*(So for
  186. instance, ownership is back to the user.
  187. The user should then call \*(Sifree_reg\*(So
  188. to transfer ownership to the register manager or call \*(Sipush_reg\*(So
  189. to give it back to the cache.
  190. Since the cache behaves itself as a stack we will use the term pop resp. push
  191. to get items from, resp. put items in the cache.
  192. .PP
  193. We shall now present the sets of routines that implement the cache.
  194. .IP \(bu
  195. The routines
  196. .DS
  197. \*(Si
  198. reg_t alloc_reg(void)
  199. reg_t alloc_reg_var(void)
  200. reg_t alloc_float(void)
  201. reg_t alloc_float_var(void)
  202. reg_t alloc_double(void)
  203. reg_t alloc_double_var(void)
  204. void forced_alloc_reg(reg_t)
  205. void soft_alloc_reg(reg_t)
  206. void free_reg(reg_t)
  207. void free_double_reg(reg_t)
  208. \*(So
  209. .DE
  210. allocate and deallocate registers. If there are no more register left,
  211. i.e. they are owned by the cache,
  212. one or more registers will be freed by flushing part of the cache
  213. onto the real stack.
  214. The \*(Sialloc_xxx_var\*(So primitives try to allocate a register that
  215. can be used to store local variables. (In the current implementation
  216. only the input and local registers.) If none can be found \*(SiNULL\*(So
  217. is returned. \*(Siforced_alloc_reg\*(So forces the allocation of a certain
  218. register. If it was already in use, its contents are moved to another
  219. register. Finally \*(Sisoft_alloc_reg\*(So provides the possibility to
  220. push a register onto the cache and still keep a copy for later use.
  221. (Used to implement the \*(Sidup 4\*(So for example.)
  222. .IP \(bu
  223. The routines
  224. .DS
  225. \*(Si
  226. void push_const(arith)
  227. arith pop_const(void)
  228. \*(So
  229. .DE
  230. push or pop a constant onto or from the stack. Distinction between
  231. constants and other types is made so as not to loose any information; constants
  232. may be used later on as immediate operators, which is not the case
  233. for other types. If \*(Sipop_const\*(So is called, but the element on top of
  234. the cache has either one of the external or register fields non-zero a
  235. fatal error will be reported.
  236. .IP \(bu
  237. The routines
  238. .DS
  239. \*(Si
  240. reg_t pop_reg(void)
  241. reg_t pop_float(void)
  242. reg_t pop_double(void)
  243. reg_t pop_reg_c13(char *n)
  244. void pop_reg_as(reg_t)
  245. void push_reg(reg_t)
  246. \*(So
  247. .DE
  248. push or pop a register. These will be used most often since results from one
  249. EM instruction, which are computed in a register, are often used in the next.
  250. When the element on top of the cache is more
  251. than just a register the cache manager
  252. will generate code to compute the sum of its fields and put the result in a
  253. register. This register will then be given to the user.
  254. If the user wants the result is a special register, he should use the
  255. \*(Sipop_reg_as\*(So routine.
  256. The \*(Sipop_reg_c13\*(So gives an optional number (as character string) whose
  257. value can be represented in 13 bits. The constant can then be used as an
  258. offset for the SPARC \*(Sild\*(So and \*(Sist\*(So instructions.
  259. .IP \(bu
  260. The routine
  261. .DS
  262. \*(Si
  263. void push_ext(char *)
  264. \*(So
  265. .DE
  266. pushes an external onto the stack. There is no pop-variant of this one since
  267. there is no use in popping an external.
  268. .IP \(bu
  269. The routines
  270. .DS
  271. \*(Si
  272. void inc_tos(arith n)
  273. void inc_tos_reg(reg_t r)
  274. \*(So
  275. .DE
  276. increment the element on top of the cache by either the constant \*(Sin\*(So
  277. or by a register. The latter is useful for pointer addition when referencing
  278. external memory.
  279. .KS
  280. .IP \(bu
  281. The routine
  282. .DS
  283. \*(Si
  284. int type_of_tos(void)
  285. \*(So
  286. .DE
  287. .KE
  288. returns the type of the element on top of the cache. This is a combination
  289. (binary OR) of \*(SiT_ext\*(So, \*(SiT_reg\*(So or \*(SiT_float\*(So,
  290. \*(SiT_reg2\*(So or \*(SiT_float2\*(So, and \*(SiT_cst\*(So,
  291. and tells the
  292. user which of the three fields are non-zero. When the register-fields
  293. represent \*(Si%g0\*(So, it is considered zero.
  294. .IP \(bu
  295. Miscellaneous routines:
  296. .DS
  297. \*(Si
  298. void init_cache(void)
  299. void cache_need(int)
  300. void change_reg(void)
  301. void flush_cache(void)
  302. \*(So
  303. .DE
  304. \*(Siinit_cache\*(So should be called before any
  305. other cache routines, to initialize some internal datastructures.
  306. \*(Sicache_need\*(So is used to tell the cache that a certain number
  307. of register are needed for the next operation. This way the cache can
  308. load them efficiently in one fell swoop. \*(Sichange_reg\*(So is to be
  309. called when the user changes a register of which the cache (possibly) has
  310. co-ownership. Because the contents of registers in the cache are
  311. not allowed to change the user should call \*(Sichange_reg\*(So to
  312. instruct the cache to copy the contents to some other register.
  313. \*(Siflush_cache\*(So writes the cache to the stack and invalidates
  314. the cache. It should be used before branches,
  315. before labels and on other places where the stack has to be valid (i.e. where
  316. every item on the EM-stack should be stored on the real stack, not in some
  317. virtual cache).
  318. .NH 3
  319. Implementing push-pop optimization in the EM_table
  320. .PP
  321. As indicated above, there is no regular way to represent the described
  322. optimization in the EM_table. The only possible escapes from the EM_table
  323. are function calls, but that is clearly not enough to implement a good
  324. push-pop optimizer. Therefore we will use a modified version of the EM_table
  325. format, where the description of, say, the \*(Silol\*(So instruction might look
  326. like this\(dg:
  327. .FS
  328. \(dg This is not the way the \*(Silol\*(So actually looks in the EM_table;
  329. it only shows how it \fImight\fR look using the forementioned push/pop
  330. primitives.
  331. .FE
  332. .DS
  333. \*(Si
  334. reg_t A, B;
  335. const_str_t n;
  336. alloc_reg(A);
  337. push_reg(LB);
  338. inc_tos($1);
  339. B = pop_reg_c13(n);
  340. "ld [$B+$n], $A";
  341. push_reg(A);
  342. free_reg(B);
  343. \*(So
  344. .DE
  345. For more details about the exact implementation consult
  346. appendix B which contains some characteristic excerpts from the EM_table.
  347. .NH 2
  348. Stack management
  349. .PP
  350. When converting EM code to some executable code there is the problem of
  351. maintaining multiple stacks. The usual way to do this is described in
  352. .[ [
  353. Description of a Machine Architecture
  354. .]]
  355. and is shown in figure \*(SN1.
  356. .KE
  357. .PS
  358. copy "pics/EM_stack.orig"
  359. .PE
  360. .ce 1
  361. \fIFigure \*(SN1: usual stack management.
  362. .KE
  363. .sp
  364. .LP
  365. This means that the EM stack and the hardware stack (used
  366. for subroutine calls, etc.) are interleaved in memory. On the SPARC, however,
  367. this brings up a large problem: in the former model it is assumed that the
  368. resolution of the stack pointer is a word, but this is not the case on the
  369. SPARC processor. On the SPARC processor the stack-pointer as well as the
  370. frame-pointer have to be aligned on 8-byte boundaries, so one can not simply
  371. push a word on the stack and then lower the stack-pointer by 4 bytes!
  372. .NH 3
  373. Possible solutions
  374. .PP
  375. A simple idea might be to use a swiss-cheese stack; we could
  376. push a 4-byte word onto the stack and then lower the stack by 8.
  377. Unfortunately, this is not a very solid solution, because
  378. pointer-arithmetic involving pointers to objects on the stack would cause
  379. hard-to-predict anomalies.
  380. .PP
  381. Another try would be not to use the hardware stack at all. As long as we
  382. do not generate subroutine-calls everything will be all right. This
  383. approach, however, also has some disadvantages: first we would not be able
  384. to use any of the existing debuggers such as \fIadb\fR, because they all
  385. assume a regular stack format. Secondly, we would not be able to make use
  386. of the SPARC's register windows to keep local variables. Finally, doing all the
  387. administrative work necessary for subroutine calls ourselves instead of
  388. letting the hardware handle it for us,
  389. causes unnecessary procedure-call overhead.
  390. .PP
  391. Yet another alternative would be to emulate the EM-part of the stack,
  392. and to let the hardware handle the subroutine call. Since we will
  393. emulate our own stack, there are no alignment restrictions and because
  394. we will use the hardware procedure call we can still make use of
  395. the register windows.
  396. .NH 3
  397. Our implementation
  398. .PP
  399. To implement the hybrid stack we need two extra registers: one for the
  400. the EM stack pointer (the forementioned \*(Si%SP\*(So) and one for the
  401. EM local base pointer (\*(Si%LB\*(So). The most elegant solution would be to
  402. put both stacks in different segments, so they would not influence
  403. each other. Unfortunately
  404. .UX
  405. lacks the ability to add segments and
  406. since we will implement our backend under
  407. .UX,
  408. we will have to put
  409. both stacks in the same segment. Exactly how this can be done is shown
  410. in figure \*(SN2.
  411. .DS
  412. .PS
  413. copy "pics/mem_config"
  414. .PE
  415. .ce 1
  416. \fIFigure \*(SN2: our stack management.\fR
  417. .DE
  418. .sp
  419. During normal procedure execution, the SPARC stack pointer has to point to
  420. a memory location where the operating system can dump the active part of
  421. the register window. The rest of the
  422. register window will be dumped in the therefor pre-allocated (stack) space
  423. by following the frame
  424. pointer. When a signal occurs things get even more complicated and
  425. result in figure \*(SN3.
  426. .DS
  427. .PS
  428. copy "pics/signal_stack"
  429. .PE
  430. .ce 1
  431. \fIFigure \*(SN3: our signal stack.\fR
  432. .DE
  433. .PP
  434. The exact implementation of the stack is shown in figure \*(SN4.
  435. .KF
  436. .PS
  437. copy "pics/EM_stack.ours"
  438. .PE
  439. .ce 1
  440. \fIFigure \*(SN4: stack overview.\fR
  441. .KE
  442. .NH 2
  443. Miscellaneous
  444. .PP
  445. As mentioned in the previous chapter, the generated \fI.o\fR-files are
  446. not compatible with Sun's own object format. The primary reason for
  447. this is that Sun usually passes the first six parameters of a procedure call
  448. through registers. If we were to do that too, we would always have
  449. to fetch the top six words from the stack into registers, even when
  450. the procedure would not have any parameters at all. Apart from this,
  451. structure-passing is another exception in Sun's object format which
  452. makes is impossible to generate object-compatible code.\(dg
  453. .FS
  454. \(dg Exactly how Sun passes structures as parameters is described in
  455. Appendix D of the SPARC Architecture Manual (Software Considerations)
  456. .FE
  457. .bp