[KnownBits] Implement accurate unsigned and signed max and min

[foad]

@regehr do you know anyone who could help me verify that this implementation is sound and precise? I have only exhaustively tested it up to 7 bits.

[lebedev.ri]

llvm/unittests/Support/KnownBitsTest.cpp

103

In D87034#2252330, @foad wrote:

I have only exhaustively tested it up to 7 bits.

For one-time testing you could bump this all the way to 16,
but i think 7 was plenty enough to catch any correctness issues.

111–114

i would think this should start from

KnownBits KnownUMax(KnownAnd) = 0;
KnownBits KnownUMin(KnownAnd) = -1;
KnownBits KnownSMax(KnownAnd) = INT_MIN;
KnownBits KnownSMin(KnownAnd) = INT_MAX;

[RKSimon]

Can you replace the implementations in SelectionDAG::computeKnownBits with these?

[foad]

llvm/unittests/Support/KnownBitsTest.cpp

103

The time is exponential in the number of bits. 6 bits took about 1 second. 7 bits took about 20 seconds. I doubt I would make it as far as 16 bits.

111–114

No, the way these values are initialized and updated with &= as we discover each real result, is independent of which function we're testing.

[nikic]

llvm/include/llvm/Support/KnownBits.h

178

const APInt &?

llvm/lib/Support/KnownBits.cpp

113

How does this differ from LHS.getMinValue().uge(RHS.getMaxValue())?

[nikic]

llvm/lib/Support/KnownBits.cpp

113

Generally I think this code should be structured something like this:

if (LHS.getMinValue().uge(RHS.getMaxValue()))
  return LHS;
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(L.Zero & R.Zero, L.One & R.One);

[foad]

Rebase.

[foad]

In D87034#2252539, @RKSimon wrote:

Can you replace the implementations in SelectionDAG::computeKnownBits with these?

Yes, that's the idea, and the same in GlobalISel and in ValueTracking.

[foad]

llvm/include/llvm/Support/KnownBits.h

178

Could do, but then I'd need to copy it in the implementation before calling clearLowBits. I don't know which is best.

[foad]

Simplify the implementation of KnownBits::umax.

llvm/lib/Support/KnownBits.cpp

113

Thanks! Can you simplify makeGE for me too? :)

[RKSimon]

In D87034#2252892, @foad wrote:

In D87034#2252539, @RKSimon wrote:

Can you replace the implementations in SelectionDAG::computeKnownBits with these?

Yes, that's the idea, and the same in GlobalISel and in ValueTracking.

Sorry, what I meant was are there any codegen test diffs if you replace SelectionDAG::computeKnownBits with this implementation?

llvm/include/llvm/Support/KnownBits.h

178

Its more common to use the const & approach

[foad]

In D87034#2254131, @RKSimon wrote:

In D87034#2252892, @foad wrote:

In D87034#2252539, @RKSimon wrote:

Can you replace the implementations in SelectionDAG::computeKnownBits with these?

Yes, that's the idea, and the same in GlobalISel and in ValueTracking.

Sorry, what I meant was are there any codegen test diffs if you replace SelectionDAG::computeKnownBits with this implementation?

No, using it in SelectionDAG doesn't affect any existing tests.

[foad]

Use const APInt &.

[lebedev.ri]

In D87034#2254852, @foad wrote:

In D87034#2254131, @RKSimon wrote:

In D87034#2252892, @foad wrote:

In D87034#2252539, @RKSimon wrote:

Can you replace the implementations in SelectionDAG::computeKnownBits with these?

Yes, that's the idea, and the same in GlobalISel and in ValueTracking.

Sorry, what I meant was are there any codegen test diffs if you replace SelectionDAG::computeKnownBits with this implementation?

No, using it in SelectionDAG doesn't affect any existing tests.

I think the question is, is this implementation expected to be identical to those, or better?
Regardless, i believe all those implementations should be replaced to use this in *this* patch,
to give better testing coverage.

[foad]

In D87034#2254864, @lebedev.ri wrote:

In D87034#2254852, @foad wrote:

In D87034#2254131, @RKSimon wrote:

In D87034#2252892, @foad wrote:

In D87034#2252539, @RKSimon wrote:

Can you replace the implementations in SelectionDAG::computeKnownBits with these?

Yes, that's the idea, and the same in GlobalISel and in ValueTracking.

Sorry, what I meant was are there any codegen test diffs if you replace SelectionDAG::computeKnownBits with this implementation?

No, using it in SelectionDAG doesn't affect any existing tests.

I think the question is, is this implementation expected to be identical to those, or better?
Regardless, i believe all those implementations should be replaced to use this in *this* patch,
to give better testing coverage.

The new implementation is supposed to be strictly better than the existing implementations -- though not necessarily in cases that occur very often in practice.

[foad]

Use it in SelectionDAG, GlobalISel and ValueTracking.

[lebedev.ri]

Thanks.
Unless others have more comments (@nikic?), i think this is good.

[nikic]

LG as well.

llvm/lib/Support/KnownBits.cpp

89

Personally I'd write this as unsigned N = (Zero | Val).countLeadingOnes() (with the comment something like "determine number of known leading bits"). Okay either way though.

[nikic]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3434

Maybe drop this early return. Even if one operand is unknown we can determine something here.

[foad]

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

3434

Yes, well spotted, but I am planning to do that in a separate patch because it affects some codegen tests.

[foad]

Simplify makeGE.

[nikic]

Contrary to my expectations, this change had a small but measurable compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=04ea680a8ccc4f9a4d7333cd712333960348c35b&to=5350e1b5096aa4707aa525baf7398d93b4a4f1a5&stat=instructions

Unfortunately, I have no idea why. I looked at callgrind profiles and the extra instructions (consistently) end up inside a DenseMap method (without changes to number of calls). Can't explain why that would happen, and the diff is not large enough to bother looking further.

I did end up applying this small cleanup while looking over the code again: https://github.com/llvm/llvm-project/commit/ddab4cd83ea31141aaada424dccf94278482ee88

[foad]

In D87034#2259745, @nikic wrote:

Contrary to my expectations, this change had a small but measurable compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=04ea680a8ccc4f9a4d7333cd712333960348c35b&to=5350e1b5096aa4707aa525baf7398d93b4a4f1a5&stat=instructions

Unfortunately, I have no idea why. I looked at callgrind profiles and the extra instructions (consistently) end up inside a DenseMap method (without changes to number of calls). Can't explain why that would happen, and the diff is not large enough to bother looking further.

I did end up applying this small cleanup while looking over the code again: https://github.com/llvm/llvm-project/commit/ddab4cd83ea31141aaada424dccf94278482ee88

