quantum_toffoli in 462.libquantum compiles to really bad code with llc

[lattner]

Bugzilla Link	914
Resolution	FIXED
Resolved on	Mar 06, 2010 14:00
Version	1.0
OS	All
Attachments	bc for function

Extended Description

The X86 backend produces significantly slower (2.5x) code for the quantum_toffoli than the C backend.

Code layout seems to be a major contributing factor, but also there are a number of 64-bit shifts that we
may be codegen'ing poorly or something.

-Chris

[lattner]

Here's a C testcase:

void test(int control1, int control2, int target, long long *reg, int *numreg)
{
int i;
for(i=0; i < numreg; i++)
if(reg[i] & ((long long) 1 << control1))
if(reg[i] & ((long long) 1 << control2))
reg[i] ^= ((long long) 1 << target);
}

[lattner]

The code layout issues have been fixed with an llvm-gcc patch.

-Chris

[lattner]

The next major issue is that instcombine is turning things like:

if (reg[i] & ((long long) 1 << control1))

into:
if ((reg[i] >> control1) & 1))

This is bad because it makes the (expensive) shift no longer be loop invariant.

Also, it would be much better to compile the code to something like this:

long long tmp1 = ((long long) 1 << target);
long long tmp2 = ((long long) 1 << control1) & ((long long) 1 << control2);
for(i=0; i < *numreg; i++)
if(reg[i] & tmp2)
reg[i] ^= tmp1;

[lattner]

Actually, it turns out the CFE is the one doing that transformation.

[lattner]

The code layout and instcombine issues are now fixed, 462.libquantum is now 16% faster with llc than
with gcc.

-Chris