[InstCombine] reassociate bitwise logic chains based on uses

[spatel]

Summary

(X op Y) op Z --> (Y op Z) op X

This isn't a complete solution (see TODO tests for possible refinements), but it shows some nice wins and doesn't seem to cause any harm. I think the most potential danger is from conflicting with other folds and causing an infinite loop - that's the reason for avoiding patterns with constant operands.

Alternatively, we could try this in the reassociate pass, but we would not immediately see all of the logic folds that instcombine provides. I also looked at improving ValueTracking's isImpliedCondition() (and we should still add some enhancements there), but that would not work in general for bitwise logic reduction.

The tests that reduce completely to 0/-1 are motivated by issue #56653.

[spatel]

Ping.

[spatel]

Presumably, these are fuzzer bugs, but some more issues that should be solved with this patch:
https://github.com/llvm/llvm-project/issues/57028
https://github.com/llvm/llvm-project/issues/57120

They are not identical patterns, but have the shared trait of a single value with multiple uses in the logic chain.

[bcl5980]

In D131356#3725827, @spatel wrote:

Presumably, these are fuzzer bugs, but some more issues that should be solved with this patch:
https://github.com/llvm/llvm-project/issues/57028
https://github.com/llvm/llvm-project/issues/57120

They are not identical patterns, but have the shared trait of a single value with multiple uses in the logic chain.

Maybe we can run ipsccp until no changed(Similar to Instcombine) to fix all these tickets. like:

unsigned Iteration = 0;
bool MadeChanges = false;
while (runIPSCCP(M, DL, GetTLI, getAnalysis)) {
  MadeChanges = true;
}

if (!MadeChanges)
  return PreservedAnalyses::all();

[spatel]

In D131356#3726615, @bcl5980 wrote:

Maybe we can run ipsccp until no changed(Similar to Instcombine) to fix all these tickets. like:

I'm not familiar with ipsccp, and I don't know what impact running that pass to fix-point would have on compile-time, but if that works, do you want to make a patch?

It doesn't look like this patch would have any noticeable impact on compile-time:
https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&remote=rotateright

[fhahn]

In D131356#3727010, @spatel wrote:

In D131356#3726615, @bcl5980 wrote:

Maybe we can run ipsccp until no changed(Similar to Instcombine) to fix all these tickets. like:

I'm not familiar with ipsccp, and I don't know what impact running that pass to fix-point would have on compile-time, but if that works, do you want to make a patch?

IPSCCP/SCCP should iterate until they reach a fixed-point already. If running runIPSCCP(M, DL, GetTLI, getAnalysis) multiple times improves the result, then there's likely a dependency missing in the solver.

[bcl5980]

In D131356#3727010, @spatel wrote:

In D131356#3726615, @bcl5980 wrote:

Maybe we can run ipsccp until no changed(Similar to Instcombine) to fix all these tickets. like:

I'm not familiar with ipsccp, and I don't know what impact running that pass to fix-point would have on compile-time, but if that works, do you want to make a patch?

It doesn't look like this patch would have any noticeable impact on compile-time:
https://llvm-compile-time-tracker.com/index.php?config=NewPM-O3&stat=instructions&remote=rotateright

Sorry for the confused comments. This patch is OK for me. It helps on the cases with non-bool types that ipsccp can't tough. Put them to reassociate pass could avoid the potential dead loop in instcombine, but for now reassociate pass still have the history code don't work for i1 types.
And I'm also trying to fix on ipsccp to eliminate all similar issues with i1 types.

[bcl5980]

In D131356#3727022, @fhahn wrote:

In D131356#3727010, @spatel wrote:

In D131356#3726615, @bcl5980 wrote:

Maybe we can run ipsccp until no changed(Similar to Instcombine) to fix all these tickets. like:

I'm not familiar with ipsccp, and I don't know what impact running that pass to fix-point would have on compile-time, but if that works, do you want to make a patch?