Thanks. I wonder whether the number of calls to KnownBits and/or APInt constructors really affects compile time, as long as the APInts are all <= 64 bits (so they don't have to allocate any extra storage). If it does make a difference then KnownBits.h could probably be improved quite a lot e.g. by using rvalue references to avoid lots of copies.

Is there an easy way for me to reproduce one of the compile-time-tracker's tests on my own machine? E.g. compiling "sqlite3" under perf stat?

[nikic]

In D87034#2260562, @foad wrote:

Thanks. I wonder whether the number of calls to KnownBits and/or APInt constructors really affects compile time, as long as the APInts are all <= 64 bits (so they don't have to allocate any extra storage). If it does make a difference then KnownBits.h could probably be improved quite a lot e.g. by using rvalue references to avoid lots of copies.

Ah no, this was just intended as cleanup. It doesn't have a practical impact on compile-time.

Is there an easy way for me to reproduce one of the compile-time-tracker's tests on my own machine? E.g. compiling "sqlite3" under perf stat?

What I do is run ninja sqlite3 -v (or whatever the benchmark is) in test-suite and then prepend perf stat or valgrind --tool=callgrind before the printed compilation command. Results in something like...

valgrind --tool=callgrind /path/to/llvm-project/build/bin/clang -DNDEBUG -O3 -w -Werror=date-time -save-stats=obj -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DSQLITE_OMIT_LOAD_EXTENSION=1 -DSQLITE_THREADSAFE=0 -I. -save-stats=obj -MD -MT MultiSource/Applications/sqlite3/CMakeFiles/sqlite3.dir/sqlite3.c.o -MF MultiSource/Applications/sqlite3/CMakeFiles/sqlite3.dir/sqlite3.c.o.d -o MultiSource/Applications/sqlite3/CMakeFiles/sqlite3.dir/sqlite3.c.o -c ../MultiSource/Applications/sqlite3/sqlite3.c

llvm/include/llvm/Support/KnownBits.h

public:
 
   /// Return a KnownBits with the extracted bits
   /// [bitPosition,bitPosition+numBits).
   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
     return KnownBits(Zero.extractBits(NumBits, BitPosition),
                      One.extractBits(NumBits, BitPosition));
   }
 
+  /// Return KnownBits based on this, but updated given that the underlying
+  /// value is known to be greater than or equal to Val.
+  KnownBits makeGE(const APInt &Val) const;
+
   /// Returns the minimum number of trailing zero bits.
   unsigned countMinTrailingZeros() const {
     return Zero.countTrailingOnes();
   }
 
   /// Returns the minimum number of trailing one bits.
   unsigned countMinTrailingOnes() const {
     return One.countTrailingOnes();
public:
   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
   static KnownBits computeForAddCarry(
       const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
 
   /// Compute known bits resulting from adding LHS and RHS.
   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
                                     KnownBits RHS);
 
+  /// Compute known bits for umax(LHS, RHS).
+  static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
+
+  /// Compute known bits for umin(LHS, RHS).
+  static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
+
+  /// Compute known bits for smax(LHS, RHS).
+  static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
+
+  /// Compute known bits for smin(LHS, RHS).
+  static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
+
   /// Insert the bits from a smaller known bits starting at bitPosition.
   void insertBits(const KnownBits &SubBits, unsigned BitPosition) {
     Zero.insertBits(SubBits.Zero, BitPosition);
     One.insertBits(SubBits.One, BitPosition);
   }
 
   /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) {

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::UDiv: {
     break;
   }
   case Instruction::Select: {
     const Value *LHS = nullptr, *RHS = nullptr;
     SelectPatternFlavor SPF = matchSelectPattern(I, LHS, RHS).Flavor;
     if (SelectPatternResult::isMinOrMax(SPF)) {
       computeKnownBits(RHS, Known, Depth + 1, Q);
       computeKnownBits(LHS, Known2, Depth + 1, Q);
-    } else {
-      computeKnownBits(I->getOperand(2), Known, Depth + 1, Q);
-      computeKnownBits(I->getOperand(1), Known2, Depth + 1, Q);
-    }
+      switch (SPF) {
+      default:
+        llvm_unreachable("Unhandled select pattern flavor!");
+      case SPF_SMAX:
+        Known = KnownBits::smax(Known, Known2);
+        break;
+      case SPF_SMIN:
+        Known = KnownBits::smin(Known, Known2);
+        break;
+      case SPF_UMAX:
+        Known = KnownBits::umax(Known, Known2);
+        break;
+      case SPF_UMIN:
+        Known = KnownBits::umin(Known, Known2);
+        break;
+      }
+      break;
+    }
+
 
-    unsigned MaxHighOnes = 0;
-    unsigned MaxHighZeros = 0;
-    if (SPF == SPF_SMAX) {
-      // If both sides are negative, the result is negative.
-      if (Known.isNegative() && Known2.isNegative())
-        // We can derive a lower bound on the result by taking the max of the
-        // leading one bits.
-        MaxHighOnes =
-            std::max(Known.countMinLeadingOnes(), Known2.countMinLeadingOnes());
-      // If either side is non-negative, the result is non-negative.
-      else if (Known.isNonNegative() || Known2.isNonNegative())
-        MaxHighZeros = 1;
-    } else if (SPF == SPF_SMIN) {
-      // If both sides are non-negative, the result is non-negative.
-      if (Known.isNonNegative() && Known2.isNonNegative())
-        // We can derive an upper bound on the result by taking the max of the
-        // leading zero bits.
-        MaxHighZeros = std::max(Known.countMinLeadingZeros(),
-                                Known2.countMinLeadingZeros());
-      // If either side is negative, the result is negative.
-      else if (Known.isNegative() || Known2.isNegative())
-        MaxHighOnes = 1;
-    } else if (SPF == SPF_UMAX) {
-      // We can derive a lower bound on the result by taking the max of the
-      // leading one bits.
-      MaxHighOnes =
-          std::max(Known.countMinLeadingOnes(), Known2.countMinLeadingOnes());
-    } else if (SPF == SPF_UMIN) {
-      // We can derive an upper bound on the result by taking the max of the
-      // leading zero bits.
-      MaxHighZeros =
-          std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros());
-    } else if (SPF == SPF_ABS) {
+    // Only known if known in both the LHS and RHS.
+    Known.One &= Known2.One;
+    Known.Zero &= Known2.Zero;
+
+    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<Instruction>(RHS)))
-        MaxHighZeros = 1;
+        Known.Zero.setSignBit();
     }
 
