Created attachment 25330 [details] The file demonstrates a missing optimization in instcombine The code bellow is being optimized by instcombine if we put and/or instead of 'select': lor.lhs.false: ; preds = %for.body6 %or.cond87.not = xor i1 %or.cond, true ;%or.cond88 = or i1 %or.cond87.not, %cmp16 %or.cond88 = select i1 %or.cond87.not, i1 true, i1 %cmp16 %or.cond88.not = xor i1 %or.cond88, true ;%or.cond89 = and i1 %or.cond88.not, %cmp28 %or.cond89 = select i1 %or.cond88.not, i1 %cmp28, i1 false %or.cond89.not = xor i1 %or.cond89, true ;%or.cond92 = or i1 %or.cond88, %cmp28 %or.cond92 = select i1 %or.cond88, i1 true, i1 %cmp28 ;%or.cond93 = and i1 %or.cond89.not, %or.cond92 %or.cond93 = select i1 %or.cond89.not, i1 %or.cond92, i1 false There are also some changes were done in visitSelectInst() if (match(TrueVal, m_One()) && impliesPoison(FalseVal, CondVal)) { // Change: A = select B, true, C --> A = or B, C return BinaryOperator::CreateOr(CondVal, FalseVal); } IsSafeToConvert() was replaced with impliesPoison()
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.
(In reply to Juneyoung Lee from comment #6) > > ; (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.