IPSCCP/SCCP should iterate until they reach a fixed-point already. If running runIPSCCP(M, DL, GetTLI, getAnalysis) multiple times improves the result, then there's likely a dependency missing in the solver.

This is a very simple case that run once runIPSCCP can't get fix-point result. https://alive2.llvm.org/ce/z/o6rkTy
I create a issue here https://github.com/llvm/llvm-project/issues/57186
Maybe we can discuss there to make this patch's review more clean.

[spatel]

In D131356#3727970, @bcl5980 wrote:

Sorry for the confused comments. This patch is OK for me. It helps on the cases with non-bool types that ipsccp can't tough. Put them to reassociate pass could avoid the potential dead loop in instcombine, but for now reassociate pass still have the history code don't work for i1 types.
And I'm also trying to fix on ipsccp to eliminate all similar issues with i1 types.

Improving ipsccp seems good independently. I also looked at trying to solve the i1 pattern as a special-case using isImpliedCondition() from ValueTracking, but then I tried this instcombine idea, and it worked on the motivating cases plus others.

If there are no objections, would someone approve the patch formally?

[bcl5980]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op1, m_OneUse(m_Not(m_OneUse(
       return BinaryOperator::Create(
           FlippedOpcode, Builder.CreateBinOp(Opcode, B, Builder.CreateNot(C)),
           X);
   }
 
   return nullptr;
 }
 
+/// Try to reassociate a pair of binops so that values with one use only are
+/// part of the same instruction. This may enable folds that are limited with
+/// multi-use restrictions and makes it more likely to match other patterns that
+/// are looking for a common operand.
+static Instruction *reassociateForUses(BinaryOperator &BO,
+                                       InstCombinerImpl::BuilderTy &Builder) {
+  Instruction::BinaryOps Opcode = BO.getOpcode();
+  Value *X, *Y, *Z;
+  if (match(&BO, m_c_BinOp(Opcode,
+                           m_OneUse(m_c_BinOp(Opcode, m_Value(X),
+                                              m_OneUse(m_Value(Y)))),
+                           m_OneUse(m_Value(Z))))) {
+    // (X op Y) op Z --> (Y op Z) op X
+    if (!isa<Constant>(X) && !isa<Constant>(Y) && !isa<Constant>(Z) &&
+        !X->hasOneUse()) {
+      Value *YZ = Builder.CreateBinOp(Opcode, Y, Z);
+      return BinaryOperator::Create(Opcode, YZ, X);
+    }
+  }
+
+  return nullptr;
+}
+
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
 Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
   Type *Ty = I.getType();
 
   if (Value *V = simplifyAndInst(I.getOperand(0), I.getOperand(1),
                                  SQ.getWithInstruction(&I)))
if (sinkNotIntoOtherHandOfAndOrOr(I))
     return &I;
 
   // An and recurrence w/loop invariant step is equivelent to (and start, step)
   PHINode *PN = nullptr;
   Value *Start = nullptr, *Step = nullptr;
   if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN))
     return replaceInstUsesWith(I, Builder.CreateAnd(Start, Step));
 
