[InstSimplify] Remove and(x.c) if all the known bits are handled just by x or c

[RKSimon]

Summary

This is a cut down version of what SimplifyMultipleUseDemandedBits tries to - if the RHS is a constant mask then see if the LHS known bits means that result bits are all known.

I wasn't sure how much we should be calling computeKnownBits in a lighter pass such as InstSimplify so I didn't generalise this to call computeKnownBits for a non-constant RHS as well, but we could very easily in the future, we could even consider moving InstCombinerImpl::SimplifyMultipleUseDemandedBits into InstSimplify?

Noticed as @spatel wondered if extending D131838 test coverage would be easier in InstSimplify

[spatel]

I tried a compile-time-tracker experiment with this patch applied, and it shows a slight, but noticeable compile-time hit, so I'd say it's not worth doing for a theoretical win:
https://llvm-compile-time-tracker.com/?config=NewPM-O3&stat=instructions&remote=rotateright

[RKSimon]

In D131955#3726046, @spatel wrote:

I tried a compile-time-tracker experiment with this patch applied, and it shows a slight, but noticeable compile-time hit, so I'd say it's not worth doing for a theoretical win:
https://llvm-compile-time-tracker.com/?config=NewPM-O3&stat=instructions&remote=rotateright

Agreed - I'll abandon this for now.

llvm/lib/Analysis/InstructionSimplify.cpp

if (match(Op0, m_c_Or(m_Value(X), m_Not(m_Value(Y)))) &&
     return X;
   if (match(Op1, m_c_Or(m_Value(X), m_Not(m_Value(Y)))) &&
       match(Op0, m_c_Or(m_Deferred(X), m_Deferred(Y))))
     return X;
 
   if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::And))
     return V;
 
-  // A mask that only clears known zeros of a shifted value is a no-op.
+  // If all of the demanded bits are known 1 on one side, return the other.
+  // These bits cannot contribute to the result of the 'and' in this
+  // context.
+  // TODO: Generalize this for Op1 KnownBits?
   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).isZero())
-      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).isZero())
+    KnownBits Known0 = computeKnownBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+    if ((Known0.Zero | *Mask).isAllOnes())
       return Op0;
+    if ((Known0.One | ~*Mask).isAllOnes())
+      return Op1;
   }
 
   // If we have a multiplication overflow check that is being 'and'ed with a
   // check that one of the multipliers is not zero, we can omit the 'and', and
   // only keep the overflow check.
   if (isCheckForZeroAndMulWithOverflow(Op0, Op1, true))
     return Op1;
   if (isCheckForZeroAndMulWithOverflow(Op1, Op0, true))

llvm/test/Transforms/InstSimplify/AndOrXor.ll

;
   ret i8 %r
 }
 
 ; `and` isn't needed if it doesn't actually change any bits.
 define i8 @noop_and_t0(i8 %x) {
 ; CHECK-LABEL: @noop_and_t0(
 ; CHECK-NEXT:    [[A:%.*]] = shl i8 [[X:%.*]], 3
 ; CHECK-NEXT:    [[B:%.*]] = lshr i8 [[A]], 2
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[B]], 62
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 [[B]]
 ;
   %a = shl i8 %x, 3
   %b = lshr i8 %a, 2
   %r = and i8 %b, 62
   ret i8 %r
 }
 define i8 @noop_and_t1(i8 %x) {
 ; CHECK-LABEL: @noop_and_t1(
 ; CHECK-NEXT:    [[A:%.*]] = shl i8 [[X:%.*]], 3
 ; CHECK-NEXT:    [[B:%.*]] = lshr i8 [[A]], 2
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[B]], 126
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 [[B]]
 ;
   %a = shl i8 %x, 3
   %b = lshr i8 %a, 2
   %r = and i8 %b, 126
   ret i8 %r
 }
 
 ; hidden simplifydemandedbits constant.
 define i8 @noop_and_t2(i8 %x) {
 ; CHECK-LABEL: @noop_and_t2(
-; CHECK-NEXT:    [[A:%.*]] = and i8 [[X:%.*]], 2
-; CHECK-NEXT:    [[B:%.*]] = or i8 [[A]], 127
-; CHECK-NEXT:    [[C:%.*]] = and i8 [[B]], 62
-; CHECK-NEXT:    ret i8 [[C]]
+; CHECK-NEXT:    ret i8 62
 ;
   %a = and i8 %x, 2
   %b = or i8 %a, 127
   %c = and i8 %b, 62
   ret i8 %c
 }