[InstCombine] Improve bswap optimization

[austin880625]

Summary

The implementation of D149577

The patch implements a helper function that matches and fold the following cases in the InstCombine pass:

1. bswap(logic_op(x, bswap(y))) -> logic_op(bswap(x), y)
2. bswap(logic_op(bswap(x), y)) -> logic_op(x, bswap(y))
3. bswap(logic_op(bswap(x), bswap(y))) -> logic_op(x, y) in multiuse case, which still reduces the number of instructions.

The helper function accepts bswap and bitreverse intrinsics. This patch folds the bswap cases and remain the bitreverse optimization for the future

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

6029

"bswap/bitreverse" -> "bswap"

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10785

Likewise a helper here so it can be easily extended to handle bitreverse/any other intrinsics that it applies to.
Also, there are no tests for the DAGCombiner changes at the moment.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

70 ↗

(On Diff #518884)

What is this change for?

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1275

Instead of making this a member function. Can you leave it static. To create new instructions you can add an extra argument InstCombiner::BuilderTy &Builder.

It should look like: InstCombineAndOrXor.cc::reassociateFCmps

1708

if (Instruction *crossLogicOpFold = foldBitOrderCrossLogicOp<Intrinsic::bswap>(IIOperand))
   return crossLogicOpFold;

[austin880625]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

70 ↗

(On Diff #518884)

if one of the operand has more than one use, then the transform will not reduce the number of instructions(can look at the bs_and64_multiuse* test case diff) and in DAGCombiner the same optimization also uses || instead of &&:

// Unary ops: logic_op (bswap x), (bswap y) --> bswap (logic_op x, y)
if (HandOpcode == ISD::BSWAP) {
  // If either operand has other uses, this transform is not an improvement.
  if (!N0.hasOneUse() || !N1.hasOneUse())
    return SDValue();
  SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
  return DAG.getNode(HandOpcode, DL, VT, Logic);                                   
}

I noticed it just because I was referencing D6407 , It's minor and not directly related to the improvement this time. I'm not sure if this kind of change can be included.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

70 ↗

(On Diff #518884)

if one of the operand has more than one use, then the transform will not reduce the number of instructions(can look at the bs_and64_multiuse* test case diff) and in DAGCombiner the same optimization also uses || instead of &&:

// Unary ops: logic_op (bswap x), (bswap y) --> bswap (logic_op x, y)
if (HandOpcode == ISD::BSWAP) {
  // If either operand has other uses, this transform is not an improvement.
  if (!N0.hasOneUse() || !N1.hasOneUse())
    return SDValue();
  SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
  return DAG.getNode(HandOpcode, DL, VT, Logic);                                   
}

I noticed it just because I was referencing D6407 , It's minor and not directly related to the improvement this time. I'm not sure if this kind of change can be included.

It should be a seperate patch.

Its generally okay for a combine to result in the same amount of instructions so if you have a case where this is useful its fine to post as another patch.

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

6032

I don't think we need this comment... This is not the kind of optimization that needs extra justification in the code.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10785

In any case, this should be part of a separate patch, not mixed with InstCombine changes.

[austin880625]

add the diff on the test cases for CodeGen(DAGCombiner)

move the pattern matching in DAGCombiner into a helper function that also accepts BITREVERSE operation in future improvement

[austin880625]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

10785

oh I just see the new comment. Let me separate this again

[austin880625]

llvm/lib/Analysis/InstructionSimplify.cpp

6032

I just see some discussions where this optimization was mentioned, so thought about this comment might help whoever run into it
https://github.com/dotnet/runtime/issues/66249
https://reviews.llvm.org/D6407#change-hPSGuibm8ixX

If this is still not needed, I'll remove it together in the next version of the patch

[austin880625]

includes changes for InstCombine only, the DAGCombiner implementation is moved to a separate rivision D149783

[goldstein.w.n]

Can you update the summary to explain the transform.
Other than that looks good.

[RKSimon]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1288

match(X, m_OneUse(m_Intrinsic<IntrID>(m_Value(OldReorder)))) ?

1291

match(Y, m_OneUse(m_Intrinsic<IntrID>(m_Value(OldReorder)))) ?

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1296

In that case that both X and Y match the intrinsic, we should still do the optimization even if X/Y have multi-use.
I.e

declare i16 @llvm.bswap.i16(i16)
declare void @use.i16(i16)
define i16 @bs_and_lhs_bs16(i16 %x, i16 %y) {
  %bx = tail call i16 @llvm.bswap.i16(i16 %x)
  %by = tail call i16 @llvm.bswap.i16(i16 %y)
  %r = and i16 %bx, %by
  %br = tail call i16 @llvm.bswap.i16(i16 %r)

  call void @use.i16(i16 %bx)
  call void @use.i16(i16 %by)    
  ret i16 %br
}

Should become:

declare i16 @llvm.bswap.i16(i16)
declare void @use.i16(i16)
define i16 @bs_and_lhs_bs16(i16 %x, i16 %y) {
  %bx = tail call i16 @llvm.bswap.i16(i16 %x)
  %by = tail call i16 @llvm.bswap.i16(i16 %y)
  %r = and i16 %x, %y
  call void @use.i16(i16 %bx)
  call void @use.i16(i16 %by)    
  ret i16 %r
}

I think an initiali if statement that check for that case would work.

[austin880625]

handles bswap(logic_op(bswap(x), bswap(y))) -> logic_op(x, y) case with multi-use

[goldstein.w.n]

LGTM. Note, I'm not a maintainer so please wait a day or so before pushing so others can check it out.

Maybe follow up patch to enable for bitreverse?

[RKSimon]

LGTM with one minor

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1275

Can we just use a static_assert here since its a template arg?

[austin880625]

Use the static_assert for the intrinsic ID check in compile time

[RKSimon]

LGTM - cheers

[nathanchance]

This patch causes an assertion failure when building the Linux kernel for PowerPC. A reduced LLVM IR reproducer (and the C reproducer it was derived from):

target datalayout = "e-m:e-Fn32-i64:64-n32:64-S128-v256:256:256-v512:512:512"
target triple = "powerpc64le-unknown-linux-gnu"

@_end = external global [0 x i8]

define void @__attribute__kexec_setup(ptr %kernel_end) {
entry:
  %0 = call i64 @llvm.bswap.i64(i64 and (i64 ptrtoint (ptr @_end to i64), i64 4095))
  store i64 %0, ptr %kernel_end, align 8
  ret void
}

; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare i64 @llvm.bswap.i64(i64) #0

attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(none) }

extern char _end[];
long kernel_end;
void __attribute__kexec_setup() {
  kernel_end = __builtin_bswap64(({ (long)_end & 4095; }));
}

$ opt -O3 -disable-output reduced.ll
opt: /mnt/nvme/tmp/cvise.COqG3u2BwX/src/llvm/include/llvm/Support/Casting.h:578: decltype(auto) llvm::cast(From *) [To = llvm::BinaryOperator, From = llvm::Value]: Assertion `isa<To>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: opt -O3 -disable-output reduced.ll
 #0 0x00005628ee047568 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x4b8b568)
 #1 0x00005628ee0452ee llvm::sys::RunSignalHandlers() (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x4b892ee)
 #2 0x00005628ee047d28 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007fd4ef6efab0 (/usr/lib/libc.so.6+0x39ab0)
 #4 0x00007fd4ef73f26c (/usr/lib/libc.so.6+0x8926c)
 #5 0x00007fd4ef6efa08 raise (/usr/lib/libc.so.6+0x39a08)
 #6 0x00007fd4ef6d8538 abort (/usr/lib/libc.so.6+0x22538)
 #7 0x00007fd4ef6d845c (/usr/lib/libc.so.6+0x2245c)
 #8 0x00007fd4ef6e83d6 (/usr/lib/libc.so.6+0x323d6)
 #9 0x00005628edc4a2c2 llvm::Instruction* foldBitOrderCrossLogicOp<9u>(llvm::Value*, llvm::IRBuilder<llvm::TargetFolder, llvm::IRBuilderCallbackInserter>&) InstCombineCalls.cpp:0:0
#10 0x00005628edc46269 llvm::InstCombinerImpl::visitCallInst(llvm::CallInst&) InstCombineCalls.cpp:0:0
#11 0x00005628edbec59f llvm::InstCombinerImpl::run() InstructionCombining.cpp:0:0
#12 0x00005628edbeee45 combineInstructionsOverFunction(llvm::Function&, llvm::InstructionWorklist&, llvm::AAResults*, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::OptimizationRemarkEmitter&, llvm::BlockFrequencyInfo*, llvm::ProfileSummaryInfo*, unsigned int, llvm::LoopInfo*) InstructionCombining.cpp:0:0
#13 0x00005628edbee605 llvm::InstCombinePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x4732605)
#14 0x00005628ee24841d llvm::detail::PassModel<llvm::Function, llvm::InstCombinePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) PassBuilder.cpp:0:0
#15 0x00005628edb00004 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x4644004)
#16 0x00005628ec6ba78d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) BPFTargetMachine.cpp:0:0
#17 0x00005628edb04273 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x4648273)
#18 0x00005628ec6ba52d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) BPFTargetMachine.cpp:0:0
#19 0x00005628edaff1f4 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x46431f4)
#20 0x00005628ec1a08eb llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x2ce48eb)
#21 0x00005628ec1b0111 main (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x2cf4111)
#22 0x00007fd4ef6d9850 (/usr/lib/libc.so.6+0x23850)
#23 0x00007fd4ef6d990a __libc_start_main (/usr/lib/libc.so.6+0x2390a)
#24 0x00005628ec19a265 _start (/mnt/nvme/tmp/cvise.COqG3u2BwX/install/llvm-bad/bin/opt+0x2cde265)

[austin880625]

I'm not able to reproduce the failure with the given IR. Does the failure persist if the and in the bswap are moved out as a separate instruction?
Anyway maybe we should use dyn_cast with if check

[goldstein.w.n]

In D149699#4325654, @austin880625 wrote:

I'm not able to reproduce the failure with the given IR. Does the failure persist if the and in the bswap are moved out as a separate instruction?
Anyway maybe we should use dyn_cast with if check

I'm going to revert this for now so you can post the fix.
You can re-open this commit when you are ready.

The following:

-  if (match(V, m_OneUse(m_BitwiseLogic(m_Value(X), m_Value(Y))))) {
+  // Find bitwise logic op. Check that it is a BinaryOperator explicitly so we
+  // don't match ConstantExpr that aren't meaningful for this transform.
+  if (match(V, m_OneUse(m_BitwiseLogic(m_Value(X), m_Value(Y)))) &&
+      isa<BinaryOperator>(V)) {

works for me and leaves both:

@gp = external global [0 x i8]
+
+define void @foo(ptr %out, i64 %a) {
+  %gpi = ptrtoint ptr @gp to i64
+  %exp = and i64 %gpi, 4095
+  %res = call i64 @llvm.bswap.i64(i64 %exp)
+  store i64 %res, ptr %out, align 8
+  ret void
+}
+
+
+define void @bar(ptr %out, i64 %a) {
+  %gpi = ptrtoint ptr @gp to i64
+  %bs_gpi = call i64 @llvm.bswap.i64(i64 %gpi)
+  %exp = and i64 %bs_gpi, 4095
+  %res = call i64 @llvm.bswap.i64(i64 %exp)
+  store i64 %res, ptr %out, align 8
+  ret void
+}
+

working ideally.

[austin880625]

Oh I reproduced it in Debug build but cannot in Release build. I might be able to troubleshoot in detail in the following day

[austin880625]

Add explicit check for BinaryOperator and add ConstExpr test case

[austin880625]

try to update the patch base as previous one failed

[goldstein.w.n]

In D149699#4328668, @austin880625 wrote:

try to update the patch base as previous one failed

Should work now. You need to reopen the revision.

[austin880625]

Sorry if inappropriate, but does this patch need further actions/improvement on my side?

[goldstein.w.n]

In D149699#4343367, @austin880625 wrote:

Sorry if inappropriate, but does this patch need further actions/improvement on my side?

Sorry! I've been dragging my feet on this. It looks good. I will test this and the DAGCombiner patch today/tonight.
If you haven't heard back in 24hr ping back.

Its not inappropriate at all to ping. roughly once a week is appropriate at all times unless there are
unaddressed feedbacks to already handle. Sometime more often is appropriate as well if its say for
an urgent bug.

[goldstein.w.n]

LGTM. Do you need me to commit?

[goldstein.w.n]

Austin, can you give me a commit message for the re-push.

Something like

'Recommit "<original tilte>" (2nd Try)

<Explain why it now works>'

Then I'll push this and the bswap patches for you.

[austin880625]

Thanks for helping out! Here's the proposed commit message

Recommit: [InstCombine] Improve bswap optimization(2nd try)

Check the operator is BinaryOperator before cast so that we won't match ConstExpr

[goldstein.w.n]

In D149699#4346601, @austin880625 wrote:

Thanks for helping out! Here's the proposed commit message

Recommit: [InstCombine] Improve bswap optimization(2nd try)

Check the operator is BinaryOperator before cast so that we won't match ConstExpr

Does:

Recommit "[InstCombine] Improve bswap optimization" (2nd try)

Issue was assertion failure due to an unchecked `cast`. Fix is to check the operator is
`BinaryOperator` before cast so that we won't match `ConstExpr`

Sound okay? Just to reference what the original issue was.

[RKSimon]

In D149699#4347068, @goldstein.w.n wrote:

In D149699#4346601, @austin880625 wrote:

Thanks for helping out! Here's the proposed commit message

Recommit: [InstCombine] Improve bswap optimization(2nd try)

Check the operator is BinaryOperator before cast so that we won't match ConstExpr

Does:

Recommit "[InstCombine] Improve bswap optimization" (2nd try)

Issue was assertion failure due to an unchecked `cast`. Fix is to check the operator is
`BinaryOperator` before cast so that we won't match `ConstExpr`

Sound okay? Just to reference what the original issue was.

BTW: Austin Chang <[e-mail]>

[austin880625]

In D149699#4347068, @goldstein.w.n wrote:

In D149699#4346601, @austin880625 wrote:

Thanks for helping out! Here's the proposed commit message

Recommit: [InstCombine] Improve bswap optimization(2nd try)

Check the operator is BinaryOperator before cast so that we won't match ConstExpr

Does:

Recommit "[InstCombine] Improve bswap optimization" (2nd try)

Issue was assertion failure due to an unchecked `cast`. Fix is to check the operator is
`BinaryOperator` before cast so that we won't match `ConstExpr`

Sound okay? Just to reference what the original issue was.

OK, let's proceed with this one

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyUnaryIntrinsic(Function *F, Value *Op0,
   Value *X;
   switch (IID) {
   case Intrinsic::fabs:
     if (SignBitMustBeZero(Op0, Q.TLI))
       return Op0;
     break;
   case Intrinsic::bswap:
     // bswap(bswap(x)) -> x
+    // The duplicate bswap might not come from real world code, but can be
+    // introduced by other optimizations
+    // e.g. bswap(logic_op(bswap(x), bswap(y)))
+    //  --> bswap(bswap(logic_op(x, y)))
     if (match(Op0, m_BSwap(m_Value(X))))
       return X;
     break;
   case Intrinsic::bitreverse:
     // bitreverse(bitreverse(x)) -> x
     if (match(Op0, m_BitReverse(m_Value(X))))
       return X;
     break;

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static SDValue combineShiftToMULH(SDNode *N, SelectionDAG &DAG,
   }
 
   SDValue Result =
       DAG.getNode(MulhOpcode, DL, NarrowVT, LeftOp.getOperand(0), MulhRightOp);
   return (N->getOpcode() == ISD::SRA ? DAG.getSExtOrTrunc(Result, DL, WideVT)
                                      : DAG.getZExtOrTrunc(Result, DL, WideVT));
 }
 
+// fold (bswap (logic_op(bswap(x),y))) -> logic_op(x,bswap(y))
+// This helper function accept ISD::BSWAP and ISD::BITREVERSE in Opcode
+// parameter
+static SDValue foldBitOrderCrossLogicOp(SDNode *N, SelectionDAG &DAG) {
+  unsigned Opcode = N->getOpcode();
+  if (Opcode != ISD::BSWAP && Opcode != ISD::BITREVERSE)
+    return SDValue();
+
+  SDValue N0 = N->getOperand(0);
+  EVT VT = N->getValueType(0);
+  SDLoc DL(N);
+  if (ISD::isBitwiseLogicOp(N0.getOpcode()) && N0.hasOneUse()) {
+    SDValue OldLHS = N0.getOperand(0);
+    SDValue OldRHS = N0.getOperand(1);
+
+    // Need to ensure logic_op and bswap/bitreverse(x) doesn't have other uses
+    if (OldLHS.getOpcode() == Opcode && OldLHS.hasOneUse()) {
+      SDValue NewBitReorder = DAG.getNode(Opcode, DL, VT, OldRHS);
+      return DAG.getNode(N0.getOpcode(), DL, VT, OldLHS.getOperand(0),
+          NewBitReorder);
+    } else if (OldRHS.getOpcode() == Opcode && OldRHS.hasOneUse()) {
+      SDValue NewBitReorder = DAG.getNode(Opcode, DL, VT, OldLHS);
+      return DAG.getNode(N0.getOpcode(), DL, VT, OldRHS.getOperand(0),
+          NewBitReorder);
+    }
+  }
+  return SDValue();
+}
+
 SDValue DAGCombiner::visitSRA(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   if (SDValue V = DAG.simplifyShift(N0, N1))
     return V;
 
   EVT VT = N0.getValueType();
   unsigned OpSizeInBits = VT.getScalarSizeInBits();
if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL) &&
     if (ShAmt && ShAmt->getAPIntValue().ult(BW) &&
         ShAmt->getZExtValue() % 8 == 0) {
       SDValue NewSwap = DAG.getNode(ISD::BSWAP, DL, VT, N0.getOperand(0));
       unsigned InverseShift = N0.getOpcode() == ISD::SHL ? ISD::SRL : ISD::SHL;
       return DAG.getNode(InverseShift, DL, VT, NewSwap, N0.getOperand(1));
     }
   }
 
+  if (SDValue V = foldBitOrderCrossLogicOp(N, DAG))
+    return V;
+
   return SDValue();
 }
 
 SDValue DAGCombiner::visitBITREVERSE(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   EVT VT = N->getValueType(0);
 
   // fold (bitreverse c1) -> c2

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

foldShuffledIntrinsicOperands(IntrinsicInst *II,
 
   // intrinsic (shuf X, M), (shuf Y, M), ... --> shuf (intrinsic X, Y, ...), M
   Instruction *FPI = isa<FPMathOperator>(II) ? II : nullptr;
   Value *NewIntrinsic =
       Builder.CreateIntrinsic(II->getIntrinsicID(), SrcTy, NewArgs, FPI);
   return new ShuffleVectorInst(NewIntrinsic, Mask);
 }
 
+/// Fold two bit reordering intrinsics(bswap/bitreverse) with f(f(x)) = x
+/// crossing logical op, into single instruction in the operand of the logical
+/// op. The value V is given as the operand of the outer bswap/bitreverse
+/// instrinsic
+/// e.g. bswap(logic_op(bswap(x), y)) --> logic_op(x, bswap(y))
+template <Intrinsic::ID IntrID>
+static Instruction *foldBitOrderCrossLogicOp(Value *V, InstCombiner::BuilderTy &Builder) {
+  if (IntrID != Intrinsic::bswap && IntrID != Intrinsic::bitreverse)
+    return nullptr;
+
+  Value *X, *Y;
+  if (match(V, m_OneUse(m_BitwiseLogic(m_Value(X), m_Value(Y))))) {
+    Value *OldReorder;
+    BinaryOperator::BinaryOps Op = cast<BinaryOperator>(V)->getOpcode();
+
+    // At least one side need to be bswap/bitreverse so that the number of
+    // bswap can be reduced.
+    // We also need to ensure the operands whose bswap/bitreverse is being
+    // removed have no other uses.
+    if (match(X, m_Intrinsic<IntrID>(m_Value(OldReorder))) && X->hasOneUse()) {
+      Value *NewReorder = Builder.CreateUnaryIntrinsic(IntrID, Y);
+      return BinaryOperator::Create(Op, OldReorder, NewReorder);
+    } else if (match(Y, m_Intrinsic<IntrID>(m_Value(OldReorder))) &&
+               Y->hasOneUse()) {
+      Value *NewReorder = Builder.CreateUnaryIntrinsic(IntrID, X);
+      return BinaryOperator::Create(Op, NewReorder, OldReorder);
+    }
+  }
+  return nullptr;
+}
+
 /// CallInst simplification. This mostly only handles folding of intrinsic
 /// instructions. For normal calls, it allows visitCallBase to do the heavy
 /// lifting.
 Instruction *InstCombinerImpl::visitCallInst(CallInst &CI) {
   // Don't try to simplify calls without uses. It will not do anything useful,
   // but will result in the following folds being skipped.
   if (!CI.use_empty()) {
     SmallVector<Value *, 4> Args;
case Intrinsic::bswap: {
 
     // bswap(trunc(bswap(x))) -> trunc(lshr(x, c))
     if (match(IIOperand, m_Trunc(m_BSwap(m_Value(X))))) {
       unsigned C = X->getType()->getScalarSizeInBits() - BW;
       Value *CV = ConstantInt::get(X->getType(), C);
       Value *V = Builder.CreateLShr(X, CV);
       return new TruncInst(V, IIOperand->getType());
     }
+
+    if (Instruction *crossLogicOpFold =
+        foldBitOrderCrossLogicOp<Intrinsic::bswap>(IIOperand, Builder)) {
+      return crossLogicOpFold;
+    }
+
     break;
   }
   case Intrinsic::masked_load:
     if (Value *SimplifiedMaskedOp = simplifyMaskedLoad(*II))
       return replaceInstUsesWith(CI, SimplifiedMaskedOp);
     break;
   case Intrinsic::masked_store:
     return simplifyMaskedStore(*II);

llvm/test/CodeGen/X86/combine-bswap.ll

 }
 
 define i32 @bs_and_lhs_bs32(i32 %a, i32 %b) #0 {
 ; X86-LABEL: bs_and_lhs_bs32:
 ; X86:       # %bb.0:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bs_and_lhs_bs32:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl %edi, %eax
-; X64-NEXT:    bswapl %eax
-; X64-NEXT:    andl %esi, %eax
+; X64-NEXT:    movl %esi, %eax
 ; X64-NEXT:    bswapl %eax
+; X64-NEXT:    andl %edi, %eax
 ; X64-NEXT:    retq
   %1 = tail call i32 @llvm.bswap.i32(i32 %a)
   %2 = and i32 %1, %b
   %3 = tail call i32 @llvm.bswap.i32(i32 %2)
   ret i32 %3
 }
 
 define i64 @bs_and_lhs_bs64(i64 %a, i64 %b) #0 {
 ; X86-LABEL: bs_and_lhs_bs64:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax
-; X86-NEXT:    bswapl %edx
-; X86-NEXT:    andl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    bswapl %edx
+; X86-NEXT:    andl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bs_and_lhs_bs64:
 ; X64:       # %bb.0:
-; X64-NEXT:    movq %rdi, %rax
-; X64-NEXT:    bswapq %rax
-; X64-NEXT:    andq %rsi, %rax
+; X64-NEXT:    movq %rsi, %rax
 ; X64-NEXT:    bswapq %rax
+; X64-NEXT:    andq %rdi, %rax
 ; X64-NEXT:    retq
   %1 = tail call i64 @llvm.bswap.i64(i64 %a)
   %2 = and i64 %1, %b
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 define i64 @bs_and_rhs_bs64(i64 %a, i64 %b) #0 {
 ; X86-LABEL: bs_and_rhs_bs64:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
+; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    bswapl %eax
-; X86-NEXT:    bswapl %edx
-; X86-NEXT:    andl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    bswapl %eax
 ; X86-NEXT:    bswapl %edx
+; X86-NEXT:    andl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: bs_and_rhs_bs64:
 ; X64:       # %bb.0:
-; X64-NEXT:    movq %rsi, %rax
-; X64-NEXT:    bswapq %rax
-; X64-NEXT:    andq %rdi, %rax
+; X64-NEXT:    movq %rdi, %rax
 ; X64-NEXT:    bswapq %rax
+; X64-NEXT:    andq %rsi, %rax
 ; X64-NEXT:    retq
   %1 = tail call i64 @llvm.bswap.i64(i64 %b)
   %2 = and i64 %1, %a
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 ; negative test

llvm/test/Transforms/InstCombine/bswap-fold.ll

;
   ret i64 %t3
 }
 
 
 ; Issue#62236
 ; Fold: BSWAP( OP( BSWAP(x), y ) ) -> OP( x, BSWAP(y) )
 define i16 @bs_and_lhs_bs16(i16 %a, i16 %b) #0 {
 ; CHECK-LABEL: @bs_and_lhs_bs16(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[A:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[TMP2]])
-; CHECK-NEXT:    ret i16 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[B:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    ret i16 [[TMP2]]
 ;
   %1 = tail call i16 @llvm.bswap.i16(i16 %a)
   %2 = and i16 %1, %b
   %3 = tail call i16 @llvm.bswap.i16(i16 %2)
   ret i16 %3
 }
 
 define i16 @bs_or_lhs_bs16(i16 %a, i16 %b) #0 {
 ; CHECK-LABEL: @bs_or_lhs_bs16(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[A:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = or i16 [[TMP1]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[TMP2]])
-; CHECK-NEXT:    ret i16 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[B:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = or i16 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    ret i16 [[TMP2]]
 ;
   %1 = tail call i16 @llvm.bswap.i16(i16 %a)
   %2 = or i16 %1, %b
   %3 = tail call i16 @llvm.bswap.i16(i16 %2)
   ret i16 %3
 }
 
 define i16 @bs_xor_lhs_bs16(i16 %a, i16 %b) #0 {
 ; CHECK-LABEL: @bs_xor_lhs_bs16(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[A:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i16 [[TMP1]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[TMP2]])
-; CHECK-NEXT:    ret i16 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[B:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i16 [[TMP1]], [[A:%.*]]
+; CHECK-NEXT:    ret i16 [[TMP2]]
 ;
   %1 = tail call i16 @llvm.bswap.i16(i16 %a)
   %2 = xor i16 %1, %b
   %3 = tail call i16 @llvm.bswap.i16(i16 %2)
   ret i16 %3
 }
 
 define i16 @bs_and_rhs_bs16(i16 %a, i16 %b) #0 {
 ; CHECK-LABEL: @bs_and_rhs_bs16(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[TMP2]])
-; CHECK-NEXT:    ret i16 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i16 [[TMP2]]
 ;
   %1 = tail call i16 @llvm.bswap.i16(i16 %b)
   %2 = and i16 %1, %a
   %3 = tail call i16 @llvm.bswap.i16(i16 %2)
   ret i16 %3
 }
 
 define i16 @bs_or_rhs_bs16(i16 %a, i16 %b) #0 {
 ; CHECK-LABEL: @bs_or_rhs_bs16(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = or i16 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[TMP2]])
-; CHECK-NEXT:    ret i16 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = or i16 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i16 [[TMP2]]
 ;
   %1 = tail call i16 @llvm.bswap.i16(i16 %b)
   %2 = or i16 %1, %a
   %3 = tail call i16 @llvm.bswap.i16(i16 %2)
   ret i16 %3
 }
 
 define i16 @bs_xor_rhs_bs16(i16 %a, i16 %b) #0 {
 ; CHECK-LABEL: @bs_xor_rhs_bs16(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i16 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i16 @llvm.bswap.i16(i16 [[TMP2]])
-; CHECK-NEXT:    ret i16 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i16 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i16 [[TMP2]]
 ;
   %1 = tail call i16 @llvm.bswap.i16(i16 %b)
   %2 = xor i16 %1, %a
   %3 = tail call i16 @llvm.bswap.i16(i16 %2)
   ret i16 %3
 }
 
 define i32 @bs_and_rhs_bs32(i32 %a, i32 %b) #0 {
 ; CHECK-LABEL: @bs_and_rhs_bs32(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i32 @llvm.bswap.i32(i32 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 @llvm.bswap.i32(i32 [[TMP2]])
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.bswap.i32(i32 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %1 = tail call i32 @llvm.bswap.i32(i32 %b)
   %2 = and i32 %1, %a
   %3 = tail call i32 @llvm.bswap.i32(i32 %2)
   ret i32 %3
 }
 
 define i32 @bs_or_rhs_bs32(i32 %a, i32 %b) #0 {
 ; CHECK-LABEL: @bs_or_rhs_bs32(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i32 @llvm.bswap.i32(i32 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 @llvm.bswap.i32(i32 [[TMP2]])
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.bswap.i32(i32 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %1 = tail call i32 @llvm.bswap.i32(i32 %b)
   %2 = or i32 %1, %a
   %3 = tail call i32 @llvm.bswap.i32(i32 %2)
   ret i32 %3
 }
 
 define i32 @bs_xor_rhs_bs32(i32 %a, i32 %b) #0 {
 ; CHECK-LABEL: @bs_xor_rhs_bs32(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i32 @llvm.bswap.i32(i32 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i32 @llvm.bswap.i32(i32 [[TMP2]])
-; CHECK-NEXT:    ret i32 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.bswap.i32(i32 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %1 = tail call i32 @llvm.bswap.i32(i32 %b)
   %2 = xor i32 %1, %a
   %3 = tail call i32 @llvm.bswap.i32(i32 %2)
   ret i32 %3
 }
 
 define i64 @bs_and_rhs_bs64(i64 %a, i64 %b) #0 {
 ; CHECK-LABEL: @bs_and_rhs_bs64(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i64 @llvm.bswap.i64(i64 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i64 @llvm.bswap.i64(i64 [[TMP2]])
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.bswap.i64(i64 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = and i64 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %1 = tail call i64 @llvm.bswap.i64(i64 %b)
   %2 = and i64 %1, %a
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 define i64 @bs_or_rhs_bs64(i64 %a, i64 %b) #0 {
 ; CHECK-LABEL: @bs_or_rhs_bs64(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i64 @llvm.bswap.i64(i64 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = or i64 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i64 @llvm.bswap.i64(i64 [[TMP2]])
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.bswap.i64(i64 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = or i64 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %1 = tail call i64 @llvm.bswap.i64(i64 %b)
   %2 = or i64 %1, %a
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 define i64 @bs_xor_rhs_bs64(i64 %a, i64 %b) #0 {
 ; CHECK-LABEL: @bs_xor_rhs_bs64(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i64 @llvm.bswap.i64(i64 [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call i64 @llvm.bswap.i64(i64 [[TMP2]])
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @llvm.bswap.i64(i64 [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP2]]
 ;
   %1 = tail call i64 @llvm.bswap.i64(i64 %b)
   %2 = xor i64 %1, %a
   %3 = tail call i64 @llvm.bswap.i64(i64 %2)
   ret i64 %3
 }
 
 define <2 x i32> @bs_and_rhs_i32vec(<2 x i32> %a, <2 x i32> %b) #0 {
 ; CHECK-LABEL: @bs_and_rhs_i32vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[TMP2]])
-; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %1 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %b)
   %2 = and <2 x i32> %1, %a
   %3 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %2)
   ret <2 x i32> %3
 }
 
 define <2 x i32> @bs_or_rhs_i32vec(<2 x i32> %a, <2 x i32> %b) #0 {
 ; CHECK-LABEL: @bs_or_rhs_i32vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = or <2 x i32> [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[TMP2]])
-; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = or <2 x i32> [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %1 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %b)
   %2 = or <2 x i32> %1, %a
   %3 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %2)
   ret <2 x i32> %3
 }
 
 define <2 x i32> @bs_xor_rhs_i32vec(<2 x i32> %a, <2 x i32> %b) #0 {
 ; CHECK-LABEL: @bs_xor_rhs_i32vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[B:%.*]])
-; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[TMP1]], [[A:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[TMP2]])
-; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[A:%.*]])
+; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[TMP1]], [[B:%.*]]
+; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %1 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %b)
   %2 = xor <2 x i32> %1, %a
   %3 = tail call <2 x i32> @llvm.bswap.v2i32(<2 x i32> %2)
   ret <2 x i32> %3
 }
 
 define i64 @bs_and_rhs_bs64_multiuse1(i64 %a, i64 %b) #0 {