+  if (Instruction *R = reassociateForUses(I, Builder))
+    return R;
+
   return nullptr;
 }
 
 Instruction *InstCombinerImpl::matchBSwapOrBitReverse(Instruction &I,
                                                       bool MatchBSwaps,
                                                       bool MatchBitReversals) {
   SmallVector<Instruction *, 4> Insts;
   if (!recognizeBSwapOrBitReverseIdiom(&I, MatchBSwaps, MatchBitReversals,
if (match(&I, m_c_Or(m_OneUse(m_And(m_Value(A), m_Value(B))),
     // (? | D) | (A & B) -> (? | (A & B)) | D
     // (? | D) | (A & B) -> (? | (A & B)) | D
     if (match(C, m_OneUse(m_c_And(m_Specific(A), m_Value()))) ||
         match(C, m_OneUse(m_c_And(m_Specific(B), m_Value()))))
       return BinaryOperator::CreateOr(
           Builder.CreateOr(C, Builder.CreateAnd(A, B)), D);
   }
 
+  if (Instruction *R = reassociateForUses(I, Builder))
+    return R;
+
   return nullptr;
 }
 
 /// A ^ B can be specified using other logic ops in a variety of patterns. We
 /// can fold these early and efficiently by morphing an existing instruction.
 static Instruction *foldXorToXor(BinaryOperator &I,
                                  InstCombiner::BuilderTy &Builder) {
   assert(I.getOpcode() == Instruction::Xor);
Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) {
   // Just like we do in other places, we completely avoid the fold
   // for constantexprs, at least to avoid endless combine loop.
   if (match(&I, m_c_Xor(m_OneUse(m_Xor(m_CombineAnd(m_Value(X),
                                                     m_Unless(m_ConstantExpr())),
                                        m_ImmConstant(C1))),
                         m_Value(Y))))
     return BinaryOperator::CreateXor(Builder.CreateXor(X, Y), C1);
 
+  if (Instruction *R = reassociateForUses(I, Builder))
+    return R;
+
   return nullptr;
 }

llvm/test/Transforms/InstCombine/and-or-icmps.ll

 ; CHECK-NEXT:    [[L7:%.*]] = load i16, i16* [[A8]], align 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i16 [[L7]], -1
 ; CHECK-NEXT:    [[B11:%.*]] = zext i1 [[TMP1]] to i16
 ; CHECK-NEXT:    [[C10:%.*]] = icmp ugt i16 [[L7]], [[B11]]
 ; CHECK-NEXT:    [[C5:%.*]] = icmp slt i16 [[L7]], 1
 ; CHECK-NEXT:    [[C7:%.*]] = icmp slt i16 [[L7]], 0
 ; CHECK-NEXT:    [[B15:%.*]] = xor i1 [[C7]], [[C10]]
 ; CHECK-NEXT:    [[C6:%.*]] = xor i1 [[B15]], true
-; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[C10]], [[C5]]
-; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[C6]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[C5]], [[C6]]
+; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[C10]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[C10]], true
 ; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = sext i1 [[C3]] to i64
 ; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP4]]
 ; CHECK-NEXT:    store i16 [[L7]], i16* undef, align 2
 ; CHECK-NEXT:    store i1 [[C18]], i1* undef, align 1
 ; CHECK-NEXT:    store i1* [[G26]], i1** undef, align 8
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/InstCombine/and-or-not.ll

