5 7.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153
  1. .In
  2. .nr H1 4
  3. .NH
  4. FUTURE WORK
  5. .NH 2
  6. A critique of EM
  7. .PP
  8. In general, EM fits its purpose quite well. Numerous compilers have been
  9. written using EM as their intermediate language and it has even become a
  10. commercial product. A great deal of its success is probably due to its
  11. simplicity. There are no extravagant instructions but it does have all the
  12. necessary functions to write a decent compiler.
  13. .PP
  14. There are, however, a few functions that come rather close to being
  15. extravagant. The \*(Silar\*(So function for example \(em used
  16. to fetch an element from an array \(em does not make it much easier
  17. to write a frontend, but does make it unnecessary hard to write an
  18. efficient backend. Other instructions for which it is difficult
  19. to generate efficient code for are those that permit
  20. dynamic operators, such as the \*(Silos\*(So. Dynamic operators, however, provide
  21. significant extra possibilities and can therefore not be disposed of.
  22. Note that even though the array operations \*(Silar\*(So and \*(Sisar\*(So
  23. provide dynamic operators, they do not add additional power, since
  24. they can easily be replaced with a sequence using the \*(Silos\*(So or
  25. \*(Sists\*(So instructions.
  26. .PP
  27. EM code to reference arrays generated by the C frontend can be translated
  28. very efficiently for almost any processor. However the same operation
  29. generated by the Modula-2 frontend (which uses the \*(Silar\*(So),
  30. is much less efficient, although the only difference is that the
  31. latter performs range checking whereas the former does not.\(dg
  32. .FS
  33. \(dg Actually this depends on whether or not explicit range checking in enabled.
  34. This clearly shows that the current code generators are not optimal and
  35. often depend on ad-hoc decisions.
  36. .FE
  37. Since range checking can also be expressed explicitly in
  38. EM (\*(Sirck\*(So) there is no need for any of the array operations
  39. (\*(Siaar\*(So, \*(Silar\*(So and \*(Sisar\*(So).
  40. .PP
  41. Besides efficiency of the array-operations themselves, there still is another
  42. major disadvantage of using these array-operations. In sharp contrast to
  43. all other EM instructions except the \*(Silos\*(So and the \*(Sists\*(So,
  44. they allow dynamic operators, so their effect on the stack-pointer can not
  45. always be
  46. determined at compile-time. This means that efficient caching of the
  47. top-of-stack in registers is almost impossible,
  48. so using these array-operations also effects the
  49. efficiency of the surrounding code. Now that processors are produced with
  50. more and more registers it could be very beneficiary to cache the
  51. top-of-stack, so that the memory/register reference ratio decreases
  52. to the benefit of the overall performance.
  53. .PP
  54. As a final critique, we would also like to discuss the semantics of some of
  55. the EM instructions. In
  56. .[ [
  57. Description of a Machine Architecture
  58. .]]
  59. it is said that
  60. all signed instructions such as the \*(Siadi\*(So, should cause an exception
  61. on overflow. The unsigned operations such as \*(Siadu\*(So, however,
  62. should act as modulo operations and therefor not perform overflow checking.
  63. Since it is very expensive to perform overflow checking in EM,
  64. we would suggest that the backend takes care of this. For languages which
  65. do not require overflow checking, a simple message could be generated to
  66. disable overflow checking in backends. This way all backends could be
  67. written to fully comply to the official EM definition without any reduction in
  68. efficiency.\(dd
  69. .FS
  70. \(dd Currently many backends do not implement error checks because they
  71. are too expensive and almost never needed. Some frontends even have
  72. facilities build in to generate EM-code to force these checks. If this
  73. trend continues we will end up with a de-facto and a de-jure standard
  74. both developed by the same people but nonetheless incompatible.
  75. .FE
  76. When such messages will be added we would like to suggest
  77. that they can enforce overflow checks on unsigned, as well as signed arithmetic.
  78. .PP
  79. As a conclusion we would like to suggest removal of the array operations from
  80. EM, or at least discontinuation of there usage in frontends.
  81. .NH 2
  82. \*(OQWanted: Procedure call information\*(CQ
  83. .PP
  84. The advantage of an intermediate language such as EM is that the backend
  85. no longer has to know about any 'quirks' of the 'input'-language. The major
  86. disadvantage, however, is that the backend no longer knows about any 'quirks'
  87. of the 'input'-language... If the SPARC backend ever has to compete
  88. with Sun's own C-compiler for example, removal of the array-operations
  89. will not be enough. The amount of information that is lost during
  90. the translation to EM is too large to ever generate truly efficient SPARC code.
  91. .PP
  92. To write such an efficient backend one needs to know, for example, whether,
  93. when and what type of parameter is being computed, so the result can be stored
  94. in the proper place and scratch registers can be reused.
  95. (On the SPARC processor, for example, it is very beneficiary
  96. to pass the first six parameters of a procedure call through
  97. registers instead of using the stack.)
  98. One way to express such things in EM is to insert extra messages in
  99. the EM-code. The C statement \*(Sia = f(4, a + b);\*(So for example,
  100. could be translated to the following EM-code:
  101. .DS
  102. .TS
  103. ;
  104. l1f6 lf6 l.
  105. lol -4 ! a
  106. lol -8 ! b
  107. mes x, 2 ! next instruction will compute 2nd parameter
  108. adi 4
  109. mes x, 1 ! next instruction will compute 1st parameter
  110. loc 4
  111. cal _f ! call function f
  112. lfr 4
  113. stl -4 ! store result in a
  114. .TE
  115. .DE
  116. For a code expander it is important that the \*(Simes\*(So pseudo
  117. instructions appear \fIbefore\fR
  118. the EM instruction that computes the parameter, because that way the final
  119. computation (the \*(Siadi\*(So and \*(Siloc\*(So in the previous example)
  120. can be translated to machine code that performs the required computation
  121. and also puts the result in the required place. If it is found to be
  122. too difficult for the frontend to insert these \*(Simes\*(So instructions
  123. at the right place the peep-hole optimizer might swap the \*(Simes\*(So and
  124. the instruction that computes the parameter.
  125. .PP
  126. For some architectures, it is also
  127. possible to generate more efficient code for a procedure when it is a
  128. so-called leaf-procedure: a procedure that doesn't call other procedures.
  129. On the SPARC, for example, it is not necessary to rotate the register
  130. window for a call to a leaf procedure and it is also possible to use
  131. the global registers for register variables in leaf procedures.
  132. It will be a little harder to insert useful messages about leaf procedures,
  133. because just as with register messages, they are only useful to the
  134. backend when they appear immediately
  135. after or before the \*(Sipro\*(So pseudo instruction. The frontend,
  136. however, only knows whether a certain procedure is a leaf-procedure or not
  137. when it has already generated the entire procedure in EM. Just as with the
  138. \*(Sipro ? / end n\*(So-dilemma the peep-hole optimizer
  139. .[ [
  140. Using Peephole Optimization
  141. .]]
  142. might be able to lend a hand
  143. and help us out by delaying EM-code generation until it has reached the
  144. end of the procedure.
  145. .PP
  146. As with most optimizations, the main problem is that they have to be
  147. implemented with the \*(Simes\*(So pseudo instruction.
  148. Because the \*(Simes\*(So instruction can have many different meanings
  149. depending on its argument,
  150. it is important that all optimizers recognize and respect them. Addition
  151. of even a single message will require careful inspection of, and maybe even
  152. incorporate small changes to each of the optimizers.
  153. .bp