diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h
--- a/llvm/include/llvm/Analysis/ValueTracking.h
+++ b/llvm/include/llvm/Analysis/ValueTracking.h
@@ -205,6 +205,15 @@
                                    const Instruction *CxtI = nullptr,
                                    const DominatorTree *DT = nullptr);
 
+/// Get the upper bound on bit size for this Value \p Op as an unsigned integer.
+/// i.e.  x == zext(trunc(x to MaxSignificantBits) to bitwidth(x)).
+unsigned ComputeMaxUnsignedSignificantBits(const Value *Op,
+                                           const DataLayout &DL,
+                                           unsigned Depth = 0,
+                                           AssumptionCache *AC = nullptr,
+                                           const Instruction *CxtI = nullptr,
+                                           const DominatorTree *DT = nullptr);
+
 /// Map a call instruction to an intrinsic ID.  Libcalls which have equivalent
 /// intrinsics are treated as-if they were intrinsics.
 Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB,
diff --git a/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h b/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
--- a/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
+++ b/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
@@ -489,6 +489,13 @@
     return llvm::ComputeMaxSignificantBits(Op, DL, Depth, &AC, CxtI, &DT);
   }
 
+  unsigned
+  ComputeMaxUnsignedSignificantBits(const Value *Op, unsigned Depth = 0,
+                                    const Instruction *CxtI = nullptr) const {
+    return llvm::ComputeMaxUnsignedSignificantBits(Op, DL, Depth, &AC, CxtI,
+                                                   &DT);
+  }
+
   OverflowResult computeOverflowForUnsignedMul(const Value *LHS,
                                                const Value *RHS,
                                                const Instruction *CxtI) const {
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -396,6 +396,13 @@
   return V->getType()->getScalarSizeInBits() - SignBits + 1;
 }
 
+unsigned llvm::ComputeMaxUnsignedSignificantBits(
+    const Value *V, const DataLayout &DL, unsigned Depth, AssumptionCache *AC,
+    const Instruction *CxtI, const DominatorTree *DT) {
+  KnownBits KB = computeKnownBits(V, DL, Depth, AC, CxtI, DT);
+  return V->getType()->getScalarSizeInBits() - KB.countMinLeadingZeros();
+}
+
 static void computeKnownBitsAddSub(bool Add, const Value *Op0, const Value *Op1,
                                    bool NSW, const APInt &DemandedElts,
                                    KnownBits &KnownOut, KnownBits &Known2,
diff --git a/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
@@ -840,10 +840,10 @@
 }
 
 // Tries to perform
-//    (lshr (add (zext X), (zext Y)), K)
-//      -> (icmp ult (add X, Y), X)
+//    (lshr (add X, Y), K)
+//      -> (icmp ult (add (trunc X), (trunc Y)), X)
 //    where
-//      - The add's operands are zexts from a K-bits integer to a bigger type.
+//      - Only the K leading bits of X and Y can be non-zero.
 //      - The add is only used by the shr, or by iK (or narrower) truncates.
 //      - The lshr type has more than 2 bits (other types are boolean math).
 //      - K > 1
@@ -863,17 +863,15 @@
   const APInt *ShAmtAPInt = nullptr;
   Value *X = nullptr, *Y = nullptr;
   if (!match(ShiftAmt, m_APInt(ShAmtAPInt)) ||
-      !match(Add,
-             m_Add(m_OneUse(m_ZExt(m_Value(X))), m_OneUse(m_ZExt(m_Value(Y))))))
+      !match(Add, m_Add(m_OneUse(m_Value(X)), m_OneUse(m_Value(Y)))))
     return nullptr;
 
   const unsigned ShAmt = ShAmtAPInt->getZExtValue();
   if (ShAmt == 1)
     return nullptr;
 
-  // X/Y are zexts from `ShAmt`-sized ints.
-  if (X->getType()->getScalarSizeInBits() != ShAmt ||
-      Y->getType()->getScalarSizeInBits() != ShAmt)
+  if (ComputeMaxUnsignedSignificantBits(X, 0, &I) != ShAmt ||
+      ComputeMaxUnsignedSignificantBits(Y, 0, &I) != ShAmt)
     return nullptr;
 
   // Make sure that `Add` is only used by `I` and `ShAmt`-truncates.
@@ -893,6 +891,10 @@
   Instruction *AddInst = cast<Instruction>(Add);
   Builder.SetInsertPoint(AddInst);
 
+  Type *OpTy = Builder.getIntNTy(ShAmt);
+  X = Builder.CreateTrunc(X, OpTy);
+  Y = Builder.CreateTrunc(Y, OpTy);
+
   Value *NarrowAdd = Builder.CreateAdd(X, Y, "add.narrowed");
   Value *Overflow =
       Builder.CreateICmpULT(NarrowAdd, X, "add.narrowed.overflow");
diff --git a/llvm/test/Transforms/InstCombine/shift-add.ll b/llvm/test/Transforms/InstCombine/shift-add.ll
--- a/llvm/test/Transforms/InstCombine/shift-add.ll
+++ b/llvm/test/Transforms/InstCombine/shift-add.ll
@@ -493,10 +493,11 @@
 
 define i32 @lshr_16_add_known_16_leading_zeroes(i32 %a, i32 %b) {
 ; CHECK-LABEL: @lshr_16_add_known_16_leading_zeroes(
-; CHECK-NEXT:    [[A16:%.*]] = and i32 [[A:%.*]], 65535
-; CHECK-NEXT:    [[B16:%.*]] = and i32 [[B:%.*]], 65535
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[A16]], [[B16]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ADD]], 16
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[A:%.*]] to i16
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i32 [[B:%.*]] to i16
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i16 [[TMP1]], -1
+; CHECK-NEXT:    [[ADD_NARROWED_OVERFLOW:%.*]] = icmp ult i16 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[ADD_NARROWED_OVERFLOW]] to i32
 ; CHECK-NEXT:    ret i32 [[LSHR]]
 ;
   %a16 = and i32 %a, 65535 ; 0x65535
@@ -594,10 +595,11 @@
 
 define i64 @lshr_32_add_known_32_leading_zeroes(i64 %a, i64 %b) {
 ; CHECK-LABEL: @lshr_32_add_known_32_leading_zeroes(
-; CHECK-NEXT:    [[A32:%.*]] = and i64 [[A:%.*]], 4294967295
-; CHECK-NEXT:    [[B32:%.*]] = and i64 [[B:%.*]], 4294967295
-; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i64 [[A32]], [[B32]]
-; CHECK-NEXT:    [[LSHR:%.*]] = lshr i64 [[ADD]], 32
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[A:%.*]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[B:%.*]] to i32
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[ADD_NARROWED_OVERFLOW:%.*]] = icmp ult i32 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[ADD_NARROWED_OVERFLOW]] to i64
 ; CHECK-NEXT:    ret i64 [[LSHR]]
 ;
   %a32 = and i64 %a, 4294967295 ; 0xFFFFFFFF