;
   %or1 = or i32 %nota, %notb
   %or2 = or i32 %b, %a
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 define i4 @simplify_or_common_op_commute0(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_or_common_op_commute0(
-; CHECK-NEXT:    [[XY:%.*]] = and i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = and i4 [[XY]], [[Z:%.*]]
-; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
-; CHECK-NEXT:    [[R:%.*]] = or i4 [[NOT_XYZ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    ret i4 -1
 ;
   %xy = and i4 %x, %y
   %xyz = and i4 %xy, %z
   %not_xyz = xor i4 %xyz, -1
   %r = or i4 %not_xyz, %x
   ret i4 %r
 }
 
 define i4 @simplify_or_common_op_commute1(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_or_common_op_commute1(
-; CHECK-NEXT:    [[XY:%.*]] = and i4 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = and i4 [[XY]], [[Z:%.*]]
-; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
-; CHECK-NEXT:    [[R:%.*]] = or i4 [[NOT_XYZ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    ret i4 -1
 ;
   %xy = and i4 %y, %x
   %xyz = and i4 %xy, %z
   %not_xyz = xor i4 %xyz, -1
   %r = or i4 %not_xyz, %x
   ret i4 %r
 }
 
+; The common operand may bubble through multiple instructions.
+
 define i4 @simplify_or_common_op_commute2(i4 %x, i4 %y, i4 %p, i4 %q)  {
 ; CHECK-LABEL: @simplify_or_common_op_commute2(
-; CHECK-NEXT:    [[Z:%.*]] = mul i4 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[XY:%.*]] = and i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = and i4 [[Z]], [[XY]]
-; CHECK-NEXT:    [[XYZQ:%.*]] = and i4 [[XYZ]], [[Q:%.*]]
-; CHECK-NEXT:    [[NOT_XYZQ:%.*]] = xor i4 [[XYZQ]], -1
-; CHECK-NEXT:    [[R:%.*]] = or i4 [[NOT_XYZQ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    ret i4 -1
 ;
   %z = mul i4 %p, %p ; thwart complexity-based canonicalization
   %xy = and i4 %x, %y
   %xyz = and i4 %z, %xy
   %xyzq = and i4 %xyz, %q
   %not_xyzq = xor i4 %xyzq, -1
   %r = or i4 %not_xyzq, %x
   ret i4 %r
 }
 
 define <2 x i4> @simplify_or_common_op_commute3(<2 x i4> %x, <2 x i4> %y, <2 x i4> %p)  {
 ; CHECK-LABEL: @simplify_or_common_op_commute3(
-; CHECK-NEXT:    [[Z:%.*]] = mul <2 x i4> [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[XY:%.*]] = and <2 x i4> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = and <2 x i4> [[Z]], [[XY]]
-; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor <2 x i4> [[XYZ]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[NOT_XYZ]], [[X]]
-; CHECK-NEXT:    ret <2 x i4> [[R]]
+; CHECK-NEXT:    ret <2 x i4> <i4 -1, i4 -1>
 ;
   %z = mul <2 x i4> %p, %p ; thwart complexity-based canonicalization
   %xy = and <2 x i4> %y, %x
   %xyz = and <2 x i4> %z, %xy
   %not_xyz = xor <2 x i4> %xyz, <i4 -1, i4 -1>
   %r = or <2 x i4> %x, %not_xyz
   ret <2 x i4> %r
 }
 
 define i4 @simplify_and_common_op_commute0(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_and_common_op_commute0(
-; CHECK-NEXT:    [[XY:%.*]] = or i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    call void @use(i4 [[X]])
-; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[XY]], [[Z:%.*]]
-; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    call void @use(i4 [[X:%.*]])
+; CHECK-NEXT:    ret i4 0
 ;
   %xy = or i4 %x, %y
   call void @use(i4 %x)
   %xyz = or i4 %xy, %z
   %not_xyz = xor i4 %xyz, -1
   %r = and i4 %not_xyz, %x
   ret i4 %r
 }
 
 define i4 @simplify_and_common_op_commute1(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_and_common_op_commute1(
-; CHECK-NEXT:    [[XY:%.*]] = or i4 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[XY]], [[Z:%.*]]
-; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    ret i4 0
 ;
   %xy = or i4 %y, %x
   %xyz = or i4 %xy, %z
   %not_xyz = xor i4 %xyz, -1
   %r = and i4 %not_xyz, %x
   ret i4 %r
 }
 
+; The common operand may bubble through multiple instructions.
+
 define i4 @simplify_and_common_op_commute2(i4 %x, i4 %y, i4 %p, i4 %q)  {
 ; CHECK-LABEL: @simplify_and_common_op_commute2(
-; CHECK-NEXT:    [[Z:%.*]] = mul i4 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[XY:%.*]] = or i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[Z]], [[XY]]
-; CHECK-NEXT:    [[XYZQ:%.*]] = or i4 [[XYZ]], [[Q:%.*]]
-; CHECK-NEXT:    [[NOT_XYZQ:%.*]] = xor i4 [[XYZQ]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZQ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    ret i4 0
 ;
   %z = mul i4 %p, %p ; thwart complexity-based canonicalization
   %xy = or i4 %x, %y
   %xyz = or i4 %z, %xy
   %xyzq = or i4 %xyz, %q
   %not_xyzq = xor i4 %xyzq, -1
   %r = and i4 %not_xyzq, %x
   ret i4 %r
 }
 
 define <2 x i4> @simplify_and_common_op_commute3(<2 x i4> %x, <2 x i4> %y, <2 x i4> %p)  {
 ; CHECK-LABEL: @simplify_and_common_op_commute3(
-; CHECK-NEXT:    [[Z:%.*]] = mul <2 x i4> [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[XY:%.*]] = or <2 x i4> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = or <2 x i4> [[Z]], [[XY]]
-; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor <2 x i4> [[XYZ]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i4> [[NOT_XYZ]], [[X]]
-; CHECK-NEXT:    ret <2 x i4> [[R]]
+; CHECK-NEXT:    ret <2 x i4> zeroinitializer
 ;
   %z = mul <2 x i4> %p, %p ; thwart complexity-based canonicalization
   %xy = or <2 x i4> %y, %x
   %xyz = or <2 x i4> %z, %xy
   %not_xyz = xor <2 x i4> %xyz, <i4 -1, i4 -1>
   %r = and <2 x i4> %x, %not_xyz
   ret <2 x i4> %r
 }
 
+; TODO: This should simplify.
+
 define i4 @simplify_and_common_op_use1(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_and_common_op_use1(
 ; CHECK-NEXT:    [[XY:%.*]] = or i4 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i4 [[Y]])
 ; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[XY]], [[Z:%.*]]
 ; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
 ; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZ]], [[X]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %xy = or i4 %x, %y
   call void @use(i4 %y)
   %xyz = or i4 %xy, %z
   %not_xyz = xor i4 %xyz, -1
   %r = and i4 %not_xyz, %x
   ret i4 %r
 }
 
+; TODO: This should simplify.
+
 define i4 @simplify_and_common_op_use2(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @simplify_and_common_op_use2(
 ; CHECK-NEXT:    [[XY:%.*]] = or i4 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[XYZ:%.*]] = or i4 [[XY]], [[Z:%.*]]
 ; CHECK-NEXT:    call void @use(i4 [[Z]])
 ; CHECK-NEXT:    [[NOT_XYZ:%.*]] = xor i4 [[XYZ]], -1
 ; CHECK-NEXT:    [[R:%.*]] = and i4 [[NOT_XYZ]], [[X]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %xy = or i4 %x, %y
   %xyz = or i4 %xy, %z
   call void @use(i4 %z)
   %not_xyz = xor i4 %xyz, -1
   %r = and i4 %not_xyz, %x
   ret i4 %r
 }
 
 define i4 @reduce_xor_common_op_commute0(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @reduce_xor_common_op_commute0(
-; CHECK-NEXT:    [[XY:%.*]] = xor i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = xor i4 [[XY]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i4 [[XYZ]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i4 [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %xy = xor i4 %x, %y
   %xyz = xor i4 %xy, %z
   %r = or i4 %xyz, %x
   ret i4 %r
 }
 
 define i4 @reduce_xor_common_op_commute1(i4 %x, i4 %y, i4 %z)  {
 ; CHECK-LABEL: @reduce_xor_common_op_commute1(
-; CHECK-NEXT:    [[XY:%.*]] = xor i4 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = xor i4 [[XY]], [[Z:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = or i4 [[XYZ]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i4 [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = or i4 [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %xy = xor i4 %y, %x
   %xyz = xor i4 %xy, %z
   %r = or i4 %xyz, %x
   ret i4 %r
 }
 
 define i4 @annihilate_xor_common_op_commute2(i4 %x, i4 %y, i4 %p, i4 %q)  {
 ; CHECK-LABEL: @annihilate_xor_common_op_commute2(
 ; CHECK-NEXT:    [[Z:%.*]] = mul i4 [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[XY:%.*]] = xor i4 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = xor i4 [[Z]], [[XY]]
-; CHECK-NEXT:    [[XYZQ:%.*]] = xor i4 [[XYZ]], [[Q:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[XYZQ]], [[X]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i4 [[Z]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i4 [[TMP1]], [[Q:%.*]]
+; CHECK-NEXT:    ret i4 [[TMP2]]
 ;
   %z = mul i4 %p, %p ; thwart complexity-based canonicalization
   %xy = xor i4 %x, %y
   %xyz = xor i4 %z, %xy
   %xyzq = xor i4 %xyz, %q
   %r = xor i4 %xyzq, %x
   ret i4 %r
 }
 
 define <2 x i4> @reduce_xor_common_op_commute3(<2 x i4> %x, <2 x i4> %y, <2 x i4> %p)  {
 ; CHECK-LABEL: @reduce_xor_common_op_commute3(
 ; CHECK-NEXT:    [[Z:%.*]] = mul <2 x i4> [[P:%.*]], [[P]]
-; CHECK-NEXT:    [[XY:%.*]] = xor <2 x i4> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XYZ:%.*]] = xor <2 x i4> [[Z]], [[XY]]
-; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[XYZ]], [[X]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i4> [[Z]], [[Y:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = or <2 x i4> [[TMP1]], [[X:%.*]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %z = mul <2 x i4> %p, %p ; thwart complexity-based canonicalization
   %xy = xor <2 x i4> %y, %x
   %xyz = xor <2 x i4> %z, %xy
   %r = or <2 x i4> %x, %xyz
   ret <2 x i4> %r
 }

llvm/test/Transforms/InstCombine/and-or.ll

 declare void @use2(i32)
 
 define i32 @or_or_and_noOneUse_fail1(i32 %a, i32 %b) {
 ; CHECK-LABEL: @or_or_and_noOneUse_fail1(
 ; CHECK-NEXT:    [[SHR:%.*]] = ashr i32 [[A:%.*]], 23
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[SHR]], 157
 ; CHECK-NEXT:    call void @use2(i32 [[AND]])
 ; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[SHR]], [[B:%.*]]
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[AND3]], [[AND]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[B]], 23
 ; CHECK-NEXT:    [[AND9:%.*]] = and i32 [[TMP1]], 157
-; CHECK-NEXT:    [[R:%.*]] = or i32 [[OR]], [[AND9]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[AND3]], [[AND9]]
+; CHECK-NEXT:    [[R:%.*]] = or i32 [[TMP2]], [[AND]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %shr = ashr i32 %a, 23
   %conv = trunc i32 %shr to i8
   %conv1 = zext i8 %conv to i32
   %and = and i32 %conv1, 925
   call void @use2(i32 %and)
   %and3 = and i32 %shr, %b

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = and i1 [[A_0:%.*]], [[B_0:%.*]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = and i1 [[A_3:%.*]], [[B_3:%.*]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[A_2:%.*]], [[B_2:%.*]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[A_1:%.*]], [[B_1:%.*]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TMP3]], true
 ; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP0]], [[A_1]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = and i1 [[TMP2]], [[B_1]]
-; CHECK-NEXT:    [[TMP7:%.*]] = or i1 [[TMP3]], [[TMP6]]
-; CHECK-NEXT:    [[D:%.*]] = or i1 [[TMP7]], [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = or i1 [[TMP6]], [[TMP5]]
+; CHECK-NEXT:    [[D:%.*]] = or i1 [[TMP7]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP1]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP9:%.*]] = insertvalue { i1, i1, i1, i1, i1 } zeroinitializer, i1 [[D]], 0
 ; CHECK-NEXT:    [[TMP10:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP9]], i1 [[TMP4]], 1
 ; CHECK-NEXT:    [[TMP11:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP10]], i1 true, 2
 ; CHECK-NEXT:    [[TMP12:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP11]], i1 [[A_3]], 3
 ; CHECK-NEXT:    [[TMP13:%.*]] = insertvalue { i1, i1, i1, i1, i1 } [[TMP12]], i1 [[TMP8]], 4
 ; CHECK-NEXT:    ret { i1, i1, i1, i1, i1 } [[TMP13]]
 ;

llvm/test/Transforms/InstCombine/and-xor-or.ll

 }
 
 define i32 @not_and_and_or_no_or_use5(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use5
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[NOT2]], [[C]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[TMP1]], [[B]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
   %or1 = or i32 %b, %a
   %not1 = xor i32 %or1, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or2 = or i32 %and2, %not1
   call void @use(i32 %or1)
   ret i32 %or2
 }
 
 define i32 @not_and_and_or_no_or_use6(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use6
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[NOT2]], [[C]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[TMP1]], [[B]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
   %or1 = or i32 %b, %a
   %not1 = xor i32 %or1, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b

 }
 
 define i32 @not_and_and_or_no_or_use8(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@not_and_and_or_no_or_use8
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[NOT2]], [[C]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[TMP1]], [[B]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
   %or1 = or i32 %b, %a
   %not1 = xor i32 %or1, -1
   %not2 = xor i32 %a, -1
   %and1 = and i32 %not2, %b
;
   call void @use(i32 %not2)
   ret i32 %and2
 }
 
 define i32 @not_or_or_and_no_and_use5(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use5
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[NOT2]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[AND1]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
 ; CHECK-NEXT:    ret i32 [[AND2]]
 ;
   %and1 = and i32 %b, %a
   %not1 = xor i32 %and1, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and2 = and i32 %or2, %not1
   call void @use(i32 %and1)
   ret i32 %and2
 }
 
 define i32 @not_or_or_and_no_and_use6(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use6
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[NOT2]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[AND1]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[AND2]]
 ;
   %and1 = and i32 %b, %a
   %not1 = xor i32 %and1, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
;
   call void @use(i32 %or1)
   ret i32 %and2
 }
 
 define i32 @not_or_or_and_no_and_use8(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: define {{[^@]+}}@not_or_or_and_no_and_use8
 ; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B]], [[A]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[NOT2]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[TMP1]], [[B]]
+; CHECK-NEXT:    [[AND2:%.*]] = xor i32 [[AND1]], [[OR2]]
 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
 ; CHECK-NEXT:    ret i32 [[AND2]]
 ;
   %and1 = and i32 %b, %a
   %not1 = xor i32 %and1, -1
   %not2 = xor i32 %a, -1
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c

llvm/test/Transforms/LoopVectorize/ARM/mve-reduction-predselect.ll

 ; CHECK-NEXT:    [[VEC_PHI:%.*]] = phi <4 x i32> [ <i32 -1, i32 -1, i32 -1, i32 -1>, [[VECTOR_PH]] ], [ [[TMP6:%.*]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[ACTIVE_LANE_MASK:%.*]] = call <4 x i1> @llvm.get.active.lane.mask.v4i1.i32(i32 [[INDEX]], i32 257)
 ; CHECK-NEXT:    [[TMP0:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i32 [[INDEX]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[TMP0]] to <4 x i32>*
 ; CHECK-NEXT:    [[WIDE_MASKED_LOAD:%.*]] = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32(<4 x i32>* [[TMP1]], i32 4, <4 x i1> [[ACTIVE_LANE_MASK]], <4 x i32> poison)
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i32 [[INDEX]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i32* [[TMP2]] to <4 x i32>*
 ; CHECK-NEXT:    [[WIDE_MASKED_LOAD1:%.*]] = call <4 x i32> @llvm.masked.load.v4i32.p0v4i32(<4 x i32>* [[TMP3]], i32 4, <4 x i1> [[ACTIVE_LANE_MASK]], <4 x i32> poison)
-; CHECK-NEXT:    [[TMP4:%.*]] = and <4 x i32> [[VEC_PHI]], [[WIDE_MASKED_LOAD]]
-; CHECK-NEXT:    [[TMP5:%.*]] = and <4 x i32> [[TMP4]], [[WIDE_MASKED_LOAD1]]
-; CHECK-NEXT:    [[TMP6]] = select <4 x i1> [[ACTIVE_LANE_MASK]], <4 x i32> [[TMP5]], <4 x i32> [[VEC_PHI]]
+; CHECK-NEXT:    [[TMP4:%.*]] = and <4 x i32> [[WIDE_MASKED_LOAD]], [[WIDE_MASKED_LOAD1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = select <4 x i1> [[ACTIVE_LANE_MASK]], <4 x i32> [[TMP4]], <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP6]] = and <4 x i32> [[VEC_PHI]], [[TMP5]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i32 [[INDEX]], 4
 ; CHECK-NEXT:    [[TMP7:%.*]] = icmp eq i32 [[INDEX_NEXT]], 260
 ; CHECK-NEXT:    br i1 [[TMP7]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP8:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[TMP8:%.*]] = call i32 @llvm.vector.reduce.and.v4i32(<4 x i32> [[TMP6]])
 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph:
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]

llvm/test/Transforms/LoopVectorize/reduction-predselect.ll

 ; CHECK-NEXT:    [[TMP34:%.*]] = insertelement <4 x i32> [[TMP28]], i32 [[TMP33]], i64 3
 ; CHECK-NEXT:    [[TMP35:%.*]] = getelementptr inbounds i32, i32* [[B]], i32 [[TMP31]]
 ; CHECK-NEXT:    [[TMP36:%.*]] = load i32, i32* [[TMP35]], align 4
 ; CHECK-NEXT:    [[TMP37:%.*]] = insertelement <4 x i32> [[TMP29]], i32 [[TMP36]], i64 3
 ; CHECK-NEXT:    br label [[PRED_LOAD_CONTINUE6]]
 ; CHECK:       pred.load.continue6:
 ; CHECK-NEXT:    [[TMP38:%.*]] = phi <4 x i32> [ [[TMP28]], [[PRED_LOAD_CONTINUE4]] ], [ [[TMP34]], [[PRED_LOAD_IF5]] ]
 ; CHECK-NEXT:    [[TMP39:%.*]] = phi <4 x i32> [ [[TMP29]], [[PRED_LOAD_CONTINUE4]] ], [ [[TMP37]], [[PRED_LOAD_IF5]] ]
-; CHECK-NEXT:    [[TMP40:%.*]] = and <4 x i32> [[VEC_PHI]], [[TMP38]]
-; CHECK-NEXT:    [[TMP41:%.*]] = and <4 x i32> [[TMP40]], [[TMP39]]
-; CHECK-NEXT:    [[TMP42]] = select <4 x i1> [[TMP0]], <4 x i32> [[TMP41]], <4 x i32> [[VEC_PHI]]
+; CHECK-NEXT:    [[TMP40:%.*]] = and <4 x i32> [[TMP38]], [[TMP39]]
+; CHECK-NEXT:    [[TMP41:%.*]] = select <4 x i1> [[TMP0]], <4 x i32> [[TMP40]], <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP42]] = and <4 x i32> [[VEC_PHI]], [[TMP41]]
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add i32 [[INDEX]], 4
 ; CHECK-NEXT:    [[VEC_IND_NEXT]] = add <4 x i32> [[VEC_IND]], <i32 4, i32 4, i32 4, i32 4>
 ; CHECK-NEXT:    [[TMP43:%.*]] = icmp eq i32 [[INDEX_NEXT]], 260
 ; CHECK-NEXT:    br i1 [[TMP43]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP8:![0-9]+]]
 ; CHECK:       middle.block:
 ; CHECK-NEXT:    [[TMP44:%.*]] = call i32 @llvm.vector.reduce.and.v4i32(<4 x i32> [[TMP42]])
 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[SCALAR_PH]]
 ; CHECK:       scalar.ph: