[KnownBits] Define and use intersectWith and unionWith

[foad]

Summary

Define intersectWith and unionWith as two complementary ways of
combining KnownBits. The names are chosen for consistency with
ConstantRange.

Deprecate commonBits as a synonym for intersectWith.

[goldstein.w.n]

llvm/include/llvm/Support/KnownBits.h

297

Personally the text after the 'i.e' seems more useful for understanding the code (and I think matches the motivation for the code better) so I would swap the order.

'Returns the information that is known to be true for both this (aka LHS) and RHS. Another way to look at it is the greatest lower bound of LHS and RHS.'

Likewise below.

310

Since we already have KnownBits::commonBits maybe instead of adding the new essentially equivilent meet API, we could just add a non-static version of commonBits (so you could do Known.commonBits(Known2)). Seems like an all around simpler change and probably more familiar for people who have used the interface.

[foad]

Reword descriptions.

[foad]

llvm/include/llvm/Support/KnownBits.h

310

Personally I think having good and complementary names for the two operations is more important than maintaining the old name, even if it is familiar to some people.

[goldstein.w.n]

llvm/include/llvm/Support/KnownBits.h

310

Fair enough.

[goldstein.w.n]

LGTM.

[nikic]

Two pieces of feedback on the API:

• Can we call this union and intersect instead of join and meet? I think this will be more obvious to most readers.
• The fact that the instance methods modify the value in place rather than returning a new one is rather surprising -- isn't the usual convention for KnownBits methods to return the result?

[foad]

• Can we call this union and intersect instead of join and meet? I think this will be more obvious to most readers.

No because union is a keyword :-( Apart from that I think it is a good candidate. I did think seriously about union/intersect, as well as other options like and/or.

• The fact that the instance methods modify the value in place rather than returning a new one is rather surprising -- isn't the usual convention for KnownBits methods to return the result?

Maybe but I don't think there is much consistency. I chose to do it this way for a couple of reasons:

1. It is based on the way we implement binary operators like &. The work is done in the assignment form of the operator, &=, and the various non-assignment forms are implemented in terms of that. (And this was based on me googling for best practice for overloading operators for value-like classes.)
2. The meet-assignment form seems to be very useful in practice.

But I don't mind changing it if there is consensus that having A.meet(B) modify A is surprising.

[barannikov88]

meet and join sound like advanced stuff from something called lattice theory.
Why don't just use overloaded operators?

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

387

Known = LHS & RHS;
?

[foad]

Why don't just use overloaded operators?

Because operator& already does something different. It returns the known bits of the expression A&B, given the known bits of A and the known bits of B. That was probably my idea. I thought it would be nice if simple operators like A&B, A+B, A<<B etc all worked consistently in that way. But I guess we could abandon that plan and change the meaning of operator&.

[barannikov88]

In D150443#4340138, @foad wrote:

Why don't just use overloaded operators?

Because operator& already does something different. It returns the known bits of the expression A&B, given the known bits of A and the known bits of B.

This may be a bit surprising, but in a way it makes sense.

[nikic]

In D150443#4340036, @foad wrote:

• Can we call this union and intersect instead of join and meet? I think this will be more obvious to most readers.

No because union is a keyword :-( Apart from that I think it is a good candidate. I did think seriously about union/intersect, as well as other options like and/or.

Oh, so that's why the corresponding ConstantRange methods are called unionWith and intersectWith...

[foad]

Change names.

[foad]

In D150443#4340284, @nikic wrote:

In D150443#4340036, @foad wrote:

• Can we call this union and intersect instead of join and meet? I think this will be more obvious to most readers.

No because union is a keyword :-( Apart from that I think it is a good candidate. I did think seriously about union/intersect, as well as other options like and/or.

Oh, so that's why the corresponding ConstantRange methods are called unionWith and intersectWith...

Thanks, I did not know about them. It seems best to copy that design.

[nikic]

LGTM

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

241

Side note: Should use isUnknown() here.

[foad]

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

241

71ac47f39120e77c7364799ca30cbd59b5caf5f7

llvm/include/llvm/Support/KnownBits.h

unsigned countMaxActiveBits() const {
     return getBitWidth() - countMinLeadingZeros();
   }
 
   /// Create known bits from a known constant.
   static KnownBits makeConstant(const APInt &C) {
     return KnownBits(~C, C);
   }
 
+  /// Returns KnownBits information that is known to be true for both this and
+  /// RHS.
+  ///
+  /// When an operation is known to return one of its operands, this can be used
+  /// to combine information about the known bits of the operands to get the
+  /// information that must be true about the result.
+  KnownBits intersectWith(const KnownBits &RHS) const {
+    return KnownBits(Zero & RHS.Zero, One & RHS.One);
+  }
+
+  /// Returns KnownBits information that is known to be true for either this or
+  /// RHS or both.
+  ///
+  /// This can be used to combine different sources of information about the
+  /// known bits of a single value, e.g. information about the low bits and the
+  /// high bits of the result of a multiplication.
+  KnownBits unionWith(const KnownBits &RHS) const {
+    return KnownBits(Zero | RHS.Zero, One | RHS.One);
+  }
+
   /// Compute known bits common to LHS and RHS.
+  LLVM_DEPRECATED("use intersectWith instead", "intersectWith")
   static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
-    return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
+    return LHS.intersectWith(RHS);
   }
 
   /// Return true if LHS and RHS have no common bits set.
   static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
     return (LHS.Zero | RHS.Zero).isAllOnes();
   }
 
   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.

llvm/lib/Analysis/ValueTracking.cpp

static void computeKnownBitsFromCmp(const Value *V, const ICmpInst *Cmp,
   switch (Cmp->getPredicate()) {
   default:
     break;
   case ICmpInst::ICMP_EQ:
     // assume(v = a)
     if (match(Cmp, m_c_ICmp(Pred, m_V, m_Value(A)))) {
       KnownBits RHSKnown =
           computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
-      Known.Zero |= RHSKnown.Zero;
-      Known.One |= RHSKnown.One;
+      Known = Known.unionWith(RHSKnown);
       // assume(v & b = a)
     } else if (match(Cmp,
                      m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A)))) {
       KnownBits RHSKnown =
           computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
       KnownBits MaskKnown =
           computeKnownBits(B, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
if (match(Cmp, m_c_ICmp(Pred, m_V, m_Value(A)))) {
                                    m_Value(A))) &&
                C < BitWidth) {
       KnownBits RHSKnown =
           computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
 
       // For those bits in RHS that are known, we can propagate them to known
       // bits in V shifted to the right by C.
       RHSKnown.Zero.lshrInPlace(C);
-      Known.Zero |= RHSKnown.Zero;
       RHSKnown.One.lshrInPlace(C);
-      Known.One |= RHSKnown.One;
+      Known = Known.unionWith(RHSKnown);
       // assume(~(v << c) = a)
     } else if (match(Cmp, m_c_ICmp(Pred, m_Not(m_Shl(m_V, m_ConstantInt(C))),
                                    m_Value(A))) &&
                C < BitWidth) {
       KnownBits RHSKnown =
           computeKnownBits(A, Depth + 1, QueryNoAC).anyextOrTrunc(BitWidth);
       // For those bits in RHS that are known, we can propagate them inverted
       // to known bits in V shifted to the right by C.
for (unsigned ShiftAmt = 0; ShiftAmt < BitWidth; ++ShiftAmt) {
     if (ShiftAmt == 0) {
       if (!ShifterOperandIsNonZero)
         ShifterOperandIsNonZero =
             isKnownNonZero(I->getOperand(1), DemandedElts, Depth + 1, Q);
       if (*ShifterOperandIsNonZero)
         continue;
     }
 
-    Known = KnownBits::commonBits(
-        Known, KF(Known2, KnownBits::makeConstant(APInt(32, ShiftAmt))));
+    Known = Known.intersectWith(
+        KF(Known2, KnownBits::makeConstant(APInt(32, ShiftAmt))));
   }
 
   // If the known bits conflict, the result is poison. Return a 0 and hope the
   // caller can further optimize that.
   if (Known.hasConflict())
     Known.setAllZero();
 }
 
if (SelectPatternResult::isMinOrMax(SPF)) {
       }
       break;
     }
 
     computeKnownBits(I->getOperand(2), Known, Depth + 1, Q);
     computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
 
     if (SPF == SPF_ABS) {
       // RHS from matchSelectPattern returns the negation part of abs pattern.
       // If the negate has an NSW flag we can assume the sign bit of the result
       // will be 0 because that makes abs(INT_MIN) undefined.
       if (match(RHS, m_Neg(m_Specific(LHS))) &&
           Q.IIQ.hasNoSignedWrap(cast<OverflowingBinaryOperator>(RHS)))
         Known.Zero.setSignBit();
if (Depth < MaxAnalysisRecursionDepth - 1 && Known.isUnknown()) {
               default:
                 // TODO - add additional integer predicate handling.
                 break;
               }
             }
           }
         }
 
