[InstCombine] Recognize another bswap idiom.

[• chatur01]

Summary

The byte-swap recognizer can now notice that this

uint32_t bswap(uint32_t x)
{
  x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;
  x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8;
  return x;
}

is a bswap. Fixes PR23863.

[rengolin]

I'm assuming that the bswap builtin will be triggered in different ways for different target, but that's not what the test here is trying to do, right?

Are there tests to make sure that this builtin expands to the correct instructions in the different types of ARM architectures? If not, I'd add that, too.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2211

You don't seem to have added tests for the AND case.

test/Transforms/InstCombine/bswap.ll

4

Not related to this patch, but we stopped using grep a long time ago...

Maybe it'd be simple enough to add the CHECK lines?

[• chatur01]

Hi Renato! Thanks for looking at my patch.

I'm assuming that the bswap builtin will be triggered in different ways for different target, but that's not what the test here is trying to do, right?

I thought my transformation was target-independent at this level.

Are there tests to make sure that this built-in expands to the correct instructions in the different types of ARM architectures? If not, I'd add that, too.

There's certainly some, I don't think they're exhaustive of all possibilities. I'll add the test I have to ARM tests at least, but I'll have to do a more intensive sweep of the current tests to make sure they're covering all the possibilities. Sorry for the oversight, this review will have to stall until I've completed that task.

Thanks again Renato.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2211

The test I added checks for the OrOfAnds:
%or6 = or i32 %shl3, %shr5
Where the misnamed "shl3" and "shr5" are and instructions.

test/Transforms/InstCombine/bswap.ll

4

Please can such a change come in a different commit?

[rengolin]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2211

Oh, yeah, now I see it. The OR/shifts were already there, too. ok.

test/Transforms/InstCombine/bswap.ll

4

np

[• chatur01]

Add tests for ARM backend lowering of the BSWAP instrinsic.

The testing coverage in the backend is better now, is this OK to commit?

[majnemer]

I'm confused as to why this needs any target specific tests. This is a change to IR canonicalization.

[• chatur01]

I'm confused as to why this needs any target specific tests. This is a change to IR canonicalization.

I was confused about that too, but I was attempting to address this review comment:

Are there tests to make sure that this built-in expands to the correct instructions in the different types of ARM architectures? If not, I'd add that, too.

Hopefully I won't be asked to go through the other backends as well now! :)

[majnemer]

In my experience

In D12637#251754, @chatur01 wrote:

I'm confused as to why this needs any target specific tests. This is a change to IR canonicalization.

I was confused about that too, but I was attempting to address this review comment:

Are there tests to make sure that this built-in expands to the correct instructions in the different types of ARM architectures? If not, I'd add that, too.

Hopefully I won't be asked to go through the other backends as well now! :)

Backends are expected to do intelligent things with llvm.bswap, I don't think the burden is on you to make sure they aren't doing the wrong thing.

[rengolin]

I didn't mean you should create the tests, I was just asking if there were tests elsewhere about the intrinsic to instructions conversion.

Not that it'd hurt to have the extra tests...

[• chatur01]

OK, sorry for the misunderstanding. Can I commit my original revision, and land the extra backend tests as part of a separate review?

[rengolin]

Yeah, LGTM. Sorry for holding you up.

[• chatur01]

Roll back to previous revision. I'll add the extra backend tests
in a separate revision.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) &&
       Value *Or = Builder->CreateOr(X, RHS);
       Or->takeName(Op0);
       return BinaryOperator::CreateXor(Or,
                             Builder->getInt(C1->getValue() & ~RHS->getValue()));
     }
 
     // Try to fold constant and into select arguments.
     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
       if (Instruction *R = FoldOpIntoSelect(I, SI))
         return R;
 
     if (isa<PHINode>(Op0))
       if (Instruction *NV = FoldOpIntoPhi(I))
         return NV;
   }
 
   Value *A = nullptr, *B = nullptr;
   ConstantInt *C1 = nullptr, *C2 = nullptr;
 
   // (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.
-  if (match(Op0, m_Or(m_Value(), m_Value())) ||
-      match(Op1, m_Or(m_Value(), m_Value())) ||
-      (match(Op0, m_LogicalShift(m_Value(), m_Value())) &&
-       match(Op1, m_LogicalShift(m_Value(), m_Value())))) {
+  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)
     if (Instruction *BSwap = MatchBSwap(I))
       return BSwap;
-  }
 
   // (X^C)|Y -> (X|Y)^C iff Y&C == 0
   if (Op0->hasOneUse() &&
       match(Op0, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
       MaskedValueIsZero(Op1, C1->getValue(), 0, &I)) {
     Value *NOr = Builder->CreateOr(A, Op1);
     NOr->takeName(Op0);
     return BinaryOperator::CreateXor(NOr, C1);

test/Transforms/InstCombine/bswap.ll

 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32"
 
 ; RUN: opt < %s -instcombine -S | \
-; RUN:    grep "call.*llvm.bswap" | count 6
+; RUN:    grep "call.*llvm.bswap" | count 7
 
 define i32 @test1(i32 %i) {
   %tmp1 = lshr i32 %i, 24   ; <i32> [#uses=1]
   %tmp3 = lshr i32 %i, 8    ; <i32> [#uses=1]
   %tmp4 = and i32 %tmp3, 65280    ; <i32> [#uses=1]
   %tmp5 = or i32 %tmp1, %tmp4   ; <i32> [#uses=1]
   %tmp7 = shl i32 %i, 8   ; <i32> [#uses=1]
   %tmp8 = and i32 %tmp7, 16711680   ; <i32> [#uses=1]
define i32 @test6(i32 %x) nounwind readnone {
   %tmp3 = or i32 %x.mask, %tmp    ; <i32> [#uses=1]
   %tmp4 = or i32 %tmp3, %tmp2   ; <i32> [#uses=1]
   %tmp5 = shl i32 %tmp4, 8    ; <i32> [#uses=1]
   %tmp6 = lshr i32 %x, 24   ; <i32> [#uses=1]
   %tmp7 = or i32 %tmp5, %tmp6   ; <i32> [#uses=1]
   ret i32 %tmp7
 }
 
+; PR23863
+define i32 @test7(i32 %x) {
+        %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
+        %shr5 = and i32 %and4, 16711935
+        %or6 = or i32 %shl3, %shr5
+        ret i32 %or6
+}