Dead Code Elimination Regression at -O3 (trunk vs 13.0.0)

[Quuxplusone]

Bugzilla Link	PR52525
Status	NEW
Importance	P enhancement
Reported by	Theodoros Theodoridis (theodort@inf.ethz.ch)
Reported on	2021-11-16 11:03:44 -0800
Last modified on	2021-11-19 03:56:06 -0800
Version	trunk
Hardware	PC Linux
CC	florian_hahn@apple.com, htmldeveloper@gmail.com, llvm-bugs@lists.llvm.org, spatel+llvm@rotateright.com, theodort@inf.ethz.ch
Fixed by commit(s)
Attachments
Blocks
Blocked by
See also	PR52260

cat case.c
void foo(void);

static char a(char l) { return l; }
static char c(char l) { return l == 0; }

static int b, d;
static int *g;

int main() {
  if (g) {
    unsigned char f = b;
    char n = f >> 2;
    if (c(n)) {
      d = a(b) || d;
    } else if (!b)
      foo();
  }
  g = &b;
}

trunk cannot eliminate the call to foo but 13.0.0 can:

clang-13.0.0 -O3 -S -o /dev/stdout case.c
main:                                   # @main
    .cfi_startproc
# %bb.0:
    cmpq    $0, g(%rip)
    je  .LBB0_3
# %bb.1:
    movl    b(%rip), %eax
    testb   $-4, %al
    je  .LBB0_2
.LBB0_3:
    movq    $b, g(%rip)
    xorl    %eax, %eax
    retq
.LBB0_2:
    testb   %al, %al
    setne   %al
    cmpl    $0, d(%rip)
    setne   %cl
    orb %al, %cl
    movzbl  %cl, %eax
    movl    %eax, d(%rip)
    movq    $b, g(%rip)
    xorl    %eax, %eax
    retq
.Lfunc_end0:

clang-trunk -O3 -S -o /dev/stdout case.c
main:                                   # @main
    .cfi_startproc
# %bb.0:
    pushq   %rax
    .cfi_def_cfa_offset 16
    cmpq    $0, g(%rip)
    je  .LBB0_5
# %bb.1:
    movl    b(%rip), %eax
    cmpb    $3, %al
    jbe .LBB0_2
# %bb.3:
    testl   %eax, %eax
    je  .LBB0_4
.LBB0_5:
    movq    $b, g(%rip)
    xorl    %eax, %eax
    popq    %rcx
    .cfi_def_cfa_offset 8
    retq
.LBB0_2:
    .cfi_def_cfa_offset 16
    testb   %al, %al
    setne   %al
    cmpl    $0, d(%rip)
    setne   %cl
    orb %al, %cl
    movzbl  %cl, %eax
    movl    %eax, d(%rip)
    movq    $b, g(%rip)
    xorl    %eax, %eax
    popq    %rcx
    .cfi_def_cfa_offset 8
    retq
.LBB0_4:
    .cfi_def_cfa_offset 16
    callq   foo
    movq    $b, g(%rip)
    xorl    %eax, %eax
    popq    %rcx
    .cfi_def_cfa_offset 8
    retq
.Lfunc_end0:

clang-trunk -v
clang version 14.0.0 (https://github.com/llvm/llvm-project.git
1ee32055ea1dd4db70d1939cbd4f5105c2dce160)
Target: x86_64-unknown-linux-gnu
Thread model: posix

Started with https://github.com/llvm/llvm-
project/commit/f32c0fe8e50534f4210d878b9a1420793860c567

[Quuxplusone]

I'm not sure which pass should be responsible for this (instcombine and correlated-propagation are candidates), but here's a reduction - the 2nd compare is implied (false) by the first compare:

https://alive2.llvm.org/ce/z/_fmJp9

[Quuxplusone]

Posting the IR reduction with some notes here. Also, I was just reminded about
the "constraint-elimination" pass, so cc'ing Florian in case this example is a
candidate for that pass.

declare void @use(i8)

define i1 @src(i32 %x) {
entry:
  %tx = trunc i32 %x to i8
  %ugt = icmp ugt i8 %tx, 3
  br i1 %ugt, label %if, label %then

then:
  call void @use(i8 %tx) ; this prevents a transform in instcombine
  ret i1 false

if:
  %eq = icmp eq i32 %x, 0 ; the result is always 'false' because (x&255) u> 3
  ret i1 %eq
}

[Quuxplusone]

This is an interesting example!

As for the constraint-elimination pass, decomposition/looking-through trunc is not yet implemented. It is doable, but we need to be careful about the exact predicate that's used.

But for the example, we only need to reason about constant ranges, so we could also handle this in "correlated-propagation" (as mentioned) or in (IP)SCCP. The latter would require PredicateInfo to also add predicates for the condition in the wider type.