diff --git a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp
@@ -261,6 +261,82 @@
   return 0;
 }
 
+// X mul 2^C -> X << C
+static Instruction *foldMulPow2Cst(Value *Op0, Value *Op1,
+                                   const BinaryOperator &I, InstCombiner &IC) {
+  Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
+  if (!C1)
+    llvm_unreachable("Failed to constant fold mul -> logbase2");
+  BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, C1);
+  if (I.hasNoUnsignedWrap())
+    Shl->setHasNoUnsignedWrap();
+  if (I.hasNoSignedWrap() && !cast<Constant>(Op1)->isMinSignedValue())
+    Shl->setHasNoSignedWrap();
+  return Shl;
+}
+
+// X mul (C1 << N), where C1 is "1<<C2"  -->  X << (N+C2)
+// X mul (zext (C1 << N)), where C1 is "1<<C2"  -->  X << (N+C2)
+static Instruction *foldMulShl(Value *Op0, Value *Op1, const BinaryOperator &I,
+                               InstCombiner &IC) {
+  Value *ShiftLeft;
+  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
+    ShiftLeft = Op1;
+
+  Constant *CI;
+  Value *N;
+  if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
+    llvm_unreachable("match should never fail here!");
+  Constant *Log2Base = getLogBase2(N->getType(), CI);
+  if (!Log2Base)
+    llvm_unreachable("getLogBase2 should never fail here!");
+  N = IC.Builder.CreateAdd(N, Log2Base);
+  if (Op1 != ShiftLeft)
+    N = IC.Builder.CreateZExt(N, Op1->getType());
+  BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, N);
+  if (I.hasNoUnsignedWrap())
+    Shl->setHasNoUnsignedWrap();
+  if (I.hasNoSignedWrap() && cast<ShlOperator>(ShiftLeft)->hasNoSignedWrap())
+    Shl->setHasNoSignedWrap();
+  return Shl;
+}
+
+// Recursively visits the possible right hand operands of a mul
+// instruction, seeing through select instructions, to determine if we can
+// replace the mul with something simpler. If we find that an operand is not
+// able to simplify the mul, we abort the entire transformation.
+static size_t visitMulOperand(Value *Op0, Value *Op1,
+                              SmallVectorImpl<OperandFoldAction> &Actions,
+                              unsigned Depth = 0) {
+  // Check to see if this is a multiplication with an exact power of 2, if so,
+  // convert to a left shift.
+  if (match(Op1, m_Power2())) {
+    Actions.push_back(OperandFoldAction(foldMulPow2Cst, Op1));
+    return Actions.size();
+  }
+
+  // X mul (C1 << N), where C1 is "1<<C2"  -->  X << (N+C2)
+  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
+      match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
+    Actions.push_back(OperandFoldAction(foldMulShl, Op1));
+    return Actions.size();
+  }
+
+  // The remaining tests are all recursive, so bail out if we hit the limit.
+  if (Depth++ == MaxDepth)
+    return 0;
+
+  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
+    if (size_t LHSIdx = visitMulOperand(Op0, SI->getOperand(1), Actions, Depth))
+      if (visitMulOperand(Op0, SI->getOperand(2), Actions, Depth)) {
+        Actions.push_back(OperandFoldAction(nullptr, Op1, LHSIdx - 1));
+        return Actions.size();
+      }
+
+  return 0;
+}
+
+
 // TODO: This is a specific form of a much more general pattern.
 //       We could detect a select with any binop identity constant, or we
 //       could use SimplifyBinOp to see if either arm of the select reduces.
@@ -397,6 +473,17 @@
   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
     return replaceInstUsesWith(I, FoldedMul);
 
+  // (LHS mul (select (select (...)))) -> (LHS << (select (select (...))))
+  SmallVector<OperandFoldAction, 6> MulActions;
+  if (visitMulOperand(Op0, Op1, MulActions))
+    if (Instruction *Inst = combineActions(Op0, I, MulActions, *this))
+      return Inst;
+  MulActions.clear();
+  // ((select (select (...))) mul LHS) -> (LHS << (select (select (...))))
+  if (visitMulOperand(Op1, Op0, MulActions))
+    if (Instruction *Inst = combineActions(Op1, I, MulActions, *this))
+      return Inst;
+
   // Simplify mul instructions with a constant RHS.
   if (isa<Constant>(Op1)) {
     // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
@@ -469,28 +556,6 @@
   if (I.getType()->isIntOrIntVectorTy(1))
     return BinaryOperator::CreateAnd(Op0, Op1);
 
-  // X*(1 << Y) --> X << Y
-  // (1 << Y)*X --> X << Y
-  {
-    Value *Y;
-    BinaryOperator *BO = nullptr;
-    bool ShlNSW = false;
-    if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
-      BO = BinaryOperator::CreateShl(Op1, Y);
-      ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
-    } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
-      BO = BinaryOperator::CreateShl(Op0, Y);
-      ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
-    }
-    if (BO) {
-      if (I.hasNoUnsignedWrap())
-        BO->setHasNoUnsignedWrap();
-      if (I.hasNoSignedWrap() && ShlNSW)
-        BO->setHasNoSignedWrap();
-      return BO;
-    }
-  }
-
   // (bool X) * Y --> X ? Y : 0
   // Y * (bool X) --> X ? Y : 0
   if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
