I'm not sure if this is the entire problem, but we don't have a poison-safe DeMorgan fold for 'not' with 'not' op:

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

; ~(~x | y) --> x & ~y
define i1 @​src(i1 %x, i1 %y) {
%notx = xor i1 %x, true
%or = select i1 %notx, i1 true, i1 %y
%notor = xor i1 %or, true
ret i1 %notor
}

define i1 @​tgt(i1 %x, i1 %y) {
%noty = xor i1 %y, true
%and = select i1 %x, i1 %noty, i1 false
ret i1 %and
}

Can you see if there are still problems after this patch:
https://reviews.llvm.org/rGbc72baa04789

The patch changes the block, but does not optimize it. After you patch I got:

lor.lhs.false: ; preds = %for.body6
%or.cond87.not.demorgan = and i1 %cmp12, %cmp13
%or.cond87.not = xor i1 %or.cond87.not.demorgan, true
%or.cond88 = select i1 %or.cond87.not, i1 true, i1 %cmp16
%cmp28.not = xor i1 %cmp28, true
%or.cond89.not = select i1 %or.cond88, i1 true, i1 %cmp28.not
%or.cond92 = select i1 %or.cond88, i1 true, i1 %cmp28
%or.cond93 = select i1 %or.cond89.not, i1 %or.cond92, i1 false
br i1 %or.cond93, label %if.end, label %if.then

Thanks. So at least one more missing bool logic fold:

; (x || y) && (x || !y) --> x

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

This one should be in instsimplify...

I just discovered (but haven't read it all yet):
https://aqjune.github.io/posts/2021-10-4.the-select-story.html

cc'ing Juneyoung. I am assuming we just want to add some more logic folds for 'select' to get the same optimizations as with 'and'/'or'/'xor', but let me know if you see a more general solution.

; (x || y) && (x || !y) --> x

Adding this pattern seems like the easiest and fastest solution to me.

Another solution that I can think of is to attach noundef to everywhere, but it will certainly take some time.

; (x || y) && (x || !y) --> x

Adding this pattern seems like the easiest and fastest solution to me.

Ok - I'll work on it.

Interestingly, we also don't have the corresponding bitwise logic fold in -instsimplify:

define i1 @​bitwise_logic(i1 %x, i1 %y) {
%ynot = xor i1 %y, -1
%xory = or i1 %x, %y
%xorynot = or i1 %ynot, %x
%and = and i1 %xory, %xorynot
ret i1 %and
}

This is only caught inside -instcombine via SimplifyUsingDistributiveLaws().

Added the bitwise logic fold:
https://reviews.llvm.org/rGe36d351d19b1

Then needed to add some infrastructure:
https://reviews.llvm.org/rG519752062c60

And then the select fold:
https://reviews.llvm.org/rGfdbf2bb4eed1

So the IR in the attached file now becomes:
%or.cond87.not.demorgan = and i1 %cmp12, %cmp13
%or.cond87.not = xor i1 %or.cond87.not.demorgan, true
%or.cond88 = select i1 %or.cond87.not, i1 true, i1 %cmp16
br i1 %or.cond88, label %if.end, label %if.then

!(x & y) || z

Is there still more that we can do?

Nope, the resulting expression ('!(x & y) || z') is obviously the simplest form.

I could reproduce the output using the latest LLVM as well.

Resolving - if we are still missing logical and/or (select) folds, please file bugs. Thanks!

It is resolved! Thank you.