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:
15e3d86

[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 f3acb54)

[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
}