[InstCombine] Adjusting bswap pattern matching to hold for And/Shift mixed case

[opaparo]

Summary

Following a discussion that started in D41353, and tests from rL322206 to illustrate the missing pattern, I've modified the bswap pattern matching so that the "mixed" case of an 'or' of 'and' and a shift will also be considered a potential candidate for transforming to bswap.

[spatel]

Thanks for coming back to this. I think this patch is fine as one more match of a potential IR variant, but...
Since the time we started the discussion in D41353, there was a proposal to improve matching for ctpop and ctlz in D45173. I'm curious what others think about the fact that we match bswap/bitreverse in regular instcombine. Would it be better to match all of those intrinsics in the same place? Do we distinguish these based on how often we expect them to occur?

[kparzysz]

Sorry, I pasted a wrong revision in a commit message.

[kparzysz]

I screwed it up completely. Let me try to fix it.

[kparzysz]

Hopefully the right diff was restored after the commit mismatch fiasco.

[kparzysz]

@opaparo Please commandeer this revision, I only took over to restore the diff that got accidentally overwritten.

[opaparo]

Restoring the ownership of this revision.

[opaparo]

In D45731#1070485, @spatel wrote:

Thanks for coming back to this. I think this patch is fine as one more match of a potential IR variant, but...
Since the time we started the discussion in D41353, there was a proposal to improve matching for ctpop and ctlz in D45173. I'm curious what others think about the fact that we match bswap/bitreverse in regular instcombine. Would it be better to match all of those intrinsics in the same place? Do we distinguish these based on how often we expect them to occur?

Ping.
Is there a decision regarding this matter?

[spatel]

In D45731#1081031, @opaparo wrote:

In D45731#1070485, @spatel wrote:

Thanks for coming back to this. I think this patch is fine as one more match of a potential IR variant, but...
Since the time we started the discussion in D41353, there was a proposal to improve matching for ctpop and ctlz in D45173. I'm curious what others think about the fact that we match bswap/bitreverse in regular instcombine. Would it be better to match all of those intrinsics in the same place? Do we distinguish these based on how often we expect them to occur?

Ping.
Is there a decision regarding this matter?

I haven't seen anything. For reference, I mentioned ctpop/ctlz in the context of D45986 too, so I think we should do something to organize these optimizations, but I'm not sure what's best.
That said, I think this patch is fine as an enhancement of the existing code, so LGTM.

[kparzysz]

In D45731#1081206, @spatel wrote:

I haven't seen anything. For reference, I mentioned ctpop/ctlz in the context of D45986 too, so I think we should do something to organize these optimizations, but I'm not sure what's best.
That said, I think this patch is fine as an enhancement of the existing code, so LGTM.

Sorry, I was away last week. My understanding is that the distinction between the regular and the aggressive instcombine is based on how expensive the individual transformations are. If we had an infinite computational power, everything would be included in the regular instcombine. Based on that, I think that this patch is ok as is.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
   // (A >> B) | (C << D)  and  (A << B) | (B >> C)  -> bswap if possible.
   bool OrOfShifts = match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
                     match(Op1, m_LogicalShift(m_Value(), m_Value()));
 
   // (A & B) | (C & D)                              -> bswap if possible.
   bool OrOfAnds = match(Op0, m_And(m_Value(), m_Value())) &&
                   match(Op1, m_And(m_Value(), m_Value()));
 
-  if (!OrOfOrs && !OrOfShifts && !OrOfAnds)
+  // (A << B) | (C & D)                              -> bswap if possible.
+  // The bigger pattern here is ((A & C1) << C2) | ((B >> C2) & C1), which is a
+  // part of the bswap idiom for specific values of C1, C2 (e.g. C1 = 16711935,
+  // C2 = 8 for i32).
+  // This pattern can occur when the operands of the 'or' are not canonicalized
+  // for some reason (not having only one use, for example).
+  bool OrOfAndAndSh = (match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
+                       match(Op1, m_And(m_Value(), m_Value()))) ||
+                      (match(Op0, m_And(m_Value(), m_Value())) &&
+                       match(Op1, m_LogicalShift(m_Value(), m_Value())));
+
+  if (!OrOfOrs && !OrOfShifts && !OrOfAnds && !OrOfAndAndSh)
     return nullptr;
 
   SmallVector<Instruction*, 4> Insts;
   if (!recognizeBSwapOrBitReverseIdiom(&I, true, false, Insts))
     return nullptr;
   Instruction *LastInst = Insts.pop_back_val();
   LastInst->removeFromParent();
 

test/Transforms/InstCombine/bswap.ll

;
   %t = and i32 %swaphalf, 16711935
   %tshl = shl nuw i32 %t, 8
   %b = lshr i32 %swaphalf, 8
   %band = and i32 %b, 16711935
   %bswap = or i32 %tshl, %band
   ret i32 %bswap
 }
 
-; FIXME: Extra use should not prevent matching to bswap.
+; Extra use should not prevent matching to bswap.
 ; swaphalf = (x << 16 | x >> 16)
 ; ((swaphalf & 0x00ff00ff) << 8) | ((swaphalf >> 8) & 0x00ff00ff)
 
 define i32 @bswap32_and_first_extra_use(i32 %x) {
 ; CHECK-LABEL: @bswap32_and_first_extra_use(
 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 %x, 16
 ; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 %x, 16
 ; CHECK-NEXT:    [[SWAPHALF:%.*]] = or i32 [[SHL]], [[SHR]]
 ; CHECK-NEXT:    [[T:%.*]] = and i32 [[SWAPHALF]], 16711935
-; CHECK-NEXT:    [[TSHL:%.*]] = shl nuw i32 [[T]], 8
-; CHECK-NEXT:    [[B:%.*]] = lshr i32 [[SWAPHALF]], 8
-; CHECK-NEXT:    [[BAND:%.*]] = and i32 [[B]], 16711935
-; CHECK-NEXT:    [[BSWAP:%.*]] = or i32 [[TSHL]], [[BAND]]
+; CHECK-NEXT:    [[BSWAP:%.*]] = call i32 @llvm.bswap.i32(i32 %x)
 ; CHECK-NEXT:    call void @extra_use(i32 [[T]])
 ; CHECK-NEXT:    ret i32 [[BSWAP]]
 ;
   %shl = shl i32 %x, 16
   %shr = lshr i32 %x, 16
   %swaphalf = or i32 %shl, %shr
   %t = and i32 %swaphalf, 16711935
   %tshl = shl nuw i32 %t, 8