Re: programmer optimizations?

Erkki Ruohtula <eru@tele.nokia.fi> writes:
> 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).


The type rules for (ANSI) C are such that an unsigned short in an expression
is really an int (not an unsigned int) if there are enough bits in an int
to express all the range of an unsigned short. Therefore it is appropriate
to treat the expression as possibly signed. True, there may be enough
information available to the optimizer to know that the value at this point
*must* be unsigned, but "optimizer" is a misnomer. Any optimizer can only
make the code improvements its designers were able to justify the effort
for without compromizing correctness. If your application's performance
is truly hinging upon that one code statement (very rare), then you may want
to tweak it *for that platform* or even call an assembly language module.
Don't assume that the optimization is portable, though, so wrap it with
conditional compilation directives so you can retune it for the next machine
you port to.


> 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):


again, this is a clever way of making certain it works with signed dividends
as well as unsigned.


> 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
>


This makes use of a hidden optimization, treating the divisor as an
unsigned short as well. Since both operands are an unsigned short, and
result of dividing an unsigned short by an unsigned short and then
promoting to an int will always be equivalent to the result of promoting
them to ints and THEN dividing, you can divide as unsigned shorts without
violating ANSI C requirements. The same would NOT be true of multiplication,
however, unless you were guaranteed that the result were then recast into
an unsigned short (e.g. with a *= operator), so you can see that it is
necessary to examine for each operator whether the "obvious" optimizations
are really safe to apply.


In general, when writing in a high level language (and I will take it as
a postulate that C is being used as a high level language), it is best
to express the semantics of the problem, rather than what you think the
machine will translate it to. Optimization before coding should be in
algorithm design, and instruction optimization should only be performed
after measuring where the performance bottlenecks really are.


> 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.


In this case you are using the C compiler not as an HLL, but as an
intermediate language. Since you are talking in terms of a particular
C compiler being "bad" at a particular optimization, then maybe it's
valid to "tweak" the generated C code. On the other hand, you may
get the optimizations performed the way you want through a judicious
use of cast operations, so you aren't bitten by the looser assumptions
mandated by the implicit promotion rules (e.g. casting the unsigned
shorts to unsigned ints).
--
det@phlan.sw.stratus.com
(Dave Toland)
--

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