DCE breaks by adding redundant terms

[ThomasMayerl]

Sometimes, DCE breaks by adding a redundant term.

In the following example, the if statement always evaluates to false. LLVM (14) detects that and removes the dead code:

#include <stdbool.h>

void DCEMarker0_();

void f(bool s, bool sc, bool r, bool cr, bool c) {
    if ((((cr && sc && !r) || (c && !c)) && s && (!sc == !(r || r)))) {
        DCEMarker0_();
    }
}

Now, a redundant disjunction is inserted. LLVM is not able anymore to detect the dead code:

#include <stdbool.h>

void DCEMarker0_();

void f(bool s, bool sc, bool r, bool cr, bool c) {
    if (((((cr && sc && !r) || (c && !c)) && s && (!sc == !(r || (r || 0)))))) {
        DCEMarker0_();
    }
}

This is actually a regression: It worked fine up until LLVM 12.0.1. It has been an issue since LLVM 13.

This can also be seen via the following Compiler Explorer link: https://godbolt.org/z/asrdfj6fs

(Might be related to #56711)

[rotateright]

Looks like it will reduce the same as #56711, but we can leave it open for now.

[rotateright]

This was helped by 9d218b6, but not fixed completely.

It's now virtually the same pattern as #56653, so it would be fixed by https://reviews.llvm.org/D131356.

[rotateright]

Fixed with the previously mentioned commit and: 15e3d869119289991072679f82622072818468e6

[ThomasMayerl]

I have found another case where this issue can still be reproduced:

DCE works in the following snippet:

#include <stdbool.h>

void DCEMarker0_();

void f(bool s, bool c, bool r, bool sc) {
    if (!sc && (c || sc) && (!0 == !(s || sc)) && r && !c) {
        DCEMarker0_();
    }
}

However, it does not work in the following snippet:

#include <stdbool.h>

void DCEMarker0_();

void f(bool s, bool c, bool r, bool sc) {
    if (!sc && (c || sc) && (!0 == !(s || (sc && 1))) && r && !c) {
        DCEMarker0_();
    }
}

(Compiled using -O3 and commit f3acb54c1b7b7721cea5c07f64194151dddd3c4b)

[rotateright]

It would be better to open new issues for different examples. At first glance, the new example here has more in common with #57152 than with the original example in this report - it has multiple basic blocks:

define dso_local 
void @g(i1 noundef zeroext %0, i1 noundef zeroext %1, i1 noundef zeroext %2, i1 noundef zeroext %3) local_unnamed_addr #0 {
  %5 = xor i1 %1, true
  %6 = or i1 %5, %3
  br i1 %6, label %12, label %7

7:                                                ; preds = %4
  %8 = xor i1 %2, true
  %9 = or i1 %8, %0
  %10 = or i1 %9, %1
  br i1 %10, label %12, label %11

11:                                               ; preds = %7
  tail call void (...) @DCEMarker0_() #2
  br label %12

12:                                               ; preds = %4, %7, %11
  ret void
}

[rotateright]

Also note: we do not have a general-purpose boolean logic solver, so you can create more complicated (and less realistic) code sequences that will not reduce, but it is unlikely that anyone will care enough to fix those unless it is shown in real code.