Redundant comparisons are not eliminated

[jrmuizel]

Bugzilla Link	34911
Version	trunk
OS	All
CC	@sunfishcode,@rotateright

Extended Description

#include <stdlib.h>
int f(int x) {
if (x < 4)
exit(1);
if (x < 8)
exit(1);
if (x < 12)
exit(1);
if (x < 16)
exit(1);
return x + 5;
}

compiles to:

f(int): # @​f(int)
pushq %rax
cmpl $3, %edi
jle .LBB0_5
cmpl $7, %edi
jle .LBB0_5
cmpl $11, %edi
jle .LBB0_5
cmpl $15, %edi
jle .LBB0_5
addl $5, %edi
movl %edi, %eax
popq %rcx
retq
.LBB0_5:
movl $1, %edi
callq exit

compared to gcc's

f(int):
cmpl $15, %edi
jle .L7
leal 5(%rdi), %eax
ret
.L7:
subq $8, %rsp
movl $1, %edi
call exit

[jrmuizel]

FWIW, this is a reduced test case from real code: bincode-org/bincode#206

[sunfishcode]

Modifying the test slightly to manually merge the exit blocks, like this:

#include <stdlib.h>
int f(int x) {
        if (x < 4)
                goto do_exit;
        if (x < 8)
                goto do_exit;
        if (x < 12)
                goto do_exit;
        if (x < 16)
                goto do_exit;
        return x + 5;
 
do_exit:
        exit(1);
}

does cause LLVM to optimize it, in instcombine.

LLVM currently doesn't merge identical blocks until BranchFolding in CodeGen, at which point it's too late for instcombine to see it.

[jrmuizel]

FWIW, it looks like gcc does this elimination during reassoc2 pass.

[jrmuizel]

but indeed the exit(1) blocks have already been unified at that point.

[jrmuizel]

And it's gcc's pre pass that unifies the calls to exit(1)

[jrmuizel]

Daniel, can you think of sane strategy for LLVM that could be used to handle fixing this up?

[llvmbot]

This optimization is specific to functions with the following properties:

1. No return functions where you can guarantee that calling them once is "enough".
2. Readonly functions where you can prove the memory state has not changed.
3. Const functions where the inputs are the same

IE If you replace exit(1) with foo(), and foo() does not meet these properties, you can't merge these because you will change the number of calls illegally.

As for doing this algorithmically, it's tricky.

Generally, readonly and const functions can be hoisted, so it will just store and reload the result value.

That does not work for noreturn.
They can only be sunk.

It's possible to detect the set of paths that always lead to the same noreturns, and then work backwards to see if the conditions subsume each other.
IMHO, this is probably not worth it, as i'd be shocked if this case wasn't super-rare.

[llvmbot]

To be clear i mean that PRE will already take care of const/pure functions where it can (theoretically it's possible to come up with cases that can be sunk but not hoisted, but PDSE can take care of those), and that you are basically left with trying to optimize the no-returns, which i have doubts is worth it.

[llvmbot]

Also note: GCC doesn't do this as a PRE transform.

It can't, because here, as mentioned, the exits can only be sunk.

Here it performs it in tail merging.

https://github.com/gcc-mirror/gcc/blob/52ad2ea2f19be25614876f973cdc0b0574d25ad3/gcc/tree-ssa-tail-merge.c

The mechanism described for how to reverse value number is precisely that used by GVNSink.

This would fail if the functions were not noreturn.