123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468 |
- .In
- .hw data-structures
- .nr H1 3
- .NH
- SOLUTIONS
- .NH 2
- Maintaining SPARC speed
- .PP
- In chapter 3 we wrote:
- .sp 0.3
- .nf
- >If we want to generate efficient code, we should at least try to reduce the number of
- >memory references and use registers wherever we can.
- .fi
- .sp 0.3
- In this chapter we will device a strategy to swiftly generate acceptable
- code by using push-pop optimization.
- Note that this is not the push-pop
- optimization already available in the EM-kit, since that is only present
- in the assembler-to-binary part which we do not use
- .[ [
- The Code Expander Generator
- .]].
- Our push-pop optimization
- works more like the fake-stack described in
- .[ [
- The table driven code generator
- .]].
- .NH 3
- Ad-hoc optimization
- .PP
- Before getting involved in any optimization let's have a look at some
- code generated with a straightforward EM to SPARC conversion of the
- C statement: \*(Sif(a[i]);\*(So Note that \*(Si%SP\*(So is an alias
- for a general purpose
- register and acts as the EM stack pointer. It has nothing to do with
- \*(Si%sp\*(So \(em the SPARC stack pointer.
- Analogous \*(Si%LB\*(So is EMs local base pointer.
- .br
- .IP
- .HS
- .TS
- ;
- l s l s l
- l1f6 lf6 l2f6 lf6 l.
- EM code SPARC code Comment
- lae _a set _a, %g1 ! load address of external _a
- dec 4, %SP
- st %g1, [%SP]
- lol -4 set -4, %g1 ! load local -4 (i)
- ld [%g1+%LB], %g2
- dec 4, %SP
- st %g2, [%SP]
- loc 2 set 2, %g1 ! load constant 2
- dec 4, %SP
- st %g1, [%SP]
- sli 4 ld [%SP], %g1 ! pop shift count
- ld [%SP+4], %g2 ! pop shiftee
- sll %g2, %g1, %g3
- inc 4, %SP
- st %g3, [%SP] ! push 4 * i
- ads 4 ld [%SP], %g1 ! add pointer and offset
- ld [%SP+4], %g2
- add %g1, %g2, %g3
- inc 4, %SP
- st %g3, [%SP] ! push address of _a + (4 * i)
- loi 4 ld [%SP], %g1 ! load indirect 4 bytes
- ld [%g1], %g2
- st %g2, [%SP] ! push a[i]
- cal _f
- ...
- .TE
- .HS
- .LP
- Although the code is easy understand, it clearly is far from optimal.
- The above code uses approximately 60 clock-cycles\(dg
- .FS
- \(dg In general each instruction only takes one cycle,
- except for \*(Sild\*(So and
- \*(Sist\*(So which may both require additional clock cycles. The exact amount
- of extra cycles needed depends on the SPARC implementation and memory access
- time. Furthermore, the
- \*(Siset\*(So pseudo-instruction is a bit tricky. It takes one cycle when
- its argument lies between -4096 and 4095, and two cycles otherwise.
- .FE
- to push an array-element on the stack,
- something which a 68020 can do in a single instruction. The SPARC
- processor may be fast, but not fast enough to justify the above code.
- .PP
- The same statement can be translated much more efficiently:
- .DS
- .TS
- ;
- l2f6 lf6 l.
- sll %i0, 2, %g2 ! multiply index by 4
- set _a, g3
- ld [%g2+%g3], %g1 ! get contents of a[i]
- dec 4, SP
- st %g2, [SP] ! push a[i] onto the stack
- .TE
- .DE
- which, instead of 60, uses only 5 clock cycles to retrieve the element
- from memory and 5 additional cycles when the result has to be pushed
- on the stack. Note that when the result is not a parameter it does not
- have to be pushed on the stack. By making efficient use of the SPARC
- registers we can fetch \*(Sia[i]\*(So in only 5 cycles!
- .NH 3
- Analyzing optimization
- .PP
- Instead of ad-hoc optimization we will need something more solid.
- When one tries to optimize the above code in an ad-hoc manner one will
- probably notice the large overhead due to stack access. Almost every EM
- instruction requires at least three SPARC instructions: one to carry out
- the EM instruction and two to pop and push the result from and onto the
- stack. This happens for every instruction, even though the data being pushed
- will probably be needed by the next instruction. To optimize this extensive
- pushing and popping of data we will use the appropriately named push-pop
- optimization.
- .PP
- The idea behind push-pop optimization is to delay the push operation until
- it is almost certain that the data actually has to be pushed.
- As is often the case, the data does not have to be pushed,
- but will be used as input to another EM instruction.
- If we can decide at compile time that this will indeed be
- the case we can save the time of first pushing the data and then popping it
- back again by temporarily storing the data (possibly only during compilation!)
- and using it no sooner than it is actually needed.
- .PP
- The \*(Sisli 4\*(So instruction, for instance, expects two inputs on top of the
- stack: on top a counter and right below that the shiftee (the number
- to be shifted). As a result \*(Sisli\*(So
- pushes 'shiftee << counter' back to the stack. Now consider the following
- sequence, which could be the result of the expression \*(Si4 * i\*(So
- .DS
- .TS
- ;
- l1f6 lf6 l.
- lol -4
- loc 2
- sli 4
- .TE
- .DE
- In the non-optimized situation the \*(Silol\*(So would push
- a local variable (whose offset is -4) on the stack.
- Then the \*(Siloc\*(So pushes a 2 on the stack and finally \*(Sisli\*(So
- retrieves both these numbers to replace then with the result.
- On most machines it is not necessary to
- push the 2 on the stack, since it can be used in the shift instruction
- as an immediately operand. On a SPARC, for instance, one can write
- .DS
- .TS
- ;
- l2f6 lf6 l.
- ld [%LB-4], %g1 ! load local variable into register g1
- sll %g1, 2, %g2 ! perform the shift-left-by-2
- .TE
- .DE
- where the output of the \*(Silol\*(So, as well as the immediate operand 2 are used
- in the shift instruction. As suggested before, all of this can be
- achieved with push-pop optimization.
- .NH 3
- A mechanism for push-pop optimization
- .PP
- To implement the above optimization we need some mechanism to
- temporarily store information during compilation.
- We need to be able to store, compare and retrieve information from the
- temporary storage (cache) without any
- loss of information. Before describing all the routines used
- to implement our cache we will first describe how the cache works.
- .PP
- Items in the cache are structures containing an external (\*(Sichar *\*(So),
- two registers (\*(Sireg_t\*(So) and a constant (\*(Siarith\*(So),
- any of which may be 0.
- The value of such a structure is the sum of (the values of)
- its elements. To put a register in the cache, one has to be allocated either
- by calling \*(Sialloc_reg\*(So which returns a free register, by
- \*(Siforced_alloc_reg\*(So which allocates a specific register or any
- of the other routines available to allocate a register. The keep things
- simple, we will not discuss all of the available primitives here.
- When the register
- is then put in the cache by the \*(Sipush_reg\*(So routine, the ownership will
- be transferred from the user to the cache. Ownership is important, because
- only the owner of a register may (and must!) deallocate it. Registers can be
- owned by either an (imaginary) register manager, the cache or the user.
- When the user retrieves a register from the stack with \*(Sipop_reg\*(So for
- instance, ownership is back to the user.
- The user should then call \*(Sifree_reg\*(So
- to transfer ownership to the register manager or call \*(Sipush_reg\*(So
- to give it back to the cache.
- Since the cache behaves itself as a stack we will use the term pop resp. push
- to get items from, resp. put items in the cache.
- .PP
- We shall now present the sets of routines that implement the cache.
- .IP \(bu
- The routines
- .DS
- \*(Si
- reg_t alloc_reg(void)
- reg_t alloc_reg_var(void)
- reg_t alloc_float(void)
- reg_t alloc_float_var(void)
- reg_t alloc_double(void)
- reg_t alloc_double_var(void)
- void forced_alloc_reg(reg_t)
- void soft_alloc_reg(reg_t)
- void free_reg(reg_t)
- void free_double_reg(reg_t)
- \*(So
- .DE
- allocate and deallocate registers. If there are no more register left,
- i.e. they are owned by the cache,
- one or more registers will be freed by flushing part of the cache
- onto the real stack.
- The \*(Sialloc_xxx_var\*(So primitives try to allocate a register that
- can be used to store local variables. (In the current implementation
- only the input and local registers.) If none can be found \*(SiNULL\*(So
- is returned. \*(Siforced_alloc_reg\*(So forces the allocation of a certain
- register. If it was already in use, its contents are moved to another
- register. Finally \*(Sisoft_alloc_reg\*(So provides the possibility to
- push a register onto the cache and still keep a copy for later use.
- (Used to implement the \*(Sidup 4\*(So for example.)
- .IP \(bu
- The routines
- .DS
- \*(Si
- void push_const(arith)
- arith pop_const(void)
- \*(So
- .DE
- push or pop a constant onto or from the stack. Distinction between
- constants and other types is made so as not to loose any information; constants
- may be used later on as immediate operators, which is not the case
- for other types. If \*(Sipop_const\*(So is called, but the element on top of
- the cache has either one of the external or register fields non-zero a
- fatal error will be reported.
- .IP \(bu
- The routines
- .DS
- \*(Si
- reg_t pop_reg(void)
- reg_t pop_float(void)
- reg_t pop_double(void)
- reg_t pop_reg_c13(char *n)
- void pop_reg_as(reg_t)
- void push_reg(reg_t)
- \*(So
- .DE
- push or pop a register. These will be used most often since results from one
- EM instruction, which are computed in a register, are often used in the next.
- When the element on top of the cache is more
- than just a register the cache manager
- will generate code to compute the sum of its fields and put the result in a
- register. This register will then be given to the user.
- If the user wants the result is a special register, he should use the
- \*(Sipop_reg_as\*(So routine.
- The \*(Sipop_reg_c13\*(So gives an optional number (as character string) whose
- value can be represented in 13 bits. The constant can then be used as an
- offset for the SPARC \*(Sild\*(So and \*(Sist\*(So instructions.
- .IP \(bu
- The routine
- .DS
- \*(Si
- void push_ext(char *)
- \*(So
- .DE
- pushes an external onto the stack. There is no pop-variant of this one since
- there is no use in popping an external.
- .IP \(bu
- The routines
- .DS
- \*(Si
- void inc_tos(arith n)
- void inc_tos_reg(reg_t r)
- \*(So
- .DE
- increment the element on top of the cache by either the constant \*(Sin\*(So
- or by a register. The latter is useful for pointer addition when referencing
- external memory.
- .KS
- .IP \(bu
- The routine
- .DS
- \*(Si
- int type_of_tos(void)
- \*(So
- .DE
- .KE
- returns the type of the element on top of the cache. This is a combination
- (binary OR) of \*(SiT_ext\*(So, \*(SiT_reg\*(So or \*(SiT_float\*(So,
- \*(SiT_reg2\*(So or \*(SiT_float2\*(So, and \*(SiT_cst\*(So,
- and tells the
- user which of the three fields are non-zero. When the register-fields
- represent \*(Si%g0\*(So, it is considered zero.
- .IP \(bu
- Miscellaneous routines:
- .DS
- \*(Si
- void init_cache(void)
- void cache_need(int)
- void change_reg(void)
- void flush_cache(void)
- \*(So
- .DE
- \*(Siinit_cache\*(So should be called before any
- other cache routines, to initialize some internal datastructures.
- \*(Sicache_need\*(So is used to tell the cache that a certain number
- of register are needed for the next operation. This way the cache can
- load them efficiently in one fell swoop. \*(Sichange_reg\*(So is to be
- called when the user changes a register of which the cache (possibly) has
- co-ownership. Because the contents of registers in the cache are
- not allowed to change the user should call \*(Sichange_reg\*(So to
- instruct the cache to copy the contents to some other register.
- \*(Siflush_cache\*(So writes the cache to the stack and invalidates
- the cache. It should be used before branches,
- before labels and on other places where the stack has to be valid (i.e. where
- every item on the EM-stack should be stored on the real stack, not in some
- virtual cache).
- .NH 3
- Implementing push-pop optimization in the EM_table
- .PP
- As indicated above, there is no regular way to represent the described
- optimization in the EM_table. The only possible escapes from the EM_table
- are function calls, but that is clearly not enough to implement a good
- push-pop optimizer. Therefore we will use a modified version of the EM_table
- format, where the description of, say, the \*(Silol\*(So instruction might look
- like this\(dg:
- .FS
- \(dg This is not the way the \*(Silol\*(So actually looks in the EM_table;
- it only shows how it \fImight\fR look using the forementioned push/pop
- primitives.
- .FE
- .DS
- \*(Si
- reg_t A, B;
- const_str_t n;
- alloc_reg(A);
- push_reg(LB);
- inc_tos($1);
- B = pop_reg_c13(n);
- "ld [$B+$n], $A";
- push_reg(A);
- free_reg(B);
- \*(So
- .DE
- For more details about the exact implementation consult
- appendix B which contains some characteristic excerpts from the EM_table.
- .NH 2
- Stack management
- .PP
- When converting EM code to some executable code there is the problem of
- maintaining multiple stacks. The usual way to do this is described in
- .[ [
- Description of a Machine Architecture
- .]]
- and is shown in figure \*(SN1.
- .KE
- .PS
- copy "pics/EM_stack.orig"
- .PE
- .ce 1
- \fIFigure \*(SN1: usual stack management.
- .KE
- .sp
- .LP
- This means that the EM stack and the hardware stack (used
- for subroutine calls, etc.) are interleaved in memory. On the SPARC, however,
- this brings up a large problem: in the former model it is assumed that the
- resolution of the stack pointer is a word, but this is not the case on the
- SPARC processor. On the SPARC processor the stack-pointer as well as the
- frame-pointer have to be aligned on 8-byte boundaries, so one can not simply
- push a word on the stack and then lower the stack-pointer by 4 bytes!
- .NH 3
- Possible solutions
- .PP
- A simple idea might be to use a swiss-cheese stack; we could
- push a 4-byte word onto the stack and then lower the stack by 8.
- Unfortunately, this is not a very solid solution, because
- pointer-arithmetic involving pointers to objects on the stack would cause
- hard-to-predict anomalies.
- .PP
- Another try would be not to use the hardware stack at all. As long as we
- do not generate subroutine-calls everything will be all right. This
- approach, however, also has some disadvantages: first we would not be able
- to use any of the existing debuggers such as \fIadb\fR, because they all
- assume a regular stack format. Secondly, we would not be able to make use
- of the SPARC's register windows to keep local variables. Finally, doing all the
- administrative work necessary for subroutine calls ourselves instead of
- letting the hardware handle it for us,
- causes unnecessary procedure-call overhead.
- .PP
- Yet another alternative would be to emulate the EM-part of the stack,
- and to let the hardware handle the subroutine call. Since we will
- emulate our own stack, there are no alignment restrictions and because
- we will use the hardware procedure call we can still make use of
- the register windows.
- .NH 3
- Our implementation
- .PP
- To implement the hybrid stack we need two extra registers: one for the
- the EM stack pointer (the forementioned \*(Si%SP\*(So) and one for the
- EM local base pointer (\*(Si%LB\*(So). The most elegant solution would be to
- put both stacks in different segments, so they would not influence
- each other. Unfortunately
- .UX
- lacks the ability to add segments and
- since we will implement our backend under
- .UX,
- we will have to put
- both stacks in the same segment. Exactly how this can be done is shown
- in figure \*(SN2.
- .DS
- .PS
- copy "pics/mem_config"
- .PE
- .ce 1
- \fIFigure \*(SN2: our stack management.\fR
- .DE
- .sp
- During normal procedure execution, the SPARC stack pointer has to point to
- a memory location where the operating system can dump the active part of
- the register window. The rest of the
- register window will be dumped in the therefor pre-allocated (stack) space
- by following the frame
- pointer. When a signal occurs things get even more complicated and
- result in figure \*(SN3.
- .DS
- .PS
- copy "pics/signal_stack"
- .PE
- .ce 1
- \fIFigure \*(SN3: our signal stack.\fR
- .DE
- .PP
- The exact implementation of the stack is shown in figure \*(SN4.
- .KF
- .PS
- copy "pics/EM_stack.ours"
- .PE
- .ce 1
- \fIFigure \*(SN4: stack overview.\fR
- .KE
- .NH 2
- Miscellaneous
- .PP
- As mentioned in the previous chapter, the generated \fI.o\fR-files are
- not compatible with Sun's own object format. The primary reason for
- this is that Sun usually passes the first six parameters of a procedure call
- through registers. If we were to do that too, we would always have
- to fetch the top six words from the stack into registers, even when
- the procedure would not have any parameters at all. Apart from this,
- structure-passing is another exception in Sun's object format which
- makes is impossible to generate object-compatible code.\(dg
- .FS
- \(dg Exactly how Sun passes structures as parameters is described in
- Appendix D of the SPARC Architecture Manual (Software Considerations)
- .FE
- .bp
|