-    // Only known if known in both the LHS and RHS.
-    Known.One &= Known2.One;
-    Known.Zero &= Known2.Zero;
-    if (MaxHighOnes > 0)
-      Known.One.setHighBits(MaxHighOnes);
-    if (MaxHighZeros > 0)
-      Known.Zero.setHighBits(MaxHighZeros);
     break;
   }
   case Instruction::FPTrunc:
   case Instruction::FPExt:
   case Instruction::FPToUI:
   case Instruction::FPToSI:
   case Instruction::SIToFP:
   case Instruction::UIToFP:

llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

case TargetOpcode::G_MUL: {
     Known.Zero.setHighBits(std::min(LeadZ, BitWidth));
     break;
   }
   case TargetOpcode::G_SELECT: {
     computeKnownBitsMin(MI.getOperand(2).getReg(), MI.getOperand(3).getReg(),
                         Known, DemandedElts, Depth + 1);
     break;
   }
-  case TargetOpcode::G_SMIN:
+  case TargetOpcode::G_SMIN: {
+    // TODO: Handle clamp pattern with number of sign bits
+    KnownBits KnownRHS;
+    computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
+                         Depth + 1);
+    computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
+                         Depth + 1);
+    Known = KnownBits::smin(Known, KnownRHS);
+    break;
+  }
   case TargetOpcode::G_SMAX: {
     // TODO: Handle clamp pattern with number of sign bits
-    computeKnownBitsMin(MI.getOperand(1).getReg(), MI.getOperand(2).getReg(),
-                        Known, DemandedElts, Depth + 1);
+    KnownBits KnownRHS;
+    computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
+                         Depth + 1);
+    computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
+                         Depth + 1);
+    Known = KnownBits::smax(Known, KnownRHS);
     break;
   }
   case TargetOpcode::G_UMIN: {
     KnownBits KnownRHS;
     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
                          DemandedElts, Depth + 1);
     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
                          DemandedElts, Depth + 1);
-
-    // UMIN - we know that the result will have the maximum of the
-    // known zero leading bits of the inputs.
-    unsigned LeadZero = Known.countMinLeadingZeros();
-    LeadZero = std::max(LeadZero, KnownRHS.countMinLeadingZeros());
-    Known &= KnownRHS;
-    Known.Zero.setHighBits(LeadZero);
+    Known = KnownBits::umin(Known, KnownRHS);
     break;
   }
   case TargetOpcode::G_UMAX: {
     KnownBits KnownRHS;
     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
                          DemandedElts, Depth + 1);
     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
                          DemandedElts, Depth + 1);
