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

[llvmbot]

Bugzilla Link	52592
Version	trunk
OS	Linux
Reporter	LLVM Bugzilla Contributor
CC	@aeubanks

Extended Description

cat case.c
void bar(void);
void foo(void);

static char b = 1;
static int c;

static int d(int e) { return e; }

int main() {
b = 0;
bar();
c = d(2048);
if (!((((0 == c || b) && 1) ^ 2)% 5))
{
d(0);
foo();
}
}

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:

pushq	%rax
.cfi_def_cfa_offset 16
callq	bar
xorl	%eax, %eax
popq	%rcx
.cfi_def_cfa_offset 8
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
movb	$1, b(%rip)
callq	bar
movzbl	b(%rip), %eax
xorl	$1, %eax
orl	$2, %eax
imull	$-858993459, %eax, %eax         # imm = 0xCCCCCCCD
cmpl	$858993459, %eax                # imm = 0x33333333
jbe	.LBB0_1

%bb.2:

xorl	%eax, %eax
popq	%rcx
.cfi_def_cfa_offset 8
retq

.LBB0_1:
.cfi_def_cfa_offset 16
callq foo
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 38ed1db)
Target: x86_64-unknown-linux-gnu
Thread model: posix

Started with e7249e4

[gandhi56]

I believe the error is coming from a load instruction which loads the value of b

[gandhi56]

Source code:

    15 // RUN: %clang_cc1 -triple x86_64-unknown-linux_gnu -O3 -S -emit-llvm -o - %s | FileCheck %s
    14 
    13 void bar(void);
    12 void foo(void);
    11 
    10 static char b = 1;
     9 
     8 // CHECK-LABEL: define {{.*}} i32 @main()
     7 int main() {
     6     b = 0;
     5     bar();
     4     if (!((b ^ 2)% 5))
     3     {
     2         // CHECK-NOT: call {{.*}} @foo()
     1         foo();
   16  
     1     }
     2 
     3 }

IR after SimplifyCFG:

*** IR Dump After SimplifyCFGPass on main ***
; Function Attrs: nounwind uwtable
define dso_local i32 @main() local_unnamed_addr #0 {
entry:
  store i1 true, i1* @b, align 1
  tail call void @bar() #2
  %.b = load i1, i1* @b, align 1
  %0 = zext i1 %.b to i32
  %xor = xor i32 %0, 3
  %rem = urem i32 %xor, 5
  %tobool.not = icmp eq i32 %rem, 0
  br i1 %tobool.not, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  tail call void @foo() #2
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  ret i32 0
}

IR after SimplifyCFG, when line 5 from source code is removed:

*** IR Dump After SimplifyCFGPass on main ***
; Function Attrs: mustprogress nofree norecurse nosync nounwind readnone uwtable willreturn
define dso_local i32 @main() local_unnamed_addr #0 {
entry:
  ret i32 0
}

I suppose LLVM expects the value of b to change in bar(). If that is the case, then we do not know for sure if the if condition will hold true or not.

[gandhi56]

@aeubanks comments?

[nikic]

Could probably be fixed by making xor range inference more precise, though that's a bit tricky.

[gandhi56]

@nikic Where is the xor range inference implemented? Is that the only way to fix this issue?

[nikic]

@gandhi56 You can find the implementation here:

llvm-project/llvm/lib/IR/ConstantRange.cpp

Line 1401 in 127d955

ConstantRange ConstantRange::binaryXor(const ConstantRange &Other) const {

The actual fold would get performed by the CorrelatedValuePropagation (CVP) pass.

[rotateright]

Here's an alternative proposal for InstSimplify:
https://reviews.llvm.org/D116616

[rotateright]

Fixed after:
6bd127b