powerpc64le tail recursion miscompilation

[q66]

The following code enters infinite loop:

#include <stdio.h>

/*
0 100 1
100 0 0
0 100 1
100 0 0
0 100 1
100 0 0
0 100 1
100 0 0
0 100 1
100 0 0
0 100 1
...
*/

static unsigned int testfunc(unsigned int a, unsigned int b) {
    printf("%u %u %d\n", a, b, b > a);
    if (b > a) {
        return testfunc(b, a);
    }
    return a - b;
}

int main(void) {
    printf("%u\n", testfunc(0, 100));
    return 0;
}

Confirmed on ppc64le with Clang 12 and 15 by me and Git by @MaskRay. Confirmed it does not happen on at least x86_64, aarch64 and riscv64. Appears to be unrelated to anything other than the architecture, so it seems to be a codegen backend bug.

[llvmbot]

@llvm/issue-subscribers-backend-powerpc

[q66]

I checked the emitted assembly:

	.text
	.abiversion 2
	.file	"test.c"
	.globl	main                            # -- Begin function main
	.p2align	4
	.type	main,@function
main:                                   # @main
.Lfunc_begin0:
	.cfi_startproc
# %bb.0:
	li 3, 100
	li 4, 0
	cmplw	4, 3
	.p2align	4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
	mr	5, 4
	mr	4, 3
	mr	3, 5
	blt	0, .LBB0_1
# %bb.2:
	li 3, 0
	blr
	.long	0
	.quad	0
.Lfunc_end0:
	.size	main, .Lfunc_end0-.Lfunc_begin0
	.cfi_endproc
                                        # -- End function
	.ident	"clang version 12.0.1"
	.section	".note.GNU-stack","",@progbits
	.addrsig

The relevant part appears to be this:

	li 3, 100
	li 4, 0
	cmplw	4, 3
	.p2align	4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
	mr	5, 4
	mr	4, 3
	mr	3, 5
	blt	0, .LBB0_1

so it loads the values into r3 and r4 and does a comparison; then it performs a swap (r5 = r4; r4 = r3; r3 = r5) and jumps to label based on result of comparison; however, it does not compare again, so it's just bound to keep swapping the register values forever, if i understand this correctly

the label should probably be before the compare?

also, this only happens at -O2 and higher opt levels

[q66]

code emitted from gcc:

	li 10,100
	li 9,0
	.p2align 5
.L2:
	cmplw 0,10,9
	mr 8,9
	mr 9,10
	mr 10,8
	bgt 0,.L2

indeed places the compare after the label

[MaskRay]

This is a bug in https://reviews.llvm.org/D38236 ([PowerPC] eliminate partially redundant compare instruction): when MBB1 == &MBB2, there may be only one compare instruction in the loop. The code will lift the compare instruction to the preheader, failing to account for the change of the compare result in a tail call, leading to a miscompile.

Patch: https://reviews.llvm.org/D149030

[q66]

generated code with patch:

.Lfunc_begin0:
        .cfi_startproc
# %bb.0:
        li 3, 100
        li 4, 0
        .p2align        5
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        mr      5, 4
        cmplw   3, 4
        mr      4, 3
        mr      3, 5
        bgt     0, .LBB0_1
# %bb.2:
        li 3, 0
        blr

i guess that looks fine? the only difference from gcc is that the temporary save part of the swap is done before the cmp, but that should not matter as far as i can tell, otherwise it is essentially identical