-
-    // UMAX - we know that the result will have the maximum of the
-    // known one leading bits of the inputs.
-    unsigned LeadOne = Known.countMinLeadingOnes();
-    LeadOne = std::max(LeadOne, KnownRHS.countMinLeadingOnes());
-    Known.Zero &= KnownRHS.Zero;
-    Known.One &= KnownRHS.One;
-    Known.One.setHighBits(LeadOne);
+    Known = KnownBits::umax(Known, KnownRHS);
     break;
   }
   case TargetOpcode::G_FCMP:
   case TargetOpcode::G_ICMP: {
     if (TL.getBooleanContents(DstTy.isVector(),
                               Opcode == TargetOpcode::G_FCMP) ==
             TargetLowering::ZeroOrOneBooleanContent &&
         BitWidth > 1)

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

if (Known2.One.getBoolValue()) {
       Known.Zero = APInt::getSignMask(BitWidth);
       break;
     }
     break;
   }
   case ISD::UMIN: {
     Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
-
-    // UMIN - we know that the result will have the maximum of the
-    // known zero leading bits of the inputs.
-    unsigned LeadZero = Known.countMinLeadingZeros();
-    LeadZero = std::max(LeadZero, Known2.countMinLeadingZeros());
-
-    Known.Zero &= Known2.Zero;
-    Known.One &= Known2.One;
-    Known.Zero.setHighBits(LeadZero);
+    Known = KnownBits::umin(Known, Known2);
     break;
   }
   case ISD::UMAX: {
     Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
-
-    // UMAX - we know that the result will have the maximum of the
-    // known one leading bits of the inputs.
-    unsigned LeadOne = Known.countMinLeadingOnes();
-    LeadOne = std::max(LeadOne, Known2.countMinLeadingOnes());
-
-    Known.Zero &= Known2.Zero;
-    Known.One &= Known2.One;
-    Known.One.setHighBits(LeadOne);
+    Known = KnownBits::umax(Known, Known2);
     break;
   }
   case ISD::SMIN:
   case ISD::SMAX: {
     // If we have a clamp pattern, we know that the number of sign bits will be
     // the minimum of the clamp min/max range.
     bool IsMax = (Opcode == ISD::SMAX);
     ConstantSDNode *CstLow = nullptr, *CstHigh = nullptr;
if (CstLow && CstHigh) {
         }
         if (ValueLow.isNonNegative() && ValueHigh.isNonNegative()) {
           Known.Zero.setHighBits(MinSignBits);
           break;
         }
       }
     }
 
-    // Fallback - just get the shared known bits of the operands.
     Known = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
     if (Known.isUnknown()) break; // Early-out
     Known2 = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
-    Known.Zero &= Known2.Zero;
-    Known.One &= Known2.One;
+    if (IsMax)
+      Known = KnownBits::smax(Known, Known2);
+    else
+      Known = KnownBits::smin(Known, Known2);
     break;
   }
   case ISD::FrameIndex:
   case ISD::TargetFrameIndex:
     TLI->computeKnownBitsForFrameIndex(cast<FrameIndexSDNode>(Op)->getIndex(),
                                        Known, getMachineFunction());
     break;
 

llvm/lib/Support/KnownBits.cpp

if (NSW) {
       else if (LHS.isNegative() && RHS.isNegative())
         KnownOut.makeNegative();
     }
   }
 
   return KnownOut;
 }
 