-        Known = KnownBits::commonBits(Known, Known2);
+        Known = Known.intersectWith(Known2);
         // If all bits have been ruled out, there's no need to check
         // more operands.
         if (Known.isUnknown())
           break;
       }
     }
     break;
   }
   case Instruction::Call:
   case Instruction::Invoke:
     // If range metadata is attached to this call, set known bits from that,
     // and then intersect with known bits based on other properties of the
     // function.
     if (MDNode *MD =
             Q.IIQ.getMetadata(cast<Instruction>(I), LLVMContext::MD_range))
       computeKnownBitsFromRangeMetadata(*MD, Known);
     if (const Value *RV = cast<CallBase>(I)->getReturnedArgOperand()) {
       computeKnownBits(RV, Known2, Depth + 1, Q);
-      Known.Zero |= Known2.Zero;
-      Known.One |= Known2.One;
+      Known = Known.unionWith(Known2);
     }
     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
       switch (II->getIntrinsicID()) {
       default: break;
       case Intrinsic::abs: {
         computeKnownBits(I->getOperand(0), Known2, Depth + 1, Q);
         bool IntMinIsPoison = match(II->getArgOperand(1), m_One());
         Known = Known2.abs(IntMinIsPoison);
if (!!DemandedLHS) {
       computeKnownBits(LHS, DemandedLHS, Known, Depth + 1, Q);
       // If we don't know any bits, early out.
       if (Known.isUnknown())
         break;
     }
     if (!!DemandedRHS) {
       const Value *RHS = Shuf->getOperand(1);
       computeKnownBits(RHS, DemandedRHS, Known2, Depth + 1, Q);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
     break;
   }
   case Instruction::InsertElement: {
     if (isa<ScalableVectorType>(I->getType())) {
       Known.resetAll();
       return;
     }
if (DemandedElts[EltIdx]) {
       if (Known.isUnknown())
         break;
     }
     // We don't need the base vector element that has been inserted.
     APInt DemandedVecElts = DemandedElts;
     DemandedVecElts.clearBit(EltIdx);
     if (!!DemandedVecElts) {
       computeKnownBits(Vec, DemandedVecElts, Known2, Depth + 1, Q);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
     break;
   }
   case Instruction::ExtractElement: {
     // Look through extract element. If the index is non-constant or
     // out-of-range demand all elements, otherwise just the extracted element.
     const Value *Vec = I->getOperand(0);
     const Value *Idx = I->getOperand(1);

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

void GISelKnownBits::computeKnownBitsMin(Register Src0, Register Src1,
   // If we don't know any bits, early out.
   if (Known.isUnknown())
     return;
 
   KnownBits Known2;
   computeKnownBitsImpl(Src0, Known2, DemandedElts, Depth);
 
   // Only known if known in both the LHS and RHS.
-  Known = KnownBits::commonBits(Known, Known2);
+  Known = Known.intersectWith(Known2);
 }
 
 // Bitfield extract is computed as (Src >> Offset) & Mask, where Mask is
 // created using Width. Use this function when the inputs are KnownBits
 // objects. TODO: Move this KnownBits.h if this is usable in more cases.
 static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown,
                              const KnownBits &OffsetKnown,
                              const KnownBits &WidthKnown) {
case TargetOpcode::G_BUILD_VECTOR: {
     for (unsigned i = 0, e = MI.getNumOperands() - 1; i < e; ++i) {
       if (!DemandedElts[i])
         continue;
 
       computeKnownBitsImpl(MI.getOperand(i + 1).getReg(), Known2, DemandedElts,
                            Depth + 1);
 
       // Known bits are the values that are shared by every demanded element.
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
 
       // If we don't know any bits, early out.
       if (Known.isUnknown())
         break;
     }
     break;
   }
   case TargetOpcode::COPY:
for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
       //
       // We can't use NoSubRegister by name as it's defined by each target but
       // it's always defined to be 0 by tablegen.
       if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ &&
           MRI.getType(SrcReg).isValid()) {
         // For COPYs we don't do anything, don't increase the depth.
         computeKnownBitsImpl(SrcReg, Known2, DemandedElts,
                              Depth + (Opcode != TargetOpcode::COPY));
-        Known = KnownBits::commonBits(Known, Known2);
+        Known = Known.intersectWith(Known2);
         // If we reach a point where we don't know anything
         // just stop looking through the operands.
         if (Known.isUnknown())
           break;
       } else {
         // We know nothing.
         Known = KnownBits(BitWidth);
         break;
       }
     }
     break;

llvm/lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp

if (!SrcReg.isVirtual()) {
       return;
     }
     const LiveOutInfo *SrcLOI = GetLiveOutRegInfo(SrcReg, BitWidth);
     if (!SrcLOI) {
       DestLOI.IsValid = false;
       return;
     }
     DestLOI.NumSignBits = std::min(DestLOI.NumSignBits, SrcLOI->NumSignBits);
-    DestLOI.Known = KnownBits::commonBits(DestLOI.Known, SrcLOI->Known);
+    DestLOI.Known = DestLOI.Known.intersectWith(SrcLOI->Known);
   }
 }
 
 /// setArgumentFrameIndex - Record frame index for the byval
 /// argument. This overrides previous frame index entry for this argument,
 /// if any.
 void FunctionLoweringInfo::setArgumentFrameIndex(const Argument *A,
                                                  int FI) {

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

for (unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
       // BUILD_VECTOR can implicitly truncate sources, we must handle this.
       if (SrcOp.getValueSizeInBits() != BitWidth) {
         assert(SrcOp.getValueSizeInBits() > BitWidth &&
                "Expected BUILD_VECTOR implicit truncation");
         Known2 = Known2.trunc(BitWidth);
       }
 
       // Known bits are the values that are shared by every demanded element.
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
 
       // If we don't know any bits, early out.
       if (Known.isUnknown())
         break;
     }
     break;
   case ISD::VECTOR_SHUFFLE: {
     assert(!Op.getValueType().isScalableVector());
     // Collect the known bits that are shared by every vector element referenced
     // by the shuffle.
     APInt DemandedLHS, DemandedRHS;
     const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(Op);
     assert(NumElts == SVN->getMask().size() && "Unexpected vector size");
     if (!getShuffleDemandedElts(NumElts, SVN->getMask(), DemandedElts,
                                 DemandedLHS, DemandedRHS))
       break;
 
     // Known bits are the values that are shared by every demanded element.
     Known.Zero.setAllBits(); Known.One.setAllBits();
     if (!!DemandedLHS) {
       SDValue LHS = Op.getOperand(0);
       Known2 = computeKnownBits(LHS, DemandedLHS, Depth + 1);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
     // If we don't know any bits, early out.
     if (Known.isUnknown())
       break;
     if (!!DemandedRHS) {
       SDValue RHS = Op.getOperand(1);
       Known2 = computeKnownBits(RHS, DemandedRHS, Depth + 1);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
     break;
   }
   case ISD::CONCAT_VECTORS: {
     if (Op.getValueType().isScalableVector())
       break;
     // Split DemandedElts and test each of the demanded subvectors.
     Known.Zero.setAllBits(); Known.One.setAllBits();
     EVT SubVectorVT = Op.getOperand(0).getValueType();
     unsigned NumSubVectorElts = SubVectorVT.getVectorNumElements();
     unsigned NumSubVectors = Op.getNumOperands();
     for (unsigned i = 0; i != NumSubVectors; ++i) {
       APInt DemandedSub =
           DemandedElts.extractBits(NumSubVectorElts, i * NumSubVectorElts);
       if (!!DemandedSub) {
         SDValue Sub = Op.getOperand(i);
         Known2 = computeKnownBits(Sub, DemandedSub, Depth + 1);
-        Known = KnownBits::commonBits(Known, Known2);
+        Known = Known.intersectWith(Known2);
       }
       // If we don't know any bits, early out.
       if (Known.isUnknown())
         break;
     }
     break;
   }
   case ISD::INSERT_SUBVECTOR: {
case ISD::INSERT_SUBVECTOR: {
     Known.Zero.setAllBits();
     if (!!DemandedSubElts) {
       Known = computeKnownBits(Sub, DemandedSubElts, Depth + 1);
       if (Known.isUnknown())
         break; // early-out.
     }
     if (!!DemandedSrcElts) {
       Known2 = computeKnownBits(Src, DemandedSrcElts, Depth + 1);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
     break;
   }
   case ISD::EXTRACT_SUBVECTOR: {
     // Offset the demanded elts by the subvector index.
     SDValue Src = Op.getOperand(0);
     // Bail until we can represent demanded elements for scalable vectors.
     if (Op.getValueType().isScalableVector() || Src.getValueType().isScalableVector())
if ((SubBitWidth % BitWidth) == 0) {
           APIntOps::ScaleBitMask(DemandedElts, NumElts / SubScale);
       Known2 = computeKnownBits(N0, SubDemandedElts, Depth + 1);
 
       Known.Zero.setAllBits(); Known.One.setAllBits();
       for (unsigned i = 0; i != NumElts; ++i)
         if (DemandedElts[i]) {
           unsigned Shifts = IsLE ? i : NumElts - 1 - i;
           unsigned Offset = (Shifts % SubScale) * BitWidth;
-          Known = KnownBits::commonBits(Known,
-                                        Known2.extractBits(BitWidth, Offset));
+          Known = Known.intersectWith(Known2.extractBits(BitWidth, Offset));
           // If we don't know any bits, early out.
           if (Known.isUnknown())
             break;
         }
     }
     break;
   }
   case ISD::AND:
KnownBits SelectionDAG::computeKnownBits(SDValue Op, const APInt &DemandedElts,
   case ISD::VSELECT:
     Known = computeKnownBits(Op.getOperand(2), DemandedElts, Depth+1);
     // If we don't know any bits, early out.
     if (Known.isUnknown())
       break;
     Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth+1);
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   case ISD::SELECT_CC:
     Known = computeKnownBits(Op.getOperand(3), DemandedElts, Depth+1);
     // If we don't know any bits, early out.
     if (Known.isUnknown())
       break;
     Known2 = computeKnownBits(Op.getOperand(2), DemandedElts, Depth+1);
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   case ISD::SMULO:
   case ISD::UMULO:
     if (Op.getResNo() != 1)
       break;
     // The boolean result conforms to getBooleanContents.
     // If we know the result of a setcc has the top bits zero, use this info.
     // We know that we have an integer-based boolean since these operations
if (ConstantSDNode *C = isConstOrConstSplat(Op.getOperand(2), DemandedElts)) {
         Known2.One.lshrInPlace(BitWidth - Amt);
         Known2.Zero.lshrInPlace(BitWidth - Amt);
       } else {
         Known.One <<= BitWidth - Amt;
         Known.Zero <<= BitWidth - Amt;
         Known2.One.lshrInPlace(Amt);
         Known2.Zero.lshrInPlace(Amt);
       }
-      Known.One |= Known2.One;
-      Known.Zero |= Known2.Zero;
+      Known = Known.unionWith(Known2);
     }
     break;
   case ISD::SHL_PARTS:
   case ISD::SRA_PARTS:
   case ISD::SRL_PARTS: {
     assert((Op.getResNo() == 0 || Op.getResNo() == 1) && "Unknown result");
 
     // Collect lo/hi source values and concatenate.
if (CEltNo && CEltNo->getAPIntValue().ult(NumElts)) {
       unsigned EltIdx = CEltNo->getZExtValue();
       DemandedVal = !!DemandedElts[EltIdx];
       DemandedVecElts.clearBit(EltIdx);
     }
     Known.One.setAllBits();
     Known.Zero.setAllBits();
     if (DemandedVal) {
       Known2 = computeKnownBits(InVal, Depth + 1);
-      Known = KnownBits::commonBits(Known, Known2.zextOrTrunc(BitWidth));
+      Known = Known.intersectWith(Known2.zextOrTrunc(BitWidth));
     }
     if (!!DemandedVecElts) {
       Known2 = computeKnownBits(InVec, DemandedVecElts, Depth + 1);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
     break;
   }
   case ISD::BITREVERSE: {
     Known2 = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     Known = Known2.reverseBits();
     break;
   }

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

case ISD::INSERT_VECTOR_ELT: {
     Known = KnownScl.anyextOrTrunc(BitWidth);
 
     KnownBits KnownVec;
     if (SimplifyDemandedBits(Vec, DemandedBits, DemandedVecElts, KnownVec, TLO,
                              Depth + 1))
       return true;
 
     if (!!DemandedVecElts)
-      Known = KnownBits::commonBits(Known, KnownVec);
+      Known = Known.intersectWith(KnownVec);
 
     return false;
   }
   case ISD::INSERT_SUBVECTOR: {
     if (VT.isScalableVector())
       return false;
     // Demand any elements from the subvector and the remainder from the src its
     // inserted into.
if (SimplifyDemandedBits(Sub, DemandedBits, DemandedSubElts, KnownSub, TLO,
       return true;
     if (SimplifyDemandedBits(Src, DemandedBits, DemandedSrcElts, KnownSrc, TLO,
                              Depth + 1))
       return true;
 
     Known.Zero.setAllBits();
     Known.One.setAllBits();
     if (!!DemandedSubElts)
-      Known = KnownBits::commonBits(Known, KnownSub);
+      Known = Known.intersectWith(KnownSub);
     if (!!DemandedSrcElts)
-      Known = KnownBits::commonBits(Known, KnownSrc);
+      Known = Known.intersectWith(KnownSrc);
 
     // Attempt to avoid multi-use src if we don't need anything from it.
     if (!DemandedBits.isAllOnes() || !DemandedSubElts.isAllOnes() ||
         !DemandedSrcElts.isAllOnes()) {
       SDValue NewSub = SimplifyMultipleUseDemandedBits(
           Sub, DemandedBits, DemandedSubElts, TLO.DAG, Depth + 1);
       SDValue NewSrc = SimplifyMultipleUseDemandedBits(
           Src, DemandedBits, DemandedSrcElts, TLO.DAG, Depth + 1);
case ISD::CONCAT_VECTORS: {
     for (unsigned i = 0; i != NumSubVecs; ++i) {
       APInt DemandedSubElts =
           DemandedElts.extractBits(NumSubElts, i * NumSubElts);
       if (SimplifyDemandedBits(Op.getOperand(i), DemandedBits, DemandedSubElts,
                                Known2, TLO, Depth + 1))
         return true;
       // Known bits are shared by every demanded subvector element.
       if (!!DemandedSubElts)
-        Known = KnownBits::commonBits(Known, Known2);
+        Known = Known.intersectWith(Known2);
     }
     break;
   }
   case ISD::VECTOR_SHUFFLE: {
     assert(!VT.isScalableVector());
     ArrayRef<int> ShuffleMask = cast<ShuffleVectorSDNode>(Op)->getMask();
 
     // Collect demanded elements from shuffle operands..
     APInt DemandedLHS, DemandedRHS;
     if (!getShuffleDemandedElts(NumElts, ShuffleMask, DemandedElts, DemandedLHS,
                                 DemandedRHS))
       break;
 
     if (!!DemandedLHS || !!DemandedRHS) {
       SDValue Op0 = Op.getOperand(0);
       SDValue Op1 = Op.getOperand(1);
 
       Known.Zero.setAllBits();
       Known.One.setAllBits();
       if (!!DemandedLHS) {
         if (SimplifyDemandedBits(Op0, DemandedBits, DemandedLHS, Known2, TLO,
                                  Depth + 1))
           return true;
-        Known = KnownBits::commonBits(Known, Known2);
+        Known = Known.intersectWith(Known2);
       }
       if (!!DemandedRHS) {
         if (SimplifyDemandedBits(Op1, DemandedBits, DemandedRHS, Known2, TLO,
                                  Depth + 1))
           return true;
-        Known = KnownBits::commonBits(Known, Known2);
+        Known = Known.intersectWith(Known2);
       }
 
       // Attempt to avoid multi-use ops if we don't need anything from them.
       SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
           Op0, DemandedBits, DemandedLHS, TLO.DAG, Depth + 1);
       SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
           Op1, DemandedBits, DemandedRHS, TLO.DAG, Depth + 1);
       if (DemandedOp0 || DemandedOp1) {
case ISD::SELECT:
     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
     // If the operands are constants, see if we can simplify them.
     if (ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
       return true;
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   case ISD::VSELECT:
     if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, DemandedElts,
                              Known, TLO, Depth + 1))
       return true;
     if (SimplifyDemandedBits(Op.getOperand(1), DemandedBits, DemandedElts,
                              Known2, TLO, Depth + 1))
       return true;
     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   case ISD::SELECT_CC:
     if (SimplifyDemandedBits(Op.getOperand(3), DemandedBits, Known, TLO,
                              Depth + 1))
       return true;
     if (SimplifyDemandedBits(Op.getOperand(2), DemandedBits, Known2, TLO,
                              Depth + 1))
       return true;
     assert(!Known.hasConflict() && "Bits known to be one AND zero?");
     assert(!Known2.hasConflict() && "Bits known to be one AND zero?");
 
     // If the operands are constants, see if we can simplify them.
     if (ShrinkDemandedConstant(Op, DemandedBits, DemandedElts, TLO))
       return true;
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   case ISD::SETCC: {
     SDValue Op0 = Op.getOperand(0);
     SDValue Op1 = Op.getOperand(1);
     ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(2))->get();
     // If (1) we only need the sign-bit, (2) the setcc operands are the same
     // width as the setcc result, and (3) the result of a setcc conforms to 0 or
     // -1, we may be able to bypass the setcc.
if (ConstantSDNode *SA = isConstOrConstSplat(Op2, DemandedElts)) {
       if (SimplifyDemandedBits(Op1, Demanded1, DemandedElts, Known, TLO,
                                Depth + 1))
         return true;
 
       Known2.One <<= (IsFSHL ? Amt : (BitWidth - Amt));
       Known2.Zero <<= (IsFSHL ? Amt : (BitWidth - Amt));
       Known.One.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt);
       Known.Zero.lshrInPlace(IsFSHL ? (BitWidth - Amt) : Amt);
-      Known.One |= Known2.One;
-      Known.Zero |= Known2.Zero;
+      Known = Known.unionWith(Known2);
 
       // Attempt to avoid multi-use ops if we don't need anything from them.
       if (!Demanded0.isAllOnes() || !Demanded1.isAllOnes() ||
           !DemandedElts.isAllOnes()) {
         SDValue DemandedOp0 = SimplifyMultipleUseDemandedBits(
             Op0, Demanded0, DemandedElts, TLO.DAG, Depth + 1);
         SDValue DemandedOp1 = SimplifyMultipleUseDemandedBits(
             Op1, Demanded1, DemandedElts, TLO.DAG, Depth + 1);

llvm/lib/Support/KnownBits.cpp

KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) {
   if (RHS.getMinValue().uge(LHS.getMaxValue()))
     return RHS;
 
   // If the result of the umax is LHS then it must be greater than or equal to
   // the minimum possible value of RHS. Likewise for RHS. Any known bits that
   // are common to these two values are also known in the result.
   KnownBits L = LHS.makeGE(RHS.getMinValue());
   KnownBits R = RHS.makeGE(LHS.getMinValue());
-  return KnownBits::commonBits(L, R);
+  return L.intersectWith(R);
 }
 
 KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) {
   // Flip the range of values: [0, 0xFFFFFFFF] <-> [0xFFFFFFFF, 0]
   auto Flip = [](const KnownBits &Val) { return KnownBits(Val.One, Val.Zero); };
   return Flip(umax(Flip(LHS), Flip(RHS)));
 }
 
for (uint64_t ShiftAmt = MinShiftAmount.getZExtValue(),
       // Skip if the shift amount is impossible.
       if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
           (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
         continue;
       KnownBits SpecificShift;
       SpecificShift.Zero = LHS.Zero << ShiftAmt;
       SpecificShift.Zero.setLowBits(ShiftAmt);
       SpecificShift.One = LHS.One << ShiftAmt;
-      Known = KnownBits::commonBits(Known, SpecificShift);
+      Known = Known.intersectWith(SpecificShift);
       if (Known.isUnknown())
         break;
     }
   }
 
   Known.Zero.setLowBits(MinTrailingZeros);
   return Known;
 }
for (uint64_t ShiftAmt = MinShiftAmount.getZExtValue(),
       // Skip if the shift amount is impossible.
       if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
           (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
         continue;
       KnownBits SpecificShift = LHS;
       SpecificShift.Zero.lshrInPlace(ShiftAmt);
       SpecificShift.Zero.setHighBits(ShiftAmt);
       SpecificShift.One.lshrInPlace(ShiftAmt);
-      Known = KnownBits::commonBits(Known, SpecificShift);
+      Known = Known.intersectWith(SpecificShift);
       if (Known.isUnknown())
         break;
     }
   }
 
   Known.Zero.setHighBits(MinLeadingZeros);
   return Known;
 }
for (uint64_t ShiftAmt = MinShiftAmount.getZExtValue(),
          ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
       // Skip if the shift amount is impossible.
       if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
           (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
         continue;
       KnownBits SpecificShift = LHS;
       SpecificShift.Zero.ashrInPlace(ShiftAmt);
       SpecificShift.One.ashrInPlace(ShiftAmt);
-      Known = KnownBits::commonBits(Known, SpecificShift);
+      Known = Known.intersectWith(SpecificShift);
       if (Known.isUnknown())
         break;
     }
   }
 
   Known.Zero.setHighBits(MinLeadingZeros);
   Known.One.setHighBits(MinLeadingOnes);
   return Known;

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

if (SrcOp.getValueSizeInBits() != Op.getScalarValueSizeInBits()) {
       Known = Known.trunc(Op.getScalarValueSizeInBits());
     }
     break;
   }
   case AArch64ISD::CSEL: {
     KnownBits Known2;
     Known = DAG.computeKnownBits(Op->getOperand(0), Depth + 1);
     Known2 = DAG.computeKnownBits(Op->getOperand(1), Depth + 1);
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   }
   case AArch64ISD::BICi: {
     // Compute the bit cleared value.
     uint64_t Mask =
         ~(Op->getConstantOperandVal(1) << Op->getConstantOperandVal(2));
     Known = DAG.computeKnownBits(Op->getOperand(0), Depth + 1);
     Known &= KnownBits::makeConstant(APInt(Known.getBitWidth(), Mask));

llvm/lib/Target/ARM/ARMISelLowering.cpp

case ARMISD::SUBE:
     break;
   case ARMISD::CMOV: {
     // Bits are known zero/one if known on the LHS and RHS.
     Known = DAG.computeKnownBits(Op.getOperand(0), Depth+1);
     if (Known.isUnknown())
       return;
 
     KnownBits KnownRHS = DAG.computeKnownBits(Op.getOperand(1), Depth+1);
-    Known = KnownBits::commonBits(Known, KnownRHS);
+    Known = Known.intersectWith(KnownRHS);
     return;
   }
   case ISD::INTRINSIC_W_CHAIN: {
     ConstantSDNode *CN = cast<ConstantSDNode>(Op->getOperand(1));
     Intrinsic::ID IntID = static_cast<Intrinsic::ID>(CN->getZExtValue());
     switch (IntID) {
     default: return;
     case Intrinsic::arm_ldaex:
if (Op.getOpcode() == ARMISD::CSINC)
       KnownOp1 = KnownBits::computeForAddSub(
           true, false, KnownOp1, KnownBits::makeConstant(APInt(32, 1)));
     else if (Op.getOpcode() == ARMISD::CSINV)
       std::swap(KnownOp1.Zero, KnownOp1.One);
     else if (Op.getOpcode() == ARMISD::CSNEG)
       KnownOp1 = KnownBits::mul(
           KnownOp1, KnownBits::makeConstant(APInt(32, -1)));
 
-    Known = KnownBits::commonBits(KnownOp0, KnownOp1);
+    Known = KnownOp0.intersectWith(KnownOp1);
     break;
   }
   }
 }
 
 bool ARMTargetLowering::targetShrinkDemandedConstant(
     SDValue Op, const APInt &DemandedBits, const APInt &DemandedElts,
     TargetLoweringOpt &TLO) const {

llvm/lib/Target/Lanai/LanaiISelLowering.cpp

void LanaiTargetLowering::computeKnownBitsForTargetNode(
   case LanaiISD::SETCC:
     Known = KnownBits(BitWidth);
     Known.Zero.setBits(1, BitWidth);
     break;
   case LanaiISD::SELECT_CC:
     KnownBits Known2;
     Known = DAG.computeKnownBits(Op->getOperand(0), Depth + 1);
     Known2 = DAG.computeKnownBits(Op->getOperand(1), Depth + 1);
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   }
 }

llvm/lib/Target/RISCV/RISCVISelLowering.cpp

void RISCVTargetLowering::computeKnownBitsForTargetNode(const SDValue Op,
   case RISCVISD::SELECT_CC: {
     Known = DAG.computeKnownBits(Op.getOperand(4), Depth + 1);
     // If we don't know any bits, early out.
     if (Known.isUnknown())
       break;
     KnownBits Known2 = DAG.computeKnownBits(Op.getOperand(3), Depth + 1);
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   }
   case RISCVISD::REMUW: {
     KnownBits Known2;
     Known = DAG.computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     Known2 = DAG.computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
     // We only care about the lower 32 bits.
     Known = KnownBits::urem(Known.trunc(32), Known2.trunc(32));

llvm/lib/Target/Sparc/SparcISelLowering.cpp

void SparcTargetLowering::computeKnownBitsForTargetNode
   default: break;
   case SPISD::SELECT_ICC:
   case SPISD::SELECT_XCC:
   case SPISD::SELECT_FCC:
     Known = DAG.computeKnownBits(Op.getOperand(1), Depth + 1);
     Known2 = DAG.computeKnownBits(Op.getOperand(0), Depth + 1);
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   }
 }
 
 // Look at LHS/RHS/CC and see if they are a lowered setcc instruction.  If so
 // set LHS/RHS and SPCC to the LHS/RHS of the setcc and SPCC to the condition.
 static void LookThroughSetCC(SDValue &LHS, SDValue &RHS,
                              ISD::CondCode CC, unsigned &SPCC) {

llvm/lib/Target/SystemZ/SystemZISelLowering.cpp

static void computeKnownBitsBinOp(const SDValue Op, KnownBits &Known,
                                   const SelectionDAG &DAG, unsigned Depth,
                                   unsigned OpNo) {
   APInt Src0DemE = getDemandedSrcElements(Op, DemandedElts, OpNo);
   APInt Src1DemE = getDemandedSrcElements(Op, DemandedElts, OpNo + 1);
   KnownBits LHSKnown =
       DAG.computeKnownBits(Op.getOperand(OpNo), Src0DemE, Depth + 1);
   KnownBits RHSKnown =
       DAG.computeKnownBits(Op.getOperand(OpNo + 1), Src1DemE, Depth + 1);
-  Known = KnownBits::commonBits(LHSKnown, RHSKnown);
+  Known = LHSKnown.intersectWith(RHSKnown);
 }
 
 void
 SystemZTargetLowering::computeKnownBitsForTargetNode(const SDValue Op,
                                                      KnownBits &Known,
                                                      const APInt &DemandedElts,
                                                      const SelectionDAG &DAG,
                                                      unsigned Depth) const {

llvm/lib/Target/X86/X86ISelLowering.cpp

case X86ISD::PACKUS: {
     getPackDemandedElts(VT, DemandedElts, DemandedLHS, DemandedRHS);
 
     Known.One = APInt::getAllOnes(BitWidth * 2);
     Known.Zero = APInt::getAllOnes(BitWidth * 2);
 
     KnownBits Known2;
     if (!!DemandedLHS) {
       Known2 = DAG.computeKnownBits(Op.getOperand(0), DemandedLHS, Depth + 1);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
     if (!!DemandedRHS) {
       Known2 = DAG.computeKnownBits(Op.getOperand(1), DemandedRHS, Depth + 1);
-      Known = KnownBits::commonBits(Known, Known2);
+      Known = Known.intersectWith(Known2);
     }
 
     if (Known.countMinLeadingZeros() < BitWidth)
       Known.resetAll();
     Known = Known.trunc(BitWidth);
     break;
   }
   case X86ISD::VBROADCAST: {
void X86TargetLowering::computeKnownBitsForTargetNode(const SDValue Op,
   case X86ISD::CMOV: {
     Known = DAG.computeKnownBits(Op.getOperand(1), Depth + 1);
     // If we don't know any bits, early out.
     if (Known.isUnknown())
       break;
     KnownBits Known2 = DAG.computeKnownBits(Op.getOperand(0), Depth + 1);
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(Known, Known2);
+    Known = Known.intersectWith(Known2);
     break;
   }
   case X86ISD::BEXTR:
   case X86ISD::BEXTRI: {
     SDValue Op0 = Op.getOperand(0);
     SDValue Op1 = Op.getOperand(1);
 
     if (auto* Cst1 = dyn_cast<ConstantSDNode>(Op1)) {
if (getTargetConstantBitsFromNode(Op, BitWidth, UndefElts, EltBits,
       for (unsigned I = 0; I != NumElts; ++I) {
         if (!DemandedElts[I])
           continue;
         if (UndefElts[I]) {
           Known.resetAll();
           break;
         }
         KnownBits Known2 = KnownBits::makeConstant(EltBits[I]);
-        Known = KnownBits::commonBits(Known, Known2);
+        Known = Known.intersectWith(Known2);
       }
       return;
     }
     break;
   }
   }
 
   // Handle target shuffles.
if (getTargetShuffleMask(Op.getNode(), VT.getSimpleVT(), true, Ops, Mask)) {
           DemandedOps[OpIdx].setBit(EltIdx);
         }
         // Known bits are the values that are shared by every demanded element.
         for (unsigned i = 0; i != NumOps && !Known.isUnknown(); ++i) {
           if (!DemandedOps[i])
             continue;
           KnownBits Known2 =
               DAG.computeKnownBits(Ops[i], DemandedOps[i], Depth + 1);
-          Known = KnownBits::commonBits(Known, Known2);
+          Known = Known.intersectWith(Known2);
         }
       }
     }
   }
 }
 
 unsigned X86TargetLowering::ComputeNumSignBitsForTargetNode(
     SDValue Op, const APInt &DemandedElts, const SelectionDAG &DAG,
if (CIdx && CIdx->getAPIntValue().ult(VecVT.getVectorNumElements())) {
 
       KnownBits KnownScl;
       unsigned NumSclBits = Scl.getScalarValueSizeInBits();
       APInt DemandedSclBits = OriginalDemandedBits.zext(NumSclBits);
       if (SimplifyDemandedBits(Scl, DemandedSclBits, KnownScl, TLO, Depth + 1))
         return true;
 
       KnownScl = KnownScl.trunc(VecVT.getScalarSizeInBits());
-      Known = KnownBits::commonBits(KnownVec, KnownScl);
+      Known = KnownVec.intersectWith(KnownScl);
       return false;
     }
     break;
   }
   case X86ISD::PACKSS:
     // PACKSS saturates to MIN/MAX integer values. So if we just want the
     // sign bit then we can just ask for the source operands sign bit.
     // TODO - add known bits handling.
static SDValue combineSetCC(SDNode *N, SelectionDAG &DAG,
 
   // Try and make unsigned vector comparison signed. On pre AVX512 targets there
   // only are unsigned comparisons (`PCMPGT`) and on AVX512 its often better to
   // use `PCMPGT` if the result is mean to stay in a vector (and if its going to
   // a mask, there are signed AVX512 comparisons).
   if (VT.isVector() && OpVT.isVector() && OpVT.isInteger()) {
     bool CanMakeSigned = false;
     if (ISD::isUnsignedIntSetCC(CC)) {
-      KnownBits CmpKnown = KnownBits::commonBits(DAG.computeKnownBits(LHS),
-                                                 DAG.computeKnownBits(RHS));
+      KnownBits CmpKnown =
+          DAG.computeKnownBits(LHS).intersectWith(DAG.computeKnownBits(RHS));
       // If we know LHS/RHS share the same sign bit at each element we can
       // make this signed.
       // NOTE: `computeKnownBits` on a vector type aggregates common bits
       // across all lanes. So a pattern where the sign varies from lane to
       // lane, but at each lane Sign(LHS) is known to equal Sign(RHS), will be
       // missed. We could get around this by demanding each lane
       // independently, but this isn't the most important optimization and
       // that may eat into compile time.

llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

auto CanonicalizeSelectConstant = [](Instruction *I, unsigned OpNo,
       }
       return ShrinkDemandedConstant(I, OpNo, DemandedMask);
     };
     if (CanonicalizeSelectConstant(I, 1, DemandedMask) ||
         CanonicalizeSelectConstant(I, 2, DemandedMask))
       return I;
 
     // Only known if known in both the LHS and RHS.
-    Known = KnownBits::commonBits(LHSKnown, RHSKnown);
+    Known = LHSKnown.intersectWith(RHSKnown);
     break;
   }
   case Instruction::Trunc: {
     // If we do not demand the high bits of a right-shifted and truncated value,
     // then we may be able to truncate it before the shift.
     Value *X;
     const APInt *C;
     if (match(I->getOperand(0), m_OneUse(m_LShr(m_Value(X), m_APInt(C))))) {