[InstSimplify] add folds for constant mask of value shifted by constant

[spatel]

Summary

I was investigating why a different simplification wasn't happening and noticed that we don't have this fold for the easy case with constants.

We would eventually catch these via demanded bits and computing known bits in InstCombine, but I think it's better to handle the simple cases as soon as possible as a matter of efficiency?

If there's a better way to do the APInt manipulations, please let me know.

[efriedma]

We don't want to write out a bunch of patterns here which are completely redundant, but this pattern in particular is likely to come up in code involving bitfields, so it seems fine.

lib/Analysis/InstructionSimplify.cpp

1770 ↗

(On Diff #99080)

(~*Mask).shl(*ShAmt).isNullValue()? Not sure that's better.

[spatel]

lib/Analysis/InstructionSimplify.cpp

1770 ↗

(On Diff #99080)

Looks better to me - we can use the inverted mask for both cases to make things symmetrical.
That also makes it easier to write the Alive tests:
http://rise4fun.com/Alive/lY0

[spatel]

Patch updated:

1. Inverted the mask constant to simplify the code and make the 2 cases symmetrical.
2. Modified the code comments to explain that logic.

[efriedma]

Looks good.

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
       (A == Op1 || B == Op1))
     return Op1;
 
   // A & (A | ?) = A
   if (match(Op1, m_Or(m_Value(A), m_Value(B))) &&
       (A == Op0 || B == Op0))
     return Op0;
 
+  // A mask that only clears known zeros of a shifted value is a no-op.
+  Value *X;
+  const APInt *Mask;
+  const APInt *ShAmt;
+  if (match(Op1, m_APInt(Mask))) {
+    // If all bits in the inverted and shifted mask are clear:
+    // and (shl X, ShAmt), Mask --> shl X, ShAmt
+    if (match(Op0, m_Shl(m_Value(X), m_APInt(ShAmt))) &&
+        (~(*Mask)).lshr(*ShAmt).isNullValue())
+      return Op0;
+
+    // If all bits in the inverted and shifted mask are clear:
+    // and (lshr X, ShAmt), Mask --> lshr X, ShAmt
+    if (match(Op0, m_LShr(m_Value(X), m_APInt(ShAmt))) &&
+        (~(*Mask)).shl(*ShAmt).isNullValue())
+      return Op0;
+  }
+
   // A & (-A) = A if A is a power of two or zero.
   if (match(Op0, m_Neg(m_Specific(Op1))) ||
       match(Op1, m_Neg(m_Specific(Op0)))) {
     if (isKnownToBeAPowerOfTwo(Op0, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
                                Q.DT))
       return Op0;
     if (isKnownToBeAPowerOfTwo(Op1, Q.DL, /*OrZero*/ true, 0, Q.AC, Q.CxtI,
                                Q.DT))

llvm/trunk/test/Transforms/InstSimplify/AndOrXor.ll

;
   %xor = xor i32 %nega, %b
   %or = or i32 %and, %xor
   ret i32 %or
 }
 
 define i8 @lshr_perfect_mask(i8 %x) {
 ; CHECK-LABEL: @lshr_perfect_mask(
 ; CHECK-NEXT:    [[SH:%.*]] = lshr i8 %x, 5
-; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[SH]], 7
-; CHECK-NEXT:    ret i8 [[MASK]]
+; CHECK-NEXT:    ret i8 [[SH]]
 ;
   %sh = lshr i8 %x, 5
   %mask = and i8 %sh, 7  ; 0x07
   ret i8 %mask
 }
 
 define <2 x i8> @lshr_oversized_mask_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @lshr_oversized_mask_splat(
 ; CHECK-NEXT:    [[SH:%.*]] = lshr <2 x i8> %x, <i8 5, i8 5>
-; CHECK-NEXT:    [[MASK:%.*]] = and <2 x i8> [[SH]], <i8 -121, i8 -121>
-; CHECK-NEXT:    ret <2 x i8> [[MASK]]
+; CHECK-NEXT:    ret <2 x i8> [[SH]]
 ;
   %sh = lshr <2 x i8> %x, <i8 5, i8 5>
   %mask = and <2 x i8> %sh, <i8 135, i8 135>  ; 0x87
   ret <2 x i8> %mask
 }
 
 define i8 @lshr_undersized_mask(i8 %x) {
 ; CHECK-LABEL: @lshr_undersized_mask(
 ; CHECK-NEXT:    [[SH:%.*]] = lshr i8 %x, 5
 ; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[SH]], -2
 ; CHECK-NEXT:    ret i8 [[MASK]]
 ;
   %sh = lshr i8 %x, 5
   %mask = and i8 %sh, -2  ; 0xFE
   ret i8 %mask
 }
 
 define <2 x i8> @shl_perfect_mask_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @shl_perfect_mask_splat(
 ; CHECK-NEXT:    [[SH:%.*]] = shl <2 x i8> %x, <i8 6, i8 6>
-; CHECK-NEXT:    [[MASK:%.*]] = and <2 x i8> [[SH]], <i8 -64, i8 -64>
-; CHECK-NEXT:    ret <2 x i8> [[MASK]]
+; CHECK-NEXT:    ret <2 x i8> [[SH]]
 ;
   %sh = shl <2 x i8> %x, <i8 6, i8 6>
   %mask = and <2 x i8> %sh, <i8 192, i8 192>  ; 0xC0
   ret <2 x i8> %mask
 }
 
 define i8 @shl_oversized_mask(i8 %x) {
 ; CHECK-LABEL: @shl_oversized_mask(
 ; CHECK-NEXT:    [[SH:%.*]] = shl i8 %x, 6
-; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[SH]], -61
-; CHECK-NEXT:    ret i8 [[MASK]]
+; CHECK-NEXT:    ret i8 [[SH]]
 ;
   %sh = shl i8 %x, 6
   %mask = and i8 %sh, 195  ; 0xC3
   ret i8 %mask
 }
 
 define <2 x i8> @shl_undersized_mask_splat(<2 x i8> %x) {
 ; CHECK-LABEL: @shl_undersized_mask_splat(