Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -1096,6 +1096,26 @@
   return nullptr;
 }
 
+/// Fold
+///   (1 << nbits) - 1
+/// Into:
+///   ~(-(1 << nbits))
+/// Because the `not` may end up being folded into `and`.
+/// The new shl is always nsw. And is nuw if old `and` was.
+static Instruction *canonicalizeLowbitMask(BinaryOperator &I,
+                                           InstCombiner::BuilderTy &Builder) {
+  Value *NBits;
+  if (!match(&I, m_Add(m_OneUse(m_Shl(m_One(), m_Value(NBits))), m_AllOnes())))
+    return nullptr;
+
+  Constant *MinusOne = Constant::getAllOnesValue(NBits->getType());
+  auto *Shl = cast<BinaryOperator>(Builder.CreateShl(MinusOne, NBits));
+  // Always NSW. But NUW propagates from `add`.
+  Shl->setHasNoSignedWrap();
+  Shl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
+  return BinaryOperator::CreateNot(Shl);
+}
+
 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   if (Value *V = SimplifyVectorOp(I))
@@ -1347,6 +1367,9 @@
     I.setHasNoUnsignedWrap(true);
   }
 
+  if (Instruction *V = canonicalizeLowbitMask(I, Builder))
+    return V;
+
   return Changed ? &I : nullptr;
 }
 
Index: test/Transforms/InstCombine/rem.ll
===================================================================
--- test/Transforms/InstCombine/rem.ll
+++ test/Transforms/InstCombine/rem.ll
@@ -314,10 +314,10 @@
 
 define i64 @test15(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test15(
-; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 1, [[Y:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[SHL]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
-; CHECK-NEXT:    [[UREM:%.*]] = zext i32 [[TMP2]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[Y:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], [[X:%.*]]
+; CHECK-NEXT:    [[UREM:%.*]] = zext i32 [[TMP3]] to i64
 ; CHECK-NEXT:    ret i64 [[UREM]]
 ;
   %shl = shl i32 1, %y
Index: test/Transforms/InstCombine/set-lowbits-mask-canonicalize.ll
===================================================================
--- test/Transforms/InstCombine/set-lowbits-mask-canonicalize.ll
+++ test/Transforms/InstCombine/set-lowbits-mask-canonicalize.ll
@@ -17,8 +17,8 @@
 
 define i32 @shl_add(i32 %nbits) {
 ; CHECK-LABEL: @shl_add(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl i32 1, %nbits
@@ -28,8 +28,8 @@
 
 define i32 @shl_add_nsw(i32 %nbits) {
 ; CHECK-LABEL: @shl_add_nsw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl i32 1, %nbits
@@ -39,8 +39,8 @@
 
 define i32 @shl_add_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_add_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl i32 1, %nbits
@@ -50,8 +50,8 @@
 
 define i32 @shl_add_nsw_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_add_nsw_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl i32 1, %nbits
@@ -63,8 +63,8 @@
 
 define i32 @shl_nsw_add(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_add(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nsw i32 1, %nbits
@@ -74,8 +74,8 @@
 
 define i32 @shl_nsw_add_nsw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_add_nsw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nsw i32 1, %nbits
@@ -85,8 +85,8 @@
 
 define i32 @shl_nsw_add_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_add_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nsw i32 1, %nbits
@@ -96,8 +96,8 @@
 
 define i32 @shl_nsw_add_nsw_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_add_nsw_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nsw i32 1, %nbits
@@ -109,8 +109,8 @@
 
 define i32 @shl_nuw_add(i32 %nbits) {
 ; CHECK-LABEL: @shl_nuw_add(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw i32 1, %nbits
@@ -120,8 +120,8 @@
 
 define i32 @shl_nuw_add_nsw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nuw_add_nsw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw i32 1, %nbits
@@ -131,8 +131,8 @@
 
 define i32 @shl_nuw_add_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nuw_add_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw i32 1, %nbits
@@ -142,8 +142,8 @@
 
 define i32 @shl_nuw_add_nsw_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nuw_add_nsw_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw i32 1, %nbits
@@ -155,8 +155,8 @@
 
 define i32 @shl_nsw_nuw_add(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_nuw_add(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw nsw i32 1, %nbits
@@ -166,8 +166,8 @@
 
 define i32 @shl_nsw_nuw_add_nsw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_nuw_add_nsw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw nsw i32 1, %nbits
@@ -177,8 +177,8 @@
 
 define i32 @shl_nsw_nuw_add_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_nuw_add_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw nsw i32 1, %nbits
@@ -188,8 +188,8 @@
 
 define i32 @shl_nsw_nuw_add_nsw_nuw(i32 %nbits) {
 ; CHECK-LABEL: @shl_nsw_nuw_add_nsw_nuw(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl nuw nsw i32 1, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add nuw nsw i32 [[SETBIT]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 -1, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
   %setbit = shl nuw nsw i32 1, %nbits
@@ -203,8 +203,8 @@
 
 define <2 x i32> @shl_add_vec(<2 x i32> %nbits) {
 ; CHECK-LABEL: @shl_add_vec(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl <2 x i32> <i32 1, i32 1>, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add <2 x i32> [[SETBIT]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw <2 x i32> <i32 -1, i32 -1>, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor <2 x i32> [[TMP1]], <i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <2 x i32> [[RET]]
 ;
   %setbit = shl <2 x i32> <i32 1, i32 1>, %nbits
@@ -214,8 +214,8 @@
 
 define <3 x i32> @shl_add_vec_undef(<3 x i32> %nbits) {
 ; CHECK-LABEL: @shl_add_vec_undef(
-; CHECK-NEXT:    [[SETBIT:%.*]] = shl <3 x i32> <i32 1, i32 undef, i32 1>, [[NBITS:%.*]]
-; CHECK-NEXT:    [[RET:%.*]] = add <3 x i32> [[SETBIT]], <i32 -1, i32 undef, i32 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nsw <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
+; CHECK-NEXT:    [[RET:%.*]] = xor <3 x i32> [[TMP1]], <i32 -1, i32 -1, i32 -1>
 ; CHECK-NEXT:    ret <3 x i32> [[RET]]
 ;
   %setbit = shl <3 x i32> <i32 1, i32 undef, i32 1>, %nbits