Re: programmer optimizations?

"Afsal C. Majeed" <afsal@genius.tisl.soft.net> writes:
>We are having small debate here as to the use of some of the
>code optimizations by the programmer himself.
>e.g.
> replacing (n / 4)
> by (n >> 2)


"David Moore" <davidm@Rational.COM> writes
>As John remarked, this only works if n>=0. The real question is
>how much work does a given compiler do to determine n>=0. If
>n is declared unsigned, almost every compiler will make this
>reduction of strength. Any loop containing a divide is doomed
>to run slowly, so optimizer writers are always keen to eliminate
>them.


Unfortunately it seems you cannot always trust the compiler writers
to do the right thing here. I did experiments with this expression
(n / 4) with some 386/486 C compilers that I had access to.
The first one, a commercial C cross compiler (names omitted to protect
the innocent) does convert the above division into a shift instruction if
the type of "n" is "unsigned", but uses the slow division instruction,
if the type is "unsigned short" (in this compiler and the ones discussed
below, "unsigned" is 32 bits, "unsigned short" 16 bits wide. Of course,
both types can contain only positive values).


Another commercial 386 compiler also handles "unsigned n" very sensibly,
but unlike the first, it avoids the division instruction with "unsigned
short n". Instead it generates a very strange sequence of 3 shifts and a
subtraction (operand order "mov dest, src" used in examples, "sar" is
arithmetic shift right, "shr" logical shift right, "shl" logical shift left,
"sbb" substract with borrow):


xor edx,edx
mov dx, [esp] ; now register edx is the value being divided by 4
mov eax,edx
sar edx,1fH
shl edx,02H
sbb eax,edx
sar eax,02H
; now eax is the result


Maximum optimization was on. I really have trouble figuring out why
the (quite reputable) compiler generated the above. I believe the
following two instructions should have been enough in this case:


movzx eax, word ptr [sp] ; zero-extend 16-bit value into 32-bit eax
shr eax, 2


Am I missing something? The third, a certain freeware compiler, handles
"unsigned short" much better than the costlier alternatives:


mov ax, [ebp+4] ; now ax = argument (different stack frame layout)
shr ax, 2 ; note: on 386, ax is the lower 16 bits of eax.
and eax, 65535


Of course, in most situations all this does not matter much. But I found
it very surprising that this rather simple code generation task,
dividing an unsigned 16-bit value by the constant 4, was handled so badly
by two out of the three C compilers I tried it on. It does not particularly
inspire one to trust the optimizer of the compiler, if speed matters.
A bad thing, because it really is much clearer and maintainable to
write n/4, if that is what you actually mean.


Another thought is that if you are using C as the target language
of a higher level language compiler, it makes sense to automatically
generate optimizations like these, if you know your target
compiler is too stupid to properly generate them itself. Besides, the
higher level compiler may know helpful things about the program that
the C compiler cannot deduce from its input, and use them to optimize.


Erkki Ruohtula / Nokia Telecommunications Oy
eru@tele.nokia.fi / P.O. Box 33 FIN-02601 Espoo, Finland
--

Return to the comp.compilers page.
Search the comp.compilers archives again.