+KnownBits KnownBits::makeGE(const APInt &Val) const {
+  // Count the number of leading bit positions where our underlying value is
+  // known to be less than or equal to Val.
+  unsigned N = (Zero | Val).countLeadingOnes();
+
+  // For each of those bit positions, if Val has a 1 in that bit then our
+  // underlying value must also have a 1.
+  APInt MaskedVal(Val);
+  MaskedVal.clearLowBits(getBitWidth() - N);
+  return KnownBits(Zero, One | MaskedVal);
+}
+
+KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) {
+  // If we can prove that LHS >= RHS then use LHS as the result. Likewise for
+  // RHS. Ideally our caller would already have spotted these cases and
+  // optimized away the umax operation, but we handle them here for
+  // completeness.
+  if (LHS.getMinValue().uge(RHS.getMaxValue()))
+    return LHS;
+  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(L.Zero & R.Zero, L.One & R.One);
+}
+
+KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) {
+  // Flip the range of values: [0, 0xFFFFFFFF] <-> [0xFFFFFFFF, 0]
+  auto Flip = [](KnownBits Val) { return KnownBits(Val.One, Val.Zero); };
+  return Flip(umax(Flip(LHS), Flip(RHS)));
+}
+
+KnownBits KnownBits::smax(const KnownBits &LHS, const KnownBits &RHS) {
+  // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0, 0xFFFFFFFF]
+  auto Flip = [](KnownBits Val) {
+    unsigned SignBitPosition = Val.getBitWidth() - 1;
+    APInt Zero = Val.Zero;
+    APInt One = Val.One;
+    Zero.setBitVal(SignBitPosition, Val.One[SignBitPosition]);
+    One.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
+    return KnownBits(Zero, One);
+  };
+  return Flip(umax(Flip(LHS), Flip(RHS)));
+}
+
+KnownBits KnownBits::smin(const KnownBits &LHS, const KnownBits &RHS) {
+  // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0xFFFFFFFF, 0]
+  auto Flip = [](KnownBits Val) {
+    unsigned SignBitPosition = Val.getBitWidth() - 1;
+    APInt Zero = Val.One;
+    APInt One = Val.Zero;
+    Zero.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
+    One.setBitVal(SignBitPosition, Val.One[SignBitPosition]);
+    return KnownBits(Zero, One);
+  };
+  return Flip(umax(Flip(LHS), Flip(RHS)));
+}
+
 KnownBits &KnownBits::operator&=(const KnownBits &RHS) {
   // Result bit is 0 if either operand bit is 0.
   Zero |= RHS.Zero;
   // Result bit is 1 if both operand bits are 1.
   One &= RHS.One;
   return *this;
 }
 

llvm/unittests/CodeGen/GlobalISel/KnownBitsTest.cpp

)";
   if (!TM)
     return;
 
   Register CopyUMax = Copies[Copies.size() - 1];
   GISelKnownBits Info(*MF);
 
   KnownBits KnownUmax = Info.getKnownBits(CopyUMax);
   EXPECT_EQ(64u, KnownUmax.getBitWidth());
-  EXPECT_EQ(0u, KnownUmax.Zero.getZExtValue());
+  EXPECT_EQ(0xffu, KnownUmax.Zero.getZExtValue());
   EXPECT_EQ(0xffffffffffffff00, KnownUmax.One.getZExtValue());
 
-  EXPECT_EQ(0u, KnownUmax.Zero.getZExtValue());
+  EXPECT_EQ(0xffu, KnownUmax.Zero.getZExtValue());
   EXPECT_EQ(0xffffffffffffff00, KnownUmax.One.getZExtValue());
 }

