PENTIUM/486 Optimization
------------------------
By Michael Kunstelj.
G'day all...
In case any one is interested, here is some information on optimising
assembly code on the Pent / 486. If you don't know/aren't interested in
ASSEMBLY code, this will all seem about as interesting as ending titles in
a bad X-Rated movie. Still, hopefully someone out there will find this
useful. If so, enjoy... and....
Brief Intro
----------------
Now a brief intro on the innards of the 486 and Pent586.
Most processors these days have within in them a system termed a
"pipeline".
The 486 / 586 are certainly within this category. However, most people
aren't quite sure what exactly a pipeline is, here's a rough analogy:
Imagine a processing plant, with a line of employees each performing a
certain task. On one end of the line, the first employee receives a piece,
which he works apon. After completing his task, he passes it to the next
employee, who in turn works apon the item. The process continues until
the item is at the end of the line, apon which time it is considered
completed. However, with this simplistic model, does it not seem strange
that for each item, all employees must wait for the first item to
manufactured before the next one can be considered. Yup, it is, and stupid
to boot.
It makes far more sense for each employee to work on something in the
interim. Thus, employee 1 in the above example finishes his work on the
item, passes it to employee 2, and then picks up a new item and starts
working on it.
That's pretty well the same system in a Microprocessors pipeline.
Numerous blocks perform in parallel, passing their information on when
the stage in front of it is free.
Because of pipelining, times taken in terms of instruction cycles become
blurred. An instruction that takes 7 clock cycles to implement, for
example, will be behind in the pipeline from the previous instruction. After
the previous instruction is completed, the final stage in the pipeline will be
dedicated to the next instruction. This final stage may take perhaps 1 or 2
clock cycles. The net effect? The instruction will effectively appear to
have taken 1 or 2 clock cycles to execute.
The 586 Pent is a superscalar system using multiple pipeline to process
data. You get the idea from the example above sort of how it would work.
Anyway, here are some ways to speed up 486/586 code:
SPEEDING UP 486/586 CODE.
--------------------------------------------------
AGI
------
An Address Generation Interlock is occurs when a register which is
currently being used as the base or an index was the destination component
of a previous instruction.
For example,:
add edx, 4
// AGI, ONE CLOCK STALL
mov esi, [edx]
For the 486, AGI's can only occur on adjacent instructions. On the 586
Pent, having the term superscalar in its design specification to amaze
people with its high degree of parallel execution, instructions up to 3
locations away can cause an AGI.
The code: (worst case scenario)
add esi, 4
pop ebx
dec ebx
mov edx, [esi]
Takes 4 clocks on a 486. On a 586, the move command must wait for the
add command, thus AGI stalling for one clock. The code above then
would run in three clock cycles on a 586.
Some Instructions that read or write implicitly to registers cause AGI stalls.
eg. mov esp, ebp [agi] pop ebp.
When decoding an instruction with either an index or an immediate-
displacement combination, 486's have a one clock penalty. (586's do not)
Example:
mov spam, 248
mov dword ptr [esp+4], 1
486's have a one clock penalty when modifying the lower word of a
DWORD register. 586's do not.
Example:
mov al,0
mov [ebp], eax
(a one clock penalty on 486, no penalty on a 586)
CODE ALIGNMENT
-------------------------------
To speed up the 486 instructions, alignment of code should be on the
beginning of cache boundaries.
(32 bytes on 586, 16 bytes on 486)
Thus, start your routine on the start of the cache page. This will speed up
the processing of all the instructions within that page. The effect of this
speed up on the 586 is not a dramatic as is it is on the 486.
DATA ALIGNMENT
------------------------------
Misaligned access in the data cache causes an extra 3 cycles on both the
486 and 586.
Ways to speed up data:
For DWORD data, alignment should be on a 4-byte boundary.
For WORD data, alignment should be on a 2 byte boundary for the 486,
and simply within the 4-byte page for the 586.
For 8 byte data (64 bits), data should be aligned on a 8-byte boundary.
And yes, on many applications with tight inner loops, these things do
accumulate to make a noticeable speed-up.
SPEEDING UP REGISTER AND OPERAND USAGE
-------------------------------------------------------------------------------
Use the EAX as much as possible. Many instructions are 1 byte shorter
when using EAX. That's less code you have to move around and slightly
less internal processing.
Use the DS register as much as possible for roughly the same reason,
In the case of several references being made to a variable addressed with a
displacement, load the displacement into a register.
Try to use the ESP register to reference the stack in lower levels of your
subroutines.
HANDY INFO ON SPEEDING UP INTEGER INSTRUCTIONS
---------------------------------------------------------------------------------------------
Spaced out yet? Feel like optimising code now is a job for anal-retentive
nasal-spray toting coders locked in small dark rooms somewhere? Well,
here are some tips to make you swear-off from using nasal spray ever
again. Well, not actually that bad, but hey.... Here are some
optimisations one can perform on the Integer side of the 486/586. I never
use the floating point processor, and for that matter don't like it a whole
heap. Most people used fixed point routines for fast graphics etc anyway.
1. Avoid using complex instructions like LEAVE, ENTER, LOOP, string
instructions etc Simpler instructions will get the job done faster. Simpler
instructions have been getting faster with every new processor that has
come along.
2. With 8-bit operands, do your best to use the byte opcodes, rather than
using the 32 bit instructions with sign and zero extended modes. Internal
sign extension is expensive, and speed increases can be found by
simplifying the process as much as possible.
3. LEA's generally increase the chance of AGI's. However, LEA's are
advantageous when:
-> In many cases an LEA instruction may be used to replace constant
multiply instructions. (a sequence of LEA, add and shift for example)
-> LEA may be used as a three/four operand addition instruction.
LEA ECX, [EAX+EBX*4+ARRAY_NAME]
-> Can be advantageous to avoid copying a register when both operands to
an ADD are being used after the ADD as LEA need not overwrite its
operands.
4. Zero-Extension with short ints terror tales
The MOVZX takes four cycles to execute due to due zero-extension
wobblies. A better way to load a byte into a register is by:
xor eax,eax
mov al,memory
As the xor just clears the top parts of EAX, the xor may be placed on the
outside of a loop that uses just byte values. The 586 shows greater
response to such actions.
It is recommended that 16 bit data be accessed with the MOVSX and
MOVZX if you cannot place the XOR on the outside of the loop.
5. When comparing a value in a register with 0, use the TEST command.
TEST operates by ANDing the operands together without spending any
internal time worrying about a destination register. (Compared with just
ANDing a register with itself to test 0 condition)
Use test when comparing the result of a boolean AND command with an
immediate constant for equality or inequality if the register is EAX. (IF
(VAR & 4) {...} for example)
6. Address Calculations
Pull address calculations into load and store instructions. Memory
reference instructions have 4 operands: a relocatable time segment base, a
base register, a scaled index register and a displacement. Often several
integer instructions can be eliminated by fully using the operands of
memory addresses. Often, most people don't worry about it and turn to
drinking coffee instead. I'm not sure, care less. Its an options to speed
things up if you want it.
7. INTEGER DIVIDE
In most cases, an Integer Divide is preceded by a CDQ instruction.
This is as divide instructions use EDX:EAX as the dividend and CDQ sets
up EDX.
It is better to copy EAX into EDX, then right shift EDX 31 places to sign
extend.
The copy/shift instructions take the same number of clocks as CDQ,
however, on 586's allows two other instructions to execute at the same
time. If you know the value is a positive, use XOR EDX, EDX.
8. INTEGER MULTIPLY
The integer multiply by an immediate can usually be replaced with a faster
and simpler series of shifts, subs, adds and lea's.
As a rule of thumb when 6 or fewer bits are set in the binary representation
of the constant, it is better to look at other ways of multiplying and not use
INTEGER MULTIPLY. (the thumb value is 8 on a 586)
A simple way to do it is to shift and add for each bit set.
9. Clearing Registers
Using XOR reg, reg is fast but sets up conditions codes. A slightly slower
way to do it of course is to mov reg, 0 which preserves condition codes.
10. Avoid ENTER, instead, try something like:
PUSH EBP
mov ebp, esp
sub esp, BYTE_COUNT
11. JUMP INSTRUCTIONS
Jump instruction come in two forms, one real near that jumps between -127
and 128 of the current location, and a 32 bit version that does a full jump.
The short form is quite a bit faster, however unfortunately many compilers
put long jumps where short jumps would suffice.
To ensure that short jumps can be used (and you know it is possible),
explicitly specify the destination as being byte length.
12. Task Switching
Task Switching is evil. It is slow, real slow. Avoid task switching too
often, as more and more of your time will be spent in processing the task
switch.
For faster task switching, perform you task switching in software. This
allows a smaller processor state to be saved and restored. Anything that
shaves time off 75+ clock cycles isn't all that bad in my book.
13. Minimise segment register loads and the use of far pointers as dearly
much as you can. If you are doing a lot of processing on a small piece of
data far away, it might be faster just to copy the data to nearby and work
on it there.
...and....
14. THINK ABOUT WHAT YOU WANT TO DO
All the other optimisations of Unrolling Loops, moving the invariant data
etc still apply. That, however, is more an algorithmic problem for you, but
still keep it firmly in mind.
586 Specific Optimisations
--------------------------
The 586Pent has a five stage pipeline structure. (You remember, five
employees sitting in a row)
However, the pipeline is split into two different pipelines, known
as Pipeline U and Pipeline V. This allows two instructions to be
executed in parallel and thus presents the opportunity of
executing two/instuctions per clock.
The U pipeline is vwery much like the 486 pipeline, in that it can handle
the entire set of instructions. Pipeline V on the otherhand can
handle only simple instructions.
The fast parts of the U and V pipelines are possible as much of the
functions are hardwired not microcoded.
Anyway, I've blurted on about that for a bit, but what you want to know
is "How to I get two instructions running in one clock/cycle?"
Lament no further, here are the criteria:
1. Both instructions must be simple (see below)
2. There must not be a read-after-write or write-after-read
register/flag dependencies between them.
3. Neither can have a displacement and an immediate
4. Instructions with prefixes can only occurr in the U-pipe
(except for Jcc)
The following are considered "simple" instructions,
the ALU means any ALU command (ADD etc):
1. Mov reg, reg/mem/immed
2. mov mem, reg/imm
3. ALU reg, reg/mem/immed
4. ALU mem, reg/immed
5. inc reg/mem
6. dec reg/mem
7. push reg/mem
8. pop reg
9. nop
10. lea reg/mem
11. Jmp/ Call / Jcc near
Note, however, than while both pipelines can perform ALU
instructions concurrently, this is not the case when
one ALU instruction requires the output of the
other pipeline ALU instruction. E.g. ALU instruction in pipe U and
performing ADC in pipe V.
There are two exceptions to this rule:
1) In the case of a compare/branch combination.
2) With push/pop combinations.
Branch Possibility Thingy
-------------------------
Another nice optimisation with the 586 hardware is that whenever there is
a possibility of a jump, for example, Jg, the 586 will automatically
start reading code from the jump location just in case the the
Jump is accepted. Remember the CODE alignment thing above? Well,
it couldn't hurt your grandmother to align the labels on the code pages.
(So a jump will go to the start of a code page)
Amazing new 586 Optimisations and speedups
------------------------------------------
The 586 has a lot of really nice optimisations and kick-ass
features in addition to what I've mentioned above, unfortunately,
this information is proprietry and will only be given
to people who sign non-disclosure agreements and shell out a
$$ or two... Bummer...
(Meethinks, 586 clone-makers won't be too happy about that... :-) )
Compiler/OS makers will probably be the purchasers.
Quite a few of these optimisations won't work on anything less than
a 586, so don't sweat too much about it. Hey, just write
for 386/486/586 and you'll be ok.
I hope this information has been helpful for you.
Now make some coffee, brush your teeth and phone up your girlfriend and
go and see a movie. This document will be here when you get back, and I
imagine there is only so much of this you can take in one day.... :-) :-) :-)
Live long and code well...
Regards,
Michael Kunstelj.
{ > I MURDER AND EAT SENSITIVE PEOPLE < :-)
{ Contact at : virteam@smoke.canberra.edu.au or
{ mick@cairo.anu.edu.au
{
{ Disclaimer: I don't represent anyone, and no-one would be foolish
enough to represent {me. I take no responsibility of the information
presented here. If you cat explodes {when you hit the enter key, I don't
want to know. (except if you have photos...) :-) :-)
{ Plus every other disclaimer that everyone has ever thought of. So there...
;-)