I thought of an optimization that compilers for most CPUs could do that I think should be implemented. Let’s say you have C code like this:
if ((variable == 4) || (variable == 6)) { stuff }
Any existing compiler I know of would compile into something like this (eax is variable):
cmp eax, 4
jz label
cmp eax, 6
jz label
That’s a bad way to do it. It should be implemented more like this:
or eax, 2
cmp eax, 6
jz label
This saves one instruction, but more importantly, it saves a conditional branch. Conditional branches can be expensive on modern hardware. This will work on any similar “if” statement whose constants differ by a single bit.
Even if you must copy eax to another register first, it removes a conditional branch, which is probably a win. The situations in which to do this are more complicated and must take into account many things.
For constants that are 1 apart but not 1 bit apart, like 7 and 8, you can do:
sub eax, 7 // use dec eax in 1/2 case
test eax, 0xFFFFFFFE // this is a 3 byte opcode
jz label
This also works for 0 and -1: increment eax first.
myria
This will work not only if the two operands differ by a single bit, but in general if one of them can be obtained from the other via an OR-operation. So you could compile
if ((variable == 4) || (variable == 14))
to
or eax, 10
cmp eax, 14
jz label
and so on.
Now, can you do a similar optimization for three (or n) constants?
That doesn’t work because 12 and 6 would also pass your check. Your code effectively means:
if ((variable == 4) || (variable == 6) || (variable == 12) || (variable == 14))
3? don’t know =)
okay, so I… uhm… found an optimization for four constants! yay!
> This also works for 0 and -1: increment eax first.
I thought of an improvement on this.
if ((variable == 0) || (variable == -1))
can be implemented as:
add eax, 1
jbe label
because “jbe” really means “jump if carry or zero”.
Ack, nope, that doesn’t work >_<
A bit late but…
For values where the bit-representation are distinctive, say you check for 2, 4 and 8, wouldn’t (at compile-time) or’ing them together, then simply do “test eax, 14; 2|4|8″ (followed by jz) do the trick too? Would be hard to beat both in speed and size, I suspect. :-)
I’m not so sure this would be much of a win at the compiler level; it sounds like a developer-level optimisation to me.
Short conditional branches are almost free these days with speculative execution, and most modern CPUs have plenty of BPT and register rename slots.
The language also precludes doing anything much useful with this unless the operand happens to be in a register; it’s a very narrow case.
Hallo,
oh man.. So many Freaking Programmer (Jeloas). OK coud someone tell me about what the hell a u talking about? I Know C++ I know compiling.. But I dont get this shit!
THIS:
“or eax, 2
cmp eax, 6
jz label”
is better then this:
“cmp eax, 4
jz label
cmp eax, 6
jz label”
Ok i got it why (coz its then lower memory). But what is this???
tamlin: I don’t think so. If you do “test eax, 14″, it should also accept 6 (2|4), 10 (2|8), 12 (4|8) & 14( 2|4|8).
However, your idea would work, if the values IN eax always got different bit-representations, instead of only the values you test eax AGAINST (like 2,4,8).
> > This also works for 0 and -1: increment eax first.
>
> I thought of an improvement on this.
>
> if ((variable == 0) || (variable == -1))
>
> can be implemented as:
>
> add eax, 1
> jbe label
>
> because “jbe” really means “jump if carry or zero”.
In this case
inc eax
jbe label
bye
> That doesn’t work because 12 and 6 would also pass your check. Your
> code effectively means:
>
> if ((variable == 4) || (variable == 6) || (variable == 12) || (variable == 14))
>
> 3? don’t know =)
0 = 0000 & 0001 = 0000 -> wow – it’s dont work =\
4 = 0100 & 0001 = 0000
6 = 0110 & 0001 = 0000
12 = 1100 & 0001 = 0000
14 = 1110 & 0001 = 0000
jz out ; zero dont work :)
and eax, 1
jz label
:out
it’s correct ? =)
Owww…. 2 and 10 dont work =( sorry!!
its works with 0 2 4 6 8 10 12 14 =\\\\ waitt….. burning my soul :D
I’m back =)
> if ((variable == 4) || (variable == 6) || (variable == 12) || (variable == 14))
i make:
and eax, 5
int main() {
int i;
for (i = 0; i %s\n”, i, ((i & 0×05) == 4 ? “yes” : “no”));
getchar();
}
now is ok =P
bye
My C code out incorrect in last post…
for (i = 0; i %s\n”, i, ((i & 0×05) == 4 ? “yes” : “no”));
oww….. its sux =\
diferent..
for (i = 0; i != 0×10; i++)
printf (”%d -> %s\n”, i, ((i & 0×05) == 4 ? “yes” : “no”));
I give up =((((
if ((variable == 4) || (variable == 6) || (variable == 12) || (variable == 14))
in asm code:
and eax, 5 ; reset bits 2 and 4
cmp eax, 4 ; verify if bit 3 is set
je label