Serious tail merging pessimization

[lattner]

Bugzilla Link	1909
Resolution	FIXED
Resolved on	Feb 26, 2008 13:55
Version	2.1
OS	All

Extended Description

Consider:

#include <stdio.h>
#include <stdlib.h>

#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
void minmax(float result[8]) {
float min_x, max_x, min_y, max_y;

min_x = MIN(result[0], MIN(result[2], MIN(result[4], result[6])));
max_x = MAX(result[0], MAX(result[2], MAX(result[4], result[6])));
min_y = MIN(result[1], MIN(result[3], MIN(result[5], result[7])));
max_y = MAX(result[1], MAX(result[3], MAX(result[5], result[7])));

printf("transformed bounds: (%.2f, %.2f), (%.2f, %.2f)\n", min_x, min_y, max_x, max_y);
}

Without tail merging, we get ugly code. With tail merging, we get aweful code :) It seems to be merging lots of "single instructions", yielding code like this:

LBB1_53: # bb
ucomiss %xmm3, %xmm1
jmp LBB1_2 # bb21
LBB1_54: # bb128
ucomiss %xmm1, %xmm3
jmp LBB1_15 # bb136
LBB1_55: # bb243
ucomiss %xmm3, %xmm1
jmp LBB1_28 # bb251
LBB1_56: # bb358
ucomiss %xmm1, %xmm3
jmp LBB1_41 # bb366
LBB1_57: # bb395
ucomiss %xmm0, %xmm2
jmp LBB1_44 # bb385
LBB1_58: # bb425.bb456_crit_edge
movl %edi, %eax
jmp LBB1_52 # bb456
...

at the end of the function. If this is what is happening, it should be fixed. Saving a single instruction isn't worthwhile because we have to add the jump, and this makes code potentially slower.

[lattner]

Another question is why llvm isn't using minss/maxss as aggressively as GCC. We both generate minss/maxss in -ffast-math mode, but only gcc generates them without -ffast-math. I am inclined to think that this is a GCC bug though.

[llvmbot]

BTW, icc also generates minss / maxss without -ffast-math. Perhaps we need to be bug compatible?

[llvmbot]

Tail merging issue fixed:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20080218/058491.html

[lattner]

I'm fine with matching these as minss/maxss, dale what do you think?

[llvmbot]

It should be all right as long as you're careful about what rearrangements you do before producing min/max (in particular make sure "unordered" is handled correctly, and min/max operators must not be treated as commutative). The comment in gcc says:

;; These versions of the min/max patterns implement exactly the operations
;; min = (op1 < op2 ? op1 : op2)
;; max = (!(op1 < op2) ? op1 : op2)
;; Their operands are not commutative, and thus they may be used in the
;; presence of -0.0 and NaN.

[lattner]

rdar://4764697 - mins[sd]/maxs[sd] marked commutable

[llvmbot]

Ok. I'll close this bug then.

[llvmbot]

Now that I have gotten around to looking at the tail merging issue, I don't think it was broken, and Evan's change has demonstrably made things worse. The code for this was 508 bytes and is now 558.
When we have code like
LBB1_55: # bb243
ucomiss %xmm3, %xmm1
jmp LBB1_28 # bb251
the alternative would be
ucomiss %xmm3, %xmm1
ja LBB1_61 # bb256 <<< contents of bb251
jmp LBB1_29 # bb251
i.e. there is already an unconditional branch there, so you are not adding a new one. The optimization is profitable.
I propose to back out this patch, unless somebody can point to a way the new code is actually better.

[llvmbot]

LBB1_28: # bb251
ja LBB1_61 # bb256

LBB1_55: # bb243
ucomiss %xmm3, %xmm1
jmp LBB1_28 # bb251

I don't think this is a worthwhile optimization unless only cares about code size. This will end up taking two jumps when the condition is true, one when it's false.

    ucomiss %xmm3, %xmm1
    ja      LBB1_61 # bb256         <<< contents of bb251
    jmp     LBB1_29 # bb251

It takes a single jump regardless whether the condition is true.

[llvmbot]

Sure, tail merging can cause extra unconditional jumps to be executed; that's inherent in the optimization. On the other side, unconditional jumps are very fast on modern architectures, sometimes zero cycles, and one fewer page fault due to size reduction makes up for an awful lot. This patch causes a measurable 10% size increase, which is a lot. I think we need some evidence from timings that we're actually gaining something before we do that.

[llvmbot]

Using -stats, I see number of machine instrs goes from 147 to 152. That's 5 instructions out of 147. I think the 10% increase you see is rounded to instruction page size, that's not something we can control.

One x86 the execution time cost of the extra branch might not be significant (but seems noticeable on WebKit sunspider). I would guess it can be an issue on something like ARM. Without proper cost model in place, I'd err on the side of caution for lean towards optimization for speed rather than size.

[llvmbot]

Yes, it's only 5 instructions, but for purposes of the paging effect it's the number of bytes that counts. The fact that the byte size delta is proportionally greater than the instruction count delta seems to be because conditional branches are bigger than unconditional (it has nothing to do with page size). The old code had 30 conditional and 20 unconditional; the current code 42 conditional and 13 unconditional. This is generally applicable on x86, although not elsewhere.

If you want to "optimize for speed instead of space" we should disable tail merging altogether; its generated code is often slower in terms of number of instructions executed. The theory around here is that optimizing for space does optimize for speed by reducing page faults, cache hits, memory footprint, and there's a good deal of evidence that this is right. It often will not look that way in microbenchmarks however.

[llvmbot]

"If you want to "optimize for speed instead of space" we should disable tail merging altogether;"

I hear your arguments. But I don't think it's that black and white a decision. We all know the benefit of reducing code size. But there is strong arguments for not inserting unnecessary branches. The point is what's the right trade off? To me, tail merging goes to extreme to save one instruction is just too much.

BTW there are other codegen problems.

LBB1_28: # bb302
ucomiss %xmm1, %xmm0
ja LBB1_30 # bb341
LBB1_29: # bb333
movl %edx, %esi
LBB1_30: # bb341
ucomiss %xmm0, %xmm1
movss (%esi), %xmm6
ja LBB1_51 # bb358

LBB1_29 can be eliminated with the help of if-conversion.

I also modified the test case by changing MIN / MAX definition to avoid generating min / max instructions to examine icc output.
#define MIN(a,b) ((a)!=(b)?(a):(b))
#define MAX(a,b) ((a)==(b)?(a):(b))

icc generates significantly more compact code compared against llvm.

We are doing horrible stuff like this:
ucomiss %xmm1, %xmm3
sete %cl
setnp %dl
testb %cl, %dl
jne LBB1_11 # bb141

Also, why is it we are generating 45 ucomiss vs. 28 by icc?

Also note icc seems to make an effort to avoid jumping backwards. Don't know if it's intentional.

[llvmbot]

I know there are other codegen problems, I was only talking about tail merging.

The extra ucomiss are probably because taildup creates them, they get different registers in different blocks, and tail merge cannot put them back together. Turning off taildup fixes that issue, but the code is otherwise horrible.

[llvmbot]

Ok, Dale. Since you own tail merging and this is obviously a corner case, I'll let you decide what to do. But please do the followings:

1. File radars on various codegen issues.
2. Do we need to do tail merging before register allocation? Please file a radar / bugzilla.
3. Please add a mechanism to throttle tail merging. It's highly likely the cost of branches differ on the various targets that we care about.

Among the benchmarks that we regularly track, Sunspider is most likely to be affected by this. I'll let you know if I see any performance impact from this. Thanks.