[InstCombine] Adjusting bswap pattern to the new masked shl canonization

[opaparo]

Summary

A previous patch, D41233, introduced a new canonical form for a masked shl.
As a result, some of the bswap patterns were not recognized, and some bswap tests were temporarily altered.
This patch is a fix for that issue, making sure that those patterns will once again be recognized and transformed.

[hfinkel]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1431–1432

A comment here explaining why (A & B) | (C & D) will be canonicalized into (A << B) | (C & D) in all relevant cases would be useful.

[opaparo]

Added a comment explaining the change of pattern in the bswap idiom detection.

[hfinkel]

LGTM

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1436

canonic -> canonical

1437

canonic -> canonical

[spatel]

If I understand the relationship correctly between the patches, this patch would move an existing failure of bswap matching to a different place. Shouldn't we improve the matching instead? Ie, I was expecting an independent patch from D41233 here.

I added tests at rL322206 to demonstrate.

[spatel]

Not sure if my question was read - requesting a change based on that.

[opaparo]

The required changes were made in D45731

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
 
   // (A | B) | C  and  A | (B | C)                  -> bswap if possible.
   bool OrOfOrs = match(Op0, m_Or(m_Value(), m_Value())) ||
                  match(Op1, m_Or(m_Value(), m_Value()));
 
   // (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()));
+  // (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).
+  // Note the different canonic forms for 'shl's and 'shr's. For each of them
+  // the canonic form is set such that the 'and' constants are minimal (the
+  // 'and' is before the shift for 'shl' and after the shift for 'shr').
+  bool OrOfShiftAndAnd = (match(Op0, m_And(m_Value(), m_Value())) &&
+                          match(Op1, m_LogicalShift(m_Value(), m_Value()))) ||
+                         (match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
+                          match(Op1, m_And(m_Value(), m_Value())));
 
-  if (!OrOfOrs && !OrOfShifts && !OrOfAnds)
+  if (!OrOfOrs && !OrOfShifts && !OrOfShiftAndAnd)
     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

;
   %tmp6 = lshr i32 %x, 24
   %tmp7 = or i32 %tmp5, %tmp6
   ret i32 %tmp7
 }
 
 ; PR23863
 define i32 @test7(i32 %x) {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[SHL:%.*]] = shl i32 %x, 16
-; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 %x, 16
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], [[SHR]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR]], 16711935
-; CHECK-NEXT:    [[SHL3:%.*]] = shl nuw i32 [[TMP1]], 8
-; CHECK-NEXT:    [[AND4:%.*]] = lshr i32 [[OR]], 8
-; CHECK-NEXT:    [[SHR5:%.*]] = and i32 [[AND4]], 16711935
-; CHECK-NEXT:    [[OR6:%.*]] = or i32 [[SHL3]], [[SHR5]]
+; CHECK-NEXT:    [[OR6:%.*]] = call i32 @llvm.bswap.i32(i32 %x)
 ; CHECK-NEXT:    ret i32 [[OR6]]
 ;
   %shl = shl i32 %x, 16
   %shr = lshr i32 %x, 16
   %or = or i32 %shl, %shr
   %and2 = shl i32 %or, 8
   %shl3 = and i32 %and2, -16711936
   %and4 = lshr i32 %or, 8
;
   %shl = shl i32 %conv, 8
   %or = or i32 %shr, %shl
   %conv2 = trunc i32 %or to i16
   ret i16 %conv2
 }
 
 define i16 @test10(i32 %a) {
 ; CHECK-LABEL: @test10(
-; CHECK-NEXT:    [[SHR1:%.*]] = lshr i32 %a, 8
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[SHR1]], 255
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %a, 255
-; CHECK-NEXT:    [[SHL1:%.*]] = shl nuw nsw i32 [[TMP1]], 8
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[AND1]], [[SHL1]]
-; CHECK-NEXT:    [[CONV:%.*]] = trunc i32 [[OR]] to i16
-; CHECK-NEXT:    ret i16 [[CONV]]
+; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %a to i16
+; CHECK-NEXT:    [[REV:%.*]] = call i16 @llvm.bswap.i16(i16 [[TRUNC]])
+; CHECK-NEXT:    ret i16 [[REV]]
 ;
   %shr1 = lshr i32 %a, 8
   %and1 = and i32 %shr1, 255
   %and2 = shl i32 %a, 8
   %shl1 = and i32 %and2, 65280
   %or = or i32 %and1, %shl1
   %conv = trunc i32 %or to i16
   ret i16 %conv
 }