llvm/unittests/Support/KnownBitsTest.cpp

 }
 
 TEST(KnownBitsTest, AddSubExhaustive) {
   TestAddSubExhaustive(true);
   TestAddSubExhaustive(false);
 }
 
 TEST(KnownBitsTest, BinaryExhaustive) {
   unsigned Bits = 4;
   ForeachKnownBits(Bits, [&](const KnownBits &Known1) {
     ForeachKnownBits(Bits, [&](const KnownBits &Known2) {
-      KnownBits KnownAnd(Bits), KnownOr(Bits), KnownXor(Bits);
+      KnownBits KnownAnd(Bits);
       KnownAnd.Zero.setAllBits();
       KnownAnd.One.setAllBits();
-      KnownOr.Zero.setAllBits();
-      KnownOr.One.setAllBits();
-      KnownXor.Zero.setAllBits();
-      KnownXor.One.setAllBits();
+      KnownBits KnownOr(KnownAnd);
+      KnownBits KnownXor(KnownAnd);
+      KnownBits KnownUMax(KnownAnd);
+      KnownBits KnownUMin(KnownAnd);
+      KnownBits KnownSMax(KnownAnd);
+      KnownBits KnownSMin(KnownAnd);
 
       ForeachNumInKnownBits(Known1, [&](const APInt &N1) {
         ForeachNumInKnownBits(Known2, [&](const APInt &N2) {
           APInt Res;
 
           Res = N1 & N2;
           KnownAnd.One &= Res;
           KnownAnd.Zero &= ~Res;
 
           Res = N1 | N2;
           KnownOr.One &= Res;
           KnownOr.Zero &= ~Res;
 
           Res = N1 ^ N2;
           KnownXor.One &= Res;
           KnownXor.Zero &= ~Res;
+
+          Res = APIntOps::umax(N1, N2);
+          KnownUMax.One &= Res;
+          KnownUMax.Zero &= ~Res;
+
+          Res = APIntOps::umin(N1, N2);
+          KnownUMin.One &= Res;
+          KnownUMin.Zero &= ~Res;
+
+          Res = APIntOps::smax(N1, N2);
+          KnownSMax.One &= Res;
+          KnownSMax.Zero &= ~Res;
+
+          Res = APIntOps::smin(N1, N2);
+          KnownSMin.One &= Res;
+          KnownSMin.Zero &= ~Res;
         });
       });
 
       KnownBits ComputedAnd = Known1 & Known2;
       EXPECT_EQ(KnownAnd.Zero, ComputedAnd.Zero);
       EXPECT_EQ(KnownAnd.One, ComputedAnd.One);
 
       KnownBits ComputedOr = Known1 | Known2;
       EXPECT_EQ(KnownOr.Zero, ComputedOr.Zero);
       EXPECT_EQ(KnownOr.One, ComputedOr.One);
 
       KnownBits ComputedXor = Known1 ^ Known2;
       EXPECT_EQ(KnownXor.Zero, ComputedXor.Zero);
       EXPECT_EQ(KnownXor.One, ComputedXor.One);
+
+      KnownBits ComputedUMax = KnownBits::umax(Known1, Known2);
+      EXPECT_EQ(KnownUMax.Zero, ComputedUMax.Zero);
+      EXPECT_EQ(KnownUMax.One, ComputedUMax.One);
+
+      KnownBits ComputedUMin = KnownBits::umin(Known1, Known2);
+      EXPECT_EQ(KnownUMin.Zero, ComputedUMin.Zero);
+      EXPECT_EQ(KnownUMin.One, ComputedUMin.One);
+
+      KnownBits ComputedSMax = KnownBits::smax(Known1, Known2);
+      EXPECT_EQ(KnownSMax.Zero, ComputedSMax.Zero);
+      EXPECT_EQ(KnownSMax.One, ComputedSMax.One);
+
+      KnownBits ComputedSMin = KnownBits::smin(Known1, Known2);
+      EXPECT_EQ(KnownSMin.Zero, ComputedSMin.Zero);
+      EXPECT_EQ(KnownSMin.One, ComputedSMin.One);
     });
   });
 }
 
 TEST(KnownBitsTest, GetMinMaxVal) {
   unsigned Bits = 4;
   ForeachKnownBits(Bits, [&](const KnownBits &Known) {
     APInt Min = APInt::getMaxValue(Bits);