doc/sparc/5

   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