[InstSimplify] Perform known-bits analysis in SimplifyAndInst

[uweigand]

Summary

When simplifying an And operation, it can be useful to take
known bits of the LHS and RHS into consideration. The current
code already does that to some extent:

• Code at the end of SimplifyInstruction detects that *all* bits of the result of the And are known. However, this check only happens at the top level; it is not done for sub-expressions that are checked during simplification e.g. via ExpandBinOp.

• A very special case of known-bits analysis was added via https://reviews.llvm.org/D33221. This only handles the case where some bits on the LHS are known zero since the LHS is a shift operation, and the rest of the bits are known one on the RHS since it is a constant mask.

We can instead implement a more general known-bits analysis, to
handle three cases:

• If for each bit position, either LHS or RHS is known to be zero, the result must be 0.
• If for each bit position, either the LHS is known to be zero, or the RHS is known to be one, the result equals the LHS.
• And likewise with LHS and RHS swapped.

(The only other useful case seems to be if both LHS and RHS are
known to be all one bits. But that is already caught earlier
since in this case LHS == RHS.)

The shift-related special case is fully covered by the generic
case and can now be removed (all associated tests still pass).

One interesting scenario that is now simplified and wasn't
before is the case where sub-words are merged into a full word,
and subsequently a sub-word is extracted again. This is now
simplified to the original sub-word. (See new tests.)

[craig.topper]

Can something similar be done for visitOrInst? We have this tendency to add a transform for one and forget that the other is very similar.

[uweigand]

Sure, it would be possible to add the corresponding transforms to SimplifyOrInst. However, I have been unable to trigger this at all, with any workload I've tried. Should I still add the transforms anyway?

[craig.topper]

Do you have a real workload that benefits from this. Surely InstCombine would have caught it eventually?

[uweigand]

Yes, this benefits a real workload. This happens when the improved SimplifyAndInst now simplifies a partial result, which then allows *further* simplification in InstSimplify, in my case in ThreadBinOpOverPHI. This latter simplification doesn't seem to be done anywhere else.

lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   // (A | ?) & A = A
   if (match(Op0, m_c_Or(m_Specific(Op1), m_Value())))
     return Op1;
 
   // A & (A | ?) = A
   if (match(Op1, m_c_Or(m_Specific(Op0), m_Value())))
     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))
       return Op1;
   }
 
+  // Perform simplification based on known bits:
+  // If for each bit position, either LHS or RHS is known zero -> 0
+  // If for each bit position, LHS is known zero or RHS is known one -> LHS
+  // If for each bit position, LHS is known one or RHS is known zero -> RHS
+  KnownBits LHSKnown = computeKnownBits(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+  KnownBits RHSKnown = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+  if ((LHSKnown.Zero | RHSKnown.Zero).isAllOnesValue())
+    return Constant::getNullValue(Op0->getType());
+  if ((LHSKnown.Zero | RHSKnown.One).isAllOnesValue())
+    return Op0;
+  if ((LHSKnown.One | RHSKnown.Zero).isAllOnesValue())
+    return Op1;
+
   if (Value *V = simplifyAndOrOfICmps(Op0, Op1, true))
     return V;
 
   // Try some generic simplifications for associative operations.
   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
                                           MaxRecurse))
     return V;
 

test/Transforms/InstSimplify/AndOrXor.ll

 define i32 @reversed_not(i32 %a) {
 ; CHECK-LABEL: @reversed_not(
 ; CHECK-NEXT:    ret i32 -1
 ;
   %nega = xor i32 -1, %a
   %or = or i32 %a, %nega
   ret i32 %or
 }
+
+define i32 @zext_masked_hi(i8 %x, i32 %y) {
+; CHECK-LABEL: @zext_masked_hi(
+; CHECK-NEXT:    [[HI:%.*]] = and i32 %y, -256
+; CHECK-NEXT:    ret i32 [[HI]]
+;
+  %lo = zext i8 %x to i32
+  %hi = and i32 %y, -256
+  %or = or i32 %lo, %hi
+  %mask = and i32 %or, -256
+  ret i32 %mask
+}
+
+define i32 @zext_masked_lo(i8 %x, i32 %y) {
+; CHECK-LABEL: @zext_masked_lo(
+; CHECK-NEXT:    [[LO:%.*]] = zext i8 %x to i32
+; CHECK-NEXT:    ret i32 [[LO]]
+;
+  %lo = zext i8 %x to i32
+  %hi = and i32 %y, -256
+  %or = or i32 %lo, %hi
+  %mask = and i32 %or, 255
+  ret i32 %mask
+}
+