Useless code generation with code that has no side effects

[Quuxplusone]

Bugzilla Link	PR41907
Status	NEW
Importance	P normal
Reported by	Gabriel Ravier (gabravier@gmail.com)
Reported on	2019-05-16 06:58:49 -0700
Last modified on	2019-05-20 16:22:25 -0700
Version	trunk
Hardware	PC Linux
CC	gabravier@gmail.com, llvm-bugs@lists.llvm.org, llvm@meinersbur.de
Fixed by commit(s)
Attachments	badOptimize.7z (967 bytes, application/x-7z-compressed)
Blocks
Blocked by
See also

Created attachment 21954
Archive containing the file necessary to reproduce this bug and the relevant
generated assembly files

When compiling the attached code with -O3, the optimizer fails to recognize
that the code should be simplified a simple jump to "fn", and instead generates
useless code that needs not be present for the code to work. It also generates
some very weird code, such as

.LBB0_3:                                # =>This Inner Loop Header: Depth=1
        cmp     ecx, eax
        jle     .LBB0_4
# %bb.9:                                #   in Loop: Header=BB0_3 Depth=1
        cmp     ecx, eax
        jle     .LBB0_10

This strange code generation remains when adding a statement that forces the
code to have a side effect, such as "return d;" at the end of the code.

This is entirely redundant and the second part of the code should be optimized
out.

(%bb.9 being a comment, no code jumps there)

Attached is a 7z archive containing :

- The source file
- The generated assembly file "test.s" when compiling with "clang -S test.c -O3
-masm=intel -m32 -o test32.s" and "clang -S test.c -O3 -masm=intel -o test64.s"
with "x86_64-unknown-linux-gnu" as the target (for which clang was built on my
computer) and with clang 8.0.0, from Fedora 30

PS : I originally found this while trying to analyse
http://www.ioccc.org/1984/laman/laman.c using Godbolt, as seen here :
https://godbolt.org/z/1M_cJi. I was also using trunk, which is why I'm filing
this under trunk ; the bug is reproducible there (note that GCC and ICC
(correctly ?) convert the entire code to a call to fn).

PPS : The weird comparison duplication disappears when removing the duplicate
loop, but the loop itself remains

[Quuxplusone]

Attached badOptimize.7z (967 bytes, application/x-7z-compressed): Archive containing the file necessary to reproduce this bug and the relevant generated assembly files

[Quuxplusone]

PPPS : Removing the while loop (leaving the code inside intact) makes it so that the optimizer converts the entire function to a jump to "fn"

[Quuxplusone]

Code from the file:

void f()
{
    int d = 0, O = 0, g = fn();
    while (d <= g)
    {
        ++O;
        for (int f = 0; f < O && d <= g; ++f)
            ++d;
        for (int f = 0; f < O && d <= g; ++f)
            ++d;
    }
}

C/C++'s semantics allow the compiler to assume that a loop without side-effects
will terminate. But this has not been defined for LLVM-IR. That is, the
LoopDeletion pass currently requires the loop to terminate.

Relevant discussion: https://lists.llvm.org/pipermail/llvm-dev/2017-
September/117854.html

[Quuxplusone]

Yeah, I understand that (I was pretty sure it was related to this). However, the optimizer still misses possible optimizations, such as the rather stupid double identical compare (which was the original reason I'd wanted to file this bug, as I only removed side effects while trying to narrow down the cause of this bug).

[Quuxplusone]

Having look over the output of -mllvm -print-after-all, looks like the "d <= g" condition of the while and inner for-loops are moved next to each other by LoopRotate, but then never combined. Could be a job for JumpThreading. At the time JumpThreading runs, the value of 'd' look different though, due to I PHINode that is later removed by PHIElimination.