diff --git a/llvm/test/Transforms/InstCombine/mul.ll b/llvm/test/Transforms/InstCombine/mul.ll
--- a/llvm/test/Transforms/InstCombine/mul.ll
+++ b/llvm/test/Transforms/InstCombine/mul.ll
@@ -609,12 +609,12 @@
 }
 
 
-; TODO. 'select + mul' -> 'select + shl' for power of twos
+; 'select + mul' -> 'select + shl' for power of twos
 
 define i32 @shift_if_power2(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @shift_if_power2(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 16, i32 4
-; CHECK-NEXT:    [[R:%.*]] = mul i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], i32 4, i32 2
+; CHECK-NEXT:    [[R:%.*]] = shl i32 [[X:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 16, i32 4
@@ -624,8 +624,8 @@
 
 define i32 @shift_if_power2_nuw(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @shift_if_power2_nuw(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 16, i32 4
-; CHECK-NEXT:    [[R:%.*]] = mul nuw i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], i32 4, i32 2
+; CHECK-NEXT:    [[R:%.*]] = shl nuw i32 [[X:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 16, i32 4
@@ -635,8 +635,8 @@
 
 define i32 @shift_if_power2_nsw(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @shift_if_power2_nsw(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 16, i32 4
-; CHECK-NEXT:    [[R:%.*]] = mul nsw i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], i32 4, i32 2
+; CHECK-NEXT:    [[R:%.*]] = shl nsw i32 [[X:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 16, i32 4
@@ -646,8 +646,8 @@
 
 define i32 @shift_if_power2_nuw_nsw(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @shift_if_power2_nuw_nsw(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 16, i32 4
-; CHECK-NEXT:    [[R:%.*]] = mul nuw nsw i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], i32 4, i32 2
+; CHECK-NEXT:    [[R:%.*]] = shl nuw nsw i32 [[X:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 16, i32 4
@@ -655,12 +655,23 @@
   ret i32 %r
 }
 
+define i32 @shift_if_power2_nuw_nsw_min(i32 %x, i1 %cond) {
+; CHECK-LABEL: @shift_if_power2_nuw_nsw_min(
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 -2, i32 -2147483648
+; CHECK-NEXT:    [[R:%.*]] = mul nuw nsw i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %sel = select i1 %cond, i32 -2, i32 -2147483648
+  %r = mul nuw nsw i32 %sel, %x
+  ret i32 %r
+}
+
 define i32 @shift_if_power2_double_select(i32 %x, i32 %y, i1 %cond1, i1 %cond2) {
 ; CHECK-LABEL: @shift_if_power2_double_select(
-; CHECK-NEXT:    [[SHL_RES:%.*]] = shl i32 8, [[Y:%.*]]
-; CHECK-NEXT:    [[SEL1:%.*]] = select i1 [[COND1:%.*]], i32 [[SHL_RES]], i32 1024
-; CHECK-NEXT:    [[SEL2:%.*]] = select i1 [[COND2:%.*]], i32 16, i32 [[SEL1]]
-; CHECK-NEXT:    [[R:%.*]] = mul nuw i32 [[SEL2]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[Y:%.*]], 3
+; CHECK-NEXT:    [[DOTV:%.*]] = select i1 [[COND1:%.*]], i32 [[TMP1]], i32 10
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND2:%.*]], i32 4, i32 [[DOTV]]
+; CHECK-NEXT:    [[R:%.*]] = shl nuw i32 [[X:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %shl.res = shl i32 8, %y
@@ -670,10 +681,27 @@
   ret i32 %r
 }
 
+define i32 @shift_if_power2_double_select_zext(i32 %x, i16 %y, i1 %cond1, i1 %cond2) {
+; CHECK-LABEL: @shift_if_power2_double_select_zext(
+; CHECK-NEXT:    [[TMP1:%.*]] = add i16 [[Y:%.*]], 3
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[TMP1]] to i32
+; CHECK-NEXT:    [[DOTV:%.*]] = select i1 [[COND1:%.*]], i32 [[TMP2]], i32 10
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND2:%.*]], i32 4, i32 [[DOTV]]
+; CHECK-NEXT:    [[R:%.*]] = shl nuw i32 [[X:%.*]], [[R_V]]
+; CHECK-NEXT:    ret i32 [[R]]
+;
+  %shl.res = shl i16 8, %y
+  %shl = zext i16 %shl.res to i32
+  %sel1 = select i1 %cond1, i32 %shl, i32 1024
+  %sel2 = select i1 %cond2, i32 16, i32 %sel1
+  %r = mul nuw i32 %x, %sel2
+  ret i32 %r
+}
+
 define i32 @shift_if_power2_zero(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @shift_if_power2_zero(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 1, i32 4
-; CHECK-NEXT:    [[R:%.*]] = mul i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], i32 0, i32 2
+; CHECK-NEXT:    [[R:%.*]] = shl i32 [[X:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 1, i32 4
@@ -683,8 +711,8 @@
 
 define <2 x i8> @shift_if_power2_vector(<2 x i8> %px, i1 %cond) {
 ; CHECK-LABEL: @shift_if_power2_vector(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 16, i8 4>, <2 x i8> <i8 1, i8 32>
-; CHECK-NEXT:    [[R:%.*]] = mul <2 x i8> [[SEL]], [[PX:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 4, i8 2>, <2 x i8> <i8 0, i8 5>
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i8> [[PX:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %sel = select i1 %cond, <2 x i8> <i8 16, i8 4>, <2 x i8> <i8 1, i8 32>
@@ -696,7 +724,8 @@
 ; CHECK-LABEL: @shift_if_extra_use(
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], i32 4, i32 128
 ; CHECK-NEXT:    call void @use32(i32 [[SEL]])
-; CHECK-NEXT:    [[R:%.*]] = mul i32 [[SEL]], [[X:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND]], i32 2, i32 7
+; CHECK-NEXT:    [[R:%.*]] = shl i32 [[X:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %sel = select i1 %cond, i32 4, i32 128
@@ -748,8 +777,8 @@
 
 define <2 x i8> @shift_if_undef_vector(<2 x i8> %px, i1 %cond) {
 ; CHECK-LABEL: @shift_if_undef_vector(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 16, i8 4>, <2 x i8> <i8 undef, i8 32>
-; CHECK-NEXT:    [[R:%.*]] = mul <2 x i8> [[SEL]], [[PX:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 4, i8 2>, <2 x i8> <i8 undef, i8 5>
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i8> [[PX:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %sel = select i1 %cond, <2 x i8> <i8 16, i8 4>, <2 x i8> <i8 undef, i8 32>
@@ -759,8 +788,8 @@
 
 define <2 x i8> @shift_if_different_lanes_undef_vector(<2 x i8> %px, i1 %cond) {
 ; CHECK-LABEL: @shift_if_different_lanes_undef_vector(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 16, i8 undef>, <2 x i8> <i8 undef, i8 32>
-; CHECK-NEXT:    [[R:%.*]] = mul <2 x i8> [[SEL]], [[PX:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 4, i8 undef>, <2 x i8> <i8 undef, i8 5>
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i8> [[PX:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %sel = select i1 %cond, <2 x i8> <i8 16, i8 undef>, <2 x i8> <i8 undef, i8 32>
@@ -770,8 +799,8 @@
 
 define <2 x i8> @shift_if_same_lane_undef_vector(<2 x i8> %px, i1 %cond) {
 ; CHECK-LABEL: @shift_if_same_lane_undef_vector(
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 undef, i8 4>, <2 x i8> <i8 undef, i8 32>
-; CHECK-NEXT:    [[R:%.*]] = mul <2 x i8> [[SEL]], [[PX:%.*]]
+; CHECK-NEXT:    [[R_V:%.*]] = select i1 [[COND:%.*]], <2 x i8> <i8 undef, i8 2>, <2 x i8> <i8 undef, i8 5>
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i8> [[PX:%.*]], [[R_V]]
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %sel = select i1 %cond, <2 x i8> <i8 undef, i8 4>, <2 x i8> <i8 undef, i8 32>